2 * Copyright 2017 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 // @author Nicholas Ormrod <njormrod@fb.com>
21 This file contains an extensive STL compliance test suite for an STL vector
22 implementation (such as FBVector).
29 #define USING_STD_VECTOR
34 The insanity of this file deserves a superficial explanation.
36 This file tests an implementation of STL vector. It is extremely comprehensive.
37 If it compiles (more on that later) it generates a binary which, when run,
38 exhaustively tests its vector for standard compliance.
41 -If it doesn't compile, the compiler errors are mind-boggling.
42 -Not everything is testable. There are a few comments in the code where
43 the implementation must be inspected, as opposed to tested. These are very
44 simple inspections. Search for 'whitebox'.
45 -It does not test boolean specialization.
47 ==========================
48 How this file is organized
53 Data is a class designed to provide diagnostics when stored in a vector. It
54 counts the number of operations performed on it, can have any function
55 disabled or labeled as noexcept, throws errors from anywhere that is not
56 noexcept, tracks its supposed location in memory (optional), tracks
57 aggregate information, and can print a trace of its action.
59 Alloc, like Data, is a full-blown diagnostic allocator. It keeps track of
60 all space it has allocated, keeps counters, throws exceptions, and can easily
61 compare equal or not equal with other Allocs.
63 These two classes have a few useful helper functions:
64 isSane - checks that all the tracked variables make sense
65 softReset - simplifies the variables before a test
66 hardReset - brutally resets all variables to the default state
71 Google test is not quite good enough for this test file, because we need to
72 run tests across different input values and different types.
74 The STL_TEST macro takes a few arguments:
75 string - what is being tested
76 id - unique id, passed to TEST
77 restriction - requirements for test types
78 parameters - which variables to range over
80 Eg: STL_TEST("23.2.3", isCopyable, is_copy_constructible, a) { ... }
82 The restriction is used to select which types get tested. Copy construction,
83 for example, requires a data type which is copy constructible, whereas to test
84 the clear operation, the data only needs to be destructible. If the type does
85 not pass the restriction, then the test is not instantiated with that type (if
86 it were, then there would be a compiler error).
88 The variable names in the standard have very specific meaning. For example,
89 a and b are always vectors, i and j are always external iterators, etc. These
90 bindings are used in the STL_TEST - if you need a vector and an int, have
93 There is a list (BOOST_PP_SEQ) of test types and interface types. If the
94 type passes the restriction, then the test body is instantiated with that
95 type as its template parameter. Instantiation ensures that the contractual
96 elements of the standard are satisfied. Only the test types, however, and
97 not the interfact types, are actually tested.
99 If a test type passes the restriction, then it is run with a variety of
100 arguments. Each variable (e.g. a and b) have a generator, which generates
101 a range of values for that variable before each test. Generated values are not
102 reused - they are remade for every run. This causes long runtimes, but ensures
103 that corner cases are not missed.
105 There are two implicit extra parameters, z and ticks. Ignore z. Ticks, on the
106 other hand, is very important. Each is test is run multiple times with the
107 same arguments; the first time with no ticks (and hence no Data or Alloc
108 exceptions), and then once again for each and every location that an
109 exception can be thrown. This ensures that exception corner cases are alse
112 At the end of each test, a set of verification functions is run to ensure
113 that nothing was corrupted.
118 All specifications from N3337 Chapter 23 (Containers) that pertains to
119 vector is tested (if possible). Each aspect has a dedicated STL_TEST, so that
120 there are no compounding errors. The tests are organized as they appear in
123 The backbone of the testing framework is based on a small set of vector
126 -copy construction (a little bit)
132 These functions are used to generate and verify the tests. If they fail, then
133 the cascade of errors will be enormous. They are, therefore, tested first.
140 -Not all complexity checks are verified. These will be relentlessly hunted down
141 in the benchmarking phase.
143 -It seems that initializer lists with implicit arguments are constructed before
144 being passed into the vector. When one of the constructors fails, it fails in
145 the initializer list, before it even gets to the vector. The IL, however,
146 doesn't clean up properly, and already-constructed elements are not
147 destroyed. This causes a memory leak, and the tests break, but it is not the
148 fault of the vector itself. Further, since the implementation for the
149 initializer lists is specified in the standard as calling an associated
150 function with (il.begin(), il.end()), we really just have to check the throws
151 cases for the associated functions (which all work fine). Initializer lists
152 also do not work with explicit constructors.
154 -The implementation of std::copy from iterators prevents Data(int) from being
155 explicit. Explicitness is, perhaps, a desirable quality, but with fundamental
156 std library code like copy not supporting it, it seems impractical.
160 // include the vector first, to ensure its header is self-sufficient
161 #ifdef USING_STD_VECTOR
163 #define VECTOR_ std::vector
165 #include <folly/FBVector.h>
166 #define VECTOR_ folly::fbvector
169 //#define USING_STD_VECTOR
181 #include <type_traits>
184 #include <boost/iterator/iterator_adaptor.hpp>
185 #include <boost/preprocessor.hpp>
187 #include <folly/Conv.h>
188 #include <folly/Portability.h>
189 #include <folly/ScopeGuard.h>
190 #include <folly/portability/GFlags.h>
191 #include <folly/portability/GTest.h>
193 // We use some pre-processor magic to auto-generate setup and destruct code,
194 // but it also means we have some parameters that may not be used.
196 FOLLY_GCC_DISABLE_WARNING("-Wunused-parameter")
199 using namespace folly;
201 //=============================================================================
202 //=============================================================================
205 //-----------------------------------------------------------------------------
208 typedef uint32_t Flags;
210 // each method has 3 options: normal, noexcept, throw, and deleted
211 // normal is the default
212 // throw is mutually exclusive with noexcept
214 // DC - default constructor
215 // CC - copy constructor
216 // MC - move constructor
217 // OC - other constructor
218 // CA - copy assignment
219 // MA - move assignment
220 enum FlagVals : Flags {
241 ALL_DELETE = DC_DELETE | CC_DELETE | MC_DELETE
242 | CA_DELETE | MA_DELETE,
248 PROP_COPY = 0x100000,
249 PROP_MOVE = 0x200000,
250 PROP_SWAP = 0x400000,
253 //-----------------------------------------------------------------------------
256 template <bool b> struct D0 {
258 D0(const D0&) = default;
260 explicit D0(std::nullptr_t) {}
261 D0& operator=(const D0&) = default;
262 D0& operator=(D0&&) = default;
264 template <> struct D0<true> {
266 D0(const D0&) = default;
268 explicit D0(std::nullptr_t) {}
269 D0& operator=(const D0&) = default;
270 D0& operator=(D0&&) = default;
273 template <bool b> struct D1 {
275 D1(const D1&) = default;
277 explicit D1(std::nullptr_t) {}
278 D1& operator=(const D1&) = default;
279 D1& operator=(D1&&) = default;
281 template <> struct D1<true> {
283 D1(const D1&) = delete;
285 explicit D1(std::nullptr_t) {}
286 D1& operator=(const D1&) = default;
287 D1& operator=(D1&&) = default;
290 template <bool b> struct D2 {
292 D2(const D2&) = default;
294 explicit D2(std::nullptr_t) {}
295 D2& operator=(const D2&) = default;
296 D2& operator=(D2&&) = default;
298 template <> struct D2<true> {
300 D2(const D2&) = default;
302 explicit D2(std::nullptr_t) {}
303 D2& operator=(const D2&) = default;
304 D2& operator=(D2&&) = default;
307 template <bool b> struct D3 {
309 D3(const D3&) = default;
311 explicit D3(std::nullptr_t) {}
312 D3& operator=(const D3&) = default;
313 D3& operator=(D3&&) = default;
315 template <> struct D3<true> {
317 D3(const D3&) = default;
319 explicit D3(std::nullptr_t) {}
320 D3& operator=(const D3&) = delete;
321 D3& operator=(D3&&) = default;
324 template <bool b> struct D4 {
326 D4(const D4&) = default;
328 explicit D4(std::nullptr_t) {}
329 D4& operator=(const D4&) = default;
330 D4& operator=(D4&&) = default;
332 template <> struct D4<true> {
334 D4(const D4&) = default;
336 explicit D4(std::nullptr_t) {}
337 D4& operator=(const D4&) = default;
338 D4& operator=(D4&&) = delete;
342 struct Delete : D0<(f & DC_DELETE) != 0>,
343 D1<(f & CC_DELETE) != 0>,
344 D2<(f & MC_DELETE) != 0>,
345 D3<(f & CA_DELETE) != 0>,
346 D4<(f & MA_DELETE) != 0> {
348 Delete(const Delete&) = default;
349 Delete(Delete&&) = default;
350 Delete& operator=(const Delete&) = default;
351 Delete& operator=(Delete&&) = default;
353 explicit Delete(std::nullptr_t) :
354 D0<(f & DC_DELETE) != 0>(nullptr),
355 D1<(f & CC_DELETE) != 0>(nullptr),
356 D2<(f & MC_DELETE) != 0>(nullptr),
357 D3<(f & CA_DELETE) != 0>(nullptr),
358 D4<(f & MA_DELETE) != 0>(nullptr)
362 //-----------------------------------------------------------------------------
365 struct TickException : std::runtime_error {
366 explicit TickException(const std::string& s)
367 : std::runtime_error("tick: " + s) {}
371 static int CountTicks;
372 static int TicksLeft;
373 static void Tick(const std::string& s) {
374 if (TicksLeft == 0) {
375 throw TickException(s);
382 int Ticker::CountTicks = 0;
383 int Ticker::TicksLeft = -1;
386 struct DataTicker : Ticker {
387 DataTicker() noexcept(f & DC_NOEXCEPT) {
388 if (!(f & DC_NOEXCEPT)) {
392 DataTicker(const DataTicker&) noexcept((f & CC_NOEXCEPT) != 0) {
393 if (!(f & CC_NOEXCEPT)) {
394 Tick("Data(const Data&)");
397 DataTicker(DataTicker&&) noexcept((f & MC_NOEXCEPT) != 0) {
398 if (!(f & MC_NOEXCEPT)) {
399 Tick("Data(Data&&)");
402 explicit DataTicker(std::nullptr_t) noexcept((f & OC_NOEXCEPT) != 0) {
403 if (!(f & OC_NOEXCEPT)) {
407 ~DataTicker() noexcept {}
408 void operator=(const DataTicker&) noexcept((f & CA_NOEXCEPT) != 0) {
409 if (!(f & CA_NOEXCEPT)) {
410 Tick("op=(const Data&)");
413 void operator=(DataTicker&&) noexcept((f & MA_NOEXCEPT) != 0) {
414 if (!(f & MA_NOEXCEPT)) {
420 //-----------------------------------------------------------------------------
430 static int CountDestroy;
431 static int CountTotalOps;
432 static int CountLoggedConstruction;
438 Counter(const Counter&) noexcept {
442 Counter(Counter&&) noexcept {
446 explicit Counter(std::nullptr_t) noexcept {
450 void operator=(const Counter&) noexcept {
454 void operator=(Counter&&) noexcept {
458 ~Counter() noexcept {
464 int Counter::CountDC = 0;
465 int Counter::CountCC = 0;
466 int Counter::CountMC = 0;
467 int Counter::CountOC = 0;
468 int Counter::CountCA = 0;
469 int Counter::CountMA = 0;
470 int Counter::CountDestroy = 0;
471 int Counter::CountTotalOps = 0;
472 int Counter::CountLoggedConstruction = 0;
474 //-----------------------------------------------------------------------------
479 static std::map<int, int> UIDCount;
481 static std::map<const Tracker*, int> Locations;
487 Tracker(Tracker* self, int uid) : self(self), uid(uid) {}
490 template <bool isRelocatable>
491 struct DataTracker : Tracker {
492 DataTracker() noexcept : Tracker(this, UID++) {
495 if (!isRelocatable) {
496 Locations[self] = uid;
500 DataTracker(const DataTracker& o) noexcept : Tracker(this, o.uid) {
503 if (!isRelocatable) {
504 Locations[self] = uid;
506 print("Data(const Data&)");
508 DataTracker(DataTracker&& o) noexcept : Tracker(this, o.uid) {
511 if (!isRelocatable) {
512 Locations[self] = uid;
514 print("Data(Data&&)");
517 explicit DataTracker(int uid) noexcept : Tracker(this, uid) {
520 if (!isRelocatable) {
521 Locations[self] = uid;
526 ~DataTracker() noexcept {
529 if (!isRelocatable) {
530 Locations.erase(self);
534 self = (DataTracker*)0xfeebdaed;
537 DataTracker& operator=(const DataTracker& o) noexcept {
541 if (!isRelocatable) {
542 Locations[self] = uid;
544 print("op=(const Data&)");
547 DataTracker& operator=(DataTracker&& o) noexcept {
551 if (!isRelocatable) {
552 Locations[self] = uid;
554 print("op=(Data&&)");
558 void print(const std::string& fun) {
560 std::cerr << std::setw(20) << fun << ": uid = " << std::setw(3) << uid;
561 if (!isRelocatable) {
562 std::cerr << ", self = " << self;
564 std::cerr << std::endl;
569 int Tracker::UID = 1234;
570 std::map<int, int> Tracker::UIDCount;
571 int Tracker::UIDTotal = 0;
572 std::map<const Tracker*, int> Tracker::Locations;
573 bool Tracker::Print = false;
575 //-----------------------------------------------------------------------------
576 //-----------------------------------------------------------------------------
579 template <Flags f = 0, size_t pad = 0>
580 struct Data : DataTracker<(f & IS_RELOCATABLE) != 0>,
581 Counter, DataTicker<f>, Delete<f> {
582 static const Flags flags = f;
583 char spacehog[pad ? pad : 1];
586 Data(const Data&) = default;
587 Data(Data&&) = default;
588 /* implicit */ Data(int i) :
589 DataTracker<(f & IS_RELOCATABLE) != 0>(i),
591 DataTicker<f>(nullptr),
595 Data& operator=(const Data&) = default;
596 Data& operator=(Data&&) = default;
599 int operator&() const;
603 template <Flags f, size_t pad>
604 struct IsRelocatable<Data<f, pad>>
605 : std::integral_constant<bool,
606 (f & IS_RELOCATABLE) != 0
610 //-----------------------------------------------------------------------------
611 //-----------------------------------------------------------------------------
614 template <typename T>
615 struct isPropCopy : true_type {};
616 template <Flags f, size_t pad>
617 struct isPropCopy<Data<f, pad>> :
618 std::integral_constant<bool, (f & PROP_COPY) != 0> {};
620 template <typename T>
621 struct isPropMove : true_type {};
622 template <Flags f, size_t pad>
623 struct isPropMove<Data<f, pad>> :
624 std::integral_constant<bool, (f & PROP_MOVE) != 0> {};
626 template <typename T>
627 struct isPropSwap : true_type {};
628 template <Flags f, size_t pad>
629 struct isPropSwap<Data<f, pad>> :
630 std::integral_constant<bool, (f & PROP_SWAP) != 0> {};
633 struct AllocTracker {
634 static int Constructed;
635 static int Destroyed;
636 static map<void*, size_t> Allocated;
637 static map<void*, int> Owner;
639 int AllocTracker::Constructed = 0;
640 int AllocTracker::Destroyed = 0;
641 map<void*, size_t> AllocTracker::Allocated;
642 map<void*, int> AllocTracker::Owner;
645 struct Alloc : AllocTracker, Ticker {
646 typedef typename std::allocator<T>::pointer pointer;
647 typedef typename std::allocator<T>::const_pointer const_pointer;
648 typedef typename std::allocator<T>::difference_type difference_type;
649 typedef typename std::allocator<T>::size_type size_type;
650 typedef typename std::allocator<T>::value_type value_type;
657 explicit Alloc(int i = 8) : a(), id(i) {}
658 Alloc(const Alloc& o) : a(o.a), id(o.id) {}
659 Alloc(Alloc&& o) : a(move(o.a)), id(o.id) {}
660 Alloc& operator=(const Alloc&) = default;
661 Alloc& operator=(Alloc&&) = default;
662 bool operator==(const Alloc& o) const { return a == o.a && id == o.id; }
663 bool operator!=(const Alloc& o) const { return !(*this == o); }
668 pointer allocate(size_type n) {
670 cerr << "called allocate(0)" << endl;
671 throw runtime_error("allocate fail");
674 auto p = a.allocate(n);
680 void deallocate(pointer p, size_type n) {
682 cerr << "deallocate(nullptr, " << n << ")" << endl;
683 FAIL() << "deallocate failed";
685 if (Allocated[p] != n) {
686 cerr << "deallocate(" << p << ", " << n << ") invalid: ";
687 if (Allocated[p] == 0) {
688 cerr << "never allocated";
689 } else if (Allocated[p] == size_t(-1)) {
690 cerr << "already deallocated";
692 cerr << "wrong number (want " << Allocated[p] << ")";
695 FAIL() << "deallocate failed";
697 if (Owner[p] != id) {
698 cerr << "deallocate(" << p << "), where pointer is owned by "
699 << Owner[p] << ", instead of self - " << id << endl;
700 FAIL() << "deallocate failed";
706 template <class U, class... Args>
707 void construct(U* p, Args&&... args) {
709 a.construct(p, std::forward<Args>(args)...);
722 Alloc select_on_container_copy_construction() const {
723 Tick("select allocator for copy");
724 return Alloc(id + 1);
727 typedef isPropCopy<T> propagate_on_container_copy_assignment;
728 typedef isPropMove<T> propagate_on_container_move_assignment;
729 typedef isPropSwap<T> propagate_on_container_swap;
732 //=============================================================================
733 //=============================================================================
734 // Verification and resetting
736 void softReset(int ticks = -1) {
737 Counter::CountLoggedConstruction +=
738 Counter::CountDC + Counter::CountCC + Counter::CountMC
739 + Counter::CountOC - Counter::CountDestroy;
740 Counter::CountDC = Counter::CountCC = Counter::CountMC
741 = Counter::CountOC = Counter::CountCA = Counter::CountMA = 0;
742 Counter::CountDestroy = Counter::CountTotalOps = 0;
743 Ticker::CountTicks = 0;
744 Ticker::TicksLeft = ticks;
748 Tracker::UIDCount.clear();
749 Tracker::UIDTotal = 0;
750 Tracker::Locations.clear();
752 Counter::CountLoggedConstruction = 0;
754 AllocTracker::Constructed = 0;
755 AllocTracker::Destroyed = 0;
756 AllocTracker::Allocated.clear();
757 AllocTracker::Owner.clear();
761 int con = Counter::CountDC + Counter::CountCC
762 + Counter::CountMC + Counter::CountOC
763 + Counter::CountLoggedConstruction;
764 int del = Counter::CountDestroy;
769 int tot = getTotal();
770 ASSERT_GE(tot, 0) << "more objects deleted than constructed";
772 ASSERT_EQ(tot, Tracker::UIDTotal)
773 << "UIDTotal has incorrect number of objects";
776 for (const auto& kv : Tracker::UIDCount) {
777 ASSERT_TRUE(kv.second >= 0) << "there exists " << kv.second << " Data "
778 "with uid " << kv.first;
781 ASSERT_EQ(tot, altTot) << "UIDCount corrupted";
783 if (!Tracker::Locations.empty()) { // implied by IsRelocatable
784 ASSERT_EQ(tot, Tracker::Locations.size())
785 << "Locations has incorrect number of objects";
786 for (const auto& du : Tracker::Locations) {
787 ASSERT_EQ(du.second, du.first->uid) << "Locations contains wrong uid";
788 ASSERT_EQ(du.first, du.first->self) << "Data.self is corrupted";
793 //-----------------------------------------------------------------------------
796 template <typename T>
797 struct is_copy_constructibleAndAssignable
798 : std::integral_constant<bool,
799 std::is_copy_constructible<T>::value &&
800 std::is_copy_assignable<T>::value
803 template <typename T>
804 struct is_move_constructibleAndAssignable
805 : std::integral_constant<bool,
806 std::is_move_constructible<T>::value &&
807 std::is_move_assignable<T>::value
810 template <class Vector>
811 struct customAllocator
812 : std::integral_constant<bool,
814 typename Vector::allocator_type,
815 std::allocator<typename Vector::value_type>
819 template <typename T>
820 struct special_move_assignable
821 : is_move_constructibleAndAssignable<T> {};
822 template <Flags f, size_t pad>
823 struct special_move_assignable<Data<f, pad>>
824 : std::integral_constant<bool,
825 is_move_constructibleAndAssignable<Data<f, pad>>::value ||
829 //=============================================================================
830 //=============================================================================
833 //-----------------------------------------------------------------------------
840 unsigned reslo, reshi;
842 __asm__ __volatile__ (
843 "xorl %%eax,%%eax \n cpuid \n"
844 ::: "%eax", "%ebx", "%ecx", "%edx");
845 __asm__ __volatile__ (
847 : "=a" (reslo), "=d" (reshi) );
848 __asm__ __volatile__ (
849 "xorl %%eax,%%eax \n cpuid \n"
850 ::: "%eax", "%ebx", "%ecx", "%edx");
852 return ((uint64_t)reshi << 32) | reslo;
856 //-----------------------------------------------------------------------------
859 #define IBOOST_PP_VARIADIC_SIZE(...) IBOOST_PP_VARIADIC_SIZE_I(__VA_ARGS__, \
860 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, \
861 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, \
862 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, \
863 7, 6, 5, 4, 3, 2, 1,)
864 #define IBOOST_PP_VARIADIC_SIZE_I(e0, e1, e2, e3, e4, e5, e6, e7, e8, e9, \
865 e10, e11, e12, e13, e14, e15, e16, e17, e18, e19, e20, e21, e22, e23, e24, \
866 e25, e26, e27, e28, e29, e30, e31, e32, e33, e34, e35, e36, e37, e38, e39, \
867 e40, e41, e42, e43, e44, e45, e46, e47, e48, e49, e50, e51, e52, e53, e54, \
868 e55, e56, e57, e58, e59, e60, e61, e62, e63, size, ...) size
869 #define IBOOST_PP_VARIADIC_TO_SEQ(...) \
870 BOOST_PP_TUPLE_TO_SEQ(IBOOST_PP_VARIADIC_SIZE(__VA_ARGS__), (__VA_ARGS__))
872 //-----------------------------------------------------------------------------
875 #define GEN_TEST(r, name, type) \
877 string atype = PrettyType<typename type::allocator_type>()(); \
878 string ptype = PrettyType<typename type::value_type>()(); \
879 SCOPED_TRACE("allocator: " + atype); { \
880 SCOPED_TRACE("datatype: " + ptype); { \
881 test_ ## name ## 3 <type> (); \
882 if (::testing::Test::HasFatalFailure()) return; \
884 #define GEN_TYPE_TEST(r, name, type) \
885 if (0) test_I_ ## name ## 3 <type> ();
886 #define GEN_RUNNABLE_TEST(r, name, type) \
887 one = test_I_ ## name ## 3 <type> () || one;
889 #define GEN_LOOPER(r, d, arg) BOOST_PP_CAT(LOOPER_, arg)
890 #define GEN_VMAKER(r, d, arg) { BOOST_PP_CAT(VMAKER_, arg) {
891 #define GEN_UMAKER(r, d, arg) } BOOST_PP_CAT(UMAKER_, arg) }
892 #define GEN_CLOSER(r, d, arg) BOOST_PP_CAT(CLOSER_, arg)
894 #define TYPIFY(r, d, name) BOOST_PP_CAT(TYPIFY_, name)
895 #define ARGIFY(r, d, name) TYPIFY(r, d, name) name
897 #define MAKE_TEST(ref, name, types, restriction, argseq, ...) \
898 template <class Vector> void test_ ## name ## 2 (std::false_type) {} \
899 template <class Vector> void test_ ## name ## 2 (std::true_type) { \
900 BOOST_PP_SEQ_FOR_EACH(GEN_LOOPER, _, argseq) \
904 BOOST_PP_SEQ_FOR_EACH(GEN_VMAKER, _, argseq) \
906 test_ ## name <Vector, typename Vector::value_type, \
907 typename Vector::allocator_type> ( __VA_ARGS__ ); \
908 if (::testing::Test::HasFatalFailure()) { \
912 BOOST_PP_SEQ_FOR_EACH(GEN_UMAKER, _, BOOST_PP_SEQ_REVERSE(argseq)) \
916 BOOST_PP_SEQ_FOR_EACH(GEN_CLOSER, _, BOOST_PP_SEQ_REVERSE(argseq)) \
918 template <class Vector> void test_ ## name ## 3 () { \
919 test_ ## name ## 2 <Vector> (std::integral_constant<bool, \
920 restriction<typename Vector::value_type>::value && \
921 is_copy_constructible<typename Vector::value_type>::value \
925 template <class Vector> bool test_I_ ## name ## 2 (std::false_type) \
927 template <class Vector> bool test_I_ ## name ## 2 (std::true_type) { \
929 auto f = test_ ## name <Vector, \
930 typename Vector::value_type, typename Vector::allocator_type>; \
933 template <class Vector> bool test_I_ ## name ## 3 () { \
934 return test_I_ ## name ## 2 <Vector> (std::integral_constant<bool, \
935 restriction<typename Vector::value_type>::value>()); \
939 TEST(FBVector, name) { \
940 SCOPED_TRACE("N3337 reference: " ref); \
941 BOOST_PP_SEQ_FOR_EACH(GEN_TEST, name, types) \
942 BOOST_PP_SEQ_FOR_EACH(GEN_TYPE_TEST, name, INTERFACE_TYPES) \
944 BOOST_PP_SEQ_FOR_EACH(GEN_RUNNABLE_TEST, name, types) \
946 FAIL() << "No tests qualified to run"; \
950 #define DECL(name, ...) \
951 template <class Vector, typename T, typename Allocator> \
952 void test_ ## name (BOOST_PP_SEQ_ENUM(BOOST_PP_SEQ_TRANSFORM( \
953 ARGIFY, _, IBOOST_PP_VARIADIC_TO_SEQ(__VA_ARGS__))))
955 #define STL_TEST_I(ref, name, restriction, ...) \
956 DECL(name, __VA_ARGS__); \
957 MAKE_TEST(ref, name, TEST_TYPES, restriction, \
958 IBOOST_PP_VARIADIC_TO_SEQ(__VA_ARGS__), __VA_ARGS__) \
959 DECL(name, __VA_ARGS__)
961 #define STL_TEST(ref, name, restriction, ...) \
962 STL_TEST_I(ref, name, restriction, z, ## __VA_ARGS__, ticks)
964 //-----------------------------------------------------------------------------
968 typedef Data<0, 4080> ED2;
969 typedef Data<MC_NOEXCEPT> ED3;
970 typedef Data<MC_NOEXCEPT | CC_DELETE> ED4;
971 typedef Data<IS_RELOCATABLE> ED5;
973 typedef VECTOR_<int, std::allocator<int>> _TVIS;
974 typedef VECTOR_<int, Alloc<int>> _TVI;
975 typedef VECTOR_<ED1, std::allocator<ED1>> _TV1;
976 typedef VECTOR_<ED2, std::allocator<ED2>> _TV2;
977 typedef VECTOR_<ED3, std::allocator<ED3>> _TV3;
978 typedef VECTOR_<ED4, std::allocator<ED4>> _TV4;
979 typedef VECTOR_<ED5, std::allocator<ED5>> _TV5v1;
980 typedef VECTOR_<ED5, Alloc<ED5>> _TV5;
982 typedef Data<PROP_COPY> EP1;
983 typedef Data<PROP_MOVE> EP2;
984 typedef Data<PROP_SWAP> EP3;
986 typedef VECTOR_<EP1, Alloc<EP1>> _TP1;
987 typedef VECTOR_<EP2, Alloc<EP2>> _TP2;
988 typedef VECTOR_<EP3, Alloc<EP3>> _TP3;
990 #define TEST_TYPES (_TVIS)(_TVI)(_TV1)(_TV2)(_TV3)(_TV4)(_TV5v1)(_TV5) \
993 typedef Data<ALL_DELETE> DD1; // unoperable
994 typedef Data<DC_DELETE | CC_DELETE | MC_DELETE> DD2; // unconstructible
995 typedef Data<CA_DELETE | MA_DELETE> DD3; // unassignable
996 typedef Data<CC_DELETE | MC_DELETE> DD4; // uncopyable
997 typedef Data<ALL_DELETE & ~DC_DELETE> DD5; // only default constructible
998 typedef Data<CC_DELETE> DD6; // move-only copy construction
999 typedef Data<CA_DELETE> DD7; // move-only assignment
1001 typedef Data<ALL_DELETE | PROP_MOVE> DDSMA;
1002 typedef VECTOR_<DDSMA, Alloc<DDSMA>> _TSpecialMA;
1004 #define INTERFACE_TYPES \
1005 (_TVI)(VECTOR_<DD1>)(VECTOR_<DD2>)(VECTOR_<DD3>) \
1006 (VECTOR_<DD4>)(VECTOR_<DD5>)(VECTOR_<DD6>) \
1007 (VECTOR_<DD7>)(_TSpecialMA)
1009 //-----------------------------------------------------------------------------
1012 template <typename T>
1014 string operator()() {
1015 if (is_same<T, int>::value) {
1018 if (is_same<T, char>::value) {
1021 if (is_same<T, uint64_t>::value) {
1024 return typeid(T).name();
1028 template <Flags f, size_t pad>
1029 struct PrettyType<Data<f, pad>> {
1030 string operator()() {
1034 if ((f & DC_DELETE) ||
1040 if (f & DC_DELETE) {
1043 if (f & CC_DELETE) {
1046 if (f & MC_DELETE) {
1049 if (f & CA_DELETE) {
1052 if (f & MA_DELETE) {
1058 if ((f & DC_NOEXCEPT) ||
1059 (f & CC_NOEXCEPT) ||
1060 (f & MC_NOEXCEPT) ||
1061 (f & CA_NOEXCEPT) ||
1062 (f & MA_NOEXCEPT)) {
1064 if (f & DC_NOEXCEPT) {
1067 if (f & CC_NOEXCEPT) {
1070 if (f & MC_NOEXCEPT) {
1073 if (f & CA_NOEXCEPT) {
1076 if (f & MA_NOEXCEPT) {
1082 if (f & IS_RELOCATABLE) {
1083 tpe << "(relocatable)";
1087 tpe << "{pad " << pad << "}";
1094 template <typename T>
1095 struct PrettyType<std::allocator<T>> {
1096 string operator()() {
1097 return "std::allocator<" + PrettyType<T>()() + ">";
1101 template <typename T>
1102 struct PrettyType<Alloc<T>> {
1103 string operator()() {
1104 return "Alloc<" + PrettyType<T>()() + ">";
1108 //-----------------------------------------------------------------------------
1109 // Setup, teardown, runup, rundown
1111 // These four macros are run once per test. Setup and runup occur before the
1112 // test, teardown and rundown after. Setup and runup straddle the
1113 // initialization sequence, whereas rundown and teardown straddle the
1116 #define SETUP hardReset();
1119 //-----------------------------------------------------------------------------
1120 // Types and typegens
1125 #define TYPIFY_z std::nullptr_t
1127 Vector* a_p = nullptr; Vector* b_p = nullptr; \
1128 typename Vector::value_type* t_p = nullptr;
1129 #define VMAKER_z std::nullptr_t z = nullptr;
1131 verify<Vector>(0); \
1132 if (::testing::Test::HasFatalFailure()) { \
1140 #define VERIFICATION \
1141 if (b_p != nullptr) verify(t_p != nullptr ,*a_p, *b_p); \
1142 else if (a_p != nullptr) verify(t_p != nullptr, *a_p); \
1143 else verify<Vector>(t_p != nullptr); \
1144 if (::testing::Test::HasFatalFailure()) return;
1146 #define TYPIFY_ticks int
1147 #define LOOPER_ticks \
1148 int _maxTicks_ = 0; \
1149 bool ticks_thrown = false; \
1150 for (int ticks = -1; ticks < _maxTicks_; ++ticks) {
1151 #define VMAKER_ticks \
1152 string ticks_st = folly::to<string>("ticks = ", ticks); \
1153 SCOPED_TRACE(ticks_st); \
1154 { SCOPED_TRACE("pre-run verification"); \
1158 #define UMAKER_ticks _maxTicks_ = Ticker::CountTicks; } \
1159 catch (const TickException&) { ticks_thrown = true; } \
1160 catch (const std::exception& e) \
1161 { FAIL() << "EXCEPTION: " << e.what(); } \
1163 { FAIL() << "UNKNOWN EXCEPTION"; } \
1164 if (ticks >= 0 && Ticker::CountTicks > ticks && !ticks_thrown) \
1165 FAIL() << "CountTicks = " << Ticker::CountTicks << " > " \
1166 << ticks << " = ticks" \
1167 << ", but no tick error was observed"; \
1169 #define CLOSER_ticks }
1172 //--------------------------------------------------
1173 // vectors (second could be .equal, ==, or distinct)
1175 static const vector<pair<int, int>> VectorSizes = {
1179 { 10, -1}, { 10, 1}, { 10, 0},
1180 {100, -1}, {100, 1},
1182 //{ 10, -1}, { 10, 0}, { 10, 1}, { 10, 2}, { 10, 10},
1183 //{ 100, -1}, { 100, 0}, { 100, 1}, { 100, 2}, { 100, 10}, { 100, 100},
1184 //{ 1000, -1}, { 1000, 0}, { 1000, 1}, { 1000, 2}, { 1000, 10}, { 1000, 100},
1188 int populateIndex = 1426;
1189 template <class Vector>
1190 void populate(Vector& v, const pair<int, int>& ss) {
1192 for (; i < ss.first; ++i) {
1193 v.emplace_back(populateIndex++);
1195 if (ss.second >= 0) {
1196 while (v.capacity() - v.size() != size_t(ss.second)) {
1197 v.emplace_back(populateIndex++);
1202 template <typename A>
1204 static A get() { return A(); }
1206 template <typename T>
1207 struct allocGen<Alloc<T>> {
1208 static Alloc<T> get() {
1215 #define TYPIFY_a Vector&
1216 #define LOOPER_a for (const auto& a_ss : VectorSizes) {
1218 Vector a(allocGen<typename Vector::allocator_type>::get()); \
1220 populate(*a_p, a_ss); \
1221 string a_st = folly::to<string>("a (", a.size(), "/", a.capacity(), ")"); \
1223 #define UMAKER_a verify(0, a); if (::testing::Test::HasFatalFailure()) return;
1226 #define TYPIFY_b Vector&
1227 #define LOOPER_b for (int b_i = -2; b_i < (int)VectorSizes.size(); ++b_i) {
1229 Vector b_s(allocGen<typename Vector::allocator_type>::get()); \
1230 b_p = &b_s; string b_st; \
1233 b_st = "b is an alias of a"; \
1235 else if (b_i == -1) { \
1237 new (&b_s) Vector(a); \
1238 b_st = "b is a deep copy of a"; \
1241 populate(b_s, VectorSizes[b_i]); \
1242 b_st = folly::to<string>("b (", b_s.size(), "/", b_s.capacity(), ")"); \
1247 verify(0, a, b); if (::testing::Test::HasFatalFailure()) return;
1253 static const vector<int> nSizes = { 0, 1, 2, 9, 10, 11 };
1255 #define TYPIFY_n int
1256 #define LOOPER_n for (int n : nSizes) {
1258 string n_st = folly::to<string>("n = ", n); SCOPED_TRACE(n_st);
1262 //-----------------------
1263 // non-internal iterators
1265 static int ijarr[12] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
1266 static int ijarC[12] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
1268 #define TYPIFY_i int*
1270 #define VMAKER_i int* i = ijarr; SCOPED_TRACE("i = fib[0]");
1274 #define TYPIFY_j int*
1275 #define LOOPER_j for (int j_i = 0; j_i < 12; ++j_i) {
1277 int* j = ijarr + j_i; \
1278 string j_st = folly::to<string>("j = fib[", j_i, "]"); \
1281 for (int j_c = 0; j_c < 12; ++j_c) ASSERT_EQ(ijarC[j_c], ijarr[j_c]);
1284 //-------------------
1285 // internal iterators
1287 template <class Vector>
1288 std::pair<typename Vector::iterator, string>
1289 iterSpotter(Vector& v, int i) {
1290 typename Vector::iterator it;
1321 cerr << "internal error" << endl;
1325 return make_pair(it, msg);
1328 #define TYPIFY_p typename Vector::iterator
1329 #define LOOPER_p for (int p_i = 0; p_i < 4; ++p_i) {
1331 auto p_im = iterSpotter(a, p_i); \
1332 auto& p = p_im.first; \
1333 auto& p_m = p_im.second; \
1334 SCOPED_TRACE("p = " + p_m);
1338 #define TYPIFY_q typename Vector::iterator
1339 #define LOOPER_q for (int q_i = p_i; q_i < 4; ++q_i) {
1341 auto q_im = iterSpotter(a, q_i); \
1342 auto& q = q_im.first; \
1343 auto& q_m = q_im.second; \
1344 SCOPED_TRACE("q = " + q_m);
1351 static const vector<int> tVals = { 0, 1, 2, 3, 17, 66, 521 };
1353 #define TYPIFY_t typename Vector::value_type&
1354 #define LOOPER_t for (int t_v : tVals) {
1356 typename Vector::value_type t_s(t_v); \
1357 t_p = addressof(t_s); \
1358 string t_st = folly::to<string>("t(", t_v, ")"); \
1359 if (t_v < 4 && a_p != nullptr) { \
1360 auto t_im = iterSpotter(*a_p, t_v); \
1361 if (t_im.first != a_p->end()) { \
1362 t_p = addressof(*t_im.first); \
1363 t_st = "t is " + t_im.second; \
1366 typename Vector::value_type& t = *t_p; \
1374 #define TYPIFY_m typename Vector::allocator_type
1376 int m_max = 1 + (a_p != nullptr); \
1377 for (int m_i = 0; m_i < m_max; ++m_i) {
1379 typename Vector::allocator_type m = m_i == 0 \
1380 ? typename Vector::allocator_type() \
1381 : a_p->get_allocator();
1385 //-----------------------------------------------------------------------------
1389 template <class Vector>
1390 void verifyVector(const Vector& v) {
1391 ASSERT_TRUE(v.begin() <= v.end()) << "end is before begin";
1392 ASSERT_TRUE(v.empty() == (v.begin() == v.end())) << "empty != (begin == end)";
1393 ASSERT_TRUE(v.size() == size_t(distance(v.begin(), v.end())))
1394 << "size != end - begin";
1395 ASSERT_TRUE(v.size() <= v.capacity()) << "size > capacity";
1396 ASSERT_TRUE(v.capacity() <= v.max_size()) << "capacity > max_size";
1397 ASSERT_TRUE(v.data() || true); // message won't print - it will just crash
1398 ASSERT_TRUE(v.size() == 0 || v.data() != nullptr)
1399 << "nullptr data points to at least one element";
1402 void verifyAllocator(int ele, int cap) {
1403 ASSERT_EQ(ele, AllocTracker::Constructed - AllocTracker::Destroyed);
1406 for (auto kv : AllocTracker::Allocated) {
1407 if (kv.second != size_t(-1)) {
1411 ASSERT_EQ(cap, tot) << "the allocator counts " << tot << " space, "
1412 "but the vector(s) have (combined) capacity " << cap;
1416 template <class Vector>
1417 void verify(int extras) {
1418 if (!is_arithmetic<typename Vector::value_type>::value)
1419 ASSERT_EQ(0 + extras, getTotal()) << "there exist Data but no vectors";
1421 if (::testing::Test::HasFatalFailure()) return;
1422 if (customAllocator<Vector>::value) verifyAllocator(0, 0);
1424 template <class Vector>
1425 void verify(int extras, const Vector& v) {
1427 if (!is_arithmetic<typename Vector::value_type>::value)
1428 ASSERT_EQ(v.size() + extras, getTotal())
1429 << "not all Data are in the vector";
1431 if (::testing::Test::HasFatalFailure()) return;
1432 if (customAllocator<Vector>::value) verifyAllocator(v.size(), v.capacity());
1434 template <class Vector>
1435 void verify(int extras, const Vector& v1, const Vector& v2) {
1438 auto size = v1.size();
1439 auto cap = v1.capacity();
1442 cap += v2.capacity();
1444 if (!is_arithmetic<typename Vector::value_type>::value)
1445 ASSERT_EQ(size + extras, getTotal()) << "not all Data are in the vector(s)";
1447 if (::testing::Test::HasFatalFailure()) return;
1448 if (customAllocator<Vector>::value) verifyAllocator(size, cap);
1451 //=============================================================================
1454 // save the state of a vector
1455 int convertToInt(int t) {
1458 template <Flags f, size_t pad>
1459 int convertToInt(const Data<f, pad>& t) {
1462 template <typename T>
1463 int convertToInt(const std::allocator<T>&) {
1466 template <typename T>
1467 int convertToInt(const Alloc<T>& a) {
1471 template <class Vector>
1473 typedef typename Vector::size_type size_type;
1477 /* implicit */ DataState(const Vector& v) {
1480 data_ = new int[size_];
1481 for (size_type i = 0; i < size_; ++i) {
1482 data_[i] = convertToInt(v.data()[i]);
1492 bool operator==(const DataState& o) const {
1493 if (size_ != o.size_) return false;
1494 for (size_type i = 0; i < size_; ++i) {
1495 if (data_[i] != o.data_[i]) return false;
1500 int operator[](size_type i) {
1502 cerr << "trying to access DataState out of bounds" << endl;
1508 size_type size() { return size_; }
1511 // downgrade iterators
1512 template <typename It, class tag>
1513 class Transformer : public boost::iterator_adaptor<
1514 Transformer<It, tag>,
1516 typename iterator_traits<It>::value_type,
1519 friend class boost::iterator_core_access;
1520 shared_ptr<set<It>> dereferenced;
1523 explicit Transformer(const It& it)
1524 : Transformer::iterator_adaptor_(it)
1525 , dereferenced(new set<It>()) {}
1527 typename iterator_traits<It>::value_type& dereference() const {
1528 if (dereferenced->find(this->base_reference()) != dereferenced->end()) {
1529 cerr << "iterator dereferenced more than once" << endl;
1532 dereferenced->insert(this->base_reference());
1533 return *this->base_reference();
1537 template <typename It>
1538 Transformer<It, forward_iterator_tag> makeForwardIterator(const It& it) {
1539 return Transformer<It, forward_iterator_tag>(it);
1541 template <typename It>
1542 Transformer<It, input_iterator_tag> makeInputIterator(const It& it) {
1543 return Transformer<It, input_iterator_tag>(it);
1546 // mutate a value (in contract only)
1547 void mutate(int& i) {
1552 void mutate(uint64_t& i) {
1557 template <Flags f, size_t pad>
1558 void mutate(Data<f, pad>& ds) {
1564 //=============================================================================
1573 //-----------------------------------------------------------------------------
1576 STL_TEST("23.2.1 Table 96.1-7", containerTypedefs, is_destructible) {
1577 static_assert(is_same<T, typename Vector::value_type>::value,
1578 "T != Vector::value_type");
1579 static_assert(is_same<T&, typename Vector::reference>::value,
1580 "T& != Vector::reference");
1581 static_assert(is_same<const T&, typename Vector::const_reference>::value,
1582 "const T& != Vector::const_reference");
1583 static_assert(is_convertible<
1584 typename iterator_traits<typename Vector::iterator>::iterator_category,
1585 forward_iterator_tag>::value,
1586 "Vector::iterator is not a forward iterator");
1587 static_assert(is_same<T,
1588 typename iterator_traits<typename Vector::iterator>::value_type>::value,
1589 "Vector::iterator does not iterate over type T");
1590 static_assert(is_convertible<
1591 typename iterator_traits<typename Vector::const_iterator>
1592 ::iterator_category,
1593 forward_iterator_tag>::value,
1594 "Vector::const_iterator is not a forward iterator");
1595 static_assert(is_same<T,
1596 typename iterator_traits<typename Vector::const_iterator>
1597 ::value_type>::value,
1598 "Vector::const_iterator does not iterate over type T");
1599 static_assert(is_convertible<
1600 typename Vector::iterator, typename Vector::const_iterator>::value,
1601 "Vector::iterator is not convertible to Vector::const_iterator");
1602 static_assert(is_signed<typename Vector::difference_type>::value,
1603 "Vector::difference_type is not signed");
1604 static_assert(is_same<typename Vector::difference_type,
1605 typename iterator_traits<typename Vector::iterator>
1606 ::difference_type>::value,
1607 "Vector::difference_type != Vector::iterator::difference_type");
1608 static_assert(is_same<typename Vector::difference_type,
1609 typename iterator_traits<typename Vector::const_iterator>
1610 ::difference_type>::value,
1611 "Vector::difference_type != Vector::const_iterator::difference_type");
1612 static_assert(is_unsigned<typename Vector::size_type>::value,
1613 "Vector::size_type is not unsigned");
1614 static_assert(sizeof(typename Vector::size_type) >=
1615 sizeof(typename Vector::difference_type),
1616 "Vector::size_type is smaller than Vector::difference_type");
1619 STL_TEST("23.2.1 Table 96.8-9", emptyConstruction, is_destructible) {
1622 ASSERT_TRUE(u.get_allocator() == Allocator());
1623 ASSERT_EQ(0, Counter::CountTotalOps);
1625 ASSERT_TRUE(u.empty()) << u.size();
1626 ASSERT_EQ(0, u.capacity());
1633 STL_TEST("framework", populate, is_copy_constructible) {
1634 // We use emplace_back to construct vectors for testing, as well as size,
1635 // data, and capacity. We make sure these work before proceeding with tests.
1638 ASSERT_EQ(0, u.size());
1639 ASSERT_EQ(nullptr, u.data());
1642 ASSERT_EQ(1, u.size());
1643 ASSERT_LT(u.capacity(), 100)
1644 << "single push_back increased capacity to " << u.capacity();
1645 ASSERT_NE(nullptr, u.data());
1646 ASSERT_EQ(17, convertToInt(u.data()[0]))
1647 << "first object did not get emplaced correctly";
1649 for (int i = 0; i < 3; ++i) {
1650 auto cap = u.capacity();
1651 while (u.size() < cap) {
1653 ASSERT_EQ(cap, u.capacity()) << "Vector grew when it did not need to";
1654 ASSERT_EQ(22, convertToInt(u.data()[u.size() - 1]))
1655 << "push_back with excess capacity failed";
1658 ASSERT_EQ(cap, u.size());
1661 ASSERT_GT(u.capacity(), cap) << "capacity did not grow on overflow";
1662 ASSERT_EQ(cap + 1, u.size());
1663 ASSERT_EQ(4, convertToInt(u.data()[u.size() - 1]))
1664 << "grow object did not get emplaced correctly";
1668 STL_TEST("23.2.1 Table 96.10-11", copyConstruction,
1669 is_copy_constructible, a) {
1671 DataState<Vector> dsa(ca);
1672 auto am = a.get_allocator();
1676 ASSERT_TRUE(std::allocator_traits<Allocator>::
1677 select_on_container_copy_construction(am) == u.get_allocator());
1678 ASSERT_TRUE(dsa == u);
1680 (ca.data() == nullptr && u.data() == nullptr) ||
1681 (ca.data() != u.data())
1682 ) << "only a shallow copy was made";
1690 STL_TEST("23.2.1 Table 96.12", moveConstruction, is_destructible, a) {
1691 DataState<Vector> dsa(a);
1692 auto m = a.get_allocator();
1696 ASSERT_TRUE(m == u.get_allocator());
1697 ASSERT_EQ(0, Counter::CountTotalOps);
1699 ASSERT_TRUE(dsa == u);
1706 STL_TEST("23.2.1 Table 96.13", moveAssignment, special_move_assignable, a, b) {
1707 DataState<Vector> dsb(b);
1708 auto am = a.get_allocator();
1709 auto bm = b.get_allocator();
1711 Vector& ret = a = std::move(b);
1713 if (std::allocator_traits<Allocator>::
1714 propagate_on_container_move_assignment::value) {
1715 ASSERT_TRUE(bm == a.get_allocator());
1717 ASSERT_TRUE(am == a.get_allocator());
1719 ASSERT_TRUE(&ret == &a);
1720 ASSERT_TRUE(&a == &b || dsb == a) << "move assignment did not create a copy";
1721 // The source of the move may be left in any (albeit valid) state.
1724 STL_TEST("23.2.1 Table 96.14", destructible, is_destructible) {
1725 // The test generators check this clause already.
1728 STL_TEST("23.2.1 Table 96.15-18", iterators, is_destructible, a) {
1729 DataState<Vector> dsa(a);
1732 auto itb = a.begin();
1733 auto citb = ca.begin();
1734 auto Citb = a.cbegin();
1736 auto cite = ca.end();
1737 auto Cite = a.cend();
1739 ASSERT_EQ(0, Counter::CountTotalOps);
1741 ASSERT_TRUE(dsa == a) << "call to begin or end modified internal data";
1743 ASSERT_TRUE(citb == Citb) << "cv.begin != v.cbegin";
1744 ASSERT_TRUE(cite == Cite) << "cv.end != v.cend";
1746 if (ca.size() == 0) {
1747 ASSERT_TRUE( itb == ite) << "begin != end when empty";
1748 ASSERT_TRUE(Citb == Cite) << "cbegin != cend when empty";
1750 ASSERT_TRUE( itb != ite) << "begin == end when non-empty";
1751 ASSERT_TRUE(Citb != Cite) << "cbegin == cend when non-empty";
1754 auto dist = size_t(std::distance(itb, ite));
1755 auto Cdist = size_t(std::distance(Citb, Cite));
1756 ASSERT_TRUE( dist == ca.size()) << "distance(begin, end) != size";
1757 ASSERT_TRUE(Cdist == ca.size()) << "distance(cbegin, cend) != size";
1760 STL_TEST("23.2.1 Table 96.19-20", equitable, is_arithmetic, a, b) {
1763 DataState<Vector> dsa(a);
1764 DataState<Vector> dsb(b);
1766 ASSERT_TRUE((bool)(ca == cb) == (bool)(dsa == dsb))
1767 << "== does not return equality";
1768 ASSERT_TRUE((bool)(ca == cb) != (bool)(ca != cb))
1769 << "!= is not the opposite of ==";
1771 // Data is uncomparable, by design; therefore this test's restriction
1772 // is 'is_arithmetic'
1775 STL_TEST("23.2.1 Table 96.21", memberSwappable, is_destructible, a, b) {
1776 if (!std::allocator_traits<Allocator>::
1777 propagate_on_container_swap::value &&
1778 convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1779 // undefined behaviour
1783 DataState<Vector> dsa(a);
1784 DataState<Vector> dsb(b);
1785 auto adata = a.data();
1786 auto bdata = b.data();
1787 auto am = a.get_allocator();
1788 auto bm = b.get_allocator();
1793 FAIL() << "swap is noexcept";
1796 if (std::allocator_traits<Allocator>::
1797 propagate_on_container_swap::value) {
1798 ASSERT_TRUE(bm == a.get_allocator());
1799 ASSERT_TRUE(am == b.get_allocator());
1801 ASSERT_TRUE(am == a.get_allocator());
1802 ASSERT_TRUE(bm == b.get_allocator());
1804 ASSERT_EQ(0, Counter::CountTotalOps);
1806 ASSERT_TRUE(adata == b.data() && bdata == a.data());
1807 ASSERT_TRUE(dsa == b && dsb == a) << "swap did not swap";
1810 STL_TEST("23.2.1 Table 96.22", nonmemberSwappable,
1811 is_destructible, a, b) {
1812 if (!std::allocator_traits<Allocator>::
1813 propagate_on_container_swap::value &&
1814 convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1815 // undefined behaviour
1819 DataState<Vector> dsa(a);
1820 DataState<Vector> dsb(b);
1821 auto adata = a.data();
1822 auto bdata = b.data();
1823 auto am = a.get_allocator();
1824 auto bm = b.get_allocator();
1829 FAIL() << "swap is noexcept";
1832 if (std::allocator_traits<Allocator>::
1833 propagate_on_container_swap::value) {
1834 ASSERT_TRUE(bm == a.get_allocator());
1835 ASSERT_TRUE(am == b.get_allocator());
1837 ASSERT_TRUE(am == a.get_allocator());
1838 ASSERT_TRUE(bm == b.get_allocator());
1840 ASSERT_EQ(0, Counter::CountTotalOps);
1842 ASSERT_TRUE(adata == b.data() && bdata == a.data());
1843 ASSERT_TRUE(dsa == b && dsb == a) << "swap did not swap";
1846 STL_TEST("23.2.1 Table 96.23", copyAssign,
1847 is_copy_constructibleAndAssignable, a, b) {
1848 // it is possible to make use of just the copy constructor.
1850 #ifdef USING_STD_VECTOR
1851 if (std::allocator_traits<Allocator>::
1852 propagate_on_container_copy_assignment::value &&
1853 convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1854 // Bug. By the looks of things, in the above case, their bez is being
1855 // cleared and deallocated, but then the garbage pointers are being used.
1861 DataState<Vector> dsb(cb);
1862 auto am = a.get_allocator();
1863 auto bm = b.get_allocator();
1865 Vector& ret = a = cb;
1867 if (std::allocator_traits<Allocator>::
1868 propagate_on_container_copy_assignment::value) {
1869 ASSERT_TRUE(bm == a.get_allocator());
1871 ASSERT_TRUE(am == a.get_allocator());
1873 ASSERT_TRUE(&ret == &a);
1874 ASSERT_TRUE(dsb == a) << "copy-assign not equal to original";
1877 STL_TEST("23.2.1 Table 96.24-26", sizeops, is_destructible) {
1878 // This check generators check this clause already.
1881 //-----------------------------------------------------------------------------
1882 // Reversible container
1884 STL_TEST("23.2.1 Table 97.1-2", reversibleContainerTypedefs,
1886 static_assert(is_same<typename Vector::reverse_iterator,
1887 std::reverse_iterator<typename Vector::iterator>>::value,
1888 "Vector::reverse_iterator != reverse_iterator<Vector:iterator");
1889 static_assert(is_same<typename Vector::const_reverse_iterator,
1890 std::reverse_iterator<typename Vector::const_iterator>>::value,
1891 "Vector::const_reverse_iterator != "
1892 "const_reverse_iterator<Vector::iterator");
1895 STL_TEST("23.2.1 Table 97.3-5", reversibleIterators, is_destructible, a) {
1897 DataState<Vector> ds(a);
1899 auto ritb = a.rbegin();
1900 auto critb = ca.rbegin();
1901 auto Critb = a.crbegin();
1902 auto rite = a.rend();
1903 auto crite = ca.rend();
1904 auto Crite = a.crend();
1906 ASSERT_EQ(0, Counter::CountTotalOps);
1908 ASSERT_TRUE(ds == a) << "call to rbegin or rend modified internal data";
1910 ASSERT_TRUE(critb == Critb) << "cv.rbegin != v.crbegin";
1911 ASSERT_TRUE(crite == Crite) << "cv.rend != v.crend";
1913 if (ca.size() == 0) {
1914 ASSERT_TRUE( ritb == rite) << "rbegin != rend when empty";
1915 ASSERT_TRUE(Critb == Crite) << "crbegin != crend when empty";
1917 ASSERT_TRUE( ritb != rite) << "rbegin == rend when non-empty";
1918 ASSERT_TRUE(Critb != Crite) << "crbegin == crend when non-empty";
1921 auto dist = size_t(std::distance(ritb, rite));
1922 auto Cdist = size_t(std::distance(Critb, Crite));
1923 ASSERT_TRUE( dist == ca.size()) << "distance(rbegin, rend) != size";
1924 ASSERT_TRUE(Cdist == ca.size()) << "distance(crbegin, crend) != size";
1927 //-----------------------------------------------------------------------------
1928 // Lexicographical functions
1930 STL_TEST("23.2.1 Table 98", comparable, is_arithmetic) {
1931 const Vector v1 = { 1, 2, 3, 4 };
1932 const Vector v2 = { 1, 2, 3, 4, 5 };
1933 const Vector v3 = { 1, 2, 2 };
1934 const Vector v4 = { 1, 2, 2, 4, 5 };
1935 const Vector v5 = { };
1936 const Vector v6 = { 1, 2, 3, 4 };
1938 ASSERT_TRUE(v1 < v2);
1939 ASSERT_TRUE(v1 > v3);
1940 ASSERT_TRUE(v1 > v4);
1941 ASSERT_TRUE(v1 > v5);
1942 ASSERT_TRUE(v1 <= v6);
1943 ASSERT_TRUE(v1 >= v6);
1946 //-----------------------------------------------------------------------------
1947 // Allocator-aware requirements (AA)
1949 STL_TEST("23.2.1 Table 99.1", allocatorTypedefs, is_destructible) {
1950 static_assert(is_same<T, typename Vector::allocator_type::value_type>::value,
1951 "Vector and vector's allocator value_type mismatch");
1954 STL_TEST("23.2.1 Table 99.2", getAllocator, is_destructible) {
1955 // whitebox: ensure that a.get_allocator() returns a copy of its allocator
1958 STL_TEST("23.2.1 Table 99.3", defaultAllocator, is_destructible) {
1959 // there is nothing new to test here
1962 STL_TEST("23.2.1 Table 99.4", customAllocator, is_destructible, m) {
1967 ASSERT_TRUE(u.get_allocator() == m);
1974 STL_TEST("23.2.1 Table 99.5", copyWithAllocator, is_copy_constructible, a, m) {
1975 DataState<Vector> dsa(a);
1981 ASSERT_TRUE(u.get_allocator() == m);
1982 ASSERT_TRUE(dsa == u);
1984 (ca.data() == nullptr && u.data() == nullptr) ||
1985 (ca.data() != u.data())
1986 ) << "only a shallow copy was made";
1989 STL_TEST("23.2.1 Table 99.6", moveConstructionWithAllocator,
1990 is_destructible, a) {
1991 // there is nothing new to test here
1994 STL_TEST("23.2.1 Table 99.6", moveConstructionWithAllocatorSupplied,
1995 is_move_constructible, a, m) {
1996 bool deep = m != a.get_allocator();
1997 auto osize = a.size();
1998 auto oalloc = AllocTracker::Constructed;
2001 Vector u(std::move(a), cm);
2003 ASSERT_TRUE(u.get_allocator() == m);
2006 if (!AllocTracker::Allocated.empty()) {
2007 ASSERT_EQ(osize, AllocTracker::Constructed - oalloc);
2010 ASSERT_EQ(0, Counter::CountTotalOps);
2014 STL_TEST("23.2.1 Table 99.7-9", allocAssign, is_destructible) {
2015 // there is nothing new to test here
2018 STL_TEST("23.2.1-7", nAllocConstruction, is_copy_constructible, n, m) {
2019 #ifndef USING_STD_VECTOR
2024 ASSERT_TRUE(m == u.get_allocator());
2028 STL_TEST("23.2.1-7", nCopyAllocConstruction, is_copy_constructible, n, t, m) {
2032 Vector u(n, ct, cm);
2034 ASSERT_TRUE(m == u.get_allocator());
2037 STL_TEST("23.2.1-7", forwardIteratorAllocConstruction,
2038 is_destructible, i, j, m) {
2039 auto fi = makeForwardIterator(i);
2040 auto fj = makeForwardIterator(j);
2041 const auto& cfi = fi;
2042 const auto& cfj = fj;
2045 Vector u(cfi, cfj, cm);
2047 ASSERT_TRUE(m == u.get_allocator());
2050 STL_TEST("23.2.1-7", inputIteratorAllocConstruction,
2051 is_move_constructible, i, j, m) {
2052 #ifdef USING_STD_VECTOR
2053 if (Ticker::TicksLeft >= 0) return;
2056 auto ii = makeInputIterator(i);
2057 auto ij = makeInputIterator(j);
2058 const auto& cii = ii;
2059 const auto& cij = ij;
2062 Vector u(cii, cij, cm);
2064 ASSERT_TRUE(m == u.get_allocator());
2067 STL_TEST("23.2.1-7", ilAllocConstruction, is_arithmetic, m) {
2069 if (Ticker::TicksLeft >= 0) return;
2073 Vector u({ 1, 4, 7 }, cm);
2075 ASSERT_TRUE(m == u.get_allocator());
2078 //-----------------------------------------------------------------------------
2081 STL_TEST("23.2.2", dataRaces, is_destructible) {
2083 const Vector* cv = nullptr;
2084 typename Vector::size_type* s = nullptr;
2098 // White-box: check that the non-const versions of each of the above
2099 // functions is implemented in terms of (or the same as) the const version
2102 //-----------------------------------------------------------------------------
2103 // Sequence container
2105 STL_TEST("23.2.3 Table 100.1, alt", nConstruction, is_constructible, n) {
2108 ASSERT_TRUE(Allocator() == u.get_allocator());
2109 ASSERT_EQ(n, u.size());
2110 ASSERT_EQ(Counter::CountTotalOps, Counter::CountDC);
2113 STL_TEST("23.2.3 Table 100.1", nCopyConstruction,
2114 is_copy_constructible, n, t) {
2119 ASSERT_TRUE(Allocator() == u.get_allocator());
2120 ASSERT_EQ(n, u.size()) << "Vector(n, t).size() != n" << endl;
2121 for (const auto& val : u) ASSERT_EQ(convertToInt(t), convertToInt(val))
2122 << "not all elements of Vector(n, t) are equal to t";
2125 STL_TEST("23.2.3 Table 100.2", forwardIteratorConstruction,
2126 is_destructible, i, j) {
2127 // All data is emplace-constructible from int, so we restrict to
2130 auto fi = makeForwardIterator(i);
2131 auto fj = makeForwardIterator(j);
2132 const auto& cfi = fi;
2133 const auto& cfj = fj;
2137 ASSERT_TRUE(Allocator() == u.get_allocator());
2138 ASSERT_LE(Counter::CountTotalOps, j-i);
2140 ASSERT_EQ(j - i, u.size()) << "u(i,j).size() != j-i";
2141 for (auto it = u.begin(); it != u.end(); ++it, ++i)
2142 ASSERT_EQ(*i, convertToInt(*it)) << "u(i,j) constructed incorrectly";
2145 STL_TEST("23.2.3 Table 100.2", inputIteratorConstruction,
2146 is_move_constructible, i, j) {
2147 #ifdef USING_STD_VECTOR
2148 if (Ticker::TicksLeft >= 0) return;
2151 auto ii = makeInputIterator(i);
2152 auto ij = makeInputIterator(j);
2153 const auto& cii = ii;
2154 const auto& cij = ij;
2158 ASSERT_TRUE(Allocator() == u.get_allocator());
2159 ASSERT_EQ(j - i, u.size()) << "u(i,j).size() != j-i";
2160 for (auto it = u.begin(); it != u.end(); ++it, ++i)
2161 ASSERT_EQ(*i, convertToInt(*it)) << "u(i,j) constructed incorrectly";
2164 STL_TEST("23.2.3 Table 100.3", ilConstruction, is_arithmetic) {
2165 // whitebox: ensure that Vector(il) is implemented in terms of
2166 // Vector(il.begin(), il.end())
2169 if (Ticker::TicksLeft >= 0) return;
2171 Vector u = { 1, 4, 7 };
2173 ASSERT_TRUE(Allocator() == u.get_allocator());
2174 ASSERT_EQ(3, u.size()) << "u(il).size() fail";
2176 auto it = u.begin();
2177 for (; it != u.end(); ++it, i += 3)
2178 ASSERT_EQ(i, convertToInt(*it)) << "u(il) constructed incorrectly";
2181 STL_TEST("23.2.3 Table 100.4", ilAssignment,
2183 // whitebox: ensure that assign(il) is implemented in terms of
2184 // assign(il.begin(), il.end())
2187 if (Ticker::TicksLeft >= 0) return;
2189 auto am = a.get_allocator();
2191 Vector& b = a = { 1, 4, 7 };
2193 ASSERT_TRUE(am == a.get_allocator());
2194 ASSERT_TRUE(&b == &a) << "'a = ...' did not return *this";
2196 ASSERT_EQ(3, a.size()) << "u(il).size() fail";
2198 auto it = a.begin();
2199 for (; it != a.end(); ++it, i += 3)
2200 ASSERT_EQ(i, convertToInt(*it)) << "u(il) constructed incorrectly";
2203 //----------------------------
2204 // insert-and-erase subsection
2206 template <class Vector>
2207 void insertNTCheck(const Vector& a, DataState<Vector>& dsa,
2208 int idx, int n, int val) {
2209 ASSERT_EQ(dsa.size() + n, a.size());
2211 for (; i < idx; ++i) {
2212 ASSERT_EQ(dsa[i], convertToInt(a.data()[i])) << i;
2214 for (; i < idx + n; ++i) {
2215 ASSERT_EQ(val, convertToInt(a.data()[i])) << i;
2217 for (; size_t(i) < a.size(); ++i) {
2218 ASSERT_EQ(dsa[i-n], convertToInt(a.data()[i])) << i;
2222 STL_TEST("23.2.3 Table 100.5", iteratorEmplacement,
2223 is_move_constructibleAndAssignable, a, p) {
2224 DataState<Vector> dsa(a);
2225 int idx = distance(a.begin(), p);
2226 auto am = a.get_allocator();
2228 auto q = a.emplace(p, 44);
2230 ASSERT_TRUE(am == a.get_allocator());
2231 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2232 insertNTCheck(a, dsa, idx, 1, 44);
2235 STL_TEST("23.2.3 Table 100.6", iteratorInsertion,
2236 is_copy_constructibleAndAssignable, a, p, t) {
2237 DataState<Vector> dsa(a);
2238 int idx = distance(a.begin(), p);
2239 int tval = convertToInt(t);
2240 auto am = a.get_allocator();
2243 auto q = a.insert(p, ct);
2245 ASSERT_TRUE(am == a.get_allocator());
2246 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2247 insertNTCheck(a, dsa, idx, 1, tval);
2250 STL_TEST("23.2.3 Table 100.7", iteratorInsertionRV,
2251 is_move_constructibleAndAssignable, a, p, t) {
2252 // rvalue-references cannot have their address checked for aliased inserts
2253 if (a.data() <= addressof(t) && addressof(t) < a.data() + a.size()) return;
2255 DataState<Vector> dsa(a);
2256 int idx = distance(a.begin(), p);
2257 int tval = convertToInt(t);
2258 auto am = a.get_allocator();
2260 auto q = a.insert(p, std::move(t));
2262 ASSERT_TRUE(am == a.get_allocator());
2263 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2264 insertNTCheck(a, dsa, idx, 1, tval);
2267 STL_TEST("23.2.3 Table 100.8", iteratorInsertionN,
2268 is_copy_constructibleAndAssignable, a, p, n, t) {
2269 DataState<Vector> dsa(a);
2270 int idx = distance(a.begin(), p);
2271 int tval = convertToInt(t);
2272 auto am = a.get_allocator();
2275 #ifndef USING_STD_VECTOR
2281 ASSERT_TRUE(am == a.get_allocator());
2282 #ifndef USING_STD_VECTOR
2283 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2286 insertNTCheck(a, dsa, idx, n, tval);
2289 template <class Vector>
2290 void insertItCheck(const Vector& a, DataState<Vector>& dsa,
2291 int idx, int* b, int* e) {
2292 ASSERT_EQ(dsa.size() + (e - b), a.size());
2294 for (; i < idx; ++i) {
2295 ASSERT_EQ(dsa[i], convertToInt(a.data()[i]));
2297 for (; i < idx + (e - b); ++i) {
2298 ASSERT_EQ(*(b + i - idx), convertToInt(a.data()[i]));
2300 for (; size_t(i) < a.size(); ++i) {
2301 ASSERT_EQ(dsa[i - (e - b)], convertToInt(a.data()[i]));
2305 STL_TEST("23.2.3 Table 100.9", iteratorInsertionIterator,
2306 is_move_constructibleAndAssignable, a, p, i, j) {
2307 DataState<Vector> dsa(a);
2308 int idx = distance(a.begin(), p);
2310 auto fi = makeForwardIterator(i);
2311 auto fj = makeForwardIterator(j);
2312 auto am = a.get_allocator();
2313 const auto& cfi = fi;
2314 const auto& cfj = fj;
2316 #ifndef USING_STD_VECTOR
2320 a.insert(p, cfi, cfj);
2322 ASSERT_TRUE(am == a.get_allocator());
2323 #ifndef USING_STD_VECTOR
2324 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2327 insertItCheck(a, dsa, idx, i, j);
2330 STL_TEST("23.2.3 Table 100.9", iteratorInsertionInputIterator,
2331 is_move_constructibleAndAssignable, a, p, i, j) {
2332 DataState<Vector> dsa(a);
2333 int idx = distance(a.begin(), p);
2335 auto ii = makeInputIterator(i);
2336 auto ij = makeInputIterator(j);
2337 auto am = a.get_allocator();
2338 const auto& cii = ii;
2339 const auto& cij = ij;
2341 #ifndef USING_STD_VECTOR
2345 a.insert(p, cii, cij);
2347 ASSERT_TRUE(am == a.get_allocator());
2348 #ifndef USING_STD_VECTOR
2349 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2352 insertItCheck(a, dsa, idx, i, j);
2355 STL_TEST("23.2.3 Table 100.10", iteratorInsertIL,
2356 is_arithmetic, a, p) {
2358 if (Ticker::TicksLeft >= 0) return;
2360 // whitebox: ensure that insert(p, il) is implemented in terms of
2361 // insert(p, il.begin(), il.end())
2363 DataState<Vector> dsa(a);
2364 int idx = distance(a.begin(), p);
2365 auto am = a.get_allocator();
2367 #ifndef USING_STD_VECTOR
2371 a.insert(p, {1, 4, 7});
2373 ASSERT_TRUE(am == a.get_allocator());
2374 #ifndef USING_STD_VECTOR
2375 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2378 int ila[] = { 1, 4, 7 };
2381 insertItCheck(a, dsa, idx, i, j);
2384 template <class Vector>
2385 void eraseCheck(Vector& a, DataState<Vector>& dsa, int idx, int n) {
2386 ASSERT_EQ(dsa.size() - n, a.size());
2388 auto it = a.begin();
2389 for (; it != a.end(); ++it, ++i) {
2390 if (i == idx) i += n;
2391 ASSERT_EQ(dsa[i], convertToInt(*it));
2395 STL_TEST("23.2.3 Table 100.11", iteratorErase, is_move_assignable, a, p) {
2396 if (p == a.end()) return;
2398 DataState<Vector> dsa(a);
2399 int idx = distance(a.begin(), p);
2400 auto am = a.get_allocator();
2402 auto rit = a.erase(p);
2404 ASSERT_TRUE(am == a.get_allocator());
2405 ASSERT_EQ(idx, distance(a.begin(), rit)) << "wrong iterator returned";
2406 eraseCheck(a, dsa, idx, 1);
2409 STL_TEST("23.2.3 Table 100.12", iteratorEraseRange,
2410 is_move_assignable, a, p, q) {
2411 if (p == a.end()) return;
2413 DataState<Vector> dsa(a);
2414 int idx = distance(a.begin(), p);
2415 auto am = a.get_allocator();
2417 auto rit = a.erase(p, q);
2419 ASSERT_TRUE(am == a.get_allocator());
2420 ASSERT_EQ(idx, distance(a.begin(), rit)) << "wrong iterator returned";
2421 eraseCheck(a, dsa, idx, distance(p,q));
2424 //--------------------------------
2425 // end insert-and-erase subsection
2427 STL_TEST("23.2.3 Table 100.13", clear, is_destructible, a) {
2429 auto am = a.get_allocator();
2434 FAIL() << "clear must be noexcept";
2437 ASSERT_TRUE(am == a.get_allocator());
2438 ASSERT_TRUE(a.empty());
2441 STL_TEST("23.2.3 Table 100.14", assignRange, is_move_assignable, a, i, j) {
2442 auto fi = makeForwardIterator(i);
2443 auto fj = makeForwardIterator(j);
2444 const auto& cfi = fi;
2445 const auto& cfj = fj;
2446 auto am = a.get_allocator();
2450 ASSERT_TRUE(am == a.get_allocator());
2451 ASSERT_EQ(distance(i, j), a.size());
2452 for (auto it = a.begin(); it != a.end(); ++it, ++i)
2453 ASSERT_EQ(*i, convertToInt(*it));
2456 STL_TEST("23.2.3 Table 100.14", assignInputRange,
2457 is_move_constructibleAndAssignable, a, i, j) {
2458 auto ii = makeInputIterator(i);
2459 auto ij = makeInputIterator(j);
2460 const auto& cii = ii;
2461 const auto& cij = ij;
2462 auto am = a.get_allocator();
2466 ASSERT_TRUE(am == a.get_allocator());
2467 ASSERT_EQ(distance(i, j), a.size());
2468 for (auto it = a.begin(); it != a.end(); ++it, ++i)
2469 ASSERT_EQ(*i, convertToInt(*it));
2472 STL_TEST("23.2.3 Table 100.15", assignIL,
2475 // whitebox: ensure that assign(il) is implemented in terms of
2476 // assign(il.begin(), il.end())
2479 if (Ticker::TicksLeft >= 0) return;
2481 auto am = a.get_allocator();
2483 a.assign({1, 4, 7});
2485 ASSERT_TRUE(am == a.get_allocator());
2486 int ila[] = { 1, 4, 7 };
2489 ASSERT_EQ(3, a.size());
2490 for (auto it = a.begin(); it != a.end(); ++it, ++i)
2491 ASSERT_EQ(*i, convertToInt(*it));
2494 STL_TEST("23.2.3 Table 100.16", assignN,
2495 is_copy_constructibleAndAssignable, a, n, t) {
2496 auto am = a.get_allocator();
2498 auto tval = convertToInt(t);
2502 ASSERT_TRUE(am == a.get_allocator());
2503 ASSERT_EQ(n, a.size());
2504 for (auto it = a.begin(); it != a.end(); ++it)
2505 ASSERT_EQ(tval, convertToInt(*it));
2508 STL_TEST("23.2.3 Table 101.1", front, is_destructible, a) {
2509 if (a.empty()) return;
2511 ASSERT_TRUE(addressof(a.front()) == a.data());
2513 ASSERT_EQ(0, Counter::CountTotalOps);
2517 const Vector& ca = a;
2522 STL_TEST("23.2.3 Table 101.2", back, is_destructible, a) {
2523 if (a.empty()) return;
2525 ASSERT_TRUE(addressof(a.back()) == a.data() + a.size() - 1);
2527 ASSERT_EQ(0, Counter::CountTotalOps);
2531 const Vector& ca = a;
2536 STL_TEST("23.2.3 Table 101.4", emplaceBack,
2537 is_move_constructible, a) {
2538 DataState<Vector> dsa(a);
2539 auto adata = a.data();
2540 int excess = a.capacity() - a.size();
2541 auto am = a.get_allocator();
2546 ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2550 ASSERT_TRUE(am == a.get_allocator());
2551 if (excess > 0) ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2552 ASSERT_EQ(dsa.size() + 1, a.size());
2554 auto it = a.begin();
2555 for (; i < dsa.size(); ++i, ++it)
2556 ASSERT_EQ(dsa[i], convertToInt(*it));
2557 ASSERT_EQ(44, convertToInt(a.back()));
2560 STL_TEST("23.2.3 Table 101.7", pushBack, is_copy_constructible, a, t) {
2561 DataState<Vector> dsa(a);
2562 int tval = convertToInt(t);
2563 auto adata = a.data();
2564 int excess = a.capacity() - a.size();
2565 auto am = a.get_allocator();
2571 ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2575 ASSERT_TRUE(am == a.get_allocator());
2576 if (excess > 0) ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2577 ASSERT_EQ(dsa.size() + 1, a.size());
2579 auto it = a.begin();
2580 for (; i < dsa.size(); ++i, ++it)
2581 ASSERT_EQ(dsa[i], convertToInt(*it));
2582 ASSERT_EQ(tval, convertToInt(a.back()));
2585 STL_TEST("23.2.3 Table 101.8", pushBackRV,
2586 is_move_constructible, a, t) {
2587 DataState<Vector> dsa(a);
2588 int tval = convertToInt(t);
2589 auto adata = a.data();
2590 int excess = a.capacity() - a.size();
2591 auto am = a.get_allocator();
2594 a.push_back(move(t));
2596 ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2600 ASSERT_TRUE(am == a.get_allocator());
2601 if (excess > 0) ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2602 ASSERT_EQ(dsa.size() + 1, a.size());
2604 auto it = a.begin();
2605 for (; i < dsa.size(); ++i, ++it)
2606 ASSERT_EQ(dsa[i], convertToInt(*it));
2607 ASSERT_EQ(tval, convertToInt(a.back()));
2610 STL_TEST("23.2.3 Table 100.10", popBack, is_destructible, a) {
2611 if (a.empty()) return;
2613 DataState<Vector> dsa(a);
2614 auto am = a.get_allocator();
2618 ASSERT_TRUE(am == a.get_allocator());
2619 ASSERT_EQ(dsa.size() - 1, a.size());
2621 auto it = a.begin();
2622 for (; it != a.end(); ++it, ++i)
2623 ASSERT_EQ(dsa[i], convertToInt(*it));
2626 STL_TEST("23.2.3 Table 100.11", operatorBrace, is_destructible, a) {
2628 for (size_t i = 0; i < ca.size(); ++i)
2629 ASSERT_TRUE(addressof(ca[i]) == ca.data()+i);
2631 ASSERT_EQ(0, Counter::CountTotalOps);
2638 STL_TEST("23.2.3 Table 100.12", at, is_destructible, a) {
2640 for (size_t i = 0; i < ca.size(); ++i)
2641 ASSERT_TRUE(addressof(ca.at(i)) == ca.data()+i);
2643 ASSERT_EQ(0, Counter::CountTotalOps);
2647 FAIL() << "at(size) should have thrown an error";
2648 } catch (const std::out_of_range& e) {
2650 FAIL() << "at(size) threw error other than out_of_range";
2658 STL_TEST("move iterators", moveIterators, is_copy_constructibleAndAssignable) {
2663 auto mfi = make_move_iterator(makeForwardIterator(i));
2664 auto mfj = make_move_iterator(makeForwardIterator(j));
2665 auto mii = make_move_iterator(makeInputIterator(i));
2666 auto mij = make_move_iterator(makeInputIterator(j));
2668 Vector u1(mfi, mfj);
2669 Vector u2(mii, mij);
2671 u1.insert(u1.begin(), mfi, mfj);
2672 u1.insert(u1.begin(), mii, mij);
2674 u1.assign(mfi, mfj);
2675 u1.assign(mii, mij);
2679 //-----------------------------------------------------------------------------
2682 STL_TEST("23.3.6.4", dataAndCapacity, is_destructible) {
2683 // there isn't anything new to test here - data and capacity are used as the
2684 // backbone of DataState. The minimal testing we might want to do is already
2685 // done in the populate test
2688 STL_TEST("23.3.6.3", reserve, is_move_constructible, a, n) {
2689 auto adata = a.data();
2690 auto ocap = a.capacity();
2691 auto am = a.get_allocator();
2695 ASSERT_TRUE(am == a.get_allocator());
2696 if (size_t(n) <= ocap) {
2697 ASSERT_EQ(0, Counter::CountTotalOps);
2698 ASSERT_TRUE(adata == a.data());
2700 ASSERT_TRUE(a.capacity() >= size_t(n));
2701 ASSERT_LE(Counter::CountTotalOps, 2*a.size()); // move and delete
2705 STL_TEST("23.3.6.3", lengthError, is_move_constructible) {
2706 auto mx = Vector().max_size();
2708 if (mx >= big) return; // max_size is the biggest size_type; overflowed
2713 FAIL() << "reserve(big) should have thrown an error";
2714 } catch (const std::length_error& e) {
2716 FAIL() << "reserve(big) threw error other than length_error";
2720 STL_TEST("23.3.6.3", resize, is_copy_constructible, a, n) {
2721 DataState<Vector> dsa(a);
2723 auto am = a.get_allocator();
2727 ASSERT_TRUE(am == a.get_allocator());
2728 ASSERT_EQ(n, a.size());
2731 for (int i = 0; i < n; ++i) {
2732 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2735 for (int i = 0; i < sz; ++i) {
2736 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2741 STL_TEST("23.3.6.3", resizeT, is_copy_constructibleAndAssignable, a, n, t) {
2742 #ifdef USING_STD_VECTOR
2743 if (a.data() <= addressof(t) && addressof(t) < a.data() + a.size()) return;
2746 DataState<Vector> dsa(a);
2748 auto am = a.get_allocator();
2750 int val = convertToInt(t);
2754 ASSERT_TRUE(am == a.get_allocator());
2755 ASSERT_EQ(n, a.size());
2758 for (int i = 0; i < n; ++i) {
2759 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2763 for ( ; i < sz; ++i) {
2764 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2766 for ( ; i < n; ++i) {
2767 ASSERT_EQ(val, convertToInt(a[i]));
2772 STL_TEST("23.3.6.3", shrinkToFit, is_move_constructible, a) {
2773 bool willThrow = Ticker::TicksLeft >= 0;
2775 a.reserve(a.capacity() * 11);
2777 auto ocap = a.capacity();
2778 DataState<Vector> dsa(a);
2780 auto am = a.get_allocator();
2785 FAIL() << "shrink_to_fit should swallow errors";
2788 ASSERT_TRUE(am == a.get_allocator());
2789 ASSERT_TRUE(dsa == a);
2791 //ASSERT_EQ(ocap, a.capacity()); might shrink in place
2792 throw TickException("I swallowed the error");
2794 ASSERT_TRUE(a.capacity() == 0 || a.capacity() < ocap) << "Look into this";
2798 #ifndef USING_STD_VECTOR
2799 STL_TEST("EBO", ebo, is_destructible) {
2800 static_assert(!is_same<Allocator, std::allocator<T>>::value ||
2801 sizeof(Vector) == 3 * sizeof(void*),
2802 "fbvector has default allocator, but has size != 3*sizeof(void*)");
2805 STL_TEST("relinquish", relinquish, is_destructible, a) {
2807 auto cap = a.capacity();
2808 auto data = a.data();
2810 auto guts = relinquish(a);
2812 ASSERT_EQ(data, guts);
2813 ASSERT_TRUE(a.empty());
2814 ASSERT_EQ(0, a.capacity());
2816 auto alloc = a.get_allocator();
2817 for (size_t i = 0; i < sz; ++i)
2818 std::allocator_traits<decltype(alloc)>::destroy(alloc, guts + i);
2819 if (guts != nullptr)
2820 std::allocator_traits<decltype(alloc)>::deallocate(alloc, guts, cap);
2823 STL_TEST("attach", attach, is_destructible, a) {
2824 DataState<Vector> dsa(a);
2827 auto cap = a.capacity();
2828 auto guts = relinquish(a);
2830 ASSERT_EQ(a.data(), nullptr);
2831 attach(a, guts, sz, cap);
2833 ASSERT_TRUE(dsa == a);
2840 int main(int argc, char** argv) {
2841 testing::InitGoogleTest(&argc, argv);
2842 gflags::ParseCommandLineFlags(&argc, &argv, true);
2844 return RUN_ALL_TESTS();