folly/test/stl_tests/StlVectorTest.cpp

   1 /*
   2  * Copyright 2016 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 #if 0
  29 #define USING_STD_VECTOR
  30 #endif
  31
  32 /*
  33
  34 The insanity of this file deserves a superficial explanation.
  35
  36 This file tests an implementation of STL vector. It is extremely comprehensive.
  37 If it compiles (more on that later) it generates a binary which, when run,
  38 exhaustively tests its vector for standard compliance.
  39
  40 Limitations:
  41 -If it doesn't compile, the compiler errors are mind-boggling.
  42 -Not everything is testable. There are a few comments in the code where
  43  the implementation must be inspected, as opposed to tested. These are very
  44  simple inspections. Search for 'whitebox'.
  45 -It does not test boolean specialization.
  46
  47 ==========================
  48 How this file is organized
  49
  50 --------------
  51 Data and Alloc
  52
  53 Data is a class designed to provide diagnostics when stored in a vector. It
  54 counts the number of operations performed on it, can have any function
  55 disabled or labeled as noexcept, throws errors from anywhere that is not
  56 noexcept, tracks its supposed location in memory (optional), tracks
  57 aggregate information, and can print a trace of its action.
  58
  59 Alloc, like Data, is a full-blown diagnostic allocator. It keeps track of
  60 all space it has allocated, keeps counters, throws exceptions, and can easily
  61 compare equal or not equal with other Allocs.
  62
  63 These two classes have a few useful helper functions:
  64 isSane - checks that all the tracked variables make sense
  65 softReset - simplifies the variables before a test
  66 hardReset - brutally resets all variables to the default state
  67
  68 --------
  69 STL_TEST
  70
  71 Google test is not quite good enough for this test file, because we need to
  72 run tests across different input values and different types.
  73
  74 The STL_TEST macro takes a few arguments:
  75 string - what is being tested
  76 id - unique id, passed to TEST
  77 restriction - requirements for test types
  78 parameters - which variables to range over
  79
  80 Eg: STL_TEST("23.2.3", isCopyable, is_copy_constructible, a) { ... }
  81
  82 The restriction is used to select which types get tested. Copy construction,
  83 for example, requires a data type which is copy constructible, whereas to test
  84 the clear operation, the data only needs to be destructible. If the type does
  85 not pass the restriction, then the test is not instantiated with that type (if
  86 it were, then there would be a compiler error).
  87
  88 The variable names in the standard have very specific meaning. For example,
  89 a and b are always vectors, i and j are always external iterators, etc. These
  90 bindings are used in the STL_TEST - if you need a vector and an int, have
  91 parameters a and n.
  92
  93 There is a list (BOOST_PP_SEQ) of test types and interface types. If the
  94 type passes the restriction, then the test body is instantiated with that
  95 type as its template parameter. Instantiation ensures that the contractual
  96 elements of the standard are satisfied.  Only the test types, however, and
  97 not the interfact types, are actually tested.
  98
  99 If a test type passes the restriction, then it is run with a variety of
 100 arguments. Each variable (e.g. a and b) have a generator, which generates
 101 a range of values for that variable before each test. Generated values are not
 102 reused - they are remade for every run. This causes long runtimes, but ensures
 103 that corner cases are not missed.
 104
 105 There are two implicit extra parameters, z and ticks. Ignore z. Ticks, on the
 106 other hand, is very important. Each is test is run multiple times with the
 107 same arguments; the first time with no ticks (and hence no Data or Alloc
 108 exceptions), and then once again for each and every location that an
 109 exception can be thrown. This ensures that exception corner cases are alse
 110 thoroughly tested.
 111
 112 At the end of each test, a set of verification functions is run to ensure
 113 that nothing was corrupted.
 114
 115 ---------
 116 The tests
 117
 118 All specifications from N3337 Chapter 23 (Containers) that pertains to
 119 vector is tested (if possible). Each aspect has a dedicated STL_TEST, so that
 120 there are no compounding errors. The tests are organized as they appear in
 121 N3337.
 122
 123 The backbone of the testing framework is based on a small set of vector
 124 operations:
 125 -empty construction
 126 -copy construction (a little bit)
 127 -size
 128 -capacity
 129 -data
 130 -emplace_back
 131
 132 These functions are used to generate and verify the tests. If they fail, then
 133 the cascade of errors will be enormous. They are, therefore, tested first.
 134
 135 */
 136 /*
 137
 138 THOUGHTS:
 139
 140 -Not all complexity checks are verified. These will be relentlessly hunted down
 141  in the benchmarking phase.
 142
 143 -It seems that initializer lists with implicit arguments are constructed before
 144  being passed into the vector. When one of the constructors fails, it fails in
 145  the initializer list, before it even gets to the vector. The IL, however,
 146  doesn't clean up properly, and already-constructed elements are not
 147  destroyed. This causes a memory leak, and the tests break, but it is not the
 148  fault of the vector itself. Further, since the implementation for the
 149  initializer lists is specified in the standard as calling an associated
 150  function with (il.begin(), il.end()), we really just have to check the throws
 151  cases for the associated functions (which all work fine). Initializer lists
 152  also do not work with explicit constructors.
 153
 154 -The implementation of std::copy from iterators prevents Data(int) from being
 155  explicit. Explicitness is, perhaps, a desirable quality, but with fundamental
 156  std library code like copy not supporting it, it seems impractical.
 157
 158 */
 159
 160 // include the vector first, to ensure its header is self-sufficient
 161 #ifdef USING_STD_VECTOR
 162 #include <vector>
 163 #define VECTOR_ std::vector
 164 #else
 165 #include <folly/FBVector.h>
 166 #define VECTOR_ folly::fbvector
 167 #endif
 168
 169 //#define USING_STD_VECTOR
 170
 171 #include <iostream>
 172 #include <sstream>
 173 #include <typeinfo>
 174 #include <type_traits>
 175 #include <map>
 176 #include <set>
 177 #include <string>
 178 #include <stdexcept>
 179 #include <exception>
 180 #include <climits>
 181 #include <cstddef>
 182 #include <iomanip>
 183
 184 #include <gtest/gtest.h>
 185 #include <boost/iterator/iterator_adaptor.hpp>
 186 #include <boost/preprocessor.hpp>
 187
 188 #include <folly/Conv.h>
 189 #include <folly/ScopeGuard.h>
 190 #include <folly/portability/GFlags.h>
 191
 192 using namespace std;
 193 using namespace folly;
 194
 195 //=============================================================================
 196 //=============================================================================
 197 // Data type
 198
 199 //-----------------------------------------------------------------------------
 200 // Flags
 201
 202 typedef uint32_t Flags;
 203
 204 // each method has 3 options: normal, noexcept, throw, and deleted
 205 // normal is the default
 206 // throw is mutually exclusive with noexcept
 207 //
 208 // DC - default constructor
 209 // CC - copy constructor
 210 // MC - move constructor
 211 // OC - other constructor
 212 // CA - copy assignment
 213 // MA - move assignment
 214 enum FlagVals : Flags {
 215   DC_NOEXCEPT = 0x1,
 216   DC_THROW    = 0x2,
 217   DC_DELETE   = 0x8000,
 218   CC_NOEXCEPT = 0x4,
 219   CC_THROW    = 0x8,
 220   CC_DELETE   = 0x10000,
 221   MC_NOEXCEPT = 0x10,
 222   MC_THROW    = 0x20,
 223   MC_DELETE   = 0x20000,
 224   OC_NOEXCEPT = 0x40,
 225   OC_THROW    = 0x80,
 226   // OC_DELETE - DNE
 227
 228   CA_NOEXCEPT = 0x100,
 229   CA_THROW    = 0x200,
 230   CA_DELETE   = 0x40000,
 231   MA_NOEXCEPT = 0x400,
 232   MA_THROW    = 0x800,
 233   MA_DELETE   = 0x80000,
 234
 235   ALL_DELETE  = DC_DELETE | CC_DELETE | MC_DELETE
 236               | CA_DELETE | MA_DELETE,
 237
 238   IS_RELOCATABLE
 239               = 0x2000,
 240
 241   // for the allocator
 242   PROP_COPY = 0x100000,
 243   PROP_MOVE = 0x200000,
 244   PROP_SWAP = 0x400000,
 245 };
 246
 247 //-----------------------------------------------------------------------------
 248 // Deletors
 249
 250 template <bool b> struct D0 {
 251   D0() = default;
 252   D0(const D0&) = default;
 253   D0(D0&&) = default;
 254   explicit D0(std::nullptr_t) {}
 255   D0& operator=(const D0&) = default;
 256   D0& operator=(D0&&) = default;
 257 };
 258 template <> struct D0<true> {
 259   D0() = delete;
 260   D0(const D0&) = default;
 261   D0(D0&&) = default;
 262   explicit D0(std::nullptr_t) {}
 263   D0& operator=(const D0&) = default;
 264   D0& operator=(D0&&) = default;
 265 };
 266
 267 template <bool b> struct D1 {
 268   D1() = default;
 269   D1(const D1&) = default;
 270   D1(D1&&) = default;
 271   explicit D1(std::nullptr_t) {}
 272   D1& operator=(const D1&) = default;
 273   D1& operator=(D1&&) = default;
 274 };
 275 template <> struct D1<true> {
 276   D1() = default;
 277   D1(const D1&) = delete;
 278   D1(D1&&) = default;
 279   explicit D1(std::nullptr_t) {}
 280   D1& operator=(const D1&) = default;
 281   D1& operator=(D1&&) = default;
 282 };
 283
 284 template <bool b> struct D2 {
 285   D2() = default;
 286   D2(const D2&) = default;
 287   D2(D2&&) = default;
 288   explicit D2(std::nullptr_t) {}
 289   D2& operator=(const D2&) = default;
 290   D2& operator=(D2&&) = default;
 291 };
 292 template <> struct D2<true> {
 293   D2() = default;
 294   D2(const D2&) = default;
 295   D2(D2&&) = delete;
 296   explicit D2(std::nullptr_t) {}
 297   D2& operator=(const D2&) = default;
 298   D2& operator=(D2&&) = default;
 299 };
 300
 301 template <bool b> struct D3 {
 302   D3() = default;
 303   D3(const D3&) = default;
 304   D3(D3&&) = default;
 305   explicit D3(std::nullptr_t) {}
 306   D3& operator=(const D3&) = default;
 307   D3& operator=(D3&&) = default;
 308 };
 309 template <> struct D3<true> {
 310   D3() = default;
 311   D3(const D3&) = default;
 312   D3(D3&&) = default;
 313   explicit D3(std::nullptr_t) {}
 314   D3& operator=(const D3&) = delete;
 315   D3& operator=(D3&&) = default;
 316 };
 317
 318 template <bool b> struct D4 {
 319   D4() = default;
 320   D4(const D4&) = default;
 321   D4(D4&&) = default;
 322   explicit D4(std::nullptr_t) {}
 323   D4& operator=(const D4&) = default;
 324   D4& operator=(D4&&) = default;
 325 };
 326 template <> struct D4<true> {
 327   D4() = default;
 328   D4(const D4&) = default;
 329   D4(D4&&) = default;
 330   explicit D4(std::nullptr_t) {}
 331   D4& operator=(const D4&) = default;
 332   D4& operator=(D4&&) = delete;
 333 };
 334
 335 template <Flags f>
 336 struct Delete : D0<(f & DC_DELETE) != 0>
 337               , D1<(f & CC_DELETE) != 0>
 338               , D2<(f & MC_DELETE) != 0>
 339               , D3<(f & CA_DELETE) != 0>
 340               , D4<(f & MA_DELETE) != 0> {
 341   Delete() = default;
 342   Delete(const Delete&) = default;
 343   Delete(Delete&&) = default;
 344   Delete& operator=(const Delete&) = default;
 345   Delete& operator=(Delete&&) = default;
 346
 347   explicit Delete(std::nullptr_t)
 348       : D0<(f & DC_DELETE) != 0>(nullptr)
 349       , D1<(f & CC_DELETE) != 0>(nullptr)
 350       , D2<(f & MC_DELETE) != 0>(nullptr)
 351       , D3<(f & CA_DELETE) != 0>(nullptr)
 352       , D4<(f & MA_DELETE) != 0>(nullptr)
 353       {}
 354 };
 355
 356 //-----------------------------------------------------------------------------
 357 // Ticker
 358
 359 struct TickException : std::runtime_error {
 360   explicit TickException(const std::string& s)
 361     : std::runtime_error("tick: " + s) {}
 362 };
 363
 364 struct Ticker {
 365   static int CountTicks;
 366   static int TicksLeft;
 367   static void Tick(const std::string& s) {
 368     if (TicksLeft == 0) throw TickException(s);
 369     CountTicks++;
 370     TicksLeft--;
 371   }
 372 };
 373
 374 int Ticker::CountTicks = 0;
 375 int Ticker::TicksLeft = -1;
 376
 377 template <Flags f>
 378 struct DataTicker : Ticker {
 379   DataTicker() noexcept(f & DC_NOEXCEPT) {
 380     if (!(f & DC_NOEXCEPT)) Tick("Data()");
 381   }
 382   DataTicker(const DataTicker&) noexcept((f & CC_NOEXCEPT) != 0) {
 383     if (!(f & CC_NOEXCEPT)) Tick("Data(const Data&)");
 384   }
 385   DataTicker(DataTicker&&) noexcept((f & MC_NOEXCEPT) != 0) {
 386     if (!(f & MC_NOEXCEPT)) Tick("Data(Data&&)");
 387   }
 388   explicit DataTicker(std::nullptr_t) noexcept((f & OC_NOEXCEPT) != 0) {
 389     if (!(f & OC_NOEXCEPT)) Tick("Data(int)");
 390   }
 391   ~DataTicker() noexcept {}
 392   void operator=(const DataTicker&) noexcept((f & CA_NOEXCEPT) != 0) {
 393     if (!(f & CA_NOEXCEPT)) Tick("op=(const Data&)");
 394   }
 395   void operator=(DataTicker&&) noexcept((f & MA_NOEXCEPT) != 0) {
 396     if (!(f & MA_NOEXCEPT)) Tick("op=(Data&&)");
 397   }
 398 };
 399
 400 //-----------------------------------------------------------------------------
 401 // Operation counter
 402
 403 struct Counter {
 404   static int CountDC, CountCC, CountMC, CountOC, CountCA, CountMA;
 405   static int CountDestroy, CountTotalOps, CountLoggedConstruction;
 406
 407   Counter()                         noexcept { CountTotalOps++; CountDC++; }
 408   Counter(const Counter&)           noexcept { CountTotalOps++; CountCC++; }
 409   Counter(Counter&&)                noexcept { CountTotalOps++; CountMC++; }
 410   explicit Counter(std::nullptr_t)  noexcept { CountTotalOps++; CountOC++; }
 411   void operator=(const Counter&)    noexcept { CountTotalOps++; CountCA++; }
 412   void operator=(Counter&&)         noexcept { CountTotalOps++; CountMA++; }
 413   ~Counter()                      noexcept { CountTotalOps++; CountDestroy++; }
 414 };
 415
 416 int Counter::CountDC = 0;
 417 int Counter::CountCC = 0;
 418 int Counter::CountMC = 0;
 419 int Counter::CountOC = 0;
 420 int Counter::CountCA = 0;
 421 int Counter::CountMA = 0;
 422 int Counter::CountDestroy = 0;
 423 int Counter::CountTotalOps = 0;
 424 int Counter::CountLoggedConstruction = 0;
 425
 426 //-----------------------------------------------------------------------------
 427 // Tracker
 428
 429 struct Tracker {
 430   static int UID;
 431   static std::map<int, int> UIDCount;
 432   static int UIDTotal;
 433   static std::map<const Tracker*, int> Locations;
 434   static bool Print;
 435
 436   Tracker* self;
 437   int uid;
 438
 439   Tracker(Tracker* self, int uid) : self(self), uid(uid) {}
 440 };
 441
 442 template <bool isRelocatable>
 443 struct DataTracker : Tracker {
 444   DataTracker() noexcept : Tracker(this, UID++) {
 445     UIDCount[uid]++;
 446     UIDTotal++;
 447     if (!isRelocatable) Locations[self] = uid;
 448     print("Data()");
 449   }
 450   DataTracker(const DataTracker& o) noexcept : Tracker(this, o.uid) {
 451     UIDCount[uid]++;
 452     UIDTotal++;
 453     if (!isRelocatable) Locations[self] = uid;
 454     print("Data(const Data&)");
 455   }
 456   DataTracker(DataTracker&& o) noexcept : Tracker(this, o.uid) {
 457     UIDCount[uid]++;
 458     UIDTotal++;
 459     if (!isRelocatable) Locations[self] = uid;
 460     print("Data(Data&&)");
 461   }
 462
 463   explicit DataTracker(int uid) noexcept : Tracker(this, uid) {
 464     UIDCount[uid]++;
 465     UIDTotal++;
 466     if (!isRelocatable) Locations[self] = uid;
 467     print("Data(int)");
 468   }
 469
 470   ~DataTracker() noexcept {
 471     UIDCount[uid]--;
 472     UIDTotal--;
 473     if (!isRelocatable) Locations.erase(self);
 474     print("~Data()");
 475     uid = 0xdeadbeef;
 476     self = (DataTracker*)0xfeebdaed;
 477   }
 478
 479   DataTracker& operator=(const DataTracker& o) noexcept {
 480     UIDCount[uid]--;
 481     uid = o.uid;
 482     UIDCount[uid]++;
 483     if (!isRelocatable) Locations[self] = uid;
 484     print("op=(const Data&)");
 485     return *this;
 486   }
 487   DataTracker& operator=(DataTracker&& o) noexcept {
 488     UIDCount[uid]--;
 489     uid = o.uid;
 490     UIDCount[uid]++;
 491     if (!isRelocatable) Locations[self] = uid;
 492     print("op=(Data&&)");
 493     return *this;
 494   }
 495
 496   void print(const std::string& fun) {
 497     if (Print) {
 498       std::cerr << std::setw(20) << fun << ": uid = " << std::setw(3) << uid;
 499       if (!isRelocatable) std::cerr << ", self = " << self;
 500       std::cerr << std::endl;
 501     }
 502   }
 503 };
 504
 505 int Tracker::UID = 1234;
 506 std::map<int, int> Tracker::UIDCount;
 507 int Tracker::UIDTotal = 0;
 508 std::map<const Tracker*, int> Tracker::Locations;
 509 bool Tracker::Print = false;
 510
 511 //-----------------------------------------------------------------------------
 512 //-----------------------------------------------------------------------------
 513 // Data
 514
 515 template <Flags f = 0, size_t pad = 0>
 516 struct Data : DataTracker<(f & IS_RELOCATABLE) != 0>,
 517               Counter, DataTicker<f>, Delete<f> {
 518   static const Flags flags = f;
 519   char spacehog[pad ? pad : 1];
 520
 521   Data() = default;
 522   Data(const Data&) = default;
 523   Data(Data&&) = default;
 524   /* implicit */ Data(int i)
 525     : DataTracker<(f & IS_RELOCATABLE) != 0>(i), Counter()
 526     , DataTicker<f>(nullptr)
 527     , Delete<f>(nullptr)
 528   {}
 529   ~Data() = default;
 530   Data& operator=(const Data&) = default;
 531   Data& operator=(Data&&) = default;
 532
 533 private:
 534   int operator&() const;
 535 };
 536
 537 namespace folly {
 538 template <Flags f, size_t pad>
 539 struct IsRelocatable<Data<f, pad>>
 540   : std::integral_constant<bool,
 541       (f & IS_RELOCATABLE) != 0
 542     > {};
 543 };
 544
 545 //-----------------------------------------------------------------------------
 546 //-----------------------------------------------------------------------------
 547 // Allocator
 548
 549 template <typename T>
 550 struct isPropCopy : true_type {};
 551 template <Flags f, size_t pad>
 552 struct isPropCopy<Data<f, pad>> :
 553   std::integral_constant<bool, (f & PROP_COPY) != 0> {};
 554
 555 template <typename T>
 556 struct isPropMove : true_type {};
 557 template <Flags f, size_t pad>
 558 struct isPropMove<Data<f, pad>> :
 559   std::integral_constant<bool, (f & PROP_MOVE) != 0> {};
 560
 561 template <typename T>
 562 struct isPropSwap : true_type {};
 563 template <Flags f, size_t pad>
 564 struct isPropSwap<Data<f, pad>> :
 565   std::integral_constant<bool, (f & PROP_SWAP) != 0> {};
 566
 567
 568 struct AllocTracker {
 569   static int Constructed;
 570   static int Destroyed;
 571   static map<void*, size_t> Allocated;
 572   static map<void*, int> Owner;
 573 };
 574 int AllocTracker::Constructed = 0;
 575 int AllocTracker::Destroyed = 0;
 576 map<void*, size_t> AllocTracker::Allocated;
 577 map<void*, int> AllocTracker::Owner;
 578
 579 template <class T>
 580 struct Alloc : AllocTracker, Ticker {
 581   typedef typename std::allocator<T>::pointer pointer;
 582   typedef typename std::allocator<T>::const_pointer const_pointer;
 583   typedef typename std::allocator<T>::difference_type difference_type;
 584   typedef typename std::allocator<T>::size_type size_type;
 585   typedef typename std::allocator<T>::value_type value_type;
 586
 587   //-----
 588   // impl
 589
 590   std::allocator<T> a;
 591   int id;
 592   explicit Alloc(int i = 8) : a(), id(i) {}
 593   Alloc(const Alloc& o) : a(o.a), id(o.id) {}
 594   Alloc(Alloc&& o) : a(move(o.a)), id(o.id) {}
 595   Alloc& operator=(const Alloc&) = default;
 596   Alloc& operator=(Alloc&&) = default;
 597   bool operator==(const Alloc& o) const { return a == o.a && id == o.id; }
 598   bool operator!=(const Alloc& o) const { return !(*this == o); }
 599
 600   //---------
 601   // tracking
 602
 603   pointer allocate(size_type n) {
 604     if (n == 0) {
 605       cerr << "called allocate(0)" << endl;
 606       throw runtime_error("allocate fail");
 607     }
 608     Tick("allocate");
 609     auto p = a.allocate(n);
 610     Allocated[p] = n;
 611     Owner[p] = id;
 612     return p;
 613   }
 614
 615   void deallocate(pointer p, size_type n) {
 616     if (p == nullptr) {
 617       cerr << "deallocate(nullptr, " << n << ")" << endl;
 618       FAIL() << "deallocate failed";
 619     }
 620     if (Allocated[p] != n) {
 621       cerr << "deallocate(" << p << ", " << n << ") invalid: ";
 622       if (Allocated[p] == 0) cerr << "never allocated";
 623       else if (Allocated[p] == -1) cerr << "already deallocated";
 624       else cerr << "wrong number (want " << Allocated[p] << ")";
 625       cerr << endl;
 626       FAIL() << "deallocate failed";
 627     }
 628     if (Owner[p] != id) {
 629       cerr << "deallocate(" << p << "), where pointer is owned by "
 630            << Owner[p] << ", instead of self - " << id << endl;
 631       FAIL() << "deallocate failed";
 632     }
 633     Allocated[p] = -1;
 634     a.deallocate(p, n);
 635   }
 636
 637   template <class U, class... Args>
 638   void construct(U* p, Args&&... args) {
 639     Tick("construct");
 640     a.construct(p, std::forward<Args>(args)...);
 641     Constructed++;
 642   }
 643
 644   template <class U>
 645   void destroy(U* p) {
 646     Destroyed++;
 647     a.destroy(p);
 648   }
 649
 650   //--------------
 651   // container ops
 652
 653   Alloc select_on_container_copy_construction() const {
 654     Tick("select allocator for copy");
 655     return Alloc(id + 1);
 656   }
 657
 658   typedef isPropCopy<T> propagate_on_container_copy_assignment;
 659   typedef isPropMove<T> propagate_on_container_move_assignment;
 660   typedef isPropSwap<T> propagate_on_container_swap;
 661 };
 662
 663 //=============================================================================
 664 //=============================================================================
 665 // Verification and resetting
 666
 667 void softReset(int ticks = -1) {
 668   Counter::CountLoggedConstruction +=
 669     Counter::CountDC + Counter::CountCC + Counter::CountMC
 670     + Counter::CountOC - Counter::CountDestroy;
 671   Counter::CountDC = Counter::CountCC = Counter::CountMC
 672     = Counter::CountOC = Counter::CountCA = Counter::CountMA = 0;
 673   Counter::CountDestroy = Counter::CountTotalOps = 0;
 674   Ticker::CountTicks = 0;
 675   Ticker::TicksLeft = ticks;
 676 }
 677
 678 void hardReset() {
 679   Tracker::UIDCount.clear();
 680   Tracker::UIDTotal = 0;
 681   Tracker::Locations.clear();
 682   softReset();
 683   Counter::CountLoggedConstruction = 0;
 684
 685   AllocTracker::Constructed = 0;
 686   AllocTracker::Destroyed = 0;
 687   AllocTracker::Allocated.clear();
 688   AllocTracker::Owner.clear();
 689 }
 690
 691 int getTotal() {
 692   int con = Counter::CountDC + Counter::CountCC
 693           + Counter::CountMC + Counter::CountOC
 694           + Counter::CountLoggedConstruction;
 695   int del = Counter::CountDestroy;
 696   return con - del;
 697 }
 698
 699 void isSane() {
 700   int tot = getTotal();
 701   ASSERT_GE(tot, 0) << "more objects deleted than constructed";
 702
 703   ASSERT_EQ(tot, Tracker::UIDTotal)
 704     << "UIDTotal has incorrect number of objects";
 705
 706   int altTot = 0;
 707   for (const auto& kv : Tracker::UIDCount) {
 708     ASSERT_TRUE(kv.second >= 0) << "there exists " << kv.second << " Data "
 709       "with uid " << kv.first;
 710     altTot += kv.second;
 711   }
 712   ASSERT_EQ(tot, altTot) << "UIDCount corrupted";
 713
 714   if (!Tracker::Locations.empty()) { // implied by IsRelocatable
 715     ASSERT_EQ(tot, Tracker::Locations.size())
 716       << "Locations has incorrect number of objects";
 717     for (const auto& du : Tracker::Locations) {
 718       ASSERT_EQ(du.second, du.first->uid) << "Locations contains wrong uid";
 719       ASSERT_EQ(du.first, du.first->self) << "Data.self is corrupted";
 720     }
 721   }
 722 }
 723
 724 //-----------------------------------------------------------------------------
 725 // Traits
 726
 727 template <typename T>
 728 struct is_copy_constructibleAndAssignable
 729   : std::integral_constant<bool,
 730       std::is_copy_constructible<T>::value &&
 731       std::is_copy_assignable<T>::value
 732     > {};
 733
 734 template <typename T>
 735 struct is_move_constructibleAndAssignable
 736   : std::integral_constant<bool,
 737       std::is_move_constructible<T>::value &&
 738       std::is_move_assignable<T>::value
 739     > {};
 740
 741 template <class Vector>
 742 struct customAllocator
 743   : std::integral_constant<bool,
 744       !is_same<
 745         typename Vector::allocator_type,
 746         std::allocator<typename Vector::value_type>
 747       >::value
 748     > {};
 749
 750 template <typename T>
 751 struct special_move_assignable
 752   : is_move_constructibleAndAssignable<T> {};
 753 template <Flags f, size_t pad>
 754 struct special_move_assignable<Data<f, pad>>
 755   : std::integral_constant<bool,
 756       is_move_constructibleAndAssignable<Data<f, pad>>::value ||
 757       f & PROP_MOVE
 758     > {};
 759
 760 //=============================================================================
 761 //=============================================================================
 762 // Framework
 763
 764 //-----------------------------------------------------------------------------
 765 // Timing
 766
 767 uint64_t ReadTSC() {
 768 #ifdef _MSC_VER
 769    return __rdtsc();
 770 #else
 771    unsigned reslo, reshi;
 772
 773     __asm__ __volatile__  (
 774     "xorl %%eax,%%eax \n cpuid \n"
 775      ::: "%eax", "%ebx", "%ecx", "%edx");
 776     __asm__ __volatile__  (
 777     "rdtsc\n"
 778      : "=a" (reslo), "=d" (reshi) );
 779     __asm__ __volatile__  (
 780     "xorl %%eax,%%eax \n cpuid \n"
 781      ::: "%eax", "%ebx", "%ecx", "%edx");
 782
 783    return ((uint64_t)reshi << 32) | reslo;
 784 #endif
 785 }
 786
 787 //-----------------------------------------------------------------------------
 788 // New Boost
 789
 790 #define IBOOST_PP_VARIADIC_SIZE(...) IBOOST_PP_VARIADIC_SIZE_I(__VA_ARGS__,   \
 791   64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, \
 792   45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, \
 793   26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8,   \
 794   7, 6, 5, 4, 3, 2, 1,)
 795 #define IBOOST_PP_VARIADIC_SIZE_I(e0, e1, e2, e3, e4, e5, e6, e7, e8, e9,     \
 796   e10, e11, e12, e13, e14, e15, e16, e17, e18, e19, e20, e21, e22, e23, e24,  \
 797   e25, e26, e27, e28, e29, e30, e31, e32, e33, e34, e35, e36, e37, e38, e39,  \
 798   e40, e41, e42, e43, e44, e45, e46, e47, e48, e49, e50, e51, e52, e53, e54,  \
 799   e55, e56, e57, e58, e59, e60, e61, e62, e63, size, ...) size
 800 #define IBOOST_PP_VARIADIC_TO_SEQ(...) \
 801   BOOST_PP_TUPLE_TO_SEQ(IBOOST_PP_VARIADIC_SIZE(__VA_ARGS__), (__VA_ARGS__))
 802
 803 //-----------------------------------------------------------------------------
 804 // STL_TEST
 805
 806 #define GEN_TEST(r, name, type)                                   \
 807   {                                                               \
 808     string atype = PrettyType<typename type::allocator_type>()(); \
 809     string ptype = PrettyType<typename type::value_type>()();     \
 810     SCOPED_TRACE("allocator: " + atype); {                        \
 811     SCOPED_TRACE("datatype: " + ptype); {                         \
 812     test_ ## name ## 3 <type> ();                                 \
 813     if (::testing::Test::HasFatalFailure()) return;               \
 814   }}}
 815 #define GEN_TYPE_TEST(r, name, type) \
 816   if (0) test_I_ ## name ## 3 <type> ();
 817 #define GEN_RUNNABLE_TEST(r, name, type) \
 818   one = test_I_ ## name ## 3 <type> () || one;
 819
 820 #define GEN_LOOPER(r, d, arg) BOOST_PP_CAT(LOOPER_, arg)
 821 #define GEN_VMAKER(r, d, arg) { BOOST_PP_CAT(VMAKER_, arg) {
 822 #define GEN_UMAKER(r, d, arg) } BOOST_PP_CAT(UMAKER_, arg) }
 823 #define GEN_CLOSER(r, d, arg) BOOST_PP_CAT(CLOSER_, arg)
 824
 825 #define TYPIFY(r, d, name) BOOST_PP_CAT(TYPIFY_, name)
 826 #define ARGIFY(r, d, name) TYPIFY(r, d, name) name
 827
 828 #define MAKE_TEST(ref, name, types, restriction, argseq, ...)            \
 829   template <class Vector> void test_ ## name ## 2 (std::false_type) {}   \
 830   template <class Vector> void test_ ## name ## 2 (std::true_type) {     \
 831     BOOST_PP_SEQ_FOR_EACH(GEN_LOOPER, _, argseq)                         \
 832     { SETUP {                                                            \
 833     BOOST_PP_SEQ_FOR_EACH(GEN_VMAKER, _, argseq)                         \
 834     {                                                                    \
 835     test_ ## name <Vector, typename Vector::value_type,                  \
 836       typename Vector::allocator_type> ( __VA_ARGS__ );                  \
 837     if (::testing::Test::HasFatalFailure()) return;                      \
 838     }                                                                    \
 839     BOOST_PP_SEQ_FOR_EACH(GEN_UMAKER, _, BOOST_PP_SEQ_REVERSE(argseq))   \
 840     } TEARDOWN }                                                         \
 841     BOOST_PP_SEQ_FOR_EACH(GEN_CLOSER, _, BOOST_PP_SEQ_REVERSE(argseq))   \
 842   }                                                                      \
 843   template <class Vector> void test_ ## name ## 3 () {                   \
 844     test_ ## name ## 2 <Vector> (std::integral_constant<bool,            \
 845         restriction<typename Vector::value_type>::value &&               \
 846         is_copy_constructible<typename Vector::value_type>::value        \
 847       >());                                                              \
 848   }                                                                      \
 849                                                                          \
 850   template <class Vector> bool test_I_ ## name ## 2 (std::false_type)    \
 851     { return false; }                                                    \
 852   template <class Vector> bool test_I_ ## name ## 2 (std::true_type) {   \
 853     return true;                                                         \
 854     auto f = test_ ## name <Vector,                                      \
 855       typename Vector::value_type, typename Vector::allocator_type>;     \
 856     return true;                                                         \
 857   }                                                                      \
 858   template <class Vector> bool test_I_ ## name ## 3 () {                 \
 859     return test_I_ ## name ## 2 <Vector> (std::integral_constant<bool,   \
 860       restriction<typename Vector::value_type>::value>());               \
 861     return false;                                                        \
 862   }                                                                      \
 863                                                                          \
 864   TEST(FBVector, name) {                                                 \
 865     SCOPED_TRACE("N3337 reference: " ref);                               \
 866     BOOST_PP_SEQ_FOR_EACH(GEN_TEST, name, types)                         \
 867     BOOST_PP_SEQ_FOR_EACH(GEN_TYPE_TEST, name, INTERFACE_TYPES)          \
 868     bool one = false;                                                    \
 869     BOOST_PP_SEQ_FOR_EACH(GEN_RUNNABLE_TEST, name, types)                \
 870     if (!one) FAIL() << "No tests qualified to run";                     \
 871   }
 872
 873 #define DECL(name, ...)                                                       \
 874   template <class Vector, typename T, typename Allocator>                     \
 875   void test_ ## name (BOOST_PP_SEQ_ENUM(BOOST_PP_SEQ_TRANSFORM(               \
 876     ARGIFY, _, IBOOST_PP_VARIADIC_TO_SEQ(__VA_ARGS__))))
 877
 878 #define STL_TEST_I(ref, name, restriction, ...)                               \
 879   DECL(name, __VA_ARGS__);                                                    \
 880   MAKE_TEST(ref, name, TEST_TYPES, restriction,                               \
 881     IBOOST_PP_VARIADIC_TO_SEQ(__VA_ARGS__), __VA_ARGS__)                      \
 882   DECL(name, __VA_ARGS__)
 883
 884 #define STL_TEST(ref, name, restriction, ...) \
 885   STL_TEST_I(ref, name, restriction, z, ## __VA_ARGS__, ticks)
 886
 887 //-----------------------------------------------------------------------------
 888 // Test Types
 889
 890 typedef Data<> ED1;
 891 typedef Data<0, 4080> ED2;
 892 typedef Data<MC_NOEXCEPT> ED3;
 893 typedef Data<MC_NOEXCEPT | CC_DELETE> ED4;
 894 typedef Data<IS_RELOCATABLE> ED5;
 895
 896 typedef VECTOR_<int, std::allocator<int>> _TVIS;
 897 typedef VECTOR_<int, Alloc<int>> _TVI;
 898 typedef VECTOR_<ED1, std::allocator<ED1>> _TV1;
 899 typedef VECTOR_<ED2, std::allocator<ED2>> _TV2;
 900 typedef VECTOR_<ED3, std::allocator<ED3>> _TV3;
 901 typedef VECTOR_<ED4, std::allocator<ED4>> _TV4;
 902 typedef VECTOR_<ED5, std::allocator<ED5>> _TV5v1;
 903 typedef VECTOR_<ED5, Alloc<ED5>> _TV5;
 904
 905 typedef Data<PROP_COPY> EP1;
 906 typedef Data<PROP_MOVE> EP2;
 907 typedef Data<PROP_SWAP> EP3;
 908
 909 typedef VECTOR_<EP1, Alloc<EP1>> _TP1;
 910 typedef VECTOR_<EP2, Alloc<EP2>> _TP2;
 911 typedef VECTOR_<EP3, Alloc<EP3>> _TP3;
 912
 913 #define TEST_TYPES (_TVIS)(_TVI)(_TV1)(_TV2)(_TV3)(_TV4)(_TV5v1)(_TV5) \
 914   (_TP1)(_TP2)(_TP3)
 915
 916 typedef Data<ALL_DELETE> DD1; // unoperable
 917 typedef Data<DC_DELETE | CC_DELETE | MC_DELETE> DD2; // unconstructible
 918 typedef Data<CA_DELETE | MA_DELETE> DD3; // unassignable
 919 typedef Data<CC_DELETE | MC_DELETE> DD4; // uncopyable
 920 typedef Data<ALL_DELETE & ~DC_DELETE> DD5; // only default constructible
 921 typedef Data<CC_DELETE> DD6; // move-only copy construction
 922 typedef Data<CA_DELETE> DD7; // move-only assignment
 923
 924 typedef Data<ALL_DELETE | PROP_MOVE> DDSMA;
 925 typedef VECTOR_<DDSMA, Alloc<DDSMA>> _TSpecialMA;
 926
 927 #define INTERFACE_TYPES \
 928   (_TVI)(VECTOR_<DD1>)(VECTOR_<DD2>)(VECTOR_<DD3>) \
 929   (VECTOR_<DD4>)(VECTOR_<DD5>)(VECTOR_<DD6>) \
 930   (VECTOR_<DD7>)(_TSpecialMA)
 931
 932 //-----------------------------------------------------------------------------
 933 // Pretty printers
 934
 935 template <typename T>
 936 struct PrettyType {
 937   string operator()() {
 938     if (is_same<T, int>::value) return "int";
 939     if (is_same<T, char>::value) return "char";
 940     if (is_same<T, uint64_t>::value) return "uint64_t";
 941     return typeid(T).name();
 942   }
 943 };
 944
 945 template <Flags f, size_t pad>
 946 struct PrettyType<Data<f, pad>> {
 947   string operator()() {
 948     stringstream tpe;
 949     tpe << "Data";
 950
 951     if ((f & DC_DELETE) ||
 952         (f & CC_DELETE) ||
 953         (f & MC_DELETE) ||
 954         (f & CA_DELETE) ||
 955         (f & MA_DELETE)) {
 956       tpe << "[^";
 957       if (f & DC_DELETE) tpe << " DC,";
 958       if (f & CC_DELETE) tpe << " CC,";
 959       if (f & MC_DELETE) tpe << " MC,";
 960       if (f & CA_DELETE) tpe << " CA,";
 961       if (f & MA_DELETE) tpe << " MA,";
 962       tpe << "]";
 963     }
 964
 965     if ((f & DC_NOEXCEPT) ||
 966         (f & CC_NOEXCEPT) ||
 967         (f & MC_NOEXCEPT) ||
 968         (f & CA_NOEXCEPT) ||
 969         (f & MA_NOEXCEPT)) {
 970       tpe << "[safe";
 971       if (f & DC_NOEXCEPT) tpe << " DC,";
 972       if (f & CC_NOEXCEPT) tpe << " CC,";
 973       if (f & MC_NOEXCEPT) tpe << " MC,";
 974       if (f & CA_NOEXCEPT) tpe << " CA,";
 975       if (f & MA_NOEXCEPT) tpe << " MA,";
 976       tpe << "]";
 977     }
 978
 979     if (f & IS_RELOCATABLE) {
 980       tpe << "(relocatable)";
 981     }
 982
 983     if (pad != 0) {
 984       tpe << "{pad " << pad << "}";
 985     }
 986
 987     return tpe.str();
 988   }
 989 };
 990
 991 template <typename T>
 992 struct PrettyType<std::allocator<T>> {
 993   string operator()() {
 994     return "std::allocator<" + PrettyType<T>()() + ">";
 995   }
 996 };
 997
 998 template <typename T>
 999 struct PrettyType<Alloc<T>> {
1000   string operator()() {
1001     return "Alloc<" + PrettyType<T>()() + ">";
1002   }
1003 };
1004
1005 //-----------------------------------------------------------------------------
1006 // Setup, teardown, runup, rundown
1007
1008 // These four macros are run once per test. Setup and runup occur before the
1009 // test, teardown and rundown after. Setup and runup straddle the
1010 // initialization sequence, whereas rundown and teardown straddle the
1011 // cleanup.
1012
1013 #define SETUP hardReset();
1014 #define TEARDOWN
1015
1016 //-----------------------------------------------------------------------------
1017 // Types and typegens
1018
1019 //------
1020 // dummy
1021
1022 #define TYPIFY_z std::nullptr_t
1023 #define LOOPER_z                                 \
1024   Vector* a_p = nullptr; Vector* b_p = nullptr;  \
1025   typename Vector::value_type* t_p = nullptr;
1026 #define VMAKER_z std::nullptr_t z = nullptr;
1027 #define UMAKER_z                                                      \
1028   verify<Vector>(0);                                                  \
1029   if (::testing::Test::HasFatalFailure()) return;
1030 #define CLOSER_z
1031
1032 //------
1033 // ticks
1034
1035 #define VERIFICATION                                        \
1036   if (b_p != nullptr) verify(t_p != nullptr ,*a_p, *b_p);   \
1037   else if (a_p != nullptr) verify(t_p != nullptr, *a_p);    \
1038   else verify<Vector>(t_p != nullptr);                      \
1039   if (::testing::Test::HasFatalFailure()) return;
1040
1041 #define TYPIFY_ticks int
1042 #define LOOPER_ticks          \
1043   int _maxTicks_ = 0;         \
1044   bool ticks_thrown = false;  \
1045   for (int ticks = -1; ticks < _maxTicks_; ++ticks) {
1046 #define VMAKER_ticks                                        \
1047   string ticks_st = folly::to<string>("ticks = ", ticks);   \
1048   SCOPED_TRACE(ticks_st);                                   \
1049   { SCOPED_TRACE("pre-run verification");                   \
1050     VERIFICATION }                                          \
1051   try {                                                     \
1052     softReset(ticks);
1053 #define UMAKER_ticks _maxTicks_ = Ticker::CountTicks; }           \
1054   catch (const TickException&) { ticks_thrown = true; }           \
1055   catch (const std::exception& e)                                 \
1056     { FAIL() << "EXCEPTION: " << e.what(); }                      \
1057   catch (...)                                                     \
1058     { FAIL() << "UNKNOWN EXCEPTION"; }                            \
1059   if (ticks >= 0 && Ticker::CountTicks > ticks && !ticks_thrown)  \
1060     FAIL() << "CountTicks = " << Ticker::CountTicks << " > "      \
1061            << ticks << " = ticks"                                 \
1062            << ", but no tick error was observed";                 \
1063   VERIFICATION
1064 #define CLOSER_ticks }
1065
1066
1067 //--------------------------------------------------
1068 // vectors (second could be .equal, ==, or distinct)
1069
1070 static const vector<pair<int, int>> VectorSizes = {
1071   {  0, -1},
1072   {  1, -1},
1073   {  2, -1},
1074   { 10, -1}, { 10, 1}, { 10, 0},
1075   {100, -1}, {100, 1},
1076
1077   //{   10, -1}, {   10, 0}, {   10, 1}, {   10, 2}, {   10, 10},
1078   //{  100, -1}, {  100, 0}, {  100, 1}, {  100, 2}, {  100, 10}, {  100, 100},
1079   //{ 1000, -1}, { 1000, 0}, { 1000, 1}, { 1000, 2}, { 1000, 10}, { 1000, 100},
1080   //  { 1000, 1000},
1081 };
1082
1083 int populateIndex = 1426;
1084 template <class Vector>
1085 void populate(Vector& v, const pair<int, int>& ss) {
1086   int i = 0;
1087   for (; i < ss.first; ++i) {
1088     v.emplace_back(populateIndex++);
1089   }
1090   if (ss.second >= 0) {
1091     while (v.capacity() - v.size() != ss.second) {
1092       v.emplace_back(populateIndex++);
1093     }
1094   }
1095 }
1096
1097 template <typename A>
1098 struct allocGen {
1099   static A get() { return A(); }
1100 };
1101 template <typename T>
1102 struct allocGen<Alloc<T>> {
1103   static Alloc<T> get() {
1104     static int c = 0;
1105     c += 854;
1106     return Alloc<T>(c);
1107   }
1108 };
1109
1110 #define TYPIFY_a Vector&
1111 #define LOOPER_a for (const auto& a_ss : VectorSizes) {
1112 #define VMAKER_a                                                            \
1113   Vector a(allocGen<typename Vector::allocator_type>::get());               \
1114   a_p = &a;                                                                 \
1115   populate(*a_p, a_ss);                                                     \
1116   string a_st = folly::to<string>("a (", a.size(), "/", a.capacity(), ")"); \
1117   SCOPED_TRACE(a_st);
1118 #define UMAKER_a verify(0, a); if (::testing::Test::HasFatalFailure()) return;
1119 #define CLOSER_a }
1120
1121 #define TYPIFY_b Vector&
1122 #define LOOPER_b for (int b_i = -2; b_i < (int)VectorSizes.size(); ++b_i) {
1123 #define VMAKER_b                                                            \
1124   Vector b_s(allocGen<typename Vector::allocator_type>::get());             \
1125   b_p = &b_s; string b_st;                                                  \
1126   if (b_i == -2) {                                                          \
1127     b_p = &a;                                                               \
1128     b_st = "b is an alias of a";                                            \
1129   }                                                                         \
1130   else if (b_i == -1) {                                                     \
1131     b_s.~Vector();                                                          \
1132     new (&b_s) Vector(a);                                                   \
1133     b_st = "b is a deep copy of a";                                         \
1134   }                                                                         \
1135   else {                                                                    \
1136     populate(b_s, VectorSizes[b_i]);                                        \
1137     b_st = folly::to<string>("b (", b_s.size(), "/", b_s.capacity(), ")");  \
1138   }                                                                         \
1139   Vector& b = *b_p;                                                         \
1140   SCOPED_TRACE(b_st);
1141 #define UMAKER_b \
1142   verify(0, a, b); if (::testing::Test::HasFatalFailure()) return;
1143 #define CLOSER_b }
1144
1145 //----
1146 // int
1147
1148 static const vector<int> nSizes = { 0, 1, 2, 9, 10, 11 };
1149
1150 #define TYPIFY_n int
1151 #define LOOPER_n for (int n : nSizes) {
1152 #define VMAKER_n \
1153   string n_st = folly::to<string>("n = ", n); SCOPED_TRACE(n_st);
1154 #define UMAKER_n
1155 #define CLOSER_n }
1156
1157 //-----------------------
1158 // non-internal iterators
1159
1160 static int ijarr[12] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
1161 static int ijarC[12] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
1162
1163 #define TYPIFY_i int*
1164 #define LOOPER_i
1165 #define VMAKER_i int* i = ijarr; SCOPED_TRACE("i = fib[0]");
1166 #define UMAKER_i
1167 #define CLOSER_i
1168
1169 #define TYPIFY_j int*
1170 #define LOOPER_j for (int j_i = 0; j_i < 12; ++j_i) {
1171 #define VMAKER_j                                          \
1172   int* j = ijarr + j_i;                                   \
1173   string j_st = folly::to<string>("j = fib[", j_i, "]");  \
1174   SCOPED_TRACE(j_st);
1175 #define UMAKER_j \
1176   for (int j_c = 0; j_c < 12; ++j_c) ASSERT_EQ(ijarC[j_c], ijarr[j_c]);
1177 #define CLOSER_j }
1178
1179 //-------------------
1180 // internal iterators
1181
1182 template <class Vector>
1183 std::pair<typename Vector::iterator, string>
1184 iterSpotter(Vector& v, int i) {
1185   typename Vector::iterator it;
1186   string msg;
1187
1188   switch(i) {
1189   case 1:
1190     if (v.empty()) ; // fall through
1191     else {
1192       it = v.begin();
1193       ++it;
1194       msg = "a[1]";
1195       break;
1196     }
1197   case 0:
1198     it = v.begin();
1199     msg = "a.begin";
1200     break;
1201
1202   case 2:
1203     if (v.empty()) ; // fall through
1204     else {
1205       it = v.end();
1206       --it;
1207       msg = "a[-1]";
1208       break;
1209     }
1210   case 3:
1211     it = v.end();
1212     msg = "a.end";
1213     break;
1214
1215   default:
1216     cerr << "internal error" << endl;
1217     exit(1);
1218   }
1219
1220   return make_pair(it, msg);
1221 }
1222
1223 #define TYPIFY_p typename Vector::iterator
1224 #define LOOPER_p for (int p_i = 0; p_i < 4; ++p_i) {
1225 #define VMAKER_p                    \
1226   auto p_im = iterSpotter(a, p_i);  \
1227   auto& p = p_im.first;             \
1228   auto& p_m = p_im.second;          \
1229   SCOPED_TRACE("p = " + p_m);
1230 #define UMAKER_p
1231 #define CLOSER_p }
1232
1233 #define TYPIFY_q typename Vector::iterator
1234 #define LOOPER_q for (int q_i = p_i; q_i < 4; ++q_i) {
1235 #define VMAKER_q                    \
1236   auto q_im = iterSpotter(a, q_i);  \
1237   auto& q = q_im.first;             \
1238   auto& q_m = q_im.second;          \
1239   SCOPED_TRACE("q = " + q_m);
1240 #define UMAKER_q
1241 #define CLOSER_q }
1242
1243 //---------
1244 // datatype
1245
1246 static const vector<int> tVals = { 0, 1, 2, 3, 17, 66, 521 };
1247
1248 #define TYPIFY_t typename Vector::value_type&
1249 #define LOOPER_t for (int t_v : tVals) {
1250 #define VMAKER_t                                                            \
1251   typename Vector::value_type t_s(t_v);                                     \
1252   t_p = addressof(t_s);                                                     \
1253   string t_st = folly::to<string>("t(", t_v, ")");                          \
1254   if (t_v < 4 && a_p != nullptr) {                                          \
1255     auto t_im = iterSpotter(*a_p, t_v);                                     \
1256     if (t_im.first != a_p->end()) {                                         \
1257       t_p = addressof(*t_im.first);                                         \
1258       t_st = "t is " + t_im.second;                                         \
1259     }                                                                       \
1260   }                                                                         \
1261   typename Vector::value_type& t = *t_p;                                    \
1262   SCOPED_TRACE(t_st);
1263 #define UMAKER_t
1264 #define CLOSER_t }
1265
1266 //----------
1267 // allocator
1268
1269 #define TYPIFY_m typename Vector::allocator_type
1270 #define LOOPER_m                          \
1271   int m_max = 1 + (a_p != nullptr);       \
1272   for (int m_i = 0; m_i < m_max; ++m_i) {
1273 #define VMAKER_m                                \
1274   typename Vector::allocator_type m = m_i == 0  \
1275     ? typename Vector::allocator_type()         \
1276     : a_p->get_allocator();
1277 #define UMAKER_m
1278 #define CLOSER_m }
1279
1280 //-----------------------------------------------------------------------------
1281 // Verifiers
1282
1283 // verify a vector
1284 template <class Vector>
1285 void verifyVector(const Vector& v) {
1286   ASSERT_TRUE(v.begin() <= v.end()) << "end is before begin";
1287   ASSERT_TRUE(v.empty() == (v.begin() == v.end())) << "empty != (begin == end)";
1288   ASSERT_TRUE(v.size() == distance(v.begin(), v.end()))
1289     << "size != end - begin";
1290   ASSERT_TRUE(v.size() <= v.capacity()) << "size > capacity";
1291   ASSERT_TRUE(v.capacity() <= v.max_size()) << "capacity > max_size";
1292   ASSERT_TRUE(v.data() || true); // message won't print - it will just crash
1293   ASSERT_TRUE(v.size() == 0 || v.data() != nullptr)
1294     << "nullptr data points to at least one element";
1295 }
1296
1297 void verifyAllocator(int ele, int cap) {
1298   ASSERT_EQ(ele, AllocTracker::Constructed - AllocTracker::Destroyed);
1299
1300   int tot = 0;
1301   for (auto kv : AllocTracker::Allocated)
1302     if (kv.second != -1) tot += kv.second;
1303   ASSERT_EQ(cap, tot) << "the allocator counts " << tot << " space, "
1304     "but the vector(s) have (combined) capacity " << cap;
1305 }
1306
1307 // Master verifier
1308 template <class Vector>
1309 void verify(int extras) {
1310   if (!is_arithmetic<typename Vector::value_type>::value)
1311     ASSERT_EQ(0 + extras, getTotal()) << "there exist Data but no vectors";
1312   isSane();
1313   if (::testing::Test::HasFatalFailure()) return;
1314   if (customAllocator<Vector>::value) verifyAllocator(0, 0);
1315 }
1316 template <class Vector>
1317 void verify(int extras, const Vector& v) {
1318   verifyVector(v);
1319   if (!is_arithmetic<typename Vector::value_type>::value)
1320     ASSERT_EQ(v.size() + extras, getTotal())
1321       << "not all Data are in the vector";
1322   isSane();
1323   if (::testing::Test::HasFatalFailure()) return;
1324   if (customAllocator<Vector>::value) verifyAllocator(v.size(), v.capacity());
1325 }
1326 template <class Vector>
1327 void verify(int extras, const Vector& v1, const Vector& v2) {
1328   verifyVector(v1);
1329   verifyVector(v2);
1330   auto size = v1.size();
1331   auto cap = v1.capacity();
1332   if (&v1 != &v2) {
1333     size += v2.size();
1334     cap += v2.capacity();
1335   }
1336   if (!is_arithmetic<typename Vector::value_type>::value)
1337     ASSERT_EQ(size + extras, getTotal()) << "not all Data are in the vector(s)";
1338   isSane();
1339   if (::testing::Test::HasFatalFailure()) return;
1340   if (customAllocator<Vector>::value) verifyAllocator(size, cap);
1341 }
1342
1343 //=============================================================================
1344 // Helpers
1345
1346 // save the state of a vector
1347 int convertToInt(int t) {
1348   return t;
1349 }
1350 template <Flags f, size_t pad>
1351 int convertToInt(const Data<f, pad>& t) {
1352   return t.uid;
1353 }
1354 template <typename T>
1355 int convertToInt(const std::allocator<T>&) {
1356   return -1;
1357 }
1358 template <typename T>
1359 int convertToInt(const Alloc<T>& a) {
1360   return a.id;
1361 }
1362
1363 template <class Vector>
1364 class DataState {
1365   typedef typename Vector::size_type size_type;
1366   size_type size_;
1367   int* data_;
1368 public:
1369   /* implicit */ DataState(const Vector& v) {
1370     size_ = v.size();
1371     if (size_ != 0) {
1372       data_ = new int[size_];
1373       for (size_type i = 0; i < size_; ++i) {
1374         data_[i] = convertToInt(v.data()[i]);
1375       }
1376     } else {
1377       data_ = nullptr;
1378     }
1379   }
1380   ~DataState() {
1381     delete[] data_;
1382   }
1383
1384   bool operator==(const DataState& o) const {
1385     if (size_ != o.size_) return false;
1386     for (size_type i = 0; i < size_; ++i) {
1387       if (data_[i] != o.data_[i]) return false;
1388     }
1389     return true;
1390   }
1391
1392   int operator[](size_type i) {
1393     if (i >= size_) {
1394       cerr << "trying to access DataState out of bounds" << endl;
1395       exit(1);
1396     }
1397     return data_[i];
1398   }
1399
1400   size_type size() { return size_; }
1401 };
1402
1403 // downgrade iterators
1404 template <typename It, class tag>
1405 class Transformer : public boost::iterator_adaptor<
1406                             Transformer<It, tag>,
1407                             It,
1408                             typename iterator_traits<It>::value_type,
1409                             tag
1410                            > {
1411   friend class boost::iterator_core_access;
1412   shared_ptr<set<It>> dereferenced;
1413
1414 public:
1415   explicit Transformer(const It& it)
1416     : Transformer::iterator_adaptor_(it)
1417     , dereferenced(new set<It>()) {}
1418
1419   typename iterator_traits<It>::value_type& dereference() const {
1420     if (dereferenced->find(this->base_reference()) != dereferenced->end()) {
1421       cerr << "iterator dereferenced more than once" << endl;
1422       exit(1);
1423     }
1424     dereferenced->insert(this->base_reference());
1425     return *this->base_reference();
1426   }
1427 };
1428
1429 template <typename It>
1430 Transformer<It, forward_iterator_tag> makeForwardIterator(const It& it) {
1431   return Transformer<It, forward_iterator_tag>(it);
1432 }
1433 template <typename It>
1434 Transformer<It, input_iterator_tag> makeInputIterator(const It& it) {
1435   return Transformer<It, input_iterator_tag>(it);
1436 }
1437
1438 // mutate a value (in contract only)
1439 void mutate(int& i) {
1440   if (false) i = 0;
1441 }
1442 void mutate(uint64_t& i) {
1443   if (false) i = 0;
1444 }
1445 template <Flags f, size_t pad>
1446 void mutate(Data<f, pad>& ds) {
1447   if (false) ds.uid = 0;
1448 }
1449
1450 //=============================================================================
1451 // Tests
1452
1453 // #if 0
1454
1455
1456
1457 // #else
1458
1459 //-----------------------------------------------------------------------------
1460 // Container
1461
1462 STL_TEST("23.2.1 Table 96.1-7", containerTypedefs, is_destructible) {
1463   static_assert(is_same<T, typename Vector::value_type>::value,
1464     "T != Vector::value_type");
1465   static_assert(is_same<T&, typename Vector::reference>::value,
1466     "T& != Vector::reference");
1467   static_assert(is_same<const T&, typename Vector::const_reference>::value,
1468     "const T& != Vector::const_reference");
1469   static_assert(is_convertible<
1470       typename iterator_traits<typename Vector::iterator>::iterator_category,
1471       forward_iterator_tag>::value,
1472     "Vector::iterator is not a forward iterator");
1473   static_assert(is_same<T,
1474       typename iterator_traits<typename Vector::iterator>::value_type>::value,
1475     "Vector::iterator does not iterate over type T");
1476   static_assert(is_convertible<
1477       typename iterator_traits<typename Vector::const_iterator>
1478         ::iterator_category,
1479       forward_iterator_tag>::value,
1480     "Vector::const_iterator is not a forward iterator");
1481   static_assert(is_same<T,
1482       typename iterator_traits<typename Vector::const_iterator>
1483         ::value_type>::value,
1484     "Vector::const_iterator does not iterate over type T");
1485   static_assert(is_convertible<
1486       typename Vector::iterator, typename Vector::const_iterator>::value,
1487     "Vector::iterator is not convertible to Vector::const_iterator");
1488   static_assert(is_signed<typename Vector::difference_type>::value,
1489     "Vector::difference_type is not signed");
1490   static_assert(is_same<typename Vector::difference_type,
1491         typename iterator_traits<typename Vector::iterator>
1492       ::difference_type>::value,
1493     "Vector::difference_type != Vector::iterator::difference_type");
1494   static_assert(is_same<typename Vector::difference_type,
1495         typename iterator_traits<typename Vector::const_iterator>
1496       ::difference_type>::value,
1497     "Vector::difference_type != Vector::const_iterator::difference_type");
1498   static_assert(is_unsigned<typename Vector::size_type>::value,
1499     "Vector::size_type is not unsigned");
1500   static_assert(sizeof(typename Vector::size_type) >=
1501       sizeof(typename Vector::difference_type),
1502     "Vector::size_type is smaller than Vector::difference_type");
1503 }
1504
1505 STL_TEST("23.2.1 Table 96.8-9", emptyConstruction, is_destructible) {
1506   Vector u;
1507
1508   ASSERT_TRUE(u.get_allocator() == Allocator());
1509   ASSERT_EQ(0, Counter::CountTotalOps);
1510
1511   ASSERT_TRUE(u.empty()) << u.size();
1512   ASSERT_EQ(0, u.capacity());
1513
1514   if (false) {
1515     Vector();
1516   }
1517 }
1518
1519 STL_TEST("framework", populate, is_copy_constructible) {
1520   // We use emplace_back to construct vectors for testing, as well as size,
1521   // data, and capacity. We make sure these work before proceeding with tests.
1522
1523   Vector u;
1524   ASSERT_EQ(0, u.size());
1525   ASSERT_EQ(nullptr, u.data());
1526
1527   u.emplace_back(17);
1528   ASSERT_EQ(1, u.size());
1529   ASSERT_LT(u.capacity(), 100)
1530     << "single push_back increased capacity to " << u.capacity();
1531   ASSERT_NE(nullptr, u.data());
1532   ASSERT_EQ(17, convertToInt(u.data()[0]))
1533     << "first object did not get emplaced correctly";
1534
1535   for (int i = 0; i < 3; ++i) {
1536     auto cap = u.capacity();
1537     while (u.size() < cap) {
1538       u.emplace_back(22);
1539       ASSERT_EQ(cap, u.capacity()) << "Vector grew when it did not need to";
1540       ASSERT_EQ(22, convertToInt(u.data()[u.size() - 1]))
1541         << "push_back with excess capacity failed";
1542     }
1543
1544     ASSERT_EQ(cap, u.size());
1545
1546     u.emplace_back(4);
1547     ASSERT_GT(u.capacity(), cap) << "capacity did not grow on overflow";
1548     ASSERT_EQ(cap + 1, u.size());
1549     ASSERT_EQ(4, convertToInt(u.data()[u.size() - 1]))
1550       << "grow object did not get emplaced correctly";
1551   }
1552 }
1553
1554 STL_TEST("23.2.1 Table 96.10-11", copyConstruction,
1555           is_copy_constructible, a) {
1556   const auto& ca = a;
1557   DataState<Vector> dsa(ca);
1558   auto am = a.get_allocator();
1559
1560   Vector u(ca);
1561
1562   ASSERT_TRUE(std::allocator_traits<Allocator>::
1563     select_on_container_copy_construction(am) == u.get_allocator());
1564   ASSERT_TRUE(dsa == u);
1565   ASSERT_TRUE(
1566     (ca.data() == nullptr && u.data() == nullptr) ||
1567     (ca.data() != u.data())
1568   ) << "only a shallow copy was made";
1569
1570   if (false) {
1571     Vector(ca);
1572     Vector u = ca;
1573   }
1574 }
1575
1576 STL_TEST("23.2.1 Table 96.12", moveConstruction, is_destructible, a) {
1577   DataState<Vector> dsa(a);
1578   auto m = a.get_allocator();
1579
1580   Vector u(move(a));
1581
1582   ASSERT_TRUE(m == u.get_allocator());
1583   ASSERT_EQ(0, Counter::CountTotalOps);
1584
1585   ASSERT_TRUE(dsa == u);
1586
1587   if (false) {
1588     Vector u = move(a);
1589   }
1590 }
1591
1592 STL_TEST("23.2.1 Table 96.13", moveAssignment, special_move_assignable, a, b) {
1593   DataState<Vector> dsb(b);
1594   auto am = a.get_allocator();
1595   auto bm = b.get_allocator();
1596
1597   Vector& ret = a = std::move(b);
1598
1599   if (std::allocator_traits<Allocator>::
1600       propagate_on_container_move_assignment::value) {
1601     ASSERT_TRUE(bm == a.get_allocator());
1602   } else {
1603     ASSERT_TRUE(am == a.get_allocator());
1604   }
1605   ASSERT_TRUE(&ret == &a);
1606   ASSERT_TRUE(&a == &b || dsb == a) << "move assignment did not create a copy";
1607   // The source of the move may be left in any (albeit valid) state.
1608 }
1609
1610 STL_TEST("23.2.1 Table 96.14", destructible, is_destructible) {
1611   // The test generators check this clause already.
1612 }
1613
1614 STL_TEST("23.2.1 Table 96.15-18", iterators, is_destructible, a) {
1615   DataState<Vector> dsa(a);
1616   const auto& ca = a;
1617
1618   auto  itb =  a.begin();
1619   auto citb = ca.begin();
1620   auto Citb =  a.cbegin();
1621   auto  ite =  a.end();
1622   auto cite = ca.end();
1623   auto Cite =  a.cend();
1624
1625   ASSERT_EQ(0, Counter::CountTotalOps);
1626
1627   ASSERT_TRUE(dsa == a) << "call to begin or end modified internal data";
1628
1629   ASSERT_TRUE(citb == Citb) << "cv.begin != v.cbegin";
1630   ASSERT_TRUE(cite == Cite) << "cv.end != v.cend";
1631
1632   if (ca.size() == 0) {
1633     ASSERT_TRUE( itb ==  ite) << "begin != end when empty";
1634     ASSERT_TRUE(Citb == Cite) << "cbegin != cend when empty";
1635   } else {
1636     ASSERT_TRUE( itb !=  ite) << "begin == end when non-empty";
1637     ASSERT_TRUE(Citb != Cite) << "cbegin == cend when non-empty";
1638   }
1639
1640   auto  dist = std::distance( itb,  ite);
1641   auto Cdist = std::distance(Citb, Cite);
1642   ASSERT_TRUE( dist == ca.size()) << "distance(begin, end) != size";
1643   ASSERT_TRUE(Cdist == ca.size()) << "distance(cbegin, cend) != size";
1644 }
1645
1646 STL_TEST("23.2.1 Table 96.19-20", equitable, is_arithmetic, a, b) {
1647   const auto& ca = a;
1648   const auto& cb = b;
1649   DataState<Vector> dsa(a);
1650   DataState<Vector> dsb(b);
1651
1652   ASSERT_TRUE((bool)(ca == cb) == (bool)(dsa == dsb))
1653     << "== does not return equality";
1654   ASSERT_TRUE((bool)(ca == cb) != (bool)(ca != cb))
1655     << "!= is not the opposite of ==";
1656
1657   // Data is uncomparable, by design; therefore this test's restriction
1658   // is 'is_arithmetic'
1659 }
1660
1661 STL_TEST("23.2.1 Table 96.21", memberSwappable, is_destructible, a, b) {
1662   if (!std::allocator_traits<Allocator>::
1663         propagate_on_container_swap::value &&
1664       convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1665     // undefined behaviour
1666     return;
1667   }
1668
1669   DataState<Vector> dsa(a);
1670   DataState<Vector> dsb(b);
1671   auto adata = a.data();
1672   auto bdata = b.data();
1673   auto am = a.get_allocator();
1674   auto bm = b.get_allocator();
1675
1676   try {
1677     a.swap(b);
1678   } catch (...) {
1679     FAIL() << "swap is noexcept";
1680   }
1681
1682   if (std::allocator_traits<Allocator>::
1683       propagate_on_container_swap::value) {
1684     ASSERT_TRUE(bm == a.get_allocator());
1685     ASSERT_TRUE(am == b.get_allocator());
1686   } else {
1687     ASSERT_TRUE(am == a.get_allocator());
1688     ASSERT_TRUE(bm == b.get_allocator());
1689   }
1690   ASSERT_EQ(0, Counter::CountTotalOps);
1691
1692   ASSERT_TRUE(adata == b.data() && bdata == a.data());
1693   ASSERT_TRUE(dsa == b && dsb == a) << "swap did not swap";
1694 }
1695
1696 STL_TEST("23.2.1 Table 96.22", nonmemberSwappable,
1697          is_destructible, a, b) {
1698   if (!std::allocator_traits<Allocator>::
1699         propagate_on_container_swap::value &&
1700       convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1701     // undefined behaviour
1702     return;
1703   }
1704
1705   DataState<Vector> dsa(a);
1706   DataState<Vector> dsb(b);
1707   auto adata = a.data();
1708   auto bdata = b.data();
1709   auto am = a.get_allocator();
1710   auto bm = b.get_allocator();
1711
1712   try {
1713     swap(a, b);
1714   } catch (...) {
1715     FAIL() << "swap is noexcept";
1716   }
1717
1718   if (std::allocator_traits<Allocator>::
1719       propagate_on_container_swap::value) {
1720     ASSERT_TRUE(bm == a.get_allocator());
1721     ASSERT_TRUE(am == b.get_allocator());
1722   } else {
1723     ASSERT_TRUE(am == a.get_allocator());
1724     ASSERT_TRUE(bm == b.get_allocator());
1725   }
1726   ASSERT_EQ(0, Counter::CountTotalOps);
1727
1728   ASSERT_TRUE(adata == b.data() && bdata == a.data());
1729   ASSERT_TRUE(dsa == b && dsb == a) << "swap did not swap";
1730 }
1731
1732 STL_TEST("23.2.1 Table 96.23", copyAssign,
1733           is_copy_constructibleAndAssignable, a, b) {
1734   // it is possible to make use of just the copy constructor.
1735
1736   #ifdef USING_STD_VECTOR
1737   if (std::allocator_traits<Allocator>::
1738         propagate_on_container_copy_assignment::value &&
1739       convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1740     // Bug. By the looks of things, in the above case, their bez is being
1741     // cleared and deallocated, but then the garbage pointers are being used.
1742     return;
1743   }
1744   #endif
1745
1746   const auto& cb = b;
1747   DataState<Vector> dsb(cb);
1748   auto am = a.get_allocator();
1749   auto bm = b.get_allocator();
1750
1751   Vector& ret = a = cb;
1752
1753   if (std::allocator_traits<Allocator>::
1754       propagate_on_container_copy_assignment::value) {
1755     ASSERT_TRUE(bm == a.get_allocator());
1756   } else {
1757     ASSERT_TRUE(am == a.get_allocator());
1758   }
1759   ASSERT_TRUE(&ret == &a);
1760   ASSERT_TRUE(dsb == a) << "copy-assign not equal to original";
1761 }
1762
1763 STL_TEST("23.2.1 Table 96.24-26", sizeops, is_destructible) {
1764   // This check generators check this clause already.
1765 }
1766
1767 //-----------------------------------------------------------------------------
1768 // Reversible container
1769
1770 STL_TEST("23.2.1 Table 97.1-2", reversibleContainerTypedefs,
1771           is_destructible) {
1772   static_assert(is_same<typename Vector::reverse_iterator,
1773       std::reverse_iterator<typename Vector::iterator>>::value,
1774     "Vector::reverse_iterator != reverse_iterator<Vector:iterator");
1775   static_assert(is_same<typename Vector::const_reverse_iterator,
1776       std::reverse_iterator<typename Vector::const_iterator>>::value,
1777     "Vector::const_reverse_iterator != "
1778     "const_reverse_iterator<Vector::iterator");
1779 }
1780
1781 STL_TEST("23.2.1 Table 97.3-5", reversibleIterators, is_destructible, a) {
1782   const auto& ca = a;
1783   DataState<Vector> ds(a);
1784
1785   auto  ritb =  a.rbegin();
1786   auto critb = ca.rbegin();
1787   auto Critb =  a.crbegin();
1788   auto  rite =  a.rend();
1789   auto crite = ca.rend();
1790   auto Crite =  a.crend();
1791
1792   ASSERT_EQ(0, Counter::CountTotalOps);
1793
1794   ASSERT_TRUE(ds == a) << "call to rbegin or rend modified internal data";
1795
1796   ASSERT_TRUE(critb == Critb) << "cv.rbegin != v.crbegin";
1797   ASSERT_TRUE(crite == Crite) << "cv.rend != v.crend";
1798
1799   if (ca.size() == 0) {
1800     ASSERT_TRUE( ritb ==  rite) << "rbegin != rend when empty";
1801     ASSERT_TRUE(Critb == Crite) << "crbegin != crend when empty";
1802   } else {
1803     ASSERT_TRUE( ritb !=  rite) << "rbegin == rend when non-empty";
1804     ASSERT_TRUE(Critb != Crite) << "crbegin == crend when non-empty";
1805   }
1806
1807   auto  dist = std::distance( ritb,  rite);
1808   auto Cdist = std::distance(Critb, Crite);
1809   ASSERT_TRUE( dist == ca.size()) << "distance(rbegin, rend) != size";
1810   ASSERT_TRUE(Cdist == ca.size()) << "distance(crbegin, crend) != size";
1811 }
1812
1813 //-----------------------------------------------------------------------------
1814 // Lexicographical functions
1815
1816 STL_TEST("23.2.1 Table 98", comparable, is_arithmetic) {
1817   const Vector v1 = { 1, 2, 3, 4 };
1818   const Vector v2 = { 1, 2, 3, 4, 5 };
1819   const Vector v3 = { 1, 2, 2 };
1820   const Vector v4 = { 1, 2, 2, 4, 5 };
1821   const Vector v5 = { };
1822   const Vector v6 = { 1, 2, 3, 4 };
1823
1824   ASSERT_TRUE(v1 < v2);
1825   ASSERT_TRUE(v1 > v3);
1826   ASSERT_TRUE(v1 > v4);
1827   ASSERT_TRUE(v1 > v5);
1828   ASSERT_TRUE(v1 <= v6);
1829   ASSERT_TRUE(v1 >= v6);
1830 }
1831
1832 //-----------------------------------------------------------------------------
1833 // Allocator-aware requirements (AA)
1834
1835 STL_TEST("23.2.1 Table 99.1", allocatorTypedefs, is_destructible) {
1836   static_assert(is_same<T, typename Vector::allocator_type::value_type>::value,
1837     "Vector and vector's allocator value_type mismatch");
1838 }
1839
1840 STL_TEST("23.2.1 Table 99.2", getAllocator, is_destructible) {
1841   // whitebox: ensure that a.get_allocator() returns a copy of its allocator
1842 }
1843
1844 STL_TEST("23.2.1 Table 99.3", defaultAllocator, is_destructible) {
1845   // there is nothing new to test here
1846 }
1847
1848 STL_TEST("23.2.1 Table 99.4", customAllocator, is_destructible, m) {
1849   const auto& cm = m;
1850
1851   Vector u(cm);
1852
1853   ASSERT_TRUE(u.get_allocator() == m);
1854
1855   if (false) {
1856     Vector(m);
1857   }
1858 }
1859
1860 STL_TEST("23.2.1 Table 99.5", copyWithAllocator, is_copy_constructible, a, m) {
1861   DataState<Vector> dsa(a);
1862   const auto& ca = a;
1863   const auto& cm = m;
1864
1865   Vector u(ca, cm);
1866
1867   ASSERT_TRUE(u.get_allocator() == m);
1868   ASSERT_TRUE(dsa == u);
1869   ASSERT_TRUE(
1870     (ca.data() == nullptr && u.data() == nullptr) ||
1871     (ca.data() != u.data())
1872   ) << "only a shallow copy was made";
1873 }
1874
1875 STL_TEST("23.2.1 Table 99.6", moveConstructionWithAllocator,
1876          is_destructible, a) {
1877   // there is nothing new to test here
1878 }
1879
1880 STL_TEST("23.2.1 Table 99.6", moveConstructionWithAllocatorSupplied,
1881          is_move_constructible, a, m) {
1882   bool deep = m != a.get_allocator();
1883   auto osize = a.size();
1884   auto oalloc = AllocTracker::Constructed;
1885   const auto& cm = m;
1886
1887   Vector u(std::move(a), cm);
1888
1889   ASSERT_TRUE(u.get_allocator() == m);
1890
1891   if (deep) {
1892     if (!AllocTracker::Allocated.empty()) {
1893       ASSERT_EQ(osize, AllocTracker::Constructed - oalloc);
1894     }
1895   } else {
1896     ASSERT_EQ(0, Counter::CountTotalOps);
1897   }
1898 }
1899
1900 STL_TEST("23.2.1 Table 99.7-9", allocAssign, is_destructible) {
1901   // there is nothing new to test here
1902 }
1903
1904 STL_TEST("23.2.1-7", nAllocConstruction, is_copy_constructible, n, m) {
1905   #ifndef USING_STD_VECTOR
1906   const auto& cm = m;
1907
1908   Vector u(n, cm);
1909
1910   ASSERT_TRUE(m == u.get_allocator());
1911   #endif
1912 }
1913
1914 STL_TEST("23.2.1-7", nCopyAllocConstruction, is_copy_constructible, n, t, m) {
1915   const auto& cm = m;
1916   const auto& ct = t;
1917
1918   Vector u(n, ct, cm);
1919
1920   ASSERT_TRUE(m == u.get_allocator());
1921 }
1922
1923 STL_TEST("23.2.1-7", forwardIteratorAllocConstruction,
1924          is_destructible, i, j, m) {
1925   auto fi = makeForwardIterator(i);
1926   auto fj = makeForwardIterator(j);
1927   const auto& cfi = fi;
1928   const auto& cfj = fj;
1929   const auto& cm = m;
1930
1931   Vector u(cfi, cfj, cm);
1932
1933   ASSERT_TRUE(m == u.get_allocator());
1934 }
1935
1936 STL_TEST("23.2.1-7", inputIteratorAllocConstruction,
1937          is_move_constructible, i, j, m) {
1938   #ifdef USING_STD_VECTOR
1939   if (Ticker::TicksLeft >= 0) return;
1940   #endif
1941
1942   auto ii = makeInputIterator(i);
1943   auto ij = makeInputIterator(j);
1944   const auto& cii = ii;
1945   const auto& cij = ij;
1946   const auto& cm = m;
1947
1948   Vector u(cii, cij, cm);
1949
1950   ASSERT_TRUE(m == u.get_allocator());
1951 }
1952
1953 STL_TEST("23.2.1-7", ilAllocConstruction, is_arithmetic, m) {
1954   // gcc fail
1955   if (Ticker::TicksLeft >= 0) return;
1956
1957   const auto& cm = m;
1958
1959   Vector u({ 1, 4, 7 }, cm);
1960
1961   ASSERT_TRUE(m == u.get_allocator());
1962 }
1963
1964 //-----------------------------------------------------------------------------
1965 // Data races
1966
1967 STL_TEST("23.2.2", dataRaces, is_destructible) {
1968   if (false) {
1969     const Vector* cv = nullptr;
1970     typename Vector::size_type* s = nullptr;
1971
1972     cv->begin();
1973     cv->end();
1974     cv->rbegin();
1975     cv->rend();
1976     cv->front();
1977     cv->back();
1978     cv->data();
1979
1980     (*cv).at(*s);
1981     (*cv)[*s];
1982   }
1983
1984   // White-box: check that the non-const versions of each of the above
1985   // functions is implemented in terms of (or the same as) the const version
1986 }
1987
1988 //-----------------------------------------------------------------------------
1989 // Sequence container
1990
1991 STL_TEST("23.2.3 Table 100.1, alt", nConstruction, is_constructible, n) {
1992   Vector u(n);
1993
1994   ASSERT_TRUE(Allocator() == u.get_allocator());
1995   ASSERT_EQ(n, u.size());
1996   ASSERT_EQ(Counter::CountTotalOps, Counter::CountDC);
1997 }
1998
1999 STL_TEST("23.2.3 Table 100.1", nCopyConstruction,
2000          is_copy_constructible, n, t) {
2001   const auto& ct = t;
2002
2003   Vector u(n, ct);
2004
2005   ASSERT_TRUE(Allocator() == u.get_allocator());
2006   ASSERT_EQ(n, u.size()) << "Vector(n, t).size() != n" << endl;
2007   for (const auto& val : u) ASSERT_EQ(convertToInt(t), convertToInt(val))
2008     << "not all elements of Vector(n, t) are equal to t";
2009 }
2010
2011 STL_TEST("23.2.3 Table 100.2", forwardIteratorConstruction,
2012          is_destructible, i, j) {
2013   // All data is emplace-constructible from int, so we restrict to
2014   // is_destructible
2015
2016   auto fi = makeForwardIterator(i);
2017   auto fj = makeForwardIterator(j);
2018   const auto& cfi = fi;
2019   const auto& cfj = fj;
2020
2021   Vector u(cfi, cfj);
2022
2023   ASSERT_TRUE(Allocator() == u.get_allocator());
2024   ASSERT_LE(Counter::CountTotalOps, j-i);
2025
2026   ASSERT_EQ(j - i, u.size()) << "u(i,j).size() != j-i";
2027   for (auto it = u.begin(); it != u.end(); ++it, ++i)
2028     ASSERT_EQ(*i, convertToInt(*it)) << "u(i,j) constructed incorrectly";
2029 }
2030
2031 STL_TEST("23.2.3 Table 100.2", inputIteratorConstruction,
2032          is_move_constructible, i, j) {
2033   #ifdef USING_STD_VECTOR
2034   if (Ticker::TicksLeft >= 0) return;
2035   #endif
2036
2037   auto ii = makeInputIterator(i);
2038   auto ij = makeInputIterator(j);
2039   const auto& cii = ii;
2040   const auto& cij = ij;
2041
2042   Vector u(cii, cij);
2043
2044   ASSERT_TRUE(Allocator() == u.get_allocator());
2045   ASSERT_EQ(j - i, u.size()) << "u(i,j).size() != j-i";
2046   for (auto it = u.begin(); it != u.end(); ++it, ++i)
2047     ASSERT_EQ(*i, convertToInt(*it)) << "u(i,j) constructed incorrectly";
2048 }
2049
2050 STL_TEST("23.2.3 Table 100.3", ilConstruction, is_arithmetic) {
2051   // whitebox: ensure that Vector(il) is implemented in terms of
2052   // Vector(il.begin(), il.end())
2053
2054   // gcc fail
2055   if (Ticker::TicksLeft >= 0) return;
2056
2057   Vector u = { 1, 4, 7 };
2058
2059   ASSERT_TRUE(Allocator() == u.get_allocator());
2060   ASSERT_EQ(3, u.size()) << "u(il).size() fail";
2061   int i = 1;
2062   auto it = u.begin();
2063   for (; it != u.end(); ++it, i += 3)
2064     ASSERT_EQ(i, convertToInt(*it)) << "u(il) constructed incorrectly";
2065 }
2066
2067 STL_TEST("23.2.3 Table 100.4", ilAssignment,
2068          is_arithmetic, a) {
2069   // whitebox: ensure that assign(il) is implemented in terms of
2070   // assign(il.begin(), il.end())
2071
2072   // gcc fail
2073   if (Ticker::TicksLeft >= 0) return;
2074
2075   auto am = a.get_allocator();
2076
2077   Vector& b = a = { 1, 4, 7 };
2078
2079   ASSERT_TRUE(am == a.get_allocator());
2080   ASSERT_TRUE(&b == &a) << "'a = ...' did not return *this";
2081
2082   ASSERT_EQ(3, a.size()) << "u(il).size() fail";
2083   int i = 1;
2084   auto it = a.begin();
2085   for (; it != a.end(); ++it, i += 3)
2086     ASSERT_EQ(i, convertToInt(*it)) << "u(il) constructed incorrectly";
2087 }
2088
2089 //----------------------------
2090 // insert-and-erase subsection
2091
2092 template <class Vector>
2093 void insertNTCheck(const Vector& a, DataState<Vector>& dsa,
2094                    int idx, int n, int val) {
2095   ASSERT_EQ(dsa.size() + n, a.size());
2096   int i = 0;
2097   for (; i < idx; ++i) {
2098     ASSERT_EQ(dsa[i], convertToInt(a.data()[i])) << i;
2099   }
2100   for (; i < idx + n; ++i) {
2101     ASSERT_EQ(val, convertToInt(a.data()[i])) << i;
2102   }
2103   for (; i < a.size(); ++i) {
2104     ASSERT_EQ(dsa[i-n], convertToInt(a.data()[i])) << i;
2105   }
2106 }
2107
2108 STL_TEST("23.2.3 Table 100.5", iteratorEmplacement,
2109          is_move_constructibleAndAssignable, a, p) {
2110   DataState<Vector> dsa(a);
2111   int idx = distance(a.begin(), p);
2112   auto am = a.get_allocator();
2113
2114   auto q = a.emplace(p, 44);
2115
2116   ASSERT_TRUE(am == a.get_allocator());
2117   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2118   insertNTCheck(a, dsa, idx, 1, 44);
2119 }
2120
2121 STL_TEST("23.2.3 Table 100.6", iteratorInsertion,
2122          is_copy_constructibleAndAssignable, a, p, t) {
2123   DataState<Vector> dsa(a);
2124   int idx = distance(a.begin(), p);
2125   int tval = convertToInt(t);
2126   auto am = a.get_allocator();
2127   const auto& ct = t;
2128
2129   auto q = a.insert(p, ct);
2130
2131   ASSERT_TRUE(am == a.get_allocator());
2132   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2133   insertNTCheck(a, dsa, idx, 1, tval);
2134 }
2135
2136 STL_TEST("23.2.3 Table 100.7", iteratorInsertionRV,
2137          is_move_constructibleAndAssignable, a, p, t) {
2138   // rvalue-references cannot have their address checked for aliased inserts
2139   if (a.data() <= addressof(t) && addressof(t) < a.data() + a.size()) return;
2140
2141   DataState<Vector> dsa(a);
2142   int idx = distance(a.begin(), p);
2143   int tval = convertToInt(t);
2144   auto am = a.get_allocator();
2145
2146   auto q = a.insert(p, std::move(t));
2147
2148   ASSERT_TRUE(am == a.get_allocator());
2149   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2150   insertNTCheck(a, dsa, idx, 1, tval);
2151 }
2152
2153 STL_TEST("23.2.3 Table 100.8", iteratorInsertionN,
2154          is_copy_constructibleAndAssignable, a, p, n, t) {
2155   DataState<Vector> dsa(a);
2156   int idx = distance(a.begin(), p);
2157   int tval = convertToInt(t);
2158   auto am = a.get_allocator();
2159   const auto& ct = t;
2160
2161   #ifndef USING_STD_VECTOR
2162   auto q =
2163   #endif
2164
2165   a.insert(p, n, ct);
2166
2167   ASSERT_TRUE(am == a.get_allocator());
2168   #ifndef USING_STD_VECTOR
2169   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2170   #endif
2171
2172   insertNTCheck(a, dsa, idx, n, tval);
2173 }
2174
2175 template <class Vector>
2176 void insertItCheck(const Vector& a, DataState<Vector>& dsa,
2177                    int idx, int* b, int* e) {
2178   ASSERT_EQ(dsa.size() + (e - b), a.size());
2179   int i = 0;
2180   for (; i < idx; ++i) {
2181     ASSERT_EQ(dsa[i], convertToInt(a.data()[i]));
2182   }
2183   for (; i < idx + (e - b); ++i) {
2184     ASSERT_EQ(*(b + i - idx), convertToInt(a.data()[i]));
2185   }
2186   for (; i < a.size(); ++i) {
2187     ASSERT_EQ(dsa[i - (e - b)], convertToInt(a.data()[i]));
2188   }
2189 }
2190
2191 STL_TEST("23.2.3 Table 100.9", iteratorInsertionIterator,
2192          is_move_constructibleAndAssignable, a, p, i, j) {
2193   DataState<Vector> dsa(a);
2194   int idx = distance(a.begin(), p);
2195
2196   auto fi = makeForwardIterator(i);
2197   auto fj = makeForwardIterator(j);
2198   auto am = a.get_allocator();
2199   const auto& cfi = fi;
2200   const auto& cfj = fj;
2201
2202   #ifndef USING_STD_VECTOR
2203   auto q =
2204   #endif
2205
2206   a.insert(p, cfi, cfj);
2207
2208   ASSERT_TRUE(am == a.get_allocator());
2209   #ifndef USING_STD_VECTOR
2210   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2211   #endif
2212
2213   insertItCheck(a, dsa, idx, i, j);
2214 }
2215
2216 STL_TEST("23.2.3 Table 100.9", iteratorInsertionInputIterator,
2217          is_move_constructibleAndAssignable, a, p, i, j) {
2218   DataState<Vector> dsa(a);
2219   int idx = distance(a.begin(), p);
2220
2221   auto ii = makeInputIterator(i);
2222   auto ij = makeInputIterator(j);
2223   auto am = a.get_allocator();
2224   const auto& cii = ii;
2225   const auto& cij = ij;
2226
2227   #ifndef USING_STD_VECTOR
2228   auto q =
2229   #endif
2230
2231   a.insert(p, cii, cij);
2232
2233   ASSERT_TRUE(am == a.get_allocator());
2234   #ifndef USING_STD_VECTOR
2235   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2236   #endif
2237
2238   insertItCheck(a, dsa, idx, i, j);
2239 }
2240
2241 STL_TEST("23.2.3 Table 100.10", iteratorInsertIL,
2242          is_arithmetic, a, p) {
2243   // gcc fail
2244   if (Ticker::TicksLeft >= 0) return;
2245
2246   // whitebox: ensure that insert(p, il) is implemented in terms of
2247   // insert(p, il.begin(), il.end())
2248
2249   DataState<Vector> dsa(a);
2250   int idx = distance(a.begin(), p);
2251   auto am = a.get_allocator();
2252
2253   #ifndef USING_STD_VECTOR
2254   auto q =
2255   #endif
2256
2257   a.insert(p, {1, 4, 7});
2258
2259   ASSERT_TRUE(am == a.get_allocator());
2260   #ifndef USING_STD_VECTOR
2261   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2262   #endif
2263
2264   int ila[] = { 1, 4, 7 };
2265   int* i = ila;
2266   int* j = ila + 3;
2267   insertItCheck(a, dsa, idx, i, j);
2268 }
2269
2270 template <class Vector>
2271 void eraseCheck(Vector& a, DataState<Vector>& dsa, int idx, int n) {
2272   ASSERT_EQ(dsa.size() - n, a.size());
2273   size_t i = 0;
2274   auto it = a.begin();
2275   for (; it != a.end(); ++it, ++i) {
2276     if (i == idx) i += n;
2277     ASSERT_EQ(dsa[i], convertToInt(*it));
2278   }
2279 }
2280
2281 STL_TEST("23.2.3 Table 100.11", iteratorErase, is_move_assignable, a, p) {
2282   if (p == a.end()) return;
2283
2284   DataState<Vector> dsa(a);
2285   int idx = distance(a.begin(), p);
2286   auto am = a.get_allocator();
2287
2288   auto rit = a.erase(p);
2289
2290   ASSERT_TRUE(am == a.get_allocator());
2291   ASSERT_EQ(idx, distance(a.begin(), rit)) << "wrong iterator returned";
2292   eraseCheck(a, dsa, idx, 1);
2293 }
2294
2295 STL_TEST("23.2.3 Table 100.12", iteratorEraseRange,
2296          is_move_assignable, a, p, q) {
2297   if (p == a.end()) return;
2298
2299   DataState<Vector> dsa(a);
2300   int idx = distance(a.begin(), p);
2301   auto am = a.get_allocator();
2302
2303   auto rit = a.erase(p, q);
2304
2305   ASSERT_TRUE(am == a.get_allocator());
2306   ASSERT_EQ(idx, distance(a.begin(), rit)) << "wrong iterator returned";
2307   eraseCheck(a, dsa, idx, distance(p,q));
2308 }
2309
2310 //--------------------------------
2311 // end insert-and-erase subsection
2312
2313 STL_TEST("23.2.3 Table 100.13", clear, is_destructible, a) {
2314
2315   auto am = a.get_allocator();
2316
2317   try {
2318     a.clear();
2319   } catch (...) {
2320     FAIL() << "clear must be noexcept";
2321   }
2322
2323   ASSERT_TRUE(am == a.get_allocator());
2324   ASSERT_TRUE(a.empty());
2325 }
2326
2327 STL_TEST("23.2.3 Table 100.14", assignRange, is_move_assignable, a, i, j) {
2328   auto fi = makeForwardIterator(i);
2329   auto fj = makeForwardIterator(j);
2330   const auto& cfi = fi;
2331   const auto& cfj = fj;
2332   auto am = a.get_allocator();
2333
2334   a.assign(cfi, cfj);
2335
2336   ASSERT_TRUE(am == a.get_allocator());
2337   ASSERT_EQ(distance(i, j), a.size());
2338   for (auto it = a.begin(); it != a.end(); ++it, ++i)
2339     ASSERT_EQ(*i, convertToInt(*it));
2340 }
2341
2342 STL_TEST("23.2.3 Table 100.14", assignInputRange,
2343          is_move_constructibleAndAssignable, a, i, j) {
2344   auto ii = makeInputIterator(i);
2345   auto ij = makeInputIterator(j);
2346   const auto& cii = ii;
2347   const auto& cij = ij;
2348   auto am = a.get_allocator();
2349
2350   a.assign(cii, cij);
2351
2352   ASSERT_TRUE(am == a.get_allocator());
2353   ASSERT_EQ(distance(i, j), a.size());
2354   for (auto it = a.begin(); it != a.end(); ++it, ++i)
2355     ASSERT_EQ(*i, convertToInt(*it));
2356 }
2357
2358 STL_TEST("23.2.3 Table 100.15", assignIL,
2359          is_arithmetic, a) {
2360
2361   // whitebox: ensure that assign(il) is implemented in terms of
2362   // assign(il.begin(), il.end())
2363
2364   // gcc fail
2365   if (Ticker::TicksLeft >= 0) return;
2366
2367   auto am = a.get_allocator();
2368
2369   a.assign({1, 4, 7});
2370
2371   ASSERT_TRUE(am == a.get_allocator());
2372   int ila[] = { 1, 4, 7 };
2373   int* i = ila;
2374
2375   ASSERT_EQ(3, a.size());
2376   for (auto it = a.begin(); it != a.end(); ++it, ++i)
2377     ASSERT_EQ(*i, convertToInt(*it));
2378 }
2379
2380 STL_TEST("23.2.3 Table 100.16", assignN,
2381          is_copy_constructibleAndAssignable, a, n, t) {
2382   auto am = a.get_allocator();
2383   auto const& ct = t;
2384   auto tval = convertToInt(t);
2385
2386   a.assign(n, ct);
2387
2388   ASSERT_TRUE(am == a.get_allocator());
2389   ASSERT_EQ(n, a.size());
2390   for (auto it = a.begin(); it != a.end(); ++it)
2391     ASSERT_EQ(tval, convertToInt(*it));
2392 }
2393
2394 STL_TEST("23.2.3 Table 101.1", front, is_destructible, a) {
2395   if (a.empty()) return;
2396
2397   ASSERT_TRUE(addressof(a.front()) == a.data());
2398
2399   ASSERT_EQ(0, Counter::CountTotalOps);
2400
2401   if (false) {
2402     mutate(a.front());
2403     const Vector& ca = a;
2404     ca.front();
2405   }
2406 }
2407
2408 STL_TEST("23.2.3 Table 101.2", back, is_destructible, a) {
2409   if (a.empty()) return;
2410
2411   ASSERT_TRUE(addressof(a.back()) == a.data() + a.size() - 1);
2412
2413   ASSERT_EQ(0, Counter::CountTotalOps);
2414
2415   if (false) {
2416     mutate(a.back());
2417     const Vector& ca = a;
2418     ca.back();
2419   }
2420 }
2421
2422 STL_TEST("23.2.3 Table 101.4", emplaceBack,
2423          is_move_constructible, a) {
2424   DataState<Vector> dsa(a);
2425   auto adata = a.data();
2426   int excess = a.capacity() - a.size();
2427   auto am = a.get_allocator();
2428
2429   try {
2430     a.emplace_back(44);
2431   } catch (...) {
2432     ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2433     throw;
2434   }
2435
2436   ASSERT_TRUE(am == a.get_allocator());
2437   if (excess > 0) ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2438   ASSERT_EQ(dsa.size() + 1, a.size());
2439   size_t i = 0;
2440   auto it = a.begin();
2441   for (; i < dsa.size(); ++i, ++it)
2442     ASSERT_EQ(dsa[i], convertToInt(*it));
2443   ASSERT_EQ(44, convertToInt(a.back()));
2444 }
2445
2446 STL_TEST("23.2.3 Table 101.7", pushBack, is_copy_constructible, a, t) {
2447   DataState<Vector> dsa(a);
2448   int tval = convertToInt(t);
2449   auto adata = a.data();
2450   int excess = a.capacity() - a.size();
2451   auto am = a.get_allocator();
2452   const auto& ct = t;
2453
2454   try {
2455     a.push_back(ct);
2456   } catch (...) {
2457     ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2458     throw;
2459   }
2460
2461   ASSERT_TRUE(am == a.get_allocator());
2462   if (excess > 0) ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2463   ASSERT_EQ(dsa.size() + 1, a.size());
2464   size_t i = 0;
2465   auto it = a.begin();
2466   for (; i < dsa.size(); ++i, ++it)
2467     ASSERT_EQ(dsa[i], convertToInt(*it));
2468   ASSERT_EQ(tval, convertToInt(a.back()));
2469 }
2470
2471 STL_TEST("23.2.3 Table 101.8", pushBackRV,
2472          is_move_constructible, a, t) {
2473   DataState<Vector> dsa(a);
2474   int tval = convertToInt(t);
2475   auto adata = a.data();
2476   int excess = a.capacity() - a.size();
2477   auto am = a.get_allocator();
2478
2479   try {
2480     a.push_back(move(t));
2481   } catch (...) {
2482     ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2483     throw;
2484   }
2485
2486   ASSERT_TRUE(am == a.get_allocator());
2487   if (excess > 0) ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2488   ASSERT_EQ(dsa.size() + 1, a.size());
2489   size_t i = 0;
2490   auto it = a.begin();
2491   for (; i < dsa.size(); ++i, ++it)
2492     ASSERT_EQ(dsa[i], convertToInt(*it));
2493   ASSERT_EQ(tval, convertToInt(a.back()));
2494 }
2495
2496 STL_TEST("23.2.3 Table 100.10", popBack, is_destructible, a) {
2497   if (a.empty()) return;
2498
2499   DataState<Vector> dsa(a);
2500   auto am = a.get_allocator();
2501
2502   a.pop_back();
2503
2504   ASSERT_TRUE(am == a.get_allocator());
2505   ASSERT_EQ(dsa.size() - 1, a.size());
2506   size_t i = 0;
2507   auto it = a.begin();
2508   for (; it != a.end(); ++it, ++i)
2509     ASSERT_EQ(dsa[i], convertToInt(*it));
2510 }
2511
2512 STL_TEST("23.2.3 Table 100.11", operatorBrace, is_destructible, a) {
2513   const auto& ca = a;
2514   for (int i = 0; i < ca.size(); ++i)
2515     ASSERT_TRUE(addressof(ca[i]) == ca.data()+i);
2516
2517   ASSERT_EQ(0, Counter::CountTotalOps);
2518
2519   if (false) {
2520     mutate(a[0]);
2521   }
2522 }
2523
2524 STL_TEST("23.2.3 Table 100.12", at, is_destructible, a) {
2525   const auto& ca = a;
2526   for (int i = 0; i < ca.size(); ++i)
2527     ASSERT_TRUE(addressof(ca.at(i)) == ca.data()+i);
2528
2529   ASSERT_EQ(0, Counter::CountTotalOps);
2530
2531   try {
2532     ca.at(ca.size());
2533     FAIL() << "at(size) should have thrown an error";
2534   } catch (const std::out_of_range& e) {
2535   } catch (...) {
2536     FAIL() << "at(size) threw error other than out_of_range";
2537   }
2538
2539   if (false) {
2540     mutate(a.at(0));
2541   }
2542 }
2543
2544 STL_TEST("move iterators", moveIterators, is_copy_constructibleAndAssignable) {
2545   if (false) {
2546     int* i = nullptr;
2547     int* j = nullptr;
2548
2549     auto mfi = make_move_iterator(makeForwardIterator(i));
2550     auto mfj = make_move_iterator(makeForwardIterator(j));
2551     auto mii = make_move_iterator(makeInputIterator(i));
2552     auto mij = make_move_iterator(makeInputIterator(j));
2553
2554     Vector u1(mfi, mfj);
2555     Vector u2(mii, mij);
2556
2557     u1.insert(u1.begin(), mfi, mfj);
2558     u1.insert(u1.begin(), mii, mij);
2559
2560     u1.assign(mfi, mfj);
2561     u1.assign(mii, mij);
2562   }
2563 }
2564
2565 //-----------------------------------------------------------------------------
2566 // Vector-specifics
2567
2568 STL_TEST("23.3.6.4", dataAndCapacity, is_destructible) {
2569   // there isn't anything new to test here - data and capacity are used as the
2570   // backbone of DataState. The minimal testing we might want to do is already
2571   // done in the populate test
2572 }
2573
2574 STL_TEST("23.3.6.3", reserve, is_move_constructible, a, n) {
2575   auto adata = a.data();
2576   auto ocap = a.capacity();
2577   auto am = a.get_allocator();
2578
2579   a.reserve(n);
2580
2581   ASSERT_TRUE(am == a.get_allocator());
2582   if (n <= ocap) {
2583     ASSERT_EQ(0, Counter::CountTotalOps);
2584     ASSERT_TRUE(adata == a.data());
2585   } else {
2586     ASSERT_TRUE(a.capacity() >= n);
2587     ASSERT_LE(Counter::CountTotalOps, 2*a.size()); // move and delete
2588   }
2589 }
2590
2591 STL_TEST("23.3.6.3", lengthError, is_move_constructible) {
2592   auto mx = Vector().max_size();
2593   auto big = mx+1;
2594   if (mx >= big) return; // max_size is the biggest size_type; overflowed
2595
2596   Vector u;
2597   try {
2598     u.reserve(big);
2599     FAIL() << "reserve(big) should have thrown an error";
2600   } catch (const std::length_error& e) {
2601   } catch (...) {
2602     FAIL() << "reserve(big) threw error other than length_error";
2603   }
2604 }
2605
2606 STL_TEST("23.3.6.3", resize, is_copy_constructible, a, n) {
2607   DataState<Vector> dsa(a);
2608   int sz = a.size();
2609   auto am = a.get_allocator();
2610
2611   a.resize(n);
2612
2613   ASSERT_TRUE(am == a.get_allocator());
2614   ASSERT_EQ(n, a.size());
2615
2616   if (n <= sz) {
2617     for (int i = 0; i < n; ++i) {
2618       ASSERT_EQ(dsa[i], convertToInt(a[i]));
2619     }
2620   } else {
2621     for (int i = 0; i < sz; ++i) {
2622       ASSERT_EQ(dsa[i], convertToInt(a[i]));
2623     }
2624   }
2625 }
2626
2627 STL_TEST("23.3.6.3", resizeT, is_copy_constructibleAndAssignable, a, n, t) {
2628   #ifdef USING_STD_VECTOR
2629   if (a.data() <= addressof(t) && addressof(t) < a.data() + a.size()) return;
2630   #endif
2631
2632   DataState<Vector> dsa(a);
2633   int sz = a.size();
2634   auto am = a.get_allocator();
2635   const auto& ct = t;
2636   int val = convertToInt(t);
2637
2638   a.resize(n, ct);
2639
2640   ASSERT_TRUE(am == a.get_allocator());
2641   ASSERT_EQ(n, a.size());
2642
2643   if (n <= sz) {
2644     for (int i = 0; i < n; ++i) {
2645       ASSERT_EQ(dsa[i], convertToInt(a[i]));
2646     }
2647   } else {
2648     int i = 0;
2649     for ( ; i < sz; ++i) {
2650       ASSERT_EQ(dsa[i], convertToInt(a[i]));
2651     }
2652     for ( ; i < n; ++i) {
2653       ASSERT_EQ(val, convertToInt(a[i]));
2654     }
2655   }
2656 }
2657
2658 STL_TEST("23.3.6.3", shrinkToFit, is_move_constructible, a) {
2659   bool willThrow = Ticker::TicksLeft >= 0;
2660
2661   a.reserve(a.capacity() * 11);
2662
2663   auto ocap = a.capacity();
2664   DataState<Vector> dsa(a);
2665
2666   auto am = a.get_allocator();
2667
2668   try {
2669     a.shrink_to_fit();
2670   } catch (...) {
2671     FAIL() << "shrink_to_fit should swallow errors";
2672   }
2673
2674   ASSERT_TRUE(am == a.get_allocator());
2675   ASSERT_TRUE(dsa == a);
2676   if (willThrow) {
2677     //ASSERT_EQ(ocap, a.capacity()); might shrink in place
2678     throw TickException("I swallowed the error");
2679   } else {
2680     ASSERT_TRUE(a.capacity() == 0 || a.capacity() < ocap) << "Look into this";
2681   }
2682 }
2683
2684 #ifndef USING_STD_VECTOR
2685 STL_TEST("EBO", ebo, is_destructible) {
2686   static_assert(!is_same<Allocator, std::allocator<T>>::value ||
2687                 sizeof(Vector) == 3 * sizeof(void*),
2688     "fbvector has default allocator, but has size != 3*sizeof(void*)");
2689 }
2690
2691 STL_TEST("relinquish", relinquish, is_destructible, a) {
2692   auto sz = a.size();
2693   auto cap = a.capacity();
2694   auto data = a.data();
2695
2696   auto guts = relinquish(a);
2697
2698   ASSERT_EQ(data, guts);
2699   ASSERT_TRUE(a.empty());
2700   ASSERT_EQ(0, a.capacity());
2701
2702   auto alloc = a.get_allocator();
2703   for (size_t i = 0; i < sz; ++i)
2704     std::allocator_traits<decltype(alloc)>::destroy(alloc, guts + i);
2705   if (guts != nullptr)
2706     std::allocator_traits<decltype(alloc)>::deallocate(alloc, guts, cap);
2707 }
2708
2709 STL_TEST("attach", attach, is_destructible, a) {
2710   DataState<Vector> dsa(a);
2711
2712   auto sz = a.size();
2713   auto cap = a.capacity();
2714   auto guts = relinquish(a);
2715
2716   ASSERT_EQ(a.data(), nullptr);
2717   attach(a, guts, sz, cap);
2718
2719   ASSERT_TRUE(dsa == a);
2720 }
2721
2722 #endif
2723
2724 // #endif
2725
2726 int main(int argc, char** argv) {
2727   testing::InitGoogleTest(&argc, argv);
2728   gflags::ParseCommandLineFlags(&argc, &argv, true);
2729
2730   return RUN_ALL_TESTS();
2731 }