happenstance_sync_testkit/sync_model.rs
1//! The model family: seeded peer topologies, driven through push and pull from
2//! one seed, and checked at quiescence against a model of their own.
3//!
4//! # What this adds that the worked examples cannot
5//!
6//! Every rule in [`rules`](crate::rules) is a worked example against one peer.
7//! The clauses this family checks — every peer ends up holding the union
8//! (SY-4, SY-24), holds it once (SY-11), and forwards in arrival order (SY-25) —
9//! are statements about a *set* of peers under a runner, and the interesting
10//! failures are interleavings: a lost ack, a page delivered twice, a page that
11//! lands after a later one, a partition that heals. This family generates
12//! those. Each case is a topology of three to six peers — A—B—C chains
13//! included, where the ends never meet — and up to thirty-two steps of writes,
14//! exchanges, partitions and heals, each exchange carrying a fault. After the
15//! last step every link heals and the harness sweeps until nothing moves; then
16//! each peer's whole log is pulled and judged.
17//!
18//! # How it holds several peers, and SY-8
19//!
20//! The family opens **one fixture per node**, so every node is an isolated
21//! peer, and plays the runner itself: per edge, a resume token each way and at
22//! most one page in flight. Each peer is still driven only through its own
23//! port, one relationship at a time, which is what SY-8 asks of the port. What
24//! SY-8's `Rule:` line says of the whole testkit — every rule takes exactly
25//! one peer handle — is true of [`rules`](crate::rules) and not of this family,
26//! and SY-24's own `Rule:` line already names a three-peer test. The tension is
27//! recorded in `.kb/open-questions/sy-8-rule-line-versus-multi-peer-rules.md`
28//! rather than settled here.
29//!
30//! # Deterministic, and a failure prints its seed
31//!
32//! A master RNG with a fixed seed draws one `u64` per case, and that seed alone
33//! builds the case. So a peer either passes or it does not, the same on every
34//! machine, and a failure names its seed in hex beside the smallest scenario it
35//! shrank to. The case count is `proptest`'s `Config::default()`'s, so
36//! `PROPTEST_CASES` buys more coverage. Before any generated case, three
37//! scenarios pinned by value run first: a seed's meaning moves whenever the
38//! generator does, and these must not.
39//!
40//! # Bounded
41//!
42//! No clock (CF-33). Every loop is counted: steps, sweeps, pulls and shrink
43//! moves. A peer that never settles fails the rule rather than hanging it
44//! (H-13).
45//!
46//! # Not on wasm32
47//!
48//! `proptest` does not build there, so the module, its macros and its
49//! dependency are absent on that target whatever the feature says.
50
51mod oracle;
52mod regressions;
53mod scenario;
54mod simulate;
55
56use alloc::format;
57use alloc::string::String;
58use alloc::vec::Vec;
59
60use proptest::prelude::Strategy;
61use proptest::strategy::ValueTree;
62use proptest::test_runner::{Config, RngAlgorithm, TestRng, TestRunner};
63
64use happenstance_testkit::RuleOutcome;
65
66use crate::{SyncFixture, Violation};
67use oracle::{Check, Failure, judge};
68use regressions::regressions;
69use scenario::{Scenario, any_scenario, seed_bytes};
70use simulate::simulate;
71
72/// How many times the shrinker may move before it reports the smallest
73/// counterexample it has. A count rather than `proptest`'s
74/// `max_shrink_time`, because CF-33 forbids a rule reading a clock.
75const MAX_SHRINK_MOVES: usize = 1024;
76
77/// The model rules. See the [module documentation](crate::sync_model) for
78/// what the family does, and each rule for what it rejects.
79///
80/// Each rule takes `impl AsyncFn() -> F`, as the worked-example rules do, and
81/// calls it once per node of every scenario: each call must be a fresh,
82/// isolated peer.
83pub mod rules {
84 use happenstance_testkit::RuleOutcome;
85
86 use super::{Check, drive};
87 use crate::{SyncFixture, Violation};
88
89 /// SY-24 and SY-4: after every link heals and the peers settle, every
90 /// peer holds every event written anywhere, byte for byte — including
91 /// peers that never met the event's origin.
92 ///
93 /// A missing event is classified by what the model saw: never offered to
94 /// that peer is SY-24 (not forwarded); offered and acknowledged as
95 /// appended is SY-4 (quarantined); offered and acknowledged as already
96 /// held when it never was is SY-1.
97 ///
98 /// # Rejects
99 ///
100 /// A peer that holds guarded events back for review and acknowledges them
101 /// as appended: the quarantine design SY-4 names. `tests/wrong_topologies.rs`
102 /// carries it, and only a generated case can catch it, so it is also the
103 /// end-to-end check that a failure prints its seed. And a peer that dedupes
104 /// by the highest position seen per origin, which drops an event that
105 /// arrives after a later one from the same origin; that is caught by the
106 /// pinned regression `delayed_page_lands_after_a_later_one`. And a peer
107 /// whose caught-up resume token points one group past the end of its log,
108 /// so the next group it takes in is never forwarded along a lane that had
109 /// caught up: SY-24 itself.
110 ///
111 /// # Errors
112 ///
113 /// A [`Violation`] of SY-4, SY-1 or SY-24 for a peer missing an event, and
114 /// of SY-24 for a peer that refuses a push or a pull or never settles.
115 pub async fn transitive_convergence_over_a_partial_mesh<F: SyncFixture>(
116 open: impl AsyncFn() -> F,
117 ) -> Result<RuleOutcome, Violation> {
118 drive(&open, Check::Union).await
119 }
120
121 /// SY-11: re-delivering an event a peer already holds is a no-op. Every
122 /// push is acknowledged with exactly as many appended events as the peer
123 /// had never been offered, and exactly as many skipped as it had; and no
124 /// peer holds any event twice.
125 ///
126 /// # Rejects
127 ///
128 /// A peer that dedupes per batch rather than per event: a page half of
129 /// which it already holds (SF-03) is applied whole, and the half it held is
130 /// appended a second time. The pinned regression `sf03_partial_overlap`
131 /// builds that page. And the position-prefix deduper above, whose
132 /// acknowledgement calls a never-held event skipped.
133 /// `tests/wrong_topologies.rs` carries both.
134 ///
135 /// # Errors
136 ///
137 /// A [`Violation`] of SY-11 for a miscounted acknowledgement or a doubled
138 /// event, or for a peer that refuses a push or a pull or never settles.
139 pub async fn redelivery_of_an_accepted_group_is_a_no_op<F: SyncFixture>(
140 open: impl AsyncFn() -> F,
141 ) -> Result<RuleOutcome, Violation> {
142 drive(&open, Check::ExactlyOnce).await
143 }
144
145 /// SY-25: a peer hands back what it holds in the order it arrived. The
146 /// first occurrence of each event in a peer's log follows the order the
147 /// model saw it first offered.
148 ///
149 /// # Rejects
150 ///
151 /// A peer that re-sorts what it forwards by `EventId`, which looks tidy
152 /// and makes a downstream scalar cursor skip an old event that arrived
153 /// late. `tests/wrong_topologies.rs` carries it.
154 ///
155 /// # Errors
156 ///
157 /// A [`Violation`] of SY-25 for a peer whose log is out of arrival order,
158 /// or that refuses a push or a pull or never settles.
159 pub async fn forwarding_order_is_arrival_order<F: SyncFixture>(
160 open: impl AsyncFn() -> F,
161 ) -> Result<RuleOutcome, Violation> {
162 drive(&open, Check::ArrivalOrder).await
163 }
164}
165
166/// Every regression, then every generated case, judged by `check`.
167async fn drive<F, O>(open: &O, check: Check) -> Result<RuleOutcome, Violation>
168where
169 F: SyncFixture,
170 O: AsyncFn() -> F,
171{
172 for regression in regressions().map_err(|message| Violation::new(check.clause(), message))? {
173 if let Some(failure) = replay(open, ®ression.scenario, check).await {
174 return Err(Violation::new(
175 failure.clause,
176 format!(
177 "regression scenario `{}`: {}",
178 regression.name, failure.message
179 ),
180 ));
181 }
182 }
183
184 // One config, read once, so `PROPTEST_CASES` is consulted once. Each runner
185 // stores its own copy, which is why it is cloned rather than borrowed.
186 let config = Config::default();
187 let cases = config.cases;
188 let mut master = TestRunner::new_with_rng(
189 config.clone(),
190 TestRng::deterministic_rng(RngAlgorithm::ChaCha),
191 );
192 let strategy = any_scenario();
193 for case in 0..cases {
194 // A strategy draw, not a method on the RNG: it builds against both
195 // proptest 1.11 and 1.12, whose RNG traits differ.
196 let seed = proptest::num::u64::ANY
197 .new_tree(&mut master)
198 .map_err(|reason| {
199 Violation::new(
200 check.clause(),
201 format!("the seed generator rejected case {case}: {reason}"),
202 )
203 })?
204 .current();
205 let mut runner = TestRunner::new_with_rng(
206 config.clone(),
207 TestRng::from_seed(RngAlgorithm::ChaCha, &seed_bytes(seed)),
208 );
209 let mut tree = strategy.new_tree(&mut runner).map_err(|reason| {
210 Violation::new(
211 check.clause(),
212 format!("the generator rejected seed {seed:#018x}, and it has no filter: {reason}"),
213 )
214 })?;
215 let Some(failure) = replay(open, &tree.current(), check).await else {
216 continue;
217 };
218 let (smallest, failure) = shrink(open, &mut tree, check, failure).await;
219 return Err(Violation::new(
220 failure.clause,
221 describe(seed, case, cases, &smallest, &failure.message),
222 ));
223 }
224 Ok(RuleOutcome::Ran)
225}
226
227/// Runs one scenario and judges it. `None` if it passed.
228async fn replay<F, O>(open: &O, scenario: &Scenario, check: Check) -> Option<Failure>
229where
230 F: SyncFixture,
231 O: AsyncFn() -> F,
232{
233 match simulate(open, scenario).await {
234 Ok(trace) => judge(check, &trace).err(),
235 Err(message) => Some(Failure::new(check.clause(), message)),
236 }
237}
238
239/// Minimises a failing scenario: `happenstance-testkit`'s model loop, which is
240/// `TestRunner::run_one`'s minus the synchronous closure.
241async fn shrink<F, O, T>(
242 open: &O,
243 tree: &mut T,
244 check: Check,
245 failure: Failure,
246) -> (Scenario, Failure)
247where
248 F: SyncFixture,
249 O: AsyncFn() -> F,
250 T: ValueTree<Value = Scenario>,
251{
252 let mut smallest = (tree.current(), failure);
253 let mut failing = true;
254 for _ in 0..MAX_SHRINK_MOVES {
255 let moved = if failing {
256 tree.simplify()
257 } else {
258 tree.complicate()
259 };
260 if !moved {
261 break;
262 }
263 let scenario = tree.current();
264 match replay(open, &scenario, check).await {
265 Some(failure) => {
266 smallest = (scenario, failure);
267 failing = true;
268 }
269 None => failing = false,
270 }
271 }
272 smallest
273}
274
275/// The failure message: the seed in hex, the case, the smallest scenario, and
276/// what the peers did.
277///
278/// `case` is zero-based and printed from one. `case < cases`, so the
279/// saturation never bites; it is there so the addition cannot overflow.
280fn describe(seed: u64, case: u32, cases: u32, scenario: &Scenario, message: &str) -> String {
281 let case = case.saturating_add(1);
282 let topology = scenario.topology();
283 let steps: Vec<String> = scenario
284 .steps()
285 .iter()
286 .enumerate()
287 .map(|(index, step)| format!(" {index}. {step:?}"))
288 .collect();
289 format!(
290 "seed {seed:#018x} (case {case} of {cases}); smallest failing scenario ({} steps, {} \
291 peers, edges {:?}):\n{}\n{message}",
292 steps.len(),
293 topology.peers(),
294 topology.edges(),
295 steps.join("\n"),
296 )
297}
298
299/// Hands the complete model rule set to `$callback`.
300///
301/// This family's single enumeration (CF-22), beside the rules it names.
302///
303/// # Examples
304///
305/// Compiled only with the `proptest` feature, because the module defining the
306/// macro is.
307///
308/// ```
309/// macro_rules! rule_names {
310/// ($($name:ident),* $(,)?) => { [ $( stringify!($name) ),* ] };
311/// }
312///
313/// let names = happenstance_sync_testkit::for_each_sync_model_rule!(rule_names);
314/// assert!(names.contains(&"forwarding_order_is_arrival_order"));
315/// ```
316#[macro_export]
317macro_rules! for_each_sync_model_rule {
318 ($($callback:tt)+) => {
319 $($callback)+! {
320 // --- Every peer holds the union (SY-24, SY-4) --------------------
321 transitive_convergence_over_a_partial_mesh,
322
323 // --- Redelivery is a no-op (SY-11) ------------------------------
324 redelivery_of_an_accepted_group_is_a_no_op,
325
326 // --- Forwarding order is arrival order (SY-25) ------------------
327 forwarding_order_is_arrival_order,
328 }
329 };
330}
331
332/// Emits one `#[tokio::test]` per model rule.
333///
334/// The caller's crate needs `tokio` with `macros` and `rt` in its
335/// `dev-dependencies`. The default emitter of
336/// [`sync_model_conformance!`](crate::sync_model_conformance).
337#[macro_export]
338macro_rules! emit_sync_model_tokio {
339 ($($name:ident),* $(,)?) => {
340 $(
341 #[tokio::test]
342 async fn $name() -> ::core::result::Result<(), $crate::Violation> {
343 $crate::__private::model_rules::$name(__conformance_fixture)
344 .await?
345 .report(::core::stringify!($name));
346 Ok(())
347 }
348 )*
349 };
350}
351
352/// Emits one plain `#[test]` per model rule, driven by
353/// [`happenstance_testkit::block_on`]: no runtime and no `Send` bound.
354#[macro_export]
355macro_rules! emit_sync_model_blocking {
356 ($($name:ident),* $(,)?) => {
357 $(
358 #[test]
359 fn $name() -> ::core::result::Result<(), $crate::Violation> {
360 $crate::__private::block_on($crate::__private::model_rules::$name(__conformance_fixture))?
361 .report(::core::stringify!($name));
362 Ok(())
363 }
364 )*
365 };
366}
367
368/// Generates the model family for a peer adapter.
369///
370/// Takes the same fixture expression
371/// [`sync_peer_conformance!`](crate::sync_peer_conformance) does. Each rule
372/// calls it once per node, so it must build a fresh, isolated peer every time.
373///
374/// It exists behind this crate's `proptest` feature and not on
375/// `wasm32-unknown-unknown`; gate the invocation accordingly.
376///
377/// # Examples
378///
379/// ```
380/// # macro_rules! ignore { ($($t:tt)*) => {} }
381/// # ignore! {
382/// happenstance_sync_testkit::sync_model_conformance!(
383/// happenstance_sync_testkit::MemorySyncFixture::new()
384/// );
385/// # }
386/// ```
387#[macro_export]
388macro_rules! sync_model_conformance {
389 (mod_name = $mod_name:ident, emit = $emit:path, fixture = $fixture:expr) => {
390 mod $mod_name {
391 async fn __conformance_fixture() -> impl $crate::__private::SyncFixture {
392 $fixture
393 }
394
395 $crate::for_each_sync_model_rule!($emit);
396 }
397 };
398 (mod_name = $mod_name:ident, fixture = $fixture:expr) => {
399 $crate::sync_model_conformance!(
400 mod_name = $mod_name,
401 emit = $crate::emit_sync_model_tokio,
402 fixture = $fixture
403 );
404 };
405 ($fixture:expr) => {
406 $crate::sync_model_conformance!(
407 mod_name = sync_model_conformance,
408 emit = $crate::emit_sync_model_tokio,
409 fixture = $fixture
410 );
411 };
412}
413
414#[cfg(test)]
415mod tests {
416 use alloc::vec::Vec;
417
418 use super::describe;
419 use super::regressions::regressions;
420
421 /// Every `pub async fn` in this file's `rules` module.
422 fn declared_rules() -> Vec<&'static str> {
423 const SOURCE: &str = include_str!("sync_model.rs");
424 const PREFIX: &str = " pub async fn ";
425 SOURCE
426 .lines()
427 .filter_map(|line| line.strip_prefix(PREFIX))
428 .filter_map(|rest| {
429 rest.split(|c: char| !c.is_alphanumeric() && c != '_')
430 .next()
431 })
432 .collect()
433 }
434
435 /// No rule exists without appearing in the enumeration, and none is
436 /// enumerated without existing.
437 #[test]
438 fn no_orphan_sync_model_rules() {
439 let registered = crate::for_each_sync_model_rule!(crate::__sync_rule_names);
440 let mut declared = declared_rules();
441 assert!(!declared.is_empty(), "the source scan matched no rule");
442 let mut listed = registered.to_vec();
443 declared.sort_unstable();
444 listed.sort_unstable();
445 assert_eq!(declared, listed, "declared against enumerated");
446 }
447
448 #[test]
449 fn describe_names_the_seed_in_hex() {
450 let all = regressions().expect("the regressions are valid");
451 let scenario = &all.first().expect("there is a regression").scenario;
452 let text = describe(0xdead_beef, 7, 256, scenario, "what the peers did");
453 assert!(
454 text.starts_with("seed 0x00000000deadbeef (case 8 of 256)"),
455 "{text}"
456 );
457 assert!(text.contains("3 peers"), "{text}");
458 assert!(text.ends_with("what the peers did"), "{text}");
459 }
460
461 /// The case is counted from one, as "of N" reads, and the last one a
462 /// `u32` can name does not overflow.
463 #[test]
464 fn describe_counts_cases_from_one() {
465 let all = regressions().expect("the regressions are valid");
466 let scenario = &all.first().expect("there is a regression").scenario;
467 let first = describe(1, 0, 256, scenario, "");
468 assert!(first.contains("(case 1 of 256)"), "{first}");
469 let last = describe(1, u32::MAX, u32::MAX, scenario, "");
470 assert!(
471 last.contains(&format!("(case {0} of {0})", u32::MAX)),
472 "{last}"
473 );
474 }
475}