Upgrade rust/crates/arbitrary to 1.1.2 am: a27b8c53c9

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

Change-Id: Ib60771acdcb56f6f4c9cb07263dcf0e873f912c5
Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>

11 files changed, 246 insertions, 58 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 508adbd..7b04689 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,6 +1,6 @@
 {
   "git": {
-    "sha1": "d0d238d880276fd617c38f7e4712bf40db58aad6"
+    "sha1": "34be5b6d3d3bb513358e80453984652c88e07b75"
   },
   "path_in_vcs": ""
 }
\ No newline at end of file
diff --git a/Android.bp b/Android.bp
index 83c7cf4..8c371a2 100644
--- a/Android.bp
+++ b/Android.bp
@@ -39,11 +39,10 @@ license {
 
 rust_test {
     name: "arbitrary_test_src_lib",
-    // has rustc warnings
     host_supported: true,
     crate_name: "arbitrary",
     cargo_env_compat: true,
-    cargo_pkg_version: "1.1.0",
+    cargo_pkg_version: "1.1.2",
     srcs: ["src/lib.rs"],
     test_suites: ["general-tests"],
     auto_gen_config: true,
@@ -60,11 +59,10 @@ rust_test {
 
 rust_test {
     name: "arbitrary_test_tests_derive",
-    // has rustc warnings
     host_supported: true,
     crate_name: "arbitrary",
     cargo_env_compat: true,
-    cargo_pkg_version: "1.1.0",
+    cargo_pkg_version: "1.1.2",
     srcs: ["tests/derive.rs"],
     test_suites: ["general-tests"],
     auto_gen_config: true,
@@ -84,11 +82,10 @@ rust_test {
 
 rust_library_rlib {
     name: "libarbitrary",
-    // has rustc warnings
     host_supported: true,
     crate_name: "arbitrary",
     cargo_env_compat: true,
-    cargo_pkg_version: "1.1.0",
+    cargo_pkg_version: "1.1.2",
     srcs: ["src/lib.rs"],
     edition: "2018",
     features: [
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 2a7c179..73e5142 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -28,6 +28,28 @@ Released YYYY-MM-DD.
 
 --------------------------------------------------------------------------------
 
+## Unreleased
+
+Released 2022-06-16.
+
+### Fixed
+
+* Fixed a warning inside `derive(Arbitrary)`-generated
+  code. [#110](https://github.com/rust-fuzz/arbitrary/pull/110)
+
+--------------------------------------------------------------------------------
+
+## 1.1.1
+
+Released 2022-06-14.
+
+### Fixed
+
+* Fixed a stack overflow when using `derive(Arbitrary)` with recursive types and
+  empty inputs. [#109](https://github.com/rust-fuzz/arbitrary/pull/109)
+
+--------------------------------------------------------------------------------
+
 ## 1.1.0
 
 Released 2022-02-09.
diff --git a/Cargo.toml b/Cargo.toml
index a42a90b..684e705 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -12,7 +12,7 @@
 [package]
 edition = "2018"
 name = "arbitrary"
-version = "1.1.0"
+version = "1.1.2"
 authors = [
     "The Rust-Fuzz Project Developers",
     "Nick Fitzgerald <fitzgen@gmail.com>",
@@ -42,7 +42,7 @@ path = "./tests/derive.rs"
 required-features = ["derive"]
 
 [dependencies.derive_arbitrary]
-version = "1.0.0"
+version = "1.1.2"
 optional = true
 
 [dev-dependencies]
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index df4e2a1..01af004 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,6 +1,6 @@
 [package]
 name = "arbitrary"
-version = "1.1.0" # Make sure this matches the derive crate version
+version = "1.1.2" # Make sure this matches the derive crate version
 authors = [
     "The Rust-Fuzz Project Developers",
     "Nick Fitzgerald <fitzgen@gmail.com>",
@@ -19,7 +19,7 @@ repository = "https://github.com/rust-fuzz/arbitrary/"
 documentation = "https://docs.rs/arbitrary/"
 
 [dependencies]
-derive_arbitrary = { version = "1.0.0", path = "./derive", optional = true }
+derive_arbitrary = { version = "1.1.2", path = "./derive", optional = true }
 
 [dev-dependencies]
 
diff --git a/METADATA b/METADATA
index 00cf505..e7cf6dc 100644
--- a/METADATA
+++ b/METADATA
@@ -7,13 +7,13 @@ third_party {
   }
   url {
     type: ARCHIVE
-    value: "https://static.crates.io/crates/arbitrary/arbitrary-1.1.0.crate"
+    value: "https://static.crates.io/crates/arbitrary/arbitrary-1.1.2.crate"
   }
-  version: "1.1.0"
+  version: "1.1.2"
   license_type: NOTICE
   last_upgrade_date {
     year: 2022
-    month: 3
-    day: 1
+    month: 6
+    day: 16
   }
 }
diff --git a/examples/derive_enum.rs b/examples/derive_enum.rs
index fbcc106..c4fc9c9 100644
--- a/examples/derive_enum.rs
+++ b/examples/derive_enum.rs
@@ -2,6 +2,10 @@
 //!
 //! Note that this requires enabling the "derive" cargo feature.
 
+// Various enums/fields that we are deriving `Arbitrary` for aren't actually
+// used except to show off the derive.
+#![allow(dead_code)]
+
 use arbitrary::{Arbitrary, Unstructured};
 
 #[derive(Arbitrary, Debug)]
diff --git a/src/lib.rs b/src/lib.rs
index 7b791ab..2de041d 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -202,6 +202,16 @@ pub trait Arbitrary<'a>: Sized {
     /// default with a better implementation. The
     /// [`size_hint`][crate::size_hint] module will help with this task.
     ///
+    /// ## Invariant
+    ///
+    /// It must be possible to construct every possible output using only inputs
+    /// of lengths bounded by these parameters. This applies to both
+    /// [`Arbitrary::arbitrary`] and [`Arbitrary::arbitrary_take_rest`].
+    ///
+    /// This is trivially true for `(0, None)`. To restrict this further, it must be proven
+    /// that all inputs that are now excluded produced redundant outputs which are still
+    /// possible to produce using the reduced input space.
+    ///
     /// ## The `depth` Parameter
     ///
     /// If you 100% know that the type you are implementing `Arbitrary` for is
@@ -672,8 +682,8 @@ impl<'a> Arbitrary<'a> for &'a [u8] {
     }
 
     #[inline]
-    fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        <usize as Arbitrary>::size_hint(depth)
+    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
+        (0, None)
     }
 }
 
@@ -687,8 +697,8 @@ impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Vec<A> {
     }
 
     #[inline]
-    fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
+    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
+        (0, None)
     }
 }
 
@@ -702,8 +712,8 @@ impl<'a, K: Arbitrary<'a> + Ord, V: Arbitrary<'a>> Arbitrary<'a> for BTreeMap<K,
     }
 
     #[inline]
-    fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
+    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
+        (0, None)
     }
 }
 
@@ -717,8 +727,8 @@ impl<'a, A: Arbitrary<'a> + Ord> Arbitrary<'a> for BTreeSet<A> {
     }
 
     #[inline]
-    fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
+    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
+        (0, None)
     }
 }
 
@@ -732,8 +742,8 @@ impl<'a, A: Arbitrary<'a> + Ord> Arbitrary<'a> for BinaryHeap<A> {
     }
 
     #[inline]
-    fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
+    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
+        (0, None)
     }
 }
 
@@ -749,8 +759,8 @@ impl<'a, K: Arbitrary<'a> + Eq + ::std::hash::Hash, V: Arbitrary<'a>, S: BuildHa
     }
 
     #[inline]
-    fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
+    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
+        (0, None)
     }
 }
 
@@ -766,8 +776,8 @@ impl<'a, A: Arbitrary<'a> + Eq + ::std::hash::Hash, S: BuildHasher + Default> Ar
     }
 
     #[inline]
-    fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
+    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
+        (0, None)
     }
 }
 
@@ -781,8 +791,8 @@ impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for LinkedList<A> {
     }
 
     #[inline]
-    fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
+    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
+        (0, None)
     }
 }
 
@@ -796,8 +806,8 @@ impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for VecDeque<A> {
     }
 
     #[inline]
-    fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
+    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
+        (0, None)
     }
 }
 
@@ -846,8 +856,8 @@ impl<'a> Arbitrary<'a> for &'a str {
     }
 
     #[inline]
-    fn size_hint(depth: usize) -> (usize, Option<usize>) {
-        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
+    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
+        (0, None)
     }
 }
 
@@ -1104,6 +1114,56 @@ impl<'a> Arbitrary<'a> for Ipv6Addr {
 mod test {
     use super::*;
 
+    /// Generates an arbitrary `T`, and checks that the result is consistent with the
+    /// `size_hint()` reported by `T`.
+    fn checked_arbitrary<'a, T: Arbitrary<'a>>(u: &mut Unstructured<'a>) -> Result<T> {
+        let (min, max) = T::size_hint(0);
+
+        let len_before = u.len();
+        let result = T::arbitrary(u);
+
+        let consumed = len_before - u.len();
+
+        if let Some(max) = max {
+            assert!(
+                consumed <= max,
+                "incorrect maximum size: indicated {}, actually consumed {}",
+                max,
+                consumed
+            );
+        }
+
+        if result.is_ok() {
+            assert!(
+                consumed >= min,
+                "incorrect minimum size: indicated {}, actually consumed {}",
+                min,
+                consumed
+            );
+        }
+
+        result
+    }
+
+    /// Like `checked_arbitrary()`, but calls `arbitrary_take_rest()` instead of `arbitrary()`.
+    fn checked_arbitrary_take_rest<'a, T: Arbitrary<'a>>(u: Unstructured<'a>) -> Result<T> {
+        let (min, _) = T::size_hint(0);
+
+        let len_before = u.len();
+        let result = T::arbitrary_take_rest(u);
+
+        if result.is_ok() {
+            assert!(
+                len_before >= min,
+                "incorrect minimum size: indicated {}, worked with {}",
+                min,
+                len_before
+            );
+        }
+
+        result
+    }
+
     #[test]
     fn finite_buffer_fill_buffer() {
         let x = [1, 2, 3, 4];
@@ -1122,7 +1182,7 @@ mod test {
         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();
+        let actual = checked_arbitrary::<i32>(&mut buf).unwrap();
         assert_eq!(expected, actual);
     }
 
@@ -1131,7 +1191,7 @@ mod test {
         let x = [1, 2, 3, 4, 4];
         let mut buf = Unstructured::new(&x);
         let expected = &[1, 2, 3, 4];
-        let actual = <&[u8] as Arbitrary>::arbitrary(&mut buf).unwrap();
+        let actual = checked_arbitrary::<&[u8]>(&mut buf).unwrap();
         assert_eq!(expected, actual);
     }
 
@@ -1140,26 +1200,30 @@ mod test {
         let x = [1, 2, 3, 4];
         let buf = Unstructured::new(&x);
         let expected = &[1, 2, 3, 4];
-        let actual = <&[u8] as Arbitrary>::arbitrary_take_rest(buf).unwrap();
+        let actual = checked_arbitrary_take_rest::<&[u8]>(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,
+            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, 12,
         ];
         assert_eq!(
-            Vec::<u8>::arbitrary(&mut Unstructured::new(&x)).unwrap(),
+            checked_arbitrary::<&[u8]>(&mut Unstructured::new(&x)).unwrap(),
+            &[1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3]
+        );
+        assert_eq!(
+            checked_arbitrary::<Vec<u8>>(&mut Unstructured::new(&x)).unwrap(),
             &[2, 4, 6, 8, 1]
         );
         assert_eq!(
-            Vec::<u32>::arbitrary(&mut Unstructured::new(&x)).unwrap(),
+            checked_arbitrary::<Vec<u32>>(&mut Unstructured::new(&x)).unwrap(),
             &[84148994]
         );
         assert_eq!(
-            String::arbitrary(&mut Unstructured::new(&x)).unwrap(),
-            "\x01\x02\x03\x04\x05\x06\x07\x08"
+            checked_arbitrary::<String>(&mut Unstructured::new(&x)).unwrap(),
+            "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x01\x02\x03"
         );
     }
 
@@ -1167,17 +1231,30 @@ mod test {
     fn arbitrary_take_rest() {
         let x = [1, 2, 3, 4];
         assert_eq!(
-            Vec::<u8>::arbitrary_take_rest(Unstructured::new(&x)).unwrap(),
+            checked_arbitrary_take_rest::<&[u8]>(Unstructured::new(&x)).unwrap(),
+            &[1, 2, 3, 4]
+        );
+        assert_eq!(
+            checked_arbitrary_take_rest::<Vec<u8>>(Unstructured::new(&x)).unwrap(),
             &[1, 2, 3, 4]
         );
         assert_eq!(
-            Vec::<u32>::arbitrary_take_rest(Unstructured::new(&x)).unwrap(),
+            checked_arbitrary_take_rest::<Vec<u32>>(Unstructured::new(&x)).unwrap(),
             &[0x4030201]
         );
         assert_eq!(
-            String::arbitrary_take_rest(Unstructured::new(&x)).unwrap(),
+            checked_arbitrary_take_rest::<String>(Unstructured::new(&x)).unwrap(),
             "\x01\x02\x03\x04"
         );
+
+        assert_eq!(
+            checked_arbitrary_take_rest::<&[u8]>(Unstructured::new(&[])).unwrap(),
+            &[]
+        );
+        assert_eq!(
+            checked_arbitrary_take_rest::<Vec<u8>>(Unstructured::new(&[])).unwrap(),
+            &[]
+        );
     }
 
     #[test]
@@ -1186,9 +1263,6 @@ mod test {
             (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)
-        );
+        assert_eq!((1, None), <(u8, Vec<u8>) as Arbitrary>::size_hint(0));
     }
 }
diff --git a/src/unstructured.rs b/src/unstructured.rs
index ff3e1f3..07ba932 100644
--- a/src/unstructured.rs
+++ b/src/unstructured.rs
@@ -236,19 +236,20 @@ impl<'a> Unstructured<'a> {
 
             // 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 {
+            // Note: We cast to u64 so we don't overflow when checking std::u32::MAX + 4 on 32-bit archs
+            let len = if self.data.len() as u64 <= std::u8::MAX as u64 + 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 {
+            } else if self.data.len() as u64 <= std::u16::MAX as u64 + 2 {
                 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 {
+            } else if self.data.len() as u64 <= std::u32::MAX as u64 + 4 {
                 let bytes = 4;
                 let max_size = self.data.len() - bytes;
                 let (rest, for_size) = self.data.split_at(max_size);
@@ -376,11 +377,53 @@ impl<'a> Unstructured<'a> {
     /// assert!(result.is_err());
     /// ```
     pub fn choose<'b, T>(&mut self, choices: &'b [T]) -> Result<&'b T> {
-        if choices.is_empty() {
+        let idx = self.choose_index(choices.len())?;
+        Ok(&choices[idx])
+    }
+
+    /// Choose a value in `0..len`.
+    ///
+    /// Returns an error if the `len` is zero.
+    ///
+    /// # Examples
+    ///
+    /// Using Fisher–Yates shuffle shuffle to gerate an arbitrary permutation.
+    ///
+    /// [Fisher–Yates shuffle]: https://en.wikipedia.org/wiki/Fisher–Yates_shuffle
+    ///
+    /// ```
+    /// use arbitrary::Unstructured;
+    ///
+    /// let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]);
+    /// let mut permutation = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
+    /// let mut to_permute = &mut permutation[..];
+    /// while to_permute.len() > 1 {
+    ///     let idx = u.choose_index(to_permute.len()).unwrap();
+    ///     to_permute.swap(0, idx);
+    ///     to_permute = &mut to_permute[1..];
+    /// }
+    ///
+    /// println!("permutation: {:?}", permutation);
+    /// ```
+    ///
+    /// An error is returned if the length is zero:
+    ///
+    /// ```
+    /// use arbitrary::Unstructured;
+    ///
+    /// let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]);
+    /// let array: [i32; 0] = [];
+    ///
+    /// let result = u.choose_index(array.len());
+    ///
+    /// assert!(result.is_err());
+    /// ```
+    pub fn choose_index(&mut self, len: usize) -> Result<usize> {
+        if len == 0 {
             return Err(Error::EmptyChoose);
         }
-        let idx = self.int_in_range(0..=choices.len() - 1)?;
-        Ok(&choices[idx])
+        let idx = self.int_in_range(0..=len - 1)?;
+        Ok(idx)
     }
 
     /// Generate a boolean according to the given ratio.
diff --git a/tests/derive.rs b/tests/derive.rs
index adf1188..2d666f6 100755
--- a/tests/derive.rs
+++ b/tests/derive.rs
@@ -1,4 +1,7 @@
 #![cfg(feature = "derive")]
+// Various structs/fields that we are deriving `Arbitrary` for aren't actually
+// used except to exercise the derive.
+#![allow(dead_code)]
 
 use arbitrary::*;
 
@@ -164,7 +167,7 @@ fn one_lifetime() {
     assert_eq!("abc", lifetime.alpha);
 
     let (lower, upper) = <OneLifetime as Arbitrary>::size_hint(0);
-    assert_eq!(lower, std::mem::size_of::<usize>());
+    assert_eq!(lower, 0);
     assert_eq!(upper, None);
 }
 
@@ -183,6 +186,48 @@ fn two_lifetimes() {
     assert_eq!("def", lifetime.beta);
 
     let (lower, upper) = <TwoLifetimes as Arbitrary>::size_hint(0);
-    assert_eq!(lower, std::mem::size_of::<usize>() * 2);
+    assert_eq!(lower, 0);
     assert_eq!(upper, None);
 }
+
+#[test]
+fn recursive_and_empty_input() {
+    // None of the following derives should result in a stack overflow. See
+    // https://github.com/rust-fuzz/arbitrary/issues/107 for details.
+
+    #[derive(Debug, Arbitrary)]
+    enum Nat {
+        Succ(Box<Nat>),
+        Zero,
+    }
+
+    let _ = Nat::arbitrary(&mut Unstructured::new(&[]));
+
+    #[derive(Debug, Arbitrary)]
+    enum Nat2 {
+        Zero,
+        Succ(Box<Nat2>),
+    }
+
+    let _ = Nat2::arbitrary(&mut Unstructured::new(&[]));
+
+    #[derive(Debug, Arbitrary)]
+    struct Nat3 {
+        f: Option<Box<Nat3>>,
+    }
+
+    let _ = Nat3::arbitrary(&mut Unstructured::new(&[]));
+
+    #[derive(Debug, Arbitrary)]
+    struct Nat4(Option<Box<Nat4>>);
+
+    let _ = Nat4::arbitrary(&mut Unstructured::new(&[]));
+
+    #[derive(Debug, Arbitrary)]
+    enum Nat5 {
+        Zero,
+        Succ { f: Box<Nat5> },
+    }
+
+    let _ = Nat5::arbitrary(&mut Unstructured::new(&[]));
+}
diff --git a/tests/path.rs b/tests/path.rs
index 15dbbe3..c42ec0a 100644
--- a/tests/path.rs
+++ b/tests/path.rs
@@ -1,4 +1,7 @@
 #![cfg(feature = "derive")]
+// Various structs/fields that we are deriving `Arbitrary` for aren't actually
+// used except to show off the derive.
+#![allow(dead_code)]
 
 // Regression test for ensuring the derives work without Arbitrary being imported