Merging upstream version 1.71.1+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

13 files changed, 4114 insertions, 0 deletions

diff --git a/vendor/proptest/src/strategy/filter.rs b/vendor/proptest/src/strategy/filter.rs
new file mode 100644
index 000000000..029dbcebc
--- /dev/null
+++ b/vendor/proptest/src/strategy/filter.rs
@@ -0,0 +1,147 @@
+//-
+// 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 crate::std_facade::{fmt, Arc};
+
+use crate::strategy::traits::*;
+use crate::test_runner::*;
+
+/// `Strategy` and `ValueTree` filter adaptor.
+///
+/// See `Strategy::prop_filter()`.
+#[must_use = "strategies do nothing unless used"]
+pub struct Filter<S, F> {
+    pub(super) source: S,
+    pub(super) whence: Reason,
+    pub(super) fun: Arc<F>,
+}
+
+impl<S, F> Filter<S, F> {
+    pub(super) fn new(source: S, whence: Reason, fun: F) -> Self {
+        Self {
+            source,
+            whence,
+            fun: Arc::new(fun),
+        }
+    }
+}
+
+impl<S: fmt::Debug, F> fmt::Debug for Filter<S, F> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("Filter")
+            .field("source", &self.source)
+            .field("whence", &self.whence)
+            .field("fun", &"<function>")
+            .finish()
+    }
+}
+
+impl<S: Clone, F> Clone for Filter<S, F> {
+    fn clone(&self) -> Self {
+        Filter {
+            source: self.source.clone(),
+            whence: "unused".into(),
+            fun: Arc::clone(&self.fun),
+        }
+    }
+}
+
+impl<S: Strategy, F: Fn(&S::Value) -> bool> Strategy for Filter<S, F> {
+    type Tree = Filter<S::Tree, F>;
+    type Value = S::Value;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        loop {
+            let val = self.source.new_tree(runner)?;
+            if !(self.fun)(&val.current()) {
+                runner.reject_local(self.whence.clone())?;
+            } else {
+                return Ok(Filter {
+                    source: val,
+                    whence: self.whence.clone(),
+                    fun: Arc::clone(&self.fun),
+                });
+            }
+        }
+    }
+}
+
+impl<S: ValueTree, F: Fn(&S::Value) -> bool> Filter<S, F> {
+    fn ensure_acceptable(&mut self) {
+        while !(self.fun)(&self.source.current()) {
+            if !self.source.complicate() {
+                panic!(
+                    "Unable to complicate filtered strategy \
+                     back into acceptable value"
+                );
+            }
+        }
+    }
+}
+
+impl<S: ValueTree, F: Fn(&S::Value) -> bool> ValueTree for Filter<S, F> {
+    type Value = S::Value;
+
+    fn current(&self) -> S::Value {
+        self.source.current()
+    }
+
+    fn simplify(&mut self) -> bool {
+        if self.source.simplify() {
+            self.ensure_acceptable();
+            true
+        } else {
+            false
+        }
+    }
+
+    fn complicate(&mut self) -> bool {
+        if self.source.complicate() {
+            self.ensure_acceptable();
+            true
+        } else {
+            false
+        }
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    #[test]
+    fn test_filter() {
+        let input = (0..256).prop_filter("%3", |&v| 0 == v % 3);
+
+        for _ in 0..256 {
+            let mut runner = TestRunner::default();
+            let mut case = input.new_tree(&mut runner).unwrap();
+
+            assert!(0 == case.current() % 3);
+
+            while case.simplify() {
+                assert!(0 == case.current() % 3);
+            }
+            assert!(0 == case.current() % 3);
+        }
+    }
+
+    #[test]
+    fn test_filter_sanity() {
+        check_strategy_sanity(
+            (0..256).prop_filter("!%5", |&v| 0 != v % 5),
+            Some(CheckStrategySanityOptions {
+                // Due to internal rejection sampling, `simplify()` can
+                // converge back to what `complicate()` would do.
+                strict_complicate_after_simplify: false,
+                ..CheckStrategySanityOptions::default()
+            }),
+        );
+    }
+}
diff --git a/vendor/proptest/src/strategy/filter_map.rs b/vendor/proptest/src/strategy/filter_map.rs
new file mode 100644
index 000000000..52f901276
--- /dev/null
+++ b/vendor/proptest/src/strategy/filter_map.rs
@@ -0,0 +1,209 @@
+//-
+// 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 crate::std_facade::{fmt, Arc, Cell};
+
+use crate::strategy::traits::*;
+use crate::test_runner::*;
+
+/// `Strategy` and `ValueTree` filter_map adaptor.
+///
+/// See `Strategy::prop_filter_map()`.
+#[must_use = "strategies do nothing unless used"]
+pub struct FilterMap<S, F> {
+    pub(super) source: S,
+    pub(super) whence: Reason,
+    pub(super) fun: Arc<F>,
+}
+
+impl<S, F> FilterMap<S, F> {
+    pub(super) fn new(source: S, whence: Reason, fun: F) -> Self {
+        Self {
+            source,
+            whence,
+            fun: Arc::new(fun),
+        }
+    }
+}
+
+impl<S: fmt::Debug, F> fmt::Debug for FilterMap<S, F> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("FilterMap")
+            .field("source", &self.source)
+            .field("whence", &self.whence)
+            .field("fun", &"<function>")
+            .finish()
+    }
+}
+
+impl<S: Clone, F> Clone for FilterMap<S, F> {
+    fn clone(&self) -> Self {
+        Self {
+            source: self.source.clone(),
+            whence: self.whence.clone(),
+            fun: Arc::clone(&self.fun),
+        }
+    }
+}
+
+impl<S: Strategy, F: Fn(S::Value) -> Option<O>, O: fmt::Debug> Strategy
+    for FilterMap<S, F>
+{
+    type Tree = FilterMapValueTree<S::Tree, F, O>;
+    type Value = O;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        loop {
+            let val = self.source.new_tree(runner)?;
+            if let Some(current) = (self.fun)(val.current()) {
+                return Ok(FilterMapValueTree::new(val, &self.fun, current));
+            } else {
+                runner.reject_local(self.whence.clone())?;
+            }
+        }
+    }
+}
+
+/// `ValueTree` corresponding to `FilterMap`.
+pub struct FilterMapValueTree<V, F, O> {
+    source: V,
+    current: Cell<Option<O>>,
+    fun: Arc<F>,
+}
+
+impl<V: Clone + ValueTree, F: Fn(V::Value) -> Option<O>, O> Clone
+    for FilterMapValueTree<V, F, O>
+{
+    fn clone(&self) -> Self {
+        Self::new(self.source.clone(), &self.fun, self.fresh_current())
+    }
+}
+
+impl<V: fmt::Debug, F, O> fmt::Debug for FilterMapValueTree<V, F, O> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("FilterMapValueTree")
+            .field("source", &self.source)
+            .field("current", &"<current>")
+            .field("fun", &"<function>")
+            .finish()
+    }
+}
+
+impl<V: ValueTree, F: Fn(V::Value) -> Option<O>, O>
+    FilterMapValueTree<V, F, O>
+{
+    fn new(source: V, fun: &Arc<F>, current: O) -> Self {
+        Self {
+            source,
+            current: Cell::new(Some(current)),
+            fun: Arc::clone(fun),
+        }
+    }
+
+    fn fresh_current(&self) -> O {
+        (self.fun)(self.source.current())
+            .expect("internal logic error; this is a bug!")
+    }
+
+    fn ensure_acceptable(&mut self) {
+        loop {
+            if let Some(current) = (self.fun)(self.source.current()) {
+                // Found an acceptable element!
+                self.current = Cell::new(Some(current));
+                break;
+            } else if !self.source.complicate() {
+                panic!(
+                    "Unable to complicate filtered strategy \
+                     back into acceptable value"
+                );
+            }
+        }
+    }
+}
+
+impl<V: ValueTree, F: Fn(V::Value) -> Option<O>, O: fmt::Debug> ValueTree
+    for FilterMapValueTree<V, F, O>
+{
+    type Value = O;
+
+    fn current(&self) -> O {
+        // Optimization: we avoid the else branch in most success cases
+        // thereby avoiding to call the closure and the source tree.
+        if let Some(current) = self.current.replace(None) {
+            current
+        } else {
+            self.fresh_current()
+        }
+    }
+
+    fn simplify(&mut self) -> bool {
+        if self.source.simplify() {
+            self.ensure_acceptable();
+            true
+        } else {
+            false
+        }
+    }
+
+    fn complicate(&mut self) -> bool {
+        if self.source.complicate() {
+            self.ensure_acceptable();
+            true
+        } else {
+            false
+        }
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    #[test]
+    fn test_filter_map() {
+        let input = (0..256).prop_filter_map("%3 + 1", |v| {
+            if 0 == v % 3 {
+                Some(v + 1)
+            } else {
+                None
+            }
+        });
+
+        for _ in 0..256 {
+            let mut runner = TestRunner::default();
+            let mut case = input.new_tree(&mut runner).unwrap();
+
+            assert_eq!(0, (case.current() - 1) % 3);
+
+            while case.simplify() {
+                assert_eq!(0, (case.current() - 1) % 3);
+            }
+            assert_eq!(0, (case.current() - 1) % 3);
+        }
+    }
+
+    #[test]
+    fn test_filter_map_sanity() {
+        check_strategy_sanity(
+            (0..256).prop_filter_map("!%5 * 2", |v| {
+                if 0 != v % 5 {
+                    Some(v * 2)
+                } else {
+                    None
+                }
+            }),
+            Some(CheckStrategySanityOptions {
+                // Due to internal rejection sampling, `simplify()` can
+                // converge back to what `complicate()` would do.
+                strict_complicate_after_simplify: false,
+                ..CheckStrategySanityOptions::default()
+            }),
+        );
+    }
+}
diff --git a/vendor/proptest/src/strategy/flatten.rs b/vendor/proptest/src/strategy/flatten.rs
new file mode 100644
index 000000000..63ac41604
--- /dev/null
+++ b/vendor/proptest/src/strategy/flatten.rs
@@ -0,0 +1,359 @@
+//-
+// 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 crate::std_facade::{fmt, Arc};
+use core::mem;
+
+use crate::strategy::fuse::Fuse;
+use crate::strategy::traits::*;
+use crate::test_runner::*;
+
+/// Adaptor that flattens a `Strategy` which produces other `Strategy`s into a
+/// `Strategy` that picks one of those strategies and then picks values from
+/// it.
+#[derive(Debug, Clone, Copy)]
+#[must_use = "strategies do nothing unless used"]
+pub struct Flatten<S> {
+    source: S,
+}
+
+impl<S: Strategy> Flatten<S> {
+    /// Wrap `source` to flatten it.
+    pub fn new(source: S) -> Self {
+        Flatten { source }
+    }
+}
+
+impl<S: Strategy> Strategy for Flatten<S>
+where
+    S::Value: Strategy,
+{
+    type Tree = FlattenValueTree<S::Tree>;
+    type Value = <S::Value as Strategy>::Value;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        let meta = self.source.new_tree(runner)?;
+        FlattenValueTree::new(runner, meta)
+    }
+}
+
+/// The `ValueTree` produced by `Flatten`.
+pub struct FlattenValueTree<S: ValueTree>
+where
+    S::Value: Strategy,
+{
+    meta: Fuse<S>,
+    current: Fuse<<S::Value as Strategy>::Tree>,
+    // The final value to produce after successive calls to complicate() on the
+    // underlying objects return false.
+    final_complication: Option<Fuse<<S::Value as Strategy>::Tree>>,
+    // When `simplify()` or `complicate()` causes a new `Strategy` to be
+    // chosen, we need to find a new failing input for that case. To do this,
+    // we implement `complicate()` by regenerating values up to a number of
+    // times corresponding to the maximum number of test cases. A `simplify()`
+    // which does not cause a new strategy to be chosen always resets
+    // `complicate_regen_remaining` to 0.
+    //
+    // This does unfortunately depart from the direct interpretation of
+    // simplify/complicate as binary search, but is still easier to think about
+    // than other implementations of higher-order strategies.
+    runner: TestRunner,
+    complicate_regen_remaining: u32,
+}
+
+impl<S: ValueTree> Clone for FlattenValueTree<S>
+where
+    S::Value: Strategy + Clone,
+    S: Clone,
+    <S::Value as Strategy>::Tree: Clone,
+{
+    fn clone(&self) -> Self {
+        FlattenValueTree {
+            meta: self.meta.clone(),
+            current: self.current.clone(),
+            final_complication: self.final_complication.clone(),
+            runner: self.runner.clone(),
+            complicate_regen_remaining: self.complicate_regen_remaining,
+        }
+    }
+}
+
+impl<S: ValueTree> fmt::Debug for FlattenValueTree<S>
+where
+    S::Value: Strategy,
+    S: fmt::Debug,
+    <S::Value as Strategy>::Tree: fmt::Debug,
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("FlattenValueTree")
+            .field("meta", &self.meta)
+            .field("current", &self.current)
+            .field("final_complication", &self.final_complication)
+            .field(
+                "complicate_regen_remaining",
+                &self.complicate_regen_remaining,
+            )
+            .finish()
+    }
+}
+
+impl<S: ValueTree> FlattenValueTree<S>
+where
+    S::Value: Strategy,
+{
+    fn new(runner: &mut TestRunner, meta: S) -> Result<Self, Reason> {
+        let current = meta.current().new_tree(runner)?;
+        Ok(FlattenValueTree {
+            meta: Fuse::new(meta),
+            current: Fuse::new(current),
+            final_complication: None,
+            runner: runner.partial_clone(),
+            complicate_regen_remaining: 0,
+        })
+    }
+}
+
+impl<S: ValueTree> ValueTree for FlattenValueTree<S>
+where
+    S::Value: Strategy,
+{
+    type Value = <S::Value as Strategy>::Value;
+
+    fn current(&self) -> Self::Value {
+        self.current.current()
+    }
+
+    fn simplify(&mut self) -> bool {
+        self.complicate_regen_remaining = 0;
+
+        if self.current.simplify() {
+            // Now that we've simplified the derivative value, we can't
+            // re-complicate the meta value unless it gets simplified again.
+            // We also mustn't complicate back to whatever's in
+            // `final_complication` since the new state of `self.current` is
+            // the most complicated state.
+            self.meta.disallow_complicate();
+            self.final_complication = None;
+            true
+        } else if !self.meta.simplify() {
+            false
+        } else if let Ok(v) = self.meta.current().new_tree(&mut self.runner) {
+            // Shift current into final_complication and `v` into
+            // `current`. We also need to prevent that value from
+            // complicating beyond the current point in the future
+            // since we're going to return `true` from `simplify()`
+            // ourselves.
+            self.current.disallow_complicate();
+            self.final_complication = Some(Fuse::new(v));
+            mem::swap(
+                self.final_complication.as_mut().unwrap(),
+                &mut self.current,
+            );
+            // Initially complicate by regenerating the chosen value.
+            self.complicate_regen_remaining = self.runner.config().cases;
+            true
+        } else {
+            false
+        }
+    }
+
+    fn complicate(&mut self) -> bool {
+        if self.complicate_regen_remaining > 0 {
+            if self.runner.flat_map_regen() {
+                self.complicate_regen_remaining -= 1;
+
+                if let Ok(v) = self.meta.current().new_tree(&mut self.runner) {
+                    self.current = Fuse::new(v);
+                    return true;
+                }
+            } else {
+                self.complicate_regen_remaining = 0;
+            }
+        }
+
+        if self.current.complicate() {
+            return true;
+        } else if self.meta.complicate() {
+            if let Ok(v) = self.meta.current().new_tree(&mut self.runner) {
+                self.complicate_regen_remaining = self.runner.config().cases;
+                self.current = Fuse::new(v);
+                return true;
+            }
+        }
+
+        if let Some(v) = self.final_complication.take() {
+            self.current = v;
+            true
+        } else {
+            false
+        }
+    }
+}
+
+/// Similar to `Flatten`, but does not shrink the input strategy.
+///
+/// See `Strategy::prop_ind_flat_map()` fore more details.
+#[derive(Clone, Copy, Debug)]
+pub struct IndFlatten<S>(pub(super) S);
+
+impl<S: Strategy> Strategy for IndFlatten<S>
+where
+    S::Value: Strategy,
+{
+    type Tree = <S::Value as Strategy>::Tree;
+    type Value = <S::Value as Strategy>::Value;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        let inner = self.0.new_tree(runner)?;
+        inner.current().new_tree(runner)
+    }
+}
+
+/// Similar to `Map` plus `Flatten`, but does not shrink the input strategy and
+/// passes the original input through.
+///
+/// See `Strategy::prop_ind_flat_map2()` for more details.
+pub struct IndFlattenMap<S, F> {
+    pub(super) source: S,
+    pub(super) fun: Arc<F>,
+}
+
+impl<S: fmt::Debug, F> fmt::Debug for IndFlattenMap<S, F> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("IndFlattenMap")
+            .field("source", &self.source)
+            .field("fun", &"<function>")
+            .finish()
+    }
+}
+
+impl<S: Clone, F> Clone for IndFlattenMap<S, F> {
+    fn clone(&self) -> Self {
+        IndFlattenMap {
+            source: self.source.clone(),
+            fun: Arc::clone(&self.fun),
+        }
+    }
+}
+
+impl<S: Strategy, R: Strategy, F: Fn(S::Value) -> R> Strategy
+    for IndFlattenMap<S, F>
+{
+    type Tree = crate::tuple::TupleValueTree<(S::Tree, R::Tree)>;
+    type Value = (S::Value, R::Value);
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        let left = self.source.new_tree(runner)?;
+        let right_source = (self.fun)(left.current());
+        let right = right_source.new_tree(runner)?;
+
+        Ok(crate::tuple::TupleValueTree::new((left, right)))
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    use std::u32;
+
+    use crate::strategy::just::Just;
+    use crate::test_runner::Config;
+
+    #[test]
+    fn test_flat_map() {
+        // Pick random integer A, then random integer B which is ±5 of A and
+        // assert that B <= A if A > 10000. Shrinking should always converge to
+        // A=10001, B=10002.
+        let input = (0..65536).prop_flat_map(|a| (Just(a), (a - 5..a + 5)));
+
+        let mut failures = 0;
+        let mut runner = TestRunner::new_with_rng(
+            Config {
+                max_shrink_iters: u32::MAX - 1,
+                ..Config::default()
+            },
+            TestRng::deterministic_rng(RngAlgorithm::default()),
+        );
+        for _ in 0..1000 {
+            let case = input.new_tree(&mut runner).unwrap();
+            let result = runner.run_one(case, |(a, b)| {
+                if a <= 10000 || b <= a {
+                    Ok(())
+                } else {
+                    Err(TestCaseError::fail("fail"))
+                }
+            });
+
+            match result {
+                Ok(_) => {}
+                Err(TestError::Fail(_, v)) => {
+                    failures += 1;
+                    assert_eq!((10001, 10002), v);
+                }
+                result => panic!("Unexpected result: {:?}", result),
+            }
+        }
+
+        assert!(failures > 250);
+    }
+
+    #[test]
+    fn test_flat_map_sanity() {
+        check_strategy_sanity(
+            (0..65536).prop_flat_map(|a| (Just(a), (a - 5..a + 5))),
+            None,
+        );
+    }
+
+    #[test]
+    fn flat_map_respects_regen_limit() {
+        use std::sync::atomic::{AtomicBool, Ordering};
+
+        let input = (0..65536)
+            .prop_flat_map(|_| 0..65536)
+            .prop_flat_map(|_| 0..65536)
+            .prop_flat_map(|_| 0..65536)
+            .prop_flat_map(|_| 0..65536)
+            .prop_flat_map(|_| 0..65536);
+
+        // Arteficially make the first case fail and all others pass, so that
+        // the regeneration logic futilely searches for another failing
+        // example and eventually gives up. Unfortunately, the test is sort of
+        // semi-decidable; if the limit *doesn't* work, the test just runs
+        // almost forever.
+        let pass = AtomicBool::new(false);
+        let mut runner = TestRunner::new(Config {
+            max_flat_map_regens: 1000,
+            ..Config::default()
+        });
+        let case = input.new_tree(&mut runner).unwrap();
+        let _ = runner.run_one(case, |_| {
+            // Only the first run fails, all others succeed
+            prop_assert!(pass.fetch_or(true, Ordering::SeqCst));
+            Ok(())
+        });
+    }
+
+    #[test]
+    fn test_ind_flat_map_sanity() {
+        check_strategy_sanity(
+            (0..65536).prop_ind_flat_map(|a| (Just(a), (a - 5..a + 5))),
+            None,
+        );
+    }
+
+    #[test]
+    fn test_ind_flat_map2_sanity() {
+        check_strategy_sanity(
+            (0..65536).prop_ind_flat_map2(|a| a - 5..a + 5),
+            None,
+        );
+    }
+}
diff --git a/vendor/proptest/src/strategy/fuse.rs b/vendor/proptest/src/strategy/fuse.rs
new file mode 100644
index 000000000..5c0f9a374
--- /dev/null
+++ b/vendor/proptest/src/strategy/fuse.rs
@@ -0,0 +1,228 @@
+//-
+// 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 crate::strategy::*;
+use crate::test_runner::*;
+
+/// Adaptor for `Strategy` and `ValueTree` which guards `simplify()` and
+/// `complicate()` to avoid contract violations.
+///
+/// This can be used as an intermediate when the caller would otherwise need
+/// its own separate state tracking, or as a workaround for a broken
+/// `ValueTree` implementation.
+///
+/// This wrapper specifically has the following effects:
+///
+/// - Calling `complicate()` before `simplify()` was ever called does nothing
+///   and returns `false`.
+///
+/// - Calling `simplify()` after it has returned `false` and no calls to
+///   `complicate()` returned `true` does nothing and returns `false`.
+///
+/// - Calling `complicate()` after it has returned `false` and no calls to
+///   `simplify()` returned `true` does nothing and returns `false`.
+///
+/// There is also limited functionality to alter the internal state to assist
+/// in its usage as a state tracker.
+///
+/// Wrapping a `Strategy` in `Fuse` simply causes its `ValueTree` to also be
+/// wrapped in `Fuse`.
+///
+/// While this is similar to `std::iter::Fuse`, it is not exposed as a method
+/// on `Strategy` since the vast majority of proptest should never need this
+/// functionality; it mainly concerns implementors of strategies.
+#[derive(Debug, Clone, Copy)]
+#[must_use = "strategies do nothing unless used"]
+pub struct Fuse<T> {
+    inner: T,
+    may_simplify: bool,
+    may_complicate: bool,
+}
+
+impl<T> Fuse<T> {
+    /// Wrap the given `T` in `Fuse`.
+    pub fn new(inner: T) -> Self {
+        Fuse {
+            inner,
+            may_simplify: true,
+            may_complicate: false,
+        }
+    }
+}
+
+impl<T: Strategy> Strategy for Fuse<T> {
+    type Tree = Fuse<T::Tree>;
+    type Value = T::Value;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        self.inner.new_tree(runner).map(Fuse::new)
+    }
+}
+
+impl<T: ValueTree> Fuse<T> {
+    /// Return whether a call to `simplify()` may be productive.
+    ///
+    /// Formally, this is true if one of the following holds:
+    ///
+    /// - `simplify()` has never been called.
+    /// - The most recent call to `simplify()` returned `true`.
+    /// - `complicate()` has been called more recently than `simplify()` and
+    ///   the last call returned `true`.
+    pub fn may_simplify(&self) -> bool {
+        self.may_simplify
+    }
+
+    /// Disallow any further calls to `simplify()` until a call to
+    /// `complicate()` returns `true`.
+    pub fn disallow_simplify(&mut self) {
+        self.may_simplify = false;
+    }
+
+    /// Return whether a call to `complicate()` may be productive.
+    ///
+    /// Formally, this is true if one of the following holds:
+    ///
+    /// - The most recent call to `complicate()` returned `true`.
+    /// - `simplify()` has been called more recently than `complicate()` and
+    ///   the last call returned `true`.
+    pub fn may_complicate(&self) -> bool {
+        self.may_complicate
+    }
+
+    /// Disallow any further calls to `complicate()` until a call to
+    /// `simplify()` returns `true`.
+    pub fn disallow_complicate(&mut self) {
+        self.may_complicate = false;
+    }
+
+    /// Prevent any further shrinking operations from occurring.
+    pub fn freeze(&mut self) {
+        self.disallow_simplify();
+        self.disallow_complicate();
+    }
+}
+
+impl<T: ValueTree> ValueTree for Fuse<T> {
+    type Value = T::Value;
+
+    fn current(&self) -> T::Value {
+        self.inner.current()
+    }
+
+    fn simplify(&mut self) -> bool {
+        if self.may_simplify {
+            if self.inner.simplify() {
+                self.may_complicate = true;
+                true
+            } else {
+                self.may_simplify = false;
+                false
+            }
+        } else {
+            false
+        }
+    }
+
+    fn complicate(&mut self) -> bool {
+        if self.may_complicate {
+            if self.inner.complicate() {
+                self.may_simplify = true;
+                true
+            } else {
+                self.may_complicate = false;
+                false
+            }
+        } else {
+            false
+        }
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    struct StrictValueTree {
+        min: u32,
+        curr: u32,
+        max: u32,
+        ready: bool,
+    }
+
+    impl StrictValueTree {
+        fn new(start: u32) -> Self {
+            StrictValueTree {
+                min: 0,
+                curr: start,
+                max: start,
+                ready: false,
+            }
+        }
+    }
+
+    impl ValueTree for StrictValueTree {
+        type Value = u32;
+
+        fn current(&self) -> u32 {
+            self.curr
+        }
+
+        fn simplify(&mut self) -> bool {
+            assert!(self.min <= self.curr);
+            if self.curr > self.min {
+                self.max = self.curr;
+                self.curr -= 1;
+                self.ready = true;
+                true
+            } else {
+                self.min += 1;
+                false
+            }
+        }
+
+        fn complicate(&mut self) -> bool {
+            assert!(self.max >= self.curr);
+            assert!(self.ready);
+            if self.curr < self.max {
+                self.curr += 1;
+                true
+            } else {
+                self.max -= 1;
+                false
+            }
+        }
+    }
+
+    #[test]
+    fn test_sanity() {
+        check_strategy_sanity(Fuse::new(0i32..100i32), None);
+    }
+
+    #[test]
+    fn guards_bad_transitions() {
+        let mut vt = Fuse::new(StrictValueTree::new(5));
+        assert!(!vt.complicate());
+        assert_eq!(5, vt.current());
+
+        assert!(vt.simplify()); // 0, 4, 5
+        assert!(vt.simplify()); // 0, 3, 4
+        assert!(vt.simplify()); // 0, 2, 3
+        assert!(vt.simplify()); // 0, 1, 2
+        assert!(vt.simplify()); // 0, 0, 1
+        assert_eq!(0, vt.current());
+        assert!(!vt.simplify()); // 1, 0, 1
+        assert!(!vt.simplify()); // 1, 0, 1
+        assert_eq!(0, vt.current());
+        assert!(vt.complicate()); // 1, 1, 1
+        assert_eq!(1, vt.current());
+        assert!(!vt.complicate()); // 1, 1, 0
+        assert!(!vt.complicate()); // 1, 1, 0
+        assert_eq!(1, vt.current());
+    }
+}
diff --git a/vendor/proptest/src/strategy/just.rs b/vendor/proptest/src/strategy/just.rs
new file mode 100644
index 000000000..a141f8a17
--- /dev/null
+++ b/vendor/proptest/src/strategy/just.rs
@@ -0,0 +1,145 @@
+//-
+// 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.
+
+use crate::std_facade::fmt;
+
+use crate::strategy::{NewTree, Strategy, ValueTree};
+use crate::test_runner::TestRunner;
+
+macro_rules! noshrink {
+    () => {
+        fn simplify(&mut self) -> bool {
+            false
+        }
+        fn complicate(&mut self) -> bool {
+            false
+        }
+    };
+}
+
+//==============================================================================
+// Just
+//==============================================================================
+
+/// A `Strategy` which always produces a single value value and never
+/// simplifies.
+#[derive(Clone, Copy, Debug)]
+#[must_use = "strategies do nothing unless used"]
+pub struct Just<T: Clone + fmt::Debug>(
+    /// The value produced by this strategy.
+    pub T,
+);
+
+impl<T: Clone + fmt::Debug> Strategy for Just<T> {
+    type Tree = Self;
+    type Value = T;
+
+    fn new_tree(&self, _: &mut TestRunner) -> NewTree<Self> {
+        Ok(self.clone())
+    }
+}
+
+impl<T: Clone + fmt::Debug> ValueTree for Just<T> {
+    type Value = T;
+    noshrink!();
+    fn current(&self) -> T {
+        self.0.clone()
+    }
+}
+
+//==============================================================================
+// LazyJust
+//==============================================================================
+
+/// A `Strategy` which always produces a single value value and never
+/// simplifies. If `T` is `Clone`, you should use `Just` instead.
+///
+/// This is a generalization of `Just` and works by calling
+/// the provided `Fn () -> T` in `.current()` every time. This is not a
+/// very interesting strategy, but is required in cases where `T` is
+/// not `Clone`. It is also used in `proptest_derive` where we can't
+/// assume that your type is `Clone`.
+///
+/// **It is important that the function used be pure.**
+#[must_use = "strategies do nothing unless used"]
+pub struct LazyJust<T, F: Fn() -> T> {
+    /// The function executed in `.current()`.
+    function: F,
+}
+
+/// Shorthand for `LazyJust<T, fn () -> T>`.
+pub type LazyJustFn<V> = LazyJust<V, fn() -> V>;
+
+impl<T, F: Fn() -> T> LazyJust<T, F> {
+    /// Constructs a `LazyJust` strategy given the function/closure
+    /// that produces the value.
+    ///
+    /// **It is important that the function used be pure.**
+    pub fn new(function: F) -> Self {
+        Self { function }
+    }
+}
+
+impl<T: fmt::Debug, F: Clone + Fn() -> T> Strategy for LazyJust<T, F> {
+    type Tree = Self;
+    type Value = T;
+
+    fn new_tree(&self, _: &mut TestRunner) -> NewTree<Self> {
+        Ok(self.clone())
+    }
+}
+
+impl<T: fmt::Debug, F: Fn() -> T> ValueTree for LazyJust<T, F> {
+    type Value = T;
+    noshrink!();
+    fn current(&self) -> Self::Value {
+        (self.function)()
+    }
+}
+
+impl<T, F: Copy + Fn() -> T> Copy for LazyJust<T, F> {}
+
+impl<T, F: Clone + Fn() -> T> Clone for LazyJust<T, F> {
+    fn clone(&self) -> Self {
+        Self {
+            function: self.function.clone(),
+        }
+    }
+}
+
+impl<T, F: Fn() -> T> fmt::Debug for LazyJust<T, F> {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        fmt.debug_struct("LazyJust")
+            .field("function", &"<function>")
+            .finish()
+    }
+}
+
+//==============================================================================
+// Any `fn () -> T` is a Strategy
+//==============================================================================
+
+// TODO: try 'F: Fn () -> T' instead when we've got specialization.
+
+impl<T: fmt::Debug> Strategy for fn() -> T {
+    type Tree = Self;
+    type Value = T;
+
+    fn new_tree(&self, _: &mut TestRunner) -> NewTree<Self> {
+        Ok(*self)
+    }
+}
+
+impl<T: fmt::Debug> ValueTree for fn() -> T {
+    type Value = T;
+    noshrink!();
+    fn current(&self) -> Self::Value {
+        self()
+    }
+}
diff --git a/vendor/proptest/src/strategy/lazy.rs b/vendor/proptest/src/strategy/lazy.rs
new file mode 100644
index 000000000..cb95a7492
--- /dev/null
+++ b/vendor/proptest/src/strategy/lazy.rs
@@ -0,0 +1,175 @@
+//-
+// Copyright 2019 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.
+
+use crate::std_facade::{fmt, Arc};
+use core::mem;
+
+use crate::strategy::traits::*;
+use crate::test_runner::*;
+
+/// Represents a value tree that is initialized on the first call to any
+/// methods.
+///
+/// This is used to defer potentially expensive generation to shrinking time. It
+/// is public only to allow APIs to expose it as an intermediate value.
+pub struct LazyValueTree<S: Strategy> {
+    state: LazyValueTreeState<S>,
+}
+
+enum LazyValueTreeState<S: Strategy> {
+    Initialized(S::Tree),
+    Uninitialized {
+        strategy: Arc<S>,
+        runner: TestRunner,
+    },
+    Failed,
+}
+
+impl<S: Strategy> LazyValueTree<S> {
+    /// Create a new value tree where initial generation is deferred until
+    /// `maybe_init` is called.
+    pub(crate) fn new(strategy: Arc<S>, runner: &mut TestRunner) -> Self {
+        let runner = runner.partial_clone();
+        Self {
+            state: LazyValueTreeState::Uninitialized { strategy, runner },
+        }
+    }
+
+    /// Create a new value tree that has already been initialized.
+    pub(crate) fn new_initialized(value_tree: S::Tree) -> Self {
+        Self {
+            state: LazyValueTreeState::Initialized(value_tree),
+        }
+    }
+
+    /// Returns a reference to the inner value tree if initialized.
+    pub(crate) fn as_inner(&self) -> Option<&S::Tree> {
+        match &self.state {
+            LazyValueTreeState::Initialized(v) => Some(v),
+            LazyValueTreeState::Uninitialized { .. }
+            | LazyValueTreeState::Failed => None,
+        }
+    }
+
+    /// Returns a mutable reference to the inner value tree if uninitialized.
+    pub(crate) fn as_inner_mut(&mut self) -> Option<&mut S::Tree> {
+        match &mut self.state {
+            LazyValueTreeState::Initialized(v) => Some(v),
+            LazyValueTreeState::Uninitialized { .. }
+            | LazyValueTreeState::Failed => None,
+        }
+    }
+
+    /// Try initializing the value tree.
+    pub(crate) fn maybe_init(&mut self) {
+        if !self.is_uninitialized() {
+            return;
+        }
+
+        let state = mem::replace(&mut self.state, LazyValueTreeState::Failed);
+        match state {
+            LazyValueTreeState::Uninitialized {
+                strategy,
+                mut runner,
+            } => {
+                match strategy.new_tree(&mut runner) {
+                    Ok(v) => {
+                        let _ = mem::replace(
+                            &mut self.state,
+                            LazyValueTreeState::Initialized(v),
+                        );
+                    }
+                    Err(_) => {
+                        // self.state is set to Failed above. Keep it that way.
+                    }
+                }
+            }
+            LazyValueTreeState::Initialized(_) | LazyValueTreeState::Failed => {
+                unreachable!("can only reach here if uninitialized")
+            }
+        }
+    }
+
+    /// Whether this value tree still needs to be initialized.
+    pub(crate) fn is_uninitialized(&self) -> bool {
+        match &self.state {
+            LazyValueTreeState::Uninitialized { .. } => true,
+            LazyValueTreeState::Initialized(_) | LazyValueTreeState::Failed => {
+                false
+            }
+        }
+    }
+
+    /// Whether the value tree was successfully initialized.
+    pub(crate) fn is_initialized(&self) -> bool {
+        match &self.state {
+            LazyValueTreeState::Initialized(_) => true,
+            LazyValueTreeState::Uninitialized { .. }
+            | LazyValueTreeState::Failed => false,
+        }
+    }
+}
+
+impl<S: Strategy> Clone for LazyValueTree<S>
+where
+    S::Tree: Clone,
+{
+    fn clone(&self) -> Self {
+        Self {
+            state: self.state.clone(),
+        }
+    }
+}
+
+impl<S: Strategy> fmt::Debug for LazyValueTree<S>
+where
+    S::Tree: fmt::Debug,
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("LazyValueTree")
+            .field("state", &self.state)
+            .finish()
+    }
+}
+
+impl<S: Strategy> Clone for LazyValueTreeState<S>
+where
+    S::Tree: Clone,
+{
+    fn clone(&self) -> Self {
+        use LazyValueTreeState::*;
+
+        match self {
+            Initialized(v) => Initialized(v.clone()),
+            Uninitialized { strategy, runner } => Uninitialized {
+                strategy: Arc::clone(strategy),
+                runner: runner.clone(),
+            },
+            Failed => Failed,
+        }
+    }
+}
+
+impl<S: Strategy> fmt::Debug for LazyValueTreeState<S>
+where
+    S::Tree: fmt::Debug,
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match self {
+            LazyValueTreeState::Initialized(value_tree) => {
+                f.debug_tuple("Initialized").field(value_tree).finish()
+            }
+            LazyValueTreeState::Uninitialized { strategy, .. } => f
+                .debug_struct("Uninitialized")
+                .field("strategy", strategy)
+                .finish(),
+            LazyValueTreeState::Failed => write!(f, "Failed"),
+        }
+    }
+}
diff --git a/vendor/proptest/src/strategy/map.rs b/vendor/proptest/src/strategy/map.rs
new file mode 100644
index 000000000..464b99819
--- /dev/null
+++ b/vendor/proptest/src/strategy/map.rs
@@ -0,0 +1,301 @@
+//-
+// 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 crate::std_facade::Arc;
+use core::fmt;
+use core::marker::PhantomData;
+
+use crate::strategy::traits::*;
+use crate::test_runner::*;
+
+//==============================================================================
+// Map
+//==============================================================================
+
+/// `Strategy` and `ValueTree` map adaptor.
+///
+/// See `Strategy::prop_map()`.
+#[must_use = "strategies do nothing unless used"]
+pub struct Map<S, F> {
+    pub(super) source: S,
+    pub(super) fun: Arc<F>,
+}
+
+impl<S: fmt::Debug, F> fmt::Debug for Map<S, F> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("Map")
+            .field("source", &self.source)
+            .field("fun", &"<function>")
+            .finish()
+    }
+}
+
+impl<S: Clone, F> Clone for Map<S, F> {
+    fn clone(&self) -> Self {
+        Map {
+            source: self.source.clone(),
+            fun: Arc::clone(&self.fun),
+        }
+    }
+}
+
+impl<S: Strategy, O: fmt::Debug, F: Fn(S::Value) -> O> Strategy for Map<S, F> {
+    type Tree = Map<S::Tree, F>;
+    type Value = O;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        self.source.new_tree(runner).map(|v| Map {
+            source: v,
+            fun: Arc::clone(&self.fun),
+        })
+    }
+}
+
+impl<S: ValueTree, O: fmt::Debug, F: Fn(S::Value) -> O> ValueTree
+    for Map<S, F>
+{
+    type Value = O;
+
+    fn current(&self) -> O {
+        (self.fun)(self.source.current())
+    }
+
+    fn simplify(&mut self) -> bool {
+        self.source.simplify()
+    }
+
+    fn complicate(&mut self) -> bool {
+        self.source.complicate()
+    }
+}
+
+//==============================================================================
+// MapInto
+//==============================================================================
+
+// NOTE: Since this is external stable API,
+// we avoid relying on the Map in `statics`.
+
+/// `Strategy` and `ValueTree` map into adaptor.
+///
+/// See `Strategy::prop_map_into()`.
+#[must_use = "strategies do nothing unless used"]
+pub struct MapInto<S, O> {
+    pub(super) source: S,
+    pub(super) output: PhantomData<O>,
+}
+
+impl<S, O> MapInto<S, O> {
+    /// Construct a `MapInto` mapper from an `S` strategy into a strategy
+    /// producing `O`s.
+    pub(super) fn new(source: S) -> Self {
+        Self {
+            source,
+            output: PhantomData,
+        }
+    }
+}
+
+impl<S: fmt::Debug, O> fmt::Debug for MapInto<S, O> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("MapInto")
+            .field("source", &self.source)
+            .finish()
+    }
+}
+
+impl<S: Clone, O> Clone for MapInto<S, O> {
+    fn clone(&self) -> Self {
+        Self::new(self.source.clone())
+    }
+}
+
+impl<S: Strategy, O: fmt::Debug> Strategy for MapInto<S, O>
+where
+    S::Value: Into<O>,
+{
+    type Tree = MapInto<S::Tree, O>;
+    type Value = O;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        self.source.new_tree(runner).map(MapInto::new)
+    }
+}
+
+impl<S: ValueTree, O: fmt::Debug> ValueTree for MapInto<S, O>
+where
+    S::Value: Into<O>,
+{
+    type Value = O;
+
+    fn current(&self) -> O {
+        self.source.current().into()
+    }
+
+    fn simplify(&mut self) -> bool {
+        self.source.simplify()
+    }
+
+    fn complicate(&mut self) -> bool {
+        self.source.complicate()
+    }
+}
+
+//==============================================================================
+// Perturb
+//==============================================================================
+
+/// `Strategy` perturbation adaptor.
+///
+/// See `Strategy::prop_perturb()`.
+#[must_use = "strategies do nothing unless used"]
+pub struct Perturb<S, F> {
+    pub(super) source: S,
+    pub(super) fun: Arc<F>,
+}
+
+impl<S: fmt::Debug, F> fmt::Debug for Perturb<S, F> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("Perturb")
+            .field("source", &self.source)
+            .field("fun", &"<function>")
+            .finish()
+    }
+}
+
+impl<S: Clone, F> Clone for Perturb<S, F> {
+    fn clone(&self) -> Self {
+        Perturb {
+            source: self.source.clone(),
+            fun: Arc::clone(&self.fun),
+        }
+    }
+}
+
+impl<S: Strategy, O: fmt::Debug, F: Fn(S::Value, TestRng) -> O> Strategy
+    for Perturb<S, F>
+{
+    type Tree = PerturbValueTree<S::Tree, F>;
+    type Value = O;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        let rng = runner.new_rng();
+
+        self.source.new_tree(runner).map(|source| PerturbValueTree {
+            source,
+            rng,
+            fun: Arc::clone(&self.fun),
+        })
+    }
+}
+
+/// `ValueTree` perturbation adaptor.
+///
+/// See `Strategy::prop_perturb()`.
+pub struct PerturbValueTree<S, F> {
+    source: S,
+    fun: Arc<F>,
+    rng: TestRng,
+}
+
+impl<S: fmt::Debug, F> fmt::Debug for PerturbValueTree<S, F> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("PerturbValueTree")
+            .field("source", &self.source)
+            .field("fun", &"<function>")
+            .field("rng", &self.rng)
+            .finish()
+    }
+}
+
+impl<S: Clone, F> Clone for PerturbValueTree<S, F> {
+    fn clone(&self) -> Self {
+        PerturbValueTree {
+            source: self.source.clone(),
+            fun: Arc::clone(&self.fun),
+            rng: self.rng.clone(),
+        }
+    }
+}
+
+impl<S: ValueTree, O: fmt::Debug, F: Fn(S::Value, TestRng) -> O> ValueTree
+    for PerturbValueTree<S, F>
+{
+    type Value = O;
+
+    fn current(&self) -> O {
+        (self.fun)(self.source.current(), self.rng.clone())
+    }
+
+    fn simplify(&mut self) -> bool {
+        self.source.simplify()
+    }
+
+    fn complicate(&mut self) -> bool {
+        self.source.complicate()
+    }
+}
+
+//==============================================================================
+// Tests
+//==============================================================================
+
+#[cfg(test)]
+mod test {
+    use std::collections::HashSet;
+
+    use rand::RngCore;
+
+    use super::*;
+    use crate::strategy::just::Just;
+
+    #[test]
+    fn test_map() {
+        TestRunner::default()
+            .run(&(0..10).prop_map(|v| v * 2), |v| {
+                assert!(0 == v % 2);
+                Ok(())
+            })
+            .unwrap();
+    }
+
+    #[test]
+    fn test_map_into() {
+        TestRunner::default()
+            .run(&(0..10u8).prop_map_into::<usize>(), |v| {
+                assert!(v < 10);
+                Ok(())
+            })
+            .unwrap();
+    }
+
+    #[test]
+    fn perturb_uses_same_rng_every_time() {
+        let mut runner = TestRunner::default();
+        let input = Just(1).prop_perturb(|v, mut rng| v + rng.next_u32());
+
+        for _ in 0..16 {
+            let value = input.new_tree(&mut runner).unwrap();
+            assert_eq!(value.current(), value.current());
+        }
+    }
+
+    #[test]
+    fn perturb_uses_varying_random_seeds() {
+        let mut runner = TestRunner::default();
+        let input = Just(1).prop_perturb(|v, mut rng| v + rng.next_u32());
+
+        let mut seen = HashSet::new();
+        for _ in 0..64 {
+            seen.insert(input.new_tree(&mut runner).unwrap().current());
+        }
+
+        assert_eq!(64, seen.len());
+    }
+}
diff --git a/vendor/proptest/src/strategy/mod.rs b/vendor/proptest/src/strategy/mod.rs
new file mode 100644
index 000000000..6427fc103
--- /dev/null
+++ b/vendor/proptest/src/strategy/mod.rs
@@ -0,0 +1,37 @@
+//-
+// 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.
+
+//! Defines the core traits used by Proptest.
+
+mod filter;
+mod filter_map;
+mod flatten;
+mod fuse;
+mod just;
+mod lazy;
+mod map;
+mod recursive;
+mod shuffle;
+mod traits;
+mod unions;
+
+pub use self::filter::*;
+pub use self::filter_map::*;
+pub use self::flatten::*;
+pub use self::fuse::*;
+pub use self::just::*;
+pub use self::lazy::*;
+pub use self::lazy::*;
+pub use self::map::*;
+pub use self::recursive::*;
+pub use self::shuffle::*;
+pub use self::traits::*;
+pub use self::unions::*;
+
+pub mod statics;
diff --git a/vendor/proptest/src/strategy/recursive.rs b/vendor/proptest/src/strategy/recursive.rs
new file mode 100644
index 000000000..6407be7c7
--- /dev/null
+++ b/vendor/proptest/src/strategy/recursive.rs
@@ -0,0 +1,209 @@
+//-
+// 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 crate::std_facade::{fmt, Arc, Box, Vec};
+
+use crate::strategy::traits::*;
+use crate::strategy::unions::float_to_weight;
+use crate::test_runner::*;
+
+/// Return type from `Strategy::prop_recursive()`.
+#[must_use = "strategies do nothing unless used"]
+pub struct Recursive<T, F> {
+    base: BoxedStrategy<T>,
+    recurse: Arc<F>,
+    depth: u32,
+    desired_size: u32,
+    expected_branch_size: u32,
+}
+
+impl<T: fmt::Debug, F> fmt::Debug for Recursive<T, F> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("Recursive")
+            .field("base", &self.base)
+            .field("recurse", &"<function>")
+            .field("depth", &self.depth)
+            .field("desired_size", &self.desired_size)
+            .field("expected_branch_size", &self.expected_branch_size)
+            .finish()
+    }
+}
+
+impl<T, F> Clone for Recursive<T, F> {
+    fn clone(&self) -> Self {
+        Recursive {
+            base: self.base.clone(),
+            recurse: Arc::clone(&self.recurse),
+            depth: self.depth,
+            desired_size: self.desired_size,
+            expected_branch_size: self.expected_branch_size,
+        }
+    }
+}
+
+impl<
+        T: fmt::Debug + 'static,
+        R: Strategy<Value = T> + 'static,
+        F: Fn(BoxedStrategy<T>) -> R,
+    > Recursive<T, F>
+{
+    pub(super) fn new(
+        base: impl Strategy<Value = T> + 'static,
+        depth: u32,
+        desired_size: u32,
+        expected_branch_size: u32,
+        recurse: F,
+    ) -> Self {
+        Self {
+            base: base.boxed(),
+            recurse: Arc::new(recurse),
+            depth,
+            desired_size,
+            expected_branch_size,
+        }
+    }
+}
+
+impl<
+        T: fmt::Debug + 'static,
+        R: Strategy<Value = T> + 'static,
+        F: Fn(BoxedStrategy<T>) -> R,
+    > Strategy for Recursive<T, F>
+{
+    type Tree = Box<dyn ValueTree<Value = T>>;
+    type Value = T;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        // Since the generator is stateless, we can't implement any "absolutely
+        // X many items" rule. We _can_, however, with extremely high
+        // probability, obtain a value near what we want by using decaying
+        // probabilities of branching as we go down the tree.
+        //
+        // We are given a target size S and a branch size K (branch size =
+        // expected number of items immediately below each branch). We select
+        // some probability P for each level.
+        //
+        // A single level l is thus expected to hold PlK branches. Each of
+        // those will have P(l+1)K child branches of their own, so there are
+        // PlP(l+1)K² second-level branches. The total branches in the tree is
+        // thus (Σ PlK^l) for l from 0 to infinity. Each level is expected to
+        // hold K items, so the total number of items is simply K times the
+        // number of branches, or (K Σ PlK^l). So we want to find a P sequence
+        // such that (lim (K Σ PlK^l) = S), or more simply,
+        // (lim Σ PlK^l = S/K).
+        //
+        // Let Q be a second probability sequence such that Pl = Ql/K^l. This
+        // changes the formulation to (lim Σ Ql = S/K). The series Σ0.5^(l+1)
+        // converges on 1.0, so we can let Ql = S/K * 0.5^(l+1), and so
+        // Pl = S/K^(l+1) * 0.5^(l+1) = S / (2K) ^ (l+1)
+        //
+        // We don't actually have infinite levels here since we _can_ easily
+        // cap to a fixed max depth, so this will be a minor underestimate. We
+        // also clamp all probabilities to 0.9 to ensure that we can't end up
+        // with levels which are always pure branches, which further
+        // underestimates size.
+
+        let mut branch_probabilities = Vec::new();
+        let mut k2 = u64::from(self.expected_branch_size) * 2;
+        for _ in 0..self.depth {
+            branch_probabilities.push(f64::from(self.desired_size) / k2 as f64);
+            k2 = k2.saturating_mul(u64::from(self.expected_branch_size) * 2);
+        }
+
+        let mut strat = self.base.clone();
+        while let Some(branch_probability) = branch_probabilities.pop() {
+            let recursed = (self.recurse)(strat.clone());
+            let recursive_choice = recursed.boxed();
+            let non_recursive_choice = strat;
+            // Clamp the maximum branch probability to 0.9 to ensure we can
+            // generate non-recursive cases reasonably often.
+            let branch_probability = branch_probability.min(0.9);
+            let (weight_branch, weight_leaf) =
+                float_to_weight(branch_probability);
+            let branch = prop_oneof![
+                weight_leaf => non_recursive_choice,
+                weight_branch => recursive_choice,
+            ];
+            strat = branch.boxed();
+        }
+
+        strat.new_tree(runner)
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use std::cmp::max;
+
+    use super::*;
+    use crate::strategy::just::Just;
+
+    #[derive(Clone, Debug, PartialEq)]
+    enum Tree {
+        Leaf,
+        Branch(Vec<Tree>),
+    }
+
+    impl Tree {
+        fn stats(&self) -> (u32, u32) {
+            match *self {
+                Tree::Leaf => (0, 1),
+                Tree::Branch(ref children) => {
+                    let mut depth = 0;
+                    let mut count = 0;
+                    for child in children {
+                        let (d, c) = child.stats();
+                        depth = max(d, depth);
+                        count += c;
+                    }
+
+                    (depth + 1, count + 1)
+                }
+            }
+        }
+    }
+
+    #[test]
+    fn test_recursive() {
+        let mut max_depth = 0;
+        let mut max_count = 0;
+
+        let strat = Just(Tree::Leaf).prop_recursive(4, 64, 16, |element| {
+            crate::collection::vec(element, 8..16).prop_map(Tree::Branch)
+        });
+
+        let mut runner = TestRunner::deterministic();
+        for _ in 0..65536 {
+            let tree = strat.new_tree(&mut runner).unwrap().current();
+            let (depth, count) = tree.stats();
+            assert!(depth <= 4, "Got depth {}", depth);
+            assert!(count <= 128, "Got count {}", count);
+            max_depth = max(depth, max_depth);
+            max_count = max(count, max_count);
+        }
+
+        assert!(max_depth >= 3, "Only got max depth {}", max_depth);
+        assert!(max_count > 48, "Only got max count {}", max_count);
+    }
+
+    #[test]
+    fn simplifies_to_non_recursive() {
+        let strat = Just(Tree::Leaf).prop_recursive(4, 64, 16, |element| {
+            crate::collection::vec(element, 8..16).prop_map(Tree::Branch)
+        });
+
+        let mut runner = TestRunner::deterministic();
+        for _ in 0..256 {
+            let mut value = strat.new_tree(&mut runner).unwrap();
+            while value.simplify() {}
+
+            assert_eq!(Tree::Leaf, value.current());
+        }
+    }
+}
diff --git a/vendor/proptest/src/strategy/shuffle.rs b/vendor/proptest/src/strategy/shuffle.rs
new file mode 100644
index 000000000..b94a73c3b
--- /dev/null
+++ b/vendor/proptest/src/strategy/shuffle.rs
@@ -0,0 +1,287 @@
+//-
+// 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 crate::std_facade::{Cell, Vec, VecDeque};
+
+use rand::Rng;
+
+use crate::num;
+use crate::strategy::traits::*;
+use crate::test_runner::*;
+
+/// `Strategy` shuffle adaptor.
+///
+/// See `Strategy::prop_shuffle()`.
+#[derive(Clone, Debug)]
+#[must_use = "strategies do nothing unless used"]
+pub struct Shuffle<S>(pub(super) S);
+
+/// A value which can be used with the `prop_shuffle` combinator.
+///
+/// This is not a general-purpose trait. Its methods are prefixed with
+/// `shuffle_` to avoid the compiler suggesting them or this trait as
+/// corrections in errors.
+pub trait Shuffleable {
+    /// Return the length of this collection.
+    fn shuffle_len(&self) -> usize;
+    /// Swap the elements at the given indices.
+    fn shuffle_swap(&mut self, a: usize, b: usize);
+}
+
+macro_rules! shuffleable {
+    ($($t:tt)*) => {
+        impl<T> Shuffleable for $($t)* {
+            fn shuffle_len(&self) -> usize {
+                self.len()
+            }
+
+            fn shuffle_swap(&mut self, a: usize, b: usize) {
+                self.swap(a, b);
+            }
+        }
+    }
+}
+
+shuffleable!([T]);
+shuffleable!(Vec<T>);
+shuffleable!(VecDeque<T>);
+// Zero- and 1-length arrays aren't usefully shuffleable, but are included to
+// simplify external macros that may try to use them anyway.
+shuffleable!([T; 0]);
+shuffleable!([T; 1]);
+shuffleable!([T; 2]);
+shuffleable!([T; 3]);
+shuffleable!([T; 4]);
+shuffleable!([T; 5]);
+shuffleable!([T; 6]);
+shuffleable!([T; 7]);
+shuffleable!([T; 8]);
+shuffleable!([T; 9]);
+shuffleable!([T; 10]);
+shuffleable!([T; 11]);
+shuffleable!([T; 12]);
+shuffleable!([T; 13]);
+shuffleable!([T; 14]);
+shuffleable!([T; 15]);
+shuffleable!([T; 16]);
+shuffleable!([T; 17]);
+shuffleable!([T; 18]);
+shuffleable!([T; 19]);
+shuffleable!([T; 20]);
+shuffleable!([T; 21]);
+shuffleable!([T; 22]);
+shuffleable!([T; 23]);
+shuffleable!([T; 24]);
+shuffleable!([T; 25]);
+shuffleable!([T; 26]);
+shuffleable!([T; 27]);
+shuffleable!([T; 28]);
+shuffleable!([T; 29]);
+shuffleable!([T; 30]);
+shuffleable!([T; 31]);
+shuffleable!([T; 32]);
+
+impl<S: Strategy> Strategy for Shuffle<S>
+where
+    S::Value: Shuffleable,
+{
+    type Tree = ShuffleValueTree<S::Tree>;
+    type Value = S::Value;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        let rng = runner.new_rng();
+
+        self.0.new_tree(runner).map(|inner| ShuffleValueTree {
+            inner,
+            rng,
+            dist: Cell::new(None),
+            simplifying_inner: false,
+        })
+    }
+}
+
+/// `ValueTree` shuffling adaptor.
+///
+/// See `Strategy::prop_shuffle()`.
+#[derive(Clone, Debug)]
+pub struct ShuffleValueTree<V> {
+    inner: V,
+    rng: TestRng,
+    /// The maximum amount to move any one element during shuffling.
+    ///
+    /// This is `Cell` since we can't determine the bounds of the value until
+    /// the first call to `current()`. (We technically _could_ by generating a
+    /// value in `new_tree` and checking its length, but that would be a 100%
+    /// slowdown.)
+    dist: Cell<Option<num::usize::BinarySearch>>,
+    /// Whether we've started simplifying `inner`. After this point, we can no
+    /// longer simplify or complicate `dist`.
+    simplifying_inner: bool,
+}
+
+impl<V: ValueTree> ShuffleValueTree<V>
+where
+    V::Value: Shuffleable,
+{
+    fn init_dist(&self, dflt: usize) -> usize {
+        if self.dist.get().is_none() {
+            self.dist.set(Some(num::usize::BinarySearch::new(dflt)));
+        }
+
+        self.dist.get().unwrap().current()
+    }
+
+    fn force_init_dist(&self) {
+        if self.dist.get().is_none() {
+            self.init_dist(self.current().shuffle_len());
+        }
+    }
+}
+
+impl<V: ValueTree> ValueTree for ShuffleValueTree<V>
+where
+    V::Value: Shuffleable,
+{
+    type Value = V::Value;
+
+    fn current(&self) -> V::Value {
+        let mut value = self.inner.current();
+        let len = value.shuffle_len();
+        // The maximum distance to swap elements. This could be larger than
+        // `value` if `value` has reduced size during shrinking; that's OK,
+        // since we only use this to filter swaps.
+        let max_swap = self.init_dist(len);
+
+        // If empty collection or all swaps will be filtered out, there's
+        // nothing to shuffle.
+        if 0 == len || 0 == max_swap {
+            return value;
+        }
+
+        let mut rng = self.rng.clone();
+
+        for start_index in 0..len - 1 {
+            // Determine the other index to be swapped, then skip the swap if
+            // it is too far. This ordering is critical, as it ensures that we
+            // generate the same sequence of random numbers every time.
+            let end_index = rng.gen_range(start_index..len);
+            if end_index - start_index <= max_swap {
+                value.shuffle_swap(start_index, end_index);
+            }
+        }
+
+        value
+    }
+
+    fn simplify(&mut self) -> bool {
+        if self.simplifying_inner {
+            self.inner.simplify()
+        } else {
+            // Ensure that we've initialised `dist` to *something* to give
+            // consistent non-panicking behaviour even if called in an
+            // unexpected sequence.
+            self.force_init_dist();
+            if self.dist.get_mut().as_mut().unwrap().simplify() {
+                true
+            } else {
+                self.simplifying_inner = true;
+                self.inner.simplify()
+            }
+        }
+    }
+
+    fn complicate(&mut self) -> bool {
+        if self.simplifying_inner {
+            self.inner.complicate()
+        } else {
+            self.force_init_dist();
+            self.dist.get_mut().as_mut().unwrap().complicate()
+        }
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use std::borrow::ToOwned;
+    use std::collections::HashSet;
+    use std::i32;
+
+    use super::*;
+    use crate::collection;
+    use crate::strategy::just::Just;
+
+    static VALUES: &'static [i32] = &[
+        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
+    ];
+
+    #[test]
+    fn generates_different_permutations() {
+        let mut runner = TestRunner::default();
+        let mut seen = HashSet::<Vec<i32>>::new();
+
+        let input = Just(VALUES.to_owned()).prop_shuffle();
+
+        for _ in 0..1024 {
+            let mut value = input.new_tree(&mut runner).unwrap().current();
+
+            assert!(
+                seen.insert(value.clone()),
+                "Value {:?} generated more than once",
+                value
+            );
+
+            value.sort();
+            assert_eq!(VALUES, &value[..]);
+        }
+    }
+
+    #[test]
+    fn simplify_reduces_shuffle_amount() {
+        let mut runner = TestRunner::default();
+
+        let input = Just(VALUES.to_owned()).prop_shuffle();
+        for _ in 0..1024 {
+            let mut value = input.new_tree(&mut runner).unwrap();
+
+            let mut prev_dist = i32::MAX;
+            loop {
+                let v = value.current();
+                // Compute the "shuffle distance" by summing the absolute
+                // distance of each element's displacement.
+                let mut dist = 0;
+                for (ix, &nominal) in v.iter().enumerate() {
+                    dist += (nominal - ix as i32).abs();
+                }
+
+                assert!(
+                    dist <= prev_dist,
+                    "dist = {}, prev_dist = {}",
+                    dist,
+                    prev_dist
+                );
+
+                prev_dist = dist;
+                if !value.simplify() {
+                    break;
+                }
+            }
+
+            // When fully simplified, the result is in the original order.
+            assert_eq!(0, prev_dist);
+        }
+    }
+
+    #[test]
+    fn simplify_complicate_contract_upheld() {
+        check_strategy_sanity(
+            collection::vec(0i32..1000, 5..10).prop_shuffle(),
+            None,
+        );
+    }
+}
diff --git a/vendor/proptest/src/strategy/statics.rs b/vendor/proptest/src/strategy/statics.rs
new file mode 100644
index 000000000..978dc13b9
--- /dev/null
+++ b/vendor/proptest/src/strategy/statics.rs
@@ -0,0 +1,266 @@
+//-
+// 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.
+
+//! Modified versions of the normal strategy combinators which take specialised
+//! traits instead of normal functions.
+//!
+//! This entire module is strictly a workaround until
+//! <https://github.com/rust-lang/rfcs/pull/1522> and
+//! <https://github.com/rust-lang/rfcs/pull/2071> are available in stable. It
+//! allows naming types built on the combinators without resorting to dynamic
+//! dispatch or causing `Arc` to allocate space for a function pointer.
+//!
+//! External code is discouraged from using this module directly. It is
+//! deliberately not exposed in a convenient way (i.e., via the `Strategy`
+//! trait itself), but is nonetheless exposed since external trait implementors
+//! may face the same issues.
+//!
+//! **This module is subject to removal at some point after the language
+//! features linked above become stable.**
+
+use crate::std_facade::fmt;
+
+use crate::strategy::traits::*;
+use crate::test_runner::*;
+
+//==============================================================================
+// Filter
+//==============================================================================
+
+/// Essentially `Fn (&T) -> bool`.
+pub trait FilterFn<T> {
+    /// Test whether `t` passes the filter.
+    fn apply(&self, t: &T) -> bool;
+}
+
+/// Static version of `strategy::Filter`.
+#[derive(Clone)]
+#[must_use = "strategies do nothing unless used"]
+pub struct Filter<S, F> {
+    source: S,
+    whence: Reason,
+    fun: F,
+}
+
+impl<S, F> Filter<S, F> {
+    /// Adapt strategy `source` to reject values which do not pass `filter`,
+    /// using `whence` as the reported reason/location.
+    pub fn new(source: S, whence: Reason, filter: F) -> Self {
+        // NOTE: We don't use universal quantification R: Into<Reason>
+        // since the module is not conveniently exposed.
+        Filter {
+            source,
+            whence,
+            fun: filter,
+        }
+    }
+}
+
+impl<S: fmt::Debug, F> fmt::Debug for Filter<S, F> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("Filter")
+            .field("source", &self.source)
+            .field("whence", &self.whence)
+            .field("fun", &"<function>")
+            .finish()
+    }
+}
+
+impl<S: Strategy, F: FilterFn<S::Value> + Clone> Strategy for Filter<S, F> {
+    type Tree = Filter<S::Tree, F>;
+    type Value = S::Value;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        loop {
+            let val = self.source.new_tree(runner)?;
+            if !self.fun.apply(&val.current()) {
+                runner.reject_local(self.whence.clone())?;
+            } else {
+                return Ok(Filter {
+                    source: val,
+                    whence: "unused".into(),
+                    fun: self.fun.clone(),
+                });
+            }
+        }
+    }
+}
+
+impl<S: ValueTree, F: FilterFn<S::Value>> Filter<S, F> {
+    fn ensure_acceptable(&mut self) {
+        while !self.fun.apply(&self.source.current()) {
+            if !self.source.complicate() {
+                panic!(
+                    "Unable to complicate filtered strategy \
+                     back into acceptable value"
+                );
+            }
+        }
+    }
+}
+
+impl<S: ValueTree, F: FilterFn<S::Value>> ValueTree for Filter<S, F> {
+    type Value = S::Value;
+
+    fn current(&self) -> S::Value {
+        self.source.current()
+    }
+
+    fn simplify(&mut self) -> bool {
+        if self.source.simplify() {
+            self.ensure_acceptable();
+            true
+        } else {
+            false
+        }
+    }
+
+    fn complicate(&mut self) -> bool {
+        if self.source.complicate() {
+            self.ensure_acceptable();
+            true
+        } else {
+            false
+        }
+    }
+}
+
+//==============================================================================
+// Map
+//==============================================================================
+
+/// Essentially `Fn (T) -> Output`.
+pub trait MapFn<T> {
+    #[allow(missing_docs)]
+    type Output: fmt::Debug;
+
+    /// Map `T` to `Output`.
+    fn apply(&self, t: T) -> Self::Output;
+}
+
+/// Static version of `strategy::Map`.
+#[derive(Clone)]
+#[must_use = "strategies do nothing unless used"]
+pub struct Map<S, F> {
+    source: S,
+    fun: F,
+}
+
+impl<S, F> Map<S, F> {
+    /// Adapt strategy `source` by applying `fun` to values it produces.
+    pub fn new(source: S, fun: F) -> Self {
+        Map { source, fun }
+    }
+}
+
+impl<S: fmt::Debug, F> fmt::Debug for Map<S, F> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("Map")
+            .field("source", &self.source)
+            .field("fun", &"<function>")
+            .finish()
+    }
+}
+
+impl<S: Strategy, F: Clone + MapFn<S::Value>> Strategy for Map<S, F> {
+    type Tree = Map<S::Tree, F>;
+    type Value = F::Output;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        self.source.new_tree(runner).map(|v| Map {
+            source: v,
+            fun: self.fun.clone(),
+        })
+    }
+}
+
+impl<S: ValueTree, F: MapFn<S::Value>> ValueTree for Map<S, F> {
+    type Value = F::Output;
+
+    fn current(&self) -> F::Output {
+        self.fun.apply(self.source.current())
+    }
+
+    fn simplify(&mut self) -> bool {
+        self.source.simplify()
+    }
+
+    fn complicate(&mut self) -> bool {
+        self.source.complicate()
+    }
+}
+
+impl<I, O: fmt::Debug> MapFn<I> for fn(I) -> O {
+    type Output = O;
+    fn apply(&self, x: I) -> Self::Output {
+        self(x)
+    }
+}
+
+pub(crate) fn static_map<S: Strategy, O: fmt::Debug>(
+    strat: S,
+    fun: fn(S::Value) -> O,
+) -> Map<S, fn(S::Value) -> O> {
+    Map::new(strat, fun)
+}
+
+//==============================================================================
+// Tests
+//==============================================================================
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    #[test]
+    fn test_static_filter() {
+        #[derive(Clone, Copy, Debug)]
+        struct MyFilter;
+        impl FilterFn<i32> for MyFilter {
+            fn apply(&self, &v: &i32) -> bool {
+                0 == v % 3
+            }
+        }
+
+        let input = Filter::new(0..256, "%3".into(), MyFilter);
+
+        for _ in 0..256 {
+            let mut runner = TestRunner::default();
+            let mut case = input.new_tree(&mut runner).unwrap();
+
+            assert!(0 == case.current() % 3);
+
+            while case.simplify() {
+                assert!(0 == case.current() % 3);
+            }
+            assert!(0 == case.current() % 3);
+        }
+    }
+
+    #[test]
+    fn test_static_map() {
+        #[derive(Clone, Copy, Debug)]
+        struct MyMap;
+        impl MapFn<i32> for MyMap {
+            type Output = i32;
+            fn apply(&self, v: i32) -> i32 {
+                v * 2
+            }
+        }
+
+        let input = Map::new(0..10, MyMap);
+
+        TestRunner::default()
+            .run(&input, |v| {
+                assert!(0 == v % 2);
+                Ok(())
+            })
+            .unwrap();
+    }
+}
diff --git a/vendor/proptest/src/strategy/traits.rs b/vendor/proptest/src/strategy/traits.rs
new file mode 100644
index 000000000..bcad20a1e
--- /dev/null
+++ b/vendor/proptest/src/strategy/traits.rs
@@ -0,0 +1,1054 @@
+//-
+// 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.
+
+use crate::std_facade::{fmt, Arc, Box, Rc};
+use core::cmp;
+
+use crate::strategy::*;
+use crate::test_runner::*;
+
+//==============================================================================
+// Traits
+//==============================================================================
+
+/// A new [`ValueTree`] from a [`Strategy`] when [`Ok`] or otherwise [`Err`]
+/// when a new value-tree can not be produced for some reason such as
+/// in the case of filtering with a predicate which always returns false.
+/// You should pass in your strategy as the type parameter.
+///
+/// [`Strategy`]: trait.Strategy.html
+/// [`ValueTree`]: trait.ValueTree.html
+/// [`Ok`]: https://doc.rust-lang.org/nightly/std/result/enum.Result.html#variant.Ok
+/// [`Err`]: https://doc.rust-lang.org/nightly/std/result/enum.Result.html#variant.Err
+pub type NewTree<S> = Result<<S as Strategy>::Tree, Reason>;
+
+/// A strategy for producing arbitrary values of a given type.
+///
+/// `fmt::Debug` is a hard requirement for all strategies currently due to
+/// `prop_flat_map()`. This constraint will be removed when specialisation
+/// becomes stable.
+#[must_use = "strategies do nothing unless used"]
+pub trait Strategy: fmt::Debug {
+    /// The value tree generated by this `Strategy`.
+    type Tree: ValueTree<Value = Self::Value>;
+
+    /// The type of value used by functions under test generated by this Strategy.
+    ///
+    /// This corresponds to the same type as the associated type `Value`
+    /// in `Self::Tree`. It is provided here to simplify usage particularly
+    /// in conjunction with `-> impl Strategy<Value = MyType>`.
+    type Value: fmt::Debug;
+
+    /// Generate a new value tree from the given runner.
+    ///
+    /// This may fail if there are constraints on the generated value and the
+    /// generator is unable to produce anything that satisfies them. Any
+    /// failure is wrapped in `TestError::Abort`.
+    ///
+    /// This method is generally expected to be deterministic. That is, given a
+    /// `TestRunner` with its RNG in a particular state, this should produce an
+    /// identical `ValueTree` every time. Non-deterministic strategies do not
+    /// cause problems during normal operation, but they do break failure
+    /// persistence since it is implemented by simply saving the seed used to
+    /// generate the test case.
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self>;
+
+    /// Returns a strategy which produces values transformed by the function
+    /// `fun`.
+    ///
+    /// There is no need (or possibility, for that matter) to define how the
+    /// output is to be shrunken. Shrinking continues to take place in terms of
+    /// the source value.
+    ///
+    /// `fun` should be a deterministic function. That is, for a given input
+    /// value, it should produce an equivalent output value on every call.
+    /// Proptest assumes that it can call the function as many times as needed
+    /// to generate as many identical values as needed. For this reason, `F` is
+    /// `Fn` rather than `FnMut`.
+    fn prop_map<O: fmt::Debug, F: Fn(Self::Value) -> O>(
+        self,
+        fun: F,
+    ) -> Map<Self, F>
+    where
+        Self: Sized,
+    {
+        Map {
+            source: self,
+            fun: Arc::new(fun),
+        }
+    }
+
+    /// Returns a strategy which produces values of type `O` by transforming
+    /// `Self` with `Into<O>`.
+    ///
+    /// You should always prefer this operation instead of `prop_map` when
+    /// you can as it is both clearer and also currently more efficient.
+    ///
+    /// There is no need (or possibility, for that matter) to define how the
+    /// output is to be shrunken. Shrinking continues to take place in terms of
+    /// the source value.
+    fn prop_map_into<O: fmt::Debug>(self) -> MapInto<Self, O>
+    where
+        Self: Sized,
+        Self::Value: Into<O>,
+    {
+        MapInto::new(self)
+    }
+
+    /// Returns a strategy which produces values transformed by the function
+    /// `fun`, which is additionally given a random number generator.
+    ///
+    /// This is exactly like `prop_map()` except for the addition of the second
+    /// argument to the function. This allows introducing chaotic variations to
+    /// generated values that are not easily expressed otherwise while allowing
+    /// shrinking to proceed reasonably.
+    ///
+    /// During shrinking, `fun` is always called with an identical random
+    /// number generator, so if it is a pure function it will always perform
+    /// the same perturbation.
+    ///
+    /// ## Example
+    ///
+    /// ```
+    /// // The prelude also gets us the `Rng` trait.
+    /// use proptest::prelude::*;
+    ///
+    /// proptest! {
+    ///   #[test]
+    ///   fn test_something(a in (0i32..10).prop_perturb(
+    ///       // Perturb the integer `a` (range 0..10) to a pair of that
+    ///       // integer and another that's ± 10 of it.
+    ///       // Note that this particular case would be better implemented as
+    ///       // `(0i32..10, -10i32..10).prop_map(|(a, b)| (a, a + b))`
+    ///       // but is shown here for simplicity.
+    ///       |centre, rng| (centre, centre + rng.gen_range(-10, 10))))
+    ///   {
+    ///       // Test stuff
+    ///   }
+    /// }
+    /// # fn main() { }
+    /// ```
+    fn prop_perturb<O: fmt::Debug, F: Fn(Self::Value, TestRng) -> O>(
+        self,
+        fun: F,
+    ) -> Perturb<Self, F>
+    where
+        Self: Sized,
+    {
+        Perturb {
+            source: self,
+            fun: Arc::new(fun),
+        }
+    }
+
+    /// Maps values produced by this strategy into new strategies and picks
+    /// values from those strategies.
+    ///
+    /// `fun` is used to transform the values produced by this strategy into
+    /// other strategies. Values are then chosen from the derived strategies.
+    /// Shrinking proceeds by shrinking individual values as well as shrinking
+    /// the input used to generate the internal strategies.
+    ///
+    /// ## Shrinking
+    ///
+    /// In the case of test failure, shrinking will not only shrink the output
+    /// from the combinator itself, but also the input, i.e., the strategy used
+    /// to generate the output itself. Doing this requires searching the new
+    /// derived strategy for a new failing input. The combinator will generate
+    /// up to `Config::cases` values for this search.
+    ///
+    /// As a result, nested `prop_flat_map`/`Flatten` combinators risk
+    /// exponential run time on this search for new failing values. To ensure
+    /// that test failures occur within a reasonable amount of time, all of
+    /// these combinators share a single "flat map regen" counter, and will
+    /// stop generating new values if it exceeds `Config::max_flat_map_regens`.
+    ///
+    /// ## Example
+    ///
+    /// Generate two integers, where the second is always less than the first,
+    /// without using filtering:
+    ///
+    /// ```
+    /// use proptest::prelude::*;
+    ///
+    /// proptest! {
+    ///   # /*
+    ///   #[test]
+    ///   # */
+    ///   fn test_two(
+    ///     // Pick integers in the 1..65536 range, and derive a strategy
+    ///     // which emits a tuple of that integer and another one which is
+    ///     // some value less than it.
+    ///     (a, b) in (1..65536).prop_flat_map(|a| (Just(a), 0..a))
+    ///   ) {
+    ///     prop_assert!(b < a);
+    ///   }
+    /// }
+    /// #
+    /// # fn main() { test_two(); }
+    /// ```
+    ///
+    /// ## Choosing the right flat-map
+    ///
+    /// `Strategy` has three "flat-map" combinators. They look very similar at
+    /// first, and can be used to produce superficially identical test results.
+    /// For example, the following three expressions all produce inputs which
+    /// are 2-tuples `(a,b)` where the `b` component is less than `a`.
+    ///
+    /// ```no_run
+    /// # #![allow(unused_variables)]
+    /// use proptest::prelude::*;
+    ///
+    /// let flat_map = (1..10).prop_flat_map(|a| (Just(a), 0..a));
+    /// let ind_flat_map = (1..10).prop_ind_flat_map(|a| (Just(a), 0..a));
+    /// let ind_flat_map2 = (1..10).prop_ind_flat_map2(|a| 0..a);
+    /// ```
+    ///
+    /// The three do differ however in terms of how they shrink.
+    ///
+    /// For `flat_map`, both `a` and `b` will shrink, and the invariant that
+    /// `b < a` is maintained. This is a "dependent" or "higher-order" strategy
+    /// in that it remembers that the strategy for choosing `b` is dependent on
+    /// the value chosen for `a`.
+    ///
+    /// For `ind_flat_map`, the invariant `b < a` is maintained, but only
+    /// because `a` does not shrink. This is due to the fact that the
+    /// dependency between the strategies is not tracked; `a` is simply seen as
+    /// a constant.
+    ///
+    /// Finally, for `ind_flat_map2`, the invariant `b < a` is _not_
+    /// maintained, because `a` can shrink independently of `b`, again because
+    /// the dependency between the two variables is not tracked, but in this
+    /// case the derivation of `a` is still exposed to the shrinking system.
+    ///
+    /// The use-cases for the independent flat-map variants is pretty narrow.
+    /// For the majority of cases where invariants need to be maintained and
+    /// you want all components to shrink, `prop_flat_map` is the way to go.
+    /// `prop_ind_flat_map` makes the most sense when the input to the map
+    /// function is not exposed in the output and shrinking across strategies
+    /// is not expected to be useful. `prop_ind_flat_map2` is useful for using
+    /// related values as starting points while not constraining them to that
+    /// relation.
+    fn prop_flat_map<S: Strategy, F: Fn(Self::Value) -> S>(
+        self,
+        fun: F,
+    ) -> Flatten<Map<Self, F>>
+    where
+        Self: Sized,
+    {
+        Flatten::new(Map {
+            source: self,
+            fun: Arc::new(fun),
+        })
+    }
+
+    /// Maps values produced by this strategy into new strategies and picks
+    /// values from those strategies while considering the new strategies to be
+    /// independent.
+    ///
+    /// This is very similar to `prop_flat_map()`, but shrinking will *not*
+    /// attempt to shrink the input that produces the derived strategies. This
+    /// is appropriate for when the derived strategies already fully shrink in
+    /// the desired way.
+    ///
+    /// In most cases, you want `prop_flat_map()`.
+    ///
+    /// See `prop_flat_map()` for a more detailed explanation on how the
+    /// three flat-map combinators differ.
+    fn prop_ind_flat_map<S: Strategy, F: Fn(Self::Value) -> S>(
+        self,
+        fun: F,
+    ) -> IndFlatten<Map<Self, F>>
+    where
+        Self: Sized,
+    {
+        IndFlatten(Map {
+            source: self,
+            fun: Arc::new(fun),
+        })
+    }
+
+    /// Similar to `prop_ind_flat_map()`, but produces 2-tuples with the input
+    /// generated from `self` in slot 0 and the derived strategy in slot 1.
+    ///
+    /// See `prop_flat_map()` for a more detailed explanation on how the
+    /// three flat-map combinators differ.
+    fn prop_ind_flat_map2<S: Strategy, F: Fn(Self::Value) -> S>(
+        self,
+        fun: F,
+    ) -> IndFlattenMap<Self, F>
+    where
+        Self: Sized,
+    {
+        IndFlattenMap {
+            source: self,
+            fun: Arc::new(fun),
+        }
+    }
+
+    /// Returns a strategy which only produces values accepted by `fun`.
+    ///
+    /// This results in a very naïve form of rejection sampling and should only
+    /// be used if (a) relatively few values will actually be rejected; (b) it
+    /// isn't easy to express what you want by using another strategy and/or
+    /// `map()`.
+    ///
+    /// There are a lot of downsides to this form of filtering. It slows
+    /// testing down, since values must be generated but then discarded.
+    /// Proptest only allows a limited number of rejects this way (across the
+    /// entire `TestRunner`). Rejection can interfere with shrinking;
+    /// particularly, complex filters may largely or entirely prevent shrinking
+    /// from substantially altering the original value.
+    ///
+    /// Local rejection sampling is still preferable to rejecting the entire
+    /// input to a test (via `TestCaseError::Reject`), however, and the default
+    /// number of local rejections allowed is much higher than the number of
+    /// whole-input rejections.
+    ///
+    /// `whence` is used to record where and why the rejection occurred.
+    fn prop_filter<R: Into<Reason>, F: Fn(&Self::Value) -> bool>(
+        self,
+        whence: R,
+        fun: F,
+    ) -> Filter<Self, F>
+    where
+        Self: Sized,
+    {
+        Filter::new(self, whence.into(), fun)
+    }
+
+    /// Returns a strategy which only produces transformed values where `fun`
+    /// returns `Some(value)` and rejects those where `fun` returns `None`.
+    ///
+    /// Using this method is preferable to using `.prop_map(..).prop_filter(..)`.
+    ///
+    /// This results in a very naïve form of rejection sampling and should only
+    /// be used if (a) relatively few values will actually be rejected; (b) it
+    /// isn't easy to express what you want by using another strategy and/or
+    /// `map()`.
+    ///
+    /// There are a lot of downsides to this form of filtering. It slows
+    /// testing down, since values must be generated but then discarded.
+    /// Proptest only allows a limited number of rejects this way (across the
+    /// entire `TestRunner`). Rejection can interfere with shrinking;
+    /// particularly, complex filters may largely or entirely prevent shrinking
+    /// from substantially altering the original value.
+    ///
+    /// Local rejection sampling is still preferable to rejecting the entire
+    /// input to a test (via `TestCaseError::Reject`), however, and the default
+    /// number of local rejections allowed is much higher than the number of
+    /// whole-input rejections.
+    ///
+    /// `whence` is used to record where and why the rejection occurred.
+    fn prop_filter_map<F: Fn(Self::Value) -> Option<O>, O: fmt::Debug>(
+        self,
+        whence: impl Into<Reason>,
+        fun: F,
+    ) -> FilterMap<Self, F>
+    where
+        Self: Sized,
+    {
+        FilterMap::new(self, whence.into(), fun)
+    }
+
+    /// Returns a strategy which picks uniformly from `self` and `other`.
+    ///
+    /// When shrinking, if a value from `other` was originally chosen but that
+    /// value can be shrunken no further, it switches to a value from `self`
+    /// and starts shrinking that.
+    ///
+    /// Be aware that chaining `prop_union` calls will result in a very
+    /// right-skewed distribution. If this is not what you want, you can call
+    /// the `.or()` method on the `Union` to add more values to the same union,
+    /// or directly call `Union::new()`.
+    ///
+    /// Both `self` and `other` must be of the same type. To combine
+    /// heterogeneous strategies, call the `boxed()` method on both `self` and
+    /// `other` to erase the type differences before calling `prop_union()`.
+    fn prop_union(self, other: Self) -> Union<Self>
+    where
+        Self: Sized,
+    {
+        Union::new(vec![self, other])
+    }
+
+    /// Generate a recursive structure with `self` items as leaves.
+    ///
+    /// `recurse` is applied to various strategies that produce the same type
+    /// as `self` with nesting depth _n_ to create a strategy that produces the
+    /// same type with nesting depth _n+1_. Generated structures will have a
+    /// depth between 0 and `depth` and will usually have up to `desired_size`
+    /// total elements, though they may have more. `expected_branch_size` gives
+    /// the expected maximum size for any collection which may contain
+    /// recursive elements and is used to control branch probability to achieve
+    /// the desired size. Passing a too small value can result in trees vastly
+    /// larger than desired.
+    ///
+    /// Note that `depth` only counts branches; i.e., `depth = 0` is a single
+    /// leaf, and `depth = 1` is a leaf or a branch containing only leaves.
+    ///
+    /// In practise, generated values usually have a lower depth than `depth`
+    /// (but `depth` is a hard limit) and almost always under
+    /// `expected_branch_size` (though it is not a hard limit) since the
+    /// underlying code underestimates probabilities.
+    ///
+    /// Shrinking shrinks both the inner values and attempts switching from
+    /// recursive to non-recursive cases.
+    ///
+    /// ## Example
+    ///
+    /// ```rust,no_run
+    /// # #![allow(unused_variables)]
+    /// use std::collections::HashMap;
+    ///
+    /// use proptest::prelude::*;
+    ///
+    /// /// Define our own JSON AST type
+    /// #[derive(Debug, Clone)]
+    /// enum JsonNode {
+    ///   Null,
+    ///   Bool(bool),
+    ///   Number(f64),
+    ///   String(String),
+    ///   Array(Vec<JsonNode>),
+    ///   Map(HashMap<String, JsonNode>),
+    /// }
+    ///
+    /// # fn main() {
+    /// #
+    /// // Define a strategy for generating leaf nodes of the AST
+    /// let json_leaf = prop_oneof![
+    ///   Just(JsonNode::Null),
+    ///   prop::bool::ANY.prop_map(JsonNode::Bool),
+    ///   prop::num::f64::ANY.prop_map(JsonNode::Number),
+    ///   ".*".prop_map(JsonNode::String),
+    /// ];
+    ///
+    /// // Now define a strategy for a whole tree
+    /// let json_tree = json_leaf.prop_recursive(
+    ///   4, // No more than 4 branch levels deep
+    ///   64, // Target around 64 total elements
+    ///   16, // Each collection is up to 16 elements long
+    ///   |element| prop_oneof![
+    ///     // NB `element` is an `Arc` and we'll need to reference it twice,
+    ///     // so we clone it the first time.
+    ///     prop::collection::vec(element.clone(), 0..16)
+    ///       .prop_map(JsonNode::Array),
+    ///     prop::collection::hash_map(".*", element, 0..16)
+    ///       .prop_map(JsonNode::Map)
+    ///   ]);
+    /// # }
+    /// ```
+    fn prop_recursive<
+        R: Strategy<Value = Self::Value> + 'static,
+        F: Fn(BoxedStrategy<Self::Value>) -> R,
+    >(
+        self,
+        depth: u32,
+        desired_size: u32,
+        expected_branch_size: u32,
+        recurse: F,
+    ) -> Recursive<Self::Value, F>
+    where
+        Self: Sized + 'static,
+    {
+        Recursive::new(self, depth, desired_size, expected_branch_size, recurse)
+    }
+
+    /// Shuffle the contents of the values produced by this strategy.
+    ///
+    /// That is, this modifies a strategy producing a `Vec`, slice, etc, to
+    /// shuffle the contents of that `Vec`/slice/etc.
+    ///
+    /// Initially, the value is fully shuffled. During shrinking, the input
+    /// value will initially be unchanged while the result will gradually be
+    /// restored to its original order. Once de-shuffling either completes or
+    /// is cancelled by calls to `complicate()` pinning it to a particular
+    /// permutation, the inner value will be simplified.
+    ///
+    /// ## Example
+    ///
+    /// ```
+    /// use proptest::prelude::*;
+    ///
+    /// static VALUES: &'static [u32] = &[0, 1, 2, 3, 4];
+    ///
+    /// fn is_permutation(orig: &[u32], mut actual: Vec<u32>) -> bool {
+    ///   actual.sort();
+    ///   orig == &actual[..]
+    /// }
+    ///
+    /// proptest! {
+    ///   # /*
+    ///   #[test]
+    ///   # */
+    ///   fn test_is_permutation(
+    ///       ref perm in Just(VALUES.to_owned()).prop_shuffle()
+    ///   ) {
+    ///       assert!(is_permutation(VALUES, perm.clone()));
+    ///   }
+    /// }
+    /// #
+    /// # fn main() { test_is_permutation(); }
+    /// ```
+    fn prop_shuffle(self) -> Shuffle<Self>
+    where
+        Self: Sized,
+        Self::Value: Shuffleable,
+    {
+        Shuffle(self)
+    }
+
+    /// Erases the type of this `Strategy` so it can be passed around as a
+    /// simple trait object.
+    ///
+    /// See also `sboxed()` if this `Strategy` is `Send` and `Sync` and you
+    /// want to preserve that information.
+    ///
+    /// Strategies of this type afford cheap shallow cloning via reference
+    /// counting by using an `Arc` internally.
+    fn boxed(self) -> BoxedStrategy<Self::Value>
+    where
+        Self: Sized + 'static,
+    {
+        BoxedStrategy(Arc::new(BoxedStrategyWrapper(self)))
+    }
+
+    /// Erases the type of this `Strategy` so it can be passed around as a
+    /// simple trait object.
+    ///
+    /// Unlike `boxed()`, this conversion retains the `Send` and `Sync` traits
+    /// on the output.
+    ///
+    /// Strategies of this type afford cheap shallow cloning via reference
+    /// counting by using an `Arc` internally.
+    fn sboxed(self) -> SBoxedStrategy<Self::Value>
+    where
+        Self: Sized + Send + Sync + 'static,
+    {
+        SBoxedStrategy(Arc::new(BoxedStrategyWrapper(self)))
+    }
+
+    /// Wraps this strategy to prevent values from being subject to shrinking.
+    ///
+    /// Suppressing shrinking is useful when testing things like linear
+    /// approximation functions. Ordinarily, proptest will tend to shrink the
+    /// input to the function until the result is just barely outside the
+    /// acceptable range whereas the original input may have produced a result
+    /// far outside of it. Since this makes it harder to see what the actual
+    /// problem is, making the input `NoShrink` allows learning about inputs
+    /// that produce more incorrect results.
+    fn no_shrink(self) -> NoShrink<Self>
+    where
+        Self: Sized,
+    {
+        NoShrink(self)
+    }
+}
+
+/// A generated value and its associated shrinker.
+///
+/// Conceptually, a `ValueTree` represents a spectrum between a "minimally
+/// complex" value and a starting, randomly-chosen value. For values such as
+/// numbers, this can be thought of as a simple binary search, and this is how
+/// the `ValueTree` state machine is defined.
+///
+/// The `ValueTree` state machine notionally has three fields: low, current,
+/// and high. Initially, low is the "minimally complex" value for the type, and
+/// high and current are both the initially chosen value. It can be queried for
+/// its current state. When shrinking, the controlling code tries simplifying
+/// the value one step. If the test failure still happens with the simplified
+/// value, further simplification occurs. Otherwise, the code steps back up
+/// towards the prior complexity.
+///
+/// The main invariants here are that the "high" value always corresponds to a
+/// failing test case, and that repeated calls to `complicate()` will return
+/// `false` only once the "current" value has returned to what it was before
+/// the last call to `simplify()`.
+///
+/// While it would be possible for default do-nothing implementations of
+/// `simplify()` and `complicate()` to be provided, this was not done
+/// deliberately since the majority of strategies will want to define their own
+/// shrinking anyway, and the minority that do not must call it out explicitly
+/// by their own implementation.
+pub trait ValueTree {
+    /// The type of the value produced by this `ValueTree`.
+    type Value: fmt::Debug;
+
+    /// Returns the current value.
+    fn current(&self) -> Self::Value;
+    /// Attempts to simplify the current value. Notionally, this sets the
+    /// "high" value to the current value, and the current value to a "halfway
+    /// point" between high and low, rounding towards low.
+    ///
+    /// Returns whether any state changed as a result of this call. This does
+    /// not necessarily imply that the value of `current()` has changed, since
+    /// in the most general case, it is not possible for an implementation to
+    /// determine this.
+    ///
+    /// This call needs to correctly handle being called even immediately after
+    /// it had been called previously and returned `false`.
+    fn simplify(&mut self) -> bool;
+    /// Attempts to partially undo the last simplification. Notionally, this
+    /// sets the "low" value to one plus the current value, and the current
+    /// value to a "halfway point" between high and the new low, rounding
+    /// towards low.
+    ///
+    /// Returns whether any state changed as a result of this call. This does
+    /// not necessarily imply that the value of `current()` has changed, since
+    /// in the most general case, it is not possible for an implementation to
+    /// determine this.
+    ///
+    /// It is usually expected that, immediately after a call to `simplify()`
+    /// which returns true, this call will itself return true. However, this is
+    /// not always the case; in some strategies, particularly those that use
+    /// some form of rejection sampling, the act of trying to simplify may
+    /// change the state such that `simplify()` returns true, yet ultimately
+    /// left the resulting value unchanged, in which case there is nothing left
+    /// to complicate.
+    ///
+    /// This call does not need to gracefully handle being called before
+    /// `simplify()` was ever called, but does need to correctly handle being
+    /// called even immediately after it had been called previously and
+    /// returned `false`.
+    fn complicate(&mut self) -> bool;
+}
+
+//==============================================================================
+// NoShrink
+//==============================================================================
+
+/// Wraps a `Strategy` or `ValueTree` to suppress shrinking of generated
+/// values.
+///
+/// See `Strategy::no_shrink()` for more details.
+#[derive(Clone, Copy, Debug)]
+#[must_use = "strategies do nothing unless used"]
+pub struct NoShrink<T>(T);
+
+impl<T: Strategy> Strategy for NoShrink<T> {
+    type Tree = NoShrink<T::Tree>;
+    type Value = T::Value;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        self.0.new_tree(runner).map(NoShrink)
+    }
+}
+
+impl<T: ValueTree> ValueTree for NoShrink<T> {
+    type Value = T::Value;
+
+    fn current(&self) -> T::Value {
+        self.0.current()
+    }
+
+    fn simplify(&mut self) -> bool {
+        false
+    }
+    fn complicate(&mut self) -> bool {
+        false
+    }
+}
+
+//==============================================================================
+// Trait objects
+//==============================================================================
+
+macro_rules! proxy_strategy {
+    ($typ:ty $(, $lt:tt)*) => {
+        impl<$($lt,)* S : Strategy + ?Sized> Strategy for $typ {
+            type Tree = S::Tree;
+            type Value = S::Value;
+
+            fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+                (**self).new_tree(runner)
+            }
+        }
+    };
+}
+proxy_strategy!(Box<S>);
+proxy_strategy!(&'a S, 'a);
+proxy_strategy!(&'a mut S, 'a);
+proxy_strategy!(Rc<S>);
+proxy_strategy!(Arc<S>);
+
+impl<T: ValueTree + ?Sized> ValueTree for Box<T> {
+    type Value = T::Value;
+    fn current(&self) -> Self::Value {
+        (**self).current()
+    }
+    fn simplify(&mut self) -> bool {
+        (**self).simplify()
+    }
+    fn complicate(&mut self) -> bool {
+        (**self).complicate()
+    }
+}
+
+/// A boxed `ValueTree`.
+type BoxedVT<T> = Box<dyn ValueTree<Value = T>>;
+
+/// A boxed `Strategy` trait object as produced by `Strategy::boxed()`.
+///
+/// Strategies of this type afford cheap shallow cloning via reference
+/// counting by using an `Arc` internally.
+#[derive(Debug)]
+#[must_use = "strategies do nothing unless used"]
+pub struct BoxedStrategy<T>(Arc<dyn Strategy<Value = T, Tree = BoxedVT<T>>>);
+
+/// A boxed `Strategy` trait object which is also `Sync` and
+/// `Send`, as produced by `Strategy::sboxed()`.
+///
+/// Strategies of this type afford cheap shallow cloning via reference
+/// counting by using an `Arc` internally.
+#[derive(Debug)]
+#[must_use = "strategies do nothing unless used"]
+pub struct SBoxedStrategy<T>(
+    Arc<dyn Strategy<Value = T, Tree = BoxedVT<T>> + Sync + Send>,
+);
+
+impl<T> Clone for BoxedStrategy<T> {
+    fn clone(&self) -> Self {
+        BoxedStrategy(Arc::clone(&self.0))
+    }
+}
+
+impl<T> Clone for SBoxedStrategy<T> {
+    fn clone(&self) -> Self {
+        SBoxedStrategy(Arc::clone(&self.0))
+    }
+}
+
+impl<T: fmt::Debug> Strategy for BoxedStrategy<T> {
+    type Tree = BoxedVT<T>;
+    type Value = T;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        self.0.new_tree(runner)
+    }
+
+    // Optimization: Don't rebox the strategy.
+
+    fn boxed(self) -> BoxedStrategy<Self::Value>
+    where
+        Self: Sized + 'static,
+    {
+        self
+    }
+}
+
+impl<T: fmt::Debug> Strategy for SBoxedStrategy<T> {
+    type Tree = BoxedVT<T>;
+    type Value = T;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        self.0.new_tree(runner)
+    }
+
+    // Optimization: Don't rebox the strategy.
+
+    fn sboxed(self) -> SBoxedStrategy<Self::Value>
+    where
+        Self: Sized + Send + Sync + 'static,
+    {
+        self
+    }
+
+    fn boxed(self) -> BoxedStrategy<Self::Value>
+    where
+        Self: Sized + 'static,
+    {
+        BoxedStrategy(self.0)
+    }
+}
+
+#[derive(Debug)]
+struct BoxedStrategyWrapper<T>(T);
+impl<T: Strategy> Strategy for BoxedStrategyWrapper<T>
+where
+    T::Tree: 'static,
+{
+    type Tree = Box<dyn ValueTree<Value = T::Value>>;
+    type Value = T::Value;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        Ok(Box::new(self.0.new_tree(runner)?))
+    }
+}
+
+//==============================================================================
+// Sanity checking
+//==============================================================================
+
+/// Options passed to `check_strategy_sanity()`.
+#[derive(Clone, Copy, Debug)]
+pub struct CheckStrategySanityOptions {
+    /// If true (the default), require that `complicate()` return `true` at
+    /// least once after any call to `simplify()` which itself returns once.
+    ///
+    /// This property is not required by contract, but many strategies are
+    /// designed in a way that this is expected to hold.
+    pub strict_complicate_after_simplify: bool,
+
+    /// If true, cause local rejects to return an error instead of retrying.
+    /// Defaults to false. Useful for testing behaviors around error handling.
+    pub error_on_local_rejects: bool,
+
+    // Needs to be public for FRU syntax.
+    #[allow(missing_docs)]
+    #[doc(hidden)]
+    pub _non_exhaustive: (),
+}
+
+impl Default for CheckStrategySanityOptions {
+    fn default() -> Self {
+        CheckStrategySanityOptions {
+            strict_complicate_after_simplify: true,
+            error_on_local_rejects: false,
+            _non_exhaustive: (),
+        }
+    }
+}
+
+/// Run some tests on the given `Strategy` to ensure that it upholds the
+/// simplify/complicate contracts.
+///
+/// This is used to internally test proptest, but is made generally available
+/// for external implementations to use as well.
+///
+/// `options` can be passed to configure the test; if `None`, the defaults are
+/// used. Note that the defaults check for certain properties which are **not**
+/// actually required by the `Strategy` and `ValueTree` contracts; if you think
+/// your code is right but it fails the test, consider whether a non-default
+/// configuration is necessary.
+///
+/// This can work with fallible strategies, but limits how many times it will
+/// retry failures.
+pub fn check_strategy_sanity<S: Strategy>(
+    strategy: S,
+    options: Option<CheckStrategySanityOptions>,
+) where
+    S::Tree: Clone + fmt::Debug,
+    S::Value: cmp::PartialEq,
+{
+    // Like assert_eq!, but also pass if both values do not equal themselves.
+    // This allows the test to work correctly with things like NaN.
+    macro_rules! assert_same {
+        ($a:expr, $b:expr, $($stuff:tt)*) => { {
+            let a = $a;
+            let b = $b;
+            if a == a || b == b {
+                assert_eq!(a, b, $($stuff)*);
+            }
+        } }
+    }
+
+    let options = options.unwrap_or_else(CheckStrategySanityOptions::default);
+    let mut config = Config::default();
+    if options.error_on_local_rejects {
+        config.max_local_rejects = 0;
+    }
+    let mut runner = TestRunner::new(config);
+
+    for _ in 0..1024 {
+        let mut gen_tries = 0;
+        let mut state;
+        loop {
+            let err = match strategy.new_tree(&mut runner) {
+                Ok(s) => {
+                    state = s;
+                    break;
+                }
+                Err(e) => e,
+            };
+
+            gen_tries += 1;
+            if gen_tries > 100 {
+                panic!(
+                    "Strategy passed to check_strategy_sanity failed \
+                     to generate a value over 100 times in a row; \
+                     last failure reason: {}",
+                    err
+                );
+            }
+        }
+
+        {
+            let mut state = state.clone();
+            let mut count = 0;
+            while state.simplify() || state.complicate() {
+                count += 1;
+                if count > 65536 {
+                    panic!(
+                        "Failed to converge on any value. State:\n{:#?}",
+                        state
+                    );
+                }
+            }
+        }
+
+        let mut num_simplifies = 0;
+        let mut before_simplified;
+        loop {
+            before_simplified = state.clone();
+            if !state.simplify() {
+                break;
+            }
+
+            let mut complicated = state.clone();
+            let before_complicated = state.clone();
+            if options.strict_complicate_after_simplify {
+                assert!(
+                    complicated.complicate(),
+                    "complicate() returned false immediately after \
+                     simplify() returned true. internal state after \
+                     {} calls to simplify():\n\
+                     {:#?}\n\
+                     simplified to:\n\
+                     {:#?}\n\
+                     complicated to:\n\
+                     {:#?}",
+                    num_simplifies,
+                    before_simplified,
+                    state,
+                    complicated
+                );
+            }
+
+            let mut prev_complicated = complicated.clone();
+            let mut num_complications = 0;
+            loop {
+                if !complicated.complicate() {
+                    break;
+                }
+                prev_complicated = complicated.clone();
+                num_complications += 1;
+
+                if num_complications > 65_536 {
+                    panic!(
+                        "complicate() returned true over 65536 times in a \
+                         row; aborting due to possible infinite loop. \
+                         If this is not an infinite loop, it may be \
+                         necessary to reconsider how shrinking is \
+                         implemented or use a simpler test strategy. \
+                         Internal state:\n{:#?}",
+                        state
+                    );
+                }
+            }
+
+            assert_same!(
+                before_simplified.current(),
+                complicated.current(),
+                "Calling simplify(), then complicate() until it \
+                 returned false, did not return to the value before \
+                 simplify. Expected:\n\
+                 {:#?}\n\
+                 Actual:\n\
+                 {:#?}\n\
+                 Internal state after {} calls to simplify():\n\
+                 {:#?}\n\
+                 Internal state after another call to simplify():\n\
+                 {:#?}\n\
+                 Internal state after {} subsequent calls to \
+                 complicate():\n\
+                 {:#?}",
+                before_simplified.current(),
+                complicated.current(),
+                num_simplifies,
+                before_simplified,
+                before_complicated,
+                num_complications + 1,
+                complicated
+            );
+
+            for iter in 1..16 {
+                assert_same!(
+                    prev_complicated.current(),
+                    complicated.current(),
+                    "complicate() returned false but changed the output \
+                     value anyway.\n\
+                     Old value:\n\
+                     {:#?}\n\
+                     New value:\n\
+                     {:#?}\n\
+                     Old internal state:\n\
+                     {:#?}\n\
+                     New internal state after {} calls to complicate()\
+                     including the :\n\
+                     {:#?}",
+                    prev_complicated.current(),
+                    complicated.current(),
+                    prev_complicated,
+                    iter,
+                    complicated
+                );
+
+                assert!(
+                    !complicated.complicate(),
+                    "complicate() returned true after having returned \
+                     false;\n\
+                     Internal state before:\n{:#?}\n\
+                     Internal state after calling complicate() {} times:\n\
+                     {:#?}",
+                    prev_complicated,
+                    iter + 1,
+                    complicated
+                );
+            }
+
+            num_simplifies += 1;
+            if num_simplifies > 65_536 {
+                panic!(
+                    "simplify() returned true over 65536 times in a row, \
+                     aborting due to possible infinite loop. If this is not \
+                     an infinite loop, it may be necessary to reconsider \
+                     how shrinking is implemented or use a simpler test \
+                     strategy. Internal state:\n{:#?}",
+                    state
+                );
+            }
+        }
+
+        for iter in 0..16 {
+            assert_same!(
+                before_simplified.current(),
+                state.current(),
+                "simplify() returned false but changed the output \
+                 value anyway.\n\
+                 Old value:\n\
+                 {:#?}\n\
+                 New value:\n\
+                 {:#?}\n\
+                 Previous internal state:\n\
+                 {:#?}\n\
+                 New internal state after calling simplify() {} times:\n\
+                 {:#?}",
+                before_simplified.current(),
+                state.current(),
+                before_simplified,
+                iter,
+                state
+            );
+
+            if state.simplify() {
+                panic!(
+                    "simplify() returned true after having returned false. \
+                     Previous internal state:\n\
+                     {:#?}\n\
+                     New internal state after calling simplify() {} times:\n\
+                     {:#?}",
+                    before_simplified,
+                    iter + 1,
+                    state
+                );
+            }
+        }
+    }
+}
diff --git a/vendor/proptest/src/strategy/unions.rs b/vendor/proptest/src/strategy/unions.rs
new file mode 100644
index 000000000..fb5806297
--- /dev/null
+++ b/vendor/proptest/src/strategy/unions.rs
@@ -0,0 +1,697 @@
+//-
+// 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 crate::std_facade::{fmt, Arc, Vec};
+use core::cmp::{max, min};
+use core::u32;
+
+#[cfg(not(feature = "std"))]
+use num_traits::float::FloatCore;
+
+use crate::num::sample_uniform;
+use crate::strategy::{lazy::LazyValueTree, 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 **relative** `weight` of a particular `Strategy` corresponding to `T`
+/// coupled with `Arc<T>`. The weight is currently given in `u32`.
+pub type WA<T> = (u32, Arc<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> {
+    // In principle T could be any `Strategy + Clone`, but that isn't possible
+    // for BC reasons with the 0.9 series.
+    options: Vec<WA<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<WA<T>> =
+            options.into_iter().map(|v| (1, Arc::new(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<WA<T>> = it
+            .map(|r| r.map(|v| (1, Arc::new(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"
+        );
+        let options =
+            options.into_iter().map(|(w, v)| (w, Arc::new(v))).collect();
+        Self { options }
+    }
+
+    /// Add `other` as an additional alternate strategy with weight 1.
+    pub fn or(mut self, other: T) -> Self {
+        self.options.push((1, Arc::new(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>;
+    type Value = T::Value;
+
+    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
+        fn extract_weight<V>(&(w, _): &WA<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);
+
+        // Delay initialization for all options less than pick.
+        for option in &self.options[0..pick] {
+            options.push(LazyValueTree::new(Arc::clone(&option.1), runner));
+        }
+
+        // Initialize the tree at pick so at least one value is available. Note
+        // that if generation for the value at pick fails, the entire strategy
+        // will fail. This seems like the right call.
+        options.push(LazyValueTree::new_initialized(
+            self.options[pick].1.new_tree(runner)?,
+        ));
+
+        Ok(UnionValueTree {
+            options,
+            pick,
+            min_pick: 0,
+            prev_pick: None,
+        })
+    }
+}
+
+macro_rules! access_vec {
+    ([$($muta:tt)*] $dst:ident = $this:expr, $ix:expr, $body:block) => {{
+        let $dst = &$($muta)* $this.options[$ix];
+        $body
+    }}
+}
+
+/// `ValueTree` corresponding to `Union`.
+pub struct UnionValueTree<T: Strategy> {
+    options: Vec<LazyValueTree<T>>,
+    // This struct maintains the invariant that between function calls,
+    // `pick` and `prev_pick` (if Some) always point to initialized
+    // trees.
+    pick: usize,
+    min_pick: usize,
+    prev_pick: Option<usize>,
+}
+
+macro_rules! lazy_union_value_tree_body {
+    ($typ:ty, $access:ident) => {
+        type Value = $typ;
+
+        fn current(&self) -> Self::Value {
+            $access!([] opt = self, self.pick, {
+                opt.as_inner().unwrap_or_else(||
+                    panic!(
+                        "value tree at self.pick = {} must be initialized",
+                        self.pick,
+                    )
+                ).current()
+            })
+        }
+
+        fn simplify(&mut self) -> bool {
+            let orig_pick = self.pick;
+            if $access!([mut] opt = self, orig_pick, {
+                opt.as_inner_mut().unwrap_or_else(||
+                    panic!(
+                        "value tree at self.pick = {} must be initialized",
+                        orig_pick,
+                    )
+                ).simplify()
+            }) {
+                self.prev_pick = None;
+                return true;
+            }
+
+            assert!(
+                self.pick >= self.min_pick,
+                "self.pick = {} should never go below self.min_pick = {}",
+                self.pick,
+                self.min_pick,
+            );
+            if self.pick == self.min_pick {
+                // No more simplification to be done.
+                return false;
+            }
+
+            // self.prev_pick is always a valid pick.
+            self.prev_pick = Some(self.pick);
+
+            let mut next_pick = self.pick;
+            while next_pick > self.min_pick {
+                next_pick -= 1;
+                let initialized = $access!([mut] opt = self, next_pick, {
+                    opt.maybe_init();
+                    opt.is_initialized()
+                });
+                if initialized {
+                    // next_pick was correctly initialized above.
+                    self.pick = next_pick;
+                    return true;
+                }
+            }
+
+            false
+        }
+
+        fn complicate(&mut self) -> bool {
+            if let Some(pick) = self.prev_pick {
+                // simplify() ensures that the previous pick was initialized.
+                self.pick = pick;
+                self.min_pick = pick;
+                self.prev_pick = None;
+                true
+            } else {
+                let pick = self.pick;
+                $access!([mut] opt = self, pick, {
+                    opt.as_inner_mut().unwrap_or_else(||
+                        panic!(
+                            "value tree at self.pick = {} must be initialized",
+                            pick,
+                        )
+                    ).complicate()
+                })
+            }
+        }
+    }
+}
+
+impl<T: Strategy> ValueTree for UnionValueTree<T> {
+    lazy_union_value_tree_body!(T::Value, access_vec);
+}
+
+impl<T: Strategy> Clone for UnionValueTree<T>
+where
+    T::Tree: Clone,
+{
+    fn clone(&self) -> Self {
+        Self {
+            options: self.options.clone(),
+            pick: self.pick,
+            min_pick: self.min_pick,
+            prev_pick: self.prev_pick,
+        }
+    }
+}
+
+impl<T: Strategy> fmt::Debug for UnionValueTree<T>
+where
+    T::Tree: fmt::Debug,
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("UnionValueTree")
+            .field("options", &self.options)
+            .field("pick", &self.pick)
+            .field("min_pick", &self.min_pick)
+            .field("prev_pick", &self.prev_pick)
+            .finish()
+    }
+}
+
+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.
+///
+/// The difference between this and `TupleUnion` is that with this, value trees
+/// for variants that aren't picked at first are generated lazily.
+#[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, Arc<impl Strategy>)` pairs where all
+    /// strategies ultimately produce the same value. Each `u32` indicates the
+    /// relative weight of its corresponding strategy.
+    /// You may use `WA<S>` as an alias for `(u32, Arc<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<(WA<A>, $(WA<$gen>),*)> {
+            type Tree = TupleUnionValueTree<
+                (LazyValueTree<A>, $(Option<LazyValueTree<$gen>>),*)>;
+            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: (
+                        if 0 == pick {
+                            LazyValueTree::new_initialized(
+                                ((self.0).0).1.new_tree(runner)?)
+                        } else {
+                            LazyValueTree::new(
+                                Arc::clone(&((self.0).0).1), runner)
+                        },
+                        $(
+                        if $ix == pick {
+                            Some(LazyValueTree::new_initialized(
+                                 ((self.0).$ix).1.new_tree(runner)?))
+                        } else if $ix < pick {
+                            Some(LazyValueTree::new(
+                                    Arc::clone(&((self.0).$ix).1), 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 : Strategy, $($gen: Strategy<Value = A::Value>),*> ValueTree
+        for TupleUnionValueTree<
+            (LazyValueTree<A>, $(Option<LazyValueTree<$gen>>),*)
+        > {
+            lazy_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 super::*;
+    use crate::strategy::just::Just;
+
+    // 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, Arc::new(10u32..20u32)),
+            (1, Arc::new(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, Arc::new(Just(0usize))),
+            (2, Arc::new(Just(1usize))),
+            (1, Arc::new(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 = Arc::new(1i32..10);
+
+        macro_rules! test {
+            ($($part:expr),*) => {{
+                let input = TupleUnion::new((
+                    $((1, $part.clone())),*,
+                    (1, Arc::new(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, Arc::new(0i32..100i32)),
+                (1, Arc::new(200i32..1000i32)),
+                (1, Arc::new(2000i32..3000i32)),
+            )),
+            None,
+        );
+    }
+
+    /// Test that unions work even if local filtering causes errors.
+    #[test]
+    fn test_filter_union_sanity() {
+        let filter_strategy = (0u32..256).prop_filter("!%5", |&v| 0 != v % 5);
+        check_strategy_sanity(
+            Union::new(vec![filter_strategy; 8]),
+            Some(filter_sanity_options()),
+        );
+    }
+
+    /// Test that tuple unions work even if local filtering causes errors.
+    #[test]
+    fn test_filter_tuple_union_sanity() {
+        let filter_strategy = (0u32..256).prop_filter("!%5", |&v| 0 != v % 5);
+        check_strategy_sanity(
+            TupleUnion::new((
+                (1, Arc::new(filter_strategy.clone())),
+                (1, Arc::new(filter_strategy.clone())),
+                (1, Arc::new(filter_strategy.clone())),
+                (1, Arc::new(filter_strategy.clone())),
+            )),
+            Some(filter_sanity_options()),
+        );
+    }
+
+    fn filter_sanity_options() -> CheckStrategySanityOptions {
+        CheckStrategySanityOptions {
+            // Due to internal rejection sampling, `simplify()` can
+            // converge back to what `complicate()` would do.
+            strict_complicate_after_simplify: false,
+            // Make failed filters return errors to test edge cases.
+            error_on_local_rejects: true,
+            ..CheckStrategySanityOptions::default()
+        }
+    }
+}