summaryrefslogtreecommitdiffstats
path: root/vendor/proptest/src/num.rs
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/proptest/src/num.rs')
-rw-r--r--vendor/proptest/src/num.rs1388
1 files changed, 1388 insertions, 0 deletions
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 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, 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<X: SampleUniform>(
+ run: &mut TestRunner,
+ start: X,
+ end: X,
+) -> X {
+ Uniform::new(start, end).sample(run.rng())
+}
+
+pub(crate) fn sample_uniform_incl<X: SampleUniform>(
+ 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<Self> {
+ 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<Self> {
+ 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<Self> {
+ 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<Self> {
+ 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<Self> {
+ 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<Self> {
+ 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<Self::Bits>,
+{
+ 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<Self> {
+ 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<P: Fn(i32) -> 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<P: Fn(u32) -> 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()
+ }));
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-24 20:26:22 +0000