summaryrefslogtreecommitdiffstats
path: root/third_party/rust/indexmap/src
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/rust/indexmap/src')
-rw-r--r--third_party/rust/indexmap/src/arbitrary.rs75
-rw-r--r--third_party/rust/indexmap/src/equivalent.rs27
-rw-r--r--third_party/rust/indexmap/src/lib.rs194
-rw-r--r--third_party/rust/indexmap/src/macros.rs178
-rw-r--r--third_party/rust/indexmap/src/map.rs1947
-rw-r--r--third_party/rust/indexmap/src/map/core.rs700
-rw-r--r--third_party/rust/indexmap/src/map/core/raw.rs191
-rw-r--r--third_party/rust/indexmap/src/mutable_keys.rs75
-rw-r--r--third_party/rust/indexmap/src/rayon/map.rs583
-rw-r--r--third_party/rust/indexmap/src/rayon/mod.rs27
-rw-r--r--third_party/rust/indexmap/src/rayon/set.rs741
-rw-r--r--third_party/rust/indexmap/src/rustc.rs158
-rw-r--r--third_party/rust/indexmap/src/serde.rs155
-rw-r--r--third_party/rust/indexmap/src/serde_seq.rs112
-rw-r--r--third_party/rust/indexmap/src/set.rs1912
-rw-r--r--third_party/rust/indexmap/src/util.rs31
16 files changed, 7106 insertions, 0 deletions
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<K, V, S>
+ where
+ K: Arbitrary<'a> + Hash + Eq,
+ V: Arbitrary<'a>,
+ S: BuildHasher + Default,
+ {
+ fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
+ u.arbitrary_iter()?.collect()
+ }
+
+ fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
+ u.arbitrary_take_rest_iter()?.collect()
+ }
+ }
+
+ impl<'a, T, S> Arbitrary<'a> for IndexSet<T, S>
+ where
+ T: Arbitrary<'a> + Hash + Eq,
+ S: BuildHasher + Default,
+ {
+ fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
+ u.arbitrary_iter()?.collect()
+ }
+
+ fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
+ 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<K, V, S> Arbitrary for IndexMap<K, V, S>
+ 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<dyn Iterator<Item = Self>> {
+ let vec = Vec::from_iter(self.clone());
+ Box::new(vec.shrink().map(Self::from_iter))
+ }
+ }
+
+ impl<T, S> Arbitrary for IndexSet<T, S>
+ 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<dyn Iterator<Item = Self>> {
+ 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<K: ?Sized> {
+ /// Compare self to `key` and return `true` if they are equal.
+ fn equivalent(&self, key: &K) -> bool;
+}
+
+impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q
+where
+ Q: Eq,
+ K: Borrow<Q>,
+{
+ #[inline]
+ fn equivalent(&self, key: &K) -> bool {
+ *self == *key.borrow()
+ }
+}
diff --git a/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<K, V> = IndexMap<K, V, FnvBuildHasher>;
+//! type FnvIndexSet<T> = IndexSet<T, FnvBuildHasher>;
+//!
+//! type FxIndexMap<K, V> = IndexMap<K, V, FxBuildHasher>;
+//! type FxIndexSet<T> = IndexSet<T, FxBuildHasher>;
+//!
+//! let std: IndexSet<i32> = (0..100).collect();
+//! let fnv: FnvIndexSet<i32> = (0..100).collect();
+//! let fx: FxIndexSet<i32> = (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<K, V> {
+ hash: HashValue,
+ key: K,
+ value: V,
+}
+
+impl<K, V> Clone for Bucket<K, V>
+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<K, V> Bucket<K, V> {
+ // 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<Self::Entry>;
+ fn as_entries(&self) -> &[Self::Entry];
+ fn as_entries_mut(&mut self) -> &mut [Self::Entry];
+ fn with_entries<F>(&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::Item> {
+ self.iter.next().map($map_elt)
+ }
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.iter.size_hint()
+ }
+
+ fn count(self) -> usize {
+ self.iter.len()
+ }
+
+ fn nth(&mut self, n: usize) -> Option<Self::Item> {
+ self.iter.nth(n).map($map_elt)
+ }
+
+ fn last(mut self) -> Option<Self::Item> {
+ self.next_back()
+ }
+
+ fn collect<C>(self) -> C
+ where
+ C: FromIterator<Self::Item>,
+ {
+ // 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::Item> {
+ self.iter.next_back().map($map_elt)
+ }
+
+ fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
+ 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<C>(self, consumer: C) -> C::Result
+ where
+ C: UnindexedConsumer<Self::Item>,
+ {
+ 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<usize> {
+ 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<C>(self, consumer: C) -> C::Result
+ where
+ C: Consumer<Self::Item>,
+ {
+ self.entries.into_par_iter().map($map_elt).drive(consumer)
+ }
+
+ fn len(&self) -> usize {
+ self.entries.len()
+ }
+
+ fn with_producer<CB>(self, callback: CB) -> CB::Output
+ where
+ CB: ProducerCallback<Self::Item>,
+ {
+ 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<K, V, S = RandomState> {
+ pub(crate) core: IndexMapCore<K, V>,
+ hash_builder: S,
+}
+#[cfg(not(has_std))]
+pub struct IndexMap<K, V, S> {
+ pub(crate) core: IndexMapCore<K, V>,
+ hash_builder: S,
+}
+
+impl<K, V, S> Clone for IndexMap<K, V, S>
+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<K, V, S> Entries for IndexMap<K, V, S> {
+ type Entry = Bucket<K, V>;
+
+ #[inline]
+ fn into_entries(self) -> Vec<Self::Entry> {
+ 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<F>(&mut self, f: F)
+ where
+ F: FnOnce(&mut [Self::Entry]),
+ {
+ self.core.with_entries(f);
+ }
+}
+
+impl<K, V, S> fmt::Debug for IndexMap<K, V, S>
+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<K, V> IndexMap<K, V> {
+ /// 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<K, V, S> IndexMap<K, V, S> {
+ /// 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<K, V> {
+ 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<K, V> {
+ 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<usize>`,
+ /// 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<R>(&mut self, range: R) -> Drain<'_, K, V>
+ where
+ R: RangeBounds<usize>,
+ {
+ 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<K, V, S> IndexMap<K, V, S>
+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<Q: ?Sized + 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<V> {
+ 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<V>) {
+ 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<Q: ?Sized>(&self, key: &Q) -> bool
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ 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<Q: ?Sized>(&self, key: &Q) -> Option<&V>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ 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<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ 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<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ 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<Q: ?Sized>(&self, key: &Q) -> Option<usize>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ if self.is_empty() {
+ None
+ } else {
+ let hash = self.hash(key);
+ self.core.get_index_of(hash, key)
+ }
+ }
+
+ pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ if let Some(i) = self.get_index_of(key) {
+ let entry = &mut self.as_entries_mut()[i];
+ Some(&mut entry.value)
+ } else {
+ None
+ }
+ }
+
+ pub fn get_full_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &K, &mut V)>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ if let Some(i) = self.get_index_of(key) {
+ let entry = &mut self.as_entries_mut()[i];
+ Some((i, &entry.key, &mut entry.value))
+ } else {
+ None
+ }
+ }
+
+ pub(crate) fn get_full_mut2_impl<Q: ?Sized>(
+ &mut self,
+ key: &Q,
+ ) -> Option<(usize, &mut K, &mut V)>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ if let Some(i) = self.get_index_of(key) {
+ let entry = &mut self.as_entries_mut()[i];
+ Some((i, &mut entry.key, &mut entry.value))
+ } else {
+ None
+ }
+ }
+
+ /// Remove the key-value pair equivalent to `key` and return
+ /// its value.
+ ///
+ /// **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<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ 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<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ 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<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ 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<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ 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<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ 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<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ 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<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ 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<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ 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<F>(&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<F>(&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<F>(&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<F>(self, mut cmp: F) -> IntoIter<K, V>
+ 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<F>(&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<F>(self, mut cmp: F) -> IntoIter<K, V>
+ 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<K, V, S> IndexMap<K, V, S> {
+ /// 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<K, V>>,
+}
+
+impl<'a, K, V> Iterator for Keys<'a, K, V> {
+ type Item = &'a K;
+
+ iterator_methods!(Bucket::key_ref);
+}
+
+impl<K, V> DoubleEndedIterator for Keys<'_, K, V> {
+ double_ended_iterator_methods!(Bucket::key_ref);
+}
+
+impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for Keys<'_, K, V> {}
+
+// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
+impl<K, V> Clone for Keys<'_, K, V> {
+ fn clone(&self) -> Self {
+ Keys {
+ iter: self.iter.clone(),
+ }
+ }
+}
+
+impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+/// An owning iterator over the keys of a `IndexMap`.
+///
+/// This `struct` is created by the [`into_keys`] method on [`IndexMap`].
+/// See its documentation for more.
+///
+/// [`IndexMap`]: struct.IndexMap.html
+/// [`into_keys`]: struct.IndexMap.html#method.into_keys
+pub struct IntoKeys<K, V> {
+ iter: vec::IntoIter<Bucket<K, V>>,
+}
+
+impl<K, V> Iterator for IntoKeys<K, V> {
+ type Item = K;
+
+ iterator_methods!(Bucket::key);
+}
+
+impl<K, V> DoubleEndedIterator for IntoKeys<K, V> {
+ double_ended_iterator_methods!(Bucket::key);
+}
+
+impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for IntoKeys<K, V> {}
+
+impl<K: fmt::Debug, V> fmt::Debug for IntoKeys<K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
+ f.debug_list().entries(iter).finish()
+ }
+}
+
+/// An iterator over the values of a `IndexMap`.
+///
+/// This `struct` is created by the [`values`] method on [`IndexMap`]. See its
+/// documentation for more.
+///
+/// [`values`]: struct.IndexMap.html#method.values
+/// [`IndexMap`]: struct.IndexMap.html
+pub struct Values<'a, K, V> {
+ iter: SliceIter<'a, Bucket<K, V>>,
+}
+
+impl<'a, K, V> Iterator for Values<'a, K, V> {
+ type Item = &'a V;
+
+ iterator_methods!(Bucket::value_ref);
+}
+
+impl<K, V> DoubleEndedIterator for Values<'_, K, V> {
+ double_ended_iterator_methods!(Bucket::value_ref);
+}
+
+impl<K, V> ExactSizeIterator for Values<'_, K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for Values<'_, K, V> {}
+
+// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
+impl<K, V> Clone for Values<'_, K, V> {
+ fn clone(&self) -> Self {
+ Values {
+ iter: self.iter.clone(),
+ }
+ }
+}
+
+impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+/// A mutable iterator over the values of a `IndexMap`.
+///
+/// This `struct` is created by the [`values_mut`] method on [`IndexMap`]. See its
+/// documentation for more.
+///
+/// [`values_mut`]: struct.IndexMap.html#method.values_mut
+/// [`IndexMap`]: struct.IndexMap.html
+pub struct ValuesMut<'a, K, V> {
+ iter: SliceIterMut<'a, Bucket<K, V>>,
+}
+
+impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
+ type Item = &'a mut V;
+
+ iterator_methods!(Bucket::value_mut);
+}
+
+impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> {
+ double_ended_iterator_methods!(Bucket::value_mut);
+}
+
+impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
+
+impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let iter = self.iter.as_slice().iter().map(Bucket::value_ref);
+ f.debug_list().entries(iter).finish()
+ }
+}
+
+/// An owning iterator over the values of a `IndexMap`.
+///
+/// This `struct` is created by the [`into_values`] method on [`IndexMap`].
+/// See its documentation for more.
+///
+/// [`IndexMap`]: struct.IndexMap.html
+/// [`into_values`]: struct.IndexMap.html#method.into_values
+pub struct IntoValues<K, V> {
+ iter: vec::IntoIter<Bucket<K, V>>,
+}
+
+impl<K, V> Iterator for IntoValues<K, V> {
+ type Item = V;
+
+ iterator_methods!(Bucket::value);
+}
+
+impl<K, V> DoubleEndedIterator for IntoValues<K, V> {
+ double_ended_iterator_methods!(Bucket::value);
+}
+
+impl<K, V> ExactSizeIterator for IntoValues<K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for IntoValues<K, V> {}
+
+impl<K, V: fmt::Debug> fmt::Debug for IntoValues<K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let iter = self.iter.as_slice().iter().map(Bucket::value_ref);
+ f.debug_list().entries(iter).finish()
+ }
+}
+
+/// An iterator over the entries of a `IndexMap`.
+///
+/// This `struct` is created by the [`iter`] method on [`IndexMap`]. See its
+/// documentation for more.
+///
+/// [`iter`]: struct.IndexMap.html#method.iter
+/// [`IndexMap`]: struct.IndexMap.html
+pub struct Iter<'a, K, V> {
+ iter: SliceIter<'a, Bucket<K, V>>,
+}
+
+impl<'a, K, V> Iterator for Iter<'a, K, V> {
+ type Item = (&'a K, &'a V);
+
+ iterator_methods!(Bucket::refs);
+}
+
+impl<K, V> DoubleEndedIterator for Iter<'_, K, V> {
+ double_ended_iterator_methods!(Bucket::refs);
+}
+
+impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for Iter<'_, K, V> {}
+
+// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
+impl<K, V> Clone for Iter<'_, K, V> {
+ fn clone(&self) -> Self {
+ Iter {
+ iter: self.iter.clone(),
+ }
+ }
+}
+
+impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+/// A mutable iterator over the entries of a `IndexMap`.
+///
+/// This `struct` is created by the [`iter_mut`] method on [`IndexMap`]. See its
+/// documentation for more.
+///
+/// [`iter_mut`]: struct.IndexMap.html#method.iter_mut
+/// [`IndexMap`]: struct.IndexMap.html
+pub struct IterMut<'a, K, V> {
+ iter: SliceIterMut<'a, Bucket<K, V>>,
+}
+
+impl<'a, K, V> Iterator for IterMut<'a, K, V> {
+ type Item = (&'a K, &'a mut V);
+
+ iterator_methods!(Bucket::ref_mut);
+}
+
+impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> {
+ double_ended_iterator_methods!(Bucket::ref_mut);
+}
+
+impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for IterMut<'_, K, V> {}
+
+impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let iter = self.iter.as_slice().iter().map(Bucket::refs);
+ f.debug_list().entries(iter).finish()
+ }
+}
+
+/// An owning iterator over the entries of a `IndexMap`.
+///
+/// This `struct` is created by the [`into_iter`] method on [`IndexMap`]
+/// (provided by the `IntoIterator` trait). See its documentation for more.
+///
+/// [`into_iter`]: struct.IndexMap.html#method.into_iter
+/// [`IndexMap`]: struct.IndexMap.html
+pub struct IntoIter<K, V> {
+ iter: vec::IntoIter<Bucket<K, V>>,
+}
+
+impl<K, V> Iterator for IntoIter<K, V> {
+ type Item = (K, V);
+
+ iterator_methods!(Bucket::key_value);
+}
+
+impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
+ double_ended_iterator_methods!(Bucket::key_value);
+}
+
+impl<K, V> ExactSizeIterator for IntoIter<K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for IntoIter<K, V> {}
+
+impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let iter = self.iter.as_slice().iter().map(Bucket::refs);
+ f.debug_list().entries(iter).finish()
+ }
+}
+
+/// A draining iterator over the entries of a `IndexMap`.
+///
+/// This `struct` is created by the [`drain`] method on [`IndexMap`]. See its
+/// documentation for more.
+///
+/// [`drain`]: struct.IndexMap.html#method.drain
+/// [`IndexMap`]: struct.IndexMap.html
+pub struct Drain<'a, K, V> {
+ pub(crate) iter: vec::Drain<'a, Bucket<K, V>>,
+}
+
+impl<K, V> Iterator for Drain<'_, K, V> {
+ type Item = (K, V);
+
+ iterator_methods!(Bucket::key_value);
+}
+
+impl<K, V> DoubleEndedIterator for Drain<'_, K, V> {
+ double_ended_iterator_methods!(Bucket::key_value);
+}
+
+impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for Drain<'_, K, V> {}
+
+impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Drain<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let iter = self.iter.as_slice().iter().map(Bucket::refs);
+ f.debug_list().entries(iter).finish()
+ }
+}
+
+impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S> {
+ type Item = (&'a K, &'a V);
+ type IntoIter = Iter<'a, K, V>;
+ fn into_iter(self) -> Self::IntoIter {
+ self.iter()
+ }
+}
+
+impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S> {
+ type Item = (&'a K, &'a mut V);
+ type IntoIter = IterMut<'a, K, V>;
+ fn into_iter(self) -> Self::IntoIter {
+ self.iter_mut()
+ }
+}
+
+impl<K, V, S> IntoIterator for IndexMap<K, V, S> {
+ type Item = (K, V);
+ type IntoIter = IntoIter<K, V>;
+ fn into_iter(self) -> Self::IntoIter {
+ IntoIter {
+ iter: self.into_entries().into_iter(),
+ }
+ }
+}
+
+/// Access `IndexMap` values corresponding to a key.
+///
+/// # Examples
+///
+/// ```
+/// 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<K, V, Q: ?Sized, S> Index<&Q> for IndexMap<K, V, S>
+where
+ Q: Hash + Equivalent<K>,
+ 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<K, V, Q: ?Sized, S> IndexMut<&Q> for IndexMap<K, V, S>
+where
+ Q: Hash + Equivalent<K>,
+ 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<K, V, S> Index<usize> for IndexMap<K, V, S> {
+ 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<K, V, S> IndexMut<usize> for IndexMap<K, V, S> {
+ /// 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<K, V, S> FromIterator<(K, V)> for IndexMap<K, V, S>
+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<I: IntoIterator<Item = (K, V)>>(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<K, V, const N: usize> From<[(K, V); N]> for IndexMap<K, V, RandomState>
+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<K, V, S> Extend<(K, V)> for IndexMap<K, V, S>
+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<I: IntoIterator<Item = (K, V)>>(&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<K, V, S>
+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<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iterable: I) {
+ self.extend(iterable.into_iter().map(|(&key, &value)| (key, value)));
+ }
+}
+
+impl<K, V, S> Default for IndexMap<K, V, S>
+where
+ S: Default,
+{
+ /// Return an empty `IndexMap`
+ fn default() -> Self {
+ Self::with_capacity_and_hasher(0, S::default())
+ }
+}
+
+impl<K, V1, S1, V2, S2> PartialEq<IndexMap<K, V2, S2>> for IndexMap<K, V1, S1>
+where
+ K: Hash + Eq,
+ V1: PartialEq<V2>,
+ S1: BuildHasher,
+ S2: BuildHasher,
+{
+ fn eq(&self, other: &IndexMap<K, V2, S2>) -> bool {
+ if self.len() != other.len() {
+ return false;
+ }
+
+ self.iter()
+ .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
+ }
+}
+
+impl<K, V, S> Eq for IndexMap<K, V, S>
+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::<String, String>::new();
+ println!("{:?}", map);
+ assert_eq!(map.capacity(), 0);
+ assert_eq!(map.len(), 0);
+ assert_eq!(map.is_empty(), true);
+ }
+
+ #[test]
+ fn insert() {
+ let insert = [0, 4, 2, 12, 8, 7, 11, 5];
+ let not_present = [1, 3, 6, 9, 10];
+ let mut map = IndexMap::with_capacity(insert.len());
+
+ for (i, &elt) in insert.iter().enumerate() {
+ assert_eq!(map.len(), i);
+ map.insert(elt, elt);
+ assert_eq!(map.len(), i + 1);
+ assert_eq!(map.get(&elt), Some(&elt));
+ assert_eq!(map[&elt], elt);
+ }
+ println!("{:?}", map);
+
+ for &elt in &not_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 &not_present {
+ assert!(map.get(&elt).is_none());
+ }
+ }
+
+ #[test]
+ fn reserve() {
+ let mut map = IndexMap::<usize, usize>::new();
+ assert_eq!(map.capacity(), 0);
+ map.reserve(100);
+ let capacity = map.capacity();
+ assert!(capacity >= 100);
+ for i in 0..capacity {
+ assert_eq!(map.len(), i);
+ map.insert(i, i * i);
+ assert_eq!(map.len(), i + 1);
+ assert_eq!(map.capacity(), capacity);
+ assert_eq!(map.get(&i), Some(&(i * i)));
+ }
+ map.insert(capacity, std::usize::MAX);
+ assert_eq!(map.len(), capacity + 1);
+ assert!(map.capacity() > capacity);
+ assert_eq!(map.get(&capacity), Some(&std::usize::MAX));
+ }
+
+ #[test]
+ fn shrink_to_fit() {
+ let mut map = IndexMap::<usize, usize>::new();
+ assert_eq!(map.capacity(), 0);
+ for i in 0..100 {
+ assert_eq!(map.len(), i);
+ map.insert(i, i * i);
+ assert_eq!(map.len(), i + 1);
+ assert!(map.capacity() >= i + 1);
+ assert_eq!(map.get(&i), Some(&(i * i)));
+ map.shrink_to_fit();
+ assert_eq!(map.len(), i + 1);
+ assert_eq!(map.capacity(), i + 1);
+ assert_eq!(map.get(&i), Some(&(i * i)));
+ }
+ }
+
+ #[test]
+ fn remove() {
+ let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
+ let mut map = IndexMap::new();
+
+ for &elt in &insert {
+ map.insert(elt, elt);
+ }
+
+ assert_eq!(map.keys().count(), map.len());
+ assert_eq!(map.keys().count(), insert.len());
+ for (a, b) in insert.iter().zip(map.keys()) {
+ assert_eq!(a, b);
+ }
+
+ let remove_fail = [99, 77];
+ let remove = [4, 12, 8, 7];
+
+ for &key in &remove_fail {
+ assert!(map.swap_remove_full(&key).is_none());
+ }
+ println!("{:?}", map);
+ for &key in &remove {
+ //println!("{:?}", map);
+ let index = map.get_full(&key).unwrap().0;
+ assert_eq!(map.swap_remove_full(&key), Some((index, key, key)));
+ }
+ println!("{:?}", map);
+
+ for key in &insert {
+ assert_eq!(map.get(key).is_some(), !remove.contains(key));
+ }
+ assert_eq!(map.len(), insert.len() - remove.len());
+ assert_eq!(map.keys().count(), insert.len() - remove.len());
+ }
+
+ #[test]
+ fn remove_to_empty() {
+ let mut map = indexmap! { 0 => 0, 4 => 4, 5 => 5 };
+ map.swap_remove(&5).unwrap();
+ map.swap_remove(&4).unwrap();
+ map.swap_remove(&0).unwrap();
+ assert!(map.is_empty());
+ }
+
+ #[test]
+ fn swap_remove_index() {
+ let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
+ let mut map = IndexMap::new();
+
+ for &elt in &insert {
+ map.insert(elt, elt * 2);
+ }
+
+ let mut vector = insert.to_vec();
+ let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1];
+
+ // check that the same swap remove sequence on vec and map
+ // have the same result.
+ for &rm in remove_sequence {
+ let out_vec = vector.swap_remove(rm);
+ let (out_map, _) = map.swap_remove_index(rm).unwrap();
+ assert_eq!(out_vec, out_map);
+ }
+ assert_eq!(vector.len(), map.len());
+ for (a, b) in vector.iter().zip(map.keys()) {
+ assert_eq!(a, b);
+ }
+ }
+
+ #[test]
+ fn partial_eq_and_eq() {
+ let mut map_a = IndexMap::new();
+ map_a.insert(1, "1");
+ map_a.insert(2, "2");
+ let mut map_b = map_a.clone();
+ assert_eq!(map_a, map_b);
+ map_b.swap_remove(&1);
+ assert_ne!(map_a, map_b);
+
+ let map_c: IndexMap<_, String> = map_b.into_iter().map(|(k, v)| (k, v.into())).collect();
+ assert_ne!(map_a, map_c);
+ assert_ne!(map_c, map_a);
+ }
+
+ #[test]
+ fn extend() {
+ let mut map = IndexMap::new();
+ map.extend(vec![(&1, &2), (&3, &4)]);
+ map.extend(vec![(5, 6)]);
+ assert_eq!(
+ map.into_iter().collect::<Vec<_>>(),
+ vec![(1, 2), (3, 4), (5, 6)]
+ );
+ }
+
+ #[test]
+ fn entry() {
+ let mut map = IndexMap::new();
+
+ map.insert(1, "1");
+ map.insert(2, "2");
+ {
+ let e = map.entry(3);
+ assert_eq!(e.index(), 2);
+ let e = e.or_insert("3");
+ assert_eq!(e, &"3");
+ }
+
+ let e = map.entry(2);
+ assert_eq!(e.index(), 1);
+ assert_eq!(e.key(), &2);
+ match e {
+ Entry::Occupied(ref e) => assert_eq!(e.get(), &"2"),
+ Entry::Vacant(_) => panic!(),
+ }
+ assert_eq!(e.or_insert("4"), &"2");
+ }
+
+ #[test]
+ fn entry_and_modify() {
+ let mut map = IndexMap::new();
+
+ map.insert(1, "1");
+ map.entry(1).and_modify(|x| *x = "2");
+ assert_eq!(Some(&"2"), map.get(&1));
+
+ map.entry(2).and_modify(|x| *x = "doesn't exist");
+ assert_eq!(None, map.get(&2));
+ }
+
+ #[test]
+ fn entry_or_default() {
+ let mut map = IndexMap::new();
+
+ #[derive(Debug, PartialEq)]
+ enum TestEnum {
+ DefaultValue,
+ NonDefaultValue,
+ }
+
+ impl Default for TestEnum {
+ fn default() -> Self {
+ TestEnum::DefaultValue
+ }
+ }
+
+ map.insert(1, TestEnum::NonDefaultValue);
+ assert_eq!(&mut TestEnum::NonDefaultValue, map.entry(1).or_default());
+
+ assert_eq!(&mut TestEnum::DefaultValue, map.entry(2).or_default());
+ }
+
+ #[test]
+ fn occupied_entry_key() {
+ // These keys match hash and equality, but their addresses are distinct.
+ let (k1, k2) = (&mut 1, &mut 1);
+ let k1_ptr = k1 as *const i32;
+ let k2_ptr = k2 as *const i32;
+ assert_ne!(k1_ptr, k2_ptr);
+
+ let mut map = IndexMap::new();
+ map.insert(k1, "value");
+ match map.entry(k2) {
+ Entry::Occupied(ref e) => {
+ // `OccupiedEntry::key` should reference the key in the map,
+ // not the key that was used to find the entry.
+ let ptr = *e.key() as *const i32;
+ assert_eq!(ptr, k1_ptr);
+ assert_ne!(ptr, k2_ptr);
+ }
+ Entry::Vacant(_) => panic!(),
+ }
+ }
+
+ #[test]
+ fn keys() {
+ let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
+ let map: IndexMap<_, _> = vec.into_iter().collect();
+ let keys: Vec<_> = map.keys().copied().collect();
+ assert_eq!(keys.len(), 3);
+ assert!(keys.contains(&1));
+ assert!(keys.contains(&2));
+ assert!(keys.contains(&3));
+ }
+
+ #[test]
+ fn into_keys() {
+ let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
+ let map: IndexMap<_, _> = vec.into_iter().collect();
+ let keys: Vec<i32> = map.into_keys().collect();
+ assert_eq!(keys.len(), 3);
+ assert!(keys.contains(&1));
+ assert!(keys.contains(&2));
+ assert!(keys.contains(&3));
+ }
+
+ #[test]
+ fn values() {
+ let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
+ let map: IndexMap<_, _> = vec.into_iter().collect();
+ let values: Vec<_> = map.values().copied().collect();
+ assert_eq!(values.len(), 3);
+ assert!(values.contains(&'a'));
+ assert!(values.contains(&'b'));
+ assert!(values.contains(&'c'));
+ }
+
+ #[test]
+ fn values_mut() {
+ let vec = vec![(1, 1), (2, 2), (3, 3)];
+ let mut map: IndexMap<_, _> = vec.into_iter().collect();
+ for value in map.values_mut() {
+ *value *= 2
+ }
+ let values: Vec<_> = map.values().copied().collect();
+ assert_eq!(values.len(), 3);
+ assert!(values.contains(&2));
+ assert!(values.contains(&4));
+ assert!(values.contains(&6));
+ }
+
+ #[test]
+ fn into_values() {
+ let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
+ let map: IndexMap<_, _> = vec.into_iter().collect();
+ let values: Vec<char> = map.into_values().collect();
+ assert_eq!(values.len(), 3);
+ assert!(values.contains(&'a'));
+ assert!(values.contains(&'b'));
+ assert!(values.contains(&'c'));
+ }
+
+ #[test]
+ #[cfg(has_std)]
+ fn from_array() {
+ let map = IndexMap::from([(1, 2), (3, 4)]);
+ let mut expected = IndexMap::new();
+ expected.insert(1, 2);
+ expected.insert(3, 4);
+
+ assert_eq!(map, expected)
+ }
+}
diff --git a/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<K, V> {
+ /// indices mapping from the entry hash to its index.
+ indices: RawTable<usize>,
+ /// entries is a dense vec of entries in their order.
+ entries: Vec<Bucket<K, V>>,
+}
+
+#[inline(always)]
+fn get_hash<K, V>(entries: &[Bucket<K, V>]) -> impl Fn(&usize) -> u64 + '_ {
+ move |&i| entries[i].hash.get()
+}
+
+#[inline]
+fn equivalent<'a, K, V, Q: ?Sized + Equivalent<K>>(
+ key: &'a Q,
+ entries: &'a [Bucket<K, V>],
+) -> impl Fn(&usize) -> bool + 'a {
+ move |&i| Q::equivalent(key, &entries[i].key)
+}
+
+#[inline]
+fn erase_index(table: &mut RawTable<usize>, 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<usize>, hash: HashValue, old: usize, new: usize) {
+ let index = table
+ .get_mut(hash.get(), move |&i| i == old)
+ .expect("index not found");
+ *index = new;
+}
+
+impl<K, V> Clone for IndexMapCore<K, V>
+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<K, V> fmt::Debug for IndexMapCore<K, V>
+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<K, V> Entries for IndexMapCore<K, V> {
+ type Entry = Bucket<K, V>;
+
+ #[inline]
+ fn into_entries(self) -> Vec<Self::Entry> {
+ 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<F>(&mut self, f: F)
+ where
+ F: FnOnce(&mut [Self::Entry]),
+ {
+ f(&mut self.entries);
+ self.rebuild_hash_table();
+ }
+}
+
+impl<K, V> IndexMapCore<K, V> {
+ #[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<R>(&mut self, range: R) -> Drain<'_, Bucket<K, V>>
+ where
+ R: RangeBounds<usize>,
+ {
+ 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<R>(&mut self, range: R) -> rayon::vec::Drain<'_, Bucket<K, V>>
+ where
+ K: Send,
+ V: Send,
+ R: RangeBounds<usize>,
+ {
+ 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<Q>(&self, hash: HashValue, key: &Q) -> Option<usize>
+ where
+ Q: ?Sized + Equivalent<K>,
+ {
+ 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<V>)
+ where
+ K: Eq,
+ {
+ match self.get_index_of(hash, &key) {
+ Some(i) => (i, Some(replace(&mut self.entries[i].value, value))),
+ None => (self.push(hash, key, value), None),
+ }
+ }
+
+ /// Remove an entry by shifting all entries that follow it
+ pub(crate) fn shift_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)>
+ where
+ Q: ?Sized + Equivalent<K>,
+ {
+ 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<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)>
+ where
+ Q: ?Sized + Equivalent<K>,
+ {
+ 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<F>(&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<F>(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<F>(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<F>(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<K: fmt::Debug, V: fmt::Debug> 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<K, V> OccupiedEntry<'_, K, V> {
+ /// Sets the value of the entry to `value`, and returns the entry's old value.
+ pub fn insert(&mut self, value: V) -> V {
+ replace(self.get_mut(), value)
+ }
+
+ /// 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<K: fmt::Debug, V: fmt::Debug> 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<K, V>,
+ 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<K: fmt::Debug, V> 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<T: Send + Sync>() {}
+ assert_send_sync::<IndexMapCore<i32, i32>>();
+ assert_send_sync::<Entry<'_, i32, i32>>();
+}
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<usize>;
+
+/// Inserts many entries into a raw table without reallocating.
+///
+/// ***Panics*** if there is not sufficient capacity already.
+pub(super) fn insert_bulk_no_grow<K, V>(indices: &mut RawTable<usize>, entries: &[Bucket<K, V>]) {
+ 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<usize>);
+impl fmt::Debug for DebugIndices<'_> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ // SAFETY: we're not letting any of the buckets escape this function
+ let indices = unsafe { self.0.iter().map(|raw_bucket| raw_bucket.read()) };
+ f.debug_list().entries(indices).finish()
+ }
+}
+
+impl<K, V> IndexMapCore<K, V> {
+ /// 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<Item = &mut usize> {
+ // 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<K, V>,
+ raw_bucket: RawBucket,
+ key: K,
+}
+
+// `hashbrown::raw::Bucket` is only `Send`, not `Sync`.
+// SAFETY: `&self` only accesses the bucket to read it.
+unsafe impl<K: Sync, V: Sync> 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<Q: ?Sized>(
+ &mut self,
+ key: &Q,
+ ) -> Option<(usize, &mut Self::Key, &mut Self::Value)>
+ where
+ Q: Hash + Equivalent<Self::Key>;
+
+ /// 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<F>(&mut self, keep: F)
+ where
+ F: FnMut(&mut Self::Key, &mut Self::Value) -> bool;
+
+ /// This method is not useful in itself – it is there to “seal” the trait
+ /// for external implementation, so that we can add methods without
+ /// causing breaking changes.
+ fn __private_marker(&self) -> PrivateMarker;
+}
+
+/// Opt-in mutable access to keys.
+///
+/// See [`MutableKeys`](trait.MutableKeys.html) for more information.
+impl<K, V, S> MutableKeys for IndexMap<K, V, S>
+where
+ K: Eq + Hash,
+ S: BuildHasher,
+{
+ type Key = K;
+ type Value = V;
+ fn get_full_mut2<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &mut K, &mut V)>
+ where
+ Q: Hash + Equivalent<K>,
+ {
+ self.get_full_mut2_impl(key)
+ }
+
+ fn retain2<F>(&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<K, V, S> IntoParallelIterator for IndexMap<K, V, S>
+where
+ K: Send,
+ V: Send,
+{
+ type Item = (K, V);
+ type Iter = IntoParIter<K, V>;
+
+ fn into_par_iter(self) -> Self::Iter {
+ IntoParIter {
+ entries: self.into_entries(),
+ }
+ }
+}
+
+/// A parallel owning iterator over the entries of a `IndexMap`.
+///
+/// This `struct` is created by the [`into_par_iter`] method on [`IndexMap`]
+/// (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<K, V> {
+ entries: Vec<Bucket<K, V>>,
+}
+
+impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoParIter<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<K: Send, V: Send> ParallelIterator for IntoParIter<K, V> {
+ type Item = (K, V);
+
+ parallel_iterator_methods!(Bucket::key_value);
+}
+
+impl<K: Send, V: Send> IndexedParallelIterator for IntoParIter<K, V> {
+ indexed_parallel_iterator_methods!(Bucket::key_value);
+}
+
+/// Requires crate feature `"rayon"`.
+impl<'a, K, V, S> IntoParallelIterator for &'a IndexMap<K, V, S>
+where
+ K: Sync,
+ 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<K, V>],
+}
+
+impl<K, V> Clone for ParIter<'_, K, V> {
+ fn clone(&self) -> Self {
+ ParIter { ..*self }
+ }
+}
+
+impl<K: fmt::Debug, V: fmt::Debug> 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<K: Sync, V: Sync> IndexedParallelIterator for ParIter<'_, K, V> {
+ indexed_parallel_iterator_methods!(Bucket::refs);
+}
+
+/// Requires crate feature `"rayon"`.
+impl<'a, K, V, S> IntoParallelIterator for &'a mut IndexMap<K, V, S>
+where
+ K: Sync + Send,
+ 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<K, V>],
+}
+
+impl<K: fmt::Debug, V: fmt::Debug> 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<K: Sync + Send, V: Send> IndexedParallelIterator for ParIterMut<'_, K, V> {
+ indexed_parallel_iterator_methods!(Bucket::ref_mut);
+}
+
+/// Requires crate feature `"rayon"`.
+impl<'a, K, V, S> ParallelDrainRange<usize> for &'a mut IndexMap<K, V, S>
+where
+ K: Send,
+ V: Send,
+{
+ type Item = (K, V);
+ type Iter = ParDrain<'a, K, V>;
+
+ fn par_drain<R: RangeBounds<usize>>(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<K, V>>,
+}
+
+impl<K: Send, V: Send> ParallelIterator for ParDrain<'_, K, V> {
+ type Item = (K, V);
+
+ parallel_iterator_methods!(Bucket::key_value);
+}
+
+impl<K: Send, V: Send> 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<K, V, S> IndexMap<K, V, S>
+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<K, V, S> IndexMap<K, V, S>
+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<V2, S2>(&self, other: &IndexMap<K, V2, S2>) -> bool
+ where
+ V: PartialEq<V2>,
+ 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<K, V>],
+}
+
+impl<K, V> Clone for ParKeys<'_, K, V> {
+ fn clone(&self) -> Self {
+ ParKeys { ..*self }
+ }
+}
+
+impl<K: fmt::Debug, V> 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<K: Sync, V: Sync> 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<K, V>],
+}
+
+impl<K, V> Clone for ParValues<'_, K, V> {
+ fn clone(&self) -> Self {
+ ParValues { ..*self }
+ }
+}
+
+impl<K, V: fmt::Debug> 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<K: Sync, V: Sync> IndexedParallelIterator for ParValues<'_, K, V> {
+ indexed_parallel_iterator_methods!(Bucket::value_ref);
+}
+
+/// Requires crate feature `"rayon"`.
+impl<K, V, S> IndexMap<K, V, S>
+where
+ K: Send,
+ 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<K, V, S> IndexMap<K, V, S>
+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<F>(&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<F>(self, cmp: F) -> IntoParIter<K, V>
+ 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<F>(&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<F>(self, cmp: F) -> IntoParIter<K, V>
+ 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<K, V>],
+}
+
+impl<K, V: fmt::Debug> 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<K: Send, V: Send> IndexedParallelIterator for ParValuesMut<'_, K, V> {
+ indexed_parallel_iterator_methods!(Bucket::value_mut);
+}
+
+/// Requires crate feature `"rayon"`.
+impl<K, V, S> FromParallelIterator<(K, V)> for IndexMap<K, V, S>
+where
+ K: Eq + Hash + Send,
+ V: Send,
+ S: BuildHasher + Default + Send,
+{
+ fn from_par_iter<I>(iter: I) -> Self
+ where
+ I: IntoParallelIterator<Item = (K, V)>,
+ {
+ 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<K, V, S> ParallelExtend<(K, V)> for IndexMap<K, V, S>
+where
+ K: Eq + Hash + Send,
+ V: Send,
+ S: BuildHasher + Send,
+{
+ fn par_extend<I>(&mut self, iter: I)
+ where
+ I: IntoParallelIterator<Item = (K, V)>,
+ {
+ 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<K, V, S>
+where
+ K: Copy + Eq + Hash + Send + Sync,
+ V: Copy + Send + Sync,
+ S: BuildHasher + Send,
+{
+ fn par_extend<I>(&mut self, iter: I)
+ where
+ I: IntoParallelIterator<Item = (&'a K, &'a V)>,
+ {
+ 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<_>>(),
+ 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<I: IntoParallelIterator>(iter: I) -> LinkedList<Vec<I::Item>> {
+ 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<T> = crate::Bucket<T, ()>;
+
+/// Requires crate feature `"rayon"`.
+impl<T, S> IntoParallelIterator for IndexSet<T, S>
+where
+ T: Send,
+{
+ type Item = T;
+ type Iter = IntoParIter<T>;
+
+ fn into_par_iter(self) -> Self::Iter {
+ IntoParIter {
+ entries: self.into_entries(),
+ }
+ }
+}
+
+/// A parallel owning iterator over the items of a `IndexSet`.
+///
+/// This `struct` is created by the [`into_par_iter`] method on [`IndexSet`]
+/// (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<T> {
+ entries: Vec<Bucket<T>>,
+}
+
+impl<T: fmt::Debug> fmt::Debug for IntoParIter<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<T: Send> ParallelIterator for IntoParIter<T> {
+ type Item = T;
+
+ parallel_iterator_methods!(Bucket::key);
+}
+
+impl<T: Send> IndexedParallelIterator for IntoParIter<T> {
+ indexed_parallel_iterator_methods!(Bucket::key);
+}
+
+/// Requires crate feature `"rayon"`.
+impl<'a, T, S> IntoParallelIterator for &'a IndexSet<T, S>
+where
+ T: Sync,
+{
+ 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<T>],
+}
+
+impl<T> Clone for ParIter<'_, T> {
+ fn clone(&self) -> Self {
+ ParIter { ..*self }
+ }
+}
+
+impl<T: fmt::Debug> 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<T: Sync> IndexedParallelIterator for ParIter<'_, T> {
+ indexed_parallel_iterator_methods!(Bucket::key_ref);
+}
+
+/// Requires crate feature `"rayon"`.
+impl<'a, T, S> ParallelDrainRange<usize> for &'a mut IndexSet<T, S>
+where
+ T: Send,
+{
+ type Item = T;
+ type Iter = ParDrain<'a, T>;
+
+ fn par_drain<R: RangeBounds<usize>>(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<T>>,
+}
+
+impl<T: Send> ParallelIterator for ParDrain<'_, T> {
+ type Item = T;
+
+ parallel_iterator_methods!(Bucket::key);
+}
+
+impl<T: Send> 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<T, S> IndexSet<T, S>
+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<T, S2>,
+ ) -> 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<T, S2>,
+ ) -> 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<T, S2>,
+ ) -> 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<T, S2>) -> 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<S2>(&self, other: &IndexSet<T, S2>) -> 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<S2>(&self, other: &IndexSet<T, S2>) -> 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<S2>(&self, other: &IndexSet<T, S2>) -> 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<S2>(&self, other: &IndexSet<T, S2>) -> 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<T, S1>,
+ set2: &'a IndexSet<T, S2>,
+}
+
+impl<T, S1, S2> Clone for ParDifference<'_, T, S1, S2> {
+ fn clone(&self) -> Self {
+ ParDifference { ..*self }
+ }
+}
+
+impl<T, S1, S2> 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<C>(self, consumer: C) -> C::Result
+ where
+ C: UnindexedConsumer<Self::Item>,
+ {
+ 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<T, S1>,
+ set2: &'a IndexSet<T, S2>,
+}
+
+impl<T, S1, S2> Clone for ParIntersection<'_, T, S1, S2> {
+ fn clone(&self) -> Self {
+ ParIntersection { ..*self }
+ }
+}
+
+impl<T, S1, S2> 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<C>(self, consumer: C) -> C::Result
+ where
+ C: UnindexedConsumer<Self::Item>,
+ {
+ 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<T, S1>,
+ set2: &'a IndexSet<T, S2>,
+}
+
+impl<T, S1, S2> Clone for ParSymmetricDifference<'_, T, S1, S2> {
+ fn clone(&self) -> Self {
+ ParSymmetricDifference { ..*self }
+ }
+}
+
+impl<T, S1, S2> 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<C>(self, consumer: C) -> C::Result
+ where
+ C: UnindexedConsumer<Self::Item>,
+ {
+ 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<T, S1>,
+ set2: &'a IndexSet<T, S2>,
+}
+
+impl<T, S1, S2> Clone for ParUnion<'_, T, S1, S2> {
+ fn clone(&self) -> Self {
+ ParUnion { ..*self }
+ }
+}
+
+impl<T, S1, S2> 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<C>(self, consumer: C) -> C::Result
+ where
+ C: UnindexedConsumer<Self::Item>,
+ {
+ 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<T, S> IndexSet<T, S>
+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<F>(&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<F>(self, cmp: F) -> IntoParIter<T>
+ 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<F>(&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<F>(self, cmp: F) -> IntoParIter<T>
+ 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<T, S> FromParallelIterator<T> for IndexSet<T, S>
+where
+ T: Eq + Hash + Send,
+ S: BuildHasher + Default + Send,
+{
+ fn from_par_iter<I>(iter: I) -> Self
+ where
+ I: IntoParallelIterator<Item = T>,
+ {
+ 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<T, S> ParallelExtend<T> for IndexSet<T, S>
+where
+ T: Eq + Hash + Send,
+ S: BuildHasher + Send,
+{
+ fn par_extend<I>(&mut self, iter: I)
+ where
+ I: IntoParallelIterator<Item = T>,
+ {
+ for vec in collect(iter) {
+ self.extend(vec);
+ }
+ }
+}
+
+/// Requires crate feature `"rayon"`.
+impl<'a, T: 'a, S> ParallelExtend<&'a T> for IndexSet<T, S>
+where
+ T: Copy + Eq + Hash + Send + Sync,
+ S: BuildHasher + Send,
+{
+ fn par_extend<I>(&mut self, iter: I)
+ where
+ I: IntoParallelIterator<Item = &'a T>,
+ {
+ 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<_>>(),
+ 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<Item = &'a i32>,
+ I2: Iterator<Item = i32>,
+ {
+ 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<K, V, S> IntoParallelIterator for IndexMap<K, V, S>
+ where
+ K: Send,
+ V: Send,
+ {
+ type Item = (K, V);
+ type Iter = IntoParIter<K, V>;
+
+ fn into_par_iter(self) -> Self::Iter {
+ IntoParIter {
+ entries: self.into_entries(),
+ }
+ }
+ }
+
+ pub struct IntoParIter<K, V> {
+ entries: Vec<Bucket<K, V>>,
+ }
+
+ impl<K: Send, V: Send> ParallelIterator for IntoParIter<K, V> {
+ type Item = (K, V);
+
+ parallel_iterator_methods!(Bucket::key_value);
+ }
+
+ impl<K: Send, V: Send> IndexedParallelIterator for IntoParIter<K, V> {
+ indexed_parallel_iterator_methods!(Bucket::key_value);
+ }
+
+ impl<'a, K, V, S> IntoParallelIterator for &'a IndexMap<K, V, S>
+ 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<K, V>],
+ }
+
+ impl<'a, K: Sync, V: Sync> ParallelIterator for ParIter<'a, K, V> {
+ type Item = (&'a K, &'a V);
+
+ parallel_iterator_methods!(Bucket::refs);
+ }
+
+ impl<K: Sync, V: Sync> IndexedParallelIterator for ParIter<'_, K, V> {
+ indexed_parallel_iterator_methods!(Bucket::refs);
+ }
+
+ impl<'a, K, V, S> IntoParallelIterator for &'a mut IndexMap<K, V, S>
+ 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<K, V>],
+ }
+
+ 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<K: Sync + Send, V: Send> IndexedParallelIterator for ParIterMut<'_, K, V> {
+ indexed_parallel_iterator_methods!(Bucket::ref_mut);
+ }
+}
+
+mod set {
+ use super::*;
+
+ impl<T, S> IntoParallelIterator for IndexSet<T, S>
+ where
+ T: Send,
+ {
+ type Item = T;
+ type Iter = IntoParIter<T>;
+
+ fn into_par_iter(self) -> Self::Iter {
+ IntoParIter {
+ entries: self.into_entries(),
+ }
+ }
+ }
+
+ pub struct IntoParIter<T> {
+ entries: Vec<Bucket<T, ()>>,
+ }
+
+ impl<T: Send> ParallelIterator for IntoParIter<T> {
+ type Item = T;
+
+ parallel_iterator_methods!(Bucket::key);
+ }
+
+ impl<T: Send> IndexedParallelIterator for IntoParIter<T> {
+ indexed_parallel_iterator_methods!(Bucket::key);
+ }
+
+ impl<'a, T, S> IntoParallelIterator for &'a IndexSet<T, S>
+ 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<T, ()>],
+ }
+
+ impl<'a, T: Sync> ParallelIterator for ParIter<'a, T> {
+ type Item = &'a T;
+
+ parallel_iterator_methods!(Bucket::key_ref);
+ }
+
+ impl<T: Sync> 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<K, V, S> Serialize for IndexMap<K, V, S>
+where
+ K: Serialize + Hash + Eq,
+ V: Serialize,
+ S: BuildHasher,
+{
+ fn serialize<T>(&self, serializer: T) -> Result<T::Ok, T::Error>
+ where
+ T: Serializer,
+ {
+ serializer.collect_map(self)
+ }
+}
+
+struct IndexMapVisitor<K, V, S>(PhantomData<(K, V, S)>);
+
+impl<'de, K, V, S> Visitor<'de> for IndexMapVisitor<K, V, S>
+where
+ K: Deserialize<'de> + Eq + Hash,
+ V: Deserialize<'de>,
+ S: Default + BuildHasher,
+{
+ type Value = IndexMap<K, V, S>;
+
+ fn expecting(&self, formatter: &mut Formatter<'_>) -> fmt::Result {
+ write!(formatter, "a map")
+ }
+
+ fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
+ 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<K, V, S>
+where
+ K: Deserialize<'de> + Eq + Hash,
+ V: Deserialize<'de>,
+ S: Default + BuildHasher,
+{
+ fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+ where
+ D: Deserializer<'de>,
+ {
+ deserializer.deserialize_map(IndexMapVisitor(PhantomData))
+ }
+}
+
+impl<'de, K, V, S, E> IntoDeserializer<'de, E> for IndexMap<K, V, S>
+where
+ K: IntoDeserializer<'de, E> + Eq + Hash,
+ V: IntoDeserializer<'de, E>,
+ S: BuildHasher,
+ E: Error,
+{
+ type Deserializer = MapDeserializer<'de, <Self as IntoIterator>::IntoIter, E>;
+
+ fn into_deserializer(self) -> Self::Deserializer {
+ MapDeserializer::new(self.into_iter())
+ }
+}
+
+use crate::IndexSet;
+
+/// Requires crate feature `"serde"` or `"serde-1"`
+impl<T, S> Serialize for IndexSet<T, S>
+where
+ T: Serialize + Hash + Eq,
+ S: BuildHasher,
+{
+ fn serialize<Se>(&self, serializer: Se) -> Result<Se::Ok, Se::Error>
+ where
+ Se: Serializer,
+ {
+ serializer.collect_seq(self)
+ }
+}
+
+struct IndexSetVisitor<T, S>(PhantomData<(T, S)>);
+
+impl<'de, T, S> Visitor<'de> for IndexSetVisitor<T, S>
+where
+ T: Deserialize<'de> + Eq + Hash,
+ S: Default + BuildHasher,
+{
+ type Value = IndexSet<T, S>;
+
+ fn expecting(&self, formatter: &mut Formatter<'_>) -> fmt::Result {
+ write!(formatter, "a set")
+ }
+
+ fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
+ 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<T, S>
+where
+ T: Deserialize<'de> + Eq + Hash,
+ S: Default + BuildHasher,
+{
+ fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+ where
+ D: Deserializer<'de>,
+ {
+ deserializer.deserialize_seq(IndexSetVisitor(PhantomData))
+ }
+}
+
+impl<'de, T, S, E> IntoDeserializer<'de, E> for IndexSet<T, S>
+where
+ T: IntoDeserializer<'de, E> + Eq + Hash,
+ S: BuildHasher,
+ E: Error,
+{
+ type Deserializer = SeqDeserializer<<Self as IntoIterator>::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<i32, u64>,
+//! // ...
+//! }
+//! ```
+//!
+//! 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<i32, u64>,
+/// // ...
+/// }
+/// ```
+///
+/// Requires crate feature `"serde"` or `"serde-1"`
+pub fn serialize<K, V, S, T>(map: &IndexMap<K, V, S>, serializer: T) -> Result<T::Ok, T::Error>
+where
+ K: Serialize + Hash + Eq,
+ V: Serialize,
+ S: BuildHasher,
+ T: Serializer,
+{
+ serializer.collect_seq(map)
+}
+
+/// Visitor to deserialize a *sequenced* `IndexMap`
+struct SeqVisitor<K, V, S>(PhantomData<(K, V, S)>);
+
+impl<'de, K, V, S> Visitor<'de> for SeqVisitor<K, V, S>
+where
+ K: Deserialize<'de> + Eq + Hash,
+ V: Deserialize<'de>,
+ S: Default + BuildHasher,
+{
+ type Value = IndexMap<K, V, S>;
+
+ fn expecting(&self, formatter: &mut Formatter<'_>) -> fmt::Result {
+ write!(formatter, "a sequenced map")
+ }
+
+ fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
+ 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<i32, u64>,
+/// // ...
+/// }
+/// ```
+///
+/// Requires crate feature `"serde"` or `"serde-1"`
+pub fn deserialize<'de, D, K, V, S>(deserializer: D) -> Result<IndexMap<K, V, S>, D::Error>
+where
+ D: Deserializer<'de>,
+ 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<T> = super::Bucket<T, ()>;
+
+/// 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<T, S = RandomState> {
+ pub(crate) map: IndexMap<T, (), S>,
+}
+#[cfg(not(has_std))]
+pub struct IndexSet<T, S> {
+ pub(crate) map: IndexMap<T, (), S>,
+}
+
+impl<T, S> Clone for IndexSet<T, S>
+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<T, S> Entries for IndexSet<T, S> {
+ type Entry = Bucket<T>;
+
+ #[inline]
+ fn into_entries(self) -> Vec<Self::Entry> {
+ 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<F>(&mut self, f: F)
+ where
+ F: FnOnce(&mut [Self::Entry]),
+ {
+ self.map.with_entries(f);
+ }
+}
+
+impl<T, S> fmt::Debug for IndexSet<T, S>
+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<T> IndexSet<T> {
+ /// 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<T, S> IndexSet<T, S> {
+ /// 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<usize>`,
+ /// 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<R>(&mut self, range: R) -> Drain<'_, T>
+ where
+ R: RangeBounds<usize>,
+ {
+ 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<T, S> IndexSet<T, S>
+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<T, S2>) -> 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<T, S2>,
+ ) -> 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<T, S2>) -> 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<T, S2>) -> 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<Q: ?Sized>(&self, value: &Q) -> bool
+ where
+ Q: Hash + Equivalent<T>,
+ {
+ 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<Q: ?Sized>(&self, value: &Q) -> Option<&T>
+ where
+ Q: Hash + Equivalent<T>,
+ {
+ self.map.get_key_value(value).map(|(x, &())| x)
+ }
+
+ /// Return item index and value
+ pub fn get_full<Q: ?Sized>(&self, value: &Q) -> Option<(usize, &T)>
+ where
+ Q: Hash + Equivalent<T>,
+ {
+ self.map.get_full(value).map(|(i, x, &())| (i, x))
+ }
+
+ /// Return item index, if it exists in the set
+ pub fn get_index_of<Q: ?Sized>(&self, value: &Q) -> Option<usize>
+ where
+ Q: Hash + Equivalent<T>,
+ {
+ 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<T> {
+ 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<T>) {
+ 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<Q: ?Sized>(&mut self, value: &Q) -> bool
+ where
+ Q: Hash + Equivalent<T>,
+ {
+ 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<Q: ?Sized>(&mut self, value: &Q) -> bool
+ where
+ Q: Hash + Equivalent<T>,
+ {
+ 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<Q: ?Sized>(&mut self, value: &Q) -> bool
+ where
+ Q: Hash + Equivalent<T>,
+ {
+ 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<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
+ where
+ Q: Hash + Equivalent<T>,
+ {
+ 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<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
+ where
+ Q: Hash + Equivalent<T>,
+ {
+ 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<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
+ where
+ Q: Hash + Equivalent<T>,
+ {
+ 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<Q: ?Sized>(&mut self, value: &Q) -> Option<(usize, T)>
+ where
+ Q: Hash + Equivalent<T>,
+ {
+ 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<Q: ?Sized>(&mut self, value: &Q) -> Option<(usize, T)>
+ where
+ Q: Hash + Equivalent<T>,
+ {
+ 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<T> {
+ 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<F>(&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<F>(&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<F>(self, mut cmp: F) -> IntoIter<T>
+ 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<F>(&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<F>(self, mut cmp: F) -> IntoIter<T>
+ 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<T, S> IndexSet<T, S> {
+ /// 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<T> {
+ 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<T> {
+ 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<T, S> Index<usize> for IndexSet<T, S> {
+ 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<T> {
+ iter: vec::IntoIter<Bucket<T>>,
+}
+
+impl<T> Iterator for IntoIter<T> {
+ type Item = T;
+
+ iterator_methods!(Bucket::key);
+}
+
+impl<T> DoubleEndedIterator for IntoIter<T> {
+ double_ended_iterator_methods!(Bucket::key);
+}
+
+impl<T> ExactSizeIterator for IntoIter<T> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<T> FusedIterator for IntoIter<T> {}
+
+impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
+ f.debug_list().entries(iter).finish()
+ }
+}
+
+/// An iterator over the items of a `IndexSet`.
+///
+/// This `struct` is created by the [`iter`] method on [`IndexSet`].
+/// See its documentation for more.
+///
+/// [`IndexSet`]: struct.IndexSet.html
+/// [`iter`]: struct.IndexSet.html#method.iter
+pub struct Iter<'a, T> {
+ iter: slice::Iter<'a, Bucket<T>>,
+}
+
+impl<'a, T> Iterator for Iter<'a, T> {
+ type Item = &'a T;
+
+ iterator_methods!(Bucket::key_ref);
+}
+
+impl<T> DoubleEndedIterator for Iter<'_, T> {
+ double_ended_iterator_methods!(Bucket::key_ref);
+}
+
+impl<T> ExactSizeIterator for Iter<'_, T> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<T> FusedIterator for Iter<'_, T> {}
+
+impl<T> Clone for Iter<'_, T> {
+ fn clone(&self) -> Self {
+ Iter {
+ iter: self.iter.clone(),
+ }
+ }
+}
+
+impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+/// A draining iterator over the items of a `IndexSet`.
+///
+/// This `struct` is created by the [`drain`] method on [`IndexSet`].
+/// See its documentation for more.
+///
+/// [`IndexSet`]: struct.IndexSet.html
+/// [`drain`]: struct.IndexSet.html#method.drain
+pub struct Drain<'a, T> {
+ iter: vec::Drain<'a, Bucket<T>>,
+}
+
+impl<T> Iterator for Drain<'_, T> {
+ type Item = T;
+
+ iterator_methods!(Bucket::key);
+}
+
+impl<T> DoubleEndedIterator for Drain<'_, T> {
+ double_ended_iterator_methods!(Bucket::key);
+}
+
+impl<T> ExactSizeIterator for Drain<'_, T> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<T> FusedIterator for Drain<'_, T> {}
+
+impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
+ f.debug_list().entries(iter).finish()
+ }
+}
+
+impl<'a, T, S> IntoIterator for &'a IndexSet<T, S> {
+ type Item = &'a T;
+ type IntoIter = Iter<'a, T>;
+
+ fn into_iter(self) -> Self::IntoIter {
+ self.iter()
+ }
+}
+
+impl<T, S> IntoIterator for IndexSet<T, S> {
+ type Item = T;
+ type IntoIter = IntoIter<T>;
+
+ fn into_iter(self) -> Self::IntoIter {
+ IntoIter {
+ iter: self.into_entries().into_iter(),
+ }
+ }
+}
+
+impl<T, S> FromIterator<T> for IndexSet<T, S>
+where
+ T: Hash + Eq,
+ S: BuildHasher + Default,
+{
+ fn from_iter<I: IntoIterator<Item = T>>(iterable: I) -> Self {
+ let iter = iterable.into_iter().map(|x| (x, ()));
+ IndexSet {
+ map: IndexMap::from_iter(iter),
+ }
+ }
+}
+
+#[cfg(has_std)]
+impl<T, const N: usize> From<[T; N]> for IndexSet<T, RandomState>
+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<T, S> Extend<T> for IndexSet<T, S>
+where
+ T: Hash + Eq,
+ S: BuildHasher,
+{
+ fn extend<I: IntoIterator<Item = T>>(&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<T, S>
+where
+ T: Hash + Eq + Copy + 'a,
+ S: BuildHasher,
+{
+ fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iterable: I) {
+ let iter = iterable.into_iter().copied();
+ self.extend(iter);
+ }
+}
+
+impl<T, S> Default for IndexSet<T, S>
+where
+ S: Default,
+{
+ /// Return an empty `IndexSet`
+ fn default() -> Self {
+ IndexSet {
+ map: IndexMap::default(),
+ }
+ }
+}
+
+impl<T, S1, S2> PartialEq<IndexSet<T, S2>> for IndexSet<T, S1>
+where
+ T: Hash + Eq,
+ S1: BuildHasher,
+ S2: BuildHasher,
+{
+ fn eq(&self, other: &IndexSet<T, S2>) -> bool {
+ self.len() == other.len() && self.is_subset(other)
+ }
+}
+
+impl<T, S> Eq for IndexSet<T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+}
+
+impl<T, S> IndexSet<T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ /// Returns `true` if `self` has no elements in common with `other`.
+ pub fn is_disjoint<S2>(&self, other: &IndexSet<T, S2>) -> 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<S2>(&self, other: &IndexSet<T, S2>) -> 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<S2>(&self, other: &IndexSet<T, S2>) -> 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<T, S>,
+}
+
+impl<'a, T, S> Iterator for Difference<'a, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ type Item = &'a T;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ while let Some(item) = self.iter.next() {
+ if !self.other.contains(item) {
+ return Some(item);
+ }
+ }
+ None
+ }
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (0, self.iter.size_hint().1)
+ }
+}
+
+impl<T, S> DoubleEndedIterator for Difference<'_, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ fn next_back(&mut self) -> Option<Self::Item> {
+ while let Some(item) = self.iter.next_back() {
+ if !self.other.contains(item) {
+ return Some(item);
+ }
+ }
+ None
+ }
+}
+
+impl<T, S> FusedIterator for Difference<'_, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+}
+
+impl<T, S> Clone for Difference<'_, T, S> {
+ fn clone(&self) -> Self {
+ Difference {
+ iter: self.iter.clone(),
+ ..*self
+ }
+ }
+}
+
+impl<T, S> fmt::Debug for Difference<'_, T, S>
+where
+ T: fmt::Debug + Eq + Hash,
+ S: BuildHasher,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+/// A lazy iterator producing elements in the intersection of `IndexSet`s.
+///
+/// This `struct` is created by the [`intersection`] method on [`IndexSet`].
+/// See its documentation for more.
+///
+/// [`IndexSet`]: struct.IndexSet.html
+/// [`intersection`]: struct.IndexSet.html#method.intersection
+pub struct Intersection<'a, T, S> {
+ iter: Iter<'a, T>,
+ other: &'a IndexSet<T, S>,
+}
+
+impl<'a, T, S> Iterator for Intersection<'a, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ type Item = &'a T;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ while let Some(item) = self.iter.next() {
+ if self.other.contains(item) {
+ return Some(item);
+ }
+ }
+ None
+ }
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (0, self.iter.size_hint().1)
+ }
+}
+
+impl<T, S> DoubleEndedIterator for Intersection<'_, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ fn next_back(&mut self) -> Option<Self::Item> {
+ while let Some(item) = self.iter.next_back() {
+ if self.other.contains(item) {
+ return Some(item);
+ }
+ }
+ None
+ }
+}
+
+impl<T, S> FusedIterator for Intersection<'_, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+}
+
+impl<T, S> Clone for Intersection<'_, T, S> {
+ fn clone(&self) -> Self {
+ Intersection {
+ iter: self.iter.clone(),
+ ..*self
+ }
+ }
+}
+
+impl<T, S> fmt::Debug for Intersection<'_, T, S>
+where
+ T: fmt::Debug + Eq + Hash,
+ S: BuildHasher,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+/// A lazy iterator producing elements in the symmetric difference of `IndexSet`s.
+///
+/// This `struct` is created by the [`symmetric_difference`] method on
+/// [`IndexSet`]. See its documentation for more.
+///
+/// [`IndexSet`]: struct.IndexSet.html
+/// [`symmetric_difference`]: struct.IndexSet.html#method.symmetric_difference
+pub struct SymmetricDifference<'a, T, S1, S2> {
+ iter: Chain<Difference<'a, T, S2>, Difference<'a, T, S1>>,
+}
+
+impl<'a, T, S1, S2> Iterator for SymmetricDifference<'a, T, S1, S2>
+where
+ T: Eq + Hash,
+ S1: BuildHasher,
+ S2: BuildHasher,
+{
+ type Item = &'a T;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ self.iter.next()
+ }
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.iter.size_hint()
+ }
+
+ fn fold<B, F>(self, init: B, f: F) -> B
+ where
+ F: FnMut(B, Self::Item) -> B,
+ {
+ self.iter.fold(init, f)
+ }
+}
+
+impl<T, S1, S2> DoubleEndedIterator for SymmetricDifference<'_, T, S1, S2>
+where
+ T: Eq + Hash,
+ S1: BuildHasher,
+ S2: BuildHasher,
+{
+ fn next_back(&mut self) -> Option<Self::Item> {
+ self.iter.next_back()
+ }
+
+ fn rfold<B, F>(self, init: B, f: F) -> B
+ where
+ F: FnMut(B, Self::Item) -> B,
+ {
+ self.iter.rfold(init, f)
+ }
+}
+
+impl<T, S1, S2> FusedIterator for SymmetricDifference<'_, T, S1, S2>
+where
+ T: Eq + Hash,
+ S1: BuildHasher,
+ S2: BuildHasher,
+{
+}
+
+impl<T, S1, S2> Clone for SymmetricDifference<'_, T, S1, S2> {
+ fn clone(&self) -> Self {
+ SymmetricDifference {
+ iter: self.iter.clone(),
+ }
+ }
+}
+
+impl<T, S1, S2> fmt::Debug for SymmetricDifference<'_, T, S1, S2>
+where
+ T: fmt::Debug + Eq + Hash,
+ S1: BuildHasher,
+ S2: BuildHasher,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+/// A lazy iterator producing elements in the union of `IndexSet`s.
+///
+/// This `struct` is created by the [`union`] method on [`IndexSet`].
+/// See its documentation for more.
+///
+/// [`IndexSet`]: struct.IndexSet.html
+/// [`union`]: struct.IndexSet.html#method.union
+pub struct Union<'a, T, S> {
+ iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
+}
+
+impl<'a, T, S> Iterator for Union<'a, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ type Item = &'a T;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ self.iter.next()
+ }
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.iter.size_hint()
+ }
+
+ fn fold<B, F>(self, init: B, f: F) -> B
+ where
+ F: FnMut(B, Self::Item) -> B,
+ {
+ self.iter.fold(init, f)
+ }
+}
+
+impl<T, S> DoubleEndedIterator for Union<'_, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ fn next_back(&mut self) -> Option<Self::Item> {
+ self.iter.next_back()
+ }
+
+ fn rfold<B, F>(self, init: B, f: F) -> B
+ where
+ F: FnMut(B, Self::Item) -> B,
+ {
+ self.iter.rfold(init, f)
+ }
+}
+
+impl<T, S> FusedIterator for Union<'_, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+}
+
+impl<T, S> Clone for Union<'_, T, S> {
+ fn clone(&self) -> Self {
+ Union {
+ iter: self.iter.clone(),
+ }
+ }
+}
+
+impl<T, S> fmt::Debug for Union<'_, T, S>
+where
+ T: fmt::Debug + Eq + Hash,
+ S: BuildHasher,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+impl<T, S1, S2> BitAnd<&IndexSet<T, S2>> for &IndexSet<T, S1>
+where
+ T: Eq + Hash + Clone,
+ S1: BuildHasher + Default,
+ S2: BuildHasher,
+{
+ type Output = IndexSet<T, S1>;
+
+ /// 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<T, S2>) -> Self::Output {
+ self.intersection(other).cloned().collect()
+ }
+}
+
+impl<T, S1, S2> BitOr<&IndexSet<T, S2>> for &IndexSet<T, S1>
+where
+ T: Eq + Hash + Clone,
+ S1: BuildHasher + Default,
+ S2: BuildHasher,
+{
+ type Output = IndexSet<T, S1>;
+
+ /// 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<T, S2>) -> Self::Output {
+ self.union(other).cloned().collect()
+ }
+}
+
+impl<T, S1, S2> BitXor<&IndexSet<T, S2>> for &IndexSet<T, S1>
+where
+ T: Eq + Hash + Clone,
+ S1: BuildHasher + Default,
+ S2: BuildHasher,
+{
+ type Output = IndexSet<T, S1>;
+
+ /// 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<T, S2>) -> Self::Output {
+ self.symmetric_difference(other).cloned().collect()
+ }
+}
+
+impl<T, S1, S2> Sub<&IndexSet<T, S2>> for &IndexSet<T, S1>
+where
+ T: Eq + Hash + Clone,
+ S1: BuildHasher + Default,
+ S2: BuildHasher,
+{
+ type Output = IndexSet<T, S1>;
+
+ /// 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<T, S2>) -> 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::<String>::new();
+ println!("{:?}", set);
+ assert_eq!(set.capacity(), 0);
+ assert_eq!(set.len(), 0);
+ assert_eq!(set.is_empty(), true);
+ }
+
+ #[test]
+ fn insert() {
+ let insert = [0, 4, 2, 12, 8, 7, 11, 5];
+ let not_present = [1, 3, 6, 9, 10];
+ let mut set = IndexSet::with_capacity(insert.len());
+
+ for (i, &elt) in insert.iter().enumerate() {
+ assert_eq!(set.len(), i);
+ set.insert(elt);
+ assert_eq!(set.len(), i + 1);
+ assert_eq!(set.get(&elt), Some(&elt));
+ }
+ println!("{:?}", set);
+
+ for &elt in &not_present {
+ assert!(set.get(&elt).is_none());
+ }
+ }
+
+ #[test]
+ fn insert_full() {
+ let insert = vec![9, 2, 7, 1, 4, 6, 13];
+ let present = vec![1, 6, 2];
+ let mut set = IndexSet::with_capacity(insert.len());
+
+ for (i, &elt) in insert.iter().enumerate() {
+ assert_eq!(set.len(), i);
+ let (index, success) = set.insert_full(elt);
+ assert!(success);
+ assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0));
+ assert_eq!(set.len(), i + 1);
+ }
+
+ let len = set.len();
+ for &elt in &present {
+ let (index, success) = set.insert_full(elt);
+ assert!(!success);
+ assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0));
+ assert_eq!(set.len(), len);
+ }
+ }
+
+ #[test]
+ fn insert_2() {
+ let mut set = IndexSet::with_capacity(16);
+
+ let mut values = vec![];
+ values.extend(0..16);
+ values.extend(if cfg!(miri) { 32..64 } else { 128..267 });
+
+ for &i in &values {
+ let old_set = set.clone();
+ set.insert(i);
+ for value in old_set.iter() {
+ if set.get(value).is_none() {
+ println!("old_set: {:?}", old_set);
+ println!("set: {:?}", set);
+ panic!("did not find {} in set", value);
+ }
+ }
+ }
+
+ for &i in &values {
+ assert!(set.get(&i).is_some(), "did not find {}", i);
+ }
+ }
+
+ #[test]
+ fn insert_dup() {
+ let mut elements = vec![0, 2, 4, 6, 8];
+ let mut set: IndexSet<u8> = elements.drain(..).collect();
+ {
+ let (i, v) = set.get_full(&0).unwrap();
+ assert_eq!(set.len(), 5);
+ assert_eq!(i, 0);
+ assert_eq!(*v, 0);
+ }
+ {
+ let inserted = set.insert(0);
+ let (i, v) = set.get_full(&0).unwrap();
+ assert_eq!(set.len(), 5);
+ assert_eq!(inserted, false);
+ assert_eq!(i, 0);
+ assert_eq!(*v, 0);
+ }
+ }
+
+ #[test]
+ fn insert_order() {
+ let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
+ let mut set = IndexSet::new();
+
+ for &elt in &insert {
+ set.insert(elt);
+ }
+
+ assert_eq!(set.iter().count(), set.len());
+ assert_eq!(set.iter().count(), insert.len());
+ for (a, b) in insert.iter().zip(set.iter()) {
+ assert_eq!(a, b);
+ }
+ for (i, v) in (0..insert.len()).zip(set.iter()) {
+ assert_eq!(set.get_index(i).unwrap(), v);
+ }
+ }
+
+ #[test]
+ fn replace() {
+ let replace = [0, 4, 2, 12, 8, 7, 11, 5];
+ let not_present = [1, 3, 6, 9, 10];
+ let mut set = IndexSet::with_capacity(replace.len());
+
+ for (i, &elt) in replace.iter().enumerate() {
+ assert_eq!(set.len(), i);
+ set.replace(elt);
+ assert_eq!(set.len(), i + 1);
+ assert_eq!(set.get(&elt), Some(&elt));
+ }
+ println!("{:?}", set);
+
+ for &elt in &not_present {
+ assert!(set.get(&elt).is_none());
+ }
+ }
+
+ #[test]
+ fn replace_full() {
+ let replace = vec![9, 2, 7, 1, 4, 6, 13];
+ let present = vec![1, 6, 2];
+ let mut set = IndexSet::with_capacity(replace.len());
+
+ for (i, &elt) in replace.iter().enumerate() {
+ assert_eq!(set.len(), i);
+ let (index, replaced) = set.replace_full(elt);
+ assert!(replaced.is_none());
+ assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0));
+ assert_eq!(set.len(), i + 1);
+ }
+
+ let len = set.len();
+ for &elt in &present {
+ let (index, replaced) = set.replace_full(elt);
+ assert_eq!(Some(elt), replaced);
+ assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0));
+ assert_eq!(set.len(), len);
+ }
+ }
+
+ #[test]
+ fn replace_2() {
+ let mut set = IndexSet::with_capacity(16);
+
+ let mut values = vec![];
+ values.extend(0..16);
+ values.extend(if cfg!(miri) { 32..64 } else { 128..267 });
+
+ for &i in &values {
+ let old_set = set.clone();
+ set.replace(i);
+ for value in old_set.iter() {
+ if set.get(value).is_none() {
+ println!("old_set: {:?}", old_set);
+ println!("set: {:?}", set);
+ panic!("did not find {} in set", value);
+ }
+ }
+ }
+
+ for &i in &values {
+ assert!(set.get(&i).is_some(), "did not find {}", i);
+ }
+ }
+
+ #[test]
+ fn replace_dup() {
+ let mut elements = vec![0, 2, 4, 6, 8];
+ let mut set: IndexSet<u8> = elements.drain(..).collect();
+ {
+ let (i, v) = set.get_full(&0).unwrap();
+ assert_eq!(set.len(), 5);
+ assert_eq!(i, 0);
+ assert_eq!(*v, 0);
+ }
+ {
+ let replaced = set.replace(0);
+ let (i, v) = set.get_full(&0).unwrap();
+ assert_eq!(set.len(), 5);
+ assert_eq!(replaced, Some(0));
+ assert_eq!(i, 0);
+ assert_eq!(*v, 0);
+ }
+ }
+
+ #[test]
+ fn replace_order() {
+ let replace = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
+ let mut set = IndexSet::new();
+
+ for &elt in &replace {
+ set.replace(elt);
+ }
+
+ assert_eq!(set.iter().count(), set.len());
+ assert_eq!(set.iter().count(), replace.len());
+ for (a, b) in replace.iter().zip(set.iter()) {
+ assert_eq!(a, b);
+ }
+ for (i, v) in (0..replace.len()).zip(set.iter()) {
+ assert_eq!(set.get_index(i).unwrap(), v);
+ }
+ }
+
+ #[test]
+ fn grow() {
+ let insert = [0, 4, 2, 12, 8, 7, 11];
+ let not_present = [1, 3, 6, 9, 10];
+ let mut set = IndexSet::with_capacity(insert.len());
+
+ for (i, &elt) in insert.iter().enumerate() {
+ assert_eq!(set.len(), i);
+ set.insert(elt);
+ assert_eq!(set.len(), i + 1);
+ assert_eq!(set.get(&elt), Some(&elt));
+ }
+
+ println!("{:?}", set);
+ for &elt in &insert {
+ set.insert(elt * 10);
+ }
+ for &elt in &insert {
+ set.insert(elt * 100);
+ }
+ for (i, &elt) in insert.iter().cycle().enumerate().take(100) {
+ set.insert(elt * 100 + i as i32);
+ }
+ println!("{:?}", set);
+ for &elt in &not_present {
+ assert!(set.get(&elt).is_none());
+ }
+ }
+
+ #[test]
+ fn reserve() {
+ let mut set = IndexSet::<usize>::new();
+ assert_eq!(set.capacity(), 0);
+ set.reserve(100);
+ let capacity = set.capacity();
+ assert!(capacity >= 100);
+ for i in 0..capacity {
+ assert_eq!(set.len(), i);
+ set.insert(i);
+ assert_eq!(set.len(), i + 1);
+ assert_eq!(set.capacity(), capacity);
+ assert_eq!(set.get(&i), Some(&i));
+ }
+ set.insert(capacity);
+ assert_eq!(set.len(), capacity + 1);
+ assert!(set.capacity() > capacity);
+ assert_eq!(set.get(&capacity), Some(&capacity));
+ }
+
+ #[test]
+ fn shrink_to_fit() {
+ let mut set = IndexSet::<usize>::new();
+ assert_eq!(set.capacity(), 0);
+ for i in 0..100 {
+ assert_eq!(set.len(), i);
+ set.insert(i);
+ assert_eq!(set.len(), i + 1);
+ assert!(set.capacity() >= i + 1);
+ assert_eq!(set.get(&i), Some(&i));
+ set.shrink_to_fit();
+ assert_eq!(set.len(), i + 1);
+ assert_eq!(set.capacity(), i + 1);
+ assert_eq!(set.get(&i), Some(&i));
+ }
+ }
+
+ #[test]
+ fn remove() {
+ let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
+ let mut set = IndexSet::new();
+
+ for &elt in &insert {
+ set.insert(elt);
+ }
+
+ assert_eq!(set.iter().count(), set.len());
+ assert_eq!(set.iter().count(), insert.len());
+ for (a, b) in insert.iter().zip(set.iter()) {
+ assert_eq!(a, b);
+ }
+
+ let remove_fail = [99, 77];
+ let remove = [4, 12, 8, 7];
+
+ for &value in &remove_fail {
+ assert!(set.swap_remove_full(&value).is_none());
+ }
+ println!("{:?}", set);
+ for &value in &remove {
+ //println!("{:?}", set);
+ let index = set.get_full(&value).unwrap().0;
+ assert_eq!(set.swap_remove_full(&value), Some((index, value)));
+ }
+ println!("{:?}", set);
+
+ for value in &insert {
+ assert_eq!(set.get(value).is_some(), !remove.contains(value));
+ }
+ assert_eq!(set.len(), insert.len() - remove.len());
+ assert_eq!(set.iter().count(), insert.len() - remove.len());
+ }
+
+ #[test]
+ fn swap_remove_index() {
+ let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
+ let mut set = IndexSet::new();
+
+ for &elt in &insert {
+ set.insert(elt);
+ }
+
+ let mut vector = insert.to_vec();
+ let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1];
+
+ // check that the same swap remove sequence on vec and set
+ // have the same result.
+ for &rm in remove_sequence {
+ let out_vec = vector.swap_remove(rm);
+ let out_set = set.swap_remove_index(rm).unwrap();
+ assert_eq!(out_vec, out_set);
+ }
+ assert_eq!(vector.len(), set.len());
+ for (a, b) in vector.iter().zip(set.iter()) {
+ assert_eq!(a, b);
+ }
+ }
+
+ #[test]
+ fn partial_eq_and_eq() {
+ let mut set_a = IndexSet::new();
+ set_a.insert(1);
+ set_a.insert(2);
+ let mut set_b = set_a.clone();
+ assert_eq!(set_a, set_b);
+ set_b.swap_remove(&1);
+ assert_ne!(set_a, set_b);
+
+ let set_c: IndexSet<_> = set_b.into_iter().collect();
+ assert_ne!(set_a, set_c);
+ assert_ne!(set_c, set_a);
+ }
+
+ #[test]
+ fn extend() {
+ let mut set = IndexSet::new();
+ set.extend(vec![&1, &2, &3, &4]);
+ set.extend(vec![5, 6]);
+ assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4, 5, 6]);
+ }
+
+ #[test]
+ fn comparisons() {
+ let set_a: IndexSet<_> = (0..3).collect();
+ let set_b: IndexSet<_> = (3..6).collect();
+ let set_c: IndexSet<_> = (0..6).collect();
+ let set_d: IndexSet<_> = (3..9).collect();
+
+ assert!(!set_a.is_disjoint(&set_a));
+ assert!(set_a.is_subset(&set_a));
+ assert!(set_a.is_superset(&set_a));
+
+ assert!(set_a.is_disjoint(&set_b));
+ assert!(set_b.is_disjoint(&set_a));
+ assert!(!set_a.is_subset(&set_b));
+ assert!(!set_b.is_subset(&set_a));
+ assert!(!set_a.is_superset(&set_b));
+ assert!(!set_b.is_superset(&set_a));
+
+ assert!(!set_a.is_disjoint(&set_c));
+ assert!(!set_c.is_disjoint(&set_a));
+ assert!(set_a.is_subset(&set_c));
+ assert!(!set_c.is_subset(&set_a));
+ assert!(!set_a.is_superset(&set_c));
+ assert!(set_c.is_superset(&set_a));
+
+ assert!(!set_c.is_disjoint(&set_d));
+ assert!(!set_d.is_disjoint(&set_c));
+ assert!(!set_c.is_subset(&set_d));
+ assert!(!set_d.is_subset(&set_c));
+ assert!(!set_c.is_superset(&set_d));
+ assert!(!set_d.is_superset(&set_c));
+ }
+
+ #[test]
+ fn iter_comparisons() {
+ use std::iter::empty;
+
+ fn check<'a, I1, I2>(iter1: I1, iter2: I2)
+ where
+ I1: Iterator<Item = &'a i32>,
+ I2: Iterator<Item = i32>,
+ {
+ assert!(iter1.copied().eq(iter2));
+ }
+
+ let set_a: IndexSet<_> = (0..3).collect();
+ let set_b: IndexSet<_> = (3..6).collect();
+ let set_c: IndexSet<_> = (0..6).collect();
+ let set_d: IndexSet<_> = (3..9).rev().collect();
+
+ check(set_a.difference(&set_a), empty());
+ check(set_a.symmetric_difference(&set_a), empty());
+ check(set_a.intersection(&set_a), 0..3);
+ check(set_a.union(&set_a), 0..3);
+
+ check(set_a.difference(&set_b), 0..3);
+ check(set_b.difference(&set_a), 3..6);
+ check(set_a.symmetric_difference(&set_b), 0..6);
+ check(set_b.symmetric_difference(&set_a), (3..6).chain(0..3));
+ check(set_a.intersection(&set_b), empty());
+ check(set_b.intersection(&set_a), empty());
+ check(set_a.union(&set_b), 0..6);
+ check(set_b.union(&set_a), (3..6).chain(0..3));
+
+ check(set_a.difference(&set_c), empty());
+ check(set_c.difference(&set_a), 3..6);
+ check(set_a.symmetric_difference(&set_c), 3..6);
+ check(set_c.symmetric_difference(&set_a), 3..6);
+ check(set_a.intersection(&set_c), 0..3);
+ check(set_c.intersection(&set_a), 0..3);
+ check(set_a.union(&set_c), 0..6);
+ check(set_c.union(&set_a), 0..6);
+
+ check(set_c.difference(&set_d), 0..3);
+ check(set_d.difference(&set_c), (6..9).rev());
+ check(
+ set_c.symmetric_difference(&set_d),
+ (0..3).chain((6..9).rev()),
+ );
+ check(set_d.symmetric_difference(&set_c), (6..9).rev().chain(0..3));
+ check(set_c.intersection(&set_d), 3..6);
+ check(set_d.intersection(&set_c), (3..6).rev());
+ check(set_c.union(&set_d), (0..6).chain((6..9).rev()));
+ check(set_d.union(&set_c), (3..9).rev().chain(0..3));
+ }
+
+ #[test]
+ fn ops() {
+ let empty = IndexSet::<i32>::new();
+ let set_a: IndexSet<_> = (0..3).collect();
+ let set_b: IndexSet<_> = (3..6).collect();
+ let set_c: IndexSet<_> = (0..6).collect();
+ let set_d: IndexSet<_> = (3..9).rev().collect();
+
+ #[allow(clippy::eq_op)]
+ {
+ assert_eq!(&set_a & &set_a, set_a);
+ assert_eq!(&set_a | &set_a, set_a);
+ assert_eq!(&set_a ^ &set_a, empty);
+ assert_eq!(&set_a - &set_a, empty);
+ }
+
+ assert_eq!(&set_a & &set_b, empty);
+ assert_eq!(&set_b & &set_a, empty);
+ assert_eq!(&set_a | &set_b, set_c);
+ assert_eq!(&set_b | &set_a, set_c);
+ assert_eq!(&set_a ^ &set_b, set_c);
+ assert_eq!(&set_b ^ &set_a, set_c);
+ assert_eq!(&set_a - &set_b, set_a);
+ assert_eq!(&set_b - &set_a, set_b);
+
+ assert_eq!(&set_a & &set_c, set_a);
+ assert_eq!(&set_c & &set_a, set_a);
+ assert_eq!(&set_a | &set_c, set_c);
+ assert_eq!(&set_c | &set_a, set_c);
+ assert_eq!(&set_a ^ &set_c, set_b);
+ assert_eq!(&set_c ^ &set_a, set_b);
+ assert_eq!(&set_a - &set_c, empty);
+ assert_eq!(&set_c - &set_a, set_b);
+
+ assert_eq!(&set_c & &set_d, set_b);
+ assert_eq!(&set_d & &set_c, set_b);
+ assert_eq!(&set_c | &set_d, &set_a | &set_d);
+ assert_eq!(&set_d | &set_c, &set_a | &set_d);
+ assert_eq!(&set_c ^ &set_d, &set_a | &(&set_d - &set_b));
+ assert_eq!(&set_d ^ &set_c, &set_a | &(&set_d - &set_b));
+ assert_eq!(&set_c - &set_d, set_a);
+ assert_eq!(&set_d - &set_c, &set_d - &set_b);
+ }
+
+ #[test]
+ #[cfg(has_std)]
+ fn from_array() {
+ let set1 = IndexSet::from([1, 2, 3, 4]);
+ let set2: IndexSet<_> = [1, 2, 3, 4].into();
+
+ assert_eq!(set1, set2);
+ }
+}
diff --git a/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<A, B, C>(t: (A, B, C)) -> C {
+ t.2
+}
+
+pub(crate) fn simplify_range<R>(range: R, len: usize) -> Range<usize>
+where
+ R: RangeBounds<usize>,
+{
+ let start = match range.start_bound() {
+ Bound::Unbounded => 0,
+ Bound::Included(&i) if i <= len => i,
+ Bound::Excluded(&i) if i < len => i + 1,
+ 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
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-12 03:28:21 +0000