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

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