/** Keeps the O(D^2) Myers trace to a few MB, well inside the Worker memory limit. */
const MAX_EDIT_DISTANCE = 1000;
/** Bounds total Myers work (diagonal visits plus snake steps) per file, since cost is O((N+M)·D). */
const MAX_DIFF_WORK = 4_000_000;
const MAX_MERGE_LINES = 50_000;
/** Total Myers work across every file of one merge (or of all merges sharing a budget). */
const MAX_TOTAL_DIFF_WORK = 20_000_000;
export type DiffBudget = { diffWork: number };
const NO_MATCH = -1;
const NEWLINE = 10;
export class MergeTooComplexError extends Error {}
/** Labels come from branch names; strip line breaks so a label can never forge a marker line. */
function markerLabel(label: string): string {
return label.replace(/[\r\n]/g, " ");
}
/** Splits text into lines that keep their terminators, so joining them reproduces the input exactly. */
export function splitLines(text: string): string[] {
const lines: string[] = [];
let start = 0;
for (let index = 0; index < text.length; index++) {
if (text.charCodeAt(index) === NEWLINE) {
lines.push(text.slice(start, index + 1));
start = index + 1;
}
}
if (start < text.length) lines.push(text.slice(start));
return lines;
}
/**
* Myers' O(ND) diff over interned lines, returning for each `left` index the matched `right` index
* (or -1). Throws once the edit distance exceeds the budget so callers can fall back to real git.
*/
function lineMatches(left: number[], right: number[], budget: DiffBudget): Int32Array {
const matches = new Int32Array(left.length).fill(NO_MATCH);
let prefix = 0;