Merge "Upgrade rust/crates/smallvec to 1.4.2"
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 @@
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 @@
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 @@
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 @@
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 @@
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
similarity index 69%
rename from lib.rs
rename to 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 @@
#[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::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 @@
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 @@
/// 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 @@
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 @@
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 @@
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 @@
/// 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 @@
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 @@
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
similarity index 100%
rename from specialization.rs
rename to 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(());
+}
