proptest/
num.rs

1//-
2// Copyright 2017, 2018 Jason Lingle
3//
4// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
5// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
6// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
7// option. This file may not be copied, modified, or distributed
8// except according to those terms.
9
10//! Strategies to generate numeric values (as opposed to integers used as bit
11//! fields).
12//!
13//! All strategies in this module shrink by binary searching towards 0.
14
15mod float_samplers;
16
17use crate::test_runner::TestRunner;
18use rand::distributions::uniform::{SampleUniform, Uniform};
19use rand::distributions::{Distribution, Standard};
20
21/// Generate a random value of `X`, sampled uniformly from the half
22/// open range `[low, high)` (excluding `high`). Panics if `low >= high`.
23pub(crate) fn sample_uniform<X: SampleUniform>(
24    run: &mut TestRunner,
25    start: X,
26    end: X,
27) -> X {
28    Uniform::new(start, end).sample(run.rng())
29}
30
31/// Generate a random value of `X`, sampled uniformly from the closed
32/// range `[low, high]` (inclusive). Panics if `low > high`.
33pub fn sample_uniform_incl<X: SampleUniform>(
34    run: &mut TestRunner,
35    start: X,
36    end: X,
37) -> X {
38    Uniform::new_inclusive(start, end).sample(run.rng())
39}
40
41macro_rules! int_any {
42    ($typ: ident) => {
43        /// Type of the `ANY` constant.
44        #[derive(Clone, Copy, Debug)]
45        #[must_use = "strategies do nothing unless used"]
46        pub struct Any(());
47        /// Generates integers with completely arbitrary values, uniformly
48        /// distributed over the whole range.
49        pub const ANY: Any = Any(());
50
51        impl Strategy for Any {
52            type Tree = BinarySearch;
53            type Value = $typ;
54
55            fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
56                Ok(BinarySearch::new(runner.rng().gen()))
57            }
58        }
59    };
60}
61
62macro_rules! numeric_api {
63    ($typ:ident, $epsilon:expr) => {
64        numeric_api!($typ, $typ, $epsilon);
65    };
66    ($typ:ident, $sample_typ:ty, $epsilon:expr) => {
67        impl Strategy for ::core::ops::Range<$typ> {
68            type Tree = BinarySearch;
69            type Value = $typ;
70
71            fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
72                if self.is_empty() {
73                    panic!(
74                        "Invalid use of empty range {}..{}.",
75                        self.start, self.end
76                    );
77                }
78
79                Ok(BinarySearch::new_clamped(
80                    self.start,
81                    $crate::num::sample_uniform::<$sample_typ>(
82                        runner,
83                        self.start.into(),
84                        self.end.into(),
85                    )
86                    .into(),
87                    self.end - $epsilon,
88                ))
89            }
90        }
91
92        impl Strategy for ::core::ops::RangeInclusive<$typ> {
93            type Tree = BinarySearch;
94            type Value = $typ;
95
96            fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
97                if self.is_empty() {
98                    panic!(
99                        "Invalid use of empty range {}..={}.",
100                        self.start(),
101                        self.end()
102                    );
103                }
104
105                Ok(BinarySearch::new_clamped(
106                    *self.start(),
107                    $crate::num::sample_uniform_incl::<$sample_typ>(
108                        runner,
109                        (*self.start()).into(),
110                        (*self.end()).into(),
111                    )
112                    .into(),
113                    *self.end(),
114                ))
115            }
116        }
117
118        impl Strategy for ::core::ops::RangeFrom<$typ> {
119            type Tree = BinarySearch;
120            type Value = $typ;
121
122            fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
123                Ok(BinarySearch::new_clamped(
124                    self.start,
125                    $crate::num::sample_uniform_incl::<$sample_typ>(
126                        runner,
127                        self.start.into(),
128                        ::core::$typ::MAX.into(),
129                    )
130                    .into(),
131                    ::core::$typ::MAX,
132                ))
133            }
134        }
135
136        impl Strategy for ::core::ops::RangeTo<$typ> {
137            type Tree = BinarySearch;
138            type Value = $typ;
139
140            fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
141                Ok(BinarySearch::new_clamped(
142                    ::core::$typ::MIN,
143                    $crate::num::sample_uniform::<$sample_typ>(
144                        runner,
145                        ::core::$typ::MIN.into(),
146                        self.end.into(),
147                    )
148                    .into(),
149                    self.end,
150                ))
151            }
152        }
153
154        impl Strategy for ::core::ops::RangeToInclusive<$typ> {
155            type Tree = BinarySearch;
156            type Value = $typ;
157
158            fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
159                Ok(BinarySearch::new_clamped(
160                    ::core::$typ::MIN,
161                    $crate::num::sample_uniform_incl::<$sample_typ>(
162                        runner,
163                        ::core::$typ::MIN.into(),
164                        self.end.into(),
165                    )
166                    .into(),
167                    self.end,
168                ))
169            }
170        }
171    };
172}
173
174macro_rules! signed_integer_bin_search {
175    ($typ:ident) => {
176        #[allow(missing_docs)]
177        pub mod $typ {
178            use rand::Rng;
179
180            use crate::strategy::*;
181            use crate::test_runner::TestRunner;
182
183            int_any!($typ);
184
185            /// Shrinks an integer towards 0, using binary search to find
186            /// boundary points.
187            #[derive(Clone, Copy, Debug)]
188            pub struct BinarySearch {
189                lo: $typ,
190                curr: $typ,
191                hi: $typ,
192            }
193            impl BinarySearch {
194                /// Creates a new binary searcher starting at the given value.
195                pub fn new(start: $typ) -> Self {
196                    BinarySearch {
197                        lo: 0,
198                        curr: start,
199                        hi: start,
200                    }
201                }
202
203                /// Creates a new binary searcher which will not produce values
204                /// on the other side of `lo` or `hi` from `start`. `lo` is
205                /// inclusive, `hi` is exclusive.
206                fn new_clamped(lo: $typ, start: $typ, hi: $typ) -> Self {
207                    use core::cmp::{max, min};
208
209                    BinarySearch {
210                        lo: if start < 0 {
211                            min(0, hi - 1)
212                        } else {
213                            max(0, lo)
214                        },
215                        hi: start,
216                        curr: start,
217                    }
218                }
219
220                fn reposition(&mut self) -> bool {
221                    // Won't ever overflow since lo starts at 0 and advances
222                    // towards hi.
223                    let interval = self.hi - self.lo;
224                    let new_mid = self.lo + interval / 2;
225
226                    if new_mid == self.curr {
227                        false
228                    } else {
229                        self.curr = new_mid;
230                        true
231                    }
232                }
233
234                fn magnitude_greater(lhs: $typ, rhs: $typ) -> bool {
235                    if 0 == lhs {
236                        false
237                    } else if lhs < 0 {
238                        lhs < rhs
239                    } else {
240                        lhs > rhs
241                    }
242                }
243            }
244            impl ValueTree for BinarySearch {
245                type Value = $typ;
246
247                fn current(&self) -> $typ {
248                    self.curr
249                }
250
251                fn simplify(&mut self) -> bool {
252                    if !BinarySearch::magnitude_greater(self.hi, self.lo) {
253                        return false;
254                    }
255
256                    self.hi = self.curr;
257                    self.reposition()
258                }
259
260                fn complicate(&mut self) -> bool {
261                    if !BinarySearch::magnitude_greater(self.hi, self.lo) {
262                        return false;
263                    }
264
265                    self.lo = self.curr + if self.hi < 0 { -1 } else { 1 };
266
267                    self.reposition()
268                }
269            }
270
271            numeric_api!($typ, 1);
272        }
273    };
274}
275
276macro_rules! unsigned_integer_bin_search {
277    ($typ:ident) => {
278        #[allow(missing_docs)]
279        pub mod $typ {
280            use rand::Rng;
281
282            use crate::strategy::*;
283            use crate::test_runner::TestRunner;
284
285            int_any!($typ);
286
287            /// Shrinks an integer towards 0, using binary search to find
288            /// boundary points.
289            #[derive(Clone, Copy, Debug)]
290            pub struct BinarySearch {
291                lo: $typ,
292                curr: $typ,
293                hi: $typ,
294            }
295            impl BinarySearch {
296                /// Creates a new binary searcher starting at the given value.
297                pub fn new(start: $typ) -> Self {
298                    BinarySearch {
299                        lo: 0,
300                        curr: start,
301                        hi: start,
302                    }
303                }
304
305                /// Creates a new binary searcher which will not search below
306                /// the given `lo` value.
307                fn new_clamped(lo: $typ, start: $typ, _hi: $typ) -> Self {
308                    BinarySearch {
309                        lo: lo,
310                        curr: start,
311                        hi: start,
312                    }
313                }
314
315                /// Creates a new binary searcher which will not search below
316                /// the given `lo` value.
317                pub fn new_above(lo: $typ, start: $typ) -> Self {
318                    BinarySearch::new_clamped(lo, start, start)
319                }
320
321                fn reposition(&mut self) -> bool {
322                    let interval = self.hi - self.lo;
323                    let new_mid = self.lo + interval / 2;
324
325                    if new_mid == self.curr {
326                        false
327                    } else {
328                        self.curr = new_mid;
329                        true
330                    }
331                }
332            }
333            impl ValueTree for BinarySearch {
334                type Value = $typ;
335
336                fn current(&self) -> $typ {
337                    self.curr
338                }
339
340                fn simplify(&mut self) -> bool {
341                    if self.hi <= self.lo {
342                        return false;
343                    }
344
345                    self.hi = self.curr;
346                    self.reposition()
347                }
348
349                fn complicate(&mut self) -> bool {
350                    if self.hi <= self.lo {
351                        return false;
352                    }
353
354                    self.lo = self.curr + 1;
355                    self.reposition()
356                }
357            }
358
359            numeric_api!($typ, 1);
360        }
361    };
362}
363
364signed_integer_bin_search!(i8);
365signed_integer_bin_search!(i16);
366signed_integer_bin_search!(i32);
367signed_integer_bin_search!(i64);
368#[cfg(not(target_arch = "wasm32"))]
369signed_integer_bin_search!(i128);
370signed_integer_bin_search!(isize);
371unsigned_integer_bin_search!(u8);
372unsigned_integer_bin_search!(u16);
373unsigned_integer_bin_search!(u32);
374unsigned_integer_bin_search!(u64);
375#[cfg(not(target_arch = "wasm32"))]
376unsigned_integer_bin_search!(u128);
377unsigned_integer_bin_search!(usize);
378
379bitflags! {
380    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
381    pub(crate) struct FloatTypes: u32 {
382        const POSITIVE          = 0b0000_0001;
383        const NEGATIVE          = 0b0000_0010;
384        const NORMAL            = 0b0000_0100;
385        const SUBNORMAL         = 0b0000_1000;
386        const ZERO              = 0b0001_0000;
387        const INFINITE          = 0b0010_0000;
388        const QUIET_NAN         = 0b0100_0000;
389        const SIGNALING_NAN     = 0b1000_0000;
390        const ANY =
391            Self::POSITIVE.bits() |
392            Self::NEGATIVE.bits() |
393            Self::NORMAL.bits() |
394            Self::SUBNORMAL.bits() |
395            Self::ZERO.bits() |
396            Self::INFINITE.bits() |
397            Self::QUIET_NAN.bits();
398    }
399}
400
401impl FloatTypes {
402    fn normalise(mut self) -> Self {
403        if !self.intersects(FloatTypes::POSITIVE | FloatTypes::NEGATIVE) {
404            self |= FloatTypes::POSITIVE;
405        }
406
407        if !self.intersects(
408            FloatTypes::NORMAL
409                | FloatTypes::SUBNORMAL
410                | FloatTypes::ZERO
411                | FloatTypes::INFINITE
412                | FloatTypes::QUIET_NAN
413                | FloatTypes::SIGNALING_NAN,
414        ) {
415            self |= FloatTypes::NORMAL;
416        }
417        self
418    }
419}
420
421trait FloatLayout
422where
423    Standard: Distribution<Self::Bits>,
424{
425    type Bits: Copy;
426
427    const SIGN_MASK: Self::Bits;
428    const EXP_MASK: Self::Bits;
429    const EXP_ZERO: Self::Bits;
430    const MANTISSA_MASK: Self::Bits;
431}
432
433impl FloatLayout for f32 {
434    type Bits = u32;
435
436    const SIGN_MASK: u32 = 0x8000_0000;
437    const EXP_MASK: u32 = 0x7F80_0000;
438    const EXP_ZERO: u32 = 0x3F80_0000;
439    const MANTISSA_MASK: u32 = 0x007F_FFFF;
440}
441
442impl FloatLayout for f64 {
443    type Bits = u64;
444
445    const SIGN_MASK: u64 = 0x8000_0000_0000_0000;
446    const EXP_MASK: u64 = 0x7FF0_0000_0000_0000;
447    const EXP_ZERO: u64 = 0x3FF0_0000_0000_0000;
448    const MANTISSA_MASK: u64 = 0x000F_FFFF_FFFF_FFFF;
449}
450
451macro_rules! float_any {
452    ($typ:ident) => {
453        /// Strategies which produce floating-point values from particular
454        /// classes. See the various `Any`-typed constants in this module.
455        ///
456        /// Note that this usage is fairly advanced and primarily useful to
457        /// implementors of algorithms that need to handle wild values in a
458        /// particular way. For testing things like graphics processing or game
459        /// physics, simply using ranges (e.g., `-1.0..2.0`) will often be more
460        /// practical.
461        ///
462        /// `Any` can be OR'ed to combine multiple classes. For example,
463        /// `POSITIVE | INFINITE` will generate arbitrary positive, non-NaN
464        /// floats, including positive infinity (but not negative infinity, of
465        /// course).
466        ///
467        /// If neither `POSITIVE` nor `NEGATIVE` has been OR'ed into an `Any`
468        /// but a type to be generated requires a sign, `POSITIVE` is assumed.
469        /// If no classes are OR'ed into an `Any` (i.e., only `POSITIVE` and/or
470        /// `NEGATIVE` are given), `NORMAL` is assumed.
471        ///
472        /// The various float classes are assigned fixed weights for generation
473        /// which are believed to be reasonable for most applications. Roughly:
474        ///
475        /// - If `POSITIVE | NEGATIVE`, the sign is evenly distributed between
476        ///   both options.
477        ///
478        /// - Classes are weighted as follows, in descending order:
479        ///   `NORMAL` > `ZERO` > `SUBNORMAL` > `INFINITE` > `QUIET_NAN` =
480        ///   `SIGNALING_NAN`.
481        #[derive(Clone, Copy, Debug)]
482        #[must_use = "strategies do nothing unless used"]
483        pub struct Any(FloatTypes);
484
485        #[cfg(test)]
486        impl Any {
487            pub(crate) fn from_bits(bits: u32) -> Self {
488                Any(FloatTypes::from_bits_truncate(bits))
489            }
490
491            pub(crate) fn normal_bits(&self) -> FloatTypes {
492                self.0.normalise()
493            }
494        }
495
496        impl ops::BitOr for Any {
497            type Output = Self;
498
499            fn bitor(self, rhs: Self) -> Self {
500                Any(self.0 | rhs.0)
501            }
502        }
503
504        impl ops::BitOrAssign for Any {
505            fn bitor_assign(&mut self, rhs: Self) {
506                self.0 |= rhs.0
507            }
508        }
509
510        /// Generates positive floats
511        ///
512        /// By itself, implies the `NORMAL` class, unless another class is
513        /// OR'ed in. That is, using `POSITIVE` as a strategy by itself will
514        /// generate arbitrary values between the type's `MIN_POSITIVE` and
515        /// `MAX`, while `POSITIVE | INFINITE` would only allow generating
516        /// positive infinity.
517        pub const POSITIVE: Any = Any(FloatTypes::POSITIVE);
518        /// Generates negative floats.
519        ///
520        /// By itself, implies the `NORMAL` class, unless another class is
521        /// OR'ed in. That is, using `POSITIVE` as a strategy by itself will
522        /// generate arbitrary values between the type's `MIN` and
523        /// `-MIN_POSITIVE`, while `NEGATIVE | INFINITE` would only allow
524        /// generating positive infinity.
525        pub const NEGATIVE: Any = Any(FloatTypes::NEGATIVE);
526        /// Generates "normal" floats.
527        ///
528        /// These are finite values where the first bit of the mantissa is an
529        /// implied `1`. When positive, this represents the range
530        /// `MIN_POSITIVE` through `MAX`, both inclusive.
531        ///
532        /// Generated values are uniform over the discrete floating-point
533        /// space, which means the numeric distribution is an inverse
534        /// exponential step function. For example, values between 1.0 and 2.0
535        /// are generated with the same frequency as values between 2.0 and
536        /// 4.0, even though the latter covers twice the numeric range.
537        ///
538        /// If neither `POSITIVE` nor `NEGATIVE` is OR'ed with this constant,
539        /// `POSITIVE` is implied.
540        pub const NORMAL: Any = Any(FloatTypes::NORMAL);
541        /// Generates subnormal floats.
542        ///
543        /// These are finite non-zero values where the first bit of the
544        /// mantissa is not an implied zero. When positive, this represents the
545        /// range `MIN`, inclusive, through `MIN_POSITIVE`, exclusive.
546        ///
547        /// Subnormals are generated with a uniform distribution both in terms
548        /// of discrete floating-point space and numerically.
549        ///
550        /// If neither `POSITIVE` nor `NEGATIVE` is OR'ed with this constant,
551        /// `POSITIVE` is implied.
552        pub const SUBNORMAL: Any = Any(FloatTypes::SUBNORMAL);
553        /// Generates zero-valued floats.
554        ///
555        /// Note that IEEE floats support both positive and negative zero, so
556        /// this class does interact with the sign flags.
557        ///
558        /// If neither `POSITIVE` nor `NEGATIVE` is OR'ed with this constant,
559        /// `POSITIVE` is implied.
560        pub const ZERO: Any = Any(FloatTypes::ZERO);
561        /// Generates infinity floats.
562        ///
563        /// If neither `POSITIVE` nor `NEGATIVE` is OR'ed with this constant,
564        /// `POSITIVE` is implied.
565        pub const INFINITE: Any = Any(FloatTypes::INFINITE);
566        /// Generates "Quiet NaN" floats.
567        ///
568        /// Operations on quiet NaNs generally simply propagate the NaN rather
569        /// than invoke any exception mechanism.
570        ///
571        /// The payload of the NaN is uniformly distributed over the possible
572        /// values which safe Rust allows, including the sign bit (as
573        /// controlled by `POSITIVE` and `NEGATIVE`).
574        ///
575        /// Note however that in Rust 1.23.0 and earlier, this constitutes only
576        /// one particular payload due to apparent issues with particular MIPS
577        /// and PA-RISC processors which fail to implement IEEE 754-2008
578        /// correctly.
579        ///
580        /// On Rust 1.24.0 and later, this does produce arbitrary payloads as
581        /// documented.
582        ///
583        /// On platforms where the CPU and the IEEE standard disagree on the
584        /// format of a quiet NaN, values generated conform to the hardware's
585        /// expectations.
586        pub const QUIET_NAN: Any = Any(FloatTypes::QUIET_NAN);
587        /// Generates "Signaling NaN" floats if allowed by the platform.
588        ///
589        /// On most platforms, signalling NaNs by default behave the same as
590        /// quiet NaNs, but it is possible to configure the OS or CPU to raise
591        /// an asynchronous exception if an operation is performed on a
592        /// signalling NaN.
593        ///
594        /// In Rust 1.23.0 and earlier, this silently behaves the same as
595        /// [`QUIET_NAN`](const.QUIET_NAN.html).
596        ///
597        /// On platforms where the CPU and the IEEE standard disagree on the
598        /// format of a quiet NaN, values generated conform to the hardware's
599        /// expectations.
600        ///
601        /// Note that certain platforms — most notably, x86/AMD64 — allow the
602        /// architecture to turn a signalling NaN into a quiet NaN with the
603        /// same payload. Whether this happens can depend on what registers the
604        /// compiler decides to use to pass the value around, what CPU flags
605        /// are set, and what compiler settings are in use.
606        pub const SIGNALING_NAN: Any = Any(FloatTypes::SIGNALING_NAN);
607
608        /// Generates literally arbitrary floating-point values, including
609        /// infinities and quiet NaNs (but not signaling NaNs).
610        ///
611        /// Equivalent to `POSITIVE | NEGATIVE | NORMAL | SUBNORMAL | ZERO |
612        /// INFINITE | QUIET_NAN`.
613        ///
614        /// See [`SIGNALING_NAN`](const.SIGNALING_NAN.html) if you also want to
615        /// generate signalling NaNs. This signalling NaNs are not included by
616        /// default since in most contexts they either make no difference, or
617        /// if the process enabled the relevant CPU mode, result in
618        /// hardware-triggered exceptions that usually just abort the process.
619        ///
620        /// Before proptest 0.4.1, this erroneously generated values in the
621        /// range 0.0..1.0.
622        pub const ANY: Any = Any(FloatTypes::ANY);
623
624        impl Strategy for Any {
625            type Tree = BinarySearch;
626            type Value = $typ;
627
628            fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
629                let flags = self.0.normalise();
630                let sign_mask = if flags.contains(FloatTypes::NEGATIVE) {
631                    $typ::SIGN_MASK
632                } else {
633                    0
634                };
635                let sign_or = if flags.contains(FloatTypes::POSITIVE) {
636                    0
637                } else {
638                    $typ::SIGN_MASK
639                };
640
641                macro_rules! weight {
642                    ($case:ident, $weight:expr) => {
643                        if flags.contains(FloatTypes::$case) {
644                            $weight
645                        } else {
646                            0
647                        }
648                    }
649                }
650
651                // A few CPUs disagree with IEEE about the meaning of the
652                // signalling bit. Assume the `NAN` constant is a quiet NaN as
653                // interpreted by the hardware and generate values based on
654                // that.
655                let quiet_or = ::core::$typ::NAN.to_bits() &
656                    ($typ::EXP_MASK | ($typ::EXP_MASK >> 1));
657                let signaling_or = (quiet_or ^ ($typ::EXP_MASK >> 1)) |
658                    $typ::EXP_MASK;
659
660                let (class_mask, class_or, allow_edge_exp, allow_zero_mant) =
661                    prop_oneof![
662                        weight!(NORMAL, 20) => Just(
663                            ($typ::EXP_MASK | $typ::MANTISSA_MASK, 0,
664                             false, true)),
665                        weight!(SUBNORMAL, 3) => Just(
666                            ($typ::MANTISSA_MASK, 0, true, false)),
667                        weight!(ZERO, 4) => Just(
668                            (0, 0, true, true)),
669                        weight!(INFINITE, 2) => Just(
670                            (0, $typ::EXP_MASK, true, true)),
671                        weight!(QUIET_NAN, 1) => Just(
672                            ($typ::MANTISSA_MASK >> 1, quiet_or,
673                             true, false)),
674                        weight!(SIGNALING_NAN, 1) => Just(
675                            ($typ::MANTISSA_MASK >> 1, signaling_or,
676                             true, false)),
677                    ].new_tree(runner)?.current();
678
679                let mut generated_value: <$typ as FloatLayout>::Bits =
680                    runner.rng().gen();
681                generated_value &= sign_mask | class_mask;
682                generated_value |= sign_or | class_or;
683                let exp = generated_value & $typ::EXP_MASK;
684                if !allow_edge_exp && (0 == exp || $typ::EXP_MASK == exp) {
685                    generated_value &= !$typ::EXP_MASK;
686                    generated_value |= $typ::EXP_ZERO;
687                }
688                if !allow_zero_mant &&
689                    0 == generated_value & $typ::MANTISSA_MASK
690                {
691                    generated_value |= 1;
692                }
693
694                Ok(BinarySearch::new_with_types(
695                    $typ::from_bits(generated_value), flags))
696            }
697        }
698    }
699}
700
701macro_rules! float_bin_search {
702    ($typ:ident, $sample_typ:ident) => {
703        #[allow(missing_docs)]
704        pub mod $typ {
705            use super::float_samplers::$sample_typ;
706
707            use core::ops;
708            #[cfg(not(feature = "std"))]
709            use num_traits::float::FloatCore;
710
711            use rand::Rng;
712
713            use super::{FloatLayout, FloatTypes};
714            use crate::strategy::*;
715            use crate::test_runner::TestRunner;
716
717            float_any!($typ);
718
719            /// Shrinks a float towards 0, using binary search to find boundary
720            /// points.
721            ///
722            /// Non-finite values immediately shrink to 0.
723            #[derive(Clone, Copy, Debug)]
724            pub struct BinarySearch {
725                lo: $typ,
726                curr: $typ,
727                hi: $typ,
728                allowed: FloatTypes,
729            }
730
731            impl BinarySearch {
732                /// Creates a new binary searcher starting at the given value.
733                pub fn new(start: $typ) -> Self {
734                    BinarySearch {
735                        lo: 0.0,
736                        curr: start,
737                        hi: start,
738                        allowed: FloatTypes::all(),
739                    }
740                }
741
742                fn new_with_types(start: $typ, allowed: FloatTypes) -> Self {
743                    BinarySearch {
744                        lo: 0.0,
745                        curr: start,
746                        hi: start,
747                        allowed,
748                    }
749                }
750
751                /// Creates a new binary searcher which will not produce values
752                /// on the other side of `lo` or `hi` from `start`. `lo` is
753                /// inclusive, `hi` is exclusive.
754                fn new_clamped(lo: $typ, start: $typ, hi: $typ) -> Self {
755                    BinarySearch {
756                        lo: if start.is_sign_negative() {
757                            hi.min(0.0)
758                        } else {
759                            lo.max(0.0)
760                        },
761                        hi: start,
762                        curr: start,
763                        allowed: FloatTypes::all(),
764                    }
765                }
766
767                fn current_allowed(&self) -> bool {
768                    use core::num::FpCategory::*;
769
770                    // Don't reposition if the new value is not allowed
771                    let class_allowed = match self.curr.classify() {
772                        Nan =>
773                        // We don't need to inspect whether the
774                        // signallingness of the NaN matches the allowed
775                        // set, as we never try to switch between them,
776                        // instead shrinking to 0.
777                        {
778                            self.allowed.contains(FloatTypes::QUIET_NAN)
779                                || self
780                                    .allowed
781                                    .contains(FloatTypes::SIGNALING_NAN)
782                        }
783                        Infinite => self.allowed.contains(FloatTypes::INFINITE),
784                        Zero => self.allowed.contains(FloatTypes::ZERO),
785                        Subnormal => {
786                            self.allowed.contains(FloatTypes::SUBNORMAL)
787                        }
788                        Normal => self.allowed.contains(FloatTypes::NORMAL),
789                    };
790                    let signum = self.curr.signum();
791                    let sign_allowed = if signum > 0.0 {
792                        self.allowed.contains(FloatTypes::POSITIVE)
793                    } else if signum < 0.0 {
794                        self.allowed.contains(FloatTypes::NEGATIVE)
795                    } else {
796                        true
797                    };
798
799                    class_allowed && sign_allowed
800                }
801
802                fn ensure_acceptable(&mut self) {
803                    while !self.current_allowed() {
804                        if !self.complicate_once() {
805                            panic!(
806                                "Unable to complicate floating-point back \
807                                 to acceptable value"
808                            );
809                        }
810                    }
811                }
812
813                fn reposition(&mut self) -> bool {
814                    let interval = self.hi - self.lo;
815                    let interval =
816                        if interval.is_finite() { interval } else { 0.0 };
817                    let new_mid = self.lo + interval / 2.0;
818
819                    let new_mid = if new_mid == self.curr || 0.0 == interval {
820                        new_mid
821                    } else {
822                        self.lo
823                    };
824
825                    if new_mid == self.curr {
826                        false
827                    } else {
828                        self.curr = new_mid;
829                        true
830                    }
831                }
832
833                fn done(lo: $typ, hi: $typ) -> bool {
834                    (lo.abs() > hi.abs() && !hi.is_nan()) || lo.is_nan()
835                }
836
837                fn complicate_once(&mut self) -> bool {
838                    if BinarySearch::done(self.lo, self.hi) {
839                        return false;
840                    }
841
842                    self.lo = if self.curr == self.lo {
843                        self.hi
844                    } else {
845                        self.curr
846                    };
847
848                    self.reposition()
849                }
850            }
851            impl ValueTree for BinarySearch {
852                type Value = $typ;
853
854                fn current(&self) -> $typ {
855                    self.curr
856                }
857
858                fn simplify(&mut self) -> bool {
859                    if BinarySearch::done(self.lo, self.hi) {
860                        return false;
861                    }
862
863                    self.hi = self.curr;
864                    if self.reposition() {
865                        self.ensure_acceptable();
866                        true
867                    } else {
868                        false
869                    }
870                }
871
872                fn complicate(&mut self) -> bool {
873                    if self.complicate_once() {
874                        self.ensure_acceptable();
875                        true
876                    } else {
877                        false
878                    }
879                }
880            }
881
882            numeric_api!($typ, $sample_typ, 0.0);
883        }
884    };
885}
886
887float_bin_search!(f32, F32U);
888float_bin_search!(f64, F64U);
889
890#[cfg(test)]
891mod test {
892    use crate::strategy::*;
893    use crate::test_runner::*;
894
895    use super::*;
896
897    #[test]
898    fn u8_inclusive_end_included() {
899        let mut runner = TestRunner::deterministic();
900        let mut ok = 0;
901        for _ in 0..20 {
902            let tree = (0..=1).new_tree(&mut runner).unwrap();
903            let test = runner.run_one(tree, |v| {
904                prop_assert_eq!(v, 1);
905                Ok(())
906            });
907            if test.is_ok() {
908                ok += 1;
909            }
910        }
911        assert!(ok > 1, "inclusive end not included.");
912    }
913
914    #[test]
915    fn u8_inclusive_to_end_included() {
916        let mut runner = TestRunner::deterministic();
917        let mut ok = 0;
918        for _ in 0..20 {
919            let tree = (..=1u8).new_tree(&mut runner).unwrap();
920            let test = runner.run_one(tree, |v| {
921                prop_assert_eq!(v, 1);
922                Ok(())
923            });
924            if test.is_ok() {
925                ok += 1;
926            }
927        }
928        assert!(ok > 1, "inclusive end not included.");
929    }
930
931    #[test]
932    fn i8_binary_search_always_converges() {
933        fn assert_converges<P: Fn(i32) -> bool>(start: i8, pass: P) {
934            let mut state = i8::BinarySearch::new(start);
935            loop {
936                if !pass(state.current() as i32) {
937                    if !state.simplify() {
938                        break;
939                    }
940                } else {
941                    if !state.complicate() {
942                        break;
943                    }
944                }
945            }
946
947            assert!(!pass(state.current() as i32));
948            assert!(
949                pass(state.current() as i32 - 1)
950                    || pass(state.current() as i32 + 1)
951            );
952        }
953
954        for start in -128..0 {
955            for target in start + 1..1 {
956                assert_converges(start as i8, |v| v > target);
957            }
958        }
959
960        for start in 0..128 {
961            for target in 0..start {
962                assert_converges(start as i8, |v| v < target);
963            }
964        }
965    }
966
967    #[test]
968    fn u8_binary_search_always_converges() {
969        fn assert_converges<P: Fn(u32) -> bool>(start: u8, pass: P) {
970            let mut state = u8::BinarySearch::new(start);
971            loop {
972                if !pass(state.current() as u32) {
973                    if !state.simplify() {
974                        break;
975                    }
976                } else {
977                    if !state.complicate() {
978                        break;
979                    }
980                }
981            }
982
983            assert!(!pass(state.current() as u32));
984            assert!(pass(state.current() as u32 - 1));
985        }
986
987        for start in 0..255 {
988            for target in 0..start {
989                assert_converges(start as u8, |v| v <= target);
990            }
991        }
992    }
993
994    #[test]
995    fn signed_integer_range_including_zero_converges_to_zero() {
996        let mut runner = TestRunner::default();
997        for _ in 0..100 {
998            let mut state = (-42i32..64i32).new_tree(&mut runner).unwrap();
999            let init_value = state.current();
1000            assert!(init_value >= -42 && init_value < 64);
1001
1002            while state.simplify() {
1003                let v = state.current();
1004                assert!(v >= -42 && v < 64);
1005            }
1006
1007            assert_eq!(0, state.current());
1008        }
1009    }
1010
1011    #[test]
1012    fn negative_integer_range_stays_in_bounds() {
1013        let mut runner = TestRunner::default();
1014        for _ in 0..100 {
1015            let mut state = (..-42i32).new_tree(&mut runner).unwrap();
1016            let init_value = state.current();
1017            assert!(init_value < -42);
1018
1019            while state.simplify() {
1020                assert!(
1021                    state.current() < -42,
1022                    "Violated bounds: {}",
1023                    state.current()
1024                );
1025            }
1026
1027            assert_eq!(-43, state.current());
1028        }
1029    }
1030
1031    #[test]
1032    fn positive_signed_integer_range_stays_in_bounds() {
1033        let mut runner = TestRunner::default();
1034        for _ in 0..100 {
1035            let mut state = (42i32..).new_tree(&mut runner).unwrap();
1036            let init_value = state.current();
1037            assert!(init_value >= 42);
1038
1039            while state.simplify() {
1040                assert!(
1041                    state.current() >= 42,
1042                    "Violated bounds: {}",
1043                    state.current()
1044                );
1045            }
1046
1047            assert_eq!(42, state.current());
1048        }
1049    }
1050
1051    #[test]
1052    fn unsigned_integer_range_stays_in_bounds() {
1053        let mut runner = TestRunner::default();
1054        for _ in 0..100 {
1055            let mut state = (42u32..56u32).new_tree(&mut runner).unwrap();
1056            let init_value = state.current();
1057            assert!(init_value >= 42 && init_value < 56);
1058
1059            while state.simplify() {
1060                assert!(
1061                    state.current() >= 42,
1062                    "Violated bounds: {}",
1063                    state.current()
1064                );
1065            }
1066
1067            assert_eq!(42, state.current());
1068        }
1069    }
1070
1071    mod contract_sanity {
1072        macro_rules! contract_sanity {
1073            ($t:tt) => {
1074                mod $t {
1075                    use crate::strategy::check_strategy_sanity;
1076
1077                    const FORTY_TWO: $t = 42 as $t;
1078                    const FIFTY_SIX: $t = 56 as $t;
1079
1080                    #[test]
1081                    fn range() {
1082                        check_strategy_sanity(FORTY_TWO..FIFTY_SIX, None);
1083                    }
1084
1085                    #[test]
1086                    fn range_inclusive() {
1087                        check_strategy_sanity(FORTY_TWO..=FIFTY_SIX, None);
1088                    }
1089
1090                    #[test]
1091                    fn range_to() {
1092                        check_strategy_sanity(..FIFTY_SIX, None);
1093                    }
1094
1095                    #[test]
1096                    fn range_to_inclusive() {
1097                        check_strategy_sanity(..=FIFTY_SIX, None);
1098                    }
1099
1100                    #[test]
1101                    fn range_from() {
1102                        check_strategy_sanity(FORTY_TWO.., None);
1103                    }
1104                }
1105            };
1106        }
1107        contract_sanity!(u8);
1108        contract_sanity!(i8);
1109        contract_sanity!(u16);
1110        contract_sanity!(i16);
1111        contract_sanity!(u32);
1112        contract_sanity!(i32);
1113        contract_sanity!(u64);
1114        contract_sanity!(i64);
1115        contract_sanity!(usize);
1116        contract_sanity!(isize);
1117        contract_sanity!(f32);
1118        contract_sanity!(f64);
1119    }
1120
1121    #[test]
1122    fn unsigned_integer_binsearch_simplify_complicate_contract_upheld() {
1123        check_strategy_sanity(0u32..1000u32, None);
1124        check_strategy_sanity(0u32..1u32, None);
1125    }
1126
1127    #[test]
1128    fn signed_integer_binsearch_simplify_complicate_contract_upheld() {
1129        check_strategy_sanity(0i32..1000i32, None);
1130        check_strategy_sanity(0i32..1i32, None);
1131    }
1132
1133    #[test]
1134    fn positive_float_simplifies_to_zero() {
1135        let mut runner = TestRunner::default();
1136        let mut value = (0.0f64..2.0).new_tree(&mut runner).unwrap();
1137
1138        while value.simplify() {}
1139
1140        assert_eq!(0.0, value.current());
1141    }
1142
1143    #[test]
1144    fn positive_float_simplifies_to_base() {
1145        let mut runner = TestRunner::default();
1146        let mut value = (1.0f64..2.0).new_tree(&mut runner).unwrap();
1147
1148        while value.simplify() {}
1149
1150        assert_eq!(1.0, value.current());
1151    }
1152
1153    #[test]
1154    fn negative_float_simplifies_to_zero() {
1155        let mut runner = TestRunner::default();
1156        let mut value = (-2.0f64..0.0).new_tree(&mut runner).unwrap();
1157
1158        while value.simplify() {}
1159
1160        assert_eq!(0.0, value.current());
1161    }
1162
1163    #[test]
1164    fn positive_float_complicates_to_original() {
1165        let mut runner = TestRunner::default();
1166        let mut value = (1.0f64..2.0).new_tree(&mut runner).unwrap();
1167        let orig = value.current();
1168
1169        assert!(value.simplify());
1170        while value.complicate() {}
1171
1172        assert_eq!(orig, value.current());
1173    }
1174
1175    #[test]
1176    fn positive_infinity_simplifies_directly_to_zero() {
1177        let mut value = f64::BinarySearch::new(::std::f64::INFINITY);
1178
1179        assert!(value.simplify());
1180        assert_eq!(0.0, value.current());
1181        assert!(value.complicate());
1182        assert_eq!(::std::f64::INFINITY, value.current());
1183        assert!(!value.clone().complicate());
1184        assert!(!value.clone().simplify());
1185    }
1186
1187    #[test]
1188    fn negative_infinity_simplifies_directly_to_zero() {
1189        let mut value = f64::BinarySearch::new(::std::f64::NEG_INFINITY);
1190
1191        assert!(value.simplify());
1192        assert_eq!(0.0, value.current());
1193        assert!(value.complicate());
1194        assert_eq!(::std::f64::NEG_INFINITY, value.current());
1195        assert!(!value.clone().complicate());
1196        assert!(!value.clone().simplify());
1197    }
1198
1199    #[test]
1200    fn nan_simplifies_directly_to_zero() {
1201        let mut value = f64::BinarySearch::new(::std::f64::NAN);
1202
1203        assert!(value.simplify());
1204        assert_eq!(0.0, value.current());
1205        assert!(value.complicate());
1206        assert!(value.current().is_nan());
1207        assert!(!value.clone().complicate());
1208        assert!(!value.clone().simplify());
1209    }
1210
1211    #[test]
1212    fn float_simplifies_to_smallest_normal() {
1213        let mut runner = TestRunner::default();
1214        let mut value = (::std::f64::MIN_POSITIVE..2.0)
1215            .new_tree(&mut runner)
1216            .unwrap();
1217
1218        while value.simplify() {}
1219
1220        assert_eq!(::std::f64::MIN_POSITIVE, value.current());
1221    }
1222
1223    macro_rules! float_generation_test_body {
1224        ($strategy:ident, $typ:ident) => {
1225            use std::num::FpCategory;
1226
1227            let strategy = $strategy;
1228            let bits = strategy.normal_bits();
1229
1230            let mut seen_positive = 0;
1231            let mut seen_negative = 0;
1232            let mut seen_normal = 0;
1233            let mut seen_subnormal = 0;
1234            let mut seen_zero = 0;
1235            let mut seen_infinite = 0;
1236            let mut seen_quiet_nan = 0;
1237            let mut seen_signaling_nan = 0;
1238            let mut runner = TestRunner::deterministic();
1239
1240            // Check whether this version of Rust honours the NaN payload in
1241            // from_bits
1242            let fidelity_1 = f32::from_bits(0x7F80_0001).to_bits();
1243            let fidelity_2 = f32::from_bits(0xFF80_0001).to_bits();
1244            let nan_fidelity = fidelity_1 != fidelity_2;
1245
1246            for _ in 0..1024 {
1247                let mut tree = strategy.new_tree(&mut runner).unwrap();
1248                let mut increment = 1;
1249
1250                loop {
1251                    let value = tree.current();
1252
1253                    let sign = value.signum(); // So we correctly handle -0
1254                    if sign < 0.0 {
1255                        prop_assert!(bits.contains(FloatTypes::NEGATIVE));
1256                        seen_negative += increment;
1257                    } else if sign > 0.0 {
1258                        // i.e., not NaN
1259                        prop_assert!(bits.contains(FloatTypes::POSITIVE));
1260                        seen_positive += increment;
1261                    }
1262
1263                    match value.classify() {
1264                        FpCategory::Nan if nan_fidelity => {
1265                            let raw = value.to_bits();
1266                            let is_negative = raw << 1 >> 1 != raw;
1267                            if is_negative {
1268                                prop_assert!(
1269                                    bits.contains(FloatTypes::NEGATIVE)
1270                                );
1271                                seen_negative += increment;
1272                            } else {
1273                                prop_assert!(
1274                                    bits.contains(FloatTypes::POSITIVE)
1275                                );
1276                                seen_positive += increment;
1277                            }
1278
1279                            let is_quiet = raw & ($typ::EXP_MASK >> 1)
1280                                == ::std::$typ::NAN.to_bits()
1281                                    & ($typ::EXP_MASK >> 1);
1282                            if is_quiet {
1283                                // x86/AMD64 turn signalling NaNs into quiet
1284                                // NaNs quite aggressively depending on what
1285                                // registers LLVM decides to use to pass the
1286                                // value around, so accept either case here.
1287                                prop_assert!(
1288                                    bits.contains(FloatTypes::QUIET_NAN)
1289                                        || bits.contains(
1290                                            FloatTypes::SIGNALING_NAN
1291                                        )
1292                                );
1293                                seen_quiet_nan += increment;
1294                                seen_signaling_nan += increment;
1295                            } else {
1296                                prop_assert!(
1297                                    bits.contains(FloatTypes::SIGNALING_NAN)
1298                                );
1299                                seen_signaling_nan += increment;
1300                            }
1301                        }
1302
1303                        FpCategory::Nan => {
1304                            // Since safe Rust doesn't currently allow
1305                            // generating any NaN other than one particular
1306                            // payload, don't check the sign or signallingness
1307                            // and consider this to be both signs and
1308                            // signallingness for counting purposes.
1309                            seen_positive += increment;
1310                            seen_negative += increment;
1311                            seen_quiet_nan += increment;
1312                            seen_signaling_nan += increment;
1313                            prop_assert!(
1314                                bits.contains(FloatTypes::QUIET_NAN)
1315                                    || bits.contains(FloatTypes::SIGNALING_NAN)
1316                            );
1317                        }
1318                        FpCategory::Infinite => {
1319                            prop_assert!(bits.contains(FloatTypes::INFINITE));
1320                            seen_infinite += increment;
1321                        }
1322                        FpCategory::Zero => {
1323                            prop_assert!(bits.contains(FloatTypes::ZERO));
1324                            seen_zero += increment;
1325                        }
1326                        FpCategory::Subnormal => {
1327                            prop_assert!(bits.contains(FloatTypes::SUBNORMAL));
1328                            seen_subnormal += increment;
1329                        }
1330                        FpCategory::Normal => {
1331                            prop_assert!(bits.contains(FloatTypes::NORMAL));
1332                            seen_normal += increment;
1333                        }
1334                    }
1335
1336                    // Don't count simplified values towards the counts
1337                    increment = 0;
1338                    if !tree.simplify() {
1339                        break;
1340                    }
1341                }
1342            }
1343
1344            if bits.contains(FloatTypes::POSITIVE) {
1345                prop_assert!(seen_positive > 200);
1346            }
1347            if bits.contains(FloatTypes::NEGATIVE) {
1348                prop_assert!(seen_negative > 200);
1349            }
1350            if bits.contains(FloatTypes::NORMAL) {
1351                prop_assert!(seen_normal > 100);
1352            }
1353            if bits.contains(FloatTypes::SUBNORMAL) {
1354                prop_assert!(seen_subnormal > 5);
1355            }
1356            if bits.contains(FloatTypes::ZERO) {
1357                prop_assert!(seen_zero > 5);
1358            }
1359            if bits.contains(FloatTypes::INFINITE) {
1360                prop_assert!(seen_infinite > 0);
1361            }
1362            if bits.contains(FloatTypes::QUIET_NAN) {
1363                prop_assert!(seen_quiet_nan > 0);
1364            }
1365            if bits.contains(FloatTypes::SIGNALING_NAN) {
1366                prop_assert!(seen_signaling_nan > 0);
1367            }
1368        };
1369    }
1370
1371    proptest! {
1372        #![proptest_config(crate::test_runner::Config::with_cases(1024))]
1373
1374        #[test]
1375        fn f32_any_generates_desired_values(
1376            strategy in crate::bits::u32::ANY.prop_map(f32::Any::from_bits)
1377        ) {
1378            float_generation_test_body!(strategy, f32);
1379        }
1380
1381        #[test]
1382        fn f32_any_sanity(
1383            strategy in crate::bits::u32::ANY.prop_map(f32::Any::from_bits)
1384        ) {
1385            check_strategy_sanity(strategy, Some(CheckStrategySanityOptions {
1386                strict_complicate_after_simplify: false,
1387                .. CheckStrategySanityOptions::default()
1388            }));
1389        }
1390
1391        #[test]
1392        fn f64_any_generates_desired_values(
1393            strategy in crate::bits::u32::ANY.prop_map(f64::Any::from_bits)
1394        ) {
1395            float_generation_test_body!(strategy, f64);
1396        }
1397
1398        #[test]
1399        fn f64_any_sanity(
1400            strategy in crate::bits::u32::ANY.prop_map(f64::Any::from_bits)
1401        ) {
1402            check_strategy_sanity(strategy, Some(CheckStrategySanityOptions {
1403                strict_complicate_after_simplify: false,
1404                .. CheckStrategySanityOptions::default()
1405            }));
1406        }
1407    }
1408
1409    mod panic_on_empty {
1410        macro_rules! panic_on_empty {
1411            ($t:tt) => {
1412                mod $t {
1413                    use crate::strategy::Strategy;
1414                    use crate::test_runner::TestRunner;
1415                    use std::panic;
1416                    use std::string::String;
1417
1418                    const ZERO: $t = 0 as $t;
1419                    const ONE: $t = 1 as $t;
1420
1421                    #[test]
1422                    fn range() {
1423                        assert_eq!(
1424                            panic::catch_unwind(|| {
1425                                let mut runner = TestRunner::deterministic();
1426                                let _ = (ZERO..ZERO).new_tree(&mut runner);
1427                            })
1428                            .err()
1429                            .and_then(|a| a
1430                                .downcast_ref::<String>()
1431                                .map(|s| {
1432                                    s == "Invalid use of empty range 0..0."
1433                                })),
1434                            Some(true)
1435                        );
1436                    }
1437
1438                    #[test]
1439                    fn range_inclusive() {
1440                        assert_eq!(
1441                            panic::catch_unwind(|| {
1442                                let mut runner = TestRunner::deterministic();
1443                                let _ = (ONE..=ZERO).new_tree(&mut runner);
1444                            })
1445                            .err()
1446                            .and_then(|a| a
1447                                .downcast_ref::<String>()
1448                                .map(|s| {
1449                                    s == "Invalid use of empty range 1..=0."
1450                                })),
1451                            Some(true)
1452                        );
1453                    }
1454                }
1455            };
1456        }
1457        panic_on_empty!(u8);
1458        panic_on_empty!(i8);
1459        panic_on_empty!(u16);
1460        panic_on_empty!(i16);
1461        panic_on_empty!(u32);
1462        panic_on_empty!(i32);
1463        panic_on_empty!(u64);
1464        panic_on_empty!(i64);
1465        panic_on_empty!(usize);
1466        panic_on_empty!(isize);
1467        panic_on_empty!(f32);
1468        panic_on_empty!(f64);
1469    }
1470}