private ComputeDiffRecursive()

in server/src/diff.ts [386:468]
52 lines of code
14 McCabe index (conditional complexity)

	private ComputeDiffRecursive(originalStart: number, originalEnd: number, modifiedStart: number, modifiedEnd: number, quitEarlyArr: boolean[]): DiffChange[] {
		quitEarlyArr[0] = false;

		// Find the start of the differences
		while (originalStart <= originalEnd && modifiedStart <= modifiedEnd && this.ElementsAreEqual(originalStart, modifiedStart)) {
			originalStart++;
			modifiedStart++;
		}

		// Find the end of the differences
		while (originalEnd >= originalStart && modifiedEnd >= modifiedStart && this.ElementsAreEqual(originalEnd, modifiedEnd)) {
			originalEnd--;
			modifiedEnd--;
		}

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

			if (modifiedStart <= modifiedEnd) {
				Debug.Assert(originalStart === originalEnd + 1, 'originalStart should only be one more than originalEnd');

				// All insertions
				changes = [
					new DiffChange(originalStart, 0, modifiedStart, modifiedEnd - modifiedStart + 1)
				];
			} else if (originalStart <= originalEnd) {
				Debug.Assert(modifiedStart === modifiedEnd + 1, 'modifiedStart should only be one more than modifiedEnd');

				// All deletions
				changes = [
					new DiffChange(originalStart, originalEnd - originalStart + 1, modifiedStart, 0)
				];
			} else {
				Debug.Assert(originalStart === originalEnd + 1, 'originalStart should only be one more than originalEnd');
				Debug.Assert(modifiedStart === modifiedEnd + 1, 'modifiedStart should only be one more than modifiedEnd');

				// Identical sequences - No differences
				changes = [];
			}

			return changes;
		}

		// This problem can be solved using the Divide-And-Conquer technique.
		const midOriginalArr = [0];
		const midModifiedArr = [0];
		const result = this.ComputeRecursionPoint(originalStart, originalEnd, modifiedStart, modifiedEnd, midOriginalArr, midModifiedArr, quitEarlyArr);

		const midOriginal = midOriginalArr[0];
		const midModified = midModifiedArr[0];

		if (result !== null) {
			// Result is not-null when there was enough memory to compute the changes while
			// searching for the recursion point
			return result;
		} else if (!quitEarlyArr[0]) {
			// We can break the problem down recursively by finding the changes in the
			// First Half:   (originalStart, modifiedStart) to (midOriginal, midModified)
			// Second Half:  (midOriginal + 1, minModified + 1) to (originalEnd, modifiedEnd)
			// NOTE: ComputeDiff() is inclusive, therefore the second range starts on the next point

			const leftChanges = this.ComputeDiffRecursive(originalStart, midOriginal, modifiedStart, midModified, quitEarlyArr);
			let rightChanges: DiffChange[] = [];

			if (!quitEarlyArr[0]) {
				rightChanges = this.ComputeDiffRecursive(midOriginal + 1, originalEnd, midModified + 1, modifiedEnd, quitEarlyArr);
			} else {
				// We did't have time to finish the first half, so we don't have time to compute this half.
				// Consider the entire rest of the sequence different.
				rightChanges = [
					new DiffChange(midOriginal + 1, originalEnd - (midOriginal + 1) + 1, midModified + 1, modifiedEnd - (midModified + 1) + 1)
				];
			}

			return this.ConcatenateChanges(leftChanges, rightChanges);
		}

		// If we hit here, we quit early, and so can't return anything meaningful
		return [
			new DiffChange(originalStart, originalEnd - originalStart + 1, modifiedStart, modifiedEnd - modifiedStart + 1)
		];
	}