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