Auto merge of #74710 - JohnTitor:rollup-bdz4oee, r=JohnTitor

Rollup of 12 pull requests

Successful merges:

 - #74361 (Improve doc theme logo display)
 - #74504 (Add right border bar to Dark and Light theme)
 - #74572 (Internally unify rustc_deprecated and deprecated)
 - #74601 (Clean up E0724 explanation)
 - #74623 (polymorphize GlobalAlloc::Function)
 - #74665 (Don't ICE on unconstrained anonymous lifetimes inside associated types.)
 - #74666 (More BTreeMap test cases, some exposing undefined behaviour)
 - #74669 (Fix typo)
 - #74677 (Remove needless unsafety from BTreeMap::drain_filter)
 - #74680 (Add missing backticks in diagnostics note)
 - #74694 (Clean up E0727 explanation)
 - #74703 (Fix ICE while building MIR with type errors)

Failed merges:

r? @ghost

2 files changed, 127 insertions, 20 deletions

diff --git a/src/liballoc/collections/btree/map.rs b/src/liballoc/collections/btree/map.rs
index d2f4278d0d0..24d1f61fa68 100644
--- a/src/liballoc/collections/btree/map.rs
+++ b/src/liballoc/collections/btree/map.rs
@@ -1672,19 +1672,12 @@ impl<'a, K: 'a, V: 'a> DrainFilterInner<'a, K, V> {
         edge.reborrow().next_kv().ok().map(|kv| kv.into_kv())
     }
 
-    unsafe fn next_kv(
-        &mut self,
-    ) -> Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>> {
-        let edge = self.cur_leaf_edge.as_ref()?;
-        unsafe { ptr::read(edge).next_kv().ok() }
-    }
-
     /// Implementation of a typical `DrainFilter::next` method, given the predicate.
     pub(super) fn next<F>(&mut self, pred: &mut F) -> Option<(K, V)>
     where
         F: FnMut(&K, &mut V) -> bool,
     {
-        while let Some(mut kv) = unsafe { self.next_kv() } {
+        while let Ok(mut kv) = self.cur_leaf_edge.take()?.next_kv() {
             let (k, v) = kv.kv_mut();
             if pred(k, v) {
                 *self.length -= 1;
diff --git a/src/liballoc/tests/btree/map.rs b/src/liballoc/tests/btree/map.rs
index f66b5814ca0..f9f81716e35 100644
--- a/src/liballoc/tests/btree/map.rs
+++ b/src/liballoc/tests/btree/map.rs
@@ -3,6 +3,7 @@ use std::collections::BTreeMap;
 use std::convert::TryFrom;
 use std::fmt::Debug;
 use std::iter::FromIterator;
+use std::mem;
 use std::ops::Bound::{self, Excluded, Included, Unbounded};
 use std::ops::RangeBounds;
 use std::panic::{catch_unwind, AssertUnwindSafe};
@@ -25,6 +26,20 @@ const MIN_INSERTS_HEIGHT_1: usize = NODE_CAPACITY + 1;
 // It's not the minimum size: removing an element from such a tree does not always reduce height.
 const MIN_INSERTS_HEIGHT_2: usize = NODE_CAPACITY + (NODE_CAPACITY + 1) * NODE_CAPACITY + 1;
 
+// Gather all references from a mutable iterator and make sure Miri notices if
+// using them is dangerous.
+fn test_all_refs<'a, T: 'a>(dummy: &mut T, iter: impl Iterator<Item = &'a mut T>) {
+    // Gather all those references.
+    let mut refs: Vec<&mut T> = iter.collect();
+    // Use them all. Twice, to be sure we got all interleavings.
+    for r in refs.iter_mut() {
+        mem::swap(dummy, r);
+    }
+    for r in refs {
+        mem::swap(dummy, r);
+    }
+}
+
 #[test]
 fn test_basic_large() {
     let mut map = BTreeMap::new();
@@ -268,7 +283,14 @@ fn test_iter_mut_mutation() {
 }
 
 #[test]
+#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
 fn test_values_mut() {
+    let mut a: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect();
+    test_all_refs(&mut 13, a.values_mut());
+}
+
+#[test]
+fn test_values_mut_mutation() {
     let mut a = BTreeMap::new();
     a.insert(1, String::from("hello"));
     a.insert(2, String::from("goodbye"));
@@ -282,6 +304,36 @@ fn test_values_mut() {
 }
 
 #[test]
+#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
+fn test_iter_entering_root_twice() {
+    let mut map: BTreeMap<_, _> = (0..2).map(|i| (i, i)).collect();
+    let mut it = map.iter_mut();
+    let front = it.next().unwrap();
+    let back = it.next_back().unwrap();
+    assert_eq!(front, (&0, &mut 0));
+    assert_eq!(back, (&1, &mut 1));
+    *front.1 = 24;
+    *back.1 = 42;
+    assert_eq!(front, (&0, &mut 24));
+    assert_eq!(back, (&1, &mut 42));
+}
+
+#[test]
+#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
+fn test_iter_descending_to_same_node_twice() {
+    let mut map: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)).collect();
+    let mut it = map.iter_mut();
+    // Descend into first child.
+    let front = it.next().unwrap();
+    // Descend into first child again, after running through second child.
+    while it.next_back().is_some() {}
+    // Check immutable access.
+    assert_eq!(front, (&0, &mut 0));
+    // Perform mutable access.
+    *front.1 = 42;
+}
+
+#[test]
 fn test_iter_mixed() {
     // Miri is too slow
     let size = if cfg!(miri) { 200 } else { 10000 };
@@ -835,10 +887,8 @@ mod test_drain_filter {
             }
         }
 
-        let mut map = BTreeMap::new();
-        map.insert(0, D);
-        map.insert(4, D);
-        map.insert(8, D);
+        // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
+        let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
 
         catch_unwind(move || {
             drop(map.drain_filter(|i, _| {
@@ -846,7 +896,7 @@ mod test_drain_filter {
                 true
             }))
         })
-        .ok();
+        .unwrap_err();
 
         assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
         assert_eq!(DROPS.load(Ordering::SeqCst), 3);
@@ -864,10 +914,8 @@ mod test_drain_filter {
             }
         }
 
-        let mut map = BTreeMap::new();
-        map.insert(0, D);
-        map.insert(4, D);
-        map.insert(8, D);
+        // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
+        let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
 
         catch_unwind(AssertUnwindSafe(|| {
             drop(map.drain_filter(|i, _| {
@@ -878,7 +926,45 @@ mod test_drain_filter {
                 }
             }))
         }))
-        .ok();
+        .unwrap_err();
+
+        assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
+        assert_eq!(DROPS.load(Ordering::SeqCst), 1);
+        assert_eq!(map.len(), 2);
+        assert_eq!(map.first_entry().unwrap().key(), &4);
+        assert_eq!(map.last_entry().unwrap().key(), &8);
+    }
+
+    // Same as above, but attempt to use the iterator again after the panic in the predicate
+    #[test]
+    fn pred_panic_reuse() {
+        static PREDS: AtomicUsize = AtomicUsize::new(0);
+        static DROPS: AtomicUsize = AtomicUsize::new(0);
+
+        struct D;
+        impl Drop for D {
+            fn drop(&mut self) {
+                DROPS.fetch_add(1, Ordering::SeqCst);
+            }
+        }
+
+        // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
+        let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
+
+        {
+            let mut it = map.drain_filter(|i, _| {
+                PREDS.fetch_add(1usize << i, Ordering::SeqCst);
+                match i {
+                    0 => true,
+                    _ => panic!(),
+                }
+            });
+            catch_unwind(AssertUnwindSafe(|| while it.next().is_some() {})).unwrap_err();
+            // Iterator behaviour after a panic is explicitly unspecified,
+            // so this is just the current implementation:
+            let result = catch_unwind(AssertUnwindSafe(|| it.next()));
+            assert!(matches!(result, Ok(None)));
+        }
 
         assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
         assert_eq!(DROPS.load(Ordering::SeqCst), 1);
@@ -1283,6 +1369,34 @@ fn test_split_off_empty_left() {
     assert!(right.into_iter().eq(data));
 }
 
+// In a tree with 3 levels, if all but a part of the first leaf node is split off,
+// make sure fix_top eliminates both top levels.
+#[test]
+fn test_split_off_tiny_left_height_2() {
+    let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
+    let mut left: BTreeMap<_, _> = pairs.clone().collect();
+    let right = left.split_off(&1);
+    assert_eq!(left.len(), 1);
+    assert_eq!(right.len(), MIN_INSERTS_HEIGHT_2 - 1);
+    assert_eq!(*left.first_key_value().unwrap().0, 0);
+    assert_eq!(*right.first_key_value().unwrap().0, 1);
+}
+
+// In a tree with 3 levels, if only part of the last leaf node is split off,
+// make sure fix_top eliminates both top levels.
+#[test]
+fn test_split_off_tiny_right_height_2() {
+    let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
+    let last = MIN_INSERTS_HEIGHT_2 - 1;
+    let mut left: BTreeMap<_, _> = pairs.clone().collect();
+    assert_eq!(*left.last_key_value().unwrap().0, last);
+    let right = left.split_off(&last);
+    assert_eq!(left.len(), MIN_INSERTS_HEIGHT_2 - 1);
+    assert_eq!(right.len(), 1);
+    assert_eq!(*left.last_key_value().unwrap().0, last - 1);
+    assert_eq!(*right.last_key_value().unwrap().0, last);
+}
+
 #[test]
 fn test_split_off_large_random_sorted() {
     // Miri is too slow
@@ -1319,7 +1433,7 @@ fn test_into_iter_drop_leak_height_0() {
     map.insert("d", D);
     map.insert("e", D);
 
-    catch_unwind(move || drop(map.into_iter())).ok();
+    catch_unwind(move || drop(map.into_iter())).unwrap_err();
 
     assert_eq!(DROPS.load(Ordering::SeqCst), 5);
 }
@@ -1343,7 +1457,7 @@ fn test_into_iter_drop_leak_height_1() {
         DROPS.store(0, Ordering::SeqCst);
         PANIC_POINT.store(panic_point, Ordering::SeqCst);
         let map: BTreeMap<_, _> = (0..size).map(|i| (i, D)).collect();
-        catch_unwind(move || drop(map.into_iter())).ok();
+        catch_unwind(move || drop(map.into_iter())).unwrap_err();
         assert_eq!(DROPS.load(Ordering::SeqCst), size);
     }
 }