Skip to main content

tuwunel_service/integrity/short_ids/
check.rs

1//! The short-id census as a stream of findings.
2//!
3//! The repair's final verification folds this stream into the outcome it
4//! records, so a run reports what verification would record for the database as
5//! it stands. Nothing here writes.
6
7use std::fmt;
8
9use futures::{Stream, StreamExt, TryFutureExt, TryStreamExt, future::ready};
10use tuwunel_core::{Result, implement, utils::IterStream};
11
12use super::{
13	Identity, Reason, Shape,
14	gc::{Collected, inspect as inspect_gc},
15	identity::{Family, Identities, Kind, census as census_identities},
16	rooms::{Rooms, inspect as inspect_rooms},
17	state::{findings as state_findings, survey},
18};
19use crate::{Services, integrity::Report};
20
21/// Residue the short-id census finds, in the terms the repair's outcome records.
22///
23/// The outcome counts a finding once under its shape, or a `Malformed` subject's
24/// number of times, and keeps the first few as samples.
25pub(crate) struct Finding {
26	/// The class of residue, which names the outcome slot it counts in.
27	pub(crate) shape: Shape,
28
29	/// Where the census found it.
30	pub(crate) subject: Subject,
31
32	/// What kept the repair from resolving it.
33	pub(crate) reason: Reason,
34}
35
36/// Where a finding lies.
37///
38/// Most subjects name one row, id or state, and verification samples its bytes.
39/// The rest stand for findings no single row carries: a total, an incomplete
40/// census, or residue a census could not rule out.
41pub(crate) enum Subject {
42	/// An identity row, by the event id or state key it names.
43	Identity(Identity),
44
45	/// A short id a state entry names.
46	Short(u64),
47
48	/// A state, by its short state hash.
49	State(u64),
50
51	/// A short room id.
52	Room(u64),
53
54	/// A family's malformed identity rows, as one total.
55	///
56	/// Each of those rows also comes as its own `Identity` finding, and the
57	/// outcome records both, so only verification takes this one.
58	Malformed(u64),
59
60	/// A state census that could not attribute every row.
61	Incomplete,
62
63	/// A census that could not prove further residue absent.
64	///
65	/// It comes at the end of the stream, where verification joins it with the
66	/// uncertainty the repair captured before its own writes.
67	Uncertain,
68}
69
70/// Streams the short-id residue, one finding per defect.
71///
72/// This is the census verification folds, less each family's malformed row
73/// total, which repeats rows already streamed one by one.
74#[tracing::instrument(level = "trace", skip_all)]
75pub(crate) fn check(services: &Services) -> impl Stream<Item = Result<Finding>> + Send + '_ {
76	scan(services).try_filter(|finding| ready(!matches!(finding.subject, Subject::Malformed(_))))
77}
78
79/// Streams the short-id residue the repair's verification records.
80///
81/// Findings come in the order the outcome records them: identity rows, states,
82/// unreachable states and short room ids, then the censuses that could not prove
83/// further residue absent. Each describes the database as it stands, and none
84/// forecasts a repair: publishing snapshots drops digest roots and parent links,
85/// so a repair can collect unreachable states that a run before it does not
86/// report.
87#[tracing::instrument(level = "trace", skip_all)]
88pub(crate) fn scan(services: &Services) -> impl Stream<Item = Result<Finding>> + Send + '_ {
89	let states = census_identities(services)
90		.and_then(async |identities| {
91			let census = survey(services, &identities).await?;
92			let findings = identity_findings(identities)
93				.try_stream()
94				.chain(state_findings(services, census));
95
96			Ok(findings)
97		})
98		.try_flatten_stream();
99
100	let residues = inspect_gc(services)
101		.and_then(async |collected| {
102			let rooms = inspect_rooms(services).await?;
103			let findings = residue_findings(collected, rooms).try_stream();
104
105			Ok(findings)
106		})
107		.try_flatten_stream();
108
109	states.chain(residues)
110}
111
112impl Report for Finding {
113	#[inline]
114	fn kind(&self) -> &'static str { self.shape.label() }
115}
116
117impl fmt::Display for Finding {
118	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
119		write!(f, "{}: {} ({})", self.kind(), self.subject, self.reason.label())
120	}
121}
122
123impl fmt::Display for Subject {
124	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
125		match self {
126			| Self::Identity(identity) => write!(f, "identity {}", identity.escape_ascii()),
127			| Self::Short(short) => write!(f, "short id {short}"),
128			| Self::State(state) => write!(f, "state {state}"),
129			| Self::Room(room) => write!(f, "short room id {room}"),
130			| Self::Malformed(count) => write!(f, "{count} malformed identity rows"),
131			| Self::Incomplete => write!(f, "a state census that could not attribute every row"),
132			| Self::Uncertain =>
133				write!(f, "an incomplete census leaves further residue unproven"),
134		}
135	}
136}
137
138fn identity_findings(
139	Identities { events, statekeys }: Identities,
140) -> impl Iterator<Item = Finding> + Send {
141	family(events, Shape::EventAlias).chain(family(statekeys, Shape::StatekeyAlias))
142}
143
144fn family(family: Family, alias: Shape) -> impl Iterator<Item = Finding> + Send {
145	let Family { candidates, malformed, .. } = family;
146	let unnamed = malformed.ne(&0).then_some(Finding {
147		shape: alias,
148		subject: Subject::Malformed(malformed),
149		reason: Reason::Identity,
150	});
151
152	candidates
153		.into_iter()
154		.map(move |candidate| Finding {
155			shape: candidate_shape(candidate.kind, alias),
156			subject: Subject::Identity(candidate.identity),
157			reason: Reason::Identity,
158		})
159		.chain(unnamed)
160}
161
162fn candidate_shape(kind: Kind, alias: Shape) -> Shape {
163	match kind {
164		| Kind::Reverse => Shape::DanglingWinner,
165		| Kind::Forward => Shape::PromotableReverse,
166		| Kind::Alias(_) | Kind::Unresolved => alias,
167	}
168}
169
170fn residue_findings(collected: Collected, rooms: Rooms) -> impl Iterator<Item = Finding> + Send {
171	let unreachable = collected
172		.unfinished
173		.into_iter()
174		.map(|id| Finding {
175			shape: Shape::UnreachableState,
176			subject: Subject::State(id),
177			reason: Reason::References,
178		});
179
180	// An unclassified stray counts once as purge residue, even as a live-room alias.
181	let purged = rooms.unfinished.into_iter().map(|id| Finding {
182		shape: Shape::PurgeResidue,
183		subject: Subject::Room(id),
184		reason: Reason::Ownership,
185	});
186
187	let uncertain = [
188		collected
189			.unknown
190			.then_some((Shape::UnreachableState, Reason::References)),
191		rooms
192			.unknown
193			.then_some((Shape::PurgeResidue, Reason::Ownership)),
194	];
195
196	let uncertain = uncertain
197		.into_iter()
198		.flatten()
199		.map(|(shape, reason)| Finding {
200			shape,
201			subject: Subject::Uncertain,
202			reason,
203		});
204
205	unreachable.chain(purged).chain(uncertain)
206}
207
208#[implement(Shape)]
209fn label(self) -> &'static str {
210	match self {
211		| Self::EventAlias => "event-short-id",
212		| Self::StatekeyAlias => "statekey-short-id",
213		| Self::DanglingWinner => "dangling-winner",
214		| Self::PromotableReverse => "promotable-reverse",
215		| Self::EventAliasEntry => "event-alias-entry",
216		| Self::StatekeyAliasEntry => "statekey-alias-entry",
217		| Self::AffectedState => "affected-state",
218		| Self::DiffCollision => "diff-collision",
219		| Self::EventOrphanEntry => "event-orphan-entry",
220		| Self::StatekeyOrphanEntry => "statekey-orphan-entry",
221		| Self::AuthChainCache => "auth-chain-cache",
222		| Self::UnreachableState => "unreachable-state",
223		| Self::PurgeResidue => "purge-residue",
224		| Self::LiveRoomAlias => "live-room-alias",
225		| Self::DeclinedMarker => "declined-marker",
226	}
227}
228
229#[implement(Reason)]
230fn label(self) -> &'static str {
231	match self {
232		| Self::Identity => "identity unproven",
233		| Self::HistoricalState => "history unproven",
234		| Self::References => "references unproven",
235		| Self::Ownership => "ownership unproven",
236	}
237}