Add UnorderedKeyError

2 files changed, 43 insertions, 31 deletions

diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs
index f0a1561f650..b585e2082f1 100644
--- a/library/alloc/src/collections/btree/map.rs
+++ b/library/alloc/src/collections/btree/map.rs
@@ -1,6 +1,7 @@
 use crate::vec::Vec;
 use core::borrow::Borrow;
 use core::cmp::Ordering;
+use core::error::Error;
 use core::fmt::{self, Debug};
 use core::hash::{Hash, Hasher};
 use core::iter::FusedIterator;
@@ -2750,7 +2751,7 @@ impl<K: Debug, V: Debug> Debug for Cursor<'_, K, V> {
 /// references is tied to its own lifetime, instead of just the underlying map. This means
 /// cursors cannot yield multiple elements at once.
 ///
-/// Cursors always point to a gao between two elements in the map, and can
+/// Cursors always point to a gap between two elements in the map, and can
 /// operate on the two immediately adjacent elements.
 ///
 /// A `CursorMut` is created with the [`BTreeMap::lower_bound_mut`] and [`BTreeMap::upper_bound_mut`]
@@ -2780,7 +2781,7 @@ impl<K: Debug, V: Debug, A> Debug for CursorMut<'_, K, V, A> {
 /// references is tied to its own lifetime, instead of just the underlying map. This means
 /// cursors cannot yield multiple elements at once.
 ///
-/// Cursors always point to a gao between two elements in the map, and can
+/// Cursors always point to a gap between two elements in the map, and can
 /// operate on the two immediately adjacent elements.
 ///
 /// A `CursorMutKey` is created from a [`CursorMut`] with the
@@ -3142,20 +3143,21 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMutKey<'a, K, V, A> {
     /// - the given key compares greater than or equal to the next element (if
     ///   any).
     #[unstable(feature = "btree_cursors", issue = "107540")]
-    pub fn insert_after(&mut self, key: K, value: V) {
+    pub fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> {
         if let Some((prev, _)) = self.peek_prev() {
             if &key <= prev {
-                panic!("key must be ordered above the previous element");
+                return Err(UnorderedKeyError {});
             }
         }
         if let Some((next, _)) = self.peek_next() {
             if &key >= next {
-                panic!("key must be ordered below the next element");
+                return Err(UnorderedKeyError {});
             }
         }
         unsafe {
             self.insert_after_unchecked(key, value);
         }
+        Ok(())
     }
 
     /// Inserts a new element into the `BTreeMap` in the gap that the
@@ -3172,20 +3174,21 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMutKey<'a, K, V, A> {
     /// - the given key compares less than or equal to the previous element (if
     ///   any).
     #[unstable(feature = "btree_cursors", issue = "107540")]
-    pub fn insert_before(&mut self, key: K, value: V) {
+    pub fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> {
         if let Some((prev, _)) = self.peek_prev() {
             if &key <= prev {
-                panic!("key must be ordered above the previous element");
+                return Err(UnorderedKeyError {});
             }
         }
         if let Some((next, _)) = self.peek_next() {
             if &key >= next {
-                panic!("key must be ordered below the next element");
+                return Err(UnorderedKeyError {});
             }
         }
         unsafe {
             self.insert_before_unchecked(key, value);
         }
+        Ok(())
     }
 
     /// Removes the next element from the `BTreeMap`.
@@ -3286,7 +3289,7 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> {
     /// - the given key compares greater than or equal to the next element (if
     ///   any).
     #[unstable(feature = "btree_cursors", issue = "107540")]
-    pub fn insert_after(&mut self, key: K, value: V) {
+    pub fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> {
         self.inner.insert_after(key, value)
     }
 
@@ -3304,7 +3307,7 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> {
     /// - the given key compares less than or equal to the previous element (if
     ///   any).
     #[unstable(feature = "btree_cursors", issue = "107540")]
-    pub fn insert_before(&mut self, key: K, value: V) {
+    pub fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> {
         self.inner.insert_before(key, value)
     }
 
@@ -3327,5 +3330,22 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> {
     }
 }
 
+/// Error type returned by [`CursorMut::insert_before`] and
+/// [`CursorMut::insert_after`] if the key being inserted is not properly
+/// ordered with regards to adjacent keys.
+#[derive(Clone, PartialEq, Eq, Debug)]
+#[unstable(feature = "btree_cursors", issue = "107540")]
+pub struct UnorderedKeyError {}
+
+#[unstable(feature = "btree_cursors", issue = "107540")]
+impl fmt::Display for UnorderedKeyError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "key is not properly ordered relative to neighbors")
+    }
+}
+
+#[unstable(feature = "btree_cursors", issue = "107540")]
+impl Error for UnorderedKeyError {}
+
 #[cfg(test)]
 mod tests;
diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs
index eea00cc5d67..c1e5df51204 100644
--- a/library/alloc/src/collections/btree/map/tests.rs
+++ b/library/alloc/src/collections/btree/map/tests.rs
@@ -2378,14 +2378,14 @@ fn test_cursor_mut() {
     assert_eq!(cur.peek_next(), Some((&5, &mut 'e')));
     assert_eq!(cur.peek_prev(), Some((&3, &mut 'c')));
 
-    cur.insert_before(4, 'd');
+    cur.insert_before(4, 'd').unwrap();
     assert_eq!(cur.peek_next(), Some((&5, &mut 'e')));
     assert_eq!(cur.peek_prev(), Some((&4, &mut 'd')));
 
     assert_eq!(cur.next(), Some((&5, &mut 'e')));
     assert_eq!(cur.peek_next(), None);
     assert_eq!(cur.peek_prev(), Some((&5, &mut 'e')));
-    cur.insert_before(6, 'f');
+    cur.insert_before(6, 'f').unwrap();
     assert_eq!(cur.peek_next(), None);
     assert_eq!(cur.peek_prev(), Some((&6, &mut 'f')));
     assert_eq!(cur.remove_prev(), Some((6, 'f')));
@@ -2409,14 +2409,14 @@ fn test_cursor_mut_key() {
     assert_eq!(cur.peek_next(), Some((&mut 5, &mut 'e')));
     assert_eq!(cur.peek_prev(), Some((&mut 3, &mut 'c')));
 
-    cur.insert_before(4, 'd');
+    cur.insert_before(4, 'd').unwrap();
     assert_eq!(cur.peek_next(), Some((&mut 5, &mut 'e')));
     assert_eq!(cur.peek_prev(), Some((&mut 4, &mut 'd')));
 
     assert_eq!(cur.next(), Some((&mut 5, &mut 'e')));
     assert_eq!(cur.peek_next(), None);
     assert_eq!(cur.peek_prev(), Some((&mut 5, &mut 'e')));
-    cur.insert_before(6, 'f');
+    cur.insert_before(6, 'f').unwrap();
     assert_eq!(cur.peek_next(), None);
     assert_eq!(cur.peek_prev(), Some((&mut 6, &mut 'f')));
     assert_eq!(cur.remove_prev(), Some((6, 'f')));
@@ -2439,74 +2439,66 @@ fn test_cursor_empty() {
     let mut cur = map.lower_bound_mut(Bound::Excluded(&3));
     assert_eq!(cur.peek_next(), None);
     assert_eq!(cur.peek_prev(), None);
-    cur.insert_after(0, 0);
+    cur.insert_after(0, 0).unwrap();
     assert_eq!(cur.peek_next(), Some((&0, &mut 0)));
     assert_eq!(cur.peek_prev(), None);
     assert_eq!(map, BTreeMap::from([(0, 0)]));
 }
 
-#[should_panic(expected = "key must be ordered above the previous element")]
 #[test]
 fn test_cursor_mut_insert_before_1() {
     let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
     let mut cur = map.upper_bound_mut(Bound::Included(&2));
-    cur.insert_before(0, 'd');
+    cur.insert_before(0, 'd').unwrap_err();
 }
 
-#[should_panic(expected = "key must be ordered above the previous element")]
 #[test]
 fn test_cursor_mut_insert_before_2() {
     let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
     let mut cur = map.upper_bound_mut(Bound::Included(&2));
-    cur.insert_before(1, 'd');
+    cur.insert_before(1, 'd').unwrap_err();
 }
 
-#[should_panic(expected = "key must be ordered above the previous element")]
 #[test]
 fn test_cursor_mut_insert_before_3() {
     let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
     let mut cur = map.upper_bound_mut(Bound::Included(&2));
-    cur.insert_before(2, 'd');
+    cur.insert_before(2, 'd').unwrap_err();
 }
 
-#[should_panic(expected = "key must be ordered below the next element")]
 #[test]
 fn test_cursor_mut_insert_before_4() {
     let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
     let mut cur = map.upper_bound_mut(Bound::Included(&2));
-    cur.insert_before(3, 'd');
+    cur.insert_before(3, 'd').unwrap_err();
 }
 
-#[should_panic(expected = "key must be ordered above the previous element")]
 #[test]
 fn test_cursor_mut_insert_after_1() {
     let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
     let mut cur = map.upper_bound_mut(Bound::Included(&2));
-    cur.insert_after(1, 'd');
+    cur.insert_after(1, 'd').unwrap_err();
 }
 
-#[should_panic(expected = "key must be ordered above the previous element")]
 #[test]
 fn test_cursor_mut_insert_after_2() {
     let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
     let mut cur = map.upper_bound_mut(Bound::Included(&2));
-    cur.insert_after(2, 'd');
+    cur.insert_after(2, 'd').unwrap_err();
 }
 
-#[should_panic(expected = "key must be ordered below the next element")]
 #[test]
 fn test_cursor_mut_insert_after_3() {
     let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
     let mut cur = map.upper_bound_mut(Bound::Included(&2));
-    cur.insert_after(3, 'd');
+    cur.insert_after(3, 'd').unwrap_err();
 }
 
-#[should_panic(expected = "key must be ordered below the next element")]
 #[test]
 fn test_cursor_mut_insert_after_4() {
     let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
     let mut cur = map.upper_bound_mut(Bound::Included(&2));
-    cur.insert_after(4, 'd');
+    cur.insert_after(4, 'd').unwrap_err();
 }
 
 #[test]