1use std::{
2 collections::BTreeMap,
3 hash::{BuildHasher, RandomState},
4 str::from_utf8,
5 sync::Arc,
6};
7
8use futures::{FutureExt, StreamExt, TryStreamExt, future::lazy};
9use ruma::EventId;
10use tuwunel_core::{
11 Result, err,
12 utils::{TryReadyExt, result::NotFound, stream::TryWidebandExt},
13};
14use tuwunel_database::{Database, Map, SEP};
15
16use super::{Identity, short_of};
17use crate::{Services, integrity::ScanExt};
18
19pub(crate) struct Identities {
20 pub(crate) events: Family,
21 pub(crate) statekeys: Family,
22}
23
24pub(crate) struct Family {
25 pub(crate) candidates: Vec<Candidate>,
26 pub(crate) malformed: u64,
27 pub(crate) forward: &'static str,
28 pub(crate) reverse: &'static str,
29
30 claims: BTreeMap<u64, u64>,
32
33 reverse_claims: BTreeMap<Identity, u64>,
35}
36
37pub(crate) struct Candidate {
38 pub(crate) short: u64,
39 pub(crate) identity: Identity,
40 pub(crate) kind: Kind,
41}
42
43#[derive(Clone, Copy)]
49pub(crate) enum Kind {
50 Reverse,
52
53 Forward,
55
56 Alias(u64),
59
60 Unresolved,
62}
63
64#[derive(Clone, Copy)]
69struct Columns {
70 forward: &'static str,
71 reverse: &'static str,
72}
73
74#[derive(Default, Eq, PartialEq)]
79struct Tally {
80 rows: u64,
81 malformed: u64,
82 digest: u64,
83}
84
85const EVENTS: Columns = Columns {
86 forward: "eventid_shorteventid",
87 reverse: "shorteventid_eventid",
88};
89
90const STATEKEYS: Columns = Columns {
91 forward: "statekey_shortstatekey",
92 reverse: "shortstatekey_statekey",
93};
94
95#[tracing::instrument(level = "debug", skip_all)]
96pub(crate) async fn census(services: &Services) -> Result<Identities> {
97 let events = family(services, EVENTS).await?;
98 let statekeys = family(services, STATEKEYS).await?;
99
100 Ok(Identities { events, statekeys })
101}
102
103#[tracing::instrument(level = "debug", skip_all)]
104async fn family(services: &Services, Columns { forward, reverse }: Columns) -> Result<Family> {
105 let db = &services.db;
106 let dangling = db[forward]
107 .raw_stream()
108 .scanned(&services.server)
109 .map_ok(|(identity, short)| decode(short, identity))
110 .wide_and_then(async |(short, identity)| {
111 let kind = match malformed(forward, short, &identity) {
112 | true => Some(Kind::Unresolved),
113 | false => reverse_kind(&db[reverse], short, &identity).await?,
114 };
115
116 Ok(kind.map(|kind| Candidate { short, identity, kind }))
117 });
118
119 let unpointed = lazy(|_| db[reverse].raw_stream())
121 .flatten_stream()
122 .scanned(&services.server)
123 .map_ok(|(short, identity)| decode(short, identity))
124 .wide_and_then(async |(short, identity)| {
125 let kind = match malformed(forward, short, &identity) {
126 | true => Some(Kind::Unresolved),
127 | false => forward_kind(&db[forward], short, &identity).await?,
128 };
129
130 Ok(kind.map(|kind| Candidate { short, identity, kind }))
131 });
132
133 let candidates: Vec<_> = dangling
134 .chain(unpointed)
135 .ready_try_filter_map(Ok)
136 .try_collect()
137 .await?;
138
139 let claims: BTreeMap<u64, u64> = candidates
140 .iter()
141 .flat_map(|candidate| {
142 let winner = match candidate.kind {
143 | Kind::Alias(winner) => Some(winner),
144 | _ => None,
145 };
146
147 [Some(candidate.short), winner]
148 .into_iter()
149 .flatten()
150 .map(|short| (short, 0_u64))
151 })
152 .collect();
153
154 let claims = count_claims(services, forward, claims).await?;
155
156 let reverse_claims: BTreeMap<Identity, u64> = candidates
157 .iter()
158 .filter(|candidate| matches!(candidate.kind, Kind::Forward))
159 .map(|candidate| (candidate.identity.clone(), 0_u64))
160 .collect();
161
162 let reverse_claims = count_reverse_claims(services, reverse, reverse_claims).await?;
163
164 let malformed_rows = candidates
165 .iter()
166 .filter(|candidate| malformed(forward, candidate.short, &candidate.identity))
167 .count()
168 .try_into()
169 .map_err(|_| err!("candidate count exceeds integer width"))?;
170
171 Ok(Family {
172 candidates,
173 malformed: malformed_rows,
174 forward,
175 reverse,
176 claims,
177 reverse_claims,
178 })
179}
180
181fn decode(short: &[u8], identity: &[u8]) -> (u64, Identity) {
182 (short_of(short).unwrap_or_default(), Identity::from_slice(identity))
183}
184
185fn malformed(forward: &str, short: u64, identity: &[u8]) -> bool {
186 short == 0 || !valid(identity, forward == EVENTS.forward)
187}
188
189fn valid(identity: &[u8], event: bool) -> bool {
190 if event {
191 return from_utf8(identity).is_ok_and(|event_id| <&EventId>::try_from(event_id).is_ok());
192 }
193
194 let Some(separator) = identity.iter().position(|byte| *byte == SEP) else {
195 return false;
196 };
197
198 let (event_type, key) = identity.split_at(separator);
199
200 from_utf8(event_type).is_ok() && from_utf8(&key[1..]).is_ok()
202}
203
204#[tracing::instrument(level = "trace", skip_all)]
205async fn reverse_kind(map: &Arc<Map>, short: u64, identity: &[u8]) -> Result<Option<Kind>> {
206 map.get(&short.to_be_bytes())
207 .map(NotFound::present)
208 .await
209 .map(|value| match value.as_deref() {
210 | Some(stored) if stored == identity => None,
211 | Some(_) => Some(Kind::Unresolved),
212 | None => Some(Kind::Reverse),
213 })
214}
215
216#[tracing::instrument(level = "trace", skip_all)]
217async fn forward_kind(map: &Arc<Map>, short: u64, identity: &[u8]) -> Result<Option<Kind>> {
218 map.get(identity)
219 .map(NotFound::present)
220 .await
221 .map(|value| match value.as_deref().map(short_of) {
222 | None => Some(Kind::Forward),
223 | Some(Some(winner)) if winner == short => None,
224 | Some(Some(winner)) => Some(Kind::Alias(winner)),
225 | Some(None) => Some(Kind::Unresolved),
226 })
227}
228
229#[tracing::instrument(level = "debug", skip_all)]
230async fn count_claims(
231 services: &Services,
232 forward: &str,
233 claims: BTreeMap<u64, u64>,
234) -> Result<BTreeMap<u64, u64>> {
235 if claims.is_empty() {
237 return Ok(claims);
238 }
239
240 services.db[forward]
241 .raw_stream()
242 .scanned(&services.server)
243 .ready_try_fold(claims, |mut claims: BTreeMap<u64, u64>, (_, value)| {
244 if let Some(count) = value
246 .get(..8)
247 .and_then(short_of)
248 .and_then(|short| claims.get_mut(&short))
249 {
250 *count = count.saturating_add(1);
251 }
252
253 Ok(claims)
254 })
255 .await
256}
257
258#[tracing::instrument(level = "debug", skip_all)]
259async fn count_reverse_claims(
260 services: &Services,
261 reverse: &str,
262 claims: BTreeMap<Identity, u64>,
263) -> Result<BTreeMap<Identity, u64>> {
264 if claims.is_empty() {
265 return Ok(claims);
266 }
267
268 services.db[reverse]
269 .raw_stream()
270 .scanned(&services.server)
271 .ready_try_fold(claims, |mut claims: BTreeMap<Identity, u64>, (_, identity)| {
272 if let Some(count) = claims.get_mut(identity) {
273 *count = count.saturating_add(1);
274 }
275
276 Ok(claims)
277 })
278 .await
279}
280
281#[tracing::instrument(level = "trace", skip_all)]
282pub(crate) async fn admitted(
283 db: &Database,
284 family: &Family,
285 candidate: &Candidate,
286) -> Result<bool> {
287 let Candidate { short, identity, kind } = candidate;
288
289 if malformed(family.forward, *short, identity) {
290 return Ok(false);
291 }
292
293 let claims = |short| {
294 family
295 .claims
296 .get(&short)
297 .copied()
298 .unwrap_or_default()
299 };
300
301 let (forward, reverse) = (&db[family.forward], &db[family.reverse]);
302 let accepted = match *kind {
303 | Kind::Unresolved => false,
304 | Kind::Reverse =>
305 claims(*short) == 1
306 && points_to(forward, identity, *short).await?
307 && absent(reverse, &short.to_be_bytes()).await?,
308 | Kind::Forward =>
309 claims(*short) == 0
310 && family.reverse_claims.get(identity) == Some(&1)
311 && names(reverse, *short, identity).await?
312 && absent(forward, identity).await?,
313 | Kind::Alias(winner) =>
314 winner != 0
315 && winner != *short
316 && claims(*short) == 0
317 && claims(winner) == 1
318 && points_to(forward, identity, winner).await?
319 && names(reverse, *short, identity).await?
320 && names(reverse, winner, identity).await?,
321 };
322
323 Ok(accepted)
324}
325
326#[tracing::instrument(level = "trace", skip_all)]
327async fn points_to(map: &Arc<Map>, identity: &[u8], short: u64) -> Result<bool> {
328 map.get(identity)
329 .map(NotFound::present)
330 .await
331 .map(|value| value.as_deref().and_then(short_of) == Some(short))
332}
333
334#[tracing::instrument(level = "trace", skip_all)]
335async fn absent(map: &Arc<Map>, key: &[u8]) -> Result<bool> {
336 map.get(key)
337 .map(NotFound::present)
338 .await
339 .map(|value| value.is_none())
340}
341
342#[tracing::instrument(level = "trace", skip_all)]
343async fn names(map: &Arc<Map>, short: u64, identity: &[u8]) -> Result<bool> {
344 map.get(&short.to_be_bytes())
345 .map(NotFound::present)
346 .await
347 .map(|value| value.as_deref() == Some(identity))
348}
349
350#[tracing::instrument(level = "debug", skip_all)]
357pub(crate) async fn consistent(services: &Services) -> Result<bool> {
358 let hasher = RandomState::new();
359
360 Ok(paired(services, &hasher, EVENTS).await? && paired(services, &hasher, STATEKEYS).await?)
361}
362
363#[tracing::instrument(level = "debug", skip_all)]
364async fn paired(services: &Services, hasher: &RandomState, columns: Columns) -> Result<bool> {
365 let forward = tally(services, hasher, columns, columns.forward).await?;
366 let agree = forward.malformed == 0
367 && tally(services, hasher, columns, columns.reverse).await? == forward;
368
369 Ok(agree)
370}
371
372#[tracing::instrument(
373 level = "debug",
374 skip_all,
375 fields(
376 %column,
377 ),
378)]
379async fn tally(
380 services: &Services,
381 hasher: &RandomState,
382 columns: Columns,
383 column: &str,
384) -> Result<Tally> {
385 let forward = column == columns.forward;
386
387 services.db[column]
388 .raw_stream()
389 .scanned(&services.server)
390 .ready_try_fold(Tally::default(), |tally, (key, value)| {
391 let (short, identity) = match forward {
392 | true => (value, key),
393 | false => (key, value),
394 };
395
396 let short = short_of(short).unwrap_or_default();
397 let invalid = forward && malformed(columns.forward, short, identity);
398
399 Ok(tally.add(hasher, short, identity, invalid))
400 })
401 .await
402}
403
404impl Tally {
405 fn add(self, hasher: &RandomState, short: u64, identity: &[u8], invalid: bool) -> Self {
406 let digest = hasher.hash_one((short, identity));
407
408 Self {
409 rows: self.rows.saturating_add(1),
410 malformed: self.malformed.saturating_add(invalid.into()),
411 digest: self.digest.wrapping_add(digest),
412 }
413 }
414}