src/vs/editor/common/diff/defaultLinesDiffComputer/defaultLinesDiffComputer.ts
271 LOC · 252 covered · 19 uncovered · 53 ranges · 286 concepts · 19 introducers · 133 tests
File neighbourhood
The centred file is linked to every concept that introduces one of its ranges, every test that runs code from the file, and the gray connector concepts standing between those tests and the file's own introducer concepts. Undirected links join concepts to every file where they introduce source and concepts to the tests they introduce; arrows show specialization between the displayed concepts and bridge only concepts omitted from this view. Concept colors match the source ranges below; connector concepts have no source color and are shown in gray.
Focused file, its introducer and connector concepts, their introduced files, and tests that run code from the file
In the embedded map, ordinary wheel input scrolls the page; use the visible controls to zoom and drag to pan. Open the full-screen map for canvas navigation: wheel pans, Ctrl/Command plus wheel zooms, and arrow keys pan when this region is focused. On touch screens, open the full-screen map to pan or pinch. If JavaScript or WebGL is unavailable, use the related-file, concept, and source links on this page.
Graph controls are ready.
Interactive rendering requires JavaScript and WebGL. Use the related-file, concept, and source links on this page while the interactive map is unavailable.
1
>
/*---------------------------------------------------------------------------------------------
heuristicSequenceOptimizations.ts ×9
2
>
* Copyright (c) Microsoft Corporation. All rights reserved.
3
>
* Licensed under the MIT License. See License.txt in the project root for license information.
4
>
*--------------------------------------------------------------------------------------------*/
5
>
6
>
import { equals } from '../../../../base/common/arrays.js';
7
>
import { assertFn } from '../../../../base/common/assert.js';
8
>
import { LineRange } from '../../core/ranges/lineRange.js';
9
>
import { OffsetRange } from '../../core/ranges/offsetRange.js';
10
>
import { Position } from '../../core/position.js';
11
>
import { Range } from '../../core/range.js';
12
>
import { ArrayText } from '../../core/text/abstractText.js';
13
>
import { ILinesDiffComputer, ILinesDiffComputerOptions, LinesDiff, MovedText } from '../linesDiffComputer.js';
14
>
import { DetailedLineRangeMapping, LineRangeMapping, lineRangeMappingFromRangeMappings, RangeMapping } from '../rangeMapping.js';
15
>
import { DateTimeout, InfiniteTimeout, ITimeout, SequenceDiff } from './algorithms/diffAlgorithm.js';
16
>
import { DynamicProgrammingDiffing } from './algorithms/dynamicProgrammingDiffing.js';
17
>
import { MyersDiffAlgorithm } from './algorithms/myersDiffAlgorithm.js';
18
>
import { computeMovedLines } from './computeMovedLines.js';
19
>
import { extendDiffsToEntireWordIfAppropriate, optimizeSequenceDiffs, removeShortMatches, removeVeryShortMatchingLinesBetweenDiffs, removeVeryShortMatchingTextBetweenLongDiffs } from './heuristicSequenceOptimizations.js';
20
>
import { LineSequence } from './lineSequence.js';
21
>
import { LinesSliceCharSequence } from './linesSliceCharSequence.js';
22
>
23
>
export class DefaultLinesDiffComputer implements ILinesDiffComputer {
24
>
private readonly dynamicProgrammingDiffing = new DynamicProgrammingDiffing();
defaultLinesDiffComputer.ts ×8
25
>
private readonly myersDiffingAlgorithm = new MyersDiffAlgorithm();
27
>
computeDiff(originalLines: string[], modifiedLines: string[], options: ILinesDiffComputerOptions): LinesDiff {
28
>
if (originalLines.length <= 1 && equals(originalLines, modifiedLines, (a, b) => a === b)) {
defaultLinesDiffComputer.ts ×8
29
return new LinesDiff([], [], false);
30
}
32
>
if (originalLines.length === 1 && originalLines[0].length === 0 || modifiedLines.length === 1 && modifiedLines[0].length === 0) {
34
>
new DetailedLineRangeMapping(
35
>
new LineRange(1, originalLines.length + 1),
36
>
new LineRange(1, modifiedLines.length + 1),
37
>
[
38
>
new RangeMapping(
39
>
new Range(1, 1, originalLines.length, originalLines[originalLines.length - 1].length + 1),
40
>
new Range(1, 1, modifiedLines.length, modifiedLines[modifiedLines.length - 1].length + 1),
41
>
)
42
>
]
43
>
)
44
>
], [], false);
45
>
}
47
>
const timeout = options.maxComputationTimeMs === 0 ? InfiniteTimeout.instance : new DateTimeout(options.maxComputationTimeMs);
defaultLinesDiffComputer.ts ×8
48
>
const considerWhitespaceChanges = !options.ignoreTrimWhitespace;
49
>
50
>
const perfectHashes = new Map<string, number>();
51
>
function getOrCreateHash(text: string): number {
53
>
if (hash === undefined) {
54
>
hash = perfectHashes.size;
55
>
perfectHashes.set(text, hash);
56
>
}
57
>
return hash;
58
>
}
60
>
const originalLinesHashes = originalLines.map((l) => getOrCreateHash(l.trim()));
61
>
const modifiedLinesHashes = modifiedLines.map((l) => getOrCreateHash(l.trim()));
62
>
63
>
const sequence1 = new LineSequence(originalLinesHashes, originalLines);
64
>
const sequence2 = new LineSequence(modifiedLinesHashes, modifiedLines);
65
>
66
>
const lineAlignmentResult = (() => {
68
>
// Use the improved algorithm for small files
69
>
return this.dynamicProgrammingDiffing.compute(
70
>
sequence1,
71
>
sequence2,
72
>
timeout,
73
>
(offset1, offset2) =>
80
>
}
81
82
return this.myersDiffingAlgorithm.compute(
83
sequence1,
84
sequence2,
85
timeout
86
);
88
>
89
>
let lineAlignments = lineAlignmentResult.diffs;
90
>
let hitTimeout = lineAlignmentResult.hitTimeout;
91
>
lineAlignments = optimizeSequenceDiffs(sequence1, sequence2, lineAlignments);
92
>
lineAlignments = removeVeryShortMatchingLinesBetweenDiffs(sequence1, sequence2, lineAlignments);
93
>
94
>
const alignments: RangeMapping[] = [];
95
>
96
>
const scanForWhitespaceChanges = (equalLinesCount: number) => {
99
>
}
101
>
for (let i = 0; i < equalLinesCount; i++) {
103
>
const seq2Offset = seq2LastStart + i;
104
>
if (originalLines[seq1Offset] !== modifiedLines[seq2Offset]) {
106
>
const characterDiffs = this.refineDiff(originalLines, modifiedLines, new SequenceDiff(
107
>
new OffsetRange(seq1Offset, seq1Offset + 1),
108
>
new OffsetRange(seq2Offset, seq2Offset + 1),
109
>
), timeout, considerWhitespaceChanges, options);
110
>
for (const a of characterDiffs.mappings) {
111
>
alignments.push(a);
112
>
}
113
>
if (characterDiffs.hitTimeout) {
114
hitTimeout = true;
115
}
120
>
let seq1LastStart = 0;
121
>
let seq2LastStart = 0;
122
>
123
>
for (const diff of lineAlignments) {
124
>
assertFn(() => diff.seq1Range.start - seq1LastStart === diff.seq2Range.start - seq2LastStart);
heuristicSequenceOptimizations.ts ×3
125
>
126
>
const equalLinesCount = diff.seq1Range.start - seq1LastStart;
127
>
128
>
scanForWhitespaceChanges(equalLinesCount);
129
>
130
>
seq1LastStart = diff.seq1Range.endExclusive;
131
>
seq2LastStart = diff.seq2Range.endExclusive;
132
>
133
>
const characterDiffs = this.refineDiff(originalLines, modifiedLines, diff, timeout, considerWhitespaceChanges, options);
134
>
if (characterDiffs.hitTimeout) {
135
hitTimeout = true;
136
}
138
>
alignments.push(a);
139
>
}
140
>
}
142
>
scanForWhitespaceChanges(originalLines.length - seq1LastStart);
143
>
144
>
const original = new ArrayText(originalLines);
145
>
const modified = new ArrayText(modifiedLines);
146
>
147
>
const changes = lineRangeMappingFromRangeMappings(alignments, original, modified);
148
>
149
>
let moves: MovedText[] = [];
150
>
if (options.computeMoves) {
151
>
moves = this.computeMoves(changes, originalLines, modifiedLines, originalLinesHashes, modifiedLinesHashes, timeout, considerWhitespaceChanges, options);
computeMovedLines.ts ×11
152
>
}
154
>
// Make sure all ranges are valid
155
>
assertFn(() => {
156
>
function validatePosition(pos: Position, lines: string[]): boolean {
157
>
if (pos.lineNumber < 1 || pos.lineNumber > lines.length) { return false; }
heuristicSequenceOptimizations.ts ×26
158
>
const line = lines[pos.lineNumber - 1];
159
>
if (pos.column < 1 || pos.column > line.length + 1) { return false; }
160
>
return true;
161
>
}
163
>
function validateRange(range: LineRange, lines: string[]): boolean {
164
>
if (range.startLineNumber < 1 || range.startLineNumber > lines.length + 1) { return false; }
heuristicSequenceOptimizations.ts ×26
165
>
if (range.endLineNumberExclusive < 1 || range.endLineNumberExclusive > lines.length + 1) { return false; }
166
>
return true;
167
>
}
169
>
for (const c of changes) {
171
>
for (const ic of c.innerChanges) {
172
>
const valid = validatePosition(ic.modifiedRange.getStartPosition(), modifiedLines) && validatePosition(ic.modifiedRange.getEndPosition(), modifiedLines) &&
173
>
validatePosition(ic.originalRange.getStartPosition(), originalLines) && validatePosition(ic.originalRange.getEndPosition(), originalLines);
174
>
if (!valid) {
175
return false;
176
}
178
>
if (!validateRange(c.modified, modifiedLines) || !validateRange(c.original, originalLines)) {
179
return false;
180
}
183
>
});
184
>
185
>
return new LinesDiff(changes, moves, hitTimeout);
188
>
private computeMoves(
190
>
originalLines: string[],
191
>
modifiedLines: string[],
192
>
hashedOriginalLines: number[],
193
>
hashedModifiedLines: number[],
194
>
timeout: ITimeout,
195
>
considerWhitespaceChanges: boolean,
196
>
options: ILinesDiffComputerOptions,
197
>
): MovedText[] {
198
>
const moves = computeMovedLines(
199
>
changes,
200
>
originalLines,
201
>
modifiedLines,
202
>
hashedOriginalLines,
203
>
hashedModifiedLines,
204
>
timeout,
205
>
);
206
>
const movesWithDiffs = moves.map(m => {
207
>
const moveChanges = this.refineDiff(originalLines, modifiedLines, new SequenceDiff(
defaultLinesDiffComputer.ts ×1
208
>
m.original.toOffsetRange(),
209
>
m.modified.toOffsetRange(),
210
>
), timeout, considerWhitespaceChanges, options);
211
>
const mappings = lineRangeMappingFromRangeMappings(moveChanges.mappings, new ArrayText(originalLines), new ArrayText(modifiedLines), true);
212
>
return new MovedText(m, mappings);
214
>
return movesWithDiffs;
215
>
}
217
>
private refineDiff(originalLines: string[], modifiedLines: string[], diff: SequenceDiff, timeout: ITimeout, considerWhitespaceChanges: boolean, options: ILinesDiffComputerOptions): { mappings: RangeMapping[]; hitTimeout: boolean } {
219
>
const rangeMapping = lineRangeMapping.toRangeMapping2(originalLines, modifiedLines);
220
>
221
>
const slice1 = new LinesSliceCharSequence(originalLines, rangeMapping.originalRange, considerWhitespaceChanges);
222
>
const slice2 = new LinesSliceCharSequence(modifiedLines, rangeMapping.modifiedRange, considerWhitespaceChanges);
223
>
224
>
const diffResult = slice1.length + slice2.length < 500
225
>
? this.dynamicProgrammingDiffing.compute(slice1, slice2, timeout)
defaultLinesDiffComputer.ts ×1
228
>
const check = false;
229
>
230
>
let diffs = diffResult.diffs;
231
>
if (check) { SequenceDiff.assertSorted(diffs); }
232
>
diffs = optimizeSequenceDiffs(slice1, slice2, diffs);
233
>
if (check) { SequenceDiff.assertSorted(diffs); }
234
>
diffs = extendDiffsToEntireWordIfAppropriate(slice1, slice2, diffs, (seq, idx) => seq.findWordContaining(idx));
235
>
if (check) { SequenceDiff.assertSorted(diffs); }
236
>
237
>
if (options.extendToSubwords) {
238
diffs = extendDiffsToEntireWordIfAppropriate(slice1, slice2, diffs, (seq, idx) => seq.findSubWordContaining(idx), true);
239
if (check) { SequenceDiff.assertSorted(diffs); }
240
}
242
>
diffs = removeShortMatches(slice1, slice2, diffs);
243
>
if (check) { SequenceDiff.assertSorted(diffs); }
244
>
diffs = removeVeryShortMatchingTextBetweenLongDiffs(slice1, slice2, diffs);
245
>
if (check) { SequenceDiff.assertSorted(diffs); }
246
>
247
>
const result = diffs.map(
248
>
(d) =>
249
>
new RangeMapping(
250
>
slice1.translateRange(d.seq1Range),
251
>
slice2.translateRange(d.seq2Range)
252
>
)
253
>
);
254
>
255
>
if (check) { RangeMapping.assertSorted(result); }
256
>
257
>
// Assert: result applied on original should be the same as diff applied to original
258
>
259
>
return {
260
>
mappings: result,
261
>
hitTimeout: diffResult.hitTimeout,
262
>
};
263
>
}
265
>
266
>
function toLineRangeMapping(sequenceDiff: SequenceDiff) {
heuristicSequenceOptimizations.ts ×26
267
>
return new LineRangeMapping(
268
>
new LineRange(sequenceDiff.seq1Range.start + 1, sequenceDiff.seq1Range.endExclusive + 1),
269
>
new LineRange(sequenceDiff.seq2Range.start + 1, sequenceDiff.seq2Range.endExclusive + 1),
270
>
);
271
>
}