// Copyright 2017 The Chromium Authors. All rights reserved. // 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 #include #include #include #include #include #include "base/check.h" #include "base/compiler_specific.h" #include "base/containers/checked_iterators.h" #include "base/containers/contiguous_iterator.h" #include "base/cxx20_to_address.h" namespace base { // [views.constants] constexpr size_t dynamic_extent = std::numeric_limits::max(); template class span; namespace internal { template using size_constant = std::integral_constant; template struct ExtentImpl : size_constant {}; template struct ExtentImpl : size_constant {}; template struct ExtentImpl> : size_constant {}; template struct ExtentImpl> : size_constant {}; template using Extent = ExtentImpl>; template struct IsSpanImpl : std::false_type {}; template struct IsSpanImpl> : std::true_type {}; template using IsNotSpan = std::negation>>; template struct IsStdArrayImpl : std::false_type {}; template struct IsStdArrayImpl> : std::true_type {}; template using IsNotStdArray = std::negation>>; template using IsNotCArray = std::negation>>; template using IsLegalDataConversion = std::is_convertible; template using IteratorHasConvertibleReferenceType = IsLegalDataConversion>, T>; template using EnableIfCompatibleContiguousIterator = std::enable_if_t< std::conjunction, IteratorHasConvertibleReferenceType>::value>; template using ContainerHasConvertibleData = IsLegalDataConversion< std::remove_pointer_t()))>, T>; template using ContainerHasIntegralSize = std::is_integral()))>; template using EnableIfLegalSpanConversion = std::enable_if_t<(ToExtent == dynamic_extent || ToExtent == FromExtent) && IsLegalDataConversion::value>; // SFINAE check if Array can be converted to a span. template using EnableIfSpanCompatibleArray = std::enable_if_t<(Extent == dynamic_extent || Extent == internal::Extent::value) && ContainerHasConvertibleData::value>; // SFINAE check if Container can be converted to a span. template using IsSpanCompatibleContainer = std::conjunction, IsNotStdArray, IsNotCArray, ContainerHasConvertibleData, ContainerHasIntegralSize>; template using EnableIfSpanCompatibleContainer = std::enable_if_t::value>; template using EnableIfSpanCompatibleContainerAndSpanIsDynamic = std::enable_if_t::value && Extent == dynamic_extent>; // A helper template for storing the size of a span. Spans with static extents // don't require additional storage, since the extent itself is specified in the // template parameter. template class ExtentStorage { public: constexpr explicit ExtentStorage(size_t size) noexcept {} constexpr size_t size() const noexcept { return Extent; } }; // Specialization of ExtentStorage for dynamic extents, which do require // explicit storage for the size. template <> struct ExtentStorage { constexpr explicit ExtentStorage(size_t size) noexcept : size_(size) {} constexpr size_t size() const noexcept { return size_; } private: size_t size_; }; // must_not_be_dynamic_extent prevents |dynamic_extent| from being returned in a // constexpr context. template constexpr size_t must_not_be_dynamic_extent() { static_assert( kExtent != dynamic_extent, "EXTENT should only be used for containers with a static extent."); return kExtent; } } // 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 StringPiece, 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). A mutable span can also be implicitly converted to an // immutable span. // // 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: the caller can supply either // a span or a span, while the callee will have a read-only view. // For read-write access a mutable span is required. // // Without span: // Read-Only: // // std::string HexEncode(const uint8_t* data, size_t size); // std::vector 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 data); // std::vector data_buffer = GenerateData(); // std::string r = HexEncode(data_buffer); // // Mutable: // // ssize_t SafeSNPrintf(base::span, const char* fmt, Args...); // char str_buffer[100]; // SafeSNPrintf(str_buffer, "Pi ~= %lf", 3.14); // // Spans with "const" and pointers // ------------------------------- // // Const and pointers can get confusing. Here are vectors of pointers and their // corresponding spans: // // const std::vector => base::span // std::vector => base::span // const std::vector => base::span // // Differences from the C++20 draft // -------------------------------- // // http://eel.is/c++draft/views contains the latest C++20 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.objectrep]: // - as_bytes() and as_writable_bytes() return spans of uint8_t instead of // std::byte (std::byte is a C++17 feature) // // Differences from [span.cons]: // - Constructing a static span (i.e. Extent != dynamic_extent) from a dynamic // sized container (e.g. std::vector) requires an explicit conversion (in the // C++20 draft this is simply UB) // // 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. // [span], class template span template class GSL_POINTER span : public internal::ExtentStorage { private: using ExtentStorage = internal::ExtentStorage; public: using element_type = T; using value_type = std::remove_cv_t; using size_type = size_t; using difference_type = ptrdiff_t; using pointer = T*; using reference = T&; using iterator = CheckedContiguousIterator; // TODO(https://crbug.com/828324): Drop the const_iterator typedef once gMock // supports containers without this nested type. using const_iterator = iterator; using reverse_iterator = std::reverse_iterator; static constexpr size_t extent = Extent; // [span.cons], span constructors, copy, assignment, and destructor constexpr span() noexcept : ExtentStorage(0), data_(nullptr) { static_assert(Extent == dynamic_extent || Extent == 0, "Invalid Extent"); } template > constexpr span(It first, size_t count) noexcept : ExtentStorage(count), // The use of to_address() here is to handle the case where the iterator // `first` is pointing to the container's `end()`. In that case we can // not use the address returned from the iterator, or dereference it // through the iterator's `operator*`, but we can store it. We must assume // in this case that `count` is 0, since the iterator does not point to // valid data. Future hardening of iterators may disallow pulling the // address from `end()`, as demonstrated by asserts() in libstdc++: // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93960. // // The span API dictates that the `data()` is accessible when size is 0, // since the pointer may be valid, so we cannot prevent storing and // giving out an invalid pointer here without breaking API compatibility // and our unit tests. Thus protecting against this can likely only be // successful from inside iterators themselves, where the context about // the pointer is known. // // We can not protect here generally against an invalid iterator/count // being passed in, since we have no context to determine if the // iterator or count are valid. data_(base::to_address(first)) { CHECK(Extent == dynamic_extent || Extent == count); } template < typename It, typename End, typename = internal::EnableIfCompatibleContiguousIterator, typename = std::enable_if_t::value>> constexpr span(It begin, End end) noexcept // Subtracting two iterators gives a ptrdiff_t, but the result should be // non-negative: see CHECK below. : span(begin, static_cast(end - begin)) { // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. CHECK(begin <= end); } template < size_t N, typename = internal::EnableIfSpanCompatibleArray> constexpr span(T (&array)[N]) noexcept : span(std::data(array), N) {} template < typename U, size_t N, typename = internal::EnableIfSpanCompatibleArray&, T, Extent>> constexpr span(std::array& array) noexcept : span(std::data(array), N) {} template &, T, Extent>> constexpr span(const std::array& array) noexcept : span(std::data(array), N) {} // Conversion from a container that has compatible std::data() and integral // std::size(). template < typename Container, typename = internal::EnableIfSpanCompatibleContainerAndSpanIsDynamic> constexpr span(Container& container) noexcept : span(std::data(container), std::size(container)) {} template < typename Container, typename = internal::EnableIfSpanCompatibleContainerAndSpanIsDynamic< const Container&, T, Extent>> constexpr span(const Container& container) noexcept : span(std::data(container), std::size(container)) {} constexpr span(const span& other) noexcept = default; // Conversions from spans of compatible types and extents: this allows a // span to be seamlessly used as a span, but not the other way // around. If extent is not dynamic, OtherExtent has to be equal to Extent. template < typename U, size_t OtherExtent, typename = internal::EnableIfLegalSpanConversion> constexpr span(const span& other) : span(other.data(), other.size()) {} constexpr span& operator=(const span& other) noexcept = default; ~span() noexcept = default; // [span.sub], span subviews template constexpr span first() const noexcept { static_assert(Count <= Extent, "Count must not exceed Extent"); CHECK(Extent != dynamic_extent || Count <= size()); return {data(), Count}; } template constexpr span last() const noexcept { static_assert(Count <= Extent, "Count must not exceed Extent"); CHECK(Extent != dynamic_extent || Count <= size()); return {data() + (size() - Count), Count}; } template constexpr span subspan() const noexcept { static_assert(Offset <= Extent, "Offset must not exceed Extent"); static_assert(Count == dynamic_extent || Count <= Extent - Offset, "Count must not exceed Extent - Offset"); CHECK(Extent != dynamic_extent || Offset <= size()); CHECK(Extent != dynamic_extent || Count == dynamic_extent || Count <= size() - Offset); return {data() + Offset, Count != dynamic_extent ? Count : size() - Offset}; } constexpr span first(size_t count) const noexcept { // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. CHECK(count <= size()); return {data(), count}; } constexpr span last(size_t count) const noexcept { // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. CHECK(count <= size()); return {data() + (size() - count), count}; } constexpr span subspan(size_t offset, size_t count = dynamic_extent) const noexcept { // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. CHECK(offset <= size()); CHECK(count == dynamic_extent || count <= size() - offset); return {data() + offset, count != dynamic_extent ? count : size() - offset}; } // [span.obs], span observers constexpr size_t size() const noexcept { return ExtentStorage::size(); } constexpr size_t size_bytes() const noexcept { return size() * sizeof(T); } [[nodiscard]] constexpr bool empty() const noexcept { return size() == 0; } // [span.elem], span element access constexpr T& operator[](size_t idx) const noexcept { // Note: CHECK_LT is not constexpr, hence regular CHECK must be used. CHECK(idx < size()); return *(data() + idx); } constexpr T& front() const noexcept { static_assert(Extent == dynamic_extent || Extent > 0, "Extent must not be 0"); CHECK(Extent != dynamic_extent || !empty()); return *data(); } constexpr T& back() const noexcept { static_assert(Extent == dynamic_extent || Extent > 0, "Extent must not be 0"); CHECK(Extent != dynamic_extent || !empty()); return *(data() + size() - 1); } constexpr T* data() const noexcept { return data_; } // [span.iter], span iterator support constexpr iterator begin() const noexcept { return iterator(data_, data_ + size()); } constexpr iterator end() const noexcept { return iterator(data_, data_ + size(), data_ + size()); } constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(end()); } constexpr reverse_iterator rend() const noexcept { return reverse_iterator(begin()); } private: T* data_; }; // span::extent can not be declared inline prior to C++17, hence this // definition is required. template constexpr size_t span::extent; // [span.objectrep], views of object representation template span as_bytes(span s) noexcept { return {reinterpret_cast(s.data()), s.size_bytes()}; } template ::value>> span as_writable_bytes(span s) noexcept { return {reinterpret_cast(s.data()), s.size_bytes()}; } // Type-deducing helpers for constructing a span. template constexpr auto make_span(It it, size_t size) noexcept { using T = std::remove_reference_t>; return span(it, size); } template >> constexpr auto make_span(It it, End end) noexcept { using T = std::remove_reference_t>; return span(it, end); } // 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 constexpr auto make_span(Container&& container) noexcept { using T = std::remove_pointer_t()))>; using Extent = internal::Extent; return span(std::forward(container)); } // make_span utility functions that allow callers to explicit specify the span's // extent, the value_type is deduced automatically. This is useful when passing // a dynamically sized container to a method expecting static spans, when the // container is known to have the correct size. // // Note: This will CHECK that N indeed matches size(container). // // Usage: auto static_span = base::make_span(...); template constexpr auto make_span(It it, size_t size) noexcept { using T = std::remove_reference_t>; return span(it, size); } template >> constexpr auto make_span(It it, End end) noexcept { using T = std::remove_reference_t>; return span(it, end); } template constexpr auto make_span(Container&& container) noexcept { using T = std::remove_pointer_t()))>; return span(std::data(container), std::size(container)); } } // namespace base // 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) \ ::base::internal::must_not_be_dynamic_extent() #endif // BASE_CONTAINERS_SPAN_H_