1 // Copyright 2020 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 15 // This span implementation is a stand-in for C++20's std::span. Do NOT include 16 // this header directly; instead, include it as "pw_span/span.h". 17 // 18 // A span is a non-owning array view class. It refers to an external array by 19 // storing a pointer and length. Unlike std::array, the size does not have to be 20 // a template parameter, so this class can be used to without stating its size. 21 // 22 // This file a modified version of base::span from Chromium: 23 // https://chromium.googlesource.com/chromium/src/+/d93ae920e4309682deb9352a4637cfc2941c1d1f/base/containers/span.h 24 // 25 // In order to minimize changes from the original, this file does NOT fully 26 // adhere to Pigweed's style guide. 27 // 28 // A few changes were made to the Chromium version of span. These include: 29 // - Use std::data and std::size instead of base::* versions. 30 // - Rename base namespace to pw. 31 // - Rename internal namespace to pw_span_internal. 32 // - Remove uses of checked_iterators.h and CHECK. 33 // - Replace make_span functions with C++17 class template deduction guides. 34 // - Use std::byte instead of uint8_t for compatibility with std::span. 35 #pragma once 36 37 #include <algorithm> 38 #include <array> 39 #include <cstddef> 40 #include <iterator> 41 #include <limits> 42 #include <type_traits> 43 #include <utility> 44 45 #include "pw_span/internal/config.h" 46 47 #if PW_SPAN_ENABLE_ASSERTS 48 49 #include "pw_assert/assert.h" 50 51 #define _PW_SPAN_ASSERT(arg) PW_ASSERT(arg) 52 53 #else 54 #define _PW_SPAN_ASSERT(arg) 55 #endif // PW_SPAN_ENABLE_ASSERTS 56 57 namespace pw { 58 59 // [views.constants] 60 constexpr size_t dynamic_extent = std::numeric_limits<size_t>::max(); 61 62 template <typename T, size_t Extent = dynamic_extent> 63 class span; 64 65 namespace pw_span_internal { 66 67 template <typename T> 68 struct ExtentImpl : std::integral_constant<size_t, dynamic_extent> {}; 69 70 template <typename T, size_t N> 71 struct ExtentImpl<T[N]> : std::integral_constant<size_t, N> {}; 72 73 template <typename T, size_t N> 74 struct ExtentImpl<std::array<T, N>> : std::integral_constant<size_t, N> {}; 75 76 template <typename T, size_t N> 77 struct ExtentImpl<span<T, N>> : std::integral_constant<size_t, N> {}; 78 79 template <typename T> 80 using Extent = ExtentImpl<std::remove_cv_t<std::remove_reference_t<T>>>; 81 82 template <typename T> 83 struct IsSpanImpl : std::false_type {}; 84 85 template <typename T, size_t Extent> 86 struct IsSpanImpl<span<T, Extent>> : std::true_type {}; 87 88 template <typename T> 89 using IsSpan = IsSpanImpl<std::decay_t<T>>; 90 91 template <typename T> 92 struct IsStdArrayImpl : std::false_type {}; 93 94 template <typename T, size_t N> 95 struct IsStdArrayImpl<std::array<T, N>> : std::true_type {}; 96 97 template <typename T> 98 using IsStdArray = IsStdArrayImpl<std::decay_t<T>>; 99 100 template <typename T> 101 using IsCArray = std::is_array<std::remove_reference_t<T>>; 102 103 template <typename From, typename To> 104 using IsLegalDataConversion = std::is_convertible<From (*)[], To (*)[]>; 105 106 template <typename Container, typename T> 107 using ContainerHasConvertibleData = IsLegalDataConversion< 108 std::remove_pointer_t<decltype(std::data(std::declval<Container>()))>, 109 T>; 110 111 template <typename Container> 112 using ContainerHasIntegralSize = 113 std::is_integral<decltype(std::size(std::declval<Container>()))>; 114 115 template <typename From, size_t FromExtent, typename To, size_t ToExtent> 116 using EnableIfLegalSpanConversion = 117 std::enable_if_t<(ToExtent == dynamic_extent || ToExtent == FromExtent) && 118 IsLegalDataConversion<From, To>::value>; 119 120 // SFINAE check if Array can be converted to a span<T>. 121 template <typename Array, typename T, size_t Extent> 122 using EnableIfSpanCompatibleArray = 123 std::enable_if_t<(Extent == dynamic_extent || 124 Extent == pw_span_internal::Extent<Array>::value) && 125 ContainerHasConvertibleData<Array, T>::value>; 126 127 // SFINAE check if Container can be converted to a span<T>. 128 template <typename Container, typename T> 129 using IsSpanCompatibleContainer = 130 std::conditional_t<!IsSpan<Container>::value && 131 !IsStdArray<Container>::value && 132 !IsCArray<Container>::value && 133 ContainerHasConvertibleData<Container, T>::value && 134 ContainerHasIntegralSize<Container>::value, 135 std::true_type, 136 std::false_type>; 137 138 template <typename Container, typename T> 139 using EnableIfSpanCompatibleContainer = 140 std::enable_if_t<IsSpanCompatibleContainer<Container, T>::value>; 141 142 template <typename Container, typename T, size_t Extent> 143 using EnableIfSpanCompatibleContainerAndSpanIsDynamic = 144 std::enable_if_t<IsSpanCompatibleContainer<Container, T>::value && 145 Extent == dynamic_extent>; 146 147 // A helper template for storing the size of a span. Spans with static extents 148 // don't require additional storage, since the extent itself is specified in the 149 // template parameter. 150 template <size_t Extent> 151 class ExtentStorage { 152 public: 153 constexpr explicit ExtentStorage(size_t /* size */) noexcept {} 154 constexpr size_t size() const noexcept { return Extent; } 155 }; 156 157 // Specialization of ExtentStorage for dynamic extents, which do require 158 // explicit storage for the size. 159 template <> 160 struct ExtentStorage<dynamic_extent> { 161 constexpr explicit ExtentStorage(size_t size) noexcept : size_(size) {} 162 constexpr size_t size() const noexcept { return size_; } 163 164 private: 165 size_t size_; 166 }; 167 168 } // namespace pw_span_internal 169 170 // A span is a value type that represents an array of elements of type T. Since 171 // it only consists of a pointer to memory with an associated size, it is very 172 // light-weight. It is cheap to construct, copy, move and use spans, so that 173 // users are encouraged to use it as a pass-by-value parameter. A span does not 174 // own the underlying memory, so care must be taken to ensure that a span does 175 // not outlive the backing store. 176 // 177 // span is somewhat analogous to StringPiece, but with arbitrary element types, 178 // allowing mutation if T is non-const. 179 // 180 // span is implicitly convertible from C++ arrays, as well as most [1] 181 // container-like types that provide a data() and size() method (such as 182 // std::vector<T>). A mutable span<T> can also be implicitly converted to an 183 // immutable span<const T>. 184 // 185 // Consider using a span for functions that take a data pointer and size 186 // parameter: it allows the function to still act on an array-like type, while 187 // allowing the caller code to be a bit more concise. 188 // 189 // For read-only data access pass a span<const T>: the caller can supply either 190 // a span<const T> or a span<T>, while the callee will have a read-only view. 191 // For read-write access a mutable span<T> is required. 192 // 193 // Without span: 194 // Read-Only: 195 // // std::string HexEncode(const uint8_t* data, size_t size); 196 // std::vector<uint8_t> data_buffer = GenerateData(); 197 // std::string r = HexEncode(data_buffer.data(), data_buffer.size()); 198 // 199 // Mutable: 200 // // ssize_t SafeSNPrintf(char* buf, size_t N, const char* fmt, Args...); 201 // char str_buffer[100]; 202 // SafeSNPrintf(str_buffer, sizeof(str_buffer), "Pi ~= %lf", 3.14); 203 // 204 // With span: 205 // Read-Only: 206 // // std::string HexEncode(std::span<const uint8_t> data); 207 // std::vector<uint8_t> data_buffer = GenerateData(); 208 // std::string r = HexEncode(data_buffer); 209 // 210 // Mutable: 211 // // ssize_t SafeSNPrintf(std::span<char>, const char* fmt, Args...); 212 // char str_buffer[100]; 213 // SafeSNPrintf(str_buffer, "Pi ~= %lf", 3.14); 214 // 215 // Spans with "const" and pointers 216 // ------------------------------- 217 // 218 // Const and pointers can get confusing. Here are vectors of pointers and their 219 // corresponding spans: 220 // 221 // const std::vector<int*> => std::span<int* const> 222 // std::vector<const int*> => std::span<const int*> 223 // const std::vector<const int*> => std::span<const int* const> 224 // 225 // Differences from the C++20 draft 226 // -------------------------------- 227 // 228 // http://eel.is/c++draft/views contains the latest C++20 draft of std::span. 229 // Chromium tries to follow the draft as close as possible. Differences between 230 // the draft and the implementation are documented in subsections below. 231 // 232 // Differences from [span.cons]: 233 // - Constructing a static span (i.e. Extent != dynamic_extent) from a dynamic 234 // sized container (e.g. std::vector) requires an explicit conversion (in the 235 // C++20 draft this is simply UB) 236 // 237 // Furthermore, all constructors and methods are marked noexcept due to the lack 238 // of exceptions in Chromium. 239 240 // [span], class template span 241 template <typename T, size_t Extent> 242 class span : public pw_span_internal::ExtentStorage<Extent> { 243 private: 244 using ExtentStorage = pw_span_internal::ExtentStorage<Extent>; 245 246 public: 247 using element_type = T; 248 using value_type = std::remove_cv_t<T>; 249 using size_type = size_t; 250 using difference_type = ptrdiff_t; 251 using pointer = T*; 252 using reference = T&; 253 using iterator = T*; 254 using reverse_iterator = std::reverse_iterator<iterator>; 255 static constexpr size_t extent = Extent; 256 257 // [span.cons], span constructors, copy, assignment, and destructor 258 constexpr span() noexcept : ExtentStorage(0), data_(nullptr) { 259 static_assert(Extent == dynamic_extent || Extent == 0, "Invalid Extent"); 260 } 261 262 constexpr span(T* data, size_t size) noexcept 263 : ExtentStorage(size), data_(data) { 264 _PW_SPAN_ASSERT(Extent == dynamic_extent || Extent == size); 265 } 266 267 // Prevent construction from nullptr, which is disallowed by C++20's std::span 268 constexpr span(std::nullptr_t data, size_t size) = delete; 269 270 // Artificially templatized to break ambiguity for span(ptr, 0). 271 template <typename = void> 272 constexpr span(T* begin, T* end) noexcept : span(begin, end - begin) { 273 // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. 274 _PW_SPAN_ASSERT(begin <= end); 275 } 276 277 template < 278 size_t N, 279 typename = 280 pw_span_internal::EnableIfSpanCompatibleArray<T (&)[N], T, Extent>> 281 constexpr span(T (&array)[N]) noexcept : span(std::data(array), N) {} 282 283 template <typename U, 284 size_t N, 285 typename = pw_span_internal:: 286 EnableIfSpanCompatibleArray<std::array<U, N>&, T, Extent>> 287 constexpr span(std::array<U, N>& array) noexcept 288 : span(std::data(array), N) {} 289 290 template <typename U, 291 size_t N, 292 typename = pw_span_internal:: 293 EnableIfSpanCompatibleArray<const std::array<U, N>&, T, Extent>> 294 constexpr span(const std::array<U, N>& array) noexcept 295 : span(std::data(array), N) {} 296 297 // Conversion from a container that has compatible std::data() and integral 298 // std::size(). 299 template <typename Container, 300 typename = pw_span_internal:: 301 EnableIfSpanCompatibleContainerAndSpanIsDynamic<Container&, 302 T, 303 Extent>> 304 constexpr span(Container& container) noexcept 305 : span(std::data(container), std::size(container)) {} 306 307 template < 308 typename Container, 309 typename = pw_span_internal:: 310 EnableIfSpanCompatibleContainerAndSpanIsDynamic<const Container&, 311 T, 312 Extent>> 313 constexpr span(const Container& container) noexcept 314 : span(std::data(container), std::size(container)) {} 315 316 constexpr span(const span& other) noexcept = default; 317 318 // Conversions from spans of compatible types and extents: this allows a 319 // span<T> to be seamlessly used as a span<const T>, but not the other way 320 // around. If extent is not dynamic, OtherExtent has to be equal to Extent. 321 template <typename U, 322 size_t OtherExtent, 323 typename = pw_span_internal:: 324 EnableIfLegalSpanConversion<U, OtherExtent, T, Extent>> 325 constexpr span(const span<U, OtherExtent>& other) 326 : span(other.data(), other.size()) {} 327 328 constexpr span& operator=(const span& other) noexcept = default; 329 ~span() noexcept = default; 330 331 // [span.sub], span subviews 332 template <size_t Count> 333 constexpr span<T, Count> first() const noexcept { 334 static_assert(Count <= Extent, "Count must not exceed Extent"); 335 _PW_SPAN_ASSERT(Extent != dynamic_extent || Count <= size()); 336 return {data(), Count}; 337 } 338 339 template <size_t Count> 340 constexpr span<T, Count> last() const noexcept { 341 static_assert(Count <= Extent, "Count must not exceed Extent"); 342 _PW_SPAN_ASSERT(Extent != dynamic_extent || Count <= size()); 343 return {data() + (size() - Count), Count}; 344 } 345 346 template <size_t Offset, size_t Count = dynamic_extent> 347 constexpr span<T, 348 (Count != dynamic_extent 349 ? Count 350 : (Extent != dynamic_extent ? Extent - Offset 351 : dynamic_extent))> 352 subspan() const noexcept { 353 static_assert(Offset <= Extent, "Offset must not exceed Extent"); 354 static_assert(Count == dynamic_extent || Count <= Extent - Offset, 355 "Count must not exceed Extent - Offset"); 356 _PW_SPAN_ASSERT(Extent != dynamic_extent || Offset <= size()); 357 _PW_SPAN_ASSERT(Extent != dynamic_extent || Count == dynamic_extent || 358 Count <= size() - Offset); 359 return {data() + Offset, Count != dynamic_extent ? Count : size() - Offset}; 360 } 361 362 constexpr span<T, dynamic_extent> first(size_t count) const noexcept { 363 // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. 364 _PW_SPAN_ASSERT(count <= size()); 365 return {data(), count}; 366 } 367 368 constexpr span<T, dynamic_extent> last(size_t count) const noexcept { 369 // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. 370 _PW_SPAN_ASSERT(count <= size()); 371 return {data() + (size() - count), count}; 372 } 373 374 constexpr span<T, dynamic_extent> subspan( 375 size_t offset, size_t count = dynamic_extent) const noexcept { 376 // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. 377 _PW_SPAN_ASSERT(offset <= size()); 378 _PW_SPAN_ASSERT(count == dynamic_extent || count <= size() - offset); 379 return {data() + offset, count != dynamic_extent ? count : size() - offset}; 380 } 381 382 // [span.obs], span observers 383 constexpr size_t size() const noexcept { return ExtentStorage::size(); } 384 constexpr size_t size_bytes() const noexcept { return size() * sizeof(T); } 385 [[nodiscard]] constexpr bool empty() const noexcept { return size() == 0; } 386 387 // [span.elem], span element access 388 constexpr T& operator[](size_t idx) const noexcept { 389 // Note: CHECK_LT is not constexpr, hence regular CHECK must be used. 390 _PW_SPAN_ASSERT(idx < size()); 391 return *(data() + idx); 392 } 393 394 constexpr T& front() const noexcept { 395 static_assert(Extent == dynamic_extent || Extent > 0, 396 "Extent must not be 0"); 397 _PW_SPAN_ASSERT(Extent != dynamic_extent || !empty()); 398 return *data(); 399 } 400 401 constexpr T& back() const noexcept { 402 static_assert(Extent == dynamic_extent || Extent > 0, 403 "Extent must not be 0"); 404 _PW_SPAN_ASSERT(Extent != dynamic_extent || !empty()); 405 return *(data() + size() - 1); 406 } 407 408 constexpr T* data() const noexcept { return data_; } 409 410 // [span.iter], span iterator support 411 constexpr iterator begin() const noexcept { return data_; } 412 constexpr iterator end() const noexcept { return data_ + size(); } 413 414 constexpr reverse_iterator rbegin() const noexcept { 415 return reverse_iterator(end()); 416 } 417 constexpr reverse_iterator rend() const noexcept { 418 return reverse_iterator(begin()); 419 } 420 421 private: 422 T* data_; 423 }; 424 425 // span<T, Extent>::extent can not be declared inline prior to C++17, hence this 426 // definition is required. 427 // template <class T, size_t Extent> 428 // constexpr size_t span<T, Extent>::extent; 429 430 // [span.objectrep], views of object representation 431 template <typename T, size_t X> 432 span<const std::byte, (X == dynamic_extent ? dynamic_extent : sizeof(T) * X)> 433 as_bytes(span<T, X> s) noexcept { 434 return {reinterpret_cast<const std::byte*>(s.data()), s.size_bytes()}; 435 } 436 437 template <typename T, 438 size_t X, 439 typename = std::enable_if_t<!std::is_const<T>::value>> 440 span<std::byte, (X == dynamic_extent ? dynamic_extent : sizeof(T) * X)> 441 as_writable_bytes(span<T, X> s) noexcept { 442 return {reinterpret_cast<std::byte*>(s.data()), s.size_bytes()}; 443 } 444 445 // Type-deducing helpers for constructing a span. 446 // Pigweed: Instead of a make_span function, provide the deduction guides 447 // specified in the C++20 standard. 448 #ifdef __cpp_deduction_guides 449 450 template <class T, std::size_t N> 451 span(T (&)[N]) -> span<T, N>; 452 453 template <class T, std::size_t N> 454 span(std::array<T, N>&) -> span<T, N>; 455 456 template <class T, std::size_t N> 457 span(const std::array<T, N>&) -> span<const T, N>; 458 459 namespace pw_span_internal { 460 461 // Containers can be mutable or const and have mutable or const members. Check 462 // the type of the accessed elements to determine which type of span should be 463 // created (e.g. span<char> or span<const char>). 464 template <typename T> 465 using ValueType = std::remove_reference_t<decltype(std::declval<T>()[0])>; 466 467 } // namespace pw_span_internal 468 469 // This diverges a little from the standard, which uses std::ranges. 470 template <class Container> 471 span(Container&) -> span<pw_span_internal::ValueType<Container>>; 472 473 template <class Container> 474 span(const Container&) -> span<pw_span_internal::ValueType<const Container>>; 475 476 #endif // __cpp_deduction_guides 477 478 } // namespace pw 479 480 #undef _PW_SPAN_ASSERT 481