fuse.rs - source
Description: Source of the Rust file `library/core/src/iter/adapters/fuse.rs`.

#
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}