diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/main.rs | 2 | ||||
| -rw-r--r-- | src/swarm/topology.rs | 62 | ||||
| -rw-r--r-- | src/testrand.rs | 82 | ||||
| -rw-r--r-- | src/transport/sim.rs | 35 |
4 files changed, 149 insertions, 32 deletions
diff --git a/src/main.rs b/src/main.rs index d1e8053..bfc45f0 100644 --- a/src/main.rs +++ b/src/main.rs @@ -26,6 +26,8 @@ mod remake; mod simtest; mod state; mod swarm; +#[cfg(test)] +mod testrand; mod transport; use api::auth::AuthState; diff --git a/src/swarm/topology.rs b/src/swarm/topology.rs index b40b120..0dae7e9 100644 --- a/src/swarm/topology.rs +++ b/src/swarm/topology.rs @@ -417,6 +417,68 @@ mod tests { .collect() } + fn hex(bytes: [u8; 32]) -> String { + bytes.iter().map(|byte| format!("{byte:02x}")).collect() + } + + /// Over random swarms (size, `k`, who is reachable, who is stable): links only + /// between reachable members, never to oneself, symmetric; a full mesh while small, + /// otherwise at least `k` links each and connected; independent of the order members + /// are listed in; and each member's own view (`neighbours`) agrees with the graph. + #[test] + fn random_swarms() { + crate::testrand::for_seeds(300, |rng| { + let n = rng.between(1, 60); + let k = rng.between(2, 14); + let mut all: Vec<String> = (0..n).map(|_| hex(rng.bytes32())).collect(); + let unreachable: BTreeSet<String> = + all.iter().filter(|_| rng.chance(0.3)).cloned().collect(); + let stable: BTreeSet<String> = + all.iter().filter(|_| rng.chance(0.3)).cloned().collect(); + let is_unreachable = |m: &str| unreachable.contains(m); + let is_stable = |m: &str| stable.contains(m); + + let g = super::graph(&all, k, &is_unreachable, &is_stable); + // Owned: `all` is shuffled below. + let live: BTreeSet<String> = all + .iter() + .filter(|m| !unreachable.contains(*m)) + .cloned() + .collect(); + assert_eq!(g.keys().cloned().collect::<BTreeSet<_>>(), live); + for (a, ns) in &g { + assert!(!ns.contains(a), "{a} links to itself"); + for b in ns { + assert!(live.contains(b), "{a} links to unreachable {b}"); + assert!(g[b].contains(a), "{a} -> {b} but not back"); + } + } + if live.len() <= k + 1 { + assert!( + g.values().all(|ns| ns.len() + 1 == live.len()), + "not a full mesh" + ); + } else { + assert!( + g.values().all(|ns| ns.len() >= k), + "a member with fewer than k links" + ); + assert!(connected(&g), "not connected"); + } + + rng.shuffle(&mut all); + assert_eq!(super::graph(&all, k, &is_unreachable, &is_stable), g); + + if let Some(local) = live.iter().nth(rng.below(live.len())) { + let others: Vec<String> = all.iter().filter(|m| *m != local).cloned().collect(); + assert_eq!( + neighbours(&others, local, k, &is_unreachable, &is_stable), + g[local] + ); + } + }); + } + #[test] fn small_swarms_are_a_full_mesh() { let ms = members(13); diff --git a/src/testrand.rs b/src/testrand.rs new file mode 100644 index 0000000..dbb2148 --- /dev/null +++ b/src/testrand.rs @@ -0,0 +1,82 @@ +//! A small, seedable random generator for tests (SplitMix64), and a runner for +//! property tests over many seeds. No dependency; reproducible: a failing case names +//! its seed. + +use std::time::Duration; + +pub(crate) struct Rng(u64); + +impl Rng { + pub(crate) fn new(seed: u64) -> Self { + Self(seed) + } + + pub(crate) fn next_u64(&mut self) -> u64 { + self.0 = self.0.wrapping_add(0x9e37_79b9_7f4a_7c15); + let mut z = self.0; + z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9); + z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb); + z ^ (z >> 31) + } + + /// Uniform in [0, 1). + pub(crate) fn next_f64(&mut self) -> f64 { + (self.next_u64() >> 11) as f64 / (1_u64 << 53) as f64 + } + + pub(crate) fn chance(&mut self, probability: f64) -> bool { + probability > 0.0 && self.next_f64() < probability + } + + /// Uniform in [0, n); 0 if `n` is 0. + pub(crate) fn below(&mut self, n: usize) -> usize { + if n == 0 { + return 0; + } + (self.next_u64() % n as u64) as usize + } + + /// Uniform in [min, max]. + pub(crate) fn between(&mut self, min: usize, max: usize) -> usize { + min + self.below(max - min + 1) + } + + pub(crate) fn pick<'a, T>(&mut self, items: &'a [T]) -> &'a T { + &items[self.below(items.len())] + } + + pub(crate) fn bytes32(&mut self) -> [u8; 32] { + let mut bytes = [0; 32]; + for chunk in bytes.chunks_mut(8) { + chunk.copy_from_slice(&self.next_u64().to_le_bytes()); + } + bytes + } + + pub(crate) fn shuffle<T>(&mut self, items: &mut [T]) { + for i in (1..items.len()).rev() { + items.swap(i, self.below(i + 1)); + } + } + + /// Uniform in the range (`min` if it is empty). + pub(crate) fn duration_in(&mut self, (min, max): (Duration, Duration)) -> Duration { + if max <= min { + return min; + } + min + (max - min).mul_f64(self.next_f64()) + } +} + +/// Runs `check` once per seed in `0..cases`, each with its own generator. A failing case +/// says its seed, to rerun it alone with `Rng::new(seed)`. +pub(crate) fn for_seeds(cases: u64, check: impl Fn(&mut Rng)) { + for seed in 0..cases { + let result = + std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| check(&mut Rng::new(seed)))); + if let Err(panic) = result { + eprintln!("property failed for seed {seed}"); + std::panic::resume_unwind(panic); + } + } +} diff --git a/src/transport/sim.rs b/src/transport/sim.rs index 1556d69..ce5977f 100644 --- a/src/transport/sim.rs +++ b/src/transport/sim.rs @@ -26,6 +26,7 @@ use tracing::{debug, warn}; use super::mycelium::{decode_message, encode_message}; use super::{EncodedMessage, MessageHandler, MessageKind, ParsedMessage, Transport}; +use crate::testrand::Rng; /// How one direction of a link behaves. #[derive(Clone, Debug)] @@ -72,7 +73,7 @@ pub(crate) struct NetCounts { } struct NetInner { - rng: SplitMix64, + rng: Rng, default_link: LinkParams, links: HashMap<(String, String), LinkParams>, down: HashSet<String>, @@ -90,7 +91,7 @@ impl SimNet { pub(crate) fn new(seed: u64) -> Self { Self { inner: Arc::new(Mutex::new(NetInner { - rng: SplitMix64(seed), + rng: Rng::new(seed), default_link: LinkParams::default(), links: HashMap::new(), down: HashSet::new(), @@ -306,36 +307,6 @@ impl Transport for SimTransport { } } -/// A small, seedable generator (SplitMix64): enough for network decisions, and no -/// dependency. -struct SplitMix64(u64); - -impl SplitMix64 { - fn next_u64(&mut self) -> u64 { - self.0 = self.0.wrapping_add(0x9e37_79b9_7f4a_7c15); - let mut z = self.0; - z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9); - z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb); - z ^ (z >> 31) - } - - /// Uniform in [0, 1). - fn next_f64(&mut self) -> f64 { - (self.next_u64() >> 11) as f64 / (1_u64 << 53) as f64 - } - - fn chance(&mut self, probability: f64) -> bool { - probability > 0.0 && self.next_f64() < probability - } - - fn duration_in(&mut self, (min, max): (Duration, Duration)) -> Duration { - if max <= min { - return min; - } - min + (max - min).mul_f64(self.next_f64()) - } -} - #[cfg(test)] mod tests { use super::*; |