core/iter/adapters/
fuse.rs

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

core/iter/adapters/
fuse.rs
