chadtmiller.com/pds.js
An atproto PDS in JavaScript, for Cloudflare Workers and Node
0
0
/**
* Line diffing for the repository browser: two texts in, unified-diff hunks
* out. Myers' greedy algorithm walks the edit graph, so the work scales with
* the size of the change rather than the size of the file.
*
* Workers-clean: strings and typed arrays only.
*/
/** Lines of context around each change, matching git's default. */
const CONTEXT = 3;
/**
* Edit-distance ceiling. Myers costs O((n+m)·d), so a file rewritten end to
* end is the expensive case. Past this the caller reports the change without
* hunks rather than stalling the page.
*/
const MAX_EDITS = 2000;
/**
* @typedef {Object} DiffLine
* @property {'context'|'add'|'delete'} type
* @property {string} text
* @property {number|null} oldLine - 1-based line number before the change
* @property {number|null} newLine - 1-based line number after the change
*/
/**
* @typedef {Object} DiffHunk
* @property {number} oldStart
* @property {number} oldLines
* @property {number} newStart
* @property {number} newLines
* @property {DiffLine[]} lines
*/
/**
* Split a text into lines for diffing. A trailing newline ends the last line
* rather than starting an empty one, so a commit that only adds or removes a
* final newline reports no hunks. git marks that case with
* "\ No newline at end of file".
* @param {string} text
* @returns {string[]}
*/
export function splitLines(text) {
if (text === '') return [];
const lines = text.split('\n');
if (lines[lines.length - 1] === '') lines.pop();
return lines;
}
/**
* The edit script between two line arrays, as an ordered list of operations.
*
* @param {string[]} before
* @param {string[]} after
* @param {number} maxEdits
* @returns {Array<{type: 'context'|'add'|'delete', text: string}>|null} null
* when the edit distance passes maxEdits
*/
function editScript(before, after, maxEdits) {
const n = before.length;
const m = after.length;
const max = Math.min(n + m, maxEdits);
const offset = max;
const v = new Int32Array(2 * max + 2);
/** V at the start of each round, which the backtrack walks in reverse. */
const trace = [];
for (let d = 0; d <= max; d++) {
trace.push(v.slice());
for (let k = -d; k <= d; k += 2) {
// Extend the furthest-reaching path on the neighbouring diagonal: down
// when it reaches further, right otherwise.
const down =
k === -d || (k !== d && v[offset + k - 1] < v[offset + k + 1]);
let x = down ? v[offset + k + 1] : v[offset + k - 1] + 1;
let y = x - k;
while (x < n && y < m && before[x] === after[y]) {
x++;
y++;
}
v[offset + k] = x;
if (x >= n && y >= m) return backtrack(trace, before, after, d, offset);
}
}
return null;
}
/**
* Walk the recorded traces back from the end point, emitting the operations
* in reverse and then reversing them.
*
* @param {Int32Array[]} trace
* @param {string[]} before
* @param {string[]} after
* @param {number} depth
* @param {number} offset
* @returns {Array<{type: 'context'|'add'|'delete', text: string}>}
*/
function backtrack(trace, before, after, depth, offset) {
/** @type {Array<{type: 'context'|'add'|'delete', text: string}>} */
const ops = [];
let x = before.length;
let y = after.length;
for (let d = depth; d > 0; d--) {
const v = trace[d];
const k = x - y;
const down = k === -d || (k !== d && v[offset + k - 1] < v[offset + k + 1]);
const previousK = down ? k + 1 : k - 1;
const previousX = v[offset + previousK];
const previousY = previousX - previousK;
while (x > previousX && y > previousY) {
x--;
y--;
ops.push({ type: 'context', text: before[x] });
}
if (x > previousX) {
x--;
ops.push({ type: 'delete', text: before[x] });
} else {
y--;
ops.push({ type: 'add', text: after[y] });
}
}
while (x > 0 && y > 0) {
x--;
y--;
ops.push({ type: 'context', text: before[x] });
}
return ops.reverse();
}
// ---- compaction ----
//
// Myers reports one edit script, but a change surrounded by lines identical
// to its own can sit at several positions for the same cost. Inserting a doc
// comment into a file full of them is the everyday case. The pass below is
// git's xdl_change_compact: slide each group of changed lines to the extreme
// of its freedom, then place it where the surrounding indentation reads
// best. Its constants and weights come from git's xdiff, so the hunks land
// where a reader comparing against `git show` expects them.
/** Deepest indent that still counts, and the run of blanks that still counts. */
const MAX_INDENT = 200;
const MAX_BLANKS = 20;
/** How much a lower effective indent outweighs the penalties. */
const INDENT_WEIGHT = 60;
/** Cap on positions scored per group, so a huge block stays affordable. */
const MAX_SLIDING = 100;
const START_OF_FILE_PENALTY = 1;
const END_OF_FILE_PENALTY = 21;
const TOTAL_BLANK_WEIGHT = -30;
const POST_BLANK_WEIGHT = 6;
const RELATIVE_INDENT_PENALTY = -4;
const RELATIVE_INDENT_WITH_BLANK_PENALTY = 10;
const RELATIVE_OUTDENT_PENALTY = 24;
const RELATIVE_OUTDENT_WITH_BLANK_PENALTY = 17;
const RELATIVE_DEDENT_PENALTY = 23;
const RELATIVE_DEDENT_WITH_BLANK_PENALTY = 17;
/**
* A line's indent in columns, or -1 when the line is blank. A tab advances to
* the next multiple of eight; other whitespace advances nothing.
* @param {string} line
* @returns {number}
*/
function getIndent(line) {
let indent = 0;
for (const char of line) {
if (char === ' ') indent += 1;
else if (char === '\t') indent += 8 - (indent % 8);
else if (char !== '\r' && char !== '\v' && char !== '\f') return indent;
if (indent >= MAX_INDENT) return MAX_INDENT;
}
return -1;
}
/**
* @typedef {Object} DiffSide
* @property {string[]} lines
* @property {Uint8Array} changed - 1 where the line is part of a change
*/
/**
* What the neighbourhood of a split point looks like, for scoring.
* @param {DiffSide} side
* @param {number} split - index of the line just after the split
*/
function measureSplit(side, split) {
const { lines } = side;
const m = {
endOfFile: split >= lines.length,
indent: split >= lines.length ? -1 : getIndent(lines[split]),
preBlank: 0,
preIndent: -1,
postBlank: 0,
postIndent: -1,
};
for (let i = split - 1; i >= 0; i--) {
m.preIndent = getIndent(lines[i]);
if (m.preIndent !== -1) break;
m.preBlank += 1;
if (m.preBlank === MAX_BLANKS) {
m.preIndent = 0;
break;
}
}
for (let i = split + 1; i < lines.length; i++) {
m.postIndent = getIndent(lines[i]);
if (m.postIndent !== -1) break;
m.postBlank += 1;
if (m.postBlank === MAX_BLANKS) {
m.postIndent = 0;
break;
}
}
return m;
}
/**
* Fold one split's measurement into a running score. Lower is better.
* @param {ReturnType<typeof measureSplit>} m
* @param {{effectiveIndent: number, penalty: number}} score
*/
function scoreAddSplit(m, score) {
if (m.preIndent === -1 && m.preBlank === 0) {
score.penalty += START_OF_FILE_PENALTY;
}
if (m.endOfFile) score.penalty += END_OF_FILE_PENALTY;
const postBlank = m.indent === -1 ? 1 + m.postBlank : 0;
const totalBlank = m.preBlank + postBlank;
score.penalty += TOTAL_BLANK_WEIGHT * totalBlank;
score.penalty += POST_BLANK_WEIGHT * postBlank;
const indent = m.indent !== -1 ? m.indent : m.postIndent;
const anyBlanks = totalBlank !== 0;
score.effectiveIndent += indent;
if (indent === -1 || m.preIndent === -1) return;
if (indent > m.preIndent) {
score.penalty += anyBlanks
? RELATIVE_INDENT_WITH_BLANK_PENALTY
: RELATIVE_INDENT_PENALTY;
} else if (indent < m.preIndent) {
// Indented less than the line before. A line that the next one indents
// under opens a block; otherwise it closes one.
if (m.postIndent !== -1 && m.postIndent > indent) {
score.penalty += anyBlanks
? RELATIVE_OUTDENT_WITH_BLANK_PENALTY
: RELATIVE_OUTDENT_PENALTY;
} else {
score.penalty += anyBlanks
? RELATIVE_DEDENT_WITH_BLANK_PENALTY
: RELATIVE_DEDENT_PENALTY;
}
}
}
/**
* @param {{effectiveIndent: number, penalty: number}} a
* @param {{effectiveIndent: number, penalty: number}} b
*/
function scoreCmp(a, b) {
const indents =
(a.effectiveIndent > b.effectiveIndent ? 1 : 0) -
(a.effectiveIndent < b.effectiveIndent ? 1 : 0);
return INDENT_WEIGHT * indents + (a.penalty - b.penalty);
}
/** @param {DiffSide} side */
function groupInit(side) {
const g = { start: 0, end: 0 };
while (g.end < side.changed.length && side.changed[g.end]) g.end++;
return g;
}
/** @param {DiffSide} side @param {{start: number, end: number}} g */
function groupNext(side, g) {
if (g.end === side.changed.length) return false;
g.start = g.end + 1;
g.end = g.start;
while (g.end < side.changed.length && side.changed[g.end]) g.end++;
return true;
}
/** @param {DiffSide} side @param {{start: number, end: number}} g */
function groupPrevious(side, g) {
if (g.start === 0) return false;
g.end = g.start - 1;
g.start = g.end;
while (g.start > 0 && side.changed[g.start - 1]) g.start--;
return true;
}
/**
* Move a group one line earlier, which is only possible when the line before
* it repeats its last line. Sliding onto the single unchanged line that
* separated this group from the one before it joins the two, so the group
* then absorbs everything still marked ahead of it. Without that step the
* next slide would clear a line the joined group owns, and the change would
* be lost.
* @param {DiffSide} side @param {{start: number, end: number}} g
*/
function slideUp(side, g) {
if (g.start > 0 && side.lines[g.start - 1] === side.lines[g.end - 1]) {
side.changed[--g.start] = 1;
side.changed[--g.end] = 0;
while (g.start > 0 && side.changed[g.start - 1]) g.start--;
return true;
}
return false;
}
/**
* Move a group one line later, absorbing a following group the same way.
* @param {DiffSide} side @param {{start: number, end: number}} g
*/
function slideDown(side, g) {
if (g.end < side.lines.length && side.lines[g.start] === side.lines[g.end]) {
side.changed[g.start++] = 0;
side.changed[g.end++] = 1;
while (g.end < side.changed.length && side.changed[g.end]) g.end++;
return true;
}
return false;
}
/**
* Move every change group on one side to its best position, walking the other
* side in step so a group can prefer to line up with a change over there.
* @param {DiffSide} side - the side being compacted
* @param {DiffSide} other
*/
function compact(side, other) {
const g = groupInit(side);
const go = groupInit(other);
for (;;) {
if (g.end !== g.start) {
let groupSize;
let earliestEnd;
let endMatchingOther;
// Sliding can merge this group with a neighbour, which makes it bigger
// and gives it new freedom. Repeat until the size settles.
do {
groupSize = g.end - g.start;
endMatchingOther = -1;
while (slideUp(side, g)) groupPrevious(other, go);
earliestEnd = g.end;
if (go.end > go.start) endMatchingOther = g.end;
while (slideDown(side, g)) {
groupNext(other, go);
if (go.end > go.start) endMatchingOther = g.end;
}
} while (groupSize !== g.end - g.start);
if (g.end === earliestEnd) {
// The group is pinned; nothing to choose.
} else if (endMatchingOther !== -1) {
// Line the group up with the last change on the other side that it
// can reach, so both files show the change in the same place.
while (go.end === go.start) {
slideUp(side, g);
groupPrevious(other, go);
}
} else {
let shift = Math.max(
earliestEnd,
g.end - groupSize - 1,
g.end - MAX_SLIDING,
);
let bestShift = -1;
let bestScore = { effectiveIndent: 0, penalty: 0 };
for (; shift <= g.end; shift++) {
const score = { effectiveIndent: 0, penalty: 0 };
scoreAddSplit(measureSplit(side, shift), score);
scoreAddSplit(measureSplit(side, shift - groupSize), score);
if (bestShift === -1 || scoreCmp(score, bestScore) <= 0) {
bestScore = score;
bestShift = shift;
}
}
while (g.end > bestShift) {
slideUp(side, g);
groupPrevious(other, go);
}
}
}
if (!groupNext(side, g)) break;
groupNext(other, go);
}
}
/**
* The hunks between two texts, the way `git diff -U3` groups them.
*
* @param {string} beforeText
* @param {string} afterText
* @param {{context?: number, maxEdits?: number}} [options]
* @returns {DiffHunk[]|null} null when the change is too large to diff
*/
export function diffLines(beforeText, afterText, options = {}) {
const context = options.context ?? CONTEXT;
const before = splitLines(beforeText);
const after = splitLines(afterText);
const ops = editScript(before, after, options.maxEdits ?? MAX_EDITS);
if (!ops) return null;
// The edit script says which lines changed. Compaction then decides where
// each run of them sits, so the two sides are tracked as flags rather than
// as the ordered operations Myers emitted.
const beforeSide = {
lines: before,
changed: new Uint8Array(before.length),
};
const afterSide = { lines: after, changed: new Uint8Array(after.length) };
let atBefore = 0;
let atAfter = 0;
for (const op of ops) {
if (op.type === 'context') {
atBefore++;
atAfter++;
} else if (op.type === 'delete') {
beforeSide.changed[atBefore++] = 1;
} else {
afterSide.changed[atAfter++] = 1;
}
}
compact(beforeSide, afterSide);
compact(afterSide, beforeSide);
/** @type {DiffLine[]} */
const lines = [];
let oldLine = 0;
let newLine = 0;
while (oldLine < before.length || newLine < after.length) {
// A group's deletions all print before its additions, the way a unified
// diff reads.
if (oldLine < before.length && beforeSide.changed[oldLine]) {
oldLine++;
lines.push({
type: 'delete',
text: before[oldLine - 1],
oldLine,
newLine: null,
});
} else if (newLine < after.length && afterSide.changed[newLine]) {
newLine++;
lines.push({
type: 'add',
text: after[newLine - 1],
oldLine: null,
newLine,
});
} else {
oldLine++;
newLine++;
lines.push({
type: 'context',
text: before[oldLine - 1],
oldLine,
newLine,
});
}
}
const changed = lines
.map((line, index) => (line.type === 'context' ? -1 : index))
.filter((index) => index >= 0);
if (changed.length === 0) return [];
/** Ranges of lines to show, each a change plus its context. */
/** @type {Array<{from: number, to: number}>} */
const ranges = [];
for (const index of changed) {
const from = Math.max(0, index - context);
const to = Math.min(lines.length - 1, index + context);
const last = ranges[ranges.length - 1];
// Ranges that touch or overlap become one hunk, so the context between
// two nearby changes is not printed twice.
if (last && from <= last.to + 1) last.to = Math.max(last.to, to);
else ranges.push({ from, to });
}
return ranges.map((range) => {
const body = lines.slice(range.from, range.to + 1);
const oldCount = body.filter((line) => line.type !== 'add').length;
const newCount = body.filter((line) => line.type !== 'delete').length;
const firstOld = body.find((line) => line.oldLine !== null);
const firstNew = body.find((line) => line.newLine !== null);
return {
// An empty side starts at 0, which is what git prints for a file that
// gains or loses all of its lines.
oldStart: oldCount === 0 ? 0 : (firstOld?.oldLine ?? 0),
oldLines: oldCount,
newStart: newCount === 0 ? 0 : (firstNew?.newLine ?? 0),
newLines: newCount,
lines: body,
};
});
}