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