diff options
Diffstat (limited to 'library/alloc/src/collections')
| -rw-r--r-- | library/alloc/src/collections/binary_heap/mod.rs (renamed from library/alloc/src/collections/binary_heap.rs) | 65 | ||||
| -rw-r--r-- | library/alloc/src/collections/binary_heap/tests.rs | 121 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/map/tests.rs | 6 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/mod.rs | 3 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/node.rs | 28 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/set/tests.rs | 4 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/testing/crash_test.rs | 119 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/testing/mod.rs | 3 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/testing/ord_chaos.rs | 81 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/testing/rng.rs | 28 | ||||
| -rw-r--r-- | library/alloc/src/collections/linked_list/tests.rs | 69 | ||||
| -rw-r--r-- | library/alloc/src/collections/vec_deque/into_iter.rs | 4 | ||||
| -rw-r--r-- | library/alloc/src/collections/vec_deque/mod.rs | 186 | ||||
| -rw-r--r-- | library/alloc/src/collections/vec_deque/spec_from_iter.rs | 33 | ||||
| -rw-r--r-- | library/alloc/src/collections/vec_deque/tests.rs | 42 |
15 files changed, 397 insertions, 395 deletions
diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap/mod.rs index 4583bc9a1..0b73b1af4 100644 --- a/library/alloc/src/collections/binary_heap.rs +++ b/library/alloc/src/collections/binary_heap/mod.rs @@ -146,6 +146,7 @@ use core::fmt; use core::iter::{FromIterator, FusedIterator, InPlaceIterable, SourceIter, TrustedLen}; use core::mem::{self, swap, ManuallyDrop}; +use core::num::NonZeroUsize; use core::ops::{Deref, DerefMut}; use core::ptr; @@ -165,12 +166,20 @@ mod tests; /// It is a logic error for an item to be modified in such a way that the /// item's ordering relative to any other item, as determined by the [`Ord`] /// trait, changes while it is in the heap. This is normally only possible -/// through [`Cell`], [`RefCell`], global state, I/O, or unsafe code. The +/// through interior mutability, global state, I/O, or unsafe code. The /// behavior resulting from such a logic error is not specified, but will /// be encapsulated to the `BinaryHeap` that observed the logic error and not /// result in undefined behavior. This could include panics, incorrect results, /// aborts, memory leaks, and non-termination. /// +/// As long as no elements change their relative order while being in the heap +/// as described above, the API of `BinaryHeap` guarantees that the heap +/// invariant remains intact i.e. its methods all behave as documented. For +/// example if a method is documented as iterating in sorted order, that's +/// guaranteed to work as long as elements in the heap have not changed order, +/// even in the presence of closures getting unwinded out of, iterators getting +/// leaked, and similar foolishness. +/// /// # Examples /// /// ``` @@ -279,7 +288,9 @@ pub struct BinaryHeap<T> { #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] pub struct PeekMut<'a, T: 'a + Ord> { heap: &'a mut BinaryHeap<T>, - sift: bool, + // If a set_len + sift_down are required, this is Some. If a &mut T has not + // yet been exposed to peek_mut()'s caller, it's None. + original_len: Option<NonZeroUsize>, } #[stable(feature = "collection_debug", since = "1.17.0")] @@ -292,7 +303,14 @@ impl<T: Ord + fmt::Debug> fmt::Debug for PeekMut<'_, T> { #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] impl<T: Ord> Drop for PeekMut<'_, T> { fn drop(&mut self) { - if self.sift { + if let Some(original_len) = self.original_len { + // SAFETY: That's how many elements were in the Vec at the time of + // the PeekMut::deref_mut call, and therefore also at the time of + // the BinaryHeap::peek_mut call. Since the PeekMut did not end up + // getting leaked, we are now undoing the leak amplification that + // the DerefMut prepared for. + unsafe { self.heap.data.set_len(original_len.get()) }; + // SAFETY: PeekMut is only instantiated for non-empty heaps. unsafe { self.heap.sift_down(0) }; } @@ -313,7 +331,26 @@ impl<T: Ord> Deref for PeekMut<'_, T> { impl<T: Ord> DerefMut for PeekMut<'_, T> { fn deref_mut(&mut self) -> &mut T { debug_assert!(!self.heap.is_empty()); - self.sift = true; + + let len = self.heap.len(); + if len > 1 { + // Here we preemptively leak all the rest of the underlying vector + // after the currently max element. If the caller mutates the &mut T + // we're about to give them, and then leaks the PeekMut, all these + // elements will remain leaked. If they don't leak the PeekMut, then + // either Drop or PeekMut::pop will un-leak the vector elements. + // + // This is technique is described throughout several other places in + // the standard library as "leak amplification". + unsafe { + // SAFETY: len > 1 so len != 0. + self.original_len = Some(NonZeroUsize::new_unchecked(len)); + // SAFETY: len > 1 so all this does for now is leak elements, + // which is safe. + self.heap.data.set_len(1); + } + } + // SAFE: PeekMut is only instantiated for non-empty heaps unsafe { self.heap.data.get_unchecked_mut(0) } } @@ -323,9 +360,16 @@ impl<'a, T: Ord> PeekMut<'a, T> { /// Removes the peeked value from the heap and returns it. #[stable(feature = "binary_heap_peek_mut_pop", since = "1.18.0")] pub fn pop(mut this: PeekMut<'a, T>) -> T { - let value = this.heap.pop().unwrap(); - this.sift = false; - value + if let Some(original_len) = this.original_len.take() { + // SAFETY: This is how many elements were in the Vec at the time of + // the BinaryHeap::peek_mut call. + unsafe { this.heap.data.set_len(original_len.get()) }; + + // Unlike in Drop, here we don't also need to do a sift_down even if + // the caller could've mutated the element. It is removed from the + // heap on the next line and pop() is not sensitive to its value. + } + this.heap.pop().unwrap() } } @@ -398,8 +442,9 @@ impl<T: Ord> BinaryHeap<T> { /// Returns a mutable reference to the greatest item in the binary heap, or /// `None` if it is empty. /// - /// Note: If the `PeekMut` value is leaked, the heap may be in an - /// inconsistent state. + /// Note: If the `PeekMut` value is leaked, some heap elements might get + /// leaked along with it, but the remaining elements will remain a valid + /// heap. /// /// # Examples /// @@ -426,7 +471,7 @@ impl<T: Ord> BinaryHeap<T> { /// otherwise it's *O*(1). #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T>> { - if self.is_empty() { None } else { Some(PeekMut { heap: self, sift: false }) } + if self.is_empty() { None } else { Some(PeekMut { heap: self, original_len: None }) } } /// Removes the greatest item from the binary heap and returns it, or `None` if it diff --git a/library/alloc/src/collections/binary_heap/tests.rs b/library/alloc/src/collections/binary_heap/tests.rs index 5a05215ae..ffbb6c80a 100644 --- a/library/alloc/src/collections/binary_heap/tests.rs +++ b/library/alloc/src/collections/binary_heap/tests.rs @@ -1,8 +1,9 @@ use super::*; use crate::boxed::Box; +use crate::testing::crash_test::{CrashTestDummy, Panic}; +use core::mem; use std::iter::TrustedLen; use std::panic::{catch_unwind, AssertUnwindSafe}; -use std::sync::atomic::{AtomicU32, Ordering}; #[test] fn test_iterator() { @@ -147,6 +148,24 @@ fn test_peek_mut() { } #[test] +fn test_peek_mut_leek() { + let data = vec![4, 2, 7]; + let mut heap = BinaryHeap::from(data); + let mut max = heap.peek_mut().unwrap(); + *max = -1; + + // The PeekMut object's Drop impl would have been responsible for moving the + // -1 out of the max position of the BinaryHeap, but we don't run it. + mem::forget(max); + + // Absent some mitigation like leak amplification, the -1 would incorrectly + // end up in the last position of the returned Vec, with the rest of the + // heap's original contents in front of it in sorted order. + let sorted_vec = heap.into_sorted_vec(); + assert!(sorted_vec.is_sorted(), "{:?}", sorted_vec); +} + +#[test] fn test_peek_mut_pop() { let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]; let mut heap = BinaryHeap::from(data); @@ -291,33 +310,83 @@ fn test_drain_sorted() { #[test] fn test_drain_sorted_leak() { - static DROPS: AtomicU32 = AtomicU32::new(0); - - #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)] - struct D(u32, bool); - - impl Drop for D { - fn drop(&mut self) { - DROPS.fetch_add(1, Ordering::SeqCst); - - if self.1 { - panic!("panic in `drop`"); - } - } - } - + let d0 = CrashTestDummy::new(0); + let d1 = CrashTestDummy::new(1); + let d2 = CrashTestDummy::new(2); + let d3 = CrashTestDummy::new(3); + let d4 = CrashTestDummy::new(4); + let d5 = CrashTestDummy::new(5); let mut q = BinaryHeap::from(vec![ - D(0, false), - D(1, false), - D(2, false), - D(3, true), - D(4, false), - D(5, false), + d0.spawn(Panic::Never), + d1.spawn(Panic::Never), + d2.spawn(Panic::Never), + d3.spawn(Panic::InDrop), + d4.spawn(Panic::Never), + d5.spawn(Panic::Never), ]); - catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).ok(); + catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).unwrap_err(); + + assert_eq!(d0.dropped(), 1); + assert_eq!(d1.dropped(), 1); + assert_eq!(d2.dropped(), 1); + assert_eq!(d3.dropped(), 1); + assert_eq!(d4.dropped(), 1); + assert_eq!(d5.dropped(), 1); + assert!(q.is_empty()); +} + +#[test] +fn test_drain_forget() { + let a = CrashTestDummy::new(0); + let b = CrashTestDummy::new(1); + let c = CrashTestDummy::new(2); + let mut q = + BinaryHeap::from(vec![a.spawn(Panic::Never), b.spawn(Panic::Never), c.spawn(Panic::Never)]); + + catch_unwind(AssertUnwindSafe(|| { + let mut it = q.drain(); + it.next(); + mem::forget(it); + })) + .unwrap(); + // Behaviour after leaking is explicitly unspecified and order is arbitrary, + // so it's fine if these start failing, but probably worth knowing. + assert!(q.is_empty()); + assert_eq!(a.dropped() + b.dropped() + c.dropped(), 1); + assert_eq!(a.dropped(), 0); + assert_eq!(b.dropped(), 0); + assert_eq!(c.dropped(), 1); + drop(q); + assert_eq!(a.dropped(), 0); + assert_eq!(b.dropped(), 0); + assert_eq!(c.dropped(), 1); +} - assert_eq!(DROPS.load(Ordering::SeqCst), 6); +#[test] +fn test_drain_sorted_forget() { + let a = CrashTestDummy::new(0); + let b = CrashTestDummy::new(1); + let c = CrashTestDummy::new(2); + let mut q = + BinaryHeap::from(vec![a.spawn(Panic::Never), b.spawn(Panic::Never), c.spawn(Panic::Never)]); + + catch_unwind(AssertUnwindSafe(|| { + let mut it = q.drain_sorted(); + it.next(); + mem::forget(it); + })) + .unwrap(); + // Behaviour after leaking is explicitly unspecified, + // so it's fine if these start failing, but probably worth knowing. + assert_eq!(q.len(), 2); + assert_eq!(a.dropped(), 0); + assert_eq!(b.dropped(), 0); + assert_eq!(c.dropped(), 1); + drop(q); + assert_eq!(a.dropped(), 1); + assert_eq!(b.dropped(), 1); + assert_eq!(c.dropped(), 1); } #[test] @@ -415,7 +484,7 @@ fn test_retain() { #[test] #[cfg(not(target_os = "emscripten"))] fn panic_safe() { - use rand::{seq::SliceRandom, thread_rng}; + use rand::seq::SliceRandom; use std::cmp; use std::panic::{self, AssertUnwindSafe}; use std::sync::atomic::{AtomicUsize, Ordering}; @@ -440,7 +509,7 @@ fn panic_safe() { self.0.partial_cmp(&other.0) } } - let mut rng = thread_rng(); + let mut rng = crate::test_helpers::test_rng(); const DATASZ: usize = 32; // Miri is too slow let ntest = if cfg!(miri) { 1 } else { 10 }; diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs index 4c372b1d6..700b1463b 100644 --- a/library/alloc/src/collections/btree/map/tests.rs +++ b/library/alloc/src/collections/btree/map/tests.rs @@ -1,12 +1,12 @@ -use super::super::testing::crash_test::{CrashTestDummy, Panic}; -use super::super::testing::ord_chaos::{Cyclic3, Governed, Governor}; -use super::super::testing::rng::DeterministicRng; use super::Entry::{Occupied, Vacant}; use super::*; use crate::boxed::Box; use crate::fmt::Debug; use crate::rc::Rc; use crate::string::{String, ToString}; +use crate::testing::crash_test::{CrashTestDummy, Panic}; +use crate::testing::ord_chaos::{Cyclic3, Governed, Governor}; +use crate::testing::rng::DeterministicRng; use crate::vec::Vec; use std::cmp::Ordering; use std::convert::TryFrom; diff --git a/library/alloc/src/collections/btree/mod.rs b/library/alloc/src/collections/btree/mod.rs index 9d43ac5c5..7552f2fc0 100644 --- a/library/alloc/src/collections/btree/mod.rs +++ b/library/alloc/src/collections/btree/mod.rs @@ -21,6 +21,3 @@ trait Recover<Q: ?Sized> { fn take(&mut self, key: &Q) -> Option<Self::Key>; fn replace(&mut self, key: Self::Key) -> Option<Self::Key>; } - -#[cfg(test)] -mod testing; diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs index da766b67a..691246644 100644 --- a/library/alloc/src/collections/btree/node.rs +++ b/library/alloc/src/collections/btree/node.rs @@ -318,7 +318,10 @@ impl<BorrowType: marker::BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> pub fn ascend( self, ) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> { - let _ = BorrowType::TRAVERSAL_PERMIT; + const { + assert!(BorrowType::TRAVERSAL_PERMIT); + } + // We need to use raw pointers to nodes because, if BorrowType is marker::ValMut, // there might be outstanding mutable references to values that we must not invalidate. let leaf_ptr: *const _ = Self::as_leaf_ptr(&self); @@ -1003,7 +1006,10 @@ impl<BorrowType: marker::BorrowType, K, V> /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should /// both, upon success, do nothing. pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { - let _ = BorrowType::TRAVERSAL_PERMIT; + const { + assert!(BorrowType::TRAVERSAL_PERMIT); + } + // We need to use raw pointers to nodes because, if BorrowType is // marker::ValMut, there might be outstanding mutable references to // values that we must not invalidate. There's no worry accessing the @@ -1666,17 +1672,17 @@ pub mod marker { pub struct ValMut<'a>(PhantomData<&'a mut ()>); pub trait BorrowType { - // If node references of this borrow type allow traversing to other - // nodes in the tree, this constant can be evaluated. Thus reading it - // serves as a compile-time assertion. - const TRAVERSAL_PERMIT: () = (); + /// If node references of this borrow type allow traversing to other + /// nodes in the tree, this constant is set to `true`. It can be used + /// for a compile-time assertion. + const TRAVERSAL_PERMIT: bool = true; } impl BorrowType for Owned { - // Reject evaluation, because traversal isn't needed. Instead traversal - // happens using the result of `borrow_mut`. - // By disabling traversal, and only creating new references to roots, - // we know that every reference of the `Owned` type is to a root node. - const TRAVERSAL_PERMIT: () = panic!(); + /// Reject traversal, because it isn't needed. Instead traversal + /// happens using the result of `borrow_mut`. + /// By disabling traversal, and only creating new references to roots, + /// we know that every reference of the `Owned` type is to a root node. + const TRAVERSAL_PERMIT: bool = false; } impl BorrowType for Dying {} impl<'a> BorrowType for Immut<'a> {} diff --git a/library/alloc/src/collections/btree/set/tests.rs b/library/alloc/src/collections/btree/set/tests.rs index 502d3e1d1..7b8d41a60 100644 --- a/library/alloc/src/collections/btree/set/tests.rs +++ b/library/alloc/src/collections/btree/set/tests.rs @@ -1,6 +1,6 @@ -use super::super::testing::crash_test::{CrashTestDummy, Panic}; -use super::super::testing::rng::DeterministicRng; use super::*; +use crate::testing::crash_test::{CrashTestDummy, Panic}; +use crate::testing::rng::DeterministicRng; use crate::vec::Vec; use std::cmp::Ordering; use std::hash::{Hash, Hasher}; diff --git a/library/alloc/src/collections/btree/testing/crash_test.rs b/library/alloc/src/collections/btree/testing/crash_test.rs deleted file mode 100644 index bcf5f5f72..000000000 --- a/library/alloc/src/collections/btree/testing/crash_test.rs +++ /dev/null @@ -1,119 +0,0 @@ -// We avoid relying on anything else in the crate, apart from the `Debug` trait. -use crate::fmt::Debug; -use std::cmp::Ordering; -use std::sync::atomic::{AtomicUsize, Ordering::SeqCst}; - -/// A blueprint for crash test dummy instances that monitor particular events. -/// Some instances may be configured to panic at some point. -/// Events are `clone`, `drop` or some anonymous `query`. -/// -/// Crash test dummies are identified and ordered by an id, so they can be used -/// as keys in a BTreeMap. -#[derive(Debug)] -pub struct CrashTestDummy { - pub id: usize, - cloned: AtomicUsize, - dropped: AtomicUsize, - queried: AtomicUsize, -} - -impl CrashTestDummy { - /// Creates a crash test dummy design. The `id` determines order and equality of instances. - pub fn new(id: usize) -> CrashTestDummy { - CrashTestDummy { - id, - cloned: AtomicUsize::new(0), - dropped: AtomicUsize::new(0), - queried: AtomicUsize::new(0), - } - } - - /// Creates an instance of a crash test dummy that records what events it experiences - /// and optionally panics. - pub fn spawn(&self, panic: Panic) -> Instance<'_> { - Instance { origin: self, panic } - } - - /// Returns how many times instances of the dummy have been cloned. - pub fn cloned(&self) -> usize { - self.cloned.load(SeqCst) - } - - /// Returns how many times instances of the dummy have been dropped. - pub fn dropped(&self) -> usize { - self.dropped.load(SeqCst) - } - - /// Returns how many times instances of the dummy have had their `query` member invoked. - pub fn queried(&self) -> usize { - self.queried.load(SeqCst) - } -} - -#[derive(Debug)] -pub struct Instance<'a> { - origin: &'a CrashTestDummy, - panic: Panic, -} - -#[derive(Copy, Clone, Debug, PartialEq, Eq)] -pub enum Panic { - Never, - InClone, - InDrop, - InQuery, -} - -impl Instance<'_> { - pub fn id(&self) -> usize { - self.origin.id - } - - /// Some anonymous query, the result of which is already given. - pub fn query<R>(&self, result: R) -> R { - self.origin.queried.fetch_add(1, SeqCst); - if self.panic == Panic::InQuery { - panic!("panic in `query`"); - } - result - } -} - -impl Clone for Instance<'_> { - fn clone(&self) -> Self { - self.origin.cloned.fetch_add(1, SeqCst); - if self.panic == Panic::InClone { - panic!("panic in `clone`"); - } - Self { origin: self.origin, panic: Panic::Never } - } -} - -impl Drop for Instance<'_> { - fn drop(&mut self) { - self.origin.dropped.fetch_add(1, SeqCst); - if self.panic == Panic::InDrop { - panic!("panic in `drop`"); - } - } -} - -impl PartialOrd for Instance<'_> { - fn partial_cmp(&self, other: &Self) -> Option<Ordering> { - self.id().partial_cmp(&other.id()) - } -} - -impl Ord for Instance<'_> { - fn cmp(&self, other: &Self) -> Ordering { - self.id().cmp(&other.id()) - } -} - -impl PartialEq for Instance<'_> { - fn eq(&self, other: &Self) -> bool { - self.id().eq(&other.id()) - } -} - -impl Eq for Instance<'_> {} diff --git a/library/alloc/src/collections/btree/testing/mod.rs b/library/alloc/src/collections/btree/testing/mod.rs deleted file mode 100644 index 7a094f8a5..000000000 --- a/library/alloc/src/collections/btree/testing/mod.rs +++ /dev/null @@ -1,3 +0,0 @@ -pub mod crash_test; -pub mod ord_chaos; -pub mod rng; diff --git a/library/alloc/src/collections/btree/testing/ord_chaos.rs b/library/alloc/src/collections/btree/testing/ord_chaos.rs deleted file mode 100644 index 96ce7c157..000000000 --- a/library/alloc/src/collections/btree/testing/ord_chaos.rs +++ /dev/null @@ -1,81 +0,0 @@ -use std::cell::Cell; -use std::cmp::Ordering::{self, *}; -use std::ptr; - -// Minimal type with an `Ord` implementation violating transitivity. -#[derive(Debug)] -pub enum Cyclic3 { - A, - B, - C, -} -use Cyclic3::*; - -impl PartialOrd for Cyclic3 { - fn partial_cmp(&self, other: &Self) -> Option<Ordering> { - Some(self.cmp(other)) - } -} - -impl Ord for Cyclic3 { - fn cmp(&self, other: &Self) -> Ordering { - match (self, other) { - (A, A) | (B, B) | (C, C) => Equal, - (A, B) | (B, C) | (C, A) => Less, - (A, C) | (B, A) | (C, B) => Greater, - } - } -} - -impl PartialEq for Cyclic3 { - fn eq(&self, other: &Self) -> bool { - self.cmp(&other) == Equal - } -} - -impl Eq for Cyclic3 {} - -// Controls the ordering of values wrapped by `Governed`. -#[derive(Debug)] -pub struct Governor { - flipped: Cell<bool>, -} - -impl Governor { - pub fn new() -> Self { - Governor { flipped: Cell::new(false) } - } - - pub fn flip(&self) { - self.flipped.set(!self.flipped.get()); - } -} - -// Type with an `Ord` implementation that forms a total order at any moment -// (assuming that `T` respects total order), but can suddenly be made to invert -// that total order. -#[derive(Debug)] -pub struct Governed<'a, T>(pub T, pub &'a Governor); - -impl<T: Ord> PartialOrd for Governed<'_, T> { - fn partial_cmp(&self, other: &Self) -> Option<Ordering> { - Some(self.cmp(other)) - } -} - -impl<T: Ord> Ord for Governed<'_, T> { - fn cmp(&self, other: &Self) -> Ordering { - assert!(ptr::eq(self.1, other.1)); - let ord = self.0.cmp(&other.0); - if self.1.flipped.get() { ord.reverse() } else { ord } - } -} - -impl<T: PartialEq> PartialEq for Governed<'_, T> { - fn eq(&self, other: &Self) -> bool { - assert!(ptr::eq(self.1, other.1)); - self.0.eq(&other.0) - } -} - -impl<T: Eq> Eq for Governed<'_, T> {} diff --git a/library/alloc/src/collections/btree/testing/rng.rs b/library/alloc/src/collections/btree/testing/rng.rs deleted file mode 100644 index ecf543bee..000000000 --- a/library/alloc/src/collections/btree/testing/rng.rs +++ /dev/null @@ -1,28 +0,0 @@ -/// XorShiftRng -pub struct DeterministicRng { - count: usize, - x: u32, - y: u32, - z: u32, - w: u32, -} - -impl DeterministicRng { - pub fn new() -> Self { - DeterministicRng { count: 0, x: 0x193a6754, y: 0xa8a7d469, z: 0x97830e05, w: 0x113ba7bb } - } - - /// Guarantees that each returned number is unique. - pub fn next(&mut self) -> u32 { - self.count += 1; - assert!(self.count <= 70029); - let x = self.x; - let t = x ^ (x << 11); - self.x = self.y; - self.y = self.z; - self.z = self.w; - let w_ = self.w; - self.w = w_ ^ (w_ >> 19) ^ (t ^ (t >> 8)); - self.w - } -} diff --git a/library/alloc/src/collections/linked_list/tests.rs b/library/alloc/src/collections/linked_list/tests.rs index f8fbfa1bf..04594d55b 100644 --- a/library/alloc/src/collections/linked_list/tests.rs +++ b/library/alloc/src/collections/linked_list/tests.rs @@ -1,10 +1,11 @@ use super::*; +use crate::testing::crash_test::{CrashTestDummy, Panic}; use crate::vec::Vec; use std::panic::{catch_unwind, AssertUnwindSafe}; use std::thread; -use rand::{thread_rng, RngCore}; +use rand::RngCore; #[test] fn test_basic() { @@ -480,12 +481,12 @@ fn test_split_off_2() { } } -fn fuzz_test(sz: i32) { +fn fuzz_test(sz: i32, rng: &mut impl RngCore) { let mut m: LinkedList<_> = LinkedList::new(); let mut v = vec![]; for i in 0..sz { check_links(&m); - let r: u8 = thread_rng().next_u32() as u8; + let r: u8 = rng.next_u32() as u8; match r % 6 { 0 => { m.pop_back(); @@ -520,11 +521,12 @@ fn fuzz_test(sz: i32) { #[test] fn test_fuzz() { + let mut rng = crate::test_helpers::test_rng(); for _ in 0..25 { - fuzz_test(3); - fuzz_test(16); + fuzz_test(3, &mut rng); + fuzz_test(16, &mut rng); #[cfg(not(miri))] // Miri is too slow - fuzz_test(189); + fuzz_test(189, &mut rng); } } @@ -984,35 +986,34 @@ fn drain_filter_complex() { #[test] fn drain_filter_drop_panic_leak() { - static mut DROPS: i32 = 0; - - struct D(bool); - - impl Drop for D { - fn drop(&mut self) { - unsafe { - DROPS += 1; - } - - if self.0 { - panic!("panic in `drop`"); - } - } - } - + let d0 = CrashTestDummy::new(0); + let d1 = CrashTestDummy::new(1); + let d2 = CrashTestDummy::new(2); + let d3 = CrashTestDummy::new(3); + let d4 = CrashTestDummy::new(4); + let d5 = CrashTestDummy::new(5); + let d6 = CrashTestDummy::new(6); + let d7 = CrashTestDummy::new(7); let mut q = LinkedList::new(); - q.push_back(D(false)); - q.push_back(D(false)); - q.push_back(D(false)); - q.push_back(D(false)); - q.push_back(D(false)); - q.push_front(D(false)); - q.push_front(D(true)); - q.push_front(D(false)); - - catch_unwind(AssertUnwindSafe(|| drop(q.drain_filter(|_| true)))).ok(); - - assert_eq!(unsafe { DROPS }, 8); + q.push_back(d3.spawn(Panic::Never)); + q.push_back(d4.spawn(Panic::Never)); + q.push_back(d5.spawn(Panic::Never)); + q.push_back(d6.spawn(Panic::Never)); + q.push_back(d7.spawn(Panic::Never)); + q.push_front(d2.spawn(Panic::Never)); + q.push_front(d1.spawn(Panic::InDrop)); + q.push_front(d0.spawn(Panic::Never)); + + catch_unwind(AssertUnwindSafe(|| drop(q.drain_filter(|_| true)))).unwrap_err(); + + assert_eq!(d0.dropped(), 1); + assert_eq!(d1.dropped(), 1); + assert_eq!(d2.dropped(), 1); + assert_eq!(d3.dropped(), 1); + assert_eq!(d4.dropped(), 1); + assert_eq!(d5.dropped(), 1); + assert_eq!(d6.dropped(), 1); + assert_eq!(d7.dropped(), 1); assert!(q.is_empty()); } diff --git a/library/alloc/src/collections/vec_deque/into_iter.rs b/library/alloc/src/collections/vec_deque/into_iter.rs index 55f6138cd..e54880e86 100644 --- a/library/alloc/src/collections/vec_deque/into_iter.rs +++ b/library/alloc/src/collections/vec_deque/into_iter.rs @@ -25,6 +25,10 @@ impl<T, A: Allocator> IntoIter<T, A> { pub(super) fn new(inner: VecDeque<T, A>) -> Self { IntoIter { inner } } + + pub(super) fn into_vecdeque(self) -> VecDeque<T, A> { + self.inner + } } #[stable(feature = "collection_debug", since = "1.17.0")] diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs index 4866c53e7..8317ac431 100644 --- a/library/alloc/src/collections/vec_deque/mod.rs +++ b/library/alloc/src/collections/vec_deque/mod.rs @@ -55,6 +55,10 @@ use self::spec_extend::SpecExtend; mod spec_extend; +use self::spec_from_iter::SpecFromIter; + +mod spec_from_iter; + #[cfg(test)] mod tests; @@ -531,12 +535,13 @@ impl<T> VecDeque<T> { /// /// let deque: VecDeque<u32> = VecDeque::new(); /// ``` - // FIXME: This should probably be const #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_const_stable(feature = "const_vec_deque_new", since = "1.68.0")] #[must_use] - pub fn new() -> VecDeque<T> { - VecDeque::new_in(Global) + pub const fn new() -> VecDeque<T> { + // FIXME: This should just be `VecDeque::new_in(Global)` once that hits stable. + VecDeque { head: 0, len: 0, buf: RawVec::NEW } } /// Creates an empty deque with space for at least `capacity` elements. @@ -586,6 +591,38 @@ impl<T, A: Allocator> VecDeque<T, A> { VecDeque { head: 0, len: 0, buf: RawVec::with_capacity_in(capacity, alloc) } } + /// Creates a `VecDeque` from a raw allocation, when the initialized + /// part of that allocation forms a *contiguous* subslice thereof. + /// + /// For use by `vec::IntoIter::into_vecdeque` + /// + /// # Safety + /// + /// All the usual requirements on the allocated memory like in + /// `Vec::from_raw_parts_in`, but takes a *range* of elements that are + /// initialized rather than only supporting `0..len`. Requires that + /// `initialized.start` ≤ `initialized.end` ≤ `capacity`. + #[inline] + pub(crate) unsafe fn from_contiguous_raw_parts_in( + ptr: *mut T, + initialized: Range<usize>, + capacity: usize, + alloc: A, + ) -> Self { + debug_assert!(initialized.start <= initialized.end); + debug_assert!(initialized.end <= capacity); + + // SAFETY: Our safety precondition guarantees the range length won't wrap, + // and that the allocation is valid for use in `RawVec`. + unsafe { + VecDeque { + head: initialized.start, + len: initialized.end.unchecked_sub(initialized.start), + buf: RawVec::from_raw_parts_in(ptr, capacity, alloc), + } + } + } + /// Provides a reference to the element at the given index. /// /// Element at index 0 is the front of the queue. @@ -599,6 +636,7 @@ impl<T, A: Allocator> VecDeque<T, A> { /// buf.push_back(3); /// buf.push_back(4); /// buf.push_back(5); + /// buf.push_back(6); /// assert_eq!(buf.get(1), Some(&4)); /// ``` #[stable(feature = "rust1", since = "1.0.0")] @@ -624,10 +662,11 @@ impl<T, A: Allocator> VecDeque<T, A> { /// buf.push_back(3); /// buf.push_back(4); /// buf.push_back(5); + /// buf.push_back(6); + /// assert_eq!(buf[1], 4); /// if let Some(elem) = buf.get_mut(1) { /// *elem = 7; /// } - /// /// assert_eq!(buf[1], 7); /// ``` #[stable(feature = "rust1", since = "1.0.0")] @@ -905,65 +944,72 @@ impl<T, A: Allocator> VecDeque<T, A> { return; } - if target_cap < self.capacity() { - // There are three cases of interest: - // All elements are out of desired bounds - // Elements are contiguous, and head is out of desired bounds - // Elements are discontiguous, and tail is out of desired bounds + // There are three cases of interest: + // All elements are out of desired bounds + // Elements are contiguous, and tail is out of desired bounds + // Elements are discontiguous + // + // At all other times, element positions are unaffected. + + // `head` and `len` are at most `isize::MAX` and `target_cap < self.capacity()`, so nothing can + // overflow. + let tail_outside = (target_cap + 1..=self.capacity()).contains(&(self.head + self.len)); + + if self.len == 0 { + self.head = 0; + } else if self.head >= target_cap && tail_outside { + // Head and tail are both out of bounds, so copy all of them to the front. // - // At all other times, element positions are unaffected. + // H := head + // L := last element + // H L + // [. . . . . . . . o o o o o o o . ] + // H L + // [o o o o o o o . ] + unsafe { + // nonoverlapping because `self.head >= target_cap >= self.len`. + self.copy_nonoverlapping(self.head, 0, self.len); + } + self.head = 0; + } else if self.head < target_cap && tail_outside { + // Head is in bounds, tail is out of bounds. + // Copy the overflowing part to the beginning of the + // buffer. This won't overlap because `target_cap >= self.len`. // - // Indicates that elements at the head should be moved. - - let tail_outside = (target_cap + 1..=self.capacity()).contains(&(self.head + self.len)); - // Move elements from out of desired bounds (positions after target_cap) - if self.len == 0 { - self.head = 0; - } else if self.head >= target_cap && tail_outside { - // H := head - // L := last element - // H L - // [. . . . . . . . o o o o o o o . ] - // H L - // [o o o o o o o . ] - unsafe { - // nonoverlapping because self.head >= target_cap >= self.len - self.copy_nonoverlapping(self.head, 0, self.len); - } - self.head = 0; - } else if self.head < target_cap && tail_outside { - // H := head - // L := last element - // H L - // [. . . o o o o o o o . . . . . . ] - // L H - // [o o . o o o o o ] - let len = self.head + self.len - target_cap; - unsafe { - self.copy_nonoverlapping(target_cap, 0, len); - } - } else if self.head >= target_cap { - // H := head - // L := last element - // L H - // [o o o o o . . . . . . . . . o o ] - // L H - // [o o o o o . o o ] - let len = self.capacity() - self.head; - let new_head = target_cap - len; - unsafe { - // can't use copy_nonoverlapping here for the same reason - // as in `handle_capacity_increase()` - self.copy(self.head, new_head, len); - } - self.head = new_head; + // H := head + // L := last element + // H L + // [. . . o o o o o o o . . . . . . ] + // L H + // [o o . o o o o o ] + let len = self.head + self.len - target_cap; + unsafe { + self.copy_nonoverlapping(target_cap, 0, len); } - - self.buf.shrink_to_fit(target_cap); - - debug_assert!(self.head < self.capacity() || self.capacity() == 0); - debug_assert!(self.len <= self.capacity()); + } else if !self.is_contiguous() { + // The head slice is at least partially out of bounds, tail is in bounds. + // Copy the head backwards so it lines up with the target capacity. + // This won't overlap because `target_cap >= self.len`. + // + // H := head + // L := last element + // L H + // [o o o o o . . . . . . . . . o o ] + // L H + // [o o o o o . o o ] + let head_len = self.capacity() - self.head; + let new_head = target_cap - head_len; + unsafe { + // can't use `copy_nonoverlapping()` here because the new and old + // regions for the head might overlap. + self.copy(self.head, new_head, head_len); + } + self.head = new_head; } + self.buf.shrink_to_fit(target_cap); + + debug_assert!(self.head < self.capacity() || self.capacity() == 0); + debug_assert!(self.len <= self.capacity()); } /// Shortens the deque, keeping the first `len` elements and dropping @@ -1878,7 +1924,7 @@ impl<T, A: Allocator> VecDeque<T, A> { #[stable(feature = "append", since = "1.4.0")] pub fn append(&mut self, other: &mut Self) { if T::IS_ZST { - self.len += other.len; + self.len = self.len.checked_add(other.len).expect("capacity overflow"); other.len = 0; other.head = 0; return; @@ -2505,7 +2551,7 @@ impl<T, A: Allocator> VecDeque<T, A> { /// The deque is assumed to be partitioned according to the given predicate. /// This means that all elements for which the predicate returns true are at the start of the deque /// and all elements for which the predicate returns false are at the end. - /// For example, [7, 15, 3, 5, 4, 12, 6] is a partitioned under the predicate x % 2 != 0 + /// For example, `[7, 15, 3, 5, 4, 12, 6]` is partitioned under the predicate `x % 2 != 0` /// (all odd numbers are at the start, all even at the end). /// /// If the deque is not partitioned, the returned result is unspecified and meaningless, @@ -2699,18 +2745,8 @@ impl<T, A: Allocator> IndexMut<usize> for VecDeque<T, A> { #[stable(feature = "rust1", since = "1.0.0")] impl<T> FromIterator<T> for VecDeque<T> { - #[inline] fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> VecDeque<T> { - // Since converting is O(1) now, might as well re-use that logic - // (including things like the `vec::IntoIter`→`Vec` specialization) - // especially as that could save us some monomorphiziation work - // if one uses the same iterators (like slice ones) with both. - return from_iter_via_vec(iter.into_iter()); - - #[inline] - fn from_iter_via_vec<U>(iter: impl Iterator<Item = U>) -> VecDeque<U> { - Vec::from_iter(iter).into() - } + SpecFromIter::spec_from_iter(iter.into_iter()) } } @@ -2794,9 +2830,9 @@ impl<T, A: Allocator> From<Vec<T, A>> for VecDeque<T, A> { /// [`Vec<T>`]: crate::vec::Vec /// [`VecDeque<T>`]: crate::collections::VecDeque /// - /// In its current implementation, this is a very cheap - /// conversion. This isn't yet a guarantee though, and - /// shouldn't be relied on. + /// This conversion is guaranteed to run in *O*(1) time + /// and to not re-allocate the `Vec`'s buffer or allocate + /// any additional memory. #[inline] fn from(other: Vec<T, A>) -> Self { let (ptr, len, cap, alloc) = other.into_raw_parts_with_alloc(); diff --git a/library/alloc/src/collections/vec_deque/spec_from_iter.rs b/library/alloc/src/collections/vec_deque/spec_from_iter.rs new file mode 100644 index 000000000..7650492eb --- /dev/null +++ b/library/alloc/src/collections/vec_deque/spec_from_iter.rs @@ -0,0 +1,33 @@ +use super::{IntoIter, VecDeque}; + +/// Specialization trait used for `VecDeque::from_iter` +pub(super) trait SpecFromIter<T, I> { + fn spec_from_iter(iter: I) -> Self; +} + +impl<T, I> SpecFromIter<T, I> for VecDeque<T> +where + I: Iterator<Item = T>, +{ + default fn spec_from_iter(iterator: I) -> Self { + // Since converting is O(1) now, just re-use the `Vec` logic for + // anything where we can't do something extra-special for `VecDeque`, + // especially as that could save us some monomorphiziation work + // if one uses the same iterators (like slice ones) with both. + crate::vec::Vec::from_iter(iterator).into() + } +} + +impl<T> SpecFromIter<T, crate::vec::IntoIter<T>> for VecDeque<T> { + #[inline] + fn spec_from_iter(iterator: crate::vec::IntoIter<T>) -> Self { + iterator.into_vecdeque() + } +} + +impl<T> SpecFromIter<T, IntoIter<T>> for VecDeque<T> { + #[inline] + fn spec_from_iter(iterator: IntoIter<T>) -> Self { + iterator.into_vecdeque() + } +} diff --git a/library/alloc/src/collections/vec_deque/tests.rs b/library/alloc/src/collections/vec_deque/tests.rs index 220ad71be..205a8ff3c 100644 --- a/library/alloc/src/collections/vec_deque/tests.rs +++ b/library/alloc/src/collections/vec_deque/tests.rs @@ -749,6 +749,48 @@ fn test_drain() { } #[test] +fn issue_108453() { + let mut deque = VecDeque::with_capacity(10); + + deque.push_back(1u8); + deque.push_back(2); + deque.push_back(3); + + deque.push_front(10); + deque.push_front(9); + + deque.shrink_to(9); + + assert_eq!(deque.into_iter().collect::<Vec<_>>(), vec![9, 10, 1, 2, 3]); +} + +#[test] +fn test_shrink_to() { + // test deques with capacity 16 with all possible head positions, lengths and target capacities. + let cap = 16; + + for len in 0..cap { + for head in 0..cap { + let expected = (1..=len).collect::<VecDeque<_>>(); + + for target_cap in len..cap { + let mut deque = VecDeque::with_capacity(cap); + // currently, `with_capacity` always allocates the exact capacity if it's greater than 8. + assert_eq!(deque.capacity(), cap); + + // we can let the head point anywhere in the buffer since the deque is empty. + deque.head = head; + deque.extend(1..=len); + + deque.shrink_to(target_cap); + + assert_eq!(deque, expected); + } + } + } +} + +#[test] fn test_shrink_to_fit() { // This test checks that every single combination of head and tail position, // is tested. Capacity 15 should be large enough to cover every case. |