chadtmiller.com/pds.js
An atproto PDS in JavaScript, for Cloudflare Workers and Node
0
0
import { describe, expect, it } from 'vitest';
import { encodeTree, mergeText, mergeTrees } from '../src/merge3.js';
import { objectId, parseTree } from '../src/objects.js';
const encoder = new TextEncoder();
const decoder = new TextDecoder();
describe('mergeText', () => {
const base = 'one\ntwo\nthree\nfour\nfive\n';
it('takes the one side that changed, whichever it is', () => {
const ours = 'one\nTWO\nthree\nfour\nfive\n';
expect(mergeText(base, ours, base)).toEqual({ text: ours, conflicts: 0 });
expect(mergeText(base, base, ours)).toEqual({ text: ours, conflicts: 0 });
expect(mergeText(base, ours, ours)).toEqual({ text: ours, conflicts: 0 });
});
it('puts changes to different regions together', () => {
const ours = 'ONE\ntwo\nthree\nfour\nfive\n';
const theirs = 'one\ntwo\nthree\nfour\nFIVE\n';
expect(mergeText(base, ours, theirs)).toEqual({
text: 'ONE\ntwo\nthree\nfour\nFIVE\n',
conflicts: 0,
});
});
it('keeps an insertion on one side beside a change on the other', () => {
const ours = 'one\ntwo\nthree\nfour\nfive\nsix\n';
const theirs = 'one\ntwo\nTHREE\nfour\nfive\n';
expect(mergeText(base, ours, theirs)).toEqual({
text: 'one\ntwo\nTHREE\nfour\nfive\nsix\n',
conflicts: 0,
});
});
it('keeps a deletion on one side beside a change elsewhere', () => {
const ours = 'two\nthree\nfour\nfive\n';
const theirs = 'one\ntwo\nthree\nfour\nFIVE\n';
expect(mergeText(base, ours, theirs)).toEqual({
text: 'two\nthree\nfour\nFIVE\n',
conflicts: 0,
});
});
it('marks the region both sides changed differently, and only that', () => {
const ours = 'one\nTWO\nthree\nfour\nfive\n';
const theirs = 'one\ndos\nthree\nfour\nfive\n';
const answer = mergeText(base, ours, theirs, {
ours: 'main',
theirs: 'agent/plural',
});
expect(answer.conflicts).toBe(1);
expect(answer.text).toBe(
[
'one',
'<<<<<<< main',
'TWO',
'=======',
'dos',
'>>>>>>> agent/plural',
'three',
'four',
'five',
'',
].join('\n'),
);
});
it('counts each disagreeing region once', () => {
const ours = 'ONE\ntwo\nthree\nfour\nFIVE\n';
const theirs = 'uno\ntwo\nthree\nfour\ncinco\n';
expect(mergeText(base, ours, theirs).conflicts).toBe(2);
});
it('reads a last line with no newline as a different line, as git does', () => {
// Adding a line after `b` rewrites `b` itself, since the newline is
// part of the line; that change touches the one beside it, and git
// merge-file answers a conflict here too.
expect(mergeText('a\nb', 'a\nb\nc', 'A\nb').conflicts).toBe(1);
expect(mergeText('a\nb\n', 'a\nb\nc\n', 'A\nb\n')).toEqual({
text: 'A\nb\nc\n',
conflicts: 0,
});
});
it('merges an empty base as two insertions', () => {
expect(mergeText('', 'a\n', 'a\n')).toEqual({ text: 'a\n', conflicts: 0 });
expect(mergeText('', 'a\n', 'b\n').conflicts).toBe(1);
});
});
/**
* @param {string} type @param {Uint8Array} data
*/
const object = (type, data) => ({ type, data, sha: objectId(type, data) });
/** @param {string} text */
const blob = (text) => object('blob', encoder.encode(text));
/**
* @param {Record<string, {sha: string, dir?: boolean}>} files
*/
const tree = (files) => {
const data = encodeTree(
Object.entries(files).map(([name, entry]) => ({
mode: entry.dir ? '40000' : '100644',
name,
sha: entry.sha,
type: entry.dir ? 'dir' : 'file',
})),
);
return object('tree', data);
};
/** @param {Array<{sha: string, type: string, data: Uint8Array}>} objects */
const storeOf = (objects) => {
const held = new Map(objects.map((one) => [one.sha, one]));
return { get: async (/** @type {string} */ sha) => held.get(sha) ?? null };
};
describe('encodeTree', () => {
it('orders a directory as if its name ended in a slash', () => {
const a = blob('a');
const data = encodeTree([
{ mode: '100644', name: 'src.txt', sha: a.sha, type: 'file' },
{ mode: '40000', name: 'src', sha: a.sha, type: 'dir' },
{ mode: '100644', name: 'src-old', sha: a.sha, type: 'file' },
]);
expect(parseTree(data).map((entry) => entry.name)).toEqual([
'src-old',
'src.txt',
'src',
]);
});
});
describe('mergeTrees', () => {
const readme = blob('# Demo\n');
const count = blob('export const count = 1;\n');
const baseTree = tree({ 'README.md': readme, 'count.js': count });
it('answers the same tree where nothing changed on either side', async () => {
const store = storeOf([readme, count, baseTree]);
const answer = await mergeTrees(
store,
baseTree.sha,
baseTree.sha,
baseTree.sha,
);
expect(answer.sha).toBe(baseTree.sha);
expect(answer.objects.size).toBe(0);
expect(answer.conflicts).toEqual([]);
});
it('takes each side where they changed different files, as one new tree', async () => {
const notes = blob('notes\n');
const counted = blob('export const count = 2;\n');
const ours = tree({
'README.md': readme,
'count.js': count,
'NOTES.md': notes,
});
const theirs = tree({ 'README.md': readme, 'count.js': counted });
const store = storeOf([
readme,
count,
notes,
counted,
baseTree,
ours,
theirs,
]);
const answer = await mergeTrees(store, baseTree.sha, ours.sha, theirs.sha);
expect(answer.conflicts).toEqual([]);
const merged = /** @type {{data: Uint8Array}} */ (
answer.objects.get(answer.sha)
);
expect(
parseTree(merged.data).map((entry) => [entry.name, entry.sha]),
).toEqual([
['NOTES.md', notes.sha],
['README.md', readme.sha],
['count.js', counted.sha],
]);
});
it('merges a file both sides changed in different places, as a new blob', async () => {
const base = blob('a\nb\nc\n');
const ours = blob('A\nb\nc\n');
const theirs = blob('a\nb\nC\n');
const bT = tree({ 'f.txt': base });
const oT = tree({ 'f.txt': ours });
const tT = tree({ 'f.txt': theirs });
const store = storeOf([base, ours, theirs, bT, oT, tT]);
const answer = await mergeTrees(store, bT.sha, oT.sha, tT.sha);
expect(answer.conflicts).toEqual([]);
const entry = parseTree(
/** @type {{data: Uint8Array}} */ (answer.objects.get(answer.sha)).data,
)[0];
const mergedBlob = /** @type {{data: Uint8Array}} */ (
answer.objects.get(entry.sha)
);
expect(decoder.decode(mergedBlob.data)).toBe('A\nb\nC\n');
});
it('names the path both sides changed the same way differently', async () => {
const base = blob('a\nb\n');
const ours = blob('A\nb\n');
const theirs = blob('x\nb\n');
const bT = tree({ 'f.txt': base });
const oT = tree({ 'f.txt': ours });
const tT = tree({ 'f.txt': theirs });
const store = storeOf([base, ours, theirs, bT, oT, tT]);
const answer = await mergeTrees(store, bT.sha, oT.sha, tT.sha);
expect(answer.conflicts).toEqual(['f.txt']);
});
it('names a file one side deleted and the other changed, with its directory', async () => {
const base = blob('a\n');
const changed = blob('b\n');
const bInner = tree({ 'f.txt': base });
const oInner = tree({ 'f.txt': changed });
const bT = tree({ src: { sha: bInner.sha, dir: true } });
const oT = tree({ src: { sha: oInner.sha, dir: true } });
const tT = tree({});
const store = storeOf([base, changed, bInner, oInner, bT, oT, tT]);
const answer = await mergeTrees(store, bT.sha, oT.sha, tT.sha);
expect(answer.conflicts).toEqual(['src']);
});
it('descends into a directory both sides changed and names the path inside', async () => {
const base = blob('a\nb\n');
const ours = blob('A\nb\n');
const theirs = blob('x\nb\n');
const bInner = tree({ 'f.txt': base });
const oInner = tree({ 'f.txt': ours });
const tInner = tree({ 'f.txt': theirs });
const bT = tree({ src: { sha: bInner.sha, dir: true } });
const oT = tree({ src: { sha: oInner.sha, dir: true } });
const tT = tree({ src: { sha: tInner.sha, dir: true } });
const store = storeOf([
base,
ours,
theirs,
bInner,
oInner,
tInner,
bT,
oT,
tT,
]);
const answer = await mergeTrees(store, bT.sha, oT.sha, tT.sha);
expect(answer.conflicts).toEqual(['src/f.txt']);
});
it('treats bytes it cannot read as text as a conflict when both sides changed them', async () => {
const base = object('blob', Uint8Array.from([0, 1, 2]));
const ours = object('blob', Uint8Array.from([0, 1, 3]));
const theirs = object('blob', Uint8Array.from([0, 1, 4]));
const bT = tree({ 'img.bin': base });
const oT = tree({ 'img.bin': ours });
const tT = tree({ 'img.bin': theirs });
const store = storeOf([base, ours, theirs, bT, oT, tT]);
expect((await mergeTrees(store, bT.sha, oT.sha, tT.sha)).conflicts).toEqual(
['img.bin'],
);
});
});