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