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

   1 use crate::{
   2     fmt,
   3     iter::{adapters::SourceIter, FusedIterator, InPlaceIterable},
   4     ops::Try,
   5 };
   6
   7 /// An iterator that filters the elements of `iter` with `predicate`.
   8 ///
   9 /// This `struct` is created by the [`filter`] method on [`Iterator`]. See its
  10 /// documentation for more.
  11 ///
  12 /// [`filter`]: Iterator::filter
  13 /// [`Iterator`]: trait.Iterator.html
  14 #[must_use = "iterators are lazy and do nothing unless consumed"]
  15 #[stable(feature = "rust1", since = "1.0.0")]
  16 #[derive(Clone)]
  17 pub struct Filter<I, P> {
  18     iter: I,
  19     predicate: P,
  20 }
  21 impl<I, P> Filter<I, P> {
  22     pub(in crate::iter) fn new(iter: I, predicate: P) -> Filter<I, P> {
  23         Filter { iter, predicate }
  24     }
  25 }
  26
  27 #[stable(feature = "core_impl_debug", since = "1.9.0")]
  28 impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> {
  29     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  30         f.debug_struct("Filter").field("iter", &self.iter).finish()
  31     }
  32 }
  33
  34 fn filter_fold<T, Acc>(
  35     mut predicate: impl FnMut(&T) -> bool,
  36     mut fold: impl FnMut(Acc, T) -> Acc,
  37 ) -> impl FnMut(Acc, T) -> Acc {
  38     move |acc, item| if predicate(&item) { fold(acc, item) } else { acc }
  39 }
  40
  41 fn filter_try_fold<'a, T, Acc, R: Try<Ok = Acc>>(
  42     predicate: &'a mut impl FnMut(&T) -> bool,
  43     mut fold: impl FnMut(Acc, T) -> R + 'a,
  44 ) -> impl FnMut(Acc, T) -> R + 'a {
  45     move |acc, item| if predicate(&item) { fold(acc, item) } else { try { acc } }
  46 }
  47
  48 #[stable(feature = "rust1", since = "1.0.0")]
  49 impl<I: Iterator, P> Iterator for Filter<I, P>
  50 where
  51     P: FnMut(&I::Item) -> bool,
  52 {
  53     type Item = I::Item;
  54
  55     #[inline]
  56     fn next(&mut self) -> Option<I::Item> {
  57         self.iter.find(&mut self.predicate)
  58     }
  59
  60     #[inline]
  61     fn size_hint(&self) -> (usize, Option<usize>) {
  62         let (_, upper) = self.iter.size_hint();
  63         (0, upper) // can't know a lower bound, due to the predicate
  64     }
  65
  66     // this special case allows the compiler to make `.filter(_).count()`
  67     // branchless. Barring perfect branch prediction (which is unattainable in
  68     // the general case), this will be much faster in >90% of cases (containing
  69     // virtually all real workloads) and only a tiny bit slower in the rest.
  70     //
  71     // Having this specialization thus allows us to write `.filter(p).count()`
  72     // where we would otherwise write `.map(|x| p(x) as usize).sum()`, which is
  73     // less readable and also less backwards-compatible to Rust before 1.10.
  74     //
  75     // Using the branchless version will also simplify the LLVM byte code, thus
  76     // leaving more budget for LLVM optimizations.
  77     #[inline]
  78     fn count(self) -> usize {
  79         #[inline]
  80         fn to_usize<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut(T) -> usize {
  81             move |x| predicate(&x) as usize
  82         }
  83
  84         self.iter.map(to_usize(self.predicate)).sum()
  85     }
  86
  87     #[inline]
  88     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
  89     where
  90         Self: Sized,
  91         Fold: FnMut(Acc, Self::Item) -> R,
  92         R: Try<Ok = Acc>,
  93     {
  94         self.iter.try_fold(init, filter_try_fold(&mut self.predicate, fold))
  95     }
  96
  97     #[inline]
  98     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
  99     where
 100         Fold: FnMut(Acc, Self::Item) -> Acc,
 101     {
 102         self.iter.fold(init, filter_fold(self.predicate, fold))
 103     }
 104 }
 105
 106 #[stable(feature = "rust1", since = "1.0.0")]
 107 impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
 108 where
 109     P: FnMut(&I::Item) -> bool,
 110 {
 111     #[inline]
 112     fn next_back(&mut self) -> Option<I::Item> {
 113         self.iter.rfind(&mut self.predicate)
 114     }
 115
 116     #[inline]
 117     fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
 118     where
 119         Self: Sized,
 120         Fold: FnMut(Acc, Self::Item) -> R,
 121         R: Try<Ok = Acc>,
 122     {
 123         self.iter.try_rfold(init, filter_try_fold(&mut self.predicate, fold))
 124     }
 125
 126     #[inline]
 127     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 128     where
 129         Fold: FnMut(Acc, Self::Item) -> Acc,
 130     {
 131         self.iter.rfold(init, filter_fold(self.predicate, fold))
 132     }
 133 }
 134
 135 #[stable(feature = "fused", since = "1.26.0")]
 136 impl<I: FusedIterator, P> FusedIterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {}
 137
 138 #[unstable(issue = "none", feature = "inplace_iteration")]
 139 unsafe impl<S: Iterator, P, I: Iterator> SourceIter for Filter<I, P>
 140 where
 141     P: FnMut(&I::Item) -> bool,
 142     I: SourceIter<Source = S>,
 143 {
 144     type Source = S;
 145
 146     #[inline]
 147     unsafe fn as_inner(&mut self) -> &mut S {
 148         // SAFETY: unsafe function forwarding to unsafe function with the same requirements
 149         unsafe { SourceIter::as_inner(&mut self.iter) }
 150     }
 151 }
 152
 153 #[unstable(issue = "none", feature = "inplace_iteration")]
 154 unsafe impl<I: InPlaceIterable, P> InPlaceIterable for Filter<I, P> where P: FnMut(&I::Item) -> bool {}