folly/test/stl_tests/StlVectorTest.cpp

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