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

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