1use crate::intrinsics;
2use crate::iter::adapters::zip::try_get_unchecked;
3use crate::iter::adapters::SourceIter;
4use crate::iter::{
5 FusedIterator, TrustedFused, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce,
6};
7use 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")]
17pub 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}
23impl<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")]
34impl<I> FusedIterator for Fuse<I> where I: Iterator {}
35
36#[unstable(issue = "none", feature = "trusted_fused")]
37unsafe 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")]
42impl<I> Iterator for Fuse<I>
43where
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")]
127impl<I> DoubleEndedIterator for Fuse<I>
128where
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")]
172impl<I> ExactSizeIterator for Fuse<I>
173where
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")]
192impl<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.
210unsafe 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.
219unsafe impl<I> TrustedRandomAccess for Fuse<I> where I: TrustedRandomAccess {}
220
221#[doc(hidden)]
222#[unstable(feature = "trusted_random_access", issue = "none")]
223unsafe impl<I> TrustedRandomAccessNoCoerce for Fuse<I>
224where
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)]
235trait 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)]
271impl<I> FuseImpl<I> for Fuse<I>
272where
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)]
353impl<I> FuseImpl<I> for Fuse<I>
354where
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")]
430unsafe impl<I> SourceIter for Fuse<I>
431where
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]
446fn 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