/** Keeps the O(D^2) Myers trace to a few MB, well inside the Worker memory limit. */
const MAX_EDIT_DISTANCE = 1000;
const NO_MATCH = -1;
const NEWLINE = 10;
export class MergeTooComplexError extends Error {}
/** 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[]): Int32Array {
const matches = new Int32Array(left.length).fill(NO_MATCH);
let prefix = 0;
while (prefix < left.length && prefix < right.length && left[prefix] === right[prefix]) {
matches[prefix] = prefix;
prefix++;
}
let suffix = 0;
while (
suffix < left.length - prefix &&
suffix < right.length - prefix &&
left[left.length - 1 - suffix] === right[right.length - 1 - suffix]
) {
matches[left.length - 1 - suffix] = right.length - 1 - suffix;
suffix++;