[llvm][ADT] Allow using structured bindings with `llvm::enumerate`

[zero9178]

Summary

This patch adds the ability to deconstruct the value_type returned by llvm::enumarate into index and value of the wrapping range. Main use case is the common occurence of using it during loop iteration. After this patch it'd then be possible to write code such as:

for (auto [index, value] : enumerate(container)) {
   ...
}

where index is the current index and value a reference to elements in the given container.

---

The order of index first, before value was mainly chosen to stay consistent with the current documentation of llvm::enumerate, but I'd personally be open to (and would have a slight preference of) swapping the order of the two as well.

[kuhar]

Neat!

The order of index first, before value was mainly chosen to stay consistent with the current documentation of llvm::enumerate, but I'd personally be open to (and would have a slight preference of) swapping the order of the two as well.

I'd *personally* prefer to keep it as index, value, because that's the order in python, rust, and swift.

llvm/unittests/ADT/STLExtrasTest.cpp

85–86

Can we also have a test that updates the value? I'm not sure if this is currently supported based on the get function.

[zero9178]

In D131486#3709825, @kuhar wrote:

Neat!

The order of index first, before value was mainly chosen to stay consistent with the current documentation of llvm::enumerate, but I'd personally be open to (and would have a slight preference of) swapping the order of the two as well.

I'd *personally* prefer to keep it as index, value, because that's the order in python, rust, and swift.

That's a very good argument as well. I shall keep the current state then.

llvm/unittests/ADT/STLExtrasTest.cpp

85–86

I did so already in line 81

[zero9178]

Fix a typo in one of the tests

[kuhar]

llvm/unittests/ADT/STLExtrasTest.cpp

84–87

We can simplify this sequence of checks to EXPECT_THAT(foobar, ElementsAre(4, 5, 6));

85–86

Can we move that test into this testcase then?

[zero9178]

Move modify test to corresponding test case

[zero9178]

• Make use of ElementsAre
• Also add test cases for rvalue refs.

[kuhar]

Looks good to me, but I'm not 100% sure about const/ref correctness. Please wait for a second approval before submitting (e.g., from @dblaikie).

llvm/unittests/ADT/STLExtrasTest.cpp

46

nit: I think it's more common to have this just after using namespace llvm;

142

I'm surprised this doesn't require auto&& [index, value], but this seems consistent with the existing behavior with X.value()

[zero9178]

llvm/unittests/ADT/STLExtrasTest.cpp

142

The part before the structured bindings (here the auto) surprisingly does not apply to the destructed elements (index and value) but to the unnamed variable that the range assigns to.
This unnamed variable is essentially equal to what was X in the loop above, hence it also works with auto without issues.

The types of index and value are actually derived from the std::tuple_element specializations and the return type of get.

[zero9178]

Addressed Review comments

[dblaikie]

Seems OK to me - thanks for checking!

llvm/include/llvm/ADT/STLExtras.h

template <typename R> struct result_pair {
   std::size_t index() const { return Index; }
   value_reference value() const { return *Iter; }
 
 private:
   std::size_t Index = std::numeric_limits<std::size_t>::max();
   IterOfRange<R> Iter;
 };
 
+template <std::size_t i, typename R>
+decltype(auto) get(const result_pair<R> &Pair) {
+  static_assert(i < 2);
+  if constexpr (i == 0) {
+    return Pair.index();
+  } else {
+    return Pair.value();
+  }
+}
+
 template <typename R>
 class enumerator_iter
     : public iterator_facade_base<enumerator_iter<R>, std::forward_iterator_tag,
                                   const result_pair<R>> {
   using result_type = result_pair<R>;
 
 public:
   explicit enumerator_iter(IterOfRange<R> EndIter)

 /// 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());
 /// }
 ///
+/// or using structured bindings:
+///
+/// for (auto [Index, Value] : enumerate(Items)) {
+///   printf("Item %d - %c\n", Index, Value);
+/// }
+///
 /// Output:
 ///   Item 0 - A
 ///   Item 1 - B
 ///   Item 2 - C
 ///   Item 3 - D
 ///
 template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
   return detail::enumerator<R>(std::forward<R>(TheRange));

 ///
 /// The std::pointer_traits<>::to_address(p) variations of these overloads has
 /// not been implemented.
 template <class Ptr> auto to_address(const Ptr &P) { return P.operator->(); }
 template <class T> constexpr T *to_address(T *P) { return P; }
 
 } // end namespace llvm
 
+namespace std {
+template <typename R>
+struct tuple_size<llvm::detail::result_pair<R>>
+    : std::integral_constant<std::size_t, 2> {};
+
+template <std::size_t i, typename R>
+struct tuple_element<i, llvm::detail::result_pair<R>>
+    : std::conditional<i == 0, std::size_t,
+                       typename llvm::detail::result_pair<R>::value_reference> {
+};
+
+} // namespace std
+
 #endif // LLVM_ADT_STLEXTRAS_H

llvm/unittests/ADT/STLExtrasTest.cpp

 //===- STLExtrasTest.cpp - Unit tests for STL extras ----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/STLExtras.h"
+#include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 #include <climits>
 #include <list>
 #include <vector>
 
 using namespace llvm;
 
+using testing::ElementsAre;
+
 namespace {
 
 int f(rank<0>) { return 0; }
 int f(rank<1>) { return 1; }
 int f(rank<2>) { return 2; }
 int f(rank<4>) { return 4; }
 
 TEST(STLExtrasTest, Rank) {
TEST(STLExtrasTest, Rank) {
   // But going past 3 should work fine.
   EXPECT_EQ(4, f(rank<4>()));
 
   // And we can even go higher and just fall back to the last overload.
   EXPECT_EQ(4, f(rank<5>()));
   EXPECT_EQ(4, f(rank<6>()));
 }
 
 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());
+  for (auto [index, value] : llvm::enumerate(foo)) {
+    CharResults.emplace_back(index, 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]);
+
+  EXPECT_THAT(CharResults,
+              ElementsAre(CharPairType(0u, 'a'), CharPairType(1u, 'b'),
+                          CharPairType(2u, 'c')));
 
   // 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());
+  for (auto [index, value] : llvm::enumerate(bar)) {
+    IntResults.emplace_back(index, 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]);
+  EXPECT_THAT(IntResults, ElementsAre(IntPairType(0u, 1), IntPairType(1u, 2),
+                                      IntPairType(2u, 3)));
 
   // Test an empty range.
   IntResults.clear();
   const std::vector<int> baz{};
-  for (auto X : llvm::enumerate(baz)) {
-    IntResults.emplace_back(X.index(), X.value());
+  for (auto [index, value] : llvm::enumerate(baz)) {
+    IntResults.emplace_back(index, 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();
   }
-  EXPECT_EQ('b', foo[0]);
-  EXPECT_EQ('c', foo[1]);
-  EXPECT_EQ('d', foo[2]);
+  EXPECT_THAT(foo, ElementsAre('b', 'c', 'd'));
+
+  // Also test if this works with structured bindings.
+  foo = {'a', 'b', 'c'};
+
+  for (auto [index, value] : llvm::enumerate(foo)) {
+    ++value;
+  }
+  EXPECT_THAT(foo, ElementsAre('b', 'c', 'd'));
 }
 
 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());
   }
 
-  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]);
+  EXPECT_THAT(Results,
+              ElementsAre(PairType(0u, 1), PairType(1u, 2), PairType(2u, 3)));
+
+  // Also test if this works with structured bindings.
+  Results.clear();
+
+  for (auto [index, value] : llvm::enumerate(std::vector<int>{1, 2, 3})) {
+    Results.emplace_back(index, value);
+  }
+
+  EXPECT_THAT(Results,
+              ElementsAre(PairType(0u, 1), PairType(1u, 2), PairType(2u, 3)));
 }
 
 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());
   }
 
-  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]);
+  EXPECT_THAT(Results, ElementsAre(PairType(0u, '2'), PairType(1u, '3'),
+                                   PairType(2u, '4')));
+
+  // Also test if this works with structured bindings.
+  Results.clear();
+
+  for (auto [index, value] :
+       llvm::enumerate(std::vector<char>{'1', '2', '3'})) {
+    ++value;
+    Results.emplace_back(index, value);
+  }
+
+  EXPECT_THAT(Results, ElementsAre(PairType(0u, '2'), PairType(1u, '3'),
+                                   PairType(2u, '4')));
 }
 
 template <bool B> struct CanMove {};
 template <> struct CanMove<false> {
   CanMove(CanMove &&) = delete;
 
   CanMove() = default;
   CanMove(const CanMove &) = default;