folly/test/stl_tests/StlVectorTest.cpp

   1 /*
   2  * Copyright 2014 Facebook, Inc.
   3  *
   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
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16
  17 // @author Nicholas Ormrod <njormrod@fb.com>
  18
  19 /*
  20
  21 This file contains an extensive STL compliance test suite for an STL vector
  22 implementation (such as FBVector).
  23
  24 GCC 4.7 is required.
  25
  26 */
  27
  28 // only compile if GCC is at least 4.7
  29 #if __GNUC__ > 4 || __GNUC__ == 4 && __GNUC_MINOR__ >= 7
  30
  31 #if 0
  32 #define USING_STD_VECTOR
  33 #endif
  34
  35 /*
  36
  37 The insanity of this file deserves a superficial explanation.
  38
  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.
  42
  43 Limitations:
  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.
  49
  50 ==========================
  51 How this file is organized
  52
  53 --------------
  54 Data and Alloc
  55
  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.
  61
  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.
  65
  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
  70
  71 --------
  72 STL_TEST
  73
  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.
  76
  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
  82
  83 Eg: STL_TEST("23.2.3", isCopyable, is_copy_constructible, a) { ... }
  84
  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).
  90
  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
  94 parameters a and n.
  95
  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.
 101
 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.
 107
 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
 113 thoroughly tested.
 114
 115 At the end of each test, a set of verification functions is run to ensure
 116 that nothing was corrupted.
 117
 118 ---------
 119 The tests
 120
 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
 124 N3337.
 125
 126 The backbone of the testing framework is based on a small set of vector
 127 operations:
 128 -empty construction
 129 -copy construction (a little bit)
 130 -size
 131 -capacity
 132 -data
 133 -emplace_back
 134
 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.
 137
 138 */
 139 /*
 140
 141 THOUGHTS:
 142
 143 -Not all complexity checks are verified. These will be relentlessly hunted down
 144  in the benchmarking phase.
 145
 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.
 156
 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.
 160
 161 */
 162
 163 // include the vector first, to ensure its header is self-sufficient
 164 #ifdef USING_STD_VECTOR
 165 #include <vector>
 166 #define VECTOR_ std::vector
 167 #else
 168 #include <folly/FBVector.h>
 169 #define VECTOR_ folly::fbvector
 170 #endif
 171
 172 //#define USING_STD_VECTOR
 173
 174 #include <iostream>
 175 #include <sstream>
 176 #include <typeinfo>
 177 #include <type_traits>
 178 #include <map>
 179 #include <set>
 180 #include <string>
 181 #include <stdexcept>
 182 #include <exception>
 183 #include <climits>
 184 #include <cstddef>
 185 #include <iomanip>
 186
 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>
 193
 194 using namespace std;
 195 using namespace folly;
 196
 197 //=============================================================================
 198 //=============================================================================
 199 // Data type
 200
 201 //-----------------------------------------------------------------------------
 202 // Flags
 203
 204 typedef uint32_t Flags;
 205
 206 // each method has 3 options: normal, noexcept, throw, and deleted
 207 // normal is the default
 208 // throw is mutually exclusive with noexcept
 209 //
 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 {
 217   DC_NOEXCEPT = 0x1,
 218   DC_THROW    = 0x2,
 219   DC_DELETE   = 0x8000,
 220   CC_NOEXCEPT = 0x4,
 221   CC_THROW    = 0x8,
 222   CC_DELETE   = 0x10000,
 223   MC_NOEXCEPT = 0x10,
 224   MC_THROW    = 0x20,
 225   MC_DELETE   = 0x20000,
 226   OC_NOEXCEPT = 0x40,
 227   OC_THROW    = 0x80,
 228   // OC_DELETE - DNE
 229
 230   CA_NOEXCEPT = 0x100,
 231   CA_THROW    = 0x200,
 232   CA_DELETE   = 0x40000,
 233   MA_NOEXCEPT = 0x400,
 234   MA_THROW    = 0x800,
 235   MA_DELETE   = 0x80000,
 236
 237   ALL_DELETE  = DC_DELETE | CC_DELETE | MC_DELETE
 238               | CA_DELETE | MA_DELETE,
 239
 240   IS_RELOCATABLE
 241               = 0x2000,
 242
 243   // for the allocator
 244   PROP_COPY = 0x100000,
 245   PROP_MOVE = 0x200000,
 246   PROP_SWAP = 0x400000,
 247 };
 248
 249 //-----------------------------------------------------------------------------
 250 // Deletors
 251
 252 template <bool b> struct D0 {
 253   D0() = default;
 254   D0(const D0&) = default;
 255   D0(D0&&) = default;
 256   explicit D0(std::nullptr_t) {}
 257   D0& operator=(const D0&) = default;
 258   D0& operator=(D0&&) = default;
 259 };
 260 template <> struct D0<true> {
 261   D0() = delete;
 262   D0(const D0&) = default;
 263   D0(D0&&) = default;
 264   explicit D0(std::nullptr_t) {}
 265   D0& operator=(const D0&) = default;
 266   D0& operator=(D0&&) = default;
 267 };
 268
 269 template <bool b> struct D1 {
 270   D1() = default;
 271   D1(const D1&) = default;
 272   D1(D1&&) = default;
 273   explicit D1(std::nullptr_t) {}
 274   D1& operator=(const D1&) = default;
 275   D1& operator=(D1&&) = default;
 276 };
 277 template <> struct D1<true> {
 278   D1() = default;
 279   D1(const D1&) = delete;
 280   D1(D1&&) = default;
 281   explicit D1(std::nullptr_t) {}
 282   D1& operator=(const D1&) = default;
 283   D1& operator=(D1&&) = default;
 284 };
 285
 286 template <bool b> struct D2 {
 287   D2() = default;
 288   D2(const D2&) = default;
 289   D2(D2&&) = default;
 290   explicit D2(std::nullptr_t) {}
 291   D2& operator=(const D2&) = default;
 292   D2& operator=(D2&&) = default;
 293 };
 294 template <> struct D2<true> {
 295   D2() = default;
 296   D2(const D2&) = default;
 297   D2(D2&&) = delete;
 298   explicit D2(std::nullptr_t) {}
 299   D2& operator=(const D2&) = default;
 300   D2& operator=(D2&&) = default;
 301 };
 302
 303 template <bool b> struct D3 {
 304   D3() = default;
 305   D3(const D3&) = default;
 306   D3(D3&&) = default;
 307   explicit D3(std::nullptr_t) {}
 308   D3& operator=(const D3&) = default;
 309   D3& operator=(D3&&) = default;
 310 };
 311 template <> struct D3<true> {
 312   D3() = default;
 313   D3(const D3&) = default;
 314   D3(D3&&) = default;
 315   explicit D3(std::nullptr_t) {}
 316   D3& operator=(const D3&) = delete;
 317   D3& operator=(D3&&) = default;
 318 };
 319
 320 template <bool b> struct D4 {
 321   D4() = default;
 322   D4(const D4&) = default;
 323   D4(D4&&) = default;
 324   explicit D4(std::nullptr_t) {}
 325   D4& operator=(const D4&) = default;
 326   D4& operator=(D4&&) = default;
 327 };
 328 template <> struct D4<true> {
 329   D4() = default;
 330   D4(const D4&) = default;
 331   D4(D4&&) = default;
 332   explicit D4(std::nullptr_t) {}
 333   D4& operator=(const D4&) = default;
 334   D4& operator=(D4&&) = delete;
 335 };
 336
 337 template <Flags f>
 338 struct Delete : D0<f & DC_DELETE>
 339               , D1<f & CC_DELETE>
 340               , D2<f & MC_DELETE>
 341               , D3<f & CA_DELETE>
 342               , D4<f & MA_DELETE> {
 343   Delete() = default;
 344   Delete(const Delete&) = default;
 345   Delete(Delete&&) = default;
 346   Delete& operator=(const Delete&) = default;
 347   Delete& operator=(Delete&&) = default;
 348
 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)
 355       {}
 356 };
 357
 358 //-----------------------------------------------------------------------------
 359 // Ticker
 360
 361 struct TickException : std::runtime_error {
 362   explicit TickException(const std::string& s)
 363     : std::runtime_error("tick: " + s) {}
 364 };
 365
 366 struct Ticker {
 367   static int CountTicks;
 368   static int TicksLeft;
 369   static void Tick(const std::string& s) {
 370     if (TicksLeft == 0) throw TickException(s);
 371     CountTicks++;
 372     TicksLeft--;
 373   }
 374 };
 375
 376 int Ticker::CountTicks = 0;
 377 int Ticker::TicksLeft = -1;
 378
 379 template <Flags f>
 380 struct DataTicker : Ticker {
 381   DataTicker() noexcept(f & DC_NOEXCEPT) {
 382     if (!(f & DC_NOEXCEPT)) Tick("Data()");
 383   }
 384   DataTicker(const DataTicker&) noexcept(f & CC_NOEXCEPT) {
 385     if (!(f & CC_NOEXCEPT)) Tick("Data(const Data&)");
 386   }
 387   DataTicker(DataTicker&&) noexcept(f & MC_NOEXCEPT) {
 388     if (!(f & MC_NOEXCEPT)) Tick("Data(Data&&)");
 389   }
 390   explicit DataTicker(std::nullptr_t) noexcept(f & OC_NOEXCEPT) {
 391     if (!(f & OC_NOEXCEPT)) Tick("Data(int)");
 392   }
 393   ~DataTicker() noexcept {}
 394   void operator=(const DataTicker&) noexcept(f & CA_NOEXCEPT) {
 395     if (!(f & CA_NOEXCEPT)) Tick("op=(const Data&)");
 396   }
 397   void operator=(DataTicker&&) noexcept(f & MA_NOEXCEPT) {
 398     if (!(f & MA_NOEXCEPT)) Tick("op=(Data&&)");
 399   }
 400 };
 401
 402 //-----------------------------------------------------------------------------
 403 // Operation counter
 404
 405 struct Counter {
 406   static int CountDC, CountCC, CountMC, CountOC, CountCA, CountMA;
 407   static int CountDestroy, CountTotalOps, CountLoggedConstruction;
 408
 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++; }
 416 };
 417
 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;
 427
 428 //-----------------------------------------------------------------------------
 429 // Tracker
 430
 431 struct Tracker {
 432   static int UID;
 433   static std::map<int, int> UIDCount;
 434   static int UIDTotal;
 435   static std::map<const Tracker*, int> Locations;
 436   static bool Print;
 437
 438   Tracker* self;
 439   int uid;
 440
 441   Tracker(Tracker* self, int uid) : self(self), uid(uid) {}
 442 };
 443
 444 template <bool isRelocatable>
 445 struct DataTracker : Tracker {
 446   DataTracker() noexcept : Tracker(this, UID++) {
 447     UIDCount[uid]++;
 448     UIDTotal++;
 449     if (!isRelocatable) Locations[self] = uid;
 450     print("Data()");
 451   }
 452   DataTracker(const DataTracker& o) noexcept : Tracker(this, o.uid) {
 453     UIDCount[uid]++;
 454     UIDTotal++;
 455     if (!isRelocatable) Locations[self] = uid;
 456     print("Data(const Data&)");
 457   }
 458   DataTracker(DataTracker&& o) noexcept : Tracker(this, o.uid) {
 459     UIDCount[uid]++;
 460     UIDTotal++;
 461     if (!isRelocatable) Locations[self] = uid;
 462     print("Data(Data&&)");
 463   }
 464
 465   explicit DataTracker(int uid) noexcept : Tracker(this, uid) {
 466     UIDCount[uid]++;
 467     UIDTotal++;
 468     if (!isRelocatable) Locations[self] = uid;
 469     print("Data(int)");
 470   }
 471
 472   ~DataTracker() noexcept {
 473     UIDCount[uid]--;
 474     UIDTotal--;
 475     if (!isRelocatable) Locations.erase(self);
 476     print("~Data()");
 477     uid = 0xdeadbeef;
 478     self = (DataTracker*)0xfeebdaed;
 479   }
 480
 481   DataTracker& operator=(const DataTracker& o) noexcept {
 482     UIDCount[uid]--;
 483     uid = o.uid;
 484     UIDCount[uid]++;
 485     if (!isRelocatable) Locations[self] = uid;
 486     print("op=(const Data&)");
 487     return *this;
 488   }
 489   DataTracker& operator=(DataTracker&& o) noexcept {
 490     UIDCount[uid]--;
 491     uid = o.uid;
 492     UIDCount[uid]++;
 493     if (!isRelocatable) Locations[self] = uid;
 494     print("op=(Data&&)");
 495     return *this;
 496   }
 497
 498   void print(const std::string& fun) {
 499     if (Print) {
 500       std::cerr << std::setw(20) << fun << ": uid = " << std::setw(3) << uid;
 501       if (!isRelocatable) std::cerr << ", self = " << self;
 502       std::cerr << std::endl;
 503     }
 504   }
 505 };
 506
 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;
 512
 513 //-----------------------------------------------------------------------------
 514 //-----------------------------------------------------------------------------
 515 // Data
 516
 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];
 522
 523   Data() = default;
 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)
 529     , Delete<f>(nullptr)
 530   {}
 531   ~Data() = default;
 532   Data& operator=(const Data&) = default;
 533   Data& operator=(Data&&) = default;
 534
 535 private:
 536   int operator&() const;
 537 };
 538
 539 namespace folly {
 540 template <Flags f, size_t pad>
 541 struct IsRelocatable<Data<f, pad>>
 542   : std::integral_constant<bool,
 543       f & IS_RELOCATABLE
 544     > {};
 545 };
 546
 547 //-----------------------------------------------------------------------------
 548 //-----------------------------------------------------------------------------
 549 // Allocator
 550
 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> {};
 556
 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> {};
 562
 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> {};
 568
 569
 570 struct AllocTracker {
 571   static int Constructed;
 572   static int Destroyed;
 573   static map<void*, size_t> Allocated;
 574   static map<void*, int> Owner;
 575 };
 576 int AllocTracker::Constructed = 0;
 577 int AllocTracker::Destroyed = 0;
 578 map<void*, size_t> AllocTracker::Allocated;
 579 map<void*, int> AllocTracker::Owner;
 580
 581 template <class T>
 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;
 587
 588   //-----
 589   // impl
 590
 591   std::allocator<T> a;
 592   int id;
 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); }
 600
 601   //---------
 602   // tracking
 603
 604   pointer allocate(size_type n) {
 605     if (n == 0) {
 606       cerr << "called allocate(0)" << endl;
 607       throw runtime_error("allocate fail");
 608     }
 609     Tick("allocate");
 610     auto p = a.allocate(n);
 611     Allocated[p] = n;
 612     Owner[p] = id;
 613     return p;
 614   }
 615
 616   void deallocate(pointer p, size_type n) {
 617     if (p == nullptr) {
 618       cerr << "deallocate(nullptr, " << n << ")" << endl;
 619       FAIL() << "deallocate failed";
 620     }
 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] << ")";
 626       cerr << endl;
 627       FAIL() << "deallocate failed";
 628     }
 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";
 633     }
 634     Allocated[p] = -1;
 635     a.deallocate(p, n);
 636   }
 637
 638   template <class U, class... Args>
 639   void construct(U* p, Args&&... args) {
 640     Tick("construct");
 641     a.construct(p, std::forward<Args>(args)...);
 642     Constructed++;
 643   }
 644
 645   template <class U>
 646   void destroy(U* p) {
 647     Destroyed++;
 648     a.destroy(p);
 649   }
 650
 651   //--------------
 652   // container ops
 653
 654   Alloc select_on_container_copy_construction() const {
 655     Tick("select allocator for copy");
 656     return Alloc(id + 1);
 657   }
 658
 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;
 662 };
 663
 664 //=============================================================================
 665 //=============================================================================
 666 // Verification and resetting
 667
 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;
 677 }
 678
 679 void hardReset() {
 680   Tracker::UIDCount.clear();
 681   Tracker::UIDTotal = 0;
 682   Tracker::Locations.clear();
 683   softReset();
 684   Counter::CountLoggedConstruction = 0;
 685
 686   AllocTracker::Constructed = 0;
 687   AllocTracker::Destroyed = 0;
 688   AllocTracker::Allocated.clear();
 689   AllocTracker::Owner.clear();
 690 }
 691
 692 int getTotal() {
 693   int con = Counter::CountDC + Counter::CountCC
 694           + Counter::CountMC + Counter::CountOC
 695           + Counter::CountLoggedConstruction;
 696   int del = Counter::CountDestroy;
 697   return con - del;
 698 }
 699
 700 void isSane() {
 701   int tot = getTotal();
 702   ASSERT_GE(tot, 0) << "more objects deleted than constructed";
 703
 704   ASSERT_EQ(tot, Tracker::UIDTotal)
 705     << "UIDTotal has incorrect number of objects";
 706
 707   int altTot = 0;
 708   for (const auto& kv : Tracker::UIDCount) {
 709     ASSERT_TRUE(kv.second >= 0) << "there exists " << kv.second << " Data "
 710       "with uid " << kv.first;
 711     altTot += kv.second;
 712   }
 713   ASSERT_EQ(tot, altTot) << "UIDCount corrupted";
 714
 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";
 721     }
 722   }
 723 }
 724
 725 //-----------------------------------------------------------------------------
 726 // Traits
 727
 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
 733     > {};
 734
 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
 740     > {};
 741
 742 template <class Vector>
 743 struct customAllocator
 744   : std::integral_constant<bool,
 745       !is_same<
 746         typename Vector::allocator_type,
 747         std::allocator<typename Vector::value_type>
 748       >::value
 749     > {};
 750
 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 ||
 758       f & PROP_MOVE
 759     > {};
 760
 761 //=============================================================================
 762 //=============================================================================
 763 // Framework
 764
 765 //-----------------------------------------------------------------------------
 766 // Timing
 767
 768 uint64_t ReadTSC() {
 769    unsigned reslo, reshi;
 770
 771     __asm__ __volatile__  (
 772     "xorl %%eax,%%eax \n cpuid \n"
 773      ::: "%eax", "%ebx", "%ecx", "%edx");
 774     __asm__ __volatile__  (
 775     "rdtsc\n"
 776      : "=a" (reslo), "=d" (reshi) );
 777     __asm__ __volatile__  (
 778     "xorl %%eax,%%eax \n cpuid \n"
 779      ::: "%eax", "%ebx", "%ecx", "%edx");
 780
 781    return ((uint64_t)reshi << 32) | reslo;
 782 }
 783
 784 //-----------------------------------------------------------------------------
 785 // New Boost
 786
 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))
 799
 800 //-----------------------------------------------------------------------------
 801 // STL_TEST
 802
 803 #define GEN_TEST(r, name, type)                                   \
 804   {                                                               \
 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;               \
 811   }}}
 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;
 816
 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)
 821
 822 #define TYPIFY(r, d, name) BOOST_PP_CAT(TYPIFY_, name)
 823 #define ARGIFY(r, d, name) TYPIFY(r, d, name) name
 824
 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)                         \
 829     { SETUP {                                                            \
 830     BOOST_PP_SEQ_FOR_EACH(GEN_VMAKER, _, argseq)                         \
 831     {                                                                    \
 832     test_ ## name <Vector, typename Vector::value_type,                  \
 833       typename Vector::allocator_type> ( rawargs );                      \
 834     if (::testing::Test::HasFatalFailure()) return;                      \
 835     }                                                                    \
 836     BOOST_PP_SEQ_FOR_EACH(GEN_UMAKER, _, BOOST_PP_SEQ_REVERSE(argseq))   \
 837     } TEARDOWN }                                                         \
 838     BOOST_PP_SEQ_FOR_EACH(GEN_CLOSER, _, BOOST_PP_SEQ_REVERSE(argseq))   \
 839   }                                                                      \
 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        \
 844       >());                                                              \
 845   }                                                                      \
 846                                                                          \
 847   template <class Vector> bool test_I_ ## name ## 2 (std::false_type)    \
 848     { return false; }                                                    \
 849   template <class Vector> bool test_I_ ## name ## 2 (std::true_type) {   \
 850     return true;                                                         \
 851     auto f = test_ ## name <Vector,                                      \
 852       typename Vector::value_type, typename Vector::allocator_type>;     \
 853     return true;                                                         \
 854   }                                                                      \
 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>());               \
 858     return false;                                                        \
 859   }                                                                      \
 860                                                                          \
 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)          \
 865     bool one = false;                                                    \
 866     BOOST_PP_SEQ_FOR_EACH(GEN_RUNNABLE_TEST, name, types)                \
 867     if (!one) FAIL() << "No tests qualified to run";                     \
 868   }
 869
 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))))
 874
 875 #define STL_TEST_I(ref, name, restriction, args...)                           \
 876   DECL(name, args);                                                           \
 877   MAKE_TEST(ref, name, TEST_TYPES, restriction,                               \
 878     IBOOST_PP_VARIADIC_TO_SEQ(args), args)                                    \
 879   DECL(name, args)
 880
 881 #define STL_TEST(ref, name, restriction, args...) \
 882   STL_TEST_I(ref, name, restriction, z, ## args, ticks)
 883
 884 //-----------------------------------------------------------------------------
 885 // Test Types
 886
 887 typedef Data<> ED1;
 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;
 892
 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;
 901
 902 typedef Data<PROP_COPY> EP1;
 903 typedef Data<PROP_MOVE> EP2;
 904 typedef Data<PROP_SWAP> EP3;
 905
 906 typedef VECTOR_<EP1, Alloc<EP1>> _TP1;
 907 typedef VECTOR_<EP2, Alloc<EP2>> _TP2;
 908 typedef VECTOR_<EP3, Alloc<EP3>> _TP3;
 909
 910 #define TEST_TYPES (_TVIS)(_TVI)(_TV1)(_TV2)(_TV3)(_TV4)(_TV5v1)(_TV5) \
 911   (_TP1)(_TP2)(_TP3)
 912
 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
 920
 921 typedef Data<ALL_DELETE | PROP_MOVE> DDSMA;
 922 typedef VECTOR_<DDSMA, Alloc<DDSMA>> _TSpecialMA;
 923
 924 #define INTERFACE_TYPES \
 925   (_TVI)(VECTOR_<DD1>)(VECTOR_<DD2>)(VECTOR_<DD3>) \
 926   (VECTOR_<DD4>)(VECTOR_<DD5>)(VECTOR_<DD6>) \
 927   (VECTOR_<DD7>)(_TSpecialMA)
 928
 929 //-----------------------------------------------------------------------------
 930 // Pretty printers
 931
 932 template <typename T>
 933 struct PrettyType {
 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();
 939   }
 940 };
 941
 942 template <Flags f, size_t pad>
 943 struct PrettyType<Data<f, pad>> {
 944   string operator()() {
 945     stringstream tpe;
 946     tpe << "Data";
 947
 948     if ((f & DC_DELETE) ||
 949         (f & CC_DELETE) ||
 950         (f & MC_DELETE) ||
 951         (f & CA_DELETE) ||
 952         (f & MA_DELETE)) {
 953       tpe << "[^";
 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,";
 959       tpe << "]";
 960     }
 961
 962     if ((f & DC_NOEXCEPT) ||
 963         (f & CC_NOEXCEPT) ||
 964         (f & MC_NOEXCEPT) ||
 965         (f & CA_NOEXCEPT) ||
 966         (f & MA_NOEXCEPT)) {
 967       tpe << "[safe";
 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,";
 973       tpe << "]";
 974     }
 975
 976     if (f & IS_RELOCATABLE) {
 977       tpe << "(relocatable)";
 978     }
 979
 980     if (pad != 0) {
 981       tpe << "{pad " << pad << "}";
 982     }
 983
 984     return tpe.str();
 985   }
 986 };
 987
 988 template <typename T>
 989 struct PrettyType<std::allocator<T>> {
 990   string operator()() {
 991     return "std::allocator<" + PrettyType<T>()() + ">";
 992   }
 993 };
 994
 995 template <typename T>
 996 struct PrettyType<Alloc<T>> {
 997   string operator()() {
 998     return "Alloc<" + PrettyType<T>()() + ">";
 999   }
1000 };
1001
1002 //-----------------------------------------------------------------------------
1003 // Setup, teardown, runup, rundown
1004
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
1008 // cleanup.
1009
1010 #define SETUP hardReset();
1011 #define TEARDOWN
1012
1013 //-----------------------------------------------------------------------------
1014 // Types and typegens
1015
1016 //------
1017 // dummy
1018
1019 #define TYPIFY_z std::nullptr_t
1020 #define LOOPER_z                                 \
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;
1024 #define UMAKER_z                                                      \
1025   verify<Vector>(0);                                                  \
1026   if (::testing::Test::HasFatalFailure()) return;
1027 #define CLOSER_z
1028
1029 //------
1030 // ticks
1031
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;
1037
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");                   \
1047     VERIFICATION }                                          \
1048   try {                                                     \
1049     softReset(ticks);
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(); }                      \
1054   catch (...)                                                     \
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";                 \
1060   VERIFICATION
1061 #define CLOSER_ticks }
1062
1063
1064 //--------------------------------------------------
1065 // vectors (second could be .equal, ==, or distinct)
1066
1067 static const vector<pair<int, int>> VectorSizes = {
1068   {  0, -1},
1069   {  1, -1},
1070   {  2, -1},
1071   { 10, -1}, { 10, 1}, { 10, 0},
1072   {100, -1}, {100, 1},
1073
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},
1077   //  { 1000, 1000},
1078 };
1079
1080 int populateIndex = 1426;
1081 template <class Vector>
1082 void populate(Vector& v, const pair<int, int>& ss) {
1083   int i = 0;
1084   for (; i < ss.first; ++i) {
1085     v.emplace_back(populateIndex++);
1086   }
1087   if (ss.second >= 0) {
1088     while (v.capacity() - v.size() != ss.second) {
1089       v.emplace_back(populateIndex++);
1090     }
1091   }
1092 }
1093
1094 template <typename A>
1095 struct allocGen {
1096   static A get() { return A(); }
1097 };
1098 template <typename T>
1099 struct allocGen<Alloc<T>> {
1100   static Alloc<T> get() {
1101     static int c = 0;
1102     c += 854;
1103     return Alloc<T>(c);
1104   }
1105 };
1106
1107 #define TYPIFY_a Vector&
1108 #define LOOPER_a for (const auto& a_ss : VectorSizes) {
1109 #define VMAKER_a                                                            \
1110   Vector a(allocGen<typename Vector::allocator_type>::get());               \
1111   a_p = &a;                                                                 \
1112   populate(*a_p, a_ss);                                                     \
1113   string a_st = folly::to<string>("a (", a.size(), "/", a.capacity(), ")"); \
1114   SCOPED_TRACE(a_st);
1115 #define UMAKER_a verify(0, a); if (::testing::Test::HasFatalFailure()) return;
1116 #define CLOSER_a }
1117
1118 #define TYPIFY_b Vector&
1119 #define LOOPER_b for (int b_i = -2; b_i < (int)VectorSizes.size(); ++b_i) {
1120 #define VMAKER_b                                                            \
1121   Vector b_s(allocGen<typename Vector::allocator_type>::get());             \
1122   b_p = &b_s; string b_st;                                                  \
1123   if (b_i == -2) {                                                          \
1124     b_p = &a;                                                               \
1125     b_st = "b is an alias of a";                                            \
1126   }                                                                         \
1127   else if (b_i == -1) {                                                     \
1128     b_s.~Vector();                                                          \
1129     new (&b_s) Vector(a);                                                   \
1130     b_st = "b is a deep copy of a";                                         \
1131   }                                                                         \
1132   else {                                                                    \
1133     populate(b_s, VectorSizes[b_i]);                                        \
1134     b_st = folly::to<string>("b (", b_s.size(), "/", b_s.capacity(), ")");  \
1135   }                                                                         \
1136   Vector& b = *b_p;                                                         \
1137   SCOPED_TRACE(b_st);
1138 #define UMAKER_b \
1139   verify(0, a, b); if (::testing::Test::HasFatalFailure()) return;
1140 #define CLOSER_b }
1141
1142 //----
1143 // int
1144
1145 static const vector<int> nSizes = { 0, 1, 2, 9, 10, 11 };
1146
1147 #define TYPIFY_n int
1148 #define LOOPER_n for (int n : nSizes) {
1149 #define VMAKER_n \
1150   string n_st = folly::to<string>("n = ", n); SCOPED_TRACE(n_st);
1151 #define UMAKER_n
1152 #define CLOSER_n }
1153
1154 //-----------------------
1155 // non-internal iterators
1156
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 };
1159
1160 #define TYPIFY_i int*
1161 #define LOOPER_i
1162 #define VMAKER_i int* i = ijarr; SCOPED_TRACE("i = fib[0]");
1163 #define UMAKER_i
1164 #define CLOSER_i
1165
1166 #define TYPIFY_j int*
1167 #define LOOPER_j for (int j_i = 0; j_i < 12; ++j_i) {
1168 #define VMAKER_j                                          \
1169   int* j = ijarr + j_i;                                   \
1170   string j_st = folly::to<string>("j = fib[", j_i, "]");  \
1171   SCOPED_TRACE(j_st);
1172 #define UMAKER_j \
1173   for (int j_c = 0; j_c < 12; ++j_c) ASSERT_EQ(ijarC[j_c], ijarr[j_c]);
1174 #define CLOSER_j }
1175
1176 //-------------------
1177 // internal iterators
1178
1179 template <class Vector>
1180 std::pair<typename Vector::iterator, string>
1181 iterSpotter(Vector& v, int i) {
1182   typename Vector::iterator it;
1183   string msg;
1184
1185   switch(i) {
1186   case 1:
1187     if (v.empty()) ; // fall through
1188     else {
1189       it = v.begin();
1190       ++it;
1191       msg = "a[1]";
1192       break;
1193     }
1194   case 0:
1195     it = v.begin();
1196     msg = "a.begin";
1197     break;
1198
1199   case 2:
1200     if (v.empty()) ; // fall through
1201     else {
1202       it = v.end();
1203       --it;
1204       msg = "a[-1]";
1205       break;
1206     }
1207   case 3:
1208     it = v.end();
1209     msg = "a.end";
1210     break;
1211
1212   default:
1213     cerr << "internal error" << endl;
1214     exit(1);
1215   }
1216
1217   return make_pair(it, msg);
1218 }
1219
1220 #define TYPIFY_p typename Vector::iterator
1221 #define LOOPER_p for (int p_i = 0; p_i < 4; ++p_i) {
1222 #define VMAKER_p                    \
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);
1227 #define UMAKER_p
1228 #define CLOSER_p }
1229
1230 #define TYPIFY_q typename Vector::iterator
1231 #define LOOPER_q for (int q_i = p_i; q_i < 4; ++q_i) {
1232 #define VMAKER_q                    \
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);
1237 #define UMAKER_q
1238 #define CLOSER_q }
1239
1240 //---------
1241 // datatype
1242
1243 static const vector<int> tVals = { 0, 1, 2, 3, 17, 66, 521 };
1244
1245 #define TYPIFY_t typename Vector::value_type&
1246 #define LOOPER_t for (int t_v : tVals) {
1247 #define VMAKER_t                                                            \
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;                                         \
1256     }                                                                       \
1257   }                                                                         \
1258   typename Vector::value_type& t = *t_p;                                    \
1259   SCOPED_TRACE(t_st);
1260 #define UMAKER_t
1261 #define CLOSER_t }
1262
1263 //----------
1264 // allocator
1265
1266 #define TYPIFY_m typename Vector::allocator_type
1267 #define LOOPER_m                          \
1268   int m_max = 1 + (a_p != nullptr);       \
1269   for (int m_i = 0; m_i < m_max; ++m_i) {
1270 #define VMAKER_m                                \
1271   typename Vector::allocator_type m = m_i == 0  \
1272     ? typename Vector::allocator_type()         \
1273     : a_p->get_allocator();
1274 #define UMAKER_m
1275 #define CLOSER_m }
1276
1277 //-----------------------------------------------------------------------------
1278 // Verifiers
1279
1280 // verify a vector
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";
1292 }
1293
1294 void verifyAllocator(int ele, int cap) {
1295   ASSERT_EQ(ele, AllocTracker::Constructed - AllocTracker::Destroyed);
1296
1297   int tot = 0;
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;
1302 }
1303
1304 // Master verifier
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";
1309   isSane();
1310   if (::testing::Test::HasFatalFailure()) return;
1311   if (customAllocator<Vector>::value) verifyAllocator(0, 0);
1312 }
1313 template <class Vector>
1314 void verify(int extras, const Vector& v) {
1315   verifyVector(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";
1319   isSane();
1320   if (::testing::Test::HasFatalFailure()) return;
1321   if (customAllocator<Vector>::value) verifyAllocator(v.size(), v.capacity());
1322 }
1323 template <class Vector>
1324 void verify(int extras, const Vector& v1, const Vector& v2) {
1325   verifyVector(v1);
1326   verifyVector(v2);
1327   auto size = v1.size();
1328   auto cap = v1.capacity();
1329   if (&v1 != &v2) {
1330     size += v2.size();
1331     cap += v2.capacity();
1332   }
1333   if (!is_arithmetic<typename Vector::value_type>::value)
1334     ASSERT_EQ(size + extras, getTotal()) << "not all Data are in the vector(s)";
1335   isSane();
1336   if (::testing::Test::HasFatalFailure()) return;
1337   if (customAllocator<Vector>::value) verifyAllocator(size, cap);
1338 }
1339
1340 //=============================================================================
1341 // Helpers
1342
1343 // save the state of a vector
1344 int convertToInt(int t) {
1345   return t;
1346 }
1347 template <Flags f, size_t pad>
1348 int convertToInt(const Data<f, pad>& t) {
1349   return t.uid;
1350 }
1351 template <typename T>
1352 int convertToInt(const std::allocator<T>&) {
1353   return -1;
1354 }
1355 template <typename T>
1356 int convertToInt(const Alloc<T>& a) {
1357   return a.id;
1358 }
1359
1360 template <class Vector>
1361 class DataState {
1362   typedef typename Vector::size_type size_type;
1363   size_type size_;
1364   int* data_;
1365 public:
1366   /* implicit */ DataState(const Vector& v) {
1367     size_ = v.size();
1368     if (size_ != 0) {
1369       data_ = new int[size_];
1370       for (size_type i = 0; i < size_; ++i) {
1371         data_[i] = convertToInt(v.data()[i]);
1372       }
1373     } else {
1374       data_ = nullptr;
1375     }
1376   }
1377   ~DataState() {
1378     delete[] data_;
1379   }
1380
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;
1385     }
1386     return true;
1387   }
1388
1389   int operator[](size_type i) {
1390     if (i >= size_) {
1391       cerr << "trying to access DataState out of bounds" << endl;
1392       exit(1);
1393     }
1394     return data_[i];
1395   }
1396
1397   size_type size() { return size_; }
1398 };
1399
1400 // downgrade iterators
1401 template <typename It, class tag>
1402 class Transformer : public boost::iterator_adaptor<
1403                             Transformer<It, tag>,
1404                             It,
1405                             typename iterator_traits<It>::value_type,
1406                             tag
1407                            > {
1408   friend class boost::iterator_core_access;
1409   shared_ptr<set<It>> dereferenced;
1410
1411 public:
1412   explicit Transformer(const It& it)
1413     : Transformer::iterator_adaptor_(it)
1414     , dereferenced(new set<It>()) {}
1415
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;
1419       exit(1);
1420     }
1421     dereferenced->insert(this->base_reference());
1422     return *this->base_reference();
1423   }
1424 };
1425
1426 template <typename It>
1427 Transformer<It, forward_iterator_tag> makeForwardIterator(const It& it) {
1428   return Transformer<It, forward_iterator_tag>(it);
1429 }
1430 template <typename It>
1431 Transformer<It, input_iterator_tag> makeInputIterator(const It& it) {
1432   return Transformer<It, input_iterator_tag>(it);
1433 }
1434
1435 // mutate a value (in contract only)
1436 void mutate(int& i) {
1437   if (false) i = 0;
1438 }
1439 void mutate(uint64_t& i) {
1440   if (false) i = 0;
1441 }
1442 template <Flags f, size_t pad>
1443 void mutate(Data<f, pad>& ds) {
1444   if (false) ds.uid = 0;
1445 }
1446
1447 //=============================================================================
1448 // Tests
1449
1450 // #if 0
1451
1452
1453
1454 // #else
1455
1456 //-----------------------------------------------------------------------------
1457 // Container
1458
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");
1500 }
1501
1502 STL_TEST("23.2.1 Table 96.8-9", emptyConstruction, is_destructible) {
1503   Vector u;
1504
1505   ASSERT_TRUE(u.get_allocator() == Allocator());
1506   ASSERT_EQ(0, Counter::CountTotalOps);
1507
1508   ASSERT_TRUE(u.empty()) << u.size();
1509   ASSERT_EQ(0, u.capacity());
1510
1511   if (false) {
1512     Vector();
1513   }
1514 }
1515
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.
1519
1520   Vector u;
1521   ASSERT_EQ(0, u.size());
1522   ASSERT_EQ(nullptr, u.data());
1523
1524   u.emplace_back(17);
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";
1531
1532   for (int i = 0; i < 3; ++i) {
1533     auto cap = u.capacity();
1534     while (u.size() < cap) {
1535       u.emplace_back(22);
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";
1539     }
1540
1541     ASSERT_EQ(cap, u.size());
1542
1543     u.emplace_back(4);
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";
1548   }
1549 }
1550
1551 STL_TEST("23.2.1 Table 96.10-11", copyConstruction,
1552           is_copy_constructible, a) {
1553   const auto& ca = a;
1554   DataState<Vector> dsa(ca);
1555   auto am = a.get_allocator();
1556
1557   Vector u(ca);
1558
1559   ASSERT_TRUE(std::allocator_traits<Allocator>::
1560     select_on_container_copy_construction(am) == u.get_allocator());
1561   ASSERT_TRUE(dsa == u);
1562   ASSERT_TRUE(
1563     (ca.data() == nullptr && u.data() == nullptr) ||
1564     (ca.data() != u.data())
1565   ) << "only a shallow copy was made";
1566
1567   if (false) {
1568     Vector(ca);
1569     Vector u = ca;
1570   }
1571 }
1572
1573 STL_TEST("23.2.1 Table 96.12", moveConstruction, is_destructible, a) {
1574   DataState<Vector> dsa(a);
1575   auto m = a.get_allocator();
1576
1577   Vector u(move(a));
1578
1579   ASSERT_TRUE(m == u.get_allocator());
1580   ASSERT_EQ(0, Counter::CountTotalOps);
1581
1582   ASSERT_TRUE(dsa == u);
1583
1584   if (false) {
1585     Vector u = move(a);
1586   }
1587 }
1588
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();
1593
1594   Vector& ret = a = std::move(b);
1595
1596   if (std::allocator_traits<Allocator>::
1597       propagate_on_container_move_assignment::value) {
1598     ASSERT_TRUE(bm == a.get_allocator());
1599   } else {
1600     ASSERT_TRUE(am == a.get_allocator());
1601   }
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.
1605 }
1606
1607 STL_TEST("23.2.1 Table 96.14", destructible, is_destructible) {
1608   // The test generators check this clause already.
1609 }
1610
1611 STL_TEST("23.2.1 Table 96.15-18", iterators, is_destructible, a) {
1612   DataState<Vector> dsa(a);
1613   const auto& ca = a;
1614
1615   auto  itb =  a.begin();
1616   auto citb = ca.begin();
1617   auto Citb =  a.cbegin();
1618   auto  ite =  a.end();
1619   auto cite = ca.end();
1620   auto Cite =  a.cend();
1621
1622   ASSERT_EQ(0, Counter::CountTotalOps);
1623
1624   ASSERT_TRUE(dsa == a) << "call to begin or end modified internal data";
1625
1626   ASSERT_TRUE(citb == Citb) << "cv.begin != v.cbegin";
1627   ASSERT_TRUE(cite == Cite) << "cv.end != v.cend";
1628
1629   if (ca.size() == 0) {
1630     ASSERT_TRUE( itb ==  ite) << "begin != end when empty";
1631     ASSERT_TRUE(Citb == Cite) << "cbegin != cend when empty";
1632   } else {
1633     ASSERT_TRUE( itb !=  ite) << "begin == end when non-empty";
1634     ASSERT_TRUE(Citb != Cite) << "cbegin == cend when non-empty";
1635   }
1636
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";
1641 }
1642
1643 STL_TEST("23.2.1 Table 96.19-20", equitable, is_arithmetic, a, b) {
1644   const auto& ca = a;
1645   const auto& cb = b;
1646   DataState<Vector> dsa(a);
1647   DataState<Vector> dsb(b);
1648
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 ==";
1653
1654   // Data is uncomparable, by design; therefore this test's restriction
1655   // is 'is_arithmetic'
1656 }
1657
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
1663     return;
1664   }
1665
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();
1672
1673   try {
1674     a.swap(b);
1675   } catch (...) {
1676     FAIL() << "swap is noexcept";
1677   }
1678
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());
1683   } else {
1684     ASSERT_TRUE(am == a.get_allocator());
1685     ASSERT_TRUE(bm == b.get_allocator());
1686   }
1687   ASSERT_EQ(0, Counter::CountTotalOps);
1688
1689   ASSERT_TRUE(adata == b.data() && bdata == a.data());
1690   ASSERT_TRUE(dsa == b && dsb == a) << "swap did not swap";
1691 }
1692
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
1699     return;
1700   }
1701
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();
1708
1709   try {
1710     swap(a, b);
1711   } catch (...) {
1712     FAIL() << "swap is noexcept";
1713   }
1714
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());
1719   } else {
1720     ASSERT_TRUE(am == a.get_allocator());
1721     ASSERT_TRUE(bm == b.get_allocator());
1722   }
1723   ASSERT_EQ(0, Counter::CountTotalOps);
1724
1725   ASSERT_TRUE(adata == b.data() && bdata == a.data());
1726   ASSERT_TRUE(dsa == b && dsb == a) << "swap did not swap";
1727 }
1728
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.
1732
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.
1739     return;
1740   }
1741   #endif
1742
1743   const auto& cb = b;
1744   DataState<Vector> dsb(cb);
1745   auto am = a.get_allocator();
1746   auto bm = b.get_allocator();
1747
1748   Vector& ret = a = cb;
1749
1750   if (std::allocator_traits<Allocator>::
1751       propagate_on_container_copy_assignment::value) {
1752     ASSERT_TRUE(bm == a.get_allocator());
1753   } else {
1754     ASSERT_TRUE(am == a.get_allocator());
1755   }
1756   ASSERT_TRUE(&ret == &a);
1757   ASSERT_TRUE(dsb == a) << "copy-assign not equal to original";
1758 }
1759
1760 STL_TEST("23.2.1 Table 96.24-26", sizeops, is_destructible) {
1761   // This check generators check this clause already.
1762 }
1763
1764 //-----------------------------------------------------------------------------
1765 // Reversible container
1766
1767 STL_TEST("23.2.1 Table 97.1-2", reversibleContainerTypedefs,
1768           is_destructible) {
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");
1776 }
1777
1778 STL_TEST("23.2.1 Table 97.3-5", reversibleIterators, is_destructible, a) {
1779   const auto& ca = a;
1780   DataState<Vector> ds(a);
1781
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();
1788
1789   ASSERT_EQ(0, Counter::CountTotalOps);
1790
1791   ASSERT_TRUE(ds == a) << "call to rbegin or rend modified internal data";
1792
1793   ASSERT_TRUE(critb == Critb) << "cv.rbegin != v.crbegin";
1794   ASSERT_TRUE(crite == Crite) << "cv.rend != v.crend";
1795
1796   if (ca.size() == 0) {
1797     ASSERT_TRUE( ritb ==  rite) << "rbegin != rend when empty";
1798     ASSERT_TRUE(Critb == Crite) << "crbegin != crend when empty";
1799   } else {
1800     ASSERT_TRUE( ritb !=  rite) << "rbegin == rend when non-empty";
1801     ASSERT_TRUE(Critb != Crite) << "crbegin == crend when non-empty";
1802   }
1803
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";
1808 }
1809
1810 //-----------------------------------------------------------------------------
1811 // Lexicographical functions
1812
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 };
1820
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);
1827 }
1828
1829 //-----------------------------------------------------------------------------
1830 // Allocator-aware requirements (AA)
1831
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");
1835 }
1836
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
1839 }
1840
1841 STL_TEST("23.2.1 Table 99.3", defaultAllocator, is_destructible) {
1842   // there is nothing new to test here
1843 }
1844
1845 STL_TEST("23.2.1 Table 99.4", customAllocator, is_destructible, m) {
1846   const auto& cm = m;
1847
1848   Vector u(cm);
1849
1850   ASSERT_TRUE(u.get_allocator() == m);
1851
1852   if (false) {
1853     Vector(m);
1854   }
1855 }
1856
1857 STL_TEST("23.2.1 Table 99.5", copyWithAllocator, is_copy_constructible, a, m) {
1858   DataState<Vector> dsa(a);
1859   const auto& ca = a;
1860   const auto& cm = m;
1861
1862   Vector u(ca, cm);
1863
1864   ASSERT_TRUE(u.get_allocator() == m);
1865   ASSERT_TRUE(dsa == u);
1866   ASSERT_TRUE(
1867     (ca.data() == nullptr && u.data() == nullptr) ||
1868     (ca.data() != u.data())
1869   ) << "only a shallow copy was made";
1870 }
1871
1872 STL_TEST("23.2.1 Table 99.6", moveConstructionWithAllocator,
1873          is_destructible, a) {
1874   // there is nothing new to test here
1875 }
1876
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;
1882   const auto& cm = m;
1883
1884   Vector u(std::move(a), cm);
1885
1886   ASSERT_TRUE(u.get_allocator() == m);
1887
1888   if (deep) {
1889     if (!AllocTracker::Allocated.empty()) {
1890       ASSERT_EQ(osize, AllocTracker::Constructed - oalloc);
1891     }
1892   } else {
1893     ASSERT_EQ(0, Counter::CountTotalOps);
1894   }
1895 }
1896
1897 STL_TEST("23.2.1 Table 99.7-9", allocAssign, is_destructible) {
1898   // there is nothing new to test here
1899 }
1900
1901 STL_TEST("23.2.1-7", nAllocConstruction, is_copy_constructible, n, m) {
1902   #ifndef USING_STD_VECTOR
1903   const auto& cm = m;
1904
1905   Vector u(n, cm);
1906
1907   ASSERT_TRUE(m == u.get_allocator());
1908   #endif
1909 }
1910
1911 STL_TEST("23.2.1-7", nCopyAllocConstruction, is_copy_constructible, n, t, m) {
1912   const auto& cm = m;
1913   const auto& ct = t;
1914
1915   Vector u(n, ct, cm);
1916
1917   ASSERT_TRUE(m == u.get_allocator());
1918 }
1919
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;
1926   const auto& cm = m;
1927
1928   Vector u(cfi, cfj, cm);
1929
1930   ASSERT_TRUE(m == u.get_allocator());
1931 }
1932
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;
1937   #endif
1938
1939   auto ii = makeInputIterator(i);
1940   auto ij = makeInputIterator(j);
1941   const auto& cii = ii;
1942   const auto& cij = ij;
1943   const auto& cm = m;
1944
1945   Vector u(cii, cij, cm);
1946
1947   ASSERT_TRUE(m == u.get_allocator());
1948 }
1949
1950 STL_TEST("23.2.1-7", ilAllocConstruction, is_arithmetic, m) {
1951   // gcc fail
1952   if (Ticker::TicksLeft >= 0) return;
1953
1954   const auto& cm = m;
1955
1956   Vector u({ 1, 4, 7 }, cm);
1957
1958   ASSERT_TRUE(m == u.get_allocator());
1959 }
1960
1961 //-----------------------------------------------------------------------------
1962 // Data races
1963
1964 STL_TEST("23.2.2", dataRaces, is_destructible) {
1965   if (false) {
1966     const Vector* cv = nullptr;
1967     typename Vector::size_type* s = nullptr;
1968
1969     cv->begin();
1970     cv->end();
1971     cv->rbegin();
1972     cv->rend();
1973     cv->front();
1974     cv->back();
1975     cv->data();
1976
1977     (*cv).at(*s);
1978     (*cv)[*s];
1979   }
1980
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
1983 }
1984
1985 //-----------------------------------------------------------------------------
1986 // Sequence container
1987
1988 STL_TEST("23.2.3 Table 100.1, alt", nConstruction, is_constructible, n) {
1989   Vector u(n);
1990
1991   ASSERT_TRUE(Allocator() == u.get_allocator());
1992   ASSERT_EQ(n, u.size());
1993   ASSERT_EQ(Counter::CountTotalOps, Counter::CountDC);
1994 }
1995
1996 STL_TEST("23.2.3 Table 100.1", nCopyConstruction,
1997          is_copy_constructible, n, t) {
1998   const auto& ct = t;
1999
2000   Vector u(n, ct);
2001
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";
2006 }
2007
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
2011   // is_destructible
2012
2013   auto fi = makeForwardIterator(i);
2014   auto fj = makeForwardIterator(j);
2015   const auto& cfi = fi;
2016   const auto& cfj = fj;
2017
2018   Vector u(cfi, cfj);
2019
2020   ASSERT_TRUE(Allocator() == u.get_allocator());
2021   ASSERT_LE(Counter::CountTotalOps, j-i);
2022
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";
2026 }
2027
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;
2032   #endif
2033
2034   auto ii = makeInputIterator(i);
2035   auto ij = makeInputIterator(j);
2036   const auto& cii = ii;
2037   const auto& cij = ij;
2038
2039   Vector u(cii, cij);
2040
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";
2045 }
2046
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())
2050
2051   // gcc fail
2052   if (Ticker::TicksLeft >= 0) return;
2053
2054   Vector u = { 1, 4, 7 };
2055
2056   ASSERT_TRUE(Allocator() == u.get_allocator());
2057   ASSERT_EQ(3, u.size()) << "u(il).size() fail";
2058   int i = 1;
2059   auto it = u.begin();
2060   for (; it != u.end(); ++it, i += 3)
2061     ASSERT_EQ(i, convertToInt(*it)) << "u(il) constructed incorrectly";
2062 }
2063
2064 STL_TEST("23.2.3 Table 100.4", ilAssignment,
2065          is_arithmetic, a) {
2066   // whitebox: ensure that assign(il) is implemented in terms of
2067   // assign(il.begin(), il.end())
2068
2069   // gcc fail
2070   if (Ticker::TicksLeft >= 0) return;
2071
2072   auto am = a.get_allocator();
2073
2074   Vector& b = a = { 1, 4, 7 };
2075
2076   ASSERT_TRUE(am == a.get_allocator());
2077   ASSERT_TRUE(&b == &a) << "'a = ...' did not return *this";
2078
2079   ASSERT_EQ(3, a.size()) << "u(il).size() fail";
2080   int i = 1;
2081   auto it = a.begin();
2082   for (; it != a.end(); ++it, i += 3)
2083     ASSERT_EQ(i, convertToInt(*it)) << "u(il) constructed incorrectly";
2084 }
2085
2086 //----------------------------
2087 // insert-and-erase subsection
2088
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());
2093   int i = 0;
2094   for (; i < idx; ++i) {
2095     ASSERT_EQ(dsa[i], convertToInt(a.data()[i])) << i;
2096   }
2097   for (; i < idx + n; ++i) {
2098     ASSERT_EQ(val, convertToInt(a.data()[i])) << i;
2099   }
2100   for (; i < a.size(); ++i) {
2101     ASSERT_EQ(dsa[i-n], convertToInt(a.data()[i])) << i;
2102   }
2103 }
2104
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();
2110
2111   auto q = a.emplace(p, 44);
2112
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);
2116 }
2117
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();
2124   const auto& ct = t;
2125
2126   auto q = a.insert(p, ct);
2127
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);
2131 }
2132
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;
2137
2138   DataState<Vector> dsa(a);
2139   int idx = distance(a.begin(), p);
2140   int tval = convertToInt(t);
2141   auto am = a.get_allocator();
2142
2143   auto q = a.insert(p, std::move(t));
2144
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);
2148 }
2149
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();
2156   const auto& ct = t;
2157
2158   #ifndef USING_STD_VECTOR
2159   auto q =
2160   #endif
2161
2162   a.insert(p, n, ct);
2163
2164   ASSERT_TRUE(am == a.get_allocator());
2165   #ifndef USING_STD_VECTOR
2166   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2167   #endif
2168
2169   insertNTCheck(a, dsa, idx, n, tval);
2170 }
2171
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());
2176   int i = 0;
2177   for (; i < idx; ++i) {
2178     ASSERT_EQ(dsa[i], convertToInt(a.data()[i]));
2179   }
2180   for (; i < idx + (e - b); ++i) {
2181     ASSERT_EQ(*(b + i - idx), convertToInt(a.data()[i]));
2182   }
2183   for (; i < a.size(); ++i) {
2184     ASSERT_EQ(dsa[i - (e - b)], convertToInt(a.data()[i]));
2185   }
2186 }
2187
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);
2192
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;
2198
2199   #ifndef USING_STD_VECTOR
2200   auto q =
2201   #endif
2202
2203   a.insert(p, cfi, cfj);
2204
2205   ASSERT_TRUE(am == a.get_allocator());
2206   #ifndef USING_STD_VECTOR
2207   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2208   #endif
2209
2210   insertItCheck(a, dsa, idx, i, j);
2211 }
2212
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);
2217
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;
2223
2224   #ifndef USING_STD_VECTOR
2225   auto q =
2226   #endif
2227
2228   a.insert(p, cii, cij);
2229
2230   ASSERT_TRUE(am == a.get_allocator());
2231   #ifndef USING_STD_VECTOR
2232   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2233   #endif
2234
2235   insertItCheck(a, dsa, idx, i, j);
2236 }
2237
2238 STL_TEST("23.2.3 Table 100.10", iteratorInsertIL,
2239          is_arithmetic, a, p) {
2240   // gcc fail
2241   if (Ticker::TicksLeft >= 0) return;
2242
2243   // whitebox: ensure that insert(p, il) is implemented in terms of
2244   // insert(p, il.begin(), il.end())
2245
2246   DataState<Vector> dsa(a);
2247   int idx = distance(a.begin(), p);
2248   auto am = a.get_allocator();
2249
2250   #ifndef USING_STD_VECTOR
2251   auto q =
2252   #endif
2253
2254   a.insert(p, {1, 4, 7});
2255
2256   ASSERT_TRUE(am == a.get_allocator());
2257   #ifndef USING_STD_VECTOR
2258   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2259   #endif
2260
2261   int ila[] = { 1, 4, 7 };
2262   int* i = ila;
2263   int* j = ila + 3;
2264   insertItCheck(a, dsa, idx, i, j);
2265 }
2266
2267 template <class Vector>
2268 void eraseCheck(Vector& a, DataState<Vector>& dsa, int idx, int n) {
2269   ASSERT_EQ(dsa.size() - n, a.size());
2270   size_t i = 0;
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));
2275   }
2276 }
2277
2278 STL_TEST("23.2.3 Table 100.11", iteratorErase, is_move_assignable, a, p) {
2279   if (p == a.end()) return;
2280
2281   DataState<Vector> dsa(a);
2282   int idx = distance(a.begin(), p);
2283   auto am = a.get_allocator();
2284
2285   auto rit = a.erase(p);
2286
2287   ASSERT_TRUE(am == a.get_allocator());
2288   ASSERT_EQ(idx, distance(a.begin(), rit)) << "wrong iterator returned";
2289   eraseCheck(a, dsa, idx, 1);
2290 }
2291
2292 STL_TEST("23.2.3 Table 100.12", iteratorEraseRange,
2293          is_move_assignable, a, p, q) {
2294   if (p == a.end()) return;
2295
2296   DataState<Vector> dsa(a);
2297   int idx = distance(a.begin(), p);
2298   auto am = a.get_allocator();
2299
2300   auto rit = a.erase(p, q);
2301
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));
2305 }
2306
2307 //--------------------------------
2308 // end insert-and-erase subsection
2309
2310 STL_TEST("23.2.3 Table 100.13", clear, is_destructible, a) {
2311
2312   auto am = a.get_allocator();
2313
2314   try {
2315     a.clear();
2316   } catch (...) {
2317     FAIL() << "clear must be noexcept";
2318   }
2319
2320   ASSERT_TRUE(am == a.get_allocator());
2321   ASSERT_TRUE(a.empty());
2322 }
2323
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();
2330
2331   a.assign(cfi, cfj);
2332
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));
2337 }
2338
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();
2346
2347   a.assign(cii, cij);
2348
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));
2353 }
2354
2355 STL_TEST("23.2.3 Table 100.15", assignIL,
2356          is_arithmetic, a) {
2357
2358   // whitebox: ensure that assign(il) is implemented in terms of
2359   // assign(il.begin(), il.end())
2360
2361   // gcc fail
2362   if (Ticker::TicksLeft >= 0) return;
2363
2364   auto am = a.get_allocator();
2365
2366   a.assign({1, 4, 7});
2367
2368   ASSERT_TRUE(am == a.get_allocator());
2369   int ila[] = { 1, 4, 7 };
2370   int* i = ila;
2371
2372   ASSERT_EQ(3, a.size());
2373   for (auto it = a.begin(); it != a.end(); ++it, ++i)
2374     ASSERT_EQ(*i, convertToInt(*it));
2375 }
2376
2377 STL_TEST("23.2.3 Table 100.16", assignN,
2378          is_copy_constructibleAndAssignable, a, n, t) {
2379   auto am = a.get_allocator();
2380   auto const& ct = t;
2381   auto tval = convertToInt(t);
2382
2383   a.assign(n, ct);
2384
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));
2389 }
2390
2391 STL_TEST("23.2.3 Table 101.1", front, is_destructible, a) {
2392   if (a.empty()) return;
2393
2394   ASSERT_TRUE(addressof(a.front()) == a.data());
2395
2396   ASSERT_EQ(0, Counter::CountTotalOps);
2397
2398   if (false) {
2399     mutate(a.front());
2400     const Vector& ca = a;
2401     ca.front();
2402   }
2403 }
2404
2405 STL_TEST("23.2.3 Table 101.2", back, is_destructible, a) {
2406   if (a.empty()) return;
2407
2408   ASSERT_TRUE(addressof(a.back()) == a.data() + a.size() - 1);
2409
2410   ASSERT_EQ(0, Counter::CountTotalOps);
2411
2412   if (false) {
2413     mutate(a.back());
2414     const Vector& ca = a;
2415     ca.back();
2416   }
2417 }
2418
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();
2425
2426   try {
2427     a.emplace_back(44);
2428   } catch (...) {
2429     ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2430     throw;
2431   }
2432
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());
2436   size_t i = 0;
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()));
2441 }
2442
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();
2449   const auto& ct = t;
2450
2451   try {
2452     a.push_back(ct);
2453   } catch (...) {
2454     ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2455     throw;
2456   }
2457
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());
2461   size_t i = 0;
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()));
2466 }
2467
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();
2475
2476   try {
2477     a.push_back(move(t));
2478   } catch (...) {
2479     ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2480     throw;
2481   }
2482
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());
2486   size_t i = 0;
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()));
2491 }
2492
2493 STL_TEST("23.2.3 Table 100.10", popBack, is_destructible, a) {
2494   if (a.empty()) return;
2495
2496   DataState<Vector> dsa(a);
2497   auto am = a.get_allocator();
2498
2499   a.pop_back();
2500
2501   ASSERT_TRUE(am == a.get_allocator());
2502   ASSERT_EQ(dsa.size() - 1, a.size());
2503   size_t i = 0;
2504   auto it = a.begin();
2505   for (; it != a.end(); ++it, ++i)
2506     ASSERT_EQ(dsa[i], convertToInt(*it));
2507 }
2508
2509 STL_TEST("23.2.3 Table 100.11", operatorBrace, is_destructible, a) {
2510   const auto& ca = a;
2511   for (int i = 0; i < ca.size(); ++i)
2512     ASSERT_TRUE(addressof(ca[i]) == ca.data()+i);
2513
2514   ASSERT_EQ(0, Counter::CountTotalOps);
2515
2516   if (false) {
2517     mutate(a[0]);
2518   }
2519 }
2520
2521 STL_TEST("23.2.3 Table 100.12", at, is_destructible, a) {
2522   const auto& ca = a;
2523   for (int i = 0; i < ca.size(); ++i)
2524     ASSERT_TRUE(addressof(ca.at(i)) == ca.data()+i);
2525
2526   ASSERT_EQ(0, Counter::CountTotalOps);
2527
2528   try {
2529     ca.at(ca.size());
2530     FAIL() << "at(size) should have thrown an error";
2531   } catch (const std::out_of_range& e) {
2532   } catch (...) {
2533     FAIL() << "at(size) threw error other than out_of_range";
2534   }
2535
2536   if (false) {
2537     mutate(a.at(0));
2538   }
2539 }
2540
2541 STL_TEST("move iterators", moveIterators, is_copy_constructibleAndAssignable) {
2542   if (false) {
2543     int* i = nullptr;
2544     int* j = nullptr;
2545
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));
2550
2551     Vector u1(mfi, mfj);
2552     Vector u2(mii, mij);
2553
2554     u1.insert(u1.begin(), mfi, mfj);
2555     u1.insert(u1.begin(), mii, mij);
2556
2557     u1.assign(mfi, mfj);
2558     u1.assign(mii, mij);
2559   }
2560 }
2561
2562 //-----------------------------------------------------------------------------
2563 // Vector-specifics
2564
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
2569 }
2570
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();
2575
2576   a.reserve(n);
2577
2578   ASSERT_TRUE(am == a.get_allocator());
2579   if (n <= ocap) {
2580     ASSERT_EQ(0, Counter::CountTotalOps);
2581     ASSERT_TRUE(adata == a.data());
2582   } else {
2583     ASSERT_TRUE(a.capacity() >= n);
2584     ASSERT_LE(Counter::CountTotalOps, 2*a.size()); // move and delete
2585   }
2586 }
2587
2588 STL_TEST("23.3.6.3", lengthError, is_move_constructible) {
2589   auto mx = Vector().max_size();
2590   auto big = mx+1;
2591   if (mx >= big) return; // max_size is the biggest size_type; overflowed
2592
2593   Vector u;
2594   try {
2595     u.reserve(big);
2596     FAIL() << "reserve(big) should have thrown an error";
2597   } catch (const std::length_error& e) {
2598   } catch (...) {
2599     FAIL() << "reserve(big) threw error other than length_error";
2600   }
2601 }
2602
2603 STL_TEST("23.3.6.3", resize, is_copy_constructible, a, n) {
2604   DataState<Vector> dsa(a);
2605   int sz = a.size();
2606   auto am = a.get_allocator();
2607
2608   a.resize(n);
2609
2610   ASSERT_TRUE(am == a.get_allocator());
2611   ASSERT_EQ(n, a.size());
2612
2613   if (n <= sz) {
2614     for (int i = 0; i < n; ++i) {
2615       ASSERT_EQ(dsa[i], convertToInt(a[i]));
2616     }
2617   } else {
2618     for (int i = 0; i < sz; ++i) {
2619       ASSERT_EQ(dsa[i], convertToInt(a[i]));
2620     }
2621   }
2622 }
2623
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;
2627   #endif
2628
2629   DataState<Vector> dsa(a);
2630   int sz = a.size();
2631   auto am = a.get_allocator();
2632   const auto& ct = t;
2633   int val = convertToInt(t);
2634
2635   a.resize(n, ct);
2636
2637   ASSERT_TRUE(am == a.get_allocator());
2638   ASSERT_EQ(n, a.size());
2639
2640   if (n <= sz) {
2641     for (int i = 0; i < n; ++i) {
2642       ASSERT_EQ(dsa[i], convertToInt(a[i]));
2643     }
2644   } else {
2645     int i = 0;
2646     for ( ; i < sz; ++i) {
2647       ASSERT_EQ(dsa[i], convertToInt(a[i]));
2648     }
2649     for ( ; i < n; ++i) {
2650       ASSERT_EQ(val, convertToInt(a[i]));
2651     }
2652   }
2653 }
2654
2655 STL_TEST("23.3.6.3", shrinkToFit, is_move_constructible, a) {
2656   bool willThrow = Ticker::TicksLeft >= 0;
2657
2658   a.reserve(a.capacity() * 11);
2659
2660   auto ocap = a.capacity();
2661   DataState<Vector> dsa(a);
2662
2663   auto am = a.get_allocator();
2664
2665   try {
2666     a.shrink_to_fit();
2667   } catch (...) {
2668     FAIL() << "shrink_to_fit should swallow errors";
2669   }
2670
2671   ASSERT_TRUE(am == a.get_allocator());
2672   ASSERT_TRUE(dsa == a);
2673   if (willThrow) {
2674     //ASSERT_EQ(ocap, a.capacity()); might shrink in place
2675     throw TickException("I swallowed the error");
2676   } else {
2677     ASSERT_TRUE(a.capacity() == 0 || a.capacity() < ocap) << "Look into this";
2678   }
2679 }
2680
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*)");
2686 }
2687
2688 STL_TEST("relinquish", relinquish, is_destructible, a) {
2689   auto sz = a.size();
2690   auto cap = a.capacity();
2691   auto data = a.data();
2692
2693   auto guts = relinquish(a);
2694
2695   ASSERT_EQ(data, guts);
2696   ASSERT_TRUE(a.empty());
2697   ASSERT_EQ(0, a.capacity());
2698
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);
2704 }
2705
2706 STL_TEST("attach", attach, is_destructible, a) {
2707   DataState<Vector> dsa(a);
2708
2709   auto sz = a.size();
2710   auto cap = a.capacity();
2711   auto guts = relinquish(a);
2712
2713   ASSERT_EQ(a.data(), nullptr);
2714   attach(a, guts, sz, cap);
2715
2716   ASSERT_TRUE(dsa == a);
2717 }
2718
2719 #endif
2720
2721 // #endif
2722
2723 int main(int argc, char** argv) {
2724   testing::InitGoogleTest(&argc, argv);
2725   gflags::ParseCommandLineFlags(&argc, &argv, true);
2726
2727   return RUN_ALL_TESTS();
2728 }
2729
2730 #else // GCC 4.7 guard
2731
2732 // do nothing
2733 TEST(placeholder, gccversion) {}
2734
2735 int main(int argc, char** argv) {
2736   testing::InitGoogleTest(&argc, argv);
2737   gflags::ParseCommandLineFlags(&argc, &argv, true);
2738
2739   return RUN_ALL_TESTS();
2740 }
2741
2742 #endif // GCC 4.7 guard