diffutil.ts 86.1%

87 of 101 lines run, 2 of 2 functions, 34 of 36 branches · run #26 on main · run missed

// A line diff (Myers, O(ND)) used to align blame computed on the base
// version of a file with the lines of the editor's current text.

/** For each line of `after`, the index of the matching line in `before`, or -1 when new. */
export function alignLines(before: string[], after: string[]): number[] {
  const n = before.length;
  const m = after.length;
  const result = new Array<number>(m).fill(-1);
  if (n === 0 || m === 0) {
    return result;
  }
  // Trim common prefix and suffix first; they dominate real edits.
  let start = 0;
  while (start < n && start < m && before[start] === after[start]) {
    result[start] = start;
    start++;
  }
  let endB = n;
  let endA = m;
  while (endB > start && endA > start && before[endB - 1] === after[endA - 1]) {
    endB--;
    endA--;
    result[endA] = endB;
  }
  const a = before.slice(start, endB);
  const b = after.slice(start, endA);
  if (a.length === 0 || b.length === 0) {
    return result;
  }
  // Bail out to positional matching on huge middles to bound memory.
  if (a.length * b.length > 25_000_000) {
    for (let i = 0; i < Math.min(a.length, b.length); i++) {
      if (a[i] === b[i]) {
        result[start + i] = start + i;
      }
    }
    return result;
  }
  for (const [i, j] of myers(a, b)) {
    result[start + j] = start + i;
  }
  return result;
}

/** Pairs (i, j) of equal lines a[i] === b[j] along a shortest edit script. */
function myers(a: string[], b: string[]): [number, number][] {
  const n = a.length;
  const m = b.length;
  const max = n + m;
  const offset = max;
  const trace: Int32Array[] = [];
  let v = new Int32Array(2 * max + 2);
  v[offset + 1] = 0;
  outer: for (let d = 0; d <= max; d++) {
    const snapshot = v.slice();
    trace.push(snapshot);
    for (let k = -d; k <= d; k += 2) {
      let x: number;
      if (k === -d || (k !== d && v[offset + k - 1] < v[offset + k + 1])) {
        x = v[offset + k + 1];
      } else {
        x = v[offset + k - 1] + 1;
      }
      let y = x - k;
      while (x < n && y < m && a[x] === b[y]) {
        x++;
        y++;
      }
      v[offset + k] = x;
      if (x >= n && y >= m) {
        break outer;
      }
    }
  }
  // Backtrack.
  const pairs: [number, number][] = [];
  let x = n;
  let y = m;
  for (let d = trace.length - 1; d >= 0; d--) {
    const vd = trace[d];
    const k = x - y;
    let prevK: number;
    if (k === -d || (k !== d && vd[offset + k - 1] < vd[offset + k + 1])) {
      prevK = k + 1;
    } else {
      prevK = k - 1;
    }
    const prevX = vd[offset + prevK];
    const prevY = prevX - prevK;
    while (x > prevX && y > prevY) {
      x--;
      y--;
      pairs.push([x, y]);
    }
    if (d > 0) {
      x = prevX;
      y = prevY;
    }
  }
  return pairs.reverse();
}

1	0×	// A line diff (Myers, O(ND)) used to align blame computed on the base
2	0×	// version of a file with the lines of the editor's current text.
3	1×
4	0×	/** For each line of `after`, the index of the matching line in `before`, or -1 when new. */
5	1×	export function alignLines(before: string[], after: string[]): number[] {
6	1×	const n = before.length;
7	1×	const m = after.length;
8	1×	const result = new Array<number>(m).fill(-1);
9	1×	if (n === 0 \|\| m === 0) {
10	2×	return result;
11	2×	}
12	3×	// Trim common prefix and suffix first; they dominate real edits.
13	3×	let start = 0;
14	1×	while (start < n && start < m && before[start] === after[start]) {
15	3×	result[start] = start;
16	3×	start++;
17	3×	}
18	3×	let endB = n;
19	3×	let endA = m;
20	1×	while (endB > start && endA > start && before[endB - 1] === after[endA - 1]) {
21	0×	endB--;
22	0×	endA--;
23	0×	result[endA] = endB;
24	0×	}
25	3×	const a = before.slice(start, endB);
26	3×	const b = after.slice(start, endA);
27	1×	if (a.length === 0 \|\| b.length === 0) {
28	1×	return result;
29	1×	}
30	2×	// Bail out to positional matching on huge middles to bound memory.
31	1×	if (a.length * b.length > 25_000_000) {
32	0×	for (let i = 0; i < Math.min(a.length, b.length); i++) {
33	0×	if (a[i] === b[i]) {
34	0×	result[start + i] = start + i;
35	0×	}
36	0×	}
37	0×	return result;
38	0×	}
39	1×	for (const [i, j] of myers(a, b)) {
40	1×	result[start + j] = start + i;
41	1×	}
42	1×	return result;
43	2×	}
44	2×
45	2×	/** Pairs (i, j) of equal lines a[i] === b[j] along a shortest edit script. */
46	2×	function myers(a: string[], b: string[]): [number, number][] {
47	2×	const n = a.length;
48	2×	const m = b.length;
49	2×	const max = n + m;
50	2×	const offset = max;
51	2×	const trace: Int32Array[] = [];
52	2×	let v = new Int32Array(2 * max + 2);
53	2×	v[offset + 1] = 0;
54	2×	outer: for (let d = 0; d <= max; d++) {
55	9×	const snapshot = v.slice();
56	9×	trace.push(snapshot);
57	9×	for (let k = -d; k <= d; k += 2) {
58	21×	let x: number;
59	21×	if (k === -d \|\| (k !== d && v[offset + k - 1] < v[offset + k + 1])) {
60	14×	x = v[offset + k + 1];
61	21×	} else {
62	7×	x = v[offset + k - 1] + 1;
63	7×	}
64	21×	let y = x - k;
65	21×	while (x < n && y < m && a[x] === b[y]) {
66	7×	x++;
67	7×	y++;
68	7×	}
69	21×	v[offset + k] = x;
70	21×	if (x >= n && y >= m) {
71	2×	break outer;
72	2×	}
73	21×	}
74	7×	}
75	2×	// Backtrack.
76	2×	const pairs: [number, number][] = [];
77	2×	let x = n;
78	2×	let y = m;
79	2×	for (let d = trace.length - 1; d >= 0; d--) {
80	9×	const vd = trace[d];
81	9×	const k = x - y;
82	9×	let prevK: number;
83	9×	if (k === -d \|\| (k !== d && vd[offset + k - 1] < vd[offset + k + 1])) {
84	6×	prevK = k + 1;
85	9×	} else {
86	3×	prevK = k - 1;
87	3×	}
88	9×	const prevX = vd[offset + prevK];
89	9×	const prevY = prevX - prevK;
90	9×	while (x > prevX && y > prevY) {
91	5×	x--;
92	5×	y--;
93	5×	pairs.push([x, y]);
94	5×	}
95	9×	if (d > 0) {
96	7×	x = prevX;
97	7×	y = prevY;
98	7×	}
99	9×	}
100	2×	return pairs.reverse();
101	2×	}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

Coverage / src/diffutil.ts 86.1%

Keyboard