Most of these materials concern "stitched" order, which serves as an existence proof for an algorithm that can be used by a Matrix server to provide events in such an order.

It contains testcases that provide examples of the described behaviour in various situations, and Python source code that passes those testcases, giving an unambiguous description of the algorithm.

The algorithm is described in algorithm.md.

The key parts of the Python implementation are in python/stch/dag.py.

The draft MSCs are at msc/msc.md and msc/msc2.md.

You can discuss this proposal in the Matrix room: #stitched-ordering:matrix.org.

Running

Before you start

Load and set up the Python virtual environment:

python3 -m venv venv
. venv/bin/activate
pip install graphviz

Running all the testcases:

Make sure your virtual environment is set up as described in "Before you start".

To run all testcases:

./python/stitch.py

Or to format and type check the code, run the unit tests, and then run all the testcases:

make

(Requires make, mypy and black.)

Rendering the docs

Make sure your virtual environment is set up as described in "Before you start".

To regenerate the pictures based on the testcases:

make render

(Requires graphviz.)

Testcase format

Various testcases can be found inside the testcases/ directory.

The format for these testcases is:

Everything after # on any line is ignored
One or more phases, each starting with a line exactly like:
```
=== when we receive these events ===
```
Each phase consists of a batch, then an order section starting with:
```
=== then we arrange into this order ===
```
and then optionally an updated gaps list starting with:
```
=== and we notify about these gaps ===
```
Batches describe an incoming batch of events to be processed by the stitching algorithm. Orders describe the expected outcome of the algorithm: the full stitched order of all events in the DAG, and which events are sent over /sync. Updated gaps lists show what the server will tell the client about which gaps were updated.
The batch format is inspired (vaguely) by Mermaid diagrams, but is a custom format:
- To create an event, write its name (no spaces, just letters and numbers) at the beginning of the line. E.g. "A" or "A --> B".
- To indicate a prev_event relationship, after the event name, write " --> " followed by the name of another event, which is the prev_event.
- The event on the right-hand side does not have to exist (prev_events can be "dangling" references). Unlike in Mermaid, mentioning an event in this location does not make it exist.
- Unlike Mermaid, there is no initial diagram type, and the events are not indented.
- Node order matters: when we create an event, it is appended to the "received order".
Each order section is a list of events, one per line, in the order we expect them to be in the stitched order:
- Normal events just look like "A"
- New events (i.e. those that will be provided in the next /sync) are suffixed with an asterisk e.g. "A*"
- Gaps are a list of the missing events, prefixed by "-" e.g. "-A,B"
- Gaps are also provided over /sync, so they may also by suffixed with a asterisk e.g. "-A,B,C*"
The updated gaps list is a list of events, one per line, that used to be mentioned in gaps but are now real events. There is no meaningful order of events in the gaps list.