use integer_sqrt::IntegerSquareRoot;
use proptest::arbitrary::any;
use proptest::prelude::Rng;
use proptest::strategy::{Strategy, ValueTree};
use proptest::test_runner::{Reason, TestRunner};
use rand::{self, SeedableRng};
pub type TestRng = rand_xorshift::XorShiftRng;
pub type TestRngSeed = [u8; 16];
pub fn gen_rng() -> impl Strategy<Value = TestRng> {
gen_seed().prop_map(TestRng::from_seed)
}
pub fn gen_seed() -> impl Strategy<Value = TestRngSeed> {
any::<TestRngSeed>().no_shrink()
}
#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
pub struct NetworkDimension {
size: u16,
faulty: u16,
}
impl NetworkDimension {
#[inline]
pub fn new(size: u16, faulty: u16) -> Self {
let dim = NetworkDimension { size, faulty };
assert!(
dim.is_bft(),
"Tried to create network dimension that violates BFT-property."
);
dim
}
#[inline]
pub fn faulty(self) -> usize {
self.faulty.into()
}
#[inline]
pub fn size(self) -> usize {
self.size.into()
}
#[inline]
fn is_bft(self) -> bool {
self.faulty * 3 < self.size
}
#[inline]
pub fn range(min_size: u16, max_size: u16) -> NetworkDimensionStrategy {
NetworkDimensionStrategy { min_size, max_size }
}
#[inline]
pub fn succ(self) -> NetworkDimension {
let mut n = self.size;
let mut f = self.faulty + 1;
if 3 * f >= n {
f = 0;
n += 1;
}
NetworkDimension::new(n, f)
}
}
#[derive(Copy, Clone, Debug)]
pub struct NetworkDimensionTree {
high: u32,
current: u32,
low: u32,
}
impl NetworkDimensionTree {
pub fn gen<R: Rng>(mut rng: R, min_size: u16, max_size: u16) -> Self {
assert!(min_size > 0, "minimum network size is 1");
let total = rng.gen_range(min_size, max_size + 1);
let max_faulty = (total - 1) / 3;
let faulty = rng.gen_range(0, max_faulty + 1);
let high = NetworkDimension::new(total, faulty);
NetworkDimensionTree {
high: high.into(),
current: high.into(),
low: u32::from(min_size),
}
}
}
impl ValueTree for NetworkDimensionTree {
type Value = NetworkDimension;
fn current(&self) -> Self::Value {
self.current.into()
}
fn simplify(&mut self) -> bool {
let prev = *self;
self.high = self.current;
self.current = (self.low + self.high) / 2;
(prev.high != self.high || prev.current != self.current)
}
fn complicate(&mut self) -> bool {
let prev = *self;
if self.high == self.current {
return false;
}
self.low = self.current + 1;
self.current = (self.low + self.high) / 2;
(prev.current != self.current || prev.low != self.low)
}
}
impl From<NetworkDimension> for u32 {
fn from(dim: NetworkDimension) -> u32 {
let b = (u32::from(dim.size) - 1) / 3;
let start = 3 * b * (b + 1) / 2;
let offset = (u32::from(dim.size) - 3 * b - 1) * (b + 1) + u32::from(dim.faulty);
start + offset
}
}
impl From<u32> for NetworkDimension {
fn from(n: u32) -> NetworkDimension {
let b = max_sum(n / 3);
let start = 3 * b * (b + 1) / 2;
let offset = n - start;
let faulty = offset % (b + 1);
let size = 3 * b + 1 + offset / (b + 1);
NetworkDimension::new(size as u16, faulty as u16)
}
}
pub fn max_sum(n: u32) -> u32 {
((1 + 8 * n).integer_sqrt() - 1) / 2
}
#[derive(Debug)]
pub struct NetworkDimensionStrategy {
pub min_size: u16,
pub max_size: u16,
}
impl Strategy for NetworkDimensionStrategy {
type Value = NetworkDimension;
type Tree = NetworkDimensionTree;
fn new_tree(&self, runner: &mut TestRunner) -> Result<Self::Tree, Reason> {
Ok(NetworkDimensionTree::gen(
runner.rng(),
self.min_size,
self.max_size,
))
}
}