src/vs/editor/common/diff/defaultLinesDiffComputer/computeMovedLines.ts
329 LOC · 318 covered · 11 uncovered · 70 ranges · 286 concepts · 20 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 { ITimeout, SequenceDiff } from './algorithms/diffAlgorithm.js';
7
>
import { DetailedLineRangeMapping, LineRangeMapping } from '../rangeMapping.js';
8
>
import { pushMany, compareBy, numberComparator, reverseOrder } from '../../../../base/common/arrays.js';
9
>
import { MonotonousArray, findLastMonotonous } from '../../../../base/common/arraysFind.js';
10
>
import { SetMap } from '../../../../base/common/map.js';
11
>
import { LineRange, LineRangeSet } from '../../core/ranges/lineRange.js';
12
>
import { LinesSliceCharSequence } from './linesSliceCharSequence.js';
13
>
import { LineRangeFragment, isSpace } from './utils.js';
14
>
import { MyersDiffAlgorithm } from './algorithms/myersDiffAlgorithm.js';
15
>
import { Range } from '../../core/range.js';
16
>
17
>
export function computeMovedLines(
19
>
originalLines: string[],
20
>
modifiedLines: string[],
21
>
hashedOriginalLines: number[],
22
>
hashedModifiedLines: number[],
23
>
timeout: ITimeout
24
>
): LineRangeMapping[] {
25
>
let { moves, excludedChanges } = computeMovesFromSimpleDeletionsToSimpleInsertions(changes, originalLines, modifiedLines, timeout);
26
>
27
>
if (!timeout.isValid()) { return []; }
28
>
29
>
const filteredChanges = changes.filter(c => !excludedChanges.has(c));
30
>
const unchangedMoves = computeUnchangedMoves(filteredChanges, hashedOriginalLines, hashedModifiedLines, originalLines, modifiedLines, timeout);
31
>
pushMany(moves, unchangedMoves);
32
>
33
>
moves = joinCloseConsecutiveMoves(moves);
34
>
// Ignore too short moves
35
>
moves = moves.filter(current => {
36
>
const lines = current.original.toOffsetRange().slice(originalLines).map(l => l.trim());
computeMovedLines.ts ×6
37
>
const originalText = lines.join('\n');
38
>
return originalText.length >= 15 && countWhere(lines, l => l.length >= 2) >= 2;
40
>
moves = removeMovesInSameDiff(changes, moves);
41
>
42
>
return moves;
43
>
}
45
>
function countWhere<T>(arr: T[], predicate: (t: T) => boolean): number {
computeMovedLines.ts ×6
46
>
let count = 0;
47
>
for (const t of arr) {
48
>
if (predicate(t)) {
49
>
count++;
50
>
}
51
>
}
52
>
return count;
53
>
}
56
>
changes: DetailedLineRangeMapping[],
57
>
originalLines: string[],
58
>
modifiedLines: string[],
59
>
timeout: ITimeout,
60
>
) {
61
>
const moves: LineRangeMapping[] = [];
62
>
63
>
const deletions = changes
64
>
.filter(c => c.modified.isEmpty && c.original.length >= 3)
65
>
.map(d => new LineRangeFragment(d.original, originalLines, d));
66
>
const insertions = new Set(changes
67
>
.filter(c => c.original.isEmpty && c.modified.length >= 3)
68
>
.map(d => new LineRangeFragment(d.modified, modifiedLines, d)));
69
>
70
>
const excludedChanges = new Set<DetailedLineRangeMapping>();
71
>
72
>
for (const deletion of deletions) {
74
>
let best: LineRangeFragment | undefined;
75
>
for (const insertion of insertions) {
77
>
if (similarity > highestSimilarity) {
78
>
highestSimilarity = similarity;
79
>
best = insertion;
80
>
}
81
>
}
83
>
if (highestSimilarity > 0.90 && best) {
85
>
moves.push(new LineRangeMapping(deletion.range, best.range));
86
>
excludedChanges.add(deletion.source);
87
>
excludedChanges.add(best.source);
88
>
}
90
>
if (!timeout.isValid()) {
91
return { moves, excludedChanges };
92
}
95
>
return { moves, excludedChanges };
96
>
}
99
>
changes: DetailedLineRangeMapping[],
100
>
hashedOriginalLines: number[],
101
>
hashedModifiedLines: number[],
102
>
originalLines: string[],
103
>
modifiedLines: string[],
104
>
timeout: ITimeout,
105
>
) {
106
>
const moves: LineRangeMapping[] = [];
107
>
108
>
const original3LineHashes = new SetMap<string, { range: LineRange }>();
109
>
110
>
for (const change of changes) {
111
>
for (let i = change.original.startLineNumber; i < change.original.endLineNumberExclusive - 2; i++) {
computeMovedLines.ts ×4
112
>
const key = `${hashedOriginalLines[i - 1]}:${hashedOriginalLines[i + 1 - 1]}:${hashedOriginalLines[i + 2 - 1]}`;
computeMovedLines.ts ×1
113
>
original3LineHashes.add(key, { range: new LineRange(i, i + 3) });
114
>
}
117
>
interface PossibleMapping {
118
>
modifiedLineRange: LineRange;
119
>
originalLineRange: LineRange;
120
>
}
121
>
122
>
const possibleMappings: PossibleMapping[] = [];
123
>
124
>
changes.sort(compareBy(c => c.modified.startLineNumber, numberComparator));
125
>
126
>
for (const change of changes) {
128
>
for (let i = change.modified.startLineNumber; i < change.modified.endLineNumberExclusive - 2; i++) {
129
>
const key = `${hashedModifiedLines[i - 1]}:${hashedModifiedLines[i + 1 - 1]}:${hashedModifiedLines[i + 2 - 1]}`;
computeMovedLines.ts ×2
130
>
const currentModifiedRange = new LineRange(i, i + 3);
131
>
132
>
const nextMappings: PossibleMapping[] = [];
133
>
original3LineHashes.forEach(key, ({ range }) => {
136
>
if (lastMapping.originalLineRange.endLineNumberExclusive + 1 === range.endLineNumberExclusive &&
137
>
lastMapping.modifiedLineRange.endLineNumberExclusive + 1 === currentModifiedRange.endLineNumberExclusive) {
138
>
lastMapping.originalLineRange = new LineRange(lastMapping.originalLineRange.startLineNumber, range.endLineNumberExclusive);
139
>
lastMapping.modifiedLineRange = new LineRange(lastMapping.modifiedLineRange.startLineNumber, currentModifiedRange.endLineNumberExclusive);
140
>
nextMappings.push(lastMapping);
141
>
return;
142
>
}
143
>
}
145
>
const mapping: PossibleMapping = {
146
>
modifiedLineRange: currentModifiedRange,
147
>
originalLineRange: range,
148
>
};
149
>
possibleMappings.push(mapping);
150
>
nextMappings.push(mapping);
152
>
lastMappings = nextMappings;
153
>
}
154
>
155
>
if (!timeout.isValid()) {
156
return [];
157
}
160
>
possibleMappings.sort(reverseOrder(compareBy(m => m.modifiedLineRange.length, numberComparator)));
161
>
162
>
const modifiedSet = new LineRangeSet();
163
>
const originalSet = new LineRangeSet();
164
>
165
>
for (const mapping of possibleMappings) {
167
>
const diffOrigToMod = mapping.modifiedLineRange.startLineNumber - mapping.originalLineRange.startLineNumber;
168
>
const modifiedSections = modifiedSet.subtractFrom(mapping.modifiedLineRange);
169
>
const originalTranslatedSections = originalSet.subtractFrom(mapping.originalLineRange).getWithDelta(diffOrigToMod);
170
>
171
>
const modifiedIntersectedSections = modifiedSections.getIntersection(originalTranslatedSections);
172
>
173
>
for (const s of modifiedIntersectedSections.ranges) {
174
>
if (s.length < 3) {
175
continue;
176
}
178
>
const originalLineRange = s.delta(-diffOrigToMod);
179
>
180
>
moves.push(new LineRangeMapping(originalLineRange, modifiedLineRange));
181
>
182
>
modifiedSet.addRange(modifiedLineRange);
183
>
originalSet.addRange(originalLineRange);
184
>
}
185
>
}
187
>
moves.sort(compareBy(m => m.original.startLineNumber, numberComparator));
188
>
189
>
const monotonousChanges = new MonotonousArray(changes);
190
>
for (let i = 0; i < moves.length; i++) {
192
>
const firstTouchingChangeOrig = monotonousChanges.findLastMonotonous(c => c.original.startLineNumber <= move.original.startLineNumber)!;
193
>
const firstTouchingChangeMod = findLastMonotonous(changes, c => c.modified.startLineNumber <= move.modified.startLineNumber)!;
194
>
const linesAbove = Math.max(
195
>
move.original.startLineNumber - firstTouchingChangeOrig.original.startLineNumber,
196
>
move.modified.startLineNumber - firstTouchingChangeMod.modified.startLineNumber
197
>
);
198
>
199
>
const lastTouchingChangeOrig = monotonousChanges.findLastMonotonous(c => c.original.startLineNumber < move.original.endLineNumberExclusive)!;
200
>
const lastTouchingChangeMod = findLastMonotonous(changes, c => c.modified.startLineNumber < move.modified.endLineNumberExclusive)!;
201
>
const linesBelow = Math.max(
202
>
lastTouchingChangeOrig.original.endLineNumberExclusive - move.original.endLineNumberExclusive,
203
>
lastTouchingChangeMod.modified.endLineNumberExclusive - move.modified.endLineNumberExclusive
204
>
);
205
>
206
>
let extendToTop: number;
207
>
for (extendToTop = 0; extendToTop < linesAbove; extendToTop++) {
209
>
const modLine = move.modified.startLineNumber - extendToTop - 1;
210
>
if (origLine > originalLines.length || modLine > modifiedLines.length) {
211
break;
212
}
213
>
if (modifiedSet.contains(modLine) || originalSet.contains(origLine)) {
computeMovedLines.ts ×6
215
>
}
216
>
if (!areLinesSimilar(originalLines[origLine - 1], modifiedLines[modLine - 1], timeout)) {
computeMovedLines.ts ×6
217
>
break;
218
>
}
219
>
}
221
>
if (extendToTop > 0) {
222
>
originalSet.addRange(new LineRange(move.original.startLineNumber - extendToTop, move.original.startLineNumber));
computeMovedLines.ts ×1
223
>
modifiedSet.addRange(new LineRange(move.modified.startLineNumber - extendToTop, move.modified.startLineNumber));
224
>
}
226
>
let extendToBottom: number;
227
>
for (extendToBottom = 0; extendToBottom < linesBelow; extendToBottom++) {
228
>
const origLine = move.original.endLineNumberExclusive + extendToBottom;
229
>
const modLine = move.modified.endLineNumberExclusive + extendToBottom;
230
>
if (origLine > originalLines.length || modLine > modifiedLines.length) {
231
break;
232
}
233
>
if (modifiedSet.contains(modLine) || originalSet.contains(origLine)) {
computeMovedLines.ts ×14
235
>
}
236
>
if (!areLinesSimilar(originalLines[origLine - 1], modifiedLines[modLine - 1], timeout)) {
computeMovedLines.ts ×14
238
>
}
240
>
241
>
if (extendToBottom > 0) {
242
>
originalSet.addRange(new LineRange(move.original.endLineNumberExclusive, move.original.endLineNumberExclusive + extendToBottom));
computeMovedLines.ts ×2
243
>
modifiedSet.addRange(new LineRange(move.modified.endLineNumberExclusive, move.modified.endLineNumberExclusive + extendToBottom));
244
>
}
246
>
if (extendToTop > 0 || extendToBottom > 0) {
248
>
new LineRange(move.original.startLineNumber - extendToTop, move.original.endLineNumberExclusive + extendToBottom),
249
>
new LineRange(move.modified.startLineNumber - extendToTop, move.modified.endLineNumberExclusive + extendToBottom),
250
>
);
251
>
}
253
>
254
>
return moves;
255
>
}
257
>
function areLinesSimilar(line1: string, line2: string, timeout: ITimeout): boolean {
computeMovedLines.ts ×14
258
>
if (line1.trim() === line2.trim()) { return true; }
259
>
if (line1.length > 300 && line2.length > 300) { return false; }
261
>
const myersDiffingAlgorithm = new MyersDiffAlgorithm();
262
>
const result = myersDiffingAlgorithm.compute(
263
>
new LinesSliceCharSequence([line1], new Range(1, 1, 1, line1.length), false),
264
>
new LinesSliceCharSequence([line2], new Range(1, 1, 1, line2.length), false),
265
>
timeout
266
>
);
267
>
let commonNonSpaceCharCount = 0;
268
>
const inverted = SequenceDiff.invert(result.diffs, line1.length);
269
>
for (const seq of inverted) {
270
>
seq.seq1Range.forEach(idx => {
272
>
commonNonSpaceCharCount++;
273
>
}
275
>
}
276
>
277
>
function countNonWsChars(str: string): number {
278
>
let count = 0;
279
>
for (let i = 0; i < line1.length; i++) {
281
>
count++;
282
>
}
283
>
}
285
>
}
286
>
287
>
const longerLineLength = countNonWsChars(line1.length > line2.length ? line1 : line2);
computeMovedLines.ts ×14
288
>
const r = commonNonSpaceCharCount / longerLineLength > 0.6 && longerLineLength > 10;
289
>
return r;
290
>
}
292
>
function joinCloseConsecutiveMoves(moves: LineRangeMapping[]): LineRangeMapping[] {
computeMovedLines.ts ×11
293
>
if (moves.length === 0) {
295
>
}
297
>
moves.sort(compareBy(m => m.original.startLineNumber, numberComparator));
298
>
299
>
const result = [moves[0]];
300
>
for (let i = 1; i < moves.length; i++) {
302
>
const current = moves[i];
303
>
304
>
const originalDist = current.original.startLineNumber - last.original.endLineNumberExclusive;
305
>
const modifiedDist = current.modified.startLineNumber - last.modified.endLineNumberExclusive;
306
>
const currentMoveAfterLast = originalDist >= 0 && modifiedDist >= 0;
307
>
308
>
if (currentMoveAfterLast && originalDist + modifiedDist <= 2) {
310
>
continue;
311
>
}
313
>
result.push(current);
314
>
}
316
>
}
318
>
function removeMovesInSameDiff(changes: DetailedLineRangeMapping[], moves: LineRangeMapping[]) {
computeMovedLines.ts ×11
319
>
const changesMonotonous = new MonotonousArray(changes);
320
>
moves = moves.filter(m => {
321
>
const diffBeforeEndOfMoveOriginal = changesMonotonous.findLastMonotonous(c => c.original.startLineNumber < m.original.endLineNumberExclusive)
computeMovedLines.ts ×6
322
|| new LineRangeMapping(new LineRange(1, 1), new LineRange(1, 1));
323
>
const diffBeforeEndOfMoveModified = findLastMonotonous(changes, c => c.modified.startLineNumber < m.modified.endLineNumberExclusive);
computeMovedLines.ts ×6
324
>
325
>
const differentDiffs = diffBeforeEndOfMoveOriginal !== diffBeforeEndOfMoveModified;
326
>
return differentDiffs;
328
>
return moves;
329
>
}