folly/test/stl_tests/StlVectorTest.cpp

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