Upgrade rust/crates/arbitrary to 1.0.0-rc2

Test: make
Change-Id: Ie4a2a8a5e93ba9728c6a9d5e8ec489d82ab5d521

12 files changed, 349 insertions, 667 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index e531caf..36e1045 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,5 @@
 {
   "git": {
-    "sha1": "570e96046a3f8589d2359a49b9197ea158077d3f"
+    "sha1": "89a6e201efdbfe6bd1495e15ded0b1a67d651525"
   }
 }
diff --git a/Android.bp b/Android.bp
index 5d10059..d826d44 100644
--- a/Android.bp
+++ b/Android.bp
@@ -13,8 +13,8 @@ rust_library_rlib {
 }
 
 // dependent_library ["feature_list"]
-//   derive_arbitrary-0.4.6
+//   derive_arbitrary-1.0.0-rc2
 //   proc-macro2-1.0.24 "default,proc-macro"
-//   quote-1.0.7 "default,proc-macro"
-//   syn-1.0.48 "clone-impls,default,derive,parsing,printing,proc-macro,quote"
+//   quote-1.0.8 "default,proc-macro"
+//   syn-1.0.60 "clone-impls,default,derive,parsing,printing,proc-macro,quote"
 //   unicode-xid-0.2.1 "default"
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 8a05879..e4d4268 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -28,6 +28,62 @@ Released YYYY-MM-DD.
 
 --------------------------------------------------------------------------------
 
+## 1.0.0-rc2
+
+### Added
+
+* The `Arbitrary` trait is now implemented for `&[u8]`. [#67](https://github.com/rust-fuzz/arbitrary/pull/67)
+
+### Changed
+
+* Rename `Unstructured#get_bytes` to `Unstructured#bytes`. [#70](https://github.com/rust-fuzz/arbitrary/pull/70)
+* Passing an empty slice of choices to `Unstructured#choose` returns an error. Previously it would panic. [71](https://github.com/rust-fuzz/arbitrary/pull/71)
+
+### Removed
+
+*
+
+--------------------------------------------------------------------------------
+
+## 1.0.0-rc1
+
+Released 2020-11-25.
+
+### Added
+
+* The `Arbitrary` trait is now implemented for `&str`. [#63](https://github.com/rust-fuzz/arbitrary/pull/63)
+
+### Changed
+
+* The `Arbitrary` trait now has a lifetime parameter, allowing `Arbitrary` implementations that borrow from the raw input (e.g. the new `&str` implementaton). The `derive(Arbitrary)` macro also supports deriving `Arbitrary` on types with lifetimes now. [#63](https://github.com/rust-fuzz/arbitrary/pull/63)
+
+### Removed
+
+* The `shrink` method on the `Arbitrary` trait has been removed.
+
+  We have found that, in practice, using [internal reduction](https://drmaciver.github.io/papers/reduction-via-generation-preview.pdf) via approaches like `cargo fuzz tmin`, where the raw input bytes are reduced rather than the `T: Arbitrary` type constructed from those raw bytes, has the best efficiency-to-maintenance ratio. To the best of our knowledge, no one is relying on or using the `Arbitrary::shrink` method. If you *are* using and relying on the `Arbitrary::shrink` method, please reach out by [dropping a comment here](https://github.com/rust-fuzz/arbitrary/issues/62) and explaining how you're using it and what your use case is. We'll figure out what the best solution is, including potentially adding shrinking functionality back to the `arbitrary` crate.
+
+--------------------------------------------------------------------------------
+
+## 0.4.7
+
+Released 2020-10-14.
+
+### Added
+
+* Added an optimization to avoid unnecessarily consuming bytes from the
+  underlying data when there is only one possible choice in
+  `Unstructured::{int_in_range, choose, etc..}`.
+
+* Added license files to the derive crate.
+
+### Changed
+
+* The `Arbitrary` implementation for `std::time::Duration` should now be faster
+  and produce durations with a more-uniform distribution of nanoseconds.
+
+--------------------------------------------------------------------------------
+
 ## 0.4.6
 
 Released 2020-08-22.
diff --git a/Cargo.toml b/Cargo.toml
index 0857f9f..5f5ff2d 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -13,15 +13,15 @@
 [package]
 edition = "2018"
 name = "arbitrary"
-version = "0.4.6"
-authors = ["The Rust-Fuzz Project Developers", "Nick Fitzgerald <fitzgen@gmail.com>", "Manish Goregaokar <manishsmail@gmail.com>", "Simonas Kazlauskas <arbitrary@kazlauskas.me>", "Brian L. Troutwine <brian@troutwine.us>"]
+version = "1.0.0-rc2"
+authors = ["The Rust-Fuzz Project Developers", "Nick Fitzgerald <fitzgen@gmail.com>", "Manish Goregaokar <manishsmail@gmail.com>", "Simonas Kazlauskas <arbitrary@kazlauskas.me>", "Brian L. Troutwine <brian@troutwine.us>", "Corey Farwell <coreyf@rwell.org>"]
 description = "The trait for generating structured data from unstructured data"
 documentation = "https://docs.rs/arbitrary/"
 readme = "README.md"
 keywords = ["arbitrary", "testing"]
 categories = ["development-tools::testing"]
 license = "MIT/Apache-2.0"
-repository = "https://github.com/nagisa/rust_arbitrary/"
+repository = "https://github.com/rust-fuzz/arbitrary/"
 
 [[example]]
 name = "derive_enum"
@@ -32,7 +32,7 @@ name = "derive"
 path = "./tests/derive.rs"
 required-features = ["derive"]
 [dependencies.derive_arbitrary]
-version = "=0.4.6"
+version = "1.0.0-rc1"
 optional = true
 
 [dev-dependencies]
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index ab70b1e..3ca96bd 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,18 +1,25 @@
 [package]
 name = "arbitrary"
-version = "0.4.6" # Make sure this matches the derive crate version
-authors = ["The Rust-Fuzz Project Developers", "Nick Fitzgerald <fitzgen@gmail.com>", "Manish Goregaokar <manishsmail@gmail.com>", "Simonas Kazlauskas <arbitrary@kazlauskas.me>", "Brian L. Troutwine <brian@troutwine.us>"]
+version = "1.0.0-rc2" # Make sure this matches the derive crate version
+authors = [
+    "The Rust-Fuzz Project Developers",
+    "Nick Fitzgerald <fitzgen@gmail.com>",
+    "Manish Goregaokar <manishsmail@gmail.com>",
+    "Simonas Kazlauskas <arbitrary@kazlauskas.me>",
+    "Brian L. Troutwine <brian@troutwine.us>",
+    "Corey Farwell <coreyf@rwell.org>",
+]
 categories = ["development-tools::testing"]
 edition = "2018"
 keywords = ["arbitrary", "testing"]
 readme = "README.md"
 description = "The trait for generating structured data from unstructured data"
 license = "MIT/Apache-2.0"
-repository = "https://github.com/nagisa/rust_arbitrary/"
+repository = "https://github.com/rust-fuzz/arbitrary/"
 documentation = "https://docs.rs/arbitrary/"
 
 [dependencies]
-derive_arbitrary = { version = "=0.4.6", path = "./derive", optional = true }
+derive_arbitrary = { version = "1.0.0-rc1", path = "./derive", optional = true }
 
 [dev-dependencies]
 
diff --git a/METADATA b/METADATA
index 551a31d..99531d8 100644
--- a/METADATA
+++ b/METADATA
@@ -1,13 +1,5 @@
 name: "arbitrary"
-description:
-    "The Arbitrary crate lets you construct arbitrary instance of a type."
-    ""
-    "This crate is primarily intended to be combined with a fuzzer like "
-    "libFuzzer and cargo-fuzz or AFL, and to help you turn the raw, untyped "
-    "byte buffers that they produce into well-typed, valid, structured values. "
-    "This allows you to combine structure-aware test case generation with "
-    "coverage-guided, mutation-based fuzzers."
-
+description: "The trait for generating structured data from unstructured data"
 third_party {
   url {
     type: HOMEPAGE
@@ -15,9 +7,13 @@ third_party {
   }
   url {
     type: ARCHIVE
-    value: "https://static.crates.io/crates/arbitrary/arbitrary-0.4.6.crate"
+    value: "https://static.crates.io/crates/arbitrary/arbitrary-1.0.0-rc2.crate"
   }
-  version: "0.4.6"
-  last_upgrade_date { year: 2020 month: 10 day: 5 }
+  version: "1.0.0-rc2"
   license_type: NOTICE
+  last_upgrade_date {
+    year: 2021
+    month: 2
+    day: 9
+  }
 }
diff --git a/README.md b/README.md
index 7c62e6f..66bf2d1 100644
--- a/README.md
+++ b/README.md
@@ -77,8 +77,8 @@ pub struct Rgb {
     pub b: u8,
 }
 
-impl Arbitrary for Rgb {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a> Arbitrary<'a> for Rgb {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         let r = u8::arbitrary(u)?;
         let g = u8::arbitrary(u)?;
         let b = u8::arbitrary(u)?;
@@ -87,33 +87,6 @@ impl Arbitrary for Rgb {
 }
 ```
 
-### Shrinking
-
-To assist with test case reduction, where you want to find the smallest and most
-easily understandable test case that still demonstrates a bug you've discovered,
-the `Arbitrary` trait has a `shrink` method. The `shrink` method returns an
-iterator of "smaller" instances of `self`. The provided, default implementation
-returns an empty iterator.
-
-We can override the default for our `Rgb` struct above by shrinking each of its
-components and then gluing them back together again:
-
-```rust
-impl Arbitrary for Rgb {
-    // ...
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let rs = self.r.shrink();
-        let gs = self.g.shrink();
-        let bs = self.b.shrink();
-        Box::new(rs.zip(gs).zip(bs).map(|((r, g), b)| Rgb { r, g, b }))
-    }
-}
-```
-
-Note that deriving `Arbitrary` will automatically derive a custom `shrink`
-implementation for you.
-
 ## License
 
 Licensed under dual MIT or Apache-2.0 at your choice.
diff --git a/src/error.rs b/src/error.rs
index 8cbd076..f590c12 100644
--- a/src/error.rs
+++ b/src/error.rs
@@ -4,6 +4,8 @@ use std::{error, fmt};
 #[derive(Debug, Clone, Copy)]
 #[non_exhaustive]
 pub enum Error {
+    /// No choices were provided to the Unstructured::choose call
+    EmptyChoose,
     /// There was not enough underlying data to fulfill some request for raw
     /// bytes.
     NotEnoughData,
@@ -14,6 +16,10 @@ pub enum Error {
 impl fmt::Display for Error {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match self {
+            Error::EmptyChoose => write!(
+                f,
+                "`arbitrary::Unstructured::choose` must be given a non-empty set of choices"
+            ),
             Error::NotEnoughData => write!(
                 f,
                 "There is not enough underlying raw data to construct an `Arbitrary` instance"
diff --git a/src/lib.rs b/src/lib.rs
index 2a10718..9a52e47 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -45,25 +45,14 @@ use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedL
 use std::ffi::{CString, OsString};
 use std::path::PathBuf;
 use std::rc::Rc;
-use std::sync::atomic::{AtomicBool, AtomicIsize, AtomicUsize, Ordering};
+use std::sync::atomic::{AtomicBool, AtomicIsize, AtomicUsize};
 use std::sync::{Arc, Mutex};
 
-fn empty<T: 'static>() -> Box<dyn Iterator<Item = T>> {
-    Box::new(iter::empty())
-}
-
-fn once<T: 'static>(val: T) -> Box<dyn Iterator<Item = T>> {
-    Box::new(iter::once(val))
-}
-
 /// Generate arbitrary structured values from raw, unstructured data.
 ///
 /// The `Arbitrary` trait allows you to generate valid structured values, like
 /// `HashMap`s, or ASTs, or `MyTomlConfig`, or any other data structure from
-/// raw, unstructured bytes provided by a fuzzer. It also features built-in
-/// shrinking, so that if you find a test case that triggers a bug, you can find
-/// the smallest, most easiest-to-understand test case that still triggers that
-/// bug.
+/// raw, unstructured bytes provided by a fuzzer.
 ///
 /// # Deriving `Arbitrary`
 ///
@@ -75,7 +64,7 @@ fn once<T: 'static>(val: T) -> Box<dyn Iterator<Item = T>> {
 ///
 /// ```toml
 /// [dependencies]
-/// arbitrary = { version = "0.2.0", features = ["derive"] }
+/// arbitrary = { version = "0.4", features = ["derive"] }
 /// ```
 ///
 /// Then, you add the `#[derive(Arbitrary)]` annotation to your `struct` or
@@ -118,11 +107,11 @@ fn once<T: 'static>(val: T) -> Box<dyn Iterator<Item = T>> {
 /// # }
 /// use arbitrary::{Arbitrary, Result, Unstructured};
 ///
-/// impl<T> Arbitrary for MyCollection<T>
+/// impl<'a, T> Arbitrary<'a> for MyCollection<T>
 /// where
-///     T: Arbitrary,
+///     T: Arbitrary<'a>,
 /// {
-///     fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+///     fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
 ///         // Get an iterator of arbitrary `T`s.
 ///         let iter = u.arbitrary_iter::<T>()?;
 ///
@@ -138,7 +127,7 @@ fn once<T: 'static>(val: T) -> Box<dyn Iterator<Item = T>> {
 /// }
 /// # }
 /// ```
-pub trait Arbitrary: Sized + 'static {
+pub trait Arbitrary<'a>: Sized {
     /// Generate an arbitrary value of `Self` from the given unstructured data.
     ///
     /// Calling `Arbitrary::arbitrary` requires that you have some raw data,
@@ -179,14 +168,14 @@ pub trait Arbitrary: Sized + 'static {
     /// ```
     ///
     /// See also the documentation for [`Unstructured`][crate::Unstructured].
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self>;
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self>;
 
     /// Generate an arbitrary value of `Self` from the entirety of the given unstructured data.
     ///
     /// This is similar to Arbitrary::arbitrary, however it assumes that it is the
     /// last consumer of the given data, and is thus able to consume it all if it needs.
     /// See also the documentation for [`Unstructured`][crate::Unstructured].
-    fn arbitrary_take_rest(mut u: Unstructured<'_>) -> Result<Self> {
+    fn arbitrary_take_rest(mut u: Unstructured<'a>) -> Result<Self> {
         Self::arbitrary(&mut u)
     }
 
@@ -232,10 +221,10 @@ pub trait Arbitrary: Sized + 'static {
     ///     Right(R),
     /// }
     ///
-    /// impl<L, R> Arbitrary for MyEither<L, R>
+    /// impl<'a, L, R> Arbitrary<'a> for MyEither<L, R>
     /// where
-    ///     L: Arbitrary,
-    ///     R: Arbitrary,
+    ///     L: Arbitrary<'a>,
+    ///     R: Arbitrary<'a>,
     /// {
     ///     fn arbitrary(u: &mut Unstructured) -> arbitrary::Result<Self> {
     ///         // ...
@@ -267,29 +256,10 @@ pub trait Arbitrary: Sized + 'static {
         let _ = depth;
         (0, None)
     }
-
-    /// Generate an iterator of derived values which are "smaller" than the
-    /// original `self` instance.
-    ///
-    /// You can use this to help find the smallest test case that reproduces a
-    /// bug.
-    ///
-    /// Using `#[derive(Arbitrary)]` will automatically implement shrinking for
-    /// your type.
-    ///
-    /// However, if you are implementing `Arbirary` by hand and you want support
-    /// for shrinking your type, you must override the default provided
-    /// implementation of `shrink`, which just returns an empty iterator. You
-    /// should try pretty hard to have your `shrink` implementation return a
-    /// *lazy* iterator: one that computes the next value as it is needed,
-    /// rather than computing them up front when `shrink` is first called.
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        empty()
-    }
 }
 
-impl Arbitrary for () {
-    fn arbitrary(_: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a> Arbitrary<'a> for () {
+    fn arbitrary(_: &mut Unstructured<'a>) -> Result<Self> {
         Ok(())
     }
 
@@ -299,26 +269,22 @@ impl Arbitrary for () {
     }
 }
 
-impl Arbitrary for bool {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
-        Ok(<u8 as Arbitrary>::arbitrary(u)? & 1 == 1)
+impl<'a> Arbitrary<'a> for bool {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
+        Ok(<u8 as Arbitrary<'a>>::arbitrary(u)? & 1 == 1)
     }
 
     #[inline]
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        <u8 as Arbitrary>::size_hint(depth)
-    }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        Box::new(if *self { once(false) } else { empty() })
+        <u8 as Arbitrary<'a>>::size_hint(depth)
     }
 }
 
 macro_rules! impl_arbitrary_for_integers {
     ( $( $ty:ty: $unsigned:ty; )* ) => {
         $(
-            impl Arbitrary for $ty {
-                fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+            impl<'a> Arbitrary<'a> for $ty {
+                fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
                     let mut buf = [0; mem::size_of::<$ty>()];
                     u.fill_buffer(&mut buf)?;
                     let mut x: $unsigned = 0;
@@ -334,20 +300,6 @@ macro_rules! impl_arbitrary_for_integers {
                     (n, Some(n))
                 }
 
-                fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-                    let mut x = *self;
-                    if x == 0 {
-                        return empty();
-                    }
-                    Box::new(iter::once(0).chain(std::iter::from_fn(move || {
-                        x = x / 2;
-                        if x == 0 {
-                            None
-                        } else {
-                            Some(x)
-                        }
-                    })))
-                }
             }
         )*
     }
@@ -371,45 +323,14 @@ impl_arbitrary_for_integers! {
 macro_rules! impl_arbitrary_for_floats {
     ( $( $ty:ident : $unsigned:ty; )* ) => {
         $(
-            impl Arbitrary for $ty {
-                fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
-                    Ok(Self::from_bits(<$unsigned as Arbitrary>::arbitrary(u)?))
+            impl<'a> Arbitrary<'a> for $ty {
+                fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
+                    Ok(Self::from_bits(<$unsigned as Arbitrary<'a>>::arbitrary(u)?))
                 }
 
                 #[inline]
                 fn size_hint(depth: usize) -> (usize, Option<usize>) {
-                    <$unsigned as Arbitrary>::size_hint(depth)
-                }
-
-                fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-                    if *self == 0.0 {
-                        empty()
-                    } else if !self.is_finite() {
-                        once(0.0)
-                    } else {
-                        let mut x = *self;
-                        Box::new(iter::once(0.0).chain(iter::from_fn(move || {
-                            // NB: do not test for zero like we do for integers
-                            // because dividing by two until we reach a fixed
-                            // point is NOT guaranteed to end at zero in
-                            // non-default rounding modes of IEEE-754!
-                            //
-                            // For example, with 64-bit floats and the
-                            // round-to-positive-infinity mode:
-                            //
-                            //     5e-324 / 2.0 == 5e-324
-                            //
-                            // (5e-234 is the smallest postive number that can
-                            // be precisely represented in a 64-bit float.)
-                            let y = x;
-                            x = x / 2.0;
-                            if x == y {
-                                None
-                            } else {
-                                Some(x)
-                            }
-                        })))
-                    }
+                    <$unsigned as Arbitrary<'a>>::size_hint(depth)
                 }
             }
         )*
@@ -421,13 +342,13 @@ impl_arbitrary_for_floats! {
     f64: u64;
 }
 
-impl Arbitrary for char {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a> Arbitrary<'a> for char {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         use std::char;
         const CHAR_END: u32 = 0x0011_000;
         // The size of the surrogate blocks
         const SURROGATES_START: u32 = 0xD800;
-        let mut c = <u32 as Arbitrary>::arbitrary(u)? % CHAR_END;
+        let mut c = <u32 as Arbitrary<'a>>::arbitrary(u)? % CHAR_END;
         if let Some(c) = char::from_u32(c) {
             return Ok(c);
         } else {
@@ -440,66 +361,40 @@ impl Arbitrary for char {
 
     #[inline]
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        <u32 as Arbitrary>::size_hint(depth)
-    }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let x = *self as u32;
-        Box::new(x.shrink().filter_map(|x| {
-            use std::convert::TryFrom;
-            char::try_from(x).ok()
-        }))
+        <u32 as Arbitrary<'a>>::size_hint(depth)
     }
 }
 
-impl Arbitrary for AtomicBool {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a> Arbitrary<'a> for AtomicBool {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         Arbitrary::arbitrary(u).map(Self::new)
     }
 
     #[inline]
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        <bool as Arbitrary>::size_hint(depth)
-    }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        if self.load(Ordering::SeqCst) {
-            once(AtomicBool::new(false))
-        } else {
-            empty()
-        }
+        <bool as Arbitrary<'a>>::size_hint(depth)
     }
 }
 
-impl Arbitrary for AtomicIsize {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a> Arbitrary<'a> for AtomicIsize {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         Arbitrary::arbitrary(u).map(Self::new)
     }
 
     #[inline]
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        <isize as Arbitrary>::size_hint(depth)
-    }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let x = self.load(Ordering::SeqCst);
-        Box::new(x.shrink().map(Self::new))
+        <isize as Arbitrary<'a>>::size_hint(depth)
     }
 }
 
-impl Arbitrary for AtomicUsize {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a> Arbitrary<'a> for AtomicUsize {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         Arbitrary::arbitrary(u).map(Self::new)
     }
 
     #[inline]
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        <usize as Arbitrary>::size_hint(depth)
-    }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let x = self.load(Ordering::SeqCst);
-        Box::new(x.shrink().map(Self::new))
+        <usize as Arbitrary<'a>>::size_hint(depth)
     }
 }
 
@@ -511,11 +406,11 @@ macro_rules! impl_range {
         $fun:ident($fun_closure:expr),
         $size_hint_closure:expr
     ) => {
-        impl<A> Arbitrary for $range
+        impl<'a, A> Arbitrary<'a> for $range
         where
-            A: Arbitrary + Clone + PartialOrd,
+            A: Arbitrary<'a> + Clone + PartialOrd,
         {
-            fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+            fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
                 let value: $value_ty = Arbitrary::arbitrary(u)?;
                 Ok($fun(value, $fun_closure))
             }
@@ -524,11 +419,6 @@ macro_rules! impl_range {
             fn size_hint(depth: usize) -> (usize, Option<usize>) {
                 $size_hint_closure(depth)
             }
-
-            fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-                let value: $value_ty = $value_closure(self);
-                Box::new(value.shrink().map(|v| $fun(v, $fun_closure)))
-            }
         }
     };
 }
@@ -575,7 +465,7 @@ impl_range!(
     |depth| <A as Arbitrary>::size_hint(depth)
 );
 
-fn bounded_range<CB, I, R>(bounds: (I, I), cb: CB) -> R
+pub(crate) fn bounded_range<CB, I, R>(bounds: (I, I), cb: CB) -> R
 where
     CB: Fn((I, I)) -> R,
     I: PartialOrd,
@@ -588,7 +478,7 @@ where
     cb((start, end))
 }
 
-fn unbounded_range<CB, I, R>(bound: I, cb: CB) -> R
+pub(crate) fn unbounded_range<CB, I, R>(bound: I, cb: CB) -> R
 where
     CB: Fn(I) -> R,
     R: RangeBounds<I>,
@@ -596,11 +486,11 @@ where
     cb(bound)
 }
 
-impl Arbitrary for Duration {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a> Arbitrary<'a> for Duration {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         Ok(Self::new(
             <u64 as Arbitrary>::arbitrary(u)?,
-            <u32 as Arbitrary>::arbitrary(u)? % 1_000_000_000,
+            u.int_in_range(0..=999_999_999)?,
         ))
     }
 
@@ -611,19 +501,11 @@ impl Arbitrary for Duration {
             <u32 as Arbitrary>::size_hint(depth),
         )
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        Box::new(
-            (self.as_secs(), self.subsec_nanos())
-                .shrink()
-                .map(|(secs, nanos)| Duration::new(secs, nanos % 1_000_000_000)),
-        )
-    }
 }
 
-impl<A: Arbitrary> Arbitrary for Option<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
-        Ok(if <bool as Arbitrary>::arbitrary(u)? {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Option<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
+        Ok(if <bool as Arbitrary<'a>>::arbitrary(u)? {
             Some(Arbitrary::arbitrary(u)?)
         } else {
             None
@@ -637,19 +519,11 @@ impl<A: Arbitrary> Arbitrary for Option<A> {
             crate::size_hint::or((0, Some(0)), <A as Arbitrary>::size_hint(depth)),
         )
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        if let Some(ref a) = *self {
-            Box::new(iter::once(None).chain(a.shrink().map(Some)))
-        } else {
-            empty()
-        }
-    }
 }
 
-impl<A: Arbitrary, B: Arbitrary> Arbitrary for std::result::Result<A, B> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
-        Ok(if <bool as Arbitrary>::arbitrary(u)? {
+impl<'a, A: Arbitrary<'a>, B: Arbitrary<'a>> Arbitrary<'a> for std::result::Result<A, B> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
+        Ok(if <bool as Arbitrary<'a>>::arbitrary(u)? {
             Ok(<A as Arbitrary>::arbitrary(u)?)
         } else {
             Err(<B as Arbitrary>::arbitrary(u)?)
@@ -666,13 +540,6 @@ impl<A: Arbitrary, B: Arbitrary> Arbitrary for std::result::Result<A, B> {
             ),
         )
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        match *self {
-            Ok(ref a) => Box::new(a.shrink().map(Ok)),
-            Err(ref b) => Box::new(b.shrink().map(Err)),
-        }
-    }
 }
 
 macro_rules! arbitrary_tuple {
@@ -680,13 +547,13 @@ macro_rules! arbitrary_tuple {
     ($last: ident $($xs: ident)*) => {
         arbitrary_tuple!($($xs)*);
 
-        impl<$($xs: Arbitrary,)* $last: Arbitrary> Arbitrary for ($($xs,)* $last,) {
-            fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+        impl<'a, $($xs: Arbitrary<'a>,)* $last: Arbitrary<'a>> Arbitrary<'a> for ($($xs,)* $last,) {
+            fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
                 Ok(($($xs::arbitrary(u)?,)* Arbitrary::arbitrary(u)?,))
             }
 
             #[allow(unused_mut, non_snake_case)]
-            fn arbitrary_take_rest(mut u: Unstructured<'_>) -> Result<Self> {
+            fn arbitrary_take_rest(mut u: Unstructured<'a>) -> Result<Self> {
                 $(let $xs = $xs::arbitrary(&mut u)?;)*
                 let $last = $last::arbitrary_take_rest(u)?;
                 Ok(($($xs,)* $last,))
@@ -699,15 +566,6 @@ macro_rules! arbitrary_tuple {
                     $( <$xs as Arbitrary>::size_hint(depth) ),*
                 ])
             }
-
-            #[allow(non_snake_case)]
-            fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-                let ( $( $xs, )* $last, ) = self;
-                let ( $( mut $xs, )* mut $last,) = ( $( $xs.shrink(), )* $last.shrink(),);
-                Box::new(iter::from_fn(move || {
-                    Some(( $( $xs.next()? ,)* $last.next()?, ))
-                }))
-            }
         }
     };
 }
@@ -717,8 +575,8 @@ macro_rules! arbitrary_array {
     {$n:expr, ($t:ident, $a:ident) $(($ts:ident, $as:ident))*} => {
         arbitrary_array!{($n - 1), $(($ts, $as))*}
 
-        impl<T: Arbitrary> Arbitrary for [T; $n] {
-            fn arbitrary(u: &mut Unstructured<'_>) -> Result<[T; $n]> {
+        impl<'a, T: Arbitrary<'a>> Arbitrary<'a> for [T; $n] {
+            fn arbitrary(u: &mut Unstructured<'a>) -> Result<[T; $n]> {
                 Ok([
                     Arbitrary::arbitrary(u)?,
                     $(<$ts as Arbitrary>::arbitrary(u)?),*
@@ -726,7 +584,7 @@ macro_rules! arbitrary_array {
             }
 
             #[allow(unused_mut)]
-            fn arbitrary_take_rest(mut u: Unstructured<'_>) -> Result<[T; $n]> {
+            fn arbitrary_take_rest(mut u: Unstructured<'a>) -> Result<[T; $n]> {
                 $(let $as = $ts::arbitrary(&mut u)?;)*
                 let last = Arbitrary::arbitrary_take_rest(u)?;
 
@@ -742,41 +600,17 @@ macro_rules! arbitrary_array {
                     $( <$ts as Arbitrary>::size_hint(depth) ),*
                 ])
             }
-
-            #[allow(unused_mut)] // For the `[T; 1]` case.
-            fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-                let mut i = 0;
-                let mut shrinkers = [
-                    self[i].shrink(),
-                    $({
-                        i += 1;
-                        let t: &$ts = &self[i];
-                        t.shrink()
-                    }),*
-                ];
-                Box::new(iter::from_fn(move || {
-                    let mut i = 0;
-                    Some([
-                        shrinkers[i].next()?,
-                        $({
-                            i += 1;
-                            let t: $ts = shrinkers[i].next()?;
-                            t
-                        }),*
-                    ])
-                }))
-            }
         }
     };
     ($n: expr,) => {};
 }
 
-impl<T: Arbitrary> Arbitrary for [T; 0] {
-    fn arbitrary(_: &mut Unstructured<'_>) -> Result<[T; 0]> {
+impl<'a, T: Arbitrary<'a>> Arbitrary<'a> for [T; 0] {
+    fn arbitrary(_: &mut Unstructured<'a>) -> Result<[T; 0]> {
         Ok([])
     }
 
-    fn arbitrary_take_rest(_: Unstructured<'_>) -> Result<[T; 0]> {
+    fn arbitrary_take_rest(_: Unstructured<'a>) -> Result<[T; 0]> {
         Ok([])
     }
 
@@ -784,10 +618,6 @@ impl<T: Arbitrary> Arbitrary for [T; 0] {
     fn size_hint(_: usize) -> (usize, Option<usize>) {
         crate::size_hint::and_all(&[])
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        Box::new(iter::from_fn(|| None))
-    }
 }
 
 arbitrary_array! { 32, (T, a) (T, b) (T, c) (T, d) (T, e) (T, f) (T, g) (T, h)
@@ -796,41 +626,28 @@ arbitrary_array! { 32, (T, a) (T, b) (T, c) (T, d) (T, e) (T, f) (T, g) (T, h)
 (T, z) (T, aa) (T, ab) (T, ac) (T, ad) (T, ae) (T, af)
 (T, ag) }
 
-fn shrink_collection<'a, T, A: Arbitrary>(
-    entries: impl Iterator<Item = T>,
-    f: impl Fn(&T) -> Box<dyn Iterator<Item = A>>,
-) -> Box<dyn Iterator<Item = Vec<A>>> {
-    let entries: Vec<_> = entries.collect();
-    if entries.is_empty() {
-        return empty();
-    }
-
-    let mut shrinkers: Vec<Vec<_>> = vec![];
-    let mut i = entries.len();
-    loop {
-        shrinkers.push(entries.iter().take(i).map(&f).collect());
-        i = i / 2;
-        if i == 0 {
-            break;
-        }
+impl<'a> Arbitrary<'a> for &'a [u8] {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
+        let len = u.arbitrary_len::<u8>()?;
+        u.bytes(len)
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
+        Ok(u.take_rest())
+    }
+
+    #[inline]
+    fn size_hint(depth: usize) -> (usize, Option<usize>) {
+        <usize as Arbitrary>::size_hint(depth)
     }
-    Box::new(iter::once(vec![]).chain(iter::from_fn(move || loop {
-        let mut shrinker = shrinkers.pop()?;
-        let x: Option<Vec<A>> = shrinker.iter_mut().map(|s| s.next()).collect();
-        if x.is_none() {
-            continue;
-        }
-        shrinkers.push(shrinker);
-        return x;
-    })))
 }
 
-impl<A: Arbitrary> Arbitrary for Vec<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Vec<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         u.arbitrary_iter()?.collect()
     }
 
-    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
         u.arbitrary_take_rest_iter()?.collect()
     }
 
@@ -838,18 +655,14 @@ impl<A: Arbitrary> Arbitrary for Vec<A> {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        shrink_collection(self.iter(), |x| x.shrink())
-    }
 }
 
-impl<K: Arbitrary + Ord, V: Arbitrary> Arbitrary for BTreeMap<K, V> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, K: Arbitrary<'a> + Ord, V: Arbitrary<'a>> Arbitrary<'a> for BTreeMap<K, V> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         u.arbitrary_iter()?.collect()
     }
 
-    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
         u.arbitrary_take_rest_iter()?.collect()
     }
 
@@ -857,20 +670,14 @@ impl<K: Arbitrary + Ord, V: Arbitrary> Arbitrary for BTreeMap<K, V> {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let collections =
-            shrink_collection(self.iter(), |(k, v)| Box::new(k.shrink().zip(v.shrink())));
-        Box::new(collections.map(|entries| entries.into_iter().collect()))
-    }
 }
 
-impl<A: Arbitrary + Ord> Arbitrary for BTreeSet<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a> + Ord> Arbitrary<'a> for BTreeSet<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         u.arbitrary_iter()?.collect()
     }
 
-    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
         u.arbitrary_take_rest_iter()?.collect()
     }
 
@@ -878,19 +685,14 @@ impl<A: Arbitrary + Ord> Arbitrary for BTreeSet<A> {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let collections = shrink_collection(self.iter(), |v| v.shrink());
-        Box::new(collections.map(|entries| entries.into_iter().collect()))
-    }
 }
 
-impl<A: Arbitrary + Ord> Arbitrary for BinaryHeap<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a> + Ord> Arbitrary<'a> for BinaryHeap<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         u.arbitrary_iter()?.collect()
     }
 
-    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
         u.arbitrary_take_rest_iter()?.collect()
     }
 
@@ -898,19 +700,16 @@ impl<A: Arbitrary + Ord> Arbitrary for BinaryHeap<A> {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let collections = shrink_collection(self.iter(), |v| v.shrink());
-        Box::new(collections.map(|entries| entries.into_iter().collect()))
-    }
 }
 
-impl<K: Arbitrary + Eq + ::std::hash::Hash, V: Arbitrary> Arbitrary for HashMap<K, V> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, K: Arbitrary<'a> + Eq + ::std::hash::Hash, V: Arbitrary<'a>> Arbitrary<'a>
+    for HashMap<K, V>
+{
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         u.arbitrary_iter()?.collect()
     }
 
-    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
         u.arbitrary_take_rest_iter()?.collect()
     }
 
@@ -918,20 +717,14 @@ impl<K: Arbitrary + Eq + ::std::hash::Hash, V: Arbitrary> Arbitrary for HashMap<
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let collections =
-            shrink_collection(self.iter(), |(k, v)| Box::new(k.shrink().zip(v.shrink())));
-        Box::new(collections.map(|entries| entries.into_iter().collect()))
-    }
 }
 
-impl<A: Arbitrary + Eq + ::std::hash::Hash> Arbitrary for HashSet<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a> + Eq + ::std::hash::Hash> Arbitrary<'a> for HashSet<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         u.arbitrary_iter()?.collect()
     }
 
-    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
         u.arbitrary_take_rest_iter()?.collect()
     }
 
@@ -939,19 +732,14 @@ impl<A: Arbitrary + Eq + ::std::hash::Hash> Arbitrary for HashSet<A> {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let collections = shrink_collection(self.iter(), |v| v.shrink());
-        Box::new(collections.map(|entries| entries.into_iter().collect()))
-    }
 }
 
-impl<A: Arbitrary> Arbitrary for LinkedList<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for LinkedList<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         u.arbitrary_iter()?.collect()
     }
 
-    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
         u.arbitrary_take_rest_iter()?.collect()
     }
 
@@ -959,19 +747,14 @@ impl<A: Arbitrary> Arbitrary for LinkedList<A> {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let collections = shrink_collection(self.iter(), |v| v.shrink());
-        Box::new(collections.map(|entries| entries.into_iter().collect()))
-    }
 }
 
-impl<A: Arbitrary> Arbitrary for VecDeque<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for VecDeque<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         u.arbitrary_iter()?.collect()
     }
 
-    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
         u.arbitrary_take_rest_iter()?.collect()
     }
 
@@ -979,19 +762,14 @@ impl<A: Arbitrary> Arbitrary for VecDeque<A> {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let collections = shrink_collection(self.iter(), |v| v.shrink());
-        Box::new(collections.map(|entries| entries.into_iter().collect()))
-    }
 }
 
-impl<A> Arbitrary for Cow<'static, A>
+impl<'a, A> Arbitrary<'a> for Cow<'a, A>
 where
     A: ToOwned + ?Sized,
-    <A as ToOwned>::Owned: Arbitrary,
+    <A as ToOwned>::Owned: Arbitrary<'a>,
 {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         Arbitrary::arbitrary(u).map(Cow::Owned)
     }
 
@@ -1001,36 +779,29 @@ where
             <<A as ToOwned>::Owned as Arbitrary>::size_hint(depth)
         })
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        match *self {
-            Cow::Owned(ref o) => Box::new(o.shrink().map(Cow::Owned)),
-            Cow::Borrowed(b) => Box::new(b.to_owned().shrink().map(Cow::Owned)),
-        }
-    }
 }
 
-impl Arbitrary for String {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a> Arbitrary<'a> for &'a str {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         let size = u.arbitrary_len::<u8>()?;
         match str::from_utf8(&u.peek_bytes(size).unwrap()) {
             Ok(s) => {
-                u.get_bytes(size).unwrap();
-                Ok(s.into())
+                u.bytes(size).unwrap();
+                Ok(s)
             }
             Err(e) => {
                 let i = e.valid_up_to();
-                let valid = u.get_bytes(i).unwrap();
+                let valid = u.bytes(i).unwrap();
                 let s = unsafe {
                     debug_assert!(str::from_utf8(valid).is_ok());
                     str::from_utf8_unchecked(valid)
                 };
-                Ok(s.into())
+                Ok(s)
             }
         }
     }
 
-    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
         let bytes = u.take_rest();
         str::from_utf8(bytes)
             .map_err(|_| Error::IncorrectFormat)
@@ -1041,15 +812,25 @@ impl Arbitrary for String {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
     }
+}
 
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let collections = shrink_collection(self.chars(), |ch| ch.shrink());
-        Box::new(collections.map(|chars| chars.into_iter().collect()))
+impl<'a> Arbitrary<'a> for String {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
+        <&str as Arbitrary>::arbitrary(u).map(Into::into)
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
+        <&str as Arbitrary>::arbitrary_take_rest(u).map(Into::into)
+    }
+
+    #[inline]
+    fn size_hint(depth: usize) -> (usize, Option<usize>) {
+        <&str as Arbitrary>::size_hint(depth)
     }
 }
 
-impl Arbitrary for CString {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a> Arbitrary<'a> for CString {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         <Vec<u8> as Arbitrary>::arbitrary(u).map(|mut x| {
             x.retain(|&c| c != 0);
             Self::new(x).unwrap()
@@ -1060,17 +841,10 @@ impl Arbitrary for CString {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         <Vec<u8> as Arbitrary>::size_hint(depth)
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let collections = shrink_collection(self.as_bytes().iter(), |b| {
-            Box::new(b.shrink().filter(|&b| b != 0))
-        });
-        Box::new(collections.map(|bytes| Self::new(bytes).unwrap()))
-    }
 }
 
-impl Arbitrary for OsString {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a> Arbitrary<'a> for OsString {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         <String as Arbitrary>::arbitrary(u).map(From::from)
     }
 
@@ -1078,18 +852,10 @@ impl Arbitrary for OsString {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         <String as Arbitrary>::size_hint(depth)
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        match self.clone().into_string() {
-            Err(_) if self.is_empty() => empty(),
-            Err(_) => once(OsString::from("".to_string())),
-            Ok(s) => Box::new(s.shrink().map(From::from)),
-        }
-    }
 }
 
-impl Arbitrary for PathBuf {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a> Arbitrary<'a> for PathBuf {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         <OsString as Arbitrary>::arbitrary(u).map(From::from)
     }
 
@@ -1097,15 +863,10 @@ impl Arbitrary for PathBuf {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         <OsString as Arbitrary>::size_hint(depth)
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let s = self.clone().into_os_string();
-        Box::new(s.shrink().map(From::from))
-    }
 }
 
-impl<A: Arbitrary> Arbitrary for Box<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Box<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         Arbitrary::arbitrary(u).map(Self::new)
     }
 
@@ -1113,14 +874,10 @@ impl<A: Arbitrary> Arbitrary for Box<A> {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         crate::size_hint::recursion_guard(depth, |depth| <A as Arbitrary>::size_hint(depth))
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        Box::new((&**self).shrink().map(Self::new))
-    }
 }
 
-impl<A: Arbitrary> Arbitrary for Box<[A]> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Box<[A]> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         <Vec<A> as Arbitrary>::arbitrary(u).map(|x| x.into_boxed_slice())
     }
 
@@ -1128,14 +885,10 @@ impl<A: Arbitrary> Arbitrary for Box<[A]> {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         <Vec<A> as Arbitrary>::size_hint(depth)
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        Box::new(shrink_collection(self.iter(), |x| x.shrink()).map(|v| v.into_boxed_slice()))
-    }
 }
 
-impl Arbitrary for Box<str> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a> Arbitrary<'a> for Box<str> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         <String as Arbitrary>::arbitrary(u).map(|x| x.into_boxed_str())
     }
 
@@ -1143,11 +896,6 @@ impl Arbitrary for Box<str> {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         <String as Arbitrary>::size_hint(depth)
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let collections = shrink_collection(self.chars(), |ch| ch.shrink());
-        Box::new(collections.map(|chars| chars.into_iter().collect::<String>().into_boxed_str()))
-    }
 }
 
 // impl Arbitrary for Box<CStr> {
@@ -1163,8 +911,8 @@ impl Arbitrary for Box<str> {
 //     }
 // }
 
-impl<A: Arbitrary> Arbitrary for Arc<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Arc<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         Arbitrary::arbitrary(u).map(Self::new)
     }
 
@@ -1172,14 +920,10 @@ impl<A: Arbitrary> Arbitrary for Arc<A> {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         crate::size_hint::recursion_guard(depth, |depth| <A as Arbitrary>::size_hint(depth))
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        Box::new((&**self).shrink().map(Self::new))
-    }
 }
 
-impl<A: Arbitrary> Arbitrary for Rc<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Rc<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         Arbitrary::arbitrary(u).map(Self::new)
     }
 
@@ -1187,77 +931,54 @@ impl<A: Arbitrary> Arbitrary for Rc<A> {
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
         crate::size_hint::recursion_guard(depth, |depth| <A as Arbitrary>::size_hint(depth))
     }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        Box::new((&**self).shrink().map(Self::new))
-    }
 }
 
-impl<A: Arbitrary> Arbitrary for Cell<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Cell<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         Arbitrary::arbitrary(u).map(Self::new)
     }
 
     #[inline]
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        <A as Arbitrary>::size_hint(depth)
+        <A as Arbitrary<'a>>::size_hint(depth)
     }
-
-    // Note: can't implement `shrink` without either more trait bounds on `A`
-    // (copy or default) or `Cell::update`:
-    // https://github.com/rust-lang/rust/issues/50186
 }
 
-impl<A: Arbitrary> Arbitrary for RefCell<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for RefCell<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         Arbitrary::arbitrary(u).map(Self::new)
     }
 
     #[inline]
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        <A as Arbitrary>::size_hint(depth)
-    }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let x = self.borrow();
-        Box::new(x.shrink().map(Self::new))
+        <A as Arbitrary<'a>>::size_hint(depth)
     }
 }
 
-impl<A: Arbitrary> Arbitrary for UnsafeCell<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for UnsafeCell<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         Arbitrary::arbitrary(u).map(Self::new)
     }
 
     #[inline]
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        <A as Arbitrary>::size_hint(depth)
+        <A as Arbitrary<'a>>::size_hint(depth)
     }
-
-    // We can't non-trivially (i.e. not an empty iterator) implement `shrink` in
-    // a safe way, since we don't have a safe way to get the inner value.
 }
 
-impl<A: Arbitrary> Arbitrary for Mutex<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Mutex<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         Arbitrary::arbitrary(u).map(Self::new)
     }
 
     #[inline]
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        <A as Arbitrary>::size_hint(depth)
-    }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        match self.lock() {
-            Err(_) => empty(),
-            Ok(g) => Box::new(g.shrink().map(Self::new)),
-        }
+        <A as Arbitrary<'a>>::size_hint(depth)
     }
 }
 
-impl<A: Arbitrary> Arbitrary for iter::Empty<A> {
-    fn arbitrary(_: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for iter::Empty<A> {
+    fn arbitrary(_: &mut Unstructured<'a>) -> Result<Self> {
         Ok(iter::empty())
     }
 
@@ -1265,12 +986,10 @@ impl<A: Arbitrary> Arbitrary for iter::Empty<A> {
     fn size_hint(_depth: usize) -> (usize, Option<usize>) {
         (0, Some(0))
     }
-
-    // Nothing to shrink here.
 }
 
-impl<A: Arbitrary> Arbitrary for ::std::marker::PhantomData<A> {
-    fn arbitrary(_: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for ::std::marker::PhantomData<A> {
+    fn arbitrary(_: &mut Unstructured<'a>) -> Result<Self> {
         Ok(::std::marker::PhantomData)
     }
 
@@ -1278,23 +997,16 @@ impl<A: Arbitrary> Arbitrary for ::std::marker::PhantomData<A> {
     fn size_hint(_depth: usize) -> (usize, Option<usize>) {
         (0, Some(0))
     }
-
-    // Nothing to shrink here.
 }
 
-impl<A: Arbitrary> Arbitrary for ::std::num::Wrapping<A> {
-    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for ::std::num::Wrapping<A> {
+    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
         Arbitrary::arbitrary(u).map(::std::num::Wrapping)
     }
 
     #[inline]
     fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        <A as Arbitrary>::size_hint(depth)
-    }
-
-    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
-        let ref x = self.0;
-        Box::new(x.shrink().map(::std::num::Wrapping))
+        <A as Arbitrary<'a>>::size_hint(depth)
     }
 }
 
@@ -1325,6 +1037,24 @@ mod test {
     }
 
     #[test]
+    fn arbitrary_for_bytes() {
+        let x = [1, 2, 3, 4, 4];
+        let mut buf = Unstructured::new(&x);
+        let expected = &[1, 2, 3, 4];
+        let actual = <&[u8] as Arbitrary>::arbitrary(&mut buf).unwrap();
+        assert_eq!(expected, actual);
+    }
+
+    #[test]
+    fn arbitrary_take_rest_for_bytes() {
+        let x = [1, 2, 3, 4];
+        let buf = Unstructured::new(&x);
+        let expected = &[1, 2, 3, 4];
+        let actual = <&[u8] as Arbitrary>::arbitrary_take_rest(buf).unwrap();
+        assert_eq!(expected, actual);
+    }
+
+    #[test]
     fn arbitrary_collection() {
         let x = [
             1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 8,
@@ -1361,113 +1091,11 @@ mod test {
     }
 
     #[test]
-    fn shrink_tuple() {
-        let tup = (10, 20, 30);
-        assert_eq!(
-            tup.shrink().collect::<Vec<_>>(),
-            [(0, 0, 0), (5, 10, 15), (2, 5, 7), (1, 2, 3)]
-        );
-    }
-
-    #[test]
-    fn shrink_array() {
-        let tup = [10, 20, 30];
-        assert_eq!(
-            tup.shrink().collect::<Vec<_>>(),
-            [[0, 0, 0], [5, 10, 15], [2, 5, 7], [1, 2, 3]]
-        );
-    }
-
-    #[test]
-    fn shrink_vec() {
-        let v = vec![4, 4, 4, 4];
-        assert_eq!(
-            v.shrink().collect::<Vec<_>>(),
-            [
-                vec![],
-                vec![0],
-                vec![2],
-                vec![1],
-                vec![0, 0],
-                vec![2, 2],
-                vec![1, 1],
-                vec![0, 0, 0, 0],
-                vec![2, 2, 2, 2],
-                vec![1, 1, 1, 1]
-            ]
-        );
-    }
-
-    #[test]
-    fn shrink_string() {
-        let s = "aaaa".to_string();
-        assert_eq!(
-            s.shrink().collect::<Vec<_>>(),
-            [
-                "",
-                "\u{0}",
-                "0",
-                "\u{18}",
-                "\u{c}",
-                "\u{6}",
-                "\u{3}",
-                "\u{1}",
-                "\u{0}\u{0}",
-                "00",
-                "\u{18}\u{18}",
-                "\u{c}\u{c}",
-                "\u{6}\u{6}",
-                "\u{3}\u{3}",
-                "\u{1}\u{1}",
-                "\u{0}\u{0}\u{0}\u{0}",
-                "0000",
-                "\u{18}\u{18}\u{18}\u{18}",
-                "\u{c}\u{c}\u{c}\u{c}",
-                "\u{6}\u{6}\u{6}\u{6}",
-                "\u{3}\u{3}\u{3}\u{3}",
-                "\u{1}\u{1}\u{1}\u{1}"
-            ]
-            .iter()
-            .map(|s| s.to_string())
-            .collect::<Vec<_>>(),
-        );
-    }
-
-    #[test]
-    fn shrink_cstring() {
-        let s = CString::new(b"aaaa".to_vec()).unwrap();
+    fn size_hint_for_tuples() {
         assert_eq!(
-            s.shrink().collect::<Vec<_>>(),
-            [
-                &[][..],
-                &[b'0'][..],
-                &[0x18][..],
-                &[0x0c][..],
-                &[0x06][..],
-                &[0x03][..],
-                &[0x01][..],
-                &[b'0', b'0'][..],
-                &[0x18, 0x18][..],
-                &[0x0c, 0x0c][..],
-                &[0x06, 0x06][..],
-                &[0x03, 0x03][..],
-                &[0x01, 0x01][..],
-                &[b'0', b'0', b'0', b'0'][..],
-                &[0x18, 0x18, 0x18, 0x18][..],
-                &[0x0c, 0x0c, 0x0c, 0x0c][..],
-                &[0x06, 0x06, 0x06, 0x06][..],
-                &[0x03, 0x03, 0x03, 0x03][..],
-                &[0x01, 0x01, 0x01, 0x01][..],
-            ]
-            .iter()
-            .map(|s| CString::new(s.to_vec()).unwrap())
-            .collect::<Vec<_>>(),
+            (7, Some(7)),
+            <(bool, u16, i32) as Arbitrary<'_>>::size_hint(0)
         );
-    }
-
-    #[test]
-    fn size_hint_for_tuples() {
-        assert_eq!((7, Some(7)), <(bool, u16, i32) as Arbitrary>::size_hint(0));
         assert_eq!(
             (1 + mem::size_of::<usize>(), None),
             <(u8, Vec<u8>) as Arbitrary>::size_hint(0)
diff --git a/src/size_hint.rs b/src/size_hint.rs
index e2aecc2..045c148 100644
--- a/src/size_hint.rs
+++ b/src/size_hint.rs
@@ -8,9 +8,6 @@
 /// size hint.
 ///
 /// Otherwise, returns the default size hint: `(0, None)`.
-///
-/// See the [docs for `Arbitrary::shrink`][crate::Arbitrary::shrink] for example
-/// usage.
 #[inline]
 pub fn recursion_guard(
     depth: usize,
diff --git a/src/unstructured.rs b/src/unstructured.rs
index 7f1b728..9e2f497 100644
--- a/src/unstructured.rs
+++ b/src/unstructured.rs
@@ -165,9 +165,9 @@ impl<'a> Unstructured<'a> {
     /// ```
     pub fn arbitrary<A>(&mut self) -> Result<A>
     where
-        A: Arbitrary,
+        A: Arbitrary<'a>,
     {
-        <A as Arbitrary>::arbitrary(self)
+        <A as Arbitrary<'a>>::arbitrary(self)
     }
 
     /// Get the number of elements to insert when building up a collection of
@@ -190,11 +190,11 @@ impl<'a> Unstructured<'a> {
     /// #     pub fn insert(&mut self, element: T) {}
     /// # }
     ///
-    /// impl<T> Arbitrary for MyCollection<T>
+    /// impl<'a, T> Arbitrary<'a> for MyCollection<T>
     /// where
-    ///     T: Arbitrary,
+    ///     T: Arbitrary<'a>,
     /// {
-    ///     fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+    ///     fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
     ///         // Get the number of `T`s we should insert into our collection.
     ///         let len = u.arbitrary_len::<T>()?;
     ///
@@ -211,7 +211,7 @@ impl<'a> Unstructured<'a> {
     /// ```
     pub fn arbitrary_len<ElementType>(&mut self) -> Result<usize>
     where
-        ElementType: Arbitrary,
+        ElementType: Arbitrary<'a>,
     {
         let byte_size = self.arbitrary_byte_size()?;
         let (lower, upper) = <ElementType as Arbitrary>::size_hint(0);
@@ -233,7 +233,8 @@ impl<'a> Unstructured<'a> {
             //
             // https://github.com/rust-fuzz/libfuzzer-sys/blob/0c450753/libfuzzer/utils/FuzzedDataProvider.h#L92-L97
 
-            // We only consume as many bytes as necessary to cover the entire range of the byte string
+            // We only consume as many bytes as necessary to cover the entire
+            // range of the byte string.
             let len = if self.data.len() <= std::u8::MAX as usize + 1 {
                 let bytes = 1;
                 let max_size = self.data.len() - bytes;
@@ -310,6 +311,12 @@ impl<'a> Unstructured<'a> {
             "`arbitrary::Unstructured::int_in_range` requires a non-empty range"
         );
 
+        // When there is only one possible choice, don't waste any entropy from
+        // the underlying data.
+        if start == end {
+            return Ok((*start, 0));
+        }
+
         let range: T::Widest = end.as_widest() - start.as_widest();
         let mut result = T::Widest::ZERO;
         let mut offset: usize = 0;
@@ -338,29 +345,39 @@ impl<'a> Unstructured<'a> {
     /// This should only be used inside of `Arbitrary` implementations.
     ///
     /// Returns an error if there is not enough underlying data to make a
-    /// choice.
+    /// choice or if no choices are provided.
     ///
-    /// # Panics
+    /// # Examples
     ///
-    /// Panics if `choices` is empty.
+    /// Selecting from an array of choices:
     ///
-    /// # Example
+    /// ```
+    /// use arbitrary::Unstructured;
+    ///
+    /// let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]);
+    /// let choices = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
+    ///
+    /// let choice = u.choose(&choices).unwrap();
+    ///
+    /// println!("chose {}", choice);
+    /// ```
+    ///
+    /// An error is returned if no choices are provided:
     ///
     /// ```
     /// use arbitrary::Unstructured;
     ///
     /// let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]);
+    /// let choices: [char; 0] = [];
     ///
-    /// let choices = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
-    /// if let Ok(ch) = u.choose(&choices) {
-    ///     println!("chose {}", ch);
-    /// }
+    /// let result = u.choose(&choices);
+    ///
+    /// assert!(result.is_err());
     /// ```
     pub fn choose<'b, T>(&mut self, choices: &'b [T]) -> Result<&'b T> {
-        assert!(
-            !choices.is_empty(),
-            "`arbitrary::Unstructured::choose` must be given a non-empty set of choices"
-        );
+        if choices.is_empty() {
+            return Err(Error::EmptyChoose);
+        }
         let idx = self.int_in_range(0..=choices.len() - 1)?;
         Ok(&choices[idx])
     }
@@ -412,10 +429,10 @@ impl<'a> Unstructured<'a> {
     ///
     /// let mut u = Unstructured::new(&[1, 2, 3, 4]);
     ///
-    /// assert!(u.get_bytes(2).unwrap() == &[1, 2]);
-    /// assert!(u.get_bytes(2).unwrap() == &[3, 4]);
+    /// assert!(u.bytes(2).unwrap() == &[1, 2]);
+    /// assert!(u.bytes(2).unwrap() == &[3, 4]);
     /// ```
-    pub fn get_bytes(&mut self, size: usize) -> Result<&'a [u8]> {
+    pub fn bytes(&mut self, size: usize) -> Result<&'a [u8]> {
         if self.data.len() < size {
             return Err(Error::NotEnoughData);
         }
@@ -473,7 +490,7 @@ impl<'a> Unstructured<'a> {
     ///
     /// This is useful for implementing [`Arbitrary::arbitrary`] on collections
     /// since the implementation is simply `u.arbitrary_iter()?.collect()`
-    pub fn arbitrary_iter<'b, ElementType: Arbitrary>(
+    pub fn arbitrary_iter<'b, ElementType: Arbitrary<'a>>(
         &'b mut self,
     ) -> Result<ArbitraryIter<'a, 'b, ElementType>> {
         Ok(ArbitraryIter {
@@ -487,7 +504,7 @@ impl<'a> Unstructured<'a> {
     ///
     /// This is useful for implementing [`Arbitrary::arbitrary_take_rest`] on collections
     /// since the implementation is simply `u.arbitrary_take_rest_iter()?.collect()`
-    pub fn arbitrary_take_rest_iter<ElementType: Arbitrary>(
+    pub fn arbitrary_take_rest_iter<ElementType: Arbitrary<'a>>(
         self,
     ) -> Result<ArbitraryTakeRestIter<'a, ElementType>> {
         let (lower, upper) = ElementType::size_hint(0);
@@ -509,7 +526,7 @@ pub struct ArbitraryIter<'a, 'b, ElementType> {
     _marker: PhantomData<ElementType>,
 }
 
-impl<'a, 'b, ElementType: Arbitrary> Iterator for ArbitraryIter<'a, 'b, ElementType> {
+impl<'a, 'b, ElementType: Arbitrary<'a>> Iterator for ArbitraryIter<'a, 'b, ElementType> {
     type Item = Result<ElementType>;
     fn next(&mut self) -> Option<Result<ElementType>> {
         let keep_going = self.u.arbitrary().unwrap_or(false);
@@ -528,7 +545,7 @@ pub struct ArbitraryTakeRestIter<'a, ElementType> {
     _marker: PhantomData<ElementType>,
 }
 
-impl<'a, ElementType: Arbitrary> Iterator for ArbitraryTakeRestIter<'a, ElementType> {
+impl<'a, ElementType: Arbitrary<'a>> Iterator for ArbitraryTakeRestIter<'a, ElementType> {
     type Item = Result<ElementType>;
     fn next(&mut self) -> Option<Result<ElementType>> {
         if let Some(mut u) = self.u.take() {
diff --git a/tests/derive.rs b/tests/derive.rs
index 7f1e85e..9dfbbd5 100644
--- a/tests/derive.rs
+++ b/tests/derive.rs
@@ -2,7 +2,7 @@
 
 use arbitrary::*;
 
-fn arbitrary_from<T: Arbitrary>(input: &[u8]) -> T {
+fn arbitrary_from<'a, T: Arbitrary<'a>>(input: &'a [u8]) -> T {
     let mut buf = Unstructured::new(input);
     T::arbitrary(&mut buf).expect("can create arbitrary instance OK")
 }
@@ -21,15 +21,6 @@ fn struct_with_named_fields() {
     assert_eq!(rgb.g, 5);
     assert_eq!(rgb.b, 6);
 
-    assert_eq!(
-        rgb.shrink().collect::<Vec<_>>(),
-        vec![
-            Rgb { r: 0, g: 0, b: 0 },
-            Rgb { r: 2, g: 2, b: 3 },
-            Rgb { r: 1, g: 1, b: 1 }
-        ]
-    );
-
     assert_eq!((3, Some(3)), <Rgb as Arbitrary>::size_hint(0));
 }
 
@@ -46,11 +37,6 @@ fn tuple_struct() {
     assert_eq!(s.0, 42);
     assert_eq!(s.1, true);
 
-    for ((a, b), s) in 42.shrink().zip(true.shrink()).zip(s.shrink()) {
-        assert_eq!(a, s.0);
-        assert_eq!(b, s.1);
-    }
-
     assert_eq!((2, Some(2)), <MyTupleStruct as Arbitrary>::size_hint(0));
 }
 
@@ -106,36 +92,16 @@ fn derive_enum() {
         match e {
             MyEnum::Unit => {
                 saw_unit = true;
-                assert_eq!(e.shrink().count(), 0);
             }
             MyEnum::Tuple(a, b) => {
                 saw_tuple = true;
                 assert_eq!(a, arbitrary_from(&raw[4..5]));
                 assert_eq!(b, arbitrary_from(&raw[5..]));
-
-                for ((a, b), e) in a.shrink().zip(b.shrink()).zip(e.shrink()) {
-                    match e {
-                        MyEnum::Tuple(c, d) => {
-                            assert_eq!(a, c);
-                            assert_eq!(b, d);
-                        }
-                        _ => panic!("should never shrink to a different variant"),
-                    }
-                }
             }
             MyEnum::Struct { a, b } => {
                 saw_struct = true;
                 assert_eq!(a, arbitrary_from(&raw[4..8]));
                 assert_eq!(b, arbitrary_from(&raw[8..]));
-                for ((a, b), e) in a.shrink().zip(b.shrink()).zip(e.shrink()) {
-                    match e {
-                        MyEnum::Struct { a: c, b: d } => {
-                            assert_eq!(a, c);
-                            assert_eq!(b, d);
-                        }
-                        _ => panic!("should never shrink to a different variant"),
-                    }
-                }
             }
         }
     }
@@ -184,3 +150,39 @@ fn generics() {
     assert_eq!(lower, 4);
     assert_eq!(upper, Some(4));
 }
+
+#[derive(Arbitrary, Debug)]
+struct OneLifetime<'a> {
+    alpha: &'a str,
+}
+
+#[test]
+fn one_lifetime() {
+    // Last byte is used for length
+    let raw: Vec<u8> = vec![97, 98, 99, 100, 3];
+    let lifetime: OneLifetime = arbitrary_from(&raw);
+    assert_eq!("abc", lifetime.alpha);
+
+    let (lower, upper) = <OneLifetime as Arbitrary>::size_hint(0);
+    assert_eq!(lower, 8);
+    assert_eq!(upper, None);
+}
+
+#[derive(Arbitrary, Debug)]
+struct TwoLifetimes<'a, 'b> {
+    alpha: &'a str,
+    beta: &'b str,
+}
+
+#[test]
+fn two_lifetimes() {
+    // Last byte is used for length
+    let raw: Vec<u8> = vec![97, 98, 99, 100, 101, 102, 103, 3];
+    let lifetime: TwoLifetimes = arbitrary_from(&raw);
+    assert_eq!("abc", lifetime.alpha);
+    assert_eq!("def", lifetime.beta);
+
+    let (lower, upper) = <TwoLifetimes as Arbitrary>::size_hint(0);
+    assert_eq!(lower, 16);
+    assert_eq!(upper, None);
+}