1 // Copyright 2020 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 #include "base/containers/checked_iterators.h"
6
7 #include <algorithm>
8 #include <iterator>
9
10 #include "base/check_op.h"
11 #include "base/debug/alias.h"
12 #include "base/ranges/algorithm.h"
13 #include "base/test/gtest_util.h"
14 #include "build/build_config.h"
15 #include "testing/gtest/include/gtest/gtest.h"
16
17 namespace base {
18
TEST(CheckedContiguousIterator,SatisfiesContiguousIteratorConcept)19 TEST(CheckedContiguousIterator, SatisfiesContiguousIteratorConcept) {
20 static_assert(std::contiguous_iterator<CheckedContiguousIterator<int>>);
21 }
22
23 template <class T, size_t N>
MakeConstIter(T (& arr)[N],size_t cur)24 constexpr CheckedContiguousConstIterator<T> MakeConstIter(T (&arr)[N],
25 size_t cur) {
26 // We allow cur == N as that makes a pointer at one-past-the-end which is
27 // considered part of the same allocation.
28 CHECK_LE(cur, N);
29 return
30 // SAFETY: `arr` has 1 element, `arr + 1` is considered a pointer into the
31 // same allocation, as it's one past the end.
32 UNSAFE_BUFFERS(
33 CheckedContiguousConstIterator<T>(arr, arr + cur, arr + N));
34 }
35
36 template <class T, size_t N>
MakeIter(T (& arr)[N],size_t cur)37 constexpr CheckedContiguousIterator<T> MakeIter(T (&arr)[N], size_t cur) {
38 // We allow cur == N as that makes a pointer at one-past-the-end which is
39 // considered part of the same allocation.
40 CHECK_LE(cur, N);
41 return
42 // SAFETY: `arr` has 1 element, `arr + 1` is considered a pointer into the
43 // same allocation, as it's one past the end.
44 UNSAFE_BUFFERS(CheckedContiguousIterator<T>(arr, arr + cur, arr + N));
45 }
46
47 // Checks that constexpr CheckedContiguousConstIterators can be compared at
48 // compile time.
TEST(CheckedContiguousIterator,StaticComparisonOperators)49 TEST(CheckedContiguousIterator, StaticComparisonOperators) {
50 static constexpr int arr[] = {0};
51
52 constexpr CheckedContiguousConstIterator<int> begin = MakeConstIter(arr, 0u);
53 constexpr CheckedContiguousConstIterator<int> end = MakeConstIter(arr, 1u);
54
55 static_assert(begin == begin);
56 static_assert(end == end);
57
58 static_assert(begin != end);
59 static_assert(end != begin);
60
61 static_assert(begin < end);
62
63 static_assert(begin <= begin);
64 static_assert(begin <= end);
65 static_assert(end <= end);
66
67 static_assert(end > begin);
68
69 static_assert(end >= end);
70 static_assert(end >= begin);
71 static_assert(begin >= begin);
72 }
73
74 // Checks that comparison between iterators and const iterators works in both
75 // directions.
TEST(CheckedContiguousIterator,ConvertingComparisonOperators)76 TEST(CheckedContiguousIterator, ConvertingComparisonOperators) {
77 static int arr[] = {0};
78
79 CheckedContiguousIterator<int> begin = MakeIter(arr, 0u);
80 CheckedContiguousConstIterator<int> cbegin = MakeConstIter(arr, 0u);
81
82 CheckedContiguousIterator<int> end = MakeIter(arr, 1u);
83 CheckedContiguousConstIterator<int> cend = MakeConstIter(arr, 1u);
84
85 EXPECT_EQ(begin, cbegin);
86 EXPECT_EQ(cbegin, begin);
87 EXPECT_EQ(end, cend);
88 EXPECT_EQ(cend, end);
89
90 EXPECT_NE(begin, cend);
91 EXPECT_NE(cbegin, end);
92 EXPECT_NE(end, cbegin);
93 EXPECT_NE(cend, begin);
94
95 EXPECT_LT(begin, cend);
96 EXPECT_LT(cbegin, end);
97
98 EXPECT_LE(begin, cbegin);
99 EXPECT_LE(cbegin, begin);
100 EXPECT_LE(begin, cend);
101 EXPECT_LE(cbegin, end);
102 EXPECT_LE(end, cend);
103 EXPECT_LE(cend, end);
104
105 EXPECT_GT(end, cbegin);
106 EXPECT_GT(cend, begin);
107
108 EXPECT_GE(end, cend);
109 EXPECT_GE(cend, end);
110 EXPECT_GE(end, cbegin);
111 EXPECT_GE(cend, begin);
112 EXPECT_GE(begin, cbegin);
113 EXPECT_GE(cbegin, begin);
114 }
115
TEST(CheckedContiguousIteratorDeathTest,OutOfBounds)116 TEST(CheckedContiguousIteratorDeathTest, OutOfBounds) {
117 static int arr[] = {0, 1, 2};
118
119 CheckedContiguousIterator<int> it = MakeIter(arr, 1u);
120
121 EXPECT_CHECK_DEATH(base::debug::Alias(&it[-2]));
122 EXPECT_EQ(it[-1], 0);
123 EXPECT_EQ(it[0], 1);
124 EXPECT_EQ(it[1], 2);
125 EXPECT_CHECK_DEATH(base::debug::Alias(&it[3]));
126
127 it += 2; // At [3], in bounds (at end).
128 it -= 3; // At [0], in bounds.
129 it += 1; // Back to [1], in bounds.
130
131 EXPECT_CHECK_DEATH({
132 it -= 2;
133 base::debug::Alias(&it);
134 });
135 EXPECT_CHECK_DEATH({
136 it += 3;
137 base::debug::Alias(&it);
138 });
139 EXPECT_CHECK_DEATH({
140 auto o = it - 2;
141 base::debug::Alias(&o);
142 });
143 EXPECT_CHECK_DEATH({
144 auto o = it + 3;
145 base::debug::Alias(&o);
146 });
147
148 it++; // At [2], in bounds.
149 ++it; // At [3], in bounds (at end).
150 EXPECT_CHECK_DEATH({
151 ++it;
152 base::debug::Alias(&it);
153 });
154 EXPECT_CHECK_DEATH({
155 it++;
156 base::debug::Alias(&it);
157 });
158
159 it -= 3; // At [0], in bounds.
160 EXPECT_CHECK_DEATH({
161 --it;
162 base::debug::Alias(&it);
163 });
164 EXPECT_CHECK_DEATH({
165 it--;
166 base::debug::Alias(&it);
167 });
168 }
169
170 } // namespace base
171
172 namespace {
173
174 // Helper template that wraps an iterator and disables its dereference and
175 // increment operations.
176 template <typename Iterator>
177 struct DisableDerefAndIncr : Iterator {
178 using Iterator::Iterator;
179
180 // NOLINTNEXTLINE(google-explicit-constructor)
DisableDerefAndIncr__anon9a44f86c0111::DisableDerefAndIncr181 constexpr DisableDerefAndIncr(const Iterator& iter) : Iterator(iter) {}
182
183 void operator*() = delete;
184 void operator++() = delete;
185 void operator++(int) = delete;
186 };
187
188 } // namespace
189
190 // Inherit `pointer_traits` specialization from the base class.
191 template <typename Iter>
192 struct std::pointer_traits<DisableDerefAndIncr<Iter>>
193 : ::std::pointer_traits<Iter> {};
194
195 namespace base {
196
197 // Tests that using std::copy with CheckedContiguousIterator<int> results in an
198 // optimized code-path that does not invoke the iterator's dereference and
199 // increment operations, as expected in libc++. This fails to compile if
200 // std::copy is not optimized.
201 // NOTE: This test relies on implementation details of the STL and thus might
202 // break in the future during a libc++ roll. If this does happen, please reach
203 // out to memory-safety-dev@chromium.org to reevaluate whether this test will
204 // still be needed.
205 #if defined(_LIBCPP_VERSION)
TEST(CheckedContiguousIterator,OptimizedCopy)206 TEST(CheckedContiguousIterator, OptimizedCopy) {
207 using Iter = DisableDerefAndIncr<CheckedContiguousIterator<int>>;
208
209 int arr_in[5] = {1, 2, 3, 4, 5};
210 int arr_out[5];
211
212 Iter in_begin = MakeIter(arr_in, 0u);
213 Iter in_end = MakeIter(arr_in, 5u);
214 Iter out_begin = MakeIter(arr_out, 0u);
215 Iter out_end = std::copy(in_begin, in_end, out_begin);
216 EXPECT_EQ(out_end, out_begin + (in_end - in_begin));
217
218 EXPECT_TRUE(ranges::equal(arr_in, arr_out));
219 }
220 #endif // defined(_LIBCPP_VERSION)
221
222 } // namespace base
223