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 "test_macros.h"
  13
  14 #ifndef _LIBCPP_VERSION
  15 #error This header may only be used for libc++ tests
  16 #endif
  17
  18 #if _LIBCPP_HARDENING_MODE != _LIBCPP_HARDENING_MODE_DEBUG
  19 #error The library must be built with the debug mode enabled in order to use this header
  20 #endif
  21
  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 <= 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