From db74ff043cee132bb36db7affc0aad69efc76a70 Mon Sep 17 00:00:00 2001 From: Jeff Vander Stoep Date: Mon, 6 Feb 2023 09:06:35 +0100 Subject: Upgrade smallvec to 1.10.0 This project was upgraded with external_updater. Usage: tools/external_updater/updater.sh update rust/crates/smallvec For more info, check https://cs.android.com/android/platform/superproject/+/master:tools/external_updater/README.md Test: TreeHugger Change-Id: I8fa5daa13515be93b49312868a697ccb190b01a8 --- .cargo_vcs_info.json | 7 +-- .github/workflows/main.yml | 28 +++++++++-- Android.bp | 2 +- Cargo.toml | 33 ++++++++++-- Cargo.toml.orig | 21 +++++++- METADATA | 14 ++++-- benches/bench.rs | 19 +++++++ debug_metadata/README.md | 111 +++++++++++++++++++++++++++++++++++++++++ debug_metadata/smallvec.natvis | 35 +++++++++++++ scripts/run_miri.sh | 3 ++ src/lib.rs | 45 ++++++++++++++--- tests/debugger_visualizer.rs | 68 +++++++++++++++++++++++++ 12 files changed, 358 insertions(+), 28 deletions(-) create mode 100644 debug_metadata/README.md create mode 100644 debug_metadata/smallvec.natvis create mode 100644 tests/debugger_visualizer.rs diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json index aa1c5bb..5d6626b 100644 --- a/.cargo_vcs_info.json +++ b/.cargo_vcs_info.json @@ -1,5 +1,6 @@ { "git": { - "sha1": "0a4fdff3b012ed4d4b603800bf971239e5a966ba" - } -} + "sha1": "3c77a35df6df29a1c516a59f1d04738432edf57f" + }, + "path_in_vcs": "" +} \ No newline at end of file diff --git a/.github/workflows/main.yml b/.github/workflows/main.yml index 6baaaea..467bf1f 100644 --- a/.github/workflows/main.yml +++ b/.github/workflows/main.yml @@ -7,12 +7,12 @@ on: workflow_dispatch: jobs: - linux-ci: - name: Linux - runs-on: ubuntu-latest + ci: + name: Build/Test strategy: matrix: toolchain: ["stable", "beta", "nightly", "1.36.0"] + os: [ubuntu-latest] include: - toolchain: stable env: @@ -20,10 +20,16 @@ jobs: - toolchain: beta env: DO_FUZZ: 1 + - os: windows-latest + toolchain: nightly + + runs-on: ${{ matrix.os }} + steps: - uses: actions/checkout@v2 - name: Install packages + if: matrix.os == 'ubuntu-latest' run: sudo apt-get install -y binutils-dev libunwind8-dev libcurl4-openssl-dev libelf-dev libdw-dev cmake gcc libiberty-dev - name: Install toolchain @@ -37,9 +43,11 @@ jobs: run: cargo build --verbose - name: Cargo test + if: matrix.toolchain != '1.36.0' run: cargo test --verbose - name: Cargo test w/ serde + if: matrix.toolchain != '1.36.0' run: cargo test --verbose --features serde - name: Cargo check w/o default features @@ -50,6 +58,14 @@ jobs: if: matrix.toolchain == 'beta' run: cargo test --verbose --features union + - name: Cargo test w/ debugger_visualizer + if: matrix.toolchain == 'nightly' + run: cargo test --test debugger_visualizer --verbose --features debugger_visualizer -- --test-threads=1 + + - name: Cargo test w/ debugger_visualizer and union + if: matrix.toolchain == 'nightly' + run: cargo test --test debugger_visualizer --verbose --features 'debugger_visualizer,union' -- --test-threads=1 + - name: Cargo test all features if: matrix.toolchain == 'nightly' run: cargo test --verbose --all-features @@ -59,8 +75,10 @@ jobs: run: cargo bench --verbose bench - name: miri - if: matrix.toolchain == 'nightly' + if: matrix.toolchain == 'nightly' && matrix.os == 'ubuntu-latest' run: bash ./scripts/run_miri.sh + env: + MIRIFLAGS: '-Zmiri-tag-raw-pointers' - name: fuzz if: env.DO_FUZZ == '1' @@ -71,7 +89,7 @@ jobs: name: homu build finished runs-on: ubuntu-latest needs: - - "linux-ci" + - "ci" steps: - name: Mark the job as successful diff --git a/Android.bp b/Android.bp index c86cf0e..d13eba1 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.8.0", + cargo_pkg_version: "1.10.0", srcs: ["src/lib.rs"], edition: "2018", apex_available: [ diff --git a/Cargo.toml b/Cargo.toml index 7ff65de..a365ca1 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -12,18 +12,35 @@ [package] edition = "2018" name = "smallvec" -version = "1.8.0" +version = "1.10.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/" readme = "README.md" -keywords = ["small", "vec", "vector", "stack", "no_std"] +keywords = [ + "small", + "vec", + "vector", + "stack", + "no_std", +] categories = ["data-structures"] -license = "MIT/Apache-2.0" +license = "MIT OR Apache-2.0" repository = "https://github.com/servo/rust-smallvec" + [package.metadata.docs.rs] all-features = true -rustdoc-args = ["--cfg", "docsrs"] +rustdoc-args = [ + "--cfg", + "docsrs", +] + +[[test]] +name = "debugger_visualizer" +path = "tests/debugger_visualizer.rs" +test = false +required-features = ["debugger_visualizer"] + [dependencies.arbitrary] version = "1" optional = true @@ -32,12 +49,20 @@ optional = true version = "1" optional = true default-features = false + [dev-dependencies.bincode] version = "1.0.1" +[dev-dependencies.debugger_test] +version = "0.1.0" + +[dev-dependencies.debugger_test_parser] +version = "0.1.0" + [features] const_generics = [] const_new = ["const_generics"] +debugger_visualizer = [] may_dangle = [] specialization = [] union = [] diff --git a/Cargo.toml.orig b/Cargo.toml.orig index 605fdb3..90209b7 100644 --- a/Cargo.toml.orig +++ b/Cargo.toml.orig @@ -1,9 +1,9 @@ [package] name = "smallvec" -version = "1.8.0" +version = "1.10.0" edition = "2018" authors = ["The Servo Project Developers"] -license = "MIT/Apache-2.0" +license = "MIT OR 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" keywords = ["small", "vec", "vector", "stack", "no_std"] @@ -19,13 +19,30 @@ union = [] specialization = [] may_dangle = [] +# UNSTABLE FEATURES (requires Rust nightly) +# Enable to use the #[debugger_visualizer] attribute. +debugger_visualizer = [] + [dependencies] serde = { version = "1", optional = true, default-features = false } arbitrary = { version = "1", optional = true } [dev_dependencies] bincode = "1.0.1" +debugger_test = "0.1.0" +debugger_test_parser = "0.1.0" [package.metadata.docs.rs] all-features = true rustdoc-args = ["--cfg", "docsrs"] + +[[test]] +name = "debugger_visualizer" +path = "tests/debugger_visualizer.rs" +required-features = ["debugger_visualizer"] +# Do not run these tests by default. These tests need to +# be run with the additional rustc flag `--test-threads=1` +# since each test causes a debugger to attach to the current +# test process. If multiple debuggers try to attach at the same +# time, the test will fail. +test = false diff --git a/METADATA b/METADATA index e726d44..3a50c0d 100644 --- a/METADATA +++ b/METADATA @@ -1,3 +1,7 @@ +# This project was upgraded with external_updater. +# Usage: tools/external_updater/updater.sh update rust/crates/smallvec +# For more info, check https://cs.android.com/android/platform/superproject/+/master:tools/external_updater/README.md + name: "smallvec" description: "\'Small vector\' optimization: store up to a small number of items on the stack" third_party { @@ -7,13 +11,13 @@ third_party { } url { type: ARCHIVE - value: "https://static.crates.io/crates/smallvec/smallvec-1.8.0.crate" + value: "https://static.crates.io/crates/smallvec/smallvec-1.10.0.crate" } - version: "1.8.0" + version: "1.10.0" license_type: NOTICE last_upgrade_date { - year: 2022 - month: 3 - day: 1 + year: 2023 + month: 2 + day: 6 } } diff --git a/benches/bench.rs b/benches/bench.rs index ad73226..b52ee15 100644 --- a/benches/bench.rs +++ b/benches/bench.rs @@ -96,6 +96,8 @@ make_benches! { SmallVec<[u64; VEC_SIZE]> { bench_push => gen_push(SPILLED_SIZE as _), bench_push_small => gen_push(VEC_SIZE as _), + bench_insert_push => gen_insert_push(SPILLED_SIZE as _), + bench_insert_push_small => gen_insert_push(VEC_SIZE as _), bench_insert => gen_insert(SPILLED_SIZE as _), bench_insert_small => gen_insert(VEC_SIZE as _), bench_remove => gen_remove(SPILLED_SIZE as _), @@ -118,6 +120,8 @@ make_benches! { Vec { bench_push_vec => gen_push(SPILLED_SIZE as _), bench_push_vec_small => gen_push(VEC_SIZE as _), + bench_insert_push_vec => gen_insert_push(SPILLED_SIZE as _), + bench_insert_push_vec_small => gen_insert_push(VEC_SIZE as _), bench_insert_vec => gen_insert(SPILLED_SIZE as _), bench_insert_vec_small => gen_insert(VEC_SIZE as _), bench_remove_vec => gen_remove(SPILLED_SIZE as _), @@ -151,6 +155,21 @@ fn gen_push>(n: u64, b: &mut Bencher) { }); } +fn gen_insert_push>(n: u64, b: &mut Bencher) { + #[inline(never)] + fn insert_push_noinline>(vec: &mut V, x: u64) { + vec.insert(x as usize, x); + } + + b.iter(|| { + let mut vec = V::new(); + for x in 0..n { + insert_push_noinline(&mut vec, x); + } + vec + }); +} + fn gen_insert>(n: u64, b: &mut Bencher) { #[inline(never)] fn insert_noinline>(vec: &mut V, p: usize, x: u64) { diff --git a/debug_metadata/README.md b/debug_metadata/README.md new file mode 100644 index 0000000..1375008 --- /dev/null +++ b/debug_metadata/README.md @@ -0,0 +1,111 @@ +## Debugger Visualizers + +Many languages and debuggers enable developers to control how a type is +displayed in a debugger. These are called "debugger visualizations" or "debugger +views". + +The Windows debuggers (WinDbg\CDB) support defining custom debugger visualizations using +the `Natvis` framework. To use Natvis, developers write XML documents using the natvis +schema that describe how debugger types should be displayed with the `.natvis` extension. +(See: https://docs.microsoft.com/en-us/visualstudio/debugger/create-custom-views-of-native-objects?view=vs-2019) +The Natvis files provide patterns which match type names a description of how to display +those types. + +The Natvis schema can be found either online (See: https://code.visualstudio.com/docs/cpp/natvis#_schema) +or locally at `\Xml\Schemas\1033\natvis.xsd`. + +The GNU debugger (GDB) supports defining custom debugger views using Pretty Printers. +Pretty printers are written as python scripts that describe how a type should be displayed +when loaded up in GDB/LLDB. (See: https://sourceware.org/gdb/onlinedocs/gdb/Pretty-Printing.html#Pretty-Printing) +The pretty printers provide patterns, which match type names, and for matching +types, descibe how to display those types. (For writing a pretty printer, see: https://sourceware.org/gdb/onlinedocs/gdb/Writing-a-Pretty_002dPrinter.html#Writing-a-Pretty_002dPrinter). + +### Embedding Visualizers + +Through the use of the currently unstable `#[debugger_visualizer]` attribute, the `smallvec` +crate can embed debugger visualizers into the crate metadata. + +Currently the two types of visualizers supported are Natvis and Pretty printers. + +For Natvis files, when linking an executable with a crate that includes Natvis files, +the MSVC linker will embed the contents of all Natvis files into the generated `PDB`. + +For pretty printers, the compiler will encode the contents of the pretty printer +in the `.debug_gdb_scripts` section of the `ELF` generated. + +### Testing Visualizers + +The `smallvec` crate supports testing debugger visualizers defined for this crate. The entry point for +these tests are `tests/debugger_visualizer.rs`. These tests are defined using the `debugger_test` and +`debugger_test_parser` crates. The `debugger_test` crate is a proc macro crate which defines a +single proc macro attribute, `#[debugger_test]`. For more detailed information about this crate, +see https://crates.io/crates/debugger_test. The CI pipeline for the `smallvec` crate has been updated +to run the debugger visualizer tests to ensure debugger visualizers do not become broken/stale. + +The `#[debugger_test]` proc macro attribute may only be used on test functions and will run the +function under the debugger specified by the `debugger` meta item. + +This proc macro attribute has 3 required values: + +1. The first required meta item, `debugger`, takes a string value which specifies the debugger to launch. +2. The second required meta item, `commands`, takes a string of new line (`\n`) separated list of debugger +commands to run. +3. The third required meta item, `expected_statements`, takes a string of new line (`\n`) separated list of +statements that must exist in the debugger output. Pattern matching through regular expressions is also +supported by using the `pattern:` prefix for each expected statement. + +#### Example: + +```rust +#[debugger_test( + debugger = "cdb", + commands = "command1\ncommand2\ncommand3", + expected_statements = "statement1\nstatement2\nstatement3")] +fn test() { + +} +``` + +Using a multiline string is also supported, with a single debugger command/expected statement per line: + +```rust +#[debugger_test( + debugger = "cdb", + commands = " +command1 +command2 +command3", + expected_statements = " +statement1 +pattern:statement[0-9]+ +statement3")] +fn test() { + +} +``` + +In the example above, the second expected statement uses pattern matching through a regular expression +by using the `pattern:` prefix. + +#### Testing Locally + +Currently, only Natvis visualizations have been defined for the `smallvec` crate via `debug_metadata/smallvec.natvis`, +which means the `tests/debugger_visualizer.rs` tests need to be run on Windows using the `*-pc-windows-msvc` targets. +To run these tests locally, first ensure the debugging tools for Windows are installed or install them following +the steps listed here, [Debugging Tools for Windows](https://docs.microsoft.com/en-us/windows-hardware/drivers/debugger/). +Once the debugging tools have been installed, the tests can be run in the same manner as they are in the CI +pipeline. + +#### Note + +When running the debugger visualizer tests, `tests/debugger_visualizer.rs`, they need to be run consecutively +and not in parallel. This can be achieved by passing the flag `--test-threads=1` to rustc. This is due to +how the debugger tests are run. Each test marked with the `#[debugger_test]` attribute launches a debugger +and attaches it to the current test process. If tests are running in parallel, the test will try to attach +a debugger to the current process which may already have a debugger attached causing the test to fail. + +For example: + +``` +cargo test --test debugger_visualizer --features debugger_visualizer -- --test-threads=1 +``` diff --git a/debug_metadata/smallvec.natvis b/debug_metadata/smallvec.natvis new file mode 100644 index 0000000..b38d47c --- /dev/null +++ b/debug_metadata/smallvec.natvis @@ -0,0 +1,35 @@ + + + + + + + {{ len={len()} }} + + is_inline() ? $T2 : capacity + len() + + + len() + data_ptr() + + + + + + + + + + {{ len={len()} }} + + is_inline() ? $T2 : capacity + len() + + + len() + data_ptr() + + + + \ No newline at end of file diff --git a/scripts/run_miri.sh b/scripts/run_miri.sh index 817928a..010ceb0 100644 --- a/scripts/run_miri.sh +++ b/scripts/run_miri.sh @@ -11,6 +11,7 @@ cargo clean MIRI_NIGHTLY=nightly-$(curl -s https://rust-lang.github.io/rustup-components-history/x86_64-unknown-linux-gnu/miri) echo "Installing latest nightly with Miri: $MIRI_NIGHTLY" +rustup override unset rustup default "$MIRI_NIGHTLY" rustup component add miri @@ -19,3 +20,5 @@ cargo miri setup cargo miri test --verbose cargo miri test --verbose --features union cargo miri test --verbose --all-features + +rustup override set nightly diff --git a/src/lib.rs b/src/lib.rs index 1699a71..a335ca4 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -81,6 +81,11 @@ #![cfg_attr(feature = "specialization", allow(incomplete_features))] #![cfg_attr(feature = "specialization", feature(specialization))] #![cfg_attr(feature = "may_dangle", feature(dropck_eyepatch))] +#![cfg_attr( + feature = "debugger_visualizer", + feature(debugger_visualizer), + debugger_visualizer(natvis_file = "../debug_metadata/smallvec.natvis") +)] #![deny(missing_docs)] #[doc(hidden)] @@ -392,8 +397,11 @@ impl<'a, T: 'a + Array> Drop for Drain<'a, T> { let start = source_vec.len(); let tail = self.tail_start; if tail != start { - let src = source_vec.as_ptr().add(tail); - let dst = source_vec.as_mut_ptr().add(start); + // as_mut_ptr creates a &mut, invalidating other pointers. + // This pattern avoids calling it with a pointer already present. + let ptr = source_vec.as_mut_ptr(); + let src = ptr.add(tail); + let dst = ptr.add(start); ptr::copy(src, dst, self.tail_len); } source_vec.set_len(start + self.tail_len); @@ -813,13 +821,14 @@ impl SmallVec { unsafe { self.set_len(start); - let range_slice = slice::from_raw_parts_mut(self.as_mut_ptr().add(start), end - start); + let range_slice = slice::from_raw_parts(self.as_ptr().add(start), end - start); Drain { tail_start: end, tail_len: len - end, iter: range_slice.iter(), - vec: NonNull::from(self), + // Since self is a &mut, passing it to a function would invalidate the slice iterator. + vec: NonNull::new_unchecked(self as *mut _), } } } @@ -1064,17 +1073,22 @@ impl SmallVec { /// Insert an element at position `index`, shifting all elements after it to the right. /// - /// Panics if `index` is out of bounds. + /// Panics if `index > len`. pub fn insert(&mut self, index: usize, element: A::Item) { self.reserve(1); unsafe { let (mut ptr, len_ptr, _) = self.triple_mut(); let len = *len_ptr; - assert!(index <= len); - *len_ptr = len + 1; ptr = ptr.add(index); - ptr::copy(ptr, ptr.add(1), len - index); + if index < len { + ptr::copy(ptr, ptr.add(1), len - index); + } else if index == len { + // No elements need shifting. + } else { + panic!("index exceeds length"); + } + *len_ptr = len + 1; ptr::write(ptr, element); } } @@ -1112,6 +1126,10 @@ impl SmallVec { len: old_len + lower_size_bound, }; + // The set_len above invalidates the previous pointers, so we must re-create them. + let start = self.as_mut_ptr(); + let ptr = start.add(index); + while num_added < lower_size_bound { let element = match iter.next() { Some(x) => x, @@ -1219,6 +1237,15 @@ impl SmallVec { self.truncate(len - del); } + /// Retains only the elements specified by the predicate. + /// + /// This method is identical in behaviour to [`retain`]; it is included only + /// to maintain api-compatability with `std::Vec`, where the methods are + /// separate for historical reasons. + pub fn retain_mut bool>(&mut self, f: F) { + self.retain(f) + } + /// Removes consecutive duplicate elements. pub fn dedup(&mut self) where @@ -2062,6 +2089,7 @@ impl SmallVec<[T; N]> { #[cfg_attr(docsrs, doc(cfg(feature = "const_generics")))] unsafe impl Array for [T; N] { type Item = T; + #[inline] fn size() -> usize { N } @@ -2073,6 +2101,7 @@ macro_rules! impl_array( $( unsafe impl Array for [T; $size] { type Item = T; + #[inline] fn size() -> usize { $size } } )+ diff --git a/tests/debugger_visualizer.rs b/tests/debugger_visualizer.rs new file mode 100644 index 0000000..210f539 --- /dev/null +++ b/tests/debugger_visualizer.rs @@ -0,0 +1,68 @@ +use debugger_test::debugger_test; +use smallvec::{smallvec, SmallVec}; + +#[inline(never)] +fn __break() {} + +#[debugger_test( + debugger = "cdb", + commands = r#" +.nvlist +dx sv + +g + +dx sv + +g + +dx sv +"#, + expected_statements = r#" +sv : { len=0x2 } [Type: smallvec::SmallVec >] + [] [Type: smallvec::SmallVec >] + [capacity] : 4 + [len] : 0x2 [Type: unsigned __int64] + [0] : 1 [Type: int] + [1] : 2 [Type: int] + +sv : { len=0x5 } [Type: smallvec::SmallVec >] + [] [Type: smallvec::SmallVec >] + [capacity] : 0x8 [Type: unsigned __int64] + [len] : 0x5 [Type: unsigned __int64] + [0] : 5 [Type: int] + [1] : 2 [Type: int] + [2] : 3 [Type: int] + [3] : 4 [Type: int] + [4] : 5 [Type: int] + +sv : { len=0x5 } [Type: smallvec::SmallVec >] + [] [Type: smallvec::SmallVec >] + [capacity] : 0x8 [Type: unsigned __int64] + [len] : 0x5 [Type: unsigned __int64] + [0] : 2 [Type: int] + [1] : 3 [Type: int] + [2] : 4 [Type: int] + [3] : 5 [Type: int] + [4] : 5 [Type: int] +"# +)] +#[inline(never)] +fn test_debugger_visualizer() { + // This SmallVec can hold up to 4 items on the stack: + let mut sv: SmallVec<[i32; 4]> = smallvec![1, 2]; + __break(); + + // Overfill the SmallVec to move its contents to the heap + for i in 3..6 { + sv.push(i); + } + + // Update the contents of the first value of the SmallVec. + sv[0] = sv[1] + sv[2]; + __break(); + + // Sort the SmallVec in place. + sv.sort(); + __break(); +} -- cgit v1.2.3