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")
197 FOLLY_GCC_DISABLE_WARNING("-Wunused-variable")
200 using namespace folly;
202 //=============================================================================
203 //=============================================================================
206 //-----------------------------------------------------------------------------
209 typedef uint32_t Flags;
211 // each method has 3 options: normal, noexcept, throw, and deleted
212 // normal is the default
213 // throw is mutually exclusive with noexcept
215 // DC - default constructor
216 // CC - copy constructor
217 // MC - move constructor
218 // OC - other constructor
219 // CA - copy assignment
220 // MA - move assignment
221 enum FlagVals : Flags {
242 ALL_DELETE = DC_DELETE | CC_DELETE | MC_DELETE
243 | CA_DELETE | MA_DELETE,
249 PROP_COPY = 0x100000,
250 PROP_MOVE = 0x200000,
251 PROP_SWAP = 0x400000,
254 //-----------------------------------------------------------------------------
257 template <bool b> struct D0 {
259 D0(const D0&) = default;
261 explicit D0(std::nullptr_t) {}
262 D0& operator=(const D0&) = default;
263 D0& operator=(D0&&) = default;
265 template <> struct D0<true> {
267 D0(const D0&) = default;
269 explicit D0(std::nullptr_t) {}
270 D0& operator=(const D0&) = default;
271 D0& operator=(D0&&) = default;
274 template <bool b> struct D1 {
276 D1(const D1&) = default;
278 explicit D1(std::nullptr_t) {}
279 D1& operator=(const D1&) = default;
280 D1& operator=(D1&&) = default;
282 template <> struct D1<true> {
284 D1(const D1&) = delete;
286 explicit D1(std::nullptr_t) {}
287 D1& operator=(const D1&) = default;
288 D1& operator=(D1&&) = default;
291 template <bool b> struct D2 {
293 D2(const D2&) = default;
295 explicit D2(std::nullptr_t) {}
296 D2& operator=(const D2&) = default;
297 D2& operator=(D2&&) = default;
299 template <> struct D2<true> {
301 D2(const D2&) = default;
303 explicit D2(std::nullptr_t) {}
304 D2& operator=(const D2&) = default;
305 D2& operator=(D2&&) = default;
308 template <bool b> struct D3 {
310 D3(const D3&) = default;
312 explicit D3(std::nullptr_t) {}
313 D3& operator=(const D3&) = default;
314 D3& operator=(D3&&) = default;
316 template <> struct D3<true> {
318 D3(const D3&) = default;
320 explicit D3(std::nullptr_t) {}
321 D3& operator=(const D3&) = delete;
322 D3& operator=(D3&&) = default;
325 template <bool b> struct D4 {
327 D4(const D4&) = default;
329 explicit D4(std::nullptr_t) {}
330 D4& operator=(const D4&) = default;
331 D4& operator=(D4&&) = default;
333 template <> struct D4<true> {
335 D4(const D4&) = default;
337 explicit D4(std::nullptr_t) {}
338 D4& operator=(const D4&) = default;
339 D4& operator=(D4&&) = delete;
343 struct Delete : D0<(f & DC_DELETE) != 0>,
344 D1<(f & CC_DELETE) != 0>,
345 D2<(f & MC_DELETE) != 0>,
346 D3<(f & CA_DELETE) != 0>,
347 D4<(f & MA_DELETE) != 0> {
349 Delete(const Delete&) = default;
350 Delete(Delete&&) = default;
351 Delete& operator=(const Delete&) = default;
352 Delete& operator=(Delete&&) = default;
354 explicit Delete(std::nullptr_t) :
355 D0<(f & DC_DELETE) != 0>(nullptr),
356 D1<(f & CC_DELETE) != 0>(nullptr),
357 D2<(f & MC_DELETE) != 0>(nullptr),
358 D3<(f & CA_DELETE) != 0>(nullptr),
359 D4<(f & MA_DELETE) != 0>(nullptr)
363 //-----------------------------------------------------------------------------
366 struct TickException : std::runtime_error {
367 explicit TickException(const std::string& s)
368 : std::runtime_error("tick: " + s) {}
372 static int CountTicks;
373 static int TicksLeft;
374 static void Tick(const std::string& s) {
375 if (TicksLeft == 0) {
376 throw TickException(s);
383 int Ticker::CountTicks = 0;
384 int Ticker::TicksLeft = -1;
387 struct DataTicker : Ticker {
388 DataTicker() noexcept(f & DC_NOEXCEPT) {
389 if (!(f & DC_NOEXCEPT)) {
393 DataTicker(const DataTicker&) noexcept((f & CC_NOEXCEPT) != 0) {
394 if (!(f & CC_NOEXCEPT)) {
395 Tick("Data(const Data&)");
398 DataTicker(DataTicker&&) noexcept((f & MC_NOEXCEPT) != 0) {
399 if (!(f & MC_NOEXCEPT)) {
400 Tick("Data(Data&&)");
403 explicit DataTicker(std::nullptr_t) noexcept((f & OC_NOEXCEPT) != 0) {
404 if (!(f & OC_NOEXCEPT)) {
408 ~DataTicker() noexcept {}
409 void operator=(const DataTicker&) noexcept((f & CA_NOEXCEPT) != 0) {
410 if (!(f & CA_NOEXCEPT)) {
411 Tick("op=(const Data&)");
414 void operator=(DataTicker&&) noexcept((f & MA_NOEXCEPT) != 0) {
415 if (!(f & MA_NOEXCEPT)) {
421 //-----------------------------------------------------------------------------
431 static int CountDestroy;
432 static int CountTotalOps;
433 static int CountLoggedConstruction;
439 Counter(const Counter&) noexcept {
443 Counter(Counter&&) noexcept {
447 explicit Counter(std::nullptr_t) noexcept {
451 void operator=(const Counter&) noexcept {
455 void operator=(Counter&&) noexcept {
459 ~Counter() noexcept {
465 int Counter::CountDC = 0;
466 int Counter::CountCC = 0;
467 int Counter::CountMC = 0;
468 int Counter::CountOC = 0;
469 int Counter::CountCA = 0;
470 int Counter::CountMA = 0;
471 int Counter::CountDestroy = 0;
472 int Counter::CountTotalOps = 0;
473 int Counter::CountLoggedConstruction = 0;
475 //-----------------------------------------------------------------------------
480 static std::map<int, int> UIDCount;
482 static std::map<const Tracker*, int> Locations;
488 Tracker(Tracker* self, int uid) : self(self), uid(uid) {}
491 template <bool isRelocatable>
492 struct DataTracker : Tracker {
493 DataTracker() noexcept : Tracker(this, UID++) {
496 if (!isRelocatable) {
497 Locations[self] = uid;
501 DataTracker(const DataTracker& o) noexcept : Tracker(this, o.uid) {
504 if (!isRelocatable) {
505 Locations[self] = uid;
507 print("Data(const Data&)");
509 DataTracker(DataTracker&& o) noexcept : Tracker(this, o.uid) {
512 if (!isRelocatable) {
513 Locations[self] = uid;
515 print("Data(Data&&)");
518 explicit DataTracker(int uid) noexcept : Tracker(this, uid) {
521 if (!isRelocatable) {
522 Locations[self] = uid;
527 ~DataTracker() noexcept {
530 if (!isRelocatable) {
531 Locations.erase(self);
535 self = (DataTracker*)0xfeebdaed;
538 DataTracker& operator=(const DataTracker& o) noexcept {
542 if (!isRelocatable) {
543 Locations[self] = uid;
545 print("op=(const Data&)");
548 DataTracker& operator=(DataTracker&& o) noexcept {
552 if (!isRelocatable) {
553 Locations[self] = uid;
555 print("op=(Data&&)");
559 void print(const std::string& fun) {
561 std::cerr << std::setw(20) << fun << ": uid = " << std::setw(3) << uid;
562 if (!isRelocatable) {
563 std::cerr << ", self = " << self;
565 std::cerr << std::endl;
570 int Tracker::UID = 1234;
571 std::map<int, int> Tracker::UIDCount;
572 int Tracker::UIDTotal = 0;
573 std::map<const Tracker*, int> Tracker::Locations;
574 bool Tracker::Print = false;
576 //-----------------------------------------------------------------------------
577 //-----------------------------------------------------------------------------
580 template <Flags f = 0, size_t pad = 0>
581 struct Data : DataTracker<(f & IS_RELOCATABLE) != 0>,
582 Counter, DataTicker<f>, Delete<f> {
583 static const Flags flags = f;
584 char spacehog[pad ? pad : 1];
587 Data(const Data&) = default;
588 Data(Data&&) = default;
589 /* implicit */ Data(int i) :
590 DataTracker<(f & IS_RELOCATABLE) != 0>(i),
592 DataTicker<f>(nullptr),
596 Data& operator=(const Data&) = default;
597 Data& operator=(Data&&) = default;
600 int operator&() const;
604 template <Flags f, size_t pad>
605 struct IsRelocatable<Data<f, pad>>
606 : std::integral_constant<bool,
607 (f & IS_RELOCATABLE) != 0
611 //-----------------------------------------------------------------------------
612 //-----------------------------------------------------------------------------
615 template <typename T>
616 struct isPropCopy : true_type {};
617 template <Flags f, size_t pad>
618 struct isPropCopy<Data<f, pad>> :
619 std::integral_constant<bool, (f & PROP_COPY) != 0> {};
621 template <typename T>
622 struct isPropMove : true_type {};
623 template <Flags f, size_t pad>
624 struct isPropMove<Data<f, pad>> :
625 std::integral_constant<bool, (f & PROP_MOVE) != 0> {};
627 template <typename T>
628 struct isPropSwap : true_type {};
629 template <Flags f, size_t pad>
630 struct isPropSwap<Data<f, pad>> :
631 std::integral_constant<bool, (f & PROP_SWAP) != 0> {};
634 struct AllocTracker {
635 static int Constructed;
636 static int Destroyed;
637 static map<void*, size_t> Allocated;
638 static map<void*, int> Owner;
640 int AllocTracker::Constructed = 0;
641 int AllocTracker::Destroyed = 0;
642 map<void*, size_t> AllocTracker::Allocated;
643 map<void*, int> AllocTracker::Owner;
646 struct Alloc : AllocTracker, Ticker {
647 typedef typename std::allocator<T>::pointer pointer;
648 typedef typename std::allocator<T>::const_pointer const_pointer;
649 typedef typename std::allocator<T>::difference_type difference_type;
650 typedef typename std::allocator<T>::size_type size_type;
651 typedef typename std::allocator<T>::value_type value_type;
658 explicit Alloc(int i = 8) : a(), id(i) {}
659 Alloc(const Alloc& o) : a(o.a), id(o.id) {}
660 Alloc(Alloc&& o) noexcept : a(move(o.a)), id(o.id) {}
661 Alloc& operator=(const Alloc&) = default;
662 Alloc& operator=(Alloc&&) noexcept = default;
663 bool operator==(const Alloc& o) const { return a == o.a && id == o.id; }
664 bool operator!=(const Alloc& o) const { return !(*this == o); }
669 pointer allocate(size_type n) {
671 cerr << "called allocate(0)" << endl;
672 throw runtime_error("allocate fail");
675 auto p = a.allocate(n);
681 void deallocate(pointer p, size_type n) {
683 cerr << "deallocate(nullptr, " << n << ")" << endl;
684 FAIL() << "deallocate failed";
686 if (Allocated[p] != n) {
687 cerr << "deallocate(" << p << ", " << n << ") invalid: ";
688 if (Allocated[p] == 0) {
689 cerr << "never allocated";
690 } else if (Allocated[p] == size_t(-1)) {
691 cerr << "already deallocated";
693 cerr << "wrong number (want " << Allocated[p] << ")";
696 FAIL() << "deallocate failed";
698 if (Owner[p] != id) {
699 cerr << "deallocate(" << p << "), where pointer is owned by "
700 << Owner[p] << ", instead of self - " << id << endl;
701 FAIL() << "deallocate failed";
707 template <class U, class... Args>
708 void construct(U* p, Args&&... args) {
710 a.construct(p, std::forward<Args>(args)...);
723 Alloc select_on_container_copy_construction() const {
724 Tick("select allocator for copy");
725 return Alloc(id + 1);
728 typedef isPropCopy<T> propagate_on_container_copy_assignment;
729 typedef isPropMove<T> propagate_on_container_move_assignment;
730 typedef isPropSwap<T> propagate_on_container_swap;
733 //=============================================================================
734 //=============================================================================
735 // Verification and resetting
737 void softReset(int ticks = -1) {
738 Counter::CountLoggedConstruction +=
739 Counter::CountDC + Counter::CountCC + Counter::CountMC
740 + Counter::CountOC - Counter::CountDestroy;
741 Counter::CountDC = Counter::CountCC = Counter::CountMC
742 = Counter::CountOC = Counter::CountCA = Counter::CountMA = 0;
743 Counter::CountDestroy = Counter::CountTotalOps = 0;
744 Ticker::CountTicks = 0;
745 Ticker::TicksLeft = ticks;
749 Tracker::UIDCount.clear();
750 Tracker::UIDTotal = 0;
751 Tracker::Locations.clear();
753 Counter::CountLoggedConstruction = 0;
755 AllocTracker::Constructed = 0;
756 AllocTracker::Destroyed = 0;
757 AllocTracker::Allocated.clear();
758 AllocTracker::Owner.clear();
762 int con = Counter::CountDC + Counter::CountCC
763 + Counter::CountMC + Counter::CountOC
764 + Counter::CountLoggedConstruction;
765 int del = Counter::CountDestroy;
770 int tot = getTotal();
771 ASSERT_GE(tot, 0) << "more objects deleted than constructed";
773 ASSERT_EQ(tot, Tracker::UIDTotal)
774 << "UIDTotal has incorrect number of objects";
777 for (const auto& kv : Tracker::UIDCount) {
778 ASSERT_TRUE(kv.second >= 0) << "there exists " << kv.second << " Data "
779 "with uid " << kv.first;
782 ASSERT_EQ(tot, altTot) << "UIDCount corrupted";
784 if (!Tracker::Locations.empty()) { // implied by IsRelocatable
785 ASSERT_EQ(tot, Tracker::Locations.size())
786 << "Locations has incorrect number of objects";
787 for (const auto& du : Tracker::Locations) {
788 ASSERT_EQ(du.second, du.first->uid) << "Locations contains wrong uid";
789 ASSERT_EQ(du.first, du.first->self) << "Data.self is corrupted";
794 //-----------------------------------------------------------------------------
797 template <typename T>
798 struct is_copy_constructibleAndAssignable
799 : std::integral_constant<bool,
800 std::is_copy_constructible<T>::value &&
801 std::is_copy_assignable<T>::value
804 template <typename T>
805 struct is_move_constructibleAndAssignable
806 : std::integral_constant<bool,
807 std::is_move_constructible<T>::value &&
808 std::is_move_assignable<T>::value
811 template <class Vector>
812 struct customAllocator
813 : std::integral_constant<bool,
815 typename Vector::allocator_type,
816 std::allocator<typename Vector::value_type>
820 template <typename T>
821 struct special_move_assignable
822 : is_move_constructibleAndAssignable<T> {};
823 template <Flags f, size_t pad>
824 struct special_move_assignable<Data<f, pad>>
825 : std::integral_constant<bool,
826 is_move_constructibleAndAssignable<Data<f, pad>>::value ||
830 //=============================================================================
831 //=============================================================================
834 //-----------------------------------------------------------------------------
841 unsigned reslo, reshi;
843 __asm__ __volatile__ (
844 "xorl %%eax,%%eax \n cpuid \n"
845 ::: "%eax", "%ebx", "%ecx", "%edx");
846 __asm__ __volatile__ (
848 : "=a" (reslo), "=d" (reshi) );
849 __asm__ __volatile__ (
850 "xorl %%eax,%%eax \n cpuid \n"
851 ::: "%eax", "%ebx", "%ecx", "%edx");
853 return ((uint64_t)reshi << 32) | reslo;
857 //-----------------------------------------------------------------------------
860 #define IBOOST_PP_VARIADIC_SIZE(...) IBOOST_PP_VARIADIC_SIZE_I(__VA_ARGS__, \
861 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, \
862 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, \
863 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, \
864 7, 6, 5, 4, 3, 2, 1,)
865 #define IBOOST_PP_VARIADIC_SIZE_I(e0, e1, e2, e3, e4, e5, e6, e7, e8, e9, \
866 e10, e11, e12, e13, e14, e15, e16, e17, e18, e19, e20, e21, e22, e23, e24, \
867 e25, e26, e27, e28, e29, e30, e31, e32, e33, e34, e35, e36, e37, e38, e39, \
868 e40, e41, e42, e43, e44, e45, e46, e47, e48, e49, e50, e51, e52, e53, e54, \
869 e55, e56, e57, e58, e59, e60, e61, e62, e63, size, ...) size
870 #define IBOOST_PP_VARIADIC_TO_SEQ(...) \
871 BOOST_PP_TUPLE_TO_SEQ(IBOOST_PP_VARIADIC_SIZE(__VA_ARGS__), (__VA_ARGS__))
873 //-----------------------------------------------------------------------------
876 #define GEN_TEST(r, name, type) \
878 string atype = PrettyType<typename type::allocator_type>()(); \
879 string ptype = PrettyType<typename type::value_type>()(); \
880 SCOPED_TRACE("allocator: " + atype); { \
881 SCOPED_TRACE("datatype: " + ptype); { \
882 test_ ## name ## 3 <type> (); \
883 if (::testing::Test::HasFatalFailure()) return; \
885 #define GEN_TYPE_TEST(r, name, type) \
886 if (0) test_I_ ## name ## 3 <type> ();
887 #define GEN_RUNNABLE_TEST(r, name, type) \
888 one = test_I_ ## name ## 3 <type> () || one;
890 #define GEN_LOOPER(r, d, arg) BOOST_PP_CAT(LOOPER_, arg)
891 #define GEN_VMAKER(r, d, arg) { BOOST_PP_CAT(VMAKER_, arg) {
892 #define GEN_UMAKER(r, d, arg) } BOOST_PP_CAT(UMAKER_, arg) }
893 #define GEN_CLOSER(r, d, arg) BOOST_PP_CAT(CLOSER_, arg)
895 #define TYPIFY(r, d, name) BOOST_PP_CAT(TYPIFY_, name)
896 #define ARGIFY(r, d, name) TYPIFY(r, d, name) name
898 #define MAKE_TEST(ref, name, types, restriction, argseq, ...) \
899 template <class Vector> void test_ ## name ## 2 (std::false_type) {} \
900 template <class Vector> void test_ ## name ## 2 (std::true_type) { \
901 BOOST_PP_SEQ_FOR_EACH(GEN_LOOPER, _, argseq) \
905 BOOST_PP_SEQ_FOR_EACH(GEN_VMAKER, _, argseq) \
907 test_ ## name <Vector, typename Vector::value_type, \
908 typename Vector::allocator_type> ( __VA_ARGS__ ); \
909 if (::testing::Test::HasFatalFailure()) { \
913 BOOST_PP_SEQ_FOR_EACH(GEN_UMAKER, _, BOOST_PP_SEQ_REVERSE(argseq)) \
917 BOOST_PP_SEQ_FOR_EACH(GEN_CLOSER, _, BOOST_PP_SEQ_REVERSE(argseq)) \
919 template <class Vector> void test_ ## name ## 3 () { \
920 test_ ## name ## 2 <Vector> (std::integral_constant<bool, \
921 restriction<typename Vector::value_type>::value && \
922 is_copy_constructible<typename Vector::value_type>::value \
926 template <class Vector> bool test_I_ ## name ## 2 (std::false_type) \
928 template <class Vector> bool test_I_ ## name ## 2 (std::true_type) { \
930 auto f = test_ ## name <Vector, \
931 typename Vector::value_type, typename Vector::allocator_type>; \
935 template <class Vector> bool test_I_ ## name ## 3 () { \
936 return test_I_ ## name ## 2 <Vector> (std::integral_constant<bool, \
937 restriction<typename Vector::value_type>::value>()); \
941 TEST(FBVector, name) { \
942 SCOPED_TRACE("N3337 reference: " ref); \
943 BOOST_PP_SEQ_FOR_EACH(GEN_TEST, name, types) \
944 BOOST_PP_SEQ_FOR_EACH(GEN_TYPE_TEST, name, INTERFACE_TYPES) \
946 BOOST_PP_SEQ_FOR_EACH(GEN_RUNNABLE_TEST, name, types) \
948 FAIL() << "No tests qualified to run"; \
952 #define DECL(name, ...) \
953 template <class Vector, typename T, typename Allocator> \
954 void test_ ## name (BOOST_PP_SEQ_ENUM(BOOST_PP_SEQ_TRANSFORM( \
955 ARGIFY, _, IBOOST_PP_VARIADIC_TO_SEQ(__VA_ARGS__))))
957 #define STL_TEST_I(ref, name, restriction, ...) \
958 DECL(name, __VA_ARGS__); \
959 MAKE_TEST(ref, name, TEST_TYPES, restriction, \
960 IBOOST_PP_VARIADIC_TO_SEQ(__VA_ARGS__), __VA_ARGS__) \
961 DECL(name, __VA_ARGS__)
963 #define STL_TEST(ref, name, restriction, ...) \
964 STL_TEST_I(ref, name, restriction, z, ## __VA_ARGS__, ticks)
966 //-----------------------------------------------------------------------------
970 typedef Data<0, 4080> ED2;
971 typedef Data<MC_NOEXCEPT> ED3;
972 typedef Data<MC_NOEXCEPT | CC_DELETE> ED4;
973 typedef Data<IS_RELOCATABLE> ED5;
975 typedef VECTOR_<int, std::allocator<int>> _TVIS;
976 typedef VECTOR_<int, Alloc<int>> _TVI;
977 typedef VECTOR_<ED1, std::allocator<ED1>> _TV1;
978 typedef VECTOR_<ED2, std::allocator<ED2>> _TV2;
979 typedef VECTOR_<ED3, std::allocator<ED3>> _TV3;
980 typedef VECTOR_<ED4, std::allocator<ED4>> _TV4;
981 typedef VECTOR_<ED5, std::allocator<ED5>> _TV5v1;
982 typedef VECTOR_<ED5, Alloc<ED5>> _TV5;
984 typedef Data<PROP_COPY> EP1;
985 typedef Data<PROP_MOVE> EP2;
986 typedef Data<PROP_SWAP> EP3;
988 typedef VECTOR_<EP1, Alloc<EP1>> _TP1;
989 typedef VECTOR_<EP2, Alloc<EP2>> _TP2;
990 typedef VECTOR_<EP3, Alloc<EP3>> _TP3;
992 #define TEST_TYPES (_TVIS)(_TVI)(_TV1)(_TV2)(_TV3)(_TV4)(_TV5v1)(_TV5) \
995 typedef Data<ALL_DELETE> DD1; // unoperable
996 typedef Data<DC_DELETE | CC_DELETE | MC_DELETE> DD2; // unconstructible
997 typedef Data<CA_DELETE | MA_DELETE> DD3; // unassignable
998 typedef Data<CC_DELETE | MC_DELETE> DD4; // uncopyable
999 typedef Data<ALL_DELETE & ~DC_DELETE> DD5; // only default constructible
1000 typedef Data<CC_DELETE> DD6; // move-only copy construction
1001 typedef Data<CA_DELETE> DD7; // move-only assignment
1003 typedef Data<ALL_DELETE | PROP_MOVE> DDSMA;
1004 typedef VECTOR_<DDSMA, Alloc<DDSMA>> _TSpecialMA;
1006 #define INTERFACE_TYPES \
1007 (_TVI)(VECTOR_<DD1>)(VECTOR_<DD2>)(VECTOR_<DD3>) \
1008 (VECTOR_<DD4>)(VECTOR_<DD5>)(VECTOR_<DD6>) \
1009 (VECTOR_<DD7>)(_TSpecialMA)
1011 //-----------------------------------------------------------------------------
1014 template <typename T>
1016 string operator()() {
1017 if (is_same<T, int>::value) {
1020 if (is_same<T, char>::value) {
1023 if (is_same<T, uint64_t>::value) {
1026 return typeid(T).name();
1030 template <Flags f, size_t pad>
1031 struct PrettyType<Data<f, pad>> {
1032 string operator()() {
1036 if ((f & DC_DELETE) ||
1042 if (f & DC_DELETE) {
1045 if (f & CC_DELETE) {
1048 if (f & MC_DELETE) {
1051 if (f & CA_DELETE) {
1054 if (f & MA_DELETE) {
1060 if ((f & DC_NOEXCEPT) ||
1061 (f & CC_NOEXCEPT) ||
1062 (f & MC_NOEXCEPT) ||
1063 (f & CA_NOEXCEPT) ||
1064 (f & MA_NOEXCEPT)) {
1066 if (f & DC_NOEXCEPT) {
1069 if (f & CC_NOEXCEPT) {
1072 if (f & MC_NOEXCEPT) {
1075 if (f & CA_NOEXCEPT) {
1078 if (f & MA_NOEXCEPT) {
1084 if (f & IS_RELOCATABLE) {
1085 tpe << "(relocatable)";
1089 tpe << "{pad " << pad << "}";
1096 template <typename T>
1097 struct PrettyType<std::allocator<T>> {
1098 string operator()() {
1099 return "std::allocator<" + PrettyType<T>()() + ">";
1103 template <typename T>
1104 struct PrettyType<Alloc<T>> {
1105 string operator()() {
1106 return "Alloc<" + PrettyType<T>()() + ">";
1110 //-----------------------------------------------------------------------------
1111 // Setup, teardown, runup, rundown
1113 // These four macros are run once per test. Setup and runup occur before the
1114 // test, teardown and rundown after. Setup and runup straddle the
1115 // initialization sequence, whereas rundown and teardown straddle the
1118 #define SETUP hardReset();
1121 //-----------------------------------------------------------------------------
1122 // Types and typegens
1127 #define TYPIFY_z std::nullptr_t
1129 Vector* a_p = nullptr; Vector* b_p = nullptr; \
1130 typename Vector::value_type* t_p = nullptr;
1131 #define VMAKER_z std::nullptr_t z = nullptr;
1133 verify<Vector>(0); \
1134 if (::testing::Test::HasFatalFailure()) { \
1142 #define VERIFICATION \
1143 if (b_p != nullptr) verify(t_p != nullptr ,*a_p, *b_p); \
1144 else if (a_p != nullptr) verify(t_p != nullptr, *a_p); \
1145 else verify<Vector>(t_p != nullptr); \
1146 if (::testing::Test::HasFatalFailure()) return;
1148 #define TYPIFY_ticks int
1149 #define LOOPER_ticks \
1150 int _maxTicks_ = 0; \
1151 bool ticks_thrown = false; \
1152 for (int ticks = -1; ticks < _maxTicks_; ++ticks) {
1153 #define VMAKER_ticks \
1154 string ticks_st = folly::to<string>("ticks = ", ticks); \
1155 SCOPED_TRACE(ticks_st); \
1156 { SCOPED_TRACE("pre-run verification"); \
1160 #define UMAKER_ticks _maxTicks_ = Ticker::CountTicks; } \
1161 catch (const TickException&) { ticks_thrown = true; } \
1162 catch (const std::exception& e) \
1163 { FAIL() << "EXCEPTION: " << e.what(); } \
1165 { FAIL() << "UNKNOWN EXCEPTION"; } \
1166 if (ticks >= 0 && Ticker::CountTicks > ticks && !ticks_thrown) \
1167 FAIL() << "CountTicks = " << Ticker::CountTicks << " > " \
1168 << ticks << " = ticks" \
1169 << ", but no tick error was observed"; \
1171 #define CLOSER_ticks }
1174 //--------------------------------------------------
1175 // vectors (second could be .equal, ==, or distinct)
1177 static const vector<pair<int, int>> VectorSizes = {
1181 { 10, -1}, { 10, 1}, { 10, 0},
1182 #if !FOLLY_SANITIZE_ADDRESS
1183 {100, -1}, {100, 1},
1186 //{ 10, -1}, { 10, 0}, { 10, 1}, { 10, 2}, { 10, 10},
1187 //{ 100, -1}, { 100, 0}, { 100, 1}, { 100, 2}, { 100, 10}, { 100, 100},
1188 //{ 1000, -1}, { 1000, 0}, { 1000, 1}, { 1000, 2}, { 1000, 10}, { 1000, 100},
1192 int populateIndex = 1426;
1193 template <class Vector>
1194 void populate(Vector& v, const pair<int, int>& ss) {
1196 for (; i < ss.first; ++i) {
1197 v.emplace_back(populateIndex++);
1199 if (ss.second >= 0) {
1200 while (v.capacity() - v.size() != size_t(ss.second)) {
1201 v.emplace_back(populateIndex++);
1206 template <typename A>
1208 static A get() { return A(); }
1210 template <typename T>
1211 struct allocGen<Alloc<T>> {
1212 static Alloc<T> get() {
1219 #define TYPIFY_a Vector&
1220 #define LOOPER_a for (const auto& a_ss : VectorSizes) {
1222 Vector a(allocGen<typename Vector::allocator_type>::get()); \
1224 populate(*a_p, a_ss); \
1225 string a_st = folly::to<string>("a (", a.size(), "/", a.capacity(), ")"); \
1227 #define UMAKER_a verify(0, a); if (::testing::Test::HasFatalFailure()) return;
1230 #define TYPIFY_b Vector&
1231 #define LOOPER_b for (int b_i = -2; b_i < (int)VectorSizes.size(); ++b_i) {
1233 Vector b_s(allocGen<typename Vector::allocator_type>::get()); \
1234 b_p = &b_s; string b_st; \
1237 b_st = "b is an alias of a"; \
1239 else if (b_i == -1) { \
1241 new (&b_s) Vector(a); \
1242 b_st = "b is a deep copy of a"; \
1245 populate(b_s, VectorSizes[b_i]); \
1246 b_st = folly::to<string>("b (", b_s.size(), "/", b_s.capacity(), ")"); \
1251 verify(0, a, b); if (::testing::Test::HasFatalFailure()) return;
1257 static const vector<int> nSizes = { 0, 1, 2, 9, 10, 11 };
1259 #define TYPIFY_n int
1260 #define LOOPER_n for (int n : nSizes) {
1262 string n_st = folly::to<string>("n = ", n); SCOPED_TRACE(n_st);
1266 //-----------------------
1267 // non-internal iterators
1269 static int ijarr[12] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
1270 static int ijarC[12] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
1272 #define TYPIFY_i int*
1274 #define VMAKER_i int* i = ijarr; SCOPED_TRACE("i = fib[0]");
1278 #define TYPIFY_j int*
1279 #define LOOPER_j for (int j_i = 0; j_i < 12; ++j_i) {
1281 int* j = ijarr + j_i; \
1282 string j_st = folly::to<string>("j = fib[", j_i, "]"); \
1285 for (int j_c = 0; j_c < 12; ++j_c) ASSERT_EQ(ijarC[j_c], ijarr[j_c]);
1288 //-------------------
1289 // internal iterators
1291 template <class Vector>
1292 std::pair<typename Vector::iterator, string>
1293 iterSpotter(Vector& v, int i) {
1294 typename Vector::iterator it;
1325 cerr << "internal error" << endl;
1329 return make_pair(it, msg);
1332 #define TYPIFY_p typename Vector::iterator
1333 #define LOOPER_p for (int p_i = 0; p_i < 4; ++p_i) {
1335 auto p_im = iterSpotter(a, p_i); \
1336 auto& p = p_im.first; \
1337 auto& p_m = p_im.second; \
1338 SCOPED_TRACE("p = " + p_m);
1342 #define TYPIFY_q typename Vector::iterator
1343 #define LOOPER_q for (int q_i = p_i; q_i < 4; ++q_i) {
1345 auto q_im = iterSpotter(a, q_i); \
1346 auto& q = q_im.first; \
1347 auto& q_m = q_im.second; \
1348 SCOPED_TRACE("q = " + q_m);
1355 static const vector<int> tVals = { 0, 1, 2, 3, 17, 66, 521 };
1357 #define TYPIFY_t typename Vector::value_type&
1358 #define LOOPER_t for (int t_v : tVals) {
1360 typename Vector::value_type t_s(t_v); \
1361 t_p = addressof(t_s); \
1362 string t_st = folly::to<string>("t(", t_v, ")"); \
1363 if (t_v < 4 && a_p != nullptr) { \
1364 auto t_im = iterSpotter(*a_p, t_v); \
1365 if (t_im.first != a_p->end()) { \
1366 t_p = addressof(*t_im.first); \
1367 t_st = "t is " + t_im.second; \
1370 typename Vector::value_type& t = *t_p; \
1378 #define TYPIFY_m typename Vector::allocator_type
1380 int m_max = 1 + (a_p != nullptr); \
1381 for (int m_i = 0; m_i < m_max; ++m_i) {
1383 typename Vector::allocator_type m = m_i == 0 \
1384 ? typename Vector::allocator_type() \
1385 : a_p->get_allocator();
1389 //-----------------------------------------------------------------------------
1393 template <class Vector>
1394 void verifyVector(const Vector& v) {
1395 ASSERT_TRUE(v.begin() <= v.end()) << "end is before begin";
1396 ASSERT_TRUE(v.empty() == (v.begin() == v.end())) << "empty != (begin == end)";
1397 ASSERT_TRUE(v.size() == size_t(distance(v.begin(), v.end())))
1398 << "size != end - begin";
1399 ASSERT_TRUE(v.size() <= v.capacity()) << "size > capacity";
1400 ASSERT_TRUE(v.capacity() <= v.max_size()) << "capacity > max_size";
1401 ASSERT_TRUE(v.data() || true); // message won't print - it will just crash
1402 ASSERT_TRUE(v.size() == 0 || v.data() != nullptr)
1403 << "nullptr data points to at least one element";
1406 void verifyAllocator(int ele, int cap) {
1407 ASSERT_EQ(ele, AllocTracker::Constructed - AllocTracker::Destroyed);
1410 for (auto kv : AllocTracker::Allocated) {
1411 if (kv.second != size_t(-1)) {
1415 ASSERT_EQ(cap, tot) << "the allocator counts " << tot << " space, "
1416 "but the vector(s) have (combined) capacity " << cap;
1420 template <class Vector>
1421 void verify(int extras) {
1422 if (!is_arithmetic<typename Vector::value_type>::value) {
1423 ASSERT_EQ(0 + extras, getTotal()) << "there exist Data but no vectors";
1426 if (::testing::Test::HasFatalFailure()) {
1429 if (customAllocator<Vector>::value) {
1430 verifyAllocator(0, 0);
1433 template <class Vector>
1434 void verify(int extras, const Vector& v) {
1436 if (!is_arithmetic<typename Vector::value_type>::value) {
1437 ASSERT_EQ(v.size() + extras, getTotal())
1438 << "not all Data are in the vector";
1441 if (::testing::Test::HasFatalFailure()) {
1444 if (customAllocator<Vector>::value) {
1445 verifyAllocator(v.size(), v.capacity());
1448 template <class Vector>
1449 void verify(int extras, const Vector& v1, const Vector& v2) {
1452 auto size = v1.size();
1453 auto cap = v1.capacity();
1456 cap += v2.capacity();
1458 if (!is_arithmetic<typename Vector::value_type>::value) {
1459 ASSERT_EQ(size + extras, getTotal()) << "not all Data are in the vector(s)";
1462 if (::testing::Test::HasFatalFailure()) {
1465 if (customAllocator<Vector>::value) {
1466 verifyAllocator(size, cap);
1470 //=============================================================================
1473 // save the state of a vector
1474 int convertToInt(int t) {
1477 template <Flags f, size_t pad>
1478 int convertToInt(const Data<f, pad>& t) {
1481 template <typename T>
1482 int convertToInt(const std::allocator<T>&) {
1485 template <typename T>
1486 int convertToInt(const Alloc<T>& a) {
1490 template <class Vector>
1492 typedef typename Vector::size_type size_type;
1497 /* implicit */ DataState(const Vector& v) {
1500 data_ = new int[size_];
1501 for (size_type i = 0; i < size_; ++i) {
1502 data_[i] = convertToInt(v.data()[i]);
1512 bool operator==(const DataState& o) const {
1513 if (size_ != o.size_) {
1516 for (size_type i = 0; i < size_; ++i) {
1517 if (data_[i] != o.data_[i]) {
1524 int operator[](size_type i) {
1526 cerr << "trying to access DataState out of bounds" << endl;
1532 size_type size() { return size_; }
1535 // downgrade iterators
1536 template <typename It, class tag>
1537 class Transformer : public boost::iterator_adaptor<
1538 Transformer<It, tag>,
1540 typename iterator_traits<It>::value_type,
1543 friend class boost::iterator_core_access;
1544 shared_ptr<set<It>> dereferenced;
1547 explicit Transformer(const It& it)
1548 : Transformer::iterator_adaptor_(it)
1549 , dereferenced(new set<It>()) {}
1551 typename iterator_traits<It>::value_type& dereference() const {
1552 if (dereferenced->find(this->base_reference()) != dereferenced->end()) {
1553 cerr << "iterator dereferenced more than once" << endl;
1556 dereferenced->insert(this->base_reference());
1557 return *this->base_reference();
1561 template <typename It>
1562 Transformer<It, forward_iterator_tag> makeForwardIterator(const It& it) {
1563 return Transformer<It, forward_iterator_tag>(it);
1565 template <typename It>
1566 Transformer<It, input_iterator_tag> makeInputIterator(const It& it) {
1567 return Transformer<It, input_iterator_tag>(it);
1570 // mutate a value (in contract only)
1571 void mutate(int& i) {
1576 void mutate(uint64_t& i) {
1581 template <Flags f, size_t pad>
1582 void mutate(Data<f, pad>& ds) {
1588 //=============================================================================
1597 //-----------------------------------------------------------------------------
1600 STL_TEST("23.2.1 Table 96.1-7", containerTypedefs, is_destructible) {
1601 static_assert(is_same<T, typename Vector::value_type>::value,
1602 "T != Vector::value_type");
1603 static_assert(is_same<T&, typename Vector::reference>::value,
1604 "T& != Vector::reference");
1605 static_assert(is_same<const T&, typename Vector::const_reference>::value,
1606 "const T& != Vector::const_reference");
1607 static_assert(is_convertible<
1608 typename iterator_traits<typename Vector::iterator>::iterator_category,
1609 forward_iterator_tag>::value,
1610 "Vector::iterator is not a forward iterator");
1611 static_assert(is_same<T,
1612 typename iterator_traits<typename Vector::iterator>::value_type>::value,
1613 "Vector::iterator does not iterate over type T");
1614 static_assert(is_convertible<
1615 typename iterator_traits<typename Vector::const_iterator>
1616 ::iterator_category,
1617 forward_iterator_tag>::value,
1618 "Vector::const_iterator is not a forward iterator");
1619 static_assert(is_same<T,
1620 typename iterator_traits<typename Vector::const_iterator>
1621 ::value_type>::value,
1622 "Vector::const_iterator does not iterate over type T");
1623 static_assert(is_convertible<
1624 typename Vector::iterator, typename Vector::const_iterator>::value,
1625 "Vector::iterator is not convertible to Vector::const_iterator");
1626 static_assert(is_signed<typename Vector::difference_type>::value,
1627 "Vector::difference_type is not signed");
1628 static_assert(is_same<typename Vector::difference_type,
1629 typename iterator_traits<typename Vector::iterator>
1630 ::difference_type>::value,
1631 "Vector::difference_type != Vector::iterator::difference_type");
1632 static_assert(is_same<typename Vector::difference_type,
1633 typename iterator_traits<typename Vector::const_iterator>
1634 ::difference_type>::value,
1635 "Vector::difference_type != Vector::const_iterator::difference_type");
1636 static_assert(is_unsigned<typename Vector::size_type>::value,
1637 "Vector::size_type is not unsigned");
1638 static_assert(sizeof(typename Vector::size_type) >=
1639 sizeof(typename Vector::difference_type),
1640 "Vector::size_type is smaller than Vector::difference_type");
1643 STL_TEST("23.2.1 Table 96.8-9", emptyConstruction, is_destructible) {
1646 ASSERT_TRUE(u.get_allocator() == Allocator());
1647 ASSERT_EQ(0, Counter::CountTotalOps);
1649 ASSERT_TRUE(u.empty()) << u.size();
1650 ASSERT_EQ(0, u.capacity());
1657 STL_TEST("framework", populate, is_copy_constructible) {
1658 // We use emplace_back to construct vectors for testing, as well as size,
1659 // data, and capacity. We make sure these work before proceeding with tests.
1662 ASSERT_EQ(0, u.size());
1663 ASSERT_EQ(nullptr, u.data());
1666 ASSERT_EQ(1, u.size());
1667 ASSERT_LT(u.capacity(), 100)
1668 << "single push_back increased capacity to " << u.capacity();
1669 ASSERT_NE(nullptr, u.data());
1670 ASSERT_EQ(17, convertToInt(u.data()[0]))
1671 << "first object did not get emplaced correctly";
1673 for (int i = 0; i < 3; ++i) {
1674 auto cap = u.capacity();
1675 while (u.size() < cap) {
1677 ASSERT_EQ(cap, u.capacity()) << "Vector grew when it did not need to";
1678 ASSERT_EQ(22, convertToInt(u.data()[u.size() - 1]))
1679 << "push_back with excess capacity failed";
1682 ASSERT_EQ(cap, u.size());
1685 ASSERT_GT(u.capacity(), cap) << "capacity did not grow on overflow";
1686 ASSERT_EQ(cap + 1, u.size());
1687 ASSERT_EQ(4, convertToInt(u.data()[u.size() - 1]))
1688 << "grow object did not get emplaced correctly";
1692 STL_TEST("23.2.1 Table 96.10-11", copyConstruction,
1693 is_copy_constructible, a) {
1695 DataState<Vector> dsa(ca);
1696 auto am = a.get_allocator();
1700 ASSERT_TRUE(std::allocator_traits<Allocator>::
1701 select_on_container_copy_construction(am) == u.get_allocator());
1702 ASSERT_TRUE(dsa == u);
1704 (ca.data() == nullptr && u.data() == nullptr) ||
1705 (ca.data() != u.data())
1706 ) << "only a shallow copy was made";
1714 STL_TEST("23.2.1 Table 96.12", moveConstruction, is_destructible, a) {
1715 DataState<Vector> dsa(a);
1716 auto m = a.get_allocator();
1720 ASSERT_TRUE(m == u.get_allocator());
1721 ASSERT_EQ(0, Counter::CountTotalOps);
1723 ASSERT_TRUE(dsa == u);
1726 Vector u2 = move(a);
1730 STL_TEST("23.2.1 Table 96.13", moveAssignment, special_move_assignable, a, b) {
1731 DataState<Vector> dsb(b);
1732 auto am = a.get_allocator();
1733 auto bm = b.get_allocator();
1735 Vector& ret = a = std::move(b);
1737 if (std::allocator_traits<Allocator>::
1738 propagate_on_container_move_assignment::value) {
1739 ASSERT_TRUE(bm == a.get_allocator());
1741 ASSERT_TRUE(am == a.get_allocator());
1743 ASSERT_TRUE(&ret == &a);
1744 ASSERT_TRUE(&a == &b || dsb == a) << "move assignment did not create a copy";
1745 // The source of the move may be left in any (albeit valid) state.
1748 STL_TEST("23.2.1 Table 96.14", destructible, is_destructible) {
1749 // The test generators check this clause already.
1752 STL_TEST("23.2.1 Table 96.15-18", iterators, is_destructible, a) {
1753 DataState<Vector> dsa(a);
1756 auto itb = a.begin();
1757 auto citb = ca.begin();
1758 auto Citb = a.cbegin();
1760 auto cite = ca.end();
1761 auto Cite = a.cend();
1763 ASSERT_EQ(0, Counter::CountTotalOps);
1765 ASSERT_TRUE(dsa == a) << "call to begin or end modified internal data";
1767 ASSERT_TRUE(citb == Citb) << "cv.begin != v.cbegin";
1768 ASSERT_TRUE(cite == Cite) << "cv.end != v.cend";
1770 if (ca.size() == 0) {
1771 ASSERT_TRUE( itb == ite) << "begin != end when empty";
1772 ASSERT_TRUE(Citb == Cite) << "cbegin != cend when empty";
1774 ASSERT_TRUE( itb != ite) << "begin == end when non-empty";
1775 ASSERT_TRUE(Citb != Cite) << "cbegin == cend when non-empty";
1778 auto dist = size_t(std::distance(itb, ite));
1779 auto Cdist = size_t(std::distance(Citb, Cite));
1780 ASSERT_TRUE( dist == ca.size()) << "distance(begin, end) != size";
1781 ASSERT_TRUE(Cdist == ca.size()) << "distance(cbegin, cend) != size";
1784 STL_TEST("23.2.1 Table 96.19-20", equitable, is_arithmetic, a, b) {
1787 DataState<Vector> dsa(a);
1788 DataState<Vector> dsb(b);
1790 ASSERT_TRUE((bool)(ca == cb) == (bool)(dsa == dsb))
1791 << "== does not return equality";
1792 ASSERT_TRUE((bool)(ca == cb) != (bool)(ca != cb))
1793 << "!= is not the opposite of ==";
1795 // Data is uncomparable, by design; therefore this test's restriction
1796 // is 'is_arithmetic'
1799 STL_TEST("23.2.1 Table 96.21", memberSwappable, is_destructible, a, b) {
1800 if (!std::allocator_traits<Allocator>::
1801 propagate_on_container_swap::value &&
1802 convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1803 // undefined behaviour
1807 DataState<Vector> dsa(a);
1808 DataState<Vector> dsb(b);
1809 auto adata = a.data();
1810 auto bdata = b.data();
1811 auto am = a.get_allocator();
1812 auto bm = b.get_allocator();
1817 FAIL() << "swap is noexcept";
1820 if (std::allocator_traits<Allocator>::
1821 propagate_on_container_swap::value) {
1822 ASSERT_TRUE(bm == a.get_allocator());
1823 ASSERT_TRUE(am == b.get_allocator());
1825 ASSERT_TRUE(am == a.get_allocator());
1826 ASSERT_TRUE(bm == b.get_allocator());
1828 ASSERT_EQ(0, Counter::CountTotalOps);
1830 ASSERT_TRUE(adata == b.data() && bdata == a.data());
1831 ASSERT_TRUE(dsa == b && dsb == a) << "swap did not swap";
1834 STL_TEST("23.2.1 Table 96.22", nonmemberSwappable,
1835 is_destructible, a, b) {
1836 if (!std::allocator_traits<Allocator>::
1837 propagate_on_container_swap::value &&
1838 convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1839 // undefined behaviour
1843 DataState<Vector> dsa(a);
1844 DataState<Vector> dsb(b);
1845 auto adata = a.data();
1846 auto bdata = b.data();
1847 auto am = a.get_allocator();
1848 auto bm = b.get_allocator();
1853 FAIL() << "swap is noexcept";
1856 if (std::allocator_traits<Allocator>::
1857 propagate_on_container_swap::value) {
1858 ASSERT_TRUE(bm == a.get_allocator());
1859 ASSERT_TRUE(am == b.get_allocator());
1861 ASSERT_TRUE(am == a.get_allocator());
1862 ASSERT_TRUE(bm == b.get_allocator());
1864 ASSERT_EQ(0, Counter::CountTotalOps);
1866 ASSERT_TRUE(adata == b.data() && bdata == a.data());
1867 ASSERT_TRUE(dsa == b && dsb == a) << "swap did not swap";
1870 STL_TEST("23.2.1 Table 96.23", copyAssign,
1871 is_copy_constructibleAndAssignable, a, b) {
1872 // it is possible to make use of just the copy constructor.
1874 #ifdef USING_STD_VECTOR
1875 if (std::allocator_traits<Allocator>::
1876 propagate_on_container_copy_assignment::value &&
1877 convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1878 // Bug. By the looks of things, in the above case, their bez is being
1879 // cleared and deallocated, but then the garbage pointers are being used.
1885 DataState<Vector> dsb(cb);
1886 auto am = a.get_allocator();
1887 auto bm = b.get_allocator();
1889 Vector& ret = a = cb;
1891 if (std::allocator_traits<Allocator>::
1892 propagate_on_container_copy_assignment::value) {
1893 ASSERT_TRUE(bm == a.get_allocator());
1895 ASSERT_TRUE(am == a.get_allocator());
1897 ASSERT_TRUE(&ret == &a);
1898 ASSERT_TRUE(dsb == a) << "copy-assign not equal to original";
1901 STL_TEST("23.2.1 Table 96.24-26", sizeops, is_destructible) {
1902 // This check generators check this clause already.
1905 //-----------------------------------------------------------------------------
1906 // Reversible container
1908 STL_TEST("23.2.1 Table 97.1-2", reversibleContainerTypedefs,
1910 static_assert(is_same<typename Vector::reverse_iterator,
1911 std::reverse_iterator<typename Vector::iterator>>::value,
1912 "Vector::reverse_iterator != reverse_iterator<Vector:iterator");
1913 static_assert(is_same<typename Vector::const_reverse_iterator,
1914 std::reverse_iterator<typename Vector::const_iterator>>::value,
1915 "Vector::const_reverse_iterator != "
1916 "const_reverse_iterator<Vector::iterator");
1919 STL_TEST("23.2.1 Table 97.3-5", reversibleIterators, is_destructible, a) {
1921 DataState<Vector> ds(a);
1923 auto ritb = a.rbegin();
1924 auto critb = ca.rbegin();
1925 auto Critb = a.crbegin();
1926 auto rite = a.rend();
1927 auto crite = ca.rend();
1928 auto Crite = a.crend();
1930 ASSERT_EQ(0, Counter::CountTotalOps);
1932 ASSERT_TRUE(ds == a) << "call to rbegin or rend modified internal data";
1934 ASSERT_TRUE(critb == Critb) << "cv.rbegin != v.crbegin";
1935 ASSERT_TRUE(crite == Crite) << "cv.rend != v.crend";
1937 if (ca.size() == 0) {
1938 ASSERT_TRUE( ritb == rite) << "rbegin != rend when empty";
1939 ASSERT_TRUE(Critb == Crite) << "crbegin != crend when empty";
1941 ASSERT_TRUE( ritb != rite) << "rbegin == rend when non-empty";
1942 ASSERT_TRUE(Critb != Crite) << "crbegin == crend when non-empty";
1945 auto dist = size_t(std::distance(ritb, rite));
1946 auto Cdist = size_t(std::distance(Critb, Crite));
1947 ASSERT_TRUE( dist == ca.size()) << "distance(rbegin, rend) != size";
1948 ASSERT_TRUE(Cdist == ca.size()) << "distance(crbegin, crend) != size";
1951 //-----------------------------------------------------------------------------
1952 // Lexicographical functions
1954 STL_TEST("23.2.1 Table 98", comparable, is_arithmetic) {
1955 const Vector v1 = { 1, 2, 3, 4 };
1956 const Vector v2 = { 1, 2, 3, 4, 5 };
1957 const Vector v3 = { 1, 2, 2 };
1958 const Vector v4 = { 1, 2, 2, 4, 5 };
1959 const Vector v5 = { };
1960 const Vector v6 = { 1, 2, 3, 4 };
1962 ASSERT_TRUE(v1 < v2);
1963 ASSERT_TRUE(v1 > v3);
1964 ASSERT_TRUE(v1 > v4);
1965 ASSERT_TRUE(v1 > v5);
1966 ASSERT_TRUE(v1 <= v6);
1967 ASSERT_TRUE(v1 >= v6);
1970 //-----------------------------------------------------------------------------
1971 // Allocator-aware requirements (AA)
1973 STL_TEST("23.2.1 Table 99.1", allocatorTypedefs, is_destructible) {
1974 static_assert(is_same<T, typename Vector::allocator_type::value_type>::value,
1975 "Vector and vector's allocator value_type mismatch");
1978 STL_TEST("23.2.1 Table 99.2", getAllocator, is_destructible) {
1979 // whitebox: ensure that a.get_allocator() returns a copy of its allocator
1982 STL_TEST("23.2.1 Table 99.3", defaultAllocator, is_destructible) {
1983 // there is nothing new to test here
1986 STL_TEST("23.2.1 Table 99.4", customAllocator, is_destructible, m) {
1991 ASSERT_TRUE(u.get_allocator() == m);
1998 STL_TEST("23.2.1 Table 99.5", copyWithAllocator, is_copy_constructible, a, m) {
1999 DataState<Vector> dsa(a);
2005 ASSERT_TRUE(u.get_allocator() == m);
2006 ASSERT_TRUE(dsa == u);
2008 (ca.data() == nullptr && u.data() == nullptr) ||
2009 (ca.data() != u.data())
2010 ) << "only a shallow copy was made";
2013 STL_TEST("23.2.1 Table 99.6", moveConstructionWithAllocator,
2014 is_destructible, a) {
2015 // there is nothing new to test here
2018 STL_TEST("23.2.1 Table 99.6", moveConstructionWithAllocatorSupplied,
2019 is_move_constructible, a, m) {
2020 bool deep = m != a.get_allocator();
2021 auto osize = a.size();
2022 auto oalloc = AllocTracker::Constructed;
2025 Vector u(std::move(a), cm);
2027 ASSERT_TRUE(u.get_allocator() == m);
2030 if (!AllocTracker::Allocated.empty()) {
2031 ASSERT_EQ(osize, AllocTracker::Constructed - oalloc);
2034 ASSERT_EQ(0, Counter::CountTotalOps);
2038 STL_TEST("23.2.1 Table 99.7-9", allocAssign, is_destructible) {
2039 // there is nothing new to test here
2042 STL_TEST("23.2.1-7", nAllocConstruction, is_copy_constructible, n, m) {
2043 #ifndef USING_STD_VECTOR
2048 ASSERT_TRUE(m == u.get_allocator());
2052 STL_TEST("23.2.1-7", nCopyAllocConstruction, is_copy_constructible, n, t, m) {
2056 Vector u(n, ct, cm);
2058 ASSERT_TRUE(m == u.get_allocator());
2061 STL_TEST("23.2.1-7", forwardIteratorAllocConstruction,
2062 is_destructible, i, j, m) {
2063 auto fi = makeForwardIterator(i);
2064 auto fj = makeForwardIterator(j);
2065 const auto& cfi = fi;
2066 const auto& cfj = fj;
2069 Vector u(cfi, cfj, cm);
2071 ASSERT_TRUE(m == u.get_allocator());
2074 STL_TEST("23.2.1-7", inputIteratorAllocConstruction,
2075 is_move_constructible, i, j, m) {
2076 #ifdef USING_STD_VECTOR
2077 if (Ticker::TicksLeft >= 0) return;
2080 auto ii = makeInputIterator(i);
2081 auto ij = makeInputIterator(j);
2082 const auto& cii = ii;
2083 const auto& cij = ij;
2086 Vector u(cii, cij, cm);
2088 ASSERT_TRUE(m == u.get_allocator());
2091 STL_TEST("23.2.1-7", ilAllocConstruction, is_arithmetic, m) {
2093 if (Ticker::TicksLeft >= 0) {
2099 Vector u({ 1, 4, 7 }, cm);
2101 ASSERT_TRUE(m == u.get_allocator());
2104 //-----------------------------------------------------------------------------
2107 STL_TEST("23.2.2", dataRaces, is_destructible) {
2109 const Vector* cv = nullptr;
2110 typename Vector::size_type* s = nullptr;
2124 // White-box: check that the non-const versions of each of the above
2125 // functions is implemented in terms of (or the same as) the const version
2128 //-----------------------------------------------------------------------------
2129 // Sequence container
2131 STL_TEST("23.2.3 Table 100.1, alt", nConstruction, is_constructible, n) {
2134 ASSERT_TRUE(Allocator() == u.get_allocator());
2135 ASSERT_EQ(n, u.size());
2136 ASSERT_EQ(Counter::CountTotalOps, Counter::CountDC);
2139 STL_TEST("23.2.3 Table 100.1", nCopyConstruction,
2140 is_copy_constructible, n, t) {
2145 ASSERT_TRUE(Allocator() == u.get_allocator());
2146 ASSERT_EQ(n, u.size()) << "Vector(n, t).size() != n" << endl;
2147 for (const auto& val : u) {
2148 ASSERT_EQ(convertToInt(t), convertToInt(val))
2149 << "not all elements of Vector(n, t) are equal to t";
2153 STL_TEST("23.2.3 Table 100.2", forwardIteratorConstruction,
2154 is_destructible, i, j) {
2155 // All data is emplace-constructible from int, so we restrict to
2158 auto fi = makeForwardIterator(i);
2159 auto fj = makeForwardIterator(j);
2160 const auto& cfi = fi;
2161 const auto& cfj = fj;
2165 ASSERT_TRUE(Allocator() == u.get_allocator());
2166 ASSERT_LE(Counter::CountTotalOps, j-i);
2168 ASSERT_EQ(j - i, u.size()) << "u(i,j).size() != j-i";
2169 for (auto it = u.begin(); it != u.end(); ++it, ++i) {
2170 ASSERT_EQ(*i, convertToInt(*it)) << "u(i,j) constructed incorrectly";
2174 STL_TEST("23.2.3 Table 100.2", inputIteratorConstruction,
2175 is_move_constructible, i, j) {
2176 #ifdef USING_STD_VECTOR
2177 if (Ticker::TicksLeft >= 0) return;
2180 auto ii = makeInputIterator(i);
2181 auto ij = makeInputIterator(j);
2182 const auto& cii = ii;
2183 const auto& cij = ij;
2187 ASSERT_TRUE(Allocator() == u.get_allocator());
2188 ASSERT_EQ(j - i, u.size()) << "u(i,j).size() != j-i";
2189 for (auto it = u.begin(); it != u.end(); ++it, ++i) {
2190 ASSERT_EQ(*i, convertToInt(*it)) << "u(i,j) constructed incorrectly";
2194 STL_TEST("23.2.3 Table 100.3", ilConstruction, is_arithmetic) {
2195 // whitebox: ensure that Vector(il) is implemented in terms of
2196 // Vector(il.begin(), il.end())
2199 if (Ticker::TicksLeft >= 0) {
2203 Vector u = { 1, 4, 7 };
2205 ASSERT_TRUE(Allocator() == u.get_allocator());
2206 ASSERT_EQ(3, u.size()) << "u(il).size() fail";
2208 auto it = u.begin();
2209 for (; it != u.end(); ++it, i += 3) {
2210 ASSERT_EQ(i, convertToInt(*it)) << "u(il) constructed incorrectly";
2214 STL_TEST("23.2.3 Table 100.4", ilAssignment,
2216 // whitebox: ensure that assign(il) is implemented in terms of
2217 // assign(il.begin(), il.end())
2220 if (Ticker::TicksLeft >= 0) {
2224 auto am = a.get_allocator();
2226 Vector& b = a = { 1, 4, 7 };
2228 ASSERT_TRUE(am == a.get_allocator());
2229 ASSERT_TRUE(&b == &a) << "'a = ...' did not return *this";
2231 ASSERT_EQ(3, a.size()) << "u(il).size() fail";
2233 auto it = a.begin();
2234 for (; it != a.end(); ++it, i += 3) {
2235 ASSERT_EQ(i, convertToInt(*it)) << "u(il) constructed incorrectly";
2239 //----------------------------
2240 // insert-and-erase subsection
2242 template <class Vector>
2243 void insertNTCheck(const Vector& a, DataState<Vector>& dsa,
2244 int idx, int n, int val) {
2245 ASSERT_EQ(dsa.size() + n, a.size());
2247 for (; i < idx; ++i) {
2248 ASSERT_EQ(dsa[i], convertToInt(a.data()[i])) << i;
2250 for (; i < idx + n; ++i) {
2251 ASSERT_EQ(val, convertToInt(a.data()[i])) << i;
2253 for (; size_t(i) < a.size(); ++i) {
2254 ASSERT_EQ(dsa[i-n], convertToInt(a.data()[i])) << i;
2258 STL_TEST("23.2.3 Table 100.5", iteratorEmplacement,
2259 is_move_constructibleAndAssignable, a, p) {
2260 DataState<Vector> dsa(a);
2261 int idx = distance(a.begin(), p);
2262 auto am = a.get_allocator();
2264 auto q = a.emplace(p, 44);
2266 ASSERT_TRUE(am == a.get_allocator());
2267 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2268 insertNTCheck(a, dsa, idx, 1, 44);
2271 STL_TEST("23.2.3 Table 100.6", iteratorInsertion,
2272 is_copy_constructibleAndAssignable, a, p, t) {
2273 DataState<Vector> dsa(a);
2274 int idx = distance(a.begin(), p);
2275 int tval = convertToInt(t);
2276 auto am = a.get_allocator();
2279 auto q = a.insert(p, ct);
2281 ASSERT_TRUE(am == a.get_allocator());
2282 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2283 insertNTCheck(a, dsa, idx, 1, tval);
2286 STL_TEST("23.2.3 Table 100.7", iteratorInsertionRV,
2287 is_move_constructibleAndAssignable, a, p, t) {
2288 // rvalue-references cannot have their address checked for aliased inserts
2289 if (a.data() <= addressof(t) && addressof(t) < a.data() + a.size()) {
2293 DataState<Vector> dsa(a);
2294 int idx = distance(a.begin(), p);
2295 int tval = convertToInt(t);
2296 auto am = a.get_allocator();
2298 auto q = a.insert(p, std::move(t));
2300 ASSERT_TRUE(am == a.get_allocator());
2301 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2302 insertNTCheck(a, dsa, idx, 1, tval);
2305 STL_TEST("23.2.3 Table 100.8", iteratorInsertionN,
2306 is_copy_constructibleAndAssignable, a, p, n, t) {
2307 DataState<Vector> dsa(a);
2308 int idx = distance(a.begin(), p);
2309 int tval = convertToInt(t);
2310 auto am = a.get_allocator();
2313 #ifndef USING_STD_VECTOR
2319 ASSERT_TRUE(am == a.get_allocator());
2320 #ifndef USING_STD_VECTOR
2321 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2324 insertNTCheck(a, dsa, idx, n, tval);
2327 template <class Vector>
2328 void insertItCheck(const Vector& a, DataState<Vector>& dsa,
2329 int idx, int* b, int* e) {
2330 ASSERT_EQ(dsa.size() + (e - b), a.size());
2332 for (; i < idx; ++i) {
2333 ASSERT_EQ(dsa[i], convertToInt(a.data()[i]));
2335 for (; i < idx + (e - b); ++i) {
2336 ASSERT_EQ(*(b + i - idx), convertToInt(a.data()[i]));
2338 for (; size_t(i) < a.size(); ++i) {
2339 ASSERT_EQ(dsa[i - (e - b)], convertToInt(a.data()[i]));
2343 STL_TEST("23.2.3 Table 100.9", iteratorInsertionIterator,
2344 is_move_constructibleAndAssignable, a, p, i, j) {
2345 DataState<Vector> dsa(a);
2346 int idx = distance(a.begin(), p);
2348 auto fi = makeForwardIterator(i);
2349 auto fj = makeForwardIterator(j);
2350 auto am = a.get_allocator();
2351 const auto& cfi = fi;
2352 const auto& cfj = fj;
2354 #ifndef USING_STD_VECTOR
2358 a.insert(p, cfi, cfj);
2360 ASSERT_TRUE(am == a.get_allocator());
2361 #ifndef USING_STD_VECTOR
2362 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2365 insertItCheck(a, dsa, idx, i, j);
2368 STL_TEST("23.2.3 Table 100.9", iteratorInsertionInputIterator,
2369 is_move_constructibleAndAssignable, a, p, i, j) {
2370 DataState<Vector> dsa(a);
2371 int idx = distance(a.begin(), p);
2373 auto ii = makeInputIterator(i);
2374 auto ij = makeInputIterator(j);
2375 auto am = a.get_allocator();
2376 const auto& cii = ii;
2377 const auto& cij = ij;
2379 #ifndef USING_STD_VECTOR
2383 a.insert(p, cii, cij);
2385 ASSERT_TRUE(am == a.get_allocator());
2386 #ifndef USING_STD_VECTOR
2387 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2390 insertItCheck(a, dsa, idx, i, j);
2393 STL_TEST("23.2.3 Table 100.10", iteratorInsertIL,
2394 is_arithmetic, a, p) {
2396 if (Ticker::TicksLeft >= 0) {
2400 // whitebox: ensure that insert(p, il) is implemented in terms of
2401 // insert(p, il.begin(), il.end())
2403 DataState<Vector> dsa(a);
2404 int idx = distance(a.begin(), p);
2405 auto am = a.get_allocator();
2407 #ifndef USING_STD_VECTOR
2411 a.insert(p, {1, 4, 7});
2413 ASSERT_TRUE(am == a.get_allocator());
2414 #ifndef USING_STD_VECTOR
2415 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2418 int ila[] = { 1, 4, 7 };
2421 insertItCheck(a, dsa, idx, i, j);
2424 template <class Vector>
2425 void eraseCheck(Vector& a, DataState<Vector>& dsa, int idx, int n) {
2426 ASSERT_EQ(dsa.size() - n, a.size());
2428 auto it = a.begin();
2429 for (; it != a.end(); ++it, ++i) {
2433 ASSERT_EQ(dsa[i], convertToInt(*it));
2437 STL_TEST("23.2.3 Table 100.11", iteratorErase, is_move_assignable, a, p) {
2442 DataState<Vector> dsa(a);
2443 int idx = distance(a.begin(), p);
2444 auto am = a.get_allocator();
2446 auto rit = a.erase(p);
2448 ASSERT_TRUE(am == a.get_allocator());
2449 ASSERT_EQ(idx, distance(a.begin(), rit)) << "wrong iterator returned";
2450 eraseCheck(a, dsa, idx, 1);
2453 STL_TEST("23.2.3 Table 100.12", iteratorEraseRange,
2454 is_move_assignable, a, p, q) {
2459 DataState<Vector> dsa(a);
2460 int idx = distance(a.begin(), p);
2461 auto am = a.get_allocator();
2463 auto rit = a.erase(p, q);
2465 ASSERT_TRUE(am == a.get_allocator());
2466 ASSERT_EQ(idx, distance(a.begin(), rit)) << "wrong iterator returned";
2467 eraseCheck(a, dsa, idx, distance(p,q));
2470 //--------------------------------
2471 // end insert-and-erase subsection
2473 STL_TEST("23.2.3 Table 100.13", clear, is_destructible, a) {
2475 auto am = a.get_allocator();
2480 FAIL() << "clear must be noexcept";
2483 ASSERT_TRUE(am == a.get_allocator());
2484 ASSERT_TRUE(a.empty());
2487 STL_TEST("23.2.3 Table 100.14", assignRange, is_move_assignable, a, i, j) {
2488 auto fi = makeForwardIterator(i);
2489 auto fj = makeForwardIterator(j);
2490 const auto& cfi = fi;
2491 const auto& cfj = fj;
2492 auto am = a.get_allocator();
2496 ASSERT_TRUE(am == a.get_allocator());
2497 ASSERT_EQ(distance(i, j), a.size());
2498 for (auto it = a.begin(); it != a.end(); ++it, ++i) {
2499 ASSERT_EQ(*i, convertToInt(*it));
2503 STL_TEST("23.2.3 Table 100.14", assignInputRange,
2504 is_move_constructibleAndAssignable, a, i, j) {
2505 auto ii = makeInputIterator(i);
2506 auto ij = makeInputIterator(j);
2507 const auto& cii = ii;
2508 const auto& cij = ij;
2509 auto am = a.get_allocator();
2513 ASSERT_TRUE(am == a.get_allocator());
2514 ASSERT_EQ(distance(i, j), a.size());
2515 for (auto it = a.begin(); it != a.end(); ++it, ++i) {
2516 ASSERT_EQ(*i, convertToInt(*it));
2520 STL_TEST("23.2.3 Table 100.15", assignIL,
2523 // whitebox: ensure that assign(il) is implemented in terms of
2524 // assign(il.begin(), il.end())
2527 if (Ticker::TicksLeft >= 0) {
2531 auto am = a.get_allocator();
2533 a.assign({1, 4, 7});
2535 ASSERT_TRUE(am == a.get_allocator());
2536 int ila[] = { 1, 4, 7 };
2539 ASSERT_EQ(3, a.size());
2540 for (auto it = a.begin(); it != a.end(); ++it, ++i) {
2541 ASSERT_EQ(*i, convertToInt(*it));
2545 STL_TEST("23.2.3 Table 100.16", assignN,
2546 is_copy_constructibleAndAssignable, a, n, t) {
2547 auto am = a.get_allocator();
2549 auto tval = convertToInt(t);
2553 ASSERT_TRUE(am == a.get_allocator());
2554 ASSERT_EQ(n, a.size());
2555 for (auto it = a.begin(); it != a.end(); ++it) {
2556 ASSERT_EQ(tval, convertToInt(*it));
2560 STL_TEST("23.2.3 Table 101.1", front, is_destructible, a) {
2565 ASSERT_TRUE(addressof(a.front()) == a.data());
2567 ASSERT_EQ(0, Counter::CountTotalOps);
2571 const Vector& ca = a;
2576 STL_TEST("23.2.3 Table 101.2", back, is_destructible, a) {
2581 ASSERT_TRUE(addressof(a.back()) == a.data() + a.size() - 1);
2583 ASSERT_EQ(0, Counter::CountTotalOps);
2587 const Vector& ca = a;
2592 STL_TEST("23.2.3 Table 101.4", emplaceBack,
2593 is_move_constructible, a) {
2594 DataState<Vector> dsa(a);
2595 auto adata = a.data();
2596 int excess = a.capacity() - a.size();
2597 auto am = a.get_allocator();
2602 ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2606 ASSERT_TRUE(am == a.get_allocator());
2608 ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2610 ASSERT_EQ(dsa.size() + 1, a.size());
2612 auto it = a.begin();
2613 for (; i < dsa.size(); ++i, ++it) {
2614 ASSERT_EQ(dsa[i], convertToInt(*it));
2616 ASSERT_EQ(44, convertToInt(a.back()));
2619 STL_TEST("23.2.3 Table 101.7", pushBack, is_copy_constructible, a, t) {
2620 DataState<Vector> dsa(a);
2621 int tval = convertToInt(t);
2622 auto adata = a.data();
2623 int excess = a.capacity() - a.size();
2624 auto am = a.get_allocator();
2630 ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2634 ASSERT_TRUE(am == a.get_allocator());
2636 ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2638 ASSERT_EQ(dsa.size() + 1, a.size());
2640 auto it = a.begin();
2641 for (; i < dsa.size(); ++i, ++it) {
2642 ASSERT_EQ(dsa[i], convertToInt(*it));
2644 ASSERT_EQ(tval, convertToInt(a.back()));
2647 STL_TEST("23.2.3 Table 101.8", pushBackRV,
2648 is_move_constructible, a, t) {
2649 DataState<Vector> dsa(a);
2650 int tval = convertToInt(t);
2651 auto adata = a.data();
2652 int excess = a.capacity() - a.size();
2653 auto am = a.get_allocator();
2656 a.push_back(move(t));
2658 ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2662 ASSERT_TRUE(am == a.get_allocator());
2664 ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2666 ASSERT_EQ(dsa.size() + 1, a.size());
2668 auto it = a.begin();
2669 for (; i < dsa.size(); ++i, ++it) {
2670 ASSERT_EQ(dsa[i], convertToInt(*it));
2672 ASSERT_EQ(tval, convertToInt(a.back()));
2675 STL_TEST("23.2.3 Table 100.10", popBack, is_destructible, a) {
2680 DataState<Vector> dsa(a);
2681 auto am = a.get_allocator();
2685 ASSERT_TRUE(am == a.get_allocator());
2686 ASSERT_EQ(dsa.size() - 1, a.size());
2688 auto it = a.begin();
2689 for (; it != a.end(); ++it, ++i) {
2690 ASSERT_EQ(dsa[i], convertToInt(*it));
2694 STL_TEST("23.2.3 Table 100.11", operatorBrace, is_destructible, a) {
2696 for (size_t i = 0; i < ca.size(); ++i) {
2697 ASSERT_TRUE(addressof(ca[i]) == ca.data()+i);
2700 ASSERT_EQ(0, Counter::CountTotalOps);
2707 STL_TEST("23.2.3 Table 100.12", at, is_destructible, a) {
2709 for (size_t i = 0; i < ca.size(); ++i) {
2710 ASSERT_TRUE(addressof(ca.at(i)) == ca.data()+i);
2713 ASSERT_EQ(0, Counter::CountTotalOps);
2717 FAIL() << "at(size) should have thrown an error";
2718 } catch (const std::out_of_range& e) {
2720 FAIL() << "at(size) threw error other than out_of_range";
2728 STL_TEST("move iterators", moveIterators, is_copy_constructibleAndAssignable) {
2733 auto mfi = make_move_iterator(makeForwardIterator(i));
2734 auto mfj = make_move_iterator(makeForwardIterator(j));
2735 auto mii = make_move_iterator(makeInputIterator(i));
2736 auto mij = make_move_iterator(makeInputIterator(j));
2738 Vector u1(mfi, mfj);
2739 Vector u2(mii, mij);
2741 u1.insert(u1.begin(), mfi, mfj);
2742 u1.insert(u1.begin(), mii, mij);
2744 u1.assign(mfi, mfj);
2745 u1.assign(mii, mij);
2749 //-----------------------------------------------------------------------------
2752 STL_TEST("23.3.6.4", dataAndCapacity, is_destructible) {
2753 // there isn't anything new to test here - data and capacity are used as the
2754 // backbone of DataState. The minimal testing we might want to do is already
2755 // done in the populate test
2758 STL_TEST("23.3.6.3", reserve, is_move_constructible, a, n) {
2759 auto adata = a.data();
2760 auto ocap = a.capacity();
2761 auto am = a.get_allocator();
2765 ASSERT_TRUE(am == a.get_allocator());
2766 if (size_t(n) <= ocap) {
2767 ASSERT_EQ(0, Counter::CountTotalOps);
2768 ASSERT_TRUE(adata == a.data());
2770 ASSERT_TRUE(a.capacity() >= size_t(n));
2771 ASSERT_LE(Counter::CountTotalOps, 2*a.size()); // move and delete
2775 STL_TEST("23.3.6.3", lengthError, is_move_constructible) {
2776 auto mx = Vector().max_size();
2779 return; // max_size is the biggest size_type; overflowed
2785 FAIL() << "reserve(big) should have thrown an error";
2786 } catch (const std::length_error& e) {
2788 FAIL() << "reserve(big) threw error other than length_error";
2792 STL_TEST("23.3.6.3", resize, is_copy_constructible, a, n) {
2793 DataState<Vector> dsa(a);
2795 auto am = a.get_allocator();
2799 ASSERT_TRUE(am == a.get_allocator());
2800 ASSERT_EQ(n, a.size());
2803 for (int i = 0; i < n; ++i) {
2804 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2807 for (int i = 0; i < sz; ++i) {
2808 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2813 STL_TEST("23.3.6.3", resizeT, is_copy_constructibleAndAssignable, a, n, t) {
2814 #ifdef USING_STD_VECTOR
2815 if (a.data() <= addressof(t) && addressof(t) < a.data() + a.size()) return;
2818 DataState<Vector> dsa(a);
2820 auto am = a.get_allocator();
2822 int val = convertToInt(t);
2826 ASSERT_TRUE(am == a.get_allocator());
2827 ASSERT_EQ(n, a.size());
2830 for (int i = 0; i < n; ++i) {
2831 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2835 for ( ; i < sz; ++i) {
2836 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2838 for ( ; i < n; ++i) {
2839 ASSERT_EQ(val, convertToInt(a[i]));
2844 STL_TEST("23.3.6.3", shrinkToFit, is_move_constructible, a) {
2845 bool willThrow = Ticker::TicksLeft >= 0;
2847 a.reserve(a.capacity() * 11);
2849 auto ocap = a.capacity();
2850 DataState<Vector> dsa(a);
2852 auto am = a.get_allocator();
2857 FAIL() << "shrink_to_fit should swallow errors";
2860 ASSERT_TRUE(am == a.get_allocator());
2861 ASSERT_TRUE(dsa == a);
2863 //ASSERT_EQ(ocap, a.capacity()); might shrink in place
2864 throw TickException("I swallowed the error");
2866 ASSERT_TRUE(a.capacity() == 0 || a.capacity() < ocap) << "Look into this";
2870 #ifndef USING_STD_VECTOR
2871 STL_TEST("EBO", ebo, is_destructible) {
2872 static_assert(!is_same<Allocator, std::allocator<T>>::value ||
2873 sizeof(Vector) == 3 * sizeof(void*),
2874 "fbvector has default allocator, but has size != 3*sizeof(void*)");
2877 STL_TEST("relinquish", relinquish, is_destructible, a) {
2879 auto cap = a.capacity();
2880 auto data = a.data();
2882 auto guts = relinquish(a);
2884 ASSERT_EQ(data, guts);
2885 ASSERT_TRUE(a.empty());
2886 ASSERT_EQ(0, a.capacity());
2888 auto alloc = a.get_allocator();
2889 for (size_t i = 0; i < sz; ++i) {
2890 std::allocator_traits<decltype(alloc)>::destroy(alloc, guts + i);
2892 if (guts != nullptr) {
2895 std::allocator<typename decltype(alloc)::value_type>>::value) {
2898 std::allocator_traits<decltype(alloc)>::deallocate(alloc, guts, cap);
2903 STL_TEST("attach", attach, is_destructible, a) {
2904 DataState<Vector> dsa(a);
2907 auto cap = a.capacity();
2908 auto guts = relinquish(a);
2910 ASSERT_EQ(a.data(), nullptr);
2911 attach(a, guts, sz, cap);
2913 ASSERT_TRUE(dsa == a);
2920 int main(int argc, char** argv) {
2921 testing::InitGoogleTest(&argc, argv);
2922 gflags::ParseCommandLineFlags(&argc, &argv, true);
2924 return RUN_ALL_TESTS();