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

core/iter/adapters/
fuse.rs
