1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149 | export interface DiffOp {
tag: "eq" | "del" | "add";
line: string;
}
export interface Hunk {
aStart: number;
aLen: number;
bStart: number;
bLen: number;
ops: DiffOp[];
}
const MAX_LINES = 40000;
const MAX_PRODUCT = 4_000_000;
const MAX_D = 2000;
const TRACE_BUDGET = 8_000_000;
/** Myers O(ND) line diff. Returns null when the input is too large. */
export function diffLines(aText: string, bText: string): DiffOp[] | null {
const a = aText.split("\n");
const b = bText.split("\n");
if (a[a.length - 1] === "") a.pop();
if (b[b.length - 1] === "") b.pop();
const N = a.length, M = b.length;
if (N === 0 || M === 0) {
const ops: DiffOp[] = [];
for (const line of a) ops.push({ tag: "del", line });
for (const line of b) ops.push({ tag: "add", line });
return ops;
}
if (N + M > MAX_LINES) return null;
if (N * M > MAX_PRODUCT) return null;
const max = N + M;
const dCap = Math.min(MAX_D, Math.max(1, Math.floor(TRACE_BUDGET / max)));
const offset = max;
const v = new Int32Array(2 * max + 2);
const trace: Int32Array[] = [];
let dFound = -1;
outer: for (let d = 0; d <= max; d++) {
if (d > dCap) return null;
trace.push(v.slice());
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) {
dFound = d;
break outer;
}
}
}
const ops: DiffOp[] = [];
let x = N, y = M;
for (let d = dFound; d > 0; d--) {
const vPrev = trace[d];
const k = x - y;
const prevK =
k === -d || (k !== d && vPrev[offset + k - 1] < vPrev[offset + k + 1]) ? k + 1 : k - 1;
const prevX = vPrev[offset + prevK];
const prevY = prevX - prevK;
while (x > prevX && y > prevY) {
ops.push({ tag: "eq", line: a[--x] });
y--;
}
if (x === prevX) {
ops.push({ tag: "add", line: b[--y] });
} else {
ops.push({ tag: "del", line: a[--x] });
}
}
while (x > 0) {
ops.push({ tag: "eq", line: a[--x] });
y--;
}
ops.reverse();
return ops;
}
/** Group diff ops into unified hunks with `context` lines of context. */
export function toHunks(ops: DiffOp[], context = 3): Hunk[] {
// indexes of non-eq ops
const changes: number[] = [];
ops.forEach((op, i) => {
if (op.tag !== "eq") changes.push(i);
});
if (!changes.length) return [];
// merge change ranges whose context windows touch
const ranges: [number, number][] = [];
let start = changes[0], end = changes[0];
for (const i of changes.slice(1)) {
if (i - end <= context * 2) {
end = i;
} else {
ranges.push([start, end]);
start = end = i;
}
}
ranges.push([start, end]);
const hunks: Hunk[] = [];
let aLine = 1, bLine = 1, opIdx = 0;
for (const [s, e] of ranges) {
const from = Math.max(0, s - context);
const to = Math.min(ops.length - 1, e + context);
// advance line counters up to `from`
while (opIdx < from) {
const op = ops[opIdx++];
if (op.tag !== "add") aLine++;
if (op.tag !== "del") bLine++;
}
const hunk: Hunk = { aStart: aLine, aLen: 0, bStart: bLine, bLen: 0, ops: [] };
while (opIdx <= to) {
const op = ops[opIdx++];
hunk.ops.push(op);
if (op.tag !== "add") {
hunk.aLen++;
aLine++;
}
if (op.tag !== "del") {
hunk.bLen++;
bLine++;
}
}
if (hunk.aLen === 0) hunk.aStart = aLine - 1;
if (hunk.bLen === 0) hunk.bStart = bLine - 1;
hunks.push(hunk);
}
return hunks;
}
export function isBinary(data: Uint8Array): boolean {
const n = Math.min(data.length, 8000);
for (let i = 0; i < n; i++) if (data[i] === 0) return true;
return false;
}
|