span.h (21829B)
1 // Copyright 2017 The Chromium Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef BASE_CONTAINERS_SPAN_H_ 6 #define BASE_CONTAINERS_SPAN_H_ 7 8 #include <stddef.h> 9 #include <stdint.h> 10 11 #include <array> 12 #include <iterator> 13 #include <limits> 14 #include <type_traits> 15 #include <utility> 16 17 #include "base/check.h" 18 #include "base/compiler_specific.h" 19 #include "base/containers/checked_iterators.h" 20 #include "base/containers/contiguous_iterator.h" 21 #include "base/cxx20_to_address.h" 22 #include "base/numerics/safe_conversions.h" 23 #include "base/template_util.h" 24 25 namespace base { 26 27 // [views.constants] 28 constexpr size_t dynamic_extent = std::numeric_limits<size_t>::max(); 29 30 template <typename T, 31 size_t Extent = dynamic_extent, 32 typename InternalPtrType = T*> 33 class span; 34 35 namespace internal { 36 37 template <size_t I> 38 using size_constant = std::integral_constant<size_t, I>; 39 40 template <typename T> 41 struct ExtentImpl : size_constant<dynamic_extent> {}; 42 43 template <typename T, size_t N> 44 struct ExtentImpl<T[N]> : size_constant<N> {}; 45 46 template <typename T, size_t N> 47 struct ExtentImpl<std::array<T, N>> : size_constant<N> {}; 48 49 template <typename T, size_t N> 50 struct ExtentImpl<base::span<T, N>> : size_constant<N> {}; 51 52 template <typename T> 53 using Extent = ExtentImpl<remove_cvref_t<T>>; 54 55 template <typename T> 56 struct IsSpanImpl : std::false_type {}; 57 58 template <typename T, size_t Extent> 59 struct IsSpanImpl<span<T, Extent>> : std::true_type {}; 60 61 template <typename T> 62 using IsNotSpan = std::negation<IsSpanImpl<std::decay_t<T>>>; 63 64 template <typename T> 65 struct IsStdArrayImpl : std::false_type {}; 66 67 template <typename T, size_t N> 68 struct IsStdArrayImpl<std::array<T, N>> : std::true_type {}; 69 70 template <typename T> 71 using IsNotStdArray = std::negation<IsStdArrayImpl<std::decay_t<T>>>; 72 73 template <typename T> 74 using IsNotCArray = std::negation<std::is_array<std::remove_reference_t<T>>>; 75 76 template <typename From, typename To> 77 using IsLegalDataConversion = std::is_convertible<From (*)[], To (*)[]>; 78 79 template <typename Iter, typename T> 80 using IteratorHasConvertibleReferenceType = 81 IsLegalDataConversion<std::remove_reference_t<iter_reference_t<Iter>>, T>; 82 83 template <typename Iter, typename T> 84 using EnableIfCompatibleContiguousIterator = std::enable_if_t< 85 std::conjunction_v<IsContiguousIterator<Iter>, 86 IteratorHasConvertibleReferenceType<Iter, T>>>; 87 88 template <typename Container, typename T> 89 using ContainerHasConvertibleData = IsLegalDataConversion< 90 std::remove_pointer_t<decltype(std::data(std::declval<Container>()))>, 91 T>; 92 93 template <typename Container> 94 using ContainerHasIntegralSize = 95 std::is_integral<decltype(std::size(std::declval<Container>()))>; 96 97 template <typename From, size_t FromExtent, typename To, size_t ToExtent> 98 using EnableIfLegalSpanConversion = 99 std::enable_if_t<(ToExtent == dynamic_extent || ToExtent == FromExtent) && 100 IsLegalDataConversion<From, To>::value>; 101 102 // SFINAE check if Array can be converted to a span<T>. 103 template <typename Array, typename T, size_t Extent> 104 using EnableIfSpanCompatibleArray = 105 std::enable_if_t<(Extent == dynamic_extent || 106 Extent == internal::Extent<Array>::value) && 107 ContainerHasConvertibleData<Array, T>::value>; 108 109 // SFINAE check if Container can be converted to a span<T>. 110 template <typename Container, typename T> 111 using IsSpanCompatibleContainer = 112 std::conjunction<IsNotSpan<Container>, 113 IsNotStdArray<Container>, 114 IsNotCArray<Container>, 115 ContainerHasConvertibleData<Container, T>, 116 ContainerHasIntegralSize<Container>>; 117 118 template <typename Container, typename T> 119 using EnableIfSpanCompatibleContainer = 120 std::enable_if_t<IsSpanCompatibleContainer<Container, T>::value>; 121 122 template <typename Container, typename T, size_t Extent> 123 using EnableIfSpanCompatibleContainerAndSpanIsDynamic = 124 std::enable_if_t<IsSpanCompatibleContainer<Container, T>::value && 125 Extent == dynamic_extent>; 126 127 // A helper template for storing the size of a span. Spans with static extents 128 // don't require additional storage, since the extent itself is specified in the 129 // template parameter. 130 template <size_t Extent> 131 class ExtentStorage { 132 public: 133 constexpr explicit ExtentStorage(size_t size) noexcept {} 134 constexpr size_t size() const noexcept { return Extent; } 135 }; 136 137 // Specialization of ExtentStorage for dynamic extents, which do require 138 // explicit storage for the size. 139 template <> 140 struct ExtentStorage<dynamic_extent> { 141 constexpr explicit ExtentStorage(size_t size) noexcept : size_(size) {} 142 constexpr size_t size() const noexcept { return size_; } 143 144 private: 145 size_t size_; 146 }; 147 148 // must_not_be_dynamic_extent prevents |dynamic_extent| from being returned in a 149 // constexpr context. 150 template <size_t kExtent> 151 constexpr size_t must_not_be_dynamic_extent() { 152 static_assert( 153 kExtent != dynamic_extent, 154 "EXTENT should only be used for containers with a static extent."); 155 return kExtent; 156 } 157 158 } // namespace internal 159 160 // A span is a value type that represents an array of elements of type T. Since 161 // it only consists of a pointer to memory with an associated size, it is very 162 // light-weight. It is cheap to construct, copy, move and use spans, so that 163 // users are encouraged to use it as a pass-by-value parameter. A span does not 164 // own the underlying memory, so care must be taken to ensure that a span does 165 // not outlive the backing store. 166 // 167 // span is somewhat analogous to std::string_view, but with arbitrary element 168 // types, allowing mutation if T is non-const. 169 // 170 // span is implicitly convertible from C++ arrays, as well as most [1] 171 // container-like types that provide a data() and size() method (such as 172 // std::vector<T>). A mutable span<T> can also be implicitly converted to an 173 // immutable span<const T>. 174 // 175 // Consider using a span for functions that take a data pointer and size 176 // parameter: it allows the function to still act on an array-like type, while 177 // allowing the caller code to be a bit more concise. 178 // 179 // For read-only data access pass a span<const T>: the caller can supply either 180 // a span<const T> or a span<T>, while the callee will have a read-only view. 181 // For read-write access a mutable span<T> is required. 182 // 183 // Without span: 184 // Read-Only: 185 // // std::string HexEncode(const uint8_t* data, size_t size); 186 // std::vector<uint8_t> data_buffer = GenerateData(); 187 // std::string r = HexEncode(data_buffer.data(), data_buffer.size()); 188 // 189 // Mutable: 190 // // ssize_t SafeSNPrintf(char* buf, size_t N, const char* fmt, Args...); 191 // char str_buffer[100]; 192 // SafeSNPrintf(str_buffer, sizeof(str_buffer), "Pi ~= %lf", 3.14); 193 // 194 // With span: 195 // Read-Only: 196 // // std::string HexEncode(base::span<const uint8_t> data); 197 // std::vector<uint8_t> data_buffer = GenerateData(); 198 // std::string r = HexEncode(data_buffer); 199 // 200 // Mutable: 201 // // ssize_t SafeSNPrintf(base::span<char>, const char* fmt, Args...); 202 // char str_buffer[100]; 203 // SafeSNPrintf(str_buffer, "Pi ~= %lf", 3.14); 204 // 205 // Spans with "const" and pointers 206 // ------------------------------- 207 // 208 // Const and pointers can get confusing. Here are vectors of pointers and their 209 // corresponding spans: 210 // 211 // const std::vector<int*> => base::span<int* const> 212 // std::vector<const int*> => base::span<const int*> 213 // const std::vector<const int*> => base::span<const int* const> 214 // 215 // Differences from the C++20 draft 216 // -------------------------------- 217 // 218 // http://eel.is/c++draft/views contains the latest C++20 draft of std::span. 219 // Chromium tries to follow the draft as close as possible. Differences between 220 // the draft and the implementation are documented in subsections below. 221 // 222 // Differences from [span.objectrep]: 223 // - as_bytes() and as_writable_bytes() return spans of uint8_t instead of 224 // std::byte (std::byte is a C++17 feature) 225 // 226 // Differences from [span.cons]: 227 // - Constructing a static span (i.e. Extent != dynamic_extent) from a dynamic 228 // sized container (e.g. std::vector) requires an explicit conversion (in the 229 // C++20 draft this is simply UB) 230 // 231 // Furthermore, all constructors and methods are marked noexcept due to the lack 232 // of exceptions in Chromium. 233 // 234 // Due to the lack of class template argument deduction guides in C++14 235 // appropriate make_span() utility functions are provided. 236 237 // [span], class template span 238 template <typename T, size_t Extent, typename InternalPtrType> 239 class GSL_POINTER span : public internal::ExtentStorage<Extent> { 240 private: 241 using ExtentStorage = internal::ExtentStorage<Extent>; 242 243 public: 244 using element_type = T; 245 using value_type = std::remove_cv_t<T>; 246 using size_type = size_t; 247 using difference_type = ptrdiff_t; 248 using pointer = T*; 249 using const_pointer = const T*; 250 using reference = T&; 251 using const_reference = const T&; 252 using iterator = CheckedContiguousIterator<T>; 253 using reverse_iterator = std::reverse_iterator<iterator>; 254 static constexpr size_t extent = Extent; 255 256 // [span.cons], span constructors, copy, assignment, and destructor 257 constexpr span() noexcept : ExtentStorage(0), data_(nullptr) { 258 static_assert(Extent == dynamic_extent || Extent == 0, "Invalid Extent"); 259 } 260 261 template <typename It, 262 typename = internal::EnableIfCompatibleContiguousIterator<It, T>> 263 constexpr span(It first, StrictNumeric<size_t> count) noexcept 264 : ExtentStorage(count), 265 // The use of to_address() here is to handle the case where the iterator 266 // `first` is pointing to the container's `end()`. In that case we can 267 // not use the address returned from the iterator, or dereference it 268 // through the iterator's `operator*`, but we can store it. We must 269 // assume in this case that `count` is 0, since the iterator does not 270 // point to valid data. Future hardening of iterators may disallow 271 // pulling the address from `end()`, as demonstrated by asserts() in 272 // libstdc++: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93960. 273 // 274 // The span API dictates that the `data()` is accessible when size is 0, 275 // since the pointer may be valid, so we cannot prevent storing and 276 // giving out an invalid pointer here without breaking API compatibility 277 // and our unit tests. Thus protecting against this can likely only be 278 // successful from inside iterators themselves, where the context about 279 // the pointer is known. 280 // 281 // We can not protect here generally against an invalid iterator/count 282 // being passed in, since we have no context to determine if the 283 // iterator or count are valid. 284 data_(base::to_address(first)) { 285 CHECK(Extent == dynamic_extent || Extent == count); 286 } 287 288 template <typename It, 289 typename End, 290 typename = internal::EnableIfCompatibleContiguousIterator<It, T>, 291 typename = std::enable_if_t<!std::is_convertible_v<End, size_t>>> 292 constexpr span(It begin, End end) noexcept 293 // Subtracting two iterators gives a ptrdiff_t, but the result should be 294 // non-negative: see CHECK below. 295 : span(begin, static_cast<size_t>(end - begin)) { 296 // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. 297 CHECK(begin <= end); 298 } 299 300 template < 301 size_t N, 302 typename = internal::EnableIfSpanCompatibleArray<T (&)[N], T, Extent>> 303 constexpr span(T (&array)[N]) noexcept : span(std::data(array), N) {} 304 305 template < 306 typename U, 307 size_t N, 308 typename = 309 internal::EnableIfSpanCompatibleArray<std::array<U, N>&, T, Extent>> 310 constexpr span(std::array<U, N>& array) noexcept 311 : span(std::data(array), N) {} 312 313 template <typename U, 314 size_t N, 315 typename = internal:: 316 EnableIfSpanCompatibleArray<const std::array<U, N>&, T, Extent>> 317 constexpr span(const std::array<U, N>& array) noexcept 318 : span(std::data(array), N) {} 319 320 // Conversion from a container that has compatible std::data() and integral 321 // std::size(). 322 template < 323 typename Container, 324 typename = 325 internal::EnableIfSpanCompatibleContainerAndSpanIsDynamic<Container&, 326 T, 327 Extent>> 328 constexpr span(Container& container) noexcept 329 : span(std::data(container), std::size(container)) {} 330 331 template < 332 typename Container, 333 typename = internal::EnableIfSpanCompatibleContainerAndSpanIsDynamic< 334 const Container&, 335 T, 336 Extent>> 337 constexpr span(const Container& container) noexcept 338 : span(std::data(container), std::size(container)) {} 339 340 constexpr span(const span& other) noexcept = default; 341 342 // Conversions from spans of compatible types and extents: this allows a 343 // span<T> to be seamlessly used as a span<const T>, but not the other way 344 // around. If extent is not dynamic, OtherExtent has to be equal to Extent. 345 template < 346 typename U, 347 size_t OtherExtent, 348 typename = 349 internal::EnableIfLegalSpanConversion<U, OtherExtent, T, Extent>> 350 constexpr span(const span<U, OtherExtent>& other) 351 : span(other.data(), other.size()) {} 352 353 constexpr span& operator=(const span& other) noexcept = default; 354 ~span() noexcept = default; 355 356 // [span.sub], span subviews 357 template <size_t Count> 358 constexpr span<T, Count> first() const noexcept { 359 static_assert(Count <= Extent, "Count must not exceed Extent"); 360 CHECK(Extent != dynamic_extent || Count <= size()); 361 return {data(), Count}; 362 } 363 364 template <size_t Count> 365 constexpr span<T, Count> last() const noexcept { 366 static_assert(Count <= Extent, "Count must not exceed Extent"); 367 CHECK(Extent != dynamic_extent || Count <= size()); 368 return {data() + (size() - Count), Count}; 369 } 370 371 template <size_t Offset, size_t Count = dynamic_extent> 372 constexpr span<T, 373 (Count != dynamic_extent 374 ? Count 375 : (Extent != dynamic_extent ? Extent - Offset 376 : dynamic_extent))> 377 subspan() const noexcept { 378 static_assert(Offset <= Extent, "Offset must not exceed Extent"); 379 static_assert(Count == dynamic_extent || Count <= Extent - Offset, 380 "Count must not exceed Extent - Offset"); 381 CHECK(Extent != dynamic_extent || Offset <= size()); 382 CHECK(Extent != dynamic_extent || Count == dynamic_extent || 383 Count <= size() - Offset); 384 return {data() + Offset, Count != dynamic_extent ? Count : size() - Offset}; 385 } 386 387 constexpr span<T, dynamic_extent> first(size_t count) const noexcept { 388 // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. 389 CHECK(count <= size()); 390 return {data(), count}; 391 } 392 393 constexpr span<T, dynamic_extent> last(size_t count) const noexcept { 394 // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. 395 CHECK(count <= size()); 396 return {data() + (size() - count), count}; 397 } 398 399 constexpr span<T, dynamic_extent> subspan(size_t offset, 400 size_t count = dynamic_extent) const 401 noexcept { 402 // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. 403 CHECK(offset <= size()); 404 CHECK(count == dynamic_extent || count <= size() - offset); 405 return {data() + offset, count != dynamic_extent ? count : size() - offset}; 406 } 407 408 // [span.obs], span observers 409 constexpr size_t size() const noexcept { return ExtentStorage::size(); } 410 constexpr size_t size_bytes() const noexcept { return size() * sizeof(T); } 411 [[nodiscard]] constexpr bool empty() const noexcept { return size() == 0; } 412 413 // [span.elem], span element access 414 constexpr T& operator[](size_t idx) const noexcept { 415 // Note: CHECK_LT is not constexpr, hence regular CHECK must be used. 416 CHECK(idx < size()); 417 return *(data() + idx); 418 } 419 420 constexpr T& front() const noexcept { 421 static_assert(Extent == dynamic_extent || Extent > 0, 422 "Extent must not be 0"); 423 CHECK(Extent != dynamic_extent || !empty()); 424 return *data(); 425 } 426 427 constexpr T& back() const noexcept { 428 static_assert(Extent == dynamic_extent || Extent > 0, 429 "Extent must not be 0"); 430 CHECK(Extent != dynamic_extent || !empty()); 431 return *(data() + size() - 1); 432 } 433 434 constexpr T* data() const noexcept { return data_; } 435 436 // [span.iter], span iterator support 437 constexpr iterator begin() const noexcept { 438 return iterator(data(), data() + size()); 439 } 440 441 constexpr iterator end() const noexcept { 442 return iterator(data(), data() + size(), data() + size()); 443 } 444 445 constexpr reverse_iterator rbegin() const noexcept { 446 return reverse_iterator(end()); 447 } 448 449 constexpr reverse_iterator rend() const noexcept { 450 return reverse_iterator(begin()); 451 } 452 453 private: 454 // This field is not a raw_ptr<> because it was filtered by the rewriter 455 // for: #constexpr-ctor-field-initializer, #global-scope, #union 456 InternalPtrType data_; 457 }; 458 459 // span<T, Extent>::extent can not be declared inline prior to C++17, hence this 460 // definition is required. 461 template <class T, size_t Extent, typename InternalPtrType> 462 constexpr size_t span<T, Extent, InternalPtrType>::extent; 463 464 template <typename It, 465 typename T = std::remove_reference_t<iter_reference_t<It>>> 466 span(It, StrictNumeric<size_t>) -> span<T>; 467 468 template <typename It, 469 typename End, 470 typename = std::enable_if_t<!std::is_convertible_v<End, size_t>>, 471 typename T = std::remove_reference_t<iter_reference_t<It>>> 472 span(It, End) -> span<T>; 473 474 template <typename T, size_t N> 475 span(T (&)[N]) -> span<T, N>; 476 477 template <typename T, size_t N> 478 span(std::array<T, N>&) -> span<T, N>; 479 480 template <typename T, size_t N> 481 span(const std::array<T, N>&) -> span<const T, N>; 482 483 template <typename Container, 484 typename T = std::remove_pointer_t< 485 decltype(std::data(std::declval<Container>()))>, 486 size_t X = internal::Extent<Container>::value> 487 span(Container&&) -> span<T, X>; 488 489 // [span.objectrep], views of object representation 490 template <typename T, size_t X> 491 span<const uint8_t, (X == dynamic_extent ? dynamic_extent : sizeof(T) * X)> 492 as_bytes(span<T, X> s) noexcept { 493 return {reinterpret_cast<const uint8_t*>(s.data()), s.size_bytes()}; 494 } 495 496 template <typename T, 497 size_t X, 498 typename = std::enable_if_t<!std::is_const_v<T>>> 499 span<uint8_t, (X == dynamic_extent ? dynamic_extent : sizeof(T) * X)> 500 as_writable_bytes(span<T, X> s) noexcept { 501 return {reinterpret_cast<uint8_t*>(s.data()), s.size_bytes()}; 502 } 503 504 // Type-deducing helpers for constructing a span. 505 template <int&... ExplicitArgumentBarrier, typename It> 506 constexpr auto make_span(It it, StrictNumeric<size_t> size) noexcept { 507 using T = std::remove_reference_t<iter_reference_t<It>>; 508 return span<T>(it, size); 509 } 510 511 template <int&... ExplicitArgumentBarrier, 512 typename It, 513 typename End, 514 typename = std::enable_if_t<!std::is_convertible_v<End, size_t>>> 515 constexpr auto make_span(It it, End end) noexcept { 516 using T = std::remove_reference_t<iter_reference_t<It>>; 517 return span<T>(it, end); 518 } 519 520 // make_span utility function that deduces both the span's value_type and extent 521 // from the passed in argument. 522 // 523 // Usage: auto span = base::make_span(...); 524 template <int&... ExplicitArgumentBarrier, typename Container> 525 constexpr auto make_span(Container&& container) noexcept { 526 using T = 527 std::remove_pointer_t<decltype(std::data(std::declval<Container>()))>; 528 using Extent = internal::Extent<Container>; 529 return span<T, Extent::value>(std::forward<Container>(container)); 530 } 531 532 // make_span utility functions that allow callers to explicit specify the span's 533 // extent, the value_type is deduced automatically. This is useful when passing 534 // a dynamically sized container to a method expecting static spans, when the 535 // container is known to have the correct size. 536 // 537 // Note: This will CHECK that N indeed matches size(container). 538 // 539 // Usage: auto static_span = base::make_span<N>(...); 540 template <size_t N, int&... ExplicitArgumentBarrier, typename It> 541 constexpr auto make_span(It it, StrictNumeric<size_t> size) noexcept { 542 using T = std::remove_reference_t<iter_reference_t<It>>; 543 return span<T, N>(it, size); 544 } 545 546 template <size_t N, 547 int&... ExplicitArgumentBarrier, 548 typename It, 549 typename End, 550 typename = std::enable_if_t<!std::is_convertible_v<End, size_t>>> 551 constexpr auto make_span(It it, End end) noexcept { 552 using T = std::remove_reference_t<iter_reference_t<It>>; 553 return span<T, N>(it, end); 554 } 555 556 template <size_t N, int&... ExplicitArgumentBarrier, typename Container> 557 constexpr auto make_span(Container&& container) noexcept { 558 using T = 559 std::remove_pointer_t<decltype(std::data(std::declval<Container>()))>; 560 return span<T, N>(std::data(container), std::size(container)); 561 } 562 563 } // namespace base 564 565 // EXTENT returns the size of any type that can be converted to a |base::span| 566 // with definite extent, i.e. everything that is a contiguous storage of some 567 // sort with static size. Specifically, this works for std::array in a constexpr 568 // context. Note: 569 // * |std::size| should be preferred for plain arrays. 570 // * In run-time contexts, functions such as |std::array::size| should be 571 // preferred. 572 #define EXTENT(x) \ 573 ::base::internal::must_not_be_dynamic_extent<decltype( \ 574 ::base::make_span(x))::extent>() 575 576 #endif // BASE_CONTAINERS_SPAN_H_