diff options
Diffstat (limited to 'vendor/proptest/src/bits.rs')
| -rw-r--r-- | vendor/proptest/src/bits.rs | 677 |
1 files changed, 677 insertions, 0 deletions
diff --git a/vendor/proptest/src/bits.rs b/vendor/proptest/src/bits.rs new file mode 100644 index 000000000..49de83085 --- /dev/null +++ b/vendor/proptest/src/bits.rs @@ -0,0 +1,677 @@ +//- +// Copyright 2017, 2018 The proptest developers +// +// 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 for working with bit sets. +//! +//! Besides `BitSet` itself, this also defines strategies for all the primitive +//! integer types. These strategies are appropriate for integers which are used +//! as bit flags, etc; e.g., where the most reasonable simplification of `64` +//! is `0` (clearing one bit) and not `63` (clearing one bit but setting 6 +//! others). For integers treated as numeric values, see the corresponding +//! modules of the `num` module instead. + +use crate::std_facade::{fmt, Vec}; +use core::marker::PhantomData; +use core::mem; + +#[cfg(feature = "bit-set")] +use bit_set::BitSet; +use rand::{self, seq::IteratorRandom, Rng}; + +use crate::collection::SizeRange; +use crate::num::sample_uniform_incl; +use crate::strategy::*; +use crate::test_runner::*; + +/// Trait for types which can be handled with `BitSetStrategy`. +#[cfg_attr(feature = "cargo-clippy", allow(len_without_is_empty))] +pub trait BitSetLike: Clone + fmt::Debug { + /// Create a new value of `Self` with space for up to `max` bits, all + /// initialised to zero. + fn new_bitset(max: usize) -> Self; + /// Return an upper bound on the greatest bit set _plus one_. + fn len(&self) -> usize; + /// Test whether the given bit is set. + fn test(&self, ix: usize) -> bool; + /// Set the given bit. + fn set(&mut self, ix: usize); + /// Clear the given bit. + fn clear(&mut self, ix: usize); + /// Return the number of bits set. + /// + /// This has a default for backwards compatibility, which simply does a + /// linear scan through the bits. Implementations are strongly encouraged + /// to override this. + fn count(&self) -> usize { + let mut n = 0; + for i in 0..self.len() { + if self.test(i) { + n += 1; + } + } + n + } +} + +macro_rules! int_bitset { + ($typ:ty) => { + impl BitSetLike for $typ { + fn new_bitset(_: usize) -> Self { + 0 + } + fn len(&self) -> usize { + mem::size_of::<$typ>() * 8 + } + fn test(&self, ix: usize) -> bool { + 0 != (*self & ((1 as $typ) << ix)) + } + fn set(&mut self, ix: usize) { + *self |= (1 as $typ) << ix; + } + fn clear(&mut self, ix: usize) { + *self &= !((1 as $typ) << ix); + } + fn count(&self) -> usize { + self.count_ones() as usize + } + } + }; +} +int_bitset!(u8); +int_bitset!(u16); +int_bitset!(u32); +int_bitset!(u64); +int_bitset!(usize); +int_bitset!(i8); +int_bitset!(i16); +int_bitset!(i32); +int_bitset!(i64); +int_bitset!(isize); + +#[cfg(feature = "bit-set")] +impl BitSetLike for BitSet { + fn new_bitset(max: usize) -> Self { + BitSet::with_capacity(max) + } + + fn len(&self) -> usize { + self.capacity() + } + + fn test(&self, bit: usize) -> bool { + self.contains(bit) + } + + fn set(&mut self, bit: usize) { + self.insert(bit); + } + + fn clear(&mut self, bit: usize) { + self.remove(bit); + } + + fn count(&self) -> usize { + self.len() + } +} + +impl BitSetLike for Vec<bool> { + fn new_bitset(max: usize) -> Self { + vec![false; max] + } + + fn len(&self) -> usize { + self.len() + } + + fn test(&self, bit: usize) -> bool { + if bit >= self.len() { + false + } else { + self[bit] + } + } + + fn set(&mut self, bit: usize) { + if bit >= self.len() { + self.resize(bit + 1, false); + } + + self[bit] = true; + } + + fn clear(&mut self, bit: usize) { + if bit < self.len() { + self[bit] = false; + } + } + + fn count(&self) -> usize { + self.iter().filter(|&&b| b).count() + } +} + +/// Generates values as a set of bits between the two bounds. +/// +/// Values are generated by uniformly setting individual bits to 0 +/// or 1 between the bounds. Shrinking iteratively clears bits. +#[must_use = "strategies do nothing unless used"] +#[derive(Clone, Copy, Debug)] +pub struct BitSetStrategy<T: BitSetLike> { + min: usize, + max: usize, + mask: Option<T>, +} + +impl<T: BitSetLike> BitSetStrategy<T> { + /// Create a strategy which generates values where bits between `min` + /// (inclusive) and `max` (exclusive) may be set. + /// + /// Due to the generics, the functions in the typed submodules are usually + /// preferable to calling this directly. + pub fn new(min: usize, max: usize) -> Self { + BitSetStrategy { + min, + max, + mask: None, + } + } + + /// Create a strategy which generates values where any bits set (and only + /// those bits) in `mask` may be set. + pub fn masked(mask: T) -> Self { + BitSetStrategy { + min: 0, + max: mask.len(), + mask: Some(mask), + } + } +} + +impl<T: BitSetLike> Strategy for BitSetStrategy<T> { + type Tree = BitSetValueTree<T>; + type Value = T; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + let mut inner = T::new_bitset(self.max); + for bit in self.min..self.max { + if self.mask.as_ref().map_or(true, |mask| mask.test(bit)) + && runner.rng().gen() + { + inner.set(bit); + } + } + + Ok(BitSetValueTree { + inner, + shrink: self.min, + prev_shrink: None, + min_count: 0, + }) + } +} + +/// Generates bit sets with a particular number of bits set. +/// +/// Specifically, this strategy is given both a size range and a bit range. To +/// produce a new value, it selects a size, then uniformly selects that many +/// bits from within the bit range. +/// +/// Shrinking happens as with [`BitSetStrategy`](struct.BitSetStrategy.html). +#[derive(Clone, Debug)] +#[must_use = "strategies do nothing unless used"] +pub struct SampledBitSetStrategy<T: BitSetLike> { + size: SizeRange, + bits: SizeRange, + _marker: PhantomData<T>, +} + +impl<T: BitSetLike> SampledBitSetStrategy<T> { + /// Create a strategy which generates values where bits within the bounds + /// given by `bits` may be set. The number of bits that are set is chosen + /// to be in the range given by `size`. + /// + /// Due to the generics, the functions in the typed submodules are usually + /// preferable to calling this directly. + /// + /// ## Panics + /// + /// Panics if `size` includes a value that is greater than the number of + /// bits in `bits`. + pub fn new(size: impl Into<SizeRange>, bits: impl Into<SizeRange>) -> Self { + let size = size.into(); + let bits = bits.into(); + size.assert_nonempty(); + + let available_bits = bits.end_excl() - bits.start(); + assert!( + size.end_excl() <= available_bits + 1, + "Illegal SampledBitSetStrategy: have {} bits available, \ + but requested size is {}..{}", + available_bits, + size.start(), + size.end_excl() + ); + SampledBitSetStrategy { + size, + bits, + _marker: PhantomData, + } + } +} + +impl<T: BitSetLike> Strategy for SampledBitSetStrategy<T> { + type Tree = BitSetValueTree<T>; + type Value = T; + + fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { + let mut bits = T::new_bitset(self.bits.end_excl()); + let count = sample_uniform_incl( + runner, + self.size.start(), + self.size.end_incl(), + ); + if bits.len() < count { + panic!("not enough bits to sample"); + } + + for bit in self.bits.iter().choose_multiple(runner.rng(), count) { + bits.set(bit); + } + + Ok(BitSetValueTree { + inner: bits, + shrink: self.bits.start(), + prev_shrink: None, + min_count: self.size.start(), + }) + } +} + +/// Value tree produced by `BitSetStrategy` and `SampledBitSetStrategy`. +#[derive(Clone, Copy, Debug)] +pub struct BitSetValueTree<T: BitSetLike> { + inner: T, + shrink: usize, + prev_shrink: Option<usize>, + min_count: usize, +} + +impl<T: BitSetLike> ValueTree for BitSetValueTree<T> { + type Value = T; + + fn current(&self) -> T { + self.inner.clone() + } + + fn simplify(&mut self) -> bool { + if self.inner.count() <= self.min_count { + return false; + } + + while self.shrink < self.inner.len() && !self.inner.test(self.shrink) { + self.shrink += 1; + } + + if self.shrink >= self.inner.len() { + self.prev_shrink = None; + false + } else { + self.prev_shrink = Some(self.shrink); + self.inner.clear(self.shrink); + self.shrink += 1; + true + } + } + + fn complicate(&mut self) -> bool { + if let Some(bit) = self.prev_shrink.take() { + self.inner.set(bit); + true + } else { + false + } + } +} + +macro_rules! int_api { + ($typ:ident, $max:expr) => { + #[allow(missing_docs)] + pub mod $typ { + use super::*; + + /// Generates integers where all bits may be set. + pub const ANY: BitSetStrategy<$typ> = BitSetStrategy { + min: 0, + max: $max, + mask: None, + }; + + /// Generates values where bits between the given bounds may be + /// set. + pub fn between(min: usize, max: usize) -> BitSetStrategy<$typ> { + BitSetStrategy::new(min, max) + } + + /// Generates values where any bits set in `mask` (and no others) + /// may be set. + pub fn masked(mask: $typ) -> BitSetStrategy<$typ> { + BitSetStrategy::masked(mask) + } + + /// Create a strategy which generates values where bits within the + /// bounds given by `bits` may be set. The number of bits that are + /// set is chosen to be in the range given by `size`. + /// + /// ## Panics + /// + /// Panics if `size` includes a value that is greater than the + /// number of bits in `bits`. + pub fn sampled( + size: impl Into<SizeRange>, + bits: impl Into<SizeRange>, + ) -> SampledBitSetStrategy<$typ> { + SampledBitSetStrategy::new(size, bits) + } + } + }; +} + +int_api!(u8, 8); +int_api!(u16, 16); +int_api!(u32, 32); +int_api!(u64, 64); +int_api!(i8, 8); +int_api!(i16, 16); +int_api!(i32, 32); +int_api!(i64, 64); + +macro_rules! minimal_api { + ($md:ident, $typ:ty) => { + #[allow(missing_docs)] + pub mod $md { + use super::*; + + /// Generates values where bits between the given bounds may be + /// set. + pub fn between(min: usize, max: usize) -> BitSetStrategy<$typ> { + BitSetStrategy::new(min, max) + } + + /// Generates values where any bits set in `mask` (and no others) + /// may be set. + pub fn masked(mask: $typ) -> BitSetStrategy<$typ> { + BitSetStrategy::masked(mask) + } + + /// Create a strategy which generates values where bits within the + /// bounds given by `bits` may be set. The number of bits that are + /// set is chosen to be in the range given by `size`. + /// + /// ## Panics + /// + /// Panics if `size` includes a value that is greater than the + /// number of bits in `bits`. + pub fn sampled( + size: impl Into<SizeRange>, + bits: impl Into<SizeRange>, + ) -> SampledBitSetStrategy<$typ> { + SampledBitSetStrategy::new(size, bits) + } + } + }; +} +minimal_api!(usize, usize); +minimal_api!(isize, isize); +#[cfg(feature = "bit-set")] +minimal_api!(bitset, BitSet); +minimal_api!(bool_vec, Vec<bool>); + +pub(crate) mod varsize { + use super::*; + use core::iter::FromIterator; + + #[cfg(feature = "bit-set")] + type Inner = BitSet; + #[cfg(not(feature = "bit-set"))] + type Inner = Vec<bool>; + + #[derive(Debug, Clone)] + pub(crate) struct VarBitSet(Inner); + + impl VarBitSet { + pub(crate) fn saturated(len: usize) -> Self { + (0..len).collect::<VarBitSet>() + } + + #[cfg(not(feature = "bit-set"))] + pub(crate) fn iter<'a>(&'a self) -> impl Iterator<Item = usize> + 'a { + (0..self.len()).into_iter().filter(move |&ix| self.test(ix)) + } + + #[cfg(feature = "bit-set")] + pub(crate) fn iter<'a>(&'a self) -> impl Iterator<Item = usize> + 'a { + self.0.iter() + } + } + + impl BitSetLike for VarBitSet { + fn new_bitset(max: usize) -> Self { + VarBitSet(Inner::new_bitset(max)) + } + + fn len(&self) -> usize { + BitSetLike::len(&self.0) + } + + fn test(&self, bit: usize) -> bool { + BitSetLike::test(&self.0, bit) + } + + fn set(&mut self, bit: usize) { + BitSetLike::set(&mut self.0, bit); + } + + fn clear(&mut self, bit: usize) { + BitSetLike::clear(&mut self.0, bit); + } + + fn count(&self) -> usize { + BitSetLike::count(&self.0) + } + } + + impl FromIterator<usize> for VarBitSet { + fn from_iter<T: IntoIterator<Item = usize>>(iter: T) -> Self { + let mut bits = VarBitSet::new_bitset(0); + for bit in iter { + bits.set(bit); + } + bits + } + } + + /* + pub(crate) fn between(min: usize, max: usize) -> BitSetStrategy<VarBitSet> { + BitSetStrategy::new(min, max) + } + + pub(crate) fn masked(mask: VarBitSet) -> BitSetStrategy<VarBitSet> { + BitSetStrategy::masked(mask) + } + */ + + pub(crate) fn sampled( + size: impl Into<SizeRange>, + bits: impl Into<SizeRange>, + ) -> SampledBitSetStrategy<VarBitSet> { + SampledBitSetStrategy::new(size, bits) + } +} + +pub(crate) use self::varsize::VarBitSet; + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn generates_values_in_range() { + let input = u32::between(4, 8); + + let mut runner = TestRunner::default(); + for _ in 0..256 { + let value = input.new_tree(&mut runner).unwrap().current(); + assert!(0 == value & !0xF0u32, "Generate value {}", value); + } + } + + #[test] + fn generates_values_in_mask() { + let mut accum = 0; + + let mut runner = TestRunner::deterministic(); + let input = u32::masked(0xdeadbeef); + for _ in 0..1024 { + accum |= input.new_tree(&mut runner).unwrap().current(); + } + + assert_eq!(0xdeadbeef, accum); + } + + #[cfg(feature = "bit-set")] + #[test] + fn mask_bounds_for_bitset_correct() { + let mut seen_0 = false; + let mut seen_2 = false; + + let mut mask = BitSet::new(); + mask.insert(0); + mask.insert(2); + + let mut runner = TestRunner::deterministic(); + let input = bitset::masked(mask); + for _ in 0..32 { + let v = input.new_tree(&mut runner).unwrap().current(); + seen_0 |= v.contains(0); + seen_2 |= v.contains(2); + } + + assert!(seen_0); + assert!(seen_2); + } + + #[test] + fn mask_bounds_for_vecbool_correct() { + let mut seen_0 = false; + let mut seen_2 = false; + + let mask = vec![true, false, true, false]; + + let mut runner = TestRunner::deterministic(); + let input = bool_vec::masked(mask); + for _ in 0..32 { + let v = input.new_tree(&mut runner).unwrap().current(); + assert_eq!(4, v.len()); + seen_0 |= v[0]; + seen_2 |= v[2]; + } + + assert!(seen_0); + assert!(seen_2); + } + + #[test] + fn shrinks_to_zero() { + let input = u32::between(4, 24); + + let mut runner = TestRunner::default(); + for _ in 0..256 { + let mut value = input.new_tree(&mut runner).unwrap(); + let mut prev = value.current(); + while value.simplify() { + let v = value.current(); + assert!( + 1 == (prev & !v).count_ones(), + "Shrank from {} to {}", + prev, + v + ); + prev = v; + } + + assert_eq!(0, value.current()); + } + } + + #[test] + fn complicates_to_previous() { + let input = u32::between(4, 24); + + let mut runner = TestRunner::default(); + for _ in 0..256 { + let mut value = input.new_tree(&mut runner).unwrap(); + let orig = value.current(); + if value.simplify() { + assert!(value.complicate()); + assert_eq!(orig, value.current()); + } + } + } + + #[test] + fn sampled_selects_correct_sizes_and_bits() { + let input = u32::sampled(4..8, 10..20); + let mut seen_counts = [0; 32]; + let mut seen_bits = [0; 32]; + + let mut runner = TestRunner::deterministic(); + for _ in 0..2048 { + let value = input.new_tree(&mut runner).unwrap().current(); + let count = value.count_ones() as usize; + assert!(count >= 4 && count < 8); + seen_counts[count] += 1; + + for bit in 0..32 { + if 0 != value & (1 << bit) { + assert!(bit >= 10 && bit < 20); + seen_bits[bit] += value; + } + } + } + + for i in 4..8 { + assert!(seen_counts[i] >= 256 && seen_counts[i] < 1024); + } + + let least_seen_bit_count = + seen_bits[10..20].iter().cloned().min().unwrap(); + let most_seen_bit_count = + seen_bits[10..20].iter().cloned().max().unwrap(); + assert_eq!(1, most_seen_bit_count / least_seen_bit_count); + } + + #[test] + fn sampled_doesnt_shrink_below_min_size() { + let input = u32::sampled(4..8, 10..20); + + let mut runner = TestRunner::default(); + for _ in 0..256 { + let mut value = input.new_tree(&mut runner).unwrap(); + while value.simplify() {} + + assert_eq!(4, value.current().count_ones()); + } + } + + #[test] + fn test_sanity() { + check_strategy_sanity(u32::masked(0xdeadbeef), None); + } +} |