From 76e216f29b44322b52c49d8c56f20763beb271b5 Mon Sep 17 00:00:00 2001 From: Lukas Markeffsky <@> Date: Sat, 14 Jan 2023 11:48:43 +0100 Subject: Use associated items of `char` instead of freestanding items in `core::char` --- library/core/src/char/decode.rs | 6 ++---- library/core/src/char/methods.rs | 24 ++++-------------------- library/core/src/char/mod.rs | 2 +- library/core/src/iter/range.rs | 1 - library/core/src/str/iter.rs | 10 +++++----- 5 files changed, 12 insertions(+), 31 deletions(-) (limited to 'library/core/src') diff --git a/library/core/src/char/decode.rs b/library/core/src/char/decode.rs index eeb08803040..dbfe251f2bb 100644 --- a/library/core/src/char/decode.rs +++ b/library/core/src/char/decode.rs @@ -3,8 +3,6 @@ use crate::error::Error; use crate::fmt; -use super::from_u32_unchecked; - /// An iterator that decodes UTF-16 encoded code points from an iterator of `u16`s. /// /// This `struct` is created by the [`decode_utf16`] method on [`char`]. See its @@ -49,7 +47,7 @@ impl> Iterator for DecodeUtf16 { if !u.is_utf16_surrogate() { // SAFETY: not a surrogate - Some(Ok(unsafe { from_u32_unchecked(u as u32) })) + Some(Ok(unsafe { char::from_u32_unchecked(u as u32) })) } else if u >= 0xDC00 { // a trailing surrogate Some(Err(DecodeUtf16Error { code: u })) @@ -69,7 +67,7 @@ impl> Iterator for DecodeUtf16 { // all ok, so lets decode it. let c = (((u & 0x3ff) as u32) << 10 | (u2 & 0x3ff) as u32) + 0x1_0000; // SAFETY: we checked that it's a legal unicode value - Some(Ok(unsafe { from_u32_unchecked(c) })) + Some(Ok(unsafe { char::from_u32_unchecked(c) })) } } diff --git a/library/core/src/char/methods.rs b/library/core/src/char/methods.rs index 3e7383b4cd1..9bc97ea0bff 100644 --- a/library/core/src/char/methods.rs +++ b/library/core/src/char/methods.rs @@ -53,15 +53,13 @@ impl char { /// Basic usage: /// /// ``` - /// use std::char::decode_utf16; - /// /// // 𝄞music /// let v = [ /// 0xD834, 0xDD1E, 0x006d, 0x0075, 0x0073, 0xDD1E, 0x0069, 0x0063, 0xD834, /// ]; /// /// assert_eq!( - /// decode_utf16(v) + /// char::decode_utf16(v) /// .map(|r| r.map_err(|e| e.unpaired_surrogate())) /// .collect::>(), /// vec![ @@ -77,16 +75,14 @@ impl char { /// A lossy decoder can be obtained by replacing `Err` results with the replacement character: /// /// ``` - /// use std::char::{decode_utf16, REPLACEMENT_CHARACTER}; - /// /// // 𝄞music /// let v = [ /// 0xD834, 0xDD1E, 0x006d, 0x0075, 0x0073, 0xDD1E, 0x0069, 0x0063, 0xD834, /// ]; /// /// assert_eq!( - /// decode_utf16(v) - /// .map(|r| r.unwrap_or(REPLACEMENT_CHARACTER)) + /// char::decode_utf16(v) + /// .map(|r| r.unwrap_or(char::REPLACEMENT_CHARACTER)) /// .collect::(), /// "𝄞mus�ic�" /// ); @@ -123,8 +119,6 @@ impl char { /// Basic usage: /// /// ``` - /// use std::char; - /// /// let c = char::from_u32(0x2764); /// /// assert_eq!(Some('❤'), c); @@ -133,8 +127,6 @@ impl char { /// Returning `None` when the input is not a valid `char`: /// /// ``` - /// use std::char; - /// /// let c = char::from_u32(0x110000); /// /// assert_eq!(None, c); @@ -176,8 +168,6 @@ impl char { /// Basic usage: /// /// ``` - /// use std::char; - /// /// let c = unsafe { char::from_u32_unchecked(0x2764) }; /// /// assert_eq!('❤', c); @@ -210,8 +200,6 @@ impl char { /// Basic usage: /// /// ``` - /// use std::char; - /// /// let c = char::from_digit(4, 10); /// /// assert_eq!(Some('4'), c); @@ -225,8 +213,6 @@ impl char { /// Returning `None` when the input is not a digit: /// /// ``` - /// use std::char; - /// /// let c = char::from_digit(20, 10); /// /// assert_eq!(None, c); @@ -235,8 +221,6 @@ impl char { /// Passing a large radix, causing a panic: /// /// ```should_panic - /// use std::char; - /// /// // this panics /// let _c = char::from_digit(1, 37); /// ``` @@ -1786,7 +1770,7 @@ pub fn encode_utf16_raw(mut code: u32, dst: &mut [u16]) -> &mut [u16] { } else { panic!( "encode_utf16: need {} units to encode U+{:X}, but the buffer has {}", - from_u32_unchecked(code).len_utf16(), + char::from_u32_unchecked(code).len_utf16(), code, dst.len(), ) diff --git a/library/core/src/char/mod.rs b/library/core/src/char/mod.rs index af98059cf42..8ec78e88733 100644 --- a/library/core/src/char/mod.rs +++ b/library/core/src/char/mod.rs @@ -189,7 +189,7 @@ impl Iterator for EscapeUnicode { } EscapeUnicodeState::Value => { let hex_digit = ((self.c as u32) >> (self.hex_digit_idx * 4)) & 0xf; - let c = from_digit(hex_digit, 16).unwrap(); + let c = char::from_digit(hex_digit, 16).unwrap(); if self.hex_digit_idx == 0 { self.state = EscapeUnicodeState::RightBrace; } else { diff --git a/library/core/src/iter/range.rs b/library/core/src/iter/range.rs index ac7b389b15b..1ad33cc9733 100644 --- a/library/core/src/iter/range.rs +++ b/library/core/src/iter/range.rs @@ -1,4 +1,3 @@ -use crate::char; use crate::convert::TryFrom; use crate::mem; use crate::ops::{self, Try}; diff --git a/library/core/src/str/iter.rs b/library/core/src/str/iter.rs index d969475aa48..95c682f42d0 100644 --- a/library/core/src/str/iter.rs +++ b/library/core/src/str/iter.rs @@ -1,6 +1,6 @@ //! Iterators for `str` methods. -use crate::char; +use crate::char as char_mod; use crate::fmt::{self, Write}; use crate::iter::{Chain, FlatMap, Flatten}; use crate::iter::{Copied, Filter, FusedIterator, Map, TrustedLen}; @@ -1455,8 +1455,8 @@ impl FusedIterator for EncodeUtf16<'_> {} #[derive(Clone, Debug)] pub struct EscapeDebug<'a> { pub(super) inner: Chain< - Flatten>, - FlatMap, char::EscapeDebug, CharEscapeDebugContinue>, + Flatten>, + FlatMap, char_mod::EscapeDebug, CharEscapeDebugContinue>, >, } @@ -1464,14 +1464,14 @@ pub struct EscapeDebug<'a> { #[stable(feature = "str_escape", since = "1.34.0")] #[derive(Clone, Debug)] pub struct EscapeDefault<'a> { - pub(super) inner: FlatMap, char::EscapeDefault, CharEscapeDefault>, + pub(super) inner: FlatMap, char_mod::EscapeDefault, CharEscapeDefault>, } /// The return type of [`str::escape_unicode`]. #[stable(feature = "str_escape", since = "1.34.0")] #[derive(Clone, Debug)] pub struct EscapeUnicode<'a> { - pub(super) inner: FlatMap, char::EscapeUnicode, CharEscapeUnicode>, + pub(super) inner: FlatMap, char_mod::EscapeUnicode, CharEscapeUnicode>, } macro_rules! escape_types_impls { -- cgit 1.4.1-3-g733a5 From 703ff60d9f885dfe317e3d271d9f341509efac92 Mon Sep 17 00:00:00 2001 From: Lukas Bergdoll Date: Sat, 21 Jan 2023 10:17:06 +0100 Subject: Use NonNull in merge_sort This is more clear about the intent of the pointer and avoids problems if the allocation returns a null pointer. --- library/core/src/slice/sort.rs | 34 +++++++++++++++++++--------------- 1 file changed, 19 insertions(+), 15 deletions(-) (limited to 'library/core/src') diff --git a/library/core/src/slice/sort.rs b/library/core/src/slice/sort.rs index 2181f9a8118..7f8895b150f 100644 --- a/library/core/src/slice/sort.rs +++ b/library/core/src/slice/sort.rs @@ -1203,7 +1203,7 @@ pub fn merge_sort( // `is_less` panics. When merging two sorted runs, this buffer holds a copy of the shorter run, // which will always have length at most `len / 2`. let buf = BufGuard::new(len / 2, elem_alloc_fn, elem_dealloc_fn); - let buf_ptr = buf.buf_ptr; + let buf_ptr = buf.buf_ptr.as_ptr(); let mut runs = RunVec::new(run_alloc_fn, run_dealloc_fn); @@ -1298,7 +1298,7 @@ pub fn merge_sort( where ElemDeallocF: Fn(*mut T, usize), { - buf_ptr: *mut T, + buf_ptr: ptr::NonNull, capacity: usize, elem_dealloc_fn: ElemDeallocF, } @@ -1315,7 +1315,11 @@ pub fn merge_sort( where ElemAllocF: Fn(usize) -> *mut T, { - Self { buf_ptr: elem_alloc_fn(len), capacity: len, elem_dealloc_fn } + Self { + buf_ptr: ptr::NonNull::new(elem_alloc_fn(len)).unwrap(), + capacity: len, + elem_dealloc_fn, + } } } @@ -1324,7 +1328,7 @@ pub fn merge_sort( ElemDeallocF: Fn(*mut T, usize), { fn drop(&mut self) { - (self.elem_dealloc_fn)(self.buf_ptr, self.capacity); + (self.elem_dealloc_fn)(self.buf_ptr.as_ptr(), self.capacity); } } @@ -1333,7 +1337,7 @@ pub fn merge_sort( RunAllocF: Fn(usize) -> *mut TimSortRun, RunDeallocF: Fn(*mut TimSortRun, usize), { - buf_ptr: *mut TimSortRun, + buf_ptr: ptr::NonNull, capacity: usize, len: usize, run_alloc_fn: RunAllocF, @@ -1350,7 +1354,7 @@ pub fn merge_sort( const START_RUN_CAPACITY: usize = 16; Self { - buf_ptr: run_alloc_fn(START_RUN_CAPACITY), + buf_ptr: ptr::NonNull::new(run_alloc_fn(START_RUN_CAPACITY)).unwrap(), capacity: START_RUN_CAPACITY, len: 0, run_alloc_fn, @@ -1361,15 +1365,15 @@ pub fn merge_sort( fn push(&mut self, val: TimSortRun) { if self.len == self.capacity { let old_capacity = self.capacity; - let old_buf_ptr = self.buf_ptr; + let old_buf_ptr = self.buf_ptr.as_ptr(); self.capacity = self.capacity * 2; - self.buf_ptr = (self.run_alloc_fn)(self.capacity); + self.buf_ptr = ptr::NonNull::new((self.run_alloc_fn)(self.capacity)).unwrap(); // SAFETY: buf_ptr new and old were correctly allocated and old_buf_ptr has // old_capacity valid elements. unsafe { - ptr::copy_nonoverlapping(old_buf_ptr, self.buf_ptr, old_capacity); + ptr::copy_nonoverlapping(old_buf_ptr, self.buf_ptr.as_ptr(), old_capacity); } (self.run_dealloc_fn)(old_buf_ptr, old_capacity); @@ -1377,7 +1381,7 @@ pub fn merge_sort( // SAFETY: The invariant was just checked. unsafe { - self.buf_ptr.add(self.len).write(val); + self.buf_ptr.as_ptr().add(self.len).write(val); } self.len += 1; } @@ -1390,7 +1394,7 @@ pub fn merge_sort( // SAFETY: buf_ptr needs to be valid and len invariant upheld. unsafe { // the place we are taking from. - let ptr = self.buf_ptr.add(index); + let ptr = self.buf_ptr.as_ptr().add(index); // Shift everything down to fill in that spot. ptr::copy(ptr.add(1), ptr, self.len - index - 1); @@ -1400,7 +1404,7 @@ pub fn merge_sort( fn as_slice(&self) -> &[TimSortRun] { // SAFETY: Safe as long as buf_ptr is valid and len invariant was upheld. - unsafe { &*ptr::slice_from_raw_parts(self.buf_ptr, self.len) } + unsafe { &*ptr::slice_from_raw_parts(self.buf_ptr.as_ptr(), self.len) } } fn len(&self) -> usize { @@ -1419,7 +1423,7 @@ pub fn merge_sort( if index < self.len { // SAFETY: buf_ptr and len invariant must be upheld. unsafe { - return &*(self.buf_ptr.add(index)); + return &*(self.buf_ptr.as_ptr().add(index)); } } @@ -1436,7 +1440,7 @@ pub fn merge_sort( if index < self.len { // SAFETY: buf_ptr and len invariant must be upheld. unsafe { - return &mut *(self.buf_ptr.add(index)); + return &mut *(self.buf_ptr.as_ptr().add(index)); } } @@ -1452,7 +1456,7 @@ pub fn merge_sort( fn drop(&mut self) { // As long as TimSortRun is Copy we don't need to drop them individually but just the // whole allocation. - (self.run_dealloc_fn)(self.buf_ptr, self.capacity); + (self.run_dealloc_fn)(self.buf_ptr.as_ptr(), self.capacity); } } } -- cgit 1.4.1-3-g733a5 From a3065a1a34fe1c0b85bdf3ff1f3d0bd470235e6b Mon Sep 17 00:00:00 2001 From: Lukas Bergdoll Date: Sun, 22 Jan 2023 11:55:35 +0100 Subject: Unify insertion sort implementations Avoid duplicate insertion sort implementations. Optimize implementations. --- library/core/src/slice/sort.rs | 359 +++++++++++++++++++++-------------------- 1 file changed, 188 insertions(+), 171 deletions(-) (limited to 'library/core/src') diff --git a/library/core/src/slice/sort.rs b/library/core/src/slice/sort.rs index 7f8895b150f..6bb53b16e61 100644 --- a/library/core/src/slice/sort.rs +++ b/library/core/src/slice/sort.rs @@ -13,115 +13,178 @@ use crate::cmp; use crate::mem::{self, MaybeUninit, SizedTypeProperties}; use crate::ptr; -/// When dropped, copies from `src` into `dest`. -struct CopyOnDrop { +// When dropped, copies from `src` into `dest`. +struct InsertionHole { src: *const T, dest: *mut T, } -impl Drop for CopyOnDrop { +impl Drop for InsertionHole { fn drop(&mut self) { - // SAFETY: This is a helper class. - // Please refer to its usage for correctness. - // Namely, one must be sure that `src` and `dst` does not overlap as required by `ptr::copy_nonoverlapping`. unsafe { ptr::copy_nonoverlapping(self.src, self.dest, 1); } } } -/// Shifts the first element to the right until it encounters a greater or equal element. -fn shift_head(v: &mut [T], is_less: &mut F) +/// Inserts `v[v.len() - 1]` into pre-sorted sequence `v[..v.len() - 1]` so that whole `v[..]` +/// becomes sorted. +unsafe fn insert_tail(v: &mut [T], is_less: &mut F) where F: FnMut(&T, &T) -> bool, { - let len = v.len(); - // SAFETY: The unsafe operations below involves indexing without a bounds check (by offsetting a - // pointer) and copying memory (`ptr::copy_nonoverlapping`). - // - // a. Indexing: - // 1. We checked the size of the array to >=2. - // 2. All the indexing that we will do is always between {0 <= index < len} at most. - // - // b. Memory copying - // 1. We are obtaining pointers to references which are guaranteed to be valid. - // 2. They cannot overlap because we obtain pointers to difference indices of the slice. - // Namely, `i` and `i-1`. - // 3. If the slice is properly aligned, the elements are properly aligned. - // It is the caller's responsibility to make sure the slice is properly aligned. - // - // See comments below for further detail. + debug_assert!(v.len() >= 2); + + let arr_ptr = v.as_mut_ptr(); + let i = v.len() - 1; + + // SAFETY: caller must ensure v is at least len 2. unsafe { - // If the first two elements are out-of-order... - if len >= 2 && is_less(v.get_unchecked(1), v.get_unchecked(0)) { - // Read the first element into a stack-allocated variable. If a following comparison - // operation panics, `hole` will get dropped and automatically write the element back - // into the slice. - let tmp = mem::ManuallyDrop::new(ptr::read(v.get_unchecked(0))); - let v = v.as_mut_ptr(); - let mut hole = CopyOnDrop { src: &*tmp, dest: v.add(1) }; - ptr::copy_nonoverlapping(v.add(1), v.add(0), 1); - - for i in 2..len { - if !is_less(&*v.add(i), &*tmp) { + // See insert_head which talks about why this approach is beneficial. + let i_ptr = arr_ptr.add(i); + + // It's important that we use i_ptr here. If this check is positive and we continue, + // We want to make sure that no other copy of the value was seen by is_less. + // Otherwise we would have to copy it back. + if is_less(&*i_ptr, &*i_ptr.sub(1)) { + // It's important, that we use tmp for comparison from now on. As it is the value that + // will be copied back. And notionally we could have created a divergence if we copy + // back the wrong value. + let tmp = mem::ManuallyDrop::new(ptr::read(i_ptr)); + // Intermediate state of the insertion process is always tracked by `hole`, which + // serves two purposes: + // 1. Protects integrity of `v` from panics in `is_less`. + // 2. Fills the remaining hole in `v` in the end. + // + // Panic safety: + // + // 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: &*tmp, dest: i_ptr.sub(1) }; + ptr::copy_nonoverlapping(hole.dest, i_ptr, 1); + + // SAFETY: We know i is at least 1. + for j in (0..(i - 1)).rev() { + let j_ptr = arr_ptr.add(j); + if !is_less(&*tmp, &*j_ptr) { break; } - // Move `i`-th element one place to the left, thus shifting the hole to the right. - ptr::copy_nonoverlapping(v.add(i), v.add(i - 1), 1); - hole.dest = v.add(i); + ptr::copy_nonoverlapping(j_ptr, hole.dest, 1); + hole.dest = j_ptr; } // `hole` gets dropped and thus copies `tmp` into the remaining hole in `v`. } } } -/// Shifts the last element to the left until it encounters a smaller or equal element. -fn shift_tail(v: &mut [T], is_less: &mut F) +/// Inserts `v[0]` into pre-sorted sequence `v[1..]` so that whole `v[..]` becomes sorted. +/// +/// This is the integral subroutine of insertion sort. +unsafe fn insert_head(v: &mut [T], is_less: &mut F) where F: FnMut(&T, &T) -> bool, { - let len = v.len(); - // SAFETY: The unsafe operations below involves indexing without a bound check (by offsetting a - // pointer) and copying memory (`ptr::copy_nonoverlapping`). - // - // a. Indexing: - // 1. We checked the size of the array to >= 2. - // 2. All the indexing that we will do is always between `0 <= index < len-1` at most. - // - // b. Memory copying - // 1. We are obtaining pointers to references which are guaranteed to be valid. - // 2. They cannot overlap because we obtain pointers to difference indices of the slice. - // Namely, `i` and `i+1`. - // 3. If the slice is properly aligned, the elements are properly aligned. - // It is the caller's responsibility to make sure the slice is properly aligned. - // - // See comments below for further detail. + debug_assert!(v.len() >= 2); + unsafe { - // If the last two elements are out-of-order... - if len >= 2 && is_less(v.get_unchecked(len - 1), v.get_unchecked(len - 2)) { - // Read the last element into a stack-allocated variable. If a following comparison - // operation panics, `hole` will get dropped and automatically write the element back - // into the slice. - let tmp = mem::ManuallyDrop::new(ptr::read(v.get_unchecked(len - 1))); - let v = v.as_mut_ptr(); - let mut hole = CopyOnDrop { src: &*tmp, dest: v.add(len - 2) }; - ptr::copy_nonoverlapping(v.add(len - 2), v.add(len - 1), 1); - - for i in (0..len - 2).rev() { - if !is_less(&*tmp, &*v.add(i)) { + if is_less(v.get_unchecked(1), v.get_unchecked(0)) { + let arr_ptr = v.as_mut_ptr(); + + // There are three ways to implement insertion here: + // + // 1. Swap adjacent elements until the first one gets to its final destination. + // However, this way we copy data around more than is necessary. If elements are big + // structures (costly to copy), this method will be slow. + // + // 2. Iterate until the right place for the first element is found. Then shift the + // elements succeeding it to make room for it and finally place it into the + // remaining hole. This is a good method. + // + // 3. Copy the first element into a temporary variable. Iterate until the right place + // for it is found. As we go along, copy every traversed element into the slot + // preceding it. Finally, copy data from the temporary variable into the remaining + // hole. This method is very good. Benchmarks demonstrated slightly better + // performance than with the 2nd method. + // + // All methods were benchmarked, and the 3rd showed best results. So we chose that one. + let tmp = mem::ManuallyDrop::new(ptr::read(arr_ptr)); + + // Intermediate state of the insertion process is always tracked by `hole`, which + // serves two purposes: + // 1. Protects integrity of `v` from panics in `is_less`. + // 2. Fills the remaining hole in `v` in the end. + // + // Panic safety: + // + // 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: &*tmp, dest: arr_ptr.add(1) }; + ptr::copy_nonoverlapping(arr_ptr.add(1), arr_ptr.add(0), 1); + + for i in 2..v.len() { + if !is_less(&v.get_unchecked(i), &*tmp) { break; } - - // Move `i`-th element one place to the right, thus shifting the hole to the left. - ptr::copy_nonoverlapping(v.add(i), v.add(i + 1), 1); - hole.dest = v.add(i); + ptr::copy_nonoverlapping(arr_ptr.add(i), arr_ptr.add(i - 1), 1); + hole.dest = arr_ptr.add(i); } // `hole` gets dropped and thus copies `tmp` into the remaining hole in `v`. } } } +/// Sort `v` assuming `v[..offset]` is already sorted. +/// +/// Never inline this function to avoid code bloat. It still optimizes nicely and has practically no +/// performance impact. Even improving performance in some cases. +#[inline(never)] +fn insertion_sort_shift_left(v: &mut [T], offset: usize, is_less: &mut F) +where + F: FnMut(&T, &T) -> bool, +{ + let len = v.len(); + + // Using assert here improves performance. + assert!(offset != 0 && offset <= len); + + // Shift each element of the unsorted region v[i..] as far left as is needed to make v sorted. + for i in offset..len { + // SAFETY: we tested that `offset` must be at least 1, so this loop is only entered if len + // >= 2. + unsafe { + insert_tail(&mut v[..=i], is_less); + } + } +} + +/// Sort `v` assuming `v[offset..]` is already sorted. +/// +/// Never inline this function to avoid code bloat. It still optimizes nicely and has practically no +/// performance impact. Even improving performance in some cases. +#[inline(never)] +fn insertion_sort_shift_right(v: &mut [T], offset: usize, is_less: &mut F) +where + F: FnMut(&T, &T) -> bool, +{ + let len = v.len(); + + // Using assert here improves performance. + assert!(offset != 0 && offset <= len && len >= 2); + + // Shift each element of the unsorted region v[..i] as far left as is needed to make v sorted. + for i in (0..offset).rev() { + // We ensured that the slice length is always at least 2 long. + // We know that start_found will be at least one less than end, + // and the range is exclusive. Which gives us i always <= (end - 2). + unsafe { + insert_head(&mut v[i..len], is_less); + } + } +} + /// Partially sorts a slice by shifting several out-of-order elements around. /// /// Returns `true` if the slice is sorted at the end. This function is *O*(*n*) worst-case. @@ -161,26 +224,19 @@ where // Swap the found pair of elements. This puts them in correct order. v.swap(i - 1, i); - // Shift the smaller element to the left. - shift_tail(&mut v[..i], is_less); - // Shift the greater element to the right. - shift_head(&mut v[i..], is_less); + if i >= 2 { + // Shift the smaller element to the left. + insertion_sort_shift_left(&mut v[..i], i - 1, is_less); + + // Shift the greater element to the right. + insertion_sort_shift_right(&mut v[..i], 1, is_less); + } } // Didn't manage to sort the slice in the limited number of steps. false } -/// Sorts a slice using insertion sort, which is *O*(*n*^2) worst-case. -fn insertion_sort(v: &mut [T], is_less: &mut F) -where - F: FnMut(&T, &T) -> bool, -{ - for i in 1..v.len() { - shift_tail(&mut v[..i + 1], is_less); - } -} - /// Sorts `v` using heapsort, which guarantees *O*(*n* \* log(*n*)) worst-case. #[cold] #[unstable(feature = "sort_internals", reason = "internal to sort module", issue = "none")] @@ -507,7 +563,7 @@ where // SAFETY: `pivot` is a reference to the first element of `v`, so `ptr::read` is safe. let tmp = mem::ManuallyDrop::new(unsafe { ptr::read(pivot) }); - let _pivot_guard = CopyOnDrop { src: &*tmp, dest: pivot }; + let _pivot_guard = InsertionHole { src: &*tmp, dest: pivot }; let pivot = &*tmp; // Find the first pair of out-of-order elements. @@ -560,7 +616,7 @@ where // operation panics, the pivot will be automatically written back into the slice. // SAFETY: The pointer here is valid because it is obtained from a reference to a slice. let tmp = mem::ManuallyDrop::new(unsafe { ptr::read(pivot) }); - let _pivot_guard = CopyOnDrop { src: &*tmp, dest: pivot }; + let _pivot_guard = InsertionHole { src: &*tmp, dest: pivot }; let pivot = &*tmp; // Now partition the slice. @@ -742,7 +798,9 @@ where // Very short slices get sorted using insertion sort. if len <= MAX_INSERTION { - insertion_sort(v, is_less); + if len >= 2 { + insertion_sort_shift_left(v, 1, is_less); + } return; } @@ -844,10 +902,14 @@ fn partition_at_index_loop<'a, T, F>( let mut was_balanced = true; loop { + let len = v.len(); + // For slices of up to this length it's probably faster to simply sort them. const MAX_INSERTION: usize = 10; - if v.len() <= MAX_INSERTION { - insertion_sort(v, is_less); + if len <= MAX_INSERTION { + if len >= 2 { + insertion_sort_shift_left(v, 1, is_less); + } return; } @@ -887,7 +949,7 @@ fn partition_at_index_loop<'a, T, F>( } let (mid, _) = partition(v, pivot, is_less); - was_balanced = cmp::min(mid, v.len() - mid) >= v.len() / 8; + was_balanced = cmp::min(mid, len - mid) >= len / 8; // Split the slice into `left`, `pivot`, and `right`. let (left, right) = v.split_at_mut(mid); @@ -954,75 +1016,6 @@ where (left, pivot, right) } -/// Inserts `v[0]` into pre-sorted sequence `v[1..]` so that whole `v[..]` becomes sorted. -/// -/// This is the integral subroutine of insertion sort. -fn insert_head(v: &mut [T], is_less: &mut F) -where - F: FnMut(&T, &T) -> bool, -{ - if v.len() >= 2 && is_less(&v[1], &v[0]) { - // SAFETY: Copy tmp back even if panic, and ensure unique observation. - unsafe { - // There are three ways to implement insertion here: - // - // 1. Swap adjacent elements until the first one gets to its final destination. - // However, this way we copy data around more than is necessary. If elements are big - // structures (costly to copy), this method will be slow. - // - // 2. Iterate until the right place for the first element is found. Then shift the - // elements succeeding it to make room for it and finally place it into the - // remaining hole. This is a good method. - // - // 3. Copy the first element into a temporary variable. Iterate until the right place - // for it is found. As we go along, copy every traversed element into the slot - // preceding it. Finally, copy data from the temporary variable into the remaining - // hole. This method is very good. Benchmarks demonstrated slightly better - // performance than with the 2nd method. - // - // All methods were benchmarked, and the 3rd showed best results. So we chose that one. - let tmp = mem::ManuallyDrop::new(ptr::read(&v[0])); - - // Intermediate state of the insertion process is always tracked by `hole`, which - // serves two purposes: - // 1. Protects integrity of `v` from panics in `is_less`. - // 2. Fills the remaining hole in `v` in the end. - // - // Panic safety: - // - // 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: &*tmp, dest: &mut v[1] }; - ptr::copy_nonoverlapping(&v[1], &mut v[0], 1); - - for i in 2..v.len() { - if !is_less(&v[i], &*tmp) { - break; - } - ptr::copy_nonoverlapping(&v[i], &mut v[i - 1], 1); - hole.dest = &mut v[i]; - } - // `hole` gets dropped and thus copies `tmp` into the remaining hole in `v`. - } - } - - // When dropped, copies from `src` into `dest`. - struct InsertionHole { - src: *const T, - dest: *mut T, - } - - impl Drop for InsertionHole { - fn drop(&mut self) { - // SAFETY: The caller must ensure that src and dest are correctly set. - unsafe { - ptr::copy_nonoverlapping(self.src, self.dest, 1); - } - } - } -} - /// Merges non-decreasing runs `v[..mid]` and `v[mid..]` using `buf` as temporary storage, and /// stores the result into `v[..]`. /// @@ -1180,8 +1173,6 @@ pub fn merge_sort( { // Slices of up to this length get sorted using insertion sort. const MAX_INSERTION: usize = 20; - // Very short runs are extended using insertion sort to span at least this many elements. - const MIN_RUN: usize = 10; // The caller should have already checked that. debug_assert!(!T::IS_ZST); @@ -1191,9 +1182,7 @@ pub fn merge_sort( // 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() { - insert_head(&mut v[i..], is_less); - } + insertion_sort_shift_left(v, 1, is_less); } return; } @@ -1236,10 +1225,7 @@ pub fn merge_sort( // Insert some more elements into the run if it's too short. Insertion sort is faster than // merge sort on short sequences, so this significantly improves performance. - while start > 0 && end - start < MIN_RUN { - start -= 1; - insert_head(&mut v[start..end], is_less); - } + start = provide_sorted_batch(v, start, end, is_less); // Push this run onto the stack. runs.push(TimSortRun { start, len: end - start }); @@ -1467,3 +1453,34 @@ pub struct TimSortRun { len: usize, start: usize, } + +/// Takes a range as denoted by start and end, that is already sorted and extends it to the left if +/// necessary with sorts optimized for smaller ranges such as insertion sort. +#[cfg(not(no_global_oom_handling))] +fn provide_sorted_batch(v: &mut [T], mut start: usize, end: usize, is_less: &mut F) -> usize +where + F: FnMut(&T, &T) -> bool, +{ + debug_assert!(end > start); + + // This value is a balance between least comparisons and best performance, as + // influenced by for example cache locality. + const MIN_INSERTION_RUN: usize = 10; + + // Insert some more elements into the run if it's too short. Insertion sort is faster than + // merge sort on short sequences, so this significantly improves performance. + let start_found = start; + let start_end_diff = end - start; + + if start_end_diff < MIN_INSERTION_RUN && start != 0 { + // v[start_found..end] are elements that are already sorted in the input. We want to extend + // the sorted region to the left, so we push up MIN_INSERTION_RUN - 1 to the right. Which is + // more efficient that trying to push those already sorted elements to the left. + + start = if end >= MIN_INSERTION_RUN { end - MIN_INSERTION_RUN } else { 0 }; + + insertion_sort_shift_right(&mut v[start..end], start_found - start, is_less); + } + + start +} -- cgit 1.4.1-3-g733a5 From f297afa0c91243b17283be17864f2c48f91127d9 Mon Sep 17 00:00:00 2001 From: Lukas Bergdoll Date: Sun, 22 Jan 2023 12:01:06 +0100 Subject: Flip scanning direction of stable sort Memory pre-fetching prefers forward scanning vs backwards scanning, and the code-gen is usually better. For the most sensitive types such as integers, these are planned to be merged bidirectionally at once. So there is no benefit in scanning backwards. The largest perf gains are seen for full ascending and descending inputs, which see 1.5x speedups. Random inputs benefit too, and some patterns can loose out, but these losses are minimal. --- library/core/src/slice/sort.rs | 112 ++++++++++++++++++++++++----------------- 1 file changed, 67 insertions(+), 45 deletions(-) (limited to 'library/core/src') diff --git a/library/core/src/slice/sort.rs b/library/core/src/slice/sort.rs index 6bb53b16e61..227db51a0b4 100644 --- a/library/core/src/slice/sort.rs +++ b/library/core/src/slice/sort.rs @@ -1196,52 +1196,37 @@ pub fn merge_sort( let mut runs = RunVec::new(run_alloc_fn, run_dealloc_fn); - // In order to identify natural runs in `v`, we traverse it backwards. That might seem like a - // strange decision, but consider the fact that merges more often go in the opposite direction - // (forwards). According to benchmarks, merging forwards is slightly faster than merging - // backwards. To conclude, identifying runs by traversing backwards improves performance. - let mut end = len; - while end > 0 { - // Find the next natural run, and reverse it if it's strictly descending. - let mut start = end - 1; - if start > 0 { - start -= 1; - - // SAFETY: The v.get_unchecked must be fed with correct inbound indicies. - 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)) { - start -= 1; - } - v[start..end].reverse(); - } else { - while start > 0 && !is_less(v.get_unchecked(start), v.get_unchecked(start - 1)) - { - start -= 1; - } - } - } + let mut end = 0; + let mut start = 0; + + // Scan forward. Memory pre-fetching prefers forward scanning vs backwards scanning, and the + // code-gen is usually better. For the most sensitive types such as integers, these are merged + // bidirectionally at once. So there is no benefit in scanning backwards. + while end < len { + let (streak_end, was_reversed) = find_streak(&v[start..], is_less); + end += streak_end; + if was_reversed { + v[start..end].reverse(); } // Insert some more elements into the run if it's too short. Insertion sort is faster than // merge sort on short sequences, so this significantly improves performance. - start = provide_sorted_batch(v, start, end, is_less); + end = provide_sorted_batch(v, start, end, is_less); // Push this run onto the stack. runs.push(TimSortRun { start, len: end - start }); - end = start; + start = end; // Merge some pairs of adjacent runs to satisfy the invariants. - while let Some(r) = collapse(runs.as_slice()) { - let left = runs[r + 1]; - let right = runs[r]; - // SAFETY: `buf_ptr` must hold enough capacity for the shorter of the two sides, and - // neither side may be on length 0. + while let Some(r) = collapse(runs.as_slice(), len) { + let left = runs[r]; + let right = runs[r + 1]; + let merge_slice = &mut v[left.start..right.start + right.len]; unsafe { - merge(&mut v[left.start..right.start + right.len], left.len, buf_ptr, is_less); + merge(merge_slice, left.len, buf_ptr, is_less); } - runs[r] = TimSortRun { start: left.start, len: left.len + right.len }; - runs.remove(r + 1); + runs[r + 1] = TimSortRun { start: left.start, len: left.len + right.len }; + runs.remove(r); } } @@ -1263,10 +1248,10 @@ pub fn merge_sort( // run starts at index 0, it will always demand a merge operation until the stack is fully // collapsed, in order to complete the sort. #[inline] - fn collapse(runs: &[TimSortRun]) -> Option { + fn collapse(runs: &[TimSortRun], stop: usize) -> Option { let n = runs.len(); if n >= 2 - && (runs[n - 1].start == 0 + && (runs[n - 1].start + runs[n - 1].len == stop || 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)) @@ -1454,14 +1439,15 @@ pub struct TimSortRun { start: usize, } -/// Takes a range as denoted by start and end, that is already sorted and extends it to the left if +/// Takes a range as denoted by start and end, that is already sorted and extends it to the right if /// necessary with sorts optimized for smaller ranges such as insertion sort. #[cfg(not(no_global_oom_handling))] -fn provide_sorted_batch(v: &mut [T], mut start: usize, end: usize, is_less: &mut F) -> usize +fn provide_sorted_batch(v: &mut [T], start: usize, mut end: usize, is_less: &mut F) -> usize where F: FnMut(&T, &T) -> bool, { - debug_assert!(end > start); + let len = v.len(); + assert!(end >= start && end <= len); // This value is a balance between least comparisons and best performance, as // influenced by for example cache locality. @@ -1469,18 +1455,54 @@ where // Insert some more elements into the run if it's too short. Insertion sort is faster than // merge sort on short sequences, so this significantly improves performance. - let start_found = start; let start_end_diff = end - start; - if start_end_diff < MIN_INSERTION_RUN && start != 0 { + if start_end_diff < MIN_INSERTION_RUN && end < len { // v[start_found..end] are elements that are already sorted in the input. We want to extend // the sorted region to the left, so we push up MIN_INSERTION_RUN - 1 to the right. Which is // more efficient that trying to push those already sorted elements to the left. + end = cmp::min(start + MIN_INSERTION_RUN, len); + let presorted_start = cmp::max(start_end_diff, 1); - start = if end >= MIN_INSERTION_RUN { end - MIN_INSERTION_RUN } else { 0 }; + insertion_sort_shift_left(&mut v[start..end], presorted_start, is_less); + } - insertion_sort_shift_right(&mut v[start..end], start_found - start, is_less); + end +} + +/// Finds a streak of presorted elements starting at the beginning of the slice. Returns the first +/// value that is not part of said streak, and a bool denoting wether the streak was reversed. +/// Streaks can be increasing or decreasing. +fn find_streak(v: &[T], is_less: &mut F) -> (usize, bool) +where + F: FnMut(&T, &T) -> bool, +{ + let len = v.len(); + + if len < 2 { + return (len, false); } - start + let mut end = 2; + + // SAFETY: See below specific. + unsafe { + // SAFETY: We checked that len >= 2, so 0 and 1 are valid indices. + let assume_reverse = is_less(v.get_unchecked(1), v.get_unchecked(0)); + + // SAFETY: We know end >= 2 and check end < len. + // From that follows that accessing v at end and end - 1 is safe. + if assume_reverse { + while end < len && is_less(v.get_unchecked(end), v.get_unchecked(end - 1)) { + end += 1; + } + + (end, true) + } else { + while end < len && !is_less(v.get_unchecked(end), v.get_unchecked(end - 1)) { + end += 1; + } + (end, false) + } + } } -- cgit 1.4.1-3-g733a5 From 5eff2645335e86f714a92a592f81936fead1f6a4 Mon Sep 17 00:00:00 2001 From: Lukas Bergdoll Date: Mon, 23 Jan 2023 09:12:25 +0100 Subject: Document missing unsafe blocks --- library/core/src/slice/sort.rs | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-) (limited to 'library/core/src') diff --git a/library/core/src/slice/sort.rs b/library/core/src/slice/sort.rs index 227db51a0b4..fc35c46d583 100644 --- a/library/core/src/slice/sort.rs +++ b/library/core/src/slice/sort.rs @@ -21,6 +21,9 @@ struct InsertionHole { impl Drop for InsertionHole { fn drop(&mut self) { + // SAFETY: This is a helper class. Please refer to its usage for correctness. Namely, one + // must be sure that `src` and `dst` does not overlap as required by + // `ptr::copy_nonoverlapping` and are both valid for writes. unsafe { ptr::copy_nonoverlapping(self.src, self.dest, 1); } @@ -88,6 +91,7 @@ where { debug_assert!(v.len() >= 2); + // SAFETY: caller must ensure v is at least len 2. unsafe { if is_less(v.get_unchecked(1), v.get_unchecked(0)) { let arr_ptr = v.as_mut_ptr(); @@ -153,7 +157,8 @@ where // Shift each element of the unsorted region v[i..] as far left as is needed to make v sorted. for i in offset..len { // SAFETY: we tested that `offset` must be at least 1, so this loop is only entered if len - // >= 2. + // >= 2. The range is exclusive and we know `i` must be at least 1 so this slice has at + // >least len 2. unsafe { insert_tail(&mut v[..=i], is_less); } @@ -176,9 +181,10 @@ where // Shift each element of the unsorted region v[..i] as far left as is needed to make v sorted. for i in (0..offset).rev() { - // We ensured that the slice length is always at least 2 long. - // We know that start_found will be at least one less than end, - // and the range is exclusive. Which gives us i always <= (end - 2). + // SAFETY: we tested that `offset` must be at least 1, so this loop is only entered if len + // >= 2.We ensured that the slice length is always at least 2 long. We know that start_found + // will be at least one less than end, and the range is exclusive. Which gives us i always + // <= (end - 2). unsafe { insert_head(&mut v[i..len], is_less); } @@ -1222,6 +1228,8 @@ pub fn merge_sort( let left = runs[r]; let right = runs[r + 1]; let merge_slice = &mut v[left.start..right.start + right.len]; + // SAFETY: `buf_ptr` must hold enough capacity for the shorter of the two sides, and + // neither side may be on length 0. unsafe { merge(merge_slice, left.len, buf_ptr, is_less); } -- cgit 1.4.1-3-g733a5 From d1052349affb49f87d6684f4b7781dbcba8db5a2 Mon Sep 17 00:00:00 2001 From: Peter Jaszkowiak Date: Fri, 3 Feb 2023 16:50:49 -0700 Subject: reword descriptions of the deprecated int modules --- library/core/src/num/shells/i128.rs | 4 +--- library/core/src/num/shells/i16.rs | 4 +--- library/core/src/num/shells/i32.rs | 4 +--- library/core/src/num/shells/i64.rs | 4 +--- library/core/src/num/shells/i8.rs | 4 +--- library/core/src/num/shells/isize.rs | 4 +--- library/core/src/num/shells/u128.rs | 4 +--- library/core/src/num/shells/u16.rs | 4 +--- library/core/src/num/shells/u32.rs | 4 +--- library/core/src/num/shells/u64.rs | 4 +--- library/core/src/num/shells/u8.rs | 4 +--- library/core/src/num/shells/usize.rs | 4 +--- 12 files changed, 12 insertions(+), 36 deletions(-) (limited to 'library/core/src') diff --git a/library/core/src/num/shells/i128.rs b/library/core/src/num/shells/i128.rs index 7b048dc5206..b3b3d3b4875 100644 --- a/library/core/src/num/shells/i128.rs +++ b/library/core/src/num/shells/i128.rs @@ -1,6 +1,4 @@ -//! Constants for the 128-bit signed integer type. -//! -//! *[See also the `i128` primitive type][i128].* +//! Redundant constants module for the [`i128` primitive type][i128]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/i16.rs b/library/core/src/num/shells/i16.rs index 5c5812d5c5e..70a452e1939 100644 --- a/library/core/src/num/shells/i16.rs +++ b/library/core/src/num/shells/i16.rs @@ -1,6 +1,4 @@ -//! Constants for the 16-bit signed integer type. -//! -//! *[See also the `i16` primitive type][i16].* +//! Redundant constants module for the [`i16` primitive type][i16]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/i32.rs b/library/core/src/num/shells/i32.rs index b283ac64415..c30849e2591 100644 --- a/library/core/src/num/shells/i32.rs +++ b/library/core/src/num/shells/i32.rs @@ -1,6 +1,4 @@ -//! Constants for the 32-bit signed integer type. -//! -//! *[See also the `i32` primitive type][i32].* +//! Redundant constants module for the [`i32` primitive type][i32]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/i64.rs b/library/core/src/num/shells/i64.rs index a416fa7e936..77d95d71250 100644 --- a/library/core/src/num/shells/i64.rs +++ b/library/core/src/num/shells/i64.rs @@ -1,6 +1,4 @@ -//! Constants for the 64-bit signed integer type. -//! -//! *[See also the `i64` primitive type][i64].* +//! Redundant constants module for the [`i64` primitive type][i64]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/i8.rs b/library/core/src/num/shells/i8.rs index 02465013a4a..516ba8cdef3 100644 --- a/library/core/src/num/shells/i8.rs +++ b/library/core/src/num/shells/i8.rs @@ -1,6 +1,4 @@ -//! Constants for the 8-bit signed integer type. -//! -//! *[See also the `i8` primitive type][i8].* +//! Redundant constants module for the [`i8` primitive type][i8]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/isize.rs b/library/core/src/num/shells/isize.rs index 1579fbab6d4..828f7345baf 100644 --- a/library/core/src/num/shells/isize.rs +++ b/library/core/src/num/shells/isize.rs @@ -1,6 +1,4 @@ -//! Constants for the pointer-sized signed integer type. -//! -//! *[See also the `isize` primitive type][isize].* +//! Redundant constants module for the [`isize` primitive type][isize]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/u128.rs b/library/core/src/num/shells/u128.rs index fe08cee586c..b1e30e38435 100644 --- a/library/core/src/num/shells/u128.rs +++ b/library/core/src/num/shells/u128.rs @@ -1,6 +1,4 @@ -//! Constants for the 128-bit unsigned integer type. -//! -//! *[See also the `u128` primitive type][u128].* +//! Redundant constants module for the [`u128` primitive type][u128]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/u16.rs b/library/core/src/num/shells/u16.rs index 36f8c697878..b203806f460 100644 --- a/library/core/src/num/shells/u16.rs +++ b/library/core/src/num/shells/u16.rs @@ -1,6 +1,4 @@ -//! Constants for the 16-bit unsigned integer type. -//! -//! *[See also the `u16` primitive type][u16].* +//! Redundant constants module for the [`i16` primitive type][i16]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/u32.rs b/library/core/src/num/shells/u32.rs index 1c369097dcd..4c84274e752 100644 --- a/library/core/src/num/shells/u32.rs +++ b/library/core/src/num/shells/u32.rs @@ -1,6 +1,4 @@ -//! Constants for the 32-bit unsigned integer type. -//! -//! *[See also the `u32` primitive type][u32].* +//! Redundant constants module for the [`u32` primitive type][u32]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/u64.rs b/library/core/src/num/shells/u64.rs index e8b691d1555..47a95c6820f 100644 --- a/library/core/src/num/shells/u64.rs +++ b/library/core/src/num/shells/u64.rs @@ -1,6 +1,4 @@ -//! Constants for the 64-bit unsigned integer type. -//! -//! *[See also the `u64` primitive type][u64].* +//! Redundant constants module for the [`u64` primitive type][u64]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/u8.rs b/library/core/src/num/shells/u8.rs index 817c6a18aaa..360baef7228 100644 --- a/library/core/src/num/shells/u8.rs +++ b/library/core/src/num/shells/u8.rs @@ -1,6 +1,4 @@ -//! Constants for the 8-bit unsigned integer type. -//! -//! *[See also the `u8` primitive type][u8].* +//! Redundant constants module for the [`u8` primitive type][u8]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/usize.rs b/library/core/src/num/shells/usize.rs index 3e1bec5ec48..44c24dfc2cf 100644 --- a/library/core/src/num/shells/usize.rs +++ b/library/core/src/num/shells/usize.rs @@ -1,6 +1,4 @@ -//! Constants for the pointer-sized unsigned integer type. -//! -//! *[See also the `usize` primitive type][usize].* +//! Redundant constants module for the [`usize` primitive type][usize]. //! //! New code should use the associated constants directly on the primitive type. -- cgit 1.4.1-3-g733a5 From fa6c3a2d2aab19fa95c8612c53ac87ac4c8c64dc Mon Sep 17 00:00:00 2001 From: Michael Howell Date: Fri, 3 Feb 2023 19:02:20 -0700 Subject: docs: update fragment for Result impls --- library/core/src/result.rs | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'library/core/src') diff --git a/library/core/src/result.rs b/library/core/src/result.rs index f00c40f35d5..7596e9cc005 100644 --- a/library/core/src/result.rs +++ b/library/core/src/result.rs @@ -458,7 +458,7 @@ //! [`Result`] of a collection of each contained value of the original //! [`Result`] values, or [`Err`] if any of the elements was [`Err`]. //! -//! [impl-FromIterator]: Result#impl-FromIterator%3CResult%3CA%2C%20E%3E%3E-for-Result%3CV%2C%20E%3E +//! [impl-FromIterator]: Result#impl-FromIterator%3CResult%3CA,+E%3E%3E-for-Result%3CV,+E%3E //! //! ``` //! let v = [Ok(2), Ok(4), Err("err!"), Ok(8)]; @@ -474,8 +474,8 @@ //! to provide the [`product`][Iterator::product] and //! [`sum`][Iterator::sum] methods. //! -//! [impl-Product]: Result#impl-Product%3CResult%3CU%2C%20E%3E%3E-for-Result%3CT%2C%20E%3E -//! [impl-Sum]: Result#impl-Sum%3CResult%3CU%2C%20E%3E%3E-for-Result%3CT%2C%20E%3E +//! [impl-Product]: Result#impl-Product%3CResult%3CU,+E%3E%3E-for-Result%3CT,+E%3E +//! [impl-Sum]: Result#impl-Sum%3CResult%3CU,+E%3E%3E-for-Result%3CT,+E%3E //! //! ``` //! let v = [Err("error!"), Ok(1), Ok(2), Ok(3), Err("foo")]; -- cgit 1.4.1-3-g733a5 From 5a7342c3dde43c96a71bc27995030896342761f6 Mon Sep 17 00:00:00 2001 From: Scott McMurray Date: Thu, 2 Feb 2023 20:58:22 -0800 Subject: Stop using `into_iter` in `array::map` --- library/core/src/array/drain.rs | 51 +++++++++++++++++++++++++++++++++++++++++ library/core/src/array/mod.rs | 34 ++++++++++++++++++--------- library/core/tests/array.rs | 25 ++++++++++++++++++++ tests/codegen/array-map.rs | 48 ++++++++++++++++++++++++++++++++++++++ 4 files changed, 147 insertions(+), 11 deletions(-) create mode 100644 library/core/src/array/drain.rs create mode 100644 tests/codegen/array-map.rs (limited to 'library/core/src') diff --git a/library/core/src/array/drain.rs b/library/core/src/array/drain.rs new file mode 100644 index 00000000000..5ca93d54f87 --- /dev/null +++ b/library/core/src/array/drain.rs @@ -0,0 +1,51 @@ +use crate::iter::TrustedLen; +use crate::mem::ManuallyDrop; +use crate::ptr::drop_in_place; +use crate::slice; + +// INVARIANT: It's ok to drop the remainder of the inner iterator. +pub(crate) struct Drain<'a, T>(slice::IterMut<'a, T>); + +pub(crate) fn drain_array_with( + array: [T; N], + func: impl for<'a> FnOnce(Drain<'a, T>) -> R, +) -> R { + let mut array = ManuallyDrop::new(array); + // SAFETY: Now that the local won't drop it, it's ok to construct the `Drain` which will. + let drain = Drain(array.iter_mut()); + func(drain) +} + +impl Drop for Drain<'_, T> { + fn drop(&mut self) { + // SAFETY: By the type invariant, we're allowed to drop all these. + unsafe { drop_in_place(self.0.as_mut_slice()) } + } +} + +impl Iterator for Drain<'_, T> { + type Item = T; + + #[inline] + fn next(&mut self) -> Option { + let p: *const T = self.0.next()?; + // SAFETY: The iterator was already advanced, so we won't drop this later. + Some(unsafe { p.read() }) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + let n = self.len(); + (n, Some(n)) + } +} + +impl ExactSizeIterator for Drain<'_, T> { + #[inline] + fn len(&self) -> usize { + self.0.len() + } +} + +// SAFETY: This is a 1:1 wrapper for a slice iterator, which is also `TrustedLen`. +unsafe impl TrustedLen for Drain<'_, T> {} diff --git a/library/core/src/array/mod.rs b/library/core/src/array/mod.rs index 2825e0bbb43..ee340f38543 100644 --- a/library/core/src/array/mod.rs +++ b/library/core/src/array/mod.rs @@ -17,9 +17,12 @@ use crate::ops::{ }; use crate::slice::{Iter, IterMut}; +mod drain; mod equality; mod iter; +pub(crate) use drain::drain_array_with; + #[stable(feature = "array_value_iter", since = "1.51.0")] pub use iter::IntoIter; @@ -513,9 +516,12 @@ impl [T; N] { where F: FnMut(T) -> U, { - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { collect_into_array_unchecked(&mut IntoIterator::into_iter(self).map(f)) } + drain_array_with(self, |iter| { + let mut iter = iter.map(f); + // SAFETY: we know for certain that this iterator will yield exactly `N` + // items. + unsafe { collect_into_array_unchecked(&mut iter) } + }) } /// A fallible function `f` applied to each element on array `self` in order to @@ -552,9 +558,12 @@ impl [T; N] { R: Try, R::Residual: Residual<[R::Output; N]>, { - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { try_collect_into_array_unchecked(&mut IntoIterator::into_iter(self).map(f)) } + drain_array_with(self, |iter| { + let mut iter = iter.map(f); + // SAFETY: we know for certain that this iterator will yield exactly `N` + // items. + unsafe { try_collect_into_array_unchecked(&mut iter) } + }) } /// 'Zips up' two arrays into a single array of pairs. @@ -575,11 +584,14 @@ impl [T; N] { /// ``` #[unstable(feature = "array_zip", issue = "80094")] pub fn zip(self, rhs: [U; N]) -> [(T, U); N] { - let mut iter = IntoIterator::into_iter(self).zip(rhs); - - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { collect_into_array_unchecked(&mut iter) } + drain_array_with(self, |lhs| { + drain_array_with(rhs, |rhs| { + let mut iter = crate::iter::zip(lhs, rhs); + // SAFETY: we know for certain that this iterator will yield exactly `N` + // items. + unsafe { collect_into_array_unchecked(&mut iter) } + }) + }) } /// Returns a slice containing the entire array. Equivalent to `&s[..]`. diff --git a/library/core/tests/array.rs b/library/core/tests/array.rs index f268fe3ae7b..5327e4f8139 100644 --- a/library/core/tests/array.rs +++ b/library/core/tests/array.rs @@ -700,3 +700,28 @@ fn array_into_iter_rfold() { let s = it.rfold(10, |a, b| 10 * a + b); assert_eq!(s, 10432); } + +#[cfg(not(panic = "abort"))] +#[test] +fn array_map_drops_unmapped_elements_on_panic() { + struct DropCounter<'a>(usize, &'a AtomicUsize); + impl Drop for DropCounter<'_> { + fn drop(&mut self) { + self.1.fetch_add(1, Ordering::SeqCst); + } + } + + const MAX: usize = 11; + for panic_after in 0..MAX { + let counter = AtomicUsize::new(0); + let a = array::from_fn::<_, 11, _>(|i| DropCounter(i, &counter)); + let success = std::panic::catch_unwind(|| { + let _ = a.map(|x| { + assert!(x.0 < panic_after); + assert_eq!(counter.load(Ordering::SeqCst), x.0); + }); + }); + assert!(success.is_err()); + assert_eq!(counter.load(Ordering::SeqCst), MAX); + } +} diff --git a/tests/codegen/array-map.rs b/tests/codegen/array-map.rs new file mode 100644 index 00000000000..37585371a32 --- /dev/null +++ b/tests/codegen/array-map.rs @@ -0,0 +1,48 @@ +// compile-flags: -C opt-level=3 -C target-cpu=x86-64-v3 -C llvm-args=-x86-asm-syntax=intel --emit=llvm-ir,asm +// no-system-llvm +// only-x86_64 +// ignore-debug (the extra assertions get in the way) + +#![crate_type = "lib"] +#![feature(array_zip)] + +// CHECK-LABEL: @short_integer_map +#[no_mangle] +pub fn short_integer_map(x: [u32; 8]) -> [u32; 8] { + // CHECK: load <8 x i32> + // CHECK: shl <8 x i32> + // CHECK: or <8 x i32> + // CHECK: store <8 x i32> + x.map(|x| 2 * x + 1) +} + +// CHECK-LABEL: @short_integer_zip_map +#[no_mangle] +pub fn short_integer_zip_map(x: [u32; 8], y: [u32; 8]) -> [u32; 8] { + // CHECK: %[[A:.+]] = load <8 x i32> + // CHECK: %[[B:.+]] = load <8 x i32> + // CHECK: sub <8 x i32> %[[A]], %[[B]] + // CHECK: store <8 x i32> + x.zip(y).map(|(x, y)| x - y) +} + +// This test is checking that LLVM can SRoA away a bunch of the overhead, +// like fully moving the iterators to registers. Notably, previous implementations +// of `map` ended up `alloca`ing the whole `array::IntoIterator`, meaning both a +// hard-to-eliminate `memcpy` and that the iteration counts needed to be written +// out to stack every iteration, even for infallible operations on `Copy` types. +// +// This is still imperfect, as there's more copies than would be ideal, +// but hopefully work like #103830 will improve that in future, +// and update this test to be stricter. +// +// CHECK-LABEL: @long_integer_map +#[no_mangle] +pub fn long_integer_map(x: [u32; 64]) -> [u32; 64] { + // CHECK: start: + // CHECK-NEXT: alloca [{{64|65}} x i32] + // CHECK-NEXT: alloca [{{64|65}} x i32] + // CHECK-NEXT: alloca %"core::mem::manually_drop::ManuallyDrop<[u32; 64]>" + // CHECK-NOT: alloca + x.map(|x| 2 * x + 1) +} -- cgit 1.4.1-3-g733a5 From 52df0558ea349fa65036e61f0a647ea8072ec3f5 Mon Sep 17 00:00:00 2001 From: Scott McMurray Date: Thu, 2 Feb 2023 22:15:23 -0800 Subject: Stop forcing `array::map` through an unnecessary `Result` --- library/core/src/array/mod.rs | 126 +++++++++++++++++++++++------------------- tests/codegen/array-map.rs | 5 +- 2 files changed, 71 insertions(+), 60 deletions(-) (limited to 'library/core/src') diff --git a/library/core/src/array/mod.rs b/library/core/src/array/mod.rs index ee340f38543..45ec68e6e7a 100644 --- a/library/core/src/array/mod.rs +++ b/library/core/src/array/mod.rs @@ -825,14 +825,13 @@ impl [T; N] { /// Pulls `N` items from `iter` and returns them as an array. If the iterator /// yields fewer than `N` items, this function exhibits undefined behavior. /// -/// See [`try_collect_into_array`] for more information. -/// -/// /// # Safety /// /// It is up to the caller to guarantee that `iter` yields at least `N` items. /// Violating this condition causes undefined behavior. -unsafe fn try_collect_into_array_unchecked(iter: &mut I) -> R::TryType +unsafe fn try_collect_into_array_unchecked( + iter: &mut I, +) -> ChangeOutputType where // Note: `TrustedLen` here is somewhat of an experiment. This is just an // internal function, so feel free to remove if this bound turns out to be a @@ -845,11 +844,21 @@ where debug_assert!(N <= iter.size_hint().1.unwrap_or(usize::MAX)); debug_assert!(N <= iter.size_hint().0); - // SAFETY: covered by the function contract. - unsafe { try_collect_into_array(iter).unwrap_unchecked() } + let mut array = MaybeUninit::uninit_array::(); + let cf = try_collect_into_array_erased(iter, &mut array); + match cf { + ControlFlow::Break(r) => FromResidual::from_residual(r), + ControlFlow::Continue(initialized) => { + debug_assert_eq!(initialized, N); + // SAFETY: because of our function contract, all the elements + // must have been initialized. + let output = unsafe { MaybeUninit::array_assume_init(array) }; + Try::from_output(output) + } + } } -// Infallible version of `try_collect_into_array_unchecked`. +/// Infallible version of [`try_collect_into_array_unchecked`]. unsafe fn collect_into_array_unchecked(iter: &mut I) -> [I::Item; N] where I: Iterator + TrustedLen, @@ -864,63 +873,48 @@ where } } -/// Pulls `N` items from `iter` and returns them as an array. If the iterator -/// yields fewer than `N` items, `Err` is returned containing an iterator over -/// the already yielded items. +/// Rather than *returning* the array, this fills in a passed-in buffer. +/// If any of the iterator elements short-circuit, it drops everything in the +/// buffer and return the error. Otherwise it returns the number of items +/// which were initialized in the buffer. /// -/// Since the iterator is passed as a mutable reference and this function calls -/// `next` at most `N` times, the iterator can still be used afterwards to -/// retrieve the remaining items. +/// (The caller is responsible for dropping those items on success, but not +/// doing that is just a leak, not UB, so this function is itself safe.) /// -/// If `iter.next()` panicks, all items already yielded by the iterator are -/// dropped. +/// This means less monomorphization, but more importantly it means that the +/// returned array doesn't need to be copied into the `Result`, since returning +/// the result seemed (2023-01) to cause in an extra `N + 1`-length `alloca` +/// even if it's always `unwrap_unchecked` later. #[inline] -fn try_collect_into_array( +fn try_collect_into_array_erased( iter: &mut I, -) -> Result> + buffer: &mut [MaybeUninit], +) -> ControlFlow where I: Iterator, I::Item: Try, - R: Residual<[T; N]>, { - if N == 0 { - // SAFETY: An empty array is always inhabited and has no validity invariants. - return Ok(Try::from_output(unsafe { mem::zeroed() })); - } - - let mut array = MaybeUninit::uninit_array::(); - let mut guard = Guard { array_mut: &mut array, initialized: 0 }; + let n = buffer.len(); + let mut guard = Guard { array_mut: buffer, initialized: 0 }; - for _ in 0..N { + for _ in 0..n { match iter.next() { Some(item_rslt) => { - let item = match item_rslt.branch() { - ControlFlow::Break(r) => { - return Ok(FromResidual::from_residual(r)); - } - ControlFlow::Continue(elem) => elem, - }; + let item = item_rslt.branch()?; // SAFETY: `guard.initialized` starts at 0, which means push can be called - // at most N times, which this loop does. + // at most `n` times, which this loop does. unsafe { guard.push_unchecked(item); } } - None => { - let alive = 0..guard.initialized; - mem::forget(guard); - // SAFETY: `array` was initialized with exactly `initialized` - // number of elements. - return Err(unsafe { IntoIter::new_unchecked(array, alive) }); - } + None => break, } } + let initialized = guard.initialized; mem::forget(guard); - // SAFETY: All elements of the array were populated in the loop above. - let output = unsafe { array.transpose().assume_init() }; - Ok(Try::from_output(output)) + ControlFlow::Continue(initialized) } /// Panic guard for incremental initialization of arrays. @@ -934,14 +928,14 @@ where /// /// To minimize indirection fields are still pub but callers should at least use /// `push_unchecked` to signal that something unsafe is going on. -pub(crate) struct Guard<'a, T, const N: usize> { +pub(crate) struct Guard<'a, T> { /// The array to be initialized. - pub array_mut: &'a mut [MaybeUninit; N], + pub array_mut: &'a mut [MaybeUninit], /// The number of items that have been initialized so far. pub initialized: usize, } -impl Guard<'_, T, N> { +impl Guard<'_, T> { /// Adds an item to the array and updates the initialized item counter. /// /// # Safety @@ -959,9 +953,9 @@ impl Guard<'_, T, N> { } } -impl Drop for Guard<'_, T, N> { +impl Drop for Guard<'_, T> { fn drop(&mut self) { - debug_assert!(self.initialized <= N); + debug_assert!(self.initialized <= self.array_mut.len()); // SAFETY: this slice will contain only initialized objects. unsafe { @@ -972,15 +966,33 @@ impl Drop for Guard<'_, T, N> { } } -/// Returns the next chunk of `N` items from the iterator or errors with an -/// iterator over the remainder. Used for `Iterator::next_chunk`. +/// Pulls `N` items from `iter` and returns them as an array. If the iterator +/// yields fewer than `N` items, `Err` is returned containing an iterator over +/// the already yielded items. +/// +/// Since the iterator is passed as a mutable reference and this function calls +/// `next` at most `N` times, the iterator can still be used afterwards to +/// retrieve the remaining items. +/// +/// If `iter.next()` panicks, all items already yielded by the iterator are +/// dropped. +/// +/// Used for [`Iterator::next_chunk`]. #[inline] -pub(crate) fn iter_next_chunk( - iter: &mut I, -) -> Result<[I::Item; N], IntoIter> -where - I: Iterator, -{ +pub(crate) fn iter_next_chunk( + iter: &mut impl Iterator, +) -> Result<[T; N], IntoIter> { let mut map = iter.map(NeverShortCircuit); - try_collect_into_array(&mut map).map(|NeverShortCircuit(arr)| arr) + let mut array = MaybeUninit::uninit_array::(); + let ControlFlow::Continue(initialized) = try_collect_into_array_erased(&mut map, &mut array); + if initialized == N { + // SAFETY: All elements of the array were populated. + let output = unsafe { MaybeUninit::array_assume_init(array) }; + Ok(output) + } else { + let alive = 0..initialized; + // SAFETY: `array` was initialized with exactly `initialized` + // number of elements. + return Err(unsafe { IntoIter::new_unchecked(array, alive) }); + } } diff --git a/tests/codegen/array-map.rs b/tests/codegen/array-map.rs index 37585371a32..1154659eea5 100644 --- a/tests/codegen/array-map.rs +++ b/tests/codegen/array-map.rs @@ -1,4 +1,4 @@ -// compile-flags: -C opt-level=3 -C target-cpu=x86-64-v3 -C llvm-args=-x86-asm-syntax=intel --emit=llvm-ir,asm +// compile-flags: -C opt-level=3 -C target-cpu=x86-64-v3 // no-system-llvm // only-x86_64 // ignore-debug (the extra assertions get in the way) @@ -40,8 +40,7 @@ pub fn short_integer_zip_map(x: [u32; 8], y: [u32; 8]) -> [u32; 8] { #[no_mangle] pub fn long_integer_map(x: [u32; 64]) -> [u32; 64] { // CHECK: start: - // CHECK-NEXT: alloca [{{64|65}} x i32] - // CHECK-NEXT: alloca [{{64|65}} x i32] + // CHECK-NEXT: alloca [64 x i32] // CHECK-NEXT: alloca %"core::mem::manually_drop::ManuallyDrop<[u32; 64]>" // CHECK-NOT: alloca x.map(|x| 2 * x + 1) -- cgit 1.4.1-3-g733a5 From 5bc328fdeff50b742a8136d0633924514d4d76b8 Mon Sep 17 00:00:00 2001 From: Scott McMurray Date: Fri, 3 Feb 2023 03:27:51 -0800 Subject: Allow canonicalizing the `array::map` loop in trusted cases --- library/core/src/array/drain.rs | 33 ++- library/core/src/array/mod.rs | 224 ++++++++++----------- library/core/src/iter/adapters/array_chunks.rs | 14 +- library/core/src/iter/adapters/cloned.rs | 15 +- library/core/src/iter/adapters/map.rs | 15 +- library/core/src/iter/adapters/zip.rs | 9 +- library/core/src/iter/mod.rs | 1 + library/core/src/iter/traits/mod.rs | 3 + library/core/src/iter/traits/unchecked_iterator.rs | 36 ++++ library/core/src/ops/try_trait.rs | 9 + library/core/src/slice/iter.rs | 4 +- library/core/src/slice/iter/macros.rs | 9 + library/core/tests/iter/traits/iterator.rs | 3 + tests/codegen/array-map.rs | 4 +- 14 files changed, 237 insertions(+), 142 deletions(-) create mode 100644 library/core/src/iter/traits/unchecked_iterator.rs (limited to 'library/core/src') diff --git a/library/core/src/array/drain.rs b/library/core/src/array/drain.rs index 5ca93d54f87..5fadf907b62 100644 --- a/library/core/src/array/drain.rs +++ b/library/core/src/array/drain.rs @@ -1,11 +1,21 @@ -use crate::iter::TrustedLen; +use crate::iter::{TrustedLen, UncheckedIterator}; use crate::mem::ManuallyDrop; use crate::ptr::drop_in_place; use crate::slice; -// INVARIANT: It's ok to drop the remainder of the inner iterator. -pub(crate) struct Drain<'a, T>(slice::IterMut<'a, T>); - +/// A situationally-optimized version of `array.into_iter().for_each(func)`. +/// +/// [`crate::array::IntoIter`]s are great when you need an owned iterator, but +/// storing the entire array *inside* the iterator like that can sometimes +/// pessimize code. Notable, it can be more bytes than you really want to move +/// around, and because the array accesses index into it SRoA has a harder time +/// optimizing away the type than it does iterators that just hold a couple pointers. +/// +/// Thus this function exists, which gives a way to get *moved* access to the +/// elements of an array using a small iterator -- no bigger than a slice iterator. +/// +/// The function-taking-a-closure structure makes it safe, as it keeps callers +/// from looking at already-dropped elements. pub(crate) fn drain_array_with( array: [T; N], func: impl for<'a> FnOnce(Drain<'a, T>) -> R, @@ -16,6 +26,11 @@ pub(crate) fn drain_array_with( func(drain) } +/// See [`drain_array_with`] -- this is `pub(crate)` only so it's allowed to be +/// mentioned in the signature of that method. (Otherwise it hits `E0446`.) +// INVARIANT: It's ok to drop the remainder of the inner iterator. +pub(crate) struct Drain<'a, T>(slice::IterMut<'a, T>); + impl Drop for Drain<'_, T> { fn drop(&mut self) { // SAFETY: By the type invariant, we're allowed to drop all these. @@ -49,3 +64,13 @@ impl ExactSizeIterator for Drain<'_, T> { // SAFETY: This is a 1:1 wrapper for a slice iterator, which is also `TrustedLen`. unsafe impl TrustedLen for Drain<'_, T> {} + +impl UncheckedIterator for Drain<'_, T> { + unsafe fn next_unchecked(&mut self) -> T { + // SAFETY: `Drain` is 1:1 with the inner iterator, so if the caller promised + // that there's an element left, the inner iterator has one too. + let p: *const T = unsafe { self.0.next_unchecked() }; + // SAFETY: The iterator was already advanced, so we won't drop this later. + unsafe { p.read() } + } +} diff --git a/library/core/src/array/mod.rs b/library/core/src/array/mod.rs index 45ec68e6e7a..ae9f6e70f43 100644 --- a/library/core/src/array/mod.rs +++ b/library/core/src/array/mod.rs @@ -10,7 +10,7 @@ use crate::convert::{Infallible, TryFrom}; use crate::error::Error; use crate::fmt; use crate::hash::{self, Hash}; -use crate::iter::TrustedLen; +use crate::iter::UncheckedIterator; use crate::mem::{self, MaybeUninit}; use crate::ops::{ ChangeOutputType, ControlFlow, FromResidual, Index, IndexMut, NeverShortCircuit, Residual, Try, @@ -55,16 +55,11 @@ pub use iter::IntoIter; /// ``` #[inline] #[stable(feature = "array_from_fn", since = "1.63.0")] -pub fn from_fn(mut cb: F) -> [T; N] +pub fn from_fn(cb: F) -> [T; N] where F: FnMut(usize) -> T, { - let mut idx = 0; - [(); N].map(|_| { - let res = cb(idx); - idx += 1; - res - }) + try_from_fn(NeverShortCircuit::wrap_mut_1(cb)).0 } /// Creates an array `[T; N]` where each fallible array element `T` is returned by the `cb` call. @@ -104,9 +99,14 @@ where R: Try, R::Residual: Residual<[R::Output; N]>, { - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { try_collect_into_array_unchecked(&mut (0..N).map(cb)) } + let mut array = MaybeUninit::uninit_array::(); + match try_from_fn_erased(&mut array, cb) { + ControlFlow::Break(r) => FromResidual::from_residual(r), + ControlFlow::Continue(()) => { + // SAFETY: All elements of the array were populated. + try { unsafe { MaybeUninit::array_assume_init(array) } } + } + } } /// Converts a reference to `T` into a reference to an array of length 1 (without copying). @@ -430,9 +430,7 @@ trait SpecArrayClone: Clone { impl SpecArrayClone for T { #[inline] default fn clone(array: &[T; N]) -> [T; N] { - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { collect_into_array_unchecked(&mut array.iter().cloned()) } + from_trusted_iterator(array.iter().cloned()) } } @@ -516,12 +514,7 @@ impl [T; N] { where F: FnMut(T) -> U, { - drain_array_with(self, |iter| { - let mut iter = iter.map(f); - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { collect_into_array_unchecked(&mut iter) } - }) + self.try_map(NeverShortCircuit::wrap_mut_1(f)).0 } /// A fallible function `f` applied to each element on array `self` in order to @@ -558,12 +551,7 @@ impl [T; N] { R: Try, R::Residual: Residual<[R::Output; N]>, { - drain_array_with(self, |iter| { - let mut iter = iter.map(f); - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { try_collect_into_array_unchecked(&mut iter) } - }) + drain_array_with(self, |iter| try_from_trusted_iterator(iter.map(f))) } /// 'Zips up' two arrays into a single array of pairs. @@ -585,12 +573,7 @@ impl [T; N] { #[unstable(feature = "array_zip", issue = "80094")] pub fn zip(self, rhs: [U; N]) -> [(T, U); N] { drain_array_with(self, |lhs| { - drain_array_with(rhs, |rhs| { - let mut iter = crate::iter::zip(lhs, rhs); - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { collect_into_array_unchecked(&mut iter) } - }) + drain_array_with(rhs, |rhs| from_trusted_iterator(crate::iter::zip(lhs, rhs))) }) } @@ -638,9 +621,7 @@ impl [T; N] { /// ``` #[unstable(feature = "array_methods", issue = "76118")] pub fn each_ref(&self) -> [&T; N] { - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { collect_into_array_unchecked(&mut self.iter()) } + from_trusted_iterator(self.iter()) } /// Borrows each element mutably and returns an array of mutable references @@ -660,9 +641,7 @@ impl [T; N] { /// ``` #[unstable(feature = "array_methods", issue = "76118")] pub fn each_mut(&mut self) -> [&mut T; N] { - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { collect_into_array_unchecked(&mut self.iter_mut()) } + from_trusted_iterator(self.iter_mut()) } /// Divides one array reference into two at an index. @@ -822,99 +801,71 @@ impl [T; N] { } } -/// Pulls `N` items from `iter` and returns them as an array. If the iterator -/// yields fewer than `N` items, this function exhibits undefined behavior. +/// Populate an array from the first `N` elements of `iter` /// -/// # Safety +/// # Panics /// -/// It is up to the caller to guarantee that `iter` yields at least `N` items. -/// Violating this condition causes undefined behavior. -unsafe fn try_collect_into_array_unchecked( - iter: &mut I, -) -> ChangeOutputType -where - // Note: `TrustedLen` here is somewhat of an experiment. This is just an - // internal function, so feel free to remove if this bound turns out to be a - // bad idea. In that case, remember to also remove the lower bound - // `debug_assert!` below! - I: Iterator + TrustedLen, - I::Item: Try, - R: Residual<[T; N]>, -{ - debug_assert!(N <= iter.size_hint().1.unwrap_or(usize::MAX)); - debug_assert!(N <= iter.size_hint().0); - - let mut array = MaybeUninit::uninit_array::(); - let cf = try_collect_into_array_erased(iter, &mut array); - match cf { - ControlFlow::Break(r) => FromResidual::from_residual(r), - ControlFlow::Continue(initialized) => { - debug_assert_eq!(initialized, N); - // SAFETY: because of our function contract, all the elements - // must have been initialized. - let output = unsafe { MaybeUninit::array_assume_init(array) }; - Try::from_output(output) - } - } +/// If the iterator doesn't actually have enough items. +/// +/// By depending on `TrustedLen`, however, we can do that check up-front (where +/// it easily optimizes away) so it doesn't impact the loop that fills the array. +#[inline] +fn from_trusted_iterator(iter: impl UncheckedIterator) -> [T; N] { + try_from_trusted_iterator(iter.map(NeverShortCircuit)).0 } -/// Infallible version of [`try_collect_into_array_unchecked`]. -unsafe fn collect_into_array_unchecked(iter: &mut I) -> [I::Item; N] +#[inline] +fn try_from_trusted_iterator( + iter: impl UncheckedIterator, +) -> ChangeOutputType where - I: Iterator + TrustedLen, + R: Try, + R::Residual: Residual<[T; N]>, { - let mut map = iter.map(NeverShortCircuit); - - // SAFETY: The same safety considerations w.r.t. the iterator length - // apply for `try_collect_into_array_unchecked` as for - // `collect_into_array_unchecked` - match unsafe { try_collect_into_array_unchecked(&mut map) } { - NeverShortCircuit(array) => array, + assert!(iter.size_hint().0 >= N); + fn next(mut iter: impl UncheckedIterator) -> impl FnMut(usize) -> T { + move |_| { + // SAFETY: We know that `from_fn` will call this at most N times, + // and we checked to ensure that we have at least that many items. + unsafe { iter.next_unchecked() } + } } + + try_from_fn(next(iter)) } -/// Rather than *returning* the array, this fills in a passed-in buffer. -/// If any of the iterator elements short-circuit, it drops everything in the -/// buffer and return the error. Otherwise it returns the number of items -/// which were initialized in the buffer. +/// Version of [`try_from_fn`] using a passed-in slice in order to avoid +/// needing to monomorphize for every array length. /// -/// (The caller is responsible for dropping those items on success, but not -/// doing that is just a leak, not UB, so this function is itself safe.) +/// This takes a generator rather than an iterator so that *at the type level* +/// it never needs to worry about running out of items. When combined with +/// an infallible `Try` type, that means the loop canonicalizes easily, allowing +/// it to optimize well. /// -/// This means less monomorphization, but more importantly it means that the -/// returned array doesn't need to be copied into the `Result`, since returning -/// the result seemed (2023-01) to cause in an extra `N + 1`-length `alloca` -/// even if it's always `unwrap_unchecked` later. +/// It would be *possible* to unify this and [`iter_next_chunk_erased`] into one +/// function that does the union of both things, but last time it was that way +/// it resulted in poor codegen from the "are there enough source items?" checks +/// not optimizing away. So if you give it a shot, make sure to watch what +/// happens in the codegen tests. #[inline] -fn try_collect_into_array_erased( - iter: &mut I, +fn try_from_fn_erased( buffer: &mut [MaybeUninit], -) -> ControlFlow + mut generator: impl FnMut(usize) -> R, +) -> ControlFlow where - I: Iterator, - I::Item: Try, + R: Try, { - let n = buffer.len(); let mut guard = Guard { array_mut: buffer, initialized: 0 }; - for _ in 0..n { - match iter.next() { - Some(item_rslt) => { - let item = item_rslt.branch()?; + while guard.initialized < guard.array_mut.len() { + let item = generator(guard.initialized).branch()?; - // SAFETY: `guard.initialized` starts at 0, which means push can be called - // at most `n` times, which this loop does. - unsafe { - guard.push_unchecked(item); - } - } - None => break, - } + // SAFETY: The loop condition ensures we have space to push the item + unsafe { guard.push_unchecked(item) }; } - let initialized = guard.initialized; mem::forget(guard); - ControlFlow::Continue(initialized) + ControlFlow::Continue(()) } /// Panic guard for incremental initialization of arrays. @@ -928,7 +879,7 @@ where /// /// To minimize indirection fields are still pub but callers should at least use /// `push_unchecked` to signal that something unsafe is going on. -pub(crate) struct Guard<'a, T> { +struct Guard<'a, T> { /// The array to be initialized. pub array_mut: &'a mut [MaybeUninit], /// The number of items that have been initialized so far. @@ -960,7 +911,7 @@ impl Drop for Guard<'_, T> { // SAFETY: this slice will contain only initialized objects. unsafe { crate::ptr::drop_in_place(MaybeUninit::slice_assume_init_mut( - &mut self.array_mut.get_unchecked_mut(..self.initialized), + self.array_mut.get_unchecked_mut(..self.initialized), )); } } @@ -982,17 +933,44 @@ impl Drop for Guard<'_, T> { pub(crate) fn iter_next_chunk( iter: &mut impl Iterator, ) -> Result<[T; N], IntoIter> { - let mut map = iter.map(NeverShortCircuit); let mut array = MaybeUninit::uninit_array::(); - let ControlFlow::Continue(initialized) = try_collect_into_array_erased(&mut map, &mut array); - if initialized == N { - // SAFETY: All elements of the array were populated. - let output = unsafe { MaybeUninit::array_assume_init(array) }; - Ok(output) - } else { - let alive = 0..initialized; - // SAFETY: `array` was initialized with exactly `initialized` - // number of elements. - return Err(unsafe { IntoIter::new_unchecked(array, alive) }); + let r = iter_next_chunk_erased(&mut array, iter); + match r { + Ok(()) => { + // SAFETY: All elements of `array` were populated. + Ok(unsafe { MaybeUninit::array_assume_init(array) }) + } + Err(initialized) => { + // SAFETY: Only the first `initialized` elements were populated + Err(unsafe { IntoIter::new_unchecked(array, 0..initialized) }) + } + } +} + +/// Version of [`iter_next_chunk`] using a passed-in slice in order to avoid +/// needing to monomorphize for every array length. +/// +/// Unfortunately this loop has two exit conditions, the buffer filling up +/// or the iterator running out of items, making it tend to optimize poorly. +#[inline] +fn iter_next_chunk_erased( + buffer: &mut [MaybeUninit], + iter: &mut impl Iterator, +) -> Result<(), usize> { + let mut guard = Guard { array_mut: buffer, initialized: 0 }; + while guard.initialized < guard.array_mut.len() { + let Some(item) = iter.next() else { + // Unlike `try_from_fn_erased`, we want to keep the partial results, + // so we need to defuse the guard instead of using `?`. + let initialized = guard.initialized; + mem::forget(guard); + return Err(initialized) + }; + + // SAFETY: The loop condition ensures we have space to push the item + unsafe { guard.push_unchecked(item) }; } + + mem::forget(guard); + Ok(()) } diff --git a/library/core/src/iter/adapters/array_chunks.rs b/library/core/src/iter/adapters/array_chunks.rs index af786609757..13719c727e9 100644 --- a/library/core/src/iter/adapters/array_chunks.rs +++ b/library/core/src/iter/adapters/array_chunks.rs @@ -1,6 +1,5 @@ use crate::array; use crate::iter::{ByRefSized, FusedIterator, Iterator, TrustedRandomAccessNoCoerce}; -use crate::mem::{self, MaybeUninit}; use crate::ops::{ControlFlow, NeverShortCircuit, Try}; /// An iterator over `N` elements of the iterator at a time. @@ -212,19 +211,14 @@ where let mut i = 0; // Use a while loop because (0..len).step_by(N) doesn't optimize well. while inner_len - i >= N { - let mut chunk = MaybeUninit::uninit_array(); - let mut guard = array::Guard { array_mut: &mut chunk, initialized: 0 }; - while guard.initialized < N { + let chunk = crate::array::from_fn(|local| { // SAFETY: The method consumes the iterator and the loop condition ensures that // all accesses are in bounds and only happen once. unsafe { - let idx = i + guard.initialized; - guard.push_unchecked(self.iter.__iterator_get_unchecked(idx)); + let idx = i + local; + self.iter.__iterator_get_unchecked(idx) } - } - mem::forget(guard); - // SAFETY: The loop above initialized all elements - let chunk = unsafe { MaybeUninit::array_assume_init(chunk) }; + }); accum = f(accum, chunk); i += N; } diff --git a/library/core/src/iter/adapters/cloned.rs b/library/core/src/iter/adapters/cloned.rs index aba24a79dcf..914ff86c1a9 100644 --- a/library/core/src/iter/adapters/cloned.rs +++ b/library/core/src/iter/adapters/cloned.rs @@ -1,7 +1,7 @@ use crate::iter::adapters::{ zip::try_get_unchecked, TrustedRandomAccess, TrustedRandomAccessNoCoerce, }; -use crate::iter::{FusedIterator, TrustedLen}; +use crate::iter::{FusedIterator, TrustedLen, UncheckedIterator}; use crate::ops::Try; /// An iterator that clones the elements of an underlying iterator. @@ -140,3 +140,16 @@ where T: Clone, { } + +impl<'a, I, T: 'a> UncheckedIterator for Cloned +where + I: UncheckedIterator, + T: Clone, +{ + unsafe fn next_unchecked(&mut self) -> T { + // SAFETY: `Cloned` is 1:1 with the inner iterator, so if the caller promised + // that there's an element left, the inner iterator has one too. + let item = unsafe { self.it.next_unchecked() }; + item.clone() + } +} diff --git a/library/core/src/iter/adapters/map.rs b/library/core/src/iter/adapters/map.rs index 9e25dbe462c..31d02a4da6e 100644 --- a/library/core/src/iter/adapters/map.rs +++ b/library/core/src/iter/adapters/map.rs @@ -2,7 +2,7 @@ use crate::fmt; use crate::iter::adapters::{ zip::try_get_unchecked, SourceIter, TrustedRandomAccess, TrustedRandomAccessNoCoerce, }; -use crate::iter::{FusedIterator, InPlaceIterable, TrustedLen}; +use crate::iter::{FusedIterator, InPlaceIterable, TrustedLen, UncheckedIterator}; use crate::ops::Try; /// An iterator that maps the values of `iter` with `f`. @@ -187,6 +187,19 @@ where { } +impl UncheckedIterator for Map +where + I: UncheckedIterator, + F: FnMut(I::Item) -> B, +{ + unsafe fn next_unchecked(&mut self) -> B { + // SAFETY: `Map` is 1:1 with the inner iterator, so if the caller promised + // that there's an element left, the inner iterator has one too. + let item = unsafe { self.iter.next_unchecked() }; + (self.f)(item) + } +} + #[doc(hidden)] #[unstable(feature = "trusted_random_access", issue = "none")] unsafe impl TrustedRandomAccess for Map where I: TrustedRandomAccess {} diff --git a/library/core/src/iter/adapters/zip.rs b/library/core/src/iter/adapters/zip.rs index 8153c8cfef1..b6b0c90cb7d 100644 --- a/library/core/src/iter/adapters/zip.rs +++ b/library/core/src/iter/adapters/zip.rs @@ -1,7 +1,7 @@ use crate::cmp; use crate::fmt::{self, Debug}; use crate::iter::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator}; -use crate::iter::{InPlaceIterable, SourceIter, TrustedLen}; +use crate::iter::{InPlaceIterable, SourceIter, TrustedLen, UncheckedIterator}; /// An iterator that iterates two other iterators simultaneously. /// @@ -417,6 +417,13 @@ where { } +impl UncheckedIterator for Zip +where + A: UncheckedIterator, + B: UncheckedIterator, +{ +} + // Arbitrarily selects the left side of the zip iteration as extractable "source" // it would require negative trait bounds to be able to try both #[unstable(issue = "none", feature = "inplace_iteration")] diff --git a/library/core/src/iter/mod.rs b/library/core/src/iter/mod.rs index 00f57fbcc61..156b925de77 100644 --- a/library/core/src/iter/mod.rs +++ b/library/core/src/iter/mod.rs @@ -450,6 +450,7 @@ pub use self::adapters::{ pub use self::adapters::{Intersperse, IntersperseWith}; pub(crate) use self::adapters::try_process; +pub(crate) use self::traits::UncheckedIterator; mod adapters; mod range; diff --git a/library/core/src/iter/traits/mod.rs b/library/core/src/iter/traits/mod.rs index ed0fb634dbf..41ea29e6a84 100644 --- a/library/core/src/iter/traits/mod.rs +++ b/library/core/src/iter/traits/mod.rs @@ -4,6 +4,7 @@ mod double_ended; mod exact_size; mod iterator; mod marker; +mod unchecked_iterator; #[stable(feature = "rust1", since = "1.0.0")] pub use self::{ @@ -19,3 +20,5 @@ pub use self::{ pub use self::marker::InPlaceIterable; #[unstable(feature = "trusted_step", issue = "85731")] pub use self::marker::TrustedStep; + +pub(crate) use self::unchecked_iterator::UncheckedIterator; diff --git a/library/core/src/iter/traits/unchecked_iterator.rs b/library/core/src/iter/traits/unchecked_iterator.rs new file mode 100644 index 00000000000..ae4bfcad4e6 --- /dev/null +++ b/library/core/src/iter/traits/unchecked_iterator.rs @@ -0,0 +1,36 @@ +use crate::iter::TrustedLen; + +/// [`TrustedLen`] cannot have methods, so this allows augmenting it. +/// +/// It currently requires `TrustedLen` because it's unclear whether it's +/// reasonably possible to depend on the `size_hint` of anything else. +pub(crate) trait UncheckedIterator: TrustedLen { + /// Gets the next item from a non-empty iterator. + /// + /// Because there's always a value to return, that means it can return + /// the `Item` type directly, without wrapping it in an `Option`. + /// + /// # Safety + /// + /// This can only be called if `size_hint().0 != 0`, guaranteeing that + /// there's at least one item available. + /// + /// Otherwise (aka when `size_hint().1 == Some(0)`), this is UB. + /// + /// # Note to Implementers + /// + /// This has a default implementation using [`Option::unwrap_unchecked`]. + /// That's probably sufficient if your `next` *always* returns `Some`, + /// such as for infinite iterators. In more complicated situations, however, + /// sometimes there can still be `insertvalue`/`assume`/`extractvalue` + /// instructions remaining in the IR from the `Option` handling, at which + /// point you might want to implement this manually instead. + #[unstable(feature = "trusted_len_next_unchecked", issue = "37572")] + #[inline] + unsafe fn next_unchecked(&mut self) -> Self::Item { + let opt = self.next(); + // SAFETY: The caller promised that we're not empty, and + // `Self: TrustedLen` so we can actually trust the `size_hint`. + unsafe { opt.unwrap_unchecked() } + } +} diff --git a/library/core/src/ops/try_trait.rs b/library/core/src/ops/try_trait.rs index 9108fc63045..86aa1e4fd20 100644 --- a/library/core/src/ops/try_trait.rs +++ b/library/core/src/ops/try_trait.rs @@ -379,6 +379,15 @@ pub(crate) type ChangeOutputType = <::Residual as Residual>:: pub(crate) struct NeverShortCircuit(pub T); impl NeverShortCircuit { + /// Wraps a unary function to produce one that wraps the output into a `NeverShortCircuit`. + /// + /// This is useful for implementing infallible functions in terms of the `try_` ones, + /// without accidentally capturing extra generic parameters in a closure. + #[inline] + pub fn wrap_mut_1(mut f: impl FnMut(A) -> T) -> impl FnMut(A) -> NeverShortCircuit { + move |a| NeverShortCircuit(f(a)) + } + #[inline] pub fn wrap_mut_2( mut f: impl ~const FnMut(A, B) -> T, diff --git a/library/core/src/slice/iter.rs b/library/core/src/slice/iter.rs index 90ab43d1289..c4317799bcc 100644 --- a/library/core/src/slice/iter.rs +++ b/library/core/src/slice/iter.rs @@ -7,7 +7,9 @@ use crate::cmp; use crate::cmp::Ordering; use crate::fmt; use crate::intrinsics::assume; -use crate::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce}; +use crate::iter::{ + FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce, UncheckedIterator, +}; use crate::marker::{PhantomData, Send, Sized, Sync}; use crate::mem::{self, SizedTypeProperties}; use crate::num::NonZeroUsize; diff --git a/library/core/src/slice/iter/macros.rs b/library/core/src/slice/iter/macros.rs index 0fd57b197aa..89b92a7d597 100644 --- a/library/core/src/slice/iter/macros.rs +++ b/library/core/src/slice/iter/macros.rs @@ -384,6 +384,15 @@ macro_rules! iterator { #[unstable(feature = "trusted_len", issue = "37572")] unsafe impl TrustedLen for $name<'_, T> {} + + impl<'a, T> UncheckedIterator for $name<'a, T> { + unsafe fn next_unchecked(&mut self) -> $elem { + // SAFETY: The caller promised there's at least one more item. + unsafe { + next_unchecked!(self) + } + } + } } } diff --git a/library/core/tests/iter/traits/iterator.rs b/library/core/tests/iter/traits/iterator.rs index 37345c1d381..62566a9502d 100644 --- a/library/core/tests/iter/traits/iterator.rs +++ b/library/core/tests/iter/traits/iterator.rs @@ -582,6 +582,9 @@ fn test_next_chunk() { assert_eq!(it.next_chunk().unwrap(), []); assert_eq!(it.next_chunk().unwrap(), [4, 5, 6, 7, 8, 9]); assert_eq!(it.next_chunk::<4>().unwrap_err().as_slice(), &[10, 11]); + + let mut it = std::iter::repeat_with(|| panic!()); + assert_eq!(it.next_chunk::<0>().unwrap(), []); } // just tests by whether or not this compiles diff --git a/tests/codegen/array-map.rs b/tests/codegen/array-map.rs index 1154659eea5..9298e89e397 100644 --- a/tests/codegen/array-map.rs +++ b/tests/codegen/array-map.rs @@ -43,5 +43,7 @@ pub fn long_integer_map(x: [u32; 64]) -> [u32; 64] { // CHECK-NEXT: alloca [64 x i32] // CHECK-NEXT: alloca %"core::mem::manually_drop::ManuallyDrop<[u32; 64]>" // CHECK-NOT: alloca - x.map(|x| 2 * x + 1) + // CHECK: mul <{{[0-9]+}} x i32> + // CHECK: add <{{[0-9]+}} x i32> + x.map(|x| 13 * x + 7) } -- cgit 1.4.1-3-g733a5 From 1af9b4f347c1ca725e43444e0068b5e520dde7e2 Mon Sep 17 00:00:00 2001 From: Jubilee <46493976+workingjubilee@users.noreply.github.com> Date: Thu, 9 Feb 2023 23:56:20 -0800 Subject: Clarify `new_size` for realloc means bytes --- library/core/src/alloc/global.rs | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) (limited to 'library/core/src') diff --git a/library/core/src/alloc/global.rs b/library/core/src/alloc/global.rs index 1d80b8bf9ec..18da70451f2 100644 --- a/library/core/src/alloc/global.rs +++ b/library/core/src/alloc/global.rs @@ -203,7 +203,7 @@ pub unsafe trait GlobalAlloc { ptr } - /// Shrink or grow a block of memory to the given `new_size`. + /// Shrink or grow a block of memory to the given `new_size` in bytes. /// The block is described by the given `ptr` pointer and `layout`. /// /// If this returns a non-null pointer, then ownership of the memory block @@ -211,10 +211,11 @@ pub unsafe trait GlobalAlloc { /// Any access to the old `ptr` is Undefined Behavior, even if the /// allocation remained in-place. The newly returned pointer is the only valid pointer /// for accessing this memory now. + /// /// The new memory block is allocated with `layout`, - /// but with the `size` updated to `new_size`. This new layout must be - /// used when deallocating the new memory block with `dealloc`. The range - /// `0..min(layout.size(), new_size)` of the new memory block is + /// but with the `size` updated to `new_size` in bytes. + /// This new layout must be used when deallocating the new memory block with `dealloc`. + /// The range `0..min(layout.size(), new_size)` of the new memory block is /// guaranteed to have the same values as the original block. /// /// If this method returns null, then ownership of the memory -- cgit 1.4.1-3-g733a5 From 7e072199a6e650698c2f5f1e1053b20d48be43d3 Mon Sep 17 00:00:00 2001 From: Lukas Bergdoll Date: Fri, 10 Feb 2023 18:00:31 +0100 Subject: Speedup heapsort by 1.5x by making it branchless `slice::sort_unstable` will fall back to heapsort if it repeatedly fails to find a good pivot. By making the core child update code branchless it is much faster. On Zen3 sorting 10k `u64` and forcing the sort to pick heapsort, results in: 455us -> 278us --- library/core/src/slice/sort.rs | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) (limited to 'library/core/src') diff --git a/library/core/src/slice/sort.rs b/library/core/src/slice/sort.rs index 2181f9a8118..990540f55f5 100644 --- a/library/core/src/slice/sort.rs +++ b/library/core/src/slice/sort.rs @@ -198,9 +198,7 @@ where } // Choose the greater child. - if child + 1 < v.len() && is_less(&v[child], &v[child + 1]) { - child += 1; - } + child += (child + 1 < v.len() && is_less(&v[child], &v[child + 1])) as usize; // Stop if the invariant holds at `node`. if !is_less(&v[node], &v[child]) { -- cgit 1.4.1-3-g733a5 From 404e9c5e3ad75057b6bbb3bcd44fe60480e50294 Mon Sep 17 00:00:00 2001 From: Scott McMurray Date: Fri, 10 Feb 2023 12:50:17 -0800 Subject: Have a function for the `log(0)` panic, rather than copy-pasting the string constant --- library/core/src/num/int_log10.rs | 8 ++++++++ library/core/src/num/int_macros.rs | 21 +++++++++++++++------ library/core/src/num/uint_macros.rs | 21 +++++++++++++++------ 3 files changed, 38 insertions(+), 12 deletions(-) (limited to 'library/core/src') diff --git a/library/core/src/num/int_log10.rs b/library/core/src/num/int_log10.rs index 80472528f6c..0ce31b40a38 100644 --- a/library/core/src/num/int_log10.rs +++ b/library/core/src/num/int_log10.rs @@ -138,3 +138,11 @@ pub const fn i64(val: i64) -> u32 { pub const fn i128(val: i128) -> u32 { u128(val as u128) } + +/// Instantiate this panic logic once, rather than for all the ilog methods +/// on every single primitive type. +#[cold] +#[track_caller] +pub const fn panic_for_nonpositive_argument() -> ! { + panic!("argument of integer logarithm must be positive") +} diff --git a/library/core/src/num/int_macros.rs b/library/core/src/num/int_macros.rs index b59f28193e2..479f8ffb78d 100644 --- a/library/core/src/num/int_macros.rs +++ b/library/core/src/num/int_macros.rs @@ -2331,14 +2331,17 @@ macro_rules! int_impl { /// ``` #[stable(feature = "int_log", since = "1.67.0")] #[rustc_const_stable(feature = "int_log", since = "1.67.0")] - #[rustc_allow_const_fn_unstable(const_option)] #[must_use = "this returns the result of the operation, \ without modifying the original"] #[inline] #[track_caller] pub const fn ilog(self, base: Self) -> u32 { assert!(base >= 2, "base of integer logarithm must be at least 2"); - self.checked_ilog(base).expect("argument of integer logarithm must be positive") + if let Some(log) = self.checked_ilog(base) { + log + } else { + int_log10::panic_for_nonpositive_argument() + } } /// Returns the base 2 logarithm of the number, rounded down. @@ -2354,13 +2357,16 @@ macro_rules! int_impl { /// ``` #[stable(feature = "int_log", since = "1.67.0")] #[rustc_const_stable(feature = "int_log", since = "1.67.0")] - #[rustc_allow_const_fn_unstable(const_option)] #[must_use = "this returns the result of the operation, \ without modifying the original"] #[inline] #[track_caller] pub const fn ilog2(self) -> u32 { - self.checked_ilog2().expect("argument of integer logarithm must be positive") + if let Some(log) = self.checked_ilog2() { + log + } else { + int_log10::panic_for_nonpositive_argument() + } } /// Returns the base 10 logarithm of the number, rounded down. @@ -2376,13 +2382,16 @@ macro_rules! int_impl { /// ``` #[stable(feature = "int_log", since = "1.67.0")] #[rustc_const_stable(feature = "int_log", since = "1.67.0")] - #[rustc_allow_const_fn_unstable(const_option)] #[must_use = "this returns the result of the operation, \ without modifying the original"] #[inline] #[track_caller] pub const fn ilog10(self) -> u32 { - self.checked_ilog10().expect("argument of integer logarithm must be positive") + if let Some(log) = self.checked_ilog10() { + log + } else { + int_log10::panic_for_nonpositive_argument() + } } /// Returns the logarithm of the number with respect to an arbitrary base, diff --git a/library/core/src/num/uint_macros.rs b/library/core/src/num/uint_macros.rs index 1c97c468628..411ea68674d 100644 --- a/library/core/src/num/uint_macros.rs +++ b/library/core/src/num/uint_macros.rs @@ -705,14 +705,17 @@ macro_rules! uint_impl { /// ``` #[stable(feature = "int_log", since = "1.67.0")] #[rustc_const_stable(feature = "int_log", since = "1.67.0")] - #[rustc_allow_const_fn_unstable(const_option)] #[must_use = "this returns the result of the operation, \ without modifying the original"] #[inline] #[track_caller] pub const fn ilog(self, base: Self) -> u32 { assert!(base >= 2, "base of integer logarithm must be at least 2"); - self.checked_ilog(base).expect("argument of integer logarithm must be positive") + if let Some(log) = self.checked_ilog(base) { + log + } else { + int_log10::panic_for_nonpositive_argument() + } } /// Returns the base 2 logarithm of the number, rounded down. @@ -728,13 +731,16 @@ macro_rules! uint_impl { /// ``` #[stable(feature = "int_log", since = "1.67.0")] #[rustc_const_stable(feature = "int_log", since = "1.67.0")] - #[rustc_allow_const_fn_unstable(const_option)] #[must_use = "this returns the result of the operation, \ without modifying the original"] #[inline] #[track_caller] pub const fn ilog2(self) -> u32 { - self.checked_ilog2().expect("argument of integer logarithm must be positive") + if let Some(log) = self.checked_ilog2() { + log + } else { + int_log10::panic_for_nonpositive_argument() + } } /// Returns the base 10 logarithm of the number, rounded down. @@ -750,13 +756,16 @@ macro_rules! uint_impl { /// ``` #[stable(feature = "int_log", since = "1.67.0")] #[rustc_const_stable(feature = "int_log", since = "1.67.0")] - #[rustc_allow_const_fn_unstable(const_option)] #[must_use = "this returns the result of the operation, \ without modifying the original"] #[inline] #[track_caller] pub const fn ilog10(self) -> u32 { - self.checked_ilog10().expect("argument of integer logarithm must be positive") + if let Some(log) = self.checked_ilog10() { + log + } else { + int_log10::panic_for_nonpositive_argument() + } } /// Returns the logarithm of the number with respect to an arbitrary base, -- cgit 1.4.1-3-g733a5 From ee0376c368c50c7dadc84801e88cfdbf250b92a4 Mon Sep 17 00:00:00 2001 From: Lukas Bergdoll Date: Sat, 11 Feb 2023 09:32:52 +0100 Subject: Split branches in heapsort child selection This allows even better code-gen, cmp + adc. While also more clearly communicating the intent. --- library/core/src/slice/sort.rs | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'library/core/src') diff --git a/library/core/src/slice/sort.rs b/library/core/src/slice/sort.rs index 990540f55f5..8f02a446670 100644 --- a/library/core/src/slice/sort.rs +++ b/library/core/src/slice/sort.rs @@ -198,7 +198,12 @@ where } // Choose the greater child. - child += (child + 1 < v.len() && is_less(&v[child], &v[child + 1])) as usize; + if child + 1 < v.len() { + // We need a branch to be sure not to out-of-bounds index, + // but it's highly predictable. The comparison, however, + // is better done branchless, especially for primitives. + child += is_less(&v[child], &v[child + 1]) as usize; + } // Stop if the invariant holds at `node`. if !is_less(&v[node], &v[child]) { -- cgit 1.4.1-3-g733a5 From cca82fd997a8c16a1a790846ceab8717f16cc238 Mon Sep 17 00:00:00 2001 From: Michael Goulet Date: Sun, 12 Feb 2023 01:09:09 +0000 Subject: Document PointerLike --- library/core/src/marker.rs | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'library/core/src') diff --git a/library/core/src/marker.rs b/library/core/src/marker.rs index e11bca5962a..07a7d45c7eb 100644 --- a/library/core/src/marker.rs +++ b/library/core/src/marker.rs @@ -871,7 +871,10 @@ pub trait Destruct {} #[rustc_deny_explicit_impl] pub trait Tuple {} -/// A marker for things +/// A marker for pointer-like types. +/// +/// All types that have the same size and alignment as a `usize` or +/// `*const ()` automatically implement this trait. #[unstable(feature = "pointer_like_trait", issue = "none")] #[cfg_attr(bootstrap, lang = "pointer_sized")] #[cfg_attr(not(bootstrap), lang = "pointer_like")] -- cgit 1.4.1-3-g733a5 From 79d2430e9961c9b38aa8366f028fbcbcf98e74a5 Mon Sep 17 00:00:00 2001 From: Scott McMurray Date: Sun, 12 Feb 2023 10:37:25 -0800 Subject: Add a doc note about why `Chain` is not `ExactSizeIterator` --- library/core/src/iter/traits/exact_size.rs | 10 ++++++++++ library/core/src/iter/traits/marker.rs | 11 +++++++++++ 2 files changed, 21 insertions(+) (limited to 'library/core/src') diff --git a/library/core/src/iter/traits/exact_size.rs b/library/core/src/iter/traits/exact_size.rs index 1757e37ec0e..908830d8a95 100644 --- a/library/core/src/iter/traits/exact_size.rs +++ b/library/core/src/iter/traits/exact_size.rs @@ -21,6 +21,16 @@ /// /// [`len`]: ExactSizeIterator::len /// +/// # When *shouldn't* an adapter be `ExactSizeIterator`? +/// +/// If an adapter makes an iterator *longer*, then it's usually incorrect for +/// that adapter to implement `ExactSizeIterator`. The inner exact-sized +/// iterator might already be `usize::MAX`-long, and thus the length of the +/// longer adapted iterator would no longer be exactly representable in `usize`. +/// +/// This is why [`Chain`](crate::iter::Chain) isn't `ExactSizeIterator`, +/// even when `A` and `B` are both `ExactSizeIterator`. +/// /// # Examples /// /// Basic usage: diff --git a/library/core/src/iter/traits/marker.rs b/library/core/src/iter/traits/marker.rs index da753745740..af02848233d 100644 --- a/library/core/src/iter/traits/marker.rs +++ b/library/core/src/iter/traits/marker.rs @@ -31,6 +31,17 @@ impl FusedIterator for &mut I {} /// The iterator must produce exactly the number of elements it reported /// or diverge before reaching the end. /// +/// # When *shouldn't* an adapter be `TrustedLen`? +/// +/// If an adapter makes an iterator *shorter* by a given amount, then it's +/// usually incorrect for that adapter to implement `TrustedLen`. The inner +/// iterator might return more than `usize::MAX` items, but there's no way to +/// know what `k` elements less than that will be, since the `size_hint` from +/// the inner iterator has already saturated and lost that information. +/// +/// This is why [`Skip`](crate::iter::Skip) isn't `TrustedLen`, even when +/// `I` implements `TrustedLen`. +/// /// # Safety /// /// This trait must only be implemented when the contract is upheld. Consumers -- cgit 1.4.1-3-g733a5 From ef6a59b7a921af918ea5e87ecd9d736899c9161b Mon Sep 17 00:00:00 2001 From: Tshepang Mbambo Date: Tue, 14 Feb 2023 01:43:41 +0200 Subject: "Basic usage" is redundant for there is just one example --- library/core/src/ptr/const_ptr.rs | 20 -------------------- library/core/src/ptr/mut_ptr.rs | 22 ---------------------- 2 files changed, 42 deletions(-) (limited to 'library/core/src') diff --git a/library/core/src/ptr/const_ptr.rs b/library/core/src/ptr/const_ptr.rs index 16eb726f6f6..57e2ffe5d20 100644 --- a/library/core/src/ptr/const_ptr.rs +++ b/library/core/src/ptr/const_ptr.rs @@ -23,8 +23,6 @@ impl *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let s: &str = "Follow the rabbit"; /// let ptr: *const u8 = s.as_ptr(); @@ -323,8 +321,6 @@ impl *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let ptr: *const u8 = &10u8 as *const u8; /// @@ -384,8 +380,6 @@ impl *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// #![feature(ptr_as_uninit)] /// @@ -449,8 +443,6 @@ impl *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let s: &str = "123"; /// let ptr: *const u8 = s.as_ptr(); @@ -526,8 +518,6 @@ impl *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// // Iterate using a raw pointer in increments of two elements /// let data = [1u8, 2, 3, 4, 5]; @@ -908,8 +898,6 @@ impl *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let s: &str = "123"; /// let ptr: *const u8 = s.as_ptr(); @@ -993,8 +981,6 @@ impl *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let s: &str = "123"; /// @@ -1072,8 +1058,6 @@ impl *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// // Iterate using a raw pointer in increments of two elements /// let data = [1u8, 2, 3, 4, 5]; @@ -1152,8 +1136,6 @@ impl *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// // Iterate using a raw pointer in increments of two elements (backwards) /// let data = [1u8, 2, 3, 4, 5]; @@ -1359,7 +1341,6 @@ impl *const T { /// /// # Examples /// - /// Basic usage: /// ``` /// #![feature(pointer_is_aligned)] /// #![feature(pointer_byte_offsets)] @@ -1482,7 +1463,6 @@ impl *const T { /// /// # Examples /// - /// Basic usage: /// ``` /// #![feature(pointer_is_aligned)] /// #![feature(pointer_byte_offsets)] diff --git a/library/core/src/ptr/mut_ptr.rs b/library/core/src/ptr/mut_ptr.rs index 0a2f63e3ec6..422d0f2b8f0 100644 --- a/library/core/src/ptr/mut_ptr.rs +++ b/library/core/src/ptr/mut_ptr.rs @@ -22,8 +22,6 @@ impl *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let mut s = [1, 2, 3]; /// let ptr: *mut u32 = s.as_mut_ptr(); @@ -332,8 +330,6 @@ impl *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let ptr: *mut u8 = &mut 10u8 as *mut u8; /// @@ -396,8 +392,6 @@ impl *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// #![feature(ptr_as_uninit)] /// @@ -461,8 +455,6 @@ impl *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let mut s = [1, 2, 3]; /// let ptr: *mut u32 = s.as_mut_ptr(); @@ -539,8 +531,6 @@ impl *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// // Iterate using a raw pointer in increments of two elements /// let mut data = [1u8, 2, 3, 4, 5]; @@ -660,8 +650,6 @@ impl *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let mut s = [1, 2, 3]; /// let ptr: *mut u32 = s.as_mut_ptr(); @@ -1010,8 +998,6 @@ impl *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let s: &str = "123"; /// let ptr: *const u8 = s.as_ptr(); @@ -1095,8 +1081,6 @@ impl *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let s: &str = "123"; /// @@ -1174,8 +1158,6 @@ impl *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// // Iterate using a raw pointer in increments of two elements /// let data = [1u8, 2, 3, 4, 5]; @@ -1254,8 +1236,6 @@ impl *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// // Iterate using a raw pointer in increments of two elements (backwards) /// let data = [1u8, 2, 3, 4, 5]; @@ -1627,7 +1607,6 @@ impl *mut T { /// /// # Examples /// - /// Basic usage: /// ``` /// #![feature(pointer_is_aligned)] /// #![feature(pointer_byte_offsets)] @@ -1752,7 +1731,6 @@ impl *mut T { /// /// # Examples /// - /// Basic usage: /// ``` /// #![feature(pointer_is_aligned)] /// #![feature(pointer_byte_offsets)] -- cgit 1.4.1-3-g733a5 From 646e6672000f17154f38f03b0a6948727510d663 Mon Sep 17 00:00:00 2001 From: lcnr Date: Tue, 14 Feb 2023 10:17:19 +0100 Subject: add a `#[rustc_coinductive]` attribute --- compiler/rustc_feature/src/builtin_attrs.rs | 7 +++++-- compiler/rustc_hir_analysis/src/collect.rs | 12 ++++++----- compiler/rustc_middle/src/ty/mod.rs | 10 ++++++---- compiler/rustc_middle/src/ty/trait_def.rs | 31 +++++++++-------------------- compiler/rustc_passes/src/check_attr.rs | 15 ++++++++++++++ compiler/rustc_span/src/symbol.rs | 1 + library/core/src/marker.rs | 1 + 7 files changed, 44 insertions(+), 33 deletions(-) (limited to 'library/core/src') diff --git a/compiler/rustc_feature/src/builtin_attrs.rs b/compiler/rustc_feature/src/builtin_attrs.rs index af56a0b2459..9b1eee32890 100644 --- a/compiler/rustc_feature/src/builtin_attrs.rs +++ b/compiler/rustc_feature/src/builtin_attrs.rs @@ -682,14 +682,17 @@ pub const BUILTIN_ATTRIBUTES: &[BuiltinAttribute] = &[ "language items are subject to change", ), rustc_attr!( - rustc_pass_by_value, Normal, - template!(Word), ErrorFollowing, + rustc_pass_by_value, Normal, template!(Word), ErrorFollowing, "#[rustc_pass_by_value] is used to mark types that must be passed by value instead of reference." ), rustc_attr!( rustc_coherence_is_core, AttributeType::CrateLevel, template!(Word), ErrorFollowing, @only_local: true, "#![rustc_coherence_is_core] allows inherent methods on builtin types, only intended to be used in `core`." ), + rustc_attr!( + rustc_coinductive, AttributeType::Normal, template!(Word), WarnFollowing, @only_local: true, + "#![rustc_coinductive] changes a trait to be coinductive, allowing cycles in the trait solver." + ), rustc_attr!( rustc_allow_incoherent_impl, AttributeType::Normal, template!(Word), ErrorFollowing, @only_local: true, "#[rustc_allow_incoherent_impl] has to be added to all impl items of an incoherent inherent impl." diff --git a/compiler/rustc_hir_analysis/src/collect.rs b/compiler/rustc_hir_analysis/src/collect.rs index 80426c239ac..9f33d84ab52 100644 --- a/compiler/rustc_hir_analysis/src/collect.rs +++ b/compiler/rustc_hir_analysis/src/collect.rs @@ -934,9 +934,10 @@ fn trait_def(tcx: TyCtxt<'_>, def_id: DefId) -> ty::TraitDef { } let is_marker = tcx.has_attr(def_id, sym::marker); + let rustc_coinductive = tcx.has_attr(def_id, sym::rustc_coinductive); let skip_array_during_method_dispatch = tcx.has_attr(def_id, sym::rustc_skip_array_during_method_dispatch); - let spec_kind = if tcx.has_attr(def_id, sym::rustc_unsafe_specialization_marker) { + let specialization_kind = if tcx.has_attr(def_id, sym::rustc_unsafe_specialization_marker) { ty::trait_def::TraitSpecializationKind::Marker } else if tcx.has_attr(def_id, sym::rustc_specialization_trait) { ty::trait_def::TraitSpecializationKind::AlwaysApplicable @@ -1036,16 +1037,17 @@ fn trait_def(tcx: TyCtxt<'_>, def_id: DefId) -> ty::TraitDef { no_dups.then_some(list) }); - ty::TraitDef::new( + ty::TraitDef { def_id, unsafety, paren_sugar, - is_auto, + has_auto_impl: is_auto, is_marker, + is_coinductive: rustc_coinductive || is_auto, skip_array_during_method_dispatch, - spec_kind, + specialization_kind, must_implement_one_of, - ) + } } fn are_suggestable_generic_args(generic_args: &[hir::GenericArg<'_>]) -> bool { diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs index 6d8c9d73763..5b7ca750f78 100644 --- a/compiler/rustc_middle/src/ty/mod.rs +++ b/compiler/rustc_middle/src/ty/mod.rs @@ -2388,15 +2388,17 @@ impl<'tcx> TyCtxt<'tcx> { self.trait_def(trait_def_id).has_auto_impl } + /// Returns `true` if this is coinductive, either because it is + /// an auto trait or because it has the `#[rustc_coinductive]` attribute. + pub fn trait_is_coinductive(self, trait_def_id: DefId) -> bool { + self.trait_def(trait_def_id).is_coinductive + } + /// Returns `true` if this is a trait alias. pub fn trait_is_alias(self, trait_def_id: DefId) -> bool { self.def_kind(trait_def_id) == DefKind::TraitAlias } - pub fn trait_is_coinductive(self, trait_def_id: DefId) -> bool { - self.trait_is_auto(trait_def_id) || self.lang_items().sized_trait() == Some(trait_def_id) - } - /// Returns layout of a generator. Layout might be unavailable if the /// generator is tainted by errors. pub fn generator_layout(self, def_id: DefId) -> Option<&'tcx GeneratorLayout<'tcx>> { diff --git a/compiler/rustc_middle/src/ty/trait_def.rs b/compiler/rustc_middle/src/ty/trait_def.rs index b38a5fbf20f..71353acaaa7 100644 --- a/compiler/rustc_middle/src/ty/trait_def.rs +++ b/compiler/rustc_middle/src/ty/trait_def.rs @@ -31,6 +31,15 @@ pub struct TraitDef { /// and thus `impl`s of it are allowed to overlap. pub is_marker: bool, + /// If `true`, then this trait has to `#[rustc_coinductive]` attribute or + /// is an auto trait. This indicates that trait solver cycles involving an + /// `X: ThisTrait` goal are accepted. + /// + /// In the future all traits should be coinductive, but we need a better + /// formal understanding of what exactly that means and should probably + /// also have already switched to the new trait solver. + pub is_coinductive: bool, + /// If `true`, then this trait has the `#[rustc_skip_array_during_method_dispatch]` /// attribute, indicating that editions before 2021 should not consider this trait /// during method dispatch if the receiver is an array. @@ -81,28 +90,6 @@ impl TraitImpls { } impl<'tcx> TraitDef { - pub fn new( - def_id: DefId, - unsafety: hir::Unsafety, - paren_sugar: bool, - has_auto_impl: bool, - is_marker: bool, - skip_array_during_method_dispatch: bool, - specialization_kind: TraitSpecializationKind, - must_implement_one_of: Option>, - ) -> TraitDef { - TraitDef { - def_id, - unsafety, - paren_sugar, - has_auto_impl, - is_marker, - skip_array_during_method_dispatch, - specialization_kind, - must_implement_one_of, - } - } - pub fn ancestors( &self, tcx: TyCtxt<'tcx>, diff --git a/compiler/rustc_passes/src/check_attr.rs b/compiler/rustc_passes/src/check_attr.rs index 238ec9ca30f..225095948af 100644 --- a/compiler/rustc_passes/src/check_attr.rs +++ b/compiler/rustc_passes/src/check_attr.rs @@ -156,6 +156,7 @@ impl CheckAttrVisitor<'_> { | sym::rustc_dirty | sym::rustc_if_this_changed | sym::rustc_then_this_would_need => self.check_rustc_dirty_clean(&attr), + sym::rustc_coinductive => self.check_rustc_coinductive(&attr, span, target), sym::cmse_nonsecure_entry => { self.check_cmse_nonsecure_entry(hir_id, attr, span, target) } @@ -1608,6 +1609,20 @@ impl CheckAttrVisitor<'_> { } } + /// Checks if the `#[rustc_coinductive]` attribute is applied to a trait. + fn check_rustc_coinductive(&self, attr: &Attribute, span: Span, target: Target) -> bool { + match target { + Target::Trait => true, + _ => { + self.tcx.sess.emit_err(errors::AttrShouldBeAppliedToTrait { + attr_span: attr.span, + defn_span: span, + }); + false + } + } + } + /// Checks if `#[link_section]` is applied to a function or static. fn check_link_section(&self, hir_id: HirId, attr: &Attribute, span: Span, target: Target) { match target { diff --git a/compiler/rustc_span/src/symbol.rs b/compiler/rustc_span/src/symbol.rs index ef417d3e0a7..56835a2466a 100644 --- a/compiler/rustc_span/src/symbol.rs +++ b/compiler/rustc_span/src/symbol.rs @@ -1224,6 +1224,7 @@ symbols! { rustc_capture_analysis, rustc_clean, rustc_coherence_is_core, + rustc_coinductive, rustc_const_stable, rustc_const_unstable, rustc_conversion_suggestion, diff --git a/library/core/src/marker.rs b/library/core/src/marker.rs index 07a7d45c7eb..520ae0edb09 100644 --- a/library/core/src/marker.rs +++ b/library/core/src/marker.rs @@ -97,6 +97,7 @@ unsafe impl Send for &T {} #[fundamental] // for Default, for example, which requires that `[T]: !Default` be evaluatable #[rustc_specialization_trait] #[rustc_deny_explicit_impl] +#[cfg_attr(not(bootstrap), rustc_coinductive)] pub trait Sized { // Empty. } -- cgit 1.4.1-3-g733a5