#![stable(feature = "rust1", since = "1.0.0")]
use core::cmp::{self, Ordering};
+use core::convert::TryFrom;
use core::fmt;
use core::hash::{Hash, Hasher};
use core::intrinsics::{arith_offset, assume};
-use core::iter::{FromIterator, FusedIterator, InPlaceIterable, SourceIter, TrustedLen};
+use core::iter::{
+ FromIterator, FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccess,
+};
use core::marker::PhantomData;
use core::mem::{self, ManuallyDrop, MaybeUninit};
use core::ops::Bound::{Excluded, Included, Unbounded};
impl<T> FromIterator<T> for Vec<T> {
#[inline]
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T> {
- <Self as SpecFrom<T, I::IntoIter>>::from_iter(iter.into_iter())
+ <Self as SpecFromIter<T, I::IntoIter>>::from_iter(iter.into_iter())
}
}
}
}
-// Specialization trait used for Vec::from_iter
-trait SpecFrom<T, I> {
+/// Specialization trait used for Vec::from_iter
+///
+/// ## The delegation graph:
+///
+/// ```text
+/// +-------------+
+/// |FromIterator |
+/// +-+-----------+
+/// |
+/// v
+/// +-+-------------------------------+ +---------------------+
+/// |SpecFromIter +---->+SpecFromIterNested |
+/// |where I: | | |where I: |
+/// | Iterator (default)----------+ | | Iterator (default) |
+/// | vec::IntoIter | | | TrustedLen |
+/// | SourceIterMarker---fallback-+ | | |
+/// | slice::Iter | | |
+/// | Iterator<Item = &Clone> | +---------------------+
+/// +---------------------------------+
+///
+/// ```
+trait SpecFromIter<T, I> {
fn from_iter(iter: I) -> Self;
}
-impl<T, I> SpecFrom<T, I> for Vec<T>
+/// Another specialization trait for Vec::from_iter
+/// necessary to manually prioritize overlapping specializations
+/// see [`SpecFromIter`] for details.
+trait SpecFromIterNested<T, I> {
+ fn from_iter(iter: I) -> Self;
+}
+
+impl<T, I> SpecFromIterNested<T, I> for Vec<T>
where
I: Iterator<Item = T>,
{
vector
}
};
+ // must delegate to spec_extend() since extend() itself delegates
+ // to spec_from for empty Vecs
<Vec<T> as SpecExtend<T, I>>::spec_extend(&mut vector, iterator);
vector
}
}
-struct InPlaceIterFront<T> {
+impl<T, I> SpecFromIterNested<T, I> for Vec<T>
+where
+ I: TrustedLen<Item = T>,
+{
+ fn from_iter(iterator: I) -> Self {
+ let mut vector = Vec::new();
+ // must delegate to spec_extend() since extend() itself delegates
+ // to spec_from for empty Vecs
+ vector.spec_extend(iterator);
+ vector
+ }
+}
+
+impl<T, I> SpecFromIter<T, I> for Vec<T>
+where
+ I: Iterator<Item = T>,
+{
+ default fn from_iter(iterator: I) -> Self {
+ SpecFromIterNested::from_iter(iterator)
+ }
+}
+
+// A helper struct for in-place iteration that drops the destination slice of iteration,
+// i.e. the head. The source slice (the tail) is dropped by IntoIter.
+struct InPlaceDrop<T> {
inner: *mut T,
dst: *mut T,
- did_panic: bool,
}
-impl<T> InPlaceIterFront<T> {
- unsafe fn len(&self) -> usize {
- self.dst.offset_from(self.inner) as usize
+impl<T> InPlaceDrop<T> {
+ fn len(&self) -> usize {
+ unsafe { self.dst.offset_from(self.inner) as usize }
}
}
-impl<T> Drop for InPlaceIterFront<T> {
+impl<T> Drop for InPlaceDrop<T> {
#[inline]
fn drop(&mut self) {
- unsafe {
- if mem::needs_drop::<T>() && self.did_panic {
- ptr::drop_in_place(slice::from_raw_parts_mut(self.inner, self.len()) as *mut _);
+ if mem::needs_drop::<T>() {
+ unsafe {
+ ptr::drop_in_place(slice::from_raw_parts_mut(self.inner, self.len()));
}
}
}
}
-fn from_into_iter_source<T, I>(mut iterator: I) -> Vec<T>
-where
- I: Iterator<Item = T> + InPlaceIterable + SourceIter<Source = IntoIter<T>>,
-{
- let original_ptr = iterator.as_inner().buf.as_ptr();
- let mut front_buffer =
- InPlaceIterFront { inner: original_ptr, dst: original_ptr, did_panic: true };
-
- while let Some(item) = iterator.next() {
- let source_iter = iterator.as_inner();
- debug_assert_eq!(original_ptr, source_iter.buf.as_ptr());
- unsafe {
- debug_assert!(
- front_buffer.dst as *const _ < source_iter.ptr,
- "InPlaceIterable implementation produced more\
- items than it consumed from the source"
- );
- ptr::write(front_buffer.dst, item);
- front_buffer.dst = front_buffer.dst.add(1);
- }
- }
-
- let src = iterator.as_inner();
- front_buffer.did_panic = false;
- let vec = unsafe { Vec::from_raw_parts(src.buf.as_ptr(), front_buffer.len(), src.cap) };
- src.cap = 0;
- src.buf = unsafe { NonNull::new_unchecked(RawVec::NEW.ptr()) };
- src.ptr = src.buf.as_ptr();
- src.end = src.buf.as_ptr();
- vec
-}
-
-impl<T> SpecFrom<T, IntoIter<T>> for Vec<T> {
+impl<T> SpecFromIter<T, IntoIter<T>> for Vec<T> {
fn from_iter(iterator: IntoIter<T>) -> Self {
// A common case is passing a vector into a function which immediately
// re-collects into a vector. We can short circuit this if the IntoIter
// has not been advanced at all.
- if iterator.buf.as_ptr() as *const _ == iterator.ptr {
+ // When it has been advanced We can also reuse the memory and move the data to the front.
+ // But we only do so when the resulting Vec wouldn't have more unused capacity
+ // than creating it through the generic FromIterator implementation would. That limitation
+ // is not strictly necessary as Vec's allocation behavior is intentionally unspecified.
+ // But it is a conservative choice.
+ let has_advanced = iterator.buf.as_ptr() as *const _ != iterator.ptr;
+ if !has_advanced || iterator.len() >= iterator.cap / 2 {
unsafe {
let it = ManuallyDrop::new(iterator);
+ if has_advanced {
+ ptr::copy(it.ptr, it.buf.as_ptr(), it.len());
+ }
return Vec::from_raw_parts(it.buf.as_ptr(), it.len(), it.cap);
}
}
- from_into_iter_source(iterator)
+ let mut vec = Vec::new();
+ // must delegate to spec_extend() since extend() itself delegates
+ // to spec_from for empty Vecs
+ vec.spec_extend(iterator);
+ vec
}
}
-// Further specialization potential once lattice specialization exists
-// and https://github.com/rust-lang/rust/issues/62645 has been solved:
-// This can be broadened to only require size and alignment equality between
-// input and output Item types.
-impl<T, I> SpecFrom<T, I> for Vec<T>
+fn write_in_place_with_drop<T>(
+ src_end: *const T,
+) -> impl FnMut(InPlaceDrop<T>, T) -> Result<InPlaceDrop<T>, !> {
+ move |mut sink, item| {
+ unsafe {
+ // the InPlaceIterable contract cannot be verified precisely here since
+ // try_fold has an exclusive reference to the source pointer
+ // all we can do is check if it's still in range
+ debug_assert!(sink.dst as *const _ <= src_end, "InPlaceIterable contract violation");
+ ptr::write(sink.dst, item);
+ sink.dst = sink.dst.add(1);
+ }
+ Ok(sink)
+ }
+}
+
+/// Specialization marker for collecting an iterator pipeline into a Vec while reusing the
+/// source allocation, i.e. executing the pipeline in place.
+///
+/// The SourceIter parent trait is necessary for the specializing function to access the allocation
+/// which is to be reused. But it is not sufficient for the specialization to be valid. See
+/// additional bounds on the impl.
+#[rustc_unsafe_specialization_marker]
+trait SourceIterMarker: SourceIter<Source: AsIntoIter> {}
+
+// The std-internal SourceIter/InPlaceIterable traits are only implemented by chains of
+// Adapter<Adapter<Adapter<IntoIter>>> (all owned by core/std). Additional bounds
+// on the adapter implementations (beyond `impl<I: Trait> Trait for Adapter<I>`) only depend on other
+// traits already marked as specialization traits (Copy, TrustedRandomAccess, FusedIterator).
+// I.e. the marker does not depend on lifetimes of user-supplied types. Modulo the Copy hole, which
+// several other specializations already depend on.
+impl<T> SourceIterMarker for T where T: SourceIter<Source: AsIntoIter> + InPlaceIterable {}
+
+impl<T, I> SpecFromIter<T, I> for Vec<T>
where
- I: Iterator<Item = T> + InPlaceIterable + SourceIter<Source = IntoIter<T>>,
+ I: Iterator<Item = T> + SourceIterMarker,
{
- default fn from_iter(iterator: I) -> Self {
- from_into_iter_source(iterator)
+ default fn from_iter(mut iterator: I) -> Self {
+ // Additional requirements which cannot expressed via trait bounds. We rely on const eval
+ // instead:
+ // a) no ZSTs as there would be no allocation to reuse and pointer arithmetic would panic
+ // b) size match as required by Alloc contract
+ // c) alignments match as required by Alloc contract
+ if mem::size_of::<T>() == 0
+ || mem::size_of::<T>()
+ != mem::size_of::<<<I as SourceIter>::Source as AsIntoIter>::Item>()
+ || mem::align_of::<T>()
+ != mem::align_of::<<<I as SourceIter>::Source as AsIntoIter>::Item>()
+ {
+ // fallback to more generic implementations
+ return SpecFromIterNested::from_iter(iterator);
+ }
+
+ let (src_buf, src_ptr, dst_buf, dst_end, cap) = unsafe {
+ let inner = iterator.as_inner().as_into_iter();
+ (
+ inner.buf.as_ptr(),
+ inner.ptr,
+ inner.buf.as_ptr() as *mut T,
+ inner.end as *const T,
+ inner.cap,
+ )
+ };
+
+ // use try-fold since
+ // - it vectorizes better for some iterator adapters
+ // - unlike most internal iteration methods methods it only takes a &mut self
+ // - it lets us thread the write pointer through its innards and get it back in the end
+ let sink = InPlaceDrop { inner: dst_buf, dst: dst_buf };
+ let sink = iterator
+ .try_fold::<_, _, Result<_, !>>(sink, write_in_place_with_drop(dst_end))
+ .unwrap();
+ // iteration succeeded, don't drop head
+ let dst = mem::ManuallyDrop::new(sink).dst;
+
+ let src = unsafe { iterator.as_inner().as_into_iter() };
+ // check if SourceIter contract was upheld
+ // caveat: if they weren't we may not even make it to this point
+ debug_assert_eq!(src_buf, src.buf.as_ptr());
+ // check InPlaceIterable contract. This is only possible if the iterator advanced the
+ // source pointer at all. If it uses unchecked access via TrustedRandomAccess
+ // then the source pointer will stay in its initial position and we can't use it as reference
+ if src.ptr != src_ptr {
+ debug_assert!(
+ dst as *const _ <= src.ptr,
+ "InPlaceIterable contract violation, write pointer advanced beyond read pointer"
+ );
+ }
+
+ // drop any remaining values at the tail of the source
+ src.drop_remaining();
+ // but prevent drop of the allocation itself once IntoIter goes out of scope
+ src.forget_allocation();
+
+ let vec = unsafe {
+ let len = dst.offset_from(dst_buf) as usize;
+ Vec::from_raw_parts(dst_buf, len, cap)
+ };
+
+ vec
}
}
-impl<'a, T: 'a, I> SpecFrom<&'a T, I> for Vec<T>
+impl<'a, T: 'a, I> SpecFromIter<&'a T, I> for Vec<T>
where
I: Iterator<Item = &'a T>,
T: Clone,
{
default fn from_iter(iterator: I) -> Self {
- SpecFrom::from_iter(iterator.cloned())
+ SpecFromIter::from_iter(iterator.cloned())
+ }
+}
+
+impl<'a, T: 'a> SpecFromIter<&'a T, slice::Iter<'a, T>> for Vec<T>
+where
+ T: Copy,
+{
+ // reuses the extend specialization for T: Copy
+ fn from_iter(iterator: slice::Iter<'a, T>) -> Self {
+ let mut vec = Vec::new();
+ // must delegate to spec_extend() since extend() itself delegates
+ // to spec_from for empty Vecs
+ vec.spec_extend(iterator);
+ vec
}
}
}
}
+impl<T> SpecExtend<T, IntoIter<T>> for Vec<T> {
+ fn spec_extend(&mut self, mut iterator: IntoIter<T>) {
+ unsafe {
+ self.append_elements(iterator.as_slice() as _);
+ }
+ iterator.ptr = iterator.end;
+ }
+}
+
impl<'a, T: 'a, I> SpecExtend<&'a T, I> for Vec<T>
where
I: Iterator<Item = &'a T>,
{
fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) {
let slice = iterator.as_slice();
- self.reserve(slice.len());
- unsafe {
- let len = self.len();
- let dst_slice = slice::from_raw_parts_mut(self.as_mut_ptr().add(len), slice.len());
- dst_slice.copy_from_slice(slice);
- self.set_len(len + slice.len());
- }
+ unsafe { self.append_elements(slice) };
}
}
impl<T> Vec<T> {
+ // leaf method to which various SpecFrom/SpecExtend implementations delegate when
+ // they have no further optimizations to apply
fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) {
// This is the case for a general iterator.
//
}
}
+#[stable(feature = "array_try_from_vec", since = "1.48.0")]
+impl<T, const N: usize> TryFrom<Vec<T>> for [T; N] {
+ type Error = Vec<T>;
+
+ /// Gets the entire contents of the `Vec<T>` as an array,
+ /// if its size exactly matches that of the requested array.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::convert::TryInto;
+ /// assert_eq!(vec![1, 2, 3].try_into(), Ok([1, 2, 3]));
+ /// assert_eq!(<Vec<i32>>::new().try_into(), Ok([]));
+ /// ```
+ ///
+ /// If the length doesn't match, the input comes back in `Err`:
+ /// ```
+ /// use std::convert::TryInto;
+ /// let r: Result<[i32; 4], _> = (0..10).collect::<Vec<_>>().try_into();
+ /// assert_eq!(r, Err(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]));
+ /// ```
+ ///
+ /// If you're fine with just getting a prefix of the `Vec<T>`,
+ /// you can call [`.truncate(N)`](Vec::truncate) first.
+ /// ```
+ /// use std::convert::TryInto;
+ /// let mut v = String::from("hello world").into_bytes();
+ /// v.sort();
+ /// v.truncate(2);
+ /// let [a, b]: [_; 2] = v.try_into().unwrap();
+ /// assert_eq!(a, b' ');
+ /// assert_eq!(b, b'd');
+ /// ```
+ fn try_from(mut vec: Vec<T>) -> Result<[T; N], Vec<T>> {
+ if vec.len() != N {
+ return Err(vec);
+ }
+
+ // SAFETY: `.set_len(0)` is always sound.
+ unsafe { vec.set_len(0) };
+
+ // SAFETY: A `Vec`'s pointer is always aligned property, and
+ // the alignment the array needs is the same as the items.
+ // We checked earlier that we have sufficient items.
+ // The items will not double-drop as the `set_len`
+ // tells the `Vec` not to also drop them.
+ let array = unsafe { ptr::read(vec.as_ptr() as *const [T; N]) };
+ Ok(array)
+ }
+}
+
////////////////////////////////////////////////////////////////////////////////
// Clone-on-write
////////////////////////////////////////////////////////////////////////////////
fn as_raw_mut_slice(&mut self) -> *mut [T] {
ptr::slice_from_raw_parts_mut(self.ptr as *mut T, self.len())
}
+
+ fn drop_remaining(&mut self) {
+ if mem::needs_drop::<T>() {
+ unsafe {
+ ptr::drop_in_place(self.as_mut_slice());
+ }
+ }
+ self.ptr = self.end;
+ }
+
+ /// Relinquishes the backing allocation, equivalent to
+ /// `ptr::write(&mut self, Vec::new().into_iter())`
+ fn forget_allocation(&mut self) {
+ self.cap = 0;
+ self.buf = unsafe { NonNull::new_unchecked(RawVec::NEW.ptr()) };
+ self.ptr = self.buf.as_ptr();
+ self.end = self.buf.as_ptr();
+ }
}
#[stable(feature = "vec_intoiter_as_ref", since = "1.46.0")]
fn count(self) -> usize {
self.len()
}
+
+ unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item
+ where
+ Self: TrustedRandomAccess,
+ {
+ // SAFETY: the caller must uphold the contract for
+ // `Iterator::get_unchecked`.
+ unsafe {
+ if mem::size_of::<T>() == 0 { mem::zeroed() } else { ptr::read(self.ptr.add(i)) }
+ }
+ }
}
#[stable(feature = "rust1", since = "1.0.0")]
#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<T> TrustedLen for IntoIter<T> {}
+#[doc(hidden)]
+#[unstable(issue = "none", feature = "std_internals")]
+// T: Copy as approximation for !Drop since get_unchecked does not advance self.ptr
+// and thus we can't implement drop-handling
+unsafe impl<T> TrustedRandomAccess for IntoIter<T>
+where
+ T: Copy,
+{
+ fn may_have_side_effect() -> bool {
+ false
+ }
+}
+
#[stable(feature = "vec_into_iter_clone", since = "1.8.0")]
impl<T: Clone> Clone for IntoIter<T> {
fn clone(&self) -> IntoIter<T> {
}
}
-#[unstable(issue = "0", feature = "inplace_iteration")]
+#[unstable(issue = "none", feature = "inplace_iteration")]
unsafe impl<T> InPlaceIterable for IntoIter<T> {}
-#[unstable(issue = "0", feature = "inplace_iteration")]
+#[unstable(issue = "none", feature = "inplace_iteration")]
unsafe impl<T> SourceIter for IntoIter<T> {
type Source = IntoIter<T>;
#[inline]
- fn as_inner(&mut self) -> &mut Self::Source {
+ unsafe fn as_inner(&mut self) -> &mut Self::Source {
+ self
+ }
+}
+
+// internal helper trait for in-place iteration specialization.
+#[rustc_specialization_trait]
+pub(crate) trait AsIntoIter {
+ type Item;
+ fn as_into_iter(&mut self) -> &mut IntoIter<Self::Item>;
+}
+
+impl<T> AsIntoIter for IntoIter<T> {
+ type Item = T;
+
+ fn as_into_iter(&mut self) -> &mut IntoIter<Self::Item> {
self
}
}