From 36d22d82aa202bb199967e9512281e9a53db42c9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 21:33:14 +0200 Subject: Adding upstream version 115.7.0esr. Signed-off-by: Daniel Baumann --- third_party/rust/indexmap/src/arbitrary.rs | 75 + third_party/rust/indexmap/src/equivalent.rs | 27 + third_party/rust/indexmap/src/lib.rs | 194 +++ third_party/rust/indexmap/src/macros.rs | 178 +++ third_party/rust/indexmap/src/map.rs | 1947 +++++++++++++++++++++++++ third_party/rust/indexmap/src/map/core.rs | 700 +++++++++ third_party/rust/indexmap/src/map/core/raw.rs | 191 +++ third_party/rust/indexmap/src/mutable_keys.rs | 75 + third_party/rust/indexmap/src/rayon/map.rs | 583 ++++++++ third_party/rust/indexmap/src/rayon/mod.rs | 27 + third_party/rust/indexmap/src/rayon/set.rs | 741 ++++++++++ third_party/rust/indexmap/src/rustc.rs | 158 ++ third_party/rust/indexmap/src/serde.rs | 155 ++ third_party/rust/indexmap/src/serde_seq.rs | 112 ++ third_party/rust/indexmap/src/set.rs | 1912 ++++++++++++++++++++++++ third_party/rust/indexmap/src/util.rs | 31 + 16 files changed, 7106 insertions(+) create mode 100644 third_party/rust/indexmap/src/arbitrary.rs create mode 100644 third_party/rust/indexmap/src/equivalent.rs create mode 100644 third_party/rust/indexmap/src/lib.rs create mode 100644 third_party/rust/indexmap/src/macros.rs create mode 100644 third_party/rust/indexmap/src/map.rs create mode 100644 third_party/rust/indexmap/src/map/core.rs create mode 100644 third_party/rust/indexmap/src/map/core/raw.rs create mode 100644 third_party/rust/indexmap/src/mutable_keys.rs create mode 100644 third_party/rust/indexmap/src/rayon/map.rs create mode 100644 third_party/rust/indexmap/src/rayon/mod.rs create mode 100644 third_party/rust/indexmap/src/rayon/set.rs create mode 100644 third_party/rust/indexmap/src/rustc.rs create mode 100644 third_party/rust/indexmap/src/serde.rs create mode 100644 third_party/rust/indexmap/src/serde_seq.rs create mode 100644 third_party/rust/indexmap/src/set.rs create mode 100644 third_party/rust/indexmap/src/util.rs (limited to 'third_party/rust/indexmap/src') diff --git a/third_party/rust/indexmap/src/arbitrary.rs b/third_party/rust/indexmap/src/arbitrary.rs new file mode 100644 index 0000000000..1347c8b54f --- /dev/null +++ b/third_party/rust/indexmap/src/arbitrary.rs @@ -0,0 +1,75 @@ +#[cfg(feature = "arbitrary")] +mod impl_arbitrary { + use crate::{IndexMap, IndexSet}; + use arbitrary::{Arbitrary, Result, Unstructured}; + use core::hash::{BuildHasher, Hash}; + + impl<'a, K, V, S> Arbitrary<'a> for IndexMap + where + K: Arbitrary<'a> + Hash + Eq, + V: Arbitrary<'a>, + S: BuildHasher + Default, + { + fn arbitrary(u: &mut Unstructured<'a>) -> Result { + u.arbitrary_iter()?.collect() + } + + fn arbitrary_take_rest(u: Unstructured<'a>) -> Result { + u.arbitrary_take_rest_iter()?.collect() + } + } + + impl<'a, T, S> Arbitrary<'a> for IndexSet + where + T: Arbitrary<'a> + Hash + Eq, + S: BuildHasher + Default, + { + fn arbitrary(u: &mut Unstructured<'a>) -> Result { + u.arbitrary_iter()?.collect() + } + + fn arbitrary_take_rest(u: Unstructured<'a>) -> Result { + u.arbitrary_take_rest_iter()?.collect() + } + } +} + +#[cfg(feature = "quickcheck")] +mod impl_quickcheck { + use crate::{IndexMap, IndexSet}; + use alloc::boxed::Box; + use alloc::vec::Vec; + use core::hash::{BuildHasher, Hash}; + use quickcheck::{Arbitrary, Gen}; + + impl Arbitrary for IndexMap + where + K: Arbitrary + Hash + Eq, + V: Arbitrary, + S: BuildHasher + Default + Clone + 'static, + { + fn arbitrary(g: &mut Gen) -> Self { + Self::from_iter(Vec::arbitrary(g)) + } + + fn shrink(&self) -> Box> { + let vec = Vec::from_iter(self.clone()); + Box::new(vec.shrink().map(Self::from_iter)) + } + } + + impl Arbitrary for IndexSet + where + T: Arbitrary + Hash + Eq, + S: BuildHasher + Default + Clone + 'static, + { + fn arbitrary(g: &mut Gen) -> Self { + Self::from_iter(Vec::arbitrary(g)) + } + + fn shrink(&self) -> Box> { + let vec = Vec::from_iter(self.clone()); + Box::new(vec.shrink().map(Self::from_iter)) + } + } +} diff --git a/third_party/rust/indexmap/src/equivalent.rs b/third_party/rust/indexmap/src/equivalent.rs new file mode 100644 index 0000000000..ad6635ffac --- /dev/null +++ b/third_party/rust/indexmap/src/equivalent.rs @@ -0,0 +1,27 @@ +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 { + /// Compare self to `key` and return `true` if they are equal. + fn equivalent(&self, key: &K) -> bool; +} + +impl Equivalent for Q +where + Q: Eq, + K: Borrow, +{ + #[inline] + fn equivalent(&self, key: &K) -> bool { + *self == *key.borrow() + } +} diff --git a/third_party/rust/indexmap/src/lib.rs b/third_party/rust/indexmap/src/lib.rs new file mode 100644 index 0000000000..6e94936124 --- /dev/null +++ b/third_party/rust/indexmap/src/lib.rs @@ -0,0 +1,194 @@ +// We *mostly* avoid unsafe code, but `map::core::raw` allows it to use `RawTable` buckets. +#![deny(unsafe_code)] +#![warn(rust_2018_idioms)] +#![doc(html_root_url = "https://docs.rs/indexmap/1/")] +#![no_std] + +//! [`IndexMap`] is a hash table where the iteration order of the key-value +//! pairs is independent of the hash values of the keys. +//! +//! [`IndexSet`] is a corresponding hash set using the same implementation and +//! with similar properties. +//! +//! [`IndexMap`]: map/struct.IndexMap.html +//! [`IndexSet`]: set/struct.IndexSet.html +//! +//! +//! ### Feature Highlights +//! +//! [`IndexMap`] and [`IndexSet`] are drop-in compatible with the std `HashMap` +//! and `HashSet`, but they also have some features of note: +//! +//! - The ordering semantics (see their documentation for details) +//! - Sorting methods and the [`.pop()`][IndexMap::pop] methods. +//! - The [`Equivalent`] trait, which offers more flexible equality definitions +//! between borrowed and owned versions of keys. +//! - The [`MutableKeys`][map::MutableKeys] trait, which gives opt-in mutable +//! access to hash map keys. +//! +//! ### Alternate Hashers +//! +//! [`IndexMap`] and [`IndexSet`] have a default hasher type `S = RandomState`, +//! just like the standard `HashMap` and `HashSet`, which is resistant to +//! HashDoS attacks but not the most performant. Type aliases can make it easier +//! to use alternate hashers: +//! +//! ``` +//! use fnv::FnvBuildHasher; +//! use fxhash::FxBuildHasher; +//! use indexmap::{IndexMap, IndexSet}; +//! +//! type FnvIndexMap = IndexMap; +//! type FnvIndexSet = IndexSet; +//! +//! type FxIndexMap = IndexMap; +//! type FxIndexSet = IndexSet; +//! +//! let std: IndexSet = (0..100).collect(); +//! let fnv: FnvIndexSet = (0..100).collect(); +//! let fx: FxIndexSet = (0..100).collect(); +//! assert_eq!(std, fnv); +//! assert_eq!(std, fx); +//! ``` +//! +//! ### Rust Version +//! +//! This version of indexmap requires Rust 1.56 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 +//! 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. +//! +//! - Creating maps and sets using [`new`][IndexMap::new] and +//! [`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. +//! A no-std compatible hasher will be needed as well, for example +//! from the crate `twox-hash`. +//! - Macros [`indexmap!`] and [`indexset!`] are unavailable without `std`. +//! +//! [def]: map/struct.IndexMap.html#impl-Default + +extern crate alloc; + +#[cfg(has_std)] +#[macro_use] +extern crate std; + +use alloc::vec::{self, Vec}; + +mod arbitrary; +#[macro_use] +mod macros; +mod equivalent; +mod mutable_keys; +#[cfg(feature = "serde")] +mod serde; +#[cfg(feature = "serde")] +pub mod serde_seq; +mod util; + +pub mod map; +pub mod set; + +// Placed after `map` and `set` so new `rayon` methods on the types +// are documented after the "normal" methods. +#[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; + +// shared private items + +/// Hash value newtype. Not larger than usize, since anything larger +/// isn't used for selecting position anyway. +#[derive(Clone, Copy, Debug, PartialEq)] +struct HashValue(usize); + +impl HashValue { + #[inline(always)] + fn get(self) -> u64 { + self.0 as u64 + } +} + +#[derive(Copy, Debug)] +struct Bucket { + hash: HashValue, + key: K, + value: V, +} + +impl Clone for Bucket +where + K: Clone, + V: Clone, +{ + fn clone(&self) -> Self { + Bucket { + hash: self.hash, + key: self.key.clone(), + value: self.value.clone(), + } + } + + fn clone_from(&mut self, other: &Self) { + self.hash = other.hash; + self.key.clone_from(&other.key); + self.value.clone_from(&other.value); + } +} + +impl Bucket { + // field accessors -- used for `f` instead of closures in `.map(f)` + fn key_ref(&self) -> &K { + &self.key + } + fn value_ref(&self) -> &V { + &self.value + } + fn value_mut(&mut self) -> &mut V { + &mut self.value + } + fn key(self) -> K { + self.key + } + fn value(self) -> V { + self.value + } + fn key_value(self) -> (K, V) { + (self.key, self.value) + } + fn refs(&self) -> (&K, &V) { + (&self.key, &self.value) + } + fn ref_mut(&mut self) -> (&K, &mut V) { + (&self.key, &mut self.value) + } + fn muts(&mut self) -> (&mut K, &mut V) { + (&mut self.key, &mut self.value) + } +} + +trait Entries { + type Entry; + fn into_entries(self) -> Vec; + fn as_entries(&self) -> &[Self::Entry]; + fn as_entries_mut(&mut self) -> &mut [Self::Entry]; + fn with_entries(&mut self, f: F) + where + F: FnOnce(&mut [Self::Entry]); +} diff --git a/third_party/rust/indexmap/src/macros.rs b/third_party/rust/indexmap/src/macros.rs new file mode 100644 index 0000000000..ca26287be9 --- /dev/null +++ b/third_party/rust/indexmap/src/macros.rs @@ -0,0 +1,178 @@ +#[cfg(has_std)] +#[macro_export] +/// Create an `IndexMap` from a list of key-value pairs +/// +/// ## Example +/// +/// ``` +/// use indexmap::indexmap; +/// +/// let map = indexmap!{ +/// "a" => 1, +/// "b" => 2, +/// }; +/// assert_eq!(map["a"], 1); +/// assert_eq!(map["b"], 2); +/// assert_eq!(map.get("c"), None); +/// +/// // "a" is the first key +/// 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); + $( + _map.insert($key, $value); + )* + _map + } + }; +} + +#[cfg(has_std)] +#[macro_export] +/// Create an `IndexSet` from a list of values +/// +/// ## Example +/// +/// ``` +/// use indexmap::indexset; +/// +/// let set = indexset!{ +/// "a", +/// "b", +/// }; +/// assert!(set.contains("a")); +/// assert!(set.contains("b")); +/// assert!(!set.contains("c")); +/// +/// // "a" is the first value +/// 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); + $( + _set.insert($value); + )* + _set + } + }; +} + +// generate all the Iterator methods by just forwarding to the underlying +// self.iter and mapping its element. +macro_rules! iterator_methods { + // $map_elt is the mapping function from the underlying iterator's element + // same mapping function for both options and iterators + ($map_elt:expr) => { + fn next(&mut self) -> Option { + self.iter.next().map($map_elt) + } + + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } + + fn count(self) -> usize { + self.iter.len() + } + + fn nth(&mut self, n: usize) -> Option { + self.iter.nth(n).map($map_elt) + } + + fn last(mut self) -> Option { + self.next_back() + } + + fn collect(self) -> C + where + C: FromIterator, + { + // NB: forwarding this directly to standard iterators will + // allow it to leverage unstable traits like `TrustedLen`. + self.iter.map($map_elt).collect() + } + }; +} + +macro_rules! double_ended_iterator_methods { + // $map_elt is the mapping function from the underlying iterator's element + // same mapping function for both options and iterators + ($map_elt:expr) => { + fn next_back(&mut self) -> Option { + self.iter.next_back().map($map_elt) + } + + fn nth_back(&mut self, n: usize) -> Option { + self.iter.nth_back(n).map($map_elt) + } + }; +} + +// generate `ParallelIterator` methods by just forwarding to the underlying +// self.entries and mapping its elements. +#[cfg(any(feature = "rayon", feature = "rustc-rayon"))] +macro_rules! parallel_iterator_methods { + // $map_elt is the mapping function from the underlying iterator's element + ($map_elt:expr) => { + fn drive_unindexed(self, consumer: C) -> C::Result + where + C: UnindexedConsumer, + { + self.entries + .into_par_iter() + .map($map_elt) + .drive_unindexed(consumer) + } + + // NB: This allows indexed collection, e.g. directly into a `Vec`, but the + // underlying iterator must really be indexed. We should remove this if we + // start having tombstones that must be filtered out. + fn opt_len(&self) -> Option { + Some(self.entries.len()) + } + }; +} + +// generate `IndexedParallelIterator` methods by just forwarding to the underlying +// self.entries and mapping its elements. +#[cfg(any(feature = "rayon", feature = "rustc-rayon"))] +macro_rules! indexed_parallel_iterator_methods { + // $map_elt is the mapping function from the underlying iterator's element + ($map_elt:expr) => { + fn drive(self, consumer: C) -> C::Result + where + C: Consumer, + { + self.entries.into_par_iter().map($map_elt).drive(consumer) + } + + fn len(&self) -> usize { + self.entries.len() + } + + fn with_producer(self, callback: CB) -> CB::Output + where + CB: ProducerCallback, + { + self.entries + .into_par_iter() + .map($map_elt) + .with_producer(callback) + } + }; +} diff --git a/third_party/rust/indexmap/src/map.rs b/third_party/rust/indexmap/src/map.rs new file mode 100644 index 0000000000..d39448d06d --- /dev/null +++ b/third_party/rust/indexmap/src/map.rs @@ -0,0 +1,1947 @@ +//! `IndexMap` is a hash table where the iteration order of the key-value +//! pairs is independent of the hash values of the keys. + +mod core; + +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}; + +#[cfg(has_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}; + +/// A hash table where the iteration order of the key-value pairs is independent +/// of the hash values of the keys. +/// +/// The interface is closely compatible with the standard `HashMap`, but also +/// has additional features. +/// +/// # Order +/// +/// The key-value pairs have a consistent order that is determined by +/// the sequence of insertion and removal calls on the map. The order does +/// not depend on the keys or the hash function at all. +/// +/// All iterators traverse the map in *the order*. +/// +/// The insertion order is preserved, with **notable exceptions** like the +/// `.remove()` or `.swap_remove()` methods. Methods such as `.sort_by()` of +/// course result in a new order, depending on the sorting order. +/// +/// # Indices +/// +/// The key-value pairs are indexed in a compact range without holes in the +/// range `0..self.len()`. For example, the method `.get_full` looks up the +/// index for a key, and the method `.get_index` looks up the key-value pair by +/// index. +/// +/// # Examples +/// +/// ``` +/// use indexmap::IndexMap; +/// +/// // count the frequency of each letter in a sentence. +/// let mut letters = IndexMap::new(); +/// for ch in "a short treatise on fungi".chars() { +/// *letters.entry(ch).or_insert(0) += 1; +/// } +/// +/// assert_eq!(letters[&'s'], 2); +/// assert_eq!(letters[&'t'], 3); +/// assert_eq!(letters[&'u'], 1); +/// assert_eq!(letters.get(&'y'), None); +/// ``` +#[cfg(has_std)] +pub struct IndexMap { + pub(crate) core: IndexMapCore, + hash_builder: S, +} +#[cfg(not(has_std))] +pub struct IndexMap { + pub(crate) core: IndexMapCore, + hash_builder: S, +} + +impl Clone for IndexMap +where + K: Clone, + V: Clone, + S: Clone, +{ + fn clone(&self) -> Self { + IndexMap { + core: self.core.clone(), + hash_builder: self.hash_builder.clone(), + } + } + + fn clone_from(&mut self, other: &Self) { + self.core.clone_from(&other.core); + self.hash_builder.clone_from(&other.hash_builder); + } +} + +impl Entries for IndexMap { + type Entry = Bucket; + + #[inline] + fn into_entries(self) -> Vec { + self.core.into_entries() + } + + #[inline] + fn as_entries(&self) -> &[Self::Entry] { + self.core.as_entries() + } + + #[inline] + fn as_entries_mut(&mut self) -> &mut [Self::Entry] { + self.core.as_entries_mut() + } + + fn with_entries(&mut self, f: F) + where + F: FnOnce(&mut [Self::Entry]), + { + self.core.with_entries(f); + } +} + +impl fmt::Debug for IndexMap +where + K: fmt::Debug, + V: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + if cfg!(not(feature = "test_debug")) { + f.debug_map().entries(self.iter()).finish() + } else { + // Let the inner `IndexMapCore` print all of its details + f.debug_struct("IndexMap") + .field("core", &self.core) + .finish() + } + } +} + +#[cfg(has_std)] +impl IndexMap { + /// Create a new map. (Does not allocate.) + #[inline] + pub fn new() -> Self { + Self::with_capacity(0) + } + + /// Create a new map with capacity for `n` key-value pairs. (Does not + /// allocate if `n` is zero.) + /// + /// Computes in **O(n)** time. + #[inline] + pub fn with_capacity(n: usize) -> Self { + Self::with_capacity_and_hasher(n, <_>::default()) + } +} + +impl IndexMap { + /// Create a new map with capacity for `n` key-value pairs. (Does not + /// allocate if `n` is zero.) + /// + /// Computes in **O(n)** time. + #[inline] + pub fn with_capacity_and_hasher(n: usize, hash_builder: S) -> Self { + if n == 0 { + Self::with_hasher(hash_builder) + } else { + IndexMap { + core: IndexMapCore::with_capacity(n), + hash_builder, + } + } + } + + /// Create a new map with `hash_builder`. + /// + /// This function is `const`, so it + /// can be called in `static` contexts. + pub const fn with_hasher(hash_builder: S) -> Self { + IndexMap { + core: IndexMapCore::new(), + hash_builder, + } + } + + /// Computes in **O(1)** time. + pub fn capacity(&self) -> usize { + self.core.capacity() + } + + /// Return a reference to the map's `BuildHasher`. + pub fn hasher(&self) -> &S { + &self.hash_builder + } + + /// Return the number of key-value pairs in the map. + /// + /// Computes in **O(1)** time. + #[inline] + pub fn len(&self) -> usize { + self.core.len() + } + + /// Returns true if the map contains no elements. + /// + /// Computes in **O(1)** time. + #[inline] + pub fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// 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(), + } + } + + /// 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(), + } + } + + /// 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(), + } + } + + /// Return an owning iterator over the keys of the map, in their order + pub fn into_keys(self) -> IntoKeys { + IntoKeys { + iter: self.into_entries().into_iter(), + } + } + + /// 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(), + } + } + + /// 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(), + } + } + + /// Return an owning iterator over the values of the map, in their order + pub fn into_values(self) -> IntoValues { + IntoValues { + iter: self.into_entries().into_iter(), + } + } + + /// Remove all key-value pairs in the map, while preserving its capacity. + /// + /// Computes in **O(n)** time. + pub fn clear(&mut self) { + self.core.clear(); + } + + /// Shortens the map, keeping the first `len` elements and dropping the rest. + /// + /// If `len` is greater than the map's current length, this has no effect. + pub fn truncate(&mut self, len: usize) { + self.core.truncate(len); + } + + /// Clears the `IndexMap` in the given index range, returning those + /// key-value pairs as a drain iterator. + /// + /// The range may be any type that implements `RangeBounds`, + /// including all of the `std::ops::Range*` types, or even a tuple pair of + /// `Bound` start and end values. To drain the map entirely, use `RangeFull` + /// like `map.drain(..)`. + /// + /// This shifts down all entries following the drained range to fill the + /// gap, and keeps the allocated memory for reuse. + /// + /// ***Panics*** if the starting point is greater than the end point or if + /// the end point is greater than the length of the map. + pub fn drain(&mut self, range: R) -> Drain<'_, K, V> + where + R: RangeBounds, + { + Drain { + iter: self.core.drain(range), + } + } + + /// Splits the collection into two at the given index. + /// + /// Returns a newly allocated map containing the elements in the range + /// `[at, len)`. After the call, the original map will be left containing + /// the elements `[0, at)` with its previous capacity unchanged. + /// + /// ***Panics*** if `at > len`. + pub fn split_off(&mut self, at: usize) -> Self + where + S: Clone, + { + Self { + core: self.core.split_off(at), + hash_builder: self.hash_builder.clone(), + } + } +} + +impl IndexMap +where + K: Hash + Eq, + S: BuildHasher, +{ + /// Reserve capacity for `additional` more key-value pairs. + /// + /// Computes in **O(n)** time. + pub fn reserve(&mut self, additional: usize) { + self.core.reserve(additional); + } + + /// Shrink the capacity of the map as much as possible. + /// + /// Computes in **O(n)** time. + pub fn shrink_to_fit(&mut self) { + self.core.shrink_to(0); + } + + /// Shrink the capacity of the map with a lower limit. + /// + /// Computes in **O(n)** time. + pub fn shrink_to(&mut self, min_capacity: usize) { + self.core.shrink_to(min_capacity); + } + + fn hash(&self, key: &Q) -> HashValue { + let mut h = self.hash_builder.build_hasher(); + key.hash(&mut h); + HashValue(h.finish() as usize) + } + + /// Insert a key-value pair in the map. + /// + /// If an equivalent key already exists in the map: the key remains and + /// retains in its place in the order, its corresponding value is updated + /// with `value` and the older value is returned inside `Some(_)`. + /// + /// If no equivalent key existed in the map: the new key-value pair is + /// inserted, last in order, and `None` is returned. + /// + /// Computes in **O(1)** time (amortized average). + /// + /// See also [`entry`](#method.entry) if you you want to insert *or* modify + /// or if you need to get the index of the corresponding key-value pair. + pub fn insert(&mut self, key: K, value: V) -> Option { + self.insert_full(key, value).1 + } + + /// Insert a key-value pair in the map, and get their index. + /// + /// If an equivalent key already exists in the map: the key remains and + /// retains in its place in the order, its corresponding value is updated + /// with `value` and the older value is returned inside `(index, Some(_))`. + /// + /// If no equivalent key existed in the map: the new key-value pair is + /// inserted, last in order, and `(index, None)` is returned. + /// + /// Computes in **O(1)** time (amortized average). + /// + /// See also [`entry`](#method.entry) if you you want to insert *or* modify + /// or if you need to get the index of the corresponding key-value pair. + pub fn insert_full(&mut self, key: K, value: V) -> (usize, Option) { + let hash = self.hash(&key); + self.core.insert_full(hash, key, value) + } + + /// Get the given key’s corresponding entry in the map for insertion and/or + /// in-place manipulation. + /// + /// Computes in **O(1)** time (amortized average). + pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { + let hash = self.hash(&key); + self.core.entry(hash, key) + } + + /// Return `true` if an equivalent to `key` exists in the map. + /// + /// Computes in **O(1)** time (average). + pub fn contains_key(&self, key: &Q) -> bool + where + Q: Hash + Equivalent, + { + self.get_index_of(key).is_some() + } + + /// Return a reference to the value stored for `key`, if it is present, + /// else `None`. + /// + /// Computes in **O(1)** time (average). + pub fn get(&self, key: &Q) -> Option<&V> + where + Q: Hash + Equivalent, + { + if let Some(i) = self.get_index_of(key) { + let entry = &self.as_entries()[i]; + Some(&entry.value) + } else { + None + } + } + + /// Return references to the key-value pair stored for `key`, + /// if it is present, else `None`. + /// + /// Computes in **O(1)** time (average). + pub fn get_key_value(&self, key: &Q) -> Option<(&K, &V)> + where + Q: Hash + Equivalent, + { + if let Some(i) = self.get_index_of(key) { + let entry = &self.as_entries()[i]; + Some((&entry.key, &entry.value)) + } else { + None + } + } + + /// Return item index, key and value + pub fn get_full(&self, key: &Q) -> Option<(usize, &K, &V)> + where + Q: Hash + Equivalent, + { + if let Some(i) = self.get_index_of(key) { + let entry = &self.as_entries()[i]; + Some((i, &entry.key, &entry.value)) + } else { + None + } + } + + /// Return item index, if it exists in the map + /// + /// Computes in **O(1)** time (average). + pub fn get_index_of(&self, key: &Q) -> Option + where + Q: Hash + Equivalent, + { + if self.is_empty() { + None + } else { + let hash = self.hash(key); + self.core.get_index_of(hash, key) + } + } + + pub fn get_mut(&mut self, key: &Q) -> Option<&mut V> + where + Q: Hash + Equivalent, + { + if let Some(i) = self.get_index_of(key) { + let entry = &mut self.as_entries_mut()[i]; + Some(&mut entry.value) + } else { + None + } + } + + pub fn get_full_mut(&mut self, key: &Q) -> Option<(usize, &K, &mut V)> + where + Q: Hash + Equivalent, + { + if let Some(i) = self.get_index_of(key) { + let entry = &mut self.as_entries_mut()[i]; + Some((i, &entry.key, &mut entry.value)) + } else { + None + } + } + + pub(crate) fn get_full_mut2_impl( + &mut self, + key: &Q, + ) -> Option<(usize, &mut K, &mut V)> + where + Q: Hash + Equivalent, + { + 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. + /// + /// **NOTE:** This is equivalent to `.swap_remove(key)`, if you need to + /// preserve the order of the keys in the map, use `.shift_remove(key)` + /// instead. + /// + /// Computes in **O(1)** time (average). + pub fn remove(&mut self, key: &Q) -> Option + where + Q: Hash + Equivalent, + { + self.swap_remove(key) + } + + /// Remove and return the key-value pair equivalent to `key`. + /// + /// **NOTE:** This is equivalent to `.swap_remove_entry(key)`, if you need to + /// preserve the order of the keys in the map, use `.shift_remove_entry(key)` + /// instead. + /// + /// Computes in **O(1)** time (average). + pub fn remove_entry(&mut self, key: &Q) -> Option<(K, V)> + where + Q: Hash + Equivalent, + { + self.swap_remove_entry(key) + } + + /// Remove the key-value pair equivalent to `key` and return + /// its value. + /// + /// Like `Vec::swap_remove`, the pair is removed by swapping it with the + /// last element of the map and popping it off. **This perturbs + /// the position of what used to be the last element!** + /// + /// Return `None` if `key` is not in map. + /// + /// Computes in **O(1)** time (average). + pub fn swap_remove(&mut self, key: &Q) -> Option + where + Q: Hash + Equivalent, + { + self.swap_remove_full(key).map(third) + } + + /// Remove and return the key-value pair equivalent to `key`. + /// + /// Like `Vec::swap_remove`, the pair is removed by swapping it with the + /// last element of the map and popping it off. **This perturbs + /// the position of what used to be the last element!** + /// + /// Return `None` if `key` is not in map. + /// + /// Computes in **O(1)** time (average). + pub fn swap_remove_entry(&mut self, key: &Q) -> Option<(K, V)> + where + Q: Hash + Equivalent, + { + match self.swap_remove_full(key) { + Some((_, key, value)) => Some((key, value)), + None => None, + } + } + + /// Remove the key-value pair equivalent to `key` and return it and + /// the index it had. + /// + /// Like `Vec::swap_remove`, the pair is removed by swapping it with the + /// last element of the map and popping it off. **This perturbs + /// the position of what used to be the last element!** + /// + /// Return `None` if `key` is not in map. + /// + /// Computes in **O(1)** time (average). + pub fn swap_remove_full(&mut self, key: &Q) -> Option<(usize, K, V)> + where + Q: Hash + Equivalent, + { + if self.is_empty() { + return None; + } + let hash = self.hash(key); + self.core.swap_remove_full(hash, key) + } + + /// Remove the key-value pair equivalent to `key` and return + /// its value. + /// + /// Like `Vec::remove`, the pair is removed by shifting all of the + /// elements that follow it, preserving their relative order. + /// **This perturbs the index of all of those elements!** + /// + /// Return `None` if `key` is not in map. + /// + /// Computes in **O(n)** time (average). + pub fn shift_remove(&mut self, key: &Q) -> Option + where + Q: Hash + Equivalent, + { + self.shift_remove_full(key).map(third) + } + + /// Remove and return the key-value pair equivalent to `key`. + /// + /// Like `Vec::remove`, the pair is removed by shifting all of the + /// elements that follow it, preserving their relative order. + /// **This perturbs the index of all of those elements!** + /// + /// Return `None` if `key` is not in map. + /// + /// Computes in **O(n)** time (average). + pub fn shift_remove_entry(&mut self, key: &Q) -> Option<(K, V)> + where + Q: Hash + Equivalent, + { + match self.shift_remove_full(key) { + Some((_, key, value)) => Some((key, value)), + None => None, + } + } + + /// Remove the key-value pair equivalent to `key` and return it and + /// the index it had. + /// + /// Like `Vec::remove`, the pair is removed by shifting all of the + /// elements that follow it, preserving their relative order. + /// **This perturbs the index of all of those elements!** + /// + /// Return `None` if `key` is not in map. + /// + /// Computes in **O(n)** time (average). + pub fn shift_remove_full(&mut self, key: &Q) -> Option<(usize, K, V)> + where + Q: Hash + Equivalent, + { + if self.is_empty() { + return None; + } + let hash = self.hash(key); + self.core.shift_remove_full(hash, key) + } + + /// Remove the last key-value pair + /// + /// This preserves the order of the remaining elements. + /// + /// Computes in **O(1)** time (average). + pub fn pop(&mut self) -> Option<(K, V)> { + self.core.pop() + } + + /// Scan through each key-value pair in the map and keep those where the + /// closure `keep` returns `true`. + /// + /// The elements are visited in order, and remaining elements keep their + /// order. + /// + /// Computes in **O(n)** time (average). + pub fn retain(&mut self, mut keep: F) + where + F: FnMut(&K, &mut V) -> bool, + { + self.core.retain_in_order(move |k, v| keep(k, v)); + } + + pub(crate) fn retain_mut(&mut self, keep: F) + where + F: FnMut(&mut K, &mut V) -> bool, + { + self.core.retain_in_order(keep); + } + + /// Sort the map’s key-value pairs by the default ordering of the keys. + /// + /// See [`sort_by`](Self::sort_by) for details. + pub fn sort_keys(&mut self) + where + K: Ord, + { + self.with_entries(move |entries| { + entries.sort_by(move |a, b| K::cmp(&a.key, &b.key)); + }); + } + + /// Sort the map’s key-value pairs in place using the comparison + /// function `cmp`. + /// + /// The comparison function receives two key and value pairs to compare (you + /// can sort by keys or values or their combination as needed). + /// + /// Computes in **O(n log n + c)** time and **O(n)** space where *n* is + /// the length of the map and *c* the capacity. The sort is stable. + pub fn sort_by(&mut self, mut cmp: F) + where + F: FnMut(&K, &V, &K, &V) -> Ordering, + { + self.with_entries(move |entries| { + entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); + }); + } + + /// Sort the key-value pairs of the map and return a by-value iterator of + /// the key-value pairs with the result. + /// + /// The sort is stable. + pub fn sorted_by(self, mut cmp: F) -> IntoIter + where + F: FnMut(&K, &V, &K, &V) -> Ordering, + { + 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(), + } + } + + /// Sort the map's key-value pairs by the default ordering of the keys, but + /// may not preserve the order of equal elements. + /// + /// See [`sort_unstable_by`](Self::sort_unstable_by) for details. + pub fn sort_unstable_keys(&mut self) + where + K: Ord, + { + self.with_entries(move |entries| { + entries.sort_unstable_by(move |a, b| K::cmp(&a.key, &b.key)); + }); + } + + /// Sort the map's key-value pairs in place using the comparison function `cmp`, but + /// may not preserve the order of equal elements. + /// + /// The comparison function receives two key and value pairs to compare (you + /// can sort by keys or values or their combination as needed). + /// + /// Computes in **O(n log n + c)** time where *n* is + /// the length of the map and *c* is the capacity. The sort is unstable. + pub fn sort_unstable_by(&mut self, mut cmp: F) + where + F: FnMut(&K, &V, &K, &V) -> Ordering, + { + self.with_entries(move |entries| { + entries.sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); + }); + } + + /// Sort the key-value pairs of the map and return a by-value iterator of + /// the key-value pairs with the result. + /// + /// The sort is unstable. + #[inline] + pub fn sorted_unstable_by(self, mut cmp: F) -> IntoIter + where + F: FnMut(&K, &V, &K, &V) -> Ordering, + { + 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(), + } + } + + /// Reverses the order of the map’s key-value pairs in place. + /// + /// Computes in **O(n)** time and **O(1)** space. + pub fn reverse(&mut self) { + self.core.reverse() + } +} + +impl IndexMap { + /// Get a key-value pair by index + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Computes in **O(1)** time. + pub fn get_index(&self, index: usize) -> Option<(&K, &V)> { + self.as_entries().get(index).map(Bucket::refs) + } + + /// Get a key-value pair by index + /// + /// 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) + } + + /// Get the first key-value pair + /// + /// Computes in **O(1)** time. + pub fn first(&self) -> Option<(&K, &V)> { + self.as_entries().first().map(Bucket::refs) + } + + /// Get the first key-value pair, with mutable access to the value + /// + /// Computes in **O(1)** time. + pub fn first_mut(&mut self) -> Option<(&K, &mut V)> { + self.as_entries_mut().first_mut().map(Bucket::ref_mut) + } + + /// Get the last key-value pair + /// + /// Computes in **O(1)** time. + pub fn last(&self) -> Option<(&K, &V)> { + self.as_entries().last().map(Bucket::refs) + } + + /// Get the last key-value pair, with mutable access to the value + /// + /// Computes in **O(1)** time. + pub fn last_mut(&mut self) -> Option<(&K, &mut V)> { + self.as_entries_mut().last_mut().map(Bucket::ref_mut) + } + + /// Remove the key-value pair by index + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Like `Vec::swap_remove`, the pair is removed by swapping it with the + /// last element of the map and popping it off. **This perturbs + /// the position of what used to be the last element!** + /// + /// Computes in **O(1)** time (average). + pub fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> { + self.core.swap_remove_index(index) + } + + /// Remove the key-value pair by index + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Like `Vec::remove`, the pair is removed by shifting all of the + /// elements that follow it, preserving their relative order. + /// **This perturbs the index of all of those elements!** + /// + /// Computes in **O(n)** time (average). + pub fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> { + self.core.shift_remove_index(index) + } + + /// Moves the position of a key-value pair from one index to another + /// by shifting all other pairs in-between. + /// + /// * If `from < to`, the other pairs will shift down while the targeted pair moves up. + /// * If `from > to`, the other pairs will shift up while the targeted pair moves down. + /// + /// ***Panics*** if `from` or `to` are out of bounds. + /// + /// Computes in **O(n)** time (average). + pub fn move_index(&mut self, from: usize, to: usize) { + self.core.move_index(from, to) + } + + /// Swaps the position of two key-value pairs in the map. + /// + /// ***Panics*** if `a` or `b` are out of bounds. + pub fn swap_indices(&mut self, a: usize, b: usize) { + self.core.swap_indices(a, b) + } +} + +/// 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>, +} + +impl<'a, K, V> Iterator for Keys<'a, K, V> { + type Item = &'a K; + + iterator_methods!(Bucket::key_ref); +} + +impl DoubleEndedIterator for Keys<'_, K, V> { + double_ended_iterator_methods!(Bucket::key_ref); +} + +impl ExactSizeIterator for Keys<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for Keys<'_, K, V> {} + +// FIXME(#26925) Remove in favor of `#[derive(Clone)]` +impl Clone for Keys<'_, K, V> { + fn clone(&self) -> Self { + Keys { + iter: self.iter.clone(), + } + } +} + +impl 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 { + iter: vec::IntoIter>, +} + +impl Iterator for IntoKeys { + type Item = K; + + iterator_methods!(Bucket::key); +} + +impl DoubleEndedIterator for IntoKeys { + double_ended_iterator_methods!(Bucket::key); +} + +impl ExactSizeIterator for IntoKeys { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for IntoKeys {} + +impl fmt::Debug for IntoKeys { + 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>, +} + +impl<'a, K, V> Iterator for Values<'a, K, V> { + type Item = &'a V; + + iterator_methods!(Bucket::value_ref); +} + +impl DoubleEndedIterator for Values<'_, K, V> { + double_ended_iterator_methods!(Bucket::value_ref); +} + +impl ExactSizeIterator for Values<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for Values<'_, K, V> {} + +// FIXME(#26925) Remove in favor of `#[derive(Clone)]` +impl Clone for Values<'_, K, V> { + fn clone(&self) -> Self { + Values { + iter: self.iter.clone(), + } + } +} + +impl 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>, +} + +impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { + type Item = &'a mut V; + + iterator_methods!(Bucket::value_mut); +} + +impl DoubleEndedIterator for ValuesMut<'_, K, V> { + double_ended_iterator_methods!(Bucket::value_mut); +} + +impl ExactSizeIterator for ValuesMut<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for ValuesMut<'_, K, V> {} + +impl 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 { + iter: vec::IntoIter>, +} + +impl Iterator for IntoValues { + type Item = V; + + iterator_methods!(Bucket::value); +} + +impl DoubleEndedIterator for IntoValues { + double_ended_iterator_methods!(Bucket::value); +} + +impl ExactSizeIterator for IntoValues { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for IntoValues {} + +impl fmt::Debug for IntoValues { + 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>, +} + +impl<'a, K, V> Iterator for Iter<'a, K, V> { + type Item = (&'a K, &'a V); + + iterator_methods!(Bucket::refs); +} + +impl DoubleEndedIterator for Iter<'_, K, V> { + double_ended_iterator_methods!(Bucket::refs); +} + +impl ExactSizeIterator for Iter<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for Iter<'_, K, V> {} + +// FIXME(#26925) Remove in favor of `#[derive(Clone)]` +impl Clone for Iter<'_, K, V> { + fn clone(&self) -> Self { + Iter { + iter: self.iter.clone(), + } + } +} + +impl 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>, +} + +impl<'a, K, V> Iterator for IterMut<'a, K, V> { + type Item = (&'a K, &'a mut V); + + iterator_methods!(Bucket::ref_mut); +} + +impl DoubleEndedIterator for IterMut<'_, K, V> { + double_ended_iterator_methods!(Bucket::ref_mut); +} + +impl ExactSizeIterator for IterMut<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for IterMut<'_, K, V> {} + +impl 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 { + iter: vec::IntoIter>, +} + +impl Iterator for IntoIter { + type Item = (K, V); + + iterator_methods!(Bucket::key_value); +} + +impl DoubleEndedIterator for IntoIter { + double_ended_iterator_methods!(Bucket::key_value); +} + +impl ExactSizeIterator for IntoIter { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for IntoIter {} + +impl fmt::Debug for IntoIter { + 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>, +} + +impl Iterator for Drain<'_, K, V> { + type Item = (K, V); + + iterator_methods!(Bucket::key_value); +} + +impl DoubleEndedIterator for Drain<'_, K, V> { + double_ended_iterator_methods!(Bucket::key_value); +} + +impl ExactSizeIterator for Drain<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for Drain<'_, K, V> {} + +impl 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 { + 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 { + type Item = (&'a K, &'a mut V); + type IntoIter = IterMut<'a, K, V>; + fn into_iter(self) -> Self::IntoIter { + self.iter_mut() + } +} + +impl IntoIterator for IndexMap { + type Item = (K, V); + type IntoIter = IntoIter; + fn into_iter(self) -> Self::IntoIter { + IntoIter { + iter: self.into_entries().into_iter(), + } + } +} + +/// Access `IndexMap` values corresponding to a key. +/// +/// # Examples +/// +/// ``` +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// for word in "Lorem ipsum dolor sit amet".split_whitespace() { +/// map.insert(word.to_lowercase(), word.to_uppercase()); +/// } +/// assert_eq!(map["lorem"], "LOREM"); +/// assert_eq!(map["ipsum"], "IPSUM"); +/// ``` +/// +/// ```should_panic +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// map.insert("foo", 1); +/// println!("{:?}", map["bar"]); // panics! +/// ``` +impl Index<&Q> for IndexMap +where + Q: Hash + Equivalent, + K: Hash + Eq, + S: BuildHasher, +{ + type Output = V; + + /// Returns a reference to the value corresponding to the supplied `key`. + /// + /// ***Panics*** if `key` is not present in the map. + fn index(&self, key: &Q) -> &V { + self.get(key).expect("IndexMap: key not found") + } +} + +/// Access `IndexMap` values corresponding to a key. +/// +/// Mutable indexing allows changing / updating values of key-value +/// pairs that are already present. +/// +/// You can **not** insert new pairs with index syntax, use `.insert()`. +/// +/// # Examples +/// +/// ``` +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// for word in "Lorem ipsum dolor sit amet".split_whitespace() { +/// map.insert(word.to_lowercase(), word.to_string()); +/// } +/// let lorem = &mut map["lorem"]; +/// assert_eq!(lorem, "Lorem"); +/// lorem.retain(char::is_lowercase); +/// assert_eq!(map["lorem"], "orem"); +/// ``` +/// +/// ```should_panic +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// map.insert("foo", 1); +/// map["bar"] = 1; // panics! +/// ``` +impl IndexMut<&Q> for IndexMap +where + Q: Hash + Equivalent, + K: Hash + Eq, + S: BuildHasher, +{ + /// Returns a mutable reference to the value corresponding to the supplied `key`. + /// + /// ***Panics*** if `key` is not present in the map. + fn index_mut(&mut self, key: &Q) -> &mut V { + self.get_mut(key).expect("IndexMap: key not found") + } +} + +/// Access `IndexMap` values at indexed positions. +/// +/// # Examples +/// +/// ``` +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// for word in "Lorem ipsum dolor sit amet".split_whitespace() { +/// map.insert(word.to_lowercase(), word.to_uppercase()); +/// } +/// assert_eq!(map[0], "LOREM"); +/// assert_eq!(map[1], "IPSUM"); +/// map.reverse(); +/// assert_eq!(map[0], "AMET"); +/// assert_eq!(map[1], "SIT"); +/// map.sort_keys(); +/// assert_eq!(map[0], "AMET"); +/// assert_eq!(map[1], "DOLOR"); +/// ``` +/// +/// ```should_panic +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// map.insert("foo", 1); +/// println!("{:?}", map[10]); // panics! +/// ``` +impl Index for IndexMap { + type Output = V; + + /// Returns a reference to the value at the supplied `index`. + /// + /// ***Panics*** if `index` is out of bounds. + fn index(&self, index: usize) -> &V { + self.get_index(index) + .expect("IndexMap: index out of bounds") + .1 + } +} + +/// Access `IndexMap` values at indexed positions. +/// +/// Mutable indexing allows changing / updating indexed values +/// that are already present. +/// +/// You can **not** insert new values with index syntax, use `.insert()`. +/// +/// # Examples +/// +/// ``` +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// for word in "Lorem ipsum dolor sit amet".split_whitespace() { +/// map.insert(word.to_lowercase(), word.to_string()); +/// } +/// let lorem = &mut map[0]; +/// assert_eq!(lorem, "Lorem"); +/// lorem.retain(char::is_lowercase); +/// assert_eq!(map["lorem"], "orem"); +/// ``` +/// +/// ```should_panic +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// map.insert("foo", 1); +/// map[10] = 1; // panics! +/// ``` +impl IndexMut for IndexMap { + /// Returns a mutable reference to the value at the supplied `index`. + /// + /// ***Panics*** if `index` is out of bounds. + fn index_mut(&mut self, index: usize) -> &mut V { + self.get_index_mut(index) + .expect("IndexMap: index out of bounds") + .1 + } +} + +impl FromIterator<(K, V)> for IndexMap +where + K: Hash + Eq, + S: BuildHasher + Default, +{ + /// Create an `IndexMap` from the sequence of key-value pairs in the + /// iterable. + /// + /// `from_iter` uses the same logic as `extend`. See + /// [`extend`](#method.extend) for more details. + fn from_iter>(iterable: I) -> Self { + let iter = iterable.into_iter(); + let (low, _) = iter.size_hint(); + let mut map = Self::with_capacity_and_hasher(low, <_>::default()); + map.extend(iter); + map + } +} + +#[cfg(has_std)] +impl From<[(K, V); N]> for IndexMap +where + K: Hash + Eq, +{ + /// # Examples + /// + /// ``` + /// use indexmap::IndexMap; + /// + /// let map1 = IndexMap::from([(1, 2), (3, 4)]); + /// let map2: IndexMap<_, _> = [(1, 2), (3, 4)].into(); + /// assert_eq!(map1, map2); + /// ``` + fn from(arr: [(K, V); N]) -> Self { + Self::from_iter(arr) + } +} + +impl Extend<(K, V)> for IndexMap +where + K: Hash + Eq, + S: BuildHasher, +{ + /// Extend the map with all key-value pairs in the iterable. + /// + /// This is equivalent to calling [`insert`](#method.insert) for each of + /// them in order, which means that for keys that already existed + /// in the map, their value is updated but it keeps the existing order. + /// + /// New keys are inserted in the order they appear in the sequence. If + /// equivalents of a key occur more than once, the last corresponding value + /// prevails. + fn extend>(&mut self, iterable: I) { + // (Note: this is a copy of `std`/`hashbrown`'s reservation logic.) + // Keys may be already present or show multiple times in the iterator. + // Reserve the entire hint lower bound if the map is empty. + // Otherwise reserve half the hint (rounded up), so the map + // will only resize twice in the worst case. + let iter = iterable.into_iter(); + let reserve = if self.is_empty() { + iter.size_hint().0 + } else { + (iter.size_hint().0 + 1) / 2 + }; + self.reserve(reserve); + iter.for_each(move |(k, v)| { + self.insert(k, v); + }); + } +} + +impl<'a, K, V, S> Extend<(&'a K, &'a V)> for IndexMap +where + K: Hash + Eq + Copy, + V: Copy, + S: BuildHasher, +{ + /// Extend the map with all key-value pairs in the iterable. + /// + /// See the first extend method for more details. + fn extend>(&mut self, iterable: I) { + self.extend(iterable.into_iter().map(|(&key, &value)| (key, value))); + } +} + +impl Default for IndexMap +where + S: Default, +{ + /// Return an empty `IndexMap` + fn default() -> Self { + Self::with_capacity_and_hasher(0, S::default()) + } +} + +impl PartialEq> for IndexMap +where + K: Hash + Eq, + V1: PartialEq, + S1: BuildHasher, + S2: BuildHasher, +{ + fn eq(&self, other: &IndexMap) -> bool { + if self.len() != other.len() { + return false; + } + + self.iter() + .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v)) + } +} + +impl Eq for IndexMap +where + K: Eq + Hash, + V: Eq, + 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::::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::::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::::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![(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 = 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 = 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/third_party/rust/indexmap/src/map/core.rs b/third_party/rust/indexmap/src/map/core.rs new file mode 100644 index 0000000000..ea7aaae62e --- /dev/null +++ b/third_party/rust/indexmap/src/map/core.rs @@ -0,0 +1,700 @@ +//! This is the core implementation that doesn't depend on the hasher at all. +//! +//! The methods of `IndexMapCore` don't use any Hash properties of K. +//! +//! It's cleaner to separate them out, then the compiler checks that we are not +//! using Hash at all in these methods. +//! +//! However, we should probably not let this show in the public API or docs. + +mod raw; + +use hashbrown::raw::RawTable; + +use crate::vec::{Drain, Vec}; +use core::cmp; +use core::fmt; +use core::mem::replace; +use core::ops::RangeBounds; + +use crate::equivalent::Equivalent; +use crate::util::simplify_range; +use crate::{Bucket, Entries, HashValue}; + +/// Core of the map that does not depend on S +pub(crate) struct IndexMapCore { + /// indices mapping from the entry hash to its index. + indices: RawTable, + /// entries is a dense vec of entries in their order. + entries: Vec>, +} + +#[inline(always)] +fn get_hash(entries: &[Bucket]) -> impl Fn(&usize) -> u64 + '_ { + move |&i| entries[i].hash.get() +} + +#[inline] +fn equivalent<'a, K, V, Q: ?Sized + Equivalent>( + key: &'a Q, + entries: &'a [Bucket], +) -> impl Fn(&usize) -> bool + 'a { + move |&i| Q::equivalent(key, &entries[i].key) +} + +#[inline] +fn erase_index(table: &mut RawTable, hash: HashValue, index: usize) { + let erased = table.erase_entry(hash.get(), move |&i| i == index); + debug_assert!(erased); +} + +#[inline] +fn update_index(table: &mut RawTable, hash: HashValue, old: usize, new: usize) { + let index = table + .get_mut(hash.get(), move |&i| i == old) + .expect("index not found"); + *index = new; +} + +impl Clone for IndexMapCore +where + K: Clone, + 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 } + } + + 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(); + } + self.entries.clone_from(&other.entries); + } +} + +impl fmt::Debug for IndexMapCore +where + K: fmt::Debug, + V: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("IndexMapCore") + .field("indices", &raw::DebugIndices(&self.indices)) + .field("entries", &self.entries) + .finish() + } +} + +impl Entries for IndexMapCore { + type Entry = Bucket; + + #[inline] + fn into_entries(self) -> Vec { + self.entries + } + + #[inline] + fn as_entries(&self) -> &[Self::Entry] { + &self.entries + } + + #[inline] + fn as_entries_mut(&mut self) -> &mut [Self::Entry] { + &mut self.entries + } + + fn with_entries(&mut self, f: F) + where + F: FnOnce(&mut [Self::Entry]), + { + f(&mut self.entries); + self.rebuild_hash_table(); + } +} + +impl IndexMapCore { + #[inline] + pub(crate) const fn new() -> Self { + IndexMapCore { + indices: RawTable::new(), + entries: Vec::new(), + } + } + + #[inline] + pub(crate) fn with_capacity(n: usize) -> Self { + IndexMapCore { + indices: RawTable::with_capacity(n), + entries: Vec::with_capacity(n), + } + } + + #[inline] + pub(crate) fn len(&self) -> usize { + self.indices.len() + } + + #[inline] + pub(crate) fn capacity(&self) -> usize { + cmp::min(self.indices.capacity(), self.entries.capacity()) + } + + pub(crate) fn clear(&mut self) { + self.indices.clear(); + self.entries.clear(); + } + + pub(crate) fn truncate(&mut self, len: usize) { + if len < self.len() { + self.erase_indices(len, self.entries.len()); + self.entries.truncate(len); + } + } + + pub(crate) fn drain(&mut self, range: R) -> Drain<'_, Bucket> + where + R: RangeBounds, + { + let range = simplify_range(range, self.entries.len()); + self.erase_indices(range.start, range.end); + self.entries.drain(range) + } + + #[cfg(feature = "rayon")] + pub(crate) fn par_drain(&mut self, range: R) -> rayon::vec::Drain<'_, Bucket> + where + K: Send, + V: Send, + R: RangeBounds, + { + use rayon::iter::ParallelDrainRange; + let range = simplify_range(range, self.entries.len()); + self.erase_indices(range.start, range.end); + self.entries.par_drain(range) + } + + pub(crate) fn split_off(&mut self, at: usize) -> Self { + assert!(at <= self.entries.len()); + self.erase_indices(at, self.entries.len()); + let entries = self.entries.split_off(at); + + let mut indices = RawTable::with_capacity(entries.len()); + raw::insert_bulk_no_grow(&mut indices, &entries); + Self { indices, entries } + } + + /// 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(); + } + + /// Reserve entries capacity to match the indices + fn reserve_entries(&mut self) { + let additional = self.indices.capacity() - self.entries.len(); + self.entries.reserve_exact(additional); + } + + /// Shrink the capacity of the map with a lower bound + pub(crate) fn shrink_to(&mut self, min_capacity: usize) { + self.indices + .shrink_to(min_capacity, get_hash(&self.entries)); + self.entries.shrink_to(min_capacity); + } + + /// Remove the last key-value pair + pub(crate) fn pop(&mut self) -> Option<(K, V)> { + if let Some(entry) = self.entries.pop() { + let last = self.entries.len(); + erase_index(&mut self.indices, entry.hash, last); + Some((entry.key, entry.value)) + } else { + None + } + } + + /// 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() { + // Reserve our own capacity synced to the indices, + // rather than letting `Vec::push` just double it. + self.reserve_entries(); + } + self.entries.push(Bucket { hash, key, value }); + i + } + + /// Return the index in `entries` where an equivalent key can be found + pub(crate) fn get_index_of(&self, hash: HashValue, key: &Q) -> Option + where + Q: ?Sized + Equivalent, + { + let eq = equivalent(key, &self.entries); + self.indices.get(hash.get(), eq).copied() + } + + pub(crate) fn insert_full(&mut self, hash: HashValue, key: K, value: V) -> (usize, Option) + 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), + } + } + + /// Remove an entry by shifting all entries that follow it + pub(crate) fn shift_remove_full(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)> + where + Q: ?Sized + Equivalent, + { + let eq = equivalent(key, &self.entries); + match self.indices.remove_entry(hash.get(), eq) { + Some(index) => { + let (key, value) = self.shift_remove_finish(index); + Some((index, key, value)) + } + None => None, + } + } + + /// Remove an entry by shifting all entries that follow it + pub(crate) fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> { + match self.entries.get(index) { + Some(entry) => { + erase_index(&mut self.indices, entry.hash, index); + Some(self.shift_remove_finish(index)) + } + None => None, + } + } + + /// Remove an entry by shifting all entries that follow it + /// + /// The index should already be removed from `self.indices`. + fn shift_remove_finish(&mut self, index: usize) -> (K, V) { + // Correct indices that point to the entries that followed the removed entry. + self.decrement_indices(index + 1, self.entries.len()); + + // Use Vec::remove to actually remove the entry. + let entry = self.entries.remove(index); + (entry.key, entry.value) + } + + /// Decrement all indices in the range `start..end`. + /// + /// The index `start - 1` should not exist in `self.indices`. + /// All entries should still be in their original positions. + fn decrement_indices(&mut self, start: usize, end: usize) { + // Use a heuristic between a full sweep vs. a `find()` for every shifted item. + let shifted_entries = &self.entries[start..end]; + if shifted_entries.len() > self.indices.buckets() / 2 { + // Shift all indices in range. + for i in self.indices_mut() { + if start <= *i && *i < end { + *i -= 1; + } + } + } else { + // Find each entry in range to shift its index. + for (i, entry) in (start..end).zip(shifted_entries) { + update_index(&mut self.indices, entry.hash, i, i - 1); + } + } + } + + /// Increment all indices in the range `start..end`. + /// + /// The index `end` should not exist in `self.indices`. + /// All entries should still be in their original positions. + fn increment_indices(&mut self, start: usize, end: usize) { + // Use a heuristic between a full sweep vs. a `find()` for every shifted item. + let shifted_entries = &self.entries[start..end]; + if shifted_entries.len() > self.indices.buckets() / 2 { + // Shift all indices in range. + for i in self.indices_mut() { + if start <= *i && *i < end { + *i += 1; + } + } + } else { + // Find each entry in range to shift its index, updated in reverse so + // we never have duplicated indices that might have a hash collision. + for (i, entry) in (start..end).zip(shifted_entries).rev() { + update_index(&mut self.indices, entry.hash, i, i + 1); + } + } + } + + 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. + update_index(&mut self.indices, from_hash, from, usize::MAX); + + // Update all other indices and rotate the entry positions. + if from < to { + self.decrement_indices(from + 1, to + 1); + self.entries[from..=to].rotate_left(1); + } else if to < from { + self.increment_indices(to, from); + self.entries[to..=from].rotate_right(1); + } + + // Change the sentinal index to its final position. + update_index(&mut self.indices, from_hash, usize::MAX, to); + } + } + + /// Remove an entry by swapping it with the last + pub(crate) fn swap_remove_full(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)> + where + Q: ?Sized + Equivalent, + { + let eq = equivalent(key, &self.entries); + match self.indices.remove_entry(hash.get(), eq) { + Some(index) => { + let (key, value) = self.swap_remove_finish(index); + Some((index, key, value)) + } + None => None, + } + } + + /// Remove an entry by swapping it with the last + pub(crate) fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> { + match self.entries.get(index) { + Some(entry) => { + erase_index(&mut self.indices, entry.hash, index); + Some(self.swap_remove_finish(index)) + } + None => None, + } + } + + /// Finish removing an entry by swapping it with the last + /// + /// The index should already be removed from `self.indices`. + fn swap_remove_finish(&mut self, index: usize) -> (K, V) { + // use swap_remove, but then we need to update the index that points + // to the other entry that has to move + let entry = self.entries.swap_remove(index); + + // correct index that points to the entry that had to swap places + if let Some(entry) = self.entries.get(index) { + // was not last element + // examine new element in `index` and find it in indices + let last = self.entries.len(); + update_index(&mut self.indices, entry.hash, last, index); + } + + (entry.key, entry.value) + } + + /// Erase `start..end` from `indices`, and shift `end..` indices down to `start..` + /// + /// All of these items should still be at their original location in `entries`. + /// This is used by `drain`, which will let `Vec::drain` do the work on `entries`. + fn erase_indices(&mut self, start: usize, end: usize) { + let (init, shifted_entries) = self.entries.split_at(end); + let (start_entries, erased_entries) = init.split_at(start); + + let erased = erased_entries.len(); + let shifted = shifted_entries.len(); + let half_capacity = self.indices.buckets() / 2; + + // Use a heuristic between different strategies + if erased == 0 { + // Degenerate case, nothing to do + } else if start + shifted < half_capacity && start < erased { + // Reinsert everything, as there are few kept indices + self.indices.clear(); + + // Reinsert stable indices, then shifted indices + raw::insert_bulk_no_grow(&mut self.indices, start_entries); + raw::insert_bulk_no_grow(&mut self.indices, shifted_entries); + } else if erased + shifted < half_capacity { + // Find each affected index, as there are few to adjust + + // Find erased indices + for (i, entry) in (start..).zip(erased_entries) { + erase_index(&mut self.indices, entry.hash, i); + } + + // Find shifted indices + for ((new, old), entry) in (start..).zip(end..).zip(shifted_entries) { + update_index(&mut self.indices, entry.hash, old, new); + } + } else { + // Sweep the whole table for adjustments + self.erase_indices_sweep(start, end); + } + + debug_assert_eq!(self.indices.len(), start + shifted); + } + + pub(crate) fn retain_in_order(&mut self, mut keep: F) + 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.rebuild_hash_table(); + } + } + + fn rebuild_hash_table(&mut self) { + self.indices.clear(); + raw::insert_bulk_no_grow(&mut self.indices, &self.entries); + } + + pub(crate) fn reverse(&mut self) { + self.entries.reverse(); + + // No need to save hash indices, can easily calculate what they should + // be, given that this is an in-place reversal. + let len = self.entries.len(); + for i in self.indices_mut() { + *i = len - *i - 1; + } + } +} + +/// Entry for an existing key-value pair or a vacant location to +/// insert one. +pub enum Entry<'a, K, V> { + /// Existing slot with equivalent key. + Occupied(OccupiedEntry<'a, K, V>), + /// Vacant slot (no equivalent key in the map). + Vacant(VacantEntry<'a, K, V>), +} + +impl<'a, K, V> Entry<'a, K, V> { + /// Inserts the given default value in the entry if it is vacant and returns a mutable + /// reference to it. Otherwise a mutable reference to an already existent value is returned. + /// + /// Computes in **O(1)** time (amortized average). + pub fn or_insert(self, default: V) -> &'a mut V { + match self { + Entry::Occupied(entry) => entry.into_mut(), + Entry::Vacant(entry) => entry.insert(default), + } + } + + /// Inserts the result of the `call` function in the entry if it is vacant and returns a mutable + /// reference to it. Otherwise a mutable reference to an already existent value is returned. + /// + /// Computes in **O(1)** time (amortized average). + pub fn or_insert_with(self, call: F) -> &'a mut V + where + F: FnOnce() -> V, + { + match self { + Entry::Occupied(entry) => entry.into_mut(), + Entry::Vacant(entry) => entry.insert(call()), + } + } + + /// Inserts the result of the `call` function with a reference to the entry's key if it is + /// vacant, and returns a mutable reference to the new value. Otherwise a mutable reference to + /// an already existent value is returned. + /// + /// Computes in **O(1)** time (amortized average). + pub fn or_insert_with_key(self, call: F) -> &'a mut V + where + F: FnOnce(&K) -> V, + { + match self { + Entry::Occupied(entry) => entry.into_mut(), + Entry::Vacant(entry) => { + let value = call(&entry.key); + entry.insert(value) + } + } + } + + /// Gets a reference to the entry's key, either within the map if occupied, + /// or else the new key that was used to find the entry. + pub fn key(&self) -> &K { + match *self { + Entry::Occupied(ref entry) => entry.key(), + Entry::Vacant(ref entry) => entry.key(), + } + } + + /// Return the index where the key-value pair exists or will be inserted. + pub fn index(&self) -> usize { + match *self { + Entry::Occupied(ref entry) => entry.index(), + Entry::Vacant(ref entry) => entry.index(), + } + } + + /// Modifies the entry if it is occupied. + pub fn and_modify(self, f: F) -> Self + where + F: FnOnce(&mut V), + { + match self { + Entry::Occupied(mut o) => { + f(o.get_mut()); + Entry::Occupied(o) + } + x => x, + } + } + + /// Inserts a default-constructed value in the entry if it is vacant and returns a mutable + /// reference to it. Otherwise a mutable reference to an already existent value is returned. + /// + /// Computes in **O(1)** time (amortized average). + pub fn or_default(self) -> &'a mut V + where + V: Default, + { + match self { + Entry::Occupied(entry) => entry.into_mut(), + Entry::Vacant(entry) => entry.insert(V::default()), + } + } +} + +impl fmt::Debug for Entry<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match *self { + Entry::Vacant(ref v) => f.debug_tuple(stringify!(Entry)).field(v).finish(), + Entry::Occupied(ref o) => f.debug_tuple(stringify!(Entry)).field(o).finish(), + } + } +} + +pub use self::raw::OccupiedEntry; + +// Extra methods that don't threaten the unsafe encapsulation. +impl 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) + } + + /// Remove the key, value pair stored in the map for this entry, and return the value. + /// + /// **NOTE:** This is equivalent to `.swap_remove()`. + pub fn remove(self) -> V { + self.swap_remove() + } + + /// Remove the key, value pair stored in the map for this entry, and return the value. + /// + /// Like `Vec::swap_remove`, the pair is removed by swapping it with the + /// last element of the map and popping it off. **This perturbs + /// the position of what used to be the last element!** + /// + /// Computes in **O(1)** time (average). + pub fn swap_remove(self) -> V { + self.swap_remove_entry().1 + } + + /// Remove the key, value pair stored in the map for this entry, and return the value. + /// + /// Like `Vec::remove`, the pair is removed by shifting all of the + /// elements that follow it, preserving their relative order. + /// **This perturbs the index of all of those elements!** + /// + /// Computes in **O(n)** time (average). + pub fn shift_remove(self) -> V { + self.shift_remove_entry().1 + } + + /// Remove and return the key, value pair stored in the map for this entry + /// + /// **NOTE:** This is equivalent to `.swap_remove_entry()`. + pub fn remove_entry(self) -> (K, V) { + self.swap_remove_entry() + } +} + +impl fmt::Debug for OccupiedEntry<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct(stringify!(OccupiedEntry)) + .field("key", self.key()) + .field("value", self.get()) + .finish() + } +} + +/// A view into a vacant entry in a `IndexMap`. +/// It is part of the [`Entry`] enum. +/// +/// [`Entry`]: enum.Entry.html +pub struct VacantEntry<'a, K, V> { + map: &'a mut IndexMapCore, + hash: HashValue, + key: K, +} + +impl<'a, K, V> VacantEntry<'a, K, V> { + /// Gets a reference to the key that was used to find the entry. + pub fn key(&self) -> &K { + &self.key + } + + /// Takes ownership of the key, leaving the entry vacant. + pub fn into_key(self) -> K { + self.key + } + + /// Return the index where the key-value pair will be inserted. + pub fn index(&self) -> usize { + self.map.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 + } +} + +impl fmt::Debug for VacantEntry<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple(stringify!(VacantEntry)) + .field(self.key()) + .finish() + } +} + +#[test] +fn assert_send_sync() { + fn assert_send_sync() {} + assert_send_sync::>(); + assert_send_sync::>(); +} diff --git a/third_party/rust/indexmap/src/map/core/raw.rs b/third_party/rust/indexmap/src/map/core/raw.rs new file mode 100644 index 0000000000..bf1672d52a --- /dev/null +++ b/third_party/rust/indexmap/src/map/core/raw.rs @@ -0,0 +1,191 @@ +#![allow(unsafe_code)] +//! 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 core::fmt; +use core::mem::replace; +use hashbrown::raw::RawTable; + +type RawBucket = hashbrown::raw::Bucket; + +/// Inserts many entries into a raw table without reallocating. +/// +/// ***Panics*** if there is not sufficient capacity already. +pub(super) fn insert_bulk_no_grow(indices: &mut RawTable, entries: &[Bucket]) { + assert!(indices.capacity() - indices.len() >= entries.len()); + for entry in entries { + // SAFETY: we asserted that sufficient capacity exists for all entries. + unsafe { + indices.insert_no_grow(entry.hash.get(), indices.len()); + } + } +} + +pub(super) struct DebugIndices<'a>(pub &'a RawTable); +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()) }; + f.debug_list().entries(indices).finish() + } +} + +impl IndexMapCore { + /// Sweep the whole table to erase indices start..end + pub(super) fn erase_indices_sweep(&mut self, start: usize, end: usize) { + // SAFETY: we're not letting any of the buckets escape this function + 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 { + self.indices.erase(bucket); + } + } + } + } + + pub(crate) fn entry(&mut self, hash: HashValue, key: K) -> Entry<'_, K, V> + where + K: Eq, + { + let eq = equivalent(&key, &self.entries); + match self.indices.find(hash.get(), eq) { + // SAFETY: The entry is created with a live raw bucket, at the same time + // we have a &mut reference to the map, so it can not be modified further. + Some(raw_bucket) => Entry::Occupied(OccupiedEntry { + map: self, + raw_bucket, + key, + }), + None => Entry::Vacant(VacantEntry { + map: self, + hash, + key, + }), + } + } + + pub(super) fn indices_mut(&mut self) -> impl Iterator { + // SAFETY: we're not letting any of the buckets escape this function, + // only the item references that are appropriately bound to `&mut self`. + unsafe { self.indices.iter().map(|bucket| bucket.as_mut()) } + } + + /// Return the raw bucket for the given index + fn find_index(&self, index: usize) -> RawBucket { + // We'll get a "nice" bounds-check from indexing `self.entries`, + // and then we expect to find it in the table as well. + let hash = self.entries[index].hash.get(); + self.indices + .find(hash, move |&i| i == index) + .expect("index not found") + } + + pub(crate) fn swap_indices(&mut self, a: usize, b: usize) { + // SAFETY: Can't take two `get_mut` references from one table, so we + // must use raw buckets to do the swap. This is still safe because we + // are locally sure they won't dangle, and we write them individually. + 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); + } + self.entries.swap(a, b); + } +} + +/// A view into an occupied entry in a `IndexMap`. +/// It is part of the [`Entry`] enum. +/// +/// [`Entry`]: enum.Entry.html +// SAFETY: The lifetime of the map reference also constrains the raw bucket, +// which is essentially a raw pointer into the map indices. +pub struct OccupiedEntry<'a, K, V> { + map: &'a mut IndexMapCore, + raw_bucket: RawBucket, + key: K, +} + +// `hashbrown::raw::Bucket` is only `Send`, not `Sync`. +// SAFETY: `&self` only accesses the bucket to read it. +unsafe impl Sync for OccupiedEntry<'_, K, V> {} + +// The parent module also adds methods that don't threaten the unsafe encapsulation. +impl<'a, K, V> OccupiedEntry<'a, K, V> { + /// Gets a reference to the entry's key in the map. + /// + /// Note that this is not the key that was used to find the entry. There may be an observable + /// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like + /// extra fields or the memory address of an allocation. + pub fn key(&self) -> &K { + &self.map.entries[self.index()].key + } + + /// Gets a reference to the entry's value in the map. + pub fn get(&self) -> &V { + &self.map.entries[self.index()].value + } + + /// Gets a mutable reference to the entry's value in the map. + /// + /// If you need a reference which may outlive the destruction of the + /// `Entry` value, see `into_mut`. + pub fn get_mut(&mut self) -> &mut V { + let index = self.index(); + &mut self.map.entries[index].value + } + + /// Put the new key in the occupied entry's key slot + pub(crate) fn replace_key(self) -> K { + let index = self.index(); + let old_key = &mut self.map.entries[index].key; + replace(old_key, self.key) + } + + /// Return the index of the key-value pair + #[inline] + pub fn index(&self) -> usize { + // SAFETY: we have &mut map keep keeping the bucket stable + unsafe { self.raw_bucket.read() } + } + + /// Converts into a mutable reference to the entry's value in the map, + /// with a lifetime bound to the map itself. + pub fn into_mut(self) -> &'a mut V { + let index = self.index(); + &mut self.map.entries[index].value + } + + /// Remove and return the key, value pair stored in the map for this entry + /// + /// Like `Vec::swap_remove`, the pair is removed by swapping it with the + /// last element of the map and popping it off. **This perturbs + /// the position of what used to be the last element!** + /// + /// Computes in **O(1)** time (average). + 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) }; + self.map.swap_remove_finish(index) + } + + /// Remove and return the key, value pair stored in the map for this entry + /// + /// Like `Vec::remove`, the pair is removed by shifting all of the + /// elements that follow it, preserving their relative order. + /// **This perturbs the index of all of those elements!** + /// + /// Computes in **O(n)** time (average). + 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) }; + self.map.shift_remove_finish(index) + } +} diff --git a/third_party/rust/indexmap/src/mutable_keys.rs b/third_party/rust/indexmap/src/mutable_keys.rs new file mode 100644 index 0000000000..35a90c4723 --- /dev/null +++ b/third_party/rust/indexmap/src/mutable_keys.rs @@ -0,0 +1,75 @@ +use core::hash::{BuildHasher, Hash}; + +use super::{Equivalent, IndexMap}; + +pub struct PrivateMarker {} + +/// Opt-in mutable access to keys. +/// +/// These methods expose `&mut K`, mutable references to the key as it is stored +/// in the map. +/// You are allowed to modify the keys in the hashmap **if the modification +/// does not change the key’s hash and equality**. +/// +/// If keys are modified erroneously, you can no longer look them up. +/// This is sound (memory safe) but a logical error hazard (just like +/// implementing PartialEq, Eq, or Hash incorrectly would be). +/// +/// `use` this trait to enable its methods for `IndexMap`. +pub trait MutableKeys { + type Key; + type Value; + + /// Return item index, mutable reference to key and value + fn get_full_mut2( + &mut self, + key: &Q, + ) -> Option<(usize, &mut Self::Key, &mut Self::Value)> + where + Q: Hash + Equivalent; + + /// Scan through each key-value pair in the map and keep those where the + /// closure `keep` returns `true`. + /// + /// The elements are visited in order, and remaining elements keep their + /// order. + /// + /// Computes in **O(n)** time (average). + fn retain2(&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. +/// +/// See [`MutableKeys`](trait.MutableKeys.html) for more information. +impl MutableKeys for IndexMap +where + K: Eq + Hash, + S: BuildHasher, +{ + type Key = K; + type Value = V; + fn get_full_mut2(&mut self, key: &Q) -> Option<(usize, &mut K, &mut V)> + where + Q: Hash + Equivalent, + { + self.get_full_mut2_impl(key) + } + + fn retain2(&mut self, keep: F) + where + F: FnMut(&mut K, &mut V) -> bool, + { + self.retain_mut(keep) + } + + fn __private_marker(&self) -> PrivateMarker { + PrivateMarker {} + } +} diff --git a/third_party/rust/indexmap/src/rayon/map.rs b/third_party/rust/indexmap/src/rayon/map.rs new file mode 100644 index 0000000000..8819f13ed7 --- /dev/null +++ b/third_party/rust/indexmap/src/rayon/map.rs @@ -0,0 +1,583 @@ +//! Parallel iterator types for `IndexMap` with [rayon](https://docs.rs/rayon/1.0/rayon). +//! +//! 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 core::cmp::Ordering; +use core::fmt; +use core::hash::{BuildHasher, Hash}; +use core::ops::RangeBounds; + +use crate::Bucket; +use crate::Entries; +use crate::IndexMap; + +/// Requires crate feature `"rayon"`. +impl IntoParallelIterator for IndexMap +where + K: Send, + V: Send, +{ + type Item = (K, V); + type Iter = IntoParIter; + + 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`] +/// (provided by rayon's `IntoParallelIterator` trait). See its documentation for more. +/// +/// [`into_par_iter`]: ../struct.IndexMap.html#method.into_par_iter +/// [`IndexMap`]: ../struct.IndexMap.html +pub struct IntoParIter { + entries: Vec>, +} + +impl fmt::Debug for IntoParIter { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.entries.iter().map(Bucket::refs); + f.debug_list().entries(iter).finish() + } +} + +impl ParallelIterator for IntoParIter { + type Item = (K, V); + + parallel_iterator_methods!(Bucket::key_value); +} + +impl IndexedParallelIterator for IntoParIter { + indexed_parallel_iterator_methods!(Bucket::key_value); +} + +/// Requires crate feature `"rayon"`. +impl<'a, K, V, S> IntoParallelIterator for &'a IndexMap +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.as_entries(), + } + } +} + +/// A parallel iterator over the entries of a `IndexMap`. +/// +/// This `struct` is created by the [`par_iter`] method on [`IndexMap`] +/// (provided by rayon's `IntoParallelRefIterator` trait). See its documentation for more. +/// +/// [`par_iter`]: ../struct.IndexMap.html#method.par_iter +/// [`IndexMap`]: ../struct.IndexMap.html +pub struct ParIter<'a, K, V> { + entries: &'a [Bucket], +} + +impl Clone for ParIter<'_, K, V> { + fn clone(&self) -> Self { + ParIter { ..*self } + } +} + +impl fmt::Debug for ParIter<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.entries.iter().map(Bucket::refs); + f.debug_list().entries(iter).finish() + } +} + +impl<'a, K: Sync, V: Sync> ParallelIterator for ParIter<'a, K, V> { + type Item = (&'a K, &'a V); + + parallel_iterator_methods!(Bucket::refs); +} + +impl 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 +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: self.as_entries_mut(), + } + } +} + +/// A parallel mutable iterator over the entries of a `IndexMap`. +/// +/// This `struct` is created by the [`par_iter_mut`] method on [`IndexMap`] +/// (provided by rayon's `IntoParallelRefMutIterator` trait). See its documentation for more. +/// +/// [`par_iter_mut`]: ../struct.IndexMap.html#method.par_iter_mut +/// [`IndexMap`]: ../struct.IndexMap.html +pub struct ParIterMut<'a, K, V> { + entries: &'a mut [Bucket], +} + +impl fmt::Debug for ParIterMut<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.entries.iter().map(Bucket::refs); + f.debug_list().entries(iter).finish() + } +} + +impl<'a, K: Sync + Send, V: Send> ParallelIterator for ParIterMut<'a, K, V> { + type Item = (&'a K, &'a mut V); + + parallel_iterator_methods!(Bucket::ref_mut); +} + +impl IndexedParallelIterator for ParIterMut<'_, K, V> { + indexed_parallel_iterator_methods!(Bucket::ref_mut); +} + +/// Requires crate feature `"rayon"`. +impl<'a, K, V, S> ParallelDrainRange for &'a mut IndexMap +where + K: Send, + V: Send, +{ + type Item = (K, V); + type Iter = ParDrain<'a, K, V>; + + fn par_drain>(self, range: R) -> Self::Iter { + ParDrain { + entries: self.core.par_drain(range), + } + } +} + +/// A parallel draining iterator over the entries of a `IndexMap`. +/// +/// This `struct` is created by the [`par_drain`] method on [`IndexMap`] +/// (provided by rayon's `ParallelDrainRange` trait). See its documentation for more. +/// +/// [`par_drain`]: ../struct.IndexMap.html#method.par_drain +/// [`IndexMap`]: ../struct.IndexMap.html +pub struct ParDrain<'a, K: Send, V: Send> { + entries: rayon::vec::Drain<'a, Bucket>, +} + +impl ParallelIterator for ParDrain<'_, K, V> { + type Item = (K, V); + + parallel_iterator_methods!(Bucket::key_value); +} + +impl IndexedParallelIterator for ParDrain<'_, K, V> { + indexed_parallel_iterator_methods!(Bucket::key_value); +} + +/// Parallel iterator methods and other parallel methods. +/// +/// The following methods **require crate feature `"rayon"`**. +/// +/// See also the `IntoParallelIterator` implementations. +impl IndexMap +where + K: Sync, + V: Sync, +{ + /// Return a parallel iterator over the keys of the map. + /// + /// While parallel iterators can process items in any order, their relative order + /// in the map is still preserved for operations like `reduce` and `collect`. + pub fn par_keys(&self) -> ParKeys<'_, K, V> { + ParKeys { + entries: self.as_entries(), + } + } + + /// Return a parallel iterator over the values of the map. + /// + /// While parallel iterators can process items in any order, their relative order + /// in the map is still preserved for operations like `reduce` and `collect`. + pub fn par_values(&self) -> ParValues<'_, K, V> { + ParValues { + entries: self.as_entries(), + } + } +} + +impl IndexMap +where + K: Hash + Eq + Sync, + V: Sync, + S: BuildHasher, +{ + /// Returns `true` if `self` contains all of the same key-value pairs as `other`, + /// regardless of each map's indexed order, determined in parallel. + pub fn par_eq(&self, other: &IndexMap) -> bool + where + V: PartialEq, + V2: Sync, + S2: BuildHasher + Sync, + { + self.len() == other.len() + && self + .par_iter() + .all(move |(key, value)| other.get(key).map_or(false, |v| *value == *v)) + } +} + +/// A parallel iterator over the keys of a `IndexMap`. +/// +/// This `struct` is created by the [`par_keys`] method on [`IndexMap`]. See its +/// documentation for more. +/// +/// [`par_keys`]: ../struct.IndexMap.html#method.par_keys +/// [`IndexMap`]: ../struct.IndexMap.html +pub struct ParKeys<'a, K, V> { + entries: &'a [Bucket], +} + +impl Clone for ParKeys<'_, K, V> { + fn clone(&self) -> Self { + ParKeys { ..*self } + } +} + +impl fmt::Debug for ParKeys<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.entries.iter().map(Bucket::key_ref); + f.debug_list().entries(iter).finish() + } +} + +impl<'a, K: Sync, V: Sync> ParallelIterator for ParKeys<'a, K, V> { + type Item = &'a K; + + parallel_iterator_methods!(Bucket::key_ref); +} + +impl IndexedParallelIterator for ParKeys<'_, K, V> { + indexed_parallel_iterator_methods!(Bucket::key_ref); +} + +/// A parallel iterator over the values of a `IndexMap`. +/// +/// This `struct` is created by the [`par_values`] method on [`IndexMap`]. See its +/// documentation for more. +/// +/// [`par_values`]: ../struct.IndexMap.html#method.par_values +/// [`IndexMap`]: ../struct.IndexMap.html +pub struct ParValues<'a, K, V> { + entries: &'a [Bucket], +} + +impl Clone for ParValues<'_, K, V> { + fn clone(&self) -> Self { + ParValues { ..*self } + } +} + +impl fmt::Debug for ParValues<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.entries.iter().map(Bucket::value_ref); + f.debug_list().entries(iter).finish() + } +} + +impl<'a, K: Sync, V: Sync> ParallelIterator for ParValues<'a, K, V> { + type Item = &'a V; + + parallel_iterator_methods!(Bucket::value_ref); +} + +impl IndexedParallelIterator for ParValues<'_, K, V> { + indexed_parallel_iterator_methods!(Bucket::value_ref); +} + +/// Requires crate feature `"rayon"`. +impl IndexMap +where + K: Send, + V: Send, +{ + /// Return a parallel iterator over mutable references to the values of the map + /// + /// While parallel iterators can process items in any order, their relative order + /// in the map is still preserved for operations like `reduce` and `collect`. + pub fn par_values_mut(&mut self) -> ParValuesMut<'_, K, V> { + ParValuesMut { + entries: self.as_entries_mut(), + } + } +} + +impl IndexMap +where + K: Hash + Eq + Send, + V: Send, + S: BuildHasher, +{ + /// Sort the map’s key-value pairs in parallel, by the default ordering of the keys. + pub fn par_sort_keys(&mut self) + where + K: Ord, + { + self.with_entries(|entries| { + entries.par_sort_by(|a, b| K::cmp(&a.key, &b.key)); + }); + } + + /// Sort the map’s key-value pairs in place and in parallel, using the comparison + /// function `cmp`. + /// + /// The comparison function receives two key and value pairs to compare (you + /// can sort by keys or values or their combination as needed). + pub fn par_sort_by(&mut self, cmp: F) + where + F: Fn(&K, &V, &K, &V) -> Ordering + Sync, + { + self.with_entries(|entries| { + entries.par_sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); + }); + } + + /// Sort the key-value pairs of the map in parallel and return a by-value parallel + /// iterator of the key-value pairs with the result. + pub fn par_sorted_by(self, cmp: F) -> IntoParIter + where + F: Fn(&K, &V, &K, &V) -> Ordering + Sync, + { + let mut entries = self.into_entries(); + entries.par_sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); + IntoParIter { entries } + } + + /// Sort the map's key-value pairs in parallel, by the default ordering of the keys. + pub fn par_sort_unstable_keys(&mut self) + where + K: Ord, + { + self.with_entries(|entries| { + entries.par_sort_unstable_by(|a, b| K::cmp(&a.key, &b.key)); + }); + } + + /// Sort the map's key-value pairs in place and in parallel, using the comparison + /// function `cmp`. + /// + /// The comparison function receives two key and value pairs to compare (you + /// can sort by keys or values or their combination as needed). + pub fn par_sort_unstable_by(&mut self, cmp: F) + where + F: Fn(&K, &V, &K, &V) -> Ordering + Sync, + { + self.with_entries(|entries| { + entries.par_sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); + }); + } + + /// Sort the key-value pairs of the map in parallel and return a by-value parallel + /// iterator of the key-value pairs with the result. + pub fn par_sorted_unstable_by(self, cmp: F) -> IntoParIter + where + F: Fn(&K, &V, &K, &V) -> Ordering + Sync, + { + let mut entries = self.into_entries(); + entries.par_sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); + IntoParIter { entries } + } +} + +/// A parallel mutable iterator over the values of a `IndexMap`. +/// +/// This `struct` is created by the [`par_values_mut`] method on [`IndexMap`]. See its +/// documentation for more. +/// +/// [`par_values_mut`]: ../struct.IndexMap.html#method.par_values_mut +/// [`IndexMap`]: ../struct.IndexMap.html +pub struct ParValuesMut<'a, K, V> { + entries: &'a mut [Bucket], +} + +impl fmt::Debug for ParValuesMut<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.entries.iter().map(Bucket::value_ref); + f.debug_list().entries(iter).finish() + } +} + +impl<'a, K: Send, V: Send> ParallelIterator for ParValuesMut<'a, K, V> { + type Item = &'a mut V; + + parallel_iterator_methods!(Bucket::value_mut); +} + +impl IndexedParallelIterator for ParValuesMut<'_, K, V> { + indexed_parallel_iterator_methods!(Bucket::value_mut); +} + +/// Requires crate feature `"rayon"`. +impl FromParallelIterator<(K, V)> for IndexMap +where + K: Eq + Hash + Send, + V: Send, + S: BuildHasher + Default + Send, +{ + fn from_par_iter(iter: I) -> Self + where + I: IntoParallelIterator, + { + let list = collect(iter); + let len = list.iter().map(Vec::len).sum(); + let mut map = Self::with_capacity_and_hasher(len, S::default()); + for vec in list { + map.extend(vec); + } + map + } +} + +/// Requires crate feature `"rayon"`. +impl ParallelExtend<(K, V)> for IndexMap +where + K: Eq + Hash + Send, + V: Send, + S: BuildHasher + Send, +{ + fn par_extend(&mut self, iter: I) + where + I: IntoParallelIterator, + { + for vec in collect(iter) { + self.extend(vec); + } + } +} + +/// Requires crate feature `"rayon"`. +impl<'a, K: 'a, V: 'a, S> ParallelExtend<(&'a K, &'a V)> for IndexMap +where + K: Copy + Eq + Hash + Send + Sync, + V: Copy + Send + Sync, + S: BuildHasher + Send, +{ + fn par_extend(&mut self, iter: I) + where + I: IntoParallelIterator, + { + for vec in collect(iter) { + self.extend(vec); + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + use std::string::String; + + #[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.par_keys().count(), map.len()); + assert_eq!(map.par_keys().count(), insert.len()); + insert.par_iter().zip(map.par_keys()).for_each(|(a, b)| { + assert_eq!(a, b); + }); + (0..insert.len()) + .into_par_iter() + .zip(map.par_keys()) + .for_each(|(i, k)| { + assert_eq!(map.get_index(i).unwrap().0, k); + }); + } + + #[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!(map_a.par_eq(&map_b)); + map_b.swap_remove(&1); + assert!(!map_a.par_eq(&map_b)); + map_b.insert(3, "3"); + assert!(!map_a.par_eq(&map_b)); + + let map_c: IndexMap<_, String> = + map_b.into_par_iter().map(|(k, v)| (k, v.into())).collect(); + assert!(!map_a.par_eq(&map_c)); + assert!(!map_c.par_eq(&map_a)); + } + + #[test] + fn extend() { + let mut map = IndexMap::new(); + map.par_extend(vec![(&1, &2), (&3, &4)]); + map.par_extend(vec![(5, 6)]); + assert_eq!( + map.into_par_iter().collect::>(), + vec![(1, 2), (3, 4), (5, 6)] + ); + } + + #[test] + fn keys() { + let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; + let map: IndexMap<_, _> = vec.into_par_iter().collect(); + let keys: Vec<_> = map.par_keys().copied().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_par_iter().collect(); + let values: Vec<_> = map.par_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_par_iter().collect(); + map.par_values_mut().for_each(|value| *value *= 2); + let values: Vec<_> = map.par_values().copied().collect(); + assert_eq!(values.len(), 3); + assert!(values.contains(&2)); + assert!(values.contains(&4)); + assert!(values.contains(&6)); + } +} diff --git a/third_party/rust/indexmap/src/rayon/mod.rs b/third_party/rust/indexmap/src/rayon/mod.rs new file mode 100644 index 0000000000..ebb1ac2d1e --- /dev/null +++ b/third_party/rust/indexmap/src/rayon/mod.rs @@ -0,0 +1,27 @@ +use rayon::prelude::*; + +use alloc::collections::LinkedList; + +use crate::vec::Vec; + +pub mod map; +pub mod set; + +// This form of intermediate collection is also how Rayon collects `HashMap`. +// Note that the order will also be preserved! +fn collect(iter: I) -> LinkedList> { + iter.into_par_iter() + .fold(Vec::new, |mut vec, elem| { + vec.push(elem); + vec + }) + .map(|vec| { + let mut list = LinkedList::new(); + list.push_back(vec); + list + }) + .reduce(LinkedList::new, |mut list1, mut list2| { + list1.append(&mut list2); + list1 + }) +} diff --git a/third_party/rust/indexmap/src/rayon/set.rs b/third_party/rust/indexmap/src/rayon/set.rs new file mode 100644 index 0000000000..6749dc0d7f --- /dev/null +++ b/third_party/rust/indexmap/src/rayon/set.rs @@ -0,0 +1,741 @@ +//! Parallel iterator types for `IndexSet` with [rayon](https://docs.rs/rayon/1.0/rayon). +//! +//! 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 core::cmp::Ordering; +use core::fmt; +use core::hash::{BuildHasher, Hash}; +use core::ops::RangeBounds; + +use crate::Entries; +use crate::IndexSet; + +type Bucket = crate::Bucket; + +/// Requires crate feature `"rayon"`. +impl IntoParallelIterator for IndexSet +where + T: Send, +{ + type Item = T; + type Iter = IntoParIter; + + 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`] +/// (provided by rayon's `IntoParallelIterator` trait). See its documentation for more. +/// +/// [`IndexSet`]: ../struct.IndexSet.html +/// [`into_par_iter`]: ../struct.IndexSet.html#method.into_par_iter +pub struct IntoParIter { + entries: Vec>, +} + +impl fmt::Debug for IntoParIter { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.entries.iter().map(Bucket::key_ref); + f.debug_list().entries(iter).finish() + } +} + +impl ParallelIterator for IntoParIter { + type Item = T; + + parallel_iterator_methods!(Bucket::key); +} + +impl IndexedParallelIterator for IntoParIter { + indexed_parallel_iterator_methods!(Bucket::key); +} + +/// Requires crate feature `"rayon"`. +impl<'a, T, S> IntoParallelIterator for &'a IndexSet +where + T: Sync, +{ + type Item = &'a T; + type Iter = ParIter<'a, T>; + + fn into_par_iter(self) -> Self::Iter { + ParIter { + entries: self.as_entries(), + } + } +} + +/// A parallel iterator over the items of a `IndexSet`. +/// +/// This `struct` is created by the [`par_iter`] method on [`IndexSet`] +/// (provided by rayon's `IntoParallelRefIterator` trait). See its documentation for more. +/// +/// [`IndexSet`]: ../struct.IndexSet.html +/// [`par_iter`]: ../struct.IndexSet.html#method.par_iter +pub struct ParIter<'a, T> { + entries: &'a [Bucket], +} + +impl Clone for ParIter<'_, T> { + fn clone(&self) -> Self { + ParIter { ..*self } + } +} + +impl fmt::Debug for ParIter<'_, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.entries.iter().map(Bucket::key_ref); + f.debug_list().entries(iter).finish() + } +} + +impl<'a, T: Sync> ParallelIterator for ParIter<'a, T> { + type Item = &'a T; + + parallel_iterator_methods!(Bucket::key_ref); +} + +impl IndexedParallelIterator for ParIter<'_, T> { + indexed_parallel_iterator_methods!(Bucket::key_ref); +} + +/// Requires crate feature `"rayon"`. +impl<'a, T, S> ParallelDrainRange for &'a mut IndexSet +where + T: Send, +{ + type Item = T; + type Iter = ParDrain<'a, T>; + + fn par_drain>(self, range: R) -> Self::Iter { + ParDrain { + entries: self.map.core.par_drain(range), + } + } +} + +/// A parallel draining iterator over the items of a `IndexSet`. +/// +/// This `struct` is created by the [`par_drain`] method on [`IndexSet`] +/// (provided by rayon's `ParallelDrainRange` trait). See its documentation for more. +/// +/// [`par_drain`]: ../struct.IndexSet.html#method.par_drain +/// [`IndexSet`]: ../struct.IndexSet.html +pub struct ParDrain<'a, T: Send> { + entries: rayon::vec::Drain<'a, Bucket>, +} + +impl ParallelIterator for ParDrain<'_, T> { + type Item = T; + + parallel_iterator_methods!(Bucket::key); +} + +impl IndexedParallelIterator for ParDrain<'_, T> { + indexed_parallel_iterator_methods!(Bucket::key); +} + +/// Parallel iterator methods and other parallel methods. +/// +/// The following methods **require crate feature `"rayon"`**. +/// +/// See also the `IntoParallelIterator` implementations. +impl IndexSet +where + T: Hash + Eq + Sync, + S: BuildHasher + Sync, +{ + /// Return a parallel iterator over the values that are in `self` but not `other`. + /// + /// While parallel iterators can process items in any order, their relative order + /// in the `self` set is still preserved for operations like `reduce` and `collect`. + pub fn par_difference<'a, S2>( + &'a self, + other: &'a IndexSet, + ) -> ParDifference<'a, T, S, S2> + where + S2: BuildHasher + Sync, + { + ParDifference { + set1: self, + set2: other, + } + } + + /// Return a parallel iterator over the values that are in `self` or `other`, + /// but not in both. + /// + /// While parallel iterators can process items in any order, their relative order + /// in the sets is still preserved for operations like `reduce` and `collect`. + /// Values from `self` are produced in their original order, followed by + /// values from `other` in their original order. + pub fn par_symmetric_difference<'a, S2>( + &'a self, + other: &'a IndexSet, + ) -> ParSymmetricDifference<'a, T, S, S2> + where + S2: BuildHasher + Sync, + { + ParSymmetricDifference { + set1: self, + set2: other, + } + } + + /// Return a parallel iterator over the values that are in both `self` and `other`. + /// + /// While parallel iterators can process items in any order, their relative order + /// in the `self` set is still preserved for operations like `reduce` and `collect`. + pub fn par_intersection<'a, S2>( + &'a self, + other: &'a IndexSet, + ) -> ParIntersection<'a, T, S, S2> + where + S2: BuildHasher + Sync, + { + ParIntersection { + set1: self, + set2: other, + } + } + + /// Return a parallel iterator over all values that are in `self` or `other`. + /// + /// While parallel iterators can process items in any order, their relative order + /// in the sets is still preserved for operations like `reduce` and `collect`. + /// Values from `self` are produced in their original order, followed by + /// values that are unique to `other` in their original order. + pub fn par_union<'a, S2>(&'a self, other: &'a IndexSet) -> ParUnion<'a, T, S, S2> + where + S2: BuildHasher + Sync, + { + ParUnion { + set1: self, + set2: other, + } + } + + /// Returns `true` if `self` contains all of the same values as `other`, + /// regardless of each set's indexed order, determined in parallel. + pub fn par_eq(&self, other: &IndexSet) -> bool + where + S2: BuildHasher + Sync, + { + self.len() == other.len() && self.par_is_subset(other) + } + + /// Returns `true` if `self` has no elements in common with `other`, + /// determined in parallel. + pub fn par_is_disjoint(&self, other: &IndexSet) -> bool + where + S2: BuildHasher + Sync, + { + if self.len() <= other.len() { + self.par_iter().all(move |value| !other.contains(value)) + } else { + other.par_iter().all(move |value| !self.contains(value)) + } + } + + /// Returns `true` if all elements of `other` are contained in `self`, + /// determined in parallel. + pub fn par_is_superset(&self, other: &IndexSet) -> bool + where + S2: BuildHasher + Sync, + { + other.par_is_subset(self) + } + + /// Returns `true` if all elements of `self` are contained in `other`, + /// determined in parallel. + pub fn par_is_subset(&self, other: &IndexSet) -> bool + where + S2: BuildHasher + Sync, + { + self.len() <= other.len() && self.par_iter().all(move |value| other.contains(value)) + } +} + +/// A parallel iterator producing elements in the difference of `IndexSet`s. +/// +/// This `struct` is created by the [`par_difference`] method on [`IndexSet`]. +/// See its documentation for more. +/// +/// [`IndexSet`]: ../struct.IndexSet.html +/// [`par_difference`]: ../struct.IndexSet.html#method.par_difference +pub struct ParDifference<'a, T, S1, S2> { + set1: &'a IndexSet, + set2: &'a IndexSet, +} + +impl Clone for ParDifference<'_, T, S1, S2> { + fn clone(&self) -> Self { + ParDifference { ..*self } + } +} + +impl fmt::Debug for ParDifference<'_, 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.set1.difference(self.set2)) + .finish() + } +} + +impl<'a, T, S1, S2> ParallelIterator for ParDifference<'a, T, S1, S2> +where + T: Hash + Eq + Sync, + S1: BuildHasher + Sync, + S2: BuildHasher + Sync, +{ + type Item = &'a T; + + fn drive_unindexed(self, consumer: C) -> C::Result + where + C: UnindexedConsumer, + { + let Self { set1, set2 } = self; + + set1.par_iter() + .filter(move |&item| !set2.contains(item)) + .drive_unindexed(consumer) + } +} + +/// A parallel iterator producing elements in the intersection of `IndexSet`s. +/// +/// This `struct` is created by the [`par_intersection`] method on [`IndexSet`]. +/// See its documentation for more. +/// +/// [`IndexSet`]: ../struct.IndexSet.html +/// [`par_intersection`]: ../struct.IndexSet.html#method.par_intersection +pub struct ParIntersection<'a, T, S1, S2> { + set1: &'a IndexSet, + set2: &'a IndexSet, +} + +impl Clone for ParIntersection<'_, T, S1, S2> { + fn clone(&self) -> Self { + ParIntersection { ..*self } + } +} + +impl fmt::Debug for ParIntersection<'_, 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.set1.intersection(self.set2)) + .finish() + } +} + +impl<'a, T, S1, S2> ParallelIterator for ParIntersection<'a, T, S1, S2> +where + T: Hash + Eq + Sync, + S1: BuildHasher + Sync, + S2: BuildHasher + Sync, +{ + type Item = &'a T; + + fn drive_unindexed(self, consumer: C) -> C::Result + where + C: UnindexedConsumer, + { + let Self { set1, set2 } = self; + + set1.par_iter() + .filter(move |&item| set2.contains(item)) + .drive_unindexed(consumer) + } +} + +/// A parallel iterator producing elements in the symmetric difference of `IndexSet`s. +/// +/// This `struct` is created by the [`par_symmetric_difference`] method on +/// [`IndexSet`]. See its documentation for more. +/// +/// [`IndexSet`]: ../struct.IndexSet.html +/// [`par_symmetric_difference`]: ../struct.IndexSet.html#method.par_symmetric_difference +pub struct ParSymmetricDifference<'a, T, S1, S2> { + set1: &'a IndexSet, + set2: &'a IndexSet, +} + +impl Clone for ParSymmetricDifference<'_, T, S1, S2> { + fn clone(&self) -> Self { + ParSymmetricDifference { ..*self } + } +} + +impl fmt::Debug for ParSymmetricDifference<'_, 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.set1.symmetric_difference(self.set2)) + .finish() + } +} + +impl<'a, T, S1, S2> ParallelIterator for ParSymmetricDifference<'a, T, S1, S2> +where + T: Hash + Eq + Sync, + S1: BuildHasher + Sync, + S2: BuildHasher + Sync, +{ + type Item = &'a T; + + fn drive_unindexed(self, consumer: C) -> C::Result + where + C: UnindexedConsumer, + { + let Self { set1, set2 } = self; + + set1.par_difference(set2) + .chain(set2.par_difference(set1)) + .drive_unindexed(consumer) + } +} + +/// A parallel iterator producing elements in the union of `IndexSet`s. +/// +/// This `struct` is created by the [`par_union`] method on [`IndexSet`]. +/// See its documentation for more. +/// +/// [`IndexSet`]: ../struct.IndexSet.html +/// [`par_union`]: ../struct.IndexSet.html#method.par_union +pub struct ParUnion<'a, T, S1, S2> { + set1: &'a IndexSet, + set2: &'a IndexSet, +} + +impl Clone for ParUnion<'_, T, S1, S2> { + fn clone(&self) -> Self { + ParUnion { ..*self } + } +} + +impl fmt::Debug for ParUnion<'_, 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.set1.union(self.set2)).finish() + } +} + +impl<'a, T, S1, S2> ParallelIterator for ParUnion<'a, T, S1, S2> +where + T: Hash + Eq + Sync, + S1: BuildHasher + Sync, + S2: BuildHasher + Sync, +{ + type Item = &'a T; + + fn drive_unindexed(self, consumer: C) -> C::Result + where + C: UnindexedConsumer, + { + let Self { set1, set2 } = self; + + set1.par_iter() + .chain(set2.par_difference(set1)) + .drive_unindexed(consumer) + } +} + +/// Parallel sorting methods. +/// +/// The following methods **require crate feature `"rayon"`**. +impl IndexSet +where + T: Hash + Eq + Send, + S: BuildHasher + Send, +{ + /// Sort the set’s values in parallel by their default ordering. + pub fn par_sort(&mut self) + where + T: Ord, + { + self.with_entries(|entries| { + entries.par_sort_by(|a, b| T::cmp(&a.key, &b.key)); + }); + } + + /// Sort the set’s values in place and in parallel, using the comparison function `cmp`. + pub fn par_sort_by(&mut self, cmp: F) + where + F: Fn(&T, &T) -> Ordering + Sync, + { + self.with_entries(|entries| { + entries.par_sort_by(move |a, b| cmp(&a.key, &b.key)); + }); + } + + /// Sort the values of the set in parallel and return a by-value parallel iterator of + /// the values with the result. + pub fn par_sorted_by(self, cmp: F) -> IntoParIter + where + F: Fn(&T, &T) -> Ordering + Sync, + { + let mut entries = self.into_entries(); + entries.par_sort_by(move |a, b| cmp(&a.key, &b.key)); + IntoParIter { entries } + } + + /// Sort the set's values in parallel by their default ordering. + pub fn par_sort_unstable(&mut self) + where + T: Ord, + { + self.with_entries(|entries| { + entries.par_sort_unstable_by(|a, b| T::cmp(&a.key, &b.key)); + }); + } + + /// Sort the set’s values in place and in parallel, using the comparison function `cmp`. + pub fn par_sort_unstable_by(&mut self, cmp: F) + where + F: Fn(&T, &T) -> Ordering + Sync, + { + self.with_entries(|entries| { + entries.par_sort_unstable_by(move |a, b| cmp(&a.key, &b.key)); + }); + } + + /// Sort the values of the set in parallel and return a by-value parallel iterator of + /// the values with the result. + pub fn par_sorted_unstable_by(self, cmp: F) -> IntoParIter + where + F: Fn(&T, &T) -> Ordering + Sync, + { + let mut entries = self.into_entries(); + entries.par_sort_unstable_by(move |a, b| cmp(&a.key, &b.key)); + IntoParIter { entries } + } +} + +/// Requires crate feature `"rayon"`. +impl FromParallelIterator for IndexSet +where + T: Eq + Hash + Send, + S: BuildHasher + Default + Send, +{ + fn from_par_iter(iter: I) -> Self + where + I: IntoParallelIterator, + { + let list = collect(iter); + let len = list.iter().map(Vec::len).sum(); + let mut set = Self::with_capacity_and_hasher(len, S::default()); + for vec in list { + set.extend(vec); + } + set + } +} + +/// Requires crate feature `"rayon"`. +impl ParallelExtend for IndexSet +where + T: Eq + Hash + Send, + S: BuildHasher + Send, +{ + fn par_extend(&mut self, iter: I) + where + I: IntoParallelIterator, + { + for vec in collect(iter) { + self.extend(vec); + } + } +} + +/// Requires crate feature `"rayon"`. +impl<'a, T: 'a, S> ParallelExtend<&'a T> for IndexSet +where + T: Copy + Eq + Hash + Send + Sync, + S: BuildHasher + Send, +{ + fn par_extend(&mut self, iter: I) + where + I: IntoParallelIterator, + { + for vec in collect(iter) { + self.extend(vec); + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[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.par_iter().count(), set.len()); + assert_eq!(set.par_iter().count(), insert.len()); + insert.par_iter().zip(&set).for_each(|(a, b)| { + assert_eq!(a, b); + }); + (0..insert.len()) + .into_par_iter() + .zip(&set) + .for_each(|(i, v)| { + assert_eq!(set.get_index(i).unwrap(), v); + }); + } + + #[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!(set_a.par_eq(&set_b)); + set_b.swap_remove(&1); + assert!(!set_a.par_eq(&set_b)); + set_b.insert(3); + assert!(!set_a.par_eq(&set_b)); + + let set_c: IndexSet<_> = set_b.into_par_iter().collect(); + assert!(!set_a.par_eq(&set_c)); + assert!(!set_c.par_eq(&set_a)); + } + + #[test] + fn extend() { + let mut set = IndexSet::new(); + set.par_extend(vec![&1, &2, &3, &4]); + set.par_extend(vec![5, 6]); + assert_eq!( + set.into_par_iter().collect::>(), + 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.par_is_disjoint(&set_a)); + assert!(set_a.par_is_subset(&set_a)); + assert!(set_a.par_is_superset(&set_a)); + + assert!(set_a.par_is_disjoint(&set_b)); + assert!(set_b.par_is_disjoint(&set_a)); + assert!(!set_a.par_is_subset(&set_b)); + assert!(!set_b.par_is_subset(&set_a)); + assert!(!set_a.par_is_superset(&set_b)); + assert!(!set_b.par_is_superset(&set_a)); + + assert!(!set_a.par_is_disjoint(&set_c)); + assert!(!set_c.par_is_disjoint(&set_a)); + assert!(set_a.par_is_subset(&set_c)); + assert!(!set_c.par_is_subset(&set_a)); + assert!(!set_a.par_is_superset(&set_c)); + assert!(set_c.par_is_superset(&set_a)); + + assert!(!set_c.par_is_disjoint(&set_d)); + assert!(!set_d.par_is_disjoint(&set_c)); + assert!(!set_c.par_is_subset(&set_d)); + assert!(!set_d.par_is_subset(&set_c)); + assert!(!set_c.par_is_superset(&set_d)); + assert!(!set_d.par_is_superset(&set_c)); + } + + #[test] + fn iter_comparisons() { + use std::iter::empty; + + fn check<'a, I1, I2>(iter1: I1, iter2: I2) + where + I1: ParallelIterator, + I2: Iterator, + { + let v1: Vec<_> = iter1.copied().collect(); + let v2: Vec<_> = iter2.collect(); + assert_eq!(v1, v2); + } + + 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.par_difference(&set_a), empty()); + check(set_a.par_symmetric_difference(&set_a), empty()); + check(set_a.par_intersection(&set_a), 0..3); + check(set_a.par_union(&set_a), 0..3); + + check(set_a.par_difference(&set_b), 0..3); + check(set_b.par_difference(&set_a), 3..6); + check(set_a.par_symmetric_difference(&set_b), 0..6); + check(set_b.par_symmetric_difference(&set_a), (3..6).chain(0..3)); + check(set_a.par_intersection(&set_b), empty()); + check(set_b.par_intersection(&set_a), empty()); + check(set_a.par_union(&set_b), 0..6); + check(set_b.par_union(&set_a), (3..6).chain(0..3)); + + check(set_a.par_difference(&set_c), empty()); + check(set_c.par_difference(&set_a), 3..6); + check(set_a.par_symmetric_difference(&set_c), 3..6); + check(set_c.par_symmetric_difference(&set_a), 3..6); + check(set_a.par_intersection(&set_c), 0..3); + check(set_c.par_intersection(&set_a), 0..3); + check(set_a.par_union(&set_c), 0..6); + check(set_c.par_union(&set_a), 0..6); + + check(set_c.par_difference(&set_d), 0..3); + check(set_d.par_difference(&set_c), (6..9).rev()); + check( + set_c.par_symmetric_difference(&set_d), + (0..3).chain((6..9).rev()), + ); + check( + set_d.par_symmetric_difference(&set_c), + (6..9).rev().chain(0..3), + ); + check(set_c.par_intersection(&set_d), 3..6); + check(set_d.par_intersection(&set_c), (3..6).rev()); + check(set_c.par_union(&set_d), (0..6).chain((6..9).rev())); + check(set_d.par_union(&set_c), (3..9).rev().chain(0..3)); + } +} diff --git a/third_party/rust/indexmap/src/rustc.rs b/third_party/rust/indexmap/src/rustc.rs new file mode 100644 index 0000000000..b843858b32 --- /dev/null +++ b/third_party/rust/indexmap/src/rustc.rs @@ -0,0 +1,158 @@ +//! Minimal support for `rustc-rayon`, not intended for general use. + +use crate::vec::Vec; +use crate::{Bucket, Entries, IndexMap, IndexSet}; + +use rustc_rayon::iter::plumbing::{Consumer, ProducerCallback, UnindexedConsumer}; +use rustc_rayon::iter::{IndexedParallelIterator, IntoParallelIterator, ParallelIterator}; + +mod map { + use super::*; + + impl IntoParallelIterator for IndexMap + where + K: Send, + V: Send, + { + type Item = (K, V); + type Iter = IntoParIter; + + fn into_par_iter(self) -> Self::Iter { + IntoParIter { + entries: self.into_entries(), + } + } + } + + pub struct IntoParIter { + entries: Vec>, + } + + impl ParallelIterator for IntoParIter { + type Item = (K, V); + + parallel_iterator_methods!(Bucket::key_value); + } + + impl IndexedParallelIterator for IntoParIter { + indexed_parallel_iterator_methods!(Bucket::key_value); + } + + impl<'a, K, V, S> IntoParallelIterator for &'a IndexMap + 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.as_entries(), + } + } + } + + pub struct ParIter<'a, K, V> { + entries: &'a [Bucket], + } + + impl<'a, K: Sync, V: Sync> ParallelIterator for ParIter<'a, K, V> { + type Item = (&'a K, &'a V); + + parallel_iterator_methods!(Bucket::refs); + } + + impl IndexedParallelIterator for ParIter<'_, K, V> { + indexed_parallel_iterator_methods!(Bucket::refs); + } + + impl<'a, K, V, S> IntoParallelIterator for &'a mut IndexMap + 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: self.as_entries_mut(), + } + } + } + + pub struct ParIterMut<'a, K, V> { + entries: &'a mut [Bucket], + } + + impl<'a, K: Sync + Send, V: Send> ParallelIterator for ParIterMut<'a, K, V> { + type Item = (&'a K, &'a mut V); + + parallel_iterator_methods!(Bucket::ref_mut); + } + + impl IndexedParallelIterator for ParIterMut<'_, K, V> { + indexed_parallel_iterator_methods!(Bucket::ref_mut); + } +} + +mod set { + use super::*; + + impl IntoParallelIterator for IndexSet + where + T: Send, + { + type Item = T; + type Iter = IntoParIter; + + fn into_par_iter(self) -> Self::Iter { + IntoParIter { + entries: self.into_entries(), + } + } + } + + pub struct IntoParIter { + entries: Vec>, + } + + impl ParallelIterator for IntoParIter { + type Item = T; + + parallel_iterator_methods!(Bucket::key); + } + + impl IndexedParallelIterator for IntoParIter { + indexed_parallel_iterator_methods!(Bucket::key); + } + + impl<'a, T, S> IntoParallelIterator for &'a IndexSet + where + T: Sync, + { + type Item = &'a T; + type Iter = ParIter<'a, T>; + + fn into_par_iter(self) -> Self::Iter { + ParIter { + entries: self.as_entries(), + } + } + } + + pub struct ParIter<'a, T> { + entries: &'a [Bucket], + } + + impl<'a, T: Sync> ParallelIterator for ParIter<'a, T> { + type Item = &'a T; + + parallel_iterator_methods!(Bucket::key_ref); + } + + impl IndexedParallelIterator for ParIter<'_, T> { + indexed_parallel_iterator_methods!(Bucket::key_ref); + } +} diff --git a/third_party/rust/indexmap/src/serde.rs b/third_party/rust/indexmap/src/serde.rs new file mode 100644 index 0000000000..c6dd6d5ea0 --- /dev/null +++ b/third_party/rust/indexmap/src/serde.rs @@ -0,0 +1,155 @@ +use serde::de::value::{MapDeserializer, SeqDeserializer}; +use serde::de::{ + Deserialize, Deserializer, Error, IntoDeserializer, MapAccess, SeqAccess, Visitor, +}; +use serde::ser::{Serialize, Serializer}; + +use core::fmt::{self, Formatter}; +use core::hash::{BuildHasher, Hash}; +use core::marker::PhantomData; + +use crate::IndexMap; + +/// Requires crate feature `"serde"` or `"serde-1"` +impl Serialize for IndexMap +where + K: Serialize + Hash + Eq, + V: Serialize, + S: BuildHasher, +{ + fn serialize(&self, serializer: T) -> Result + where + T: Serializer, + { + serializer.collect_map(self) + } +} + +struct IndexMapVisitor(PhantomData<(K, V, S)>); + +impl<'de, K, V, S> Visitor<'de> for IndexMapVisitor +where + K: Deserialize<'de> + Eq + Hash, + V: Deserialize<'de>, + S: Default + BuildHasher, +{ + type Value = IndexMap; + + fn expecting(&self, formatter: &mut Formatter<'_>) -> fmt::Result { + write!(formatter, "a map") + } + + fn visit_map(self, mut map: A) -> Result + where + A: MapAccess<'de>, + { + let mut values = + IndexMap::with_capacity_and_hasher(map.size_hint().unwrap_or(0), S::default()); + + while let Some((key, value)) = map.next_entry()? { + values.insert(key, value); + } + + Ok(values) + } +} + +/// Requires crate feature `"serde"` or `"serde-1"` +impl<'de, K, V, S> Deserialize<'de> for IndexMap +where + K: Deserialize<'de> + Eq + Hash, + V: Deserialize<'de>, + S: Default + BuildHasher, +{ + fn deserialize(deserializer: D) -> Result + where + D: Deserializer<'de>, + { + deserializer.deserialize_map(IndexMapVisitor(PhantomData)) + } +} + +impl<'de, K, V, S, E> IntoDeserializer<'de, E> for IndexMap +where + K: IntoDeserializer<'de, E> + Eq + Hash, + V: IntoDeserializer<'de, E>, + S: BuildHasher, + E: Error, +{ + type Deserializer = MapDeserializer<'de, ::IntoIter, E>; + + fn into_deserializer(self) -> Self::Deserializer { + MapDeserializer::new(self.into_iter()) + } +} + +use crate::IndexSet; + +/// Requires crate feature `"serde"` or `"serde-1"` +impl Serialize for IndexSet +where + T: Serialize + Hash + Eq, + S: BuildHasher, +{ + fn serialize(&self, serializer: Se) -> Result + where + Se: Serializer, + { + serializer.collect_seq(self) + } +} + +struct IndexSetVisitor(PhantomData<(T, S)>); + +impl<'de, T, S> Visitor<'de> for IndexSetVisitor +where + T: Deserialize<'de> + Eq + Hash, + S: Default + BuildHasher, +{ + type Value = IndexSet; + + fn expecting(&self, formatter: &mut Formatter<'_>) -> fmt::Result { + write!(formatter, "a set") + } + + fn visit_seq(self, mut seq: A) -> Result + where + A: SeqAccess<'de>, + { + let mut values = + IndexSet::with_capacity_and_hasher(seq.size_hint().unwrap_or(0), S::default()); + + while let Some(value) = seq.next_element()? { + values.insert(value); + } + + Ok(values) + } +} + +/// Requires crate feature `"serde"` or `"serde-1"` +impl<'de, T, S> Deserialize<'de> for IndexSet +where + T: Deserialize<'de> + Eq + Hash, + S: Default + BuildHasher, +{ + fn deserialize(deserializer: D) -> Result + where + D: Deserializer<'de>, + { + deserializer.deserialize_seq(IndexSetVisitor(PhantomData)) + } +} + +impl<'de, T, S, E> IntoDeserializer<'de, E> for IndexSet +where + T: IntoDeserializer<'de, E> + Eq + Hash, + S: BuildHasher, + E: Error, +{ + type Deserializer = SeqDeserializer<::IntoIter, E>; + + fn into_deserializer(self) -> Self::Deserializer { + SeqDeserializer::new(self.into_iter()) + } +} diff --git a/third_party/rust/indexmap/src/serde_seq.rs b/third_party/rust/indexmap/src/serde_seq.rs new file mode 100644 index 0000000000..d326a02e37 --- /dev/null +++ b/third_party/rust/indexmap/src/serde_seq.rs @@ -0,0 +1,112 @@ +//! Functions to serialize and deserialize an `IndexMap` as an ordered sequence. +//! +//! The default `serde` implementation serializes `IndexMap` as a normal map, +//! but there is no guarantee that serialization formats will preserve the order +//! of the key-value pairs. This module serializes `IndexMap` as a sequence of +//! `(key, value)` elements instead, in order. +//! +//! This module may be used in a field attribute for derived implementations: +//! +//! ``` +//! # use indexmap::IndexMap; +//! # use serde_derive::{Deserialize, Serialize}; +//! #[derive(Deserialize, Serialize)] +//! struct Data { +//! #[serde(with = "indexmap::serde_seq")] +//! map: IndexMap, +//! // ... +//! } +//! ``` +//! +//! Requires crate feature `"serde"` or `"serde-1"` + +use serde::de::{Deserialize, Deserializer, SeqAccess, Visitor}; +use serde::ser::{Serialize, Serializer}; + +use core::fmt::{self, Formatter}; +use core::hash::{BuildHasher, Hash}; +use core::marker::PhantomData; + +use crate::IndexMap; + +/// Serializes an `IndexMap` as an ordered sequence. +/// +/// This function may be used in a field attribute for deriving `Serialize`: +/// +/// ``` +/// # use indexmap::IndexMap; +/// # use serde_derive::Serialize; +/// #[derive(Serialize)] +/// struct Data { +/// #[serde(serialize_with = "indexmap::serde_seq::serialize")] +/// map: IndexMap, +/// // ... +/// } +/// ``` +/// +/// Requires crate feature `"serde"` or `"serde-1"` +pub fn serialize(map: &IndexMap, serializer: T) -> Result +where + K: Serialize + Hash + Eq, + V: Serialize, + S: BuildHasher, + T: Serializer, +{ + serializer.collect_seq(map) +} + +/// Visitor to deserialize a *sequenced* `IndexMap` +struct SeqVisitor(PhantomData<(K, V, S)>); + +impl<'de, K, V, S> Visitor<'de> for SeqVisitor +where + K: Deserialize<'de> + Eq + Hash, + V: Deserialize<'de>, + S: Default + BuildHasher, +{ + type Value = IndexMap; + + fn expecting(&self, formatter: &mut Formatter<'_>) -> fmt::Result { + write!(formatter, "a sequenced map") + } + + fn visit_seq(self, mut seq: A) -> Result + where + A: SeqAccess<'de>, + { + let capacity = seq.size_hint().unwrap_or(0); + let mut map = IndexMap::with_capacity_and_hasher(capacity, S::default()); + + while let Some((key, value)) = seq.next_element()? { + map.insert(key, value); + } + + Ok(map) + } +} + +/// Deserializes an `IndexMap` from an ordered sequence. +/// +/// This function may be used in a field attribute for deriving `Deserialize`: +/// +/// ``` +/// # use indexmap::IndexMap; +/// # use serde_derive::Deserialize; +/// #[derive(Deserialize)] +/// struct Data { +/// #[serde(deserialize_with = "indexmap::serde_seq::deserialize")] +/// map: IndexMap, +/// // ... +/// } +/// ``` +/// +/// Requires crate feature `"serde"` or `"serde-1"` +pub fn deserialize<'de, D, K, V, S>(deserializer: D) -> Result, D::Error> +where + D: Deserializer<'de>, + K: Deserialize<'de> + Eq + Hash, + V: Deserialize<'de>, + S: Default + BuildHasher, +{ + deserializer.deserialize_seq(SeqVisitor(PhantomData)) +} diff --git a/third_party/rust/indexmap/src/set.rs b/third_party/rust/indexmap/src/set.rs new file mode 100644 index 0000000000..3728947426 --- /dev/null +++ b/third_party/rust/indexmap/src/set.rs @@ -0,0 +1,1912 @@ +//! A hash set implemented using `IndexMap` + +#[cfg(feature = "rayon")] +pub use crate::rayon::set as rayon; + +#[cfg(has_std)] +use std::collections::hash_map::RandomState; + +use crate::vec::{self, 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}; + +type Bucket = super::Bucket; + +/// A hash set where the iteration order of the values is independent of their +/// hash values. +/// +/// The interface is closely compatible with the standard `HashSet`, but also +/// has additional features. +/// +/// # Order +/// +/// The values have a consistent order that is determined by the sequence of +/// insertion and removal calls on the set. The order does not depend on the +/// values or the hash function at all. Note that insertion order and value +/// are not affected if a re-insertion is attempted once an element is +/// already present. +/// +/// All iterators traverse the set *in order*. Set operation iterators like +/// `union` produce a concatenated order, as do their matching "bitwise" +/// operators. See their documentation for specifics. +/// +/// The insertion order is preserved, with **notable exceptions** like the +/// `.remove()` or `.swap_remove()` methods. Methods such as `.sort_by()` of +/// course result in a new order, depending on the sorting order. +/// +/// # Indices +/// +/// The values are indexed in a compact range without holes in the range +/// `0..self.len()`. For example, the method `.get_full` looks up the index for +/// a value, and the method `.get_index` looks up the value by index. +/// +/// # Examples +/// +/// ``` +/// use indexmap::IndexSet; +/// +/// // Collects which letters appear in a sentence. +/// let letters: IndexSet<_> = "a short treatise on fungi".chars().collect(); +/// +/// assert!(letters.contains(&'s')); +/// assert!(letters.contains(&'t')); +/// assert!(letters.contains(&'u')); +/// assert!(!letters.contains(&'y')); +/// ``` +#[cfg(has_std)] +pub struct IndexSet { + pub(crate) map: IndexMap, +} +#[cfg(not(has_std))] +pub struct IndexSet { + pub(crate) map: IndexMap, +} + +impl Clone for IndexSet +where + T: Clone, + S: Clone, +{ + fn clone(&self) -> Self { + IndexSet { + map: self.map.clone(), + } + } + + fn clone_from(&mut self, other: &Self) { + self.map.clone_from(&other.map); + } +} + +impl Entries for IndexSet { + type Entry = Bucket; + + #[inline] + fn into_entries(self) -> Vec { + self.map.into_entries() + } + + #[inline] + fn as_entries(&self) -> &[Self::Entry] { + self.map.as_entries() + } + + #[inline] + fn as_entries_mut(&mut self) -> &mut [Self::Entry] { + self.map.as_entries_mut() + } + + fn with_entries(&mut self, f: F) + where + F: FnOnce(&mut [Self::Entry]), + { + self.map.with_entries(f); + } +} + +impl fmt::Debug for IndexSet +where + T: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + if cfg!(not(feature = "test_debug")) { + f.debug_set().entries(self.iter()).finish() + } else { + // Let the inner `IndexMap` print all of its details + f.debug_struct("IndexSet").field("map", &self.map).finish() + } + } +} + +#[cfg(has_std)] +impl IndexSet { + /// Create a new set. (Does not allocate.) + pub fn new() -> Self { + IndexSet { + map: IndexMap::new(), + } + } + + /// Create a new set with capacity for `n` elements. + /// (Does not allocate if `n` is zero.) + /// + /// Computes in **O(n)** time. + pub fn with_capacity(n: usize) -> Self { + IndexSet { + map: IndexMap::with_capacity(n), + } + } +} + +impl IndexSet { + /// Create a new set with capacity for `n` elements. + /// (Does not allocate if `n` is zero.) + /// + /// Computes in **O(n)** time. + pub fn with_capacity_and_hasher(n: usize, hash_builder: S) -> Self { + IndexSet { + map: IndexMap::with_capacity_and_hasher(n, hash_builder), + } + } + + /// Create a new set with `hash_builder`. + /// + /// This function is `const`, so it + /// can be called in `static` contexts. + pub const fn with_hasher(hash_builder: S) -> Self { + IndexSet { + map: IndexMap::with_hasher(hash_builder), + } + } + + /// Computes in **O(1)** time. + pub fn capacity(&self) -> usize { + self.map.capacity() + } + + /// Return a reference to the set's `BuildHasher`. + pub fn hasher(&self) -> &S { + self.map.hasher() + } + + /// Return the number of elements in the set. + /// + /// Computes in **O(1)** time. + pub fn len(&self) -> usize { + self.map.len() + } + + /// Returns true if the set contains no elements. + /// + /// Computes in **O(1)** time. + pub fn is_empty(&self) -> bool { + self.map.is_empty() + } + + /// 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(), + } + } + + /// Remove all elements in the set, while preserving its capacity. + /// + /// Computes in **O(n)** time. + pub fn clear(&mut self) { + self.map.clear(); + } + + /// Shortens the set, keeping the first `len` elements and dropping the rest. + /// + /// If `len` is greater than the set's current length, this has no effect. + pub fn truncate(&mut self, len: usize) { + self.map.truncate(len); + } + + /// Clears the `IndexSet` in the given index range, returning those values + /// as a drain iterator. + /// + /// The range may be any type that implements `RangeBounds`, + /// including all of the `std::ops::Range*` types, or even a tuple pair of + /// `Bound` start and end values. To drain the set entirely, use `RangeFull` + /// like `set.drain(..)`. + /// + /// This shifts down all entries following the drained range to fill the + /// gap, and keeps the allocated memory for reuse. + /// + /// ***Panics*** if the starting point is greater than the end point or if + /// the end point is greater than the length of the set. + pub fn drain(&mut self, range: R) -> Drain<'_, T> + where + R: RangeBounds, + { + Drain { + iter: self.map.drain(range).iter, + } + } + + /// Splits the collection into two at the given index. + /// + /// Returns a newly allocated set containing the elements in the range + /// `[at, len)`. After the call, the original set will be left containing + /// the elements `[0, at)` with its previous capacity unchanged. + /// + /// ***Panics*** if `at > len`. + pub fn split_off(&mut self, at: usize) -> Self + where + S: Clone, + { + Self { + map: self.map.split_off(at), + } + } +} + +impl IndexSet +where + T: Hash + Eq, + S: BuildHasher, +{ + /// Reserve capacity for `additional` more values. + /// + /// Computes in **O(n)** time. + pub fn reserve(&mut self, additional: usize) { + self.map.reserve(additional); + } + + /// Shrink the capacity of the set as much as possible. + /// + /// Computes in **O(n)** time. + pub fn shrink_to_fit(&mut self) { + self.map.shrink_to_fit(); + } + + /// Shrink the capacity of the set with a lower limit. + /// + /// Computes in **O(n)** time. + pub fn shrink_to(&mut self, min_capacity: usize) { + self.map.shrink_to(min_capacity); + } + + /// Insert the value into the set. + /// + /// If an equivalent item already exists in the set, it returns + /// `false` leaving the original value in the set and without + /// altering its insertion order. Otherwise, it inserts the new + /// item and returns `true`. + /// + /// Computes in **O(1)** time (amortized average). + pub fn insert(&mut self, value: T) -> bool { + self.map.insert(value, ()).is_none() + } + + /// Insert the value into the set, and get its index. + /// + /// If an equivalent item already exists in the set, it returns + /// the index of the existing item and `false`, leaving the + /// original value in the set and without altering its insertion + /// order. Otherwise, it inserts the new item and returns the index + /// of the inserted item and `true`. + /// + /// 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) + } + } + } + + /// Return an iterator over the values that are in `self` but not `other`. + /// + /// Values are produced in the same order that they appear in `self`. + pub fn difference<'a, S2>(&'a self, other: &'a IndexSet) -> Difference<'a, T, S2> + where + S2: BuildHasher, + { + Difference { + iter: self.iter(), + other, + } + } + + /// Return an iterator over the values that are in `self` or `other`, + /// but not in both. + /// + /// Values from `self` are produced in their original order, followed by + /// values from `other` in their original order. + pub fn symmetric_difference<'a, S2>( + &'a self, + other: &'a IndexSet, + ) -> SymmetricDifference<'a, T, S, S2> + where + S2: BuildHasher, + { + SymmetricDifference { + iter: self.difference(other).chain(other.difference(self)), + } + } + + /// Return an iterator over the values that are in both `self` and `other`. + /// + /// Values are produced in the same order that they appear in `self`. + pub fn intersection<'a, S2>(&'a self, other: &'a IndexSet) -> Intersection<'a, T, S2> + where + S2: BuildHasher, + { + Intersection { + iter: self.iter(), + other, + } + } + + /// Return an iterator over all values that are in `self` or `other`. + /// + /// Values from `self` are produced in their original order, followed by + /// values that are unique to `other` in their original order. + pub fn union<'a, S2>(&'a self, other: &'a IndexSet) -> Union<'a, T, S> + where + S2: BuildHasher, + { + Union { + iter: self.iter().chain(other.difference(self)), + } + } + + /// Return `true` if an equivalent to `value` exists in the set. + /// + /// Computes in **O(1)** time (average). + pub fn contains(&self, value: &Q) -> bool + where + Q: Hash + Equivalent, + { + self.map.contains_key(value) + } + + /// Return a reference to the value stored in the set, if it is present, + /// else `None`. + /// + /// Computes in **O(1)** time (average). + pub fn get(&self, value: &Q) -> Option<&T> + where + Q: Hash + Equivalent, + { + self.map.get_key_value(value).map(|(x, &())| x) + } + + /// Return item index and value + pub fn get_full(&self, value: &Q) -> Option<(usize, &T)> + where + Q: Hash + Equivalent, + { + self.map.get_full(value).map(|(i, x, &())| (i, x)) + } + + /// Return item index, if it exists in the set + pub fn get_index_of(&self, value: &Q) -> Option + where + Q: Hash + Equivalent, + { + self.map.get_index_of(value) + } + + /// Adds a value to the set, replacing the existing value, if any, that is + /// equal to the given one, without altering its insertion order. Returns + /// the replaced value. + /// + /// Computes in **O(1)** time (average). + pub fn replace(&mut self, value: T) -> Option { + self.replace_full(value).1 + } + + /// Adds a value to the set, replacing the existing value, if any, that is + /// equal to the given one, without altering its insertion order. Returns + /// the index of the item and its replaced value. + /// + /// Computes in **O(1)** time (average). + pub fn replace_full(&mut self, value: T) -> (usize, Option) { + use super::map::Entry::*; + + match self.map.entry(value) { + Vacant(e) => { + let index = e.index(); + e.insert(()); + (index, None) + } + Occupied(e) => (e.index(), Some(e.replace_key())), + } + } + + /// Remove the value from the set, and return `true` if it was present. + /// + /// **NOTE:** This is equivalent to `.swap_remove(value)`, if you want + /// to preserve the order of the values in the set, use `.shift_remove(value)`. + /// + /// Computes in **O(1)** time (average). + pub fn remove(&mut self, value: &Q) -> bool + where + Q: Hash + Equivalent, + { + self.swap_remove(value) + } + + /// Remove the value from the set, and return `true` if it was present. + /// + /// Like `Vec::swap_remove`, the value is removed by swapping it with the + /// last element of the set and popping it off. **This perturbs + /// the position of what used to be the last element!** + /// + /// Return `false` if `value` was not in the set. + /// + /// Computes in **O(1)** time (average). + pub fn swap_remove(&mut self, value: &Q) -> bool + where + Q: Hash + Equivalent, + { + self.map.swap_remove(value).is_some() + } + + /// Remove the value from the set, and return `true` if it was present. + /// + /// Like `Vec::remove`, the value is removed by shifting all of the + /// elements that follow it, preserving their relative order. + /// **This perturbs the index of all of those elements!** + /// + /// Return `false` if `value` was not in the set. + /// + /// Computes in **O(n)** time (average). + pub fn shift_remove(&mut self, value: &Q) -> bool + where + Q: Hash + Equivalent, + { + self.map.shift_remove(value).is_some() + } + + /// Removes and returns the value in the set, if any, that is equal to the + /// given one. + /// + /// **NOTE:** This is equivalent to `.swap_take(value)`, if you need to + /// preserve the order of the values in the set, use `.shift_take(value)` + /// instead. + /// + /// Computes in **O(1)** time (average). + pub fn take(&mut self, value: &Q) -> Option + where + Q: Hash + Equivalent, + { + self.swap_take(value) + } + + /// Removes and returns the value in the set, if any, that is equal to the + /// given one. + /// + /// Like `Vec::swap_remove`, the value is removed by swapping it with the + /// last element of the set and popping it off. **This perturbs + /// the position of what used to be the last element!** + /// + /// Return `None` if `value` was not in the set. + /// + /// Computes in **O(1)** time (average). + pub fn swap_take(&mut self, value: &Q) -> Option + where + Q: Hash + Equivalent, + { + self.map.swap_remove_entry(value).map(|(x, ())| x) + } + + /// Removes and returns the value in the set, if any, that is equal to the + /// given one. + /// + /// Like `Vec::remove`, the value is removed by shifting all of the + /// elements that follow it, preserving their relative order. + /// **This perturbs the index of all of those elements!** + /// + /// Return `None` if `value` was not in the set. + /// + /// Computes in **O(n)** time (average). + pub fn shift_take(&mut self, value: &Q) -> Option + where + Q: Hash + Equivalent, + { + self.map.shift_remove_entry(value).map(|(x, ())| x) + } + + /// Remove the value from the set return it and the index it had. + /// + /// Like `Vec::swap_remove`, the value is removed by swapping it with the + /// last element of the set and popping it off. **This perturbs + /// the position of what used to be the last element!** + /// + /// Return `None` if `value` was not in the set. + pub fn swap_remove_full(&mut self, value: &Q) -> Option<(usize, T)> + where + Q: Hash + Equivalent, + { + self.map.swap_remove_full(value).map(|(i, x, ())| (i, x)) + } + + /// Remove the value from the set return it and the index it had. + /// + /// Like `Vec::remove`, the value is removed by shifting all of the + /// elements that follow it, preserving their relative order. + /// **This perturbs the index of all of those elements!** + /// + /// Return `None` if `value` was not in the set. + pub fn shift_remove_full(&mut self, value: &Q) -> Option<(usize, T)> + where + Q: Hash + Equivalent, + { + self.map.shift_remove_full(value).map(|(i, x, ())| (i, x)) + } + + /// Remove the last value + /// + /// This preserves the order of the remaining elements. + /// + /// Computes in **O(1)** time (average). + pub fn pop(&mut self) -> Option { + self.map.pop().map(|(x, ())| x) + } + + /// Scan through each value in the set and keep those where the + /// closure `keep` returns `true`. + /// + /// The elements are visited in order, and remaining elements keep their + /// order. + /// + /// Computes in **O(n)** time (average). + pub fn retain(&mut self, mut keep: F) + where + F: FnMut(&T) -> bool, + { + self.map.retain(move |x, &mut ()| keep(x)) + } + + /// Sort the set’s values by their default ordering. + /// + /// See [`sort_by`](Self::sort_by) for details. + pub fn sort(&mut self) + where + T: Ord, + { + self.map.sort_keys() + } + + /// Sort the set’s values in place using the comparison function `cmp`. + /// + /// Computes in **O(n log n)** time and **O(n)** space. The sort is stable. + pub fn sort_by(&mut self, mut cmp: F) + where + F: FnMut(&T, &T) -> Ordering, + { + self.map.sort_by(move |a, _, b, _| cmp(a, b)); + } + + /// Sort the values of the set and return a by-value iterator of + /// the values with the result. + /// + /// The sort is stable. + pub fn sorted_by(self, mut cmp: F) -> IntoIter + where + F: FnMut(&T, &T) -> Ordering, + { + let mut entries = self.into_entries(); + entries.sort_by(move |a, b| cmp(&a.key, &b.key)); + IntoIter { + iter: entries.into_iter(), + } + } + + /// Sort the set's values by their default ordering. + /// + /// See [`sort_unstable_by`](Self::sort_unstable_by) for details. + pub fn sort_unstable(&mut self) + where + T: Ord, + { + self.map.sort_unstable_keys() + } + + /// Sort the set's values in place using the comparison funtion `cmp`. + /// + /// Computes in **O(n log n)** time. The sort is unstable. + pub fn sort_unstable_by(&mut self, mut cmp: F) + where + F: FnMut(&T, &T) -> Ordering, + { + self.map.sort_unstable_by(move |a, _, b, _| cmp(a, b)) + } + + /// Sort the values of the set and return a by-value iterator of + /// the values with the result. + pub fn sorted_unstable_by(self, mut cmp: F) -> IntoIter + where + F: FnMut(&T, &T) -> Ordering, + { + let mut entries = self.into_entries(); + entries.sort_unstable_by(move |a, b| cmp(&a.key, &b.key)); + IntoIter { + iter: entries.into_iter(), + } + } + + /// Reverses the order of the set’s values in place. + /// + /// Computes in **O(n)** time and **O(1)** space. + pub fn reverse(&mut self) { + self.map.reverse() + } +} + +impl IndexSet { + /// Get a value by index + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Computes in **O(1)** time. + pub fn get_index(&self, index: usize) -> Option<&T> { + self.as_entries().get(index).map(Bucket::key_ref) + } + + /// Get the first value + /// + /// Computes in **O(1)** time. + pub fn first(&self) -> Option<&T> { + self.as_entries().first().map(Bucket::key_ref) + } + + /// Get the last value + /// + /// Computes in **O(1)** time. + pub fn last(&self) -> Option<&T> { + self.as_entries().last().map(Bucket::key_ref) + } + + /// Remove the value by index + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Like `Vec::swap_remove`, the value is removed by swapping it with the + /// last element of the set and popping it off. **This perturbs + /// the position of what used to be the last element!** + /// + /// Computes in **O(1)** time (average). + pub fn swap_remove_index(&mut self, index: usize) -> Option { + self.map.swap_remove_index(index).map(|(x, ())| x) + } + + /// Remove the value by index + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Like `Vec::remove`, the value is removed by shifting all of the + /// elements that follow it, preserving their relative order. + /// **This perturbs the index of all of those elements!** + /// + /// Computes in **O(n)** time (average). + pub fn shift_remove_index(&mut self, index: usize) -> Option { + self.map.shift_remove_index(index).map(|(x, ())| x) + } + + /// Moves the position of a value from one index to another + /// by shifting all other values in-between. + /// + /// * If `from < to`, the other values will shift down while the targeted value moves up. + /// * If `from > to`, the other values will shift up while the targeted value moves down. + /// + /// ***Panics*** if `from` or `to` are out of bounds. + /// + /// Computes in **O(n)** time (average). + pub fn move_index(&mut self, from: usize, to: usize) { + self.map.move_index(from, to) + } + + /// Swaps the position of two values in the set. + /// + /// ***Panics*** if `a` or `b` are out of bounds. + pub fn swap_indices(&mut self, a: usize, b: usize) { + self.map.swap_indices(a, b) + } +} + +/// Access `IndexSet` values at indexed positions. +/// +/// # Examples +/// +/// ``` +/// use indexmap::IndexSet; +/// +/// let mut set = IndexSet::new(); +/// for word in "Lorem ipsum dolor sit amet".split_whitespace() { +/// set.insert(word.to_string()); +/// } +/// assert_eq!(set[0], "Lorem"); +/// assert_eq!(set[1], "ipsum"); +/// set.reverse(); +/// assert_eq!(set[0], "amet"); +/// assert_eq!(set[1], "sit"); +/// set.sort(); +/// assert_eq!(set[0], "Lorem"); +/// assert_eq!(set[1], "amet"); +/// ``` +/// +/// ```should_panic +/// use indexmap::IndexSet; +/// +/// let mut set = IndexSet::new(); +/// set.insert("foo"); +/// println!("{:?}", set[10]); // panics! +/// ``` +impl Index for IndexSet { + type Output = T; + + /// Returns a reference to the value at the supplied `index`. + /// + /// ***Panics*** if `index` is out of bounds. + fn index(&self, index: usize) -> &T { + self.get_index(index) + .expect("IndexSet: index out of bounds") + } +} + +/// 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 { + iter: vec::IntoIter>, +} + +impl Iterator for IntoIter { + type Item = T; + + iterator_methods!(Bucket::key); +} + +impl DoubleEndedIterator for IntoIter { + double_ended_iterator_methods!(Bucket::key); +} + +impl ExactSizeIterator for IntoIter { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for IntoIter {} + +impl fmt::Debug for IntoIter { + 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>, +} + +impl<'a, T> Iterator for Iter<'a, T> { + type Item = &'a T; + + iterator_methods!(Bucket::key_ref); +} + +impl DoubleEndedIterator for Iter<'_, T> { + double_ended_iterator_methods!(Bucket::key_ref); +} + +impl ExactSizeIterator for Iter<'_, T> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for Iter<'_, T> {} + +impl Clone for Iter<'_, T> { + fn clone(&self) -> Self { + Iter { + iter: self.iter.clone(), + } + } +} + +impl 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>, +} + +impl Iterator for Drain<'_, T> { + type Item = T; + + iterator_methods!(Bucket::key); +} + +impl DoubleEndedIterator for Drain<'_, T> { + double_ended_iterator_methods!(Bucket::key); +} + +impl ExactSizeIterator for Drain<'_, T> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl FusedIterator for Drain<'_, T> {} + +impl 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 { + type Item = &'a T; + type IntoIter = Iter<'a, T>; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl IntoIterator for IndexSet { + type Item = T; + type IntoIter = IntoIter; + + fn into_iter(self) -> Self::IntoIter { + IntoIter { + iter: self.into_entries().into_iter(), + } + } +} + +impl FromIterator for IndexSet +where + T: Hash + Eq, + S: BuildHasher + Default, +{ + fn from_iter>(iterable: I) -> Self { + let iter = iterable.into_iter().map(|x| (x, ())); + IndexSet { + map: IndexMap::from_iter(iter), + } + } +} + +#[cfg(has_std)] +impl From<[T; N]> for IndexSet +where + T: Eq + Hash, +{ + /// # Examples + /// + /// ``` + /// use indexmap::IndexSet; + /// + /// let set1 = IndexSet::from([1, 2, 3, 4]); + /// let set2: IndexSet<_> = [1, 2, 3, 4].into(); + /// assert_eq!(set1, set2); + /// ``` + fn from(arr: [T; N]) -> Self { + Self::from_iter(arr) + } +} + +impl Extend for IndexSet +where + T: Hash + Eq, + S: BuildHasher, +{ + fn extend>(&mut self, iterable: I) { + let iter = iterable.into_iter().map(|x| (x, ())); + self.map.extend(iter); + } +} + +impl<'a, T, S> Extend<&'a T> for IndexSet +where + T: Hash + Eq + Copy + 'a, + S: BuildHasher, +{ + fn extend>(&mut self, iterable: I) { + let iter = iterable.into_iter().copied(); + self.extend(iter); + } +} + +impl Default for IndexSet +where + S: Default, +{ + /// Return an empty `IndexSet` + fn default() -> Self { + IndexSet { + map: IndexMap::default(), + } + } +} + +impl PartialEq> for IndexSet +where + T: Hash + Eq, + S1: BuildHasher, + S2: BuildHasher, +{ + fn eq(&self, other: &IndexSet) -> bool { + self.len() == other.len() && self.is_subset(other) + } +} + +impl Eq for IndexSet +where + T: Eq + Hash, + S: BuildHasher, +{ +} + +impl IndexSet +where + T: Eq + Hash, + S: BuildHasher, +{ + /// Returns `true` if `self` has no elements in common with `other`. + pub fn is_disjoint(&self, other: &IndexSet) -> bool + where + S2: BuildHasher, + { + if self.len() <= other.len() { + self.iter().all(move |value| !other.contains(value)) + } else { + other.iter().all(move |value| !self.contains(value)) + } + } + + /// Returns `true` if all elements of `self` are contained in `other`. + pub fn is_subset(&self, other: &IndexSet) -> bool + where + S2: BuildHasher, + { + self.len() <= other.len() && self.iter().all(move |value| other.contains(value)) + } + + /// Returns `true` if all elements of `other` are contained in `self`. + pub fn is_superset(&self, other: &IndexSet) -> bool + where + S2: BuildHasher, + { + other.is_subset(self) + } +} + +/// 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, +} + +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 { + while let Some(item) = self.iter.next() { + if !self.other.contains(item) { + return Some(item); + } + } + None + } + + fn size_hint(&self) -> (usize, Option) { + (0, self.iter.size_hint().1) + } +} + +impl DoubleEndedIterator for Difference<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ + fn next_back(&mut self) -> Option { + while let Some(item) = self.iter.next_back() { + if !self.other.contains(item) { + return Some(item); + } + } + None + } +} + +impl FusedIterator for Difference<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ +} + +impl Clone for Difference<'_, T, S> { + fn clone(&self) -> Self { + Difference { + iter: self.iter.clone(), + ..*self + } + } +} + +impl 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, +} + +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 { + while let Some(item) = self.iter.next() { + if self.other.contains(item) { + return Some(item); + } + } + None + } + + fn size_hint(&self) -> (usize, Option) { + (0, self.iter.size_hint().1) + } +} + +impl DoubleEndedIterator for Intersection<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ + fn next_back(&mut self) -> Option { + while let Some(item) = self.iter.next_back() { + if self.other.contains(item) { + return Some(item); + } + } + None + } +} + +impl FusedIterator for Intersection<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ +} + +impl Clone for Intersection<'_, T, S> { + fn clone(&self) -> Self { + Intersection { + iter: self.iter.clone(), + ..*self + } + } +} + +impl 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, 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.iter.next() + } + + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } + + fn fold(self, init: B, f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter.fold(init, f) + } +} + +impl DoubleEndedIterator for SymmetricDifference<'_, T, S1, S2> +where + T: Eq + Hash, + S1: BuildHasher, + S2: BuildHasher, +{ + fn next_back(&mut self) -> Option { + self.iter.next_back() + } + + fn rfold(self, init: B, f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter.rfold(init, f) + } +} + +impl FusedIterator for SymmetricDifference<'_, T, S1, S2> +where + T: Eq + Hash, + S1: BuildHasher, + S2: BuildHasher, +{ +} + +impl Clone for SymmetricDifference<'_, T, S1, S2> { + fn clone(&self) -> Self { + SymmetricDifference { + iter: self.iter.clone(), + } + } +} + +impl 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, 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.iter.next() + } + + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } + + fn fold(self, init: B, f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter.fold(init, f) + } +} + +impl DoubleEndedIterator for Union<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ + fn next_back(&mut self) -> Option { + self.iter.next_back() + } + + fn rfold(self, init: B, f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter.rfold(init, f) + } +} + +impl FusedIterator for Union<'_, T, S> +where + T: Eq + Hash, + S: BuildHasher, +{ +} + +impl Clone for Union<'_, T, S> { + fn clone(&self) -> Self { + Union { + iter: self.iter.clone(), + } + } +} + +impl 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 BitAnd<&IndexSet> for &IndexSet +where + T: Eq + Hash + Clone, + S1: BuildHasher + Default, + S2: BuildHasher, +{ + type Output = IndexSet; + + /// Returns the set intersection, cloned into a new set. + /// + /// Values are collected in the same order that they appear in `self`. + fn bitand(self, other: &IndexSet) -> Self::Output { + self.intersection(other).cloned().collect() + } +} + +impl BitOr<&IndexSet> for &IndexSet +where + T: Eq + Hash + Clone, + S1: BuildHasher + Default, + S2: BuildHasher, +{ + type Output = IndexSet; + + /// Returns the set union, cloned into a new set. + /// + /// Values from `self` are collected in their original order, followed by + /// values that are unique to `other` in their original order. + fn bitor(self, other: &IndexSet) -> Self::Output { + self.union(other).cloned().collect() + } +} + +impl BitXor<&IndexSet> for &IndexSet +where + T: Eq + Hash + Clone, + S1: BuildHasher + Default, + S2: BuildHasher, +{ + type Output = IndexSet; + + /// Returns the set symmetric-difference, cloned into a new set. + /// + /// Values from `self` are collected in their original order, followed by + /// values from `other` in their original order. + fn bitxor(self, other: &IndexSet) -> Self::Output { + self.symmetric_difference(other).cloned().collect() + } +} + +impl Sub<&IndexSet> for &IndexSet +where + T: Eq + Hash + Clone, + S1: BuildHasher + Default, + S2: BuildHasher, +{ + type Output = IndexSet; + + /// Returns the set difference, cloned into a new set. + /// + /// Values are collected in the same order that they appear in `self`. + fn sub(self, other: &IndexSet) -> Self::Output { + 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::::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 = 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 = 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::::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::::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![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, + I2: Iterator, + { + 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::::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/third_party/rust/indexmap/src/util.rs b/third_party/rust/indexmap/src/util.rs new file mode 100644 index 0000000000..a24dfafde7 --- /dev/null +++ b/third_party/rust/indexmap/src/util.rs @@ -0,0 +1,31 @@ +use core::ops::{Bound, Range, RangeBounds}; + +pub(crate) fn third(t: (A, B, C)) -> C { + t.2 +} + +pub(crate) fn simplify_range(range: R, len: usize) -> Range +where + R: RangeBounds, +{ + let start = match range.start_bound() { + Bound::Unbounded => 0, + Bound::Included(&i) if i <= len => i, + Bound::Excluded(&i) if i < len => i + 1, + bound => panic!("range start {:?} should be <= length {}", bound, len), + }; + let end = match range.end_bound() { + Bound::Unbounded => len, + Bound::Excluded(&i) if i <= len => i, + Bound::Included(&i) if i < len => i + 1, + bound => panic!("range end {:?} should be <= length {}", bound, len), + }; + if start > end { + panic!( + "range start {:?} should be <= range end {:?}", + range.start_bound(), + range.end_bound() + ); + } + start..end +} -- cgit v1.2.3