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 493