[ADT] Add filter_iterator for filtering elements

[timshen]

Summary

filter_iterator is an iterator adaptor that filters a given iterator by a given predicate.

[chandlerc]

Cool, glad this is getting added!

include/llvm/ADT/STLExtras.h

239 ↗

(On Diff #66070)

No need for '\brief'.

242–244 ↗

(On Diff #66070)

I might rephrase this as "The predicate parameter should be a callable object that accepts the wrapped iterator's reference type and returns a bool. When incrementing or decrementing the iterator, it will call the predicate on each element and skip any where it returns false."

My goal is to highlight:

• The predicate is a callable.
• We will invoke it on every element, and invoke it while incrementing or decrementing as opposed to when dereferencing.

246–248 ↗

(On Diff #66070)

Why not support operator--? It seems easy?

252 ↗

(On Diff #66070)

Why not use (and add below) a make_filter_iterator? It seems like we will often want to avoid naming the type due to the predicate.

269–273 ↗

(On Diff #66070)

Instead, of the std::conditional, use std::common_type:

typename std::common_type<std::forward_iterator_tag,
                          typename std::iterator_traits<
                              WrappedIteratorT>::iterator_category>::type

This will use the derived to base conversion to select the best tag type possible, and as an advantage will fail to compile with an output iterator.

If you add operator--, then std::forward_iterator_tag above becomes std::bidirectional_iterator_tag. And you will *really* want to use common_type because the conditional gets crazy.

274–277 ↗

(On Diff #66070)

You don't need these four lines. The adaptor base will do this for you.

302–309 ↗

(On Diff #66070)

This needs its own doxygen comment.

unittests/Support/IteratorTest.cpp

104 ↗

(On Diff #66070)

Please test other forms of callables. std::function, function pointer at least.

Also test an input iterator and combining filter with some of our other adaptors like a filtered pointee iterator.

[timshen]

Updated iterator_adaptor_base, iterator category, comments and tests.

[timshen]

include/llvm/ADT/STLExtras.h

274–277 ↗

(On Diff #66070)

The adaptor will do PointerT = T* and ReferenceT = T& for me, but I want to forward WrappedIteratorT's pointer and reference type in filter_iterator (because the filtered elements have the same type as the original ones).

unittests/Support/IteratorTest.cpp

104 ↗

(On Diff #66070)

During adding the tests I do find a iterator_adaptor_base constructor problem. Changed the constructor to take WrappedIteratorT only. All users seem to still work.

[chandlerc]

One high level question that I'd love others' thoughts on: should this be spelled "filter_iterator" and "make_filter_range" or "filtered_iterator" and "make_filtered_range". For a type, I personally prefer "filtered_iterator". For the factory function, I wonder if we want something more like "reverse", perhaps "filter"?

include/llvm/ADT/STLExtras.h

246–248 ↗

(On Diff #66156)

I think I was very wrong to suggest this. IT's actually really hard to support being bi-directional, because now your iterator needs to retain *both* begin and end in addition to the current position so that it can stop backing up when necessary. The code below, if you back up from end and filter out begin, will walk completely past the start of the wrapped iterator. Oops.

It also forces you to copy the predicate into the begin and the end in order to be able to move the end iterator.

All of this complexity doesn't seem worth it when the user can always reverse the wrapped iterator rather than reversing this iterator. Go back to your original (simpler) design and make it a forward iterator. =D

252 ↗

(On Diff #66156)

I think this should be PredicateT here (at least for consistency).

284–287 ↗

(On Diff #66156)

I think you should make the constructor(s) for this iterator private and add some comments explaining that because even the begin iterator tracks the end, we need to construct these iterators as a range with begin and end anyways.

Then you can befriend the make_... function below.

Also, I think you should have two constructors, one that is exactly as your current, and one that accepts just one wrapped iterator, the end, and leaves the predicate uninitialized.

With that, you'll be able to avoid unnecessary copying of the predicate (see below) and we shouldn't ever be using the predicate on the end iterator based on my suggestion above.

285 ↗

(On Diff #66156)

You should move all of these.

311 ↗

(On Diff #66156)

No need for '\brief' here either. =]

313 ↗

(On Diff #66156)

As above, this should be PredicateT.

316 ↗

(On Diff #66156)

I think you want to accept the predicate by value and move it as we should be modeling "consume" semantics here. See above for avoiding the copy.

And a by-value parameter for an empty struct is more efficient than any kind of reference.

317 ↗

(On Diff #66156)

"IterT" is pretty ambiguous in the context including WrappedIteratorT... Also, I'd create the alias in the template parameter list so you can use it in the return type:

template <typename WrappedIteratorT, typename PredicateT>
          typename FilterIteratorT =
              filter_iterator<WrappedIteratorT, PredicateT>>

274–277 ↗

(On Diff #66070)

If we want to change this it should be changed in iterator_adaptor_base, not specialized here IMO.

And if you're going to fix that, it should be in a separate patch from the one adding the new iterator.

[timshen]

Changed it back to forward iterator. Do not keep predicate and the second iterator in end() construction.

include/llvm/ADT/STLExtras.h

246–248 ↗

(On Diff #66156)

...so that it can stop backing up when necessary.

I don't think so, since when a user calls operator--() and our wrapped iterator goes past the original begin, the user deserve the undefined behavior, right? It's like in general calling operator--() on begin().

It also forces you to copy the predicate into the begin and the end in order to be able to move the end iterator.

Great point. Saving one predicate copy sounds awesome. I'll change it back to a forward iterator.

274–277 ↗

(On Diff #66156)

Changing iterator_adaptor_base is weird, because forwarding the WrappedIteratorT's typedefs only makes sense in filter_iterator. In filter_iterator, the wrapped iterator has the same element as the filter_iterator has, while in the general iterator_adaptor_base it's not true.

Notice that filter_iterator doesn't require typename T parameter as iterator_adaptor_base does.

317 ↗

(On Diff #66156)

It's really hard to let a class friend declaration cope with default template argument. I will leave the local type alias alone, with a better name FilterIteratorT.

[dblaikie]

unittests/Support/IteratorTest.cpp

156 ↗

(On Diff #66377)

rather than repeating '7' here (the length of the array) you can use llvm::array_lengthof, but probably better than that, just use std::end(a) (and std::begin(a) if you like symmetry). Same goes for other cases of the array length constants in this test file.

[dblaikie]

unittests/Support/IteratorTest.cpp

113 ↗

(On Diff #66377)

Rather than adding something complex like std::function to the test - might be worth just having a simple stateful function object that exercises whatever specific behavior you're interested in.

137 ↗

(On Diff #66377)

we don't usually put 'const' on value typed locals - I'd skip this unless there's a particular need/reason (similar feedback for all const locals)

156 ↗

(On Diff #66377)

Probably use make_filter_range here and elsewhere in the tests.

[timshen]

filter_iterator -> filtered_iterator
Use std::begin() and std::end() for arrays.

[timshen]

std::function -> Callable object
s/const auto/auto/

unittests/Support/IteratorTest.cpp

156 ↗

(On Diff #66398)

Ehhh... I already used them?

[timshen]

Friendly ping :)

[timshen]

Rebase onto D23217.

[dblaikie]

In D22951#501451, @chandlerc wrote:

One high level question that I'd love others' thoughts on: should this be spelled "filter_iterator" and "make_filter_range" or "filtered_iterator" and "make_filtered_range". For a type, I personally prefer "filtered_iterator". For the factory function, I wonder if we want something more like "reverse", perhaps "filter"?

I'll vote for "filter" here - at least the version that takes an existing range (& perhaps that's the only version we should have - we already have utilities for making ranges out of a pair of iterators, so users with 'legacy' iterator APIs can use that to construct a range to pass to filter).

As for the name of the iterator - I'd be OK making that an unmentionable implementation detail. Most of the time its type is going to include a lambda type anyway, right - and thus be unmentionable.

include/llvm/ADT/STLExtras.h

305 ↗

(On Diff #67251)

If you like you can just define the friend inline at the friend declaration:

friend void foo() {
  ...
}

unittests/Support/IteratorTest.cpp

161–163 ↗

(On Diff #67251)

The distance tests probably aren't necessary if you're testing for exact equality anyway?

[timshen]

Removed std::distance check. Changed name to filter_iterator and make_filter_range.

[timshen]

In D22951#514042, @dblaikie wrote:

In D22951#501451, @chandlerc wrote:

One high level question that I'd love others' thoughts on: should this be spelled "filter_iterator" and "make_filter_range" or "filtered_iterator" and "make_filtered_range". For a type, I personally prefer "filtered_iterator". For the factory function, I wonder if we want something more like "reverse", perhaps "filter"?

I'll vote for "filter" here - at least the version that takes an existing range (& perhaps that's the only version we should have - we already have utilities for making ranges out of a pair of iterators, so users with 'legacy' iterator APIs can use that to construct a range to pass to filter).

As for the name of the iterator - I'd be OK making that an unmentionable implementation detail. Most of the time its type is going to include a lambda type anyway, right - and thus be unmentionable.

I don't have strong opinion on this. Changed to filter_iterator and make_filter_range.

unittests/Support/IteratorTest.cpp

161–163 ↗

(On Diff #67251)

Right. Removed.

[dblaikie]

include/llvm/ADT/STLExtras.h

311 ↗

(On Diff #67880)

This seems to be the wrong API - the function should accept any range, not just an iterator_range. (ie: you should be able to pass a std::vector to this function directly (or a std::set, SmallVector, DenseMap, etc))

So it should probably take the range as totally generic type T, as an rvalue reference/perfect forwarding.

This then gets into the issue of temporaries - which came up recently in the "zip" thread. It'd be good to resolve this aspect of teh design for both these utilities, before they go in.

(or, if you're in a hurry, just put some big comment saying this will do bad things with temporaries+range-for, for now)

unittests/Support/IteratorTest.cpp

182 ↗

(On Diff #67880)

Should just be able to pass "A" here, rather than "make_range(InputIterator(std::begin(A)), InputIterator(std::end(A)))"

Similarly in other test cases. I suppose the Composition test isn't able to do that (though the pointee iterator should have a wrapper utility that works as a range adapter) - but I'm not sure how useful/important that test is anyway. The iterators should be orthogonal, so testing combinations seems like it'd create an unbounded test matrix.

[timshen]

include/llvm/ADT/STLExtras.h

305 ↗

(On Diff #67880)

As discussed, with an inline friend definition we still need a declaration outside of the class, so I keep the function as it is now.

[timshen]

Changed make_filter_range to take an arbitrary range.

[timshen]

include/llvm/ADT/STLExtras.h

317 ↗

(On Diff #67912)

Added a comment with "FIXME".

unittests/Support/IteratorTest.cpp

182 ↗

(On Diff #67912)

For this specific one it needs to be make_range(InputIterator(std::begin(A)), InputIterator(std::end(A))), because otherwise the iterator is random access iterator.

For others I have removed the unnecessary make_range calls.

[dblaikie]

include/llvm/ADT/STLExtras.h

255 ↗

(On Diff #67912)

Might be worth renaming one of the 'A's to make this a bit easier to read.

321 ↗

(On Diff #67912)

I'd suggest renaming this to simply 'filter'. But if you'd rather defer that to some broader discussion, that's OK too.

[timshen]

Change the example comment to be more readable.

[timshen]

include/llvm/ADT/STLExtras.h

321 ↗

(On Diff #67916)

Yeah we can talk about that later.

One quick argument of not naming it to "filter" is that, it's so general that people may think of other possibilities by looking at the name, e.g. in-place filtering of a container or something.

llvm/trunk/include/llvm/ADT/STLExtras.h

 #include <cassert>
 #include <cstddef> // for std::size_t
 #include <cstdlib> // for qsort
 #include <functional>
 #include <iterator>
 #include <memory>
 #include <utility> // for std::pair
 
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Compiler.h"
 
 namespace llvm {
+namespace detail {
+
+template <typename RangeT>
+using IterOfRange = decltype(std::begin(std::declval<RangeT>()));
+
+} // End detail namespace
 
 //===----------------------------------------------------------------------===//
 //     Extra additions to <functional>
 //===----------------------------------------------------------------------===//
 
 template<class Ty>
 struct identity : public std::unary_function<Ty, Ty> {
   Ty &operator()(Ty &self) const {
auto reverse(
     ContainerTy &&C,
     typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
     -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
                            llvm::make_reverse_iterator(std::begin(C)))) {
   return make_range(llvm::make_reverse_iterator(std::end(C)),
                     llvm::make_reverse_iterator(std::begin(C)));
 }
 
+/// An iterator adaptor that filters the elements of given inner iterators.
+///
+/// The predicate parameter should be a callable object that accepts the wrapped
+/// iterator's reference type and returns a bool. When incrementing or
+/// decrementing the iterator, it will call the predicate on each element and
+/// skip any where it returns false.
+///
+/// \code
+///   int A[] = { 1, 2, 3, 4 };
+///   auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
+///   // R contains { 1, 3 }.
+/// \endcode
+template <typename WrappedIteratorT, typename PredicateT>
+class filter_iterator
+    : public iterator_adaptor_base<
+          filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
+          typename std::common_type<
+              std::forward_iterator_tag,
+              typename std::iterator_traits<
+                  WrappedIteratorT>::iterator_category>::type> {
+  using BaseT = iterator_adaptor_base<
+      filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
+      typename std::common_type<
+          std::forward_iterator_tag,
+          typename std::iterator_traits<WrappedIteratorT>::iterator_category>::
+          type>;
+
+  struct PayloadType {
+    WrappedIteratorT End;
+    PredicateT Pred;
+  };
+
+  Optional<PayloadType> Payload;
+
+  void findNextValid() {
+    assert(Payload && "Payload should be engaged when findNextValid is called");
+    while (this->I != Payload->End && !Payload->Pred(*this->I))
+      BaseT::operator++();
+  }
+
+  // Construct the begin iterator. The begin iterator requires to know where end
+  // is, so that it can properly stop when it hits end.
+  filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
+      : BaseT(std::move(Begin)),
+        Payload(PayloadType{std::move(End), std::move(Pred)}) {
+    findNextValid();
+  }
+
+  // Construct the end iterator. It's not incrementable, so Payload doesn't
+  // have to be engaged.
+  filter_iterator(WrappedIteratorT End) : BaseT(End) {}
+
+public:
+  using BaseT::operator++;
+
+  filter_iterator &operator++() {
+    BaseT::operator++();
+    findNextValid();
+    return *this;
+  }
+
+  template <typename RT, typename PT>
+  friend iterator_range<filter_iterator<detail::IterOfRange<RT>, PT>>
+  make_filter_range(RT &&, PT);
+};
+
+/// Convenience function that takes a range of elements and a predicate,
+/// and return a new filter_iterator range.
+///
+/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
+/// lifetime of that temporary is not kept by the returned range object, and the
+/// temporary is going to be dropped on the floor after the make_iterator_range
+/// full expression that contains this function call.
+template <typename RangeT, typename PredicateT>
+iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
+make_filter_range(RangeT &&Range, PredicateT Pred) {
+  using FilterIteratorT =
+      filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
+  return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
+                                    std::end(std::forward<RangeT>(Range)),
+                                    std::move(Pred)),
+                    FilterIteratorT(std::end(std::forward<RangeT>(Range))));
+}
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <utility>
 //===----------------------------------------------------------------------===//
 
 /// \brief Function object to check whether the first component of a std::pair
 /// compares less than the first component of another std::pair.
 struct less_first {
   template <typename T> bool operator()(const T &lhs, const T &rhs) const {

llvm/trunk/include/llvm/ADT/iterator.h

: public iterator_facade_base<DerivedT, IteratorCategoryT, T,
                                   DifferenceTypeT, PointerT, ReferenceT> {
   typedef typename iterator_adaptor_base::iterator_facade_base BaseT;
 
 protected:
   WrappedIteratorT I;
 
   iterator_adaptor_base() = default;
 
-  template <typename U>
-  explicit iterator_adaptor_base(
-      U &&u,
-      typename std::enable_if<
-          !std::is_base_of<typename std::remove_cv<
-                               typename std::remove_reference<U>::type>::type,
-                           DerivedT>::value,
-          int>::type = 0)
-      : I(std::forward<U &&>(u)) {}
+  explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) {}
 
   const WrappedIteratorT &wrapped() const { return I; }
 
 public:
   typedef DifferenceTypeT difference_type;
 
   DerivedT &operator+=(difference_type n) {
     static_assert(

llvm/trunk/unittests/Support/IteratorTest.cpp

for (int i = 0; i < 4; ++i) {
     EXPECT_EQ(Begin, I - i);
 
     test_iterator K = I++;
     EXPECT_EQ(K, std::prev(I));
   }
   EXPECT_EQ(End, I);
 }
 
+TEST(FilterIteratorTest, Lambda) {
+  auto IsOdd = [](int N) { return N % 2 == 1; };
+  int A[] = {0, 1, 2, 3, 4, 5, 6};
+  auto Range = make_filter_range(A, IsOdd);
+  SmallVector<int, 3> Actual(Range.begin(), Range.end());
+  EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
+}
+
+TEST(FilterIteratorTest, CallableObject) {
+  int Counter = 0;
+  struct Callable {
+    int &Counter;
+
+    Callable(int &Counter) : Counter(Counter) {}
+
+    bool operator()(int N) {
+      Counter++;
+      return N % 2 == 1;
+    }
+  };
+  Callable IsOdd(Counter);
+  int A[] = {0, 1, 2, 3, 4, 5, 6};
+  auto Range = make_filter_range(A, IsOdd);
+  EXPECT_EQ(2, Counter);
+  SmallVector<int, 3> Actual(Range.begin(), Range.end());
+  EXPECT_GE(Counter, 7);
+  EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
+}
+
+TEST(FilterIteratorTest, FunctionPointer) {
+  bool (*IsOdd)(int) = [](int N) { return N % 2 == 1; };
+  int A[] = {0, 1, 2, 3, 4, 5, 6};
+  auto Range = make_filter_range(A, IsOdd);
+  SmallVector<int, 3> Actual(Range.begin(), Range.end());
+  EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
+}
+
+TEST(FilterIteratorTest, Composition) {
+  auto IsOdd = [](int N) { return N % 2 == 1; };
+  std::unique_ptr<int> A[] = {make_unique<int>(0), make_unique<int>(1),
+                              make_unique<int>(2), make_unique<int>(3),
+                              make_unique<int>(4), make_unique<int>(5),
+                              make_unique<int>(6)};
+  using PointeeIterator = pointee_iterator<std::unique_ptr<int> *>;
+  auto Range = make_filter_range(
+      make_range(PointeeIterator(std::begin(A)), PointeeIterator(std::end(A))),
+      IsOdd);
+  SmallVector<int, 3> Actual(Range.begin(), Range.end());
+  EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
+}
+
+TEST(FilterIteratorTest, InputIterator) {
+  struct InputIterator
+      : iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag> {
+    using BaseT =
+        iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag>;
+
+    InputIterator(int *It) : BaseT(It) {}
+  };
+
+  auto IsOdd = [](int N) { return N % 2 == 1; };
+  int A[] = {0, 1, 2, 3, 4, 5, 6};
+  auto Range = make_filter_range(
+      make_range(InputIterator(std::begin(A)), InputIterator(std::end(A))),
+      IsOdd);
+  SmallVector<int, 3> Actual(Range.begin(), Range.end());
+  EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
+}
+
 } // anonymous namespace