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

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