Beagle SCM

DIS-081: caller-supplied commit order; commits[] append-only

DIS-044 made the RGA tie-break the merged commit INDEX, and wmerge_commits (dog/WEAVE.c:645-687) infers that index by re-deriving a topo order from two sorted lists — an O(n^2) ready-test plus a smaller-hashlet tie-break for concurrent heads. The weave stores no parent edges by design (dog/WEAVE.h:133-134): graf owns the DAG and already walks the closure in topo order (be/shared/weave.js build). So libdog reconstructs DAG knowledge it deliberately does not keep, from a shadow of it, on every merge. The cost is a full renumbering: WEAVEMerge permutes commits[] and remaps every token's ins/rms through ra/rb, so an index is not a stable name across a merge. Move the ordering contract to the API and the table becomes append-only.

Input

Context

The weave's commit table serves two roles that only one of them needs order.

• Identity: a token names its inserter by INDEX into commits[] (dog/WEAVE.h:75,118), removers likewise (:119).
• Rank: the RGA tie-break sorts concurrent siblings by merged commit index DESC (dog/WEAVE.c:691-695), so the index must be a causal rank.
• Scope: weavescope is one bit per slot (dog/WEAVE.h:131), so slots must stay dense small integers — this constrains any redesign.
• Callers already have the order: WEAVEScope takes a reachable commit-id set supplied by graf (dog/WEAVE.h:133-135).

Goals

Specify the order as an API contract, then make the table append-only.

• State in the WEAVE API who assigns causal rank, what it guarantees, and what breaks if a caller violates it.
• commits[] becomes append-only: parent a's slots keep their numbers, b's non-shared ids append.
• wmerge_commits and the ra remap go away; rb shrinks to a dedup-aware offset.
• Path-independence is preserved: every clone must derive the same order for the same DAG.

Constraints

The contract moves outward, so the failure mode moves outward with it.

• A caller that supplies a non-causal or path-dependent rank corrupts merge order SILENTLY — today's self-contained version cannot be got wrong that way.
• Changing commits[] semantics touches the 'C' column of the 'W' blob: needs a version gate or a proven-compatible layout.
• Callers land FIRST (gritzko), so no window exists where WEAVE expects an order no caller supplies.

WIP

Design decisions

Split identity from rank; the caller owns rank.

• Rank is supplied by the caller, not inferred — the caller walked the DAG to build the weave in the first place.
• The caller pre-sorts its appends so the APPEND ORDER IS THE RANK; no side column, and the hot tie-break keeps a bare index compare.
• Identity (commits[inserter], ordinal) and WEAVEIdHash are untouched — this changes numbering, not identity.
• DIS-082 subsumes this if it lands: an append-only body never renumbers anything, so re-scope rather than implement both.

TODOs

Callers first, WEAVE second.

• Read WEAVEMerge's remap pass end to end — this ticket is a proposal until that is done.
• Write the ordering contract into the WEAVE API docs and a wiki page.
• Caller side: make graf/be/shared/weave.js build supply the rank explicitly.
• Caller side: audit every WEAVEMerge and WEAVENext call for order compliance.
• WEAVE side: append-only commits[], delete wmerge_commits, drop the ra remap.
• Blob: version-gate the 'C' column change, or prove the layout unchanged.
• Fuzz the contract violation — a path-dependent caller rank must fail loudly, not silently.

Blockers and bummers

• The DIS-044 fuzzer keys commit-id = line index (monotonic), so it cannot surface an ordering regression — same gap that hid DIS-044 itself.

Outcome