diff options
Diffstat (limited to 'vendor/indexmap/src/map')
| -rw-r--r-- | vendor/indexmap/src/map/core.rs | 738 | ||||
| -rw-r--r-- | vendor/indexmap/src/map/core/entry.rs | 571 | ||||
| -rw-r--r-- | vendor/indexmap/src/map/core/raw_entry_v1.rs | 665 | ||||
| -rw-r--r-- | vendor/indexmap/src/map/iter.rs | 776 | ||||
| -rw-r--r-- | vendor/indexmap/src/map/mutable.rs | 166 | ||||
| -rw-r--r-- | vendor/indexmap/src/map/serde_seq.rs | 138 | ||||
| -rw-r--r-- | vendor/indexmap/src/map/slice.rs | 631 | ||||
| -rw-r--r-- | vendor/indexmap/src/map/tests.rs | 1008 |
8 files changed, 0 insertions, 4693 deletions
diff --git a/vendor/indexmap/src/map/core.rs b/vendor/indexmap/src/map/core.rs deleted file mode 100644 index 9022c8ee..00000000 --- a/vendor/indexmap/src/map/core.rs +++ /dev/null @@ -1,738 +0,0 @@ -//! This is the core implementation that doesn't depend on the hasher at all. -//! -//! The methods of `IndexMapCore` don't use any Hash properties of K. -//! -//! It's cleaner to separate them out, then the compiler checks that we are not -//! using Hash at all in these methods. -//! -//! However, we should probably not let this show in the public API or docs. - -mod entry; - -pub mod raw_entry_v1; - -use hashbrown::hash_table; - -use crate::vec::{self, Vec}; -use crate::TryReserveError; -use core::mem; -use core::ops::RangeBounds; - -use crate::util::simplify_range; -use crate::{Bucket, Equivalent, HashValue}; - -type Indices = hash_table::HashTable<usize>; -type Entries<K, V> = Vec<Bucket<K, V>>; - -pub use entry::{Entry, IndexedEntry, OccupiedEntry, VacantEntry}; - -/// Core of the map that does not depend on S -#[derive(Debug)] -pub(crate) struct IndexMapCore<K, V> { - /// indices mapping from the entry hash to its index. - indices: Indices, - /// entries is a dense vec maintaining entry order. - entries: Entries<K, V>, -} - -/// Mutable references to the parts of an `IndexMapCore`. -/// -/// When using `HashTable::find_entry`, that takes hold of `&mut indices`, so we have to borrow our -/// `&mut entries` separately, and there's no way to go back to a `&mut IndexMapCore`. So this type -/// is used to implement methods on the split references, and `IndexMapCore` can also call those to -/// avoid duplication. -struct RefMut<'a, K, V> { - indices: &'a mut Indices, - entries: &'a mut Entries<K, V>, -} - -#[inline(always)] -fn get_hash<K, V>(entries: &[Bucket<K, V>]) -> impl Fn(&usize) -> u64 + '_ { - move |&i| entries[i].hash.get() -} - -#[inline] -fn equivalent<'a, K, V, Q: ?Sized + Equivalent<K>>( - key: &'a Q, - entries: &'a [Bucket<K, V>], -) -> impl Fn(&usize) -> bool + 'a { - move |&i| Q::equivalent(key, &entries[i].key) -} - -#[inline] -fn erase_index(table: &mut Indices, hash: HashValue, index: usize) { - if let Ok(entry) = table.find_entry(hash.get(), move |&i| i == index) { - entry.remove(); - } else if cfg!(debug_assertions) { - panic!("index not found"); - } -} - -#[inline] -fn update_index(table: &mut Indices, hash: HashValue, old: usize, new: usize) { - let index = table - .find_mut(hash.get(), move |&i| i == old) - .expect("index not found"); - *index = new; -} - -/// Inserts many entries into the indices table without reallocating, -/// and without regard for duplication. -/// -/// ***Panics*** if there is not sufficient capacity already. -fn insert_bulk_no_grow<K, V>(indices: &mut Indices, entries: &[Bucket<K, V>]) { - assert!(indices.capacity() - indices.len() >= entries.len()); - for entry in entries { - indices.insert_unique(entry.hash.get(), indices.len(), |_| unreachable!()); - } -} - -impl<K, V> Clone for IndexMapCore<K, V> -where - K: Clone, - V: Clone, -{ - fn clone(&self) -> Self { - let mut new = Self::new(); - new.clone_from(self); - new - } - - fn clone_from(&mut self, other: &Self) { - self.indices.clone_from(&other.indices); - if self.entries.capacity() < other.entries.len() { - // If we must resize, match the indices capacity. - let additional = other.entries.len() - self.entries.len(); - self.borrow_mut().reserve_entries(additional); - } - self.entries.clone_from(&other.entries); - } -} - -impl<K, V> crate::Entries for IndexMapCore<K, V> { - type Entry = Bucket<K, V>; - - #[inline] - fn into_entries(self) -> Vec<Self::Entry> { - self.entries - } - - #[inline] - fn as_entries(&self) -> &[Self::Entry] { - &self.entries - } - - #[inline] - fn as_entries_mut(&mut self) -> &mut [Self::Entry] { - &mut self.entries - } - - fn with_entries<F>(&mut self, f: F) - where - F: FnOnce(&mut [Self::Entry]), - { - f(&mut self.entries); - self.rebuild_hash_table(); - } -} - -impl<K, V> IndexMapCore<K, V> { - /// 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 { - indices: Indices::new(), - entries: Vec::new(), - } - } - - #[inline] - fn borrow_mut(&mut self) -> RefMut<'_, K, V> { - RefMut::new(&mut self.indices, &mut self.entries) - } - - #[inline] - pub(crate) fn with_capacity(n: usize) -> Self { - IndexMapCore { - indices: Indices::with_capacity(n), - entries: Vec::with_capacity(n), - } - } - - #[inline] - pub(crate) fn len(&self) -> usize { - self.indices.len() - } - - #[inline] - pub(crate) fn capacity(&self) -> usize { - Ord::min(self.indices.capacity(), self.entries.capacity()) - } - - pub(crate) fn clear(&mut self) { - self.indices.clear(); - self.entries.clear(); - } - - pub(crate) fn truncate(&mut self, len: usize) { - if len < self.len() { - self.erase_indices(len, self.entries.len()); - self.entries.truncate(len); - } - } - - #[track_caller] - pub(crate) fn drain<R>(&mut self, range: R) -> vec::Drain<'_, Bucket<K, V>> - where - R: RangeBounds<usize>, - { - let range = simplify_range(range, self.entries.len()); - self.erase_indices(range.start, range.end); - self.entries.drain(range) - } - - #[cfg(feature = "rayon")] - pub(crate) fn par_drain<R>(&mut self, range: R) -> rayon::vec::Drain<'_, Bucket<K, V>> - where - K: Send, - V: Send, - R: RangeBounds<usize>, - { - use rayon::iter::ParallelDrainRange; - let range = simplify_range(range, self.entries.len()); - self.erase_indices(range.start, range.end); - self.entries.par_drain(range) - } - - #[track_caller] - pub(crate) fn split_off(&mut self, at: usize) -> Self { - let len = self.entries.len(); - assert!( - at <= len, - "index out of bounds: the len is {len} but the index is {at}. Expected index <= len" - ); - - self.erase_indices(at, self.entries.len()); - let entries = self.entries.split_off(at); - - let mut indices = Indices::with_capacity(entries.len()); - insert_bulk_no_grow(&mut indices, &entries); - Self { indices, entries } - } - - #[track_caller] - 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 = Indices::with_capacity(entries.len()); - 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()); - 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)); - // Only grow entries if necessary, since we also round up capacity. - if additional > self.entries.capacity() - self.entries.len() { - self.borrow_mut().reserve_entries(additional); - } - } - - /// Reserve capacity for `additional` more key-value pairs, without over-allocating. - pub(crate) fn reserve_exact(&mut self, additional: usize) { - self.indices.reserve(additional, get_hash(&self.entries)); - self.entries.reserve_exact(additional); - } - - /// Try to reserve capacity for `additional` more key-value pairs. - pub(crate) fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { - self.indices - .try_reserve(additional, get_hash(&self.entries)) - .map_err(TryReserveError::from_hashbrown)?; - // Only grow entries if necessary, since we also round up capacity. - if additional > self.entries.capacity() - self.entries.len() { - self.try_reserve_entries(additional) - } else { - Ok(()) - } - } - - /// Try to reserve entries capacity, rounded up to match the indices - fn try_reserve_entries(&mut self, additional: usize) -> Result<(), TryReserveError> { - // Use a soft-limit on the maximum capacity, but if the caller explicitly - // requested more, do it and let them have the resulting error. - let new_capacity = Ord::min(self.indices.capacity(), Self::MAX_ENTRIES_CAPACITY); - let try_add = new_capacity - self.entries.len(); - if try_add > additional && self.entries.try_reserve_exact(try_add).is_ok() { - return Ok(()); - } - self.entries - .try_reserve_exact(additional) - .map_err(TryReserveError::from_alloc) - } - - /// Try to reserve capacity for `additional` more key-value pairs, without over-allocating. - pub(crate) fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> { - self.indices - .try_reserve(additional, get_hash(&self.entries)) - .map_err(TryReserveError::from_hashbrown)?; - self.entries - .try_reserve_exact(additional) - .map_err(TryReserveError::from_alloc) - } - - /// Shrink the capacity of the map with a lower bound - pub(crate) fn shrink_to(&mut self, min_capacity: usize) { - self.indices - .shrink_to(min_capacity, get_hash(&self.entries)); - self.entries.shrink_to(min_capacity); - } - - /// Remove the last key-value pair - pub(crate) fn pop(&mut self) -> Option<(K, V)> { - if let Some(entry) = self.entries.pop() { - let last = self.entries.len(); - erase_index(&mut self.indices, entry.hash, last); - Some((entry.key, entry.value)) - } else { - None - } - } - - /// Return the index in `entries` where an equivalent key can be found - pub(crate) fn get_index_of<Q>(&self, hash: HashValue, key: &Q) -> Option<usize> - where - Q: ?Sized + Equivalent<K>, - { - let eq = equivalent(key, &self.entries); - self.indices.find(hash.get(), eq).copied() - } - - /// 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.borrow_mut().reserve_entries(1); - } - self.entries.push(Bucket { hash, key, value }); - } - - pub(crate) fn insert_full(&mut self, hash: HashValue, key: K, value: V) -> (usize, Option<V>) - where - K: Eq, - { - let eq = equivalent(&key, &self.entries); - let hasher = get_hash(&self.entries); - match self.indices.entry(hash.get(), eq, hasher) { - hash_table::Entry::Occupied(entry) => { - let i = *entry.get(); - (i, Some(mem::replace(&mut self.entries[i].value, value))) - } - hash_table::Entry::Vacant(entry) => { - let i = self.entries.len(); - entry.insert(i); - self.push_entry(hash, key, value); - debug_assert_eq!(self.indices.len(), self.entries.len()); - (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, - { - let eq = equivalent(&key, &self.entries); - let hasher = get_hash(&self.entries); - match self.indices.entry(hash.get(), eq, hasher) { - hash_table::Entry::Occupied(entry) => { - let i = *entry.get(); - let entry = &mut self.entries[i]; - let kv = ( - mem::replace(&mut entry.key, key), - mem::replace(&mut entry.value, value), - ); - (i, Some(kv)) - } - hash_table::Entry::Vacant(entry) => { - let i = self.entries.len(); - entry.insert(i); - self.push_entry(hash, key, value); - debug_assert_eq!(self.indices.len(), self.entries.len()); - (i, None) - } - } - } - - /// Remove an entry by shifting all entries that follow it - pub(crate) fn shift_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)> - where - Q: ?Sized + Equivalent<K>, - { - let eq = equivalent(key, &self.entries); - match self.indices.find_entry(hash.get(), eq) { - Ok(entry) => { - let (index, _) = entry.remove(); - let (key, value) = self.borrow_mut().shift_remove_finish(index); - Some((index, key, value)) - } - Err(_) => None, - } - } - - /// Remove an entry by shifting all entries that follow it - #[inline] - pub(crate) fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> { - self.borrow_mut().shift_remove_index(index) - } - - #[inline] - #[track_caller] - pub(super) fn move_index(&mut self, from: usize, to: usize) { - self.borrow_mut().move_index(from, to); - } - - #[inline] - #[track_caller] - pub(crate) fn swap_indices(&mut self, a: usize, b: usize) { - self.borrow_mut().swap_indices(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 - Q: ?Sized + Equivalent<K>, - { - let eq = equivalent(key, &self.entries); - match self.indices.find_entry(hash.get(), eq) { - Ok(entry) => { - let (index, _) = entry.remove(); - let (key, value) = self.borrow_mut().swap_remove_finish(index); - Some((index, key, value)) - } - Err(_) => None, - } - } - - /// Remove an entry by swapping it with the last - #[inline] - pub(crate) fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> { - self.borrow_mut().swap_remove_index(index) - } - - /// Erase `start..end` from `indices`, and shift `end..` indices down to `start..` - /// - /// All of these items should still be at their original location in `entries`. - /// This is used by `drain`, which will let `Vec::drain` do the work on `entries`. - fn erase_indices(&mut self, start: usize, end: usize) { - let (init, shifted_entries) = self.entries.split_at(end); - let (start_entries, erased_entries) = init.split_at(start); - - let erased = erased_entries.len(); - let shifted = shifted_entries.len(); - let half_capacity = self.indices.capacity() / 2; - - // Use a heuristic between different strategies - if erased == 0 { - // Degenerate case, nothing to do - } else if start + shifted < half_capacity && start < erased { - // Reinsert everything, as there are few kept indices - self.indices.clear(); - - // Reinsert stable indices, then shifted indices - insert_bulk_no_grow(&mut self.indices, start_entries); - insert_bulk_no_grow(&mut self.indices, shifted_entries); - } else if erased + shifted < half_capacity { - // Find each affected index, as there are few to adjust - - // Find erased indices - for (i, entry) in (start..).zip(erased_entries) { - erase_index(&mut self.indices, entry.hash, i); - } - - // Find shifted indices - for ((new, old), entry) in (start..).zip(end..).zip(shifted_entries) { - update_index(&mut self.indices, entry.hash, old, new); - } - } else { - // Sweep the whole table for adjustments - let offset = end - start; - self.indices.retain(move |i| { - if *i >= end { - *i -= offset; - true - } else { - *i < start - } - }); - } - - debug_assert_eq!(self.indices.len(), start + shifted); - } - - pub(crate) fn retain_in_order<F>(&mut self, mut keep: F) - where - F: FnMut(&mut K, &mut V) -> bool, - { - self.entries - .retain_mut(|entry| keep(&mut entry.key, &mut entry.value)); - if self.entries.len() < self.indices.len() { - self.rebuild_hash_table(); - } - } - - fn rebuild_hash_table(&mut self) { - self.indices.clear(); - insert_bulk_no_grow(&mut self.indices, &self.entries); - } - - pub(crate) fn reverse(&mut self) { - self.entries.reverse(); - - // No need to save hash indices, can easily calculate what they should - // be, given that this is an in-place reversal. - let len = self.entries.len(); - for i in &mut self.indices { - *i = len - *i - 1; - } - } -} - -/// Reserve entries capacity, rounded up to match the indices (via `try_capacity`). -fn reserve_entries<K, V>(entries: &mut Entries<K, V>, additional: usize, try_capacity: 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 try_capacity = try_capacity.min(IndexMapCore::<K, V>::MAX_ENTRIES_CAPACITY); - let try_add = try_capacity - entries.len(); - if try_add > additional && entries.try_reserve_exact(try_add).is_ok() { - return; - } - entries.reserve_exact(additional); -} - -impl<'a, K, V> RefMut<'a, K, V> { - #[inline] - fn new(indices: &'a mut Indices, entries: &'a mut Entries<K, V>) -> Self { - Self { indices, entries } - } - - /// Reserve entries capacity, rounded up to match the indices - #[inline] - fn reserve_entries(&mut self, additional: usize) { - reserve_entries(self.entries, additional, self.indices.capacity()); - } - - /// Insert a key-value pair in `entries`, - /// *without* checking whether it already exists. - fn insert_unique(self, hash: HashValue, key: K, value: V) -> OccupiedEntry<'a, K, V> { - let i = self.indices.len(); - debug_assert_eq!(i, self.entries.len()); - let entry = self - .indices - .insert_unique(hash.get(), i, get_hash(self.entries)); - if self.entries.len() == self.entries.capacity() { - // We can't call `indices.capacity()` while this `entry` has borrowed it, so we'll have - // to amortize growth on our own. It's still an improvement over the basic `Vec::push` - // doubling though, since we also consider `MAX_ENTRIES_CAPACITY`. - reserve_entries(self.entries, 1, 2 * self.entries.capacity()); - } - self.entries.push(Bucket { hash, key, value }); - OccupiedEntry::new(self.entries, entry) - } - - /// Insert a key-value pair in `entries` at a particular index, - /// *without* checking whether it already exists. - 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_unique(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() - }); - 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 }); - } - - /// Remove an entry by shifting all entries that follow it - fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> { - match self.entries.get(index) { - Some(entry) => { - erase_index(self.indices, entry.hash, index); - Some(self.shift_remove_finish(index)) - } - None => None, - } - } - - /// Remove an entry by shifting all entries that follow it - /// - /// The index should already be removed from `self.indices`. - fn shift_remove_finish(&mut self, index: usize) -> (K, V) { - // Correct indices that point to the entries that followed the removed entry. - self.decrement_indices(index + 1, self.entries.len()); - - // Use Vec::remove to actually remove the entry. - let entry = self.entries.remove(index); - (entry.key, entry.value) - } - - /// Remove an entry by swapping it with the last - fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> { - match self.entries.get(index) { - Some(entry) => { - erase_index(self.indices, entry.hash, index); - Some(self.swap_remove_finish(index)) - } - None => None, - } - } - - /// Finish removing an entry by swapping it with the last - /// - /// The index should already be removed from `self.indices`. - fn swap_remove_finish(&mut self, index: usize) -> (K, V) { - // use swap_remove, but then we need to update the index that points - // to the other entry that has to move - let entry = self.entries.swap_remove(index); - - // correct index that points to the entry that had to swap places - if let Some(entry) = self.entries.get(index) { - // was not last element - // examine new element in `index` and find it in indices - let last = self.entries.len(); - update_index(self.indices, entry.hash, last, index); - } - - (entry.key, entry.value) - } - - /// Decrement all indices in the range `start..end`. - /// - /// The index `start - 1` should not exist in `self.indices`. - /// All entries should still be in their original positions. - fn decrement_indices(&mut self, start: usize, end: usize) { - // Use a heuristic between a full sweep vs. a `find()` for every shifted item. - let shifted_entries = &self.entries[start..end]; - if shifted_entries.len() > self.indices.capacity() / 2 { - // Shift all indices in range. - for i in &mut *self.indices { - if start <= *i && *i < end { - *i -= 1; - } - } - } else { - // Find each entry in range to shift its index. - for (i, entry) in (start..end).zip(shifted_entries) { - update_index(self.indices, entry.hash, i, i - 1); - } - } - } - - /// Increment all indices in the range `start..end`. - /// - /// The index `end` should not exist in `self.indices`. - /// All entries should still be in their original positions. - fn increment_indices(&mut self, start: usize, end: usize) { - // Use a heuristic between a full sweep vs. a `find()` for every shifted item. - let shifted_entries = &self.entries[start..end]; - if shifted_entries.len() > self.indices.capacity() / 2 { - // Shift all indices in range. - for i in &mut *self.indices { - if start <= *i && *i < end { - *i += 1; - } - } - } else { - // Find each entry in range to shift its index, updated in reverse so - // we never have duplicated indices that might have a hash collision. - for (i, entry) in (start..end).zip(shifted_entries).rev() { - update_index(self.indices, entry.hash, i, i + 1); - } - } - } - - #[track_caller] - fn move_index(&mut self, from: usize, to: usize) { - let from_hash = self.entries[from].hash; - let _ = self.entries[to]; // explicit bounds check - if from != to { - // Use a sentinel index so other indices don't collide. - update_index(self.indices, from_hash, from, usize::MAX); - - // Update all other indices and rotate the entry positions. - if from < to { - self.decrement_indices(from + 1, to + 1); - self.entries[from..=to].rotate_left(1); - } else if to < from { - self.increment_indices(to, from); - self.entries[to..=from].rotate_right(1); - } - - // Change the sentinel index to its final position. - update_index(self.indices, from_hash, usize::MAX, to); - } - } - - #[track_caller] - 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 `entries`, - // and then we expect to find it in the table as well. - match 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 }, - ) { - [Some(ref_a), Some(ref_b)] => { - mem::swap(ref_a, ref_b); - self.entries.swap(a, b); - } - _ => panic!("indices not found"), - } - } -} - -#[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>>(); - assert_send_sync::<raw_entry_v1::RawEntryMut<'_, i32, i32, ()>>(); -} diff --git a/vendor/indexmap/src/map/core/entry.rs b/vendor/indexmap/src/map/core/entry.rs deleted file mode 100644 index 6ab29ca5..00000000 --- a/vendor/indexmap/src/map/core/entry.rs +++ /dev/null @@ -1,571 +0,0 @@ -use super::{equivalent, Entries, IndexMapCore, RefMut}; -use crate::HashValue; -use core::{fmt, mem}; -use hashbrown::hash_table; - -impl<K, V> IndexMapCore<K, V> { - pub(crate) fn entry(&mut self, hash: HashValue, key: K) -> Entry<'_, K, V> - where - K: Eq, - { - let entries = &mut self.entries; - let eq = equivalent(&key, entries); - match self.indices.find_entry(hash.get(), eq) { - Ok(index) => Entry::Occupied(OccupiedEntry { entries, index }), - Err(absent) => Entry::Vacant(VacantEntry { - map: RefMut::new(absent.into_table(), entries), - 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(), - } - } - - /// Sets the value of the entry (after inserting if vacant), and returns an `OccupiedEntry`. - /// - /// Computes in **O(1)** time (amortized average). - pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> { - match self { - Entry::Occupied(mut entry) => { - entry.insert(value); - entry - } - Entry::Vacant(entry) => entry.insert_entry(value), - } - } - - /// 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> { - entries: &'a mut Entries<K, V>, - index: hash_table::OccupiedEntry<'a, usize>, -} - -impl<'a, K, V> OccupiedEntry<'a, K, V> { - pub(crate) fn new( - entries: &'a mut Entries<K, V>, - index: hash_table::OccupiedEntry<'a, usize>, - ) -> Self { - Self { entries, index } - } - - /// Return the index of the key-value pair - #[inline] - pub fn index(&self) -> usize { - *self.index.get() - } - - #[inline] - fn into_ref_mut(self) -> RefMut<'a, K, V> { - RefMut::new(self.index.into_table(), self.entries) - } - - /// 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.entries[self.index()].key - } - - pub(crate) fn key_mut(&mut self) -> &mut K { - let index = self.index(); - &mut self.entries[index].key - } - - /// Gets a reference to the entry's value in the map. - pub fn get(&self) -> &V { - &self.entries[self.index()].value - } - - /// Gets a mutable reference to the entry's value in the map. - /// - /// If you need a reference which may outlive the destruction of the - /// [`Entry`] value, see [`into_mut`][Self::into_mut]. - pub fn get_mut(&mut self) -> &mut V { - let index = self.index(); - &mut self.entries[index].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 { - let index = self.index(); - &mut self.entries[index].value - } - - pub(super) fn into_muts(self) -> (&'a mut K, &'a mut V) { - let index = self.index(); - self.entries[index].muts() - } - - /// 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 (index, entry) = self.index.remove(); - RefMut::new(entry.into_table(), self.entries).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 (index, entry) = self.index.remove(); - RefMut::new(entry.into_table(), self.entries).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). - #[track_caller] - pub fn move_index(self, to: usize) { - let index = self.index(); - self.into_ref_mut().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 index = self.index(); - self.into_ref_mut().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() - } -} - -impl<'a, K, V> From<IndexedEntry<'a, K, V>> for OccupiedEntry<'a, K, V> { - fn from(other: IndexedEntry<'a, K, V>) -> Self { - let IndexedEntry { - map: RefMut { indices, entries }, - index, - } = other; - let hash = entries[index].hash; - Self { - entries, - index: indices - .find_entry(hash.get(), move |&i| i == index) - .expect("index not found"), - } - } -} - -/// 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: RefMut<'a, 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 - } - - pub(crate) fn key_mut(&mut self) -> &mut K { - &mut 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. - /// - /// Computes in **O(1)** time (amortized average). - pub fn insert(self, value: V) -> &'a mut V { - self.insert_entry(value).into_mut() - } - - /// Inserts the entry's key and the given value into the map, and returns an `OccupiedEntry`. - /// - /// Computes in **O(1)** time (amortized average). - pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> { - let Self { map, hash, key } = self; - map.insert_unique(hash, key, 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(mut self, index: usize, value: V) -> &'a mut V { - self.map - .shift_insert_unique(index, self.hash, self.key, value); - &mut self.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: RefMut<'a, 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: map.borrow_mut(), - 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 - } - - pub(crate) fn key_mut(&mut self) -> &mut K { - &mut 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(mut 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(mut 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). - #[track_caller] - pub fn move_index(mut 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(mut 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() - } -} - -impl<'a, K, V> From<OccupiedEntry<'a, K, V>> for IndexedEntry<'a, K, V> { - fn from(other: OccupiedEntry<'a, K, V>) -> Self { - Self { - index: other.index(), - map: other.into_ref_mut(), - } - } -} diff --git a/vendor/indexmap/src/map/core/raw_entry_v1.rs b/vendor/indexmap/src/map/core/raw_entry_v1.rs deleted file mode 100644 index 757a3cee..00000000 --- a/vendor/indexmap/src/map/core/raw_entry_v1.rs +++ /dev/null @@ -1,665 +0,0 @@ -//! 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::{Entries, RefMut}; -use crate::{Equivalent, HashValue, IndexMap}; -use core::fmt; -use core::hash::{BuildHasher, Hash, Hasher}; -use core::marker::PhantomData; -use core::mem; -use hashbrown::hash_table; - -/// 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.find(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, mut is_match: F) -> RawEntryMut<'a, K, V, S> - where - F: FnMut(&K) -> bool, - { - let ref_entries = &*self.map.core.entries; - let eq = move |&i: &usize| is_match(&ref_entries[i].key); - match self.map.core.indices.find_entry(hash, eq) { - Ok(index) => RawEntryMut::Occupied(RawOccupiedEntryMut { - entries: &mut self.map.core.entries, - index, - hash_builder: PhantomData, - }), - Err(absent) => RawEntryMut::Vacant(RawVacantEntryMut { - map: RefMut::new(absent.into_table(), &mut self.map.core.entries), - 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> { - entries: &'a mut Entries<K, V>, - index: hash_table::OccupiedEntry<'a, usize>, - 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.index.get() - } - - #[inline] - fn into_ref_mut(self) -> RefMut<'a, K, V> { - RefMut::new(self.index.into_table(), self.entries) - } - - /// 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.entries[self.index()].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 { - let index = self.index(); - &mut self.entries[index].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 { - let index = self.index(); - &mut self.entries[index].key - } - - /// Gets a reference to the entry's value in the map. - pub fn get(&self) -> &V { - &self.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 - /// [`RawEntryMut`] value, see [`into_mut`][Self::into_mut]. - pub fn get_mut(&mut self) -> &mut V { - let index = self.index(); - &mut self.entries[index].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 { - let index = self.index(); - &mut self.entries[index].value - } - - /// Gets a reference to the entry's key and value in the map. - pub fn get_key_value(&self) -> (&K, &V) { - self.entries[self.index()].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) { - let index = self.index(); - self.entries[index].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) { - let index = self.index(); - self.entries[index].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 (index, entry) = self.index.remove(); - RefMut::new(entry.into_table(), self.entries).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 (index, entry) = self.index.remove(); - RefMut::new(entry.into_table(), self.entries).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 index = self.index(); - self.into_ref_mut().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 index = self.index(); - self.into_ref_mut().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: RefMut<'a, 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); - self.map.insert_unique(hash, key, value).into_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( - mut 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/vendor/indexmap/src/map/iter.rs b/vendor/indexmap/src/map/iter.rs deleted file mode 100644 index cce9abed..00000000 --- a/vendor/indexmap/src/map/iter.rs +++ /dev/null @@ -1,776 +0,0 @@ -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(), - } - } -} - -/// A mutable iterator over the entries of an [`IndexMap`]. -/// -/// This `struct` is created by the [`MutableKeys::iter_mut2`][super::MutableKeys::iter_mut2] method. -/// See its documentation for more. -pub struct IterMut2<'a, K, V> { - iter: slice::IterMut<'a, Bucket<K, V>>, -} - -impl<'a, K, V> IterMut2<'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 IterMut2<'a, K, V> { - type Item = (&'a mut K, &'a mut V); - - iterator_methods!(Bucket::muts); -} - -impl<K, V> DoubleEndedIterator for IterMut2<'_, K, V> { - double_ended_iterator_methods!(Bucket::muts); -} - -impl<K, V> ExactSizeIterator for IterMut2<'_, K, V> { - fn len(&self) -> usize { - self.iter.len() - } -} - -impl<K, V> FusedIterator for IterMut2<'_, K, V> {} - -impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut2<'_, 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 IterMut2<'_, 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. -#[derive(Clone)] -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 indices. Similarly, if `Keys` is obtained from -/// [`Slice::keys`], indices 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<K, V> Index<usize> for Keys<'_, 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, -{ - #[track_caller] - 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<I, K, V, S> fmt::Debug for Splice<'_, 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/vendor/indexmap/src/map/mutable.rs b/vendor/indexmap/src/map/mutable.rs deleted file mode 100644 index e429c8be..00000000 --- a/vendor/indexmap/src/map/mutable.rs +++ /dev/null @@ -1,166 +0,0 @@ -use core::hash::{BuildHasher, Hash}; - -use super::{ - Bucket, Entries, Entry, Equivalent, IndexMap, IndexedEntry, IterMut2, OccupiedEntry, - VacantEntry, -}; - -/// 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)>; - - /// Return an iterator over the key-value pairs of the map, in their order - fn iter_mut2(&mut self) -> IterMut2<'_, Self::Key, 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 iter_mut2(&mut self) -> IterMut2<'_, Self::Key, Self::Value> { - IterMut2::new(self.as_entries_mut()) - } - - fn retain2<F>(&mut self, keep: F) - where - F: FnMut(&mut K, &mut V) -> bool, - { - self.core.retain_in_order(keep); - } -} - -/// Opt-in mutable access to [`Entry`] 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 `Entry`. -/// -/// This trait is sealed and cannot be implemented for types outside this crate. -pub trait MutableEntryKey: private::Sealed { - type Key; - - /// Gets a mutable reference to the entry's key, either within the map if occupied, - /// or else the new key that was used to find the entry. - fn key_mut(&mut self) -> &mut Self::Key; -} - -/// Opt-in mutable access to [`Entry`] keys. -/// -/// See [`MutableEntryKey`] for more information. -impl<K, V> MutableEntryKey for Entry<'_, K, V> { - type Key = K; - fn key_mut(&mut self) -> &mut Self::Key { - match self { - Entry::Occupied(e) => e.key_mut(), - Entry::Vacant(e) => e.key_mut(), - } - } -} - -/// Opt-in mutable access to [`OccupiedEntry`] keys. -/// -/// See [`MutableEntryKey`] for more information. -impl<K, V> MutableEntryKey for OccupiedEntry<'_, K, V> { - type Key = K; - fn key_mut(&mut self) -> &mut Self::Key { - self.key_mut() - } -} - -/// Opt-in mutable access to [`VacantEntry`] keys. -/// -/// See [`MutableEntryKey`] for more information. -impl<K, V> MutableEntryKey for VacantEntry<'_, K, V> { - type Key = K; - fn key_mut(&mut self) -> &mut Self::Key { - self.key_mut() - } -} - -/// Opt-in mutable access to [`IndexedEntry`] keys. -/// -/// See [`MutableEntryKey`] for more information. -impl<K, V> MutableEntryKey for IndexedEntry<'_, K, V> { - type Key = K; - fn key_mut(&mut self) -> &mut Self::Key { - self.key_mut() - } -} - -mod private { - pub trait Sealed {} - - impl<K, V, S> Sealed for super::IndexMap<K, V, S> {} - impl<K, V> Sealed for super::Entry<'_, K, V> {} - impl<K, V> Sealed for super::OccupiedEntry<'_, K, V> {} - impl<K, V> Sealed for super::VacantEntry<'_, K, V> {} - impl<K, V> Sealed for super::IndexedEntry<'_, K, V> {} -} diff --git a/vendor/indexmap/src/map/serde_seq.rs b/vendor/indexmap/src/map/serde_seq.rs deleted file mode 100644 index 602ae7dc..00000000 --- a/vendor/indexmap/src/map/serde_seq.rs +++ /dev/null @@ -1,138 +0,0 @@ -//! 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/vendor/indexmap/src/map/slice.rs b/vendor/indexmap/src/map/slice.rs deleted file mode 100644 index 035744ef..00000000 --- a/vendor/indexmap/src/map/slice.rs +++ /dev/null @@ -1,631 +0,0 @@ -use super::{ - Bucket, Entries, IndexMap, IntoIter, IntoKeys, IntoValues, Iter, IterMut, Keys, Values, - ValuesMut, -}; -use crate::util::{slice_eq, try_simplify_range}; -use crate::GetDisjointMutError; - -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)) - } - - /// Get an array of `N` key-value pairs by `N` indices - /// - /// Valid indices are *0 <= index < self.len()* and each index needs to be unique. - pub fn get_disjoint_mut<const N: usize>( - &mut self, - indices: [usize; N], - ) -> Result<[(&K, &mut V); N], GetDisjointMutError> { - let indices = indices.map(Some); - let key_values = self.get_disjoint_opt_mut(indices)?; - Ok(key_values.map(Option::unwrap)) - } - - #[allow(unsafe_code)] - pub(crate) fn get_disjoint_opt_mut<const N: usize>( - &mut self, - indices: [Option<usize>; N], - ) -> Result<[Option<(&K, &mut V)>; N], GetDisjointMutError> { - // SAFETY: Can't allow duplicate indices as we would return several mutable refs to the same data. - let len = self.len(); - for i in 0..N { - if let Some(idx) = indices[i] { - if idx >= len { - return Err(GetDisjointMutError::IndexOutOfBounds); - } else if indices[..i].contains(&Some(idx)) { - return Err(GetDisjointMutError::OverlappingIndices); - } - } - } - - let entries_ptr = self.entries.as_mut_ptr(); - let out = indices.map(|idx_opt| { - match idx_opt { - Some(idx) => { - // SAFETY: The base pointer is valid as it comes from a slice and the reference is always - // in-bounds & unique as we've already checked the indices above. - let kv = unsafe { (*(entries_ptr.add(idx))).ref_mut() }; - Some(kv) - } - None => None, - } - }); - - Ok(out) - } -} - -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, V, K2, V2> PartialEq<Slice<K2, V2>> for Slice<K, V> -where - K: PartialEq<K2>, - V: PartialEq<V2>, -{ - fn eq(&self, other: &Slice<K2, V2>) -> bool { - slice_eq(&self.entries, &other.entries, |b1, b2| { - b1.key == b2.key && b1.value == b2.value - }) - } -} - -impl<K, V, K2, V2> PartialEq<[(K2, V2)]> for Slice<K, V> -where - K: PartialEq<K2>, - V: PartialEq<V2>, -{ - fn eq(&self, other: &[(K2, V2)]) -> bool { - slice_eq(&self.entries, other, |b, t| b.key == t.0 && b.value == t.1) - } -} - -impl<K, V, K2, V2> PartialEq<Slice<K2, V2>> for [(K, V)] -where - K: PartialEq<K2>, - V: PartialEq<V2>, -{ - fn eq(&self, other: &Slice<K2, V2>) -> bool { - slice_eq(self, &other.entries, |t, b| t.0 == b.key && t.1 == b.value) - } -} - -impl<K, V, K2, V2, const N: usize> PartialEq<[(K2, V2); N]> for Slice<K, V> -where - K: PartialEq<K2>, - V: PartialEq<V2>, -{ - fn eq(&self, other: &[(K2, V2); N]) -> bool { - <Self as PartialEq<[_]>>::eq(self, other) - } -} - -impl<K, V, const N: usize, K2, V2> PartialEq<Slice<K2, V2>> for [(K, V); N] -where - K: PartialEq<K2>, - V: PartialEq<V2>, -{ - fn eq(&self, other: &Slice<K2, V2>) -> bool { - <[_] as PartialEq<_>>::eq(self, 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/vendor/indexmap/src/map/tests.rs b/vendor/indexmap/src/map/tests.rs deleted file mode 100644 index f97f2f14..00000000 --- a/vendor/indexmap/src/map/tests.rs +++ /dev/null @@ -1,1008 +0,0 @@ -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 insert_sorted_bad() { - let mut map = IndexMap::new(); - map.insert(10, ()); - for i in 0..10 { - map.insert(i, ()); - } - - // The binary search will want to insert this at the end (index == len()), - // but that's only possible for *new* inserts. It should still be handled - // without panicking though, and in this case it's simple enough that we - // know the exact result. (But don't read this as an API guarantee!) - assert_eq!(map.first(), Some((&10, &()))); - map.insert_sorted(10, ()); - assert_eq!(map.last(), Some((&10, &()))); - assert!(map.keys().copied().eq(0..=10)); - - // Other out-of-order entries can also "insert" to a binary-searched - // position, moving in either direction. - map.move_index(5, 0); - map.move_index(6, 10); - assert_eq!(map.first(), Some((&5, &()))); - assert_eq!(map.last(), Some((&6, &()))); - map.insert_sorted(5, ()); // moves back up - map.insert_sorted(6, ()); // moves back down - assert!(map.keys().copied().eq(0..=10)); -} - -#[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()); - assert!(map.first_entry().is_none()); - assert!(map.last_entry().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"); - - { - let e = map.first_entry().unwrap(); - assert_eq!(*e.key(), 0); - assert_eq!(*e.get(), "0"); - } - - { - let e = map.last_entry().unwrap(); - assert_eq!(*e.key(), 2); - assert_eq!(*e.get(), "2"); - } -} - -#[test] -fn from_entries() { - let mut map = IndexMap::from([(1, "1"), (2, "2"), (3, "3")]); - - { - let e = match map.entry(1) { - Entry::Occupied(e) => IndexedEntry::from(e), - Entry::Vacant(_) => panic!(), - }; - assert_eq!(e.index(), 0); - assert_eq!(*e.key(), 1); - assert_eq!(*e.get(), "1"); - } - - { - let e = match map.get_index_entry(1) { - Some(e) => OccupiedEntry::from(e), - None => panic!(), - }; - assert_eq!(e.index(), 1); - assert_eq!(*e.key(), 2); - assert_eq!(*e.get(), "2"); - } -} - -#[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] -fn drain_range() { - // Test the various heuristics of `erase_indices` - for range in [ - 0..0, // nothing erased - 10..90, // reinsert the few kept (..10 and 90..) - 80..90, // update the few to adjust (80..) - 20..30, // sweep everything - ] { - let mut vec = Vec::from_iter(0..100); - let mut map: IndexMap<i32, ()> = (0..100).map(|i| (i, ())).collect(); - drop(vec.drain(range.clone())); - drop(map.drain(range)); - assert!(vec.iter().eq(map.keys())); - for (i, x) in vec.iter().enumerate() { - assert_eq!(map.get_index_of(x), Some(i)); - } - } -} - -#[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::<IterMut2<'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); -} - -macro_rules! move_index_oob { - ($test:ident, $from:expr, $to:expr) => { - #[test] - #[should_panic(expected = "index out of bounds")] - fn $test() { - let mut map: IndexMap<i32, ()> = (0..10).map(|k| (k, ())).collect(); - map.move_index($from, $to); - } - }; -} -move_index_oob!(test_move_index_out_of_bounds_0_10, 0, 10); -move_index_oob!(test_move_index_out_of_bounds_0_max, 0, usize::MAX); -move_index_oob!(test_move_index_out_of_bounds_10_0, 10, 0); -move_index_oob!(test_move_index_out_of_bounds_max_0, usize::MAX, 0); - -#[test] -fn disjoint_mut_empty_map() { - let mut map: IndexMap<u32, u32> = IndexMap::default(); - assert_eq!( - map.get_disjoint_mut([&0, &1, &2, &3]), - [None, None, None, None] - ); -} - -#[test] -fn disjoint_mut_empty_param() { - let mut map: IndexMap<u32, u32> = IndexMap::default(); - map.insert(1, 10); - assert_eq!(map.get_disjoint_mut([] as [&u32; 0]), []); -} - -#[test] -fn disjoint_mut_single_fail() { - let mut map: IndexMap<u32, u32> = IndexMap::default(); - map.insert(1, 10); - assert_eq!(map.get_disjoint_mut([&0]), [None]); -} - -#[test] -fn disjoint_mut_single_success() { - let mut map: IndexMap<u32, u32> = IndexMap::default(); - map.insert(1, 10); - assert_eq!(map.get_disjoint_mut([&1]), [Some(&mut 10)]); -} - -#[test] -fn disjoint_mut_multi_success() { - let mut map: IndexMap<u32, u32> = IndexMap::default(); - map.insert(1, 100); - map.insert(2, 200); - map.insert(3, 300); - map.insert(4, 400); - assert_eq!( - map.get_disjoint_mut([&1, &2]), - [Some(&mut 100), Some(&mut 200)] - ); - assert_eq!( - map.get_disjoint_mut([&1, &3]), - [Some(&mut 100), Some(&mut 300)] - ); - assert_eq!( - map.get_disjoint_mut([&3, &1, &4, &2]), - [ - Some(&mut 300), - Some(&mut 100), - Some(&mut 400), - Some(&mut 200) - ] - ); -} - -#[test] -fn disjoint_mut_multi_success_unsized_key() { - let mut map: IndexMap<&'static str, u32> = IndexMap::default(); - map.insert("1", 100); - map.insert("2", 200); - map.insert("3", 300); - map.insert("4", 400); - - assert_eq!( - map.get_disjoint_mut(["1", "2"]), - [Some(&mut 100), Some(&mut 200)] - ); - assert_eq!( - map.get_disjoint_mut(["1", "3"]), - [Some(&mut 100), Some(&mut 300)] - ); - assert_eq!( - map.get_disjoint_mut(["3", "1", "4", "2"]), - [ - Some(&mut 300), - Some(&mut 100), - Some(&mut 400), - Some(&mut 200) - ] - ); -} - -#[test] -fn disjoint_mut_multi_success_borrow_key() { - let mut map: IndexMap<String, u32> = IndexMap::default(); - map.insert("1".into(), 100); - map.insert("2".into(), 200); - map.insert("3".into(), 300); - map.insert("4".into(), 400); - - assert_eq!( - map.get_disjoint_mut(["1", "2"]), - [Some(&mut 100), Some(&mut 200)] - ); - assert_eq!( - map.get_disjoint_mut(["1", "3"]), - [Some(&mut 100), Some(&mut 300)] - ); - assert_eq!( - map.get_disjoint_mut(["3", "1", "4", "2"]), - [ - Some(&mut 300), - Some(&mut 100), - Some(&mut 400), - Some(&mut 200) - ] - ); -} - -#[test] -fn disjoint_mut_multi_fail_missing() { - let mut map: IndexMap<u32, u32> = IndexMap::default(); - map.insert(1, 100); - map.insert(2, 200); - map.insert(3, 300); - map.insert(4, 400); - - assert_eq!(map.get_disjoint_mut([&1, &5]), [Some(&mut 100), None]); - assert_eq!(map.get_disjoint_mut([&5, &6]), [None, None]); - assert_eq!( - map.get_disjoint_mut([&1, &5, &4]), - [Some(&mut 100), None, Some(&mut 400)] - ); -} - -#[test] -#[should_panic] -fn disjoint_mut_multi_fail_duplicate_panic() { - let mut map: IndexMap<u32, u32> = IndexMap::default(); - map.insert(1, 100); - map.get_disjoint_mut([&1, &2, &1]); -} - -#[test] -fn disjoint_indices_mut_fail_oob() { - let mut map: IndexMap<u32, u32> = IndexMap::default(); - map.insert(1, 10); - map.insert(321, 20); - assert_eq!( - map.get_disjoint_indices_mut([1, 3]), - Err(crate::GetDisjointMutError::IndexOutOfBounds) - ); -} - -#[test] -fn disjoint_indices_mut_empty() { - let mut map: IndexMap<u32, u32> = IndexMap::default(); - map.insert(1, 10); - map.insert(321, 20); - assert_eq!(map.get_disjoint_indices_mut([]), Ok([])); -} - -#[test] -fn disjoint_indices_mut_success() { - let mut map: IndexMap<u32, u32> = IndexMap::default(); - map.insert(1, 10); - map.insert(321, 20); - assert_eq!(map.get_disjoint_indices_mut([0]), Ok([(&1, &mut 10)])); - - assert_eq!(map.get_disjoint_indices_mut([1]), Ok([(&321, &mut 20)])); - assert_eq!( - map.get_disjoint_indices_mut([0, 1]), - Ok([(&1, &mut 10), (&321, &mut 20)]) - ); -} - -#[test] -fn disjoint_indices_mut_fail_duplicate() { - let mut map: IndexMap<u32, u32> = IndexMap::default(); - map.insert(1, 10); - map.insert(321, 20); - assert_eq!( - map.get_disjoint_indices_mut([1, 0, 1]), - Err(crate::GetDisjointMutError::OverlappingIndices) - ); -} |