Beagle SCM

DIS-082: append-only weave — body + tok32-pair index, tombs as entries

Today's 'W' blob is rewritten whole on every fold (dog/WEAVE.h:100) because DELETION MUTATES stored tokens: a later commit sets rm and pushes into 'M', so earlier bytes cannot be final. Make deletion its own index entry and the BODY becomes strictly append-only — a commit's text bytes are final forever, the small parent-sorted INDEX merges per commit, and the merge-time renumbering that DIS-081 exists to fix never happens. The shape: a BODY of text pieces, an INDEX of tok32 pairs carrying the CT parent/child relation, and a per-commit table of bounds. 'X'/'K'/'I'/'M'/'C'/'A' collapse into three streams.

Input

Context

The current six-column layout pays for in-place tombstones.

• WEAVENext re-emits the entire weave per fold, so writes are O(history); WEAVEMerge then permutes commits[] and remaps every ins/rms.
• 'A' is a u64 anchor hash per token — on word tokens the anchor column can outweigh the text it anchors.
• 'M' needs the tok32 custom bit as a multi-remover escape, spending the one spare bit in the token.
• Literature fit: run collapsing (YATA/Yjs), columnar delta encoding (Automerge), local indices instead of global ids (Chronofold).

Goals

An append-only format where a commit's bytes are final once written.

• Deletion is an appended index entry, never a mutation of the deleted token.
• Body offsets serve as identity, causal rank, and blame key at once — one number replaces 'C', 'I' and 'A'.
• Scope is a bound plus a small exclusion list, not a bitmap over commits.
• Free the tok32 bits the diff class/color set needs, without touching the syntax tag.

Constraints

Weaves are derived data; git is the oplog.

• A weave is a local materialization, rebuildable from the commit DAG — different builds never meet, so offsets MAY be arrival-local.
• RENDERED MERGE BYTES must agree across clones, so the RGA sibling tie-break reads the canonical hash, NEVER a body offset.
• Sources over MAX_SOURCE_SIZE (4 MB) stay blobs, untokenised — big generated files are not diffed and do not enter a weave.
• The 24-bit tok32 offset caps the BODY at 16 MiB, matching MAX_SOURCE_MARKED_UP; the exposure is churn over history, not file size.

WIP

Streams

Three streams replace the six columns; TLV tags below are PROPOSALS, pin them before coding. The BODY is append-only, the INDEX is SORTED — not the same property.

• BODY 'B': u8, the text of every token ever inserted, live and dead, in append order; a commit appends only the tokens it inserts. Strictly append-only.
• INDEX 'E': tokv32 entries — a declared PAIR of tok32 (parent, child), 64 bits — sorted by parent offset then by sibling order.
• tokv32 is a real ABC record type with fixed bit layout, so the index is a tokv32cs/tokv32b and sorting/search go through the typed slice API, not pointer work.
• The index is PARENT-SORTED and is RE-SORTED after each commit: a commit's new entries merge into the sorted array, so the index is rewritten per commit.
• APPEND-ONLY IS A PROPERTY OF THE BODY ALONE. The index is not append-only, not "append-only except at forks" — it is a sorted array maintained by merge.
• That is still the win: the body is the larger stream and never moves, and merging a small sorted batch is one sequential pass, not WEAVENext's whole-weave re-emit.
• COMMITS 'C': per commit, the record (id, body range [start,end), L, K, P, ignore-set); append order is build order.
• IGNORE 'G': pool of ignored-commit-INDEX lists referenced by 'C' records, so a commit record stays fixed-size; consecutive indices may compress to ranges — compression, not correctness.
• Nothing else is stored per token: no anchor hash, no inserter index, no remover list, no side bits.

Entry shapes

The child tok32's TAG field carries the entry TYPE; a syntax tag means an ordinary token, a reserved letter means tomb or terminator.

• INSERT: parent = body offset of the left-neighbour token (the CT parent), child = this token, tag = syntax tag, offset = its first body byte.
• TOMB: parent = body offset of the target token, child tag = the tomb letter, child offset = the DELETING commit's INDEX in 'C'.
• TERMINATOR: closes one inserted chain, flagged by its own letter; parent = the chain's last token, child offset = termpos, the chain's end.
• A tomb carries NO body bytes, so its offset field names a commit, not a token — a body range cannot: pure-delete commits append nothing, so consecutive ones share identical [start,end).
• Multiple removers are multiple tomb children of one target; the 'M' count+N escape and the custom bit both disappear.
• Token LENGTH is implicit inside a chain — the next entry's offset — and explicit only at the terminator, so chains cost no length column.
• A chain costs one entry per token plus one terminator; parent-sorted and offset-sorted coincide within a chain, which is why the implicit length works.
• A FORK (two children of one parent) breaks that coincidence, which is exactly what the terminator escape covers.

Reading

Document order is a preorder walk of the CT; visibility is a bound plus an exclusion.

• ORDER: DFS from the root — emit a token, then recurse into its children in RGA sibling order: causally related siblings descendant-first; the TIE-BREAK for CONCURRENT siblings is canonical commit hash DESC, then ordinal ASC within a commit.
• Siblings are contiguous in 'E' because it is parent-sorted, so the walk is a scan plus a binary search per fork, never a hash lookup.
• ANCESTRY is already stored: u precedes v iff idx(u) < K_v and u not in ignore(v) — the sibling compare is two lookups, no topo rank is ever recomputed.
• VISIBLE to commit c: offset < L_c and the inserting commit not in c's ignore-set; a TOMB is visible iff its deleting commit's index is under K_c and not ignored.
• For linear history the ignore-set is empty, so visibility is one integer compare — the weavescope bitmap is not needed at all.
• L_c is the body length at c, K_c the commit-index cut; P_c is the MATERIALIZED length at c — an allocation size for the render and an integrity check on the walk.
• BLAME: binary search a token's body offset in the 'C' range table (empty pure-delete ranges never cover an offset); why: needs no per-token inserter at all.
• MERGE: nothing splices, nothing shifts, no table is renumbered — the merge record only carries its own cut K and ignore-set.
• The general rule: ignore(c) = [0, K_c) \ closure(parents(c)), closure supplied by the caller (graf owns the DAG, the shape WEAVEScope takes today); two-parent intuition: a commit hides only when NEITHER parent saw it.

Design decisions

Settled in conversation; the rest is Blockers.

• Deletion-as-entry is the load-bearing change — everything append-only follows from it, and nothing else in the format forces a rewrite.
• Offsets are arrival-local and that is ACCEPTED, because weaves are never exchanged; only the sibling tie-break must be canonical.
• Freed tok32 bits: custom (no multi-remover escape) plus side (a tomb entry IS the removal) — 3 bits, enough for the diff class/color set.
• The syntax tag does not move; it stays in the child tok32 exactly as today.
• Declare tokv32 (a tok32 pair, 64-bit fixed layout) so the index gets the typed slice/buffer family rather than ad-hoc pair handling.
• Index maintenance is a per-commit MERGE: sort the commit's new entries, merge into the parent-sorted array, one sequential pass. Not an overflow region, not sort-at-load.

TODOs

Spec first, then reader, then writer, then callers, then cutover. Nothing lands before the parity harness exists.

• STAGE 0 — spec and oracle, no production code
  • Write the format up as a wiki page; this ticket is the sketch, the wiki page is the spec
  • Pin the TLV tag letters and the tomb/terminator type letters against the existing 'W' tags — 'V' outer, 'B'/'E'/'C'/'G' subs, tags 'A'/'B'/'E'/'T'
  • Decide the right-origin question WITH the conflict rule (Dirty), not after it — see Blockers
  • Build a parity harness: same commit DAG through old and new, compare materialized bytes per rev — was test/AWEAVE02; old engine deleted 2026-07-31, harness now oracle-only (test/CFOLD02)
  • Extend the fuzzer beyond monotonic commit ids — SplitMix ids in tests + fuzz/CFOLD.c; 10 min x 8 workers clean, corpus kept at fuzz/CFOLD.corpus/
• STAGE 1 — reader against a hand-built fixture
  • Parse the three streams; reject malformed entries with a named error, not a bare code
  • DFS materialize at tip; byte-parity against WEAVEAlive on the fixture
  • Visibility predicate (L, ignore-set, tombs); byte-parity against WEAVEProduce per rev
  • Blame by range binary search; parity against why: output on the fixture
  • Measure the walk: confirm fork-free chains stay a linear scan — cfstat.bsearch == 0 asserted
• STAGE 2 — writer
  • Fold: append body bytes, append insert entries, append the chain terminator
  • Tomb append; confirm the pre-existing prefix is byte-identical after a delete
  • Merge: ignore-set from the caller-supplied closure; assert no body byte before the merge changed
  • Assert BODY append-only in a test, not by inspection — hash the prefix before and after every fold
  • Assert the INDEX stays parent-sorted after every commit's merge; it is rewritten, so a prefix-stability test would be wrong
• STAGE 2.5 — CFOLD cutover in dog (2026-07-31, //DIS-082 wt)
  • AWEAVE renamed CFOLD (files, symbols, ok64 codes regenerated); WEAVE.{c,h} + tests deleted
  • WEAVE03/04 salvaged as CFOLD03 (DIS-045 blank-EOL merge, real C) and CFOLD04 (DIS-047 scaling bench: fold 2.05x, produce 1.99x doubling)
  • Emit port: CFOLDEmitDiff/CFOLDEmitFull over (from,to) COMMIT INDICES on a multi-scope walk; test/CFOLD05 asserts BYTE-PARITY with the WEAVE02 hunk expectations
  • No fenced EmitMerged (DIS-080: markerless): merged bytes = CFOLDProduce at the merge commit
  • No DIFF-007 coarse fallback: a >16 MiB body is refused at FOLD time (CFOLDBIG, test/CFOLD05)
• STAGE 3 — callers, one at a time, each parity-checked before the next (plan below)
  • jab C++ binding (2026-07-31, //DIS-082-jab wt): weave.hpp -> cfold.hpp, 11 _cfold_* leaves; cont.cpp PROTO["CFOLD"]; test/weave.js rewritten; 104/105 ctest + weave.js OK
  • ITERATION API (ruling: iteration, not flat dumps): CFOLDIterNext/cfoldtok/CFOLDIterMem — one DFS step per call, state in a caller-owned zeroed u32 area; produce/emit/walk are loops over it; yields BODY offsets so CFOLDBlame composes; a first-cut CFOLDTokens array dump was built and REMOVED
  • binding cursor restored on it: stateless _cfold_step + _cfold_itermem, JS rewind(rev)/next()/tok{text,tag,off,end,alive} — the _weave_step pattern, so why.js keeps its loop shape; both wts identical, dog 73/73
  • test/bass.js (JABCbass, JAB-008 canary) ported to the CFOLD family; probe re-sized 1500 -> 1200 folds per its own sizing rule (7s under the hard 10s cap, still 25% over the 960 pre-fix exhaustion point); jab wt 105/105
  • be/shared/weave.js (2026-07-31, //DIS-082-be): ONE weave per file — build() -> {weave, rev, ids}, commits record only on change/delete/join, carries are free; fold/merge take ancestors; foldWt(w, rev, ids, bytes, ext); weave3 folds base once; JOIN_ID exported
  • be/views/why/why.js onto blame: origin = blame(tok.off) per cursor token; ?a..b deletes surface by from/to diff (wash = range head, see Blockers)
  • patch/expected/classify onto the one-weave join (ctx.w is the only stable ref — fold/merge return fresh containers); diff.js+links.js onto rev-hashlet emits; parity: 27/27 patch, 15/15 status, 17/17 non-skip diff, why suite green
  • be suite 327 cases: the 4 weave-relevant baseline failures fixed; ALL remaining failures are the JAB-020 git.pack namespace drift in the fresh jab binary (shared/wire.js:269 still calls the old function form) — seed-path only, zero weave involvement, set flaps with scratch reuse
  • Retire mergedLive onto the C emit — now cursor+blame based in JS, still a mirror of the conflict rule; the C span API (freed class bits) subsumes it
  • bro.js consumes the class bits instead of re-deriving them from hunk adjacency
• STAGE 4 — cutover
  • Measure on a real repo: body size, index size, fold time, render time, all vs. the current format
  • Confirm the ignore-set stays small on branchy history — the scope story rests on it
  • Version-gate or rebuild: weaves are derived, so rebuilding is legitimate if the cost is measured
  • Delete wmerge_commits, the ra/rb remap, and the old columns; re-scope DIS-081 as subsumed — old columns/remap went with WEAVE.c 2026-07-31; DIS-081 re-scope still open

//DIS-082-jab conversion plan

The jab binary embeds dog and exposes it to JS via jab/weave.hpp (JSC leaves, installed by cont.cpp); JS-side callers live in be/. The old surface is 12 _weave_* leaves; the CFOLD surface is smaller because scope bitmaps, the identity hash and the step cursor all dissolve into commit indices and body offsets.

• ORDER: (1) land dog CFOLD; (2) advance jab's dog/ to it — the compile break in weave.hpp IS the checklist; (3) rewrite the binding; (4) port be/ callers one verb at a time, parity-checked: cat, diff, why, patch, get, bro; (5) rerun the be test suite + a pty-click pager check.
• BINDING cfold.hpp (replaces weave.hpp): container holds one 'V' blob; hashlet convention unchanged (id = hi64 of the sha1, 16-hex strings).
  • KEEP, reshaped: _cfold_next(dest, base, len, blob, ext, hash, ancestors[]) — fold now takes the ANCESTOR hashlet array (the closure graf already computes for _weave_scope); pairwise _weave_merge(a,b) becomes _cfold_merge(dest, base, len, hash, ancestors[]) — one weave, no weave-pair plumbing.
  • KEEP: _cfold_count, _cfold_commits, _cfold_alive; _cfold_produce(rev) takes a commit INDEX (or hashlet), not a bitmap.
  • KEEP: _cfold_emitdiff/_cfold_emitfull with from/to as commit hashlets resolved via CFOLDFindCommit — scope-bitmap args gone.
  • DROP: _weave_scope (visibility is stored), _weave_idhash (identity = body offset).
  • KEEP the step cursor, on the ITERATION API (ruling 2026-07-31): _cfold_step(blob, len, rev, cursor) with the DFS state in a JS-owned Uint32Array (_cfold_itermem sizes it) — tokens yield BODY offsets, _cfold_blame(off) -> commit hashlet names the inserter; flat array dumps rejected.
  • ADD before _weave_step can go: the C merged-live render (bytes + conflict SPANS per Dirty's shared-anchor/interior-insertion rule) that retires JS mergedLive — this is where the freed tok32 class bits (DIS-080 blue/orange/yellow) surface.
• RECONSTRUCTION (be/shared/weave.js build + graf.js): today replays a file's DAG as one weave PER NODE with pairwise merges; with CFOLD it is ONE weave per file, folded once per commit in topo order with the closure as ancestors — the per-node weave array, the merge cascade and the 16 MB-per-node buffers collapse into one growing buffer.
• JS CALLERS to touch (grep abc.ram("WEAVE" / .scope(): weave.js, graf.js, classify.js, expected.js, ingest.js, idxmaint.js, submount.js, patch.js, diff.js, bro.js, why.js, test/diff/links/links.js, plus jab's own test/weave.js.
• RISK: mergedLive/_weave_step is the long pole (needs the new C span API); everything else is arg reshaping. The MAX_SOURCE_MARKED_UP fixed-buffer policy carries over unchanged — the body cap (16 MiB) equals it by design.

Blockers and bummers

• JS cannot reach a tomb's DELETING commit: cfoldtok is {off,end,tag,alive} and _cfold_blame names inserters only, so why:'s ?a..b surfaced-delete wash approximates with the range HEAD; exact colouring needs a tomb accessor (e.g. the iterator yielding the tomb's commit index, or the freed class bits).
• LEFT-ORIGIN ONLY: the index stores a parent, not a right origin — Fugue (Weidner/Kleppmann 2023) shows left-only anchoring interleaves concurrent runs; the ORDERING question stays open.
• The Dirty interior-insertion test needs no stored right origin: the right neighbour at insert time is DERIVABLE (next token visible to the inserting commit) — but the derivation must be specified.
• Fork frequency is unmeasured: chains carry the format's efficiency, so if real edits fork often the terminator escape stops being an escape.
• The ignore-set is assumed small; nothing has measured it on real branchy history yet.

Outcome

Suggested commit (//DIS-082 wt, staged): DIS-082: CFOLD replaces WEAVE (append-only weave + emit)

• dog cutover staged in //DIS-082: CFOLD.{c,h,cli.c}, tests CFOLD01-05, fuzz/CFOLD.c + corpus; WEAVE.{c,h}, WEAVE01-04, fuzz/WEAVE.c deleted; 73/73 ctest, fuzz clean (10 min x 8 + corpus rerun)
• known wart: six stale STAGED rows for the pre-rename AWEAVE.* names — delete file# row-unstage (ULOG-004 shape) is not implemented, needs a hand fix or the ulog edit verb
• jab binding staged in //DIS-082-jab: cfold.hpp, cont.cpp, INDEX.md, test/weave.js, dog/CFOLD.{c,h}; suggested commit: DIS-082: jab binding on CFOLD (_cfold_* leaves)
• //DIS-082-jab wart: deleted weave.hpp could not be delete-staged (same ULOG-004 gap); its dog/ CFOLD copy is a STAND-IN for the real subrepo advance once dog lands
• be port staged in //DIS-082-be (base ///be/#e633d1be): shared/{weave,expected,classify}.js, verbs/patch/patch.js, views/{diff/diff,why/why}.js, test/diff/links/links.js; suggested commit: DIS-082: be JS on CFOLD (one weave per file)