From 9835e2ae736235810b4ea1c162ca5e65c547e770 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 18 May 2024 04:49:50 +0200 Subject: Merging upstream version 1.71.1+dfsg1. Signed-off-by: Daniel Baumann --- vendor/proptest/src/num.rs | 1388 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1388 insertions(+) create mode 100644 vendor/proptest/src/num.rs (limited to 'vendor/proptest/src/num.rs') diff --git a/vendor/proptest/src/num.rs b/vendor/proptest/src/num.rs new file mode 100644 index 000000000..75431c7b6 --- /dev/null +++ b/vendor/proptest/src/num.rs @@ -0,0 +1,1388 @@ +//- +// Copyright 2017, 2018 Jason Lingle +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Strategies to generate numeric values (as opposed to integers used as bit +//! fields). +//! +//! All strategies in this module shrink by binary searching towards 0. + +mod float_samplers; + +use crate::test_runner::TestRunner; +use rand::distributions::uniform::{SampleUniform, Uniform}; +use rand::distributions::{Distribution, Standard}; + +pub(crate) fn sample_uniform( + run: &mut TestRunner, + start: X, + end: X, +) -> X { + Uniform::new(start, end).sample(run.rng()) +} + +pub(crate) fn sample_uniform_incl( + run: &mut TestRunner, + start: X, + end: X, +) -> X { + Uniform::new_inclusive(start, end).sample(run.rng()) +} + +macro_rules! int_any { + ($typ: ident) => { + /// Type of the `ANY` constant. + #[derive(Clone, Copy, Debug)] + #[must_use = "strategies do nothing unless used"] + pub struct Any(()); + /// Generates integers with completely arbitrary values, uniformly + /// distributed over the whole range. + pub const ANY: Any = Any(()); + + impl Strategy for Any { + type Tree = BinarySearch; + type Value = $typ; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree { + Ok(BinarySearch::new(runner.rng().gen())) + } + } + }; +} + +macro_rules! numeric_api { + ($typ:ident, $epsilon:expr) => { + numeric_api!($typ, $typ, $epsilon); + }; + ($typ:ident, $sample_typ:ty, $epsilon:expr) => { + impl Strategy for ::core::ops::Range<$typ> { + type Tree = BinarySearch; + type Value = $typ; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree { + Ok(BinarySearch::new_clamped( + self.start, + $crate::num::sample_uniform::<$sample_typ>( + runner, + self.start.into(), + self.end.into(), + ) + .into(), + self.end - $epsilon, + )) + } + } + + impl Strategy for ::core::ops::RangeInclusive<$typ> { + type Tree = BinarySearch; + type Value = $typ; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree { + Ok(BinarySearch::new_clamped( + *self.start(), + $crate::num::sample_uniform_incl::<$sample_typ>( + runner, + (*self.start()).into(), + (*self.end()).into(), + ) + .into(), + *self.end(), + )) + } + } + + impl Strategy for ::core::ops::RangeFrom<$typ> { + type Tree = BinarySearch; + type Value = $typ; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree { + Ok(BinarySearch::new_clamped( + self.start, + $crate::num::sample_uniform_incl::<$sample_typ>( + runner, + self.start.into(), + ::core::$typ::MAX.into(), + ) + .into(), + ::core::$typ::MAX, + )) + } + } + + impl Strategy for ::core::ops::RangeTo<$typ> { + type Tree = BinarySearch; + type Value = $typ; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree { + Ok(BinarySearch::new_clamped( + ::core::$typ::MIN, + $crate::num::sample_uniform::<$sample_typ>( + runner, + ::core::$typ::MIN.into(), + self.end.into(), + ) + .into(), + self.end, + )) + } + } + + impl Strategy for ::core::ops::RangeToInclusive<$typ> { + type Tree = BinarySearch; + type Value = $typ; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree { + Ok(BinarySearch::new_clamped( + ::core::$typ::MIN, + $crate::num::sample_uniform_incl::<$sample_typ>( + runner, + ::core::$typ::MIN.into(), + self.end.into(), + ) + .into(), + self.end, + )) + } + } + }; +} + +macro_rules! signed_integer_bin_search { + ($typ:ident) => { + #[allow(missing_docs)] + pub mod $typ { + use rand::Rng; + + use crate::strategy::*; + use crate::test_runner::TestRunner; + + int_any!($typ); + + /// Shrinks an integer towards 0, using binary search to find + /// boundary points. + #[derive(Clone, Copy, Debug)] + pub struct BinarySearch { + lo: $typ, + curr: $typ, + hi: $typ, + } + impl BinarySearch { + /// Creates a new binary searcher starting at the given value. + pub fn new(start: $typ) -> Self { + BinarySearch { + lo: 0, + curr: start, + hi: start, + } + } + + /// Creates a new binary searcher which will not produce values + /// on the other side of `lo` or `hi` from `start`. `lo` is + /// inclusive, `hi` is exclusive. + fn new_clamped(lo: $typ, start: $typ, hi: $typ) -> Self { + use core::cmp::{max, min}; + + BinarySearch { + lo: if start < 0 { + min(0, hi - 1) + } else { + max(0, lo) + }, + hi: start, + curr: start, + } + } + + fn reposition(&mut self) -> bool { + // Won't ever overflow since lo starts at 0 and advances + // towards hi. + let interval = self.hi - self.lo; + let new_mid = self.lo + interval / 2; + + if new_mid == self.curr { + false + } else { + self.curr = new_mid; + true + } + } + + fn magnitude_greater(lhs: $typ, rhs: $typ) -> bool { + if 0 == lhs { + false + } else if lhs < 0 { + lhs < rhs + } else { + lhs > rhs + } + } + } + impl ValueTree for BinarySearch { + type Value = $typ; + + fn current(&self) -> $typ { + self.curr + } + + fn simplify(&mut self) -> bool { + if !BinarySearch::magnitude_greater(self.hi, self.lo) { + return false; + } + + self.hi = self.curr; + self.reposition() + } + + fn complicate(&mut self) -> bool { + if !BinarySearch::magnitude_greater(self.hi, self.lo) { + return false; + } + + self.lo = self.curr + if self.hi < 0 { -1 } else { 1 }; + + self.reposition() + } + } + + numeric_api!($typ, 1); + } + }; +} + +macro_rules! unsigned_integer_bin_search { + ($typ:ident) => { + #[allow(missing_docs)] + pub mod $typ { + use rand::Rng; + + use crate::strategy::*; + use crate::test_runner::TestRunner; + + int_any!($typ); + + /// Shrinks an integer towards 0, using binary search to find + /// boundary points. + #[derive(Clone, Copy, Debug)] + pub struct BinarySearch { + lo: $typ, + curr: $typ, + hi: $typ, + } + impl BinarySearch { + /// Creates a new binary searcher starting at the given value. + pub fn new(start: $typ) -> Self { + BinarySearch { + lo: 0, + curr: start, + hi: start, + } + } + + /// Creates a new binary searcher which will not search below + /// the given `lo` value. + fn new_clamped(lo: $typ, start: $typ, _hi: $typ) -> Self { + BinarySearch { + lo: lo, + curr: start, + hi: start, + } + } + + /// Creates a new binary searcher which will not search below + /// the given `lo` value. + pub fn new_above(lo: $typ, start: $typ) -> Self { + BinarySearch::new_clamped(lo, start, start) + } + + fn reposition(&mut self) -> bool { + let interval = self.hi - self.lo; + let new_mid = self.lo + interval / 2; + + if new_mid == self.curr { + false + } else { + self.curr = new_mid; + true + } + } + } + impl ValueTree for BinarySearch { + type Value = $typ; + + fn current(&self) -> $typ { + self.curr + } + + fn simplify(&mut self) -> bool { + if self.hi <= self.lo { + return false; + } + + self.hi = self.curr; + self.reposition() + } + + fn complicate(&mut self) -> bool { + if self.hi <= self.lo { + return false; + } + + self.lo = self.curr + 1; + self.reposition() + } + } + + numeric_api!($typ, 1); + } + }; +} + +signed_integer_bin_search!(i8); +signed_integer_bin_search!(i16); +signed_integer_bin_search!(i32); +signed_integer_bin_search!(i64); +#[cfg(not(target_arch = "wasm32"))] +signed_integer_bin_search!(i128); +signed_integer_bin_search!(isize); +unsigned_integer_bin_search!(u8); +unsigned_integer_bin_search!(u16); +unsigned_integer_bin_search!(u32); +unsigned_integer_bin_search!(u64); +#[cfg(not(target_arch = "wasm32"))] +unsigned_integer_bin_search!(u128); +unsigned_integer_bin_search!(usize); + +bitflags! { + pub(crate) struct FloatTypes: u32 { + const POSITIVE = 0b0000_0001; + const NEGATIVE = 0b0000_0010; + const NORMAL = 0b0000_0100; + const SUBNORMAL = 0b0000_1000; + const ZERO = 0b0001_0000; + const INFINITE = 0b0010_0000; + const QUIET_NAN = 0b0100_0000; + const SIGNALING_NAN = 0b1000_0000; + const ANY = + Self::POSITIVE.bits | + Self::NEGATIVE.bits | + Self::NORMAL.bits | + Self::SUBNORMAL.bits | + Self::ZERO.bits | + Self::INFINITE.bits | + Self::QUIET_NAN.bits; + } +} + +impl FloatTypes { + fn normalise(mut self) -> Self { + if !self.intersects(FloatTypes::POSITIVE | FloatTypes::NEGATIVE) { + self |= FloatTypes::POSITIVE; + } + + if !self.intersects( + FloatTypes::NORMAL + | FloatTypes::SUBNORMAL + | FloatTypes::ZERO + | FloatTypes::INFINITE + | FloatTypes::QUIET_NAN + | FloatTypes::SIGNALING_NAN, + ) { + self |= FloatTypes::NORMAL; + } + self + } +} + +trait FloatLayout +where + Standard: Distribution, +{ + type Bits: Copy; + + const SIGN_MASK: Self::Bits; + const EXP_MASK: Self::Bits; + const EXP_ZERO: Self::Bits; + const MANTISSA_MASK: Self::Bits; +} + +impl FloatLayout for f32 { + type Bits = u32; + + const SIGN_MASK: u32 = 0x8000_0000; + const EXP_MASK: u32 = 0x7F80_0000; + const EXP_ZERO: u32 = 0x3F80_0000; + const MANTISSA_MASK: u32 = 0x007F_FFFF; +} + +impl FloatLayout for f64 { + type Bits = u64; + + const SIGN_MASK: u64 = 0x8000_0000_0000_0000; + const EXP_MASK: u64 = 0x7FF0_0000_0000_0000; + const EXP_ZERO: u64 = 0x3FF0_0000_0000_0000; + const MANTISSA_MASK: u64 = 0x000F_FFFF_FFFF_FFFF; +} + +macro_rules! float_any { + ($typ:ident) => { + /// Strategies which produce floating-point values from particular + /// classes. See the various `Any`-typed constants in this module. + /// + /// Note that this usage is fairly advanced and primarily useful to + /// implementors of algorithms that need to handle wild values in a + /// particular way. For testing things like graphics processing or game + /// physics, simply using ranges (e.g., `-1.0..2.0`) will often be more + /// practical. + /// + /// `Any` can be OR'ed to combine multiple classes. For example, + /// `POSITIVE | INFINITE` will generate arbitrary positive, non-NaN + /// floats, including positive infinity (but not negative infinity, of + /// course). + /// + /// If neither `POSITIVE` nor `NEGATIVE` has been OR'ed into an `Any` + /// but a type to be generated requires a sign, `POSITIVE` is assumed. + /// If no classes are OR'ed into an `Any` (i.e., only `POSITIVE` and/or + /// `NEGATIVE` are given), `NORMAL` is assumed. + /// + /// The various float classes are assigned fixed weights for generation + /// which are believed to be reasonable for most applications. Roughly: + /// + /// - If `POSITIVE | NEGATIVE`, the sign is evenly distributed between + /// both options. + /// + /// - Classes are weighted as follows, in descending order: + /// `NORMAL` > `ZERO` > `SUBNORMAL` > `INFINITE` > `QUIET_NAN` = + /// `SIGNALING_NAN`. + #[derive(Clone, Copy, Debug)] + #[must_use = "strategies do nothing unless used"] + pub struct Any(FloatTypes); + + #[cfg(test)] + impl Any { + pub(crate) fn from_bits(bits: u32) -> Self { + Any(FloatTypes::from_bits_truncate(bits)) + } + + pub(crate) fn normal_bits(&self) -> FloatTypes { + self.0.normalise() + } + } + + impl ops::BitOr for Any { + type Output = Self; + + fn bitor(self, rhs: Self) -> Self { + Any(self.0 | rhs.0) + } + } + + impl ops::BitOrAssign for Any { + fn bitor_assign(&mut self, rhs: Self) { + self.0 |= rhs.0 + } + } + + /// Generates positive floats + /// + /// By itself, implies the `NORMAL` class, unless another class is + /// OR'ed in. That is, using `POSITIVE` as a strategy by itself will + /// generate arbitrary values between the type's `MIN_POSITIVE` and + /// `MAX`, while `POSITIVE | INFINITE` would only allow generating + /// positive infinity. + pub const POSITIVE: Any = Any(FloatTypes::POSITIVE); + /// Generates negative floats. + /// + /// By itself, implies the `NORMAL` class, unless another class is + /// OR'ed in. That is, using `POSITIVE` as a strategy by itself will + /// generate arbitrary values between the type's `MIN` and + /// `-MIN_POSITIVE`, while `NEGATIVE | INFINITE` would only allow + /// generating positive infinity. + pub const NEGATIVE: Any = Any(FloatTypes::NEGATIVE); + /// Generates "normal" floats. + /// + /// These are finite values where the first bit of the mantissa is an + /// implied `1`. When positive, this represents the range + /// `MIN_POSITIVE` through `MAX`, both inclusive. + /// + /// Generated values are uniform over the discrete floating-point + /// space, which means the numeric distribution is an inverse + /// exponential step function. For example, values between 1.0 and 2.0 + /// are generated with the same frequency as values between 2.0 and + /// 4.0, even though the latter covers twice the numeric range. + /// + /// If neither `POSITIVE` nor `NEGATIVE` is OR'ed with this constant, + /// `POSITIVE` is implied. + pub const NORMAL: Any = Any(FloatTypes::NORMAL); + /// Generates subnormal floats. + /// + /// These are finite non-zero values where the first bit of the + /// mantissa is not an implied zero. When positive, this represents the + /// range `MIN`, inclusive, through `MIN_POSITIVE`, exclusive. + /// + /// Subnormals are generated with a uniform distribution both in terms + /// of discrete floating-point space and numerically. + /// + /// If neither `POSITIVE` nor `NEGATIVE` is OR'ed with this constant, + /// `POSITIVE` is implied. + pub const SUBNORMAL: Any = Any(FloatTypes::SUBNORMAL); + /// Generates zero-valued floats. + /// + /// Note that IEEE floats support both positive and negative zero, so + /// this class does interact with the sign flags. + /// + /// If neither `POSITIVE` nor `NEGATIVE` is OR'ed with this constant, + /// `POSITIVE` is implied. + pub const ZERO: Any = Any(FloatTypes::ZERO); + /// Generates infinity floats. + /// + /// If neither `POSITIVE` nor `NEGATIVE` is OR'ed with this constant, + /// `POSITIVE` is implied. + pub const INFINITE: Any = Any(FloatTypes::INFINITE); + /// Generates "Quiet NaN" floats. + /// + /// Operations on quiet NaNs generally simply propagate the NaN rather + /// than invoke any exception mechanism. + /// + /// The payload of the NaN is uniformly distributed over the possible + /// values which safe Rust allows, including the sign bit (as + /// controlled by `POSITIVE` and `NEGATIVE`). + /// + /// Note however that in Rust 1.23.0 and earlier, this constitutes only + /// one particular payload due to apparent issues with particular MIPS + /// and PA-RISC processors which fail to implement IEEE 754-2008 + /// correctly. + /// + /// On Rust 1.24.0 and later, this does produce arbitrary payloads as + /// documented. + /// + /// On platforms where the CPU and the IEEE standard disagree on the + /// format of a quiet NaN, values generated conform to the hardware's + /// expectations. + pub const QUIET_NAN: Any = Any(FloatTypes::QUIET_NAN); + /// Generates "Signaling NaN" floats if allowed by the platform. + /// + /// On most platforms, signalling NaNs by default behave the same as + /// quiet NaNs, but it is possible to configure the OS or CPU to raise + /// an asynchronous exception if an operation is performed on a + /// signalling NaN. + /// + /// In Rust 1.23.0 and earlier, this silently behaves the same as + /// [`QUIET_NAN`](const.QUIET_NAN.html). + /// + /// On platforms where the CPU and the IEEE standard disagree on the + /// format of a quiet NaN, values generated conform to the hardware's + /// expectations. + /// + /// Note that certain platforms — most notably, x86/AMD64 — allow the + /// architecture to turn a signalling NaN into a quiet NaN with the + /// same payload. Whether this happens can depend on what registers the + /// compiler decides to use to pass the value around, what CPU flags + /// are set, and what compiler settings are in use. + pub const SIGNALING_NAN: Any = Any(FloatTypes::SIGNALING_NAN); + + /// Generates literally arbitrary floating-point values, including + /// infinities and quiet NaNs (but not signaling NaNs). + /// + /// Equivalent to `POSITIVE | NEGATIVE | NORMAL | SUBNORMAL | ZERO | + /// INFINITE | QUIET_NAN`. + /// + /// See [`SIGNALING_NAN`](const.SIGNALING_NAN.html) if you also want to + /// generate signalling NaNs. This signalling NaNs are not included by + /// default since in most contexts they either make no difference, or + /// if the process enabled the relevant CPU mode, result in + /// hardware-triggered exceptions that usually just abort the process. + /// + /// Before proptest 0.4.1, this erroneously generated values in the + /// range 0.0..1.0. + pub const ANY: Any = Any(FloatTypes::ANY); + + impl Strategy for Any { + type Tree = BinarySearch; + type Value = $typ; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree { + let flags = self.0.normalise(); + let sign_mask = if flags.contains(FloatTypes::NEGATIVE) { + $typ::SIGN_MASK + } else { + 0 + }; + let sign_or = if flags.contains(FloatTypes::POSITIVE) { + 0 + } else { + $typ::SIGN_MASK + }; + + macro_rules! weight { + ($case:ident, $weight:expr) => { + if flags.contains(FloatTypes::$case) { + $weight + } else { + 0 + } + } + } + + // A few CPUs disagree with IEEE about the meaning of the + // signalling bit. Assume the `NAN` constant is a quiet NaN as + // interpreted by the hardware and generate values based on + // that. + let quiet_or = ::core::$typ::NAN.to_bits() & + ($typ::EXP_MASK | ($typ::EXP_MASK >> 1)); + let signaling_or = (quiet_or ^ ($typ::EXP_MASK >> 1)) | + $typ::EXP_MASK; + + let (class_mask, class_or, allow_edge_exp, allow_zero_mant) = + prop_oneof![ + weight!(NORMAL, 20) => Just( + ($typ::EXP_MASK | $typ::MANTISSA_MASK, 0, + false, true)), + weight!(SUBNORMAL, 3) => Just( + ($typ::MANTISSA_MASK, 0, true, false)), + weight!(ZERO, 4) => Just( + (0, 0, true, true)), + weight!(INFINITE, 2) => Just( + (0, $typ::EXP_MASK, true, true)), + weight!(QUIET_NAN, 1) => Just( + ($typ::MANTISSA_MASK >> 1, quiet_or, + true, false)), + weight!(SIGNALING_NAN, 1) => Just( + ($typ::MANTISSA_MASK >> 1, signaling_or, + true, false)), + ].new_tree(runner)?.current(); + + let mut generated_value: <$typ as FloatLayout>::Bits = + runner.rng().gen(); + generated_value &= sign_mask | class_mask; + generated_value |= sign_or | class_or; + let exp = generated_value & $typ::EXP_MASK; + if !allow_edge_exp && (0 == exp || $typ::EXP_MASK == exp) { + generated_value &= !$typ::EXP_MASK; + generated_value |= $typ::EXP_ZERO; + } + if !allow_zero_mant && + 0 == generated_value & $typ::MANTISSA_MASK + { + generated_value |= 1; + } + + Ok(BinarySearch::new_with_types( + $typ::from_bits(generated_value), flags)) + } + } + } +} + +macro_rules! float_bin_search { + ($typ:ident, $sample_typ:ident) => { + #[allow(missing_docs)] + pub mod $typ { + use super::float_samplers::$sample_typ; + + use core::ops; + #[cfg(not(feature = "std"))] + use num_traits::float::FloatCore; + + use rand::Rng; + + use super::{FloatLayout, FloatTypes}; + use crate::strategy::*; + use crate::test_runner::TestRunner; + + float_any!($typ); + + /// Shrinks a float towards 0, using binary search to find boundary + /// points. + /// + /// Non-finite values immediately shrink to 0. + #[derive(Clone, Copy, Debug)] + pub struct BinarySearch { + lo: $typ, + curr: $typ, + hi: $typ, + allowed: FloatTypes, + } + + impl BinarySearch { + /// Creates a new binary searcher starting at the given value. + pub fn new(start: $typ) -> Self { + BinarySearch { + lo: 0.0, + curr: start, + hi: start, + allowed: FloatTypes::all(), + } + } + + fn new_with_types(start: $typ, allowed: FloatTypes) -> Self { + BinarySearch { + lo: 0.0, + curr: start, + hi: start, + allowed, + } + } + + /// Creates a new binary searcher which will not produce values + /// on the other side of `lo` or `hi` from `start`. `lo` is + /// inclusive, `hi` is exclusive. + fn new_clamped(lo: $typ, start: $typ, hi: $typ) -> Self { + BinarySearch { + lo: if start.is_sign_negative() { + hi.min(0.0) + } else { + lo.max(0.0) + }, + hi: start, + curr: start, + allowed: FloatTypes::all(), + } + } + + fn current_allowed(&self) -> bool { + use core::num::FpCategory::*; + + // Don't reposition if the new value is not allowed + let class_allowed = match self.curr.classify() { + Nan => + // We don't need to inspect whether the + // signallingness of the NaN matches the allowed + // set, as we never try to switch between them, + // instead shrinking to 0. + { + self.allowed.contains(FloatTypes::QUIET_NAN) + || self + .allowed + .contains(FloatTypes::SIGNALING_NAN) + } + Infinite => self.allowed.contains(FloatTypes::INFINITE), + Zero => self.allowed.contains(FloatTypes::ZERO), + Subnormal => { + self.allowed.contains(FloatTypes::SUBNORMAL) + } + Normal => self.allowed.contains(FloatTypes::NORMAL), + }; + let signum = self.curr.signum(); + let sign_allowed = if signum > 0.0 { + self.allowed.contains(FloatTypes::POSITIVE) + } else if signum < 0.0 { + self.allowed.contains(FloatTypes::NEGATIVE) + } else { + true + }; + + class_allowed && sign_allowed + } + + fn ensure_acceptable(&mut self) { + while !self.current_allowed() { + if !self.complicate_once() { + panic!( + "Unable to complicate floating-point back \ + to acceptable value" + ); + } + } + } + + fn reposition(&mut self) -> bool { + let interval = self.hi - self.lo; + let interval = + if interval.is_finite() { interval } else { 0.0 }; + let new_mid = self.lo + interval / 2.0; + + let new_mid = if new_mid == self.curr || 0.0 == interval { + new_mid + } else { + self.lo + }; + + if new_mid == self.curr { + false + } else { + self.curr = new_mid; + true + } + } + + fn done(lo: $typ, hi: $typ) -> bool { + (lo.abs() > hi.abs() && !hi.is_nan()) || lo.is_nan() + } + + fn complicate_once(&mut self) -> bool { + if BinarySearch::done(self.lo, self.hi) { + return false; + } + + self.lo = if self.curr == self.lo { + self.hi + } else { + self.curr + }; + + self.reposition() + } + } + impl ValueTree for BinarySearch { + type Value = $typ; + + fn current(&self) -> $typ { + self.curr + } + + fn simplify(&mut self) -> bool { + if BinarySearch::done(self.lo, self.hi) { + return false; + } + + self.hi = self.curr; + if self.reposition() { + self.ensure_acceptable(); + true + } else { + false + } + } + + fn complicate(&mut self) -> bool { + if self.complicate_once() { + self.ensure_acceptable(); + true + } else { + false + } + } + } + + numeric_api!($typ, $sample_typ, 0.0); + } + }; +} + +float_bin_search!(f32, F32U); +float_bin_search!(f64, F64U); + +#[cfg(test)] +mod test { + use crate::strategy::*; + use crate::test_runner::*; + + use super::*; + + #[test] + fn u8_inclusive_end_included() { + let mut runner = TestRunner::deterministic(); + let mut ok = 0; + for _ in 0..20 { + let tree = (0..=1).new_tree(&mut runner).unwrap(); + let test = runner.run_one(tree, |v| { + prop_assert_eq!(v, 1); + Ok(()) + }); + if test.is_ok() { + ok += 1; + } + } + assert!(ok > 1, "inclusive end not included."); + } + + #[test] + fn u8_inclusive_to_end_included() { + let mut runner = TestRunner::deterministic(); + let mut ok = 0; + for _ in 0..20 { + let tree = (..=1u8).new_tree(&mut runner).unwrap(); + let test = runner.run_one(tree, |v| { + prop_assert_eq!(v, 1); + Ok(()) + }); + if test.is_ok() { + ok += 1; + } + } + assert!(ok > 1, "inclusive end not included."); + } + + #[test] + fn i8_binary_search_always_converges() { + fn assert_converges bool>(start: i8, pass: P) { + let mut state = i8::BinarySearch::new(start); + loop { + if !pass(state.current() as i32) { + if !state.simplify() { + break; + } + } else { + if !state.complicate() { + break; + } + } + } + + assert!(!pass(state.current() as i32)); + assert!( + pass(state.current() as i32 - 1) + || pass(state.current() as i32 + 1) + ); + } + + for start in -128..0 { + for target in start + 1..1 { + assert_converges(start as i8, |v| v > target); + } + } + + for start in 0..128 { + for target in 0..start { + assert_converges(start as i8, |v| v < target); + } + } + } + + #[test] + fn u8_binary_search_always_converges() { + fn assert_converges bool>(start: u8, pass: P) { + let mut state = u8::BinarySearch::new(start); + loop { + if !pass(state.current() as u32) { + if !state.simplify() { + break; + } + } else { + if !state.complicate() { + break; + } + } + } + + assert!(!pass(state.current() as u32)); + assert!(pass(state.current() as u32 - 1)); + } + + for start in 0..255 { + for target in 0..start { + assert_converges(start as u8, |v| v <= target); + } + } + } + + #[test] + fn signed_integer_range_including_zero_converges_to_zero() { + let mut runner = TestRunner::default(); + for _ in 0..100 { + let mut state = (-42i32..64i32).new_tree(&mut runner).unwrap(); + let init_value = state.current(); + assert!(init_value >= -42 && init_value < 64); + + while state.simplify() { + let v = state.current(); + assert!(v >= -42 && v < 64); + } + + assert_eq!(0, state.current()); + } + } + + #[test] + fn negative_integer_range_stays_in_bounds() { + let mut runner = TestRunner::default(); + for _ in 0..100 { + let mut state = (..-42i32).new_tree(&mut runner).unwrap(); + let init_value = state.current(); + assert!(init_value < -42); + + while state.simplify() { + assert!( + state.current() < -42, + "Violated bounds: {}", + state.current() + ); + } + + assert_eq!(-43, state.current()); + } + } + + #[test] + fn positive_signed_integer_range_stays_in_bounds() { + let mut runner = TestRunner::default(); + for _ in 0..100 { + let mut state = (42i32..).new_tree(&mut runner).unwrap(); + let init_value = state.current(); + assert!(init_value >= 42); + + while state.simplify() { + assert!( + state.current() >= 42, + "Violated bounds: {}", + state.current() + ); + } + + assert_eq!(42, state.current()); + } + } + + #[test] + fn unsigned_integer_range_stays_in_bounds() { + let mut runner = TestRunner::default(); + for _ in 0..100 { + let mut state = (42u32..56u32).new_tree(&mut runner).unwrap(); + let init_value = state.current(); + assert!(init_value >= 42 && init_value < 56); + + while state.simplify() { + assert!( + state.current() >= 42, + "Violated bounds: {}", + state.current() + ); + } + + assert_eq!(42, state.current()); + } + } + + mod contract_sanity { + macro_rules! contract_sanity { + ($t:tt) => { + mod $t { + use crate::strategy::check_strategy_sanity; + + const FOURTY_TWO: $t = 42 as $t; + const FIFTY_SIX: $t = 56 as $t; + + #[test] + fn range() { + check_strategy_sanity(FOURTY_TWO..FIFTY_SIX, None); + } + + #[test] + fn range_inclusive() { + check_strategy_sanity(FOURTY_TWO..=FIFTY_SIX, None); + } + + #[test] + fn range_to() { + check_strategy_sanity(..FIFTY_SIX, None); + } + + #[test] + fn range_to_inclusive() { + check_strategy_sanity(..=FIFTY_SIX, None); + } + + #[test] + fn range_from() { + check_strategy_sanity(FOURTY_TWO.., None); + } + } + }; + } + contract_sanity!(u8); + contract_sanity!(i8); + contract_sanity!(u16); + contract_sanity!(i16); + contract_sanity!(u32); + contract_sanity!(i32); + contract_sanity!(u64); + contract_sanity!(i64); + contract_sanity!(usize); + contract_sanity!(isize); + contract_sanity!(f32); + contract_sanity!(f64); + } + + #[test] + fn unsigned_integer_binsearch_simplify_complicate_contract_upheld() { + check_strategy_sanity(0u32..1000u32, None); + check_strategy_sanity(0u32..1u32, None); + } + + #[test] + fn signed_integer_binsearch_simplify_complicate_contract_upheld() { + check_strategy_sanity(0i32..1000i32, None); + check_strategy_sanity(0i32..1i32, None); + } + + #[test] + fn positive_float_simplifies_to_zero() { + let mut runner = TestRunner::default(); + let mut value = (0.0f64..2.0).new_tree(&mut runner).unwrap(); + + while value.simplify() {} + + assert_eq!(0.0, value.current()); + } + + #[test] + fn positive_float_simplifies_to_base() { + let mut runner = TestRunner::default(); + let mut value = (1.0f64..2.0).new_tree(&mut runner).unwrap(); + + while value.simplify() {} + + assert_eq!(1.0, value.current()); + } + + #[test] + fn negative_float_simplifies_to_zero() { + let mut runner = TestRunner::default(); + let mut value = (-2.0f64..0.0).new_tree(&mut runner).unwrap(); + + while value.simplify() {} + + assert_eq!(0.0, value.current()); + } + + #[test] + fn positive_float_complicates_to_original() { + let mut runner = TestRunner::default(); + let mut value = (1.0f64..2.0).new_tree(&mut runner).unwrap(); + let orig = value.current(); + + assert!(value.simplify()); + while value.complicate() {} + + assert_eq!(orig, value.current()); + } + + #[test] + fn positive_infinity_simplifies_directly_to_zero() { + let mut value = f64::BinarySearch::new(::std::f64::INFINITY); + + assert!(value.simplify()); + assert_eq!(0.0, value.current()); + assert!(value.complicate()); + assert_eq!(::std::f64::INFINITY, value.current()); + assert!(!value.clone().complicate()); + assert!(!value.clone().simplify()); + } + + #[test] + fn negative_infinity_simplifies_directly_to_zero() { + let mut value = f64::BinarySearch::new(::std::f64::NEG_INFINITY); + + assert!(value.simplify()); + assert_eq!(0.0, value.current()); + assert!(value.complicate()); + assert_eq!(::std::f64::NEG_INFINITY, value.current()); + assert!(!value.clone().complicate()); + assert!(!value.clone().simplify()); + } + + #[test] + fn nan_simplifies_directly_to_zero() { + let mut value = f64::BinarySearch::new(::std::f64::NAN); + + assert!(value.simplify()); + assert_eq!(0.0, value.current()); + assert!(value.complicate()); + assert!(value.current().is_nan()); + assert!(!value.clone().complicate()); + assert!(!value.clone().simplify()); + } + + #[test] + fn float_simplifies_to_smallest_normal() { + let mut runner = TestRunner::default(); + let mut value = (::std::f64::MIN_POSITIVE..2.0) + .new_tree(&mut runner) + .unwrap(); + + while value.simplify() {} + + assert_eq!(::std::f64::MIN_POSITIVE, value.current()); + } + + macro_rules! float_generation_test_body { + ($strategy:ident, $typ:ident) => { + use std::num::FpCategory; + + let strategy = $strategy; + let bits = strategy.normal_bits(); + + let mut seen_positive = 0; + let mut seen_negative = 0; + let mut seen_normal = 0; + let mut seen_subnormal = 0; + let mut seen_zero = 0; + let mut seen_infinite = 0; + let mut seen_quiet_nan = 0; + let mut seen_signaling_nan = 0; + let mut runner = TestRunner::deterministic(); + + // Check whether this version of Rust honours the NaN payload in + // from_bits + let fidelity_1 = f32::from_bits(0x7F80_0001).to_bits(); + let fidelity_2 = f32::from_bits(0xFF80_0001).to_bits(); + let nan_fidelity = fidelity_1 != fidelity_2; + + for _ in 0..1024 { + let mut tree = strategy.new_tree(&mut runner).unwrap(); + let mut increment = 1; + + loop { + let value = tree.current(); + + let sign = value.signum(); // So we correctly handle -0 + if sign < 0.0 { + prop_assert!(bits.contains(FloatTypes::NEGATIVE)); + seen_negative += increment; + } else if sign > 0.0 { + // i.e., not NaN + prop_assert!(bits.contains(FloatTypes::POSITIVE)); + seen_positive += increment; + } + + match value.classify() { + FpCategory::Nan if nan_fidelity => { + let raw = value.to_bits(); + let is_negative = raw << 1 >> 1 != raw; + if is_negative { + prop_assert!( + bits.contains(FloatTypes::NEGATIVE) + ); + seen_negative += increment; + } else { + prop_assert!( + bits.contains(FloatTypes::POSITIVE) + ); + seen_positive += increment; + } + + let is_quiet = raw & ($typ::EXP_MASK >> 1) + == ::std::$typ::NAN.to_bits() + & ($typ::EXP_MASK >> 1); + if is_quiet { + // x86/AMD64 turn signalling NaNs into quiet + // NaNs quite aggressively depending on what + // registers LLVM decides to use to pass the + // value around, so accept either case here. + prop_assert!( + bits.contains(FloatTypes::QUIET_NAN) + || bits.contains( + FloatTypes::SIGNALING_NAN + ) + ); + seen_quiet_nan += increment; + seen_signaling_nan += increment; + } else { + prop_assert!( + bits.contains(FloatTypes::SIGNALING_NAN) + ); + seen_signaling_nan += increment; + } + } + + FpCategory::Nan => { + // Since safe Rust doesn't currently allow + // generating any NaN other than one particular + // payload, don't check the sign or signallingness + // and consider this to be both signs and + // signallingness for counting purposes. + seen_positive += increment; + seen_negative += increment; + seen_quiet_nan += increment; + seen_signaling_nan += increment; + prop_assert!( + bits.contains(FloatTypes::QUIET_NAN) + || bits.contains(FloatTypes::SIGNALING_NAN) + ); + } + FpCategory::Infinite => { + prop_assert!(bits.contains(FloatTypes::INFINITE)); + seen_infinite += increment; + } + FpCategory::Zero => { + prop_assert!(bits.contains(FloatTypes::ZERO)); + seen_zero += increment; + } + FpCategory::Subnormal => { + prop_assert!(bits.contains(FloatTypes::SUBNORMAL)); + seen_subnormal += increment; + } + FpCategory::Normal => { + prop_assert!(bits.contains(FloatTypes::NORMAL)); + seen_normal += increment; + } + } + + // Don't count simplified values towards the counts + increment = 0; + if !tree.simplify() { + break; + } + } + } + + if bits.contains(FloatTypes::POSITIVE) { + prop_assert!(seen_positive > 200); + } + if bits.contains(FloatTypes::NEGATIVE) { + prop_assert!(seen_negative > 200); + } + if bits.contains(FloatTypes::NORMAL) { + prop_assert!(seen_normal > 100); + } + if bits.contains(FloatTypes::SUBNORMAL) { + prop_assert!(seen_subnormal > 5); + } + if bits.contains(FloatTypes::ZERO) { + prop_assert!(seen_zero > 5); + } + if bits.contains(FloatTypes::INFINITE) { + prop_assert!(seen_infinite > 0); + } + if bits.contains(FloatTypes::QUIET_NAN) { + prop_assert!(seen_quiet_nan > 0); + } + if bits.contains(FloatTypes::SIGNALING_NAN) { + prop_assert!(seen_signaling_nan > 0); + } + }; + } + + proptest! { + #![proptest_config(crate::test_runner::Config::with_cases(1024))] + + #[test] + fn f32_any_generates_desired_values( + strategy in crate::bits::u32::ANY.prop_map(f32::Any::from_bits) + ) { + float_generation_test_body!(strategy, f32); + } + + #[test] + fn f32_any_sanity( + strategy in crate::bits::u32::ANY.prop_map(f32::Any::from_bits) + ) { + check_strategy_sanity(strategy, Some(CheckStrategySanityOptions { + strict_complicate_after_simplify: false, + .. CheckStrategySanityOptions::default() + })); + } + + #[test] + fn f64_any_generates_desired_values( + strategy in crate::bits::u32::ANY.prop_map(f64::Any::from_bits) + ) { + float_generation_test_body!(strategy, f64); + } + + #[test] + fn f64_any_sanity( + strategy in crate::bits::u32::ANY.prop_map(f64::Any::from_bits) + ) { + check_strategy_sanity(strategy, Some(CheckStrategySanityOptions { + strict_complicate_after_simplify: false, + .. CheckStrategySanityOptions::default() + })); + } + } +} -- cgit v1.2.3