1use crate::iter::InPlaceIterable;
2use crate::num::NonZero;
3use crate::ops::{ChangeOutputType, ControlFlow, FromResidual, Residual, Try};
4
5mod array_chunks;
6mod by_ref_sized;
7mod chain;
8mod cloned;
9mod copied;
10mod cycle;
11mod enumerate;
12mod filter;
13mod filter_map;
14mod flatten;
15mod fuse;
16mod inspect;
17mod intersperse;
18mod map;
19mod map_while;
20mod map_windows;
21mod peekable;
22mod rev;
23mod scan;
24mod skip;
25mod skip_while;
26mod step_by;
27mod take;
28mod take_while;
29mod zip;
30
31#[stable(feature = "rust1", since = "1.0.0")]
32pub use self::{
33 chain::Chain, cycle::Cycle, enumerate::Enumerate, filter::Filter, filter_map::FilterMap,
34 flatten::FlatMap, fuse::Fuse, inspect::Inspect, map::Map, peekable::Peekable, rev::Rev,
35 scan::Scan, skip::Skip, skip_while::SkipWhile, take::Take, take_while::TakeWhile, zip::Zip,
36};
37
38#[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")]
39pub use self::array_chunks::ArrayChunks;
40
41#[unstable(feature = "std_internals", issue = "none")]
42pub use self::by_ref_sized::ByRefSized;
43
44#[stable(feature = "iter_cloned", since = "1.1.0")]
45pub use self::cloned::Cloned;
46
47#[stable(feature = "iterator_step_by", since = "1.28.0")]
48pub use self::step_by::StepBy;
49
50#[stable(feature = "iterator_flatten", since = "1.29.0")]
51pub use self::flatten::Flatten;
52
53#[stable(feature = "iter_copied", since = "1.36.0")]
54pub use self::copied::Copied;
55
56#[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
57pub use self::intersperse::{Intersperse, IntersperseWith};
58
59#[stable(feature = "iter_map_while", since = "1.57.0")]
60pub use self::map_while::MapWhile;
61
62#[unstable(feature = "iter_map_windows", reason = "recently added", issue = "87155")]
63pub use self::map_windows::MapWindows;
64
65#[unstable(feature = "trusted_random_access", issue = "none")]
66pub use self::zip::TrustedRandomAccess;
67
68#[unstable(feature = "trusted_random_access", issue = "none")]
69pub use self::zip::TrustedRandomAccessNoCoerce;
70
71#[stable(feature = "iter_zip", since = "1.59.0")]
72pub use self::zip::zip;
73
74/// This trait provides transitive access to source-stage in an iterator-adapter pipeline
75/// under the conditions that
76/// * the iterator source `S` itself implements `SourceIter<Source = S>`
77/// * there is a delegating implementation of this trait for each adapter in the pipeline between
78/// the source and the pipeline consumer.
79///
80/// When the source is an owning iterator struct (commonly called `IntoIter`) then
81/// this can be useful for specializing [`FromIterator`] implementations or recovering the
82/// remaining elements after an iterator has been partially exhausted.
83///
84/// Note that implementations do not necessarily have to provide access to the inner-most
85/// source of a pipeline. A stateful intermediate adapter might eagerly evaluate a part
86/// of the pipeline and expose its internal storage as source.
87///
88/// The trait is unsafe because implementers must uphold additional safety properties.
89/// See [`as_inner`] for details.
90///
91/// The primary use of this trait is in-place iteration. Refer to the [`vec::in_place_collect`]
92/// module documentation for more information.
93///
94/// [`vec::in_place_collect`]: ../../../../alloc/vec/in_place_collect/index.html
95///
96/// # Examples
97///
98/// Retrieving a partially consumed source:
99///
100/// ```
101/// # #![feature(inplace_iteration)]
102/// # use std::iter::SourceIter;
103///
104/// let mut iter = vec![9, 9, 9].into_iter().map(|i| i * i);
105/// let _ = iter.next();
106/// let mut remainder = std::mem::replace(unsafe { iter.as_inner() }, Vec::new().into_iter());
107/// println!("n = {} elements remaining", remainder.len());
108/// ```
109///
110/// [`FromIterator`]: crate::iter::FromIterator
111/// [`as_inner`]: SourceIter::as_inner
112#[unstable(issue = "none", feature = "inplace_iteration")]
113#[doc(hidden)]
114#[rustc_specialization_trait]
115pub unsafe trait SourceIter {
116 /// A source stage in an iterator pipeline.
117 type Source;
118
119 /// Retrieve the source of an iterator pipeline.
120 ///
121 /// # Safety
122 ///
123 /// Implementations must return the same mutable reference for their lifetime, unless
124 /// replaced by a caller.
125 ///
126 /// Callers may only replace the reference when they stopped iteration and drop the
127 /// iterator pipeline after extracting the source.
128 ///
129 /// This means iterator adapters can rely on the source not changing during
130 /// iteration but they cannot rely on it in their Drop implementations.
131 ///
132 /// Implementing this method means adapters relinquish private-only access to their
133 /// source and can only rely on guarantees made based on method receiver types.
134 /// The lack of restricted access also requires that adapters must uphold the source's
135 /// public API even when they have access to its internals.
136 ///
137 /// Callers in turn must expect the source to be in any state that is consistent with
138 /// its public API since adapters sitting between it and the source have the same
139 /// access. In particular an adapter may have consumed more elements than strictly necessary.
140 ///
141 /// The overall goal of these requirements is to let the consumer of a pipeline use
142 /// * whatever remains in the source after iteration has stopped
143 /// * the memory that has become unused by advancing a consuming iterator
144 ///
145 /// [`next()`]: Iterator::next()
146 unsafe fn as_inner(&mut self) -> &mut Self::Source;
147}
148
149/// An iterator adapter that produces output as long as the underlying
150/// iterator produces values where `Try::branch` says to `ControlFlow::Continue`.
151///
152/// If a `ControlFlow::Break` is encountered, the iterator stops and the
153/// residual is stored.
154pub(crate) struct GenericShunt<'a, I, R> {
155 iter: I,
156 residual: &'a mut Option<R>,
157}
158
159/// Process the given iterator as if it yielded a the item's `Try::Output`
160/// type instead. Any `Try::Residual`s encountered will stop the inner iterator
161/// and be propagated back to the overall result.
162pub(crate) fn try_process<I, T, R, F, U>(iter: I, mut f: F) -> ChangeOutputType<I::Item, U>
163where
164 I: Iterator<Item: Try<Output = T, Residual = R>>,
165 for<'a> F: FnMut(GenericShunt<'a, I, R>) -> U,
166 R: Residual<U>,
167{
168 let mut residual: Option = None;
169 let shunt: GenericShunt<'_, I, R> = GenericShunt { iter, residual: &mut residual };
170 let value: U = f(shunt);
171 match residual {
172 Some(r: R) => FromResidual::from_residual(r),
173 None => Try::from_output(value),
174 }
175}
176
177impl<I, R> Iterator for GenericShunt<'_, I, R>
178where
179 I: Iterator<Item: Try<Residual = R>>,
180{
181 type Item = <I::Item as Try>::Output;
182
183 fn next(&mut self) -> Option<Self::Item> {
184 self.try_for_each(ControlFlow::Break).break_value()
185 }
186
187 fn size_hint(&self) -> (usize, Option<usize>) {
188 if self.residual.is_some() {
189 (0, Some(0))
190 } else {
191 let (_, upper) = self.iter.size_hint();
192 (0, upper)
193 }
194 }
195
196 fn try_fold<B, F, T>(&mut self, init: B, mut f: F) -> T
197 where
198 F: FnMut(B, Self::Item) -> T,
199 T: Try<Output = B>,
200 {
201 self.iter
202 .try_fold(init, |acc, x| match Try::branch(x) {
203 ControlFlow::Continue(x) => ControlFlow::from_try(f(acc, x)),
204 ControlFlow::Break(r) => {
205 *self.residual = Some(r);
206 ControlFlow::Break(try { acc })
207 }
208 })
209 .into_try()
210 }
211
212 impl_fold_via_try_fold! { fold -> try_fold }
213}
214
215#[unstable(issue = "none", feature = "inplace_iteration")]
216unsafe impl<I, R> SourceIter for GenericShunt<'_, I, R>
217where
218 I: SourceIter,
219{
220 type Source = I::Source;
221
222 #[inline]
223 unsafe fn as_inner(&mut self) -> &mut Self::Source {
224 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
225 unsafe { SourceIter::as_inner(&mut self.iter) }
226 }
227}
228
229// SAFETY: GenericShunt::next calls `I::try_for_each`, which has to advance `iter`
230// in order to return `Some(_)`. Since `iter` has type `I: InPlaceIterable` it's
231// guaranteed that at least one item will be moved out from the underlying source.
232#[unstable(issue = "none", feature = "inplace_iteration")]
233unsafe impl<I, R> InPlaceIterable for GenericShunt<'_, I, R>
234where
235 I: InPlaceIterable,
236{
237 const EXPAND_BY: Option<NonZero<usize>> = I::EXPAND_BY;
238 const MERGE_BY: Option<NonZero<usize>> = I::MERGE_BY;
239}
240