Merging upstream version 1.76.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

4 files changed, 313 insertions, 26 deletions

diff --git a/vendor/indexmap/src/map/core.rs b/vendor/indexmap/src/map/core.rs
index 3e392ace6..4a78035c9 100644
--- a/vendor/indexmap/src/map/core.rs
+++ b/vendor/indexmap/src/map/core.rs
@@ -410,6 +410,26 @@ impl<K, V> IndexMapCore<K, V> {
         }
     }
 
+    pub(crate) fn swap_indices(&mut self, a: usize, b: usize) {
+        // If they're equal and in-bounds, there's nothing to do.
+        if a == b && a < self.entries.len() {
+            return;
+        }
+
+        // We'll get a "nice" bounds-check from indexing `self.entries`,
+        // and then we expect to find it in the table as well.
+        let [ref_a, ref_b] = self
+            .indices
+            .get_many_mut(
+                [self.entries[a].hash.get(), self.entries[b].hash.get()],
+                move |i, &x| if i == 0 { x == a } else { x == b },
+            )
+            .expect("indices not found");
+
+        mem::swap(ref_a, ref_b);
+        self.entries.swap(a, b);
+    }
+
     /// Remove an entry by swapping it with the last
     pub(crate) fn swap_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)>
     where
diff --git a/vendor/indexmap/src/map/core/raw.rs b/vendor/indexmap/src/map/core/raw.rs
index 332770cc2..be71c9cff 100644
--- a/vendor/indexmap/src/map/core/raw.rs
+++ b/vendor/indexmap/src/map/core/raw.rs
@@ -100,29 +100,6 @@ impl<K, V> IndexMapCore<K, V> {
         // only the item references that are appropriately bound to `&mut self`.
         unsafe { self.indices.iter().map(|bucket| bucket.as_mut()) }
     }
-
-    /// Return the raw bucket for the given index
-    fn find_index(&self, index: usize) -> RawBucket {
-        // We'll get a "nice" bounds-check from indexing `self.entries`,
-        // and then we expect to find it in the table as well.
-        let hash = self.entries[index].hash.get();
-        self.indices
-            .find(hash, move |&i| i == index)
-            .expect("index not found")
-    }
-
-    pub(crate) fn swap_indices(&mut self, a: usize, b: usize) {
-        // SAFETY: Can't take two `get_mut` references from one table, so we
-        // must use raw buckets to do the swap. This is still safe because we
-        // are locally sure they won't dangle, and we write them individually.
-        unsafe {
-            let raw_bucket_a = self.find_index(a);
-            let raw_bucket_b = self.find_index(b);
-            *raw_bucket_a.as_mut() = b;
-            *raw_bucket_b.as_mut() = a;
-        }
-        self.entries.swap(a, b);
-    }
 }
 
 /// A view into an occupied entry in a `IndexMap`.
diff --git a/vendor/indexmap/src/map/slice.rs b/vendor/indexmap/src/map/slice.rs
index 9fb876fd2..ebab208c9 100644
--- a/vendor/indexmap/src/map/slice.rs
+++ b/vendor/indexmap/src/map/slice.rs
@@ -27,7 +27,7 @@ pub struct Slice<K, V> {
 // and reference lifetimes are bound together in function signatures.
 #[allow(unsafe_code)]
 impl<K, V> Slice<K, V> {
-    pub(super) fn from_slice(entries: &[Bucket<K, V>]) -> &Self {
+    pub(super) const fn from_slice(entries: &[Bucket<K, V>]) -> &Self {
         unsafe { &*(entries as *const [Bucket<K, V>] as *const Self) }
     }
 
@@ -49,15 +49,25 @@ impl<K, V> Slice<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 fn len(&self) -> usize {
+    pub const fn len(&self) -> usize {
         self.entries.len()
     }
 
     /// Returns true if the map slice contains no elements.
     #[inline]
-    pub fn is_empty(&self) -> bool {
+    pub const fn is_empty(&self) -> bool {
         self.entries.is_empty()
     }
 
@@ -201,6 +211,65 @@ impl<K, V> Slice<K, V> {
     pub fn into_values(self: Box<Self>) -> IntoValues<K, V> {
         IntoValues::new(self.into_entries())
     }
+
+    /// Search over a sorted map for a key.
+    ///
+    /// Returns the position where that key is present, or the position where it can be inserted to
+    /// maintain the sort. See [`slice::binary_search`] for more details.
+    ///
+    /// Computes in **O(log(n))** time, which is notably less scalable than looking the key up in
+    /// the map this is a slice from using [`IndexMap::get_index_of`], but this can also position
+    /// missing keys.
+    pub fn binary_search_keys(&self, x: &K) -> Result<usize, usize>
+    where
+        K: Ord,
+    {
+        self.binary_search_by(|p, _| p.cmp(x))
+    }
+
+    /// Search over a sorted map with a comparator function.
+    ///
+    /// Returns the position where that value is present, or the position where it can be inserted
+    /// to maintain the sort. See [`slice::binary_search_by`] for more details.
+    ///
+    /// Computes in **O(log(n))** time.
+    #[inline]
+    pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
+    where
+        F: FnMut(&'a K, &'a V) -> Ordering,
+    {
+        self.entries.binary_search_by(move |a| f(&a.key, &a.value))
+    }
+
+    /// Search over a sorted map with an extraction function.
+    ///
+    /// Returns the position where that value is present, or the position where it can be inserted
+    /// to maintain the sort. See [`slice::binary_search_by_key`] for more details.
+    ///
+    /// Computes in **O(log(n))** time.
+    #[inline]
+    pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
+    where
+        F: FnMut(&'a K, &'a V) -> B,
+        B: Ord,
+    {
+        self.binary_search_by(|k, v| f(k, v).cmp(b))
+    }
+
+    /// Returns the index of the partition point of a sorted map according to the given predicate
+    /// (the index of the first element of the second partition).
+    ///
+    /// See [`slice::partition_point`] for more details.
+    ///
+    /// Computes in **O(log(n))** time.
+    #[must_use]
+    pub fn partition_point<P>(&self, mut pred: P) -> usize
+    where
+        P: FnMut(&K, &V) -> bool,
+    {
+        self.entries
+            .partition_point(move |a| pred(&a.key, &a.value))
+    }
 }
 
 impl<'a, K, V> IntoIterator for &'a Slice<K, V> {
diff --git a/vendor/indexmap/src/map/tests.rs b/vendor/indexmap/src/map/tests.rs
index f273d7162..3d2315d3e 100644
--- a/vendor/indexmap/src/map/tests.rs
+++ b/vendor/indexmap/src/map/tests.rs
@@ -447,3 +447,224 @@ fn iter_default() {
     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);
+}