Skip to main content

tuwunel_service/rooms/event_handler/
state_local_build.rs

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
41/// State before or after one event, in the shape the sibling builders return.
42type StateIds = HashMap<ShortStateKey, OwnedEventId>;
43
44/// Summary of one local build attempt, for the admin debug command.
45#[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/// Immutable process-lifetime totals for production local state builds.
56///
57/// Relaxed loads make each snapshot observational rather than a
58/// synchronization primitive.
59#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
60pub struct StateLocalMetrics {
61	/// Production local walks started.
62	pub walk_attempts: u64,
63	/// Local walks that produced complete state.
64	pub walk_resolved: u64,
65	/// Walks that fell back because an ancestor was absent.
66	pub fallback_absent: u64,
67	/// Walks that reached the configured node ceiling.
68	pub fallback_ceiling: u64,
69	/// Walks with an absent auth dependency.
70	pub fallback_auth_missing: u64,
71	/// Walks whose ancestors were all committed.
72	pub fallback_all_committed: u64,
73	/// Walks that reached the live-entry ceiling.
74	pub fallback_entries: u64,
75	/// Walks whose memo canary was absent.
76	pub fallback_canary: u64,
77	/// Walks whose create event did not match.
78	pub fallback_create_mismatch: u64,
79	/// Walks whose complete inputs could not be evaluated.
80	pub fallback_unevaluable: u64,
81	/// Walks that fell back after a recoverable lookup or state-build error.
82	pub fallback_error: u64,
83	/// Walks whose inner result errored or whose task did not complete.
84	pub walk_failures: u64,
85	/// State-event folds denied by the positional auth gate.
86	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/// Active writes fork-node memo rows; Shadow suppresses all persistent
199/// writes.
200#[derive(Clone, Copy, Eq, PartialEq)]
201pub(super) enum WalkMode {
202	Active,
203	Shadow,
204}
205
206/// State threaded through one walk's discovery and build phases.
207struct 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
229/// Held outlier in the walk sub-DAG.
230struct Node {
231	pdu: PduEvent,
232	consumers: usize,
233}
234
235/// Ancestry classification from the discovery phase.
236#[derive(Clone, Copy)]
237enum Class {
238	/// Committed to the timeline with resolved state at the event.
239	Committed(ShortStateHash),
240
241	/// Uncommitted, but an eventid_resolvedstate row exists.
242	Memoized,
243
244	/// Uncommitted outlier we hold; the index into Walk::nodes.
245	Held(usize),
246}
247
248/// Why a walk gave up; every reason falls back to the federation fetch.
249#[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
269/// Ceiling on simultaneously live state-map entries across one walk: the sum
270/// of the lengths of materialized maps no consumer has released yet.
271/// Exceeding it falls back to the federation fetch. Deliberately a const, not
272/// config; revisit only if operation trips it.
273const MAX_LIVE_ENTRIES: usize = 1 << 19;
274
275/// Build the state before `incoming_pdu` from events we already hold, walking
276/// locally held uncommitted ancestry down to committed or memoized ancestors
277/// with an auth gate on every folded state event. Some(map) is a complete
278/// gated build in the shape the sibling builders return; None falls back to
279/// the federation state fetch, for any reason. Err propagates only server
280/// shutdown and room-version failures.
281#[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	// Abort on caller cancellation; a dropped JoinHandle only detaches.
316	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/// Walk body on its own task: a poll descends every combinator layer from the
331/// task root, and under /send intake, already the server's deepest stack, the
332/// walk's auth-gate subtree overflows the worker stack in debug builds.
333#[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/// Read an observational snapshot of production local-build totals.
398///
399/// The values cover this process lifetime and do not reset when read.
400#[implement(super::Service)]
401#[inline]
402#[must_use]
403pub fn state_local_metrics(&self) -> StateLocalMetrics { self.state_local.snapshot() }
404
405/// Run a diagnostic walk for one stored event and describe the outcome.
406///
407/// The walk does not write authoritative state, resolved-state memos, or
408/// production counters. It may allocate short IDs and warm auth-chain caches.
409#[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/// Drive discovery then the post-order build; any abnormality sets
454/// walk.fallback and yields None.
455#[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() // size firewall
465		.await
466}
467
468/// Classify the uncommitted ancestry below the incoming event with point
469/// reads only, emitting held nodes in post-order; every condition the build
470/// cannot survive sets walk.fallback here, before any state materializes.
471#[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			// Post-order emission: every prev of this node is fully classified.
484			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		// The sibling builders already failed the all-committed shape before
556		// the walk ran; re-resolving it would only fail again.
557		walk.fallback = Some(Fallback::AllCommitted);
558		return Ok(());
559	}
560
561	walk.count_consumers();
562
563	Ok(())
564}
565
566/// The auth gate must stay evaluable: every auth event of a held node has to
567/// be present locally before the walk commits to building through it. Hydra
568/// rooms chain the create event implied by the room id.
569#[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/// Compute state through the walk sub-DAG in post-order, so every node's
589/// prevs resolve before it, then combine at the incoming event's own prevs.
590#[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	// Mirror fetch_state's canary: the original create event must still be in
612	// the built state.
613	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/// Resolve one held node: state-before from its prevs, its own gated fold on
635/// top, retained until the last consumer releases it.
636#[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/// State after one prev: an already-resolved node or materialized frontier
688/// entry shares its map; otherwise the frontier materializes here.
689#[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/// State after a committed frontier event: its stored state plus its own key
712/// folded unguarded, exactly the degree-one builder's shape.
713///
714/// Every event holding a `shorteventid_shortstatehash` row passed spec check 5
715/// (auth against the state at its own position) as a hard reject; soft failure
716/// (spec check 6) still writes the row, so soft-failed events are valid fold
717/// inputs while positionally rejected events never gain a row.
718#[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/// State after a memoized frontier event: the memo row is its complete
763/// state-before, so its own gated fold preserves that guarantee for
764/// descendants.
765#[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/// Fold the event's own state key over its state-before, only when the
821/// position-correct auth gate passes; a rejection leaves state unchanged.
822///
823/// Evaluation failures abort the local walk so federation can rebuild a
824/// complete input state.
825#[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/// State before a fork node, resolving the state after each of its prevs
869/// exactly as the committed-prev fork resolves today. Fork outputs are the
870/// artifacts worth memoizing; chain nodes are cheap to re-derive.
871#[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	// Sequential: materializing a frontier prev writes the walk's accounting.
881	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	// Only polled chains can affect resolution. Check completeness before using
936	// its result or writing the transitively complete memo.
937	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		// Strict frontier loads and the polled-chain sentinel make this state
963		// transitively complete for later memo consumers.
964		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	/// Consumer counts drive state-map reaping: each held node's prevs and
1023	/// the incoming event's own prevs each count one consumption.
1024	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	/// Retain a computed state map until its last consumer releases it; the
1051	/// running live-entry total is the walk's memory ceiling. Arc-shared maps
1052	/// count once per holder, deliberately over-counting toward the ceiling.
1053	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	/// Release one consumption of each prev, dropping maps no consumer
1068	/// awaits.
1069	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}