Skip to main content

tuwunel_service/integrity/short_ids/state/
history.rs

1use std::{
2	collections::{BTreeMap, BTreeSet},
3	io::Error as IoError,
4	iter::{once, repeat_n},
5	str::from_utf8,
6};
7
8use futures::{FutureExt, TryFutureExt, TryStreamExt, stream::unfold};
9use ruma::{EventId, OwnedEventId, OwnedRoomId, RoomId, api::error::ErrorKind};
10use serde::Deserialize;
11use tuwunel_core::{
12	Error, Result,
13	utils::{
14		IterStream, OptionExt, TryReadyExt,
15		result::NotFound,
16		stream::{TryBroadbandExt, TryWidebandExt},
17	},
18};
19use tuwunel_database::{Database, keyval::KeyBuf};
20use tuwunel_matrix::{
21	PduEvent,
22	pdu::AuthEvents,
23	room::state::resolution::{AuthCheckOutcome, FetchEvent, StateMap, auth_check},
24	room_version::{from_create_event, rules},
25};
26
27use super::{
28	CompressedState, Diff, Identity, Mapping, Materialized, Projection, Services, apply, claim,
29	identity, layer, lookup, materialize, project, project_entry, row, short_of, statekey,
30	visit as visit_state,
31};
32use crate::{
33	integrity::ScanExt,
34	rooms::state_compressor::{
35		CompressedStateEvent, compress_state_event, parse_compressed_state_event,
36	},
37};
38
39type Anchors = BTreeMap<u64, Vec<u64>>;
40type Auth = BTreeMap<OwnedEventId, AuthEvents>;
41type Dependents<'a> = BTreeMap<&'a OwnedEventId, Vec<&'a OwnedEventId>>;
42type Events = BTreeSet<OwnedEventId>;
43type Step = (PduEvent, Option<CompressedState>);
44type Steps = Vec<Option<Step>>;
45type Boundary = (PduEvent, StateMap<PduEvent>);
46
47const EVENTS: (&str, &str) = ("eventid_shorteventid", "shorteventid_eventid");
48const STATEKEYS: (&str, &str) = ("statekey_shortstatekey", "shortstatekey_statekey");
49
50#[derive(Clone, Copy)]
51struct Accepted<'a>(&'a Services);
52
53pub(crate) struct References {
54	pub(crate) affected: BTreeSet<u64>,
55	anchors: Anchors,
56	held: BTreeSet<u64>,
57	unreadable: Vec<(&'static str, KeyBuf)>,
58	rooms: BTreeSet<OwnedRoomId>,
59	complete: bool,
60}
61
62#[derive(Deserialize)]
63struct Located {
64	room_id: OwnedRoomId,
65}
66
67impl FetchEvent for Accepted<'_> {
68	async fn get<T>(self, event_id: &EventId) -> Result<T>
69	where
70		T: for<'de> Deserialize<'de> + Send,
71	{
72		self.0
73			.timeline
74			.get_non_outlier(event_id)
75			.map_err(read_error)
76			.await
77	}
78
79	async fn exists(self, event_id: &EventId) -> Result<bool> {
80		self.0
81			.timeline
82			.non_outlier_pdu_exists(event_id)
83			.map_ok(|()| true)
84			.map_err(read_error)
85			.await
86	}
87}
88
89// Rewrap storage failures so auth cannot read them as missing or invalid evidence.
90pub(crate) fn read_error(error: Error) -> Error {
91	match error {
92		| error @ Error::Err(..) => IoError::other(error).into(),
93		| error @ Error::Io(..) if error.is_not_found() => IoError::other(error).into(),
94		| error => error,
95	}
96}
97
98#[tracing::instrument(level = "debug", skip_all)]
99pub(crate) async fn references(
100	services: &Services,
101	affected: BTreeSet<u64>,
102) -> Result<References> {
103	let initial = References {
104		affected,
105		anchors: Anchors::new(),
106		held: BTreeSet::new(),
107		unreadable: Vec::new(),
108		rooms: BTreeSet::new(),
109		complete: true,
110	};
111
112	if initial.affected.is_empty() {
113		return Ok(initial);
114	}
115
116	["shorteventid_shortstatehash", "roomid_shortstatehash", "eventid_resolvedstate"]
117		.try_stream()
118		.try_fold(initial, |references, column| scan(services, references, column))
119		.and_then(|references| locate(services, references))
120		.await
121}
122
123#[tracing::instrument(level = "debug", skip_all)]
124async fn scan(
125	services: &Services,
126	references: References,
127	column: &'static str,
128) -> Result<References> {
129	services.db[column]
130		.raw_stream()
131		.scanned(&services.server)
132		.ready_try_fold(references, |references, (key, value)| {
133			Ok(reference(references, column, key, value))
134		})
135		.await
136}
137
138fn reference(
139	references: References,
140	column: &'static str,
141	key: &[u8],
142	value: &[u8],
143) -> References {
144	let Some(id) = claim(value) else {
145		return unreadable(references, column, key);
146	};
147
148	if !references.affected.contains(&id) {
149		return references;
150	}
151
152	match column {
153		| _ if column != "shorteventid_shortstatehash" => held(references, id),
154		| _ => match short_of(key) {
155			| None => held(references, id),
156			| Some(event) => anchored(references, id, event),
157		},
158	}
159}
160
161fn unreadable(mut references: References, column: &'static str, key: &[u8]) -> References {
162	references
163		.unreadable
164		.push((column, KeyBuf::from_slice(key)));
165
166	references
167}
168
169fn held(mut references: References, id: u64) -> References {
170	references.held.insert(id);
171	references
172}
173
174fn anchored(mut references: References, id: u64, event: u64) -> References {
175	references
176		.anchors
177		.entry(id)
178		.or_default()
179		.push(event);
180
181	references
182}
183
184#[tracing::instrument(level = "debug", skip_all)]
185async fn locate(services: &Services, references: References) -> Result<References> {
186	let rooms = references
187		.unreadable
188		.iter()
189		.try_stream()
190		.broad_and_then(async |(column, key)| room(services, column, key).await)
191		.ready_try_fold(Some(BTreeSet::new()), |rooms, room| {
192			Ok(rooms.zip(room).map(|(mut rooms, room)| {
193				rooms.insert(room);
194				rooms
195			}))
196		})
197		.await?;
198
199	Ok(match rooms {
200		| Some(rooms) => References { rooms, ..references },
201		| None => incomplete(references),
202	})
203}
204
205#[tracing::instrument(level = "trace", skip_all)]
206async fn room(services: &Services, column: &str, key: &[u8]) -> Result<Option<OwnedRoomId>> {
207	let db = &services.db;
208	let event = match column {
209		| "roomid_shortstatehash" => {
210			return Ok(from_utf8(key)
211				.ok()
212				.and_then(|room| RoomId::parse(room).ok()));
213		},
214		| "eventid_resolvedstate" => Some(Identity::from_slice(key)),
215		| _ => short_of(key)
216			.map_async(async |short| {
217				lookup(db, "shorteventid_eventid", &short.to_be_bytes()).await
218			})
219			.await
220			.transpose()?
221			.flatten(),
222	};
223
224	let Some(event) = event else {
225		return Ok(None);
226	};
227
228	match lookup(db, "eventid_pduid", &event).await? {
229		| Some(pdu_id) => located(db, "pduid_pdu", &pdu_id).await,
230		| None => located(db, "eventid_outlierpdu", &event).await,
231	}
232}
233
234async fn located(db: &Database, map: &str, key: &[u8]) -> Result<Option<OwnedRoomId>> {
235	db[map]
236		.get(key)
237		.map_ok(|pdu| {
238			serde_json::from_slice(&pdu)
239				.ok()
240				.map(|located: Located| located.room_id)
241		})
242		.map(NotFound::present)
243		.map_ok(Option::flatten)
244		.await
245}
246
247fn incomplete(references: References) -> References {
248	References { complete: false, ..references }
249}
250
251#[tracing::instrument(level = "trace", skip_all)]
252pub(crate) async fn target(
253	services: &Services,
254	projection: &Projection,
255	references: &References,
256	id: u64,
257) -> Result<Materialized> {
258	if !references.complete || references.held.contains(&id) {
259		return Ok(None);
260	}
261
262	let Some(anchors) = references
263		.anchors
264		.get(&id)
265		.filter(|anchors| !anchors.is_empty())
266	else {
267		return Ok(None);
268	};
269
270	let Some(original) = row(&services.db, id).await? else {
271		return Ok(None);
272	};
273
274	let (first, agreed) = anchors
275		.try_stream()
276		.try_fold((None, true), async |(first, agreed), anchor| -> Result<_> {
277			// Once anchors disagree the row stays withheld; later anchors are never read.
278			if !agreed {
279				return Ok((first, agreed));
280			}
281
282			let next = reconstruct(services, projection, references, *anchor, id).await?;
283			let agreed = next.is_some()
284				&& first
285					.as_ref()
286					.is_none_or(|first| Some(first) == next.as_ref());
287
288			Ok((first.or(next), agreed))
289		})
290		.await?;
291
292	let Some(first) = first.filter(|_| agreed) else {
293		return Ok(None);
294	};
295
296	let target = intact(services, projection, id, &first)
297		.await?
298		.then_some((original, first));
299
300	Ok(target)
301}
302
303#[tracing::instrument(level = "trace", skip_all)]
304async fn reconstruct(
305	services: &Services,
306	projection: &Projection,
307	references: &References,
308	anchor: u64,
309	id: u64,
310) -> Result<Option<CompressedState>> {
311	let db = &services.db;
312	let Some((_, event)) =
313		identity(db, &projection.events, anchor, "shorteventid_eventid").await?
314	else {
315		return Ok(None);
316	};
317
318	let Some(anchor) = accepted(services, &event).await? else {
319		return Ok(None);
320	};
321
322	// An unreadable referrer in this room may name this state.
323	if references.rooms.contains(&anchor.room_id) {
324		return Ok(None);
325	}
326
327	if pointer(services, projection, &anchor).await? != Some(id) {
328		return Ok(None);
329	}
330
331	let steps = unfold((Some(anchor.clone()), Events::new()), async |(current, visited)| {
332		let current = current?;
333		let step = predecessor(services, projection, references, &current, &visited).await;
334		let next = step
335			.as_ref()
336			.ok()
337			.and_then(Option::as_ref)
338			.filter(|(_, boundary)| boundary.is_none())
339			.map(|(pdu, _)| pdu.clone());
340
341		Some((step, (next, visit(visited, current.event_id))))
342	})
343	.try_collect()
344	.await?;
345
346	let Some((base, steps)) = boundary(steps) else {
347		return Ok(None);
348	};
349
350	let Some((create, state)) = validate(services, projection, base, &anchor.room_id).await?
351	else {
352		return Ok(None);
353	};
354
355	let target = steps
356		.try_stream()
357		.try_fold(Some(state), async |state, pdu| -> Result<_> {
358			let Some(state) = state else {
359				return Ok(None);
360			};
361
362			let authorized = authorized(services, &pdu, &create, &state).await?;
363
364			Ok(authorized.then(|| state_row(state, pdu)))
365		})
366		.await?;
367
368	let Some(target) = target else {
369		return Ok(None);
370	};
371
372	if !authorized(services, &anchor, &create, &target).await? {
373		return Ok(None);
374	}
375
376	let compressed = target
377		.values()
378		.try_stream()
379		.broad_and_then(async |pdu| entry_for(services, projection, pdu).await)
380		.ready_try_fold(Some(CompressedState::new()), |state, entry| {
381			Ok(state.zip(entry).map(|(mut state, entry)| {
382				state.insert(entry);
383				state
384			}))
385		})
386		.await?;
387
388	Ok(compressed.and_then(|state| project(state, projection)))
389}
390
391#[tracing::instrument(level = "trace", skip_all)]
392async fn accepted(services: &Services, event: &[u8]) -> Result<Option<PduEvent>> {
393	services.server.check_running()?;
394	let db = &services.db;
395	let Some(pdu_id) = lookup(db, "eventid_pduid", event)
396		.map_ok(|pdu_id| pdu_id.filter(|pdu_id| matches!(pdu_id.len(), 16 | 24)))
397		.await?
398	else {
399		return Ok(None);
400	};
401
402	let Some(pdu) = db["pduid_pdu"]
403		.get(&pdu_id)
404		.map_ok(|pdu| serde_json::from_slice(&pdu).ok())
405		.map(NotFound::present)
406		.map_ok(Option::flatten)
407		.map_ok(|pdu| pdu.filter(|pdu: &PduEvent| pdu.event_id.as_bytes() == event))
408		.await?
409	else {
410		// A mismatched row is refused before the room read, which cannot change that.
411		return Ok(None);
412	};
413
414	let valid = lookup(db, "roomid_shortroomid", pdu.room_id.as_bytes())
415		.map_ok(|room| room.as_deref().and_then(short_of) == claim(&pdu_id))
416		.await?;
417
418	Ok(valid.then_some(pdu))
419}
420
421#[tracing::instrument(level = "trace", skip_all)]
422async fn pointer(
423	services: &Services,
424	projection: &Projection,
425	pdu: &PduEvent,
426) -> Result<Option<u64>> {
427	let db = &services.db;
428	let event_id = pdu.event_id.as_bytes();
429	let Some(short) = canonical(db, &projection.events, EVENTS, event_id).await? else {
430		return Ok(None);
431	};
432
433	let Some(id) = lookup(db, "shorteventid_shortstatehash", &short.to_be_bytes())
434		.map_ok(|value| value.as_deref().and_then(short_of))
435		.await?
436	else {
437		return Ok(None);
438	};
439
440	// A disagreeing alias settles the decline; a read still pending then cannot change it.
441	let agree = projection
442		.events
443		.aliases
444		.iter()
445		.filter(|(_, (_, identity))| identity.as_slice() == event_id)
446		.try_stream()
447		.broad_try_all(async |(alias, _)| {
448			lookup(db, "shorteventid_shortstatehash", &alias.to_be_bytes())
449				.map_ok(|pointer| {
450					pointer
451						.as_deref()
452						.is_none_or(|value| short_of(value) == Some(id))
453				})
454				.await
455		})
456		.await?;
457
458	Ok(agree.then_some(id))
459}
460
461#[tracing::instrument(level = "trace", skip_all)]
462async fn predecessor(
463	services: &Services,
464	projection: &Projection,
465	references: &References,
466	current: &PduEvent,
467	visited: &Events,
468) -> Result<Option<Step>> {
469	let [previous] = current.prev_events.as_slice() else {
470		return Ok(None);
471	};
472
473	if visited.contains(previous) || previous == &current.event_id {
474		return Ok(None);
475	}
476
477	let Some(previous) = accepted(services, previous.as_bytes()).await? else {
478		return Ok(None);
479	};
480
481	if previous.room_id != current.room_id {
482		return Ok(None);
483	}
484
485	let Some(shortstatehash) = pointer(services, projection, &previous).await? else {
486		return Ok(None);
487	};
488
489	if references.affected.contains(&shortstatehash) {
490		return Ok(Some((previous, None)));
491	}
492
493	let base = materialize(services, shortstatehash)
494		.map_ok(|materialized| materialized.and_then(|(_, state)| project(state, projection)))
495		.await?;
496
497	Ok(base.map(|base| (previous, Some(base))))
498}
499
500fn visit(mut visited: Events, event: OwnedEventId) -> Events {
501	visited.insert(event);
502	visited
503}
504
505fn boundary(mut steps: Steps) -> Option<(CompressedState, impl Iterator<Item = PduEvent>)> {
506	if steps.iter().any(Option::is_none) {
507		return None;
508	}
509
510	let (pdu, base) = steps.pop()??;
511
512	let predecessors = once(pdu).chain(
513		steps
514			.into_iter()
515			.rev()
516			.flatten()
517			.map(|(pdu, _)| pdu),
518	);
519
520	base.map(|base| (base, predecessors))
521}
522
523#[tracing::instrument(level = "trace", skip_all)]
524async fn validate(
525	services: &Services,
526	projection: &Projection,
527	base: CompressedState,
528	room: &RoomId,
529) -> Result<Option<Boundary>> {
530	// A rejected entry stops the fold as Err(None), apart from a read failure in Err(Some).
531	let loaded = base
532		.try_stream()
533		.wide_and_then(async |entry| checked_entry(services, projection, room, entry).await)
534		.map_err(Some)
535		.ready_try_fold(StateMap::new(), |state, pdu| {
536			pdu.map(|pdu| state_row(state, pdu)).ok_or(None)
537		})
538		.await;
539
540	let state = match loaded {
541		| Ok(state) => state,
542		| Err(None) => return Ok(None),
543		| Err(Some(error)) => return Err(error),
544	};
545
546	let Some(create) = state
547		.get(&("m.room.create".into(), "".into()))
548		.filter(|create| create.prev_events.is_empty() && create.auth_events.is_empty())
549		.cloned()
550	else {
551		return Ok(None);
552	};
553
554	let permitted = permits(services, &create, &create, &StateMap::new()).await?;
555
556	Ok(permitted.then_some((create, state)))
557}
558
559#[tracing::instrument(level = "trace", skip_all)]
560async fn checked_entry(
561	services: &Services,
562	projection: &Projection,
563	room: &RoomId,
564	entry: CompressedStateEvent,
565) -> Result<Option<PduEvent>> {
566	let (_, event) = parse_compressed_state_event(entry);
567	let Some((_, identity)) =
568		identity(&services.db, &projection.events, event, "shorteventid_eventid").await?
569	else {
570		return Ok(None);
571	};
572
573	let Some(pdu) = accepted(services, &identity).await? else {
574		return Ok(None);
575	};
576
577	let valid = pdu.room_id.as_str() == room.as_str()
578		&& entry_for(services, projection, &pdu).await? == Some(entry);
579
580	Ok(valid.then_some(pdu))
581}
582
583fn state_row(mut state: StateMap<PduEvent>, pdu: PduEvent) -> StateMap<PduEvent> {
584	if let Some(key) = pdu.state_key.as_ref() {
585		state.insert((pdu.kind.to_cow_str().as_ref().into(), key.clone()), pdu);
586	}
587
588	state
589}
590
591#[tracing::instrument(level = "trace", skip_all)]
592async fn permits(
593	services: &Services,
594	pdu: &PduEvent,
595	create: &PduEvent,
596	state: &StateMap<PduEvent>,
597) -> Result<bool> {
598	let Ok(rules) = from_create_event(create).and_then(|version| rules(&version)) else {
599		return Ok(false);
600	};
601
602	auth_check(&rules, pdu, Accepted(services), state)
603		.map(allowed)
604		.await
605}
606
607pub(crate) fn allowed(result: Result<AuthCheckOutcome>) -> Result<bool> {
608	match result {
609		| Ok(outcome) => Ok(matches!(outcome, AuthCheckOutcome::Allow)),
610		| Err(
611			Error::Database(..)
612			| Error::Json(..)
613			| Error::SerdeDe(..)
614			| Error::Request(ErrorKind::BadJson | ErrorKind::NotFound, ..),
615		) => Ok(false),
616		| Err(error) => Err(error),
617	}
618}
619
620#[tracing::instrument(level = "trace", skip_all)]
621async fn authorized(
622	services: &Services,
623	pdu: &PduEvent,
624	create: &PduEvent,
625	state: &StateMap<PduEvent>,
626) -> Result<bool> {
627	let authorized = authenticated(services, pdu, create).await?
628		&& permits(services, pdu, create, state).await?;
629
630	Ok(authorized)
631}
632
633#[tracing::instrument(level = "trace", skip_all)]
634async fn entry_for(
635	services: &Services,
636	projection: &Projection,
637	pdu: &PduEvent,
638) -> Result<Option<CompressedStateEvent>> {
639	let Some(key) = pdu.state_key.as_ref() else {
640		return Ok(None);
641	};
642
643	let db = &services.db;
644	let Some(shortstatekey) =
645		canonical(db, &projection.statekeys, STATEKEYS, &statekey(&pdu.kind, key)).await?
646	else {
647		return Ok(None);
648	};
649
650	canonical(db, &projection.events, EVENTS, pdu.event_id.as_bytes())
651		.map_ok(|event| event.map(|event| compress_state_event(shortstatekey, event)))
652		.await
653}
654
655#[tracing::instrument(level = "trace", skip_all)]
656async fn canonical(
657	db: &Database,
658	mapping: &Mapping,
659	(forward, reverse): (&str, &str),
660	name: &[u8],
661) -> Result<Option<u64>> {
662	let Some(short) = lookup(db, forward, name)
663		.map_ok(|value| value.as_deref().and_then(short_of))
664		.await?
665	else {
666		return Ok(None);
667	};
668
669	identity(db, mapping, short, reverse)
670		.map_ok(|checked| {
671			checked
672				.filter(|(winner, identity)| *winner == short && identity.as_slice() == name)
673				.map(|(short, _)| short)
674		})
675		.await
676}
677
678#[tracing::instrument(level = "trace", skip_all)]
679async fn authenticated(services: &Services, pdu: &PduEvent, create: &PduEvent) -> Result<bool> {
680	let pending = [pdu.event_id.clone(), create.event_id.clone()].into();
681	let walk = unfold((pending, Events::new()), async |(pending, visited)| {
682		let (event, pending) = pending_event(pending)?;
683		let fetched = accepted(services, event.as_bytes())
684			.map_ok(|pdu| pdu.filter(|pdu| admissible(pdu, create)))
685			.await;
686
687		let Ok(Some(event)) = fetched else {
688			return Some((fetched.map(|_| None), (Events::new(), visited)));
689		};
690
691		let visited = visit(visited, event.event_id.clone());
692		let pending = pending_auth(pending, &visited, &event);
693
694		Some((Ok(Some((event.event_id, event.auth_events))), (pending, visited)))
695	});
696
697	let graph = walk
698		.ready_try_fold(Some(Auth::new()), |graph, item| {
699			Ok(graph
700				.zip(item)
701				.map(|(graph, (event, dependencies))| auth_row(graph, event, dependencies)))
702		})
703		.await?;
704
705	Ok(graph.as_ref().is_some_and(acyclic))
706}
707
708fn pending_event(mut pending: Events) -> Option<(OwnedEventId, Events)> {
709	let event = pending.pop_first()?;
710
711	Some((event, pending))
712}
713
714fn admissible(event: &PduEvent, create: &PduEvent) -> bool {
715	event.room_id == create.room_id
716		&& (event.kind.to_cow_str() != "m.room.create"
717			|| (event.event_id == create.event_id
718				&& event.state_key.as_deref() == Some("")
719				&& event.prev_events.is_empty()
720				&& event.auth_events.is_empty()))
721}
722
723fn pending_auth(mut pending: Events, visited: &Events, pdu: &PduEvent) -> Events {
724	pending.extend(
725		pdu.auth_events
726			.iter()
727			.filter(|event| !visited.contains(*event))
728			.cloned(),
729	);
730
731	pending
732}
733
734fn auth_row(mut graph: Auth, event: OwnedEventId, dependencies: AuthEvents) -> Auth {
735	graph.insert(event, dependencies);
736	graph
737}
738
739fn acyclic(graph: &Auth) -> bool {
740	let dependents: Dependents<'_> = graph
741		.iter()
742		.flat_map(|(id, auth)| {
743			auth.iter()
744				.map(move |dependency| (dependency, id))
745		})
746		.fold(BTreeMap::new(), |mut dependents, (dependency, id)| {
747			dependents.entry(dependency).or_default().push(id);
748			dependents
749		});
750
751	let pending: BTreeMap<&OwnedEventId, usize> = graph
752		.iter()
753		.map(|(id, auth)| (id, auth.len()))
754		.collect();
755
756	let ready: Vec<&OwnedEventId> = pending
757		.iter()
758		.filter(|(_, count)| **count == 0)
759		.map(|(id, _)| *id)
760		.collect();
761
762	// Kahn's walk: each resolved event releases the events depending on it.
763	let resolved = repeat_n((), graph.len())
764		.scan((pending, ready), |(pending, ready), ()| {
765			let id = ready.pop()?;
766
767			dependents
768				.get(id)
769				.into_iter()
770				.flatten()
771				.filter(|dependent| released(pending, dependent))
772				.for_each(|dependent| ready.push(*dependent));
773
774			Some(())
775		})
776		.count();
777
778	resolved == graph.len()
779}
780
781fn released(pending: &mut BTreeMap<&OwnedEventId, usize>, dependent: &OwnedEventId) -> bool {
782	pending.get_mut(dependent).is_some_and(|count| {
783		*count = count.saturating_sub(1);
784		*count == 0
785	})
786}
787
788#[tracing::instrument(level = "trace", skip_all)]
789async fn intact(
790	services: &Services,
791	projection: &Projection,
792	id: u64,
793	target: &CompressedState,
794) -> Result<bool> {
795	let chain = unfold((Some(id), BTreeSet::new()), async |(id, visited)| {
796		let id = id?;
797		let diff = layer(&services.db, id)
798			.map_ok(|diff| diff.filter(|_| !visited.contains(&id)))
799			.await;
800
801		let parent = diff
802			.as_ref()
803			.ok()
804			.and_then(Option::as_ref)
805			.and_then(|diff| diff.parent);
806
807		Some((diff, (parent, visit_state(visited, id))))
808	})
809	.ready_try_fold(Some(Vec::new()), |chain, diff| {
810		Ok(chain.zip(diff).map(|(mut chain, diff)| {
811			chain.push(diff);
812			chain
813		}))
814	})
815	.await?;
816
817	let Some(diffs) = chain else {
818		return Ok(false);
819	};
820
821	let Some(damaged) = diffs
822		.iter()
823		.rev()
824		.try_fold(BTreeSet::new(), |damaged, diff| damage(damaged, diff, projection))
825	else {
826		return Ok(false);
827	};
828
829	let original = diffs
830		.into_iter()
831		.rev()
832		.fold(CompressedState::new(), apply);
833
834	let Some(original) = project(original, projection) else {
835		return Ok(false);
836	};
837
838	let unaffected = |entry: &&CompressedStateEvent| {
839		!damaged.contains(&parse_compressed_state_event(**entry).0)
840	};
841
842	let agrees = original
843		.iter()
844		.filter(unaffected)
845		.eq(target.iter().filter(unaffected));
846
847	Ok(agrees)
848}
849
850fn damage(damaged: BTreeSet<u64>, diff: &Diff, projection: &Projection) -> Option<BTreeSet<u64>> {
851	// A root's reader ignores removed entries, so only a child's overlap is damage.
852	let overlap = diff
853		.added
854		.intersection(&diff.removed)
855		.filter(|_| diff.parent.is_some());
856
857	let damaged = keys(overlap, projection).try_fold(damaged, |mut damaged, key| {
858		damaged.insert(key?);
859		Some(damaged)
860	})?;
861
862	let written = diff.added.symmetric_difference(&diff.removed);
863
864	keys(written, projection).try_fold(damaged, |mut damaged, key| {
865		damaged.remove(&key?);
866		Some(damaged)
867	})
868}
869
870fn keys<'a, I>(entries: I, projection: &Projection) -> impl Iterator<Item = Option<u64>>
871where
872	I: Iterator<Item = &'a CompressedStateEvent>,
873{
874	entries.map(move |entry| {
875		project_entry(*entry, projection).map(|entry| parse_compressed_state_event(entry).0)
876	})
877}