diff options
author | Treehugger Robot <treehugger-gerrit@google.com> | 2020-09-29 15:59:07 +0000 |
---|---|---|
committer | Gerrit Code Review <noreply-gerritcodereview@google.com> | 2020-09-29 15:59:07 +0000 |
commit | 5237030d92994002c7adc200089887593fcf2b4b (patch) | |
tree | 016def8e169faec1a21e319a82de77ec852c2ccd | |
parent | 5986c40c21100f7fe0f624ea3969fe2b5dedba7d (diff) | |
parent | b9330f0c56e6a7994bd421b0b722496b28b7bd89 (diff) | |
download | smallvec-5237030d92994002c7adc200089887593fcf2b4b.tar.gz |
Merge "Upgrade rust/crates/smallvec to 1.4.2"platform-tools-30.0.5
-rw-r--r-- | .cargo_vcs_info.json | 2 | ||||
-rw-r--r-- | .travis.yml | 39 | ||||
-rw-r--r-- | Android.bp | 2 | ||||
-rw-r--r-- | Cargo.toml | 8 | ||||
-rw-r--r-- | Cargo.toml.orig | 8 | ||||
-rw-r--r-- | METADATA | 6 | ||||
-rw-r--r-- | src/lib.rs (renamed from lib.rs) | 938 | ||||
-rw-r--r-- | src/specialization.rs (renamed from specialization.rs) | 0 | ||||
-rw-r--r-- | src/tests.rs | 907 |
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 @@ -4,6 +4,6 @@ rust_library { name: "libsmallvec", host_supported: true, crate_name: "smallvec", - srcs: ["lib.rs"], + srcs: ["src/lib.rs"], edition: "2018", } @@ -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 } @@ -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 } } @@ -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(()); +} |