chadtmiller.com/pds.js
An atproto PDS in JavaScript, for Cloudflare Workers and Node
0
0
/**
* The three-way merge: what a pull request's changes and main's changes
* since it branched come to when put together.
*
* Text merges line by line, the way `git merge` does. Each side's changes
* against the base are found, and a region only one side changed takes that
* side. A region both changed the same way takes either. A region they
* changed differently is a conflict, and reads with git's own markers.
*
* A tree merges entry by entry. An entry only one side changed takes that
* side; two blobs both changed merge as text; a change on one side against
* a deletion on the other, or against a different kind of entry, is a
* conflict. A merged tree is a new object where anything under it changed,
* and the same object where nothing did.
*
* Workers-clean: no node imports.
*/
import { objectId, parseTree } from './objects.js';
const encoder = new TextEncoder();
const decoder = new TextDecoder();
/**
* Lines at most a side may have before the merge gives up on a line-level
* answer and treats the file as one region. Past this the table the diff
* builds is the product of two sides, which is more than one file is worth.
*/
const MAX_LINES = 5000;
/**
* @param {string} text
* @returns {string[]} the lines, each with its newline, so joining them
* back gives the text
*/
function lines(text) {
if (text === '') return [];
const found = text.split('\n');
const last = found.pop() ?? '';
const out = found.map((line) => `${line}\n`);
if (last !== '') out.push(last);
return out;
}
/**
* The longest common subsequence of two line lists, as index pairs in
* order.
* @param {string[]} a
* @param {string[]} b
* @returns {Array<[number, number]>}
*/
function matches(a, b) {
const rows = a.length + 1;
const cols = b.length + 1;
const table = new Uint32Array(rows * cols);
for (let i = a.length - 1; i >= 0; i--) {
for (let j = b.length - 1; j >= 0; j--) {
table[i * cols + j] =
a[i] === b[j]
? table[(i + 1) * cols + j + 1] + 1
: Math.max(table[(i + 1) * cols + j], table[i * cols + j + 1]);
}
}
/** @type {Array<[number, number]>} */
const found = [];
let i = 0;
let j = 0;
while (i < a.length && j < b.length) {
if (a[i] === b[j]) {
found.push([i, j]);
i++;
j++;
} else if (table[(i + 1) * cols + j] >= table[i * cols + j + 1]) {
i++;
} else {
j++;
}
}
return found;
}
/**
* @typedef {Object} TextMerge
* @property {string} text - the merged text, with conflict markers where
* the sides disagree
* @property {number} conflicts - how many regions the sides disagree on
*/
/**
* Merge two texts against their common base.
* @param {string} base
* @param {string} ours - main's side, which the markers call HEAD
* @param {string} theirs - the branch's side
* @param {Object} [labels]
* @param {string} [labels.ours]
* @param {string} [labels.theirs]
* @returns {TextMerge}
*/
export function mergeText(base, ours, theirs, labels = {}) {
if (ours === theirs) return { text: ours, conflicts: 0 };
if (ours === base) return { text: theirs, conflicts: 0 };
if (theirs === base) return { text: ours, conflicts: 0 };
const b = lines(base);
const o = lines(ours);
const t = lines(theirs);
if (Math.max(b.length, o.length, t.length) > MAX_LINES) {
return { text: conflict(ours, theirs, labels), conflicts: 1 };
}
// Where each side still has the base's lines, as a map from base index to
// that side's index.
const inOurs = new Map(matches(b, o));
const inTheirs = new Map(matches(b, t));
/** @type {string[]} */
const out = [];
let conflicts = 0;
let bi = 0;
let oi = 0;
let ti = 0;
while (bi < b.length || oi < o.length || ti < t.length) {
// A base line both sides keep is stable: copy it and move all three.
const oAt = inOurs.get(bi);
const tAt = inTheirs.get(bi);
if (
bi < b.length &&
oAt !== undefined &&
tAt !== undefined &&
oAt === oi &&
tAt === ti
) {
out.push(b[bi]);
bi++;
oi++;
ti++;
continue;
}
// Otherwise a changed region runs to the next base line both sides
// keep in step.
let end = bi;
while (end < b.length) {
const oNext = inOurs.get(end);
const tNext = inTheirs.get(end);
if (oNext !== undefined && tNext !== undefined) {
// Both keep it, but a side may have inserted before it; the region
// closes here and the insertion belongs to the region.
break;
}
end++;
}
const oEnd =
end < b.length ? /** @type {number} */ (inOurs.get(end)) : o.length;
const tEnd =
end < b.length ? /** @type {number} */ (inTheirs.get(end)) : t.length;
const baseRegion = b.slice(bi, end).join('');
const ourRegion = o.slice(oi, oEnd).join('');
const theirRegion = t.slice(ti, tEnd).join('');
if (ourRegion === theirRegion) out.push(ourRegion);
else if (ourRegion === baseRegion) out.push(theirRegion);
else if (theirRegion === baseRegion) out.push(ourRegion);
else {
out.push(conflict(ourRegion, theirRegion, labels));
conflicts++;
}
bi = end;
oi = oEnd;
ti = tEnd;
}
return { text: out.join(''), conflicts };
}
/**
* One conflicted region, as git writes it.
* @param {string} ours @param {string} theirs
* @param {{ours?: string, theirs?: string}} labels
*/
function conflict(ours, theirs, labels) {
const ended = (/** @type {string} */ text) =>
text === '' || text.endsWith('\n') ? text : `${text}\n`;
return `<<<<<<< ${labels.ours ?? 'HEAD'}\n${ended(ours)}=======\n${ended(theirs)}>>>>>>> ${labels.theirs ?? 'branch'}\n`;
}
/**
* Whether bytes are text this merge can read. A NUL in the first 8KB says
* binary, the way git decides.
* @param {Uint8Array} bytes
*/
const isBinary = (bytes) => bytes.subarray(0, 8192).includes(0);
/**
* A tree's entries in git's own byte form, in git's own order: by name, a
* directory sorting as if its name ended in a slash.
* @param {import('./objects.js').TreeEntry[]} entries
* @returns {Uint8Array}
*/
export function encodeTree(entries) {
const sorted = [...entries].sort((a, b) => {
const an = a.type === 'dir' ? `${a.name}/` : a.name;
const bn = b.type === 'dir' ? `${b.name}/` : b.name;
return an < bn ? -1 : an > bn ? 1 : 0;
});
/** @type {Uint8Array[]} */
const parts = [];
for (const entry of sorted) {
const head = encoder.encode(`${entry.mode} ${entry.name}\0`);
const raw = Uint8Array.from(
(entry.sha.match(/../g) ?? []).map((pair) => Number.parseInt(pair, 16)),
);
const row = new Uint8Array(head.length + raw.length);
row.set(head, 0);
row.set(raw, head.length);
parts.push(row);
}
const data = new Uint8Array(parts.reduce((n, part) => n + part.length, 0));
let at = 0;
for (const part of parts) {
data.set(part, at);
at += part.length;
}
return data;
}
/**
* @typedef {Object} TreeMerge
* @property {string} sha - the merged tree
* @property {Map<string, {type: string, data: Uint8Array}>} objects - the
* blobs and trees the merge made, by id
* @property {string[]} conflicts - paths the sides disagree on
*/
/**
* @typedef {Object} MergeStore
* @property {(sha: string) => Promise<{type: string, data: Uint8Array}|null>} get
*/
/**
* Merge two trees against their common base.
* @param {MergeStore} store - answers for every object of all three trees
* @param {string|null} base - the base tree, null where the path is new
* @param {string|null} ours
* @param {string|null} theirs
* @param {Object} [options]
* @param {string} [options.path] - where this tree is, for the conflict paths
* @param {{ours?: string, theirs?: string}} [options.labels]
* @returns {Promise<TreeMerge>}
*/
export async function mergeTrees(store, base, ours, theirs, options = {}) {
const at = options.path ?? '';
/** @type {Map<string, {type: string, data: Uint8Array}>} */
const objects = new Map();
/** @type {string[]} */
const conflicts = [];
/** @param {string|null} sha */
const entriesOf = async (sha) => {
if (!sha) return new Map();
const tree = await store.get(sha);
if (!tree || tree.type !== 'tree') return new Map();
return new Map(parseTree(tree.data).map((entry) => [entry.name, entry]));
};
const [b, o, t] = await Promise.all([
entriesOf(base),
entriesOf(ours),
entriesOf(theirs),
]);
/** @type {import('./objects.js').TreeEntry[]} */
const merged = [];
const names = [...new Set([...b.keys(), ...o.keys(), ...t.keys()])];
for (const name of names) {
const path = at ? `${at}/${name}` : name;
const bE = b.get(name) ?? null;
const oE = o.get(name) ?? null;
const tE = t.get(name) ?? null;
const same = (
/** @type {import('./objects.js').TreeEntry|null} */ x,
/** @type {import('./objects.js').TreeEntry|null} */ y,
) =>
(x === null && y === null) || (x?.sha === y?.sha && x?.mode === y?.mode);
if (same(oE, tE)) {
if (oE) merged.push(oE);
continue;
}
if (same(oE, bE)) {
if (tE) merged.push(tE);
continue;
}
if (same(tE, bE)) {
if (oE) merged.push(oE);
continue;
}
// Both sides changed it, differently.
if (!oE || !tE) {
// One side deleted what the other changed.
conflicts.push(path);
merged.push(/** @type {import('./objects.js').TreeEntry} */ (oE ?? tE));
continue;
}
if (oE.type === 'dir' && tE.type === 'dir') {
const inner = await mergeTrees(
store,
bE?.type === 'dir' ? bE.sha : null,
oE.sha,
tE.sha,
{ path, labels: options.labels },
);
for (const [sha, object] of inner.objects) objects.set(sha, object);
conflicts.push(...inner.conflicts);
merged.push({ ...oE, sha: inner.sha });
continue;
}
if (oE.type === 'file' && tE.type === 'file' && oE.mode === tE.mode) {
const [bB, oB, tB] = await Promise.all([
bE?.type === 'file' ? store.get(bE.sha) : null,
store.get(oE.sha),
store.get(tE.sha),
]);
if (oB && tB && !isBinary(oB.data) && !isBinary(tB.data)) {
const answer = mergeText(
bB ? decoder.decode(bB.data) : '',
decoder.decode(oB.data),
decoder.decode(tB.data),
options.labels,
);
if (answer.conflicts > 0) conflicts.push(path);
const data = encoder.encode(answer.text);
const sha = objectId('blob', data);
objects.set(sha, { type: 'blob', data });
merged.push({ ...oE, sha });
continue;
}
}
// Different kinds, different modes, or bytes no merge can read.
conflicts.push(path);
merged.push(oE);
}
const data = encodeTree(merged);
const sha = objectId('tree', data);
if (sha !== ours && sha !== theirs && sha !== base) {
objects.set(sha, { type: 'tree', data });
}
return { sha, objects, conflicts };
}