Visualize Your Ideas With Code
type Subsequence = {
aIndex: number;
bIndex: number;
prev?: Subsequence | undefined;
};
/**
* Performs a patience diff on two arrays of strings, returning an object
* containing the lines that were deleted, inserted, and potentially moved
* lines. The plus parameter can result in a significant performance hit due
* to additional Longest Common Substring searches.
*
* @param aLines - The original array of strings
* @param bLines - The new array of strings
* @param plus - Whether to return the moved lines
*
* Adapted from Jonathan "jonTrent" Trent's patience-diff algorithm.
* Types and tests added by Hunter "hhenrichsen" Henrichsen.
*
* {@link https://github.com/jonTrent/PatienceDiff}
*/
export function patienceDiff(
aLines: string[],
bLines: string[],
): {
lines: {
line: string;
aIndex: number;
bIndex: number;
}[];
lineCountDeleted: number;
lineCountInserted: number;
} {
/**
* Finds all unique values in lines[start...end], inclusive. This
* function is used in preparation for determining the longest common
* subsequence.
*
* @param lines - The array to search
* @param start - The starting index (inclusive)
* @param end - The ending index (inclusive)
* @returns A map of the unique lines to their index
*/
function findUnique(lines: string[], start: number, end: number) {
const lineMap = new Map<string, {count: number; index: number}>();
for (let i = start; i <= end; i++) {
const line = lines[i];
const data = lineMap.get(line);
if (data) {
data.count++;
data.index = i;
} else {
lineMap.set(line, {count: 1, index: i});
}
}
const newMap = new Map<string, number>();
for (const [key, value] of lineMap) {
if (value.count === 1) {
newMap.set(key, value.index);
}
}
return newMap;
}
/**
* Finds all the unique common entries between aArray[aStart...aEnd] and
* bArray[bStart...bEnd], inclusive. This function uses findUnique to pare
* down the aArray and bArray ranges first, before then walking the
* comparison between the two arrays.
*
*
* @param aArray - The original array
* @param aStart - The start of the original array to search
* @param aEnd - The end of the original array to search, inclusive
* @param bArray - The new array
* @param bStart - the start of the new array to search
* @param bEnd - The end of the new array to search, inclusive
* @returns a Map, with the key as the common line between aArray and
* bArray, with the value as an object containing the array indices of the
* matching uniqe lines.
*/
function uniqueCommon(
aArray: string[],
aStart: number,
aEnd: number,
bArray: string[],
bStart: number,
bEnd: number,
): Map<string, Subsequence> {
const aUnique = findUnique(aArray, aStart, aEnd);
const bUnique = findUnique(bArray, bStart, bEnd);
return [...aUnique.entries()].reduce<Map<string, Subsequence>>(
(paired, [key, value]) => {
const bIndex = bUnique.get(key);
if (bIndex !== undefined) {
paired.set(key, {
aIndex: value,
bIndex,
});
}
return paired;
},
new Map(),
);
}
/**
* Takes a map from the unique common lines between two arrays and determines
* the longest common subsequence.
*
* @see uniqueCommon
*
* @param abMap - The map of unique common lines between two arrays.
* @returns An array of objects containing the indices of the longest common
* subsequence.
*/
function longestCommonSubsequence(
abMap: Map<string, Subsequence>,
): Subsequence[] {
const jagged: [Subsequence][] = [];
abMap.forEach(value => {
let i = 0;
while (jagged[i] && jagged[i].at(-1)!.bIndex < value.bIndex) {
i++;
}
if (i > 0) {
value.prev = jagged[i - 1].at(-1);
}
if (!jagged[i]) {
jagged[i] = [value];
} else {
jagged[i].push(value);
}
});
// Pull out the longest common subsequence
let lcs: Subsequence[] = [];
if (jagged.length > 0) {
lcs = [jagged.at(-1)!.at(-1)!];
let cursor = lcs.at(-1);
while (cursor?.prev) {
cursor = cursor.prev;
lcs.push(cursor);
}
}
return lcs.reverse();
}
/**
* Keeps track of the aLines that have been deleted, are shared between aLines
* and bLines, and bLines that have been inserted.
*/
const result: {
line: string;
aIndex: number;
bIndex: number;
moved: boolean;
}[] = [];
let deleted = 0;
let inserted = 0;
function addToResult(aIndex: number, bIndex: number) {
if (bIndex < 0) {
deleted++;
} else if (aIndex < 0) {
inserted++;
}
result.push({
line: 0 <= aIndex ? aLines[aIndex] : bLines[bIndex],
aIndex,
bIndex,
moved: false,
});
}
function addSubMatch(
aStart: number,
aEnd: number,
bStart: number,
bEnd: number,
) {
// Match any lines at the beginning of aLines and bLines.
while (
aStart <= aEnd &&
bStart <= bEnd &&
aLines[aStart] === bLines[bStart]
) {
addToResult(aStart++, bStart++);
}
// Match any lines at the end of aLines and bLines, but don't place them
// in the "result" array just yet, as the lines between these matches at
// the beginning and the end need to be analyzed first.
const aEndTemp = aEnd;
while (aStart <= aEnd && bStart <= bEnd && aLines[aEnd] === bLines[bEnd]) {
aEnd--;
bEnd--;
}
// Now, check to determine with the remaining lines in the subsequence
// whether there are any unique common lines between aLines and bLines.
//
// If not, add the subsequence to the result (all aLines having been
// deleted, and all bLines having been inserted).
//
// If there are unique common lines between aLines and bLines, then let's
// recursively perform the patience diff on the subsequence.
const uniqueCommonMap = uniqueCommon(
aLines,
aStart,
aEnd,
bLines,
bStart,
bEnd,
);
if (uniqueCommonMap.size === 0) {
while (aStart <= aEnd) {
addToResult(aStart++, -1);
}
while (bStart <= bEnd) {
addToResult(-1, bStart++);
}
} else {
recurseLCS(aStart, aEnd, bStart, bEnd, uniqueCommonMap);
}
// Finally, let's add the matches at the end to the result.
while (aEnd < aEndTemp) {
addToResult(++aEnd, ++bEnd);
}
}
/**
* Finds the longest common subsequence between the arrays
* aLines[aStart...aEnd] and bLines[bStart...bEnd], inclusive. Then for each
* subsequence, recursively performs another LCS search (via addSubMatch),
* until there are none found, at which point the subsequence is dumped to
* the result.
*
* @param aStart - The start of the original array to search
* @param aEnd - The end of the original array to search, inclusive
* @param bStart - The start of the new array to search
* @param bEnd - The end of the new array to search, inclusive
* @param uniqueCommonMap - A map of the unique common lines between
* aLines[aStart...aEnd] and bLines[bStart...bEnd], inclusive.
*/
function recurseLCS(
aStart: number,
aEnd: number,
bStart: number,
bEnd: number,
uniqueCommonMap: Map<string, Subsequence> = uniqueCommon(
aLines,
aStart,
aEnd,
bLines,
bStart,
bEnd,
),
) {
const lcs = longestCommonSubsequence(uniqueCommonMap);
if (lcs.length === 0) {
addSubMatch(aStart, aEnd, bStart, bEnd);
} else {
if (aStart < lcs[0].aIndex || bStart < lcs[0].bIndex) {
addSubMatch(aStart, lcs[0].aIndex - 1, bStart, lcs[0].bIndex - 1);
}
let i;
for (i = 0; i < lcs.length - 1; i++) {
addSubMatch(
lcs[i].aIndex,
lcs[i + 1].aIndex - 1,
lcs[i].bIndex,
lcs[i + 1].bIndex - 1,
);
}
if (lcs[i].aIndex <= aEnd || lcs[i].bIndex <= bEnd) {
addSubMatch(lcs[i].aIndex, aEnd, lcs[i].bIndex, bEnd);
}
}
}
recurseLCS(0, aLines.length - 1, 0, bLines.length - 1);
return {
lines: result,
lineCountDeleted: deleted,
lineCountInserted: inserted,
};
}
/**
* Utility function for debugging patienceDiff.
*
* @internal
*/
export function printDiff(diff: ReturnType<typeof patienceDiff>) {
diff.lines.forEach(line => {
if (line.bIndex < 0) {
console.log(`- ${line.line}`);
} else if (line.aIndex < 0) {
console.log(`+ ${line.line}`);
} else {
console.log(` ${line.line}`);
}
});
}