Improve the genericity of `llvm::enumerate()`.

[zturner]

Summary

This all started when I tried to store the results of an enumerate range into a vector and then sort according to the value. In doing so, I found out that enumerate was insufficiently generic, as it did not support iterator_facade_base and so you couldn't even call std::distance() on two of its iterators.

Ideally, one should not have to write this code:

std::vector<std::pair<size_t, std::string>> Items;
for (auto X : enumerate(Range))
  Items.push_back(std::make_pair(X.Index, X.Value));

just to get something they can sort. It would be nice if you could write one line like std::vector<std::pair<size_t, std::string>>(enumerate(X).begin(), enumerate(X).end());

But the value type of an enumerate isn't even a pair, so you don't know how to specify it (if that was what you wanted). We'd like to make use of type deduction.

To make all this work I re-wrote enumerate to support iterator_facade_base, and I add an additional helper function called to_vector which you can now call as auto Results = to_vector<N>(enumerate(Range)); (replacing enumerate with whatever adapter you want), and it will return you a SmallVector<T, N> where T is the value type of the original range.

[dblaikie]

llvm/include/llvm/ADT/STLExtras.h

894–898 ↗

(On Diff #91436)

Perhaps not relevant now - but eventually this might want to be generalized to arbitrary range conversion (conversion to a std::set? etc... )

1040 ↗

(On Diff #91436)

Usually op overloads should be non-members whenever possible (ensures implicit conversions happen symmetrically for left and right operands) - though perhaps that isn't possible with the iterator facade helper?

1045 ↗

(On Diff #91436)

This doesn't look valid - is it? (I think R is a type, not a variable, so shouldn't be valid in these expressions)

1048 ↗

(On Diff #91436)

Missing return? This should've warned/broken the build/crashed-at-O0, etc? Was there some missing test coverage?

1062 ↗

(On Diff #91436)

If the index of the end is going to be -1, it could be used to quickly catch a few mistakes with iterators - assert(index != -1) in operator++, for example?

1065–1067 ↗

(On Diff #91436)

Once there's a generic utility function for all ranges as you've provided with to_vector - is this member still useful/necessary? (indeed this function seems to be untested - the test case exercises the generic to_vector instead)

[bryant]

llvm/include/llvm/ADT/STLExtras.h

1024 ↗

(On Diff #91436)

can iterator_adaptor_base be used for this? it looks like its default template params fit.

[zturner]

Will address the rest of the comments in a later followup.

llvm/include/llvm/ADT/STLExtras.h

1062 ↗

(On Diff #91436)

-1 is sufficient to be end, but not necessary. For example, when ++'ing a valid iterator, you don't know if it's end without having the end of the backing container. So in that case index will just be whatever. Such an assert would still be fine, but it would only guarantee that you're not incrementing the result of std::end(enumerate(R)), and it wouldn't trigger when you increment an iterator past it's actual end.

1065–1067 ↗

(On Diff #91436)

This was from some early attempts that is not needed anymore. I meant to remove it, but forgot. Thanks for catching it.

[zturner]

A few improvements as suggested by blaikie@

[zturner]

llvm/include/llvm/ADT/STLExtras.h

1024 ↗

(On Diff #91436)

I was not able to make this work well. iterator_adapter_base stores a copy of the iterator While I also want to store a copy of the iterator, I also need to store an index. And I need both to be part of the iterator's value_type. So if I want to use iterator_adapter_base, It becomes wasteful because I store a copy of the iterator twice. Once in iterator_adapter_base and again in the result member variable.

[chandlerc]

llvm/include/llvm/ADT/STLExtras.h

891–897 ↗

(On Diff #91484)

Why not a range constructor for SmallVector?

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

 #include <cstdlib> // for qsort
 #include <functional>
 #include <iterator>
 #include <memory>
 #include <tuple>
 #include <utility> // for std::pair
 
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
 
 namespace llvm {
 
 // Only used by compiler if both template types are the same.  Useful when
 // using SFINAE to test for the existence of member functions.
 template <typename T, T> struct SameType;
 
 namespace detail {
 
 template <typename RangeT>
 using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
 
+template <typename RangeT>
+using ValueOfRange = typename std::remove_reference<decltype(
+    *std::begin(std::declval<RangeT &>()))>::type;
+
 } // End detail namespace
 
 //===----------------------------------------------------------------------===//
 //     Extra additions to <functional>
 //===----------------------------------------------------------------------===//
 
 template<class Ty>
 struct identity : public std::unary_function<Ty, Ty> {

 
 /// Provide wrappers to std::partition which take ranges instead of having to
 /// pass begin/end explicitly.
 template <typename R, typename UnaryPredicate>
 auto partition(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) {
   return std::partition(std::begin(Range), std::end(Range), P);
 }
 
+/// \brief Given a range of type R, iterate the entire range and return a
+/// SmallVector with elements of the vector.  This is useful, for example,
+/// when you want to iterate a range and then sort the results.
+template <unsigned Size, typename R>
+SmallVector<detail::ValueOfRange<R>, Size> to_vector(R &&Range) {
+  return {std::begin(Range), std::end(Range)};
+}
+
 /// Provide a container algorithm similar to C++ Library Fundamentals v2's
 /// `erase_if` which is equivalent to:
 ///
 ///   C.erase(remove_if(C, pred), C.end());
 ///
 /// This version works for any container with an erase method call accepting
 /// two iterators.
 template <typename Container, typename UnaryPredicate>
template <typename T> struct deref {
   auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
     assert(lhs);
     assert(rhs);
     return func(*lhs, *rhs);
   }
 };
 
 namespace detail {
-template <typename R> class enumerator_impl {
-public:
-  template <typename X> struct result_pair {
-    result_pair(std::size_t Index, X Value) : Index(Index), Value(Value) {}
+template <typename R> class enumerator_iter;
+
+template <typename R> struct result_pair {
+  friend class enumerator_iter<R>;
 
-    const std::size_t Index;
-    X Value;
-  };
+  result_pair() : Index(-1) {}
+  result_pair(std::size_t Index, IterOfRange<R> Iter)
+      : Index(Index), Iter(Iter) {}
+
+  result_pair<R> &operator=(const result_pair<R> &Other) {
+    Index = Other.Index;
+    Iter = Other.Iter;
+    return *this;
+  }
+
+  std::size_t index() const { return Index; }
+  const ValueOfRange<R> &value() const { return *Iter; }
+  ValueOfRange<R> &value() { return *Iter; }
+
+private:
+  std::size_t Index;
+  IterOfRange<R> Iter;
 
-  class iterator {
-    typedef
-        typename std::iterator_traits<IterOfRange<R>>::reference iter_reference;
-    typedef result_pair<iter_reference> result_type;
+template <typename R>
+class enumerator_iter
+    : public iterator_facade_base<
+          enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
+          typename std::iterator_traits<IterOfRange<R>>::difference_type,
+          typename std::iterator_traits<IterOfRange<R>>::pointer,
+          typename std::iterator_traits<IterOfRange<R>>::reference> {
+  using result_type = result_pair<R>;
 
-  public:
-    iterator(IterOfRange<R> &&Iter, std::size_t Index)
-        : Iter(Iter), Index(Index) {}
+  enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
+      : Result(Index, Iter) {}
 
-    result_type operator*() const { return result_type(Index, *Iter); }
+  result_type &operator*() { return Result; }
+  const result_type &operator*() const { return Result; }
 
-    iterator &operator++() {
-      ++Iter;
-      ++Index;
-      return *this;
-    }
+  enumerator_iter<R> &operator++() {
+    assert(Result.Index != -1);
+    ++Result.Iter;
+    ++Result.Index;
 
-    bool operator!=(const iterator &RHS) const { return Iter != RHS.Iter; }
+  bool operator==(const enumerator_iter<R> &RHS) const {
+    // Don't compare indices here, only iterators.  It's possible for an end
+    // iterator to have different indices depending on whether it was created
+    // by calling std::end() versus incrementing a valid iterator.
+    return Result.Iter == RHS.Result.Iter;
+  }
+
+  enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
+    Result = Other.Result;
+    return *this;
+  }
 
-  private:
-    IterOfRange<R> Iter;
-    std::size_t Index;
-  };
+  result_type Result;
 
+template <typename R> class enumerator {
 public:
-  explicit enumerator_impl(R &&Range) : Range(std::forward<R>(Range)) {}
+  explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
 
-  iterator begin() { return iterator(std::begin(Range), 0); }
-  iterator end() { return iterator(std::end(Range), std::size_t(-1)); }
+  enumerator_iter<R> begin() {
+    return enumerator_iter<R>(0, std::begin(TheRange));
+  }
+  enumerator_iter<R> end() {
+    return enumerator_iter<R>(-1, std::end(TheRange));
+  }
 
 private:
-  R Range;
+  R TheRange;
 };
 }
 
 /// Given an input range, returns a new range whose values are are pair (A,B)
 /// such that A is the 0-based index of the item in the sequence, and B is
 /// the value from the original sequence.  Example:
 ///
 /// std::vector<char> Items = {'A', 'B', 'C', 'D'};
 /// for (auto X : enumerate(Items)) {
 ///   printf("Item %d - %c\n", X.Index, X.Value);
 /// }
 ///
 /// Output:
 ///   Item 0 - A
 ///   Item 1 - B
 ///   Item 2 - C
 ///   Item 3 - D
 ///
-template <typename R> detail::enumerator_impl<R> enumerate(R &&Range) {
-  return detail::enumerator_impl<R>(std::forward<R>(Range));
+template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
+  return detail::enumerator<R>(std::forward<R>(TheRange));
 }
 
 namespace detail {
 template <typename F, typename Tuple, std::size_t... I>
 auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>)
     -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
   return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
 }

llvm/trunk/unittests/ADT/STLExtrasTest.cpp

 TEST(STLExtrasTest, EnumerateLValue) {
   // Test that a simple LValue can be enumerated and gives correct results with
   // multiple types, including the empty container.
   std::vector<char> foo = {'a', 'b', 'c'};
   typedef std::pair<std::size_t, char> CharPairType;
   std::vector<CharPairType> CharResults;
 
   for (auto X : llvm::enumerate(foo)) {
-    CharResults.emplace_back(X.Index, X.Value);
+    CharResults.emplace_back(X.index(), X.value());
   }
   ASSERT_EQ(3u, CharResults.size());
   EXPECT_EQ(CharPairType(0u, 'a'), CharResults[0]);
   EXPECT_EQ(CharPairType(1u, 'b'), CharResults[1]);
   EXPECT_EQ(CharPairType(2u, 'c'), CharResults[2]);
 
   // Test a const range of a different type.
   typedef std::pair<std::size_t, int> IntPairType;
   std::vector<IntPairType> IntResults;
   const std::vector<int> bar = {1, 2, 3};
   for (auto X : llvm::enumerate(bar)) {
-    IntResults.emplace_back(X.Index, X.Value);
+    IntResults.emplace_back(X.index(), X.value());
   }
   ASSERT_EQ(3u, IntResults.size());
   EXPECT_EQ(IntPairType(0u, 1), IntResults[0]);
   EXPECT_EQ(IntPairType(1u, 2), IntResults[1]);
   EXPECT_EQ(IntPairType(2u, 3), IntResults[2]);
 
   // Test an empty range.
   IntResults.clear();
   const std::vector<int> baz{};
   for (auto X : llvm::enumerate(baz)) {
-    IntResults.emplace_back(X.Index, X.Value);
+    IntResults.emplace_back(X.index(), X.value());
   }
   EXPECT_TRUE(IntResults.empty());
 }
 
 TEST(STLExtrasTest, EnumerateModifyLValue) {
   // Test that you can modify the underlying entries of an lvalue range through
   // the enumeration iterator.
   std::vector<char> foo = {'a', 'b', 'c'};
 
   for (auto X : llvm::enumerate(foo)) {
-    ++X.Value;
+    ++X.value();
   }
   EXPECT_EQ('b', foo[0]);
   EXPECT_EQ('c', foo[1]);
   EXPECT_EQ('d', foo[2]);
 }
 
 TEST(STLExtrasTest, EnumerateRValueRef) {
   // Test that an rvalue can be enumerated.
   typedef std::pair<std::size_t, int> PairType;
   std::vector<PairType> Results;
 
   auto Enumerator = llvm::enumerate(std::vector<int>{1, 2, 3});
 
   for (auto X : llvm::enumerate(std::vector<int>{1, 2, 3})) {
-    Results.emplace_back(X.Index, X.Value);
+    Results.emplace_back(X.index(), X.value());
   }
 
   ASSERT_EQ(3u, Results.size());
   EXPECT_EQ(PairType(0u, 1), Results[0]);
   EXPECT_EQ(PairType(1u, 2), Results[1]);
   EXPECT_EQ(PairType(2u, 3), Results[2]);
 }
 
 TEST(STLExtrasTest, EnumerateModifyRValue) {
   // Test that when enumerating an rvalue, modification still works (even if
   // this isn't terribly useful, it at least shows that we haven't snuck an
   // extra const in there somewhere.
   typedef std::pair<std::size_t, char> PairType;
   std::vector<PairType> Results;
 
   for (auto X : llvm::enumerate(std::vector<char>{'1', '2', '3'})) {
-    ++X.Value;
-    Results.emplace_back(X.Index, X.Value);
+    ++X.value();
+    Results.emplace_back(X.index(), X.value());
   }
 
   ASSERT_EQ(3u, Results.size());
   EXPECT_EQ(PairType(0u, '2'), Results[0]);
   EXPECT_EQ(PairType(1u, '3'), Results[1]);
   EXPECT_EQ(PairType(2u, '4'), Results[2]);
 }
 
TEST(STLExtrasTest, CountAdaptor) {
   v.push_back(1);
 
   EXPECT_EQ(3, count(v, 1));
   EXPECT_EQ(2, count(v, 2));
   EXPECT_EQ(1, count(v, 3));
   EXPECT_EQ(1, count(v, 4));
 }
 
+TEST(STLExtrasTest, ToVector) {
+  std::vector<char> v = {'a', 'b', 'c'};
+  auto Enumerated = to_vector<4>(enumerate(v));
+  ASSERT_EQ(3, Enumerated.size());
+  for (size_t I = 0; I < v.size(); ++I) {
+    EXPECT_EQ(I, Enumerated[I].index());
+    EXPECT_EQ(v[I], Enumerated[I].value());
+  }
+}
+
 TEST(STLExtrasTest, ConcatRange) {
   std::vector<int> Expected = {1, 2, 3, 4, 5, 6, 7, 8};
   std::vector<int> Test;
 
   std::vector<int> V1234 = {1, 2, 3, 4};
   std::list<int> L56 = {5, 6};
   SmallVector<int, 2> SV78 = {7, 8};
 

llvm/trunk/utils/TableGen/GlobalISelEmitter.cpp

 private:
   const CodeGenInstruction *I;
   const InstructionMatcher &Matched;
   std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
 
   /// True if the instruction can be built solely by mutating the opcode.
   bool canMutate() const {
     for (const auto &Renderer : enumerate(OperandRenderers)) {
-      if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.Value)) {
+      if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
         if (Matched.getOperand(Copy->getSymbolicName()).getOperandIndex() !=
-            Renderer.Index)
+            Renderer.index())
           return false;
       } else
         return false;
     }
 
     return true;
   }