feat(stitched): Minor improvements to the repl

Cargo.lock

@@ -935,6 +935,15 @@ version = "0.7.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "c3e64b0cc0439b12df2fa678eae89a1c56a529fd067a9115f7827f1fffd22b32"
 
+[[package]]
+name = "clipboard-win"
+version = "5.4.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "bde03770d3df201d4fb868f2c9c59e66a3e4e2bd06692a0fe701e7103c7e84d4"
+dependencies = [
+ "error-code",
+]
+
 [[package]]
 name = "cmake"
 version = "0.1.57"
@@ -1090,7 +1099,6 @@ dependencies = [
  "core_affinity",
  "ctor",
  "cyborgtime",
- "ed25519-dalek",
  "either",
  "figment",
  "futures",
@@ -1210,6 +1218,7 @@ dependencies = [
  "hickory-resolver",
  "http",
  "image",
+ "indexmap",
  "ipaddress",
  "itertools 0.14.0",
  "ldap3",
@@ -1820,6 +1829,12 @@ dependencies = [
  "windows-sys 0.61.2",
 ]
 
+[[package]]
+name = "error-code"
+version = "3.3.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "dea2df4cf52843e0452895c455a1a2cfbb842a1e7329671acf418fdc53ed4c59"
+
 [[package]]
 name = "event-listener"
 version = "5.3.1"
@@ -3659,6 +3674,33 @@ dependencies = [
  "syn",
 ]
 
+[[package]]
+name = "peg"
+version = "0.8.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9928cfca101b36ec5163e70049ee5368a8a1c3c6efc9ca9c5f9cc2f816152477"
+dependencies = [
+ "peg-macros",
+ "peg-runtime",
+]
+
+[[package]]
+name = "peg-macros"
+version = "0.8.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6298ab04c202fa5b5d52ba03269fb7b74550b150323038878fe6c372d8280f71"
+dependencies = [
+ "peg-runtime",
+ "proc-macro2",
+ "quote",
+]
+
+[[package]]
+name = "peg-runtime"
+version = "0.8.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "132dca9b868d927b35b5dd728167b2dee150eb1ad686008fc71ccb298b776fca"
+
 [[package]]
 name = "percent-encoding"
 version = "2.3.2"
@@ -4586,6 +4628,25 @@ version = "1.0.22"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "b39cdef0fa800fc44525c84ccb54a029961a8215f9619753635a9c0d2538d46d"
 
+[[package]]
+name = "rustyline"
+version = "17.0.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e902948a25149d50edc1a8e0141aad50f54e22ba83ff988cf8f7c9ef07f50564"
+dependencies = [
+ "bitflags",
+ "cfg-if",
+ "clipboard-win",
+ "libc",
+ "log",
+ "memchr",
+ "nix",
+ "unicode-segmentation",
+ "unicode-width 0.2.2",
+ "utf8parse",
+ "windows-sys 0.60.2",
+]
+
 [[package]]
 name = "rustyline-async"
 version = "0.4.6"
@@ -5108,6 +5169,16 @@ version = "1.2.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "6ce2be8dc25455e1f91df71bfa12ad37d7af1092ae736f3a6cd0e37bc7810596"
 
+[[package]]
+name = "stitcher"
+version = "0.5.3"
+dependencies = [
+ "indexmap",
+ "itertools 0.14.0",
+ "peg",
+ "rustyline",
+]
+
 [[package]]
 name = "strict"
 version = "0.2.0"
@@ -5869,6 +5940,12 @@ version = "1.0.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "b6c140620e7ffbb22c2dee59cafe6084a59b5ffc27a8859a5f0d494b5d52b6be"
 
+[[package]]
+name = "utf8parse"
+version = "0.2.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "06abde3611657adf66d383f00b093d7faecc7fa57071cce2578660c9f1010821"
+
 [[package]]
 name = "uuid"
 version = "1.19.0"

Cargo.toml

@@ -548,6 +548,10 @@ features = ["sync", "tls-rustls", "rustls-provider"]
 [workspace.dependencies.resolv-conf]
 version = "0.7.5"
 
+# Used by stitched ordering
+[workspace.dependencies.indexmap]
+version = "2.13.0"
+
 #
 # Patches
 #

changelog.d/1302.bugfix.md

@@ -1 +0,0 @@
-UIAA requests which check for out-of-band success (sent by matrix-js-sdk)  will no longer create unhelpful errors in the logs.

docs/_meta.json

@@ -34,14 +34,6 @@
         "name": "troubleshooting",
         "label": "Troubleshooting"
     },
-    "security",
-    {
-        "type": "dir-section-header",
-        "name": "community",
-        "label": "Community",
-        "collapsible": true,
-        "collapsed": false
-    },
     {
         "type": "divider"
     },
@@ -71,5 +63,7 @@
     },
     {
         "type": "divider"
-    }
+    },
+    "community",
+    "security"
 ]

docs/_nav.json

@@ -19,21 +19,16 @@
             {
                 "text": "Admin Command Reference",
                 "link": "/reference/admin/"
+            },
+            {
+                "text": "Server Reference",
+                "link": "/reference/server"
             }
         ]
     },
     {
         "text": "Community",
-        "items": [
-            {
-                "text": "Community Guidelines",
-                "link": "/community/guidelines"
-            },
-            {
-                "text": "Become a Partnered Homeserver!",
-                "link": "/community/ops-guidelines"
-            }
-        ]
+        "link": "/community"
     },
     {
         "text": "Security",

docs/community/_meta.json

@@ -1,12 +0,0 @@
-[
-    {
-        "type": "file",
-        "name": "guidelines",
-        "label": "Community Guidelines"
-    },
-    {
-        "type": "file",
-        "name": "ops-guidelines",
-        "label": "Partnered Homeserver Guidelines"
-    }
-]

docs/community/ops-guidelines.mdx

@@ -1,32 +0,0 @@
-# Partnered Homeserver Operator Requirements
-> _So you want to be an officially sanctioned public Continuwuity homeserver operator?_
-
-Thank you for your interest in the project! There's a few things we need from you first to make sure your homeserver meets our quality standards and that you are prepared to handle the additional workload introduced by operating a public chat service.
-
-## Stuff you must have
-if you don't do these things we will tell you to go away
-
-- Your homeserver must be running an up-to-date version of Continuwuity
-- You must have a CAPTCHA, external registration system, or apply-to-join system that provides one-time-use invite codes (we do not accept fully open nor static token registration)
-- Your homeserver must have support details listed in [`/.well-known/matrix/support`](https://spec.matrix.org/v1.17/client-server-api/#getwell-knownmatrixsupport)
-- Your rules and guidelines must align with [the project's own code of conduct](guidelines).
-- You must be reasonably responsive (i.e. don't leave us hanging for a week if we alert you to an issue on your server)
-- Your homeserver's community rooms (if any) must be protected by a moderation bot subscribed to policy lists like the Community Moderation Effort (you can get one from https://asgard.chat if you don't want to run your own)
-
-## Stuff we encourage you to have
-not strictly required but we will consider your request more strongly if you have it
-
-- You should have automated moderation tooling that can automatically suspend abusive users on your homeserver who are added to policy lists
-- You should have multiple server administrators (increased bus factor)
-- You should have a terms of service and privacy policy prominently available
-
-## Stuff you get
-
-- Prominent listing in our README!
-- A gold star sticker
-- Access to a low noise room for more direct communication with maintainers and collaboration with fellow operators
-- Read-only access to the continuwuity internal ban list
-- Early notice of upcoming releases
-
-## Sound good?
-To get started, ping a team member in [our main chatroom](https://matrix.to/#/#continuwuity:continuwuity.org) and ask to be added to the list.

rspress.config.ts

@@ -54,9 +54,6 @@ export default defineConfig({
         }, {
             from: '/server_reference',
             to: '/reference/server'
-        }, {
-            from: '/community$',
-            to: '/community/guidelines'
         }
         ]
     })],

src/api/client/membership/join.rs

@@ -657,6 +657,7 @@ async fn join_room_by_id_helper_remote(
 	let auth_check = state_res::event_auth::auth_check(
 		&state_res::RoomVersion::new(&room_version_id)?,
 		&parsed_join_pdu,
+		None, // TODO: third party invite
 		|k, s| state_fetch(k.clone(), s.into()),
 		&state_fetch(StateEventType::RoomCreate, "".into())
 			.await

src/core/Cargo.toml

@@ -10,31 +10,31 @@ version.workspace = true
 [lib]
 path = "mod.rs"
 crate-type = [
-    "rlib",
-    #	"dylib",
+	"rlib",
+#	"dylib",
 ]
 
 [features]
 brotli_compression = [
-    "reqwest/brotli",
+	"reqwest/brotli",
 ]
 conduwuit_mods = [
     "dep:libloading"
 ]
 gzip_compression = [
-    "reqwest/gzip",
+	"reqwest/gzip",
 ]
 hardened_malloc = [
-    "dep:hardened_malloc-rs"
+	"dep:hardened_malloc-rs"
 ]
 jemalloc = [
-    "dep:tikv-jemalloc-sys",
-    "dep:tikv-jemalloc-ctl",
-    "dep:tikv-jemallocator",
+	"dep:tikv-jemalloc-sys",
+	"dep:tikv-jemalloc-ctl",
+	"dep:tikv-jemallocator",
 ]
 jemalloc_conf = []
 jemalloc_prof = [
-    "tikv-jemalloc-sys/profiling",
+	"tikv-jemalloc-sys/profiling",
 ]
 jemalloc_stats = [
     "tikv-jemalloc-sys/stats",
@@ -43,10 +43,10 @@ jemalloc_stats = [
 ]
 perf_measurements = []
 release_max_log_level = [
-    "tracing/max_level_trace",
-    "tracing/release_max_level_info",
-    "log/max_level_trace",
-    "log/release_max_level_info",
+	"tracing/max_level_trace",
+	"tracing/release_max_level_info",
+	"log/max_level_trace",
+	"log/release_max_level_info",
 ]
 sentry_telemetry = []
 zstd_compression = [
@@ -110,7 +110,6 @@ tracing.workspace = true
 url.workspace = true
 parking_lot.workspace = true
 lock_api.workspace = true
-ed25519-dalek = "~2"
 
 [target.'cfg(unix)'.dependencies]
 nix.workspace = true

src/core/matrix/state_res/event_auth.rs

@@ -1,36 +1,26 @@
 use std::{borrow::Borrow, collections::BTreeSet};
 
-use ed25519_dalek::{Verifier, VerifyingKey};
 use futures::{
 	Future,
 	future::{OptionFuture, join, join3},
 };
-use itertools::Itertools;
 use ruma::{
-	CanonicalJsonObject, Int, OwnedUserId, RoomVersionId, UserId,
-	canonical_json::to_canonical_value,
+	Int, OwnedUserId, RoomVersionId, UserId,
 	events::room::{
 		create::RoomCreateEventContent,
 		join_rules::{JoinRule, RoomJoinRulesEventContent},
 		member::{MembershipState, ThirdPartyInvite},
 		power_levels::RoomPowerLevelsEventContent,
-		third_party_invite::{PublicKey, RoomThirdPartyInviteEventContent},
+		third_party_invite::RoomThirdPartyInviteEventContent,
 	},
 	int,
-	serde::{
-		Base64, Base64DecodeError, Raw,
-		base64::{Standard, UrlSafe},
-	},
-	signatures::{ParseError, VerificationError},
+	serde::{Base64, Raw},
 };
 use serde::{
 	Deserialize,
 	de::{Error as _, IgnoredAny},
 };
-use serde_json::{
-	from_str as from_json_str, to_value,
-	value::{RawValue as RawJsonValue, to_raw_value},
-};
+use serde_json::{from_str as from_json_str, value::RawValue as RawJsonValue};
 
 use super::{
 	Error, Event, Result, StateEventType, StateKey, TimelineEventType,
@@ -40,7 +30,7 @@ use super::{
 	},
 	room_version::RoomVersion,
 };
-use crate::{debug, error, trace, utils::to_canonical_object, warn};
+use crate::{debug, error, trace, warn};
 
 // FIXME: field extracting could be bundled for `content`
 #[derive(Deserialize)]
@@ -167,14 +157,15 @@ pub fn auth_types_for_event(
 pub async fn auth_check<E, F, Fut>(
 	room_version: &RoomVersion,
 	incoming_event: &E,
+	current_third_party_invite: Option<&E>,
 	fetch_state: F,
 	create_event: &E,
 ) -> Result<bool, Error>
 where
-	F: Fn(&StateEventType, &str) -> Fut + Send + Sync,
+	F: Fn(&StateEventType, &str) -> Fut + Send,
 	Fut: Future<Output = Option<E>> + Send,
 	E: Event + Send + Sync,
-	for<'a> &'a E: Event + Send + Sync,
+	for<'a> &'a E: Event + Send,
 {
 	debug!(
 		event_id = %incoming_event.event_id(),
@@ -424,15 +415,13 @@ where
 			sender,
 			sender_member_event.as_ref(),
 			incoming_event,
+			current_third_party_invite,
 			power_levels_event.as_ref(),
 			join_rules_event.as_ref(),
 			user_for_join_auth.as_deref(),
 			&user_for_join_auth_membership,
 			&room_create_event,
-			&fetch_state,
-		)
-		.await?
-		{
+		)? {
 			return Ok(false);
 		}
 
@@ -669,25 +658,23 @@ where
 /// event and the current State.
 #[allow(clippy::too_many_arguments)]
 #[allow(clippy::cognitive_complexity)]
-async fn valid_membership_change<F, Fut, E>(
+fn valid_membership_change<E>(
 	room_version: &RoomVersion,
 	target_user: &UserId,
 	target_user_membership_event: Option<&E>,
 	sender: &UserId,
 	sender_membership_event: Option<&E>,
 	current_event: &E,
+	current_third_party_invite: Option<&E>,
 	power_levels_event: Option<&E>,
 	join_rules_event: Option<&E>,
 	user_for_join_auth: Option<&UserId>,
 	user_for_join_auth_membership: &MembershipState,
 	create_room: &E,
-	fetch_state: &F,
 ) -> Result<bool>
 where
-	F: Fn(&StateEventType, &str) -> Fut + Send + Sync,
-	Fut: Future<Output = Option<E>> + Send,
 	E: Event + Send + Sync,
-	for<'a> &'a E: Event + Send + Sync,
+	for<'a> &'a E: Event + Send,
 {
 	#[derive(Deserialize)]
 	struct GetThirdPartyInvite {
@@ -963,62 +950,68 @@ where
 		| MembershipState::Invite => {
 			// If content has third_party_invite key
 			trace!("starting target_membership=invite check");
-			if let Some(third_party_invite) = third_party_invite {
-				let allow = verify_third_party_invite(
-					target_user_current_membership,
-					&serde_json::to_value(third_party_invite)?,
-					target_user,
-					current_event,
-					fetch_state,
-				)
-				.await;
-				if !allow {
-					warn!("Third party invite invalid");
-				}
-				return Ok(allow);
+			match third_party_invite.and_then(|i| i.deserialize().ok()) {
+				| Some(tp_id) =>
+					if target_user_current_membership == MembershipState::Ban {
+						warn!(?target_user_membership_event_id, "Can't invite banned user");
+						false
+					} else {
+						let allow = verify_third_party_invite(
+							Some(target_user),
+							sender,
+							&tp_id,
+							current_third_party_invite,
+						);
+						if !allow {
+							warn!("Third party invite invalid");
+						}
+						allow
+					},
+				| _ =>
+					if !sender_is_joined {
+						warn!(
+							%sender,
+							?sender_membership_event_id,
+							?sender_membership,
+							"sender cannot produce an invite without being joined to the room",
+						);
+						false
+					} else if matches!(
+						target_user_current_membership,
+						MembershipState::Join | MembershipState::Ban
+					) {
+						warn!(
+							?target_user_membership_event_id,
+							?target_user_current_membership,
+							"cannot invite a user who is banned or already joined",
+						);
+						false
+					} else {
+						let allow = sender_creator
+							|| sender_power
+								.filter(|&p| p >= &power_levels.invite)
+								.is_some();
+						if !allow {
+							warn!(
+								%sender,
+								has=?sender_power,
+								required=?power_levels.invite,
+								"sender does not have enough power to produce invites",
+							);
+						}
+						trace!(
+							%sender,
+							?sender_membership_event_id,
+							?sender_membership,
+							?target_user_membership_event_id,
+							?target_user_current_membership,
+							sender_pl=?sender_power,
+							required_pl=?power_levels.invite,
+							"allowing invite"
+						);
+						allow
+					},
 			}
-			if !sender_is_joined {
-				warn!(
-					%sender,
-					?sender_membership_event_id,
-					?sender_membership,
-					"sender cannot produce an invite without being joined to the room",
-				);
-				return Ok(false);
-			} else if matches!(
-				target_user_current_membership,
-				MembershipState::Join | MembershipState::Ban
-			) {
-				warn!(
-					?target_user_membership_event_id,
-					?target_user_current_membership,
-					"cannot invite a user who is banned or already joined",
-				);
-				return Ok(false);
-			}
-			let allow = sender_creator
-				|| sender_power
-					.filter(|&p| p >= &power_levels.invite)
-					.is_some();
-			if !allow {
-				warn!(
-					%sender,
-					has=?sender_power,
-					required=?power_levels.invite,
-					"sender does not have enough power to produce invites",
-				);
-			}
-			trace!(
-				%sender,
-				?sender_membership_event_id,
-				?sender_membership,
-				?target_user_membership_event_id,
-				?target_user_current_membership,
-				sender_pl=?sender_power,
-				required_pl=?power_levels.invite,
-				"allowing invite"
-			);
-			return Ok(allow);
 		},
 		| MembershipState::Leave => {
 			let can_unban = if target_user_current_membership == MembershipState::Ban {
@@ -1506,187 +1499,399 @@ fn get_send_level(
 		.unwrap_or_else(|| if state_key.is_some() { int!(50) } else { int!(0) })
 }
 
-fn verify_payload(pk: &[u8], sig: &[u8], c: &[u8]) -> Result<(), ruma::signatures::Error> {
-	VerifyingKey::from_bytes(
-		pk.try_into()
-			.map_err(|_| ParseError::PublicKey(ed25519_dalek::SignatureError::new()))?,
-	)
-	.map_err(ParseError::PublicKey)?
-	.verify(c, &sig.try_into().map_err(ParseError::Signature)?)
-	.map_err(VerificationError::Signature)
-	.map_err(ruma::signatures::Error::from)
-}
+fn verify_third_party_invite(
+	target_user: Option<&UserId>,
+	sender: &UserId,
+	tp_id: &ThirdPartyInvite,
+	current_third_party_invite: Option<&impl Event>,
+) -> bool {
+	// 1. Check for user being banned happens before this is called
+	// checking for mxid and token keys is done by ruma when deserializing
 
-/// Decodes a base64 string as either URL-safe or standard base64, as per the
-/// spec. It attempts to decode urlsafe first.
-fn decode_base64(content: &str) -> Result<Vec<u8>, Base64DecodeError> {
-	if let Ok(decoded) = Base64::<UrlSafe>::parse(content) {
-		Ok(decoded.as_bytes().to_vec())
-	} else {
-		Base64::<Standard>::parse(content).map(|v| v.as_bytes().to_vec())
+	// The state key must match the invitee
+	if target_user != Some(&tp_id.signed.mxid) {
+		return false;
 	}
-}
 
-fn get_public_keys(event: &CanonicalJsonObject) -> Vec<Vec<u8>> {
-	let mut public_keys = Vec::new();
-	if let Some(public_key) = event.get("public_key").and_then(|v| v.as_str()) {
-		if let Ok(v) = decode_base64(public_key) {
-			trace!(
-				encoded = public_key,
-				decoded = ?v,
-				"found public key in public_key property of m.room.third_party_invite event",
-			);
-			public_keys.push(v);
-		} else {
-			warn!("m.room.third_party_invite event has invalid public_key");
-		}
-	}
-	if let Some(keys) = event.get("public_keys").and_then(|v| v.as_array()) {
-		for key in keys {
-			if let Some(key_obj) = key.as_object() {
-				if let Some(public_key) = key_obj.get("public_key").and_then(|v| v.as_str()) {
-					if let Ok(v) = decode_base64(public_key) {
-						trace!(
-							encoded = public_key,
-							decoded = ?v,
-							"found public key in public_keys list of m.room.third_party_invite \
-							 event",
-						);
-						public_keys.push(v);
-					} else {
-						warn!(
-							"m.room.third_party_invite event has invalid public_key in \
-							 public_keys list"
-						);
-					}
-				} else {
-					warn!(
-						"m.room.third_party_invite event has entry in public_keys list missing \
-						 public_key property"
-					);
-				}
-			} else {
-				warn!(
-					"m.room.third_party_invite event has invalid entry in public_keys list, \
-					 expected object"
-				);
-			}
-		}
-	}
-	public_keys
-}
-
-/// Checks a third-party invite is valid.
-async fn verify_third_party_invite<F, Fut, E>(
-	target_current_membership: MembershipState,
-	raw_third_party_invite: &serde_json::Value,
-	target: &UserId,
-	event: &E,
-	fetch_state: &F,
-) -> bool
-where
-	F: Fn(&StateEventType, &str) -> Fut + Send + Sync,
-	Fut: Future<Output = Option<E>> + Send,
-	E: Event + Send + Sync,
-	for<'a> &'a E: Event + Send + Sync,
-{
-	// 4.1.1: If target user is banned, reject.
-	if target_current_membership == MembershipState::Ban {
-		warn!("invite target is banned");
-		return false;
-	}
-	// 4.1.2: If content.third_party_invite does not have a signed property, reject.
-	let Some(signed) = raw_third_party_invite.get("signed") else {
-		warn!("invite event third_party_invite missing signed property");
-		return false;
-	};
-	// 4.2.3: If signed does not have mxid and token properties, reject.
-	let Some(mxid) = signed.get("mxid").and_then(|v| v.as_str()) else {
-		warn!("invite event third_party_invite signed missing/invalid mxid property");
-		return false;
-	};
-	let Some(token) = signed.get("token").and_then(|v| v.as_str()) else {
-		warn!("invite event third_party_invite signed missing token property");
-		return false;
-	};
-	// 4.2.4: If mxid does not match state_key, reject.
-	if mxid != target.as_str() {
-		warn!("invite event third_party_invite signed mxid does not match state_key");
-		return false;
-	}
-	// 4.2.5: If there is no m.room.third_party_invite event in the room
-	// state matching the token, reject.
-	let Some(third_party_invite_event) =
-		fetch_state(&StateEventType::RoomThirdPartyInvite, token).await
-	else {
-		warn!("invite event third_party_invite token has no matching m.room.third_party_invite");
-		return false;
-	};
-	// 4.2.6: If sender does not match sender of the m.room.third_party_invite,
-	// reject.
-	if third_party_invite_event.sender() != event.sender() {
-		warn!("invite event sender does not match m.room.third_party_invite sender");
-		return false;
-	}
-	// 4.2.7: If any signature in signed matches any public key in the
-	// m.room.third_party_invite event, allow. The public keys are in
-	// content of m.room.third_party_invite as:
-	//   1. A single public key in the public_key property.
-	//   2. A list of public keys in the public_keys property.
-	debug!(
-		"Fetching signatures in third-party-invite event {}",
-		third_party_invite_event.event_id()
-	);
-	trace!("third-party-invite event content: {}", third_party_invite_event.content().get());
-
-	let Some(signatures) = signed.get("signatures").and_then(|v| v.as_object()) else {
-		warn!("invite event third_party_invite signed missing/invalid signatures");
-		return false;
+	// If there is no m.room.third_party_invite event in the current room state with
+	// state_key matching token, reject
+	#[allow(clippy::manual_let_else)]
+	let current_tpid = match current_third_party_invite {
+		| Some(id) => id,
+		| None => return false,
 	};
 
-	for pk in get_public_keys(
-		&to_canonical_object(third_party_invite_event.content())
-			.expect("m.room.third_party_invite event content is not a JSON object"),
-	) {
-		// signatures -> { server_name: { ed25519:N: signature } }
-		for (server_name, server_sigs) in signatures {
-			trace!("Searching for signatures from {}", server_name);
-			if let Some(server_sigs) = server_sigs.as_object() {
-				for (key_id, signature_value) in server_sigs {
-					trace!("Checking signature with key id {}", key_id);
-					if let Some(signature_str) = signature_value.as_str() {
-						if let Ok(signature) = decode_base64(signature_str) {
-							debug!(
-								%server_name,
-								%key_id,
-								"verifying third-party invite signature",
-							);
-							match verify_payload(
-								&pk,
-								&signature,
-								serde_json::to_string(&to_canonical_value(signed).unwrap())
-									.unwrap()
-									.as_bytes(),
-							) {
-								| Ok(()) => {
-									debug!("valid third-party invite signature found");
-									return true;
-								},
-								| Err(e) => {
-									warn!(
-										%server_name,
-										%key_id,
-										"invalid third-party invite signature: {e}",
-									);
-								},
-							}
-						}
-					}
-				}
-			}
+	if current_tpid.state_key() != Some(&tp_id.signed.token) {
+		return false;
+	}
+
+	if sender != current_tpid.sender() {
+		return false;
+	}
+
+	// If any signature in signed matches any public key in the
+	// m.room.third_party_invite event, allow
+	#[allow(clippy::manual_let_else)]
+	let tpid_ev =
+		match from_json_str::<RoomThirdPartyInviteEventContent>(current_tpid.content().get()) {
+			| Ok(ev) => ev,
+			| Err(_) => return false,
+		};
+
+	#[allow(clippy::manual_let_else)]
+	let decoded_invite_token = match Base64::parse(&tp_id.signed.token) {
+		| Ok(tok) => tok,
+		// FIXME: Log a warning?
+		| Err(_) => return false,
+	};
+
+	// A list of public keys in the public_keys field
+	for key in tpid_ev.public_keys.unwrap_or_default() {
+		if key.public_key == decoded_invite_token {
+			return true;
 		}
 	}
 
-	warn!("no valid signature found for third-party invite");
-	false
+	// A single public key in the public_key field
+	tpid_ev.public_key == decoded_invite_token
+}
+
+#[cfg(test)]
+mod tests {
+	use ruma::events::{
+		StateEventType, TimelineEventType,
+		room::{
+			join_rules::{
+				AllowRule, JoinRule, Restricted, RoomJoinRulesEventContent, RoomMembership,
+			},
+			member::{MembershipState, RoomMemberEventContent},
+		},
+	};
+	use serde_json::value::to_raw_value as to_raw_json_value;
+
+	use crate::{
+		matrix::{Event, EventTypeExt, Pdu as PduEvent},
+		state_res::{
+			RoomVersion, StateMap,
+			event_auth::valid_membership_change,
+			test_utils::{
+				INITIAL_EVENTS, INITIAL_EVENTS_CREATE_ROOM, alice, charlie, ella, event_id,
+				member_content_ban, member_content_join, room_id, to_pdu_event,
+			},
+		},
+	};
+
+	#[test]
+	fn test_ban_pass() {
+		let _ = tracing::subscriber::set_default(
+			tracing_subscriber::fmt().with_test_writer().finish(),
+		);
+		let events = INITIAL_EVENTS();
+
+		let auth_events = events
+			.values()
+			.map(|ev| (ev.event_type().with_state_key(ev.state_key().unwrap()), ev.clone()))
+			.collect::<StateMap<_>>();
+
+		let requester = to_pdu_event(
+			"HELLO",
+			alice(),
+			TimelineEventType::RoomMember,
+			Some(charlie().as_str()),
+			member_content_ban(),
+			&[],
+			&["IMC"],
+		);
+
+		let fetch_state = |ty, key| auth_events.get(&(ty, key)).cloned();
+		let target_user = charlie();
+		let sender = alice();
+
+		assert!(
+			valid_membership_change(
+				&RoomVersion::V6,
+				target_user,
+				fetch_state(StateEventType::RoomMember, target_user.as_str().into()).as_ref(),
+				sender,
+				fetch_state(StateEventType::RoomMember, sender.as_str().into()).as_ref(),
+				&requester,
+				None::<&PduEvent>,
+				fetch_state(StateEventType::RoomPowerLevels, "".into()).as_ref(),
+				fetch_state(StateEventType::RoomJoinRules, "".into()).as_ref(),
+				None,
+				&MembershipState::Leave,
+				&fetch_state(StateEventType::RoomCreate, "".into()).unwrap(),
+			)
+			.unwrap()
+		);
+	}
+
+	#[test]
+	fn test_join_non_creator() {
+		let _ = tracing::subscriber::set_default(
+			tracing_subscriber::fmt().with_test_writer().finish(),
+		);
+		let events = INITIAL_EVENTS_CREATE_ROOM();
+
+		let auth_events = events
+			.values()
+			.map(|ev| (ev.event_type().with_state_key(ev.state_key().unwrap()), ev.clone()))
+			.collect::<StateMap<_>>();
+
+		let requester = to_pdu_event(
+			"HELLO",
+			charlie(),
+			TimelineEventType::RoomMember,
+			Some(charlie().as_str()),
+			member_content_join(),
+			&["CREATE"],
+			&["CREATE"],
+		);
+
+		let fetch_state = |ty, key| auth_events.get(&(ty, key)).cloned();
+		let target_user = charlie();
+		let sender = charlie();
+
+		assert!(
+			!valid_membership_change(
+				&RoomVersion::V6,
+				target_user,
+				fetch_state(StateEventType::RoomMember, target_user.as_str().into()).as_ref(),
+				sender,
+				fetch_state(StateEventType::RoomMember, sender.as_str().into()).as_ref(),
+				&requester,
+				None::<&PduEvent>,
+				fetch_state(StateEventType::RoomPowerLevels, "".into()).as_ref(),
+				fetch_state(StateEventType::RoomJoinRules, "".into()).as_ref(),
+				None,
+				&MembershipState::Leave,
+				&fetch_state(StateEventType::RoomCreate, "".into()).unwrap(),
+			)
+			.unwrap()
+		);
+	}
+
+	#[test]
+	fn test_join_creator() {
+		let _ = tracing::subscriber::set_default(
+			tracing_subscriber::fmt().with_test_writer().finish(),
+		);
+		let events = INITIAL_EVENTS_CREATE_ROOM();
+
+		let auth_events = events
+			.values()
+			.map(|ev| (ev.event_type().with_state_key(ev.state_key().unwrap()), ev.clone()))
+			.collect::<StateMap<_>>();
+
+		let requester = to_pdu_event(
+			"HELLO",
+			alice(),
+			TimelineEventType::RoomMember,
+			Some(alice().as_str()),
+			member_content_join(),
+			&["CREATE"],
+			&["CREATE"],
+		);
+
+		let fetch_state = |ty, key| auth_events.get(&(ty, key)).cloned();
+		let target_user = alice();
+		let sender = alice();
+
+		assert!(
+			valid_membership_change(
+				&RoomVersion::V6,
+				target_user,
+				fetch_state(StateEventType::RoomMember, target_user.as_str().into()).as_ref(),
+				sender,
+				fetch_state(StateEventType::RoomMember, sender.as_str().into()).as_ref(),
+				&requester,
+				None::<&PduEvent>,
+				fetch_state(StateEventType::RoomPowerLevels, "".into()).as_ref(),
+				fetch_state(StateEventType::RoomJoinRules, "".into()).as_ref(),
+				None,
+				&MembershipState::Leave,
+				&fetch_state(StateEventType::RoomCreate, "".into()).unwrap(),
+			)
+			.unwrap()
+		);
+	}
+
+	#[test]
+	fn test_ban_fail() {
+		let _ = tracing::subscriber::set_default(
+			tracing_subscriber::fmt().with_test_writer().finish(),
+		);
+		let events = INITIAL_EVENTS();
+
+		let auth_events = events
+			.values()
+			.map(|ev| (ev.event_type().with_state_key(ev.state_key().unwrap()), ev.clone()))
+			.collect::<StateMap<_>>();
+
+		let requester = to_pdu_event(
+			"HELLO",
+			charlie(),
+			TimelineEventType::RoomMember,
+			Some(alice().as_str()),
+			member_content_ban(),
+			&[],
+			&["IMC"],
+		);
+
+		let fetch_state = |ty, key| auth_events.get(&(ty, key)).cloned();
+		let target_user = alice();
+		let sender = charlie();
+
+		assert!(
+			!valid_membership_change(
+				&RoomVersion::V6,
+				target_user,
+				fetch_state(StateEventType::RoomMember, target_user.as_str().into()).as_ref(),
+				sender,
+				fetch_state(StateEventType::RoomMember, sender.as_str().into()).as_ref(),
+				&requester,
+				None::<&PduEvent>,
+				fetch_state(StateEventType::RoomPowerLevels, "".into()).as_ref(),
+				fetch_state(StateEventType::RoomJoinRules, "".into()).as_ref(),
+				None,
+				&MembershipState::Leave,
+				&fetch_state(StateEventType::RoomCreate, "".into()).unwrap(),
+			)
+			.unwrap()
+		);
+	}
+
+	#[test]
+	fn test_restricted_join_rule() {
+		let _ = tracing::subscriber::set_default(
+			tracing_subscriber::fmt().with_test_writer().finish(),
+		);
+		let mut events = INITIAL_EVENTS();
+		*events.get_mut(&event_id("IJR")).unwrap() = to_pdu_event(
+			"IJR",
+			alice(),
+			TimelineEventType::RoomJoinRules,
+			Some(""),
+			to_raw_json_value(&RoomJoinRulesEventContent::new(JoinRule::Restricted(
+				Restricted::new(vec![AllowRule::RoomMembership(RoomMembership::new(
+					room_id().to_owned(),
+				))]),
+			)))
+			.unwrap(),
+			&["CREATE", "IMA", "IPOWER"],
+			&["IPOWER"],
+		);
+
+		let mut member = RoomMemberEventContent::new(MembershipState::Join);
+		member.join_authorized_via_users_server = Some(alice().to_owned());
+
+		let auth_events = events
+			.values()
+			.map(|ev| (ev.event_type().with_state_key(ev.state_key().unwrap()), ev.clone()))
+			.collect::<StateMap<_>>();
+
+		let requester = to_pdu_event(
+			"HELLO",
+			ella(),
+			TimelineEventType::RoomMember,
+			Some(ella().as_str()),
+			to_raw_json_value(&RoomMemberEventContent::new(MembershipState::Join)).unwrap(),
+			&["CREATE", "IJR", "IPOWER", "new"],
+			&["new"],
+		);
+
+		let fetch_state = |ty, key| auth_events.get(&(ty, key)).cloned();
+		let target_user = ella();
+		let sender = ella();
+
+		assert!(
+			valid_membership_change(
+				&RoomVersion::V9,
+				target_user,
+				fetch_state(StateEventType::RoomMember, target_user.as_str().into()).as_ref(),
+				sender,
+				fetch_state(StateEventType::RoomMember, sender.as_str().into()).as_ref(),
+				&requester,
+				None::<&PduEvent>,
+				fetch_state(StateEventType::RoomPowerLevels, "".into()).as_ref(),
+				fetch_state(StateEventType::RoomJoinRules, "".into()).as_ref(),
+				Some(alice()),
+				&MembershipState::Join,
+				&fetch_state(StateEventType::RoomCreate, "".into()).unwrap(),
+			)
+			.unwrap()
+		);
+
+		assert!(
+			!valid_membership_change(
+				&RoomVersion::V9,
+				target_user,
+				fetch_state(StateEventType::RoomMember, target_user.as_str().into()).as_ref(),
+				sender,
+				fetch_state(StateEventType::RoomMember, sender.as_str().into()).as_ref(),
+				&requester,
+				None::<&PduEvent>,
+				fetch_state(StateEventType::RoomPowerLevels, "".into()).as_ref(),
+				fetch_state(StateEventType::RoomJoinRules, "".into()).as_ref(),
+				Some(ella()),
+				&MembershipState::Leave,
+				&fetch_state(StateEventType::RoomCreate, "".into()).unwrap(),
+			)
+			.unwrap()
+		);
+	}
+
+	#[test]
+	fn test_knock() {
+		let _ = tracing::subscriber::set_default(
+			tracing_subscriber::fmt().with_test_writer().finish(),
+		);
+		let mut events = INITIAL_EVENTS();
+		*events.get_mut(&event_id("IJR")).unwrap() = to_pdu_event(
+			"IJR",
+			alice(),
+			TimelineEventType::RoomJoinRules,
+			Some(""),
+			to_raw_json_value(&RoomJoinRulesEventContent::new(JoinRule::Knock)).unwrap(),
+			&["CREATE", "IMA", "IPOWER"],
+			&["IPOWER"],
+		);
+
+		let auth_events = events
+			.values()
+			.map(|ev| (ev.event_type().with_state_key(ev.state_key().unwrap()), ev.clone()))
+			.collect::<StateMap<_>>();
+
+		let requester = to_pdu_event(
+			"HELLO",
+			ella(),
+			TimelineEventType::RoomMember,
+			Some(ella().as_str()),
+			to_raw_json_value(&RoomMemberEventContent::new(MembershipState::Knock)).unwrap(),
+			&[],
+			&["IMC"],
+		);
+
+		let fetch_state = |ty, key| auth_events.get(&(ty, key)).cloned();
+		let target_user = ella();
+		let sender = ella();
+
+		assert!(
+			valid_membership_change(
+				&RoomVersion::V7,
+				target_user,
+				fetch_state(StateEventType::RoomMember, target_user.as_str().into()).as_ref(),
+				sender,
+				fetch_state(StateEventType::RoomMember, sender.as_str().into()).as_ref(),
+				&requester,
+				None::<&PduEvent>,
+				fetch_state(StateEventType::RoomPowerLevels, "".into()).as_ref(),
+				fetch_state(StateEventType::RoomJoinRules, "".into()).as_ref(),
+				None,
+				&MembershipState::Leave,
+				&fetch_state(StateEventType::RoomCreate, "".into()).unwrap(),
+			)
+			.unwrap()
+		);
+	}
 }

src/core/matrix/state_res/mod.rs

@@ -717,6 +717,9 @@ where
 
 		// The key for this is (eventType + a state_key of the signed token not sender)
 		// so search for it
+		let current_third_party = auth_state.iter().find_map(|(_, pdu)| {
+			(*pdu.event_type() == TimelineEventType::RoomThirdPartyInvite).then_some(pdu)
+		});
 
 		let fetch_state = |ty: &StateEventType, key: &str| {
 			future::ready(
@@ -729,6 +732,7 @@ where
 		let auth_result = auth_check(
 			room_version,
 			&event,
+			current_third_party,
 			fetch_state,
 			&fetch_state(&StateEventType::RoomCreate, "")
 				.await

src/service/Cargo.toml

@@ -118,6 +118,7 @@ webpage.optional = true
 blurhash.workspace = true
 blurhash.optional = true
 recaptcha-verify = { version = "0.1.5", default-features = false }
+indexmap.workspace = true
 
 [target.'cfg(all(unix, target_os = "linux"))'.dependencies]
 sd-notify.workspace = true

src/service/rooms/event_handler/handle_outlier_pdu.rs

@@ -184,6 +184,7 @@ where
 	let auth_check = state_res::event_auth::auth_check(
 		&to_room_version(&room_version_id),
 		&pdu_event,
+		None, // TODO: third party invite
 		state_fetch,
 		create_event.as_pdu(),
 	)

src/service/rooms/event_handler/upgrade_outlier_pdu.rs

@@ -100,6 +100,7 @@ where
 	let auth_check = state_res::event_auth::auth_check(
 		&room_version,
 		&incoming_pdu,
+		None, // TODO: third party invite
 		|ty, sk| state_fetch(ty.clone(), sk.into()),
 		create_event.as_pdu(),
 	)
@@ -139,6 +140,7 @@ where
 	let auth_check = state_res::event_auth::auth_check(
 		&room_version,
 		&incoming_pdu,
+		None, // third-party invite
 		state_fetch,
 		create_event.as_pdu(),
 	)

src/service/rooms/timeline/create.rs

@@ -236,9 +236,15 @@ pub async fn create_hash_and_sign_event(
 		| _ => create_pdu.as_ref().unwrap().as_pdu(),
 	};
 
-	let auth_check = state_res::auth_check(&room_version, &pdu, auth_fetch, create_event)
-		.await
-		.map_err(|e| err!(Request(Forbidden(warn!("Auth check failed: {e:?}")))))?;
+	let auth_check = state_res::auth_check(
+		&room_version,
+		&pdu,
+		None, // TODO: third_party_invite
+		auth_fetch,
+		create_event,
+	)
+	.await
+	.map_err(|e| err!(Request(Forbidden(warn!("Auth check failed: {e:?}")))))?;
 
 	if !auth_check {
 		return Err!(Request(Forbidden("Event is not authorized.")));

src/service/uiaa/mod.rs

@@ -233,16 +233,6 @@ pub async fn try_auth(
 		| AuthData::Dummy(_) => {
 			uiaainfo.completed.push(AuthType::Dummy);
 		},
-		| AuthData::FallbackAcknowledgement(_) => {
-			// The client is checking if authentication has succeeded out-of-band. This is
-			// possible if the client is using "fallback auth" (see spec section
-			// 4.9.1.4), which we don't support (and probably never will, because it's a
-			// disgusting hack).
-
-			// Return early to tell the client that no, authentication did not succeed while
-			// it wasn't looking.
-			return Ok((false, uiaainfo));
-		},
 		| k => error!("type not supported: {:?}", k),
 	}
 

src/stitcher/Cargo.toml

@@ -0,0 +1,19 @@
+[package]
+name = "stitcher"
+description = "An implementation of stitched ordering (https://codeberg.org/andybalaam/stitched-order)"
+edition.workspace = true
+license.workspace = true
+readme.workspace = true
+repository.workspace = true
+version.workspace = true
+
+[lib]
+path = "mod.rs"
+
+[dependencies]
+indexmap.workspace = true
+itertools.workspace = true
+
+[dev-dependencies]
+peg = "0.8.5"
+rustyline = { version = "17.0.2", default-features = false }

src/stitcher/algorithm.rs

@@ -0,0 +1,141 @@
+use std::collections::HashSet;
+
+use indexmap::IndexSet;
+use itertools::Itertools;
+
+use super::{Batch, Gap, OrderKey, StitchedItem, StitcherBackend};
+
+/// Updates to a gap in the stitched order.
+#[derive(Debug)]
+pub struct GapUpdate<'id, K: OrderKey> {
+	/// The opaque key of the gap to update.
+	pub key: K,
+	/// The new contents of the gap. If this is empty, the gap should be
+	/// deleted.
+	pub gap: Gap,
+	/// New items to insert after the gap. These items _should not_ be
+	/// synchronized to clients.
+	pub inserted_items: Vec<StitchedItem<'id>>,
+}
+
+/// Updates to the stitched order.
+#[derive(Debug)]
+pub struct OrderUpdates<'id, K: OrderKey> {
+	/// Updates to individual gaps. The items inserted by these updates _should
+	/// not_ be synchronized to clients.
+	pub gap_updates: Vec<GapUpdate<'id, K>>,
+	/// New items to append to the end of the order. These items _should_ be
+	/// synchronized to clients.
+	pub new_items: Vec<StitchedItem<'id>>,
+	// The subset of events in the batch which got slotted into an existing gap. This is tracked
+	// for unit testing and may eventually be sent to clients.
+	pub events_added_to_gaps: HashSet<&'id str>,
+}
+
+/// The stitcher, which implements the stitched ordering algorithm.
+/// Its primary method is [`Stitcher::stitch`].
+pub struct Stitcher<'backend, B: StitcherBackend> {
+	backend: &'backend B,
+}
+
+impl<B: StitcherBackend> Stitcher<'_, B> {
+	/// Create a new [`Stitcher`] given a [`StitcherBackend`].
+	pub fn new(backend: &B) -> Stitcher<'_, B> { Stitcher { backend } }
+
+	/// Given a [`Batch`], compute the [`OrderUpdates`] which should be made to
+	/// the stitched order to incorporate that batch. It is the responsibility
+	/// of the caller to apply the updates.
+	pub fn stitch<'id>(&self, batch: &Batch<'id>) -> OrderUpdates<'id, B::Key> {
+		let mut gap_updates = Vec::new();
+		let mut events_added_to_gaps: HashSet<&'id str> = HashSet::new();
+
+		// Events in the batch which haven't been fitted into a gap or appended to the
+		// end yet.
+		let mut remaining_events: IndexSet<_> = batch.events().collect();
+
+		// 1: Find existing gaps which include IDs of events in `batch`
+		let matching_gaps = self.backend.find_matching_gaps(batch.events());
+
+		// Repeat steps 2-9 for each matching gap
+		for (key, mut gap) in matching_gaps {
+			// 2. Find events in `batch` which are mentioned in `gap`
+			let matching_events = remaining_events.iter().filter(|id| gap.contains(**id));
+
+			// Extend `events_added_to_gaps` with the matching events, which are destined to
+			// be slotted into gaps.
+			events_added_to_gaps.extend(matching_events.clone());
+
+			// 3. Create the to-insert list from the predecessor sets of each matching event
+			let events_to_insert: Vec<_> = matching_events
+				.filter_map(|event| batch.predecessors(event))
+				.flat_map(|predecessors| predecessors.predecessor_set.iter())
+				.filter(|event| remaining_events.contains(*event))
+				.copied()
+				.collect();
+
+			// 4. Remove the events in the to-insert list from `remaining_events` so they
+			//    aren't processed again
+			remaining_events.retain(|event| !events_to_insert.contains(event));
+
+			// 5 and 6
+			let inserted_items = self.sort_events_and_create_gaps(batch, events_to_insert);
+
+			// 8. Update gap
+			gap.retain(|id| !batch.contains(id));
+
+			// 7 and 9. Append to-insert list and delete gap if empty
+			// The actual work of mutating the order is handled by the callee,
+			// we just record an update to make.
+			gap_updates.push(GapUpdate { key: key.clone(), gap, inserted_items });
+		}
+
+		// 10. Append remaining events and gaps
+		let new_items = self.sort_events_and_create_gaps(batch, remaining_events);
+
+		OrderUpdates {
+			gap_updates,
+			new_items,
+			events_added_to_gaps,
+		}
+	}
+
+	fn sort_events_and_create_gaps<'id>(
+		&self,
+		batch: &Batch<'id>,
+		events_to_insert: impl IntoIterator<Item = &'id str>,
+	) -> Vec<StitchedItem<'id>> {
+		// 5. Sort the to-insert list with DAG;received order
+		let events_to_insert = events_to_insert
+			.into_iter()
+			.sorted_by(batch.compare_by_dag_received())
+			.collect_vec();
+
+		// allocate 1.5x the size of the to-insert list
+		let items_capacity = events_to_insert
+			.capacity()
+			.saturating_add(events_to_insert.capacity().div_euclid(2));
+
+		let mut items = Vec::with_capacity(items_capacity);
+
+		for event in events_to_insert {
+			let missing_prev_events: HashSet<String> = batch
+				.predecessors(event)
+				.expect("events in to_insert should be in batch")
+				.prev_events
+				.iter()
+				.filter(|prev_event| {
+					!(batch.contains(prev_event) || self.backend.event_exists(prev_event))
+				})
+				.map(|id| String::from(*id))
+				.collect();
+
+			if !missing_prev_events.is_empty() {
+				items.push(StitchedItem::Gap(missing_prev_events));
+			}
+
+			items.push(StitchedItem::Event(event));
+		}
+
+		items
+	}
+}

src/stitcher/examples/repl.rs

@@ -0,0 +1,88 @@
+use std::collections::HashSet;
+
+use rustyline::{DefaultEditor, Result, error::ReadlineError};
+use stitcher::{Batch, EventEdges, Stitcher, memory_backend::MemoryStitcherBackend};
+
+const BANNER: &str = "
+stitched ordering test repl
+- append an event by typing its name: `A`
+- to add prev events, type an arrow and then space-separated event names: `A --> B C D`
+- to add multiple events at once, separate them with commas
+- use `/reset` to clear the ordering
+Ctrl-D to exit, Ctrl-C to clear input
+"
+.trim_ascii();
+
+enum Command<'line> {
+	AppendEvents(EventEdges<'line>),
+	ResetOrder,
+}
+
+peg::parser! {
+	// partially copied from the test case parser
+	grammar command_parser() for str {
+		/// Parse whitespace.
+		rule _ -> () = quiet! { $([' '])* {} }
+
+		/// Parse an event ID.
+		rule event_id() -> &'input str
+			= quiet! { id:$([char if char.is_ascii_alphanumeric() || ['_', '-'].contains(&char)]+) { id } }
+			  / expected!("an event ID containing only [a-zA-Z0-9_-]")
+
+		/// Parse an event and its prev events.
+		rule event() -> (&'input str, HashSet<&'input str>)
+			= id:event_id() prev_events:(_ "-->" _ id:(event_id() ++ _) { id })? {
+				(id, prev_events.into_iter().flatten().collect())
+			}
+
+		pub rule command() -> Command<'input> =
+			"/reset" { Command::ResetOrder }
+			/ events:event() ++ (_ "," _) { Command::AppendEvents(events.into_iter().collect()) }
+	}
+}
+
+fn main() -> Result<()> {
+	let mut backend = MemoryStitcherBackend::default();
+	let mut reader = DefaultEditor::new()?;
+
+	println!("{BANNER}");
+
+	loop {
+		match reader.readline("> ") {
+			| Ok(line) => match command_parser::command(&line) {
+				| Ok(Command::AppendEvents(events)) => {
+					let batch = Batch::from_edges(&events);
+					let stitcher = Stitcher::new(&backend);
+					let updates = stitcher.stitch(&batch);
+
+					for update in &updates.gap_updates {
+						println!("update to gap {}:", update.key);
+						println!("    new gap contents: {:?}", update.gap);
+						println!("    inserted items: {:?}", update.inserted_items);
+					}
+
+					println!("events added to gaps: {:?}", &updates.events_added_to_gaps);
+					println!();
+					println!("items to sync: {:?}", &updates.new_items);
+					backend.extend(updates);
+					println!("order: {backend:?}");
+				},
+				| Ok(Command::ResetOrder) => {
+					backend.clear();
+					println!("order cleared.");
+				},
+				| Err(parse_error) => {
+					println!("parse error!! {parse_error}");
+				},
+			},
+			| Err(ReadlineError::Interrupted) => {
+				println!("interrupt");
+			},
+			| Err(ReadlineError::Eof) => {
+				println!("goodbye :3");
+				break Ok(());
+			},
+			| Err(err) => break Err(err),
+		}
+	}
+}

src/stitcher/memory_backend.rs

@@ -0,0 +1,130 @@
+use std::{
+	fmt::Debug,
+	sync::atomic::{AtomicU64, Ordering},
+};
+
+use crate::{Gap, OrderUpdates, StitchedItem, StitcherBackend};
+
+/// A version of [`StitchedItem`] which owns event IDs.
+#[derive(Debug)]
+enum MemoryStitcherItem {
+	Event(String),
+	Gap(Gap),
+}
+
+impl From<StitchedItem<'_>> for MemoryStitcherItem {
+	fn from(value: StitchedItem) -> Self {
+		match value {
+			| StitchedItem::Event(id) => MemoryStitcherItem::Event(id.to_string()),
+			| StitchedItem::Gap(gap) => MemoryStitcherItem::Gap(gap),
+		}
+	}
+}
+
+impl<'id> From<&'id MemoryStitcherItem> for StitchedItem<'id> {
+	fn from(value: &'id MemoryStitcherItem) -> Self {
+		match value {
+			| MemoryStitcherItem::Event(id) => StitchedItem::Event(id),
+			| MemoryStitcherItem::Gap(gap) => StitchedItem::Gap(gap.clone()),
+		}
+	}
+}
+
+/// A stitcher backend which holds a stitched ordering in RAM.
+#[derive(Default)]
+pub struct MemoryStitcherBackend {
+	items: Vec<(u64, MemoryStitcherItem)>,
+	counter: AtomicU64,
+}
+
+impl MemoryStitcherBackend {
+	fn next_id(&self) -> u64 { self.counter.fetch_add(1, Ordering::Relaxed) }
+
+	/// Extend this ordering with new updates.
+	pub fn extend(&mut self, results: OrderUpdates<'_, <Self as StitcherBackend>::Key>) {
+		for update in results.gap_updates {
+			let Some(gap_index) = self.items.iter().position(|(key, _)| *key == update.key)
+			else {
+				panic!("bad update key {}", update.key);
+			};
+
+			let insertion_index = if update.gap.is_empty() {
+				self.items.remove(gap_index);
+				gap_index
+			} else {
+				match self.items.get_mut(gap_index) {
+					| Some((_, MemoryStitcherItem::Gap(gap))) => {
+						*gap = update.gap;
+					},
+					| Some((key, other)) => {
+						panic!("expected item with key {key} to be a gap, it was {other:?}");
+					},
+					| None => unreachable!("we just checked that this index is valid"),
+				}
+				gap_index.checked_add(1).expect(
+					"should never allocate usize::MAX ids. what kind of test are you running",
+				)
+			};
+
+			let to_insert: Vec<_> = update
+				.inserted_items
+				.into_iter()
+				.map(|item| (self.next_id(), item.into()))
+				.collect();
+			self.items
+				.splice(insertion_index..insertion_index, to_insert.into_iter())
+				.for_each(drop);
+		}
+
+		let new_items: Vec<_> = results
+			.new_items
+			.into_iter()
+			.map(|item| (self.next_id(), item.into()))
+			.collect();
+		self.items.extend(new_items);
+	}
+
+	/// Iterate over the items in this ordering.
+	pub fn iter(&self) -> impl Iterator<Item = StitchedItem<'_>> {
+		self.items.iter().map(|(_, item)| item.into())
+	}
+
+	/// Clear this ordering.
+	pub fn clear(&mut self) { self.items.clear(); }
+}
+
+impl StitcherBackend for MemoryStitcherBackend {
+	type Key = u64;
+
+	fn find_matching_gaps<'a>(
+		&'a self,
+		events: impl Iterator<Item = &'a str>,
+	) -> impl Iterator<Item = (Self::Key, Gap)> {
+		// nobody cares about test suite performance right
+		let mut gaps = vec![];
+
+		for event in events {
+			for (key, item) in &self.items {
+				if let MemoryStitcherItem::Gap(gap) = item
+					&& gap.contains(event)
+				{
+					gaps.push((*key, gap.clone()));
+				}
+			}
+		}
+
+		gaps.into_iter()
+	}
+
+	fn event_exists<'a>(&'a self, event: &'a str) -> bool {
+		self.items
+			.iter()
+			.any(|item| matches!(&item.1, MemoryStitcherItem::Event(id) if event == id))
+	}
+}
+
+impl Debug for MemoryStitcherBackend {
+	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+		f.debug_list().entries(self.iter()).finish()
+	}
+}

src/stitcher/mod.rs

@@ -0,0 +1,160 @@
+use std::{cmp::Ordering, collections::HashSet};
+
+use indexmap::IndexMap;
+
+pub mod algorithm;
+pub mod memory_backend;
+#[cfg(test)]
+mod test;
+
+pub use algorithm::*;
+
+/// A gap in the stitched order.
+pub type Gap = HashSet<String>;
+
+/// An item in the stitched order.
+#[derive(Debug)]
+pub enum StitchedItem<'id> {
+	/// A single event.
+	Event(&'id str),
+	/// A gap representing one or more missing events.
+	Gap(Gap),
+}
+
+/// An opaque key returned by a [`StitcherBackend`] to identify an item in its
+/// order.
+pub trait OrderKey: Eq + Clone {}
+
+impl<T: Eq + Clone> OrderKey for T {}
+
+/// A trait providing read-only access to an existing stitched order.
+pub trait StitcherBackend {
+	type Key: OrderKey;
+
+	/// Return all gaps containing one or more events listed in `events`.
+	fn find_matching_gaps<'a>(
+		&'a self,
+		events: impl Iterator<Item = &'a str>,
+	) -> impl Iterator<Item = (Self::Key, Gap)>;
+
+	/// Return whether an event exists in the stitched order.
+	fn event_exists<'a>(&'a self, event: &'a str) -> bool;
+}
+
+/// An ordered map from an event ID to its `prev_events`.
+pub type EventEdges<'id> = IndexMap<&'id str, HashSet<&'id str>>;
+
+/// Information about the `prev_events` of an event.
+/// This struct does not store the ID of the event itself.
+#[derive(Debug)]
+struct EventPredecessors<'id> {
+	/// The `prev_events` of the event.
+	pub prev_events: HashSet<&'id str>,
+	/// The predecessor set of the event. This is derived from, and a superset
+	/// of, [`EventPredecessors::prev_events`]. See
+	/// [`Batch::find_predecessor_set`] for details. It is cached in this
+	/// struct for performance.
+	pub predecessor_set: HashSet<&'id str>,
+}
+
+/// A batch of events to be inserted into the stitched order.
+#[derive(Debug)]
+pub struct Batch<'id> {
+	events: IndexMap<&'id str, EventPredecessors<'id>>,
+}
+
+impl<'id> Batch<'id> {
+	/// Create a new [`Batch`] from an [`EventEdges`].
+	pub fn from_edges<'edges>(edges: &EventEdges<'edges>) -> Batch<'edges> {
+		let mut events = IndexMap::new();
+
+		for (event, prev_events) in edges {
+			let predecessor_set = Self::find_predecessor_set(event, edges);
+
+			events.insert(*event, EventPredecessors {
+				prev_events: prev_events.clone(),
+				predecessor_set,
+			});
+		}
+
+		Batch { events }
+	}
+
+	/// Build the predecessor set of `event` using `edges`. The predecessor set
+	/// is a subgraph of the room's DAG which may be thought of as a tree
+	/// rooted at `event` containing _only_ events which are included in
+	/// `edges`. It is represented as a set and not a proper tree structure for
+	/// efficiency.
+	fn find_predecessor_set<'a>(event: &'a str, edges: &EventEdges<'a>) -> HashSet<&'a str> {
+		// The predecessor set which we are building.
+		let mut predecessor_set = HashSet::new();
+
+		// The queue of events to check for membership in `remaining_events`.
+		let mut events_to_check = vec![event];
+		// Events which we have already checked and do not need to revisit.
+		let mut events_already_checked = HashSet::new();
+
+		while let Some(event) = events_to_check.pop() {
+			// Don't add this event to the queue again.
+			events_already_checked.insert(event);
+
+			// If this event is in `edges`, add it to the predecessor set.
+			if let Some(children) = edges.get(event) {
+				predecessor_set.insert(event);
+
+				// Also add all its `prev_events` to the queue. It's fine if some of them don't
+				// exist in `edges` because they'll just be discarded when they're popped
+				// off the queue.
+				events_to_check.extend(
+					children
+						.iter()
+						.filter(|event| !events_already_checked.contains(*event)),
+				);
+			}
+		}
+
+		predecessor_set
+	}
+
+	/// Iterate over all the events contained in this batch.
+	fn events(&self) -> impl Iterator<Item = &'id str> { self.events.keys().copied() }
+
+	/// Check whether an event exists in this batch.
+	fn contains(&self, event: &'id str) -> bool { self.events.contains_key(event) }
+
+	/// Return the predecessors of an event, if it exists in this batch.
+	fn predecessors(&self, event: &str) -> Option<&EventPredecessors<'id>> {
+		self.events.get(event)
+	}
+
+	/// Compare two events by DAG;received order.
+	///
+	/// If either event is in the other's predecessor set it comes first,
+	/// otherwise they are sorted by which comes first in the batch.
+	fn compare_by_dag_received(&self) -> impl FnMut(&&'id str, &&'id str) -> Ordering {
+		|a, b| {
+			if self
+				.predecessors(a)
+				.is_some_and(|it| it.predecessor_set.contains(b))
+			{
+				Ordering::Greater
+			} else if self
+				.predecessors(b)
+				.is_some_and(|it| it.predecessor_set.contains(a))
+			{
+				Ordering::Less
+			} else {
+				let a_index = self
+					.events
+					.get_index_of(a)
+					.expect("a should be in this batch");
+				let b_index = self
+					.events
+					.get_index_of(b)
+					.expect("b should be in this batch");
+
+				a_index.cmp(&b_index)
+			}
+		}
+	}
+}

src/stitcher/test/mod.rs

@@ -0,0 +1,102 @@
+use itertools::Itertools;
+
+use super::{algorithm::*, *};
+use crate::memory_backend::MemoryStitcherBackend;
+
+mod parser;
+
+fn run_testcase(testcase: parser::TestCase<'_>) {
+	let mut backend = MemoryStitcherBackend::default();
+
+	for (index, phase) in testcase.into_iter().enumerate() {
+		let stitcher = Stitcher::new(&backend);
+		let batch = Batch::from_edges(&phase.batch);
+		let updates = stitcher.stitch(&batch);
+
+		println!();
+		println!("===== phase {index}");
+		for update in &updates.gap_updates {
+			println!("update to gap {}:", update.key);
+			println!("    new gap contents: {:?}", update.gap);
+			println!("    inserted items: {:?}", update.inserted_items);
+		}
+
+		println!("expected new items: {:?}", &phase.order.new_items);
+		println!("  actual new items: {:?}", &updates.new_items);
+		for (expected, actual) in phase
+			.order
+			.new_items
+			.iter()
+			.zip_eq(updates.new_items.iter())
+		{
+			assert_eq!(
+				expected, actual,
+				"bad new item, expected {expected:?} but got {actual:?}"
+			);
+		}
+
+		if let Some(updated_gaps) = phase.updated_gaps {
+			println!("expected events added to gaps: {updated_gaps:?}");
+			println!("  actual events added to gaps: {:?}", updates.events_added_to_gaps);
+			assert_eq!(
+				updated_gaps, updates.events_added_to_gaps,
+				"incorrect events added to gaps"
+			);
+		}
+
+		backend.extend(updates);
+		println!("extended ordering: {:?}", backend);
+
+		for (expected, ref actual) in phase.order.iter().zip_eq(backend.iter()) {
+			assert_eq!(
+				expected, actual,
+				"bad item in order, expected {expected:?} but got {actual:?}",
+			);
+		}
+	}
+}
+
+macro_rules! testcase {
+	($index:literal : $id:ident) => {
+		#[test]
+		fn $id() {
+			let testcase = parser::parse(include_str!(concat!(
+				"./testcases/",
+				$index,
+				"-",
+				stringify!($id),
+				".stitched"
+			)));
+
+			run_testcase(testcase);
+		}
+	};
+}
+
+testcase!("001": receiving_new_events);
+testcase!("002": recovering_after_netsplit);
+testcase!("zzz": being_before_a_gap_item_beats_being_after_an_existing_item_multiple);
+testcase!("zzz": being_before_a_gap_item_beats_being_after_an_existing_item);
+testcase!("zzz": chains_are_reordered_using_prev_events);
+testcase!("zzz": empty_then_simple_chain);
+testcase!("zzz": empty_then_two_chains_interleaved);
+testcase!("zzz": empty_then_two_chains);
+testcase!("zzz": filling_in_a_gap_with_a_batch_containing_gaps);
+testcase!("zzz": gaps_appear_before_events_referring_to_them_received_order);
+testcase!("zzz": gaps_appear_before_events_referring_to_them);
+testcase!("zzz": if_prev_events_determine_order_they_override_received);
+testcase!("zzz": insert_into_first_of_several_gaps);
+testcase!("zzz": insert_into_last_of_several_gaps);
+testcase!("zzz": insert_into_middle_of_several_gaps);
+testcase!("zzz": linked_events_are_split_across_gaps);
+testcase!("zzz": linked_events_in_a_diamond_are_split_across_gaps);
+testcase!("zzz": middle_of_batch_matches_gap_and_end_of_batch_matches_end);
+testcase!("zzz": middle_of_batch_matches_gap);
+testcase!("zzz": multiple_events_referring_to_the_same_missing_event_first_has_more);
+testcase!("zzz": multiple_events_referring_to_the_same_missing_event);
+testcase!("zzz": multiple_events_referring_to_the_same_missing_event_with_more);
+testcase!("zzz": multiple_missing_prev_events_turn_into_a_single_gap);
+testcase!("zzz": partially_filling_a_gap_leaves_it_before_new_nodes);
+testcase!("zzz": partially_filling_a_gap_with_two_events);
+testcase!("zzz": received_order_wins_within_a_subgroup_if_no_prev_event_chain);
+testcase!("zzz": subgroups_are_processed_in_first_received_order);

src/stitcher/test/parser.rs

@@ -0,0 +1,140 @@
+use std::collections::HashSet;
+
+use indexmap::IndexMap;
+
+use super::StitchedItem;
+
+pub(super) type TestEventId<'id> = &'id str;
+
+pub(super) type TestGap<'id> = HashSet<TestEventId<'id>>;
+
+#[derive(Debug)]
+pub(super) enum TestStitchedItem<'id> {
+	Event(TestEventId<'id>),
+	Gap(TestGap<'id>),
+}
+
+impl PartialEq<StitchedItem<'_>> for TestStitchedItem<'_> {
+	fn eq(&self, other: &StitchedItem<'_>) -> bool {
+		match (self, other) {
+			| (TestStitchedItem::Event(lhs), StitchedItem::Event(rhs)) => lhs == rhs,
+			| (TestStitchedItem::Gap(lhs), StitchedItem::Gap(rhs)) =>
+				lhs.iter().all(|id| rhs.contains(*id)),
+			| _ => false,
+		}
+	}
+}
+
+pub(super) type TestCase<'id> = Vec<Phase<'id>>;
+
+pub(super) struct Phase<'id> {
+	pub batch: Batch<'id>,
+	pub order: Order<'id>,
+	pub updated_gaps: Option<HashSet<TestEventId<'id>>>,
+}
+
+pub(super) type Batch<'id> = IndexMap<TestEventId<'id>, HashSet<TestEventId<'id>>>;
+
+pub(super) struct Order<'id> {
+	pub inserted_items: Vec<TestStitchedItem<'id>>,
+	pub new_items: Vec<TestStitchedItem<'id>>,
+}
+
+impl<'id> Order<'id> {
+	pub(super) fn iter(&self) -> impl Iterator<Item = &TestStitchedItem<'id>> {
+		self.inserted_items.iter().chain(self.new_items.iter())
+	}
+}
+
+peg::parser! {
+	grammar testcase() for str {
+		/// Parse whitespace.
+		rule _ -> () = quiet! { $([' '])* {} }
+
+		/// Parse empty lines and comments.
+		rule newline() -> () = quiet! { (("#" [^'\n']*)? "\n")+ {} }
+
+		/// Parse an "event ID" in a test case, which may only consist of ASCII letters and numbers.
+		rule event_id() -> TestEventId<'input>
+			= quiet! { id:$([char if char.is_ascii_alphanumeric()]+) { id } }
+			  / expected!("event id")
+
+		/// Parse a gap in the order section.
+		rule gap() -> TestGap<'input>
+			= "-" events:event_id() ++ "," { events.into_iter().collect() }
+
+		/// Parse either an event id or a gap.
+		rule stitched_item() -> TestStitchedItem<'input> =
+			id:event_id() { TestStitchedItem::Event(id) }
+			/ gap:gap() { TestStitchedItem::Gap(gap) }
+
+		/// Parse an event line in the batch section, mapping an event name to zero or one prev events.
+		/// The prev events are merged together by [`batch()`].
+		rule batch_event() -> (TestEventId<'input>, Option<TestEventId<'input>>)
+			= id:event_id() prev:(_ "-->" _ prev:event_id() { prev })? { (id, prev) }
+
+		/// Parse the batch section of a phase.
+		rule batch() -> Batch<'input>
+			= events:batch_event() ++ newline() {
+				/*
+				Repeated event lines need to be merged together. For example,
+
+				A --> B
+				A --> C
+
+				represents a _single_ event `A` with two prev events, `B` and `C`.
+				*/
+				events.into_iter()
+					.fold(IndexMap::new(), |mut batch: Batch<'_>, (id, prev_event)| {
+						// Find the prev events set of this event in the batch.
+						// If it doesn't exist, make a new empty one.
+						let mut prev_events = batch.entry(id).or_default();
+						// If this event line defines a prev event to add, insert it into the set.
+						if let Some(prev_event) = prev_event {
+							prev_events.insert(prev_event);
+						}
+
+						batch
+					})
+			}
+
+		rule order() -> Order<'input> =
+			items:(item:stitched_item() new:"*"? { (item, new.is_some()) }) ** newline()
+			{
+				let (mut inserted_items, mut new_items) = (vec![], vec![]);
+
+				for (item, new) in items {
+					if new {
+						new_items.push(item);
+					} else {
+						inserted_items.push(item);
+					}
+				}
+
+				Order {
+					inserted_items,
+					new_items,
+				}
+			}
+
+		rule updated_gaps() -> HashSet<TestEventId<'input>> =
+			events:event_id() ++ newline() { events.into_iter().collect() }
+
+		rule phase() -> Phase<'input> =
+					  "=== when we receive these events ==="
+			newline() batch:batch()
+			newline() "=== then we arrange into this order ==="
+			newline() order:order()
+			updated_gaps:(
+			newline() "=== and we notify about these gaps ==="
+			newline() updated_gaps:updated_gaps() { updated_gaps }
+			)?
+			{ Phase { batch, order, updated_gaps } }
+
+		pub rule testcase() -> TestCase<'input> = phase() ++ newline()
+	}
+}
+
+pub(super) fn parse<'input>(input: &'input str) -> TestCase<'input> {
+	testcase::testcase(input.trim_ascii_end()).expect("parse error")
+}

src/stitcher/test/testcases/001-receiving_new_events.stitched

@@ -0,0 +1,22 @@
+=== when we receive these events ===
+A
+B --> A
+C --> B
+=== then we arrange into this order ===
+# Given the server has some existing events in this order:
+A*
+B*
+C*
+
+=== when we receive these events ===
+# When it receives new ones:
+D --> C
+E --> D
+
+=== then we arrange into this order ===
+# Then it simply appends them at the end of the order:
+A
+B
+C
+D*
+E*

src/stitcher/test/testcases/002-recovering_after_netsplit.stitched

@@ -0,0 +1,46 @@
+=== when we receive these events ===
+A1
+A2 --> A1
+A3 --> A2
+=== then we arrange into this order ===
+# Given the server has some existing events in this order:
+A1*
+A2*
+A3*
+
+=== when we receive these events ===
+# And after a netsplit the server receives some unrelated events, which refer to
+# some unknown event, because the server didn't receive all of them:
+B7 --> B6
+B8 --> B7
+B9 --> B8
+
+=== then we arrange into this order ===
+# Then these events are new, and we add a gap to show something is missing:
+A1
+A2
+A3
+-B6*
+B7*
+B8*
+B9*
+=== when we receive these events ===
+# Then if we backfill and receive more of those events later:
+B4 --> B3
+B5 --> B4
+B6 --> B5
+=== then we arrange into this order ===
+# They are slotted into the gap, and a new gap is created to represent the
+# still-missing events:
+A1
+A2
+A3
+-B3
+B4
+B5
+B6
+B7
+B8
+B9
+=== and we notify about these gaps ===
+B6

src/stitcher/test/testcases/zzz-being_before_a_gap_item_beats_being_after_an_existing_item.stitched

@@ -0,0 +1,30 @@
+=== when we receive these events ===
+D --> C
+=== then we arrange into this order ===
+# We may see situations that are ambiguous about whether an event is new or
+# belongs in a gap, because it is a predecessor of a gap event and also has a
+# new event as its predecessor. This a rare case where either outcome could be
+# valid. If the initial order is this:
+-C*
+D*
+=== when we receive these events ===
+# And then we receive B
+B --> A
+=== then we arrange into this order ===
+# Which is new because it's unrelated to everything else
+-C
+D
+-A*
+B*
+=== when we receive these events ===
+# And later it turns out that C refers back to B
+C --> B
+=== then we arrange into this order ===
+# Then we place C into the early gap even though it is after B, so arguably
+# should be the newest
+C
+D
+-A
+B
+=== and we notify about these gaps ===
+C

src/stitcher/test/testcases/zzz-being_before_a_gap_item_beats_being_after_an_existing_item_multiple.stitched

@@ -0,0 +1,28 @@
+=== when we receive these events ===
+# An ambiguous situation can occur when we have multiple gaps that both might
+# accepts an event. This should be relatively rare.
+A --> G1
+B --> A
+C --> G2
+=== then we arrange into this order ===
+-G1*
+A*
+B*
+-G2*
+C*
+=== when we receive these events ===
+# When we receive F, which is a predecessor of both G1 and G2
+F
+G1 --> F
+G2 --> F
+=== then we arrange into this order ===
+# Then F appears in the earlier gap, but arguably it should appear later.
+F
+G1
+A
+B
+G2
+C
+=== and we notify about these gaps ===
+G1
+G2

src/stitcher/test/testcases/zzz-chains_are_reordered_using_prev_events.stitched

@@ -0,0 +1,10 @@
+=== when we receive these events ===
+# Even though we see C first, it is re-ordered because we must obey prev_events
+# so A comes first.
+C --> A
+A
+B --> A
+=== then we arrange into this order ===
+A*
+C*
+B*

src/stitcher/test/testcases/zzz-empty_then_simple_chain.stitched

@@ -0,0 +1,8 @@
+=== when we receive these events ===
+A
+B --> A
+C --> B
+=== then we arrange into this order ===
+A*
+B*
+C*

src/stitcher/test/testcases/zzz-empty_then_two_chains.stitched

@@ -0,0 +1,18 @@
+=== when we receive these events ===
+# A chain ABC
+A
+B --> A
+C --> B
+# And a separate chain XYZ
+X --> W
+Y --> X
+Z --> Y
+=== then we arrange into this order ===
+# Should produce them in order with a gap
+A*
+B*
+C*
+-W*
+X*
+Y*
+Z*

src/stitcher/test/testcases/zzz-empty_then_two_chains_interleaved.stitched

@@ -0,0 +1,18 @@
+=== when we receive these events ===
+# Same as empty_then_two_chains except for received order
+# A chain ABC, and a separate chain XYZ, but interleaved
+A
+X --> W
+B --> A
+Y --> X
+C --> B
+Z --> Y
+=== then we arrange into this order ===
+# Should produce them in order with a gap
+A*
+-W*
+X*
+B*
+Y*
+C*
+Z*

src/stitcher/test/testcases/zzz-filling_in_a_gap_with_a_batch_containing_gaps.stitched

@@ -0,0 +1,33 @@
+=== when we receive these events ===
+# Given 3 gaps exist
+B --> A
+D --> C
+F --> E
+=== then we arrange into this order ===
+-A*
+B*
+-C*
+D*
+-E*
+F*
+
+=== when we receive these events ===
+# When we fill one with something that also refers to non-existent events
+C --> X
+C --> Y
+G --> C
+G --> Z
+=== then we arrange into this order ===
+# Then we fill in the gap (C) and make new gaps too (X+Y and Z)
+-A
+B
+-X,Y
+C
+D
+-E
+F
+-Z*
+G*
+=== and we notify about these gaps ===
+# And we notify about the gap that was updated
+C

src/stitcher/test/testcases/zzz-gaps_appear_before_events_referring_to_them.stitched

@@ -0,0 +1,13 @@
+=== when we receive these events ===
+# Several events refer to missing events and the events are unrelated
+C --> Y
+C --> Z
+A --> X
+B
+=== then we arrange into this order ===
+# The gaps appear immediately before the events referring to them
+-Y,Z*
+C*
+-X*
+A*
+B*

src/stitcher/test/testcases/zzz-gaps_appear_before_events_referring_to_them_received_order.stitched

@@ -0,0 +1,14 @@
+=== when we receive these events ===
+# Several events refer to missing events and the events are related
+C --> Y
+C --> Z
+C --> B
+A --> X
+B --> A
+=== then we arrange into this order ===
+# The gaps appear immediately before the events referring to them
+-X*
+A*
+B*
+-Y,Z*
+C*

src/stitcher/test/testcases/zzz-if_prev_events_determine_order_they_override_received.stitched

@@ -0,0 +1,15 @@
+=== when we receive these events ===
+# The relationships determine the order here, so they override received order
+F --> E
+C --> B
+D --> C
+E --> D
+B --> A
+A
+=== then we arrange into this order ===
+A*
+B*
+C*
+D*
+E*
+F*

src/stitcher/test/testcases/zzz-insert_into_first_of_several_gaps.stitched

@@ -0,0 +1,27 @@
+=== when we receive these events ===
+# Given 3 gaps exist
+B --> A
+D --> C
+F --> E
+=== then we arrange into this order ===
+-A*
+B*
+-C*
+D*
+-E*
+F*
+
+=== when we receive these events ===
+# When the first of them is filled in
+A
+=== then we arrange into this order ===
+# Then we slot it into the gap, not at the end
+A
+B
+-C
+D
+-E
+F
+=== and we notify about these gaps ===
+# And we notify about the gap being filled in
+A

src/stitcher/test/testcases/zzz-insert_into_last_of_several_gaps.stitched

@@ -0,0 +1,27 @@
+=== when we receive these events ===
+# Given 3 gaps exist
+B --> A
+D --> C
+F --> E
+=== then we arrange into this order ===
+-A*
+B*
+-C*
+D*
+-E*
+F*
+
+=== when we receive these events ===
+# When the last gap is filled in
+E
+=== then we arrange into this order ===
+# Then we slot it into the gap, not at the end
+-A
+B
+-C
+D
+E
+F
+=== and we notify about these gaps ===
+# And we notify about the gap being filled in
+E

src/stitcher/test/testcases/zzz-insert_into_middle_of_several_gaps.stitched

@@ -0,0 +1,27 @@
+=== when we receive these events ===
+# Given 3 gaps exist
+B --> A
+D --> C
+F --> E
+=== then we arrange into this order ===
+-A*
+B*
+-C*
+D*
+-E*
+F*
+
+=== when we receive these events ===
+# When a middle one is filled in
+C
+=== then we arrange into this order ===
+# Then we slot it into the gap, not at the end
+-A
+B
+C
+D
+-E
+F
+=== and we notify about these gaps ===
+# And we notify about the gap being filled in
+C

src/stitcher/test/testcases/zzz-linked_events_are_split_across_gaps.stitched

@@ -0,0 +1,29 @@
+=== when we receive these events ===
+# Given a couple of gaps
+B --> X2
+D --> X4
+=== then we arrange into this order ===
+-X2*
+B*
+-X4*
+D*
+
+=== when we receive these events ===
+# And linked events that fill those in and are newer
+X1
+X2 --> X1
+X3 --> X2
+X4 --> X3
+X5 --> X4
+=== then we arrange into this order ===
+# Then the gaps are filled and new events appear at the front
+X1
+X2
+B
+X3
+X4
+D
+X5*
+=== and we notify about these gaps ===
+X2
+X4

src/stitcher/test/testcases/zzz-linked_events_in_a_diamond_are_split_across_gaps.stitched

@@ -0,0 +1,31 @@
+=== when we receive these events ===
+# Given a couple of gaps
+B --> X2a
+D --> X3
+=== then we arrange into this order ===
+-X2a*
+B*
+-X3*
+D*
+
+=== when we receive these events ===
+# When we receive a diamond that touches gaps and some new events
+X1
+X2a --> X1
+X2b --> X1
+X3 --> X2a
+X3 --> X2b
+X4 --> X3
+=== then we arrange into this order ===
+# Then matching events and direct predecessors fit into the gaps
+# and other stuff is new
+X1
+X2a
+B
+X2b
+X3
+D
+X4*
+=== and we notify about these gaps ===
+X2a
+X3

src/stitcher/test/testcases/zzz-middle_of_batch_matches_gap.stitched

@@ -0,0 +1,25 @@
+=== when we receive these events ===
+# Given a gap before all the Bs
+B1 --> C2
+B2 --> B1
+=== then we arrange into this order ===
+-C2*
+B1*
+B2*
+
+=== when we receive these events ===
+# When a batch arrives with a not-last event matching the gap
+C1
+C2 --> C1
+C3 --> C2
+=== then we arrange into this order ===
+# Then we slot the matching events into the gap
+# and the later events are new
+C1
+C2
+B1
+B2
+C3*
+=== and we notify about these gaps ===
+# And we notify about the gap being filled in
+C2

src/stitcher/test/testcases/zzz-middle_of_batch_matches_gap_and_end_of_batch_matches_end.stitched

@@ -0,0 +1,26 @@
+=== when we receive these events ===
+# Given a gap before all the Bs
+B1 --> C2
+B2 --> B1
+=== then we arrange into this order ===
+-C2*
+B1*
+B2*
+
+=== when we receive these events ===
+# When a batch arrives with a not-last event matching the gap, and the last
+# event linked to a recent event
+C1
+C2 --> C1
+C3 --> C2
+C3 --> B2
+=== then we arrange into this order ===
+# Then we slot the entire batch into the gap
+C1
+C2
+B1
+B2
+C3*
+=== and we notify about these gaps ===
+# And we notify about the gap being filled in
+C2

src/stitcher/test/testcases/zzz-multiple_events_referring_to_the_same_missing_event.stitched

@@ -0,0 +1,26 @@
+=== when we receive these events ===
+# If multiple events all refer to the same missing event:
+A --> X
+B --> X
+C --> X
+=== then we arrange into this order ===
+# Then we insert gaps before all of them. This avoids the need to search the
+# entire existing order whenever we create a new gap.
+-X*
+A*
+-X*
+B*
+-X*
+C*
+=== when we receive these events ===
+# The ambiguity is resolved when the missing event arrives:
+X
+=== then we arrange into this order ===
+# We choose the earliest gap, and all the relevant gaps are removed (which does
+# mean we need to search the existing order).
+X
+A
+B
+C
+=== and we notify about these gaps ===
+X

src/stitcher/test/testcases/zzz-multiple_events_referring_to_the_same_missing_event_first_has_more.stitched

@@ -0,0 +1,29 @@
+=== when we receive these events ===
+# Several events refer to the same missing event, but the first refers to
+# others too
+A --> X
+A --> Y
+A --> Z
+B --> X
+C --> X
+=== then we arrange into this order ===
+# We end up with multiple gaps
+-X,Y,Z*
+A*
+-X*
+B*
+-X*
+C*
+
+=== when we receive these events ===
+# When we receive the missing item
+X
+=== then we arrange into this order ===
+# It goes into the earliest slot, and the non-empty gap remains
+-Y,Z
+X
+A
+B
+C
+=== and we notify about these gaps ===
+X

src/stitcher/test/testcases/zzz-multiple_events_referring_to_the_same_missing_event_with_more.stitched

@@ -0,0 +1,28 @@
+=== when we receive these events ===
+# Several events refer to the same missing event, but one refers to others too
+A --> X
+B --> X
+B --> Y
+B --> Z
+C --> X
+=== then we arrange into this order ===
+# We end up with multiple gaps
+-X*
+A*
+-X,Y,Z*
+B*
+-X*
+C*
+
+=== when we receive these events ===
+# When we receive the missing item
+X
+=== then we arrange into this order ===
+# It goes into the earliest slot, and the non-empty gap remains
+X
+A
+-Y,Z
+B
+C
+=== and we notify about these gaps ===
+X

src/stitcher/test/testcases/zzz-multiple_missing_prev_events_turn_into_a_single_gap.stitched

@@ -0,0 +1,9 @@
+=== when we receive these events ===
+# A refers to multiple missing things
+A --> X
+A --> Y
+A --> Z
+=== then we arrange into this order ===
+# But we only make one gap, with multiple IDs in it
+-X,Y,Z*
+A*

src/stitcher/test/testcases/zzz-partially_filling_a_gap_leaves_it_before_new_nodes.stitched

@@ -0,0 +1,23 @@
+=== when we receive these events ===
+A
+F --> B
+F --> C
+F --> D
+F --> E
+=== then we arrange into this order ===
+# Given a gap that lists several nodes:
+A*
+-B,C,D,E*
+F*
+=== when we receive these events ===
+# When we provide one of the missing events:
+C
+=== then we arrange into this order ===
+# Then it is inserted after the gap, and the gap is shrunk:
+A
+-B,D,E
+C
+F
+=== and we notify about these gaps ===
+# And we notify about the gap that was updated
+C

src/stitcher/test/testcases/zzz-partially_filling_a_gap_with_two_events.stitched

@@ -0,0 +1,27 @@
+=== when we receive these events ===
+# Given an event references multiple missing events
+A
+F --> B
+F --> C
+F --> D
+F --> E
+=== then we arrange into this order ===
+A*
+-B,C,D,E*
+F*
+
+=== when we receive these events ===
+# When we provide some of the missing events
+C
+E
+=== then we arrange into this order ===
+# Then we insert them after the gap and shrink the list of events in the gap
+A
+-B,D
+C
+E
+F
+=== and we notify about these gaps ===
+# And we notify about the gap that was updated
+C
+E

src/stitcher/test/testcases/zzz-received_order_wins_within_a_subgroup_if_no_prev_event_chain.stitched

@@ -0,0 +1,16 @@
+=== when we receive these events ===
+# Everything is after A, but there is no prev_event chain between the others, so
+# we use received order.
+A
+F --> A
+C --> A
+D --> A
+E --> A
+B --> A
+=== then we arrange into this order ===
+A*
+F*
+C*
+D*
+E*
+B*

src/stitcher/test/testcases/zzz-subgroups_are_processed_in_first_received_order.stitched

@@ -0,0 +1,16 @@
+=== when we receive these events ===
+# We preserve the received order where it does not conflict with the prev_events
+A
+X --> W
+Y --> X
+Z --> Y
+B --> A
+C --> B
+=== then we arrange into this order ===
+A*
+-W*
+X*
+Y*
+Z*
+B*
+C*