Skip to main content

tuwunel_service/migrations/injectivity/seen/state/
orphan.rs

1use std::collections::BTreeSet;
2
3use futures::{FutureExt, TryFutureExt, TryStreamExt};
4use serde_json::from_slice;
5use tuwunel_core::{
6	Err, Result, err,
7	utils::{IterStream, TryReadyExt, result::NotFound, stream::TryBroadbandExt},
8};
9use tuwunel_database::{Database, Txn};
10use tuwunel_matrix::PduEvent;
11
12use crate::{
13	Services,
14	integrity::{
15		ScanExt,
16		short_ids::{
17			Identity, short_of,
18			state::{Aliases, Census, Mapping, claim, identity, lookup, present, statekey},
19		},
20	},
21};
22
23type Alias = (u64, (u64, Identity));
24
25#[tracing::instrument(level = "trace", skip_all)]
26pub(super) async fn recover(services: &Services, census: &Census) -> Result<Aliases> {
27	if !census.complete || census.orphans.is_empty() {
28		return Ok(Aliases::new());
29	}
30
31	let claimed: BTreeSet<u64> = services.db["statekey_shortstatekey"]
32		.raw_stream()
33		.scanned(&services.server)
34		.ready_try_filter_map(|(_, value)| {
35			Ok(claim(value).filter(|short| census.orphans.contains_key(short)))
36		})
37		.try_collect()
38		.await?;
39
40	census
41		.orphans
42		.iter()
43		.filter(|(short, _)| !claimed.contains(*short))
44		.try_stream()
45		.try_filter_map(|(short, events)| recover_one(services, census, *short, events))
46		.try_collect()
47		.await
48}
49
50#[tracing::instrument(level = "trace", skip_all)]
51async fn recover_one(
52	services: &Services,
53	census: &Census,
54	short: u64,
55	events: &BTreeSet<u64>,
56) -> Result<Option<Alias>> {
57	let Some(alias) = recoverable(services, census, short, events).await? else {
58		return Ok(None);
59	};
60
61	reinstate(&services.db, alias).await
62}
63
64/// The reverse row an orphan state key short can reinstate, decided by reads alone.
65///
66/// Every event the orphan's entries name must be an accepted state event of one
67/// state key, whose forward row names a winner that maps back to it. Anything
68/// less leaves the orphan as it is.
69#[tracing::instrument(level = "trace", skip_all)]
70async fn recoverable(
71	services: &Services,
72	census: &Census,
73	short: u64,
74	events: &BTreeSet<u64>,
75) -> Result<Option<Alias>> {
76	services.server.check_running()?;
77	let db = &services.db;
78	let Some(statekey) = unanimous(db, &census.projection.events, events).await? else {
79		return Ok(None);
80	};
81
82	let Some(winner) = lookup(db, "statekey_shortstatekey", &statekey)
83		.await?
84		.as_deref()
85		.and_then(short_of)
86	else {
87		return Ok(None);
88	};
89
90	if identity(db, &census.projection.statekeys, winner, "shortstatekey_statekey")
91		.await?
92		.is_none_or(|(canonical, checked)| canonical != winner || checked != statekey)
93	{
94		return Ok(None);
95	}
96
97	Ok(Some((short, (winner, statekey))))
98}
99
100/// Writes a decided reverse row and reads it back.
101///
102/// A reverse row that appeared since the decision is left alone, and a readback
103/// that disagrees with the write is an error.
104#[tracing::instrument(level = "trace", skip_all)]
105async fn reinstate(db: &Database, alias: Alias) -> Result<Option<Alias>> {
106	let (short, (_, statekey)) = &alias;
107	let key = short.to_be_bytes();
108
109	if present(db, "shortstatekey_statekey", &key).await? {
110		return Ok(None);
111	}
112
113	Txn::insert(&db["shortstatekey_statekey"], [(key, statekey.as_slice())])
114		.try_execute()
115		.map_err(|error| err!("orphan identity publication: {error}"))?;
116
117	if lookup(db, "shortstatekey_statekey", &key)
118		.await?
119		.is_none_or(|published| published.ne(statekey))
120	{
121		return Err!("orphan identity verification failed");
122	}
123
124	Ok(Some(alias))
125}
126
127#[tracing::instrument(level = "trace", skip_all)]
128async fn unanimous(
129	db: &Database,
130	mapping: &Mapping,
131	events: &BTreeSet<u64>,
132) -> Result<Option<Identity>> {
133	let Some(first) = events.first().copied() else {
134		return Ok(None);
135	};
136
137	let Some(statekey) = accepted_occurrence(db, mapping, first).await? else {
138		return Ok(None);
139	};
140
141	// A dissent decides the outcome, so dropping reads still pending is sound.
142	let agreed = events
143		.iter()
144		.copied()
145		.skip(1)
146		.try_stream()
147		.broad_try_all(|event| {
148			accepted_occurrence(db, mapping, event)
149				.map_ok(|other| other.as_ref() == Some(&statekey))
150		})
151		.await?;
152
153	Ok(agreed.then_some(statekey))
154}
155
156#[tracing::instrument(level = "trace", skip_all)]
157async fn accepted_occurrence(
158	db: &Database,
159	mapping: &Mapping,
160	event: u64,
161) -> Result<Option<Identity>> {
162	let Some((_, event_id)) = identity(db, mapping, event, "shorteventid_eventid").await? else {
163		return Ok(None);
164	};
165
166	accepted_key(db, &event_id).await
167}
168
169#[tracing::instrument(level = "trace", skip_all)]
170async fn accepted_key(db: &Database, event_id: &[u8]) -> Result<Option<Identity>> {
171	let Some(pdu_id) = lookup(db, "eventid_pduid", event_id).await? else {
172		return Ok(None);
173	};
174
175	let Some(pdu) = db["pduid_pdu"]
176		.get(&pdu_id)
177		.map(NotFound::present)
178		.await?
179	else {
180		return Ok(None);
181	};
182
183	// A full decode: only a well-formed accepted PDU may vote.
184	let Ok(pdu) = from_slice::<PduEvent>(&pdu) else {
185		return Ok(None);
186	};
187
188	let Some(state_key) = pdu.state_key.as_ref() else {
189		return Ok(None);
190	};
191
192	if pdu.event_id.as_bytes() != event_id {
193		return Ok(None);
194	}
195
196	Ok(Some(statekey(&pdu.kind, state_key)))
197}