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