in server/src/diff.ts [612:846]
private ComputeRecursionPoint(originalStart: number, originalEnd: number, modifiedStart: number, modifiedEnd: number, midOriginalArr: number[], midModifiedArr: number[], quitEarlyArr: boolean[]) {
let originalIndex = 0, modifiedIndex = 0;
let diagonalForwardStart = 0, diagonalForwardEnd = 0;
let diagonalReverseStart = 0, diagonalReverseEnd = 0;
// To traverse the edit graph and produce the proper LCS, our actual
// start position is just outside the given boundary
originalStart--;
modifiedStart--;
// We set these up to make the compiler happy, but they will
// be replaced before we return with the actual recursion point
midOriginalArr[0] = 0;
midModifiedArr[0] = 0;
// Clear out the history
this.m_forwardHistory = [];
this.m_reverseHistory = [];
// Each cell in the two arrays corresponds to a diagonal in the edit graph.
// The integer value in the cell represents the originalIndex of the furthest
// reaching point found so far that ends in that diagonal.
// The modifiedIndex can be computed mathematically from the originalIndex and the diagonal number.
const maxDifferences = (originalEnd - originalStart) + (modifiedEnd - modifiedStart);
const numDiagonals = maxDifferences + 1;
const forwardPoints = new Int32Array(numDiagonals);
const reversePoints = new Int32Array(numDiagonals);
// diagonalForwardBase: Index into forwardPoints of the diagonal which passes through (originalStart, modifiedStart)
// diagonalReverseBase: Index into reversePoints of the diagonal which passes through (originalEnd, modifiedEnd)
const diagonalForwardBase = (modifiedEnd - modifiedStart);
const diagonalReverseBase = (originalEnd - originalStart);
// diagonalForwardOffset: Geometric offset which allows modifiedIndex to be computed from originalIndex and the
// diagonal number (relative to diagonalForwardBase)
// diagonalReverseOffset: Geometric offset which allows modifiedIndex to be computed from originalIndex and the
// diagonal number (relative to diagonalReverseBase)
const diagonalForwardOffset = (originalStart - modifiedStart);
const diagonalReverseOffset = (originalEnd - modifiedEnd);
// delta: The difference between the end diagonal and the start diagonal. This is used to relate diagonal numbers
// relative to the start diagonal with diagonal numbers relative to the end diagonal.
// The Even/Oddn-ness of this delta is important for determining when we should check for overlap
const delta = diagonalReverseBase - diagonalForwardBase;
const deltaIsEven = (delta % 2 === 0);
// Here we set up the start and end points as the furthest points found so far
// in both the forward and reverse directions, respectively
forwardPoints[diagonalForwardBase] = originalStart;
reversePoints[diagonalReverseBase] = originalEnd;
// Remember if we quit early, and thus need to do a best-effort result instead of a real result.
quitEarlyArr[0] = false;
// A couple of points:
// --With this method, we iterate on the number of differences between the two sequences.
// The more differences there actually are, the longer this will take.
// --Also, as the number of differences increases, we have to search on diagonals further
// away from the reference diagonal (which is diagonalForwardBase for forward, diagonalReverseBase for reverse).
// --We extend on even diagonals (relative to the reference diagonal) only when numDifferences
// is even and odd diagonals only when numDifferences is odd.
for (let numDifferences = 1; numDifferences <= (maxDifferences / 2) + 1; numDifferences++) {
let furthestOriginalIndex = 0;
let furthestModifiedIndex = 0;
// Run the algorithm in the forward direction
diagonalForwardStart = this.ClipDiagonalBound(diagonalForwardBase - numDifferences, numDifferences, diagonalForwardBase, numDiagonals);
diagonalForwardEnd = this.ClipDiagonalBound(diagonalForwardBase + numDifferences, numDifferences, diagonalForwardBase, numDiagonals);
for (let diagonal = diagonalForwardStart; diagonal <= diagonalForwardEnd; diagonal += 2) {
// STEP 1: We extend the furthest reaching point in the present diagonal
// by looking at the diagonals above and below and picking the one whose point
// is further away from the start point (originalStart, modifiedStart)
if (diagonal === diagonalForwardStart || (diagonal < diagonalForwardEnd && forwardPoints[diagonal - 1] < forwardPoints[diagonal + 1])) {
originalIndex = forwardPoints[diagonal + 1];
} else {
originalIndex = forwardPoints[diagonal - 1] + 1;
}
modifiedIndex = originalIndex - (diagonal - diagonalForwardBase) - diagonalForwardOffset;
// Save the current originalIndex so we can test for false overlap in step 3
const tempOriginalIndex = originalIndex;
// STEP 2: We can continue to extend the furthest reaching point in the present diagonal
// so long as the elements are equal.
while (originalIndex < originalEnd && modifiedIndex < modifiedEnd && this.ElementsAreEqual(originalIndex + 1, modifiedIndex + 1)) {
originalIndex++;
modifiedIndex++;
}
forwardPoints[diagonal] = originalIndex;
if (originalIndex + modifiedIndex > furthestOriginalIndex + furthestModifiedIndex) {
furthestOriginalIndex = originalIndex;
furthestModifiedIndex = modifiedIndex;
}
// STEP 3: If delta is odd (overlap first happens on forward when delta is odd)
// and diagonal is in the range of reverse diagonals computed for numDifferences-1
// (the previous iteration; we haven't computed reverse diagonals for numDifferences yet)
// then check for overlap.
if (!deltaIsEven && Math.abs(diagonal - diagonalReverseBase) <= (numDifferences - 1)) {
if (originalIndex >= reversePoints[diagonal]) {
midOriginalArr[0] = originalIndex;
midModifiedArr[0] = modifiedIndex;
if (tempOriginalIndex <= reversePoints[diagonal] && LocalConstants.MaxDifferencesHistory > 0 && numDifferences <= (LocalConstants.MaxDifferencesHistory + 1)) {
// BINGO! We overlapped, and we have the full trace in memory!
return this.WALKTRACE(diagonalForwardBase, diagonalForwardStart, diagonalForwardEnd, diagonalForwardOffset,
diagonalReverseBase, diagonalReverseStart, diagonalReverseEnd, diagonalReverseOffset,
forwardPoints, reversePoints,
originalIndex, originalEnd, midOriginalArr,
modifiedIndex, modifiedEnd, midModifiedArr,
deltaIsEven, quitEarlyArr
);
} else {
// Either false overlap, or we didn't have enough memory for the full trace
// Just return the recursion point
return null;
}
}
}
}
// Check to see if we should be quitting early, before moving on to the next iteration.
const matchLengthOfLongest = ((furthestOriginalIndex - originalStart) + (furthestModifiedIndex - modifiedStart) - numDifferences) / 2;
if (this.ContinueProcessingPredicate !== null && !this.ContinueProcessingPredicate(furthestOriginalIndex, matchLengthOfLongest)) {
// We can't finish, so skip ahead to generating a result from what we have.
quitEarlyArr[0] = true;
// Use the furthest distance we got in the forward direction.
midOriginalArr[0] = furthestOriginalIndex;
midModifiedArr[0] = furthestModifiedIndex;
if (matchLengthOfLongest > 0 && LocalConstants.MaxDifferencesHistory > 0 && numDifferences <= (LocalConstants.MaxDifferencesHistory + 1)) {
// Enough of the history is in memory to walk it backwards
return this.WALKTRACE(diagonalForwardBase, diagonalForwardStart, diagonalForwardEnd, diagonalForwardOffset,
diagonalReverseBase, diagonalReverseStart, diagonalReverseEnd, diagonalReverseOffset,
forwardPoints, reversePoints,
originalIndex, originalEnd, midOriginalArr,
modifiedIndex, modifiedEnd, midModifiedArr,
deltaIsEven, quitEarlyArr
);
} else {
// We didn't actually remember enough of the history.
//Since we are quitting the diff early, we need to shift back the originalStart and modified start
//back into the boundary limits since we decremented their value above beyond the boundary limit.
originalStart++;
modifiedStart++;
return [
new DiffChange(originalStart, originalEnd - originalStart + 1,
modifiedStart, modifiedEnd - modifiedStart + 1)
];
}
}
// Run the algorithm in the reverse direction
diagonalReverseStart = this.ClipDiagonalBound(diagonalReverseBase - numDifferences, numDifferences, diagonalReverseBase, numDiagonals);
diagonalReverseEnd = this.ClipDiagonalBound(diagonalReverseBase + numDifferences, numDifferences, diagonalReverseBase, numDiagonals);
for (let diagonal = diagonalReverseStart; diagonal <= diagonalReverseEnd; diagonal += 2) {
// STEP 1: We extend the furthest reaching point in the present diagonal
// by looking at the diagonals above and below and picking the one whose point
// is further away from the start point (originalEnd, modifiedEnd)
if (diagonal === diagonalReverseStart || (diagonal < diagonalReverseEnd && reversePoints[diagonal - 1] >= reversePoints[diagonal + 1])) {
originalIndex = reversePoints[diagonal + 1] - 1;
} else {
originalIndex = reversePoints[diagonal - 1];
}
modifiedIndex = originalIndex - (diagonal - diagonalReverseBase) - diagonalReverseOffset;
// Save the current originalIndex so we can test for false overlap
const tempOriginalIndex = originalIndex;
// STEP 2: We can continue to extend the furthest reaching point in the present diagonal
// as long as the elements are equal.
while (originalIndex > originalStart && modifiedIndex > modifiedStart && this.ElementsAreEqual(originalIndex, modifiedIndex)) {
originalIndex--;
modifiedIndex--;
}
reversePoints[diagonal] = originalIndex;
// STEP 4: If delta is even (overlap first happens on reverse when delta is even)
// and diagonal is in the range of forward diagonals computed for numDifferences
// then check for overlap.
if (deltaIsEven && Math.abs(diagonal - diagonalForwardBase) <= numDifferences) {
if (originalIndex <= forwardPoints[diagonal]) {
midOriginalArr[0] = originalIndex;
midModifiedArr[0] = modifiedIndex;
if (tempOriginalIndex >= forwardPoints[diagonal] && LocalConstants.MaxDifferencesHistory > 0 && numDifferences <= (LocalConstants.MaxDifferencesHistory + 1)) {
// BINGO! We overlapped, and we have the full trace in memory!
return this.WALKTRACE(diagonalForwardBase, diagonalForwardStart, diagonalForwardEnd, diagonalForwardOffset,
diagonalReverseBase, diagonalReverseStart, diagonalReverseEnd, diagonalReverseOffset,
forwardPoints, reversePoints,
originalIndex, originalEnd, midOriginalArr,
modifiedIndex, modifiedEnd, midModifiedArr,
deltaIsEven, quitEarlyArr
);
} else {
// Either false overlap, or we didn't have enough memory for the full trace
// Just return the recursion point
return null;
}
}
}
}
// Save current vectors to history before the next iteration
if (numDifferences <= LocalConstants.MaxDifferencesHistory) {
// We are allocating space for one extra int, which we fill with
// the index of the diagonal base index
let temp = new Int32Array(diagonalForwardEnd - diagonalForwardStart + 2);
temp[0] = diagonalForwardBase - diagonalForwardStart + 1;
MyArray.Copy2(forwardPoints, diagonalForwardStart, temp, 1, diagonalForwardEnd - diagonalForwardStart + 1);
this.m_forwardHistory.push(temp);
temp = new Int32Array(diagonalReverseEnd - diagonalReverseStart + 2);
temp[0] = diagonalReverseBase - diagonalReverseStart + 1;
MyArray.Copy2(reversePoints, diagonalReverseStart, temp, 1, diagonalReverseEnd - diagonalReverseStart + 1);
this.m_reverseHistory.push(temp);
}
}
// If we got here, then we have the full trace in history. We just have to convert it to a change list
// NOTE: This part is a bit messy
return this.WALKTRACE(diagonalForwardBase, diagonalForwardStart, diagonalForwardEnd, diagonalForwardOffset,
diagonalReverseBase, diagonalReverseStart, diagonalReverseEnd, diagonalReverseOffset,
forwardPoints, reversePoints,
originalIndex, originalEnd, midOriginalArr,
modifiedIndex, modifiedEnd, midModifiedArr,
deltaIsEven, quitEarlyArr
);
}