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