2 * Copyright 2015 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).
28 // only compile if GCC is at least 4.7
29 #if __GNUC__ > 4 || __GNUC__ == 4 && __GNUC_MINOR__ >= 7
32 #define USING_STD_VECTOR
37 The insanity of this file deserves a superficial explanation.
39 This file tests an implementation of STL vector. It is extremely comprehensive.
40 If it compiles (more on that later) it generates a binary which, when run,
41 exhaustively tests its vector for standard compliance.
44 -If it doesn't compile, the compiler errors are mind-boggling.
45 -Not everything is testable. There are a few comments in the code where
46 the implementation must be inspected, as opposed to tested. These are very
47 simple inspections. Search for 'whitebox'.
48 -It does not test boolean specialization.
50 ==========================
51 How this file is organized
56 Data is a class designed to provide diagnostics when stored in a vector. It
57 counts the number of operations performed on it, can have any function
58 disabled or labeled as noexcept, throws errors from anywhere that is not
59 noexcept, tracks its supposed location in memory (optional), tracks
60 aggregate information, and can print a trace of its action.
62 Alloc, like Data, is a full-blown diagnostic allocator. It keeps track of
63 all space it has allocated, keeps counters, throws exceptions, and can easily
64 compare equal or not equal with other Allocs.
66 These two classes have a few useful helper functions:
67 isSane - checks that all the tracked variables make sense
68 softReset - simplifies the variables before a test
69 hardReset - brutally resets all variables to the default state
74 Google test is not quite good enough for this test file, because we need to
75 run tests across different input values and different types.
77 The STL_TEST macro takes a few arguments:
78 string - what is being tested
79 id - unique id, passed to TEST
80 restriction - requirements for test types
81 parameters - which variables to range over
83 Eg: STL_TEST("23.2.3", isCopyable, is_copy_constructible, a) { ... }
85 The restriction is used to select which types get tested. Copy construction,
86 for example, requires a data type which is copy constructible, whereas to test
87 the clear operation, the data only needs to be destructible. If the type does
88 not pass the restriction, then the test is not instantiated with that type (if
89 it were, then there would be a compiler error).
91 The variable names in the standard have very specific meaning. For example,
92 a and b are always vectors, i and j are always external iterators, etc. These
93 bindings are used in the STL_TEST - if you need a vector and an int, have
96 There is a list (BOOST_PP_SEQ) of test types and interface types. If the
97 type passes the restriction, then the test body is instantiated with that
98 type as its template parameter. Instantiation ensures that the contractual
99 elements of the standard are satisfied. Only the test types, however, and
100 not the interfact types, are actually tested.
102 If a test type passes the restriction, then it is run with a variety of
103 arguments. Each variable (e.g. a and b) have a generator, which generates
104 a range of values for that variable before each test. Generated values are not
105 reused - they are remade for every run. This causes long runtimes, but ensures
106 that corner cases are not missed.
108 There are two implicit extra parameters, z and ticks. Ignore z. Ticks, on the
109 other hand, is very important. Each is test is run multiple times with the
110 same arguments; the first time with no ticks (and hence no Data or Alloc
111 exceptions), and then once again for each and every location that an
112 exception can be thrown. This ensures that exception corner cases are alse
115 At the end of each test, a set of verification functions is run to ensure
116 that nothing was corrupted.
121 All specifications from N3337 Chapter 23 (Containers) that pertains to
122 vector is tested (if possible). Each aspect has a dedicated STL_TEST, so that
123 there are no compounding errors. The tests are organized as they appear in
126 The backbone of the testing framework is based on a small set of vector
129 -copy construction (a little bit)
135 These functions are used to generate and verify the tests. If they fail, then
136 the cascade of errors will be enormous. They are, therefore, tested first.
143 -Not all complexity checks are verified. These will be relentlessly hunted down
144 in the benchmarking phase.
146 -It seems that initializer lists with implicit arguments are constructed before
147 being passed into the vector. When one of the constructors fails, it fails in
148 the initializer list, before it even gets to the vector. The IL, however,
149 doesn't clean up properly, and already-constructed elements are not
150 destroyed. This causes a memory leak, and the tests break, but it is not the
151 fault of the vector itself. Further, since the implementation for the
152 initializer lists is specified in the standard as calling an associated
153 function with (il.begin(), il.end()), we really just have to check the throws
154 cases for the associated functions (which all work fine). Initializer lists
155 also do not work with explicit constructors.
157 -The implementation of std::copy from iterators prevents Data(int) from being
158 explicit. Explicitness is, perhaps, a desirable quality, but with fundamental
159 std library code like copy not supporting it, it seems impractical.
163 // include the vector first, to ensure its header is self-sufficient
164 #ifdef USING_STD_VECTOR
166 #define VECTOR_ std::vector
168 #include <folly/FBVector.h>
169 #define VECTOR_ folly::fbvector
172 //#define USING_STD_VECTOR
177 #include <type_traits>
187 #include <folly/ScopeGuard.h>
188 #include <folly/Conv.h>
189 #include <boost/preprocessor.hpp>
190 #include <boost/iterator/iterator_adaptor.hpp>
191 #include <gflags/gflags.h>
192 #include <gtest/gtest.h>
195 using namespace folly;
197 //=============================================================================
198 //=============================================================================
201 //-----------------------------------------------------------------------------
204 typedef uint32_t Flags;
206 // each method has 3 options: normal, noexcept, throw, and deleted
207 // normal is the default
208 // throw is mutually exclusive with noexcept
210 // DC - default constructor
211 // CC - copy constructor
212 // MC - move constructor
213 // OC - other constructor
214 // CA - copy assignment
215 // MA - move assignment
216 enum FlagVals : Flags {
237 ALL_DELETE = DC_DELETE | CC_DELETE | MC_DELETE
238 | CA_DELETE | MA_DELETE,
244 PROP_COPY = 0x100000,
245 PROP_MOVE = 0x200000,
246 PROP_SWAP = 0x400000,
249 //-----------------------------------------------------------------------------
252 template <bool b> struct D0 {
254 D0(const D0&) = default;
256 explicit D0(std::nullptr_t) {}
257 D0& operator=(const D0&) = default;
258 D0& operator=(D0&&) = default;
260 template <> struct D0<true> {
262 D0(const D0&) = default;
264 explicit D0(std::nullptr_t) {}
265 D0& operator=(const D0&) = default;
266 D0& operator=(D0&&) = default;
269 template <bool b> struct D1 {
271 D1(const D1&) = default;
273 explicit D1(std::nullptr_t) {}
274 D1& operator=(const D1&) = default;
275 D1& operator=(D1&&) = default;
277 template <> struct D1<true> {
279 D1(const D1&) = delete;
281 explicit D1(std::nullptr_t) {}
282 D1& operator=(const D1&) = default;
283 D1& operator=(D1&&) = default;
286 template <bool b> struct D2 {
288 D2(const D2&) = default;
290 explicit D2(std::nullptr_t) {}
291 D2& operator=(const D2&) = default;
292 D2& operator=(D2&&) = default;
294 template <> struct D2<true> {
296 D2(const D2&) = default;
298 explicit D2(std::nullptr_t) {}
299 D2& operator=(const D2&) = default;
300 D2& operator=(D2&&) = default;
303 template <bool b> struct D3 {
305 D3(const D3&) = default;
307 explicit D3(std::nullptr_t) {}
308 D3& operator=(const D3&) = default;
309 D3& operator=(D3&&) = default;
311 template <> struct D3<true> {
313 D3(const D3&) = default;
315 explicit D3(std::nullptr_t) {}
316 D3& operator=(const D3&) = delete;
317 D3& operator=(D3&&) = default;
320 template <bool b> struct D4 {
322 D4(const D4&) = default;
324 explicit D4(std::nullptr_t) {}
325 D4& operator=(const D4&) = default;
326 D4& operator=(D4&&) = default;
328 template <> struct D4<true> {
330 D4(const D4&) = default;
332 explicit D4(std::nullptr_t) {}
333 D4& operator=(const D4&) = default;
334 D4& operator=(D4&&) = delete;
338 struct Delete : D0<f & DC_DELETE>
342 , D4<f & MA_DELETE> {
344 Delete(const Delete&) = default;
345 Delete(Delete&&) = default;
346 Delete& operator=(const Delete&) = default;
347 Delete& operator=(Delete&&) = default;
349 explicit Delete(std::nullptr_t)
350 : D0<f & DC_DELETE>(nullptr)
351 , D1<f & CC_DELETE>(nullptr)
352 , D2<f & MC_DELETE>(nullptr)
353 , D3<f & CA_DELETE>(nullptr)
354 , D4<f & MA_DELETE>(nullptr)
358 //-----------------------------------------------------------------------------
361 struct TickException : std::runtime_error {
362 explicit TickException(const std::string& s)
363 : std::runtime_error("tick: " + s) {}
367 static int CountTicks;
368 static int TicksLeft;
369 static void Tick(const std::string& s) {
370 if (TicksLeft == 0) throw TickException(s);
376 int Ticker::CountTicks = 0;
377 int Ticker::TicksLeft = -1;
380 struct DataTicker : Ticker {
381 DataTicker() noexcept(f & DC_NOEXCEPT) {
382 if (!(f & DC_NOEXCEPT)) Tick("Data()");
384 DataTicker(const DataTicker&) noexcept(f & CC_NOEXCEPT) {
385 if (!(f & CC_NOEXCEPT)) Tick("Data(const Data&)");
387 DataTicker(DataTicker&&) noexcept(f & MC_NOEXCEPT) {
388 if (!(f & MC_NOEXCEPT)) Tick("Data(Data&&)");
390 explicit DataTicker(std::nullptr_t) noexcept(f & OC_NOEXCEPT) {
391 if (!(f & OC_NOEXCEPT)) Tick("Data(int)");
393 ~DataTicker() noexcept {}
394 void operator=(const DataTicker&) noexcept(f & CA_NOEXCEPT) {
395 if (!(f & CA_NOEXCEPT)) Tick("op=(const Data&)");
397 void operator=(DataTicker&&) noexcept(f & MA_NOEXCEPT) {
398 if (!(f & MA_NOEXCEPT)) Tick("op=(Data&&)");
402 //-----------------------------------------------------------------------------
406 static int CountDC, CountCC, CountMC, CountOC, CountCA, CountMA;
407 static int CountDestroy, CountTotalOps, CountLoggedConstruction;
409 Counter() noexcept { CountTotalOps++; CountDC++; }
410 Counter(const Counter&) noexcept { CountTotalOps++; CountCC++; }
411 Counter(Counter&&) noexcept { CountTotalOps++; CountMC++; }
412 explicit Counter(std::nullptr_t) noexcept { CountTotalOps++; CountOC++; }
413 void operator=(const Counter&) noexcept { CountTotalOps++; CountCA++; }
414 void operator=(Counter&&) noexcept { CountTotalOps++; CountMA++; }
415 ~Counter() noexcept { CountTotalOps++; CountDestroy++; }
418 int Counter::CountDC = 0;
419 int Counter::CountCC = 0;
420 int Counter::CountMC = 0;
421 int Counter::CountOC = 0;
422 int Counter::CountCA = 0;
423 int Counter::CountMA = 0;
424 int Counter::CountDestroy = 0;
425 int Counter::CountTotalOps = 0;
426 int Counter::CountLoggedConstruction = 0;
428 //-----------------------------------------------------------------------------
433 static std::map<int, int> UIDCount;
435 static std::map<const Tracker*, int> Locations;
441 Tracker(Tracker* self, int uid) : self(self), uid(uid) {}
444 template <bool isRelocatable>
445 struct DataTracker : Tracker {
446 DataTracker() noexcept : Tracker(this, UID++) {
449 if (!isRelocatable) Locations[self] = uid;
452 DataTracker(const DataTracker& o) noexcept : Tracker(this, o.uid) {
455 if (!isRelocatable) Locations[self] = uid;
456 print("Data(const Data&)");
458 DataTracker(DataTracker&& o) noexcept : Tracker(this, o.uid) {
461 if (!isRelocatable) Locations[self] = uid;
462 print("Data(Data&&)");
465 explicit DataTracker(int uid) noexcept : Tracker(this, uid) {
468 if (!isRelocatable) Locations[self] = uid;
472 ~DataTracker() noexcept {
475 if (!isRelocatable) Locations.erase(self);
478 self = (DataTracker*)0xfeebdaed;
481 DataTracker& operator=(const DataTracker& o) noexcept {
485 if (!isRelocatable) Locations[self] = uid;
486 print("op=(const Data&)");
489 DataTracker& operator=(DataTracker&& o) noexcept {
493 if (!isRelocatable) Locations[self] = uid;
494 print("op=(Data&&)");
498 void print(const std::string& fun) {
500 std::cerr << std::setw(20) << fun << ": uid = " << std::setw(3) << uid;
501 if (!isRelocatable) std::cerr << ", self = " << self;
502 std::cerr << std::endl;
507 int Tracker::UID = 1234;
508 std::map<int, int> Tracker::UIDCount;
509 int Tracker::UIDTotal = 0;
510 std::map<const Tracker*, int> Tracker::Locations;
511 bool Tracker::Print = false;
513 //-----------------------------------------------------------------------------
514 //-----------------------------------------------------------------------------
517 template <Flags f = 0, size_t pad = 0>
518 struct Data : DataTracker<f & IS_RELOCATABLE>,
519 Counter, DataTicker<f>, Delete<f> {
520 static const Flags flags = f;
521 char spacehog[pad ? pad : 1];
524 Data(const Data&) = default;
525 Data(Data&&) = default;
526 /* implicit */ Data(int i)
527 : DataTracker<f & IS_RELOCATABLE>(i), Counter()
528 , DataTicker<f>(nullptr)
532 Data& operator=(const Data&) = default;
533 Data& operator=(Data&&) = default;
536 int operator&() const;
540 template <Flags f, size_t pad>
541 struct IsRelocatable<Data<f, pad>>
542 : std::integral_constant<bool,
547 //-----------------------------------------------------------------------------
548 //-----------------------------------------------------------------------------
551 template <typename T>
552 struct isPropCopy : true_type {};
553 template <Flags f, size_t pad>
554 struct isPropCopy<Data<f, pad>> :
555 std::integral_constant<bool, f & PROP_COPY> {};
557 template <typename T>
558 struct isPropMove : true_type {};
559 template <Flags f, size_t pad>
560 struct isPropMove<Data<f, pad>> :
561 std::integral_constant<bool, f & PROP_MOVE> {};
563 template <typename T>
564 struct isPropSwap : true_type {};
565 template <Flags f, size_t pad>
566 struct isPropSwap<Data<f, pad>> :
567 std::integral_constant<bool, f & PROP_SWAP> {};
570 struct AllocTracker {
571 static int Constructed;
572 static int Destroyed;
573 static map<void*, size_t> Allocated;
574 static map<void*, int> Owner;
576 int AllocTracker::Constructed = 0;
577 int AllocTracker::Destroyed = 0;
578 map<void*, size_t> AllocTracker::Allocated;
579 map<void*, int> AllocTracker::Owner;
582 struct Alloc : AllocTracker, Ticker {
583 typedef typename std::allocator<T>::pointer pointer;
584 typedef typename std::allocator<T>::const_pointer const_pointer;
585 typedef typename std::allocator<T>::size_type size_type;
586 typedef typename std::allocator<T>::value_type value_type;
593 explicit Alloc(int i = 8) : a(a), id(i) {}
594 Alloc(const Alloc& o) : a(o.a), id(o.id) {}
595 Alloc(Alloc&& o) : a(move(o.a)), id(o.id) {}
596 Alloc& operator=(const Alloc&) = default;
597 Alloc& operator=(Alloc&&) = default;
598 bool operator==(const Alloc& o) const { return a == o.a && id == o.id; }
599 bool operator!=(const Alloc& o) const { return !(*this == o); }
604 pointer allocate(size_type n) {
606 cerr << "called allocate(0)" << endl;
607 throw runtime_error("allocate fail");
610 auto p = a.allocate(n);
616 void deallocate(pointer p, size_type n) {
618 cerr << "deallocate(nullptr, " << n << ")" << endl;
619 FAIL() << "deallocate failed";
621 if (Allocated[p] != n) {
622 cerr << "deallocate(" << p << ", " << n << ") invalid: ";
623 if (Allocated[p] == 0) cerr << "never allocated";
624 else if (Allocated[p] == -1) cerr << "already deallocated";
625 else cerr << "wrong number (want " << Allocated[p] << ")";
627 FAIL() << "deallocate failed";
629 if (Owner[p] != id) {
630 cerr << "deallocate(" << p << "), where pointer is owned by "
631 << Owner[p] << ", instead of self - " << id << endl;
632 FAIL() << "deallocate failed";
638 template <class U, class... Args>
639 void construct(U* p, Args&&... args) {
641 a.construct(p, std::forward<Args>(args)...);
654 Alloc select_on_container_copy_construction() const {
655 Tick("select allocator for copy");
656 return Alloc(id + 1);
659 typedef isPropCopy<T> propagate_on_container_copy_assignment;
660 typedef isPropMove<T> propagate_on_container_move_assignment;
661 typedef isPropSwap<T> propagate_on_container_swap;
664 //=============================================================================
665 //=============================================================================
666 // Verification and resetting
668 void softReset(int ticks = -1) {
669 Counter::CountLoggedConstruction +=
670 Counter::CountDC + Counter::CountCC + Counter::CountMC
671 + Counter::CountOC - Counter::CountDestroy;
672 Counter::CountDC = Counter::CountCC = Counter::CountMC
673 = Counter::CountOC = Counter::CountCA = Counter::CountMA = 0;
674 Counter::CountDestroy = Counter::CountTotalOps = 0;
675 Ticker::CountTicks = 0;
676 Ticker::TicksLeft = ticks;
680 Tracker::UIDCount.clear();
681 Tracker::UIDTotal = 0;
682 Tracker::Locations.clear();
684 Counter::CountLoggedConstruction = 0;
686 AllocTracker::Constructed = 0;
687 AllocTracker::Destroyed = 0;
688 AllocTracker::Allocated.clear();
689 AllocTracker::Owner.clear();
693 int con = Counter::CountDC + Counter::CountCC
694 + Counter::CountMC + Counter::CountOC
695 + Counter::CountLoggedConstruction;
696 int del = Counter::CountDestroy;
701 int tot = getTotal();
702 ASSERT_GE(tot, 0) << "more objects deleted than constructed";
704 ASSERT_EQ(tot, Tracker::UIDTotal)
705 << "UIDTotal has incorrect number of objects";
708 for (const auto& kv : Tracker::UIDCount) {
709 ASSERT_TRUE(kv.second >= 0) << "there exists " << kv.second << " Data "
710 "with uid " << kv.first;
713 ASSERT_EQ(tot, altTot) << "UIDCount corrupted";
715 if (!Tracker::Locations.empty()) { // implied by IsRelocatable
716 ASSERT_EQ(tot, Tracker::Locations.size())
717 << "Locations has incorrect number of objects";
718 for (const auto& du : Tracker::Locations) {
719 ASSERT_EQ(du.second, du.first->uid) << "Locations contains wrong uid";
720 ASSERT_EQ(du.first, du.first->self) << "Data.self is corrupted";
725 //-----------------------------------------------------------------------------
728 template <typename T>
729 struct is_copy_constructibleAndAssignable
730 : std::integral_constant<bool,
731 std::is_copy_constructible<T>::value &&
732 std::is_copy_assignable<T>::value
735 template <typename T>
736 struct is_move_constructibleAndAssignable
737 : std::integral_constant<bool,
738 std::is_move_constructible<T>::value &&
739 std::is_move_assignable<T>::value
742 template <class Vector>
743 struct customAllocator
744 : std::integral_constant<bool,
746 typename Vector::allocator_type,
747 std::allocator<typename Vector::value_type>
751 template <typename T>
752 struct special_move_assignable
753 : is_move_constructibleAndAssignable<T> {};
754 template <Flags f, size_t pad>
755 struct special_move_assignable<Data<f, pad>>
756 : std::integral_constant<bool,
757 is_move_constructibleAndAssignable<Data<f, pad>>::value ||
761 //=============================================================================
762 //=============================================================================
765 //-----------------------------------------------------------------------------
769 unsigned reslo, reshi;
771 __asm__ __volatile__ (
772 "xorl %%eax,%%eax \n cpuid \n"
773 ::: "%eax", "%ebx", "%ecx", "%edx");
774 __asm__ __volatile__ (
776 : "=a" (reslo), "=d" (reshi) );
777 __asm__ __volatile__ (
778 "xorl %%eax,%%eax \n cpuid \n"
779 ::: "%eax", "%ebx", "%ecx", "%edx");
781 return ((uint64_t)reshi << 32) | reslo;
784 //-----------------------------------------------------------------------------
787 #define IBOOST_PP_VARIADIC_SIZE(...) IBOOST_PP_VARIADIC_SIZE_I(__VA_ARGS__, \
788 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, \
789 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, \
790 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, \
791 7, 6, 5, 4, 3, 2, 1,)
792 #define IBOOST_PP_VARIADIC_SIZE_I(e0, e1, e2, e3, e4, e5, e6, e7, e8, e9, \
793 e10, e11, e12, e13, e14, e15, e16, e17, e18, e19, e20, e21, e22, e23, e24, \
794 e25, e26, e27, e28, e29, e30, e31, e32, e33, e34, e35, e36, e37, e38, e39, \
795 e40, e41, e42, e43, e44, e45, e46, e47, e48, e49, e50, e51, e52, e53, e54, \
796 e55, e56, e57, e58, e59, e60, e61, e62, e63, size, ...) size
797 #define IBOOST_PP_VARIADIC_TO_SEQ(args...) \
798 BOOST_PP_TUPLE_TO_SEQ(IBOOST_PP_VARIADIC_SIZE(args), (args))
800 //-----------------------------------------------------------------------------
803 #define GEN_TEST(r, name, type) \
805 string atype = PrettyType<typename type::allocator_type>()(); \
806 string ptype = PrettyType<typename type::value_type>()(); \
807 SCOPED_TRACE("allocator: " + atype); { \
808 SCOPED_TRACE("datatype: " + ptype); { \
809 test_ ## name ## 3 <type> (); \
810 if (::testing::Test::HasFatalFailure()) return; \
812 #define GEN_TYPE_TEST(r, name, type) \
813 if (0) test_I_ ## name ## 3 <type> ();
814 #define GEN_RUNNABLE_TEST(r, name, type) \
815 one = test_I_ ## name ## 3 <type> () || one;
817 #define GEN_LOOPER(r, d, arg) BOOST_PP_CAT(LOOPER_, arg)
818 #define GEN_VMAKER(r, d, arg) { BOOST_PP_CAT(VMAKER_, arg) {
819 #define GEN_UMAKER(r, d, arg) } BOOST_PP_CAT(UMAKER_, arg) }
820 #define GEN_CLOSER(r, d, arg) BOOST_PP_CAT(CLOSER_, arg)
822 #define TYPIFY(r, d, name) BOOST_PP_CAT(TYPIFY_, name)
823 #define ARGIFY(r, d, name) TYPIFY(r, d, name) name
825 #define MAKE_TEST(ref, name, types, restriction, argseq, rawargs...) \
826 template <class Vector> void test_ ## name ## 2 (std::false_type) {} \
827 template <class Vector> void test_ ## name ## 2 (std::true_type) { \
828 BOOST_PP_SEQ_FOR_EACH(GEN_LOOPER, _, argseq) \
830 BOOST_PP_SEQ_FOR_EACH(GEN_VMAKER, _, argseq) \
832 test_ ## name <Vector, typename Vector::value_type, \
833 typename Vector::allocator_type> ( rawargs ); \
834 if (::testing::Test::HasFatalFailure()) return; \
836 BOOST_PP_SEQ_FOR_EACH(GEN_UMAKER, _, BOOST_PP_SEQ_REVERSE(argseq)) \
838 BOOST_PP_SEQ_FOR_EACH(GEN_CLOSER, _, BOOST_PP_SEQ_REVERSE(argseq)) \
840 template <class Vector> void test_ ## name ## 3 () { \
841 test_ ## name ## 2 <Vector> (std::integral_constant<bool, \
842 restriction<typename Vector::value_type>::value && \
843 is_copy_constructible<typename Vector::value_type>::value \
847 template <class Vector> bool test_I_ ## name ## 2 (std::false_type) \
849 template <class Vector> bool test_I_ ## name ## 2 (std::true_type) { \
851 auto f = test_ ## name <Vector, \
852 typename Vector::value_type, typename Vector::allocator_type>; \
855 template <class Vector> bool test_I_ ## name ## 3 () { \
856 return test_I_ ## name ## 2 <Vector> (std::integral_constant<bool, \
857 restriction<typename Vector::value_type>::value>()); \
861 TEST(FBVector, name) { \
862 SCOPED_TRACE("N3337 reference: " ref); \
863 BOOST_PP_SEQ_FOR_EACH(GEN_TEST, name, types) \
864 BOOST_PP_SEQ_FOR_EACH(GEN_TYPE_TEST, name, INTERFACE_TYPES) \
866 BOOST_PP_SEQ_FOR_EACH(GEN_RUNNABLE_TEST, name, types) \
867 if (!one) FAIL() << "No tests qualified to run"; \
870 #define DECL(name, args...) \
871 template <class Vector, typename T, typename Allocator> \
872 void test_ ## name (BOOST_PP_SEQ_ENUM(BOOST_PP_SEQ_TRANSFORM( \
873 ARGIFY, _, IBOOST_PP_VARIADIC_TO_SEQ(args))))
875 #define STL_TEST_I(ref, name, restriction, args...) \
877 MAKE_TEST(ref, name, TEST_TYPES, restriction, \
878 IBOOST_PP_VARIADIC_TO_SEQ(args), args) \
881 #define STL_TEST(ref, name, restriction, args...) \
882 STL_TEST_I(ref, name, restriction, z, ## args, ticks)
884 //-----------------------------------------------------------------------------
888 typedef Data<0, 4080> ED2;
889 typedef Data<MC_NOEXCEPT> ED3;
890 typedef Data<MC_NOEXCEPT | CC_DELETE> ED4;
891 typedef Data<IS_RELOCATABLE> ED5;
893 typedef VECTOR_<int, std::allocator<int>> _TVIS;
894 typedef VECTOR_<int, Alloc<int>> _TVI;
895 typedef VECTOR_<ED1, std::allocator<ED1>> _TV1;
896 typedef VECTOR_<ED2, std::allocator<ED2>> _TV2;
897 typedef VECTOR_<ED3, std::allocator<ED3>> _TV3;
898 typedef VECTOR_<ED4, std::allocator<ED4>> _TV4;
899 typedef VECTOR_<ED5, std::allocator<ED5>> _TV5v1;
900 typedef VECTOR_<ED5, Alloc<ED5>> _TV5;
902 typedef Data<PROP_COPY> EP1;
903 typedef Data<PROP_MOVE> EP2;
904 typedef Data<PROP_SWAP> EP3;
906 typedef VECTOR_<EP1, Alloc<EP1>> _TP1;
907 typedef VECTOR_<EP2, Alloc<EP2>> _TP2;
908 typedef VECTOR_<EP3, Alloc<EP3>> _TP3;
910 #define TEST_TYPES (_TVIS)(_TVI)(_TV1)(_TV2)(_TV3)(_TV4)(_TV5v1)(_TV5) \
913 typedef Data<ALL_DELETE> DD1; // unoperable
914 typedef Data<DC_DELETE | CC_DELETE | MC_DELETE> DD2; // unconstructible
915 typedef Data<CA_DELETE | MA_DELETE> DD3; // unassignable
916 typedef Data<CC_DELETE | MC_DELETE> DD4; // uncopyable
917 typedef Data<ALL_DELETE & ~DC_DELETE> DD5; // only default constructible
918 typedef Data<CC_DELETE> DD6; // move-only copy construction
919 typedef Data<CA_DELETE> DD7; // move-only assignment
921 typedef Data<ALL_DELETE | PROP_MOVE> DDSMA;
922 typedef VECTOR_<DDSMA, Alloc<DDSMA>> _TSpecialMA;
924 #define INTERFACE_TYPES \
925 (_TVI)(VECTOR_<DD1>)(VECTOR_<DD2>)(VECTOR_<DD3>) \
926 (VECTOR_<DD4>)(VECTOR_<DD5>)(VECTOR_<DD6>) \
927 (VECTOR_<DD7>)(_TSpecialMA)
929 //-----------------------------------------------------------------------------
932 template <typename T>
934 string operator()() {
935 if (is_same<T, int>::value) return "int";
936 if (is_same<T, char>::value) return "char";
937 if (is_same<T, uint64_t>::value) return "uint64_t";
938 return typeid(T).name();
942 template <Flags f, size_t pad>
943 struct PrettyType<Data<f, pad>> {
944 string operator()() {
948 if ((f & DC_DELETE) ||
954 if (f & DC_DELETE) tpe << " DC,";
955 if (f & CC_DELETE) tpe << " CC,";
956 if (f & MC_DELETE) tpe << " MC,";
957 if (f & CA_DELETE) tpe << " CA,";
958 if (f & MA_DELETE) tpe << " MA,";
962 if ((f & DC_NOEXCEPT) ||
968 if (f & DC_NOEXCEPT) tpe << " DC,";
969 if (f & CC_NOEXCEPT) tpe << " CC,";
970 if (f & MC_NOEXCEPT) tpe << " MC,";
971 if (f & CA_NOEXCEPT) tpe << " CA,";
972 if (f & MA_NOEXCEPT) tpe << " MA,";
976 if (f & IS_RELOCATABLE) {
977 tpe << "(relocatable)";
981 tpe << "{pad " << pad << "}";
988 template <typename T>
989 struct PrettyType<std::allocator<T>> {
990 string operator()() {
991 return "std::allocator<" + PrettyType<T>()() + ">";
995 template <typename T>
996 struct PrettyType<Alloc<T>> {
997 string operator()() {
998 return "Alloc<" + PrettyType<T>()() + ">";
1002 //-----------------------------------------------------------------------------
1003 // Setup, teardown, runup, rundown
1005 // These four macros are run once per test. Setup and runup occur before the
1006 // test, teardown and rundown after. Setup and runup straddle the
1007 // initialization sequence, whereas rundown and teardown straddle the
1010 #define SETUP hardReset();
1013 //-----------------------------------------------------------------------------
1014 // Types and typegens
1019 #define TYPIFY_z std::nullptr_t
1021 Vector* a_p = nullptr; Vector* b_p = nullptr; \
1022 typename Vector::value_type* t_p = nullptr;
1023 #define VMAKER_z std::nullptr_t z = nullptr;
1025 verify<Vector>(0); \
1026 if (::testing::Test::HasFatalFailure()) return;
1032 #define VERIFICATION \
1033 if (b_p != nullptr) verify(t_p != nullptr ,*a_p, *b_p); \
1034 else if (a_p != nullptr) verify(t_p != nullptr, *a_p); \
1035 else verify<Vector>(t_p != nullptr); \
1036 if (::testing::Test::HasFatalFailure()) return;
1038 #define TYPIFY_ticks int
1039 #define LOOPER_ticks \
1040 int _maxTicks_ = 0; \
1041 bool ticks_thrown = false; \
1042 for (int ticks = -1; ticks < _maxTicks_; ++ticks) {
1043 #define VMAKER_ticks \
1044 string ticks_st = folly::to<string>("ticks = ", ticks); \
1045 SCOPED_TRACE(ticks_st); \
1046 { SCOPED_TRACE("pre-run verification"); \
1050 #define UMAKER_ticks _maxTicks_ = Ticker::CountTicks; } \
1051 catch (const TickException&) { ticks_thrown = true; } \
1052 catch (const std::exception& e) \
1053 { FAIL() << "EXCEPTION: " << e.what(); } \
1055 { FAIL() << "UNKNOWN EXCEPTION"; } \
1056 if (ticks >= 0 && Ticker::CountTicks > ticks && !ticks_thrown) \
1057 FAIL() << "CountTicks = " << Ticker::CountTicks << " > " \
1058 << ticks << " = ticks" \
1059 << ", but no tick error was observed"; \
1061 #define CLOSER_ticks }
1064 //--------------------------------------------------
1065 // vectors (second could be .equal, ==, or distinct)
1067 static const vector<pair<int, int>> VectorSizes = {
1071 { 10, -1}, { 10, 1}, { 10, 0},
1072 {100, -1}, {100, 1},
1074 //{ 10, -1}, { 10, 0}, { 10, 1}, { 10, 2}, { 10, 10},
1075 //{ 100, -1}, { 100, 0}, { 100, 1}, { 100, 2}, { 100, 10}, { 100, 100},
1076 //{ 1000, -1}, { 1000, 0}, { 1000, 1}, { 1000, 2}, { 1000, 10}, { 1000, 100},
1080 int populateIndex = 1426;
1081 template <class Vector>
1082 void populate(Vector& v, const pair<int, int>& ss) {
1084 for (; i < ss.first; ++i) {
1085 v.emplace_back(populateIndex++);
1087 if (ss.second >= 0) {
1088 while (v.capacity() - v.size() != ss.second) {
1089 v.emplace_back(populateIndex++);
1094 template <typename A>
1096 static A get() { return A(); }
1098 template <typename T>
1099 struct allocGen<Alloc<T>> {
1100 static Alloc<T> get() {
1107 #define TYPIFY_a Vector&
1108 #define LOOPER_a for (const auto& a_ss : VectorSizes) {
1110 Vector a(allocGen<typename Vector::allocator_type>::get()); \
1112 populate(*a_p, a_ss); \
1113 string a_st = folly::to<string>("a (", a.size(), "/", a.capacity(), ")"); \
1115 #define UMAKER_a verify(0, a); if (::testing::Test::HasFatalFailure()) return;
1118 #define TYPIFY_b Vector&
1119 #define LOOPER_b for (int b_i = -2; b_i < (int)VectorSizes.size(); ++b_i) {
1121 Vector b_s(allocGen<typename Vector::allocator_type>::get()); \
1122 b_p = &b_s; string b_st; \
1125 b_st = "b is an alias of a"; \
1127 else if (b_i == -1) { \
1129 new (&b_s) Vector(a); \
1130 b_st = "b is a deep copy of a"; \
1133 populate(b_s, VectorSizes[b_i]); \
1134 b_st = folly::to<string>("b (", b_s.size(), "/", b_s.capacity(), ")"); \
1139 verify(0, a, b); if (::testing::Test::HasFatalFailure()) return;
1145 static const vector<int> nSizes = { 0, 1, 2, 9, 10, 11 };
1147 #define TYPIFY_n int
1148 #define LOOPER_n for (int n : nSizes) {
1150 string n_st = folly::to<string>("n = ", n); SCOPED_TRACE(n_st);
1154 //-----------------------
1155 // non-internal iterators
1157 static int ijarr[12] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
1158 static int ijarC[12] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
1160 #define TYPIFY_i int*
1162 #define VMAKER_i int* i = ijarr; SCOPED_TRACE("i = fib[0]");
1166 #define TYPIFY_j int*
1167 #define LOOPER_j for (int j_i = 0; j_i < 12; ++j_i) {
1169 int* j = ijarr + j_i; \
1170 string j_st = folly::to<string>("j = fib[", j_i, "]"); \
1173 for (int j_c = 0; j_c < 12; ++j_c) ASSERT_EQ(ijarC[j_c], ijarr[j_c]);
1176 //-------------------
1177 // internal iterators
1179 template <class Vector>
1180 std::pair<typename Vector::iterator, string>
1181 iterSpotter(Vector& v, int i) {
1182 typename Vector::iterator it;
1187 if (v.empty()) ; // fall through
1200 if (v.empty()) ; // fall through
1213 cerr << "internal error" << endl;
1217 return make_pair(it, msg);
1220 #define TYPIFY_p typename Vector::iterator
1221 #define LOOPER_p for (int p_i = 0; p_i < 4; ++p_i) {
1223 auto p_im = iterSpotter(a, p_i); \
1224 auto& p = p_im.first; \
1225 auto& p_m = p_im.second; \
1226 SCOPED_TRACE("p = " + p_m);
1230 #define TYPIFY_q typename Vector::iterator
1231 #define LOOPER_q for (int q_i = p_i; q_i < 4; ++q_i) {
1233 auto q_im = iterSpotter(a, q_i); \
1234 auto& q = q_im.first; \
1235 auto& q_m = q_im.second; \
1236 SCOPED_TRACE("q = " + q_m);
1243 static const vector<int> tVals = { 0, 1, 2, 3, 17, 66, 521 };
1245 #define TYPIFY_t typename Vector::value_type&
1246 #define LOOPER_t for (int t_v : tVals) {
1248 typename Vector::value_type t_s(t_v); \
1249 t_p = addressof(t_s); \
1250 string t_st = folly::to<string>("t(", t_v, ")"); \
1251 if (t_v < 4 && a_p != nullptr) { \
1252 auto t_im = iterSpotter(*a_p, t_v); \
1253 if (t_im.first != a_p->end()) { \
1254 t_p = addressof(*t_im.first); \
1255 t_st = "t is " + t_im.second; \
1258 typename Vector::value_type& t = *t_p; \
1266 #define TYPIFY_m typename Vector::allocator_type
1268 int m_max = 1 + (a_p != nullptr); \
1269 for (int m_i = 0; m_i < m_max; ++m_i) {
1271 typename Vector::allocator_type m = m_i == 0 \
1272 ? typename Vector::allocator_type() \
1273 : a_p->get_allocator();
1277 //-----------------------------------------------------------------------------
1281 template <class Vector>
1282 void verifyVector(const Vector& v) {
1283 ASSERT_TRUE(v.begin() <= v.end()) << "end is before begin";
1284 ASSERT_TRUE(v.empty() == (v.begin() == v.end())) << "empty != (begin == end)";
1285 ASSERT_TRUE(v.size() == distance(v.begin(), v.end()))
1286 << "size != end - begin";
1287 ASSERT_TRUE(v.size() <= v.capacity()) << "size > capacity";
1288 ASSERT_TRUE(v.capacity() <= v.max_size()) << "capacity > max_size";
1289 ASSERT_TRUE(v.data() || true); // message won't print - it will just crash
1290 ASSERT_TRUE(v.size() == 0 || v.data() != nullptr)
1291 << "nullptr data points to at least one element";
1294 void verifyAllocator(int ele, int cap) {
1295 ASSERT_EQ(ele, AllocTracker::Constructed - AllocTracker::Destroyed);
1298 for (auto kv : AllocTracker::Allocated)
1299 if (kv.second != -1) tot += kv.second;
1300 ASSERT_EQ(cap, tot) << "the allocator counts " << tot << " space, "
1301 "but the vector(s) have (combined) capacity " << cap;
1305 template <class Vector>
1306 void verify(int extras) {
1307 if (!is_arithmetic<typename Vector::value_type>::value)
1308 ASSERT_EQ(0 + extras, getTotal()) << "there exist Data but no vectors";
1310 if (::testing::Test::HasFatalFailure()) return;
1311 if (customAllocator<Vector>::value) verifyAllocator(0, 0);
1313 template <class Vector>
1314 void verify(int extras, const Vector& v) {
1316 if (!is_arithmetic<typename Vector::value_type>::value)
1317 ASSERT_EQ(v.size() + extras, getTotal())
1318 << "not all Data are in the vector";
1320 if (::testing::Test::HasFatalFailure()) return;
1321 if (customAllocator<Vector>::value) verifyAllocator(v.size(), v.capacity());
1323 template <class Vector>
1324 void verify(int extras, const Vector& v1, const Vector& v2) {
1327 auto size = v1.size();
1328 auto cap = v1.capacity();
1331 cap += v2.capacity();
1333 if (!is_arithmetic<typename Vector::value_type>::value)
1334 ASSERT_EQ(size + extras, getTotal()) << "not all Data are in the vector(s)";
1336 if (::testing::Test::HasFatalFailure()) return;
1337 if (customAllocator<Vector>::value) verifyAllocator(size, cap);
1340 //=============================================================================
1343 // save the state of a vector
1344 int convertToInt(int t) {
1347 template <Flags f, size_t pad>
1348 int convertToInt(const Data<f, pad>& t) {
1351 template <typename T>
1352 int convertToInt(const std::allocator<T>&) {
1355 template <typename T>
1356 int convertToInt(const Alloc<T>& a) {
1360 template <class Vector>
1362 typedef typename Vector::size_type size_type;
1366 /* implicit */ DataState(const Vector& v) {
1369 data_ = new int[size_];
1370 for (size_type i = 0; i < size_; ++i) {
1371 data_[i] = convertToInt(v.data()[i]);
1381 bool operator==(const DataState& o) const {
1382 if (size_ != o.size_) return false;
1383 for (size_type i = 0; i < size_; ++i) {
1384 if (data_[i] != o.data_[i]) return false;
1389 int operator[](size_type i) {
1391 cerr << "trying to access DataState out of bounds" << endl;
1397 size_type size() { return size_; }
1400 // downgrade iterators
1401 template <typename It, class tag>
1402 class Transformer : public boost::iterator_adaptor<
1403 Transformer<It, tag>,
1405 typename iterator_traits<It>::value_type,
1408 friend class boost::iterator_core_access;
1409 shared_ptr<set<It>> dereferenced;
1412 explicit Transformer(const It& it)
1413 : Transformer::iterator_adaptor_(it)
1414 , dereferenced(new set<It>()) {}
1416 typename iterator_traits<It>::value_type& dereference() const {
1417 if (dereferenced->find(this->base_reference()) != dereferenced->end()) {
1418 cerr << "iterator dereferenced more than once" << endl;
1421 dereferenced->insert(this->base_reference());
1422 return *this->base_reference();
1426 template <typename It>
1427 Transformer<It, forward_iterator_tag> makeForwardIterator(const It& it) {
1428 return Transformer<It, forward_iterator_tag>(it);
1430 template <typename It>
1431 Transformer<It, input_iterator_tag> makeInputIterator(const It& it) {
1432 return Transformer<It, input_iterator_tag>(it);
1435 // mutate a value (in contract only)
1436 void mutate(int& i) {
1439 void mutate(uint64_t& i) {
1442 template <Flags f, size_t pad>
1443 void mutate(Data<f, pad>& ds) {
1444 if (false) ds.uid = 0;
1447 //=============================================================================
1456 //-----------------------------------------------------------------------------
1459 STL_TEST("23.2.1 Table 96.1-7", containerTypedefs, is_destructible) {
1460 static_assert(is_same<T, typename Vector::value_type>::value,
1461 "T != Vector::value_type");
1462 static_assert(is_same<T&, typename Vector::reference>::value,
1463 "T& != Vector::reference");
1464 static_assert(is_same<const T&, typename Vector::const_reference>::value,
1465 "const T& != Vector::const_reference");
1466 static_assert(is_convertible<
1467 typename iterator_traits<typename Vector::iterator>::iterator_category,
1468 forward_iterator_tag>::value,
1469 "Vector::iterator is not a forward iterator");
1470 static_assert(is_same<T,
1471 typename iterator_traits<typename Vector::iterator>::value_type>::value,
1472 "Vector::iterator does not iterate over type T");
1473 static_assert(is_convertible<
1474 typename iterator_traits<typename Vector::const_iterator>
1475 ::iterator_category,
1476 forward_iterator_tag>::value,
1477 "Vector::const_iterator is not a forward iterator");
1478 static_assert(is_same<T,
1479 typename iterator_traits<typename Vector::const_iterator>
1480 ::value_type>::value,
1481 "Vector::const_iterator does not iterate over type T");
1482 static_assert(is_convertible<
1483 typename Vector::iterator, typename Vector::const_iterator>::value,
1484 "Vector::iterator is not convertible to Vector::const_iterator");
1485 static_assert(is_signed<typename Vector::difference_type>::value,
1486 "Vector::difference_type is not signed");
1487 static_assert(is_same<typename Vector::difference_type,
1488 typename iterator_traits<typename Vector::iterator>
1489 ::difference_type>::value,
1490 "Vector::difference_type != Vector::iterator::difference_type");
1491 static_assert(is_same<typename Vector::difference_type,
1492 typename iterator_traits<typename Vector::const_iterator>
1493 ::difference_type>::value,
1494 "Vector::difference_type != Vector::const_iterator::difference_type");
1495 static_assert(is_unsigned<typename Vector::size_type>::value,
1496 "Vector::size_type is not unsigned");
1497 static_assert(sizeof(typename Vector::size_type) >=
1498 sizeof(typename Vector::difference_type),
1499 "Vector::size_type is smaller than Vector::difference_type");
1502 STL_TEST("23.2.1 Table 96.8-9", emptyConstruction, is_destructible) {
1505 ASSERT_TRUE(u.get_allocator() == Allocator());
1506 ASSERT_EQ(0, Counter::CountTotalOps);
1508 ASSERT_TRUE(u.empty()) << u.size();
1509 ASSERT_EQ(0, u.capacity());
1516 STL_TEST("framework", populate, is_copy_constructible) {
1517 // We use emplace_back to construct vectors for testing, as well as size,
1518 // data, and capacity. We make sure these work before proceeding with tests.
1521 ASSERT_EQ(0, u.size());
1522 ASSERT_EQ(nullptr, u.data());
1525 ASSERT_EQ(1, u.size());
1526 ASSERT_LT(u.capacity(), 100)
1527 << "single push_back increased capacity to " << u.capacity();
1528 ASSERT_NE(nullptr, u.data());
1529 ASSERT_EQ(17, convertToInt(u.data()[0]))
1530 << "first object did not get emplaced correctly";
1532 for (int i = 0; i < 3; ++i) {
1533 auto cap = u.capacity();
1534 while (u.size() < cap) {
1536 ASSERT_EQ(cap, u.capacity()) << "Vector grew when it did not need to";
1537 ASSERT_EQ(22, convertToInt(u.data()[u.size() - 1]))
1538 << "push_back with excess capacity failed";
1541 ASSERT_EQ(cap, u.size());
1544 ASSERT_GT(u.capacity(), cap) << "capacity did not grow on overflow";
1545 ASSERT_EQ(cap + 1, u.size());
1546 ASSERT_EQ(4, convertToInt(u.data()[u.size() - 1]))
1547 << "grow object did not get emplaced correctly";
1551 STL_TEST("23.2.1 Table 96.10-11", copyConstruction,
1552 is_copy_constructible, a) {
1554 DataState<Vector> dsa(ca);
1555 auto am = a.get_allocator();
1559 ASSERT_TRUE(std::allocator_traits<Allocator>::
1560 select_on_container_copy_construction(am) == u.get_allocator());
1561 ASSERT_TRUE(dsa == u);
1563 (ca.data() == nullptr && u.data() == nullptr) ||
1564 (ca.data() != u.data())
1565 ) << "only a shallow copy was made";
1573 STL_TEST("23.2.1 Table 96.12", moveConstruction, is_destructible, a) {
1574 DataState<Vector> dsa(a);
1575 auto m = a.get_allocator();
1579 ASSERT_TRUE(m == u.get_allocator());
1580 ASSERT_EQ(0, Counter::CountTotalOps);
1582 ASSERT_TRUE(dsa == u);
1589 STL_TEST("23.2.1 Table 96.13", moveAssignment, special_move_assignable, a, b) {
1590 DataState<Vector> dsb(b);
1591 auto am = a.get_allocator();
1592 auto bm = b.get_allocator();
1594 Vector& ret = a = std::move(b);
1596 if (std::allocator_traits<Allocator>::
1597 propagate_on_container_move_assignment::value) {
1598 ASSERT_TRUE(bm == a.get_allocator());
1600 ASSERT_TRUE(am == a.get_allocator());
1602 ASSERT_TRUE(&ret == &a);
1603 ASSERT_TRUE(&a == &b || dsb == a) << "move assignment did not create a copy";
1604 // The source of the move may be left in any (albeit valid) state.
1607 STL_TEST("23.2.1 Table 96.14", destructible, is_destructible) {
1608 // The test generators check this clause already.
1611 STL_TEST("23.2.1 Table 96.15-18", iterators, is_destructible, a) {
1612 DataState<Vector> dsa(a);
1615 auto itb = a.begin();
1616 auto citb = ca.begin();
1617 auto Citb = a.cbegin();
1619 auto cite = ca.end();
1620 auto Cite = a.cend();
1622 ASSERT_EQ(0, Counter::CountTotalOps);
1624 ASSERT_TRUE(dsa == a) << "call to begin or end modified internal data";
1626 ASSERT_TRUE(citb == Citb) << "cv.begin != v.cbegin";
1627 ASSERT_TRUE(cite == Cite) << "cv.end != v.cend";
1629 if (ca.size() == 0) {
1630 ASSERT_TRUE( itb == ite) << "begin != end when empty";
1631 ASSERT_TRUE(Citb == Cite) << "cbegin != cend when empty";
1633 ASSERT_TRUE( itb != ite) << "begin == end when non-empty";
1634 ASSERT_TRUE(Citb != Cite) << "cbegin == cend when non-empty";
1637 auto dist = std::distance( itb, ite);
1638 auto Cdist = std::distance(Citb, Cite);
1639 ASSERT_TRUE( dist == ca.size()) << "distance(begin, end) != size";
1640 ASSERT_TRUE(Cdist == ca.size()) << "distance(cbegin, cend) != size";
1643 STL_TEST("23.2.1 Table 96.19-20", equitable, is_arithmetic, a, b) {
1646 DataState<Vector> dsa(a);
1647 DataState<Vector> dsb(b);
1649 ASSERT_TRUE((bool)(ca == cb) == (bool)(dsa == dsb))
1650 << "== does not return equality";
1651 ASSERT_TRUE((bool)(ca == cb) != (bool)(ca != cb))
1652 << "!= is not the opposite of ==";
1654 // Data is uncomparable, by design; therefore this test's restriction
1655 // is 'is_arithmetic'
1658 STL_TEST("23.2.1 Table 96.21", memberSwappable, is_destructible, a, b) {
1659 if (!std::allocator_traits<Allocator>::
1660 propagate_on_container_swap::value &&
1661 convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1662 // undefined behaviour
1666 DataState<Vector> dsa(a);
1667 DataState<Vector> dsb(b);
1668 auto adata = a.data();
1669 auto bdata = b.data();
1670 auto am = a.get_allocator();
1671 auto bm = b.get_allocator();
1676 FAIL() << "swap is noexcept";
1679 if (std::allocator_traits<Allocator>::
1680 propagate_on_container_swap::value) {
1681 ASSERT_TRUE(bm == a.get_allocator());
1682 ASSERT_TRUE(am == b.get_allocator());
1684 ASSERT_TRUE(am == a.get_allocator());
1685 ASSERT_TRUE(bm == b.get_allocator());
1687 ASSERT_EQ(0, Counter::CountTotalOps);
1689 ASSERT_TRUE(adata == b.data() && bdata == a.data());
1690 ASSERT_TRUE(dsa == b && dsb == a) << "swap did not swap";
1693 STL_TEST("23.2.1 Table 96.22", nonmemberSwappable,
1694 is_destructible, a, b) {
1695 if (!std::allocator_traits<Allocator>::
1696 propagate_on_container_swap::value &&
1697 convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1698 // undefined behaviour
1702 DataState<Vector> dsa(a);
1703 DataState<Vector> dsb(b);
1704 auto adata = a.data();
1705 auto bdata = b.data();
1706 auto am = a.get_allocator();
1707 auto bm = b.get_allocator();
1712 FAIL() << "swap is noexcept";
1715 if (std::allocator_traits<Allocator>::
1716 propagate_on_container_swap::value) {
1717 ASSERT_TRUE(bm == a.get_allocator());
1718 ASSERT_TRUE(am == b.get_allocator());
1720 ASSERT_TRUE(am == a.get_allocator());
1721 ASSERT_TRUE(bm == b.get_allocator());
1723 ASSERT_EQ(0, Counter::CountTotalOps);
1725 ASSERT_TRUE(adata == b.data() && bdata == a.data());
1726 ASSERT_TRUE(dsa == b && dsb == a) << "swap did not swap";
1729 STL_TEST("23.2.1 Table 96.23", copyAssign,
1730 is_copy_constructibleAndAssignable, a, b) {
1731 // it is possible to make use of just the copy constructor.
1733 #ifdef USING_STD_VECTOR
1734 if (std::allocator_traits<Allocator>::
1735 propagate_on_container_copy_assignment::value &&
1736 convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1737 // Bug. By the looks of things, in the above case, their bez is being
1738 // cleared and deallocated, but then the garbage pointers are being used.
1744 DataState<Vector> dsb(cb);
1745 auto am = a.get_allocator();
1746 auto bm = b.get_allocator();
1748 Vector& ret = a = cb;
1750 if (std::allocator_traits<Allocator>::
1751 propagate_on_container_copy_assignment::value) {
1752 ASSERT_TRUE(bm == a.get_allocator());
1754 ASSERT_TRUE(am == a.get_allocator());
1756 ASSERT_TRUE(&ret == &a);
1757 ASSERT_TRUE(dsb == a) << "copy-assign not equal to original";
1760 STL_TEST("23.2.1 Table 96.24-26", sizeops, is_destructible) {
1761 // This check generators check this clause already.
1764 //-----------------------------------------------------------------------------
1765 // Reversible container
1767 STL_TEST("23.2.1 Table 97.1-2", reversibleContainerTypedefs,
1769 static_assert(is_same<typename Vector::reverse_iterator,
1770 std::reverse_iterator<typename Vector::iterator>>::value,
1771 "Vector::reverse_iterator != reverse_iterator<Vector:iterator");
1772 static_assert(is_same<typename Vector::const_reverse_iterator,
1773 std::reverse_iterator<typename Vector::const_iterator>>::value,
1774 "Vector::const_reverse_iterator != "
1775 "const_reverse_iterator<Vector::iterator");
1778 STL_TEST("23.2.1 Table 97.3-5", reversibleIterators, is_destructible, a) {
1780 DataState<Vector> ds(a);
1782 auto ritb = a.rbegin();
1783 auto critb = ca.rbegin();
1784 auto Critb = a.crbegin();
1785 auto rite = a.rend();
1786 auto crite = ca.rend();
1787 auto Crite = a.crend();
1789 ASSERT_EQ(0, Counter::CountTotalOps);
1791 ASSERT_TRUE(ds == a) << "call to rbegin or rend modified internal data";
1793 ASSERT_TRUE(critb == Critb) << "cv.rbegin != v.crbegin";
1794 ASSERT_TRUE(crite == Crite) << "cv.rend != v.crend";
1796 if (ca.size() == 0) {
1797 ASSERT_TRUE( ritb == rite) << "rbegin != rend when empty";
1798 ASSERT_TRUE(Critb == Crite) << "crbegin != crend when empty";
1800 ASSERT_TRUE( ritb != rite) << "rbegin == rend when non-empty";
1801 ASSERT_TRUE(Critb != Crite) << "crbegin == crend when non-empty";
1804 auto dist = std::distance( ritb, rite);
1805 auto Cdist = std::distance(Critb, Crite);
1806 ASSERT_TRUE( dist == ca.size()) << "distance(rbegin, rend) != size";
1807 ASSERT_TRUE(Cdist == ca.size()) << "distance(crbegin, crend) != size";
1810 //-----------------------------------------------------------------------------
1811 // Lexicographical functions
1813 STL_TEST("23.2.1 Table 98", comparable, is_arithmetic) {
1814 const Vector v1 = { 1, 2, 3, 4 };
1815 const Vector v2 = { 1, 2, 3, 4, 5 };
1816 const Vector v3 = { 1, 2, 2 };
1817 const Vector v4 = { 1, 2, 2, 4, 5 };
1818 const Vector v5 = { };
1819 const Vector v6 = { 1, 2, 3, 4 };
1821 ASSERT_TRUE(v1 < v2);
1822 ASSERT_TRUE(v1 > v3);
1823 ASSERT_TRUE(v1 > v4);
1824 ASSERT_TRUE(v1 > v5);
1825 ASSERT_TRUE(v1 <= v6);
1826 ASSERT_TRUE(v1 >= v6);
1829 //-----------------------------------------------------------------------------
1830 // Allocator-aware requirements (AA)
1832 STL_TEST("23.2.1 Table 99.1", allocatorTypedefs, is_destructible) {
1833 static_assert(is_same<T, typename Vector::allocator_type::value_type>::value,
1834 "Vector and vector's allocator value_type mismatch");
1837 STL_TEST("23.2.1 Table 99.2", getAllocator, is_destructible) {
1838 // whitebox: ensure that a.get_allocator() returns a copy of its allocator
1841 STL_TEST("23.2.1 Table 99.3", defaultAllocator, is_destructible) {
1842 // there is nothing new to test here
1845 STL_TEST("23.2.1 Table 99.4", customAllocator, is_destructible, m) {
1850 ASSERT_TRUE(u.get_allocator() == m);
1857 STL_TEST("23.2.1 Table 99.5", copyWithAllocator, is_copy_constructible, a, m) {
1858 DataState<Vector> dsa(a);
1864 ASSERT_TRUE(u.get_allocator() == m);
1865 ASSERT_TRUE(dsa == u);
1867 (ca.data() == nullptr && u.data() == nullptr) ||
1868 (ca.data() != u.data())
1869 ) << "only a shallow copy was made";
1872 STL_TEST("23.2.1 Table 99.6", moveConstructionWithAllocator,
1873 is_destructible, a) {
1874 // there is nothing new to test here
1877 STL_TEST("23.2.1 Table 99.6", moveConstructionWithAllocatorSupplied,
1878 is_move_constructible, a, m) {
1879 bool deep = m != a.get_allocator();
1880 auto osize = a.size();
1881 auto oalloc = AllocTracker::Constructed;
1884 Vector u(std::move(a), cm);
1886 ASSERT_TRUE(u.get_allocator() == m);
1889 if (!AllocTracker::Allocated.empty()) {
1890 ASSERT_EQ(osize, AllocTracker::Constructed - oalloc);
1893 ASSERT_EQ(0, Counter::CountTotalOps);
1897 STL_TEST("23.2.1 Table 99.7-9", allocAssign, is_destructible) {
1898 // there is nothing new to test here
1901 STL_TEST("23.2.1-7", nAllocConstruction, is_copy_constructible, n, m) {
1902 #ifndef USING_STD_VECTOR
1907 ASSERT_TRUE(m == u.get_allocator());
1911 STL_TEST("23.2.1-7", nCopyAllocConstruction, is_copy_constructible, n, t, m) {
1915 Vector u(n, ct, cm);
1917 ASSERT_TRUE(m == u.get_allocator());
1920 STL_TEST("23.2.1-7", forwardIteratorAllocConstruction,
1921 is_destructible, i, j, m) {
1922 auto fi = makeForwardIterator(i);
1923 auto fj = makeForwardIterator(j);
1924 const auto& cfi = fi;
1925 const auto& cfj = fj;
1928 Vector u(cfi, cfj, cm);
1930 ASSERT_TRUE(m == u.get_allocator());
1933 STL_TEST("23.2.1-7", inputIteratorAllocConstruction,
1934 is_move_constructible, i, j, m) {
1935 #ifdef USING_STD_VECTOR
1936 if (Ticker::TicksLeft >= 0) return;
1939 auto ii = makeInputIterator(i);
1940 auto ij = makeInputIterator(j);
1941 const auto& cii = ii;
1942 const auto& cij = ij;
1945 Vector u(cii, cij, cm);
1947 ASSERT_TRUE(m == u.get_allocator());
1950 STL_TEST("23.2.1-7", ilAllocConstruction, is_arithmetic, m) {
1952 if (Ticker::TicksLeft >= 0) return;
1956 Vector u({ 1, 4, 7 }, cm);
1958 ASSERT_TRUE(m == u.get_allocator());
1961 //-----------------------------------------------------------------------------
1964 STL_TEST("23.2.2", dataRaces, is_destructible) {
1966 const Vector* cv = nullptr;
1967 typename Vector::size_type* s = nullptr;
1981 // White-box: check that the non-const versions of each of the above
1982 // functions is implemented in terms of (or the same as) the const version
1985 //-----------------------------------------------------------------------------
1986 // Sequence container
1988 STL_TEST("23.2.3 Table 100.1, alt", nConstruction, is_constructible, n) {
1991 ASSERT_TRUE(Allocator() == u.get_allocator());
1992 ASSERT_EQ(n, u.size());
1993 ASSERT_EQ(Counter::CountTotalOps, Counter::CountDC);
1996 STL_TEST("23.2.3 Table 100.1", nCopyConstruction,
1997 is_copy_constructible, n, t) {
2002 ASSERT_TRUE(Allocator() == u.get_allocator());
2003 ASSERT_EQ(n, u.size()) << "Vector(n, t).size() != n" << endl;
2004 for (const auto& val : u) ASSERT_EQ(convertToInt(t), convertToInt(val))
2005 << "not all elements of Vector(n, t) are equal to t";
2008 STL_TEST("23.2.3 Table 100.2", forwardIteratorConstruction,
2009 is_destructible, i, j) {
2010 // All data is emplace-constructible from int, so we restrict to
2013 auto fi = makeForwardIterator(i);
2014 auto fj = makeForwardIterator(j);
2015 const auto& cfi = fi;
2016 const auto& cfj = fj;
2020 ASSERT_TRUE(Allocator() == u.get_allocator());
2021 ASSERT_LE(Counter::CountTotalOps, j-i);
2023 ASSERT_EQ(j - i, u.size()) << "u(i,j).size() != j-i";
2024 for (auto it = u.begin(); it != u.end(); ++it, ++i)
2025 ASSERT_EQ(*i, convertToInt(*it)) << "u(i,j) constructed incorrectly";
2028 STL_TEST("23.2.3 Table 100.2", inputIteratorConstruction,
2029 is_move_constructible, i, j) {
2030 #ifdef USING_STD_VECTOR
2031 if (Ticker::TicksLeft >= 0) return;
2034 auto ii = makeInputIterator(i);
2035 auto ij = makeInputIterator(j);
2036 const auto& cii = ii;
2037 const auto& cij = ij;
2041 ASSERT_TRUE(Allocator() == u.get_allocator());
2042 ASSERT_EQ(j - i, u.size()) << "u(i,j).size() != j-i";
2043 for (auto it = u.begin(); it != u.end(); ++it, ++i)
2044 ASSERT_EQ(*i, convertToInt(*it)) << "u(i,j) constructed incorrectly";
2047 STL_TEST("23.2.3 Table 100.3", ilConstruction, is_arithmetic) {
2048 // whitebox: ensure that Vector(il) is implemented in terms of
2049 // Vector(il.begin(), il.end())
2052 if (Ticker::TicksLeft >= 0) return;
2054 Vector u = { 1, 4, 7 };
2056 ASSERT_TRUE(Allocator() == u.get_allocator());
2057 ASSERT_EQ(3, u.size()) << "u(il).size() fail";
2059 auto it = u.begin();
2060 for (; it != u.end(); ++it, i += 3)
2061 ASSERT_EQ(i, convertToInt(*it)) << "u(il) constructed incorrectly";
2064 STL_TEST("23.2.3 Table 100.4", ilAssignment,
2066 // whitebox: ensure that assign(il) is implemented in terms of
2067 // assign(il.begin(), il.end())
2070 if (Ticker::TicksLeft >= 0) return;
2072 auto am = a.get_allocator();
2074 Vector& b = a = { 1, 4, 7 };
2076 ASSERT_TRUE(am == a.get_allocator());
2077 ASSERT_TRUE(&b == &a) << "'a = ...' did not return *this";
2079 ASSERT_EQ(3, a.size()) << "u(il).size() fail";
2081 auto it = a.begin();
2082 for (; it != a.end(); ++it, i += 3)
2083 ASSERT_EQ(i, convertToInt(*it)) << "u(il) constructed incorrectly";
2086 //----------------------------
2087 // insert-and-erase subsection
2089 template <class Vector>
2090 void insertNTCheck(const Vector& a, DataState<Vector>& dsa,
2091 int idx, int n, int val) {
2092 ASSERT_EQ(dsa.size() + n, a.size());
2094 for (; i < idx; ++i) {
2095 ASSERT_EQ(dsa[i], convertToInt(a.data()[i])) << i;
2097 for (; i < idx + n; ++i) {
2098 ASSERT_EQ(val, convertToInt(a.data()[i])) << i;
2100 for (; i < a.size(); ++i) {
2101 ASSERT_EQ(dsa[i-n], convertToInt(a.data()[i])) << i;
2105 STL_TEST("23.2.3 Table 100.5", iteratorEmplacement,
2106 is_move_constructibleAndAssignable, a, p) {
2107 DataState<Vector> dsa(a);
2108 int idx = distance(a.begin(), p);
2109 auto am = a.get_allocator();
2111 auto q = a.emplace(p, 44);
2113 ASSERT_TRUE(am == a.get_allocator());
2114 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2115 insertNTCheck(a, dsa, idx, 1, 44);
2118 STL_TEST("23.2.3 Table 100.6", iteratorInsertion,
2119 is_copy_constructibleAndAssignable, a, p, t) {
2120 DataState<Vector> dsa(a);
2121 int idx = distance(a.begin(), p);
2122 int tval = convertToInt(t);
2123 auto am = a.get_allocator();
2126 auto q = a.insert(p, ct);
2128 ASSERT_TRUE(am == a.get_allocator());
2129 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2130 insertNTCheck(a, dsa, idx, 1, tval);
2133 STL_TEST("23.2.3 Table 100.7", iteratorInsertionRV,
2134 is_move_constructibleAndAssignable, a, p, t) {
2135 // rvalue-references cannot have their address checked for aliased inserts
2136 if (a.data() <= addressof(t) && addressof(t) < a.data() + a.size()) return;
2138 DataState<Vector> dsa(a);
2139 int idx = distance(a.begin(), p);
2140 int tval = convertToInt(t);
2141 auto am = a.get_allocator();
2143 auto q = a.insert(p, std::move(t));
2145 ASSERT_TRUE(am == a.get_allocator());
2146 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2147 insertNTCheck(a, dsa, idx, 1, tval);
2150 STL_TEST("23.2.3 Table 100.8", iteratorInsertionN,
2151 is_copy_constructibleAndAssignable, a, p, n, t) {
2152 DataState<Vector> dsa(a);
2153 int idx = distance(a.begin(), p);
2154 int tval = convertToInt(t);
2155 auto am = a.get_allocator();
2158 #ifndef USING_STD_VECTOR
2164 ASSERT_TRUE(am == a.get_allocator());
2165 #ifndef USING_STD_VECTOR
2166 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2169 insertNTCheck(a, dsa, idx, n, tval);
2172 template <class Vector>
2173 void insertItCheck(const Vector& a, DataState<Vector>& dsa,
2174 int idx, int* b, int* e) {
2175 ASSERT_EQ(dsa.size() + (e - b), a.size());
2177 for (; i < idx; ++i) {
2178 ASSERT_EQ(dsa[i], convertToInt(a.data()[i]));
2180 for (; i < idx + (e - b); ++i) {
2181 ASSERT_EQ(*(b + i - idx), convertToInt(a.data()[i]));
2183 for (; i < a.size(); ++i) {
2184 ASSERT_EQ(dsa[i - (e - b)], convertToInt(a.data()[i]));
2188 STL_TEST("23.2.3 Table 100.9", iteratorInsertionIterator,
2189 is_move_constructibleAndAssignable, a, p, i, j) {
2190 DataState<Vector> dsa(a);
2191 int idx = distance(a.begin(), p);
2193 auto fi = makeForwardIterator(i);
2194 auto fj = makeForwardIterator(j);
2195 auto am = a.get_allocator();
2196 const auto& cfi = fi;
2197 const auto& cfj = fj;
2199 #ifndef USING_STD_VECTOR
2203 a.insert(p, cfi, cfj);
2205 ASSERT_TRUE(am == a.get_allocator());
2206 #ifndef USING_STD_VECTOR
2207 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2210 insertItCheck(a, dsa, idx, i, j);
2213 STL_TEST("23.2.3 Table 100.9", iteratorInsertionInputIterator,
2214 is_move_constructibleAndAssignable, a, p, i, j) {
2215 DataState<Vector> dsa(a);
2216 int idx = distance(a.begin(), p);
2218 auto ii = makeInputIterator(i);
2219 auto ij = makeInputIterator(j);
2220 auto am = a.get_allocator();
2221 const auto& cii = ii;
2222 const auto& cij = ij;
2224 #ifndef USING_STD_VECTOR
2228 a.insert(p, cii, cij);
2230 ASSERT_TRUE(am == a.get_allocator());
2231 #ifndef USING_STD_VECTOR
2232 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2235 insertItCheck(a, dsa, idx, i, j);
2238 STL_TEST("23.2.3 Table 100.10", iteratorInsertIL,
2239 is_arithmetic, a, p) {
2241 if (Ticker::TicksLeft >= 0) return;
2243 // whitebox: ensure that insert(p, il) is implemented in terms of
2244 // insert(p, il.begin(), il.end())
2246 DataState<Vector> dsa(a);
2247 int idx = distance(a.begin(), p);
2248 auto am = a.get_allocator();
2250 #ifndef USING_STD_VECTOR
2254 a.insert(p, {1, 4, 7});
2256 ASSERT_TRUE(am == a.get_allocator());
2257 #ifndef USING_STD_VECTOR
2258 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2261 int ila[] = { 1, 4, 7 };
2264 insertItCheck(a, dsa, idx, i, j);
2267 template <class Vector>
2268 void eraseCheck(Vector& a, DataState<Vector>& dsa, int idx, int n) {
2269 ASSERT_EQ(dsa.size() - n, a.size());
2271 auto it = a.begin();
2272 for (; it != a.end(); ++it, ++i) {
2273 if (i == idx) i += n;
2274 ASSERT_EQ(dsa[i], convertToInt(*it));
2278 STL_TEST("23.2.3 Table 100.11", iteratorErase, is_move_assignable, a, p) {
2279 if (p == a.end()) return;
2281 DataState<Vector> dsa(a);
2282 int idx = distance(a.begin(), p);
2283 auto am = a.get_allocator();
2285 auto rit = a.erase(p);
2287 ASSERT_TRUE(am == a.get_allocator());
2288 ASSERT_EQ(idx, distance(a.begin(), rit)) << "wrong iterator returned";
2289 eraseCheck(a, dsa, idx, 1);
2292 STL_TEST("23.2.3 Table 100.12", iteratorEraseRange,
2293 is_move_assignable, a, p, q) {
2294 if (p == a.end()) return;
2296 DataState<Vector> dsa(a);
2297 int idx = distance(a.begin(), p);
2298 auto am = a.get_allocator();
2300 auto rit = a.erase(p, q);
2302 ASSERT_TRUE(am == a.get_allocator());
2303 ASSERT_EQ(idx, distance(a.begin(), rit)) << "wrong iterator returned";
2304 eraseCheck(a, dsa, idx, distance(p,q));
2307 //--------------------------------
2308 // end insert-and-erase subsection
2310 STL_TEST("23.2.3 Table 100.13", clear, is_destructible, a) {
2312 auto am = a.get_allocator();
2317 FAIL() << "clear must be noexcept";
2320 ASSERT_TRUE(am == a.get_allocator());
2321 ASSERT_TRUE(a.empty());
2324 STL_TEST("23.2.3 Table 100.14", assignRange, is_move_assignable, a, i, j) {
2325 auto fi = makeForwardIterator(i);
2326 auto fj = makeForwardIterator(j);
2327 const auto& cfi = fi;
2328 const auto& cfj = fj;
2329 auto am = a.get_allocator();
2333 ASSERT_TRUE(am == a.get_allocator());
2334 ASSERT_EQ(distance(i, j), a.size());
2335 for (auto it = a.begin(); it != a.end(); ++it, ++i)
2336 ASSERT_EQ(*i, convertToInt(*it));
2339 STL_TEST("23.2.3 Table 100.14", assignInputRange,
2340 is_move_constructibleAndAssignable, a, i, j) {
2341 auto ii = makeInputIterator(i);
2342 auto ij = makeInputIterator(j);
2343 const auto& cii = ii;
2344 const auto& cij = ij;
2345 auto am = a.get_allocator();
2349 ASSERT_TRUE(am == a.get_allocator());
2350 ASSERT_EQ(distance(i, j), a.size());
2351 for (auto it = a.begin(); it != a.end(); ++it, ++i)
2352 ASSERT_EQ(*i, convertToInt(*it));
2355 STL_TEST("23.2.3 Table 100.15", assignIL,
2358 // whitebox: ensure that assign(il) is implemented in terms of
2359 // assign(il.begin(), il.end())
2362 if (Ticker::TicksLeft >= 0) return;
2364 auto am = a.get_allocator();
2366 a.assign({1, 4, 7});
2368 ASSERT_TRUE(am == a.get_allocator());
2369 int ila[] = { 1, 4, 7 };
2372 ASSERT_EQ(3, a.size());
2373 for (auto it = a.begin(); it != a.end(); ++it, ++i)
2374 ASSERT_EQ(*i, convertToInt(*it));
2377 STL_TEST("23.2.3 Table 100.16", assignN,
2378 is_copy_constructibleAndAssignable, a, n, t) {
2379 auto am = a.get_allocator();
2381 auto tval = convertToInt(t);
2385 ASSERT_TRUE(am == a.get_allocator());
2386 ASSERT_EQ(n, a.size());
2387 for (auto it = a.begin(); it != a.end(); ++it)
2388 ASSERT_EQ(tval, convertToInt(*it));
2391 STL_TEST("23.2.3 Table 101.1", front, is_destructible, a) {
2392 if (a.empty()) return;
2394 ASSERT_TRUE(addressof(a.front()) == a.data());
2396 ASSERT_EQ(0, Counter::CountTotalOps);
2400 const Vector& ca = a;
2405 STL_TEST("23.2.3 Table 101.2", back, is_destructible, a) {
2406 if (a.empty()) return;
2408 ASSERT_TRUE(addressof(a.back()) == a.data() + a.size() - 1);
2410 ASSERT_EQ(0, Counter::CountTotalOps);
2414 const Vector& ca = a;
2419 STL_TEST("23.2.3 Table 101.4", emplaceBack,
2420 is_move_constructible, a) {
2421 DataState<Vector> dsa(a);
2422 auto adata = a.data();
2423 int excess = a.capacity() - a.size();
2424 auto am = a.get_allocator();
2429 ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2433 ASSERT_TRUE(am == a.get_allocator());
2434 if (excess > 0) ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2435 ASSERT_EQ(dsa.size() + 1, a.size());
2437 auto it = a.begin();
2438 for (; i < dsa.size(); ++i, ++it)
2439 ASSERT_EQ(dsa[i], convertToInt(*it));
2440 ASSERT_EQ(44, convertToInt(a.back()));
2443 STL_TEST("23.2.3 Table 101.7", pushBack, is_copy_constructible, a, t) {
2444 DataState<Vector> dsa(a);
2445 int tval = convertToInt(t);
2446 auto adata = a.data();
2447 int excess = a.capacity() - a.size();
2448 auto am = a.get_allocator();
2454 ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2458 ASSERT_TRUE(am == a.get_allocator());
2459 if (excess > 0) ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2460 ASSERT_EQ(dsa.size() + 1, a.size());
2462 auto it = a.begin();
2463 for (; i < dsa.size(); ++i, ++it)
2464 ASSERT_EQ(dsa[i], convertToInt(*it));
2465 ASSERT_EQ(tval, convertToInt(a.back()));
2468 STL_TEST("23.2.3 Table 101.8", pushBackRV,
2469 is_move_constructible, a, t) {
2470 DataState<Vector> dsa(a);
2471 int tval = convertToInt(t);
2472 auto adata = a.data();
2473 int excess = a.capacity() - a.size();
2474 auto am = a.get_allocator();
2477 a.push_back(move(t));
2479 ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2483 ASSERT_TRUE(am == a.get_allocator());
2484 if (excess > 0) ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2485 ASSERT_EQ(dsa.size() + 1, a.size());
2487 auto it = a.begin();
2488 for (; i < dsa.size(); ++i, ++it)
2489 ASSERT_EQ(dsa[i], convertToInt(*it));
2490 ASSERT_EQ(tval, convertToInt(a.back()));
2493 STL_TEST("23.2.3 Table 100.10", popBack, is_destructible, a) {
2494 if (a.empty()) return;
2496 DataState<Vector> dsa(a);
2497 auto am = a.get_allocator();
2501 ASSERT_TRUE(am == a.get_allocator());
2502 ASSERT_EQ(dsa.size() - 1, a.size());
2504 auto it = a.begin();
2505 for (; it != a.end(); ++it, ++i)
2506 ASSERT_EQ(dsa[i], convertToInt(*it));
2509 STL_TEST("23.2.3 Table 100.11", operatorBrace, is_destructible, a) {
2511 for (int i = 0; i < ca.size(); ++i)
2512 ASSERT_TRUE(addressof(ca[i]) == ca.data()+i);
2514 ASSERT_EQ(0, Counter::CountTotalOps);
2521 STL_TEST("23.2.3 Table 100.12", at, is_destructible, a) {
2523 for (int i = 0; i < ca.size(); ++i)
2524 ASSERT_TRUE(addressof(ca.at(i)) == ca.data()+i);
2526 ASSERT_EQ(0, Counter::CountTotalOps);
2530 FAIL() << "at(size) should have thrown an error";
2531 } catch (const std::out_of_range& e) {
2533 FAIL() << "at(size) threw error other than out_of_range";
2541 STL_TEST("move iterators", moveIterators, is_copy_constructibleAndAssignable) {
2546 auto mfi = make_move_iterator(makeForwardIterator(i));
2547 auto mfj = make_move_iterator(makeForwardIterator(j));
2548 auto mii = make_move_iterator(makeInputIterator(i));
2549 auto mij = make_move_iterator(makeInputIterator(j));
2551 Vector u1(mfi, mfj);
2552 Vector u2(mii, mij);
2554 u1.insert(u1.begin(), mfi, mfj);
2555 u1.insert(u1.begin(), mii, mij);
2557 u1.assign(mfi, mfj);
2558 u1.assign(mii, mij);
2562 //-----------------------------------------------------------------------------
2565 STL_TEST("23.3.6.4", dataAndCapacity, is_destructible) {
2566 // there isn't anything new to test here - data and capacity are used as the
2567 // backbone of DataState. The minimal testing we might want to do is already
2568 // done in the populate test
2571 STL_TEST("23.3.6.3", reserve, is_move_constructible, a, n) {
2572 auto adata = a.data();
2573 auto ocap = a.capacity();
2574 auto am = a.get_allocator();
2578 ASSERT_TRUE(am == a.get_allocator());
2580 ASSERT_EQ(0, Counter::CountTotalOps);
2581 ASSERT_TRUE(adata == a.data());
2583 ASSERT_TRUE(a.capacity() >= n);
2584 ASSERT_LE(Counter::CountTotalOps, 2*a.size()); // move and delete
2588 STL_TEST("23.3.6.3", lengthError, is_move_constructible) {
2589 auto mx = Vector().max_size();
2591 if (mx >= big) return; // max_size is the biggest size_type; overflowed
2596 FAIL() << "reserve(big) should have thrown an error";
2597 } catch (const std::length_error& e) {
2599 FAIL() << "reserve(big) threw error other than length_error";
2603 STL_TEST("23.3.6.3", resize, is_copy_constructible, a, n) {
2604 DataState<Vector> dsa(a);
2606 auto am = a.get_allocator();
2610 ASSERT_TRUE(am == a.get_allocator());
2611 ASSERT_EQ(n, a.size());
2614 for (int i = 0; i < n; ++i) {
2615 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2618 for (int i = 0; i < sz; ++i) {
2619 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2624 STL_TEST("23.3.6.3", resizeT, is_copy_constructibleAndAssignable, a, n, t) {
2625 #ifdef USING_STD_VECTOR
2626 if (a.data() <= addressof(t) && addressof(t) < a.data() + a.size()) return;
2629 DataState<Vector> dsa(a);
2631 auto am = a.get_allocator();
2633 int val = convertToInt(t);
2637 ASSERT_TRUE(am == a.get_allocator());
2638 ASSERT_EQ(n, a.size());
2641 for (int i = 0; i < n; ++i) {
2642 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2646 for ( ; i < sz; ++i) {
2647 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2649 for ( ; i < n; ++i) {
2650 ASSERT_EQ(val, convertToInt(a[i]));
2655 STL_TEST("23.3.6.3", shrinkToFit, is_move_constructible, a) {
2656 bool willThrow = Ticker::TicksLeft >= 0;
2658 a.reserve(a.capacity() * 11);
2660 auto ocap = a.capacity();
2661 DataState<Vector> dsa(a);
2663 auto am = a.get_allocator();
2668 FAIL() << "shrink_to_fit should swallow errors";
2671 ASSERT_TRUE(am == a.get_allocator());
2672 ASSERT_TRUE(dsa == a);
2674 //ASSERT_EQ(ocap, a.capacity()); might shrink in place
2675 throw TickException("I swallowed the error");
2677 ASSERT_TRUE(a.capacity() == 0 || a.capacity() < ocap) << "Look into this";
2681 #ifndef USING_STD_VECTOR
2682 STL_TEST("EBO", ebo, is_destructible) {
2683 static_assert(!is_same<Allocator, std::allocator<T>>::value ||
2684 sizeof(Vector) == 3 * sizeof(void*),
2685 "fbvector has default allocator, but has size != 3*sizeof(void*)");
2688 STL_TEST("relinquish", relinquish, is_destructible, a) {
2690 auto cap = a.capacity();
2691 auto data = a.data();
2693 auto guts = relinquish(a);
2695 ASSERT_EQ(data, guts);
2696 ASSERT_TRUE(a.empty());
2697 ASSERT_EQ(0, a.capacity());
2699 auto alloc = a.get_allocator();
2700 for (size_t i = 0; i < sz; ++i)
2701 std::allocator_traits<decltype(alloc)>::destroy(alloc, guts + i);
2702 if (guts != nullptr)
2703 std::allocator_traits<decltype(alloc)>::deallocate(alloc, guts, cap);
2706 STL_TEST("attach", attach, is_destructible, a) {
2707 DataState<Vector> dsa(a);
2710 auto cap = a.capacity();
2711 auto guts = relinquish(a);
2713 ASSERT_EQ(a.data(), nullptr);
2714 attach(a, guts, sz, cap);
2716 ASSERT_TRUE(dsa == a);
2723 int main(int argc, char** argv) {
2724 testing::InitGoogleTest(&argc, argv);
2725 gflags::ParseCommandLineFlags(&argc, &argv, true);
2727 return RUN_ALL_TESTS();
2730 #else // GCC 4.7 guard
2733 TEST(placeholder, gccversion) {}
2735 int main(int argc, char** argv) {
2736 testing::InitGoogleTest(&argc, argv);
2737 gflags::ParseCommandLineFlags(&argc, &argv, true);
2739 return RUN_ALL_TESTS();
2742 #endif // GCC 4.7 guard