[libc] Add a span facility

[gchatelet]

Summary

This is intended to replace ArrayRef.

[tschuett]

Where do you use enable_if? data_ is libc coding conventions? It is not conforming to the LLVM coding conventions.

[gchatelet]

• Address comments

[gchatelet]

In D132254#3735835, @tschuett wrote:

Where do you use enable_if? data_ is libc coding conventions? It is not conforming to the LLVM coding conventions.

Thx @tschuett for the comments. Done.

[tschuett]

libc/src/__support/CPP/span.h

18

Nit: You may use nested namespaces.

83

Nit: snake case?

[gchatelet]

• Address comments

[gchatelet]

libc/src/__support/CPP/span.h

83

Nit:snake case?

Did you meant camelCase for dynamic_extent?

[sivachandra]

libc/src/__support/CPP/span.h

83

I think s/countToSize/count_to_size/

[gchatelet]

libc/src/__support/CPP/span.h

83

It was count_to_size (snake case) originally and I thought @tschuett asked me to go to camelCase. Then I figured out that the modifications I made to the file probably messed out with the lines on which the comment was attached (Phabricator... sigh). I inferred that it was probably dynamic_extent that was the culprit rather than count_to_size. But now I'm confused😅

[sivachandra]

libc/src/__support/CPP/span.h

83

I am also confused. Normal LLVM conventions do not apply in the libc directory, and the cpp namespace is even more special. So, I think count_to_size is correct. Likewise Data and Size are also not compliant. We can go with span_data and span_size to disambiguate with the methods data and size.

[gchatelet]

Address comments and rebase

[gchatelet]

• Also convert countToSize to snake_case

[tschuett]

https://llvm.org/docs/CodingStandards.html#id43

"As an exception, classes that mimic STL classes can have member names in STL’s style of lower-case words separated by underscores (e.g. begin(), push_back(), and empty()). Classes that provide multiple iterators should add a singular prefix to begin() and end() (e.g. global_begin() and use_begin())."

libc/src/__support/CPP/CMakeLists.txt

add_header_library(
   limits
   HDRS
     limits.h
   DEPENDS
     .uint
 )
 
 add_header_library(
+  span
+  HDRS
+    span.h
+  DEPENDS
+    .type_traits
+)
+
+add_header_library(
   string_view
   HDRS
     StringView.h
 )
 
 add_header_library(
   stringstream
   HDRS

libc/src/__support/CPP/span.h

+//===-- Standalone implementation std::span ---------------------*- 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_SRC_SUPPORT_CPP_SPAN_H
+#define LLVM_LIBC_SRC_SUPPORT_CPP_SPAN_H
+
+#include <stddef.h> // For size_t
+
+#include "array.h"       // For array
+#include "type_traits.h" // For remove_cv_t
+
+namespace __llvm_libc::cpp {
+
+// A trimmed down implementation of std::span.
+// Missing features:
+// - No constant size spans (e.g. Span<int, 4>),
+// - Only handle pointer like types, no fancy interators nor object overriding
+//   the & operator,
+// - No implicit type conversion (e.g. Span<B>, initialized with As where A
+//   inherits from B),
+// - No reverse iterators
+template <typename T> class span {
+public:
+  using element_type = T;
+  using value_type = remove_cv_t<T>;
+  using size_type = size_t;
+  using difference_type = ptrdiff_t;
+  using pointer = T *;
+  using const_pointer = const T *;
+  using reference = T &;
+  using const_reference = const T &;
+  using iterator = T *;
+
+  static constexpr size_type dynamic_extent = -1;
+
+  constexpr span() : Data(nullptr), Size(0) {}
+
+  constexpr span(pointer first, size_type count) : Data(first), Size(count) {}
+
+  constexpr span(pointer first, pointer end) : Data(first), Size(end - first) {}
+
+  template <size_t N>
+  constexpr span(element_type (&arr)[N]) : Data(arr), Size(N) {}
+
+  template <size_t N>
+  constexpr span(array<T, N> &arr) : Data(arr.data()), Size(arr.size()) {}
+
+  constexpr span(const span &s) = default;
+  constexpr span &operator=(const span &s) = default;
+  ~span() = default;
+  constexpr reference operator[](size_type index) const {
+    return data()[index];
+  }
+  constexpr iterator begin() const { return data(); }
+  constexpr iterator end() const { return data() + size(); }
+  constexpr reference front() const { return (*this)[0]; }
+  constexpr reference back() const { return (*this)[size() - 1]; }
+  constexpr pointer data() const { return Data; }
+  constexpr size_type size() const { return Size; }
+  constexpr size_type size_bytes() const { return sizeof(T) * size(); }
+  constexpr bool empty() const { return size() == 0; }
+
+  constexpr span<element_type> subspan(size_type offset,
+                                       size_type count = dynamic_extent) const {
+    return span<element_type>(data() + offset, countToSize(offset, count));
+  }
+
+  constexpr span<element_type> first(size_type count) const {
+    return subspan(0, count);
+  }
+
+  constexpr span<element_type> last(size_type count) const {
+    return span<element_type>(data() + (size() - count), count);
+  }
+
+private:
+  constexpr size_type countToSize(size_type offset, size_type count) const {
+    if (count == dynamic_extent) {
+      return size() - offset;
+    }
+    return count;
+  }
+
+  T *Data;
+  size_t Size;
+};
+
+} // namespace __llvm_libc::cpp
+
+#endif /* LLVM_LIBC_SRC_SUPPORT_CPP_SPAN_H */

libc/test/src/__support/CPP/CMakeLists.txt

add_libc_unittest(
   optional_test
   SUITE
     libc_cpp_utils_unittests
   SRCS
     optional_test.cpp
   DEPENDS
   libc.src.__support.CPP.optional
 )
+
+add_libc_unittest(
+  span_test
+  SUITE
+    libc_cpp_utils_unittests
+  SRCS
+    span_test.cpp
+  DEPENDS
+  libc.src.__support.CPP.span
+)

libc/test/src/__support/CPP/span_test.cpp

+//===-- Unittests for span ------------------------------------------------===//
+//
+// 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 "src/__support/CPP/array.h"
+#include "src/__support/CPP/span.h"
+#include "utils/UnitTest/Test.h"
+
+using __llvm_libc::cpp::array;
+using __llvm_libc::cpp::span;
+
+TEST(LlvmLibcSpanTest, InitializeEmpty) {
+  span<int> s;
+  ASSERT_EQ(s.size(), size_t(0));
+  ASSERT_TRUE(s.empty());
+  ASSERT_TRUE(s.data() == nullptr);
+}
+
+TEST(LlvmLibcSpanTest, InitializeSingleton) {
+  int a = 42;
+  span<int> s(&a, 1);
+  ASSERT_EQ(s.size(), size_t(1));
+  ASSERT_FALSE(s.empty());
+  ASSERT_TRUE(s.data() == &a);
+  ASSERT_EQ(s.front(), 42);
+  ASSERT_EQ(s.back(), 42);
+}
+
+TEST(LlvmLibcSpanTest, InitializeCArray) {
+  int a[] = {1, 2, 3};
+  span<int> s(a);
+  ASSERT_EQ(s.size(), size_t(3));
+  ASSERT_FALSE(s.empty());
+  ASSERT_TRUE(s.data() == &a[0]);
+  ASSERT_EQ(s.front(), 1);
+  ASSERT_EQ(s.back(), 3);
+  ASSERT_EQ(s[0], 1);
+  ASSERT_EQ(s[1], 2);
+  ASSERT_EQ(s[2], 3);
+}
+
+TEST(LlvmLibcSpanTest, InitializeArray) {
+  array<int, 3> a = {1, 2, 3};
+  span<int> s(a);
+  ASSERT_EQ(s.size(), size_t(3));
+  ASSERT_FALSE(s.empty());
+  ASSERT_TRUE(s.data() == &a[0]);
+  ASSERT_EQ(s.front(), 1);
+  ASSERT_EQ(s.back(), 3);
+  ASSERT_EQ(s[0], 1);
+  ASSERT_EQ(s[1], 2);
+  ASSERT_EQ(s[2], 3);
+}
+
+TEST(LlvmLibcSpanTest, Modify) {
+  int a[] = {1, 2, 3};
+  span<int> s(a);
+  for (int &value : s)
+    ++value;
+  ASSERT_EQ(s.size(), size_t(3));
+  ASSERT_EQ(s[0], 2);
+  ASSERT_EQ(s[1], 3);
+  ASSERT_EQ(s[2], 4);
+}
+
+TEST(LlvmLibcSpanTest, SubSpan) {
+  int a[] = {1, 2, 3};
+  span<const int> s(a);
+  { // same span
+    const auto _ = s.subspan(0);
+    ASSERT_EQ(_.size(), size_t(3));
+    ASSERT_EQ(_[0], 1);
+    ASSERT_EQ(_[1], 2);
+    ASSERT_EQ(_[2], 3);
+  }
+  { // last element
+    const auto _ = s.subspan(2);
+    ASSERT_EQ(_.size(), size_t(1));
+    ASSERT_EQ(_[0], 3);
+  }
+  { // no element
+    const auto _ = s.subspan(3);
+    ASSERT_EQ(_.size(), size_t(0));
+  }
+  { // first element
+    const auto _ = s.subspan(0, 1);
+    ASSERT_EQ(_.size(), size_t(1));
+    ASSERT_EQ(_[0], 1);
+  }
+}
+
+TEST(LlvmLibcSpanTest, FirstAndLastSubSpan) {
+  int a[] = {1, 2, 3};
+  span<const int> s(a);
+
+  const auto first = s.first(2);
+  ASSERT_EQ(first.size(), size_t(2));
+  ASSERT_EQ(first[0], 1);
+  ASSERT_EQ(first[1], 2);
+
+  const auto last = s.last(2);
+  ASSERT_EQ(last.size(), size_t(2));
+  ASSERT_EQ(last[0], 2);
+  ASSERT_EQ(last[1], 3);
+}