diff options
Diffstat (limited to 'library/alloc/src')
| -rw-r--r-- | library/alloc/src/collections/binary_heap.rs | 21 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/map/tests.rs | 2 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/navigate.rs | 15 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/node.rs | 332 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/search.rs | 53 | ||||
| -rw-r--r-- | library/alloc/src/fmt.rs | 11 | ||||
| -rw-r--r-- | library/alloc/src/lib.rs | 5 | ||||
| -rw-r--r-- | library/alloc/src/raw_vec.rs | 18 | ||||
| -rw-r--r-- | library/alloc/src/rc.rs | 7 | ||||
| -rw-r--r-- | library/alloc/src/slice.rs | 4 | ||||
| -rw-r--r-- | library/alloc/src/str.rs | 44 | ||||
| -rw-r--r-- | library/alloc/src/sync.rs | 7 | ||||
| -rw-r--r-- | library/alloc/src/vec/into_iter.rs | 27 | ||||
| -rw-r--r-- | library/alloc/src/vec/mod.rs | 23 | ||||
| -rw-r--r-- | library/alloc/src/vec/source_iter_marker.rs | 4 | ||||
| -rw-r--r-- | library/alloc/src/vec/spec_extend.rs | 7 | ||||
| -rw-r--r-- | library/alloc/src/vec/spec_from_iter_nested.rs | 9 |
17 files changed, 338 insertions, 251 deletions
diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap.rs index b5e66d37ab4..bf9f7432fb5 100644 --- a/library/alloc/src/collections/binary_heap.rs +++ b/library/alloc/src/collections/binary_heap.rs @@ -958,6 +958,27 @@ impl<T> BinaryHeap<T> { self.data.shrink_to(min_capacity) } + /// Returns a slice of all values in the underlying vector, in arbitrary + /// order. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(binary_heap_as_slice)] + /// use std::collections::BinaryHeap; + /// use std::io::{self, Write}; + /// + /// let heap = BinaryHeap::from(vec![1, 2, 3, 4, 5, 6, 7]); + /// + /// io::sink().write(heap.as_slice()).unwrap(); + /// ``` + #[unstable(feature = "binary_heap_as_slice", issue = "83659")] + pub fn as_slice(&self) -> &[T] { + self.data.as_slice() + } + /// Consumes the `BinaryHeap` and returns the underlying vector /// in arbitrary order. /// diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs index e636e490e1b..3a74b6a6fa8 100644 --- a/library/alloc/src/collections/btree/map/tests.rs +++ b/library/alloc/src/collections/btree/map/tests.rs @@ -776,7 +776,6 @@ fn test_range_backwards_4() { } #[test] -#[should_panic] fn test_range_finding_ill_order_in_map() { let mut map = BTreeMap::new(); map.insert(Cyclic3::B, ()); @@ -789,7 +788,6 @@ fn test_range_finding_ill_order_in_map() { } #[test] -#[should_panic] fn test_range_finding_ill_order_in_range_ord() { // Has proper order the first time asked, then flips around. struct EvilTwin(i32); diff --git a/library/alloc/src/collections/btree/navigate.rs b/library/alloc/src/collections/btree/navigate.rs index c2c99a9360c..4399feaccc9 100644 --- a/library/alloc/src/collections/btree/navigate.rs +++ b/library/alloc/src/collections/btree/navigate.rs @@ -29,11 +29,18 @@ impl<BorrowType, K, V> LeafRange<BorrowType, K, V> { impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { /// Finds the distinct leaf edges delimiting a specified range in a tree. - /// Returns either a pair of different handles into the same tree or a pair - /// of empty options. + /// + /// If such distinct edges exist, returns them in ascending order, meaning + /// that a non-zero number of calls to `next_unchecked` on the `front` of + /// the result and/or calls to `next_back_unchecked` on the `back` of the + /// result will eventually reach the same edge. + /// + /// If there are no such edges, i.e., if the tree contains no key within + /// the range, returns a pair of empty options. + /// /// # Safety - /// Unless `BorrowType` is `Immut`, do not use the duplicate handles to - /// visit the same KV twice. + /// Unless `BorrowType` is `Immut`, do not use the handles to visit the same + /// KV twice. unsafe fn find_leaf_edges_spanning_range<Q: ?Sized, R>( self, range: R, diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs index 9a7119470f3..f330a1bb3dc 100644 --- a/library/alloc/src/collections/btree/node.rs +++ b/library/alloc/src/collections/btree/node.rs @@ -128,106 +128,6 @@ impl<K, V> InternalNode<K, V> { /// is not a separate type and has no destructor. type BoxedNode<K, V> = NonNull<LeafNode<K, V>>; -/// The root node of an owned tree. -/// -/// Note that this does not have a destructor, and must be cleaned up manually. -pub type Root<K, V> = NodeRef<marker::Owned, K, V, marker::LeafOrInternal>; - -impl<K, V> Root<K, V> { - /// Returns a new owned tree, with its own root node that is initially empty. - pub fn new() -> Self { - NodeRef::new_leaf().forget_type() - } -} - -impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> { - fn new_leaf() -> Self { - Self::from_new_leaf(LeafNode::new()) - } - - fn from_new_leaf(leaf: Box<LeafNode<K, V>>) -> Self { - NodeRef { height: 0, node: NonNull::from(Box::leak(leaf)), _marker: PhantomData } - } -} - -impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> { - fn new_internal(child: Root<K, V>) -> Self { - let mut new_node = unsafe { InternalNode::new() }; - new_node.edges[0].write(child.node); - unsafe { NodeRef::from_new_internal(new_node, child.height + 1) } - } - - /// # Safety - /// `height` must not be zero. - unsafe fn from_new_internal(internal: Box<InternalNode<K, V>>, height: usize) -> Self { - debug_assert!(height > 0); - let node = NonNull::from(Box::leak(internal)).cast(); - let mut this = NodeRef { height, node, _marker: PhantomData }; - this.borrow_mut().correct_all_childrens_parent_links(); - this - } -} - -impl<K, V, Type> NodeRef<marker::Owned, K, V, Type> { - /// Mutably borrows the owned root node. Unlike `reborrow_mut`, this is safe - /// because the return value cannot be used to destroy the root, and there - /// cannot be other references to the tree. - pub fn borrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> { - NodeRef { height: self.height, node: self.node, _marker: PhantomData } - } - - /// Slightly mutably borrows the owned root node. - pub fn borrow_valmut(&mut self) -> NodeRef<marker::ValMut<'_>, K, V, Type> { - NodeRef { height: self.height, node: self.node, _marker: PhantomData } - } - - /// Irreversibly transitions to a reference that permits traversal and offers - /// destructive methods and little else. - pub fn into_dying(self) -> NodeRef<marker::Dying, K, V, Type> { - NodeRef { height: self.height, node: self.node, _marker: PhantomData } - } -} - -impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> { - /// Adds a new internal node with a single edge pointing to the previous root node, - /// make that new node the root node, and return it. This increases the height by 1 - /// and is the opposite of `pop_internal_level`. - pub fn push_internal_level(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> { - super::mem::take_mut(self, |old_root| NodeRef::new_internal(old_root).forget_type()); - - // `self.borrow_mut()`, except that we just forgot we're internal now: - NodeRef { height: self.height, node: self.node, _marker: PhantomData } - } - - /// Removes the internal root node, using its first child as the new root node. - /// As it is intended only to be called when the root node has only one child, - /// no cleanup is done on any of the keys, values and other children. - /// This decreases the height by 1 and is the opposite of `push_internal_level`. - /// - /// Requires exclusive access to the `Root` object but not to the root node; - /// it will not invalidate other handles or references to the root node. - /// - /// Panics if there is no internal level, i.e., if the root node is a leaf. - pub fn pop_internal_level(&mut self) { - assert!(self.height > 0); - - let top = self.node; - - // SAFETY: we asserted to be internal. - let internal_self = unsafe { self.borrow_mut().cast_to_internal_unchecked() }; - // SAFETY: we borrowed `self` exclusively and its borrow type is exclusive. - let internal_node = unsafe { &mut *NodeRef::as_internal_ptr(&internal_self) }; - // SAFETY: the first edge is always initialized. - self.node = unsafe { internal_node.edges[0].assume_init_read() }; - self.height -= 1; - self.clear_parent_link(); - - unsafe { - Global.deallocate(top.cast(), Layout::new::<InternalNode<K, V>>()); - } - } -} - // N.B. `NodeRef` is always covariant in `K` and `V`, even when the `BorrowType` // is `Mut`. This is technically wrong, but cannot result in any unsafety due to // internal use of `NodeRef` because we stay completely generic over `K` and `V`. @@ -292,6 +192,11 @@ pub struct NodeRef<BorrowType, K, V, Type> { _marker: PhantomData<(BorrowType, Type)>, } +/// The root node of an owned tree. +/// +/// Note that this does not have a destructor, and must be cleaned up manually. +pub type Root<K, V> = NodeRef<marker::Owned, K, V, marker::LeafOrInternal>; + impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<marker::Immut<'a>, K, V, Type> {} impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> { fn clone(&self) -> Self { @@ -307,6 +212,34 @@ unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::ValMu unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {} unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Dying, K, V, Type> {} +impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> { + fn new_leaf() -> Self { + Self::from_new_leaf(LeafNode::new()) + } + + fn from_new_leaf(leaf: Box<LeafNode<K, V>>) -> Self { + NodeRef { height: 0, node: NonNull::from(Box::leak(leaf)), _marker: PhantomData } + } +} + +impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> { + fn new_internal(child: Root<K, V>) -> Self { + let mut new_node = unsafe { InternalNode::new() }; + new_node.edges[0].write(child.node); + unsafe { NodeRef::from_new_internal(new_node, child.height + 1) } + } + + /// # Safety + /// `height` must not be zero. + unsafe fn from_new_internal(internal: Box<InternalNode<K, V>>, height: usize) -> Self { + debug_assert!(height > 0); + let node = NonNull::from(Box::leak(internal)).cast(); + let mut this = NodeRef { height, node, _marker: PhantomData }; + this.borrow_mut().correct_all_childrens_parent_links(); + this + } +} + impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> { /// Unpack a node reference that was packed as `NodeRef::parent`. fn from_internal(node: NonNull<InternalNode<K, V>>, height: usize) -> Self { @@ -420,6 +353,19 @@ impl<BorrowType: marker::BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> } } +impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> { + /// Could be a public implementation of PartialEq, but only used in this module. + fn eq(&self, other: &Self) -> bool { + let Self { node, height, _marker } = self; + if node.eq(&other.node) { + debug_assert_eq!(*height, other.height); + true + } else { + false + } + } +} + impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> { /// Exposes the leaf portion of any leaf or internal node in an immutable tree. fn into_leaf(self) -> &'a LeafNode<K, V> { @@ -461,20 +407,6 @@ impl<K, V> NodeRef<marker::Dying, K, V, marker::LeafOrInternal> { } } -impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> { - /// Unsafely asserts to the compiler the static information that this node is a `Leaf`. - unsafe fn cast_to_leaf_unchecked(self) -> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> { - debug_assert!(self.height == 0); - NodeRef { height: self.height, node: self.node, _marker: PhantomData } - } - - /// Unsafely asserts to the compiler the static information that this node is an `Internal`. - unsafe fn cast_to_internal_unchecked(self) -> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { - debug_assert!(self.height > 0); - NodeRef { height: self.height, node: self.node, _marker: PhantomData } - } -} - impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> { /// Temporarily takes out another, mutable reference to the same node. Beware, as /// this method is very dangerous, doubly so since it may not immediately appear @@ -577,6 +509,22 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> { } } +impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { + /// # Safety + /// Every item returned by `range` is a valid edge index for the node. + unsafe fn correct_childrens_parent_links<R: Iterator<Item = usize>>(&mut self, range: R) { + for i in range { + debug_assert!(i <= self.len()); + unsafe { Handle::new_edge(self.reborrow_mut(), i) }.correct_parent_link(); + } + } + + fn correct_all_childrens_parent_links(&mut self) { + let len = self.len(); + unsafe { self.correct_childrens_parent_links(0..=len) }; + } +} + impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> { /// Sets the node's link to its parent edge, /// without invalidating other references to the node. @@ -596,6 +544,71 @@ impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> { } } +impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> { + /// Returns a new owned tree, with its own root node that is initially empty. + pub fn new() -> Self { + NodeRef::new_leaf().forget_type() + } + + /// Adds a new internal node with a single edge pointing to the previous root node, + /// make that new node the root node, and return it. This increases the height by 1 + /// and is the opposite of `pop_internal_level`. + pub fn push_internal_level(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> { + super::mem::take_mut(self, |old_root| NodeRef::new_internal(old_root).forget_type()); + + // `self.borrow_mut()`, except that we just forgot we're internal now: + NodeRef { height: self.height, node: self.node, _marker: PhantomData } + } + + /// Removes the internal root node, using its first child as the new root node. + /// As it is intended only to be called when the root node has only one child, + /// no cleanup is done on any of the keys, values and other children. + /// This decreases the height by 1 and is the opposite of `push_internal_level`. + /// + /// Requires exclusive access to the `Root` object but not to the root node; + /// it will not invalidate other handles or references to the root node. + /// + /// Panics if there is no internal level, i.e., if the root node is a leaf. + pub fn pop_internal_level(&mut self) { + assert!(self.height > 0); + + let top = self.node; + + // SAFETY: we asserted to be internal. + let internal_self = unsafe { self.borrow_mut().cast_to_internal_unchecked() }; + // SAFETY: we borrowed `self` exclusively and its borrow type is exclusive. + let internal_node = unsafe { &mut *NodeRef::as_internal_ptr(&internal_self) }; + // SAFETY: the first edge is always initialized. + self.node = unsafe { internal_node.edges[0].assume_init_read() }; + self.height -= 1; + self.clear_parent_link(); + + unsafe { + Global.deallocate(top.cast(), Layout::new::<InternalNode<K, V>>()); + } + } +} + +impl<K, V, Type> NodeRef<marker::Owned, K, V, Type> { + /// Mutably borrows the owned root node. Unlike `reborrow_mut`, this is safe + /// because the return value cannot be used to destroy the root, and there + /// cannot be other references to the tree. + pub fn borrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> { + NodeRef { height: self.height, node: self.node, _marker: PhantomData } + } + + /// Slightly mutably borrows the owned root node. + pub fn borrow_valmut(&mut self) -> NodeRef<marker::ValMut<'_>, K, V, Type> { + NodeRef { height: self.height, node: self.node, _marker: PhantomData } + } + + /// Irreversibly transitions to a reference that permits traversal and offers + /// destructive methods and little else. + pub fn into_dying(self) -> NodeRef<marker::Dying, K, V, Type> { + NodeRef { height: self.height, node: self.node, _marker: PhantomData } + } +} + impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> { /// Adds a key-value pair to the end of the node. pub fn push(&mut self, key: K, val: V) { @@ -610,22 +623,6 @@ impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> { } } -impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { - /// # Safety - /// Every item returned by `range` is a valid edge index for the node. - unsafe fn correct_childrens_parent_links<R: Iterator<Item = usize>>(&mut self, range: R) { - for i in range { - debug_assert!(i <= self.len()); - unsafe { Handle::new_edge(self.reborrow_mut(), i) }.correct_parent_link(); - } - } - - fn correct_all_childrens_parent_links(&mut self) { - let len = self.len(); - unsafe { self.correct_childrens_parent_links(0..=len) }; - } -} - impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { /// Adds a key-value pair, and an edge to go to the right of that pair, /// to the end of the node. @@ -645,6 +642,20 @@ impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { } } +impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Leaf> { + /// Removes any static information asserting that this node is a `Leaf` node. + pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { + NodeRef { height: self.height, node: self.node, _marker: PhantomData } + } +} + +impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> { + /// Removes any static information asserting that this node is an `Internal` node. + pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { + NodeRef { height: self.height, node: self.node, _marker: PhantomData } + } +} + impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { /// Checks whether a node is an `Internal` node or a `Leaf` node. pub fn force( @@ -669,6 +680,20 @@ impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { } } +impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> { + /// Unsafely asserts to the compiler the static information that this node is a `Leaf`. + unsafe fn cast_to_leaf_unchecked(self) -> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> { + debug_assert!(self.height == 0); + NodeRef { height: self.height, node: self.node, _marker: PhantomData } + } + + /// Unsafely asserts to the compiler the static information that this node is an `Internal`. + unsafe fn cast_to_internal_unchecked(self) -> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { + debug_assert!(self.height > 0); + NodeRef { height: self.height, node: self.node, _marker: PhantomData } + } +} + /// A reference to a specific key-value pair or edge within a node. The `Node` parameter /// must be a `NodeRef`, while the `Type` can either be `KV` (signifying a handle on a key-value /// pair) or `Edge` (signifying a handle on an edge). @@ -722,19 +747,6 @@ impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, mar } } -impl<BorrowType, K, V, NodeType> NodeRef<BorrowType, K, V, NodeType> { - /// Could be a public implementation of PartialEq, but only used in this module. - fn eq(&self, other: &Self) -> bool { - let Self { node, height, _marker } = self; - if node.eq(&other.node) { - debug_assert_eq!(*height, other.height); - true - } else { - false - } - } -} - impl<BorrowType, K, V, NodeType, HandleType> PartialEq for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> { @@ -754,16 +766,6 @@ impl<BorrowType, K, V, NodeType, HandleType> } } -impl<'a, K, V, Type> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, Type> { - /// Unsafely asserts to the compiler the static information that the handle's node is a `Leaf`. - pub unsafe fn cast_to_leaf_unchecked( - self, - ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, Type> { - let node = unsafe { self.node.cast_to_leaf_unchecked() }; - Handle { node, idx: self.idx, _marker: PhantomData } - } -} - impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> { /// Temporarily takes out another, mutable handle on the same location. Beware, as /// this method is very dangerous, doubly so since it may not immediately appear @@ -1466,20 +1468,6 @@ impl<'a, K: 'a, V: 'a> BalancingContext<'a, K, V> { } } -impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Leaf> { - /// Removes any static information asserting that this node is a `Leaf` node. - pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { - NodeRef { height: self.height, node: self.node, _marker: PhantomData } - } -} - -impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> { - /// Removes any static information asserting that this node is an `Internal` node. - pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { - NodeRef { height: self.height, node: self.node, _marker: PhantomData } - } -} - impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> { pub fn forget_node_type( self, @@ -1531,6 +1519,16 @@ impl<BorrowType, K, V, Type> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInte } } +impl<'a, K, V, Type> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, Type> { + /// Unsafely asserts to the compiler the static information that the handle's node is a `Leaf`. + pub unsafe fn cast_to_leaf_unchecked( + self, + ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, Type> { + let node = unsafe { self.node.cast_to_leaf_unchecked() }; + Handle { node, idx: self.idx, _marker: PhantomData } + } +} + impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> { /// Move the suffix after `self` from one node to another one. `right` must be empty. /// The first edge of `right` remains unchanged. diff --git a/library/alloc/src/collections/btree/search.rs b/library/alloc/src/collections/btree/search.rs index 5dc62d4ec70..5651a03c47a 100644 --- a/library/alloc/src/collections/btree/search.rs +++ b/library/alloc/src/collections/btree/search.rs @@ -68,13 +68,16 @@ impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Lea /// of the range is different from the edge matching the upper bound, i.e., /// the nearest node that has at least one key contained in the range. /// - /// If found, returns an `Ok` with that node, the pair of edge indices in it - /// delimiting the range, and the corresponding pair of bounds for - /// continuing the search in the child nodes, in case the node is internal. + /// If found, returns an `Ok` with that node, the strictly ascending pair of + /// edge indices in the node delimiting the range, and the corresponding + /// pair of bounds for continuing the search in the child nodes, in case + /// the node is internal. /// /// If not found, returns an `Err` with the leaf edge matching the entire /// range. /// + /// As a diagnostic service, panics if the range specifies impossible bounds. + /// /// The result is meaningful only if the tree is ordered by key. pub fn search_tree_for_bifurcation<'r, Q: ?Sized, R>( mut self, @@ -112,10 +115,8 @@ impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Lea let mut upper_bound = SearchBound::from_range(end); loop { let (lower_edge_idx, lower_child_bound) = self.find_lower_bound_index(lower_bound); - let (upper_edge_idx, upper_child_bound) = self.find_upper_bound_index(upper_bound); - if lower_edge_idx > upper_edge_idx { - panic!("Ord is ill-defined in BTreeMap range") - } + let (upper_edge_idx, upper_child_bound) = + unsafe { self.find_upper_bound_index(upper_bound, lower_edge_idx) }; if lower_edge_idx < upper_edge_idx { return Ok(( self, @@ -125,6 +126,7 @@ impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Lea upper_child_bound, )); } + debug_assert_eq!(lower_edge_idx, upper_edge_idx); let common_edge = unsafe { Handle::new_edge(self, lower_edge_idx) }; match common_edge.force() { Leaf(common_edge) => return Err(common_edge), @@ -164,7 +166,7 @@ impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Lea Q: ?Sized + Ord, K: Borrow<Q>, { - let (edge_idx, bound) = self.find_upper_bound_index(bound); + let (edge_idx, bound) = unsafe { self.find_upper_bound_index(bound, 0) }; let edge = unsafe { Handle::new_edge(self, edge_idx) }; (edge, bound) } @@ -183,29 +185,33 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> { Q: Ord, K: Borrow<Q>, { - match self.find_key_index(key) { + match unsafe { self.find_key_index(key, 0) } { IndexResult::KV(idx) => Found(unsafe { Handle::new_kv(self, idx) }), IndexResult::Edge(idx) => GoDown(unsafe { Handle::new_edge(self, idx) }), } } /// Returns either the KV index in the node at which the key (or an equivalent) - /// exists, or the edge index where the key belongs. + /// exists, or the edge index where the key belongs, starting from a particular index. /// /// The result is meaningful only if the tree is ordered by key, like the tree /// in a `BTreeMap` is. - fn find_key_index<Q: ?Sized>(&self, key: &Q) -> IndexResult + /// + /// # Safety + /// `start_index` must be a valid edge index for the node. + unsafe fn find_key_index<Q: ?Sized>(&self, key: &Q, start_index: usize) -> IndexResult where Q: Ord, K: Borrow<Q>, { let node = self.reborrow(); let keys = node.keys(); - for (i, k) in keys.iter().enumerate() { + debug_assert!(start_index <= keys.len()); + for (offset, k) in unsafe { keys.get_unchecked(start_index..) }.iter().enumerate() { match key.cmp(k.borrow()) { Ordering::Greater => {} - Ordering::Equal => return IndexResult::KV(i), - Ordering::Less => return IndexResult::Edge(i), + Ordering::Equal => return IndexResult::KV(start_index + offset), + Ordering::Less => return IndexResult::Edge(start_index + offset), } } IndexResult::Edge(keys.len()) @@ -225,11 +231,11 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> { K: Borrow<Q>, { match bound { - Included(key) => match self.find_key_index(key) { + Included(key) => match unsafe { self.find_key_index(key, 0) } { IndexResult::KV(idx) => (idx, AllExcluded), IndexResult::Edge(idx) => (idx, bound), }, - Excluded(key) => match self.find_key_index(key) { + Excluded(key) => match unsafe { self.find_key_index(key, 0) } { IndexResult::KV(idx) => (idx + 1, AllIncluded), IndexResult::Edge(idx) => (idx, bound), }, @@ -238,26 +244,31 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> { } } - /// Clone of `find_lower_bound_index` for the upper bound. - fn find_upper_bound_index<'r, Q>( + /// Mirror image of `find_lower_bound_index` for the upper bound, + /// with an additional parameter to skip part of the key array. + /// + /// # Safety + /// `start_index` must be a valid edge index for the node. + unsafe fn find_upper_bound_index<'r, Q>( &self, bound: SearchBound<&'r Q>, + start_index: usize, ) -> (usize, SearchBound<&'r Q>) where Q: ?Sized + Ord, K: Borrow<Q>, { match bound { - Included(key) => match self.find_key_index(key) { + Included(key) => match unsafe { self.find_key_index(key, start_index) } { IndexResult::KV(idx) => (idx + 1, AllExcluded), IndexResult::Edge(idx) => (idx, bound), }, - Excluded(key) => match self.find_key_index(key) { + Excluded(key) => match unsafe { self.find_key_index(key, start_index) } { IndexResult::KV(idx) => (idx, AllIncluded), IndexResult::Edge(idx) => (idx, bound), }, AllIncluded => (self.len(), AllIncluded), - AllExcluded => (0, AllExcluded), + AllExcluded => (start_index, AllExcluded), } } } diff --git a/library/alloc/src/fmt.rs b/library/alloc/src/fmt.rs index f9424b1d747..3ef55f06e51 100644 --- a/library/alloc/src/fmt.rs +++ b/library/alloc/src/fmt.rs @@ -19,6 +19,10 @@ //! format!("{value}", value=4); // => "4" //! format!("{} {}", 1, 2); // => "1 2" //! format!("{:04}", 42); // => "0042" with leading zeros +//! format!("{:#?}", (100, 200)); // => "( +//! // 100, +//! // 200, +//! // )" //! ``` //! //! From these, you can see that the first argument is a format string. It is @@ -157,13 +161,12 @@ //! //! * `+` - This is intended for numeric types and indicates that the sign //! should always be printed. Positive signs are never printed by -//! default, and the negative sign is only printed by default for the -//! `Signed` trait. This flag indicates that the correct sign (`+` or `-`) -//! should always be printed. +//! default, and the negative sign is only printed by default for signed values. +//! This flag indicates that the correct sign (`+` or `-`) should always be printed. //! * `-` - Currently not used //! * `#` - This flag indicates that the "alternate" form of printing should //! be used. The alternate forms are: -//! * `#?` - pretty-print the [`Debug`] formatting +//! * `#?` - pretty-print the [`Debug`] formatting (adds linebreaks and indentation) //! * `#x` - precedes the argument with a `0x` //! * `#X` - precedes the argument with a `0x` //! * `#b` - precedes the argument with a `0b` diff --git a/library/alloc/src/lib.rs b/library/alloc/src/lib.rs index 40f2de8f70d..14cb1d3b405 100644 --- a/library/alloc/src/lib.rs +++ b/library/alloc/src/lib.rs @@ -108,6 +108,7 @@ // that the feature-gate isn't enabled. Ideally, it wouldn't check for the feature gate for docs // from other crates, but since this can only appear for lang items, it doesn't seem worth fixing. #![feature(intra_doc_pointers)] +#![feature(iter_zip)] #![feature(lang_items)] #![feature(layout_for_ptr)] #![feature(maybe_uninit_ref)] @@ -132,7 +133,6 @@ #![feature(trusted_len)] #![feature(unboxed_closures)] #![feature(unicode_internals)] -#![cfg_attr(bootstrap, feature(unsafe_block_in_unsafe_fn))] #![feature(unsize)] #![feature(unsized_fn_params)] #![feature(allocator_internals)] @@ -141,8 +141,7 @@ #![feature(alloc_layout_extra)] #![feature(trusted_random_access)] #![feature(try_trait)] -#![cfg_attr(bootstrap, feature(type_alias_impl_trait))] -#![cfg_attr(not(bootstrap), feature(min_type_alias_impl_trait))] +#![feature(min_type_alias_impl_trait)] #![feature(associated_type_bounds)] #![feature(slice_group_by)] #![feature(decl_macro)] diff --git a/library/alloc/src/raw_vec.rs b/library/alloc/src/raw_vec.rs index 56f4ebe57f8..dc02c9c883e 100644 --- a/library/alloc/src/raw_vec.rs +++ b/library/alloc/src/raw_vec.rs @@ -315,8 +315,24 @@ impl<T, A: Allocator> RawVec<T, A> { /// # vector.push_all(&[1, 3, 5, 7, 9]); /// # } /// ``` + #[inline] pub fn reserve(&mut self, len: usize, additional: usize) { - handle_reserve(self.try_reserve(len, additional)); + // Callers expect this function to be very cheap when there is already sufficient capacity. + // Therefore, we move all the resizing and error-handling logic from grow_amortized and + // handle_reserve behind a call, while making sure that the this function is likely to be + // inlined as just a comparison and a call if the comparison fails. + #[cold] + fn do_reserve_and_handle<T, A: Allocator>( + slf: &mut RawVec<T, A>, + len: usize, + additional: usize, + ) { + handle_reserve(slf.grow_amortized(len, additional)); + } + + if self.needs_to_grow(len, additional) { + do_reserve_and_handle(self, len, additional); + } } /// The same as `reserve`, but returns on errors instead of panicking or aborting. diff --git a/library/alloc/src/rc.rs b/library/alloc/src/rc.rs index dac4acc4692..2ee5e6c791c 100644 --- a/library/alloc/src/rc.rs +++ b/library/alloc/src/rc.rs @@ -1848,8 +1848,11 @@ impl<T, I: iter::TrustedLen<Item = T>> ToRcSlice<T> for I { Rc::from_iter_exact(self, low) } } else { - // Fall back to normal implementation. - self.collect::<Vec<T>>().into() + // TrustedLen contract guarantees that `upper_bound == `None` implies an iterator + // length exceeding `usize::MAX`. + // The default implementation would collect into a vec which would panic. + // Thus we panic here immediately without invoking `Vec` code. + panic!("capacity overflow"); } } } diff --git a/library/alloc/src/slice.rs b/library/alloc/src/slice.rs index 8cd4ef7a14e..036b84bb1d5 100644 --- a/library/alloc/src/slice.rs +++ b/library/alloc/src/slice.rs @@ -642,7 +642,7 @@ impl [u8] { /// /// To uppercase the value in-place, use [`make_ascii_uppercase`]. /// - /// [`make_ascii_uppercase`]: u8::make_ascii_uppercase + /// [`make_ascii_uppercase`]: slice::make_ascii_uppercase #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")] #[inline] pub fn to_ascii_uppercase(&self) -> Vec<u8> { @@ -659,7 +659,7 @@ impl [u8] { /// /// To lowercase the value in-place, use [`make_ascii_lowercase`]. /// - /// [`make_ascii_lowercase`]: u8::make_ascii_lowercase + /// [`make_ascii_lowercase`]: slice::make_ascii_lowercase #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")] #[inline] pub fn to_ascii_lowercase(&self) -> Vec<u8> { diff --git a/library/alloc/src/str.rs b/library/alloc/src/str.rs index 3730b407972..879af7cf4dd 100644 --- a/library/alloc/src/str.rs +++ b/library/alloc/src/str.rs @@ -92,8 +92,8 @@ impl<S: Borrow<str>> Join<&str> for [S] { } } -macro_rules! spezialize_for_lengths { - ($separator:expr, $target:expr, $iter:expr; $($num:expr),*) => { +macro_rules! specialize_for_lengths { + ($separator:expr, $target:expr, $iter:expr; $($num:expr),*) => {{ let mut target = $target; let iter = $iter; let sep_bytes = $separator; @@ -104,7 +104,8 @@ macro_rules! spezialize_for_lengths { $num => { for s in iter { copy_slice_and_advance!(target, sep_bytes); - copy_slice_and_advance!(target, s.borrow().as_ref()); + let content_bytes = s.borrow().as_ref(); + copy_slice_and_advance!(target, content_bytes); } }, )* @@ -112,11 +113,13 @@ macro_rules! spezialize_for_lengths { // arbitrary non-zero size fallback for s in iter { copy_slice_and_advance!(target, sep_bytes); - copy_slice_and_advance!(target, s.borrow().as_ref()); + let content_bytes = s.borrow().as_ref(); + copy_slice_and_advance!(target, content_bytes); } } } - }; + target + }} } macro_rules! copy_slice_and_advance { @@ -155,30 +158,33 @@ where // if the `len` calculation overflows, we'll panic // we would have run out of memory anyway and the rest of the function requires // the entire Vec pre-allocated for safety - let len = sep_len + let reserved_len = sep_len .checked_mul(iter.len()) .and_then(|n| { slice.iter().map(|s| s.borrow().as_ref().len()).try_fold(n, usize::checked_add) }) .expect("attempt to join into collection with len > usize::MAX"); - // crucial for safety - let mut result = Vec::with_capacity(len); - assert!(result.capacity() >= len); + // prepare an uninitialized buffer + let mut result = Vec::with_capacity(reserved_len); + debug_assert!(result.capacity() >= reserved_len); result.extend_from_slice(first.borrow().as_ref()); unsafe { - { - let pos = result.len(); - let target = result.get_unchecked_mut(pos..len); - - // copy separator and slices over without bounds checks - // generate loops with hardcoded offsets for small separators - // massive improvements possible (~ x2) - spezialize_for_lengths!(sep, target, iter; 0, 1, 2, 3, 4); - } - result.set_len(len); + let pos = result.len(); + let target = result.get_unchecked_mut(pos..reserved_len); + + // copy separator and slices over without bounds checks + // generate loops with hardcoded offsets for small separators + // massive improvements possible (~ x2) + let remain = specialize_for_lengths!(sep, target, iter; 0, 1, 2, 3, 4); + + // A weird borrow implementation may return different + // slices for the length calculation and the actual copy. + // Make sure we don't expose uninitialized bytes to the caller. + let result_len = reserved_len - remain.len(); + result.set_len(result_len); } result } diff --git a/library/alloc/src/sync.rs b/library/alloc/src/sync.rs index aeae888dddc..1b7e656cefd 100644 --- a/library/alloc/src/sync.rs +++ b/library/alloc/src/sync.rs @@ -2481,8 +2481,11 @@ impl<T, I: iter::TrustedLen<Item = T>> ToArcSlice<T> for I { Arc::from_iter_exact(self, low) } } else { - // Fall back to normal implementation. - self.collect::<Vec<T>>().into() + // TrustedLen contract guarantees that `upper_bound == `None` implies an iterator + // length exceeding `usize::MAX`. + // The default implementation would collect into a vec which would panic. + // Thus we panic here immediately without invoking `Vec` code. + panic!("capacity overflow"); } } } diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs index bcbdffabc7f..324e894bafd 100644 --- a/library/alloc/src/vec/into_iter.rs +++ b/library/alloc/src/vec/into_iter.rs @@ -85,20 +85,29 @@ impl<T, A: Allocator> IntoIter<T, A> { ptr::slice_from_raw_parts_mut(self.ptr as *mut T, self.len()) } - pub(super) fn drop_remaining(&mut self) { - unsafe { - ptr::drop_in_place(self.as_mut_slice()); - } - self.ptr = self.end; - } + /// Drops remaining elements and relinquishes the backing allocation. + /// + /// This is roughly equivalent to the following, but more efficient + /// + /// ``` + /// # let mut into_iter = Vec::<u8>::with_capacity(10).into_iter(); + /// (&mut into_iter).for_each(core::mem::drop); + /// unsafe { core::ptr::write(&mut into_iter, Vec::new().into_iter()); } + /// ``` + pub(super) fn forget_allocation_drop_remaining(&mut self) { + let remaining = self.as_raw_mut_slice(); - /// Relinquishes the backing allocation, equivalent to - /// `ptr::write(&mut self, Vec::new().into_iter())` - pub(super) fn forget_allocation(&mut self) { + // overwrite the individual fields instead of creating a new + // struct and then overwriting &mut self. + // this creates less assembly self.cap = 0; self.buf = unsafe { NonNull::new_unchecked(RawVec::NEW.ptr()) }; self.ptr = self.buf.as_ptr(); self.end = self.buf.as_ptr(); + + unsafe { + ptr::drop_in_place(remaining); + } } } diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index ff93c772b5b..91c3b16deee 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -58,7 +58,7 @@ use core::convert::TryFrom; use core::fmt; use core::hash::{Hash, Hasher}; use core::intrinsics::{arith_offset, assume}; -use core::iter::FromIterator; +use core::iter::{self, FromIterator}; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop, MaybeUninit}; use core::ops::{self, Index, IndexMut, Range, RangeBounds}; @@ -267,12 +267,12 @@ mod spec_extend; /// unspecified, and you should use the appropriate methods to modify these. /// The pointer will never be null, so this type is null-pointer-optimized. /// -/// However, the pointer may not actually point to allocated memory. In particular, +/// However, the pointer might not actually point to allocated memory. In particular, /// if you construct a `Vec` with capacity 0 via [`Vec::new`], [`vec![]`][`vec!`], /// [`Vec::with_capacity(0)`][`Vec::with_capacity`], or by calling [`shrink_to_fit`] /// on an empty Vec, it will not allocate memory. Similarly, if you store zero-sized /// types inside a `Vec`, it will not allocate space for them. *Note that in this case -/// the `Vec` may not report a [`capacity`] of 0*. `Vec` will allocate if and only +/// the `Vec` might not report a [`capacity`] of 0*. `Vec` will allocate if and only /// if [`mem::size_of::<T>`]`() * capacity() > 0`. In general, `Vec`'s allocation /// details are very subtle — if you intend to allocate memory using a `Vec` /// and use it for something else (either to pass to unsafe code, or to build your @@ -347,7 +347,7 @@ mod spec_extend; /// whatever is most efficient or otherwise easy to implement. Do not rely on /// removed data to be erased for security purposes. Even if you drop a `Vec`, its /// buffer may simply be reused by another `Vec`. Even if you zero a `Vec`'s memory -/// first, that may not actually happen because the optimizer does not consider +/// first, that might not actually happen because the optimizer does not consider /// this a side-effect that must be preserved. There is one case which we will /// not break, however: using `unsafe` code to write to the excess capacity, /// and then increasing the length to match, is always valid. @@ -410,6 +410,10 @@ impl<T> Vec<T> { /// /// [Capacity and reallocation]: #capacity-and-reallocation /// + /// # Panics + /// + /// Panics if the new capacity exceeds `isize::MAX` bytes. + /// /// # Examples /// /// ``` @@ -541,6 +545,10 @@ impl<T, A: Allocator> Vec<T, A> { /// /// [Capacity and reallocation]: #capacity-and-reallocation /// + /// # Panics + /// + /// Panics if the new capacity exceeds `isize::MAX` bytes. + /// /// # Examples /// /// ``` @@ -2268,11 +2276,8 @@ impl<T: Clone, A: Allocator> ExtendFromWithinSpec for Vec<T, A> { // - caller guaratees that src is a valid index let to_clone = unsafe { this.get_unchecked(src) }; - to_clone - .iter() - .cloned() - .zip(spare.iter_mut()) - .map(|(src, dst)| dst.write(src)) + iter::zip(to_clone, spare) + .map(|(src, dst)| dst.write(src.clone())) // Note: // - Element was just initialized with `MaybeUninit::write`, so it's ok to increace len // - len is increased after each element to prevent leaks (see issue #82533) diff --git a/library/alloc/src/vec/source_iter_marker.rs b/library/alloc/src/vec/source_iter_marker.rs index 50882fc1767..e857d284d3a 100644 --- a/library/alloc/src/vec/source_iter_marker.rs +++ b/library/alloc/src/vec/source_iter_marker.rs @@ -69,9 +69,9 @@ where } // drop any remaining values at the tail of the source - src.drop_remaining(); // but prevent drop of the allocation itself once IntoIter goes out of scope - src.forget_allocation(); + // if the drop panics then we also leak any elements collected into dst_buf + src.forget_allocation_drop_remaining(); let vec = unsafe { Vec::from_raw_parts(dst_buf, len, cap) }; diff --git a/library/alloc/src/vec/spec_extend.rs b/library/alloc/src/vec/spec_extend.rs index b6186a7ebaf..e132befcfa5 100644 --- a/library/alloc/src/vec/spec_extend.rs +++ b/library/alloc/src/vec/spec_extend.rs @@ -47,7 +47,12 @@ where }); } } else { - self.extend_desugared(iterator) + // Per TrustedLen contract a `None` upper bound means that the iterator length + // truly exceeds usize::MAX, which would eventually lead to a capacity overflow anyway. + // Since the other branch already panics eagerly (via `reserve()`) we do the same here. + // This avoids additional codegen for a fallback code path which would eventually + // panic anyway. + panic!("capacity overflow"); } } } diff --git a/library/alloc/src/vec/spec_from_iter_nested.rs b/library/alloc/src/vec/spec_from_iter_nested.rs index ec390c62165..948cf044197 100644 --- a/library/alloc/src/vec/spec_from_iter_nested.rs +++ b/library/alloc/src/vec/spec_from_iter_nested.rs @@ -46,10 +46,13 @@ where fn from_iter(iterator: I) -> Self { let mut vector = match iterator.size_hint() { (_, Some(upper)) => Vec::with_capacity(upper), - _ => Vec::new(), + // TrustedLen contract guarantees that `size_hint() == (_, None)` means that there + // are more than `usize::MAX` elements. + // Since the previous branch would eagerly panic if the capacity is too large + // (via `with_capacity`) we do the same here. + _ => panic!("capacity overflow"), }; - // must delegate to spec_extend() since extend() itself delegates - // to spec_from for empty Vecs + // reuse extend specialization for TrustedLen vector.spec_extend(iterator); vector } |