From eb70c82d297c010123e88986f176eb827f8a3b7c Mon Sep 17 00:00:00 2001 From: Amanieu d'Antras Date: Thu, 8 Dec 2022 18:31:01 +0000 Subject: BTreeMap: Change internal insert function to return a handle This is a prerequisite for cursor support for `BTreeMap`. --- library/alloc/src/collections/btree/borrow.rs | 22 ++++++ library/alloc/src/collections/btree/map/entry.rs | 40 +++++----- library/alloc/src/collections/btree/node.rs | 94 +++++++++++++++++++----- 3 files changed, 119 insertions(+), 37 deletions(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/collections/btree/borrow.rs b/library/alloc/src/collections/btree/borrow.rs index 016f139a501..000b9bd0fab 100644 --- a/library/alloc/src/collections/btree/borrow.rs +++ b/library/alloc/src/collections/btree/borrow.rs @@ -41,6 +41,28 @@ impl<'a, T> DormantMutRef<'a, T> { // SAFETY: our own safety conditions imply this reference is again unique. unsafe { &mut *self.ptr.as_ptr() } } + + /// Borrows a new mutable reference from the unique borrow initially captured. + /// + /// # Safety + /// + /// The reborrow must have ended, i.e., the reference returned by `new` and + /// all pointers and references derived from it, must not be used anymore. + pub unsafe fn reborrow(&mut self) -> &'a mut T { + // SAFETY: our own safety conditions imply this reference is again unique. + unsafe { &mut *self.ptr.as_ptr() } + } + + /// Borrows a new shared reference from the unique borrow initially captured. + /// + /// # Safety + /// + /// The reborrow must have ended, i.e., the reference returned by `new` and + /// all pointers and references derived from it, must not be used anymore. + pub unsafe fn reborrow_shared(&self) -> &'a T { + // SAFETY: our own safety conditions imply this reference is again unique. + unsafe { &*self.ptr.as_ptr() } + } } #[cfg(test)] diff --git a/library/alloc/src/collections/btree/map/entry.rs b/library/alloc/src/collections/btree/map/entry.rs index 370b58864af..e9366eec9ce 100644 --- a/library/alloc/src/collections/btree/map/entry.rs +++ b/library/alloc/src/collections/btree/map/entry.rs @@ -347,7 +347,7 @@ impl<'a, K: Ord, V, A: Allocator + Clone> VacantEntry<'a, K, V, A> { /// assert_eq!(map["poneyland"], 37); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn insert(self, value: V) -> &'a mut V { + pub fn insert(mut self, value: V) -> &'a mut V { let out_ptr = match self.handle { None => { // SAFETY: There is no tree yet so no reference to it exists. @@ -358,25 +358,27 @@ impl<'a, K: Ord, V, A: Allocator + Clone> VacantEntry<'a, K, V, A> { map.length = 1; val_ptr } - Some(handle) => match handle.insert_recursing(self.key, value, self.alloc.clone()) { - (None, val_ptr) => { - // SAFETY: We have consumed self.handle. - let map = unsafe { self.dormant_map.awaken() }; - map.length += 1; - val_ptr - } - (Some(ins), val_ptr) => { - drop(ins.left); - // SAFETY: We have consumed self.handle and dropped the - // remaining reference to the tree, ins.left. - let map = unsafe { self.dormant_map.awaken() }; - let root = map.root.as_mut().unwrap(); // same as ins.left - root.push_internal_level(self.alloc).push(ins.kv.0, ins.kv.1, ins.right); - map.length += 1; - val_ptr - } - }, + Some(handle) => { + let new_handle = + handle.insert_recursing(self.key, value, self.alloc.clone(), |ins| { + drop(ins.left); + // SAFETY: Pushing a new root node doesn't invalidate + // handles to existing nodes. + let map = unsafe { self.dormant_map.reborrow() }; + let root = map.root.as_mut().unwrap(); // same as ins.left + root.push_internal_level(self.alloc).push(ins.kv.0, ins.kv.1, ins.right) + }); + + // Get the pointer to the value + let val_ptr = new_handle.into_val_mut(); + + // SAFETY: We have consumed self.handle. + let map = unsafe { self.dormant_map.awaken() }; + map.length += 1; + val_ptr + } }; + // Now that we have finished growing the tree using borrowed references, // dereference the pointer to a part of it, that we picked up along the way. unsafe { &mut *out_ptr } diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs index 6912466448f..76b304e756f 100644 --- a/library/alloc/src/collections/btree/node.rs +++ b/library/alloc/src/collections/btree/node.rs @@ -442,6 +442,24 @@ impl<'a, K, V, Type> NodeRef, K, V, Type> { // SAFETY: we have exclusive access to the entire node. unsafe { &mut *ptr } } + + /// Returns a dormant copy of this node with its lifetime erased which can + /// be reawakened later. + pub fn dormant(&self) -> NodeRef { + NodeRef { height: self.height, node: self.node, _marker: PhantomData } + } +} + +impl NodeRef { + /// Revert to the unique borrow initially captured. + /// + /// # Safety + /// + /// The reborrow must have ended, i.e., the reference returned by `new` and + /// all pointers and references derived from it, must not be used anymore. + pub unsafe fn awaken<'a>(self) -> NodeRef, K, V, Type> { + NodeRef { height: self.height, node: self.node, _marker: PhantomData } + } } impl NodeRef { @@ -798,6 +816,25 @@ impl<'a, K, V, NodeType, HandleType> Handle, K, V, NodeT // We can't use Handle::new_kv or Handle::new_edge because we don't know our type Handle { node: unsafe { self.node.reborrow_mut() }, idx: self.idx, _marker: PhantomData } } + + /// Returns a dormant copy of this handle which can be reawakened later. + /// + /// See [`DormantMutRef`] for more details. + pub fn dormant(&self) -> Handle, HandleType> { + Handle { node: self.node.dormant(), idx: self.idx, _marker: PhantomData } + } +} + +impl Handle, HandleType> { + /// Revert to the unique borrow initially captured. + /// + /// # Safety + /// + /// The reborrow must have ended, i.e., the reference returned by `new` and + /// all pointers and references derived from it, must not be used anymore. + pub unsafe fn awaken<'a>(self) -> Handle, K, V, NodeType>, HandleType> { + Handle { node: unsafe { self.node.awaken() }, idx: self.idx, _marker: PhantomData } + } } impl Handle, marker::Edge> { @@ -851,9 +888,11 @@ impl<'a, K: 'a, V: 'a> Handle, K, V, marker::Leaf>, mark /// Inserts a new key-value pair between the key-value pairs to the right and left of /// this edge. This method assumes that there is enough space in the node for the new /// pair to fit. - /// - /// The returned pointer points to the inserted value. - fn insert_fit(&mut self, key: K, val: V) -> *mut V { + unsafe fn insert_fit( + mut self, + key: K, + val: V, + ) -> Handle, K, V, marker::Leaf>, marker::KV> { debug_assert!(self.node.len() < CAPACITY); let new_len = self.node.len() + 1; @@ -862,7 +901,7 @@ impl<'a, K: 'a, V: 'a> Handle, K, V, marker::Leaf>, mark slice_insert(self.node.val_area_mut(..new_len), self.idx, val); *self.node.len_mut() = new_len as u16; - self.node.val_area_mut(self.idx).assume_init_mut() + Handle::new_kv(self.node, self.idx) } } } @@ -871,21 +910,26 @@ impl<'a, K: 'a, V: 'a> Handle, K, V, marker::Leaf>, mark /// Inserts a new key-value pair between the key-value pairs to the right and left of /// this edge. This method splits the node if there isn't enough room. /// - /// The returned pointer points to the inserted value. + /// Returns a dormant handle to the inserted node which can be reawakened + /// once splitting is complete. fn insert( - mut self, + self, key: K, val: V, alloc: A, - ) -> (Option>, *mut V) { + ) -> ( + Option>, + Handle, marker::KV>, + ) { if self.node.len() < CAPACITY { - let val_ptr = self.insert_fit(key, val); - (None, val_ptr) + // SAFETY: There is enough space in the node for insertion. + let handle = unsafe { self.insert_fit(key, val) }; + (None, handle.dormant()) } else { let (middle_kv_idx, insertion) = splitpoint(self.idx); let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) }; let mut result = middle.split(alloc); - let mut insertion_edge = match insertion { + let insertion_edge = match insertion { LeftOrRight::Left(insert_idx) => unsafe { Handle::new_edge(result.left.reborrow_mut(), insert_idx) }, @@ -893,8 +937,10 @@ impl<'a, K: 'a, V: 'a> Handle, K, V, marker::Leaf>, mark Handle::new_edge(result.right.borrow_mut(), insert_idx) }, }; - let val_ptr = insertion_edge.insert_fit(key, val); - (Some(result), val_ptr) + // SAFETY: We just split the node, so there is enough space for + // insertion. + let handle = unsafe { insertion_edge.insert_fit(key, val).dormant() }; + (Some(result), handle) } } } @@ -976,21 +1022,31 @@ impl<'a, K: 'a, V: 'a> Handle, K, V, marker::Leaf>, mark key: K, value: V, alloc: A, - ) -> (Option>, *mut V) { - let (mut split, val_ptr) = match self.insert(key, value, alloc.clone()) { - (None, val_ptr) => return (None, val_ptr), - (Some(split), val_ptr) => (split.forget_node_type(), val_ptr), + split_root: impl FnOnce(SplitResult<'a, K, V, marker::LeafOrInternal>), + ) -> Handle, K, V, marker::Leaf>, marker::KV> { + let (mut split, handle) = match self.insert(key, value, alloc.clone()) { + // SAFETY: we have finished splitting and can now re-awaken the + // handle to the inserted element. + (None, handle) => return unsafe { handle.awaken() }, + (Some(split), handle) => (split.forget_node_type(), handle), }; loop { split = match split.left.ascend() { Ok(parent) => { match parent.insert(split.kv.0, split.kv.1, split.right, alloc.clone()) { - None => return (None, val_ptr), + // SAFETY: we have finished splitting and can now re-awaken the + // handle to the inserted element. + None => return unsafe { handle.awaken() }, Some(split) => split.forget_node_type(), } } - Err(root) => return (Some(SplitResult { left: root, ..split }), val_ptr), + Err(root) => { + split_root(SplitResult { left: root, ..split }); + // SAFETY: we have finished splitting and can now re-awaken the + // handle to the inserted element. + return unsafe { handle.awaken() }; + } }; } } @@ -1667,6 +1723,7 @@ pub mod marker { pub enum Owned {} pub enum Dying {} + pub enum DormantMut {} pub struct Immut<'a>(PhantomData<&'a ()>); pub struct Mut<'a>(PhantomData<&'a mut ()>); pub struct ValMut<'a>(PhantomData<&'a mut ()>); @@ -1688,6 +1745,7 @@ pub mod marker { impl<'a> BorrowType for Immut<'a> {} impl<'a> BorrowType for Mut<'a> {} impl<'a> BorrowType for ValMut<'a> {} + impl BorrowType for DormantMut {} pub enum KV {} pub enum Edge {} -- cgit 1.4.1-3-g733a5 From 36831b3ccbc4104c6b559cbd341dbd7ee6251ec7 Mon Sep 17 00:00:00 2001 From: Amanieu d'Antras Date: Thu, 8 Dec 2022 18:32:43 +0000 Subject: BTreeMap: Add Cursor and CursorMut --- library/alloc/src/collections/btree/map.rs | 730 ++++++++++++++++++++++- library/alloc/src/collections/btree/map/tests.rs | 49 ++ library/alloc/src/collections/btree/navigate.rs | 55 +- library/alloc/src/collections/btree/node.rs | 10 +- 4 files changed, 839 insertions(+), 5 deletions(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index 1d9c4460ec9..386cd1a1657 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -6,7 +6,7 @@ use core::hash::{Hash, Hasher}; use core::iter::{FromIterator, FusedIterator}; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop}; -use core::ops::{Index, RangeBounds}; +use core::ops::{Bound, Index, RangeBounds}; use core::ptr; use crate::alloc::{Allocator, Global}; @@ -15,7 +15,7 @@ use super::borrow::DormantMutRef; use super::dedup_sorted_iter::DedupSortedIter; use super::navigate::{LazyLeafRange, LeafRange}; use super::node::{self, marker, ForceResult::*, Handle, NodeRef, Root}; -use super::search::SearchResult::*; +use super::search::{SearchBound, SearchResult::*}; use super::set_val::SetValZST; mod entry; @@ -2422,6 +2422,732 @@ impl BTreeMap { pub const fn is_empty(&self) -> bool { self.len() == 0 } + + /// Returns a [`Cursor`] pointing at the first element that is above the + /// given bound. + /// + /// If no such element exists then a cursor pointing at the "ghost" + /// non-element is returned. + /// + /// Passing [`Bound::Unbounded`] will return a cursor pointing at the first + /// element of the map. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(btree_cursors)] + /// + /// use std::collections::BTreeMap; + /// use std::ops::Bound; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "a"); + /// a.insert(2, "b"); + /// a.insert(3, "c"); + /// a.insert(4, "c"); + /// let cursor = a.lower_bound(Bound::Excluded(&2)); + /// assert_eq!(cursor.key(), Some(&3)); + /// ``` + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn lower_bound(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> + where + K: Borrow + Ord, + Q: Ord, + { + let root_node = match self.root.as_ref() { + None => return Cursor { current: None, root: None }, + Some(root) => root.reborrow(), + }; + let edge = root_node.lower_bound(SearchBound::from_range(bound)); + Cursor { current: edge.next_kv().ok(), root: self.root.as_ref() } + } + + /// Returns a [`CursorMut`] pointing at the first element that is above the + /// given bound. + /// + /// If no such element exists then a cursor pointing at the "ghost" + /// non-element is returned. + /// + /// Passing [`Bound::Unbounded`] will return a cursor pointing at the first + /// element of the map. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(btree_cursors)] + /// + /// use std::collections::BTreeMap; + /// use std::ops::Bound; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "a"); + /// a.insert(2, "b"); + /// a.insert(3, "c"); + /// a.insert(4, "c"); + /// let cursor = a.lower_bound_mut(Bound::Excluded(&2)); + /// assert_eq!(cursor.key(), Some(&3)); + /// ``` + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn lower_bound_mut(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A> + where + K: Borrow + Ord, + Q: Ord, + { + let (root, dormant_root) = DormantMutRef::new(&mut self.root); + let root_node = match root.as_mut() { + None => { + return CursorMut { + current: None, + root: dormant_root, + length: &mut self.length, + alloc: &mut *self.alloc, + }; + } + Some(root) => root.borrow_mut(), + }; + let edge = root_node.lower_bound(SearchBound::from_range(bound)); + CursorMut { + current: edge.next_kv().ok(), + root: dormant_root, + length: &mut self.length, + alloc: &mut *self.alloc, + } + } + + /// Returns a [`Cursor`] pointing at the last element that is below the + /// given bound. + /// + /// If no such element exists then a cursor pointing at the "ghost" + /// non-element is returned. + /// + /// Passing [`Bound::Unbounded`] will return a cursor pointing at the last + /// element of the map. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(btree_cursors)] + /// + /// use std::collections::BTreeMap; + /// use std::ops::Bound; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "a"); + /// a.insert(2, "b"); + /// a.insert(3, "c"); + /// a.insert(4, "c"); + /// let cursor = a.upper_bound(Bound::Excluded(&3)); + /// assert_eq!(cursor.key(), Some(&2)); + /// ``` + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn upper_bound(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> + where + K: Borrow + Ord, + Q: Ord, + { + let root_node = match self.root.as_ref() { + None => return Cursor { current: None, root: None }, + Some(root) => root.reborrow(), + }; + let edge = root_node.upper_bound(SearchBound::from_range(bound)); + Cursor { current: edge.next_back_kv().ok(), root: self.root.as_ref() } + } + + /// Returns a [`CursorMut`] pointing at the last element that is below the + /// given bound. + /// + /// If no such element exists then a cursor pointing at the "ghost" + /// non-element is returned. + /// + /// Passing [`Bound::Unbounded`] will return a cursor pointing at the last + /// element of the map. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(btree_cursors)] + /// + /// use std::collections::BTreeMap; + /// use std::ops::Bound; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "a"); + /// a.insert(2, "b"); + /// a.insert(3, "c"); + /// a.insert(4, "c"); + /// let cursor = a.upper_bound_mut(Bound::Excluded(&3)); + /// assert_eq!(cursor.key(), Some(&2)); + /// ``` + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn upper_bound_mut(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A> + where + K: Borrow + Ord, + Q: Ord, + { + let (root, dormant_root) = DormantMutRef::new(&mut self.root); + let root_node = match root.as_mut() { + None => { + return CursorMut { + current: None, + root: dormant_root, + length: &mut self.length, + alloc: &mut *self.alloc, + }; + } + Some(root) => root.borrow_mut(), + }; + let edge = root_node.upper_bound(SearchBound::from_range(bound)); + CursorMut { + current: edge.next_back_kv().ok(), + root: dormant_root, + length: &mut self.length, + alloc: &mut *self.alloc, + } + } +} + +/// A cursor over a `BTreeMap`. +/// +/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth. +/// +/// Cursors always point to an element in the tree, and index in a logically circular way. +/// To accommodate this, there is a "ghost" non-element that yields `None` between the last and +/// first elements of the tree. +/// +/// A `Cursor` is created with the [`BTreeMap::lower_bound`] and [`BTreeMap::upper_bound`] methods. +#[unstable(feature = "btree_cursors", issue = "107540")] +pub struct Cursor<'a, K: 'a, V: 'a> { + current: Option, K, V, marker::LeafOrInternal>, marker::KV>>, + root: Option<&'a node::Root>, +} + +#[unstable(feature = "btree_cursors", issue = "107540")] +impl Clone for Cursor<'_, K, V> { + fn clone(&self) -> Self { + let Cursor { current, root } = *self; + Cursor { current, root } + } +} + +#[unstable(feature = "btree_cursors", issue = "107540")] +impl Debug for Cursor<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("Cursor").field(&self.key_value()).finish() + } +} + +/// A cursor over a `BTreeMap` with editing operations. +/// +/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can +/// safely mutate the tree during iteration. This is because the lifetime of its yielded +/// references is tied to its own lifetime, instead of just the underlying tree. This means +/// cursors cannot yield multiple elements at once. +/// +/// Cursors always point to an element in the tree, and index in a logically circular way. +/// To accommodate this, there is a "ghost" non-element that yields `None` between the last and +/// first elements of the tree. +/// +/// A `Cursor` is created with the [`BTreeMap::lower_bound_mut`] and [`BTreeMap::upper_bound_mut`] +/// methods. +#[unstable(feature = "btree_cursors", issue = "107540")] +pub struct CursorMut< + 'a, + K: 'a, + V: 'a, + #[unstable(feature = "allocator_api", issue = "32838")] A = Global, +> { + current: Option, K, V, marker::LeafOrInternal>, marker::KV>>, + root: DormantMutRef<'a, Option>>, + length: &'a mut usize, + alloc: &'a mut A, +} + +#[unstable(feature = "btree_cursors", issue = "107540")] +impl Debug for CursorMut<'_, K, V, A> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("CursorMut").field(&self.key_value()).finish() + } +} + +impl<'a, K, V> Cursor<'a, K, V> { + /// Moves the cursor to the next element of the `BTreeMap`. + /// + /// If the cursor is pointing to the "ghost" non-element then this will move it to + /// the first element of the `BTreeMap`. If it is pointing to the last + /// element of the `BTreeMap` then this will move it to the "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn move_next(&mut self) { + match self.current.take() { + None => { + self.current = self.root.and_then(|root| { + root.reborrow().first_leaf_edge().forget_node_type().right_kv().ok() + }); + } + Some(current) => { + self.current = current.next_leaf_edge().next_kv().ok(); + } + } + } + + /// Moves the cursor to the previous element of the `BTreeMap`. + /// + /// If the cursor is pointing to the "ghost" non-element then this will move it to + /// the last element of the `BTreeMap`. If it is pointing to the first + /// element of the `BTreeMap` then this will move it to the "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn move_prev(&mut self) { + match self.current.take() { + None => { + self.current = self.root.and_then(|root| { + root.reborrow().last_leaf_edge().forget_node_type().left_kv().ok() + }); + } + Some(current) => { + self.current = current.next_back_leaf_edge().next_back_kv().ok(); + } + } + } + + /// Returns a reference to the key of the element that the cursor is + /// currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn key(&self) -> Option<&'a K> { + self.current.as_ref().map(|current| current.into_kv().0) + } + + /// Returns a reference to the value of the element that the cursor is + /// currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn value(&self) -> Option<&'a V> { + self.current.as_ref().map(|current| current.into_kv().1) + } + + /// Returns a reference to the key and value of the element that the cursor + /// is currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn key_value(&self) -> Option<(&'a K, &'a V)> { + self.current.as_ref().map(|current| current.into_kv()) + } + + /// Returns a reference to the next element. + /// + /// If the cursor is pointing to the "ghost" non-element then this returns + /// the first element of the `BTreeMap`. If it is pointing to the last + /// element of the `BTreeMap` then this returns `None`. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn peek_next(&self) -> Option<(&'a K, &'a V)> { + let mut next = self.clone(); + next.move_next(); + next.current.as_ref().map(|current| current.into_kv()) + } + + /// Returns a reference to the previous element. + /// + /// If the cursor is pointing to the "ghost" non-element then this returns + /// the last element of the `BTreeMap`. If it is pointing to the first + /// element of the `BTreeMap` then this returns `None`. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn peek_prev(&self) -> Option<(&'a K, &'a V)> { + let mut prev = self.clone(); + prev.move_prev(); + prev.current.as_ref().map(|current| current.into_kv()) + } +} + +impl<'a, K, V, A> CursorMut<'a, K, V, A> { + /// Moves the cursor to the next element of the `BTreeMap`. + /// + /// If the cursor is pointing to the "ghost" non-element then this will move it to + /// the first element of the `BTreeMap`. If it is pointing to the last + /// element of the `BTreeMap` then this will move it to the "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn move_next(&mut self) { + match self.current.take() { + None => { + // SAFETY: The previous borrow of root has ended. + self.current = unsafe { self.root.reborrow() }.as_mut().and_then(|root| { + root.borrow_mut().first_leaf_edge().forget_node_type().right_kv().ok() + }); + } + Some(current) => { + self.current = current.next_leaf_edge().next_kv().ok(); + } + } + } + + /// Moves the cursor to the previous element of the `BTreeMap`. + /// + /// If the cursor is pointing to the "ghost" non-element then this will move it to + /// the last element of the `BTreeMap`. If it is pointing to the first + /// element of the `BTreeMap` then this will move it to the "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn move_prev(&mut self) { + match self.current.take() { + None => { + // SAFETY: The previous borrow of root has ended. + self.current = unsafe { self.root.reborrow() }.as_mut().and_then(|root| { + root.borrow_mut().last_leaf_edge().forget_node_type().left_kv().ok() + }); + } + Some(current) => { + self.current = current.next_back_leaf_edge().next_back_kv().ok(); + } + } + } + + /// Returns a reference to the key of the element that the cursor is + /// currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn key(&self) -> Option<&K> { + self.current.as_ref().map(|current| current.reborrow().into_kv().0) + } + + /// Returns a reference to the value of the element that the cursor is + /// currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn value(&self) -> Option<&V> { + self.current.as_ref().map(|current| current.reborrow().into_kv().1) + } + + /// Returns a reference to the key and value of the element that the cursor + /// is currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn key_value(&self) -> Option<(&K, &V)> { + self.current.as_ref().map(|current| current.reborrow().into_kv()) + } + + /// Returns a mutable reference to the value of the element that the cursor + /// is currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn value_mut(&mut self) -> Option<&mut V> { + self.current.as_mut().map(|current| current.kv_mut().1) + } + + /// Returns a reference to the key and mutable reference to the value of the + /// element that the cursor is currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn key_value_mut(&mut self) -> Option<(&K, &mut V)> { + self.current.as_mut().map(|current| { + let (k, v) = current.kv_mut(); + (&*k, v) + }) + } + + /// Returns a mutable reference to the of the element that the cursor is + /// currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + /// + /// # Safety + /// + /// This can be used to modify the key, but you must ensure that the + /// `BTreeMap` invariants are maintained. Specifically: + /// + /// * The key must remain unique within the tree. + /// * The key must remain in sorted order with regards to other elements in + /// the tree. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub unsafe fn key_mut_unchecked(&mut self) -> Option<&mut K> { + self.current.as_mut().map(|current| current.kv_mut().0) + } + + /// Returns a reference to the key and value of the next element. + /// + /// If the cursor is pointing to the "ghost" non-element then this returns + /// the first element of the `BTreeMap`. If it is pointing to the last + /// element of the `BTreeMap` then this returns `None`. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn peek_next(&mut self) -> Option<(&K, &mut V)> { + let (k, v) = match self.current { + None => { + // SAFETY: The previous borrow of root has ended. + unsafe { self.root.reborrow() } + .as_mut()? + .borrow_mut() + .first_leaf_edge() + .next_kv() + .ok()? + .into_kv_valmut() + } + // SAFETY: We're not using this to mutate the tree. + Some(ref mut current) => { + unsafe { current.reborrow_mut() }.next_leaf_edge().next_kv().ok()?.into_kv_valmut() + } + }; + Some((k, v)) + } + + /// Returns a reference to the key and value of the previous element. + /// + /// If the cursor is pointing to the "ghost" non-element then this returns + /// the last element of the `BTreeMap`. If it is pointing to the first + /// element of the `BTreeMap` then this returns `None`. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn peek_prev(&mut self) -> Option<(&K, &mut V)> { + let (k, v) = match self.current.as_mut() { + None => { + // SAFETY: The previous borrow of root has ended. + unsafe { self.root.reborrow() } + .as_mut()? + .borrow_mut() + .first_leaf_edge() + .next_kv() + .ok()? + .into_kv_valmut() + } + Some(current) => { + // SAFETY: We're not using this to mutate the tree. + unsafe { current.reborrow_mut() } + .next_back_leaf_edge() + .next_back_kv() + .ok()? + .into_kv_valmut() + } + }; + Some((k, v)) + } + + /// Returns a read-only cursor pointing to the current element. + /// + /// The lifetime of the returned `Cursor` is bound to that of the + /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the + /// `CursorMut` is frozen for the lifetime of the `Cursor`. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn as_cursor(&self) -> Cursor<'_, K, V> { + Cursor { + // SAFETY: The tree is immutable while the cursor exists. + root: unsafe { self.root.reborrow_shared().as_ref() }, + current: self.current.as_ref().map(|current| current.reborrow()), + } + } +} + +// Now the tree editing operations +impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { + /// Inserts a new element into the `BTreeMap` after the current one. + /// + /// If the cursor is pointing at the "ghost" non-element then the new element is + /// inserted at the front of the `BTreeMap`. + /// + /// # Safety + /// + /// You must ensure that the `BTreeMap` invariants are maintained. + /// Specifically: + /// + /// * The key of the newly inserted element must be unique in the tree. + /// * All keys in the tree must remain in sorted order. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub unsafe fn insert_after_unchecked(&mut self, key: K, value: V) { + let edge = match self.current.take() { + None => { + // SAFETY: We have no other reference to the tree. + match unsafe { self.root.reborrow() } { + root @ None => { + // Tree is empty, allocate a new root. + let mut node = NodeRef::new_leaf(self.alloc.clone()); + node.borrow_mut().push(key, value); + *root = Some(node.forget_type()); + *self.length += 1; + return; + } + Some(root) => root.borrow_mut().first_leaf_edge(), + } + } + Some(current) => current.next_leaf_edge(), + }; + + let handle = edge.insert_recursing(key, value, self.alloc.clone(), |ins| { + drop(ins.left); + // SAFETY: The handle to the newly inserted value is always on a + // leaf node, so adding a new root node doesn't invalidate it. + let root = unsafe { self.root.reborrow().as_mut().unwrap() }; + root.push_internal_level(self.alloc.clone()).push(ins.kv.0, ins.kv.1, ins.right) + }); + self.current = handle.left_edge().next_back_kv().ok(); + *self.length += 1; + } + + /// Inserts a new element into the `BTreeMap` before the current one. + /// + /// If the cursor is pointing at the "ghost" non-element then the new element is + /// inserted at the end of the `BTreeMap`. + /// + /// # Safety + /// + /// You must ensure that the `BTreeMap` invariants are maintained. + /// Specifically: + /// + /// * The key of the newly inserted element must be unique in the tree. + /// * All keys in the tree must remain in sorted order. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub unsafe fn insert_before_unchecked(&mut self, key: K, value: V) { + let edge = match self.current.take() { + None => { + // SAFETY: We have no other reference to the tree. + match unsafe { self.root.reborrow() } { + root @ None => { + // Tree is empty, allocate a new root. + let mut node = NodeRef::new_leaf(self.alloc.clone()); + node.borrow_mut().push(key, value); + *root = Some(node.forget_type()); + *self.length += 1; + return; + } + Some(root) => root.borrow_mut().last_leaf_edge(), + } + } + Some(current) => current.next_back_leaf_edge(), + }; + + let handle = edge.insert_recursing(key, value, self.alloc.clone(), |ins| { + drop(ins.left); + // SAFETY: The handle to the newly inserted value is always on a + // leaf node, so adding a new root node doesn't invalidate it. + let root = unsafe { self.root.reborrow().as_mut().unwrap() }; + root.push_internal_level(self.alloc.clone()).push(ins.kv.0, ins.kv.1, ins.right) + }); + self.current = handle.right_edge().next_kv().ok(); + *self.length += 1; + } + + /// Inserts a new element into the `BTreeMap` after the current one. + /// + /// If the cursor is pointing at the "ghost" non-element then the new element is + /// inserted at the front of the `BTreeMap`. + /// + /// # Panics + /// + /// This function panics if: + /// - the given key compares less than or equal to the current element (if + /// any). + /// - 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) { + if let Some(current) = self.key() { + if &key <= current { + panic!("key must be ordered above the current element"); + } + } + if let Some((next, _)) = self.peek_prev() { + if &key >= next { + panic!("key must be ordered below the next element"); + } + } + unsafe { + self.insert_after_unchecked(key, value); + } + } + + /// Inserts a new element into the `BTreeMap` before the current one. + /// + /// If the cursor is pointing at the "ghost" non-element then the new element is + /// inserted at the end of the `BTreeMap`. + /// + /// # Panics + /// + /// This function panics if: + /// - the given key compares greater than or equal to the current element + /// (if any). + /// - 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) { + if let Some(current) = self.key() { + if &key >= current { + panic!("key must be ordered below the current element"); + } + } + if let Some((prev, _)) = self.peek_prev() { + if &key <= prev { + panic!("key must be ordered above the previous element"); + } + } + unsafe { + self.insert_before_unchecked(key, value); + } + } + + /// Removes the current element from the `BTreeMap`. + /// + /// The element that was removed is returned, and the cursor is + /// moved to point to the next element in the `BTreeMap`. + /// + /// If the cursor is currently pointing to the "ghost" non-element then no element + /// is removed and `None` is returned. The cursor is not moved in this case. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn remove_current(&mut self) -> Option<(K, V)> { + let current = self.current.take()?; + let mut emptied_internal_root = false; + let (kv, pos) = + current.remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone()); + self.current = pos.next_kv().ok(); + *self.length -= 1; + if emptied_internal_root { + // SAFETY: This is safe since current does not point within the now + // empty root node. + let root = unsafe { self.root.reborrow().as_mut().unwrap() }; + root.pop_internal_level(self.alloc.clone()); + } + Some(kv) + } + + /// Removes the current element from the `BTreeMap`. + /// + /// The element that was removed is returned, and the cursor is + /// moved to point to the previous element in the `BTreeMap`. + /// + /// If the cursor is currently pointing to the "ghost" non-element then no element + /// is removed and `None` is returned. The cursor is not moved in this case. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn remove_current_and_move_back(&mut self) -> Option<(K, V)> { + let current = self.current.take()?; + let mut emptied_internal_root = false; + let (kv, pos) = + current.remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone()); + self.current = pos.next_back_kv().ok(); + *self.length -= 1; + if emptied_internal_root { + // SAFETY: This is safe since current does not point within the now + // empty root node. + let root = unsafe { self.root.reborrow().as_mut().unwrap() }; + root.pop_internal_level(self.alloc.clone()); + } + Some(kv) + } } #[cfg(test)] diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs index 700b1463bfd..76c2f27b466 100644 --- a/library/alloc/src/collections/btree/map/tests.rs +++ b/library/alloc/src/collections/btree/map/tests.rs @@ -2336,3 +2336,52 @@ fn from_array() { let unordered_duplicates = BTreeMap::from([(3, 4), (1, 2), (1, 2)]); assert_eq!(map, unordered_duplicates); } + +#[test] +fn test_cursor() { + let map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + + let mut cur = map.lower_bound(Bound::Unbounded); + assert_eq!(cur.key(), Some(&1)); + cur.move_next(); + assert_eq!(cur.key(), Some(&2)); + assert_eq!(cur.peek_next(), Some((&3, &'c'))); + cur.move_prev(); + assert_eq!(cur.key(), Some(&1)); + assert_eq!(cur.peek_prev(), None); + + let mut cur = map.upper_bound(Bound::Excluded(&1)); + assert_eq!(cur.key(), None); + cur.move_next(); + assert_eq!(cur.key(), Some(&1)); + cur.move_prev(); + assert_eq!(cur.key(), None); + assert_eq!(cur.peek_prev(), Some((&3, &'c'))); +} + +#[test] +fn test_cursor_mut() { + let mut map = BTreeMap::from([(1, 'a'), (3, 'c'), (5, 'e')]); + let mut cur = map.lower_bound_mut(Bound::Excluded(&3)); + assert_eq!(cur.key(), Some(&5)); + cur.insert_before(4, 'd'); + assert_eq!(cur.key(), Some(&5)); + assert_eq!(cur.peek_prev(), Some((&4, &mut 'd'))); + cur.move_next(); + assert_eq!(cur.key(), None); + cur.insert_before(6, 'f'); + assert_eq!(cur.key(), None); + assert_eq!(cur.remove_current(), None); + assert_eq!(cur.key(), None); + cur.insert_after(0, '?'); + assert_eq!(cur.key(), None); + assert_eq!(map, BTreeMap::from([(0, '?'), (1, 'a'), (3, 'c'), (4, 'd'), (5, 'e'), (6, 'f')])); + + let mut cur = map.upper_bound_mut(Bound::Included(&5)); + assert_eq!(cur.key(), Some(&5)); + assert_eq!(cur.remove_current(), Some((5, 'e'))); + assert_eq!(cur.key(), Some(&6)); + assert_eq!(cur.remove_current_and_move_back(), Some((6, 'f'))); + assert_eq!(cur.key(), Some(&4)); + assert_eq!(map, BTreeMap::from([(0, '?'), (1, 'a'), (3, 'c'), (4, 'd')])); +} diff --git a/library/alloc/src/collections/btree/navigate.rs b/library/alloc/src/collections/btree/navigate.rs index 1e33c1e64d6..b890717e50b 100644 --- a/library/alloc/src/collections/btree/navigate.rs +++ b/library/alloc/src/collections/btree/navigate.rs @@ -4,6 +4,7 @@ use core::ops::RangeBounds; use core::ptr; use super::node::{marker, ForceResult::*, Handle, NodeRef}; +use super::search::SearchBound; use crate::alloc::Allocator; // `front` and `back` are always both `None` or both `Some`. @@ -386,7 +387,7 @@ impl /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV /// on the left side, which is either in the same leaf node or in an ancestor node. /// If the leaf edge is the first one in the tree, returns [`Result::Err`] with the root node. - fn next_back_kv( + pub fn next_back_kv( self, ) -> Result< Handle, marker::KV>, @@ -707,7 +708,9 @@ impl } /// Returns the leaf edge closest to a KV for backward navigation. - fn next_back_leaf_edge(self) -> Handle, marker::Edge> { + pub fn next_back_leaf_edge( + self, + ) -> Handle, marker::Edge> { match self.force() { Leaf(leaf_kv) => leaf_kv.left_edge(), Internal(internal_kv) => { @@ -717,3 +720,51 @@ impl } } } + +impl NodeRef { + /// Returns the leaf edge corresponding to the first point at which the + /// given bound is true. + pub fn lower_bound( + self, + mut bound: SearchBound<&Q>, + ) -> Handle, marker::Edge> + where + Q: Ord, + K: Borrow, + { + let mut node = self; + loop { + let (edge, new_bound) = node.find_lower_bound_edge(bound); + match edge.force() { + Leaf(edge) => return edge, + Internal(edge) => { + node = edge.descend(); + bound = new_bound; + } + } + } + } + + /// Returns the leaf edge corresponding to the last point at which the + /// given bound is true. + pub fn upper_bound( + self, + mut bound: SearchBound<&Q>, + ) -> Handle, marker::Edge> + where + Q: Ord, + K: Borrow, + { + let mut node = self; + loop { + let (edge, new_bound) = node.find_upper_bound_edge(bound); + match edge.force() { + Leaf(edge) => return edge, + Internal(edge) => { + node = edge.descend(); + bound = new_bound; + } + } + } + } +} diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs index 76b304e756f..3233a575ecf 100644 --- a/library/alloc/src/collections/btree/node.rs +++ b/library/alloc/src/collections/btree/node.rs @@ -819,7 +819,7 @@ impl<'a, K, V, NodeType, HandleType> Handle, K, V, NodeT /// Returns a dormant copy of this handle which can be reawakened later. /// - /// See [`DormantMutRef`] for more details. + /// See `DormantMutRef` for more details. pub fn dormant(&self) -> Handle, HandleType> { Handle { node: self.node.dormant(), idx: self.idx, _marker: PhantomData } } @@ -1099,6 +1099,14 @@ impl<'a, K: 'a, V: 'a, NodeType> Handle, K, V, NodeType> let leaf = self.node.into_leaf_mut(); unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() } } + + pub fn into_kv_valmut(self) -> (&'a K, &'a mut V) { + debug_assert!(self.idx < self.node.len()); + let leaf = self.node.into_leaf_mut(); + let k = unsafe { leaf.keys.get_unchecked(self.idx).assume_init_ref() }; + let v = unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() }; + (k, v) + } } impl<'a, K, V, NodeType> Handle, K, V, NodeType>, marker::KV> { -- cgit 1.4.1-3-g733a5 From 83b05ef0ee05307143e2d04db401d6085f4759b9 Mon Sep 17 00:00:00 2001 From: Trevor Gross Date: Sat, 28 Jan 2023 17:06:30 -0500 Subject: Stabilize feature 'cstr_from_bytes_until_nul' --- library/alloc/src/lib.rs | 1 - library/core/src/error.rs | 2 +- library/core/src/ffi/c_str.rs | 10 ++++------ library/std/src/lib.rs | 1 - src/tools/miri/tests/pass-dep/shims/pthreads.rs | 1 - 5 files changed, 5 insertions(+), 10 deletions(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/lib.rs b/library/alloc/src/lib.rs index 76dabfb429d..e9cc3875f68 100644 --- a/library/alloc/src/lib.rs +++ b/library/alloc/src/lib.rs @@ -116,7 +116,6 @@ #![feature(const_eval_select)] #![feature(const_pin)] #![feature(const_waker)] -#![feature(cstr_from_bytes_until_nul)] #![feature(dispatch_from_dyn)] #![feature(error_generic_member_access)] #![feature(error_in_core)] diff --git a/library/core/src/error.rs b/library/core/src/error.rs index d2fac23ff18..e11a5e99184 100644 --- a/library/core/src/error.rs +++ b/library/core/src/error.rs @@ -505,7 +505,7 @@ impl Error for crate::ffi::FromBytesWithNulError { } } -#[unstable(feature = "cstr_from_bytes_until_nul", issue = "95027")] +#[stable(feature = "cstr_from_bytes_until_nul", since = "CURRENT_RUSTC_VERSION")] impl Error for crate::ffi::FromBytesUntilNulError {} #[unstable(feature = "get_many_mut", issue = "104642")] diff --git a/library/core/src/ffi/c_str.rs b/library/core/src/ffi/c_str.rs index 15dd9ea7e80..288bac67f75 100644 --- a/library/core/src/ffi/c_str.rs +++ b/library/core/src/ffi/c_str.rs @@ -150,10 +150,10 @@ impl FromBytesWithNulError { /// This error is created by the [`CStr::from_bytes_until_nul`] method. /// #[derive(Clone, PartialEq, Eq, Debug)] -#[unstable(feature = "cstr_from_bytes_until_nul", issue = "95027")] +#[stable(feature = "cstr_from_bytes_until_nul", since = "CURRENT_RUSTC_VERSION")] pub struct FromBytesUntilNulError(()); -#[unstable(feature = "cstr_from_bytes_until_nul", issue = "95027")] +#[stable(feature = "cstr_from_bytes_until_nul", since = "CURRENT_RUSTC_VERSION")] impl fmt::Display for FromBytesUntilNulError { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "data provided does not contain a nul") @@ -306,8 +306,6 @@ impl CStr { /// /// # Examples /// ``` - /// #![feature(cstr_from_bytes_until_nul)] - /// /// use std::ffi::CStr; /// /// let mut buffer = [0u8; 16]; @@ -322,8 +320,8 @@ impl CStr { /// assert_eq!(c_str.to_str().unwrap(), "AAAAAAAA"); /// ``` /// - #[unstable(feature = "cstr_from_bytes_until_nul", issue = "95027")] - #[rustc_const_unstable(feature = "cstr_from_bytes_until_nul", issue = "95027")] + #[stable(feature = "cstr_from_bytes_until_nul", since = "CURRENT_RUSTC_VERSION")] + #[rustc_const_unstable(feature = "const_cstr_from_bytes_until_nul", issue = "95027")] pub const fn from_bytes_until_nul(bytes: &[u8]) -> Result<&CStr, FromBytesUntilNulError> { let nul_pos = memchr::memchr(0, bytes); match nul_pos { diff --git a/library/std/src/lib.rs b/library/std/src/lib.rs index 762f7a7c9a1..cd9f74820ae 100644 --- a/library/std/src/lib.rs +++ b/library/std/src/lib.rs @@ -278,7 +278,6 @@ #![feature(char_error_internals)] #![feature(char_internals)] #![feature(core_intrinsics)] -#![feature(cstr_from_bytes_until_nul)] #![feature(cstr_internals)] #![feature(duration_constants)] #![feature(error_generic_member_access)] diff --git a/src/tools/miri/tests/pass-dep/shims/pthreads.rs b/src/tools/miri/tests/pass-dep/shims/pthreads.rs index 09dd92564d3..80b8d67401a 100644 --- a/src/tools/miri/tests/pass-dep/shims/pthreads.rs +++ b/src/tools/miri/tests/pass-dep/shims/pthreads.rs @@ -1,5 +1,4 @@ //@ignore-target-windows: No libc on Windows -#![feature(cstr_from_bytes_until_nul)] use std::ffi::{CStr, CString}; use std::thread; -- cgit 1.4.1-3-g733a5 From 4f36673e152170951f8b01bcdd6c2da953a65ccc Mon Sep 17 00:00:00 2001 From: Danilo Bargen Date: Tue, 7 Feb 2023 21:32:11 +0100 Subject: Docs: Fix format of headings in String::reserve --- library/alloc/src/string.rs | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/string.rs b/library/alloc/src/string.rs index ca182c8109e..75659188515 100644 --- a/library/alloc/src/string.rs +++ b/library/alloc/src/string.rs @@ -928,12 +928,12 @@ impl String { /// Copies elements from `src` range to the end of the string. /// - /// ## Panics + /// # Panics /// /// Panics if the starting point or end point do not lie on a [`char`] /// boundary, or if they're out of bounds. /// - /// ## Examples + /// # Examples /// /// ``` /// #![feature(string_extend_from_within)] -- cgit 1.4.1-3-g733a5 From 77c85e9cba0c3f8b185c63f013cca1350b2e5492 Mon Sep 17 00:00:00 2001 From: Tobias Bucher Date: Tue, 10 Jan 2023 15:59:47 +0100 Subject: Remove a couple of `#[doc(hidden)] pub fn` and their `#[feature]` gates --- library/alloc/src/ffi/c_str.rs | 8 +-- library/core/src/array/mod.rs | 17 +------ library/core/src/char/convert.rs | 28 +++++------ library/core/src/error.rs | 16 ------ library/core/src/ffi/c_str.rs | 11 +++-- library/core/src/num/dec2flt/mod.rs | 17 +++---- library/core/src/num/error.rs | 57 +++++++--------------- library/core/src/num/mod.rs | 12 ----- library/std/src/lib.rs | 4 -- .../src/library-features/char-error-internals.md | 5 -- .../src/library-features/int-error-internals.md | 5 -- 11 files changed, 48 insertions(+), 132 deletions(-) delete mode 100644 src/doc/unstable-book/src/library-features/char-error-internals.md delete mode 100644 src/doc/unstable-book/src/library-features/int-error-internals.md (limited to 'library/alloc/src') diff --git a/library/alloc/src/ffi/c_str.rs b/library/alloc/src/ffi/c_str.rs index 11bd4c4dc1b..f99395c72aa 100644 --- a/library/alloc/src/ffi/c_str.rs +++ b/library/alloc/src/ffi/c_str.rs @@ -991,12 +991,6 @@ impl IntoStringError { pub fn utf8_error(&self) -> Utf8Error { self.error } - - #[doc(hidden)] - #[unstable(feature = "cstr_internals", issue = "none")] - pub fn __source(&self) -> &Utf8Error { - &self.error - } } impl IntoStringError { @@ -1141,6 +1135,6 @@ impl core::error::Error for IntoStringError { } fn source(&self) -> Option<&(dyn core::error::Error + 'static)> { - Some(self.__source()) + Some(&self.error) } } diff --git a/library/core/src/array/mod.rs b/library/core/src/array/mod.rs index 2825e0bbb43..5decd7d5a65 100644 --- a/library/core/src/array/mod.rs +++ b/library/core/src/array/mod.rs @@ -131,7 +131,8 @@ pub struct TryFromSliceError(()); impl fmt::Display for TryFromSliceError { #[inline] fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - fmt::Display::fmt(self.__description(), f) + #[allow(deprecated)] + self.description().fmt(f) } } @@ -139,20 +140,6 @@ impl fmt::Display for TryFromSliceError { impl Error for TryFromSliceError { #[allow(deprecated)] fn description(&self) -> &str { - self.__description() - } -} - -impl TryFromSliceError { - #[unstable( - feature = "array_error_internals", - reason = "available through Error trait and this method should not \ - be exposed publicly", - issue = "none" - )] - #[inline] - #[doc(hidden)] - pub fn __description(&self) -> &str { "could not convert slice to array" } } diff --git a/library/core/src/char/convert.rs b/library/core/src/char/convert.rs index f1a51a550f5..136bbcb8b21 100644 --- a/library/core/src/char/convert.rs +++ b/library/core/src/char/convert.rs @@ -2,6 +2,7 @@ use crate::char::TryFromCharError; use crate::convert::TryFrom; +use crate::error::Error; use crate::fmt; use crate::mem::transmute; use crate::str::FromStr; @@ -150,14 +151,16 @@ pub struct ParseCharError { kind: CharErrorKind, } -impl ParseCharError { - #[unstable( - feature = "char_error_internals", - reason = "this method should not be available publicly", - issue = "none" - )] - #[doc(hidden)] - pub fn __description(&self) -> &str { +#[derive(Copy, Clone, Debug, PartialEq, Eq)] +enum CharErrorKind { + EmptyString, + TooManyChars, +} + +#[stable(feature = "char_from_str", since = "1.20.0")] +impl Error for ParseCharError { + #[allow(deprecated)] + fn description(&self) -> &str { match self.kind { CharErrorKind::EmptyString => "cannot parse char from empty string", CharErrorKind::TooManyChars => "too many characters in string", @@ -165,16 +168,11 @@ impl ParseCharError { } } -#[derive(Copy, Clone, Debug, PartialEq, Eq)] -enum CharErrorKind { - EmptyString, - TooManyChars, -} - #[stable(feature = "char_from_str", since = "1.20.0")] impl fmt::Display for ParseCharError { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - self.__description().fmt(f) + #[allow(deprecated)] + self.description().fmt(f) } } diff --git a/library/core/src/error.rs b/library/core/src/error.rs index e11a5e99184..571bc4bcfd1 100644 --- a/library/core/src/error.rs +++ b/library/core/src/error.rs @@ -486,25 +486,9 @@ impl Error for crate::char::CharTryFromError { } } -#[stable(feature = "char_from_str", since = "1.20.0")] -impl Error for crate::char::ParseCharError { - #[allow(deprecated)] - fn description(&self) -> &str { - self.__description() - } -} - #[stable(feature = "duration_checked_float", since = "1.66.0")] impl Error for crate::time::TryFromFloatSecsError {} -#[stable(feature = "frombyteswithnulerror_impls", since = "1.17.0")] -impl Error for crate::ffi::FromBytesWithNulError { - #[allow(deprecated)] - fn description(&self) -> &str { - self.__description() - } -} - #[stable(feature = "cstr_from_bytes_until_nul", since = "CURRENT_RUSTC_VERSION")] impl Error for crate::ffi::FromBytesUntilNulError {} diff --git a/library/core/src/ffi/c_str.rs b/library/core/src/ffi/c_str.rs index 82e5fa75ded..cd00fd0daf9 100644 --- a/library/core/src/ffi/c_str.rs +++ b/library/core/src/ffi/c_str.rs @@ -1,4 +1,5 @@ use crate::cmp::Ordering; +use crate::error::Error; use crate::ffi::c_char; use crate::fmt; use crate::intrinsics; @@ -129,10 +130,12 @@ impl FromBytesWithNulError { const fn not_nul_terminated() -> FromBytesWithNulError { FromBytesWithNulError { kind: FromBytesWithNulErrorKind::NotNulTerminated } } +} - #[doc(hidden)] - #[unstable(feature = "cstr_internals", issue = "none")] - pub fn __description(&self) -> &str { +#[stable(feature = "frombyteswithnulerror_impls", since = "1.17.0")] +impl Error for FromBytesWithNulError { + #[allow(deprecated)] + fn description(&self) -> &str { match self.kind { FromBytesWithNulErrorKind::InteriorNul(..) => { "data provided contains an interior nul byte" @@ -180,7 +183,7 @@ impl Default for &CStr { impl fmt::Display for FromBytesWithNulError { #[allow(deprecated, deprecated_in_future)] fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.write_str(self.__description())?; + f.write_str(self.description())?; if let FromBytesWithNulErrorKind::InteriorNul(pos) = self.kind { write!(f, " at byte pos {pos}")?; } diff --git a/library/core/src/num/dec2flt/mod.rs b/library/core/src/num/dec2flt/mod.rs index a888ced49b3..f8d493e8b62 100644 --- a/library/core/src/num/dec2flt/mod.rs +++ b/library/core/src/num/dec2flt/mod.rs @@ -75,6 +75,7 @@ issue = "none" )] +use crate::error::Error; use crate::fmt; use crate::str::FromStr; @@ -182,15 +183,10 @@ enum FloatErrorKind { Invalid, } -impl ParseFloatError { - #[unstable( - feature = "int_error_internals", - reason = "available through Error trait and this method should \ - not be exposed publicly", - issue = "none" - )] - #[doc(hidden)] - pub fn __description(&self) -> &str { +#[stable(feature = "rust1", since = "1.0.0")] +impl Error for ParseFloatError { + #[allow(deprecated)] + fn description(&self) -> &str { match self.kind { FloatErrorKind::Empty => "cannot parse float from empty string", FloatErrorKind::Invalid => "invalid float literal", @@ -201,7 +197,8 @@ impl ParseFloatError { #[stable(feature = "rust1", since = "1.0.0")] impl fmt::Display for ParseFloatError { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - self.__description().fmt(f) + #[allow(deprecated)] + self.description().fmt(f) } } diff --git a/library/core/src/num/error.rs b/library/core/src/num/error.rs index 768dd87816d..1bae4efe7d9 100644 --- a/library/core/src/num/error.rs +++ b/library/core/src/num/error.rs @@ -9,23 +9,19 @@ use crate::fmt; #[derive(Debug, Copy, Clone, PartialEq, Eq)] pub struct TryFromIntError(pub(crate) ()); -impl TryFromIntError { - #[unstable( - feature = "int_error_internals", - reason = "available through Error trait and this method should \ - not be exposed publicly", - issue = "none" - )] - #[doc(hidden)] - pub fn __description(&self) -> &str { - "out of range integral type conversion attempted" +#[stable(feature = "try_from", since = "1.34.0")] +impl fmt::Display for TryFromIntError { + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { + #[allow(deprecated)] + self.description().fmt(fmt) } } #[stable(feature = "try_from", since = "1.34.0")] -impl fmt::Display for TryFromIntError { - fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { - self.__description().fmt(fmt) +impl Error for TryFromIntError { + #[allow(deprecated)] + fn description(&self) -> &str { + "out of range integral type conversion attempted" } } @@ -121,28 +117,13 @@ impl ParseIntError { pub fn kind(&self) -> &IntErrorKind { &self.kind } - #[unstable( - feature = "int_error_internals", - reason = "available through Error trait and this method should \ - not be exposed publicly", - issue = "none" - )] - #[doc(hidden)] - pub fn __description(&self) -> &str { - match self.kind { - IntErrorKind::Empty => "cannot parse integer from empty string", - IntErrorKind::InvalidDigit => "invalid digit found in string", - IntErrorKind::PosOverflow => "number too large to fit in target type", - IntErrorKind::NegOverflow => "number too small to fit in target type", - IntErrorKind::Zero => "number would be zero for non-zero type", - } - } } #[stable(feature = "rust1", since = "1.0.0")] impl fmt::Display for ParseIntError { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - self.__description().fmt(f) + #[allow(deprecated)] + self.description().fmt(f) } } @@ -150,14 +131,12 @@ impl fmt::Display for ParseIntError { impl Error for ParseIntError { #[allow(deprecated)] fn description(&self) -> &str { - self.__description() - } -} - -#[stable(feature = "try_from", since = "1.34.0")] -impl Error for TryFromIntError { - #[allow(deprecated)] - fn description(&self) -> &str { - self.__description() + match self.kind { + IntErrorKind::Empty => "cannot parse integer from empty string", + IntErrorKind::InvalidDigit => "invalid digit found in string", + IntErrorKind::PosOverflow => "number too large to fit in target type", + IntErrorKind::NegOverflow => "number too small to fit in target type", + IntErrorKind::Zero => "number would be zero for non-zero type", + } } } diff --git a/library/core/src/num/mod.rs b/library/core/src/num/mod.rs index ac7f579ebb5..0497416745f 100644 --- a/library/core/src/num/mod.rs +++ b/library/core/src/num/mod.rs @@ -9,9 +9,6 @@ use crate::mem; use crate::ops::{Add, Mul, Sub}; use crate::str::FromStr; -#[cfg(not(no_fp_fmt_parse))] -use crate::error::Error; - // Used because the `?` operator is not allowed in a const context. macro_rules! try_opt { ($e:expr) => { @@ -61,15 +58,6 @@ pub use wrapping::Wrapping; #[cfg(not(no_fp_fmt_parse))] pub use dec2flt::ParseFloatError; -#[cfg(not(no_fp_fmt_parse))] -#[stable(feature = "rust1", since = "1.0.0")] -impl Error for ParseFloatError { - #[allow(deprecated)] - fn description(&self) -> &str { - self.__description() - } -} - #[stable(feature = "rust1", since = "1.0.0")] pub use error::ParseIntError; diff --git a/library/std/src/lib.rs b/library/std/src/lib.rs index cd9f74820ae..363a2667174 100644 --- a/library/std/src/lib.rs +++ b/library/std/src/lib.rs @@ -273,12 +273,9 @@ #![feature(utf8_chunks)] // // Library features (core): -#![feature(array_error_internals)] #![feature(atomic_mut_ptr)] -#![feature(char_error_internals)] #![feature(char_internals)] #![feature(core_intrinsics)] -#![feature(cstr_internals)] #![feature(duration_constants)] #![feature(error_generic_member_access)] #![feature(error_in_core)] @@ -290,7 +287,6 @@ #![feature(float_next_up_down)] #![feature(hasher_prefixfree_extras)] #![feature(hashmap_internals)] -#![feature(int_error_internals)] #![feature(is_some_and)] #![feature(maybe_uninit_slice)] #![feature(maybe_uninit_write_slice)] diff --git a/src/doc/unstable-book/src/library-features/char-error-internals.md b/src/doc/unstable-book/src/library-features/char-error-internals.md deleted file mode 100644 index 8013b4988e1..00000000000 --- a/src/doc/unstable-book/src/library-features/char-error-internals.md +++ /dev/null @@ -1,5 +0,0 @@ -# `char_error_internals` - -This feature is internal to the Rust compiler and is not intended for general use. - ------------------------- diff --git a/src/doc/unstable-book/src/library-features/int-error-internals.md b/src/doc/unstable-book/src/library-features/int-error-internals.md deleted file mode 100644 index 402e4fa5ef6..00000000000 --- a/src/doc/unstable-book/src/library-features/int-error-internals.md +++ /dev/null @@ -1,5 +0,0 @@ -# `int_error_internals` - -This feature is internal to the Rust compiler and is not intended for general use. - ------------------------- -- cgit 1.4.1-3-g733a5