Merge "Upgrade rust/crates/smallvec to 1.4.2" am: 5237030d92 am: 2b62ce0785 am: c0ccb926b3 am: f575d2366e

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

Change-Id: Icecfed9463143a1010e08e8596ea54128fc8d2ce

9 files changed, 1003 insertions, 907 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 51909b5..76701ab 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,5 @@
 {
   "git": {
-    "sha1": "5513f4716bad73823a29f2484a359158fce576be"
+    "sha1": "9ae70763eca410f80001cd100e42e846213acd61"
   }
 }
diff --git a/.travis.yml b/.travis.yml
index 4454c72..7542cda 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -19,19 +19,26 @@ matrix:
       env: DO_FUZZ=true
     - rust: stable
       env: DO_FUZZ=true
-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 != 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:
+  - |
+    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
diff --git a/Android.bp b/Android.bp
index a7dee9a..4cf532b 100644
--- a/Android.bp
+++ b/Android.bp
@@ -4,6 +4,6 @@ rust_library {
     name: "libsmallvec",
     host_supported: true,
     crate_name: "smallvec",
-    srcs: ["lib.rs"],
+    srcs: ["src/lib.rs"],
     edition: "2018",
 }
diff --git a/Cargo.toml b/Cargo.toml
index d5c8b5c..5d565ab 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -13,8 +13,8 @@
 [package]
 edition = "2018"
 name = "smallvec"
-version = "1.4.1"
-authors = ["Simon Sapin <simon.sapin@exyr.org>"]
+version = "1.4.2"
+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/"
 readme = "README.md"
@@ -22,10 +22,6 @@ keywords = ["small", "vec", "vector", "stack", "no_std"]
 categories = ["data-structures"]
 license = "MIT/Apache-2.0"
 repository = "https://github.com/servo/rust-smallvec"
-
-[lib]
-name = "smallvec"
-path = "lib.rs"
 [dependencies.serde]
 version = "1"
 optional = true
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index 65d995a..f163aff 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,8 +1,8 @@
 [package]
 name = "smallvec"
-version = "1.4.1"
+version = "1.4.2"
 edition = "2018"
-authors = ["Simon Sapin <simon.sapin@exyr.org>"]
+authors = ["The Servo Project Developers"]
 license = "MIT/Apache-2.0"
 repository = "https://github.com/servo/rust-smallvec"
 description = "'Small vector' optimization: store up to a small number of items on the stack"
@@ -18,10 +18,6 @@ union = []
 specialization = []
 may_dangle = []
 
-[lib]
-name = "smallvec"
-path = "lib.rs"
-
 [dependencies]
 serde = { version = "1", optional = true, default-features = false }
 
diff --git a/METADATA b/METADATA
index 02051c5..2e5d655 100644
--- a/METADATA
+++ b/METADATA
@@ -9,11 +9,11 @@ third_party {
     type: ARCHIVE
     value: "https://static.crates.io/crates/smallvec/smallvec-1.4.1.crate"
   }
-  version: "1.4.1"
+  version: "1.4.2"
   license_type: NOTICE
   last_upgrade_date {
     year: 2020
-    month: 7
-    day: 30
+    month: 8
+    day: 11
   }
 }
diff --git a/lib.rs b/src/lib.rs
index 3dbc901..0f0f186 100644
--- a/lib.rs
+++ b/src/lib.rs
@@ -72,10 +72,10 @@
 
 #![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", allow(incomplete_features))]
-#![cfg_attr(feature = "const_generics", feature(const_generics))]
+#![cfg_attr(feature = "const_generics", feature(min_const_generics))]
 #![deny(missing_docs)]
 
 #[doc(hidden)]
@@ -84,6 +84,9 @@ pub extern crate alloc;
 #[cfg(any(test, feature = "write"))]
 extern crate std;
 
+#[cfg(test)]
+mod tests;
+
 use alloc::alloc::{Layout, LayoutErr};
 use alloc::boxed::Box;
 use alloc::{vec, vec::Vec};
@@ -95,7 +98,7 @@ use core::hint::unreachable_unchecked;
 use core::iter::{repeat, FromIterator, FusedIterator, IntoIterator};
 use core::mem;
 use core::mem::MaybeUninit;
-use core::ops::{self, RangeBounds};
+use core::ops::{self, Range, RangeBounds};
 use core::ptr::{self, NonNull};
 use core::slice::{self, SliceIndex};
 
@@ -677,7 +680,11 @@ impl<A: Array> SmallVec<A> {
                 let &mut (ptr, ref mut len_ptr) = self.data.heap_mut();
                 (ptr, len_ptr, self.capacity)
             } else {
-                (self.data.inline_mut(), &mut self.capacity, Self::inline_capacity())
+                (
+                    self.data.inline_mut(),
+                    &mut self.capacity,
+                    Self::inline_capacity(),
+                )
             }
         }
     }
@@ -972,8 +979,6 @@ impl<A: Array> SmallVec<A> {
 
     /// Insert multiple elements at position `index`, shifting all following elements toward the
     /// back.
-    ///
-    /// Note: when the iterator panics, this can leak memory.
     pub fn insert_many<I: IntoIterator<Item = A::Item>>(&mut self, index: usize, iterable: I) {
         let iter = iterable.into_iter();
         if index == self.len() {
@@ -988,13 +993,19 @@ impl<A: Array> SmallVec<A> {
         unsafe {
             let old_len = self.len();
             assert!(index <= old_len);
-            let mut ptr = self.as_mut_ptr().add(index);
+            let start = self.as_mut_ptr();
+            let mut ptr = start.add(index);
 
             // Move the trailing elements.
             ptr::copy(ptr, ptr.add(lower_size_bound), old_len - index);
 
             // In case the iterator panics, don't double-drop the items we just copied above.
-            self.set_len(index);
+            self.set_len(0);
+            let mut guard = DropOnPanic {
+                start,
+                skip: index..(index + lower_size_bound),
+                len: old_len + lower_size_bound,
+            };
 
             let mut num_added = 0;
             for element in iter {
@@ -1002,13 +1013,21 @@ impl<A: Array> SmallVec<A> {
                 if num_added >= lower_size_bound {
                     // Iterator provided more elements than the hint.  Move trailing items again.
                     self.reserve(1);
-                    ptr = self.as_mut_ptr().add(index);
+                    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;
                 }
                 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
                 ptr::copy(
@@ -1020,6 +1039,24 @@ impl<A: Array> SmallVec<A> {
 
             self.set_len(old_len + num_added);
         }
+
+        struct DropOnPanic<T> {
+            start: *mut T,
+            skip: Range<usize>,
+            len: usize,
+        }
+
+        impl<T> Drop for DropOnPanic<T> {
+            fn drop(&mut self) {
+                for i in 0..self.len {
+                    if !self.skip.contains(&i) {
+                        unsafe {
+                            ptr::drop_in_place(self.start.add(i));
+                        }
+                    }
+                }
+            }
+        }
     }
 
     /// Convert a SmallVec to a Vec, without reallocating if the SmallVec has already spilled onto
@@ -1050,7 +1087,8 @@ impl<A: Array> SmallVec<A> {
     /// This method returns `Err(Self)` if the SmallVec is too short (and the `A` contains uninitialized elements),
     /// or if the SmallVec is too long (and all the elements were spilled to the heap).
     pub fn into_inner(self) -> Result<A, Self> {
-        if self.spilled() || self.len() != A::size() { // Note: A::size, not Self::inline_capacity
+        if self.spilled() || self.len() != A::size() {
+            // Note: A::size, not Self::inline_capacity
             Err(self)
         } else {
             unsafe {
@@ -1246,6 +1284,22 @@ impl<A: Array> SmallVec<A> {
             data: SmallVecData::from_heap(ptr, length),
         }
     }
+
+    /// Returns a raw pointer to the vector's buffer.
+    pub fn as_ptr(&self) -> *const A::Item {
+        // We shadow the slice method of the same name to avoid going through
+        // `deref`, which creates an intermediate reference that may place
+        // additional safety constraints on the contents of the slice.
+        self.triple().0
+    }
+
+    /// Returns a raw mutable pointer to the vector's buffer.
+    pub fn as_mut_ptr(&mut self) -> *mut A::Item {
+        // We shadow the slice method of the same name to avoid going through
+        // `deref_mut`, which creates an intermediate reference that may place
+        // additional safety constraints on the contents of the slice.
+        self.triple_mut().0
+    }
 }
 
 impl<A: Array> SmallVec<A>
@@ -1894,867 +1948,3 @@ where
         SmallVec::from_slice(self)
     }
 }
-
-#[cfg(test)]
-mod tests {
-    use crate::SmallVec;
-
-    use std::iter::FromIterator;
-
-    use alloc::borrow::ToOwned;
-    use alloc::boxed::Box;
-    use alloc::rc::Rc;
-    use alloc::{vec, vec::Vec};
-
-    #[test]
-    pub fn test_zero() {
-        let mut v = SmallVec::<[_; 0]>::new();
-        assert!(!v.spilled());
-        v.push(0usize);
-        assert!(v.spilled());
-        assert_eq!(&*v, &[0]);
-    }
-
-    // We heap allocate all these strings so that double frees will show up under valgrind.
-
-    #[test]
-    pub fn test_inline() {
-        let mut v = SmallVec::<[_; 16]>::new();
-        v.push("hello".to_owned());
-        v.push("there".to_owned());
-        assert_eq!(&*v, &["hello".to_owned(), "there".to_owned(),][..]);
-    }
-
-    #[test]
-    pub fn test_spill() {
-        let mut v = SmallVec::<[_; 2]>::new();
-        v.push("hello".to_owned());
-        assert_eq!(v[0], "hello");
-        v.push("there".to_owned());
-        v.push("burma".to_owned());
-        assert_eq!(v[0], "hello");
-        v.push("shave".to_owned());
-        assert_eq!(
-            &*v,
-            &[
-                "hello".to_owned(),
-                "there".to_owned(),
-                "burma".to_owned(),
-                "shave".to_owned(),
-            ][..]
-        );
-    }
-
-    #[test]
-    pub fn test_double_spill() {
-        let mut v = SmallVec::<[_; 2]>::new();
-        v.push("hello".to_owned());
-        v.push("there".to_owned());
-        v.push("burma".to_owned());
-        v.push("shave".to_owned());
-        v.push("hello".to_owned());
-        v.push("there".to_owned());
-        v.push("burma".to_owned());
-        v.push("shave".to_owned());
-        assert_eq!(
-            &*v,
-            &[
-                "hello".to_owned(),
-                "there".to_owned(),
-                "burma".to_owned(),
-                "shave".to_owned(),
-                "hello".to_owned(),
-                "there".to_owned(),
-                "burma".to_owned(),
-                "shave".to_owned(),
-            ][..]
-        );
-    }
-
-    /// https://github.com/servo/rust-smallvec/issues/4
-    #[test]
-    fn issue_4() {
-        SmallVec::<[Box<u32>; 2]>::new();
-    }
-
-    /// https://github.com/servo/rust-smallvec/issues/5
-    #[test]
-    fn issue_5() {
-        assert!(Some(SmallVec::<[&u32; 2]>::new()).is_some());
-    }
-
-    #[test]
-    fn test_with_capacity() {
-        let v: SmallVec<[u8; 3]> = SmallVec::with_capacity(1);
-        assert!(v.is_empty());
-        assert!(!v.spilled());
-        assert_eq!(v.capacity(), 3);
-
-        let v: SmallVec<[u8; 3]> = SmallVec::with_capacity(10);
-        assert!(v.is_empty());
-        assert!(v.spilled());
-        assert_eq!(v.capacity(), 10);
-    }
-
-    #[test]
-    fn drain() {
-        let mut v: SmallVec<[u8; 2]> = SmallVec::new();
-        v.push(3);
-        assert_eq!(v.drain(..).collect::<Vec<_>>(), &[3]);
-
-        // spilling the vec
-        v.push(3);
-        v.push(4);
-        v.push(5);
-        let old_capacity = v.capacity();
-        assert_eq!(v.drain(1..).collect::<Vec<_>>(), &[4, 5]);
-        // drain should not change the capacity
-        assert_eq!(v.capacity(), old_capacity);
-    }
-
-    #[test]
-    fn drain_rev() {
-        let mut v: SmallVec<[u8; 2]> = SmallVec::new();
-        v.push(3);
-        assert_eq!(v.drain(..).rev().collect::<Vec<_>>(), &[3]);
-
-        // spilling the vec
-        v.push(3);
-        v.push(4);
-        v.push(5);
-        assert_eq!(v.drain(..).rev().collect::<Vec<_>>(), &[5, 4, 3]);
-    }
-
-    #[test]
-    fn drain_forget() {
-        let mut v: SmallVec<[u8; 1]> = smallvec![0, 1, 2, 3, 4, 5, 6, 7];
-        std::mem::forget(v.drain(2..5));
-        assert_eq!(v.len(), 2);
-    }
-
-    #[test]
-    fn into_iter() {
-        let mut v: SmallVec<[u8; 2]> = SmallVec::new();
-        v.push(3);
-        assert_eq!(v.into_iter().collect::<Vec<_>>(), &[3]);
-
-        // spilling the vec
-        let mut v: SmallVec<[u8; 2]> = SmallVec::new();
-        v.push(3);
-        v.push(4);
-        v.push(5);
-        assert_eq!(v.into_iter().collect::<Vec<_>>(), &[3, 4, 5]);
-    }
-
-    #[test]
-    fn into_iter_rev() {
-        let mut v: SmallVec<[u8; 2]> = SmallVec::new();
-        v.push(3);
-        assert_eq!(v.into_iter().rev().collect::<Vec<_>>(), &[3]);
-
-        // spilling the vec
-        let mut v: SmallVec<[u8; 2]> = SmallVec::new();
-        v.push(3);
-        v.push(4);
-        v.push(5);
-        assert_eq!(v.into_iter().rev().collect::<Vec<_>>(), &[5, 4, 3]);
-    }
-
-    #[test]
-    fn into_iter_drop() {
-        use std::cell::Cell;
-
-        struct DropCounter<'a>(&'a Cell<i32>);
-
-        impl<'a> Drop for DropCounter<'a> {
-            fn drop(&mut self) {
-                self.0.set(self.0.get() + 1);
-            }
-        }
-
-        {
-            let cell = Cell::new(0);
-            let mut v: SmallVec<[DropCounter<'_>; 2]> = SmallVec::new();
-            v.push(DropCounter(&cell));
-            v.into_iter();
-            assert_eq!(cell.get(), 1);
-        }
-
-        {
-            let cell = Cell::new(0);
-            let mut v: SmallVec<[DropCounter<'_>; 2]> = SmallVec::new();
-            v.push(DropCounter(&cell));
-            v.push(DropCounter(&cell));
-            assert!(v.into_iter().next().is_some());
-            assert_eq!(cell.get(), 2);
-        }
-
-        {
-            let cell = Cell::new(0);
-            let mut v: SmallVec<[DropCounter<'_>; 2]> = SmallVec::new();
-            v.push(DropCounter(&cell));
-            v.push(DropCounter(&cell));
-            v.push(DropCounter(&cell));
-            assert!(v.into_iter().next().is_some());
-            assert_eq!(cell.get(), 3);
-        }
-        {
-            let cell = Cell::new(0);
-            let mut v: SmallVec<[DropCounter<'_>; 2]> = SmallVec::new();
-            v.push(DropCounter(&cell));
-            v.push(DropCounter(&cell));
-            v.push(DropCounter(&cell));
-            {
-                let mut it = v.into_iter();
-                assert!(it.next().is_some());
-                assert!(it.next_back().is_some());
-            }
-            assert_eq!(cell.get(), 3);
-        }
-    }
-
-    #[test]
-    fn test_capacity() {
-        let mut v: SmallVec<[u8; 2]> = SmallVec::new();
-        v.reserve(1);
-        assert_eq!(v.capacity(), 2);
-        assert!(!v.spilled());
-
-        v.reserve_exact(0x100);
-        assert!(v.capacity() >= 0x100);
-
-        v.push(0);
-        v.push(1);
-        v.push(2);
-        v.push(3);
-
-        v.shrink_to_fit();
-        assert!(v.capacity() < 0x100);
-    }
-
-    #[test]
-    fn test_truncate() {
-        let mut v: SmallVec<[Box<u8>; 8]> = SmallVec::new();
-
-        for x in 0..8 {
-            v.push(Box::new(x));
-        }
-        v.truncate(4);
-
-        assert_eq!(v.len(), 4);
-        assert!(!v.spilled());
-
-        assert_eq!(*v.swap_remove(1), 1);
-        assert_eq!(*v.remove(1), 3);
-        v.insert(1, Box::new(3));
-
-        assert_eq!(&v.iter().map(|v| **v).collect::<Vec<_>>(), &[0, 3, 2]);
-    }
-
-    #[test]
-    fn test_insert_many() {
-        let mut v: SmallVec<[u8; 8]> = SmallVec::new();
-        for x in 0..4 {
-            v.push(x);
-        }
-        assert_eq!(v.len(), 4);
-        v.insert_many(1, [5, 6].iter().cloned());
-        assert_eq!(
-            &v.iter().map(|v| *v).collect::<Vec<_>>(),
-            &[0, 5, 6, 1, 2, 3]
-        );
-    }
-
-    struct MockHintIter<T: Iterator> {
-        x: T,
-        hint: usize,
-    }
-    impl<T: Iterator> Iterator for MockHintIter<T> {
-        type Item = T::Item;
-        fn next(&mut self) -> Option<Self::Item> {
-            self.x.next()
-        }
-        fn size_hint(&self) -> (usize, Option<usize>) {
-            (self.hint, None)
-        }
-    }
-
-    #[test]
-    fn test_insert_many_short_hint() {
-        let mut v: SmallVec<[u8; 8]> = SmallVec::new();
-        for x in 0..4 {
-            v.push(x);
-        }
-        assert_eq!(v.len(), 4);
-        v.insert_many(
-            1,
-            MockHintIter {
-                x: [5, 6].iter().cloned(),
-                hint: 5,
-            },
-        );
-        assert_eq!(
-            &v.iter().map(|v| *v).collect::<Vec<_>>(),
-            &[0, 5, 6, 1, 2, 3]
-        );
-    }
-
-    #[test]
-    fn test_insert_many_long_hint() {
-        let mut v: SmallVec<[u8; 8]> = SmallVec::new();
-        for x in 0..4 {
-            v.push(x);
-        }
-        assert_eq!(v.len(), 4);
-        v.insert_many(
-            1,
-            MockHintIter {
-                x: [5, 6].iter().cloned(),
-                hint: 1,
-            },
-        );
-        assert_eq!(
-            &v.iter().map(|v| *v).collect::<Vec<_>>(),
-            &[0, 5, 6, 1, 2, 3]
-        );
-    }
-
-    #[test]
-    // https://github.com/servo/rust-smallvec/issues/96
-    fn test_insert_many_panic() {
-        struct PanicOnDoubleDrop {
-            dropped: Box<bool>,
-        }
-
-        impl Drop for PanicOnDoubleDrop {
-            fn drop(&mut self) {
-                assert!(!*self.dropped, "already dropped");
-                *self.dropped = true;
-            }
-        }
-
-        struct BadIter;
-        impl Iterator for BadIter {
-            type Item = PanicOnDoubleDrop;
-            fn size_hint(&self) -> (usize, Option<usize>) {
-                (1, None)
-            }
-            fn next(&mut self) -> Option<Self::Item> {
-                panic!()
-            }
-        }
-
-        // These boxes are leaked on purpose by panicking `insert_many`,
-        // so we clean them up manually to appease Miri's leak checker.
-        let mut box1 = Box::new(false);
-        let mut box2 = Box::new(false);
-
-        let mut vec: SmallVec<[PanicOnDoubleDrop; 0]> = vec![
-            PanicOnDoubleDrop {
-                dropped: unsafe { Box::from_raw(&mut *box1) },
-            },
-            PanicOnDoubleDrop {
-                dropped: unsafe { Box::from_raw(&mut *box2) },
-            },
-        ]
-        .into();
-        let result = ::std::panic::catch_unwind(move || {
-            vec.insert_many(0, BadIter);
-        });
-        assert!(result.is_err());
-
-        drop(box1);
-        drop(box2);
-    }
-
-    #[test]
-    #[should_panic]
-    fn test_invalid_grow() {
-        let mut v: SmallVec<[u8; 8]> = SmallVec::new();
-        v.extend(0..8);
-        v.grow(5);
-    }
-
-    #[test]
-    fn test_insert_from_slice() {
-        let mut v: SmallVec<[u8; 8]> = SmallVec::new();
-        for x in 0..4 {
-            v.push(x);
-        }
-        assert_eq!(v.len(), 4);
-        v.insert_from_slice(1, &[5, 6]);
-        assert_eq!(
-            &v.iter().map(|v| *v).collect::<Vec<_>>(),
-            &[0, 5, 6, 1, 2, 3]
-        );
-    }
-
-    #[test]
-    fn test_extend_from_slice() {
-        let mut v: SmallVec<[u8; 8]> = SmallVec::new();
-        for x in 0..4 {
-            v.push(x);
-        }
-        assert_eq!(v.len(), 4);
-        v.extend_from_slice(&[5, 6]);
-        assert_eq!(
-            &v.iter().map(|v| *v).collect::<Vec<_>>(),
-            &[0, 1, 2, 3, 5, 6]
-        );
-    }
-
-    #[test]
-    #[should_panic]
-    fn test_drop_panic_smallvec() {
-        // This test should only panic once, and not double panic,
-        // which would mean a double drop
-        struct DropPanic;
-
-        impl Drop for DropPanic {
-            fn drop(&mut self) {
-                panic!("drop");
-            }
-        }
-
-        let mut v = SmallVec::<[_; 1]>::new();
-        v.push(DropPanic);
-    }
-
-    #[test]
-    fn test_eq() {
-        let mut a: SmallVec<[u32; 2]> = SmallVec::new();
-        let mut b: SmallVec<[u32; 2]> = SmallVec::new();
-        let mut c: SmallVec<[u32; 2]> = SmallVec::new();
-        // a = [1, 2]
-        a.push(1);
-        a.push(2);
-        // b = [1, 2]
-        b.push(1);
-        b.push(2);
-        // c = [3, 4]
-        c.push(3);
-        c.push(4);
-
-        assert!(a == b);
-        assert!(a != c);
-    }
-
-    #[test]
-    fn test_ord() {
-        let mut a: SmallVec<[u32; 2]> = SmallVec::new();
-        let mut b: SmallVec<[u32; 2]> = SmallVec::new();
-        let mut c: SmallVec<[u32; 2]> = SmallVec::new();
-        // a = [1]
-        a.push(1);
-        // b = [1, 1]
-        b.push(1);
-        b.push(1);
-        // c = [1, 2]
-        c.push(1);
-        c.push(2);
-
-        assert!(a < b);
-        assert!(b > a);
-        assert!(b < c);
-        assert!(c > b);
-    }
-
-    #[test]
-    fn test_hash() {
-        use std::collections::hash_map::DefaultHasher;
-        use std::hash::Hash;
-
-        {
-            let mut a: SmallVec<[u32; 2]> = SmallVec::new();
-            let b = [1, 2];
-            a.extend(b.iter().cloned());
-            let mut hasher = DefaultHasher::new();
-            assert_eq!(a.hash(&mut hasher), b.hash(&mut hasher));
-        }
-        {
-            let mut a: SmallVec<[u32; 2]> = SmallVec::new();
-            let b = [1, 2, 11, 12];
-            a.extend(b.iter().cloned());
-            let mut hasher = DefaultHasher::new();
-            assert_eq!(a.hash(&mut hasher), b.hash(&mut hasher));
-        }
-    }
-
-    #[test]
-    fn test_as_ref() {
-        let mut a: SmallVec<[u32; 2]> = SmallVec::new();
-        a.push(1);
-        assert_eq!(a.as_ref(), [1]);
-        a.push(2);
-        assert_eq!(a.as_ref(), [1, 2]);
-        a.push(3);
-        assert_eq!(a.as_ref(), [1, 2, 3]);
-    }
-
-    #[test]
-    fn test_as_mut() {
-        let mut a: SmallVec<[u32; 2]> = SmallVec::new();
-        a.push(1);
-        assert_eq!(a.as_mut(), [1]);
-        a.push(2);
-        assert_eq!(a.as_mut(), [1, 2]);
-        a.push(3);
-        assert_eq!(a.as_mut(), [1, 2, 3]);
-        a.as_mut()[1] = 4;
-        assert_eq!(a.as_mut(), [1, 4, 3]);
-    }
-
-    #[test]
-    fn test_borrow() {
-        use std::borrow::Borrow;
-
-        let mut a: SmallVec<[u32; 2]> = SmallVec::new();
-        a.push(1);
-        assert_eq!(a.borrow(), [1]);
-        a.push(2);
-        assert_eq!(a.borrow(), [1, 2]);
-        a.push(3);
-        assert_eq!(a.borrow(), [1, 2, 3]);
-    }
-
-    #[test]
-    fn test_borrow_mut() {
-        use std::borrow::BorrowMut;
-
-        let mut a: SmallVec<[u32; 2]> = SmallVec::new();
-        a.push(1);
-        assert_eq!(a.borrow_mut(), [1]);
-        a.push(2);
-        assert_eq!(a.borrow_mut(), [1, 2]);
-        a.push(3);
-        assert_eq!(a.borrow_mut(), [1, 2, 3]);
-        BorrowMut::<[u32]>::borrow_mut(&mut a)[1] = 4;
-        assert_eq!(a.borrow_mut(), [1, 4, 3]);
-    }
-
-    #[test]
-    fn test_from() {
-        assert_eq!(&SmallVec::<[u32; 2]>::from(&[1][..])[..], [1]);
-        assert_eq!(&SmallVec::<[u32; 2]>::from(&[1, 2, 3][..])[..], [1, 2, 3]);
-
-        let vec = vec![];
-        let small_vec: SmallVec<[u8; 3]> = SmallVec::from(vec);
-        assert_eq!(&*small_vec, &[]);
-        drop(small_vec);
-
-        let vec = vec![1, 2, 3, 4, 5];
-        let small_vec: SmallVec<[u8; 3]> = SmallVec::from(vec);
-        assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
-        drop(small_vec);
-
-        let vec = vec![1, 2, 3, 4, 5];
-        let small_vec: SmallVec<[u8; 1]> = SmallVec::from(vec);
-        assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
-        drop(small_vec);
-
-        let array = [1];
-        let small_vec: SmallVec<[u8; 1]> = SmallVec::from(array);
-        assert_eq!(&*small_vec, &[1]);
-        drop(small_vec);
-
-        let array = [99; 128];
-        let small_vec: SmallVec<[u8; 128]> = SmallVec::from(array);
-        assert_eq!(&*small_vec, vec![99u8; 128].as_slice());
-        drop(small_vec);
-    }
-
-    #[test]
-    fn test_from_slice() {
-        assert_eq!(&SmallVec::<[u32; 2]>::from_slice(&[1][..])[..], [1]);
-        assert_eq!(
-            &SmallVec::<[u32; 2]>::from_slice(&[1, 2, 3][..])[..],
-            [1, 2, 3]
-        );
-    }
-
-    #[test]
-    fn test_exact_size_iterator() {
-        let mut vec = SmallVec::<[u32; 2]>::from(&[1, 2, 3][..]);
-        assert_eq!(vec.clone().into_iter().len(), 3);
-        assert_eq!(vec.drain(..2).len(), 2);
-        assert_eq!(vec.into_iter().len(), 1);
-    }
-
-    #[test]
-    fn test_into_iter_as_slice() {
-        let vec = SmallVec::<[u32; 2]>::from(&[1, 2, 3][..]);
-        let mut iter = vec.clone().into_iter();
-        assert_eq!(iter.as_slice(), &[1, 2, 3]);
-        assert_eq!(iter.as_mut_slice(), &[1, 2, 3]);
-        iter.next();
-        assert_eq!(iter.as_slice(), &[2, 3]);
-        assert_eq!(iter.as_mut_slice(), &[2, 3]);
-        iter.next_back();
-        assert_eq!(iter.as_slice(), &[2]);
-        assert_eq!(iter.as_mut_slice(), &[2]);
-    }
-
-    #[test]
-    fn test_into_iter_clone() {
-        // Test that the cloned iterator yields identical elements and that it owns its own copy
-        // (i.e. no use after move errors).
-        let mut iter = SmallVec::<[u8; 2]>::from_iter(0..3).into_iter();
-        let mut clone_iter = iter.clone();
-        while let Some(x) = iter.next() {
-            assert_eq!(x, clone_iter.next().unwrap());
-        }
-        assert_eq!(clone_iter.next(), None);
-    }
-
-    #[test]
-    fn test_into_iter_clone_partially_consumed_iterator() {
-        // Test that the cloned iterator only contains the remaining elements of the original iterator.
-        let mut iter = SmallVec::<[u8; 2]>::from_iter(0..3).into_iter().skip(1);
-        let mut clone_iter = iter.clone();
-        while let Some(x) = iter.next() {
-            assert_eq!(x, clone_iter.next().unwrap());
-        }
-        assert_eq!(clone_iter.next(), None);
-    }
-
-    #[test]
-    fn test_into_iter_clone_empty_smallvec() {
-        let mut iter = SmallVec::<[u8; 2]>::new().into_iter();
-        let mut clone_iter = iter.clone();
-        assert_eq!(iter.next(), None);
-        assert_eq!(clone_iter.next(), None);
-    }
-
-    #[test]
-    fn shrink_to_fit_unspill() {
-        let mut vec = SmallVec::<[u8; 2]>::from_iter(0..3);
-        vec.pop();
-        assert!(vec.spilled());
-        vec.shrink_to_fit();
-        assert!(!vec.spilled(), "shrink_to_fit will un-spill if possible");
-    }
-
-    #[test]
-    fn test_into_vec() {
-        let vec = SmallVec::<[u8; 2]>::from_iter(0..2);
-        assert_eq!(vec.into_vec(), vec![0, 1]);
-
-        let vec = SmallVec::<[u8; 2]>::from_iter(0..3);
-        assert_eq!(vec.into_vec(), vec![0, 1, 2]);
-    }
-
-    #[test]
-    fn test_into_inner() {
-        let vec = SmallVec::<[u8; 2]>::from_iter(0..2);
-        assert_eq!(vec.into_inner(), Ok([0, 1]));
-
-        let vec = SmallVec::<[u8; 2]>::from_iter(0..1);
-        assert_eq!(vec.clone().into_inner(), Err(vec));
-
-        let vec = SmallVec::<[u8; 2]>::from_iter(0..3);
-        assert_eq!(vec.clone().into_inner(), Err(vec));
-    }
-
-    #[test]
-    fn test_from_vec() {
-        let vec = vec![];
-        let small_vec: SmallVec<[u8; 3]> = SmallVec::from_vec(vec);
-        assert_eq!(&*small_vec, &[]);
-        drop(small_vec);
-
-        let vec = vec![];
-        let small_vec: SmallVec<[u8; 1]> = SmallVec::from_vec(vec);
-        assert_eq!(&*small_vec, &[]);
-        drop(small_vec);
-
-        let vec = vec![1];
-        let small_vec: SmallVec<[u8; 3]> = SmallVec::from_vec(vec);
-        assert_eq!(&*small_vec, &[1]);
-        drop(small_vec);
-
-        let vec = vec![1, 2, 3];
-        let small_vec: SmallVec<[u8; 3]> = SmallVec::from_vec(vec);
-        assert_eq!(&*small_vec, &[1, 2, 3]);
-        drop(small_vec);
-
-        let vec = vec![1, 2, 3, 4, 5];
-        let small_vec: SmallVec<[u8; 3]> = SmallVec::from_vec(vec);
-        assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
-        drop(small_vec);
-
-        let vec = vec![1, 2, 3, 4, 5];
-        let small_vec: SmallVec<[u8; 1]> = SmallVec::from_vec(vec);
-        assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
-        drop(small_vec);
-    }
-
-    #[test]
-    fn test_retain() {
-        // Test inline data storate
-        let mut sv: SmallVec<[i32; 5]> = SmallVec::from_slice(&[1, 2, 3, 3, 4]);
-        sv.retain(|&mut i| i != 3);
-        assert_eq!(sv.pop(), Some(4));
-        assert_eq!(sv.pop(), Some(2));
-        assert_eq!(sv.pop(), Some(1));
-        assert_eq!(sv.pop(), None);
-
-        // Test spilled data storage
-        let mut sv: SmallVec<[i32; 3]> = SmallVec::from_slice(&[1, 2, 3, 3, 4]);
-        sv.retain(|&mut i| i != 3);
-        assert_eq!(sv.pop(), Some(4));
-        assert_eq!(sv.pop(), Some(2));
-        assert_eq!(sv.pop(), Some(1));
-        assert_eq!(sv.pop(), None);
-
-        // Test that drop implementations are called for inline.
-        let one = Rc::new(1);
-        let mut sv: SmallVec<[Rc<i32>; 3]> = SmallVec::new();
-        sv.push(Rc::clone(&one));
-        assert_eq!(Rc::strong_count(&one), 2);
-        sv.retain(|_| false);
-        assert_eq!(Rc::strong_count(&one), 1);
-
-        // Test that drop implementations are called for spilled data.
-        let mut sv: SmallVec<[Rc<i32>; 1]> = SmallVec::new();
-        sv.push(Rc::clone(&one));
-        sv.push(Rc::new(2));
-        assert_eq!(Rc::strong_count(&one), 2);
-        sv.retain(|_| false);
-        assert_eq!(Rc::strong_count(&one), 1);
-    }
-
-    #[test]
-    fn test_dedup() {
-        let mut dupes: SmallVec<[i32; 5]> = SmallVec::from_slice(&[1, 1, 2, 3, 3]);
-        dupes.dedup();
-        assert_eq!(&*dupes, &[1, 2, 3]);
-
-        let mut empty: SmallVec<[i32; 5]> = SmallVec::new();
-        empty.dedup();
-        assert!(empty.is_empty());
-
-        let mut all_ones: SmallVec<[i32; 5]> = SmallVec::from_slice(&[1, 1, 1, 1, 1]);
-        all_ones.dedup();
-        assert_eq!(all_ones.len(), 1);
-
-        let mut no_dupes: SmallVec<[i32; 5]> = SmallVec::from_slice(&[1, 2, 3, 4, 5]);
-        no_dupes.dedup();
-        assert_eq!(no_dupes.len(), 5);
-    }
-
-    #[test]
-    fn test_resize() {
-        let mut v: SmallVec<[i32; 8]> = SmallVec::new();
-        v.push(1);
-        v.resize(5, 0);
-        assert_eq!(v[..], [1, 0, 0, 0, 0][..]);
-
-        v.resize(2, -1);
-        assert_eq!(v[..], [1, 0][..]);
-    }
-
-    #[cfg(feature = "write")]
-    #[test]
-    fn test_write() {
-        use std::io::Write;
-
-        let data = [1, 2, 3, 4, 5];
-
-        let mut small_vec: SmallVec<[u8; 2]> = SmallVec::new();
-        let len = small_vec.write(&data[..]).unwrap();
-        assert_eq!(len, 5);
-        assert_eq!(small_vec.as_ref(), data.as_ref());
-
-        let mut small_vec: SmallVec<[u8; 2]> = SmallVec::new();
-        small_vec.write_all(&data[..]).unwrap();
-        assert_eq!(small_vec.as_ref(), data.as_ref());
-    }
-
-    #[cfg(feature = "serde")]
-    extern crate bincode;
-
-    #[cfg(feature = "serde")]
-    #[test]
-    fn test_serde() {
-        use self::bincode::{config, deserialize};
-        let mut small_vec: SmallVec<[i32; 2]> = SmallVec::new();
-        small_vec.push(1);
-        let encoded = config().limit(100).serialize(&small_vec).unwrap();
-        let decoded: SmallVec<[i32; 2]> = deserialize(&encoded).unwrap();
-        assert_eq!(small_vec, decoded);
-        small_vec.push(2);
-        // Spill the vec
-        small_vec.push(3);
-        small_vec.push(4);
-        // Check again after spilling.
-        let encoded = config().limit(100).serialize(&small_vec).unwrap();
-        let decoded: SmallVec<[i32; 2]> = deserialize(&encoded).unwrap();
-        assert_eq!(small_vec, decoded);
-    }
-
-    #[test]
-    fn grow_to_shrink() {
-        let mut v: SmallVec<[u8; 2]> = SmallVec::new();
-        v.push(1);
-        v.push(2);
-        v.push(3);
-        assert!(v.spilled());
-        v.clear();
-        // Shrink to inline.
-        v.grow(2);
-        assert!(!v.spilled());
-        assert_eq!(v.capacity(), 2);
-        assert_eq!(v.len(), 0);
-        v.push(4);
-        assert_eq!(v[..], [4]);
-    }
-
-    #[test]
-    fn resumable_extend() {
-        let s = "a b c";
-        // This iterator yields: (Some('a'), None, Some('b'), None, Some('c')), None
-        let it = s
-            .chars()
-            .scan(0, |_, ch| if ch.is_whitespace() { None } else { Some(ch) });
-        let mut v: SmallVec<[char; 4]> = SmallVec::new();
-        v.extend(it);
-        assert_eq!(v[..], ['a']);
-    }
-
-    // #139
-    #[test]
-    fn uninhabited() {
-        enum Void {}
-        let _sv = SmallVec::<[Void; 8]>::new();
-    }
-
-    #[test]
-    fn grow_spilled_same_size() {
-        let mut v: SmallVec<[u8; 2]> = SmallVec::new();
-        v.push(0);
-        v.push(1);
-        v.push(2);
-        assert!(v.spilled());
-        assert_eq!(v.capacity(), 4);
-        // grow with the same capacity
-        v.grow(4);
-        assert_eq!(v.capacity(), 4);
-        assert_eq!(v[..], [0, 1, 2]);
-    }
-
-    #[cfg(feature = "const_generics")]
-    #[test]
-    fn const_generics() {
-        let _v = SmallVec::<[i32; 987]>::default();
-    }
-
-    #[test]
-    fn empty_macro() {
-        let _v: SmallVec<[u8; 1]> = smallvec![];
-    }
-
-    #[test]
-    fn zero_size_items() {
-        SmallVec::<[(); 0]>::new().push(());
-    }
-}
diff --git a/specialization.rs b/src/specialization.rs
index 658fa77..658fa77 100644
--- a/specialization.rs
+++ b/src/specialization.rs
diff --git a/src/tests.rs b/src/tests.rs
new file mode 100644
index 0000000..0452ae8
--- /dev/null
+++ b/src/tests.rs
@@ -0,0 +1,907 @@
+use crate::{smallvec, SmallVec};
+
+use std::iter::FromIterator;
+
+use alloc::borrow::ToOwned;
+use alloc::boxed::Box;
+use alloc::rc::Rc;
+use alloc::{vec, vec::Vec};
+
+#[test]
+pub fn test_zero() {
+    let mut v = SmallVec::<[_; 0]>::new();
+    assert!(!v.spilled());
+    v.push(0usize);
+    assert!(v.spilled());
+    assert_eq!(&*v, &[0]);
+}
+
+// We heap allocate all these strings so that double frees will show up under valgrind.
+
+#[test]
+pub fn test_inline() {
+    let mut v = SmallVec::<[_; 16]>::new();
+    v.push("hello".to_owned());
+    v.push("there".to_owned());
+    assert_eq!(&*v, &["hello".to_owned(), "there".to_owned(),][..]);
+}
+
+#[test]
+pub fn test_spill() {
+    let mut v = SmallVec::<[_; 2]>::new();
+    v.push("hello".to_owned());
+    assert_eq!(v[0], "hello");
+    v.push("there".to_owned());
+    v.push("burma".to_owned());
+    assert_eq!(v[0], "hello");
+    v.push("shave".to_owned());
+    assert_eq!(
+        &*v,
+        &[
+            "hello".to_owned(),
+            "there".to_owned(),
+            "burma".to_owned(),
+            "shave".to_owned(),
+        ][..]
+    );
+}
+
+#[test]
+pub fn test_double_spill() {
+    let mut v = SmallVec::<[_; 2]>::new();
+    v.push("hello".to_owned());
+    v.push("there".to_owned());
+    v.push("burma".to_owned());
+    v.push("shave".to_owned());
+    v.push("hello".to_owned());
+    v.push("there".to_owned());
+    v.push("burma".to_owned());
+    v.push("shave".to_owned());
+    assert_eq!(
+        &*v,
+        &[
+            "hello".to_owned(),
+            "there".to_owned(),
+            "burma".to_owned(),
+            "shave".to_owned(),
+            "hello".to_owned(),
+            "there".to_owned(),
+            "burma".to_owned(),
+            "shave".to_owned(),
+        ][..]
+    );
+}
+
+/// https://github.com/servo/rust-smallvec/issues/4
+#[test]
+fn issue_4() {
+    SmallVec::<[Box<u32>; 2]>::new();
+}
+
+/// https://github.com/servo/rust-smallvec/issues/5
+#[test]
+fn issue_5() {
+    assert!(Some(SmallVec::<[&u32; 2]>::new()).is_some());
+}
+
+#[test]
+fn test_with_capacity() {
+    let v: SmallVec<[u8; 3]> = SmallVec::with_capacity(1);
+    assert!(v.is_empty());
+    assert!(!v.spilled());
+    assert_eq!(v.capacity(), 3);
+
+    let v: SmallVec<[u8; 3]> = SmallVec::with_capacity(10);
+    assert!(v.is_empty());
+    assert!(v.spilled());
+    assert_eq!(v.capacity(), 10);
+}
+
+#[test]
+fn drain() {
+    let mut v: SmallVec<[u8; 2]> = SmallVec::new();
+    v.push(3);
+    assert_eq!(v.drain(..).collect::<Vec<_>>(), &[3]);
+
+    // spilling the vec
+    v.push(3);
+    v.push(4);
+    v.push(5);
+    let old_capacity = v.capacity();
+    assert_eq!(v.drain(1..).collect::<Vec<_>>(), &[4, 5]);
+    // drain should not change the capacity
+    assert_eq!(v.capacity(), old_capacity);
+}
+
+#[test]
+fn drain_rev() {
+    let mut v: SmallVec<[u8; 2]> = SmallVec::new();
+    v.push(3);
+    assert_eq!(v.drain(..).rev().collect::<Vec<_>>(), &[3]);
+
+    // spilling the vec
+    v.push(3);
+    v.push(4);
+    v.push(5);
+    assert_eq!(v.drain(..).rev().collect::<Vec<_>>(), &[5, 4, 3]);
+}
+
+#[test]
+fn drain_forget() {
+    let mut v: SmallVec<[u8; 1]> = smallvec![0, 1, 2, 3, 4, 5, 6, 7];
+    std::mem::forget(v.drain(2..5));
+    assert_eq!(v.len(), 2);
+}
+
+#[test]
+fn into_iter() {
+    let mut v: SmallVec<[u8; 2]> = SmallVec::new();
+    v.push(3);
+    assert_eq!(v.into_iter().collect::<Vec<_>>(), &[3]);
+
+    // spilling the vec
+    let mut v: SmallVec<[u8; 2]> = SmallVec::new();
+    v.push(3);
+    v.push(4);
+    v.push(5);
+    assert_eq!(v.into_iter().collect::<Vec<_>>(), &[3, 4, 5]);
+}
+
+#[test]
+fn into_iter_rev() {
+    let mut v: SmallVec<[u8; 2]> = SmallVec::new();
+    v.push(3);
+    assert_eq!(v.into_iter().rev().collect::<Vec<_>>(), &[3]);
+
+    // spilling the vec
+    let mut v: SmallVec<[u8; 2]> = SmallVec::new();
+    v.push(3);
+    v.push(4);
+    v.push(5);
+    assert_eq!(v.into_iter().rev().collect::<Vec<_>>(), &[5, 4, 3]);
+}
+
+#[test]
+fn into_iter_drop() {
+    use std::cell::Cell;
+
+    struct DropCounter<'a>(&'a Cell<i32>);
+
+    impl<'a> Drop for DropCounter<'a> {
+        fn drop(&mut self) {
+            self.0.set(self.0.get() + 1);
+        }
+    }
+
+    {
+        let cell = Cell::new(0);
+        let mut v: SmallVec<[DropCounter<'_>; 2]> = SmallVec::new();
+        v.push(DropCounter(&cell));
+        v.into_iter();
+        assert_eq!(cell.get(), 1);
+    }
+
+    {
+        let cell = Cell::new(0);
+        let mut v: SmallVec<[DropCounter<'_>; 2]> = SmallVec::new();
+        v.push(DropCounter(&cell));
+        v.push(DropCounter(&cell));
+        assert!(v.into_iter().next().is_some());
+        assert_eq!(cell.get(), 2);
+    }
+
+    {
+        let cell = Cell::new(0);
+        let mut v: SmallVec<[DropCounter<'_>; 2]> = SmallVec::new();
+        v.push(DropCounter(&cell));
+        v.push(DropCounter(&cell));
+        v.push(DropCounter(&cell));
+        assert!(v.into_iter().next().is_some());
+        assert_eq!(cell.get(), 3);
+    }
+    {
+        let cell = Cell::new(0);
+        let mut v: SmallVec<[DropCounter<'_>; 2]> = SmallVec::new();
+        v.push(DropCounter(&cell));
+        v.push(DropCounter(&cell));
+        v.push(DropCounter(&cell));
+        {
+            let mut it = v.into_iter();
+            assert!(it.next().is_some());
+            assert!(it.next_back().is_some());
+        }
+        assert_eq!(cell.get(), 3);
+    }
+}
+
+#[test]
+fn test_capacity() {
+    let mut v: SmallVec<[u8; 2]> = SmallVec::new();
+    v.reserve(1);
+    assert_eq!(v.capacity(), 2);
+    assert!(!v.spilled());
+
+    v.reserve_exact(0x100);
+    assert!(v.capacity() >= 0x100);
+
+    v.push(0);
+    v.push(1);
+    v.push(2);
+    v.push(3);
+
+    v.shrink_to_fit();
+    assert!(v.capacity() < 0x100);
+}
+
+#[test]
+fn test_truncate() {
+    let mut v: SmallVec<[Box<u8>; 8]> = SmallVec::new();
+
+    for x in 0..8 {
+        v.push(Box::new(x));
+    }
+    v.truncate(4);
+
+    assert_eq!(v.len(), 4);
+    assert!(!v.spilled());
+
+    assert_eq!(*v.swap_remove(1), 1);
+    assert_eq!(*v.remove(1), 3);
+    v.insert(1, Box::new(3));
+
+    assert_eq!(&v.iter().map(|v| **v).collect::<Vec<_>>(), &[0, 3, 2]);
+}
+
+#[test]
+fn test_insert_many() {
+    let mut v: SmallVec<[u8; 8]> = SmallVec::new();
+    for x in 0..4 {
+        v.push(x);
+    }
+    assert_eq!(v.len(), 4);
+    v.insert_many(1, [5, 6].iter().cloned());
+    assert_eq!(
+        &v.iter().map(|v| *v).collect::<Vec<_>>(),
+        &[0, 5, 6, 1, 2, 3]
+    );
+}
+
+struct MockHintIter<T: Iterator> {
+    x: T,
+    hint: usize,
+}
+impl<T: Iterator> Iterator for MockHintIter<T> {
+    type Item = T::Item;
+    fn next(&mut self) -> Option<Self::Item> {
+        self.x.next()
+    }
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.hint, None)
+    }
+}
+
+#[test]
+fn test_insert_many_short_hint() {
+    let mut v: SmallVec<[u8; 8]> = SmallVec::new();
+    for x in 0..4 {
+        v.push(x);
+    }
+    assert_eq!(v.len(), 4);
+    v.insert_many(
+        1,
+        MockHintIter {
+            x: [5, 6].iter().cloned(),
+            hint: 5,
+        },
+    );
+    assert_eq!(
+        &v.iter().map(|v| *v).collect::<Vec<_>>(),
+        &[0, 5, 6, 1, 2, 3]
+    );
+}
+
+#[test]
+fn test_insert_many_long_hint() {
+    let mut v: SmallVec<[u8; 8]> = SmallVec::new();
+    for x in 0..4 {
+        v.push(x);
+    }
+    assert_eq!(v.len(), 4);
+    v.insert_many(
+        1,
+        MockHintIter {
+            x: [5, 6].iter().cloned(),
+            hint: 1,
+        },
+    );
+    assert_eq!(
+        &v.iter().map(|v| *v).collect::<Vec<_>>(),
+        &[0, 5, 6, 1, 2, 3]
+    );
+}
+
+// https://github.com/servo/rust-smallvec/issues/96
+mod insert_many_panic {
+    use crate::{smallvec, SmallVec};
+    use alloc::boxed::Box;
+
+    struct PanicOnDoubleDrop {
+        dropped: Box<bool>,
+    }
+
+    impl PanicOnDoubleDrop {
+        fn new() -> Self {
+            Self {
+                dropped: Box::new(false),
+            }
+        }
+    }
+
+    impl Drop for PanicOnDoubleDrop {
+        fn drop(&mut self) {
+            assert!(!*self.dropped, "already dropped");
+            *self.dropped = true;
+        }
+    }
+
+    /// Claims to yield `hint` items, but actually yields `count`, then panics.
+    struct BadIter {
+        hint: usize,
+        count: usize,
+    }
+
+    impl Iterator for BadIter {
+        type Item = PanicOnDoubleDrop;
+        fn size_hint(&self) -> (usize, Option<usize>) {
+            (self.hint, None)
+        }
+        fn next(&mut self) -> Option<Self::Item> {
+            if self.count == 0 {
+                panic!()
+            }
+            self.count -= 1;
+            Some(PanicOnDoubleDrop::new())
+        }
+    }
+
+    #[test]
+    fn panic_early_at_start() {
+        let mut vec: SmallVec<[PanicOnDoubleDrop; 0]> =
+            smallvec![PanicOnDoubleDrop::new(), PanicOnDoubleDrop::new(),];
+        let result = ::std::panic::catch_unwind(move || {
+            vec.insert_many(0, BadIter { hint: 1, count: 0 });
+        });
+        assert!(result.is_err());
+    }
+
+    #[test]
+    fn panic_early_in_middle() {
+        let mut vec: SmallVec<[PanicOnDoubleDrop; 0]> =
+            smallvec![PanicOnDoubleDrop::new(), PanicOnDoubleDrop::new(),];
+        let result = ::std::panic::catch_unwind(move || {
+            vec.insert_many(1, BadIter { hint: 4, count: 2 });
+        });
+        assert!(result.is_err());
+    }
+
+    #[test]
+    fn panic_early_at_end() {
+        let mut vec: SmallVec<[PanicOnDoubleDrop; 0]> =
+            smallvec![PanicOnDoubleDrop::new(), PanicOnDoubleDrop::new(),];
+        let result = ::std::panic::catch_unwind(move || {
+            vec.insert_many(2, BadIter { hint: 3, count: 1 });
+        });
+        assert!(result.is_err());
+    }
+
+    #[test]
+    fn panic_late_at_start() {
+        let mut vec: SmallVec<[PanicOnDoubleDrop; 0]> =
+            smallvec![PanicOnDoubleDrop::new(), PanicOnDoubleDrop::new(),];
+        let result = ::std::panic::catch_unwind(move || {
+            vec.insert_many(0, BadIter { hint: 3, count: 5 });
+        });
+        assert!(result.is_err());
+    }
+
+    #[test]
+    fn panic_late_at_end() {
+        let mut vec: SmallVec<[PanicOnDoubleDrop; 0]> =
+            smallvec![PanicOnDoubleDrop::new(), PanicOnDoubleDrop::new(),];
+        let result = ::std::panic::catch_unwind(move || {
+            vec.insert_many(2, BadIter { hint: 3, count: 5 });
+        });
+        assert!(result.is_err());
+    }
+}
+
+#[test]
+#[should_panic]
+fn test_invalid_grow() {
+    let mut v: SmallVec<[u8; 8]> = SmallVec::new();
+    v.extend(0..8);
+    v.grow(5);
+}
+
+#[test]
+fn test_insert_from_slice() {
+    let mut v: SmallVec<[u8; 8]> = SmallVec::new();
+    for x in 0..4 {
+        v.push(x);
+    }
+    assert_eq!(v.len(), 4);
+    v.insert_from_slice(1, &[5, 6]);
+    assert_eq!(
+        &v.iter().map(|v| *v).collect::<Vec<_>>(),
+        &[0, 5, 6, 1, 2, 3]
+    );
+}
+
+#[test]
+fn test_extend_from_slice() {
+    let mut v: SmallVec<[u8; 8]> = SmallVec::new();
+    for x in 0..4 {
+        v.push(x);
+    }
+    assert_eq!(v.len(), 4);
+    v.extend_from_slice(&[5, 6]);
+    assert_eq!(
+        &v.iter().map(|v| *v).collect::<Vec<_>>(),
+        &[0, 1, 2, 3, 5, 6]
+    );
+}
+
+#[test]
+#[should_panic]
+fn test_drop_panic_smallvec() {
+    // This test should only panic once, and not double panic,
+    // which would mean a double drop
+    struct DropPanic;
+
+    impl Drop for DropPanic {
+        fn drop(&mut self) {
+            panic!("drop");
+        }
+    }
+
+    let mut v = SmallVec::<[_; 1]>::new();
+    v.push(DropPanic);
+}
+
+#[test]
+fn test_eq() {
+    let mut a: SmallVec<[u32; 2]> = SmallVec::new();
+    let mut b: SmallVec<[u32; 2]> = SmallVec::new();
+    let mut c: SmallVec<[u32; 2]> = SmallVec::new();
+    // a = [1, 2]
+    a.push(1);
+    a.push(2);
+    // b = [1, 2]
+    b.push(1);
+    b.push(2);
+    // c = [3, 4]
+    c.push(3);
+    c.push(4);
+
+    assert!(a == b);
+    assert!(a != c);
+}
+
+#[test]
+fn test_ord() {
+    let mut a: SmallVec<[u32; 2]> = SmallVec::new();
+    let mut b: SmallVec<[u32; 2]> = SmallVec::new();
+    let mut c: SmallVec<[u32; 2]> = SmallVec::new();
+    // a = [1]
+    a.push(1);
+    // b = [1, 1]
+    b.push(1);
+    b.push(1);
+    // c = [1, 2]
+    c.push(1);
+    c.push(2);
+
+    assert!(a < b);
+    assert!(b > a);
+    assert!(b < c);
+    assert!(c > b);
+}
+
+#[test]
+fn test_hash() {
+    use std::collections::hash_map::DefaultHasher;
+    use std::hash::Hash;
+
+    {
+        let mut a: SmallVec<[u32; 2]> = SmallVec::new();
+        let b = [1, 2];
+        a.extend(b.iter().cloned());
+        let mut hasher = DefaultHasher::new();
+        assert_eq!(a.hash(&mut hasher), b.hash(&mut hasher));
+    }
+    {
+        let mut a: SmallVec<[u32; 2]> = SmallVec::new();
+        let b = [1, 2, 11, 12];
+        a.extend(b.iter().cloned());
+        let mut hasher = DefaultHasher::new();
+        assert_eq!(a.hash(&mut hasher), b.hash(&mut hasher));
+    }
+}
+
+#[test]
+fn test_as_ref() {
+    let mut a: SmallVec<[u32; 2]> = SmallVec::new();
+    a.push(1);
+    assert_eq!(a.as_ref(), [1]);
+    a.push(2);
+    assert_eq!(a.as_ref(), [1, 2]);
+    a.push(3);
+    assert_eq!(a.as_ref(), [1, 2, 3]);
+}
+
+#[test]
+fn test_as_mut() {
+    let mut a: SmallVec<[u32; 2]> = SmallVec::new();
+    a.push(1);
+    assert_eq!(a.as_mut(), [1]);
+    a.push(2);
+    assert_eq!(a.as_mut(), [1, 2]);
+    a.push(3);
+    assert_eq!(a.as_mut(), [1, 2, 3]);
+    a.as_mut()[1] = 4;
+    assert_eq!(a.as_mut(), [1, 4, 3]);
+}
+
+#[test]
+fn test_borrow() {
+    use std::borrow::Borrow;
+
+    let mut a: SmallVec<[u32; 2]> = SmallVec::new();
+    a.push(1);
+    assert_eq!(a.borrow(), [1]);
+    a.push(2);
+    assert_eq!(a.borrow(), [1, 2]);
+    a.push(3);
+    assert_eq!(a.borrow(), [1, 2, 3]);
+}
+
+#[test]
+fn test_borrow_mut() {
+    use std::borrow::BorrowMut;
+
+    let mut a: SmallVec<[u32; 2]> = SmallVec::new();
+    a.push(1);
+    assert_eq!(a.borrow_mut(), [1]);
+    a.push(2);
+    assert_eq!(a.borrow_mut(), [1, 2]);
+    a.push(3);
+    assert_eq!(a.borrow_mut(), [1, 2, 3]);
+    BorrowMut::<[u32]>::borrow_mut(&mut a)[1] = 4;
+    assert_eq!(a.borrow_mut(), [1, 4, 3]);
+}
+
+#[test]
+fn test_from() {
+    assert_eq!(&SmallVec::<[u32; 2]>::from(&[1][..])[..], [1]);
+    assert_eq!(&SmallVec::<[u32; 2]>::from(&[1, 2, 3][..])[..], [1, 2, 3]);
+
+    let vec = vec![];
+    let small_vec: SmallVec<[u8; 3]> = SmallVec::from(vec);
+    assert_eq!(&*small_vec, &[]);
+    drop(small_vec);
+
+    let vec = vec![1, 2, 3, 4, 5];
+    let small_vec: SmallVec<[u8; 3]> = SmallVec::from(vec);
+    assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
+    drop(small_vec);
+
+    let vec = vec![1, 2, 3, 4, 5];
+    let small_vec: SmallVec<[u8; 1]> = SmallVec::from(vec);
+    assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
+    drop(small_vec);
+
+    let array = [1];
+    let small_vec: SmallVec<[u8; 1]> = SmallVec::from(array);
+    assert_eq!(&*small_vec, &[1]);
+    drop(small_vec);
+
+    let array = [99; 128];
+    let small_vec: SmallVec<[u8; 128]> = SmallVec::from(array);
+    assert_eq!(&*small_vec, vec![99u8; 128].as_slice());
+    drop(small_vec);
+}
+
+#[test]
+fn test_from_slice() {
+    assert_eq!(&SmallVec::<[u32; 2]>::from_slice(&[1][..])[..], [1]);
+    assert_eq!(
+        &SmallVec::<[u32; 2]>::from_slice(&[1, 2, 3][..])[..],
+        [1, 2, 3]
+    );
+}
+
+#[test]
+fn test_exact_size_iterator() {
+    let mut vec = SmallVec::<[u32; 2]>::from(&[1, 2, 3][..]);
+    assert_eq!(vec.clone().into_iter().len(), 3);
+    assert_eq!(vec.drain(..2).len(), 2);
+    assert_eq!(vec.into_iter().len(), 1);
+}
+
+#[test]
+fn test_into_iter_as_slice() {
+    let vec = SmallVec::<[u32; 2]>::from(&[1, 2, 3][..]);
+    let mut iter = vec.clone().into_iter();
+    assert_eq!(iter.as_slice(), &[1, 2, 3]);
+    assert_eq!(iter.as_mut_slice(), &[1, 2, 3]);
+    iter.next();
+    assert_eq!(iter.as_slice(), &[2, 3]);
+    assert_eq!(iter.as_mut_slice(), &[2, 3]);
+    iter.next_back();
+    assert_eq!(iter.as_slice(), &[2]);
+    assert_eq!(iter.as_mut_slice(), &[2]);
+}
+
+#[test]
+fn test_into_iter_clone() {
+    // Test that the cloned iterator yields identical elements and that it owns its own copy
+    // (i.e. no use after move errors).
+    let mut iter = SmallVec::<[u8; 2]>::from_iter(0..3).into_iter();
+    let mut clone_iter = iter.clone();
+    while let Some(x) = iter.next() {
+        assert_eq!(x, clone_iter.next().unwrap());
+    }
+    assert_eq!(clone_iter.next(), None);
+}
+
+#[test]
+fn test_into_iter_clone_partially_consumed_iterator() {
+    // Test that the cloned iterator only contains the remaining elements of the original iterator.
+    let mut iter = SmallVec::<[u8; 2]>::from_iter(0..3).into_iter().skip(1);
+    let mut clone_iter = iter.clone();
+    while let Some(x) = iter.next() {
+        assert_eq!(x, clone_iter.next().unwrap());
+    }
+    assert_eq!(clone_iter.next(), None);
+}
+
+#[test]
+fn test_into_iter_clone_empty_smallvec() {
+    let mut iter = SmallVec::<[u8; 2]>::new().into_iter();
+    let mut clone_iter = iter.clone();
+    assert_eq!(iter.next(), None);
+    assert_eq!(clone_iter.next(), None);
+}
+
+#[test]
+fn shrink_to_fit_unspill() {
+    let mut vec = SmallVec::<[u8; 2]>::from_iter(0..3);
+    vec.pop();
+    assert!(vec.spilled());
+    vec.shrink_to_fit();
+    assert!(!vec.spilled(), "shrink_to_fit will un-spill if possible");
+}
+
+#[test]
+fn test_into_vec() {
+    let vec = SmallVec::<[u8; 2]>::from_iter(0..2);
+    assert_eq!(vec.into_vec(), vec![0, 1]);
+
+    let vec = SmallVec::<[u8; 2]>::from_iter(0..3);
+    assert_eq!(vec.into_vec(), vec![0, 1, 2]);
+}
+
+#[test]
+fn test_into_inner() {
+    let vec = SmallVec::<[u8; 2]>::from_iter(0..2);
+    assert_eq!(vec.into_inner(), Ok([0, 1]));
+
+    let vec = SmallVec::<[u8; 2]>::from_iter(0..1);
+    assert_eq!(vec.clone().into_inner(), Err(vec));
+
+    let vec = SmallVec::<[u8; 2]>::from_iter(0..3);
+    assert_eq!(vec.clone().into_inner(), Err(vec));
+}
+
+#[test]
+fn test_from_vec() {
+    let vec = vec![];
+    let small_vec: SmallVec<[u8; 3]> = SmallVec::from_vec(vec);
+    assert_eq!(&*small_vec, &[]);
+    drop(small_vec);
+
+    let vec = vec![];
+    let small_vec: SmallVec<[u8; 1]> = SmallVec::from_vec(vec);
+    assert_eq!(&*small_vec, &[]);
+    drop(small_vec);
+
+    let vec = vec![1];
+    let small_vec: SmallVec<[u8; 3]> = SmallVec::from_vec(vec);
+    assert_eq!(&*small_vec, &[1]);
+    drop(small_vec);
+
+    let vec = vec![1, 2, 3];
+    let small_vec: SmallVec<[u8; 3]> = SmallVec::from_vec(vec);
+    assert_eq!(&*small_vec, &[1, 2, 3]);
+    drop(small_vec);
+
+    let vec = vec![1, 2, 3, 4, 5];
+    let small_vec: SmallVec<[u8; 3]> = SmallVec::from_vec(vec);
+    assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
+    drop(small_vec);
+
+    let vec = vec![1, 2, 3, 4, 5];
+    let small_vec: SmallVec<[u8; 1]> = SmallVec::from_vec(vec);
+    assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
+    drop(small_vec);
+}
+
+#[test]
+fn test_retain() {
+    // Test inline data storate
+    let mut sv: SmallVec<[i32; 5]> = SmallVec::from_slice(&[1, 2, 3, 3, 4]);
+    sv.retain(|&mut i| i != 3);
+    assert_eq!(sv.pop(), Some(4));
+    assert_eq!(sv.pop(), Some(2));
+    assert_eq!(sv.pop(), Some(1));
+    assert_eq!(sv.pop(), None);
+
+    // Test spilled data storage
+    let mut sv: SmallVec<[i32; 3]> = SmallVec::from_slice(&[1, 2, 3, 3, 4]);
+    sv.retain(|&mut i| i != 3);
+    assert_eq!(sv.pop(), Some(4));
+    assert_eq!(sv.pop(), Some(2));
+    assert_eq!(sv.pop(), Some(1));
+    assert_eq!(sv.pop(), None);
+
+    // Test that drop implementations are called for inline.
+    let one = Rc::new(1);
+    let mut sv: SmallVec<[Rc<i32>; 3]> = SmallVec::new();
+    sv.push(Rc::clone(&one));
+    assert_eq!(Rc::strong_count(&one), 2);
+    sv.retain(|_| false);
+    assert_eq!(Rc::strong_count(&one), 1);
+
+    // Test that drop implementations are called for spilled data.
+    let mut sv: SmallVec<[Rc<i32>; 1]> = SmallVec::new();
+    sv.push(Rc::clone(&one));
+    sv.push(Rc::new(2));
+    assert_eq!(Rc::strong_count(&one), 2);
+    sv.retain(|_| false);
+    assert_eq!(Rc::strong_count(&one), 1);
+}
+
+#[test]
+fn test_dedup() {
+    let mut dupes: SmallVec<[i32; 5]> = SmallVec::from_slice(&[1, 1, 2, 3, 3]);
+    dupes.dedup();
+    assert_eq!(&*dupes, &[1, 2, 3]);
+
+    let mut empty: SmallVec<[i32; 5]> = SmallVec::new();
+    empty.dedup();
+    assert!(empty.is_empty());
+
+    let mut all_ones: SmallVec<[i32; 5]> = SmallVec::from_slice(&[1, 1, 1, 1, 1]);
+    all_ones.dedup();
+    assert_eq!(all_ones.len(), 1);
+
+    let mut no_dupes: SmallVec<[i32; 5]> = SmallVec::from_slice(&[1, 2, 3, 4, 5]);
+    no_dupes.dedup();
+    assert_eq!(no_dupes.len(), 5);
+}
+
+#[test]
+fn test_resize() {
+    let mut v: SmallVec<[i32; 8]> = SmallVec::new();
+    v.push(1);
+    v.resize(5, 0);
+    assert_eq!(v[..], [1, 0, 0, 0, 0][..]);
+
+    v.resize(2, -1);
+    assert_eq!(v[..], [1, 0][..]);
+}
+
+#[cfg(feature = "write")]
+#[test]
+fn test_write() {
+    use std::io::Write;
+
+    let data = [1, 2, 3, 4, 5];
+
+    let mut small_vec: SmallVec<[u8; 2]> = SmallVec::new();
+    let len = small_vec.write(&data[..]).unwrap();
+    assert_eq!(len, 5);
+    assert_eq!(small_vec.as_ref(), data.as_ref());
+
+    let mut small_vec: SmallVec<[u8; 2]> = SmallVec::new();
+    small_vec.write_all(&data[..]).unwrap();
+    assert_eq!(small_vec.as_ref(), data.as_ref());
+}
+
+#[cfg(feature = "serde")]
+extern crate bincode;
+
+#[cfg(feature = "serde")]
+#[test]
+fn test_serde() {
+    use self::bincode::{config, deserialize};
+    let mut small_vec: SmallVec<[i32; 2]> = SmallVec::new();
+    small_vec.push(1);
+    let encoded = config().limit(100).serialize(&small_vec).unwrap();
+    let decoded: SmallVec<[i32; 2]> = deserialize(&encoded).unwrap();
+    assert_eq!(small_vec, decoded);
+    small_vec.push(2);
+    // Spill the vec
+    small_vec.push(3);
+    small_vec.push(4);
+    // Check again after spilling.
+    let encoded = config().limit(100).serialize(&small_vec).unwrap();
+    let decoded: SmallVec<[i32; 2]> = deserialize(&encoded).unwrap();
+    assert_eq!(small_vec, decoded);
+}
+
+#[test]
+fn grow_to_shrink() {
+    let mut v: SmallVec<[u8; 2]> = SmallVec::new();
+    v.push(1);
+    v.push(2);
+    v.push(3);
+    assert!(v.spilled());
+    v.clear();
+    // Shrink to inline.
+    v.grow(2);
+    assert!(!v.spilled());
+    assert_eq!(v.capacity(), 2);
+    assert_eq!(v.len(), 0);
+    v.push(4);
+    assert_eq!(v[..], [4]);
+}
+
+#[test]
+fn resumable_extend() {
+    let s = "a b c";
+    // This iterator yields: (Some('a'), None, Some('b'), None, Some('c')), None
+    let it = s
+        .chars()
+        .scan(0, |_, ch| if ch.is_whitespace() { None } else { Some(ch) });
+    let mut v: SmallVec<[char; 4]> = SmallVec::new();
+    v.extend(it);
+    assert_eq!(v[..], ['a']);
+}
+
+// #139
+#[test]
+fn uninhabited() {
+    enum Void {}
+    let _sv = SmallVec::<[Void; 8]>::new();
+}
+
+#[test]
+fn grow_spilled_same_size() {
+    let mut v: SmallVec<[u8; 2]> = SmallVec::new();
+    v.push(0);
+    v.push(1);
+    v.push(2);
+    assert!(v.spilled());
+    assert_eq!(v.capacity(), 4);
+    // grow with the same capacity
+    v.grow(4);
+    assert_eq!(v.capacity(), 4);
+    assert_eq!(v[..], [0, 1, 2]);
+}
+
+#[cfg(feature = "const_generics")]
+#[test]
+fn const_generics() {
+    let _v = SmallVec::<[i32; 987]>::default();
+}
+
+#[test]
+fn empty_macro() {
+    let _v: SmallVec<[u8; 1]> = smallvec![];
+}
+
+#[test]
+fn zero_size_items() {
+    SmallVec::<[(); 0]>::new().push(());
+}