[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

No need for '\brief'.

242–244

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

Why not support operator--? It seems easy?

252

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

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

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

302–309

This needs its own doxygen comment.

unittests/Support/IteratorTest.cpp

106

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

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

106

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

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

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

274–277

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.

284–287

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

You should move all of these.

311

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

313

As above, this should be PredicateT.

316

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

"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>>

[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

...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

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

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

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

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

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

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

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

304

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

friend void foo() {
  ...
}

unittests/Support/IteratorTest.cpp

152–154

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

152–154

Right. Removed.

[dblaikie]

include/llvm/ADT/STLExtras.h

310

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

166

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

304

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

310

Added a comment with "FIXME".

unittests/Support/IteratorTest.cpp

166

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

248

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

314

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

314

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.

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/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Compiler.h"
 
 namespace llvm {
 
 //===----------------------------------------------------------------------===//
 //     Extra additions to <functional>
 //===----------------------------------------------------------------------===//
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 };
+///   const auto R = make_filter_range(A, A + 4,
+///                                    [](int A) { return A % 2 == 1; });
+///   // R contains { 1, 3 }.
+/// \endcode
+template <typename WrappedIteratorT, typename Predicate>
+class filter_iterator
+    : public iterator_adaptor_base<
+          filter_iterator<WrappedIteratorT, Predicate>, WrappedIteratorT,
+          typename std::common_type<
+              std::bidirectional_iterator_tag,
+              typename std::iterator_traits<
+                  WrappedIteratorT>::iterator_category>::type,
+          typename std::iterator_traits<WrappedIteratorT>::value_type,
+          typename std::iterator_traits<WrappedIteratorT>::difference_type,
+          typename std::iterator_traits<WrappedIteratorT>::pointer,
+          typename std::iterator_traits<WrappedIteratorT>::reference> {
+  using IteratorCategoryT = typename std::common_type<
+      std::bidirectional_iterator_tag,
+      typename std::iterator_traits<WrappedIteratorT>::iterator_category>::type;
+  using BaseT = iterator_adaptor_base<
+      filter_iterator<WrappedIteratorT, Predicate>, WrappedIteratorT,
+      IteratorCategoryT,
+      typename std::iterator_traits<WrappedIteratorT>::value_type,
+      typename std::iterator_traits<WrappedIteratorT>::difference_type,
+      typename std::iterator_traits<WrappedIteratorT>::pointer,
+      typename std::iterator_traits<WrappedIteratorT>::reference>;
+
+  WrappedIteratorT End;
+  Predicate Pred;
+
+  void findNextValid() {
+    while (this->I != End && !Pred(*this->I))
+      BaseT::operator++();
+  }
+
+public:
+  filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, Predicate Pred)
+      : BaseT(Begin), End(End), Pred(Pred) {
+    findNextValid();
+  }
+
+  using BaseT::operator++;
+  using BaseT::operator--;
+
+  filter_iterator &operator++() {
+    BaseT::operator++();
+    findNextValid();
+    return *this;
+  }
+
+  filter_iterator &operator--() {
+    static_assert(
+        std::is_same<std::bidirectional_iterator_tag, IteratorCategoryT>::value,
+        "operator--() reuiqres the underlying type to be at least "
+        "bidirectional");
+    BaseT::operator--();
+    // Hopefully users don't call operator--() on Begin. They will be doomed.
+    while (!Pred(*this->I))
+      BaseT::operator--();
+    return *this;
+  }
+};
+
+/// \brief Convenience function that takes a range of elements and a predicate,
+/// and return a new filter_iterator range.
+template <typename WrappedIteratorT, typename Predicate>
+iterator_range<filter_iterator<WrappedIteratorT, Predicate>>
+make_filter_range(iterator_range<WrappedIteratorT> Range,
+                  const Predicate &Pred) {
+  using IterT = filter_iterator<WrappedIteratorT, Predicate>;
+  return make_range(IterT(Range.begin(), Range.end(), Pred),
+                    IterT(Range.end(), Range.end(), Pred));
+}
+
 //===----------------------------------------------------------------------===//
 //     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 {

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(

unittests/Support/IteratorTest.cpp

 //===- IteratorTest.cpp - Unit tests for iterator utilities ---------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "gtest/gtest.h"
 
+#include <functional>
+
 using namespace llvm;
 
 namespace {
 
 TEST(PointeeIteratorTest, Basic) {
   int arr[4] = { 1, 2, 3, 4 };
   SmallVector<int *, 4> V;
   V.push_back(&arr[0]);
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 a) { return a % 2 == 1; };
+  int a[] = {0, 1, 2, 3, 4, 5, 6};
+  const auto Range = make_filter_range(make_range(a, a + 7), IsOdd);
+  ASSERT_EQ(3, std::distance(Range.begin(), Range.end()));
+  SmallVector<int, 3> Actual(Range.begin(), Range.end());
+  EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
+}
+
+TEST(FilterIteratorTest, StdFunction) {
+  std::function<bool(int)> IsOdd = [](int a) { return a % 2 == 1; };
+  int a[] = {0, 1, 2, 3, 4, 5, 6};
+  const auto Range = make_filter_range(make_range(a, a + 7), IsOdd);
+  ASSERT_EQ(3, std::distance(Range.begin(), Range.end()));
+  SmallVector<int, 3> Actual(Range.begin(), Range.end());
+  EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
+}
+
+TEST(FilterIteratorTest, FunctionPointer) {
+  bool (*IsOdd)(int) = [](int a) { return a % 2 == 1; };
+  int a[] = {0, 1, 2, 3, 4, 5, 6};
+  const auto Range = make_filter_range(make_range(a, a + 7), IsOdd);
+  ASSERT_EQ(3, std::distance(Range.begin(), Range.end()));
+  SmallVector<int, 3> Actual(Range.begin(), Range.end());
+  EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
+}
+
+TEST(FilterIteratorTest, Composition) {
+  const auto IsOdd = [](int a) { return a % 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> *>;
+  const auto Range = make_filter_range(
+      make_range(PointeeIterator(a), PointeeIterator(a + 7)), IsOdd);
+  ASSERT_EQ(3, std::distance(Range.begin(), Range.end()));
+  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 a) { return a % 2 == 1; };
+  int a[] = {0, 1, 2, 3, 4, 5, 6};
+  const auto Range = make_filter_range(
+      make_range(InputIterator(a), InputIterator(a + 7)), IsOdd);
+  SmallVector<int, 3> Actual(Range.begin(), Range.end());
+  EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
+}
+
+TEST(FilterIteratorTest, Decrement) {
+  auto IsOdd = [](int a) { return a % 2 == 1; };
+  int a[] = {0, 1, 2, 3, 4, 5, 6};
+  auto Iter = make_filter_range(make_range(a, a + 7), IsOdd).begin();
+  EXPECT_EQ(1, *Iter);
+  ++Iter;
+  EXPECT_EQ(3, *Iter);
+  --Iter;
+  EXPECT_EQ(1, *Iter);
+  std::advance(Iter, 2);
+  EXPECT_EQ(5, *Iter);
+  --Iter;
+  EXPECT_EQ(3, *Iter);
+}
+
 } // anonymous namespace