third_party/rust_crates/vendor/proptest/src/strategy/unions.rs - fuchsia - Git at Google

 //-
 // Copyright 2017 Jason Lingle
 //
 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.

 use core::cmp::{max, min};
 use core::u32;
 use crate::std_facade::Vec;

 #[cfg(not(feature="std"))]
 use num_traits::float::FloatCore;

 use crate::num::sample_uniform;
 use crate::strategy::traits::*;
 use crate::test_runner::*;

 /// A **relative** `weight` of a particular `Strategy` corresponding to `T`
 /// coupled with `T` itself. The weight is currently given in `u32`.
 pub type W<T> = (u32, T);

 /// A `Strategy` which picks from one of several delegate `Stragegy`s.
 ///
 /// See `Strategy::prop_union()`.
 #[derive(Clone, Debug)]
 #[must_use = "strategies do nothing unless used"]
 pub struct Union<T : Strategy> {
     options: Vec<W<T>>,
 }

 impl<T : Strategy> Union<T> {
     /// Create a strategy which selects uniformly from the given delegate
     /// strategies.
     ///
     /// When shrinking, after maximal simplification of the chosen element, the
     /// strategy will move to earlier options and continue simplification with
     /// those.
     ///
     /// ## Panics
     ///
     /// Panics if `options` is empty.
     pub fn new(options: impl IntoIterator<Item = T>) -> Self {
         let options: Vec<W<T>> = options.into_iter()
             .map(|v| (1, v)).collect();
         assert!(!options.is_empty());
         Self { options }
     }

     pub(crate) fn try_new<E>(it: impl Iterator<Item = Result<T, E>>)
                              -> Result<Self, E> {
         let options: Vec<W<T>> = it.map(|r| r.map(|v| (1, v)))
             .collect::<Result<_, _>>()?;

         assert!(!options.is_empty());
         Ok(Self { options })
     }

     /// Create a strategy which selects from the given delegate strategies.
     ///
     /// Each strategy is assigned a non-zero weight which determines how
     /// frequently that strategy is chosen. For example, a strategy with a
     /// weight of 2 will be chosen twice as frequently as one with a weight of
     /// 1\.
     ///
     /// ## Panics
     ///
     /// Panics if `options` is empty or any element has a weight of 0.
     ///
     /// Panics if the sum of the weights overflows a `u32`.
     pub fn new_weighted(options: Vec<W<T>>) -> Self {
         assert!(!options.is_empty());
         assert!(!options.iter().any(|&(w, _)| 0 == w),
                 "Union option has a weight of 0");
         assert!(options.iter().map(|&(w, _)| u64::from(w)).sum::<u64>() <=
                 u64::from(u32::MAX), "Union weights overflow u32");
         Self { options }
     }

     /// Add `other` as an additional alternate strategy with weight 1.
     pub fn or(mut self, other: T) -> Self {
         self.options.push((1, other));
         self
     }
 }

 fn pick_weighted<I : Iterator<Item = u32>>(runner: &mut TestRunner,
                                            weights1: I, weights2: I) -> usize {
     let sum = weights1.map(u64::from).sum();
     let weighted_pick = sample_uniform(runner, 0..sum);
     weights2.scan(0u64, |state, w| {
         *state += u64::from(w);
         Some(*state)
     }).filter(|&v| v <= weighted_pick).count()
 }

 impl<T : Strategy> Strategy for Union<T> {
     type Tree = UnionValueTree<T::Tree>;
     type Value = T::Value;

     fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
         fn extract_weight<V>(&(w, _): &W<V>) -> u32 { w }

         let pick = pick_weighted(
             runner,
             self.options.iter().map(extract_weight::<T>),
             self.options.iter().map(extract_weight::<T>));

         let mut options = Vec::with_capacity(pick);
         for option in &self.options[0..pick+1] {
             options.push(option.1.new_tree(runner)?);
         }

         Ok(UnionValueTree { options, pick, min_pick: 0, prev_pick: None })
     }
 }

 /// `ValueTree` corresponding to `Union`.
 #[derive(Clone, Debug)]
 pub struct UnionValueTree<T : ValueTree> {
     options: Vec<T>,
     pick: usize,
     min_pick: usize,
     prev_pick: Option<usize>,
 }

 macro_rules! access_vec {
     ([$($muta:tt)*] $dst:ident = $this:expr, $ix:expr, $body:block) => {{
         let $dst = &$($muta)* $this.options[$ix];
         $body
     }}
 }

 macro_rules! union_value_tree_body {
     ($typ:ty, $access:ident) => {
         type Value = $typ;

         fn current(&self) -> Self::Value {
             $access!([] opt = self, self.pick, {
                 opt.current()
             })
         }

         fn simplify(&mut self) -> bool {
             if $access!([mut] opt = self, self.pick, { opt.simplify() }) {
                 self.prev_pick = None;
                 true
             } else if self.pick > self.min_pick {
                 self.prev_pick = Some(self.pick);
                 self.pick -= 1;
                 true
             } else {
                 false
             }
         }

         fn complicate(&mut self) -> bool {
             if let Some(pick) = self.prev_pick {
                 self.pick = pick;
                 self.min_pick = pick;
                 self.prev_pick = None;
                 true
             } else {
                 $access!([mut] opt = self, self.pick, { opt.complicate() })
             }
         }
     }
 }

 impl<T : ValueTree> ValueTree for UnionValueTree<T> {
     union_value_tree_body!(T::Value, access_vec);
 }

 macro_rules! def_access_tuple {
     ($b:tt $name:ident, $($n:tt)*) => {
         macro_rules! $name {
             ([$b($b muta:tt)*] $b dst:ident = $b this:expr,
              $b ix:expr, $b body:block) => {
                 match $b ix {
                     0 => {
                         let $b dst = &$b($b muta)* $b this.options.0;
                         $b body
                     },
                     $(
                         $n => {
                             if let Some(ref $b($b muta)* $b dst) =
                                 $b this.options.$n
                             {
                                 $b body
                             } else {
                                 panic!("TupleUnion tried to access \
                                         uninitialised slot {}", $n)
                             }
                         },
                     )*
                     _ => panic!("TupleUnion tried to access out-of-range \
                                  slot {}", $b ix),
                 }
             }
         }
     }
 }

 def_access_tuple!($ access_tuple2, 1);
 def_access_tuple!($ access_tuple3, 1 2);
 def_access_tuple!($ access_tuple4, 1 2 3);
 def_access_tuple!($ access_tuple5, 1 2 3 4);
 def_access_tuple!($ access_tuple6, 1 2 3 4 5);
 def_access_tuple!($ access_tuple7, 1 2 3 4 5 6);
 def_access_tuple!($ access_tuple8, 1 2 3 4 5 6 7);
 def_access_tuple!($ access_tuple9, 1 2 3 4 5 6 7 8);
 def_access_tuple!($ access_tupleA, 1 2 3 4 5 6 7 8 9);

 /// Similar to `Union`, but internally uses a tuple to hold the strategies.
 ///
 /// This allows better performance than vanilla `Union` since one does not need
 /// to resort to boxing and dynamic dispatch to handle heterogeneous
 /// strategies.
 #[must_use = "strategies do nothing unless used"]
 #[derive(Clone, Copy, Debug)]
 pub struct TupleUnion<T>(T);

 impl<T> TupleUnion<T> {
     /// Wrap `tuple` in a `TupleUnion`.
     ///
     /// The struct definition allows any `T` for `tuple`, but to be useful, it
     /// must be a 2- to 10-tuple of `(u32, impl Strategy)` pairs where all
     /// strategies ultimately produce the same value. Each `u32` indicates the
     /// relative weight of its corresponding strategy.
     /// You may use `W<S>` as an alias for `(u32, S)`.
     ///
     /// Using this constructor directly is discouraged; prefer to use
     /// `prop_oneof!` since it is generally clearer.
     pub fn new(tuple: T) -> Self {
         TupleUnion(tuple)
     }
 }

 macro_rules! tuple_union {
     ($($gen:ident $ix:tt)*) => {
         impl<A : Strategy, $($gen: Strategy<Value = A::Value>),*>
         Strategy for TupleUnion<(W<A>, $(W<$gen>),*)> {
             type Tree = TupleUnionValueTree<
                 (A::Tree, $(Option<$gen::Tree>),*)>;
             type Value = A::Value;

             fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
                 let weights = [((self.0).0).0, $(((self.0).$ix).0),*];
                 let pick = pick_weighted(runner, weights.iter().cloned(),
                                          weights.iter().cloned());

                 Ok(TupleUnionValueTree {
                     options: (
                         ((self.0).0).1.new_tree(runner)?,
                         $(if $ix <= pick {
                             Some(((self.0).$ix).1.new_tree(runner)?)
                         } else {
                             None
                         }),*),
                     pick: pick,
                     min_pick: 0,
                     prev_pick: None,
                 })
             }
         }
     }
 }

 tuple_union!(B 1);
 tuple_union!(B 1 C 2);
 tuple_union!(B 1 C 2 D 3);
 tuple_union!(B 1 C 2 D 3 E 4);
 tuple_union!(B 1 C 2 D 3 E 4 F 5);
 tuple_union!(B 1 C 2 D 3 E 4 F 5 G 6);
 tuple_union!(B 1 C 2 D 3 E 4 F 5 G 6 H 7);
 tuple_union!(B 1 C 2 D 3 E 4 F 5 G 6 H 7 I 8);
 tuple_union!(B 1 C 2 D 3 E 4 F 5 G 6 H 7 I 8 J 9);

 /// `ValueTree` type produced by `TupleUnion`.
 #[derive(Clone, Copy, Debug)]
 pub struct TupleUnionValueTree<T> {
     options: T,
     pick: usize,
     min_pick: usize,
     prev_pick: Option<usize>,
 }

 macro_rules! value_tree_tuple {
     ($access:ident, $($gen:ident)*) => {
         impl<A : ValueTree, $($gen: ValueTree<Value = A::Value>),*> ValueTree
         for TupleUnionValueTree<(A, $(Option<$gen>),*)> {
             union_value_tree_body!(A::Value, $access);
         }
     }
 }

 value_tree_tuple!(access_tuple2, B);
 value_tree_tuple!(access_tuple3, B C);
 value_tree_tuple!(access_tuple4, B C D);
 value_tree_tuple!(access_tuple5, B C D E);
 value_tree_tuple!(access_tuple6, B C D E F);
 value_tree_tuple!(access_tuple7, B C D E F G);
 value_tree_tuple!(access_tuple8, B C D E F G H);
 value_tree_tuple!(access_tuple9, B C D E F G H I);
 value_tree_tuple!(access_tupleA, B C D E F G H I J);

 const WEIGHT_BASE: u32 = 0x8000_0000;

 /// Convert a floating-point weight in the range (0.0,1.0) to a pair of weights
 /// that can be used with `Union` and similar.
 ///
 /// The first return value is the weight corresponding to `f`; the second
 /// return value is the weight corresponding to `1.0 - f`.
 ///
 /// This call does not make any guarantees as to what range of weights it may
 /// produce, except that adding the two return values will never overflow a
 /// `u32`. As such, it is generally not meaningful to combine any other weights
 /// with the two returned.
 ///
 /// ## Panics
 ///
 /// Panics if `f` is not a real number between 0.0 and 1.0, both exclusive.
 pub fn float_to_weight(f: f64) -> (u32, u32) {
     assert!(f > 0.0 && f < 1.0, "Invalid probability: {}", f);

     // Clamp to 1..WEIGHT_BASE-1 so that we never produce a weight of 0.
     let pos = max(1, min(WEIGHT_BASE - 1,
                          (f * f64::from(WEIGHT_BASE)).round() as u32));
     let neg = WEIGHT_BASE - pos;

     (pos, neg)
 }

 #[cfg(test)]
 mod test {
     use crate::strategy::just::Just;
     use super::*;

     // FIXME(2018-06-01): figure out a way to run this test on no_std.
     // The problem is that the default seed is fixed and does not produce
     // enough passed tests. We need some universal source of non-determinism
     // for the seed, which is unlikely.
     #[cfg(feature = "std")]
     #[test]
     fn test_union() {
         let input = (10u32..20u32).prop_union(30u32..40u32);
         // Expect that 25% of cases pass (left input happens to be < 15, and
         // left is chosen as initial value). Of the 75% that fail, 50% should
         // converge to 15 and 50% to 30 (the latter because the left is beneath
         // the passing threshold).
         let mut passed = 0;
         let mut converged_low = 0;
         let mut converged_high = 0;
         let mut runner = TestRunner::deterministic();
         for _ in 0..256 {
             let case = input.new_tree(&mut runner).unwrap();
             let result = runner.run_one(case, |v| {
                 prop_assert!(v < 15);
                 Ok(())
             });

             match result {
                 Ok(true) => passed += 1,
                 Err(TestError::Fail(_, 15)) => converged_low += 1,
                 Err(TestError::Fail(_, 30)) => converged_high += 1,
                 e => panic!("Unexpected result: {:?}", e),
             }
         }

         assert!(passed >= 32 && passed <= 96,
                 "Bad passed count: {}", passed);
         assert!(converged_low >= 32 && converged_low <= 160,
                 "Bad converged_low count: {}", converged_low);
         assert!(converged_high >= 32 && converged_high <= 160,
                 "Bad converged_high count: {}", converged_high);
     }

     #[test]
     fn test_union_weighted() {
         let input = Union::new_weighted(vec![
             (1, Just(0usize)),
             (2, Just(1usize)),
             (1, Just(2usize)),
         ]);

         let mut counts = [0, 0, 0];
         let mut runner = TestRunner::deterministic();
         for _ in 0..65536 {
             counts[input.new_tree(&mut runner).unwrap().current()] += 1;
         }

         println!("{:?}", counts);
         assert!(counts[0] > 0);
         assert!(counts[2] > 0);
         assert!(counts[1] > counts[0] * 3/2);
         assert!(counts[1] > counts[2] * 3/2);
     }

     #[test]
     fn test_union_sanity() {
         check_strategy_sanity(Union::new_weighted(vec![
             (1, 0i32..100),
             (2, 200i32..300),
             (1, 400i32..500),
         ]), None);
     }

     // FIXME(2018-06-01): See note on `test_union`.
     #[cfg(feature = "std")]
     #[test]
     fn test_tuple_union() {
         let input = TupleUnion::new(
             ((1, 10u32..20u32),
              (1, 30u32..40u32)));
         // Expect that 25% of cases pass (left input happens to be < 15, and
         // left is chosen as initial value). Of the 75% that fail, 50% should
         // converge to 15 and 50% to 30 (the latter because the left is beneath
         // the passing threshold).
         let mut passed = 0;
         let mut converged_low = 0;
         let mut converged_high = 0;
         let mut runner = TestRunner::deterministic();
         for _ in 0..256 {
             let case = input.new_tree(&mut runner).unwrap();
             let result = runner.run_one(case, |v| {
                 prop_assert!(v < 15);
                 Ok(())
             });

             match result {
                 Ok(true) => passed += 1,
                 Err(TestError::Fail(_, 15)) => converged_low += 1,
                 Err(TestError::Fail(_, 30)) => converged_high += 1,
                 e => panic!("Unexpected result: {:?}", e),
             }
         }

         assert!(passed >= 32 && passed <= 96,
                 "Bad passed count: {}", passed);
         assert!(converged_low >= 32 && converged_low <= 160,
                 "Bad converged_low count: {}", converged_low);
         assert!(converged_high >= 32 && converged_high <= 160,
                 "Bad converged_high count: {}", converged_high);
     }

     #[test]
     fn test_tuple_union_weighting() {
         let input = TupleUnion::new((
             (1, Just(0usize)),
             (2, Just(1usize)),
             (1, Just(2usize)),
         ));

         let mut counts = [0, 0, 0];
         let mut runner = TestRunner::deterministic();
         for _ in 0..65536 {
             counts[input.new_tree(&mut runner).unwrap().current()] += 1;
         }

         println!("{:?}", counts);
         assert!(counts[0] > 0);
         assert!(counts[2] > 0);
         assert!(counts[1] > counts[0] * 3/2);
         assert!(counts[1] > counts[2] * 3/2);
     }

     #[test]
     fn test_tuple_union_all_sizes() {
         let mut runner = TestRunner::deterministic();
         let r = 1i32..10;

         macro_rules! test {
             ($($part:expr),*) => {{
                 let input = TupleUnion::new((
                     $((1, $part.clone())),*,
                     (1, Just(0i32))
                 ));

                 let mut pass = false;
                 for _ in 0..1024 {
                     if 0 == input.new_tree(&mut runner).unwrap().current() {
                         pass = true;
                         break;
                     }
                 }

                 assert!(pass);
             }}
         }

         test!(r); // 2
         test!(r, r); // 3
         test!(r, r, r); // 4
         test!(r, r, r, r); // 5
         test!(r, r, r, r, r); // 6
         test!(r, r, r, r, r, r); // 7
         test!(r, r, r, r, r, r, r); // 8
         test!(r, r, r, r, r, r, r, r); // 9
         test!(r, r, r, r, r, r, r, r, r); // 10
     }

     #[test]
     fn test_tuple_union_sanity() {
         check_strategy_sanity(
             TupleUnion::new(((1, 0i32..100i32), (1, 200i32..1000i32),
                              (1, 2000i32..3000i32))),
             None);
     }
 }
	//-
	// Copyright 2017 Jason Lingle
	//
	// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
	// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
	// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
	// option. This file may not be copied, modified, or distributed
	// except according to those terms.

	use core::cmp::{max, min};
	use core::u32;
	use crate::std_facade::Vec;

	#[cfg(not(feature="std"))]
	use num_traits::float::FloatCore;

	use crate::num::sample_uniform;
	use crate::strategy::traits::*;
	use crate::test_runner::*;

	/// A relative `weight` of a particular `Strategy` corresponding to `T`
	/// coupled with `T` itself. The weight is currently given in `u32`.
	pub type W<T> = (u32, T);

	/// A `Strategy` which picks from one of several delegate `Stragegy`s.
	///
	/// See `Strategy::prop_union()`.
	#[derive(Clone, Debug)]
	#[must_use = "strategies do nothing unless used"]
	pub struct Union<T : Strategy> {
	options: Vec<W<T>>,
	}

	impl<T : Strategy> Union<T> {
	/// Create a strategy which selects uniformly from the given delegate
	/// strategies.
	///
	/// When shrinking, after maximal simplification of the chosen element, the
	/// strategy will move to earlier options and continue simplification with
	/// those.
	///
	/// ## Panics
	///
	/// Panics if `options` is empty.
	pub fn new(options: impl IntoIterator<Item = T>) -> Self {
	let options: Vec<W<T>> = options.into_iter()
	.map(\|v\| (1, v)).collect();
	assert!(!options.is_empty());
	Self { options }
	}

	pub(crate) fn try_new<E>(it: impl Iterator<Item = Result<T, E>>)
	-> Result<Self, E> {
	let options: Vec<W<T>> = it.map(\|r\| r.map(\|v\| (1, v)))
	.collect::<Result<_, _>>()?;

	assert!(!options.is_empty());
	Ok(Self { options })
	}

	/// Create a strategy which selects from the given delegate strategies.
	///
	/// Each strategy is assigned a non-zero weight which determines how
	/// frequently that strategy is chosen. For example, a strategy with a
	/// weight of 2 will be chosen twice as frequently as one with a weight of
	/// 1\.
	///
	/// ## Panics
	///
	/// Panics if `options` is empty or any element has a weight of 0.
	///
	/// Panics if the sum of the weights overflows a `u32`.
	pub fn new_weighted(options: Vec<W<T>>) -> Self {
	assert!(!options.is_empty());
	assert!(!options.iter().any(\|&(w, _)\| 0 == w),
	"Union option has a weight of 0");
	assert!(options.iter().map(\|&(w, _)\| u64::from(w)).sum::<u64>() <=
	u64::from(u32::MAX), "Union weights overflow u32");
	Self { options }
	}

	/// Add `other` as an additional alternate strategy with weight 1.
	pub fn or(mut self, other: T) -> Self {
	self.options.push((1, other));
	self
	}
	}

	fn pick_weighted<I : Iterator<Item = u32>>(runner: &mut TestRunner,
	weights1: I, weights2: I) -> usize {
	let sum = weights1.map(u64::from).sum();
	let weighted_pick = sample_uniform(runner, 0..sum);
	weights2.scan(0u64, \|state, w\| {
	*state += u64::from(w);
	Some(*state)
	}).filter(\|&v\| v <= weighted_pick).count()
	}

	impl<T : Strategy> Strategy for Union<T> {
	type Tree = UnionValueTree<T::Tree>;
	type Value = T::Value;

	fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
	fn extract_weight<V>(&(w, _): &W<V>) -> u32 { w }

	let pick = pick_weighted(
	runner,
	self.options.iter().map(extract_weight::<T>),
	self.options.iter().map(extract_weight::<T>));

	let mut options = Vec::with_capacity(pick);
	for option in &self.options[0..pick+1] {
	options.push(option.1.new_tree(runner)?);
	}

	Ok(UnionValueTree { options, pick, min_pick: 0, prev_pick: None })
	}
	}

	/// `ValueTree` corresponding to `Union`.
	#[derive(Clone, Debug)]
	pub struct UnionValueTree<T : ValueTree> {
	options: Vec<T>,
	pick: usize,
	min_pick: usize,
	prev_pick: Option<usize>,
	}

	macro_rules! access_vec {
	([$($muta:tt)*] $dst:ident = $this:expr, $ix:expr, $body:block) => {{
	let $dst = &$($muta)* $this.options[$ix];
	$body
	}}
	}

	macro_rules! union_value_tree_body {
	($typ:ty, $access:ident) => {
	type Value = $typ;

	fn current(&self) -> Self::Value {
	$access!([] opt = self, self.pick, {
	opt.current()
	})
	}

	fn simplify(&mut self) -> bool {
	if $access!([mut] opt = self, self.pick, { opt.simplify() }) {
	self.prev_pick = None;
	true
	} else if self.pick > self.min_pick {
	self.prev_pick = Some(self.pick);
	self.pick -= 1;
	true
	} else {
	false
	}
	}

	fn complicate(&mut self) -> bool {
	if let Some(pick) = self.prev_pick {
	self.pick = pick;
	self.min_pick = pick;
	self.prev_pick = None;
	true
	} else {
	$access!([mut] opt = self, self.pick, { opt.complicate() })
	}
	}
	}
	}

	impl<T : ValueTree> ValueTree for UnionValueTree<T> {
	union_value_tree_body!(T::Value, access_vec);
	}

	macro_rules! def_access_tuple {
	($b:tt $name:ident, $($n:tt)*) => {
	macro_rules! $name {
	([$b($b muta:tt)*] $b dst:ident = $b this:expr,
	$b ix:expr, $b body:block) => {
	match $b ix {
	0 => {
	let $b dst = &$b($b muta)* $b this.options.0;
	$b body
	},
	$(
	$n => {
	if let Some(ref $b($b muta)* $b dst) =
	$b this.options.$n
	{
	$b body
	} else {
	panic!("TupleUnion tried to access \
	uninitialised slot {}", $n)
	}
	},
	)*
	_ => panic!("TupleUnion tried to access out-of-range \
	slot {}", $b ix),
	}
	}
	}
	}
	}

	def_access_tuple!($ access_tuple2, 1);
	def_access_tuple!($ access_tuple3, 1 2);
	def_access_tuple!($ access_tuple4, 1 2 3);
	def_access_tuple!($ access_tuple5, 1 2 3 4);
	def_access_tuple!($ access_tuple6, 1 2 3 4 5);
	def_access_tuple!($ access_tuple7, 1 2 3 4 5 6);
	def_access_tuple!($ access_tuple8, 1 2 3 4 5 6 7);
	def_access_tuple!($ access_tuple9, 1 2 3 4 5 6 7 8);
	def_access_tuple!($ access_tupleA, 1 2 3 4 5 6 7 8 9);

	/// Similar to `Union`, but internally uses a tuple to hold the strategies.
	///
	/// This allows better performance than vanilla `Union` since one does not need
	/// to resort to boxing and dynamic dispatch to handle heterogeneous
	/// strategies.
	#[must_use = "strategies do nothing unless used"]
	#[derive(Clone, Copy, Debug)]
	pub struct TupleUnion<T>(T);

	impl<T> TupleUnion<T> {
	/// Wrap `tuple` in a `TupleUnion`.
	///
	/// The struct definition allows any `T` for `tuple`, but to be useful, it
	/// must be a 2- to 10-tuple of `(u32, impl Strategy)` pairs where all
	/// strategies ultimately produce the same value. Each `u32` indicates the
	/// relative weight of its corresponding strategy.
	/// You may use `W<S>` as an alias for `(u32, S)`.
	///
	/// Using this constructor directly is discouraged; prefer to use
	/// `prop_oneof!` since it is generally clearer.
	pub fn new(tuple: T) -> Self {
	TupleUnion(tuple)
	}
	}

	macro_rules! tuple_union {
	($($gen:ident $ix:tt)*) => {
	impl<A : Strategy, $($gen: Strategy<Value = A::Value>),*>
	Strategy for TupleUnion<(W<A>, $(W<$gen>),*)> {
	type Tree = TupleUnionValueTree<
	(A::Tree, $(Option<$gen::Tree>),*)>;
	type Value = A::Value;

	fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
	let weights = [((self.0).0).0, $(((self.0).$ix).0),*];
	let pick = pick_weighted(runner, weights.iter().cloned(),
	weights.iter().cloned());

	Ok(TupleUnionValueTree {
	options: (
	((self.0).0).1.new_tree(runner)?,
	$(if $ix <= pick {
	Some(((self.0).$ix).1.new_tree(runner)?)
	} else {
	None
	}),*),
	pick: pick,
	min_pick: 0,
	prev_pick: None,
	})
	}
	}
	}
	}

	tuple_union!(B 1);
	tuple_union!(B 1 C 2);
	tuple_union!(B 1 C 2 D 3);
	tuple_union!(B 1 C 2 D 3 E 4);
	tuple_union!(B 1 C 2 D 3 E 4 F 5);
	tuple_union!(B 1 C 2 D 3 E 4 F 5 G 6);
	tuple_union!(B 1 C 2 D 3 E 4 F 5 G 6 H 7);
	tuple_union!(B 1 C 2 D 3 E 4 F 5 G 6 H 7 I 8);
	tuple_union!(B 1 C 2 D 3 E 4 F 5 G 6 H 7 I 8 J 9);

	/// `ValueTree` type produced by `TupleUnion`.
	#[derive(Clone, Copy, Debug)]
	pub struct TupleUnionValueTree<T> {
	options: T,
	pick: usize,
	min_pick: usize,
	prev_pick: Option<usize>,
	}

	macro_rules! value_tree_tuple {
	($access:ident, $($gen:ident)*) => {
	impl<A : ValueTree, $($gen: ValueTree<Value = A::Value>),*> ValueTree
	for TupleUnionValueTree<(A, $(Option<$gen>),*)> {
	union_value_tree_body!(A::Value, $access);
	}
	}
	}

	value_tree_tuple!(access_tuple2, B);
	value_tree_tuple!(access_tuple3, B C);
	value_tree_tuple!(access_tuple4, B C D);
	value_tree_tuple!(access_tuple5, B C D E);
	value_tree_tuple!(access_tuple6, B C D E F);
	value_tree_tuple!(access_tuple7, B C D E F G);
	value_tree_tuple!(access_tuple8, B C D E F G H);
	value_tree_tuple!(access_tuple9, B C D E F G H I);
	value_tree_tuple!(access_tupleA, B C D E F G H I J);

	const WEIGHT_BASE: u32 = 0x8000_0000;

	/// Convert a floating-point weight in the range (0.0,1.0) to a pair of weights
	/// that can be used with `Union` and similar.
	///
	/// The first return value is the weight corresponding to `f`; the second
	/// return value is the weight corresponding to `1.0 - f`.
	///
	/// This call does not make any guarantees as to what range of weights it may
	/// produce, except that adding the two return values will never overflow a
	/// `u32`. As such, it is generally not meaningful to combine any other weights
	/// with the two returned.
	///
	/// ## Panics
	///
	/// Panics if `f` is not a real number between 0.0 and 1.0, both exclusive.
	pub fn float_to_weight(f: f64) -> (u32, u32) {
	assert!(f > 0.0 && f < 1.0, "Invalid probability: {}", f);

	// Clamp to 1..WEIGHT_BASE-1 so that we never produce a weight of 0.
	let pos = max(1, min(WEIGHT_BASE - 1,
	(f * f64::from(WEIGHT_BASE)).round() as u32));
	let neg = WEIGHT_BASE - pos;

	(pos, neg)
	}

	#[cfg(test)]
	mod test {
	use crate::strategy::just::Just;
	use super::*;

	// FIXME(2018-06-01): figure out a way to run this test on no_std.
	// The problem is that the default seed is fixed and does not produce
	// enough passed tests. We need some universal source of non-determinism
	// for the seed, which is unlikely.
	#[cfg(feature = "std")]
	#[test]
	fn test_union() {
	let input = (10u32..20u32).prop_union(30u32..40u32);
	// Expect that 25% of cases pass (left input happens to be < 15, and
	// left is chosen as initial value). Of the 75% that fail, 50% should
	// converge to 15 and 50% to 30 (the latter because the left is beneath
	// the passing threshold).
	let mut passed = 0;
	let mut converged_low = 0;
	let mut converged_high = 0;
	let mut runner = TestRunner::deterministic();
	for _ in 0..256 {
	let case = input.new_tree(&mut runner).unwrap();
	let result = runner.run_one(case, \|v\| {
	prop_assert!(v < 15);
	Ok(())
	});

	match result {
	Ok(true) => passed += 1,
	Err(TestError::Fail(_, 15)) => converged_low += 1,
	Err(TestError::Fail(_, 30)) => converged_high += 1,
	e => panic!("Unexpected result: {:?}", e),
	}
	}

	assert!(passed >= 32 && passed <= 96,
	"Bad passed count: {}", passed);
	assert!(converged_low >= 32 && converged_low <= 160,
	"Bad converged_low count: {}", converged_low);
	assert!(converged_high >= 32 && converged_high <= 160,
	"Bad converged_high count: {}", converged_high);
	}

	#[test]
	fn test_union_weighted() {
	let input = Union::new_weighted(vec![
	(1, Just(0usize)),
	(2, Just(1usize)),
	(1, Just(2usize)),
	]);

	let mut counts = [0, 0, 0];
	let mut runner = TestRunner::deterministic();
	for _ in 0..65536 {
	counts[input.new_tree(&mut runner).unwrap().current()] += 1;
	}

	println!("{:?}", counts);
	assert!(counts[0] > 0);
	assert!(counts[2] > 0);
	assert!(counts[1] > counts[0] * 3/2);
	assert!(counts[1] > counts[2] * 3/2);
	}

	#[test]
	fn test_union_sanity() {
	check_strategy_sanity(Union::new_weighted(vec![
	(1, 0i32..100),
	(2, 200i32..300),
	(1, 400i32..500),
	]), None);
	}

	// FIXME(2018-06-01): See note on `test_union`.
	#[cfg(feature = "std")]
	#[test]
	fn test_tuple_union() {
	let input = TupleUnion::new(
	((1, 10u32..20u32),
	(1, 30u32..40u32)));
	// Expect that 25% of cases pass (left input happens to be < 15, and
	// left is chosen as initial value). Of the 75% that fail, 50% should
	// converge to 15 and 50% to 30 (the latter because the left is beneath
	// the passing threshold).
	let mut passed = 0;
	let mut converged_low = 0;
	let mut converged_high = 0;
	let mut runner = TestRunner::deterministic();
	for _ in 0..256 {
	let case = input.new_tree(&mut runner).unwrap();
	let result = runner.run_one(case, \|v\| {
	prop_assert!(v < 15);
	Ok(())
	});

	match result {
	Ok(true) => passed += 1,
	Err(TestError::Fail(_, 15)) => converged_low += 1,
	Err(TestError::Fail(_, 30)) => converged_high += 1,
	e => panic!("Unexpected result: {:?}", e),
	}
	}

	assert!(passed >= 32 && passed <= 96,
	"Bad passed count: {}", passed);
	assert!(converged_low >= 32 && converged_low <= 160,
	"Bad converged_low count: {}", converged_low);
	assert!(converged_high >= 32 && converged_high <= 160,
	"Bad converged_high count: {}", converged_high);
	}

	#[test]
	fn test_tuple_union_weighting() {
	let input = TupleUnion::new((
	(1, Just(0usize)),
	(2, Just(1usize)),
	(1, Just(2usize)),
	));

	let mut counts = [0, 0, 0];
	let mut runner = TestRunner::deterministic();
	for _ in 0..65536 {
	counts[input.new_tree(&mut runner).unwrap().current()] += 1;
	}

	println!("{:?}", counts);
	assert!(counts[0] > 0);
	assert!(counts[2] > 0);
	assert!(counts[1] > counts[0] * 3/2);
	assert!(counts[1] > counts[2] * 3/2);
	}

	#[test]
	fn test_tuple_union_all_sizes() {
	let mut runner = TestRunner::deterministic();
	let r = 1i32..10;

	macro_rules! test {
	($($part:expr),*) => {{
	let input = TupleUnion::new((
	$((1, $part.clone())),*,
	(1, Just(0i32))
	));

	let mut pass = false;
	for _ in 0..1024 {
	if 0 == input.new_tree(&mut runner).unwrap().current() {
	pass = true;
	break;
	}
	}

	assert!(pass);
	}}
	}

	test!(r); // 2
	test!(r, r); // 3
	test!(r, r, r); // 4
	test!(r, r, r, r); // 5
	test!(r, r, r, r, r); // 6
	test!(r, r, r, r, r, r); // 7
	test!(r, r, r, r, r, r, r); // 8
	test!(r, r, r, r, r, r, r, r); // 9
	test!(r, r, r, r, r, r, r, r, r); // 10
	}

	#[test]
	fn test_tuple_union_sanity() {
	check_strategy_sanity(
	TupleUnion::new(((1, 0i32..100i32), (1, 200i32..1000i32),
	(1, 2000i32..3000i32))),
	None);
	}
	}