Merging upstream version 1.71.1+dfsg1.

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

5 files changed, 50 insertions, 25 deletions

diff --git a/vendor/litemap/src/map.rs b/vendor/litemap/src/map.rs
index 669dc464d..bcd7eb8c9 100644
--- a/vendor/litemap/src/map.rs
+++ b/vendor/litemap/src/map.rs
@@ -153,9 +153,8 @@ where
     /// ```rust
     /// use litemap::LiteMap;
     ///
-    /// let mut map = LiteMap::new_vec();
-    /// assert!(map.try_append(1, "uno").is_none());
-    /// assert!(map.try_append(3, "tres").is_none());
+    /// let mut map: LiteMap<i32, &str, Vec<_>> =
+    ///     LiteMap::from_iter([(1, "uno"), (3, "tres")].into_iter());
     ///
     /// assert_eq!(map.first(), Some((&1, &"uno")));
     /// ```
@@ -171,9 +170,8 @@ where
     /// ```rust
     /// use litemap::LiteMap;
     ///
-    /// let mut map = LiteMap::new_vec();
-    /// assert!(map.try_append(1, "uno").is_none());
-    /// assert!(map.try_append(3, "tres").is_none());
+    /// let mut map: LiteMap<i32, &str, Vec<_>> =
+    ///     LiteMap::from_iter([(1, "uno"), (3, "tres")].into_iter());
     ///
     /// assert_eq!(map.last(), Some((&3, &"tres")));
     /// ```
@@ -500,22 +498,11 @@ where
 impl<K, V, S> FromIterator<(K, V)> for LiteMap<K, V, S>
 where
     K: Ord,
-    S: StoreMut<K, V>,
+    S: StoreFromIterable<K, V>,
 {
     fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
-        let iter = iter.into_iter();
-        let mut map = match iter.size_hint() {
-            (_, Some(upper)) => Self::with_capacity(upper),
-            (lower, None) => Self::with_capacity(lower),
-        };
-
-        for (key, value) in iter {
-            if let Some((key, value)) = map.try_append(key, value) {
-                map.insert(key, value);
-            }
-        }
-
-        map
+        let values = S::lm_sort_from_iter(iter);
+        Self::from_sorted_store_unchecked(values)
     }
 }
 
@@ -609,7 +596,6 @@ mod test {
 
         assert_eq!(expected, actual);
     }
-
     fn make_13() -> LiteMap<usize, &'static str> {
         let mut result = LiteMap::new();
         result.insert(1, "one");
diff --git a/vendor/litemap/src/serde.rs b/vendor/litemap/src/serde.rs
index 7550fb7a9..019f0fdbb 100644
--- a/vendor/litemap/src/serde.rs
+++ b/vendor/litemap/src/serde.rs
@@ -64,7 +64,7 @@ impl<'de, K, V, R> Visitor<'de> for LiteMapVisitor<K, V, R>
 where
     K: Deserialize<'de> + Ord,
     V: Deserialize<'de>,
-    R: StoreMut<K, V>,
+    R: StoreMut<K, V> + StoreFromIterable<K, V>,
 {
     type Value = LiteMap<K, V, R>;
 
@@ -127,7 +127,7 @@ impl<'de, K, V, R> Deserialize<'de> for LiteMap<K, V, R>
 where
     K: Ord + Deserialize<'de>,
     V: Deserialize<'de>,
-    R: StoreMut<K, V>,
+    R: StoreMut<K, V> + StoreFromIterable<K, V>,
 {
     fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
     where
diff --git a/vendor/litemap/src/store/mod.rs b/vendor/litemap/src/store/mod.rs
index 7f4386783..3468ebb97 100644
--- a/vendor/litemap/src/store/mod.rs
+++ b/vendor/litemap/src/store/mod.rs
@@ -71,6 +71,11 @@ pub trait Store<K: ?Sized, V: ?Sized>: Sized {
         F: FnMut(&K) -> Ordering;
 }
 
+pub trait StoreFromIterable<K, V>: Store<K, V> {
+    /// Create a sorted store from `iter`.
+    fn lm_sort_from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self;
+}
+
 pub trait StoreMut<K, V>: Store<K, V> {
     /// Creates a new store with the specified capacity hint.
     ///
@@ -84,6 +89,7 @@ pub trait StoreMut<K, V>: Store<K, V> {
 
     /// Gets a key/value pair at the specified index, with a mutable value.
     fn lm_get_mut(&mut self, index: usize) -> Option<(&K, &mut V)>;
+
     /// Pushes one additional item onto the store.
     fn lm_push(&mut self, key: K, value: V);
 
diff --git a/vendor/litemap/src/store/vec_impl.rs b/vendor/litemap/src/store/vec_impl.rs
index e94e0fb7f..361b926c3 100644
--- a/vendor/litemap/src/store/vec_impl.rs
+++ b/vendor/litemap/src/store/vec_impl.rs
@@ -98,6 +98,39 @@ impl<K, V> StoreMut<K, V> for Vec<(K, V)> {
     }
 }
 
+impl<K: Ord, V> StoreFromIterable<K, V> for Vec<(K, V)> {
+    fn lm_sort_from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
+        let iter = iter.into_iter();
+        let mut container = match iter.size_hint() {
+            (_, Some(upper)) => Self::with_capacity(upper),
+            (lower, None) => Self::with_capacity(lower),
+        };
+
+        for (key, value) in iter {
+            if let Some(last) = container.lm_last() {
+                if last.0 >= &key {
+                    match container.lm_binary_search_by(|k| k.cmp(&key)) {
+                        #[allow(clippy::unwrap_used)] // Index came from binary_search
+                        Ok(found) => {
+                            let _ =
+                                core::mem::replace(container.lm_get_mut(found).unwrap().1, value);
+                        }
+                        Err(ins) => {
+                            container.insert(ins, (key, value));
+                        }
+                    }
+                } else {
+                    container.push((key, value))
+                }
+            } else {
+                container.push((key, value))
+            }
+        }
+
+        container
+    }
+}
+
 impl<'a, K: 'a, V: 'a> StoreIterable<'a, K, V> for Vec<(K, V)> {
     type KeyValueIter = core::iter::Map<core::slice::Iter<'a, (K, V)>, MapF<K, V>>;
 
diff --git a/vendor/litemap/src/testing.rs b/vendor/litemap/src/testing.rs
index 827c8dd23..2fb8c522a 100644
--- a/vendor/litemap/src/testing.rs
+++ b/vendor/litemap/src/testing.rs
@@ -98,7 +98,7 @@ where
     for (k, v) in SORTED_DATA.iter() {
         #[allow(clippy::single_match)] // for clarity
         match map.try_append(*k, *v) {
-            Some(_) => panic!("appending sorted data: {:?} to {:?}", k, map),
+            Some(_) => panic!("appending sorted data: {k:?} to {map:?}"),
             None => (), // OK
         };
     }
@@ -107,7 +107,7 @@ where
         #[allow(clippy::single_match)] // for clarity
         match map.try_append(*k, *v) {
             Some(_) => (), // OK
-            None => panic!("cannot append random data: {:?} to{:?}", k, map),
+            None => panic!("cannot append random data: {k:?} to{map:?}"),
         };
     }
     assert_eq!(10, map.len());