Upgrade rust/crates/smallvec to 1.6.1

Test: make
Change-Id: I93787933923d91dbeaf9e9ebe2b9cdca44e07528

7 files changed, 108 insertions, 71 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 76701ab..9ef75e5 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,5 @@
 {
   "git": {
-    "sha1": "9ae70763eca410f80001cd100e42e846213acd61"
+    "sha1": "4e53e072808815ed6b847c77193c568ee076c29d"
   }
 }
diff --git a/.travis.yml b/.travis.yml
index 7542cda..32fba28 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -19,26 +19,19 @@ matrix:
       env: DO_FUZZ=true
     - rust: stable
       env: DO_FUZZ=true
-script:
-  - |
-    if [[ "$TRAVIS_RUST_VERSION" == stable ]]
-    then
-      rustup component add rustfmt
-      cargo fmt --all -- --check
-    fi
-  - |
-    cargo build --verbose &&
-    cargo test --verbose &&
-    cargo test --verbose --features serde &&
-    ([ $TRAVIS_RUST_VERSION != nightly ] || cargo check --verbose --no-default-features) &&
-    ([ $TRAVIS_RUST_VERSION != nightly ] || cargo test --verbose --features union) &&
-    ([ $TRAVIS_RUST_VERSION != nightly ] || cargo test --verbose --all-features) &&
-    ([ $TRAVIS_RUST_VERSION != nightly ] || cargo bench --verbose bench) &&
-    ([ $TRAVIS_RUST_VERSION != nightly ] || bash ./scripts/run_miri.sh) &&
-    if [ "$DO_FUZZ" = true ]
-    then
-    (
-      cd fuzz
-      ./travis-fuzz.sh
-    )
-    fi
+script: |
+  cargo build --verbose &&
+  cargo test --verbose &&
+  cargo test --verbose --features serde &&
+  ([ $TRAVIS_RUST_VERSION != nightly ] || cargo check --verbose --no-default-features) &&
+  ([ $TRAVIS_RUST_VERSION != beta ] || cargo test --verbose --features union) &&
+  ([ $TRAVIS_RUST_VERSION != nightly ] || cargo test --verbose --all-features) &&
+  ([ $TRAVIS_RUST_VERSION != nightly ] || cargo bench --verbose bench) &&
+  ([ $TRAVIS_RUST_VERSION != nightly ] || bash ./scripts/run_miri.sh) &&
+  if [ "$DO_FUZZ" = true ]
+  then
+  (
+    cd fuzz
+    ./travis-fuzz.sh
+  )
+  fi
diff --git a/Cargo.toml b/Cargo.toml
index 5d565ab..1759894 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -13,7 +13,7 @@
 [package]
 edition = "2018"
 name = "smallvec"
-version = "1.4.2"
+version = "1.6.1"
 authors = ["The Servo Project Developers"]
 description = "'Small vector' optimization: store up to a small number of items on the stack"
 documentation = "https://docs.rs/smallvec/"
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index f163aff..b19b93e 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,6 +1,6 @@
 [package]
 name = "smallvec"
-version = "1.4.2"
+version = "1.6.1"
 edition = "2018"
 authors = ["The Servo Project Developers"]
 license = "MIT/Apache-2.0"
diff --git a/METADATA b/METADATA
index eeb89e8..3ff6a4b 100644
--- a/METADATA
+++ b/METADATA
@@ -7,13 +7,13 @@ third_party {
   }
   url {
     type: ARCHIVE
-    value: "https://static.crates.io/crates/smallvec/smallvec-1.4.2.crate"
+    value: "https://static.crates.io/crates/smallvec/smallvec-1.6.1.crate"
   }
-  version: "1.4.2"
+  version: "1.6.1"
   license_type: NOTICE
   last_upgrade_date {
-    year: 2020
-    month: 8
-    day: 11
+    year: 2021
+    month: 1
+    day: 8
   }
 }
diff --git a/src/lib.rs b/src/lib.rs
index 0f0f186..5e9de82 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -28,7 +28,7 @@
 //!
 //! ### `union`
 //!
-//! **This feature is unstable and requires a nightly build of the Rust toolchain.**
+//! **This feature requires Rust 1.49.**
 //!
 //! When the `union` feature is enabled `smallvec` will track its state (inline or spilled)
 //! without the use of an enum tag, reducing the size of the `smallvec` by one machine word.
@@ -37,7 +37,7 @@
 //! machine words.
 //!
 //! To use this feature add `features = ["union"]` in the `smallvec` section of Cargo.toml.
-//! Note that this feature requires a nightly compiler (for now).
+//! Note that this feature requires Rust 1.49.
 //!
 //! Tracking issue: [rust-lang/rust#55149](https://github.com/rust-lang/rust/issues/55149)
 //!
@@ -71,11 +71,9 @@
 //! Tracking issue: [rust-lang/rust#34761](https://github.com/rust-lang/rust/issues/34761)
 
 #![no_std]
-#![cfg_attr(feature = "union", feature(untagged_unions))]
 #![cfg_attr(feature = "specialization", allow(incomplete_features))]
 #![cfg_attr(feature = "specialization", feature(specialization))]
 #![cfg_attr(feature = "may_dangle", feature(dropck_eyepatch))]
-#![cfg_attr(feature = "const_generics", feature(min_const_generics))]
 #![deny(missing_docs)]
 
 #[doc(hidden)]
@@ -87,6 +85,7 @@ extern crate std;
 #[cfg(test)]
 mod tests;
 
+#[allow(deprecated)]
 use alloc::alloc::{Layout, LayoutErr};
 use alloc::boxed::Box;
 use alloc::{vec, vec::Vec};
@@ -233,6 +232,13 @@ pub enum CollectionAllocErr {
     },
 }
 
+impl fmt::Display for CollectionAllocErr {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "Allocation error: {:?}", self)
+    }
+}
+
+#[allow(deprecated)]
 impl From<LayoutErr> for CollectionAllocErr {
     fn from(_: LayoutErr) -> Self {
         CollectionAllocErr::CapacityOverflow
@@ -345,7 +351,7 @@ impl<'a, T: 'a + Array> Drop for Drain<'a, T> {
 
 #[cfg(feature = "union")]
 union SmallVecData<A: Array> {
-    inline: MaybeUninit<A>,
+    inline: core::mem::ManuallyDrop<MaybeUninit<A>>,
     heap: (*mut A::Item, usize),
 }
 
@@ -361,11 +367,13 @@ impl<A: Array> SmallVecData<A> {
     }
     #[inline]
     fn from_inline(inline: MaybeUninit<A>) -> SmallVecData<A> {
-        SmallVecData { inline }
+        SmallVecData {
+            inline: core::mem::ManuallyDrop::new(inline),
+        }
     }
     #[inline]
     unsafe fn into_inline(self) -> MaybeUninit<A> {
-        self.inline
+        core::mem::ManuallyDrop::into_inner(self.inline)
     }
     #[inline]
     unsafe fn heap(&self) -> (*mut A::Item, usize) {
@@ -747,13 +755,15 @@ impl<A: Array> SmallVec<A> {
     #[inline]
     pub fn push(&mut self, value: A::Item) {
         unsafe {
-            let (_, &mut len, cap) = self.triple_mut();
-            if len == cap {
+            let (mut ptr, mut len, cap) = self.triple_mut();
+            if *len == cap {
                 self.reserve(1);
+                let &mut (heap_ptr, ref mut heap_len) = self.data.heap_mut();
+                ptr = heap_ptr;
+                len = heap_len;
             }
-            let (ptr, len_ptr, _) = self.triple_mut();
-            *len_ptr = len + 1;
-            ptr::write(ptr.add(len), value);
+            ptr::write(ptr.add(*len), value);
+            *len += 1;
         }
     }
 
@@ -771,6 +781,25 @@ impl<A: Array> SmallVec<A> {
         }
     }
 
+    /// Moves all the elements of `other` into `self`, leaving `other` empty.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// # use smallvec::{SmallVec, smallvec};
+    /// let mut v0: SmallVec<[u8; 16]> = smallvec![1, 2, 3];
+    /// let mut v1: SmallVec<[u8; 32]> = smallvec![4, 5, 6];
+    /// v0.append(&mut v1);
+    /// assert_eq!(*v0, [1, 2, 3, 4, 5, 6]);
+    /// assert_eq!(*v1, []);
+    /// ```
+    pub fn append<B>(&mut self, other: &mut SmallVec<B>)
+    where
+        B: Array<Item = A::Item>,
+    {
+        self.extend(other.drain(..))
+    }
+
     /// Re-allocate to set the capacity to `max(new_cap, inline_size())`.
     ///
     /// Panics if `new_cap` is less than the vector's length
@@ -980,7 +1009,7 @@ impl<A: Array> SmallVec<A> {
     /// Insert multiple elements at position `index`, shifting all following elements toward the
     /// back.
     pub fn insert_many<I: IntoIterator<Item = A::Item>>(&mut self, index: usize, iterable: I) {
-        let iter = iterable.into_iter();
+        let mut iter = iterable.into_iter();
         if index == self.len() {
             return self.extend(iter);
         }
@@ -988,13 +1017,16 @@ impl<A: Array> SmallVec<A> {
         let (lower_size_bound, _) = iter.size_hint();
         assert!(lower_size_bound <= core::isize::MAX as usize); // Ensure offset is indexable
         assert!(index + lower_size_bound >= index); // Protect against overflow
-        self.reserve(lower_size_bound);
+
+        let mut num_added = 0;
+        let old_len = self.len();
+        assert!(index <= old_len);
 
         unsafe {
-            let old_len = self.len();
-            assert!(index <= old_len);
+            // Reserve space for `lower_size_bound` elements.
+            self.reserve(lower_size_bound);
             let start = self.as_mut_ptr();
-            let mut ptr = start.add(index);
+            let ptr = start.add(index);
 
             // Move the trailing elements.
             ptr::copy(ptr, ptr.add(lower_size_bound), old_len - index);
@@ -1007,42 +1039,39 @@ impl<A: Array> SmallVec<A> {
                 len: old_len + lower_size_bound,
             };
 
-            let mut num_added = 0;
-            for element in iter {
-                let mut cur = ptr.add(num_added);
-                if num_added >= lower_size_bound {
-                    // Iterator provided more elements than the hint.  Move trailing items again.
-                    self.reserve(1);
-                    let start = self.as_mut_ptr();
-                    ptr = start.add(index);
-                    cur = ptr.add(num_added);
-                    ptr::copy(cur, cur.add(1), old_len - index);
-
-                    guard.start = start;
-                    guard.len += 1;
-                    guard.skip.end += 1;
-                }
+            while num_added < lower_size_bound {
+                let element = match iter.next() {
+                    Some(x) => x,
+                    None => break,
+                };
+                let cur = ptr.add(num_added);
                 ptr::write(cur, element);
                 guard.skip.start += 1;
                 num_added += 1;
             }
-            mem::forget(guard);
 
             if num_added < lower_size_bound {
-                // Iterator provided fewer elements than the hint
+                // Iterator provided fewer elements than the hint. Move the tail backward.
                 ptr::copy(
                     ptr.add(lower_size_bound),
                     ptr.add(num_added),
                     old_len - index,
                 );
             }
-
+            // There are no more duplicate or uninitialized slots, so the guard is not needed.
             self.set_len(old_len + num_added);
+            mem::forget(guard);
+        }
+
+        // Insert any remaining elements one-by-one.
+        for element in iter {
+            self.insert(index + num_added, element);
+            num_added += 1;
         }
 
         struct DropOnPanic<T> {
             start: *mut T,
-            skip: Range<usize>,
+            skip: Range<usize>, // Space we copied-out-of, but haven't written-to yet.
             len: usize,
         }
 
@@ -1525,8 +1554,10 @@ where
     where
         B: SeqAccess<'de>,
     {
+        use serde::de::Error;
         let len = seq.size_hint().unwrap_or(0);
-        let mut values = SmallVec::with_capacity(len);
+        let mut values = SmallVec::new();
+        values.try_reserve(len).map_err(B::Error::custom)?;
 
         while let Some(value) = seq.next_element()? {
             values.push(value);
@@ -1928,9 +1959,9 @@ macro_rules! impl_array(
 
 #[cfg(not(feature = "const_generics"))]
 impl_array!(
-    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36, 0x40, 0x60, 0x80,
-    0x100, 0x200, 0x400, 0x600, 0x800, 0x1000, 0x2000, 0x4000, 0x6000, 0x8000, 0x10000, 0x20000,
-    0x40000, 0x60000, 0x80000, 0x10_0000
+    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
+    26, 27, 28, 29, 30, 31, 32, 36, 0x40, 0x60, 0x80, 0x100, 0x200, 0x400, 0x600, 0x800, 0x1000,
+    0x2000, 0x4000, 0x6000, 0x8000, 0x10000, 0x20000, 0x40000, 0x60000, 0x80000, 0x10_0000
 );
 
 /// Convenience trait for constructing a `SmallVec`
diff --git a/src/tests.rs b/src/tests.rs
index 0452ae8..19f6da8 100644
--- a/src/tests.rs
+++ b/src/tests.rs
@@ -905,3 +905,16 @@ fn empty_macro() {
 fn zero_size_items() {
     SmallVec::<[(); 0]>::new().push(());
 }
+
+#[test]
+fn test_insert_many_overflow() {
+    let mut v: SmallVec<[u8; 1]> = SmallVec::new();
+    v.push(123);
+
+    // Prepare an iterator with small lower bound
+    let iter = (0u8..5).filter(|n| n % 2 == 0);
+    assert_eq!(iter.size_hint().0, 0);
+
+    v.insert_many(0, iter);
+    assert_eq!(&*v, &[0, 2, 4, 123]);
+}