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