diff options
| author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-30 03:57:19 +0000 |
|---|---|---|
| committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-30 03:57:19 +0000 |
| commit | a0b8f38ab54ac451646aa00cd5e91b6c76f22a84 (patch) | |
| tree | fc451898ccaf445814e26b46664d78702178101d /vendor/indexmap | |
| parent | Adding debian version 1.71.1+dfsg1-2. (diff) | |
| download | rustc-a0b8f38ab54ac451646aa00cd5e91b6c76f22a84.tar.xz rustc-a0b8f38ab54ac451646aa00cd5e91b6c76f22a84.zip | |
Merging upstream version 1.72.1+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/indexmap')
26 files changed, 3612 insertions, 2056 deletions
diff --git a/vendor/indexmap/.cargo-checksum.json b/vendor/indexmap/.cargo-checksum.json index 0f44683d7..8b983cd05 100644 --- a/vendor/indexmap/.cargo-checksum.json +++ b/vendor/indexmap/.cargo-checksum.json @@ -1 +1 @@ -{"files":{"Cargo.toml":"1290d383adfdcd24f158a4619afb5547d633c83c0a1ab3b5c1ee0dabe4fb1f36","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"ecc269ef87fd38a1d98e30bfac9ba964a9dbd9315c3770fed98d4d7cb5882055","README.md":"f8b02aa7c20fc0f5bc13de9e9e78899ec8cdbc16c2db880a1d0bc14c25b07542","RELEASES.md":"85d9d9bc78e94df7ce90300bb94099b9ab2696d1b3f6b815c22761522878e679","benches/bench.rs":"3b2900abbc9e8a60af78b0395222ee75e86bc68519a0f38477387d1572eed397","benches/faststring.rs":"5fdd6cdb19d0557ed58f241e809a240cf8939d9e5b87a72d5f127f81ab98380b","build.rs":"558b4d0b9e9b3a44f7e1a2b69f7a7567ea721cd45cb54f4e458e850bf702f35c","src/arbitrary.rs":"bb8bda10f686abe57eef1446d3fc3fc6fb251f95629b28c20e620a4838c43db8","src/equivalent.rs":"2e6ae24ef09a09b917f4e2b0f6288f901878e42f5080f61b1bd1afdcc90aba87","src/lib.rs":"ea2cbe4f6cc2c4a75f42c9fc936503e6bee0f136c60f6811a2a9907ed8886443","src/macros.rs":"80c22f630e7f81e6fa663ca4c9e50cf5f332c8905d72d1338bd16f24eb353c2a","src/map.rs":"2e9cbfa240865cfd6b6b972bdbdb39283e6302dd2d0d72b3c2bfce4414bf5729","src/map/core.rs":"8422cd774c5db7d83cdeb0c5836c10f29caa1bee8d95b0d674b01b32e7ce80d8","src/map/core/raw.rs":"4e5fac4fecccc352268351d8b1f82b345067b5c029bba7e6ab88e8f8bc799c6a","src/mutable_keys.rs":"a919065b59000286eb11c7d46f6896bf0a1d484c9dac5e61d80bb8990c9fbedb","src/rayon/map.rs":"1a508c7c95c5d56113b851f7ce140d62ad541f1c6129352a7ec62d5bea7af4a1","src/rayon/mod.rs":"019e9379ccab57a299ab5b5a2c0efc7561b77a715a5afe8f797c7e8330c6206c","src/rayon/set.rs":"ba00e88e90fb7ab803589f99f24b595d60309e541aae3d01fdde21bff3840194","src/rustc.rs":"fe7a348c5a10a66880cb6c737593fe79d3b6de40f44ba0d7b89204aa95e14a3a","src/serde.rs":"d45ec8fb9c02594ca6f2e9b20764778b2b4193a24a52f1e233160a33efc6e683","src/serde_seq.rs":"c54a52fa607b6ccddda1e76e829778ca304c49b5f434edc5e582a5386c35d662","src/set.rs":"0a57affb623fa6b28df18cc14841e4f076cbd1da5c809635d202f865640af1ee","src/util.rs":"ab712bce71b54cf2763e6010e64bb5944d1d59ce15e2f2beffa7ceed204d6a68","tests/equivalent_trait.rs":"efe9393069e3cfc893d2c9c0343679979578e437fdb98a10baefeced027ba310","tests/macros_full_path.rs":"c33c86d7341581fdd08e2e6375a4afca507fa603540c54a3b9e51c4cd011cd71","tests/quick.rs":"1addbc6cbcb1aae5b8bde0fb0e18197d947e8f13244e4ae7ebf97bdda00eafea","tests/tests.rs":"f6dbeeb0e2950402b0e66ac52bf74c9e4197d3c5d9c0dde64a7998a2ef74d327"},"package":"bd070e393353796e801d209ad339e89596eb4c8d430d18ede6a1cced8fafbd99"}
\ No newline at end of file +{"files":{"Cargo.toml":"22de53b350fe2ece033469dc50c449aed2d48b2e51bd95cd289e5a64281ad941","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"ecc269ef87fd38a1d98e30bfac9ba964a9dbd9315c3770fed98d4d7cb5882055","README.md":"8a6d3b3ddc2b028e309885d80152bea5434dd61c2dc9a64a68daf161fe00233b","RELEASES.md":"6caa90a493de65e6764415168586c647749ad49341f2de807ba70f212f8989b5","benches/bench.rs":"3b2900abbc9e8a60af78b0395222ee75e86bc68519a0f38477387d1572eed397","benches/faststring.rs":"5fdd6cdb19d0557ed58f241e809a240cf8939d9e5b87a72d5f127f81ab98380b","src/arbitrary.rs":"068713b1e8e762dbe9e4d19d555e77c17e59408335a40f4777d6100340605655","src/lib.rs":"f9d5ee25446660e93cbc6de314a8699c1f44da2a56ec3e1b432f61389f77af74","src/macros.rs":"32ab59dfb19713598769252e5fbcef31744dd0399bc839375c4edb5f00701b0d","src/map.rs":"ae2696a0c9746c6694db72d46e34b24d5f91e28d16d024be4d507b56e778ea56","src/map/core.rs":"55ecc1f83ac0b78d687008a057f912be2cfad270af29d1c880dde7b8ad269350","src/map/core/raw.rs":"b0aaa4cf58d789acd056c1d4cca914cd945e3f1f097479298e4432b909ccf9e4","src/map/iter.rs":"23278a1787d08dcbc30885c0653369d82a695a7b8f1084d7709fbf903e53a776","src/map/serde_seq.rs":"eff1ccbefe20c8f4338afa92732473e28fd0b752cb2bc153600ee5387d484627","src/map/slice.rs":"e264c31592ce382830281605846663ecc1694074d5b57b862de9fd090e022fc9","src/map/tests.rs":"7a192e8330a1df604d6a151e854d1d0638c068a8418f8922e92a65868ae5d569","src/mutable_keys.rs":"2bdd739bde1dd7f81c82e90595b877fbdb1cd9f963b180fcc819128bb1c750a7","src/rayon/map.rs":"22a30fa68437f69c24752c8ed17be6e084d02b0c12730e48e238a4e92f208b55","src/rayon/mod.rs":"019e9379ccab57a299ab5b5a2c0efc7561b77a715a5afe8f797c7e8330c6206c","src/rayon/set.rs":"cea2517db405ee64306e24b571ed773e129eae43ecfc866e93e365c118edc0ed","src/rustc.rs":"fe7a348c5a10a66880cb6c737593fe79d3b6de40f44ba0d7b89204aa95e14a3a","src/serde.rs":"91bbf14e3afbcf518aeb7f8a9b65011d0ede2f88d12857dfddda451f35574281","src/set.rs":"e78aa42ea1719f0398c83edd04512b1d7a699eab0578e1f6327a9eec094520ca","src/set/iter.rs":"9b90c736185889fca8b0a461293da4a1a1e50d9db539bd5b9f72254bee461a3e","src/set/slice.rs":"404cf6c749e220d2b29790180edb66b67056a5370f39955175b8f22d01fd21c1","src/set/tests.rs":"81bbb18834603479f26af1a1a6b676fe5ec949e23b2a358fcc868acedc886fa4","src/util.rs":"dbd57cfdac2a72db8c5ce83bf288bcaf33b5ae59adddcd088792a624c4c0e909","tests/equivalent_trait.rs":"efe9393069e3cfc893d2c9c0343679979578e437fdb98a10baefeced027ba310","tests/macros_full_path.rs":"c33c86d7341581fdd08e2e6375a4afca507fa603540c54a3b9e51c4cd011cd71","tests/quick.rs":"f34ae9ce8aa51d9338595c299a2088ab56dbb5c04786050009a2fa22a6bbfa32","tests/tests.rs":"f6dbeeb0e2950402b0e66ac52bf74c9e4197d3c5d9c0dde64a7998a2ef74d327"},"package":"d5477fe2230a79769d8dc68e0eabf5437907c0457a5614a9e8dddb67f65eb65d"}
\ No newline at end of file diff --git a/vendor/indexmap/Cargo.toml b/vendor/indexmap/Cargo.toml index 28f3618f0..d46c15d68 100644 --- a/vendor/indexmap/Cargo.toml +++ b/vendor/indexmap/Cargo.toml @@ -11,9 +11,9 @@ [package] edition = "2021" -rust-version = "1.56" +rust-version = "1.64" name = "indexmap" -version = "1.9.3" +version = "2.0.0" description = "A hash table with consistent order and fast iteration." documentation = "https://docs.rs/indexmap/" readme = "README.md" @@ -28,17 +28,21 @@ categories = [ license = "Apache-2.0 OR MIT" repository = "https://github.com/bluss/indexmap" -[package.metadata.release] -no-dev-version = true -tag-name = "{{version}}" - [package.metadata.docs.rs] features = [ "arbitrary", "quickcheck", - "serde-1", + "serde", "rayon", ] +rustdoc-args = [ + "--cfg", + "docsrs", +] + +[package.metadata.release] +no-dev-version = true +tag-name = "{{version}}" [profile.bench] debug = true @@ -51,8 +55,12 @@ version = "1.0" optional = true default-features = false +[dependencies.equivalent] +version = "1.0" +default-features = false + [dependencies.hashbrown] -version = "0.12" +version = "0.14" features = ["raw"] default-features = false @@ -62,7 +70,7 @@ optional = true default-features = false [dependencies.rayon] -version = "1.4.1" +version = "1.5.3" optional = true [dependencies.rustc-rayon] @@ -98,11 +106,7 @@ features = ["small_rng"] [dev-dependencies.serde_derive] version = "1.0" -[build-dependencies.autocfg] -version = "1" - [features] -serde-1 = ["serde"] +default = ["std"] std = [] test_debug = [] -test_low_transition_point = [] diff --git a/vendor/indexmap/README.md b/vendor/indexmap/README.md index d80b7099c..c87360191 100644 --- a/vendor/indexmap/README.md +++ b/vendor/indexmap/README.md @@ -3,7 +3,7 @@ [](https://github.com/bluss/indexmap/actions) [](https://crates.io/crates/indexmap) [](https://docs.rs/indexmap) -[](https://img.shields.io/badge/rust-1.56%2B-orange.svg) +[](https://img.shields.io/badge/rust-1.64%2B-orange.svg) A pure-Rust hash table which preserves (in a limited sense) insertion order. diff --git a/vendor/indexmap/RELEASES.md b/vendor/indexmap/RELEASES.md index 7ea8b702e..1fe5ad89e 100644 --- a/vendor/indexmap/RELEASES.md +++ b/vendor/indexmap/RELEASES.md @@ -1,3 +1,39 @@ +- 2.0.0 + + - **MSRV**: Rust 1.64.0 or later is now required. + + - The `"std"` feature is no longer auto-detected. It is included in the + default feature set, or else can be enabled like any other Cargo feature. + + - The `"serde-1"` feature has been removed, leaving just the optional + `"serde"` dependency to be enabled like a feature itself. + + - `IndexMap::get_index_mut` now returns `Option<(&K, &mut V)>`, changing + the key part from `&mut K` to `&K`. There is also a new alternative + `MutableKeys::get_index_mut2` to access the former behavior. + + - The new `map::Slice<K, V>` and `set::Slice<T>` offer a linear view of maps + and sets, behaving a lot like normal `[(K, V)]` and `[T]` slices. Notably, + comparison traits like `Eq` only consider items in order, rather than hash + lookups, and slices even implement `Hash`. + + - `IndexMap` and `IndexSet` now have `sort_by_cached_key` and + `par_sort_by_cached_key` methods which perform stable sorts in place + using a key extraction function. + + - `IndexMap` and `IndexSet` now have `reserve_exact`, `try_reserve`, and + `try_reserve_exact` methods that correspond to the same methods on `Vec`. + However, exactness only applies to the direct capacity for items, while the + raw hash table still follows its own rules for capacity and load factor. + + - The `Equivalent` trait is now re-exported from the `equivalent` crate, + intended as a common base to allow types to work with multiple map types. + + - The `hashbrown` dependency has been updated to version 0.14. + + - The `serde_seq` module has been moved from the crate root to below the + `map` module. + - 1.9.3 - Bump the `rustc-rayon` dependency, for compiler use only. diff --git a/vendor/indexmap/build.rs b/vendor/indexmap/build.rs deleted file mode 100644 index 9f9fa054f..000000000 --- a/vendor/indexmap/build.rs +++ /dev/null @@ -1,8 +0,0 @@ -fn main() { - // If "std" is explicitly requested, don't bother probing the target for it. - match std::env::var_os("CARGO_FEATURE_STD") { - Some(_) => autocfg::emit("has_std"), - None => autocfg::new().emit_sysroot_crate("std"), - } - autocfg::rerun_path("build.rs"); -} diff --git a/vendor/indexmap/src/arbitrary.rs b/vendor/indexmap/src/arbitrary.rs index 1347c8b54..7798438c1 100644 --- a/vendor/indexmap/src/arbitrary.rs +++ b/vendor/indexmap/src/arbitrary.rs @@ -1,4 +1,5 @@ #[cfg(feature = "arbitrary")] +#[cfg_attr(docsrs, doc(cfg(feature = "arbitrary")))] mod impl_arbitrary { use crate::{IndexMap, IndexSet}; use arbitrary::{Arbitrary, Result, Unstructured}; @@ -35,6 +36,7 @@ mod impl_arbitrary { } #[cfg(feature = "quickcheck")] +#[cfg_attr(docsrs, doc(cfg(feature = "quickcheck")))] mod impl_quickcheck { use crate::{IndexMap, IndexSet}; use alloc::boxed::Box; diff --git a/vendor/indexmap/src/equivalent.rs b/vendor/indexmap/src/equivalent.rs deleted file mode 100644 index ad6635ffa..000000000 --- a/vendor/indexmap/src/equivalent.rs +++ /dev/null @@ -1,27 +0,0 @@ -use core::borrow::Borrow; - -/// Key equivalence trait. -/// -/// This trait allows hash table lookup to be customized. -/// It has one blanket implementation that uses the regular `Borrow` solution, -/// just like `HashMap` and `BTreeMap` do, so that you can pass `&str` to lookup -/// into a map with `String` keys and so on. -/// -/// # Contract -/// -/// The implementor **must** hash like `K`, if it is hashable. -pub trait Equivalent<K: ?Sized> { - /// Compare self to `key` and return `true` if they are equal. - fn equivalent(&self, key: &K) -> bool; -} - -impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q -where - Q: Eq, - K: Borrow<Q>, -{ - #[inline] - fn equivalent(&self, key: &K) -> bool { - *self == *key.borrow() - } -} diff --git a/vendor/indexmap/src/lib.rs b/vendor/indexmap/src/lib.rs index 6e9493612..8939d261a 100644 --- a/vendor/indexmap/src/lib.rs +++ b/vendor/indexmap/src/lib.rs @@ -14,7 +14,7 @@ //! [`IndexSet`]: set/struct.IndexSet.html //! //! -//! ### Feature Highlights +//! ### Highlights //! //! [`IndexMap`] and [`IndexSet`] are drop-in compatible with the std `HashMap` //! and `HashSet`, but they also have some features of note: @@ -26,6 +26,34 @@ //! - The [`MutableKeys`][map::MutableKeys] trait, which gives opt-in mutable //! access to hash map keys. //! +//! ### Feature Flags +//! +//! To reduce the amount of compiled code in the crate by default, certain +//! features are gated behind [feature flags]. These allow you to opt in to (or +//! out of) functionality. Below is a list of the features available in this +//! crate. +//! +//! * `std`: Enables features which require the Rust standard library. For more +//! information see the section on [`no_std`]. +//! * `rayon`: Enables parallel iteration and other parallel methods. +//! * `serde`: Adds implementations for [`Serialize`] and [`Deserialize`] +//! to [`IndexMap`] and [`IndexSet`]. Alternative implementations for +//! (de)serializing [`IndexMap`] as an ordered sequence are available in the +//! [`map::serde_seq`] module. +//! * `arbitrary`: Adds implementations for the [`arbitrary::Arbitrary`] trait +//! to [`IndexMap`] and [`IndexSet`]. +//! * `quickcheck`: Adds implementations for the [`quickcheck::Arbitrary`] trait +//! to [`IndexMap`] and [`IndexSet`]. +//! +//! _Note: only the `std` feature is enabled by default._ +//! +//! [feature flags]: https://doc.rust-lang.org/cargo/reference/manifest.html#the-features-section +//! [`no_std`]: #no-standard-library-targets +//! [`Serialize`]: `::serde::Serialize` +//! [`Deserialize`]: `::serde::Deserialize` +//! [`arbitrary::Arbitrary`]: `::arbitrary::Arbitrary` +//! [`quickcheck::Arbitrary`]: `::quickcheck::Arbitrary` +//! //! ### Alternate Hashers //! //! [`IndexMap`] and [`IndexSet`] have a default hasher type `S = RandomState`, @@ -53,21 +81,20 @@ //! //! ### Rust Version //! -//! This version of indexmap requires Rust 1.56 or later. +//! This version of indexmap requires Rust 1.64 or later. //! -//! The indexmap 1.x release series will use a carefully considered version -//! upgrade policy, where in a later 1.x version, we will raise the minimum +//! The indexmap 2.x release series will use a carefully considered version +//! upgrade policy, where in a later 2.x version, we will raise the minimum //! required Rust version. //! //! ## No Standard Library Targets //! -//! This crate supports being built without `std`, requiring -//! `alloc` instead. This is enabled automatically when it is detected that -//! `std` is not available. There is no crate feature to enable/disable to -//! trigger this. It can be tested by building for a std-less target. +//! This crate supports being built without `std`, requiring `alloc` instead. +//! This is chosen by disabling the default "std" cargo feature, by adding +//! `default-features = false` to your dependency specification. //! //! - Creating maps and sets using [`new`][IndexMap::new] and -//! [`with_capacity`][IndexMap::with_capacity] is unavailable without `std`. +//! [`with_capacity`][IndexMap::with_capacity] is unavailable without `std`. //! Use methods [`IndexMap::default`][def], //! [`with_hasher`][IndexMap::with_hasher], //! [`with_capacity_and_hasher`][IndexMap::with_capacity_and_hasher] instead. @@ -77,9 +104,11 @@ //! //! [def]: map/struct.IndexMap.html#impl-Default +#![cfg_attr(docsrs, feature(doc_cfg))] + extern crate alloc; -#[cfg(has_std)] +#[cfg(feature = "std")] #[macro_use] extern crate std; @@ -88,12 +117,10 @@ use alloc::vec::{self, Vec}; mod arbitrary; #[macro_use] mod macros; -mod equivalent; mod mutable_keys; #[cfg(feature = "serde")] +#[cfg_attr(docsrs, doc(cfg(feature = "serde")))] mod serde; -#[cfg(feature = "serde")] -pub mod serde_seq; mod util; pub mod map; @@ -102,14 +129,15 @@ pub mod set; // Placed after `map` and `set` so new `rayon` methods on the types // are documented after the "normal" methods. #[cfg(feature = "rayon")] +#[cfg_attr(docsrs, doc(cfg(feature = "rayon")))] mod rayon; #[cfg(feature = "rustc-rayon")] mod rustc; -pub use crate::equivalent::Equivalent; pub use crate::map::IndexMap; pub use crate::set::IndexSet; +pub use equivalent::Equivalent; // shared private items @@ -192,3 +220,59 @@ trait Entries { where F: FnOnce(&mut [Self::Entry]); } + +/// The error type for `try_reserve` methods. +#[derive(Clone, PartialEq, Eq, Debug)] +pub struct TryReserveError { + kind: TryReserveErrorKind, +} + +#[derive(Clone, PartialEq, Eq, Debug)] +enum TryReserveErrorKind { + // The standard library's kind is currently opaque to us, otherwise we could unify this. + Std(alloc::collections::TryReserveError), + CapacityOverflow, + AllocError { layout: alloc::alloc::Layout }, +} + +// These are not `From` so we don't expose them in our public API. +impl TryReserveError { + fn from_alloc(error: alloc::collections::TryReserveError) -> Self { + Self { + kind: TryReserveErrorKind::Std(error), + } + } + + fn from_hashbrown(error: hashbrown::TryReserveError) -> Self { + Self { + kind: match error { + hashbrown::TryReserveError::CapacityOverflow => { + TryReserveErrorKind::CapacityOverflow + } + hashbrown::TryReserveError::AllocError { layout } => { + TryReserveErrorKind::AllocError { layout } + } + }, + } + } +} + +impl core::fmt::Display for TryReserveError { + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { + let reason = match &self.kind { + TryReserveErrorKind::Std(e) => return core::fmt::Display::fmt(e, f), + TryReserveErrorKind::CapacityOverflow => { + " because the computed capacity exceeded the collection's maximum" + } + TryReserveErrorKind::AllocError { .. } => { + " because the memory allocator returned an error" + } + }; + f.write_str("memory allocation failed")?; + f.write_str(reason) + } +} + +#[cfg(feature = "std")] +#[cfg_attr(docsrs, doc(cfg(feature = "std")))] +impl std::error::Error for TryReserveError {} diff --git a/vendor/indexmap/src/macros.rs b/vendor/indexmap/src/macros.rs index ca26287be..5317f1c94 100644 --- a/vendor/indexmap/src/macros.rs +++ b/vendor/indexmap/src/macros.rs @@ -1,4 +1,5 @@ -#[cfg(has_std)] +#[cfg(feature = "std")] +#[cfg_attr(docsrs, doc(cfg(feature = "std")))] #[macro_export] /// Create an `IndexMap` from a list of key-value pairs /// @@ -19,23 +20,23 @@ /// assert_eq!(map.keys().next(), Some(&"a")); /// ``` macro_rules! indexmap { - (@single $($x:tt)*) => (()); - (@count $($rest:expr),*) => (<[()]>::len(&[$($crate::indexmap!(@single $rest)),*])); - ($($key:expr => $value:expr,)+) => { $crate::indexmap!($($key => $value),+) }; ($($key:expr => $value:expr),*) => { { - let _cap = $crate::indexmap!(@count $($key),*); - let mut _map = $crate::IndexMap::with_capacity(_cap); + // Note: `stringify!($key)` is just here to consume the repetition, + // but we throw away that string literal during constant evaluation. + const CAP: usize = <[()]>::len(&[$({ stringify!($key); }),*]); + let mut map = $crate::IndexMap::with_capacity(CAP); $( - _map.insert($key, $value); + map.insert($key, $value); )* - _map + map } }; } -#[cfg(has_std)] +#[cfg(feature = "std")] +#[cfg_attr(docsrs, doc(cfg(feature = "std")))] #[macro_export] /// Create an `IndexSet` from a list of values /// @@ -56,18 +57,17 @@ macro_rules! indexmap { /// assert_eq!(set.iter().next(), Some(&"a")); /// ``` macro_rules! indexset { - (@single $($x:tt)*) => (()); - (@count $($rest:expr),*) => (<[()]>::len(&[$($crate::indexset!(@single $rest)),*])); - ($($value:expr,)+) => { $crate::indexset!($($value),+) }; ($($value:expr),*) => { { - let _cap = $crate::indexset!(@count $($value),*); - let mut _set = $crate::IndexSet::with_capacity(_cap); + // Note: `stringify!($value)` is just here to consume the repetition, + // but we throw away that string literal during constant evaluation. + const CAP: usize = <[()]>::len(&[$({ stringify!($value); }),*]); + let mut set = $crate::IndexSet::with_capacity(CAP); $( - _set.insert($value); + set.insert($value); )* - _set + set } }; } diff --git a/vendor/indexmap/src/map.rs b/vendor/indexmap/src/map.rs index d39448d06..cb405caf4 100644 --- a/vendor/indexmap/src/map.rs +++ b/vendor/indexmap/src/map.rs @@ -2,29 +2,39 @@ //! pairs is independent of the hash values of the keys. mod core; +mod iter; +mod slice; +#[cfg(feature = "serde")] +#[cfg_attr(docsrs, doc(cfg(feature = "serde")))] +pub mod serde_seq; + +#[cfg(test)] +mod tests; + +pub use self::core::{Entry, OccupiedEntry, VacantEntry}; +pub use self::iter::{ + Drain, IntoIter, IntoKeys, IntoValues, Iter, IterMut, Keys, Values, ValuesMut, +}; +pub use self::slice::Slice; pub use crate::mutable_keys::MutableKeys; #[cfg(feature = "rayon")] pub use crate::rayon::map as rayon; -use crate::vec::{self, Vec}; use ::core::cmp::Ordering; use ::core::fmt; use ::core::hash::{BuildHasher, Hash, Hasher}; -use ::core::iter::FusedIterator; use ::core::ops::{Index, IndexMut, RangeBounds}; -use ::core::slice::{Iter as SliceIter, IterMut as SliceIterMut}; +use alloc::boxed::Box; +use alloc::vec::Vec; -#[cfg(has_std)] +#[cfg(feature = "std")] use std::collections::hash_map::RandomState; use self::core::IndexMapCore; -use crate::equivalent::Equivalent; -use crate::util::third; -use crate::{Bucket, Entries, HashValue}; - -pub use self::core::{Entry, OccupiedEntry, VacantEntry}; +use crate::util::{third, try_simplify_range}; +use crate::{Bucket, Entries, Equivalent, HashValue, TryReserveError}; /// A hash table where the iteration order of the key-value pairs is independent /// of the hash values of the keys. @@ -67,12 +77,12 @@ pub use self::core::{Entry, OccupiedEntry, VacantEntry}; /// assert_eq!(letters[&'u'], 1); /// assert_eq!(letters.get(&'y'), None); /// ``` -#[cfg(has_std)] +#[cfg(feature = "std")] pub struct IndexMap<K, V, S = RandomState> { pub(crate) core: IndexMapCore<K, V>, hash_builder: S, } -#[cfg(not(has_std))] +#[cfg(not(feature = "std"))] pub struct IndexMap<K, V, S> { pub(crate) core: IndexMapCore<K, V>, hash_builder: S, @@ -140,7 +150,8 @@ where } } -#[cfg(has_std)] +#[cfg(feature = "std")] +#[cfg_attr(docsrs, doc(cfg(feature = "std")))] impl<K, V> IndexMap<K, V> { /// Create a new map. (Does not allocate.) #[inline] @@ -186,6 +197,11 @@ impl<K, V, S> IndexMap<K, V, S> { } } + /// Return the number of elements the map can hold without reallocating. + /// + /// This number is a lower bound; the map might be able to hold more, + /// but is guaranteed to be able to hold at least this many. + /// /// Computes in **O(1)** time. pub fn capacity(&self) -> usize { self.core.capacity() @@ -214,52 +230,38 @@ impl<K, V, S> IndexMap<K, V, S> { /// Return an iterator over the key-value pairs of the map, in their order pub fn iter(&self) -> Iter<'_, K, V> { - Iter { - iter: self.as_entries().iter(), - } + Iter::new(self.as_entries()) } /// Return an iterator over the key-value pairs of the map, in their order pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { - IterMut { - iter: self.as_entries_mut().iter_mut(), - } + IterMut::new(self.as_entries_mut()) } /// Return an iterator over the keys of the map, in their order pub fn keys(&self) -> Keys<'_, K, V> { - Keys { - iter: self.as_entries().iter(), - } + Keys::new(self.as_entries()) } /// Return an owning iterator over the keys of the map, in their order pub fn into_keys(self) -> IntoKeys<K, V> { - IntoKeys { - iter: self.into_entries().into_iter(), - } + IntoKeys::new(self.into_entries()) } /// Return an iterator over the values of the map, in their order pub fn values(&self) -> Values<'_, K, V> { - Values { - iter: self.as_entries().iter(), - } + Values::new(self.as_entries()) } /// Return an iterator over mutable references to the values of the map, /// in their order pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> { - ValuesMut { - iter: self.as_entries_mut().iter_mut(), - } + ValuesMut::new(self.as_entries_mut()) } /// Return an owning iterator over the values of the map, in their order pub fn into_values(self) -> IntoValues<K, V> { - IntoValues { - iter: self.into_entries().into_iter(), - } + IntoValues::new(self.into_entries()) } /// Remove all key-value pairs in the map, while preserving its capacity. @@ -293,9 +295,7 @@ impl<K, V, S> IndexMap<K, V, S> { where R: RangeBounds<usize>, { - Drain { - iter: self.core.drain(range), - } + Drain::new(self.core.drain(range)) } /// Splits the collection into two at the given index. @@ -328,6 +328,37 @@ where self.core.reserve(additional); } + /// Reserve capacity for `additional` more key-value pairs, without over-allocating. + /// + /// Unlike `reserve`, this does not deliberately over-allocate the entry capacity to avoid + /// frequent re-allocations. However, the underlying data structures may still have internal + /// capacity requirements, and the allocator itself may give more space than requested, so this + /// cannot be relied upon to be precisely minimal. + /// + /// Computes in **O(n)** time. + pub fn reserve_exact(&mut self, additional: usize) { + self.core.reserve_exact(additional); + } + + /// Try to reserve capacity for `additional` more key-value pairs. + /// + /// Computes in **O(n)** time. + pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.core.try_reserve(additional) + } + + /// Try to reserve capacity for `additional` more key-value pairs, without over-allocating. + /// + /// Unlike `try_reserve`, this does not deliberately over-allocate the entry capacity to avoid + /// frequent re-allocations. However, the underlying data structures may still have internal + /// capacity requirements, and the allocator itself may give more space than requested, so this + /// cannot be relied upon to be precisely minimal. + /// + /// Computes in **O(n)** time. + pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.core.try_reserve_exact(additional) + } + /// Shrink the capacity of the map as much as possible. /// /// Computes in **O(n)** time. @@ -486,21 +517,6 @@ where } } - pub(crate) fn get_full_mut2_impl<Q: ?Sized>( - &mut self, - key: &Q, - ) -> Option<(usize, &mut K, &mut V)> - where - Q: Hash + Equivalent<K>, - { - if let Some(i) = self.get_index_of(key) { - let entry = &mut self.as_entries_mut()[i]; - Some((i, &mut entry.key, &mut entry.value)) - } else { - None - } - } - /// Remove the key-value pair equivalent to `key` and return /// its value. /// @@ -713,9 +729,7 @@ where { let mut entries = self.into_entries(); entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); - IntoIter { - iter: entries.into_iter(), - } + IntoIter::new(entries) } /// Sort the map's key-value pairs by the default ordering of the keys, but @@ -759,9 +773,25 @@ where { let mut entries = self.into_entries(); entries.sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); - IntoIter { - iter: entries.into_iter(), - } + IntoIter::new(entries) + } + + /// Sort the map’s key-value pairs in place using a sort-key extraction function. + /// + /// During sorting, the function is called at most once per entry, by using temporary storage + /// to remember the results of its evaluation. The order of calls to the function is + /// unspecified and may change between versions of `indexmap` or the standard library. + /// + /// Computes in **O(m n + n log n + c)** time () and **O(n)** space, where the function is + /// **O(m)**, *n* is the length of the map, and *c* the capacity. The sort is stable. + pub fn sort_by_cached_key<T, F>(&mut self, mut sort_key: F) + where + T: Ord, + F: FnMut(&K, &V) -> T, + { + self.with_entries(move |entries| { + entries.sort_by_cached_key(move |a| sort_key(&a.key, &a.value)); + }); } /// Reverses the order of the map’s key-value pairs in place. @@ -773,6 +803,27 @@ where } impl<K, V, S> IndexMap<K, V, S> { + /// Returns a slice of all the key-value pairs in the map. + /// + /// Computes in **O(1)** time. + pub fn as_slice(&self) -> &Slice<K, V> { + Slice::from_slice(self.as_entries()) + } + + /// Returns a mutable slice of all the key-value pairs in the map. + /// + /// Computes in **O(1)** time. + pub fn as_mut_slice(&mut self) -> &mut Slice<K, V> { + Slice::from_mut_slice(self.as_entries_mut()) + } + + /// Converts into a boxed slice of all the key-value pairs in the map. + /// + /// Note that this will drop the inner hash table and any excess capacity. + pub fn into_boxed_slice(self) -> Box<Slice<K, V>> { + Slice::from_boxed(self.into_entries().into_boxed_slice()) + } + /// Get a key-value pair by index /// /// Valid indices are *0 <= index < self.len()* @@ -787,8 +838,30 @@ impl<K, V, S> IndexMap<K, V, S> { /// Valid indices are *0 <= index < self.len()* /// /// Computes in **O(1)** time. - pub fn get_index_mut(&mut self, index: usize) -> Option<(&mut K, &mut V)> { - self.as_entries_mut().get_mut(index).map(Bucket::muts) + pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)> { + self.as_entries_mut().get_mut(index).map(Bucket::ref_mut) + } + + /// Returns a slice of key-value pairs in the given range of indices. + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Computes in **O(1)** time. + pub fn get_range<R: RangeBounds<usize>>(&self, range: R) -> Option<&Slice<K, V>> { + let entries = self.as_entries(); + let range = try_simplify_range(range, entries.len())?; + entries.get(range).map(Slice::from_slice) + } + + /// Returns a mutable slice of key-value pairs in the given range of indices. + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Computes in **O(1)** time. + pub fn get_range_mut<R: RangeBounds<usize>>(&mut self, range: R) -> Option<&mut Slice<K, V>> { + let entries = self.as_entries_mut(); + let range = try_simplify_range(range, entries.len())?; + entries.get_mut(range).map(Slice::from_mut_slice) } /// Get the first key-value pair @@ -866,380 +939,6 @@ impl<K, V, S> IndexMap<K, V, S> { } } -/// An iterator over the keys of a `IndexMap`. -/// -/// This `struct` is created by the [`keys`] method on [`IndexMap`]. See its -/// documentation for more. -/// -/// [`keys`]: struct.IndexMap.html#method.keys -/// [`IndexMap`]: struct.IndexMap.html -pub struct Keys<'a, K, V> { - iter: SliceIter<'a, Bucket<K, V>>, -} - -impl<'a, K, V> Iterator for Keys<'a, K, V> { - type Item = &'a K; - - iterator_methods!(Bucket::key_ref); -} - -impl<K, V> DoubleEndedIterator for Keys<'_, K, V> { - double_ended_iterator_methods!(Bucket::key_ref); -} - -impl<K, V> ExactSizeIterator for Keys<'_, K, V> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<K, V> FusedIterator for Keys<'_, K, V> {} - -// FIXME(#26925) Remove in favor of `#[derive(Clone)]` -impl<K, V> Clone for Keys<'_, K, V> { - fn clone(&self) -> Self { - Keys { - iter: self.iter.clone(), - } - } -} - -impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.clone()).finish() - } -} - -/// An owning iterator over the keys of a `IndexMap`. -/// -/// This `struct` is created by the [`into_keys`] method on [`IndexMap`]. -/// See its documentation for more. -/// -/// [`IndexMap`]: struct.IndexMap.html -/// [`into_keys`]: struct.IndexMap.html#method.into_keys -pub struct IntoKeys<K, V> { - iter: vec::IntoIter<Bucket<K, V>>, -} - -impl<K, V> Iterator for IntoKeys<K, V> { - type Item = K; - - iterator_methods!(Bucket::key); -} - -impl<K, V> DoubleEndedIterator for IntoKeys<K, V> { - double_ended_iterator_methods!(Bucket::key); -} - -impl<K, V> ExactSizeIterator for IntoKeys<K, V> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<K, V> FusedIterator for IntoKeys<K, V> {} - -impl<K: fmt::Debug, V> fmt::Debug for IntoKeys<K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.iter.as_slice().iter().map(Bucket::key_ref); - f.debug_list().entries(iter).finish() - } -} - -/// An iterator over the values of a `IndexMap`. -/// -/// This `struct` is created by the [`values`] method on [`IndexMap`]. See its -/// documentation for more. -/// -/// [`values`]: struct.IndexMap.html#method.values -/// [`IndexMap`]: struct.IndexMap.html -pub struct Values<'a, K, V> { - iter: SliceIter<'a, Bucket<K, V>>, -} - -impl<'a, K, V> Iterator for Values<'a, K, V> { - type Item = &'a V; - - iterator_methods!(Bucket::value_ref); -} - -impl<K, V> DoubleEndedIterator for Values<'_, K, V> { - double_ended_iterator_methods!(Bucket::value_ref); -} - -impl<K, V> ExactSizeIterator for Values<'_, K, V> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<K, V> FusedIterator for Values<'_, K, V> {} - -// FIXME(#26925) Remove in favor of `#[derive(Clone)]` -impl<K, V> Clone for Values<'_, K, V> { - fn clone(&self) -> Self { - Values { - iter: self.iter.clone(), - } - } -} - -impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.clone()).finish() - } -} - -/// A mutable iterator over the values of a `IndexMap`. -/// -/// This `struct` is created by the [`values_mut`] method on [`IndexMap`]. See its -/// documentation for more. -/// -/// [`values_mut`]: struct.IndexMap.html#method.values_mut -/// [`IndexMap`]: struct.IndexMap.html -pub struct ValuesMut<'a, K, V> { - iter: SliceIterMut<'a, Bucket<K, V>>, -} - -impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { - type Item = &'a mut V; - - iterator_methods!(Bucket::value_mut); -} - -impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> { - double_ended_iterator_methods!(Bucket::value_mut); -} - -impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<K, V> FusedIterator for ValuesMut<'_, K, V> {} - -impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.iter.as_slice().iter().map(Bucket::value_ref); - f.debug_list().entries(iter).finish() - } -} - -/// An owning iterator over the values of a `IndexMap`. -/// -/// This `struct` is created by the [`into_values`] method on [`IndexMap`]. -/// See its documentation for more. -/// -/// [`IndexMap`]: struct.IndexMap.html -/// [`into_values`]: struct.IndexMap.html#method.into_values -pub struct IntoValues<K, V> { - iter: vec::IntoIter<Bucket<K, V>>, -} - -impl<K, V> Iterator for IntoValues<K, V> { - type Item = V; - - iterator_methods!(Bucket::value); -} - -impl<K, V> DoubleEndedIterator for IntoValues<K, V> { - double_ended_iterator_methods!(Bucket::value); -} - -impl<K, V> ExactSizeIterator for IntoValues<K, V> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<K, V> FusedIterator for IntoValues<K, V> {} - -impl<K, V: fmt::Debug> fmt::Debug for IntoValues<K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.iter.as_slice().iter().map(Bucket::value_ref); - f.debug_list().entries(iter).finish() - } -} - -/// An iterator over the entries of a `IndexMap`. -/// -/// This `struct` is created by the [`iter`] method on [`IndexMap`]. See its -/// documentation for more. -/// -/// [`iter`]: struct.IndexMap.html#method.iter -/// [`IndexMap`]: struct.IndexMap.html -pub struct Iter<'a, K, V> { - iter: SliceIter<'a, Bucket<K, V>>, -} - -impl<'a, K, V> Iterator for Iter<'a, K, V> { - type Item = (&'a K, &'a V); - - iterator_methods!(Bucket::refs); -} - -impl<K, V> DoubleEndedIterator for Iter<'_, K, V> { - double_ended_iterator_methods!(Bucket::refs); -} - -impl<K, V> ExactSizeIterator for Iter<'_, K, V> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<K, V> FusedIterator for Iter<'_, K, V> {} - -// FIXME(#26925) Remove in favor of `#[derive(Clone)]` -impl<K, V> Clone for Iter<'_, K, V> { - fn clone(&self) -> Self { - Iter { - iter: self.iter.clone(), - } - } -} - -impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.clone()).finish() - } -} - -/// A mutable iterator over the entries of a `IndexMap`. -/// -/// This `struct` is created by the [`iter_mut`] method on [`IndexMap`]. See its -/// documentation for more. -/// -/// [`iter_mut`]: struct.IndexMap.html#method.iter_mut -/// [`IndexMap`]: struct.IndexMap.html -pub struct IterMut<'a, K, V> { - iter: SliceIterMut<'a, Bucket<K, V>>, -} - -impl<'a, K, V> Iterator for IterMut<'a, K, V> { - type Item = (&'a K, &'a mut V); - - iterator_methods!(Bucket::ref_mut); -} - -impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> { - double_ended_iterator_methods!(Bucket::ref_mut); -} - -impl<K, V> ExactSizeIterator for IterMut<'_, K, V> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<K, V> FusedIterator for IterMut<'_, K, V> {} - -impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.iter.as_slice().iter().map(Bucket::refs); - f.debug_list().entries(iter).finish() - } -} - -/// An owning iterator over the entries of a `IndexMap`. -/// -/// This `struct` is created by the [`into_iter`] method on [`IndexMap`] -/// (provided by the `IntoIterator` trait). See its documentation for more. -/// -/// [`into_iter`]: struct.IndexMap.html#method.into_iter -/// [`IndexMap`]: struct.IndexMap.html -pub struct IntoIter<K, V> { - iter: vec::IntoIter<Bucket<K, V>>, -} - -impl<K, V> Iterator for IntoIter<K, V> { - type Item = (K, V); - - iterator_methods!(Bucket::key_value); -} - -impl<K, V> DoubleEndedIterator for IntoIter<K, V> { - double_ended_iterator_methods!(Bucket::key_value); -} - -impl<K, V> ExactSizeIterator for IntoIter<K, V> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<K, V> FusedIterator for IntoIter<K, V> {} - -impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.iter.as_slice().iter().map(Bucket::refs); - f.debug_list().entries(iter).finish() - } -} - -/// A draining iterator over the entries of a `IndexMap`. -/// -/// This `struct` is created by the [`drain`] method on [`IndexMap`]. See its -/// documentation for more. -/// -/// [`drain`]: struct.IndexMap.html#method.drain -/// [`IndexMap`]: struct.IndexMap.html -pub struct Drain<'a, K, V> { - pub(crate) iter: vec::Drain<'a, Bucket<K, V>>, -} - -impl<K, V> Iterator for Drain<'_, K, V> { - type Item = (K, V); - - iterator_methods!(Bucket::key_value); -} - -impl<K, V> DoubleEndedIterator for Drain<'_, K, V> { - double_ended_iterator_methods!(Bucket::key_value); -} - -impl<K, V> ExactSizeIterator for Drain<'_, K, V> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<K, V> FusedIterator for Drain<'_, K, V> {} - -impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Drain<'_, K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.iter.as_slice().iter().map(Bucket::refs); - f.debug_list().entries(iter).finish() - } -} - -impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S> { - type Item = (&'a K, &'a V); - type IntoIter = Iter<'a, K, V>; - fn into_iter(self) -> Self::IntoIter { - self.iter() - } -} - -impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S> { - type Item = (&'a K, &'a mut V); - type IntoIter = IterMut<'a, K, V>; - fn into_iter(self) -> Self::IntoIter { - self.iter_mut() - } -} - -impl<K, V, S> IntoIterator for IndexMap<K, V, S> { - type Item = (K, V); - type IntoIter = IntoIter<K, V>; - fn into_iter(self) -> Self::IntoIter { - IntoIter { - iter: self.into_entries().into_iter(), - } - } -} - /// Access `IndexMap` values corresponding to a key. /// /// # Examples @@ -1421,7 +1120,8 @@ where } } -#[cfg(has_std)] +#[cfg(feature = "std")] +#[cfg_attr(docsrs, doc(cfg(feature = "std")))] impl<K, V, const N: usize> From<[(K, V); N]> for IndexMap<K, V, RandomState> where K: Hash + Eq, @@ -1521,427 +1221,3 @@ where S: BuildHasher, { } - -#[cfg(test)] -mod tests { - use super::*; - use std::string::String; - - #[test] - fn it_works() { - let mut map = IndexMap::new(); - assert_eq!(map.is_empty(), true); - map.insert(1, ()); - map.insert(1, ()); - assert_eq!(map.len(), 1); - assert!(map.get(&1).is_some()); - assert_eq!(map.is_empty(), false); - } - - #[test] - fn new() { - let map = IndexMap::<String, String>::new(); - println!("{:?}", map); - assert_eq!(map.capacity(), 0); - assert_eq!(map.len(), 0); - assert_eq!(map.is_empty(), true); - } - - #[test] - fn insert() { - let insert = [0, 4, 2, 12, 8, 7, 11, 5]; - let not_present = [1, 3, 6, 9, 10]; - let mut map = IndexMap::with_capacity(insert.len()); - - for (i, &elt) in insert.iter().enumerate() { - assert_eq!(map.len(), i); - map.insert(elt, elt); - assert_eq!(map.len(), i + 1); - assert_eq!(map.get(&elt), Some(&elt)); - assert_eq!(map[&elt], elt); - } - println!("{:?}", map); - - for &elt in ¬_present { - assert!(map.get(&elt).is_none()); - } - } - - #[test] - fn insert_full() { - let insert = vec![9, 2, 7, 1, 4, 6, 13]; - let present = vec![1, 6, 2]; - let mut map = IndexMap::with_capacity(insert.len()); - - for (i, &elt) in insert.iter().enumerate() { - assert_eq!(map.len(), i); - let (index, existing) = map.insert_full(elt, elt); - assert_eq!(existing, None); - assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0)); - assert_eq!(map.len(), i + 1); - } - - let len = map.len(); - for &elt in &present { - let (index, existing) = map.insert_full(elt, elt); - assert_eq!(existing, Some(elt)); - assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0)); - assert_eq!(map.len(), len); - } - } - - #[test] - fn insert_2() { - let mut map = IndexMap::with_capacity(16); - - let mut keys = vec![]; - keys.extend(0..16); - keys.extend(if cfg!(miri) { 32..64 } else { 128..267 }); - - for &i in &keys { - let old_map = map.clone(); - map.insert(i, ()); - for key in old_map.keys() { - if map.get(key).is_none() { - println!("old_map: {:?}", old_map); - println!("map: {:?}", map); - panic!("did not find {} in map", key); - } - } - } - - for &i in &keys { - assert!(map.get(&i).is_some(), "did not find {}", i); - } - } - - #[test] - fn insert_order() { - let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; - let mut map = IndexMap::new(); - - for &elt in &insert { - map.insert(elt, ()); - } - - assert_eq!(map.keys().count(), map.len()); - assert_eq!(map.keys().count(), insert.len()); - for (a, b) in insert.iter().zip(map.keys()) { - assert_eq!(a, b); - } - for (i, k) in (0..insert.len()).zip(map.keys()) { - assert_eq!(map.get_index(i).unwrap().0, k); - } - } - - #[test] - fn grow() { - let insert = [0, 4, 2, 12, 8, 7, 11]; - let not_present = [1, 3, 6, 9, 10]; - let mut map = IndexMap::with_capacity(insert.len()); - - for (i, &elt) in insert.iter().enumerate() { - assert_eq!(map.len(), i); - map.insert(elt, elt); - assert_eq!(map.len(), i + 1); - assert_eq!(map.get(&elt), Some(&elt)); - assert_eq!(map[&elt], elt); - } - - println!("{:?}", map); - for &elt in &insert { - map.insert(elt * 10, elt); - } - for &elt in &insert { - map.insert(elt * 100, elt); - } - for (i, &elt) in insert.iter().cycle().enumerate().take(100) { - map.insert(elt * 100 + i as i32, elt); - } - println!("{:?}", map); - for &elt in ¬_present { - assert!(map.get(&elt).is_none()); - } - } - - #[test] - fn reserve() { - let mut map = IndexMap::<usize, usize>::new(); - assert_eq!(map.capacity(), 0); - map.reserve(100); - let capacity = map.capacity(); - assert!(capacity >= 100); - for i in 0..capacity { - assert_eq!(map.len(), i); - map.insert(i, i * i); - assert_eq!(map.len(), i + 1); - assert_eq!(map.capacity(), capacity); - assert_eq!(map.get(&i), Some(&(i * i))); - } - map.insert(capacity, std::usize::MAX); - assert_eq!(map.len(), capacity + 1); - assert!(map.capacity() > capacity); - assert_eq!(map.get(&capacity), Some(&std::usize::MAX)); - } - - #[test] - fn shrink_to_fit() { - let mut map = IndexMap::<usize, usize>::new(); - assert_eq!(map.capacity(), 0); - for i in 0..100 { - assert_eq!(map.len(), i); - map.insert(i, i * i); - assert_eq!(map.len(), i + 1); - assert!(map.capacity() >= i + 1); - assert_eq!(map.get(&i), Some(&(i * i))); - map.shrink_to_fit(); - assert_eq!(map.len(), i + 1); - assert_eq!(map.capacity(), i + 1); - assert_eq!(map.get(&i), Some(&(i * i))); - } - } - - #[test] - fn remove() { - let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; - let mut map = IndexMap::new(); - - for &elt in &insert { - map.insert(elt, elt); - } - - assert_eq!(map.keys().count(), map.len()); - assert_eq!(map.keys().count(), insert.len()); - for (a, b) in insert.iter().zip(map.keys()) { - assert_eq!(a, b); - } - - let remove_fail = [99, 77]; - let remove = [4, 12, 8, 7]; - - for &key in &remove_fail { - assert!(map.swap_remove_full(&key).is_none()); - } - println!("{:?}", map); - for &key in &remove { - //println!("{:?}", map); - let index = map.get_full(&key).unwrap().0; - assert_eq!(map.swap_remove_full(&key), Some((index, key, key))); - } - println!("{:?}", map); - - for key in &insert { - assert_eq!(map.get(key).is_some(), !remove.contains(key)); - } - assert_eq!(map.len(), insert.len() - remove.len()); - assert_eq!(map.keys().count(), insert.len() - remove.len()); - } - - #[test] - fn remove_to_empty() { - let mut map = indexmap! { 0 => 0, 4 => 4, 5 => 5 }; - map.swap_remove(&5).unwrap(); - map.swap_remove(&4).unwrap(); - map.swap_remove(&0).unwrap(); - assert!(map.is_empty()); - } - - #[test] - fn swap_remove_index() { - let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; - let mut map = IndexMap::new(); - - for &elt in &insert { - map.insert(elt, elt * 2); - } - - let mut vector = insert.to_vec(); - let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1]; - - // check that the same swap remove sequence on vec and map - // have the same result. - for &rm in remove_sequence { - let out_vec = vector.swap_remove(rm); - let (out_map, _) = map.swap_remove_index(rm).unwrap(); - assert_eq!(out_vec, out_map); - } - assert_eq!(vector.len(), map.len()); - for (a, b) in vector.iter().zip(map.keys()) { - assert_eq!(a, b); - } - } - - #[test] - fn partial_eq_and_eq() { - let mut map_a = IndexMap::new(); - map_a.insert(1, "1"); - map_a.insert(2, "2"); - let mut map_b = map_a.clone(); - assert_eq!(map_a, map_b); - map_b.swap_remove(&1); - assert_ne!(map_a, map_b); - - let map_c: IndexMap<_, String> = map_b.into_iter().map(|(k, v)| (k, v.into())).collect(); - assert_ne!(map_a, map_c); - assert_ne!(map_c, map_a); - } - - #[test] - fn extend() { - let mut map = IndexMap::new(); - map.extend(vec![(&1, &2), (&3, &4)]); - map.extend(vec![(5, 6)]); - assert_eq!( - map.into_iter().collect::<Vec<_>>(), - vec![(1, 2), (3, 4), (5, 6)] - ); - } - - #[test] - fn entry() { - let mut map = IndexMap::new(); - - map.insert(1, "1"); - map.insert(2, "2"); - { - let e = map.entry(3); - assert_eq!(e.index(), 2); - let e = e.or_insert("3"); - assert_eq!(e, &"3"); - } - - let e = map.entry(2); - assert_eq!(e.index(), 1); - assert_eq!(e.key(), &2); - match e { - Entry::Occupied(ref e) => assert_eq!(e.get(), &"2"), - Entry::Vacant(_) => panic!(), - } - assert_eq!(e.or_insert("4"), &"2"); - } - - #[test] - fn entry_and_modify() { - let mut map = IndexMap::new(); - - map.insert(1, "1"); - map.entry(1).and_modify(|x| *x = "2"); - assert_eq!(Some(&"2"), map.get(&1)); - - map.entry(2).and_modify(|x| *x = "doesn't exist"); - assert_eq!(None, map.get(&2)); - } - - #[test] - fn entry_or_default() { - let mut map = IndexMap::new(); - - #[derive(Debug, PartialEq)] - enum TestEnum { - DefaultValue, - NonDefaultValue, - } - - impl Default for TestEnum { - fn default() -> Self { - TestEnum::DefaultValue - } - } - - map.insert(1, TestEnum::NonDefaultValue); - assert_eq!(&mut TestEnum::NonDefaultValue, map.entry(1).or_default()); - - assert_eq!(&mut TestEnum::DefaultValue, map.entry(2).or_default()); - } - - #[test] - fn occupied_entry_key() { - // These keys match hash and equality, but their addresses are distinct. - let (k1, k2) = (&mut 1, &mut 1); - let k1_ptr = k1 as *const i32; - let k2_ptr = k2 as *const i32; - assert_ne!(k1_ptr, k2_ptr); - - let mut map = IndexMap::new(); - map.insert(k1, "value"); - match map.entry(k2) { - Entry::Occupied(ref e) => { - // `OccupiedEntry::key` should reference the key in the map, - // not the key that was used to find the entry. - let ptr = *e.key() as *const i32; - assert_eq!(ptr, k1_ptr); - assert_ne!(ptr, k2_ptr); - } - Entry::Vacant(_) => panic!(), - } - } - - #[test] - fn keys() { - let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; - let map: IndexMap<_, _> = vec.into_iter().collect(); - let keys: Vec<_> = map.keys().copied().collect(); - assert_eq!(keys.len(), 3); - assert!(keys.contains(&1)); - assert!(keys.contains(&2)); - assert!(keys.contains(&3)); - } - - #[test] - fn into_keys() { - let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; - let map: IndexMap<_, _> = vec.into_iter().collect(); - let keys: Vec<i32> = map.into_keys().collect(); - assert_eq!(keys.len(), 3); - assert!(keys.contains(&1)); - assert!(keys.contains(&2)); - assert!(keys.contains(&3)); - } - - #[test] - fn values() { - let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; - let map: IndexMap<_, _> = vec.into_iter().collect(); - let values: Vec<_> = map.values().copied().collect(); - assert_eq!(values.len(), 3); - assert!(values.contains(&'a')); - assert!(values.contains(&'b')); - assert!(values.contains(&'c')); - } - - #[test] - fn values_mut() { - let vec = vec![(1, 1), (2, 2), (3, 3)]; - let mut map: IndexMap<_, _> = vec.into_iter().collect(); - for value in map.values_mut() { - *value *= 2 - } - let values: Vec<_> = map.values().copied().collect(); - assert_eq!(values.len(), 3); - assert!(values.contains(&2)); - assert!(values.contains(&4)); - assert!(values.contains(&6)); - } - - #[test] - fn into_values() { - let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; - let map: IndexMap<_, _> = vec.into_iter().collect(); - let values: Vec<char> = map.into_values().collect(); - assert_eq!(values.len(), 3); - assert!(values.contains(&'a')); - assert!(values.contains(&'b')); - assert!(values.contains(&'c')); - } - - #[test] - #[cfg(has_std)] - fn from_array() { - let map = IndexMap::from([(1, 2), (3, 4)]); - let mut expected = IndexMap::new(); - expected.insert(1, 2); - expected.insert(3, 4); - - assert_eq!(map, expected) - } -} diff --git a/vendor/indexmap/src/map/core.rs b/vendor/indexmap/src/map/core.rs index ea7aaae62..3e392ace6 100644 --- a/vendor/indexmap/src/map/core.rs +++ b/vendor/indexmap/src/map/core.rs @@ -12,14 +12,13 @@ mod raw; use hashbrown::raw::RawTable; use crate::vec::{Drain, Vec}; -use core::cmp; +use crate::TryReserveError; use core::fmt; -use core::mem::replace; +use core::mem; use core::ops::RangeBounds; -use crate::equivalent::Equivalent; use crate::util::simplify_range; -use crate::{Bucket, Entries, HashValue}; +use crate::{Bucket, Entries, Equivalent, HashValue}; /// Core of the map that does not depend on S pub(crate) struct IndexMapCore<K, V> { @@ -62,18 +61,18 @@ where V: Clone, { fn clone(&self) -> Self { - let indices = self.indices.clone(); - let mut entries = Vec::with_capacity(indices.capacity()); - entries.clone_from(&self.entries); - IndexMapCore { indices, entries } + let mut new = Self::new(); + new.clone_from(self); + new } fn clone_from(&mut self, other: &Self) { let hasher = get_hash(&other.entries); self.indices.clone_from_with_hasher(&other.indices, hasher); if self.entries.capacity() < other.entries.len() { - // If we must resize, match the indices capacity - self.reserve_entries(); + // If we must resize, match the indices capacity. + let additional = other.entries.len() - self.entries.len(); + self.reserve_entries(additional); } self.entries.clone_from(&other.entries); } @@ -120,6 +119,9 @@ impl<K, V> Entries for IndexMapCore<K, V> { } impl<K, V> IndexMapCore<K, V> { + /// The maximum capacity before the `entries` allocation would exceed `isize::MAX`. + const MAX_ENTRIES_CAPACITY: usize = (isize::MAX as usize) / mem::size_of::<Bucket<K, V>>(); + #[inline] pub(crate) const fn new() -> Self { IndexMapCore { @@ -143,7 +145,7 @@ impl<K, V> IndexMapCore<K, V> { #[inline] pub(crate) fn capacity(&self) -> usize { - cmp::min(self.indices.capacity(), self.entries.capacity()) + Ord::min(self.indices.capacity(), self.entries.capacity()) } pub(crate) fn clear(&mut self) { @@ -193,15 +195,67 @@ impl<K, V> IndexMapCore<K, V> { /// Reserve capacity for `additional` more key-value pairs. pub(crate) fn reserve(&mut self, additional: usize) { self.indices.reserve(additional, get_hash(&self.entries)); - self.reserve_entries(); + // Only grow entries if necessary, since we also round up capacity. + if additional > self.entries.capacity() - self.entries.len() { + self.reserve_entries(additional); + } } - /// Reserve entries capacity to match the indices - fn reserve_entries(&mut self) { - let additional = self.indices.capacity() - self.entries.len(); + /// Reserve entries capacity, rounded up to match the indices + fn reserve_entries(&mut self, additional: usize) { + // Use a soft-limit on the maximum capacity, but if the caller explicitly + // requested more, do it and let them have the resulting panic. + let new_capacity = Ord::min(self.indices.capacity(), Self::MAX_ENTRIES_CAPACITY); + let try_add = new_capacity - self.entries.len(); + if try_add > additional && self.entries.try_reserve_exact(try_add).is_ok() { + return; + } + self.entries.reserve_exact(additional); + } + + /// Reserve capacity for `additional` more key-value pairs, without over-allocating. + pub(crate) fn reserve_exact(&mut self, additional: usize) { + self.indices.reserve(additional, get_hash(&self.entries)); self.entries.reserve_exact(additional); } + /// Try to reserve capacity for `additional` more key-value pairs. + pub(crate) fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.indices + .try_reserve(additional, get_hash(&self.entries)) + .map_err(TryReserveError::from_hashbrown)?; + // Only grow entries if necessary, since we also round up capacity. + if additional > self.entries.capacity() - self.entries.len() { + self.try_reserve_entries(additional) + } else { + Ok(()) + } + } + + /// Try to reserve entries capacity, rounded up to match the indices + fn try_reserve_entries(&mut self, additional: usize) -> Result<(), TryReserveError> { + // Use a soft-limit on the maximum capacity, but if the caller explicitly + // requested more, do it and let them have the resulting error. + let new_capacity = Ord::min(self.indices.capacity(), Self::MAX_ENTRIES_CAPACITY); + let try_add = new_capacity - self.entries.len(); + if try_add > additional && self.entries.try_reserve_exact(try_add).is_ok() { + return Ok(()); + } + self.entries + .try_reserve_exact(additional) + .map_err(TryReserveError::from_alloc) + } + + /// Try to reserve capacity for `additional` more key-value pairs, without over-allocating. + pub(crate) fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.indices + .try_reserve(additional, get_hash(&self.entries)) + .map_err(TryReserveError::from_hashbrown)?; + self.entries + .try_reserve_exact(additional) + .map_err(TryReserveError::from_alloc) + } + /// Shrink the capacity of the map with a lower bound pub(crate) fn shrink_to(&mut self, min_capacity: usize) { self.indices @@ -220,18 +274,14 @@ impl<K, V> IndexMapCore<K, V> { } } - /// Append a key-value pair, *without* checking whether it already exists, - /// and return the pair's new index. - fn push(&mut self, hash: HashValue, key: K, value: V) -> usize { - let i = self.entries.len(); - self.indices.insert(hash.get(), i, get_hash(&self.entries)); - if i == self.entries.capacity() { + /// Append a key-value pair to `entries`, *without* checking whether it already exists. + fn push_entry(&mut self, hash: HashValue, key: K, value: V) { + if self.entries.len() == self.entries.capacity() { // Reserve our own capacity synced to the indices, // rather than letting `Vec::push` just double it. - self.reserve_entries(); + self.reserve_entries(1); } self.entries.push(Bucket { hash, key, value }); - i } /// Return the index in `entries` where an equivalent key can be found @@ -247,9 +297,13 @@ impl<K, V> IndexMapCore<K, V> { where K: Eq, { - match self.get_index_of(hash, &key) { - Some(i) => (i, Some(replace(&mut self.entries[i].value, value))), - None => (self.push(hash, key, value), None), + match self.find_or_insert(hash, &key) { + Ok(i) => (i, Some(mem::replace(&mut self.entries[i].value, value))), + Err(i) => { + debug_assert_eq!(i, self.entries.len()); + self.push_entry(hash, key, value); + (i, None) + } } } @@ -339,7 +393,7 @@ impl<K, V> IndexMapCore<K, V> { pub(super) fn move_index(&mut self, from: usize, to: usize) { let from_hash = self.entries[from].hash; if from != to { - // Use a sentinal index so other indices don't collide. + // Use a sentinel index so other indices don't collide. update_index(&mut self.indices, from_hash, from, usize::MAX); // Update all other indices and rotate the entry positions. @@ -351,7 +405,7 @@ impl<K, V> IndexMapCore<K, V> { self.entries[to..=from].rotate_right(1); } - // Change the sentinal index to its final position. + // Change the sentinel index to its final position. update_index(&mut self.indices, from_hash, usize::MAX, to); } } @@ -447,25 +501,9 @@ impl<K, V> IndexMapCore<K, V> { where F: FnMut(&mut K, &mut V) -> bool, { - // FIXME: This could use Vec::retain_mut with MSRV 1.61. - // Like Vec::retain in self.entries, but with mutable K and V. - // We swap-shift all the items we want to keep, truncate the rest, - // then rebuild the raw hash table with the new indexes. - let len = self.entries.len(); - let mut n_deleted = 0; - for i in 0..len { - let will_keep = { - let entry = &mut self.entries[i]; - keep(&mut entry.key, &mut entry.value) - }; - if !will_keep { - n_deleted += 1; - } else if n_deleted > 0 { - self.entries.swap(i - n_deleted, i); - } - } - if n_deleted > 0 { - self.entries.truncate(len - n_deleted); + self.entries + .retain_mut(|entry| keep(&mut entry.key, &mut entry.value)); + if self.entries.len() < self.indices.len() { self.rebuild_hash_table(); } } @@ -601,7 +639,7 @@ pub use self::raw::OccupiedEntry; impl<K, V> OccupiedEntry<'_, K, V> { /// Sets the value of the entry to `value`, and returns the entry's old value. pub fn insert(&mut self, value: V) -> V { - replace(self.get_mut(), value) + mem::replace(self.get_mut(), value) } /// Remove the key, value pair stored in the map for this entry, and return the value. @@ -673,14 +711,18 @@ impl<'a, K, V> VacantEntry<'a, K, V> { /// Return the index where the key-value pair will be inserted. pub fn index(&self) -> usize { - self.map.len() + self.map.indices.len() } /// Inserts the entry's key and the given value into the map, and returns a mutable reference /// to the value. pub fn insert(self, value: V) -> &'a mut V { - let i = self.map.push(self.hash, self.key, value); - &mut self.map.entries[i].value + let i = self.index(); + let Self { map, hash, key } = self; + map.indices.insert(hash.get(), i, get_hash(&map.entries)); + debug_assert_eq!(i, map.entries.len()); + map.push_entry(hash, key, value); + &mut map.entries[i].value } } diff --git a/vendor/indexmap/src/map/core/raw.rs b/vendor/indexmap/src/map/core/raw.rs index bf1672d52..332770cc2 100644 --- a/vendor/indexmap/src/map/core/raw.rs +++ b/vendor/indexmap/src/map/core/raw.rs @@ -2,7 +2,7 @@ //! This module encapsulates the `unsafe` access to `hashbrown::raw::RawTable`, //! mostly in dealing with its bucket "pointers". -use super::{equivalent, Bucket, Entry, HashValue, IndexMapCore, VacantEntry}; +use super::{equivalent, get_hash, Bucket, Entry, HashValue, IndexMapCore, VacantEntry}; use core::fmt; use core::mem::replace; use hashbrown::raw::RawTable; @@ -26,7 +26,7 @@ pub(super) struct DebugIndices<'a>(pub &'a RawTable<usize>); impl fmt::Debug for DebugIndices<'_> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { // SAFETY: we're not letting any of the buckets escape this function - let indices = unsafe { self.0.iter().map(|raw_bucket| raw_bucket.read()) }; + let indices = unsafe { self.0.iter().map(|raw_bucket| *raw_bucket.as_ref()) }; f.debug_list().entries(indices).finish() } } @@ -38,16 +38,42 @@ impl<K, V> IndexMapCore<K, V> { unsafe { let offset = end - start; for bucket in self.indices.iter() { - let i = bucket.read(); - if i >= end { - bucket.write(i - offset); - } else if i >= start { + let i = bucket.as_mut(); + if *i >= end { + *i -= offset; + } else if *i >= start { self.indices.erase(bucket); } } } } + /// Search for a key in the table and return `Ok(entry_index)` if found. + /// Otherwise, insert the key and return `Err(new_index)`. + /// + /// Note that hashbrown may resize the table to reserve space for insertion, + /// even before checking if it's already present, so this is somewhat biased + /// towards new items. + pub(crate) fn find_or_insert(&mut self, hash: HashValue, key: &K) -> Result<usize, usize> + where + K: Eq, + { + let hash = hash.get(); + let eq = equivalent(key, &self.entries); + let hasher = get_hash(&self.entries); + // SAFETY: We're not mutating between find and read/insert. + unsafe { + match self.indices.find_or_find_insert_slot(hash, eq, hasher) { + Ok(raw_bucket) => Ok(*raw_bucket.as_ref()), + Err(slot) => { + let index = self.indices.len(); + self.indices.insert_in_slot(hash, slot, index); + Err(index) + } + } + } + } + pub(crate) fn entry(&mut self, hash: HashValue, key: K) -> Entry<'_, K, V> where K: Eq, @@ -92,8 +118,8 @@ impl<K, V> IndexMapCore<K, V> { unsafe { let raw_bucket_a = self.find_index(a); let raw_bucket_b = self.find_index(b); - raw_bucket_a.write(b); - raw_bucket_b.write(a); + *raw_bucket_a.as_mut() = b; + *raw_bucket_b.as_mut() = a; } self.entries.swap(a, b); } @@ -151,7 +177,7 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> { #[inline] pub fn index(&self) -> usize { // SAFETY: we have &mut map keep keeping the bucket stable - unsafe { self.raw_bucket.read() } + unsafe { *self.raw_bucket.as_ref() } } /// Converts into a mutable reference to the entry's value in the map, @@ -171,7 +197,7 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> { pub fn swap_remove_entry(self) -> (K, V) { // SAFETY: This is safe because it can only happen once (self is consumed) // and map.indices have not been modified since entry construction - let index = unsafe { self.map.indices.remove(self.raw_bucket) }; + let (index, _slot) = unsafe { self.map.indices.remove(self.raw_bucket) }; self.map.swap_remove_finish(index) } @@ -185,7 +211,7 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> { pub fn shift_remove_entry(self) -> (K, V) { // SAFETY: This is safe because it can only happen once (self is consumed) // and map.indices have not been modified since entry construction - let index = unsafe { self.map.indices.remove(self.raw_bucket) }; + let (index, _slot) = unsafe { self.map.indices.remove(self.raw_bucket) }; self.map.shift_remove_finish(index) } } diff --git a/vendor/indexmap/src/map/iter.rs b/vendor/indexmap/src/map/iter.rs new file mode 100644 index 000000000..db6e140dd --- /dev/null +++ b/vendor/indexmap/src/map/iter.rs @@ -0,0 +1,541 @@ +use super::{Bucket, Entries, IndexMap, Slice}; + +use alloc::vec::{self, Vec}; +use core::fmt; +use core::iter::FusedIterator; +use core::slice; + +impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S> { + type Item = (&'a K, &'a V); + type IntoIter = Iter<'a, K, V>; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S> { + type Item = (&'a K, &'a mut V); + type IntoIter = IterMut<'a, K, V>; + + fn into_iter(self) -> Self::IntoIter { + self.iter_mut() + } +} + +impl<K, V, S> IntoIterator for IndexMap<K, V, S> { + type Item = (K, V); + type IntoIter = IntoIter<K, V>; + + fn into_iter(self) -> Self::IntoIter { + IntoIter::new(self.into_entries()) + } +} + +/// An iterator over the entries of a `IndexMap`. +/// +/// This `struct` is created by the [`iter`] method on [`IndexMap`]. See its +/// documentation for more. +/// +/// [`iter`]: struct.IndexMap.html#method.iter +/// [`IndexMap`]: struct.IndexMap.html +pub struct Iter<'a, K, V> { + iter: slice::Iter<'a, Bucket<K, V>>, +} + +impl<'a, K, V> Iter<'a, K, V> { + pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self { + Self { + iter: entries.iter(), + } + } + + /// Returns a slice of the remaining entries in the iterator. + pub fn as_slice(&self) -> &'a Slice<K, V> { + Slice::from_slice(self.iter.as_slice()) + } +} + +impl<'a, K, V> Iterator for Iter<'a, K, V> { + type Item = (&'a K, &'a V); + + iterator_methods!(Bucket::refs); +} + +impl<K, V> DoubleEndedIterator for Iter<'_, K, V> { + double_ended_iterator_methods!(Bucket::refs); +} + +impl<K, V> ExactSizeIterator for Iter<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for Iter<'_, K, V> {} + +// FIXME(#26925) Remove in favor of `#[derive(Clone)]` +impl<K, V> Clone for Iter<'_, K, V> { + fn clone(&self) -> Self { + Iter { + iter: self.iter.clone(), + } + } +} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<K, V> Default for Iter<'_, K, V> { + fn default() -> Self { + Self { iter: [].iter() } + } +} + +/// A mutable iterator over the entries of a `IndexMap`. +/// +/// This `struct` is created by the [`iter_mut`] method on [`IndexMap`]. See its +/// documentation for more. +/// +/// [`iter_mut`]: struct.IndexMap.html#method.iter_mut +/// [`IndexMap`]: struct.IndexMap.html +pub struct IterMut<'a, K, V> { + iter: slice::IterMut<'a, Bucket<K, V>>, +} + +impl<'a, K, V> IterMut<'a, K, V> { + pub(super) fn new(entries: &'a mut [Bucket<K, V>]) -> Self { + Self { + iter: entries.iter_mut(), + } + } + + /// Returns a slice of the remaining entries in the iterator. + pub fn as_slice(&self) -> &Slice<K, V> { + Slice::from_slice(self.iter.as_slice()) + } + + /// Returns a mutable slice of the remaining entries in the iterator. + /// + /// To avoid creating `&mut` references that alias, this is forced to consume the iterator. + pub fn into_slice(self) -> &'a mut Slice<K, V> { + Slice::from_mut_slice(self.iter.into_slice()) + } +} + +impl<'a, K, V> Iterator for IterMut<'a, K, V> { + type Item = (&'a K, &'a mut V); + + iterator_methods!(Bucket::ref_mut); +} + +impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> { + double_ended_iterator_methods!(Bucket::ref_mut); +} + +impl<K, V> ExactSizeIterator for IterMut<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for IterMut<'_, K, V> {} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.iter.as_slice().iter().map(Bucket::refs); + f.debug_list().entries(iter).finish() + } +} + +impl<K, V> Default for IterMut<'_, K, V> { + fn default() -> Self { + Self { + iter: [].iter_mut(), + } + } +} + +/// An owning iterator over the entries of a `IndexMap`. +/// +/// This `struct` is created by the [`into_iter`] method on [`IndexMap`] +/// (provided by the `IntoIterator` trait). See its documentation for more. +/// +/// [`into_iter`]: struct.IndexMap.html#method.into_iter +/// [`IndexMap`]: struct.IndexMap.html +pub struct IntoIter<K, V> { + iter: vec::IntoIter<Bucket<K, V>>, +} + +impl<K, V> IntoIter<K, V> { + pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self { + Self { + iter: entries.into_iter(), + } + } + + /// Returns a slice of the remaining entries in the iterator. + pub fn as_slice(&self) -> &Slice<K, V> { + Slice::from_slice(self.iter.as_slice()) + } + + /// Returns a mutable slice of the remaining entries in the iterator. + pub fn as_mut_slice(&mut self) -> &mut Slice<K, V> { + Slice::from_mut_slice(self.iter.as_mut_slice()) + } +} + +impl<K, V> Iterator for IntoIter<K, V> { + type Item = (K, V); + + iterator_methods!(Bucket::key_value); +} + +impl<K, V> DoubleEndedIterator for IntoIter<K, V> { + double_ended_iterator_methods!(Bucket::key_value); +} + +impl<K, V> ExactSizeIterator for IntoIter<K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for IntoIter<K, V> {} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.iter.as_slice().iter().map(Bucket::refs); + f.debug_list().entries(iter).finish() + } +} + +impl<K, V> Default for IntoIter<K, V> { + fn default() -> Self { + Self { + iter: Vec::new().into_iter(), + } + } +} + +/// A draining iterator over the entries of a `IndexMap`. +/// +/// This `struct` is created by the [`drain`] method on [`IndexMap`]. See its +/// documentation for more. +/// +/// [`drain`]: struct.IndexMap.html#method.drain +/// [`IndexMap`]: struct.IndexMap.html +pub struct Drain<'a, K, V> { + iter: vec::Drain<'a, Bucket<K, V>>, +} + +impl<'a, K, V> Drain<'a, K, V> { + pub(super) fn new(iter: vec::Drain<'a, Bucket<K, V>>) -> Self { + Self { iter } + } + + /// Returns a slice of the remaining entries in the iterator. + pub fn as_slice(&self) -> &Slice<K, V> { + Slice::from_slice(self.iter.as_slice()) + } +} + +impl<K, V> Iterator for Drain<'_, K, V> { + type Item = (K, V); + + iterator_methods!(Bucket::key_value); +} + +impl<K, V> DoubleEndedIterator for Drain<'_, K, V> { + double_ended_iterator_methods!(Bucket::key_value); +} + +impl<K, V> ExactSizeIterator for Drain<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for Drain<'_, K, V> {} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Drain<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.iter.as_slice().iter().map(Bucket::refs); + f.debug_list().entries(iter).finish() + } +} + +/// An iterator over the keys of a `IndexMap`. +/// +/// This `struct` is created by the [`keys`] method on [`IndexMap`]. See its +/// documentation for more. +/// +/// [`keys`]: struct.IndexMap.html#method.keys +/// [`IndexMap`]: struct.IndexMap.html +pub struct Keys<'a, K, V> { + iter: slice::Iter<'a, Bucket<K, V>>, +} + +impl<'a, K, V> Keys<'a, K, V> { + pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self { + Self { + iter: entries.iter(), + } + } +} + +impl<'a, K, V> Iterator for Keys<'a, K, V> { + type Item = &'a K; + + iterator_methods!(Bucket::key_ref); +} + +impl<K, V> DoubleEndedIterator for Keys<'_, K, V> { + double_ended_iterator_methods!(Bucket::key_ref); +} + +impl<K, V> ExactSizeIterator for Keys<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for Keys<'_, K, V> {} + +// FIXME(#26925) Remove in favor of `#[derive(Clone)]` +impl<K, V> Clone for Keys<'_, K, V> { + fn clone(&self) -> Self { + Keys { + iter: self.iter.clone(), + } + } +} + +impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<K, V> Default for Keys<'_, K, V> { + fn default() -> Self { + Self { iter: [].iter() } + } +} + +/// An owning iterator over the keys of a `IndexMap`. +/// +/// This `struct` is created by the [`into_keys`] method on [`IndexMap`]. +/// See its documentation for more. +/// +/// [`IndexMap`]: struct.IndexMap.html +/// [`into_keys`]: struct.IndexMap.html#method.into_keys +pub struct IntoKeys<K, V> { + iter: vec::IntoIter<Bucket<K, V>>, +} + +impl<K, V> IntoKeys<K, V> { + pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self { + Self { + iter: entries.into_iter(), + } + } +} + +impl<K, V> Iterator for IntoKeys<K, V> { + type Item = K; + + iterator_methods!(Bucket::key); +} + +impl<K, V> DoubleEndedIterator for IntoKeys<K, V> { + double_ended_iterator_methods!(Bucket::key); +} + +impl<K, V> ExactSizeIterator for IntoKeys<K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for IntoKeys<K, V> {} + +impl<K: fmt::Debug, V> fmt::Debug for IntoKeys<K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.iter.as_slice().iter().map(Bucket::key_ref); + f.debug_list().entries(iter).finish() + } +} + +impl<K, V> Default for IntoKeys<K, V> { + fn default() -> Self { + Self { + iter: Vec::new().into_iter(), + } + } +} + +/// An iterator over the values of a `IndexMap`. +/// +/// This `struct` is created by the [`values`] method on [`IndexMap`]. See its +/// documentation for more. +/// +/// [`values`]: struct.IndexMap.html#method.values +/// [`IndexMap`]: struct.IndexMap.html +pub struct Values<'a, K, V> { + iter: slice::Iter<'a, Bucket<K, V>>, +} + +impl<'a, K, V> Values<'a, K, V> { + pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self { + Self { + iter: entries.iter(), + } + } +} + +impl<'a, K, V> Iterator for Values<'a, K, V> { + type Item = &'a V; + + iterator_methods!(Bucket::value_ref); +} + +impl<K, V> DoubleEndedIterator for Values<'_, K, V> { + double_ended_iterator_methods!(Bucket::value_ref); +} + +impl<K, V> ExactSizeIterator for Values<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for Values<'_, K, V> {} + +// FIXME(#26925) Remove in favor of `#[derive(Clone)]` +impl<K, V> Clone for Values<'_, K, V> { + fn clone(&self) -> Self { + Values { + iter: self.iter.clone(), + } + } +} + +impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<K, V> Default for Values<'_, K, V> { + fn default() -> Self { + Self { iter: [].iter() } + } +} + +/// A mutable iterator over the values of a `IndexMap`. +/// +/// This `struct` is created by the [`values_mut`] method on [`IndexMap`]. See its +/// documentation for more. +/// +/// [`values_mut`]: struct.IndexMap.html#method.values_mut +/// [`IndexMap`]: struct.IndexMap.html +pub struct ValuesMut<'a, K, V> { + iter: slice::IterMut<'a, Bucket<K, V>>, +} + +impl<'a, K, V> ValuesMut<'a, K, V> { + pub(super) fn new(entries: &'a mut [Bucket<K, V>]) -> Self { + Self { + iter: entries.iter_mut(), + } + } +} + +impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { + type Item = &'a mut V; + + iterator_methods!(Bucket::value_mut); +} + +impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> { + double_ended_iterator_methods!(Bucket::value_mut); +} + +impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for ValuesMut<'_, K, V> {} + +impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.iter.as_slice().iter().map(Bucket::value_ref); + f.debug_list().entries(iter).finish() + } +} + +impl<K, V> Default for ValuesMut<'_, K, V> { + fn default() -> Self { + Self { + iter: [].iter_mut(), + } + } +} + +/// An owning iterator over the values of a `IndexMap`. +/// +/// This `struct` is created by the [`into_values`] method on [`IndexMap`]. +/// See its documentation for more. +/// +/// [`IndexMap`]: struct.IndexMap.html +/// [`into_values`]: struct.IndexMap.html#method.into_values +pub struct IntoValues<K, V> { + iter: vec::IntoIter<Bucket<K, V>>, +} + +impl<K, V> IntoValues<K, V> { + pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self { + Self { + iter: entries.into_iter(), + } + } +} + +impl<K, V> Iterator for IntoValues<K, V> { + type Item = V; + + iterator_methods!(Bucket::value); +} + +impl<K, V> DoubleEndedIterator for IntoValues<K, V> { + double_ended_iterator_methods!(Bucket::value); +} + +impl<K, V> ExactSizeIterator for IntoValues<K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for IntoValues<K, V> {} + +impl<K, V: fmt::Debug> fmt::Debug for IntoValues<K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.iter.as_slice().iter().map(Bucket::value_ref); + f.debug_list().entries(iter).finish() + } +} + +impl<K, V> Default for IntoValues<K, V> { + fn default() -> Self { + Self { + iter: Vec::new().into_iter(), + } + } +} diff --git a/vendor/indexmap/src/serde_seq.rs b/vendor/indexmap/src/map/serde_seq.rs index d326a02e3..f10aa5781 100644 --- a/vendor/indexmap/src/serde_seq.rs +++ b/vendor/indexmap/src/map/serde_seq.rs @@ -12,13 +12,11 @@ //! # use serde_derive::{Deserialize, Serialize}; //! #[derive(Deserialize, Serialize)] //! struct Data { -//! #[serde(with = "indexmap::serde_seq")] +//! #[serde(with = "indexmap::map::serde_seq")] //! map: IndexMap<i32, u64>, //! // ... //! } //! ``` -//! -//! Requires crate feature `"serde"` or `"serde-1"` use serde::de::{Deserialize, Deserializer, SeqAccess, Visitor}; use serde::ser::{Serialize, Serializer}; @@ -27,8 +25,40 @@ use core::fmt::{self, Formatter}; use core::hash::{BuildHasher, Hash}; use core::marker::PhantomData; +use crate::map::Slice as MapSlice; +use crate::set::Slice as SetSlice; use crate::IndexMap; +/// Serializes a `map::Slice` as an ordered sequence. +/// +/// This behaves like [`crate::map::serde_seq`] for `IndexMap`, serializing a sequence +/// of `(key, value)` pairs, rather than as a map that might not preserve order. +impl<K, V> Serialize for MapSlice<K, V> +where + K: Serialize, + V: Serialize, +{ + fn serialize<T>(&self, serializer: T) -> Result<T::Ok, T::Error> + where + T: Serializer, + { + serializer.collect_seq(self) + } +} + +/// Serializes a `set::Slice` as an ordered sequence. +impl<T> Serialize for SetSlice<T> +where + T: Serialize, +{ + fn serialize<Se>(&self, serializer: Se) -> Result<Se::Ok, Se::Error> + where + Se: Serializer, + { + serializer.collect_seq(self) + } +} + /// Serializes an `IndexMap` as an ordered sequence. /// /// This function may be used in a field attribute for deriving `Serialize`: @@ -38,13 +68,11 @@ use crate::IndexMap; /// # use serde_derive::Serialize; /// #[derive(Serialize)] /// struct Data { -/// #[serde(serialize_with = "indexmap::serde_seq::serialize")] +/// #[serde(serialize_with = "indexmap::map::serde_seq::serialize")] /// map: IndexMap<i32, u64>, /// // ... /// } /// ``` -/// -/// Requires crate feature `"serde"` or `"serde-1"` pub fn serialize<K, V, S, T>(map: &IndexMap<K, V, S>, serializer: T) -> Result<T::Ok, T::Error> where K: Serialize + Hash + Eq, @@ -94,13 +122,11 @@ where /// # use serde_derive::Deserialize; /// #[derive(Deserialize)] /// struct Data { -/// #[serde(deserialize_with = "indexmap::serde_seq::deserialize")] +/// #[serde(deserialize_with = "indexmap::map::serde_seq::deserialize")] /// map: IndexMap<i32, u64>, /// // ... /// } /// ``` -/// -/// Requires crate feature `"serde"` or `"serde-1"` pub fn deserialize<'de, D, K, V, S>(deserializer: D) -> Result<IndexMap<K, V, S>, D::Error> where D: Deserializer<'de>, diff --git a/vendor/indexmap/src/map/slice.rs b/vendor/indexmap/src/map/slice.rs new file mode 100644 index 000000000..9fb876fd2 --- /dev/null +++ b/vendor/indexmap/src/map/slice.rs @@ -0,0 +1,471 @@ +use super::{ + Bucket, Entries, IndexMap, IntoIter, IntoKeys, IntoValues, Iter, IterMut, Keys, Values, + ValuesMut, +}; +use crate::util::try_simplify_range; + +use alloc::boxed::Box; +use alloc::vec::Vec; +use core::cmp::Ordering; +use core::fmt; +use core::hash::{Hash, Hasher}; +use core::ops::{self, Bound, Index, IndexMut, RangeBounds}; + +/// A dynamically-sized slice of key-value pairs in an `IndexMap`. +/// +/// This supports indexed operations much like a `[(K, V)]` slice, +/// but not any hashed operations on the map keys. +/// +/// Unlike `IndexMap`, `Slice` does consider the order for `PartialEq` +/// and `Eq`, and it also implements `PartialOrd`, `Ord`, and `Hash`. +#[repr(transparent)] +pub struct Slice<K, V> { + pub(crate) entries: [Bucket<K, V>], +} + +// SAFETY: `Slice<K, V>` is a transparent wrapper around `[Bucket<K, V>]`, +// and reference lifetimes are bound together in function signatures. +#[allow(unsafe_code)] +impl<K, V> Slice<K, V> { + pub(super) fn from_slice(entries: &[Bucket<K, V>]) -> &Self { + unsafe { &*(entries as *const [Bucket<K, V>] as *const Self) } + } + + pub(super) fn from_mut_slice(entries: &mut [Bucket<K, V>]) -> &mut Self { + unsafe { &mut *(entries as *mut [Bucket<K, V>] as *mut Self) } + } + + pub(super) fn from_boxed(entries: Box<[Bucket<K, V>]>) -> Box<Self> { + unsafe { Box::from_raw(Box::into_raw(entries) as *mut Self) } + } + + fn into_boxed(self: Box<Self>) -> Box<[Bucket<K, V>]> { + unsafe { Box::from_raw(Box::into_raw(self) as *mut [Bucket<K, V>]) } + } +} + +impl<K, V> Slice<K, V> { + pub(crate) fn into_entries(self: Box<Self>) -> Vec<Bucket<K, V>> { + self.into_boxed().into_vec() + } + + /// Return the number of key-value pairs in the map slice. + #[inline] + pub fn len(&self) -> usize { + self.entries.len() + } + + /// Returns true if the map slice contains no elements. + #[inline] + pub fn is_empty(&self) -> bool { + self.entries.is_empty() + } + + /// Get a key-value pair by index. + /// + /// Valid indices are *0 <= index < self.len()* + pub fn get_index(&self, index: usize) -> Option<(&K, &V)> { + self.entries.get(index).map(Bucket::refs) + } + + /// Get a key-value pair by index, with mutable access to the value. + /// + /// Valid indices are *0 <= index < self.len()* + pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)> { + self.entries.get_mut(index).map(Bucket::ref_mut) + } + + /// Returns a slice of key-value pairs in the given range of indices. + /// + /// Valid indices are *0 <= index < self.len()* + pub fn get_range<R: RangeBounds<usize>>(&self, range: R) -> Option<&Self> { + let range = try_simplify_range(range, self.entries.len())?; + self.entries.get(range).map(Slice::from_slice) + } + + /// Returns a mutable slice of key-value pairs in the given range of indices. + /// + /// Valid indices are *0 <= index < self.len()* + pub fn get_range_mut<R: RangeBounds<usize>>(&mut self, range: R) -> Option<&mut Self> { + let range = try_simplify_range(range, self.entries.len())?; + self.entries.get_mut(range).map(Slice::from_mut_slice) + } + + /// Get the first key-value pair. + pub fn first(&self) -> Option<(&K, &V)> { + self.entries.first().map(Bucket::refs) + } + + /// Get the first key-value pair, with mutable access to the value. + pub fn first_mut(&mut self) -> Option<(&K, &mut V)> { + self.entries.first_mut().map(Bucket::ref_mut) + } + + /// Get the last key-value pair. + pub fn last(&self) -> Option<(&K, &V)> { + self.entries.last().map(Bucket::refs) + } + + /// Get the last key-value pair, with mutable access to the value. + pub fn last_mut(&mut self) -> Option<(&K, &mut V)> { + self.entries.last_mut().map(Bucket::ref_mut) + } + + /// Divides one slice into two at an index. + /// + /// ***Panics*** if `index > len`. + pub fn split_at(&self, index: usize) -> (&Self, &Self) { + let (first, second) = self.entries.split_at(index); + (Self::from_slice(first), Self::from_slice(second)) + } + + /// Divides one mutable slice into two at an index. + /// + /// ***Panics*** if `index > len`. + pub fn split_at_mut(&mut self, index: usize) -> (&mut Self, &mut Self) { + let (first, second) = self.entries.split_at_mut(index); + (Self::from_mut_slice(first), Self::from_mut_slice(second)) + } + + /// Returns the first key-value pair and the rest of the slice, + /// or `None` if it is empty. + pub fn split_first(&self) -> Option<((&K, &V), &Self)> { + if let [first, rest @ ..] = &self.entries { + Some((first.refs(), Self::from_slice(rest))) + } else { + None + } + } + + /// Returns the first key-value pair and the rest of the slice, + /// with mutable access to the value, or `None` if it is empty. + pub fn split_first_mut(&mut self) -> Option<((&K, &mut V), &mut Self)> { + if let [first, rest @ ..] = &mut self.entries { + Some((first.ref_mut(), Self::from_mut_slice(rest))) + } else { + None + } + } + + /// Returns the last key-value pair and the rest of the slice, + /// or `None` if it is empty. + pub fn split_last(&self) -> Option<((&K, &V), &Self)> { + if let [rest @ .., last] = &self.entries { + Some((last.refs(), Self::from_slice(rest))) + } else { + None + } + } + + /// Returns the last key-value pair and the rest of the slice, + /// with mutable access to the value, or `None` if it is empty. + pub fn split_last_mut(&mut self) -> Option<((&K, &mut V), &mut Self)> { + if let [rest @ .., last] = &mut self.entries { + Some((last.ref_mut(), Self::from_mut_slice(rest))) + } else { + None + } + } + + /// Return an iterator over the key-value pairs of the map slice. + pub fn iter(&self) -> Iter<'_, K, V> { + Iter::new(&self.entries) + } + + /// Return an iterator over the key-value pairs of the map slice. + pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { + IterMut::new(&mut self.entries) + } + + /// Return an iterator over the keys of the map slice. + pub fn keys(&self) -> Keys<'_, K, V> { + Keys::new(&self.entries) + } + + /// Return an owning iterator over the keys of the map slice. + pub fn into_keys(self: Box<Self>) -> IntoKeys<K, V> { + IntoKeys::new(self.into_entries()) + } + + /// Return an iterator over the values of the map slice. + pub fn values(&self) -> Values<'_, K, V> { + Values::new(&self.entries) + } + + /// Return an iterator over mutable references to the the values of the map slice. + pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> { + ValuesMut::new(&mut self.entries) + } + + /// Return an owning iterator over the values of the map slice. + pub fn into_values(self: Box<Self>) -> IntoValues<K, V> { + IntoValues::new(self.into_entries()) + } +} + +impl<'a, K, V> IntoIterator for &'a Slice<K, V> { + type IntoIter = Iter<'a, K, V>; + type Item = (&'a K, &'a V); + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl<'a, K, V> IntoIterator for &'a mut Slice<K, V> { + type IntoIter = IterMut<'a, K, V>; + type Item = (&'a K, &'a mut V); + + fn into_iter(self) -> Self::IntoIter { + self.iter_mut() + } +} + +impl<K, V> IntoIterator for Box<Slice<K, V>> { + type IntoIter = IntoIter<K, V>; + type Item = (K, V); + + fn into_iter(self) -> Self::IntoIter { + IntoIter::new(self.into_entries()) + } +} + +impl<K, V> Default for &'_ Slice<K, V> { + fn default() -> Self { + Slice::from_slice(&[]) + } +} + +impl<K, V> Default for &'_ mut Slice<K, V> { + fn default() -> Self { + Slice::from_mut_slice(&mut []) + } +} + +impl<K, V> Default for Box<Slice<K, V>> { + fn default() -> Self { + Slice::from_boxed(Box::default()) + } +} + +impl<K: Clone, V: Clone> Clone for Box<Slice<K, V>> { + fn clone(&self) -> Self { + Slice::from_boxed(self.entries.to_vec().into_boxed_slice()) + } +} + +impl<K: Copy, V: Copy> From<&Slice<K, V>> for Box<Slice<K, V>> { + fn from(slice: &Slice<K, V>) -> Self { + Slice::from_boxed(Box::from(&slice.entries)) + } +} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Slice<K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self).finish() + } +} + +impl<K: PartialEq, V: PartialEq> PartialEq for Slice<K, V> { + fn eq(&self, other: &Self) -> bool { + self.len() == other.len() && self.iter().eq(other) + } +} + +impl<K: Eq, V: Eq> Eq for Slice<K, V> {} + +impl<K: PartialOrd, V: PartialOrd> PartialOrd for Slice<K, V> { + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + self.iter().partial_cmp(other) + } +} + +impl<K: Ord, V: Ord> Ord for Slice<K, V> { + fn cmp(&self, other: &Self) -> Ordering { + self.iter().cmp(other) + } +} + +impl<K: Hash, V: Hash> Hash for Slice<K, V> { + fn hash<H: Hasher>(&self, state: &mut H) { + self.len().hash(state); + for (key, value) in self { + key.hash(state); + value.hash(state); + } + } +} + +impl<K, V> Index<usize> for Slice<K, V> { + type Output = V; + + fn index(&self, index: usize) -> &V { + &self.entries[index].value + } +} + +impl<K, V> IndexMut<usize> for Slice<K, V> { + fn index_mut(&mut self, index: usize) -> &mut V { + &mut self.entries[index].value + } +} + +// We can't have `impl<I: RangeBounds<usize>> Index<I>` because that conflicts +// both upstream with `Index<usize>` and downstream with `Index<&Q>`. +// Instead, we repeat the implementations for all the core range types. +macro_rules! impl_index { + ($($range:ty),*) => {$( + impl<K, V, S> Index<$range> for IndexMap<K, V, S> { + type Output = Slice<K, V>; + + fn index(&self, range: $range) -> &Self::Output { + Slice::from_slice(&self.as_entries()[range]) + } + } + + impl<K, V, S> IndexMut<$range> for IndexMap<K, V, S> { + fn index_mut(&mut self, range: $range) -> &mut Self::Output { + Slice::from_mut_slice(&mut self.as_entries_mut()[range]) + } + } + + impl<K, V> Index<$range> for Slice<K, V> { + type Output = Slice<K, V>; + + fn index(&self, range: $range) -> &Self { + Self::from_slice(&self.entries[range]) + } + } + + impl<K, V> IndexMut<$range> for Slice<K, V> { + fn index_mut(&mut self, range: $range) -> &mut Self { + Self::from_mut_slice(&mut self.entries[range]) + } + } + )*} +} +impl_index!( + ops::Range<usize>, + ops::RangeFrom<usize>, + ops::RangeFull, + ops::RangeInclusive<usize>, + ops::RangeTo<usize>, + ops::RangeToInclusive<usize>, + (Bound<usize>, Bound<usize>) +); + +#[cfg(test)] +mod tests { + use super::*; + use alloc::vec::Vec; + + #[test] + fn slice_index() { + fn check( + vec_slice: &[(i32, i32)], + map_slice: &Slice<i32, i32>, + sub_slice: &Slice<i32, i32>, + ) { + assert_eq!(map_slice as *const _, sub_slice as *const _); + itertools::assert_equal( + vec_slice.iter().copied(), + map_slice.iter().map(|(&k, &v)| (k, v)), + ); + itertools::assert_equal(vec_slice.iter().map(|(k, _)| k), map_slice.keys()); + itertools::assert_equal(vec_slice.iter().map(|(_, v)| v), map_slice.values()); + } + + let vec: Vec<(i32, i32)> = (0..10).map(|i| (i, i * i)).collect(); + let map: IndexMap<i32, i32> = vec.iter().cloned().collect(); + let slice = map.as_slice(); + + // RangeFull + check(&vec[..], &map[..], &slice[..]); + + for i in 0usize..10 { + // Index + assert_eq!(vec[i].1, map[i]); + assert_eq!(vec[i].1, slice[i]); + assert_eq!(map[&(i as i32)], map[i]); + assert_eq!(map[&(i as i32)], slice[i]); + + // RangeFrom + check(&vec[i..], &map[i..], &slice[i..]); + + // RangeTo + check(&vec[..i], &map[..i], &slice[..i]); + + // RangeToInclusive + check(&vec[..=i], &map[..=i], &slice[..=i]); + + // (Bound<usize>, Bound<usize>) + let bounds = (Bound::Excluded(i), Bound::Unbounded); + check(&vec[i + 1..], &map[bounds], &slice[bounds]); + + for j in i..=10 { + // Range + check(&vec[i..j], &map[i..j], &slice[i..j]); + } + + for j in i..10 { + // RangeInclusive + check(&vec[i..=j], &map[i..=j], &slice[i..=j]); + } + } + } + + #[test] + fn slice_index_mut() { + fn check_mut( + vec_slice: &[(i32, i32)], + map_slice: &mut Slice<i32, i32>, + sub_slice: &mut Slice<i32, i32>, + ) { + assert_eq!(map_slice, sub_slice); + itertools::assert_equal( + vec_slice.iter().copied(), + map_slice.iter_mut().map(|(&k, &mut v)| (k, v)), + ); + itertools::assert_equal( + vec_slice.iter().map(|&(_, v)| v), + map_slice.values_mut().map(|&mut v| v), + ); + } + + let vec: Vec<(i32, i32)> = (0..10).map(|i| (i, i * i)).collect(); + let mut map: IndexMap<i32, i32> = vec.iter().cloned().collect(); + let mut map2 = map.clone(); + let slice = map2.as_mut_slice(); + + // RangeFull + check_mut(&vec[..], &mut map[..], &mut slice[..]); + + for i in 0usize..10 { + // IndexMut + assert_eq!(&mut map[i], &mut slice[i]); + + // RangeFrom + check_mut(&vec[i..], &mut map[i..], &mut slice[i..]); + + // RangeTo + check_mut(&vec[..i], &mut map[..i], &mut slice[..i]); + + // RangeToInclusive + check_mut(&vec[..=i], &mut map[..=i], &mut slice[..=i]); + + // (Bound<usize>, Bound<usize>) + let bounds = (Bound::Excluded(i), Bound::Unbounded); + check_mut(&vec[i + 1..], &mut map[bounds], &mut slice[bounds]); + + for j in i..=10 { + // Range + check_mut(&vec[i..j], &mut map[i..j], &mut slice[i..j]); + } + + for j in i..10 { + // RangeInclusive + check_mut(&vec[i..=j], &mut map[i..=j], &mut slice[i..=j]); + } + } + } +} diff --git a/vendor/indexmap/src/map/tests.rs b/vendor/indexmap/src/map/tests.rs new file mode 100644 index 000000000..f273d7162 --- /dev/null +++ b/vendor/indexmap/src/map/tests.rs @@ -0,0 +1,449 @@ +use super::*; +use std::string::String; + +#[test] +fn it_works() { + let mut map = IndexMap::new(); + assert_eq!(map.is_empty(), true); + map.insert(1, ()); + map.insert(1, ()); + assert_eq!(map.len(), 1); + assert!(map.get(&1).is_some()); + assert_eq!(map.is_empty(), false); +} + +#[test] +fn new() { + let map = IndexMap::<String, String>::new(); + println!("{:?}", map); + assert_eq!(map.capacity(), 0); + assert_eq!(map.len(), 0); + assert_eq!(map.is_empty(), true); +} + +#[test] +fn insert() { + let insert = [0, 4, 2, 12, 8, 7, 11, 5]; + let not_present = [1, 3, 6, 9, 10]; + let mut map = IndexMap::with_capacity(insert.len()); + + for (i, &elt) in insert.iter().enumerate() { + assert_eq!(map.len(), i); + map.insert(elt, elt); + assert_eq!(map.len(), i + 1); + assert_eq!(map.get(&elt), Some(&elt)); + assert_eq!(map[&elt], elt); + } + println!("{:?}", map); + + for &elt in ¬_present { + assert!(map.get(&elt).is_none()); + } +} + +#[test] +fn insert_full() { + let insert = vec![9, 2, 7, 1, 4, 6, 13]; + let present = vec![1, 6, 2]; + let mut map = IndexMap::with_capacity(insert.len()); + + for (i, &elt) in insert.iter().enumerate() { + assert_eq!(map.len(), i); + let (index, existing) = map.insert_full(elt, elt); + assert_eq!(existing, None); + assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0)); + assert_eq!(map.len(), i + 1); + } + + let len = map.len(); + for &elt in &present { + let (index, existing) = map.insert_full(elt, elt); + assert_eq!(existing, Some(elt)); + assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0)); + assert_eq!(map.len(), len); + } +} + +#[test] +fn insert_2() { + let mut map = IndexMap::with_capacity(16); + + let mut keys = vec![]; + keys.extend(0..16); + keys.extend(if cfg!(miri) { 32..64 } else { 128..267 }); + + for &i in &keys { + let old_map = map.clone(); + map.insert(i, ()); + for key in old_map.keys() { + if map.get(key).is_none() { + println!("old_map: {:?}", old_map); + println!("map: {:?}", map); + panic!("did not find {} in map", key); + } + } + } + + for &i in &keys { + assert!(map.get(&i).is_some(), "did not find {}", i); + } +} + +#[test] +fn insert_order() { + let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; + let mut map = IndexMap::new(); + + for &elt in &insert { + map.insert(elt, ()); + } + + assert_eq!(map.keys().count(), map.len()); + assert_eq!(map.keys().count(), insert.len()); + for (a, b) in insert.iter().zip(map.keys()) { + assert_eq!(a, b); + } + for (i, k) in (0..insert.len()).zip(map.keys()) { + assert_eq!(map.get_index(i).unwrap().0, k); + } +} + +#[test] +fn grow() { + let insert = [0, 4, 2, 12, 8, 7, 11]; + let not_present = [1, 3, 6, 9, 10]; + let mut map = IndexMap::with_capacity(insert.len()); + + for (i, &elt) in insert.iter().enumerate() { + assert_eq!(map.len(), i); + map.insert(elt, elt); + assert_eq!(map.len(), i + 1); + assert_eq!(map.get(&elt), Some(&elt)); + assert_eq!(map[&elt], elt); + } + + println!("{:?}", map); + for &elt in &insert { + map.insert(elt * 10, elt); + } + for &elt in &insert { + map.insert(elt * 100, elt); + } + for (i, &elt) in insert.iter().cycle().enumerate().take(100) { + map.insert(elt * 100 + i as i32, elt); + } + println!("{:?}", map); + for &elt in ¬_present { + assert!(map.get(&elt).is_none()); + } +} + +#[test] +fn reserve() { + let mut map = IndexMap::<usize, usize>::new(); + assert_eq!(map.capacity(), 0); + map.reserve(100); + let capacity = map.capacity(); + assert!(capacity >= 100); + for i in 0..capacity { + assert_eq!(map.len(), i); + map.insert(i, i * i); + assert_eq!(map.len(), i + 1); + assert_eq!(map.capacity(), capacity); + assert_eq!(map.get(&i), Some(&(i * i))); + } + map.insert(capacity, std::usize::MAX); + assert_eq!(map.len(), capacity + 1); + assert!(map.capacity() > capacity); + assert_eq!(map.get(&capacity), Some(&std::usize::MAX)); +} + +#[test] +fn try_reserve() { + let mut map = IndexMap::<usize, usize>::new(); + assert_eq!(map.capacity(), 0); + assert_eq!(map.try_reserve(100), Ok(())); + assert!(map.capacity() >= 100); + assert!(map.try_reserve(usize::MAX).is_err()); +} + +#[test] +fn shrink_to_fit() { + let mut map = IndexMap::<usize, usize>::new(); + assert_eq!(map.capacity(), 0); + for i in 0..100 { + assert_eq!(map.len(), i); + map.insert(i, i * i); + assert_eq!(map.len(), i + 1); + assert!(map.capacity() >= i + 1); + assert_eq!(map.get(&i), Some(&(i * i))); + map.shrink_to_fit(); + assert_eq!(map.len(), i + 1); + assert_eq!(map.capacity(), i + 1); + assert_eq!(map.get(&i), Some(&(i * i))); + } +} + +#[test] +fn remove() { + let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; + let mut map = IndexMap::new(); + + for &elt in &insert { + map.insert(elt, elt); + } + + assert_eq!(map.keys().count(), map.len()); + assert_eq!(map.keys().count(), insert.len()); + for (a, b) in insert.iter().zip(map.keys()) { + assert_eq!(a, b); + } + + let remove_fail = [99, 77]; + let remove = [4, 12, 8, 7]; + + for &key in &remove_fail { + assert!(map.swap_remove_full(&key).is_none()); + } + println!("{:?}", map); + for &key in &remove { + //println!("{:?}", map); + let index = map.get_full(&key).unwrap().0; + assert_eq!(map.swap_remove_full(&key), Some((index, key, key))); + } + println!("{:?}", map); + + for key in &insert { + assert_eq!(map.get(key).is_some(), !remove.contains(key)); + } + assert_eq!(map.len(), insert.len() - remove.len()); + assert_eq!(map.keys().count(), insert.len() - remove.len()); +} + +#[test] +fn remove_to_empty() { + let mut map = indexmap! { 0 => 0, 4 => 4, 5 => 5 }; + map.swap_remove(&5).unwrap(); + map.swap_remove(&4).unwrap(); + map.swap_remove(&0).unwrap(); + assert!(map.is_empty()); +} + +#[test] +fn swap_remove_index() { + let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; + let mut map = IndexMap::new(); + + for &elt in &insert { + map.insert(elt, elt * 2); + } + + let mut vector = insert.to_vec(); + let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1]; + + // check that the same swap remove sequence on vec and map + // have the same result. + for &rm in remove_sequence { + let out_vec = vector.swap_remove(rm); + let (out_map, _) = map.swap_remove_index(rm).unwrap(); + assert_eq!(out_vec, out_map); + } + assert_eq!(vector.len(), map.len()); + for (a, b) in vector.iter().zip(map.keys()) { + assert_eq!(a, b); + } +} + +#[test] +fn partial_eq_and_eq() { + let mut map_a = IndexMap::new(); + map_a.insert(1, "1"); + map_a.insert(2, "2"); + let mut map_b = map_a.clone(); + assert_eq!(map_a, map_b); + map_b.swap_remove(&1); + assert_ne!(map_a, map_b); + + let map_c: IndexMap<_, String> = map_b.into_iter().map(|(k, v)| (k, v.into())).collect(); + assert_ne!(map_a, map_c); + assert_ne!(map_c, map_a); +} + +#[test] +fn extend() { + let mut map = IndexMap::new(); + map.extend(vec![(&1, &2), (&3, &4)]); + map.extend(vec![(5, 6)]); + assert_eq!( + map.into_iter().collect::<Vec<_>>(), + vec![(1, 2), (3, 4), (5, 6)] + ); +} + +#[test] +fn entry() { + let mut map = IndexMap::new(); + + map.insert(1, "1"); + map.insert(2, "2"); + { + let e = map.entry(3); + assert_eq!(e.index(), 2); + let e = e.or_insert("3"); + assert_eq!(e, &"3"); + } + + let e = map.entry(2); + assert_eq!(e.index(), 1); + assert_eq!(e.key(), &2); + match e { + Entry::Occupied(ref e) => assert_eq!(e.get(), &"2"), + Entry::Vacant(_) => panic!(), + } + assert_eq!(e.or_insert("4"), &"2"); +} + +#[test] +fn entry_and_modify() { + let mut map = IndexMap::new(); + + map.insert(1, "1"); + map.entry(1).and_modify(|x| *x = "2"); + assert_eq!(Some(&"2"), map.get(&1)); + + map.entry(2).and_modify(|x| *x = "doesn't exist"); + assert_eq!(None, map.get(&2)); +} + +#[test] +fn entry_or_default() { + let mut map = IndexMap::new(); + + #[derive(Debug, PartialEq)] + enum TestEnum { + DefaultValue, + NonDefaultValue, + } + + impl Default for TestEnum { + fn default() -> Self { + TestEnum::DefaultValue + } + } + + map.insert(1, TestEnum::NonDefaultValue); + assert_eq!(&mut TestEnum::NonDefaultValue, map.entry(1).or_default()); + + assert_eq!(&mut TestEnum::DefaultValue, map.entry(2).or_default()); +} + +#[test] +fn occupied_entry_key() { + // These keys match hash and equality, but their addresses are distinct. + let (k1, k2) = (&mut 1, &mut 1); + let k1_ptr = k1 as *const i32; + let k2_ptr = k2 as *const i32; + assert_ne!(k1_ptr, k2_ptr); + + let mut map = IndexMap::new(); + map.insert(k1, "value"); + match map.entry(k2) { + Entry::Occupied(ref e) => { + // `OccupiedEntry::key` should reference the key in the map, + // not the key that was used to find the entry. + let ptr = *e.key() as *const i32; + assert_eq!(ptr, k1_ptr); + assert_ne!(ptr, k2_ptr); + } + Entry::Vacant(_) => panic!(), + } +} + +#[test] +fn keys() { + let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; + let map: IndexMap<_, _> = vec.into_iter().collect(); + let keys: Vec<_> = map.keys().copied().collect(); + assert_eq!(keys.len(), 3); + assert!(keys.contains(&1)); + assert!(keys.contains(&2)); + assert!(keys.contains(&3)); +} + +#[test] +fn into_keys() { + let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; + let map: IndexMap<_, _> = vec.into_iter().collect(); + let keys: Vec<i32> = map.into_keys().collect(); + assert_eq!(keys.len(), 3); + assert!(keys.contains(&1)); + assert!(keys.contains(&2)); + assert!(keys.contains(&3)); +} + +#[test] +fn values() { + let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; + let map: IndexMap<_, _> = vec.into_iter().collect(); + let values: Vec<_> = map.values().copied().collect(); + assert_eq!(values.len(), 3); + assert!(values.contains(&'a')); + assert!(values.contains(&'b')); + assert!(values.contains(&'c')); +} + +#[test] +fn values_mut() { + let vec = vec![(1, 1), (2, 2), (3, 3)]; + let mut map: IndexMap<_, _> = vec.into_iter().collect(); + for value in map.values_mut() { + *value *= 2 + } + let values: Vec<_> = map.values().copied().collect(); + assert_eq!(values.len(), 3); + assert!(values.contains(&2)); + assert!(values.contains(&4)); + assert!(values.contains(&6)); +} + +#[test] +fn into_values() { + let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; + let map: IndexMap<_, _> = vec.into_iter().collect(); + let values: Vec<char> = map.into_values().collect(); + assert_eq!(values.len(), 3); + assert!(values.contains(&'a')); + assert!(values.contains(&'b')); + assert!(values.contains(&'c')); +} + +#[test] +#[cfg(feature = "std")] +fn from_array() { + let map = IndexMap::from([(1, 2), (3, 4)]); + let mut expected = IndexMap::new(); + expected.insert(1, 2); + expected.insert(3, 4); + + assert_eq!(map, expected) +} + +#[test] +fn iter_default() { + struct K; + struct V; + fn assert_default<T>() + where + T: Default + Iterator, + { + assert!(T::default().next().is_none()); + } + assert_default::<Iter<'static, K, V>>(); + assert_default::<IterMut<'static, K, V>>(); + assert_default::<IntoIter<K, V>>(); + assert_default::<Keys<'static, K, V>>(); + assert_default::<IntoKeys<K, V>>(); + assert_default::<Values<'static, K, V>>(); + assert_default::<ValuesMut<'static, K, V>>(); + assert_default::<IntoValues<K, V>>(); +} diff --git a/vendor/indexmap/src/mutable_keys.rs b/vendor/indexmap/src/mutable_keys.rs index 35a90c472..7efc779b1 100644 --- a/vendor/indexmap/src/mutable_keys.rs +++ b/vendor/indexmap/src/mutable_keys.rs @@ -1,8 +1,6 @@ use core::hash::{BuildHasher, Hash}; -use super::{Equivalent, IndexMap}; - -pub struct PrivateMarker {} +use super::{Bucket, Entries, Equivalent, IndexMap}; /// Opt-in mutable access to keys. /// @@ -16,11 +14,15 @@ pub struct PrivateMarker {} /// implementing PartialEq, Eq, or Hash incorrectly would be). /// /// `use` this trait to enable its methods for `IndexMap`. -pub trait MutableKeys { +/// +/// This trait is sealed and cannot be implemented for types outside this crate. +pub trait MutableKeys: private::Sealed { type Key; type Value; /// Return item index, mutable reference to key and value + /// + /// Computes in **O(1)** time (average). fn get_full_mut2<Q: ?Sized>( &mut self, key: &Q, @@ -28,6 +30,13 @@ pub trait MutableKeys { where Q: Hash + Equivalent<Self::Key>; + /// Return mutable reference to key and value at an index. + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Computes in **O(1)** time. + fn get_index_mut2(&mut self, index: usize) -> Option<(&mut Self::Key, &mut Self::Value)>; + /// Scan through each key-value pair in the map and keep those where the /// closure `keep` returns `true`. /// @@ -38,11 +47,6 @@ pub trait MutableKeys { fn retain2<F>(&mut self, keep: F) where F: FnMut(&mut Self::Key, &mut Self::Value) -> bool; - - /// This method is not useful in itself – it is there to “seal” the trait - /// for external implementation, so that we can add methods without - /// causing breaking changes. - fn __private_marker(&self) -> PrivateMarker; } /// Opt-in mutable access to keys. @@ -55,11 +59,21 @@ where { type Key = K; type Value = V; + fn get_full_mut2<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &mut K, &mut V)> where Q: Hash + Equivalent<K>, { - self.get_full_mut2_impl(key) + if let Some(i) = self.get_index_of(key) { + let entry = &mut self.as_entries_mut()[i]; + Some((i, &mut entry.key, &mut entry.value)) + } else { + None + } + } + + fn get_index_mut2(&mut self, index: usize) -> Option<(&mut K, &mut V)> { + self.as_entries_mut().get_mut(index).map(Bucket::muts) } fn retain2<F>(&mut self, keep: F) @@ -68,8 +82,10 @@ where { self.retain_mut(keep) } +} - fn __private_marker(&self) -> PrivateMarker { - PrivateMarker {} - } +mod private { + pub trait Sealed {} + + impl<K, V, S> Sealed for super::IndexMap<K, V, S> {} } diff --git a/vendor/indexmap/src/rayon/map.rs b/vendor/indexmap/src/rayon/map.rs index 8819f13ed..d5325f2ee 100644 --- a/vendor/indexmap/src/rayon/map.rs +++ b/vendor/indexmap/src/rayon/map.rs @@ -2,24 +2,23 @@ //! //! You will rarely need to interact with this module directly unless you need to name one of the //! iterator types. -//! -//! Requires crate feature `"rayon"` use super::collect; use rayon::iter::plumbing::{Consumer, ProducerCallback, UnindexedConsumer}; use rayon::prelude::*; use crate::vec::Vec; +use alloc::boxed::Box; use core::cmp::Ordering; use core::fmt; use core::hash::{BuildHasher, Hash}; use core::ops::RangeBounds; +use crate::map::Slice; use crate::Bucket; use crate::Entries; use crate::IndexMap; -/// Requires crate feature `"rayon"`. impl<K, V, S> IntoParallelIterator for IndexMap<K, V, S> where K: Send, @@ -35,6 +34,21 @@ where } } +impl<K, V> IntoParallelIterator for Box<Slice<K, V>> +where + K: Send, + V: Send, +{ + type Item = (K, V); + type Iter = IntoParIter<K, V>; + + fn into_par_iter(self) -> Self::Iter { + IntoParIter { + entries: self.into_entries(), + } + } +} + /// A parallel owning iterator over the entries of a `IndexMap`. /// /// This `struct` is created by the [`into_par_iter`] method on [`IndexMap`] @@ -63,7 +77,6 @@ impl<K: Send, V: Send> IndexedParallelIterator for IntoParIter<K, V> { indexed_parallel_iterator_methods!(Bucket::key_value); } -/// Requires crate feature `"rayon"`. impl<'a, K, V, S> IntoParallelIterator for &'a IndexMap<K, V, S> where K: Sync, @@ -79,6 +92,21 @@ where } } +impl<'a, K, V> IntoParallelIterator for &'a Slice<K, V> +where + K: Sync, + V: Sync, +{ + type Item = (&'a K, &'a V); + type Iter = ParIter<'a, K, V>; + + fn into_par_iter(self) -> Self::Iter { + ParIter { + entries: &self.entries, + } + } +} + /// A parallel iterator over the entries of a `IndexMap`. /// /// This `struct` is created by the [`par_iter`] method on [`IndexMap`] @@ -113,7 +141,6 @@ impl<K: Sync, V: Sync> IndexedParallelIterator for ParIter<'_, K, V> { indexed_parallel_iterator_methods!(Bucket::refs); } -/// Requires crate feature `"rayon"`. impl<'a, K, V, S> IntoParallelIterator for &'a mut IndexMap<K, V, S> where K: Sync + Send, @@ -129,6 +156,21 @@ where } } +impl<'a, K, V> IntoParallelIterator for &'a mut Slice<K, V> +where + K: Sync + Send, + V: Send, +{ + type Item = (&'a K, &'a mut V); + type Iter = ParIterMut<'a, K, V>; + + fn into_par_iter(self) -> Self::Iter { + ParIterMut { + entries: &mut self.entries, + } + } +} + /// A parallel mutable iterator over the entries of a `IndexMap`. /// /// This `struct` is created by the [`par_iter_mut`] method on [`IndexMap`] @@ -157,7 +199,6 @@ impl<K: Sync + Send, V: Send> IndexedParallelIterator for ParIterMut<'_, K, V> { indexed_parallel_iterator_methods!(Bucket::ref_mut); } -/// Requires crate feature `"rayon"`. impl<'a, K, V, S> ParallelDrainRange<usize> for &'a mut IndexMap<K, V, S> where K: Send, @@ -225,6 +266,37 @@ where } } +/// Parallel iterator methods and other parallel methods. +/// +/// The following methods **require crate feature `"rayon"`**. +/// +/// See also the `IntoParallelIterator` implementations. +impl<K, V> Slice<K, V> +where + K: Sync, + V: Sync, +{ + /// Return a parallel iterator over the keys of the map slice. + /// + /// While parallel iterators can process items in any order, their relative order + /// in the slice is still preserved for operations like `reduce` and `collect`. + pub fn par_keys(&self) -> ParKeys<'_, K, V> { + ParKeys { + entries: &self.entries, + } + } + + /// Return a parallel iterator over the values of the map slice. + /// + /// While parallel iterators can process items in any order, their relative order + /// in the slice is still preserved for operations like `reduce` and `collect`. + pub fn par_values(&self) -> ParValues<'_, K, V> { + ParValues { + entries: &self.entries, + } + } +} + impl<K, V, S> IndexMap<K, V, S> where K: Hash + Eq + Sync, @@ -314,7 +386,6 @@ impl<K: Sync, V: Sync> IndexedParallelIterator for ParValues<'_, K, V> { indexed_parallel_iterator_methods!(Bucket::value_ref); } -/// Requires crate feature `"rayon"`. impl<K, V, S> IndexMap<K, V, S> where K: Send, @@ -331,6 +402,22 @@ where } } +impl<K, V> Slice<K, V> +where + K: Send, + V: Send, +{ + /// Return a parallel iterator over mutable references to the the values of the map slice. + /// + /// While parallel iterators can process items in any order, their relative order + /// in the slice is still preserved for operations like `reduce` and `collect`. + pub fn par_values_mut(&mut self) -> ParValuesMut<'_, K, V> { + ParValuesMut { + entries: &mut self.entries, + } + } +} + impl<K, V, S> IndexMap<K, V, S> where K: Hash + Eq + Send, @@ -406,6 +493,18 @@ where entries.par_sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); IntoParIter { entries } } + + /// Sort the map’s key-value pairs in place and in parallel, using a sort-key extraction + /// function. + pub fn par_sort_by_cached_key<T, F>(&mut self, sort_key: F) + where + T: Ord + Send, + F: Fn(&K, &V) -> T + Sync, + { + self.with_entries(move |entries| { + entries.par_sort_by_cached_key(move |a| sort_key(&a.key, &a.value)); + }); + } } /// A parallel mutable iterator over the values of a `IndexMap`. @@ -436,7 +535,6 @@ impl<K: Send, V: Send> IndexedParallelIterator for ParValuesMut<'_, K, V> { indexed_parallel_iterator_methods!(Bucket::value_mut); } -/// Requires crate feature `"rayon"`. impl<K, V, S> FromParallelIterator<(K, V)> for IndexMap<K, V, S> where K: Eq + Hash + Send, @@ -457,7 +555,6 @@ where } } -/// Requires crate feature `"rayon"`. impl<K, V, S> ParallelExtend<(K, V)> for IndexMap<K, V, S> where K: Eq + Hash + Send, @@ -474,7 +571,6 @@ where } } -/// Requires crate feature `"rayon"`. impl<'a, K: 'a, V: 'a, S> ParallelExtend<(&'a K, &'a V)> for IndexMap<K, V, S> where K: Copy + Eq + Hash + Send + Sync, diff --git a/vendor/indexmap/src/rayon/set.rs b/vendor/indexmap/src/rayon/set.rs index 6749dc0d7..0fc478ef0 100644 --- a/vendor/indexmap/src/rayon/set.rs +++ b/vendor/indexmap/src/rayon/set.rs @@ -2,25 +2,24 @@ //! //! You will rarely need to interact with this module directly unless you need to name one of the //! iterator types. -//! -//! Requires crate feature `"rayon"`. use super::collect; use rayon::iter::plumbing::{Consumer, ProducerCallback, UnindexedConsumer}; use rayon::prelude::*; use crate::vec::Vec; +use alloc::boxed::Box; use core::cmp::Ordering; use core::fmt; use core::hash::{BuildHasher, Hash}; use core::ops::RangeBounds; +use crate::set::Slice; use crate::Entries; use crate::IndexSet; type Bucket<T> = crate::Bucket<T, ()>; -/// Requires crate feature `"rayon"`. impl<T, S> IntoParallelIterator for IndexSet<T, S> where T: Send, @@ -35,6 +34,20 @@ where } } +impl<T> IntoParallelIterator for Box<Slice<T>> +where + T: Send, +{ + type Item = T; + type Iter = IntoParIter<T>; + + fn into_par_iter(self) -> Self::Iter { + IntoParIter { + entries: self.into_entries(), + } + } +} + /// A parallel owning iterator over the items of a `IndexSet`. /// /// This `struct` is created by the [`into_par_iter`] method on [`IndexSet`] @@ -63,7 +76,6 @@ impl<T: Send> IndexedParallelIterator for IntoParIter<T> { indexed_parallel_iterator_methods!(Bucket::key); } -/// Requires crate feature `"rayon"`. impl<'a, T, S> IntoParallelIterator for &'a IndexSet<T, S> where T: Sync, @@ -78,6 +90,20 @@ where } } +impl<'a, T> IntoParallelIterator for &'a Slice<T> +where + T: Sync, +{ + type Item = &'a T; + type Iter = ParIter<'a, T>; + + fn into_par_iter(self) -> Self::Iter { + ParIter { + entries: &self.entries, + } + } +} + /// A parallel iterator over the items of a `IndexSet`. /// /// This `struct` is created by the [`par_iter`] method on [`IndexSet`] @@ -112,7 +138,6 @@ impl<T: Sync> IndexedParallelIterator for ParIter<'_, T> { indexed_parallel_iterator_methods!(Bucket::key_ref); } -/// Requires crate feature `"rayon"`. impl<'a, T, S> ParallelDrainRange<usize> for &'a mut IndexSet<T, S> where T: Send, @@ -540,9 +565,19 @@ where entries.par_sort_unstable_by(move |a, b| cmp(&a.key, &b.key)); IntoParIter { entries } } + + /// Sort the set’s values in place and in parallel, using a key extraction function. + pub fn par_sort_by_cached_key<K, F>(&mut self, sort_key: F) + where + K: Ord + Send, + F: Fn(&T) -> K + Sync, + { + self.with_entries(move |entries| { + entries.par_sort_by_cached_key(move |a| sort_key(&a.key)); + }); + } } -/// Requires crate feature `"rayon"`. impl<T, S> FromParallelIterator<T> for IndexSet<T, S> where T: Eq + Hash + Send, @@ -562,7 +597,6 @@ where } } -/// Requires crate feature `"rayon"`. impl<T, S> ParallelExtend<T> for IndexSet<T, S> where T: Eq + Hash + Send, @@ -578,7 +612,6 @@ where } } -/// Requires crate feature `"rayon"`. impl<'a, T: 'a, S> ParallelExtend<&'a T> for IndexSet<T, S> where T: Copy + Eq + Hash + Send + Sync, diff --git a/vendor/indexmap/src/serde.rs b/vendor/indexmap/src/serde.rs index c6dd6d5ea..37de3e3e3 100644 --- a/vendor/indexmap/src/serde.rs +++ b/vendor/indexmap/src/serde.rs @@ -10,7 +10,6 @@ use core::marker::PhantomData; use crate::IndexMap; -/// Requires crate feature `"serde"` or `"serde-1"` impl<K, V, S> Serialize for IndexMap<K, V, S> where K: Serialize + Hash + Eq, @@ -54,7 +53,6 @@ where } } -/// Requires crate feature `"serde"` or `"serde-1"` impl<'de, K, V, S> Deserialize<'de> for IndexMap<K, V, S> where K: Deserialize<'de> + Eq + Hash, @@ -85,7 +83,6 @@ where use crate::IndexSet; -/// Requires crate feature `"serde"` or `"serde-1"` impl<T, S> Serialize for IndexSet<T, S> where T: Serialize + Hash + Eq, @@ -127,7 +124,6 @@ where } } -/// Requires crate feature `"serde"` or `"serde-1"` impl<'de, T, S> Deserialize<'de> for IndexSet<T, S> where T: Deserialize<'de> + Eq + Hash, diff --git a/vendor/indexmap/src/set.rs b/vendor/indexmap/src/set.rs index 372894742..dbee481f1 100644 --- a/vendor/indexmap/src/set.rs +++ b/vendor/indexmap/src/set.rs @@ -1,18 +1,28 @@ //! A hash set implemented using `IndexMap` +mod iter; +mod slice; + +#[cfg(test)] +mod tests; + +pub use self::iter::{Difference, Drain, Intersection, IntoIter, Iter, SymmetricDifference, Union}; +pub use self::slice::Slice; + #[cfg(feature = "rayon")] pub use crate::rayon::set as rayon; +use crate::TryReserveError; -#[cfg(has_std)] +#[cfg(feature = "std")] use std::collections::hash_map::RandomState; -use crate::vec::{self, Vec}; +use crate::util::try_simplify_range; +use alloc::boxed::Box; +use alloc::vec::Vec; use core::cmp::Ordering; use core::fmt; use core::hash::{BuildHasher, Hash}; -use core::iter::{Chain, FusedIterator}; use core::ops::{BitAnd, BitOr, BitXor, Index, RangeBounds, Sub}; -use core::slice; use super::{Entries, Equivalent, IndexMap}; @@ -59,11 +69,11 @@ type Bucket<T> = super::Bucket<T, ()>; /// assert!(letters.contains(&'u')); /// assert!(!letters.contains(&'y')); /// ``` -#[cfg(has_std)] +#[cfg(feature = "std")] pub struct IndexSet<T, S = RandomState> { pub(crate) map: IndexMap<T, (), S>, } -#[cfg(not(has_std))] +#[cfg(not(feature = "std"))] pub struct IndexSet<T, S> { pub(crate) map: IndexMap<T, (), S>, } @@ -124,7 +134,8 @@ where } } -#[cfg(has_std)] +#[cfg(feature = "std")] +#[cfg_attr(docsrs, doc(cfg(feature = "std")))] impl<T> IndexSet<T> { /// Create a new set. (Does not allocate.) pub fn new() -> Self { @@ -165,6 +176,11 @@ impl<T, S> IndexSet<T, S> { } } + /// Return the number of elements the set can hold without reallocating. + /// + /// This number is a lower bound; the set might be able to hold more, + /// but is guaranteed to be able to hold at least this many. + /// /// Computes in **O(1)** time. pub fn capacity(&self) -> usize { self.map.capacity() @@ -191,9 +207,7 @@ impl<T, S> IndexSet<T, S> { /// Return an iterator over the values of the set, in their order pub fn iter(&self) -> Iter<'_, T> { - Iter { - iter: self.map.as_entries().iter(), - } + Iter::new(self.as_entries()) } /// Remove all elements in the set, while preserving its capacity. @@ -227,9 +241,7 @@ impl<T, S> IndexSet<T, S> { where R: RangeBounds<usize>, { - Drain { - iter: self.map.drain(range).iter, - } + Drain::new(self.map.core.drain(range)) } /// Splits the collection into two at the given index. @@ -261,6 +273,37 @@ where self.map.reserve(additional); } + /// Reserve capacity for `additional` more values, without over-allocating. + /// + /// Unlike `reserve`, this does not deliberately over-allocate the entry capacity to avoid + /// frequent re-allocations. However, the underlying data structures may still have internal + /// capacity requirements, and the allocator itself may give more space than requested, so this + /// cannot be relied upon to be precisely minimal. + /// + /// Computes in **O(n)** time. + pub fn reserve_exact(&mut self, additional: usize) { + self.map.reserve_exact(additional); + } + + /// Try to reserve capacity for `additional` more values. + /// + /// Computes in **O(n)** time. + pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.map.try_reserve(additional) + } + + /// Try to reserve capacity for `additional` more values, without over-allocating. + /// + /// Unlike `try_reserve`, this does not deliberately over-allocate the entry capacity to avoid + /// frequent re-allocations. However, the underlying data structures may still have internal + /// capacity requirements, and the allocator itself may give more space than requested, so this + /// cannot be relied upon to be precisely minimal. + /// + /// Computes in **O(n)** time. + pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.map.try_reserve_exact(additional) + } + /// Shrink the capacity of the set as much as possible. /// /// Computes in **O(n)** time. @@ -297,16 +340,8 @@ where /// /// Computes in **O(1)** time (amortized average). pub fn insert_full(&mut self, value: T) -> (usize, bool) { - use super::map::Entry::*; - - match self.map.entry(value) { - Occupied(e) => (e.index(), false), - Vacant(e) => { - let index = e.index(); - e.insert(()); - (index, true) - } - } + let (index, existing) = self.map.insert_full(value, ()); + (index, existing.is_none()) } /// Return an iterator over the values that are in `self` but not `other`. @@ -316,10 +351,7 @@ where where S2: BuildHasher, { - Difference { - iter: self.iter(), - other, - } + Difference::new(self, other) } /// Return an iterator over the values that are in `self` or `other`, @@ -334,9 +366,7 @@ where where S2: BuildHasher, { - SymmetricDifference { - iter: self.difference(other).chain(other.difference(self)), - } + SymmetricDifference::new(self, other) } /// Return an iterator over the values that are in both `self` and `other`. @@ -346,10 +376,7 @@ where where S2: BuildHasher, { - Intersection { - iter: self.iter(), - other, - } + Intersection::new(self, other) } /// Return an iterator over all values that are in `self` or `other`. @@ -360,9 +387,7 @@ where where S2: BuildHasher, { - Union { - iter: self.iter().chain(other.difference(self)), - } + Union::new(self, other) } /// Return `true` if an equivalent to `value` exists in the set. @@ -604,9 +629,7 @@ where { let mut entries = self.into_entries(); entries.sort_by(move |a, b| cmp(&a.key, &b.key)); - IntoIter { - iter: entries.into_iter(), - } + IntoIter::new(entries) } /// Sort the set's values by their default ordering. @@ -619,7 +642,7 @@ where self.map.sort_unstable_keys() } - /// Sort the set's values in place using the comparison funtion `cmp`. + /// Sort the set's values in place using the comparison function `cmp`. /// /// Computes in **O(n log n)** time. The sort is unstable. pub fn sort_unstable_by<F>(&mut self, mut cmp: F) @@ -637,9 +660,25 @@ where { let mut entries = self.into_entries(); entries.sort_unstable_by(move |a, b| cmp(&a.key, &b.key)); - IntoIter { - iter: entries.into_iter(), - } + IntoIter::new(entries) + } + + /// Sort the set’s values in place using a key extraction function. + /// + /// During sorting, the function is called at most once per entry, by using temporary storage + /// to remember the results of its evaluation. The order of calls to the function is + /// unspecified and may change between versions of `indexmap` or the standard library. + /// + /// Computes in **O(m n + n log n + c)** time () and **O(n)** space, where the function is + /// **O(m)**, *n* is the length of the map, and *c* the capacity. The sort is stable. + pub fn sort_by_cached_key<K, F>(&mut self, mut sort_key: F) + where + K: Ord, + F: FnMut(&T) -> K, + { + self.with_entries(move |entries| { + entries.sort_by_cached_key(move |a| sort_key(&a.key)); + }); } /// Reverses the order of the set’s values in place. @@ -651,6 +690,20 @@ where } impl<T, S> IndexSet<T, S> { + /// Returns a slice of all the values in the set. + /// + /// Computes in **O(1)** time. + pub fn as_slice(&self) -> &Slice<T> { + Slice::from_slice(self.as_entries()) + } + + /// Converts into a boxed slice of all the values in the set. + /// + /// Note that this will drop the inner hash table and any excess capacity. + pub fn into_boxed_slice(self) -> Box<Slice<T>> { + Slice::from_boxed(self.into_entries().into_boxed_slice()) + } + /// Get a value by index /// /// Valid indices are *0 <= index < self.len()* @@ -660,6 +713,17 @@ impl<T, S> IndexSet<T, S> { self.as_entries().get(index).map(Bucket::key_ref) } + /// Returns a slice of values in the given range of indices. + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Computes in **O(1)** time. + pub fn get_range<R: RangeBounds<usize>>(&self, range: R) -> Option<&Slice<T>> { + let entries = self.as_entries(); + let range = try_simplify_range(range, entries.len())?; + entries.get(range).map(Slice::from_slice) + } + /// Get the first value /// /// Computes in **O(1)** time. @@ -761,141 +825,6 @@ impl<T, S> Index<usize> for IndexSet<T, S> { } } -/// An owning iterator over the items of a `IndexSet`. -/// -/// This `struct` is created by the [`into_iter`] method on [`IndexSet`] -/// (provided by the `IntoIterator` trait). See its documentation for more. -/// -/// [`IndexSet`]: struct.IndexSet.html -/// [`into_iter`]: struct.IndexSet.html#method.into_iter -pub struct IntoIter<T> { - iter: vec::IntoIter<Bucket<T>>, -} - -impl<T> Iterator for IntoIter<T> { - type Item = T; - - iterator_methods!(Bucket::key); -} - -impl<T> DoubleEndedIterator for IntoIter<T> { - double_ended_iterator_methods!(Bucket::key); -} - -impl<T> ExactSizeIterator for IntoIter<T> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<T> FusedIterator for IntoIter<T> {} - -impl<T: fmt::Debug> fmt::Debug for IntoIter<T> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.iter.as_slice().iter().map(Bucket::key_ref); - f.debug_list().entries(iter).finish() - } -} - -/// An iterator over the items of a `IndexSet`. -/// -/// This `struct` is created by the [`iter`] method on [`IndexSet`]. -/// See its documentation for more. -/// -/// [`IndexSet`]: struct.IndexSet.html -/// [`iter`]: struct.IndexSet.html#method.iter -pub struct Iter<'a, T> { - iter: slice::Iter<'a, Bucket<T>>, -} - -impl<'a, T> Iterator for Iter<'a, T> { - type Item = &'a T; - - iterator_methods!(Bucket::key_ref); -} - -impl<T> DoubleEndedIterator for Iter<'_, T> { - double_ended_iterator_methods!(Bucket::key_ref); -} - -impl<T> ExactSizeIterator for Iter<'_, T> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<T> FusedIterator for Iter<'_, T> {} - -impl<T> Clone for Iter<'_, T> { - fn clone(&self) -> Self { - Iter { - iter: self.iter.clone(), - } - } -} - -impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.clone()).finish() - } -} - -/// A draining iterator over the items of a `IndexSet`. -/// -/// This `struct` is created by the [`drain`] method on [`IndexSet`]. -/// See its documentation for more. -/// -/// [`IndexSet`]: struct.IndexSet.html -/// [`drain`]: struct.IndexSet.html#method.drain -pub struct Drain<'a, T> { - iter: vec::Drain<'a, Bucket<T>>, -} - -impl<T> Iterator for Drain<'_, T> { - type Item = T; - - iterator_methods!(Bucket::key); -} - -impl<T> DoubleEndedIterator for Drain<'_, T> { - double_ended_iterator_methods!(Bucket::key); -} - -impl<T> ExactSizeIterator for Drain<'_, T> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<T> FusedIterator for Drain<'_, T> {} - -impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.iter.as_slice().iter().map(Bucket::key_ref); - f.debug_list().entries(iter).finish() - } -} - -impl<'a, T, S> IntoIterator for &'a IndexSet<T, S> { - type Item = &'a T; - type IntoIter = Iter<'a, T>; - - fn into_iter(self) -> Self::IntoIter { - self.iter() - } -} - -impl<T, S> IntoIterator for IndexSet<T, S> { - type Item = T; - type IntoIter = IntoIter<T>; - - fn into_iter(self) -> Self::IntoIter { - IntoIter { - iter: self.into_entries().into_iter(), - } - } -} - impl<T, S> FromIterator<T> for IndexSet<T, S> where T: Hash + Eq, @@ -909,7 +838,8 @@ where } } -#[cfg(has_std)] +#[cfg(feature = "std")] +#[cfg_attr(docsrs, doc(cfg(feature = "std")))] impl<T, const N: usize> From<[T; N]> for IndexSet<T, RandomState> where T: Eq + Hash, @@ -1014,310 +944,6 @@ where } } -/// A lazy iterator producing elements in the difference of `IndexSet`s. -/// -/// This `struct` is created by the [`difference`] method on [`IndexSet`]. -/// See its documentation for more. -/// -/// [`IndexSet`]: struct.IndexSet.html -/// [`difference`]: struct.IndexSet.html#method.difference -pub struct Difference<'a, T, S> { - iter: Iter<'a, T>, - other: &'a IndexSet<T, S>, -} - -impl<'a, T, S> Iterator for Difference<'a, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ - type Item = &'a T; - - fn next(&mut self) -> Option<Self::Item> { - while let Some(item) = self.iter.next() { - if !self.other.contains(item) { - return Some(item); - } - } - None - } - - fn size_hint(&self) -> (usize, Option<usize>) { - (0, self.iter.size_hint().1) - } -} - -impl<T, S> DoubleEndedIterator for Difference<'_, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ - fn next_back(&mut self) -> Option<Self::Item> { - while let Some(item) = self.iter.next_back() { - if !self.other.contains(item) { - return Some(item); - } - } - None - } -} - -impl<T, S> FusedIterator for Difference<'_, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ -} - -impl<T, S> Clone for Difference<'_, T, S> { - fn clone(&self) -> Self { - Difference { - iter: self.iter.clone(), - ..*self - } - } -} - -impl<T, S> fmt::Debug for Difference<'_, T, S> -where - T: fmt::Debug + Eq + Hash, - S: BuildHasher, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.clone()).finish() - } -} - -/// A lazy iterator producing elements in the intersection of `IndexSet`s. -/// -/// This `struct` is created by the [`intersection`] method on [`IndexSet`]. -/// See its documentation for more. -/// -/// [`IndexSet`]: struct.IndexSet.html -/// [`intersection`]: struct.IndexSet.html#method.intersection -pub struct Intersection<'a, T, S> { - iter: Iter<'a, T>, - other: &'a IndexSet<T, S>, -} - -impl<'a, T, S> Iterator for Intersection<'a, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ - type Item = &'a T; - - fn next(&mut self) -> Option<Self::Item> { - while let Some(item) = self.iter.next() { - if self.other.contains(item) { - return Some(item); - } - } - None - } - - fn size_hint(&self) -> (usize, Option<usize>) { - (0, self.iter.size_hint().1) - } -} - -impl<T, S> DoubleEndedIterator for Intersection<'_, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ - fn next_back(&mut self) -> Option<Self::Item> { - while let Some(item) = self.iter.next_back() { - if self.other.contains(item) { - return Some(item); - } - } - None - } -} - -impl<T, S> FusedIterator for Intersection<'_, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ -} - -impl<T, S> Clone for Intersection<'_, T, S> { - fn clone(&self) -> Self { - Intersection { - iter: self.iter.clone(), - ..*self - } - } -} - -impl<T, S> fmt::Debug for Intersection<'_, T, S> -where - T: fmt::Debug + Eq + Hash, - S: BuildHasher, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.clone()).finish() - } -} - -/// A lazy iterator producing elements in the symmetric difference of `IndexSet`s. -/// -/// This `struct` is created by the [`symmetric_difference`] method on -/// [`IndexSet`]. See its documentation for more. -/// -/// [`IndexSet`]: struct.IndexSet.html -/// [`symmetric_difference`]: struct.IndexSet.html#method.symmetric_difference -pub struct SymmetricDifference<'a, T, S1, S2> { - iter: Chain<Difference<'a, T, S2>, Difference<'a, T, S1>>, -} - -impl<'a, T, S1, S2> Iterator for SymmetricDifference<'a, T, S1, S2> -where - T: Eq + Hash, - S1: BuildHasher, - S2: BuildHasher, -{ - type Item = &'a T; - - fn next(&mut self) -> Option<Self::Item> { - self.iter.next() - } - - fn size_hint(&self) -> (usize, Option<usize>) { - self.iter.size_hint() - } - - fn fold<B, F>(self, init: B, f: F) -> B - where - F: FnMut(B, Self::Item) -> B, - { - self.iter.fold(init, f) - } -} - -impl<T, S1, S2> DoubleEndedIterator for SymmetricDifference<'_, T, S1, S2> -where - T: Eq + Hash, - S1: BuildHasher, - S2: BuildHasher, -{ - fn next_back(&mut self) -> Option<Self::Item> { - self.iter.next_back() - } - - fn rfold<B, F>(self, init: B, f: F) -> B - where - F: FnMut(B, Self::Item) -> B, - { - self.iter.rfold(init, f) - } -} - -impl<T, S1, S2> FusedIterator for SymmetricDifference<'_, T, S1, S2> -where - T: Eq + Hash, - S1: BuildHasher, - S2: BuildHasher, -{ -} - -impl<T, S1, S2> Clone for SymmetricDifference<'_, T, S1, S2> { - fn clone(&self) -> Self { - SymmetricDifference { - iter: self.iter.clone(), - } - } -} - -impl<T, S1, S2> fmt::Debug for SymmetricDifference<'_, T, S1, S2> -where - T: fmt::Debug + Eq + Hash, - S1: BuildHasher, - S2: BuildHasher, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.clone()).finish() - } -} - -/// A lazy iterator producing elements in the union of `IndexSet`s. -/// -/// This `struct` is created by the [`union`] method on [`IndexSet`]. -/// See its documentation for more. -/// -/// [`IndexSet`]: struct.IndexSet.html -/// [`union`]: struct.IndexSet.html#method.union -pub struct Union<'a, T, S> { - iter: Chain<Iter<'a, T>, Difference<'a, T, S>>, -} - -impl<'a, T, S> Iterator for Union<'a, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ - type Item = &'a T; - - fn next(&mut self) -> Option<Self::Item> { - self.iter.next() - } - - fn size_hint(&self) -> (usize, Option<usize>) { - self.iter.size_hint() - } - - fn fold<B, F>(self, init: B, f: F) -> B - where - F: FnMut(B, Self::Item) -> B, - { - self.iter.fold(init, f) - } -} - -impl<T, S> DoubleEndedIterator for Union<'_, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ - fn next_back(&mut self) -> Option<Self::Item> { - self.iter.next_back() - } - - fn rfold<B, F>(self, init: B, f: F) -> B - where - F: FnMut(B, Self::Item) -> B, - { - self.iter.rfold(init, f) - } -} - -impl<T, S> FusedIterator for Union<'_, T, S> -where - T: Eq + Hash, - S: BuildHasher, -{ -} - -impl<T, S> Clone for Union<'_, T, S> { - fn clone(&self) -> Self { - Union { - iter: self.iter.clone(), - } - } -} - -impl<T, S> fmt::Debug for Union<'_, T, S> -where - T: fmt::Debug + Eq + Hash, - S: BuildHasher, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.clone()).finish() - } -} - impl<T, S1, S2> BitAnd<&IndexSet<T, S2>> for &IndexSet<T, S1> where T: Eq + Hash + Clone, @@ -1383,530 +1009,3 @@ where self.difference(other).cloned().collect() } } - -#[cfg(test)] -mod tests { - use super::*; - use std::string::String; - - #[test] - fn it_works() { - let mut set = IndexSet::new(); - assert_eq!(set.is_empty(), true); - set.insert(1); - set.insert(1); - assert_eq!(set.len(), 1); - assert!(set.get(&1).is_some()); - assert_eq!(set.is_empty(), false); - } - - #[test] - fn new() { - let set = IndexSet::<String>::new(); - println!("{:?}", set); - assert_eq!(set.capacity(), 0); - assert_eq!(set.len(), 0); - assert_eq!(set.is_empty(), true); - } - - #[test] - fn insert() { - let insert = [0, 4, 2, 12, 8, 7, 11, 5]; - let not_present = [1, 3, 6, 9, 10]; - let mut set = IndexSet::with_capacity(insert.len()); - - for (i, &elt) in insert.iter().enumerate() { - assert_eq!(set.len(), i); - set.insert(elt); - assert_eq!(set.len(), i + 1); - assert_eq!(set.get(&elt), Some(&elt)); - } - println!("{:?}", set); - - for &elt in ¬_present { - assert!(set.get(&elt).is_none()); - } - } - - #[test] - fn insert_full() { - let insert = vec![9, 2, 7, 1, 4, 6, 13]; - let present = vec![1, 6, 2]; - let mut set = IndexSet::with_capacity(insert.len()); - - for (i, &elt) in insert.iter().enumerate() { - assert_eq!(set.len(), i); - let (index, success) = set.insert_full(elt); - assert!(success); - assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); - assert_eq!(set.len(), i + 1); - } - - let len = set.len(); - for &elt in &present { - let (index, success) = set.insert_full(elt); - assert!(!success); - assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); - assert_eq!(set.len(), len); - } - } - - #[test] - fn insert_2() { - let mut set = IndexSet::with_capacity(16); - - let mut values = vec![]; - values.extend(0..16); - values.extend(if cfg!(miri) { 32..64 } else { 128..267 }); - - for &i in &values { - let old_set = set.clone(); - set.insert(i); - for value in old_set.iter() { - if set.get(value).is_none() { - println!("old_set: {:?}", old_set); - println!("set: {:?}", set); - panic!("did not find {} in set", value); - } - } - } - - for &i in &values { - assert!(set.get(&i).is_some(), "did not find {}", i); - } - } - - #[test] - fn insert_dup() { - let mut elements = vec![0, 2, 4, 6, 8]; - let mut set: IndexSet<u8> = elements.drain(..).collect(); - { - let (i, v) = set.get_full(&0).unwrap(); - assert_eq!(set.len(), 5); - assert_eq!(i, 0); - assert_eq!(*v, 0); - } - { - let inserted = set.insert(0); - let (i, v) = set.get_full(&0).unwrap(); - assert_eq!(set.len(), 5); - assert_eq!(inserted, false); - assert_eq!(i, 0); - assert_eq!(*v, 0); - } - } - - #[test] - fn insert_order() { - let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; - let mut set = IndexSet::new(); - - for &elt in &insert { - set.insert(elt); - } - - assert_eq!(set.iter().count(), set.len()); - assert_eq!(set.iter().count(), insert.len()); - for (a, b) in insert.iter().zip(set.iter()) { - assert_eq!(a, b); - } - for (i, v) in (0..insert.len()).zip(set.iter()) { - assert_eq!(set.get_index(i).unwrap(), v); - } - } - - #[test] - fn replace() { - let replace = [0, 4, 2, 12, 8, 7, 11, 5]; - let not_present = [1, 3, 6, 9, 10]; - let mut set = IndexSet::with_capacity(replace.len()); - - for (i, &elt) in replace.iter().enumerate() { - assert_eq!(set.len(), i); - set.replace(elt); - assert_eq!(set.len(), i + 1); - assert_eq!(set.get(&elt), Some(&elt)); - } - println!("{:?}", set); - - for &elt in ¬_present { - assert!(set.get(&elt).is_none()); - } - } - - #[test] - fn replace_full() { - let replace = vec![9, 2, 7, 1, 4, 6, 13]; - let present = vec![1, 6, 2]; - let mut set = IndexSet::with_capacity(replace.len()); - - for (i, &elt) in replace.iter().enumerate() { - assert_eq!(set.len(), i); - let (index, replaced) = set.replace_full(elt); - assert!(replaced.is_none()); - assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); - assert_eq!(set.len(), i + 1); - } - - let len = set.len(); - for &elt in &present { - let (index, replaced) = set.replace_full(elt); - assert_eq!(Some(elt), replaced); - assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); - assert_eq!(set.len(), len); - } - } - - #[test] - fn replace_2() { - let mut set = IndexSet::with_capacity(16); - - let mut values = vec![]; - values.extend(0..16); - values.extend(if cfg!(miri) { 32..64 } else { 128..267 }); - - for &i in &values { - let old_set = set.clone(); - set.replace(i); - for value in old_set.iter() { - if set.get(value).is_none() { - println!("old_set: {:?}", old_set); - println!("set: {:?}", set); - panic!("did not find {} in set", value); - } - } - } - - for &i in &values { - assert!(set.get(&i).is_some(), "did not find {}", i); - } - } - - #[test] - fn replace_dup() { - let mut elements = vec![0, 2, 4, 6, 8]; - let mut set: IndexSet<u8> = elements.drain(..).collect(); - { - let (i, v) = set.get_full(&0).unwrap(); - assert_eq!(set.len(), 5); - assert_eq!(i, 0); - assert_eq!(*v, 0); - } - { - let replaced = set.replace(0); - let (i, v) = set.get_full(&0).unwrap(); - assert_eq!(set.len(), 5); - assert_eq!(replaced, Some(0)); - assert_eq!(i, 0); - assert_eq!(*v, 0); - } - } - - #[test] - fn replace_order() { - let replace = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; - let mut set = IndexSet::new(); - - for &elt in &replace { - set.replace(elt); - } - - assert_eq!(set.iter().count(), set.len()); - assert_eq!(set.iter().count(), replace.len()); - for (a, b) in replace.iter().zip(set.iter()) { - assert_eq!(a, b); - } - for (i, v) in (0..replace.len()).zip(set.iter()) { - assert_eq!(set.get_index(i).unwrap(), v); - } - } - - #[test] - fn grow() { - let insert = [0, 4, 2, 12, 8, 7, 11]; - let not_present = [1, 3, 6, 9, 10]; - let mut set = IndexSet::with_capacity(insert.len()); - - for (i, &elt) in insert.iter().enumerate() { - assert_eq!(set.len(), i); - set.insert(elt); - assert_eq!(set.len(), i + 1); - assert_eq!(set.get(&elt), Some(&elt)); - } - - println!("{:?}", set); - for &elt in &insert { - set.insert(elt * 10); - } - for &elt in &insert { - set.insert(elt * 100); - } - for (i, &elt) in insert.iter().cycle().enumerate().take(100) { - set.insert(elt * 100 + i as i32); - } - println!("{:?}", set); - for &elt in ¬_present { - assert!(set.get(&elt).is_none()); - } - } - - #[test] - fn reserve() { - let mut set = IndexSet::<usize>::new(); - assert_eq!(set.capacity(), 0); - set.reserve(100); - let capacity = set.capacity(); - assert!(capacity >= 100); - for i in 0..capacity { - assert_eq!(set.len(), i); - set.insert(i); - assert_eq!(set.len(), i + 1); - assert_eq!(set.capacity(), capacity); - assert_eq!(set.get(&i), Some(&i)); - } - set.insert(capacity); - assert_eq!(set.len(), capacity + 1); - assert!(set.capacity() > capacity); - assert_eq!(set.get(&capacity), Some(&capacity)); - } - - #[test] - fn shrink_to_fit() { - let mut set = IndexSet::<usize>::new(); - assert_eq!(set.capacity(), 0); - for i in 0..100 { - assert_eq!(set.len(), i); - set.insert(i); - assert_eq!(set.len(), i + 1); - assert!(set.capacity() >= i + 1); - assert_eq!(set.get(&i), Some(&i)); - set.shrink_to_fit(); - assert_eq!(set.len(), i + 1); - assert_eq!(set.capacity(), i + 1); - assert_eq!(set.get(&i), Some(&i)); - } - } - - #[test] - fn remove() { - let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; - let mut set = IndexSet::new(); - - for &elt in &insert { - set.insert(elt); - } - - assert_eq!(set.iter().count(), set.len()); - assert_eq!(set.iter().count(), insert.len()); - for (a, b) in insert.iter().zip(set.iter()) { - assert_eq!(a, b); - } - - let remove_fail = [99, 77]; - let remove = [4, 12, 8, 7]; - - for &value in &remove_fail { - assert!(set.swap_remove_full(&value).is_none()); - } - println!("{:?}", set); - for &value in &remove { - //println!("{:?}", set); - let index = set.get_full(&value).unwrap().0; - assert_eq!(set.swap_remove_full(&value), Some((index, value))); - } - println!("{:?}", set); - - for value in &insert { - assert_eq!(set.get(value).is_some(), !remove.contains(value)); - } - assert_eq!(set.len(), insert.len() - remove.len()); - assert_eq!(set.iter().count(), insert.len() - remove.len()); - } - - #[test] - fn swap_remove_index() { - let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; - let mut set = IndexSet::new(); - - for &elt in &insert { - set.insert(elt); - } - - let mut vector = insert.to_vec(); - let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1]; - - // check that the same swap remove sequence on vec and set - // have the same result. - for &rm in remove_sequence { - let out_vec = vector.swap_remove(rm); - let out_set = set.swap_remove_index(rm).unwrap(); - assert_eq!(out_vec, out_set); - } - assert_eq!(vector.len(), set.len()); - for (a, b) in vector.iter().zip(set.iter()) { - assert_eq!(a, b); - } - } - - #[test] - fn partial_eq_and_eq() { - let mut set_a = IndexSet::new(); - set_a.insert(1); - set_a.insert(2); - let mut set_b = set_a.clone(); - assert_eq!(set_a, set_b); - set_b.swap_remove(&1); - assert_ne!(set_a, set_b); - - let set_c: IndexSet<_> = set_b.into_iter().collect(); - assert_ne!(set_a, set_c); - assert_ne!(set_c, set_a); - } - - #[test] - fn extend() { - let mut set = IndexSet::new(); - set.extend(vec![&1, &2, &3, &4]); - set.extend(vec![5, 6]); - assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4, 5, 6]); - } - - #[test] - fn comparisons() { - let set_a: IndexSet<_> = (0..3).collect(); - let set_b: IndexSet<_> = (3..6).collect(); - let set_c: IndexSet<_> = (0..6).collect(); - let set_d: IndexSet<_> = (3..9).collect(); - - assert!(!set_a.is_disjoint(&set_a)); - assert!(set_a.is_subset(&set_a)); - assert!(set_a.is_superset(&set_a)); - - assert!(set_a.is_disjoint(&set_b)); - assert!(set_b.is_disjoint(&set_a)); - assert!(!set_a.is_subset(&set_b)); - assert!(!set_b.is_subset(&set_a)); - assert!(!set_a.is_superset(&set_b)); - assert!(!set_b.is_superset(&set_a)); - - assert!(!set_a.is_disjoint(&set_c)); - assert!(!set_c.is_disjoint(&set_a)); - assert!(set_a.is_subset(&set_c)); - assert!(!set_c.is_subset(&set_a)); - assert!(!set_a.is_superset(&set_c)); - assert!(set_c.is_superset(&set_a)); - - assert!(!set_c.is_disjoint(&set_d)); - assert!(!set_d.is_disjoint(&set_c)); - assert!(!set_c.is_subset(&set_d)); - assert!(!set_d.is_subset(&set_c)); - assert!(!set_c.is_superset(&set_d)); - assert!(!set_d.is_superset(&set_c)); - } - - #[test] - fn iter_comparisons() { - use std::iter::empty; - - fn check<'a, I1, I2>(iter1: I1, iter2: I2) - where - I1: Iterator<Item = &'a i32>, - I2: Iterator<Item = i32>, - { - assert!(iter1.copied().eq(iter2)); - } - - let set_a: IndexSet<_> = (0..3).collect(); - let set_b: IndexSet<_> = (3..6).collect(); - let set_c: IndexSet<_> = (0..6).collect(); - let set_d: IndexSet<_> = (3..9).rev().collect(); - - check(set_a.difference(&set_a), empty()); - check(set_a.symmetric_difference(&set_a), empty()); - check(set_a.intersection(&set_a), 0..3); - check(set_a.union(&set_a), 0..3); - - check(set_a.difference(&set_b), 0..3); - check(set_b.difference(&set_a), 3..6); - check(set_a.symmetric_difference(&set_b), 0..6); - check(set_b.symmetric_difference(&set_a), (3..6).chain(0..3)); - check(set_a.intersection(&set_b), empty()); - check(set_b.intersection(&set_a), empty()); - check(set_a.union(&set_b), 0..6); - check(set_b.union(&set_a), (3..6).chain(0..3)); - - check(set_a.difference(&set_c), empty()); - check(set_c.difference(&set_a), 3..6); - check(set_a.symmetric_difference(&set_c), 3..6); - check(set_c.symmetric_difference(&set_a), 3..6); - check(set_a.intersection(&set_c), 0..3); - check(set_c.intersection(&set_a), 0..3); - check(set_a.union(&set_c), 0..6); - check(set_c.union(&set_a), 0..6); - - check(set_c.difference(&set_d), 0..3); - check(set_d.difference(&set_c), (6..9).rev()); - check( - set_c.symmetric_difference(&set_d), - (0..3).chain((6..9).rev()), - ); - check(set_d.symmetric_difference(&set_c), (6..9).rev().chain(0..3)); - check(set_c.intersection(&set_d), 3..6); - check(set_d.intersection(&set_c), (3..6).rev()); - check(set_c.union(&set_d), (0..6).chain((6..9).rev())); - check(set_d.union(&set_c), (3..9).rev().chain(0..3)); - } - - #[test] - fn ops() { - let empty = IndexSet::<i32>::new(); - let set_a: IndexSet<_> = (0..3).collect(); - let set_b: IndexSet<_> = (3..6).collect(); - let set_c: IndexSet<_> = (0..6).collect(); - let set_d: IndexSet<_> = (3..9).rev().collect(); - - #[allow(clippy::eq_op)] - { - assert_eq!(&set_a & &set_a, set_a); - assert_eq!(&set_a | &set_a, set_a); - assert_eq!(&set_a ^ &set_a, empty); - assert_eq!(&set_a - &set_a, empty); - } - - assert_eq!(&set_a & &set_b, empty); - assert_eq!(&set_b & &set_a, empty); - assert_eq!(&set_a | &set_b, set_c); - assert_eq!(&set_b | &set_a, set_c); - assert_eq!(&set_a ^ &set_b, set_c); - assert_eq!(&set_b ^ &set_a, set_c); - assert_eq!(&set_a - &set_b, set_a); - assert_eq!(&set_b - &set_a, set_b); - - assert_eq!(&set_a & &set_c, set_a); - assert_eq!(&set_c & &set_a, set_a); - assert_eq!(&set_a | &set_c, set_c); - assert_eq!(&set_c | &set_a, set_c); - assert_eq!(&set_a ^ &set_c, set_b); - assert_eq!(&set_c ^ &set_a, set_b); - assert_eq!(&set_a - &set_c, empty); - assert_eq!(&set_c - &set_a, set_b); - - assert_eq!(&set_c & &set_d, set_b); - assert_eq!(&set_d & &set_c, set_b); - assert_eq!(&set_c | &set_d, &set_a | &set_d); - assert_eq!(&set_d | &set_c, &set_a | &set_d); - assert_eq!(&set_c ^ &set_d, &set_a | &(&set_d - &set_b)); - assert_eq!(&set_d ^ &set_c, &set_a | &(&set_d - &set_b)); - assert_eq!(&set_c - &set_d, set_a); - assert_eq!(&set_d - &set_c, &set_d - &set_b); - } - - #[test] - #[cfg(has_std)] - fn from_array() { - let set1 = IndexSet::from([1, 2, 3, 4]); - let set2: IndexSet<_> = [1, 2, 3, 4].into(); - - assert_eq!(set1, set2); - } -} diff --git a/vendor/indexmap/src/set/iter.rs b/vendor/indexmap/src/set/iter.rs new file mode 100644 index 000000000..828756da1 --- /dev/null +++ b/vendor/indexmap/src/set/iter.rs @@ -0,0 +1,543 @@ +use super::{Bucket, Entries, IndexSet, Slice}; + +use alloc::vec::{self, Vec}; +use core::fmt; +use core::hash::{BuildHasher, Hash}; +use core::iter::{Chain, FusedIterator}; +use core::slice::Iter as SliceIter; + +impl<'a, T, S> IntoIterator for &'a IndexSet<T, S> { + type Item = &'a T; + type IntoIter = Iter<'a, T>; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl<T, S> IntoIterator for IndexSet<T, S> { + type Item = T; + type IntoIter = IntoIter<T>; + + fn into_iter(self) -> Self::IntoIter { + IntoIter::new(self.into_entries()) + } +} + +/// An iterator over the items of a `IndexSet`. +/// +/// This `struct` is created by the [`iter`] method on [`IndexSet`]. +/// See its documentation for more. +/// +/// [`IndexSet`]: struct.IndexSet.html +/// [`iter`]: struct.IndexSet.html#method.iter +pub struct Iter<'a, T> { + iter: SliceIter<'a, Bucket<T>>, +} + +impl<'a, T> Iter<'a, T> { + pub(super) fn new(entries: &'a [Bucket<T>]) -> Self { + Self { + iter: entries.iter(), + } + } + + /// Returns a slice of the remaining entries in the iterator. + pub fn as_slice(&self) -> &'a Slice<T> { + Slice::from_slice(self.iter.as_slice()) + } +} + +impl<'a, T> Iterator for Iter<'a, T> { + type Item = &'a T; + + iterator_methods!(Bucket::key_ref); +} + +impl<T> DoubleEndedIterator for Iter<'_, T> { + double_ended_iterator_methods!(Bucket::key_ref); +} + +impl<T> ExactSizeIterator for Iter<'_, T> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<T> FusedIterator for Iter<'_, T> {} + +impl<T> Clone for Iter<'_, T> { + fn clone(&self) -> Self { + Iter { + iter: self.iter.clone(), + } + } +} + +impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<T> Default for Iter<'_, T> { + fn default() -> Self { + Self { iter: [].iter() } + } +} + +/// An owning iterator over the items of a `IndexSet`. +/// +/// This `struct` is created by the [`into_iter`] method on [`IndexSet`] +/// (provided by the `IntoIterator` trait). See its documentation for more. +/// +/// [`IndexSet`]: struct.IndexSet.html +/// [`into_iter`]: struct.IndexSet.html#method.into_iter +pub struct IntoIter<T> { + iter: vec::IntoIter<Bucket<T>>, +} + +impl<T> IntoIter<T> { + pub(super) fn new(entries: Vec<Bucket<T>>) -> Self { + Self { + iter: entries.into_iter(), + } + } + + /// Returns a slice of the remaining entries in the iterator. + pub fn as_slice(&self) -> &Slice<T> { + Slice::from_slice(self.iter.as_slice()) + } +} + +impl<T> Iterator for IntoIter<T> { + type Item = T; + + iterator_methods!(Bucket::key); +} + +impl<T> DoubleEndedIterator for IntoIter<T> { + double_ended_iterator_methods!(Bucket::key); +} + +impl<T> ExactSizeIterator for IntoIter<T> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<T> FusedIterator for IntoIter<T> {} + +impl<T: fmt::Debug> fmt::Debug for IntoIter<T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.iter.as_slice().iter().map(Bucket::key_ref); + f.debug_list().entries(iter).finish() + } +} + +impl<T> Default for IntoIter<T> { + fn default() -> Self { + Self { + iter: Vec::new().into_iter(), + } + } +} + +/// A draining iterator over the items of a `IndexSet`. +/// +/// This `struct` is created by the [`drain`] method on [`IndexSet`]. +/// See its documentation for more. +/// +/// [`IndexSet`]: struct.IndexSet.html +/// [`drain`]: struct.IndexSet.html#method.drain +pub struct Drain<'a, T> { + iter: vec::Drain<'a, Bucket<T>>, +} + +impl<'a, T> Drain<'a, T> { + pub(super) fn new(iter: vec::Drain<'a, Bucket<T>>) -> Self { + Self { iter } + } + + /// Returns a slice of the remaining entries in the iterator. + pub fn as_slice(&self) -> &Slice<T> { + Slice::from_slice(self.iter.as_slice()) + } +} + +impl<T> Iterator for Drain<'_, T> { + type Item = T; + + iterator_methods!(Bucket::key); +} + +impl<T> DoubleEndedIterator for Drain<'_, T> { + double_ended_iterator_methods!(Bucket::key); +} + +impl<T> ExactSizeIterator for Drain<'_, T> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<T> FusedIterator for Drain<'_, T> {} + +impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.iter.as_slice().iter().map(Bucket::key_ref); + f.debug_list().entries(iter).finish() + } +} + +/// A lazy iterator producing elements in the difference of `IndexSet`s. +/// +/// This `struct` is created by the [`difference`] method on [`IndexSet`]. +/// See its documentation for more. +/// +/// [`IndexSet`]: struct.IndexSet.html +/// [`difference`]: struct.IndexSet.html#method.difference +pub struct Difference<'a, T, S> { + iter: Iter<'a, T>, + other: &'a IndexSet<T, S>, +} + +impl<'a, T, S> Difference<'a, T, S> { + pub(super) fn new<S1>(set: &'a IndexSet<T, S1>, other: &'a IndexSet<T, S>) -> Self { + Self { + iter: set.iter(), + other, + } + } +} + +impl<'a, T, S> Iterator for Difference<'a, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ + type Item = &'a T; + + fn next(&mut self) -> Option<Self::Item> { + while let Some(item) = self.iter.next() { + if !self.other.contains(item) { + return Some(item); + } + } + None + } + + fn size_hint(&self) -> (usize, Option<usize>) { + (0, self.iter.size_hint().1) + } +} + +impl<T, S> DoubleEndedIterator for Difference<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ + fn next_back(&mut self) -> Option<Self::Item> { + while let Some(item) = self.iter.next_back() { + if !self.other.contains(item) { + return Some(item); + } + } + None + } +} + +impl<T, S> FusedIterator for Difference<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ +} + +impl<T, S> Clone for Difference<'_, T, S> { + fn clone(&self) -> Self { + Difference { + iter: self.iter.clone(), + ..*self + } + } +} + +impl<T, S> fmt::Debug for Difference<'_, T, S> +where + T: fmt::Debug + Eq + Hash, + S: BuildHasher, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +/// A lazy iterator producing elements in the intersection of `IndexSet`s. +/// +/// This `struct` is created by the [`intersection`] method on [`IndexSet`]. +/// See its documentation for more. +/// +/// [`IndexSet`]: struct.IndexSet.html +/// [`intersection`]: struct.IndexSet.html#method.intersection +pub struct Intersection<'a, T, S> { + iter: Iter<'a, T>, + other: &'a IndexSet<T, S>, +} + +impl<'a, T, S> Intersection<'a, T, S> { + pub(super) fn new<S1>(set: &'a IndexSet<T, S1>, other: &'a IndexSet<T, S>) -> Self { + Self { + iter: set.iter(), + other, + } + } +} + +impl<'a, T, S> Iterator for Intersection<'a, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ + type Item = &'a T; + + fn next(&mut self) -> Option<Self::Item> { + while let Some(item) = self.iter.next() { + if self.other.contains(item) { + return Some(item); + } + } + None + } + + fn size_hint(&self) -> (usize, Option<usize>) { + (0, self.iter.size_hint().1) + } +} + +impl<T, S> DoubleEndedIterator for Intersection<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ + fn next_back(&mut self) -> Option<Self::Item> { + while let Some(item) = self.iter.next_back() { + if self.other.contains(item) { + return Some(item); + } + } + None + } +} + +impl<T, S> FusedIterator for Intersection<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ +} + +impl<T, S> Clone for Intersection<'_, T, S> { + fn clone(&self) -> Self { + Intersection { + iter: self.iter.clone(), + ..*self + } + } +} + +impl<T, S> fmt::Debug for Intersection<'_, T, S> +where + T: fmt::Debug + Eq + Hash, + S: BuildHasher, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +/// A lazy iterator producing elements in the symmetric difference of `IndexSet`s. +/// +/// This `struct` is created by the [`symmetric_difference`] method on +/// [`IndexSet`]. See its documentation for more. +/// +/// [`IndexSet`]: struct.IndexSet.html +/// [`symmetric_difference`]: struct.IndexSet.html#method.symmetric_difference +pub struct SymmetricDifference<'a, T, S1, S2> { + iter: Chain<Difference<'a, T, S2>, Difference<'a, T, S1>>, +} + +impl<'a, T, S1, S2> SymmetricDifference<'a, T, S1, S2> +where + T: Eq + Hash, + S1: BuildHasher, + S2: BuildHasher, +{ + pub(super) fn new(set1: &'a IndexSet<T, S1>, set2: &'a IndexSet<T, S2>) -> Self { + let diff1 = set1.difference(set2); + let diff2 = set2.difference(set1); + Self { + iter: diff1.chain(diff2), + } + } +} + +impl<'a, T, S1, S2> Iterator for SymmetricDifference<'a, T, S1, S2> +where + T: Eq + Hash, + S1: BuildHasher, + S2: BuildHasher, +{ + type Item = &'a T; + + fn next(&mut self) -> Option<Self::Item> { + self.iter.next() + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } + + fn fold<B, F>(self, init: B, f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter.fold(init, f) + } +} + +impl<T, S1, S2> DoubleEndedIterator for SymmetricDifference<'_, T, S1, S2> +where + T: Eq + Hash, + S1: BuildHasher, + S2: BuildHasher, +{ + fn next_back(&mut self) -> Option<Self::Item> { + self.iter.next_back() + } + + fn rfold<B, F>(self, init: B, f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter.rfold(init, f) + } +} + +impl<T, S1, S2> FusedIterator for SymmetricDifference<'_, T, S1, S2> +where + T: Eq + Hash, + S1: BuildHasher, + S2: BuildHasher, +{ +} + +impl<T, S1, S2> Clone for SymmetricDifference<'_, T, S1, S2> { + fn clone(&self) -> Self { + SymmetricDifference { + iter: self.iter.clone(), + } + } +} + +impl<T, S1, S2> fmt::Debug for SymmetricDifference<'_, T, S1, S2> +where + T: fmt::Debug + Eq + Hash, + S1: BuildHasher, + S2: BuildHasher, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +/// A lazy iterator producing elements in the union of `IndexSet`s. +/// +/// This `struct` is created by the [`union`] method on [`IndexSet`]. +/// See its documentation for more. +/// +/// [`IndexSet`]: struct.IndexSet.html +/// [`union`]: struct.IndexSet.html#method.union +pub struct Union<'a, T, S> { + iter: Chain<Iter<'a, T>, Difference<'a, T, S>>, +} + +impl<'a, T, S> Union<'a, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ + pub(super) fn new<S2>(set1: &'a IndexSet<T, S>, set2: &'a IndexSet<T, S2>) -> Self + where + S2: BuildHasher, + { + Self { + iter: set1.iter().chain(set2.difference(set1)), + } + } +} + +impl<'a, T, S> Iterator for Union<'a, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ + type Item = &'a T; + + fn next(&mut self) -> Option<Self::Item> { + self.iter.next() + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } + + fn fold<B, F>(self, init: B, f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter.fold(init, f) + } +} + +impl<T, S> DoubleEndedIterator for Union<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ + fn next_back(&mut self) -> Option<Self::Item> { + self.iter.next_back() + } + + fn rfold<B, F>(self, init: B, f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter.rfold(init, f) + } +} + +impl<T, S> FusedIterator for Union<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ +} + +impl<T, S> Clone for Union<'_, T, S> { + fn clone(&self) -> Self { + Union { + iter: self.iter.clone(), + } + } +} + +impl<T, S> fmt::Debug for Union<'_, T, S> +where + T: fmt::Debug + Eq + Hash, + S: BuildHasher, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} diff --git a/vendor/indexmap/src/set/slice.rs b/vendor/indexmap/src/set/slice.rs new file mode 100644 index 000000000..608311d2d --- /dev/null +++ b/vendor/indexmap/src/set/slice.rs @@ -0,0 +1,278 @@ +use super::{Bucket, Entries, IndexSet, IntoIter, Iter}; +use crate::util::try_simplify_range; + +use alloc::boxed::Box; +use alloc::vec::Vec; +use core::cmp::Ordering; +use core::fmt; +use core::hash::{Hash, Hasher}; +use core::ops::{self, Bound, Index, RangeBounds}; + +/// A dynamically-sized slice of values in an `IndexSet`. +/// +/// This supports indexed operations much like a `[T]` slice, +/// but not any hashed operations on the values. +/// +/// Unlike `IndexSet`, `Slice` does consider the order for `PartialEq` +/// and `Eq`, and it also implements `PartialOrd`, `Ord`, and `Hash`. +#[repr(transparent)] +pub struct Slice<T> { + pub(crate) entries: [Bucket<T>], +} + +// SAFETY: `Slice<T>` is a transparent wrapper around `[Bucket<T>]`, +// and reference lifetimes are bound together in function signatures. +#[allow(unsafe_code)] +impl<T> Slice<T> { + pub(super) fn from_slice(entries: &[Bucket<T>]) -> &Self { + unsafe { &*(entries as *const [Bucket<T>] as *const Self) } + } + + pub(super) fn from_boxed(entries: Box<[Bucket<T>]>) -> Box<Self> { + unsafe { Box::from_raw(Box::into_raw(entries) as *mut Self) } + } + + fn into_boxed(self: Box<Self>) -> Box<[Bucket<T>]> { + unsafe { Box::from_raw(Box::into_raw(self) as *mut [Bucket<T>]) } + } +} + +impl<T> Slice<T> { + pub(crate) fn into_entries(self: Box<Self>) -> Vec<Bucket<T>> { + self.into_boxed().into_vec() + } + + /// Return the number of elements in the set slice. + pub fn len(&self) -> usize { + self.entries.len() + } + + /// Returns true if the set slice contains no elements. + pub fn is_empty(&self) -> bool { + self.entries.is_empty() + } + + /// Get a value by index. + /// + /// Valid indices are *0 <= index < self.len()* + pub fn get_index(&self, index: usize) -> Option<&T> { + self.entries.get(index).map(Bucket::key_ref) + } + + /// Returns a slice of values in the given range of indices. + /// + /// Valid indices are *0 <= index < self.len()* + pub fn get_range<R: RangeBounds<usize>>(&self, range: R) -> Option<&Self> { + let range = try_simplify_range(range, self.entries.len())?; + self.entries.get(range).map(Self::from_slice) + } + + /// Get the first value. + pub fn first(&self) -> Option<&T> { + self.entries.first().map(Bucket::key_ref) + } + + /// Get the last value. + pub fn last(&self) -> Option<&T> { + self.entries.last().map(Bucket::key_ref) + } + + /// Divides one slice into two at an index. + /// + /// ***Panics*** if `index > len`. + pub fn split_at(&self, index: usize) -> (&Self, &Self) { + let (first, second) = self.entries.split_at(index); + (Self::from_slice(first), Self::from_slice(second)) + } + + /// Returns the first value and the rest of the slice, + /// or `None` if it is empty. + pub fn split_first(&self) -> Option<(&T, &Self)> { + if let [first, rest @ ..] = &self.entries { + Some((&first.key, Self::from_slice(rest))) + } else { + None + } + } + + /// Returns the last value and the rest of the slice, + /// or `None` if it is empty. + pub fn split_last(&self) -> Option<(&T, &Self)> { + if let [rest @ .., last] = &self.entries { + Some((&last.key, Self::from_slice(rest))) + } else { + None + } + } + + /// Return an iterator over the values of the set slice. + pub fn iter(&self) -> Iter<'_, T> { + Iter::new(&self.entries) + } +} + +impl<'a, T> IntoIterator for &'a Slice<T> { + type IntoIter = Iter<'a, T>; + type Item = &'a T; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl<T> IntoIterator for Box<Slice<T>> { + type IntoIter = IntoIter<T>; + type Item = T; + + fn into_iter(self) -> Self::IntoIter { + IntoIter::new(self.into_entries()) + } +} + +impl<T> Default for &'_ Slice<T> { + fn default() -> Self { + Slice::from_slice(&[]) + } +} + +impl<T> Default for Box<Slice<T>> { + fn default() -> Self { + Slice::from_boxed(Box::default()) + } +} + +impl<T: Clone> Clone for Box<Slice<T>> { + fn clone(&self) -> Self { + Slice::from_boxed(self.entries.to_vec().into_boxed_slice()) + } +} + +impl<T: Copy> From<&Slice<T>> for Box<Slice<T>> { + fn from(slice: &Slice<T>) -> Self { + Slice::from_boxed(Box::from(&slice.entries)) + } +} + +impl<T: fmt::Debug> fmt::Debug for Slice<T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self).finish() + } +} + +impl<T: PartialEq> PartialEq for Slice<T> { + fn eq(&self, other: &Self) -> bool { + self.len() == other.len() && self.iter().eq(other) + } +} + +impl<T: Eq> Eq for Slice<T> {} + +impl<T: PartialOrd> PartialOrd for Slice<T> { + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + self.iter().partial_cmp(other) + } +} + +impl<T: Ord> Ord for Slice<T> { + fn cmp(&self, other: &Self) -> Ordering { + self.iter().cmp(other) + } +} + +impl<T: Hash> Hash for Slice<T> { + fn hash<H: Hasher>(&self, state: &mut H) { + self.len().hash(state); + for value in self { + value.hash(state); + } + } +} + +impl<T> Index<usize> for Slice<T> { + type Output = T; + + fn index(&self, index: usize) -> &Self::Output { + &self.entries[index].key + } +} + +// We can't have `impl<I: RangeBounds<usize>> Index<I>` because that conflicts with `Index<usize>`. +// Instead, we repeat the implementations for all the core range types. +macro_rules! impl_index { + ($($range:ty),*) => {$( + impl<T, S> Index<$range> for IndexSet<T, S> { + type Output = Slice<T>; + + fn index(&self, range: $range) -> &Self::Output { + Slice::from_slice(&self.as_entries()[range]) + } + } + + impl<T> Index<$range> for Slice<T> { + type Output = Self; + + fn index(&self, range: $range) -> &Self::Output { + Slice::from_slice(&self.entries[range]) + } + } + )*} +} +impl_index!( + ops::Range<usize>, + ops::RangeFrom<usize>, + ops::RangeFull, + ops::RangeInclusive<usize>, + ops::RangeTo<usize>, + ops::RangeToInclusive<usize>, + (Bound<usize>, Bound<usize>) +); + +#[cfg(test)] +mod tests { + use super::*; + use alloc::vec::Vec; + + #[test] + fn slice_index() { + fn check(vec_slice: &[i32], set_slice: &Slice<i32>, sub_slice: &Slice<i32>) { + assert_eq!(set_slice as *const _, sub_slice as *const _); + itertools::assert_equal(vec_slice, set_slice); + } + + let vec: Vec<i32> = (0..10).map(|i| i * i).collect(); + let set: IndexSet<i32> = vec.iter().cloned().collect(); + let slice = set.as_slice(); + + // RangeFull + check(&vec[..], &set[..], &slice[..]); + + for i in 0usize..10 { + // Index + assert_eq!(vec[i], set[i]); + assert_eq!(vec[i], slice[i]); + + // RangeFrom + check(&vec[i..], &set[i..], &slice[i..]); + + // RangeTo + check(&vec[..i], &set[..i], &slice[..i]); + + // RangeToInclusive + check(&vec[..=i], &set[..=i], &slice[..=i]); + + // (Bound<usize>, Bound<usize>) + let bounds = (Bound::Excluded(i), Bound::Unbounded); + check(&vec[i + 1..], &set[bounds], &slice[bounds]); + + for j in i..=10 { + // Range + check(&vec[i..j], &set[i..j], &slice[i..j]); + } + + for j in i..10 { + // RangeInclusive + check(&vec[i..=j], &set[i..=j], &slice[i..=j]); + } + } + } +} diff --git a/vendor/indexmap/src/set/tests.rs b/vendor/indexmap/src/set/tests.rs new file mode 100644 index 000000000..44f8ed841 --- /dev/null +++ b/vendor/indexmap/src/set/tests.rs @@ -0,0 +1,545 @@ +use super::*; +use std::string::String; + +#[test] +fn it_works() { + let mut set = IndexSet::new(); + assert_eq!(set.is_empty(), true); + set.insert(1); + set.insert(1); + assert_eq!(set.len(), 1); + assert!(set.get(&1).is_some()); + assert_eq!(set.is_empty(), false); +} + +#[test] +fn new() { + let set = IndexSet::<String>::new(); + println!("{:?}", set); + assert_eq!(set.capacity(), 0); + assert_eq!(set.len(), 0); + assert_eq!(set.is_empty(), true); +} + +#[test] +fn insert() { + let insert = [0, 4, 2, 12, 8, 7, 11, 5]; + let not_present = [1, 3, 6, 9, 10]; + let mut set = IndexSet::with_capacity(insert.len()); + + for (i, &elt) in insert.iter().enumerate() { + assert_eq!(set.len(), i); + set.insert(elt); + assert_eq!(set.len(), i + 1); + assert_eq!(set.get(&elt), Some(&elt)); + } + println!("{:?}", set); + + for &elt in ¬_present { + assert!(set.get(&elt).is_none()); + } +} + +#[test] +fn insert_full() { + let insert = vec![9, 2, 7, 1, 4, 6, 13]; + let present = vec![1, 6, 2]; + let mut set = IndexSet::with_capacity(insert.len()); + + for (i, &elt) in insert.iter().enumerate() { + assert_eq!(set.len(), i); + let (index, success) = set.insert_full(elt); + assert!(success); + assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); + assert_eq!(set.len(), i + 1); + } + + let len = set.len(); + for &elt in &present { + let (index, success) = set.insert_full(elt); + assert!(!success); + assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); + assert_eq!(set.len(), len); + } +} + +#[test] +fn insert_2() { + let mut set = IndexSet::with_capacity(16); + + let mut values = vec![]; + values.extend(0..16); + values.extend(if cfg!(miri) { 32..64 } else { 128..267 }); + + for &i in &values { + let old_set = set.clone(); + set.insert(i); + for value in old_set.iter() { + if set.get(value).is_none() { + println!("old_set: {:?}", old_set); + println!("set: {:?}", set); + panic!("did not find {} in set", value); + } + } + } + + for &i in &values { + assert!(set.get(&i).is_some(), "did not find {}", i); + } +} + +#[test] +fn insert_dup() { + let mut elements = vec![0, 2, 4, 6, 8]; + let mut set: IndexSet<u8> = elements.drain(..).collect(); + { + let (i, v) = set.get_full(&0).unwrap(); + assert_eq!(set.len(), 5); + assert_eq!(i, 0); + assert_eq!(*v, 0); + } + { + let inserted = set.insert(0); + let (i, v) = set.get_full(&0).unwrap(); + assert_eq!(set.len(), 5); + assert_eq!(inserted, false); + assert_eq!(i, 0); + assert_eq!(*v, 0); + } +} + +#[test] +fn insert_order() { + let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; + let mut set = IndexSet::new(); + + for &elt in &insert { + set.insert(elt); + } + + assert_eq!(set.iter().count(), set.len()); + assert_eq!(set.iter().count(), insert.len()); + for (a, b) in insert.iter().zip(set.iter()) { + assert_eq!(a, b); + } + for (i, v) in (0..insert.len()).zip(set.iter()) { + assert_eq!(set.get_index(i).unwrap(), v); + } +} + +#[test] +fn replace() { + let replace = [0, 4, 2, 12, 8, 7, 11, 5]; + let not_present = [1, 3, 6, 9, 10]; + let mut set = IndexSet::with_capacity(replace.len()); + + for (i, &elt) in replace.iter().enumerate() { + assert_eq!(set.len(), i); + set.replace(elt); + assert_eq!(set.len(), i + 1); + assert_eq!(set.get(&elt), Some(&elt)); + } + println!("{:?}", set); + + for &elt in ¬_present { + assert!(set.get(&elt).is_none()); + } +} + +#[test] +fn replace_full() { + let replace = vec![9, 2, 7, 1, 4, 6, 13]; + let present = vec![1, 6, 2]; + let mut set = IndexSet::with_capacity(replace.len()); + + for (i, &elt) in replace.iter().enumerate() { + assert_eq!(set.len(), i); + let (index, replaced) = set.replace_full(elt); + assert!(replaced.is_none()); + assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); + assert_eq!(set.len(), i + 1); + } + + let len = set.len(); + for &elt in &present { + let (index, replaced) = set.replace_full(elt); + assert_eq!(Some(elt), replaced); + assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); + assert_eq!(set.len(), len); + } +} + +#[test] +fn replace_2() { + let mut set = IndexSet::with_capacity(16); + + let mut values = vec![]; + values.extend(0..16); + values.extend(if cfg!(miri) { 32..64 } else { 128..267 }); + + for &i in &values { + let old_set = set.clone(); + set.replace(i); + for value in old_set.iter() { + if set.get(value).is_none() { + println!("old_set: {:?}", old_set); + println!("set: {:?}", set); + panic!("did not find {} in set", value); + } + } + } + + for &i in &values { + assert!(set.get(&i).is_some(), "did not find {}", i); + } +} + +#[test] +fn replace_dup() { + let mut elements = vec![0, 2, 4, 6, 8]; + let mut set: IndexSet<u8> = elements.drain(..).collect(); + { + let (i, v) = set.get_full(&0).unwrap(); + assert_eq!(set.len(), 5); + assert_eq!(i, 0); + assert_eq!(*v, 0); + } + { + let replaced = set.replace(0); + let (i, v) = set.get_full(&0).unwrap(); + assert_eq!(set.len(), 5); + assert_eq!(replaced, Some(0)); + assert_eq!(i, 0); + assert_eq!(*v, 0); + } +} + +#[test] +fn replace_order() { + let replace = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; + let mut set = IndexSet::new(); + + for &elt in &replace { + set.replace(elt); + } + + assert_eq!(set.iter().count(), set.len()); + assert_eq!(set.iter().count(), replace.len()); + for (a, b) in replace.iter().zip(set.iter()) { + assert_eq!(a, b); + } + for (i, v) in (0..replace.len()).zip(set.iter()) { + assert_eq!(set.get_index(i).unwrap(), v); + } +} + +#[test] +fn grow() { + let insert = [0, 4, 2, 12, 8, 7, 11]; + let not_present = [1, 3, 6, 9, 10]; + let mut set = IndexSet::with_capacity(insert.len()); + + for (i, &elt) in insert.iter().enumerate() { + assert_eq!(set.len(), i); + set.insert(elt); + assert_eq!(set.len(), i + 1); + assert_eq!(set.get(&elt), Some(&elt)); + } + + println!("{:?}", set); + for &elt in &insert { + set.insert(elt * 10); + } + for &elt in &insert { + set.insert(elt * 100); + } + for (i, &elt) in insert.iter().cycle().enumerate().take(100) { + set.insert(elt * 100 + i as i32); + } + println!("{:?}", set); + for &elt in ¬_present { + assert!(set.get(&elt).is_none()); + } +} + +#[test] +fn reserve() { + let mut set = IndexSet::<usize>::new(); + assert_eq!(set.capacity(), 0); + set.reserve(100); + let capacity = set.capacity(); + assert!(capacity >= 100); + for i in 0..capacity { + assert_eq!(set.len(), i); + set.insert(i); + assert_eq!(set.len(), i + 1); + assert_eq!(set.capacity(), capacity); + assert_eq!(set.get(&i), Some(&i)); + } + set.insert(capacity); + assert_eq!(set.len(), capacity + 1); + assert!(set.capacity() > capacity); + assert_eq!(set.get(&capacity), Some(&capacity)); +} + +#[test] +fn try_reserve() { + let mut set = IndexSet::<usize>::new(); + assert_eq!(set.capacity(), 0); + assert_eq!(set.try_reserve(100), Ok(())); + assert!(set.capacity() >= 100); + assert!(set.try_reserve(usize::MAX).is_err()); +} + +#[test] +fn shrink_to_fit() { + let mut set = IndexSet::<usize>::new(); + assert_eq!(set.capacity(), 0); + for i in 0..100 { + assert_eq!(set.len(), i); + set.insert(i); + assert_eq!(set.len(), i + 1); + assert!(set.capacity() >= i + 1); + assert_eq!(set.get(&i), Some(&i)); + set.shrink_to_fit(); + assert_eq!(set.len(), i + 1); + assert_eq!(set.capacity(), i + 1); + assert_eq!(set.get(&i), Some(&i)); + } +} + +#[test] +fn remove() { + let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; + let mut set = IndexSet::new(); + + for &elt in &insert { + set.insert(elt); + } + + assert_eq!(set.iter().count(), set.len()); + assert_eq!(set.iter().count(), insert.len()); + for (a, b) in insert.iter().zip(set.iter()) { + assert_eq!(a, b); + } + + let remove_fail = [99, 77]; + let remove = [4, 12, 8, 7]; + + for &value in &remove_fail { + assert!(set.swap_remove_full(&value).is_none()); + } + println!("{:?}", set); + for &value in &remove { + //println!("{:?}", set); + let index = set.get_full(&value).unwrap().0; + assert_eq!(set.swap_remove_full(&value), Some((index, value))); + } + println!("{:?}", set); + + for value in &insert { + assert_eq!(set.get(value).is_some(), !remove.contains(value)); + } + assert_eq!(set.len(), insert.len() - remove.len()); + assert_eq!(set.iter().count(), insert.len() - remove.len()); +} + +#[test] +fn swap_remove_index() { + let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; + let mut set = IndexSet::new(); + + for &elt in &insert { + set.insert(elt); + } + + let mut vector = insert.to_vec(); + let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1]; + + // check that the same swap remove sequence on vec and set + // have the same result. + for &rm in remove_sequence { + let out_vec = vector.swap_remove(rm); + let out_set = set.swap_remove_index(rm).unwrap(); + assert_eq!(out_vec, out_set); + } + assert_eq!(vector.len(), set.len()); + for (a, b) in vector.iter().zip(set.iter()) { + assert_eq!(a, b); + } +} + +#[test] +fn partial_eq_and_eq() { + let mut set_a = IndexSet::new(); + set_a.insert(1); + set_a.insert(2); + let mut set_b = set_a.clone(); + assert_eq!(set_a, set_b); + set_b.swap_remove(&1); + assert_ne!(set_a, set_b); + + let set_c: IndexSet<_> = set_b.into_iter().collect(); + assert_ne!(set_a, set_c); + assert_ne!(set_c, set_a); +} + +#[test] +fn extend() { + let mut set = IndexSet::new(); + set.extend(vec![&1, &2, &3, &4]); + set.extend(vec![5, 6]); + assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4, 5, 6]); +} + +#[test] +fn comparisons() { + let set_a: IndexSet<_> = (0..3).collect(); + let set_b: IndexSet<_> = (3..6).collect(); + let set_c: IndexSet<_> = (0..6).collect(); + let set_d: IndexSet<_> = (3..9).collect(); + + assert!(!set_a.is_disjoint(&set_a)); + assert!(set_a.is_subset(&set_a)); + assert!(set_a.is_superset(&set_a)); + + assert!(set_a.is_disjoint(&set_b)); + assert!(set_b.is_disjoint(&set_a)); + assert!(!set_a.is_subset(&set_b)); + assert!(!set_b.is_subset(&set_a)); + assert!(!set_a.is_superset(&set_b)); + assert!(!set_b.is_superset(&set_a)); + + assert!(!set_a.is_disjoint(&set_c)); + assert!(!set_c.is_disjoint(&set_a)); + assert!(set_a.is_subset(&set_c)); + assert!(!set_c.is_subset(&set_a)); + assert!(!set_a.is_superset(&set_c)); + assert!(set_c.is_superset(&set_a)); + + assert!(!set_c.is_disjoint(&set_d)); + assert!(!set_d.is_disjoint(&set_c)); + assert!(!set_c.is_subset(&set_d)); + assert!(!set_d.is_subset(&set_c)); + assert!(!set_c.is_superset(&set_d)); + assert!(!set_d.is_superset(&set_c)); +} + +#[test] +fn iter_comparisons() { + use std::iter::empty; + + fn check<'a, I1, I2>(iter1: I1, iter2: I2) + where + I1: Iterator<Item = &'a i32>, + I2: Iterator<Item = i32>, + { + assert!(iter1.copied().eq(iter2)); + } + + let set_a: IndexSet<_> = (0..3).collect(); + let set_b: IndexSet<_> = (3..6).collect(); + let set_c: IndexSet<_> = (0..6).collect(); + let set_d: IndexSet<_> = (3..9).rev().collect(); + + check(set_a.difference(&set_a), empty()); + check(set_a.symmetric_difference(&set_a), empty()); + check(set_a.intersection(&set_a), 0..3); + check(set_a.union(&set_a), 0..3); + + check(set_a.difference(&set_b), 0..3); + check(set_b.difference(&set_a), 3..6); + check(set_a.symmetric_difference(&set_b), 0..6); + check(set_b.symmetric_difference(&set_a), (3..6).chain(0..3)); + check(set_a.intersection(&set_b), empty()); + check(set_b.intersection(&set_a), empty()); + check(set_a.union(&set_b), 0..6); + check(set_b.union(&set_a), (3..6).chain(0..3)); + + check(set_a.difference(&set_c), empty()); + check(set_c.difference(&set_a), 3..6); + check(set_a.symmetric_difference(&set_c), 3..6); + check(set_c.symmetric_difference(&set_a), 3..6); + check(set_a.intersection(&set_c), 0..3); + check(set_c.intersection(&set_a), 0..3); + check(set_a.union(&set_c), 0..6); + check(set_c.union(&set_a), 0..6); + + check(set_c.difference(&set_d), 0..3); + check(set_d.difference(&set_c), (6..9).rev()); + check( + set_c.symmetric_difference(&set_d), + (0..3).chain((6..9).rev()), + ); + check(set_d.symmetric_difference(&set_c), (6..9).rev().chain(0..3)); + check(set_c.intersection(&set_d), 3..6); + check(set_d.intersection(&set_c), (3..6).rev()); + check(set_c.union(&set_d), (0..6).chain((6..9).rev())); + check(set_d.union(&set_c), (3..9).rev().chain(0..3)); +} + +#[test] +fn ops() { + let empty = IndexSet::<i32>::new(); + let set_a: IndexSet<_> = (0..3).collect(); + let set_b: IndexSet<_> = (3..6).collect(); + let set_c: IndexSet<_> = (0..6).collect(); + let set_d: IndexSet<_> = (3..9).rev().collect(); + + #[allow(clippy::eq_op)] + { + assert_eq!(&set_a & &set_a, set_a); + assert_eq!(&set_a | &set_a, set_a); + assert_eq!(&set_a ^ &set_a, empty); + assert_eq!(&set_a - &set_a, empty); + } + + assert_eq!(&set_a & &set_b, empty); + assert_eq!(&set_b & &set_a, empty); + assert_eq!(&set_a | &set_b, set_c); + assert_eq!(&set_b | &set_a, set_c); + assert_eq!(&set_a ^ &set_b, set_c); + assert_eq!(&set_b ^ &set_a, set_c); + assert_eq!(&set_a - &set_b, set_a); + assert_eq!(&set_b - &set_a, set_b); + + assert_eq!(&set_a & &set_c, set_a); + assert_eq!(&set_c & &set_a, set_a); + assert_eq!(&set_a | &set_c, set_c); + assert_eq!(&set_c | &set_a, set_c); + assert_eq!(&set_a ^ &set_c, set_b); + assert_eq!(&set_c ^ &set_a, set_b); + assert_eq!(&set_a - &set_c, empty); + assert_eq!(&set_c - &set_a, set_b); + + assert_eq!(&set_c & &set_d, set_b); + assert_eq!(&set_d & &set_c, set_b); + assert_eq!(&set_c | &set_d, &set_a | &set_d); + assert_eq!(&set_d | &set_c, &set_a | &set_d); + assert_eq!(&set_c ^ &set_d, &set_a | &(&set_d - &set_b)); + assert_eq!(&set_d ^ &set_c, &set_a | &(&set_d - &set_b)); + assert_eq!(&set_c - &set_d, set_a); + assert_eq!(&set_d - &set_c, &set_d - &set_b); +} + +#[test] +#[cfg(feature = "std")] +fn from_array() { + let set1 = IndexSet::from([1, 2, 3, 4]); + let set2: IndexSet<_> = [1, 2, 3, 4].into(); + + assert_eq!(set1, set2); +} + +#[test] +fn iter_default() { + struct Item; + fn assert_default<T>() + where + T: Default + Iterator, + { + assert!(T::default().next().is_none()); + } + assert_default::<Iter<'static, Item>>(); + assert_default::<IntoIter<Item>>(); +} diff --git a/vendor/indexmap/src/util.rs b/vendor/indexmap/src/util.rs index a24dfafde..377ff516f 100644 --- a/vendor/indexmap/src/util.rs +++ b/vendor/indexmap/src/util.rs @@ -29,3 +29,25 @@ where } start..end } + +pub(crate) fn try_simplify_range<R>(range: R, len: usize) -> Option<Range<usize>> +where + R: RangeBounds<usize>, +{ + let start = match range.start_bound() { + Bound::Unbounded => 0, + Bound::Included(&i) if i <= len => i, + Bound::Excluded(&i) if i < len => i + 1, + _ => return None, + }; + let end = match range.end_bound() { + Bound::Unbounded => len, + Bound::Excluded(&i) if i <= len => i, + Bound::Included(&i) if i < len => i + 1, + _ => return None, + }; + if start > end { + return None; + } + Some(start..end) +} diff --git a/vendor/indexmap/tests/quick.rs b/vendor/indexmap/tests/quick.rs index e9d96accc..4142e2d66 100644 --- a/vendor/indexmap/tests/quick.rs +++ b/vendor/indexmap/tests/quick.rs @@ -452,6 +452,12 @@ quickcheck_limit! { assert_sorted_by_key(map, |t| t.1); } + fn sort_3(keyvals: Large<Vec<(i8, i8)>>) -> () { + let mut map: IndexMap<_, _> = IndexMap::from_iter(keyvals.to_vec()); + map.sort_by_cached_key(|&k, _| std::cmp::Reverse(k)); + assert_sorted_by_key(map, |t| std::cmp::Reverse(t.0)); + } + fn reverse(keyvals: Large<Vec<(i8, i8)>>) -> () { let mut map: IndexMap<_, _> = IndexMap::from_iter(keyvals.to_vec()); |