Import 'arbitrary' rust crate am: d8cadc5d18 am: 2c6dfa91c2

Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/arbitrary/+/1500663

MUST ONLY BE SUBMITTED BY AUTOMERGER

Change-Id: I8017aebf34315511eff3ab6fa1cbbbe268ffffe0

15 files changed, 3035 insertions, 0 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
new file mode 100644
index 0000000..e531caf
--- /dev/null
+++ b/.cargo_vcs_info.json
@@ -0,0 +1,5 @@
+{
+  "git": {
+    "sha1": "570e96046a3f8589d2359a49b9197ea158077d3f"
+  }
+}
diff --git a/.github/workflows/rust.yml b/.github/workflows/rust.yml
new file mode 100644
index 0000000..14c2d65
--- /dev/null
+++ b/.github/workflows/rust.yml
@@ -0,0 +1,35 @@
+name: Rust
+
+on: [push, pull_request]
+
+jobs:
+  vanilla_build:
+    name: Vanilla Build
+    runs-on: ubuntu-latest
+    steps:
+    - uses: actions/checkout@v1
+    - run: rustup update
+    - name: Build
+      run: cargo build --verbose --all
+    - name: Run tests
+      run: cargo test --verbose --all
+  all_features_build:
+    name: All Features Enabled Build
+    runs-on: ubuntu-latest
+    steps:
+    - uses: actions/checkout@v1
+    - run: rustup update
+    - name: Build
+      run: cargo build --verbose --all-features --all
+    - name: Run tests
+      run: cargo test --verbose --all-features --all
+    - name: Build Examples
+      run: cargo build --examples --all-features --all
+  rustfmt:
+    name: Check rustfmt
+    runs-on: ubuntu-latest
+    steps:
+    - uses: actions/checkout@v1
+    - run: rustup update
+    - run: rustup component add rustfmt --toolchain stable
+    - run: cargo +stable fmt --all -- --check
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..4308d82
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+target/
+**/*.rs.bk
+Cargo.lock
diff --git a/CHANGELOG.md b/CHANGELOG.md
new file mode 100644
index 0000000..8a05879
--- /dev/null
+++ b/CHANGELOG.md
@@ -0,0 +1,220 @@
+## Unreleased
+
+Released YYYY-MM-DD.
+
+### Added
+
+* TODO (or remove section if none)
+
+### Changed
+
+* TODO (or remove section if none)
+
+### Deprecated
+
+* TODO (or remove section if none)
+
+### Removed
+
+* TODO (or remove section if none)
+
+### Fixed
+
+* TODO (or remove section if none)
+
+### Security
+
+* TODO (or remove section if none)
+
+--------------------------------------------------------------------------------
+
+## 0.4.6
+
+Released 2020-08-22.
+
+### Added
+
+* Added the `Unstructured::peek_bytes` method.
+
+### Changed
+
+* Test case reduction via `cargo fuzz tmin` should be much more effective at
+  reducing the sizes of collections now. (See
+  [#53](https://github.com/rust-fuzz/arbitrary/pull/53) and the commit messages
+  for details.)
+
+* Fuzzing with mutation-based fuzzers (like libFuzzer) should be more efficient
+  now. (See [#53](https://github.com/rust-fuzz/arbitrary/pull/53) and the commit
+  messages for details)
+
+--------------------------------------------------------------------------------
+
+## 0.4.5
+
+Released 2020-06-18.
+
+### Added
+
+* Implement `Arbitrary` for zero length arrays.
+* Implement `Arbitrary` for `Range` and `RangeInclusive`.
+
+--------------------------------------------------------------------------------
+
+## 0.4.4
+
+Released 2020-04-29.
+
+### Fixed
+
+* Fixed the custom derive for enums when used via its full path (like
+  `#[derive(arbitrary::Arbitrary)]` rather than like `#[derive(Arbitrary)]`).
+
+
+## 0.4.3
+
+Released 2020-04-28.
+
+### Fixed
+
+* Fixed the custom derive when used via its full path (like
+  `#[derive(arbitrary::Arbitrary)]` rather than like `#[derive(Arbitrary)]`).
+
+--------------------------------------------------------------------------------
+
+## 0.4.2
+
+Released 2020-04-17.
+
+### Changed
+
+* We forgot to release a new version of the `derive_arbitrary` crate last
+  release. This release fixes that and so the `synstructure` dependency is
+  finally actually removed in the cargo releases.
+
+--------------------------------------------------------------------------------
+
+## 0.4.1
+
+Released 2020-03-18.
+
+### Removed
+
+* Removed an internal dependency on the `synstructure` crate when the `derive`
+  feature is enabled. This should not have any visible downstream effects other
+  than faster build times!
+
+--------------------------------------------------------------------------------
+
+## 0.4.0
+
+Released 2020-01-22.
+
+This is technically a breaking change, but we expect that nearly everyone should
+be able to upgrade without any compilation errors. The only exception is if you
+were implementing the `Arbitrary::size_hint` method by hand. If so, see the
+"changed" section below and the [API docs for
+`Arbitrary::shrink`](https://docs.rs/arbitrary/0.4.0/arbitrary/trait.Arbitrary.html#method.size_hint)
+for details.
+
+### Added
+
+* Added [the `arbitary::size_hint::recursion_guard` helper
+  function][recursion_guard] for guarding against infinite recursion in
+  `size_hint` implementations for recursive types.
+
+### Changed
+
+* The `Arbitrary::size_hint` signature now takes a `depth: usize`
+  parameter. This should be passed along unmodified to any nested calls of other
+  `size_hint` methods. If you're implementing `size_hint` for a recursive type
+  (like a linked list or tree) or a generic type with type parameters, you
+  should use [the new `arbitrary::size_hint::recursion_guard` helper
+  function][recursion_guard].
+
+### Fixed
+
+* Fixed infinite recursion in generated `size_hint` implementations
+  from `#[derive(Arbitrary)]` for recursive types.
+
+[recursion_guard]: https://docs.rs/arbitrary/0.4.0/arbitrary/size_hint/fn.recursion_guard.html
+
+--------------------------------------------------------------------------------
+
+## 0.3.2
+
+Released 2020-01-16.
+
+### Changed
+
+* Updated the custom derive's dependencies.
+
+--------------------------------------------------------------------------------
+
+## 0.3.2
+
+Released 2020-01-15.
+
+### Fixed
+
+* Fixed an over-eager assertion condition in `Unstructured::int_in_range` that
+  would incorrectly trigger when given valid ranges of length one.
+
+--------------------------------------------------------------------------------
+
+## 0.3.1
+
+Released 2020-01-14.
+
+### Fixed
+
+* Fixed some links and version numbers in README.
+
+--------------------------------------------------------------------------------
+
+## 0.3.0
+
+Released 2020-01-14.
+
+### Added
+
+* Added the `"derive"` cargo feature, to enable `#[derive(Arbitrary)]` for
+  custom types. Enabling this feature re-exports functionality from the
+  `derive_arbitrary` crate.
+* The custom derive for `Arbitrary` implements the shrink method for you now.
+* All implementations of `Arbitrary` for `std` types implement shrinking now.
+* Added the `Arbitrary::arbitrary_take_rest` method allows an `Arbitrary`
+  implementation to consume all of the rest of the remaining raw input. It has a
+  default implementation that forwards to `Arbitrary::arbitrary` and the custom
+  derive creates a smart implementation for your custom types.
+* Added the `Arbitrary::size_hint` method for hinting how many raw bytes an
+  implementation needs to construct itself. This has a default implementation,
+  but the custom derive creates a smart implementation for your custom types.
+* Added the `Unstructured::choose` method to choose one thing among a set of
+  choices.
+* Added the `Unstructured::arbitrary_len` method to get an arbitrary length for
+  a collection of some arbitrary type.
+* Added the `Unstructured::arbitrary_iter` method to create an iterator of
+  arbitrary instance of some type.
+
+### Changed
+
+* The `Arbitrary` trait was simplified a bit.
+* `Unstructured` is a concrete type now, not a trait.
+* Switched to Rust 2018 edition.
+
+### Removed
+
+* `RingBuffer` and `FiniteBuffer` are removed. Use `Unstructured` instead.
+
+### Fixed
+
+* Better `Arbitrary` implementation for `char`.
+* Better `Arbitrary` implementation for `String`.
+
+--------------------------------------------------------------------------------
+
+## 0.2.0
+
+--------------------------------------------------------------------------------
+
+## 0.1.0
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..0857f9f
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,41 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# When uploading crates to the registry Cargo will automatically
+# "normalize" Cargo.toml files for maximal compatibility
+# with all versions of Cargo and also rewrite `path` dependencies
+# to registry (e.g., crates.io) dependencies
+#
+# If you believe there's an error in this file please file an
+# issue against the rust-lang/cargo repository. If you're
+# editing this file be aware that the upstream Cargo.toml
+# will likely look very different (and much more reasonable)
+
+[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>"]
+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/"
+
+[[example]]
+name = "derive_enum"
+required-features = ["derive"]
+
+[[test]]
+name = "derive"
+path = "./tests/derive.rs"
+required-features = ["derive"]
+[dependencies.derive_arbitrary]
+version = "=0.4.6"
+optional = true
+
+[dev-dependencies]
+
+[features]
+derive = ["derive_arbitrary"]
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
new file mode 100644
index 0000000..ab70b1e
--- /dev/null
+++ b/Cargo.toml.orig
@@ -0,0 +1,32 @@
+[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>"]
+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/"
+documentation = "https://docs.rs/arbitrary/"
+
+[dependencies]
+derive_arbitrary = { version = "=0.4.6", path = "./derive", optional = true }
+
+[dev-dependencies]
+
+[features]
+# Turn this feature on to enable support for `#[derive(Arbitrary)]`.
+derive = ["derive_arbitrary"]
+
+[[example]]
+name = "derive_enum"
+required-features = ["derive"]
+
+[[test]]
+name = "derive"
+path = "./tests/derive.rs"
+required-features = ["derive"]
+
+[workspace]
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..7c62e6f
--- /dev/null
+++ b/README.md
@@ -0,0 +1,123 @@
+<div align="center">
+
+  <h1><code>Arbitrary</code></h1>
+
+  <p><strong>The trait for generating structured data from arbitrary, unstructured input.</strong></p>
+
+  <img alt="GitHub Actions Status" src="https://github.com/rust-fuzz/rust_arbitrary/workflows/Rust/badge.svg"/>
+
+</div>
+
+## About
+
+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`](https://github.com/rust-fuzz/cargo-fuzz) or
+[AFL](https://github.com/rust-fuzz/afl.rs), 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.
+
+## Documentation
+
+[**Read the API documentation on `docs.rs`!**](https://docs.rs/arbitrary)
+
+## Example
+
+Say you're writing a color conversion library, and you have an `Rgb` struct to
+represent RGB colors. You might want to implement `Arbitrary` for `Rgb` so that
+you could take arbitrary `Rgb` instances in a test function that asserts some
+property (for example, asserting that RGB converted to HSL and converted back to
+RGB always ends up exactly where we started).
+
+### Automatically Deriving `Arbitrary`
+
+Automatically deriving the `Arbitrary` trait is the recommended way to implement
+`Arbitrary` for your types.
+
+Automatically deriving `Arbitrary` requires you to enable the `"derive"` cargo
+feature:
+
+```toml
+# Cargo.toml
+
+[dependencies]
+arbitrary = { version = "0.4", features = ["derive"] }
+```
+
+And then you can simply add `#[derive(Arbitrary)]` annotations to your types:
+
+```rust
+// rgb.rs
+
+use arbitrary::Arbitrary;
+
+#[derive(Arbitrary)]
+pub struct Rgb {
+    pub r: u8,
+    pub g: u8,
+    pub b: u8,
+}
+```
+
+### Implementing `Arbitrary` By Hand
+
+Alternatively, you can write an `Arbitrary` implementation by hand:
+
+```rust
+// rgb.rs
+
+use arbitrary::{Arbitrary, Result, Unstructured};
+
+#[derive(Copy, Clone, Debug)]
+pub struct Rgb {
+    pub r: u8,
+    pub g: u8,
+    pub b: u8,
+}
+
+impl Arbitrary for Rgb {
+    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+        let r = u8::arbitrary(u)?;
+        let g = u8::arbitrary(u)?;
+        let b = u8::arbitrary(u)?;
+        Ok(Rgb { r, g, b })
+    }
+}
+```
+
+### 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.
+
+Unless you explicitly state otherwise, any contribution intentionally submitted
+for inclusion in this project by you, as defined in the Apache-2.0 license,
+shall be dual licensed as above, without any additional terms or conditions.
diff --git a/examples/derive_enum.rs b/examples/derive_enum.rs
new file mode 100644
index 0000000..fbcc106
--- /dev/null
+++ b/examples/derive_enum.rs
@@ -0,0 +1,23 @@
+//! A simple example of deriving the `Arbitrary` trait for an `enum`.
+//!
+//! Note that this requires enabling the "derive" cargo feature.
+
+use arbitrary::{Arbitrary, Unstructured};
+
+#[derive(Arbitrary, Debug)]
+enum MyEnum {
+    UnitVariant,
+    TupleVariant(bool, u32),
+    StructVariant { x: i8, y: (u8, i32) },
+}
+
+fn main() {
+    let raw = b"This is some raw, unstructured data!";
+
+    let mut unstructured = Unstructured::new(raw);
+
+    let instance = MyEnum::arbitrary(&mut unstructured)
+        .expect("`unstructured` has enough underlying data to create all variants of `MyEnum`");
+
+    println!("Here is an arbitrary enum: {:?}", instance);
+}
diff --git a/publish.sh b/publish.sh
new file mode 100755
index 0000000..24db2bd
--- /dev/null
+++ b/publish.sh
@@ -0,0 +1,14 @@
+#!/usr/bin/env bash
+
+set -eux
+
+cd $(dirname $0)/derive
+
+cargo publish
+
+cd ..
+
+# Let the crates.io index figure out we've published `derive_arbitrary` already.
+sleep 5
+
+cargo publish
diff --git a/src/error.rs b/src/error.rs
new file mode 100644
index 0000000..8cbd076
--- /dev/null
+++ b/src/error.rs
@@ -0,0 +1,34 @@
+use std::{error, fmt};
+
+/// An enumeration of buffer creation errors
+#[derive(Debug, Clone, Copy)]
+#[non_exhaustive]
+pub enum Error {
+    /// There was not enough underlying data to fulfill some request for raw
+    /// bytes.
+    NotEnoughData,
+    /// The input bytes were not of the right format
+    IncorrectFormat,
+}
+
+impl fmt::Display for Error {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Error::NotEnoughData => write!(
+                f,
+                "There is not enough underlying raw data to construct an `Arbitrary` instance"
+            ),
+            Error::IncorrectFormat => write!(
+                f,
+                "The raw data is not of the correct format to construct this type"
+            ),
+        }
+    }
+}
+
+impl error::Error for Error {}
+
+/// A `Result` with the error type fixed as `arbitrary::Error`.
+///
+/// Either an `Ok(T)` or `Err(arbitrary::Error)`.
+pub type Result<T> = std::result::Result<T, Error>;
diff --git a/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..2a10718
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1,1476 @@
+// Copyright © 2019 The Rust Fuzz Project 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.
+
+//! The `Arbitrary` trait crate.
+//!
+//! This trait provides an [`Arbitrary`](./trait.Arbitrary.html) trait to
+//! produce well-typed, structured values, from raw, byte buffers. It is
+//! generally intended to be used with fuzzers like AFL or libFuzzer. See the
+//! [`Arbitrary`](./trait.Arbitrary.html) trait's documentation for details on
+//! automatically deriving, implementing, and/or using the trait.
+
+#![deny(bad_style)]
+#![deny(missing_docs)]
+#![deny(future_incompatible)]
+#![deny(nonstandard_style)]
+#![deny(rust_2018_compatibility)]
+#![deny(rust_2018_idioms)]
+#![deny(unused)]
+
+#[cfg(feature = "derive_arbitrary")]
+pub use derive_arbitrary::*;
+
+mod error;
+pub use error::*;
+
+pub mod unstructured;
+#[doc(inline)]
+pub use unstructured::Unstructured;
+
+pub mod size_hint;
+
+use core::cell::{Cell, RefCell, UnsafeCell};
+use core::iter;
+use core::mem;
+use core::ops::{Range, RangeBounds, RangeFrom, RangeInclusive, RangeTo, RangeToInclusive};
+use core::str;
+use core::time::Duration;
+use std::borrow::{Cow, ToOwned};
+use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque};
+use std::ffi::{CString, OsString};
+use std::path::PathBuf;
+use std::rc::Rc;
+use std::sync::atomic::{AtomicBool, AtomicIsize, AtomicUsize, Ordering};
+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.
+///
+/// # Deriving `Arbitrary`
+///
+/// Automatically deriving the `Arbitrary` trait is the recommended way to
+/// implement `Arbitrary` for your types.
+///
+/// Using the custom derive requires that you enable the `"derive"` cargo
+/// feature in your `Cargo.toml`:
+///
+/// ```toml
+/// [dependencies]
+/// arbitrary = { version = "0.2.0", features = ["derive"] }
+/// ```
+///
+/// Then, you add the `#[derive(Arbitrary)]` annotation to your `struct` or
+/// `enum` type definition:
+///
+/// ```
+/// # #[cfg(feature = "derive")] mod foo {
+/// use arbitrary::Arbitrary;
+/// use std::collections::HashSet;
+///
+/// #[derive(Arbitrary)]
+/// pub struct AddressBook {
+///     friends: HashSet<Friend>,
+/// }
+///
+/// #[derive(Arbitrary, Hash, Eq, PartialEq)]
+/// pub enum Friend {
+///     Buddy { name: String },
+///     Pal { age: usize },
+/// }
+/// # }
+/// ```
+///
+/// Every member of the `struct` or `enum` must also implement `Arbitrary`.
+///
+/// # Implementing `Arbitrary` By Hand
+///
+/// Implementing `Arbitrary` mostly involves nested calls to other `Arbitrary`
+/// arbitrary implementations for each of your `struct` or `enum`'s members. But
+/// sometimes you need some amount of raw data, or you need to generate a
+/// variably-sized collection type, or you something of that sort. The
+/// [`Unstructured`][crate::Unstructured] type helps you with these tasks.
+///
+/// ```
+/// # #[cfg(feature = "derive")] mod foo {
+/// # pub struct MyCollection<T> { _t: std::marker::PhantomData<T> }
+/// # impl<T> MyCollection<T> {
+/// #     pub fn new() -> Self { MyCollection { _t: std::marker::PhantomData } }
+/// #     pub fn insert(&mut self, element: T) {}
+/// # }
+/// use arbitrary::{Arbitrary, Result, Unstructured};
+///
+/// impl<T> Arbitrary for MyCollection<T>
+/// where
+///     T: Arbitrary,
+/// {
+///     fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+///         // Get an iterator of arbitrary `T`s.
+///         let iter = u.arbitrary_iter::<T>()?;
+///
+///         // And then create a collection!
+///         let mut my_collection = MyCollection::new();
+///         for elem_result in iter {
+///             let elem = elem_result?;
+///             my_collection.insert(elem);
+///         }
+///
+///         Ok(my_collection)
+///     }
+/// }
+/// # }
+/// ```
+pub trait Arbitrary: Sized + 'static {
+    /// Generate an arbitrary value of `Self` from the given unstructured data.
+    ///
+    /// Calling `Arbitrary::arbitrary` requires that you have some raw data,
+    /// perhaps given to you by a fuzzer like AFL or libFuzzer. You wrap this
+    /// raw data in an `Unstructured`, and then you can call `<MyType as
+    /// Arbitrary>::arbitrary` to construct an arbitrary instance of `MyType`
+    /// from that unstuctured data.
+    ///
+    /// Implementation may return an error if there is not enough data to
+    /// construct a full instance of `Self`. This is generally OK: it is better
+    /// to exit early and get the fuzzer to provide more input data, than it is
+    /// to generate default values in place of the missing data, which would
+    /// bias the distribution of generated values, and ultimately make fuzzing
+    /// less efficient.
+    ///
+    /// ```
+    /// # #[cfg(feature = "derive")] fn foo() {
+    /// use arbitrary::{Arbitrary, Unstructured};
+    ///
+    /// #[derive(Arbitrary)]
+    /// pub struct MyType {
+    ///     // ...
+    /// }
+    ///
+    /// // Get the raw data from the fuzzer or wherever else.
+    /// # let get_raw_data_from_fuzzer = || &[];
+    /// let raw_data: &[u8] = get_raw_data_from_fuzzer();
+    ///
+    /// // Wrap that raw data in an `Unstructured`.
+    /// let mut unstructured = Unstructured::new(raw_data);
+    ///
+    /// // Generate an arbitrary instance of `MyType` and do stuff with it.
+    /// if let Ok(value) = MyType::arbitrary(&mut unstructured) {
+    /// #   let do_stuff = |_| {};
+    ///     do_stuff(value);
+    /// }
+    /// # }
+    /// ```
+    ///
+    /// See also the documentation for [`Unstructured`][crate::Unstructured].
+    fn arbitrary(u: &mut Unstructured<'_>) -> 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> {
+        Self::arbitrary(&mut u)
+    }
+
+    /// Get a size hint for how many bytes out of an `Unstructured` this type
+    /// needs to construct itself.
+    ///
+    /// This is useful for determining how many elements we should insert when
+    /// creating an arbitrary collection.
+    ///
+    /// The return value is similar to
+    /// [`Iterator::size_hint`][iterator-size-hint]: it returns a tuple where
+    /// the first element is a lower bound on the number of bytes required, and
+    /// the second element is an optional upper bound.
+    ///
+    /// The default implementation return `(0, None)` which is correct for any
+    /// type, but not ultimately that useful. Using `#[derive(Arbitrary)]` will
+    /// create a better implementation. If you are writing an `Arbitrary`
+    /// implementation by hand, and your type can be part of a dynamically sized
+    /// collection (such as `Vec`), you are strongly encouraged to override this
+    /// default with a better implementation. The
+    /// [`size_hint`][crate::size_hint] module will help with this task.
+    ///
+    /// ## The `depth` Parameter
+    ///
+    /// If you 100% know that the type you are implementing `Arbitrary` for is
+    /// not a recursive type, or your implementation is not transitively calling
+    /// any other `size_hint` methods, you can ignore the `depth` parameter.
+    /// Note that if you are implementing `Arbitrary` for a generic type, you
+    /// cannot guarantee the lack of type recrusion!
+    ///
+    /// Otherwise, you need to use
+    /// [`arbitrary::size_hint::recursion_guard(depth)`][crate::size_hint::recursion_guard]
+    /// to prevent potential infinite recursion when calculating size hints for
+    /// potentially recursive types:
+    ///
+    /// ```
+    /// use arbitrary::{Arbitrary, Unstructured, size_hint};
+    ///
+    /// // This can potentially be a recursive type if `L` or `R` contain
+    /// // something like `Box<Option<MyEither<L, R>>>`!
+    /// enum MyEither<L, R> {
+    ///     Left(L),
+    ///     Right(R),
+    /// }
+    ///
+    /// impl<L, R> Arbitrary for MyEither<L, R>
+    /// where
+    ///     L: Arbitrary,
+    ///     R: Arbitrary,
+    /// {
+    ///     fn arbitrary(u: &mut Unstructured) -> arbitrary::Result<Self> {
+    ///         // ...
+    /// #       unimplemented!()
+    ///     }
+    ///
+    ///     fn size_hint(depth: usize) -> (usize, Option<usize>) {
+    ///         // Protect against potential infinite recursion with
+    ///         // `recursion_guard`.
+    ///         size_hint::recursion_guard(depth, |depth| {
+    ///             // If we aren't too deep, then `recursion_guard` calls
+    ///             // this closure, which implements the natural size hint.
+    ///             // Don't forget to use the new `depth` in all nested
+    ///             // `size_hint` calls! We recommend shadowing the
+    ///             // parameter, like what is done here, so that you can't
+    ///             // accidentally use the wrong depth.
+    ///             size_hint::or(
+    ///                 <L as Arbitrary>::size_hint(depth),
+    ///                 <R as Arbitrary>::size_hint(depth),
+    ///             )
+    ///         })
+    ///     }
+    /// }
+    /// ```
+    ///
+    /// [iterator-size-hint]: https://doc.rust-lang.org/stable/std/iter/trait.Iterator.html#method.size_hint
+    #[inline]
+    fn size_hint(depth: usize) -> (usize, Option<usize>) {
+        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> {
+        Ok(())
+    }
+
+    #[inline]
+    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
+        (0, Some(0))
+    }
+}
+
+impl Arbitrary for bool {
+    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+        Ok(<u8 as Arbitrary>::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() })
+    }
+}
+
+macro_rules! impl_arbitrary_for_integers {
+    ( $( $ty:ty: $unsigned:ty; )* ) => {
+        $(
+            impl Arbitrary for $ty {
+                fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+                    let mut buf = [0; mem::size_of::<$ty>()];
+                    u.fill_buffer(&mut buf)?;
+                    let mut x: $unsigned = 0;
+                    for i in 0..mem::size_of::<$ty>() {
+                        x |= buf[i] as $unsigned << (i * 8);
+                    }
+                    Ok(x as $ty)
+                }
+
+                #[inline]
+                fn size_hint(_depth: usize) -> (usize, Option<usize>) {
+                    let n = mem::size_of::<$ty>();
+                    (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)
+                        }
+                    })))
+                }
+            }
+        )*
+    }
+}
+
+impl_arbitrary_for_integers! {
+    u8: u8;
+    u16: u16;
+    u32: u32;
+    u64: u64;
+    u128: u128;
+    usize: usize;
+    i8: u8;
+    i16: u16;
+    i32: u32;
+    i64: u64;
+    i128: u128;
+    isize: usize;
+}
+
+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)?))
+                }
+
+                #[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)
+                            }
+                        })))
+                    }
+                }
+            }
+        )*
+    }
+}
+
+impl_arbitrary_for_floats! {
+    f32: u32;
+    f64: u64;
+}
+
+impl Arbitrary for char {
+    fn arbitrary(u: &mut Unstructured<'_>) -> 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;
+        if let Some(c) = char::from_u32(c) {
+            return Ok(c);
+        } else {
+            // We found a surrogate, wrap and try again
+            c -= SURROGATES_START;
+            Ok(char::from_u32(c)
+                .expect("Generated character should be valid! This is a bug in arbitrary-rs"))
+        }
+    }
+
+    #[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()
+        }))
+    }
+}
+
+impl Arbitrary for AtomicBool {
+    fn arbitrary(u: &mut Unstructured<'_>) -> 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()
+        }
+    }
+}
+
+impl Arbitrary for AtomicIsize {
+    fn arbitrary(u: &mut Unstructured<'_>) -> 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))
+    }
+}
+
+impl Arbitrary for AtomicUsize {
+    fn arbitrary(u: &mut Unstructured<'_>) -> 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))
+    }
+}
+
+macro_rules! impl_range {
+    (
+        $range:ty,
+        $value_closure:expr,
+        $value_ty:ty,
+        $fun:ident($fun_closure:expr),
+        $size_hint_closure:expr
+    ) => {
+        impl<A> Arbitrary for $range
+        where
+            A: Arbitrary + Clone + PartialOrd,
+        {
+            fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+                let value: $value_ty = Arbitrary::arbitrary(u)?;
+                Ok($fun(value, $fun_closure))
+            }
+
+            #[inline]
+            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)))
+            }
+        }
+    };
+}
+
+impl_range!(
+    Range<A>,
+    |r: &Range<A>| (r.start.clone(), r.end.clone()),
+    (A, A),
+    bounded_range(|(a, b)| a..b),
+    |depth| crate::size_hint::and(
+        <A as Arbitrary>::size_hint(depth),
+        <A as Arbitrary>::size_hint(depth)
+    )
+);
+impl_range!(
+    RangeFrom<A>,
+    |r: &RangeFrom<A>| r.start.clone(),
+    A,
+    unbounded_range(|a| a..),
+    |depth| <A as Arbitrary>::size_hint(depth)
+);
+impl_range!(
+    RangeInclusive<A>,
+    |r: &RangeInclusive<A>| (r.start().clone(), r.end().clone()),
+    (A, A),
+    bounded_range(|(a, b)| a..=b),
+    |depth| crate::size_hint::and(
+        <A as Arbitrary>::size_hint(depth),
+        <A as Arbitrary>::size_hint(depth)
+    )
+);
+impl_range!(
+    RangeTo<A>,
+    |r: &RangeTo<A>| r.end.clone(),
+    A,
+    unbounded_range(|b| ..b),
+    |depth| <A as Arbitrary>::size_hint(depth)
+);
+impl_range!(
+    RangeToInclusive<A>,
+    |r: &RangeToInclusive<A>| r.end.clone(),
+    A,
+    unbounded_range(|b| ..=b),
+    |depth| <A as Arbitrary>::size_hint(depth)
+);
+
+fn bounded_range<CB, I, R>(bounds: (I, I), cb: CB) -> R
+where
+    CB: Fn((I, I)) -> R,
+    I: PartialOrd,
+    R: RangeBounds<I>,
+{
+    let (mut start, mut end) = bounds;
+    if start > end {
+        mem::swap(&mut start, &mut end);
+    }
+    cb((start, end))
+}
+
+fn unbounded_range<CB, I, R>(bound: I, cb: CB) -> R
+where
+    CB: Fn(I) -> R,
+    R: RangeBounds<I>,
+{
+    cb(bound)
+}
+
+impl Arbitrary for Duration {
+    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+        Ok(Self::new(
+            <u64 as Arbitrary>::arbitrary(u)?,
+            <u32 as Arbitrary>::arbitrary(u)? % 1_000_000_000,
+        ))
+    }
+
+    #[inline]
+    fn size_hint(depth: usize) -> (usize, Option<usize>) {
+        crate::size_hint::and(
+            <u64 as Arbitrary>::size_hint(depth),
+            <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)? {
+            Some(Arbitrary::arbitrary(u)?)
+        } else {
+            None
+        })
+    }
+
+    #[inline]
+    fn size_hint(depth: usize) -> (usize, Option<usize>) {
+        crate::size_hint::and(
+            <bool as Arbitrary>::size_hint(depth),
+            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)? {
+            Ok(<A as Arbitrary>::arbitrary(u)?)
+        } else {
+            Err(<B as Arbitrary>::arbitrary(u)?)
+        })
+    }
+
+    #[inline]
+    fn size_hint(depth: usize) -> (usize, Option<usize>) {
+        crate::size_hint::and(
+            <bool as Arbitrary>::size_hint(depth),
+            crate::size_hint::or(
+                <A as Arbitrary>::size_hint(depth),
+                <B as Arbitrary>::size_hint(depth),
+            ),
+        )
+    }
+
+    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 {
+    () => {};
+    ($last: ident $($xs: ident)*) => {
+        arbitrary_tuple!($($xs)*);
+
+        impl<$($xs: Arbitrary,)* $last: Arbitrary> Arbitrary for ($($xs,)* $last,) {
+            fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+                Ok(($($xs::arbitrary(u)?,)* Arbitrary::arbitrary(u)?,))
+            }
+
+            #[allow(unused_mut, non_snake_case)]
+            fn arbitrary_take_rest(mut u: Unstructured<'_>) -> Result<Self> {
+                $(let $xs = $xs::arbitrary(&mut u)?;)*
+                let $last = $last::arbitrary_take_rest(u)?;
+                Ok(($($xs,)* $last,))
+            }
+
+            #[inline]
+            fn size_hint(depth: usize) -> (usize, Option<usize>) {
+                crate::size_hint::and_all(&[
+                    <$last as Arbitrary>::size_hint(depth),
+                    $( <$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()?, ))
+                }))
+            }
+        }
+    };
+}
+arbitrary_tuple!(A B C D E F G H I J K L M N O P Q R S T U V W X Y Z);
+
+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]> {
+                Ok([
+                    Arbitrary::arbitrary(u)?,
+                    $(<$ts as Arbitrary>::arbitrary(u)?),*
+                ])
+            }
+
+            #[allow(unused_mut)]
+            fn arbitrary_take_rest(mut u: Unstructured<'_>) -> Result<[T; $n]> {
+                $(let $as = $ts::arbitrary(&mut u)?;)*
+                let last = Arbitrary::arbitrary_take_rest(u)?;
+
+                Ok([
+                    $($as,)* last
+                ])
+            }
+
+            #[inline]
+            fn size_hint(depth: usize) -> (usize, Option<usize>) {
+                crate::size_hint::and_all(&[
+                    <$t as Arbitrary>::size_hint(depth),
+                    $( <$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]> {
+        Ok([])
+    }
+
+    fn arbitrary_take_rest(_: Unstructured<'_>) -> Result<[T; 0]> {
+        Ok([])
+    }
+
+    #[inline]
+    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)
+(T, i) (T, j) (T, k) (T, l) (T, m) (T, n) (T, o) (T, p)
+(T, q) (T, r) (T, s) (T, u) (T, v) (T, w) (T, x) (T, y)
+(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;
+        }
+    }
+    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> {
+        u.arbitrary_iter()?.collect()
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_take_rest_iter()?.collect()
+    }
+
+    #[inline]
+    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> {
+        u.arbitrary_iter()?.collect()
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_take_rest_iter()?.collect()
+    }
+
+    #[inline]
+    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> {
+        u.arbitrary_iter()?.collect()
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_take_rest_iter()?.collect()
+    }
+
+    #[inline]
+    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> {
+        u.arbitrary_iter()?.collect()
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_take_rest_iter()?.collect()
+    }
+
+    #[inline]
+    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> {
+        u.arbitrary_iter()?.collect()
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_take_rest_iter()?.collect()
+    }
+
+    #[inline]
+    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> {
+        u.arbitrary_iter()?.collect()
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_take_rest_iter()?.collect()
+    }
+
+    #[inline]
+    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> {
+        u.arbitrary_iter()?.collect()
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_take_rest_iter()?.collect()
+    }
+
+    #[inline]
+    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> {
+        u.arbitrary_iter()?.collect()
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_take_rest_iter()?.collect()
+    }
+
+    #[inline]
+    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>
+where
+    A: ToOwned + ?Sized,
+    <A as ToOwned>::Owned: Arbitrary,
+{
+    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+        Arbitrary::arbitrary(u).map(Cow::Owned)
+    }
+
+    #[inline]
+    fn size_hint(depth: usize) -> (usize, Option<usize>) {
+        crate::size_hint::recursion_guard(depth, |depth| {
+            <<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> {
+        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())
+            }
+            Err(e) => {
+                let i = e.valid_up_to();
+                let valid = u.get_bytes(i).unwrap();
+                let s = unsafe {
+                    debug_assert!(str::from_utf8(valid).is_ok());
+                    str::from_utf8_unchecked(valid)
+                };
+                Ok(s.into())
+            }
+        }
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+        let bytes = u.take_rest();
+        str::from_utf8(bytes)
+            .map_err(|_| Error::IncorrectFormat)
+            .map(Into::into)
+    }
+
+    #[inline]
+    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 Arbitrary for CString {
+    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+        <Vec<u8> as Arbitrary>::arbitrary(u).map(|mut x| {
+            x.retain(|&c| c != 0);
+            Self::new(x).unwrap()
+        })
+    }
+
+    #[inline]
+    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> {
+        <String as Arbitrary>::arbitrary(u).map(From::from)
+    }
+
+    #[inline]
+    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> {
+        <OsString as Arbitrary>::arbitrary(u).map(From::from)
+    }
+
+    #[inline]
+    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> {
+        Arbitrary::arbitrary(u).map(Self::new)
+    }
+
+    #[inline]
+    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> {
+        <Vec<A> as Arbitrary>::arbitrary(u).map(|x| x.into_boxed_slice())
+    }
+
+    #[inline]
+    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> {
+        <String as Arbitrary>::arbitrary(u).map(|x| x.into_boxed_str())
+    }
+
+    #[inline]
+    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> {
+//     fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+//         <CString as Arbitrary>::arbitrary(u).map(|x| x.into_boxed_c_str())
+//     }
+// }
+
+// impl Arbitrary for Box<OsStr> {
+//     fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+//         <OsString as Arbitrary>::arbitrary(u).map(|x| x.into_boxed_osstr())
+//
+//     }
+// }
+
+impl<A: Arbitrary> Arbitrary for Arc<A> {
+    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+        Arbitrary::arbitrary(u).map(Self::new)
+    }
+
+    #[inline]
+    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> {
+        Arbitrary::arbitrary(u).map(Self::new)
+    }
+
+    #[inline]
+    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> {
+        Arbitrary::arbitrary(u).map(Self::new)
+    }
+
+    #[inline]
+    fn size_hint(depth: usize) -> (usize, Option<usize>) {
+        <A as Arbitrary>::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> {
+        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))
+    }
+}
+
+impl<A: Arbitrary> Arbitrary for UnsafeCell<A> {
+    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+        Arbitrary::arbitrary(u).map(Self::new)
+    }
+
+    #[inline]
+    fn size_hint(depth: usize) -> (usize, Option<usize>) {
+        <A as Arbitrary>::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> {
+        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)),
+        }
+    }
+}
+
+impl<A: Arbitrary> Arbitrary for iter::Empty<A> {
+    fn arbitrary(_: &mut Unstructured<'_>) -> Result<Self> {
+        Ok(iter::empty())
+    }
+
+    #[inline]
+    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> {
+        Ok(::std::marker::PhantomData)
+    }
+
+    #[inline]
+    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> {
+        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))
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    #[test]
+    fn finite_buffer_fill_buffer() {
+        let x = [1, 2, 3, 4];
+        let mut rb = Unstructured::new(&x);
+        let mut z = [0; 2];
+        rb.fill_buffer(&mut z).unwrap();
+        assert_eq!(z, [1, 2]);
+        rb.fill_buffer(&mut z).unwrap();
+        assert_eq!(z, [3, 4]);
+        rb.fill_buffer(&mut z).unwrap();
+        assert_eq!(z, [0, 0]);
+    }
+
+    #[test]
+    fn arbitrary_for_integers() {
+        let x = [1, 2, 3, 4];
+        let mut buf = Unstructured::new(&x);
+        let expected = 1 | (2 << 8) | (3 << 16) | (4 << 24);
+        let actual = i32::arbitrary(&mut 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,
+        ];
+        assert_eq!(
+            Vec::<u8>::arbitrary(&mut Unstructured::new(&x)).unwrap(),
+            &[2, 4, 6, 8, 1]
+        );
+        assert_eq!(
+            Vec::<u32>::arbitrary(&mut Unstructured::new(&x)).unwrap(),
+            &[84148994]
+        );
+        assert_eq!(
+            String::arbitrary(&mut Unstructured::new(&x)).unwrap(),
+            "\x01\x02\x03\x04\x05\x06\x07\x08"
+        );
+    }
+
+    #[test]
+    fn arbitrary_take_rest() {
+        let x = [1, 2, 3, 4];
+        assert_eq!(
+            Vec::<u8>::arbitrary_take_rest(Unstructured::new(&x)).unwrap(),
+            &[1, 2, 3, 4]
+        );
+        assert_eq!(
+            Vec::<u32>::arbitrary_take_rest(Unstructured::new(&x)).unwrap(),
+            &[0x4030201]
+        );
+        assert_eq!(
+            String::arbitrary_take_rest(Unstructured::new(&x)).unwrap(),
+            "\x01\x02\x03\x04"
+        );
+    }
+
+    #[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();
+        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<_>>(),
+        );
+    }
+
+    #[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
new file mode 100644
index 0000000..e2aecc2
--- /dev/null
+++ b/src/size_hint.rs
@@ -0,0 +1,127 @@
+//! Utilities for working with and combining the results of
+//! [`Arbitrary::size_hint`][crate::Arbitrary::size_hint].
+
+/// Protects against potential infinite recursion when calculating size hints
+/// due to indirect type recursion.
+///
+/// When the depth is not too deep, calls `f` with `depth + 1` to calculate the
+/// 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,
+    f: impl FnOnce(usize) -> (usize, Option<usize>),
+) -> (usize, Option<usize>) {
+    const MAX_DEPTH: usize = 20;
+    if depth > MAX_DEPTH {
+        (0, None)
+    } else {
+        f(depth + 1)
+    }
+}
+
+/// Take the sum of the `lhs` and `rhs` size hints.
+#[inline]
+pub fn and(lhs: (usize, Option<usize>), rhs: (usize, Option<usize>)) -> (usize, Option<usize>) {
+    let lower = lhs.0 + rhs.0;
+    let upper = lhs.1.and_then(|lhs| rhs.1.map(|rhs| lhs + rhs));
+    (lower, upper)
+}
+
+/// Take the sum of all of the given size hints.
+///
+/// If `hints` is empty, returns `(0, Some(0))`, aka the size of consuming
+/// nothing.
+#[inline]
+pub fn and_all(hints: &[(usize, Option<usize>)]) -> (usize, Option<usize>) {
+    hints.iter().copied().fold((0, Some(0)), and)
+}
+
+/// Take the minimum of the lower bounds and maximum of the upper bounds in the
+/// `lhs` and `rhs` size hints.
+#[inline]
+pub fn or(lhs: (usize, Option<usize>), rhs: (usize, Option<usize>)) -> (usize, Option<usize>) {
+    let lower = std::cmp::min(lhs.0, rhs.0);
+    let upper = lhs
+        .1
+        .and_then(|lhs| rhs.1.map(|rhs| std::cmp::max(lhs, rhs)));
+    (lower, upper)
+}
+
+/// Take the maximum of the `lhs` and `rhs` size hints.
+///
+/// If `hints` is empty, returns `(0, Some(0))`, aka the size of consuming
+/// nothing.
+#[inline]
+pub fn or_all(hints: &[(usize, Option<usize>)]) -> (usize, Option<usize>) {
+    if let Some(head) = hints.first().copied() {
+        hints[1..].iter().copied().fold(head, or)
+    } else {
+        (0, Some(0))
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    #[test]
+    fn and() {
+        assert_eq!((5, Some(5)), super::and((2, Some(2)), (3, Some(3))));
+        assert_eq!((5, None), super::and((2, Some(2)), (3, None)));
+        assert_eq!((5, None), super::and((2, None), (3, Some(3))));
+        assert_eq!((5, None), super::and((2, None), (3, None)));
+    }
+
+    #[test]
+    fn or() {
+        assert_eq!((2, Some(3)), super::or((2, Some(2)), (3, Some(3))));
+        assert_eq!((2, None), super::or((2, Some(2)), (3, None)));
+        assert_eq!((2, None), super::or((2, None), (3, Some(3))));
+        assert_eq!((2, None), super::or((2, None), (3, None)));
+    }
+
+    #[test]
+    fn and_all() {
+        assert_eq!((0, Some(0)), super::and_all(&[]));
+        assert_eq!(
+            (7, Some(7)),
+            super::and_all(&[(1, Some(1)), (2, Some(2)), (4, Some(4))])
+        );
+        assert_eq!(
+            (7, None),
+            super::and_all(&[(1, Some(1)), (2, Some(2)), (4, None)])
+        );
+        assert_eq!(
+            (7, None),
+            super::and_all(&[(1, Some(1)), (2, None), (4, Some(4))])
+        );
+        assert_eq!(
+            (7, None),
+            super::and_all(&[(1, None), (2, Some(2)), (4, Some(4))])
+        );
+    }
+
+    #[test]
+    fn or_all() {
+        assert_eq!((0, Some(0)), super::or_all(&[]));
+        assert_eq!(
+            (1, Some(4)),
+            super::or_all(&[(1, Some(1)), (2, Some(2)), (4, Some(4))])
+        );
+        assert_eq!(
+            (1, None),
+            super::or_all(&[(1, Some(1)), (2, Some(2)), (4, None)])
+        );
+        assert_eq!(
+            (1, None),
+            super::or_all(&[(1, Some(1)), (2, None), (4, Some(4))])
+        );
+        assert_eq!(
+            (1, None),
+            super::or_all(&[(1, None), (2, Some(2)), (4, Some(4))])
+        );
+    }
+}
diff --git a/src/unstructured.rs b/src/unstructured.rs
new file mode 100644
index 0000000..7f1b728
--- /dev/null
+++ b/src/unstructured.rs
@@ -0,0 +1,687 @@
+// Copyright © 2019 The Rust Fuzz Project 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.
+
+//! Wrappers around raw, unstructured bytes.
+
+use crate::{Arbitrary, Error, Result};
+use std::marker::PhantomData;
+use std::{mem, ops};
+
+/// A source of unstructured data.
+///
+/// An `Unstructured` helps `Arbitrary` implementations interpret raw data
+/// (typically provided by a fuzzer) as a "DNA string" that describes how to
+/// construct the `Arbitrary` type. The goal is that a small change to the "DNA
+/// string" (the raw data wrapped by an `Unstructured`) results in a small
+/// change to the generated `Arbitrary` instance. This helps a fuzzer
+/// efficiently explore the `Arbitrary`'s input space.
+///
+/// `Unstructured` is deterministic: given the same raw data, the same series of
+/// API calls will return the same results (modulo system resource constraints,
+/// like running out of memory). However, `Unstructured` does not guarantee
+/// anything beyond that: it makes not guarantee that it will yield bytes from
+/// the underlying data in any particular order.
+///
+/// You shouldn't generally need to use an `Unstructured` unless you are writing
+/// a custom `Arbitrary` implementation by hand, instead of deriving it. Mostly,
+/// you should just be passing it through to nested `Arbitrary::arbitrary`
+/// calls.
+///
+/// # Example
+///
+/// Imagine you were writing a color conversion crate. You might want to write
+/// fuzz tests that take a random RGB color and assert various properties, run
+/// functions and make sure nothing panics, etc.
+///
+/// Below is what translating the fuzzer's raw input into an `Unstructured` and
+/// using that to generate an arbitrary RGB color might look like:
+///
+/// ```
+/// # #[cfg(feature = "derive")] fn foo() {
+/// use arbitrary::{Arbitrary, Unstructured};
+///
+/// /// An RGB color.
+/// #[derive(Arbitrary)]
+/// pub struct Rgb {
+///     r: u8,
+///     g: u8,
+///     b: u8,
+/// }
+///
+/// // Get the raw bytes from the fuzzer.
+/// #   let get_input_from_fuzzer = || &[];
+/// let raw_data: &[u8] = get_input_from_fuzzer();
+///
+/// // Wrap it in an `Unstructured`.
+/// let mut unstructured = Unstructured::new(raw_data);
+///
+/// // Generate an `Rgb` color and run our checks.
+/// if let Ok(rgb) = Rgb::arbitrary(&mut unstructured) {
+/// #   let run_my_color_conversion_checks = |_| {};
+///     run_my_color_conversion_checks(rgb);
+/// }
+/// # }
+/// ```
+pub struct Unstructured<'a> {
+    data: &'a [u8],
+}
+
+impl<'a> Unstructured<'a> {
+    /// Create a new `Unstructured` from the given raw data.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use arbitrary::Unstructured;
+    ///
+    /// let u = Unstructured::new(&[1, 2, 3, 4]);
+    /// ```
+    pub fn new(data: &'a [u8]) -> Self {
+        Unstructured { data }
+    }
+
+    /// Get the number of remaining bytes of underlying data that are still
+    /// available.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use arbitrary::{Arbitrary, Unstructured};
+    ///
+    /// let mut u = Unstructured::new(&[1, 2, 3]);
+    ///
+    /// // Initially have three bytes of data.
+    /// assert_eq!(u.len(), 3);
+    ///
+    /// // Generating a `bool` consumes one byte from the underlying data, so
+    /// // we are left with two bytes afterwards.
+    /// let _ = bool::arbitrary(&mut u);
+    /// assert_eq!(u.len(), 2);
+    /// ```
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.data.len()
+    }
+
+    /// Is the underlying unstructured data exhausted?
+    ///
+    /// `unstructured.is_empty()` is the same as `unstructured.len() == 0`.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use arbitrary::{Arbitrary, Unstructured};
+    ///
+    /// let mut u = Unstructured::new(&[1, 2, 3, 4]);
+    ///
+    /// // Initially, we are not empty.
+    /// assert!(!u.is_empty());
+    ///
+    /// // Generating a `u32` consumes all four bytes of the underlying data, so
+    /// // we become empty afterwards.
+    /// let _ = u32::arbitrary(&mut u);
+    /// assert!(u.is_empty());
+    /// ```
+    #[inline]
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    /// Generate an arbitrary instance of `A`.
+    ///
+    /// This is simply a helper method that is equivalent to `<A as
+    /// Arbitrary>::arbitrary(self)`. This helper is a little bit more concise,
+    /// and can be used in situations where Rust's type inference will figure
+    /// out what `A` should be.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// # #[cfg(feature="derive")] fn foo() -> arbitrary::Result<()> {
+    /// use arbitrary::{Arbitrary, Unstructured};
+    ///
+    /// #[derive(Arbitrary)]
+    /// struct MyType {
+    ///     // ...
+    /// }
+    ///
+    /// fn do_stuff(value: MyType) {
+    /// #   let _ = value;
+    ///     // ...
+    /// }
+    ///
+    /// let mut u = Unstructured::new(&[1, 2, 3, 4]);
+    ///
+    /// // Rust's type inference can figure out that `value` should be of type
+    /// // `MyType` here:
+    /// let value = u.arbitrary()?;
+    /// do_stuff(value);
+    /// # Ok(()) }
+    /// ```
+    pub fn arbitrary<A>(&mut self) -> Result<A>
+    where
+        A: Arbitrary,
+    {
+        <A as Arbitrary>::arbitrary(self)
+    }
+
+    /// Get the number of elements to insert when building up a collection of
+    /// arbitrary `ElementType`s.
+    ///
+    /// This uses the [`<ElementType as
+    /// Arbitrary>::size_hint`][crate::Arbitrary::size_hint] method to smartly
+    /// choose a length such that we most likely have enough underlying bytes to
+    /// construct that many arbitrary `ElementType`s.
+    ///
+    /// This should only be called within an `Arbitrary` implementation.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use arbitrary::{Arbitrary, Result, Unstructured};
+    /// # pub struct MyCollection<T> { _t: std::marker::PhantomData<T> }
+    /// # impl<T> MyCollection<T> {
+    /// #     pub fn with_capacity(capacity: usize) -> Self { MyCollection { _t: std::marker::PhantomData } }
+    /// #     pub fn insert(&mut self, element: T) {}
+    /// # }
+    ///
+    /// impl<T> Arbitrary for MyCollection<T>
+    /// where
+    ///     T: Arbitrary,
+    /// {
+    ///     fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+    ///         // Get the number of `T`s we should insert into our collection.
+    ///         let len = u.arbitrary_len::<T>()?;
+    ///
+    ///         // And then create a collection of that length!
+    ///         let mut my_collection = MyCollection::with_capacity(len);
+    ///         for _ in 0..len {
+    ///             let element = T::arbitrary(u)?;
+    ///             my_collection.insert(element);
+    ///         }
+    ///
+    ///         Ok(my_collection)
+    ///     }
+    /// }
+    /// ```
+    pub fn arbitrary_len<ElementType>(&mut self) -> Result<usize>
+    where
+        ElementType: Arbitrary,
+    {
+        let byte_size = self.arbitrary_byte_size()?;
+        let (lower, upper) = <ElementType as Arbitrary>::size_hint(0);
+        let elem_size = upper.unwrap_or_else(|| lower * 2);
+        let elem_size = std::cmp::max(1, elem_size);
+        Ok(byte_size / elem_size)
+    }
+
+    fn arbitrary_byte_size(&mut self) -> Result<usize> {
+        if self.data.len() == 0 {
+            Ok(0)
+        } else if self.data.len() == 1 {
+            self.data = &[];
+            Ok(0)
+        } else {
+            // Take lengths from the end of the data, since the `libFuzzer` folks
+            // found that this lets fuzzers more efficiently explore the input
+            // space.
+            //
+            // 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
+            let len = if self.data.len() <= std::u8::MAX as usize + 1 {
+                let bytes = 1;
+                let max_size = self.data.len() - bytes;
+                let (rest, for_size) = self.data.split_at(max_size);
+                self.data = rest;
+                Self::int_in_range_impl(0..=max_size as u8, for_size.iter().copied())?.0 as usize
+            } else if self.data.len() <= std::u16::MAX as usize + 1 {
+                let bytes = 2;
+                let max_size = self.data.len() - bytes;
+                let (rest, for_size) = self.data.split_at(max_size);
+                self.data = rest;
+                Self::int_in_range_impl(0..=max_size as u16, for_size.iter().copied())?.0 as usize
+            } else if self.data.len() <= std::u32::MAX as usize + 1 {
+                let bytes = 4;
+                let max_size = self.data.len() - bytes;
+                let (rest, for_size) = self.data.split_at(max_size);
+                self.data = rest;
+                Self::int_in_range_impl(0..=max_size as u32, for_size.iter().copied())?.0 as usize
+            } else {
+                let bytes = 8;
+                let max_size = self.data.len() - bytes;
+                let (rest, for_size) = self.data.split_at(max_size);
+                self.data = rest;
+                Self::int_in_range_impl(0..=max_size as u64, for_size.iter().copied())?.0 as usize
+            };
+
+            Ok(len)
+        }
+    }
+
+    /// Generate an integer within the given range.
+    ///
+    /// Do not use this to generate the size of a collection. Use
+    /// `arbitrary_len` instead.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `range.start >= range.end`. That is, the given range must be
+    /// non-empty.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use arbitrary::{Arbitrary, Unstructured};
+    ///
+    /// let mut u = Unstructured::new(&[1, 2, 3, 4]);
+    ///
+    /// let x: i32 = u.int_in_range(-5_000..=-1_000)
+    ///     .expect("constructed `u` with enough bytes to generate an `i32`");
+    ///
+    /// assert!(-5_000 <= x);
+    /// assert!(x <= -1_000);
+    /// ```
+    pub fn int_in_range<T>(&mut self, range: ops::RangeInclusive<T>) -> Result<T>
+    where
+        T: Int,
+    {
+        let (result, bytes_consumed) = Self::int_in_range_impl(range, self.data.iter().cloned())?;
+        self.data = &self.data[bytes_consumed..];
+        Ok(result)
+    }
+
+    fn int_in_range_impl<T>(
+        range: ops::RangeInclusive<T>,
+        mut bytes: impl Iterator<Item = u8>,
+    ) -> Result<(T, usize)>
+    where
+        T: Int,
+    {
+        let start = range.start();
+        let end = range.end();
+        assert!(
+            start <= end,
+            "`arbitrary::Unstructured::int_in_range` requires a non-empty range"
+        );
+
+        let range: T::Widest = end.as_widest() - start.as_widest();
+        let mut result = T::Widest::ZERO;
+        let mut offset: usize = 0;
+
+        while offset < mem::size_of::<T>()
+            && (range >> T::Widest::from_usize(offset)) > T::Widest::ZERO
+        {
+            let byte = bytes.next().ok_or(Error::NotEnoughData)?;
+            result = (result << 8) | T::Widest::from_u8(byte);
+            offset += 1;
+        }
+
+        // Avoid division by zero.
+        if let Some(range) = range.checked_add(T::Widest::ONE) {
+            result = result % range;
+        }
+
+        Ok((
+            T::from_widest(start.as_widest().wrapping_add(result)),
+            offset,
+        ))
+    }
+
+    /// Choose one of the given choices.
+    ///
+    /// This should only be used inside of `Arbitrary` implementations.
+    ///
+    /// Returns an error if there is not enough underlying data to make a
+    /// choice.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `choices` is empty.
+    ///
+    /// # 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'];
+    /// if let Ok(ch) = u.choose(&choices) {
+    ///     println!("chose {}", ch);
+    /// }
+    /// ```
+    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"
+        );
+        let idx = self.int_in_range(0..=choices.len() - 1)?;
+        Ok(&choices[idx])
+    }
+
+    /// Fill a `buffer` with bytes from the underlying raw data.
+    ///
+    /// This should only be called within an `Arbitrary` implementation. This is
+    /// a very low-level operation. You should generally prefer calling nested
+    /// `Arbitrary` implementations like `<Vec<u8>>::arbitrary` and
+    /// `String::arbitrary` over using this method directly.
+    ///
+    /// If this `Unstructured` does not have enough data to fill the whole
+    /// `buffer`, an error is returned.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use arbitrary::Unstructured;
+    ///
+    /// let mut u = Unstructured::new(&[1, 2, 3, 4]);
+    ///
+    /// let mut buf = [0; 2];
+    /// assert!(u.fill_buffer(&mut buf).is_ok());
+    /// assert!(u.fill_buffer(&mut buf).is_ok());
+    /// ```
+    pub fn fill_buffer(&mut self, buffer: &mut [u8]) -> Result<()> {
+        let n = std::cmp::min(buffer.len(), self.data.len());
+        for i in 0..n {
+            buffer[i] = self.data[i];
+        }
+        for i in self.data.len()..buffer.len() {
+            buffer[i] = 0;
+        }
+        self.data = &self.data[n..];
+        Ok(())
+    }
+
+    /// Provide `size` bytes from the underlying raw data.
+    ///
+    /// This should only be called within an `Arbitrary` implementation. This is
+    /// a very low-level operation. You should generally prefer calling nested
+    /// `Arbitrary` implementations like `<Vec<u8>>::arbitrary` and
+    /// `String::arbitrary` over using this method directly.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use arbitrary::Unstructured;
+    ///
+    /// 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]);
+    /// ```
+    pub fn get_bytes(&mut self, size: usize) -> Result<&'a [u8]> {
+        if self.data.len() < size {
+            return Err(Error::NotEnoughData);
+        }
+
+        let (for_buf, rest) = self.data.split_at(size);
+        self.data = rest;
+        Ok(for_buf)
+    }
+
+    /// Peek at `size` number of bytes of the underlying raw input.
+    ///
+    /// Does not consume the bytes, only peeks at them.
+    ///
+    /// Returns `None` if there are not `size` bytes left in the underlying raw
+    /// input.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use arbitrary::Unstructured;
+    ///
+    /// let u = Unstructured::new(&[1, 2, 3]);
+    ///
+    /// assert_eq!(u.peek_bytes(0).unwrap(), []);
+    /// assert_eq!(u.peek_bytes(1).unwrap(), [1]);
+    /// assert_eq!(u.peek_bytes(2).unwrap(), [1, 2]);
+    /// assert_eq!(u.peek_bytes(3).unwrap(), [1, 2, 3]);
+    ///
+    /// assert!(u.peek_bytes(4).is_none());
+    /// ```
+    pub fn peek_bytes(&self, size: usize) -> Option<&'a [u8]> {
+        self.data.get(..size)
+    }
+
+    /// Consume all of the rest of the remaining underlying bytes.
+    ///
+    /// Returns a slice of all the remaining, unconsumed bytes.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use arbitrary::Unstructured;
+    ///
+    /// let mut u = Unstructured::new(&[1, 2, 3]);
+    ///
+    /// let mut remaining = u.take_rest();
+    ///
+    /// assert_eq!(remaining, [1, 2, 3]);
+    /// ```
+    pub fn take_rest(mut self) -> &'a [u8] {
+        mem::replace(&mut self.data, &[])
+    }
+
+    /// Provide an iterator over elements for constructing a collection
+    ///
+    /// 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>(
+        &'b mut self,
+    ) -> Result<ArbitraryIter<'a, 'b, ElementType>> {
+        Ok(ArbitraryIter {
+            u: &mut *self,
+            _marker: PhantomData,
+        })
+    }
+
+    /// Provide an iterator over elements for constructing a collection from
+    /// all the remaining bytes.
+    ///
+    /// 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>(
+        self,
+    ) -> Result<ArbitraryTakeRestIter<'a, ElementType>> {
+        let (lower, upper) = ElementType::size_hint(0);
+
+        let elem_size = upper.unwrap_or(lower * 2);
+        let elem_size = std::cmp::max(1, elem_size);
+        let size = self.len() / elem_size;
+        Ok(ArbitraryTakeRestIter {
+            size,
+            u: Some(self),
+            _marker: PhantomData,
+        })
+    }
+}
+
+/// Utility iterator produced by [`Unstructured::arbitrary_iter`]
+pub struct ArbitraryIter<'a, 'b, ElementType> {
+    u: &'b mut Unstructured<'a>,
+    _marker: PhantomData<ElementType>,
+}
+
+impl<'a, 'b, ElementType: Arbitrary> 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);
+        if keep_going {
+            Some(Arbitrary::arbitrary(self.u))
+        } else {
+            None
+        }
+    }
+}
+
+/// Utility iterator produced by [`Unstructured::arbitrary_take_rest_iter`]
+pub struct ArbitraryTakeRestIter<'a, ElementType> {
+    u: Option<Unstructured<'a>>,
+    size: usize,
+    _marker: PhantomData<ElementType>,
+}
+
+impl<'a, ElementType: Arbitrary> Iterator for ArbitraryTakeRestIter<'a, ElementType> {
+    type Item = Result<ElementType>;
+    fn next(&mut self) -> Option<Result<ElementType>> {
+        if let Some(mut u) = self.u.take() {
+            if self.size == 1 {
+                Some(Arbitrary::arbitrary_take_rest(u))
+            } else if self.size == 0 {
+                None
+            } else {
+                self.size -= 1;
+                let ret = Arbitrary::arbitrary(&mut u);
+                self.u = Some(u);
+                Some(ret)
+            }
+        } else {
+            None
+        }
+    }
+}
+
+/// A trait that is implemented for all of the primitive integers:
+///
+/// * `u8`
+/// * `u16`
+/// * `u32`
+/// * `u64`
+/// * `u128`
+/// * `usize`
+/// * `i8`
+/// * `i16`
+/// * `i32`
+/// * `i64`
+/// * `i128`
+/// * `isize`
+///
+/// Don't implement this trait yourself.
+pub trait Int:
+    Copy
+    + PartialOrd
+    + Ord
+    + ops::Sub<Self, Output = Self>
+    + ops::Rem<Self, Output = Self>
+    + ops::Shr<Self, Output = Self>
+    + ops::Shl<usize, Output = Self>
+    + ops::BitOr<Self, Output = Self>
+{
+    #[doc(hidden)]
+    type Widest: Int;
+
+    #[doc(hidden)]
+    const ZERO: Self;
+
+    #[doc(hidden)]
+    const ONE: Self;
+
+    #[doc(hidden)]
+    fn as_widest(self) -> Self::Widest;
+
+    #[doc(hidden)]
+    fn from_widest(w: Self::Widest) -> Self;
+
+    #[doc(hidden)]
+    fn from_u8(b: u8) -> Self;
+
+    #[doc(hidden)]
+    fn from_usize(u: usize) -> Self;
+
+    #[doc(hidden)]
+    fn checked_add(self, rhs: Self) -> Option<Self>;
+
+    #[doc(hidden)]
+    fn wrapping_add(self, rhs: Self) -> Self;
+}
+
+macro_rules! impl_int {
+    ( $( $ty:ty : $widest:ty ; )* ) => {
+        $(
+            impl Int for $ty {
+                type Widest = $widest;
+
+                const ZERO: Self = 0;
+
+                const ONE: Self = 1;
+
+                fn as_widest(self) -> Self::Widest {
+                    self as $widest
+                }
+
+                fn from_widest(w: Self::Widest) -> Self {
+                    let x = <$ty>::max_value().as_widest();
+                    (w % x) as Self
+                }
+
+                fn from_u8(b: u8) -> Self {
+                    b as Self
+                }
+
+                fn from_usize(u: usize) -> Self {
+                    u as Self
+                }
+
+                fn checked_add(self, rhs: Self) -> Option<Self> {
+                    <$ty>::checked_add(self, rhs)
+                }
+
+                fn wrapping_add(self, rhs: Self) -> Self {
+                    <$ty>::wrapping_add(self, rhs)
+                }
+            }
+        )*
+    }
+}
+
+impl_int! {
+    u8: u128;
+    u16: u128;
+    u32: u128;
+    u64: u128;
+    u128: u128;
+    usize: u128;
+    i8: i128;
+    i16: i128;
+    i32: i128;
+    i64: i128;
+    i128: i128;
+    isize: i128;
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_byte_size() {
+        let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 6]);
+        // Should take one byte off the end
+        assert_eq!(u.arbitrary_byte_size().unwrap(), 6);
+        assert_eq!(u.len(), 9);
+        let mut v = vec![];
+        v.resize(260, 0);
+        v.push(1);
+        v.push(4);
+        let mut u = Unstructured::new(&v);
+        // Should read two bytes off the end
+        assert_eq!(u.arbitrary_byte_size().unwrap(), 0x104);
+        assert_eq!(u.len(), 260);
+    }
+
+    #[test]
+    fn int_in_range_of_one() {
+        let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 6]);
+        let x = u.int_in_range(0..=0).unwrap();
+        assert_eq!(x, 0);
+        let choice = *u.choose(&[42]).unwrap();
+        assert_eq!(choice, 42)
+    }
+}
diff --git a/tests/derive.rs b/tests/derive.rs
new file mode 100644
index 0000000..7f1e85e
--- /dev/null
+++ b/tests/derive.rs
@@ -0,0 +1,186 @@
+#![cfg(feature = "derive")]
+
+use arbitrary::*;
+
+fn arbitrary_from<T: Arbitrary>(input: &[u8]) -> T {
+    let mut buf = Unstructured::new(input);
+    T::arbitrary(&mut buf).expect("can create arbitrary instance OK")
+}
+
+#[derive(Copy, Clone, Debug, Eq, PartialEq, Arbitrary)]
+pub struct Rgb {
+    pub r: u8,
+    pub g: u8,
+    pub b: u8,
+}
+
+#[test]
+fn struct_with_named_fields() {
+    let rgb: Rgb = arbitrary_from(&[4, 5, 6]);
+    assert_eq!(rgb.r, 4);
+    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));
+}
+
+#[derive(Copy, Clone, Debug, Arbitrary)]
+struct MyTupleStruct(u8, bool);
+
+#[test]
+fn tuple_struct() {
+    let s: MyTupleStruct = arbitrary_from(&[43, 42]);
+    assert_eq!(s.0, 43);
+    assert_eq!(s.1, false);
+
+    let s: MyTupleStruct = arbitrary_from(&[42, 43]);
+    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));
+}
+
+#[derive(Clone, Debug, Arbitrary)]
+struct EndingInVec(u8, bool, u32, Vec<u16>);
+#[derive(Clone, Debug, Arbitrary)]
+struct EndingInString(u8, bool, u32, String);
+
+#[test]
+fn test_take_rest() {
+    let bytes = [1, 1, 1, 2, 3, 4, 5, 6, 7, 8];
+    let s1 = EndingInVec::arbitrary_take_rest(Unstructured::new(&bytes)).unwrap();
+    let s2 = EndingInString::arbitrary_take_rest(Unstructured::new(&bytes)).unwrap();
+    assert_eq!(s1.0, 1);
+    assert_eq!(s2.0, 1);
+    assert_eq!(s1.1, true);
+    assert_eq!(s2.1, true);
+    assert_eq!(s1.2, 0x4030201);
+    assert_eq!(s2.2, 0x4030201);
+    assert_eq!(s1.3, vec![0x605, 0x807]);
+    assert_eq!(s2.3, "\x05\x06\x07\x08");
+}
+
+#[derive(Copy, Clone, Debug, Arbitrary)]
+enum MyEnum {
+    Unit,
+    Tuple(u8, u16),
+    Struct { a: u32, b: (bool, u64) },
+}
+
+#[test]
+fn derive_enum() {
+    let mut raw = vec![
+        // The choice of which enum variant takes 4 bytes.
+        1, 2, 3, 4,
+        // And then we need up to 13 bytes for creating `MyEnum::Struct`, the
+        // largest variant.
+        1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
+    ];
+
+    let mut saw_unit = false;
+    let mut saw_tuple = false;
+    let mut saw_struct = false;
+
+    for i in 0..=255 {
+        // Choose different variants each iteration.
+        for el in &mut raw[..4] {
+            *el = i;
+        }
+
+        let e: MyEnum = arbitrary_from(&raw);
+
+        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"),
+                    }
+                }
+            }
+        }
+    }
+
+    assert!(saw_unit);
+    assert!(saw_tuple);
+    assert!(saw_struct);
+
+    assert_eq!((4, Some(17)), <MyEnum as Arbitrary>::size_hint(0));
+}
+
+#[derive(Arbitrary, Debug)]
+enum RecursiveTree {
+    Leaf,
+    Node {
+        left: Box<RecursiveTree>,
+        right: Box<RecursiveTree>,
+    },
+}
+
+#[test]
+fn recursive() {
+    let raw = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
+    let _rec: RecursiveTree = arbitrary_from(&raw);
+
+    let (lower, upper) = <RecursiveTree as Arbitrary>::size_hint(0);
+    assert_eq!(lower, 4, "need a u32 for the discriminant at minimum");
+    assert!(
+        upper.is_none(),
+        "potentially infinitely recursive, so no upper bound"
+    );
+}
+
+#[derive(Arbitrary, Debug)]
+struct Generic<T> {
+    inner: T,
+}
+
+#[test]
+fn generics() {
+    let raw = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
+    let gen: Generic<bool> = arbitrary_from(&raw);
+    assert!(gen.inner);
+
+    let (lower, upper) = <Generic<u32> as Arbitrary>::size_hint(0);
+    assert_eq!(lower, 4);
+    assert_eq!(upper, Some(4));
+}
diff --git a/tests/path.rs b/tests/path.rs
new file mode 100644
index 0000000..15dbbe3
--- /dev/null
+++ b/tests/path.rs
@@ -0,0 +1,29 @@
+#![cfg(feature = "derive")]
+
+// Regression test for ensuring the derives work without Arbitrary being imported
+
+#[derive(arbitrary::Arbitrary, Clone, Debug)]
+pub struct Struct {
+    x: u8,
+    y: u8,
+}
+
+#[derive(arbitrary::Arbitrary, Clone, Debug)]
+pub struct Tuple(u8);
+
+#[derive(arbitrary::Arbitrary, Clone, Debug)]
+pub struct Unit(u8);
+
+#[derive(arbitrary::Arbitrary, Clone, Debug)]
+pub enum Enum {
+    X(u8),
+    Y(u8),
+}
+
+#[derive(arbitrary::Arbitrary, Clone, Debug)]
+struct EndingInVec(u8, bool, u32, Vec<u16>);
+
+#[derive(arbitrary::Arbitrary, Debug)]
+struct Generic<T> {
+    inner: T,
+}