Text CRDT - barocss/barocss-hub GitHub Wiki

Text-CRDT

Status: protocol proposals accepted by Review in #47/#48; escalations decided in D-052..D-056.

Repository-Semantics §7: the text content CRDT (Issue #48, required by D-048). It answers the §1.2 open question ("which sequence CRDT, line or char") and fills the hook-in interfaces of Online-First 6.6. Spec only: no code on develop implements any of this yet.

Labels: [decided] (with a D-link) = a recorded user decision; [decision-proposal] = proposed here, refinable with evidence; [open question]; [escalation] = a user-facing choice, listed in 7.14. Research items are marked known technique (published), observed behavior (seen in develop's code), hypothesis (unverified).

7.0 Summary

  • [decision-proposal] One sequence CRDT, Fugue (FugueMax tree rule), implemented in-house in hub-core, over bytes of UTF-8 text addressed per character position, with element ids (OpId, byte offset) so one op carries a whole run without consuming Lamport counters.
  • [decision-proposal] Line-level first: in the alpha the diff that turns an editor save into ops only emits whole-line runs (insert/delete whole lines). Character-level later changes only the diff, not the CRDT, the op format or any stored op (7.3.5).
  • [decision-proposal] One new payload TextEdit (one op per file per save) under the existing envelope {id, deps, payload} (§2.1). SetContent stays for binary files and for the first content of every file; text ops edit the content set by the latest SetContent (its epoch), whose lines are seeded virtually with deterministic ids, so no seed op exists and two replicas upgrading concurrently produce the same sequence (7.4.2).
  • [decision-proposal] Concurrent text edits in one epoch merge with no conflict record; overlapping ones get an informational concurrent-edit notice (7.8). Conflicts across epochs (a binary flip or an old peer's whole-file SetContent) keep today's content conflict.
  • Move, delete and revive are unchanged: a TextEdit is an edit for D-014 / D-023.

7.1 Which files are text

  • [decision-proposal] A content value (whole file bytes) is text iff all hold: (a) valid UTF-8 (std::str::from_utf8); (b) no NUL byte (the git/file(1) binary heuristic; known technique: git treats a NUL in the first 8000 bytes as binary); (c) size ≤ TEXT_MAX = 8 MiB [decided] (E-T4, D-053); (d) longest line ≤ 64 KiB (minified JS/JSON/lockfile-like blobs gain nothing from line merge and cost metadata; they stay bytes) [decided] (E-T4, D-053). Otherwise it is bytes (today's whole-blob LWW + content conflicts, §2.3 #18).
  • [decision-proposal] Override file .hubattributes at the working-directory root, a tracked file like .hubignore (§1.6, #24), same pattern syntax and "last match wins": <pattern> text forces text (still requires (a) and (b); size and line caps lifted up to a hard 64 MiB), <pattern> binary forces bytes. Nothing else in v1 (no eol=, no merge=). [decided] (E-T3, D-053) (alternative: reuse .hubignore with a section, or gitattributes' -text).
  • [decision-proposal] Classification is made by the author at authoring time, per save, on both the base content and the new content: a TextEdit is authored only when both are text; otherwise a SetContent is authored. It is not a node property and not a Kind variant. Receivers never re-classify: an incoming TextEdit is valid iff its bytes are valid UTF-8 and its offsets fall on character boundaries (7.4.6). So different .hubattributes versions or caps on two replicas never cause divergence.
  • Flip text → binary (a save that is no longer text, or grows past the cap): the author emits SetContent, which starts a new epoch in bytes mode. Concurrent TextEdits on the old epoch lose by the epoch rule (7.4.3) and produce a content conflict, exactly as two concurrent whole-file saves do today. Flip binary → text: the next save is a SetContent (its blob is the epoch seed); edits after it are TextEdits. No hysteresis in v1 [open question] (a file oscillating around 8 MiB alternates modes; each flip is a SetContent).
  • Line endings [decision-proposal]: no normalization. Bytes are stored and materialized exactly; a line is the bytes up to and including \n, so \r\n ends a line with its \r (mixed endings survive per line). The last line may lack \n. Consequence: appending after a final line without newline modifies that line (delete + insert), so a concurrent edit of that line duplicates it (the notice in 7.8 flags it). [decided] (E-T8, D-053) if a eol=lf normalization is wanted.
  • BOM [decision-proposal]: a leading UTF-8 BOM (EF BB BF) is its own unit in the line diff (a pseudo-line 0), so an insert "at the top of the file" goes after it and never ahead of it; removing the BOM is an ordinary delete of those 3 bytes.

7.2 Choice of the sequence CRDT (research)

Known technique sources: Weidner, Gentle, Kleppmann, "The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing" (arXiv 2305.00583, 2023; Fugue, FugueMax, the maximal non-interleaving property); Nicolaescu et al., "Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types" (GROUP 2016; YATA/Yjs); Roh et al. 2011 (RGA); Kleppmann et al., "Interleaving anomalies in collaborative text editors" (PaPoC 2019); Gentle & Kleppmann, "Collaborative Text Editing with Eg-walker" (EuroSys 2025; diamond-types); Loro docs (text is Fugue-based, rich text via Peritext-style marks); Automerge docs (text is an RGA list of characters). Discussion #6 (our research #2) covers Loro and the Kleppmann move op.

Criterion RGA (Automerge text) YATA (Yjs / yrs) Fugue / FugueMax Loro text Line-level vs char-level
Interleaving of concurrent runs at one position forward runs safe; backward-typed (prepend) runs can interleave (PaPoC 2019) forward safe; backward interleaving possible (Fugue paper §2) non-interleaving in both directions; FugueMax is maximally non-interleaving (paper, Thm.) inherits Fugue lines are atoms of one run each, so concurrent line inserts never mix inside a line in either case
Metadata id + ref per char; run-length in Automerge 2 id + 2 origins per item, items run-merged id + parent + side per element, run-merged Fugue + rich-text marks, run-merged line-level: one run per changed hunk; char: one run per typing burst
Tombstones / GC kept kept; GC drops content, keeps id stubs kept as tree nodes; content can be dropped (7.10) kept, shallow snapshots same story; fewer elements at line level
Determinism total order by (counter, actor) needs client ids + clock per char sibling order by element id only same n/a
Fit with our op model Automerge has its own change DAG, actors, hashes: a second history inside ours own update encoding, state vectors, u64 client ids: a parallel clock needs only unique, totally ordered element ids and causal delivery: our (OpId, offset) and Causality suffice own oplog, peers, version vectors: parallel model n/a
Rust implementation automerge (MIT), large dep tree yrs (MIT) none general-purpose standalone; diamond-types (ISC, eg-walker) is research-grade loro (MIT), large dep tree n/a
Performance (published) Automerge 2 replays the 260k-op editing trace in well under 1 s Yjs/yrs ~same order Fugue paper and eg-walker report the same order as Yjs for the trace same order line level: ~10–100x fewer elements than char level on code
  • Observed behavior (develop): ops are {id: OpId=(Counter, ReplicaId), deps, payload} (hub-core/src/tree.rs Op, Payload::{Create, Move, Delete, SetContent{node, blob}}), Kind has only File (no Bytes/Text variant), Causality gives deps* queries in < order (CSR tables, #33), digests hash every op (h(o), 4.12/D-051), Lamport checks and rescue (#49) work per op. Any library that carries its own ids, clock and change DAG would have to live as a per-file sub-log inside one of our payloads, so its ops would be opaque to Lamport checks, causality, digests, rescue-by-effect and the server API; or we would have to map every library op 1:1 onto our ops, at which point the library adds little.
  • Hypothesis: an in-house FugueMax over run-length elements is ~1.5–2.5 kLOC with tests (Fugue's reference implementation is small; the hard parts are the run-split order-statistic tree and the oracle), comparable to tree.rs's undo-redo replica.
  • [decision-proposal] Choice: in-house FugueMax, element = one UTF-8 character addressed as (op_id, byte_offset), stored as runs; diff at line granularity in the alpha. Rationale: the only family with a proof of (maximal) non-interleaving; needs nothing beyond our ids and causal delivery; no new dependency (license and supply chain unchanged, MIT, D-031); a sorted-fold oracle can be written exactly like tree_oracle.rs. Rejected: adopting yrs/automerge/loro (a second clock and op DAG under ours, heavy dependency trees, opaque ops for digest/rescue/API); RGA/YATA in-house (known interleaving anomalies, no advantage). loro/diamond-types may be used as dev-dependencies only for differential tests [open question].
  • [decided] (E-T1, D-053) Character-level in the alpha or line-level (proposal: line-level; char-level needs an editor integration that sends keystroke-level or range edits, #41, to be worth it).

7.3 The CRDT, precisely

7.3.1 Elements and ids

  • [decision-proposal] An element is one Unicode scalar value's UTF-8 bytes. Its id ElemId = (op: OpId, off: u32), off = byte offset of its first byte within the run that created it. Ids are unique because OpIds are (2.6 #1). Order on ElemIds: by op in <, then off. A run of n bytes uses one OpId (no counter reservation, unlike Yjs where every character consumes a clock tick).
  • Reserved: START and END (virtual, never deleted).

7.3.2 Insert rule (FugueMax tree, known technique, restated for our ids)

State per epoch is a tree; every element has a parent and a side (L/R). The list is the in-order traversal (left children, the node, right children).

  • An insertion of a run between left (an element or START) and right = the element immediately after left in the full list (tombstones included) of the author's state at the op's deps (Review R2: not at the diff base V_wd; see 7.5.1), or END: if left has no right children, the run's first element becomes a right child of left; otherwise it becomes a left child of right. Every following element of the run is the right child of the previous one (a run is a chain, hence never interleaved).
  • Siblings on the same side of the same parent are ordered by FugueMax's rule: right siblings by their right origin (in list order, later first) then by ElemId; left siblings by ElemId ascending. [decision-proposal] ElemId order is our <, nothing else; it carries no meaning.
  • The author records both origins in the op, so a receiver needs no view of the author's list.
  • Receiver rule (#53): the run is a left child of right iff right is reached from left by one right edge followed only by left edges (right is the leftmost element of left's right subtree); otherwise it is a right child of left. For conforming origins (adjacent at deps) this is exactly the rule above. Non-adjacent origins are valid, not invalid-op: the rule reads only fixed tree positions, so placement is still a pure function of the op set; only property 7.12 #4 is limited to conforming authors.

7.3.3 Delete rule

  • A delete names id ranges (op, off, len) of existing elements and marks them tombstones (kept in the tree, invisible). Deleting a tombstone again is a no-op. Insert and delete commute; there is no "undelete" (restoring text is a new insert, as in every list CRDT).

7.3.4 Materialization

  • materialize(epoch, V) = concatenation, in list order, of the bytes of elements whose inserting op is in V and that no delete in V covers. [decision-proposal] This works for any causally closed version V, not only head, because elements carry their op ids: the text "at base B" (6.5.3, 6.13 Q3) and "at the working directory's version" (7.5) are filters, not replays.
  • Validity of the result: every element is a whole UTF-8 character, so any concatenation is valid UTF-8.

7.3.5 Upgrade path to character level

  • [decision-proposal] Because every character already has an id, a character-level diff (or an editor sending range edits) emits TextEdits whose origins point inside former line runs; old line-aligned ops stay valid and unchanged; no migration, no new op kind, no feature flag beyond a capability for editors. What changes: the diff (7.5.2), metadata per edit (more, smaller runs), and the notice rule (7.8, per character range instead of per line).

7.4 Integration with the op model

7.4.1 New payload

  • [decision-proposal] TextEdit { node: NodeId, epoch: OpId, seen: Set<OpId>, del: Vec<(ElemId, len)>, ins: Vec<Ins{left: ElemId|START, right: ElemId|END, bytes}> }. One op per file per save (one record or watch step). The runs of ins are concatenated for addressing: run k's bytes start at offset sum(len(ins[0..k])) within the op. seen (Review R1) = the heads of node's content ops in the author's diff base V_wd (7.5.1); every member must be in deps* (else invalid-op); it is part of the payload and of h(o) (tag 4). Envelope and Lamport rule unchanged; deps = the author's index base (#25, V_wd; for the API the request's base), never the current frontier (Review REPAIR 2; 7.12 #18); deps must make every referenced element's op and the epoch op causal predecessors (they are, since the author saw them).
  • Contradiction (recorded, not resolved here): §1.2 says content is Bytes or Text "fixed at creation" and §2.2 lists Create{kind: File(Bytes|Text)} and "SetContent … Text: an op of the chosen sequence CRDT". Develop has Kind::File with no variant and every existing file is bytes. This spec instead makes text-ness a property of each edit (7.1) and adds a separate payload. Proposed amendment: §1.2/§2.2 read "File content is a sequence of epochs; each epoch starts with a SetContent (or the Create's empty content) and may be edited by TextEdits". Needs the Mentor's acceptance because it changes §1.2's wording.
  • Log record (ops.log, pending.log, the rescue manifest, wire Ops body, the #50 reported-rejection hash) [implemented, #54]: O <id> <deps> T <node> <epoch> s=<seen> d=<del> i=<ins>, with seen = - or comma-joined op ids in strictly ascending order; del = - or comma-joined <op>:<off>+<len> in payload order; ins = - or ;-joined <left>|<right>|<base64> in payload order, left = ^ (START) or <op>:<off>, right = $ (END) or <op>:<off>, the run's bytes in RFC 4648 base64 with padding and zero unused bits. Ids are the Appendix A form, numbers canonical decimals; anything else is rejected (corrupt on disk, protocol on the wire), so each TextEdit has exactly one spelling. Golden vector: wire::tests::text_record_round_trips_with_golden_vectors. Format v2 only (7.9).
  • h(o) payload tag 4 [implemented, #54]: 0x04 ‖ id(node) ‖ id(epoch) ‖ u64 |seen| ‖ ids ‖ u64 |del| ‖ (id(op) ‖ u32 off ‖ u32 len)* ‖ u64 |ins| ‖ (left ‖ right ‖ u64 len ‖ bytes)*, an anchor = 0x00 (START/END) or 0x01 ‖ id(op) ‖ u32 off; integers big-endian, ids as in 4.12. Golden hash 2faece6b…00b86a for the golden record.
  • Chained saves (TEXT_OP_MAX) [decided: Planner, #54]: one save produces one or more chained TextEdits per file, each with an encoded record ≤ TEXT_OP_MAX = 192 KiB. Derivation: the smallest frame a peer may announce is FRAME_FLOOR = 256 KiB + 64 (Remote-Sync 5.2.3; the default max_frame is 1 MiB, so ~1 MiB would not fit the default either); 64 KiB stay free for the Ops header (sender frontier, ~1 300 ids), so every authored record reaches every conforming peer (test max_size_chained_op_fits_a_frame_floor_peer). Op 1 has the save's deps and seen; op k+1 has deps = {op k} (its causal past equals deps*(op k) ∪ {op k}, and the record stays small) and seen = {op k}; ids are consecutive counters of the author. Split points: whole del entries, then whole ins runs; a run too long for one op is cut at a UTF-8 character boundary, preferring a line end; the continuation's left is the previous piece's last element, so anchor adjacency (7.12 #17) holds inside the chain. All ops of one save are appended in one batch (A.2.2), so a crash never leaves half a save. Worst case: N = ceil(4·ceil(B/3) / (TEXT_OP_MAX − H)) ops for a B-byte insert (base64 inflates 4/3; H ≈ 0.3 KiB envelope), i.e. 57 ops for an 8 MiB save (the Planner's "about 43" is 8 MiB / 192 KiB before base64). Core helper split_text_edit (#54); T3 wires it into record, watch, checkout-merge and rescue. Store guard (#54): an op authored by this replica whose record exceeds TEXT_OP_MAX is refused with limit, nothing written; received ops are bounded by the wire frame limit. Properties (proptest text_split.rs): every op fits; with no concurrent ops the chain's head is the saved text; with concurrent ops every chain op is valid, the concurrent ops' text is exactly what it is next to the unsplit edit and our bytes appear in the same order; deps* ⊆ base ∪ chain (7.12 #18); an 8 MiB single-line run reproduces byte for byte.

7.4.2 Epochs and the virtual seed

  • [decision-proposal] An epoch of node x is an Applied Create of x (empty content) or an Applied SetContent of x. Its seed sequence is the blob's bytes as one run created by the epoch op itself: element (epoch_op, off) for each character at byte off (seed run is a chain). No seed op is ever written. This replaces 6.6's seed(blob) -> TextState with a pure function of the epoch op and its blob, so two replicas that upgrade concurrently and both edit the same old file reference identical element ids and merge (an explicit seed op per replica would have produced two independent sequences and duplicated the whole file).
  • Requirement: the seed needs the epoch blob (on a thin client: content on demand, 6.2.4 / 7.11).
  • Membership (consistency with Online-First 6.2.2): "the epoch op is Applied in V" and "an element's inserting op is in V" are decided on a thin client by exact membership M(B) for ids below the base and by W otherwise, never by VV(B) (Online-First 6.2.2, property 19).
  • Trust caveat: this deferred check makes thin == full (Online-First 6.10 #1) hold for invalid-op verdicts only for an honest server, next to Online-First 6.7's base trust limit; a lying server's invalid TextEdit is applied by a thin client until materialization flags it.
  • Thin-client validation (review recommendation) [decision-proposal]: checking that a TextEdit's seed offsets fall on character boundaries needs the epoch blob. A thin client that lacks it accepts an op the server vouched for (it arrived in the server's stream, i.e. the server committed it after validating it with the blob) and defers its own check to materialization; a full replica and the server always validate on apply. The invalid-op verdict stays a function of the op set because the server and every full replica compute it identically and the thin client never authors a different verdict (it reports a mismatch at materialization as corruption of the server's stream, not as a new conflict).
  • A TextEdit with an epoch that is not an Applied Create/SetContent of node, or that references elements not in that epoch, or whose bytes are not UTF-8 / offsets not on character boundaries, is an invalid-op (2.2): a no-op, recorded, never a loser.

7.4.3 Content of a node (replaces the §2.3 #18 winner rule for files with text ops; identical when there are none)

  • [decision-proposal] Let content ops of x be its Applied SetContents and TextEdits. The winning epoch is the epoch of the greatest content op in < (a TextEdit counts for its epoch). Content of x = materialize(winning epoch, all ops). All TextEdits of the winning epoch merge; none is a loser.
  • Seen-later (Review R1) [decision-proposal]: content op c overwrites content op e iff e ∈ deps*(c) and either c is a SetContent or c is a TextEdit with e in the content down-closure of c.seen (e ∈ seen ∪ deps*(seen)). Conforming authors take deps = their base (7.4.1), so seen and deps agree; seen additionally keeps the verdict correct for a TextEdit whose deps reach past its diff base (a non-conforming or future author): such a dependency does not overwrite.
  • Losers: every content op e in another epoch that no content op overwrites is a loser and gets one content{node, winner, loser: e, winner_blob, loser_blob} conflict, where loser_blob of a text epoch is the materialized text of that epoch restricted to deps*(e) ∪ {e}, and winner_blob is the materialized head of the winning epoch (all its merged TextEdits; for a SetContent winner with no edits, its blob). This matches today's rule, where winner_blob is the head content, so a "keep winner" action never deletes concurrent merged edits. [decided] (Planner, #53 Review R2). Both are stored in the blob store, so the shape and the CLI-JSON fields are unchanged. With only SetContents this is exactly today's rule (every SetContent is its own epoch). A SetContent causally after a TextEdit is a normal overwrite (flip or revert), no conflict.
  • Stale-epoch save (Review R1 case): wd at epoch S1; a remote SetContent S2 (flip, old peer, binary rescue) arrives and is not checked out; the user saves → TextEdit t{epoch S1, seen ⊆ S1's ops, deps = V_wd}, so S2 ∥ t. If t is the greatest content op, S1 wins and S2 (neither in deps*(t) nor in seen*(t)) is not overwritten and is a content loser (loser_blob = S2's blob): visible, never silently dropped. If instead the user had checked out S2 first, seen ∋ S2 and S2 is overwritten as normal editing. Why it converges: seen is part of the op, so 'overwrites' and the loser set are pure functions of the op set (no dependence on delivery or on any replica's view). Why no silent drop holds: a content op disappears from head without a conflict only if some op whose author had it in its diff base (seen) or a SetContent (whose author, by 7.4.3, wrote the whole value after it) succeeds it. Chosen over (a) authoring a SetContent (which with deps = frontier would itself overwrite S2 silently) and (c) refusing (blocks saves on every remote flip; interacts with E-T7). Answered (Review REPAIR 2, checked on develop 52e9c08): SetContent needs no seen: record/watch author on the index base (prepare_on(idx.base)), mutate/rescue refuse unless at head, checkout/publish author no content ops; so a SetContent's deps never include a content op its author did not see. The thin-client and API paths are worded the same way (Online-First 6.3.1, 6.2.3, 6.4, 6.5.3).
  • [decision-proposal] A text-aware author never writes a SetContent on a text file except for a flip (7.1). Reverts, "Keep mine" in conflict UIs, checkout of an old version followed by record: all go through the diff, so they merge.

7.4.4 Move, delete, revive (D-001, D-014, D-023)

  • [decided] via D-014/D-023: a TextEdit is an edit E in the §2.3 revive rule exactly as a SetContent is (revive_by_edits iterates content ops). A concurrent (or causally later, per the §2.3 decision-proposal) TextEdit on a trashed file revives it (the whole deleted folder per D-023) with one edit-revived conflict. The text state is never discarded on delete: tombstoning a node does not touch its sequence, so edits made concurrently with the delete, by any number of replicas, are all present after the revive.
  • Move: content follows the node (row 3/16), no interaction. A move revive (D-001) brings the node back with all its text ops. A delete causally after the edits sticks (row 14 rule), and the text stays in the trashed record (restorable).
  • Concurrent edits on a node that ends up trashed (delete causally after some edits but concurrent with others): the concurrent ones revive it (D-014), so no text edit is ever silently invisible.
  • Rescued replica (#49, D-049) [decision-proposal]: reid --rescue re-authors by effect. For a text file, the effect is re-authored as a TextEdit = diff (7.5.2) between the local text of the store minus the rejected ops R (always available, also for --offline rescue) and the rescued file's bytes, with the new replica id, deps = the rescue's index base (the store minus R, at its head; #49 records at head), and seen = the content heads of that store; the CRDT then merges it with the server's concurrent edits on sync, the same effect as diffing against the server text, without needing the server's ops. Rejected (equivocating) TextEdits themselves are never replayed (their ids are tainted, D-022). A rescued binary file stays a SetContent (today).

7.4.5 Causality

  • No new structure: deps* checks (7.4.3 losers, 7.8 concurrency) use Causality as conflicts do (#33). Text ops add ops, not edges of another kind.

7.4.6 Convergence restated

  • [decision-proposal] State, conflicts and notices remain pure functions of the op set (§2.3, 2.6 #3): the FugueMax tree for a given set of runs is unique (insertion position depends only on origins and ElemId order), so the sorted fold, an incremental integrate and any delivery order give the same list.

7.5 Working directory: from editor saves to ops

7.5.1 Base of a save

  • [decision-proposal] The diff base of a tracked text file is materialize(epoch, V_wd) where V_wd is the working directory's version (checkout index workdir.version), not head: a save made while remote ops arrived is diffed against what the editor actually had. Its deps are V_wd, the index base (#25), not the current frontier: remote ops that arrived but were not checked out are concurrent with the save, and the CRDT merges them. Anchor mapping (Review R2) [decision-proposal]: the diff (7.5.2) yields, per hunk, an anchor left element taken from V_wd (the last element of the preceding V_wd-visible line, the last deleted element, or START); the op's right is then the immediate successor of left in the full list of the author's state at deps (tombstones included), never the successor among visible V_wd elements. With deps = V_wd a remote X that arrived after the checkout is not in deps, is concurrent, and is ordered by Fugue; when the diff ran on a text other than the deps state (API server-side diff, 7.5.1 hash mismatch fallback), an X inside deps right after left gives right = X and the run lands immediately after left, before X: the origins are adjacent in the author's list at generation time, which is what Fugue's intention and (maximal) non-interleaving proofs assume. Epoch-view (Review R1, fix (b)) [decision-proposal]: the op also records seen = the heads of the node's content ops (SetContents and TextEdits) in V_wd, i.e. what the user actually edited from (7.4.1, 7.4.3). Merge with the remote edits then happens in the CRDT. Check: the base's SHA-256 must equal the index's blob id for that path; if not (index damaged, or a pre-#48 index), the base is head's text and a concurrent-edit notice is recorded [decision-proposal].
  • Server API (6.5.3, 6.13 Q3): set-content on a text file is diffed by the server against materialize(epoch, base); same algorithm.

7.5.2 Diff algorithm

  • [decision-proposal] hub-diff-line/1: split both texts into lines (7.1; BOM pseudo-line), Myers O(ND) minimal edit script (known technique, Myers 1986, as in git's default) with fixed tie-breaks, in this precedence: (1) leftmost alignment (greedy forward Myers; at a tie in the forward step, V[k-1] >= V[k+1], take the deletion move, so a common line is matched as early as possible in the base), then (2) deletion before insertion within a hunk. Example (pinned by diff_line_golden_tie, #53): a\na\n → b\na\n keeps the first a, inserts b at the top and deletes the second a. [decided] (Planner, #53 Review R3); adjacent delete+insert of one hunk becomes del of that range plus one ins whose left = the last deleted element (so replaced text sits where the old text was, after concurrent inserts anchored before it) and right = the element after it in the full list; pure inserts anchor on the visible line before (left = its last element) or START. In every case right is then fixed by the anchor mapping of 7.5.1 (successor of left in the full list at deps).
  • Cost bound: if D > 20 000 lines, the diff falls back deterministically to "delete all, insert all" (one hunk) and records nothing else special (it is a valid edit; concurrent edits of the same file then duplicate, flagged by 7.8). [open question] patience/histogram diff for better hunks on code (git --histogram); purely a quality change, same ops format.
  • Determinism: convergence never depends on the diff, because receivers apply the author's ops, never re-diff. The diff must only be a pure function of (base, saved) for reproducibility, tests and the server reply; it is versioned by name (hub-diff-line/1) and a server reports the diff name it used in the set-content reply, so a server upgrade that changes it is visible and harmless (6.13 Q3 answered).
  • No-op save: identical bytes → no op (today's record behaviour).

7.5.3 Checkout of merged text and no-clobber

  • [decision-proposal] Checkout writes materialize(winning epoch, head) byte-exact (7.1 line endings). All existing safety rules hold unchanged: never overwrite an unrecorded file, a blocked path or an untracked ignored path (#19, #20 D-019, #24, #26), atomic replace, index updated.
  • [decided] (E-T7, D-056) For a dirty text file (modified since V_wd), proposal: checkout/watch first record it as a TextEdit against V_wd (7.5.1), then materialize the merged result, instead of refusing. Today's rule (refuse a dirty file without --force) stays the default for bytes. This changes user-visible behaviour of #19/#26 for text files, hence escalated. Without it, a thin client with live remote edits would refuse almost every checkout. Conditions: the dirty bytes are recorded (durable ops) before anything is written; the write is the usual atomic replace; and the flip exception: if the file's head epoch is bytes (a SetContent flip won) or the dirty content is not text, nothing is auto-recorded and checkout refuses as today.
  • [open question] Open editor buffers: the file on disk changes under VS Code; the extension (#41) should reload clean buffers and, for dirty buffers, save-hint + record first. Editor-level live merge is a #41 item.

7.6 Conflicts

  • [decision-proposal] Concurrent TextEdits on one epoch never produce a conflict record. Both sides' insertions are kept (no lost insertions); concurrent deletes of the same text delete it once; an edit of a line concurrently deleted by another keeps the edited line (its new run is live; the old line is a tombstone in both).
  • Line-level consequence (known technique, the price of line atoms): two replicas changing the same line differently produce both new lines (old line deleted twice, two inserts). Character-level (7.3.5) would merge them character-wise. The notice (7.8) points the user at it.

7.7 Line blame (6.13 Q4)

  • [decision-proposal] blame(x, V): for each line of materialize(epoch, V), the inserting op of its first non-newline element (at line level: of the whole line); the op's replica maps to its principal on the server (6.5.4, E-B9 governs who may see it). Seed elements blame to the epoch's SetContent; for history before it, the blame walks the previous epochs' whole-blob history (log per file, today's behaviour). Cost: O(lines) from element ids, no history walk inside an epoch.

7.8 Soft warning: concurrent-edit notice

  • Chained saves (#54): the ops of one chain (7.4.1) are pairwise causally ordered, so the chain alone never raises a notice; with a concurrent op, several chain ops may share one notice component with it (union of overlapping concurrent pairs).
  • [decision-proposal] A notice, not a conflict: derived (pure function of the op set), informational, never blocks anything, not counted in conflicts. For text ops a ∥ b (neither in the other's deps*) on the same node and epoch, they overlap iff their touch sets intersect, where touch(o) = elements o deletes ∪ o's origins left/right ∪ the first and last element o inserts' neighbours in the final list. Notices are derived for the node's winning epoch only (losing-epoch edits already carry content conflicts and have no head lines; #53); lines are 1-based, a deleted fragment counts at the line of the next visible character. One notice per node per connected group of overlapping ops: {kind: "concurrent-edit", node, path, ops, lines: [first, last] in head text}. It disappears when a content op of the node causally after all ops exists (someone saw the merge and edited after it), like conflicts. Thin clients: touch(o) needs the file's text state; for files outside the sparse set (ids + h(o) only, 7.11) notices are server-derived (6.1.3) and shipped with status; inside it the client computes them like any replica.
  • [decided] (E-T2, D-053) Default on (proposal) or off, and whether overlapping-but-identical edits (both inserted the same line) are flagged.
  • UX (CLI-JSON schema 1, additive): status --json gains notices: [{kind, node, path, ops, lines, authors}] (a new key; schema stays 1, the contract allows added keys); plain status prints notice: concurrent edits merged in <path> lines a-b (by X, Y); watch --json emits event {"event":"notice", ...} when a notice appears. VS Code: an information decoration on the line range + a "Show merge" action opening a diff of each side's change against their common base (materialize(epoch, ∩ deps) vs each side), and a "Dismiss" that records nothing (dismissal is local view state; the notice clears by itself on the next edit). Never a modal, never on save.

7.9 Migration and compatibility

  • Implemented (#54): feature text in Hello; the answerer checks every Ops batch it sends (the delta and Need answers): a TextEdit towards a peer without text ends the session with Error upgrade-required (fatal; the receiver has persisted nothing of that half). It covers pull from a text server, push to an old server (mixed remotes) and file:// (same session code). Receiving a TextEdit without negotiating text is unsupported. Format v2 and snapshot v2: Repository-Semantics A.2.9. Tests: crates/hub-cli/tests/text_t2.rs (with HUB_TEST_OLD_BIN = the pre-#54 develop 05a1be0 build).
  • [decision-proposal] Existing SetContent history stays valid and meaning-preserving (7.4.3 reduces to §2.3 #18 without text ops). The first text edit of an existing file needs no migration step: its epoch is the file's current SetContent (virtual seed, 7.4.2). New files: Create + SetContent as today (old peers understand the creation; only later edits are text ops).
  • Wire: Hello feature text (5.2.3). A sender never sends a TextEdit to a peer without it. A text-aware client whose remote lacks text authors SetContent (it falls back to bytes mode for every file). A server holding text ops and a client lacking text whose missing set contains text ops: the server ends the session with Error upgrade-required (fatal for that session, nothing persisted) [decided] (E-T6, D-053). It is refused entirely until upgraded, because it cannot hold a causally closed store without the text ops.
  • On disk (#33 bar): a pre-#48 v1 binary would read a T record in a committed batch as unparseable, i.e. corruption, and refuse; but A.2.5's bar requires refusing before reading anything else with a clear marker. [decision-proposal] Format v2 = v1 + T records + text state in the snapshot; the replica header becomes barocss-hub/replica/v2 (with v2-rescue replacing v1-rescue) lazily, at the first TextEdit appended (authored or received), under the exclusive lock, header-only (no log rewrite), with the same crash stages and tests as A.2.6. Until then the repository stays v1 and old binaries keep working. [decided] (E-T5, D-053): once a repo has text ops, pre-#48 binaries refuse it (a one-way upgrade).
  • Mixed remotes: a client with a text remote and a remote lacking text (an old full replica or file:// repo): once its store holds TextEdits, a push to the old remote also ends with upgrade-required (the old remote could not hold a causally closed set), not only pulls from it.
  • Old binary seeing text ops: on the wire never (feature gate); on disk refused at the header (above); via a file:// remote: same as wire.
  • Pre-upgrade content conflicts (6.13 Q6) [decision-proposal]: unchanged; they are derived from SetContents, keep their winner_blob/loser_blob, and are resolved as today by any causally later content op; resolving one with "Keep mine" or a manual edit now emits a TextEdit on the winner's epoch (a diff from the winner's text to the chosen text), so the resolution itself merges with other concurrent edits.

7.10 Tombstones and GC (6.13 Q5)

  • [decision-proposal] v1 never removes element ids: an op in a window W, or a client on an older base, may name a tombstone as origin or delete range. At a base cut (6.2.2) and in snapshots, tombstones keep only their id range and tree position (run-length; no bytes): ~24 bytes per tombstone run, independent of the deleted length.
  • [open question] Full removal of tombstone runs needs causal stability: every principal's acknowledged frontier ⊇ the delete and no client may still author against a base older than the delete. The server knows acks (6.1), but offline clients within E-B2's limit can still reference them; a rule like "after the offline limit, a client must re-base before authoring" would allow it.
  • [open question] Epoch GC: when a SetContent (flip) wins, the old epoch's tree is only needed for history/blame; it can be dropped from head state and rebuilt from the log on demand.

7.11 Performance at D-026 scale

D-026 (decisions): 100k files, 10 GB, files up to 1 GB, 1M ops, 20 concurrent editors, status/record ≤ 1 s.

  • Memory (hypothesis, to be measured): per element run ≈ 40 bytes (interned replica u32 + counter u64 + off u32 + len u32 + parent/side/sibling links in an arena, u32 each) plus text bytes once. Line-level: one run per hunk per save. 1M TextEdits with ~2 runs each ≈ 80 MB of runs worst case (all files resident); a thin client holds only its sparse set.
  • Replay: insertion via an order-statistic B-tree over runs, O(log n) per run; known technique numbers for comparable designs (eg-walker, Yjs) are millions of runs per second, so 1M text ops replay well under the 1 s open budget measured for structural ops (Performance #33). Large files are bounded by TEXT_MAX (7.1): > 8 MiB stays bytes, so the 1 GB D-026 file never enters the CRDT.
  • Snapshot (#33) (implemented in #54 as A.2.9: each epoch's seed is referenced by blob id and length, never copied; inserted bytes, tombstones' included, are read back from the op records, because loser blobs and materialize(V) need them until 7.10 GC exists). B5 target [decided: Planner, #54]: snapshot size ≤ 1.2 × (live inserted bytes + 40 B × runs) + a fixed overhead, open ≤ 1 s (B2). Measured (#54, 1M TextEdits over 10k files): 100.3 MiB (0.93 of the bound), open 0.66 s. Seed blobs referenced by a snapshot or a live TextDoc are pinned against cache eviction (Online-First 6.2.5, #47 E-B3; implemented in O2). The first #54 version copied the seeds (1078 MiB for B2, a second copy of the blob store) and missed it. v2 snapshot payload adds per text node: winning epoch id, runs (ids, tree links, tombstone flag), and the live bytes (or a reference to the epoch blob plus inserted bytes). Size ≈ live text + 40 B/run.
  • Thin-client fetch unit (6.13 Q1/Q2) [decision-proposal]: Q1: for a text file, the unit is its compact TextState at base B (live bytes + run table, tombstones without bytes) plus the node's text ops in W; bound: ≤ live size + 40 B × runs; if the run table exceeds 4× the live size the server sends a re-epoch hint (an [open question]: an explicit compaction op that starts a new epoch with the same text, losing merges with old-base concurrent edits, so not automatic). Q2: text ops of files outside the sparse set are kept in W as id + h(o) only (enough for D_r(W), 6.7); bodies are fetched with the file.
  • Bench plan (new hub-bench scenarios, results to Performance): B1 replay of the public automerge-perf editing trace (char-level, 260k ops) and its line-level conversion: ≤ 0.5 s, ≤ 100 MB; B2 1M TextEdits over 10k files of 2–200 KiB: open ≤ 1 s with snapshot, record ≤ 1 s; B3 20 concurrent editors × 500 edits on one 10k-line file, random delivery orders: convergence + p99 integrate ≤ 1 ms per op; B4 record diff of an 8 MiB file with 1% changed lines ≤ 200 ms, worst case (D cap) ≤ 1 s; B5 snapshot size and open time for B2; B6 thin-client fetch unit size for a 1 MiB file after 10k edits.

7.12 Testable properties [decision-proposal]

  1. Convergence under any delivery order: for any op set with text ops and any two causally consistent delivery orders (incremental or sorted fold), content, conflicts and notices are equal (extends 2.6 #3).
  2. No lost insertions: every byte inserted by an Applied TextEdit of the winning epoch is in the materialized text unless some Applied op deletes its element.
  3. Delete precision: an element is invisible iff some Applied delete in the op set covers it.
  4. Intention preservation (FugueMax), for conforming authors (deps = diff base, or the 7.5.1 anchor mapping at deps): an inserted element appears after its left origin and before its right origin in the final list (both may be tombstones), where right is left's successor in the author's full list at deps (7.3.2). Test (R2): histories where a remote insert is inside the op's deps but not in its diff base (server-side diff, 7.5.1 hash-mismatch fallback); the saved run sits immediately after its anchor and before the remote insert. (With deps = V_wd, a remote insert after the checkout is concurrent and ordered by Fugue: ElemId order may put it first.)
  5. Non-interleaving (Review R3): no element of an op concurrent with a run lies between two elements of that run in the final list. A causally later op may insert inside the run (typing in the middle of a line); that is not interleaving. The oracle test checks exactly this wording.
  6. Maximal non-interleaving (FugueMax property, Fugue paper): checked against a brute-force oracle on small histories.
  7. Sequential equivalence: for a single replica, materialize(record(save_1 … save_n)) equals save_n bytes, for random byte-exact texts with mixed \n/\r\n, BOM, missing final newline.
  8. Diff determinism: hub-diff-line/1(base, saved) is a pure function (same ops modulo op id on every run and platform).
  9. Virtual seed agreement: two replicas that each author a first TextEdit on the same pre-upgrade file reference the same element ids; the merge contains no duplicated seed text.
  10. Epoch reduction: with no TextEdit in the op set, content and conflicts equal the §2.3 #18 rule exactly (regression on crates/hub-core/tests/content.rs).
  11. Revive: a TextEdit concurrent with a delete of the file or an ancestor revives it (D-014/D-023) and all concurrent text edits are visible after the revive.
  12. Materialize at any version: materialize(epoch, V) equals the content of a replica that holds exactly V (for random causally closed V), the basis of 7.5.1 and server-side diff.
  13. UTF-8 closure: materialized text is always valid UTF-8; invalid TextEdits are invalid-op deterministically.
  14. Notice determinism: notices are a pure function of the op set and are exactly the overlapping concurrent groups (7.8).
  15. Authoring on the base (Review REPAIR 2; Online-First 6.10 #20): no authoring path (record, watch, live thin client, mutate, rescue, server-side API diff) produces an op whose deps include a same-node content op outside the author's base (index base, or the API's base). Test: deliver a remote SetContent/TextEdit without checkout, save; assert it is not in deps* of the new op and is a loser/merged, never silently overwritten.
  16. Stale-epoch save is visible (R1): wd at epoch S1, remote SetContent S2 not checked out, save → S2 is a content loser (never absent from both head and the conflict set); after checking out S2 first, no conflict.
  17. Anchor adjacency (R2): for every authored TextEdit, each ins.right is the immediate successor of ins.left in the author's full list at deps.
  18. Compatibility gates: a peer without text never receives a TextEdit; a pre-#48 binary refuses a v2 repo before writing (A.2.5-style test with the old binary).

7.13 Worked example: 2 agents + 1 human, one file

Replica ids: agent A1 = 1, agent A2 = 2, human H = 3. File /notes.md (node n), current content set by S = SetContent{n, blob} with id (10,3):

# Plan\n      bytes 0..7    elements (S,0)..(S,6)
- a\n         bytes 7..11   (S,7)..(S,10)
- b\n         bytes 11..15  (S,11)..(S,14)

All three start from version V0 = {…, S} (frontier {S}), concurrently:

  • A1 saves with a line - a1 after - a. Diff: pure insert after line 2. Op (11,1), deps {S}: TextEdit{n, epoch S, del [], ins [{left (S,10), right (S,11), "- a1\n"}]}.
  • A2 saves with a line - a2 after - a. Op (11,2), deps {S}: TextEdit{n, epoch S, del [], ins [{left (S,10), right (S,11), "- a2\n"}]}.
  • H changes - b to - B. Diff: one replaced hunk. Op (11,3), deps {S}: TextEdit{n, epoch S, del [((S,11),4)], ins [{left (S,14), right END, "- B\n"}]} (left = last deleted element, 7.5.2).

Integration (any order; shown in < order (11,1) < (11,2) < (11,3)):

  1. (11,1): (S,10) already has a right child (S,11) (the seed chain), so the run becomes a left child of right = (S,11): list … - a\n | - a1\n | - b\n.
  2. (11,2): same origins; (S,10) has a right child, so it is a left child of (S,11) too; left siblings ordered by ElemId ascending: (11,1) before (11,2). List … - a\n - a1\n - a2\n - b\n.
  3. (11,3): tombstones (S,11)..(S,14); (S,14) has no right child, so - B\n becomes its right child: after the tombstoned - b\n.

Merged text on every replica (and the server), for all 6 delivery orders:

# Plan
- a
- a1
- a2
- B

Conflicts: none (one epoch). Notices: touch((11,1)) ∩ touch((11,2)) ⊇ {(S,10), (S,11)}, and (S,11) is deleted by (11,3), so one notice {kind: concurrent-edit, node n, path "/notes.md", ops [(11,1),(11,2),(11,3)], lines [3,5]} (if E-T2 keeps it on). A later save by anyone with deps ⊇ all three clears it. Variants: (a) if H had instead deleted /notes.md concurrently, the agents' edits revive it (D-014) at /notes.md with text # Plan\n- a\n- a1\n- a2\n- b\n and one edit-revived conflict; (b) if H's editor saved while it still showed V0 after (11,1) had arrived, H's diff base is still materialize(S, V0) (7.5.1), seen = {S}, and H's anchor (S,14) has successor END in H's full list at deps (no remote element follows it), so the op and the result are the same. Likewise, if A2 saved from V0 after (11,1) had arrived but before it was checked out, its deps are its index base V0 (#25), with the same origins as the main example (right = (S,11), adjacent at deps); its id is (12,2) rather than (11,2), because the counter is max_counter(store)+1 and (11,1) is already in A2's store. Since (11,1) < (12,2), the left-sibling order and the result are the main result. The anchor mapping of 7.5.1 matters only for elements inside the author's base that are invisible at the diff base (tombstones) and for a base that differs from the text the diff ran on (the API's server-side diff, a refreshed index). (c) if A2 is a pre-#48 peer, its whole-file save is SetContent (11,2), a new epoch: the greatest content op is (11,3) in epoch S, so the content is # Plan\n- a\n- a1\n- B\n and A2's save is a content loser with its blob (today's behaviour), never silently dropped.

7.14 Escalations (user-facing choices)

  • E-T1 [decided] D-053: Line-level or character-level in the alpha (7.2). Proposal: line-level.
  • E-T2 [decided] D-053: concurrent-edit notice default on/off, and whether identical concurrent edits count (7.8). Proposal: on, identical edits not flagged.
  • E-T3 [decided] D-053: Override syntax: .hubattributes with text/binary (proposal), or a section in .hubignore, or git's .gitattributes names (7.1).
  • E-T4 [decided] D-053: Text size cap 8 MiB and longest-line cap 64 KiB (7.1); hard cap 64 MiB for forced text.
  • E-T5 [decided] D-053: Lazy one-way format v2 upgrade at the first text op: pre-#48 binaries then refuse the repo (7.9).
  • E-T6 [decided] D-053: A server with text ops refuses clients without text (upgrade-required) (7.9).
  • E-T7 [decided] D-056: Checkout/watch auto-records and merges a dirty text file instead of refusing (changes #19/#26 behaviour for text) (7.5.3).
  • E-T8 [decided] D-053: No line-ending normalization (proposal) vs an eol=lf attribute (7.1).

7.15 Open questions

  • Tombstone-id GC under causal stability and the offline limit (7.10); epoch GC.
  • An explicit re-epoch/compaction op for pathological run tables (7.11).
  • Patience/histogram diff (7.5.2); hysteresis around the size cap (7.1).
  • Editor live integration (dirty buffers, range edits for char-level) in VS Code (#41) (7.5.3).
  • loro/diamond-types as dev-only differential oracles (7.2).
  • Whether blame shows principals to everyone (E-B9).
⚠️ **GitHub.com Fallback** ⚠️