| // Copyright 2020 The Pigweed Authors |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); you may not |
| // use this file except in compliance with the License. You may obtain a copy of |
| // the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT |
| // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the |
| // License for the specific language governing permissions and limitations under |
| // the License. |
| |
| // pw::span is a stand-in for C++20's std::span. |
| // |
| // A span is a non-owning array view class. It refers to an external array by |
| // storing a pointer and length. Unlike std::array, the size does not have to be |
| // a template parameter, so this class can be used to without stating its size. |
| // |
| // This file a modified version of base::span from Chromium: |
| // https://chromium.googlesource.com/chromium/src/+/ef71f9c29f0dc6eddae474879c4ca5232ca93a6c/base/containers/span.h |
| // |
| // In order to minimize changes from the original, this file does NOT fully |
| // adhere to Pigweed's style guide. |
| // |
| // A few changes were made to the Chromium version of span. These include: |
| // - Use std::data and std::size instead of base::* versions. |
| // - Rename base namespace to pw. |
| // - Rename internal namespace to span_internal. |
| // - Remove uses of checked_iterators.h and CHECK. |
| // - Replace make_span functions with C++17 class template deduction guides. |
| // - Use std::byte instead of uint8_t for compatibility with std::span. |
| // |
| // Eventually, when C++20 is widely supported, this class will be replaced with |
| // std::span. |
| #pragma once |
| |
| #include <algorithm> |
| #include <array> |
| #include <cstddef> |
| #include <iterator> |
| #include <limits> |
| #include <type_traits> |
| #include <utility> |
| |
| #include "pw_polyfill/language_features.h" |
| |
| // Pigweed: Disable the asserts from Chromium for now. |
| #define _PW_SPAN_ASSERT(arg) |
| |
| namespace pw { |
| |
| // [views.constants] |
| constexpr size_t dynamic_extent = std::numeric_limits<size_t>::max(); |
| |
| template <typename T, size_t Extent = dynamic_extent> |
| class span; |
| |
| namespace span_internal { |
| |
| template <typename T> |
| struct ExtentImpl : std::integral_constant<size_t, dynamic_extent> {}; |
| |
| template <typename T, size_t N> |
| struct ExtentImpl<T[N]> : std::integral_constant<size_t, N> {}; |
| |
| template <typename T, size_t N> |
| struct ExtentImpl<std::array<T, N>> : std::integral_constant<size_t, N> {}; |
| |
| template <typename T, size_t N> |
| struct ExtentImpl<pw::span<T, N>> : std::integral_constant<size_t, N> {}; |
| |
| template <typename T> |
| using Extent = ExtentImpl<std::remove_cv_t<std::remove_reference_t<T>>>; |
| |
| template <typename T> |
| struct IsSpanImpl : std::false_type {}; |
| |
| template <typename T, size_t Extent> |
| struct IsSpanImpl<span<T, Extent>> : std::true_type {}; |
| |
| template <typename T> |
| using IsSpan = IsSpanImpl<std::decay_t<T>>; |
| |
| template <typename T> |
| struct IsStdArrayImpl : std::false_type {}; |
| |
| template <typename T, size_t N> |
| struct IsStdArrayImpl<std::array<T, N>> : std::true_type {}; |
| |
| template <typename T> |
| using IsStdArray = IsStdArrayImpl<std::decay_t<T>>; |
| |
| template <typename T> |
| using IsCArray = std::is_array<std::remove_reference_t<T>>; |
| |
| template <typename From, typename To> |
| using IsLegalDataConversion = std::is_convertible<From (*)[], To (*)[]>; |
| |
| template <typename Container, typename T> |
| using ContainerHasConvertibleData = IsLegalDataConversion< |
| std::remove_pointer_t<decltype(std::data(std::declval<Container>()))>, |
| T>; |
| |
| template <typename Container> |
| using ContainerHasIntegralSize = |
| std::is_integral<decltype(std::size(std::declval<Container>()))>; |
| |
| template <typename From, size_t FromExtent, typename To, size_t ToExtent> |
| using EnableIfLegalSpanConversion = |
| std::enable_if_t<(ToExtent == dynamic_extent || ToExtent == FromExtent) && |
| IsLegalDataConversion<From, To>::value>; |
| |
| // SFINAE check if Array can be converted to a span<T>. |
| template <typename Array, typename T, size_t Extent> |
| using EnableIfSpanCompatibleArray = |
| std::enable_if_t<(Extent == dynamic_extent || |
| Extent == span_internal::Extent<Array>::value) && |
| ContainerHasConvertibleData<Array, T>::value>; |
| |
| // SFINAE check if Container can be converted to a span<T>. |
| template <typename Container, typename T> |
| using IsSpanCompatibleContainer = |
| std::conditional_t<!IsSpan<Container>::value && |
| !IsStdArray<Container>::value && |
| !IsCArray<Container>::value && |
| ContainerHasConvertibleData<Container, T>::value && |
| ContainerHasIntegralSize<Container>::value, |
| std::true_type, |
| std::false_type>; |
| |
| template <typename Container, typename T> |
| using EnableIfSpanCompatibleContainer = |
| std::enable_if_t<IsSpanCompatibleContainer<Container, T>::value>; |
| |
| template <typename Container, typename T, size_t Extent> |
| using EnableIfSpanCompatibleContainerAndSpanIsDynamic = |
| std::enable_if_t<IsSpanCompatibleContainer<Container, 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 <size_t Extent> |
| 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<dynamic_extent> { |
| constexpr explicit ExtentStorage(size_t size) noexcept : size_(size) {} |
| constexpr size_t size() const noexcept { return size_; } |
| |
| private: |
| size_t size_; |
| }; |
| |
| } // namespace span_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<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(pw::span<const uint8_t> data); |
| // std::vector<uint8_t> data_buffer = GenerateData(); |
| // std::string r = HexEncode(data_buffer); |
| // |
| // Mutable: |
| // // ssize_t SafeSNPrintf(pw::span<char>, 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<int*> => pw::span<int* const> |
| // std::vector<const int*> => pw::span<const int*> |
| // const std::vector<const int*> => pw::span<const int* const> |
| // |
| // 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.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. |
| |
| // [span], class template span |
| template <typename T, size_t Extent> |
| class span : public span_internal::ExtentStorage<Extent> { |
| private: |
| using ExtentStorage = span_internal::ExtentStorage<Extent>; |
| |
| public: |
| using element_type = T; |
| using value_type = std::remove_cv_t<T>; |
| using size_type = size_t; |
| using difference_type = ptrdiff_t; |
| using pointer = T*; |
| using reference = T&; |
| using iterator = T*; |
| using const_iterator = const T*; |
| using reverse_iterator = std::reverse_iterator<iterator>; |
| using const_reverse_iterator = std::reverse_iterator<const_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) { |
| _PW_SPAN_ASSERT(Extent == dynamic_extent || Extent == size); |
| } |
| |
| // Artificially templatized to break ambiguity for span(ptr, 0). |
| template <typename = void> |
| constexpr span(T* begin, T* end) noexcept : span(begin, end - begin) { |
| // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. |
| _PW_SPAN_ASSERT(begin <= end); |
| } |
| |
| template <size_t N, |
| typename = |
| span_internal::EnableIfSpanCompatibleArray<T (&)[N], T, Extent>> |
| constexpr span(T (&array)[N]) noexcept : span(std::data(array), N) {} |
| |
| template < |
| size_t N, |
| typename = span_internal:: |
| EnableIfSpanCompatibleArray<std::array<value_type, N>&, T, Extent>> |
| constexpr span(std::array<value_type, N>& array) noexcept |
| : span(std::data(array), N) {} |
| |
| template <size_t N, |
| typename = span_internal::EnableIfSpanCompatibleArray< |
| const std::array<value_type, N>&, |
| T, |
| Extent>> |
| constexpr span(const std::array<value_type, N>& array) noexcept |
| : span(std::data(array), N) {} |
| |
| // Conversion from a container that has compatible std::data() and integral |
| // std::size(). |
| template <typename Container, |
| typename = span_internal:: |
| EnableIfSpanCompatibleContainerAndSpanIsDynamic<Container&, |
| T, |
| Extent>> |
| constexpr span(Container& container) noexcept |
| : span(std::data(container), std::size(container)) {} |
| |
| template < |
| typename Container, |
| typename = span_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<T> to be seamlessly used as a span<const T>, 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 = |
| span_internal::EnableIfLegalSpanConversion<U, OtherExtent, T, Extent>> |
| constexpr span(const span<U, OtherExtent>& other) |
| : span(other.data(), other.size()) {} |
| |
| PW_CONSTEXPR_FUNCTION span& operator=(const span& other) noexcept = default; |
| ~span() noexcept = default; |
| |
| // [span.sub], span subviews |
| template <size_t Count> |
| constexpr span<T, Count> first() const noexcept { |
| static_assert(Extent == dynamic_extent || Count <= Extent, |
| "Count must not exceed Extent"); |
| _PW_SPAN_ASSERT(Extent != dynamic_extent || Count <= size()); |
| return {data(), Count}; |
| } |
| |
| template <size_t Count> |
| constexpr span<T, Count> last() const noexcept { |
| static_assert(Extent == dynamic_extent || Count <= Extent, |
| "Count must not exceed Extent"); |
| _PW_SPAN_ASSERT(Extent != dynamic_extent || Count <= size()); |
| return {data() + (size() - Count), Count}; |
| } |
| |
| template <size_t Offset, size_t Count = dynamic_extent> |
| constexpr span<T, |
| (Count != dynamic_extent |
| ? Count |
| : (Extent != dynamic_extent ? Extent - Offset |
| : dynamic_extent))> |
| 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"); |
| _PW_SPAN_ASSERT(Extent != dynamic_extent || Offset <= size()); |
| _PW_SPAN_ASSERT(Extent != dynamic_extent || Count == dynamic_extent || |
| Count <= size() - Offset); |
| return {data() + Offset, Count != dynamic_extent ? Count : size() - Offset}; |
| } |
| |
| constexpr span<T, dynamic_extent> first(size_t count) const noexcept { |
| // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. |
| _PW_SPAN_ASSERT(count <= size()); |
| return {data(), count}; |
| } |
| |
| constexpr span<T, dynamic_extent> last(size_t count) const noexcept { |
| // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. |
| _PW_SPAN_ASSERT(count <= size()); |
| return {data() + (size() - count), count}; |
| } |
| |
| constexpr span<T, dynamic_extent> subspan( |
| size_t offset, size_t count = dynamic_extent) const noexcept { |
| // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. |
| _PW_SPAN_ASSERT(offset <= size()); |
| _PW_SPAN_ASSERT(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. |
| _PW_SPAN_ASSERT(idx < size()); |
| return *(data() + idx); |
| } |
| |
| constexpr T& front() const noexcept { |
| static_assert(Extent == dynamic_extent || Extent > 0, |
| "Extent must not be 0"); |
| _PW_SPAN_ASSERT(Extent != dynamic_extent || !empty()); |
| return *data(); |
| } |
| |
| constexpr T& back() const noexcept { |
| static_assert(Extent == dynamic_extent || Extent > 0, |
| "Extent must not be 0"); |
| _PW_SPAN_ASSERT(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 data_; } |
| constexpr iterator end() const noexcept { return 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<T, Extent>::extent can not be declared inline prior to C++17, hence this |
| // definition is required. |
| template <class T, size_t Extent> |
| constexpr size_t span<T, Extent>::extent; |
| |
| // [span.objectrep], views of object representation |
| template <typename T, size_t X> |
| span<const std::byte, (X == dynamic_extent ? dynamic_extent : sizeof(T) * X)> |
| as_bytes(span<T, X> s) noexcept { |
| return {reinterpret_cast<const std::byte*>(s.data()), s.size_bytes()}; |
| } |
| |
| template <typename T, |
| size_t X, |
| typename = std::enable_if_t<!std::is_const<T>::value>> |
| span<std::byte, (X == dynamic_extent ? dynamic_extent : sizeof(T) * X)> |
| as_writable_bytes(span<T, X> s) noexcept { |
| return {reinterpret_cast<std::byte*>(s.data()), s.size_bytes()}; |
| } |
| |
| // Type-deducing helpers for constructing a span. |
| // Pigweed: Instead of a make_span function, provide the deduction guides |
| // specified in the C++20 standard. |
| #ifdef __cpp_deduction_guides |
| |
| template <class T, std::size_t N> |
| span(T (&)[N]) -> span<T, N>; |
| |
| template <class T, std::size_t N> |
| span(std::array<T, N>&) -> span<T, N>; |
| |
| template <class T, std::size_t N> |
| span(const std::array<T, N>&) -> span<const T, N>; |
| |
| template <class Container> |
| span(Container&) -> span<typename Container::value_type>; |
| |
| template <class Container> |
| span(const Container&) -> span<const typename Container::value_type>; |
| |
| #endif // __cpp_deduction_guides |
| |
| } // namespace pw |
| |
| // 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. |
| 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 pw 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 <typename T, size_t X> |
| struct tuple_size<pw::span<T, X>> : public integral_constant<size_t, X> {}; |
| |
| template <typename T> |
| struct tuple_size<pw::span<T, pw::dynamic_extent>>; // not defined |
| |
| template <size_t I, typename T, size_t X> |
| struct tuple_element<I, pw::span<T, X>> { |
| static_assert( |
| pw::dynamic_extent != X, |
| "std::tuple_element<> not supported for pw::span<T, dynamic_extent>"); |
| static_assert(I < X, |
| "Index out of bounds in std::tuple_element<> (pw::span)"); |
| using type = T; |
| }; |
| #if defined(__clang__) |
| #pragma clang diagnostic pop // -Wmismatched-tags |
| #endif |
| |
| template <size_t I, typename T, size_t X> |
| constexpr T& get(pw::span<T, X> s) noexcept { |
| static_assert(pw::dynamic_extent != X, |
| "std::get<> not supported for pw::span<T, dynamic_extent>"); |
| static_assert(I < X, "Index out of bounds in std::get<> (pw::span)"); |
| return s[I]; |
| } |
| |
| } // namespace std |
| |
| #undef _PW_SPAN_ASSERT |