]>
Commit | Line | Data |
---|---|---|
1 | use crate::intrinsics; | |
2 | use crate::iter::adapters::zip::try_get_unchecked; | |
3 | use crate::iter::{ | |
4 | DoubleEndedIterator, ExactSizeIterator, FusedIterator, TrustedLen, TrustedRandomAccess, | |
5 | TrustedRandomAccessNoCoerce, | |
6 | }; | |
7 | use crate::ops::Try; | |
8 | ||
9 | /// An iterator that yields `None` forever after the underlying iterator | |
10 | /// yields `None` once. | |
11 | /// | |
12 | /// This `struct` is created by [`Iterator::fuse`]. See its documentation | |
13 | /// for more. | |
14 | #[derive(Clone, Debug)] | |
15 | #[must_use = "iterators are lazy and do nothing unless consumed"] | |
16 | #[stable(feature = "rust1", since = "1.0.0")] | |
17 | pub struct Fuse<I> { | |
18 | // NOTE: for `I: FusedIterator`, we never bother setting `None`, but | |
19 | // we still have to be prepared for that state due to variance. | |
20 | // See rust-lang/rust#85863 | |
21 | iter: Option<I>, | |
22 | } | |
23 | impl<I> Fuse<I> { | |
24 | pub(in crate::iter) fn new(iter: I) -> Fuse<I> { | |
25 | Fuse { iter: Some(iter) } | |
26 | } | |
27 | } | |
28 | ||
29 | #[stable(feature = "fused", since = "1.26.0")] | |
30 | impl<I> FusedIterator for Fuse<I> where I: Iterator {} | |
31 | ||
32 | /// Fuse the iterator if the expression is `None`. | |
33 | macro_rules! fuse { | |
34 | ($self:ident . iter . $($call:tt)+) => { | |
35 | match $self.iter { | |
36 | Some(ref mut iter) => match iter.$($call)+ { | |
37 | None => { | |
38 | $self.iter = None; | |
39 | None | |
40 | } | |
41 | item => item, | |
42 | }, | |
43 | None => None, | |
44 | } | |
45 | }; | |
46 | } | |
47 | ||
48 | /// Specialized macro that doesn't check if the expression is `None`. | |
49 | /// (We trust that a `FusedIterator` will fuse itself.) | |
50 | macro_rules! spec { | |
51 | ($self:ident . iter . $($call:tt)+) => { | |
52 | match $self.iter { | |
53 | Some(ref mut iter) => iter.$($call)+, | |
54 | None => None, | |
55 | } | |
56 | }; | |
57 | } | |
58 | ||
59 | // Any specialized implementation here is made internal | |
60 | // to avoid exposing default fns outside this trait. | |
61 | #[stable(feature = "rust1", since = "1.0.0")] | |
62 | impl<I> Iterator for Fuse<I> | |
63 | where | |
64 | I: Iterator, | |
65 | { | |
66 | type Item = <I as Iterator>::Item; | |
67 | ||
68 | #[inline] | |
69 | fn next(&mut self) -> Option<Self::Item> { | |
70 | FuseImpl::next(self) | |
71 | } | |
72 | ||
73 | #[inline] | |
74 | fn nth(&mut self, n: usize) -> Option<I::Item> { | |
75 | FuseImpl::nth(self, n) | |
76 | } | |
77 | ||
78 | #[inline] | |
79 | fn last(self) -> Option<Self::Item> { | |
80 | match self.iter { | |
81 | Some(iter) => iter.last(), | |
82 | None => None, | |
83 | } | |
84 | } | |
85 | ||
86 | #[inline] | |
87 | fn count(self) -> usize { | |
88 | match self.iter { | |
89 | Some(iter) => iter.count(), | |
90 | None => 0, | |
91 | } | |
92 | } | |
93 | ||
94 | #[inline] | |
95 | fn size_hint(&self) -> (usize, Option<usize>) { | |
96 | match self.iter { | |
97 | Some(ref iter) => iter.size_hint(), | |
98 | None => (0, Some(0)), | |
99 | } | |
100 | } | |
101 | ||
102 | #[inline] | |
103 | fn try_fold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R | |
104 | where | |
105 | Self: Sized, | |
106 | Fold: FnMut(Acc, Self::Item) -> R, | |
107 | R: Try<Output = Acc>, | |
108 | { | |
109 | FuseImpl::try_fold(self, acc, fold) | |
110 | } | |
111 | ||
112 | #[inline] | |
113 | fn fold<Acc, Fold>(self, mut acc: Acc, fold: Fold) -> Acc | |
114 | where | |
115 | Fold: FnMut(Acc, Self::Item) -> Acc, | |
116 | { | |
117 | if let Some(iter) = self.iter { | |
118 | acc = iter.fold(acc, fold); | |
119 | } | |
120 | acc | |
121 | } | |
122 | ||
123 | #[inline] | |
124 | fn find<P>(&mut self, predicate: P) -> Option<Self::Item> | |
125 | where | |
126 | P: FnMut(&Self::Item) -> bool, | |
127 | { | |
128 | FuseImpl::find(self, predicate) | |
129 | } | |
130 | ||
131 | #[inline] | |
132 | unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item | |
133 | where | |
134 | Self: TrustedRandomAccessNoCoerce, | |
135 | { | |
136 | match self.iter { | |
137 | // SAFETY: the caller must uphold the contract for | |
138 | // `Iterator::__iterator_get_unchecked`. | |
139 | Some(ref mut iter) => unsafe { try_get_unchecked(iter, idx) }, | |
140 | // SAFETY: the caller asserts there is an item at `i`, so we're not exhausted. | |
141 | None => unsafe { intrinsics::unreachable() }, | |
142 | } | |
143 | } | |
144 | } | |
145 | ||
146 | #[stable(feature = "rust1", since = "1.0.0")] | |
147 | impl<I> DoubleEndedIterator for Fuse<I> | |
148 | where | |
149 | I: DoubleEndedIterator, | |
150 | { | |
151 | #[inline] | |
152 | fn next_back(&mut self) -> Option<<I as Iterator>::Item> { | |
153 | FuseImpl::next_back(self) | |
154 | } | |
155 | ||
156 | #[inline] | |
157 | fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> { | |
158 | FuseImpl::nth_back(self, n) | |
159 | } | |
160 | ||
161 | #[inline] | |
162 | fn try_rfold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R | |
163 | where | |
164 | Self: Sized, | |
165 | Fold: FnMut(Acc, Self::Item) -> R, | |
166 | R: Try<Output = Acc>, | |
167 | { | |
168 | FuseImpl::try_rfold(self, acc, fold) | |
169 | } | |
170 | ||
171 | #[inline] | |
172 | fn rfold<Acc, Fold>(self, mut acc: Acc, fold: Fold) -> Acc | |
173 | where | |
174 | Fold: FnMut(Acc, Self::Item) -> Acc, | |
175 | { | |
176 | if let Some(iter) = self.iter { | |
177 | acc = iter.rfold(acc, fold); | |
178 | } | |
179 | acc | |
180 | } | |
181 | ||
182 | #[inline] | |
183 | fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> | |
184 | where | |
185 | P: FnMut(&Self::Item) -> bool, | |
186 | { | |
187 | FuseImpl::rfind(self, predicate) | |
188 | } | |
189 | } | |
190 | ||
191 | #[stable(feature = "rust1", since = "1.0.0")] | |
192 | impl<I> ExactSizeIterator for Fuse<I> | |
193 | where | |
194 | I: ExactSizeIterator, | |
195 | { | |
196 | fn len(&self) -> usize { | |
197 | match self.iter { | |
198 | Some(ref iter) => iter.len(), | |
199 | None => 0, | |
200 | } | |
201 | } | |
202 | ||
203 | fn is_empty(&self) -> bool { | |
204 | match self.iter { | |
205 | Some(ref iter) => iter.is_empty(), | |
206 | None => true, | |
207 | } | |
208 | } | |
209 | } | |
210 | ||
211 | #[unstable(feature = "trusted_len", issue = "37572")] | |
212 | // SAFETY: `TrustedLen` requires that an accurate length is reported via `size_hint()`. As `Fuse` | |
213 | // is just forwarding this to the wrapped iterator `I` this property is preserved and it is safe to | |
214 | // implement `TrustedLen` here. | |
215 | unsafe impl<I> TrustedLen for Fuse<I> where I: TrustedLen {} | |
216 | ||
217 | #[doc(hidden)] | |
218 | #[unstable(feature = "trusted_random_access", issue = "none")] | |
219 | // SAFETY: `TrustedRandomAccess` requires that `size_hint()` must be exact and cheap to call, and | |
220 | // `Iterator::__iterator_get_unchecked()` must be implemented accordingly. | |
221 | // | |
222 | // This is safe to implement as `Fuse` is just forwarding these to the wrapped iterator `I`, which | |
223 | // preserves these properties. | |
224 | unsafe impl<I> TrustedRandomAccess for Fuse<I> where I: TrustedRandomAccess {} | |
225 | ||
226 | #[doc(hidden)] | |
227 | #[unstable(feature = "trusted_random_access", issue = "none")] | |
228 | unsafe impl<I> TrustedRandomAccessNoCoerce for Fuse<I> | |
229 | where | |
230 | I: TrustedRandomAccessNoCoerce, | |
231 | { | |
232 | const MAY_HAVE_SIDE_EFFECT: bool = I::MAY_HAVE_SIDE_EFFECT; | |
233 | } | |
234 | ||
235 | /// Fuse specialization trait | |
236 | /// | |
237 | /// We only need to worry about `&mut self` methods, which | |
238 | /// may exhaust the iterator without consuming it. | |
239 | #[doc(hidden)] | |
240 | trait FuseImpl<I> { | |
241 | type Item; | |
242 | ||
243 | // Functions specific to any normal Iterators | |
244 | fn next(&mut self) -> Option<Self::Item>; | |
245 | fn nth(&mut self, n: usize) -> Option<Self::Item>; | |
246 | fn try_fold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R | |
247 | where | |
248 | Self: Sized, | |
249 | Fold: FnMut(Acc, Self::Item) -> R, | |
250 | R: Try<Output = Acc>; | |
251 | fn find<P>(&mut self, predicate: P) -> Option<Self::Item> | |
252 | where | |
253 | P: FnMut(&Self::Item) -> bool; | |
254 | ||
255 | // Functions specific to DoubleEndedIterators | |
256 | fn next_back(&mut self) -> Option<Self::Item> | |
257 | where | |
258 | I: DoubleEndedIterator; | |
259 | fn nth_back(&mut self, n: usize) -> Option<Self::Item> | |
260 | where | |
261 | I: DoubleEndedIterator; | |
262 | fn try_rfold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R | |
263 | where | |
264 | Self: Sized, | |
265 | Fold: FnMut(Acc, Self::Item) -> R, | |
266 | R: Try<Output = Acc>, | |
267 | I: DoubleEndedIterator; | |
268 | fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> | |
269 | where | |
270 | P: FnMut(&Self::Item) -> bool, | |
271 | I: DoubleEndedIterator; | |
272 | } | |
273 | ||
274 | /// General `Fuse` impl which sets `iter = None` when exhausted. | |
275 | #[doc(hidden)] | |
276 | impl<I> FuseImpl<I> for Fuse<I> | |
277 | where | |
278 | I: Iterator, | |
279 | { | |
280 | type Item = <I as Iterator>::Item; | |
281 | ||
282 | #[inline] | |
283 | default fn next(&mut self) -> Option<<I as Iterator>::Item> { | |
284 | fuse!(self.iter.next()) | |
285 | } | |
286 | ||
287 | #[inline] | |
288 | default fn nth(&mut self, n: usize) -> Option<I::Item> { | |
289 | fuse!(self.iter.nth(n)) | |
290 | } | |
291 | ||
292 | #[inline] | |
293 | default fn try_fold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R | |
294 | where | |
295 | Self: Sized, | |
296 | Fold: FnMut(Acc, Self::Item) -> R, | |
297 | R: Try<Output = Acc>, | |
298 | { | |
299 | if let Some(ref mut iter) = self.iter { | |
300 | acc = iter.try_fold(acc, fold)?; | |
301 | self.iter = None; | |
302 | } | |
303 | try { acc } | |
304 | } | |
305 | ||
306 | #[inline] | |
307 | default fn find<P>(&mut self, predicate: P) -> Option<Self::Item> | |
308 | where | |
309 | P: FnMut(&Self::Item) -> bool, | |
310 | { | |
311 | fuse!(self.iter.find(predicate)) | |
312 | } | |
313 | ||
314 | #[inline] | |
315 | default fn next_back(&mut self) -> Option<<I as Iterator>::Item> | |
316 | where | |
317 | I: DoubleEndedIterator, | |
318 | { | |
319 | fuse!(self.iter.next_back()) | |
320 | } | |
321 | ||
322 | #[inline] | |
323 | default fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> | |
324 | where | |
325 | I: DoubleEndedIterator, | |
326 | { | |
327 | fuse!(self.iter.nth_back(n)) | |
328 | } | |
329 | ||
330 | #[inline] | |
331 | default fn try_rfold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R | |
332 | where | |
333 | Self: Sized, | |
334 | Fold: FnMut(Acc, Self::Item) -> R, | |
335 | R: Try<Output = Acc>, | |
336 | I: DoubleEndedIterator, | |
337 | { | |
338 | if let Some(ref mut iter) = self.iter { | |
339 | acc = iter.try_rfold(acc, fold)?; | |
340 | self.iter = None; | |
341 | } | |
342 | try { acc } | |
343 | } | |
344 | ||
345 | #[inline] | |
346 | default fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> | |
347 | where | |
348 | P: FnMut(&Self::Item) -> bool, | |
349 | I: DoubleEndedIterator, | |
350 | { | |
351 | fuse!(self.iter.rfind(predicate)) | |
352 | } | |
353 | } | |
354 | ||
355 | /// Specialized `Fuse` impl which doesn't bother clearing `iter` when exhausted. | |
356 | /// However, we must still be prepared for the possibility that it was already cleared! | |
357 | #[doc(hidden)] | |
358 | impl<I> FuseImpl<I> for Fuse<I> | |
359 | where | |
360 | I: FusedIterator, | |
361 | { | |
362 | #[inline] | |
363 | fn next(&mut self) -> Option<<I as Iterator>::Item> { | |
364 | spec!(self.iter.next()) | |
365 | } | |
366 | ||
367 | #[inline] | |
368 | fn nth(&mut self, n: usize) -> Option<I::Item> { | |
369 | spec!(self.iter.nth(n)) | |
370 | } | |
371 | ||
372 | #[inline] | |
373 | fn try_fold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R | |
374 | where | |
375 | Self: Sized, | |
376 | Fold: FnMut(Acc, Self::Item) -> R, | |
377 | R: Try<Output = Acc>, | |
378 | { | |
379 | if let Some(ref mut iter) = self.iter { | |
380 | acc = iter.try_fold(acc, fold)?; | |
381 | } | |
382 | try { acc } | |
383 | } | |
384 | ||
385 | #[inline] | |
386 | fn find<P>(&mut self, predicate: P) -> Option<Self::Item> | |
387 | where | |
388 | P: FnMut(&Self::Item) -> bool, | |
389 | { | |
390 | spec!(self.iter.find(predicate)) | |
391 | } | |
392 | ||
393 | #[inline] | |
394 | fn next_back(&mut self) -> Option<<I as Iterator>::Item> | |
395 | where | |
396 | I: DoubleEndedIterator, | |
397 | { | |
398 | spec!(self.iter.next_back()) | |
399 | } | |
400 | ||
401 | #[inline] | |
402 | fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> | |
403 | where | |
404 | I: DoubleEndedIterator, | |
405 | { | |
406 | spec!(self.iter.nth_back(n)) | |
407 | } | |
408 | ||
409 | #[inline] | |
410 | fn try_rfold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R | |
411 | where | |
412 | Self: Sized, | |
413 | Fold: FnMut(Acc, Self::Item) -> R, | |
414 | R: Try<Output = Acc>, | |
415 | I: DoubleEndedIterator, | |
416 | { | |
417 | if let Some(ref mut iter) = self.iter { | |
418 | acc = iter.try_rfold(acc, fold)?; | |
419 | } | |
420 | try { acc } | |
421 | } | |
422 | ||
423 | #[inline] | |
424 | fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> | |
425 | where | |
426 | P: FnMut(&Self::Item) -> bool, | |
427 | I: DoubleEndedIterator, | |
428 | { | |
429 | spec!(self.iter.rfind(predicate)) | |
430 | } | |
431 | } |