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 // REQUIRES: has-unix-headers
10 // UNSUPPORTED: !libcpp-has-legacy-debug-mode, c++03, c++11, c++14
11
12 // test container debugging
13
14 #include <forward_list>
15 #include <list>
16 #include <vector>
17 #include <deque>
18 #include "check_assertion.h"
19 #include "container_debug_tests.h"
20 #include "test_macros.h"
21
22 using namespace IteratorDebugChecks;
23
24 template <class Container, ContainerType CT>
25 struct SequenceContainerChecks : BasicContainerChecks<Container, CT> {
26 using Base = BasicContainerChecks<Container, CT>;
27 using value_type = typename Container::value_type;
28 using allocator_type = typename Container::allocator_type;
29 using iterator = typename Container::iterator;
30 using const_iterator = typename Container::const_iterator;
31
32 using Base::makeContainer;
33 using Base::makeValueType;
34 public:
runSequenceContainerChecks35 static void run() {
36 Base::run();
37 SanityTest();
38 FrontOnEmptyContainer();
39
40 if constexpr(CT != CT_ForwardList) {
41 AssignInvalidates();
42 BackOnEmptyContainer();
43 InsertIterValue();
44 InsertIterSizeValue();
45 InsertIterIterIter();
46 EmplaceIterValue();
47 EraseIterIter();
48 }
49 else {
50 SpliceFirstElemAfter();
51 }
52 if constexpr (CT == CT_Vector || CT == CT_Deque || CT == CT_List) {
53 PopBack();
54 }
55 if constexpr (CT == CT_List || CT == CT_Deque) {
56 PopFront(); // FIXME: Run with forward list as well
57 }
58 if constexpr (CT == CT_List || CT == CT_ForwardList) {
59 RemoveFirstElem();
60 }
61 if constexpr (CT == CT_List) {
62 SpliceFirstElem();
63 SpliceSameContainer();
64 }
65 }
66
67 private:
SanityTestSequenceContainerChecks68 static void SanityTest() {
69 // sanity test
70 Container C = {1, 1, 1, 1};
71 ::DoNotOptimize(&C);
72 }
73
RemoveFirstElemSequenceContainerChecks74 static void RemoveFirstElem() {
75 // See llvm.org/PR35564
76 // remove(<first-elem>)
77 {
78 Container C = makeContainer(1);
79 auto FirstVal = *(C.begin());
80 C.remove(FirstVal);
81 assert(C.empty());
82 }
83 {
84 Container C = {1, 1, 1, 1};
85 auto FirstVal = *(C.begin());
86 C.remove(FirstVal);
87 assert(C.empty());
88 }
89 }
90
SpliceFirstElemSequenceContainerChecks91 static void SpliceFirstElem() {
92 // See llvm.org/PR35564
93 // splice(<first-elem>)
94 {
95 Container C = makeContainer(1);
96 Container C2;
97 C2.splice(C2.end(), C, C.begin(), ++C.begin());
98 }
99 {
100 Container C = makeContainer(1);
101 Container C2;
102 C2.splice(C2.end(), C, C.begin());
103 }
104 }
105
SpliceSameContainerSequenceContainerChecks106 static void SpliceSameContainer() {
107 // splice(<same-container>)
108 Container C = {1, 1};
109 C.splice(C.end(), C, C.begin());
110 }
111
SpliceFirstElemAfterSequenceContainerChecks112 static void SpliceFirstElemAfter() {
113 // See llvm.org/PR35564
114 // splice(<first-elem>)
115 {
116 Container C = makeContainer(1);
117 Container C2;
118 C2.splice_after(C2.begin(), C, C.begin(), ++C.begin());
119 }
120 {
121 Container C = makeContainer(1);
122 Container C2;
123 C2.splice_after(C2.begin(), C, C.begin());
124 }
125 }
126
AssignInvalidatesSequenceContainerChecks127 static void AssignInvalidates() {
128 // assign(Size, Value)
129 Container C(allocator_type{});
130 iterator it1, it2, it3;
131 auto reset = [&]() {
132 C = makeContainer(3);
133 it1 = C.begin();
134 it2 = ++C.begin();
135 it3 = C.end();
136 };
137 auto check = [&]() {
138 EXPECT_DEATH( C.erase(it1) );
139 EXPECT_DEATH( C.erase(it2) );
140 EXPECT_DEATH( C.erase(it3, C.end()) );
141 };
142 reset();
143 C.assign(2, makeValueType(4));
144 check();
145 reset();
146 // assign(Iter, Iter)
147 std::vector<value_type> V = {
148 makeValueType(1),
149 makeValueType(2),
150 makeValueType(3)
151 };
152 C.assign(V.begin(), V.end());
153 check();
154 reset();
155 // assign(initializer_list)
156 C.assign({makeValueType(1), makeValueType(2), makeValueType(3)});
157 check();
158 }
159
BackOnEmptyContainerSequenceContainerChecks160 static void BackOnEmptyContainer() {
161 // testing back on empty
162 Container C = makeContainer(1);
163 Container const& CC = C;
164 (void)C.back();
165 (void)CC.back();
166 C.clear();
167 EXPECT_DEATH( C.back() );
168 EXPECT_DEATH( CC.back() );
169 }
170
FrontOnEmptyContainerSequenceContainerChecks171 static void FrontOnEmptyContainer() {
172 // testing front on empty
173 Container C = makeContainer(1);
174 Container const& CC = C;
175 (void)C.front();
176 (void)CC.front();
177 C.clear();
178 EXPECT_DEATH( C.front() );
179 EXPECT_DEATH( CC.front() );
180 }
181
EraseIterIterSequenceContainerChecks182 static void EraseIterIter() {
183 // testing erase iter iter invalidation
184 Container C1 = makeContainer(3);
185 iterator it1 = C1.begin();
186 iterator it1_next = ++C1.begin();
187 iterator it1_after_next = ++C1.begin();
188 ++it1_after_next;
189 iterator it1_back = --C1.end();
190 assert(it1_next != it1_back);
191 if (CT == CT_Vector) {
192 EXPECT_DEATH( C1.erase(it1_next, it1) ); // bad range
193 }
194 C1.erase(it1, it1_after_next);
195 EXPECT_DEATH( C1.erase(it1) );
196 EXPECT_DEATH( C1.erase(it1_next) );
197 if (CT == CT_List) {
198 C1.erase(it1_back);
199 } else {
200 EXPECT_DEATH( C1.erase(it1_back) );
201 }
202 }
203
PopBackSequenceContainerChecks204 static void PopBack() {
205 // testing pop_back() invalidation
206 Container C1 = makeContainer(2);
207 iterator it1 = C1.end();
208 --it1;
209 C1.pop_back();
210 EXPECT_DEATH( C1.erase(it1) );
211 C1.erase(C1.begin());
212 assert(C1.size() == 0);
213 EXPECT_DEATH( C1.pop_back() );
214 }
215
PopFrontSequenceContainerChecks216 static void PopFront() {
217 // testing pop_front() invalidation
218 Container C1 = makeContainer(2);
219 iterator it1 = C1.begin();
220 C1.pop_front();
221 EXPECT_DEATH( C1.erase(it1) );
222 C1.erase(C1.begin());
223 assert(C1.size() == 0);
224 EXPECT_DEATH( C1.pop_front() );
225 }
226
InsertIterValueSequenceContainerChecks227 static void InsertIterValue() {
228 // testing insert(iter, value)
229 Container C1 = makeContainer(2);
230 iterator it1 = C1.begin();
231 iterator it1_next = it1;
232 ++it1_next;
233 Container C2 = C1;
234 const value_type value = makeValueType(3);
235 value_type rvalue = makeValueType(3);
236 EXPECT_DEATH( C2.insert(it1, value) ); // wrong container
237 EXPECT_DEATH( C2.insert(it1, std::move(rvalue)) ); // wrong container
238 C1.insert(it1_next, value);
239 if (CT == CT_List) {
240 C1.insert(it1_next, value);
241 C1.insert(it1, value);
242 C1.insert(it1_next, std::move(rvalue));
243 C1.insert(it1, std::move(rvalue));
244 } else {
245 EXPECT_DEATH( C1.insert(it1_next, value) ); // invalidated iterator
246 EXPECT_DEATH( C1.insert(it1, value) ); // invalidated iterator
247 EXPECT_DEATH( C1.insert(it1_next, std::move(rvalue)) ); // invalidated iterator
248 EXPECT_DEATH( C1.insert(it1, std::move(rvalue)) ); // invalidated iterator
249 }
250 }
251
EmplaceIterValueSequenceContainerChecks252 static void EmplaceIterValue() {
253 // testing emplace(iter, value)
254 Container C1 = makeContainer(2);
255 iterator it1 = C1.begin();
256 iterator it1_next = it1;
257 ++it1_next;
258 Container C2 = C1;
259 const value_type value = makeValueType(3);
260 EXPECT_DEATH( C2.emplace(it1, value) ); // wrong container
261 EXPECT_DEATH( C2.emplace(it1, makeValueType(4)) ); // wrong container
262 C1.emplace(it1_next, value);
263 if (CT == CT_List) {
264 C1.emplace(it1_next, value);
265 C1.emplace(it1, value);
266 } else {
267 EXPECT_DEATH( C1.emplace(it1_next, value) ); // invalidated iterator
268 EXPECT_DEATH( C1.emplace(it1, value) ); // invalidated iterator
269 }
270 }
271
InsertIterSizeValueSequenceContainerChecks272 static void InsertIterSizeValue() {
273 // testing insert(iter, size, value)
274 Container C1 = makeContainer(2);
275 iterator it1 = C1.begin();
276 iterator it1_next = it1;
277 ++it1_next;
278 Container C2 = C1;
279 const value_type value = makeValueType(3);
280 EXPECT_DEATH( C2.insert(it1, 1, value) ); // wrong container
281 C1.insert(it1_next, 2, value);
282 if (CT == CT_List) {
283 C1.insert(it1_next, 3, value);
284 C1.insert(it1, 1, value);
285 } else {
286 EXPECT_DEATH( C1.insert(it1_next, 1, value) ); // invalidated iterator
287 EXPECT_DEATH( C1.insert(it1, 1, value) ); // invalidated iterator
288 }
289 }
290
InsertIterIterIterSequenceContainerChecks291 static void InsertIterIterIter() {
292 // testing insert(iter, iter, iter)
293 Container C1 = makeContainer(2);
294 iterator it1 = C1.begin();
295 iterator it1_next = it1;
296 ++it1_next;
297 Container C2 = C1;
298 std::vector<value_type> V = {
299 makeValueType(1),
300 makeValueType(2),
301 makeValueType(3)
302 };
303 EXPECT_DEATH( C2.insert(it1, V.begin(), V.end()) ); // wrong container
304 C1.insert(it1_next, V.begin(), V.end());
305 if (CT == CT_List) {
306 C1.insert(it1_next, V.begin(), V.end());
307 C1.insert(it1, V.begin(), V.end());
308 } else {
309 EXPECT_DEATH( C1.insert(it1_next, V.begin(), V.end()) ); // invalidated iterator
310 EXPECT_DEATH( C1.insert(it1, V.begin(), V.end()) ); // invalidated iterator
311 }
312 }
313 };
314
main(int,char **)315 int main(int, char**)
316 {
317 using Alloc = test_allocator<int>;
318 {
319 SequenceContainerChecks<std::list<int, Alloc>, CT_List>::run();
320 SequenceContainerChecks<std::vector<int, Alloc>, CT_Vector>::run();
321 }
322 // FIXME these containers don't support iterator debugging
323 if ((false)) {
324 SequenceContainerChecks<
325 std::vector<bool, test_allocator<bool>>, CT_VectorBool>::run();
326 SequenceContainerChecks<
327 std::forward_list<int, Alloc>, CT_ForwardList>::run();
328 SequenceContainerChecks<
329 std::deque<int, Alloc>, CT_Deque>::run();
330 }
331
332 return 0;
333 }
334