From 218caa410aa38c29984be31a5229b9fa717560ee Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:19:13 +0200 Subject: Merging upstream version 1.68.2+dfsg1. Signed-off-by: Daniel Baumann --- library/alloc/tests/autotraits.rs | 2 +- library/alloc/tests/lib.rs | 1 - library/alloc/tests/slice.rs | 349 +------------------------------------- library/alloc/tests/vec.rs | 31 +++- library/alloc/tests/vec_deque.rs | 50 ++++++ 5 files changed, 80 insertions(+), 353 deletions(-) (limited to 'library/alloc/tests') diff --git a/library/alloc/tests/autotraits.rs b/library/alloc/tests/autotraits.rs index 8ff5f0abe..879e32b3f 100644 --- a/library/alloc/tests/autotraits.rs +++ b/library/alloc/tests/autotraits.rs @@ -32,7 +32,7 @@ fn test_btree_map() { // spawn(f()); // } // - // where with some unintentionally overconstrained Send impls in liballoc's + // where with some unintentionally overconstrained Send impls in alloc's // internals, the future might incorrectly not be Send even though every // single type involved in the program is Send and Sync. require_send_sync(async { diff --git a/library/alloc/tests/lib.rs b/library/alloc/tests/lib.rs index d6d2b055b..2a93a242d 100644 --- a/library/alloc/tests/lib.rs +++ b/library/alloc/tests/lib.rs @@ -1,7 +1,6 @@ #![feature(allocator_api)] #![feature(alloc_layout_extra)] #![feature(assert_matches)] -#![feature(box_syntax)] #![feature(btree_drain_filter)] #![feature(cow_is_borrowed)] #![feature(const_box)] diff --git a/library/alloc/tests/slice.rs b/library/alloc/tests/slice.rs index 21f894343..0693beb48 100644 --- a/library/alloc/tests/slice.rs +++ b/library/alloc/tests/slice.rs @@ -1,15 +1,9 @@ -use std::cell::Cell; -use std::cmp::Ordering::{self, Equal, Greater, Less}; +use std::cmp::Ordering::{Equal, Greater, Less}; use std::convert::identity; use std::fmt; use std::mem; use std::panic; use std::rc::Rc; -use std::sync::atomic::{AtomicUsize, Ordering::Relaxed}; - -use rand::distributions::Standard; -use rand::seq::SliceRandom; -use rand::{thread_rng, Rng, RngCore}; fn square(n: usize) -> usize { n * n @@ -388,123 +382,6 @@ fn test_reverse() { assert_eq!(v, (-50..51i16).rev().collect::>()); } -#[test] -#[cfg_attr(miri, ignore)] // Miri is too slow -fn test_sort() { - let mut rng = thread_rng(); - - for len in (2..25).chain(500..510) { - for &modulus in &[5, 10, 100, 1000] { - for _ in 0..10 { - let orig: Vec<_> = - rng.sample_iter::(&Standard).map(|x| x % modulus).take(len).collect(); - - // Sort in default order. - let mut v = orig.clone(); - v.sort(); - assert!(v.windows(2).all(|w| w[0] <= w[1])); - - // Sort in ascending order. - let mut v = orig.clone(); - v.sort_by(|a, b| a.cmp(b)); - assert!(v.windows(2).all(|w| w[0] <= w[1])); - - // Sort in descending order. - let mut v = orig.clone(); - v.sort_by(|a, b| b.cmp(a)); - assert!(v.windows(2).all(|w| w[0] >= w[1])); - - // Sort in lexicographic order. - let mut v1 = orig.clone(); - let mut v2 = orig.clone(); - v1.sort_by_key(|x| x.to_string()); - v2.sort_by_cached_key(|x| x.to_string()); - assert!(v1.windows(2).all(|w| w[0].to_string() <= w[1].to_string())); - assert!(v1 == v2); - - // Sort with many pre-sorted runs. - let mut v = orig.clone(); - v.sort(); - v.reverse(); - for _ in 0..5 { - let a = rng.gen::() % len; - let b = rng.gen::() % len; - if a < b { - v[a..b].reverse(); - } else { - v.swap(a, b); - } - } - v.sort(); - assert!(v.windows(2).all(|w| w[0] <= w[1])); - } - } - } - - // Sort using a completely random comparison function. - // This will reorder the elements *somehow*, but won't panic. - let mut v = [0; 500]; - for i in 0..v.len() { - v[i] = i as i32; - } - v.sort_by(|_, _| *[Less, Equal, Greater].choose(&mut rng).unwrap()); - v.sort(); - for i in 0..v.len() { - assert_eq!(v[i], i as i32); - } - - // Should not panic. - [0i32; 0].sort(); - [(); 10].sort(); - [(); 100].sort(); - - let mut v = [0xDEADBEEFu64]; - v.sort(); - assert!(v == [0xDEADBEEF]); -} - -#[test] -fn test_sort_stability() { - // Miri is too slow - let large_range = if cfg!(miri) { 0..0 } else { 500..510 }; - let rounds = if cfg!(miri) { 1 } else { 10 }; - - for len in (2..25).chain(large_range) { - for _ in 0..rounds { - let mut counts = [0; 10]; - - // create a vector like [(6, 1), (5, 1), (6, 2), ...], - // where the first item of each tuple is random, but - // the second item represents which occurrence of that - // number this element is, i.e., the second elements - // will occur in sorted order. - let orig: Vec<_> = (0..len) - .map(|_| { - let n = thread_rng().gen::() % 10; - counts[n] += 1; - (n, counts[n]) - }) - .collect(); - - let mut v = orig.clone(); - // Only sort on the first element, so an unstable sort - // may mix up the counts. - v.sort_by(|&(a, _), &(b, _)| a.cmp(&b)); - - // This comparison includes the count (the second item - // of the tuple), so elements with equal first items - // will need to be ordered with increasing - // counts... i.e., exactly asserting that this sort is - // stable. - assert!(v.windows(2).all(|w| w[0] <= w[1])); - - let mut v = orig.clone(); - v.sort_by_cached_key(|&(x, _)| x); - assert!(v.windows(2).all(|w| w[0] <= w[1])); - } - } -} - #[test] fn test_rotate_left() { let expected: Vec<_> = (0..13).collect(); @@ -1608,230 +1485,6 @@ fn test_copy_from_slice_dst_shorter() { dst.copy_from_slice(&src); } -const MAX_LEN: usize = 80; - -static DROP_COUNTS: [AtomicUsize; MAX_LEN] = [ - // FIXME(RFC 1109): AtomicUsize is not Copy. - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), - AtomicUsize::new(0), -]; - -static VERSIONS: AtomicUsize = AtomicUsize::new(0); - -#[derive(Clone, Eq)] -struct DropCounter { - x: u32, - id: usize, - version: Cell, -} - -impl PartialEq for DropCounter { - fn eq(&self, other: &Self) -> bool { - self.partial_cmp(other) == Some(Ordering::Equal) - } -} - -impl PartialOrd for DropCounter { - fn partial_cmp(&self, other: &Self) -> Option { - self.version.set(self.version.get() + 1); - other.version.set(other.version.get() + 1); - VERSIONS.fetch_add(2, Relaxed); - self.x.partial_cmp(&other.x) - } -} - -impl Ord for DropCounter { - fn cmp(&self, other: &Self) -> Ordering { - self.partial_cmp(other).unwrap() - } -} - -impl Drop for DropCounter { - fn drop(&mut self) { - DROP_COUNTS[self.id].fetch_add(1, Relaxed); - VERSIONS.fetch_sub(self.version.get(), Relaxed); - } -} - -macro_rules! test { - ($input:ident, $func:ident) => { - let len = $input.len(); - - // Work out the total number of comparisons required to sort - // this array... - let mut count = 0usize; - $input.to_owned().$func(|a, b| { - count += 1; - a.cmp(b) - }); - - // ... and then panic on each and every single one. - for panic_countdown in 0..count { - // Refresh the counters. - VERSIONS.store(0, Relaxed); - for i in 0..len { - DROP_COUNTS[i].store(0, Relaxed); - } - - let v = $input.to_owned(); - let _ = std::panic::catch_unwind(move || { - let mut v = v; - let mut panic_countdown = panic_countdown; - v.$func(|a, b| { - if panic_countdown == 0 { - SILENCE_PANIC.with(|s| s.set(true)); - panic!(); - } - panic_countdown -= 1; - a.cmp(b) - }) - }); - - // Check that the number of things dropped is exactly - // what we expect (i.e., the contents of `v`). - for (i, c) in DROP_COUNTS.iter().enumerate().take(len) { - let count = c.load(Relaxed); - assert!(count == 1, "found drop count == {} for i == {}, len == {}", count, i, len); - } - - // Check that the most recent versions of values were dropped. - assert_eq!(VERSIONS.load(Relaxed), 0); - } - }; -} - -thread_local!(static SILENCE_PANIC: Cell = Cell::new(false)); - -#[test] -#[cfg_attr(target_os = "emscripten", ignore)] // no threads -fn panic_safe() { - panic::update_hook(move |prev, info| { - if !SILENCE_PANIC.with(|s| s.get()) { - prev(info); - } - }); - - let mut rng = thread_rng(); - - // Miri is too slow (but still need to `chain` to make the types match) - let lens = if cfg!(miri) { (1..10).chain(0..0) } else { (1..20).chain(70..MAX_LEN) }; - let moduli: &[u32] = if cfg!(miri) { &[5] } else { &[5, 20, 50] }; - - for len in lens { - for &modulus in moduli { - for &has_runs in &[false, true] { - let mut input = (0..len) - .map(|id| DropCounter { - x: rng.next_u32() % modulus, - id: id, - version: Cell::new(0), - }) - .collect::>(); - - if has_runs { - for c in &mut input { - c.x = c.id as u32; - } - - for _ in 0..5 { - let a = rng.gen::() % len; - let b = rng.gen::() % len; - if a < b { - input[a..b].reverse(); - } else { - input.swap(a, b); - } - } - } - - test!(input, sort_by); - test!(input, sort_unstable_by); - } - } - } - - // Set default panic hook again. - drop(panic::take_hook()); -} - #[test] fn repeat_generic_slice() { assert_eq!([1, 2].repeat(2), vec![1, 2, 1, 2]); diff --git a/library/alloc/tests/vec.rs b/library/alloc/tests/vec.rs index 7ebed0d5c..2f07c2911 100644 --- a/library/alloc/tests/vec.rs +++ b/library/alloc/tests/vec.rs @@ -7,7 +7,9 @@ use std::borrow::Cow; use std::cell::Cell; use std::collections::TryReserveErrorKind::*; use std::fmt::Debug; +use std::hint; use std::iter::InPlaceIterable; +use std::mem; use std::mem::{size_of, swap}; use std::ops::Bound::*; use std::panic::{catch_unwind, AssertUnwindSafe}; @@ -1107,8 +1109,31 @@ fn test_into_iter_drop_allocator() { #[test] fn test_into_iter_zst() { - for _ in vec![[0u64; 0]].into_iter() {} - for _ in vec![[0u64; 0]; 5].into_iter().rev() {} + #[derive(Debug, Clone)] + struct AlignedZstWithDrop([u64; 0]); + impl Drop for AlignedZstWithDrop { + fn drop(&mut self) { + let addr = self as *mut _ as usize; + assert!(hint::black_box(addr) % mem::align_of::() == 0); + } + } + + const C: AlignedZstWithDrop = AlignedZstWithDrop([0u64; 0]); + + for _ in vec![C].into_iter() {} + for _ in vec![C; 5].into_iter().rev() {} + + let mut it = vec![C, C].into_iter(); + it.advance_by(1).unwrap(); + drop(it); + + let mut it = vec![C, C].into_iter(); + it.next_chunk::<1>().unwrap(); + drop(it); + + let mut it = vec![C, C].into_iter(); + it.next_chunk::<4>().unwrap_err(); + drop(it); } #[test] @@ -1824,7 +1849,7 @@ fn test_stable_pointers() { } // Test that, if we reserved enough space, adding and removing elements does not - // invalidate references into the vector (such as `v0`). This test also + // invalidate references into the vector (such as `v0`). This test also // runs in Miri, which would detect such problems. // Note that this test does *not* constitute a stable guarantee that all these functions do not // reallocate! Only what is explicitly documented at diff --git a/library/alloc/tests/vec_deque.rs b/library/alloc/tests/vec_deque.rs index d04de5a07..5a0b852e8 100644 --- a/library/alloc/tests/vec_deque.rs +++ b/library/alloc/tests/vec_deque.rs @@ -1045,6 +1045,20 @@ fn test_append_double_drop() { assert_eq!(count_b, 1); } +#[test] +#[should_panic] +fn test_append_zst_capacity_overflow() { + let mut v = Vec::with_capacity(usize::MAX); + // note: using resize instead of set_len here would + // be *extremely* slow in unoptimized builds. + // SAFETY: `v` has capacity `usize::MAX`, and no initialization + // is needed for empty tuples. + unsafe { v.set_len(usize::MAX) }; + let mut v = VecDeque::from(v); + let mut w = vec![()].into(); + v.append(&mut w); +} + #[test] fn test_retain() { let mut buf = VecDeque::new(); @@ -1736,3 +1750,39 @@ fn test_resize_keeps_reserved_space_from_item() { d.resize(1, v); assert_eq!(d[0].capacity(), 1234); } + +#[test] +fn test_collect_from_into_iter_keeps_allocation() { + let mut v = Vec::with_capacity(13); + v.extend(0..7); + check(v.as_ptr(), v.last().unwrap(), v.into_iter()); + + let mut v = VecDeque::with_capacity(13); + v.extend(0..7); + check(&v[0], &v[v.len() - 1], v.into_iter()); + + fn check(buf: *const i32, last: *const i32, mut it: impl Iterator) { + assert_eq!(it.next(), Some(0)); + assert_eq!(it.next(), Some(1)); + + let mut v: VecDeque = it.collect(); + assert_eq!(v.capacity(), 13); + assert_eq!(v.as_slices().0.as_ptr(), buf.wrapping_add(2)); + assert_eq!(&v[v.len() - 1] as *const _, last); + + assert_eq!(v.as_slices(), ([2, 3, 4, 5, 6].as_slice(), [].as_slice())); + v.push_front(7); + assert_eq!(v.as_slices(), ([7, 2, 3, 4, 5, 6].as_slice(), [].as_slice())); + v.push_front(8); + assert_eq!(v.as_slices(), ([8, 7, 2, 3, 4, 5, 6].as_slice(), [].as_slice())); + + // Now that we've adding thing in place of the two that we removed from + // the front of the iterator, we're back to matching the buffer pointer. + assert_eq!(v.as_slices().0.as_ptr(), buf); + assert_eq!(&v[v.len() - 1] as *const _, last); + + v.push_front(9); + assert_eq!(v.as_slices(), ([9].as_slice(), [8, 7, 2, 3, 4, 5, 6].as_slice())); + assert_eq!(v.capacity(), 13); + } +} -- cgit v1.2.3