[ADT] Extend EnumeratedArray

[jsilvanus]

Summary

EnumeratedArray is essentially a wrapper around a fixed-size
array that uses enum values instead of integers as indices.

• Add iterator support (begin/end/rbegin/rend), which enables the use of iterator/range based algorithms on EnumeratedArrays.
• Add common container typedefs (value_type etc.), allowing drop-in replacements of other containers in cases relying on these.
• Add a constructor that takes an std::initializer_list<T>.
• Make the size() function const.
• Add empty().

Iterator support slightly lowers the protection from non-type-safe accesses,
because iterator arithmetic is not enum-based, and one can now use
*(begin() + IntIndex). However, it is and was also always possible to
just cast arbitrary indices to the enum type.

[jsilvanus]

Fix line order.

[jsilvanus]

Add unit tests.

[dblaikie]

Generally looks OK - few stylistic-y nits.

llvm/include/llvm/ADT/EnumeratedArray.h

46

might also want a deduction guide for this?

53

No need to use the inline keyword for member functions defined in the class body. (it doesn't change the linkagee, though it does hint the compiler towards inlining more - which, without perf investigation, is probably not what we want to do by default)

54

don't need the const here - we don't usually use top level const (& the auto will deduce non-const anyway)

llvm/unittests/ADT/EnumeratedArrayTest.cpp

53

generally prefer value initialization (with =) rather than direct initialization, then it can't get confused with other ctors - easier to read (as a reader I know it's calling an implicit ctor, which is more likely to be the "simple" thing)

67

Don't need the {} here, I think?
(& again, we usually don't bother with top-level const on local variables in LLVM code)

[jsilvanus]

Implement review feedback.

[jsilvanus]

Thanks for the review! I've implemented all your suggestions, except for the deduction guide, cf. the inline comment.

llvm/include/llvm/ADT/EnumeratedArray.h

46

You mean a deduction guide for EnumeratedArray? How would we identify the enum type?

53

Ok, done.
I was trying to stick to the existing style, but I'm fine with cleaning this up.

54

Ok, done.

llvm/unittests/ADT/EnumeratedArrayTest.cpp

53

Ok, done!

67

We need a const object or reference to test that size() and empty() can be called on consts. This was not the case before this patch.
With a const object, clang requires the explicit {} initializer, because EnumeratedArray has no user-provided default constructor.

To avoid all this, I removed the const and the {}, and instead use a const reference for the tests.

[dblaikie]

llvm/include/llvm/ADT/EnumeratedArray.h

46

Ah, yeah, fair point - can't deduce all the template parameters just from the list of values.

53

ah, right, sorry, had missed that - if you like you could fix the style up in a separate patch (don't need to send a change like that for review - can commit it directly/post-commit review) before this one to simplify the diff here.

llvm/unittests/ADT/EnumeratedArrayTest.cpp

67

Ah, thanks for explaining - I'm OK either way, just missed/didn't understand. Maybe this change is good though, with the ConstArray name making it clear/more self-documenting about why it exists.

90–102

I wonder if maybe you can use gmock ElementsAre https://github.com/google/googletest/blob/main/docs/reference/matchers.md to simplify these? (I guess the reverse ones are a bit harder unless you use llvm::reverse, which might be more complexity/broader surface area than is desirable - guess you could make_range of rbegin+rend manually, which would probably be OK?)

109–124

Since these are static_asserts, they don't benefit from being in a test function (the test function will do nothing) - maybe pull them out/leave them at the top level?

[jsilvanus]

Implement review feedback:

• use gmock's ElementsAre to simplify tests
• move static_asserts out of non-needed test function

[dblaikie]

Looks good, thanks!

llvm/include/llvm/ADT/EnumeratedArray.h

 /// values.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_ENUMERATEDARRAY_H
 #define LLVM_ADT_ENUMERATEDARRAY_H
 
 #include <cassert>
+#include <iterator>
 
 namespace llvm {
 
 template <typename ValueType, typename Enumeration,
           Enumeration LargestEnum = Enumeration::Last, typename IndexType = int,
           IndexType Size = 1 + static_cast<IndexType>(LargestEnum)>
 class EnumeratedArray {
 public:
+  using iterator = ValueType *;
+  using const_iterator = const ValueType *;
+
+  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+  using reverse_iterator = std::reverse_iterator<iterator>;
+
+  using value_type = ValueType;
+  using reference = ValueType &;
+  using const_reference = const ValueType &;
+  using pointer = ValueType *;
+  using const_pointer = const ValueType *;
+
   EnumeratedArray() = default;
   EnumeratedArray(ValueType V) {
     for (IndexType IX = 0; IX < Size; ++IX) {
       Underlying[IX] = V;
     }
   }
+  EnumeratedArray(std::initializer_list<ValueType> Init) {
+    assert(Init.size() == Size && "Incorrect initializer size");
+    for (IndexType IX = 0; IX < Size; ++IX) {
+      Underlying[IX] = *(Init.begin() + IX);
+    }
+  }
+
   const ValueType &operator[](Enumeration Index) const {
-    auto IX = static_cast<const IndexType>(Index);
+    auto IX = static_cast<IndexType>(Index);
     assert(IX >= 0 && IX < Size && "Index is out of bounds.");
     return Underlying[IX];
   }
   ValueType &operator[](Enumeration Index) {
     return const_cast<ValueType &>(
         static_cast<const EnumeratedArray<ValueType, Enumeration, LargestEnum,
                                           IndexType, Size> &>(*this)[Index]);
   }
-  IndexType size() { return Size; }
+  IndexType size() const { return Size; }
+  bool empty() const { return size() == 0; }
+
+  iterator begin() { return Underlying; }
+  const_iterator begin() const { return Underlying; }
+
+  iterator end() { return begin() + size(); }
+  const_iterator end() const { return begin() + size(); }
+
+  reverse_iterator rbegin() { return reverse_iterator(end()); }
+  const_reverse_iterator rbegin() const {
+    return const_reverse_iterator(end());
+  }
+  reverse_iterator rend() { return reverse_iterator(begin()); }
+  const_reverse_iterator rend() const {
+    return const_reverse_iterator(begin());
+  }
 
 private:
   ValueType Underlying[Size];
 };
 
 } // namespace llvm
 
 #endif // LLVM_ADT_ENUMERATEDARRAY_H

llvm/unittests/ADT/EnumeratedArrayTest.cpp

 //===- llvm/unittest/ADT/EnumeratedArrayTest.cpp ----------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // EnumeratedArray unit tests.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/EnumeratedArray.h"
+#include "llvm/ADT/iterator_range.h"
+#include "gmock/gmock.h"
 #include "gtest/gtest.h"
+#include <type_traits>
 
 namespace llvm {
 
 //===--------------------------------------------------------------------===//
 // Test initialization and use of operator[] for both read and write.
 //===--------------------------------------------------------------------===//
 
 TEST(EnumeratedArray, InitAndIndex) {
TEST(EnumeratedArray, InitAndIndex) {
 
   Array2[Colors::Red] = true;
   Array2[Colors::Blue] = false;
   Array2[Colors::Green] = true;
 
   EXPECT_TRUE(Array2[Colors::Red]);
   EXPECT_FALSE(Array2[Colors::Blue]);
   EXPECT_TRUE(Array2[Colors::Green]);
+
+  EnumeratedArray<float, Colors, Colors::Last, size_t> Array3 = {10.0, 11.0,
+                                                                 12.0};
+  EXPECT_EQ(Array3[Colors::Red], 10.0);
+  EXPECT_EQ(Array3[Colors::Blue], 11.0);
+  EXPECT_EQ(Array3[Colors::Green], 12.0);
+}
+
+//===--------------------------------------------------------------------===//
+// Test size and empty function
+//===--------------------------------------------------------------------===//
+
+TEST(EnumeratedArray, Size) {
+
+  enum class Colors { Red, Blue, Green, Last = Green };
+
+  EnumeratedArray<float, Colors, Colors::Last, size_t> Array;
+  const auto &ConstArray = Array;
+
+  EXPECT_EQ(ConstArray.size(), 3u);
+  EXPECT_EQ(ConstArray.empty(), false);
 }
 
+//===--------------------------------------------------------------------===//
+// Test iterators
+//===--------------------------------------------------------------------===//
+
+TEST(EnumeratedArray, Iterators) {
+
+  enum class Colors { Red, Blue, Green, Last = Green };
+
+  EnumeratedArray<float, Colors, Colors::Last, size_t> Array;
+  const auto &ConstArray = Array;
+
+  Array[Colors::Red] = 1.0;
+  Array[Colors::Blue] = 2.0;
+  Array[Colors::Green] = 3.0;
+
+  EXPECT_THAT(Array, testing::ElementsAre(1.0, 2.0, 3.0));
+  EXPECT_THAT(ConstArray, testing::ElementsAre(1.0, 2.0, 3.0));
+
+  EXPECT_THAT(make_range(Array.rbegin(), Array.rend()),
+              testing::ElementsAre(3.0, 2.0, 1.0));
+  EXPECT_THAT(make_range(ConstArray.rbegin(), ConstArray.rend()),
+              testing::ElementsAre(3.0, 2.0, 1.0));
+}
+
+//===--------------------------------------------------------------------===//
+// Test typedefs
+//===--------------------------------------------------------------------===//
+
+namespace {
+
+enum class Colors { Red, Blue, Green, Last = Green };
+
+using Array = EnumeratedArray<float, Colors, Colors::Last, size_t>;
+
+static_assert(std::is_same<Array::value_type, float>::value,
+              "Incorrect value_type type");
+static_assert(std::is_same<Array::reference, float &>::value,
+              "Incorrect reference type!");
+static_assert(std::is_same<Array::pointer, float *>::value,
+              "Incorrect pointer type!");
+static_assert(std::is_same<Array::const_reference, const float &>::value,
+              "Incorrect const_reference type!");
+static_assert(std::is_same<Array::const_pointer, const float *>::value,
+              "Incorrect const_pointer type!");
+} // namespace
+
 } // namespace llvm