Vihren Atlas

diffAlgorithm.ts ×23

Code frontier

unlabeled · c_a049f31b1f13

138 tests · 6366 LOC · 40 files · introduces 0 tests · 285 LOC · 5 files

Introduces — evidence that enters the hierarchy at this concept

Code
60 ranges285 lines · 5 files
Tests
0 tests

Contains — complete concept membership

All code (extent)
1044 ranges6366 lines · 40 files · Browse complete extent
All tests (intent)
138 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.

5 files ranked by introduced lines: 285 introduced LOC across 60 ranges. Expand a file to inspect source; the > gutter marks introduced lines.

src/vs/editor/common/diff/defaultLinesDiffComputer/algorithms/diffAlgorithm.ts 122 introduced LOC · 23 ranges

Open complete file

1 > /*--------------------------------------------------------------------------------------------- diffAlgorithm.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 { forEachAdjacent } from '../../../../../base/common/arrays.js';
7 > import { BugIndicatingError } from '../../../../../base/common/errors.js';
8 > import { OffsetRange } from '../../../core/ranges/offsetRange.js';
9 >
10 > /**
11 > * Represents a synchronous diff algorithm. Should be executed in a worker.
12 > */
13 > export interface IDiffAlgorithm {
14 > compute(sequence1: ISequence, sequence2: ISequence, timeout?: ITimeout): DiffAlgorithmResult;
15 > }
16 >
17 > export class DiffAlgorithmResult {
18 > static trivial(seq1: ISequence, seq2: ISequence): DiffAlgorithmResult {
19 > return new DiffAlgorithmResult([new SequenceDiff(OffsetRange.ofLength(seq1.length), OffsetRange.ofLength(seq2.length))], false);
20 > }
21 >
22 > static trivialTimedOut(seq1: ISequence, seq2: ISequence): DiffAlgorithmResult {
23 return new DiffAlgorithmResult([new SequenceDiff(OffsetRange.ofLength(seq1.length), OffsetRange.ofLength(seq2.length))], true);
24 }
25 > diffAlgorithm.ts
26 > constructor(
27 public readonly diffs: SequenceDiff[],
28 /**
32 public readonly hitTimeout: boolean,
33 ) { }
34 > } diffAlgorithm.ts
35 >
36 > export class SequenceDiff {
37 > public static invert(sequenceDiffs: SequenceDiff[], doc1Length: number): SequenceDiff[] {
38 > const result: SequenceDiff[] = [];
39 > forEachAdjacent(sequenceDiffs, (a, b) => {
40 > result.push(SequenceDiff.fromOffsetPairs(
41 > a ? a.getEndExclusives() : OffsetPair.zero,
42 > b ? b.getStarts() : new OffsetPair(doc1Length, (a ? a.seq2Range.endExclusive - a.seq1Range.endExclusive : 0) + doc1Length)
43 > ));
44 > });
45 > return result;
46 > }
47 >
48 > public static fromOffsetPairs(start: OffsetPair, endExclusive: OffsetPair): SequenceDiff {
49 return new SequenceDiff(
50 new OffsetRange(start.offset1, endExclusive.offset1),
52 );
53 }
54 > diffAlgorithm.ts
55 > public static assertSorted(sequenceDiffs: SequenceDiff[]): void {
56 let last: SequenceDiff | undefined = undefined;
57 for (const cur of sequenceDiffs) {
64 }
65 }
66 > diffAlgorithm.ts
67 > constructor(
68 public readonly seq1Range: OffsetRange,
69 public readonly seq2Range: OffsetRange,
70 ) { }
71 > diffAlgorithm.ts
72 > public swap(): SequenceDiff {
73 return new SequenceDiff(this.seq2Range, this.seq1Range);
74 }
75 > diffAlgorithm.ts
76 > public toString(): string {
77 return `${this.seq1Range} <-> ${this.seq2Range}`;
78 }
79 > diffAlgorithm.ts
80 > public join(other: SequenceDiff): SequenceDiff {
81 return new SequenceDiff(this.seq1Range.join(other.seq1Range), this.seq2Range.join(other.seq2Range));
82 }
83 > diffAlgorithm.ts
84 > public delta(offset: number): SequenceDiff {
85 if (offset === 0) {
86 return this;
88 return new SequenceDiff(this.seq1Range.delta(offset), this.seq2Range.delta(offset));
89 }
90 > diffAlgorithm.ts
91 > public deltaStart(offset: number): SequenceDiff {
92 if (offset === 0) {
93 return this;
95 return new SequenceDiff(this.seq1Range.deltaStart(offset), this.seq2Range.deltaStart(offset));
96 }
97 > diffAlgorithm.ts
98 > public deltaEnd(offset: number): SequenceDiff {
99 if (offset === 0) {
100 return this;
102 return new SequenceDiff(this.seq1Range.deltaEnd(offset), this.seq2Range.deltaEnd(offset));
103 }
104 > diffAlgorithm.ts
105 > public intersectsOrTouches(other: SequenceDiff): boolean {
106 return this.seq1Range.intersectsOrTouches(other.seq1Range) || this.seq2Range.intersectsOrTouches(other.seq2Range);
107 }
108 > diffAlgorithm.ts
109 > public intersect(other: SequenceDiff): SequenceDiff | undefined {
110 const i1 = this.seq1Range.intersect(other.seq1Range);
111 const i2 = this.seq2Range.intersect(other.seq2Range);
115 return new SequenceDiff(i1, i2);
116 }
117 > diffAlgorithm.ts
118 > public getStarts(): OffsetPair {
119 return new OffsetPair(this.seq1Range.start, this.seq2Range.start);
120 }
121 > diffAlgorithm.ts
122 > public getEndExclusives(): OffsetPair {
123 return new OffsetPair(this.seq1Range.endExclusive, this.seq2Range.endExclusive);
124 }
125 > } diffAlgorithm.ts
126 >
127 > export class OffsetPair {
128 > public static readonly zero = new OffsetPair(0, 0);
129 > public static readonly max = new OffsetPair(Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
130 >
131 > constructor(
132 > public readonly offset1: number,
133 > public readonly offset2: number,
134 > ) {
135 > }
136 >
137 > public toString(): string {
138 return `${this.offset1} <-> ${this.offset2}`;
139 }
140 > diffAlgorithm.ts
141 > public delta(offset: number): OffsetPair {
142 if (offset === 0) {
143 return this;
145 return new OffsetPair(this.offset1 + offset, this.offset2 + offset);
146 }
147 > diffAlgorithm.ts
148 > public equals(other: OffsetPair): boolean {
149 return this.offset1 === other.offset1 && this.offset2 === other.offset2;
150 }
151 > } diffAlgorithm.ts
152 >
153 > export interface ISequence {
154 > getElement(offset: number): number;
155 > get length(): number;
156 >
157 > /**
158 > * The higher the score, the better that offset can be used to split the sequence.
159 > * Is used to optimize insertions.
160 > * Must not be negative.
161 > */
162 > getBoundaryScore?(length: number): number;
163 >
164 > /**
165 > * For line sequences, getElement returns a number representing trimmed lines.
166 > * This however checks equality for the original lines.
167 > * It prevents shifting to less matching lines.
168 > */
169 > isStronglyEqual(offset1: number, offset2: number): boolean;
170 > }
171 >
172 > export interface ITimeout {
173 > isValid(): boolean;
174 > }
175 >
176 > export class InfiniteTimeout implements ITimeout {
177 > public static instance = new InfiniteTimeout();
178 >
179 > isValid(): boolean {
180 return true;
181 }
182 > } diffAlgorithm.ts
183 >
184 > export class DateTimeout implements ITimeout {
185 > private readonly startTime = Date.now();
186 > private valid = true;
187 >
188 > constructor(private timeout: number) {
189 if (timeout <= 0) {
190 throw new BugIndicatingError('timeout must be positive');
191 }
192 }
193 > diffAlgorithm.ts
194 > // Recommendation: Set a log-point `{this.disable()}` in the body
195 > public isValid(): boolean {
196 const valid = Date.now() - this.startTime < this.timeout;
197 if (!valid && this.valid) {
200 return this.valid;
201 }
202 > diffAlgorithm.ts
203 > public disable() {
204 this.timeout = Number.MAX_SAFE_INTEGER;
205 this.isValid = () => true;
206 this.valid = true;
207 }
208 > } diffAlgorithm.ts
src/vs/editor/common/diff/defaultLinesDiffComputer/linesSliceCharSequence.ts 79 introduced LOC · 18 ranges

Open complete file

1 > /*--------------------------------------------------------------------------------------------- linesSliceCharSequence.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 { findLastIdxMonotonous, findLastMonotonous, findFirstMonotonous } from '../../../../base/common/arraysFind.js';
7 > import { CharCode } from '../../../../base/common/charCode.js';
8 > import { OffsetRange } from '../../core/ranges/offsetRange.js';
9 > import { Position } from '../../core/position.js';
10 > import { Range } from '../../core/range.js';
11 > import { ISequence } from './algorithms/diffAlgorithm.js';
12 > import { isSpace } from './utils.js';
13 >
14 > export class LinesSliceCharSequence implements ISequence {
15 > private readonly elements: number[] = [];
16 > private readonly firstElementOffsetByLineIdx: number[] = [];
17 > private readonly lineStartOffsets: number[] = [];
18 > private readonly trimmedWsLengthsByLineIdx: number[] = [];
19 >
20 > constructor(public readonly lines: string[], private readonly range: Range, public readonly considerWhitespaceChanges: boolean) {
21 this.firstElementOffsetByLineIdx.push(0);
22 for (let lineNumber = this.range.startLineNumber; lineNumber <= this.range.endLineNumber; lineNumber++) {
48 }
49 }
50 > linesSliceCharSequence.ts
51 > toString() {
52 return `Slice: "${this.text}"`;
53 }
54 > linesSliceCharSequence.ts
55 > get text(): string {
56 return this.getText(new OffsetRange(0, this.length));
57 }
58 > linesSliceCharSequence.ts
59 > getText(range: OffsetRange): string {
60 return this.elements.slice(range.start, range.endExclusive).map(e => String.fromCharCode(e)).join('');
61 }
62 > linesSliceCharSequence.ts
63 > getElement(offset: number): number {
64 return this.elements[offset];
65 }
66 > linesSliceCharSequence.ts
67 > get length(): number {
68 return this.elements.length;
69 }
70 > linesSliceCharSequence.ts
71 > public getBoundaryScore(length: number): number {
72 // a b c , d e f
73 // 11 0 0 12 15 6 13 0 0 11
98 return score;
99 }
100 > linesSliceCharSequence.ts
101 > public translateOffset(offset: number, preference: 'left' | 'right' = 'right'): Position {
102 // find smallest i, so that lineBreakOffsets[i] <= offset using binary search
103 const i = findLastIdxMonotonous(this.firstElementOffsetByLineIdx, (value) => value <= offset);
108 );
109 }
110 > linesSliceCharSequence.ts
111 > public translateRange(range: OffsetRange): Range {
112 const pos1 = this.translateOffset(range.start, 'right');
113 const pos2 = this.translateOffset(range.endExclusive, 'left');
117 return Range.fromPositions(pos1, pos2);
118 }
119 > linesSliceCharSequence.ts
120 > /**
121 > * Finds the word that contains the character at the given offset
122 > */
123 > public findWordContaining(offset: number): OffsetRange | undefined {
124 if (offset < 0 || offset >= this.elements.length) {
125 return undefined;
144 return new OffsetRange(start, end);
145 }
146 > linesSliceCharSequence.ts
147 > /** fooBar has the two sub-words foo and bar */
148 > public findSubWordContaining(offset: number): OffsetRange | undefined {
149 if (offset < 0 || offset >= this.elements.length) {
150 return undefined;
169 return new OffsetRange(start, end);
170 }
171 > linesSliceCharSequence.ts
172 > public countLinesIn(range: OffsetRange): number {
173 return this.translateOffset(range.endExclusive).lineNumber - this.translateOffset(range.start).lineNumber;
174 }
175 > linesSliceCharSequence.ts
176 > public isStronglyEqual(offset1: number, offset2: number): boolean {
177 return this.elements[offset1] === this.elements[offset2];
178 }
179 > linesSliceCharSequence.ts
180 > public extendToFullLines(range: OffsetRange): OffsetRange {
181 const start = findLastMonotonous(this.firstElementOffsetByLineIdx, x => x <= range.start) ?? 0;
182 const end = findFirstMonotonous(this.firstElementOffsetByLineIdx, x => range.endExclusive <= x) ?? this.elements.length;
183 return new OffsetRange(start, end);
184 }
185 > } linesSliceCharSequence.ts
186 >
187 function isWordChar(charCode: number): boolean {
188 return charCode >= CharCode.a && charCode <= CharCode.z
190 || charCode >= CharCode.Digit0 && charCode <= CharCode.Digit9;
191 }
192 > linesSliceCharSequence.ts
193 function isUpperCase(charCode: number): boolean {
194 return charCode >= CharCode.A && charCode <= CharCode.Z;
195 }
196 > linesSliceCharSequence.ts
197 > const enum CharBoundaryCategory {
198 > WordLower,
199 > WordUpper,
200 > WordNumber,
201 > End,
202 > Other,
203 > Separator,
204 > Space,
205 > LineBreakCR,
206 > LineBreakLF,
207 > }
208 >
209 > const score: Record<CharBoundaryCategory, number> = {
210 > [CharBoundaryCategory.WordLower]: 0,
211 > [CharBoundaryCategory.WordUpper]: 0,
212 > [CharBoundaryCategory.WordNumber]: 0,
213 > [CharBoundaryCategory.End]: 10,
214 > [CharBoundaryCategory.Other]: 2,
215 > [CharBoundaryCategory.Separator]: 30,
216 > [CharBoundaryCategory.Space]: 3,
217 > [CharBoundaryCategory.LineBreakCR]: 10,
218 > [CharBoundaryCategory.LineBreakLF]: 10,
219 > };
220 >
221 function getCategoryBoundaryScore(category: CharBoundaryCategory): number {
222 return score[category];
223 }
224 > linesSliceCharSequence.ts
225 function getCategory(charCode: number): CharBoundaryCategory {
226 if (charCode === CharCode.LineFeed) {
src/vs/editor/common/diff/defaultLinesDiffComputer/algorithms/myersDiffAlgorithm.ts 36 introduced LOC · 9 ranges

Open complete file

1 > /*--------------------------------------------------------------------------------------------- myersDiffAlgorithm.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 { OffsetRange } from '../../../core/ranges/offsetRange.js';
7 > import { DiffAlgorithmResult, IDiffAlgorithm, ISequence, ITimeout, InfiniteTimeout, SequenceDiff } from './diffAlgorithm.js';
8 >
9 > /**
10 > * An O(ND) diff algorithm that has a quadratic space worst-case complexity.
11 > */
12 > export class MyersDiffAlgorithm implements IDiffAlgorithm {
13 > compute(seq1: ISequence, seq2: ISequence, timeout: ITimeout = InfiniteTimeout.instance): DiffAlgorithmResult {
14 // These are common special cases.
15 // The early return improves performance dramatically.
102 return new DiffAlgorithmResult(result, false);
103 }
104 > } myersDiffAlgorithm.ts
105 >
106 > class SnakePath {
107 > constructor(
108 public readonly prev: SnakePath | null,
109 public readonly x: number,
112 ) {
113 }
114 > } myersDiffAlgorithm.ts
115 >
116 > /**
117 > * An array that supports fast negative indices.
118 > */
119 class FastInt32Array {
120 private positiveArr: Int32Array = new Int32Array(10);
121 private negativeArr: Int32Array = new Int32Array(10);
122 > myersDiffAlgorithm.ts
123 > get(idx: number): number {
124 if (idx < 0) {
125 idx = -idx - 1;
129 }
130 }
131 > myersDiffAlgorithm.ts
132 > set(idx: number, value: number): void {
133 if (idx < 0) {
134 idx = -idx - 1;
148 }
149 }
150 > } myersDiffAlgorithm.ts
151 >
152 > /**
153 > * An array that supports fast negative indices.
154 > */
155 class FastArrayNegativeIndices<T> {
156 private readonly positiveArr: T[] = [];
157 private readonly negativeArr: T[] = [];
158 > myersDiffAlgorithm.ts
159 > get(idx: number): T {
160 if (idx < 0) {
161 idx = -idx - 1;
165 }
166 }
167 > myersDiffAlgorithm.ts
168 > set(idx: number, value: T): void {
169 if (idx < 0) {
170 idx = -idx - 1;
src/vs/editor/common/diff/defaultLinesDiffComputer/utils.ts 32 introduced LOC · 8 ranges

Open complete file

1 > /*--------------------------------------------------------------------------------------------- utils.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 { LineRange } from '../../core/ranges/lineRange.js';
8 > import { DetailedLineRangeMapping } from '../rangeMapping.js';
9 >
10 > export class Array2D<T> {
11 > private readonly array: T[] = [];
12 >
13 > constructor(public readonly width: number, public readonly height: number) {
14 this.array = new Array<T>(width * height);
15 }
16 > utils.ts
17 > get(x: number, y: number): T {
18 return this.array[x + y * this.width];
19 }
20 > utils.ts
21 > set(x: number, y: number, value: T): void {
22 this.array[x + y * this.width] = value;
23 }
24 > } utils.ts
25 >
26 > export function isSpace(charCode: number): boolean {
27 return charCode === CharCode.Space || charCode === CharCode.Tab;
28 }
29 > utils.ts
30 > export class LineRangeFragment {
31 > private static chrKeys = new Map<string, number>();
32 >
33 > private static getKey(chr: string): number {
34 let key = this.chrKeys.get(chr);
35 if (key === undefined) {
39 return key;
40 }
41 > utils.ts
42 > private readonly totalCount: number;
43 > private readonly histogram: number[] = [];
44 > constructor(
45 public readonly range: LineRange,
46 public readonly lines: string[],
63 this.totalCount = counter;
64 }
65 > utils.ts
66 > public computeSimilarity(other: LineRangeFragment): number {
67 let sumDifferences = 0;
68 const maxLength = Math.max(this.histogram.length, other.histogram.length);
72 return 1 - (sumDifferences / (this.totalCount + other.totalCount));
73 }
74 > } utils.ts
src/vs/editor/common/diff/defaultLinesDiffComputer/algorithms/dynamicProgrammingDiffing.ts 16 introduced LOC · 2 ranges

Open complete file

1 > /*--------------------------------------------------------------------------------------------- dynamicProgrammingDiffing.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 { OffsetRange } from '../../../core/ranges/offsetRange.js';
7 > import { IDiffAlgorithm, SequenceDiff, ISequence, ITimeout, InfiniteTimeout, DiffAlgorithmResult } from './diffAlgorithm.js';
8 > import { Array2D } from '../utils.js';
9 >
10 > /**
11 > * A O(MN) diffing algorithm that supports a score function.
12 > * The algorithm can be improved by processing the 2d array diagonally.
13 > */
14 > export class DynamicProgrammingDiffing implements IDiffAlgorithm {
15 > compute(sequence1: ISequence, sequence2: ISequence, timeout: ITimeout = InfiniteTimeout.instance, equalityScore?: (offset1: number, offset2: number) => number): DiffAlgorithmResult {
16 if (sequence1.length === 0 || sequence2.length === 0) {
17 return DiffAlgorithmResult.trivial(sequence1, sequence2);

Direct hierarchy

Parents

Children