[Support] Add casting iterator adapters

[hamzasood]

Summary

This patch adds a simple type that lets you create a functor from a function at compile time.

While working on Clang, I needed a way to create an llvm::filter_iterator that filters based on the dynamic type as determined by llvm::isa. As far as I'm aware, the best way to do this currently (without lambdas as they'd make the iterator type unutterable) is:

llvm::make_filter_range(MyRange, static_cast<bool(*)(Base *)>(&isa<Derived>))

That's problematic because the iterator object ends up storing a function pointer; if the compiler can't follow the iterator's path from creation to use then it probably won't be able to get round the unnecessary indirection. This new type solves that by storing the function address as part of the object type, so there's no runtime overhead.

[dblaikie]

I'd probably still vote in favor of a lambda, even if it made the iterator
type unutterable - do you have an example where that makes things
especially difficult to read?

[hamzasood]

There’re a lot of places where you need a type that you can write down. E.g. function return type.

[timshen]

Is there a real life example that justifies the optimization?

[hamzasood]

The previous revision was an unnecessarily general solution to a specific problem.

I think there's a need for a special kind of filter_iterator that filters and casts based on the dynamic type of the elements, as determined by llvm::dyn_cast. In Clang there're at least 4 custom-written, entirely separate iterators that do just this: specific_decl_itererator, filtered_decl_iterator, specific_clause_iterator, specific_attr_iterator. And I'm at the point where I need to add yet another one.

This patch contains a generic iterator that yields Derived * from Base * by dyn_casting each element and filtering out those element whose dynamic type doesn't match.

[dblaikie]

include/llvm/Support/CastingIterators.h

40

I'd probably skip this extra generality of providing an extra predicate on top of the isa/dyn_cast filter. Users can implement that with another filtering iterator if needed.

[hamzasood]

Removed the extra predicate customisation point.

[fhahn]

@hamzasood are you still looking into pushing this patch? It would be helpful if you could show a few cases where this new utility helps with existing code in LLVM/Clang, preferably as a separate patch linked to this one.

Marking as requested changes to clear up review queue.

include/llvm/Support/CastingIterators.h

+//===- llvm/Support/CastingIterators.h ---------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_CASTING_ITERATORS_H
+#define LLVM_SUPPORT_CASTING_ITERATORS_H
+
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Casting.h"
+#include <utility>
+
+namespace llvm {
+
+namespace detail {
+
+/// Functor used as the predicate in a dyn_cast_iterator.
+template<typename DerivedT>
+struct dyn_predicate {
+  template<typename BaseT>
+  bool operator()(const BaseT *Base) const { return isa<DerivedT>(Base); }
+};
+
+} // end namespace detail
+
+/// Iterator adapter that 'dyn_cast's the elements of the given inner iterators
+/// and filters out the failed casts.
+template<typename WrappedIteratorT, typename DerivedT>
+struct dyn_cast_iterator
+    : filter_iterator<WrappedIteratorT, detail::dyn_predicate<DerivedT>> {
+  using FilterIt =
+      filter_iterator<WrappedIteratorT, detail::dyn_predicate<DerivedT>>;
+
+  dyn_cast_iterator(WrappedIteratorT Begin, WrappedIteratorT End)
+      : FilterIt(std::move(Begin), std::move(End), /* predicate */{}) {}
+
+  auto operator*() const -> decltype(cast<DerivedT>(FilterIt::operator*())) {
+    // Perform the cast on dereference.
+    // The filtering ensures that the dynamic type is correct.
+    return cast<DerivedT>(FilterIt::operator*());
+  }
+};
+
+/// Make a dyn_cast_iterator and infer the wrapped iterator type.
+template<typename DerivedT, typename WrappedIteratorT>
+dyn_cast_iterator<WrappedIteratorT, DerivedT>
+make_dyn_cast_iterator(WrappedIteratorT Begin, WrappedIteratorT End) {
+  return dyn_cast_iterator<WrappedIteratorT, DerivedT>(
+             std::move(Begin), std::move(End));
+}
+
+/// Make a dyn_cast_iterator range from the input range.
+template<typename DerivedT, typename RangeT>
+auto make_dyn_cast_range(const RangeT &Rng)
+    -> iterator_range<dyn_cast_iterator<decltype(std::begin(Rng)), DerivedT>> {
+  using IterT =
+      dyn_cast_iterator<decltype(std::begin(Rng)), DerivedT>;
+
+  return make_range(IterT(std::begin(Rng), std::end(Rng)),
+                    IterT(std::end(Rng), std::end(Rng)));
+}
+
+} // end namespace llvm
+
+#endif // LLVM_SUPPORT_CASTING_ITERATORS_H

unittests/Support/CMakeLists.txt

   CachePruningTest.cpp
   CrashRecoveryTest.cpp
   Casting.cpp
+  CastingIterators.cpp
   CheckedArithmeticTest.cpp
   Chrono.cpp
   CommandLineTest.cpp

unittests/Support/CastingIterators.cpp

+//===- llvm/unittest/Support/CastingIterators.h -----------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CastingIterators.h"
+#include "gtest/gtest.h"
+
+#include <array>
+#include <cassert>
+
+using namespace llvm;
+
+namespace {
+
+struct Number {
+  unsigned getVal() const { return Val; }
+  virtual ~Number() = default;
+protected:
+  Number(unsigned Val) : Val(Val) {}
+private:
+  unsigned Val;
+};
+
+struct EvenNumber : Number {
+  EvenNumber(unsigned Val) : Number(Val) {
+    assert((Val % 2) == 0 && "Not an even number!");
+  }
+  static bool classof(const Number *Num) { return (Num->getVal() % 2) == 0; }
+};
+
+struct OddNumber : Number {
+  OddNumber(unsigned Val) : Number(Val) {
+    assert((Val % 2) != 0 && "Not an odd number!");
+  }
+  static bool classof(const Number *Num) { return (Num->getVal() % 2) != 0; }
+};
+
+
+
+class DynCastIterTest : public testing::Test {
+protected:
+  std::array<Number *, 10> Nums;
+
+  void SetUp() override {
+    for (std::size_t i = 1; i <= Nums.size(); ++i) {
+      Nums[i - 1] = (i % 2 == 0)
+                        ? static_cast<Number *>(new EvenNumber(i))
+                        : static_cast<Number *>(new OddNumber(i));
+    }
+  }
+
+  void TearDown() override {
+    for (auto *N : Nums)
+      delete N;
+  }
+};
+
+TEST_F(DynCastIterTest, Simple) {
+  auto It = make_dyn_cast_iterator<OddNumber>(Nums.begin(), Nums.end());
+  auto End = make_dyn_cast_iterator<OddNumber>(Nums.end(), Nums.end());
+
+  EXPECT_NE(It, End);
+  ASSERT_EQ((*It)->getVal(), 1u);
+
+  ++It;
+  EXPECT_NE(It, End);
+  ASSERT_EQ((*It)->getVal(), 3u);
+
+  ++It;
+  EXPECT_NE(It, End);
+  ASSERT_EQ((*It)->getVal(), 5u);
+
+  ++It;
+  EXPECT_NE(It, End);
+  ASSERT_EQ((*It)->getVal(), 7u);
+
+  ++It;
+  EXPECT_NE(It, End);
+  ASSERT_EQ((*It)->getVal(), 9u);
+
+  ++It;
+  ASSERT_EQ(It, End);
+}
+
+TEST_F(DynCastIterTest, Range) {
+  for (EvenNumber *N : make_dyn_cast_range<EvenNumber>(Nums))
+    (void)N;
+}
+
+} // end anonymous namespace