The Space Algebra

The mathematical foundation underlying every position, region, span, mapping, and address in Xudanu — explained from the ground up, with diagrams and worked examples.

1. Why an Algebra?

If you look at a document in Xudanu, you might think "position 42" is just a number. But that number needs to do a surprising number of things:

• Identify a specific character in a document
• Be part of a span (positions 3–7) that a link can point at
• Shift when text is inserted before it (position 42 becomes 45)
• Be compared to another position (is this span before or after that one?)
• Be composed into a hierarchical address for federation (server 1, work 5, edition 3, position 2, element 7)
• Be filtered by permission tags (show only content endorsed by club 42)

The space/ module provides a single set of Rust traits — Space, Position, Region, Dsp (displacement), and OrderSpec — that abstract over all these operations. Different concrete implementations handle different needs (integers, reals, tumblers, cross-products).

2. The Four Core Traits

The entire algebra is built on four traits, defined in space/traits.rs:

The four core traits. A Space associates a Position type, a Region type, and a Dsp type.

Here's the Rust trait hierarchy in full:

pub trait Space {
    type Position: Position<Region = Self::Region>;
    type Region:   Region<Position = Self::Position>;
    type Dsp:      Dsp<Position = Self::Position, Region = Self::Region>;

    fn empty_region(&self) -> Self::Region;
    fn full_region(&self) -> Self::Region;
    fn identity_dsp(&self) -> Self::Dsp;
    fn ascending(&self) -> Box<dyn OrderSpec<Position = Self::Position>>;
    fn descending(&self) -> Box<dyn OrderSpec<Position = Self::Position>>;
}

pub trait Position {
    type Region: Region<Position = Self>;
    fn as_region(&self) -> Self::Region;  // singleton
}

pub trait Region {
    type Position: Position<Region = Self>;
    fn is_empty(&self) -> bool;
    fn is_full(&self) -> bool;
    fn contains(&self, pos: &Self::Position) -> bool;
    fn intersects(&self, other: &Self) -> bool;
    fn intersect(&self, other: &Self) -> Self;   // A ∩ B
    fn union_with(&self, other: &Self) -> Self;    // A ∪ B
    fn complement(&self) -> Self;                    // ¬A
    fn minus(&self, other: &Self) -> Self;           // A − B
    fn is_simple(&self) -> bool;   // one contiguous interval?
    fn count(&self) -> Option<usize>;  // None = infinite
}

pub trait Dsp {
    type Position: Position<Region = Self::Region>;
    type Region: Region<Position = Self::Position>;
    fn of(&self, pos: &Self::Position) -> Self::Position;       // move a point
    fn of_all(&self, region: &Self::Region) -> Self::Region;     // move a region
    fn inverse(&self) -> Self;                                     // undo
    fn compose(&self, other: &Self) -> Self;                       // chain
}

3. Position: A Point in Space

A Position is the simplest concept: a single point. In IntegerSpace, it's just a number:

pub struct IntegerPos(pub i64);  // position 42

Every position can be promoted to a singleton region (a region containing just that one point):

impl Position for IntegerPos {
    fn as_region(&self) -> IntegerRegion {
        IntegerRegion::singleton(self.0)  // just {42}
    }
}

In SequenceSpace, a position is a Sequence — a hierarchical tumbler address like 1.5.3.2.7. In CrossSpace2<Integer, Integer>, a position is a pair: Tuple2(IntegerPos(1), IntegerPos(10)).

4. Region: A Set of Points

A Region is a set of positions. It supports all the set operations you'd expect:

The four set operations every Region supports.

// A link points at characters 3–7 in a document
let span = IntegerRegion::interval(3, 7);

// Another link points at characters 5–10
let other = IntegerRegion::interval(5, 10);

// Where do they overlap?
let overlap = span.intersect(&other);    // {5, 6} — interval [5, 7)

// What's the combined coverage?
let combined = span.union_with(&other);   // {3,4,5,6,7,8,9} — interval [3, 10)

// What's in the first span but not the second?
let unique = span.minus(&other);          // {3, 4} — interval [3, 5)

// How many characters?
assert_eq!(span.count(), Some(4));        // 3,4,5,6 (stop is exclusive)

Regions can represent finite spans, infinite ranges, or arbitrary unions of intervals. The is_simple method tells you if a region is a single contiguous interval (most document spans are simple). count() returns None for infinite regions (like above(10) = all positions ≥ 10).

5. Dsp (Displacement): Moving Points

A Dsp (displacement) is a translation. In IntegerSpace, it's just an offset:

pub struct IntegerDsp(pub i64);

impl Dsp for IntegerDsp {
    fn of(&self, pos: &IntegerPos) -> IntegerPos {
        IntegerPos(pos.0.wrapping_add(self.0))  // shift by offset
    }

    fn of_all(&self, region: &IntegerRegion) -> IntegerRegion {
        // shift every point in the region by the offset
        IntegerRegion { inner: region.inner.shift(self.0) }
    }

    fn inverse(&self) -> Self {
        IntegerDsp(self.0.wrapping_neg())  // shift back
    }

    fn compose(&self, other: &Self) -> Self {
        IntegerDsp(self.0.wrapping_add(other.0))  // chain two shifts
    }
}

// A link points at position 10
let link_pos = IntegerPos(10);

// User inserts 3 characters at position 5
let shift = IntegerDsp(3);  // displacement: +3

// The link's position must move to stay correct
let new_pos = shift.of(&link_pos);  // IntegerPos(13)

// Or shift the whole span [10, 20) at once
let span = IntegerRegion::interval(10, 20);
let new_span = shift.of_all(&span);  // interval [13, 23)

Displacements form a group: they have an identity (offset 0), every displacement has an inverse (negate the offset), and composing is associative. This mathematical structure is what makes span migration work reliably.

6. OrderSpec: Sorting Positions

An OrderSpec defines how to sort positions. The simplest are ascending and descending:

pub struct IntegerAscending;
impl OrderSpec for IntegerAscending {
    fn follows(&self, a: &IntegerPos, b: &IntegerPos) -> bool {
        a.0 >= b.0  // a comes after (or equals) b
    }
}

OrderSpecs can be composed: ReverseOrder flips any order, and ChainedOrder uses a secondary order when the primary can't decide.

7. The Transition-Set Trick: How Regions Actually Work

The most clever piece of engineering in the space module is the transition-set representation used by XnRegion (which backs IntegerRegion) and RealRegion. Instead of storing every point in a region, we store the boundaries where the region starts or stops being inside.

The region [5,15) ∪ [25,35) stored as four transition points plus a boolean. Only 5 values instead of 20 individual positions.

The key insight: a region is represented as starts_inside: bool plus a sorted list of transitions: Vec<i64>. At each transition point, you flip between inside and outside. To check if a point is inside, you do a binary search and count how many transitions come before it — if that count is odd, you're inside.

The merge algorithm is deceptively simple: walk both transition lists in sorted order, flipping each region's inside/outside state, and emit a transition in the result only when the combined boolean changes:

// Pseudocode for intersect (AND), union (OR), or minus (AND NOT)
fn merge_transitions(a, b, combine: fn(bool,bool)->bool) -> Region {
    let new_starts = combine(a.starts_inside, b.starts_inside);
    walk both lists in sorted order;
    at each transition, flip the corresponding region's state;
    emit a transition in the result only when combine(a_inside, b_inside) changes;
}

By passing different combine functions, you get all set operations from the same code: |a, b| a && b for intersect, |a, b| a || b for union, |a, b| a && !b for minus.

8. Concrete Space 1: IntegerSpace (Where Documents Live)

IntegerSpace is the workhorse. Every Edition's positions are IntegerPos values. Every document span is an IntegerRegion. Every text-delta displacement is an IntegerDsp.

let space = IntegerSpace::new();

// Positions
let p = space.position(42);           // IntegerPos(42)

// Regions
let span = space.interval(3, 7);      // characters 3,4,5,6
let all_above = space.above(100, true);  // everything >= 100
let all_below = space.below(50, false);  // everything < 50

// Displacements
let shift = space.translation(5);     // IntegerDsp(5) — shift by +5

// Ordering
let asc = space.ascending();          // IntegerAscending
let desc = space.descending();        // IntegerDescending

IntegerRegion is a thin wrapper around XnRegion (defined in edition/xn_region.rs) which implements the transition-set representation described above. The full set of operations is verified by the test suite including De Morgan's laws and double-complement identity.

9. Concrete Space 2: RealSpace (For Fractional Positions)

RealSpace works with f64 positions. This is important for the O-tree CRDT, which needs to insert new positions between existing ones (without renumbering). Real positions allow fractional values like 3.5.

let space = RealSpace::new();
let pos = space.position(3.14159);

// Intervals can have open/closed endpoints
let closed = space.interval(1.0, 5.0, true, true);   // [1.0, 5.0]
let open   = space.interval(1.0, 5.0, false, false);  // (1.0, 5.0)

RealRegion uses the same transition-set trick as XnRegion, but with f64 transitions. The merge algorithm for set operations is identical. Equality uses f64::to_bits() for exact comparison (no epsilon approximation).

10. Concrete Space 3: SequenceSpace (Tumblers & Federation)

SequenceSpace is the most distinctive Xanadu concept. A Sequence is a hierarchical address — what Ted Nelson called a tumbler. Think of it as a dotted path like a file system, but for hypertext:

Sequence::from_dotted("1.5.3.2.7")
// = server 1, work 5, edition 3, position 2, element 7

Internally, a Sequence stores its numbers with zeros as separators:

// "1.5.3" is stored as [1, 0, 5, 0, 3]
// The zeros act as level separators in the hierarchy

Sequences support lexicographic comparison (1.2 < 1.3 < 2.0), addition (plus), subtraction (minus), and hierarchical decomposition (first / rest):

let addr = Sequence::from_dotted("1.5.3.2.7");
let server = addr.first();     // Sequence::one(1)
let rest1 = addr.rest();       // "5.3.2.7"
let work = rest1.first();      // Sequence::one(5)
// ...and so on

Tumbler addressing: every piece of content has a unique hierarchical path across the federated docuverse.

Prefix Regions for Hierarchical Lookup

SequenceRegion supports a special prefixed_by constructor that creates a region matching everything under a given tumbler prefix:

let space = SequenceSpace::new();
let server1 = space.prefixed_by(&Sequence::one(1), 0);

// Matches anything on server 1
server1.contains_sequence(&Sequence::from_dotted("1.5"));     // true
server1.contains_sequence(&Sequence::from_dotted("1.99.42")); // true
server1.contains_sequence(&Sequence::from_dotted("2.5"));     // false

This is how federation routing works: "give me everything under server 1" is a prefix query. The tumbler hierarchy naturally scopes to servers, works, editions, and individual elements.

SequenceDsp: Navigating the Hierarchy

A SequenceDsp has two parts: a shift (which level to move at) and a translation (what to add). This lets you express things like "move to the next work on the same server" or "go to the same position on a different edition":

// Shift at level 2 (the work level): navigate between works
let dsp = SequenceDsp::new(2, Sequence::zero());
let pos = SequencePos(Sequence::from_dotted("1.3.5"));
let shifted = dsp.of(&pos);
// Result: 1.0.1.0.3.0.5 — server becomes 0+1=1, work becomes 0+1=1,
//          but the shift at level 2 means "go to next work at this level"

11. Tumbler Addressing: The Federation Address Book

Tumblers solve a fundamental problem in federated systems: how do you give every piece of content a globally unique address without a central authority? The answer is hierarchical delegation:

10. Concrete Space 4: CrossSpace2 (Two Dimensions)

CrossSpace2<A, B> is the Cartesian product of two spaces. A position is a Tuple2(a_pos, b_pos). A region is a set of "boxes" — pairs of regions from each axis.

let space = CrossSpace2::new(IntegerSpace::new(), IntegerSpace::new());

// A 2D position: (club_id=1, token_id=10)
let pos = space.position(IntegerPos(1), IntegerPos(10));

// A 2D box: clubs 1–5, tokens 10–20
let region = space.box_region(
    IntegerRegion::interval(1, 5),
    IntegerRegion::interval(10, 20),
);

assert!(region.contains(&pos));  // true: 1 is in [1,5), 10 is in [10,20)

Cross-regions support projections — you can extract just one axis:

let club_axis = region.projection_a();  // IntegerRegion [1, 5)
let token_axis = region.projection_b(); // IntegerRegion [10, 20)

CrossSpace2: two-dimensional regions for endorsement (club × token). Boxes can overlap; projections extract one axis.

11. Concrete Space 5: CrossSpaceN (N Dimensions)

When you need 3 or more dimensions, CrossSpaceN provides a dynamic, type-erased version. Each dimension can be Integer, Real, Sequence, or even another Cross:

let space = CrossSpaceN::new(vec![
    CrossSpaceNSlot::integer(),    // dim 0: club ID
    CrossSpaceNSlot::integer(),    // dim 1: token ID
    CrossSpaceNSlot::integer(),    // dim 2: position
]);

let pos = space.position(vec![
    DynPosition::integer(1),
    DynPosition::integer(10),
    DynPosition::integer(100),
]);

Positions are DynPosition values that can be Integer, Real, Sequence, or Composite (nested). This allows runtime-polymorphic multi-dimensional addressing without compile-time generic complexity.

12. Concrete Space 6: FilterSpace (Permission Tags)

FilterSpace is fundamentally different: its "positions" are permission tags, and its "regions" are boolean expressions over tag sets. This is how the canopy filters content by permissions (see Transclusion Engine).

pub enum Filter {
    Full,                 // match everything
    Empty,                // match nothing
    Subset(u64),          // tag must be present
    Superset(u64),        // tag must be present
    Intersection(u64),    // non-empty intersection with tag set
    NotSubset(u64),       // tag must NOT be present
    NotSuperset(u64),     // tag must NOT be present
    And(Vec<Filter>),     // all must match
    Or(Vec<Filter>),      // any must match
}

Filters compose with De Morgan's laws: the complement of an AND is the OR of complements, and vice versa. The match_tag method tests whether a filter passes against a set of tags:

let filter = Filter::and(vec![
    Filter::subset(42),           // must have club 42
    Filter::not_subset(99),       // must NOT have club 99
]);

let tags = vec![42, 100];
assert!(filter.match_tag(0, &tags));  // true: has 42, doesn't have 99

let tags2 = vec![42, 99];
assert!(!filter.match_tag(0, &tags2)); // false: has 99

13. Mappings: Domain-Restricted Displacements

A Mapping is a displacement that only applies within a specific region. This is the key abstraction for span migration, three-way merge, and shared-content detection.

The edition layer defines its own mapping types in edition/mapping.rs, working with raw i64 positions and XnRegion:

pub enum Mapping {
    Empty,
    Simple { offset: i64, region: XnRegion },   // shift by offset, but only within region
    Composite(Vec<Mapping>),                     // multiple piecewise mappings
}

// Original document: positions [0, 20)
// User inserts 5 characters at position 10

// The mapping has two pieces:
let mapping = Mapping::Composite(vec![
    // Characters before position 10: don't move
    Mapping::Simple {
        offset: 0,
        region: XnRegion::interval(0, 10),
    },
    // Characters at position 10 and after: shift by +5
    Mapping::Simple {
        offset: 5,
        region: XnRegion::above(10),
    },
]);

// A link at position 15 needs to move
assert_eq!(mapping.of(15), Some(20));  // shifted to 20

// A link at position 5 stays put
assert_eq!(mapping.of(5), Some(5));    // unchanged

The space layer's SimpleMapping<S> (in space/mapping.rs) generalizes this to any space type, with full support for inverse, restrict, and compose. CompositeMapping chains multiple domain-restricted displacements. ConstantMapping maps any position in a domain to a fixed set of values (useful for default-value regions).

14. Span Migration: How Mappings Keep Links Alive

When text is edited, every link's span needs to be updated so it still points at the right characters. This is called span migration. The server's migrate_link_spans_for_delta method processes each text delta operation and adjusts link spans:

// server.rs:9542
pub fn migrate_link_spans_for_delta(
    &mut self,
    source_work_id: BeId,
    ops: &[TextDeltaOp],  // Retain/Insert/Delete
) {
    for link_id in self.work_to_links.get(&source_work_id) {
        // For each link end pointing at this work...
        if let (Some(start), Some(end)) = (hr.start_position(), hr.end_position()) {
            // Map the old span through the delta operations
            let (new_start, new_end) =
                map_span_through_delta(start, end, &delta_ops);

            // Update the link with the new span
            let new_hr = hr.with_span(Some(new_start), Some(new_end));
            link = link.with_end(&name, new_hr);
        }
    }
}

map_span_through_delta walks the retain/insert/delete operations and computes where the span's start and end positions land. Inserts before the span shift it forward; deletes inside the span shrink it; retains keep it in place.

Span migration: when "Beautiful " (10 chars) is inserted, the link span shifts from [5,11) to [5,21). The mapping encodes this shift.

15. Shared Mappings: Detecting Transcluded Content

SharedMapping (in edition/shared_mapping.rs) is a sparse, position-to-position mapping that connects identical content across editions. It's how Xudanu detects transclusions — content that appears in multiple documents.

The algorithm fingerprints each element by its content hash, then builds a mapping from positions in one edition to positions with the same content in another:

pub fn content_map_shared_onto(
    my_entries: &[(i64, Carrier)],
    other_entries: &[(i64, Carrier)],
) -> SharedMapping {
    // Build a lookup: content_fingerprint → positions in other edition
    let by_fingerprint: BTreeMap<[u8;8], Vec<i64>> = ...;

    // For each of my entries, find matching positions
    for (pos, carrier) in my_entries {
        let fp = carrier.element.content_fingerprint();
        if let Some(other_positions) = by_fingerprint.get(&fp) {
            pairs.push((*pos, other_pos));  // map my pos → their pos
        }
    }
    SharedMapping::from_pairs(pairs)
}

content_shared_region does the simpler version: just return the region of positions in my edition that also appear in the other edition (without the position-to-position mapping). This is used by the transclusion index to identify overlapping content.

16. The Compactor: Squeezing Gaps Out of Regions

Sometimes you need to take a sparse region (e.g., positions [0,5) ∪ [10,15) ∪ [20,25)) and "compact" it into a dense region [0,15) where the gaps are removed. The compactor() method on XnRegion does exactly this:

impl XnRegion {
    pub fn compactor(&self) -> Mapping {
        let mut mappings = Vec::new();
        let mut end = 0;
        for (start, stop) in &self.intervals() {
            let offset = end - start;  // how far to shift this interval
            mappings.push(Mapping::restricted(offset, XnRegion::interval(*start, *stop)));
            end += stop - start;
        }
        // Returns a Composite mapping that shifts each interval down
    }
}

// Interval [0,5):   offset = 0 - 0 = 0,  maps to [0, 5)
// Interval [10,15): offset = 5 - 10 = -5, maps to [5, 10)
// Interval [20,25): offset = 10 - 20 = -10, maps to [10, 15)
// Result: compact region [0, 15)

// The compactor returns the MAPPING, not just the region.
// You can apply it to positions or use its inverse to expand back.

17. Order Combinators: Reverse and Chain

ReverseOrder wraps any OrderSpec and reverses it:

impl<P: Position> OrderSpec for ReverseOrder<P> {
    fn follows(&self, a: &P, b: &P) -> bool {
        self.inner.follows(b, a)  // swap arguments!
    }
}

ChainedOrder uses a primary order, falling back to a secondary order when the primary can't decide (returns None from compare):

impl<P: Position> OrderSpec for ChainedOrder<P> {
    fn follows(&self, a: &P, b: &P) -> bool {
        match self.primary.compare(a, b) {
            Some(Greater | Equal) => true,
            Some(Less) => false,
            None => self.secondary.follows(a, b),  // fallback
        }
    }
}

18. Arrangement: Sorted Positions for Rendering

Arrangement<P> is a utility that takes a set of positions, sorts them by a comparison function, and provides indexed access. It's used for rendering content in order and for efficient slicing:

let arr = Arrangement::new(|a: &i64, b: &i64| a.cmp(b), vec![50, 30, 10, 40, 20]);
assert_eq!(arr.position_at(0), Some(&10));  // sorted
assert_eq!(arr.slice(1, 4), &[20, 30, 40]); // range access

19. How Everything Connects

The space algebra flows from abstract traits (top) through edition-layer implementations (middle) to application features (bottom).

20. Source Code Map