1 //! Inplace iterate-and-collect specialization for `Vec`
3 //! Note: This documents Vec internals, some of the following sections explain implementation
4 //! details and are best read together with the source of this module.
6 //! The specialization in this module applies to iterators in the shape of
7 //! `source.adapter().adapter().adapter().collect::<Vec<U>>()`
8 //! where `source` is an owning iterator obtained from [`Vec<T>`], [`Box<[T]>`][box] (by conversion to `Vec`)
9 //! or [`BinaryHeap<T>`], the adapters each consume one or more items per step
10 //! (represented by [`InPlaceIterable`]), provide transitive access to `source` (via [`SourceIter`])
11 //! and thus the underlying allocation. And finally the layouts of `T` and `U` must
12 //! have the same size and alignment, this is currently ensured via const eval instead of trait bounds
13 //! in the specialized [`SpecFromIter`] implementation.
15 //! [`BinaryHeap<T>`]: crate::collections::BinaryHeap
16 //! [box]: crate::boxed::Box
18 //! By extension some other collections which use `collect::<Vec<_>>()` internally in their
19 //! `FromIterator` implementation benefit from this too.
21 //! Access to the underlying source goes through a further layer of indirection via the private
22 //! trait [`AsVecIntoIter`] to hide the implementation detail that other collections may use
23 //! `vec::IntoIter` internally.
25 //! In-place iteration depends on the interaction of several unsafe traits, implementation
26 //! details of multiple parts in the iterator pipeline and often requires holistic reasoning
27 //! across multiple structs since iterators are executed cooperatively rather than having
28 //! a central evaluator/visitor struct executing all iterator components.
30 //! # Reading from and writing to the same allocation
32 //! By its nature collecting in place means that the reader and writer side of the iterator
33 //! use the same allocation. Since `try_fold()` (used in [`SpecInPlaceCollect`]) takes a
34 //! reference to the iterator for the duration of the iteration that means we can't interleave
35 //! the step of reading a value and getting a reference to write to. Instead raw pointers must be
36 //! used on the reader and writer side.
38 //! That writes never clobber a yet-to-be-read item is ensured by the [`InPlaceIterable`] requirements.
40 //! # Layout constraints
42 //! [`Allocator`] requires that `allocate()` and `deallocate()` have matching alignment and size.
43 //! Additionally this specialization doesn't make sense for ZSTs as there is no reallocation to
44 //! avoid and it would make pointer arithmetic more difficult.
46 //! [`Allocator`]: core::alloc::Allocator
48 //! # Drop- and panic-safety
50 //! Iteration can panic, requiring dropping the already written parts but also the remainder of
51 //! the source. Iteration can also leave some source items unconsumed which must be dropped.
52 //! All those drops in turn can panic which then must either leak the allocation or abort to avoid
55 //! This is handled by the [`InPlaceDrop`] guard for sink items (`U`) and by
56 //! [`vec::IntoIter::forget_allocation_drop_remaining()`] for remaining source items (`T`).
58 //! If dropping any remaining source item (`T`) panics then [`InPlaceDstBufDrop`] will handle dropping
59 //! the already collected sink items (`U`) and freeing the allocation.
61 //! [`vec::IntoIter::forget_allocation_drop_remaining()`]: super::IntoIter::forget_allocation_drop_remaining()
65 //! The main iteration itself is further specialized when the iterator implements
66 //! [`TrustedRandomAccessNoCoerce`] to let the optimizer see that it is a counted loop with a single
67 //! [induction variable]. This can turn some iterators into a noop, i.e. it reduces them from O(n) to
68 //! O(1). This particular optimization is quite fickle and doesn't always work, see [#79308]
70 //! [#79308]: https://github.com/rust-lang/rust/issues/79308
71 //! [induction variable]: https://en.wikipedia.org/wiki/Induction_variable
73 //! Since unchecked accesses through that trait do not advance the read pointer of `IntoIter`
74 //! this would interact unsoundly with the requirements about dropping the tail described above.
75 //! But since the normal `Drop` implementation of `IntoIter` would suffer from the same problem it
76 //! is only correct for `TrustedRandomAccessNoCoerce` to be implemented when the items don't
77 //! have a destructor. Thus that implicit requirement also makes the specialization safe to use for
78 //! in-place collection.
79 //! Note that this safety concern is about the correctness of `impl Drop for IntoIter`,
80 //! not the guarantees of `InPlaceIterable`.
82 //! # Adapter implementations
84 //! The invariants for adapters are documented in [`SourceIter`] and [`InPlaceIterable`], but
85 //! getting them right can be rather subtle for multiple, sometimes non-local reasons.
86 //! For example `InPlaceIterable` would be valid to implement for [`Peekable`], except
87 //! that it is stateful, cloneable and `IntoIter`'s clone implementation shortens the underlying
88 //! allocation which means if the iterator has been peeked and then gets cloned there no longer is
89 //! enough room, thus breaking an invariant ([#85322]).
91 //! [#85322]: https://github.com/rust-lang/rust/issues/85322
92 //! [`Peekable`]: core::iter::Peekable
97 //! Some cases that are optimized by this specialization, more can be found in the `Vec`
101 //! # #[allow(dead_code)]
102 //! /// Converts a usize vec into an isize one.
103 //! pub fn cast(vec: Vec<usize>) -> Vec<isize> {
104 //! // Does not allocate, free or panic. On optlevel>=2 it does not loop.
105 //! // Of course this particular case could and should be written with `into_raw_parts` and
106 //! // `from_raw_parts` instead.
107 //! vec.into_iter().map(|u| u as isize).collect()
112 //! # #[allow(dead_code)]
113 //! /// Drops remaining items in `src` and if the layouts of `T` and `U` match it
114 //! /// returns an empty Vec backed by the original allocation. Otherwise it returns a new
116 //! pub fn recycle_allocation<T, U>(src: Vec<T>) -> Vec<U> {
117 //! src.into_iter().filter_map(|_| None).collect()
122 //! let vec = vec![13usize; 1024];
123 //! let _ = vec.into_iter()
125 //! .filter_map(|(idx, val)| if idx % 2 == 0 { Some(val+idx) } else {None})
126 //! .collect::<Vec<_>>();
128 //! // is equivalent to the following, but doesn't require bounds checks
130 //! let mut vec = vec![13usize; 1024];
131 //! let mut write_idx = 0;
132 //! for idx in 0..vec.len() {
133 //! if idx % 2 == 0 {
134 //! vec[write_idx] = vec[idx] + idx;
138 //! vec.truncate(write_idx);
140 use core
::iter
::{InPlaceIterable, SourceIter, TrustedRandomAccessNoCoerce}
;
141 use core
::mem
::{self, ManuallyDrop, SizedTypeProperties}
;
142 use core
::ptr
::{self}
;
144 use super::{InPlaceDrop, InPlaceDstBufDrop, SpecFromIter, SpecFromIterNested, Vec}
;
146 /// Specialization marker for collecting an iterator pipeline into a Vec while reusing the
147 /// source allocation, i.e. executing the pipeline in place.
148 #[rustc_unsafe_specialization_marker]
149 pub(super) trait InPlaceIterableMarker {}
151 impl<T
> InPlaceIterableMarker
for T
where T
: InPlaceIterable {}
153 impl<T
, I
> SpecFromIter
<T
, I
> for Vec
<T
>
155 I
: Iterator
<Item
= T
> + SourceIter
<Source
: AsVecIntoIter
> + InPlaceIterableMarker
,
157 default fn from_iter(mut iterator
: I
) -> Self {
158 // See "Layout constraints" section in the module documentation. We rely on const
159 // optimization here since these conditions currently cannot be expressed as trait bounds
161 || mem
::size_of
::<T
>()
162 != mem
::size_of
::<<<I
as SourceIter
>::Source
as AsVecIntoIter
>::Item
>()
163 || mem
::align_of
::<T
>()
164 != mem
::align_of
::<<<I
as SourceIter
>::Source
as AsVecIntoIter
>::Item
>()
166 // fallback to more generic implementations
167 return SpecFromIterNested
::from_iter(iterator
);
170 let (src_buf
, src_ptr
, dst_buf
, dst_end
, cap
) = unsafe {
171 let inner
= iterator
.as_inner().as_into_iter();
175 inner
.buf
.as_ptr() as *mut T
,
176 inner
.end
as *const T
,
181 let len
= SpecInPlaceCollect
::collect_in_place(&mut iterator
, dst_buf
, dst_end
);
183 let src
= unsafe { iterator.as_inner().as_into_iter() }
;
184 // check if SourceIter contract was upheld
185 // caveat: if they weren't we might not even make it to this point
186 debug_assert_eq
!(src_buf
, src
.buf
.as_ptr());
187 // check InPlaceIterable contract. This is only possible if the iterator advanced the
188 // source pointer at all. If it uses unchecked access via TrustedRandomAccess
189 // then the source pointer will stay in its initial position and we can't use it as reference
190 if src
.ptr
!= src_ptr
{
192 unsafe { dst_buf.add(len) as *const _ }
<= src
.ptr
,
193 "InPlaceIterable contract violation, write pointer advanced beyond read pointer"
197 // The ownership of the allocation and the new `T` values is temporarily moved into `dst_guard`.
198 // This is safe because `forget_allocation_drop_remaining` immediately forgets the allocation
199 // before any panic can occur in order to avoid any double free, and then proceeds to drop
200 // any remaining values at the tail of the source.
202 // Note: This access to the source wouldn't be allowed by the TrustedRandomIteratorNoCoerce
203 // contract (used by SpecInPlaceCollect below). But see the "O(1) collect" section in the
204 // module documenttation why this is ok anyway.
205 let dst_guard
= InPlaceDstBufDrop { ptr: dst_buf, len, cap }
;
206 src
.forget_allocation_drop_remaining();
207 mem
::forget(dst_guard
);
209 let vec
= unsafe { Vec::from_raw_parts(dst_buf, len, cap) }
;
215 fn write_in_place_with_drop
<T
>(
217 ) -> impl FnMut(InPlaceDrop
<T
>, T
) -> Result
<InPlaceDrop
<T
>, !> {
218 move |mut sink
, item
| {
220 // the InPlaceIterable contract cannot be verified precisely here since
221 // try_fold has an exclusive reference to the source pointer
222 // all we can do is check if it's still in range
223 debug_assert
!(sink
.dst
as *const _
<= src_end
, "InPlaceIterable contract violation");
224 ptr
::write(sink
.dst
, item
);
225 // Since this executes user code which can panic we have to bump the pointer
227 sink
.dst
= sink
.dst
.add(1);
233 /// Helper trait to hold specialized implementations of the in-place iterate-collect loop
234 trait SpecInPlaceCollect
<T
, I
>: Iterator
<Item
= T
> {
235 /// Collects an iterator (`self`) into the destination buffer (`dst`) and returns the number of items
236 /// collected. `end` is the last writable element of the allocation and used for bounds checks.
238 /// This method is specialized and one of its implementations makes use of
239 /// `Iterator::__iterator_get_unchecked` calls with a `TrustedRandomAccessNoCoerce` bound
240 /// on `I` which means the caller of this method must take the safety conditions
241 /// of that trait into consideration.
242 fn collect_in_place(&mut self, dst
: *mut T
, end
: *const T
) -> usize;
245 impl<T
, I
> SpecInPlaceCollect
<T
, I
> for I
247 I
: Iterator
<Item
= T
>,
250 default fn collect_in_place(&mut self, dst_buf
: *mut T
, end
: *const T
) -> usize {
251 // use try-fold since
252 // - it vectorizes better for some iterator adapters
253 // - unlike most internal iteration methods, it only takes a &mut self
254 // - it lets us thread the write pointer through its innards and get it back in the end
255 let sink
= InPlaceDrop { inner: dst_buf, dst: dst_buf }
;
257 self.try_fold
::<_
, _
, Result
<_
, !>>(sink
, write_in_place_with_drop(end
)).unwrap();
258 // iteration succeeded, don't drop head
259 unsafe { ManuallyDrop::new(sink).dst.sub_ptr(dst_buf) }
263 impl<T
, I
> SpecInPlaceCollect
<T
, I
> for I
265 I
: Iterator
<Item
= T
> + TrustedRandomAccessNoCoerce
,
268 fn collect_in_place(&mut self, dst_buf
: *mut T
, end
: *const T
) -> usize {
269 let len
= self.size();
270 let mut drop_guard
= InPlaceDrop { inner: dst_buf, dst: dst_buf }
;
272 // Safety: InplaceIterable contract guarantees that for every element we read
273 // one slot in the underlying storage will have been freed up and we can immediately
274 // write back the result.
276 let dst
= dst_buf
.add(i
);
277 debug_assert
!(dst
as *const _
<= end
, "InPlaceIterable contract violation");
278 ptr
::write(dst
, self.__iterator_get_unchecked(i
));
279 // Since this executes user code which can panic we have to bump the pointer
281 drop_guard
.dst
= dst
.add(1);
284 mem
::forget(drop_guard
);
289 /// Internal helper trait for in-place iteration specialization.
291 /// Currently this is only implemented by [`vec::IntoIter`] - returning a reference to itself - and
292 /// [`binary_heap::IntoIter`] which returns a reference to its inner representation.
294 /// Since this is an internal trait it hides the implementation detail `binary_heap::IntoIter`
295 /// uses `vec::IntoIter` internally.
297 /// [`vec::IntoIter`]: super::IntoIter
298 /// [`binary_heap::IntoIter`]: crate::collections::binary_heap::IntoIter
302 /// In-place iteration relies on implementation details of `vec::IntoIter`, most importantly that
303 /// it does not create references to the whole allocation during iteration, only raw pointers
304 #[rustc_specialization_trait]
305 pub(crate) unsafe trait AsVecIntoIter
{
307 fn as_into_iter(&mut self) -> &mut super::IntoIter
<Self::Item
>;