Vihren Atlas

heuristicSequenceOptimizations.ts ×26

Code frontier

unlabeled · c_bcea04331df6

59 tests · 8684 LOC · 52 files · introduces 0 tests · 268 LOC · 7 files

Introduces — evidence that enters the hierarchy at this concept

Code
58 ranges268 lines · 7 files
Tests
0 tests

Contains — complete concept membership

All code (extent)
1441 ranges8684 lines · 52 files · Browse complete extent
All tests (intent)
59 testsBrowse complete intent

Neighbourhood graph

The orange circle is the focus. Violet and green circles are every ancestor and descendant, broader and narrower, at any distance; blue squares and pink diamonds are the introduced files and exact introduced tests of every visible concept, not only the focus's. Arrows point from broader to narrower concepts and bridge only concepts omitted from this view. Undirected links show source or test introduction. Concept and file size follows LOC; exact test nodes use test-count units.

Introduced files, introduced tests, and structurally relevant concept specialization

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 native relationship evidence on this page.

Graph controls are ready.

Interactive rendering requires JavaScript and WebGL. Use the native relationship evidence on this page while the interactive map is unavailable.

Native relationship evidence

Every exact file and test below is linked only from the concept that introduces it.

Introduced tests

Every collected test enters the hierarchy at exactly one concept.

No tests are introduced at this concept. Its intent tests are introduced by other concepts.

Introduced code

Every collected source range enters the hierarchy at exactly one concept.

7 files ranked by introduced lines: 268 introduced LOC across 58 ranges. Expand a file to inspect source; the > gutter marks introduced lines.

src/vs/editor/common/diff/defaultLinesDiffComputer/heuristicSequenceOptimizations.ts 142 introduced LOC · 26 ranges

Open complete file

36 return sequenceDiffs;
37 }
38 > heuristicSequenceOptimizations.ts
39 > const result: SequenceDiff[] = [];
40 > result.push(sequenceDiffs[0]);
41 >
42 > // First move them all to the left as much as possible and join them if possible
43 > for (let i = 1; i < sequenceDiffs.length; i++) {
44 const prevResult = result[result.length - 1];
45 let cur = sequenceDiffs[i];
71 result.push(cur);
72 }
73 > heuristicSequenceOptimizations.ts
74 > const result2: SequenceDiff[] = [];
75 > // Then move them all to the right and join them again if possible
76 > for (let i = 0; i < result.length - 1; i++) {
77 const nextResult = result[i + 1];
78 let cur = result[i];
106 result2.push(cur);
107 }
108 > heuristicSequenceOptimizations.ts
109 > if (result.length > 0) {
110 > result2.push(result[result.length - 1]);
111 > }
112 >
113 > return result2;
114 > }
115
116 // align character level diffs at whitespace characters
136
137 for (let i = 0; i < sequenceDiffs.length; i++) {
138 > const prevDiff = (i > 0 ? sequenceDiffs[i - 1] : undefined); heuristicSequenceOptimizations.ts
139 > const diff = sequenceDiffs[i];
140 > const nextDiff = (i + 1 < sequenceDiffs.length ? sequenceDiffs[i + 1] : undefined);
141 >
142 > const seq1ValidRange = new OffsetRange(prevDiff ? prevDiff.seq1Range.endExclusive + 1 : 0, nextDiff ? nextDiff.seq1Range.start - 1 : sequence1.length);
143 > const seq2ValidRange = new OffsetRange(prevDiff ? prevDiff.seq2Range.endExclusive + 1 : 0, nextDiff ? nextDiff.seq2Range.start - 1 : sequence2.length);
144 >
145 > if (diff.seq1Range.isEmpty) {
146 sequenceDiffs[i] = shiftDiffToBetterPosition(diff, sequence1, sequence2, seq1ValidRange, seq2ValidRange);
147 > } else if (diff.seq2Range.isEmpty) { heuristicSequenceOptimizations.ts
148 sequenceDiffs[i] = shiftDiffToBetterPosition(diff.swap(), sequence2, sequence1, seq2ValidRange, seq1ValidRange).swap();
149 }
150 > } heuristicSequenceOptimizations.ts
151
152 return sequenceDiffs;
153 }
154
155 > function shiftDiffToBetterPosition(diff: SequenceDiff, sequence1: ISequence, sequence2: ISequence, seq1ValidRange: OffsetRange, seq2ValidRange: OffsetRange,) { heuristicSequenceOptimizations.ts
156 > const maxShiftLimit = 100; // To prevent performance issues
157 >
158 > // don't touch previous or next!
159 > let deltaBefore = 1;
160 > while (
161 > diff.seq1Range.start - deltaBefore >= seq1ValidRange.start &&
162 diff.seq2Range.start - deltaBefore >= seq2ValidRange.start &&
163 > sequence2.isStronglyEqual(diff.seq2Range.start - deltaBefore, diff.seq2Range.endExclusive - deltaBefore) && deltaBefore < maxShiftLimit heuristicSequenceOptimizations.ts
164 > ) {
165 deltaBefore++;
166 }
167 > deltaBefore--; heuristicSequenceOptimizations.ts
168 >
169 > let deltaAfter = 0;
170 > while (
171 > diff.seq1Range.start + deltaAfter < seq1ValidRange.endExclusive &&
172 diff.seq2Range.endExclusive + deltaAfter < seq2ValidRange.endExclusive &&
173 > sequence2.isStronglyEqual(diff.seq2Range.start + deltaAfter, diff.seq2Range.endExclusive + deltaAfter) && deltaAfter < maxShiftLimit heuristicSequenceOptimizations.ts
174 > ) {
175 deltaAfter++;
176 }
177 > heuristicSequenceOptimizations.ts
178 > if (deltaBefore === 0 && deltaAfter === 0) {
179 return diff;
180 }
202
203 export function removeShortMatches(sequence1: ISequence, sequence2: ISequence, sequenceDiffs: SequenceDiff[]): SequenceDiff[] {
204 > const result: SequenceDiff[] = []; heuristicSequenceOptimizations.ts
205 > for (const s of sequenceDiffs) {
206 > const last = result[result.length - 1];
207 > if (!last) {
208 > result.push(s);
209 > continue;
210 > }
211
212 > if (s.seq1Range.start - last.seq1Range.endExclusive <= 2 || s.seq2Range.start - last.seq2Range.endExclusive <= 2) { heuristicSequenceOptimizations.ts
213 result[result.length - 1] = new SequenceDiff(last.seq1Range.join(s.seq1Range), last.seq2Range.join(s.seq2Range));
214 } else {
215 result.push(s);
216 }
217 > } heuristicSequenceOptimizations.ts
218 >
219 > return result;
220 > }
221
222 export function extendDiffsToEntireWordIfAppropriate(
223 > sequence1: LinesSliceCharSequence, heuristicSequenceOptimizations.ts
224 > sequence2: LinesSliceCharSequence,
225 > sequenceDiffs: SequenceDiff[],
226 > findParent: (seq: LinesSliceCharSequence, idx: number) => OffsetRange | undefined,
227 > force: boolean = false,
228 > ): SequenceDiff[] {
229 > const equalMappings = SequenceDiff.invert(sequenceDiffs, sequence1.length);
230 >
231 > const additional: SequenceDiff[] = [];
232 >
233 > let lastPoint = new OffsetPair(0, 0);
234 >
235 > function scanWord(pair: OffsetPair, equalMapping: SequenceDiff) {
236 if (pair.offset1 < lastPoint.offset1 || pair.offset2 < lastPoint.offset2) {
237 return;
284 lastPoint = w.getEndExclusives();
285 }
286 > heuristicSequenceOptimizations.ts
287 > while (equalMappings.length > 0) {
288 > const next = equalMappings.shift()!;
289 > if (next.seq1Range.isEmpty) {
290 continue;
291 }
294 scanWord(next.getEndExclusives().delta(-1), next);
295 }
296 > heuristicSequenceOptimizations.ts
297 > const merged = mergeSequenceDiffs(sequenceDiffs, additional);
298 > return merged;
299 > }
300
301 > function mergeSequenceDiffs(sequenceDiffs1: SequenceDiff[], sequenceDiffs2: SequenceDiff[]): SequenceDiff[] { heuristicSequenceOptimizations.ts
302 > const result: SequenceDiff[] = [];
303 >
304 > while (sequenceDiffs1.length > 0 || sequenceDiffs2.length > 0) {
305 > const sd1 = sequenceDiffs1[0];
306 > const sd2 = sequenceDiffs2[0];
307 >
308 > let next: SequenceDiff;
309 > if (sd1 && (!sd2 || sd1.seq1Range.start < sd2.seq1Range.start)) {
310 > next = sequenceDiffs1.shift()!;
311 > } else {
312 next = sequenceDiffs2.shift()!;
313 }
314 > heuristicSequenceOptimizations.ts
315 > if (result.length > 0 && result[result.length - 1].seq1Range.endExclusive >= next.seq1Range.start) {
316 result[result.length - 1] = result[result.length - 1].join(next);
317 > } else { heuristicSequenceOptimizations.ts
318 > result.push(next);
319 > }
320 > }
321 >
322 > return result;
323 > }
324
325 export function removeVeryShortMatchingLinesBetweenDiffs(sequence1: LineSequence, _sequence2: LineSequence, sequenceDiffs: SequenceDiff[]): SequenceDiff[] {
371
372 export function removeVeryShortMatchingTextBetweenLongDiffs(sequence1: LinesSliceCharSequence, sequence2: LinesSliceCharSequence, sequenceDiffs: SequenceDiff[]): SequenceDiff[] {
373 > let diffs = sequenceDiffs; heuristicSequenceOptimizations.ts
374 > if (diffs.length === 0) {
375 return diffs;
376 }
377 > heuristicSequenceOptimizations.ts
378 > let counter = 0;
379 > let shouldRepeat: boolean;
380 > do {
381 > shouldRepeat = false;
382 >
383 > const result: SequenceDiff[] = [
384 > diffs[0]
385 > ];
386 >
387 > for (let i = 1; i < diffs.length; i++) {
388 const cur = diffs[i];
389 const lastResult = result[result.length - 1];
436
437 diffs = result;
438 > } while (counter++ < 10 && shouldRepeat); heuristicSequenceOptimizations.ts
439 >
440 > const newDiffs: SequenceDiff[] = [];
441 >
442 > // Remove short suffixes/prefixes
443 > forEachWithNeighbors(diffs, (prev, cur, next) => {
444 > let newDiff = cur;
445 >
446 > function shouldMarkAsChanged(text: string): boolean {
447 > return text.length > 0 && text.trim().length <= 3 && cur.seq1Range.length + cur.seq2Range.length > 100;
448 > }
449 >
450 > const fullRange1 = sequence1.extendToFullLines(cur.seq1Range);
451 > const prefix = sequence1.getText(new OffsetRange(fullRange1.start, cur.seq1Range.start));
452 > if (shouldMarkAsChanged(prefix)) {
453 newDiff = newDiff.deltaStart(-prefix.length);
454 }
455 > const suffix = sequence1.getText(new OffsetRange(cur.seq1Range.endExclusive, fullRange1.endExclusive)); heuristicSequenceOptimizations.ts
456 > if (shouldMarkAsChanged(suffix)) {
457 newDiff = newDiff.deltaEnd(suffix.length);
458 }
459 > heuristicSequenceOptimizations.ts
460 > const availableSpace = SequenceDiff.fromOffsetPairs(
461 > prev ? prev.getEndExclusives() : OffsetPair.zero,
462 > next ? next.getStarts() : OffsetPair.max,
463 > );
464 > const result = newDiff.intersect(availableSpace)!;
465 > if (newDiffs.length > 0 && result.getStarts().equals(newDiffs[newDiffs.length - 1].getEndExclusives())) {
466 newDiffs[newDiffs.length - 1] = newDiffs[newDiffs.length - 1].join(result);
467 > } else { heuristicSequenceOptimizations.ts
468 > newDiffs.push(result);
469 > }
470 > });
471 >
472 > return newDiffs;
473 > }
src/vs/editor/common/diff/defaultLinesDiffComputer/defaultLinesDiffComputer.ts 64 introduced LOC · 9 ranges

Open complete file

155 assertFn(() => {
156 function validatePosition(pos: Position, lines: string[]): boolean {
157 > if (pos.lineNumber < 1 || pos.lineNumber > lines.length) { return false; } defaultLinesDiffComputer.ts
158 > const line = lines[pos.lineNumber - 1];
159 > if (pos.column < 1 || pos.column > line.length + 1) { return false; }
160 > return true;
161 > }
162
163 function validateRange(range: LineRange, lines: string[]): boolean {
164 > if (range.startLineNumber < 1 || range.startLineNumber > lines.length + 1) { return false; } defaultLinesDiffComputer.ts
165 > if (range.endLineNumberExclusive < 1 || range.endLineNumberExclusive > lines.length + 1) { return false; }
166 > return true;
167 > }
168
169 for (const c of changes) {
170 > if (!c.innerChanges) { return false; } defaultLinesDiffComputer.ts
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 }
177 > } defaultLinesDiffComputer.ts
178 > if (!validateRange(c.modified, modifiedLines) || !validateRange(c.original, originalLines)) {
179 return false;
180 }
181 > } defaultLinesDiffComputer.ts
182 return true;
183 });
216
217 private refineDiff(originalLines: string[], modifiedLines: string[], diff: SequenceDiff, timeout: ITimeout, considerWhitespaceChanges: boolean, options: ILinesDiffComputerOptions): { mappings: RangeMapping[]; hitTimeout: boolean } {
218 > const lineRangeMapping = toLineRangeMapping(diff); defaultLinesDiffComputer.ts
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)
226 : this.myersDiffingAlgorithm.compute(slice1, slice2, timeout);
227 > defaultLinesDiffComputer.ts
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 }
241 > defaultLinesDiffComputer.ts
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 > }
264 }
265
266 > function toLineRangeMapping(sequenceDiff: SequenceDiff) { defaultLinesDiffComputer.ts
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 > }
src/vs/editor/common/diff/rangeMapping.ts 21 introduced LOC · 9 ranges

Open complete file

131 */
132 public toRangeMapping2(original: string[], modified: string[]): RangeMapping {
133 > if (isValidLineNumber(this.original.endLineNumberExclusive, original) rangeMapping.ts
134 > && isValidLineNumber(this.modified.endLineNumberExclusive, modified)) {
135 return new RangeMapping(
136 new Range(this.original.startLineNumber, 1, this.original.endLineNumberExclusive, 1),
139 }
140
141 > if (!this.original.isEmpty && !this.modified.isEmpty) { rangeMapping.ts
142 return new RangeMapping(
143 Range.fromPositions(
152 }
153
154 > if (this.original.startLineNumber > 1 && this.modified.startLineNumber > 1) { rangeMapping.ts
155 return new RangeMapping(
156 Range.fromPositions(
169
170 throw new BugIndicatingError();
171 > } rangeMapping.ts
172 }
173
186 }
187
188 > function isValidLineNumber(lineNumber: number, lines: string[]): boolean { rangeMapping.ts
189 > return lineNumber >= 1 && lineNumber <= lines.length;
190 > }
191
192 /**
328 || a1.modified.intersectsOrTouches(a2.modified)
329 )) {
330 > const first = g[0]; rangeMapping.ts
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 > }
339
340 assertFn(() => {
341 if (!dontAssertStartLine && changes.length > 0) {
342 > if (changes[0].modified.startLineNumber !== changes[0].original.startLineNumber) { rangeMapping.ts
343 return false;
344 }
345 > rangeMapping.ts
346 > if (modifiedLines.length.lineCount - changes[changes.length - 1].modified.endLineNumberExclusive !== originalLines.length.lineCount - changes[changes.length - 1].original.endLineNumberExclusive) {
347 return false;
348 }
349 > } rangeMapping.ts
350 return checkAdjacentItems(changes,
351 (m1, m2) => m2.original.startLineNumber - m1.original.endLineNumberExclusive === m2.modified.startLineNumber - m1.modified.endLineNumberExclusive &&
src/vs/base/common/arrays.ts 17 introduced LOC · 6 ranges

Open complete file

176 let last: T | undefined;
177 for (const item of items) {
178 > if (last !== undefined && shouldBeGrouped(last, item)) { arrays.ts
179 currentGroup!.push(item);
180 > } else { arrays.ts
181 > if (currentGroup) {
182 yield currentGroup;
183 }
184 > currentGroup = [item]; arrays.ts
185 > }
186 > last = item;
187 > }
188 if (currentGroup) {
189 > yield currentGroup; arrays.ts
190 > }
191 }
192
193 export function forEachAdjacent<T>(arr: T[], f: (item1: T | undefined, item2: T | undefined) => void): void {
194 > for (let i = 0; i <= arr.length; i++) { arrays.ts
195 > f(i === 0 ? undefined : arr[i - 1], i === arr.length ? undefined : arr[i]);
196 > }
197 > }
198
199 export function forEachWithNeighbors<T>(arr: T[], f: (before: T | undefined, element: T, after: T | undefined) => void): void {
200 > for (let i = 0; i < arr.length; i++) { arrays.ts
201 > f(i === 0 ? undefined : arr[i - 1], arr[i], i + 1 === arr.length ? undefined : arr[i + 1]);
202 > }
203 > }
204
205 export function concatArrays<T extends any[]>(...arrays: T): T[number][number][] {
src/vs/editor/common/diff/defaultLinesDiffComputer/algorithms/diffAlgorithm.ts 14 introduced LOC · 5 ranges

Open complete file

47
48 public static fromOffsetPairs(start: OffsetPair, endExclusive: OffsetPair): SequenceDiff {
49 > return new SequenceDiff( diffAlgorithm.ts
50 > new OffsetRange(start.offset1, endExclusive.offset1),
51 > new OffsetRange(start.offset2, endExclusive.offset2),
52 > );
53 > }
54
55 public static assertSorted(sequenceDiffs: SequenceDiff[]): void {
108
109 public intersect(other: SequenceDiff): SequenceDiff | undefined {
110 > const i1 = this.seq1Range.intersect(other.seq1Range); diffAlgorithm.ts
111 > const i2 = this.seq2Range.intersect(other.seq2Range);
112 > if (!i1 || !i2) {
113 return undefined;
114 }
115 > return new SequenceDiff(i1, i2); diffAlgorithm.ts
116 > }
117
118 public getStarts(): OffsetPair {
119 > return new OffsetPair(this.seq1Range.start, this.seq2Range.start); diffAlgorithm.ts
120 > }
121
122 public getEndExclusives(): OffsetPair {
123 > return new OffsetPair(this.seq1Range.endExclusive, this.seq2Range.endExclusive); diffAlgorithm.ts
124 > }
125 }
126
src/vs/editor/common/diff/defaultLinesDiffComputer/algorithms/dynamicProgrammingDiffing.ts 5 introduced LOC · 1 range

Open complete file

77 function reportDecreasingAligningPositions(s1: number, s2: number): void {
78 if (s1 + 1 !== lastAligningPosS1 || s2 + 1 !== lastAligningPosS2) {
79 > result.push(new SequenceDiff( dynamicProgrammingDiffing.ts
80 > new OffsetRange(s1 + 1, lastAligningPosS1),
81 > new OffsetRange(s2 + 1, lastAligningPosS2),
82 > ));
83 > }
84 lastAligningPosS1 = s1;
85 lastAligningPosS2 = s2;
src/vs/editor/common/diff/defaultLinesDiffComputer/linesSliceCharSequence.ts 5 introduced LOC · 2 ranges

Open complete file

110
111 public translateRange(range: OffsetRange): Range {
112 > const pos1 = this.translateOffset(range.start, 'right'); linesSliceCharSequence.ts
113 > const pos2 = this.translateOffset(range.endExclusive, 'left');
114 > if (pos2.isBefore(pos1)) {
115 return Range.fromPositions(pos2, pos2);
116 }
117 > return Range.fromPositions(pos1, pos2); linesSliceCharSequence.ts
118 > }
119
120 /**

Direct hierarchy

Parents

Children