private WALKTRACE()

in server/src/diff.ts [470:594]
95 lines of code
18 McCabe index (conditional complexity)

	private WALKTRACE(diagonalForwardBase: number, diagonalForwardStart: number, diagonalForwardEnd: number, diagonalForwardOffset: number,
		diagonalReverseBase: number, diagonalReverseStart: number, diagonalReverseEnd: number, diagonalReverseOffset: number,
		forwardPoints: Int32Array, reversePoints: Int32Array,
		originalIndex: number, originalEnd: number, midOriginalArr: number[],
		modifiedIndex: number, modifiedEnd: number, midModifiedArr: number[],
		deltaIsEven: boolean, quitEarlyArr: boolean[]
	): DiffChange[] {
		let forwardChanges: DiffChange[] | null = null;
		let reverseChanges: DiffChange[] | null = null;

		// First, walk backward through the forward diagonals history
		let changeHelper = new DiffChangeHelper();
		let diagonalMin = diagonalForwardStart;
		let diagonalMax = diagonalForwardEnd;
		let diagonalRelative = (midOriginalArr[0] - midModifiedArr[0]) - diagonalForwardOffset;
		let lastOriginalIndex = Constants.MIN_SAFE_SMALL_INTEGER;
		let historyIndex = this.m_forwardHistory.length - 1;

		do {
			// Get the diagonal index from the relative diagonal number
			const diagonal = diagonalRelative + diagonalForwardBase;

			// Figure out where we came from
			if (diagonal === diagonalMin || (diagonal < diagonalMax && forwardPoints[diagonal - 1] < forwardPoints[diagonal + 1])) {
				// Vertical line (the element is an insert)
				originalIndex = forwardPoints[diagonal + 1];
				modifiedIndex = originalIndex - diagonalRelative - diagonalForwardOffset;
				if (originalIndex < lastOriginalIndex) {
					changeHelper.MarkNextChange();
				}
				lastOriginalIndex = originalIndex;
				changeHelper.AddModifiedElement(originalIndex + 1, modifiedIndex);
				diagonalRelative = (diagonal + 1) - diagonalForwardBase; //Setup for the next iteration
			} else {
				// Horizontal line (the element is a deletion)
				originalIndex = forwardPoints[diagonal - 1] + 1;
				modifiedIndex = originalIndex - diagonalRelative - diagonalForwardOffset;
				if (originalIndex < lastOriginalIndex) {
					changeHelper.MarkNextChange();
				}
				lastOriginalIndex = originalIndex - 1;
				changeHelper.AddOriginalElement(originalIndex, modifiedIndex + 1);
				diagonalRelative = (diagonal - 1) - diagonalForwardBase; //Setup for the next iteration
			}

			if (historyIndex >= 0) {
				forwardPoints = this.m_forwardHistory[historyIndex];
				diagonalForwardBase = forwardPoints[0]; //We stored this in the first spot
				diagonalMin = 1;
				diagonalMax = forwardPoints.length - 1;
			}
		} while (--historyIndex >= -1);

		// Ironically, we get the forward changes as the reverse of the
		// order we added them since we technically added them backwards
		forwardChanges = changeHelper.getReverseChanges();

		if (quitEarlyArr[0]) {
			// TODO: Calculate a partial from the reverse diagonals.
			//       For now, just assume everything after the midOriginal/midModified point is a diff

			let originalStartPoint = midOriginalArr[0] + 1;
			let modifiedStartPoint = midModifiedArr[0] + 1;

			if (forwardChanges !== null && forwardChanges.length > 0) {
				const lastForwardChange = forwardChanges[forwardChanges.length - 1];
				originalStartPoint = Math.max(originalStartPoint, lastForwardChange.getOriginalEnd());
				modifiedStartPoint = Math.max(modifiedStartPoint, lastForwardChange.getModifiedEnd());
			}

			reverseChanges = [
				new DiffChange(originalStartPoint, originalEnd - originalStartPoint + 1,
					modifiedStartPoint, modifiedEnd - modifiedStartPoint + 1)
			];
		} else {
			// Now walk backward through the reverse diagonals history
			changeHelper = new DiffChangeHelper();
			diagonalMin = diagonalReverseStart;
			diagonalMax = diagonalReverseEnd;
			diagonalRelative = (midOriginalArr[0] - midModifiedArr[0]) - diagonalReverseOffset;
			lastOriginalIndex = Constants.MAX_SAFE_SMALL_INTEGER;
			historyIndex = (deltaIsEven) ? this.m_reverseHistory.length - 1 : this.m_reverseHistory.length - 2;

			do {
				// Get the diagonal index from the relative diagonal number
				const diagonal = diagonalRelative + diagonalReverseBase;

				// Figure out where we came from
				if (diagonal === diagonalMin || (diagonal < diagonalMax && reversePoints[diagonal - 1] >= reversePoints[diagonal + 1])) {
					// Horizontal line (the element is a deletion))
					originalIndex = reversePoints[diagonal + 1] - 1;
					modifiedIndex = originalIndex - diagonalRelative - diagonalReverseOffset;
					if (originalIndex > lastOriginalIndex) {
						changeHelper.MarkNextChange();
					}
					lastOriginalIndex = originalIndex + 1;
					changeHelper.AddOriginalElement(originalIndex + 1, modifiedIndex + 1);
					diagonalRelative = (diagonal + 1) - diagonalReverseBase; //Setup for the next iteration
				} else {
					// Vertical line (the element is an insertion)
					originalIndex = reversePoints[diagonal - 1];
					modifiedIndex = originalIndex - diagonalRelative - diagonalReverseOffset;
					if (originalIndex > lastOriginalIndex) {
						changeHelper.MarkNextChange();
					}
					lastOriginalIndex = originalIndex;
					changeHelper.AddModifiedElement(originalIndex + 1, modifiedIndex + 1);
					diagonalRelative = (diagonal - 1) - diagonalReverseBase; //Setup for the next iteration
				}

				if (historyIndex >= 0) {
					reversePoints = this.m_reverseHistory[historyIndex];
					diagonalReverseBase = reversePoints[0]; //We stored this in the first spot
					diagonalMin = 1;
					diagonalMax = reversePoints.length - 1;
				}
			} while (--historyIndex >= -1);

			// There are cases where the reverse history will find diffs that
			// are correct, but not intuitive, so we need shift them.
			reverseChanges = changeHelper.getChanges();
		}

		return this.ConcatenateChanges(forwardChanges, reverseChanges);
	}