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::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) => iter.len(),
179            None => 0,
180        }
181    }
182
183    fn is_empty(&self) -> bool {
184        match self.iter {
185            Some(ref iter) => 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    ///
202    /// This is equivalent to `I::default().fuse()`[^fuse_note]; e.g. if
203    /// `I::default()` is not an empty iterator, then this will not be
204    /// an empty iterator.
205    ///
206    /// ```
207    /// # use std::iter::Fuse;
208    /// #[derive(Default)]
209    /// struct Fourever;
210    ///
211    /// impl Iterator for Fourever {
212    ///     type Item = u32;
213    ///     fn next(&mut self) -> Option<u32> {
214    ///         Some(4)
215    ///     }
216    /// }
217    ///
218    /// let mut iter: Fuse<Fourever> = Default::default();
219    /// assert_eq!(iter.next(), Some(4));
220    /// ```
221    ///
222    /// [^fuse_note]: if `I` does not override `Iterator::fuse`'s default implementation
223    fn default() -> Self {
224        Fuse { iter: Some(I::default()) }
225    }
226}
227
228#[unstable(feature = "trusted_len", issue = "37572")]
229// SAFETY: `TrustedLen` requires that an accurate length is reported via `size_hint()`. As `Fuse`
230// is just forwarding this to the wrapped iterator `I` this property is preserved and it is safe to
231// implement `TrustedLen` here.
232unsafe impl<I> TrustedLen for Fuse<I> where I: TrustedLen {}
233
234#[doc(hidden)]
235#[unstable(feature = "trusted_random_access", issue = "none")]
236// SAFETY: `TrustedRandomAccess` requires that `size_hint()` must be exact and cheap to call, and
237// `Iterator::__iterator_get_unchecked()` must be implemented accordingly.
238//
239// This is safe to implement as `Fuse` is just forwarding these to the wrapped iterator `I`, which
240// preserves these properties.
241unsafe impl<I> TrustedRandomAccess for Fuse<I> where I: TrustedRandomAccess {}
242
243#[doc(hidden)]
244#[unstable(feature = "trusted_random_access", issue = "none")]
245unsafe impl<I> TrustedRandomAccessNoCoerce for Fuse<I>
246where
247    I: TrustedRandomAccessNoCoerce,
248{
249    const MAY_HAVE_SIDE_EFFECT: bool = I::MAY_HAVE_SIDE_EFFECT;
250}
251
252/// Fuse specialization trait
253///
254/// We only need to worry about `&mut self` methods, which
255/// may exhaust the iterator without consuming it.
256#[doc(hidden)]
257trait FuseImpl<I> {
258    type Item;
259
260    // Functions specific to any normal Iterators
261    fn next(&mut self) -> Option<Self::Item>;
262    fn nth(&mut self, n: usize) -> Option<Self::Item>;
263    fn try_fold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R
264    where
265        Self: Sized,
266        Fold: FnMut(Acc, Self::Item) -> R,
267        R: Try<Output = Acc>;
268    fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
269    where
270        P: FnMut(&Self::Item) -> bool;
271
272    // Functions specific to DoubleEndedIterators
273    fn next_back(&mut self) -> Option<Self::Item>
274    where
275        I: DoubleEndedIterator;
276    fn nth_back(&mut self, n: usize) -> Option<Self::Item>
277    where
278        I: DoubleEndedIterator;
279    fn try_rfold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R
280    where
281        Self: Sized,
282        Fold: FnMut(Acc, Self::Item) -> R,
283        R: Try<Output = Acc>,
284        I: DoubleEndedIterator;
285    fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
286    where
287        P: FnMut(&Self::Item) -> bool,
288        I: DoubleEndedIterator;
289}
290
291/// General `Fuse` impl which sets `iter = None` when exhausted.
292#[doc(hidden)]
293impl<I> FuseImpl<I> for Fuse<I>
294where
295    I: Iterator,
296{
297    type Item = <I as Iterator>::Item;
298
299    #[inline]
300    default fn next(&mut self) -> Option<<I as Iterator>::Item> {
301        and_then_or_clear(&mut self.iter, Iterator::next)
302    }
303
304    #[inline]
305    default fn nth(&mut self, n: usize) -> Option<I::Item> {
306        and_then_or_clear(&mut self.iter, |iter| iter.nth(n))
307    }
308
309    #[inline]
310    default fn try_fold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R
311    where
312        Self: Sized,
313        Fold: FnMut(Acc, Self::Item) -> R,
314        R: Try<Output = Acc>,
315    {
316        if let Some(ref mut iter) = self.iter {
317            acc = iter.try_fold(acc, fold)?;
318            self.iter = None;
319        }
320        try { acc }
321    }
322
323    #[inline]
324    default fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
325    where
326        P: FnMut(&Self::Item) -> bool,
327    {
328        and_then_or_clear(&mut self.iter, |iter| iter.find(predicate))
329    }
330
331    #[inline]
332    default fn next_back(&mut self) -> Option<<I as Iterator>::Item>
333    where
334        I: DoubleEndedIterator,
335    {
336        and_then_or_clear(&mut self.iter, |iter| iter.next_back())
337    }
338
339    #[inline]
340    default fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item>
341    where
342        I: DoubleEndedIterator,
343    {
344        and_then_or_clear(&mut self.iter, |iter| iter.nth_back(n))
345    }
346
347    #[inline]
348    default fn try_rfold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R
349    where
350        Self: Sized,
351        Fold: FnMut(Acc, Self::Item) -> R,
352        R: Try<Output = Acc>,
353        I: DoubleEndedIterator,
354    {
355        if let Some(ref mut iter) = self.iter {
356            acc = iter.try_rfold(acc, fold)?;
357            self.iter = None;
358        }
359        try { acc }
360    }
361
362    #[inline]
363    default fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
364    where
365        P: FnMut(&Self::Item) -> bool,
366        I: DoubleEndedIterator,
367    {
368        and_then_or_clear(&mut self.iter, |iter| iter.rfind(predicate))
369    }
370}
371
372/// Specialized `Fuse` impl which doesn't bother clearing `iter` when exhausted.
373/// However, we must still be prepared for the possibility that it was already cleared!
374#[doc(hidden)]
375impl<I> FuseImpl<I> for Fuse<I>
376where
377    I: FusedIterator,
378{
379    #[inline]
380    fn next(&mut self) -> Option<<I as Iterator>::Item> {
381        self.iter.as_mut()?.next()
382    }
383
384    #[inline]
385    fn nth(&mut self, n: usize) -> Option<I::Item> {
386        self.iter.as_mut()?.nth(n)
387    }
388
389    #[inline]
390    fn try_fold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R
391    where
392        Self: Sized,
393        Fold: FnMut(Acc, Self::Item) -> R,
394        R: Try<Output = Acc>,
395    {
396        if let Some(ref mut iter) = self.iter {
397            acc = iter.try_fold(acc, fold)?;
398        }
399        try { acc }
400    }
401
402    #[inline]
403    fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
404    where
405        P: FnMut(&Self::Item) -> bool,
406    {
407        self.iter.as_mut()?.find(predicate)
408    }
409
410    #[inline]
411    fn next_back(&mut self) -> Option<<I as Iterator>::Item>
412    where
413        I: DoubleEndedIterator,
414    {
415        self.iter.as_mut()?.next_back()
416    }
417
418    #[inline]
419    fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item>
420    where
421        I: DoubleEndedIterator,
422    {
423        self.iter.as_mut()?.nth_back(n)
424    }
425
426    #[inline]
427    fn try_rfold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R
428    where
429        Self: Sized,
430        Fold: FnMut(Acc, Self::Item) -> R,
431        R: Try<Output = Acc>,
432        I: DoubleEndedIterator,
433    {
434        if let Some(ref mut iter) = self.iter {
435            acc = iter.try_rfold(acc, fold)?;
436        }
437        try { acc }
438    }
439
440    #[inline]
441    fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
442    where
443        P: FnMut(&Self::Item) -> bool,
444        I: DoubleEndedIterator,
445    {
446        self.iter.as_mut()?.rfind(predicate)
447    }
448}
449
450// This is used by Flatten's SourceIter impl
451#[unstable(issue = "none", feature = "inplace_iteration")]
452unsafe impl<I> SourceIter for Fuse<I>
453where
454    I: SourceIter + TrustedFused,
455{
456    type Source = I::Source;
457
458    #[inline]
459    unsafe fn as_inner(&mut self) -> &mut I::Source {
460        // SAFETY: unsafe function forwarding to unsafe function with the same requirements.
461        // TrustedFused guarantees that we'll never encounter a case where `self.iter` would
462        // be set to None.
463        unsafe { SourceIter::as_inner(self.iter.as_mut().unwrap_unchecked()) }
464    }
465}
466
467#[inline]
468fn and_then_or_clear<T, U>(opt: &mut Option<T>, f: impl FnOnce(&mut T) -> Option<U>) -> Option<U> {
469    let x = f(opt.as_mut()?);
470    if x.is_none() {
471        *opt = None;
472    }
473    x
474}
core/iter/adapters/fuse.rs

core/iter/adapters/
fuse.rs
