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

core/iter/adapters/
fuse.rs
