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