char/sorcery

static-files based git repo viewer

git clone https://git.t4t.associates/char/sorcery

Charlotte Sominitial commitd540258

main
branchesmainall refs →
3.8 KiB135 linesraw
1export interface DiffLine {
2  sign: " " | "+" | "-";
3  text: string;
4}
5
6export interface Hunk {
7  aStart: number;
8  aLines: number;
9  bStart: number;
10  bLines: number;
11  lines: DiffLine[];
12}
13
14/** myers O(ND) shortest edit script over lines, grouped into context hunks */
15export function diffLines(aText: string, bText: string, context = 3): Hunk[] {
16  const a = splitLines(aText);
17  const b = splitLines(bText);
18  const trace = myers(a, b);
19  return groupHunks(a, b, trace, context);
20}
21
22function splitLines(text: string): string[] {
23  if (text === "") return [];
24  const lines = text.split("\n");
25  if (lines.at(-1) === "") lines.pop();
26  return lines;
27}
28
29type Edit = { sign: " " | "+" | "-"; aLine: number; bLine: number };
30
31function myers(a: string[], b: string[]): Edit[] {
32  const max = a.length + b.length;
33  if (max === 0) return [];
34  const offset = max;
35  let v = new Array<number>(2 * max + 1).fill(0);
36  const traces: number[][] = [];
37
38  outer: for (let d = 0; d <= max; d++) {
39    traces.push(v.slice());
40    for (let k = -d; k <= d; k += 2) {
41      let x = k === -d || (k !== d && v[offset + k - 1] < v[offset + k + 1])
42        ? v[offset + k + 1]
43        : v[offset + k - 1] + 1;
44      let y = x - k;
45      while (x < a.length && y < b.length && a[x] === b[y]) {
46        x++;
47        y++;
48      }
49      v[offset + k] = x;
50      if (x >= a.length && y >= b.length) break outer;
51    }
52    v = v.slice();
53  }
54
55  // backtrack the recorded frontiers into an edit script
56  const edits: Edit[] = [];
57  let x = a.length;
58  let y = b.length;
59  for (let d = traces.length - 1; x > 0 || y > 0; d--) {
60    const vd = traces[d];
61    const k = x - y;
62    const prevK = k === -d || (k !== d && vd[offset + k - 1] < vd[offset + k + 1]) ? k + 1 : k - 1;
63    const prevX = vd[offset + prevK];
64    const prevY = prevX - prevK;
65    while (x > prevX && y > prevY) {
66      edits.push({ sign: " ", aLine: --x, bLine: --y });
67    }
68    if (d === 0) break;
69    if (x === prevX) edits.push({ sign: "+", aLine: x, bLine: --y });
70    else edits.push({ sign: "-", aLine: --x, bLine: y });
71  }
72  return edits.reverse();
73}
74
75function groupHunks(a: string[], b: string[], edits: Edit[], context: number): Hunk[] {
76  const hunks: Hunk[] = [];
77  let current: Hunk | null = null;
78  let trailingContext = 0;
79
80  for (let i = 0; i < edits.length; i++) {
81    const edit = edits[i];
82    if (edit.sign === " ") {
83      if (current) {
84        if (trailingContext < context) {
85          current.lines.push({ sign: " ", text: a[edit.aLine] });
86          current.aLines++;
87          current.bLines++;
88          trailingContext++;
89        } else {
90          // check whether another change follows within 2*context
91          const nextChange = edits.slice(i, i + context + 1).findIndex(e => e.sign !== " ");
92          if (nextChange === -1) {
93            current = null;
94          } else {
95            current.lines.push({ sign: " ", text: a[edit.aLine] });
96            current.aLines++;
97            current.bLines++;
98          }
99        }
100      }
101      continue;
102    }
103
104    if (!current) {
105      const lead: DiffLine[] = [];
106      let aStart = edit.aLine;
107      let bStart = edit.bLine;
108      for (let c = 1; c <= context; c++) {
109        const prev = edits[i - c];
110        if (!prev || prev.sign !== " ") break;
111        lead.unshift({ sign: " ", text: a[prev.aLine] });
112        aStart = prev.aLine;
113        bStart = prev.bLine;
114      }
115      current = {
116        aStart: aStart + 1,
117        bStart: bStart + 1,
118        aLines: lead.length,
119        bLines: lead.length,
120        lines: lead,
121      };
122      hunks.push(current);
123    }
124    trailingContext = 0;
125    if (edit.sign === "-") {
126      current.lines.push({ sign: "-", text: a[edit.aLine] });
127      current.aLines++;
128    } else {
129      current.lines.push({ sign: "+", text: b[edit.bLine] });
130      current.bLines++;
131    }
132  }
133
134  return hunks;
135}