1 files changed, 93 insertions, 51 deletions

diff --git a/vendor/indexmap/src/map/core.rs b/vendor/indexmap/src/map/core.rs
index ea7aaae62..3e392ace6 100644
--- a/vendor/indexmap/src/map/core.rs
+++ b/vendor/indexmap/src/map/core.rs
@@ -12,14 +12,13 @@ mod raw;
 use hashbrown::raw::RawTable;
 
 use crate::vec::{Drain, Vec};
-use core::cmp;
+use crate::TryReserveError;
 use core::fmt;
-use core::mem::replace;
+use core::mem;
 use core::ops::RangeBounds;
 
-use crate::equivalent::Equivalent;
 use crate::util::simplify_range;
-use crate::{Bucket, Entries, HashValue};
+use crate::{Bucket, Entries, Equivalent, HashValue};
 
 /// Core of the map that does not depend on S
 pub(crate) struct IndexMapCore<K, V> {
@@ -62,18 +61,18 @@ where
     V: Clone,
 {
     fn clone(&self) -> Self {
-        let indices = self.indices.clone();
-        let mut entries = Vec::with_capacity(indices.capacity());
-        entries.clone_from(&self.entries);
-        IndexMapCore { indices, entries }
+        let mut new = Self::new();
+        new.clone_from(self);
+        new
     }
 
     fn clone_from(&mut self, other: &Self) {
         let hasher = get_hash(&other.entries);
         self.indices.clone_from_with_hasher(&other.indices, hasher);
         if self.entries.capacity() < other.entries.len() {
-            // If we must resize, match the indices capacity
-            self.reserve_entries();
+            // If we must resize, match the indices capacity.
+            let additional = other.entries.len() - self.entries.len();
+            self.reserve_entries(additional);
         }
         self.entries.clone_from(&other.entries);
     }
@@ -120,6 +119,9 @@ impl<K, V> Entries for IndexMapCore<K, V> {
 }
 
 impl<K, V> IndexMapCore<K, V> {
+    /// The maximum capacity before the `entries` allocation would exceed `isize::MAX`.
+    const MAX_ENTRIES_CAPACITY: usize = (isize::MAX as usize) / mem::size_of::<Bucket<K, V>>();
+
     #[inline]
     pub(crate) const fn new() -> Self {
         IndexMapCore {
@@ -143,7 +145,7 @@ impl<K, V> IndexMapCore<K, V> {
 
     #[inline]
     pub(crate) fn capacity(&self) -> usize {
-        cmp::min(self.indices.capacity(), self.entries.capacity())
+        Ord::min(self.indices.capacity(), self.entries.capacity())
     }
 
     pub(crate) fn clear(&mut self) {
@@ -193,15 +195,67 @@ impl<K, V> IndexMapCore<K, V> {
     /// Reserve capacity for `additional` more key-value pairs.
     pub(crate) fn reserve(&mut self, additional: usize) {
         self.indices.reserve(additional, get_hash(&self.entries));
-        self.reserve_entries();
+        // Only grow entries if necessary, since we also round up capacity.
+        if additional > self.entries.capacity() - self.entries.len() {
+            self.reserve_entries(additional);
+        }
     }
 
-    /// Reserve entries capacity to match the indices
-    fn reserve_entries(&mut self) {
-        let additional = self.indices.capacity() - self.entries.len();
+    /// Reserve entries capacity, rounded up to match the indices
+    fn reserve_entries(&mut self, additional: usize) {
+        // Use a soft-limit on the maximum capacity, but if the caller explicitly
+        // requested more, do it and let them have the resulting panic.
+        let new_capacity = Ord::min(self.indices.capacity(), Self::MAX_ENTRIES_CAPACITY);
+        let try_add = new_capacity - self.entries.len();
+        if try_add > additional && self.entries.try_reserve_exact(try_add).is_ok() {
+            return;
+        }
+        self.entries.reserve_exact(additional);
+    }
+
+    /// Reserve capacity for `additional` more key-value pairs, without over-allocating.
+    pub(crate) fn reserve_exact(&mut self, additional: usize) {
+        self.indices.reserve(additional, get_hash(&self.entries));
         self.entries.reserve_exact(additional);
     }
 
+    /// Try to reserve capacity for `additional` more key-value pairs.
+    pub(crate) fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
+        self.indices
+            .try_reserve(additional, get_hash(&self.entries))
+            .map_err(TryReserveError::from_hashbrown)?;
+        // Only grow entries if necessary, since we also round up capacity.
+        if additional > self.entries.capacity() - self.entries.len() {
+            self.try_reserve_entries(additional)
+        } else {
+            Ok(())
+        }
+    }
+
+    /// Try to reserve entries capacity, rounded up to match the indices
+    fn try_reserve_entries(&mut self, additional: usize) -> Result<(), TryReserveError> {
+        // Use a soft-limit on the maximum capacity, but if the caller explicitly
+        // requested more, do it and let them have the resulting error.
+        let new_capacity = Ord::min(self.indices.capacity(), Self::MAX_ENTRIES_CAPACITY);
+        let try_add = new_capacity - self.entries.len();
+        if try_add > additional && self.entries.try_reserve_exact(try_add).is_ok() {
+            return Ok(());
+        }
+        self.entries
+            .try_reserve_exact(additional)
+            .map_err(TryReserveError::from_alloc)
+    }
+
+    /// Try to reserve capacity for `additional` more key-value pairs, without over-allocating.
+    pub(crate) fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
+        self.indices
+            .try_reserve(additional, get_hash(&self.entries))
+            .map_err(TryReserveError::from_hashbrown)?;
+        self.entries
+            .try_reserve_exact(additional)
+            .map_err(TryReserveError::from_alloc)
+    }
+
     /// Shrink the capacity of the map with a lower bound
     pub(crate) fn shrink_to(&mut self, min_capacity: usize) {
         self.indices
@@ -220,18 +274,14 @@ impl<K, V> IndexMapCore<K, V> {
         }
     }
 
-    /// Append a key-value pair, *without* checking whether it already exists,
-    /// and return the pair's new index.
-    fn push(&mut self, hash: HashValue, key: K, value: V) -> usize {
-        let i = self.entries.len();
-        self.indices.insert(hash.get(), i, get_hash(&self.entries));
-        if i == self.entries.capacity() {
+    /// Append a key-value pair to `entries`, *without* checking whether it already exists.
+    fn push_entry(&mut self, hash: HashValue, key: K, value: V) {
+        if self.entries.len() == self.entries.capacity() {
             // Reserve our own capacity synced to the indices,
             // rather than letting `Vec::push` just double it.
-            self.reserve_entries();
+            self.reserve_entries(1);
         }
         self.entries.push(Bucket { hash, key, value });
-        i
     }
 
     /// Return the index in `entries` where an equivalent key can be found
@@ -247,9 +297,13 @@ impl<K, V> IndexMapCore<K, V> {
     where
         K: Eq,
     {
-        match self.get_index_of(hash, &key) {
-            Some(i) => (i, Some(replace(&mut self.entries[i].value, value))),
-            None => (self.push(hash, key, value), None),
+        match self.find_or_insert(hash, &key) {
+            Ok(i) => (i, Some(mem::replace(&mut self.entries[i].value, value))),
+            Err(i) => {
+                debug_assert_eq!(i, self.entries.len());
+                self.push_entry(hash, key, value);
+                (i, None)
+            }
         }
     }
 
@@ -339,7 +393,7 @@ impl<K, V> IndexMapCore<K, V> {
     pub(super) fn move_index(&mut self, from: usize, to: usize) {
         let from_hash = self.entries[from].hash;
         if from != to {
-            // Use a sentinal index so other indices don't collide.
+            // Use a sentinel index so other indices don't collide.
             update_index(&mut self.indices, from_hash, from, usize::MAX);
 
             // Update all other indices and rotate the entry positions.
@@ -351,7 +405,7 @@ impl<K, V> IndexMapCore<K, V> {
                 self.entries[to..=from].rotate_right(1);
             }
 
-            // Change the sentinal index to its final position.
+            // Change the sentinel index to its final position.
             update_index(&mut self.indices, from_hash, usize::MAX, to);
         }
     }
@@ -447,25 +501,9 @@ impl<K, V> IndexMapCore<K, V> {
     where
         F: FnMut(&mut K, &mut V) -> bool,
     {
-        // FIXME: This could use Vec::retain_mut with MSRV 1.61.
-        // Like Vec::retain in self.entries, but with mutable K and V.
-        // We swap-shift all the items we want to keep, truncate the rest,
-        // then rebuild the raw hash table with the new indexes.
-        let len = self.entries.len();
-        let mut n_deleted = 0;
-        for i in 0..len {
-            let will_keep = {
-                let entry = &mut self.entries[i];
-                keep(&mut entry.key, &mut entry.value)
-            };
-            if !will_keep {
-                n_deleted += 1;
-            } else if n_deleted > 0 {
-                self.entries.swap(i - n_deleted, i);
-            }
-        }
-        if n_deleted > 0 {
-            self.entries.truncate(len - n_deleted);
+        self.entries
+            .retain_mut(|entry| keep(&mut entry.key, &mut entry.value));
+        if self.entries.len() < self.indices.len() {
             self.rebuild_hash_table();
         }
     }
@@ -601,7 +639,7 @@ pub use self::raw::OccupiedEntry;
 impl<K, V> OccupiedEntry<'_, K, V> {
     /// Sets the value of the entry to `value`, and returns the entry's old value.
     pub fn insert(&mut self, value: V) -> V {
-        replace(self.get_mut(), value)
+        mem::replace(self.get_mut(), value)
     }
 
     /// Remove the key, value pair stored in the map for this entry, and return the value.
@@ -673,14 +711,18 @@ impl<'a, K, V> VacantEntry<'a, K, V> {
 
     /// Return the index where the key-value pair will be inserted.
     pub fn index(&self) -> usize {
-        self.map.len()
+        self.map.indices.len()
     }
 
     /// Inserts the entry's key and the given value into the map, and returns a mutable reference
     /// to the value.
     pub fn insert(self, value: V) -> &'a mut V {
-        let i = self.map.push(self.hash, self.key, value);
-        &mut self.map.entries[i].value
+        let i = self.index();
+        let Self { map, hash, key } = self;
+        map.indices.insert(hash.get(), i, get_hash(&map.entries));
+        debug_assert_eq!(i, map.entries.len());
+        map.push_entry(hash, key, value);
+        &mut map.entries[i].value
     }
 }