fix: Deserialisation error in public keys

Cargo.lock

@@ -935,15 +935,6 @@ 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"
@@ -1099,6 +1090,7 @@ dependencies = [
  "core_affinity",
  "ctor",
  "cyborgtime",
+ "ed25519-dalek",
  "either",
  "figment",
  "futures",
@@ -1218,7 +1210,6 @@ dependencies = [
  "hickory-resolver",
  "http",
  "image",
- "indexmap",
  "ipaddress",
  "itertools 0.14.0",
  "ldap3",
@@ -1829,12 +1820,6 @@ 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"
@@ -3674,33 +3659,6 @@ 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"
@@ -4628,25 +4586,6 @@ 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"
@@ -5169,16 +5108,6 @@ 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"
@@ -5940,12 +5869,6 @@ 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,10 +548,6 @@ 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

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

docs/_nav.json

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

docs/community/_meta.json

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

docs/community/ops-guidelines.mdx

@@ -0,0 +1,32 @@
+# 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,6 +54,9 @@ export default defineConfig({
         }, {
             from: '/server_reference',
             to: '/reference/server'
+        }, {
+            from: '/community$',
+            to: '/community/guidelines'
         }
         ]
     })],

src/api/client/membership/join.rs

@@ -657,7 +657,6 @@ 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,6 +110,7 @@ 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,26 +1,36 @@
 use std::{borrow::Borrow, collections::BTreeSet};
 
+use ed25519_dalek::{Verifier, VerifyingKey};
 use futures::{
 	Future,
 	future::{OptionFuture, join, join3},
 };
+use itertools::Itertools;
 use ruma::{
-	Int, OwnedUserId, RoomVersionId, UserId,
+	CanonicalJsonObject, Int, OwnedUserId, RoomVersionId, UserId,
+	canonical_json::to_canonical_value,
 	events::room::{
 		create::RoomCreateEventContent,
 		join_rules::{JoinRule, RoomJoinRulesEventContent},
 		member::{MembershipState, ThirdPartyInvite},
 		power_levels::RoomPowerLevelsEventContent,
-		third_party_invite::RoomThirdPartyInviteEventContent,
+		third_party_invite::{PublicKey, RoomThirdPartyInviteEventContent},
 	},
 	int,
-	serde::{Base64, Raw},
+	serde::{
+		Base64, Base64DecodeError, Raw,
+		base64::{Standard, UrlSafe},
+	},
+	signatures::{ParseError, VerificationError},
 };
 use serde::{
 	Deserialize,
 	de::{Error as _, IgnoredAny},
 };
-use serde_json::{from_str as from_json_str, value::RawValue as RawJsonValue};
+use serde_json::{
+	from_str as from_json_str, to_value,
+	value::{RawValue as RawJsonValue, to_raw_value},
+};
 
 use super::{
 	Error, Event, Result, StateEventType, StateKey, TimelineEventType,
@@ -30,7 +40,7 @@ use super::{
 	},
 	room_version::RoomVersion,
 };
-use crate::{debug, error, trace, warn};
+use crate::{debug, error, trace, utils::to_canonical_object, warn};
 
 // FIXME: field extracting could be bundled for `content`
 #[derive(Deserialize)]
@@ -157,15 +167,14 @@ 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,
+	F: Fn(&StateEventType, &str) -> Fut + Send + Sync,
 	Fut: Future<Output = Option<E>> + Send,
 	E: Event + Send + Sync,
-	for<'a> &'a E: Event + Send,
+	for<'a> &'a E: Event + Send + Sync,
 {
 	debug!(
 		event_id = %incoming_event.event_id(),
@@ -415,13 +424,15 @@ 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);
 		}
 
@@ -658,23 +669,25 @@ where
 /// event and the current State.
 #[allow(clippy::too_many_arguments)]
 #[allow(clippy::cognitive_complexity)]
-fn valid_membership_change<E>(
+async fn valid_membership_change<F, Fut, 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,
+	for<'a> &'a E: Event + Send + Sync,
 {
 	#[derive(Deserialize)]
 	struct GetThirdPartyInvite {
@@ -950,68 +963,62 @@ where
 		| MembershipState::Invite => {
 			// If content has third_party_invite key
 			trace!("starting target_membership=invite check");
-			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 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);
 			}
+			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 {
@@ -1499,399 +1506,187 @@ fn get_send_level(
 		.unwrap_or_else(|| if state_key.is_some() { int!(50) } else { int!(0) })
 }
 
-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
+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)
+}
 
-	// The state key must match the invitee
-	if target_user != Some(&tp_id.signed.mxid) {
+/// 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())
+	}
+}
+
+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());
 
-	// 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,
+	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 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;
+	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}",
+									);
+								},
+							}
+						}
+					}
+				}
+			}
 		}
 	}
 
-	// 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()
-		);
-	}
+	warn!("no valid signature found for third-party invite");
+	false
 }

src/core/matrix/state_res/mod.rs

@@ -717,9 +717,6 @@ 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(
@@ -732,7 +729,6 @@ where
 		let auth_result = auth_check(
 			room_version,
 			&event,
-			current_third_party,
 			fetch_state,
 			&fetch_state(&StateEventType::RoomCreate, "")
 				.await

src/service/Cargo.toml

@@ -118,7 +118,6 @@ 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,7 +184,6 @@ 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,7 +100,6 @@ 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(),
 	)
@@ -140,7 +139,6 @@ 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,15 +236,9 @@ 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,
-		None, // TODO: third_party_invite
-		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, 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,6 +233,16 @@ 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

@@ -1,19 +0,0 @@
-[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

@@ -1,141 +0,0 @@
-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

@@ -1,88 +0,0 @@
-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

@@ -1,130 +0,0 @@
-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

@@ -1,160 +0,0 @@
-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

@@ -1,102 +0,0 @@
-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

@@ -1,140 +0,0 @@
-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

@@ -1,22 +0,0 @@
-=== 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

@@ -1,46 +0,0 @@
-=== 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

@@ -1,30 +0,0 @@
-=== 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

@@ -1,28 +0,0 @@
-=== 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

@@ -1,10 +0,0 @@
-=== 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

@@ -1,8 +0,0 @@
-=== 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

@@ -1,18 +0,0 @@
-=== 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

@@ -1,18 +0,0 @@
-=== 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

@@ -1,33 +0,0 @@
-=== 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

@@ -1,13 +0,0 @@
-=== 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

@@ -1,14 +0,0 @@
-=== 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

@@ -1,15 +0,0 @@
-=== 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

@@ -1,27 +0,0 @@
-=== 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

@@ -1,27 +0,0 @@
-=== 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

@@ -1,27 +0,0 @@
-=== 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

@@ -1,29 +0,0 @@
-=== 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

@@ -1,31 +0,0 @@
-=== 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

@@ -1,25 +0,0 @@
-=== 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

@@ -1,26 +0,0 @@
-=== 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

@@ -1,26 +0,0 @@
-=== 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

@@ -1,29 +0,0 @@
-=== 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

@@ -1,28 +0,0 @@
-=== 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

@@ -1,9 +0,0 @@
-=== 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

@@ -1,23 +0,0 @@
-=== 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

@@ -1,27 +0,0 @@
-=== 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

@@ -1,16 +0,0 @@
-=== 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

@@ -1,16 +0,0 @@
-=== 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*