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