vendor/proptest-1.0.0/src/bits.rs - toolchain/rustc - Git at Google

 //-
 // 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);
     }
 }
	//-
	// 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);
	}
	}