Merging upstream version 127.0.

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

1 files changed, 192 insertions, 6 deletions

diff --git a/third_party/rust/indexmap/tests/quick.rs b/third_party/rust/indexmap/tests/quick.rs
index e9d96acccb..56afee7239 100644
--- a/third_party/rust/indexmap/tests/quick.rs
+++ b/third_party/rust/indexmap/tests/quick.rs
@@ -19,8 +19,8 @@ use std::hash::Hash;
 use std::ops::Bound;
 use std::ops::Deref;
 
-use indexmap::map::Entry as OEntry;
-use std::collections::hash_map::Entry as HEntry;
+use indexmap::map::Entry;
+use std::collections::hash_map::Entry as StdEntry;
 
 fn set<'a, T: 'a, I>(iter: I) -> HashSet<T>
 where
@@ -113,6 +113,23 @@ quickcheck_limit! {
         true
     }
 
+    fn insert_sorted(insert: Vec<(u32, u32)>) -> bool {
+        let mut hmap = HashMap::new();
+        let mut map = IndexMap::new();
+        let mut map2 = IndexMap::new();
+        for &(key, value) in &insert {
+            hmap.insert(key, value);
+            map.insert_sorted(key, value);
+            match map2.entry(key) {
+                Entry::Occupied(e) => *e.into_mut() = value,
+                Entry::Vacant(e) => { e.insert_sorted(value); }
+            }
+        }
+        itertools::assert_equal(hmap.iter().sorted(), &map);
+        itertools::assert_equal(&map, &map2);
+        true
+    }
+
     fn pop(insert: Vec<u8>) -> bool {
         let mut map = IndexMap::new();
         for &key in &insert {
@@ -218,7 +235,7 @@ quickcheck_limit! {
     }
 
     // Use `u8` test indices so quickcheck is less likely to go out of bounds.
-    fn swap_indices(vec: Vec<u8>, a: u8, b: u8) -> TestResult {
+    fn set_swap_indices(vec: Vec<u8>, a: u8, b: u8) -> TestResult {
         let mut set = IndexSet::<u8>::from_iter(vec);
         let a = usize::from(a);
         let b = usize::from(b);
@@ -240,8 +257,39 @@ quickcheck_limit! {
         TestResult::passed()
     }
 
+    fn map_swap_indices(vec: Vec<u8>, from: u8, to: u8) -> TestResult {
+        test_map_swap_indices(vec, from, to, IndexMap::swap_indices)
+    }
+
+    fn occupied_entry_swap_indices(vec: Vec<u8>, from: u8, to: u8) -> TestResult {
+        test_map_swap_indices(vec, from, to, |map, from, to| {
+            let key = map.keys()[from];
+            match map.entry(key) {
+                Entry::Occupied(entry) => entry.swap_indices(to),
+                _ => unreachable!(),
+            }
+        })
+    }
+
+    fn indexed_entry_swap_indices(vec: Vec<u8>, from: u8, to: u8) -> TestResult {
+        test_map_swap_indices(vec, from, to, |map, from, to| {
+            map.get_index_entry(from).unwrap().swap_indices(to);
+        })
+    }
+
+    fn raw_occupied_entry_swap_indices(vec: Vec<u8>, from: u8, to: u8) -> TestResult {
+        use indexmap::map::raw_entry_v1::{RawEntryApiV1, RawEntryMut};
+        test_map_swap_indices(vec, from, to, |map, from, to| {
+            let key = map.keys()[from];
+            match map.raw_entry_mut_v1().from_key(&key) {
+                RawEntryMut::Occupied(entry) => entry.swap_indices(to),
+                _ => unreachable!(),
+            }
+        })
+    }
+
     // Use `u8` test indices so quickcheck is less likely to go out of bounds.
-    fn move_index(vec: Vec<u8>, from: u8, to: u8) -> TestResult {
+    fn set_move_index(vec: Vec<u8>, from: u8, to: u8) -> TestResult {
         let mut set = IndexSet::<u8>::from_iter(vec);
         let from = usize::from(from);
         let to = usize::from(to);
@@ -263,6 +311,138 @@ quickcheck_limit! {
         }));
         TestResult::passed()
     }
+
+    fn map_move_index(vec: Vec<u8>, from: u8, to: u8) -> TestResult {
+        test_map_move_index(vec, from, to, IndexMap::move_index)
+    }
+
+    fn occupied_entry_move_index(vec: Vec<u8>, from: u8, to: u8) -> TestResult {
+        test_map_move_index(vec, from, to, |map, from, to| {
+            let key = map.keys()[from];
+            match map.entry(key) {
+                Entry::Occupied(entry) => entry.move_index(to),
+                _ => unreachable!(),
+            }
+        })
+    }
+
+    fn indexed_entry_move_index(vec: Vec<u8>, from: u8, to: u8) -> TestResult {
+        test_map_move_index(vec, from, to, |map, from, to| {
+            map.get_index_entry(from).unwrap().move_index(to);
+        })
+    }
+
+    fn raw_occupied_entry_move_index(vec: Vec<u8>, from: u8, to: u8) -> TestResult {
+        use indexmap::map::raw_entry_v1::{RawEntryApiV1, RawEntryMut};
+        test_map_move_index(vec, from, to, |map, from, to| {
+            let key = map.keys()[from];
+            match map.raw_entry_mut_v1().from_key(&key) {
+                RawEntryMut::Occupied(entry) => entry.move_index(to),
+                _ => unreachable!(),
+            }
+        })
+    }
+
+    fn occupied_entry_shift_insert(vec: Vec<u8>, i: u8) -> TestResult {
+        test_map_shift_insert(vec, i, |map, i, key| {
+            match map.entry(key) {
+                Entry::Vacant(entry) => entry.shift_insert(i, ()),
+                _ => unreachable!(),
+            };
+        })
+    }
+
+    fn raw_occupied_entry_shift_insert(vec: Vec<u8>, i: u8) -> TestResult {
+        use indexmap::map::raw_entry_v1::{RawEntryApiV1, RawEntryMut};
+        test_map_shift_insert(vec, i, |map, i, key| {
+            match map.raw_entry_mut_v1().from_key(&key) {
+                RawEntryMut::Vacant(entry) => entry.shift_insert(i, key, ()),
+                _ => unreachable!(),
+            };
+        })
+    }
+}
+
+fn test_map_swap_indices<F>(vec: Vec<u8>, a: u8, b: u8, swap_indices: F) -> TestResult
+where
+    F: FnOnce(&mut IndexMap<u8, ()>, usize, usize),
+{
+    let mut map = IndexMap::<u8, ()>::from_iter(vec.into_iter().map(|k| (k, ())));
+    let a = usize::from(a);
+    let b = usize::from(b);
+
+    if a >= map.len() || b >= map.len() {
+        return TestResult::discard();
+    }
+
+    let mut vec = Vec::from_iter(map.keys().copied());
+    vec.swap(a, b);
+
+    swap_indices(&mut map, a, b);
+
+    // Check both iteration order and hash lookups
+    assert!(map.keys().eq(vec.iter()));
+    assert!(vec
+        .iter()
+        .enumerate()
+        .all(|(i, x)| { map.get_index_of(x) == Some(i) }));
+    TestResult::passed()
+}
+
+fn test_map_move_index<F>(vec: Vec<u8>, from: u8, to: u8, move_index: F) -> TestResult
+where
+    F: FnOnce(&mut IndexMap<u8, ()>, usize, usize),
+{
+    let mut map = IndexMap::<u8, ()>::from_iter(vec.into_iter().map(|k| (k, ())));
+    let from = usize::from(from);
+    let to = usize::from(to);
+
+    if from >= map.len() || to >= map.len() {
+        return TestResult::discard();
+    }
+
+    let mut vec = Vec::from_iter(map.keys().copied());
+    let x = vec.remove(from);
+    vec.insert(to, x);
+
+    move_index(&mut map, from, to);
+
+    // Check both iteration order and hash lookups
+    assert!(map.keys().eq(vec.iter()));
+    assert!(vec
+        .iter()
+        .enumerate()
+        .all(|(i, x)| { map.get_index_of(x) == Some(i) }));
+    TestResult::passed()
+}
+
+fn test_map_shift_insert<F>(vec: Vec<u8>, i: u8, shift_insert: F) -> TestResult
+where
+    F: FnOnce(&mut IndexMap<u8, ()>, usize, u8),
+{
+    let mut map = IndexMap::<u8, ()>::from_iter(vec.into_iter().map(|k| (k, ())));
+    let i = usize::from(i);
+    if i >= map.len() {
+        return TestResult::discard();
+    }
+
+    let mut vec = Vec::from_iter(map.keys().copied());
+    let x = vec.pop().unwrap();
+    vec.insert(i, x);
+
+    let (last, ()) = map.pop().unwrap();
+    assert_eq!(x, last);
+    map.shrink_to_fit(); // so we might have to grow and rehash the table
+
+    shift_insert(&mut map, i, last);
+
+    // Check both iteration order and hash lookups
+    assert!(map.keys().eq(vec.iter()));
+    assert!(vec
+        .iter()
+        .enumerate()
+        .all(|(i, x)| { map.get_index_of(x) == Some(i) }));
+    TestResult::passed()
 }
 
 use crate::Op::*;
@@ -310,10 +490,10 @@ where
                 b.remove(k);
             }
             RemoveEntry(ref k) => {
-                if let OEntry::Occupied(ent) = a.entry(k.clone()) {
+                if let Entry::Occupied(ent) = a.entry(k.clone()) {
                     ent.swap_remove_entry();
                 }
-                if let HEntry::Occupied(ent) = b.entry(k.clone()) {
+                if let StdEntry::Occupied(ent) = b.entry(k.clone()) {
                     ent.remove_entry();
                 }
             }
@@ -452,6 +632,12 @@ quickcheck_limit! {
         assert_sorted_by_key(map, |t| t.1);
     }
 
+    fn sort_3(keyvals: Large<Vec<(i8, i8)>>) -> () {
+        let mut map: IndexMap<_, _> = IndexMap::from_iter(keyvals.to_vec());
+        map.sort_by_cached_key(|&k, _| std::cmp::Reverse(k));
+        assert_sorted_by_key(map, |t| std::cmp::Reverse(t.0));
+    }
+
     fn reverse(keyvals: Large<Vec<(i8, i8)>>) -> () {
         let mut map: IndexMap<_, _> = IndexMap::from_iter(keyvals.to_vec());