span.h 20 KB

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