test/support/container_test_types.h

   1 //===----------------------------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is dual licensed under the MIT and the University of Illinois Open
   6 // Source Licenses. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 #ifndef SUPPORT_CONTAINER_TEST_TYPES_H
  10 #define SUPPORT_CONTAINER_TEST_TYPES_H
  11
  12 // container_test_types.h - A set of types used for testing STL containers.
  13 // The types container within this header are used to test the requirements in
  14 // [container.requirements.general]. The header is made up of 3 main components:
  15 //
  16 // * test-types: 'CopyInsertable', 'MoveInsertable' and 'EmplaceConstructible' -
  17 //    These test types are used to test the container requirements of the same
  18 //    name. These test types use the global 'AllocatorConstructController' to
  19 //    assert that they are only constructed by the containers allocator.
  20 //
  21 // * test-allocator: 'ContainerTestAllocator' - This test allocator is used to
  22 //    test the portions of [container.requirements.general] that pertain to the
  23 //    containers allocator. The three primary jobs of the test allocator are:
  24 //      1. Enforce that 'a.construct(...)' and 'a.destroy(...)' are only ever
  25 //         instantiated for 'Container::value_type'.
  26 //      2. Provide a mechanism of checking calls to 'a.construct(Args...)'.
  27 //         Including controlling when and with what types 'a.construct(...)'
  28 //         may be called with.
  29 //      3. Support the test types internals by controlling the global
  30 //        'AllocatorConstructController' object.
  31 //
  32 // * 'AllocatorConstructController' - This type defines an interface for testing
  33 //   the construction of types using an allocator. This type is used to communicate
  34 //   between the test author, the containers allocator, and the types
  35 //   being constructed by the container.
  36 //   The controller's primary functions are:
  37 //     1. Allow calls to 'a.construct(p, args...)' to be checked by a test.
  38 //        The test uses 'cc->expect<Args...>()' to specify that the allocator
  39 //        should expect one call to 'a.construct' with the specified argument
  40 //        types.
  41 //     2. Controlling the value of 'cc->isInAllocatorConstruct()' within the
  42 //        'construct' method. The test-types use this value to assert that
  43 //         they are being constructed by the allocator.
  44 //
  45 //   'AllocatorConstructController' enforces the Singleton pattern since the
  46 //    test-types, test-allocator and test need to share the same controller
  47 //    object. A pointer to the global controller is returned by
  48 //   'getConstructController()'.
  49 //
  50 //----------------------------------------------------------------------------
  51 /*
  52  * Usage: The following example checks that 'unordered_map::emplace(Args&&...)'
  53  *        with 'Args = [CopyInsertable<1> const&, CopyInsertible<2>&&]'
  54  *        calls 'alloc.construct(value_type*, Args&&...)' with the same types.
  55  *
  56  * // Typedefs for container
  57  * using Key = CopyInsertible<1>;
  58  * using Value = CopyInsertible<2>;
  59  * using ValueTp = std::pair<const Key, Value>;
  60  * using Alloc = ContainerTestAllocator<ValueTp, ValueTp>;
  61  * using Map = std::unordered_map<Key, Value, std::hash<Key>, std::equal_to<Key>, Alloc>;
  62  *
  63  * // Get the global controller, reset it, and construct an allocator with
  64  * // the controller.
  65  * ConstructController* cc = getConstructController();
  66  * cc->reset();
  67  *
  68  * // Create a Map and a Key and Value to insert. Note that the test-allocator
  69  * // does not need to be given 'cc'.
  70  * Map m;
  71  * const Key k(1);
  72  * Value v(1);
  73  *
  74  * // Tell the controller to expect a construction from the specified types.
  75  * cc->expect<Key const&, Value&&>();
  76  *
  77  * // Emplace the objects into the container. 'Alloc.construct(p, UArgs...)'
  78  * // will assert 'cc->check<UArgs&&>()' is true which will consume
  79  * // the call to 'cc->expect<...>()'.
  80  * m.emplace(k, std::move(v));
  81  *
  82  * // Assert that the "expect" was consumed by a matching "check" call within
  83  * // Alloc.
  84  * assert(!cc->unexpected());
  85  *
  86  */
  87
  88 #include <functional>
  89 #include <cassert>
  90
  91 #include "test_macros.h"
  92
  93 #if TEST_STD_VER < 11
  94 #error This header requires C++11 or greater
  95 #endif
  96
  97 namespace detail {
  98 // TypeID - Represent a unique identifier for a type. TypeID allows equality
  99 // comparisons between different types.
 100 struct TypeID {
 101   friend bool operator==(TypeID const& LHS, TypeID const& RHS)
 102   {return LHS.m_id == RHS.m_id; }
 103   friend bool operator!=(TypeID const& LHS, TypeID const& RHS)
 104   {return LHS.m_id != RHS.m_id; }
 105 private:
 106   explicit constexpr TypeID(const int* xid) : m_id(xid) {}
 107   const int* const m_id;
 108   template <class T> friend class TypeInfo;
 109 };
 110
 111 // TypeInfo - Represent information for the specified type 'T', including a
 112 // unique TypeID.
 113 template <class T>
 114 class TypeInfo {
 115 public:
 116   typedef T value_type;
 117   typedef TypeID ID;
 118   static  ID const& GetID() { static ID id(&dummy_addr); return id; }
 119
 120 private:
 121   static const int dummy_addr;
 122 };
 123
 124 template <class L, class R>
 125 inline bool operator==(TypeInfo<L> const&, TypeInfo<R> const&)
 126 { return std::is_same<L, R>::value; }
 127
 128 template <class L, class R>
 129 inline bool operator!=(TypeInfo<L> const& lhs, TypeInfo<R> const& rhs)
 130 { return !(lhs == rhs); }
 131
 132 template <class T>
 133 const int TypeInfo<T>::dummy_addr = 42;
 134
 135 // makeTypeID - Return the TypeID for the specified type 'T'.
 136 template <class T>
 137 inline constexpr TypeID const& makeTypeID() { return TypeInfo<T>::GetID(); }
 138
 139 template <class ...Args>
 140 struct ArgumentListID {};
 141
 142 // makeArgumentID - Create and return a unique identifier for a given set
 143 // of arguments.
 144 template <class ...Args>
 145 inline constexpr TypeID const& makeArgumentID() {
 146   return makeTypeID<ArgumentListID<Args...>>();
 147 }
 148
 149 } // namespace detail
 150
 151 //===----------------------------------------------------------------------===//
 152 //                        AllocatorConstructController
 153 //===----------------------------------------------------------------------===//
 154
 155 struct AllocatorConstructController {
 156   const detail::TypeID* m_expected_args;
 157   bool m_allow_constructions;
 158   bool m_allow_unchecked;
 159   int m_expected_count;
 160
 161   void clear() {
 162     m_expected_args = nullptr;
 163     m_expected_count = -1;
 164   }
 165
 166   // Check for and consume an expected construction added by 'expect'.
 167   // Return true if the construction was expected and false otherwise.
 168   // This should only be called by 'Allocator.construct'.
 169   bool check(detail::TypeID const& tid) {
 170     if (!m_expected_args)
 171       assert(m_allow_unchecked);
 172     bool res = *m_expected_args == tid;
 173     if (m_expected_count == -1 || --m_expected_count == -1)
 174       m_expected_args = nullptr;
 175     return res;
 176   }
 177
 178   // Return true iff there is an unchecked construction expression.
 179   bool unchecked() {
 180     return m_expected_args != nullptr;
 181   }
 182
 183   // Expect a call to Allocator::construct with Args that match 'tid'.
 184   void expect(detail::TypeID const& tid) {
 185     assert(!unchecked());
 186     m_expected_args = &tid;
 187   }
 188
 189   template <class ...Args>
 190   void expect(int times = 1) {
 191     assert(!unchecked());
 192     assert(times > 0);
 193     m_expected_count = times - 1;
 194     m_expected_args = &detail::makeArgumentID<Args...>();
 195   }
 196   template <class ...Args>
 197   bool check() {
 198     return check(detail::makeArgumentID<Args...>());
 199   }
 200
 201
 202   // Return true iff the program is currently within a call to "Allocator::construct"
 203   bool isInAllocatorConstruct() const {
 204     return m_allow_constructions;
 205   }
 206
 207   void inAllocatorConstruct(bool value = true) {
 208     m_allow_constructions = value;
 209   }
 210
 211   void allowUnchecked(bool value = true) {
 212     m_allow_unchecked = value;
 213   }
 214
 215   void reset() {
 216     m_allow_constructions = false;
 217     m_expected_args = nullptr;
 218     m_allow_unchecked = false;
 219     m_expected_count = -1;
 220   }
 221
 222 private:
 223   friend AllocatorConstructController* getConstructController();
 224   AllocatorConstructController()  { reset(); }
 225   AllocatorConstructController(AllocatorConstructController const&);
 226   AllocatorConstructController& operator=(AllocatorConstructController const&);
 227 };
 228
 229 typedef AllocatorConstructController ConstructController;
 230
 231 // getConstructController - Return the global allocator construction controller.
 232 inline ConstructController* getConstructController() {
 233   static ConstructController c;
 234   return &c;
 235 }
 236
 237 //===----------------------------------------------------------------------===//
 238 //                       ContainerTestAllocator
 239 //===----------------------------------------------------------------------===//
 240
 241 // ContainerTestAllocator - A STL allocator type that only allows 'construct'
 242 // and 'destroy' to be called for 'AllowConstructT' types. ContainerTestAllocator
 243 // uses the 'AllocatorConstructionController' interface.
 244 template <class T, class AllowConstructT>
 245 class ContainerTestAllocator
 246 {
 247   struct InAllocatorConstructGuard {
 248     ConstructController *m_cc;
 249     bool m_old;
 250     InAllocatorConstructGuard(ConstructController* cc) : m_cc(cc) {
 251       if (m_cc) {
 252         m_old = m_cc->isInAllocatorConstruct();
 253         m_cc->inAllocatorConstruct(true);
 254       }
 255     }
 256     ~InAllocatorConstructGuard() {
 257       if (m_cc) m_cc->inAllocatorConstruct(m_old);
 258     }
 259   private:
 260     InAllocatorConstructGuard(InAllocatorConstructGuard const&);
 261     InAllocatorConstructGuard& operator=(InAllocatorConstructGuard const&);
 262   };
 263
 264 public:
 265     typedef T value_type;
 266
 267     int construct_called;
 268     int destroy_called;
 269     ConstructController* controller;
 270
 271     ContainerTestAllocator() TEST_NOEXCEPT
 272         : controller(getConstructController()) {}
 273
 274     explicit ContainerTestAllocator(ConstructController* c)
 275        : controller(c)
 276     {}
 277
 278     template <class U>
 279     ContainerTestAllocator(ContainerTestAllocator<U, AllowConstructT> other) TEST_NOEXCEPT
 280       : controller(other.controller)
 281     {}
 282
 283     T* allocate(std::size_t n)
 284     {
 285         return static_cast<T*>(::operator new(n*sizeof(T)));
 286     }
 287
 288     void deallocate(T* p, std::size_t)
 289     {
 290         return ::operator delete(static_cast<void*>(p));
 291     }
 292
 293     template <class Up, class ...Args>
 294     void construct(Up* p, Args&&... args) {
 295       static_assert((std::is_same<Up, AllowConstructT>::value),
 296                     "Only allowed to construct Up");
 297       assert(controller->check<Args&&...>());
 298       {
 299         InAllocatorConstructGuard g(controller);
 300         ::new ((void*)p) Up(std::forward<Args>(args)...);
 301       }
 302     }
 303
 304     template <class Up>
 305     void destroy(Up* p) {
 306       static_assert((std::is_same<Up, AllowConstructT>::value),
 307                     "Only allowed to destroy Up");
 308       {
 309         InAllocatorConstructGuard g(controller);
 310         p->~Up();
 311       }
 312     }
 313
 314     friend bool operator==(ContainerTestAllocator, ContainerTestAllocator) {return true;}
 315     friend bool operator!=(ContainerTestAllocator x, ContainerTestAllocator y) {return !(x == y);}
 316 };
 317
 318
 319 namespace test_detail {
 320 typedef ContainerTestAllocator<int, int> A1;
 321 typedef std::allocator_traits<A1> A1T;
 322 typedef ContainerTestAllocator<float, int> A2;
 323 typedef std::allocator_traits<A2> A2T;
 324
 325 static_assert(std::is_same<A1T::rebind_traits<float>, A2T>::value, "");
 326 static_assert(std::is_same<A2T::rebind_traits<int>, A1T>::value, "");
 327 } // end namespace test_detail
 328
 329 //===----------------------------------------------------------------------===//
 330 //  'CopyInsertable', 'MoveInsertable' and 'EmplaceConstructible' test types
 331 //===----------------------------------------------------------------------===//
 332
 333 template <int Dummy = 0>
 334 struct CopyInsertable {
 335   int data;
 336   mutable bool copied_once;
 337   bool constructed_under_allocator;
 338
 339   explicit CopyInsertable(int val) : data(val), copied_once(false),
 340                                      constructed_under_allocator(false) {
 341     if (getConstructController()->isInAllocatorConstruct()) {
 342       copied_once = true;
 343       constructed_under_allocator = true;
 344     }
 345   }
 346
 347   CopyInsertable() : data(0), copied_once(false), constructed_under_allocator(true)
 348   {
 349     assert(getConstructController()->isInAllocatorConstruct());
 350   }
 351
 352   CopyInsertable(CopyInsertable const& other) : data(other.data),
 353                                                 copied_once(true),
 354                                                 constructed_under_allocator(true) {
 355     assert(getConstructController()->isInAllocatorConstruct());
 356     assert(other.copied_once == false);
 357     other.copied_once = true;
 358   }
 359
 360   CopyInsertable(CopyInsertable& other) : data(other.data), copied_once(true),
 361                                           constructed_under_allocator(true) {
 362     assert(getConstructController()->isInAllocatorConstruct());
 363     assert(other.copied_once == false);
 364     other.copied_once = true;
 365   }
 366
 367   CopyInsertable(CopyInsertable&& other) : CopyInsertable(other) {}
 368
 369   // Forgive pair for not downcasting this to an lvalue in its constructors.
 370   CopyInsertable(CopyInsertable const && other) : CopyInsertable(other) {}
 371
 372
 373   template <class ...Args>
 374   CopyInsertable(Args&&...) {
 375     assert(false);
 376   }
 377
 378   ~CopyInsertable() {
 379     assert(constructed_under_allocator == getConstructController()->isInAllocatorConstruct());
 380   }
 381
 382   void reset(int value) {
 383     data = value;
 384     copied_once = false;
 385     constructed_under_allocator = false;
 386   }
 387 };
 388
 389 template <int ID>
 390 bool operator==(CopyInsertable<ID> const& L, CopyInsertable<ID> const& R) {
 391   return L.data == R.data;
 392 }
 393
 394
 395 template <int ID>
 396 bool operator!=(CopyInsertable<ID> const& L, CopyInsertable<ID> const& R) {
 397   return L.data != R.data;
 398 }
 399
 400 template <int ID>
 401 bool operator <(CopyInsertable<ID> const& L, CopyInsertable<ID> const& R) {
 402   return L.data < R.data;
 403 }
 404
 405
 406 #ifdef _LIBCPP_BEGIN_NAMESPACE_STD
 407 _LIBCPP_BEGIN_NAMESPACE_STD
 408 #else
 409 namespace std {
 410 #endif
 411   template <int ID>
 412   struct hash< ::CopyInsertable<ID> > {
 413     typedef ::CopyInsertable<ID> argument_type;
 414     typedef size_t result_type;
 415
 416     size_t operator()(argument_type const& arg) const {
 417       return arg.data;
 418     }
 419   };
 420
 421   template <class _Key, class _Value, class _Less, class _Alloc>
 422   class map;
 423   template <class _Key, class _Value, class _Less, class _Alloc>
 424   class multimap;
 425   template <class _Value, class _Less, class _Alloc>
 426   class set;
 427   template <class _Value, class _Less, class _Alloc>
 428   class multiset;
 429   template <class _Key, class _Value, class _Hash, class _Equals, class _Alloc>
 430   class unordered_map;
 431   template <class _Key, class _Value, class _Hash, class _Equals, class _Alloc>
 432   class unordered_multimap;
 433   template <class _Value, class _Hash, class _Equals, class _Alloc>
 434   class unordered_set;
 435   template <class _Value, class _Hash, class _Equals, class _Alloc>
 436   class unordered_multiset;
 437
 438 #ifdef _LIBCPP_END_NAMESPACE_STD
 439 _LIBCPP_END_NAMESPACE_STD
 440 #else
 441 } // end namespace std
 442 #endif
 443
 444 // TCT - Test container type
 445 namespace TCT {
 446
 447 template <class Key = CopyInsertable<1>, class Value = CopyInsertable<2>,
 448           class ValueTp = std::pair<const Key, Value> >
 449 using unordered_map =
 450       std::unordered_map<Key, Value, std::hash<Key>, std::equal_to<Key>,
 451                               ContainerTestAllocator<ValueTp, ValueTp> >;
 452
 453 template <class Key = CopyInsertable<1>, class Value = CopyInsertable<2>,
 454           class ValueTp = std::pair<const Key, Value> >
 455 using map =
 456       std::map<Key, Value, std::less<Key>,
 457                               ContainerTestAllocator<ValueTp, ValueTp> >;
 458
 459 template <class Key = CopyInsertable<1>, class Value = CopyInsertable<2>,
 460           class ValueTp = std::pair<const Key, Value> >
 461 using unordered_multimap =
 462       std::unordered_multimap<Key, Value, std::hash<Key>, std::equal_to<Key>,
 463                                    ContainerTestAllocator<ValueTp, ValueTp> >;
 464
 465 template <class Key = CopyInsertable<1>, class Value = CopyInsertable<2>,
 466           class ValueTp = std::pair<const Key, Value> >
 467 using multimap =
 468       std::multimap<Key, Value, std::less<Key>,
 469                               ContainerTestAllocator<ValueTp, ValueTp> >;
 470
 471 template <class Value = CopyInsertable<1> >
 472 using unordered_set =
 473   std::unordered_set<Value, std::hash<Value>, std::equal_to<Value>,
 474                                ContainerTestAllocator<Value, Value> >;
 475
 476 template <class Value = CopyInsertable<1> >
 477 using set =
 478     std::set<Value, std::less<Value>, ContainerTestAllocator<Value, Value> >;
 479
 480 template <class Value = CopyInsertable<1> >
 481 using unordered_multiset =
 482     std::unordered_multiset<Value, std::hash<Value>, std::equal_to<Value>,
 483                                     ContainerTestAllocator<Value, Value> >;
 484
 485 template <class Value = CopyInsertable<1> >
 486 using multiset =
 487     std::multiset<Value, std::less<Value>, ContainerTestAllocator<Value, Value> >;
 488
 489 } // end namespace TCT
 490
 491
 492 #endif // SUPPORT_CONTAINER_TEST_TYPES_H