From a2e94ca1ee21f46eb18cd4392fa8e621ebaea20a Mon Sep 17 00:00:00 2001 From: Lukas Kalbertodt Date: Thu, 25 Jul 2019 00:39:39 +0200 Subject: Add `array::IntoIter` as a consuming/by-value array iterator The iterator is implemented using const generics. It implements the traits `Iterator`, `DoubleEndedIterator`, `ExactSizeIterator`, `FusedIterator` and `TrustedLen`. It also contains a public method `new` to create it from an array. `IntoIterator` was not implemented for arrays yet, as there are still some open questions regarding backwards compatibility. This commit only adds the iterator impl and does not yet offer a convenient way to obtain that iterator. --- src/libcore/array/iter.rs | 266 ++++++++++++++++++++++++++++ src/libcore/array/mod.rs | 432 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 698 insertions(+) create mode 100644 src/libcore/array/iter.rs create mode 100644 src/libcore/array/mod.rs (limited to 'src/libcore/array') diff --git a/src/libcore/array/iter.rs b/src/libcore/array/iter.rs new file mode 100644 index 00000000000..850a599c659 --- /dev/null +++ b/src/libcore/array/iter.rs @@ -0,0 +1,266 @@ +//! Defines the `IntoIter` owned iterator for arrays. + +use crate::{ + fmt, + iter::{ExactSizeIterator, FusedIterator, TrustedLen}, + mem::{self, MaybeUninit}, + ops::Range, + ptr, +}; +use super::LengthAtMost32; + + +/// A by-value [array] iterator. +/// +/// [array]: ../../std/primitive.array.html +#[unstable(feature = "array_value_iter", issue = "0")] +pub struct IntoIter +where + [T; N]: LengthAtMost32, +{ + /// This is the array we are iterating over. + /// + /// Elements with index `i` where `alive.start <= i < alive.end` have not + /// been yielded yet and are valid array entries. Elements with indices `i + /// < alive.start` or `i >= alive.end` have been yielded already and must + /// not be accessed anymore! Those dead elements might even be in a + /// completely uninitialized state! + /// + /// So the invariants are: + /// - `data[alive]` is alive (i.e. contains valid elements) + /// - `data[..alive.start]` and `data[alive.end..]` are dead (i.e. the + /// elements were already read and must not be touched anymore!) + data: [MaybeUninit; N], + + /// The elements in `data` that have not been yielded yet. + /// + /// Invariants: + /// - `alive.start <= alive.end` + /// - `alive.end <= N` + alive: Range, +} + +impl IntoIter +where + [T; N]: LengthAtMost32, +{ + /// Creates a new iterator over the given `array`. + /// + /// *Note*: this method might never get stabilized and/or removed in the + /// future as there will likely be another, preferred way of obtaining this + /// iterator (either via `IntoIterator` for arrays or via another way). + #[unstable(feature = "array_value_iter", issue = "0")] + pub fn new(array: [T; N]) -> Self { + // The transmute here is actually safe. The docs of `MaybeUninit` + // promise: + // + // > `MaybeUninit` is guaranteed to have the same size and alignment + // > as `T`. + // + // The docs even show a transmute from an array of `MaybeUninit` to + // an array of `T`. + // + // With that, this initialization satisfies the invariants. + + // FIXME(LukasKalbertodt): actually use `mem::transmute` here, once it + // works with const generics: + // `mem::transmute::<[T; {N}], [MaybeUninit; {N}]>(array)` + // + // Until then, we do it manually here. We first create a bitwise copy + // but cast the pointer so that it is treated as a different type. Then + // we forget `array` so that it is not dropped. + let data = unsafe { + let data = ptr::read(&array as *const [T; N] as *const [MaybeUninit; N]); + mem::forget(array); + data + }; + + Self { + data, + alive: 0..N, + } + } + + /// Returns an immutable slice of all elements that have not been yielded + /// yet. + fn as_slice(&self) -> &[T] { + // This transmute is safe. As mentioned in `new`, `MaybeUninit` retains + // the size and alignment of `T`. Furthermore, we know that all + // elements within `alive` are properly initialized. + let slice = &self.data[self.alive.clone()]; + unsafe { + mem::transmute::<&[MaybeUninit], &[T]>(slice) + } + } +} + + +#[stable(feature = "array_value_iter_impls", since = "1.38.0")] +impl Iterator for IntoIter +where + [T; N]: LengthAtMost32, +{ + type Item = T; + fn next(&mut self) -> Option { + if self.alive.start == self.alive.end { + return None; + } + + // Bump start index. + // + // From the check above we know that `alive.start != alive.end`. + // Combine this with the invariant `alive.start <= alive.end`, we know + // that `alive.start < alive.end`. Increasing `alive.start` by 1 + // maintains the invariant regarding `alive`. However, due to this + // change, for a short time, the alive zone is not `data[alive]` + // anymore, but `data[idx..alive.end]`. + let idx = self.alive.start; + self.alive.start += 1; + + // Read the element from the array. This is safe: `idx` is an index + // into the "alive" region of the array. Reading this element means + // that `data[idx]` is regarded as dead now (i.e. do not touch). As + // `idx` was the start of the alive-zone, the alive zone is now + // `data[alive]` again, restoring all invariants. + let out = unsafe { self.data.get_unchecked(idx).read() }; + + Some(out) + } + + fn size_hint(&self) -> (usize, Option) { + let len = self.len(); + (len, Some(len)) + } + + fn count(self) -> usize { + self.len() + } + + fn last(mut self) -> Option { + self.next_back() + } +} + +#[stable(feature = "array_value_iter_impls", since = "1.38.0")] +impl DoubleEndedIterator for IntoIter +where + [T; N]: LengthAtMost32, +{ + fn next_back(&mut self) -> Option { + if self.alive.start == self.alive.end { + return None; + } + + // Decrease end index. + // + // From the check above we know that `alive.start != alive.end`. + // Combine this with the invariant `alive.start <= alive.end`, we know + // that `alive.start < alive.end`. As `alive.start` cannot be negative, + // `alive.end` is at least 1, meaning that we can safely decrement it + // by one. This also maintains the invariant `alive.start <= + // alive.end`. However, due to this change, for a short time, the alive + // zone is not `data[alive]` anymore, but `data[alive.start..alive.end + // + 1]`. + self.alive.end -= 1; + + // Read the element from the array. This is safe: `alive.end` is an + // index into the "alive" region of the array. Compare the previous + // comment that states that the alive region is + // `data[alive.start..alive.end + 1]`. Reading this element means that + // `data[alive.end]` is regarded as dead now (i.e. do not touch). As + // `alive.end` was the end of the alive-zone, the alive zone is now + // `data[alive]` again, restoring all invariants. + let out = unsafe { self.data.get_unchecked(self.alive.end).read() }; + + Some(out) + } +} + +#[stable(feature = "array_value_iter_impls", since = "1.38.0")] +impl Drop for IntoIter +where + [T; N]: LengthAtMost32, +{ + fn drop(&mut self) { + // We simply drop each element via `for_each`. This should not incur + // any significant runtime overhead and avoids adding another `unsafe` + // block. + self.by_ref().for_each(drop); + } +} + +#[stable(feature = "array_value_iter_impls", since = "1.38.0")] +impl ExactSizeIterator for IntoIter +where + [T; N]: LengthAtMost32, +{ + fn len(&self) -> usize { + // Will never underflow due to the invariant `alive.start <= + // alive.end`. + self.alive.end - self.alive.start + } + fn is_empty(&self) -> bool { + self.alive.is_empty() + } +} + +#[stable(feature = "array_value_iter_impls", since = "1.38.0")] +impl FusedIterator for IntoIter +where + [T; N]: LengthAtMost32, +{} + +// The iterator indeed reports the correct length. The number of "alive" +// elements (that will still be yielded) is the length of the range `alive`. +// This range is decremented in length in either `next` or `next_back`. It is +// always decremented by 1 in those methods, but only if `Some(_)` is returned. +#[stable(feature = "array_value_iter_impls", since = "1.38.0")] +unsafe impl TrustedLen for IntoIter +where + [T; N]: LengthAtMost32, +{} + +#[stable(feature = "array_value_iter_impls", since = "1.38.0")] +impl Clone for IntoIter +where + [T; N]: LengthAtMost32, +{ + fn clone(&self) -> Self { + unsafe { + // This creates a new uninitialized array. Note that the `assume_init` + // refers to the array, not the individual elements. And it is Ok if + // the array is in an uninitialized state as all elements may be + // uninitialized (all bit patterns are valid). Compare the + // `MaybeUninit` docs for more information. + let mut new_data: [MaybeUninit; N] = MaybeUninit::uninit().assume_init(); + + // Clone all alive elements. + for idx in self.alive.clone() { + // The element at `idx` in the old array is alive, so we can + // safely call `get_ref()`. We then clone it, and write the + // clone into the new array. + let clone = self.data.get_unchecked(idx).get_ref().clone(); + new_data.get_unchecked_mut(idx).write(clone); + } + + Self { + data: new_data, + alive: self.alive.clone(), + } + } + } +} + +#[stable(feature = "array_value_iter_impls", since = "1.38.0")] +impl fmt::Debug for IntoIter +where + [T; N]: LengthAtMost32, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + // Only print the elements that were not yielded yet: we cannot + // access the yielded elements anymore. + f.debug_tuple("IntoIter") + .field(&self.as_slice()) + .finish() + } +} diff --git a/src/libcore/array/mod.rs b/src/libcore/array/mod.rs new file mode 100644 index 00000000000..120658e9a43 --- /dev/null +++ b/src/libcore/array/mod.rs @@ -0,0 +1,432 @@ +//! Implementations of things like `Eq` for fixed-length arrays +//! up to a certain length. Eventually we should able to generalize +//! to all lengths. +//! +//! *[See also the array primitive type](../../std/primitive.array.html).* + +#![stable(feature = "core_array", since = "1.36.0")] + +use crate::borrow::{Borrow, BorrowMut}; +use crate::cmp::Ordering; +use crate::convert::{Infallible, TryFrom}; +use crate::fmt; +use crate::hash::{Hash, self}; +use crate::marker::Unsize; +use crate::slice::{Iter, IterMut}; + +#[cfg(not(bootstrap))] +mod iter; + +#[cfg(not(bootstrap))] +#[unstable(feature = "array_value_iter", issue = "0")] +pub use iter::IntoIter; + +/// Utility trait implemented only on arrays of fixed size +/// +/// This trait can be used to implement other traits on fixed-size arrays +/// without causing much metadata bloat. +/// +/// The trait is marked unsafe in order to restrict implementors to fixed-size +/// arrays. User of this trait can assume that implementors have the exact +/// layout in memory of a fixed size array (for example, for unsafe +/// initialization). +/// +/// Note that the traits [`AsRef`] and [`AsMut`] provide similar methods for types that +/// may not be fixed-size arrays. Implementors should prefer those traits +/// instead. +/// +/// [`AsRef`]: ../convert/trait.AsRef.html +/// [`AsMut`]: ../convert/trait.AsMut.html +#[unstable(feature = "fixed_size_array", issue = "27778")] +pub unsafe trait FixedSizeArray { + /// Converts the array to immutable slice + #[unstable(feature = "fixed_size_array", issue = "27778")] + fn as_slice(&self) -> &[T]; + /// Converts the array to mutable slice + #[unstable(feature = "fixed_size_array", issue = "27778")] + fn as_mut_slice(&mut self) -> &mut [T]; +} + +#[unstable(feature = "fixed_size_array", issue = "27778")] +unsafe impl> FixedSizeArray for A { + #[inline] + fn as_slice(&self) -> &[T] { + self + } + #[inline] + fn as_mut_slice(&mut self) -> &mut [T] { + self + } +} + +/// The error type returned when a conversion from a slice to an array fails. +#[stable(feature = "try_from", since = "1.34.0")] +#[derive(Debug, Copy, Clone)] +pub struct TryFromSliceError(()); + +#[stable(feature = "core_array", since = "1.36.0")] +impl fmt::Display for TryFromSliceError { + #[inline] + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Display::fmt(self.__description(), f) + } +} + +impl TryFromSliceError { + #[unstable(feature = "array_error_internals", + reason = "available through Error trait and this method should not \ + be exposed publicly", + issue = "0")] + #[inline] + #[doc(hidden)] + pub fn __description(&self) -> &str { + "could not convert slice to array" + } +} + +#[stable(feature = "try_from_slice_error", since = "1.36.0")] +impl From for TryFromSliceError { + fn from(x: Infallible) -> TryFromSliceError { + match x {} + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl AsRef<[T]> for [T; N] +where + [T; N]: LengthAtMost32, +{ + #[inline] + fn as_ref(&self) -> &[T] { + &self[..] + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl AsMut<[T]> for [T; N] +where + [T; N]: LengthAtMost32, +{ + #[inline] + fn as_mut(&mut self) -> &mut [T] { + &mut self[..] + } +} + +#[stable(feature = "array_borrow", since = "1.4.0")] +impl Borrow<[T]> for [T; N] +where + [T; N]: LengthAtMost32, +{ + fn borrow(&self) -> &[T] { + self + } +} + +#[stable(feature = "array_borrow", since = "1.4.0")] +impl BorrowMut<[T]> for [T; N] +where + [T; N]: LengthAtMost32, +{ + fn borrow_mut(&mut self) -> &mut [T] { + self + } +} + +#[stable(feature = "try_from", since = "1.34.0")] +impl TryFrom<&[T]> for [T; N] +where + T: Copy, + [T; N]: LengthAtMost32, +{ + type Error = TryFromSliceError; + + fn try_from(slice: &[T]) -> Result<[T; N], TryFromSliceError> { + <&Self>::try_from(slice).map(|r| *r) + } +} + +#[stable(feature = "try_from", since = "1.34.0")] +impl<'a, T, const N: usize> TryFrom<&'a [T]> for &'a [T; N] +where + [T; N]: LengthAtMost32, +{ + type Error = TryFromSliceError; + + fn try_from(slice: &[T]) -> Result<&[T; N], TryFromSliceError> { + if slice.len() == N { + let ptr = slice.as_ptr() as *const [T; N]; + unsafe { Ok(&*ptr) } + } else { + Err(TryFromSliceError(())) + } + } +} + +#[stable(feature = "try_from", since = "1.34.0")] +impl<'a, T, const N: usize> TryFrom<&'a mut [T]> for &'a mut [T; N] +where + [T; N]: LengthAtMost32, +{ + type Error = TryFromSliceError; + + fn try_from(slice: &mut [T]) -> Result<&mut [T; N], TryFromSliceError> { + if slice.len() == N { + let ptr = slice.as_mut_ptr() as *mut [T; N]; + unsafe { Ok(&mut *ptr) } + } else { + Err(TryFromSliceError(())) + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Hash for [T; N] +where + [T; N]: LengthAtMost32, +{ + fn hash(&self, state: &mut H) { + Hash::hash(&self[..], state) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl fmt::Debug for [T; N] +where + [T; N]: LengthAtMost32, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Debug::fmt(&&self[..], f) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T, const N: usize> IntoIterator for &'a [T; N] +where + [T; N]: LengthAtMost32, +{ + type Item = &'a T; + type IntoIter = Iter<'a, T>; + + fn into_iter(self) -> Iter<'a, T> { + self.iter() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T, const N: usize> IntoIterator for &'a mut [T; N] +where + [T; N]: LengthAtMost32, +{ + type Item = &'a mut T; + type IntoIter = IterMut<'a, T>; + + fn into_iter(self) -> IterMut<'a, T> { + self.iter_mut() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl PartialEq<[B; N]> for [A; N] +where + A: PartialEq, + [A; N]: LengthAtMost32, + [B; N]: LengthAtMost32, +{ + #[inline] + fn eq(&self, other: &[B; N]) -> bool { + self[..] == other[..] + } + #[inline] + fn ne(&self, other: &[B; N]) -> bool { + self[..] != other[..] + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl PartialEq<[B]> for [A; N] +where + A: PartialEq, + [A; N]: LengthAtMost32, +{ + #[inline] + fn eq(&self, other: &[B]) -> bool { + self[..] == other[..] + } + #[inline] + fn ne(&self, other: &[B]) -> bool { + self[..] != other[..] + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl PartialEq<[A; N]> for [B] +where + B: PartialEq, + [A; N]: LengthAtMost32, +{ + #[inline] + fn eq(&self, other: &[A; N]) -> bool { + self[..] == other[..] + } + #[inline] + fn ne(&self, other: &[A; N]) -> bool { + self[..] != other[..] + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'b, A, B, const N: usize> PartialEq<&'b [B]> for [A; N] +where + A: PartialEq, + [A; N]: LengthAtMost32, +{ + #[inline] + fn eq(&self, other: &&'b [B]) -> bool { + self[..] == other[..] + } + #[inline] + fn ne(&self, other: &&'b [B]) -> bool { + self[..] != other[..] + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'b, A, B, const N: usize> PartialEq<[A; N]> for &'b [B] +where + B: PartialEq, + [A; N]: LengthAtMost32, +{ + #[inline] + fn eq(&self, other: &[A; N]) -> bool { + self[..] == other[..] + } + #[inline] + fn ne(&self, other: &[A; N]) -> bool { + self[..] != other[..] + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'b, A, B, const N: usize> PartialEq<&'b mut [B]> for [A; N] +where + A: PartialEq, + [A; N]: LengthAtMost32, +{ + #[inline] + fn eq(&self, other: &&'b mut [B]) -> bool { + self[..] == other[..] + } + #[inline] + fn ne(&self, other: &&'b mut [B]) -> bool { + self[..] != other[..] + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'b, A, B, const N: usize> PartialEq<[A; N]> for &'b mut [B] +where + B: PartialEq, + [A; N]: LengthAtMost32, +{ + #[inline] + fn eq(&self, other: &[A; N]) -> bool { + self[..] == other[..] + } + #[inline] + fn ne(&self, other: &[A; N]) -> bool { + self[..] != other[..] + } +} + +// NOTE: some less important impls are omitted to reduce code bloat +// __impl_slice_eq2! { [A; $N], &'b [B; $N] } +// __impl_slice_eq2! { [A; $N], &'b mut [B; $N] } + +#[stable(feature = "rust1", since = "1.0.0")] +impl Eq for [T; N] where [T; N]: LengthAtMost32 {} + +#[stable(feature = "rust1", since = "1.0.0")] +impl PartialOrd for [T; N] +where + [T; N]: LengthAtMost32, +{ + #[inline] + fn partial_cmp(&self, other: &[T; N]) -> Option { + PartialOrd::partial_cmp(&&self[..], &&other[..]) + } + #[inline] + fn lt(&self, other: &[T; N]) -> bool { + PartialOrd::lt(&&self[..], &&other[..]) + } + #[inline] + fn le(&self, other: &[T; N]) -> bool { + PartialOrd::le(&&self[..], &&other[..]) + } + #[inline] + fn ge(&self, other: &[T; N]) -> bool { + PartialOrd::ge(&&self[..], &&other[..]) + } + #[inline] + fn gt(&self, other: &[T; N]) -> bool { + PartialOrd::gt(&&self[..], &&other[..]) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Ord for [T; N] +where + [T; N]: LengthAtMost32, +{ + #[inline] + fn cmp(&self, other: &[T; N]) -> Ordering { + Ord::cmp(&&self[..], &&other[..]) + } +} + +/// Implemented for lengths where trait impls are allowed on arrays in core/std +#[rustc_on_unimplemented( + message="arrays only have std trait implementations for lengths 0..=32", +)] +#[unstable(feature = "const_generic_impls_guard", issue = "0", + reason = "will never be stable, just a temporary step until const generics are stable")] +pub trait LengthAtMost32 {} + +macro_rules! array_impls { + ($($N:literal)+) => { + $( + #[unstable(feature = "const_generic_impls_guard", issue = "0")] + impl LengthAtMost32 for [T; $N] {} + )+ + } +} + +array_impls! { + 0 1 2 3 4 5 6 7 8 9 + 10 11 12 13 14 15 16 17 18 19 + 20 21 22 23 24 25 26 27 28 29 + 30 31 32 +} + +// The Default impls cannot be generated using the array_impls! macro because +// they require array literals. + +macro_rules! array_impl_default { + {$n:expr, $t:ident $($ts:ident)*} => { + #[stable(since = "1.4.0", feature = "array_default")] + impl Default for [T; $n] where T: Default { + fn default() -> [T; $n] { + [$t::default(), $($ts::default()),*] + } + } + array_impl_default!{($n - 1), $($ts)*} + }; + {$n:expr,} => { + #[stable(since = "1.4.0", feature = "array_default")] + impl Default for [T; $n] { + fn default() -> [T; $n] { [] } + } + }; +} + +array_impl_default!{32, T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T} -- cgit 1.4.1-3-g733a5