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

   1 use super::InPlaceIterable;
   2 use crate::intrinsics;
   3 use crate::iter::adapters::zip::try_get_unchecked;
   4 use crate::iter::adapters::SourceIter;
   5 use crate::iter::TrustedRandomAccess;
   6 use crate::iter::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator};
   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 the [`fuse`] method on [`Iterator`]. See its
  13 /// documentation for more.
  14 ///
  15 /// [`fuse`]: trait.Iterator.html#method.fuse
  16 /// [`Iterator`]: trait.Iterator.html
  17 #[derive(Clone, Debug)]
  18 #[must_use = "iterators are lazy and do nothing unless consumed"]
  19 #[stable(feature = "rust1", since = "1.0.0")]
  20 pub struct Fuse<I> {
  21     // NOTE: for `I: FusedIterator`, this is always assumed `Some`!
  22     iter: Option<I>,
  23 }
  24 impl<I> Fuse<I> {
  25     pub(in crate::iter) fn new(iter: I) -> Fuse<I> {
  26         Fuse { iter: Some(iter) }
  27     }
  28 }
  29
  30 #[stable(feature = "fused", since = "1.26.0")]
  31 impl<I> FusedIterator for Fuse<I> where I: Iterator {}
  32
  33 /// Fuse the iterator if the expression is `None`.
  34 macro_rules! fuse {
  35     ($self:ident . iter . $($call:tt)+) => {
  36         match $self.iter {
  37             Some(ref mut iter) => match iter.$($call)+ {
  38                 None => {
  39                     $self.iter = None;
  40                     None
  41                 }
  42                 item => item,
  43             },
  44             None => None,
  45         }
  46     };
  47 }
  48
  49 // NOTE: for `I: FusedIterator`, we assume that the iterator is always `Some`.
  50 // Implementing this as a directly-expanded macro helps codegen performance.
  51 macro_rules! unchecked {
  52     ($self:ident) => {
  53         match $self {
  54             Fuse { iter: Some(iter) } => iter,
  55             // SAFETY: the specialized iterator never sets `None`
  56             Fuse { iter: None } => unsafe { intrinsics::unreachable() },
  57         }
  58     };
  59 }
  60
  61 // Any implementation here is made internal to avoid exposing default fns outside this trait
  62 #[stable(feature = "rust1", since = "1.0.0")]
  63 impl<I> Iterator for Fuse<I>
  64 where
  65     I: Iterator,
  66 {
  67     type Item = <I as Iterator>::Item;
  68
  69     #[inline]
  70     fn next(&mut self) -> Option<Self::Item> {
  71         FuseImpl::next(self)
  72     }
  73
  74     #[inline]
  75     fn nth(&mut self, n: usize) -> Option<I::Item> {
  76         FuseImpl::nth(self, n)
  77     }
  78
  79     #[inline]
  80     fn last(self) -> Option<Self::Item> {
  81         FuseImpl::last(self)
  82     }
  83
  84     #[inline]
  85     fn count(self) -> usize {
  86         FuseImpl::count(self)
  87     }
  88
  89     #[inline]
  90     fn size_hint(&self) -> (usize, Option<usize>) {
  91         FuseImpl::size_hint(self)
  92     }
  93
  94     #[inline]
  95     fn try_fold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R
  96     where
  97         Self: Sized,
  98         Fold: FnMut(Acc, Self::Item) -> R,
  99         R: Try<Ok = Acc>,
 100     {
 101         FuseImpl::try_fold(self, acc, fold)
 102     }
 103
 104     #[inline]
 105     fn fold<Acc, Fold>(self, acc: Acc, fold: Fold) -> Acc
 106     where
 107         Fold: FnMut(Acc, Self::Item) -> Acc,
 108     {
 109         FuseImpl::fold(self, acc, fold)
 110     }
 111
 112     #[inline]
 113     fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
 114     where
 115         P: FnMut(&Self::Item) -> bool,
 116     {
 117         FuseImpl::find(self, predicate)
 118     }
 119
 120     #[inline]
 121     unsafe fn get_unchecked(&mut self, idx: usize) -> Self::Item
 122     where
 123         Self: TrustedRandomAccess,
 124     {
 125         match self.iter {
 126             // SAFETY: the caller must uphold the contract for `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 #[stable(feature = "rust1", since = "1.0.0")]
 135 impl<I> DoubleEndedIterator for Fuse<I>
 136 where
 137     I: DoubleEndedIterator,
 138 {
 139     #[inline]
 140     fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
 141         FuseImpl::next_back(self)
 142     }
 143
 144     #[inline]
 145     fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
 146         FuseImpl::nth_back(self, n)
 147     }
 148
 149     #[inline]
 150     fn try_rfold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R
 151     where
 152         Self: Sized,
 153         Fold: FnMut(Acc, Self::Item) -> R,
 154         R: Try<Ok = Acc>,
 155     {
 156         FuseImpl::try_rfold(self, acc, fold)
 157     }
 158
 159     #[inline]
 160     fn rfold<Acc, Fold>(self, acc: Acc, fold: Fold) -> Acc
 161     where
 162         Fold: FnMut(Acc, Self::Item) -> Acc,
 163     {
 164         FuseImpl::rfold(self, acc, fold)
 165     }
 166
 167     #[inline]
 168     fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
 169     where
 170         P: FnMut(&Self::Item) -> bool,
 171     {
 172         FuseImpl::rfind(self, predicate)
 173     }
 174 }
 175
 176 #[stable(feature = "rust1", since = "1.0.0")]
 177 impl<I> ExactSizeIterator for Fuse<I>
 178 where
 179     I: ExactSizeIterator,
 180 {
 181     fn len(&self) -> usize {
 182         FuseImpl::len(self)
 183     }
 184
 185     fn is_empty(&self) -> bool {
 186         FuseImpl::is_empty(self)
 187     }
 188 }
 189
 190 #[doc(hidden)]
 191 #[unstable(feature = "trusted_random_access", issue = "none")]
 192 unsafe impl<I> TrustedRandomAccess for Fuse<I>
 193 where
 194     I: TrustedRandomAccess,
 195 {
 196     fn may_have_side_effect() -> bool {
 197         I::may_have_side_effect()
 198     }
 199 }
 200
 201 // Fuse specialization trait
 202 #[doc(hidden)]
 203 trait FuseImpl<I> {
 204     type Item;
 205
 206     // Functions specific to any normal Iterators
 207     fn next(&mut self) -> Option<Self::Item>;
 208     fn nth(&mut self, n: usize) -> Option<Self::Item>;
 209     fn last(self) -> Option<Self::Item>;
 210     fn count(self) -> usize;
 211     fn size_hint(&self) -> (usize, Option<usize>);
 212     fn try_fold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R
 213     where
 214         Self: Sized,
 215         Fold: FnMut(Acc, Self::Item) -> R,
 216         R: Try<Ok = Acc>;
 217     fn fold<Acc, Fold>(self, acc: Acc, fold: Fold) -> Acc
 218     where
 219         Fold: FnMut(Acc, Self::Item) -> Acc;
 220     fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
 221     where
 222         P: FnMut(&Self::Item) -> bool;
 223
 224     // Functions specific to DoubleEndedIterators
 225     fn next_back(&mut self) -> Option<Self::Item>
 226     where
 227         I: DoubleEndedIterator;
 228     fn nth_back(&mut self, n: usize) -> Option<Self::Item>
 229     where
 230         I: DoubleEndedIterator;
 231     fn try_rfold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R
 232     where
 233         Self: Sized,
 234         Fold: FnMut(Acc, Self::Item) -> R,
 235         R: Try<Ok = Acc>,
 236         I: DoubleEndedIterator;
 237     fn rfold<Acc, Fold>(self, acc: Acc, fold: Fold) -> Acc
 238     where
 239         Fold: FnMut(Acc, Self::Item) -> 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     // Functions specific to ExactSizeIterator
 247     fn len(&self) -> usize
 248     where
 249         I: ExactSizeIterator;
 250     fn is_empty(&self) -> bool
 251     where
 252         I: ExactSizeIterator;
 253 }
 254
 255 // General Fuse impl
 256 #[doc(hidden)]
 257 impl<I> FuseImpl<I> for Fuse<I>
 258 where
 259     I: Iterator,
 260 {
 261     type Item = <I as Iterator>::Item;
 262
 263     #[inline]
 264     default fn next(&mut self) -> Option<<I as Iterator>::Item> {
 265         fuse!(self.iter.next())
 266     }
 267
 268     #[inline]
 269     default fn nth(&mut self, n: usize) -> Option<I::Item> {
 270         fuse!(self.iter.nth(n))
 271     }
 272
 273     #[inline]
 274     default fn last(self) -> Option<I::Item> {
 275         match self.iter {
 276             Some(iter) => iter.last(),
 277             None => None,
 278         }
 279     }
 280
 281     #[inline]
 282     default fn count(self) -> usize {
 283         match self.iter {
 284             Some(iter) => iter.count(),
 285             None => 0,
 286         }
 287     }
 288
 289     #[inline]
 290     default fn size_hint(&self) -> (usize, Option<usize>) {
 291         match self.iter {
 292             Some(ref iter) => iter.size_hint(),
 293             None => (0, Some(0)),
 294         }
 295     }
 296
 297     #[inline]
 298     default fn try_fold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R
 299     where
 300         Self: Sized,
 301         Fold: FnMut(Acc, Self::Item) -> R,
 302         R: Try<Ok = Acc>,
 303     {
 304         if let Some(ref mut iter) = self.iter {
 305             acc = iter.try_fold(acc, fold)?;
 306             self.iter = None;
 307         }
 308         Try::from_ok(acc)
 309     }
 310
 311     #[inline]
 312     default fn fold<Acc, Fold>(self, mut acc: Acc, fold: Fold) -> Acc
 313     where
 314         Fold: FnMut(Acc, Self::Item) -> Acc,
 315     {
 316         if let Some(iter) = self.iter {
 317             acc = iter.fold(acc, fold);
 318         }
 319         acc
 320     }
 321
 322     #[inline]
 323     default fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
 324     where
 325         P: FnMut(&Self::Item) -> bool,
 326     {
 327         fuse!(self.iter.find(predicate))
 328     }
 329
 330     #[inline]
 331     default fn next_back(&mut self) -> Option<<I as Iterator>::Item>
 332     where
 333         I: DoubleEndedIterator,
 334     {
 335         fuse!(self.iter.next_back())
 336     }
 337
 338     #[inline]
 339     default fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item>
 340     where
 341         I: DoubleEndedIterator,
 342     {
 343         fuse!(self.iter.nth_back(n))
 344     }
 345
 346     #[inline]
 347     default fn try_rfold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R
 348     where
 349         Self: Sized,
 350         Fold: FnMut(Acc, Self::Item) -> R,
 351         R: Try<Ok = Acc>,
 352         I: DoubleEndedIterator,
 353     {
 354         if let Some(ref mut iter) = self.iter {
 355             acc = iter.try_rfold(acc, fold)?;
 356             self.iter = None;
 357         }
 358         Try::from_ok(acc)
 359     }
 360
 361     #[inline]
 362     default fn rfold<Acc, Fold>(self, mut acc: Acc, fold: Fold) -> Acc
 363     where
 364         Fold: FnMut(Acc, Self::Item) -> Acc,
 365         I: DoubleEndedIterator,
 366     {
 367         if let Some(iter) = self.iter {
 368             acc = iter.rfold(acc, fold);
 369         }
 370         acc
 371     }
 372
 373     #[inline]
 374     default fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
 375     where
 376         P: FnMut(&Self::Item) -> bool,
 377         I: DoubleEndedIterator,
 378     {
 379         fuse!(self.iter.rfind(predicate))
 380     }
 381
 382     #[inline]
 383     default fn len(&self) -> usize
 384     where
 385         I: ExactSizeIterator,
 386     {
 387         match self.iter {
 388             Some(ref iter) => iter.len(),
 389             None => 0,
 390         }
 391     }
 392
 393     #[inline]
 394     default fn is_empty(&self) -> bool
 395     where
 396         I: ExactSizeIterator,
 397     {
 398         match self.iter {
 399             Some(ref iter) => iter.is_empty(),
 400             None => true,
 401         }
 402     }
 403 }
 404
 405 #[doc(hidden)]
 406 impl<I> FuseImpl<I> for Fuse<I>
 407 where
 408     I: FusedIterator,
 409 {
 410     #[inline]
 411     fn next(&mut self) -> Option<<I as Iterator>::Item> {
 412         unchecked!(self).next()
 413     }
 414
 415     #[inline]
 416     fn nth(&mut self, n: usize) -> Option<I::Item> {
 417         unchecked!(self).nth(n)
 418     }
 419
 420     #[inline]
 421     fn last(self) -> Option<I::Item> {
 422         unchecked!(self).last()
 423     }
 424
 425     #[inline]
 426     fn count(self) -> usize {
 427         unchecked!(self).count()
 428     }
 429
 430     #[inline]
 431     fn size_hint(&self) -> (usize, Option<usize>) {
 432         unchecked!(self).size_hint()
 433     }
 434
 435     #[inline]
 436     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
 437     where
 438         Self: Sized,
 439         Fold: FnMut(Acc, Self::Item) -> R,
 440         R: Try<Ok = Acc>,
 441     {
 442         unchecked!(self).try_fold(init, fold)
 443     }
 444
 445     #[inline]
 446     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 447     where
 448         Fold: FnMut(Acc, Self::Item) -> Acc,
 449     {
 450         unchecked!(self).fold(init, fold)
 451     }
 452
 453     #[inline]
 454     fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
 455     where
 456         P: FnMut(&Self::Item) -> bool,
 457     {
 458         unchecked!(self).find(predicate)
 459     }
 460
 461     #[inline]
 462     fn next_back(&mut self) -> Option<<I as Iterator>::Item>
 463     where
 464         I: DoubleEndedIterator,
 465     {
 466         unchecked!(self).next_back()
 467     }
 468
 469     #[inline]
 470     fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item>
 471     where
 472         I: DoubleEndedIterator,
 473     {
 474         unchecked!(self).nth_back(n)
 475     }
 476
 477     #[inline]
 478     fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
 479     where
 480         Self: Sized,
 481         Fold: FnMut(Acc, Self::Item) -> R,
 482         R: Try<Ok = Acc>,
 483         I: DoubleEndedIterator,
 484     {
 485         unchecked!(self).try_rfold(init, fold)
 486     }
 487
 488     #[inline]
 489     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 490     where
 491         Fold: FnMut(Acc, Self::Item) -> Acc,
 492         I: DoubleEndedIterator,
 493     {
 494         unchecked!(self).rfold(init, fold)
 495     }
 496
 497     #[inline]
 498     fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
 499     where
 500         P: FnMut(&Self::Item) -> bool,
 501         I: DoubleEndedIterator,
 502     {
 503         unchecked!(self).rfind(predicate)
 504     }
 505
 506     #[inline]
 507     fn len(&self) -> usize
 508     where
 509         I: ExactSizeIterator,
 510     {
 511         unchecked!(self).len()
 512     }
 513
 514     #[inline]
 515     fn is_empty(&self) -> bool
 516     where
 517         I: ExactSizeIterator,
 518     {
 519         unchecked!(self).is_empty()
 520     }
 521 }
 522
 523 #[unstable(issue = "none", feature = "inplace_iteration")]
 524 unsafe impl<S: Iterator, I: FusedIterator> SourceIter for Fuse<I>
 525 where
 526     I: SourceIter<Source = S>,
 527 {
 528     type Source = S;
 529
 530     #[inline]
 531     unsafe fn as_inner(&mut self) -> &mut S {
 532         match self.iter {
 533             // SAFETY: unsafe function forwarding to unsafe function with the same requirements
 534             Some(ref mut iter) => unsafe { SourceIter::as_inner(iter) },
 535             // SAFETY: the specialized iterator never sets `None`
 536             None => unsafe { intrinsics::unreachable() },
 537         }
 538     }
 539 }
 540
 541 #[unstable(issue = "none", feature = "inplace_iteration")]
 542 unsafe impl<I: InPlaceIterable> InPlaceIterable for Fuse<I> {}