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