checked_iterators.h 8.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265
  1. // Copyright 2018 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_CHECKED_ITERATORS_H_
  5. #define BASE_CONTAINERS_CHECKED_ITERATORS_H_
  6. #include <iterator>
  7. #include <memory>
  8. #include <type_traits>
  9. #include "base/check_op.h"
  10. #include "base/containers/util.h"
  11. #include "build/build_config.h"
  12. namespace base {
  13. template <typename T>
  14. class CheckedContiguousIterator {
  15. public:
  16. using difference_type = std::ptrdiff_t;
  17. using value_type = std::remove_cv_t<T>;
  18. using pointer = T*;
  19. using reference = T&;
  20. using iterator_category = std::random_access_iterator_tag;
  21. // Required for converting constructor below.
  22. template <typename U>
  23. friend class CheckedContiguousIterator;
  24. // Required for certain libc++ algorithm optimizations that are not available
  25. // for NaCl.
  26. #if defined(_LIBCPP_VERSION) && !BUILDFLAG(IS_NACL)
  27. template <typename Ptr>
  28. friend struct std::pointer_traits;
  29. #endif
  30. constexpr CheckedContiguousIterator() = default;
  31. constexpr CheckedContiguousIterator(T* start, const T* end)
  32. : CheckedContiguousIterator(start, start, end) {}
  33. constexpr CheckedContiguousIterator(const T* start, T* current, const T* end)
  34. : start_(start), current_(current), end_(end) {
  35. CHECK_LE(start, current);
  36. CHECK_LE(current, end);
  37. }
  38. constexpr CheckedContiguousIterator(const CheckedContiguousIterator& other) =
  39. default;
  40. // Converting constructor allowing conversions like CCI<T> to CCI<const T>,
  41. // but disallowing CCI<const T> to CCI<T> or CCI<Derived> to CCI<Base>, which
  42. // are unsafe. Furthermore, this is the same condition as used by the
  43. // converting constructors of std::span<T> and std::unique_ptr<T[]>.
  44. // See https://wg21.link/n4042 for details.
  45. template <
  46. typename U,
  47. std::enable_if_t<std::is_convertible<U (*)[], T (*)[]>::value>* = nullptr>
  48. constexpr CheckedContiguousIterator(const CheckedContiguousIterator<U>& other)
  49. : start_(other.start_), current_(other.current_), end_(other.end_) {
  50. // We explicitly don't delegate to the 3-argument constructor here. Its
  51. // CHECKs would be redundant, since we expect |other| to maintain its own
  52. // invariant. However, DCHECKs never hurt anybody. Presumably.
  53. DCHECK_LE(other.start_, other.current_);
  54. DCHECK_LE(other.current_, other.end_);
  55. }
  56. ~CheckedContiguousIterator() = default;
  57. constexpr CheckedContiguousIterator& operator=(
  58. const CheckedContiguousIterator& other) = default;
  59. friend constexpr bool operator==(const CheckedContiguousIterator& lhs,
  60. const CheckedContiguousIterator& rhs) {
  61. lhs.CheckComparable(rhs);
  62. return lhs.current_ == rhs.current_;
  63. }
  64. friend constexpr bool operator!=(const CheckedContiguousIterator& lhs,
  65. const CheckedContiguousIterator& rhs) {
  66. lhs.CheckComparable(rhs);
  67. return lhs.current_ != rhs.current_;
  68. }
  69. friend constexpr bool operator<(const CheckedContiguousIterator& lhs,
  70. const CheckedContiguousIterator& rhs) {
  71. lhs.CheckComparable(rhs);
  72. return lhs.current_ < rhs.current_;
  73. }
  74. friend constexpr bool operator<=(const CheckedContiguousIterator& lhs,
  75. const CheckedContiguousIterator& rhs) {
  76. lhs.CheckComparable(rhs);
  77. return lhs.current_ <= rhs.current_;
  78. }
  79. friend constexpr bool operator>(const CheckedContiguousIterator& lhs,
  80. const CheckedContiguousIterator& rhs) {
  81. lhs.CheckComparable(rhs);
  82. return lhs.current_ > rhs.current_;
  83. }
  84. friend constexpr bool operator>=(const CheckedContiguousIterator& lhs,
  85. const CheckedContiguousIterator& rhs) {
  86. lhs.CheckComparable(rhs);
  87. return lhs.current_ >= rhs.current_;
  88. }
  89. constexpr CheckedContiguousIterator& operator++() {
  90. CHECK_NE(current_, end_);
  91. ++current_;
  92. return *this;
  93. }
  94. constexpr CheckedContiguousIterator operator++(int) {
  95. CheckedContiguousIterator old = *this;
  96. ++*this;
  97. return old;
  98. }
  99. constexpr CheckedContiguousIterator& operator--() {
  100. CHECK_NE(current_, start_);
  101. --current_;
  102. return *this;
  103. }
  104. constexpr CheckedContiguousIterator operator--(int) {
  105. CheckedContiguousIterator old = *this;
  106. --*this;
  107. return old;
  108. }
  109. constexpr CheckedContiguousIterator& operator+=(difference_type rhs) {
  110. if (rhs > 0) {
  111. CHECK_LE(rhs, end_ - current_);
  112. } else {
  113. CHECK_LE(-rhs, current_ - start_);
  114. }
  115. current_ += rhs;
  116. return *this;
  117. }
  118. constexpr CheckedContiguousIterator operator+(difference_type rhs) const {
  119. CheckedContiguousIterator it = *this;
  120. it += rhs;
  121. return it;
  122. }
  123. constexpr CheckedContiguousIterator& operator-=(difference_type rhs) {
  124. if (rhs < 0) {
  125. CHECK_LE(-rhs, end_ - current_);
  126. } else {
  127. CHECK_LE(rhs, current_ - start_);
  128. }
  129. current_ -= rhs;
  130. return *this;
  131. }
  132. constexpr CheckedContiguousIterator operator-(difference_type rhs) const {
  133. CheckedContiguousIterator it = *this;
  134. it -= rhs;
  135. return it;
  136. }
  137. constexpr friend difference_type operator-(
  138. const CheckedContiguousIterator& lhs,
  139. const CheckedContiguousIterator& rhs) {
  140. lhs.CheckComparable(rhs);
  141. return lhs.current_ - rhs.current_;
  142. }
  143. constexpr reference operator*() const {
  144. CHECK_NE(current_, end_);
  145. return *current_;
  146. }
  147. constexpr pointer operator->() const {
  148. CHECK_NE(current_, end_);
  149. return current_;
  150. }
  151. constexpr reference operator[](difference_type rhs) const {
  152. CHECK_GE(rhs, 0);
  153. CHECK_LT(rhs, end_ - current_);
  154. return current_[rhs];
  155. }
  156. [[nodiscard]] static bool IsRangeMoveSafe(
  157. const CheckedContiguousIterator& from_begin,
  158. const CheckedContiguousIterator& from_end,
  159. const CheckedContiguousIterator& to) {
  160. if (from_end < from_begin)
  161. return false;
  162. const auto from_begin_uintptr = get_uintptr(from_begin.current_);
  163. const auto from_end_uintptr = get_uintptr(from_end.current_);
  164. const auto to_begin_uintptr = get_uintptr(to.current_);
  165. const auto to_end_uintptr =
  166. get_uintptr((to + std::distance(from_begin, from_end)).current_);
  167. return to_begin_uintptr >= from_end_uintptr ||
  168. to_end_uintptr <= from_begin_uintptr;
  169. }
  170. private:
  171. constexpr void CheckComparable(const CheckedContiguousIterator& other) const {
  172. CHECK_EQ(start_, other.start_);
  173. CHECK_EQ(end_, other.end_);
  174. }
  175. const T* start_ = nullptr;
  176. T* current_ = nullptr;
  177. const T* end_ = nullptr;
  178. };
  179. template <typename T>
  180. using CheckedContiguousConstIterator = CheckedContiguousIterator<const T>;
  181. } // namespace base
  182. #if defined(_LIBCPP_VERSION) && !BUILDFLAG(IS_NACL)
  183. // Specialize both std::__is_cpp17_contiguous_iterator and std::pointer_traits
  184. // for CCI in case we compile with libc++ outside of NaCl. The former is
  185. // required to enable certain algorithm optimizations (e.g. std::copy can be a
  186. // simple std::memmove under certain circumstances), and is a precursor to
  187. // C++20's std::contiguous_iterator concept [1]. Once we actually use C++20 it
  188. // will be enough to add `using iterator_concept = std::contiguous_iterator_tag`
  189. // to the iterator class [2], and we can get rid of this non-standard
  190. // specialization.
  191. //
  192. // The latter is required to obtain the underlying raw pointer without resulting
  193. // in CHECK failures. The important bit is the `to_address(pointer)` overload,
  194. // which is the standard blessed way to customize `std::to_address(pointer)` in
  195. // C++20 [3].
  196. //
  197. // [1] https://wg21.link/iterator.concept.contiguous
  198. // [2] https://wg21.link/std.iterator.tags
  199. // [3] https://wg21.link/pointer.traits.optmem
  200. namespace std {
  201. template <typename T>
  202. struct __is_cpp17_contiguous_iterator<::base::CheckedContiguousIterator<T>>
  203. : true_type {};
  204. template <typename T>
  205. struct pointer_traits<::base::CheckedContiguousIterator<T>> {
  206. using pointer = ::base::CheckedContiguousIterator<T>;
  207. using element_type = T;
  208. using difference_type = ptrdiff_t;
  209. template <typename U>
  210. using rebind = ::base::CheckedContiguousIterator<U>;
  211. static constexpr pointer pointer_to(element_type& r) noexcept {
  212. return pointer(&r, &r);
  213. }
  214. static constexpr element_type* to_address(pointer p) noexcept {
  215. return p.current_;
  216. }
  217. };
  218. } // namespace std
  219. #endif
  220. #endif // BASE_CONTAINERS_CHECKED_ITERATORS_H_