Rollup merge of #111238 - workingjubilee:fix-btree-cursormut-peek-prev, r=Amanieu

btree_map: `Cursor{,Mut}::peek_prev` must agree

Our `Cursor::peek_prev` and `CursorMut::peek_prev` must agree on how to behave when they are called on the "null element". This will fix rust-lang#111228.

r? `@Amanieu`

2 files changed, 21 insertions, 2 deletions

diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs
index efbbc1c2331..2daef82d6f1 100644
--- a/library/alloc/src/collections/btree/map.rs
+++ b/library/alloc/src/collections/btree/map.rs
@@ -3079,8 +3079,8 @@ impl<'a, K, V, A> CursorMut<'a, K, V, A> {
                 unsafe { self.root.reborrow() }
                     .as_mut()?
                     .borrow_mut()
-                    .first_leaf_edge()
-                    .next_kv()
+                    .last_leaf_edge()
+                    .next_back_kv()
                     .ok()?
                     .into_kv_valmut()
             }
diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs
index da00d83bdbb..7ecffe3eef2 100644
--- a/library/alloc/src/collections/btree/map/tests.rs
+++ b/library/alloc/src/collections/btree/map/tests.rs
@@ -8,6 +8,7 @@ use crate::testing::crash_test::{CrashTestDummy, Panic};
 use crate::testing::ord_chaos::{Cyclic3, Governed, Governor};
 use crate::testing::rng::DeterministicRng;
 use crate::vec::Vec;
+use core::assert_matches::assert_matches;
 use std::cmp::Ordering;
 use std::iter;
 use std::mem;
@@ -2448,3 +2449,21 @@ fn test_cursor_mut_insert_after_4() {
     let mut cur = map.upper_bound_mut(Bound::Included(&2));
     cur.insert_after(4, 'd');
 }
+
+#[test]
+fn cursor_peek_prev_agrees_with_cursor_mut() {
+    let mut map = BTreeMap::from([(1, 1), (2, 2), (3, 3)]);
+
+    let cursor = map.lower_bound(Bound::Excluded(&3));
+    assert!(cursor.key().is_none());
+
+    let prev = cursor.peek_prev();
+    assert_matches!(prev, Some((&3, _)));
+
+    // Shadow names so the two parts of this test match.
+    let mut cursor = map.lower_bound_mut(Bound::Excluded(&3));
+    assert!(cursor.key().is_none());
+
+    let prev = cursor.peek_prev();
+    assert_matches!(prev, Some((&3, _)));
+}