From a3a5d83e665d37ebffce94e0d5c6cdae5f2852e3 Mon Sep 17 00:00:00 2001 From: Stein Somers Date: Fri, 18 Feb 2022 15:21:56 +0100 Subject: Classify BinaryHeap & LinkedList unit tests as such --- library/alloc/src/collections/binary_heap.rs | 3 + library/alloc/src/collections/binary_heap/tests.rs | 489 +++++++++++++++ library/alloc/src/collections/linked_list/tests.rs | 695 ++++++++++++++++++++- library/alloc/tests/binary_heap.rs | 489 --------------- library/alloc/tests/lib.rs | 1 - library/alloc/tests/linked_list.rs | 683 -------------------- 6 files changed, 1179 insertions(+), 1181 deletions(-) create mode 100644 library/alloc/src/collections/binary_heap/tests.rs delete mode 100644 library/alloc/tests/binary_heap.rs diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap.rs index e6c3d38dab3..37fb901b463 100644 --- a/library/alloc/src/collections/binary_heap.rs +++ b/library/alloc/src/collections/binary_heap.rs @@ -155,6 +155,9 @@ use crate::vec::{self, AsIntoIter, Vec}; use super::SpecExtend; +#[cfg(test)] +mod tests; + /// A priority queue implemented with a binary heap. /// /// This will be a max-heap. diff --git a/library/alloc/src/collections/binary_heap/tests.rs b/library/alloc/src/collections/binary_heap/tests.rs new file mode 100644 index 00000000000..7c758dbb3ab --- /dev/null +++ b/library/alloc/src/collections/binary_heap/tests.rs @@ -0,0 +1,489 @@ +use super::*; +use crate::boxed::Box; +use std::iter::TrustedLen; +use std::panic::{catch_unwind, AssertUnwindSafe}; +use std::sync::atomic::{AtomicU32, Ordering}; + +#[test] +fn test_iterator() { + let data = vec![5, 9, 3]; + let iterout = [9, 5, 3]; + let heap = BinaryHeap::from(data); + let mut i = 0; + for el in &heap { + assert_eq!(*el, iterout[i]); + i += 1; + } +} + +#[test] +fn test_iter_rev_cloned_collect() { + let data = vec![5, 9, 3]; + let iterout = vec![3, 5, 9]; + let pq = BinaryHeap::from(data); + + let v: Vec<_> = pq.iter().rev().cloned().collect(); + assert_eq!(v, iterout); +} + +#[test] +fn test_into_iter_collect() { + let data = vec![5, 9, 3]; + let iterout = vec![9, 5, 3]; + let pq = BinaryHeap::from(data); + + let v: Vec<_> = pq.into_iter().collect(); + assert_eq!(v, iterout); +} + +#[test] +fn test_into_iter_size_hint() { + let data = vec![5, 9]; + let pq = BinaryHeap::from(data); + + let mut it = pq.into_iter(); + + assert_eq!(it.size_hint(), (2, Some(2))); + assert_eq!(it.next(), Some(9)); + + assert_eq!(it.size_hint(), (1, Some(1))); + assert_eq!(it.next(), Some(5)); + + assert_eq!(it.size_hint(), (0, Some(0))); + assert_eq!(it.next(), None); +} + +#[test] +fn test_into_iter_rev_collect() { + let data = vec![5, 9, 3]; + let iterout = vec![3, 5, 9]; + let pq = BinaryHeap::from(data); + + let v: Vec<_> = pq.into_iter().rev().collect(); + assert_eq!(v, iterout); +} + +#[test] +fn test_into_iter_sorted_collect() { + let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); + let it = heap.into_iter_sorted(); + let sorted = it.collect::>(); + assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]); +} + +#[test] +fn test_drain_sorted_collect() { + let mut heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); + let it = heap.drain_sorted(); + let sorted = it.collect::>(); + assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]); +} + +fn check_exact_size_iterator(len: usize, it: I) { + let mut it = it; + + for i in 0..it.len() { + let (lower, upper) = it.size_hint(); + assert_eq!(Some(lower), upper); + assert_eq!(lower, len - i); + assert_eq!(it.len(), len - i); + it.next(); + } + assert_eq!(it.len(), 0); + assert!(it.is_empty()); +} + +#[test] +fn test_exact_size_iterator() { + let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); + check_exact_size_iterator(heap.len(), heap.iter()); + check_exact_size_iterator(heap.len(), heap.clone().into_iter()); + check_exact_size_iterator(heap.len(), heap.clone().into_iter_sorted()); + check_exact_size_iterator(heap.len(), heap.clone().drain()); + check_exact_size_iterator(heap.len(), heap.clone().drain_sorted()); +} + +fn check_trusted_len(len: usize, it: I) { + let mut it = it; + for i in 0..len { + let (lower, upper) = it.size_hint(); + if upper.is_some() { + assert_eq!(Some(lower), upper); + assert_eq!(lower, len - i); + } + it.next(); + } +} + +#[test] +fn test_trusted_len() { + let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); + check_trusted_len(heap.len(), heap.clone().into_iter_sorted()); + check_trusted_len(heap.len(), heap.clone().drain_sorted()); +} + +#[test] +fn test_peek_and_pop() { + let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]; + let mut sorted = data.clone(); + sorted.sort(); + let mut heap = BinaryHeap::from(data); + while !heap.is_empty() { + assert_eq!(heap.peek().unwrap(), sorted.last().unwrap()); + assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap()); + } +} + +#[test] +fn test_peek_mut() { + let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]; + let mut heap = BinaryHeap::from(data); + assert_eq!(heap.peek(), Some(&10)); + { + let mut top = heap.peek_mut().unwrap(); + *top -= 2; + } + assert_eq!(heap.peek(), Some(&9)); +} + +#[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); + assert_eq!(heap.peek(), Some(&10)); + { + let mut top = heap.peek_mut().unwrap(); + *top -= 2; + assert_eq!(PeekMut::pop(top), 8); + } + assert_eq!(heap.peek(), Some(&9)); +} + +#[test] +fn test_push() { + let mut heap = BinaryHeap::from(vec![2, 4, 9]); + assert_eq!(heap.len(), 3); + assert!(*heap.peek().unwrap() == 9); + heap.push(11); + assert_eq!(heap.len(), 4); + assert!(*heap.peek().unwrap() == 11); + heap.push(5); + assert_eq!(heap.len(), 5); + assert!(*heap.peek().unwrap() == 11); + heap.push(27); + assert_eq!(heap.len(), 6); + assert!(*heap.peek().unwrap() == 27); + heap.push(3); + assert_eq!(heap.len(), 7); + assert!(*heap.peek().unwrap() == 27); + heap.push(103); + assert_eq!(heap.len(), 8); + assert!(*heap.peek().unwrap() == 103); +} + +#[test] +fn test_push_unique() { + let mut heap = BinaryHeap::>::from(vec![box 2, box 4, box 9]); + assert_eq!(heap.len(), 3); + assert!(**heap.peek().unwrap() == 9); + heap.push(box 11); + assert_eq!(heap.len(), 4); + assert!(**heap.peek().unwrap() == 11); + heap.push(box 5); + assert_eq!(heap.len(), 5); + assert!(**heap.peek().unwrap() == 11); + heap.push(box 27); + assert_eq!(heap.len(), 6); + assert!(**heap.peek().unwrap() == 27); + heap.push(box 3); + assert_eq!(heap.len(), 7); + assert!(**heap.peek().unwrap() == 27); + heap.push(box 103); + assert_eq!(heap.len(), 8); + assert!(**heap.peek().unwrap() == 103); +} + +fn check_to_vec(mut data: Vec) { + let heap = BinaryHeap::from(data.clone()); + let mut v = heap.clone().into_vec(); + v.sort(); + data.sort(); + + assert_eq!(v, data); + assert_eq!(heap.into_sorted_vec(), data); +} + +#[test] +fn test_to_vec() { + check_to_vec(vec![]); + check_to_vec(vec![5]); + check_to_vec(vec![3, 2]); + check_to_vec(vec![2, 3]); + check_to_vec(vec![5, 1, 2]); + check_to_vec(vec![1, 100, 2, 3]); + check_to_vec(vec![1, 3, 5, 7, 9, 2, 4, 6, 8, 0]); + check_to_vec(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); + check_to_vec(vec![9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0]); + check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); + check_to_vec(vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]); + check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2]); + check_to_vec(vec![5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]); +} + +#[test] +fn test_in_place_iterator_specialization() { + let src: Vec = vec![1, 2, 3]; + let src_ptr = src.as_ptr(); + let heap: BinaryHeap<_> = src.into_iter().map(std::convert::identity).collect(); + let heap_ptr = heap.iter().next().unwrap() as *const usize; + assert_eq!(src_ptr, heap_ptr); + let sink: Vec<_> = heap.into_iter().map(std::convert::identity).collect(); + let sink_ptr = sink.as_ptr(); + assert_eq!(heap_ptr, sink_ptr); +} + +#[test] +fn test_empty_pop() { + let mut heap = BinaryHeap::::new(); + assert!(heap.pop().is_none()); +} + +#[test] +fn test_empty_peek() { + let empty = BinaryHeap::::new(); + assert!(empty.peek().is_none()); +} + +#[test] +fn test_empty_peek_mut() { + let mut empty = BinaryHeap::::new(); + assert!(empty.peek_mut().is_none()); +} + +#[test] +fn test_from_iter() { + let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1]; + + let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect(); + + for &x in &xs { + assert_eq!(q.pop().unwrap(), x); + } +} + +#[test] +fn test_drain() { + let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect(); + + assert_eq!(q.drain().take(5).count(), 5); + + assert!(q.is_empty()); +} + +#[test] +fn test_drain_sorted() { + let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect(); + + assert_eq!(q.drain_sorted().take(5).collect::>(), vec![9, 8, 7, 6, 5]); + + assert!(q.is_empty()); +} + +#[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 mut q = BinaryHeap::from(vec![ + D(0, false), + D(1, false), + D(2, false), + D(3, true), + D(4, false), + D(5, false), + ]); + + catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).ok(); + + assert_eq!(DROPS.load(Ordering::SeqCst), 6); +} + +#[test] +fn test_extend_ref() { + let mut a = BinaryHeap::new(); + a.push(1); + a.push(2); + + a.extend(&[3, 4, 5]); + + assert_eq!(a.len(), 5); + assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]); + + let mut a = BinaryHeap::new(); + a.push(1); + a.push(2); + let mut b = BinaryHeap::new(); + b.push(3); + b.push(4); + b.push(5); + + a.extend(&b); + + assert_eq!(a.len(), 5); + assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]); +} + +#[test] +fn test_append() { + let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]); + let mut b = BinaryHeap::from(vec![-20, 5, 43]); + + a.append(&mut b); + + assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]); + assert!(b.is_empty()); +} + +#[test] +fn test_append_to_empty() { + let mut a = BinaryHeap::new(); + let mut b = BinaryHeap::from(vec![-20, 5, 43]); + + a.append(&mut b); + + assert_eq!(a.into_sorted_vec(), [-20, 5, 43]); + assert!(b.is_empty()); +} + +#[test] +fn test_extend_specialization() { + let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]); + let b = BinaryHeap::from(vec![-20, 5, 43]); + + a.extend(b); + + assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]); +} + +#[allow(dead_code)] +fn assert_covariance() { + fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> { + d + } +} + +#[test] +fn test_retain() { + let mut a = BinaryHeap::from(vec![100, 10, 50, 1, 2, 20, 30]); + a.retain(|&x| x != 2); + + // Check that 20 moved into 10's place. + assert_eq!(a.clone().into_vec(), [100, 20, 50, 1, 10, 30]); + + a.retain(|_| true); + + assert_eq!(a.clone().into_vec(), [100, 20, 50, 1, 10, 30]); + + a.retain(|&x| x < 50); + + assert_eq!(a.clone().into_vec(), [30, 20, 10, 1]); + + a.retain(|_| false); + + assert!(a.is_empty()); +} + +// old binaryheap failed this test +// +// Integrity means that all elements are present after a comparison panics, +// even if the order might not be correct. +// +// Destructors must be called exactly once per element. +// FIXME: re-enable emscripten once it can unwind again +#[test] +#[cfg(not(target_os = "emscripten"))] +fn panic_safe() { + use rand::{seq::SliceRandom, thread_rng}; + use std::cmp; + use std::panic::{self, AssertUnwindSafe}; + use std::sync::atomic::{AtomicUsize, Ordering}; + + static DROP_COUNTER: AtomicUsize = AtomicUsize::new(0); + + #[derive(Eq, PartialEq, Ord, Clone, Debug)] + struct PanicOrd(T, bool); + + impl Drop for PanicOrd { + fn drop(&mut self) { + // update global drop count + DROP_COUNTER.fetch_add(1, Ordering::SeqCst); + } + } + + impl PartialOrd for PanicOrd { + fn partial_cmp(&self, other: &Self) -> Option { + if self.1 || other.1 { + panic!("Panicking comparison"); + } + self.0.partial_cmp(&other.0) + } + } + let mut rng = thread_rng(); + const DATASZ: usize = 32; + // Miri is too slow + let ntest = if cfg!(miri) { 1 } else { 10 }; + + // don't use 0 in the data -- we want to catch the zeroed-out case. + let data = (1..=DATASZ).collect::>(); + + // since it's a fuzzy test, run several tries. + for _ in 0..ntest { + for i in 1..=DATASZ { + DROP_COUNTER.store(0, Ordering::SeqCst); + + let mut panic_ords: Vec<_> = + data.iter().filter(|&&x| x != i).map(|&x| PanicOrd(x, false)).collect(); + let panic_item = PanicOrd(i, true); + + // heapify the sane items + panic_ords.shuffle(&mut rng); + let mut heap = BinaryHeap::from(panic_ords); + let inner_data; + + { + // push the panicking item to the heap and catch the panic + let thread_result = { + let mut heap_ref = AssertUnwindSafe(&mut heap); + panic::catch_unwind(move || { + heap_ref.push(panic_item); + }) + }; + assert!(thread_result.is_err()); + + // Assert no elements were dropped + let drops = DROP_COUNTER.load(Ordering::SeqCst); + assert!(drops == 0, "Must not drop items. drops={}", drops); + inner_data = heap.clone().into_vec(); + drop(heap); + } + let drops = DROP_COUNTER.load(Ordering::SeqCst); + assert_eq!(drops, DATASZ); + + let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::>(); + data_sorted.sort(); + assert_eq!(data_sorted, data); + } + } +} diff --git a/library/alloc/src/collections/linked_list/tests.rs b/library/alloc/src/collections/linked_list/tests.rs index 5a65ed7a962..38c702aa387 100644 --- a/library/alloc/src/collections/linked_list/tests.rs +++ b/library/alloc/src/collections/linked_list/tests.rs @@ -1,10 +1,55 @@ use super::*; +use crate::vec::Vec; +use std::panic::{catch_unwind, AssertUnwindSafe}; use std::thread; -use std::vec::Vec; use rand::{thread_rng, RngCore}; +#[test] +fn test_basic() { + let mut m = LinkedList::>::new(); + assert_eq!(m.pop_front(), None); + assert_eq!(m.pop_back(), None); + assert_eq!(m.pop_front(), None); + m.push_front(box 1); + assert_eq!(m.pop_front(), Some(box 1)); + m.push_back(box 2); + m.push_back(box 3); + assert_eq!(m.len(), 2); + assert_eq!(m.pop_front(), Some(box 2)); + assert_eq!(m.pop_front(), Some(box 3)); + assert_eq!(m.len(), 0); + assert_eq!(m.pop_front(), None); + m.push_back(box 1); + m.push_back(box 3); + m.push_back(box 5); + m.push_back(box 7); + assert_eq!(m.pop_front(), Some(box 1)); + + let mut n = LinkedList::new(); + n.push_front(2); + n.push_front(3); + { + assert_eq!(n.front().unwrap(), &3); + let x = n.front_mut().unwrap(); + assert_eq!(*x, 3); + *x = 0; + } + { + assert_eq!(n.back().unwrap(), &2); + let y = n.back_mut().unwrap(); + assert_eq!(*y, 2); + *y = 1; + } + assert_eq!(n.pop_front(), Some(0)); + assert_eq!(n.pop_front(), Some(1)); +} + +fn generate_test() -> LinkedList { + list_from(&[0, 1, 2, 3, 4, 5, 6]) +} + fn list_from(v: &[T]) -> LinkedList { v.iter().cloned().collect() } @@ -110,6 +155,123 @@ fn test_append() { check_links(&n); } +#[test] +fn test_iterator() { + let m = generate_test(); + for (i, elt) in m.iter().enumerate() { + assert_eq!(i as i32, *elt); + } + let mut n = LinkedList::new(); + assert_eq!(n.iter().next(), None); + n.push_front(4); + let mut it = n.iter(); + assert_eq!(it.size_hint(), (1, Some(1))); + assert_eq!(it.next().unwrap(), &4); + assert_eq!(it.size_hint(), (0, Some(0))); + assert_eq!(it.next(), None); +} + +#[test] +fn test_iterator_clone() { + let mut n = LinkedList::new(); + n.push_back(2); + n.push_back(3); + n.push_back(4); + let mut it = n.iter(); + it.next(); + let mut jt = it.clone(); + assert_eq!(it.next(), jt.next()); + assert_eq!(it.next_back(), jt.next_back()); + assert_eq!(it.next(), jt.next()); +} + +#[test] +fn test_iterator_double_end() { + let mut n = LinkedList::new(); + assert_eq!(n.iter().next(), None); + n.push_front(4); + n.push_front(5); + n.push_front(6); + let mut it = n.iter(); + assert_eq!(it.size_hint(), (3, Some(3))); + assert_eq!(it.next().unwrap(), &6); + assert_eq!(it.size_hint(), (2, Some(2))); + assert_eq!(it.next_back().unwrap(), &4); + assert_eq!(it.size_hint(), (1, Some(1))); + assert_eq!(it.next_back().unwrap(), &5); + assert_eq!(it.next_back(), None); + assert_eq!(it.next(), None); +} + +#[test] +fn test_rev_iter() { + let m = generate_test(); + for (i, elt) in m.iter().rev().enumerate() { + assert_eq!((6 - i) as i32, *elt); + } + let mut n = LinkedList::new(); + assert_eq!(n.iter().rev().next(), None); + n.push_front(4); + let mut it = n.iter().rev(); + assert_eq!(it.size_hint(), (1, Some(1))); + assert_eq!(it.next().unwrap(), &4); + assert_eq!(it.size_hint(), (0, Some(0))); + assert_eq!(it.next(), None); +} + +#[test] +fn test_mut_iter() { + let mut m = generate_test(); + let mut len = m.len(); + for (i, elt) in m.iter_mut().enumerate() { + assert_eq!(i as i32, *elt); + len -= 1; + } + assert_eq!(len, 0); + let mut n = LinkedList::new(); + assert!(n.iter_mut().next().is_none()); + n.push_front(4); + n.push_back(5); + let mut it = n.iter_mut(); + assert_eq!(it.size_hint(), (2, Some(2))); + assert!(it.next().is_some()); + assert!(it.next().is_some()); + assert_eq!(it.size_hint(), (0, Some(0))); + assert!(it.next().is_none()); +} + +#[test] +fn test_iterator_mut_double_end() { + let mut n = LinkedList::new(); + assert!(n.iter_mut().next_back().is_none()); + n.push_front(4); + n.push_front(5); + n.push_front(6); + let mut it = n.iter_mut(); + assert_eq!(it.size_hint(), (3, Some(3))); + assert_eq!(*it.next().unwrap(), 6); + assert_eq!(it.size_hint(), (2, Some(2))); + assert_eq!(*it.next_back().unwrap(), 4); + assert_eq!(it.size_hint(), (1, Some(1))); + assert_eq!(*it.next_back().unwrap(), 5); + assert!(it.next_back().is_none()); + assert!(it.next().is_none()); +} + +#[test] +fn test_mut_rev_iter() { + let mut m = generate_test(); + for (i, elt) in m.iter_mut().rev().enumerate() { + assert_eq!((6 - i) as i32, *elt); + } + let mut n = LinkedList::new(); + assert!(n.iter_mut().rev().next().is_none()); + n.push_front(4); + let mut it = n.iter_mut().rev(); + assert!(it.next().is_some()); + assert!(it.next().is_none()); +} + #[test] fn test_clone_from() { // Short cloned from long @@ -168,13 +330,60 @@ fn test_send() { } #[test] -fn test_fuzz() { - for _ in 0..25 { - fuzz_test(3); - fuzz_test(16); - #[cfg(not(miri))] // Miri is too slow - fuzz_test(189); - } +fn test_eq() { + let mut n = list_from(&[]); + let mut m = list_from(&[]); + assert!(n == m); + n.push_front(1); + assert!(n != m); + m.push_back(1); + assert!(n == m); + + let n = list_from(&[2, 3, 4]); + let m = list_from(&[1, 2, 3]); + assert!(n != m); +} + +#[test] +fn test_ord() { + let n = list_from(&[]); + let m = list_from(&[1, 2, 3]); + assert!(n < m); + assert!(m > n); + assert!(n <= n); + assert!(n >= n); +} + +#[test] +fn test_ord_nan() { + let nan = 0.0f64 / 0.0; + let n = list_from(&[nan]); + let m = list_from(&[nan]); + assert!(!(n < m)); + assert!(!(n > m)); + assert!(!(n <= m)); + assert!(!(n >= m)); + + let n = list_from(&[nan]); + let one = list_from(&[1.0f64]); + assert!(!(n < one)); + assert!(!(n > one)); + assert!(!(n <= one)); + assert!(!(n >= one)); + + let u = list_from(&[1.0f64, 2.0, nan]); + let v = list_from(&[1.0f64, 2.0, 3.0]); + assert!(!(u < v)); + assert!(!(u > v)); + assert!(!(u <= v)); + assert!(!(u >= v)); + + let s = list_from(&[1.0f64, 2.0, 4.0, 2.0]); + let t = list_from(&[1.0f64, 2.0, 3.0, 2.0]); + assert!(!(s < t)); + assert!(s > one); + assert!(!(s <= one)); + assert!(s >= one); } #[test] @@ -215,6 +424,62 @@ fn test_split_off() { } } +#[test] +fn test_split_off_2() { + // singleton + { + let mut m = LinkedList::new(); + m.push_back(1); + + let p = m.split_off(0); + assert_eq!(m.len(), 0); + assert_eq!(p.len(), 1); + assert_eq!(p.back(), Some(&1)); + assert_eq!(p.front(), Some(&1)); + } + + // not singleton, forwards + { + let u = vec![1, 2, 3, 4, 5]; + let mut m = list_from(&u); + let mut n = m.split_off(2); + assert_eq!(m.len(), 2); + assert_eq!(n.len(), 3); + for elt in 1..3 { + assert_eq!(m.pop_front(), Some(elt)); + } + for elt in 3..6 { + assert_eq!(n.pop_front(), Some(elt)); + } + } + // not singleton, backwards + { + let u = vec![1, 2, 3, 4, 5]; + let mut m = list_from(&u); + let mut n = m.split_off(4); + assert_eq!(m.len(), 4); + assert_eq!(n.len(), 1); + for elt in 1..5 { + assert_eq!(m.pop_front(), Some(elt)); + } + for elt in 5..6 { + assert_eq!(n.pop_front(), Some(elt)); + } + } + + // no-op on the last index + { + let mut m = LinkedList::new(); + m.push_back(1); + + let p = m.split_off(1); + assert_eq!(m.len(), 1); + assert_eq!(p.len(), 0); + assert_eq!(m.back(), Some(&1)); + assert_eq!(m.front(), Some(&1)); + } +} + fn fuzz_test(sz: i32) { let mut m: LinkedList<_> = LinkedList::new(); let mut v = vec![]; @@ -253,6 +518,25 @@ fn fuzz_test(sz: i32) { assert_eq!(i, v.len()); } +#[test] +fn test_fuzz() { + for _ in 0..25 { + fuzz_test(3); + fuzz_test(16); + #[cfg(not(miri))] // Miri is too slow + fuzz_test(189); + } +} + +#[test] +fn test_show() { + let list: LinkedList<_> = (0..10).collect(); + assert_eq!(format!("{list:?}"), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"); + + let list: LinkedList<_> = ["just", "one", "test", "more"].into_iter().collect(); + assert_eq!(format!("{list:?}"), "[\"just\", \"one\", \"test\", \"more\"]"); +} + #[test] fn drain_filter_test() { let mut m: LinkedList = LinkedList::new(); @@ -475,3 +759,398 @@ fn test_cursor_pop_front_back() { assert_eq!(c.current(), None); assert_eq!(c.index, 2); } + +#[test] +fn test_extend_ref() { + let mut a = LinkedList::new(); + a.push_back(1); + + a.extend(&[2, 3, 4]); + + assert_eq!(a.len(), 4); + assert_eq!(a, list_from(&[1, 2, 3, 4])); + + let mut b = LinkedList::new(); + b.push_back(5); + b.push_back(6); + a.extend(&b); + + assert_eq!(a.len(), 6); + assert_eq!(a, list_from(&[1, 2, 3, 4, 5, 6])); +} + +#[test] +fn test_extend() { + let mut a = LinkedList::new(); + a.push_back(1); + a.extend(vec![2, 3, 4]); // uses iterator + + assert_eq!(a.len(), 4); + assert!(a.iter().eq(&[1, 2, 3, 4])); + + let b: LinkedList<_> = [5, 6, 7].into_iter().collect(); + a.extend(b); // specializes to `append` + + assert_eq!(a.len(), 7); + assert!(a.iter().eq(&[1, 2, 3, 4, 5, 6, 7])); +} + +#[test] +fn test_contains() { + let mut l = LinkedList::new(); + l.extend(&[2, 3, 4]); + + assert!(l.contains(&3)); + assert!(!l.contains(&1)); + + l.clear(); + + assert!(!l.contains(&3)); +} + +#[test] +fn drain_filter_empty() { + let mut list: LinkedList = LinkedList::new(); + + { + let mut iter = list.drain_filter(|_| true); + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + assert_eq!(iter.size_hint(), (0, Some(0))); + } + + assert_eq!(list.len(), 0); + assert_eq!(list.into_iter().collect::>(), vec![]); +} + +#[test] +fn drain_filter_zst() { + let mut list: LinkedList<_> = [(), (), (), (), ()].into_iter().collect(); + let initial_len = list.len(); + let mut count = 0; + + { + let mut iter = list.drain_filter(|_| true); + assert_eq!(iter.size_hint(), (0, Some(initial_len))); + while let Some(_) = iter.next() { + count += 1; + assert_eq!(iter.size_hint(), (0, Some(initial_len - count))); + } + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + assert_eq!(iter.size_hint(), (0, Some(0))); + } + + assert_eq!(count, initial_len); + assert_eq!(list.len(), 0); + assert_eq!(list.into_iter().collect::>(), vec![]); +} + +#[test] +fn drain_filter_false() { + let mut list: LinkedList<_> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); + + let initial_len = list.len(); + let mut count = 0; + + { + let mut iter = list.drain_filter(|_| false); + assert_eq!(iter.size_hint(), (0, Some(initial_len))); + for _ in iter.by_ref() { + count += 1; + } + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + assert_eq!(iter.size_hint(), (0, Some(0))); + } + + assert_eq!(count, 0); + assert_eq!(list.len(), initial_len); + assert_eq!(list.into_iter().collect::>(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); +} + +#[test] +fn drain_filter_true() { + let mut list: LinkedList<_> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); + + let initial_len = list.len(); + let mut count = 0; + + { + let mut iter = list.drain_filter(|_| true); + assert_eq!(iter.size_hint(), (0, Some(initial_len))); + while let Some(_) = iter.next() { + count += 1; + assert_eq!(iter.size_hint(), (0, Some(initial_len - count))); + } + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + assert_eq!(iter.size_hint(), (0, Some(0))); + } + + assert_eq!(count, initial_len); + assert_eq!(list.len(), 0); + assert_eq!(list.into_iter().collect::>(), vec![]); +} + +#[test] +fn drain_filter_complex() { + { + // [+xxx++++++xxxxx++++x+x++] + let mut list = [ + 1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, + 39, + ] + .into_iter() + .collect::>(); + + let removed = list.drain_filter(|x| *x % 2 == 0).collect::>(); + assert_eq!(removed.len(), 10); + assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]); + + assert_eq!(list.len(), 14); + assert_eq!( + list.into_iter().collect::>(), + vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39] + ); + } + + { + // [xxx++++++xxxxx++++x+x++] + let mut list = + [2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39] + .into_iter() + .collect::>(); + + let removed = list.drain_filter(|x| *x % 2 == 0).collect::>(); + assert_eq!(removed.len(), 10); + assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]); + + assert_eq!(list.len(), 13); + assert_eq!( + list.into_iter().collect::>(), + vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39] + ); + } + + { + // [xxx++++++xxxxx++++x+x] + let mut list = + [2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36] + .into_iter() + .collect::>(); + + let removed = list.drain_filter(|x| *x % 2 == 0).collect::>(); + assert_eq!(removed.len(), 10); + assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]); + + assert_eq!(list.len(), 11); + assert_eq!( + list.into_iter().collect::>(), + vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35] + ); + } + + { + // [xxxxxxxxxx+++++++++++] + let mut list = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19] + .into_iter() + .collect::>(); + + let removed = list.drain_filter(|x| *x % 2 == 0).collect::>(); + assert_eq!(removed.len(), 10); + assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]); + + assert_eq!(list.len(), 10); + assert_eq!(list.into_iter().collect::>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]); + } + + { + // [+++++++++++xxxxxxxxxx] + let mut list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20] + .into_iter() + .collect::>(); + + let removed = list.drain_filter(|x| *x % 2 == 0).collect::>(); + assert_eq!(removed.len(), 10); + assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]); + + assert_eq!(list.len(), 10); + assert_eq!(list.into_iter().collect::>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]); + } +} + +#[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 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); + assert!(q.is_empty()); +} + +#[test] +fn drain_filter_pred_panic_leak() { + static mut DROPS: i32 = 0; + + #[derive(Debug)] + struct D(u32); + + impl Drop for D { + fn drop(&mut self) { + unsafe { + DROPS += 1; + } + } + } + + let mut q = LinkedList::new(); + q.push_back(D(3)); + q.push_back(D(4)); + q.push_back(D(5)); + q.push_back(D(6)); + q.push_back(D(7)); + q.push_front(D(2)); + q.push_front(D(1)); + q.push_front(D(0)); + + catch_unwind(AssertUnwindSafe(|| { + drop(q.drain_filter(|item| if item.0 >= 2 { panic!() } else { true })) + })) + .ok(); + + assert_eq!(unsafe { DROPS }, 2); // 0 and 1 + assert_eq!(q.len(), 6); +} + +#[test] +fn test_drop() { + static mut DROPS: i32 = 0; + struct Elem; + impl Drop for Elem { + fn drop(&mut self) { + unsafe { + DROPS += 1; + } + } + } + + let mut ring = LinkedList::new(); + ring.push_back(Elem); + ring.push_front(Elem); + ring.push_back(Elem); + ring.push_front(Elem); + drop(ring); + + assert_eq!(unsafe { DROPS }, 4); +} + +#[test] +fn test_drop_with_pop() { + static mut DROPS: i32 = 0; + struct Elem; + impl Drop for Elem { + fn drop(&mut self) { + unsafe { + DROPS += 1; + } + } + } + + let mut ring = LinkedList::new(); + ring.push_back(Elem); + ring.push_front(Elem); + ring.push_back(Elem); + ring.push_front(Elem); + + drop(ring.pop_back()); + drop(ring.pop_front()); + assert_eq!(unsafe { DROPS }, 2); + + drop(ring); + assert_eq!(unsafe { DROPS }, 4); +} + +#[test] +fn test_drop_clear() { + static mut DROPS: i32 = 0; + struct Elem; + impl Drop for Elem { + fn drop(&mut self) { + unsafe { + DROPS += 1; + } + } + } + + let mut ring = LinkedList::new(); + ring.push_back(Elem); + ring.push_front(Elem); + ring.push_back(Elem); + ring.push_front(Elem); + ring.clear(); + assert_eq!(unsafe { DROPS }, 4); + + drop(ring); + assert_eq!(unsafe { DROPS }, 4); +} + +#[test] +fn test_drop_panic() { + 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 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(false)); + q.push_front(D(true)); + + catch_unwind(move || drop(q)).ok(); + + assert_eq!(unsafe { DROPS }, 8); +} diff --git a/library/alloc/tests/binary_heap.rs b/library/alloc/tests/binary_heap.rs deleted file mode 100644 index f32118bb563..00000000000 --- a/library/alloc/tests/binary_heap.rs +++ /dev/null @@ -1,489 +0,0 @@ -use std::collections::binary_heap::{Drain, PeekMut}; -use std::collections::BinaryHeap; -use std::iter::TrustedLen; -use std::panic::{catch_unwind, AssertUnwindSafe}; -use std::sync::atomic::{AtomicU32, Ordering}; - -#[test] -fn test_iterator() { - let data = vec![5, 9, 3]; - let iterout = [9, 5, 3]; - let heap = BinaryHeap::from(data); - let mut i = 0; - for el in &heap { - assert_eq!(*el, iterout[i]); - i += 1; - } -} - -#[test] -fn test_iter_rev_cloned_collect() { - let data = vec![5, 9, 3]; - let iterout = vec![3, 5, 9]; - let pq = BinaryHeap::from(data); - - let v: Vec<_> = pq.iter().rev().cloned().collect(); - assert_eq!(v, iterout); -} - -#[test] -fn test_into_iter_collect() { - let data = vec![5, 9, 3]; - let iterout = vec![9, 5, 3]; - let pq = BinaryHeap::from(data); - - let v: Vec<_> = pq.into_iter().collect(); - assert_eq!(v, iterout); -} - -#[test] -fn test_into_iter_size_hint() { - let data = vec![5, 9]; - let pq = BinaryHeap::from(data); - - let mut it = pq.into_iter(); - - assert_eq!(it.size_hint(), (2, Some(2))); - assert_eq!(it.next(), Some(9)); - - assert_eq!(it.size_hint(), (1, Some(1))); - assert_eq!(it.next(), Some(5)); - - assert_eq!(it.size_hint(), (0, Some(0))); - assert_eq!(it.next(), None); -} - -#[test] -fn test_into_iter_rev_collect() { - let data = vec![5, 9, 3]; - let iterout = vec![3, 5, 9]; - let pq = BinaryHeap::from(data); - - let v: Vec<_> = pq.into_iter().rev().collect(); - assert_eq!(v, iterout); -} - -#[test] -fn test_into_iter_sorted_collect() { - let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); - let it = heap.into_iter_sorted(); - let sorted = it.collect::>(); - assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]); -} - -#[test] -fn test_drain_sorted_collect() { - let mut heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); - let it = heap.drain_sorted(); - let sorted = it.collect::>(); - assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]); -} - -fn check_exact_size_iterator(len: usize, it: I) { - let mut it = it; - - for i in 0..it.len() { - let (lower, upper) = it.size_hint(); - assert_eq!(Some(lower), upper); - assert_eq!(lower, len - i); - assert_eq!(it.len(), len - i); - it.next(); - } - assert_eq!(it.len(), 0); - assert!(it.is_empty()); -} - -#[test] -fn test_exact_size_iterator() { - let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); - check_exact_size_iterator(heap.len(), heap.iter()); - check_exact_size_iterator(heap.len(), heap.clone().into_iter()); - check_exact_size_iterator(heap.len(), heap.clone().into_iter_sorted()); - check_exact_size_iterator(heap.len(), heap.clone().drain()); - check_exact_size_iterator(heap.len(), heap.clone().drain_sorted()); -} - -fn check_trusted_len(len: usize, it: I) { - let mut it = it; - for i in 0..len { - let (lower, upper) = it.size_hint(); - if upper.is_some() { - assert_eq!(Some(lower), upper); - assert_eq!(lower, len - i); - } - it.next(); - } -} - -#[test] -fn test_trusted_len() { - let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); - check_trusted_len(heap.len(), heap.clone().into_iter_sorted()); - check_trusted_len(heap.len(), heap.clone().drain_sorted()); -} - -#[test] -fn test_peek_and_pop() { - let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]; - let mut sorted = data.clone(); - sorted.sort(); - let mut heap = BinaryHeap::from(data); - while !heap.is_empty() { - assert_eq!(heap.peek().unwrap(), sorted.last().unwrap()); - assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap()); - } -} - -#[test] -fn test_peek_mut() { - let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]; - let mut heap = BinaryHeap::from(data); - assert_eq!(heap.peek(), Some(&10)); - { - let mut top = heap.peek_mut().unwrap(); - *top -= 2; - } - assert_eq!(heap.peek(), Some(&9)); -} - -#[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); - assert_eq!(heap.peek(), Some(&10)); - { - let mut top = heap.peek_mut().unwrap(); - *top -= 2; - assert_eq!(PeekMut::pop(top), 8); - } - assert_eq!(heap.peek(), Some(&9)); -} - -#[test] -fn test_push() { - let mut heap = BinaryHeap::from(vec![2, 4, 9]); - assert_eq!(heap.len(), 3); - assert!(*heap.peek().unwrap() == 9); - heap.push(11); - assert_eq!(heap.len(), 4); - assert!(*heap.peek().unwrap() == 11); - heap.push(5); - assert_eq!(heap.len(), 5); - assert!(*heap.peek().unwrap() == 11); - heap.push(27); - assert_eq!(heap.len(), 6); - assert!(*heap.peek().unwrap() == 27); - heap.push(3); - assert_eq!(heap.len(), 7); - assert!(*heap.peek().unwrap() == 27); - heap.push(103); - assert_eq!(heap.len(), 8); - assert!(*heap.peek().unwrap() == 103); -} - -#[test] -fn test_push_unique() { - let mut heap = BinaryHeap::>::from(vec![box 2, box 4, box 9]); - assert_eq!(heap.len(), 3); - assert!(**heap.peek().unwrap() == 9); - heap.push(box 11); - assert_eq!(heap.len(), 4); - assert!(**heap.peek().unwrap() == 11); - heap.push(box 5); - assert_eq!(heap.len(), 5); - assert!(**heap.peek().unwrap() == 11); - heap.push(box 27); - assert_eq!(heap.len(), 6); - assert!(**heap.peek().unwrap() == 27); - heap.push(box 3); - assert_eq!(heap.len(), 7); - assert!(**heap.peek().unwrap() == 27); - heap.push(box 103); - assert_eq!(heap.len(), 8); - assert!(**heap.peek().unwrap() == 103); -} - -fn check_to_vec(mut data: Vec) { - let heap = BinaryHeap::from(data.clone()); - let mut v = heap.clone().into_vec(); - v.sort(); - data.sort(); - - assert_eq!(v, data); - assert_eq!(heap.into_sorted_vec(), data); -} - -#[test] -fn test_to_vec() { - check_to_vec(vec![]); - check_to_vec(vec![5]); - check_to_vec(vec![3, 2]); - check_to_vec(vec![2, 3]); - check_to_vec(vec![5, 1, 2]); - check_to_vec(vec![1, 100, 2, 3]); - check_to_vec(vec![1, 3, 5, 7, 9, 2, 4, 6, 8, 0]); - check_to_vec(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); - check_to_vec(vec![9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0]); - check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); - check_to_vec(vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]); - check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2]); - check_to_vec(vec![5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]); -} - -#[test] -fn test_in_place_iterator_specialization() { - let src: Vec = vec![1, 2, 3]; - let src_ptr = src.as_ptr(); - let heap: BinaryHeap<_> = src.into_iter().map(std::convert::identity).collect(); - let heap_ptr = heap.iter().next().unwrap() as *const usize; - assert_eq!(src_ptr, heap_ptr); - let sink: Vec<_> = heap.into_iter().map(std::convert::identity).collect(); - let sink_ptr = sink.as_ptr(); - assert_eq!(heap_ptr, sink_ptr); -} - -#[test] -fn test_empty_pop() { - let mut heap = BinaryHeap::::new(); - assert!(heap.pop().is_none()); -} - -#[test] -fn test_empty_peek() { - let empty = BinaryHeap::::new(); - assert!(empty.peek().is_none()); -} - -#[test] -fn test_empty_peek_mut() { - let mut empty = BinaryHeap::::new(); - assert!(empty.peek_mut().is_none()); -} - -#[test] -fn test_from_iter() { - let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1]; - - let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect(); - - for &x in &xs { - assert_eq!(q.pop().unwrap(), x); - } -} - -#[test] -fn test_drain() { - let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect(); - - assert_eq!(q.drain().take(5).count(), 5); - - assert!(q.is_empty()); -} - -#[test] -fn test_drain_sorted() { - let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect(); - - assert_eq!(q.drain_sorted().take(5).collect::>(), vec![9, 8, 7, 6, 5]); - - assert!(q.is_empty()); -} - -#[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 mut q = BinaryHeap::from(vec![ - D(0, false), - D(1, false), - D(2, false), - D(3, true), - D(4, false), - D(5, false), - ]); - - catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).ok(); - - assert_eq!(DROPS.load(Ordering::SeqCst), 6); -} - -#[test] -fn test_extend_ref() { - let mut a = BinaryHeap::new(); - a.push(1); - a.push(2); - - a.extend(&[3, 4, 5]); - - assert_eq!(a.len(), 5); - assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]); - - let mut a = BinaryHeap::new(); - a.push(1); - a.push(2); - let mut b = BinaryHeap::new(); - b.push(3); - b.push(4); - b.push(5); - - a.extend(&b); - - assert_eq!(a.len(), 5); - assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]); -} - -#[test] -fn test_append() { - let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]); - let mut b = BinaryHeap::from(vec![-20, 5, 43]); - - a.append(&mut b); - - assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]); - assert!(b.is_empty()); -} - -#[test] -fn test_append_to_empty() { - let mut a = BinaryHeap::new(); - let mut b = BinaryHeap::from(vec![-20, 5, 43]); - - a.append(&mut b); - - assert_eq!(a.into_sorted_vec(), [-20, 5, 43]); - assert!(b.is_empty()); -} - -#[test] -fn test_extend_specialization() { - let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]); - let b = BinaryHeap::from(vec![-20, 5, 43]); - - a.extend(b); - - assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]); -} - -#[allow(dead_code)] -fn assert_covariance() { - fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> { - d - } -} - -#[test] -fn test_retain() { - let mut a = BinaryHeap::from(vec![100, 10, 50, 1, 2, 20, 30]); - a.retain(|&x| x != 2); - - // Check that 20 moved into 10's place. - assert_eq!(a.clone().into_vec(), [100, 20, 50, 1, 10, 30]); - - a.retain(|_| true); - - assert_eq!(a.clone().into_vec(), [100, 20, 50, 1, 10, 30]); - - a.retain(|&x| x < 50); - - assert_eq!(a.clone().into_vec(), [30, 20, 10, 1]); - - a.retain(|_| false); - - assert!(a.is_empty()); -} - -// old binaryheap failed this test -// -// Integrity means that all elements are present after a comparison panics, -// even if the order might not be correct. -// -// Destructors must be called exactly once per element. -// FIXME: re-enable emscripten once it can unwind again -#[test] -#[cfg(not(target_os = "emscripten"))] -fn panic_safe() { - use rand::{seq::SliceRandom, thread_rng}; - use std::cmp; - use std::panic::{self, AssertUnwindSafe}; - use std::sync::atomic::{AtomicUsize, Ordering}; - - static DROP_COUNTER: AtomicUsize = AtomicUsize::new(0); - - #[derive(Eq, PartialEq, Ord, Clone, Debug)] - struct PanicOrd(T, bool); - - impl Drop for PanicOrd { - fn drop(&mut self) { - // update global drop count - DROP_COUNTER.fetch_add(1, Ordering::SeqCst); - } - } - - impl PartialOrd for PanicOrd { - fn partial_cmp(&self, other: &Self) -> Option { - if self.1 || other.1 { - panic!("Panicking comparison"); - } - self.0.partial_cmp(&other.0) - } - } - let mut rng = thread_rng(); - const DATASZ: usize = 32; - // Miri is too slow - let ntest = if cfg!(miri) { 1 } else { 10 }; - - // don't use 0 in the data -- we want to catch the zeroed-out case. - let data = (1..=DATASZ).collect::>(); - - // since it's a fuzzy test, run several tries. - for _ in 0..ntest { - for i in 1..=DATASZ { - DROP_COUNTER.store(0, Ordering::SeqCst); - - let mut panic_ords: Vec<_> = - data.iter().filter(|&&x| x != i).map(|&x| PanicOrd(x, false)).collect(); - let panic_item = PanicOrd(i, true); - - // heapify the sane items - panic_ords.shuffle(&mut rng); - let mut heap = BinaryHeap::from(panic_ords); - let inner_data; - - { - // push the panicking item to the heap and catch the panic - let thread_result = { - let mut heap_ref = AssertUnwindSafe(&mut heap); - panic::catch_unwind(move || { - heap_ref.push(panic_item); - }) - }; - assert!(thread_result.is_err()); - - // Assert no elements were dropped - let drops = DROP_COUNTER.load(Ordering::SeqCst); - assert!(drops == 0, "Must not drop items. drops={}", drops); - inner_data = heap.clone().into_vec(); - drop(heap); - } - let drops = DROP_COUNTER.load(Ordering::SeqCst); - assert_eq!(drops, DATASZ); - - let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::>(); - data_sorted.sort(); - assert_eq!(data_sorted, data); - } - } -} diff --git a/library/alloc/tests/lib.rs b/library/alloc/tests/lib.rs index cbb86265233..fb6468ef30f 100644 --- a/library/alloc/tests/lib.rs +++ b/library/alloc/tests/lib.rs @@ -44,7 +44,6 @@ use std::collections::hash_map::DefaultHasher; use std::hash::{Hash, Hasher}; mod arc; -mod binary_heap; mod borrow; mod boxed; mod btree_set_hash; diff --git a/library/alloc/tests/linked_list.rs b/library/alloc/tests/linked_list.rs index 66a9cca6644..65b09cb00c4 100644 --- a/library/alloc/tests/linked_list.rs +++ b/library/alloc/tests/linked_list.rs @@ -1,241 +1,4 @@ use std::collections::LinkedList; -use std::panic::{catch_unwind, AssertUnwindSafe}; - -#[test] -fn test_basic() { - let mut m = LinkedList::>::new(); - assert_eq!(m.pop_front(), None); - assert_eq!(m.pop_back(), None); - assert_eq!(m.pop_front(), None); - m.push_front(box 1); - assert_eq!(m.pop_front(), Some(box 1)); - m.push_back(box 2); - m.push_back(box 3); - assert_eq!(m.len(), 2); - assert_eq!(m.pop_front(), Some(box 2)); - assert_eq!(m.pop_front(), Some(box 3)); - assert_eq!(m.len(), 0); - assert_eq!(m.pop_front(), None); - m.push_back(box 1); - m.push_back(box 3); - m.push_back(box 5); - m.push_back(box 7); - assert_eq!(m.pop_front(), Some(box 1)); - - let mut n = LinkedList::new(); - n.push_front(2); - n.push_front(3); - { - assert_eq!(n.front().unwrap(), &3); - let x = n.front_mut().unwrap(); - assert_eq!(*x, 3); - *x = 0; - } - { - assert_eq!(n.back().unwrap(), &2); - let y = n.back_mut().unwrap(); - assert_eq!(*y, 2); - *y = 1; - } - assert_eq!(n.pop_front(), Some(0)); - assert_eq!(n.pop_front(), Some(1)); -} - -fn generate_test() -> LinkedList { - list_from(&[0, 1, 2, 3, 4, 5, 6]) -} - -fn list_from(v: &[T]) -> LinkedList { - v.iter().cloned().collect() -} - -#[test] -fn test_split_off() { - // singleton - { - let mut m = LinkedList::new(); - m.push_back(1); - - let p = m.split_off(0); - assert_eq!(m.len(), 0); - assert_eq!(p.len(), 1); - assert_eq!(p.back(), Some(&1)); - assert_eq!(p.front(), Some(&1)); - } - - // not singleton, forwards - { - let u = vec![1, 2, 3, 4, 5]; - let mut m = list_from(&u); - let mut n = m.split_off(2); - assert_eq!(m.len(), 2); - assert_eq!(n.len(), 3); - for elt in 1..3 { - assert_eq!(m.pop_front(), Some(elt)); - } - for elt in 3..6 { - assert_eq!(n.pop_front(), Some(elt)); - } - } - // not singleton, backwards - { - let u = vec![1, 2, 3, 4, 5]; - let mut m = list_from(&u); - let mut n = m.split_off(4); - assert_eq!(m.len(), 4); - assert_eq!(n.len(), 1); - for elt in 1..5 { - assert_eq!(m.pop_front(), Some(elt)); - } - for elt in 5..6 { - assert_eq!(n.pop_front(), Some(elt)); - } - } - - // no-op on the last index - { - let mut m = LinkedList::new(); - m.push_back(1); - - let p = m.split_off(1); - assert_eq!(m.len(), 1); - assert_eq!(p.len(), 0); - assert_eq!(m.back(), Some(&1)); - assert_eq!(m.front(), Some(&1)); - } -} - -#[test] -fn test_iterator() { - let m = generate_test(); - for (i, elt) in m.iter().enumerate() { - assert_eq!(i as i32, *elt); - } - let mut n = LinkedList::new(); - assert_eq!(n.iter().next(), None); - n.push_front(4); - let mut it = n.iter(); - assert_eq!(it.size_hint(), (1, Some(1))); - assert_eq!(it.next().unwrap(), &4); - assert_eq!(it.size_hint(), (0, Some(0))); - assert_eq!(it.next(), None); -} - -#[test] -fn test_iterator_clone() { - let mut n = LinkedList::new(); - n.push_back(2); - n.push_back(3); - n.push_back(4); - let mut it = n.iter(); - it.next(); - let mut jt = it.clone(); - assert_eq!(it.next(), jt.next()); - assert_eq!(it.next_back(), jt.next_back()); - assert_eq!(it.next(), jt.next()); -} - -#[test] -fn test_iterator_double_end() { - let mut n = LinkedList::new(); - assert_eq!(n.iter().next(), None); - n.push_front(4); - n.push_front(5); - n.push_front(6); - let mut it = n.iter(); - assert_eq!(it.size_hint(), (3, Some(3))); - assert_eq!(it.next().unwrap(), &6); - assert_eq!(it.size_hint(), (2, Some(2))); - assert_eq!(it.next_back().unwrap(), &4); - assert_eq!(it.size_hint(), (1, Some(1))); - assert_eq!(it.next_back().unwrap(), &5); - assert_eq!(it.next_back(), None); - assert_eq!(it.next(), None); -} - -#[test] -fn test_rev_iter() { - let m = generate_test(); - for (i, elt) in m.iter().rev().enumerate() { - assert_eq!((6 - i) as i32, *elt); - } - let mut n = LinkedList::new(); - assert_eq!(n.iter().rev().next(), None); - n.push_front(4); - let mut it = n.iter().rev(); - assert_eq!(it.size_hint(), (1, Some(1))); - assert_eq!(it.next().unwrap(), &4); - assert_eq!(it.size_hint(), (0, Some(0))); - assert_eq!(it.next(), None); -} - -#[test] -fn test_mut_iter() { - let mut m = generate_test(); - let mut len = m.len(); - for (i, elt) in m.iter_mut().enumerate() { - assert_eq!(i as i32, *elt); - len -= 1; - } - assert_eq!(len, 0); - let mut n = LinkedList::new(); - assert!(n.iter_mut().next().is_none()); - n.push_front(4); - n.push_back(5); - let mut it = n.iter_mut(); - assert_eq!(it.size_hint(), (2, Some(2))); - assert!(it.next().is_some()); - assert!(it.next().is_some()); - assert_eq!(it.size_hint(), (0, Some(0))); - assert!(it.next().is_none()); -} - -#[test] -fn test_iterator_mut_double_end() { - let mut n = LinkedList::new(); - assert!(n.iter_mut().next_back().is_none()); - n.push_front(4); - n.push_front(5); - n.push_front(6); - let mut it = n.iter_mut(); - assert_eq!(it.size_hint(), (3, Some(3))); - assert_eq!(*it.next().unwrap(), 6); - assert_eq!(it.size_hint(), (2, Some(2))); - assert_eq!(*it.next_back().unwrap(), 4); - assert_eq!(it.size_hint(), (1, Some(1))); - assert_eq!(*it.next_back().unwrap(), 5); - assert!(it.next_back().is_none()); - assert!(it.next().is_none()); -} - -#[test] -fn test_mut_rev_iter() { - let mut m = generate_test(); - for (i, elt) in m.iter_mut().rev().enumerate() { - assert_eq!((6 - i) as i32, *elt); - } - let mut n = LinkedList::new(); - assert!(n.iter_mut().rev().next().is_none()); - n.push_front(4); - let mut it = n.iter_mut().rev(); - assert!(it.next().is_some()); - assert!(it.next().is_none()); -} - -#[test] -fn test_eq() { - let mut n = list_from(&[]); - let mut m = list_from(&[]); - assert!(n == m); - n.push_front(1); - assert!(n != m); - m.push_back(1); - assert!(n == m); - - let n = list_from(&[2, 3, 4]); - let m = list_from(&[1, 2, 3]); - assert!(n != m); -} #[test] fn test_hash() { @@ -256,449 +19,3 @@ fn test_hash() { assert!(hash(&x) == hash(&y)); } - -#[test] -fn test_ord() { - let n = list_from(&[]); - let m = list_from(&[1, 2, 3]); - assert!(n < m); - assert!(m > n); - assert!(n <= n); - assert!(n >= n); -} - -#[test] -fn test_ord_nan() { - let nan = 0.0f64 / 0.0; - let n = list_from(&[nan]); - let m = list_from(&[nan]); - assert!(!(n < m)); - assert!(!(n > m)); - assert!(!(n <= m)); - assert!(!(n >= m)); - - let n = list_from(&[nan]); - let one = list_from(&[1.0f64]); - assert!(!(n < one)); - assert!(!(n > one)); - assert!(!(n <= one)); - assert!(!(n >= one)); - - let u = list_from(&[1.0f64, 2.0, nan]); - let v = list_from(&[1.0f64, 2.0, 3.0]); - assert!(!(u < v)); - assert!(!(u > v)); - assert!(!(u <= v)); - assert!(!(u >= v)); - - let s = list_from(&[1.0f64, 2.0, 4.0, 2.0]); - let t = list_from(&[1.0f64, 2.0, 3.0, 2.0]); - assert!(!(s < t)); - assert!(s > one); - assert!(!(s <= one)); - assert!(s >= one); -} - -#[test] -fn test_show() { - let list: LinkedList<_> = (0..10).collect(); - assert_eq!(format!("{list:?}"), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"); - - let list: LinkedList<_> = ["just", "one", "test", "more"].into_iter().collect(); - assert_eq!(format!("{list:?}"), "[\"just\", \"one\", \"test\", \"more\"]"); -} - -#[test] -fn test_extend_ref() { - let mut a = LinkedList::new(); - a.push_back(1); - - a.extend(&[2, 3, 4]); - - assert_eq!(a.len(), 4); - assert_eq!(a, list_from(&[1, 2, 3, 4])); - - let mut b = LinkedList::new(); - b.push_back(5); - b.push_back(6); - a.extend(&b); - - assert_eq!(a.len(), 6); - assert_eq!(a, list_from(&[1, 2, 3, 4, 5, 6])); -} - -#[test] -fn test_extend() { - let mut a = LinkedList::new(); - a.push_back(1); - a.extend(vec![2, 3, 4]); // uses iterator - - assert_eq!(a.len(), 4); - assert!(a.iter().eq(&[1, 2, 3, 4])); - - let b: LinkedList<_> = [5, 6, 7].into_iter().collect(); - a.extend(b); // specializes to `append` - - assert_eq!(a.len(), 7); - assert!(a.iter().eq(&[1, 2, 3, 4, 5, 6, 7])); -} - -#[test] -fn test_contains() { - let mut l = LinkedList::new(); - l.extend(&[2, 3, 4]); - - assert!(l.contains(&3)); - assert!(!l.contains(&1)); - - l.clear(); - - assert!(!l.contains(&3)); -} - -#[test] -fn drain_filter_empty() { - let mut list: LinkedList = LinkedList::new(); - - { - let mut iter = list.drain_filter(|_| true); - assert_eq!(iter.size_hint(), (0, Some(0))); - assert_eq!(iter.next(), None); - assert_eq!(iter.size_hint(), (0, Some(0))); - assert_eq!(iter.next(), None); - assert_eq!(iter.size_hint(), (0, Some(0))); - } - - assert_eq!(list.len(), 0); - assert_eq!(list.into_iter().collect::>(), vec![]); -} - -#[test] -fn drain_filter_zst() { - let mut list: LinkedList<_> = [(), (), (), (), ()].into_iter().collect(); - let initial_len = list.len(); - let mut count = 0; - - { - let mut iter = list.drain_filter(|_| true); - assert_eq!(iter.size_hint(), (0, Some(initial_len))); - while let Some(_) = iter.next() { - count += 1; - assert_eq!(iter.size_hint(), (0, Some(initial_len - count))); - } - assert_eq!(iter.size_hint(), (0, Some(0))); - assert_eq!(iter.next(), None); - assert_eq!(iter.size_hint(), (0, Some(0))); - } - - assert_eq!(count, initial_len); - assert_eq!(list.len(), 0); - assert_eq!(list.into_iter().collect::>(), vec![]); -} - -#[test] -fn drain_filter_false() { - let mut list: LinkedList<_> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); - - let initial_len = list.len(); - let mut count = 0; - - { - let mut iter = list.drain_filter(|_| false); - assert_eq!(iter.size_hint(), (0, Some(initial_len))); - for _ in iter.by_ref() { - count += 1; - } - assert_eq!(iter.size_hint(), (0, Some(0))); - assert_eq!(iter.next(), None); - assert_eq!(iter.size_hint(), (0, Some(0))); - } - - assert_eq!(count, 0); - assert_eq!(list.len(), initial_len); - assert_eq!(list.into_iter().collect::>(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); -} - -#[test] -fn drain_filter_true() { - let mut list: LinkedList<_> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); - - let initial_len = list.len(); - let mut count = 0; - - { - let mut iter = list.drain_filter(|_| true); - assert_eq!(iter.size_hint(), (0, Some(initial_len))); - while let Some(_) = iter.next() { - count += 1; - assert_eq!(iter.size_hint(), (0, Some(initial_len - count))); - } - assert_eq!(iter.size_hint(), (0, Some(0))); - assert_eq!(iter.next(), None); - assert_eq!(iter.size_hint(), (0, Some(0))); - } - - assert_eq!(count, initial_len); - assert_eq!(list.len(), 0); - assert_eq!(list.into_iter().collect::>(), vec![]); -} - -#[test] -fn drain_filter_complex() { - { - // [+xxx++++++xxxxx++++x+x++] - let mut list = [ - 1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, - 39, - ] - .into_iter() - .collect::>(); - - let removed = list.drain_filter(|x| *x % 2 == 0).collect::>(); - assert_eq!(removed.len(), 10); - assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]); - - assert_eq!(list.len(), 14); - assert_eq!( - list.into_iter().collect::>(), - vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39] - ); - } - - { - // [xxx++++++xxxxx++++x+x++] - let mut list = - [2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39] - .into_iter() - .collect::>(); - - let removed = list.drain_filter(|x| *x % 2 == 0).collect::>(); - assert_eq!(removed.len(), 10); - assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]); - - assert_eq!(list.len(), 13); - assert_eq!( - list.into_iter().collect::>(), - vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39] - ); - } - - { - // [xxx++++++xxxxx++++x+x] - let mut list = - [2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36] - .into_iter() - .collect::>(); - - let removed = list.drain_filter(|x| *x % 2 == 0).collect::>(); - assert_eq!(removed.len(), 10); - assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]); - - assert_eq!(list.len(), 11); - assert_eq!( - list.into_iter().collect::>(), - vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35] - ); - } - - { - // [xxxxxxxxxx+++++++++++] - let mut list = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19] - .into_iter() - .collect::>(); - - let removed = list.drain_filter(|x| *x % 2 == 0).collect::>(); - assert_eq!(removed.len(), 10); - assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]); - - assert_eq!(list.len(), 10); - assert_eq!(list.into_iter().collect::>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]); - } - - { - // [+++++++++++xxxxxxxxxx] - let mut list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20] - .into_iter() - .collect::>(); - - let removed = list.drain_filter(|x| *x % 2 == 0).collect::>(); - assert_eq!(removed.len(), 10); - assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]); - - assert_eq!(list.len(), 10); - assert_eq!(list.into_iter().collect::>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]); - } -} - -#[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 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); - assert!(q.is_empty()); -} - -#[test] -fn drain_filter_pred_panic_leak() { - static mut DROPS: i32 = 0; - - #[derive(Debug)] - struct D(u32); - - impl Drop for D { - fn drop(&mut self) { - unsafe { - DROPS += 1; - } - } - } - - let mut q = LinkedList::new(); - q.push_back(D(3)); - q.push_back(D(4)); - q.push_back(D(5)); - q.push_back(D(6)); - q.push_back(D(7)); - q.push_front(D(2)); - q.push_front(D(1)); - q.push_front(D(0)); - - catch_unwind(AssertUnwindSafe(|| { - drop(q.drain_filter(|item| if item.0 >= 2 { panic!() } else { true })) - })) - .ok(); - - assert_eq!(unsafe { DROPS }, 2); // 0 and 1 - assert_eq!(q.len(), 6); -} - -#[test] -fn test_drop() { - static mut DROPS: i32 = 0; - struct Elem; - impl Drop for Elem { - fn drop(&mut self) { - unsafe { - DROPS += 1; - } - } - } - - let mut ring = LinkedList::new(); - ring.push_back(Elem); - ring.push_front(Elem); - ring.push_back(Elem); - ring.push_front(Elem); - drop(ring); - - assert_eq!(unsafe { DROPS }, 4); -} - -#[test] -fn test_drop_with_pop() { - static mut DROPS: i32 = 0; - struct Elem; - impl Drop for Elem { - fn drop(&mut self) { - unsafe { - DROPS += 1; - } - } - } - - let mut ring = LinkedList::new(); - ring.push_back(Elem); - ring.push_front(Elem); - ring.push_back(Elem); - ring.push_front(Elem); - - drop(ring.pop_back()); - drop(ring.pop_front()); - assert_eq!(unsafe { DROPS }, 2); - - drop(ring); - assert_eq!(unsafe { DROPS }, 4); -} - -#[test] -fn test_drop_clear() { - static mut DROPS: i32 = 0; - struct Elem; - impl Drop for Elem { - fn drop(&mut self) { - unsafe { - DROPS += 1; - } - } - } - - let mut ring = LinkedList::new(); - ring.push_back(Elem); - ring.push_front(Elem); - ring.push_back(Elem); - ring.push_front(Elem); - ring.clear(); - assert_eq!(unsafe { DROPS }, 4); - - drop(ring); - assert_eq!(unsafe { DROPS }, 4); -} - -#[test] -fn test_drop_panic() { - 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 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(false)); - q.push_front(D(true)); - - catch_unwind(move || drop(q)).ok(); - - assert_eq!(unsafe { DROPS }, 8); -} -- cgit 1.4.1-3-g733a5 From 4dda047de346ae68fa760548f7ae63e3ae736146 Mon Sep 17 00:00:00 2001 From: jmaargh Date: Tue, 19 Apr 2022 21:12:55 +0100 Subject: Clarify docs for from_raw_parts Original safety explanation for from_raw_parts was unclear on safety for consuming a C string. This clarifies when doing so is safe. --- library/alloc/src/string.rs | 5 ++++- library/alloc/src/vec/mod.rs | 6 ++++-- 2 files changed, 8 insertions(+), 3 deletions(-) diff --git a/library/alloc/src/string.rs b/library/alloc/src/string.rs index e97c1637fd5..2272c5b7330 100644 --- a/library/alloc/src/string.rs +++ b/library/alloc/src/string.rs @@ -770,7 +770,10 @@ impl String { /// * The first `length` bytes at `buf` need to be valid UTF-8. /// /// Violating these may cause problems like corrupting the allocator's - /// internal data structures. + /// internal data structures. For example, it is normally **not** safe to + /// build a `String` from a pointer to a C `char` array containing UTF-8 + /// _unless_ you are certain that array was originally allocated by the + /// Rust standard library's allocator. /// /// The ownership of `buf` is effectively transferred to the /// `String` which may then deallocate, reallocate or change the diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 8c2f52172ee..9bf42e779c9 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -489,8 +489,10 @@ impl Vec { /// * `length` needs to be less than or equal to `capacity`. /// /// Violating these may cause problems like corrupting the allocator's - /// internal data structures. For example it is **not** safe - /// to build a `Vec` from a pointer to a C `char` array with length `size_t`. + /// internal data structures. For example it is normally **not** safe + /// to build a `Vec` from a pointer to a C `char` array with length + /// `size_t`, doing so is only safe if the array was initially allocated by + /// a `Vec` or `String`. /// It's also not safe to build one from a `Vec` and its length, because /// the allocator cares about the alignment, and these two types have different /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after -- cgit 1.4.1-3-g733a5 From 2f287d6a3e200197919e5372ac74abb66ce038ad Mon Sep 17 00:00:00 2001 From: Joshua Nelson Date: Wed, 27 Apr 2022 21:47:58 -0500 Subject: Make it possible to write doctests for bootstrap This probably isn't super useful in practice, but it was easy to fix and avoids confusing errors about mismatched versions between beta and the default toolchain. --- src/bootstrap/test.rs | 11 +++++++++++ 1 file changed, 11 insertions(+) diff --git a/src/bootstrap/test.rs b/src/bootstrap/test.rs index 9c376602d28..af84a800721 100644 --- a/src/bootstrap/test.rs +++ b/src/bootstrap/test.rs @@ -2362,6 +2362,7 @@ impl Step for Bootstrap { .env("RUSTFLAGS", "-Cdebuginfo=2") .env("CARGO_TARGET_DIR", builder.out.join("bootstrap")) .env("RUSTC_BOOTSTRAP", "1") + .env("RUSTDOC", builder.rustdoc(builder.compiler(0, builder.build.build))) .env("RUSTC", &builder.initial_rustc); if let Some(flags) = option_env!("RUSTFLAGS") { // Use the same rustc flags for testing as for "normal" compilation, @@ -2372,6 +2373,16 @@ impl Step for Bootstrap { if !builder.fail_fast { cmd.arg("--no-fail-fast"); } + match builder.doc_tests { + DocTests::Only => { + cmd.arg("--doc"); + } + DocTests::No => { + cmd.args(&["--lib", "--bins", "--examples", "--tests", "--benches"]); + } + DocTests::Yes => {} + } + cmd.arg("--").args(&builder.config.cmd.test_args()); // rustbuild tests are racy on directory creation so just run them one at a time. // Since there's not many this shouldn't be a problem. -- cgit 1.4.1-3-g733a5 From ec90f9dd338a121d175189bd72d1bab3fb882124 Mon Sep 17 00:00:00 2001 From: alexey semenyuk Date: Fri, 29 Apr 2022 23:16:53 +0000 Subject: Fix documentation for log functions unsigned int --- library/core/src/num/uint_macros.rs | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/library/core/src/num/uint_macros.rs b/library/core/src/num/uint_macros.rs index 514ac69f7e0..ce52e4773ce 100644 --- a/library/core/src/num/uint_macros.rs +++ b/library/core/src/num/uint_macros.rs @@ -689,7 +689,7 @@ macro_rules! uint_impl { /// /// # Panics /// - /// When the number is negative, zero, or if the base is not at least 2; + /// When the number is zero, or if the base is not at least 2; /// it panics in debug mode and the return value is 0 in release mode. /// /// # Examples @@ -722,7 +722,7 @@ macro_rules! uint_impl { /// /// # Panics /// - /// When the number is negative or zero it panics in debug mode and + /// When the number is zero it panics in debug mode and /// the return value is 0 in release mode. /// /// # Examples @@ -755,7 +755,7 @@ macro_rules! uint_impl { /// /// # Panics /// - /// When the number is negative or zero it panics in debug mode and the + /// When the number is zero it panics in debug mode and the /// return value is 0 in release mode. /// /// # Example -- cgit 1.4.1-3-g733a5 From 6ee70bc6b3e463c50afaea8d8191b0b4ee639771 Mon Sep 17 00:00:00 2001 From: alexey semenyuk Date: Fri, 29 Apr 2022 23:21:50 +0000 Subject: Fix documentation for log functions int --- library/core/src/num/int_macros.rs | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/library/core/src/num/int_macros.rs b/library/core/src/num/int_macros.rs index ec460286d03..1bf44734740 100644 --- a/library/core/src/num/int_macros.rs +++ b/library/core/src/num/int_macros.rs @@ -2189,7 +2189,7 @@ macro_rules! int_impl { /// /// # Panics /// - /// When the number is zero, or if the base is not at least 2; it + /// When the number is negative, zero, or if the base is not at least 2; it /// panics in debug mode and the return value is 0 in release /// mode. /// @@ -2223,7 +2223,7 @@ macro_rules! int_impl { /// /// # Panics /// - /// When the number is zero it panics in debug mode and the return value + /// When the number is negative or zero it panics in debug mode and the return value /// is 0 in release mode. /// /// # Examples @@ -2256,7 +2256,7 @@ macro_rules! int_impl { /// /// # Panics /// - /// When the number is zero it panics in debug mode and the return value + /// When the number is negative or zero it panics in debug mode and the return value /// is 0 in release mode. /// /// # Example -- cgit 1.4.1-3-g733a5 From dff97d5329d5ed45f4e32bcfccd9c0d2b72eb127 Mon Sep 17 00:00:00 2001 From: Thom Chiovoloni Date: Fri, 29 Apr 2022 20:25:02 -0700 Subject: Add a bathroom stall to weird expressions test --- src/test/ui/weird-exprs.rs | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/src/test/ui/weird-exprs.rs b/src/test/ui/weird-exprs.rs index a02b3230689..42acd30a0ff 100644 --- a/src/test/ui/weird-exprs.rs +++ b/src/test/ui/weird-exprs.rs @@ -164,6 +164,12 @@ fn monkey_barrel() { assert_eq!(val, ()); } +fn bathroom_stall() { + let mut i = 1; + matches!(2, _|_|_|_|_|_ if (i+=1) != (i+=1)); + assert_eq!(i, 13); +} + pub fn main() { strange(); funny(); @@ -183,4 +189,5 @@ pub fn main() { i_yield(); match_nested_if(); monkey_barrel(); + bathroom_stall(); } -- cgit 1.4.1-3-g733a5 From 1288883932e04317cbf075989cfc17369bff038c Mon Sep 17 00:00:00 2001 From: Elias Holzmann <9659253+EliasHolzmann@users.noreply.github.com> Date: Sat, 30 Apr 2022 02:38:22 +0200 Subject: std::fmt: Fixed documentation for specifying precision via `.*` The documentation stated that in case of the syntax `{:.*}`, "the `` part refers to the value to print, and the precision must come in the input preceding ``". This is not correct: the part does indeed refer to the value to print, but the precision does not come in the input preciding arg, but in the next implicit input (as if specified with {}). Fixes #96413. --- library/alloc/src/fmt.rs | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-) diff --git a/library/alloc/src/fmt.rs b/library/alloc/src/fmt.rs index 501a6353b2c..5f6849a9b63 100644 --- a/library/alloc/src/fmt.rs +++ b/library/alloc/src/fmt.rs @@ -221,10 +221,12 @@ //! //! 3. An asterisk `.*`: //! -//! `.*` means that this `{...}` is associated with *two* format inputs rather than one: the -//! first input holds the `usize` precision, and the second holds the value to print. Note that -//! in this case, if one uses the format string `{:.*}`, then the `` part refers -//! to the *value* to print, and the `precision` must come in the input preceding ``. +//! `.*` means that this `{...}` is associated with *two* format inputs rather than one: +//! - If a format string in the fashion of `{:.*}` is used, then the first input holds +//! the `usize` precision, and the second holds the value to print. +//! - If a format string in the fashion of `{:.*}` is used, then the `` part +//! refers to the value to print, and the `precision` is taken like it was specified with an +//! omitted positional parameter (`{}` instead of `{:}`). //! //! For example, the following calls all print the same thing `Hello x is 0.01000`: //! @@ -242,8 +244,12 @@ //! // specified in first of next two args (5)} //! println!("Hello {} is {:.*}", "x", 5, 0.01); //! +//! // Hello {arg 1 ("x")} is {arg 2 (0.01) with precision +//! // specified in next arg (5)} +//! println!("Hello {1} is {2:.*}", 5, "x", 0.01); +//! //! // Hello {next arg ("x")} is {arg 2 (0.01) with precision -//! // specified in its predecessor (5)} +//! // specified in next arg (5)} //! println!("Hello {} is {2:.*}", "x", 5, 0.01); //! //! // Hello {next arg ("x")} is {arg "number" (0.01) with precision specified -- cgit 1.4.1-3-g733a5 From afd80a21b0fd2fb378e01a49b95d9a7d61536ca6 Mon Sep 17 00:00:00 2001 From: Elias Holzmann <9659253+EliasHolzmann@users.noreply.github.com> Date: Sat, 30 Apr 2022 02:39:27 +0200 Subject: std::fmt: Added argument index comments to examples for specifying precision The examples for specifying the precision have comments explaining which argument the specifier is referring to. However, for implicit positional arguments, the examples simply talk about "next arg". To make it easier for readers to follow the comments, "next arg" was supplemented with the actual resulting argument index. --- library/alloc/src/fmt.rs | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/library/alloc/src/fmt.rs b/library/alloc/src/fmt.rs index 5f6849a9b63..361e821dd37 100644 --- a/library/alloc/src/fmt.rs +++ b/library/alloc/src/fmt.rs @@ -240,19 +240,19 @@ //! // Hello {arg 0 ("x")} is {arg 2 (0.01) with precision specified in arg 1 (5)} //! println!("Hello {0} is {2:.1$}", "x", 5, 0.01); //! -//! // Hello {next arg ("x")} is {second of next two args (0.01) with precision -//! // specified in first of next two args (5)} +//! // Hello {next arg -> arg 0 ("x")} is {second of next two args -> arg 2 (0.01) with precision +//! // specified in first of next two args -> arg 1 (5)} //! println!("Hello {} is {:.*}", "x", 5, 0.01); //! //! // Hello {arg 1 ("x")} is {arg 2 (0.01) with precision -//! // specified in next arg (5)} +//! // specified in next arg -> arg 0 (5)} //! println!("Hello {1} is {2:.*}", 5, "x", 0.01); //! -//! // Hello {next arg ("x")} is {arg 2 (0.01) with precision -//! // specified in next arg (5)} +//! // Hello {next arg -> arg 0 ("x")} is {arg 2 (0.01) with precision +//! // specified in next arg -> arg 1 (5)} //! println!("Hello {} is {2:.*}", "x", 5, 0.01); //! -//! // Hello {next arg ("x")} is {arg "number" (0.01) with precision specified +//! // Hello {next arg -> arg 0 ("x")} is {arg "number" (0.01) with precision specified //! // in arg "prec" (5)} //! println!("Hello {} is {number:.prec$}", "x", prec = 5, number = 0.01); //! ``` -- cgit 1.4.1-3-g733a5 From 79d9afda137cfeb30cefdce397851b8e20db4ae1 Mon Sep 17 00:00:00 2001 From: Elias Holzmann <9659253+EliasHolzmann@users.noreply.github.com> Date: Sat, 30 Apr 2022 02:39:59 +0200 Subject: std::fmt: Fix the grammar documentation According to the grammar documented, the format specifier `{: }` should not be legal because of the whitespace it contains. However, in reality, this is perfectly fine because the actual implementation allows spaces before the closing brace. Fixes #71088. Also, the exact meaning of most of the terminal symbols was not specified, for example the meaning of `identifier`. --- library/alloc/src/fmt.rs | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/library/alloc/src/fmt.rs b/library/alloc/src/fmt.rs index 361e821dd37..7b12f6e86c1 100644 --- a/library/alloc/src/fmt.rs +++ b/library/alloc/src/fmt.rs @@ -310,7 +310,7 @@ //! ```text //! format_string := text [ maybe_format text ] * //! maybe_format := '{' '{' | '}' '}' | format -//! format := '{' [ argument ] [ ':' format_spec ] '}' +//! format := '{' [ argument ] [ ':' format_spec ] [ ws ] * '}' //! argument := integer | identifier //! //! format_spec := [[fill]align][sign]['#']['0'][width]['.' precision]type @@ -323,7 +323,12 @@ //! count := parameter | integer //! parameter := argument '$' //! ``` -//! In the above grammar, `text` must not contain any `'{'` or `'}'` characters. +//! In the above grammar, +//! - `text` must not contain any `'{'` or `'}'` characters, +//! - `ws` is any character for which [`char::is_whitespace`] returns `true`, has no semantic +//! meaning and is completely optional, +//! - `integer` is a decimal integer that may contain leading zeroes and +//! - `identifier` is an `IDENTIFIER_OR_KEYWORD` (not an `IDENTIFIER`) as defined by the [Rust language reference](https://doc.rust-lang.org/reference/identifiers.html). //! //! # Formatting traits //! -- cgit 1.4.1-3-g733a5 From c70f3ab5e53916a2e0210a24b67c64f2b700a06f Mon Sep 17 00:00:00 2001 From: Elias Holzmann <9659253+EliasHolzmann@users.noreply.github.com> Date: Sat, 30 Apr 2022 02:40:39 +0200 Subject: std::fmt: Removed reference to Formatter::buf and other private fields Formatter::buf is not a public field and therefore isn't very helpful in user- facing documentation. Also, the other public fields of Formatter were made private during stabilization of std::fmt (4af3494bb0) and can now only be read via accessor methods. --- library/alloc/src/fmt.rs | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/library/alloc/src/fmt.rs b/library/alloc/src/fmt.rs index 7b12f6e86c1..635a3ffa3c5 100644 --- a/library/alloc/src/fmt.rs +++ b/library/alloc/src/fmt.rs @@ -369,9 +369,9 @@ //! ``` //! //! Your type will be passed as `self` by-reference, and then the function -//! should emit output into the `f.buf` stream. It is up to each format trait -//! implementation to correctly adhere to the requested formatting parameters. -//! The values of these parameters will be listed in the fields of the +//! should emit output into the Formatter `f` which implements `fmt::Write`. It is up to each +//! format trait implementation to correctly adhere to the requested formatting parameters. +//! The values of these parameters can be accessed with methods of the //! [`Formatter`] struct. In order to help with this, the [`Formatter`] struct also //! provides some helper methods. //! -- cgit 1.4.1-3-g733a5 From f3b86c37ebdddbc7555ba560b6c4b4f4d44f991d Mon Sep 17 00:00:00 2001 From: Elias Holzmann <9659253+EliasHolzmann@users.noreply.github.com> Date: Sat, 30 Apr 2022 02:41:32 +0200 Subject: std::fmt: Improved list of formatting macros Two improvements: 1. write! can not only receive a `io::Write`, but also a `fmt::Write` as first argument. 2. The description texts now contain links to the actual macros for easier navigation. --- library/alloc/src/fmt.rs | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) diff --git a/library/alloc/src/fmt.rs b/library/alloc/src/fmt.rs index 635a3ffa3c5..73b75ea4d83 100644 --- a/library/alloc/src/fmt.rs +++ b/library/alloc/src/fmt.rs @@ -460,7 +460,7 @@ //! //! ```ignore (only-for-syntax-highlight) //! format! // described above -//! write! // first argument is a &mut io::Write, the destination +//! write! // first argument is either a &mut io::Write or a &mut fmt::Write, the destination //! writeln! // same as write but appends a newline //! print! // the format string is printed to the standard output //! println! // same as print but appends a newline @@ -471,11 +471,11 @@ //! //! ### `write!` //! -//! This and [`writeln!`] are two macros which are used to emit the format string +//! [`write!`] and [`writeln!`] are two macros which are used to emit the format string //! to a specified stream. This is used to prevent intermediate allocations of //! format strings and instead directly write the output. Under the hood, this //! function is actually invoking the [`write_fmt`] function defined on the -//! [`std::io::Write`] trait. Example usage is: +//! [`std::io::Write`] and the [`std::fmt::Write`] trait. Example usage is: //! //! ``` //! # #![allow(unused_must_use)] @@ -502,7 +502,7 @@ //! //! ### `format_args!` //! -//! This is a curious macro used to safely pass around +//! [`format_args!`] is a curious macro used to safely pass around //! an opaque object describing the format string. This object //! does not require any heap allocations to create, and it only //! references information on the stack. Under the hood, all of @@ -540,10 +540,12 @@ //! [`to_string`]: crate::string::ToString::to_string "ToString::to_string" //! [`write_fmt`]: ../../std/io/trait.Write.html#method.write_fmt //! [`std::io::Write`]: ../../std/io/trait.Write.html +//! [`std::fmt::Write`]: ../../std/fmt/trait.Write.html //! [`print!`]: ../../std/macro.print.html "print!" //! [`println!`]: ../../std/macro.println.html "println!" //! [`eprint!`]: ../../std/macro.eprint.html "eprint!" //! [`eprintln!`]: ../../std/macro.eprintln.html "eprintln!" +//! [`format_args!`]: ../../std/macro.format_args.html "format_args!" //! [`fmt::Arguments`]: Arguments "fmt::Arguments" //! [`format`]: format() "fmt::format" -- cgit 1.4.1-3-g733a5 From 68982bcd67024d09394618a4ffc7f1d8c8df064d Mon Sep 17 00:00:00 2001 From: Guillaume Gomez Date: Sun, 1 May 2022 21:36:19 +0200 Subject: Update browser-ui-test version to 0.9.0 --- src/ci/docker/host-x86_64/x86_64-gnu-tools/browser-ui-test.version | 2 +- src/tools/rustdoc-gui/tester.js | 1 - 2 files changed, 1 insertion(+), 2 deletions(-) diff --git a/src/ci/docker/host-x86_64/x86_64-gnu-tools/browser-ui-test.version b/src/ci/docker/host-x86_64/x86_64-gnu-tools/browser-ui-test.version index bbde4bee23f..899f24fc754 100644 --- a/src/ci/docker/host-x86_64/x86_64-gnu-tools/browser-ui-test.version +++ b/src/ci/docker/host-x86_64/x86_64-gnu-tools/browser-ui-test.version @@ -1 +1 @@ -0.8.5 \ No newline at end of file +0.9.0 \ No newline at end of file diff --git a/src/tools/rustdoc-gui/tester.js b/src/tools/rustdoc-gui/tester.js index 841c0f2b939..d75884567af 100644 --- a/src/tools/rustdoc-gui/tester.js +++ b/src/tools/rustdoc-gui/tester.js @@ -138,7 +138,6 @@ async function main(argv) { try { // This is more convenient that setting fields one by one. let args = [ - "--no-screenshot-comparison", "--variable", "DOC_PATH", opts["doc_folder"], ]; if (opts["debug"]) { -- cgit 1.4.1-3-g733a5