core/iter/adapters/
fuse.rs

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

core/iter/adapters/
fuse.rs
