Skip to main content

tuwunel_service/integrity/short_ids/
gc.rs

1use std::collections::BTreeSet;
2
3use futures::TryStreamExt;
4use tuwunel_core::{Result, utils::IterStream};
5
6use super::{
7	short_of,
8	state::{Parents, ancestors, decode, depth},
9	sweep,
10};
11use crate::Services;
12
13pub(crate) struct Collected {
14	pub(crate) deleted: u64,
15	pub(crate) unfinished: BTreeSet<u64>,
16	pub(crate) unknown: bool,
17}
18
19#[derive(Default)]
20pub(crate) struct Graph {
21	pub(crate) parents: Parents,
22	held: BTreeSet<u64>,
23	pub(crate) unknown: bool,
24	malformed: bool,
25}
26
27pub(crate) const ROOTS: [&str; 4] = [
28	"roomid_shortstatehash",
29	"shorteventid_shortstatehash",
30	"eventid_resolvedstate",
31	"statehash_shortstatehash",
32];
33
34#[tracing::instrument(level = "debug", skip_all)]
35pub(crate) async fn inspect(services: &Services) -> Result<Collected> {
36	Ok(pending(&census(services).await?))
37}
38
39#[tracing::instrument(level = "debug", skip_all)]
40pub(crate) async fn census(services: &Services) -> Result<Graph> {
41	let graph = sweep(services, "shortstatehash_statediff", Graph::default(), index).await?;
42
43	ROOTS
44		.try_stream()
45		.try_fold(graph, async |graph, column| {
46			sweep(services, column, graph, |graph, _, value| root(graph, value)).await
47		})
48		.await
49}
50
51fn index(graph: Graph, key: &[u8], value: &[u8]) -> Graph {
52	let id = short_of(key).filter(|id| *id != 0);
53	let parent = value.get(..8).and_then(short_of);
54	let malformed = id.is_none() || decode(value).is_none();
55
56	record(graph, id, parent, malformed)
57}
58
59fn record(mut graph: Graph, id: Option<u64>, parent: Option<u64>, malformed: bool) -> Graph {
60	graph.unknown |= parent.is_none();
61	let parent = parent.filter(|id| *id != 0);
62
63	if let Some(id) = id {
64		graph.parents.insert(id, parent);
65	}
66
67	if malformed {
68		graph.malformed = true;
69		graph.held.extend(id.into_iter().chain(parent));
70	}
71
72	graph
73}
74
75fn root(mut graph: Graph, value: &[u8]) -> Graph {
76	graph.malformed |= value.len() != 8;
77
78	match value.get(..8).and_then(short_of) {
79		| None | Some(0) => graph.unknown = true,
80		| Some(id) => {
81			graph.held.insert(id);
82		},
83	}
84
85	graph
86}
87
88pub(crate) fn pending(graph: &Graph) -> Collected {
89	let broken: Vec<_> = graph
90		.parents
91		.keys()
92		.copied()
93		.filter(|id| depth(&graph.parents, *id).is_none())
94		.collect();
95
96	let retained = retained(graph, &broken);
97	let unfinished = graph
98		.parents
99		.keys()
100		.copied()
101		.filter(|id| !retained.contains(id))
102		.collect();
103
104	Collected {
105		deleted: 0,
106		unfinished,
107		unknown: graph.unknown || graph.malformed || !broken.is_empty(),
108	}
109}
110
111fn retained(graph: &Graph, broken: &[u64]) -> BTreeSet<u64> {
112	graph
113		.held
114		.iter()
115		.chain(broken)
116		.flat_map(|id| ancestors(&graph.parents, *id))
117		.collect()
118}