folly/test/stl_tests/StlVectorTest.cpp

   1 /*
   2  * Copyright 2012-present 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 } // namespace folly
 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   }
1425   isSane();
1426   if (::testing::Test::HasFatalFailure()) {
1427     return;
1428   }
1429   if (customAllocator<Vector>::value) {
1430     verifyAllocator(0, 0);
1431   }
1432 }
1433 template <class Vector>
1434 void verify(int extras, const Vector& v) {
1435   verifyVector(v);
1436   if (!is_arithmetic<typename Vector::value_type>::value) {
1437     ASSERT_EQ(v.size() + extras, getTotal())
1438       << "not all Data are in the vector";
1439   }
1440   isSane();
1441   if (::testing::Test::HasFatalFailure()) {
1442     return;
1443   }
1444   if (customAllocator<Vector>::value) {
1445     verifyAllocator(v.size(), v.capacity());
1446   }
1447 }
1448 template <class Vector>
1449 void verify(int extras, const Vector& v1, const Vector& v2) {
1450   verifyVector(v1);
1451   verifyVector(v2);
1452   auto size = v1.size();
1453   auto cap = v1.capacity();
1454   if (&v1 != &v2) {
1455     size += v2.size();
1456     cap += v2.capacity();
1457   }
1458   if (!is_arithmetic<typename Vector::value_type>::value) {
1459     ASSERT_EQ(size + extras, getTotal()) << "not all Data are in the vector(s)";
1460   }
1461   isSane();
1462   if (::testing::Test::HasFatalFailure()) {
1463     return;
1464   }
1465   if (customAllocator<Vector>::value) {
1466     verifyAllocator(size, cap);
1467   }
1468 }
1469
1470 //=============================================================================
1471 // Helpers
1472
1473 // save the state of a vector
1474 int convertToInt(int t) {
1475   return t;
1476 }
1477 template <Flags f, size_t pad>
1478 int convertToInt(const Data<f, pad>& t) {
1479   return t.uid;
1480 }
1481 template <typename T>
1482 int convertToInt(const std::allocator<T>&) {
1483   return -1;
1484 }
1485 template <typename T>
1486 int convertToInt(const Alloc<T>& a) {
1487   return a.id;
1488 }
1489
1490 template <class Vector>
1491 class DataState {
1492   typedef typename Vector::size_type size_type;
1493   size_type size_;
1494   int* data_;
1495
1496  public:
1497   /* implicit */ DataState(const Vector& v) {
1498     size_ = v.size();
1499     if (size_ != 0) {
1500       data_ = new int[size_];
1501       for (size_type i = 0; i < size_; ++i) {
1502         data_[i] = convertToInt(v.data()[i]);
1503       }
1504     } else {
1505       data_ = nullptr;
1506     }
1507   }
1508   ~DataState() {
1509     delete[] data_;
1510   }
1511
1512   bool operator==(const DataState& o) const {
1513     if (size_ != o.size_) {
1514       return false;
1515     }
1516     for (size_type i = 0; i < size_; ++i) {
1517       if (data_[i] != o.data_[i]) {
1518         return false;
1519       }
1520     }
1521     return true;
1522   }
1523
1524   int operator[](size_type i) {
1525     if (i >= size_) {
1526       cerr << "trying to access DataState out of bounds" << endl;
1527       exit(1);
1528     }
1529     return data_[i];
1530   }
1531
1532   size_type size() { return size_; }
1533 };
1534
1535 // downgrade iterators
1536 template <typename It, class tag>
1537 class Transformer : public boost::iterator_adaptor<
1538                             Transformer<It, tag>,
1539                             It,
1540                             typename iterator_traits<It>::value_type,
1541                             tag
1542                            > {
1543   friend class boost::iterator_core_access;
1544   shared_ptr<set<It>> dereferenced;
1545
1546  public:
1547   explicit Transformer(const It& it)
1548     : Transformer::iterator_adaptor_(it)
1549     , dereferenced(new set<It>()) {}
1550
1551   typename iterator_traits<It>::value_type& dereference() const {
1552     if (dereferenced->find(this->base_reference()) != dereferenced->end()) {
1553       cerr << "iterator dereferenced more than once" << endl;
1554       exit(1);
1555     }
1556     dereferenced->insert(this->base_reference());
1557     return *this->base_reference();
1558   }
1559 };
1560
1561 template <typename It>
1562 Transformer<It, forward_iterator_tag> makeForwardIterator(const It& it) {
1563   return Transformer<It, forward_iterator_tag>(it);
1564 }
1565 template <typename It>
1566 Transformer<It, input_iterator_tag> makeInputIterator(const It& it) {
1567   return Transformer<It, input_iterator_tag>(it);
1568 }
1569
1570 // mutate a value (in contract only)
1571 void mutate(int& i) {
1572   if ((false)) {
1573     i = 0;
1574   }
1575 }
1576 void mutate(uint64_t& i) {
1577   if ((false)) {
1578     i = 0;
1579   }
1580 }
1581 template <Flags f, size_t pad>
1582 void mutate(Data<f, pad>& ds) {
1583   if ((false)) {
1584     ds.uid = 0;
1585   }
1586 }
1587
1588 //=============================================================================
1589 // Tests
1590
1591 // #if 0
1592
1593
1594
1595 // #else
1596
1597 //-----------------------------------------------------------------------------
1598 // Container
1599
1600 STL_TEST("23.2.1 Table 96.1-7", containerTypedefs, is_destructible) {
1601   static_assert(is_same<T, typename Vector::value_type>::value,
1602     "T != Vector::value_type");
1603   static_assert(is_same<T&, typename Vector::reference>::value,
1604     "T& != Vector::reference");
1605   static_assert(is_same<const T&, typename Vector::const_reference>::value,
1606     "const T& != Vector::const_reference");
1607   static_assert(is_convertible<
1608       typename iterator_traits<typename Vector::iterator>::iterator_category,
1609       forward_iterator_tag>::value,
1610     "Vector::iterator is not a forward iterator");
1611   static_assert(is_same<T,
1612       typename iterator_traits<typename Vector::iterator>::value_type>::value,
1613     "Vector::iterator does not iterate over type T");
1614   static_assert(is_convertible<
1615       typename iterator_traits<typename Vector::const_iterator>
1616         ::iterator_category,
1617       forward_iterator_tag>::value,
1618     "Vector::const_iterator is not a forward iterator");
1619   static_assert(is_same<T,
1620       typename iterator_traits<typename Vector::const_iterator>
1621         ::value_type>::value,
1622     "Vector::const_iterator does not iterate over type T");
1623   static_assert(is_convertible<
1624       typename Vector::iterator, typename Vector::const_iterator>::value,
1625     "Vector::iterator is not convertible to Vector::const_iterator");
1626   static_assert(is_signed<typename Vector::difference_type>::value,
1627     "Vector::difference_type is not signed");
1628   static_assert(is_same<typename Vector::difference_type,
1629         typename iterator_traits<typename Vector::iterator>
1630       ::difference_type>::value,
1631     "Vector::difference_type != Vector::iterator::difference_type");
1632   static_assert(is_same<typename Vector::difference_type,
1633         typename iterator_traits<typename Vector::const_iterator>
1634       ::difference_type>::value,
1635     "Vector::difference_type != Vector::const_iterator::difference_type");
1636   static_assert(is_unsigned<typename Vector::size_type>::value,
1637     "Vector::size_type is not unsigned");
1638   static_assert(sizeof(typename Vector::size_type) >=
1639       sizeof(typename Vector::difference_type),
1640     "Vector::size_type is smaller than Vector::difference_type");
1641 }
1642
1643 STL_TEST("23.2.1 Table 96.8-9", emptyConstruction, is_destructible) {
1644   Vector u;
1645
1646   ASSERT_TRUE(u.get_allocator() == Allocator());
1647   ASSERT_EQ(0, Counter::CountTotalOps);
1648
1649   ASSERT_TRUE(u.empty()) << u.size();
1650   ASSERT_EQ(0, u.capacity());
1651
1652   if (false) {
1653     Vector();
1654   }
1655 }
1656
1657 STL_TEST("framework", populate, is_copy_constructible) {
1658   // We use emplace_back to construct vectors for testing, as well as size,
1659   // data, and capacity. We make sure these work before proceeding with tests.
1660
1661   Vector u;
1662   ASSERT_EQ(0, u.size());
1663   ASSERT_EQ(nullptr, u.data());
1664
1665   u.emplace_back(17);
1666   ASSERT_EQ(1, u.size());
1667   ASSERT_LT(u.capacity(), 100)
1668     << "single push_back increased capacity to " << u.capacity();
1669   ASSERT_NE(nullptr, u.data());
1670   ASSERT_EQ(17, convertToInt(u.data()[0]))
1671     << "first object did not get emplaced correctly";
1672
1673   for (int i = 0; i < 3; ++i) {
1674     auto cap = u.capacity();
1675     while (u.size() < cap) {
1676       u.emplace_back(22);
1677       ASSERT_EQ(cap, u.capacity()) << "Vector grew when it did not need to";
1678       ASSERT_EQ(22, convertToInt(u.data()[u.size() - 1]))
1679         << "push_back with excess capacity failed";
1680     }
1681
1682     ASSERT_EQ(cap, u.size());
1683
1684     u.emplace_back(4);
1685     ASSERT_GT(u.capacity(), cap) << "capacity did not grow on overflow";
1686     ASSERT_EQ(cap + 1, u.size());
1687     ASSERT_EQ(4, convertToInt(u.data()[u.size() - 1]))
1688       << "grow object did not get emplaced correctly";
1689   }
1690 }
1691
1692 STL_TEST("23.2.1 Table 96.10-11", copyConstruction,
1693           is_copy_constructible, a) {
1694   const auto& ca = a;
1695   DataState<Vector> dsa(ca);
1696   auto am = a.get_allocator();
1697
1698   Vector u(ca);
1699
1700   ASSERT_TRUE(std::allocator_traits<Allocator>::
1701     select_on_container_copy_construction(am) == u.get_allocator());
1702   ASSERT_TRUE(dsa == u);
1703   ASSERT_TRUE(
1704     (ca.data() == nullptr && u.data() == nullptr) ||
1705     (ca.data() != u.data())
1706   ) << "only a shallow copy was made";
1707
1708   if (false) {
1709     Vector(ca2);
1710     Vector u2 = ca2;
1711   }
1712 }
1713
1714 STL_TEST("23.2.1 Table 96.12", moveConstruction, is_destructible, a) {
1715   DataState<Vector> dsa(a);
1716   auto m = a.get_allocator();
1717
1718   Vector u(move(a));
1719
1720   ASSERT_TRUE(m == u.get_allocator());
1721   ASSERT_EQ(0, Counter::CountTotalOps);
1722
1723   ASSERT_TRUE(dsa == u);
1724
1725   if (false) {
1726     Vector u2 = move(a);
1727   }
1728 }
1729
1730 STL_TEST("23.2.1 Table 96.13", moveAssignment, special_move_assignable, a, b) {
1731   DataState<Vector> dsb(b);
1732   auto am = a.get_allocator();
1733   auto bm = b.get_allocator();
1734
1735   Vector& ret = a = std::move(b);
1736
1737   if (std::allocator_traits<Allocator>::
1738       propagate_on_container_move_assignment::value) {
1739     ASSERT_TRUE(bm == a.get_allocator());
1740   } else {
1741     ASSERT_TRUE(am == a.get_allocator());
1742   }
1743   ASSERT_TRUE(&ret == &a);
1744   ASSERT_TRUE(&a == &b || dsb == a) << "move assignment did not create a copy";
1745   // The source of the move may be left in any (albeit valid) state.
1746 }
1747
1748 STL_TEST("23.2.1 Table 96.14", destructible, is_destructible) {
1749   // The test generators check this clause already.
1750 }
1751
1752 STL_TEST("23.2.1 Table 96.15-18", iterators, is_destructible, a) {
1753   DataState<Vector> dsa(a);
1754   const auto& ca = a;
1755
1756   auto  itb =  a.begin();
1757   auto citb = ca.begin();
1758   auto Citb =  a.cbegin();
1759   auto  ite =  a.end();
1760   auto cite = ca.end();
1761   auto Cite =  a.cend();
1762
1763   ASSERT_EQ(0, Counter::CountTotalOps);
1764
1765   ASSERT_TRUE(dsa == a) << "call to begin or end modified internal data";
1766
1767   ASSERT_TRUE(citb == Citb) << "cv.begin != v.cbegin";
1768   ASSERT_TRUE(cite == Cite) << "cv.end != v.cend";
1769
1770   if (ca.size() == 0) {
1771     ASSERT_TRUE( itb ==  ite) << "begin != end when empty";
1772     ASSERT_TRUE(Citb == Cite) << "cbegin != cend when empty";
1773   } else {
1774     ASSERT_TRUE( itb !=  ite) << "begin == end when non-empty";
1775     ASSERT_TRUE(Citb != Cite) << "cbegin == cend when non-empty";
1776   }
1777
1778   auto dist = size_t(std::distance(itb, ite));
1779   auto Cdist = size_t(std::distance(Citb, Cite));
1780   ASSERT_TRUE( dist == ca.size()) << "distance(begin, end) != size";
1781   ASSERT_TRUE(Cdist == ca.size()) << "distance(cbegin, cend) != size";
1782 }
1783
1784 STL_TEST("23.2.1 Table 96.19-20", equitable, is_arithmetic, a, b) {
1785   const auto& ca = a;
1786   const auto& cb = b;
1787   DataState<Vector> dsa(a);
1788   DataState<Vector> dsb(b);
1789
1790   ASSERT_TRUE((bool)(ca == cb) == (bool)(dsa == dsb))
1791     << "== does not return equality";
1792   ASSERT_TRUE((bool)(ca == cb) != (bool)(ca != cb))
1793     << "!= is not the opposite of ==";
1794
1795   // Data is uncomparable, by design; therefore this test's restriction
1796   // is 'is_arithmetic'
1797 }
1798
1799 STL_TEST("23.2.1 Table 96.21", memberSwappable, is_destructible, a, b) {
1800   if (!std::allocator_traits<Allocator>::
1801         propagate_on_container_swap::value &&
1802       convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1803     // undefined behaviour
1804     return;
1805   }
1806
1807   DataState<Vector> dsa(a);
1808   DataState<Vector> dsb(b);
1809   auto adata = a.data();
1810   auto bdata = b.data();
1811   auto am = a.get_allocator();
1812   auto bm = b.get_allocator();
1813
1814   try {
1815     a.swap(b);
1816   } catch (...) {
1817     FAIL() << "swap is noexcept";
1818   }
1819
1820   if (std::allocator_traits<Allocator>::
1821       propagate_on_container_swap::value) {
1822     ASSERT_TRUE(bm == a.get_allocator());
1823     ASSERT_TRUE(am == b.get_allocator());
1824   } else {
1825     ASSERT_TRUE(am == a.get_allocator());
1826     ASSERT_TRUE(bm == b.get_allocator());
1827   }
1828   ASSERT_EQ(0, Counter::CountTotalOps);
1829
1830   ASSERT_TRUE(adata == b.data() && bdata == a.data());
1831   ASSERT_TRUE(dsa == b && dsb == a) << "swap did not swap";
1832 }
1833
1834 STL_TEST("23.2.1 Table 96.22", nonmemberSwappable,
1835          is_destructible, a, b) {
1836   if (!std::allocator_traits<Allocator>::
1837         propagate_on_container_swap::value &&
1838       convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1839     // undefined behaviour
1840     return;
1841   }
1842
1843   DataState<Vector> dsa(a);
1844   DataState<Vector> dsb(b);
1845   auto adata = a.data();
1846   auto bdata = b.data();
1847   auto am = a.get_allocator();
1848   auto bm = b.get_allocator();
1849
1850   try {
1851     swap(a, b);
1852   } catch (...) {
1853     FAIL() << "swap is noexcept";
1854   }
1855
1856   if (std::allocator_traits<Allocator>::
1857       propagate_on_container_swap::value) {
1858     ASSERT_TRUE(bm == a.get_allocator());
1859     ASSERT_TRUE(am == b.get_allocator());
1860   } else {
1861     ASSERT_TRUE(am == a.get_allocator());
1862     ASSERT_TRUE(bm == b.get_allocator());
1863   }
1864   ASSERT_EQ(0, Counter::CountTotalOps);
1865
1866   ASSERT_TRUE(adata == b.data() && bdata == a.data());
1867   ASSERT_TRUE(dsa == b && dsb == a) << "swap did not swap";
1868 }
1869
1870 STL_TEST("23.2.1 Table 96.23", copyAssign,
1871           is_copy_constructibleAndAssignable, a, b) {
1872   // it is possible to make use of just the copy constructor.
1873
1874   #ifdef USING_STD_VECTOR
1875   if (std::allocator_traits<Allocator>::
1876         propagate_on_container_copy_assignment::value &&
1877       convertToInt(a.get_allocator()) != convertToInt(b.get_allocator())) {
1878     // Bug. By the looks of things, in the above case, their bez is being
1879     // cleared and deallocated, but then the garbage pointers are being used.
1880     return;
1881   }
1882   #endif
1883
1884   const auto& cb = b;
1885   DataState<Vector> dsb(cb);
1886   auto am = a.get_allocator();
1887   auto bm = b.get_allocator();
1888
1889   Vector& ret = a = cb;
1890
1891   if (std::allocator_traits<Allocator>::
1892       propagate_on_container_copy_assignment::value) {
1893     ASSERT_TRUE(bm == a.get_allocator());
1894   } else {
1895     ASSERT_TRUE(am == a.get_allocator());
1896   }
1897   ASSERT_TRUE(&ret == &a);
1898   ASSERT_TRUE(dsb == a) << "copy-assign not equal to original";
1899 }
1900
1901 STL_TEST("23.2.1 Table 96.24-26", sizeops, is_destructible) {
1902   // This check generators check this clause already.
1903 }
1904
1905 //-----------------------------------------------------------------------------
1906 // Reversible container
1907
1908 STL_TEST("23.2.1 Table 97.1-2", reversibleContainerTypedefs,
1909           is_destructible) {
1910   static_assert(is_same<typename Vector::reverse_iterator,
1911       std::reverse_iterator<typename Vector::iterator>>::value,
1912     "Vector::reverse_iterator != reverse_iterator<Vector:iterator");
1913   static_assert(is_same<typename Vector::const_reverse_iterator,
1914       std::reverse_iterator<typename Vector::const_iterator>>::value,
1915     "Vector::const_reverse_iterator != "
1916     "const_reverse_iterator<Vector::iterator");
1917 }
1918
1919 STL_TEST("23.2.1 Table 97.3-5", reversibleIterators, is_destructible, a) {
1920   const auto& ca = a;
1921   DataState<Vector> ds(a);
1922
1923   auto  ritb =  a.rbegin();
1924   auto critb = ca.rbegin();
1925   auto Critb =  a.crbegin();
1926   auto  rite =  a.rend();
1927   auto crite = ca.rend();
1928   auto Crite =  a.crend();
1929
1930   ASSERT_EQ(0, Counter::CountTotalOps);
1931
1932   ASSERT_TRUE(ds == a) << "call to rbegin or rend modified internal data";
1933
1934   ASSERT_TRUE(critb == Critb) << "cv.rbegin != v.crbegin";
1935   ASSERT_TRUE(crite == Crite) << "cv.rend != v.crend";
1936
1937   if (ca.size() == 0) {
1938     ASSERT_TRUE( ritb ==  rite) << "rbegin != rend when empty";
1939     ASSERT_TRUE(Critb == Crite) << "crbegin != crend when empty";
1940   } else {
1941     ASSERT_TRUE( ritb !=  rite) << "rbegin == rend when non-empty";
1942     ASSERT_TRUE(Critb != Crite) << "crbegin == crend when non-empty";
1943   }
1944
1945   auto dist = size_t(std::distance(ritb, rite));
1946   auto Cdist = size_t(std::distance(Critb, Crite));
1947   ASSERT_TRUE( dist == ca.size()) << "distance(rbegin, rend) != size";
1948   ASSERT_TRUE(Cdist == ca.size()) << "distance(crbegin, crend) != size";
1949 }
1950
1951 //-----------------------------------------------------------------------------
1952 // Lexicographical functions
1953
1954 STL_TEST("23.2.1 Table 98", comparable, is_arithmetic) {
1955   const Vector v1 = { 1, 2, 3, 4 };
1956   const Vector v2 = { 1, 2, 3, 4, 5 };
1957   const Vector v3 = { 1, 2, 2 };
1958   const Vector v4 = { 1, 2, 2, 4, 5 };
1959   const Vector v5 = { };
1960   const Vector v6 = { 1, 2, 3, 4 };
1961
1962   ASSERT_TRUE(v1 < v2);
1963   ASSERT_TRUE(v1 > v3);
1964   ASSERT_TRUE(v1 > v4);
1965   ASSERT_TRUE(v1 > v5);
1966   ASSERT_TRUE(v1 <= v6);
1967   ASSERT_TRUE(v1 >= v6);
1968 }
1969
1970 //-----------------------------------------------------------------------------
1971 // Allocator-aware requirements (AA)
1972
1973 STL_TEST("23.2.1 Table 99.1", allocatorTypedefs, is_destructible) {
1974   static_assert(is_same<T, typename Vector::allocator_type::value_type>::value,
1975     "Vector and vector's allocator value_type mismatch");
1976 }
1977
1978 STL_TEST("23.2.1 Table 99.2", getAllocator, is_destructible) {
1979   // whitebox: ensure that a.get_allocator() returns a copy of its allocator
1980 }
1981
1982 STL_TEST("23.2.1 Table 99.3", defaultAllocator, is_destructible) {
1983   // there is nothing new to test here
1984 }
1985
1986 STL_TEST("23.2.1 Table 99.4", customAllocator, is_destructible, m) {
1987   const auto& cm = m;
1988
1989   Vector u(cm);
1990
1991   ASSERT_TRUE(u.get_allocator() == m);
1992
1993   if (false) {
1994     Vector t(m);
1995   }
1996 }
1997
1998 STL_TEST("23.2.1 Table 99.5", copyWithAllocator, is_copy_constructible, a, m) {
1999   DataState<Vector> dsa(a);
2000   const auto& ca = a;
2001   const auto& cm = m;
2002
2003   Vector u(ca, cm);
2004
2005   ASSERT_TRUE(u.get_allocator() == m);
2006   ASSERT_TRUE(dsa == u);
2007   ASSERT_TRUE(
2008     (ca.data() == nullptr && u.data() == nullptr) ||
2009     (ca.data() != u.data())
2010   ) << "only a shallow copy was made";
2011 }
2012
2013 STL_TEST("23.2.1 Table 99.6", moveConstructionWithAllocator,
2014          is_destructible, a) {
2015   // there is nothing new to test here
2016 }
2017
2018 STL_TEST("23.2.1 Table 99.6", moveConstructionWithAllocatorSupplied,
2019          is_move_constructible, a, m) {
2020   bool deep = m != a.get_allocator();
2021   auto osize = a.size();
2022   auto oalloc = AllocTracker::Constructed;
2023   const auto& cm = m;
2024
2025   Vector u(std::move(a), cm);
2026
2027   ASSERT_TRUE(u.get_allocator() == m);
2028
2029   if (deep) {
2030     if (!AllocTracker::Allocated.empty()) {
2031       ASSERT_EQ(osize, AllocTracker::Constructed - oalloc);
2032     }
2033   } else {
2034     ASSERT_EQ(0, Counter::CountTotalOps);
2035   }
2036 }
2037
2038 STL_TEST("23.2.1 Table 99.7-9", allocAssign, is_destructible) {
2039   // there is nothing new to test here
2040 }
2041
2042 STL_TEST("23.2.1-7", nAllocConstruction, is_copy_constructible, n, m) {
2043   #ifndef USING_STD_VECTOR
2044   const auto& cm = m;
2045
2046   Vector u(n, cm);
2047
2048   ASSERT_TRUE(m == u.get_allocator());
2049   #endif
2050 }
2051
2052 STL_TEST("23.2.1-7", nCopyAllocConstruction, is_copy_constructible, n, t, m) {
2053   const auto& cm = m;
2054   const auto& ct = t;
2055
2056   Vector u(n, ct, cm);
2057
2058   ASSERT_TRUE(m == u.get_allocator());
2059 }
2060
2061 STL_TEST("23.2.1-7", forwardIteratorAllocConstruction,
2062          is_destructible, i, j, m) {
2063   auto fi = makeForwardIterator(i);
2064   auto fj = makeForwardIterator(j);
2065   const auto& cfi = fi;
2066   const auto& cfj = fj;
2067   const auto& cm = m;
2068
2069   Vector u(cfi, cfj, cm);
2070
2071   ASSERT_TRUE(m == u.get_allocator());
2072 }
2073
2074 STL_TEST("23.2.1-7", inputIteratorAllocConstruction,
2075          is_move_constructible, i, j, m) {
2076   #ifdef USING_STD_VECTOR
2077   if (Ticker::TicksLeft >= 0) return;
2078   #endif
2079
2080   auto ii = makeInputIterator(i);
2081   auto ij = makeInputIterator(j);
2082   const auto& cii = ii;
2083   const auto& cij = ij;
2084   const auto& cm = m;
2085
2086   Vector u(cii, cij, cm);
2087
2088   ASSERT_TRUE(m == u.get_allocator());
2089 }
2090
2091 STL_TEST("23.2.1-7", ilAllocConstruction, is_arithmetic, m) {
2092   // gcc fail
2093   if (Ticker::TicksLeft >= 0) {
2094     return;
2095   }
2096
2097   const auto& cm = m;
2098
2099   Vector u({ 1, 4, 7 }, cm);
2100
2101   ASSERT_TRUE(m == u.get_allocator());
2102 }
2103
2104 //-----------------------------------------------------------------------------
2105 // Data races
2106
2107 STL_TEST("23.2.2", dataRaces, is_destructible) {
2108   if (false) {
2109     const Vector* cv = nullptr;
2110     typename Vector::size_type* s = nullptr;
2111
2112     cv->begin();
2113     cv->end();
2114     cv->rbegin();
2115     cv->rend();
2116     cv->front();
2117     cv->back();
2118     cv->data();
2119
2120     (*cv).at(*s);
2121     (*cv)[*s];
2122   }
2123
2124   // White-box: check that the non-const versions of each of the above
2125   // functions is implemented in terms of (or the same as) the const version
2126 }
2127
2128 //-----------------------------------------------------------------------------
2129 // Sequence container
2130
2131 STL_TEST("23.2.3 Table 100.1, alt", nConstruction, is_constructible, n) {
2132   Vector u(n);
2133
2134   ASSERT_TRUE(Allocator() == u.get_allocator());
2135   ASSERT_EQ(n, u.size());
2136   ASSERT_EQ(Counter::CountTotalOps, Counter::CountDC);
2137 }
2138
2139 STL_TEST("23.2.3 Table 100.1", nCopyConstruction,
2140          is_copy_constructible, n, t) {
2141   const auto& ct = t;
2142
2143   Vector u(n, ct);
2144
2145   ASSERT_TRUE(Allocator() == u.get_allocator());
2146   ASSERT_EQ(n, u.size()) << "Vector(n, t).size() != n" << endl;
2147   for (const auto& val : u) {
2148     ASSERT_EQ(convertToInt(t), convertToInt(val))
2149         << "not all elements of Vector(n, t) are equal to t";
2150   }
2151 }
2152
2153 STL_TEST("23.2.3 Table 100.2", forwardIteratorConstruction,
2154          is_destructible, i, j) {
2155   // All data is emplace-constructible from int, so we restrict to
2156   // is_destructible
2157
2158   auto fi = makeForwardIterator(i);
2159   auto fj = makeForwardIterator(j);
2160   const auto& cfi = fi;
2161   const auto& cfj = fj;
2162
2163   Vector u(cfi, cfj);
2164
2165   ASSERT_TRUE(Allocator() == u.get_allocator());
2166   ASSERT_LE(Counter::CountTotalOps, j-i);
2167
2168   ASSERT_EQ(j - i, u.size()) << "u(i,j).size() != j-i";
2169   for (auto it = u.begin(); it != u.end(); ++it, ++i) {
2170     ASSERT_EQ(*i, convertToInt(*it)) << "u(i,j) constructed incorrectly";
2171 }
2172 }
2173
2174 STL_TEST("23.2.3 Table 100.2", inputIteratorConstruction,
2175          is_move_constructible, i, j) {
2176   #ifdef USING_STD_VECTOR
2177   if (Ticker::TicksLeft >= 0) return;
2178   #endif
2179
2180   auto ii = makeInputIterator(i);
2181   auto ij = makeInputIterator(j);
2182   const auto& cii = ii;
2183   const auto& cij = ij;
2184
2185   Vector u(cii, cij);
2186
2187   ASSERT_TRUE(Allocator() == u.get_allocator());
2188   ASSERT_EQ(j - i, u.size()) << "u(i,j).size() != j-i";
2189   for (auto it = u.begin(); it != u.end(); ++it, ++i) {
2190     ASSERT_EQ(*i, convertToInt(*it)) << "u(i,j) constructed incorrectly";
2191 }
2192 }
2193
2194 STL_TEST("23.2.3 Table 100.3", ilConstruction, is_arithmetic) {
2195   // whitebox: ensure that Vector(il) is implemented in terms of
2196   // Vector(il.begin(), il.end())
2197
2198   // gcc fail
2199   if (Ticker::TicksLeft >= 0) {
2200     return;
2201   }
2202
2203   Vector u = { 1, 4, 7 };
2204
2205   ASSERT_TRUE(Allocator() == u.get_allocator());
2206   ASSERT_EQ(3, u.size()) << "u(il).size() fail";
2207   int i = 1;
2208   auto it = u.begin();
2209   for (; it != u.end(); ++it, i += 3) {
2210     ASSERT_EQ(i, convertToInt(*it)) << "u(il) constructed incorrectly";
2211 }
2212 }
2213
2214 STL_TEST("23.2.3 Table 100.4", ilAssignment,
2215          is_arithmetic, a) {
2216   // whitebox: ensure that assign(il) is implemented in terms of
2217   // assign(il.begin(), il.end())
2218
2219   // gcc fail
2220   if (Ticker::TicksLeft >= 0) {
2221     return;
2222   }
2223
2224   auto am = a.get_allocator();
2225
2226   Vector& b = a = { 1, 4, 7 };
2227
2228   ASSERT_TRUE(am == a.get_allocator());
2229   ASSERT_TRUE(&b == &a) << "'a = ...' did not return *this";
2230
2231   ASSERT_EQ(3, a.size()) << "u(il).size() fail";
2232   int i = 1;
2233   auto it = a.begin();
2234   for (; it != a.end(); ++it, i += 3) {
2235     ASSERT_EQ(i, convertToInt(*it)) << "u(il) constructed incorrectly";
2236 }
2237 }
2238
2239 //----------------------------
2240 // insert-and-erase subsection
2241
2242 template <class Vector>
2243 void insertNTCheck(const Vector& a, DataState<Vector>& dsa,
2244                    int idx, int n, int val) {
2245   ASSERT_EQ(dsa.size() + n, a.size());
2246   int i = 0;
2247   for (; i < idx; ++i) {
2248     ASSERT_EQ(dsa[i], convertToInt(a.data()[i])) << i;
2249   }
2250   for (; i < idx + n; ++i) {
2251     ASSERT_EQ(val, convertToInt(a.data()[i])) << i;
2252   }
2253   for (; size_t(i) < a.size(); ++i) {
2254     ASSERT_EQ(dsa[i-n], convertToInt(a.data()[i])) << i;
2255   }
2256 }
2257
2258 STL_TEST("23.2.3 Table 100.5", iteratorEmplacement,
2259          is_move_constructibleAndAssignable, a, p) {
2260   DataState<Vector> dsa(a);
2261   int idx = distance(a.begin(), p);
2262   auto am = a.get_allocator();
2263
2264   auto q = a.emplace(p, 44);
2265
2266   ASSERT_TRUE(am == a.get_allocator());
2267   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2268   insertNTCheck(a, dsa, idx, 1, 44);
2269 }
2270
2271 STL_TEST("23.2.3 Table 100.6", iteratorInsertion,
2272          is_copy_constructibleAndAssignable, a, p, t) {
2273   DataState<Vector> dsa(a);
2274   int idx = distance(a.begin(), p);
2275   int tval = convertToInt(t);
2276   auto am = a.get_allocator();
2277   const auto& ct = t;
2278
2279   auto q = a.insert(p, ct);
2280
2281   ASSERT_TRUE(am == a.get_allocator());
2282   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2283   insertNTCheck(a, dsa, idx, 1, tval);
2284 }
2285
2286 STL_TEST("23.2.3 Table 100.7", iteratorInsertionRV,
2287          is_move_constructibleAndAssignable, a, p, t) {
2288   // rvalue-references cannot have their address checked for aliased inserts
2289   if (a.data() <= addressof(t) && addressof(t) < a.data() + a.size()) {
2290     return;
2291   }
2292
2293   DataState<Vector> dsa(a);
2294   int idx = distance(a.begin(), p);
2295   int tval = convertToInt(t);
2296   auto am = a.get_allocator();
2297
2298   auto q = a.insert(p, std::move(t));
2299
2300   ASSERT_TRUE(am == a.get_allocator());
2301   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2302   insertNTCheck(a, dsa, idx, 1, tval);
2303 }
2304
2305 STL_TEST("23.2.3 Table 100.8", iteratorInsertionN,
2306          is_copy_constructibleAndAssignable, a, p, n, t) {
2307   DataState<Vector> dsa(a);
2308   int idx = distance(a.begin(), p);
2309   int tval = convertToInt(t);
2310   auto am = a.get_allocator();
2311   const auto& ct = t;
2312
2313   #ifndef USING_STD_VECTOR
2314   auto q =
2315   #endif
2316
2317   a.insert(p, n, ct);
2318
2319   ASSERT_TRUE(am == a.get_allocator());
2320   #ifndef USING_STD_VECTOR
2321   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2322   #endif
2323
2324   insertNTCheck(a, dsa, idx, n, tval);
2325 }
2326
2327 template <class Vector>
2328 void insertItCheck(const Vector& a, DataState<Vector>& dsa,
2329                    int idx, int* b, int* e) {
2330   ASSERT_EQ(dsa.size() + (e - b), a.size());
2331   int i = 0;
2332   for (; i < idx; ++i) {
2333     ASSERT_EQ(dsa[i], convertToInt(a.data()[i]));
2334   }
2335   for (; i < idx + (e - b); ++i) {
2336     ASSERT_EQ(*(b + i - idx), convertToInt(a.data()[i]));
2337   }
2338   for (; size_t(i) < a.size(); ++i) {
2339     ASSERT_EQ(dsa[i - (e - b)], convertToInt(a.data()[i]));
2340   }
2341 }
2342
2343 STL_TEST("23.2.3 Table 100.9", iteratorInsertionIterator,
2344          is_move_constructibleAndAssignable, a, p, i, j) {
2345   DataState<Vector> dsa(a);
2346   int idx = distance(a.begin(), p);
2347
2348   auto fi = makeForwardIterator(i);
2349   auto fj = makeForwardIterator(j);
2350   auto am = a.get_allocator();
2351   const auto& cfi = fi;
2352   const auto& cfj = fj;
2353
2354   #ifndef USING_STD_VECTOR
2355   auto q =
2356   #endif
2357
2358   a.insert(p, cfi, cfj);
2359
2360   ASSERT_TRUE(am == a.get_allocator());
2361   #ifndef USING_STD_VECTOR
2362   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2363   #endif
2364
2365   insertItCheck(a, dsa, idx, i, j);
2366 }
2367
2368 STL_TEST("23.2.3 Table 100.9", iteratorInsertionInputIterator,
2369          is_move_constructibleAndAssignable, a, p, i, j) {
2370   DataState<Vector> dsa(a);
2371   int idx = distance(a.begin(), p);
2372
2373   auto ii = makeInputIterator(i);
2374   auto ij = makeInputIterator(j);
2375   auto am = a.get_allocator();
2376   const auto& cii = ii;
2377   const auto& cij = ij;
2378
2379   #ifndef USING_STD_VECTOR
2380   auto q =
2381   #endif
2382
2383   a.insert(p, cii, cij);
2384
2385   ASSERT_TRUE(am == a.get_allocator());
2386   #ifndef USING_STD_VECTOR
2387   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2388   #endif
2389
2390   insertItCheck(a, dsa, idx, i, j);
2391 }
2392
2393 STL_TEST("23.2.3 Table 100.10", iteratorInsertIL,
2394          is_arithmetic, a, p) {
2395   // gcc fail
2396   if (Ticker::TicksLeft >= 0) {
2397     return;
2398   }
2399
2400   // whitebox: ensure that insert(p, il) is implemented in terms of
2401   // insert(p, il.begin(), il.end())
2402
2403   DataState<Vector> dsa(a);
2404   int idx = distance(a.begin(), p);
2405   auto am = a.get_allocator();
2406
2407   #ifndef USING_STD_VECTOR
2408   auto q =
2409   #endif
2410
2411   a.insert(p, {1, 4, 7});
2412
2413   ASSERT_TRUE(am == a.get_allocator());
2414   #ifndef USING_STD_VECTOR
2415   ASSERT_EQ(idx, distance(a.begin(), q)) << "incorrect iterator returned";
2416   #endif
2417
2418   int ila[] = { 1, 4, 7 };
2419   int* i = ila;
2420   int* j = ila + 3;
2421   insertItCheck(a, dsa, idx, i, j);
2422 }
2423
2424 template <class Vector>
2425 void eraseCheck(Vector& a, DataState<Vector>& dsa, int idx, int n) {
2426   ASSERT_EQ(dsa.size() - n, a.size());
2427   int i = 0;
2428   auto it = a.begin();
2429   for (; it != a.end(); ++it, ++i) {
2430     if (i == idx) {
2431       i += n;
2432     }
2433     ASSERT_EQ(dsa[i], convertToInt(*it));
2434   }
2435 }
2436
2437 STL_TEST("23.2.3 Table 100.11", iteratorErase, is_move_assignable, a, p) {
2438   if (p == a.end()) {
2439     return;
2440   }
2441
2442   DataState<Vector> dsa(a);
2443   int idx = distance(a.begin(), p);
2444   auto am = a.get_allocator();
2445
2446   auto rit = a.erase(p);
2447
2448   ASSERT_TRUE(am == a.get_allocator());
2449   ASSERT_EQ(idx, distance(a.begin(), rit)) << "wrong iterator returned";
2450   eraseCheck(a, dsa, idx, 1);
2451 }
2452
2453 STL_TEST("23.2.3 Table 100.12", iteratorEraseRange,
2454          is_move_assignable, a, p, q) {
2455   if (p == a.end()) {
2456     return;
2457   }
2458
2459   DataState<Vector> dsa(a);
2460   int idx = distance(a.begin(), p);
2461   auto am = a.get_allocator();
2462
2463   auto rit = a.erase(p, q);
2464
2465   ASSERT_TRUE(am == a.get_allocator());
2466   ASSERT_EQ(idx, distance(a.begin(), rit)) << "wrong iterator returned";
2467   eraseCheck(a, dsa, idx, distance(p,q));
2468 }
2469
2470 //--------------------------------
2471 // end insert-and-erase subsection
2472
2473 STL_TEST("23.2.3 Table 100.13", clear, is_destructible, a) {
2474
2475   auto am = a.get_allocator();
2476
2477   try {
2478     a.clear();
2479   } catch (...) {
2480     FAIL() << "clear must be noexcept";
2481   }
2482
2483   ASSERT_TRUE(am == a.get_allocator());
2484   ASSERT_TRUE(a.empty());
2485 }
2486
2487 STL_TEST("23.2.3 Table 100.14", assignRange, is_move_assignable, a, i, j) {
2488   auto fi = makeForwardIterator(i);
2489   auto fj = makeForwardIterator(j);
2490   const auto& cfi = fi;
2491   const auto& cfj = fj;
2492   auto am = a.get_allocator();
2493
2494   a.assign(cfi, cfj);
2495
2496   ASSERT_TRUE(am == a.get_allocator());
2497   ASSERT_EQ(distance(i, j), a.size());
2498   for (auto it = a.begin(); it != a.end(); ++it, ++i) {
2499     ASSERT_EQ(*i, convertToInt(*it));
2500 }
2501 }
2502
2503 STL_TEST("23.2.3 Table 100.14", assignInputRange,
2504          is_move_constructibleAndAssignable, a, i, j) {
2505   auto ii = makeInputIterator(i);
2506   auto ij = makeInputIterator(j);
2507   const auto& cii = ii;
2508   const auto& cij = ij;
2509   auto am = a.get_allocator();
2510
2511   a.assign(cii, cij);
2512
2513   ASSERT_TRUE(am == a.get_allocator());
2514   ASSERT_EQ(distance(i, j), a.size());
2515   for (auto it = a.begin(); it != a.end(); ++it, ++i) {
2516     ASSERT_EQ(*i, convertToInt(*it));
2517 }
2518 }
2519
2520 STL_TEST("23.2.3 Table 100.15", assignIL,
2521          is_arithmetic, a) {
2522
2523   // whitebox: ensure that assign(il) is implemented in terms of
2524   // assign(il.begin(), il.end())
2525
2526   // gcc fail
2527   if (Ticker::TicksLeft >= 0) {
2528     return;
2529   }
2530
2531   auto am = a.get_allocator();
2532
2533   a.assign({1, 4, 7});
2534
2535   ASSERT_TRUE(am == a.get_allocator());
2536   int ila[] = { 1, 4, 7 };
2537   int* i = ila;
2538
2539   ASSERT_EQ(3, a.size());
2540   for (auto it = a.begin(); it != a.end(); ++it, ++i) {
2541     ASSERT_EQ(*i, convertToInt(*it));
2542 }
2543 }
2544
2545 STL_TEST("23.2.3 Table 100.16", assignN,
2546          is_copy_constructibleAndAssignable, a, n, t) {
2547   auto am = a.get_allocator();
2548   auto const& ct = t;
2549   auto tval = convertToInt(t);
2550
2551   a.assign(n, ct);
2552
2553   ASSERT_TRUE(am == a.get_allocator());
2554   ASSERT_EQ(n, a.size());
2555   for (auto it = a.begin(); it != a.end(); ++it) {
2556     ASSERT_EQ(tval, convertToInt(*it));
2557 }
2558 }
2559
2560 STL_TEST("23.2.3 Table 101.1", front, is_destructible, a) {
2561   if (a.empty()) {
2562     return;
2563   }
2564
2565   ASSERT_TRUE(addressof(a.front()) == a.data());
2566
2567   ASSERT_EQ(0, Counter::CountTotalOps);
2568
2569   if (false) {
2570     mutate(a.front());
2571     const Vector& ca = a;
2572     ca.front();
2573   }
2574 }
2575
2576 STL_TEST("23.2.3 Table 101.2", back, is_destructible, a) {
2577   if (a.empty()) {
2578     return;
2579   }
2580
2581   ASSERT_TRUE(addressof(a.back()) == a.data() + a.size() - 1);
2582
2583   ASSERT_EQ(0, Counter::CountTotalOps);
2584
2585   if (false) {
2586     mutate(a.back());
2587     const Vector& ca = a;
2588     ca.back();
2589   }
2590 }
2591
2592 STL_TEST("23.2.3 Table 101.4", emplaceBack,
2593          is_move_constructible, a) {
2594   DataState<Vector> dsa(a);
2595   auto adata = a.data();
2596   int excess = a.capacity() - a.size();
2597   auto am = a.get_allocator();
2598
2599   try {
2600     a.emplace_back(44);
2601   } catch (...) {
2602     ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2603     throw;
2604   }
2605
2606   ASSERT_TRUE(am == a.get_allocator());
2607   if (excess > 0) {
2608     ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2609   }
2610   ASSERT_EQ(dsa.size() + 1, a.size());
2611   size_t i = 0;
2612   auto it = a.begin();
2613   for (; i < dsa.size(); ++i, ++it) {
2614     ASSERT_EQ(dsa[i], convertToInt(*it));
2615   }
2616   ASSERT_EQ(44, convertToInt(a.back()));
2617 }
2618
2619 STL_TEST("23.2.3 Table 101.7", pushBack, is_copy_constructible, a, t) {
2620   DataState<Vector> dsa(a);
2621   int tval = convertToInt(t);
2622   auto adata = a.data();
2623   int excess = a.capacity() - a.size();
2624   auto am = a.get_allocator();
2625   const auto& ct = t;
2626
2627   try {
2628     a.push_back(ct);
2629   } catch (...) {
2630     ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2631     throw;
2632   }
2633
2634   ASSERT_TRUE(am == a.get_allocator());
2635   if (excess > 0) {
2636     ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2637   }
2638   ASSERT_EQ(dsa.size() + 1, a.size());
2639   size_t i = 0;
2640   auto it = a.begin();
2641   for (; i < dsa.size(); ++i, ++it) {
2642     ASSERT_EQ(dsa[i], convertToInt(*it));
2643   }
2644   ASSERT_EQ(tval, convertToInt(a.back()));
2645 }
2646
2647 STL_TEST("23.2.3 Table 101.8", pushBackRV,
2648          is_move_constructible, a, t) {
2649   DataState<Vector> dsa(a);
2650   int tval = convertToInt(t);
2651   auto adata = a.data();
2652   int excess = a.capacity() - a.size();
2653   auto am = a.get_allocator();
2654
2655   try {
2656     a.push_back(move(t));
2657   } catch (...) {
2658     ASSERT_TRUE(dsa == a) << "failed strong exception guarantee";
2659     throw;
2660   }
2661
2662   ASSERT_TRUE(am == a.get_allocator());
2663   if (excess > 0) {
2664     ASSERT_TRUE(a.data() == adata) << "unnecessary relocation";
2665   }
2666   ASSERT_EQ(dsa.size() + 1, a.size());
2667   size_t i = 0;
2668   auto it = a.begin();
2669   for (; i < dsa.size(); ++i, ++it) {
2670     ASSERT_EQ(dsa[i], convertToInt(*it));
2671   }
2672   ASSERT_EQ(tval, convertToInt(a.back()));
2673 }
2674
2675 STL_TEST("23.2.3 Table 100.10", popBack, is_destructible, a) {
2676   if (a.empty()) {
2677     return;
2678   }
2679
2680   DataState<Vector> dsa(a);
2681   auto am = a.get_allocator();
2682
2683   a.pop_back();
2684
2685   ASSERT_TRUE(am == a.get_allocator());
2686   ASSERT_EQ(dsa.size() - 1, a.size());
2687   size_t i = 0;
2688   auto it = a.begin();
2689   for (; it != a.end(); ++it, ++i) {
2690     ASSERT_EQ(dsa[i], convertToInt(*it));
2691 }
2692 }
2693
2694 STL_TEST("23.2.3 Table 100.11", operatorBrace, is_destructible, a) {
2695   const auto& ca = a;
2696   for (size_t i = 0; i < ca.size(); ++i) {
2697     ASSERT_TRUE(addressof(ca[i]) == ca.data()+i);
2698   }
2699
2700   ASSERT_EQ(0, Counter::CountTotalOps);
2701
2702   if (false) {
2703     mutate(a[0]);
2704   }
2705 }
2706
2707 STL_TEST("23.2.3 Table 100.12", at, is_destructible, a) {
2708   const auto& ca = a;
2709   for (size_t i = 0; i < ca.size(); ++i) {
2710     ASSERT_TRUE(addressof(ca.at(i)) == ca.data()+i);
2711   }
2712
2713   ASSERT_EQ(0, Counter::CountTotalOps);
2714
2715   try {
2716     ca.at(ca.size());
2717     FAIL() << "at(size) should have thrown an error";
2718   } catch (const std::out_of_range& e) {
2719   } catch (...) {
2720     FAIL() << "at(size) threw error other than out_of_range";
2721   }
2722
2723   if (false) {
2724     mutate(a.at(0));
2725   }
2726 }
2727
2728 STL_TEST("move iterators", moveIterators, is_copy_constructibleAndAssignable) {
2729   if (false) {
2730     int* i = nullptr;
2731     int* j = nullptr;
2732
2733     auto mfi = make_move_iterator(makeForwardIterator(i));
2734     auto mfj = make_move_iterator(makeForwardIterator(j));
2735     auto mii = make_move_iterator(makeInputIterator(i));
2736     auto mij = make_move_iterator(makeInputIterator(j));
2737
2738     Vector u1(mfi, mfj);
2739     Vector u2(mii, mij);
2740
2741     u1.insert(u1.begin(), mfi, mfj);
2742     u1.insert(u1.begin(), mii, mij);
2743
2744     u1.assign(mfi, mfj);
2745     u1.assign(mii, mij);
2746   }
2747 }
2748
2749 //-----------------------------------------------------------------------------
2750 // Vector-specifics
2751
2752 STL_TEST("23.3.6.4", dataAndCapacity, is_destructible) {
2753   // there isn't anything new to test here - data and capacity are used as the
2754   // backbone of DataState. The minimal testing we might want to do is already
2755   // done in the populate test
2756 }
2757
2758 STL_TEST("23.3.6.3", reserve, is_move_constructible, a, n) {
2759   auto adata = a.data();
2760   auto ocap = a.capacity();
2761   auto am = a.get_allocator();
2762
2763   a.reserve(n);
2764
2765   ASSERT_TRUE(am == a.get_allocator());
2766   if (size_t(n) <= ocap) {
2767     ASSERT_EQ(0, Counter::CountTotalOps);
2768     ASSERT_TRUE(adata == a.data());
2769   } else {
2770     ASSERT_TRUE(a.capacity() >= size_t(n));
2771     ASSERT_LE(Counter::CountTotalOps, 2*a.size()); // move and delete
2772   }
2773 }
2774
2775 STL_TEST("23.3.6.3", lengthError, is_move_constructible) {
2776   auto mx = Vector().max_size();
2777   auto big = mx+1;
2778   if (mx >= big) {
2779     return; // max_size is the biggest size_type; overflowed
2780   }
2781
2782   Vector u;
2783   try {
2784     u.reserve(big);
2785     FAIL() << "reserve(big) should have thrown an error";
2786   } catch (const std::length_error& e) {
2787   } catch (...) {
2788     FAIL() << "reserve(big) threw error other than length_error";
2789   }
2790 }
2791
2792 STL_TEST("23.3.6.3", resize, is_copy_constructible, a, n) {
2793   DataState<Vector> dsa(a);
2794   int sz = a.size();
2795   auto am = a.get_allocator();
2796
2797   a.resize(n);
2798
2799   ASSERT_TRUE(am == a.get_allocator());
2800   ASSERT_EQ(n, a.size());
2801
2802   if (n <= sz) {
2803     for (int i = 0; i < n; ++i) {
2804       ASSERT_EQ(dsa[i], convertToInt(a[i]));
2805     }
2806   } else {
2807     for (int i = 0; i < sz; ++i) {
2808       ASSERT_EQ(dsa[i], convertToInt(a[i]));
2809     }
2810   }
2811 }
2812
2813 STL_TEST("23.3.6.3", resizeT, is_copy_constructibleAndAssignable, a, n, t) {
2814   #ifdef USING_STD_VECTOR
2815   if (a.data() <= addressof(t) && addressof(t) < a.data() + a.size()) return;
2816   #endif
2817
2818   DataState<Vector> dsa(a);
2819   int sz = a.size();
2820   auto am = a.get_allocator();
2821   const auto& ct = t;
2822   int val = convertToInt(t);
2823
2824   a.resize(n, ct);
2825
2826   ASSERT_TRUE(am == a.get_allocator());
2827   ASSERT_EQ(n, a.size());
2828
2829   if (n <= sz) {
2830     for (int i = 0; i < n; ++i) {
2831       ASSERT_EQ(dsa[i], convertToInt(a[i]));
2832     }
2833   } else {
2834     int i = 0;
2835     for ( ; i < sz; ++i) {
2836       ASSERT_EQ(dsa[i], convertToInt(a[i]));
2837     }
2838     for ( ; i < n; ++i) {
2839       ASSERT_EQ(val, convertToInt(a[i]));
2840     }
2841   }
2842 }
2843
2844 STL_TEST("23.3.6.3", shrinkToFit, is_move_constructible, a) {
2845   bool willThrow = Ticker::TicksLeft >= 0;
2846
2847   a.reserve(a.capacity() * 11);
2848
2849   auto ocap = a.capacity();
2850   DataState<Vector> dsa(a);
2851
2852   auto am = a.get_allocator();
2853
2854   try {
2855     a.shrink_to_fit();
2856   } catch (...) {
2857     FAIL() << "shrink_to_fit should swallow errors";
2858   }
2859
2860   ASSERT_TRUE(am == a.get_allocator());
2861   ASSERT_TRUE(dsa == a);
2862   if (willThrow) {
2863     //ASSERT_EQ(ocap, a.capacity()); might shrink in place
2864     throw TickException("I swallowed the error");
2865   } else {
2866     ASSERT_TRUE(a.capacity() == 0 || a.capacity() < ocap) << "Look into this";
2867   }
2868 }
2869
2870 #ifndef USING_STD_VECTOR
2871 STL_TEST("EBO", ebo, is_destructible) {
2872   static_assert(!is_same<Allocator, std::allocator<T>>::value ||
2873                 sizeof(Vector) == 3 * sizeof(void*),
2874     "fbvector has default allocator, but has size != 3*sizeof(void*)");
2875 }
2876
2877 STL_TEST("relinquish", relinquish, is_destructible, a) {
2878   auto sz = a.size();
2879   auto cap = a.capacity();
2880   auto data = a.data();
2881
2882   auto guts = relinquish(a);
2883
2884   ASSERT_EQ(data, guts);
2885   ASSERT_TRUE(a.empty());
2886   ASSERT_EQ(0, a.capacity());
2887
2888   auto alloc = a.get_allocator();
2889   for (size_t i = 0; i < sz; ++i) {
2890     std::allocator_traits<decltype(alloc)>::destroy(alloc, guts + i);
2891   }
2892   if (guts != nullptr) {
2893     if (std::is_same<
2894             decltype(alloc),
2895             std::allocator<typename decltype(alloc)::value_type>>::value) {
2896       free(guts);
2897     } else {
2898       std::allocator_traits<decltype(alloc)>::deallocate(alloc, guts, cap);
2899     }
2900   }
2901 }
2902
2903 STL_TEST("attach", attach, is_destructible, a) {
2904   DataState<Vector> dsa(a);
2905
2906   auto sz = a.size();
2907   auto cap = a.capacity();
2908   auto guts = relinquish(a);
2909
2910   ASSERT_EQ(a.data(), nullptr);
2911   attach(a, guts, sz, cap);
2912
2913   ASSERT_TRUE(dsa == a);
2914 }
2915
2916 #endif
2917
2918 // #endif
2919
2920 int main(int argc, char** argv) {
2921   testing::InitGoogleTest(&argc, argv);
2922   gflags::ParseCommandLineFlags(&argc, &argv, true);
2923
2924   return RUN_ALL_TESTS();
2925 }
2926
2927 FOLLY_POP_WARNING