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
89pub(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 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 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, ¤t, &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 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 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 == ¤t.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 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 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 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}