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 "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 56 constexpr bool isSequential(ContainerType CT) { 57 return CT >= CT_Vector && CT <= CT_ForwardList; 58 } 59 60 constexpr bool isAssociative(ContainerType CT) { 61 return CT >= CT_Map && CT <= CT_MultiSet; 62 } 63 64 constexpr bool isUnordered(ContainerType CT) { 65 return CT >= CT_UnorderedMap && CT <= CT_UnorderedMultiSet; 66 } 67 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 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 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