src/vs/base/common/diff/diff.ts

1315 LOC · 1140 covered · 175 uncovered · 233 ranges · 466 concepts · 90 introducers · 184 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
  >
  /*---------------------------------------------------------------------------------------------
  
diff.ts ×38

  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 { DiffChange } from './diffChange.js';
  
  7
  >
  import { stringHash } from '../hash.js';
  
  8
  >
  import { Constants } from '../uint.js';
  
  9
  >
  
  10
  >
  export class StringDiffSequence implements ISequence {
  
  11
  >
  
  12
  >
  	constructor(private source: string) { }
  
  13
  >
  
  14
  >
  	getElements(): Int32Array | number[] | string[] {
  
  15
  >
  		const source = this.source;
  
diff.ts ×2

  16
  >
  		const characters = new Int32Array(source.length);
  
  17
  >
  		for (let i = 0, len = source.length; i < len; i++) {
  
  18
  >
  			characters[i] = source.charCodeAt(i);
  
  19
  >
  		}
  
  20
  >
  		return characters;
  
  21
  >
  	}
  
  22
  >
  }
  
diff.ts ×38

  23
  >
  
  24
  >
  export function stringDiff(original: string, modified: string, pretty: boolean): IDiffChange[] {
  
  25
  >
  	return new LcsDiff(new StringDiffSequence(original), new StringDiffSequence(modified)).ComputeDiff(pretty).changes;
  
editorWebWorker.ts ×2

  26
  >
  }
  
  27
  >
  
diff.ts ×38

  28
  >
  export interface ISequence {
  
  29
  >
  	getElements(): Int32Array | number[] | string[];
  
  30
  >
  	getStrictElement?(index: number): string;
  
  31
  >
  }
  
  32
  >
  
  33
  >
  export interface IDiffChange {
  
  34
  >
  	/**
  
  35
  >
  	 * The position of the first element in the original sequence which
  
  36
  >
  	 * this change affects.
  
  37
  >
  	 */
  
  38
  >
  	originalStart: number;
  
  39
  >
  
  40
  >
  	/**
  
  41
  >
  	 * The number of elements from the original sequence which were
  
  42
  >
  	 * affected.
  
  43
  >
  	 */
  
  44
  >
  	originalLength: number;
  
  45
  >
  
  46
  >
  	/**
  
  47
  >
  	 * The position of the first element in the modified sequence which
  
  48
  >
  	 * this change affects.
  
  49
  >
  	 */
  
  50
  >
  	modifiedStart: number;
  
  51
  >
  
  52
  >
  	/**
  
  53
  >
  	 * The number of elements from the modified sequence which were
  
  54
  >
  	 * affected (added).
  
  55
  >
  	 */
  
  56
  >
  	modifiedLength: number;
  
  57
  >
  }
  
  58
  >
  
  59
  >
  export interface IContinueProcessingPredicate {
  
  60
  >
  	(furthestOriginalIndex: number, matchLengthOfLongest: number): boolean;
  
  61
  >
  }
  
  62
  >
  
  63
  >
  export interface IDiffResult {
  
  64
  >
  	quitEarly: boolean;
  
  65
  >
  	changes: IDiffChange[];
  
  66
  >
  }
  
  67
  >
  
  68
  >
  //
  
  69
  >
  // The code below has been ported from a C# implementation in VS
  
  70
  >
  //
  
  71
  >
  
  72
  >
  class Debug {
  
  73
  >
  
  74
  >
  	public static Assert(condition: boolean, message: string): void {
  
  75
  >
  		if (!condition) {
  
diff.ts ×13

  76
  
  			throw new Error(message);
  
  77
  
  		}
  
  78
  >
  	}
  
diff.ts ×13

  79
  >
  }
  
diff.ts ×38

  80
  >
  
  81
  >
  class MyArray {
  
  82
  >
  	/**
  
  83
  >
  	 * Copies a range of elements from an Array starting at the specified source index and pastes
  
  84
  >
  	 * them to another Array starting at the specified destination index. The length and the indexes
  
  85
  >
  	 * are specified as 64-bit integers.
  
  86
  >
  	 * sourceArray:
  
  87
  >
  	 *		The Array that contains the data to copy.
  
  88
  >
  	 * sourceIndex:
  
  89
  >
  	 *		A 64-bit integer that represents the index in the sourceArray at which copying begins.
  
  90
  >
  	 * destinationArray:
  
  91
  >
  	 *		The Array that receives the data.
  
  92
  >
  	 * destinationIndex:
  
  93
  >
  	 *		A 64-bit integer that represents the index in the destinationArray at which storing begins.
  
  94
  >
  	 * length:
  
  95
  >
  	 *		A 64-bit integer that represents the number of elements to copy.
  
  96
  >
  	 */
  
  97
  >
  	public static Copy(sourceArray: unknown[], sourceIndex: number, destinationArray: unknown[], destinationIndex: number, length: number) {
  
  98
  >
  		for (let i = 0; i < length; i++) {
  
diff.ts ×23

  99
  >
  			destinationArray[destinationIndex + i] = sourceArray[sourceIndex + i];
  
diff.ts ×2

  100
  >
  		}
  
  101
  >
  	}
  
diff.ts ×23

  102
  >
  	public static Copy2(sourceArray: Int32Array, sourceIndex: number, destinationArray: Int32Array, destinationIndex: number, length: number) {
  
diff.ts ×38

  103
  >
  		for (let i = 0; i < length; i++) {
  
diff.ts ×2

  104
  >
  			destinationArray[destinationIndex + i] = sourceArray[sourceIndex + i];
  
  105
  >
  		}
  
  106
  >
  	}
  
  107
  >
  }
  
diff.ts ×38

  108
  >
  
  109
  >
  //*****************************************************************************
  
  110
  >
  // LcsDiff.cs
  
  111
  >
  //
  
  112
  >
  // An implementation of the difference algorithm described in
  
  113
  >
  // "An O(ND) Difference Algorithm and its variations" by Eugene W. Myers
  
  114
  >
  //
  
  115
  >
  // Copyright (C) 2008 Microsoft Corporation @minifier_do_not_preserve
  
  116
  >
  //*****************************************************************************
  
  117
  >
  
  118
  >
  // Our total memory usage for storing history is (worst-case):
  
  119
  >
  // 2 * [(MaxDifferencesHistory + 1) * (MaxDifferencesHistory + 1) - 1] * sizeof(int)
  
  120
  >
  // 2 * [1448*1448 - 1] * 4 = 16773624 = 16MB
  
  121
  >
  const enum LocalConstants {
  
  122
  >
  	MaxDifferencesHistory = 1447
  
  123
  >
  }
  
  124
  >
  
  125
  >
  /**
  
  126
  >
   * A utility class which helps to create the set of DiffChanges from
  
  127
  >
   * a difference operation. This class accepts original DiffElements and
  
  128
  >
   * modified DiffElements that are involved in a particular change. The
  
  129
  >
   * MarkNextChange() method can be called to mark the separation between
  
  130
  >
   * distinct changes. At the end, the Changes property can be called to retrieve
  
  131
  >
   * the constructed changes.
  
  132
  >
   */
  
  133
  >
  class DiffChangeHelper {
  
  134
  >
  
  135
  >
  	private m_changes: DiffChange[];
  
  136
  >
  	private m_originalStart: number;
  
  137
  >
  	private m_modifiedStart: number;
  
  138
  >
  	private m_originalCount: number;
  
  139
  >
  	private m_modifiedCount: number;
  
  140
  >
  
  141
  >
  	/**
  
  142
  >
  	 * Constructs a new DiffChangeHelper for the given DiffSequences.
  
  143
  >
  	 */
  
  144
  >
  	constructor() {
  
  145
  >
  		this.m_changes = [];
  
diff.ts ×10

  146
  >
  		this.m_originalStart = Constants.MAX_SAFE_SMALL_INTEGER;
  
  147
  >
  		this.m_modifiedStart = Constants.MAX_SAFE_SMALL_INTEGER;
  
  148
  >
  		this.m_originalCount = 0;
  
  149
  >
  		this.m_modifiedCount = 0;
  
  150
  >
  	}
  
  151
  >
  
diff.ts ×38

  152
  >
  	/**
  
  153
  >
  	 * Marks the beginning of the next change in the set of differences.
  
  154
  >
  	 */
  
  155
  >
  	public MarkNextChange(): void {
  
  156
  >
  		// Only add to the list if there is something to add
  
diff.ts ×10

  157
  >
  		if (this.m_originalCount > 0 || this.m_modifiedCount > 0) {
  
  158
  >
  			// Add the new change to our list
  
  159
  >
  			this.m_changes.push(new DiffChange(this.m_originalStart, this.m_originalCount,
  
  160
  >
  				this.m_modifiedStart, this.m_modifiedCount));
  
  161
  >
  		}
  
  162
  >
  
  163
  >
  		// Reset for the next change
  
  164
  >
  		this.m_originalCount = 0;
  
  165
  >
  		this.m_modifiedCount = 0;
  
  166
  >
  		this.m_originalStart = Constants.MAX_SAFE_SMALL_INTEGER;
  
  167
  >
  		this.m_modifiedStart = Constants.MAX_SAFE_SMALL_INTEGER;
  
  168
  >
  	}
  
  169
  >
  
diff.ts ×38

  170
  >
  	/**
  
  171
  >
  	 * Adds the original element at the given position to the elements
  
  172
  >
  	 * affected by the current change. The modified index gives context
  
  173
  >
  	 * to the change position with respect to the original sequence.
  
  174
  >
  	 * @param originalIndex The index of the original element to add.
  
  175
  >
  	 * @param modifiedIndex The index of the modified element that provides corresponding position in the modified sequence.
  
  176
  >
  	 */
  
  177
  >
  	public AddOriginalElement(originalIndex: number, modifiedIndex: number) {
  
  178
  >
  		// The 'true' start index is the smallest of the ones we've seen
  
diff.ts ×1

  179
  >
  		this.m_originalStart = Math.min(this.m_originalStart, originalIndex);
  
  180
  >
  		this.m_modifiedStart = Math.min(this.m_modifiedStart, modifiedIndex);
  
  181
  >
  
  182
  >
  		this.m_originalCount++;
  
  183
  >
  	}
  
  184
  >
  
diff.ts ×38

  185
  >
  	/**
  
  186
  >
  	 * Adds the modified element at the given position to the elements
  
  187
  >
  	 * affected by the current change. The original index gives context
  
  188
  >
  	 * to the change position with respect to the modified sequence.
  
  189
  >
  	 * @param originalIndex The index of the original element that provides corresponding position in the original sequence.
  
  190
  >
  	 * @param modifiedIndex The index of the modified element to add.
  
  191
  >
  	 */
  
  192
  >
  	public AddModifiedElement(originalIndex: number, modifiedIndex: number): void {
  
  193
  >
  		// The 'true' start index is the smallest of the ones we've seen
  
diff.ts ×3

  194
  >
  		this.m_originalStart = Math.min(this.m_originalStart, originalIndex);
  
  195
  >
  		this.m_modifiedStart = Math.min(this.m_modifiedStart, modifiedIndex);
  
  196
  >
  
  197
  >
  		this.m_modifiedCount++;
  
  198
  >
  	}
  
  199
  >
  
diff.ts ×38

  200
  >
  	/**
  
  201
  >
  	 * Retrieves all of the changes marked by the class.
  
  202
  >
  	 */
  
  203
  >
  	public getChanges(): DiffChange[] {
  
  204
  >
  		if (this.m_originalCount > 0 || this.m_modifiedCount > 0) {
  
diff.ts ×5

  205
  >
  			// Finish up on whatever is left
  
  206
  >
  			this.MarkNextChange();
  
  207
  >
  		}
  
  208
  >
  
  209
  >
  		return this.m_changes;
  
  210
  >
  	}
  
  211
  >
  
diff.ts ×38

  212
  >
  	/**
  
  213
  >
  	 * Retrieves all of the changes marked by the class in the reverse order
  
  214
  >
  	 */
  
  215
  >
  	public getReverseChanges(): DiffChange[] {
  
  216
  >
  		if (this.m_originalCount > 0 || this.m_modifiedCount > 0) {
  
diff.ts ×10

  217
  >
  			// Finish up on whatever is left
  
  218
  >
  			this.MarkNextChange();
  
  219
  >
  		}
  
  220
  >
  
  221
  >
  		this.m_changes.reverse();
  
  222
  >
  		return this.m_changes;
  
  223
  >
  	}
  
  224
  >
  
diff.ts ×38

  225
  >
  }
  
  226
  >
  
  227
  >
  /**
  
  228
  >
   * An implementation of the difference algorithm described in
  
  229
  >
   * "An O(ND) Difference Algorithm and its variations" by Eugene W. Myers
  
  230
  >
   */
  
  231
  >
  export class LcsDiff {
  
  232
  >
  
  233
  >
  	private readonly ContinueProcessingPredicate: IContinueProcessingPredicate | null;
  
  234
  >
  
  235
  >
  	private readonly _originalSequence: ISequence;
  
  236
  >
  	private readonly _modifiedSequence: ISequence;
  
  237
  >
  	private readonly _hasStrings: boolean;
  
  238
  >
  	private readonly _originalStringElements: string[];
  
  239
  >
  	private readonly _originalElementsOrHash: Int32Array;
  
  240
  >
  	private readonly _modifiedStringElements: string[];
  
  241
  >
  	private readonly _modifiedElementsOrHash: Int32Array;
  
  242
  >
  
  243
  >
  	private m_forwardHistory: Int32Array[];
  
  244
  >
  	private m_reverseHistory: Int32Array[];
  
  245
  >
  
  246
  >
  	/**
  
  247
  >
  	 * Constructs the DiffFinder
  
  248
  >
  	 */
  
  249
  >
  	constructor(originalSequence: ISequence, modifiedSequence: ISequence, continueProcessingPredicate: IContinueProcessingPredicate | null = null) {
  
  250
  >
  		this.ContinueProcessingPredicate = continueProcessingPredicate;
  
diff.ts ×13

  251
  >
  
  252
  >
  		this._originalSequence = originalSequence;
  
  253
  >
  		this._modifiedSequence = modifiedSequence;
  
  254
  >
  
  255
  >
  		const [originalStringElements, originalElementsOrHash, originalHasStrings] = LcsDiff._getElements(originalSequence);
  
  256
  >
  		const [modifiedStringElements, modifiedElementsOrHash, modifiedHasStrings] = LcsDiff._getElements(modifiedSequence);
  
  257
  >
  
  258
  >
  		this._hasStrings = (originalHasStrings && modifiedHasStrings);
  
  259
  >
  		this._originalStringElements = originalStringElements;
  
  260
  >
  		this._originalElementsOrHash = originalElementsOrHash;
  
  261
  >
  		this._modifiedStringElements = modifiedStringElements;
  
  262
  >
  		this._modifiedElementsOrHash = modifiedElementsOrHash;
  
  263
  >
  
  264
  >
  		this.m_forwardHistory = [];
  
  265
  >
  		this.m_reverseHistory = [];
  
  266
  >
  	}
  
  267
  >
  
diff.ts ×38

  268
  >
  	private static _isStringArray(arr: Int32Array | number[] | string[]): arr is string[] {
  
  269
  >
  		return (arr.length > 0 && typeof arr[0] === 'string');
  
diff.ts ×13

  270
  >
  	}
  
  271
  >
  
diff.ts ×38

  272
  >
  	private static _getElements(sequence: ISequence): [string[], Int32Array, boolean] {
  
  273
  >
  		const elements = sequence.getElements();
  
diff.ts ×13

  274
  >
  
  275
  >
  		if (LcsDiff._isStringArray(elements)) {
  
  276
  >
  			const hashes = new Int32Array(elements.length);
  
diff.ts ×3

  277
  >
  			for (let i = 0, len = elements.length; i < len; i++) {
  
  278
  >
  				hashes[i] = stringHash(elements[i], 0);
  
  279
  >
  			}
  
  280
  >
  			return [elements, hashes, true];
  
  281
  >
  		}
  
  282
  >
  
diff.ts ×1

  283
  >
  		if (elements instanceof Int32Array) {
  
  284
  >
  			return [[], elements, false];
  
diff.ts ×2

  285
  >
  		}
  
  286
  >
  
legacyLinesDiffComputer.ts ×15

  287
  >
  		return [[], new Int32Array(elements), false];
  
  288
  >
  	}
  
diff.ts ×13

  289
  >
  
diff.ts ×38

  290
  >
  	private ElementsAreEqual(originalIndex: number, newIndex: number): boolean {
  
  291
  >
  		if (this._originalElementsOrHash[originalIndex] !== this._modifiedElementsOrHash[newIndex]) {
  
diff.ts ×2

  292
  >
  			return false;
  
diff.ts ×1

  293
  >
  		}
  
  294
  >
  		return (this._hasStrings ? this._originalStringElements[originalIndex] === this._modifiedStringElements[newIndex] : true);
  
diff.ts ×2

  295
  >
  	}
  
  296
  >
  
diff.ts ×38

  297
  >
  	private ElementsAreStrictEqual(originalIndex: number, newIndex: number): boolean {
  
  298
  >
  		if (!this.ElementsAreEqual(originalIndex, newIndex)) {
  
diff.ts ×5

  299
  
  			return false;
  
  300
  
  		}
  
  301
  >
  		const originalElement = LcsDiff._getStrictElement(this._originalSequence, originalIndex);
  
diff.ts ×5

  302
  >
  		const modifiedElement = LcsDiff._getStrictElement(this._modifiedSequence, newIndex);
  
  303
  >
  		return (originalElement === modifiedElement);
  
  304
  >
  	}
  
  305
  >
  
diff.ts ×38

  306
  >
  	private static _getStrictElement(sequence: ISequence, index: number): string | null {
  
  307
  >
  		if (typeof sequence.getStrictElement === 'function') {
  
diff.ts ×5

  308
  >
  			return sequence.getStrictElement(index);
  
diff.ts ×1

  309
  >
  		}
  
  310
  >
  		return null;
  
diff.ts ×1

  311
  >
  	}
  
diff.ts ×5

  312
  >
  
diff.ts ×38

  313
  >
  	private OriginalElementsAreEqual(index1: number, index2: number): boolean {
  
  314
  >
  		if (this._originalElementsOrHash[index1] !== this._originalElementsOrHash[index2]) {
  
diff.ts ×1

  315
  >
  			return false;
  
  316
  >
  		}
  
  317
  >
  		return (this._hasStrings ? this._originalStringElements[index1] === this._originalStringElements[index2] : true);
  
  318
  >
  	}
  
  319
  >
  
diff.ts ×38

  320
  >
  	private ModifiedElementsAreEqual(index1: number, index2: number): boolean {
  
  321
  >
  		if (this._modifiedElementsOrHash[index1] !== this._modifiedElementsOrHash[index2]) {
  
diff.ts ×1

  322
  >
  			return false;
  
  323
  >
  		}
  
  324
  >
  		return (this._hasStrings ? this._modifiedStringElements[index1] === this._modifiedStringElements[index2] : true);
  
  325
  >
  	}
  
  326
  >
  
diff.ts ×38

  327
  >
  	public ComputeDiff(pretty: boolean): IDiffResult {
  
  328
  >
  		return this._ComputeDiff(0, this._originalElementsOrHash.length - 1, 0, this._modifiedElementsOrHash.length - 1, pretty);
  
diff.ts ×13

  329
  >
  	}
  
  330
  >
  
diff.ts ×38

  331
  >
  	/**
  
  332
  >
  	 * Computes the differences between the original and modified input
  
  333
  >
  	 * sequences on the bounded range.
  
  334
  >
  	 * @returns An array of the differences between the two input sequences.
  
  335
  >
  	 */
  
  336
  >
  	private _ComputeDiff(originalStart: number, originalEnd: number, modifiedStart: number, modifiedEnd: number, pretty: boolean): IDiffResult {
  
  337
  >
  		const quitEarlyArr = [false];
  
diff.ts ×13

  338
  >
  		let changes = this.ComputeDiffRecursive(originalStart, originalEnd, modifiedStart, modifiedEnd, quitEarlyArr);
  
  339
  >
  
  340
  >
  		if (pretty) {
  
  341
  >
  			// We have to clean up the computed diff to be more intuitive
  
diff.ts ×5

  342
  >
  			// but it turns out this cannot be done correctly until the entire set
  
  343
  >
  			// of diffs have been computed
  
  344
  >
  			changes = this.PrettifyChanges(changes);
  
  345
  >
  		}
  
  346
  >
  
diff.ts ×13

  347
  >
  		return {
  
  348
  >
  			quitEarly: quitEarlyArr[0],
  
  349
  >
  			changes: changes
  
  350
  >
  		};
  
  351
  >
  	}
  
  352
  >
  
diff.ts ×38

  353
  >
  	/**
  
  354
  >
  	 * Private helper method which computes the differences on the bounded range
  
  355
  >
  	 * recursively.
  
  356
  >
  	 * @returns An array of the differences between the two input sequences.
  
  357
  >
  	 */
  
  358
  >
  	private ComputeDiffRecursive(originalStart: number, originalEnd: number, modifiedStart: number, modifiedEnd: number, quitEarlyArr: boolean[]): DiffChange[] {
  
  359
  >
  		quitEarlyArr[0] = false;
  
diff.ts ×13

  360
  >
  
  361
  >
  		// Find the start of the differences
  
  362
  >
  		while (originalStart <= originalEnd && modifiedStart <= modifiedEnd && this.ElementsAreEqual(originalStart, modifiedStart)) {
  
  363
  >
  			originalStart++;
  
diff.ts ×1

  364
  >
  			modifiedStart++;
  
  365
  >
  		}
  
  366
  >
  
diff.ts ×13

  367
  >
  		// Find the end of the differences
  
  368
  >
  		while (originalEnd >= originalStart && modifiedEnd >= modifiedStart && this.ElementsAreEqual(originalEnd, modifiedEnd)) {
  
  369
  >
  			originalEnd--;
  
diff.ts ×1

  370
  >
  			modifiedEnd--;
  
  371
  >
  		}
  
  372
  >
  
diff.ts ×13

  373
  >
  		// In the special case where we either have all insertions or all deletions or the sequences are identical
  
  374
  >
  		if (originalStart > originalEnd || modifiedStart > modifiedEnd) {
  
  375
  >
  			let changes: DiffChange[];
  
diff.ts ×3

  376
  >
  
  377
  >
  			if (modifiedStart <= modifiedEnd) {
  
  378
  >
  				Debug.Assert(originalStart === originalEnd + 1, 'originalStart should only be one more than originalEnd');
  
diff.ts ×1

  379
  >
  
  380
  >
  				// All insertions
  
  381
  >
  				changes = [
  
  382
  >
  					new DiffChange(originalStart, 0, modifiedStart, modifiedEnd - modifiedStart + 1)
  
  383
  >
  				];
  
  384
  >
  			} else if (originalStart <= originalEnd) {
  
diff.ts ×3

  385
  >
  				Debug.Assert(modifiedStart === modifiedEnd + 1, 'modifiedStart should only be one more than modifiedEnd');
  
diff.ts ×1

  386
  >
  
  387
  >
  				// All deletions
  
  388
  >
  				changes = [
  
  389
  >
  					new DiffChange(originalStart, originalEnd - originalStart + 1, modifiedStart, 0)
  
  390
  >
  				];
  
  391
  >
  			} else {
  
diff.ts ×1

  392
  >
  				Debug.Assert(originalStart === originalEnd + 1, 'originalStart should only be one more than originalEnd');
  
diff.ts ×1

  393
  >
  				Debug.Assert(modifiedStart === modifiedEnd + 1, 'modifiedStart should only be one more than modifiedEnd');
  
  394
  >
  
  395
  >
  				// Identical sequences - No differences
  
  396
  >
  				changes = [];
  
  397
  >
  			}
  
  398
  >
  
diff.ts ×3

  399
  >
  			return changes;
  
  400
  >
  		}
  
  401
  >
  
diff.ts ×23

  402
  >
  		// This problem can be solved using the Divide-And-Conquer technique.
  
  403
  >
  		const midOriginalArr = [0];
  
  404
  >
  		const midModifiedArr = [0];
  
  405
  >
  		const result = this.ComputeRecursionPoint(originalStart, originalEnd, modifiedStart, modifiedEnd, midOriginalArr, midModifiedArr, quitEarlyArr);
  
  406
  >
  
  407
  >
  		const midOriginal = midOriginalArr[0];
  
  408
  >
  		const midModified = midModifiedArr[0];
  
  409
  >
  
  410
  >
  		if (result !== null) {
  
  411
  >
  			// Result is not-null when there was enough memory to compute the changes while
  
diff.ts ×10

  412
  >
  			// searching for the recursion point
  
  413
  >
  			return result;
  
  414
  >
  		} else if (!quitEarlyArr[0]) {
  
diff.ts ×23

  415
  >
  			// We can break the problem down recursively by finding the changes in the
  
diff.ts ×2

  416
  >
  			// First Half:   (originalStart, modifiedStart) to (midOriginal, midModified)
  
  417
  >
  			// Second Half:  (midOriginal + 1, minModified + 1) to (originalEnd, modifiedEnd)
  
  418
  >
  			// NOTE: ComputeDiff() is inclusive, therefore the second range starts on the next point
  
  419
  >
  
  420
  >
  			const leftChanges = this.ComputeDiffRecursive(originalStart, midOriginal, modifiedStart, midModified, quitEarlyArr);
  
  421
  >
  			let rightChanges: DiffChange[] = [];
  
  422
  >
  
  423
  >
  			if (!quitEarlyArr[0]) {
  
  424
  >
  				rightChanges = this.ComputeDiffRecursive(midOriginal + 1, originalEnd, midModified + 1, modifiedEnd, quitEarlyArr);
  
  425
  >
  			} else {
  
  426
  
  				// We didn't have time to finish the first half, so we don't have time to compute this half.
  
  427
  
  				// Consider the entire rest of the sequence different.
  
  428
  
  				rightChanges = [
  
  429
  
  					new DiffChange(midOriginal + 1, originalEnd - (midOriginal + 1) + 1, midModified + 1, modifiedEnd - (midModified + 1) + 1)
  
  430
  
  				];
  
  431
  
  			}
  
  432
  >
  
diff.ts ×2

  433
  >
  			return this.ConcatenateChanges(leftChanges, rightChanges);
  
  434
  >
  		}
  
  435
  
  436
  
  		// If we hit here, we quit early, and so can't return anything meaningful
  
  437
  
  		return [
  
  438
  
  			new DiffChange(originalStart, originalEnd - originalStart + 1, modifiedStart, modifiedEnd - modifiedStart + 1)
  
  439
  
  		];
  
  440
  >
  	}
  
diff.ts ×13

  441
  >
  
diff.ts ×38

  442
  >
  	private WALKTRACE(diagonalForwardBase: number, diagonalForwardStart: number, diagonalForwardEnd: number, diagonalForwardOffset: number,
  
  443
  >
  		diagonalReverseBase: number, diagonalReverseStart: number, diagonalReverseEnd: number, diagonalReverseOffset: number,
  
diff.ts ×10

  444
  >
  		forwardPoints: Int32Array, reversePoints: Int32Array,
  
  445
  >
  		originalIndex: number, originalEnd: number, midOriginalArr: number[],
  
  446
  >
  		modifiedIndex: number, modifiedEnd: number, midModifiedArr: number[],
  
  447
  >
  		deltaIsEven: boolean, quitEarlyArr: boolean[]
  
  448
  >
  	): DiffChange[] {
  
  449
  >
  		let forwardChanges: DiffChange[] | null = null;
  
  450
  >
  		let reverseChanges: DiffChange[] | null = null;
  
  451
  >
  
  452
  >
  		// First, walk backward through the forward diagonals history
  
  453
  >
  		let changeHelper = new DiffChangeHelper();
  
  454
  >
  		let diagonalMin = diagonalForwardStart;
  
  455
  >
  		let diagonalMax = diagonalForwardEnd;
  
  456
  >
  		let diagonalRelative = (midOriginalArr[0] - midModifiedArr[0]) - diagonalForwardOffset;
  
  457
  >
  		let lastOriginalIndex = Constants.MIN_SAFE_SMALL_INTEGER;
  
  458
  >
  		let historyIndex = this.m_forwardHistory.length - 1;
  
  459
  >
  
  460
  >
  		do {
  
  461
  >
  			// Get the diagonal index from the relative diagonal number
  
  462
  >
  			const diagonal = diagonalRelative + diagonalForwardBase;
  
  463
  >
  
  464
  >
  			// Figure out where we came from
  
  465
  >
  			if (diagonal === diagonalMin || (diagonal < diagonalMax && forwardPoints[diagonal - 1] < forwardPoints[diagonal + 1])) {
  
  466
  >
  				// Vertical line (the element is an insert)
  
diff.ts ×3

  467
  >
  				originalIndex = forwardPoints[diagonal + 1];
  
  468
  >
  				modifiedIndex = originalIndex - diagonalRelative - diagonalForwardOffset;
  
  469
  >
  				if (originalIndex < lastOriginalIndex) {
  
  470
  >
  					changeHelper.MarkNextChange();
  
diff.ts ×1

  471
  >
  				}
  
  472
  >
  				lastOriginalIndex = originalIndex;
  
diff.ts ×3

  473
  >
  				changeHelper.AddModifiedElement(originalIndex + 1, modifiedIndex);
  
  474
  >
  				diagonalRelative = (diagonal + 1) - diagonalForwardBase; //Setup for the next iteration
  
  475
  >
  			} else {
  
diff.ts ×10

  476
  >
  				// Horizontal line (the element is a deletion)
  
diff.ts ×2

  477
  >
  				originalIndex = forwardPoints[diagonal - 1] + 1;
  
  478
  >
  				modifiedIndex = originalIndex - diagonalRelative - diagonalForwardOffset;
  
  479
  >
  				if (originalIndex < lastOriginalIndex) {
  
  480
  >
  					changeHelper.MarkNextChange();
  
diff.ts ×1

  481
  >
  				}
  
  482
  >
  				lastOriginalIndex = originalIndex - 1;
  
diff.ts ×2

  483
  >
  				changeHelper.AddOriginalElement(originalIndex, modifiedIndex + 1);
  
  484
  >
  				diagonalRelative = (diagonal - 1) - diagonalForwardBase; //Setup for the next iteration
  
  485
  >
  			}
  
  486
  >
  
diff.ts ×10

  487
  >
  			if (historyIndex >= 0) {
  
  488
  >
  				forwardPoints = this.m_forwardHistory[historyIndex];
  
diff.ts ×1

  489
  >
  				diagonalForwardBase = forwardPoints[0]; //We stored this in the first spot
  
  490
  >
  				diagonalMin = 1;
  
  491
  >
  				diagonalMax = forwardPoints.length - 1;
  
  492
  >
  			}
  
  493
  >
  		} while (--historyIndex >= -1);
  
diff.ts ×10

  494
  >
  
  495
  >
  		// Ironically, we get the forward changes as the reverse of the
  
  496
  >
  		// order we added them since we technically added them backwards
  
  497
  >
  		forwardChanges = changeHelper.getReverseChanges();
  
  498
  >
  
  499
  >
  		if (quitEarlyArr[0]) {
  
  500
  >
  			// TODO: Calculate a partial from the reverse diagonals.
  
diff.ts ×2

  501
  >
  			//       For now, just assume everything after the midOriginal/midModified point is a diff
  
  502
  >
  
  503
  >
  			let originalStartPoint = midOriginalArr[0] + 1;
  
  504
  >
  			let modifiedStartPoint = midModifiedArr[0] + 1;
  
  505
  >
  
  506
  >
  			if (forwardChanges !== null && forwardChanges.length > 0) {
  
  507
  >
  				const lastForwardChange = forwardChanges[forwardChanges.length - 1];
  
  508
  >
  				originalStartPoint = Math.max(originalStartPoint, lastForwardChange.getOriginalEnd());
  
  509
  >
  				modifiedStartPoint = Math.max(modifiedStartPoint, lastForwardChange.getModifiedEnd());
  
  510
  >
  			}
  
  511
  >
  
  512
  >
  			reverseChanges = [
  
  513
  >
  				new DiffChange(originalStartPoint, originalEnd - originalStartPoint + 1,
  
  514
  >
  					modifiedStartPoint, modifiedEnd - modifiedStartPoint + 1)
  
  515
  >
  			];
  
  516
  >
  		} else {
  
diff.ts ×10

  517
  >
  			// Now walk backward through the reverse diagonals history
  
diff.ts ×5

  518
  >
  			changeHelper = new DiffChangeHelper();
  
  519
  >
  			diagonalMin = diagonalReverseStart;
  
  520
  >
  			diagonalMax = diagonalReverseEnd;
  
  521
  >
  			diagonalRelative = (midOriginalArr[0] - midModifiedArr[0]) - diagonalReverseOffset;
  
  522
  >
  			lastOriginalIndex = Constants.MAX_SAFE_SMALL_INTEGER;
  
  523
  >
  			historyIndex = (deltaIsEven) ? this.m_reverseHistory.length - 1 : this.m_reverseHistory.length - 2;
  
  524
  >
  
  525
  >
  			do {
  
  526
  >
  				// Get the diagonal index from the relative diagonal number
  
  527
  >
  				const diagonal = diagonalRelative + diagonalReverseBase;
  
  528
  >
  
  529
  >
  				// Figure out where we came from
  
  530
  >
  				if (diagonal === diagonalMin || (diagonal < diagonalMax && reversePoints[diagonal - 1] >= reversePoints[diagonal + 1])) {
  
  531
  >
  					// Horizontal line (the element is a deletion))
  
diff.ts ×2

  532
  >
  					originalIndex = reversePoints[diagonal + 1] - 1;
  
  533
  >
  					modifiedIndex = originalIndex - diagonalRelative - diagonalReverseOffset;
  
  534
  >
  					if (originalIndex > lastOriginalIndex) {
  
  535
  >
  						changeHelper.MarkNextChange();
  
diff.ts ×1

  536
  >
  					}
  
  537
  >
  					lastOriginalIndex = originalIndex + 1;
  
diff.ts ×2

  538
  >
  					changeHelper.AddOriginalElement(originalIndex + 1, modifiedIndex + 1);
  
  539
  >
  					diagonalRelative = (diagonal + 1) - diagonalReverseBase; //Setup for the next iteration
  
  540
  >
  				} else {
  
diff.ts ×5

  541
  >
  					// Vertical line (the element is an insertion)
  
diff.ts ×2

  542
  >
  					originalIndex = reversePoints[diagonal - 1];
  
  543
  >
  					modifiedIndex = originalIndex - diagonalRelative - diagonalReverseOffset;
  
  544
  >
  					if (originalIndex > lastOriginalIndex) {
  
  545
  >
  						changeHelper.MarkNextChange();
  
diff.ts ×1

  546
  >
  					}
  
  547
  >
  					lastOriginalIndex = originalIndex;
  
diff.ts ×2

  548
  >
  					changeHelper.AddModifiedElement(originalIndex + 1, modifiedIndex + 1);
  
  549
  >
  					diagonalRelative = (diagonal - 1) - diagonalReverseBase; //Setup for the next iteration
  
  550
  >
  				}
  
  551
  >
  
diff.ts ×5

  552
  >
  				if (historyIndex >= 0) {
  
  553
  >
  					reversePoints = this.m_reverseHistory[historyIndex];
  
diff.ts ×1

  554
  >
  					diagonalReverseBase = reversePoints[0]; //We stored this in the first spot
  
  555
  >
  					diagonalMin = 1;
  
  556
  >
  					diagonalMax = reversePoints.length - 1;
  
  557
  >
  				}
  
  558
  >
  			} while (--historyIndex >= -1);
  
diff.ts ×5

  559
  >
  
  560
  >
  			// There are cases where the reverse history will find diffs that
  
  561
  >
  			// are correct, but not intuitive, so we need shift them.
  
  562
  >
  			reverseChanges = changeHelper.getChanges();
  
  563
  >
  		}
  
  564
  >
  
diff.ts ×10

  565
  >
  		return this.ConcatenateChanges(forwardChanges, reverseChanges);
  
  566
  >
  	}
  
  567
  >
  
diff.ts ×38

  568
  >
  	/**
  
  569
  >
  	 * Given the range to compute the diff on, this method finds the point:
  
  570
  >
  	 * (midOriginal, midModified)
  
  571
  >
  	 * that exists in the middle of the LCS of the two sequences and
  
  572
  >
  	 * is the point at which the LCS problem may be broken down recursively.
  
  573
  >
  	 * This method will try to keep the LCS trace in memory. If the LCS recursion
  
  574
  >
  	 * point is calculated and the full trace is available in memory, then this method
  
  575
  >
  	 * will return the change list.
  
  576
  >
  	 * @param originalStart The start bound of the original sequence range
  
  577
  >
  	 * @param originalEnd The end bound of the original sequence range
  
  578
  >
  	 * @param modifiedStart The start bound of the modified sequence range
  
  579
  >
  	 * @param modifiedEnd The end bound of the modified sequence range
  
  580
  >
  	 * @param midOriginal The middle point of the original sequence range
  
  581
  >
  	 * @param midModified The middle point of the modified sequence range
  
  582
  >
  	 * @returns The diff changes, if available, otherwise null
  
  583
  >
  	 */
  
  584
  >
  	private ComputeRecursionPoint(originalStart: number, originalEnd: number, modifiedStart: number, modifiedEnd: number, midOriginalArr: number[], midModifiedArr: number[], quitEarlyArr: boolean[]) {
  
  585
  >
  		let originalIndex = 0, modifiedIndex = 0;
  
diff.ts ×23

  586
  >
  		let diagonalForwardStart = 0, diagonalForwardEnd = 0;
  
  587
  >
  		let diagonalReverseStart = 0, diagonalReverseEnd = 0;
  
  588
  >
  
  589
  >
  		// To traverse the edit graph and produce the proper LCS, our actual
  
  590
  >
  		// start position is just outside the given boundary
  
  591
  >
  		originalStart--;
  
  592
  >
  		modifiedStart--;
  
  593
  >
  
  594
  >
  		// We set these up to make the compiler happy, but they will
  
  595
  >
  		// be replaced before we return with the actual recursion point
  
  596
  >
  		midOriginalArr[0] = 0;
  
  597
  >
  		midModifiedArr[0] = 0;
  
  598
  >
  
  599
  >
  		// Clear out the history
  
  600
  >
  		this.m_forwardHistory = [];
  
  601
  >
  		this.m_reverseHistory = [];
  
  602
  >
  
  603
  >
  		// Each cell in the two arrays corresponds to a diagonal in the edit graph.
  
  604
  >
  		// The integer value in the cell represents the originalIndex of the furthest
  
  605
  >
  		// reaching point found so far that ends in that diagonal.
  
  606
  >
  		// The modifiedIndex can be computed mathematically from the originalIndex and the diagonal number.
  
  607
  >
  		const maxDifferences = (originalEnd - originalStart) + (modifiedEnd - modifiedStart);
  
  608
  >
  		const numDiagonals = maxDifferences + 1;
  
  609
  >
  		const forwardPoints = new Int32Array(numDiagonals);
  
  610
  >
  		const reversePoints = new Int32Array(numDiagonals);
  
  611
  >
  		// diagonalForwardBase: Index into forwardPoints of the diagonal which passes through (originalStart, modifiedStart)
  
  612
  >
  		// diagonalReverseBase: Index into reversePoints of the diagonal which passes through (originalEnd, modifiedEnd)
  
  613
  >
  		const diagonalForwardBase = (modifiedEnd - modifiedStart);
  
  614
  >
  		const diagonalReverseBase = (originalEnd - originalStart);
  
  615
  >
  		// diagonalForwardOffset: Geometric offset which allows modifiedIndex to be computed from originalIndex and the
  
  616
  >
  		//    diagonal number (relative to diagonalForwardBase)
  
  617
  >
  		// diagonalReverseOffset: Geometric offset which allows modifiedIndex to be computed from originalIndex and the
  
  618
  >
  		//    diagonal number (relative to diagonalReverseBase)
  
  619
  >
  		const diagonalForwardOffset = (originalStart - modifiedStart);
  
  620
  >
  		const diagonalReverseOffset = (originalEnd - modifiedEnd);
  
  621
  >
  
  622
  >
  		// delta: The difference between the end diagonal and the start diagonal. This is used to relate diagonal numbers
  
  623
  >
  		//   relative to the start diagonal with diagonal numbers relative to the end diagonal.
  
  624
  >
  		// The Even/Oddn-ness of this delta is important for determining when we should check for overlap
  
  625
  >
  		const delta = diagonalReverseBase - diagonalForwardBase;
  
  626
  >
  		const deltaIsEven = (delta % 2 === 0);
  
  627
  >
  
  628
  >
  		// Here we set up the start and end points as the furthest points found so far
  
  629
  >
  		// in both the forward and reverse directions, respectively
  
  630
  >
  		forwardPoints[diagonalForwardBase] = originalStart;
  
  631
  >
  		reversePoints[diagonalReverseBase] = originalEnd;
  
  632
  >
  
  633
  >
  		// Remember if we quit early, and thus need to do a best-effort result instead of a real result.
  
  634
  >
  		quitEarlyArr[0] = false;
  
  635
  >
  
  636
  >
  
  637
  >
  
  638
  >
  		// A couple of points:
  
  639
  >
  		// --With this method, we iterate on the number of differences between the two sequences.
  
  640
  >
  		//   The more differences there actually are, the longer this will take.
  
  641
  >
  		// --Also, as the number of differences increases, we have to search on diagonals further
  
  642
  >
  		//   away from the reference diagonal (which is diagonalForwardBase for forward, diagonalReverseBase for reverse).
  
  643
  >
  		// --We extend on even diagonals (relative to the reference diagonal) only when numDifferences
  
  644
  >
  		//   is even and odd diagonals only when numDifferences is odd.
  
  645
  >
  		for (let numDifferences = 1; numDifferences <= (maxDifferences / 2) + 1; numDifferences++) {
  
  646
  >
  			let furthestOriginalIndex = 0;
  
  647
  >
  			let furthestModifiedIndex = 0;
  
  648
  >
  
  649
  >
  			// Run the algorithm in the forward direction
  
  650
  >
  			diagonalForwardStart = this.ClipDiagonalBound(diagonalForwardBase - numDifferences, numDifferences, diagonalForwardBase, numDiagonals);
  
  651
  >
  			diagonalForwardEnd = this.ClipDiagonalBound(diagonalForwardBase + numDifferences, numDifferences, diagonalForwardBase, numDiagonals);
  
  652
  >
  			for (let diagonal = diagonalForwardStart; diagonal <= diagonalForwardEnd; diagonal += 2) {
  
  653
  >
  				// STEP 1: We extend the furthest reaching point in the present diagonal
  
  654
  >
  				// by looking at the diagonals above and below and picking the one whose point
  
  655
  >
  				// is further away from the start point (originalStart, modifiedStart)
  
  656
  >
  				if (diagonal === diagonalForwardStart || (diagonal < diagonalForwardEnd && forwardPoints[diagonal - 1] < forwardPoints[diagonal + 1])) {
  
  657
  >
  					originalIndex = forwardPoints[diagonal + 1];
  
  658
  >
  				} else {
  
  659
  >
  					originalIndex = forwardPoints[diagonal - 1] + 1;
  
  660
  >
  				}
  
  661
  >
  				modifiedIndex = originalIndex - (diagonal - diagonalForwardBase) - diagonalForwardOffset;
  
  662
  >
  
  663
  >
  				// Save the current originalIndex so we can test for false overlap in step 3
  
  664
  >
  				const tempOriginalIndex = originalIndex;
  
  665
  >
  
  666
  >
  				// STEP 2: We can continue to extend the furthest reaching point in the present diagonal
  
  667
  >
  				// so long as the elements are equal.
  
  668
  >
  				while (originalIndex < originalEnd && modifiedIndex < modifiedEnd && this.ElementsAreEqual(originalIndex + 1, modifiedIndex + 1)) {
  
  669
  >
  					originalIndex++;
  
diff.ts ×1

  670
  >
  					modifiedIndex++;
  
  671
  >
  				}
  
  672
  >
  				forwardPoints[diagonal] = originalIndex;
  
diff.ts ×23

  673
  >
  
  674
  >
  				if (originalIndex + modifiedIndex > furthestOriginalIndex + furthestModifiedIndex) {
  
  675
  >
  					furthestOriginalIndex = originalIndex;
  
diff.ts ×1

  676
  >
  					furthestModifiedIndex = modifiedIndex;
  
  677
  >
  				}
  
  678
  >
  
diff.ts ×23

  679
  >
  				// STEP 3: If delta is odd (overlap first happens on forward when delta is odd)
  
  680
  >
  				// and diagonal is in the range of reverse diagonals computed for numDifferences-1
  
  681
  >
  				// (the previous iteration; we haven't computed reverse diagonals for numDifferences yet)
  
  682
  >
  				// then check for overlap.
  
  683
  >
  				if (!deltaIsEven && Math.abs(diagonal - diagonalReverseBase) <= (numDifferences - 1)) {
  
  684
  >
  					if (originalIndex >= reversePoints[diagonal]) {
  
diff.ts ×3

  685
  >
  						midOriginalArr[0] = originalIndex;
  
  686
  >
  						midModifiedArr[0] = modifiedIndex;
  
  687
  >
  
  688
  >
  						if (tempOriginalIndex <= reversePoints[diagonal] && LocalConstants.MaxDifferencesHistory > 0 && numDifferences <= (LocalConstants.MaxDifferencesHistory + 1)) {
  
  689
  >
  							// BINGO! We overlapped, and we have the full trace in memory!
  
diff.ts ×1

  690
  >
  							return this.WALKTRACE(diagonalForwardBase, diagonalForwardStart, diagonalForwardEnd, diagonalForwardOffset,
  
  691
  >
  								diagonalReverseBase, diagonalReverseStart, diagonalReverseEnd, diagonalReverseOffset,
  
  692
  >
  								forwardPoints, reversePoints,
  
  693
  >
  								originalIndex, originalEnd, midOriginalArr,
  
  694
  >
  								modifiedIndex, modifiedEnd, midModifiedArr,
  
  695
  >
  								deltaIsEven, quitEarlyArr
  
  696
  >
  							);
  
  697
  >
  						} else {
  
diff.ts ×3

  698
  >
  							// Either false overlap, or we didn't have enough memory for the full trace
  
diff.ts ×1

  699
  >
  							// Just return the recursion point
  
  700
  >
  							return null;
  
  701
  >
  						}
  
  702
  >
  					}
  
diff.ts ×3

  703
  >
  				}
  
  704
  >
  			}
  
diff.ts ×23

  705
  >
  
  706
  >
  			// Check to see if we should be quitting early, before moving on to the next iteration.
  
  707
  >
  			const matchLengthOfLongest = ((furthestOriginalIndex - originalStart) + (furthestModifiedIndex - modifiedStart) - numDifferences) / 2;
  
  708
  >
  
  709
  >
  			if (this.ContinueProcessingPredicate !== null && !this.ContinueProcessingPredicate(furthestOriginalIndex, matchLengthOfLongest)) {
  
  710
  >
  				// We can't finish, so skip ahead to generating a result from what we have.
  
diff.ts ×2

  711
  >
  				quitEarlyArr[0] = true;
  
  712
  >
  
  713
  >
  				// Use the furthest distance we got in the forward direction.
  
  714
  >
  				midOriginalArr[0] = furthestOriginalIndex;
  
  715
  >
  				midModifiedArr[0] = furthestModifiedIndex;
  
  716
  >
  
  717
  >
  				if (matchLengthOfLongest > 0 && LocalConstants.MaxDifferencesHistory > 0 && numDifferences <= (LocalConstants.MaxDifferencesHistory + 1)) {
  
  718
  >
  					// Enough of the history is in memory to walk it backwards
  
  719
  >
  					return this.WALKTRACE(diagonalForwardBase, diagonalForwardStart, diagonalForwardEnd, diagonalForwardOffset,
  
  720
  >
  						diagonalReverseBase, diagonalReverseStart, diagonalReverseEnd, diagonalReverseOffset,
  
  721
  >
  						forwardPoints, reversePoints,
  
  722
  >
  						originalIndex, originalEnd, midOriginalArr,
  
  723
  >
  						modifiedIndex, modifiedEnd, midModifiedArr,
  
  724
  >
  						deltaIsEven, quitEarlyArr
  
  725
  >
  					);
  
  726
  >
  				} else {
  
  727
  >
  					// We didn't actually remember enough of the history.
  
  728
  >
  
  729
  >
  					//Since we are quitting the diff early, we need to shift back the originalStart and modified start
  
  730
  >
  					//back into the boundary limits since we decremented their value above beyond the boundary limit.
  
  731
  >
  					originalStart++;
  
  732
  >
  					modifiedStart++;
  
  733
  >
  
  734
  >
  					return [
  
  735
  >
  						new DiffChange(originalStart, originalEnd - originalStart + 1,
  
  736
  >
  							modifiedStart, modifiedEnd - modifiedStart + 1)
  
  737
  >
  					];
  
  738
  >
  				}
  
  739
  >
  			}
  
  740
  >
  
diff.ts ×23

  741
  >
  			// Run the algorithm in the reverse direction
  
  742
  >
  			diagonalReverseStart = this.ClipDiagonalBound(diagonalReverseBase - numDifferences, numDifferences, diagonalReverseBase, numDiagonals);
  
  743
  >
  			diagonalReverseEnd = this.ClipDiagonalBound(diagonalReverseBase + numDifferences, numDifferences, diagonalReverseBase, numDiagonals);
  
  744
  >
  			for (let diagonal = diagonalReverseStart; diagonal <= diagonalReverseEnd; diagonal += 2) {
  
  745
  >
  				// STEP 1: We extend the furthest reaching point in the present diagonal
  
  746
  >
  				// by looking at the diagonals above and below and picking the one whose point
  
  747
  >
  				// is further away from the start point (originalEnd, modifiedEnd)
  
  748
  >
  				if (diagonal === diagonalReverseStart || (diagonal < diagonalReverseEnd && reversePoints[diagonal - 1] >= reversePoints[diagonal + 1])) {
  
  749
  >
  					originalIndex = reversePoints[diagonal + 1] - 1;
  
  750
  >
  				} else {
  
  751
  >
  					originalIndex = reversePoints[diagonal - 1];
  
diff.ts ×1

  752
  >
  				}
  
  753
  >
  				modifiedIndex = originalIndex - (diagonal - diagonalReverseBase) - diagonalReverseOffset;
  
diff.ts ×23

  754
  >
  
  755
  >
  				// Save the current originalIndex so we can test for false overlap
  
  756
  >
  				const tempOriginalIndex = originalIndex;
  
  757
  >
  
  758
  >
  				// STEP 2: We can continue to extend the furthest reaching point in the present diagonal
  
  759
  >
  				// as long as the elements are equal.
  
  760
  >
  				while (originalIndex > originalStart && modifiedIndex > modifiedStart && this.ElementsAreEqual(originalIndex, modifiedIndex)) {
  
  761
  >
  					originalIndex--;
  
diff.ts ×1

  762
  >
  					modifiedIndex--;
  
  763
  >
  				}
  
  764
  >
  				reversePoints[diagonal] = originalIndex;
  
diff.ts ×23

  765
  >
  
  766
  >
  				// STEP 4: If delta is even (overlap first happens on reverse when delta is even)
  
  767
  >
  				// and diagonal is in the range of forward diagonals computed for numDifferences
  
  768
  >
  				// then check for overlap.
  
  769
  >
  				if (deltaIsEven && Math.abs(diagonal - diagonalForwardBase) <= numDifferences) {
  
  770
  >
  					if (originalIndex <= forwardPoints[diagonal]) {
  
diff.ts ×3

  771
  >
  						midOriginalArr[0] = originalIndex;
  
  772
  >
  						midModifiedArr[0] = modifiedIndex;
  
  773
  >
  
  774
  >
  						if (tempOriginalIndex >= forwardPoints[diagonal] && LocalConstants.MaxDifferencesHistory > 0 && numDifferences <= (LocalConstants.MaxDifferencesHistory + 1)) {
  
  775
  >
  							// BINGO! We overlapped, and we have the full trace in memory!
  
diff.ts ×1

  776
  >
  							return this.WALKTRACE(diagonalForwardBase, diagonalForwardStart, diagonalForwardEnd, diagonalForwardOffset,
  
  777
  >
  								diagonalReverseBase, diagonalReverseStart, diagonalReverseEnd, diagonalReverseOffset,
  
  778
  >
  								forwardPoints, reversePoints,
  
  779
  >
  								originalIndex, originalEnd, midOriginalArr,
  
  780
  >
  								modifiedIndex, modifiedEnd, midModifiedArr,
  
  781
  >
  								deltaIsEven, quitEarlyArr
  
  782
  >
  							);
  
  783
  >
  						} else {
  
diff.ts ×3

  784
  >
  							// Either false overlap, or we didn't have enough memory for the full trace
  
diff.ts ×1

  785
  >
  							// Just return the recursion point
  
  786
  >
  							return null;
  
  787
  >
  						}
  
  788
  >
  					}
  
diff.ts ×3

  789
  >
  				}
  
  790
  >
  			}
  
diff.ts ×23

  791
  >
  
diff.ts ×2

  792
  >
  			// Save current vectors to history before the next iteration
  
  793
  >
  			if (numDifferences <= LocalConstants.MaxDifferencesHistory) {
  
  794
  >
  				// We are allocating space for one extra int, which we fill with
  
  795
  >
  				// the index of the diagonal base index
  
  796
  >
  				let temp = new Int32Array(diagonalForwardEnd - diagonalForwardStart + 2);
  
  797
  >
  				temp[0] = diagonalForwardBase - diagonalForwardStart + 1;
  
  798
  >
  				MyArray.Copy2(forwardPoints, diagonalForwardStart, temp, 1, diagonalForwardEnd - diagonalForwardStart + 1);
  
  799
  >
  				this.m_forwardHistory.push(temp);
  
  800
  >
  
  801
  >
  				temp = new Int32Array(diagonalReverseEnd - diagonalReverseStart + 2);
  
  802
  >
  				temp[0] = diagonalReverseBase - diagonalReverseStart + 1;
  
  803
  >
  				MyArray.Copy2(reversePoints, diagonalReverseStart, temp, 1, diagonalReverseEnd - diagonalReverseStart + 1);
  
  804
  >
  				this.m_reverseHistory.push(temp);
  
  805
  >
  			}
  
  806
  >
  
diff.ts ×23

  807
  >
  		}
  
  808
  
  809
  
  		// If we got here, then we have the full trace in history. We just have to convert it to a change list
  
  810
  
  		// NOTE: This part is a bit messy
  
  811
  
  		return this.WALKTRACE(diagonalForwardBase, diagonalForwardStart, diagonalForwardEnd, diagonalForwardOffset,
  
  812
  
  			diagonalReverseBase, diagonalReverseStart, diagonalReverseEnd, diagonalReverseOffset,
  
  813
  
  			forwardPoints, reversePoints,
  
  814
  
  			originalIndex, originalEnd, midOriginalArr,
  
  815
  
  			modifiedIndex, modifiedEnd, midModifiedArr,
  
  816
  
  			deltaIsEven, quitEarlyArr
  
  817
  
  		);
  
  818
  >
  	}
  
diff.ts ×23

  819
  >
  
diff.ts ×38

  820
  >
  	/**
  
  821
  >
  	 * Shifts the given changes to provide a more intuitive diff.
  
  822
  >
  	 * While the first element in a diff matches the first element after the diff,
  
  823
  >
  	 * we shift the diff down.
  
  824
  >
  	 *
  
  825
  >
  	 * @param changes The list of changes to shift
  
  826
  >
  	 * @returns The shifted changes
  
  827
  >
  	 */
  
  828
  >
  	private PrettifyChanges(changes: DiffChange[]): DiffChange[] {
  
  829
  >
  
diff.ts ×5

  830
  >
  		// Shift all the changes down first
  
  831
  >
  		for (let i = 0; i < changes.length; i++) {
  
  832
  >
  			const change = changes[i];
  
diff.ts ×20

  833
  >
  			const originalStop = (i < changes.length - 1) ? changes[i + 1].originalStart : this._originalElementsOrHash.length;
  
  834
  >
  			const modifiedStop = (i < changes.length - 1) ? changes[i + 1].modifiedStart : this._modifiedElementsOrHash.length;
  
  835
  >
  			const checkOriginal = change.originalLength > 0;
  
  836
  >
  			const checkModified = change.modifiedLength > 0;
  
  837
  >
  
  838
  >
  			while (
  
  839
  >
  				change.originalStart + change.originalLength < originalStop
  
  840
  >
  				&& change.modifiedStart + change.modifiedLength < modifiedStop
  
diff.ts ×1

  841
  >
  				&& (!checkOriginal || this.OriginalElementsAreEqual(change.originalStart, change.originalStart + change.originalLength))
  
  842
  >
  				&& (!checkModified || this.ModifiedElementsAreEqual(change.modifiedStart, change.modifiedStart + change.modifiedLength))
  
diff.ts ×1

  843
  >
  			) {
  
diff.ts ×20

  844
  >
  				const startStrictEqual = this.ElementsAreStrictEqual(change.originalStart, change.modifiedStart);
  
diff.ts ×5

  845
  >
  				const endStrictEqual = this.ElementsAreStrictEqual(change.originalStart + change.originalLength, change.modifiedStart + change.modifiedLength);
  
  846
  >
  				if (endStrictEqual && !startStrictEqual) {
  
  847
  >
  					// moving the change down would create an equal change, but the elements are not strict equal
  
diff.ts ×1

  848
  >
  					break;
  
  849
  >
  				}
  
  850
  >
  				change.originalStart++;
  
diff.ts ×1

  851
  >
  				change.modifiedStart++;
  
  852
  >
  			}
  
  853
  >
  
diff.ts ×20

  854
  >
  			const mergedChangeArr: Array<DiffChange | null> = [null];
  
  855
  >
  			if (i < changes.length - 1 && this.ChangesOverlap(changes[i], changes[i + 1], mergedChangeArr)) {
  
  856
  >
  				changes[i] = mergedChangeArr[0]!;
  
diff.ts ×1

  857
  >
  				changes.splice(i + 1, 1);
  
  858
  >
  				i--;
  
  859
  >
  				continue;
  
  860
  >
  			}
  
  861
  >
  		}
  
diff.ts ×20

  862
  >
  
diff.ts ×5

  863
  >
  		// Shift changes back up until we hit empty or whitespace-only lines
  
  864
  >
  		for (let i = changes.length - 1; i >= 0; i--) {
  
  865
  >
  			const change = changes[i];
  
diff.ts ×20

  866
  >
  
  867
  >
  			let originalStop = 0;
  
  868
  >
  			let modifiedStop = 0;
  
  869
  >
  			if (i > 0) {
  
  870
  >
  				const prevChange = changes[i - 1];
  
diff.ts ×1

  871
  >
  				originalStop = prevChange.originalStart + prevChange.originalLength;
  
  872
  >
  				modifiedStop = prevChange.modifiedStart + prevChange.modifiedLength;
  
  873
  >
  			}
  
  874
  >
  
diff.ts ×20

  875
  >
  			const checkOriginal = change.originalLength > 0;
  
  876
  >
  			const checkModified = change.modifiedLength > 0;
  
  877
  >
  
  878
  >
  			let bestDelta = 0;
  
  879
  >
  			let bestScore = this._boundaryScore(change.originalStart, change.originalLength, change.modifiedStart, change.modifiedLength);
  
  880
  >
  
  881
  >
  			for (let delta = 1; ; delta++) {
  
  882
  >
  				const originalStart = change.originalStart - delta;
  
  883
  >
  				const modifiedStart = change.modifiedStart - delta;
  
  884
  >
  
  885
  >
  				if (originalStart < originalStop || modifiedStart < modifiedStop) {
  
  886
  >
  					break;
  
diff.ts ×1

  887
  >
  				}
  
  888
  >
  
diff.ts ×1

  889
  >
  				if (checkOriginal && !this.OriginalElementsAreEqual(originalStart, originalStart + change.originalLength)) {
  
diff.ts ×20

  890
  >
  					break;
  
diff.ts ×1

  891
  >
  				}
  
  892
  >
  
diff.ts ×1

  893
  >
  				if (checkModified && !this.ModifiedElementsAreEqual(modifiedStart, modifiedStart + change.modifiedLength)) {
  
diff.ts ×20

  894
  >
  					break;
  
diff.ts ×1

  895
  >
  				}
  
  896
  >
  
diff.ts ×1

  897
  >
  				const touchingPreviousChange = (originalStart === originalStop && modifiedStart === modifiedStop);
  
  898
  >
  				const score = (
  
diff.ts ×20

  899
  >
  					(touchingPreviousChange ? 5 : 0)
  
  900
  >
  					+ this._boundaryScore(originalStart, change.originalLength, modifiedStart, change.modifiedLength)
  
  901
  >
  				);
  
  902
  >
  
  903
  >
  				if (score > bestScore) {
  
  904
  >
  					bestScore = score;
  
diff.ts ×1

  905
  >
  					bestDelta = delta;
  
  906
  >
  				}
  
  907
  >
  			}
  
diff.ts ×20

  908
  >
  
  909
  >
  			change.originalStart -= bestDelta;
  
  910
  >
  			change.modifiedStart -= bestDelta;
  
  911
  >
  
  912
  >
  			const mergedChangeArr: Array<DiffChange | null> = [null];
  
  913
  >
  			if (i > 0 && this.ChangesOverlap(changes[i - 1], changes[i], mergedChangeArr)) {
  
  914
  >
  				changes[i - 1] = mergedChangeArr[0]!;
  
diff.ts ×1

  915
  >
  				changes.splice(i, 1);
  
  916
  >
  				i++;
  
  917
  >
  				continue;
  
  918
  >
  			}
  
  919
  >
  		}
  
diff.ts ×20

  920
  >
  
diff.ts ×5

  921
  >
  		// There could be multiple longest common substrings.
  
  922
  >
  		// Give preference to the ones containing longer lines
  
  923
  >
  		if (this._hasStrings) {
  
  924
  >
  			for (let i = 1, len = changes.length; i < len; i++) {
  
diff.ts ×3

  925
  >
  				const aChange = changes[i - 1];
  
diff.ts ×2

  926
  >
  				const bChange = changes[i];
  
  927
  >
  				const matchedLength = bChange.originalStart - aChange.originalStart - aChange.originalLength;
  
  928
  >
  				const aOriginalStart = aChange.originalStart;
  
  929
  >
  				const bOriginalEnd = bChange.originalStart + bChange.originalLength;
  
  930
  >
  				const abOriginalLength = bOriginalEnd - aOriginalStart;
  
  931
  >
  				const aModifiedStart = aChange.modifiedStart;
  
  932
  >
  				const bModifiedEnd = bChange.modifiedStart + bChange.modifiedLength;
  
  933
  >
  				const abModifiedLength = bModifiedEnd - aModifiedStart;
  
  934
  >
  				// Avoid wasting a lot of time with these searches
  
  935
  >
  				if (matchedLength < 5 && abOriginalLength < 20 && abModifiedLength < 20) {
  
  936
  >
  					const t = this._findBetterContiguousSequence(
  
diff.ts ×7

  937
  >
  						aOriginalStart, abOriginalLength,
  
  938
  >
  						aModifiedStart, abModifiedLength,
  
  939
  >
  						matchedLength
  
  940
  >
  					);
  
  941
  >
  					if (t) {
  
  942
  >
  						const [originalMatchStart, modifiedMatchStart] = t;
  
diff.ts ×4

  943
  >
  						if (originalMatchStart !== aChange.originalStart + aChange.originalLength || modifiedMatchStart !== aChange.modifiedStart + aChange.modifiedLength) {
  
  944
  >
  							// switch to another sequence that has a better score
  
diff.ts ×1

  945
  >
  							aChange.originalLength = originalMatchStart - aChange.originalStart;
  
  946
  >
  							aChange.modifiedLength = modifiedMatchStart - aChange.modifiedStart;
  
  947
  >
  							bChange.originalStart = originalMatchStart + matchedLength;
  
  948
  >
  							bChange.modifiedStart = modifiedMatchStart + matchedLength;
  
  949
  >
  							bChange.originalLength = bOriginalEnd - bChange.originalStart;
  
  950
  >
  							bChange.modifiedLength = bModifiedEnd - bChange.modifiedStart;
  
  951
  >
  						}
  
  952
  >
  					}
  
diff.ts ×4

  953
  >
  				}
  
diff.ts ×7

  954
  >
  			}
  
diff.ts ×2

  955
  >
  		}
  
diff.ts ×3

  956
  >
  
diff.ts ×5

  957
  >
  		return changes;
  
  958
  >
  	}
  
  959
  >
  
diff.ts ×38

  960
  >
  	private _findBetterContiguousSequence(originalStart: number, originalLength: number, modifiedStart: number, modifiedLength: number, desiredLength: number): [number, number] | null {
  
  961
  >
  		if (originalLength < desiredLength || modifiedLength < desiredLength) {
  
diff.ts ×7

  962
  
  			return null;
  
  963
  
  		}
  
  964
  >
  		const originalMax = originalStart + originalLength - desiredLength + 1;
  
diff.ts ×7

  965
  >
  		const modifiedMax = modifiedStart + modifiedLength - desiredLength + 1;
  
  966
  >
  		let bestScore = 0;
  
  967
  >
  		let bestOriginalStart = 0;
  
  968
  >
  		let bestModifiedStart = 0;
  
  969
  >
  		for (let i = originalStart; i < originalMax; i++) {
  
  970
  >
  			for (let j = modifiedStart; j < modifiedMax; j++) {
  
  971
  >
  				const score = this._contiguousSequenceScore(i, j, desiredLength);
  
  972
  >
  				if (score > 0 && score > bestScore) {
  
  973
  >
  					bestScore = score;
  
diff.ts ×4

  974
  >
  					bestOriginalStart = i;
  
  975
  >
  					bestModifiedStart = j;
  
  976
  >
  				}
  
  977
  >
  			}
  
diff.ts ×7

  978
  >
  		}
  
  979
  >
  		if (bestScore > 0) {
  
  980
  >
  			return [bestOriginalStart, bestModifiedStart];
  
diff.ts ×4

  981
  >
  		}
  
  982
  >
  		return null;
  
diff.ts ×1

  983
  >
  	}
  
diff.ts ×7

  984
  >
  
diff.ts ×38

  985
  >
  	private _contiguousSequenceScore(originalStart: number, modifiedStart: number, length: number): number {
  
  986
  >
  		let score = 0;
  
diff.ts ×7

  987
  >
  		for (let l = 0; l < length; l++) {
  
  988
  >
  			if (!this.ElementsAreEqual(originalStart + l, modifiedStart + l)) {
  
  989
  >
  				return 0;
  
  990
  >
  			}
  
  991
  >
  			score += this._originalStringElements[originalStart + l].length;
  
  992
  >
  		}
  
  993
  >
  		return score;
  
  994
  >
  	}
  
  995
  >
  
diff.ts ×38

  996
  >
  	private _OriginalIsBoundary(index: number): boolean {
  
  997
  >
  		if (index <= 0 || index >= this._originalElementsOrHash.length - 1) {
  
diff.ts ×20

  998
  >
  			return true;
  
diff.ts ×1

  999
  >
  		}
  
  1000
  >
  		return (this._hasStrings && /^\s*$/.test(this._originalStringElements[index]));
  
diff.ts ×1

  1001
  >
  	}
  
diff.ts ×20

  1002
  >
  
diff.ts ×38

  1003
  >
  	private _OriginalRegionIsBoundary(originalStart: number, originalLength: number): boolean {
  
  1004
  >
  		if (this._OriginalIsBoundary(originalStart) || this._OriginalIsBoundary(originalStart - 1)) {
  
diff.ts ×20

  1005
  >
  			return true;
  
diff.ts ×1

  1006
  >
  		}
  
  1007
  >
  		if (originalLength > 0) {
  
diff.ts ×1

  1008
  >
  			const originalEnd = originalStart + originalLength;
  
diff.ts ×2

  1009
  >
  			if (this._OriginalIsBoundary(originalEnd - 1) || this._OriginalIsBoundary(originalEnd)) {
  
  1010
  >
  				return true;
  
diff.ts ×1

  1011
  >
  			}
  
  1012
  >
  		}
  
diff.ts ×2

  1013
  >
  		return false;
  
diff.ts ×1

  1014
  >
  	}
  
diff.ts ×20

  1015
  >
  
diff.ts ×38

  1016
  >
  	private _ModifiedIsBoundary(index: number): boolean {
  
  1017
  >
  		if (index <= 0 || index >= this._modifiedElementsOrHash.length - 1) {
  
diff.ts ×20

  1018
  >
  			return true;
  
diff.ts ×1

  1019
  >
  		}
  
  1020
  >
  		return (this._hasStrings && /^\s*$/.test(this._modifiedStringElements[index]));
  
diff.ts ×1

  1021
  >
  	}
  
diff.ts ×20

  1022
  >
  
diff.ts ×38

  1023
  >
  	private _ModifiedRegionIsBoundary(modifiedStart: number, modifiedLength: number): boolean {
  
  1024
  >
  		if (this._ModifiedIsBoundary(modifiedStart) || this._ModifiedIsBoundary(modifiedStart - 1)) {
  
diff.ts ×20

  1025
  >
  			return true;
  
diff.ts ×1

  1026
  >
  		}
  
  1027
  >
  		if (modifiedLength > 0) {
  
diff.ts ×1

  1028
  >
  			const modifiedEnd = modifiedStart + modifiedLength;
  
diff.ts ×2

  1029
  >
  			if (this._ModifiedIsBoundary(modifiedEnd - 1) || this._ModifiedIsBoundary(modifiedEnd)) {
  
  1030
  >
  				return true;
  
diff.ts ×1

  1031
  >
  			}
  
  1032
  >
  		}
  
diff.ts ×2

  1033
  >
  		return false;
  
diff.ts ×1

  1034
  >
  	}
  
diff.ts ×20

  1035
  >
  
diff.ts ×38

  1036
  >
  	private _boundaryScore(originalStart: number, originalLength: number, modifiedStart: number, modifiedLength: number): number {
  
  1037
  >
  		const originalScore = (this._OriginalRegionIsBoundary(originalStart, originalLength) ? 1 : 0);
  
diff.ts ×20

  1038
  >
  		const modifiedScore = (this._ModifiedRegionIsBoundary(modifiedStart, modifiedLength) ? 1 : 0);
  
  1039
  >
  		return (originalScore + modifiedScore);
  
  1040
  >
  	}
  
  1041
  >
  
diff.ts ×38

  1042
  >
  	/**
  
  1043
  >
  	 * Concatenates the two input DiffChange lists and returns the resulting
  
  1044
  >
  	 * list.
  
  1045
  >
  	 * @param The left changes
  
  1046
  >
  	 * @param The right changes
  
  1047
  >
  	 * @returns The concatenated list
  
  1048
  >
  	 */
  
  1049
  >
  	private ConcatenateChanges(left: DiffChange[], right: DiffChange[]): DiffChange[] {
  
  1050
  >
  		const mergedChangeArr: DiffChange[] = [];
  
diff.ts ×23

  1051
  >
  
  1052
  >
  		if (left.length === 0 || right.length === 0) {
  
  1053
  
  			return (right.length > 0) ? right : left;
  
  1054
  >
  		} else if (this.ChangesOverlap(left[left.length - 1], right[0], mergedChangeArr)) {
  
diff.ts ×23

  1055
  >
  			// Since we break the problem down recursively, it is possible that we
  
diff.ts ×1

  1056
  >
  			// might recurse in the middle of a change thereby splitting it into
  
  1057
  >
  			// two changes. Here in the combining stage, we detect and fuse those
  
  1058
  >
  			// changes back together
  
  1059
  >
  			const result = new Array<DiffChange>(left.length + right.length - 1);
  
  1060
  >
  			MyArray.Copy(left, 0, result, 0, left.length - 1);
  
  1061
  >
  			result[left.length - 1] = mergedChangeArr[0];
  
  1062
  >
  			MyArray.Copy(right, 1, result, left.length, right.length - 1);
  
  1063
  >
  
  1064
  >
  			return result;
  
  1065
  >
  		} else {
  
diff.ts ×23

  1066
  >
  			const result = new Array<DiffChange>(left.length + right.length);
  
diff.ts ×1

  1067
  >
  			MyArray.Copy(left, 0, result, 0, left.length);
  
  1068
  >
  			MyArray.Copy(right, 0, result, left.length, right.length);
  
  1069
  >
  
  1070
  >
  			return result;
  
  1071
  >
  		}
  
  1072
  >
  	}
  
diff.ts ×23

  1073
  >
  
diff.ts ×38

  1074
  >
  	/**
  
  1075
  >
  	 * Returns true if the two changes overlap and can be merged into a single
  
  1076
  >
  	 * change
  
  1077
  >
  	 * @param left The left change
  
  1078
  >
  	 * @param right The right change
  
  1079
  >
  	 * @param mergedChange The merged change if the two overlap, null otherwise
  
  1080
  >
  	 * @returns True if the two changes overlap
  
  1081
  >
  	 */
  
  1082
  >
  	private ChangesOverlap(left: DiffChange, right: DiffChange, mergedChangeArr: Array<DiffChange | null>): boolean {
  
  1083
  >
  		Debug.Assert(left.originalStart <= right.originalStart, 'Left change is not less than or equal to right change');
  
diff.ts ×23

  1084
  >
  		Debug.Assert(left.modifiedStart <= right.modifiedStart, 'Left change is not less than or equal to right change');
  
  1085
  >
  
  1086
  >
  		if (left.originalStart + left.originalLength >= right.originalStart || left.modifiedStart + left.modifiedLength >= right.modifiedStart) {
  
  1087
  >
  			const originalStart = left.originalStart;
  
diff.ts ×1

  1088
  >
  			let originalLength = left.originalLength;
  
  1089
  >
  			const modifiedStart = left.modifiedStart;
  
  1090
  >
  			let modifiedLength = left.modifiedLength;
  
  1091
  >
  
  1092
  >
  			if (left.originalStart + left.originalLength >= right.originalStart) {
  
  1093
  >
  				originalLength = right.originalStart + right.originalLength - left.originalStart;
  
  1094
  >
  			}
  
  1095
  >
  			if (left.modifiedStart + left.modifiedLength >= right.modifiedStart) {
  
  1096
  >
  				modifiedLength = right.modifiedStart + right.modifiedLength - left.modifiedStart;
  
  1097
  >
  			}
  
  1098
  >
  
  1099
  >
  			mergedChangeArr[0] = new DiffChange(originalStart, originalLength, modifiedStart, modifiedLength);
  
  1100
  >
  			return true;
  
  1101
  >
  		} else {
  
diff.ts ×23

  1102
  >
  			mergedChangeArr[0] = null;
  
diff.ts ×2

  1103
  >
  			return false;
  
  1104
  >
  		}
  
  1105
  >
  	}
  
diff.ts ×23

  1106
  >
  
diff.ts ×38

  1107
  >
  	/**
  
  1108
  >
  	 * Helper method used to clip a diagonal index to the range of valid
  
  1109
  >
  	 * diagonals. This also decides whether or not the diagonal index,
  
  1110
  >
  	 * if it exceeds the boundary, should be clipped to the boundary or clipped
  
  1111
  >
  	 * one inside the boundary depending on the Even/Odd status of the boundary
  
  1112
  >
  	 * and numDifferences.
  
  1113
  >
  	 * @param diagonal The index of the diagonal to clip.
  
  1114
  >
  	 * @param numDifferences The current number of differences being iterated upon.
  
  1115
  >
  	 * @param diagonalBaseIndex The base reference diagonal.
  
  1116
  >
  	 * @param numDiagonals The total number of diagonals.
  
  1117
  >
  	 * @returns The clipped diagonal index.
  
  1118
  >
  	 */
  
  1119
  >
  	private ClipDiagonalBound(diagonal: number, numDifferences: number, diagonalBaseIndex: number, numDiagonals: number): number {
  
  1120
  >
  		if (diagonal >= 0 && diagonal < numDiagonals) {
  
diff.ts ×23

  1121
  >
  			// Nothing to clip, its in range
  
  1122
  >
  			return diagonal;
  
  1123
  >
  		}
  
  1124
  >
  
diff.ts ×2

  1125
  >
  		// diagonalsBelow: The number of diagonals below the reference diagonal
  
  1126
  >
  		// diagonalsAbove: The number of diagonals above the reference diagonal
  
  1127
  >
  		const diagonalsBelow = diagonalBaseIndex;
  
  1128
  >
  		const diagonalsAbove = numDiagonals - diagonalBaseIndex - 1;
  
  1129
  >
  		const diffEven = (numDifferences % 2 === 0);
  
  1130
  >
  
  1131
  >
  		if (diagonal < 0) {
  
  1132
  >
  			const lowerBoundEven = (diagonalsBelow % 2 === 0);
  
diff.ts ×1

  1133
  >
  			return (diffEven === lowerBoundEven) ? 0 : 1;
  
  1134
  >
  		} else {
  
diff.ts ×2

  1135
  >
  			const upperBoundEven = (diagonalsAbove % 2 === 0);
  
diff.ts ×1

  1136
  >
  			return (diffEven === upperBoundEven) ? numDiagonals - 1 : numDiagonals - 2;
  
  1137
  >
  		}
  
  1138
  >
  	}
  
diff.ts ×23

  1139
  >
  }
  
diff.ts ×38

  1140
  >
  
  1141
  >
  
  1142
  >
  /**
  
  1143
  >
   * Precomputed equality array for character codes.
  
  1144
  >
   */
  
  1145
  >
  const precomputedEqualityArray = new Uint32Array(0x10000);
  
  1146
  >
  
  1147
  >
  /**
  
  1148
  >
   * Computes the Levenshtein distance for strings of length <= 32.
  
  1149
  >
   * @param firstString - The first string.
  
  1150
  >
   * @param secondString - The second string.
  
  1151
  >
   * @returns The Levenshtein distance.
  
  1152
  >
   */
  
  1153
  >
  const computeLevenshteinDistanceForShortStrings = (firstString: string, secondString: string): number => {
  
  1154
  
  	const firstStringLength = firstString.length;
  
  1155
  
  	const secondStringLength = secondString.length;
  
  1156
  
  	const lastBitMask = 1 << (firstStringLength - 1);
  
  1157
  
  	let positiveVector = -1;
  
  1158
  
  	let negativeVector = 0;
  
  1159
  
  	let distance = firstStringLength;
  
  1160
  
  	let index = firstStringLength;
  
  1161
  
  1162
  
  	// Initialize precomputedEqualityArray for firstString
  
  1163
  
  	while (index--) {
  
  1164
  
  		precomputedEqualityArray[firstString.charCodeAt(index)] |= 1 << index;
  
  1165
  
  	}
  
  1166
  
  1167
  
  	// Process each character of secondString
  
  1168
  
  	for (index = 0; index < secondStringLength; index++) {
  
  1169
  
  		let equalityMask = precomputedEqualityArray[secondString.charCodeAt(index)];
  
  1170
  
  		const combinedVector = equalityMask | negativeVector;
  
  1171
  
  		equalityMask |= ((equalityMask & positiveVector) + positiveVector) ^ positiveVector;
  
  1172
  
  		negativeVector |= ~(equalityMask | positiveVector);
  
  1173
  
  		positiveVector &= equalityMask;
  
  1174
  
  		if (negativeVector & lastBitMask) {
  
  1175
  
  			distance++;
  
  1176
  
  		}
  
  1177
  
  		if (positiveVector & lastBitMask) {
  
  1178
  
  			distance--;
  
  1179
  
  		}
  
  1180
  
  		negativeVector = (negativeVector << 1) | 1;
  
  1181
  
  		positiveVector = (positiveVector << 1) | ~(combinedVector | negativeVector);
  
  1182
  
  		negativeVector &= combinedVector;
  
  1183
  
  	}
  
  1184
  
  1185
  
  	// Reset precomputedEqualityArray
  
  1186
  
  	index = firstStringLength;
  
  1187
  
  	while (index--) {
  
  1188
  
  		precomputedEqualityArray[firstString.charCodeAt(index)] = 0;
  
  1189
  
  	}
  
  1190
  
  1191
  
  	return distance;
  
  1192
  
  };
  
  1193
  >
  
diff.ts ×38

  1194
  >
  /**
  
  1195
  >
   * Computes the Levenshtein distance for strings of length > 32.
  
  1196
  >
   * @param firstString - The first string.
  
  1197
  >
   * @param secondString - The second string.
  
  1198
  >
   * @returns The Levenshtein distance.
  
  1199
  >
   */
  
  1200
  
  function computeLevenshteinDistanceForLongStrings(firstString: string, secondString: string): number {
  
  1201
  
  	const firstStringLength = firstString.length;
  
  1202
  
  	const secondStringLength = secondString.length;
  
  1203
  
  	const horizontalBitArray = [];
  
  1204
  
  	const verticalBitArray = [];
  
  1205
  
  	const horizontalSize = Math.ceil(firstStringLength / 32);
  
  1206
  
  	const verticalSize = Math.ceil(secondStringLength / 32);
  
  1207
  
  1208
  
  	// Initialize horizontal and vertical bit arrays
  
  1209
  
  	for (let i = 0; i < horizontalSize; i++) {
  
  1210
  
  		horizontalBitArray[i] = -1;
  
  1211
  
  		verticalBitArray[i] = 0;
  
  1212
  
  	}
  
  1213
  
  1214
  
  	let verticalIndex = 0;
  
  1215
  
  	for (; verticalIndex < verticalSize - 1; verticalIndex++) {
  
  1216
  
  		let negativeVector = 0;
  
  1217
  
  		let positiveVector = -1;
  
  1218
  
  		const start = verticalIndex * 32;
  
  1219
  
  		const verticalLength = Math.min(32, secondStringLength) + start;
  
  1220
  
  1221
  
  		// Initialize precomputedEqualityArray for secondString
  
  1222
  
  		for (let k = start; k < verticalLength; k++) {
  
  1223
  
  			precomputedEqualityArray[secondString.charCodeAt(k)] |= 1 << k;
  
  1224
  
  		}
  
  1225
  
  1226
  
  		// Process each character of firstString
  
  1227
  
  		for (let i = 0; i < firstStringLength; i++) {
  
  1228
  
  			const equalityMask = precomputedEqualityArray[firstString.charCodeAt(i)];
  
  1229
  
  			const previousBit = (horizontalBitArray[(i / 32) | 0] >>> i) & 1;
  
  1230
  
  			const matchBit = (verticalBitArray[(i / 32) | 0] >>> i) & 1;
  
  1231
  
  			const combinedVector = equalityMask | negativeVector;
  
  1232
  
  			const combinedHorizontalVector = ((((equalityMask | matchBit) & positiveVector) + positiveVector) ^ positiveVector) | equalityMask | matchBit;
  
  1233
  
  			let positiveHorizontalVector = negativeVector | ~(combinedHorizontalVector | positiveVector);
  
  1234
  
  			let negativeHorizontalVector = positiveVector & combinedHorizontalVector;
  
  1235
  
  			if ((positiveHorizontalVector >>> 31) ^ previousBit) {
  
  1236
  
  				horizontalBitArray[(i / 32) | 0] ^= 1 << i;
  
  1237
  
  			}
  
  1238
  
  			if ((negativeHorizontalVector >>> 31) ^ matchBit) {
  
  1239
  
  				verticalBitArray[(i / 32) | 0] ^= 1 << i;
  
  1240
  
  			}
  
  1241
  
  			positiveHorizontalVector = (positiveHorizontalVector << 1) | previousBit;
  
  1242
  
  			negativeHorizontalVector = (negativeHorizontalVector << 1) | matchBit;
  
  1243
  
  			positiveVector = negativeHorizontalVector | ~(combinedVector | positiveHorizontalVector);
  
  1244
  
  			negativeVector = positiveHorizontalVector & combinedVector;
  
  1245
  
  		}
  
  1246
  
  1247
  
  		// Reset precomputedEqualityArray
  
  1248
  
  		for (let k = start; k < verticalLength; k++) {
  
  1249
  
  			precomputedEqualityArray[secondString.charCodeAt(k)] = 0;
  
  1250
  
  		}
  
  1251
  
  	}
  
  1252
  
  1253
  
  	let negativeVector = 0;
  
  1254
  
  	let positiveVector = -1;
  
  1255
  
  	const start = verticalIndex * 32;
  
  1256
  
  	const verticalLength = Math.min(32, secondStringLength - start) + start;
  
  1257
  
  1258
  
  	// Initialize precomputedEqualityArray for secondString
  
  1259
  
  	for (let k = start; k < verticalLength; k++) {
  
  1260
  
  		precomputedEqualityArray[secondString.charCodeAt(k)] |= 1 << k;
  
  1261
  
  	}
  
  1262
  
  1263
  
  	let distance = secondStringLength;
  
  1264
  
  1265
  
  	// Process each character of firstString
  
  1266
  
  	for (let i = 0; i < firstStringLength; i++) {
  
  1267
  
  		const equalityMask = precomputedEqualityArray[firstString.charCodeAt(i)];
  
  1268
  
  		const previousBit = (horizontalBitArray[(i / 32) | 0] >>> i) & 1;
  
  1269
  
  		const matchBit = (verticalBitArray[(i / 32) | 0] >>> i) & 1;
  
  1270
  
  		const combinedVector = equalityMask | negativeVector;
  
  1271
  
  		const combinedHorizontalVector = ((((equalityMask | matchBit) & positiveVector) + positiveVector) ^ positiveVector) | equalityMask | matchBit;
  
  1272
  
  		let positiveHorizontalVector = negativeVector | ~(combinedHorizontalVector | positiveVector);
  
  1273
  
  		let negativeHorizontalVector = positiveVector & combinedHorizontalVector;
  
  1274
  
  		distance += (positiveHorizontalVector >>> (secondStringLength - 1)) & 1;
  
  1275
  
  		distance -= (negativeHorizontalVector >>> (secondStringLength - 1)) & 1;
  
  1276
  
  		if ((positiveHorizontalVector >>> 31) ^ previousBit) {
  
  1277
  
  			horizontalBitArray[(i / 32) | 0] ^= 1 << i;
  
  1278
  
  		}
  
  1279
  
  		if ((negativeHorizontalVector >>> 31) ^ matchBit) {
  
  1280
  
  			verticalBitArray[(i / 32) | 0] ^= 1 << i;
  
  1281
  
  		}
  
  1282
  
  		positiveHorizontalVector = (positiveHorizontalVector << 1) | previousBit;
  
  1283
  
  		negativeHorizontalVector = (negativeHorizontalVector << 1) | matchBit;
  
  1284
  
  		positiveVector = negativeHorizontalVector | ~(combinedVector | positiveHorizontalVector);
  
  1285
  
  		negativeVector = positiveHorizontalVector & combinedVector;
  
  1286
  
  	}
  
  1287
  
  1288
  
  	// Reset precomputedEqualityArray
  
  1289
  
  	for (let k = start; k < verticalLength; k++) {
  
  1290
  
  		precomputedEqualityArray[secondString.charCodeAt(k)] = 0;
  
  1291
  
  	}
  
  1292
  
  1293
  
  	return distance;
  
  1294
  
  }
  
  1295
  >
  
diff.ts ×38

  1296
  >
  /**
  
  1297
  >
   * Computes the Levenshtein distance between two strings.
  
  1298
  >
   * @param firstString - The first string.
  
  1299
  >
   * @param secondString - The second string.
  
  1300
  >
   * @returns The Levenshtein distance.
  
  1301
  >
   */
  
  1302
  >
  export function computeLevenshteinDistance(firstString: string, secondString: string): number {
  
  1303
  
  	if (firstString.length < secondString.length) {
  
  1304
  
  		const temp = secondString;
  
  1305
  
  		secondString = firstString;
  
  1306
  
  		firstString = temp;
  
  1307
  
  	}
  
  1308
  
  	if (secondString.length === 0) {
  
  1309
  
  		return firstString.length;
  
  1310
  
  	}
  
  1311
  
  	if (firstString.length <= 32) {
  
  1312
  
  		return computeLevenshteinDistanceForShortStrings(firstString, secondString);
  
  1313
  
  	}
  
  1314
  
  	return computeLevenshteinDistanceForLongStrings(firstString, secondString);
  
  1315
  
  }