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