//-
// 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.
use crate::test_runner::TestRunner;
use core::ops::Range;
use rand::distributions::uniform::{SampleUniform, Uniform};
use rand::distributions::{Distribution, Standard};
pub(crate) fn sample_uniform<X: SampleUniform>(
run: &mut TestRunner,
range: Range<X>,
) -> X {
Uniform::new(range.start, range.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) => {
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(runner, self.clone()),
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(
runner,
*self.start(),
*self.end(),
),
*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(
runner,
self.start,
::core::$typ::MAX,
),
::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(
runner,
::core::$typ::MIN..self.end,
),
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(
runner,
::core::$typ::MIN,
self.end,
),
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) => {
#[allow(missing_docs)]
pub mod $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, 0.0);
}
};
}
float_bin_search!(f32);
float_bin_search!(f64);
#[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()
}));
}
}
}