ArrayView: Support compile-time constant sizes

webrtc/base/array_view.h

 /*
  *  Copyright 2015 The WebRTC Project Authors. All rights reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
  *  tree. An additional intellectual property rights grant can be found
  *  in the file PATENTS.  All contributing project authors may
  *  be found in the AUTHORS file in the root of the source tree.
  */
 
@@ skipping 13 matching lines @@
 //       if (arr[i] == 17)
 //         return true;
 //     }
 //     return false;
 //   }
 //
 // This is flexible, since it doesn't matter how the array is stored (C array,
 // std::vector, rtc::Buffer, ...), but it's error-prone because the caller has
 // to correctly specify the array length:
 //
-//   Contains17(arr, arraysize(arr));  // C array
-//   Contains17(&arr[0], arr.size());  // std::vector
-//   Contains17(arr, size);            // pointer + size
+//   Contains17(arr, arraysize(arr));     // C array
+//   Contains17(arr.data(), arr.size());  // std::vector
+//   Contains17(arr, size);               // pointer + size
 //   ...
 //
 // It's also kind of messy to have two separate arguments for what is
 // conceptually a single thing.
 //
 // Enter rtc::ArrayView<T>. It contains a T pointer (to an array it doesn't
 // own) and a count, and supports the basic things you'd expect, such as
 // indexing and iteration. It allows us to write our function like this:
 //
 //   bool Contains17(rtc::ArrayView<const int> arr) {
 //     for (auto e : arr) {
 //       if (e == 17)
 //         return true;
 //     }
 //     return false;
 //   }
 //
 // And even better, because a bunch of things will implicitly convert to
 // ArrayView, we can call it like this:
 //
 //   Contains17(arr);                             // C array
 //   Contains17(arr);                             // std::vector
 //   Contains17(rtc::ArrayView<int>(arr, size));  // pointer + size
 //   Contains17(nullptr);                         // nullptr -> empty ArrayView
 //   ...
 //
+// ArrayView<T> stores both a pointer and a size, but you may also use
+// ArrayView<T, N>, which has a size that's fixed at compile time (which means
+// it only has to store the pointer).
+//
 // One important point is that ArrayView<T> and ArrayView<const T> are
 // different types, which allow and don't allow mutation of the array elements,
 // respectively. The implicit conversions work just like you'd hope, so that
 // e.g. vector<int> will convert to either ArrayView<int> or ArrayView<const
 // int>, but const vector<int> will convert only to ArrayView<const int>.
 // (ArrayView itself can be the source type in such conversions, so
 // ArrayView<int> will convert to ArrayView<const int>.)
 //
-// Note: ArrayView is tiny (just a pointer and a count) and trivially copyable,
-// so it's probably cheaper to pass it by value than by const reference.
+// Note: ArrayView is tiny (just a pointer and a count if variable-sized, just
+// a pointer if fix-sized) and trivially copyable, so it's probably cheaper to
+// pass it by value than by const reference.
+
+namespace impl {
+
+// Magic constant for indicating that the size of an ArrayView is variable
+// instead of fixed.
+enum : std::ptrdiff_t { kArrayViewVarSize = -4711 };
+
+// Base class for ArrayViews of fixed nonzero size.
+template <typename T, std::ptrdiff_t Size>
+class ArrayViewBase {
+  static_assert(Size > 0, "ArrayView size must be variable or non-negative");
+
+ public:
+  ArrayViewBase(T* data, size_t size) : data_(data) {}
+
+  static constexpr size_t size() { return Size; }
+  static constexpr bool empty() { return false; }
+  T* data() const { return data_; }
+
+ protected:
+  static constexpr bool fixed_size() { return true; }
+
+ private:
+  T* data_;
+};
+
+// Specialized base class for ArrayViews of fixed zero size.
 template <typename T>
-class ArrayView final {
+class ArrayViewBase<T, 0> {
+ public:
+  explicit ArrayViewBase(T* data, size_t size) {}
+
+  static constexpr size_t size() { return 0; }
+  static constexpr bool empty() { return true; }
+  T* data() const { return nullptr; }
+
+ protected:
+  static constexpr bool fixed_size() { return true; }
+};
+
+// Specialized base class for ArrayViews of variable size.
+template <typename T>
+class ArrayViewBase<T, impl::kArrayViewVarSize> {
+ public:
+  ArrayViewBase(T* data, size_t size)
+      : data_(size == 0 ? nullptr : data), size_(size) {}
+
+  size_t size() const { return size_; }
+  bool empty() const { return size_ == 0; }
+  T* data() const { return data_; }
+
+ protected:
+  static constexpr bool fixed_size() { return false; }
+
+ private:
+  T* data_;
+  size_t size_;
+};
+
+}  // namespace impl
+
+template <typename T, std::ptrdiff_t Size = impl::kArrayViewVarSize>
+class ArrayView final : public impl::ArrayViewBase<T, Size> {
  public:
   using value_type = T;
   using const_iterator = const T*;
 
-  // Construct an empty ArrayView.
-  ArrayView() : ArrayView(static_cast<T*>(nullptr), 0) {}
-  ArrayView(std::nullptr_t) : ArrayView() {}
-
-  // Construct an ArrayView for a (pointer,size) pair.
+  // Construct an ArrayView from a pointer and a length.
   template <typename U>
   ArrayView(U* data, size_t size)
-      : data_(size == 0 ? nullptr : data), size_(size) {
-    CheckInvariant();
+      : impl::ArrayViewBase<T, Size>::ArrayViewBase(data, size) {
+    RTC_DCHECK_EQ(size == 0 ? nullptr : data, this->data());
+    RTC_DCHECK_EQ(size, this->size());
+    RTC_DCHECK_EQ(!this->data(),
+                  this->size() == 0);  // data is null iff size == 0.
   }
 
-  // Construct an ArrayView for an array.
+  // Construct an empty ArrayView. Note that fixed-size ArrayViews of size > 0
+  // cannot be empty.
+  ArrayView() : ArrayView(nullptr, 0) {}
+  ArrayView(std::nullptr_t) : ArrayView() {}
+  ArrayView(std::nullptr_t, size_t size)
+      : ArrayView(static_cast<T*>(nullptr), size) {
+    static_assert(Size == 0 || Size == impl::kArrayViewVarSize, "");
+    RTC_DCHECK_EQ(0, size);
+  }
+
+  // Construct an ArrayView from an array.
   template <typename U, size_t N>
-  ArrayView(U (&array)[N]) : ArrayView(&array[0], N) {}
+  ArrayView(U (&array)[N]) : ArrayView(array, N) {
+    static_assert(Size == N || Size == impl::kArrayViewVarSize,
+                  "Array size must match ArrayView size");
+  }
 
-  // Construct an ArrayView for any type U that has a size() method whose
-  // return value converts implicitly to size_t, and a data() method whose
-  // return value converts implicitly to T*. In particular, this means we allow
-  // conversion from ArrayView<T> to ArrayView<const T>, but not the other way
-  // around. Other allowed conversions include std::vector<T> to ArrayView<T>
-  // or ArrayView<const T>, const std::vector<T> to ArrayView<const T>, and
-  // rtc::Buffer to ArrayView<uint8_t> (with the same const behavior as
-  // std::vector).
+  // (Only if size is fixed.) Construct an ArrayView from any type U that has a
+  // static constexpr size() method whose return value is equal to Size, and a
+  // data() method whose return value converts implicitly to T*. In particular,
+  // this means we allow conversion from ArrayView<T, N> to ArrayView<const T,
+  // N>, but not the other way around. We also don't allow conversion from
+  // ArrayView<T> to ArrayView<T, N>, or from ArrayView<T, M> to ArrayView<T,
+  // N> when M != N.
+  template <typename U,
+            typename std::enable_if<
+                Size != impl::kArrayViewVarSize &&
+                HasDataAndSize<U, T>::value>::type* = nullptr>
+  ArrayView(U& u) : ArrayView(u.data(), u.size()) {
+    static_assert(U::size() == Size, "Sizes must match exactly");

[ossu, 2017/03/01 23:16:00]

Why can't the converted-to size be <= the converted-from's size?

[kwiberg-webrtc, 2017/03/02 03:00:39]

Well, it *could*, but IMO what you want for fixed-size array thingies is for the
compiler to verify that the sizes match, not for it to go, "Hey, yeah, I guess I
can fit this square peg into this round hole because its sides are at most
1/sqrt(2) times the hole's diameter."

[ossu, 2017/03/02 17:54:07]

Yeah, maybe having it implicit is too magical. I'm just wondering, if we have
something that takes an ArrayView<int, 10> and in turn wants to call a
sub-function on the two halves, where the sub-function takes an ArrayView<int,
5>, how we'd go about that as easily and securely as possible. (Without manual
pointer manipulation).

Maybe outside of the scope of this CL, and until we actually need it, but a
subview<index, size> call on static-sized ArrayViews would be sweet!

[kwiberg-webrtc, 2017/03/02 19:22:41]

Yes, a subview() with only template arguments was what I was thinking too.

+  }
+
+  // (Only if size is variable.) Construct an ArrayView from any type U that
+  // has a size() method whose return value converts implicitly to size_t, and
+  // a data() method whose return value converts implicitly to T*. In
+  // particular, this means we allow conversion from ArrayView<T> to
+  // ArrayView<const T>, but not the other way around. Other allowed
+  // conversions include
+  // ArrayView<T, N> to ArrayView<T> or ArrayView<const T>,
+  // std::vector<T> to ArrayView<T> or ArrayView<const T>,
+  // const std::vector<T> to ArrayView<const T>,
+  // rtc::Buffer to ArrayView<uint8_t> or ArrayView<const uint8_t>, and
+  // const rtc::Buffer to ArrayView<const uint8_t>.
   template <
       typename U,
-      typename std::enable_if<HasDataAndSize<U, T>::value>::type* = nullptr>
+      typename std::enable_if<Size == impl::kArrayViewVarSize &&
+                              HasDataAndSize<U, T>::value>::type* = nullptr>
   ArrayView(U& u) : ArrayView(u.data(), u.size()) {}
 
-  // Indexing, size, and iteration. These allow mutation even if the ArrayView
-  // is const, because the ArrayView doesn't own the array. (To prevent
-  // mutation, use ArrayView<const T>.)
-  size_t size() const { return size_; }
-  bool empty() const { return size_ == 0; }
-  T* data() const { return data_; }
+  // Indexing and iteration. These allow mutation even if the ArrayView is
+  // const, because the ArrayView doesn't own the array. (To prevent mutation,
+  // use a const element type.)
   T& operator[](size_t idx) const {
-    RTC_DCHECK_LT(idx, size_);
-    RTC_DCHECK(data_);  // Follows from size_ > idx and the class invariant.
-    return data_[idx];
+    RTC_DCHECK_LT(idx, this->size());
+    RTC_DCHECK(this->data());
+    return this->data()[idx];
   }
-  T* begin() const { return data_; }
-  T* end() const { return data_ + size_; }
-  const T* cbegin() const { return data_; }
-  const T* cend() const { return data_ + size_; }
+  T* begin() const { return this->data(); }
+  T* end() const { return this->data() + this->size(); }
+  const T* cbegin() const { return this->data(); }
+  const T* cend() const { return this->data() + this->size(); }
 
-  ArrayView subview(size_t offset, size_t size) const {
-    if (offset >= size_)
-      return ArrayView();
-    return ArrayView(data_ + offset, std::min(size, size_ - offset));
+  ArrayView<T> subview(size_t offset, size_t size) const {

[ossu, 2017/03/01 23:16:00]

I guess this is the way to convert to a smaller ArrayView, if wanted. Clamping
the size seems off to me. If I want a subview that's 100 entries big, why would
I accept one that's only 3 entries? Perhaps the non-sized variant could scale
automatically, but the sized one would be stricter?

On the other hand, maybe that just means a lot more std:min() expressions
littered throughout the code. Though that's probably less surprising when read.

[kwiberg-webrtc, 2017/03/02 03:00:39]

Yes, it can be argued both ways. But this was the existing behavior, and also
how std::string_view::substr() and the Google-internal ArraySlice do it.

[ossu, 2017/03/02 17:54:07]

Alright. SGTM!

+    return offset < this->size()
+               ? ArrayView<T>(this->data() + offset,
+                              std::min(size, this->size() - offset))
+               : ArrayView<T>();
   }
-  ArrayView subview(size_t offset) const { return subview(offset, size_); }
+  ArrayView<T> subview(size_t offset) const {
+    return subview(offset, this->size());
+  }
+};
 
-  // Comparing two ArrayViews compares their (pointer,size) pairs; it does
-  // *not* dereference the pointers.
-  friend bool operator==(const ArrayView& a, const ArrayView& b) {
-    return a.data_ == b.data_ && a.size_ == b.size_;
-  }
-  friend bool operator!=(const ArrayView& a, const ArrayView& b) {
-    return !(a == b);
-  }
+// Comparing two ArrayViews compares their (pointer,size) pairs; it does *not*
+// dereference the pointers.
+template <typename T, std::ptrdiff_t Size1, std::ptrdiff_t Size2>
+bool operator==(const ArrayView<T, Size1>& a, const ArrayView<T, Size2>& b) {
+  return a.data() == b.data() && a.size() == b.size();
+}
+template <typename T, std::ptrdiff_t Size1, std::ptrdiff_t Size2>
+bool operator!=(const ArrayView<T, Size1>& a, const ArrayView<T, Size2>& b) {
+  return !(a == b);
+}
 
- private:
-  // Invariant: !data_ iff size_ == 0.
-  void CheckInvariant() const { RTC_DCHECK_EQ(!data_, size_ == 0); }
-  T* data_;
-  size_t size_;
-};
+// Variable-size ArrayViews are the size of two pointers; fixed-size ArrayViews
+// are the size of one pointer. (And as a special case, fixed-size ArrayViews
+// of size 0 require no storage.)
+static_assert(sizeof(ArrayView<int>) == 2 * sizeof(int*), "");
+static_assert(sizeof(ArrayView<int, 17>) == sizeof(int*), "");
+static_assert(std::is_empty<ArrayView<int, 0>>::value, "");
 
 template <typename T>
 inline ArrayView<T> MakeArrayView(T* data, size_t size) {
   return ArrayView<T>(data, size);
 }
 
 }  // namespace rtc
 
 #endif  // WEBRTC_BASE_ARRAY_VIEW_H_