1 // -*- C++ -*- 2 3 // Copyright (C) 2009-2021 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the terms 7 // of the GNU General Public License as published by the Free Software 8 // Foundation; either version 3, or (at your option) any later 9 // version. 10 11 // This library is distributed in the hope that it will be useful, but 12 // WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 // General Public License for more details. 15 16 // You should have received a copy of the GNU General Public License along 17 // with this library; see the file COPYING3. If not see 18 // <http://www.gnu.org/licenses/>. 19 20 #ifndef _GLIBCXX_EXCEPTION_SAFETY_H 21 #define _GLIBCXX_EXCEPTION_SAFETY_H 22 23 #include <testsuite_container_traits.h> 24 #include <ext/throw_allocator.h> 25 #include <cstdlib> // getenv, atoi 26 #include <cstdio> // printf, fflush 27 28 // Container requirement testing. 29 namespace __gnu_test 30 { 31 // Base class for exception testing, contains utilities. 32 struct setup_base 33 { 34 typedef std::size_t size_type; 35 typedef std::uniform_int_distribution<size_type> distribution_type; 36 typedef std::mt19937 engine_type; 37 38 static engine_type get_enginesetup_base39 get_engine() 40 { 41 engine_type engine; 42 if (const char* v = std::getenv("GLIBCXX_SEED_TEST_RNG")) 43 { 44 // A single seed value is much smaller than the mt19937 state size, 45 // but we're not trying to be cryptographically secure here. 46 int s = std::atoi(v); 47 if (s == 0) 48 s = (int)std::random_device{}(); 49 std::printf("Using random seed %d\n", s); 50 std::fflush(stdout); 51 engine.seed((unsigned)s); 52 } 53 return engine; 54 } 55 56 // Return randomly generated integer on range [0, __max_size]. 57 static size_type generatesetup_base58 generate(size_type __max_size) 59 { 60 using param_type = typename distribution_type::param_type; 61 62 // Make the engine and distribution static... 63 static engine_type engine = get_engine(); 64 static distribution_type distribution; 65 return distribution(engine, param_type{0, __max_size}); 66 } 67 68 // Given an instantiating type, return a unique value. 69 template<typename _Tp> 70 struct generate_unique 71 { 72 typedef _Tp value_type; 73 value_typesetup_base::generate_unique74 operator value_type() 75 { 76 static value_type __ret; 77 ++__ret; 78 return __ret; 79 } 80 }; 81 82 // Partial specialization for pair. 83 template<typename _Tp1, typename _Tp2> 84 struct generate_unique<std::pair<const _Tp1, _Tp2>> 85 { 86 typedef _Tp1 first_type; 87 typedef _Tp2 second_type; 88 typedef std::pair<const _Tp1, _Tp2> pair_type; 89 90 operator pair_type() 91 { 92 static first_type _S_1; 93 static second_type _S_2; 94 ++_S_1; 95 ++_S_2; 96 return pair_type(_S_1, _S_2); 97 } 98 }; 99 100 // Partial specialization for throw_value 101 template<typename _Cond> 102 struct generate_unique<__gnu_cxx::throw_value_base<_Cond>> 103 { 104 typedef __gnu_cxx::throw_value_base<_Cond> value_type; 105 106 operator value_type() 107 { 108 static size_t _S_i(0); 109 return value_type(_S_i++); 110 } 111 }; 112 113 114 // Construct container of size n directly. _Tp == container type. 115 template<typename _Tp> 116 struct make_container_base 117 { 118 _Tp _M_container; 119 120 make_container_base() = default; 121 make_container_base(const size_type n): _M_container(n) { } 122 123 operator _Tp&() { return _M_container; } 124 }; 125 126 // Construct container of size n, via multiple insertions. For 127 // associated and unordered types, unique value_type elements are 128 // necessary. 129 template<typename _Tp, bool = traits<_Tp>::is_mapped::value> 130 struct make_insert_container_base 131 : public make_container_base<_Tp> 132 { 133 using make_container_base<_Tp>::_M_container; 134 typedef typename _Tp::value_type value_type; 135 136 make_insert_container_base(const size_type n) 137 { 138 for (size_type i = 0; i < n; ++i) 139 { 140 value_type v = generate_unique<value_type>(); 141 _M_container.insert(v); 142 } 143 assert(_M_container.size() == n); 144 } 145 }; 146 147 template<typename _Tp> 148 struct make_insert_container_base<_Tp, false> 149 : public make_container_base<_Tp> 150 { 151 using make_container_base<_Tp>::_M_container; 152 typedef typename _Tp::value_type value_type; 153 154 make_insert_container_base(const size_type n) 155 { 156 for (size_type i = 0; i < n; ++i) 157 { 158 value_type v = generate_unique<value_type>(); 159 _M_container.insert(_M_container.end(), v); 160 } 161 assert(_M_container.size() == n); 162 } 163 }; 164 165 template<typename _Tp, bool = traits<_Tp>::has_size_type_constructor::value> 166 struct make_container_n; 167 168 // Specialization for non-associative types that have a constructor with 169 // a size argument. 170 template<typename _Tp> 171 struct make_container_n<_Tp, true> 172 : public make_container_base<_Tp> 173 { 174 make_container_n(const size_type n) : make_container_base<_Tp>(n) { } 175 }; 176 177 template<typename _Tp> 178 struct make_container_n<_Tp, false> 179 : public make_insert_container_base<_Tp> 180 { 181 make_container_n(const size_type n) 182 : make_insert_container_base<_Tp>(n) { } 183 }; 184 185 186 // Randomly size and populate a given container reference. 187 // NB: Responsibility for turning off exceptions lies with caller. 188 template<typename _Tp, bool = traits<_Tp>::is_allocator_aware::value> 189 struct populate 190 { 191 typedef _Tp container_type; 192 typedef typename container_type::allocator_type allocator_type; 193 typedef typename container_type::value_type value_type; 194 195 populate(_Tp& __container) 196 { 197 const allocator_type a = __container.get_allocator(); 198 199 // Size test container. 200 const size_type max_elements = 100; 201 size_type n = generate(max_elements); 202 203 // Construct new container. 204 make_container_n<container_type> made(n); 205 container_type& tmp = made; 206 std::swap(tmp, __container); 207 } 208 }; 209 210 // Partial specialization, empty. 211 template<typename _Tp> 212 struct populate<_Tp, false> 213 { 214 populate(_Tp&) { } 215 }; 216 217 // Compare two containers for equivalence. 218 // Right now, that means size. 219 // Returns true if equal, throws if not. 220 template<typename _Tp> 221 static bool 222 compare(const _Tp& __control, const _Tp& __test) 223 { 224 // Make sure test container is in a consistent state, as 225 // compared to the control container. 226 // NB: Should be equivalent to __test != __control, but 227 // computed without equivalence operators 228 const size_type szt 229 = std::distance(__test.begin(), __test.end()); 230 const size_type szc 231 = std::distance(__control.begin(), __control.end()); 232 233 if (szt != szc) 234 throw std::logic_error( 235 "setup_base::compare containers size not equal"); 236 237 // Should test iterator validity before and after exception. 238 bool __equal_it = std::equal(__test.begin(), __test.end(), 239 __control.begin()); 240 241 if (!__equal_it) 242 throw std::logic_error( 243 "setup_base::compare containers iterators not equal"); 244 245 return true; 246 } 247 }; 248 249 250 // Containing structure holding functors. 251 struct functor_base : public setup_base 252 { 253 // Abstract the erase function. 254 template<typename _Tp> 255 struct erase_base 256 { 257 typedef typename _Tp::iterator iterator; 258 typedef typename _Tp::const_iterator const_iterator; 259 260 iterator (_Tp::* _F_erase_point)(const_iterator); 261 iterator (_Tp::* _F_erase_range)(const_iterator, const_iterator); 262 263 erase_base() 264 : _F_erase_point(&_Tp::erase), _F_erase_range(&_Tp::erase) { } 265 }; 266 267 #if _GLIBCXX_USE_CXX11_ABI == 0 || __cplusplus < 201103L 268 // Specialization, old C++03 signature. 269 template<typename _Tp1, typename _Tp2, typename _Tp3> 270 struct erase_base<std::basic_string<_Tp1, _Tp2, _Tp3>> 271 { 272 typedef std::basic_string<_Tp1, _Tp2, _Tp3> container_type; 273 typedef typename container_type::iterator iterator; 274 275 iterator (container_type::* _F_erase_point)(iterator); 276 iterator (container_type::* _F_erase_range)(iterator, iterator); 277 278 erase_base() 279 : _F_erase_point(&container_type::erase), 280 _F_erase_range(&container_type::erase) { } 281 }; 282 283 template<typename _Tp1, typename _Tp2, typename _Tp3> 284 struct erase_base<__gnu_debug::basic_string<_Tp1, _Tp2, _Tp3>> 285 { 286 typedef __gnu_debug::basic_string<_Tp1, _Tp2, _Tp3> container_type; 287 typedef typename container_type::iterator iterator; 288 289 iterator (container_type::* _F_erase_point)(iterator); 290 iterator (container_type::* _F_erase_range)(iterator, iterator); 291 292 erase_base() 293 : _F_erase_point(&container_type::erase), 294 _F_erase_range(&container_type::erase) { } 295 }; 296 #endif 297 298 // Specialization, as forward_list has erase_after. 299 template<typename _Tp1, typename _Tp2> 300 struct erase_base<std::forward_list<_Tp1, _Tp2>> 301 { 302 typedef std::forward_list<_Tp1, _Tp2> container_type; 303 typedef typename container_type::iterator iterator; 304 typedef typename container_type::const_iterator const_iterator; 305 306 iterator (container_type::* _F_erase_point)(const_iterator); 307 iterator (container_type::* _F_erase_range)(const_iterator, 308 const_iterator); 309 310 erase_base() 311 : _F_erase_point(&container_type::erase_after), 312 _F_erase_range(&container_type::erase_after) { } 313 }; 314 315 template<typename _Tp, 316 bool = traits<_Tp>::has_erase::value, 317 bool = traits<_Tp>::has_erase_after::value> 318 struct erase_point; 319 320 // Specialization for most containers. 321 template<typename _Tp> 322 struct erase_point<_Tp, true, false> : public erase_base<_Tp> 323 { 324 using erase_base<_Tp>::_F_erase_point; 325 326 void 327 operator()(_Tp& __container) 328 { 329 try 330 { 331 // NB: Should be equivalent to size() member function, but 332 // computed with begin() and end(). 333 const size_type sz = std::distance(__container.begin(), 334 __container.end()); 335 // Container::erase(pos) requires dereferenceable pos. 336 if (sz == 0) 337 throw std::logic_error("erase_point: empty container"); 338 339 // NB: Lowest common denominator: use forward iterator operations. 340 auto i = __container.begin(); 341 std::advance(i, generate(sz - 1)); 342 343 // Makes it easier to think of this as __container.erase(i) 344 (__container.*_F_erase_point)(i); 345 } 346 catch(const __gnu_cxx::forced_error&) 347 { throw; } 348 } 349 }; 350 351 // Specialization for forward_list. 352 template<typename _Tp> 353 struct erase_point<_Tp, false, true> : public erase_base<_Tp> 354 { 355 using erase_base<_Tp>::_F_erase_point; 356 357 void 358 operator()(_Tp& __container) 359 { 360 try 361 { 362 // NB: Should be equivalent to size() member function, but 363 // computed with begin() and end(). 364 const size_type sz = std::distance(__container.begin(), 365 __container.end()); 366 // forward_list::erase_after(pos) requires dereferenceable pos. 367 if (sz == 0) 368 throw std::logic_error("erase_point: empty container"); 369 370 // NB: Lowest common denominator: use forward iterator operations. 371 auto i = __container.before_begin(); 372 std::advance(i, generate(sz - 1)); 373 374 // Makes it easier to think of this as __container.erase_after(i) 375 (__container.*_F_erase_point)(i); 376 } 377 catch(const __gnu_cxx::forced_error&) 378 { throw; } 379 } 380 }; 381 382 // Specialization, empty. 383 template<typename _Tp> 384 struct erase_point<_Tp, false, false> 385 { 386 void 387 operator()(_Tp&) { } 388 }; 389 390 391 template<typename _Tp, 392 bool = traits<_Tp>::has_erase::value, 393 bool = traits<_Tp>::has_erase_after::value> 394 struct erase_range; 395 396 // Specialization for most containers. 397 template<typename _Tp> 398 struct erase_range<_Tp, true, false> : public erase_base<_Tp> 399 { 400 using erase_base<_Tp>::_F_erase_range; 401 402 void 403 operator()(_Tp& __container) 404 { 405 try 406 { 407 const size_type sz = std::distance(__container.begin(), 408 __container.end()); 409 size_type s1 = generate(sz); 410 size_type s2 = generate(sz); 411 auto i1 = __container.begin(); 412 auto i2 = __container.begin(); 413 std::advance(i1, std::min(s1, s2)); 414 std::advance(i2, std::max(s1, s2)); 415 416 // Makes it easier to think of this as __container.erase(i1, i2). 417 (__container.*_F_erase_range)(i1, i2); 418 } 419 catch(const __gnu_cxx::forced_error&) 420 { throw; } 421 } 422 }; 423 424 // Specialization for forward_list. 425 template<typename _Tp> 426 struct erase_range<_Tp, false, true> : public erase_base<_Tp> 427 { 428 using erase_base<_Tp>::_F_erase_range; 429 430 void 431 operator()(_Tp& __container) 432 { 433 try 434 { 435 const size_type sz = std::distance(__container.begin(), 436 __container.end()); 437 // forward_list::erase_after(pos, last) requires a pos != last 438 if (sz == 0) 439 return; // Caller doesn't check for this, not a logic error. 440 441 size_type s1 = generate(sz - 1); 442 size_type s2 = generate(sz - 1); 443 auto i1 = __container.before_begin(); 444 auto i2 = __container.before_begin(); 445 std::advance(i1, std::min(s1, s2)); 446 std::advance(i2, std::max(s1, s2) + 1); 447 448 // Makes it easier to think of this as 449 // __container.erase_after(i1, i2). 450 (__container.*_F_erase_range)(i1, i2); 451 } 452 catch(const __gnu_cxx::forced_error&) 453 { throw; } 454 } 455 }; 456 457 // Specialization, empty. 458 template<typename _Tp> 459 struct erase_range<_Tp, false, false> 460 { 461 void 462 operator()(_Tp&) { } 463 }; 464 465 466 template<typename _Tp, bool = traits<_Tp>::has_push_pop::value> 467 struct pop_front 468 { 469 void 470 operator()(_Tp& __container) 471 { 472 try 473 { 474 __container.pop_front(); 475 } 476 catch(const __gnu_cxx::forced_error&) 477 { throw; } 478 } 479 }; 480 481 // Specialization, empty. 482 template<typename _Tp> 483 struct pop_front<_Tp, false> 484 { 485 void 486 operator()(_Tp&) { } 487 }; 488 489 490 template<typename _Tp, bool = traits<_Tp>::has_push_pop::value 491 && traits<_Tp>::is_reversible::value> 492 struct pop_back 493 { 494 void 495 operator()(_Tp& __container) 496 { 497 try 498 { 499 __container.pop_back(); 500 } 501 catch(const __gnu_cxx::forced_error&) 502 { throw; } 503 } 504 }; 505 506 // Specialization, empty. 507 template<typename _Tp> 508 struct pop_back<_Tp, false> 509 { 510 void 511 operator()(_Tp&) { } 512 }; 513 514 515 template<typename _Tp, bool = traits<_Tp>::has_push_pop::value> 516 struct push_front 517 { 518 typedef _Tp container_type; 519 typedef typename container_type::value_type value_type; 520 521 void 522 operator()(_Tp& __test) 523 { 524 try 525 { 526 const value_type cv = generate_unique<value_type>(); 527 __test.push_front(cv); 528 } 529 catch(const __gnu_cxx::forced_error&) 530 { throw; } 531 } 532 533 // Assumes containers start out equivalent. 534 void 535 operator()(_Tp& __control, _Tp& __test) 536 { 537 try 538 { 539 const value_type cv = generate_unique<value_type>(); 540 __test.push_front(cv); 541 } 542 catch(const __gnu_cxx::forced_error&) 543 { throw; } 544 } 545 }; 546 547 // Specialization, empty. 548 template<typename _Tp> 549 struct push_front<_Tp, false> 550 { 551 void 552 operator()(_Tp&) { } 553 554 void 555 operator()(_Tp&, _Tp&) { } 556 }; 557 558 559 template<typename _Tp, bool = traits<_Tp>::has_push_pop::value 560 && traits<_Tp>::is_reversible::value> 561 struct push_back 562 { 563 typedef _Tp container_type; 564 typedef typename container_type::value_type value_type; 565 566 void 567 operator()(_Tp& __test) 568 { 569 try 570 { 571 const value_type cv = generate_unique<value_type>(); 572 __test.push_back(cv); 573 } 574 catch(const __gnu_cxx::forced_error&) 575 { throw; } 576 } 577 578 // Assumes containers start out equivalent. 579 void 580 operator()(_Tp& __control, _Tp& __test) 581 { 582 try 583 { 584 const value_type cv = generate_unique<value_type>(); 585 __test.push_back(cv); 586 } 587 catch(const __gnu_cxx::forced_error&) 588 { throw; } 589 } 590 }; 591 592 // Specialization, empty. 593 template<typename _Tp> 594 struct push_back<_Tp, false> 595 { 596 void 597 operator()(_Tp&) { } 598 599 void 600 operator()(_Tp&, _Tp&) { } 601 }; 602 603 template<typename _Tp, bool = traits<_Tp>::has_push_pop::value 604 && traits<_Tp>::has_emplace::value> 605 struct emplace_front 606 { 607 typedef _Tp container_type; 608 typedef typename container_type::value_type value_type; 609 610 void 611 operator()(_Tp& __test) 612 { 613 try 614 { 615 const value_type cv = generate_unique<value_type>(); 616 __test.emplace_front(cv); 617 } 618 catch(const __gnu_cxx::forced_error&) 619 { throw; } 620 } 621 622 // Assumes containers start out equivalent. 623 void 624 operator()(_Tp& __control, _Tp& __test) 625 { 626 try 627 { 628 const value_type cv = generate_unique<value_type>(); 629 __test.emplace_front(cv); 630 } 631 catch(const __gnu_cxx::forced_error&) 632 { throw; } 633 } 634 }; 635 636 // Specialization, empty. 637 template<typename _Tp> 638 struct emplace_front<_Tp, false> 639 { 640 void 641 operator()(_Tp&) { } 642 643 void 644 operator()(_Tp&, _Tp&) { } 645 }; 646 647 648 template<typename _Tp, bool = traits<_Tp>::has_push_pop::value 649 && traits<_Tp>::has_emplace::value 650 && traits<_Tp>::is_reversible::value> 651 struct emplace_back 652 { 653 typedef _Tp container_type; 654 typedef typename container_type::value_type value_type; 655 656 void 657 operator()(_Tp& __test) 658 { 659 try 660 { 661 const value_type cv = generate_unique<value_type>(); 662 __test.emplace_back(cv); 663 } 664 catch(const __gnu_cxx::forced_error&) 665 { throw; } 666 } 667 668 // Assumes containers start out equivalent. 669 void 670 operator()(_Tp& __control, _Tp& __test) 671 { 672 try 673 { 674 const value_type cv = generate_unique<value_type>(); 675 __test.push_back(cv); 676 } 677 catch(const __gnu_cxx::forced_error&) 678 { throw; } 679 } 680 }; 681 682 // Specialization, empty. 683 template<typename _Tp> 684 struct emplace_back<_Tp, false> 685 { 686 void 687 operator()(_Tp&) { } 688 689 void 690 operator()(_Tp&, _Tp&) { } 691 }; 692 693 694 // Abstract the insert function into two parts: 695 // 1, insert_base_functions == holds function pointer 696 // 2, insert_base == links function pointer to class insert method 697 template<typename _Tp> 698 struct insert_base 699 { 700 typedef typename _Tp::iterator iterator; 701 typedef typename _Tp::const_iterator const_iterator; 702 typedef typename _Tp::value_type value_type; 703 704 iterator (_Tp::* _F_insert_point)(const_iterator, const value_type&); 705 706 insert_base() : _F_insert_point(&_Tp::insert) { } 707 }; 708 709 // Specialization, old C++03 signature. 710 template<typename _Tp1, typename _Tp2, typename _Tp3> 711 struct insert_base<std::basic_string<_Tp1, _Tp2, _Tp3>> 712 { 713 typedef std::basic_string<_Tp1, _Tp2, _Tp3> container_type; 714 typedef typename container_type::iterator iterator; 715 typedef typename container_type::const_iterator const_iterator; 716 typedef typename container_type::value_type value_type; 717 718 #if _GLIBCXX_USE_CXX11_ABI == 0 || __cplusplus < 201103L 719 iterator (container_type::* _F_insert_point)(iterator, value_type); 720 #else 721 iterator (container_type::* _F_insert_point)(const_iterator, 722 value_type); 723 #endif 724 725 insert_base() : _F_insert_point(&container_type::insert) { } 726 }; 727 728 template<typename _Tp1, typename _Tp2, typename _Tp3> 729 struct insert_base<__gnu_debug::basic_string<_Tp1, _Tp2, _Tp3>> 730 { 731 typedef __gnu_debug::basic_string<_Tp1, _Tp2, _Tp3> container_type; 732 typedef typename container_type::iterator iterator; 733 typedef typename container_type::const_iterator const_iterator; 734 typedef typename container_type::value_type value_type; 735 736 #if _GLIBCXX_USE_CXX11_ABI == 0 || __cplusplus < 201103L 737 iterator (container_type::* _F_insert_point)(iterator, value_type); 738 #else 739 iterator (container_type::* _F_insert_point)(const_iterator, 740 value_type); 741 #endif 742 743 insert_base() : _F_insert_point(&container_type::insert) { } 744 }; 745 746 // Specialization, by value. 747 template<typename _Tp1, typename _Tp2, typename _Tp3, 748 template <typename, typename, typename> class _Tp4> 749 struct insert_base<__gnu_cxx::__versa_string<_Tp1, _Tp2, _Tp3, _Tp4>> 750 { 751 typedef __gnu_cxx::__versa_string<_Tp1, _Tp2, _Tp3, _Tp4> 752 container_type; 753 typedef typename container_type::iterator iterator; 754 typedef typename container_type::const_iterator const_iterator; 755 typedef typename container_type::value_type value_type; 756 757 iterator (container_type::* _F_insert_point)(const_iterator, 758 value_type); 759 760 insert_base() : _F_insert_point(&container_type::insert) { } 761 }; 762 763 // Specialization, as forward_list has insert_after. 764 template<typename _Tp1, typename _Tp2> 765 struct insert_base<std::forward_list<_Tp1, _Tp2>> 766 { 767 typedef std::forward_list<_Tp1, _Tp2> container_type; 768 typedef typename container_type::iterator iterator; 769 typedef typename container_type::const_iterator const_iterator; 770 typedef typename container_type::value_type value_type; 771 772 iterator (container_type::* _F_insert_point)(const_iterator, 773 const value_type&); 774 775 insert_base() : _F_insert_point(&container_type::insert_after) { } 776 }; 777 778 template<typename _Tp, bool = traits<_Tp>::has_insert::value, 779 bool = traits<_Tp>::has_insert_after::value> 780 struct insert_point; 781 782 // Specialization for most containers. 783 template<typename _Tp> 784 struct insert_point<_Tp, true, false> : public insert_base<_Tp> 785 { 786 typedef _Tp container_type; 787 typedef typename container_type::value_type value_type; 788 using insert_base<_Tp>::_F_insert_point; 789 790 void 791 operator()(_Tp& __test) 792 { 793 try 794 { 795 const value_type cv = generate_unique<value_type>(); 796 const size_type sz = std::distance(__test.begin(), __test.end()); 797 size_type s = generate(sz); 798 auto i = __test.begin(); 799 std::advance(i, s); 800 (__test.*_F_insert_point)(i, cv); 801 } 802 catch(const __gnu_cxx::forced_error&) 803 { throw; } 804 } 805 806 // Assumes containers start out equivalent. 807 void 808 operator()(_Tp& __control, _Tp& __test) 809 { 810 try 811 { 812 const value_type cv = generate_unique<value_type>(); 813 const size_type sz = std::distance(__test.begin(), __test.end()); 814 size_type s = generate(sz); 815 auto i = __test.begin(); 816 std::advance(i, s); 817 (__test.*_F_insert_point)(i, cv); 818 } 819 catch(const __gnu_cxx::forced_error&) 820 { throw; } 821 } 822 }; 823 824 // Specialization for forward_list. 825 template<typename _Tp> 826 struct insert_point<_Tp, false, true> : public insert_base<_Tp> 827 { 828 typedef _Tp container_type; 829 typedef typename container_type::value_type value_type; 830 using insert_base<_Tp>::_F_insert_point; 831 832 void 833 operator()(_Tp& __test) 834 { 835 try 836 { 837 const value_type cv = generate_unique<value_type>(); 838 const size_type sz = std::distance(__test.begin(), __test.end()); 839 size_type s = generate(sz); 840 auto i = __test.before_begin(); 841 std::advance(i, s); 842 (__test.*_F_insert_point)(i, cv); 843 } 844 catch(const __gnu_cxx::forced_error&) 845 { throw; } 846 } 847 848 // Assumes containers start out equivalent. 849 void 850 operator()(_Tp& __control, _Tp& __test) 851 { 852 try 853 { 854 const value_type cv = generate_unique<value_type>(); 855 const size_type sz = std::distance(__test.begin(), __test.end()); 856 size_type s = generate(sz); 857 auto i = __test.before_begin(); 858 std::advance(i, s); 859 (__test.*_F_insert_point)(i, cv); 860 } 861 catch(const __gnu_cxx::forced_error&) 862 { throw; } 863 } 864 }; 865 866 // Specialization, empty. 867 template<typename _Tp> 868 struct insert_point<_Tp, false, false> 869 { 870 void 871 operator()(_Tp&) { } 872 873 void 874 operator()(_Tp&, _Tp&) { } 875 }; 876 877 template<typename _Tp, bool = traits<_Tp>::has_emplace::value 878 && (traits<_Tp>::is_associative::value 879 || traits<_Tp>::is_unordered::value)> 880 struct emplace; 881 882 // Specialization for associative and unordered containers. 883 template<typename _Tp> 884 struct emplace<_Tp, true> 885 { 886 typedef _Tp container_type; 887 typedef typename container_type::value_type value_type; 888 typedef typename container_type::size_type size_type; 889 890 void 891 operator()(_Tp& __test) 892 { 893 try 894 { 895 const value_type cv = generate_unique<value_type>(); 896 __test.emplace(cv); 897 } 898 catch(const __gnu_cxx::forced_error&) 899 { throw; } 900 } 901 902 // Assumes containers start out equivalent. 903 void 904 operator()(_Tp& __control, _Tp& __test) 905 { 906 try 907 { 908 const value_type cv = generate_unique<value_type>(); 909 __test.emplace(cv); 910 } 911 catch(const __gnu_cxx::forced_error&) 912 { throw; } 913 } 914 }; 915 916 // Specialization, empty. 917 template<typename _Tp> 918 struct emplace<_Tp, false> 919 { 920 void 921 operator()(_Tp&) { } 922 923 void 924 operator()(_Tp&, _Tp&) { } 925 }; 926 927 template<typename _Tp, bool = traits<_Tp>::has_emplace::value, 928 bool = traits<_Tp>::is_associative::value 929 || traits<_Tp>::is_unordered::value, 930 bool = traits<_Tp>::has_insert_after::value> 931 struct emplace_point; 932 933 // Specialization for most containers. 934 template<typename _Tp> 935 struct emplace_point<_Tp, true, false, false> 936 { 937 typedef _Tp container_type; 938 typedef typename container_type::value_type value_type; 939 940 void 941 operator()(_Tp& __test) 942 { 943 try 944 { 945 const value_type cv = generate_unique<value_type>(); 946 const size_type sz = std::distance(__test.begin(), __test.end()); 947 size_type s = generate(sz); 948 auto i = __test.begin(); 949 std::advance(i, s); 950 __test.emplace(i, cv); 951 } 952 catch(const __gnu_cxx::forced_error&) 953 { throw; } 954 } 955 956 // Assumes containers start out equivalent. 957 void 958 operator()(_Tp& __control, _Tp& __test) 959 { 960 try 961 { 962 const value_type cv = generate_unique<value_type>(); 963 const size_type sz = std::distance(__test.begin(), __test.end()); 964 size_type s = generate(sz); 965 auto i = __test.begin(); 966 std::advance(i, s); 967 __test.emplace(i, cv); 968 } 969 catch(const __gnu_cxx::forced_error&) 970 { throw; } 971 } 972 }; 973 974 // Specialization for associative and unordered containers. 975 template<typename _Tp> 976 struct emplace_point<_Tp, true, true, false> 977 { 978 typedef _Tp container_type; 979 typedef typename container_type::value_type value_type; 980 981 void 982 operator()(_Tp& __test) 983 { 984 try 985 { 986 const value_type cv = generate_unique<value_type>(); 987 const size_type sz = std::distance(__test.begin(), __test.end()); 988 size_type s = generate(sz); 989 auto i = __test.begin(); 990 std::advance(i, s); 991 __test.emplace_hint(i, cv); 992 } 993 catch(const __gnu_cxx::forced_error&) 994 { throw; } 995 } 996 997 // Assumes containers start out equivalent. 998 void 999 operator()(_Tp& __control, _Tp& __test) 1000 { 1001 try 1002 { 1003 const value_type cv = generate_unique<value_type>(); 1004 const size_type sz = std::distance(__test.begin(), __test.end()); 1005 size_type s = generate(sz); 1006 auto i = __test.begin(); 1007 std::advance(i, s); 1008 __test.emplace_hint(i, cv); 1009 } 1010 catch(const __gnu_cxx::forced_error&) 1011 { throw; } 1012 } 1013 }; 1014 1015 // Specialization for forward_list. 1016 template<typename _Tp> 1017 struct emplace_point<_Tp, true, false, true> 1018 { 1019 typedef _Tp container_type; 1020 typedef typename container_type::value_type value_type; 1021 1022 void 1023 operator()(_Tp& __test) 1024 { 1025 try 1026 { 1027 const value_type cv = generate_unique<value_type>(); 1028 const size_type sz = std::distance(__test.begin(), __test.end()); 1029 size_type s = generate(sz); 1030 auto i = __test.before_begin(); 1031 std::advance(i, s); 1032 __test.emplace_after(i, cv); 1033 } 1034 catch(const __gnu_cxx::forced_error&) 1035 { throw; } 1036 } 1037 1038 // Assumes containers start out equivalent. 1039 void 1040 operator()(_Tp& __control, _Tp& __test) 1041 { 1042 try 1043 { 1044 const value_type cv = generate_unique<value_type>(); 1045 const size_type sz = std::distance(__test.begin(), __test.end()); 1046 size_type s = generate(sz); 1047 auto i = __test.before_begin(); 1048 std::advance(i, s); 1049 __test.emplace_after(i, cv); 1050 } 1051 catch(const __gnu_cxx::forced_error&) 1052 { throw; } 1053 } 1054 }; 1055 1056 // Specialization, empty. 1057 template<typename _Tp, bool is_associative_or_unordered, 1058 bool has_insert_after> 1059 struct emplace_point<_Tp, false, is_associative_or_unordered, 1060 has_insert_after> 1061 { 1062 void 1063 operator()(_Tp&) { } 1064 1065 void 1066 operator()(_Tp&, _Tp&) { } 1067 }; 1068 1069 template<typename _Tp, bool = traits<_Tp>::is_associative::value 1070 || traits<_Tp>::is_unordered::value> 1071 struct clear 1072 { 1073 void 1074 operator()(_Tp& __container) 1075 { 1076 try 1077 { 1078 __container.clear(); 1079 } 1080 catch(const __gnu_cxx::forced_error&) 1081 { throw; } 1082 } 1083 }; 1084 1085 // Specialization, empty. 1086 template<typename _Tp> 1087 struct clear<_Tp, false> 1088 { 1089 void 1090 operator()(_Tp&) { } 1091 }; 1092 1093 1094 template<typename _Tp, bool = traits<_Tp>::is_unordered::value> 1095 struct rehash 1096 { 1097 void 1098 operator()(_Tp& __test) 1099 { 1100 try 1101 { 1102 size_type s = generate(__test.bucket_count()); 1103 __test.rehash(s); 1104 } 1105 catch(const __gnu_cxx::forced_error&) 1106 { throw; } 1107 } 1108 1109 void 1110 operator()(_Tp& __control, _Tp& __test) 1111 { 1112 try 1113 { 1114 size_type s = generate(__test.bucket_count()); 1115 __test.rehash(s); 1116 } 1117 catch(const __gnu_cxx::forced_error&) 1118 { 1119 // Also check hash status. 1120 bool fail(false); 1121 if (__control.load_factor() != __test.load_factor()) 1122 fail = true; 1123 if (__control.max_load_factor() != __test.max_load_factor()) 1124 fail = true; 1125 if (__control.bucket_count() != __test.bucket_count()) 1126 fail = true; 1127 if (__control.max_bucket_count() != __test.max_bucket_count()) 1128 fail = true; 1129 1130 if (fail) 1131 { 1132 char buf[40]; 1133 std::string __s("setup_base::rehash " 1134 "containers not equal"); 1135 __s += "\n"; 1136 __s += "\n"; 1137 __s += "\t\t\tcontrol : test"; 1138 __s += "\n"; 1139 __s += "load_factor\t\t"; 1140 __builtin_sprintf(buf, "%lu", __control.load_factor()); 1141 __s += buf; 1142 __s += " : "; 1143 __builtin_sprintf(buf, "%lu", __test.load_factor()); 1144 __s += buf; 1145 __s += "\n"; 1146 1147 __s += "max_load_factor\t\t"; 1148 __builtin_sprintf(buf, "%lu", __control.max_load_factor()); 1149 __s += buf; 1150 __s += " : "; 1151 __builtin_sprintf(buf, "%lu", __test.max_load_factor()); 1152 __s += buf; 1153 __s += "\n"; 1154 1155 __s += "bucket_count\t\t"; 1156 __builtin_sprintf(buf, "%lu", __control.bucket_count()); 1157 __s += buf; 1158 __s += " : "; 1159 __builtin_sprintf(buf, "%lu", __test.bucket_count()); 1160 __s += buf; 1161 __s += "\n"; 1162 1163 __s += "max_bucket_count\t"; 1164 __builtin_sprintf(buf, "%lu", __control.max_bucket_count()); 1165 __s += buf; 1166 __s += " : "; 1167 __builtin_sprintf(buf, "%lu", __test.max_bucket_count()); 1168 __s += buf; 1169 __s += "\n"; 1170 1171 std::__throw_logic_error(__s.c_str()); 1172 } 1173 } 1174 } 1175 }; 1176 1177 // Specialization, empty. 1178 template<typename _Tp> 1179 struct rehash<_Tp, false> 1180 { 1181 void 1182 operator()(_Tp&) { } 1183 1184 void 1185 operator()(_Tp&, _Tp&) { } 1186 }; 1187 1188 1189 template<typename _Tp> 1190 struct swap 1191 { 1192 _Tp _M_other; 1193 1194 void 1195 operator()(_Tp& __container) 1196 { 1197 try 1198 { 1199 __container.swap(_M_other); 1200 } 1201 catch(const __gnu_cxx::forced_error&) 1202 { throw; } 1203 } 1204 }; 1205 1206 1207 template<typename _Tp> 1208 struct iterator_operations 1209 { 1210 typedef _Tp container_type; 1211 typedef typename container_type::iterator iterator; 1212 1213 void 1214 operator()(_Tp& __container) 1215 { 1216 try 1217 { 1218 // Any will do. 1219 iterator i = __container.begin(); 1220 iterator __attribute__((unused)) icopy(i); 1221 iterator __attribute__((unused)) iassign = i; 1222 } 1223 catch(const __gnu_cxx::forced_error&) 1224 { throw; } 1225 } 1226 }; 1227 1228 1229 template<typename _Tp> 1230 struct const_iterator_operations 1231 { 1232 typedef _Tp container_type; 1233 typedef typename container_type::const_iterator const_iterator; 1234 1235 void 1236 operator()(_Tp& __container) 1237 { 1238 try 1239 { 1240 // Any will do. 1241 const_iterator i = __container.begin(); 1242 const_iterator __attribute__((unused)) icopy(i); 1243 const_iterator __attribute__((unused)) iassign = i; 1244 } 1245 catch(const __gnu_cxx::forced_error&) 1246 { throw; } 1247 } 1248 }; 1249 1250 template<typename _Tp> 1251 struct assign_operator 1252 { 1253 _Tp _M_other; 1254 1255 void 1256 operator()(_Tp& __container) 1257 { 1258 try 1259 { 1260 // An exception while assigning might leave the container empty 1261 // making future attempts less relevant. So we copy it before to 1262 // always assign to a non empty container. It also check for copy 1263 // constructor exception safety at the same time. 1264 _Tp __clone(__container); 1265 __clone = _M_other; 1266 } 1267 catch(const __gnu_cxx::forced_error&) 1268 { throw; } 1269 } 1270 }; 1271 1272 1273 #if __cplusplus >= 201103L 1274 template<typename _Tp> 1275 struct move_assign_operator 1276 { 1277 _Tp _M_other; 1278 1279 void 1280 operator()(_Tp& __container) 1281 { 1282 try 1283 { 1284 __container = std::move(_M_other); 1285 } 1286 catch(const __gnu_cxx::forced_error&) 1287 { throw; } 1288 } 1289 }; 1290 #endif 1291 }; 1292 1293 // Base class for exception tests. 1294 template<typename _Tp> 1295 struct test_base: public functor_base 1296 { 1297 typedef _Tp container_type; 1298 1299 typedef functor_base base_type; 1300 typedef populate<container_type> populate; 1301 typedef make_container_n<container_type> make_container_n; 1302 1303 typedef clear<container_type> clear; 1304 typedef erase_point<container_type> erase_point; 1305 typedef erase_range<container_type> erase_range; 1306 typedef insert_point<container_type> insert_point; 1307 typedef emplace<container_type> emplace; 1308 typedef emplace_point<container_type> emplace_point; 1309 typedef emplace_front<container_type> emplace_front; 1310 typedef emplace_back<container_type> emplace_back; 1311 typedef pop_front<container_type> pop_front; 1312 typedef pop_back<container_type> pop_back; 1313 typedef push_front<container_type> push_front; 1314 typedef push_back<container_type> push_back; 1315 typedef rehash<container_type> rehash; 1316 typedef swap<container_type> swap; 1317 typedef iterator_operations<container_type> iterator_ops; 1318 typedef const_iterator_operations<container_type> const_iterator_ops; 1319 typedef assign_operator<container_type> assign_operator; 1320 #if __cplusplus >= 201103L 1321 typedef move_assign_operator<container_type> move_assign_operator; 1322 #endif 1323 1324 using base_type::compare; 1325 }; 1326 1327 1328 // Run through all member functions for basic exception safety 1329 // guarantee: no resource leaks when exceptions are thrown. 1330 // 1331 // Types of resources checked: memory. 1332 // 1333 // For each member function, use throw_value and throw_allocator as 1334 // value_type and allocator_type to force potential exception safety 1335 // errors. 1336 // 1337 // NB: Assumes 1338 // _Tp::value_type is __gnu_cxx::throw_value_* 1339 // _Tp::allocator_type is __gnu_cxx::throw_allocator_* 1340 // And that the _Cond template parameter for them both is 1341 // __gnu_cxx::limit_condition. 1342 template<typename _Tp> 1343 struct basic_safety : public test_base<_Tp> 1344 { 1345 typedef _Tp container_type; 1346 typedef test_base<container_type> base_type; 1347 typedef typename base_type::populate populate; 1348 typedef std::function<void(container_type&)> function_type; 1349 typedef __gnu_cxx::limit_condition condition_type; 1350 1351 using base_type::generate; 1352 1353 basic_safety() { run(); } 1354 1355 void 1356 run() 1357 { 1358 { 1359 // Setup. 1360 condition_type::never_adjustor off; 1361 1362 // Construct containers. 1363 container_type container; 1364 populate p1(container); 1365 1366 // Construct list of member functions to exercise. 1367 std::vector<function_type> functions; 1368 typename base_type::iterator_ops iops; 1369 functions.push_back(function_type(iops)); 1370 typename base_type::const_iterator_ops ciops; 1371 functions.push_back(function_type(ciops)); 1372 1373 typename base_type::erase_point erasep; 1374 functions.push_back(function_type(erasep)); 1375 typename base_type::erase_range eraser; 1376 functions.push_back(function_type(eraser)); 1377 typename base_type::insert_point insertp; 1378 functions.push_back(function_type(insertp)); 1379 typename base_type::emplace emplace; 1380 functions.push_back(function_type(emplace)); 1381 typename base_type::emplace_point emplacep; 1382 functions.push_back(function_type(emplacep)); 1383 typename base_type::emplace_front emplacef; 1384 functions.push_back(function_type(emplacef)); 1385 typename base_type::emplace_back emplaceb; 1386 functions.push_back(function_type(emplaceb)); 1387 typename base_type::pop_front popf; 1388 functions.push_back(function_type(popf)); 1389 typename base_type::pop_back popb; 1390 functions.push_back(function_type(popb)); 1391 typename base_type::push_front pushf; 1392 functions.push_back(function_type(pushf)); 1393 typename base_type::push_back pushb; 1394 functions.push_back(function_type(pushb)); 1395 typename base_type::rehash rehash; 1396 functions.push_back(function_type(rehash)); 1397 typename base_type::swap swap; 1398 populate p2(swap._M_other); 1399 functions.push_back(function_type(swap)); 1400 typename base_type::assign_operator assignop; 1401 populate p3(assignop._M_other); 1402 functions.push_back(function_type(assignop)); 1403 #if __cplusplus >= 201103L 1404 typename base_type::move_assign_operator massignop; 1405 populate p4(massignop._M_other); 1406 functions.push_back(function_type(massignop)); 1407 #endif 1408 // Last. 1409 typename base_type::clear clear; 1410 functions.push_back(function_type(clear)); 1411 1412 // Run tests. 1413 size_t i(1); 1414 for (auto it = functions.begin(); it != functions.end(); ++it) 1415 { 1416 function_type& f = *it; 1417 i = run_steps_to_limit(i, container, f); 1418 } 1419 } 1420 1421 // Now that all instances has been destroyed check that there is no 1422 // allocation remaining. 1423 std::cout << "Checking remaining stuff" << std::endl; 1424 __gnu_cxx::annotate_base::check(); 1425 } 1426 1427 template<typename _Funct> 1428 size_t 1429 run_steps_to_limit(size_t __step, container_type& __cont, 1430 const _Funct& __f) 1431 { 1432 bool exit(false); 1433 auto a = __cont.get_allocator(); 1434 1435 do 1436 { 1437 // Use the current step as an allocator label. 1438 a.set_label(__step); 1439 1440 try 1441 { 1442 condition_type::limit_adjustor limit(__step); 1443 __f(__cont); 1444 1445 // If we get here, done. 1446 exit = true; 1447 } 1448 catch(const __gnu_cxx::forced_error&) 1449 { 1450 // Check this step for allocations. 1451 // NB: Will throw std::logic_error if allocations. 1452 a.check(__step); 1453 1454 // Check memory allocated with operator new. 1455 1456 } 1457 ++__step; 1458 } 1459 while (!exit); 1460 1461 // Log count info. 1462 std::cout << __f.target_type().name() << std::endl; 1463 std::cout << "end count " << __step << std::endl; 1464 return __step; 1465 } 1466 }; 1467 1468 1469 // Run through all member functions with a no throw requirement, sudden death. 1470 // all: member functions erase, pop_back, pop_front, swap 1471 // iterator copy ctor, assignment operator 1472 // unordered and associative: clear 1473 // NB: Assumes _Tp::allocator_type is __gnu_cxx::throw_allocator_random. 1474 template<typename _Tp> 1475 struct generation_prohibited : public test_base<_Tp> 1476 { 1477 typedef _Tp container_type; 1478 typedef test_base<container_type> base_type; 1479 typedef typename base_type::populate populate; 1480 typedef __gnu_cxx::random_condition condition_type; 1481 1482 generation_prohibited() { run(); } 1483 1484 void 1485 run() 1486 { 1487 // Furthermore, assumes that the test functor will throw 1488 // forced_exception via throw_allocator, that all errors are 1489 // propagated and in error. Sudden death! 1490 1491 // Setup. 1492 container_type container; 1493 typename base_type::swap swap; 1494 1495 { 1496 condition_type::never_adjustor off; 1497 populate p1(container); 1498 populate p2(swap._M_other); 1499 } 1500 1501 // Run tests. 1502 { 1503 condition_type::always_adjustor on; 1504 1505 // NB: Vector and deque are special, erase can throw if the copy 1506 // constructor or assignment operator of value_type throws. 1507 if (!traits<container_type>::has_throwing_erase::value) 1508 { 1509 if (!container.empty()) 1510 { 1511 typename base_type::erase_point erasep; 1512 erasep(container); 1513 } 1514 typename base_type::erase_range eraser; 1515 eraser(container); 1516 } 1517 1518 if (!container.empty()) 1519 { 1520 typename base_type::pop_front popf; 1521 popf(container); 1522 } 1523 if (!container.empty()) 1524 { 1525 typename base_type::pop_back popb; 1526 popb(container); 1527 } 1528 1529 typename base_type::iterator_ops iops; 1530 iops(container); 1531 typename base_type::const_iterator_ops ciops; 1532 ciops(container); 1533 1534 swap(container); 1535 1536 // Last. 1537 typename base_type::clear clear; 1538 clear(container); 1539 } 1540 } 1541 }; 1542 1543 1544 // Test strong exception guarantee. 1545 // Run through all member functions with a roll-back, consistent 1546 // coherent requirement. 1547 // all: member functions insert and emplace of a single element, push_back, 1548 // push_front 1549 // unordered: rehash 1550 template<typename _Tp> 1551 struct propagation_consistent : public test_base<_Tp> 1552 { 1553 typedef _Tp container_type; 1554 typedef test_base<container_type> base_type; 1555 typedef typename base_type::populate populate; 1556 typedef std::function<void(container_type&)> function_type; 1557 typedef __gnu_cxx::limit_condition condition_type; 1558 1559 using base_type::compare; 1560 1561 propagation_consistent() { run(); } 1562 1563 // Run test. 1564 void 1565 run() 1566 { 1567 // Setup. 1568 condition_type::never_adjustor off; 1569 1570 // Construct containers. 1571 container_type container_control; 1572 1573 populate p(container_control); 1574 1575 // Construct list of member functions to exercise. 1576 std::vector<function_type> functions; 1577 typename base_type::emplace emplace; 1578 functions.push_back(function_type(emplace)); 1579 typename base_type::emplace_point emplacep; 1580 functions.push_back(function_type(emplacep)); 1581 typename base_type::emplace_front emplacef; 1582 functions.push_back(function_type(emplacef)); 1583 typename base_type::emplace_back emplaceb; 1584 functions.push_back(function_type(emplaceb)); 1585 typename base_type::push_front pushf; 1586 functions.push_back(function_type(pushf)); 1587 typename base_type::push_back pushb; 1588 functions.push_back(function_type(pushb)); 1589 typename base_type::insert_point insertp; 1590 functions.push_back(function_type(insertp)); 1591 typename base_type::rehash rehash; 1592 functions.push_back(function_type(rehash)); 1593 1594 // Run tests. 1595 for (auto i = functions.begin(); i != functions.end(); ++i) 1596 { 1597 function_type& f = *i; 1598 run_steps_to_limit(container_control, f); 1599 } 1600 } 1601 1602 template<typename _Funct> 1603 void 1604 run_steps_to_limit(container_type& container_control, const _Funct& __f) 1605 { 1606 size_t i(1); 1607 bool exit(false); 1608 1609 do 1610 { 1611 container_type container_test(container_control); 1612 1613 try 1614 { 1615 condition_type::limit_adjustor limit(i); 1616 __f(container_test); 1617 1618 // If we get here, done. 1619 exit = true; 1620 } 1621 catch(const __gnu_cxx::forced_error&) 1622 { 1623 compare(container_control, container_test); 1624 ++i; 1625 } 1626 } 1627 while (!exit); 1628 1629 // Log count info. 1630 std::cout << __f.target_type().name() << std::endl; 1631 std::cout << "end count " << i << std::endl; 1632 } 1633 }; 1634 1635 } // namespace __gnu_test 1636 1637 #endif 1638