1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #ifndef TEST_SUPPORT_CONTAINER_DEBUG_TESTS_H
10 #define TEST_SUPPORT_CONTAINER_DEBUG_TESTS_H
11
12 #include "test_macros.h"
13
14 #ifndef _LIBCPP_VERSION
15 #error This header may only be used for libc++ tests
16 #endif
17
18 #if _LIBCPP_HARDENING_MODE != _LIBCPP_HARDENING_MODE_DEBUG
19 #error The library must be built with the debug mode enabled in order to use this header
20 #endif
21
22 #include <utility>
23 #include <cstddef>
24 #include <cstdlib>
25 #include <cassert>
26
27 #include "check_assertion.h"
28 #include "test_allocator.h"
29
30 // These test make use of 'if constexpr'.
31 #if TEST_STD_VER <= 14
32 #error This header may only be used in C++17 and greater
33 #endif
34
35 namespace IteratorDebugChecks {
36
37 enum ContainerType {
38 CT_None,
39 CT_String,
40 CT_Vector,
41 CT_VectorBool,
42 CT_List,
43 CT_Deque,
44 CT_ForwardList,
45 CT_Map,
46 CT_Set,
47 CT_MultiMap,
48 CT_MultiSet,
49 CT_UnorderedMap,
50 CT_UnorderedSet,
51 CT_UnorderedMultiMap,
52 CT_UnorderedMultiSet
53 };
54
isSequential(ContainerType CT)55 constexpr bool isSequential(ContainerType CT) {
56 return CT >= CT_Vector && CT <= CT_ForwardList;
57 }
58
isAssociative(ContainerType CT)59 constexpr bool isAssociative(ContainerType CT) {
60 return CT >= CT_Map && CT <= CT_MultiSet;
61 }
62
isUnordered(ContainerType CT)63 constexpr bool isUnordered(ContainerType CT) {
64 return CT >= CT_UnorderedMap && CT <= CT_UnorderedMultiSet;
65 }
66
isSet(ContainerType CT)67 constexpr bool isSet(ContainerType CT) {
68 return CT == CT_Set
69 || CT == CT_MultiSet
70 || CT == CT_UnorderedSet
71 || CT == CT_UnorderedMultiSet;
72 }
73
isMap(ContainerType CT)74 constexpr bool isMap(ContainerType CT) {
75 return CT == CT_Map
76 || CT == CT_MultiMap
77 || CT == CT_UnorderedMap
78 || CT == CT_UnorderedMultiMap;
79 }
80
isMulti(ContainerType CT)81 constexpr bool isMulti(ContainerType CT) {
82 return CT == CT_MultiMap
83 || CT == CT_MultiSet
84 || CT == CT_UnorderedMultiMap
85 || CT == CT_UnorderedMultiSet;
86 }
87
88 template <class Container, class ValueType = typename Container::value_type>
89 struct ContainerDebugHelper {
90 static_assert(std::is_constructible<ValueType, int>::value,
91 "must be constructible from int");
92
93 static ValueType makeValueType(int val = 0, int = 0) {
94 return ValueType(val);
95 }
96 };
97
98 template <class Container>
99 struct ContainerDebugHelper<Container, char> {
100 static char makeValueType(int = 0, int = 0) {
101 return 'A';
102 }
103 };
104
105 template <class Container, class Key, class Value>
106 struct ContainerDebugHelper<Container, std::pair<const Key, Value> > {
107 using ValueType = std::pair<const Key, Value>;
108 static_assert(std::is_constructible<Key, int>::value,
109 "must be constructible from int");
110 static_assert(std::is_constructible<Value, int>::value,
111 "must be constructible from int");
112
113 static ValueType makeValueType(int key = 0, int val = 0) {
114 return ValueType(key, val);
115 }
116 };
117
118 template <class Container, ContainerType CT,
119 class Helper = ContainerDebugHelper<Container> >
120 struct BasicContainerChecks {
121 using value_type = typename Container::value_type;
122 using iterator = typename Container::iterator;
123 using const_iterator = typename Container::const_iterator;
124 using allocator_type = typename Container::allocator_type;
125 using traits = std::iterator_traits<iterator>;
126 using category = typename traits::iterator_category;
127
128 static_assert(std::is_same<test_allocator<value_type>, allocator_type>::value,
129 "the container must use a test allocator");
130
131 static constexpr bool IsBiDir =
132 std::is_convertible<category, std::bidirectional_iterator_tag>::value;
133
134 public:
135 static void run() {
136 run_iterator_tests();
137 run_container_tests();
138 run_allocator_aware_tests();
139 }
140
141 static void run_iterator_tests() {
142 TestNullIterators<iterator>();
143 TestNullIterators<const_iterator>();
144 if constexpr (IsBiDir) { DecrementBegin(); }
145 IncrementEnd();
146 DerefEndIterator();
147 }
148
149 static void run_container_tests() {
150 CopyInvalidatesIterators();
151 MoveInvalidatesIterators();
152 if constexpr (CT != CT_ForwardList) {
153 EraseIter();
154 EraseIterIter();
155 }
156 }
157
158 static void run_allocator_aware_tests() {
159 SwapNonEqualAllocators();
160 if constexpr (CT != CT_ForwardList ) {
161 // FIXME: This should work for both forward_list and string
162 SwapInvalidatesIterators();
163 }
164 }
165
166 static Container makeContainer(int size, allocator_type A = allocator_type()) {
167 Container C(A);
168 if constexpr (CT == CT_ForwardList) {
169 for (int i = 0; i < size; ++i)
170 C.insert_after(C.before_begin(), Helper::makeValueType(i));
171 } else {
172 for (int i = 0; i < size; ++i)
173 C.insert(C.end(), Helper::makeValueType(i));
174 assert(C.size() == static_cast<std::size_t>(size));
175 }
176 return C;
177 }
178
179 static value_type makeValueType(int value) {
180 return Helper::makeValueType(value);
181 }
182
183 private:
184 // Iterator tests
185 template <class Iter>
186 static void TestNullIterators() {
187 // testing null iterator
188 Iter it;
189 EXPECT_DEATH( ++it );
190 EXPECT_DEATH( it++ );
191 EXPECT_DEATH( *it );
192 if constexpr (CT != CT_VectorBool) {
193 EXPECT_DEATH( it.operator->() );
194 }
195 if constexpr (IsBiDir) {
196 EXPECT_DEATH( --it );
197 EXPECT_DEATH( it-- );
198 }
199 }
200
201 static void DecrementBegin() {
202 // testing decrement on begin
203 Container C = makeContainer(1);
204 iterator i = C.end();
205 const_iterator ci = C.cend();
206 --i;
207 --ci;
208 assert(i == C.begin());
209 EXPECT_DEATH( --i );
210 EXPECT_DEATH( i-- );
211 EXPECT_DEATH( --ci );
212 EXPECT_DEATH( ci-- );
213 }
214
215 static void IncrementEnd() {
216 // testing increment on end
217 Container C = makeContainer(1);
218 iterator i = C.begin();
219 const_iterator ci = C.begin();
220 ++i;
221 ++ci;
222 assert(i == C.end());
223 EXPECT_DEATH( ++i );
224 EXPECT_DEATH( i++ );
225 EXPECT_DEATH( ++ci );
226 EXPECT_DEATH( ci++ );
227 }
228
229 static void DerefEndIterator() {
230 // testing deref end iterator
231 Container C = makeContainer(1);
232 iterator i = C.begin();
233 const_iterator ci = C.cbegin();
234 (void)*i; (void)*ci;
235 if constexpr (CT != CT_VectorBool) {
236 i.operator->();
237 ci.operator->();
238 }
239 ++i; ++ci;
240 assert(i == C.end());
241 EXPECT_DEATH( *i );
242 EXPECT_DEATH( *ci );
243 if constexpr (CT != CT_VectorBool) {
244 EXPECT_DEATH( i.operator->() );
245 EXPECT_DEATH( ci.operator->() );
246 }
247 }
248
249 // Container tests
250 static void CopyInvalidatesIterators() {
251 // copy invalidates iterators
252 Container C1 = makeContainer(3);
253 iterator i = C1.begin();
254 Container C2 = C1;
255 if constexpr (CT == CT_ForwardList) {
256 iterator i_next = i;
257 ++i_next;
258 (void)*i_next;
259 EXPECT_DEATH( C2.erase_after(i) );
260 C1.erase_after(i);
261 EXPECT_DEATH( *i_next );
262 } else {
263 EXPECT_DEATH( C2.erase(i) );
264 (void)*i;
265 C1.erase(i);
266 EXPECT_DEATH( *i );
267 }
268 }
269
270 static void MoveInvalidatesIterators() {
271 // copy move invalidates iterators
272 Container C1 = makeContainer(3);
273 iterator i = C1.begin();
274 Container C2 = std::move(C1);
275 (void) *i;
276 if constexpr (CT == CT_ForwardList) {
277 EXPECT_DEATH( C1.erase_after(i) );
278 C2.erase_after(i);
279 } else {
280 EXPECT_DEATH( C1.erase(i) );
281 C2.erase(i);
282 EXPECT_DEATH(*i);
283 }
284 }
285
286 static void EraseIter() {
287 // testing erase invalidation
288 Container C1 = makeContainer(2);
289 iterator it1 = C1.begin();
290 iterator it1_next = it1;
291 ++it1_next;
292 Container C2 = C1;
293 EXPECT_DEATH( C2.erase(it1) ); // wrong container
294 EXPECT_DEATH( C2.erase(C2.end()) ); // erase with end
295 C1.erase(it1_next);
296 EXPECT_DEATH( C1.erase(it1_next) ); // invalidated iterator
297 C1.erase(it1);
298 EXPECT_DEATH( C1.erase(it1) ); // invalidated iterator
299 }
300
301 static void EraseIterIter() {
302 // testing erase iter iter invalidation
303 Container C1 = makeContainer(2);
304 iterator it1 = C1.begin();
305 iterator it1_next = it1;
306 ++it1_next;
307 Container C2 = C1;
308 iterator it2 = C2.begin();
309 iterator it2_next = it2;
310 ++it2_next;
311 EXPECT_DEATH( C2.erase(it1, it1_next) ); // begin from wrong container
312 EXPECT_DEATH( C2.erase(it1, it2_next) ); // end from wrong container
313 EXPECT_DEATH( C2.erase(it2, it1_next) ); // both from wrong container
314 C2.erase(it2, it2_next);
315 }
316
317 // Allocator aware tests
318 static void SwapInvalidatesIterators() {
319 // testing swap invalidates iterators
320 Container C1 = makeContainer(3);
321 Container C2 = makeContainer(3);
322 iterator it1 = C1.begin();
323 iterator it2 = C2.begin();
324 swap(C1, C2);
325 EXPECT_DEATH( C1.erase(it1) );
326 if (CT == CT_String) {
327 EXPECT_DEATH(C1.erase(it2));
328 } else
329 C1.erase(it2);
330 //C2.erase(it1);
331 EXPECT_DEATH( C1.erase(it1) );
332 }
333
334 static void SwapNonEqualAllocators() {
335 // testing swap with non-equal allocators
336 Container C1 = makeContainer(3, allocator_type(1));
337 Container C2 = makeContainer(1, allocator_type(2));
338 Container C3 = makeContainer(2, allocator_type(2));
339 swap(C2, C3);
340 EXPECT_DEATH( swap(C1, C2) );
341 }
342
343 private:
344 BasicContainerChecks() = delete;
345 };
346
347 } // namespace IteratorDebugChecks
348
349 #endif // TEST_SUPPORT_CONTAINER_DEBUG_TESTS_H
350