diff options
| author | Peter <peter.wilkins@polecat.com> | 2019-12-08 23:16:18 +0000 |
|---|---|---|
| committer | Peter <peter.wilkins@polecat.com> | 2019-12-08 23:49:30 +0000 |
| commit | 8f6a06285efe12d778ff7f44067aebeed7b14428 (patch) | |
| tree | 856b9d17a8e4700c44a2794e63ec75ecf9660397 /src/liballoc | |
| parent | 947772fc31b96ce90f57720f74571f14e35df66b (diff) | |
| parent | 59947fcae6a40df12e33af8c8c7291014b7603e0 (diff) | |
| download | rust-8f6a06285efe12d778ff7f44067aebeed7b14428.tar.gz rust-8f6a06285efe12d778ff7f44067aebeed7b14428.zip | |
move from non zero impls to `libcore/convert/num.rs`
Diffstat (limited to 'src/liballoc')
38 files changed, 919 insertions, 489 deletions
diff --git a/src/liballoc/alloc/tests.rs b/src/liballoc/alloc/tests.rs index c69f4e49ee1..956298d7836 100644 --- a/src/liballoc/alloc/tests.rs +++ b/src/liballoc/alloc/tests.rs @@ -1,15 +1,15 @@ use super::*; extern crate test; -use test::Bencher; use crate::boxed::Box; +use test::Bencher; #[test] fn allocate_zeroed() { unsafe { let layout = Layout::from_size_align(1024, 1).unwrap(); - let ptr = Global.alloc_zeroed(layout.clone()) - .unwrap_or_else(|_| handle_alloc_error(layout)); + let ptr = + Global.alloc_zeroed(layout.clone()).unwrap_or_else(|_| handle_alloc_error(layout)); let mut i = ptr.cast::<u8>().as_ptr(); let end = i.add(layout.size()); diff --git a/src/liballoc/benches/btree/map.rs b/src/liballoc/benches/btree/map.rs index 4c17bdc3e9e..eb5f51d9adc 100644 --- a/src/liballoc/benches/btree/map.rs +++ b/src/liballoc/benches/btree/map.rs @@ -1,12 +1,12 @@ +use std::collections::BTreeMap; use std::iter::Iterator; use std::vec::Vec; -use std::collections::BTreeMap; -use rand::{Rng, seq::SliceRandom, thread_rng}; -use test::{Bencher, black_box}; +use rand::{seq::SliceRandom, thread_rng, Rng}; +use test::{black_box, Bencher}; macro_rules! map_insert_rand_bench { - ($name: ident, $n: expr, $map: ident) => ( + ($name: ident, $n: expr, $map: ident) => { #[bench] pub fn $name(b: &mut Bencher) { let n: usize = $n; @@ -27,11 +27,11 @@ macro_rules! map_insert_rand_bench { }); black_box(map); } - ) + }; } macro_rules! map_insert_seq_bench { - ($name: ident, $n: expr, $map: ident) => ( + ($name: ident, $n: expr, $map: ident) => { #[bench] pub fn $name(b: &mut Bencher) { let mut map = $map::new(); @@ -50,11 +50,11 @@ macro_rules! map_insert_seq_bench { }); black_box(map); } - ) + }; } macro_rules! map_find_rand_bench { - ($name: ident, $n: expr, $map: ident) => ( + ($name: ident, $n: expr, $map: ident) => { #[bench] pub fn $name(b: &mut Bencher) { let mut map = $map::new(); @@ -78,11 +78,11 @@ macro_rules! map_find_rand_bench { black_box(t); }) } - ) + }; } macro_rules! map_find_seq_bench { - ($name: ident, $n: expr, $map: ident) => ( + ($name: ident, $n: expr, $map: ident) => { #[bench] pub fn $name(b: &mut Bencher) { let mut map = $map::new(); @@ -101,20 +101,20 @@ macro_rules! map_find_seq_bench { black_box(x); }) } - ) + }; } -map_insert_rand_bench!{insert_rand_100, 100, BTreeMap} -map_insert_rand_bench!{insert_rand_10_000, 10_000, BTreeMap} +map_insert_rand_bench! {insert_rand_100, 100, BTreeMap} +map_insert_rand_bench! {insert_rand_10_000, 10_000, BTreeMap} -map_insert_seq_bench!{insert_seq_100, 100, BTreeMap} -map_insert_seq_bench!{insert_seq_10_000, 10_000, BTreeMap} +map_insert_seq_bench! {insert_seq_100, 100, BTreeMap} +map_insert_seq_bench! {insert_seq_10_000, 10_000, BTreeMap} -map_find_rand_bench!{find_rand_100, 100, BTreeMap} -map_find_rand_bench!{find_rand_10_000, 10_000, BTreeMap} +map_find_rand_bench! {find_rand_100, 100, BTreeMap} +map_find_rand_bench! {find_rand_10_000, 10_000, BTreeMap} -map_find_seq_bench!{find_seq_100, 100, BTreeMap} -map_find_seq_bench!{find_seq_10_000, 10_000, BTreeMap} +map_find_seq_bench! {find_seq_100, 100, BTreeMap} +map_find_seq_bench! {find_seq_10_000, 10_000, BTreeMap} fn bench_iter(b: &mut Bencher, size: i32) { let mut map = BTreeMap::<i32, i32>::new(); @@ -145,3 +145,28 @@ pub fn iter_1000(b: &mut Bencher) { pub fn iter_100000(b: &mut Bencher) { bench_iter(b, 100000); } + +fn bench_first_and_last(b: &mut Bencher, size: i32) { + let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); + b.iter(|| { + for _ in 0..10 { + black_box(map.first_key_value()); + black_box(map.last_key_value()); + } + }); +} + +#[bench] +pub fn first_and_last_0(b: &mut Bencher) { + bench_first_and_last(b, 0); +} + +#[bench] +pub fn first_and_last_100(b: &mut Bencher) { + bench_first_and_last(b, 100); +} + +#[bench] +pub fn first_and_last_10k(b: &mut Bencher) { + bench_first_and_last(b, 10_000); +} diff --git a/src/liballoc/benches/btree/set.rs b/src/liballoc/benches/btree/set.rs index 6357ea3ea11..18502ded308 100644 --- a/src/liballoc/benches/btree/set.rs +++ b/src/liballoc/benches/btree/set.rs @@ -1,7 +1,7 @@ use std::collections::BTreeSet; use rand::{thread_rng, Rng}; -use test::{black_box, Bencher}; +use test::Bencher; fn random(n: usize) -> BTreeSet<usize> { let mut rng = thread_rng(); @@ -31,7 +31,6 @@ fn pos(n: usize) -> BTreeSet<i32> { set } - fn stagger(n1: usize, factor: usize) -> [BTreeSet<u32>; 2] { let n2 = n1 * factor; let mut sets = [BTreeSet::new(), BTreeSet::new()]; @@ -52,10 +51,7 @@ macro_rules! set_bench { let sets = $sets; // measure - b.iter(|| { - let x = sets[0].$set_func(&sets[1]).$result_func(); - black_box(x); - }) + b.iter(|| sets[0].$set_func(&sets[1]).$result_func()) } }; } diff --git a/src/liballoc/benches/lib.rs b/src/liballoc/benches/lib.rs index 4bf5ec10c41..9acda886064 100644 --- a/src/liballoc/benches/lib.rs +++ b/src/liballoc/benches/lib.rs @@ -1,3 +1,4 @@ +#![feature(map_first_last)] #![feature(repr_simd)] #![feature(test)] diff --git a/src/liballoc/benches/slice.rs b/src/liballoc/benches/slice.rs index ef91d801dc7..e20c043286e 100644 --- a/src/liballoc/benches/slice.rs +++ b/src/liballoc/benches/slice.rs @@ -1,9 +1,9 @@ use std::{mem, ptr}; +use rand::distributions::{Alphanumeric, Standard}; use rand::{thread_rng, Rng, SeedableRng}; -use rand::distributions::{Standard, Alphanumeric}; use rand_xorshift::XorShiftRng; -use test::{Bencher, black_box}; +use test::{black_box, Bencher}; #[bench] fn iterator(b: &mut Bencher) { @@ -239,7 +239,7 @@ macro_rules! sort { b.iter(|| v.clone().$f()); b.bytes = $len * mem::size_of_val(&$gen(1)[0]) as u64; } - } + }; } macro_rules! sort_strings { @@ -251,7 +251,7 @@ macro_rules! sort_strings { b.iter(|| v.clone().$f()); b.bytes = $len * mem::size_of::<&str>() as u64; } - } + }; } macro_rules! sort_expensive { @@ -273,7 +273,7 @@ macro_rules! sort_expensive { }); b.bytes = $len * mem::size_of_val(&$gen(1)[0]) as u64; } - } + }; } macro_rules! sort_lexicographic { @@ -284,7 +284,7 @@ macro_rules! sort_lexicographic { b.iter(|| v.clone().$f(|x| x.to_string())); b.bytes = $len * mem::size_of_val(&$gen(1)[0]) as u64; } - } + }; } sort!(sort, sort_small_ascending, gen_ascending, 10); @@ -325,24 +325,25 @@ macro_rules! reverse { fn $name(b: &mut Bencher) { // odd length and offset by 1 to be as unaligned as possible let n = 0xFFFFF; - let mut v: Vec<_> = - (0..1+(n / mem::size_of::<$ty>() as u64)) - .map($f) - .collect(); + let mut v: Vec<_> = (0..1 + (n / mem::size_of::<$ty>() as u64)).map($f).collect(); b.iter(|| black_box(&mut v[1..]).reverse()); b.bytes = n; } - } + }; } reverse!(reverse_u8, u8, |x| x as u8); reverse!(reverse_u16, u16, |x| x as u16); -reverse!(reverse_u8x3, [u8;3], |x| [x as u8, (x>>8) as u8, (x>>16) as u8]); +reverse!(reverse_u8x3, [u8; 3], |x| [x as u8, (x >> 8) as u8, (x >> 16) as u8]); reverse!(reverse_u32, u32, |x| x as u32); reverse!(reverse_u64, u64, |x| x as u64); reverse!(reverse_u128, u128, |x| x as u128); -#[repr(simd)] struct F64x4(f64, f64, f64, f64); -reverse!(reverse_simd_f64x4, F64x4, |x| { let x = x as f64; F64x4(x,x,x,x) }); +#[repr(simd)] +struct F64x4(f64, f64, f64, f64); +reverse!(reverse_simd_f64x4, F64x4, |x| { + let x = x as f64; + F64x4(x, x, x, x) +}); macro_rules! rotate { ($name:ident, $gen:expr, $len:expr, $mid:expr) => { @@ -350,32 +351,32 @@ macro_rules! rotate { fn $name(b: &mut Bencher) { let size = mem::size_of_val(&$gen(1)[0]); let mut v = $gen($len * 8 / size); - b.iter(|| black_box(&mut v).rotate_left(($mid*8+size-1)/size)); + b.iter(|| black_box(&mut v).rotate_left(($mid * 8 + size - 1) / size)); b.bytes = (v.len() * size) as u64; } - } + }; } rotate!(rotate_tiny_by1, gen_random, 16, 1); -rotate!(rotate_tiny_half, gen_random, 16, 16/2); -rotate!(rotate_tiny_half_plus_one, gen_random, 16, 16/2+1); +rotate!(rotate_tiny_half, gen_random, 16, 16 / 2); +rotate!(rotate_tiny_half_plus_one, gen_random, 16, 16 / 2 + 1); rotate!(rotate_medium_by1, gen_random, 9158, 1); rotate!(rotate_medium_by727_u64, gen_random, 9158, 727); rotate!(rotate_medium_by727_bytes, gen_random_bytes, 9158, 727); rotate!(rotate_medium_by727_strings, gen_strings, 9158, 727); -rotate!(rotate_medium_half, gen_random, 9158, 9158/2); -rotate!(rotate_medium_half_plus_one, gen_random, 9158, 9158/2+1); +rotate!(rotate_medium_half, gen_random, 9158, 9158 / 2); +rotate!(rotate_medium_half_plus_one, gen_random, 9158, 9158 / 2 + 1); // Intended to use more RAM than the machine has cache -rotate!(rotate_huge_by1, gen_random, 5*1024*1024, 1); -rotate!(rotate_huge_by9199_u64, gen_random, 5*1024*1024, 9199); -rotate!(rotate_huge_by9199_bytes, gen_random_bytes, 5*1024*1024, 9199); -rotate!(rotate_huge_by9199_strings, gen_strings, 5*1024*1024, 9199); -rotate!(rotate_huge_by9199_big, gen_big_random, 5*1024*1024, 9199); -rotate!(rotate_huge_by1234577_u64, gen_random, 5*1024*1024, 1234577); -rotate!(rotate_huge_by1234577_bytes, gen_random_bytes, 5*1024*1024, 1234577); -rotate!(rotate_huge_by1234577_strings, gen_strings, 5*1024*1024, 1234577); -rotate!(rotate_huge_by1234577_big, gen_big_random, 5*1024*1024, 1234577); -rotate!(rotate_huge_half, gen_random, 5*1024*1024, 5*1024*1024/2); -rotate!(rotate_huge_half_plus_one, gen_random, 5*1024*1024, 5*1024*1024/2+1); +rotate!(rotate_huge_by1, gen_random, 5 * 1024 * 1024, 1); +rotate!(rotate_huge_by9199_u64, gen_random, 5 * 1024 * 1024, 9199); +rotate!(rotate_huge_by9199_bytes, gen_random_bytes, 5 * 1024 * 1024, 9199); +rotate!(rotate_huge_by9199_strings, gen_strings, 5 * 1024 * 1024, 9199); +rotate!(rotate_huge_by9199_big, gen_big_random, 5 * 1024 * 1024, 9199); +rotate!(rotate_huge_by1234577_u64, gen_random, 5 * 1024 * 1024, 1234577); +rotate!(rotate_huge_by1234577_bytes, gen_random_bytes, 5 * 1024 * 1024, 1234577); +rotate!(rotate_huge_by1234577_strings, gen_strings, 5 * 1024 * 1024, 1234577); +rotate!(rotate_huge_by1234577_big, gen_big_random, 5 * 1024 * 1024, 1234577); +rotate!(rotate_huge_half, gen_random, 5 * 1024 * 1024, 5 * 1024 * 1024 / 2); +rotate!(rotate_huge_half_plus_one, gen_random, 5 * 1024 * 1024, 5 * 1024 * 1024 / 2 + 1); diff --git a/src/liballoc/benches/str.rs b/src/liballoc/benches/str.rs index 7f8661bd968..391475bc0c7 100644 --- a/src/liballoc/benches/str.rs +++ b/src/liballoc/benches/str.rs @@ -1,4 +1,4 @@ -use test::{Bencher, black_box}; +use test::{black_box, Bencher}; #[bench] fn char_iterator(b: &mut Bencher) { @@ -12,7 +12,9 @@ fn char_iterator_for(b: &mut Bencher) { let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb"; b.iter(|| { - for ch in s.chars() { black_box(ch); } + for ch in s.chars() { + black_box(ch); + } }); } @@ -40,7 +42,9 @@ fn char_iterator_rev_for(b: &mut Bencher) { let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb"; b.iter(|| { - for ch in s.chars().rev() { black_box(ch); } + for ch in s.chars().rev() { + black_box(ch); + } }); } @@ -79,7 +83,9 @@ fn split_ascii(b: &mut Bencher) { fn split_extern_fn(b: &mut Bencher) { let s = "Mary had a little lamb, Little lamb, little-lamb."; let len = s.split(' ').count(); - fn pred(c: char) -> bool { c == ' ' } + fn pred(c: char) -> bool { + c == ' ' + } b.iter(|| assert_eq!(s.split(pred).count(), len)); } @@ -185,16 +191,19 @@ fn bench_contains_equal(b: &mut Bencher) { }) } - macro_rules! make_test_inner { ($s:ident, $code:expr, $name:ident, $str:expr, $iters:expr) => { #[bench] fn $name(bencher: &mut Bencher) { let mut $s = $str; black_box(&mut $s); - bencher.iter(|| for _ in 0..$iters { black_box($code); }); + bencher.iter(|| { + for _ in 0..$iters { + black_box($code); + } + }); } - } + }; } macro_rules! make_test { @@ -261,15 +270,9 @@ make_test!(match_indices_a_str, s, s.match_indices("a").count()); make_test!(split_a_str, s, s.split("a").count()); -make_test!(trim_ascii_char, s, { - s.trim_matches(|c: char| c.is_ascii()) -}); -make_test!(trim_start_ascii_char, s, { - s.trim_start_matches(|c: char| c.is_ascii()) -}); -make_test!(trim_end_ascii_char, s, { - s.trim_end_matches(|c: char| c.is_ascii()) -}); +make_test!(trim_ascii_char, s, { s.trim_matches(|c: char| c.is_ascii()) }); +make_test!(trim_start_ascii_char, s, { s.trim_start_matches(|c: char| c.is_ascii()) }); +make_test!(trim_end_ascii_char, s, { s.trim_end_matches(|c: char| c.is_ascii()) }); make_test!(find_underscore_char, s, s.find('_')); make_test!(rfind_underscore_char, s, s.rfind('_')); diff --git a/src/liballoc/benches/vec_deque.rs b/src/liballoc/benches/vec_deque.rs index 7d2d3cfa612..bf2dffd1e93 100644 --- a/src/liballoc/benches/vec_deque.rs +++ b/src/liballoc/benches/vec_deque.rs @@ -1,5 +1,5 @@ use std::collections::VecDeque; -use test::{Bencher, black_box}; +use test::{black_box, Bencher}; #[bench] fn bench_new(b: &mut Bencher) { diff --git a/src/liballoc/benches/vec_deque_append.rs b/src/liballoc/benches/vec_deque_append.rs index 78ec91d9e3e..5825bdc355f 100644 --- a/src/liballoc/benches/vec_deque_append.rs +++ b/src/liballoc/benches/vec_deque_append.rs @@ -30,8 +30,5 @@ fn main() { assert!(BENCH_N % 2 == 0); let median = (durations[(l / 2) - 1] + durations[l / 2]) / 2; - println!( - "\ncustom-bench vec_deque_append {:?} ns/iter\n", - median.as_nanos() - ); + println!("\ncustom-bench vec_deque_append {:?} ns/iter\n", median.as_nanos()); } diff --git a/src/liballoc/boxed.rs b/src/liballoc/boxed.rs index 567b8ea7224..51ad3a04e87 100644 --- a/src/liballoc/boxed.rs +++ b/src/liballoc/boxed.rs @@ -152,6 +152,33 @@ impl<T> Box<T> { Box(ptr.cast().into()) } + /// Constructs a new `Box` with uninitialized contents, with the memory + /// being filled with `0` bytes. + /// + /// See [`MaybeUninit::zeroed`][zeroed] for examples of correct and incorrect usage + /// of this method. + /// + /// # Examples + /// + /// ``` + /// #![feature(new_uninit)] + /// + /// let zero = Box::<u32>::new_zeroed(); + /// let zero = unsafe { zero.assume_init() }; + /// + /// assert_eq!(*zero, 0) + /// ``` + /// + /// [zeroed]: ../../std/mem/union.MaybeUninit.html#method.zeroed + #[unstable(feature = "new_uninit", issue = "63291")] + pub fn new_zeroed() -> Box<mem::MaybeUninit<T>> { + unsafe { + let mut uninit = Self::new_uninit(); + ptr::write_bytes::<T>(uninit.as_mut_ptr(), 0, 1); + uninit + } + } + /// Constructs a new `Pin<Box<T>>`. If `T` does not implement `Unpin`, then /// `x` will be pinned in memory and unable to be moved. #[stable(feature = "pin", since = "1.33.0")] diff --git a/src/liballoc/collections/btree/map.rs b/src/liballoc/collections/btree/map.rs index 83fd4485f73..5b48b594ff9 100644 --- a/src/liballoc/collections/btree/map.rs +++ b/src/liballoc/collections/btree/map.rs @@ -598,6 +598,121 @@ impl<K: Ord, V> BTreeMap<K, V> { } } + /// Returns the first key-value pair in the map. + /// The key in this pair is the minimum key in the map. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(map_first_last)] + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// assert_eq!(map.first_key_value(), None); + /// map.insert(1, "b"); + /// map.insert(2, "a"); + /// assert_eq!(map.first_key_value(), Some((&1, &"b"))); + /// ``` + #[unstable(feature = "map_first_last", issue = "62924")] + pub fn first_key_value<T: ?Sized>(&self) -> Option<(&K, &V)> + where T: Ord, K: Borrow<T> + { + let front = first_leaf_edge(self.root.as_ref()); + front.right_kv().ok().map(Handle::into_kv) + } + + /// Returns the first entry in the map for in-place manipulation. + /// The key of this entry is the minimum key in the map. + /// + /// # Examples + /// + /// Contrived way to `clear` a map: + /// + /// ``` + /// #![feature(map_first_last)] + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// map.insert(1, "a"); + /// map.insert(2, "b"); + /// while let Some(entry) = map.first_entry() { + /// let (key, val) = entry.remove_entry(); + /// assert!(!map.contains_key(&key)); + /// } + /// ``` + #[unstable(feature = "map_first_last", issue = "62924")] + pub fn first_entry<T: ?Sized>(&mut self) -> Option<OccupiedEntry<'_, K, V>> + where T: Ord, K: Borrow<T> + { + match self.length { + 0 => None, + _ => Some(OccupiedEntry { + handle: self.root.as_mut().first_kv(), + length: &mut self.length, + _marker: PhantomData, + }), + } + } + + /// Returns the last key-value pair in the map. + /// The key in this pair is the maximum key in the map. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(map_first_last)] + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// map.insert(1, "b"); + /// map.insert(2, "a"); + /// assert_eq!(map.last_key_value(), Some((&2, &"a"))); + /// ``` + #[unstable(feature = "map_first_last", issue = "62924")] + pub fn last_key_value<T: ?Sized>(&self) -> Option<(&K, &V)> + where T: Ord, K: Borrow<T> + { + let back = last_leaf_edge(self.root.as_ref()); + back.left_kv().ok().map(Handle::into_kv) + } + + /// Returns the last entry in the map for in-place manipulation. + /// The key of this entry is the maximum key in the map. + /// + /// # Examples + /// + /// Contrived way to `clear` a map: + /// + /// ``` + /// #![feature(map_first_last)] + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// map.insert(1, "a"); + /// map.insert(2, "b"); + /// while let Some(entry) = map.last_entry() { + /// let (key, val) = entry.remove_entry(); + /// assert!(!map.contains_key(&key)); + /// } + /// ``` + #[unstable(feature = "map_first_last", issue = "62924")] + pub fn last_entry<T: ?Sized>(&mut self) -> Option<OccupiedEntry<'_, K, V>> + where T: Ord, K: Borrow<T> + { + match self.length { + 0 => None, + _ => Some(OccupiedEntry { + handle: self.root.as_mut().last_kv(), + length: &mut self.length, + _marker: PhantomData, + }), + } + } + /// Returns `true` if the map contains a value for the specified key. /// /// The key may be any borrowed form of the map's key type, but the ordering diff --git a/src/liballoc/collections/btree/mod.rs b/src/liballoc/collections/btree/mod.rs index 8b7dc07063b..f73a24d0991 100644 --- a/src/liballoc/collections/btree/mod.rs +++ b/src/liballoc/collections/btree/mod.rs @@ -1,6 +1,6 @@ +pub mod map; mod node; mod search; -pub mod map; pub mod set; #[doc(hidden)] diff --git a/src/liballoc/collections/btree/node.rs b/src/liballoc/collections/btree/node.rs index 0b5a271dbea..ab010b35f6a 100644 --- a/src/liballoc/collections/btree/node.rs +++ b/src/liballoc/collections/btree/node.rs @@ -596,7 +596,7 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> { // (We might be one-past-the-end, but that is allowed by LLVM.) // Getting the pointer is tricky though. `NodeHeader` does not have a `keys` // field because we want its size to not depend on the alignment of `K` - // (needed becuase `as_header` should be safe). We cannot call `as_leaf` + // (needed because `as_header` should be safe). We cannot call `as_leaf` // because we might be the shared root. // For this reason, `NodeHeader` has this `K2` parameter (that's usually `()` // and hence just adds a size-0-align-1 field, not affecting layout). diff --git a/src/liballoc/collections/btree/search.rs b/src/liballoc/collections/btree/search.rs index dfb67d2ea57..3f3c49a2ef8 100644 --- a/src/liballoc/collections/btree/search.rs +++ b/src/liballoc/collections/btree/search.rs @@ -1,21 +1,23 @@ use core::borrow::Borrow; use core::cmp::Ordering; -use super::node::{Handle, NodeRef, marker, ForceResult::*}; +use super::node::{marker, ForceResult::*, Handle, NodeRef}; use SearchResult::*; pub enum SearchResult<BorrowType, K, V, FoundType, GoDownType> { Found(Handle<NodeRef<BorrowType, K, V, FoundType>, marker::KV>), - GoDown(Handle<NodeRef<BorrowType, K, V, GoDownType>, marker::Edge>) + GoDown(Handle<NodeRef<BorrowType, K, V, GoDownType>, marker::Edge>), } pub fn search_tree<BorrowType, K, V, Q: ?Sized>( mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>, - key: &Q + key: &Q, ) -> SearchResult<BorrowType, K, V, marker::LeafOrInternal, marker::Leaf> - where Q: Ord, K: Borrow<Q> { - +where + Q: Ord, + K: Borrow<Q>, +{ loop { match search_node(node, key) { Found(handle) => return Found(handle), @@ -25,38 +27,38 @@ pub fn search_tree<BorrowType, K, V, Q: ?Sized>( node = internal.descend(); continue; } - } + }, } } } pub fn search_node<BorrowType, K, V, Type, Q: ?Sized>( node: NodeRef<BorrowType, K, V, Type>, - key: &Q + key: &Q, ) -> SearchResult<BorrowType, K, V, Type, Type> - where Q: Ord, K: Borrow<Q> { - +where + Q: Ord, + K: Borrow<Q>, +{ match search_linear(&node, key) { - (idx, true) => Found( - Handle::new_kv(node, idx) - ), - (idx, false) => SearchResult::GoDown( - Handle::new_edge(node, idx) - ) + (idx, true) => Found(Handle::new_kv(node, idx)), + (idx, false) => SearchResult::GoDown(Handle::new_edge(node, idx)), } } pub fn search_linear<BorrowType, K, V, Type, Q: ?Sized>( node: &NodeRef<BorrowType, K, V, Type>, - key: &Q + key: &Q, ) -> (usize, bool) - where Q: Ord, K: Borrow<Q> { - +where + Q: Ord, + K: Borrow<Q>, +{ for (i, k) in node.keys().iter().enumerate() { match key.cmp(k.borrow()) { - Ordering::Greater => {}, + Ordering::Greater => {} Ordering::Equal => return (i, true), - Ordering::Less => return (i, false) + Ordering::Less => return (i, false), } } (node.keys().len(), false) diff --git a/src/liballoc/collections/btree/set.rs b/src/liballoc/collections/btree/set.rs index f0796354e00..85b93e0eda4 100644 --- a/src/liballoc/collections/btree/set.rs +++ b/src/liballoc/collections/btree/set.rs @@ -194,16 +194,16 @@ pub struct Difference<'a, T: 'a> { #[derive(Debug)] enum DifferenceInner<'a, T: 'a> { Stitch { - // iterate all of self and some of other, spotting matches along the way + // iterate all of `self` and some of `other`, spotting matches along the way self_iter: Iter<'a, T>, other_iter: Peekable<Iter<'a, T>>, }, Search { - // iterate a small set, look up in the large set + // iterate `self`, look up in `other` self_iter: Iter<'a, T>, other_set: &'a BTreeSet<T>, }, - Iterate(Iter<'a, T>), // simply stream self's elements + Iterate(Iter<'a, T>), // simply produce all values in `self` } #[stable(feature = "collection_debug", since = "1.17.0")] @@ -356,7 +356,7 @@ impl<T: Ord> BTreeSet<T> { #[stable(feature = "rust1", since = "1.0.0")] pub fn difference<'a>(&'a self, other: &'a BTreeSet<T>) -> Difference<'a, T> { let (self_min, self_max) = if let (Some(self_min), Some(self_max)) = - (self.iter().next(), self.iter().next_back()) + (self.first(), self.last()) { (self_min, self_max) } else { @@ -365,7 +365,7 @@ impl<T: Ord> BTreeSet<T> { }; }; let (other_min, other_max) = if let (Some(other_min), Some(other_max)) = - (other.iter().next(), other.iter().next_back()) + (other.first(), other.last()) { (other_min, other_max) } else { @@ -450,7 +450,7 @@ impl<T: Ord> BTreeSet<T> { #[stable(feature = "rust1", since = "1.0.0")] pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T>) -> Intersection<'a, T> { let (self_min, self_max) = if let (Some(self_min), Some(self_max)) = - (self.iter().next(), self.iter().next_back()) + (self.first(), self.last()) { (self_min, self_max) } else { @@ -459,7 +459,7 @@ impl<T: Ord> BTreeSet<T> { }; }; let (other_min, other_max) = if let (Some(other_min), Some(other_max)) = - (other.iter().next(), other.iter().next_back()) + (other.first(), other.last()) { (other_min, other_max) } else { @@ -625,14 +625,14 @@ impl<T: Ord> BTreeSet<T> { return false; } let (self_min, self_max) = if let (Some(self_min), Some(self_max)) = - (self.iter().next(), self.iter().next_back()) + (self.first(), self.last()) { (self_min, self_max) } else { return true; // self is empty }; let (other_min, other_max) = if let (Some(other_min), Some(other_max)) = - (other.iter().next(), other.iter().next_back()) + (other.first(), other.last()) { (other_min, other_max) } else { @@ -654,14 +654,12 @@ impl<T: Ord> BTreeSet<T> { Less => (), } if self_iter.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF { - // Big difference in number of elements. for next in self_iter { if !other.contains(next) { return false; } } } else { - // Self is not much smaller than other set. let mut other_iter = other.iter(); other_iter.next(); other_iter.next_back(); @@ -702,6 +700,96 @@ impl<T: Ord> BTreeSet<T> { other.is_subset(self) } + /// Returns a reference to the first value in the set, if any. + /// This value is always the minimum of all values in the set. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(map_first_last)] + /// use std::collections::BTreeSet; + /// + /// let mut map = BTreeSet::new(); + /// assert_eq!(map.first(), None); + /// map.insert(1); + /// assert_eq!(map.first(), Some(&1)); + /// map.insert(2); + /// assert_eq!(map.first(), Some(&1)); + /// ``` + #[unstable(feature = "map_first_last", issue = "62924")] + pub fn first(&self) -> Option<&T> { + self.map.first_key_value().map(|(k, _)| k) + } + + /// Returns a reference to the last value in the set, if any. + /// This value is always the maximum of all values in the set. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(map_first_last)] + /// use std::collections::BTreeSet; + /// + /// let mut map = BTreeSet::new(); + /// assert_eq!(map.first(), None); + /// map.insert(1); + /// assert_eq!(map.last(), Some(&1)); + /// map.insert(2); + /// assert_eq!(map.last(), Some(&2)); + /// ``` + #[unstable(feature = "map_first_last", issue = "62924")] + pub fn last(&self) -> Option<&T> { + self.map.last_key_value().map(|(k, _)| k) + } + + /// Removes the first value from the set and returns it, if any. + /// The first value is always the minimum value in the set. + /// + /// # Examples + /// + /// ``` + /// #![feature(map_first_last)] + /// use std::collections::BTreeSet; + /// + /// let mut set = BTreeSet::new(); + /// + /// set.insert(1); + /// while let Some(n) = set.pop_first() { + /// assert_eq!(n, 1); + /// } + /// assert!(set.is_empty()); + /// ``` + #[unstable(feature = "map_first_last", issue = "62924")] + pub fn pop_first(&mut self) -> Option<T> { + self.map.first_entry().map(|entry| entry.remove_entry().0) + } + + /// Removes the last value from the set and returns it, if any. + /// The last value is always the maximum value in the set. + /// + /// # Examples + /// + /// ``` + /// #![feature(map_first_last)] + /// use std::collections::BTreeSet; + /// + /// let mut set = BTreeSet::new(); + /// + /// set.insert(1); + /// while let Some(n) = set.pop_last() { + /// assert_eq!(n, 1); + /// } + /// assert!(set.is_empty()); + /// ``` + #[unstable(feature = "map_first_last", issue = "62924")] + pub fn pop_last(&mut self) -> Option<T> { + self.map.last_entry().map(|entry| entry.remove_entry().0) + } + /// Adds a value to the set. /// /// If the set did not have this value present, `true` is returned. diff --git a/src/liballoc/collections/linked_list/tests.rs b/src/liballoc/collections/linked_list/tests.rs index 1001f6bba3b..94b92df1294 100644 --- a/src/liballoc/collections/linked_list/tests.rs +++ b/src/liballoc/collections/linked_list/tests.rs @@ -177,8 +177,7 @@ fn test_insert_prev() { } check_links(&m); assert_eq!(m.len(), 3 + len * 2); - assert_eq!(m.into_iter().collect::<Vec<_>>(), - [-2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1]); + assert_eq!(m.into_iter().collect::<Vec<_>>(), [-2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1]); } #[test] @@ -187,13 +186,13 @@ fn test_insert_prev() { fn test_send() { let n = list_from(&[1, 2, 3]); thread::spawn(move || { - check_links(&n); - let a: &[_] = &[&1, &2, &3]; - assert_eq!(a, &*n.iter().collect::<Vec<_>>()); - }) - .join() - .ok() - .unwrap(); + check_links(&n); + let a: &[_] = &[&1, &2, &3]; + assert_eq!(a, &*n.iter().collect::<Vec<_>>()); + }) + .join() + .ok() + .unwrap(); } #[test] diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs index 8f3dfabd888..7795083e058 100644 --- a/src/liballoc/collections/vec_deque.rs +++ b/src/liballoc/collections/vec_deque.rs @@ -835,7 +835,8 @@ impl<T> VecDeque<T> { } } - /// Shortens the `VecDeque`, dropping excess elements from the back. + /// Shortens the `VecDeque`, keeping the first `len` elements and dropping + /// the rest. /// /// If `len` is greater than the `VecDeque`'s current length, this has no /// effect. @@ -855,8 +856,31 @@ impl<T> VecDeque<T> { /// ``` #[stable(feature = "deque_extras", since = "1.16.0")] pub fn truncate(&mut self, len: usize) { - for _ in len..self.len() { - self.pop_back(); + // Safe because: + // + // * Any slice passed to `drop_in_place` is valid; the second case has + // `len <= front.len()` and returning on `len > self.len()` ensures + // `begin <= back.len()` in the first case + // * The head of the VecDeque is moved before calling `drop_in_place`, + // so no value is dropped twice if `drop_in_place` panics + unsafe { + if len > self.len() { + return; + } + let num_dropped = self.len() - len; + let (front, back) = self.as_mut_slices(); + if len > front.len() { + let begin = len - front.len(); + let drop_back = back.get_unchecked_mut(begin..) as *mut _; + self.head = self.wrap_sub(self.head, num_dropped); + ptr::drop_in_place(drop_back); + } else { + let drop_back = back as *mut _; + let drop_front = front.get_unchecked_mut(len..) as *mut _; + self.head = self.wrap_sub(self.head, num_dropped); + ptr::drop_in_place(drop_front); + ptr::drop_in_place(drop_back); + } } } @@ -1117,7 +1141,7 @@ impl<T> VecDeque<T> { #[stable(feature = "rust1", since = "1.0.0")] #[inline] pub fn clear(&mut self) { - self.drain(..); + self.truncate(0); } /// Returns `true` if the `VecDeque` contains an element equal to the diff --git a/src/liballoc/collections/vec_deque/tests.rs b/src/liballoc/collections/vec_deque/tests.rs index d578ee0dac4..8dc097cc088 100644 --- a/src/liballoc/collections/vec_deque/tests.rs +++ b/src/liballoc/collections/vec_deque/tests.rs @@ -66,11 +66,8 @@ fn test_swap_front_back_remove() { let final_len = usable_cap / 2; for len in 0..final_len { - let expected: VecDeque<_> = if back { - (0..len).collect() - } else { - (0..len).rev().collect() - }; + let expected: VecDeque<_> = + if back { (0..len).collect() } else { (0..len).rev().collect() }; for tail_pos in 0..usable_cap { tester.tail = tail_pos; tester.head = tail_pos; @@ -111,7 +108,6 @@ fn test_insert() { // this test isn't covering what it wants to let cap = tester.capacity(); - // len is the length *after* insertion for len in 1..cap { // 0, 1, 2, .., len - 1 @@ -198,9 +194,7 @@ fn test_drain() { assert!(tester.head < tester.cap()); // We should see the correct values in the VecDeque - let expected: VecDeque<_> = (0..drain_start) - .chain(drain_end..len) - .collect(); + let expected: VecDeque<_> = (0..drain_start).chain(drain_end..len).collect(); assert_eq!(expected, tester); } } @@ -385,6 +379,41 @@ fn test_clone_from() { } #[test] +fn test_vec_deque_truncate_drop() { + static mut DROPS: u32 = 0; + #[derive(Clone)] + struct Elem(i32); + impl Drop for Elem { + fn drop(&mut self) { + unsafe { + DROPS += 1; + } + } + } + + let v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)]; + for push_front in 0..=v.len() { + let v = v.clone(); + let mut tester = VecDeque::with_capacity(5); + for (index, elem) in v.into_iter().enumerate() { + if index < push_front { + tester.push_front(elem); + } else { + tester.push_back(elem); + } + } + assert_eq!(unsafe { DROPS }, 0); + tester.truncate(3); + assert_eq!(unsafe { DROPS }, 2); + tester.truncate(0); + assert_eq!(unsafe { DROPS }, 5); + unsafe { + DROPS = 0; + } + } +} + +#[test] fn issue_53529() { use crate::boxed::Box; diff --git a/src/liballoc/fmt.rs b/src/liballoc/fmt.rs index cbfc55233a1..18ebae33309 100644 --- a/src/liballoc/fmt.rs +++ b/src/liballoc/fmt.rs @@ -516,24 +516,24 @@ #[unstable(feature = "fmt_internals", issue = "0")] pub use core::fmt::rt; +#[stable(feature = "fmt_flags_align", since = "1.28.0")] +pub use core::fmt::Alignment; #[stable(feature = "rust1", since = "1.0.0")] -pub use core::fmt::{Formatter, Result, Write}; +pub use core::fmt::Error; +#[stable(feature = "rust1", since = "1.0.0")] +pub use core::fmt::{write, ArgumentV1, Arguments}; #[stable(feature = "rust1", since = "1.0.0")] pub use core::fmt::{Binary, Octal}; #[stable(feature = "rust1", since = "1.0.0")] pub use core::fmt::{Debug, Display}; #[stable(feature = "rust1", since = "1.0.0")] -pub use core::fmt::{LowerHex, Pointer, UpperHex}; -#[stable(feature = "rust1", since = "1.0.0")] -pub use core::fmt::{LowerExp, UpperExp}; +pub use core::fmt::{DebugList, DebugMap, DebugSet, DebugStruct, DebugTuple}; #[stable(feature = "rust1", since = "1.0.0")] -pub use core::fmt::Error; +pub use core::fmt::{Formatter, Result, Write}; #[stable(feature = "rust1", since = "1.0.0")] -pub use core::fmt::{write, ArgumentV1, Arguments}; +pub use core::fmt::{LowerExp, UpperExp}; #[stable(feature = "rust1", since = "1.0.0")] -pub use core::fmt::{DebugList, DebugMap, DebugSet, DebugStruct, DebugTuple}; -#[stable(feature = "fmt_flags_align", since = "1.28.0")] -pub use core::fmt::{Alignment}; +pub use core::fmt::{LowerHex, Pointer, UpperHex}; use crate::string; @@ -568,8 +568,6 @@ use crate::string; pub fn format(args: Arguments<'_>) -> string::String { let capacity = args.estimated_capacity(); let mut output = string::String::with_capacity(capacity); - output - .write_fmt(args) - .expect("a formatting trait implementation returned an error"); + output.write_fmt(args).expect("a formatting trait implementation returned an error"); output } diff --git a/src/liballoc/macros.rs b/src/liballoc/macros.rs index 2f2cdc39c63..422d3486f92 100644 --- a/src/liballoc/macros.rs +++ b/src/liballoc/macros.rs @@ -98,5 +98,8 @@ macro_rules! vec { #[macro_export] #[stable(feature = "rust1", since = "1.0.0")] macro_rules! format { - ($($arg:tt)*) => ($crate::fmt::format($crate::__export::format_args!($($arg)*))) + ($($arg:tt)*) => {{ + let res = $crate::fmt::format($crate::__export::format_args!($($arg)*)); + res + }} } diff --git a/src/liballoc/prelude/v1.rs b/src/liballoc/prelude/v1.rs index 3cb285bf049..6a53b4ca1f6 100644 --- a/src/liballoc/prelude/v1.rs +++ b/src/liballoc/prelude/v1.rs @@ -4,7 +4,11 @@ #![unstable(feature = "alloc_prelude", issue = "58935")] -#[unstable(feature = "alloc_prelude", issue = "58935")] pub use crate::borrow::ToOwned; -#[unstable(feature = "alloc_prelude", issue = "58935")] pub use crate::boxed::Box; -#[unstable(feature = "alloc_prelude", issue = "58935")] pub use crate::string::{String, ToString}; -#[unstable(feature = "alloc_prelude", issue = "58935")] pub use crate::vec::Vec; +#[unstable(feature = "alloc_prelude", issue = "58935")] +pub use crate::borrow::ToOwned; +#[unstable(feature = "alloc_prelude", issue = "58935")] +pub use crate::boxed::Box; +#[unstable(feature = "alloc_prelude", issue = "58935")] +pub use crate::string::{String, ToString}; +#[unstable(feature = "alloc_prelude", issue = "58935")] +pub use crate::vec::Vec; diff --git a/src/liballoc/raw_vec/tests.rs b/src/liballoc/raw_vec/tests.rs index d35b62fc1ef..b214cef3011 100644 --- a/src/liballoc/raw_vec/tests.rs +++ b/src/liballoc/raw_vec/tests.rs @@ -16,7 +16,9 @@ fn allocator_param() { // A dumb allocator that consumes a fixed amount of fuel // before allocation attempts start failing. - struct BoundedAlloc { fuel: usize } + struct BoundedAlloc { + fuel: usize, + } unsafe impl Alloc for BoundedAlloc { unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> { let size = layout.size(); @@ -24,7 +26,10 @@ fn allocator_param() { return Err(AllocErr); } match Global.alloc(layout) { - ok @ Ok(_) => { self.fuel -= size; ok } + ok @ Ok(_) => { + self.fuel -= size; + ok + } err @ Err(_) => err, } } diff --git a/src/liballoc/rc.rs b/src/liballoc/rc.rs index a11f9e8c145..1ff1c3c834f 100644 --- a/src/liballoc/rc.rs +++ b/src/liballoc/rc.rs @@ -361,6 +361,35 @@ impl<T> Rc<T> { } } + /// Constructs a new `Rc` with uninitialized contents, with the memory + /// being filled with `0` bytes. + /// + /// See [`MaybeUninit::zeroed`][zeroed] for examples of correct and + /// incorrect usage of this method. + /// + /// # Examples + /// + /// ``` + /// #![feature(new_uninit)] + /// + /// use std::rc::Rc; + /// + /// let zero = Rc::<u32>::new_zeroed(); + /// let zero = unsafe { zero.assume_init() }; + /// + /// assert_eq!(*zero, 0) + /// ``` + /// + /// [zeroed]: ../../std/mem/union.MaybeUninit.html#method.zeroed + #[unstable(feature = "new_uninit", issue = "63291")] + pub fn new_zeroed() -> Rc<mem::MaybeUninit<T>> { + unsafe { + let mut uninit = Self::new_uninit(); + ptr::write_bytes::<T>(Rc::get_mut_unchecked(&mut uninit).as_mut_ptr(), 0, 1); + uninit + } + } + /// Constructs a new `Pin<Rc<T>>`. If `T` does not implement `Unpin`, then /// `value` will be pinned in memory and unable to be moved. #[stable(feature = "pin", since = "1.33.0")] @@ -897,7 +926,7 @@ impl<T: ?Sized> Rc<T> { // reference (see #54908). let layout = Layout::new::<RcBox<()>>() .extend(value_layout).unwrap().0 - .pad_to_align().unwrap(); + .pad_to_align(); // Allocate for the layout. let mem = Global.alloc(layout) @@ -1619,10 +1648,8 @@ impl<T> Weak<T> { /// Returns a raw pointer to the object `T` pointed to by this `Weak<T>`. /// - /// It is up to the caller to ensure that the object is still alive when accessing it through - /// the pointer. - /// - /// The pointer may be [`null`] or be dangling in case the object has already been destroyed. + /// The pointer is valid only if there are some strong references. The pointer may be dangling + /// or even [`null`] otherwise. /// /// # Examples /// @@ -1702,14 +1729,18 @@ impl<T> Weak<T> { /// This can be used to safely get a strong reference (by calling [`upgrade`] /// later) or to deallocate the weak count by dropping the `Weak<T>`. /// - /// It takes ownership of one weak count. In case a [`null`] is passed, a dangling [`Weak`] is - /// returned. + /// It takes ownership of one weak count (with the exception of pointers created by [`new`], + /// as these don't have any corresponding weak count). /// /// # Safety /// - /// The pointer must represent one valid weak count. In other words, it must point to `T` which - /// is or *was* managed by an [`Rc`] and the weak count of that [`Rc`] must not have reached - /// 0. It is allowed for the strong count to be 0. + /// The pointer must have originated from the [`into_raw`] (or [`as_raw`], provided there was + /// a corresponding [`forget`] on the `Weak<T>`) and must still own its potential weak reference + /// count. + /// + /// It is allowed for the strong count to be 0 at the time of calling this, but the weak count + /// must be non-zero or the pointer must have originated from a dangling `Weak<T>` (one created + /// by [`new`]). /// /// # Examples /// @@ -1734,11 +1765,13 @@ impl<T> Weak<T> { /// assert!(unsafe { Weak::from_raw(raw_2) }.upgrade().is_none()); /// ``` /// - /// [`null`]: ../../std/ptr/fn.null.html /// [`into_raw`]: struct.Weak.html#method.into_raw /// [`upgrade`]: struct.Weak.html#method.upgrade /// [`Rc`]: struct.Rc.html /// [`Weak`]: struct.Weak.html + /// [`as_raw`]: struct.Weak.html#method.as_raw + /// [`new`]: struct.Weak.html#method.new + /// [`forget`]: ../../std/mem/fn.forget.html #[unstable(feature = "weak_into_raw", issue = "60728")] pub unsafe fn from_raw(ptr: *const T) -> Self { if ptr.is_null() { diff --git a/src/liballoc/slice.rs b/src/liballoc/slice.rs index 08243ef7c51..2f6d10c027b 100644 --- a/src/liballoc/slice.rs +++ b/src/liballoc/slice.rs @@ -82,7 +82,6 @@ //! [`.chunks`]: ../../std/primitive.slice.html#method.chunks //! [`.windows`]: ../../std/primitive.slice.html#method.windows #![stable(feature = "rust1", since = "1.0.0")] - // Many of the usings in this module are only used in the test configuration. // It's cleaner to just turn off the unused_imports warning than to fix them. #![cfg_attr(test, allow(unused_imports, dead_code))] @@ -91,32 +90,32 @@ use core::borrow::{Borrow, BorrowMut}; use core::cmp::Ordering::{self, Less}; use core::mem::{self, size_of}; use core::ptr; -use core::{u8, u16, u32}; +use core::{u16, u32, u8}; use crate::borrow::ToOwned; use crate::boxed::Box; use crate::vec::Vec; +#[stable(feature = "slice_get_slice", since = "1.28.0")] +pub use core::slice::SliceIndex; +#[stable(feature = "from_ref", since = "1.28.0")] +pub use core::slice::{from_mut, from_ref}; #[stable(feature = "rust1", since = "1.0.0")] -pub use core::slice::{Chunks, Windows}; +pub use core::slice::{from_raw_parts, from_raw_parts_mut}; #[stable(feature = "rust1", since = "1.0.0")] -pub use core::slice::{Iter, IterMut}; +pub use core::slice::{Chunks, Windows}; +#[stable(feature = "chunks_exact", since = "1.31.0")] +pub use core::slice::{ChunksExact, ChunksExactMut}; #[stable(feature = "rust1", since = "1.0.0")] -pub use core::slice::{SplitMut, ChunksMut, Split}; +pub use core::slice::{ChunksMut, Split, SplitMut}; #[stable(feature = "rust1", since = "1.0.0")] -pub use core::slice::{SplitN, RSplitN, SplitNMut, RSplitNMut}; +pub use core::slice::{Iter, IterMut}; +#[stable(feature = "rchunks", since = "1.31.0")] +pub use core::slice::{RChunks, RChunksExact, RChunksExactMut, RChunksMut}; #[stable(feature = "slice_rsplit", since = "1.27.0")] pub use core::slice::{RSplit, RSplitMut}; #[stable(feature = "rust1", since = "1.0.0")] -pub use core::slice::{from_raw_parts, from_raw_parts_mut}; -#[stable(feature = "from_ref", since = "1.28.0")] -pub use core::slice::{from_ref, from_mut}; -#[stable(feature = "slice_get_slice", since = "1.28.0")] -pub use core::slice::SliceIndex; -#[stable(feature = "chunks_exact", since = "1.31.0")] -pub use core::slice::{ChunksExact, ChunksExactMut}; -#[stable(feature = "rchunks", since = "1.31.0")] -pub use core::slice::{RChunks, RChunksMut, RChunksExact, RChunksExactMut}; +pub use core::slice::{RSplitN, RSplitNMut, SplitN, SplitNMut}; //////////////////////////////////////////////////////////////////////////////// // Basic slice extension methods @@ -138,9 +137,9 @@ pub use hack::to_vec; // `test_permutations` test mod hack { use crate::boxed::Box; - use crate::vec::Vec; #[cfg(test)] use crate::string::ToString; + use crate::vec::Vec; pub fn into_vec<T>(b: Box<[T]>) -> Vec<T> { unsafe { @@ -153,7 +152,8 @@ mod hack { #[inline] pub fn to_vec<T>(s: &[T]) -> Vec<T> - where T: Clone + where + T: Clone, { let mut vector = Vec::with_capacity(s.len()); vector.extend_from_slice(s); @@ -193,7 +193,8 @@ impl<T> [T] { #[stable(feature = "rust1", since = "1.0.0")] #[inline] pub fn sort(&mut self) - where T: Ord + where + T: Ord, { merge_sort(self, |a, b| a.lt(b)); } @@ -246,7 +247,8 @@ impl<T> [T] { #[stable(feature = "rust1", since = "1.0.0")] #[inline] pub fn sort_by<F>(&mut self, mut compare: F) - where F: FnMut(&T, &T) -> Ordering + where + F: FnMut(&T, &T) -> Ordering, { merge_sort(self, |a, b| compare(a, b) == Less); } @@ -285,7 +287,9 @@ impl<T> [T] { #[stable(feature = "slice_sort_by_key", since = "1.7.0")] #[inline] pub fn sort_by_key<K, F>(&mut self, mut f: F) - where F: FnMut(&T) -> K, K: Ord + where + F: FnMut(&T) -> K, + K: Ord, { merge_sort(self, |a, b| f(a).lt(&f(b))); } @@ -325,11 +329,13 @@ impl<T> [T] { #[stable(feature = "slice_sort_by_cached_key", since = "1.34.0")] #[inline] pub fn sort_by_cached_key<K, F>(&mut self, f: F) - where F: FnMut(&T) -> K, K: Ord + where + F: FnMut(&T) -> K, + K: Ord, { // Helper macro for indexing our vector by the smallest possible type, to reduce allocation. macro_rules! sort_by_key { - ($t:ty, $slice:ident, $f:ident) => ({ + ($t:ty, $slice:ident, $f:ident) => {{ let mut indices: Vec<_> = $slice.iter().map($f).enumerate().map(|(i, k)| (k, i as $t)).collect(); // The elements of `indices` are unique, as they are indexed, so any sort will be @@ -344,19 +350,27 @@ impl<T> [T] { indices[i].1 = index; $slice.swap(i, index as usize); } - }) + }}; } - let sz_u8 = mem::size_of::<(K, u8)>(); - let sz_u16 = mem::size_of::<(K, u16)>(); - let sz_u32 = mem::size_of::<(K, u32)>(); + let sz_u8 = mem::size_of::<(K, u8)>(); + let sz_u16 = mem::size_of::<(K, u16)>(); + let sz_u32 = mem::size_of::<(K, u32)>(); let sz_usize = mem::size_of::<(K, usize)>(); let len = self.len(); - if len < 2 { return } - if sz_u8 < sz_u16 && len <= ( u8::MAX as usize) { return sort_by_key!( u8, self, f) } - if sz_u16 < sz_u32 && len <= (u16::MAX as usize) { return sort_by_key!(u16, self, f) } - if sz_u32 < sz_usize && len <= (u32::MAX as usize) { return sort_by_key!(u32, self, f) } + if len < 2 { + return; + } + if sz_u8 < sz_u16 && len <= (u8::MAX as usize) { + return sort_by_key!(u8, self, f); + } + if sz_u16 < sz_u32 && len <= (u16::MAX as usize) { + return sort_by_key!(u16, self, f); + } + if sz_u32 < sz_usize && len <= (u32::MAX as usize) { + return sort_by_key!(u32, self, f); + } sort_by_key!(usize, self, f) } @@ -373,7 +387,8 @@ impl<T> [T] { #[stable(feature = "rust1", since = "1.0.0")] #[inline] pub fn to_vec(&self) -> Vec<T> - where T: Clone + where + T: Clone, { // N.B., see the `hack` module in this file for more details. hack::to_vec(self) @@ -421,7 +436,10 @@ impl<T> [T] { /// b"0123456789abcdef".repeat(usize::max_value()); /// ``` #[stable(feature = "repeat_generic_slice", since = "1.40.0")] - pub fn repeat(&self, n: usize) -> Vec<T> where T: Copy { + pub fn repeat(&self, n: usize) -> Vec<T> + where + T: Copy, + { if n == 0 { return Vec::new(); } @@ -486,7 +504,8 @@ impl<T> [T] { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn concat<Item: ?Sized>(&self) -> <Self as Concat<Item>>::Output - where Self: Concat<Item> + where + Self: Concat<Item>, { Concat::concat(self) } @@ -503,7 +522,8 @@ impl<T> [T] { /// ``` #[stable(feature = "rename_connect_to_join", since = "1.3.0")] pub fn join<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output - where Self: Join<Separator> + where + Self: Join<Separator>, { Join::join(self, sep) } @@ -521,11 +541,11 @@ impl<T> [T] { #[stable(feature = "rust1", since = "1.0.0")] #[rustc_deprecated(since = "1.3.0", reason = "renamed to join")] pub fn connect<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output - where Self: Join<Separator> + where + Self: Join<Separator>, { Join::join(self, sep) } - } #[lang = "slice_u8_alloc"] @@ -668,8 +688,8 @@ impl<T: Clone, V: Borrow<[T]>> Join<&[T]> for [V] { Some(first) => first, None => return vec![], }; - let size = slice.iter().map(|v| v.borrow().len()).sum::<usize>() + - sep.len() * (slice.len() - 1); + let size = + slice.iter().map(|v| v.borrow().len()).sum::<usize>() + sep.len() * (slice.len() - 1); let mut result = Vec::with_capacity(size); result.extend_from_slice(first.borrow()); @@ -734,7 +754,8 @@ impl<T: Clone> ToOwned for [T] { /// /// This is the integral subroutine of insertion sort. fn insert_head<T, F>(v: &mut [T], is_less: &mut F) - where F: FnMut(&T, &T) -> bool +where + F: FnMut(&T, &T) -> bool, { if v.len() >= 2 && is_less(&v[1], &v[0]) { unsafe { @@ -767,10 +788,7 @@ fn insert_head<T, F>(v: &mut [T], is_less: &mut F) // If `is_less` panics at any point during the process, `hole` will get dropped and // fill the hole in `v` with `tmp`, thus ensuring that `v` still holds every object it // initially held exactly once. - let mut hole = InsertionHole { - src: &mut *tmp, - dest: &mut v[1], - }; + let mut hole = InsertionHole { src: &mut *tmp, dest: &mut v[1] }; ptr::copy_nonoverlapping(&v[1], &mut v[0], 1); for i in 2..v.len() { @@ -792,7 +810,9 @@ fn insert_head<T, F>(v: &mut [T], is_less: &mut F) impl<T> Drop for InsertionHole<T> { fn drop(&mut self) { - unsafe { ptr::copy_nonoverlapping(self.src, self.dest, 1); } + unsafe { + ptr::copy_nonoverlapping(self.src, self.dest, 1); + } } } } @@ -805,7 +825,8 @@ fn insert_head<T, F>(v: &mut [T], is_less: &mut F) /// The two slices must be non-empty and `mid` must be in bounds. Buffer `buf` must be long enough /// to hold a copy of the shorter slice. Also, `T` must not be a zero-sized type. unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &mut F) - where F: FnMut(&T, &T) -> bool +where + F: FnMut(&T, &T) -> bool, { let len = v.len(); let v = v.as_mut_ptr(); @@ -834,11 +855,7 @@ unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &mut F) if mid <= len - mid { // The left run is shorter. ptr::copy_nonoverlapping(v, buf, mid); - hole = MergeHole { - start: buf, - end: buf.add(mid), - dest: v, - }; + hole = MergeHole { start: buf, end: buf.add(mid), dest: v }; // Initially, these pointers point to the beginnings of their arrays. let left = &mut hole.start; @@ -858,11 +875,7 @@ unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &mut F) } else { // The right run is shorter. ptr::copy_nonoverlapping(v_mid, buf, len - mid); - hole = MergeHole { - start: buf, - end: buf.add(len - mid), - dest: v_mid, - }; + hole = MergeHole { start: buf, end: buf.add(len - mid), dest: v_mid }; // Initially, these pointers point past the ends of their arrays. let left = &mut hole.dest; @@ -905,7 +918,9 @@ unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &mut F) fn drop(&mut self) { // `T` is not a zero-sized type, so it's okay to divide by its size. let len = (self.end as usize - self.start as usize) / mem::size_of::<T>(); - unsafe { ptr::copy_nonoverlapping(self.start, self.dest, len); } + unsafe { + ptr::copy_nonoverlapping(self.start, self.dest, len); + } } } } @@ -923,7 +938,8 @@ unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &mut F) /// /// The invariants ensure that the total running time is `O(n log n)` worst-case. fn merge_sort<T, F>(v: &mut [T], mut is_less: F) - where F: FnMut(&T, &T) -> bool +where + F: FnMut(&T, &T) -> bool, { // Slices of up to this length get sorted using insertion sort. const MAX_INSERTION: usize = 20; @@ -940,7 +956,7 @@ fn merge_sort<T, F>(v: &mut [T], mut is_less: F) // Short arrays get sorted in-place via insertion sort to avoid allocations. if len <= MAX_INSERTION { if len >= 2 { - for i in (0..len-1).rev() { + for i in (0..len - 1).rev() { insert_head(&mut v[i..], &mut is_less); } } @@ -966,14 +982,13 @@ fn merge_sort<T, F>(v: &mut [T], mut is_less: F) start -= 1; unsafe { if is_less(v.get_unchecked(start + 1), v.get_unchecked(start)) { - while start > 0 && is_less(v.get_unchecked(start), - v.get_unchecked(start - 1)) { + while start > 0 && is_less(v.get_unchecked(start), v.get_unchecked(start - 1)) { start -= 1; } v[start..end].reverse(); } else { - while start > 0 && !is_less(v.get_unchecked(start), - v.get_unchecked(start - 1)) { + while start > 0 && !is_less(v.get_unchecked(start), v.get_unchecked(start - 1)) + { start -= 1; } } @@ -988,10 +1003,7 @@ fn merge_sort<T, F>(v: &mut [T], mut is_less: F) } // Push this run onto the stack. - runs.push(Run { - start, - len: end - start, - }); + runs.push(Run { start, len: end - start }); end = start; // Merge some pairs of adjacent runs to satisfy the invariants. @@ -999,13 +1011,14 @@ fn merge_sort<T, F>(v: &mut [T], mut is_less: F) let left = runs[r + 1]; let right = runs[r]; unsafe { - merge(&mut v[left.start .. right.start + right.len], left.len, buf.as_mut_ptr(), - &mut is_less); + merge( + &mut v[left.start..right.start + right.len], + left.len, + buf.as_mut_ptr(), + &mut is_less, + ); } - runs[r] = Run { - start: left.start, - len: left.len + right.len, - }; + runs[r] = Run { start: left.start, len: left.len + right.len }; runs.remove(r + 1); } } @@ -1030,15 +1043,13 @@ fn merge_sort<T, F>(v: &mut [T], mut is_less: F) #[inline] fn collapse(runs: &[Run]) -> Option<usize> { let n = runs.len(); - if n >= 2 && (runs[n - 1].start == 0 || - runs[n - 2].len <= runs[n - 1].len || - (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len) || - (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len)) { - if n >= 3 && runs[n - 3].len < runs[n - 1].len { - Some(n - 3) - } else { - Some(n - 2) - } + if n >= 2 + && (runs[n - 1].start == 0 + || runs[n - 2].len <= runs[n - 1].len + || (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len) + || (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len)) + { + if n >= 3 && runs[n - 3].len < runs[n - 1].len { Some(n - 3) } else { Some(n - 2) } } else { None } diff --git a/src/liballoc/sync.rs b/src/liballoc/sync.rs index 4b10f089c29..19b0086fa33 100644 --- a/src/liballoc/sync.rs +++ b/src/liballoc/sync.rs @@ -341,6 +341,35 @@ impl<T> Arc<T> { } } + /// Constructs a new `Arc` with uninitialized contents, with the memory + /// being filled with `0` bytes. + /// + /// See [`MaybeUninit::zeroed`][zeroed] for examples of correct and incorrect usage + /// of this method. + /// + /// # Examples + /// + /// ``` + /// #![feature(new_uninit)] + /// + /// use std::sync::Arc; + /// + /// let zero = Arc::<u32>::new_zeroed(); + /// let zero = unsafe { zero.assume_init() }; + /// + /// assert_eq!(*zero, 0) + /// ``` + /// + /// [zeroed]: ../../std/mem/union.MaybeUninit.html#method.zeroed + #[unstable(feature = "new_uninit", issue = "63291")] + pub fn new_zeroed() -> Arc<mem::MaybeUninit<T>> { + unsafe { + let mut uninit = Self::new_uninit(); + ptr::write_bytes::<T>(Arc::get_mut_unchecked(&mut uninit).as_mut_ptr(), 0, 1); + uninit + } + } + /// Constructs a new `Pin<Arc<T>>`. If `T` does not implement `Unpin`, then /// `data` will be pinned in memory and unable to be moved. #[stable(feature = "pin", since = "1.33.0")] @@ -751,7 +780,7 @@ impl<T: ?Sized> Arc<T> { // reference (see #54908). let layout = Layout::new::<ArcInner<()>>() .extend(value_layout).unwrap().0 - .pad_to_align().unwrap(); + .pad_to_align(); let mem = Global.alloc(layout) .unwrap_or_else(|_| handle_alloc_error(layout)); @@ -1295,10 +1324,8 @@ impl<T> Weak<T> { /// Returns a raw pointer to the object `T` pointed to by this `Weak<T>`. /// - /// It is up to the caller to ensure that the object is still alive when accessing it through - /// the pointer. - /// - /// The pointer may be [`null`] or be dangling in case the object has already been destroyed. + /// The pointer is valid only if there are some strong references. The pointer may be dangling + /// or even [`null`] otherwise. /// /// # Examples /// @@ -1379,14 +1406,18 @@ impl<T> Weak<T> { /// This can be used to safely get a strong reference (by calling [`upgrade`] /// later) or to deallocate the weak count by dropping the `Weak<T>`. /// - /// It takes ownership of one weak count. In case a [`null`] is passed, a dangling [`Weak`] is - /// returned. + /// It takes ownership of one weak count (with the exception of pointers created by [`new`], + /// as these don't have any corresponding weak count). /// /// # Safety /// - /// The pointer must represent one valid weak count. In other words, it must point to `T` which - /// is or *was* managed by an [`Arc`] and the weak count of that [`Arc`] must not have reached - /// 0. It is allowed for the strong count to be 0. + /// The pointer must have originated from the [`into_raw`] (or [`as_raw'], provided there was + /// a corresponding [`forget`] on the `Weak<T>`) and must still own its potential weak reference + /// count. + /// + /// It is allowed for the strong count to be 0 at the time of calling this, but the weak count + /// must be non-zero or the pointer must have originated from a dangling `Weak<T>` (one created + /// by [`new`]). /// /// # Examples /// @@ -1411,11 +1442,13 @@ impl<T> Weak<T> { /// assert!(unsafe { Weak::from_raw(raw_2) }.upgrade().is_none()); /// ``` /// - /// [`null`]: ../../std/ptr/fn.null.html + /// [`as_raw`]: struct.Weak.html#method.as_raw + /// [`new`]: struct.Weak.html#method.new /// [`into_raw`]: struct.Weak.html#method.into_raw /// [`upgrade`]: struct.Weak.html#method.upgrade /// [`Weak`]: struct.Weak.html /// [`Arc`]: struct.Arc.html + /// [`forget`]: ../../std/mem/fn.forget.html #[unstable(feature = "weak_into_raw", issue = "60728")] pub unsafe fn from_raw(ptr: *const T) -> Self { if ptr.is_null() { diff --git a/src/liballoc/tests.rs b/src/liballoc/tests.rs index ed46ba8a1b9..1b6e0bb291c 100644 --- a/src/liballoc/tests.rs +++ b/src/liballoc/tests.rs @@ -1,12 +1,12 @@ //! Test for `boxed` mod. use core::any::Any; -use core::convert::TryInto; -use core::ops::Deref; -use core::result::Result::{Err, Ok}; use core::clone::Clone; +use core::convert::TryInto; use core::f64; use core::i64; +use core::ops::Deref; +use core::result::Result::{Err, Ok}; use std::boxed::Box; diff --git a/src/liballoc/tests/arc.rs b/src/liballoc/tests/arc.rs index cf2ad2a8e60..2fbb59b0419 100644 --- a/src/liballoc/tests/arc.rs +++ b/src/liballoc/tests/arc.rs @@ -1,9 +1,9 @@ use std::any::Any; -use std::sync::{Arc, Weak}; use std::cell::RefCell; use std::cmp::PartialEq; use std::iter::TrustedLen; use std::mem; +use std::sync::{Arc, Weak}; #[test] fn uninhabited() { @@ -12,7 +12,7 @@ fn uninhabited() { a = a.clone(); assert!(a.upgrade().is_none()); - let mut a: Weak<dyn Any> = a; // Unsizing + let mut a: Weak<dyn Any> = a; // Unsizing a = a.clone(); assert!(a.upgrade().is_none()); } @@ -20,8 +20,8 @@ fn uninhabited() { #[test] fn slice() { let a: Arc<[u32; 3]> = Arc::new([3, 2, 1]); - let a: Arc<[u32]> = a; // Unsizing - let b: Arc<[u32]> = Arc::from(&[3, 2, 1][..]); // Conversion + let a: Arc<[u32]> = a; // Unsizing + let b: Arc<[u32]> = Arc::from(&[3, 2, 1][..]); // Conversion assert_eq!(a, b); // Exercise is_dangling() with a DST @@ -33,7 +33,7 @@ fn slice() { #[test] fn trait_object() { let a: Arc<u32> = Arc::new(4); - let a: Arc<dyn Any> = a; // Unsizing + let a: Arc<dyn Any> = a; // Unsizing // Exercise is_dangling() with a DST let mut a = Arc::downgrade(&a); @@ -43,7 +43,7 @@ fn trait_object() { let mut b = Weak::<u32>::new(); b = b.clone(); assert!(b.upgrade().is_none()); - let mut b: Weak<dyn Any> = b; // Unsizing + let mut b: Weak<dyn Any> = b; // Unsizing b = b.clone(); assert!(b.upgrade().is_none()); } @@ -57,7 +57,7 @@ fn float_nan_ne() { #[test] fn partial_eq() { - struct TestPEq (RefCell<usize>); + struct TestPEq(RefCell<usize>); impl PartialEq for TestPEq { fn eq(&self, other: &TestPEq) -> bool { *self.0.borrow_mut() += 1; @@ -74,7 +74,7 @@ fn partial_eq() { #[test] fn eq() { #[derive(Eq)] - struct TestEq (RefCell<usize>); + struct TestEq(RefCell<usize>); impl PartialEq for TestEq { fn eq(&self, other: &TestEq) -> bool { *self.0.borrow_mut() += 1; @@ -160,13 +160,10 @@ fn shared_from_iter_trustedlen_normal() { fn shared_from_iter_trustedlen_panic() { // Exercise the `TrustedLen` implementation when `size_hint()` matches // `(_, Some(exact_len))` but where `.next()` drops before the last iteration. - let iter = (0..SHARED_ITER_MAX) - .map(|val| { - match val { - 98 => panic!("I've almost got 99 problems."), - _ => Box::new(val), - } - }); + let iter = (0..SHARED_ITER_MAX).map(|val| match val { + 98 => panic!("I've almost got 99 problems."), + _ => Box::new(val), + }); assert_trusted_len(&iter); let _ = iter.collect::<Rc<[_]>>(); @@ -193,16 +190,8 @@ fn shared_from_iter_trustedlen_no_fuse() { } } - let vec = vec![ - Some(Box::new(42)), - Some(Box::new(24)), - None, - Some(Box::new(12)), - ]; + let vec = vec![Some(Box::new(42)), Some(Box::new(24)), None, Some(Box::new(12))]; let iter = Iter(vec.into_iter()); assert_trusted_len(&iter); - assert_eq!( - &[Box::new(42), Box::new(24)], - &*iter.collect::<Rc<[_]>>() - ); + assert_eq!(&[Box::new(42), Box::new(24)], &*iter.collect::<Rc<[_]>>()); } diff --git a/src/liballoc/tests/binary_heap.rs b/src/liballoc/tests/binary_heap.rs index a44cf1eaf6d..a896a1064d9 100644 --- a/src/liballoc/tests/binary_heap.rs +++ b/src/liballoc/tests/binary_heap.rs @@ -347,7 +347,7 @@ fn assert_covariance() { // Destructors must be called exactly once per element. // FIXME: re-enable emscripten once it can unwind again #[test] -#[cfg(not(any(miri, target_os = "emscripten")))] // Miri does not support catching panics +#[cfg(not(target_os = "emscripten"))] fn panic_safe() { use std::cmp; use std::panic::{self, AssertUnwindSafe}; @@ -376,7 +376,10 @@ fn panic_safe() { } let mut rng = thread_rng(); const DATASZ: usize = 32; + #[cfg(not(miri))] // Miri is too slow const NTEST: usize = 10; + #[cfg(miri)] + const NTEST: usize = 1; // don't use 0 in the data -- we want to catch the zeroed-out case. let data = (1..=DATASZ).collect::<Vec<_>>(); diff --git a/src/liballoc/tests/boxed.rs b/src/liballoc/tests/boxed.rs index bc3d53bf30d..66782ecbeb7 100644 --- a/src/liballoc/tests/boxed.rs +++ b/src/liballoc/tests/boxed.rs @@ -1,5 +1,5 @@ -use std::ptr::NonNull; use std::mem::MaybeUninit; +use std::ptr::NonNull; #[test] fn unitialized_zero_size_box() { diff --git a/src/liballoc/tests/btree/map.rs b/src/liballoc/tests/btree/map.rs index 266a0d055d5..27843aeaeb0 100644 --- a/src/liballoc/tests/btree/map.rs +++ b/src/liballoc/tests/btree/map.rs @@ -58,15 +58,35 @@ fn test_basic_large() { fn test_basic_small() { let mut map = BTreeMap::new(); assert_eq!(map.remove(&1), None); + assert_eq!(map.len(), 0); + assert_eq!(map.first_key_value(), None); + assert_eq!(map.last_key_value(), None); assert_eq!(map.get(&1), None); assert_eq!(map.insert(1, 1), None); + assert_eq!(map.len(), 1); assert_eq!(map.get(&1), Some(&1)); + assert_eq!(map.first_key_value(), Some((&1, &1))); + assert_eq!(map.last_key_value(), Some((&1, &1))); assert_eq!(map.insert(1, 2), Some(1)); + assert_eq!(map.len(), 1); assert_eq!(map.get(&1), Some(&2)); + assert_eq!(map.first_key_value(), Some((&1, &2))); + assert_eq!(map.last_key_value(), Some((&1, &2))); assert_eq!(map.insert(2, 4), None); + assert_eq!(map.len(), 2); assert_eq!(map.get(&2), Some(&4)); + assert_eq!(map.first_key_value(), Some((&1, &2))); + assert_eq!(map.last_key_value(), Some((&2, &4))); assert_eq!(map.remove(&1), Some(2)); + assert_eq!(map.len(), 1); + assert_eq!(map.get(&1), None); + assert_eq!(map.get(&2), Some(&4)); + assert_eq!(map.first_key_value(), Some((&2, &4))); + assert_eq!(map.last_key_value(), Some((&2, &4))); assert_eq!(map.remove(&2), Some(4)); + assert_eq!(map.len(), 0); + assert_eq!(map.first_key_value(), None); + assert_eq!(map.last_key_value(), None); assert_eq!(map.remove(&1), None); } @@ -605,6 +625,31 @@ fn test_vacant_entry_key() { assert_eq!(a[key], value); } +#[test] +fn test_first_last_entry() { + let mut a = BTreeMap::new(); + assert!(a.first_entry().is_none()); + assert!(a.last_entry().is_none()); + a.insert(1, 42); + assert_eq!(a.first_entry().unwrap().key(), &1); + assert_eq!(a.last_entry().unwrap().key(), &1); + a.insert(2, 24); + assert_eq!(a.first_entry().unwrap().key(), &1); + assert_eq!(a.last_entry().unwrap().key(), &2); + a.insert(0, 6); + assert_eq!(a.first_entry().unwrap().key(), &0); + assert_eq!(a.last_entry().unwrap().key(), &2); + let (k1, v1) = a.first_entry().unwrap().remove_entry(); + assert_eq!(k1, 0); + assert_eq!(v1, 6); + let (k2, v2) = a.last_entry().unwrap().remove_entry(); + assert_eq!(k2, 2); + assert_eq!(v2, 24); + assert_eq!(a.first_entry().unwrap().key(), &1); + assert_eq!(a.last_entry().unwrap().key(), &1); +} + + macro_rules! create_append_test { ($name:ident, $len:expr) => { #[test] diff --git a/src/liballoc/tests/btree/mod.rs b/src/liballoc/tests/btree/mod.rs index 4c704d0f8c2..1d08ae13e05 100644 --- a/src/liballoc/tests/btree/mod.rs +++ b/src/liballoc/tests/btree/mod.rs @@ -11,12 +11,7 @@ struct DeterministicRng { impl DeterministicRng { fn new() -> Self { - DeterministicRng { - x: 0x193a6754, - y: 0xa8a7d469, - z: 0x97830e05, - w: 0x113ba7bb, - } + DeterministicRng { x: 0x193a6754, y: 0xa8a7d469, z: 0x97830e05, w: 0x113ba7bb } } fn next(&mut self) -> u32 { diff --git a/src/liballoc/tests/btree/set.rs b/src/liballoc/tests/btree/set.rs index e4883abc8b5..13cd2628022 100644 --- a/src/liballoc/tests/btree/set.rs +++ b/src/liballoc/tests/btree/set.rs @@ -470,6 +470,34 @@ fn test_append() { assert_eq!(a.contains(&5), true); } +#[test] +fn test_first_last() { + let mut a = BTreeSet::new(); + assert_eq!(a.first(), None); + assert_eq!(a.last(), None); + a.insert(1); + assert_eq!(a.first(), Some(&1)); + assert_eq!(a.last(), Some(&1)); + a.insert(2); + assert_eq!(a.first(), Some(&1)); + assert_eq!(a.last(), Some(&2)); + a.insert(3); + assert_eq!(a.first(), Some(&1)); + assert_eq!(a.last(), Some(&3)); + + assert_eq!(a.len(), 3); + assert_eq!(a.pop_first(), Some(1)); + assert_eq!(a.len(), 2); + assert_eq!(a.pop_last(), Some(3)); + assert_eq!(a.len(), 1); + assert_eq!(a.pop_first(), Some(2)); + assert_eq!(a.len(), 0); + assert_eq!(a.pop_last(), None); + assert_eq!(a.len(), 0); + assert_eq!(a.pop_first(), None); + assert_eq!(a.len(), 0); +} + fn rand_data(len: usize) -> Vec<u32> { let mut rng = DeterministicRng::new(); Vec::from_iter((0..len).map(|_| rng.next())) diff --git a/src/liballoc/tests/lib.rs b/src/liballoc/tests/lib.rs index 3273feb7b5d..605e0ef55d7 100644 --- a/src/liballoc/tests/lib.rs +++ b/src/liballoc/tests/lib.rs @@ -2,6 +2,7 @@ #![feature(box_syntax)] #![feature(drain_filter)] #![feature(exact_size_is_empty)] +#![feature(map_first_last)] #![feature(new_uninit)] #![feature(pattern)] #![feature(trusted_len)] diff --git a/src/liballoc/tests/linked_list.rs b/src/liballoc/tests/linked_list.rs index 8a26454c389..daa49c48c6a 100644 --- a/src/liballoc/tests/linked_list.rs +++ b/src/liballoc/tests/linked_list.rs @@ -102,7 +102,6 @@ fn test_split_off() { assert_eq!(m.back(), Some(&1)); assert_eq!(m.front(), Some(&1)); } - } #[test] @@ -305,8 +304,7 @@ fn test_show() { assert_eq!(format!("{:?}", list), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"); let list: LinkedList<_> = vec!["just", "one", "test", "more"].iter().cloned().collect(); - assert_eq!(format!("{:?}", list), - "[\"just\", \"one\", \"test\", \"more\"]"); + assert_eq!(format!("{:?}", list), "[\"just\", \"one\", \"test\", \"more\"]"); } #[test] @@ -446,19 +444,14 @@ fn drain_filter_true() { #[test] fn drain_filter_complex() { - - { // [+xxx++++++xxxxx++++x+x++] + { + // [+xxx++++++xxxxx++++x+x++] let mut list = vec![ - 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::<LinkedList<_>>(); + 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::<LinkedList<_>>(); let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>(); assert_eq!(removed.len(), 10); @@ -471,17 +464,13 @@ fn drain_filter_complex() { ); } - { // [xxx++++++xxxxx++++x+x++] + { + // [xxx++++++xxxxx++++x+x++] let mut list = vec![ - 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::<LinkedList<_>>(); + 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::<LinkedList<_>>(); let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>(); assert_eq!(removed.len(), 10); @@ -494,16 +483,12 @@ fn drain_filter_complex() { ); } - { // [xxx++++++xxxxx++++x+x] - let mut list = vec![ - 2, 4, 6, - 7, 9, 11, 13, 15, 17, - 18, 20, 22, 24, 26, - 27, 29, 31, 33, - 34, - 35, - 36 - ].into_iter().collect::<LinkedList<_>>(); + { + // [xxx++++++xxxxx++++x+x] + let mut list = + vec![2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36] + .into_iter() + .collect::<LinkedList<_>>(); let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>(); assert_eq!(removed.len(), 10); @@ -516,11 +501,11 @@ fn drain_filter_complex() { ); } - { // [xxxxxxxxxx+++++++++++] - let mut list = vec![ - 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, - 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 - ].into_iter().collect::<LinkedList<_>>(); + { + // [xxxxxxxxxx+++++++++++] + let mut list = vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19] + .into_iter() + .collect::<LinkedList<_>>(); let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>(); assert_eq!(removed.len(), 10); @@ -530,11 +515,11 @@ fn drain_filter_complex() { assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]); } - { // [+++++++++++xxxxxxxxxx] - let mut list = vec![ - 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, - 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 - ].into_iter().collect::<LinkedList<_>>(); + { + // [+++++++++++xxxxxxxxxx] + let mut list = vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20] + .into_iter() + .collect::<LinkedList<_>>(); let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>(); assert_eq!(removed.len(), 10); diff --git a/src/liballoc/tests/rc.rs b/src/liballoc/tests/rc.rs index 7854ca0fc16..e77c57d9a5a 100644 --- a/src/liballoc/tests/rc.rs +++ b/src/liballoc/tests/rc.rs @@ -1,9 +1,9 @@ use std::any::Any; -use std::rc::{Rc, Weak}; use std::cell::RefCell; use std::cmp::PartialEq; -use std::mem; use std::iter::TrustedLen; +use std::mem; +use std::rc::{Rc, Weak}; #[test] fn uninhabited() { @@ -12,7 +12,7 @@ fn uninhabited() { a = a.clone(); assert!(a.upgrade().is_none()); - let mut a: Weak<dyn Any> = a; // Unsizing + let mut a: Weak<dyn Any> = a; // Unsizing a = a.clone(); assert!(a.upgrade().is_none()); } @@ -20,8 +20,8 @@ fn uninhabited() { #[test] fn slice() { let a: Rc<[u32; 3]> = Rc::new([3, 2, 1]); - let a: Rc<[u32]> = a; // Unsizing - let b: Rc<[u32]> = Rc::from(&[3, 2, 1][..]); // Conversion + let a: Rc<[u32]> = a; // Unsizing + let b: Rc<[u32]> = Rc::from(&[3, 2, 1][..]); // Conversion assert_eq!(a, b); // Exercise is_dangling() with a DST @@ -33,7 +33,7 @@ fn slice() { #[test] fn trait_object() { let a: Rc<u32> = Rc::new(4); - let a: Rc<dyn Any> = a; // Unsizing + let a: Rc<dyn Any> = a; // Unsizing // Exercise is_dangling() with a DST let mut a = Rc::downgrade(&a); @@ -43,7 +43,7 @@ fn trait_object() { let mut b = Weak::<u32>::new(); b = b.clone(); assert!(b.upgrade().is_none()); - let mut b: Weak<dyn Any> = b; // Unsizing + let mut b: Weak<dyn Any> = b; // Unsizing b = b.clone(); assert!(b.upgrade().is_none()); } @@ -57,7 +57,7 @@ fn float_nan_ne() { #[test] fn partial_eq() { - struct TestPEq (RefCell<usize>); + struct TestPEq(RefCell<usize>); impl PartialEq for TestPEq { fn eq(&self, other: &TestPEq) -> bool { *self.0.borrow_mut() += 1; @@ -74,7 +74,7 @@ fn partial_eq() { #[test] fn eq() { #[derive(Eq)] - struct TestEq (RefCell<usize>); + struct TestEq(RefCell<usize>); impl PartialEq for TestEq { fn eq(&self, other: &TestEq) -> bool { *self.0.borrow_mut() += 1; @@ -156,13 +156,10 @@ fn shared_from_iter_trustedlen_normal() { fn shared_from_iter_trustedlen_panic() { // Exercise the `TrustedLen` implementation when `size_hint()` matches // `(_, Some(exact_len))` but where `.next()` drops before the last iteration. - let iter = (0..SHARED_ITER_MAX) - .map(|val| { - match val { - 98 => panic!("I've almost got 99 problems."), - _ => Box::new(val), - } - }); + let iter = (0..SHARED_ITER_MAX).map(|val| match val { + 98 => panic!("I've almost got 99 problems."), + _ => Box::new(val), + }); assert_trusted_len(&iter); let _ = iter.collect::<Rc<[_]>>(); @@ -189,16 +186,8 @@ fn shared_from_iter_trustedlen_no_fuse() { } } - let vec = vec![ - Some(Box::new(42)), - Some(Box::new(24)), - None, - Some(Box::new(12)), - ]; + let vec = vec![Some(Box::new(42)), Some(Box::new(24)), None, Some(Box::new(12))]; let iter = Iter(vec.into_iter()); assert_trusted_len(&iter); - assert_eq!( - &[Box::new(42), Box::new(24)], - &*iter.collect::<Rc<[_]>>() - ); + assert_eq!(&[Box::new(42), Box::new(24)], &*iter.collect::<Rc<[_]>>()); } diff --git a/src/liballoc/tests/slice.rs b/src/liballoc/tests/slice.rs index ad2cd7c95eb..d9707b95740 100644 --- a/src/liballoc/tests/slice.rs +++ b/src/liballoc/tests/slice.rs @@ -4,7 +4,6 @@ use std::mem; use std::panic; use std::rc::Rc; use std::sync::atomic::{Ordering::Relaxed, AtomicUsize}; -use std::thread; use rand::{Rng, RngCore, thread_rng}; use rand::seq::SliceRandom; @@ -1406,11 +1405,9 @@ fn test_box_slice_clone() { #[test] #[allow(unused_must_use)] // here, we care about the side effects of `.clone()` #[cfg_attr(target_os = "emscripten", ignore)] -#[cfg(not(miri))] // Miri does not support threads fn test_box_slice_clone_panics() { use std::sync::Arc; use std::sync::atomic::{AtomicUsize, Ordering}; - use std::thread::spawn; struct Canary { count: Arc<AtomicUsize>, @@ -1446,7 +1443,7 @@ fn test_box_slice_clone_panics() { panics: true, }; - spawn(move || { + std::panic::catch_unwind(move || { // When xs is dropped, +5. let xs = vec![canary.clone(), canary.clone(), canary.clone(), panic, canary] .into_boxed_slice(); @@ -1454,7 +1451,6 @@ fn test_box_slice_clone_panics() { // When panic is cloned, +3. xs.clone(); }) - .join() .unwrap_err(); // Total = 8 @@ -1566,7 +1562,7 @@ macro_rules! test { } let v = $input.to_owned(); - let _ = thread::spawn(move || { + let _ = std::panic::catch_unwind(move || { let mut v = v; let mut panic_countdown = panic_countdown; v.$func(|a, b| { @@ -1577,7 +1573,7 @@ macro_rules! test { panic_countdown -= 1; a.cmp(b) }) - }).join(); + }); // Check that the number of things dropped is exactly // what we expect (i.e., the contents of `v`). @@ -1598,7 +1594,6 @@ thread_local!(static SILENCE_PANIC: Cell<bool> = Cell::new(false)); #[test] #[cfg_attr(target_os = "emscripten", ignore)] // no threads -#[cfg(not(miri))] // Miri does not support threads fn panic_safe() { let prev = panic::take_hook(); panic::set_hook(Box::new(move |info| { @@ -1609,8 +1604,18 @@ fn panic_safe() { let mut rng = thread_rng(); - for len in (1..20).chain(70..MAX_LEN) { - for &modulus in &[5, 20, 50] { + #[cfg(not(miri))] // Miri is too slow + let lens = (1..20).chain(70..MAX_LEN); + #[cfg(not(miri))] // Miri is too slow + let moduli = &[5, 20, 50]; + + #[cfg(miri)] + let lens = (1..13); + #[cfg(miri)] + let moduli = &[10]; + + for len in lens { + for &modulus in moduli { for &has_runs in &[false, true] { let mut input = (0..len) .map(|id| { @@ -1643,6 +1648,9 @@ fn panic_safe() { } } } + + // Set default panic hook again. + drop(panic::take_hook()); } #[test] diff --git a/src/liballoc/tests/vec.rs b/src/liballoc/tests/vec.rs index 80537217697..9ee254f99ac 100644 --- a/src/liballoc/tests/vec.rs +++ b/src/liballoc/tests/vec.rs @@ -944,10 +944,9 @@ fn drain_filter_complex() { } } -// Miri does not support catching panics // FIXME: re-enable emscripten once it can unwind again #[test] -#[cfg(not(any(miri, target_os = "emscripten")))] +#[cfg(not(target_os = "emscripten"))] fn drain_filter_consumed_panic() { use std::rc::Rc; use std::sync::Mutex; @@ -985,7 +984,7 @@ fn drain_filter_consumed_panic() { }; let drain = data.drain_filter(filter); - // NOTE: The DrainFilter is explictly consumed + // NOTE: The DrainFilter is explicitly consumed drain.for_each(drop); }); @@ -999,7 +998,7 @@ fn drain_filter_consumed_panic() { // FIXME: Re-enable emscripten once it can catch panics #[test] -#[cfg(not(any(miri, target_os = "emscripten")))] // Miri does not support catching panics +#[cfg(not(target_os = "emscripten"))] fn drain_filter_unconsumed_panic() { use std::rc::Rc; use std::sync::Mutex; diff --git a/src/liballoc/tests/vec_deque.rs b/src/liballoc/tests/vec_deque.rs index d49b553fc02..5a0162a5361 100644 --- a/src/liballoc/tests/vec_deque.rs +++ b/src/liballoc/tests/vec_deque.rs @@ -1,8 +1,8 @@ -use std::fmt::Debug; -use std::collections::{VecDeque, vec_deque::Drain}; use std::collections::TryReserveError::*; +use std::collections::{vec_deque::Drain, VecDeque}; +use std::fmt::Debug; use std::mem::size_of; -use std::{usize, isize}; +use std::{isize, usize}; use crate::hash; @@ -148,34 +148,20 @@ fn test_param_taggy() { #[test] fn test_param_taggypar() { - test_parameterized::<Taggypar<i32>>(Onepar::<i32>(1), - Twopar::<i32>(1, 2), - Threepar::<i32>(1, 2, 3), - Twopar::<i32>(17, 42)); + test_parameterized::<Taggypar<i32>>( + Onepar::<i32>(1), + Twopar::<i32>(1, 2), + Threepar::<i32>(1, 2, 3), + Twopar::<i32>(17, 42), + ); } #[test] fn test_param_reccy() { - let reccy1 = RecCy { - x: 1, - y: 2, - t: One(1), - }; - let reccy2 = RecCy { - x: 345, - y: 2, - t: Two(1, 2), - }; - let reccy3 = RecCy { - x: 1, - y: 777, - t: Three(1, 2, 3), - }; - let reccy4 = RecCy { - x: 19, - y: 252, - t: Two(17, 42), - }; + let reccy1 = RecCy { x: 1, y: 2, t: One(1) }; + let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) }; + let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) }; + let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) }; test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4); } @@ -320,8 +306,7 @@ fn test_mut_rev_iter_wrap() { assert_eq!(d.pop_front(), Some(1)); d.push_back(4); - assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<_>>(), - vec![4, 3, 2]); + assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<_>>(), vec![4, 3, 2]); } #[test] @@ -372,7 +357,6 @@ fn test_mut_rev_iter() { #[test] fn test_into_iter() { - // Empty iter { let d: VecDeque<i32> = VecDeque::new(); @@ -431,7 +415,6 @@ fn test_into_iter() { #[test] fn test_drain() { - // Empty iter { let mut d: VecDeque<i32> = VecDeque::new(); @@ -650,12 +633,8 @@ fn test_show() { let ringbuf: VecDeque<_> = (0..10).collect(); assert_eq!(format!("{:?}", ringbuf), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"); - let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"] - .iter() - .cloned() - .collect(); - assert_eq!(format!("{:?}", ringbuf), - "[\"just\", \"one\", \"test\", \"more\"]"); + let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"].iter().cloned().collect(); + assert_eq!(format!("{:?}", ringbuf), "[\"just\", \"one\", \"test\", \"more\"]"); } #[test] @@ -955,7 +934,6 @@ fn test_append_permutations() { // doesn't pop more values than are pushed for src_pop_back in 0..(src_push_back + src_push_front) { for src_pop_front in 0..(src_push_back + src_push_front - src_pop_back) { - let src = construct_vec_deque( src_push_back, src_pop_back, @@ -966,8 +944,8 @@ fn test_append_permutations() { for dst_push_back in 0..MAX { for dst_push_front in 0..MAX { for dst_pop_back in 0..(dst_push_back + dst_push_front) { - for dst_pop_front - in 0..(dst_push_back + dst_push_front - dst_pop_back) + for dst_pop_front in + 0..(dst_push_back + dst_push_front - dst_pop_back) { let mut dst = construct_vec_deque( dst_push_back, @@ -1124,7 +1102,6 @@ fn test_reserve_exact_2() { #[test] #[cfg(not(miri))] // Miri does not support signalling OOM fn test_try_reserve() { - // These are the interesting cases: // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM) // * > isize::MAX should always fail @@ -1158,22 +1135,27 @@ fn test_try_reserve() { if guards_against_isize { // Check isize::MAX + 1 does count as overflow if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP + 1) { - } else { panic!("isize::MAX + 1 should trigger an overflow!") } + } else { + panic!("isize::MAX + 1 should trigger an overflow!") + } // Check usize::MAX does count as overflow if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) { - } else { panic!("usize::MAX should trigger an overflow!") } + } else { + panic!("usize::MAX should trigger an overflow!") + } } else { // Check isize::MAX is an OOM // VecDeque starts with capacity 7, always adds 1 to the capacity // and also rounds the number to next power of 2 so this is the // furthest we can go without triggering CapacityOverflow if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_CAP) { - } else { panic!("isize::MAX + 1 should trigger an OOM!") } + } else { + panic!("isize::MAX + 1 should trigger an OOM!") + } } } - { // Same basic idea, but with non-zero len let mut ten_bytes: VecDeque<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); @@ -1186,33 +1168,42 @@ fn test_try_reserve() { } if guards_against_isize { if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 9) { - } else { panic!("isize::MAX + 1 should trigger an overflow!"); } + } else { + panic!("isize::MAX + 1 should trigger an overflow!"); + } } else { if let Err(AllocError { .. }) = ten_bytes.try_reserve(MAX_CAP - 9) { - } else { panic!("isize::MAX + 1 should trigger an OOM!") } + } else { + panic!("isize::MAX + 1 should trigger an OOM!") + } } // Should always overflow in the add-to-len if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_USIZE) { - } else { panic!("usize::MAX should trigger an overflow!") } + } else { + panic!("usize::MAX should trigger an overflow!") + } } - { // Same basic idea, but with interesting type size let mut ten_u32s: VecDeque<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); - if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 10) { + if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10) { panic!("isize::MAX shouldn't trigger an overflow!"); } - if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 10) { + if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10) { panic!("isize::MAX shouldn't trigger an overflow!"); } if guards_against_isize { - if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 9) { - } else { panic!("isize::MAX + 1 should trigger an overflow!"); } + if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 9) { + } else { + panic!("isize::MAX + 1 should trigger an overflow!"); + } } else { - if let Err(AllocError { .. }) = ten_u32s.try_reserve(MAX_CAP/4 - 9) { - } else { panic!("isize::MAX + 1 should trigger an OOM!") } + if let Err(AllocError { .. }) = ten_u32s.try_reserve(MAX_CAP / 4 - 9) { + } else { + panic!("isize::MAX + 1 should trigger an OOM!") + } } // Should fail in the mul-by-size if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_USIZE - 20) { @@ -1220,13 +1211,11 @@ fn test_try_reserve() { panic!("usize::MAX should trigger an overflow!"); } } - } #[test] #[cfg(not(miri))] // Miri does not support signalling OOM fn test_try_reserve_exact() { - // This is exactly the same as test_try_reserve with the method changed. // See that test for comments. @@ -1247,21 +1236,26 @@ fn test_try_reserve_exact() { if guards_against_isize { if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP + 1) { - } else { panic!("isize::MAX + 1 should trigger an overflow!") } + } else { + panic!("isize::MAX + 1 should trigger an overflow!") + } if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_USIZE) { - } else { panic!("usize::MAX should trigger an overflow!") } + } else { + panic!("usize::MAX should trigger an overflow!") + } } else { // Check isize::MAX is an OOM // VecDeque starts with capacity 7, always adds 1 to the capacity // and also rounds the number to next power of 2 so this is the // furthest we can go without triggering CapacityOverflow if let Err(AllocError { .. }) = empty_bytes.try_reserve_exact(MAX_CAP) { - } else { panic!("isize::MAX + 1 should trigger an OOM!") } + } else { + panic!("isize::MAX + 1 should trigger an OOM!") + } } } - { let mut ten_bytes: VecDeque<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); @@ -1273,36 +1267,46 @@ fn test_try_reserve_exact() { } if guards_against_isize { if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 9) { - } else { panic!("isize::MAX + 1 should trigger an overflow!"); } + } else { + panic!("isize::MAX + 1 should trigger an overflow!"); + } } else { if let Err(AllocError { .. }) = ten_bytes.try_reserve_exact(MAX_CAP - 9) { - } else { panic!("isize::MAX + 1 should trigger an OOM!") } + } else { + panic!("isize::MAX + 1 should trigger an OOM!") + } } if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_USIZE) { - } else { panic!("usize::MAX should trigger an overflow!") } + } else { + panic!("usize::MAX should trigger an overflow!") + } } - { let mut ten_u32s: VecDeque<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); - if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 10) { + if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10) { panic!("isize::MAX shouldn't trigger an overflow!"); } - if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 10) { + if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10) { panic!("isize::MAX shouldn't trigger an overflow!"); } if guards_against_isize { - if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 9) { - } else { panic!("isize::MAX + 1 should trigger an overflow!"); } + if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9) { + } else { + panic!("isize::MAX + 1 should trigger an overflow!"); + } } else { - if let Err(AllocError { .. }) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 9) { - } else { panic!("isize::MAX + 1 should trigger an OOM!") } + if let Err(AllocError { .. }) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9) { + } else { + panic!("isize::MAX + 1 should trigger an OOM!") + } } if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_USIZE - 20) { - } else { panic!("usize::MAX should trigger an overflow!") } + } else { + panic!("usize::MAX should trigger an overflow!") + } } - } #[test] @@ -1404,9 +1408,8 @@ fn test_rotate_right_parts() { #[test] fn test_rotate_left_random() { let shifts = [ - 6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1, - 4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11, - 9, 4, 12, 3, 12, 9, 11, 1, 7, 9, 7, 2, + 6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1, 4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11, 9, 4, 12, 3, + 12, 9, 11, 1, 7, 9, 7, 2, ]; let n = 12; let mut v: VecDeque<_> = (0..n).collect(); @@ -1423,9 +1426,8 @@ fn test_rotate_left_random() { #[test] fn test_rotate_right_random() { let shifts = [ - 6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1, - 4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11, - 9, 4, 12, 3, 12, 9, 11, 1, 7, 9, 7, 2, + 6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1, 4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11, 9, 4, 12, 3, + 12, 9, 11, 1, 7, 9, 7, 2, ]; let n = 12; let mut v: VecDeque<_> = (0..n).collect(); @@ -1447,8 +1449,7 @@ fn test_try_fold_empty() { #[test] fn test_try_fold_none() { let v: VecDeque<u32> = (0..12).collect(); - assert_eq!(None, v.into_iter().try_fold(0, |a, b| - if b < 11 { Some(a + b) } else { None })); + assert_eq!(None, v.into_iter().try_fold(0, |a, b| if b < 11 { Some(a + b) } else { None })); } #[test] @@ -1463,7 +1464,6 @@ fn test_try_fold_unit() { assert_eq!(Some(()), v.into_iter().try_fold((), |(), ()| Some(()))); } - #[test] fn test_try_fold_unit_none() { let v: std::collections::VecDeque<()> = [(); 10].iter().cloned().collect(); @@ -1534,7 +1534,7 @@ fn test_try_rfold_rotated() { #[test] fn test_try_rfold_moves_iter() { - let v : VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect(); + let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect(); let mut iter = v.into_iter(); assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None); assert_eq!(iter.next_back(), Some(&70)); diff --git a/src/liballoc/vec.rs b/src/liballoc/vec.rs index 5b53a6a2899..1a700b99056 100644 --- a/src/liballoc/vec.rs +++ b/src/liballoc/vec.rs @@ -629,6 +629,8 @@ impl<T> Vec<T> { /// The capacity will remain at least as large as both the length /// and the supplied value. /// + /// # Panics + /// /// Panics if the current capacity is smaller than the supplied /// minimum capacity. /// @@ -727,25 +729,20 @@ impl<T> Vec<T> { /// [`drain`]: #method.drain #[stable(feature = "rust1", since = "1.0.0")] pub fn truncate(&mut self, len: usize) { - if mem::needs_drop::<T>() { - let current_len = self.len; - unsafe { - let mut ptr = self.as_mut_ptr().add(self.len); - // Set the final length at the end, keeping in mind that - // dropping an element might panic. Works around a missed - // optimization, as seen in the following issue: - // https://github.com/rust-lang/rust/issues/51802 - let mut local_len = SetLenOnDrop::new(&mut self.len); - - // drop any extra elements - for _ in len..current_len { - local_len.decrement_len(1); - ptr = ptr.offset(-1); - ptr::drop_in_place(ptr); - } + // This is safe because: + // + // * the slice passed to `drop_in_place` is valid; the `len > self.len` + // case avoids creating an invalid slice, and + // * the `len` of the vector is shrunk before calling `drop_in_place`, + // such that no value will be dropped twice in case `drop_in_place` + // were to panic once (if it panics twice, the program aborts). + unsafe { + if len > self.len { + return; } - } else if len <= self.len { + let s = self.get_unchecked_mut(len..) as *mut _; self.len = len; + ptr::drop_in_place(s); } } @@ -861,7 +858,7 @@ impl<T> Vec<T> { /// /// [`truncate`]: #method.truncate /// [`resize`]: #method.resize - /// [`extend`]: #method.extend-1 + /// [`extend`]: ../../std/iter/trait.Extend.html#tymethod.extend /// [`clear`]: #method.clear /// /// # Safety @@ -1338,10 +1335,9 @@ impl<T> Vec<T> { /// Splits the collection into two at the given index. /// - /// Returns a newly allocated `Self`. `self` contains elements `[0, at)`, - /// and the returned `Self` contains elements `[at, len)`. - /// - /// Note that the capacity of `self` does not change. + /// Returns a newly allocated vector containing the elements in the range + /// `[at, len)`. After the call, the original vector will be left containing + /// the elements `[0, at)` with its previous capacity unchanged. /// /// # Panics /// @@ -1630,11 +1626,6 @@ impl<'a> SetLenOnDrop<'a> { fn increment_len(&mut self, increment: usize) { self.local_len += increment; } - - #[inline] - fn decrement_len(&mut self, decrement: usize) { - self.local_len -= decrement; - } } impl Drop for SetLenOnDrop<'_> { @@ -2712,6 +2703,9 @@ impl<T> ExactSizeIterator for Drain<'_, T> { } } +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl<T> TrustedLen for Drain<'_, T> {} + #[stable(feature = "fused", since = "1.26.0")] impl<T> FusedIterator for Drain<'_, T> {} @@ -2848,7 +2842,7 @@ pub struct DrainFilter<'a, T, F> old_len: usize, /// The filter test predicate. pred: F, - /// A flag that indicates a panic has occured in the filter test prodicate. + /// A flag that indicates a panic has occurred in the filter test prodicate. /// This is used as a hint in the drop implmentation to prevent consumption /// of the remainder of the `DrainFilter`. Any unprocessed items will be /// backshifted in the `vec`, but no further items will be dropped or |