1use std::{
2 borrow::Borrow,
3 collections::HashMap,
4 mem::take,
5 sync::{
6 Arc,
7 atomic::{AtomicBool, AtomicU64, Ordering},
8 },
9};
10
11use futures::{FutureExt, StreamExt, TryFutureExt, TryStreamExt, future::join};
12use ruma::{
13 EventId, OwnedEventId, OwnedRoomId, RoomId, RoomVersionId,
14 events::{StateEventType, TimelineEventType},
15 room_version_rules::RoomVersionRules,
16};
17use tracing::{Instrument, Span};
18use tuwunel_core::{
19 Result, debug, debug_warn, defer, err, implement, trace,
20 utils::{
21 math::fetch_add_usize,
22 stream::{BroadbandExt, IterStream, ReadyExt, WidebandExt},
23 },
24};
25use tuwunel_matrix::{
26 Event, PduEvent,
27 pdu::PrevEvents,
28 room::state::resolution::{AuthCheckOutcome, auth_check},
29 room_version::{self, from_create_event},
30};
31
32use crate::rooms::{
33 short::{ShortStateHash, ShortStateKey},
34 state::IdMapState,
35 state_compressor::CompressedState,
36};
37
38#[cfg(test)]
39mod tests;
40
41type StateIds = HashMap<ShortStateKey, OwnedEventId>;
43
44#[derive(Debug)]
46pub struct LocalBuildReport {
47 pub state_len: Option<usize>,
48 pub visited: usize,
49 pub forks: usize,
50 pub gate_drops: usize,
51 pub memo_hits: usize,
52 pub fallback: Option<String>,
53}
54
55#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
60pub struct StateLocalMetrics {
61 pub walk_attempts: u64,
63 pub walk_resolved: u64,
65 pub fallback_absent: u64,
67 pub fallback_ceiling: u64,
69 pub fallback_auth_missing: u64,
71 pub fallback_all_committed: u64,
73 pub fallback_entries: u64,
75 pub fallback_canary: u64,
77 pub fallback_create_mismatch: u64,
79 pub fallback_unevaluable: u64,
81 pub fallback_error: u64,
83 pub walk_failures: u64,
85 pub gate_denials: u64,
87}
88
89#[derive(Default)]
90pub(super) struct StateLocalCounters {
91 walk_attempts: AtomicU64,
92 walk_resolved: AtomicU64,
93 fallback_absent: AtomicU64,
94 fallback_ceiling: AtomicU64,
95 fallback_auth_missing: AtomicU64,
96 fallback_all_committed: AtomicU64,
97 fallback_entries: AtomicU64,
98 fallback_canary: AtomicU64,
99 fallback_create_mismatch: AtomicU64,
100 fallback_unevaluable: AtomicU64,
101 fallback_error: AtomicU64,
102 walk_failures: AtomicU64,
103 gate_denials: AtomicU64,
104}
105
106struct WalkAttempt {
107 counters: Arc<StateLocalCounters>,
108 settled: bool,
109}
110
111#[implement(StateLocalCounters)]
112fn start_walk(&self) { self.walk_attempts.fetch_add(1, Ordering::Relaxed); }
113
114#[implement(StateLocalCounters)]
115fn settle_walk(&self, outcome: WalkOutcome) {
116 match outcome {
117 | WalkOutcome::Resolved => {
118 self.walk_resolved.fetch_add(1, Ordering::Relaxed);
119 },
120 | WalkOutcome::Fallback(fallback) => self.record_fallback(fallback),
121 | WalkOutcome::Failure => {
122 self.walk_failures.fetch_add(1, Ordering::Relaxed);
123 },
124 }
125}
126
127#[implement(StateLocalCounters)]
128fn record_fallback(&self, fallback: Fallback) {
129 let counter = match fallback {
130 | Fallback::Absent => &self.fallback_absent,
131 | Fallback::Ceiling => &self.fallback_ceiling,
132 | Fallback::AuthMissing => &self.fallback_auth_missing,
133 | Fallback::AllCommitted => &self.fallback_all_committed,
134 | Fallback::Entries => &self.fallback_entries,
135 | Fallback::Canary => &self.fallback_canary,
136 | Fallback::CreateMismatch => &self.fallback_create_mismatch,
137 | Fallback::Unevaluable => &self.fallback_unevaluable,
138 | Fallback::Error => &self.fallback_error,
139 };
140
141 counter.fetch_add(1, Ordering::Relaxed);
142}
143
144#[implement(StateLocalCounters)]
145fn add_gate_denials(&self, gate_denials: usize) {
146 if gate_denials == 0 {
147 return;
148 }
149
150 fetch_add_usize(&self.gate_denials, gate_denials, Ordering::Relaxed);
151}
152
153#[implement(StateLocalCounters)]
154fn snapshot(&self) -> StateLocalMetrics {
155 StateLocalMetrics {
156 walk_attempts: self.walk_attempts.load(Ordering::Relaxed),
157 walk_resolved: self.walk_resolved.load(Ordering::Relaxed),
158 fallback_absent: self.fallback_absent.load(Ordering::Relaxed),
159 fallback_ceiling: self.fallback_ceiling.load(Ordering::Relaxed),
160 fallback_auth_missing: self.fallback_auth_missing.load(Ordering::Relaxed),
161 fallback_all_committed: self
162 .fallback_all_committed
163 .load(Ordering::Relaxed),
164 fallback_entries: self.fallback_entries.load(Ordering::Relaxed),
165 fallback_canary: self.fallback_canary.load(Ordering::Relaxed),
166 fallback_create_mismatch: self
167 .fallback_create_mismatch
168 .load(Ordering::Relaxed),
169 fallback_unevaluable: self.fallback_unevaluable.load(Ordering::Relaxed),
170 fallback_error: self.fallback_error.load(Ordering::Relaxed),
171 walk_failures: self.walk_failures.load(Ordering::Relaxed),
172 gate_denials: self.gate_denials.load(Ordering::Relaxed),
173 }
174}
175
176#[implement(WalkAttempt)]
177fn start(counters: Arc<StateLocalCounters>) -> Self {
178 counters.start_walk();
179
180 Self { counters, settled: false }
181}
182
183#[implement(WalkAttempt)]
184fn settle(mut self, outcome: WalkOutcome, gate_denials: usize) {
185 self.counters.add_gate_denials(gate_denials);
186 self.counters.settle_walk(outcome);
187 self.settled = true;
188}
189
190impl Drop for WalkAttempt {
191 fn drop(&mut self) {
192 if !self.settled {
193 self.counters.settle_walk(WalkOutcome::Failure);
194 }
195 }
196}
197
198#[derive(Clone, Copy, Eq, PartialEq)]
201pub(super) enum WalkMode {
202 Active,
203 Shadow,
204}
205
206struct Walk<'a> {
208 room_id: &'a RoomId,
209 room_version: &'a RoomVersionId,
210 room_rules: RoomVersionRules,
211 create_event_id: &'a EventId,
212 mode: WalkMode,
213 max_nodes: usize,
214 top_prevs: PrevEvents,
215 class: HashMap<OwnedEventId, Class>,
216 nodes: Vec<Node>,
217 order: Vec<usize>,
218 frontier: HashMap<OwnedEventId, usize>,
219 resolved: HashMap<OwnedEventId, Arc<StateIds>>,
220 live_entries: usize,
221 peak_entries: usize,
222 forks: usize,
223 gate_drops: usize,
224 memo_hits: usize,
225 fallback: Option<Fallback>,
226 attempt: Option<WalkAttempt>,
227}
228
229struct Node {
231 pdu: PduEvent,
232 consumers: usize,
233}
234
235#[derive(Clone, Copy)]
237enum Class {
238 Committed(ShortStateHash),
240
241 Memoized,
243
244 Held(usize),
246}
247
248#[derive(Clone, Copy)]
250enum Fallback {
251 Absent,
252 Ceiling,
253 AuthMissing,
254 AllCommitted,
255 Entries,
256 Canary,
257 CreateMismatch,
258 Unevaluable,
259 Error,
260}
261
262#[derive(Clone, Copy)]
263enum WalkOutcome {
264 Resolved,
265 Fallback(Fallback),
266 Failure,
267}
268
269const MAX_LIVE_ENTRIES: usize = 1 << 19;
274
275#[implement(super::Service)]
282pub(super) async fn state_at_incoming_local<Pdu>(
283 &self,
284 room_id: &RoomId,
285 incoming_pdu: &Pdu,
286 room_version: &RoomVersionId,
287 create_event_id: &EventId,
288 mode: WalkMode,
289) -> Result<Option<StateIds>>
290where
291 Pdu: Event,
292{
293 let top_prevs = incoming_pdu
294 .prev_events()
295 .map(ToOwned::to_owned)
296 .collect();
297
298 let services = self.services.clone();
299 let room_id = room_id.to_owned();
300 let room_version = room_version.clone();
301 let create_event_id = create_event_id.to_owned();
302 let parent = Span::current();
303 let attempt = WalkAttempt::start(self.state_local.clone());
304
305 let task = self.services.server.runtime().spawn(
306 async move {
307 services
308 .event_handler
309 .walk_task(room_id, room_version, create_event_id, mode, top_prevs, attempt)
310 .await
311 }
312 .instrument(parent),
313 );
314
315 let abort = task.abort_handle();
317
318 defer! {{ abort.abort(); }};
319
320 task.await.unwrap_or_else(|error| {
321 debug_warn!(
322 %error,
323 "Local state build task failed; falling back to federation fetch.",
324 );
325
326 Ok(None)
327 })
328}
329
330#[implement(super::Service)]
334#[tracing::instrument(name = "local", level = "debug", skip_all)]
335async fn walk_task(
336 &self,
337 room_id: OwnedRoomId,
338 room_version: RoomVersionId,
339 create_event_id: OwnedEventId,
340 mode: WalkMode,
341 top_prevs: PrevEvents,
342 attempt: WalkAttempt,
343) -> Result<Option<StateIds>> {
344 let max_nodes = self
345 .services
346 .server
347 .config
348 .federation
349 .resolve_state_locally_max;
350
351 let mut walk = Walk::new(
352 &room_id,
353 &room_version,
354 &create_event_id,
355 mode,
356 max_nodes,
357 top_prevs,
358 Some(attempt),
359 )?;
360
361 let state = self.walk_state(&mut walk).await;
362 let state = state.inspect_err(|_| {
363 walk.settle(WalkOutcome::Failure);
364 })?;
365
366 debug!(
367 visited = walk.nodes.len(),
368 forks = walk.forks,
369 gate_drops = walk.gate_drops,
370 memo_hits = walk.memo_hits,
371 live_entries_peak = walk.peak_entries,
372 outcome = walk.fallback.map_or("resolved", Fallback::name),
373 "Local state build finished.",
374 );
375
376 if let Some(fallback) = walk.fallback {
377 debug_warn!(
378 reason = fallback.name(),
379 "Local state build falling back to federation fetch.",
380 );
381 }
382
383 let (state, outcome) = match (state, walk.fallback) {
384 | (Some(state), None) => (Some(state), WalkOutcome::Resolved),
385 | (None, Some(fallback)) => (None, WalkOutcome::Fallback(fallback)),
386 | _ => {
387 debug_assert!(false, "local walk state and fallback disagree");
388 (None, WalkOutcome::Failure)
389 },
390 };
391
392 walk.settle(outcome);
393
394 Ok(state)
395}
396
397#[implement(super::Service)]
401#[inline]
402#[must_use]
403pub fn state_local_metrics(&self) -> StateLocalMetrics { self.state_local.snapshot() }
404
405#[implement(super::Service)]
410pub async fn local_state_report(&self, event_id: &EventId) -> Result<LocalBuildReport> {
411 let pdu = self.services.timeline.get_pdu(event_id).await?;
412
413 let create_event = self
414 .services
415 .state_accessor
416 .room_state_get(pdu.room_id(), &StateEventType::RoomCreate, "")
417 .await?;
418
419 let room_version = from_create_event(&create_event)?;
420 let max_nodes = self
421 .services
422 .server
423 .config
424 .federation
425 .resolve_state_locally_max;
426
427 let top_prevs = pdu.prev_events().map(ToOwned::to_owned).collect();
428
429 let mut walk = Walk::new(
430 pdu.room_id(),
431 &room_version,
432 create_event.event_id(),
433 WalkMode::Shadow,
434 max_nodes,
435 top_prevs,
436 None,
437 )?;
438
439 let state = self.walk_state(&mut walk).await?;
440
441 Ok(LocalBuildReport {
442 state_len: state.map(|state| state.len()),
443 visited: walk.nodes.len(),
444 forks: walk.forks,
445 gate_drops: walk.gate_drops,
446 memo_hits: walk.memo_hits,
447 fallback: walk
448 .fallback
449 .map(|fallback| fallback.name().to_owned()),
450 })
451}
452
453#[implement(super::Service)]
456async fn walk_state(&self, walk: &mut Walk<'_>) -> Result<Option<StateIds>> {
457 self.walk_discover(walk).await?;
458
459 if walk.fallback.is_some() {
460 return Ok(None);
461 }
462
463 self.walk_build(walk)
464 .boxed() .await
466}
467
468#[implement(super::Service)]
472async fn walk_discover(&self, walk: &mut Walk<'_>) -> Result {
473 let mut stack: Vec<(OwnedEventId, bool)> = walk
474 .top_prevs
475 .iter()
476 .map(|prev| (prev.clone(), false))
477 .collect();
478
479 while let Some((event_id, expanded)) = stack.pop() {
480 self.services.server.check_running()?;
481
482 if expanded {
483 let Some(Class::Held(index)) = walk.class.get(&event_id).copied() else {
485 debug_assert!(false, "expanded stack entries are held nodes");
486 walk.fallback = Some(Fallback::Error);
487 return Ok(());
488 };
489
490 walk.order.push(index);
491 continue;
492 }
493
494 if walk.class.contains_key(&event_id) {
495 continue;
496 }
497
498 if let Ok(shortstatehash) = self
499 .services
500 .state
501 .pdu_shortstatehash(&event_id)
502 .await
503 {
504 walk.class
505 .insert(event_id, Class::Committed(shortstatehash));
506
507 continue;
508 }
509
510 if self
511 .db
512 .eventid_resolvedstate
513 .exists(&event_id)
514 .await
515 .is_ok()
516 {
517 walk.class.insert(event_id, Class::Memoized);
518 continue;
519 }
520
521 let Ok(pdu) = self.services.timeline.get_pdu(&event_id).await else {
522 trace!(%event_id, "Ancestor is not held locally.");
523 walk.fallback = Some(Fallback::Absent);
524 return Ok(());
525 };
526
527 if walk.nodes.len() >= walk.max_nodes {
528 walk.fallback = Some(Fallback::Ceiling);
529 return Ok(());
530 }
531
532 if pdu.prev_events().next().is_none() {
533 debug_warn!(%event_id, "Held uncommitted ancestor has no prev events.");
534 walk.fallback = Some(Fallback::Error);
535 return Ok(());
536 }
537
538 if !self.walk_auth_present(walk, &pdu).await {
539 walk.fallback = Some(Fallback::AuthMissing);
540 return Ok(());
541 }
542
543 walk.class
544 .insert(event_id.clone(), Class::Held(walk.nodes.len()));
545
546 stack.push((event_id, true));
547 stack.extend(
548 pdu.prev_events()
549 .map(|prev| (prev.to_owned(), false)),
550 );
551 walk.nodes.push(Node { pdu, consumers: 0 });
552 }
553
554 if walk.nodes.is_empty() {
555 walk.fallback = Some(Fallback::AllCommitted);
558 return Ok(());
559 }
560
561 walk.count_consumers();
562
563 Ok(())
564}
565
566#[implement(super::Service)]
570async fn walk_auth_present(&self, walk: &Walk<'_>, pdu: &PduEvent) -> bool {
571 let is_hydra = !walk
572 .room_rules
573 .event_format
574 .allow_room_create_in_auth_events;
575
576 let not_create = *pdu.kind() != TimelineEventType::RoomCreate;
577 let hydra_create_id = (not_create && is_hydra)
578 .then(|| pdu.room_id().as_event_id().ok())
579 .flatten();
580
581 pdu.auth_events()
582 .chain(hydra_create_id.as_deref())
583 .stream()
584 .all(|auth_id| self.services.timeline.pdu_exists(auth_id))
585 .await
586}
587
588#[implement(super::Service)]
591async fn walk_build(&self, walk: &mut Walk<'_>) -> Result<Option<StateIds>> {
592 let order = take(&mut walk.order);
593 for index in order {
594 self.services.server.check_running()?;
595
596 if !self.walk_node(walk, index).await {
597 return Ok(None);
598 }
599 }
600
601 let top_prevs = take(&mut walk.top_prevs);
602 let state = match top_prevs.as_slice() {
603 | [prev] => self.state_after(walk, prev).await,
604 | _ => self.fork_resolve(walk, &top_prevs, None).await,
605 };
606
607 let Some(state) = state else {
608 return Ok(None);
609 };
610
611 let create_entry = self
614 .services
615 .short
616 .get_shortstatekey(&StateEventType::RoomCreate, "")
617 .await
618 .ok()
619 .and_then(|shortstatekey| state.get(&shortstatekey))
620 .map(AsRef::as_ref);
621
622 if state.is_empty() || create_entry != Some(walk.create_event_id) {
623 walk.fallback = Some(Fallback::CreateMismatch);
624 return Ok(None);
625 }
626
627 walk.resolved.clear();
628
629 let state = Arc::try_unwrap(state).unwrap_or_else(|state| (*state).clone());
630
631 Ok(Some(state))
632}
633
634#[implement(super::Service)]
637async fn walk_node(&self, walk: &mut Walk<'_>, index: usize) -> bool {
638 let node = &walk.nodes[index];
639 let event_id = node.pdu.event_id().to_owned();
640 let prevs: PrevEvents = node
641 .pdu
642 .prev_events()
643 .map(ToOwned::to_owned)
644 .collect();
645
646 let before = match prevs.as_slice() {
647 | [prev] => self.state_after(walk, prev).await,
648 | _ =>
649 self.fork_resolve(walk, &prevs, Some(&event_id))
650 .await,
651 };
652
653 let Some(before) = before else {
654 return false;
655 };
656
657 let after = match walk.nodes[index].pdu.state_key() {
658 | None => Ok(before),
659 | Some(_) =>
660 self.gated_fold(
661 &walk.room_rules,
662 &mut walk.gate_drops,
663 &walk.nodes[index].pdu,
664 &before,
665 )
666 .await,
667 };
668
669 let after = after.inspect_err(|error| {
670 debug_warn!(event_id = %event_id, %error, "Auth gate could not be evaluated.");
671 });
672
673 let Ok(after) = after else {
674 walk.fallback = Some(Fallback::Unevaluable);
675 return false;
676 };
677
678 if !walk.retain(event_id, after) {
679 return false;
680 }
681
682 walk.release(&prevs);
683
684 true
685}
686
687#[implement(super::Service)]
690async fn state_after(&self, walk: &mut Walk<'_>, event_id: &EventId) -> Option<Arc<StateIds>> {
691 if let Some(state) = walk.resolved.get(event_id) {
692 return Some(state.clone());
693 }
694
695 let state = match walk.class.get(event_id).copied() {
696 | Some(Class::Committed(shortstatehash)) =>
697 self.committed_state_after(walk, event_id, shortstatehash)
698 .await,
699 | Some(Class::Memoized) => self.memoized_state_after(walk, event_id).await,
700 | Some(Class::Held(_)) | None => {
701 debug_assert!(false, "held nodes resolve before their consumers");
702 walk.fallback = Some(Fallback::Error);
703 None
704 },
705 }?;
706
707 walk.retain(event_id.to_owned(), state.clone())
708 .then_some(state)
709}
710
711#[implement(super::Service)]
719async fn committed_state_after(
720 &self,
721 walk: &mut Walk<'_>,
722 event_id: &EventId,
723 shortstatehash: ShortStateHash,
724) -> Option<Arc<StateIds>> {
725 let pdu = self.services.timeline.get_pdu(event_id);
726
727 let state = self
728 .services
729 .state_accessor
730 .state_full_ids_strict(shortstatehash)
731 .try_collect::<StateIds>();
732
733 let (pdu, state) = join(pdu, state).await;
734 let Ok(mut state) = state.inspect_err(|e| {
735 debug_warn!(%event_id, %e, "Failed loading complete committed state.");
736 }) else {
737 walk.fallback = Some(Fallback::Unevaluable);
738 return None;
739 };
740
741 let Ok(pdu) = pdu.inspect_err(|e| {
742 debug_warn!(%event_id, %e, "Failed loading committed event.");
743 }) else {
744 walk.fallback = Some(Fallback::Error);
745 return None;
746 };
747
748 if let Some(state_key) = pdu.state_key() {
749 let event_type = pdu.event_type().to_cow_str().into();
750 let shortstatekey = self
751 .services
752 .short
753 .get_or_create_shortstatekey(&event_type, state_key)
754 .await;
755
756 state.insert(shortstatekey, event_id.to_owned());
757 }
758
759 Some(Arc::new(state))
760}
761
762#[implement(super::Service)]
766async fn memoized_state_after(
767 &self,
768 walk: &mut Walk<'_>,
769 event_id: &EventId,
770) -> Option<Arc<StateIds>> {
771 walk.memo_hits = walk.memo_hits.saturating_add(1);
772
773 let state = self.cached_resolved_state(event_id);
774
775 let pdu = self
776 .services
777 .timeline
778 .get_pdu(event_id)
779 .inspect_err(|e| debug_warn!(%event_id, %e, "Failed loading memoized event."));
780
781 let (state, pdu) = join(state, pdu).await;
782
783 let state = match state {
784 | Ok(Some(state)) => state,
785 | Ok(None) => {
786 walk.fallback = Some(Fallback::Canary);
787 return None;
788 },
789 | Err(e) => {
790 debug_warn!(%event_id, %e, "Failed loading complete memoized state.");
791 walk.fallback = Some(Fallback::Unevaluable);
792 return None;
793 },
794 };
795
796 let Ok(pdu) = pdu else {
797 walk.fallback = Some(Fallback::Error);
798 return None;
799 };
800
801 let before = Arc::new(state);
802 if pdu.state_key().is_none() {
803 return Some(before);
804 }
805
806 let after = self
807 .gated_fold(&walk.room_rules, &mut walk.gate_drops, &pdu, &before)
808 .await;
809
810 match after {
811 | Ok(after) => Some(after),
812 | Err(error) => {
813 debug_warn!(%event_id, %error, "Memoized auth gate could not be evaluated.");
814 walk.fallback = Some(Fallback::Unevaluable);
815 None
816 },
817 }
818}
819
820#[implement(super::Service)]
826async fn gated_fold(
827 &self,
828 room_rules: &RoomVersionRules,
829 gate_drops: &mut usize,
830 pdu: &PduEvent,
831 before: &Arc<StateIds>,
832) -> Result<Arc<StateIds>> {
833 let create_shortstatekey = self
834 .services
835 .short
836 .get_shortstatekey(&StateEventType::RoomCreate, "")
837 .await?;
838
839 if !before.contains_key(&create_shortstatekey) {
840 return Err(err!(Database("State before event is missing the room create event.")));
841 }
842
843 let state_fetch = IdMapState { services: &self.services, ids: before };
844
845 if let AuthCheckOutcome::Deny(error) =
846 auth_check(room_rules, pdu, &*self.services.timeline, state_fetch).await?
847 {
848 debug!(event_id = %pdu.event_id(), %error, "Auth gate rejected fold.");
849 *gate_drops = gate_drops.saturating_add(1);
850 return Ok(before.clone());
851 }
852
853 let state_key = pdu.state_key().expect("only state events fold");
854
855 let event_type = pdu.event_type().to_cow_str().into();
856 let shortstatekey = self
857 .services
858 .short
859 .get_or_create_shortstatekey(&event_type, state_key)
860 .await;
861
862 let mut state = StateIds::clone(before);
863 state.insert(shortstatekey, pdu.event_id().to_owned());
864
865 Ok(Arc::new(state))
866}
867
868#[implement(super::Service)]
872async fn fork_resolve(
873 &self,
874 walk: &mut Walk<'_>,
875 prevs: &[OwnedEventId],
876 memo_event_id: Option<&EventId>,
877) -> Option<Arc<StateIds>> {
878 walk.forks = walk.forks.saturating_add(1);
879
880 let mut afters = Vec::with_capacity(prevs.len());
882 for prev in prevs {
883 afters.push(self.state_after(walk, prev).await?);
884 }
885
886 let (room_id, room_version) = (walk.room_id, walk.room_version);
887 let fork_states: Result<Vec<_>> = afters
888 .iter()
889 .stream()
890 .wide_then(async |after| {
891 let state = after
892 .iter()
893 .map(|(shortstatekey, event_id)| (*shortstatekey, event_id));
894
895 self.fork_state(state).await
896 })
897 .try_collect()
898 .await;
899
900 let Ok(fork_states) = fork_states.inspect_err(|e| {
901 debug_warn!(%e, "Failed converting complete fork state.");
902 }) else {
903 walk.fallback = Some(Fallback::Unevaluable);
904 return None;
905 };
906
907 let chain_complete = AtomicBool::new(true);
908 let auth_chains = prevs
909 .iter()
910 .zip(&afters)
911 .stream()
912 .wide_then(|(prev_event, after)| {
913 self.fork_chain_strict(
914 room_id,
915 room_version,
916 after.values().map(Borrow::borrow),
917 &chain_complete,
918 )
919 .inspect_err(move |e| {
920 debug_warn!(%prev_event, %e, "Failed loading complete fork auth chain.");
921 })
922 })
923 .ready_filter_map(Result::ok);
924
925 let resolved = self
926 .state_resolution(
927 room_id,
928 room_version,
929 fork_states.into_iter().stream(),
930 auth_chains,
931 Some(&chain_complete),
932 )
933 .await;
934
935 if !chain_complete.load(Ordering::Relaxed) {
938 debug_warn!("Polled fork auth chain was incomplete.");
939 walk.fallback = Some(Fallback::Unevaluable);
940 return None;
941 }
942
943 let Ok(resolved) = resolved else {
944 walk.fallback = Some(Fallback::Error);
945 return None;
946 };
947
948 let state: StateIds = resolved
949 .into_iter()
950 .stream()
951 .broad_then(async |((event_type, state_key), event_id)| {
952 self.services
953 .short
954 .get_or_create_shortstatekey(&event_type, &state_key)
955 .map(move |shortstatekey| (shortstatekey, event_id))
956 .await
957 })
958 .collect()
959 .await;
960
961 if let Some(event_id) = memo_event_id.filter(|_| walk.mode == WalkMode::Active) {
962 let compressed: Arc<CompressedState> = self
965 .services
966 .state_compressor
967 .compress_state_events(
968 state
969 .iter()
970 .map(|(shortstatekey, event_id)| (shortstatekey, event_id.borrow())),
971 )
972 .collect()
973 .map(Arc::new)
974 .await;
975
976 self.cache_resolved_state(walk.room_id, event_id, compressed)
977 .await;
978 }
979
980 Some(Arc::new(state))
981}
982
983impl<'a> Walk<'a> {
984 fn new(
985 room_id: &'a RoomId,
986 room_version: &'a RoomVersionId,
987 create_event_id: &'a EventId,
988 mode: WalkMode,
989 max_nodes: usize,
990 top_prevs: PrevEvents,
991 attempt: Option<WalkAttempt>,
992 ) -> Result<Self> {
993 Ok(Self {
994 room_id,
995 room_version,
996 room_rules: room_version::rules(room_version)?,
997 create_event_id,
998 mode,
999 max_nodes,
1000 top_prevs,
1001 class: HashMap::new(),
1002 nodes: Vec::new(),
1003 order: Vec::new(),
1004 frontier: HashMap::new(),
1005 resolved: HashMap::new(),
1006 live_entries: 0,
1007 peak_entries: 0,
1008 forks: 0,
1009 gate_drops: 0,
1010 memo_hits: 0,
1011 fallback: None,
1012 attempt,
1013 })
1014 }
1015
1016 fn settle(&mut self, outcome: WalkOutcome) {
1017 if let Some(attempt) = self.attempt.take() {
1018 attempt.settle(outcome, self.gate_drops);
1019 }
1020 }
1021
1022 fn count_consumers(&mut self) {
1025 let mut held = vec![0_usize; self.nodes.len()];
1026
1027 let edges = self
1028 .nodes
1029 .iter()
1030 .flat_map(|node| node.pdu.prev_events())
1031 .chain(self.top_prevs.iter().map(AsRef::as_ref));
1032
1033 for prev in edges {
1034 match self.class.get(prev).copied() {
1035 | Some(Class::Held(index)) => held[index] = held[index].saturating_add(1),
1036 | Some(_) => {
1037 let consumers = self.frontier.entry(prev.to_owned()).or_default();
1038
1039 *consumers = consumers.saturating_add(1);
1040 },
1041 | None => debug_assert!(false, "every walk edge is classified"),
1042 }
1043 }
1044
1045 for (node, consumers) in self.nodes.iter_mut().zip(held) {
1046 node.consumers = consumers;
1047 }
1048 }
1049
1050 fn retain(&mut self, event_id: OwnedEventId, state: Arc<StateIds>) -> bool {
1054 let live_entries = self.live_entries.saturating_add(state.len());
1055 if live_entries > MAX_LIVE_ENTRIES {
1056 self.fallback = Some(Fallback::Entries);
1057 return false;
1058 }
1059
1060 self.live_entries = live_entries;
1061 self.peak_entries = self.peak_entries.max(live_entries);
1062 self.resolved.insert(event_id, state);
1063
1064 true
1065 }
1066
1067 fn release(&mut self, prevs: &[OwnedEventId]) {
1070 for prev in prevs {
1071 let remaining = match self.class.get(prev).copied() {
1072 | Some(Class::Held(index)) => {
1073 let node = &mut self.nodes[index];
1074 node.consumers = node.consumers.saturating_sub(1);
1075 node.consumers
1076 },
1077 | _ => {
1078 let Some(consumers) = self.frontier.get_mut(prev) else {
1079 continue;
1080 };
1081
1082 *consumers = consumers.saturating_sub(1);
1083 *consumers
1084 },
1085 };
1086
1087 if remaining == 0
1088 && let Some(state) = self.resolved.remove(prev)
1089 {
1090 self.live_entries = self.live_entries.saturating_sub(state.len());
1091 }
1092 }
1093 }
1094}
1095
1096impl Drop for Walk<'_> {
1097 fn drop(&mut self) { self.settle(WalkOutcome::Failure); }
1098}
1099
1100impl Fallback {
1101 fn name(self) -> &'static str {
1102 match self {
1103 | Self::Absent => "absent",
1104 | Self::Ceiling => "ceiling",
1105 | Self::AuthMissing => "auth_missing",
1106 | Self::AllCommitted => "all_committed",
1107 | Self::Entries => "entries",
1108 | Self::Canary => "canary",
1109 | Self::CreateMismatch => "create_mismatch",
1110 | Self::Unevaluable => "unevaluable",
1111 | Self::Error => "error",
1112 }
1113 }
1114}