From 8f2129788afc336eaee3610f16ec698e1c869d01 Mon Sep 17 00:00:00 2001 From: David LeGare Date: Wed, 2 Mar 2022 16:21:23 +0000 Subject: Update smallvec to 1.8.0 Test: cd external/rust/crates && atest --host -c Change-Id: I2a9bbf3cbe9a9458f13552e4c09e33f231a96b57 --- .cargo_vcs_info.json | 2 +- .github/workflows/main.yml | 83 +++++++++++++++++++++++++++ .travis.yml | 37 ------------ Android.bp | 2 +- Cargo.toml | 19 +++++-- Cargo.toml.orig | 8 ++- METADATA | 10 ++-- benches/bench.rs | 11 ++-- src/arbitrary.rs | 19 +++++++ src/lib.rs | 138 ++++++++++++++++++++++++++++++++++++++++++--- src/tests.rs | 65 +++++++++++++++++++++ 11 files changed, 329 insertions(+), 65 deletions(-) create mode 100644 .github/workflows/main.yml delete mode 100644 .travis.yml create mode 100644 src/arbitrary.rs diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json index 9ef75e5..aa1c5bb 100644 --- a/.cargo_vcs_info.json +++ b/.cargo_vcs_info.json @@ -1,5 +1,5 @@ { "git": { - "sha1": "4e53e072808815ed6b847c77193c568ee076c29d" + "sha1": "0a4fdff3b012ed4d4b603800bf971239e5a966ba" } } diff --git a/.github/workflows/main.yml b/.github/workflows/main.yml new file mode 100644 index 0000000..6baaaea --- /dev/null +++ b/.github/workflows/main.yml @@ -0,0 +1,83 @@ +name: CI + +on: + push: + branches: [auto] + pull_request: + workflow_dispatch: + +jobs: + linux-ci: + name: Linux + runs-on: ubuntu-latest + strategy: + matrix: + toolchain: ["stable", "beta", "nightly", "1.36.0"] + include: + - toolchain: stable + env: + DO_FUZZ: 1 + - toolchain: beta + env: + DO_FUZZ: 1 + steps: + - uses: actions/checkout@v2 + + - name: Install packages + run: sudo apt-get install -y binutils-dev libunwind8-dev libcurl4-openssl-dev libelf-dev libdw-dev cmake gcc libiberty-dev + + - name: Install toolchain + uses: actions-rs/toolchain@v1 + with: + profile: minimal + toolchain: ${{ matrix.toolchain }} + override: true + + - name: Cargo build + run: cargo build --verbose + + - name: Cargo test + run: cargo test --verbose + + - name: Cargo test w/ serde + run: cargo test --verbose --features serde + + - name: Cargo check w/o default features + if: matrix.toolchain == 'nightly' + run: cargo check --verbose --no-default-features + + - name: Cargo test w/ union + if: matrix.toolchain == 'beta' + run: cargo test --verbose --features union + + - name: Cargo test all features + if: matrix.toolchain == 'nightly' + run: cargo test --verbose --all-features + + - name: Cargo bench + if: matrix.toolchain == 'nightly' + run: cargo bench --verbose bench + + - name: miri + if: matrix.toolchain == 'nightly' + run: bash ./scripts/run_miri.sh + + - name: fuzz + if: env.DO_FUZZ == '1' + working-directory: fuzz + run: ./travis_fuzz.sh + + build_result: + name: homu build finished + runs-on: ubuntu-latest + needs: + - "linux-ci" + + steps: + - name: Mark the job as successful + run: exit 0 + if: success() + - name: Mark the job as unsuccessful + run: exit 1 + if: "!success()" + diff --git a/.travis.yml b/.travis.yml deleted file mode 100644 index 32fba28..0000000 --- a/.travis.yml +++ /dev/null @@ -1,37 +0,0 @@ -language: rust -addons: - apt: - update: true - packages: - - binutils-dev - - libunwind8-dev - - libcurl4-openssl-dev - - libelf-dev - - libdw-dev - - cmake - - gcc - - libiberty-dev -matrix: - include: - - rust: 1.36.0 - - rust: nightly - - rust: beta - 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 != beta ] || cargo test --verbose --features union) && - ([ $TRAVIS_RUST_VERSION != nightly ] || cargo test --verbose --all-features) && - ([ $TRAVIS_RUST_VERSION != nightly ] || cargo bench --verbose bench) && - ([ $TRAVIS_RUST_VERSION != nightly ] || bash ./scripts/run_miri.sh) && - if [ "$DO_FUZZ" = true ] - then - ( - cd fuzz - ./travis-fuzz.sh - ) - fi diff --git a/Android.bp b/Android.bp index f7fbc23..b82f929 100644 --- a/Android.bp +++ b/Android.bp @@ -42,7 +42,7 @@ rust_library { host_supported: true, crate_name: "smallvec", cargo_env_compat: true, - cargo_pkg_version: "1.6.1", + cargo_pkg_version: "1.8.0", srcs: ["src/lib.rs"], edition: "2018", apex_available: [ diff --git a/Cargo.toml b/Cargo.toml index 1759894..7ff65de 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -3,17 +3,16 @@ # When uploading crates to the registry Cargo will automatically # "normalize" Cargo.toml files for maximal compatibility # with all versions of Cargo and also rewrite `path` dependencies -# to registry (e.g., crates.io) dependencies +# to registry (e.g., crates.io) dependencies. # -# If you believe there's an error in this file please file an -# issue against the rust-lang/cargo repository. If you're -# editing this file be aware that the upstream Cargo.toml -# will likely look very different (and much more reasonable) +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. [package] edition = "2018" name = "smallvec" -version = "1.6.1" +version = "1.8.0" 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/" @@ -22,6 +21,13 @@ keywords = ["small", "vec", "vector", "stack", "no_std"] categories = ["data-structures"] license = "MIT/Apache-2.0" repository = "https://github.com/servo/rust-smallvec" +[package.metadata.docs.rs] +all-features = true +rustdoc-args = ["--cfg", "docsrs"] +[dependencies.arbitrary] +version = "1" +optional = true + [dependencies.serde] version = "1" optional = true @@ -31,6 +37,7 @@ version = "1.0.1" [features] const_generics = [] +const_new = ["const_generics"] may_dangle = [] specialization = [] union = [] diff --git a/Cargo.toml.orig b/Cargo.toml.orig index b19b93e..605fdb3 100644 --- a/Cargo.toml.orig +++ b/Cargo.toml.orig @@ -1,6 +1,6 @@ [package] name = "smallvec" -version = "1.6.1" +version = "1.8.0" edition = "2018" authors = ["The Servo Project Developers"] license = "MIT/Apache-2.0" @@ -13,6 +13,7 @@ documentation = "https://docs.rs/smallvec/" [features] const_generics = [] +const_new = ["const_generics"] write = [] union = [] specialization = [] @@ -20,6 +21,11 @@ may_dangle = [] [dependencies] serde = { version = "1", optional = true, default-features = false } +arbitrary = { version = "1", optional = true } [dev_dependencies] bincode = "1.0.1" + +[package.metadata.docs.rs] +all-features = true +rustdoc-args = ["--cfg", "docsrs"] diff --git a/METADATA b/METADATA index 3ff6a4b..e726d44 100644 --- a/METADATA +++ b/METADATA @@ -7,13 +7,13 @@ third_party { } url { type: ARCHIVE - value: "https://static.crates.io/crates/smallvec/smallvec-1.6.1.crate" + value: "https://static.crates.io/crates/smallvec/smallvec-1.8.0.crate" } - version: "1.6.1" + version: "1.8.0" license_type: NOTICE last_upgrade_date { - year: 2021 - month: 1 - day: 8 + year: 2022 + month: 3 + day: 1 } } diff --git a/benches/bench.rs b/benches/bench.rs index 7a3c07e..ad73226 100644 --- a/benches/bench.rs +++ b/benches/bench.rs @@ -159,12 +159,11 @@ fn gen_insert>(n: u64, b: &mut Bencher) { b.iter(|| { let mut vec = V::new(); - // Add one element, with each iteration we insert one before the end. - // This means that we benchmark the insertion operation and not the - // time it takes to `ptr::copy` the data. + // Always insert at position 0 so that we are subject to shifts of + // many different lengths. vec.push(0); for x in 0..n { - insert_noinline(&mut vec, x as _, x); + insert_noinline(&mut vec, 0, x); } vec }); @@ -179,8 +178,8 @@ fn gen_remove>(n: usize, b: &mut Bencher) { b.iter(|| { let mut vec = V::from_elem(0, n as _); - for x in (0..n - 1).rev() { - remove_noinline(&mut vec, x); + for _ in 0..n { + remove_noinline(&mut vec, 0); } }); } diff --git a/src/arbitrary.rs b/src/arbitrary.rs new file mode 100644 index 0000000..cbdfcb0 --- /dev/null +++ b/src/arbitrary.rs @@ -0,0 +1,19 @@ +use crate::{Array, SmallVec}; +use arbitrary::{Arbitrary, Unstructured}; + +impl<'a, A: Array> Arbitrary<'a> for SmallVec +where + ::Item: Arbitrary<'a>, +{ + fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result { + u.arbitrary_iter()?.collect() + } + + fn arbitrary_take_rest(u: Unstructured<'a>) -> arbitrary::Result { + u.arbitrary_take_rest_iter()?.collect() + } + + fn size_hint(depth: usize) -> (usize, Option) { + arbitrary::size_hint::and(::size_hint(depth), (0, None)) + } +} diff --git a/src/lib.rs b/src/lib.rs index 5e9de82..1699a71 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -43,12 +43,18 @@ //! //! ### `const_generics` //! -//! **This feature is unstable and requires a nightly build of the Rust toolchain.** +//! **This feature requires Rust 1.51.** //! //! When this feature is enabled, `SmallVec` works with any arrays of any size, not just a fixed //! list of sizes. //! -//! Tracking issue: [rust-lang/rust#44580](https://github.com/rust-lang/rust/issues/44580) +//! ### `const_new` +//! +//! **This feature requires Rust 1.51.** +//! +//! This feature exposes the functions [`SmallVec::new_const`], [`SmallVec::from_const`], and [`smallvec_inline`] which enables the `SmallVec` to be initialized from a const context. +//! For details, see the +//! [Rust Reference](https://doc.rust-lang.org/reference/const_eval.html#const-functions). //! //! ### `specialization` //! @@ -71,6 +77,7 @@ //! Tracking issue: [rust-lang/rust#34761](https://github.com/rust-lang/rust/issues/34761) #![no_std] +#![cfg_attr(docsrs, feature(doc_cfg))] #![cfg_attr(feature = "specialization", allow(incomplete_features))] #![cfg_attr(feature = "specialization", feature(specialization))] #![cfg_attr(feature = "may_dangle", feature(dropck_eyepatch))] @@ -172,6 +179,52 @@ macro_rules! smallvec { }); } +/// Creates an inline [`SmallVec`] containing the arguments. This macro is enabled by the feature `const_new`. +/// +/// `smallvec_inline!` allows `SmallVec`s to be defined with the same syntax as array expressions in `const` contexts. +/// The inline storage `A` will always be an array of the size specified by the arguments. +/// There are two forms of this macro: +/// +/// - Create a [`SmallVec`] containing a given list of elements: +/// +/// ``` +/// # #[macro_use] extern crate smallvec; +/// # use smallvec::SmallVec; +/// # fn main() { +/// const V: SmallVec<[i32; 3]> = smallvec_inline![1, 2, 3]; +/// assert_eq!(V[0], 1); +/// assert_eq!(V[1], 2); +/// assert_eq!(V[2], 3); +/// # } +/// ``` +/// +/// - Create a [`SmallVec`] from a given element and size: +/// +/// ``` +/// # #[macro_use] extern crate smallvec; +/// # use smallvec::SmallVec; +/// # fn main() { +/// const V: SmallVec<[i32; 3]> = smallvec_inline![1; 3]; +/// assert_eq!(V, SmallVec::from_buf([1, 1, 1])); +/// # } +/// ``` +/// +/// Note that the behavior mimics that of array expressions, in contrast to [`smallvec`]. +#[cfg(feature = "const_new")] +#[cfg_attr(docsrs, doc(cfg(feature = "const_new")))] +#[macro_export] +macro_rules! smallvec_inline { + // count helper: transform any expression into 1 + (@one $x:expr) => (1usize); + ($elem:expr; $n:expr) => ({ + $crate::SmallVec::<[_; $n]>::from_const([$elem; $n]) + }); + ($($x:expr),+ $(,)?) => ({ + const N: usize = 0usize $(+ $crate::smallvec_inline!(@one $x))*; + $crate::SmallVec::<[_; N]>::from_const([$($x,)*]) + }); +} + /// `panic!()` in debug builds, optimization hint in release. #[cfg(not(feature = "union"))] macro_rules! debug_unreachable { @@ -355,6 +408,17 @@ union SmallVecData { heap: (*mut A::Item, usize), } +#[cfg(all(feature = "union", feature = "const_new"))] +impl SmallVecData<[T; N]> { + #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))] + #[inline] + const fn from_const(inline: MaybeUninit<[T; N]>) -> Self { + SmallVecData { + inline: core::mem::ManuallyDrop::new(inline), + } + } +} + #[cfg(feature = "union")] impl SmallVecData { #[inline] @@ -395,6 +459,15 @@ enum SmallVecData { Heap((*mut A::Item, usize)), } +#[cfg(all(not(feature = "union"), feature = "const_new"))] +impl SmallVecData<[T; N]> { + #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))] + #[inline] + const fn from_const(inline: MaybeUninit<[T; N]>) -> Self { + SmallVecData::Inline(inline) + } +} + #[cfg(not(feature = "union"))] impl SmallVecData { #[inline] @@ -483,7 +556,7 @@ impl SmallVec { /// Construct an empty vector #[inline] pub fn new() -> SmallVec { - // Try to detect invalid custom implementations of `Array`. Hopefuly, + // Try to detect invalid custom implementations of `Array`. Hopefully, // this check should be optimized away entirely for valid ones. assert!( mem::size_of::() == A::size() * mem::size_of::() @@ -725,11 +798,11 @@ impl SmallVec { let len = self.len(); let start = match range.start_bound() { Included(&n) => n, - Excluded(&n) => n + 1, + Excluded(&n) => n.checked_add(1).expect("Range start out of bounds"), Unbounded => 0, }; let end = match range.end_bound() { - Included(&n) => n + 1, + Included(&n) => n.checked_add(1).expect("Range end out of bounds"), Excluded(&n) => n, Unbounded => len, }; @@ -1489,6 +1562,7 @@ impl BorrowMut<[A::Item]> for SmallVec { } #[cfg(feature = "write")] +#[cfg_attr(docsrs, doc(cfg(feature = "write")))] impl> io::Write for SmallVec { #[inline] fn write(&mut self, buf: &[u8]) -> io::Result { @@ -1509,6 +1583,7 @@ impl> io::Write for SmallVec { } #[cfg(feature = "serde")] +#[cfg_attr(docsrs, doc(cfg(feature = "serde")))] impl Serialize for SmallVec where A::Item: Serialize, @@ -1523,6 +1598,7 @@ where } #[cfg(feature = "serde")] +#[cfg_attr(docsrs, doc(cfg(feature = "serde")))] impl<'de, A: Array> Deserialize<'de> for SmallVec where A::Item: Deserialize<'de>, @@ -1575,6 +1651,9 @@ trait SpecFrom { #[cfg(feature = "specialization")] mod specialization; +#[cfg(feature = "arbitrary")] +mod arbitrary; + #[cfg(feature = "specialization")] impl<'a, A: Array> SpecFrom for SmallVec where @@ -1727,6 +1806,21 @@ where fn clone(&self) -> SmallVec { SmallVec::from(self.as_slice()) } + + fn clone_from(&mut self, source: &Self) { + // Inspired from `impl Clone for Vec`. + + // drop anything that will not be overwritten + self.truncate(source.len()); + + // self.len <= other.len due to the truncate above, so the + // slices here are always in-bounds. + let (init, tail) = source.split_at(self.len()); + + // reuse the contained values' allocations/resources. + self.clone_from_slice(init); + self.extend(tail.iter().cloned()); + } } impl PartialEq> for SmallVec @@ -1937,7 +2031,35 @@ impl<'a> Drop for SetLenOnDrop<'a> { } } -#[cfg(feature = "const_generics")] +#[cfg(feature = "const_new")] +impl SmallVec<[T; N]> { + /// Construct an empty vector. + /// + /// This is a `const` version of [`SmallVec::new`] that is enabled by the feature `const_new`, with the limitation that it only works for arrays. + #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))] + #[inline] + pub const fn new_const() -> Self { + SmallVec { + capacity: 0, + data: SmallVecData::from_const(MaybeUninit::uninit()), + } + } + + /// The array passed as an argument is moved to be an inline version of `SmallVec`. + /// + /// This is a `const` version of [`SmallVec::from_buf`] that is enabled by the feature `const_new`, with the limitation that it only works for arrays. + #[cfg_attr(docsrs, doc(cfg(feature = "const_new")))] + #[inline] + pub const fn from_const(items: [T; N]) -> Self { + SmallVec { + capacity: N, + data: SmallVecData::from_const(MaybeUninit::new(items)), + } + } +} + +#[cfg(all(feature = "const_generics", not(doc)))] +#[cfg_attr(docsrs, doc(cfg(feature = "const_generics")))] unsafe impl Array for [T; N] { type Item = T; fn size() -> usize { @@ -1945,7 +2067,7 @@ unsafe impl Array for [T; N] { } } -#[cfg(not(feature = "const_generics"))] +#[cfg(any(not(feature = "const_generics"), doc))] macro_rules! impl_array( ($($size:expr),+) => { $( @@ -1957,7 +2079,7 @@ macro_rules! impl_array( } ); -#[cfg(not(feature = "const_generics"))] +#[cfg(any(not(feature = "const_generics"), doc))] impl_array!( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 36, 0x40, 0x60, 0x80, 0x100, 0x200, 0x400, 0x600, 0x800, 0x1000, diff --git a/src/tests.rs b/src/tests.rs index 19f6da8..7643fd7 100644 --- a/src/tests.rs +++ b/src/tests.rs @@ -111,6 +111,13 @@ fn drain() { assert_eq!(v.drain(1..).collect::>(), &[4, 5]); // drain should not change the capacity assert_eq!(v.capacity(), old_capacity); + + // Exercise the tail-shifting code when in the inline state + // This has the potential to produce UB due to aliasing + let mut v: SmallVec<[u8; 2]> = SmallVec::new(); + v.push(1); + v.push(2); + assert_eq!(v.drain(..1).collect::>(), &[1]); } #[test] @@ -423,6 +430,13 @@ fn test_invalid_grow() { v.grow(5); } +#[test] +#[should_panic] +fn drain_overflow() { + let mut v: SmallVec<[u8; 8]> = smallvec![0]; + v.drain(..=std::usize::MAX); +} + #[test] fn test_insert_from_slice() { let mut v: SmallVec<[u8; 8]> = SmallVec::new(); @@ -896,6 +910,35 @@ fn const_generics() { let _v = SmallVec::<[i32; 987]>::default(); } +#[cfg(feature = "const_new")] +#[test] +fn const_new() { + let v = const_new_inner(); + assert_eq!(v.capacity(), 4); + assert_eq!(v.len(), 0); + let v = const_new_inline_sized(); + assert_eq!(v.capacity(), 4); + assert_eq!(v.len(), 4); + assert_eq!(v[0], 1); + let v = const_new_inline_args(); + assert_eq!(v.capacity(), 2); + assert_eq!(v.len(), 2); + assert_eq!(v[0], 1); + assert_eq!(v[1], 4); +} +#[cfg(feature = "const_new")] +const fn const_new_inner() -> SmallVec<[i32; 4]> { + SmallVec::<[i32; 4]>::new_const() +} +#[cfg(feature = "const_new")] +const fn const_new_inline_sized() -> SmallVec<[i32; 4]> { + crate::smallvec_inline![1; 4] +} +#[cfg(feature = "const_new")] +const fn const_new_inline_args() -> SmallVec<[i32; 2]> { + crate::smallvec_inline![1, 4] +} + #[test] fn empty_macro() { let _v: SmallVec<[u8; 1]> = smallvec![]; @@ -918,3 +961,25 @@ fn test_insert_many_overflow() { v.insert_many(0, iter); assert_eq!(&*v, &[0, 2, 4, 123]); } + +#[test] +fn test_clone_from() { + let mut a: SmallVec<[u8; 2]> = SmallVec::new(); + a.push(1); + a.push(2); + a.push(3); + + let mut b: SmallVec<[u8; 2]> = SmallVec::new(); + b.push(10); + + let mut c: SmallVec<[u8; 2]> = SmallVec::new(); + c.push(20); + c.push(21); + c.push(22); + + a.clone_from(&b); + assert_eq!(&*a, &[10]); + + b.clone_from(&c); + assert_eq!(&*b, &[20, 21, 22]); +} -- cgit v1.2.3 From 88f8ef87938627ae9f20f33f131c3c7b79dc458a Mon Sep 17 00:00:00 2001 From: David LeGare Date: Wed, 2 Mar 2022 19:54:35 +0000 Subject: Update TEST_MAPPING Test: cd external/rust/crates && atest --host -c Change-Id: Ib48a7fe57c6a644e1a44c3d697146c3fec568edd --- TEST_MAPPING | 3 +++ 1 file changed, 3 insertions(+) diff --git a/TEST_MAPPING b/TEST_MAPPING index 713deb2..b91be4d 100644 --- a/TEST_MAPPING +++ b/TEST_MAPPING @@ -4,6 +4,9 @@ { "path": "external/rust/crates/parking_lot_core" }, + { + "path": "external/rust/crates/tinyvec" + }, { "path": "external/rust/crates/vulkano" } -- cgit v1.2.3