src/vs/editor/common/diff/rangeMapping.ts
416 LOC · 273 covered · 143 uncovered · 72 ranges · 419 concepts · 19 introducers · 187 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
>
/*---------------------------------------------------------------------------------------------
rangeMapping.ts ×28
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 { groupAdjacentBy } from '../../../base/common/arrays.js';
7
>
import { assertFn, checkAdjacentItems } from '../../../base/common/assert.js';
8
>
import { BugIndicatingError } from '../../../base/common/errors.js';
9
>
import { LineRange } from '../core/ranges/lineRange.js';
10
>
import { Position } from '../core/position.js';
11
>
import { Range } from '../core/range.js';
12
>
import { TextReplacement, TextEdit } from '../core/edits/textEdit.js';
13
>
import { AbstractText } from '../core/text/abstractText.js';
14
>
import { IChange } from './legacyLinesDiffComputer.js';
15
>
16
>
/**
17
>
* Maps a line range in the original text model to a line range in the modified text model.
18
>
*/
19
>
export class LineRangeMapping {
20
>
public static inverse(mapping: readonly LineRangeMapping[], originalLineCount: number, modifiedLineCount: number): LineRangeMapping[] {
21
const result: LineRangeMapping[] = [];
22
let lastOriginalEndLineNumber = 1;
23
let lastModifiedEndLineNumber = 1;
24
25
for (const m of mapping) {
26
const r = new LineRangeMapping(
27
new LineRange(lastOriginalEndLineNumber, m.original.startLineNumber),
28
new LineRange(lastModifiedEndLineNumber, m.modified.startLineNumber),
29
);
30
if (!r.modified.isEmpty) {
31
result.push(r);
32
}
33
lastOriginalEndLineNumber = m.original.endLineNumberExclusive;
34
lastModifiedEndLineNumber = m.modified.endLineNumberExclusive;
35
}
36
const r = new LineRangeMapping(
37
new LineRange(lastOriginalEndLineNumber, originalLineCount + 1),
38
new LineRange(lastModifiedEndLineNumber, modifiedLineCount + 1),
39
);
40
if (!r.modified.isEmpty) {
41
result.push(r);
42
}
43
return result;
44
}
46
>
public static clip(mapping: readonly LineRangeMapping[], originalRange: LineRange, modifiedRange: LineRange): LineRangeMapping[] {
47
const result: LineRangeMapping[] = [];
48
for (const m of mapping) {
49
const original = m.original.intersect(originalRange);
50
const modified = m.modified.intersect(modifiedRange);
51
if (original && !original.isEmpty && modified && !modified.isEmpty) {
52
result.push(new LineRangeMapping(original, modified));
53
}
54
}
55
return result;
56
}
58
>
/**
59
>
* The line range in the original text model.
60
>
*/
61
>
public readonly original: LineRange;
62
>
63
>
/**
64
>
* The line range in the modified text model.
65
>
*/
66
>
public readonly modified: LineRange;
67
>
68
>
constructor(
70
>
modifiedRange: LineRange
71
>
) {
72
>
this.original = originalRange;
73
>
this.modified = modifiedRange;
74
>
}
76
>
77
>
public toString(): string {
79
>
}
81
>
public flip(): LineRangeMapping {
82
return new LineRangeMapping(this.modified, this.original);
83
}
85
>
public join(other: LineRangeMapping): LineRangeMapping {
87
>
this.original.join(other.original),
88
>
this.modified.join(other.modified)
89
>
);
90
>
}
92
>
public get changedLineCount() {
93
return Math.max(this.original.length, this.modified.length);
94
}
96
>
/**
97
>
* This method assumes that the LineRangeMapping describes a valid diff!
98
>
* I.e. if one range is empty, the other range cannot be the entire document.
99
>
* It avoids various problems when the line range points to non-existing line-numbers.
100
>
*/
101
>
public toRangeMapping(): RangeMapping {
102
const origInclusiveRange = this.original.toInclusiveRange();
103
const modInclusiveRange = this.modified.toInclusiveRange();
104
if (origInclusiveRange && modInclusiveRange) {
105
return new RangeMapping(origInclusiveRange, modInclusiveRange);
106
} else if (this.original.startLineNumber === 1 || this.modified.startLineNumber === 1) {
107
if (!(this.modified.startLineNumber === 1 && this.original.startLineNumber === 1)) {
108
// If one line range starts at 1, the other one must start at 1 as well.
109
throw new BugIndicatingError('not a valid diff');
110
}
111
112
// Because one range is empty and both ranges start at line 1, none of the ranges can cover all lines.
113
// Thus, `endLineNumberExclusive` is a valid line number.
114
return new RangeMapping(
115
new Range(this.original.startLineNumber, 1, this.original.endLineNumberExclusive, 1),
116
new Range(this.modified.startLineNumber, 1, this.modified.endLineNumberExclusive, 1),
117
);
118
} else {
119
// We can assume here that both startLineNumbers are greater than 1.
120
return new RangeMapping(
121
new Range(this.original.startLineNumber - 1, Number.MAX_SAFE_INTEGER, this.original.endLineNumberExclusive - 1, Number.MAX_SAFE_INTEGER),
122
new Range(this.modified.startLineNumber - 1, Number.MAX_SAFE_INTEGER, this.modified.endLineNumberExclusive - 1, Number.MAX_SAFE_INTEGER),
123
);
124
}
125
}
127
>
/**
128
>
* This method assumes that the LineRangeMapping describes a valid diff!
129
>
* I.e. if one range is empty, the other range cannot be the entire document.
130
>
* It avoids various problems when the line range points to non-existing line-numbers.
131
>
*/
132
>
public toRangeMapping2(original: string[], modified: string[]): RangeMapping {
133
>
if (isValidLineNumber(this.original.endLineNumberExclusive, original)
heuristicSequenceOptimizations.ts ×26
134
>
&& isValidLineNumber(this.modified.endLineNumberExclusive, modified)) {
136
>
new Range(this.original.startLineNumber, 1, this.original.endLineNumberExclusive, 1),
137
>
new Range(this.modified.startLineNumber, 1, this.modified.endLineNumberExclusive, 1),
138
>
);
139
>
}
143
>
Range.fromPositions(
144
>
new Position(this.original.startLineNumber, 1),
145
>
normalizePosition(new Position(this.original.endLineNumberExclusive - 1, Number.MAX_SAFE_INTEGER), original)
146
>
),
147
>
Range.fromPositions(
148
>
new Position(this.modified.startLineNumber, 1),
149
>
normalizePosition(new Position(this.modified.endLineNumberExclusive - 1, Number.MAX_SAFE_INTEGER), modified)
150
>
),
151
>
);
152
>
}
154
>
if (this.original.startLineNumber > 1 && this.modified.startLineNumber > 1) {
heuristicSequenceOptimizations.ts ×26
156
>
Range.fromPositions(
157
>
normalizePosition(new Position(this.original.startLineNumber - 1, Number.MAX_SAFE_INTEGER), original),
158
>
normalizePosition(new Position(this.original.endLineNumberExclusive - 1, Number.MAX_SAFE_INTEGER), original)
159
>
),
160
>
Range.fromPositions(
161
>
normalizePosition(new Position(this.modified.startLineNumber - 1, Number.MAX_SAFE_INTEGER), modified),
162
>
normalizePosition(new Position(this.modified.endLineNumberExclusive - 1, Number.MAX_SAFE_INTEGER), modified)
163
>
),
164
>
);
165
>
}
166
167
// Situation now: one range is empty and one range touches the last line and one range starts at line 1.
168
// I don't think this can happen.
169
170
throw new BugIndicatingError();
173
>
174
>
function normalizePosition(position: Position, content: string[]): Position {
rangeMapping.ts ×4
175
>
if (position.lineNumber < 1) {
176
return new Position(1, 1);
177
}
179
return new Position(content.length, content[content.length - 1].length + 1);
180
}
182
>
if (position.column > line.length + 1) {
183
>
return new Position(position.lineNumber, line.length + 1);
184
>
}
185
return position;
186
}
188
>
function isValidLineNumber(lineNumber: number, lines: string[]): boolean {
heuristicSequenceOptimizations.ts ×26
189
>
return lineNumber >= 1 && lineNumber <= lines.length;
190
>
}
192
>
/**
193
>
* Maps a line range in the original text model to a line range in the modified text model.
194
>
* Also contains inner range mappings.
195
>
*/
196
>
export class DetailedLineRangeMapping extends LineRangeMapping {
197
>
public static toTextEdit(mapping: readonly DetailedLineRangeMapping[], modified: AbstractText): TextEdit {
198
const replacements: TextReplacement[] = [];
199
for (const m of mapping) {
200
for (const r of m.innerChanges ?? []) {
201
const replacement = r.toTextEdit(modified);
202
replacements.push(replacement);
203
}
204
}
205
return new TextEdit(replacements);
206
}
208
>
public static fromRangeMappings(rangeMappings: RangeMapping[]): DetailedLineRangeMapping {
209
const originalRange = LineRange.join(rangeMappings.map(r => LineRange.fromRangeInclusive(r.originalRange)));
210
const modifiedRange = LineRange.join(rangeMappings.map(r => LineRange.fromRangeInclusive(r.modifiedRange)));
211
return new DetailedLineRangeMapping(originalRange, modifiedRange, rangeMappings);
212
}
214
>
/**
215
>
* If inner changes have not been computed, this is set to undefined.
216
>
* Otherwise, it represents the character-level diff in this line range.
217
>
* The original range of each range mapping should be contained in the original line range (same for modified), exceptions are new-lines.
218
>
* Must not be an empty array.
219
>
*/
220
>
public readonly innerChanges: RangeMapping[] | undefined;
221
>
222
>
constructor(
224
>
modifiedRange: LineRange,
225
>
innerChanges: RangeMapping[] | undefined
226
>
) {
227
>
super(originalRange, modifiedRange);
228
>
this.innerChanges = innerChanges;
229
>
}
231
>
public override flip(): DetailedLineRangeMapping {
232
return new DetailedLineRangeMapping(this.modified, this.original, this.innerChanges?.map(c => c.flip()));
233
}
235
>
public withInnerChangesFromLineRanges(): DetailedLineRangeMapping {
236
return new DetailedLineRangeMapping(this.original, this.modified, [this.toRangeMapping()]);
237
}
239
>
240
>
/**
241
>
* Maps a range in the original text model to a range in the modified text model.
242
>
*/
243
>
export class RangeMapping {
244
>
public static fromEdit(edit: TextEdit): RangeMapping[] {
245
const newRanges = edit.getNewRanges();
246
const result = edit.replacements.map((e, idx) => new RangeMapping(e.range, newRanges[idx]));
247
return result;
248
}
250
>
public static fromEditJoin(edit: TextEdit): RangeMapping {
251
const newRanges = edit.getNewRanges();
252
const result = edit.replacements.map((e, idx) => new RangeMapping(e.range, newRanges[idx]));
253
return RangeMapping.join(result);
254
}
256
>
public static join(rangeMappings: RangeMapping[]): RangeMapping {
257
if (rangeMappings.length === 0) {
258
throw new BugIndicatingError('Cannot join an empty list of range mappings');
259
}
260
let result = rangeMappings[0];
261
for (let i = 1; i < rangeMappings.length; i++) {
262
result = result.join(rangeMappings[i]);
263
}
264
return result;
265
}
267
>
public static assertSorted(rangeMappings: RangeMapping[]): void {
270
>
const current = rangeMappings[i];
271
>
if (!(
272
>
previous.originalRange.getEndPosition().isBeforeOrEqual(current.originalRange.getStartPosition())
273
>
&& previous.modifiedRange.getEndPosition().isBeforeOrEqual(current.modifiedRange.getStartPosition())
274
>
)) {
275
throw new BugIndicatingError('Range mappings must be sorted');
276
}
280
>
/**
281
>
* The original range.
282
>
*/
283
>
readonly originalRange: Range;
284
>
285
>
/**
286
>
* The modified range.
287
>
*/
288
>
readonly modifiedRange: Range;
289
>
290
>
constructor(
292
>
modifiedRange: Range
293
>
) {
294
>
this.originalRange = originalRange;
295
>
this.modifiedRange = modifiedRange;
296
>
}
298
>
public toString(): string {
299
return `{${this.originalRange.toString()}->${this.modifiedRange.toString()}}`;
300
}
302
>
public flip(): RangeMapping {
303
return new RangeMapping(this.modifiedRange, this.originalRange);
304
}
306
>
/**
307
>
* Creates a single text edit that describes the change from the original to the modified text.
308
>
*/
309
>
public toTextEdit(modified: AbstractText): TextReplacement {
310
const newText = modified.getValueOfRange(this.modifiedRange);
311
return new TextReplacement(this.originalRange, newText);
312
}
314
>
public join(other: RangeMapping): RangeMapping {
315
return new RangeMapping(
316
this.originalRange.plusRange(other.originalRange),
317
this.modifiedRange.plusRange(other.modifiedRange)
318
);
319
}
321
>
322
>
export function lineRangeMappingFromRangeMappings(alignments: readonly RangeMapping[], originalLines: AbstractText, modifiedLines: AbstractText, dontAssertStartLine: boolean = false): DetailedLineRangeMapping[] {
324
>
for (const g of groupAdjacentBy(
325
>
alignments.map(a => getLineRangeMapping(a, originalLines, modifiedLines)),
326
>
(a1, a2) =>
331
>
const last = g[g.length - 1];
332
>
333
>
changes.push(new DetailedLineRangeMapping(
334
>
first.original.join(last.original),
335
>
first.modified.join(last.modified),
336
>
g.map(a => a.innerChanges![0]),
337
>
));
338
>
}
340
>
assertFn(() => {
341
>
if (!dontAssertStartLine && changes.length > 0) {
342
>
if (changes[0].modified.startLineNumber !== changes[0].original.startLineNumber) {
heuristicSequenceOptimizations.ts ×26
343
return false;
344
}
346
>
if (modifiedLines.length.lineCount - changes[changes.length - 1].modified.endLineNumberExclusive !== originalLines.length.lineCount - changes[changes.length - 1].original.endLineNumberExclusive) {
347
return false;
348
}
351
>
(m1, m2) => m2.original.startLineNumber - m1.original.endLineNumberExclusive === m2.modified.startLineNumber - m1.modified.endLineNumberExclusive &&
352
>
// There has to be an unchanged line in between (otherwise both diffs should have been joined)
rangeMapping.ts ×2
353
>
m1.original.endLineNumberExclusive < m2.original.startLineNumber &&
354
>
m1.modified.endLineNumberExclusive < m2.modified.startLineNumber,
356
>
});
357
>
358
>
return changes;
359
>
}
361
>
export function getLineRangeMapping(rangeMapping: RangeMapping, originalLines: AbstractText, modifiedLines: AbstractText): DetailedLineRangeMapping {
363
>
let lineEndDelta = 0;
364
>
365
>
// rangeMapping describes the edit that replaces `rangeMapping.originalRange` with `newText := getText(modifiedLines, rangeMapping.modifiedRange)`.
366
>
367
>
// original: ]xxx \n <- this line is not modified
368
>
// modified: ]xx \n
369
>
if (rangeMapping.modifiedRange.endColumn === 1 && rangeMapping.originalRange.endColumn === 1
370
>
&& rangeMapping.originalRange.startLineNumber + lineStartDelta <= rangeMapping.originalRange.endLineNumber
rangeMapping.ts ×2
371
>
&& rangeMapping.modifiedRange.startLineNumber + lineStartDelta <= rangeMapping.modifiedRange.endLineNumber) {
rangeMapping.ts ×5
373
>
lineEndDelta = -1;
374
>
}
376
>
// original: xxx[ \n <- this line is not modified
377
>
// modified: xxx[ \n
378
>
if (rangeMapping.modifiedRange.startColumn - 1 >= modifiedLines.getLineLength(rangeMapping.modifiedRange.startLineNumber)
379
>
&& rangeMapping.originalRange.startColumn - 1 >= originalLines.getLineLength(rangeMapping.originalRange.startLineNumber)
rangeMapping.ts ×1
380
>
&& rangeMapping.originalRange.startLineNumber <= rangeMapping.originalRange.endLineNumber + lineEndDelta
rangeMapping.ts ×1
381
>
&& rangeMapping.modifiedRange.startLineNumber <= rangeMapping.modifiedRange.endLineNumber + lineEndDelta) {
rangeMapping.ts ×5
383
>
lineStartDelta = 1;
384
>
}
386
>
const originalLineRange = new LineRange(
387
>
rangeMapping.originalRange.startLineNumber + lineStartDelta,
388
>
rangeMapping.originalRange.endLineNumber + 1 + lineEndDelta
389
>
);
390
>
const modifiedLineRange = new LineRange(
391
>
rangeMapping.modifiedRange.startLineNumber + lineStartDelta,
392
>
rangeMapping.modifiedRange.endLineNumber + 1 + lineEndDelta
393
>
);
394
>
395
>
return new DetailedLineRangeMapping(originalLineRange, modifiedLineRange, [rangeMapping]);
396
>
}
398
>
export function lineRangeMappingFromChange(change: IChange): LineRangeMapping {
399
let originalRange: LineRange;
400
if (change.originalEndLineNumber === 0) {
401
// Insertion
402
originalRange = new LineRange(change.originalStartLineNumber + 1, change.originalStartLineNumber + 1);
403
} else {
404
originalRange = new LineRange(change.originalStartLineNumber, change.originalEndLineNumber + 1);
405
}
406
407
let modifiedRange: LineRange;
408
if (change.modifiedEndLineNumber === 0) {
409
// Deletion
410
modifiedRange = new LineRange(change.modifiedStartLineNumber + 1, change.modifiedStartLineNumber + 1);
411
} else {
412
modifiedRange = new LineRange(change.modifiedStartLineNumber, change.modifiedEndLineNumber + 1);
413
}
414
415
return new LineRangeMapping(originalRange, modifiedRange);
416
}