aarch64/usr/lib/rustlib/src/rust/library/alloc/src/vec/in_place_collect.rs - manifest_repos/toolchain - Git at Google

 //! Inplace iterate-and-collect specialization for `Vec`
 //!
 //! Note: This documents Vec internals, some of the following sections explain implementation
 //! details and are best read together with the source of this module.
 //!
 //! The specialization in this module applies to iterators in the shape of
 //! `source.adapter().adapter().adapter().collect::<Vec<U>>()`
 //! where `source` is an owning iterator obtained from [`Vec<T>`], [`Box<[T]>`][box] (by conversion to `Vec`)
 //! or [`BinaryHeap<T>`], the adapters each consume one or more items per step
 //! (represented by [`InPlaceIterable`]), provide transitive access to `source` (via [`SourceIter`])
 //! and thus the underlying allocation. And finally the layouts of `T` and `U` must
 //! have the same size and alignment, this is currently ensured via const eval instead of trait bounds
 //! in the specialized [`SpecFromIter`] implementation.
 //!
 //! [`BinaryHeap<T>`]: crate::collections::BinaryHeap
 //! [box]: crate::boxed::Box
 //!
 //! By extension some other collections which use `collect::<Vec<_>>()` internally in their
 //! `FromIterator` implementation benefit from this too.
 //!
 //! Access to the underlying source goes through a further layer of indirection via the private
 //! trait [`AsVecIntoIter`] to hide the implementation detail that other collections may use
 //! `vec::IntoIter` internally.
 //!
 //! In-place iteration depends on the interaction of several unsafe traits, implementation
 //! details of multiple parts in the iterator pipeline and often requires holistic reasoning
 //! across multiple structs since iterators are executed cooperatively rather than having
 //! a central evaluator/visitor struct executing all iterator components.
 //!
 //! # Reading from and writing to the same allocation
 //!
 //! By its nature collecting in place means that the reader and writer side of the iterator
 //! use the same allocation. Since `try_fold()` (used in [`SpecInPlaceCollect`]) takes a
 //! reference to the iterator for the duration of the iteration that means we can't interleave
 //! the step of reading a value and getting a reference to write to. Instead raw pointers must be
 //! used on the reader and writer side.
 //!
 //! That writes never clobber a yet-to-be-read item is ensured by the [`InPlaceIterable`] requirements.
 //!
 //! # Layout constraints
 //!
 //! [`Allocator`] requires that `allocate()` and `deallocate()` have matching alignment and size.
 //! Additionally this specialization doesn't make sense for ZSTs as there is no reallocation to
 //! avoid and it would make pointer arithmetic more difficult.
 //!
 //! [`Allocator`]: core::alloc::Allocator
 //!
 //! # Drop- and panic-safety
 //!
 //! Iteration can panic, requiring dropping the already written parts but also the remainder of
 //! the source. Iteration can also leave some source items unconsumed which must be dropped.
 //! All those drops in turn can panic which then must either leak the allocation or abort to avoid
 //! double-drops.
 //!
 //! This is handled by the [`InPlaceDrop`] guard for sink items (`U`) and by
 //! [`vec::IntoIter::forget_allocation_drop_remaining()`] for remaining source items (`T`).
 //!
 //! If dropping any remaining source item (`T`) panics then [`InPlaceDstBufDrop`] will handle dropping
 //! the already collected sink items (`U`) and freeing the allocation.
 //!
 //! [`vec::IntoIter::forget_allocation_drop_remaining()`]: super::IntoIter::forget_allocation_drop_remaining()
 //!
 //! # O(1) collect
 //!
 //! The main iteration itself is further specialized when the iterator implements
 //! [`TrustedRandomAccessNoCoerce`] to let the optimizer see that it is a counted loop with a single
 //! [induction variable]. This can turn some iterators into a noop, i.e. it reduces them from O(n) to
 //! O(1). This particular optimization is quite fickle and doesn't always work, see [#79308]
 //!
 //! [#79308]: https://github.com/rust-lang/rust/issues/79308
 //! [induction variable]: https://en.wikipedia.org/wiki/Induction_variable
 //!
 //! Since unchecked accesses through that trait do not advance the read pointer of `IntoIter`
 //! this would interact unsoundly with the requirements about dropping the tail described above.
 //! But since the normal `Drop` implementation of `IntoIter` would suffer from the same problem it
 //! is only correct for `TrustedRandomAccessNoCoerce` to be implemented when the items don't
 //! have a destructor. Thus that implicit requirement also makes the specialization safe to use for
 //! in-place collection.
 //! Note that this safety concern is about the correctness of `impl Drop for IntoIter`,
 //! not the guarantees of `InPlaceIterable`.
 //!
 //! # Adapter implementations
 //!
 //! The invariants for adapters are documented in [`SourceIter`] and [`InPlaceIterable`], but
 //! getting them right can be rather subtle for multiple, sometimes non-local reasons.
 //! For example `InPlaceIterable` would be valid to implement for [`Peekable`], except
 //! that it is stateful, cloneable and `IntoIter`'s clone implementation shortens the underlying
 //! allocation which means if the iterator has been peeked and then gets cloned there no longer is
 //! enough room, thus breaking an invariant ([#85322]).
 //!
 //! [#85322]: https://github.com/rust-lang/rust/issues/85322
 //! [`Peekable`]: core::iter::Peekable
 //!
 //!
 //! # Examples
 //!
 //! Some cases that are optimized by this specialization, more can be found in the `Vec`
 //! benchmarks:
 //!
 //! ```rust
 //! # #[allow(dead_code)]
 //! /// Converts a usize vec into an isize one.
 //! pub fn cast(vec: Vec<usize>) -> Vec<isize> {
 //!   // Does not allocate, free or panic. On optlevel>=2 it does not loop.
 //!   // Of course this particular case could and should be written with `into_raw_parts` and
 //!   // `from_raw_parts` instead.
 //!   vec.into_iter().map(|u| u as isize).collect()
 //! }
 //! ```
 //!
 //! ```rust
 //! # #[allow(dead_code)]
 //! /// Drops remaining items in `src` and if the layouts of `T` and `U` match it
 //! /// returns an empty Vec backed by the original allocation. Otherwise it returns a new
 //! /// empty vec.
 //! pub fn recycle_allocation<T, U>(src: Vec<T>) -> Vec<U> {
 //!   src.into_iter().filter_map(|_| None).collect()
 //! }
 //! ```
 //!
 //! ```rust
 //! let vec = vec![13usize; 1024];
 //! let _ = vec.into_iter()
 //!   .enumerate()
 //!   .filter_map(|(idx, val)| if idx % 2 == 0 { Some(val+idx) } else {None})
 //!   .collect::<Vec<_>>();
 //!
 //! // is equivalent to the following, but doesn't require bounds checks
 //!
 //! let mut vec = vec![13usize; 1024];
 //! let mut write_idx = 0;
 //! for idx in 0..vec.len() {
 //!    if idx % 2 == 0 {
 //!       vec[write_idx] = vec[idx] + idx;
 //!       write_idx += 1;
 //!    }
 //! }
 //! vec.truncate(write_idx);
 //! ```
 use core::iter::{InPlaceIterable, SourceIter, TrustedRandomAccessNoCoerce};
 use core::mem::{self, ManuallyDrop, SizedTypeProperties};
 use core::ptr::{self};

 use super::{InPlaceDrop, InPlaceDstBufDrop, SpecFromIter, SpecFromIterNested, Vec};

 /// Specialization marker for collecting an iterator pipeline into a Vec while reusing the
 /// source allocation, i.e. executing the pipeline in place.
 #[rustc_unsafe_specialization_marker]
 pub(super) trait InPlaceIterableMarker {}

 impl<T> InPlaceIterableMarker for T where T: InPlaceIterable {}

 impl<T, I> SpecFromIter<T, I> for Vec<T>
 where
     I: Iterator<Item = T> + SourceIter<Source: AsVecIntoIter> + InPlaceIterableMarker,
 {
     default fn from_iter(mut iterator: I) -> Self {
         // See "Layout constraints" section in the module documentation. We rely on const
         // optimization here since these conditions currently cannot be expressed as trait bounds
         if T::IS_ZST
             || mem::size_of::<T>()
                 != mem::size_of::<<<I as SourceIter>::Source as AsVecIntoIter>::Item>()
             || mem::align_of::<T>()
                 != mem::align_of::<<<I as SourceIter>::Source as AsVecIntoIter>::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,
             )
         };

         let len = SpecInPlaceCollect::collect_in_place(&mut iterator, dst_buf, dst_end);

         let src = unsafe { iterator.as_inner().as_into_iter() };
         // check if SourceIter contract was upheld
         // caveat: if they weren't we might 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!(
                 unsafe { dst_buf.add(len) as *const _ } <= src.ptr,
                 "InPlaceIterable contract violation, write pointer advanced beyond read pointer"
             );
         }

         // The ownership of the allocation and the new `T` values is temporarily moved into `dst_guard`.
         // This is safe because `forget_allocation_drop_remaining` immediately forgets the allocation
         // before any panic can occur in order to avoid any double free, and then proceeds to drop
         // any remaining values at the tail of the source.
         //
         // Note: This access to the source wouldn't be allowed by the TrustedRandomIteratorNoCoerce
         // contract (used by SpecInPlaceCollect below). But see the "O(1) collect" section in the
         // module documenttation why this is ok anyway.
         let dst_guard = InPlaceDstBufDrop { ptr: dst_buf, len, cap };
         src.forget_allocation_drop_remaining();
         mem::forget(dst_guard);

         let vec = unsafe { Vec::from_raw_parts(dst_buf, len, cap) };

         vec
     }
 }

 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);
             // Since this executes user code which can panic we have to bump the pointer
             // after each step.
             sink.dst = sink.dst.add(1);
         }
         Ok(sink)
     }
 }

 /// Helper trait to hold specialized implementations of the in-place iterate-collect loop
 trait SpecInPlaceCollect<T, I>: Iterator<Item = T> {
     /// Collects an iterator (`self`) into the destination buffer (`dst`) and returns the number of items
     /// collected. `end` is the last writable element of the allocation and used for bounds checks.
     ///
     /// This method is specialized and one of its implementations makes use of
     /// `Iterator::__iterator_get_unchecked` calls with a `TrustedRandomAccessNoCoerce` bound
     /// on `I` which means the caller of this method must take the safety conditions
     /// of that trait into consideration.
     fn collect_in_place(&mut self, dst: *mut T, end: *const T) -> usize;
 }

 impl<T, I> SpecInPlaceCollect<T, I> for I
 where
     I: Iterator<Item = T>,
 {
     #[inline]
     default fn collect_in_place(&mut self, dst_buf: *mut T, end: *const T) -> usize {
         // use try-fold since
         // - it vectorizes better for some iterator adapters
         // - unlike most internal iteration 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 =
             self.try_fold::<_, _, Result<_, !>>(sink, write_in_place_with_drop(end)).unwrap();
         // iteration succeeded, don't drop head
         unsafe { ManuallyDrop::new(sink).dst.sub_ptr(dst_buf) }
     }
 }

 impl<T, I> SpecInPlaceCollect<T, I> for I
 where
     I: Iterator<Item = T> + TrustedRandomAccessNoCoerce,
 {
     #[inline]
     fn collect_in_place(&mut self, dst_buf: *mut T, end: *const T) -> usize {
         let len = self.size();
         let mut drop_guard = InPlaceDrop { inner: dst_buf, dst: dst_buf };
         for i in 0..len {
             // Safety: InplaceIterable contract guarantees that for every element we read
             // one slot in the underlying storage will have been freed up and we can immediately
             // write back the result.
             unsafe {
                 let dst = dst_buf.add(i);
                 debug_assert!(dst as *const _ <= end, "InPlaceIterable contract violation");
                 ptr::write(dst, self.__iterator_get_unchecked(i));
                 // Since this executes user code which can panic we have to bump the pointer
                 // after each step.
                 drop_guard.dst = dst.add(1);
             }
         }
         mem::forget(drop_guard);
         len
     }
 }

 /// Internal helper trait for in-place iteration specialization.
 ///
 /// Currently this is only implemented by [`vec::IntoIter`] - returning a reference to itself - and
 /// [`binary_heap::IntoIter`] which returns a reference to its inner representation.
 ///
 /// Since this is an internal trait it hides the implementation detail `binary_heap::IntoIter`
 /// uses `vec::IntoIter` internally.
 ///
 /// [`vec::IntoIter`]: super::IntoIter
 /// [`binary_heap::IntoIter`]: crate::collections::binary_heap::IntoIter
 ///
 /// # Safety
 ///
 /// In-place iteration relies on implementation details of `vec::IntoIter`, most importantly that
 /// it does not create references to the whole allocation during iteration, only raw pointers
 #[rustc_specialization_trait]
 pub(crate) unsafe trait AsVecIntoIter {
     type Item;
     fn as_into_iter(&mut self) -> &mut super::IntoIter<Self::Item>;
 }
	//! Inplace iterate-and-collect specialization for `Vec`
	//!
	//! Note: This documents Vec internals, some of the following sections explain implementation
	//! details and are best read together with the source of this module.
	//!
	//! The specialization in this module applies to iterators in the shape of
	//! `source.adapter().adapter().adapter().collect::<Vec<U>>()`
	//! where `source` is an owning iterator obtained from [`Vec<T>`], [`Box<[T]>`][box] (by conversion to `Vec`)
	//! or [`BinaryHeap<T>`], the adapters each consume one or more items per step
	//! (represented by [`InPlaceIterable`]), provide transitive access to `source` (via [`SourceIter`])
	//! and thus the underlying allocation. And finally the layouts of `T` and `U` must
	//! have the same size and alignment, this is currently ensured via const eval instead of trait bounds
	//! in the specialized [`SpecFromIter`] implementation.
	//!
	//! [`BinaryHeap<T>`]: crate::collections::BinaryHeap
	//! [box]: crate::boxed::Box
	//!
	//! By extension some other collections which use `collect::<Vec<_>>()` internally in their
	//! `FromIterator` implementation benefit from this too.
	//!
	//! Access to the underlying source goes through a further layer of indirection via the private
	//! trait [`AsVecIntoIter`] to hide the implementation detail that other collections may use
	//! `vec::IntoIter` internally.
	//!
	//! In-place iteration depends on the interaction of several unsafe traits, implementation
	//! details of multiple parts in the iterator pipeline and often requires holistic reasoning
	//! across multiple structs since iterators are executed cooperatively rather than having
	//! a central evaluator/visitor struct executing all iterator components.
	//!
	//! # Reading from and writing to the same allocation
	//!
	//! By its nature collecting in place means that the reader and writer side of the iterator
	//! use the same allocation. Since `try_fold()` (used in [`SpecInPlaceCollect`]) takes a
	//! reference to the iterator for the duration of the iteration that means we can't interleave
	//! the step of reading a value and getting a reference to write to. Instead raw pointers must be
	//! used on the reader and writer side.
	//!
	//! That writes never clobber a yet-to-be-read item is ensured by the [`InPlaceIterable`] requirements.
	//!
	//! # Layout constraints
	//!
	//! [`Allocator`] requires that `allocate()` and `deallocate()` have matching alignment and size.
	//! Additionally this specialization doesn't make sense for ZSTs as there is no reallocation to
	//! avoid and it would make pointer arithmetic more difficult.
	//!
	//! [`Allocator`]: core::alloc::Allocator
	//!
	//! # Drop- and panic-safety
	//!
	//! Iteration can panic, requiring dropping the already written parts but also the remainder of
	//! the source. Iteration can also leave some source items unconsumed which must be dropped.
	//! All those drops in turn can panic which then must either leak the allocation or abort to avoid
	//! double-drops.
	//!
	//! This is handled by the [`InPlaceDrop`] guard for sink items (`U`) and by
	//! [`vec::IntoIter::forget_allocation_drop_remaining()`] for remaining source items (`T`).
	//!
	//! If dropping any remaining source item (`T`) panics then [`InPlaceDstBufDrop`] will handle dropping
	//! the already collected sink items (`U`) and freeing the allocation.
	//!
	//! [`vec::IntoIter::forget_allocation_drop_remaining()`]: super::IntoIter::forget_allocation_drop_remaining()
	//!
	//! # O(1) collect
	//!
	//! The main iteration itself is further specialized when the iterator implements
	//! [`TrustedRandomAccessNoCoerce`] to let the optimizer see that it is a counted loop with a single
	//! [induction variable]. This can turn some iterators into a noop, i.e. it reduces them from O(n) to
	//! O(1). This particular optimization is quite fickle and doesn't always work, see [#79308]
	//!
	//! [#79308]: https://github.com/rust-lang/rust/issues/79308
	//! [induction variable]: https://en.wikipedia.org/wiki/Induction_variable
	//!
	//! Since unchecked accesses through that trait do not advance the read pointer of `IntoIter`
	//! this would interact unsoundly with the requirements about dropping the tail described above.
	//! But since the normal `Drop` implementation of `IntoIter` would suffer from the same problem it
	//! is only correct for `TrustedRandomAccessNoCoerce` to be implemented when the items don't
	//! have a destructor. Thus that implicit requirement also makes the specialization safe to use for
	//! in-place collection.
	//! Note that this safety concern is about the correctness of `impl Drop for IntoIter`,
	//! not the guarantees of `InPlaceIterable`.
	//!
	//! # Adapter implementations
	//!
	//! The invariants for adapters are documented in [`SourceIter`] and [`InPlaceIterable`], but
	//! getting them right can be rather subtle for multiple, sometimes non-local reasons.
	//! For example `InPlaceIterable` would be valid to implement for [`Peekable`], except
	//! that it is stateful, cloneable and `IntoIter`'s clone implementation shortens the underlying
	//! allocation which means if the iterator has been peeked and then gets cloned there no longer is
	//! enough room, thus breaking an invariant ([#85322]).
	//!
	//! [#85322]: https://github.com/rust-lang/rust/issues/85322
	//! [`Peekable`]: core::iter::Peekable
	//!
	//!
	//! # Examples
	//!
	//! Some cases that are optimized by this specialization, more can be found in the `Vec`
	//! benchmarks:
	//!
	//! ```rust
	//! # #[allow(dead_code)]
	//! /// Converts a usize vec into an isize one.
	//! pub fn cast(vec: Vec<usize>) -> Vec<isize> {
	//! // Does not allocate, free or panic. On optlevel>=2 it does not loop.
	//! // Of course this particular case could and should be written with `into_raw_parts` and
	//! // `from_raw_parts` instead.
	//! vec.into_iter().map(\|u\| u as isize).collect()
	//! }
	//! ```
	//!
	//! ```rust
	//! # #[allow(dead_code)]
	//! /// Drops remaining items in `src` and if the layouts of `T` and `U` match it
	//! /// returns an empty Vec backed by the original allocation. Otherwise it returns a new
	//! /// empty vec.
	//! pub fn recycle_allocation<T, U>(src: Vec<T>) -> Vec<U> {
	//! src.into_iter().filter_map(\|_\| None).collect()
	//! }
	//! ```
	//!
	//! ```rust
	//! let vec = vec![13usize; 1024];
	//! let _ = vec.into_iter()
	//! .enumerate()
	//! .filter_map(\|(idx, val)\| if idx % 2 == 0 { Some(val+idx) } else {None})
	//! .collect::<Vec<_>>();
	//!
	//! // is equivalent to the following, but doesn't require bounds checks
	//!
	//! let mut vec = vec![13usize; 1024];
	//! let mut write_idx = 0;
	//! for idx in 0..vec.len() {
	//! if idx % 2 == 0 {
	//! vec[write_idx] = vec[idx] + idx;
	//! write_idx += 1;
	//! }
	//! }
	//! vec.truncate(write_idx);
	//! ```
	use core::iter::{InPlaceIterable, SourceIter, TrustedRandomAccessNoCoerce};
	use core::mem::{self, ManuallyDrop, SizedTypeProperties};
	use core::ptr::{self};

	use super::{InPlaceDrop, InPlaceDstBufDrop, SpecFromIter, SpecFromIterNested, Vec};

	/// Specialization marker for collecting an iterator pipeline into a Vec while reusing the
	/// source allocation, i.e. executing the pipeline in place.
	#[rustc_unsafe_specialization_marker]
	pub(super) trait InPlaceIterableMarker {}

	impl<T> InPlaceIterableMarker for T where T: InPlaceIterable {}

	impl<T, I> SpecFromIter<T, I> for Vec<T>
	where
	I: Iterator<Item = T> + SourceIter<Source: AsVecIntoIter> + InPlaceIterableMarker,
	{
	default fn from_iter(mut iterator: I) -> Self {
	// See "Layout constraints" section in the module documentation. We rely on const
	// optimization here since these conditions currently cannot be expressed as trait bounds
	if T::IS_ZST
	\|\| mem::size_of::<T>()
	!= mem::size_of::<<<I as SourceIter>::Source as AsVecIntoIter>::Item>()
	\|\| mem::align_of::<T>()
	!= mem::align_of::<<<I as SourceIter>::Source as AsVecIntoIter>::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,
	)
	};

	let len = SpecInPlaceCollect::collect_in_place(&mut iterator, dst_buf, dst_end);

	let src = unsafe { iterator.as_inner().as_into_iter() };
	// check if SourceIter contract was upheld
	// caveat: if they weren't we might 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!(
	unsafe { dst_buf.add(len) as *const _ } <= src.ptr,
	"InPlaceIterable contract violation, write pointer advanced beyond read pointer"
	);
	}

	// The ownership of the allocation and the new `T` values is temporarily moved into `dst_guard`.
	// This is safe because `forget_allocation_drop_remaining` immediately forgets the allocation
	// before any panic can occur in order to avoid any double free, and then proceeds to drop
	// any remaining values at the tail of the source.
	//
	// Note: This access to the source wouldn't be allowed by the TrustedRandomIteratorNoCoerce
	// contract (used by SpecInPlaceCollect below). But see the "O(1) collect" section in the
	// module documenttation why this is ok anyway.
	let dst_guard = InPlaceDstBufDrop { ptr: dst_buf, len, cap };
	src.forget_allocation_drop_remaining();
	mem::forget(dst_guard);

	let vec = unsafe { Vec::from_raw_parts(dst_buf, len, cap) };

	vec
	}
	}

	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);
	// Since this executes user code which can panic we have to bump the pointer
	// after each step.
	sink.dst = sink.dst.add(1);
	}
	Ok(sink)
	}
	}

	/// Helper trait to hold specialized implementations of the in-place iterate-collect loop
	trait SpecInPlaceCollect<T, I>: Iterator<Item = T> {
	/// Collects an iterator (`self`) into the destination buffer (`dst`) and returns the number of items
	/// collected. `end` is the last writable element of the allocation and used for bounds checks.
	///
	/// This method is specialized and one of its implementations makes use of
	/// `Iterator::__iterator_get_unchecked` calls with a `TrustedRandomAccessNoCoerce` bound
	/// on `I` which means the caller of this method must take the safety conditions
	/// of that trait into consideration.
	fn collect_in_place(&mut self, dst: mut T, end: const T) -> usize;
	}

	impl<T, I> SpecInPlaceCollect<T, I> for I
	where
	I: Iterator<Item = T>,
	{
	#[inline]
	default fn collect_in_place(&mut self, dst_buf: mut T, end: const T) -> usize {
	// use try-fold since
	// - it vectorizes better for some iterator adapters
	// - unlike most internal iteration 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 =
	self.try_fold::<_, _, Result<_, !>>(sink, write_in_place_with_drop(end)).unwrap();
	// iteration succeeded, don't drop head
	unsafe { ManuallyDrop::new(sink).dst.sub_ptr(dst_buf) }
	}
	}

	impl<T, I> SpecInPlaceCollect<T, I> for I
	where
	I: Iterator<Item = T> + TrustedRandomAccessNoCoerce,
	{
	#[inline]
	fn collect_in_place(&mut self, dst_buf: mut T, end: const T) -> usize {
	let len = self.size();
	let mut drop_guard = InPlaceDrop { inner: dst_buf, dst: dst_buf };
	for i in 0..len {
	// Safety: InplaceIterable contract guarantees that for every element we read
	// one slot in the underlying storage will have been freed up and we can immediately
	// write back the result.
	unsafe {
	let dst = dst_buf.add(i);
	debug_assert!(dst as *const _ <= end, "InPlaceIterable contract violation");
	ptr::write(dst, self.__iterator_get_unchecked(i));
	// Since this executes user code which can panic we have to bump the pointer
	// after each step.
	drop_guard.dst = dst.add(1);
	}
	}
	mem::forget(drop_guard);
	len
	}
	}

	/// Internal helper trait for in-place iteration specialization.
	///
	/// Currently this is only implemented by [`vec::IntoIter`] - returning a reference to itself - and
	/// [`binary_heap::IntoIter`] which returns a reference to its inner representation.
	///
	/// Since this is an internal trait it hides the implementation detail `binary_heap::IntoIter`
	/// uses `vec::IntoIter` internally.
	///
	/// [`vec::IntoIter`]: super::IntoIter
	/// [`binary_heap::IntoIter`]: crate::collections::binary_heap::IntoIter
	///
	/// # Safety
	///
	/// In-place iteration relies on implementation details of `vec::IntoIter`, most importantly that
	/// it does not create references to the whole allocation during iteration, only raw pointers
	#[rustc_specialization_trait]
	pub(crate) unsafe trait AsVecIntoIter {
	type Item;
	fn as_into_iter(&mut self) -> &mut super::IntoIter<Self::Item>;
	}