Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 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 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | 1x 1x 1068x 1068x 1068x 1065x 1065x 1065x 1x 1996x 1996x 1996x 1996x 1996x 1996x 1996x 1996x 1996x 1996x 1996x 1996x 1996x 1996x 1996x 1996x 1996x 1x 1080x 1079x 1079x 1x 41x 41x 120x 120x 76x 76x 76x 76x 120x 120x 41x 41x 1x 1080x 1080x 1080x 1080x 1x 9187x 9187x 587968x 587968x 587968x 587968x 9187x 9187x 1x 1957x 1957x 1957x 1957x 9431x 2936x 2936x 2936x 1957x 1957x 1x 1x 1x 1x 1x 1x 1x 1x | import { canonicalJSON, decodeText, encodeText, sha256 } from './hash.js';
import { ZERO_DIGEST } from './vfs-file.js';
import type { Hash, LogRow } from './types.js';
/**
* Codec and set algebra for `.vfs/commits` — one JSON object per line, no
* enclosing brackets and no commas, so the file grows by *appending* and every
* line parses on its own.
*
* Rows are immutable and identified, which is what makes merging two logs plain
* set union: dedupe by `op` and the result is the same whichever order the rows
* arrived in, and re-recording an operation is a no-op.
*/
/**
* Identity of an operation. Computed by whoever originates it, from the facts
* of the operation alone — never from the file it lands in or the order it
* lands in. Two replicas that record the same operation produce the same `op`,
* which is the whole basis of the dedup.
*/
export async function opId(row: Omit<LogRow, 'op' | 'batch'>): Promise<Hash> {
return sha256(encodeText([row.peerId, row.uuid, row.at, row.type, row.path, row.hash ?? ''].join('|')));
}
/** Fills in the `op` of a row whose facts are already decided. */
export async function makeRow(row: Omit<LogRow, 'op'>): Promise<LogRow> {
return { op: await opId(row), ...row };
}
/** Canonical key order, falsy optionals dropped, so a row encodes byte-stably. */
export function canonicalRow(row: LogRow): LogRow {
const out: Record<string, unknown> = {
op: row.op,
batch: row.batch,
at: row.at,
peerId: row.peerId,
uuid: row.uuid,
type: row.type,
kind: row.kind,
path: row.path,
};
if (row.hash !== undefined) out.hash = row.hash;
if (row.size !== undefined) out.size = row.size;
if (row.prev !== undefined) out.prev = row.prev;
if (row.prev2) out.prev2 = row.prev2;
if (row.prevPath) out.prevPath = row.prevPath;
return out as unknown as LogRow;
}
export function encodeRows(rows: LogRow[]): Uint8Array {
if (rows.length === 0) return new Uint8Array();
return encodeText(`${rows.map((row) => canonicalJSON(canonicalRow(row))).join('\n')}\n`);
}
/**
* Parses whatever whole lines are in `data`.
*
* A trailing partial line is dropped rather than thrown on: the tail of the log
* is read from a remembered offset, and a reader can legitimately arrive while
* an append is half-landed.
*/
export function parseRows(data: Uint8Array): LogRow[] {
const rows: LogRow[] = [];
for (const line of decodeText(data).split('\n')) {
const text = line.trim();
if (!text || !text.startsWith('{') || !text.endsWith('}')) continue;
try {
const row = JSON.parse(text) as LogRow & { peer?: string };
// The lazy half of the v2 -> v3 migration. Closed segments are immutable
// and cached forever, so renaming a key in them would break the invariant
// the cache rests on, for no gain. A permanent one-line cost instead.
row.peerId ??= row.peer as string;
rows.push(row);
} catch {
// a torn line: the next read from a clean offset will bring it whole
}
}
return rows;
}
// -------------------------------------------------------------- set digest
/**
* XOR of the `op` ids in a set. Order-independent and replica-independent, so
* "do we hold the same operations?" is one comparison instead of a diff.
*
* The known weakness is that inserting an `op` twice cancels it out — which is
* only safe because dedup by `op` is an invariant the merge needs anyway. If it
* ever stops holding, a sum mod 2^256 is the drop-in replacement.
*/
export function xorDigest(rows: Iterable<LogRow>): Hash {
let acc = ZERO_DIGEST;
for (const row of rows) acc = xorHex(acc, row.op);
return acc;
}
export function xorHex(left: Hash | undefined, right: Hash | undefined): Hash {
let out = '';
for (let i = 0; i < 64; i++) {
// A row whose `op` is short or missing is a corrupt line, not a reason to
// fail a sync: it folds in as zeroes and the digest simply disagrees.
const a = Number.parseInt(left?.[i] ?? '0', 16) || 0;
const b = Number.parseInt(right?.[i] ?? '0', 16) || 0;
out += ((a ^ b) & 0xf).toString(16);
}
return out;
}
// ------------------------------------------------------------------- union
/**
* Rows of `incoming` that `existing` does not already hold.
*
* Appending only the difference is what keeps a merge from re-uploading the
* whole segment, which on Drive is what an append costs.
*/
export function missingRows(existing: Iterable<LogRow>, incoming: Iterable<LogRow>): LogRow[] {
const held = new Set<Hash>();
for (const row of existing) held.add(row.op);
const out: LogRow[] = [];
for (const row of incoming) {
if (held.has(row.op)) continue;
held.add(row.op);
out.push(row);
}
return out;
}
/** Set union of two logs, deduplicated by `op`. Idempotent by construction. */
export function unionRows(...logs: Iterable<LogRow>[]): LogRow[] {
const byOp = new Map<Hash, LogRow>();
for (const log of logs) for (const row of log) if (!byOp.has(row.op)) byOp.set(row.op, row);
return [...byOp.values()];
}
/**
* Chronological order, with `op` as tiebreak.
*
* The file itself is in arrival order — that is what keeps offsets stable and
* lets the tail be range-read — so whoever reads it puts the rows back in time
* order in memory.
*/
export function sortRows(rows: LogRow[]): LogRow[] {
return [...rows].sort((x, y) => x.at - y.at || (x.op < y.op ? -1 : x.op > y.op ? 1 : 0));
}
|