Oregami
Repositories/oxedyne/daimond

oxedyne/daimond/dev/verify_deltalog.mjs

17.9 KiB, 1 run

created by r2519314175:355, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1// verify_deltalog.mjs — crystal version history is a delta log, and every
2// version in it still comes back byte for byte.
3//
4// Until this change every capp page edit wrote a full uncompressed copy of the
5// page into `versions/`, and nothing anywhere prunes them: the shipped Log Life
6// page is 101,834 bytes, so a hundred edits was 10.2 MB against a per-Diamond
7// share of 4 MiB. A version now stores either a full copy — a KEYFRAME — or the
8// splices from the snapshot before it, with one keyframe every twenty.
9//
10// The arithmetic and the chain planning are `src/diamond_delta.rs`'s and are
11// tested natively against that same page; `dev/breakproof_deltalog.sh` proves
12// each of those checks against broken code. What only a browser can reach is the
13// OPFS edge in `src/wasm/diamond.rs` — the directory walk that decides which file
14// is which, the chain read, and the proof `write_snapshot` performs before a
15// version is allowed to stand. That is what this is for.
16//
17// What is pinned:
18// * a run of page edits writes patches, not copies, and no version stands on
19// more than nineteen of them;
20// * every version reads back as the exact bytes it was written as, page and
21// memory both;
22// * the whole history weighs a fraction of what the same history cost before;
23// * A CORRUPTED PATCH IS REFUSED, not silently answered with the keyframe under
24// it — which is the failure this whole encoding exists to prevent, and the
25// one that would otherwise be discovered months later;
26// * a patch DELETED from the middle of a chain is refused the same way;
27// * THE DAMAGE IS BOUNDED BY THE INTERVAL: versions before the break read, and
28// so do versions past the next keyframe;
29// * and the Diamond MENDS — a version whose parent cannot be rebuilt records a
30// full copy, so the history continues rather than ending at the break.
31//
32// Run with dev/serve.mjs (DAIMOND_PORT) up. No gateway, no mock model.
33//
34// node dev/verify_deltalog.mjs
35import { open, clearDiamonds } from './harness.mjs';
36
37const ok = [], bad = [];
38// The store's errors arrive coloured, and a colour code in a verifier's own
39// output is a line nobody can read in a log file.
40const ESC = String.fromCharCode(27);
41const plain = (s) => String(s)
42 .split(ESC).map((x, i) => i ? x.replace(/^\[[0-9;]*m/, '') : x).join('')
43 .replace(/\\u001b\[[0-9;]*m/g, '');
44const check = (name, pass, detail) => {
45 (pass ? ok : bad).push(name);
46 console.log((pass ? ' ok ' : ' FAIL ') + name + (detail ? ' — ' + plain(detail) : ''));
47};
48
49// How many page edits to make. Enough to cross the keyframe interval twice, so
50// a chain is walked in earnest and a keyframe count means something.
51const TURNS = 45;
52const EVERY = 20; // src/diamond_delta.rs KEYFRAME_EVERY
53
54const s = await open({ name: 'deltalog', connect: false, defaults: false });
55const p = s.page;
56await p.waitForTimeout(1500);
57await clearDiamonds(s);
58
59await p.evaluate(async () => {
60 const mod = await import('../pkg/oxedyne_daimond.js');
61 window.__d = {
62 mod,
63 app: new mod.DaimondApp('http://127.0.0.1/v1/chat/completions', '', 'none', 256, '', true),
64 root: await navigator.storage.getDirectory(),
65 };
66 window.__at = async (path) => {
67 let cur = __d.root;
68 for (const part of path.split('/')) cur = await cur.getDirectoryHandle(part);
69 return cur;
70 };
71 window.__dir = async (path) => {
72 const cur = await __at(path);
73 const out = [];
74 for await (const [name, h] of cur.entries()) {
75 if (h.kind !== 'file') continue;
76 out.push({ name, size: (await h.getFile()).size });
77 }
78 return out.sort((a, b) => a.name.localeCompare(b.name));
79 };
80 // The sequence of edits, in one place, so what is written and what it is
81 // compared against cannot drift apart.
82 window.__page0 = async () => (await (await fetch('/capps/lifelog/crystal.html')).text());
83 window.__turn = (page, n) => {
84 const lines = page.split('\n');
85 if (n % 3 === 0) {
86 // A section pasted in, which is what a new lane or a new card is.
87 const at = (n * 71 + 3) % lines.length;
88 const block = ['<section class="lane lane-' + n + '">'];
89 for (let k = 0; k < 6; k++) {
90 block.push(' <div class="row" data-k="' + k + '">entry ' + n + '</div>');
91 }
92 block.push('</section>');
93 lines.splice(at, 0, ...block);
94 } else {
95 // One line changed, which is the commonest turn by far.
96 const at = (n * 37 + 11) % lines.length;
97 lines[at] = lines[at] + ' <!-- ' + n + ' -->';
98 }
99 return lines.join('\n');
100 };
101 window.__data = (n) => JSON.stringify({ title: 'Delta log',
102 lanes: Array.from({ length: n }, (_, k) => ({ k, note: 'lane ' + k + ' as at turn ' + n })) });
103});
104
105// The real page, and a run of edits of the shape a turn makes.
106
107const built = await p.evaluate(async (turns) => {
108 const page0 = await __page0();
109 const id = await __d.app.create_diamond('Delta log');
110 let page = page0, full = 0;
111 // Version 0 is the empty crystal `create_diamond` lays down, so the first
112 // write is version 1 and version N holds turn N - 1.
113 for (let n = 0; n <= turns; n++) {
114 if (n > 0) page = __turn(page, n);
115 await __d.app.write_crystal_both(id, __data(n), page);
116 full += new Blob([page]).size + new Blob([__data(n)]).size;
117 }
118 return { id, bytes: new Blob([page0]).size, full };
119}, TURNS);
120
121check('the fixture is the real shipped Log Life capp page',
122 built.bytes === 101834, String(built.bytes));
123
124const files = await p.evaluate(async (id) => __dir('diamonds/' + id + '/versions'), built.id);
125const count = (ext) => files.filter(f => f.name.endsWith(ext)).length;
126const weight = files.reduce((a, f) => a + f.size, 0);
127
128/// The deepest run of patches standing on one full copy, which is what the
129/// interval is for: it bounds both what one bad splice can invalidate and what
130/// the history view has to read to answer a question about an old version.
131const deepest = (kf, patch) => {
132 const rows = files
133 .map(f => ({ v: parseInt(f.name, 10),
134 kf: f.name.endsWith(kf), pt: f.name.endsWith(patch) }))
135 .filter(r => !isNaN(r.v) && (r.kf || r.pt))
136 .sort((a, b) => a.v - b.v);
137 let run = 0, worst = 0;
138 for (const r of rows) {
139 run = r.kf ? 0 : run + 1;
140 worst = Math.max(worst, run);
141 }
142 return { worst, rows: rows.length };
143};
144
145check('the page is stored as splices, not as a copy per version',
146 count('.hpatch') > TURNS - 5, count('.hpatch') + ' patches, ' + count('.html') + ' full copies');
147check('and the memory beside it is too',
148 count('.jpatch') > TURNS - 8, count('.jpatch') + ' patches, ' + count('.json') + ' full copies');
149
150const pageDeep = deepest('.html', '.hpatch');
151const dataDeep = deepest('.json', '.jpatch');
152check('no page version stands on more than nineteen patches',
153 pageDeep.worst > 0 && pageDeep.worst <= EVERY - 1,
154 pageDeep.worst + ' deep over ' + pageDeep.rows + ' snapshots');
155check('and no memory version does either',
156 dataDeep.worst > 0 && dataDeep.worst <= EVERY - 1,
157 dataDeep.worst + ' deep over ' + dataDeep.rows + ' snapshots');
158check('the interval is really the interval, not a keyframe on everything',
159 pageDeep.worst >= EVERY - 1, String(pageDeep.worst));
160check('the whole history weighs a fraction of what the copies weighed',
161 weight * 4 < built.full,
162 Math.round(weight / 1024) + ' KiB against ' + Math.round(built.full / 1024) + ' KiB');
163
164// What the sync budget is spent against. `collectDiamonds` weighs each Diamond
165// with `export_diamond_size` BEFORE materialising it, and a Diamond that estimate
166// rejects is never built -- so that answer has to hold, and nothing in a browser
167// had ever checked it. The estimate weighed every file as though it travelled
168// base64; most of a Diamond is valid UTF-8 and travels as itself.
169
170const weighed = await p.evaluate(async (id) => {
171 // The whole directory, which is what `export_size` walks -- the crystal, the
172 // page, every snapshot, the metadata, the log and the sidecars.
173 const walk = async (dir, rel, out) => {
174 for await (const [name, h] of dir.entries()) {
175 const child = rel ? rel + '/' + name : name;
176 if (h.kind === 'directory') await walk(h, child, out);
177 else out.push({ path: child, size: (await h.getFile()).size });
178 }
179 return out;
180 };
181 const all = await walk(await __at('diamonds/' + id), '', []);
182 return {
183 pre: await __d.app.export_diamond_size(id),
184 exact: (await __d.app.export_diamond(id)).length,
185 // What the same Diamond weighed before this: four bytes for three of
186 // EVERY file plus its path, which is what `export_size` did for every
187 // kind alike.
188 old: all.reduce((a, f) => a + Math.floor(f.size * 4 / 3) + f.path.length, 0),
189 };
190}, built.id);
191const oldWay = weighed.old;
192
193check('the size estimate is never under what the pack really costs, which is the '
194 + 'direction a refusal points',
195 weighed.pre >= weighed.exact,
196 weighed.pre + ' estimated, ' + weighed.exact + ' real');
197check('and it is closer than weighing every file as base64 was',
198 weighed.pre < oldWay,
199 Math.round(weighed.pre / 1024) + ' KiB against the old ' + Math.round(oldWay / 1024)
200 + ' KiB, real ' + Math.round(weighed.exact / 1024) + ' KiB');
201
202// Every version reads back as itself. Compared inside the page: a hundred
203// kilobytes per version is not something to carry across the bridge forty-six
204// times.
205
206const same = await p.evaluate(async (arg) => {
207 let page = await __page0();
208 const wrong = [];
209 for (let n = 0; n <= arg.turns; n++) {
210 if (n > 0) page = __turn(page, n);
211 const data = __data(n);
212 let gotP, gotD;
213 try {
214 gotP = await __d.app.read_version_page(arg.id, n + 1);
215 gotD = await __d.app.read_version(arg.id, n + 1);
216 } catch (e) {
217 wrong.push({ v: n + 1, err: String(e).slice(0, 60) });
218 continue;
219 }
220 if (gotP !== page) wrong.push({ v: n + 1, what: 'page', got: gotP.length, want: page.length });
221 if (gotD !== data) wrong.push({ v: n + 1, what: 'data', got: gotD.length, want: data.length });
222 }
223 // And the version the Diamond was created at, which has an empty crystal and
224 // no page at all.
225 const zero = { page: await __d.app.read_version_page(arg.id, 0),
226 data: await __d.app.read_version(arg.id, 0) };
227 return { wrong, zero };
228}, { id: built.id, turns: TURNS });
229
230check('every version reads back as the exact bytes it was written as',
231 same.wrong.length === 0,
232 same.wrong.length ? JSON.stringify(same.wrong.slice(0, 3)) : (TURNS + 1) + ' versions');
233check('and version 0 is still the empty crystal it was created with',
234 same.zero.page === '' && same.zero.data === '', JSON.stringify(same.zero));
235
236// A corrupted patch is refused, not answered with the keyframe. This is the one
237// failure the whole encoding exists to prevent: a splice list bent by a bit is
238// still structurally valid -- the offsets fit, the file is the right length --
239// so a reader with no checksum returns a page nobody ever wrote, and nothing
240// says so until somebody notices months later that an old version is wrong.
241
242const hpatches = files.filter(f => f.name.endsWith('.hpatch'))
243 .map(f => parseInt(f.name, 10)).sort((a, b) => a - b);
244const victim = hpatches.filter(v => v % EVERY > 2 && v % EVERY < EVERY - 2)[0];
245const nextKf = files.filter(f => f.name.endsWith('.html'))
246 .map(f => parseInt(f.name, 10)).filter(v => v > victim).sort((a, b) => a - b)[0];
247
248const bent = await p.evaluate(async (arg) => {
249 const dir = await __at('diamonds/' + arg.id + '/versions');
250 const name = String(arg.v).padStart(4, '0') + '.hpatch';
251 const fh = await dir.getFileHandle(name);
252 const buf = new Uint8Array(await (await fh.getFile()).arrayBuffer());
253 const keep = Array.from(buf);
254 // One bit, in the payload rather than the header: the crudest damage a
255 // storage layer can do, and the one a length check cannot see.
256 buf[buf.length - 1] ^= 0x20;
257 let w = await fh.createWritable();
258 await w.write(buf); await w.close();
259 const at = async (v) => {
260 try { return { v, len: (await __d.app.read_version_page(arg.id, v)).length }; }
261 catch (e) { return { v, err: String(e).slice(0, 40) }; }
262 };
263 const before = await at(arg.v - 1);
264 const broken = [await at(arg.v), await at(arg.v + 1)];
265 const past = arg.nextKf ? await at(arg.nextKf) : null;
266 // Put it back, and require the version to be readable again: a check that
267 // cannot tell damage from a reader that refuses everything is not a check.
268 w = await fh.createWritable();
269 await w.write(new Uint8Array(keep)); await w.close();
270 const healed = await at(arg.v);
271 return { before, broken, past, healed };
272}, { id: built.id, v: victim, nextKf });
273
274check('a version standing on a corrupted patch is REFUSED, not answered',
275 bent.broken.every(a => a.err !== undefined), JSON.stringify(bent.broken));
276check('the damage stops under it: the version before the break still reads',
277 bent.before.len > 90000, JSON.stringify(bent.before));
278check('and it stops at the next keyframe, so the loss is bounded by the interval',
279 bent.past && bent.past.len > 90000, JSON.stringify(bent.past));
280check('putting the patch back makes the version readable again',
281 bent.healed.len > 90000, JSON.stringify(bent.healed));
282
283// A patch missing from the middle of a chain. The two files answer this
284// differently, and the difference is the sparse page snapshot rule rather than
285// anything the delta log introduced.
286//
287// The MEMORY is snapshotted at every version, so a gap in it is a gap: the
288// version whose file has gone is refused, and so is every version over it.
289//
290// The PAGE is snapshotted only where it changed, so a version with no page
291// snapshot has always meant "the page did not move here" and is answered with
292// the last one that did. A deleted page patch is indistinguishable from that,
293// and nothing in the file system can tell them apart. What it CANNOT do is
294// spread: the version after it was made against bytes that are no longer under
295// it, its checksum says so, and it is refused.
296
297const gone = await p.evaluate(async (arg) => {
298 const dir = await __at('diamonds/' + arg.id + '/versions');
299 const at = async (v) => {
300 try {
301 return { v, page: (await __d.app.read_version_page(arg.id, v)).length,
302 data: (await __d.app.read_version(arg.id, v)).length };
303 } catch (e) { return { v, err: String(e).slice(0, 40) }; }
304 };
305 const take = async (name) => {
306 const fh = await dir.getFileHandle(name);
307 const keep = Array.from(new Uint8Array(await (await fh.getFile()).arrayBuffer()));
308 await dir.removeEntry(name);
309 return keep;
310 };
311 const put = async (name, keep) => {
312 const fh = await dir.getFileHandle(name, { create: true });
313 const w = await fh.createWritable();
314 await w.write(new Uint8Array(keep)); await w.close();
315 };
316 const n = String(arg.v).padStart(4, '0');
317 const before = await at(arg.v - 1);
318
319 const hkeep = await take(n + '.hpatch');
320 const noPage = [await at(arg.v), await at(arg.v + 1)];
321 await put(n + '.hpatch', hkeep);
322
323 const jkeep = await take(n + '.jpatch');
324 const noData = [await at(arg.v), await at(arg.v + 1)];
325 await put(n + '.jpatch', jkeep);
326
327 return { before, noPage, noData, healed: await at(arg.v) };
328}, { id: built.id, v: victim });
329
330check('a memory patch DELETED from the middle of a chain is refused, not skipped over',
331 gone.noData.every(a => a.err !== undefined), JSON.stringify(gone.noData));
332check('a deleted PAGE patch cannot spread: the version over it is refused',
333 gone.noPage[1].err !== undefined, JSON.stringify(gone.noPage[1]));
334check('though the version itself reads as the last one that changed the page, which is what \
335a version with no page snapshot has always meant',
336 gone.noPage[0].page === gone.before.page, JSON.stringify(gone.noPage[0]));
337check('and putting both back makes the chain whole again',
338 gone.healed.page > 90000 && gone.healed.page !== gone.before.page,
339 JSON.stringify(gone.healed));
340
341// ...and the Diamond mends itself on the next write. A parent that cannot be
342// rebuilt is not a reason to refuse the write in front of the user. It is a
343// reason to record a full copy, which is both the safe answer and the one that
344// gives the version after it something to build on.
345
346const mended = await p.evaluate(async (arg) => {
347 // Break a patch the HEAD stands on, so the next write's parent is the one
348 // that cannot be rebuilt.
349 const dir = await __at('diamonds/' + arg.id + '/versions');
350 const rows = [];
351 for await (const [name, h] of dir.entries()) if (h.kind === 'file') rows.push(name);
352 const kf = Math.max(...rows.filter(n => n.endsWith('.html')).map(n => parseInt(n, 10)));
353 const inChain = rows.filter(n => n.endsWith('.hpatch') && parseInt(n, 10) > kf)
354 .sort((a, b) => parseInt(a, 10) - parseInt(b, 10));
355 const name = inChain[0];
356 const fh = await dir.getFileHandle(name);
357 const buf = new Uint8Array(await (await fh.getFile()).arrayBuffer());
358 buf[buf.length - 1] ^= 0x20;
359 const w = await fh.createWritable();
360 await w.write(buf); await w.close();
361 // The page FILE is untouched, so the store still knows what the page is; it
362 // is the chain behind it that has gone.
363 const page = await __d.app.read_crystal_page(arg.id);
364 const next = page + '\n<!-- mended -->\n';
365 let wrote = null;
366 try {
367 await __d.app.write_crystal_both(arg.id,
368 JSON.stringify({ title: 'Delta log', mended: true }), next);
369 } catch (e) { wrote = String(e).slice(0, 60); }
370 const now = [];
371 for await (const [n2, h] of dir.entries()) if (h.kind === 'file') now.push(n2);
372 const top = Math.max(...now.map(n2 => parseInt(n2, 10)).filter(n2 => !isNaN(n2)));
373 let got = null, err = null;
374 try { got = (await __d.app.read_version_page(arg.id, top)).length; }
375 catch (e) { err = String(e).slice(0, 60); }
376 return { broke: name, top, wrote, kinds: now.filter(n2 => parseInt(n2, 10) === top),
377 got, want: next.length, err };
378}, { id: built.id });
379
380check('a chain the store cannot walk does not refuse the write in front of the user',
381 mended.wrote === null, String(mended.wrote));
382check('a version whose parent cannot be rebuilt is recorded as a full copy',
383 mended.kinds.some(k => k.endsWith('.html')),
384 'broke ' + mended.broke + ', v' + mended.top + ' is ' + JSON.stringify(mended.kinds));
385check('so the history continues from there rather than ending at the break',
386 mended.err === null && mended.got === mended.want,
387 JSON.stringify({ got: mended.got, want: mended.want, err: mended.err }));
388
389console.log('');
390console.log(' ' + ok.length + ' ok, ' + bad.length + ' failed');
391await s.close();
392process.exit(bad.length ? 1 : 0);