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 
5 #ifndef BASE_CONTAINERS_CHECKED_ITERATORS_H_
6 #define BASE_CONTAINERS_CHECKED_ITERATORS_H_
7 
8 #include <iterator>
9 #include <memory>
10 #include <type_traits>
11 
12 #include "base/containers/util.h"
13 #include "base/logging.h"
14 
15 namespace base {
16 
17 template <typename T>
18 class CheckedContiguousIterator {
19  public:
20   using difference_type = std::ptrdiff_t;
21   using value_type = std::remove_cv_t<T>;
22   using pointer = T*;
23   using reference = T&;
24   using iterator_category = std::random_access_iterator_tag;
25 
26   // Required for converting constructor below.
27   template <typename U>
28   friend class CheckedContiguousIterator;
29 
30   constexpr CheckedContiguousIterator() = default;
CheckedContiguousIterator(T * start,const T * end)31   constexpr CheckedContiguousIterator(T* start, const T* end)
32       : CheckedContiguousIterator(start, start, end) {}
CheckedContiguousIterator(const T * start,T * current,const T * 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 
41   // Converting constructor allowing conversions like CCI<T> to CCI<const T>,
42   // but disallowing CCI<const T> to CCI<T> or CCI<Derived> to CCI<Base>, which
43   // are unsafe. Furthermore, this is the same condition as used by the
44   // converting constructors of std::span<T> and std::unique_ptr<T[]>.
45   // See https://wg21.link/n4042 for details.
46   template <
47       typename U,
48       std::enable_if_t<std::is_convertible<U (*)[], T (*)[]>::value>* = nullptr>
CheckedContiguousIterator(const CheckedContiguousIterator<U> & other)49   constexpr CheckedContiguousIterator(const CheckedContiguousIterator<U>& other)
50       : start_(other.start_), current_(other.current_), end_(other.end_) {
51     // We explicitly don't delegate to the 3-argument constructor here. Its
52     // CHECKs would be redundant, since we expect |other| to maintain its own
53     // invariant. However, DCHECKs never hurt anybody. Presumably.
54     DCHECK_LE(other.start_, other.current_);
55     DCHECK_LE(other.current_, other.end_);
56   }
57 
58   ~CheckedContiguousIterator() = default;
59 
60   constexpr CheckedContiguousIterator& operator=(
61       const CheckedContiguousIterator& other) = default;
62 
63   constexpr bool operator==(const CheckedContiguousIterator& other) const {
64     CheckComparable(other);
65     return current_ == other.current_;
66   }
67 
68   constexpr bool operator!=(const CheckedContiguousIterator& other) const {
69     CheckComparable(other);
70     return current_ != other.current_;
71   }
72 
73   constexpr bool operator<(const CheckedContiguousIterator& other) const {
74     CheckComparable(other);
75     return current_ < other.current_;
76   }
77 
78   constexpr bool operator<=(const CheckedContiguousIterator& other) const {
79     CheckComparable(other);
80     return current_ <= other.current_;
81   }
82 
83   constexpr bool operator>(const CheckedContiguousIterator& other) const {
84     CheckComparable(other);
85     return current_ > other.current_;
86   }
87 
88   constexpr bool operator>=(const CheckedContiguousIterator& other) const {
89     CheckComparable(other);
90     return current_ >= other.current_;
91   }
92 
93   constexpr CheckedContiguousIterator& operator++() {
94     CHECK_NE(current_, end_);
95     ++current_;
96     return *this;
97   }
98 
99   constexpr CheckedContiguousIterator operator++(int) {
100     CheckedContiguousIterator old = *this;
101     ++*this;
102     return old;
103   }
104 
105   constexpr CheckedContiguousIterator& operator--() {
106     CHECK_NE(current_, start_);
107     --current_;
108     return *this;
109   }
110 
111   constexpr CheckedContiguousIterator operator--(int) {
112     CheckedContiguousIterator old = *this;
113     --*this;
114     return old;
115   }
116 
117   constexpr CheckedContiguousIterator& operator+=(difference_type rhs) {
118     if (rhs > 0) {
119       CHECK_LE(rhs, end_ - current_);
120     } else {
121       CHECK_LE(-rhs, current_ - start_);
122     }
123     current_ += rhs;
124     return *this;
125   }
126 
127   constexpr CheckedContiguousIterator operator+(difference_type rhs) const {
128     CheckedContiguousIterator it = *this;
129     it += rhs;
130     return it;
131   }
132 
133   constexpr CheckedContiguousIterator& operator-=(difference_type rhs) {
134     if (rhs < 0) {
135       CHECK_LE(-rhs, end_ - current_);
136     } else {
137       CHECK_LE(rhs, current_ - start_);
138     }
139     current_ -= rhs;
140     return *this;
141   }
142 
143   constexpr CheckedContiguousIterator operator-(difference_type rhs) const {
144     CheckedContiguousIterator it = *this;
145     it -= rhs;
146     return it;
147   }
148 
149   constexpr friend difference_type operator-(
150       const CheckedContiguousIterator& lhs,
151       const CheckedContiguousIterator& rhs) {
152     CHECK_EQ(lhs.start_, rhs.start_);
153     CHECK_EQ(lhs.end_, rhs.end_);
154     return lhs.current_ - rhs.current_;
155   }
156 
157   constexpr reference operator*() const {
158     CHECK_NE(current_, end_);
159     return *current_;
160   }
161 
162   constexpr pointer operator->() const {
163     CHECK_NE(current_, end_);
164     return current_;
165   }
166 
167   constexpr reference operator[](difference_type rhs) const {
168     CHECK_GE(rhs, 0);
169     CHECK_LT(rhs, end_ - current_);
170     return current_[rhs];
171   }
172 
IsRangeMoveSafe(const CheckedContiguousIterator & from_begin,const CheckedContiguousIterator & from_end,const CheckedContiguousIterator & to)173   static bool IsRangeMoveSafe(const CheckedContiguousIterator& from_begin,
174                               const CheckedContiguousIterator& from_end,
175                               const CheckedContiguousIterator& to)
176       WARN_UNUSED_RESULT {
177     if (from_end < from_begin)
178       return false;
179     const auto from_begin_uintptr = get_uintptr(from_begin.current_);
180     const auto from_end_uintptr = get_uintptr(from_end.current_);
181     const auto to_begin_uintptr = get_uintptr(to.current_);
182     const auto to_end_uintptr =
183         get_uintptr((to + std::distance(from_begin, from_end)).current_);
184 
185     return to_begin_uintptr >= from_end_uintptr ||
186            to_end_uintptr <= from_begin_uintptr;
187   }
188 
189  private:
CheckComparable(const CheckedContiguousIterator & other)190   constexpr void CheckComparable(const CheckedContiguousIterator& other) const {
191     CHECK_EQ(start_, other.start_);
192     CHECK_EQ(end_, other.end_);
193   }
194 
195   const T* start_ = nullptr;
196   T* current_ = nullptr;
197   const T* end_ = nullptr;
198 };
199 
200 template <typename T>
201 using CheckedContiguousConstIterator = CheckedContiguousIterator<const T>;
202 
203 }  // namespace base
204 
205 #endif  // BASE_CONTAINERS_CHECKED_ITERATORS_H_
206