Skip to main content

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, &regression.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}