library/core/src/iter/adapters/fuse.rs

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