[libc] Enhance ArrayRef + unittests

[gchatelet]

Summary

This patch mostly adds unittests for ArrayRef and MutableArrayRef, additionnaly:

• We mimic the behavior of std::vector and disallow CV qualified type (ArrayRef<const X> is not allowed). This is to make sure that the type traits are always valid (e.g. value_type, pointer, ...).
• In the previous implementation ArrayRef would define value_type as const T but this is not correct, it should be T for both MutableArrayRef and ArrayRef.
• We add the equals method to ease testing,
• We define the constructor taking an Array outside of the base implementation to ensure we match const Array<T>& and not Array<const T>& in the case of ArrayRef.

[sivachandra]

Overall, a very nice change. Thanks for doing it. The clang-tidy warnings in the equals method are legitimate and should be fixed before submitting.

libc/utils/CPP/ArrayRef.h

90

Calling it equals is a bit misleading when we are comparing references. Unless this name is inspired from other places in llvm-project, may be name it equalData or something like that?

113

Since this is a struct, may be make the using statements private?

125

Same here?

[gchatelet]

libc/utils/CPP/ArrayRef.h

90

I agree it's not ideal but I tried to stick to the llvm's ArrayRef naming.

[gchatelet]

• Made internal using and static_assert private.

libc/test/utils/CPP/CMakeLists.txt

add_libc_unittest(
   stringview_test
   SUITE
     libc_cpp_utils_unittests
   SRCS
     stringview_test.cpp
   DEPENDS
     libc.utils.CPP.standalone_cpp
 )
+
+add_libc_unittest(
+  arrayref_test
+  SUITE
+    libc_cpp_utils_unittests
+  SRCS
+    arrayref_test.cpp
+  DEPENDS
+    libc.utils.CPP.standalone_cpp
+)

libc/test/utils/CPP/arrayref_test.cpp

+//===-- Unittests for ArrayRef --------------------------------------------===//
+//
+// 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 "utils/CPP/ArrayRef.h"
+#include "utils/UnitTest/Test.h"
+
+namespace __llvm_libc {
+namespace cpp {
+
+// The following tests run on both 'ArrayRef' and 'MutableArrayRef'.
+using Types = testing::TypeList<ArrayRef<int>, MutableArrayRef<int>>;
+
+TYPED_TEST(LlvmLibcArrayRefTest, ConstructFromElement, Types) {
+  using value_type = typename ParamType::value_type;
+  using const_pointer = typename ParamType::const_pointer;
+  value_type element = 5;
+  ParamType arrayref(element);
+  EXPECT_FALSE(arrayref.empty());
+  EXPECT_EQ(arrayref.size(), 1UL);
+  EXPECT_EQ(arrayref[0], 5);
+  EXPECT_EQ((const_pointer)arrayref.data(), (const_pointer)&element);
+}
+
+TYPED_TEST(LlvmLibcArrayRefTest, ConstructFromPointerAndSize, Types) {
+  using value_type = typename ParamType::value_type;
+  using const_pointer = typename ParamType::const_pointer;
+  value_type values[] = {1, 2};
+  ParamType arrayref(values, 2);
+  EXPECT_FALSE(arrayref.empty());
+  EXPECT_EQ(arrayref.size(), 2UL);
+  EXPECT_EQ(arrayref[0], 1);
+  EXPECT_EQ(arrayref[1], 2);
+  EXPECT_EQ((const_pointer)arrayref.data(), (const_pointer)values);
+}
+
+TYPED_TEST(LlvmLibcArrayRefTest, ConstructFromIterator, Types) {
+  using value_type = typename ParamType::value_type;
+  using const_pointer = typename ParamType::const_pointer;
+  value_type values[] = {1, 2};
+  ParamType arrayref(&values[0], &values[2]);
+  EXPECT_FALSE(arrayref.empty());
+  EXPECT_EQ(arrayref.size(), 2UL);
+  EXPECT_EQ(arrayref[0], 1);
+  EXPECT_EQ(arrayref[1], 2);
+  EXPECT_EQ((const_pointer)arrayref.data(), (const_pointer)&values[0]);
+}
+
+TYPED_TEST(LlvmLibcArrayRefTest, ConstructFromCArray, Types) {
+  using value_type = typename ParamType::value_type;
+  using const_pointer = typename ParamType::const_pointer;
+  value_type values[] = {1, 2};
+  ParamType arrayref(values);
+  EXPECT_FALSE(arrayref.empty());
+  EXPECT_EQ(arrayref.size(), 2UL);
+  EXPECT_EQ(arrayref[0], 1);
+  EXPECT_EQ(arrayref[1], 2);
+  EXPECT_EQ((const_pointer)arrayref.data(), (const_pointer)values);
+}
+
+TYPED_TEST(LlvmLibcArrayRefTest, ConstructFromLibcArray, Types) {
+  using value_type = typename ParamType::value_type;
+  using const_pointer = typename ParamType::const_pointer;
+  Array<value_type, 2> values = {1, 2};
+  ParamType arrayref(values);
+  EXPECT_FALSE(arrayref.empty());
+  EXPECT_EQ(arrayref.size(), 2UL);
+  EXPECT_EQ(arrayref[0], 1);
+  EXPECT_EQ(arrayref[1], 2);
+  EXPECT_EQ((const_pointer)arrayref.data(), (const_pointer)values.data());
+}
+
+TYPED_TEST(LlvmLibcArrayRefTest, Equals, Types) {
+  using value_type = typename ParamType::value_type;
+  value_type values[] = {1, 2, 3};
+  ParamType initial(values);
+  EXPECT_TRUE(initial.equals(initial));
+  ParamType shallow_copy(values);
+  EXPECT_TRUE(initial.equals(shallow_copy));
+  value_type same_values[] = {1, 2, 3};
+  EXPECT_TRUE(initial.equals(same_values));
+  value_type different_values[] = {1, 2, 4};
+  EXPECT_FALSE(initial.equals(different_values));
+}
+
+TYPED_TEST(LlvmLibcArrayRefTest, SliceUnary, Types) {
+  using value_type = typename ParamType::value_type;
+  value_type values[] = {1, 2, 3};
+  ParamType arrayref(values);
+  {
+    value_type values[] = {1, 2, 3};
+    EXPECT_TRUE(arrayref.slice(0).equals(values));
+  }
+  {
+    value_type values[] = {2, 3};
+    EXPECT_TRUE(arrayref.slice(1).equals(values));
+  }
+  {
+    value_type values[] = {3};
+    EXPECT_TRUE(arrayref.slice(2).equals(values));
+  }
+  { EXPECT_TRUE(arrayref.slice(3).empty()); }
+}
+
+TYPED_TEST(LlvmLibcArrayRefTest, SliceBinary, Types) {
+  using value_type = typename ParamType::value_type;
+  value_type values[] = {1, 2, 3};
+  ParamType arrayref(values);
+  {
+    EXPECT_TRUE(arrayref.slice(0, 0).empty());
+    EXPECT_TRUE(arrayref.slice(1, 0).empty());
+    EXPECT_TRUE(arrayref.slice(2, 0).empty());
+    EXPECT_TRUE(arrayref.slice(3, 0).empty());
+  }
+  {
+    value_type values[] = {1};
+    EXPECT_TRUE(arrayref.slice(0, 1).equals(values));
+  }
+  {
+    value_type values[] = {2};
+    EXPECT_TRUE(arrayref.slice(1, 1).equals(values));
+  }
+  {
+    value_type values[] = {3};
+    EXPECT_TRUE(arrayref.slice(2, 1).equals(values));
+  }
+  {
+    value_type values[] = {1, 2};
+    EXPECT_TRUE(arrayref.slice(0, 2).equals(values));
+  }
+  {
+    value_type values[] = {2, 3};
+    EXPECT_TRUE(arrayref.slice(1, 2).equals(values));
+  }
+  {
+    value_type values[] = {1, 2, 3};
+    EXPECT_TRUE(arrayref.slice(0, 3).equals(values));
+  }
+}
+
+TYPED_TEST(LlvmLibcArrayRefTest, DropFront, Types) {
+  using value_type = typename ParamType::value_type;
+  value_type values[] = {1, 2, 3};
+  ParamType arrayref(values);
+  {
+    value_type values[] = {1, 2, 3};
+    EXPECT_TRUE(arrayref.drop_front(0).equals(values));
+  }
+  {
+    value_type values[] = {2, 3};
+    EXPECT_TRUE(arrayref.drop_front(1).equals(values));
+  }
+  {
+    value_type values[] = {3};
+    EXPECT_TRUE(arrayref.drop_front(2).equals(values));
+  }
+  { EXPECT_TRUE(arrayref.drop_front(3).empty()); }
+}
+
+TYPED_TEST(LlvmLibcArrayRefTest, DropBack, Types) {
+  using value_type = typename ParamType::value_type;
+  value_type values[] = {1, 2, 3};
+  ParamType arrayref(values);
+  {
+    value_type values[] = {1, 2, 3};
+    EXPECT_TRUE(arrayref.drop_back(0).equals(values));
+  }
+  {
+    value_type values[] = {1, 2};
+    EXPECT_TRUE(arrayref.drop_back(1).equals(values));
+  }
+  {
+    value_type values[] = {1};
+    EXPECT_TRUE(arrayref.drop_back(2).equals(values));
+  }
+  { EXPECT_TRUE(arrayref.drop_back(3).empty()); }
+}
+
+TYPED_TEST(LlvmLibcArrayRefTest, TakeFront, Types) {
+  using value_type = typename ParamType::value_type;
+  value_type values[] = {1, 2, 3};
+  ParamType arrayref(values);
+  { EXPECT_TRUE(arrayref.take_front(0).empty()); }
+  {
+    value_type values[] = {1};
+    EXPECT_TRUE(arrayref.take_front(1).equals(values));
+  }
+  {
+    value_type values[] = {1, 2};
+    EXPECT_TRUE(arrayref.take_front(2).equals(values));
+  }
+  {
+    value_type values[] = {1, 2, 3};
+    EXPECT_TRUE(arrayref.take_front(3).equals(values));
+  }
+}
+
+TYPED_TEST(LlvmLibcArrayRefTest, TakeBack, Types) {
+  using value_type = typename ParamType::value_type;
+  value_type values[] = {1, 2, 3};
+  ParamType arrayref(values);
+  { EXPECT_TRUE(arrayref.take_back(0).empty()); }
+  {
+    value_type values[] = {3};
+    EXPECT_TRUE(arrayref.take_back(1).equals(values));
+  }
+  {
+    value_type values[] = {2, 3};
+    EXPECT_TRUE(arrayref.take_back(2).equals(values));
+  }
+  {
+    value_type values[] = {1, 2, 3};
+    EXPECT_TRUE(arrayref.take_back(3).equals(values));
+  }
+}
+
+} // namespace cpp
+} // namespace __llvm_libc

libc/utils/CPP/ArrayRef.h

 //===-- Self contained ArrayRef type ----------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIBC_UTILS_CPP_ARRAYREF_H
 #define LLVM_LIBC_UTILS_CPP_ARRAYREF_H
 
 #include "Array.h"
+#include "TypeTraits.h" //RemoveCVType
 
 #include <stddef.h> // For size_t.
 
 namespace __llvm_libc {
 namespace cpp {
 
 // The implementations of ArrayRef and MutableArrayRef in this file are based
 // on the implementations of the types with the same names in
 // llvm/ADT/ArrayRef.h. The implementations in this file are of a limited
 // functionality, but can be extended in an as needed basis.
 namespace internal {
-template <typename T> class ArrayRefBase {
+template <typename QualifiedT> class ArrayRefBase {
 public:
-  using iterator = T *;
-  using pointer = T *;
-  using reference = T &;
+  using value_type = RemoveCVType<QualifiedT>;
+  using pointer = value_type *;
+  using const_pointer = const value_type *;
+  using reference = value_type &;
+  using const_reference = const value_type &;
+  using iterator = const_pointer;
+  using const_iterator = const_pointer;
+  using size_type = size_t;
+  using difference_type = ptrdiff_t;
 
   ArrayRefBase() = default;
 
-  // From Array.
-  template <size_t N>
-  ArrayRefBase(Array<T, N> &Arr) : Data(Arr.Data), Length(N) {}
-
   // Construct an ArrayRefBase from a single element.
-  explicit ArrayRefBase(T &OneElt) : Data(&OneElt), Length(1) {}
+  explicit ArrayRefBase(QualifiedT &OneElt) : Data(&OneElt), Length(1) {}
 
   // Construct an ArrayRefBase from a pointer and length.
-  ArrayRefBase(pointer Data, size_t Length) : Data(Data), Length(Length) {}
+  ArrayRefBase(QualifiedT *Data, size_t Length) : Data(Data), Length(Length) {}
 
   // Construct an ArrayRefBase from a range.
-  ArrayRefBase(iterator Begin, iterator End)
+  ArrayRefBase(QualifiedT *Begin, QualifiedT *End)
       : Data(Begin), Length(End - Begin) {}
 
   // Construct an ArrayRefBase from a C array.
   template <size_t N>
-  constexpr ArrayRefBase(T (&Arr)[N]) : Data(Arr), Length(N) {}
+  constexpr ArrayRefBase(QualifiedT (&Arr)[N]) : Data(Arr), Length(N) {}
 
-  iterator begin() const { return Data; }
-  iterator end() const { return Data + Length; }
-
-  bool empty() const { return Length == 0; }
+  QualifiedT *data() const { return Data; }
+  size_t size() const { return Length; }
 
-  pointer data() const { return Data; }
+  auto begin() const { return data(); }
+  auto end() const { return data() + size(); }
 
-  size_t size() const { return Length; }
+  bool empty() const { return size() == 0; }
 
-  reference operator[](size_t Index) const { return Data[Index]; }
+  auto operator[](size_t Index) const { return data()[Index]; }
 
   // slice(n, m) - Chop off the first N elements of the array, and keep M
   // elements in the array.
-  ArrayRefBase<T> slice(size_t N, size_t M) const {
-    return ArrayRefBase<T>(data() + N, M);
-  }
+  auto slice(size_t N, size_t M) const { return ArrayRefBase(data() + N, M); }
   // slice(n) - Chop off the first N elements of the array.
-  ArrayRefBase<T> slice(size_t N) const { return slice(N, size() - N); }
+  auto slice(size_t N) const { return slice(N, size() - N); }
 
   // Drop the first \p N elements of the array.
-  ArrayRefBase<T> drop_front(size_t N = 1) const {
-    return slice(N, size() - N);
-  }
+  auto drop_front(size_t N = 1) const { return slice(N, size() - N); }
 
   // Drop the last \p N elements of the array.
-  ArrayRefBase<T> drop_back(size_t N = 1) const { return slice(0, size() - N); }
+  auto drop_back(size_t N = 1) const { return slice(0, size() - N); }
 
   // Return a copy of *this with only the first \p N elements.
-  ArrayRefBase<T> take_front(size_t N = 1) const {
+  auto take_front(size_t N = 1) const {
     if (N >= size())
       return *this;
     return drop_back(size() - N);
   }
 
   // Return a copy of *this with only the last \p N elements.
-  ArrayRefBase<T> take_back(size_t N = 1) const {
+  auto take_back(size_t N = 1) const {
     if (N >= size())
       return *this;
     return drop_front(size() - N);
   }
 
+  // equals - Check for element-wise equality.
+  bool equals(ArrayRefBase<QualifiedT> RHS) const {
+    if (Length != RHS.Length)
+      return false;
+    auto First1 = begin();
+    auto Last1 = end();
+    auto First2 = RHS.begin();
+    for (; First1 != Last1; ++First1, ++First2) {
+      if (!(*First1 == *First2)) {
+        return false;
+      }
+    }
+    return true;
+  }
+
 private:
-  pointer Data = nullptr;
+  QualifiedT *Data = nullptr;
   size_t Length = 0;
 };
 } // namespace internal
 
-template <typename T> using ArrayRef = internal::ArrayRefBase<const T>;
-template <typename T> using MutableArrayRef = internal::ArrayRefBase<T>;
+template <typename T> struct ArrayRef : public internal::ArrayRefBase<const T> {
+private:
+  static_assert(IsSameV<T, RemoveCVType<T>>,
+                "ArrayRef must have a non-const, non-volatile value_type");
+  using Impl = internal::ArrayRefBase<const T>;
+  using Impl::Impl;
+
+public:
+  // From Array.
+  template <size_t N> ArrayRef(const Array<T, N> &Arr) : Impl(Arr.Data, N) {}
+};
+
+template <typename T>
+struct MutableArrayRef : public internal::ArrayRefBase<T> {
+private:
+  static_assert(
+      IsSameV<T, RemoveCVType<T>>,
+      "MutableArrayRef must have a non-const, non-volatile value_type");
+  using Impl = internal::ArrayRefBase<T>;
+  using Impl::Impl;
+
+public:
+  // From Array.
+  template <size_t N> MutableArrayRef(Array<T, N> &Arr) : Impl(Arr.Data, N) {}
+};
 
 } // namespace cpp
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_UTILS_CPP_ARRAYREF_H