The Ent, DagWood & Trace DAG

The versioning spine adapted from the original Udanax-Gold C++ code: partial-order positions, branch topologies, the navigation cache, assertion-based content, and conflict-preserving materialization.

1. Heritage: From Udanax-Gold to Rust

The ent/ module is one of the most direct lineages from the original Udanax-Gold C++ codebase. The original source files—entx.hxx, dagwoodx.hxx, tracepx.hxx, branchx.hxx—defined a partial-ordering data structure called a trace DAG that tracked the history of every edit, fork, and merge in a Xanadu document.

Xudanu preserves this architecture faithfully. Every struct and method carries [Original] and [Adapted] comments citing the exact C++ source line numbers. The three C++ class hierarchies—Ent, DagWood, and BranchDescription—become Rust structs with the same names (modulo CamelCase-to-snake_case conventions).

2. The Three Layers

The ent/ module has seven files organized into three conceptual layers:

The three layers: versioning spine (blue/green), content model (purple), and bridge to the Edition world (amber/cyan).

3. TracePosition: The Coordinate

Every point in the version history is identified by a TracePosition: a pair of a BranchId and a u32 position within that branch.

pub struct TracePosition {
    branch: BranchId,    // which branch of the DAG
    position: u32,       // how far along the branch
}

This replaces the original C++ BoundedTrace class hierarchy. The original had an abstract TracePosition with one concrete subclass; the Rust version collapses to a single struct since "only one concrete subclass existed in the original" (tracepx.hxx lines 57–204).

4. BranchKind: Root, Tree, Dag

The original C++ had three subclasses of BranchDescription: RootBranch (no parents), TreeBranch (one parent), and DagBranch (two parents). In Rust, these become a single enum:

pub enum BranchKind {
    Root,
    Tree { parent: TracePosition },
    Dag  { parent1: TracePosition, parent2: TracePosition },
}

The three branch topologies. A Dag branch has two parents and is the mechanism for merge points.

Each Branch also maintains:

• last_position: u32 — the highest position allocated on this branch (starts at 2).
• left / right: Option<BranchId> — a binary tree of child branches (see Section 9).

5. Position Numbering: Why Position 3?

One of the most subtle aspects of the DagWood is its position numbering. Every new DagWood starts with a root branch, then immediately creates a trunk branch:

// dagwood.rs constructor
let (root_branch_id, root_pos) = branches.create_root();  // root at position 1
let _ = dagwood.create_after(root_branch_id, root);       // trunk branch created

The numbering convention is:

6. The Partial Order: is_le and Visibility

The DagWood defines a partial ordering of TracePositions. is_le(a, b) returns true if position a is "less than or equal to" position b—meaning a is an ancestor of (or identical to) b in the DAG.

This is the fundamental semantic operation. It answers: "Does the history leading to b include everything at a?" If yes, then content written at a is visible from b.

A fork-and-merge DAG. Positions A and B are incomparable (neither is_le the other). Merge point M has both as ancestors.

The partial order satisfies three properties that the test suite verifies exhaustively on random DAGs (tests D26–D29):

• Reflexivity: is_le(p, p) = true
• Antisymmetry: is_le(a,b) && is_le(b,a) ⇒ a == b
• Transitivity: is_le(a,b) && is_le(b,c) ⇒ is_le(a,c)

7. The Navigation Cache: Max-Over-Paths

The naive way to compute is_le(a, b) is to walk upward from b through parent links and check if you reach a's branch. But this is O(branches) per query, and repeated queries re-traverse the same paths.

The original Udanax-Gold code solved this with a navigation cache that stores, for each branch reachable from the reference position, the maximum position visible on that branch. The key insight is the max-over-paths invariant:

The algorithm has three pieces, mirroring the original cacheIn / cacheRecur methods:

cache_in_into(pos)

For a given position (branch, pos):

• If branch is not yet visited (None in cache): store pos, then recurse to parents.
• If already visited: update to max(old, pos), no recursion.

cache_recur_into(branch_id)

Follows the branch topology:

• Root → stop (the recursion ends here).
• Tree { parent } → cache_in_into(parent).
• Dag { parent1, parent2 } → recurse into both parents.

is_le(a, b)

// Step 1: cache b's upward reachability
self.cache_trace_pos(b);

// Step 2: check if a's branch is reachable with a.position <= cached max
match self.nav_cache.get(&a.branch()) {
    Some(&mark) => a.position() <= mark,
    None => false,
}

// Structure:
//   trunk: root → pos3 → pos4 → pos5
//   fork from pos3 → Y (pos 3)
//   fork from pos4 → Z (pos 3)
//   merge(Y, Z) → W (pos 3)

// Path W → Z → trunk enters at position 4
// Path W → Y → trunk enters at position 3
// Cache[trunk] = max(3, 4) = 4

// Therefore:
is_le(trunk_pos3, W) = true   // 3 <= 4
is_le(trunk_pos4, W) = true   // 4 <= 4
is_le(trunk_pos5, W) = false  // 5 > 4  ← not visible!

Two paths converge at W. The cache stores the maximum entry position (4), not the minimum.

8. TraceView: The Read Face

TraceView is a frozen snapshot of visibility from a single reference position. It owns its own navigation cache, independent of DagWood's mutable internal cache:

pub struct TraceView {
    reference: TracePosition,
    nav_cache: HashMap<BranchId, u32>,
}

This is important for concurrent reads: multiple TraceViews can exist simultaneously without interfering with each other or with DagWood's internal cache used by is_le. Test V2 verifies this independence explicitly.

The TraceView API:

9. The Branch Binary Tree: install_branch

When a new branch is forked off from an existing position, it must be registered as a child of that position's branch. The original Udanax-Gold code used a peculiar insertion algorithm that builds a binary tree of branches with a swap-after-recurse pattern:

pub fn install_branch(&mut self, parent_id: BranchId, child_id: BranchId) {
    if parent_id == child_id { return; }       // identity guard

    // If left slot is empty, install there
    if parent.left.is_none() {
        parent.left = Some(child_id);
        return;
    }

    // Left is occupied: recurse into left child, THEN swap left/right
    let left_child = parent.left.unwrap();
    self.install_branch(left_child, child_id)?;

    // The swap (not a standard rotation!)
    let tmp = parent.left;
    parent.left = parent.right;
    parent.right = tmp;
}

This binary tree of branches is stored in the trunk map, which maps TracePosition → BranchId. When new_position() is called, it creates a new branch as a child of the root and registers it in the trunk.

10. AssertionPayload: The 13 Operations

On top of the versioning spine sits the content model. Content is expressed as a log of assertions—immutable, append-only operations stamped with a TracePosition. There are 13 payload types:

Each assertion is stored with its TracePosition:

pub struct Assertion {
    pub id: AssertionId,
    pub position: TracePosition,   // WHERE in the version DAG
    pub payload: AssertionPayload, // WHAT was done
}

11. AssertionStore and Visibility Filtering

The AssertionStore is a simple append-only log:

pub struct AssertionStore {
    assertions: Vec<Assertion>,
    next_id: u64,
}

The sole filtering mechanism is visibility. Given a TraceView, the store returns only assertions whose position is visible from the view's reference:

pub fn visible_assertions<'a>(&'a self, view: &TraceView) -> Vec<&'a Assertion> {
    self.assertions
        .iter()
        .filter(|a| view.is_visible(a.position))
        .collect()
}

12. Materialization: History Determines Meaning

materialize_document turns a flat assertion log into a tree structure (nodes containing spans and annotations). The process:

1. Filter assertions by TraceView visibility.
2. Build a VisibleIndex — O(1) lookup HashMaps by entity ID.
3. Recursively materialize the root node, its children, their spans, and annotations.

For single-valued properties (like span text or child ordinals), when multiple assertions exist on the same branch, the one at the highest position wins (last-writer-wins within a branch). This is how sequential edits work: position 4 overrides position 3 on the same branch.

// Within a single branch, latest position wins
fn collect_span_text_indexed(idx: &VisibleIndex, span_id: SpanId) -> AlternativeSet<String> {
    let mut per_branch: HashMap<BranchId, (u32, String)> = HashMap::new();

    for assertion in idx.set_span_text.get(&span_id) {
        let branch = assertion.position.branch();
        let pos = assertion.position.position();
        // Latest position on each branch wins
        if pos > existing_pos { per_branch.insert(branch, (pos, text)); }
    }
    // ...
}

13. AlternativeSet: Conflict Preservation

This is where the DagWood's conflict-preservation philosophy becomes visible. When two branches diverge and then merge, both versions of a span's text are visible. The materializer does not pick one. Instead, it returns an AlternativeSet:

pub enum AlternativeSet<T> {
    Single(T),              // no conflict: one value
    Alternatives(Vec<T>),   // conflict: all visible divergent values
}

Two branches set different text for the same span. After merge, both values are preserved as alternatives. The system never silently discards either.

This is the philosophical heart of the system. Unlike Git (which requires manual conflict resolution) or operational transforms (which merge automatically but may lose intent), the DagWood preserves all divergent states and lets the consumer decide what to present. The frontend can show alternatives side-by-side, offer a choice, or apply a merge strategy—but the data layer never throws anything away.

14. The H-Tree: Linking Trace to Canopy

The H-Tree (history tree) connects the trace DAG to the canopy — the hierarchical crum structure used for filtered queries (see Transclusion Engine for canopy details).

Each HUpperCrumData node sits at a TracePosition and holds:

• hcut: TracePosition — where in the version history this crum lives
• bert_crum: Arc<CanopyCrumData> — the corresponding canopy crum (permissions/endorsement flags)
• o_parents: Vec<Arc<dyn HPart>> — parent crumbs in the H-tree

The H-tree enables delayed_store_backfollow — a filtered backward traversal through version history. Starting from a crum, it walks parent links, applying a PropFinder filter at each level. Only crumbs whose permission flags pass the filter are visited:

pub fn delayed_store_backfollow(
    crum: &Arc<Mutex<HUpperCrumData>>,
    finder: &PropFinder,
    hcrum_cache: &mut HashSet<u32>,   // cycle prevention
    visitor: &mut dyn FnMut(&Arc<Mutex<HUpperCrumData>>),
) {
    // Skip if already visited (by hash)
    if hcrum_cache.contains(&hash) { return; }
    hcrum_cache.insert(hash);

    // Narrow the filter by this crum's flags
    let new_finder = finder.pass(crum_flags);
    if new_finder.is_empty() { return; } // filter closed: nothing more matches

    visitor(crum);  // visit this crum

    // Recurse into parents
    for parent in &o_parents {
        Self::delayed_store_backfollow(parent, &new_finder, cache, visitor);
    }
}

15. BackfollowEngine: Bridging Ent to Editions

The BackfollowEngine (in edition/backfollow.rs) is the bridge between the ent DAG world and the Edition/O-tree world. It owns:

pub struct BackfollowEngine {
    transclusion_index: TransclusionIndex,
    bert_canopy: BertCanopy,
    sensor_canopy: SensorCanopy,
    dagwood: DagWood,                    // ← the ent DAG
    assertion_store: AssertionStore,     // ← the content model
    edition_metas: HashMap<u64, EditionMeta>,
    fingerprint_to_works: HashMap<[u8;32], HashSet<u64>>,
    work_spans: HashMap<u64, Vec<SpanId>>,
    // ...
}

When a work is registered, the engine:

1. Allocates a TracePosition in the DagWood (dagwood.new_position())
2. Creates an H-crum at that position with the work's permission flags
3. Calls bridge_edition_to_assertions to translate the Edition's O-tree content into assertions

The bridge translates each O-tree entry into CreateSpan + SetSpanText + AttachSpanToNode assertions:

fn bridge_edition_to_assertions(&mut self, work_id: u64, edition: &Edition, tp: TracePosition) {
    let node_id = DocumentId::new(work_id).node_id();

    // First time: create the document node
    if first_time {
        self.assertion_store.add(tp, AssertionPayload::CreateNode {
            node_id, kind: "document".into(),
        });
    }

    // For each O-tree entry, create/update a span
    for (i, (_, carrier)) in edition.all_entries().iter().enumerate() {
        let span_id = spans[i];
        let text = carrier.element.as_text().unwrap_or("");
        self.assertion_store.add(tp, AssertionPayload::SetSpanText { span_id, text });
    }
}

This means the Edition model (per-line attribution, O-tree positions) and the ent model (assertions, visibility, alternatives) are two views of the same data. The Edition is the "fast path" for current-state access; the ent DAG is the "history path" for version-aware queries and cross-work materialization.

The bridge is bidirectional. Editions are translated into assertions (forward); assertions are materialized back into documents (reverse).

16. WASM Bindings: DagWood in the Browser

The wasm.rs module exposes the DagWood, TraceView, and AssertionStore to JavaScript via wasm-bindgen. The wrappers are thin:

// JavaScript-callable API
let dw = WasmDagWood.new();
let pos1 = dw.new_position();
let pos2 = dw.new_position_after(pos1);
let merged = dw.new_successor_after(pos1, anotherPos);

let view = dw.trace_view(merged);
console.log(view.is_visible(pos1));   // true

let store = WasmAssertionStore.new();
store.add(pos1, JSON.stringify({
    CreateNode: { node_id: 1, kind: "document" }
}));

let doc = store.materialize_document_json(view, 1);
// → JSON tree of MaterializedNode → MaterializedSpan → MaterializedAnnotation

The assertion payload is passed as a JSON string and parsed into AssertionPayload internally. This means the full assertion model is available in the browser without recompiling—the same Rust code runs in the server and in WASM.

17. Properties Proven by the Test Suite

The ent/ module has one of the most rigorous test suites in the codebase. Beyond unit tests, it includes property-based tests on randomly generated DAGs and stress tests at scale:

18. Source Code Map