// 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 #include "base/containers/checked_iterators.h" #include "base/logging.h" #include "base/macros.h" #include "base/stl_util.h" namespace base { // [views.constants] constexpr size_t dynamic_extent = std::numeric_limits::max(); template class span; namespace internal { template struct ExtentImpl : std::integral_constant {}; template struct ExtentImpl : std::integral_constant {}; template struct ExtentImpl> : std::integral_constant {}; template struct ExtentImpl> : std::integral_constant {}; template using Extent = ExtentImpl>>; template struct IsSpanImpl : std::false_type {}; template struct IsSpanImpl> : std::true_type {}; template using IsSpan = IsSpanImpl>; template struct IsStdArrayImpl : std::false_type {}; template struct IsStdArrayImpl> : std::true_type {}; template using IsStdArray = IsStdArrayImpl>; template using IsCArray = std::is_array>; template using IsLegalDataConversion = std::is_convertible; 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::conditional_t::value && !IsStdArray::value && !IsCArray::value && ContainerHasConvertibleData::value && ContainerHasIntegralSize::value, std::true_type, std::false_type>; 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_; }; } // 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) // // Differences from [span.obs]: // - empty() is marked with WARN_UNUSED_RESULT instead of [[nodiscard]] // ([[nodiscard]] is a C++17 feature) // // 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 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; using const_iterator = CheckedContiguousConstIterator; using reverse_iterator = std::reverse_iterator; using const_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"); } constexpr span(T* data, size_t size) noexcept : ExtentStorage(size), data_(data) { CHECK(Extent == dynamic_extent || Extent == size); } // Artificially templatized to break ambiguity for span(ptr, 0). template constexpr span(T* begin, T* end) noexcept : span(begin, 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(base::data(array), N) {} template < size_t N, typename = internal:: EnableIfSpanCompatibleArray&, T, Extent>> constexpr span(std::array& array) noexcept : span(base::data(array), N) {} template &, T, Extent>> constexpr span(const std::array& array) noexcept : span(base::data(array), N) {} // Conversion from a container that has compatible base::data() and integral // base::size(). template < typename Container, typename = internal::EnableIfSpanCompatibleContainerAndSpanIsDynamic> constexpr span(Container& container) noexcept : span(base::data(container), base::size(container)) {} template < typename Container, typename = internal::EnableIfSpanCompatibleContainerAndSpanIsDynamic< const Container&, T, Extent>> constexpr span(const Container& container) noexcept : span(base::data(container), base::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(Extent == dynamic_extent || Count <= Extent, "Count must not exceed Extent"); CHECK(Extent != dynamic_extent || Count <= size()); return {data(), Count}; } template constexpr span last() const noexcept { static_assert(Extent == dynamic_extent || 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(Extent == dynamic_extent || Offset <= Extent, "Offset must not exceed Extent"); static_assert(Extent == dynamic_extent || 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); } constexpr bool empty() const noexcept WARN_UNUSED_RESULT { 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 const_iterator cbegin() const noexcept { return begin(); } constexpr const_iterator cend() const noexcept { return end(); } constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(end()); } constexpr reverse_iterator rend() const noexcept { return reverse_iterator(begin()); } constexpr const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(cend()); } constexpr const_reverse_iterator crend() const noexcept { return const_reverse_iterator(cbegin()); } 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 span make_span(T* data, size_t size) noexcept { return {data, size}; } template constexpr span make_span(T* begin, T* end) noexcept { return {begin, 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 function that allows 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(Container&& container) noexcept { using T = std::remove_pointer_t()))>; return span(base::data(container), base::size(container)); } } // namespace base // Note: std::tuple_size, std::tuple_element and std::get are specialized for // static spans, so that they can be used in C++17's structured bindings. While // we don't support C++17 yet, there is no harm in providing these // specializations already. namespace std { // [span.tuple], tuple interface #if defined(__clang__) // Due to https://llvm.org/PR39871 and https://llvm.org/PR41331 and their // respective fixes different versions of libc++ declare std::tuple_size and // std::tuple_element either as classes or structs. In order to be able to // specialize std::tuple_size and std::tuple_element for custom base types we // thus need to disable -Wmismatched-tags in order to support all build // configurations. Note that this is blessed by the standard in // https://timsong-cpp.github.io/cppwp/n4140/dcl.type.elab#3. #pragma clang diagnostic push #pragma clang diagnostic ignored "-Wmismatched-tags" #endif template struct tuple_size> : public integral_constant {}; template struct tuple_size>; // not defined template struct tuple_element> { static_assert( base::dynamic_extent != X, "std::tuple_element<> not supported for base::span"); static_assert(I < X, "Index out of bounds in std::tuple_element<> (base::span)"); using type = T; }; #if defined(__clang__) #pragma clang diagnostic pop // -Wmismatched-tags #endif template constexpr T& get(base::span s) noexcept { static_assert(base::dynamic_extent != X, "std::get<> not supported for base::span"); static_assert(I < X, "Index out of bounds in std::get<> (base::span)"); return s[I]; } } // namespace std #endif // BASE_CONTAINERS_SPAN_H_