1 // -*- C++ -*-
2
3 // Copyright (C) 2009-2023 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
39 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
58 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
74 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 #if __cpp_rtti
1463 std::cout << __f.target_type().name() << std::endl;
1464 #else
1465 std::cout << "[no type info - rtti disabled]\n";
1466 #endif
1467 std::cout << "end count " << __step << std::endl;
1468 return __step;
1469 }
1470 };
1471
1472
1473 // Run through all member functions with a no throw requirement, sudden death.
1474 // all: member functions erase, pop_back, pop_front, swap
1475 // iterator copy ctor, assignment operator
1476 // unordered and associative: clear
1477 // NB: Assumes _Tp::allocator_type is __gnu_cxx::throw_allocator_random.
1478 template<typename _Tp>
1479 struct generation_prohibited : public test_base<_Tp>
1480 {
1481 typedef _Tp container_type;
1482 typedef test_base<container_type> base_type;
1483 typedef typename base_type::populate populate;
1484 typedef __gnu_cxx::random_condition condition_type;
1485
1486 generation_prohibited() { run(); }
1487
1488 void
1489 run()
1490 {
1491 // Furthermore, assumes that the test functor will throw
1492 // forced_exception via throw_allocator, that all errors are
1493 // propagated and in error. Sudden death!
1494
1495 // Setup.
1496 container_type container;
1497 typename base_type::swap swap;
1498
1499 {
1500 condition_type::never_adjustor off;
1501 populate p1(container);
1502 populate p2(swap._M_other);
1503 }
1504
1505 // Run tests.
1506 {
1507 condition_type::always_adjustor on;
1508
1509 // NB: Vector and deque are special, erase can throw if the copy
1510 // constructor or assignment operator of value_type throws.
1511 if (!traits<container_type>::has_throwing_erase::value)
1512 {
1513 if (!container.empty())
1514 {
1515 typename base_type::erase_point erasep;
1516 erasep(container);
1517 }
1518 typename base_type::erase_range eraser;
1519 eraser(container);
1520 }
1521
1522 if (!container.empty())
1523 {
1524 typename base_type::pop_front popf;
1525 popf(container);
1526 }
1527 if (!container.empty())
1528 {
1529 typename base_type::pop_back popb;
1530 popb(container);
1531 }
1532
1533 typename base_type::iterator_ops iops;
1534 iops(container);
1535 typename base_type::const_iterator_ops ciops;
1536 ciops(container);
1537
1538 swap(container);
1539
1540 // Last.
1541 typename base_type::clear clear;
1542 clear(container);
1543 }
1544 }
1545 };
1546
1547
1548 // Test strong exception guarantee.
1549 // Run through all member functions with a roll-back, consistent
1550 // coherent requirement.
1551 // all: member functions insert and emplace of a single element, push_back,
1552 // push_front
1553 // unordered: rehash
1554 template<typename _Tp>
1555 struct propagation_consistent : public test_base<_Tp>
1556 {
1557 typedef _Tp container_type;
1558 typedef test_base<container_type> base_type;
1559 typedef typename base_type::populate populate;
1560 typedef std::function<void(container_type&)> function_type;
1561 typedef __gnu_cxx::limit_condition condition_type;
1562
1563 using base_type::compare;
1564
1565 propagation_consistent() { run(); }
1566
1567 // Run test.
1568 void
1569 run()
1570 {
1571 // Setup.
1572 condition_type::never_adjustor off;
1573
1574 // Construct containers.
1575 container_type container_control;
1576
1577 populate p(container_control);
1578
1579 // Construct list of member functions to exercise.
1580 std::vector<function_type> functions;
1581 typename base_type::emplace emplace;
1582 functions.push_back(function_type(emplace));
1583 typename base_type::emplace_point emplacep;
1584 functions.push_back(function_type(emplacep));
1585 typename base_type::emplace_front emplacef;
1586 functions.push_back(function_type(emplacef));
1587 typename base_type::emplace_back emplaceb;
1588 functions.push_back(function_type(emplaceb));
1589 typename base_type::push_front pushf;
1590 functions.push_back(function_type(pushf));
1591 typename base_type::push_back pushb;
1592 functions.push_back(function_type(pushb));
1593 typename base_type::insert_point insertp;
1594 functions.push_back(function_type(insertp));
1595 typename base_type::rehash rehash;
1596 functions.push_back(function_type(rehash));
1597
1598 // Run tests.
1599 for (auto i = functions.begin(); i != functions.end(); ++i)
1600 {
1601 function_type& f = *i;
1602 run_steps_to_limit(container_control, f);
1603 }
1604 }
1605
1606 template<typename _Funct>
1607 void
1608 run_steps_to_limit(container_type& container_control, const _Funct& __f)
1609 {
1610 size_t i(1);
1611 bool exit(false);
1612
1613 do
1614 {
1615 container_type container_test(container_control);
1616
1617 try
1618 {
1619 condition_type::limit_adjustor limit(i);
1620 __f(container_test);
1621
1622 // If we get here, done.
1623 exit = true;
1624 }
1625 catch(const __gnu_cxx::forced_error&)
1626 {
1627 compare(container_control, container_test);
1628 ++i;
1629 }
1630 }
1631 while (!exit);
1632
1633 // Log count info.
1634 #if __cpp_rtti
1635 std::cout << __f.target_type().name() << std::endl;
1636 #else
1637 std::cout << "[no type info - rtti disabled]\n";
1638 #endif
1639 std::cout << "end count " << i << std::endl;
1640 }
1641 };
1642
1643 } // namespace __gnu_test
1644
1645 #endif