diff options
Diffstat (limited to 'third_party/rust/indexmap/src/map')
| -rw-r--r-- | third_party/rust/indexmap/src/map/core.rs | 460 | ||||
| -rw-r--r-- | third_party/rust/indexmap/src/map/core/entry.rs | 481 | ||||
| -rw-r--r-- | third_party/rust/indexmap/src/map/core/raw.rs | 174 | ||||
| -rw-r--r-- | third_party/rust/indexmap/src/map/core/raw_entry_v1.rs | 652 | ||||
| -rw-r--r-- | third_party/rust/indexmap/src/map/iter.rs | 713 | ||||
| -rw-r--r-- | third_party/rust/indexmap/src/map/mutable.rs | 87 | ||||
| -rw-r--r-- | third_party/rust/indexmap/src/map/serde_seq.rs | 138 | ||||
| -rw-r--r-- | third_party/rust/indexmap/src/map/slice.rs | 539 | ||||
| -rw-r--r-- | third_party/rust/indexmap/src/map/tests.rs | 727 |
9 files changed, 3606 insertions, 365 deletions
diff --git a/third_party/rust/indexmap/src/map/core.rs b/third_party/rust/indexmap/src/map/core.rs index ea7aaae62e..16e87c7c6a 100644 --- a/third_party/rust/indexmap/src/map/core.rs +++ b/third_party/rust/indexmap/src/map/core.rs @@ -7,19 +7,22 @@ //! //! However, we should probably not let this show in the public API or docs. +mod entry; mod raw; +pub mod raw_entry_v1; + use hashbrown::raw::RawTable; -use crate::vec::{Drain, Vec}; -use core::cmp; -use core::fmt; -use core::mem::replace; +use crate::vec::{self, Vec}; +use crate::TryReserveError; +use core::mem; use core::ops::RangeBounds; -use crate::equivalent::Equivalent; use crate::util::simplify_range; -use crate::{Bucket, Entries, HashValue}; +use crate::{Bucket, Entries, Equivalent, HashValue}; + +pub use entry::{Entry, IndexedEntry, OccupiedEntry, VacantEntry}; /// Core of the map that does not depend on S pub(crate) struct IndexMapCore<K, V> { @@ -62,29 +65,30 @@ where V: Clone, { fn clone(&self) -> Self { - let indices = self.indices.clone(); - let mut entries = Vec::with_capacity(indices.capacity()); - entries.clone_from(&self.entries); - IndexMapCore { indices, entries } + let mut new = Self::new(); + new.clone_from(self); + new } fn clone_from(&mut self, other: &Self) { let hasher = get_hash(&other.entries); self.indices.clone_from_with_hasher(&other.indices, hasher); if self.entries.capacity() < other.entries.len() { - // If we must resize, match the indices capacity - self.reserve_entries(); + // If we must resize, match the indices capacity. + let additional = other.entries.len() - self.entries.len(); + self.reserve_entries(additional); } self.entries.clone_from(&other.entries); } } -impl<K, V> fmt::Debug for IndexMapCore<K, V> +#[cfg(feature = "test_debug")] +impl<K, V> core::fmt::Debug for IndexMapCore<K, V> where - K: fmt::Debug, - V: fmt::Debug, + K: core::fmt::Debug, + V: core::fmt::Debug, { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { f.debug_struct("IndexMapCore") .field("indices", &raw::DebugIndices(&self.indices)) .field("entries", &self.entries) @@ -120,6 +124,9 @@ impl<K, V> Entries for IndexMapCore<K, V> { } impl<K, V> IndexMapCore<K, V> { + /// The maximum capacity before the `entries` allocation would exceed `isize::MAX`. + const MAX_ENTRIES_CAPACITY: usize = (isize::MAX as usize) / mem::size_of::<Bucket<K, V>>(); + #[inline] pub(crate) const fn new() -> Self { IndexMapCore { @@ -143,7 +150,7 @@ impl<K, V> IndexMapCore<K, V> { #[inline] pub(crate) fn capacity(&self) -> usize { - cmp::min(self.indices.capacity(), self.entries.capacity()) + Ord::min(self.indices.capacity(), self.entries.capacity()) } pub(crate) fn clear(&mut self) { @@ -158,7 +165,7 @@ impl<K, V> IndexMapCore<K, V> { } } - pub(crate) fn drain<R>(&mut self, range: R) -> Drain<'_, Bucket<K, V>> + pub(crate) fn drain<R>(&mut self, range: R) -> vec::Drain<'_, Bucket<K, V>> where R: RangeBounds<usize>, { @@ -190,18 +197,92 @@ impl<K, V> IndexMapCore<K, V> { Self { indices, entries } } + pub(crate) fn split_splice<R>(&mut self, range: R) -> (Self, vec::IntoIter<Bucket<K, V>>) + where + R: RangeBounds<usize>, + { + let range = simplify_range(range, self.len()); + self.erase_indices(range.start, self.entries.len()); + let entries = self.entries.split_off(range.end); + let drained = self.entries.split_off(range.start); + + let mut indices = RawTable::with_capacity(entries.len()); + raw::insert_bulk_no_grow(&mut indices, &entries); + (Self { indices, entries }, drained.into_iter()) + } + + /// Append from another map without checking whether items already exist. + pub(crate) fn append_unchecked(&mut self, other: &mut Self) { + self.reserve(other.len()); + raw::insert_bulk_no_grow(&mut self.indices, &other.entries); + self.entries.append(&mut other.entries); + other.indices.clear(); + } + /// Reserve capacity for `additional` more key-value pairs. pub(crate) fn reserve(&mut self, additional: usize) { self.indices.reserve(additional, get_hash(&self.entries)); - self.reserve_entries(); + // Only grow entries if necessary, since we also round up capacity. + if additional > self.entries.capacity() - self.entries.len() { + self.reserve_entries(additional); + } + } + + /// Reserve entries capacity, rounded up to match the indices + fn reserve_entries(&mut self, additional: usize) { + // Use a soft-limit on the maximum capacity, but if the caller explicitly + // requested more, do it and let them have the resulting panic. + let new_capacity = Ord::min(self.indices.capacity(), Self::MAX_ENTRIES_CAPACITY); + let try_add = new_capacity - self.entries.len(); + if try_add > additional && self.entries.try_reserve_exact(try_add).is_ok() { + return; + } + self.entries.reserve_exact(additional); } - /// Reserve entries capacity to match the indices - fn reserve_entries(&mut self) { - let additional = self.indices.capacity() - self.entries.len(); + /// Reserve capacity for `additional` more key-value pairs, without over-allocating. + pub(crate) fn reserve_exact(&mut self, additional: usize) { + self.indices.reserve(additional, get_hash(&self.entries)); self.entries.reserve_exact(additional); } + /// Try to reserve capacity for `additional` more key-value pairs. + pub(crate) fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.indices + .try_reserve(additional, get_hash(&self.entries)) + .map_err(TryReserveError::from_hashbrown)?; + // Only grow entries if necessary, since we also round up capacity. + if additional > self.entries.capacity() - self.entries.len() { + self.try_reserve_entries(additional) + } else { + Ok(()) + } + } + + /// Try to reserve entries capacity, rounded up to match the indices + fn try_reserve_entries(&mut self, additional: usize) -> Result<(), TryReserveError> { + // Use a soft-limit on the maximum capacity, but if the caller explicitly + // requested more, do it and let them have the resulting error. + let new_capacity = Ord::min(self.indices.capacity(), Self::MAX_ENTRIES_CAPACITY); + let try_add = new_capacity - self.entries.len(); + if try_add > additional && self.entries.try_reserve_exact(try_add).is_ok() { + return Ok(()); + } + self.entries + .try_reserve_exact(additional) + .map_err(TryReserveError::from_alloc) + } + + /// Try to reserve capacity for `additional` more key-value pairs, without over-allocating. + pub(crate) fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.indices + .try_reserve(additional, get_hash(&self.entries)) + .map_err(TryReserveError::from_hashbrown)?; + self.entries + .try_reserve_exact(additional) + .map_err(TryReserveError::from_alloc) + } + /// Shrink the capacity of the map with a lower bound pub(crate) fn shrink_to(&mut self, min_capacity: usize) { self.indices @@ -220,18 +301,25 @@ impl<K, V> IndexMapCore<K, V> { } } - /// Append a key-value pair, *without* checking whether it already exists, - /// and return the pair's new index. - fn push(&mut self, hash: HashValue, key: K, value: V) -> usize { - let i = self.entries.len(); - self.indices.insert(hash.get(), i, get_hash(&self.entries)); - if i == self.entries.capacity() { + /// Append a key-value pair to `entries`, *without* checking whether it already exists. + fn push_entry(&mut self, hash: HashValue, key: K, value: V) { + if self.entries.len() == self.entries.capacity() { // Reserve our own capacity synced to the indices, // rather than letting `Vec::push` just double it. - self.reserve_entries(); + self.reserve_entries(1); } self.entries.push(Bucket { hash, key, value }); - i + } + + /// Insert a key-value pair in `entries` at a particular index, + /// *without* checking whether it already exists. + fn insert_entry(&mut self, index: usize, hash: HashValue, key: K, value: V) { + if self.entries.len() == self.entries.capacity() { + // Reserve our own capacity synced to the indices, + // rather than letting `Vec::insert` just double it. + self.reserve_entries(1); + } + self.entries.insert(index, Bucket { hash, key, value }); } /// Return the index in `entries` where an equivalent key can be found @@ -247,12 +335,66 @@ impl<K, V> IndexMapCore<K, V> { where K: Eq, { - match self.get_index_of(hash, &key) { - Some(i) => (i, Some(replace(&mut self.entries[i].value, value))), - None => (self.push(hash, key, value), None), + match self.find_or_insert(hash, &key) { + Ok(i) => (i, Some(mem::replace(&mut self.entries[i].value, value))), + Err(i) => { + debug_assert_eq!(i, self.entries.len()); + self.push_entry(hash, key, value); + (i, None) + } + } + } + + /// Same as `insert_full`, except it also replaces the key + pub(crate) fn replace_full( + &mut self, + hash: HashValue, + key: K, + value: V, + ) -> (usize, Option<(K, V)>) + where + K: Eq, + { + match self.find_or_insert(hash, &key) { + Ok(i) => { + let entry = &mut self.entries[i]; + let kv = ( + mem::replace(&mut entry.key, key), + mem::replace(&mut entry.value, value), + ); + (i, Some(kv)) + } + Err(i) => { + debug_assert_eq!(i, self.entries.len()); + self.push_entry(hash, key, value); + (i, None) + } } } + fn insert_unique(&mut self, hash: HashValue, key: K, value: V) -> usize { + let i = self.indices.len(); + self.indices.insert(hash.get(), i, get_hash(&self.entries)); + debug_assert_eq!(i, self.entries.len()); + self.push_entry(hash, key, value); + i + } + + fn shift_insert_unique(&mut self, index: usize, hash: HashValue, key: K, value: V) { + let end = self.indices.len(); + assert!(index <= end); + // Increment others first so we don't have duplicate indices. + self.increment_indices(index, end); + let entries = &*self.entries; + self.indices.insert(hash.get(), index, move |&i| { + // Adjust for the incremented indices to find hashes. + debug_assert_ne!(i, index); + let i = if i < index { i } else { i - 1 }; + entries[i].hash.get() + }); + self.insert_entry(index, hash, key, value); + } + /// 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 @@ -339,7 +481,7 @@ impl<K, V> IndexMapCore<K, V> { pub(super) fn move_index(&mut self, from: usize, to: usize) { let from_hash = self.entries[from].hash; if from != to { - // Use a sentinal index so other indices don't collide. + // Use a sentinel index so other indices don't collide. update_index(&mut self.indices, from_hash, from, usize::MAX); // Update all other indices and rotate the entry positions. @@ -351,11 +493,31 @@ impl<K, V> IndexMapCore<K, V> { self.entries[to..=from].rotate_right(1); } - // Change the sentinal index to its final position. + // Change the sentinel index to its final position. update_index(&mut self.indices, from_hash, usize::MAX, to); } } + pub(crate) fn swap_indices(&mut self, a: usize, b: usize) { + // If they're equal and in-bounds, there's nothing to do. + if a == b && a < self.entries.len() { + return; + } + + // We'll get a "nice" bounds-check from indexing `self.entries`, + // and then we expect to find it in the table as well. + let [ref_a, ref_b] = self + .indices + .get_many_mut( + [self.entries[a].hash.get(), self.entries[b].hash.get()], + move |i, &x| if i == 0 { x == a } else { x == b }, + ) + .expect("indices not found"); + + mem::swap(ref_a, ref_b); + self.entries.swap(a, b); + } + /// 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 @@ -447,25 +609,9 @@ impl<K, V> IndexMapCore<K, V> { where F: FnMut(&mut K, &mut V) -> bool, { - // FIXME: This could use Vec::retain_mut with MSRV 1.61. - // Like Vec::retain in self.entries, but with mutable K and V. - // We swap-shift all the items we want to keep, truncate the rest, - // then rebuild the raw hash table with the new indexes. - let len = self.entries.len(); - let mut n_deleted = 0; - for i in 0..len { - let will_keep = { - let entry = &mut self.entries[i]; - keep(&mut entry.key, &mut entry.value) - }; - if !will_keep { - n_deleted += 1; - } else if n_deleted > 0 { - self.entries.swap(i - n_deleted, i); - } - } - if n_deleted > 0 { - self.entries.truncate(len - n_deleted); + self.entries + .retain_mut(|entry| keep(&mut entry.key, &mut entry.value)); + if self.entries.len() < self.indices.len() { self.rebuild_hash_table(); } } @@ -487,214 +633,10 @@ impl<K, V> IndexMapCore<K, V> { } } -/// 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>>(); + assert_send_sync::<IndexedEntry<'_, i32, i32>>(); } diff --git a/third_party/rust/indexmap/src/map/core/entry.rs b/third_party/rust/indexmap/src/map/core/entry.rs new file mode 100644 index 0000000000..6c31070788 --- /dev/null +++ b/third_party/rust/indexmap/src/map/core/entry.rs @@ -0,0 +1,481 @@ +use super::raw::RawTableEntry; +use super::IndexMapCore; +use crate::HashValue; +use core::{fmt, mem}; + +impl<K, V> IndexMapCore<K, V> { + pub(crate) fn entry(&mut self, hash: HashValue, key: K) -> Entry<'_, K, V> + where + K: Eq, + { + match self.raw_entry(hash, |k| *k == key) { + Ok(raw) => Entry::Occupied(OccupiedEntry { raw }), + Err(map) => Entry::Vacant(VacantEntry { map, hash, key }), + } + } +} + +/// Entry for an existing key-value pair in an [`IndexMap`][crate::IndexMap] +/// 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> { + /// 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(), + } + } + + /// 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(), + } + } + + /// Modifies the entry if it is occupied. + pub fn and_modify<F>(mut self, f: F) -> Self + where + F: FnOnce(&mut V), + { + if let Entry::Occupied(entry) = &mut self { + f(entry.get_mut()); + } + self + } + + /// 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 { + let mut tuple = f.debug_tuple("Entry"); + match self { + Entry::Vacant(v) => tuple.field(v), + Entry::Occupied(o) => tuple.field(o), + }; + tuple.finish() + } +} + +/// A view into an occupied entry in an [`IndexMap`][crate::IndexMap]. +/// It is part of the [`Entry`] enum. +pub struct OccupiedEntry<'a, K, V> { + raw: RawTableEntry<'a, K, V>, +} + +impl<'a, K, V> OccupiedEntry<'a, K, V> { + /// Return the index of the key-value pair + #[inline] + pub fn index(&self) -> usize { + self.raw.index() + } + + /// 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.raw.bucket().key + } + + /// Gets a reference to the entry's value in the map. + pub fn get(&self) -> &V { + &self.raw.bucket().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`][Self::into_mut]. + pub fn get_mut(&mut self) -> &mut V { + &mut self.raw.bucket_mut().value + } + + /// 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 { + &mut self.raw.into_bucket().value + } + + /// Sets the value of the entry to `value`, and returns the entry's old value. + pub fn insert(&mut self, value: V) -> V { + mem::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()`][Self::swap_remove], replacing this + /// entry's position with the last element, and it is deprecated in favor of calling that + /// explicitly. If you need to preserve the relative order of the keys in the map, use + /// [`.shift_remove()`][Self::shift_remove] instead. + #[deprecated(note = "`remove` disrupts the map order -- \ + use `swap_remove` or `shift_remove` for explicit behavior.")] + 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`][crate::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`][crate::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()`][Self::swap_remove_entry], + /// replacing this entry's position with the last element, and it is deprecated in favor of + /// calling that explicitly. If you need to preserve the relative order of the keys in the map, + /// use [`.shift_remove_entry()`][Self::shift_remove_entry] instead. + #[deprecated(note = "`remove_entry` disrupts the map order -- \ + use `swap_remove_entry` or `shift_remove_entry` for explicit behavior.")] + pub fn remove_entry(self) -> (K, V) { + self.swap_remove_entry() + } + + /// Remove and return the key, value pair stored in the map for this entry + /// + /// Like [`Vec::swap_remove`][crate::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) { + let (map, index) = self.raw.remove_index(); + map.swap_remove_finish(index) + } + + /// Remove and return the key, value pair stored in the map for this entry + /// + /// Like [`Vec::remove`][crate::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) { + let (map, index) = self.raw.remove_index(); + map.shift_remove_finish(index) + } + + /// Moves the position of the entry to a new index + /// by shifting all other entries in-between. + /// + /// This is equivalent to [`IndexMap::move_index`][`crate::IndexMap::move_index`] + /// coming `from` the current [`.index()`][Self::index]. + /// + /// * If `self.index() < to`, the other pairs will shift down while the targeted pair moves up. + /// * If `self.index() > to`, the other pairs will shift up while the targeted pair moves down. + /// + /// ***Panics*** if `to` is out of bounds. + /// + /// Computes in **O(n)** time (average). + pub fn move_index(self, to: usize) { + let (map, index) = self.raw.into_inner(); + map.move_index(index, to); + } + + /// Swaps the position of entry with another. + /// + /// This is equivalent to [`IndexMap::swap_indices`][`crate::IndexMap::swap_indices`] + /// with the current [`.index()`][Self::index] as one of the two being swapped. + /// + /// ***Panics*** if the `other` index is out of bounds. + /// + /// Computes in **O(1)** time (average). + pub fn swap_indices(self, other: usize) { + let (map, index) = self.raw.into_inner(); + map.swap_indices(index, other) + } +} + +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("OccupiedEntry") + .field("key", self.key()) + .field("value", self.get()) + .finish() + } +} + +/// A view into a vacant entry in an [`IndexMap`][crate::IndexMap]. +/// It is part of the [`Entry`] enum. +pub struct VacantEntry<'a, K, V> { + map: &'a mut IndexMapCore<K, V>, + hash: HashValue, + key: K, +} + +impl<'a, K, V> VacantEntry<'a, K, V> { + /// Return the index where a key-value pair may be inserted. + pub fn index(&self) -> usize { + self.map.indices.len() + } + + /// 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 + } + + /// 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 Self { map, hash, key } = self; + let i = map.insert_unique(hash, key, value); + &mut map.entries[i].value + } + + /// Inserts the entry's key and the given value into the map at its ordered + /// position among sorted keys, and returns the new index and a mutable + /// reference to the value. + /// + /// If the existing keys are **not** already sorted, then the insertion + /// index is unspecified (like [`slice::binary_search`]), but the key-value + /// pair is inserted at that position regardless. + /// + /// Computes in **O(n)** time (average). + pub fn insert_sorted(self, value: V) -> (usize, &'a mut V) + where + K: Ord, + { + let slice = crate::map::Slice::from_slice(&self.map.entries); + let i = slice.binary_search_keys(&self.key).unwrap_err(); + (i, self.shift_insert(i, value)) + } + + /// Inserts the entry's key and the given value into the map at the given index, + /// shifting others to the right, and returns a mutable reference to the value. + /// + /// ***Panics*** if `index` is out of bounds. + /// + /// Computes in **O(n)** time (average). + pub fn shift_insert(self, index: usize, value: V) -> &'a mut V { + let Self { map, hash, key } = self; + map.shift_insert_unique(index, hash, key, value); + &mut map.entries[index].value + } +} + +impl<K: fmt::Debug, V> fmt::Debug for VacantEntry<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("VacantEntry").field(self.key()).finish() + } +} + +/// A view into an occupied entry in an [`IndexMap`][crate::IndexMap] obtained by index. +/// +/// This `struct` is created from the [`get_index_entry`][crate::IndexMap::get_index_entry] method. +pub struct IndexedEntry<'a, K, V> { + map: &'a mut IndexMapCore<K, V>, + // We have a mutable reference to the map, which keeps the index + // valid and pointing to the correct entry. + index: usize, +} + +impl<'a, K, V> IndexedEntry<'a, K, V> { + pub(crate) fn new(map: &'a mut IndexMapCore<K, V>, index: usize) -> Self { + Self { map, index } + } + + /// Return the index of the key-value pair + #[inline] + pub fn index(&self) -> usize { + self.index + } + + /// Gets a reference to the entry's key in the map. + 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 + /// `IndexedEntry` value, see [`into_mut`][Self::into_mut]. + pub fn get_mut(&mut self) -> &mut V { + &mut self.map.entries[self.index].value + } + + /// Sets the value of the entry to `value`, and returns the entry's old value. + pub fn insert(&mut self, value: V) -> V { + mem::replace(self.get_mut(), value) + } + + /// 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 { + &mut self.map.entries[self.index].value + } + + /// Remove and return the key, value pair stored in the map for this entry + /// + /// Like [`Vec::swap_remove`][crate::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) { + self.map.swap_remove_index(self.index).unwrap() + } + + /// Remove and return the key, value pair stored in the map for this entry + /// + /// Like [`Vec::remove`][crate::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) { + self.map.shift_remove_index(self.index).unwrap() + } + + /// Remove the key, value pair stored in the map for this entry, and return the value. + /// + /// Like [`Vec::swap_remove`][crate::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`][crate::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 + } + + /// Moves the position of the entry to a new index + /// by shifting all other entries in-between. + /// + /// This is equivalent to [`IndexMap::move_index`][`crate::IndexMap::move_index`] + /// coming `from` the current [`.index()`][Self::index]. + /// + /// * If `self.index() < to`, the other pairs will shift down while the targeted pair moves up. + /// * If `self.index() > to`, the other pairs will shift up while the targeted pair moves down. + /// + /// ***Panics*** if `to` is out of bounds. + /// + /// Computes in **O(n)** time (average). + pub fn move_index(self, to: usize) { + self.map.move_index(self.index, to); + } + + /// Swaps the position of entry with another. + /// + /// This is equivalent to [`IndexMap::swap_indices`][`crate::IndexMap::swap_indices`] + /// with the current [`.index()`][Self::index] as one of the two being swapped. + /// + /// ***Panics*** if the `other` index is out of bounds. + /// + /// Computes in **O(1)** time (average). + pub fn swap_indices(self, other: usize) { + self.map.swap_indices(self.index, other) + } +} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IndexedEntry<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("IndexedEntry") + .field("index", &self.index) + .field("key", self.key()) + .field("value", self.get()) + .finish() + } +} diff --git a/third_party/rust/indexmap/src/map/core/raw.rs b/third_party/rust/indexmap/src/map/core/raw.rs index bf1672d52a..451994339a 100644 --- a/third_party/rust/indexmap/src/map/core/raw.rs +++ b/third_party/rust/indexmap/src/map/core/raw.rs @@ -2,9 +2,7 @@ //! This module encapsulates the `unsafe` access to `hashbrown::raw::RawTable`, //! mostly in dealing with its bucket "pointers". -use super::{equivalent, Bucket, Entry, HashValue, IndexMapCore, VacantEntry}; -use core::fmt; -use core::mem::replace; +use super::{equivalent, get_hash, Bucket, HashValue, IndexMapCore}; use hashbrown::raw::RawTable; type RawBucket = hashbrown::raw::Bucket<usize>; @@ -22,11 +20,14 @@ pub(super) fn insert_bulk_no_grow<K, V>(indices: &mut RawTable<usize>, entries: } } +#[cfg(feature = "test_debug")] pub(super) struct DebugIndices<'a>(pub &'a RawTable<usize>); -impl fmt::Debug for DebugIndices<'_> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + +#[cfg(feature = "test_debug")] +impl core::fmt::Debug for DebugIndices<'_> { + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { // SAFETY: we're not letting any of the buckets escape this function - let indices = unsafe { self.0.iter().map(|raw_bucket| raw_bucket.read()) }; + let indices = unsafe { self.0.iter().map(|raw_bucket| *raw_bucket.as_ref()) }; f.debug_list().entries(indices).finish() } } @@ -38,34 +39,57 @@ impl<K, V> IndexMapCore<K, V> { unsafe { let offset = end - start; for bucket in self.indices.iter() { - let i = bucket.read(); - if i >= end { - bucket.write(i - offset); - } else if i >= start { + let i = bucket.as_mut(); + if *i >= end { + *i -= offset; + } else if *i >= start { self.indices.erase(bucket); } } } } - pub(crate) fn entry(&mut self, hash: HashValue, key: K) -> Entry<'_, K, V> + /// Search for a key in the table and return `Ok(entry_index)` if found. + /// Otherwise, insert the key and return `Err(new_index)`. + /// + /// Note that hashbrown may resize the table to reserve space for insertion, + /// even before checking if it's already present, so this is somewhat biased + /// towards new items. + pub(crate) fn find_or_insert(&mut self, hash: HashValue, key: &K) -> Result<usize, usize> where K: Eq, { - let eq = equivalent(&key, &self.entries); + let hash = hash.get(); + let eq = equivalent(key, &self.entries); + let hasher = get_hash(&self.entries); + // SAFETY: We're not mutating between find and read/insert. + unsafe { + match self.indices.find_or_find_insert_slot(hash, eq, hasher) { + Ok(raw_bucket) => Ok(*raw_bucket.as_ref()), + Err(slot) => { + let index = self.indices.len(); + self.indices.insert_in_slot(hash, slot, index); + Err(index) + } + } + } + } + + pub(super) fn raw_entry( + &mut self, + hash: HashValue, + mut is_match: impl FnMut(&K) -> bool, + ) -> Result<RawTableEntry<'_, K, V>, &mut Self> { + let entries = &*self.entries; + let eq = move |&i: &usize| is_match(&entries[i].key); 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 { + Some(raw_bucket) => Ok(RawTableEntry { map: self, raw_bucket, - key, - }), - None => Entry::Vacant(VacantEntry { - map: self, - hash, - key, }), + None => Err(self), } } @@ -74,118 +98,56 @@ impl<K, V> IndexMapCore<K, V> { // 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 +/// A view into an occupied raw entry in an `IndexMap`. // 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> { +pub(super) struct RawTableEntry<'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 - } +unsafe impl<K: Sync, V: Sync> Sync for RawTableEntry<'_, K, V> {} - /// Gets a reference to the entry's value in the map. - pub fn get(&self) -> &V { - &self.map.entries[self.index()].value +impl<'a, K, V> RawTableEntry<'a, K, V> { + /// Return the index of the key-value pair + #[inline] + pub(super) fn index(&self) -> usize { + // SAFETY: we have `&mut map` keeping the bucket stable + unsafe { *self.raw_bucket.as_ref() } } - /// 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 + #[inline] + pub(super) fn bucket(&self) -> &Bucket<K, V> { + &self.map.entries[self.index()] } - /// Put the new key in the occupied entry's key slot - pub(crate) fn replace_key(self) -> K { + #[inline] + pub(super) fn bucket_mut(&mut self) -> &mut Bucket<K, V> { let index = self.index(); - let old_key = &mut self.map.entries[index].key; - replace(old_key, self.key) + &mut self.map.entries[index] } - /// 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 { + pub(super) fn into_bucket(self) -> &'a mut Bucket<K, V> { let index = self.index(); - &mut self.map.entries[index].value + &mut self.map.entries[index] } - /// 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) { + /// Remove the index from indices, leaving the actual entries to the caller. + pub(super) fn remove_index(self) -> (&'a mut IndexMapCore<K, V>, usize) { // 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) + let (index, _slot) = unsafe { self.map.indices.remove(self.raw_bucket) }; + (self.map, 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) + /// Take no action, just return the index and the original map reference. + pub(super) fn into_inner(self) -> (&'a mut IndexMapCore<K, V>, usize) { + let index = self.index(); + (self.map, index) } } diff --git a/third_party/rust/indexmap/src/map/core/raw_entry_v1.rs b/third_party/rust/indexmap/src/map/core/raw_entry_v1.rs new file mode 100644 index 0000000000..87e532d557 --- /dev/null +++ b/third_party/rust/indexmap/src/map/core/raw_entry_v1.rs @@ -0,0 +1,652 @@ +//! Opt-in access to the experimental raw entry API. +//! +//! This module is designed to mimic the raw entry API of [`HashMap`][std::collections::hash_map], +//! matching its unstable state as of Rust 1.75. See the tracking issue +//! [rust#56167](https://github.com/rust-lang/rust/issues/56167) for more details. +//! +//! The trait [`RawEntryApiV1`] and the `_v1` suffix on its methods are meant to insulate this for +//! the future, in case later breaking changes are needed. If the standard library stabilizes its +//! `hash_raw_entry` feature (or some replacement), matching *inherent* methods will be added to +//! `IndexMap` without such an opt-in trait. + +use super::raw::RawTableEntry; +use super::IndexMapCore; +use crate::{Equivalent, HashValue, IndexMap}; +use core::fmt; +use core::hash::{BuildHasher, Hash, Hasher}; +use core::marker::PhantomData; +use core::mem; + +/// Opt-in access to the experimental raw entry API. +/// +/// See the [`raw_entry_v1`][self] module documentation for more information. +pub trait RawEntryApiV1<K, V, S>: private::Sealed { + /// Creates a raw immutable entry builder for the [`IndexMap`]. + /// + /// Raw entries provide the lowest level of control for searching and + /// manipulating a map. They must be manually initialized with a hash and + /// then manually searched. + /// + /// This is useful for + /// * Hash memoization + /// * Using a search key that doesn't work with the [`Equivalent`] trait + /// * Using custom comparison logic without newtype wrappers + /// + /// Unless you are in such a situation, higher-level and more foolproof APIs like + /// [`get`][IndexMap::get] should be preferred. + /// + /// Immutable raw entries have very limited use; you might instead want + /// [`raw_entry_mut_v1`][Self::raw_entry_mut_v1]. + /// + /// # Examples + /// + /// ``` + /// use core::hash::{BuildHasher, Hash}; + /// use indexmap::map::{IndexMap, RawEntryApiV1}; + /// + /// let mut map = IndexMap::new(); + /// map.extend([("a", 100), ("b", 200), ("c", 300)]); + /// + /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 { + /// use core::hash::Hasher; + /// let mut state = hash_builder.build_hasher(); + /// key.hash(&mut state); + /// state.finish() + /// } + /// + /// for k in ["a", "b", "c", "d", "e", "f"] { + /// let hash = compute_hash(map.hasher(), k); + /// let i = map.get_index_of(k); + /// let v = map.get(k); + /// let kv = map.get_key_value(k); + /// let ikv = map.get_full(k); + /// + /// println!("Key: {} and value: {:?}", k, v); + /// + /// assert_eq!(map.raw_entry_v1().from_key(k), kv); + /// assert_eq!(map.raw_entry_v1().from_hash(hash, |q| *q == k), kv); + /// assert_eq!(map.raw_entry_v1().from_key_hashed_nocheck(hash, k), kv); + /// assert_eq!(map.raw_entry_v1().from_hash_full(hash, |q| *q == k), ikv); + /// assert_eq!(map.raw_entry_v1().index_from_hash(hash, |q| *q == k), i); + /// } + /// ``` + fn raw_entry_v1(&self) -> RawEntryBuilder<'_, K, V, S>; + + /// Creates a raw entry builder for the [`IndexMap`]. + /// + /// Raw entries provide the lowest level of control for searching and + /// manipulating a map. They must be manually initialized with a hash and + /// then manually searched. After this, insertions into a vacant entry + /// still require an owned key to be provided. + /// + /// Raw entries are useful for such exotic situations as: + /// + /// * Hash memoization + /// * Deferring the creation of an owned key until it is known to be required + /// * Using a search key that doesn't work with the [`Equivalent`] trait + /// * Using custom comparison logic without newtype wrappers + /// + /// Because raw entries provide much more low-level control, it's much easier + /// to put the `IndexMap` into an inconsistent state which, while memory-safe, + /// will cause the map to produce seemingly random results. Higher-level and more + /// foolproof APIs like [`entry`][IndexMap::entry] should be preferred when possible. + /// + /// Raw entries give mutable access to the keys. This must not be used + /// to modify how the key would compare or hash, as the map will not re-evaluate + /// where the key should go, meaning the keys may become "lost" if their + /// location does not reflect their state. For instance, if you change a key + /// so that the map now contains keys which compare equal, search may start + /// acting erratically, with two keys randomly masking each other. Implementations + /// are free to assume this doesn't happen (within the limits of memory-safety). + /// + /// # Examples + /// + /// ``` + /// use core::hash::{BuildHasher, Hash}; + /// use indexmap::map::{IndexMap, RawEntryApiV1}; + /// use indexmap::map::raw_entry_v1::RawEntryMut; + /// + /// let mut map = IndexMap::new(); + /// map.extend([("a", 100), ("b", 200), ("c", 300)]); + /// + /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 { + /// use core::hash::Hasher; + /// let mut state = hash_builder.build_hasher(); + /// key.hash(&mut state); + /// state.finish() + /// } + /// + /// // Existing key (insert and update) + /// match map.raw_entry_mut_v1().from_key("a") { + /// RawEntryMut::Vacant(_) => unreachable!(), + /// RawEntryMut::Occupied(mut view) => { + /// assert_eq!(view.index(), 0); + /// assert_eq!(view.get(), &100); + /// let v = view.get_mut(); + /// let new_v = (*v) * 10; + /// *v = new_v; + /// assert_eq!(view.insert(1111), 1000); + /// } + /// } + /// + /// assert_eq!(map["a"], 1111); + /// assert_eq!(map.len(), 3); + /// + /// // Existing key (take) + /// let hash = compute_hash(map.hasher(), "c"); + /// match map.raw_entry_mut_v1().from_key_hashed_nocheck(hash, "c") { + /// RawEntryMut::Vacant(_) => unreachable!(), + /// RawEntryMut::Occupied(view) => { + /// assert_eq!(view.index(), 2); + /// assert_eq!(view.shift_remove_entry(), ("c", 300)); + /// } + /// } + /// assert_eq!(map.raw_entry_v1().from_key("c"), None); + /// assert_eq!(map.len(), 2); + /// + /// // Nonexistent key (insert and update) + /// let key = "d"; + /// let hash = compute_hash(map.hasher(), key); + /// match map.raw_entry_mut_v1().from_hash(hash, |q| *q == key) { + /// RawEntryMut::Occupied(_) => unreachable!(), + /// RawEntryMut::Vacant(view) => { + /// assert_eq!(view.index(), 2); + /// let (k, value) = view.insert("d", 4000); + /// assert_eq!((*k, *value), ("d", 4000)); + /// *value = 40000; + /// } + /// } + /// assert_eq!(map["d"], 40000); + /// assert_eq!(map.len(), 3); + /// + /// match map.raw_entry_mut_v1().from_hash(hash, |q| *q == key) { + /// RawEntryMut::Vacant(_) => unreachable!(), + /// RawEntryMut::Occupied(view) => { + /// assert_eq!(view.index(), 2); + /// assert_eq!(view.swap_remove_entry(), ("d", 40000)); + /// } + /// } + /// assert_eq!(map.get("d"), None); + /// assert_eq!(map.len(), 2); + /// ``` + fn raw_entry_mut_v1(&mut self) -> RawEntryBuilderMut<'_, K, V, S>; +} + +impl<K, V, S> RawEntryApiV1<K, V, S> for IndexMap<K, V, S> { + fn raw_entry_v1(&self) -> RawEntryBuilder<'_, K, V, S> { + RawEntryBuilder { map: self } + } + + fn raw_entry_mut_v1(&mut self) -> RawEntryBuilderMut<'_, K, V, S> { + RawEntryBuilderMut { map: self } + } +} + +/// A builder for computing where in an [`IndexMap`] a key-value pair would be stored. +/// +/// This `struct` is created by the [`IndexMap::raw_entry_v1`] method, provided by the +/// [`RawEntryApiV1`] trait. See its documentation for more. +pub struct RawEntryBuilder<'a, K, V, S> { + map: &'a IndexMap<K, V, S>, +} + +impl<K, V, S> fmt::Debug for RawEntryBuilder<'_, K, V, S> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("RawEntryBuilder").finish_non_exhaustive() + } +} + +impl<'a, K, V, S> RawEntryBuilder<'a, K, V, S> { + /// Access an entry by key. + pub fn from_key<Q>(self, key: &Q) -> Option<(&'a K, &'a V)> + where + S: BuildHasher, + Q: ?Sized + Hash + Equivalent<K>, + { + self.map.get_key_value(key) + } + + /// Access an entry by a key and its hash. + pub fn from_key_hashed_nocheck<Q>(self, hash: u64, key: &Q) -> Option<(&'a K, &'a V)> + where + Q: ?Sized + Equivalent<K>, + { + let hash = HashValue(hash as usize); + let i = self.map.core.get_index_of(hash, key)?; + self.map.get_index(i) + } + + /// Access an entry by hash. + pub fn from_hash<F>(self, hash: u64, is_match: F) -> Option<(&'a K, &'a V)> + where + F: FnMut(&K) -> bool, + { + let map = self.map; + let i = self.index_from_hash(hash, is_match)?; + map.get_index(i) + } + + /// Access an entry by hash, including its index. + pub fn from_hash_full<F>(self, hash: u64, is_match: F) -> Option<(usize, &'a K, &'a V)> + where + F: FnMut(&K) -> bool, + { + let map = self.map; + let i = self.index_from_hash(hash, is_match)?; + let (key, value) = map.get_index(i)?; + Some((i, key, value)) + } + + /// Access the index of an entry by hash. + pub fn index_from_hash<F>(self, hash: u64, mut is_match: F) -> Option<usize> + where + F: FnMut(&K) -> bool, + { + let hash = HashValue(hash as usize); + let entries = &*self.map.core.entries; + let eq = move |&i: &usize| is_match(&entries[i].key); + self.map.core.indices.get(hash.get(), eq).copied() + } +} + +/// A builder for computing where in an [`IndexMap`] a key-value pair would be stored. +/// +/// This `struct` is created by the [`IndexMap::raw_entry_mut_v1`] method, provided by the +/// [`RawEntryApiV1`] trait. See its documentation for more. +pub struct RawEntryBuilderMut<'a, K, V, S> { + map: &'a mut IndexMap<K, V, S>, +} + +impl<K, V, S> fmt::Debug for RawEntryBuilderMut<'_, K, V, S> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("RawEntryBuilderMut").finish_non_exhaustive() + } +} + +impl<'a, K, V, S> RawEntryBuilderMut<'a, K, V, S> { + /// Access an entry by key. + pub fn from_key<Q>(self, key: &Q) -> RawEntryMut<'a, K, V, S> + where + S: BuildHasher, + Q: ?Sized + Hash + Equivalent<K>, + { + let hash = self.map.hash(key); + self.from_key_hashed_nocheck(hash.get(), key) + } + + /// Access an entry by a key and its hash. + pub fn from_key_hashed_nocheck<Q>(self, hash: u64, key: &Q) -> RawEntryMut<'a, K, V, S> + where + Q: ?Sized + Equivalent<K>, + { + self.from_hash(hash, |k| Q::equivalent(key, k)) + } + + /// Access an entry by hash. + pub fn from_hash<F>(self, hash: u64, is_match: F) -> RawEntryMut<'a, K, V, S> + where + F: FnMut(&K) -> bool, + { + let hash = HashValue(hash as usize); + match self.map.core.raw_entry(hash, is_match) { + Ok(raw) => RawEntryMut::Occupied(RawOccupiedEntryMut { + raw, + hash_builder: PhantomData, + }), + Err(map) => RawEntryMut::Vacant(RawVacantEntryMut { + map, + hash_builder: &self.map.hash_builder, + }), + } + } +} + +/// Raw entry for an existing key-value pair or a vacant location to +/// insert one. +pub enum RawEntryMut<'a, K, V, S> { + /// Existing slot with equivalent key. + Occupied(RawOccupiedEntryMut<'a, K, V, S>), + /// Vacant slot (no equivalent key in the map). + Vacant(RawVacantEntryMut<'a, K, V, S>), +} + +impl<K: fmt::Debug, V: fmt::Debug, S> fmt::Debug for RawEntryMut<'_, K, V, S> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let mut tuple = f.debug_tuple("RawEntryMut"); + match self { + Self::Vacant(v) => tuple.field(v), + Self::Occupied(o) => tuple.field(o), + }; + tuple.finish() + } +} + +impl<'a, K, V, S> RawEntryMut<'a, K, V, S> { + /// Return the index where the key-value pair exists or may be inserted. + #[inline] + pub fn index(&self) -> usize { + match self { + Self::Occupied(entry) => entry.index(), + Self::Vacant(entry) => entry.index(), + } + } + + /// Inserts the given default key and value in the entry if it is vacant and returns mutable + /// references to them. Otherwise mutable references to an already existent pair are returned. + pub fn or_insert(self, default_key: K, default_value: V) -> (&'a mut K, &'a mut V) + where + K: Hash, + S: BuildHasher, + { + match self { + Self::Occupied(entry) => entry.into_key_value_mut(), + Self::Vacant(entry) => entry.insert(default_key, default_value), + } + } + + /// Inserts the result of the `call` function in the entry if it is vacant and returns mutable + /// references to them. Otherwise mutable references to an already existent pair are returned. + pub fn or_insert_with<F>(self, call: F) -> (&'a mut K, &'a mut V) + where + F: FnOnce() -> (K, V), + K: Hash, + S: BuildHasher, + { + match self { + Self::Occupied(entry) => entry.into_key_value_mut(), + Self::Vacant(entry) => { + let (key, value) = call(); + entry.insert(key, value) + } + } + } + + /// Modifies the entry if it is occupied. + pub fn and_modify<F>(mut self, f: F) -> Self + where + F: FnOnce(&mut K, &mut V), + { + if let Self::Occupied(entry) = &mut self { + let (k, v) = entry.get_key_value_mut(); + f(k, v); + } + self + } +} + +/// A raw view into an occupied entry in an [`IndexMap`]. +/// It is part of the [`RawEntryMut`] enum. +pub struct RawOccupiedEntryMut<'a, K, V, S> { + raw: RawTableEntry<'a, K, V>, + hash_builder: PhantomData<&'a S>, +} + +impl<K: fmt::Debug, V: fmt::Debug, S> fmt::Debug for RawOccupiedEntryMut<'_, K, V, S> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("RawOccupiedEntryMut") + .field("key", self.key()) + .field("value", self.get()) + .finish_non_exhaustive() + } +} + +impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> { + /// Return the index of the key-value pair + #[inline] + pub fn index(&self) -> usize { + self.raw.index() + } + + /// 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.raw.bucket().key + } + + /// Gets a mutable 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_mut(&mut self) -> &mut K { + &mut self.raw.bucket_mut().key + } + + /// Converts into a mutable reference to the entry's key in the map, + /// with a lifetime bound to the map itself. + /// + /// 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 into_key(self) -> &'a mut K { + &mut self.raw.into_bucket().key + } + + /// Gets a reference to the entry's value in the map. + pub fn get(&self) -> &V { + &self.raw.bucket().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 + /// [`RawEntryMut`] value, see [`into_mut`][Self::into_mut]. + pub fn get_mut(&mut self) -> &mut V { + &mut self.raw.bucket_mut().value + } + + /// 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 { + &mut self.raw.into_bucket().value + } + + /// Gets a reference to the entry's key and value in the map. + pub fn get_key_value(&self) -> (&K, &V) { + self.raw.bucket().refs() + } + + /// Gets a reference to the entry's key and value in the map. + pub fn get_key_value_mut(&mut self) -> (&mut K, &mut V) { + self.raw.bucket_mut().muts() + } + + /// Converts into a mutable reference to the entry's key and value in the map, + /// with a lifetime bound to the map itself. + pub fn into_key_value_mut(self) -> (&'a mut K, &'a mut V) { + self.raw.into_bucket().muts() + } + + /// Sets the value of the entry, and returns the entry's old value. + pub fn insert(&mut self, value: V) -> V { + mem::replace(self.get_mut(), value) + } + + /// Sets the key of the entry, and returns the entry's old key. + pub fn insert_key(&mut self, key: K) -> K { + mem::replace(self.key_mut(), key) + } + + /// Remove the key, value pair stored in the map for this entry, and return the value. + /// + /// **NOTE:** This is equivalent to [`.swap_remove()`][Self::swap_remove], replacing this + /// entry's position with the last element, and it is deprecated in favor of calling that + /// explicitly. If you need to preserve the relative order of the keys in the map, use + /// [`.shift_remove()`][Self::shift_remove] instead. + #[deprecated(note = "`remove` disrupts the map order -- \ + use `swap_remove` or `shift_remove` for explicit behavior.")] + 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`][crate::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`][crate::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()`][Self::swap_remove_entry], + /// replacing this entry's position with the last element, and it is deprecated in favor of + /// calling that explicitly. If you need to preserve the relative order of the keys in the map, + /// use [`.shift_remove_entry()`][Self::shift_remove_entry] instead. + #[deprecated(note = "`remove_entry` disrupts the map order -- \ + use `swap_remove_entry` or `shift_remove_entry` for explicit behavior.")] + pub fn remove_entry(self) -> (K, V) { + self.swap_remove_entry() + } + + /// Remove and return the key, value pair stored in the map for this entry + /// + /// Like [`Vec::swap_remove`][crate::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) { + let (map, index) = self.raw.remove_index(); + map.swap_remove_finish(index) + } + + /// Remove and return the key, value pair stored in the map for this entry + /// + /// Like [`Vec::remove`][crate::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) { + let (map, index) = self.raw.remove_index(); + map.shift_remove_finish(index) + } + + /// Moves the position of the entry to a new index + /// by shifting all other entries in-between. + /// + /// This is equivalent to [`IndexMap::move_index`] + /// coming `from` the current [`.index()`][Self::index]. + /// + /// * If `self.index() < to`, the other pairs will shift down while the targeted pair moves up. + /// * If `self.index() > to`, the other pairs will shift up while the targeted pair moves down. + /// + /// ***Panics*** if `to` is out of bounds. + /// + /// Computes in **O(n)** time (average). + pub fn move_index(self, to: usize) { + let (map, index) = self.raw.into_inner(); + map.move_index(index, to); + } + + /// Swaps the position of entry with another. + /// + /// This is equivalent to [`IndexMap::swap_indices`] + /// with the current [`.index()`][Self::index] as one of the two being swapped. + /// + /// ***Panics*** if the `other` index is out of bounds. + /// + /// Computes in **O(1)** time (average). + pub fn swap_indices(self, other: usize) { + let (map, index) = self.raw.into_inner(); + map.swap_indices(index, other) + } +} + +/// A view into a vacant raw entry in an [`IndexMap`]. +/// It is part of the [`RawEntryMut`] enum. +pub struct RawVacantEntryMut<'a, K, V, S> { + map: &'a mut IndexMapCore<K, V>, + hash_builder: &'a S, +} + +impl<K, V, S> fmt::Debug for RawVacantEntryMut<'_, K, V, S> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("RawVacantEntryMut").finish_non_exhaustive() + } +} + +impl<'a, K, V, S> RawVacantEntryMut<'a, K, V, S> { + /// Return the index where a key-value pair may be inserted. + pub fn index(&self) -> usize { + self.map.indices.len() + } + + /// Inserts the given key and value into the map, + /// and returns mutable references to them. + pub fn insert(self, key: K, value: V) -> (&'a mut K, &'a mut V) + where + K: Hash, + S: BuildHasher, + { + let mut h = self.hash_builder.build_hasher(); + key.hash(&mut h); + self.insert_hashed_nocheck(h.finish(), key, value) + } + + /// Inserts the given key and value into the map with the provided hash, + /// and returns mutable references to them. + pub fn insert_hashed_nocheck(self, hash: u64, key: K, value: V) -> (&'a mut K, &'a mut V) { + let hash = HashValue(hash as usize); + let i = self.map.insert_unique(hash, key, value); + self.map.entries[i].muts() + } + + /// Inserts the given key and value into the map at the given index, + /// shifting others to the right, and returns mutable references to them. + /// + /// ***Panics*** if `index` is out of bounds. + /// + /// Computes in **O(n)** time (average). + pub fn shift_insert(self, index: usize, key: K, value: V) -> (&'a mut K, &'a mut V) + where + K: Hash, + S: BuildHasher, + { + let mut h = self.hash_builder.build_hasher(); + key.hash(&mut h); + self.shift_insert_hashed_nocheck(index, h.finish(), key, value) + } + + /// Inserts the given key and value into the map with the provided hash + /// at the given index, and returns mutable references to them. + /// + /// ***Panics*** if `index` is out of bounds. + /// + /// Computes in **O(n)** time (average). + pub fn shift_insert_hashed_nocheck( + self, + index: usize, + hash: u64, + key: K, + value: V, + ) -> (&'a mut K, &'a mut V) { + let hash = HashValue(hash as usize); + self.map.shift_insert_unique(index, hash, key, value); + self.map.entries[index].muts() + } +} + +mod private { + pub trait Sealed {} + + impl<K, V, S> Sealed for super::IndexMap<K, V, S> {} +} diff --git a/third_party/rust/indexmap/src/map/iter.rs b/third_party/rust/indexmap/src/map/iter.rs new file mode 100644 index 0000000000..1ec3703cfb --- /dev/null +++ b/third_party/rust/indexmap/src/map/iter.rs @@ -0,0 +1,713 @@ +use super::core::IndexMapCore; +use super::{Bucket, Entries, IndexMap, Slice}; + +use alloc::vec::{self, Vec}; +use core::fmt; +use core::hash::{BuildHasher, Hash}; +use core::iter::FusedIterator; +use core::ops::{Index, RangeBounds}; +use core::slice; + +impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S> { + type Item = (&'a K, &'a V); + type IntoIter = Iter<'a, K, V>; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S> { + type Item = (&'a K, &'a mut V); + type IntoIter = IterMut<'a, K, V>; + + fn into_iter(self) -> Self::IntoIter { + self.iter_mut() + } +} + +impl<K, V, S> IntoIterator for IndexMap<K, V, S> { + type Item = (K, V); + type IntoIter = IntoIter<K, V>; + + fn into_iter(self) -> Self::IntoIter { + IntoIter::new(self.into_entries()) + } +} + +/// An iterator over the entries of an [`IndexMap`]. +/// +/// This `struct` is created by the [`IndexMap::iter`] method. +/// See its documentation for more. +pub struct Iter<'a, K, V> { + iter: slice::Iter<'a, Bucket<K, V>>, +} + +impl<'a, K, V> Iter<'a, K, V> { + pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self { + Self { + iter: entries.iter(), + } + } + + /// Returns a slice of the remaining entries in the iterator. + pub fn as_slice(&self) -> &'a Slice<K, V> { + Slice::from_slice(self.iter.as_slice()) + } +} + +impl<'a, K, V> Iterator for Iter<'a, K, V> { + type Item = (&'a K, &'a V); + + iterator_methods!(Bucket::refs); +} + +impl<K, V> DoubleEndedIterator for Iter<'_, K, V> { + double_ended_iterator_methods!(Bucket::refs); +} + +impl<K, V> ExactSizeIterator for Iter<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for Iter<'_, K, V> {} + +// FIXME(#26925) Remove in favor of `#[derive(Clone)]` +impl<K, V> Clone for Iter<'_, K, V> { + fn clone(&self) -> Self { + Iter { + iter: self.iter.clone(), + } + } +} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<K, V> Default for Iter<'_, K, V> { + fn default() -> Self { + Self { iter: [].iter() } + } +} + +/// A mutable iterator over the entries of an [`IndexMap`]. +/// +/// This `struct` is created by the [`IndexMap::iter_mut`] method. +/// See its documentation for more. +pub struct IterMut<'a, K, V> { + iter: slice::IterMut<'a, Bucket<K, V>>, +} + +impl<'a, K, V> IterMut<'a, K, V> { + pub(super) fn new(entries: &'a mut [Bucket<K, V>]) -> Self { + Self { + iter: entries.iter_mut(), + } + } + + /// Returns a slice of the remaining entries in the iterator. + pub fn as_slice(&self) -> &Slice<K, V> { + Slice::from_slice(self.iter.as_slice()) + } + + /// Returns a mutable slice of the remaining entries in the iterator. + /// + /// To avoid creating `&mut` references that alias, this is forced to consume the iterator. + pub fn into_slice(self) -> &'a mut Slice<K, V> { + Slice::from_mut_slice(self.iter.into_slice()) + } +} + +impl<'a, K, V> Iterator for IterMut<'a, K, V> { + type Item = (&'a K, &'a mut V); + + iterator_methods!(Bucket::ref_mut); +} + +impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> { + double_ended_iterator_methods!(Bucket::ref_mut); +} + +impl<K, V> ExactSizeIterator for IterMut<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for IterMut<'_, K, V> {} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.iter.as_slice().iter().map(Bucket::refs); + f.debug_list().entries(iter).finish() + } +} + +impl<K, V> Default for IterMut<'_, K, V> { + fn default() -> Self { + Self { + iter: [].iter_mut(), + } + } +} + +/// An owning iterator over the entries of an [`IndexMap`]. +/// +/// This `struct` is created by the [`IndexMap::into_iter`] method +/// (provided by the [`IntoIterator`] trait). See its documentation for more. +pub struct IntoIter<K, V> { + iter: vec::IntoIter<Bucket<K, V>>, +} + +impl<K, V> IntoIter<K, V> { + pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self { + Self { + iter: entries.into_iter(), + } + } + + /// Returns a slice of the remaining entries in the iterator. + pub fn as_slice(&self) -> &Slice<K, V> { + Slice::from_slice(self.iter.as_slice()) + } + + /// Returns a mutable slice of the remaining entries in the iterator. + pub fn as_mut_slice(&mut self) -> &mut Slice<K, V> { + Slice::from_mut_slice(self.iter.as_mut_slice()) + } +} + +impl<K, V> Iterator for IntoIter<K, V> { + type Item = (K, V); + + iterator_methods!(Bucket::key_value); +} + +impl<K, V> DoubleEndedIterator for IntoIter<K, V> { + double_ended_iterator_methods!(Bucket::key_value); +} + +impl<K, V> ExactSizeIterator for IntoIter<K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for IntoIter<K, V> {} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.iter.as_slice().iter().map(Bucket::refs); + f.debug_list().entries(iter).finish() + } +} + +impl<K, V> Default for IntoIter<K, V> { + fn default() -> Self { + Self { + iter: Vec::new().into_iter(), + } + } +} + +/// A draining iterator over the entries of an [`IndexMap`]. +/// +/// This `struct` is created by the [`IndexMap::drain`] method. +/// See its documentation for more. +pub struct Drain<'a, K, V> { + iter: vec::Drain<'a, Bucket<K, V>>, +} + +impl<'a, K, V> Drain<'a, K, V> { + pub(super) fn new(iter: vec::Drain<'a, Bucket<K, V>>) -> Self { + Self { iter } + } + + /// Returns a slice of the remaining entries in the iterator. + pub fn as_slice(&self) -> &Slice<K, V> { + Slice::from_slice(self.iter.as_slice()) + } +} + +impl<K, V> Iterator for Drain<'_, K, V> { + type Item = (K, V); + + iterator_methods!(Bucket::key_value); +} + +impl<K, V> DoubleEndedIterator for Drain<'_, K, V> { + double_ended_iterator_methods!(Bucket::key_value); +} + +impl<K, V> ExactSizeIterator for Drain<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for Drain<'_, K, V> {} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Drain<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.iter.as_slice().iter().map(Bucket::refs); + f.debug_list().entries(iter).finish() + } +} + +/// An iterator over the keys of an [`IndexMap`]. +/// +/// This `struct` is created by the [`IndexMap::keys`] method. +/// See its documentation for more. +pub struct Keys<'a, K, V> { + iter: slice::Iter<'a, Bucket<K, V>>, +} + +impl<'a, K, V> Keys<'a, K, V> { + pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self { + Self { + iter: entries.iter(), + } + } +} + +impl<'a, K, V> Iterator for Keys<'a, K, V> { + type Item = &'a K; + + iterator_methods!(Bucket::key_ref); +} + +impl<K, V> DoubleEndedIterator for Keys<'_, K, V> { + double_ended_iterator_methods!(Bucket::key_ref); +} + +impl<K, V> ExactSizeIterator for Keys<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for Keys<'_, K, V> {} + +// FIXME(#26925) Remove in favor of `#[derive(Clone)]` +impl<K, V> Clone for Keys<'_, K, V> { + fn clone(&self) -> Self { + Keys { + iter: self.iter.clone(), + } + } +} + +impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<K, V> Default for Keys<'_, K, V> { + fn default() -> Self { + Self { iter: [].iter() } + } +} + +/// Access [`IndexMap`] keys at indexed positions. +/// +/// While [`Index<usize> for IndexMap`][values] accesses a map's values, +/// indexing through [`IndexMap::keys`] offers an alternative to access a map's +/// keys instead. +/// +/// [values]: IndexMap#impl-Index<usize>-for-IndexMap<K,+V,+S> +/// +/// Since `Keys` is also an iterator, consuming items from the iterator will +/// offset the effective indexes. Similarly, if `Keys` is obtained from +/// [`Slice::keys`], indexes will be interpreted relative to the position of +/// that slice. +/// +/// # 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.keys()[0], "lorem"); +/// assert_eq!(map[1], "IPSUM"); +/// assert_eq!(map.keys()[1], "ipsum"); +/// +/// map.reverse(); +/// assert_eq!(map.keys()[0], "amet"); +/// assert_eq!(map.keys()[1], "sit"); +/// +/// map.sort_keys(); +/// assert_eq!(map.keys()[0], "amet"); +/// assert_eq!(map.keys()[1], "dolor"); +/// +/// // Advancing the iterator will offset the indexing +/// let mut keys = map.keys(); +/// assert_eq!(keys[0], "amet"); +/// assert_eq!(keys.next().map(|s| &**s), Some("amet")); +/// assert_eq!(keys[0], "dolor"); +/// assert_eq!(keys[1], "ipsum"); +/// +/// // Slices may have an offset as well +/// let slice = &map[2..]; +/// assert_eq!(slice[0], "IPSUM"); +/// assert_eq!(slice.keys()[0], "ipsum"); +/// ``` +/// +/// ```should_panic +/// use indexmap::IndexMap; +/// +/// let mut map = IndexMap::new(); +/// map.insert("foo", 1); +/// println!("{:?}", map.keys()[10]); // panics! +/// ``` +impl<'a, K, V> Index<usize> for Keys<'a, K, V> { + type Output = K; + + /// Returns a reference to the key at the supplied `index`. + /// + /// ***Panics*** if `index` is out of bounds. + fn index(&self, index: usize) -> &K { + &self.iter.as_slice()[index].key + } +} + +/// An owning iterator over the keys of an [`IndexMap`]. +/// +/// This `struct` is created by the [`IndexMap::into_keys`] method. +/// See its documentation for more. +pub struct IntoKeys<K, V> { + iter: vec::IntoIter<Bucket<K, V>>, +} + +impl<K, V> IntoKeys<K, V> { + pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self { + Self { + iter: entries.into_iter(), + } + } +} + +impl<K, V> Iterator for IntoKeys<K, V> { + type Item = K; + + iterator_methods!(Bucket::key); +} + +impl<K, V> DoubleEndedIterator for IntoKeys<K, V> { + double_ended_iterator_methods!(Bucket::key); +} + +impl<K, V> ExactSizeIterator for IntoKeys<K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for IntoKeys<K, V> {} + +impl<K: fmt::Debug, V> fmt::Debug for IntoKeys<K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.iter.as_slice().iter().map(Bucket::key_ref); + f.debug_list().entries(iter).finish() + } +} + +impl<K, V> Default for IntoKeys<K, V> { + fn default() -> Self { + Self { + iter: Vec::new().into_iter(), + } + } +} + +/// An iterator over the values of an [`IndexMap`]. +/// +/// This `struct` is created by the [`IndexMap::values`] method. +/// See its documentation for more. +pub struct Values<'a, K, V> { + iter: slice::Iter<'a, Bucket<K, V>>, +} + +impl<'a, K, V> Values<'a, K, V> { + pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self { + Self { + iter: entries.iter(), + } + } +} + +impl<'a, K, V> Iterator for Values<'a, K, V> { + type Item = &'a V; + + iterator_methods!(Bucket::value_ref); +} + +impl<K, V> DoubleEndedIterator for Values<'_, K, V> { + double_ended_iterator_methods!(Bucket::value_ref); +} + +impl<K, V> ExactSizeIterator for Values<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for Values<'_, K, V> {} + +// FIXME(#26925) Remove in favor of `#[derive(Clone)]` +impl<K, V> Clone for Values<'_, K, V> { + fn clone(&self) -> Self { + Values { + iter: self.iter.clone(), + } + } +} + +impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +impl<K, V> Default for Values<'_, K, V> { + fn default() -> Self { + Self { iter: [].iter() } + } +} + +/// A mutable iterator over the values of an [`IndexMap`]. +/// +/// This `struct` is created by the [`IndexMap::values_mut`] method. +/// See its documentation for more. +pub struct ValuesMut<'a, K, V> { + iter: slice::IterMut<'a, Bucket<K, V>>, +} + +impl<'a, K, V> ValuesMut<'a, K, V> { + pub(super) fn new(entries: &'a mut [Bucket<K, V>]) -> Self { + Self { + iter: entries.iter_mut(), + } + } +} + +impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { + type Item = &'a mut V; + + iterator_methods!(Bucket::value_mut); +} + +impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> { + double_ended_iterator_methods!(Bucket::value_mut); +} + +impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for ValuesMut<'_, K, V> {} + +impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.iter.as_slice().iter().map(Bucket::value_ref); + f.debug_list().entries(iter).finish() + } +} + +impl<K, V> Default for ValuesMut<'_, K, V> { + fn default() -> Self { + Self { + iter: [].iter_mut(), + } + } +} + +/// An owning iterator over the values of an [`IndexMap`]. +/// +/// This `struct` is created by the [`IndexMap::into_values`] method. +/// See its documentation for more. +pub struct IntoValues<K, V> { + iter: vec::IntoIter<Bucket<K, V>>, +} + +impl<K, V> IntoValues<K, V> { + pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self { + Self { + iter: entries.into_iter(), + } + } +} + +impl<K, V> Iterator for IntoValues<K, V> { + type Item = V; + + iterator_methods!(Bucket::value); +} + +impl<K, V> DoubleEndedIterator for IntoValues<K, V> { + double_ended_iterator_methods!(Bucket::value); +} + +impl<K, V> ExactSizeIterator for IntoValues<K, V> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<K, V> FusedIterator for IntoValues<K, V> {} + +impl<K, V: fmt::Debug> fmt::Debug for IntoValues<K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = self.iter.as_slice().iter().map(Bucket::value_ref); + f.debug_list().entries(iter).finish() + } +} + +impl<K, V> Default for IntoValues<K, V> { + fn default() -> Self { + Self { + iter: Vec::new().into_iter(), + } + } +} + +/// A splicing iterator for `IndexMap`. +/// +/// This `struct` is created by [`IndexMap::splice()`]. +/// See its documentation for more. +pub struct Splice<'a, I, K, V, S> +where + I: Iterator<Item = (K, V)>, + K: Hash + Eq, + S: BuildHasher, +{ + map: &'a mut IndexMap<K, V, S>, + tail: IndexMapCore<K, V>, + drain: vec::IntoIter<Bucket<K, V>>, + replace_with: I, +} + +impl<'a, I, K, V, S> Splice<'a, I, K, V, S> +where + I: Iterator<Item = (K, V)>, + K: Hash + Eq, + S: BuildHasher, +{ + pub(super) fn new<R>(map: &'a mut IndexMap<K, V, S>, range: R, replace_with: I) -> Self + where + R: RangeBounds<usize>, + { + let (tail, drain) = map.core.split_splice(range); + Self { + map, + tail, + drain, + replace_with, + } + } +} + +impl<I, K, V, S> Drop for Splice<'_, I, K, V, S> +where + I: Iterator<Item = (K, V)>, + K: Hash + Eq, + S: BuildHasher, +{ + fn drop(&mut self) { + // Finish draining unconsumed items. We don't strictly *have* to do this + // manually, since we already split it into separate memory, but it will + // match the drop order of `vec::Splice` items this way. + let _ = self.drain.nth(usize::MAX); + + // Now insert all the new items. If a key matches an existing entry, it + // keeps the original position and only replaces the value, like `insert`. + while let Some((key, value)) = self.replace_with.next() { + // Since the tail is disjoint, we can try to update it first, + // or else insert (update or append) the primary map. + let hash = self.map.hash(&key); + if let Some(i) = self.tail.get_index_of(hash, &key) { + self.tail.as_entries_mut()[i].value = value; + } else { + self.map.core.insert_full(hash, key, value); + } + } + + // Finally, re-append the tail + self.map.core.append_unchecked(&mut self.tail); + } +} + +impl<I, K, V, S> Iterator for Splice<'_, I, K, V, S> +where + I: Iterator<Item = (K, V)>, + K: Hash + Eq, + S: BuildHasher, +{ + type Item = (K, V); + + fn next(&mut self) -> Option<Self::Item> { + self.drain.next().map(Bucket::key_value) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.drain.size_hint() + } +} + +impl<I, K, V, S> DoubleEndedIterator for Splice<'_, I, K, V, S> +where + I: Iterator<Item = (K, V)>, + K: Hash + Eq, + S: BuildHasher, +{ + fn next_back(&mut self) -> Option<Self::Item> { + self.drain.next_back().map(Bucket::key_value) + } +} + +impl<I, K, V, S> ExactSizeIterator for Splice<'_, I, K, V, S> +where + I: Iterator<Item = (K, V)>, + K: Hash + Eq, + S: BuildHasher, +{ + fn len(&self) -> usize { + self.drain.len() + } +} + +impl<I, K, V, S> FusedIterator for Splice<'_, I, K, V, S> +where + I: Iterator<Item = (K, V)>, + K: Hash + Eq, + S: BuildHasher, +{ +} + +impl<'a, I, K, V, S> fmt::Debug for Splice<'a, I, K, V, S> +where + I: fmt::Debug + Iterator<Item = (K, V)>, + K: fmt::Debug + Hash + Eq, + V: fmt::Debug, + S: BuildHasher, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + // Follow `vec::Splice` in only printing the drain and replacement + f.debug_struct("Splice") + .field("drain", &self.drain) + .field("replace_with", &self.replace_with) + .finish() + } +} diff --git a/third_party/rust/indexmap/src/map/mutable.rs b/third_party/rust/indexmap/src/map/mutable.rs new file mode 100644 index 0000000000..7df325948f --- /dev/null +++ b/third_party/rust/indexmap/src/map/mutable.rs @@ -0,0 +1,87 @@ +use core::hash::{BuildHasher, Hash}; + +use super::{Bucket, Entries, Equivalent, IndexMap}; + +/// Opt-in mutable access to [`IndexMap`] 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 map **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`. +/// +/// This trait is sealed and cannot be implemented for types outside this crate. +pub trait MutableKeys: private::Sealed { + type Key; + type Value; + + /// Return item index, mutable reference to key and value + /// + /// Computes in **O(1)** time (average). + fn get_full_mut2<Q>(&mut self, key: &Q) -> Option<(usize, &mut Self::Key, &mut Self::Value)> + where + Q: ?Sized + Hash + Equivalent<Self::Key>; + + /// Return mutable reference to key and value at an index. + /// + /// Valid indices are *0 <= index < self.len()* + /// + /// Computes in **O(1)** time. + fn get_index_mut2(&mut self, index: usize) -> Option<(&mut Self::Key, &mut Self::Value)>; + + /// Scan through each key-value pair in the map and keep those where the + /// closure `keep` returns `true`. + /// + /// 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; +} + +/// Opt-in mutable access to [`IndexMap`] keys. +/// +/// See [`MutableKeys`] for more information. +impl<K, V, S> MutableKeys for IndexMap<K, V, S> +where + S: BuildHasher, +{ + type Key = K; + type Value = V; + + fn get_full_mut2<Q>(&mut self, key: &Q) -> Option<(usize, &mut K, &mut V)> + where + Q: ?Sized + 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 + } + } + + fn get_index_mut2(&mut self, index: usize) -> Option<(&mut K, &mut V)> { + self.as_entries_mut().get_mut(index).map(Bucket::muts) + } + + fn retain2<F>(&mut self, keep: F) + where + F: FnMut(&mut K, &mut V) -> bool, + { + self.core.retain_in_order(keep); + } +} + +mod private { + pub trait Sealed {} + + impl<K, V, S> Sealed for super::IndexMap<K, V, S> {} +} diff --git a/third_party/rust/indexmap/src/map/serde_seq.rs b/third_party/rust/indexmap/src/map/serde_seq.rs new file mode 100644 index 0000000000..602ae7dc74 --- /dev/null +++ b/third_party/rust/indexmap/src/map/serde_seq.rs @@ -0,0 +1,138 @@ +//! 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::map::serde_seq")] +//! map: IndexMap<i32, u64>, +//! // ... +//! } +//! ``` + +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::map::Slice as MapSlice; +use crate::serde::cautious_capacity; +use crate::set::Slice as SetSlice; +use crate::IndexMap; + +/// Serializes a [`map::Slice`][MapSlice] as an ordered sequence. +/// +/// This behaves like [`crate::map::serde_seq`] for `IndexMap`, serializing a sequence +/// of `(key, value)` pairs, rather than as a map that might not preserve order. +impl<K, V> Serialize for MapSlice<K, V> +where + K: Serialize, + V: Serialize, +{ + fn serialize<T>(&self, serializer: T) -> Result<T::Ok, T::Error> + where + T: Serializer, + { + serializer.collect_seq(self) + } +} + +/// Serializes a [`set::Slice`][SetSlice] as an ordered sequence. +impl<T> Serialize for SetSlice<T> +where + T: Serialize, +{ + fn serialize<Se>(&self, serializer: Se) -> Result<Se::Ok, Se::Error> + where + Se: Serializer, + { + serializer.collect_seq(self) + } +} + +/// Serializes an [`IndexMap`] as an ordered sequence. +/// +/// This function may be used in a field attribute for deriving [`Serialize`]: +/// +/// ``` +/// # use indexmap::IndexMap; +/// # use serde_derive::Serialize; +/// #[derive(Serialize)] +/// struct Data { +/// #[serde(serialize_with = "indexmap::map::serde_seq::serialize")] +/// map: IndexMap<i32, u64>, +/// // ... +/// } +/// ``` +pub fn serialize<K, V, S, T>(map: &IndexMap<K, V, S>, serializer: T) -> Result<T::Ok, T::Error> +where + K: Serialize, + V: Serialize, + 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 = cautious_capacity::<K, V>(seq.size_hint()); + 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::map::serde_seq::deserialize")] +/// map: IndexMap<i32, u64>, +/// // ... +/// } +/// ``` +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/map/slice.rs b/third_party/rust/indexmap/src/map/slice.rs new file mode 100644 index 0000000000..b2f00f4807 --- /dev/null +++ b/third_party/rust/indexmap/src/map/slice.rs @@ -0,0 +1,539 @@ +use super::{ + Bucket, Entries, IndexMap, IntoIter, IntoKeys, IntoValues, Iter, IterMut, Keys, Values, + ValuesMut, +}; +use crate::util::try_simplify_range; + +use alloc::boxed::Box; +use alloc::vec::Vec; +use core::cmp::Ordering; +use core::fmt; +use core::hash::{Hash, Hasher}; +use core::ops::{self, Bound, Index, IndexMut, RangeBounds}; + +/// A dynamically-sized slice of key-value pairs in an [`IndexMap`]. +/// +/// This supports indexed operations much like a `[(K, V)]` slice, +/// but not any hashed operations on the map keys. +/// +/// Unlike `IndexMap`, `Slice` does consider the order for [`PartialEq`] +/// and [`Eq`], and it also implements [`PartialOrd`], [`Ord`], and [`Hash`]. +#[repr(transparent)] +pub struct Slice<K, V> { + pub(crate) entries: [Bucket<K, V>], +} + +// SAFETY: `Slice<K, V>` is a transparent wrapper around `[Bucket<K, V>]`, +// and reference lifetimes are bound together in function signatures. +#[allow(unsafe_code)] +impl<K, V> Slice<K, V> { + pub(super) const fn from_slice(entries: &[Bucket<K, V>]) -> &Self { + unsafe { &*(entries as *const [Bucket<K, V>] as *const Self) } + } + + pub(super) fn from_mut_slice(entries: &mut [Bucket<K, V>]) -> &mut Self { + unsafe { &mut *(entries as *mut [Bucket<K, V>] as *mut Self) } + } + + pub(super) fn from_boxed(entries: Box<[Bucket<K, V>]>) -> Box<Self> { + unsafe { Box::from_raw(Box::into_raw(entries) as *mut Self) } + } + + fn into_boxed(self: Box<Self>) -> Box<[Bucket<K, V>]> { + unsafe { Box::from_raw(Box::into_raw(self) as *mut [Bucket<K, V>]) } + } +} + +impl<K, V> Slice<K, V> { + pub(crate) fn into_entries(self: Box<Self>) -> Vec<Bucket<K, V>> { + self.into_boxed().into_vec() + } + + /// Returns an empty slice. + pub const fn new<'a>() -> &'a Self { + Self::from_slice(&[]) + } + + /// Returns an empty mutable slice. + pub fn new_mut<'a>() -> &'a mut Self { + Self::from_mut_slice(&mut []) + } + + /// Return the number of key-value pairs in the map slice. + #[inline] + pub const fn len(&self) -> usize { + self.entries.len() + } + + /// Returns true if the map slice contains no elements. + #[inline] + pub const fn is_empty(&self) -> bool { + self.entries.is_empty() + } + + /// Get a key-value pair by index. + /// + /// Valid indices are *0 <= index < self.len()* + pub fn get_index(&self, index: usize) -> Option<(&K, &V)> { + self.entries.get(index).map(Bucket::refs) + } + + /// Get a key-value pair by index, with mutable access to the value. + /// + /// Valid indices are *0 <= index < self.len()* + pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)> { + self.entries.get_mut(index).map(Bucket::ref_mut) + } + + /// Returns a slice of key-value pairs in the given range of indices. + /// + /// Valid indices are *0 <= index < self.len()* + pub fn get_range<R: RangeBounds<usize>>(&self, range: R) -> Option<&Self> { + let range = try_simplify_range(range, self.entries.len())?; + self.entries.get(range).map(Slice::from_slice) + } + + /// Returns a mutable slice of key-value pairs in the given range of indices. + /// + /// Valid indices are *0 <= index < self.len()* + pub fn get_range_mut<R: RangeBounds<usize>>(&mut self, range: R) -> Option<&mut Self> { + let range = try_simplify_range(range, self.entries.len())?; + self.entries.get_mut(range).map(Slice::from_mut_slice) + } + + /// Get the first key-value pair. + pub fn first(&self) -> Option<(&K, &V)> { + self.entries.first().map(Bucket::refs) + } + + /// Get the first key-value pair, with mutable access to the value. + pub fn first_mut(&mut self) -> Option<(&K, &mut V)> { + self.entries.first_mut().map(Bucket::ref_mut) + } + + /// Get the last key-value pair. + pub fn last(&self) -> Option<(&K, &V)> { + self.entries.last().map(Bucket::refs) + } + + /// Get the last key-value pair, with mutable access to the value. + pub fn last_mut(&mut self) -> Option<(&K, &mut V)> { + self.entries.last_mut().map(Bucket::ref_mut) + } + + /// Divides one slice into two at an index. + /// + /// ***Panics*** if `index > len`. + pub fn split_at(&self, index: usize) -> (&Self, &Self) { + let (first, second) = self.entries.split_at(index); + (Self::from_slice(first), Self::from_slice(second)) + } + + /// Divides one mutable slice into two at an index. + /// + /// ***Panics*** if `index > len`. + pub fn split_at_mut(&mut self, index: usize) -> (&mut Self, &mut Self) { + let (first, second) = self.entries.split_at_mut(index); + (Self::from_mut_slice(first), Self::from_mut_slice(second)) + } + + /// Returns the first key-value pair and the rest of the slice, + /// or `None` if it is empty. + pub fn split_first(&self) -> Option<((&K, &V), &Self)> { + if let [first, rest @ ..] = &self.entries { + Some((first.refs(), Self::from_slice(rest))) + } else { + None + } + } + + /// Returns the first key-value pair and the rest of the slice, + /// with mutable access to the value, or `None` if it is empty. + pub fn split_first_mut(&mut self) -> Option<((&K, &mut V), &mut Self)> { + if let [first, rest @ ..] = &mut self.entries { + Some((first.ref_mut(), Self::from_mut_slice(rest))) + } else { + None + } + } + + /// Returns the last key-value pair and the rest of the slice, + /// or `None` if it is empty. + pub fn split_last(&self) -> Option<((&K, &V), &Self)> { + if let [rest @ .., last] = &self.entries { + Some((last.refs(), Self::from_slice(rest))) + } else { + None + } + } + + /// Returns the last key-value pair and the rest of the slice, + /// with mutable access to the value, or `None` if it is empty. + pub fn split_last_mut(&mut self) -> Option<((&K, &mut V), &mut Self)> { + if let [rest @ .., last] = &mut self.entries { + Some((last.ref_mut(), Self::from_mut_slice(rest))) + } else { + None + } + } + + /// Return an iterator over the key-value pairs of the map slice. + pub fn iter(&self) -> Iter<'_, K, V> { + Iter::new(&self.entries) + } + + /// Return an iterator over the key-value pairs of the map slice. + pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { + IterMut::new(&mut self.entries) + } + + /// Return an iterator over the keys of the map slice. + pub fn keys(&self) -> Keys<'_, K, V> { + Keys::new(&self.entries) + } + + /// Return an owning iterator over the keys of the map slice. + pub fn into_keys(self: Box<Self>) -> IntoKeys<K, V> { + IntoKeys::new(self.into_entries()) + } + + /// Return an iterator over the values of the map slice. + pub fn values(&self) -> Values<'_, K, V> { + Values::new(&self.entries) + } + + /// Return an iterator over mutable references to the the values of the map slice. + pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> { + ValuesMut::new(&mut self.entries) + } + + /// Return an owning iterator over the values of the map slice. + pub fn into_values(self: Box<Self>) -> IntoValues<K, V> { + IntoValues::new(self.into_entries()) + } + + /// Search over a sorted map for a key. + /// + /// Returns the position where that key is present, or the position where it can be inserted to + /// maintain the sort. See [`slice::binary_search`] for more details. + /// + /// Computes in **O(log(n))** time, which is notably less scalable than looking the key up in + /// the map this is a slice from using [`IndexMap::get_index_of`], but this can also position + /// missing keys. + pub fn binary_search_keys(&self, x: &K) -> Result<usize, usize> + where + K: Ord, + { + self.binary_search_by(|p, _| p.cmp(x)) + } + + /// Search over a sorted map with a comparator function. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search_by`] for more details. + /// + /// Computes in **O(log(n))** time. + #[inline] + pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize> + where + F: FnMut(&'a K, &'a V) -> Ordering, + { + self.entries.binary_search_by(move |a| f(&a.key, &a.value)) + } + + /// Search over a sorted map with an extraction function. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search_by_key`] for more details. + /// + /// Computes in **O(log(n))** time. + #[inline] + pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize> + where + F: FnMut(&'a K, &'a V) -> B, + B: Ord, + { + self.binary_search_by(|k, v| f(k, v).cmp(b)) + } + + /// Returns the index of the partition point of a sorted map according to the given predicate + /// (the index of the first element of the second partition). + /// + /// See [`slice::partition_point`] for more details. + /// + /// Computes in **O(log(n))** time. + #[must_use] + pub fn partition_point<P>(&self, mut pred: P) -> usize + where + P: FnMut(&K, &V) -> bool, + { + self.entries + .partition_point(move |a| pred(&a.key, &a.value)) + } +} + +impl<'a, K, V> IntoIterator for &'a Slice<K, V> { + type IntoIter = Iter<'a, K, V>; + type Item = (&'a K, &'a V); + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl<'a, K, V> IntoIterator for &'a mut Slice<K, V> { + type IntoIter = IterMut<'a, K, V>; + type Item = (&'a K, &'a mut V); + + fn into_iter(self) -> Self::IntoIter { + self.iter_mut() + } +} + +impl<K, V> IntoIterator for Box<Slice<K, V>> { + type IntoIter = IntoIter<K, V>; + type Item = (K, V); + + fn into_iter(self) -> Self::IntoIter { + IntoIter::new(self.into_entries()) + } +} + +impl<K, V> Default for &'_ Slice<K, V> { + fn default() -> Self { + Slice::from_slice(&[]) + } +} + +impl<K, V> Default for &'_ mut Slice<K, V> { + fn default() -> Self { + Slice::from_mut_slice(&mut []) + } +} + +impl<K, V> Default for Box<Slice<K, V>> { + fn default() -> Self { + Slice::from_boxed(Box::default()) + } +} + +impl<K: Clone, V: Clone> Clone for Box<Slice<K, V>> { + fn clone(&self) -> Self { + Slice::from_boxed(self.entries.to_vec().into_boxed_slice()) + } +} + +impl<K: Copy, V: Copy> From<&Slice<K, V>> for Box<Slice<K, V>> { + fn from(slice: &Slice<K, V>) -> Self { + Slice::from_boxed(Box::from(&slice.entries)) + } +} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Slice<K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self).finish() + } +} + +impl<K: PartialEq, V: PartialEq> PartialEq for Slice<K, V> { + fn eq(&self, other: &Self) -> bool { + self.len() == other.len() && self.iter().eq(other) + } +} + +impl<K: Eq, V: Eq> Eq for Slice<K, V> {} + +impl<K: PartialOrd, V: PartialOrd> PartialOrd for Slice<K, V> { + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + self.iter().partial_cmp(other) + } +} + +impl<K: Ord, V: Ord> Ord for Slice<K, V> { + fn cmp(&self, other: &Self) -> Ordering { + self.iter().cmp(other) + } +} + +impl<K: Hash, V: Hash> Hash for Slice<K, V> { + fn hash<H: Hasher>(&self, state: &mut H) { + self.len().hash(state); + for (key, value) in self { + key.hash(state); + value.hash(state); + } + } +} + +impl<K, V> Index<usize> for Slice<K, V> { + type Output = V; + + fn index(&self, index: usize) -> &V { + &self.entries[index].value + } +} + +impl<K, V> IndexMut<usize> for Slice<K, V> { + fn index_mut(&mut self, index: usize) -> &mut V { + &mut self.entries[index].value + } +} + +// We can't have `impl<I: RangeBounds<usize>> Index<I>` because that conflicts +// both upstream with `Index<usize>` and downstream with `Index<&Q>`. +// Instead, we repeat the implementations for all the core range types. +macro_rules! impl_index { + ($($range:ty),*) => {$( + impl<K, V, S> Index<$range> for IndexMap<K, V, S> { + type Output = Slice<K, V>; + + fn index(&self, range: $range) -> &Self::Output { + Slice::from_slice(&self.as_entries()[range]) + } + } + + impl<K, V, S> IndexMut<$range> for IndexMap<K, V, S> { + fn index_mut(&mut self, range: $range) -> &mut Self::Output { + Slice::from_mut_slice(&mut self.as_entries_mut()[range]) + } + } + + impl<K, V> Index<$range> for Slice<K, V> { + type Output = Slice<K, V>; + + fn index(&self, range: $range) -> &Self { + Self::from_slice(&self.entries[range]) + } + } + + impl<K, V> IndexMut<$range> for Slice<K, V> { + fn index_mut(&mut self, range: $range) -> &mut Self { + Self::from_mut_slice(&mut self.entries[range]) + } + } + )*} +} +impl_index!( + ops::Range<usize>, + ops::RangeFrom<usize>, + ops::RangeFull, + ops::RangeInclusive<usize>, + ops::RangeTo<usize>, + ops::RangeToInclusive<usize>, + (Bound<usize>, Bound<usize>) +); + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn slice_index() { + fn check( + vec_slice: &[(i32, i32)], + map_slice: &Slice<i32, i32>, + sub_slice: &Slice<i32, i32>, + ) { + assert_eq!(map_slice as *const _, sub_slice as *const _); + itertools::assert_equal( + vec_slice.iter().copied(), + map_slice.iter().map(|(&k, &v)| (k, v)), + ); + itertools::assert_equal(vec_slice.iter().map(|(k, _)| k), map_slice.keys()); + itertools::assert_equal(vec_slice.iter().map(|(_, v)| v), map_slice.values()); + } + + let vec: Vec<(i32, i32)> = (0..10).map(|i| (i, i * i)).collect(); + let map: IndexMap<i32, i32> = vec.iter().cloned().collect(); + let slice = map.as_slice(); + + // RangeFull + check(&vec[..], &map[..], &slice[..]); + + for i in 0usize..10 { + // Index + assert_eq!(vec[i].1, map[i]); + assert_eq!(vec[i].1, slice[i]); + assert_eq!(map[&(i as i32)], map[i]); + assert_eq!(map[&(i as i32)], slice[i]); + + // RangeFrom + check(&vec[i..], &map[i..], &slice[i..]); + + // RangeTo + check(&vec[..i], &map[..i], &slice[..i]); + + // RangeToInclusive + check(&vec[..=i], &map[..=i], &slice[..=i]); + + // (Bound<usize>, Bound<usize>) + let bounds = (Bound::Excluded(i), Bound::Unbounded); + check(&vec[i + 1..], &map[bounds], &slice[bounds]); + + for j in i..=10 { + // Range + check(&vec[i..j], &map[i..j], &slice[i..j]); + } + + for j in i..10 { + // RangeInclusive + check(&vec[i..=j], &map[i..=j], &slice[i..=j]); + } + } + } + + #[test] + fn slice_index_mut() { + fn check_mut( + vec_slice: &[(i32, i32)], + map_slice: &mut Slice<i32, i32>, + sub_slice: &mut Slice<i32, i32>, + ) { + assert_eq!(map_slice, sub_slice); + itertools::assert_equal( + vec_slice.iter().copied(), + map_slice.iter_mut().map(|(&k, &mut v)| (k, v)), + ); + itertools::assert_equal( + vec_slice.iter().map(|&(_, v)| v), + map_slice.values_mut().map(|&mut v| v), + ); + } + + let vec: Vec<(i32, i32)> = (0..10).map(|i| (i, i * i)).collect(); + let mut map: IndexMap<i32, i32> = vec.iter().cloned().collect(); + let mut map2 = map.clone(); + let slice = map2.as_mut_slice(); + + // RangeFull + check_mut(&vec[..], &mut map[..], &mut slice[..]); + + for i in 0usize..10 { + // IndexMut + assert_eq!(&mut map[i], &mut slice[i]); + + // RangeFrom + check_mut(&vec[i..], &mut map[i..], &mut slice[i..]); + + // RangeTo + check_mut(&vec[..i], &mut map[..i], &mut slice[..i]); + + // RangeToInclusive + check_mut(&vec[..=i], &mut map[..=i], &mut slice[..=i]); + + // (Bound<usize>, Bound<usize>) + let bounds = (Bound::Excluded(i), Bound::Unbounded); + check_mut(&vec[i + 1..], &mut map[bounds], &mut slice[bounds]); + + for j in i..=10 { + // Range + check_mut(&vec[i..j], &mut map[i..j], &mut slice[i..j]); + } + + for j in i..10 { + // RangeInclusive + check_mut(&vec[i..=j], &mut map[i..=j], &mut slice[i..=j]); + } + } + } +} diff --git a/third_party/rust/indexmap/src/map/tests.rs b/third_party/rust/indexmap/src/map/tests.rs new file mode 100644 index 0000000000..bba78ff54c --- /dev/null +++ b/third_party/rust/indexmap/src/map/tests.rs @@ -0,0 +1,727 @@ +use super::*; +use std::string::String; + +#[test] +fn it_works() { + let mut map = IndexMap::new(); + assert_eq!(map.is_empty(), true); + map.insert(1, ()); + map.insert(1, ()); + assert_eq!(map.len(), 1); + assert!(map.get(&1).is_some()); + assert_eq!(map.is_empty(), false); +} + +#[test] +fn new() { + let map = IndexMap::<String, String>::new(); + println!("{:?}", map); + assert_eq!(map.capacity(), 0); + assert_eq!(map.len(), 0); + assert_eq!(map.is_empty(), true); +} + +#[test] +fn insert() { + let insert = [0, 4, 2, 12, 8, 7, 11, 5]; + let not_present = [1, 3, 6, 9, 10]; + let mut map = IndexMap::with_capacity(insert.len()); + + for (i, &elt) in insert.iter().enumerate() { + assert_eq!(map.len(), i); + map.insert(elt, elt); + assert_eq!(map.len(), i + 1); + assert_eq!(map.get(&elt), Some(&elt)); + assert_eq!(map[&elt], elt); + } + println!("{:?}", map); + + for &elt in ¬_present { + assert!(map.get(&elt).is_none()); + } +} + +#[test] +fn insert_full() { + let insert = vec![9, 2, 7, 1, 4, 6, 13]; + let present = vec![1, 6, 2]; + let mut map = IndexMap::with_capacity(insert.len()); + + for (i, &elt) in insert.iter().enumerate() { + assert_eq!(map.len(), i); + let (index, existing) = map.insert_full(elt, elt); + assert_eq!(existing, None); + assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0)); + assert_eq!(map.len(), i + 1); + } + + let len = map.len(); + for &elt in &present { + let (index, existing) = map.insert_full(elt, elt); + assert_eq!(existing, Some(elt)); + assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0)); + assert_eq!(map.len(), len); + } +} + +#[test] +fn insert_2() { + let mut map = IndexMap::with_capacity(16); + + let mut keys = vec![]; + keys.extend(0..16); + keys.extend(if cfg!(miri) { 32..64 } else { 128..267 }); + + for &i in &keys { + let old_map = map.clone(); + map.insert(i, ()); + for key in old_map.keys() { + if map.get(key).is_none() { + println!("old_map: {:?}", old_map); + println!("map: {:?}", map); + panic!("did not find {} in map", key); + } + } + } + + for &i in &keys { + assert!(map.get(&i).is_some(), "did not find {}", i); + } +} + +#[test] +fn insert_order() { + let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; + let mut map = IndexMap::new(); + + for &elt in &insert { + map.insert(elt, ()); + } + + assert_eq!(map.keys().count(), map.len()); + assert_eq!(map.keys().count(), insert.len()); + for (a, b) in insert.iter().zip(map.keys()) { + assert_eq!(a, b); + } + for (i, k) in (0..insert.len()).zip(map.keys()) { + assert_eq!(map.get_index(i).unwrap().0, k); + } +} + +#[test] +fn shift_insert() { + 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.shift_insert(0, elt, ()); + } + + assert_eq!(map.keys().count(), map.len()); + assert_eq!(map.keys().count(), insert.len()); + for (a, b) in insert.iter().rev().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); + } + + // "insert" that moves an existing entry + map.shift_insert(0, insert[0], ()); + assert_eq!(map.keys().count(), insert.len()); + assert_eq!(insert[0], map.keys()[0]); + for (a, b) in insert[1..].iter().rev().zip(map.keys().skip(1)) { + assert_eq!(a, b); + } +} + +#[test] +fn grow() { + let insert = [0, 4, 2, 12, 8, 7, 11]; + let not_present = [1, 3, 6, 9, 10]; + let mut map = IndexMap::with_capacity(insert.len()); + + for (i, &elt) in insert.iter().enumerate() { + assert_eq!(map.len(), i); + map.insert(elt, elt); + assert_eq!(map.len(), i + 1); + assert_eq!(map.get(&elt), Some(&elt)); + assert_eq!(map[&elt], elt); + } + + println!("{:?}", map); + for &elt in &insert { + map.insert(elt * 10, elt); + } + for &elt in &insert { + map.insert(elt * 100, elt); + } + for (i, &elt) in insert.iter().cycle().enumerate().take(100) { + map.insert(elt * 100 + i as i32, elt); + } + println!("{:?}", map); + for &elt in ¬_present { + assert!(map.get(&elt).is_none()); + } +} + +#[test] +fn reserve() { + let mut map = IndexMap::<usize, usize>::new(); + assert_eq!(map.capacity(), 0); + map.reserve(100); + let capacity = map.capacity(); + assert!(capacity >= 100); + for i in 0..capacity { + assert_eq!(map.len(), i); + map.insert(i, i * i); + assert_eq!(map.len(), i + 1); + assert_eq!(map.capacity(), capacity); + assert_eq!(map.get(&i), Some(&(i * i))); + } + map.insert(capacity, std::usize::MAX); + assert_eq!(map.len(), capacity + 1); + assert!(map.capacity() > capacity); + assert_eq!(map.get(&capacity), Some(&std::usize::MAX)); +} + +#[test] +fn try_reserve() { + let mut map = IndexMap::<usize, usize>::new(); + assert_eq!(map.capacity(), 0); + assert_eq!(map.try_reserve(100), Ok(())); + assert!(map.capacity() >= 100); + assert!(map.try_reserve(usize::MAX).is_err()); +} + +#[test] +fn shrink_to_fit() { + let mut map = IndexMap::<usize, usize>::new(); + assert_eq!(map.capacity(), 0); + for i in 0..100 { + assert_eq!(map.len(), i); + map.insert(i, i * i); + assert_eq!(map.len(), i + 1); + assert!(map.capacity() >= i + 1); + assert_eq!(map.get(&i), Some(&(i * i))); + map.shrink_to_fit(); + assert_eq!(map.len(), i + 1); + assert_eq!(map.capacity(), i + 1); + assert_eq!(map.get(&i), Some(&(i * i))); + } +} + +#[test] +fn remove() { + let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; + let mut map = IndexMap::new(); + + for &elt in &insert { + map.insert(elt, elt); + } + + assert_eq!(map.keys().count(), map.len()); + assert_eq!(map.keys().count(), insert.len()); + for (a, b) in insert.iter().zip(map.keys()) { + assert_eq!(a, b); + } + + let remove_fail = [99, 77]; + let remove = [4, 12, 8, 7]; + + for &key in &remove_fail { + assert!(map.swap_remove_full(&key).is_none()); + } + println!("{:?}", map); + for &key in &remove { + //println!("{:?}", map); + let index = map.get_full(&key).unwrap().0; + assert_eq!(map.swap_remove_full(&key), Some((index, key, key))); + } + println!("{:?}", map); + + for key in &insert { + assert_eq!(map.get(key).is_some(), !remove.contains(key)); + } + assert_eq!(map.len(), insert.len() - remove.len()); + assert_eq!(map.keys().count(), insert.len() - remove.len()); +} + +#[test] +fn remove_to_empty() { + let mut map = indexmap! { 0 => 0, 4 => 4, 5 => 5 }; + map.swap_remove(&5).unwrap(); + map.swap_remove(&4).unwrap(); + map.swap_remove(&0).unwrap(); + assert!(map.is_empty()); +} + +#[test] +fn swap_remove_index() { + let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; + let mut map = IndexMap::new(); + + for &elt in &insert { + map.insert(elt, elt * 2); + } + + let mut vector = insert.to_vec(); + let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1]; + + // check that the same swap remove sequence on vec and map + // have the same result. + for &rm in remove_sequence { + let out_vec = vector.swap_remove(rm); + let (out_map, _) = map.swap_remove_index(rm).unwrap(); + assert_eq!(out_vec, out_map); + } + assert_eq!(vector.len(), map.len()); + for (a, b) in vector.iter().zip(map.keys()) { + assert_eq!(a, b); + } +} + +#[test] +fn partial_eq_and_eq() { + let mut map_a = IndexMap::new(); + map_a.insert(1, "1"); + map_a.insert(2, "2"); + let mut map_b = map_a.clone(); + assert_eq!(map_a, map_b); + map_b.swap_remove(&1); + assert_ne!(map_a, map_b); + + let map_c: IndexMap<_, String> = map_b.into_iter().map(|(k, v)| (k, v.into())).collect(); + assert_ne!(map_a, map_c); + assert_ne!(map_c, map_a); +} + +#[test] +fn extend() { + let mut map = IndexMap::new(); + map.extend(vec![(&1, &2), (&3, &4)]); + map.extend(vec![(5, 6)]); + assert_eq!( + map.into_iter().collect::<Vec<_>>(), + vec![(1, 2), (3, 4), (5, 6)] + ); +} + +#[test] +fn entry() { + let mut map = IndexMap::new(); + + map.insert(1, "1"); + map.insert(2, "2"); + { + let e = map.entry(3); + assert_eq!(e.index(), 2); + let e = e.or_insert("3"); + assert_eq!(e, &"3"); + } + + let e = map.entry(2); + assert_eq!(e.index(), 1); + assert_eq!(e.key(), &2); + match e { + Entry::Occupied(ref e) => assert_eq!(e.get(), &"2"), + Entry::Vacant(_) => panic!(), + } + assert_eq!(e.or_insert("4"), &"2"); +} + +#[test] +fn entry_and_modify() { + let mut map = IndexMap::new(); + + map.insert(1, "1"); + map.entry(1).and_modify(|x| *x = "2"); + assert_eq!(Some(&"2"), map.get(&1)); + + map.entry(2).and_modify(|x| *x = "doesn't exist"); + assert_eq!(None, map.get(&2)); +} + +#[test] +fn entry_or_default() { + let mut map = IndexMap::new(); + + #[derive(Debug, PartialEq)] + enum TestEnum { + DefaultValue, + NonDefaultValue, + } + + impl Default for TestEnum { + fn default() -> Self { + TestEnum::DefaultValue + } + } + + map.insert(1, TestEnum::NonDefaultValue); + assert_eq!(&mut TestEnum::NonDefaultValue, map.entry(1).or_default()); + + assert_eq!(&mut TestEnum::DefaultValue, map.entry(2).or_default()); +} + +#[test] +fn occupied_entry_key() { + // These keys match hash and equality, but their addresses are distinct. + let (k1, k2) = (&mut 1, &mut 1); + let k1_ptr = k1 as *const i32; + let k2_ptr = k2 as *const i32; + assert_ne!(k1_ptr, k2_ptr); + + let mut map = IndexMap::new(); + map.insert(k1, "value"); + match map.entry(k2) { + Entry::Occupied(ref e) => { + // `OccupiedEntry::key` should reference the key in the map, + // not the key that was used to find the entry. + let ptr = *e.key() as *const i32; + assert_eq!(ptr, k1_ptr); + assert_ne!(ptr, k2_ptr); + } + Entry::Vacant(_) => panic!(), + } +} + +#[test] +fn get_index_entry() { + let mut map = IndexMap::new(); + + assert!(map.get_index_entry(0).is_none()); + + map.insert(0, "0"); + map.insert(1, "1"); + map.insert(2, "2"); + map.insert(3, "3"); + + assert!(map.get_index_entry(4).is_none()); + + { + let e = map.get_index_entry(1).unwrap(); + assert_eq!(*e.key(), 1); + assert_eq!(*e.get(), "1"); + assert_eq!(e.swap_remove(), "1"); + } + + { + let mut e = map.get_index_entry(1).unwrap(); + assert_eq!(*e.key(), 3); + assert_eq!(*e.get(), "3"); + assert_eq!(e.insert("4"), "3"); + } + + assert_eq!(*map.get(&3).unwrap(), "4"); +} + +#[test] +fn keys() { + let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; + let map: IndexMap<_, _> = vec.into_iter().collect(); + let keys: Vec<_> = map.keys().copied().collect(); + assert_eq!(keys.len(), 3); + assert!(keys.contains(&1)); + assert!(keys.contains(&2)); + assert!(keys.contains(&3)); +} + +#[test] +fn into_keys() { + let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; + let map: IndexMap<_, _> = vec.into_iter().collect(); + let keys: Vec<i32> = map.into_keys().collect(); + assert_eq!(keys.len(), 3); + assert!(keys.contains(&1)); + assert!(keys.contains(&2)); + assert!(keys.contains(&3)); +} + +#[test] +fn values() { + let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; + let map: IndexMap<_, _> = vec.into_iter().collect(); + let values: Vec<_> = map.values().copied().collect(); + assert_eq!(values.len(), 3); + assert!(values.contains(&'a')); + assert!(values.contains(&'b')); + assert!(values.contains(&'c')); +} + +#[test] +fn values_mut() { + let vec = vec![(1, 1), (2, 2), (3, 3)]; + let mut map: IndexMap<_, _> = vec.into_iter().collect(); + for value in map.values_mut() { + *value *= 2 + } + let values: Vec<_> = map.values().copied().collect(); + assert_eq!(values.len(), 3); + assert!(values.contains(&2)); + assert!(values.contains(&4)); + assert!(values.contains(&6)); +} + +#[test] +fn into_values() { + let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; + let map: IndexMap<_, _> = vec.into_iter().collect(); + let values: Vec<char> = map.into_values().collect(); + assert_eq!(values.len(), 3); + assert!(values.contains(&'a')); + assert!(values.contains(&'b')); + assert!(values.contains(&'c')); +} + +#[test] +#[cfg(feature = "std")] +fn from_array() { + let map = IndexMap::from([(1, 2), (3, 4)]); + let mut expected = IndexMap::new(); + expected.insert(1, 2); + expected.insert(3, 4); + + assert_eq!(map, expected) +} + +#[test] +fn iter_default() { + struct K; + struct V; + fn assert_default<T>() + where + T: Default + Iterator, + { + assert!(T::default().next().is_none()); + } + assert_default::<Iter<'static, K, V>>(); + assert_default::<IterMut<'static, K, V>>(); + assert_default::<IntoIter<K, V>>(); + assert_default::<Keys<'static, K, V>>(); + assert_default::<IntoKeys<K, V>>(); + assert_default::<Values<'static, K, V>>(); + assert_default::<ValuesMut<'static, K, V>>(); + assert_default::<IntoValues<K, V>>(); +} + +#[test] +fn test_binary_search_by() { + // adapted from std's test for binary_search + let b: IndexMap<_, i32> = [] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(0)); + + let b: IndexMap<_, i32> = [4] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&3)), Err(0)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&4)), Ok(0)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(1)); + + let b: IndexMap<_, i32> = [1, 2, 4, 6, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(3)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&6)), Ok(3)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&7)), Err(4)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&8)), Ok(4)); + + let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&9)), Err(6)); + + let b: IndexMap<_, i32> = [1, 2, 4, 6, 7, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&6)), Ok(3)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(3)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&8)), Ok(5)); + + let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&7)), Err(5)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&0)), Err(0)); + + let b: IndexMap<_, i32> = [1, 3, 3, 3, 7] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&0)), Err(0)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&1)), Ok(0)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&2)), Err(1)); + assert!(match b.binary_search_by(|_, x| x.cmp(&3)) { + Ok(1..=3) => true, + _ => false, + }); + assert!(match b.binary_search_by(|_, x| x.cmp(&3)) { + Ok(1..=3) => true, + _ => false, + }); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&4)), Err(4)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(4)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&6)), Err(4)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&7)), Ok(4)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&8)), Err(5)); +} + +#[test] +fn test_binary_search_by_key() { + // adapted from std's test for binary_search + let b: IndexMap<_, i32> = [] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(0)); + + let b: IndexMap<_, i32> = [4] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by_key(&3, |_, &x| x), Err(0)); + assert_eq!(b.binary_search_by_key(&4, |_, &x| x), Ok(0)); + assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(1)); + + let b: IndexMap<_, i32> = [1, 2, 4, 6, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(3)); + assert_eq!(b.binary_search_by_key(&6, |_, &x| x), Ok(3)); + assert_eq!(b.binary_search_by_key(&7, |_, &x| x), Err(4)); + assert_eq!(b.binary_search_by_key(&8, |_, &x| x), Ok(4)); + + let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by_key(&9, |_, &x| x), Err(6)); + + let b: IndexMap<_, i32> = [1, 2, 4, 6, 7, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by_key(&6, |_, &x| x), Ok(3)); + assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(3)); + assert_eq!(b.binary_search_by_key(&8, |_, &x| x), Ok(5)); + + let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by_key(&7, |_, &x| x), Err(5)); + assert_eq!(b.binary_search_by_key(&0, |_, &x| x), Err(0)); + + let b: IndexMap<_, i32> = [1, 3, 3, 3, 7] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by_key(&0, |_, &x| x), Err(0)); + assert_eq!(b.binary_search_by_key(&1, |_, &x| x), Ok(0)); + assert_eq!(b.binary_search_by_key(&2, |_, &x| x), Err(1)); + assert!(match b.binary_search_by_key(&3, |_, &x| x) { + Ok(1..=3) => true, + _ => false, + }); + assert!(match b.binary_search_by_key(&3, |_, &x| x) { + Ok(1..=3) => true, + _ => false, + }); + assert_eq!(b.binary_search_by_key(&4, |_, &x| x), Err(4)); + assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(4)); + assert_eq!(b.binary_search_by_key(&6, |_, &x| x), Err(4)); + assert_eq!(b.binary_search_by_key(&7, |_, &x| x), Ok(4)); + assert_eq!(b.binary_search_by_key(&8, |_, &x| x), Err(5)); +} + +#[test] +fn test_partition_point() { + // adapted from std's test for partition_point + let b: IndexMap<_, i32> = [] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.partition_point(|_, &x| x < 5), 0); + + let b: IndexMap<_, i32> = [4] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.partition_point(|_, &x| x < 3), 0); + assert_eq!(b.partition_point(|_, &x| x < 4), 0); + assert_eq!(b.partition_point(|_, &x| x < 5), 1); + + let b: IndexMap<_, i32> = [1, 2, 4, 6, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.partition_point(|_, &x| x < 5), 3); + assert_eq!(b.partition_point(|_, &x| x < 6), 3); + assert_eq!(b.partition_point(|_, &x| x < 7), 4); + assert_eq!(b.partition_point(|_, &x| x < 8), 4); + + let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.partition_point(|_, &x| x < 9), 6); + + let b: IndexMap<_, i32> = [1, 2, 4, 6, 7, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.partition_point(|_, &x| x < 6), 3); + assert_eq!(b.partition_point(|_, &x| x < 5), 3); + assert_eq!(b.partition_point(|_, &x| x < 8), 5); + + let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.partition_point(|_, &x| x < 7), 5); + assert_eq!(b.partition_point(|_, &x| x < 0), 0); + + let b: IndexMap<_, i32> = [1, 3, 3, 3, 7] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.partition_point(|_, &x| x < 0), 0); + assert_eq!(b.partition_point(|_, &x| x < 1), 0); + assert_eq!(b.partition_point(|_, &x| x < 2), 1); + assert_eq!(b.partition_point(|_, &x| x < 3), 1); + assert_eq!(b.partition_point(|_, &x| x < 4), 4); + assert_eq!(b.partition_point(|_, &x| x < 5), 4); + assert_eq!(b.partition_point(|_, &x| x < 6), 4); + assert_eq!(b.partition_point(|_, &x| x < 7), 4); + assert_eq!(b.partition_point(|_, &x| x < 8), 5); +} |