chromium/base/containers/span.h

// Copyright 2017 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef BASE_CONTAINERS_SPAN_H_
#define BASE_CONTAINERS_SPAN_H_

#include <stddef.h>
#include <stdint.h>
#include <string.h>

#include <algorithm>
#include <array>
#include <concepts>
#include <iosfwd>
#include <iterator>
#include <limits>
#include <memory>
#include <optional>
#include <span>
#include <type_traits>
#include <utility>

#include "base/check.h"
#include "base/compiler_specific.h"
#include "base/containers/checked_iterators.h"
#include "base/containers/dynamic_extent.h"
#include "base/numerics/safe_conversions.h"
#include "base/types/to_address.h"
#include "third_party/abseil-cpp/absl/base/attributes.h"

namespace base {

template <typename T,
          size_t Extent = dynamic_extent,
          typename InternalPtrType = T*>
class span;

namespace internal {

LegalDataConversion;

CompatibleIter;

CompatibleRange;

LegacyRangeDataIsPointer;

LegacyRange;

// NOTE: Ideally we'd just use `CompatibleRange`, however this currently breaks
// code that was written prior to C++20 being standardized and assumes providing
// .data() and .size() is sufficient.
// TODO: https://crbug.com/1504998 - Remove in favor of CompatibleRange and fix
// callsites.
LegacyCompatibleRange;

size_constant;

template <typename T>
struct ExtentImpl : size_constant<dynamic_extent> { … };

ExtentImpl<T[N]>;

ExtentImpl<std::array<T, N>>;

ExtentImpl<base::span<T, N>>;

Extent;

ExtentV;

// must_not_be_dynamic_extent prevents |dynamic_extent| from being returned in a
// constexpr context.
template <size_t kExtent>
constexpr size_t must_not_be_dynamic_extent() { … }

template <class T, class U, size_t N, size_t M>
  requires((N == M || N == dynamic_extent || M == dynamic_extent) &&
           std::equality_comparable_with<T, U>)
constexpr bool span_eq(span<T, N> l, span<U, M> r);
template <class T, class U, size_t N, size_t M>
  requires((N == M || N == dynamic_extent || M == dynamic_extent) &&
           std::three_way_comparable_with<T, U>)
constexpr auto span_cmp(span<T, N> l, span<U, M> r)
    -> decltype(l …);
template <class T, size_t N>
constexpr std::ostream& span_stream(std::ostream& l, span<T, N> r);

}  // namespace internal

// A span is a value type that represents an array of elements of type T. Since
// it only consists of a pointer to memory with an associated size, it is very
// light-weight. It is cheap to construct, copy, move and use spans, so that
// users are encouraged to use it as a pass-by-value parameter. A span does not
// own the underlying memory, so care must be taken to ensure that a span does
// not outlive the backing store.
//
// span is somewhat analogous to std::string_view, but with arbitrary element
// types, allowing mutation if T is non-const.
//
// span is implicitly convertible from C++ arrays, as well as most [1]
// container-like types that provide a data() and size() method (such as
// std::vector<T>). A mutable span<T> can also be implicitly converted to an
// immutable span<const T>.
//
// Consider using a span for functions that take a data pointer and size
// parameter: it allows the function to still act on an array-like type, while
// allowing the caller code to be a bit more concise.
//
// For read-only data access pass a span<const T>: the caller can supply either
// a span<const T> or a span<T>, while the callee will have a read-only view.
// For read-write access a mutable span<T> is required.
//
// Without span:
//   Read-Only:
//     // std::string HexEncode(const uint8_t* data, size_t size);
//     std::vector<uint8_t> data_buffer = GenerateData();
//     std::string r = HexEncode(data_buffer.data(), data_buffer.size());
//
//  Mutable:
//     // ssize_t SafeSNPrintf(char* buf, size_t N, const char* fmt, Args...);
//     char str_buffer[100];
//     SafeSNPrintf(str_buffer, sizeof(str_buffer), "Pi ~= %lf", 3.14);
//
// With span:
//   Read-Only:
//     // std::string HexEncode(base::span<const uint8_t> data);
//     std::vector<uint8_t> data_buffer = GenerateData();
//     std::string r = HexEncode(data_buffer);
//
//  Mutable:
//     // ssize_t SafeSNPrintf(base::span<char>, const char* fmt, Args...);
//     char str_buffer[100];
//     SafeSNPrintf(str_buffer, "Pi ~= %lf", 3.14);
//
// Dynamic-extent spans vs fixed-extent spans
// ------------------------------------------
//
// A `span<T>` has a dynamic extent—the size of the sequence of objects it
// refers to is only known at runtime. It is also possible to create a span with
// a fixed size at compile time by specifying the second template parameter,
// e.g. `span<int, 6>` is a span of 6 elements. Operations on a fixed-extent
// span will fail to compile if an index or size would lead to an out-of-bounds
// access.
//
// A fixed-extent span implicitly converts to a dynamic-extent span (e.g.
// `span<int, 6>` is implicitly convertible to `span<int>`), so most code that
// operates on spans of arbitrary length can just accept a `span<T>`: there is
// no need to add an additional overload for specially handling the `span<T, N>`
// case.
//
// There are several ways to go from a dynamic-extent span to a fixed-extent
// span:
// - Use the convenience `to_fixed_extent<N>()` method. This returns
//   `std::nullopt` if `size() != N`.
// - Use `first<N>()`, `last<N>()`, or `subspan<Index, N>()` to create a
//   subsequence of the original span. These methods will `CHECK()` at runtime
//   if the requested subsequence would lead to an out-of-bounds access.
// - Explicitly construct `span<T, N>` from `span<T>`: this will `CHECK()` at
//   runtime if the input span's `size()` is not exactly `N`.
//
// Spans with "const" and pointers
// -------------------------------
//
// Const and pointers can get confusing. Here are vectors of pointers and their
// corresponding spans:
//
//   const std::vector<int*>        =>  base::span<int* const>
//   std::vector<const int*>        =>  base::span<const int*>
//   const std::vector<const int*>  =>  base::span<const int* const>
//
// Differences from the C++ standard
// ---------------------------------
//
// http://eel.is/c++draft/views.span contains the latest C++ draft of std::span.
// Chromium tries to follow the draft as close as possible. Differences between
// the draft and the implementation are documented in subsections below.
//
// Differences from [span.overview]:
// - Dynamic spans are implemented as a partial specialization of the regular
//   class template. This leads to significantly simpler checks involving the
//   extent, at the expense of some duplicated code. The same strategy is used
//   by libc++.
//
// Differences from [span.objectrep]:
// - as_bytes() and as_writable_bytes() return spans of uint8_t instead of
//   std::byte.
//
// Differences from [span.cons]:
// - The constructors from a contiguous range apart from a C array are folded
//   into a single one, using a construct similarly to the one proposed
//   (but not standardized) in https://wg21.link/P1419.
//   The C array constructor is kept so that a span can be constructed from
//   an init list like {{1, 2, 3}}.
//   TODO: https://crbug.com/828324 - Consider adding C++26's constructor from
//   a std::initializer_list instead.
// - The conversion constructors from a contiguous range into a dynamic span
//   don't check for the range concept, but rather whether std::ranges::data
//   and std::ranges::size are well formed. This is due to legacy reasons and
//   should be fixed.
//
// Differences from [span.deduct]:
// - The deduction guides from a contiguous range are folded into a single one,
//   and treat borrowed ranges correctly.
// - Add deduction guide from rvalue array.
//
// Other differences:
// - Using StrictNumeric<size_t> instead of size_t where possible.
//
// Additions beyond the C++ standard draft
// - as_chars() function.
// - as_writable_chars() function.
// - as_byte_span() function.
// - as_writable_byte_span() function.
// - copy_from() method.
// - copy_from_nonoverlapping() method.
// - span_from_ref() function.
// - byte_span_from_ref() function.
// - span_from_cstring() function.
// - span_with_nul_from_cstring() function.
// - byte_span_from_cstring() function.
// - byte_span_with_nul_from_cstring() function.
// - split_at() method.
// - to_fixed_extent() method.
// - operator==() comparator function.
// - operator<=>() comparator function.
// - operator<<() printing function.
//
// Furthermore, all constructors and methods are marked noexcept due to the lack
// of exceptions in Chromium.
//
// Due to the lack of class template argument deduction guides in C++14
// appropriate make_span() utility functions are provided for historic reasons.

// [span], class template span
template <typename T, size_t N, typename InternalPtrType>
class GSL_POINTER span { … };

// [span], class template span
span<T, dynamic_extent, InternalPtrType>;

// [span.deduct], deduction guides.
template <typename It, typename EndOrSize>
  requires(std::contiguous_iterator<It>)
span(It, EndOrSize) -> span<std::remove_reference_t<std::iter_reference_t<It>>>;

template <
    typename R,
    typename T = std::remove_reference_t<std::ranges::range_reference_t<R>>>
  requires(std::ranges::contiguous_range<R>)
span(R&&)
    -> span<std::conditional_t<std::ranges::borrowed_range<R>, T, const T>,
            internal::ExtentV<R>>;

// This guide prefers to let the contiguous_range guide match, since it can
// produce a fixed-size span. Whereas, LegacyRange only produces a dynamic-sized
// span.
template <typename R>
  requires(!std::ranges::contiguous_range<R> && internal::LegacyRange<R>)
span(R&& r) noexcept
    -> span<std::remove_reference_t<decltype(*std::ranges::data(r))>>;

template <typename T, size_t N>
span(const T (&)[N]) -> span<const T, N>;

// span can be printed and will print each of its values, including in Gtests.
//
// TODO(danakj): This could move to a ToString() member method if gtest printers
// were hooked up to base::ToString().
template <class T, size_t N>
constexpr std::ostream& operator<<(std::ostream& l, span<T, N> r) { … }

// [span.objectrep], views of object representation
template <typename T, size_t X, typename InternalPtrType>
constexpr auto as_bytes(span<T, X, InternalPtrType> s) noexcept { … }

template <typename T, size_t X, typename InternalPtrType>
  requires(!std::is_const_v<T>)
constexpr auto as_writable_bytes(span<T, X, InternalPtrType> s) noexcept { … }

// as_chars() is the equivalent of as_bytes(), except that it returns a
// span of const char rather than const uint8_t. This non-std function is
// added since chrome still represents many things as char arrays which
// rightfully should be uint8_t.
template <typename T, size_t X, typename InternalPtrType>
constexpr auto as_chars(span<T, X, InternalPtrType> s) noexcept { … }

// as_string_view() converts a span over byte-sized primitives (holding chars or
// uint8_t) into a std::string_view, where each byte is represented as a char.
// It also accepts any type that can implicitly convert to a span, such as
// arrays.
//
// If you want to view an arbitrary span type as a string, first explicitly
// convert it to bytes via `base::as_bytes()`.
//
// For spans over byte-sized primitives, this is sugar for:
// ```
// std::string_view(as_chars(span).begin(), as_chars(span).end())
// ```
constexpr std::string_view as_string_view(span<const char> s) noexcept { … }
constexpr std::string_view as_string_view(
    span<const unsigned char> s) noexcept { … }

// as_writable_chars() is the equivalent of as_writable_bytes(), except that
// it returns a span of char rather than uint8_t. This non-std function is
// added since chrome still represents many things as char arrays which
// rightfully should be uint8_t.
template <typename T, size_t X, typename InternalPtrType>
  requires(!std::is_const_v<T>)
auto as_writable_chars(span<T, X, InternalPtrType> s) noexcept { … }

// Type-deducing helper for constructing a span.
//
// # Safety
// The contiguous iterator `it` must point to the first element of at least
// `size` many elements or Undefined Behaviour may result as the span may give
// access beyond the bounds of the collection pointed to by `it`.
template <int&... ExplicitArgumentBarrier, typename It>
UNSAFE_BUFFER_USAGE constexpr auto make_span(
    It it,
    StrictNumeric<size_t> size) noexcept { … }

// Type-deducing helper for constructing a span.
//
// # Checks
// The function CHECKs that `it <= end` and will terminate otherwise.
//
// # Safety
// The contiguous iterator `it` and its end sentinel `end` must be for the same
// allocation or Undefined Behaviour may result as the span may give access
// beyond the bounds of the collection pointed to by `it`.
template <int&... ExplicitArgumentBarrier,
          typename It,
          typename End,
          typename = std::enable_if_t<!std::is_convertible_v<End, size_t>>>
UNSAFE_BUFFER_USAGE constexpr auto make_span(It it, End end) noexcept { … }

// make_span utility function that deduces both the span's value_type and extent
// from the passed in argument.
//
// Usage: auto span = base::make_span(...);
template <int&... ExplicitArgumentBarrier, typename Container>
constexpr auto make_span(Container&& container) noexcept { … }

// `span_from_ref` converts a reference to T into a span of length 1.  This is a
// non-std helper that is inspired by the `std::slice::from_ref()` function from
// Rust.
template <typename T>
constexpr span<T, 1u> span_from_ref(
    T& single_object ABSL_ATTRIBUTE_LIFETIME_BOUND) noexcept { … }

// `byte_span_from_ref` converts a reference to T into a span of uint8_t of
// length sizeof(T).  This is a non-std helper that is a sugar for
// `as_writable_bytes(span_from_ref(x))`.
//
// Const references are turned into a `span<const T, sizeof(T)>` while mutable
// references are turned into a `span<T, sizeof(T)>`.
template <typename T>
constexpr span<const uint8_t, sizeof(T)> byte_span_from_ref(
    const T& single_object ABSL_ATTRIBUTE_LIFETIME_BOUND) noexcept { … }
template <typename T>
constexpr span<uint8_t, sizeof(T)> byte_span_from_ref(
    T& single_object ABSL_ATTRIBUTE_LIFETIME_BOUND) noexcept { … }

// Converts a string literal (such as `"hello"`) to a span of `CharT` while
// omitting the terminating NUL character. These two are equivalent:
// ```
// base::span<char, 5u> s1 = base::span_from_cstring("hello");
// base::span<char, 5u> s2 = base::span(std::string_view("hello"));
// ```
//
// If you want to include the NUL terminator in the span, then use
// `span_with_nul_from_cstring()`.
//
// Internal NUL characters (ie. that are not at the end of the string) are
// always preserved.
template <class CharT, size_t N>
constexpr span<const CharT, N - 1> span_from_cstring(
    const CharT (&lit ABSL_ATTRIBUTE_LIFETIME_BOUND)[N])
    ENABLE_IF_ATTR(lit[N - 1u] == CharT{ … }

// Converts a string literal (such as `"hello"`) to a span of `CharT` that
// includes the terminating NUL character. These two are equivalent:
// ```
// base::span<char, 6u> s1 = base::span_with_nul_from_cstring("hello");
// auto h = std::cstring_view("hello");
// base::span<char, 6u> s2 =
//     UNSAFE_BUFFERS(base::span(h.data(), h.size() + 1u));
// ```
//
// If you do not want to include the NUL terminator, then use
// `span_from_cstring()` or use a view type (e.g. `base::cstring_view` or
// `std::string_view`) in place of a string literal.
//
// Internal NUL characters (ie. that are not at the end of the string) are
// always preserved.
template <class CharT, size_t N>
constexpr span<const CharT, N> span_with_nul_from_cstring(
    const CharT (&lit ABSL_ATTRIBUTE_LIFETIME_BOUND)[N])
    ENABLE_IF_ATTR(lit[N - 1u] == CharT{ … }

// Converts a string literal (such as `"hello"`) to a span of `uint8_t` while
// omitting the terminating NUL character. These two are equivalent:
// ```
// base::span<uint8_t, 5u> s1 = base::byte_span_from_cstring("hello");
// base::span<uint8_t, 5u> s2 = base::as_byte_span(std::string_view("hello"));
// ```
//
// If you want to include the NUL terminator in the span, then use
// `byte_span_with_nul_from_cstring()`.
//
// Internal NUL characters (ie. that are not at the end of the string) are
// always preserved.
template <size_t N>
constexpr span<const uint8_t, N - 1> byte_span_from_cstring(
    const char (&lit ABSL_ATTRIBUTE_LIFETIME_BOUND)[N])
    ENABLE_IF_ATTR(lit[N - 1u] == '\0', "requires string literal as input") { … }

// Converts a string literal (such as `"hello"`) to a span of `uint8_t` that
// includes the terminating NUL character. These two are equivalent:
// ```
// base::span<uint8_t, 6u> s1 = base::byte_span_with_nul_from_cstring("hello");
// auto h = base::cstring_view("hello");
// base::span<uint8_t, 6u> s2 = base::as_bytes(
//     UNSAFE_BUFFERS(base::span(h.data(), h.size() + 1u)));
// ```
//
// If you do not want to include the NUL terminator, then use
// `byte_span_from_cstring()` or use a view type (`base::cstring_view` or
// `std::string_view`) in place of a string literal and `as_byte_span()`.
//
// Internal NUL characters (ie. that are not at the end of the string) are
// always preserved.
template <size_t N>
constexpr span<const uint8_t, N> byte_span_with_nul_from_cstring(
    const char (&lit ABSL_ATTRIBUTE_LIFETIME_BOUND)[N])
    ENABLE_IF_ATTR(lit[N - 1u] == '\0', "requires string literal as input") { … }

// Convenience function for converting an object which is itself convertible
// to span into a span of bytes (i.e. span of const uint8_t). Typically used
// to convert std::string or string-objects holding chars, or std::vector
// or vector-like objects holding other scalar types, prior to passing them
// into an API that requires byte spans.
template <int&... ExplicitArgumentBarrier, typename Spannable>
  requires requires(const Spannable& arg) { … }

template <int&... ExplicitArgumentBarrier, typename T, size_t N>
constexpr span<const uint8_t, N * sizeof(T)> as_byte_span(
    const T (&arr ABSL_ATTRIBUTE_LIFETIME_BOUND)[N]) { … }

// Convenience function for converting an object which is itself convertible
// to span into a span of mutable bytes (i.e. span of uint8_t). Typically used
// to convert std::string or string-objects holding chars, or std::vector
// or vector-like objects holding other scalar types, prior to passing them
// into an API that requires mutable byte spans.
template <int&... ExplicitArgumentBarrier, typename Spannable>
  requires requires(Spannable&& arg) { … }

// This overload for arrays preserves the compile-time size N of the array in
// the span type signature span<uint8_t, N>.
template <int&... ExplicitArgumentBarrier, typename T, size_t N>
constexpr span<uint8_t, N * sizeof(T)> as_writable_byte_span(
    T (&arr ABSL_ATTRIBUTE_LIFETIME_BOUND)[N]) { … }

template <int&... ExplicitArgumentBarrier, typename T, size_t N>
constexpr span<uint8_t, N * sizeof(T)> as_writable_byte_span(
    T (&&arr ABSL_ATTRIBUTE_LIFETIME_BOUND)[N]) { … }

namespace internal {

// Template helper for implementing operator==.
template <class T, class U, size_t N, size_t M>
  requires((N == M || N == dynamic_extent || M == dynamic_extent) &&
           std::equality_comparable_with<T, U>)
constexpr bool span_eq(span<T, N> l, span<U, M> r) { … }

// Template helper for implementing operator<=>.
template <class T, class U, size_t N, size_t M>
  requires((N == M || N == dynamic_extent || M == dynamic_extent) &&
           std::three_way_comparable_with<T, U>)
constexpr auto span_cmp(span<T, N> l, span<U, M> r)
    -> decltype(l[0u] <=> r[0u]) { … }

// Template helper for implementing printing.
template <class T, size_t N>
constexpr std::ostream& span_stream(std::ostream& l, span<T, N> r) { … }

}  // namespace internal

}  // namespace base

enable_borrowed_range;

enable_view;

// EXTENT returns the size of any type that can be converted to a |base::span|
// with definite extent, i.e. everything that is a contiguous storage of some
// sort with static size. Specifically, this works for std::array in a constexpr
// context. Note:
//   * |std::size| should be preferred for plain arrays.
//   * In run-time contexts, functions such as |std::array::size| should be
//     preferred.
#define EXTENT(x) …

#endif  // BASE_CONTAINERS_SPAN_H_