folly/test/stl_tests/StlVectorTest.cpp

   1 /*
   2  * Copyright 2013 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 // @author Nicholas Ormrod <njormrod@fb.com>
  18
  19 /*
  20
  21 This file contains an extensive STL compliance test suite for an STL vector
  22 implementation (such as FBVector).
  23
  24 GCC 4.7 is required.
  25
  26 */
  27
  28 // only compile if GCC is at least 4.7
  29 #if __GNUC__ > 4 || __GNUC__ == 4 && __GNUC_MINOR__ >= 7
  30
  31 #if 0
  32 #define USING_STD_VECTOR
  33 #endif
  34
  35 /*
  36
  37 The insanity of this file deserves a superficial explanation.
  38
  39 This file tests an implementation of STL vector. It is extremely comprehensive.
  40 If it compiles (more on that later) it generates a binary which, when run,
  41 exhaustively tests its vector for standard compliance.
  42
  43 Limitations:
  44 -If it doesn't compile, the compiler errors are mind-boggling.
  45 -Not everything is testable. There are a few comments in the code where
  46  the implementation must be inspected, as opposed to tested. These are very
  47  simple inspections. Search for 'whitebox'.
  48 -It does not test boolean specialization.
  49
  50 ==========================
  51 How this file is organized
  52
  53 --------------
  54 Data and Alloc
  55
  56 Data is a class designed to provide diagnostics when stored in a vector. It
  57 counts the number of operations performed on it, can have any function
  58 disabled or labeled as noexcept, throws errors from anywhere that is not
  59 noexcept, tracks its supposed location in memory (optional), tracks
  60 aggregate information, and can print a trace of its action.
  61
  62 Alloc, like Data, is a full-blown diagnostic allocator. It keeps track of
  63 all space it has allocated, keeps counters, throws exceptions, and can easily
  64 compare equal or not equal with other Allocs.
  65
  66 These two classes have a few useful helper functions:
  67 isSane - checks that all the tracked variables make sense
  68 softReset - simplifies the variables before a test
  69 hardReset - brutally resets all variables to the default state
  70
  71 --------
  72 STL_TEST
  73
  74 Google test is not quite good enough for this test file, because we need to
  75 run tests across different input values and different types.
  76
  77 The STL_TEST macro takes a few arguments:
  78 string - what is being tested
  79 id - unique id, passed to TEST
  80 restriction - requirements for test types
  81 parameters - which variables to range over
  82
  83 Eg: STL_TEST("23.2.3", isCopyable, is_copy_constructible, a) { ... }
  84
  85 The restriction is used to select which types get tested. Copy construction,
  86 for example, requires a data type which is copy constructible, whereas to test
  87 the clear operation, the data only needs to be destructible. If the type does
  88 not pass the restriction, then the test is not instantiated with that type (if
  89 it were, then there would be a compiler error).
  90
  91 The variable names in the standard have very specific meaning. For example,
  92 a and b are always vectors, i and j are always external iterators, etc. These
  93 bindings are used in the STL_TEST - if you need a vector and an int, have
  94 parameters a and n.
  95
  96 There is a list (BOOST_PP_SEQ) of test types and interface types. If the
  97 type passes the restriction, then the test body is instantiated with that
  98 type as its template parameter. Instantiation ensures that the contractual
  99 elements of the standard are satisfied.  Only the test types, however, and
 100 not the interfact types, are actually tested.
 101
 102 If a test type passes the restriction, then it is run with a variety of
 103 arguments. Each variable (e.g. a and b) have a generator, which generates
 104 a range of values for that variable before each test. Generated values are not
 105 reused - they are remade for every run. This causes long runtimes, but ensures
 106 that corner cases are not missed.
 107
 108 There are two implicit extra parameters, z and ticks. Ignore z. Ticks, on the
 109 other hand, is very important. Each is test is run multiple times with the
 110 same arguments; the first time with no ticks (and hence no Data or Alloc
 111 exceptions), and then once again for each and every location that an
 112 exception can be thrown. This ensures that exception corner cases are alse
 113 thoroughly tested.
 114
 115 At the end of each test, a set of verification functions is run to ensure
 116 that nothing was corrupted.
 117
 118 ---------
 119 The tests
 120
 121 All specifications from N3337 Chapter 23 (Containers) that pertains to
 122 vector is tested (if possible). Each aspect has a dedicated STL_TEST, so that
 123 there are no compounding errors. The tests are organized as they appear in
 124 N3337.
 125
 126 The backbone of the testing framework is based on a small set of vector
 127 operations:
 128 -empty construction
 129 -copy construction (a little bit)
 130 -size
 131 -capacity
 132 -data
 133 -emplace_back
 134
 135 These functions are used to generate and verify the tests. If they fail, then
 136 the cascade of errors will be enormous. They are, therefore, tested first.
 137
 138 */
 139 /*
 140
 141 THOUGHTS:
 142
 143 -Not all complexity checks are verified. These will be relentlessly hunted down
 144  in the benchmarking phase.
 145
 146 -It seems that initializer lists with implicit arguments are constructed before
 147  being passed into the vector. When one of the constructors fails, it fails in
 148  the initializer list, before it even gets to the vector. The IL, however,
 149  doesn't clean up properly, and already-constructed elements are not
 150  destroyed. This causes a memory leak, and the tests break, but it is not the
 151  fault of the vector itself. Further, since the implementation for the
 152  initializer lists is specified in the standard as calling an associated
 153  function with (il.begin(), il.end()), we really just have to check the throws
 154  cases for the associated functions (which all work fine). Initializer lists
 155  also do not work with explicit constructors.
 156
 157 -The implementation of std::copy from iterators prevents Data(int) from being
 158  explicit. Explicitness is, perhaps, a desirable quality, but with fundamental
 159  std library code like copy not supporting it, it seems impractical.
 160
 161 */
 162
 163 // include the vector first, to ensure its header is self-sufficient
 164 #ifdef USING_STD_VECTOR
 165 #include <vector>
 166 #define VECTOR_ std::vector
 167 #else
 168 #define FOLLY_BENCHMARK_USE_NS_IFOLLY
 169 #include "folly/FBVector.h"
 170 #define VECTOR_ Ifolly::fbvector
 171 #endif
 172
 173 //#define USING_STD_VECTOR
 174
 175 #include <iostream>
 176 #include <sstream>
 177 #include <typeinfo>
 178 #include <type_traits>
 179 #include <map>
 180 #include <set>
 181 #include <string>
 182 #include <stdexcept>
 183 #include <exception>
 184 #include <climits>
 185 #include <cstddef>
 186 #include <iomanip>
 187
 188 #include "folly/ScopeGuard.h"
 189 #include "folly/Conv.h"
 190 #include "boost/preprocessor.hpp"
 191 #include "boost/iterator/iterator_adaptor.hpp"
 192 #include <gflags/gflags.h>
 193 #include <gtest/gtest.h>
 194
 195 using namespace std;
 196 using namespace folly;
 197 namespace Ifolly {}
 198 using namespace Ifolly;
 199
 200 //=============================================================================
 201 //=============================================================================
 202 // Data type
 203
 204 //-----------------------------------------------------------------------------
 205 // Flags
 206
 207 typedef uint32_t Flags;
 208
 209 // each method has 3 options: normal, noexcept, throw, and deleted
 210 // normal is the default
 211 // throw is mutually exclusive with noexcept
 212 //
 213 // DC - default constructor
 214 // CC - copy constructor
 215 // MC - move constructor
 216 // OC - other constructor
 217 // CA - copy assignment
 218 // MA - move assignment
 219 enum FlagVals : Flags {
 220   DC_NOEXCEPT = 0x1,
 221   DC_THROW    = 0x2,
 222   DC_DELETE   = 0x8000,
 223   CC_NOEXCEPT = 0x4,
 224   CC_THROW    = 0x8,
 225   CC_DELETE   = 0x10000,
 226   MC_NOEXCEPT = 0x10,
 227   MC_THROW    = 0x20,
 228   MC_DELETE   = 0x20000,
 229   OC_NOEXCEPT = 0x40,
 230   OC_THROW    = 0x80,
 231   // OC_DELETE - DNE
 232
 233   CA_NOEXCEPT = 0x100,
 234   CA_THROW    = 0x200,
 235   CA_DELETE   = 0x40000,
 236   MA_NOEXCEPT = 0x400,
 237   MA_THROW    = 0x800,
 238   MA_DELETE   = 0x80000,
 239
 240   ALL_DELETE  = DC_DELETE | CC_DELETE | MC_DELETE
 241               | CA_DELETE | MA_DELETE,
 242
 243   IS_RELOCATABLE
 244               = 0x2000,
 245
 246   // for the allocator
 247   PROP_COPY = 0x100000,
 248   PROP_MOVE = 0x200000,
 249   PROP_SWAP = 0x400000,
 250 };
 251
 252 //-----------------------------------------------------------------------------
 253 // Deletors
 254
 255 template <bool b> struct D0 {
 256   D0() = default;
 257   D0(const D0&) = default;
 258   D0(D0&&) = default;
 259   explicit D0(std::nullptr_t) {}
 260   D0& operator=(const D0&) = default;
 261   D0& operator=(D0&&) = default;
 262 };
 263 template <> struct D0<true> {
 264   D0() = delete;
 265   D0(const D0&) = default;
 266   D0(D0&&) = default;
 267   explicit D0(std::nullptr_t) {}
 268   D0& operator=(const D0&) = default;
 269   D0& operator=(D0&&) = default;
 270 };
 271
 272 template <bool b> struct D1 {
 273   D1() = default;
 274   D1(const D1&) = default;
 275   D1(D1&&) = default;
 276   explicit D1(std::nullptr_t) {}
 277   D1& operator=(const D1&) = default;
 278   D1& operator=(D1&&) = default;
 279 };
 280 template <> struct D1<true> {
 281   D1() = default;
 282   D1(const D1&) = delete;
 283   D1(D1&&) = default;
 284   explicit D1(std::nullptr_t) {}
 285   D1& operator=(const D1&) = default;
 286   D1& operator=(D1&&) = default;
 287 };
 288
 289 template <bool b> struct D2 {
 290   D2() = default;
 291   D2(const D2&) = default;
 292   D2(D2&&) = default;
 293   explicit D2(std::nullptr_t) {}
 294   D2& operator=(const D2&) = default;
 295   D2& operator=(D2&&) = default;
 296 };
 297 template <> struct D2<true> {
 298   D2() = default;
 299   D2(const D2&) = default;
 300   D2(D2&&) = delete;
 301   explicit D2(std::nullptr_t) {}
 302   D2& operator=(const D2&) = default;
 303   D2& operator=(D2&&) = default;
 304 };
 305
 306 template <bool b> struct D3 {
 307   D3() = default;
 308   D3(const D3&) = default;
 309   D3(D3&&) = default;
 310   explicit D3(std::nullptr_t) {}
 311   D3& operator=(const D3&) = default;
 312   D3& operator=(D3&&) = default;
 313 };
 314 template <> struct D3<true> {
 315   D3() = default;
 316   D3(const D3&) = default;
 317   D3(D3&&) = default;
 318   explicit D3(std::nullptr_t) {}
 319   D3& operator=(const D3&) = delete;
 320   D3& operator=(D3&&) = default;
 321 };
 322
 323 template <bool b> struct D4 {
 324   D4() = default;
 325   D4(const D4&) = default;
 326   D4(D4&&) = default;
 327   explicit D4(std::nullptr_t) {}
 328   D4& operator=(const D4&) = default;
 329   D4& operator=(D4&&) = default;
 330 };
 331 template <> struct D4<true> {
 332   D4() = default;
 333   D4(const D4&) = default;
 334   D4(D4&&) = default;
 335   explicit D4(std::nullptr_t) {}
 336   D4& operator=(const D4&) = default;
 337   D4& operator=(D4&&) = delete;
 338 };
 339
 340 template <Flags f>
 341 struct Delete : D0<f & DC_DELETE>
 342               , D1<f & CC_DELETE>
 343               , D2<f & MC_DELETE>
 344               , D3<f & CA_DELETE>
 345               , D4<f & MA_DELETE> {
 346   Delete() = default;
 347   Delete(const Delete&) = default;
 348   Delete(Delete&&) = default;
 349   Delete& operator=(const Delete&) = default;
 350   Delete& operator=(Delete&&) = default;
 351
 352   explicit Delete(std::nullptr_t)
 353       : D0<f & DC_DELETE>(nullptr)
 354       , D1<f & CC_DELETE>(nullptr)
 355       , D2<f & MC_DELETE>(nullptr)
 356       , D3<f & CA_DELETE>(nullptr)
 357       , D4<f & MA_DELETE>(nullptr)
 358       {}
 359 };
 360
 361 //-----------------------------------------------------------------------------
 362 // Ticker
 363
 364 struct TickException : std::runtime_error {
 365   explicit TickException(const std::string& s)
 366     : std::runtime_error("tick: " + s) {}
 367 };
 368
 369 struct Ticker {
 370   static int CountTicks;
 371   static int TicksLeft;
 372   static void Tick(const std::string& s) {
 373     if (TicksLeft == 0) throw TickException(s);
 374     CountTicks++;
 375     TicksLeft--;
 376   }
 377 };
 378
 379 int Ticker::CountTicks = 0;
 380 int Ticker::TicksLeft = -1;
 381
 382 template <Flags f>
 383 struct DataTicker : Ticker {
 384   DataTicker() noexcept(f & DC_NOEXCEPT) {
 385     if (!(f & DC_NOEXCEPT)) Tick("Data()");
 386   }
 387   DataTicker(const DataTicker&) noexcept(f & CC_NOEXCEPT) {
 388     if (!(f & CC_NOEXCEPT)) Tick("Data(const Data&)");
 389   }
 390   DataTicker(DataTicker&&) noexcept(f & MC_NOEXCEPT) {
 391     if (!(f & MC_NOEXCEPT)) Tick("Data(Data&&)");
 392   }
 393   explicit DataTicker(std::nullptr_t) noexcept(f & OC_NOEXCEPT) {
 394     if (!(f & OC_NOEXCEPT)) Tick("Data(int)");
 395   }
 396   ~DataTicker() noexcept {}
 397   void operator=(const DataTicker&) noexcept(f & CA_NOEXCEPT) {
 398     if (!(f & CA_NOEXCEPT)) Tick("op=(const Data&)");
 399   }
 400   void operator=(DataTicker&&) noexcept(f & MA_NOEXCEPT) {
 401     if (!(f & MA_NOEXCEPT)) Tick("op=(Data&&)");
 402   }
 403 };
 404
 405 //-----------------------------------------------------------------------------
 406 // Operation counter
 407
 408 struct Counter {
 409   static int CountDC, CountCC, CountMC, CountOC, CountCA, CountMA;
 410   static int CountDestroy, CountTotalOps, CountLoggedConstruction;
 411
 412   Counter()                         noexcept { CountTotalOps++; CountDC++; }
 413   Counter(const Counter&)           noexcept { CountTotalOps++; CountCC++; }
 414   Counter(Counter&&)                noexcept { CountTotalOps++; CountMC++; }
 415   explicit Counter(std::nullptr_t)  noexcept { CountTotalOps++; CountOC++; }
 416   void operator=(const Counter&)    noexcept { CountTotalOps++; CountCA++; }
 417   void operator=(Counter&&)         noexcept { CountTotalOps++; CountMA++; }
 418   ~Counter()                      noexcept { CountTotalOps++; CountDestroy++; }
 419 };
 420
 421 int Counter::CountDC = 0;
 422 int Counter::CountCC = 0;
 423 int Counter::CountMC = 0;
 424 int Counter::CountOC = 0;
 425 int Counter::CountCA = 0;
 426 int Counter::CountMA = 0;
 427 int Counter::CountDestroy = 0;
 428 int Counter::CountTotalOps = 0;
 429 int Counter::CountLoggedConstruction = 0;
 430
 431 //-----------------------------------------------------------------------------
 432 // Tracker
 433
 434 struct Tracker {
 435   static int UID;
 436   static std::map<int, int> UIDCount;
 437   static int UIDTotal;
 438   static std::map<const Tracker*, int> Locations;
 439   static bool Print;
 440
 441   Tracker* self;
 442   int uid;
 443
 444   Tracker(Tracker* self, int uid) : self(self), uid(uid) {}
 445 };
 446
 447 template <bool isRelocatable>
 448 struct DataTracker : Tracker {
 449   DataTracker() noexcept : Tracker(this, UID++) {
 450     UIDCount[uid]++;
 451     UIDTotal++;
 452     if (!isRelocatable) Locations[self] = uid;
 453     print("Data()");
 454   }
 455   DataTracker(const DataTracker& o) noexcept : Tracker(this, o.uid) {
 456     UIDCount[uid]++;
 457     UIDTotal++;
 458     if (!isRelocatable) Locations[self] = uid;
 459     print("Data(const Data&)");
 460   }
 461   DataTracker(DataTracker&& o) noexcept : Tracker(this, o.uid) {
 462     UIDCount[uid]++;
 463     UIDTotal++;
 464     if (!isRelocatable) Locations[self] = uid;
 465     print("Data(Data&&)");
 466   }
 467
 468   explicit DataTracker(int uid) noexcept : Tracker(this, uid) {
 469     UIDCount[uid]++;
 470     UIDTotal++;
 471     if (!isRelocatable) Locations[self] = uid;
 472     print("Data(int)");
 473   }
 474
 475   ~DataTracker() noexcept {
 476     UIDCount[uid]--;
 477     UIDTotal--;
 478     if (!isRelocatable) Locations.erase(self);
 479     print("~Data()");
 480     uid = 0xdeadbeef;
 481     self = (DataTracker*)0xfeebdaed;
 482   }
 483
 484   DataTracker& operator=(const DataTracker& o) noexcept {
 485     UIDCount[uid]--;
 486     uid = o.uid;
 487     UIDCount[uid]++;
 488     if (!isRelocatable) Locations[self] = uid;
 489     print("op=(const Data&)");
 490     return *this;
 491   }
 492   DataTracker& operator=(DataTracker&& o) noexcept {
 493     UIDCount[uid]--;
 494     uid = o.uid;
 495     UIDCount[uid]++;
 496     if (!isRelocatable) Locations[self] = uid;
 497     print("op=(Data&&)");
 498     return *this;
 499   }
 500
 501   void print(const std::string& fun) {
 502     if (Print) {
 503       std::cerr << std::setw(20) << fun << ": uid = " << std::setw(3) << uid;
 504       if (!isRelocatable) std::cerr << ", self = " << self;
 505       std::cerr << std::endl;
 506     }
 507   }
 508 };
 509
 510 int Tracker::UID = 1234;
 511 std::map<int, int> Tracker::UIDCount;
 512 int Tracker::UIDTotal = 0;
 513 std::map<const Tracker*, int> Tracker::Locations;
 514 bool Tracker::Print = false;
 515
 516 //-----------------------------------------------------------------------------
 517 //-----------------------------------------------------------------------------
 518 // Data
 519
 520 template <Flags f = 0, size_t pad = 0>
 521 struct Data : DataTracker<f & IS_RELOCATABLE>,
 522               Counter, DataTicker<f>, Delete<f> {
 523   static const Flags flags = f;
 524   char spacehog[pad ? pad : 1];
 525
 526   Data() = default;
 527   Data(const Data&) = default;
 528   Data(Data&&) = default;
 529   /* implicit */ Data(int i)
 530     : DataTracker<f & IS_RELOCATABLE>(i), Counter()
 531     , DataTicker<f>(nullptr)
 532     , Delete<f>(nullptr)
 533   {}
 534   ~Data() = default;
 535   Data& operator=(const Data&) = default;
 536   Data& operator=(Data&&) = default;
 537
 538 private:
 539   int operator&() const;
 540 };
 541
 542 namespace folly {
 543 template <Flags f, size_t pad>
 544 struct IsRelocatable<Data<f, pad>>
 545   : std::integral_constant<bool,
 546       f & IS_RELOCATABLE
 547     > {};
 548 };
 549
 550 //-----------------------------------------------------------------------------
 551 //-----------------------------------------------------------------------------
 552 // Allocator
 553
 554 template <typename T>
 555 struct isPropCopy : true_type {};
 556 template <Flags f, size_t pad>
 557 struct isPropCopy<Data<f, pad>> :
 558   std::integral_constant<bool, f & PROP_COPY> {};
 559
 560 template <typename T>
 561 struct isPropMove : true_type {};
 562 template <Flags f, size_t pad>
 563 struct isPropMove<Data<f, pad>> :
 564   std::integral_constant<bool, f & PROP_MOVE> {};
 565
 566 template <typename T>
 567 struct isPropSwap : true_type {};
 568 template <Flags f, size_t pad>
 569 struct isPropSwap<Data<f, pad>> :
 570   std::integral_constant<bool, f & PROP_SWAP> {};
 571
 572
 573 struct AllocTracker {
 574   static int Constructed;
 575   static int Destroyed;
 576   static map<void*, size_t> Allocated;
 577   static map<void*, int> Owner;
 578 };
 579 int AllocTracker::Constructed = 0;
 580 int AllocTracker::Destroyed = 0;
 581 map<void*, size_t> AllocTracker::Allocated;
 582 map<void*, int> AllocTracker::Owner;
 583
 584 template <class T>
 585 struct Alloc : AllocTracker, Ticker {
 586   typedef typename std::allocator<T>::pointer pointer;
 587   typedef typename std::allocator<T>::const_pointer const_pointer;
 588   typedef typename std::allocator<T>::size_type size_type;
 589   typedef typename std::allocator<T>::value_type value_type;
 590
 591   //-----
 592   // impl
 593
 594   std::allocator<T> a;
 595   int id;
 596   explicit Alloc(int i = 8) : a(a), id(i) {}
 597   Alloc(const Alloc& o) : a(o.a), id(o.id) {}
 598   Alloc(Alloc&& o) : a(move(o.a)), id(o.id) {}
 599   Alloc& operator=(const Alloc&) = default;
 600   Alloc& operator=(Alloc&&) = default;
 601   bool operator==(const Alloc& o) const { return a == o.a && id == o.id; }
 602   bool operator!=(const Alloc& o) const { return !(*this == o); }
 603
 604   //---------
 605   // tracking
 606
 607   pointer allocate(size_type n) {
 608     if (n == 0) {
 609       cerr << "called allocate(0)" << endl;
 610       throw runtime_error("allocate fail");
 611     }
 612     Tick("allocate");
 613     auto p = a.allocate(n);
 614     Allocated[p] = n;
 615     Owner[p] = id;
 616     return p;
 617   }
 618
 619   void deallocate(pointer p, size_type n) {
 620     if (p == nullptr) {
 621       cerr << "deallocate(nullptr, " << n << ")" << endl;
 622       FAIL() << "deallocate failed";
 623     }
 624     if (Allocated[p] != n) {
 625       cerr << "deallocate(" << p << ", " << n << ") invalid: ";
 626       if (Allocated[p] == 0) cerr << "never allocated";
 627       else if (Allocated[p] == -1) cerr << "already deallocated";
 628       else cerr << "wrong number (want " << Allocated[p] << ")";
 629       cerr << endl;
 630       FAIL() << "deallocate failed";
 631     }
 632     if (Owner[p] != id) {
 633       cerr << "deallocate(" << p << "), where pointer is owned by "
 634            << Owner[p] << ", instead of self - " << id << endl;
 635       FAIL() << "deallocate failed";
 636     }
 637     Allocated[p] = -1;
 638     a.deallocate(p, n);
 639   }
 640
 641   template <class U, class... Args>
 642   void construct(U* p, Args&&... args) {
 643     Tick("construct");
 644     a.construct(p, std::forward<Args>(args)...);
 645     Constructed++;
 646   }
 647
 648   template <class U>
 649   void destroy(U* p) {
 650     Destroyed++;
 651     a.destroy(p);
 652   }
 653
 654   //--------------
 655   // container ops
 656
 657   Alloc select_on_container_copy_construction() const {
 658     Tick("select allocator for copy");
 659     return Alloc(id + 1);
 660   }
 661
 662   typedef isPropCopy<T> propagate_on_container_copy_assignment;
 663   typedef isPropMove<T> propagate_on_container_move_assignment;
 664   typedef isPropSwap<T> propagate_on_container_swap;
 665 };
 666
 667 //=============================================================================
 668 //=============================================================================
 669 // Verification and resetting
 670
 671 void softReset(int ticks = -1) {
 672   Counter::CountLoggedConstruction +=
 673     Counter::CountDC + Counter::CountCC + Counter::CountMC
 674     + Counter::CountOC - Counter::CountDestroy;
 675   Counter::CountDC = Counter::CountCC = Counter::CountMC
 676     = Counter::CountOC = Counter::CountCA = Counter::CountMA = 0;
 677   Counter::CountDestroy = Counter::CountTotalOps = 0;
 678   Ticker::CountTicks = 0;
 679   Ticker::TicksLeft = ticks;
 680 }
 681
 682 void hardReset() {
 683   Tracker::UIDCount.clear();
 684   Tracker::UIDTotal = 0;
 685   Tracker::Locations.clear();
 686   softReset();
 687   Counter::CountLoggedConstruction = 0;
 688
 689   AllocTracker::Constructed = 0;
 690   AllocTracker::Destroyed = 0;
 691   AllocTracker::Allocated.clear();
 692   AllocTracker::Owner.clear();
 693 }
 694
 695 int getTotal() {
 696   int con = Counter::CountDC + Counter::CountCC
 697           + Counter::CountMC + Counter::CountOC
 698           + Counter::CountLoggedConstruction;
 699   int del = Counter::CountDestroy;
 700   return con - del;
 701 }
 702
 703 void isSane() {
 704   int tot = getTotal();
 705   ASSERT_GE(tot, 0) << "more objects deleted than constructed";
 706
 707   ASSERT_EQ(tot, Tracker::UIDTotal)
 708     << "UIDTotal has incorrect number of objects";
 709
 710   int altTot = 0;
 711   for (const auto& kv : Tracker::UIDCount) {
 712     ASSERT_TRUE(kv.second >= 0) << "there exists " << kv.second << " Data "
 713       "with uid " << kv.first;
 714     altTot += kv.second;
 715   }
 716   ASSERT_EQ(tot, altTot) << "UIDCount corrupted";
 717
 718   if (!Tracker::Locations.empty()) { // implied by IsRelocatable
 719     ASSERT_EQ(tot, Tracker::Locations.size())
 720       << "Locations has incorrect number of objects";
 721     for (const auto& du : Tracker::Locations) {
 722       ASSERT_EQ(du.second, du.first->uid) << "Locations contains wrong uid";
 723       ASSERT_EQ(du.first, du.first->self) << "Data.self is corrupted";
 724     }
 725   }
 726 }
 727
 728 //-----------------------------------------------------------------------------
 729 // Traits
 730
 731 template <typename T>
 732 struct is_copy_constructibleAndAssignable
 733   : std::integral_constant<bool,
 734       std::is_copy_constructible<T>::value &&
 735       std::is_copy_assignable<T>::value
 736     > {};
 737
 738 template <typename T>
 739 struct is_move_constructibleAndAssignable
 740   : std::integral_constant<bool,
 741       std::is_move_constructible<T>::value &&
 742       std::is_move_assignable<T>::value
 743     > {};
 744
 745 template <class Vector>
 746 struct customAllocator
 747   : std::integral_constant<bool,
 748       !is_same<
 749         typename Vector::allocator_type,
 750         std::allocator<typename Vector::value_type>
 751       >::value
 752     > {};
 753
 754 template <typename T>
 755 struct special_move_assignable
 756   : is_move_constructibleAndAssignable<T> {};
 757 template <Flags f, size_t pad>
 758 struct special_move_assignable<Data<f, pad>>
 759   : std::integral_constant<bool,
 760       is_move_constructibleAndAssignable<Data<f, pad>>::value ||
 761       f & PROP_MOVE
 762     > {};
 763
 764 //=============================================================================
 765 //=============================================================================
 766 // Framework
 767
 768 //-----------------------------------------------------------------------------
 769 // Timing
 770
 771 uint64_t ReadTSC() {
 772    unsigned reslo, reshi;
 773
 774     __asm__ __volatile__  (
 775     "xorl %%eax,%%eax \n cpuid \n"
 776      ::: "%eax", "%ebx", "%ecx", "%edx");
 777     __asm__ __volatile__  (
 778     "rdtsc\n"
 779      : "=a" (reslo), "=d" (reshi) );
 780     __asm__ __volatile__  (
 781     "xorl %%eax,%%eax \n cpuid \n"
 782      ::: "%eax", "%ebx", "%ecx", "%edx");
 783
 784    return ((uint64_t)reshi << 32) | reslo;
 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(args...) \
 801   BOOST_PP_TUPLE_TO_SEQ(IBOOST_PP_VARIADIC_SIZE(args), (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, rawargs...)     \
 829   template <class Vector> void test_ ## name ## 2 (std::false_type) {}   \
 830   template <class Vector> void test_ ## name ## 2 (std::true_type) {     \
 831     BOOST_PP_SEQ_FOR_EACH(GEN_LOOPER, _, argseq)                         \
 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> ( rawargs );                      \
 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, args...)                                                   \
 874   template <class Vector, typename T, typename Allocator>                     \
 875   void test_ ## name (BOOST_PP_SEQ_ENUM(BOOST_PP_SEQ_TRANSFORM(               \
 876     ARGIFY, _, IBOOST_PP_VARIADIC_TO_SEQ(args))))
 877
 878 #define STL_TEST_I(ref, name, restriction, args...)                           \
 879   DECL(name, args);                                                           \
 880   MAKE_TEST(ref, name, TEST_TYPES, restriction,                               \
 881     IBOOST_PP_VARIADIC_TO_SEQ(args), args)                                    \
 882   DECL(name, args)
 883
 884 #define STL_TEST(ref, name, restriction, args...) \
 885   STL_TEST_I(ref, name, restriction, z, ## 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   google::ParseCommandLineFlags(&argc, &argv, true);
2729
2730   return RUN_ALL_TESTS();
2731 }
2732
2733 #else // GCC 4.7 guard
2734
2735 #include <gflags/gflags.h>
2736 #include <gtest/gtest.h>
2737
2738 // do nothing
2739 TEST(placeholder, gccversion) {}
2740
2741 int main(int argc, char** argv) {
2742   testing::InitGoogleTest(&argc, argv);
2743   google::ParseCommandLineFlags(&argc, &argv, true);
2744
2745   return RUN_ALL_TESTS();
2746 }
2747
2748 #endif // GCC 4.7 guard
2749