libcxx/test/support/container_debug_tests.h

   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