tuwunel_service/rooms/state_res/resolve/
auth_difference.rs

1use std::{borrow::Borrow, collections::HashMap, hash::Hash};
2
3use futures::{FutureExt, Stream};
4use ruma::EventId;
5use tuwunel_core::{
6	matrix::event_id::RandomState,
7	utils::stream::{IterStream, ReadyExt},
8};
9
10use super::AuthSet;
11
12struct Counts<Id> {
13	by_id: HashMap<Id, usize, RandomState>,
14	total: usize,
15}
16
17impl<Id> Default for Counts<Id> {
18	fn default() -> Self { Self { by_id: HashMap::default(), total: 0 } }
19}
20
21impl<Id: Eq + Hash> Counts<Id> {
22	fn merge(mut self, set: AuthSet<Id>) -> Self {
23		self.total = self.total.saturating_add(1);
24		for id in set {
25			let count = self.by_id.entry(id).or_default();
26
27			*count = count.saturating_add(1);
28		}
29
30		self
31	}
32}
33
34/// Get the auth difference for the given auth chains.
35///
36/// Definition in the specification:
37///
38/// The auth difference is calculated by first calculating the full auth chain
39/// for each state _Si_, that is the union of the auth chains for each event in
40/// _Si_, and then taking every event that doesn’t appear in every auth chain.
41/// If _Ci_ is the full auth chain of _Si_, then the auth difference is ∪_Ci_ −
42/// ∩_Ci_.
43///
44/// ## Arguments
45///
46/// * `auth_sets` - The list of full recursive sets of `auth_events`. Inputs
47///   must not contain duplicates.
48///
49/// ## Returns
50///
51/// Outputs the event IDs that are not present in all the auth chains, in no
52/// particular order.
53#[tracing::instrument(level = "debug", skip_all)]
54pub(super) fn auth_difference<'a, AuthSets, Id>(auth_sets: AuthSets) -> impl Stream<Item = Id>
55where
56	AuthSets: Stream<Item = AuthSet<Id>>,
57	Id: Borrow<EventId> + Clone + Eq + Hash + Send + 'a,
58{
59	auth_sets
60		.ready_fold_default(Counts::<Id>::merge)
61		.map(|Counts { by_id, total }: Counts<Id>| {
62			by_id
63				.into_iter()
64				.filter_map(move |(id, count)| (count < total).then_some(id))
65				.stream()
66		})
67		.flatten_stream()
68}
tuwunel_service/rooms/state_res/resolve/auth_difference.rs

tuwunel_service/rooms/state_res/resolve/
auth_difference.rs
