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 | #[stable (feature = "rust1" , since = "1.0.0" )] |
32 | pub 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" )] |
39 | pub use self::array_chunks::ArrayChunks; |
40 | |
41 | #[unstable (feature = "std_internals" , issue = "none" )] |
42 | pub use self::by_ref_sized::ByRefSized; |
43 | |
44 | #[stable (feature = "iter_cloned" , since = "1.1.0" )] |
45 | pub use self::cloned::Cloned; |
46 | |
47 | #[stable (feature = "iterator_step_by" , since = "1.28.0" )] |
48 | pub use self::step_by::StepBy; |
49 | |
50 | #[stable (feature = "iterator_flatten" , since = "1.29.0" )] |
51 | pub use self::flatten::Flatten; |
52 | |
53 | #[stable (feature = "iter_copied" , since = "1.36.0" )] |
54 | pub use self::copied::Copied; |
55 | |
56 | #[unstable (feature = "iter_intersperse" , reason = "recently added" , issue = "79524" )] |
57 | pub use self::intersperse::{Intersperse, IntersperseWith}; |
58 | |
59 | #[stable (feature = "iter_map_while" , since = "1.57.0" )] |
60 | pub use self::map_while::MapWhile; |
61 | |
62 | #[unstable (feature = "iter_map_windows" , reason = "recently added" , issue = "87155" )] |
63 | pub use self::map_windows::MapWindows; |
64 | |
65 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
66 | pub use self::zip::TrustedRandomAccess; |
67 | |
68 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
69 | pub use self::zip::TrustedRandomAccessNoCoerce; |
70 | |
71 | #[stable (feature = "iter_zip" , since = "1.59.0" )] |
72 | pub 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 ] |
115 | pub 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. |
154 | pub(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. |
162 | pub(crate) fn try_process<I, T, R, F, U>(iter: I, mut f: F) -> ChangeOutputType<I::Item, U> |
163 | where |
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 | |
177 | impl<I, R> Iterator for GenericShunt<'_, I, R> |
178 | where |
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" )] |
216 | unsafe impl<I, R> SourceIter for GenericShunt<'_, I, R> |
217 | where |
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" )] |
233 | unsafe impl<I, R> InPlaceIterable for GenericShunt<'_, I, R> |
234 | where |
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 | |