Introduce `__sanitizer::ArrayRef<T>` type.

[delcypher]

Summary

This type is a light-weight container around a contiguous sequence
of elements of type T.

The type is inspired by LLVM ADT's ArrayRef but has more limited
functionality.

This patch includes tests for the new type but no uses in the runtime
itself. In future patches I will use this type as a foundation for
building a safe abstraction for operating on an environment array.

[dblaikie]

While I'm in favor of this type looking more like llvm's MutableArrayRef (ie: allowing mutability or immutability to be encoded in the type parameter (const T versus non-const T)) rather than needing the two types LLVM has (ArrayRef + MutableArrayRef). I wonder if having this type called "ArrayRef" when it is subtly different from llvm's ArrayRef might be confusing? Wonder if it needs another/better name - though the standard doesn't offer us a great alternative, it seems the standardized equivalent is std::span, which might be sufficiently different not to be a good name to use either? Not sure.

compiler-rt/lib/sanitizer_common/sanitizer_array_ref.h

87

Might just be better/easier to use "data_" directly, rather than const_casting+begin?

Or use "data()" instead, like llvm::ArrayRef does?

[delcypher]

In D78050#1979455, @dblaikie wrote:

While I'm in favor of this type looking more like llvm's MutableArrayRef (ie: allowing mutability or immutability to be encoded in the type parameter (const T versus non-const T)) rather than needing the two types LLVM has (ArrayRef + MutableArrayRef). I wonder if having this type called "ArrayRef" when it is subtly different from llvm's ArrayRef might be confusing?

Thank you for raising this. I probably should have said "loosely inspired" by ArrayRef because I wasn't aware of MutableArrayRef and I hadn't noticed that LLVM ADT's ArrayRef was immutable. Given that LLVM's ADT ArrayRef is immutable my choice of naming would certainly be confusing. For my use case I actually only need the underlying data to be mutable so I don't need an immutable version.

Wonder if it needs another/better name - though the standard doesn't offer us a great alternative, it seems the standardized equivalent is std::span, which might be sufficiently different not to be a good name to use either? Not sure.

My early draft name was actually BufferRef<T>. Does that seem any better?

compiler-rt/lib/sanitizer_common/sanitizer_array_ref.h

87

Good idea.

[dblaikie]

In D78050#1979667, @delcypher wrote:

In D78050#1979455, @dblaikie wrote:

While I'm in favor of this type looking more like llvm's MutableArrayRef (ie: allowing mutability or immutability to be encoded in the type parameter (const T versus non-const T)) rather than needing the two types LLVM has (ArrayRef + MutableArrayRef). I wonder if having this type called "ArrayRef" when it is subtly different from llvm's ArrayRef might be confusing?

Thank you for raising this. I probably should have said "loosely inspired" by ArrayRef because I wasn't aware of MutableArrayRef and I hadn't noticed that LLVM ADT's ArrayRef was immutable. Given that LLVM's ADT ArrayRef is immutable my choice of naming would certainly be confusing. For my use case I actually only need the underlying data to be mutable so I don't need an immutable version.

Wonder if it needs another/better name - though the standard doesn't offer us a great alternative, it seems the standardized equivalent is std::span, which might be sufficiently different not to be a good name to use either? Not sure.

My early draft name was actually BufferRef<T>. Does that seem any better?

Might be best just to resort to calling it MutableArrayRef to match LLVM's since they're so similar? Maybe one day we can revisit the design decision in LLVM and fix both, etc.

[delcypher]

• Rename ArrayRef<T> -> MutableArrayRef<T>.
• Remove duplicate const returning methods. They don't seem to be needed.
• Add elementTy.
• Add iterator type.

[dblaikie]

Don't suppose there's any sane way to reuse any part of the main llvm version? Might at least be worth a few comments encouraging future developers to try to keep this mostly aligned with the llvm one? (maybe document broadly the features/etc that are omitted from this version but present in the llvm one)

Is this more or less copy/paste, except for some features that aren't supportable/suitable for this usage?

compiler-rt/lib/sanitizer_common/sanitizer_mutable_array_ref.h

81 ↗

(On Diff #257455)

Going to use data() here?

[delcypher]

Remove unnecessary const_cast<>.

[delcypher]

In D78050#1981672, @dblaikie wrote:

Don't suppose there's any sane way to reuse any part of the main llvm version? Might at least be worth a few comments encouraging future developers to try to keep this mostly aligned with the llvm one? (maybe document broadly the features/etc that are omitted from this version but present in the llvm one)

We can't depend on libcxx in the compiler-rt runtimes. There's probably something crazy we could with macros that fudge the types to make it work but that doesn't sound sane.

Is this more or less copy/paste, except for some features that aren't supportable/suitable for this usage?

Not really. It just has the bare minimum functionality that I needed. I only looked at ArrayRef<> when I needed to do something I didn't know how to implement.

compiler-rt/lib/sanitizer_common/sanitizer_mutable_array_ref.h

81 ↗

(On Diff #257455)

Oh sorry. I missed this. I'll fix this.

[delcypher]

Abandoning this change in favour of:

• https://reviews.llvm.org/D78178
• https://reviews.llvm.org/D78179

compiler-rt/lib/sanitizer_common/CMakeLists.txt

set(SANITIZER_IMPL_HEADERS
   sanitizer_allocator_internal.h
   sanitizer_allocator_local_cache.h
   sanitizer_allocator_primary32.h
   sanitizer_allocator_primary64.h
   sanitizer_allocator_report.h
   sanitizer_allocator_secondary.h
   sanitizer_allocator_size_class_map.h
   sanitizer_allocator_stats.h
+  sanitizer_array_ref.h
   sanitizer_asm.h
   sanitizer_atomic.h
   sanitizer_atomic_clang.h
   sanitizer_atomic_clang_mips.h
   sanitizer_atomic_clang_other.h
   sanitizer_atomic_clang_x86.h
   sanitizer_atomic_msvc.h
   sanitizer_bitvector.h

compiler-rt/lib/sanitizer_common/sanitizer_array_ref.h

+//===-- sanitizer_array_ref.h -----------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Lightweight reference to a contiguous array of elements
+// of type `T`. It does not own any storage. Consequently
+// care must be taken to ensure the life-time of this object
+// does not outlive the storage it references.
+//
+//===----------------------------------------------------------------------===//
+#ifndef SANITIZER_ARRAY_REF_H
+#define SANITIZER_ARRAY_REF_H
+#include "sanitizer_common.h"
+#include "sanitizer_internal_defs.h"
+#include "sanitizer_libc.h"
+
+namespace __sanitizer {
+
+template <class T>
+class ArrayRef {
+ public:
+  explicit ArrayRef(T *data, uptr size) : data_(data), size_(size) {}
+  template <uptr N>
+  explicit ArrayRef(T (&ptr)[N]) : data_(ptr), size_(N) {}
+
+  // Accessors
+  T *data() const { return data_; }
+  // TODO(dliew): Consider returning smart iterator that tracks if derefence is
+  // safe.
+  const T *begin() const { return data_; }
+  T *begin() { return data_; }
+  const T *end() const {
+    if (size_ == 0)
+      return begin();
+    return &(data_[size_ - 1]);
+  }
+  T *end() {
+    if (size_ == 0)
+      return begin();
+    return &(data_[size_ - 1]);
+  }
+  const T &operator[](uptr idx) const {
+    CHECK_LT(idx, size_);
+    return data_[idx];
+  }
+  T &operator[](uptr idx) {
+    CHECK_LT(idx, size_);
+    return data_[idx];
+  }
+
+  // Properties
+  bool containsPtr(T *ptr) const {
+    if (ptr >= begin() && ptr <= end())
+      return true;
+    return false;
+  }
+  bool isValidIndex(uptr idx) const { return idx < size_; }
+  bool overlaps(const ArrayRef<T> &other) const {
+    if (begin() <= other.begin() && other.begin() <= end())
+      return true;
+    if (other.begin() <= begin() && other.end() >= begin())
+      return true;
+    return false;
+  }
+  uptr size() const { return size_; }
+
+  // Copy operations
+  void copyFrom(const ArrayRef<T> &src) {
+    CHECK_GE(size_, src.size_);
+    CHECK(!overlaps(src));
+    internal_memcpy(data_, src.data_, sizeof(T) * src.size_);
+  }
+  uptr truncatedCopyFrom(const ArrayRef<T> &src) {
+    CHECK(!overlaps(src));
+    uptr elts_to_copy = Min(size_, src.size_);
+    internal_memcpy(data_, src.data_, sizeof(T) * elts_to_copy);
+    return elts_to_copy;
+  }
+
+  // Return an `ArrayRef` that drops the first `n` elements
+  ArrayRef<T> slice(uptr n) const {
+    CHECK_LE(n, size());
+    T *slice_begin = const_cast<T *>(begin()) + n;
+    uptr slice_size = size() - n;
+    return ArrayRef<T>(slice_begin, slice_size);
+  }
+
+ private:
+  T *data_;
+  uptr size_;  // number of elements of type T in buffer.
+};
+
+}  // namespace __sanitizer
+
+#endif

compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt

 include(CompilerRTCompile)
 
 clang_compiler_add_cxx_check()
 
 # FIXME: use SANITIZER_COMMON_SUPPORTED_ARCH here
 filter_available_targets(SANITIZER_UNITTEST_SUPPORTED_ARCH x86_64 i386 mips64 mips64el)
 if(APPLE)
   darwin_filter_host_archs(SANITIZER_UNITTEST_SUPPORTED_ARCH SANITIZER_UNITTEST_SUPPORTED_ARCH)
 endif()
 
 set(SANITIZER_UNITTESTS
   sanitizer_allocator_test.cpp
+  sanitizer_array_ref_test.cpp
   sanitizer_atomic_test.cpp
   sanitizer_bitvector_test.cpp
   sanitizer_bvgraph_test.cpp
   sanitizer_common_test.cpp
   sanitizer_deadlock_detector_test.cpp
   sanitizer_flags_test.cpp
   sanitizer_format_interceptor_test.cpp
   sanitizer_ioctl_test.cpp

compiler-rt/lib/sanitizer_common/tests/sanitizer_array_ref_test.cpp

+//===-- sanitizer_array_ref_test.cpp --------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of Sanitizer runtime.
+// Tests for sanitizer_bitvector.h.
+//
+//===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_array_ref.h"
+
+#include "gtest/gtest.h"
+#include "sanitizer_test_utils.h"
+
+using namespace __sanitizer;
+
+static const char kDeathRegex[] = ".*CHECK failed:.*";
+
+int data[] = {0, 1, 2, 3};
+ArrayRef<int> ref(data, ARRAY_SIZE(data));
+
+TEST(ArrayRef, CArrayConstructor) {
+  ArrayRef<int> other_ref(data);
+  EXPECT_EQ(other_ref.size(), ARRAY_SIZE(data));
+  for (unsigned index = 0; index < ARRAY_SIZE(data); ++index) {
+    EXPECT_EQ(ref[index], data[index]);
+  }
+}
+
+TEST(ArrayRef, IndexOperatorSafeRead) {
+  for (unsigned index = 0; index < ARRAY_SIZE(data); ++index) {
+    EXPECT_EQ(ref[index], data[index]);
+  }
+}
+
+TEST(ArrayRef, IndexOperatorSafeWrite) {
+  for (unsigned index = 0; index < ARRAY_SIZE(data); ++index) {
+    ref[index] = static_cast<int>(index) * 2;
+  }
+  for (unsigned index = 0; index < ARRAY_SIZE(data); ++index) {
+    EXPECT_EQ(data[index], static_cast<int>(index) * 2);
+  }
+}
+
+TEST(ArrayRef, IndexOperatorBadRead) { EXPECT_DEATH(ref[4], kDeathRegex); }
+
+TEST(ArrayRef, Size) { EXPECT_EQ(ref.size(), static_cast<uptr>(4)); }
+
+TEST(ArrayRef, Data) {
+  ArrayRef<int> ref(data, ARRAY_SIZE(data));
+  EXPECT_EQ(ref.data(), &(data[0]));
+}
+
+TEST(ArrayRef, Begin) {
+  ArrayRef<int> ref(data, ARRAY_SIZE(data));
+  EXPECT_EQ(ref.begin(), &(data[0]));
+}
+
+TEST(ArrayRef, End) {
+  ArrayRef<int> ref(data, ARRAY_SIZE(data));
+  EXPECT_EQ(ref.end(), &(data[3]));
+}
+
+TEST(ArrayRef, LoopCXX98) {
+  // Loop like it's 1998!
+  unsigned index = 0;
+  for (auto it = ref.begin(), end = ref.end(); it != end; ++it) {
+    EXPECT_EQ(it, &(data[index]));
+    ++index;
+  }
+}
+TEST(ArrayRef, LoopCXX11) {
+  // Loop like it's 2011!
+  unsigned index = 0;
+  for (auto& elt : ref) {
+    EXPECT_EQ(elt, data[index]);
+    ++index;
+  }
+}
+
+TEST(ArrayRef, IsValidIndex) {
+  unsigned index = 0;
+  for (; index < ARRAY_SIZE(data); ++index) {
+    EXPECT_TRUE(ref.isValidIndex(index));
+  }
+  EXPECT_FALSE(ref.isValidIndex(index));
+}
+
+TEST(ArrayRef, OverlapDisjoint) {
+  ArrayRef<int> left_ref(data, 2);
+  ArrayRef<int> right_ref(&(data[2]), 2);
+  EXPECT_FALSE(left_ref.overlaps(right_ref));
+  EXPECT_FALSE(right_ref.overlaps(left_ref));
+}
+
+TEST(ArrayRef, OverlapOneEltOverlap) {
+  ArrayRef<int> left_ref(data, 3);
+  ArrayRef<int> right_ref(&(data[2]), 2);
+  EXPECT_TRUE(left_ref.overlaps(right_ref));
+  EXPECT_TRUE(right_ref.overlaps(left_ref));
+}
+
+TEST(ArrayRef, copyFrom) {
+  int other_data[5] = {0};
+  static_assert(sizeof(other_data) > sizeof(data),
+                "other_data should be larger than data");
+  ArrayRef<int> other_ref(other_data, ARRAY_SIZE(other_data));
+  for (unsigned index = 0; index < ARRAY_SIZE(other_data); ++index) {
+    EXPECT_EQ(other_data[index], 0);
+  }
+  other_ref.copyFrom(ref);
+  for (unsigned index = 0; index < ARRAY_SIZE(other_data); ++index) {
+    if (index < ARRAY_SIZE(data)) {
+      EXPECT_EQ(other_ref[index], data[index]);
+    } else {
+      EXPECT_EQ(other_ref[index], 0);
+    }
+  }
+}
+
+TEST(ArrayRef, copyFromUnsafeOverlap) {
+  ArrayRef<int> other_ref(data, ARRAY_SIZE(data));
+  EXPECT_DEATH(other_ref.copyFrom(ref), kDeathRegex);
+}
+
+TEST(ArrayRef, copyFromUnsafeOverlapOneElt) {
+  ArrayRef<int> left_ref(data, 3);
+  ArrayRef<int> right_ref(&(data[2]), 2);
+  EXPECT_DEATH(left_ref.copyFrom(right_ref), kDeathRegex);
+}
+
+TEST(ArrayRef, copyFromInsufficientSpace) {
+  int other_data[2] = {0};
+  static_assert(sizeof(other_data) < sizeof(data),
+                "other_data should be smaller");
+  ArrayRef<int> other_ref(other_data, ARRAY_SIZE(other_data));
+  EXPECT_DEATH(other_ref.copyFrom(ref), kDeathRegex);
+}
+
+TEST(ArrayRef, truncatedCopyFrom) {
+  int other_data[ARRAY_SIZE(data) - 2] = {0};
+  ArrayRef<int> other_ref(other_data, ARRAY_SIZE(other_data));
+  for (unsigned index = 0; index < ARRAY_SIZE(other_data); ++index) {
+    EXPECT_EQ(other_data[index], 0);
+  }
+  uptr elts = other_ref.truncatedCopyFrom(ref);
+  EXPECT_EQ(elts, ARRAY_SIZE(other_data));
+  for (unsigned index = 0; index < ARRAY_SIZE(other_data); ++index) {
+    EXPECT_EQ(other_ref[index], ref[index]);
+  }
+}
+
+TEST(ArrayRef, truncatedCopyFromNoTrunc) {
+  int other_data[ARRAY_SIZE(data)] = {0};
+  ArrayRef<int> other_ref(other_data, ARRAY_SIZE(other_data));
+  for (unsigned index = 0; index < ARRAY_SIZE(other_data); ++index) {
+    EXPECT_EQ(other_data[index], 0);
+  }
+  uptr elts = other_ref.truncatedCopyFrom(ref);
+  EXPECT_EQ(elts, ARRAY_SIZE(data));
+  for (unsigned index = 0; index < ARRAY_SIZE(other_data); ++index) {
+    EXPECT_EQ(other_ref[index], ref[index]);
+  }
+}
+
+TEST(ArrayRef, truncatedCopyFromUnsafeOverlap) {
+  ArrayRef<int> other_ref(data, ARRAY_SIZE(data));
+  EXPECT_DEATH(other_ref.truncatedCopyFrom(ref), kDeathRegex);
+}
+
+TEST(ArrayRef, containsPtr) {
+  for (unsigned index = 0; index < ARRAY_SIZE(data); ++index) {
+    EXPECT_TRUE(ref.containsPtr(&(data[index])));
+  }
+  EXPECT_FALSE(ref.containsPtr(&(data[ARRAY_SIZE(data)])));
+  EXPECT_FALSE(ref.containsPtr(nullptr));
+}
+
+TEST(ArrayRef, zeroSize) {
+  ArrayRef<int*> null_ref(nullptr, 0);
+  EXPECT_EQ(null_ref.size(), (uptr)0);
+  EXPECT_EQ(null_ref.begin(), null_ref.end());
+  EXPECT_EQ(null_ref.begin(), nullptr);
+}
+
+TEST(ArrayRef, zeroSizeBadAccess) {
+  ArrayRef<int*> null_ref(nullptr, 0);
+  EXPECT_DEATH(null_ref[0], kDeathRegex);
+}
+
+TEST(ArrayRef, slice) {
+  auto slice = ref.slice(2);
+  EXPECT_EQ(slice.size(), ref.size() - 2);
+  for (unsigned index = 0; index < slice.size(); ++index) {
+    EXPECT_EQ(slice[index], ref[index + 2]);
+  }
+}
+
+TEST(ArrayRef, sliceToZero) {
+  auto slice = ref.slice(ref.size());
+  EXPECT_EQ(slice.size(), static_cast<uptr>(0));
+}
+
+TEST(ArrayRef, sliceTooLarge) {
+  EXPECT_DEATH(ref.slice(ref.size() + 1), kDeathRegex);
+}
+
+TEST(ArrayRef, assign) {
+  int other_data[2] = {0};
+  ArrayRef<int> other_ref(other_data);
+  EXPECT_EQ(other_ref.size(), ARRAY_SIZE(other_data));
+  other_ref = ref;
+  EXPECT_EQ(other_ref.size(), ref.size());
+  EXPECT_EQ(other_ref.data(), ref.data());
+}