1// Copyright 2017 The Chromium Authors. All rights reserved. 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 <algorithm> 12#include <array> 13#include <iterator> 14#include <string_view> 15#include <type_traits> 16#include <utility> 17 18#include "base/logging.h" 19#include "base/stl_util.h" 20 21namespace base { 22 23// [views.constants] 24constexpr size_t dynamic_extent = static_cast<size_t>(-1); 25 26template <typename T, size_t Extent = dynamic_extent> 27class span; 28 29namespace internal { 30 31template <typename T> 32struct IsSpanImpl : std::false_type {}; 33 34template <typename T, size_t Extent> 35struct IsSpanImpl<span<T, Extent>> : std::true_type {}; 36 37template <typename T> 38using IsSpan = IsSpanImpl<std::decay_t<T>>; 39 40template <typename T> 41struct IsStdArrayImpl : std::false_type {}; 42 43template <typename T, size_t N> 44struct IsStdArrayImpl<std::array<T, N>> : std::true_type {}; 45 46template <typename T> 47using IsStdArray = IsStdArrayImpl<std::decay_t<T>>; 48 49template <typename T> 50using IsCArray = std::is_array<std::remove_reference_t<T>>; 51 52template <typename From, typename To> 53using IsLegalDataConversion = std::is_convertible<From (*)[], To (*)[]>; 54 55template <typename Container, typename T> 56using ContainerHasConvertibleData = IsLegalDataConversion< 57 std::remove_pointer_t<decltype(std::data(std::declval<Container>()))>, 58 T>; 59 60template <typename Container> 61using ContainerHasIntegralSize = 62 std::is_integral<decltype(std::size(std::declval<Container>()))>; 63 64template <typename From, size_t FromExtent, typename To, size_t ToExtent> 65using EnableIfLegalSpanConversion = 66 std::enable_if_t<(ToExtent == dynamic_extent || ToExtent == FromExtent) && 67 IsLegalDataConversion<From, To>::value>; 68 69// SFINAE check if Array can be converted to a span<T>. 70template <typename Array, size_t N, typename T, size_t Extent> 71using EnableIfSpanCompatibleArray = 72 std::enable_if_t<(Extent == dynamic_extent || Extent == N) && 73 ContainerHasConvertibleData<Array, T>::value>; 74 75// SFINAE check if Container can be converted to a span<T>. 76template <typename Container, typename T> 77using EnableIfSpanCompatibleContainer = 78 std::enable_if_t<!internal::IsSpan<Container>::value && 79 !internal::IsStdArray<Container>::value && 80 !internal::IsCArray<Container>::value && 81 ContainerHasConvertibleData<Container, T>::value && 82 ContainerHasIntegralSize<Container>::value>; 83 84} // namespace internal 85 86// A span is a value type that represents an array of elements of type T. Since 87// it only consists of a pointer to memory with an associated size, it is very 88// light-weight. It is cheap to construct, copy, move and use spans, so that 89// users are encouraged to use it as a pass-by-value parameter. A span does not 90// own the underlying memory, so care must be taken to ensure that a span does 91// not outlive the backing store. 92// 93// span is somewhat analogous to std::string_view, but with arbitrary element 94// types, allowing mutation if T is non-const. 95// 96// span is implicitly convertible from C++ arrays, as well as most [1] 97// container-like types that provide a data() and size() method (such as 98// std::vector<T>). A mutable span<T> can also be implicitly converted to an 99// immutable span<const T>. 100// 101// Consider using a span for functions that take a data pointer and size 102// parameter: it allows the function to still act on an array-like type, while 103// allowing the caller code to be a bit more concise. 104// 105// For read-only data access pass a span<const T>: the caller can supply either 106// a span<const T> or a span<T>, while the callee will have a read-only view. 107// For read-write access a mutable span<T> is required. 108// 109// Without span: 110// Read-Only: 111// // std::string HexEncode(const uint8_t* data, size_t size); 112// std::vector<uint8_t> data_buffer = GenerateData(); 113// std::string r = HexEncode(data_buffer.data(), data_buffer.size()); 114// 115// Mutable: 116// // ssize_t SafeSNPrintf(char* buf, size_t N, const char* fmt, Args...); 117// char str_buffer[100]; 118// SafeSNPrintf(str_buffer, sizeof(str_buffer), "Pi ~= %lf", 3.14); 119// 120// With span: 121// Read-Only: 122// // std::string HexEncode(base::span<const uint8_t> data); 123// std::vector<uint8_t> data_buffer = GenerateData(); 124// std::string r = HexEncode(data_buffer); 125// 126// Mutable: 127// // ssize_t SafeSNPrintf(base::span<char>, const char* fmt, Args...); 128// char str_buffer[100]; 129// SafeSNPrintf(str_buffer, "Pi ~= %lf", 3.14); 130// 131// Spans with "const" and pointers 132// ------------------------------- 133// 134// Const and pointers can get confusing. Here are vectors of pointers and their 135// corresponding spans: 136// 137// const std::vector<int*> => base::span<int* const> 138// std::vector<const int*> => base::span<const int*> 139// const std::vector<const int*> => base::span<const int* const> 140// 141// Differences from the working group proposal 142// ------------------------------------------- 143// 144// https://wg21.link/P0122 is the latest working group proposal, Chromium 145// currently implements R7. Differences between the proposal and the 146// implementation are documented in subsections below. 147// 148// Differences from [span.objectrep]: 149// - as_bytes() and as_writable_bytes() return spans of uint8_t instead of 150// std::byte 151// 152// Differences in constants and types: 153// - index_type is aliased to size_t 154// 155// Differences from [span.sub]: 156// - using size_t instead of ptrdiff_t for indexing 157// 158// Differences from [span.obs]: 159// - using size_t instead of ptrdiff_t to represent size() 160// 161// Differences from [span.elem]: 162// - using size_t instead of ptrdiff_t for indexing 163// 164// Furthermore, all constructors and methods are marked noexcept due to the lack 165// of exceptions in Chromium. 166// 167// Due to the lack of class template argument deduction guides in C++14 168// appropriate make_span() utility functions are provided. 169 170// [span], class template span 171template <typename T, size_t Extent> 172class span { 173 public: 174 using element_type = T; 175 using value_type = std::remove_cv_t<T>; 176 using index_type = size_t; 177 using difference_type = ptrdiff_t; 178 using pointer = T*; 179 using reference = T&; 180 using iterator = T*; 181 using const_iterator = const T*; 182 using reverse_iterator = std::reverse_iterator<iterator>; 183 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 184 static constexpr index_type extent = Extent; 185 186 // [span.cons], span constructors, copy, assignment, and destructor 187 constexpr span() noexcept : data_(nullptr), size_(0) { 188 static_assert(Extent == dynamic_extent || Extent == 0, "Invalid Extent"); 189 } 190 191 constexpr span(T* data, size_t size) noexcept : data_(data), size_(size) { 192 CHECK(Extent == dynamic_extent || Extent == size); 193 } 194 195 // Artificially templatized to break ambiguity for span(ptr, 0). 196 template <typename = void> 197 constexpr span(T* begin, T* end) noexcept : span(begin, end - begin) { 198 // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. 199 CHECK(begin <= end); 200 } 201 202 template < 203 size_t N, 204 typename = internal::EnableIfSpanCompatibleArray<T (&)[N], N, T, Extent>> 205 constexpr span(T (&array)[N]) noexcept : span(std::data(array), N) {} 206 207 template < 208 size_t N, 209 typename = internal:: 210 EnableIfSpanCompatibleArray<std::array<value_type, N>&, N, T, Extent>> 211 constexpr span(std::array<value_type, N>& array) noexcept 212 : span(std::data(array), N) {} 213 214 template <size_t N, 215 typename = internal::EnableIfSpanCompatibleArray< 216 const std::array<value_type, N>&, 217 N, 218 T, 219 Extent>> 220 constexpr span(const std::array<value_type, N>& array) noexcept 221 : span(std::data(array), N) {} 222 223 // Conversion from a container that has compatible std::data() and integral 224 // std::size(). 225 template <typename Container, 226 typename = internal::EnableIfSpanCompatibleContainer<Container&, T>> 227 constexpr span(Container& container) noexcept 228 : span(std::data(container), std::size(container)) {} 229 230 template < 231 typename Container, 232 typename = internal::EnableIfSpanCompatibleContainer<const Container&, T>> 233 span(const Container& container) noexcept 234 : span(std::data(container), std::size(container)) {} 235 236 constexpr span(const span& other) noexcept = default; 237 238 // Conversions from spans of compatible types and extents: this allows a 239 // span<T> to be seamlessly used as a span<const T>, but not the other way 240 // around. If extent is not dynamic, OtherExtent has to be equal to Extent. 241 template < 242 typename U, 243 size_t OtherExtent, 244 typename = 245 internal::EnableIfLegalSpanConversion<U, OtherExtent, T, Extent>> 246 constexpr span(const span<U, OtherExtent>& other) 247 : span(other.data(), other.size()) {} 248 249 constexpr span& operator=(const span& other) noexcept = default; 250 ~span() noexcept = default; 251 252 // [span.sub], span subviews 253 template <size_t Count> 254 constexpr span<T, Count> first() const noexcept { 255 static_assert(Extent == dynamic_extent || Count <= Extent, 256 "Count must not exceed Extent"); 257 CHECK(Extent != dynamic_extent || Count <= size()); 258 return {data(), Count}; 259 } 260 261 template <size_t Count> 262 constexpr span<T, Count> last() const noexcept { 263 static_assert(Extent == dynamic_extent || Count <= Extent, 264 "Count must not exceed Extent"); 265 CHECK(Extent != dynamic_extent || Count <= size()); 266 return {data() + (size() - Count), Count}; 267 } 268 269 template <size_t Offset, size_t Count = dynamic_extent> 270 constexpr span<T, 271 (Count != dynamic_extent 272 ? Count 273 : (Extent != dynamic_extent ? Extent - Offset 274 : dynamic_extent))> 275 subspan() const noexcept { 276 static_assert(Extent == dynamic_extent || Offset <= Extent, 277 "Offset must not exceed Extent"); 278 static_assert(Extent == dynamic_extent || Count == dynamic_extent || 279 Count <= Extent - Offset, 280 "Count must not exceed Extent - Offset"); 281 CHECK(Extent != dynamic_extent || Offset <= size()); 282 CHECK(Extent != dynamic_extent || Count == dynamic_extent || 283 Count <= size() - Offset); 284 return {data() + Offset, Count != dynamic_extent ? Count : size() - Offset}; 285 } 286 287 constexpr span<T, dynamic_extent> first(size_t count) const noexcept { 288 // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. 289 CHECK(count <= size()); 290 return {data(), count}; 291 } 292 293 constexpr span<T, dynamic_extent> last(size_t count) const noexcept { 294 // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. 295 CHECK(count <= size()); 296 return {data() + (size() - count), count}; 297 } 298 299 constexpr span<T, dynamic_extent> subspan( 300 size_t offset, 301 size_t count = dynamic_extent) const noexcept { 302 // Note: CHECK_LE is not constexpr, hence regular CHECK must be used. 303 CHECK(offset <= size()); 304 CHECK(count == dynamic_extent || count <= size() - offset); 305 return {data() + offset, count != dynamic_extent ? count : size() - offset}; 306 } 307 308 // [span.obs], span observers 309 constexpr size_t size() const noexcept { return size_; } 310 constexpr size_t size_bytes() const noexcept { return size() * sizeof(T); } 311 constexpr bool empty() const noexcept { return size() == 0; } 312 313 // [span.elem], span element access 314 constexpr T& operator[](size_t idx) const noexcept { 315 // Note: CHECK_LT is not constexpr, hence regular CHECK must be used. 316 CHECK(idx < size()); 317 return *(data() + idx); 318 } 319 320 constexpr T& operator()(size_t idx) const noexcept { 321 // Note: CHECK_LT is not constexpr, hence regular CHECK must be used. 322 CHECK(idx < size()); 323 return *(data() + idx); 324 } 325 326 constexpr T* data() const noexcept { return data_; } 327 328 // [span.iter], span iterator support 329 constexpr iterator begin() const noexcept { return data(); } 330 constexpr iterator end() const noexcept { return data() + size(); } 331 332 constexpr const_iterator cbegin() const noexcept { return begin(); } 333 constexpr const_iterator cend() const noexcept { return end(); } 334 335 constexpr reverse_iterator rbegin() const noexcept { 336 return reverse_iterator(end()); 337 } 338 constexpr reverse_iterator rend() const noexcept { 339 return reverse_iterator(begin()); 340 } 341 342 constexpr const_reverse_iterator crbegin() const noexcept { 343 return const_reverse_iterator(cend()); 344 } 345 constexpr const_reverse_iterator crend() const noexcept { 346 return const_reverse_iterator(cbegin()); 347 } 348 349 private: 350 T* data_; 351 size_t size_; 352}; 353 354// span<T, Extent>::extent can not be declared inline prior to C++17, hence this 355// definition is required. 356template <class T, size_t Extent> 357constexpr size_t span<T, Extent>::extent; 358 359// [span.comparison], span comparison operators 360// Relational operators. Equality is a element-wise comparison. 361template <typename T, size_t X, typename U, size_t Y> 362constexpr bool operator==(span<T, X> lhs, span<U, Y> rhs) noexcept { 363 return std::equal(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend()); 364} 365 366template <typename T, size_t X, typename U, size_t Y> 367constexpr bool operator!=(span<T, X> lhs, span<U, Y> rhs) noexcept { 368 return !(lhs == rhs); 369} 370 371template <typename T, size_t X, typename U, size_t Y> 372constexpr bool operator<(span<T, X> lhs, span<U, Y> rhs) noexcept { 373 return std::lexicographical_compare(lhs.cbegin(), lhs.cend(), rhs.cbegin(), 374 rhs.cend()); 375} 376 377template <typename T, size_t X, typename U, size_t Y> 378constexpr bool operator<=(span<T, X> lhs, span<U, Y> rhs) noexcept { 379 return !(rhs < lhs); 380} 381 382template <typename T, size_t X, typename U, size_t Y> 383constexpr bool operator>(span<T, X> lhs, span<U, Y> rhs) noexcept { 384 return rhs < lhs; 385} 386 387template <typename T, size_t X, typename U, size_t Y> 388constexpr bool operator>=(span<T, X> lhs, span<U, Y> rhs) noexcept { 389 return !(lhs < rhs); 390} 391 392// [span.objectrep], views of object representation 393template <typename T, size_t X> 394span<const uint8_t, (X == dynamic_extent ? dynamic_extent : sizeof(T) * X)> 395as_bytes(span<T, X> s) noexcept { 396 return {reinterpret_cast<const uint8_t*>(s.data()), s.size_bytes()}; 397} 398 399template <typename T, 400 size_t X, 401 typename = std::enable_if_t<!std::is_const<T>::value>> 402span<uint8_t, (X == dynamic_extent ? dynamic_extent : sizeof(T) * X)> 403as_writable_bytes(span<T, X> s) noexcept { 404 return {reinterpret_cast<uint8_t*>(s.data()), s.size_bytes()}; 405} 406 407// Type-deducing helpers for constructing a span. 408template <typename T> 409constexpr span<T> make_span(T* data, size_t size) noexcept { 410 return {data, size}; 411} 412 413template <typename T> 414constexpr span<T> make_span(T* begin, T* end) noexcept { 415 return {begin, end}; 416} 417 418template <typename T, size_t N> 419constexpr span<T, N> make_span(T (&array)[N]) noexcept { 420 return array; 421} 422 423template <typename T, size_t N> 424constexpr span<T, N> make_span(std::array<T, N>& array) noexcept { 425 return array; 426} 427 428template <typename T, size_t N> 429constexpr span<const T, N> make_span(const std::array<T, N>& array) noexcept { 430 return array; 431} 432 433template <typename Container, 434 typename T = typename Container::value_type, 435 typename = internal::EnableIfSpanCompatibleContainer<Container&, T>> 436constexpr span<T> make_span(Container& container) noexcept { 437 return container; 438} 439 440template < 441 typename Container, 442 typename T = const typename Container::value_type, 443 typename = internal::EnableIfSpanCompatibleContainer<const Container&, T>> 444constexpr span<T> make_span(const Container& container) noexcept { 445 return container; 446} 447 448template <typename T, size_t X> 449constexpr span<T, X> make_span(const span<T, X>& span) noexcept { 450 return span; 451} 452 453} // namespace base 454 455#endif // BASE_CONTAINERS_SPAN_H_ 456