Spaces:
Paused
Paused
File size: 2,023 Bytes
f55c62a | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | export interface LineDiff {
type: 'same' | 'add' | 'remove';
content: string;
oldLineNumber?: number;
newLineNumber?: number;
truncated?: boolean;
}
export function calculateLineDiff(
oldText: string,
newText: string
): LineDiff[] {
const oldLines = oldText.split('\n');
const newLines = newText.split('\n');
// Safety check
if (oldLines.length * newLines.length > 2500000) {
// 1500 x 1500 lines
return [
{
type: 'remove',
content: `[Content too large to diff: ${oldLines.length} lines]`,
oldLineNumber: 1,
truncated: true,
},
{
type: 'add',
content: `[Content too large to diff: ${newLines.length} lines]`,
newLineNumber: 1,
truncated: true,
},
];
}
return computeDiff(oldLines, newLines);
}
function computeDiff(oldLines: string[], newLines: string[]): LineDiff[] {
const N = oldLines.length;
const M = newLines.length;
const dp: number[][] = Array(N + 1)
.fill(0)
.map(() => Array(M + 1).fill(0));
for (let i = 1; i <= N; i++) {
for (let j = 1; j <= M; j++) {
if (oldLines[i - 1] === newLines[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
const diff: LineDiff[] = [];
let i = N;
let j = M;
while (i > 0 || j > 0) {
if (i > 0 && j > 0 && oldLines[i - 1] === newLines[j - 1]) {
diff.push({
type: 'same',
content: oldLines[i - 1],
oldLineNumber: i,
newLineNumber: j,
});
i--;
j--;
} else if (j > 0 && (i === 0 || dp[i][j - 1] >= dp[i - 1][j])) {
diff.push({
type: 'add',
content: newLines[j - 1],
newLineNumber: j,
});
j--;
} else if (i > 0 && (j === 0 || dp[i][j - 1] < dp[i - 1][j])) {
diff.push({
type: 'remove',
content: oldLines[i - 1],
oldLineNumber: i,
});
i--;
}
}
return diff.reverse();
}
|