The Math

draft

The Math half of XTXP defines what every implementation of Xmesh must compute. Implementations are free in how they compute it. They must agree on what comes out, down to the SHA-256 of the canonical XML.

Requirements

1. Convergence. Peers that have seen the same set of operations hold the same document, whatever order those operations arrived in.
2. Intent preservation. An attribute change and a concurrent child insertion on the same element both survive. In v1, not yet across a move: see moves.
3. No cycles. Concurrent moves can never make an element its own ancestor.
4. No central authority. Merging needs no server to decide order.

Built on Yrs

The first implementation of Xmesh is a thin layer on Yrs, the Rust port of Yjs, using Yrs’s own XML types. Yrs already provides the hard, well-tested parts: XML elements, attributes and text, YATA ordering, state vectors, a compact binary update format, and snapshots. Xmesh adds what XTXP needs on top:

• mapping every XML node kind onto Yrs’s XML types
• XML Patch translation, from UI actions to Yrs operations
• canonical XML output, for hashing and rendering

Building v1 on a stable, open implementation is deliberate: make something, get feedback, understand it, then make the next thing. A foundation that has already stabilised saves time and effort that a fresh design would spend rediscovering its problems. Where it falls short, the gaps are written down (moves) and the next design is ready to reflect on.

Xmesh stays a pure core: no networking, no files, no clocks. See decision 13.

Data model

Select the diagram to view it full screenPlantUML source

decided for v1 (decision 20)

The document is a Yrs XML fragment holding the root element.

XML	Yrs type	Notes
Element	XML element	Its tag is the expanded name, namespace URI plus local name, such as {http://www.w3.org/2000/svg}circle.
Attribute	attribute on the XML element	Keyed by expanded name, such as {http://www.inkscape.org/namespaces/inkscape}label. Last writer wins per attribute.
Text	XML text	Mixed content, as in SVG’s <text> and <tspan>, comes for free.
Comment, processing instruction, CDATA	XML element with a reserved name	Yrs has no types for these, so each is an element in an XTXP namespace holding its text. Inkscape’s XML still maps across in full; the exact encoding is settled in M1.

• Node IDs need no coordination. A node’s ID is the Yrs ID of the item that created it: client ID plus counter. Client IDs are fresh per session and connection, so IDs never collide.
• Namespaces are stored expanded. Prefixes such as inkscape:, sodipodi: and xlink: are chosen only when writing XML out, by the canonical form.
• Genesis is one fixed update. Every document starts from the same initial update that creates the root, identical byte for byte everywhere, so two peers can never create two different roots.
• Deletion is a Yrs delete. The element and everything under it leave the current document. History keeps them, because garbage collection is off, so undo and earlier snapshots can bring them back. Edits that arrive inside a deleted element aren’t shown.

Ordering

Yrs orders concurrent insertions with YATA (Yet Another Transformation Approach), for an element’s children and for text alike. Each insertion remembers the neighbours it went between, and ties are broken by client ID, so two people inserting at the same spot at the same time get the same order on every peer.

Immortal parents

Within an element, edits never replace it:

• its attributes are updated one at a time, last writer wins per attribute
• new children are inserted into it alongside what’s there

Setting @fill="blue" updates one attribute. The <circle> keeps its identity, so a concurrent edit to the same circle still has something to land on, and an attribute change and a concurrent child insertion on the same element both survive.

Moves in v1: a copy

decided for v1, with known gaps

Yrs’s XML types have no move. In v1, moving an element deletes it and inserts a copy at the new place, in one transaction. Reordering among siblings, such as raising or lowering a shape, is a move too.

Concurrent moves can’t form a cycle, because a move makes a copy rather than rewiring a parent. The cost is three known gaps, kept as expected failures in the test vectors so they stay visible:

1. An edit made during a move goes to the original. If Alice moves a group while Bob changes its fill, Bob’s change lands on the deleted original and doesn’t appear on Alice’s copy.
2. Two concurrent moves make two copies. If Alice moves G into A while Bob moves it into B, G appears twice.
3. Moving a large group costs its full size, because the subtree is copied.

So in v1, requirement 2 (intent preservation) doesn’t yet hold across a move.

Later: a tree layer of our own

draft · to reflect on after M2

Two designs are on the table for closing the gaps.

A “moved to” link, like an HTTP 301. The deleted original records where its copy went, and readers follow the link: edits that landed on the original after the move are folded into the copy, and when an element was moved twice at once, one copy is shown, chosen the same way on every peer. This has to happen when the tree is read, not by copying edits across, or every peer that noticed would copy them and children would arrive several times. Reading edits inside a deleted element means working with Yrs’s history rather than its normal API.

A node map with cycle-safe moves, after Evan Wallace’s mutable tree algorithm (prior art). Each node keeps a map of every parent it has had, each with a counter and a position; a move is a map write, and reading the tree resolves cycles deterministically:

Select the diagram to view it full screenPlantUML source

1. The root (from genesis) is rooted.
2. Give every other node its preferred edge: highest counter, then lowest parent node ID.
3. Follow preferred edges. Every node whose chain reaches the root is rooted, at its preferred edge.
4. Take the nodes that aren’t rooted. They are caught in cycles. Go through them in ascending node ID order (client ID, then counter). For each one, take its best edge whose parent is now rooted. If it has one, it is rooted there; then root any nodes whose preferred edge leads to it.
5. Repeat step 4 until every node is rooted. This always ends, because every node’s first edge, from when it was created, points to a parent that existed before it.
6. Within each parent, order children by the position on their chosen edge, a fractional key ending in the client ID.
7. Hide deleted nodes and everything under them.

The yrs_tree crate implements Wallace’s algorithm on Yrs, and would be spiked against this algorithm and the test vectors.

Clocks and state vectors

• Every operation is stamped with an ID: the client that made it, plus that client’s own counter.
• Every peer keeps a state vector: for each client, the highest counter it has integrated.
• Two peers sync by exchanging state vectors. Each sends the operations the other is missing.

Yrs provides all three.

Snapshots name points in history

decided

A state vector says how far a peer has got, but it doesn’t pin a state. In Yrs, deleting something doesn’t use a clock value: deletions are recorded in a separate delete set. So two peers with the same state vector can still differ by what they’ve deleted.

A point in history is therefore named by a snapshot: a state vector plus a delete set, as Yrs defines it.

• A session records the full snapshot it was forked at. Rebuilding a fork from it gives exactly the state at the fork, even if content was deleted afterwards.
• Addresses and ETags carry a short hash of a snapshot. @{snapshot} in a URL is that hash, and the host keeps the snapshot it stands for. Because the hash covers deletions, deleting a shape changes the ETag, so a no-JS browser polling with If-None-Match sees it.
• Snapshots need Yrs’s garbage collection off, so deleted content is kept. This is the rule from the start.

Terminology

Per-client counters stamp operations, and state vectors describe what a peer has seen. Neither is a vector clock in the usual sense.

Canonical form v0

decided as a starting point (decision 21)

Convergence is checked by comparing the SHA-256 of each peer’s XML, so every implementation must write exactly the same bytes. Full W3C Canonical XML is built for XML signatures and is more than this needs. Xmesh canonical form v0 is:

• UTF-8, with no XML declaration.
• Deleted nodes left out, with everything under them.
• Attributes sorted by expanded name: namespace URI, then local name.
• Fixed prefixes for known namespaces: SVG as the default namespace, and inkscape:, sodipodi: and xlink:. Any other namespace gets ns1, ns2 and so on, in order of first use.
• No whitespace except what’s inside text, CDATA, comment and processing-instruction nodes, which are written as they are.
• Minimal escaping: & and < in text; &, < and " in attribute values, which are always double-quoted.

The version is part of the form, so a later change never leaves doubt about which rules produced a hash.

The patch language

UI actions are expressed as XML Patch operations, an import and export format only, never sent between peers, (RFC 5261: add, replace, remove, addressed by XPath) before they reach the engine. Xmesh translates each patch into Yrs operations that refer to node IDs, not positions, because XPath positions shift under concurrent edits.

RFC 7351 registers the application/xml-patch+xml media type for these documents. The patch operations themselves are defined in RFC 5261.

Still open

• History and garbage collection. Garbage collection stays off, so deleted content is kept. How much history to keep is part of the roadmap.
• Snapshot hashes: which hash, how short it can safely be, and how it’s written after @.
• Provenance beyond the host: whether clients should occasionally sign a hash chain of their own operations (see Identity and access).

See open questions.