1use std::{
2 collections::{BTreeMap, BTreeSet},
3 iter::repeat,
4};
5
6use futures::{
7 FutureExt, Stream, StreamExt, TryFutureExt, TryStreamExt, future::try_join, stream::unfold,
8};
9use ruma::events::TimelineEventType;
10use tuwunel_core::{
11 Err, Result, implement,
12 itertools::Itertools,
13 smallvec::SmallVec,
14 utils::{
15 BoolExt, IterStream, TryReadyExt,
16 result::NotFound,
17 stream::{TryBroadbandExt, TryWidebandExt},
18 },
19};
20use tuwunel_database::{Database, SEP, keyval::ValBuf};
21
22use super::{
23 Identity, Reason, Shape,
24 check::{Finding, Subject},
25 identity::{Candidate, Family, Identities, Kind, admitted},
26 short_of,
27};
28use crate::{
29 Services,
30 integrity::ScanExt,
31 rooms::state_compressor::{
32 CompressedState, CompressedStateEvent, compress_state_event, parse_compressed_state_event,
33 },
34};
35
36pub(crate) mod history;
37pub(crate) type Parents = BTreeMap<u64, Option<u64>>;
38pub(crate) type Aliases = BTreeMap<u64, (u64, Identity)>;
39type Occurrences = BTreeMap<u64, BTreeSet<u64>>;
40pub(crate) type Absences = Vec<Absence>;
41type Absence = (u64, u64, bool, bool);
42type Observations = [Option<Observation>; 2];
43type Observation = (Shape, u64, Reason);
44pub(crate) type Materialized = Option<(ValBuf, CompressedState)>;
45type Found = SmallVec<[Finding; 1]>;
46
47pub(crate) struct Mapping {
48 pub(crate) aliases: Aliases,
49 pub(crate) refused: BTreeSet<u64>,
50}
51
52pub(crate) struct Projection {
53 pub(crate) statekeys: Mapping,
54 pub(crate) events: Mapping,
55}
56
57pub(crate) struct Census {
58 pub(crate) parents: Parents,
59 pub(crate) seeds: BTreeSet<u64>,
60 pub(crate) unknown: bool,
61 pub(crate) held: Vec<u64>,
62 pub(crate) orphans: Occurrences,
63 pub(crate) complete: bool,
64 pub(crate) projection: Projection,
65 pub(crate) exposed: BTreeSet<u64>,
66}
67
68pub(crate) struct Scanned {
69 pub(crate) id: Option<u64>,
70 pub(crate) parent: Option<u64>,
71 pub(crate) diff: Option<Diff>,
72 pub(crate) absences: Absences,
73}
74
75pub(crate) struct Diff {
76 pub(crate) parent: Option<u64>,
77 pub(crate) added: CompressedState,
78 pub(crate) removed: CompressedState,
79}
80
81#[tracing::instrument(level = "debug", skip_all)]
86pub(super) fn findings(
87 services: &Services,
88 census: Census,
89) -> impl Stream<Item = Result<Finding>> + Send + '_ {
90 let incomplete = census.unknown || !census.complete || !census.held.is_empty();
91 let head = incomplete.then_some(Finding {
92 shape: Shape::AffectedState,
93 subject: Subject::Incomplete,
94 reason: Reason::References,
95 });
96
97 let affected = descendants(&census.parents, &census.seeds).into_iter();
98
99 let states = unfold((census, affected), async |(census, mut affected)| {
102 let id = affected.next()?;
103 let found = inspect_state(services, &census, id).await;
104
105 Some((found, (census, affected)))
106 });
107
108 head.try_stream().chain(
109 states
110 .map_ok(IterStream::try_stream)
111 .try_flatten(),
112 )
113}
114
115#[tracing::instrument(level = "trace", skip_all)]
116async fn inspect_state(services: &Services, census: &Census, id: u64) -> Result<Found> {
117 services.server.check_running()?;
118 let state = |shape| Finding {
119 shape,
120 subject: Subject::State(id),
121 reason: Reason::HistoricalState,
122 };
123
124 let Some(bytes) = row(&services.db, id).await? else {
125 return Err!("state disappeared during final injectivity verification");
126 };
127
128 let Some(diff) = decode(&bytes) else {
129 return Ok([state(Shape::AffectedState)].into());
130 };
131
132 let collided = diff
133 .added
134 .is_disjoint(&diff.removed)
135 .is_false()
136 .then(|| state(Shape::DiffCollision));
137
138 let found = diff
139 .added
140 .iter()
141 .chain(&diff.removed)
142 .copied()
143 .try_stream()
144 .wide_and_then(|entry| inspect_entry(services, &census.projection, entry))
145 .ready_try_fold(collided.into_iter().collect(), observed)
146 .await?;
147
148 let invalid = materialize(services, id)
149 .await?
150 .and_then(|(_, state)| project(state, &census.projection))
151 .is_none();
152
153 let unverified = invalid || !census.seeds.contains(&id);
154
155 Ok(extended(found, unverified.then(|| state(Shape::AffectedState))))
156}
157
158#[tracing::instrument(level = "trace", skip_all)]
159async fn inspect_entry(
160 services: &Services,
161 projection: &Projection,
162 entry: CompressedStateEvent,
163) -> Result<Observations> {
164 let (key, event) = parse_compressed_state_event(entry);
165 let key = inspect_half(
166 services,
167 &projection.statekeys,
168 key,
169 "shortstatekey_statekey",
170 (Shape::StatekeyAliasEntry, Shape::StatekeyOrphanEntry),
171 );
172
173 let event = inspect_half(
174 services,
175 &projection.events,
176 event,
177 "shorteventid_eventid",
178 (Shape::EventAliasEntry, Shape::EventOrphanEntry),
179 );
180
181 try_join(key, event).map_ok(Into::into).await
182}
183
184fn observed(found: Found, observations: Observations) -> Result<Found> {
185 let entries = observations
186 .into_iter()
187 .flatten()
188 .map(|(shape, short, reason)| Finding {
189 shape,
190 subject: Subject::Short(short),
191 reason,
192 });
193
194 Ok(extended(found, entries))
195}
196
197fn extended(mut found: Found, more: impl IntoIterator<Item = Finding>) -> Found {
198 found.extend(more);
199 found
200}
201
202#[tracing::instrument(level = "trace", skip_all)]
203async fn inspect_half(
204 services: &Services,
205 mapping: &Mapping,
206 short: u64,
207 reverse: &str,
208 (alias, orphan): (Shape, Shape),
209) -> Result<Option<Observation>> {
210 if !present(&services.db, reverse, &short.to_be_bytes()).await? {
211 return Ok(Some((orphan, short, Reason::Identity)));
212 }
213
214 Ok(candidate(mapping, short).then_some((alias, short, Reason::HistoricalState)))
215}
216
217#[tracing::instrument(level = "trace", skip_all)]
218pub(crate) async fn survey(services: &Services, identities: &Identities) -> Result<Census> {
219 let (statekeys, events) =
220 try_join(mapping(services, &identities.statekeys), mapping(services, &identities.events))
221 .await?;
222
223 census(services, Projection { statekeys, events }).await
224}
225
226#[tracing::instrument(level = "trace", skip_all)]
227pub(crate) async fn census(services: &Services, projection: Projection) -> Result<Census> {
228 let statekeys = presence(services, "shortstatekey_statekey").await?;
229 let events = presence(services, "shorteventid_eventid").await?;
230 let initial = Census {
231 parents: Parents::new(),
232 seeds: BTreeSet::new(),
233 unknown: false,
234 held: Vec::new(),
235 orphans: Occurrences::new(),
236 complete: true,
237 projection,
238 exposed: BTreeSet::new(),
239 };
240
241 services.db["shortstatehash_statediff"]
242 .raw_stream()
243 .scanned(&services.server)
244 .map_ok(|(key, value)| Scanned {
245 id: short_of(key),
246 parent: value.get(..8).and_then(short_of),
247 diff: decode(value),
248 absences: Absences::new(),
249 })
250 .ready_try_fold(initial, |census, scanned| {
251 tally(census, scan(&statekeys, &events, scanned))
252 })
253 .await
254}
255
256#[tracing::instrument(level = "trace", skip_all)]
257pub(crate) async fn presence(services: &Services, column: &str) -> Result<Vec<u64>> {
258 services.db[column]
260 .raw_keys()
261 .scanned(&services.server)
262 .ready_try_filter_map(|key| Ok(short_of(key)))
263 .try_collect()
264 .await
265}
266
267#[tracing::instrument(level = "trace", skip_all)]
268pub(crate) fn scan(statekeys: &[u64], events: &[u64], scanned: Scanned) -> Scanned {
269 let Some(diff) = scanned.diff.as_ref() else {
270 return scanned;
271 };
272
273 let absences = diff
274 .added
275 .iter()
276 .chain(&diff.removed)
277 .copied()
278 .map(|entry| absence(statekeys, events, entry))
279 .filter(|(_, _, key_missing, event_missing)| *key_missing || *event_missing)
280 .collect();
281
282 Scanned { absences, ..scanned }
283}
284
285#[tracing::instrument(level = "trace", skip_all)]
286fn absence(statekeys: &[u64], events: &[u64], entry: CompressedStateEvent) -> Absence {
287 let (key, event) = parse_compressed_state_event(entry);
288 let key_missing = statekeys.binary_search(&key).is_err();
289 let event_missing = events.binary_search(&event).is_err();
290
291 (key, event, key_missing, event_missing)
292}
293
294fn tally(census: Census, Scanned { id, parent, diff, absences }: Scanned) -> Result<Census> {
295 let Some(diff) = diff else {
296 return Ok(index(incomplete(census), id, parent, true));
297 };
298
299 let exposed = !diff.added.is_disjoint(&diff.removed);
300 let seed = exposed || !absences.is_empty() || infected(&census.projection, &diff);
301 let census = absences
302 .into_iter()
303 .fold(exposure(census, id, exposed), occurrence);
304
305 Ok(index(census, id, parent, seed))
306}
307
308fn infected(projection: &Projection, diff: &Diff) -> bool {
309 diff.added
310 .iter()
311 .chain(&diff.removed)
312 .copied()
313 .map(parse_compressed_state_event)
314 .any(|(key, event)| {
315 candidate(&projection.statekeys, key) || candidate(&projection.events, event)
316 })
317}
318
319fn exposure(mut census: Census, id: Option<u64>, exposed: bool) -> Census {
320 census.exposed.extend(id.filter(|_| exposed));
321 census
322}
323
324fn candidate(mapping: &Mapping, short: u64) -> bool {
325 mapping.aliases.contains_key(&short) || mapping.refused.contains(&short)
326}
327
328fn incomplete(census: Census) -> Census { Census { complete: false, ..census } }
329
330fn occurrence(mut census: Census, (key, event, key_missing, event_missing): Absence) -> Census {
331 if key_missing {
332 census
333 .orphans
334 .entry(key)
335 .or_default()
336 .insert(event);
337
338 census.projection.statekeys.refused.insert(key);
339 }
340
341 if event_missing {
342 census.projection.events.refused.insert(event);
343 }
344
345 census
346}
347
348pub(crate) fn index(
349 mut census: Census,
350 id: Option<u64>,
351 parent: Option<u64>,
352 seed: bool,
353) -> Census {
354 census.unknown |= parent.is_none();
355 let parent = parent.filter(|parent| *parent != 0);
356 let Some(id) = id.filter(|id| *id != 0) else {
357 census.held.extend(parent);
358 return census;
359 };
360
361 census.parents.insert(id, parent);
362
363 if seed {
364 census.seeds.insert(id);
365 }
366
367 census
368}
369
370pub(crate) fn descendants(parents: &Parents, seeds: &BTreeSet<u64>) -> BTreeSet<u64> {
371 if seeds.is_empty() {
372 return BTreeSet::new();
373 }
374
375 parents
376 .keys()
377 .copied()
378 .filter(|id| ancestors(parents, *id).any(|ancestor| seeds.contains(&ancestor)))
379 .collect()
380}
381
382pub(crate) fn ancestors(parents: &Parents, id: u64) -> impl Iterator<Item = u64> + '_ {
383 repeat(()).scan((Some(id), BTreeSet::new()), |(next, visited), ()| {
384 let id = (*next)?;
385
386 if !visited.insert(id) {
387 return None;
388 }
389
390 *next = parents.get(&id).copied().flatten();
391 Some(id)
392 })
393}
394
395pub(crate) fn depth(parents: &Parents, id: u64) -> Option<usize> {
396 let (depth, root) = ancestors(parents, id)
397 .fold((0_usize, None), |(depth, _), id| (depth.saturating_add(1), Some(id)));
398
399 parents
400 .get(&root?)
401 .is_some_and(Option::is_none)
402 .then_some(depth)
403}
404
405pub(crate) fn claim(value: &[u8]) -> Option<u64> { value.get(..8).and_then(short_of) }
406
407#[tracing::instrument(level = "trace", skip_all)]
408pub(crate) async fn materialize(services: &Services, id: u64) -> Result<Materialized> {
409 let Some(original) = row(&services.db, id).await? else {
410 return Ok(None);
411 };
412
413 let bytes = original.as_slice();
414 let chain = unfold((Some(id), BTreeSet::new()), async |(next, visited)| {
415 let next = next?;
416 let loaded = match services.server.check_running() {
417 | Err(error) => Err(error),
418 | Ok(()) if visited.contains(&next) => Ok(None),
419 | Ok(()) if next == id => Ok(decode(bytes)),
420 | Ok(()) => layer(&services.db, next).await,
421 };
422
423 let parent = loaded
424 .as_ref()
425 .ok()
426 .and_then(Option::as_ref)
427 .and_then(|diff| diff.parent);
428
429 Some((loaded, (parent, visit(visited, next))))
430 })
431 .try_collect::<Vec<_>>()
432 .await?;
433
434 let state = chain
435 .into_iter()
436 .rev()
437 .try_fold(CompressedState::new(), |state, diff| {
438 diff.filter(|diff| diff.added.is_disjoint(&diff.removed))
440 .map(|diff| apply(state, diff))
441 });
442
443 Ok(state.map(|state| (original, state)))
444}
445
446#[tracing::instrument(level = "trace", skip_all)]
447pub(crate) async fn layer(db: &Database, id: u64) -> Result<Option<Diff>> {
448 fetch(db, "shortstatehash_statediff", &id.to_be_bytes(), decode)
449 .map_ok(Option::flatten)
450 .await
451}
452
453pub(crate) fn visit(mut visited: BTreeSet<u64>, id: u64) -> BTreeSet<u64> {
454 visited.insert(id);
455 visited
456}
457
458pub(crate) fn apply(state: CompressedState, diff: Diff) -> CompressedState {
459 let Diff { parent, added, removed } = diff;
460
461 let (mut state, smaller) = match state.len() >= added.len() {
463 | true => (state, added),
464 | false => (added, state),
465 };
466
467 state.extend(smaller);
468
469 if parent.is_some() {
470 for entry in &removed {
471 state.remove(entry);
472 }
473 }
474
475 state
476}
477
478pub(crate) fn decode(bytes: &[u8]) -> Option<Diff> {
479 let parent = short_of(bytes.get(..8)?)?;
480 let parent = parent.ne(&0).then_some(parent);
481 let tail = bytes.get(8..)?;
482 let separator = (0..tail.len())
483 .step_by(16)
484 .find(|offset| tail.get(*offset..offset.saturating_add(8)) == Some(&[0; 8]));
485
486 let (added, removed) = match separator {
487 | None => (tail, &[][..]),
488 | Some(offset) => {
489 let removed = tail
490 .get(offset.checked_add(8)?..)
491 .filter(|removed| !removed.is_empty())?;
492
493 (tail.get(..offset)?, removed)
494 },
495 };
496
497 let added = entries(added)?;
498 let removed = entries(removed)?;
499
500 Some(Diff { parent, added, removed })
501}
502
503fn entries(bytes: &[u8]) -> Option<CompressedState> {
504 let (chunks, []): (&[CompressedStateEvent], _) = bytes.as_chunks() else {
505 return None;
506 };
507
508 chunks
509 .iter()
510 .copied()
511 .map(|entry| {
512 let (key, event) = parse_compressed_state_event(entry);
513 let valid = key != 0 && event != 0;
514
515 valid.then_some(entry)
516 })
517 .collect()
518}
519
520#[tracing::instrument(level = "trace", skip_all)]
521pub(crate) async fn mapping(services: &Services, family: &Family) -> Result<Mapping> {
522 let initial = Mapping {
523 aliases: Aliases::new(),
524 refused: BTreeSet::new(),
525 };
526
527 family
528 .candidates
529 .iter()
530 .try_stream()
531 .broad_and_then(async |candidate| {
532 services.server.check_running()?;
533 let winner = match candidate.kind {
534 | Kind::Alias(winner) =>
535 admitted(&services.db, family, candidate)
536 .map_ok(|admitted| admitted.then_some(winner))
537 .await?,
538 | _ => None,
539 };
540
541 Ok((candidate, winner))
542 })
543 .ready_try_fold(initial, |mapping, (candidate, winner)| {
544 Ok(classify(mapping, candidate, winner))
545 })
546 .await
547}
548
549fn classify(mut mapping: Mapping, candidate: &Candidate, winner: Option<u64>) -> Mapping {
550 match winner {
551 | None => {
552 mapping.refused.insert(candidate.short);
553 },
554 | Some(winner) => {
555 mapping
556 .aliases
557 .insert(candidate.short, (winner, candidate.identity.clone()));
558 },
559 }
560
561 mapping
562}
563
564pub(crate) fn project(
565 state: CompressedState,
566 projection: &Projection,
567) -> Option<CompressedState> {
568 state
569 .into_iter()
570 .map(|entry| project_entry(entry, projection))
571 .collect::<Option<CompressedState>>()
572 .filter(unique_keys)
573}
574
575fn project_entry(
576 entry: CompressedStateEvent,
577 projection: &Projection,
578) -> Option<CompressedStateEvent> {
579 let (key, event) = parse_compressed_state_event(entry);
580 let (key, _) = projection.statekeys.resolve(key)?;
581 let (event, _) = projection.events.resolve(event)?;
582
583 Some(compress_state_event(key, event))
584}
585
586#[implement(Mapping)]
587fn resolve(&self, short: u64) -> Option<(u64, Option<&Identity>)> {
588 self.refused.contains(&short).is_false().then(|| {
589 self.aliases
590 .get(&short)
591 .map_or((short, None), |(winner, identity)| (*winner, Some(identity)))
592 })
593}
594
595fn unique_keys(state: &CompressedState) -> bool {
596 state
598 .iter()
599 .map(|entry| parse_compressed_state_event(*entry).0)
600 .tuple_windows()
601 .all(|(left, right)| left != right)
602}
603
604#[tracing::instrument(level = "trace", skip_all)]
605pub(crate) async fn identity(
606 db: &Database,
607 mapping: &Mapping,
608 short: u64,
609 reverse: &str,
610) -> Result<Option<(u64, Identity)>> {
611 let Some((winner, known)) = mapping.resolve(short) else {
612 return Ok(None);
613 };
614
615 match known {
616 | Some(identity) => Ok(Some((winner, identity.clone()))),
617 | None =>
618 lookup(db, reverse, &short.to_be_bytes())
619 .map_ok(|identity| identity.map(|identity| (short, identity)))
620 .await,
621 }
622}
623
624#[tracing::instrument(level = "trace", skip_all)]
625pub(crate) async fn row(db: &Database, id: u64) -> Result<Option<ValBuf>> {
626 fetch(db, "shortstatehash_statediff", &id.to_be_bytes(), ValBuf::from_slice).await
627}
628
629#[tracing::instrument(level = "trace", skip_all)]
630pub(crate) async fn lookup(db: &Database, map: &str, key: &[u8]) -> Result<Option<Identity>> {
631 fetch(db, map, key, Identity::from_slice).await
632}
633
634#[tracing::instrument(level = "trace", skip_all)]
635pub(crate) async fn fetch<T>(
636 db: &Database,
637 map: &str,
638 key: &[u8],
639 convert: impl FnOnce(&[u8]) -> T,
640) -> Result<Option<T>> {
641 db[map]
642 .get(key)
643 .map_ok(|value| convert(&value))
644 .map(NotFound::present)
645 .await
646}
647
648#[tracing::instrument(level = "trace", skip_all)]
649pub(crate) async fn present(db: &Database, map: &str, key: &[u8]) -> Result<bool> {
650 db[map]
651 .exists(key)
652 .map(NotFound::present)
653 .map_ok(|found| found.is_some())
654 .await
655}
656
657pub(crate) fn statekey(kind: &TimelineEventType, state_key: &str) -> Identity {
658 kind.to_cow_str()
659 .as_bytes()
660 .iter()
661 .copied()
662 .chain([SEP])
663 .chain(state_key.as_bytes().iter().copied())
664 .collect()
665}