Vihren Atlas

heuristicSequenceOptimizations.ts ×9

Code frontier

unlabeled · c_50226ecb4ddf

133 tests · 7991 LOC · 52 files · introduces 0 tests · 129 LOC · 4 files

Introduces — evidence that enters the hierarchy at this concept

Code
28 ranges129 lines · 4 files
Tests
0 tests

Contains — complete concept membership

All code (extent)
1274 ranges7991 lines · 52 files · Browse complete extent
All tests (intent)
133 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.

4 files ranked by introduced lines: 129 introduced LOC across 28 ranges. Expand a file to inspect source; the > gutter marks introduced lines.

src/vs/editor/common/diff/defaultLinesDiffComputer/heuristicSequenceOptimizations.ts 52 introduced LOC · 9 ranges

Open complete file

1 > /*--------------------------------------------------------------------------------------------- heuristicSequenceOptimizations.ts
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 { forEachWithNeighbors } from '../../../../base/common/arrays.js';
7 > import { OffsetRange } from '../../core/ranges/offsetRange.js';
8 > import { ISequence, OffsetPair, SequenceDiff } from './algorithms/diffAlgorithm.js';
9 > import { LineSequence } from './lineSequence.js';
10 > import { LinesSliceCharSequence } from './linesSliceCharSequence.js';
11 >
12 > export function optimizeSequenceDiffs(sequence1: ISequence, sequence2: ISequence, sequenceDiffs: SequenceDiff[]): SequenceDiff[] {
13 let result = sequenceDiffs;
14 result = joinSequenceDiffsByShifting(sequence1, sequence2, result);
19 return result;
20 }
21 > heuristicSequenceOptimizations.ts
22 > /**
23 > * This function fixes issues like this:
24 > * ```
25 > * import { Baz, Bar } from "foo";
26 > * ```
27 > * <->
28 > * ```
29 > * import { Baz, Bar, Foo } from "foo";
30 > * ```
31 > * Computed diff: [ {Add "," after Bar}, {Add "Foo " after space} }
32 > * Improved diff: [{Add ", Foo" after Bar}]
33 > */
34 function joinSequenceDiffsByShifting(sequence1: ISequence, sequence2: ISequence, sequenceDiffs: SequenceDiff[]): SequenceDiff[] {
35 if (sequenceDiffs.length === 0) {
113 return result2;
114 }
115 > heuristicSequenceOptimizations.ts
116 > // align character level diffs at whitespace characters
117 > // import { IBar } from "foo";
118 > // import { I[Arr, I]Bar } from "foo";
119 > // ->
120 > // import { [IArr, ]IBar } from "foo";
121 >
122 > // import { ITransaction, observableValue, transaction } from 'vs/base/common/observable';
123 > // import { ITransaction, observable[FromEvent, observable]Value, transaction } from 'vs/base/common/observable';
124 > // ->
125 > // import { ITransaction, [observableFromEvent, ]observableValue, transaction } from 'vs/base/common/observable';
126 >
127 > // collectBrackets(level + 1, levelPerBracketType);
128 > // collectBrackets(level + 1, levelPerBracket[ + 1, levelPerBracket]Type);
129 > // ->
130 > // collectBrackets(level + 1, [levelPerBracket + 1, ]levelPerBracketType);
131 >
132 function shiftSequenceDiffs(sequence1: ISequence, sequence2: ISequence, sequenceDiffs: SequenceDiff[]): SequenceDiff[] {
133 if (!sequence1.getBoundaryScore || !sequence2.getBoundaryScore) {
152 return sequenceDiffs;
153 }
154 > heuristicSequenceOptimizations.ts
155 function shiftDiffToBetterPosition(diff: SequenceDiff, sequence1: ISequence, sequence2: ISequence, seq1ValidRange: OffsetRange, seq2ValidRange: OffsetRange,) {
156 const maxShiftLimit = 100; // To prevent performance issues
200 return diff.delta(bestDelta);
201 }
202 > heuristicSequenceOptimizations.ts
203 > export function removeShortMatches(sequence1: ISequence, sequence2: ISequence, sequenceDiffs: SequenceDiff[]): SequenceDiff[] {
204 const result: SequenceDiff[] = [];
205 for (const s of sequenceDiffs) {
219 return result;
220 }
221 > heuristicSequenceOptimizations.ts
222 > export function extendDiffsToEntireWordIfAppropriate(
223 sequence1: LinesSliceCharSequence,
224 sequence2: LinesSliceCharSequence,
298 return merged;
299 }
300 > heuristicSequenceOptimizations.ts
301 function mergeSequenceDiffs(sequenceDiffs1: SequenceDiff[], sequenceDiffs2: SequenceDiff[]): SequenceDiff[] {
302 const result: SequenceDiff[] = [];
322 return result;
323 }
324 > heuristicSequenceOptimizations.ts
325 > export function removeVeryShortMatchingLinesBetweenDiffs(sequence1: LineSequence, _sequence2: LineSequence, sequenceDiffs: SequenceDiff[]): SequenceDiff[] {
326 let diffs = sequenceDiffs;
327 if (diffs.length === 0) {
369 return diffs;
370 }
371 > heuristicSequenceOptimizations.ts
372 > export function removeVeryShortMatchingTextBetweenLongDiffs(sequence1: LinesSliceCharSequence, sequence2: LinesSliceCharSequence, sequenceDiffs: SequenceDiff[]): SequenceDiff[] {
373 let diffs = sequenceDiffs;
374 if (diffs.length === 0) {
src/vs/editor/common/diff/defaultLinesDiffComputer/defaultLinesDiffComputer.ts 31 introduced LOC · 5 ranges

Open complete file

1 > /*--------------------------------------------------------------------------------------------- defaultLinesDiffComputer.ts
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();
25 private readonly myersDiffingAlgorithm = new MyersDiffAlgorithm();
26 > defaultLinesDiffComputer.ts
27 > computeDiff(originalLines: string[], modifiedLines: string[], options: ILinesDiffComputerOptions): LinesDiff {
28 if (originalLines.length <= 1 && equals(originalLines, modifiedLines, (a, b) => a === b)) {
29 return new LinesDiff([], [], false);
185 return new LinesDiff(changes, moves, hitTimeout);
186 }
187 > defaultLinesDiffComputer.ts
188 > private computeMoves(
189 changes: DetailedLineRangeMapping[],
190 originalLines: string[],
214 return movesWithDiffs;
215 }
216 > defaultLinesDiffComputer.ts
217 > private refineDiff(originalLines: string[], modifiedLines: string[], diff: SequenceDiff, timeout: ITimeout, considerWhitespaceChanges: boolean, options: ILinesDiffComputerOptions): { mappings: RangeMapping[]; hitTimeout: boolean } {
218 const lineRangeMapping = toLineRangeMapping(diff);
219 const rangeMapping = lineRangeMapping.toRangeMapping2(originalLines, modifiedLines);
262 };
263 }
264 > } defaultLinesDiffComputer.ts
265 >
266 function toLineRangeMapping(sequenceDiff: SequenceDiff) {
267 return new LineRangeMapping(
src/vs/editor/common/diff/defaultLinesDiffComputer/computeMovedLines.ts 23 introduced LOC · 7 ranges

Open complete file

1 > /*--------------------------------------------------------------------------------------------- computeMovedLines.ts
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(
18 changes: DetailedLineRangeMapping[],
19 originalLines: string[],
42 return moves;
43 }
44 > computeMovedLines.ts
45 function countWhere<T>(arr: T[], predicate: (t: T) => boolean): number {
46 let count = 0;
52 return count;
53 }
54 > computeMovedLines.ts
55 function computeMovesFromSimpleDeletionsToSimpleInsertions(
56 changes: DetailedLineRangeMapping[],
95 return { moves, excludedChanges };
96 }
97 > computeMovedLines.ts
98 function computeUnchangedMoves(
99 changes: DetailedLineRangeMapping[],
254 return moves;
255 }
256 > computeMovedLines.ts
257 function areLinesSimilar(line1: string, line2: string, timeout: ITimeout): boolean {
258 if (line1.trim() === line2.trim()) { return true; }
289 return r;
290 }
291 > computeMovedLines.ts
292 function joinCloseConsecutiveMoves(moves: LineRangeMapping[]): LineRangeMapping[] {
293 if (moves.length === 0) {
315 return result;
316 }
317 > computeMovedLines.ts
318 function removeMovesInSameDiff(changes: DetailedLineRangeMapping[], moves: LineRangeMapping[]) {
319 const changesMonotonous = new MonotonousArray(changes);
src/vs/editor/common/diff/defaultLinesDiffComputer/lineSequence.ts 23 introduced LOC · 7 ranges

Open complete file

1 > /*--------------------------------------------------------------------------------------------- lineSequence.ts
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 { CharCode } from '../../../../base/common/charCode.js';
7 > import { OffsetRange } from '../../core/ranges/offsetRange.js';
8 > import { ISequence } from './algorithms/diffAlgorithm.js';
9 >
10 > export class LineSequence implements ISequence {
11 > constructor(
12 private readonly trimmedHash: number[],
13 private readonly lines: string[]
14 ) { }
15 > lineSequence.ts
16 > getElement(offset: number): number {
17 return this.trimmedHash[offset];
18 }
19 > lineSequence.ts
20 > get length(): number {
21 return this.trimmedHash.length;
22 }
23 > lineSequence.ts
24 > getBoundaryScore(length: number): number {
25 const indentationBefore = length === 0 ? 0 : getIndentation(this.lines[length - 1]);
26 const indentationAfter = length === this.lines.length ? 0 : getIndentation(this.lines[length]);
27 return 1000 - (indentationBefore + indentationAfter);
28 }
29 > lineSequence.ts
30 > getText(range: OffsetRange): string {
31 return this.lines.slice(range.start, range.endExclusive).join('\n');
32 }
33 > lineSequence.ts
34 > isStronglyEqual(offset1: number, offset2: number): boolean {
35 return this.lines[offset1] === this.lines[offset2];
36 }
37 > } lineSequence.ts
38 >
39 function getIndentation(str: string): number {
40 let i = 0;

Direct hierarchy

Parents

Children