Editions & Works

The fundamental data model of Xudanu: how documents are stored, edited, attributed, and optimized — from a single character to a 1 MB book.

1. The Core Model: Works and Editions

Everything in Xudanu is a Work. A work is a named, versioned document — like a wiki page, a chapter of a book, or a collaborative note. Works are the unit of sharing, permissioning, and federation.

A Edition is an immutable snapshot of a Work's content at a point in time. Every time you edit a Work, you produce a new Edition. The server tracks the current Edition and (optionally) previous ones for history and three-way merging.

Figure 1: A Work contains Editions. Each Edition holds an O-tree of elements, endorsement metadata, and signed provenance spans.

The key relationship: a Work is the identity (who can see it, what it's called). An Edition is the content (what it says right now). The server maintains a current_edition on each Work and updates it atomically after each edit is applied.

Source Code Map

2. The O-Tree: How an Edition Stores Its Elements

An Edition's content lives in an O-tree — a splay-tree structure originally designed for the Udanax-Gold hypertext system. Each element is stored at an integer position (0, 1, 2, ...) in a OrglRoot, which wraps a splay tree of Loaf nodes.

The O-tree is not a B-tree or a trie. It's a splay tree: every time you access a position, the tree reorganizes itself to make that position (and its neighbors) faster to access next time. This means:

• Accessing the same region repeatedly is amortized O(1)
• Sequential access (positions 0, 1, 2, 3...) is extremely fast after the first access
• Random access to distant positions costs O(log n) on first touch, then accelerates

Figure 2: The O-tree organizes elements (Carriers) into a splay tree. Accessing an element reorganizes the tree to optimize future nearby accesses.

The tree nodes are called Loaf (a Xanadu term). There are three variants:

The Dsp variant is particularly clever — it allows inserting or removing elements without renumbering every position in the tree. When you insert a character in the middle of a document, the tree creates a Dsp node that shifts subsequent positions by +1. Only the path to the insertion point is modified.

3. The Splay Mechanism: Self-Optimizing Access

The splay tree is the heart of the O-tree's performance. Understanding how it works is essential for anyone working on the edition layer.

What Is a Splay Tree?

A splay tree is a self-adjusting binary search tree. Unlike balanced trees (AVL, Red-Black) that maintain strict invariants after every operation, a splay tree does no explicit rebalancing. Instead, every time you access a node, you splay it — rotate it up to the root using a sequence of zig, zig-zig, and zig-zag rotations.

This has a remarkable property: the most recently accessed elements are always near the root. For text editing — where you typically edit the same paragraph for a while before jumping elsewhere — this is near-optimal behavior.

Figure 3: Splay rotation brings the accessed node to the root. Subsequent nearby accesses become O(1).

Splay Operations

The splay operation uses three rotation patterns depending on the node's position relative to its parent and grandparent:

The amortized cost of any splay operation is O(log n), but the static optimality property guarantees that a sequence of m accesses on a tree of n items costs O(m + n log n) — within a constant factor of the optimal binary search tree for that access pattern.

4. RangeElement and Carrier: What Lives Inside an Edition

Each position in an Edition holds a Carrier, which wraps a RangeElement. The Carrier adds metadata (label, provenance) to the raw content.

Figure 4: A Carrier wraps a RangeElement with metadata. The Text variant's string can be any length — 1 char or 500 chars.

The RangeElement::Text { text: String } variant is special: it can hold any number of characters in its string. This is not a design afterthought — it's the foundation of the run-length carrier optimization (Section 5).

Each Carrier also carries:

• label — an optional RangeElementId used for Xanadu-style labeling and deep linking
• provenance — an optional ElementProvenance recording who created this element, when, and whether they're human or LLM (see Section 7)

The char_len() method on Carrier returns how many characters the element represents. For a per-character element, this is 1. For a per-line element, this might be 55. This method is the bridge between the element-position world (the O-tree) and the character-position world (text deltas).

5. Building an Edition: Per-Character vs Per-Line

When text arrives at the server — from a client creating a document, from federation, or from a checkpoint restore — it must be converted into an Edition. There are two ways to do this.

The Old Way: from_text() — One Element Per Character

The original implementation created one Carrier per character. The text "Hello\nWorld" produced 11 elements:

H  e  l  l  o  \n  W  o  r  l  d
0  1  2  3  4   5  6  7  8  9  10    ← positions

Each of those 11 elements is a 184-byte Carrier struct, wrapped in an 8-byte Arc, holding a heap-allocated String of one character. For a book-sized text (~854 KB), that's 865,208 elements — over 162 MB of heap just to store 854 KB of text, a 190x inflation.

The New Way: from_text_batched() — One Element Per Line

The run-length carrier optimization batches text by splitting on newlines. Each line (including its trailing \n) becomes a single element. The same text now produces just 2 elements:

"Hello\n"    "World"
   0            1        ← positions

For that same 854 KB book, this produces only 4,515 elements instead of 865,208 — a 193x reduction in element count.

Figure 5: The same text stored as per-character elements vs per-line elements. For a book, the difference is 163 MB vs 1.7 MB.

Why Per-Line?

Lines are the natural boundary for text editing. Most edits happen within a line. Splitting on \n gives elements that are:

• Stable — an edit on line 5 doesn't change line 3's element
• Reasonably sized — average prose line is ~55 characters
• Preservative of edit fidelity — the delta protocol operates on character offsets and can split any element at any character boundary (see Section 6)

6. Editing: Deltas, Splits, and Character-Level Precision

When a user types in the editor, the React frontend computes a text delta — a sequence of retain, insert, and delete operations expressed in character offsets. The delta is sent to the server via WebSocket, where apply_text_delta_to_edition() applies it to the current Edition.

The challenge: deltas work on character positions, but elements are at element positions. The bridge is the entry_char_start table — a cumulative offset array that maps character positions to element positions.

Figure 6: A character-level delta splits a per-line element, applies the edit, and coalesces the fragments back together.

The split_text_carrier() Function

When a delta boundary falls inside an element (e.g., "delete character 8" inside a 12-character element), split_text_carrier() extracts a substring by:

1. Converting the character offsets to byte offsets (UTF-8 safe)
2. Slicing the source string
3. Creating a new Carrier with the slice, inheriting provenance from the parent

This means edits always work at character precision, regardless of how the elements are batched. The batching is an invisible optimization — the user (and the delta protocol) never see it.

7. Attribution: Who Wrote What

Xudanu tracks who created every element in a document. This is not revision history (which tracks snapshots over time) but fine-grained, per-element attribution — every piece of text knows which user (or AI model) wrote it, and carries a cryptographic signature to prove it.

ElementProvenance

Each Carrier can carry an ElementProvenance struct:

ElementProvenance {
    author_public_key: [u8; 32],      // Ed25519 public key
    author_display_name: String,       // "alice" or "gpt-4"
    author_club_id: u64,               // identity group
    timestamp: u64,                    // Unix seconds
    author_type: AuthorType,           // Human | Llm
    llm_model: Option<String>,        // "gpt-4o" etc for LLM content
}

Human vs LLM Attribution

The AuthorType enum distinguishes between human-written and AI-generated content. In the UI:

• Green overlay — human-authored text
• Purple (#7c4dff) overlay — LLM-generated text

Figure 7: The attribution canvas overlays color on each element. Adjacent elements with different provenance stay separate.

How Attribution Gets Attached

When a user sends a delta, the server looks up their identity (public key, display name, club ID) from the session and creates an ElementProvenance. Every element created by the delta (insertions, splits) inherits this provenance. For LLM operations (narration, writing feedback), the provenance uses a zeroed public key with the model name as display name and AuthorType::Llm.

Span-Level Signatures

Beyond per-element metadata, Xudanu supports SpanProvenance — cryptographically signed proofs that a range of elements was authored by a specific key. A span is defined by:

1. Collecting the BLAKE3 fingerprints of all elements in the span
2. Computing a combined fingerprint
3. Signing it with the author's Ed25519 private key

This makes attribution tamper-evident: you can verify that a specific author signed a specific range of content, even after the document has been edited elsewhere.

8. The Cost of Attribution (and How We Reduced It)

Attribution is powerful but has a cost. Every element with provenance carries an additional ~63 bytes (32-byte key + display name + club ID + timestamp + type tag). With per-character storage, this is catastrophic.

The Numbers

Our benchmark measures real memory usage for an 854 KB book-sized text:

Figure 8: Memory comparison for a book-sized document. The per-character approach inflates 854 KB to 212 MB; per-line brings it to 1.9 MB.

9. Coalescing: Re-Merging Fragmented Elements

Editing splits elements. When you insert a character in the middle of a line, split_text_carrier() breaks the line into two or three fragments. Over time, this fragmentation accumulates — each edit potentially adding one or two extra elements.

Coalescing is the reverse operation: after applying a delta, we scan adjacent elements and merge any that share the same provenance and label back into a single element. This is done by Edition::coalesce().

How Coalescing Works

The algorithm is a single linear pass over the element list:

1. Start with the first element
2. If the next element has the same provenance and same label and is also Text, concatenate their strings
3. Continue until you hit a boundary (different provenance, different label, or non-Text element)
4. Emit the merged element, advance, repeat

Figure 9: Coalescing merges adjacent elements with matching provenance into single, larger elements.

When Coalescing Happens

Coalescing is called automatically after every delta application and LLM text append. The cost is a single linear scan over the element list — for a 4,515-element book, this takes about 650 microseconds. The benefit is that fragmentation from edits is cleaned up immediately, keeping the element count close to the optimal per-line baseline.

What Coalescing Cannot Merge

Elements with different provenance will never be merged. This is correct behavior — it preserves the attribution boundary. If Alice writes "Hello " and GPT-4 writes "world", those are two elements, and coalescing respects that. The attribution boundary is structural, not just metadata.

Similarly, elements with different labels (used for Xanadu deep linking) won't be merged, because the label identity must be preserved for transclusion queries.

10. The Complete Lifecycle: Create, Edit, Attribute, Coalesce

Let's trace the complete lifecycle of a document from creation through several edits by different users and an AI, showing how each optimization interacts.

Figure 10: The complete lifecycle of a document through creation, editing, AI attribution, and concurrent merging.

The Interaction Between All Three Optimizations

The three optimizations work together as a pipeline:

The splay tree ensures that the elements being edited are always fast to access. Batching ensures there aren't too many elements in the first place. Coalescing ensures that splits from edits don't accumulate over time. Together, they keep a document's element count close to its line count, regardless of how many edits have been applied.

Key Takeaways for Developers

• Use from_text_batched() for all production text. It's the default in all server paths now.
• Don't worry about element count. Coalescing runs after every delta. The count stays near-optimal.
• Attribution boundaries are structural. Two adjacent elements with different provenance won't coalesce. This is correct — it preserves the visual color boundary in the UI.
• The splay tree adapts to your access pattern. No configuration needed. If you're iterating over all elements, consider using all_entries() which caches the result.
• char_len() is your friend. When you need to convert between character positions (from the UI) and element positions (in the tree), use char_len() to compute cumulative offsets.