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