350 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef TEST_SUPPORT_CONTAINER_DEBUG_TESTS_H10#define TEST_SUPPORT_CONTAINER_DEBUG_TESTS_H11 12#include "test_macros.h"13 14#ifndef _LIBCPP_VERSION15#error This header may only be used for libc++ tests16#endif17 18#if _LIBCPP_HARDENING_MODE != _LIBCPP_HARDENING_MODE_DEBUG19#error The library must be built with the debug mode enabled in order to use this header20#endif21 22#include <utility>23#include <cstddef>24#include <cstdlib>25#include <cassert>26 27#include "check_assertion.h"28#include "test_allocator.h"29 30// These test make use of 'if constexpr'.31#if TEST_STD_VER <= 1432#error This header may only be used in C++17 and greater33#endif34 35namespace IteratorDebugChecks {36 37enum 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_UnorderedMultiSet53};54 55constexpr bool isSequential(ContainerType CT) {56 return CT >= CT_Vector && CT <= CT_ForwardList;57}58 59constexpr bool isAssociative(ContainerType CT) {60 return CT >= CT_Map && CT <= CT_MultiSet;61}62 63constexpr bool isUnordered(ContainerType CT) {64 return CT >= CT_UnorderedMap && CT <= CT_UnorderedMultiSet;65}66 67constexpr bool isSet(ContainerType CT) {68 return CT == CT_Set69 || CT == CT_MultiSet70 || CT == CT_UnorderedSet71 || CT == CT_UnorderedMultiSet;72}73 74constexpr bool isMap(ContainerType CT) {75 return CT == CT_Map76 || CT == CT_MultiMap77 || CT == CT_UnorderedMap78 || CT == CT_UnorderedMultiMap;79}80 81constexpr bool isMulti(ContainerType CT) {82 return CT == CT_MultiMap83 || CT == CT_MultiSet84 || CT == CT_UnorderedMultiMap85 || CT == CT_UnorderedMultiSet;86}87 88template <class Container, class ValueType = typename Container::value_type>89struct 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 98template <class Container>99struct ContainerDebugHelper<Container, char> {100 static char makeValueType(int = 0, int = 0) {101 return 'A';102 }103};104 105template <class Container, class Key, class Value>106struct 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 118template <class Container, ContainerType CT,119 class Helper = ContainerDebugHelper<Container> >120struct 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 string162 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 tests185 template <class Iter>186 static void TestNullIterators() {187 // testing null iterator188 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 begin203 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 end217 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 iterator231 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 tests250 static void CopyInvalidatesIterators() {251 // copy invalidates iterators252 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 iterators272 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 invalidation288 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 container294 EXPECT_DEATH( C2.erase(C2.end()) ); // erase with end295 C1.erase(it1_next);296 EXPECT_DEATH( C1.erase(it1_next) ); // invalidated iterator297 C1.erase(it1);298 EXPECT_DEATH( C1.erase(it1) ); // invalidated iterator299 }300 301 static void EraseIterIter() {302 // testing erase iter iter invalidation303 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 container312 EXPECT_DEATH( C2.erase(it1, it2_next) ); // end from wrong container313 EXPECT_DEATH( C2.erase(it2, it1_next) ); // both from wrong container314 C2.erase(it2, it2_next);315 }316 317 // Allocator aware tests318 static void SwapInvalidatesIterators() {319 // testing swap invalidates iterators320 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 } else329 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 allocators336 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 IteratorDebugChecks348 349#endif // TEST_SUPPORT_CONTAINER_DEBUG_TESTS_H350