2 * Copyright 2014 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 #define FOLLY_BENCHMARK_USE_NS_IFOLLY
169 #include "folly/FBVector.h"
170 #define VECTOR_ Ifolly::fbvector
173 //#define USING_STD_VECTOR
178 #include <type_traits>
188 #include "folly/ScopeGuard.h"
189 #include "folly/Conv.h"
190 #include <boost/preprocessor.hpp>
191 #include <boost/iterator/iterator_adaptor.hpp>
192 #include <gflags/gflags.h>
193 #include <gtest/gtest.h>
196 using namespace folly;
198 using namespace Ifolly;
200 //=============================================================================
201 //=============================================================================
204 //-----------------------------------------------------------------------------
207 typedef uint32_t Flags;
209 // each method has 3 options: normal, noexcept, throw, and deleted
210 // normal is the default
211 // throw is mutually exclusive with noexcept
213 // DC - default constructor
214 // CC - copy constructor
215 // MC - move constructor
216 // OC - other constructor
217 // CA - copy assignment
218 // MA - move assignment
219 enum FlagVals : Flags {
240 ALL_DELETE = DC_DELETE | CC_DELETE | MC_DELETE
241 | CA_DELETE | MA_DELETE,
247 PROP_COPY = 0x100000,
248 PROP_MOVE = 0x200000,
249 PROP_SWAP = 0x400000,
252 //-----------------------------------------------------------------------------
255 template <bool b> struct D0 {
257 D0(const D0&) = default;
259 explicit D0(std::nullptr_t) {}
260 D0& operator=(const D0&) = default;
261 D0& operator=(D0&&) = default;
263 template <> struct D0<true> {
265 D0(const D0&) = default;
267 explicit D0(std::nullptr_t) {}
268 D0& operator=(const D0&) = default;
269 D0& operator=(D0&&) = default;
272 template <bool b> struct D1 {
274 D1(const D1&) = default;
276 explicit D1(std::nullptr_t) {}
277 D1& operator=(const D1&) = default;
278 D1& operator=(D1&&) = default;
280 template <> struct D1<true> {
282 D1(const D1&) = delete;
284 explicit D1(std::nullptr_t) {}
285 D1& operator=(const D1&) = default;
286 D1& operator=(D1&&) = default;
289 template <bool b> struct D2 {
291 D2(const D2&) = default;
293 explicit D2(std::nullptr_t) {}
294 D2& operator=(const D2&) = default;
295 D2& operator=(D2&&) = default;
297 template <> struct D2<true> {
299 D2(const D2&) = default;
301 explicit D2(std::nullptr_t) {}
302 D2& operator=(const D2&) = default;
303 D2& operator=(D2&&) = default;
306 template <bool b> struct D3 {
308 D3(const D3&) = default;
310 explicit D3(std::nullptr_t) {}
311 D3& operator=(const D3&) = default;
312 D3& operator=(D3&&) = default;
314 template <> struct D3<true> {
316 D3(const D3&) = default;
318 explicit D3(std::nullptr_t) {}
319 D3& operator=(const D3&) = delete;
320 D3& operator=(D3&&) = default;
323 template <bool b> struct D4 {
325 D4(const D4&) = default;
327 explicit D4(std::nullptr_t) {}
328 D4& operator=(const D4&) = default;
329 D4& operator=(D4&&) = default;
331 template <> struct D4<true> {
333 D4(const D4&) = default;
335 explicit D4(std::nullptr_t) {}
336 D4& operator=(const D4&) = default;
337 D4& operator=(D4&&) = delete;
341 struct Delete : D0<f & DC_DELETE>
345 , D4<f & MA_DELETE> {
347 Delete(const Delete&) = default;
348 Delete(Delete&&) = default;
349 Delete& operator=(const Delete&) = default;
350 Delete& operator=(Delete&&) = default;
352 explicit Delete(std::nullptr_t)
353 : D0<f & DC_DELETE>(nullptr)
354 , D1<f & CC_DELETE>(nullptr)
355 , D2<f & MC_DELETE>(nullptr)
356 , D3<f & CA_DELETE>(nullptr)
357 , D4<f & MA_DELETE>(nullptr)
361 //-----------------------------------------------------------------------------
364 struct TickException : std::runtime_error {
365 explicit TickException(const std::string& s)
366 : std::runtime_error("tick: " + s) {}
370 static int CountTicks;
371 static int TicksLeft;
372 static void Tick(const std::string& s) {
373 if (TicksLeft == 0) throw TickException(s);
379 int Ticker::CountTicks = 0;
380 int Ticker::TicksLeft = -1;
383 struct DataTicker : Ticker {
384 DataTicker() noexcept(f & DC_NOEXCEPT) {
385 if (!(f & DC_NOEXCEPT)) Tick("Data()");
387 DataTicker(const DataTicker&) noexcept(f & CC_NOEXCEPT) {
388 if (!(f & CC_NOEXCEPT)) Tick("Data(const Data&)");
390 DataTicker(DataTicker&&) noexcept(f & MC_NOEXCEPT) {
391 if (!(f & MC_NOEXCEPT)) Tick("Data(Data&&)");
393 explicit DataTicker(std::nullptr_t) noexcept(f & OC_NOEXCEPT) {
394 if (!(f & OC_NOEXCEPT)) Tick("Data(int)");
396 ~DataTicker() noexcept {}
397 void operator=(const DataTicker&) noexcept(f & CA_NOEXCEPT) {
398 if (!(f & CA_NOEXCEPT)) Tick("op=(const Data&)");
400 void operator=(DataTicker&&) noexcept(f & MA_NOEXCEPT) {
401 if (!(f & MA_NOEXCEPT)) Tick("op=(Data&&)");
405 //-----------------------------------------------------------------------------
409 static int CountDC, CountCC, CountMC, CountOC, CountCA, CountMA;
410 static int CountDestroy, CountTotalOps, CountLoggedConstruction;
412 Counter() noexcept { CountTotalOps++; CountDC++; }
413 Counter(const Counter&) noexcept { CountTotalOps++; CountCC++; }
414 Counter(Counter&&) noexcept { CountTotalOps++; CountMC++; }
415 explicit Counter(std::nullptr_t) noexcept { CountTotalOps++; CountOC++; }
416 void operator=(const Counter&) noexcept { CountTotalOps++; CountCA++; }
417 void operator=(Counter&&) noexcept { CountTotalOps++; CountMA++; }
418 ~Counter() noexcept { CountTotalOps++; CountDestroy++; }
421 int Counter::CountDC = 0;
422 int Counter::CountCC = 0;
423 int Counter::CountMC = 0;
424 int Counter::CountOC = 0;
425 int Counter::CountCA = 0;
426 int Counter::CountMA = 0;
427 int Counter::CountDestroy = 0;
428 int Counter::CountTotalOps = 0;
429 int Counter::CountLoggedConstruction = 0;
431 //-----------------------------------------------------------------------------
436 static std::map<int, int> UIDCount;
438 static std::map<const Tracker*, int> Locations;
444 Tracker(Tracker* self, int uid) : self(self), uid(uid) {}
447 template <bool isRelocatable>
448 struct DataTracker : Tracker {
449 DataTracker() noexcept : Tracker(this, UID++) {
452 if (!isRelocatable) Locations[self] = uid;
455 DataTracker(const DataTracker& o) noexcept : Tracker(this, o.uid) {
458 if (!isRelocatable) Locations[self] = uid;
459 print("Data(const Data&)");
461 DataTracker(DataTracker&& o) noexcept : Tracker(this, o.uid) {
464 if (!isRelocatable) Locations[self] = uid;
465 print("Data(Data&&)");
468 explicit DataTracker(int uid) noexcept : Tracker(this, uid) {
471 if (!isRelocatable) Locations[self] = uid;
475 ~DataTracker() noexcept {
478 if (!isRelocatable) Locations.erase(self);
481 self = (DataTracker*)0xfeebdaed;
484 DataTracker& operator=(const DataTracker& o) noexcept {
488 if (!isRelocatable) Locations[self] = uid;
489 print("op=(const Data&)");
492 DataTracker& operator=(DataTracker&& o) noexcept {
496 if (!isRelocatable) Locations[self] = uid;
497 print("op=(Data&&)");
501 void print(const std::string& fun) {
503 std::cerr << std::setw(20) << fun << ": uid = " << std::setw(3) << uid;
504 if (!isRelocatable) std::cerr << ", self = " << self;
505 std::cerr << std::endl;
510 int Tracker::UID = 1234;
511 std::map<int, int> Tracker::UIDCount;
512 int Tracker::UIDTotal = 0;
513 std::map<const Tracker*, int> Tracker::Locations;
514 bool Tracker::Print = false;
516 //-----------------------------------------------------------------------------
517 //-----------------------------------------------------------------------------
520 template <Flags f = 0, size_t pad = 0>
521 struct Data : DataTracker<f & IS_RELOCATABLE>,
522 Counter, DataTicker<f>, Delete<f> {
523 static const Flags flags = f;
524 char spacehog[pad ? pad : 1];
527 Data(const Data&) = default;
528 Data(Data&&) = default;
529 /* implicit */ Data(int i)
530 : DataTracker<f & IS_RELOCATABLE>(i), Counter()
531 , DataTicker<f>(nullptr)
535 Data& operator=(const Data&) = default;
536 Data& operator=(Data&&) = default;
539 int operator&() const;
543 template <Flags f, size_t pad>
544 struct IsRelocatable<Data<f, pad>>
545 : std::integral_constant<bool,
550 //-----------------------------------------------------------------------------
551 //-----------------------------------------------------------------------------
554 template <typename T>
555 struct isPropCopy : true_type {};
556 template <Flags f, size_t pad>
557 struct isPropCopy<Data<f, pad>> :
558 std::integral_constant<bool, f & PROP_COPY> {};
560 template <typename T>
561 struct isPropMove : true_type {};
562 template <Flags f, size_t pad>
563 struct isPropMove<Data<f, pad>> :
564 std::integral_constant<bool, f & PROP_MOVE> {};
566 template <typename T>
567 struct isPropSwap : true_type {};
568 template <Flags f, size_t pad>
569 struct isPropSwap<Data<f, pad>> :
570 std::integral_constant<bool, f & PROP_SWAP> {};
573 struct AllocTracker {
574 static int Constructed;
575 static int Destroyed;
576 static map<void*, size_t> Allocated;
577 static map<void*, int> Owner;
579 int AllocTracker::Constructed = 0;
580 int AllocTracker::Destroyed = 0;
581 map<void*, size_t> AllocTracker::Allocated;
582 map<void*, int> AllocTracker::Owner;
585 struct Alloc : AllocTracker, Ticker {
586 typedef typename std::allocator<T>::pointer pointer;
587 typedef typename std::allocator<T>::const_pointer const_pointer;
588 typedef typename std::allocator<T>::size_type size_type;
589 typedef typename std::allocator<T>::value_type value_type;
596 explicit Alloc(int i = 8) : a(a), id(i) {}
597 Alloc(const Alloc& o) : a(o.a), id(o.id) {}
598 Alloc(Alloc&& o) : a(move(o.a)), id(o.id) {}
599 Alloc& operator=(const Alloc&) = default;
600 Alloc& operator=(Alloc&&) = default;
601 bool operator==(const Alloc& o) const { return a == o.a && id == o.id; }
602 bool operator!=(const Alloc& o) const { return !(*this == o); }
607 pointer allocate(size_type n) {
609 cerr << "called allocate(0)" << endl;
610 throw runtime_error("allocate fail");
613 auto p = a.allocate(n);
619 void deallocate(pointer p, size_type n) {
621 cerr << "deallocate(nullptr, " << n << ")" << endl;
622 FAIL() << "deallocate failed";
624 if (Allocated[p] != n) {
625 cerr << "deallocate(" << p << ", " << n << ") invalid: ";
626 if (Allocated[p] == 0) cerr << "never allocated";
627 else if (Allocated[p] == -1) cerr << "already deallocated";
628 else cerr << "wrong number (want " << Allocated[p] << ")";
630 FAIL() << "deallocate failed";
632 if (Owner[p] != id) {
633 cerr << "deallocate(" << p << "), where pointer is owned by "
634 << Owner[p] << ", instead of self - " << id << endl;
635 FAIL() << "deallocate failed";
641 template <class U, class... Args>
642 void construct(U* p, Args&&... args) {
644 a.construct(p, std::forward<Args>(args)...);
657 Alloc select_on_container_copy_construction() const {
658 Tick("select allocator for copy");
659 return Alloc(id + 1);
662 typedef isPropCopy<T> propagate_on_container_copy_assignment;
663 typedef isPropMove<T> propagate_on_container_move_assignment;
664 typedef isPropSwap<T> propagate_on_container_swap;
667 //=============================================================================
668 //=============================================================================
669 // Verification and resetting
671 void softReset(int ticks = -1) {
672 Counter::CountLoggedConstruction +=
673 Counter::CountDC + Counter::CountCC + Counter::CountMC
674 + Counter::CountOC - Counter::CountDestroy;
675 Counter::CountDC = Counter::CountCC = Counter::CountMC
676 = Counter::CountOC = Counter::CountCA = Counter::CountMA = 0;
677 Counter::CountDestroy = Counter::CountTotalOps = 0;
678 Ticker::CountTicks = 0;
679 Ticker::TicksLeft = ticks;
683 Tracker::UIDCount.clear();
684 Tracker::UIDTotal = 0;
685 Tracker::Locations.clear();
687 Counter::CountLoggedConstruction = 0;
689 AllocTracker::Constructed = 0;
690 AllocTracker::Destroyed = 0;
691 AllocTracker::Allocated.clear();
692 AllocTracker::Owner.clear();
696 int con = Counter::CountDC + Counter::CountCC
697 + Counter::CountMC + Counter::CountOC
698 + Counter::CountLoggedConstruction;
699 int del = Counter::CountDestroy;
704 int tot = getTotal();
705 ASSERT_GE(tot, 0) << "more objects deleted than constructed";
707 ASSERT_EQ(tot, Tracker::UIDTotal)
708 << "UIDTotal has incorrect number of objects";
711 for (const auto& kv : Tracker::UIDCount) {
712 ASSERT_TRUE(kv.second >= 0) << "there exists " << kv.second << " Data "
713 "with uid " << kv.first;
716 ASSERT_EQ(tot, altTot) << "UIDCount corrupted";
718 if (!Tracker::Locations.empty()) { // implied by IsRelocatable
719 ASSERT_EQ(tot, Tracker::Locations.size())
720 << "Locations has incorrect number of objects";
721 for (const auto& du : Tracker::Locations) {
722 ASSERT_EQ(du.second, du.first->uid) << "Locations contains wrong uid";
723 ASSERT_EQ(du.first, du.first->self) << "Data.self is corrupted";
728 //-----------------------------------------------------------------------------
731 template <typename T>
732 struct is_copy_constructibleAndAssignable
733 : std::integral_constant<bool,
734 std::is_copy_constructible<T>::value &&
735 std::is_copy_assignable<T>::value
738 template <typename T>
739 struct is_move_constructibleAndAssignable
740 : std::integral_constant<bool,
741 std::is_move_constructible<T>::value &&
742 std::is_move_assignable<T>::value
745 template <class Vector>
746 struct customAllocator
747 : std::integral_constant<bool,
749 typename Vector::allocator_type,
750 std::allocator<typename Vector::value_type>
754 template <typename T>
755 struct special_move_assignable
756 : is_move_constructibleAndAssignable<T> {};
757 template <Flags f, size_t pad>
758 struct special_move_assignable<Data<f, pad>>
759 : std::integral_constant<bool,
760 is_move_constructibleAndAssignable<Data<f, pad>>::value ||
764 //=============================================================================
765 //=============================================================================
768 //-----------------------------------------------------------------------------
772 unsigned reslo, reshi;
774 __asm__ __volatile__ (
775 "xorl %%eax,%%eax \n cpuid \n"
776 ::: "%eax", "%ebx", "%ecx", "%edx");
777 __asm__ __volatile__ (
779 : "=a" (reslo), "=d" (reshi) );
780 __asm__ __volatile__ (
781 "xorl %%eax,%%eax \n cpuid \n"
782 ::: "%eax", "%ebx", "%ecx", "%edx");
784 return ((uint64_t)reshi << 32) | reslo;
787 //-----------------------------------------------------------------------------
790 #define IBOOST_PP_VARIADIC_SIZE(...) IBOOST_PP_VARIADIC_SIZE_I(__VA_ARGS__, \
791 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, \
792 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, \
793 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, \
794 7, 6, 5, 4, 3, 2, 1,)
795 #define IBOOST_PP_VARIADIC_SIZE_I(e0, e1, e2, e3, e4, e5, e6, e7, e8, e9, \
796 e10, e11, e12, e13, e14, e15, e16, e17, e18, e19, e20, e21, e22, e23, e24, \
797 e25, e26, e27, e28, e29, e30, e31, e32, e33, e34, e35, e36, e37, e38, e39, \
798 e40, e41, e42, e43, e44, e45, e46, e47, e48, e49, e50, e51, e52, e53, e54, \
799 e55, e56, e57, e58, e59, e60, e61, e62, e63, size, ...) size
800 #define IBOOST_PP_VARIADIC_TO_SEQ(args...) \
801 BOOST_PP_TUPLE_TO_SEQ(IBOOST_PP_VARIADIC_SIZE(args), (args))
803 //-----------------------------------------------------------------------------
806 #define GEN_TEST(r, name, type) \
808 string atype = PrettyType<typename type::allocator_type>()(); \
809 string ptype = PrettyType<typename type::value_type>()(); \
810 SCOPED_TRACE("allocator: " + atype); { \
811 SCOPED_TRACE("datatype: " + ptype); { \
812 test_ ## name ## 3 <type> (); \
813 if (::testing::Test::HasFatalFailure()) return; \
815 #define GEN_TYPE_TEST(r, name, type) \
816 if (0) test_I_ ## name ## 3 <type> ();
817 #define GEN_RUNNABLE_TEST(r, name, type) \
818 one = test_I_ ## name ## 3 <type> () || one;
820 #define GEN_LOOPER(r, d, arg) BOOST_PP_CAT(LOOPER_, arg)
821 #define GEN_VMAKER(r, d, arg) { BOOST_PP_CAT(VMAKER_, arg) {
822 #define GEN_UMAKER(r, d, arg) } BOOST_PP_CAT(UMAKER_, arg) }
823 #define GEN_CLOSER(r, d, arg) BOOST_PP_CAT(CLOSER_, arg)
825 #define TYPIFY(r, d, name) BOOST_PP_CAT(TYPIFY_, name)
826 #define ARGIFY(r, d, name) TYPIFY(r, d, name) name
828 #define MAKE_TEST(ref, name, types, restriction, argseq, rawargs...) \
829 template <class Vector> void test_ ## name ## 2 (std::false_type) {} \
830 template <class Vector> void test_ ## name ## 2 (std::true_type) { \
831 BOOST_PP_SEQ_FOR_EACH(GEN_LOOPER, _, argseq) \
833 BOOST_PP_SEQ_FOR_EACH(GEN_VMAKER, _, argseq) \
835 test_ ## name <Vector, typename Vector::value_type, \
836 typename Vector::allocator_type> ( rawargs ); \
837 if (::testing::Test::HasFatalFailure()) return; \
839 BOOST_PP_SEQ_FOR_EACH(GEN_UMAKER, _, BOOST_PP_SEQ_REVERSE(argseq)) \
841 BOOST_PP_SEQ_FOR_EACH(GEN_CLOSER, _, BOOST_PP_SEQ_REVERSE(argseq)) \
843 template <class Vector> void test_ ## name ## 3 () { \
844 test_ ## name ## 2 <Vector> (std::integral_constant<bool, \
845 restriction<typename Vector::value_type>::value && \
846 is_copy_constructible<typename Vector::value_type>::value \
850 template <class Vector> bool test_I_ ## name ## 2 (std::false_type) \
852 template <class Vector> bool test_I_ ## name ## 2 (std::true_type) { \
854 auto f = test_ ## name <Vector, \
855 typename Vector::value_type, typename Vector::allocator_type>; \
858 template <class Vector> bool test_I_ ## name ## 3 () { \
859 return test_I_ ## name ## 2 <Vector> (std::integral_constant<bool, \
860 restriction<typename Vector::value_type>::value>()); \
864 TEST(FBVector, name) { \
865 SCOPED_TRACE("N3337 reference: " ref); \
866 BOOST_PP_SEQ_FOR_EACH(GEN_TEST, name, types) \
867 BOOST_PP_SEQ_FOR_EACH(GEN_TYPE_TEST, name, INTERFACE_TYPES) \
869 BOOST_PP_SEQ_FOR_EACH(GEN_RUNNABLE_TEST, name, types) \
870 if (!one) FAIL() << "No tests qualified to run"; \
873 #define DECL(name, args...) \
874 template <class Vector, typename T, typename Allocator> \
875 void test_ ## name (BOOST_PP_SEQ_ENUM(BOOST_PP_SEQ_TRANSFORM( \
876 ARGIFY, _, IBOOST_PP_VARIADIC_TO_SEQ(args))))
878 #define STL_TEST_I(ref, name, restriction, args...) \
880 MAKE_TEST(ref, name, TEST_TYPES, restriction, \
881 IBOOST_PP_VARIADIC_TO_SEQ(args), args) \
884 #define STL_TEST(ref, name, restriction, args...) \
885 STL_TEST_I(ref, name, restriction, z, ## args, ticks)
887 //-----------------------------------------------------------------------------
891 typedef Data<0, 4080> ED2;
892 typedef Data<MC_NOEXCEPT> ED3;
893 typedef Data<MC_NOEXCEPT | CC_DELETE> ED4;
894 typedef Data<IS_RELOCATABLE> ED5;
896 typedef VECTOR_<int, std::allocator<int>> _TVIS;
897 typedef VECTOR_<int, Alloc<int>> _TVI;
898 typedef VECTOR_<ED1, std::allocator<ED1>> _TV1;
899 typedef VECTOR_<ED2, std::allocator<ED2>> _TV2;
900 typedef VECTOR_<ED3, std::allocator<ED3>> _TV3;
901 typedef VECTOR_<ED4, std::allocator<ED4>> _TV4;
902 typedef VECTOR_<ED5, std::allocator<ED5>> _TV5v1;
903 typedef VECTOR_<ED5, Alloc<ED5>> _TV5;
905 typedef Data<PROP_COPY> EP1;
906 typedef Data<PROP_MOVE> EP2;
907 typedef Data<PROP_SWAP> EP3;
909 typedef VECTOR_<EP1, Alloc<EP1>> _TP1;
910 typedef VECTOR_<EP2, Alloc<EP2>> _TP2;
911 typedef VECTOR_<EP3, Alloc<EP3>> _TP3;
913 #define TEST_TYPES (_TVIS)(_TVI)(_TV1)(_TV2)(_TV3)(_TV4)(_TV5v1)(_TV5) \
916 typedef Data<ALL_DELETE> DD1; // unoperable
917 typedef Data<DC_DELETE | CC_DELETE | MC_DELETE> DD2; // unconstructible
918 typedef Data<CA_DELETE | MA_DELETE> DD3; // unassignable
919 typedef Data<CC_DELETE | MC_DELETE> DD4; // uncopyable
920 typedef Data<ALL_DELETE & ~DC_DELETE> DD5; // only default constructible
921 typedef Data<CC_DELETE> DD6; // move-only copy construction
922 typedef Data<CA_DELETE> DD7; // move-only assignment
924 typedef Data<ALL_DELETE | PROP_MOVE> DDSMA;
925 typedef VECTOR_<DDSMA, Alloc<DDSMA>> _TSpecialMA;
927 #define INTERFACE_TYPES \
928 (_TVI)(VECTOR_<DD1>)(VECTOR_<DD2>)(VECTOR_<DD3>) \
929 (VECTOR_<DD4>)(VECTOR_<DD5>)(VECTOR_<DD6>) \
930 (VECTOR_<DD7>)(_TSpecialMA)
932 //-----------------------------------------------------------------------------
935 template <typename T>
937 string operator()() {
938 if (is_same<T, int>::value) return "int";
939 if (is_same<T, char>::value) return "char";
940 if (is_same<T, uint64_t>::value) return "uint64_t";
941 return typeid(T).name();
945 template <Flags f, size_t pad>
946 struct PrettyType<Data<f, pad>> {
947 string operator()() {
951 if ((f & DC_DELETE) ||
957 if (f & DC_DELETE) tpe << " DC,";
958 if (f & CC_DELETE) tpe << " CC,";
959 if (f & MC_DELETE) tpe << " MC,";
960 if (f & CA_DELETE) tpe << " CA,";
961 if (f & MA_DELETE) tpe << " MA,";
965 if ((f & DC_NOEXCEPT) ||
971 if (f & DC_NOEXCEPT) tpe << " DC,";
972 if (f & CC_NOEXCEPT) tpe << " CC,";
973 if (f & MC_NOEXCEPT) tpe << " MC,";
974 if (f & CA_NOEXCEPT) tpe << " CA,";
975 if (f & MA_NOEXCEPT) tpe << " MA,";
979 if (f & IS_RELOCATABLE) {
980 tpe << "(relocatable)";
984 tpe << "{pad " << pad << "}";
991 template <typename T>
992 struct PrettyType<std::allocator<T>> {
993 string operator()() {
994 return "std::allocator<" + PrettyType<T>()() + ">";
998 template <typename T>
999 struct PrettyType<Alloc<T>> {
1000 string operator()() {
1001 return "Alloc<" + PrettyType<T>()() + ">";
1005 //-----------------------------------------------------------------------------
1006 // Setup, teardown, runup, rundown
1008 // These four macros are run once per test. Setup and runup occur before the
1009 // test, teardown and rundown after. Setup and runup straddle the
1010 // initialization sequence, whereas rundown and teardown straddle the
1013 #define SETUP hardReset();
1016 //-----------------------------------------------------------------------------
1017 // Types and typegens
1022 #define TYPIFY_z std::nullptr_t
1024 Vector* a_p = nullptr; Vector* b_p = nullptr; \
1025 typename Vector::value_type* t_p = nullptr;
1026 #define VMAKER_z std::nullptr_t z = nullptr;
1028 verify<Vector>(0); \
1029 if (::testing::Test::HasFatalFailure()) return;
1035 #define VERIFICATION \
1036 if (b_p != nullptr) verify(t_p != nullptr ,*a_p, *b_p); \
1037 else if (a_p != nullptr) verify(t_p != nullptr, *a_p); \
1038 else verify<Vector>(t_p != nullptr); \
1039 if (::testing::Test::HasFatalFailure()) return;
1041 #define TYPIFY_ticks int
1042 #define LOOPER_ticks \
1043 int _maxTicks_ = 0; \
1044 bool ticks_thrown = false; \
1045 for (int ticks = -1; ticks < _maxTicks_; ++ticks) {
1046 #define VMAKER_ticks \
1047 string ticks_st = folly::to<string>("ticks = ", ticks); \
1048 SCOPED_TRACE(ticks_st); \
1049 { SCOPED_TRACE("pre-run verification"); \
1053 #define UMAKER_ticks _maxTicks_ = Ticker::CountTicks; } \
1054 catch (const TickException&) { ticks_thrown = true; } \
1055 catch (const std::exception& e) \
1056 { FAIL() << "EXCEPTION: " << e.what(); } \
1058 { FAIL() << "UNKNOWN EXCEPTION"; } \
1059 if (ticks >= 0 && Ticker::CountTicks > ticks && !ticks_thrown) \
1060 FAIL() << "CountTicks = " << Ticker::CountTicks << " > " \
1061 << ticks << " = ticks" \
1062 << ", but no tick error was observed"; \
1064 #define CLOSER_ticks }
1067 //--------------------------------------------------
1068 // vectors (second could be .equal, ==, or distinct)
1070 static const vector<pair<int, int>> VectorSizes = {
1074 { 10, -1}, { 10, 1}, { 10, 0},
1075 {100, -1}, {100, 1},
1077 //{ 10, -1}, { 10, 0}, { 10, 1}, { 10, 2}, { 10, 10},
1078 //{ 100, -1}, { 100, 0}, { 100, 1}, { 100, 2}, { 100, 10}, { 100, 100},
1079 //{ 1000, -1}, { 1000, 0}, { 1000, 1}, { 1000, 2}, { 1000, 10}, { 1000, 100},
1083 int populateIndex = 1426;
1084 template <class Vector>
1085 void populate(Vector& v, const pair<int, int>& ss) {
1087 for (; i < ss.first; ++i) {
1088 v.emplace_back(populateIndex++);
1090 if (ss.second >= 0) {
1091 while (v.capacity() - v.size() != ss.second) {
1092 v.emplace_back(populateIndex++);
1097 template <typename A>
1099 static A get() { return A(); }
1101 template <typename T>
1102 struct allocGen<Alloc<T>> {
1103 static Alloc<T> get() {
1110 #define TYPIFY_a Vector&
1111 #define LOOPER_a for (const auto& a_ss : VectorSizes) {
1113 Vector a(allocGen<typename Vector::allocator_type>::get()); \
1115 populate(*a_p, a_ss); \
1116 string a_st = folly::to<string>("a (", a.size(), "/", a.capacity(), ")"); \
1118 #define UMAKER_a verify(0, a); if (::testing::Test::HasFatalFailure()) return;
1121 #define TYPIFY_b Vector&
1122 #define LOOPER_b for (int b_i = -2; b_i < (int)VectorSizes.size(); ++b_i) {
1124 Vector b_s(allocGen<typename Vector::allocator_type>::get()); \
1125 b_p = &b_s; string b_st; \
1128 b_st = "b is an alias of a"; \
1130 else if (b_i == -1) { \
1132 new (&b_s) Vector(a); \
1133 b_st = "b is a deep copy of a"; \
1136 populate(b_s, VectorSizes[b_i]); \
1137 b_st = folly::to<string>("b (", b_s.size(), "/", b_s.capacity(), ")"); \
1142 verify(0, a, b); if (::testing::Test::HasFatalFailure()) return;
1148 static const vector<int> nSizes = { 0, 1, 2, 9, 10, 11 };
1150 #define TYPIFY_n int
1151 #define LOOPER_n for (int n : nSizes) {
1153 string n_st = folly::to<string>("n = ", n); SCOPED_TRACE(n_st);
1157 //-----------------------
1158 // non-internal iterators
1160 static int ijarr[12] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
1161 static int ijarC[12] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
1163 #define TYPIFY_i int*
1165 #define VMAKER_i int* i = ijarr; SCOPED_TRACE("i = fib[0]");
1169 #define TYPIFY_j int*
1170 #define LOOPER_j for (int j_i = 0; j_i < 12; ++j_i) {
1172 int* j = ijarr + j_i; \
1173 string j_st = folly::to<string>("j = fib[", j_i, "]"); \
1176 for (int j_c = 0; j_c < 12; ++j_c) ASSERT_EQ(ijarC[j_c], ijarr[j_c]);
1179 //-------------------
1180 // internal iterators
1182 template <class Vector>
1183 std::pair<typename Vector::iterator, string>
1184 iterSpotter(Vector& v, int i) {
1185 typename Vector::iterator it;
1190 if (v.empty()) ; // fall through
1203 if (v.empty()) ; // fall through
1216 cerr << "internal error" << endl;
1220 return make_pair(it, msg);
1223 #define TYPIFY_p typename Vector::iterator
1224 #define LOOPER_p for (int p_i = 0; p_i < 4; ++p_i) {
1226 auto p_im = iterSpotter(a, p_i); \
1227 auto& p = p_im.first; \
1228 auto& p_m = p_im.second; \
1229 SCOPED_TRACE("p = " + p_m);
1233 #define TYPIFY_q typename Vector::iterator
1234 #define LOOPER_q for (int q_i = p_i; q_i < 4; ++q_i) {
1236 auto q_im = iterSpotter(a, q_i); \
1237 auto& q = q_im.first; \
1238 auto& q_m = q_im.second; \
1239 SCOPED_TRACE("q = " + q_m);
1246 static const vector<int> tVals = { 0, 1, 2, 3, 17, 66, 521 };
1248 #define TYPIFY_t typename Vector::value_type&
1249 #define LOOPER_t for (int t_v : tVals) {
1251 typename Vector::value_type t_s(t_v); \
1252 t_p = addressof(t_s); \
1253 string t_st = folly::to<string>("t(", t_v, ")"); \
1254 if (t_v < 4 && a_p != nullptr) { \
1255 auto t_im = iterSpotter(*a_p, t_v); \
1256 if (t_im.first != a_p->end()) { \
1257 t_p = addressof(*t_im.first); \
1258 t_st = "t is " + t_im.second; \
1261 typename Vector::value_type& t = *t_p; \
1269 #define TYPIFY_m typename Vector::allocator_type
1271 int m_max = 1 + (a_p != nullptr); \
1272 for (int m_i = 0; m_i < m_max; ++m_i) {
1274 typename Vector::allocator_type m = m_i == 0 \
1275 ? typename Vector::allocator_type() \
1276 : a_p->get_allocator();
1280 //-----------------------------------------------------------------------------
1284 template <class Vector>
1285 void verifyVector(const Vector& v) {
1286 ASSERT_TRUE(v.begin() <= v.end()) << "end is before begin";
1287 ASSERT_TRUE(v.empty() == (v.begin() == v.end())) << "empty != (begin == end)";
1288 ASSERT_TRUE(v.size() == distance(v.begin(), v.end()))
1289 << "size != end - begin";
1290 ASSERT_TRUE(v.size() <= v.capacity()) << "size > capacity";
1291 ASSERT_TRUE(v.capacity() <= v.max_size()) << "capacity > max_size";
1292 ASSERT_TRUE(v.data() || true); // message won't print - it will just crash
1293 ASSERT_TRUE(v.size() == 0 || v.data() != nullptr)
1294 << "nullptr data points to at least one element";
1297 void verifyAllocator(int ele, int cap) {
1298 ASSERT_EQ(ele, AllocTracker::Constructed - AllocTracker::Destroyed);
1301 for (auto kv : AllocTracker::Allocated)
1302 if (kv.second != -1) tot += kv.second;
1303 ASSERT_EQ(cap, tot) << "the allocator counts " << tot << " space, "
1304 "but the vector(s) have (combined) capacity " << cap;
1308 template <class Vector>
1309 void verify(int extras) {
1310 if (!is_arithmetic<typename Vector::value_type>::value)
1311 ASSERT_EQ(0 + extras, getTotal()) << "there exist Data but no vectors";
1313 if (::testing::Test::HasFatalFailure()) return;
1314 if (customAllocator<Vector>::value) verifyAllocator(0, 0);
1316 template <class Vector>
1317 void verify(int extras, const Vector& v) {
1319 if (!is_arithmetic<typename Vector::value_type>::value)
1320 ASSERT_EQ(v.size() + extras, getTotal())
1321 << "not all Data are in the vector";
1323 if (::testing::Test::HasFatalFailure()) return;
1324 if (customAllocator<Vector>::value) verifyAllocator(v.size(), v.capacity());
1326 template <class Vector>
1327 void verify(int extras, const Vector& v1, const Vector& v2) {
1330 auto size = v1.size();
1331 auto cap = v1.capacity();
1334 cap += v2.capacity();
1336 if (!is_arithmetic<typename Vector::value_type>::value)
1337 ASSERT_EQ(size + extras, getTotal()) << "not all Data are in the vector(s)";
1339 if (::testing::Test::HasFatalFailure()) return;
1340 if (customAllocator<Vector>::value) verifyAllocator(size, cap);
1343 //=============================================================================
1346 // save the state of a vector
1347 int convertToInt(int t) {
1350 template <Flags f, size_t pad>
1351 int convertToInt(const Data<f, pad>& t) {
1354 template <typename T>
1355 int convertToInt(const std::allocator<T>&) {
1358 template <typename T>
1359 int convertToInt(const Alloc<T>& a) {
1363 template <class Vector>
1365 typedef typename Vector::size_type size_type;
1369 /* implicit */ DataState(const Vector& v) {
1372 data_ = new int[size_];
1373 for (size_type i = 0; i < size_; ++i) {
1374 data_[i] = convertToInt(v.data()[i]);
1384 bool operator==(const DataState& o) const {
1385 if (size_ != o.size_) return false;
1386 for (size_type i = 0; i < size_; ++i) {
1387 if (data_[i] != o.data_[i]) return false;
1392 int operator[](size_type i) {
1394 cerr << "trying to access DataState out of bounds" << endl;
1400 size_type size() { return size_; }
1403 // downgrade iterators
1404 template <typename It, class tag>
1405 class Transformer : public boost::iterator_adaptor<
1406 Transformer<It, tag>,
1408 typename iterator_traits<It>::value_type,
1411 friend class boost::iterator_core_access;
1412 shared_ptr<set<It>> dereferenced;
1415 explicit Transformer(const It& it)
1416 : Transformer::iterator_adaptor_(it)
1417 , dereferenced(new set<It>()) {}
1419 typename iterator_traits<It>::value_type& dereference() const {
1420 if (dereferenced->find(this->base_reference()) != dereferenced->end()) {
1421 cerr << "iterator dereferenced more than once" << endl;
1424 dereferenced->insert(this->base_reference());
1425 return *this->base_reference();
1429 template <typename It>
1430 Transformer<It, forward_iterator_tag> makeForwardIterator(const It& it) {
1431 return Transformer<It, forward_iterator_tag>(it);
1433 template <typename It>
1434 Transformer<It, input_iterator_tag> makeInputIterator(const It& it) {
1435 return Transformer<It, input_iterator_tag>(it);
1438 // mutate a value (in contract only)
1439 void mutate(int& i) {
1442 void mutate(uint64_t& i) {
1445 template <Flags f, size_t pad>
1446 void mutate(Data<f, pad>& ds) {
1447 if (false) ds.uid = 0;
1450 //=============================================================================
1459 //-----------------------------------------------------------------------------
1462 STL_TEST("23.2.1 Table 96.1-7", containerTypedefs, is_destructible) {
1463 static_assert(is_same<T, typename Vector::value_type>::value,
1464 "T != Vector::value_type");
1465 static_assert(is_same<T&, typename Vector::reference>::value,
1466 "T& != Vector::reference");
1467 static_assert(is_same<const T&, typename Vector::const_reference>::value,
1468 "const T& != Vector::const_reference");
1469 static_assert(is_convertible<
1470 typename iterator_traits<typename Vector::iterator>::iterator_category,
1471 forward_iterator_tag>::value,
1472 "Vector::iterator is not a forward iterator");
1473 static_assert(is_same<T,
1474 typename iterator_traits<typename Vector::iterator>::value_type>::value,
1475 "Vector::iterator does not iterate over type T");
1476 static_assert(is_convertible<
1477 typename iterator_traits<typename Vector::const_iterator>
1478 ::iterator_category,
1479 forward_iterator_tag>::value,
1480 "Vector::const_iterator is not a forward iterator");
1481 static_assert(is_same<T,
1482 typename iterator_traits<typename Vector::const_iterator>
1483 ::value_type>::value,
1484 "Vector::const_iterator does not iterate over type T");
1485 static_assert(is_convertible<
1486 typename Vector::iterator, typename Vector::const_iterator>::value,
1487 "Vector::iterator is not convertible to Vector::const_iterator");
1488 static_assert(is_signed<typename Vector::difference_type>::value,
1489 "Vector::difference_type is not signed");
1490 static_assert(is_same<typename Vector::difference_type,
1491 typename iterator_traits<typename Vector::iterator>
1492 ::difference_type>::value,
1493 "Vector::difference_type != Vector::iterator::difference_type");
1494 static_assert(is_same<typename Vector::difference_type,
1495 typename iterator_traits<typename Vector::const_iterator>
1496 ::difference_type>::value,
1497 "Vector::difference_type != Vector::const_iterator::difference_type");
1498 static_assert(is_unsigned<typename Vector::size_type>::value,
1499 "Vector::size_type is not unsigned");
1500 static_assert(sizeof(typename Vector::size_type) >=
1501 sizeof(typename Vector::difference_type),
1502 "Vector::size_type is smaller than Vector::difference_type");
1505 STL_TEST("23.2.1 Table 96.8-9", emptyConstruction, is_destructible) {
1508 ASSERT_TRUE(u.get_allocator() == Allocator());
1509 ASSERT_EQ(0, Counter::CountTotalOps);
1511 ASSERT_TRUE(u.empty()) << u.size();
1512 ASSERT_EQ(0, u.capacity());
1519 STL_TEST("framework", populate, is_copy_constructible) {
1520 // We use emplace_back to construct vectors for testing, as well as size,
1521 // data, and capacity. We make sure these work before proceeding with tests.
1524 ASSERT_EQ(0, u.size());
1525 ASSERT_EQ(nullptr, u.data());
1528 ASSERT_EQ(1, u.size());
1529 ASSERT_LT(u.capacity(), 100)
1530 << "single push_back increased capacity to " << u.capacity();
1531 ASSERT_NE(nullptr, u.data());
1532 ASSERT_EQ(17, convertToInt(u.data()[0]))
1533 << "first object did not get emplaced correctly";
1535 for (int i = 0; i < 3; ++i) {
1536 auto cap = u.capacity();
1537 while (u.size() < cap) {
1539 ASSERT_EQ(cap, u.capacity()) << "Vector grew when it did not need to";
1540 ASSERT_EQ(22, convertToInt(u.data()[u.size() - 1]))
1541 << "push_back with excess capacity failed";
1544 ASSERT_EQ(cap, u.size());
1547 ASSERT_GT(u.capacity(), cap) << "capacity did not grow on overflow";
1548 ASSERT_EQ(cap + 1, u.size());
1549 ASSERT_EQ(4, convertToInt(u.data()[u.size() - 1]))
1550 << "grow object did not get emplaced correctly";
1554 STL_TEST("23.2.1 Table 96.10-11", copyConstruction,
1555 is_copy_constructible, a) {
1557 DataState<Vector> dsa(ca);
1558 auto am = a.get_allocator();
1562 ASSERT_TRUE(std::allocator_traits<Allocator>::
1563 select_on_container_copy_construction(am) == u.get_allocator());
1564 ASSERT_TRUE(dsa == u);
1566 (ca.data() == nullptr && u.data() == nullptr) ||
1567 (ca.data() != u.data())
1568 ) << "only a shallow copy was made";
1576 STL_TEST("23.2.1 Table 96.12", moveConstruction, is_destructible, a) {
1577 DataState<Vector> dsa(a);
1578 auto m = a.get_allocator();
1582 ASSERT_TRUE(m == u.get_allocator());
1583 ASSERT_EQ(0, Counter::CountTotalOps);
1585 ASSERT_TRUE(dsa == u);
1592 STL_TEST("23.2.1 Table 96.13", moveAssignment, special_move_assignable, a, b) {
1593 DataState<Vector> dsb(b);
1594 auto am = a.get_allocator();
1595 auto bm = b.get_allocator();
1597 Vector& ret = a = std::move(b);
1599 if (std::allocator_traits<Allocator>::
1600 propagate_on_container_move_assignment::value) {
1601 ASSERT_TRUE(bm == a.get_allocator());
1603 ASSERT_TRUE(am == a.get_allocator());
1605 ASSERT_TRUE(&ret == &a);
1606 ASSERT_TRUE(&a == &b || dsb == a) << "move assignment did not create a copy";
1607 // The source of the move may be left in any (albeit valid) state.
1610 STL_TEST("23.2.1 Table 96.14", destructible, is_destructible) {
1611 // The test generators check this clause already.
1614 STL_TEST("23.2.1 Table 96.15-18", iterators, is_destructible, a) {
1615 DataState<Vector> dsa(a);
1618 auto itb = a.begin();
1619 auto citb = ca.begin();
1620 auto Citb = a.cbegin();
1622 auto cite = ca.end();
1623 auto Cite = a.cend();
1625 ASSERT_EQ(0, Counter::CountTotalOps);
1627 ASSERT_TRUE(dsa == a) << "call to begin or end modified internal data";
1629 ASSERT_TRUE(citb == Citb) << "cv.begin != v.cbegin";
1630 ASSERT_TRUE(cite == Cite) << "cv.end != v.cend";
1632 if (ca.size() == 0) {
1633 ASSERT_TRUE( itb == ite) << "begin != end when empty";
1634 ASSERT_TRUE(Citb == Cite) << "cbegin != cend when empty";
1636 ASSERT_TRUE( itb != ite) << "begin == end when non-empty";
1637 ASSERT_TRUE(Citb != Cite) << "cbegin == cend when non-empty";
1640 auto dist = std::distance( itb, ite);
1641 auto Cdist = std::distance(Citb, Cite);
1642 ASSERT_TRUE( dist == ca.size()) << "distance(begin, end) != size";
1643 ASSERT_TRUE(Cdist == ca.size()) << "distance(cbegin, cend) != size";
1646 STL_TEST("23.2.1 Table 96.19-20", equitable, is_arithmetic, a, b) {
1649 DataState<Vector> dsa(a);
1650 DataState<Vector> dsb(b);
1652 ASSERT_TRUE((bool)(ca == cb) == (bool)(dsa == dsb))
1653 << "== does not return equality";
1654 ASSERT_TRUE((bool)(ca == cb) != (bool)(ca != cb))
1655 << "!= is not the opposite of ==";
1657 // Data is uncomparable, by design; therefore this test's restriction
1658 // is 'is_arithmetic'
1661 STL_TEST("23.2.1 Table 96.21", memberSwappable, is_destructible, a, b) {
1662 if (!std::allocator_traits<Allocator>::
1663 propagate_on_container_swap::value &&
1664 convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1665 // undefined behaviour
1669 DataState<Vector> dsa(a);
1670 DataState<Vector> dsb(b);
1671 auto adata = a.data();
1672 auto bdata = b.data();
1673 auto am = a.get_allocator();
1674 auto bm = b.get_allocator();
1679 FAIL() << "swap is noexcept";
1682 if (std::allocator_traits<Allocator>::
1683 propagate_on_container_swap::value) {
1684 ASSERT_TRUE(bm == a.get_allocator());
1685 ASSERT_TRUE(am == b.get_allocator());
1687 ASSERT_TRUE(am == a.get_allocator());
1688 ASSERT_TRUE(bm == b.get_allocator());
1690 ASSERT_EQ(0, Counter::CountTotalOps);
1692 ASSERT_TRUE(adata == b.data() && bdata == a.data());
1693 ASSERT_TRUE(dsa == b && dsb == a) << "swap did not swap";
1696 STL_TEST("23.2.1 Table 96.22", nonmemberSwappable,
1697 is_destructible, a, b) {
1698 if (!std::allocator_traits<Allocator>::
1699 propagate_on_container_swap::value &&
1700 convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1701 // undefined behaviour
1705 DataState<Vector> dsa(a);
1706 DataState<Vector> dsb(b);
1707 auto adata = a.data();
1708 auto bdata = b.data();
1709 auto am = a.get_allocator();
1710 auto bm = b.get_allocator();
1715 FAIL() << "swap is noexcept";
1718 if (std::allocator_traits<Allocator>::
1719 propagate_on_container_swap::value) {
1720 ASSERT_TRUE(bm == a.get_allocator());
1721 ASSERT_TRUE(am == b.get_allocator());
1723 ASSERT_TRUE(am == a.get_allocator());
1724 ASSERT_TRUE(bm == b.get_allocator());
1726 ASSERT_EQ(0, Counter::CountTotalOps);
1728 ASSERT_TRUE(adata == b.data() && bdata == a.data());
1729 ASSERT_TRUE(dsa == b && dsb == a) << "swap did not swap";
1732 STL_TEST("23.2.1 Table 96.23", copyAssign,
1733 is_copy_constructibleAndAssignable, a, b) {
1734 // it is possible to make use of just the copy constructor.
1736 #ifdef USING_STD_VECTOR
1737 if (std::allocator_traits<Allocator>::
1738 propagate_on_container_copy_assignment::value &&
1739 convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1740 // Bug. By the looks of things, in the above case, their bez is being
1741 // cleared and deallocated, but then the garbage pointers are being used.
1747 DataState<Vector> dsb(cb);
1748 auto am = a.get_allocator();
1749 auto bm = b.get_allocator();
1751 Vector& ret = a = cb;
1753 if (std::allocator_traits<Allocator>::
1754 propagate_on_container_copy_assignment::value) {
1755 ASSERT_TRUE(bm == a.get_allocator());
1757 ASSERT_TRUE(am == a.get_allocator());
1759 ASSERT_TRUE(&ret == &a);
1760 ASSERT_TRUE(dsb == a) << "copy-assign not equal to original";
1763 STL_TEST("23.2.1 Table 96.24-26", sizeops, is_destructible) {
1764 // This check generators check this clause already.
1767 //-----------------------------------------------------------------------------
1768 // Reversible container
1770 STL_TEST("23.2.1 Table 97.1-2", reversibleContainerTypedefs,
1772 static_assert(is_same<typename Vector::reverse_iterator,
1773 std::reverse_iterator<typename Vector::iterator>>::value,
1774 "Vector::reverse_iterator != reverse_iterator<Vector:iterator");
1775 static_assert(is_same<typename Vector::const_reverse_iterator,
1776 std::reverse_iterator<typename Vector::const_iterator>>::value,
1777 "Vector::const_reverse_iterator != "
1778 "const_reverse_iterator<Vector::iterator");
1781 STL_TEST("23.2.1 Table 97.3-5", reversibleIterators, is_destructible, a) {
1783 DataState<Vector> ds(a);
1785 auto ritb = a.rbegin();
1786 auto critb = ca.rbegin();
1787 auto Critb = a.crbegin();
1788 auto rite = a.rend();
1789 auto crite = ca.rend();
1790 auto Crite = a.crend();
1792 ASSERT_EQ(0, Counter::CountTotalOps);
1794 ASSERT_TRUE(ds == a) << "call to rbegin or rend modified internal data";
1796 ASSERT_TRUE(critb == Critb) << "cv.rbegin != v.crbegin";
1797 ASSERT_TRUE(crite == Crite) << "cv.rend != v.crend";
1799 if (ca.size() == 0) {
1800 ASSERT_TRUE( ritb == rite) << "rbegin != rend when empty";
1801 ASSERT_TRUE(Critb == Crite) << "crbegin != crend when empty";
1803 ASSERT_TRUE( ritb != rite) << "rbegin == rend when non-empty";
1804 ASSERT_TRUE(Critb != Crite) << "crbegin == crend when non-empty";
1807 auto dist = std::distance( ritb, rite);
1808 auto Cdist = std::distance(Critb, Crite);
1809 ASSERT_TRUE( dist == ca.size()) << "distance(rbegin, rend) != size";
1810 ASSERT_TRUE(Cdist == ca.size()) << "distance(crbegin, crend) != size";
1813 //-----------------------------------------------------------------------------
1814 // Lexicographical functions
1816 STL_TEST("23.2.1 Table 98", comparable, is_arithmetic) {
1817 const Vector v1 = { 1, 2, 3, 4 };
1818 const Vector v2 = { 1, 2, 3, 4, 5 };
1819 const Vector v3 = { 1, 2, 2 };
1820 const Vector v4 = { 1, 2, 2, 4, 5 };
1821 const Vector v5 = { };
1822 const Vector v6 = { 1, 2, 3, 4 };
1824 ASSERT_TRUE(v1 < v2);
1825 ASSERT_TRUE(v1 > v3);
1826 ASSERT_TRUE(v1 > v4);
1827 ASSERT_TRUE(v1 > v5);
1828 ASSERT_TRUE(v1 <= v6);
1829 ASSERT_TRUE(v1 >= v6);
1832 //-----------------------------------------------------------------------------
1833 // Allocator-aware requirements (AA)
1835 STL_TEST("23.2.1 Table 99.1", allocatorTypedefs, is_destructible) {
1836 static_assert(is_same<T, typename Vector::allocator_type::value_type>::value,
1837 "Vector and vector's allocator value_type mismatch");
1840 STL_TEST("23.2.1 Table 99.2", getAllocator, is_destructible) {
1841 // whitebox: ensure that a.get_allocator() returns a copy of its allocator
1844 STL_TEST("23.2.1 Table 99.3", defaultAllocator, is_destructible) {
1845 // there is nothing new to test here
1848 STL_TEST("23.2.1 Table 99.4", customAllocator, is_destructible, m) {
1853 ASSERT_TRUE(u.get_allocator() == m);
1860 STL_TEST("23.2.1 Table 99.5", copyWithAllocator, is_copy_constructible, a, m) {
1861 DataState<Vector> dsa(a);
1867 ASSERT_TRUE(u.get_allocator() == m);
1868 ASSERT_TRUE(dsa == u);
1870 (ca.data() == nullptr && u.data() == nullptr) ||
1871 (ca.data() != u.data())
1872 ) << "only a shallow copy was made";
1875 STL_TEST("23.2.1 Table 99.6", moveConstructionWithAllocator,
1876 is_destructible, a) {
1877 // there is nothing new to test here
1880 STL_TEST("23.2.1 Table 99.6", moveConstructionWithAllocatorSupplied,
1881 is_move_constructible, a, m) {
1882 bool deep = m != a.get_allocator();
1883 auto osize = a.size();
1884 auto oalloc = AllocTracker::Constructed;
1887 Vector u(std::move(a), cm);
1889 ASSERT_TRUE(u.get_allocator() == m);
1892 if (!AllocTracker::Allocated.empty()) {
1893 ASSERT_EQ(osize, AllocTracker::Constructed - oalloc);
1896 ASSERT_EQ(0, Counter::CountTotalOps);
1900 STL_TEST("23.2.1 Table 99.7-9", allocAssign, is_destructible) {
1901 // there is nothing new to test here
1904 STL_TEST("23.2.1-7", nAllocConstruction, is_copy_constructible, n, m) {
1905 #ifndef USING_STD_VECTOR
1910 ASSERT_TRUE(m == u.get_allocator());
1914 STL_TEST("23.2.1-7", nCopyAllocConstruction, is_copy_constructible, n, t, m) {
1918 Vector u(n, ct, cm);
1920 ASSERT_TRUE(m == u.get_allocator());
1923 STL_TEST("23.2.1-7", forwardIteratorAllocConstruction,
1924 is_destructible, i, j, m) {
1925 auto fi = makeForwardIterator(i);
1926 auto fj = makeForwardIterator(j);
1927 const auto& cfi = fi;
1928 const auto& cfj = fj;
1931 Vector u(cfi, cfj, cm);
1933 ASSERT_TRUE(m == u.get_allocator());
1936 STL_TEST("23.2.1-7", inputIteratorAllocConstruction,
1937 is_move_constructible, i, j, m) {
1938 #ifdef USING_STD_VECTOR
1939 if (Ticker::TicksLeft >= 0) return;
1942 auto ii = makeInputIterator(i);
1943 auto ij = makeInputIterator(j);
1944 const auto& cii = ii;
1945 const auto& cij = ij;
1948 Vector u(cii, cij, cm);
1950 ASSERT_TRUE(m == u.get_allocator());
1953 STL_TEST("23.2.1-7", ilAllocConstruction, is_arithmetic, m) {
1955 if (Ticker::TicksLeft >= 0) return;
1959 Vector u({ 1, 4, 7 }, cm);
1961 ASSERT_TRUE(m == u.get_allocator());
1964 //-----------------------------------------------------------------------------
1967 STL_TEST("23.2.2", dataRaces, is_destructible) {
1969 const Vector* cv = nullptr;
1970 typename Vector::size_type* s = nullptr;
1984 // White-box: check that the non-const versions of each of the above
1985 // functions is implemented in terms of (or the same as) the const version
1988 //-----------------------------------------------------------------------------
1989 // Sequence container
1991 STL_TEST("23.2.3 Table 100.1, alt", nConstruction, is_constructible, n) {
1994 ASSERT_TRUE(Allocator() == u.get_allocator());
1995 ASSERT_EQ(n, u.size());
1996 ASSERT_EQ(Counter::CountTotalOps, Counter::CountDC);
1999 STL_TEST("23.2.3 Table 100.1", nCopyConstruction,
2000 is_copy_constructible, n, t) {
2005 ASSERT_TRUE(Allocator() == u.get_allocator());
2006 ASSERT_EQ(n, u.size()) << "Vector(n, t).size() != n" << endl;
2007 for (const auto& val : u) ASSERT_EQ(convertToInt(t), convertToInt(val))
2008 << "not all elements of Vector(n, t) are equal to t";
2011 STL_TEST("23.2.3 Table 100.2", forwardIteratorConstruction,
2012 is_destructible, i, j) {
2013 // All data is emplace-constructible from int, so we restrict to
2016 auto fi = makeForwardIterator(i);
2017 auto fj = makeForwardIterator(j);
2018 const auto& cfi = fi;
2019 const auto& cfj = fj;
2023 ASSERT_TRUE(Allocator() == u.get_allocator());
2024 ASSERT_LE(Counter::CountTotalOps, j-i);
2026 ASSERT_EQ(j - i, u.size()) << "u(i,j).size() != j-i";
2027 for (auto it = u.begin(); it != u.end(); ++it, ++i)
2028 ASSERT_EQ(*i, convertToInt(*it)) << "u(i,j) constructed incorrectly";
2031 STL_TEST("23.2.3 Table 100.2", inputIteratorConstruction,
2032 is_move_constructible, i, j) {
2033 #ifdef USING_STD_VECTOR
2034 if (Ticker::TicksLeft >= 0) return;
2037 auto ii = makeInputIterator(i);
2038 auto ij = makeInputIterator(j);
2039 const auto& cii = ii;
2040 const auto& cij = ij;
2044 ASSERT_TRUE(Allocator() == u.get_allocator());
2045 ASSERT_EQ(j - i, u.size()) << "u(i,j).size() != j-i";
2046 for (auto it = u.begin(); it != u.end(); ++it, ++i)
2047 ASSERT_EQ(*i, convertToInt(*it)) << "u(i,j) constructed incorrectly";
2050 STL_TEST("23.2.3 Table 100.3", ilConstruction, is_arithmetic) {
2051 // whitebox: ensure that Vector(il) is implemented in terms of
2052 // Vector(il.begin(), il.end())
2055 if (Ticker::TicksLeft >= 0) return;
2057 Vector u = { 1, 4, 7 };
2059 ASSERT_TRUE(Allocator() == u.get_allocator());
2060 ASSERT_EQ(3, u.size()) << "u(il).size() fail";
2062 auto it = u.begin();
2063 for (; it != u.end(); ++it, i += 3)
2064 ASSERT_EQ(i, convertToInt(*it)) << "u(il) constructed incorrectly";
2067 STL_TEST("23.2.3 Table 100.4", ilAssignment,
2069 // whitebox: ensure that assign(il) is implemented in terms of
2070 // assign(il.begin(), il.end())
2073 if (Ticker::TicksLeft >= 0) return;
2075 auto am = a.get_allocator();
2077 Vector& b = a = { 1, 4, 7 };
2079 ASSERT_TRUE(am == a.get_allocator());
2080 ASSERT_TRUE(&b == &a) << "'a = ...' did not return *this";
2082 ASSERT_EQ(3, a.size()) << "u(il).size() fail";
2084 auto it = a.begin();
2085 for (; it != a.end(); ++it, i += 3)
2086 ASSERT_EQ(i, convertToInt(*it)) << "u(il) constructed incorrectly";
2089 //----------------------------
2090 // insert-and-erase subsection
2092 template <class Vector>
2093 void insertNTCheck(const Vector& a, DataState<Vector>& dsa,
2094 int idx, int n, int val) {
2095 ASSERT_EQ(dsa.size() + n, a.size());
2097 for (; i < idx; ++i) {
2098 ASSERT_EQ(dsa[i], convertToInt(a.data()[i])) << i;
2100 for (; i < idx + n; ++i) {
2101 ASSERT_EQ(val, convertToInt(a.data()[i])) << i;
2103 for (; i < a.size(); ++i) {
2104 ASSERT_EQ(dsa[i-n], convertToInt(a.data()[i])) << i;
2108 STL_TEST("23.2.3 Table 100.5", iteratorEmplacement,
2109 is_move_constructibleAndAssignable, a, p) {
2110 DataState<Vector> dsa(a);
2111 int idx = distance(a.begin(), p);
2112 auto am = a.get_allocator();
2114 auto q = a.emplace(p, 44);
2116 ASSERT_TRUE(am == a.get_allocator());
2117 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2118 insertNTCheck(a, dsa, idx, 1, 44);
2121 STL_TEST("23.2.3 Table 100.6", iteratorInsertion,
2122 is_copy_constructibleAndAssignable, a, p, t) {
2123 DataState<Vector> dsa(a);
2124 int idx = distance(a.begin(), p);
2125 int tval = convertToInt(t);
2126 auto am = a.get_allocator();
2129 auto q = a.insert(p, ct);
2131 ASSERT_TRUE(am == a.get_allocator());
2132 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2133 insertNTCheck(a, dsa, idx, 1, tval);
2136 STL_TEST("23.2.3 Table 100.7", iteratorInsertionRV,
2137 is_move_constructibleAndAssignable, a, p, t) {
2138 // rvalue-references cannot have their address checked for aliased inserts
2139 if (a.data() <= addressof(t) && addressof(t) < a.data() + a.size()) return;
2141 DataState<Vector> dsa(a);
2142 int idx = distance(a.begin(), p);
2143 int tval = convertToInt(t);
2144 auto am = a.get_allocator();
2146 auto q = a.insert(p, std::move(t));
2148 ASSERT_TRUE(am == a.get_allocator());
2149 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2150 insertNTCheck(a, dsa, idx, 1, tval);
2153 STL_TEST("23.2.3 Table 100.8", iteratorInsertionN,
2154 is_copy_constructibleAndAssignable, a, p, n, t) {
2155 DataState<Vector> dsa(a);
2156 int idx = distance(a.begin(), p);
2157 int tval = convertToInt(t);
2158 auto am = a.get_allocator();
2161 #ifndef USING_STD_VECTOR
2167 ASSERT_TRUE(am == a.get_allocator());
2168 #ifndef USING_STD_VECTOR
2169 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2172 insertNTCheck(a, dsa, idx, n, tval);
2175 template <class Vector>
2176 void insertItCheck(const Vector& a, DataState<Vector>& dsa,
2177 int idx, int* b, int* e) {
2178 ASSERT_EQ(dsa.size() + (e - b), a.size());
2180 for (; i < idx; ++i) {
2181 ASSERT_EQ(dsa[i], convertToInt(a.data()[i]));
2183 for (; i < idx + (e - b); ++i) {
2184 ASSERT_EQ(*(b + i - idx), convertToInt(a.data()[i]));
2186 for (; i < a.size(); ++i) {
2187 ASSERT_EQ(dsa[i - (e - b)], convertToInt(a.data()[i]));
2191 STL_TEST("23.2.3 Table 100.9", iteratorInsertionIterator,
2192 is_move_constructibleAndAssignable, a, p, i, j) {
2193 DataState<Vector> dsa(a);
2194 int idx = distance(a.begin(), p);
2196 auto fi = makeForwardIterator(i);
2197 auto fj = makeForwardIterator(j);
2198 auto am = a.get_allocator();
2199 const auto& cfi = fi;
2200 const auto& cfj = fj;
2202 #ifndef USING_STD_VECTOR
2206 a.insert(p, cfi, cfj);
2208 ASSERT_TRUE(am == a.get_allocator());
2209 #ifndef USING_STD_VECTOR
2210 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2213 insertItCheck(a, dsa, idx, i, j);
2216 STL_TEST("23.2.3 Table 100.9", iteratorInsertionInputIterator,
2217 is_move_constructibleAndAssignable, a, p, i, j) {
2218 DataState<Vector> dsa(a);
2219 int idx = distance(a.begin(), p);
2221 auto ii = makeInputIterator(i);
2222 auto ij = makeInputIterator(j);
2223 auto am = a.get_allocator();
2224 const auto& cii = ii;
2225 const auto& cij = ij;
2227 #ifndef USING_STD_VECTOR
2231 a.insert(p, cii, cij);
2233 ASSERT_TRUE(am == a.get_allocator());
2234 #ifndef USING_STD_VECTOR
2235 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2238 insertItCheck(a, dsa, idx, i, j);
2241 STL_TEST("23.2.3 Table 100.10", iteratorInsertIL,
2242 is_arithmetic, a, p) {
2244 if (Ticker::TicksLeft >= 0) return;
2246 // whitebox: ensure that insert(p, il) is implemented in terms of
2247 // insert(p, il.begin(), il.end())
2249 DataState<Vector> dsa(a);
2250 int idx = distance(a.begin(), p);
2251 auto am = a.get_allocator();
2253 #ifndef USING_STD_VECTOR
2257 a.insert(p, {1, 4, 7});
2259 ASSERT_TRUE(am == a.get_allocator());
2260 #ifndef USING_STD_VECTOR
2261 ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2264 int ila[] = { 1, 4, 7 };
2267 insertItCheck(a, dsa, idx, i, j);
2270 template <class Vector>
2271 void eraseCheck(Vector& a, DataState<Vector>& dsa, int idx, int n) {
2272 ASSERT_EQ(dsa.size() - n, a.size());
2274 auto it = a.begin();
2275 for (; it != a.end(); ++it, ++i) {
2276 if (i == idx) i += n;
2277 ASSERT_EQ(dsa[i], convertToInt(*it));
2281 STL_TEST("23.2.3 Table 100.11", iteratorErase, is_move_assignable, a, p) {
2282 if (p == a.end()) return;
2284 DataState<Vector> dsa(a);
2285 int idx = distance(a.begin(), p);
2286 auto am = a.get_allocator();
2288 auto rit = a.erase(p);
2290 ASSERT_TRUE(am == a.get_allocator());
2291 ASSERT_EQ(idx, distance(a.begin(), rit)) << "wrong iterator returned";
2292 eraseCheck(a, dsa, idx, 1);
2295 STL_TEST("23.2.3 Table 100.12", iteratorEraseRange,
2296 is_move_assignable, a, p, q) {
2297 if (p == a.end()) return;
2299 DataState<Vector> dsa(a);
2300 int idx = distance(a.begin(), p);
2301 auto am = a.get_allocator();
2303 auto rit = a.erase(p, q);
2305 ASSERT_TRUE(am == a.get_allocator());
2306 ASSERT_EQ(idx, distance(a.begin(), rit)) << "wrong iterator returned";
2307 eraseCheck(a, dsa, idx, distance(p,q));
2310 //--------------------------------
2311 // end insert-and-erase subsection
2313 STL_TEST("23.2.3 Table 100.13", clear, is_destructible, a) {
2315 auto am = a.get_allocator();
2320 FAIL() << "clear must be noexcept";
2323 ASSERT_TRUE(am == a.get_allocator());
2324 ASSERT_TRUE(a.empty());
2327 STL_TEST("23.2.3 Table 100.14", assignRange, is_move_assignable, a, i, j) {
2328 auto fi = makeForwardIterator(i);
2329 auto fj = makeForwardIterator(j);
2330 const auto& cfi = fi;
2331 const auto& cfj = fj;
2332 auto am = a.get_allocator();
2336 ASSERT_TRUE(am == a.get_allocator());
2337 ASSERT_EQ(distance(i, j), a.size());
2338 for (auto it = a.begin(); it != a.end(); ++it, ++i)
2339 ASSERT_EQ(*i, convertToInt(*it));
2342 STL_TEST("23.2.3 Table 100.14", assignInputRange,
2343 is_move_constructibleAndAssignable, a, i, j) {
2344 auto ii = makeInputIterator(i);
2345 auto ij = makeInputIterator(j);
2346 const auto& cii = ii;
2347 const auto& cij = ij;
2348 auto am = a.get_allocator();
2352 ASSERT_TRUE(am == a.get_allocator());
2353 ASSERT_EQ(distance(i, j), a.size());
2354 for (auto it = a.begin(); it != a.end(); ++it, ++i)
2355 ASSERT_EQ(*i, convertToInt(*it));
2358 STL_TEST("23.2.3 Table 100.15", assignIL,
2361 // whitebox: ensure that assign(il) is implemented in terms of
2362 // assign(il.begin(), il.end())
2365 if (Ticker::TicksLeft >= 0) return;
2367 auto am = a.get_allocator();
2369 a.assign({1, 4, 7});
2371 ASSERT_TRUE(am == a.get_allocator());
2372 int ila[] = { 1, 4, 7 };
2375 ASSERT_EQ(3, a.size());
2376 for (auto it = a.begin(); it != a.end(); ++it, ++i)
2377 ASSERT_EQ(*i, convertToInt(*it));
2380 STL_TEST("23.2.3 Table 100.16", assignN,
2381 is_copy_constructibleAndAssignable, a, n, t) {
2382 auto am = a.get_allocator();
2384 auto tval = convertToInt(t);
2388 ASSERT_TRUE(am == a.get_allocator());
2389 ASSERT_EQ(n, a.size());
2390 for (auto it = a.begin(); it != a.end(); ++it)
2391 ASSERT_EQ(tval, convertToInt(*it));
2394 STL_TEST("23.2.3 Table 101.1", front, is_destructible, a) {
2395 if (a.empty()) return;
2397 ASSERT_TRUE(addressof(a.front()) == a.data());
2399 ASSERT_EQ(0, Counter::CountTotalOps);
2403 const Vector& ca = a;
2408 STL_TEST("23.2.3 Table 101.2", back, is_destructible, a) {
2409 if (a.empty()) return;
2411 ASSERT_TRUE(addressof(a.back()) == a.data() + a.size() - 1);
2413 ASSERT_EQ(0, Counter::CountTotalOps);
2417 const Vector& ca = a;
2422 STL_TEST("23.2.3 Table 101.4", emplaceBack,
2423 is_move_constructible, a) {
2424 DataState<Vector> dsa(a);
2425 auto adata = a.data();
2426 int excess = a.capacity() - a.size();
2427 auto am = a.get_allocator();
2432 ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2436 ASSERT_TRUE(am == a.get_allocator());
2437 if (excess > 0) ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2438 ASSERT_EQ(dsa.size() + 1, a.size());
2440 auto it = a.begin();
2441 for (; i < dsa.size(); ++i, ++it)
2442 ASSERT_EQ(dsa[i], convertToInt(*it));
2443 ASSERT_EQ(44, convertToInt(a.back()));
2446 STL_TEST("23.2.3 Table 101.7", pushBack, is_copy_constructible, a, t) {
2447 DataState<Vector> dsa(a);
2448 int tval = convertToInt(t);
2449 auto adata = a.data();
2450 int excess = a.capacity() - a.size();
2451 auto am = a.get_allocator();
2457 ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2461 ASSERT_TRUE(am == a.get_allocator());
2462 if (excess > 0) ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2463 ASSERT_EQ(dsa.size() + 1, a.size());
2465 auto it = a.begin();
2466 for (; i < dsa.size(); ++i, ++it)
2467 ASSERT_EQ(dsa[i], convertToInt(*it));
2468 ASSERT_EQ(tval, convertToInt(a.back()));
2471 STL_TEST("23.2.3 Table 101.8", pushBackRV,
2472 is_move_constructible, a, t) {
2473 DataState<Vector> dsa(a);
2474 int tval = convertToInt(t);
2475 auto adata = a.data();
2476 int excess = a.capacity() - a.size();
2477 auto am = a.get_allocator();
2480 a.push_back(move(t));
2482 ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2486 ASSERT_TRUE(am == a.get_allocator());
2487 if (excess > 0) ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2488 ASSERT_EQ(dsa.size() + 1, a.size());
2490 auto it = a.begin();
2491 for (; i < dsa.size(); ++i, ++it)
2492 ASSERT_EQ(dsa[i], convertToInt(*it));
2493 ASSERT_EQ(tval, convertToInt(a.back()));
2496 STL_TEST("23.2.3 Table 100.10", popBack, is_destructible, a) {
2497 if (a.empty()) return;
2499 DataState<Vector> dsa(a);
2500 auto am = a.get_allocator();
2504 ASSERT_TRUE(am == a.get_allocator());
2505 ASSERT_EQ(dsa.size() - 1, a.size());
2507 auto it = a.begin();
2508 for (; it != a.end(); ++it, ++i)
2509 ASSERT_EQ(dsa[i], convertToInt(*it));
2512 STL_TEST("23.2.3 Table 100.11", operatorBrace, is_destructible, a) {
2514 for (int i = 0; i < ca.size(); ++i)
2515 ASSERT_TRUE(addressof(ca[i]) == ca.data()+i);
2517 ASSERT_EQ(0, Counter::CountTotalOps);
2524 STL_TEST("23.2.3 Table 100.12", at, is_destructible, a) {
2526 for (int i = 0; i < ca.size(); ++i)
2527 ASSERT_TRUE(addressof(ca.at(i)) == ca.data()+i);
2529 ASSERT_EQ(0, Counter::CountTotalOps);
2533 FAIL() << "at(size) should have thrown an error";
2534 } catch (const std::out_of_range& e) {
2536 FAIL() << "at(size) threw error other than out_of_range";
2544 STL_TEST("move iterators", moveIterators, is_copy_constructibleAndAssignable) {
2549 auto mfi = make_move_iterator(makeForwardIterator(i));
2550 auto mfj = make_move_iterator(makeForwardIterator(j));
2551 auto mii = make_move_iterator(makeInputIterator(i));
2552 auto mij = make_move_iterator(makeInputIterator(j));
2554 Vector u1(mfi, mfj);
2555 Vector u2(mii, mij);
2557 u1.insert(u1.begin(), mfi, mfj);
2558 u1.insert(u1.begin(), mii, mij);
2560 u1.assign(mfi, mfj);
2561 u1.assign(mii, mij);
2565 //-----------------------------------------------------------------------------
2568 STL_TEST("23.3.6.4", dataAndCapacity, is_destructible) {
2569 // there isn't anything new to test here - data and capacity are used as the
2570 // backbone of DataState. The minimal testing we might want to do is already
2571 // done in the populate test
2574 STL_TEST("23.3.6.3", reserve, is_move_constructible, a, n) {
2575 auto adata = a.data();
2576 auto ocap = a.capacity();
2577 auto am = a.get_allocator();
2581 ASSERT_TRUE(am == a.get_allocator());
2583 ASSERT_EQ(0, Counter::CountTotalOps);
2584 ASSERT_TRUE(adata == a.data());
2586 ASSERT_TRUE(a.capacity() >= n);
2587 ASSERT_LE(Counter::CountTotalOps, 2*a.size()); // move and delete
2591 STL_TEST("23.3.6.3", lengthError, is_move_constructible) {
2592 auto mx = Vector().max_size();
2594 if (mx >= big) return; // max_size is the biggest size_type; overflowed
2599 FAIL() << "reserve(big) should have thrown an error";
2600 } catch (const std::length_error& e) {
2602 FAIL() << "reserve(big) threw error other than length_error";
2606 STL_TEST("23.3.6.3", resize, is_copy_constructible, a, n) {
2607 DataState<Vector> dsa(a);
2609 auto am = a.get_allocator();
2613 ASSERT_TRUE(am == a.get_allocator());
2614 ASSERT_EQ(n, a.size());
2617 for (int i = 0; i < n; ++i) {
2618 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2621 for (int i = 0; i < sz; ++i) {
2622 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2627 STL_TEST("23.3.6.3", resizeT, is_copy_constructibleAndAssignable, a, n, t) {
2628 #ifdef USING_STD_VECTOR
2629 if (a.data() <= addressof(t) && addressof(t) < a.data() + a.size()) return;
2632 DataState<Vector> dsa(a);
2634 auto am = a.get_allocator();
2636 int val = convertToInt(t);
2640 ASSERT_TRUE(am == a.get_allocator());
2641 ASSERT_EQ(n, a.size());
2644 for (int i = 0; i < n; ++i) {
2645 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2649 for ( ; i < sz; ++i) {
2650 ASSERT_EQ(dsa[i], convertToInt(a[i]));
2652 for ( ; i < n; ++i) {
2653 ASSERT_EQ(val, convertToInt(a[i]));
2658 STL_TEST("23.3.6.3", shrinkToFit, is_move_constructible, a) {
2659 bool willThrow = Ticker::TicksLeft >= 0;
2661 a.reserve(a.capacity() * 11);
2663 auto ocap = a.capacity();
2664 DataState<Vector> dsa(a);
2666 auto am = a.get_allocator();
2671 FAIL() << "shrink_to_fit should swallow errors";
2674 ASSERT_TRUE(am == a.get_allocator());
2675 ASSERT_TRUE(dsa == a);
2677 //ASSERT_EQ(ocap, a.capacity()); might shrink in place
2678 throw TickException("I swallowed the error");
2680 ASSERT_TRUE(a.capacity() == 0 || a.capacity() < ocap) << "Look into this";
2684 #ifndef USING_STD_VECTOR
2685 STL_TEST("EBO", ebo, is_destructible) {
2686 static_assert(!is_same<Allocator, std::allocator<T>>::value ||
2687 sizeof(Vector) == 3 * sizeof(void*),
2688 "fbvector has default allocator, but has size != 3*sizeof(void*)");
2691 STL_TEST("relinquish", relinquish, is_destructible, a) {
2693 auto cap = a.capacity();
2694 auto data = a.data();
2696 auto guts = relinquish(a);
2698 ASSERT_EQ(data, guts);
2699 ASSERT_TRUE(a.empty());
2700 ASSERT_EQ(0, a.capacity());
2702 auto alloc = a.get_allocator();
2703 for (size_t i = 0; i < sz; ++i)
2704 std::allocator_traits<decltype(alloc)>::destroy(alloc, guts + i);
2705 if (guts != nullptr)
2706 std::allocator_traits<decltype(alloc)>::deallocate(alloc, guts, cap);
2709 STL_TEST("attach", attach, is_destructible, a) {
2710 DataState<Vector> dsa(a);
2713 auto cap = a.capacity();
2714 auto guts = relinquish(a);
2716 ASSERT_EQ(a.data(), nullptr);
2717 attach(a, guts, sz, cap);
2719 ASSERT_TRUE(dsa == a);
2726 int main(int argc, char** argv) {
2727 testing::InitGoogleTest(&argc, argv);
2728 google::ParseCommandLineFlags(&argc, &argv, true);
2730 return RUN_ALL_TESTS();
2733 #else // GCC 4.7 guard
2735 #include <gflags/gflags.h>
2736 #include <gtest/gtest.h>
2739 TEST(placeholder, gccversion) {}
2741 int main(int argc, char** argv) {
2742 testing::InitGoogleTest(&argc, argv);
2743 google::ParseCommandLineFlags(&argc, &argv, true);
2745 return RUN_ALL_TESTS();
2748 #endif // GCC 4.7 guard