clang/test/Analysis/Inputs/system-header-simulator-cxx.h

   1 // Like the compiler, the static analyzer treats some functions differently if
   2 // they come from a system header -- for example, it is assumed that system
   3 // functions do not arbitrarily free() their parameters, and that some bugs
   4 // found in system headers cannot be fixed by the user and should be
   5 // suppressed.
   6 #pragma clang system_header
   7
   8 typedef unsigned char uint8_t;
   9
  10 typedef __typeof__(sizeof(int)) size_t;
  11 typedef __typeof__((char*)0-(char*)0) ptrdiff_t;
  12 void *memmove(void *s1, const void *s2, size_t n);
  13
  14 namespace std {
  15   typedef size_t size_type;
  16 #if __cplusplus >= 201103L
  17   using nullptr_t = decltype(nullptr);
  18 #endif
  19 }
  20
  21 namespace std {
  22   struct input_iterator_tag { };
  23   struct output_iterator_tag { };
  24   struct forward_iterator_tag : public input_iterator_tag { };
  25   struct bidirectional_iterator_tag : public forward_iterator_tag { };
  26   struct random_access_iterator_tag : public bidirectional_iterator_tag { };
  27
  28   template <typename Iterator> struct iterator_traits {
  29     typedef typename Iterator::difference_type difference_type;
  30     typedef typename Iterator::value_type value_type;
  31     typedef typename Iterator::pointer pointer;
  32     typedef typename Iterator::reference reference;
  33     typedef typename Iterator::iterator_category iterator_category;
  34   };
  35 }
  36
  37 template <typename T, typename Ptr, typename Ref> struct __vector_iterator {
  38   typedef __vector_iterator<T, T *, T &> iterator;
  39   typedef __vector_iterator<T, const T *, const T &> const_iterator;
  40
  41   typedef ptrdiff_t difference_type;
  42   typedef T value_type;
  43   typedef Ptr pointer;
  44   typedef Ref reference;
  45   typedef std::random_access_iterator_tag iterator_category;
  46
  47   __vector_iterator(const Ptr p = 0) : ptr(p) {}
  48   __vector_iterator(const iterator &rhs): ptr(rhs.base()) {}
  49   __vector_iterator<T, Ptr, Ref>& operator++() { ++ ptr; return *this; }
  50   __vector_iterator<T, Ptr, Ref> operator++(int) {
  51     auto tmp = *this;
  52     ++ ptr;
  53     return tmp;
  54   }
  55   __vector_iterator<T, Ptr, Ref> operator--() { -- ptr; return *this; }
  56   __vector_iterator<T, Ptr, Ref> operator--(int) {
  57     auto tmp = *this; -- ptr;
  58     return tmp;
  59   }
  60   __vector_iterator<T, Ptr, Ref> operator+(difference_type n) {
  61     return ptr + n;
  62   }
  63   friend __vector_iterator<T, Ptr, Ref> operator+(
  64       difference_type n,
  65       const __vector_iterator<T, Ptr, Ref> &iter) {
  66     return n + iter.ptr;
  67   }
  68   __vector_iterator<T, Ptr, Ref> operator-(difference_type n) {
  69     return ptr - n;
  70   }
  71   __vector_iterator<T, Ptr, Ref> operator+=(difference_type n) {
  72     return ptr += n;
  73   }
  74   __vector_iterator<T, Ptr, Ref> operator-=(difference_type n) {
  75     return ptr -= n;
  76   }
  77
  78   template<typename U, typename Ptr2, typename Ref2>
  79   difference_type operator-(const __vector_iterator<U, Ptr2, Ref2> &rhs);
  80
  81   Ref operator*() const { return *ptr; }
  82   Ptr operator->() const { return ptr; }
  83
  84   Ref operator[](difference_type n) {
  85     return *(ptr+n);
  86   }
  87
  88   bool operator==(const iterator &rhs) const { return ptr == rhs.ptr; }
  89   bool operator==(const const_iterator &rhs) const { return ptr == rhs.ptr; }
  90
  91   bool operator!=(const iterator &rhs) const { return ptr != rhs.ptr; }
  92   bool operator!=(const const_iterator &rhs) const { return ptr != rhs.ptr; }
  93
  94   const Ptr& base() const { return ptr; }
  95
  96 private:
  97   Ptr ptr;
  98 };
  99
 100 template <typename T, typename Ptr, typename Ref> struct __deque_iterator {
 101   typedef __deque_iterator<T, T *, T &> iterator;
 102   typedef __deque_iterator<T, const T *, const T &> const_iterator;
 103
 104   typedef ptrdiff_t difference_type;
 105   typedef T value_type;
 106   typedef Ptr pointer;
 107   typedef Ref reference;
 108   typedef std::random_access_iterator_tag iterator_category;
 109
 110   __deque_iterator(const Ptr p = 0) : ptr(p) {}
 111   __deque_iterator(const iterator &rhs): ptr(rhs.base()) {}
 112   __deque_iterator<T, Ptr, Ref>& operator++() { ++ ptr; return *this; }
 113   __deque_iterator<T, Ptr, Ref> operator++(int) {
 114     auto tmp = *this;
 115     ++ ptr;
 116     return tmp;
 117   }
 118   __deque_iterator<T, Ptr, Ref> operator--() { -- ptr; return *this; }
 119   __deque_iterator<T, Ptr, Ref> operator--(int) {
 120     auto tmp = *this; -- ptr;
 121     return tmp;
 122   }
 123   __deque_iterator<T, Ptr, Ref> operator+(difference_type n) {
 124     return ptr + n;
 125   }
 126   friend __deque_iterator<T, Ptr, Ref> operator+(
 127       difference_type n,
 128       const __deque_iterator<T, Ptr, Ref> &iter) {
 129     return n + iter.ptr;
 130   }
 131   __deque_iterator<T, Ptr, Ref> operator-(difference_type n) {
 132     return ptr - n;
 133   }
 134   __deque_iterator<T, Ptr, Ref> operator+=(difference_type n) {
 135     return ptr += n;
 136   }
 137   __deque_iterator<T, Ptr, Ref> operator-=(difference_type n) {
 138     return ptr -= n;
 139   }
 140
 141   Ref operator*() const { return *ptr; }
 142   Ptr operator->() const { return ptr; }
 143
 144   Ref operator[](difference_type n) {
 145     return *(ptr+n);
 146   }
 147
 148   bool operator==(const iterator &rhs) const { return ptr == rhs.ptr; }
 149   bool operator==(const const_iterator &rhs) const { return ptr == rhs.ptr; }
 150
 151   bool operator!=(const iterator &rhs) const { return ptr != rhs.ptr; }
 152   bool operator!=(const const_iterator &rhs) const { return ptr != rhs.ptr; }
 153
 154   const Ptr& base() const { return ptr; }
 155
 156 private:
 157   Ptr ptr;
 158 };
 159
 160 template <typename T, typename Ptr, typename Ref> struct __list_iterator {
 161   typedef __list_iterator<T, __typeof__(T::data) *, __typeof__(T::data) &> iterator;
 162   typedef __list_iterator<T, const __typeof__(T::data) *, const __typeof__(T::data) &> const_iterator;
 163
 164   typedef ptrdiff_t difference_type;
 165   typedef T value_type;
 166   typedef Ptr pointer;
 167   typedef Ref reference;
 168   typedef std::bidirectional_iterator_tag iterator_category;
 169
 170   __list_iterator(T* it = 0) : item(it) {}
 171   __list_iterator(const iterator &rhs): item(rhs.item) {}
 172   __list_iterator<T, Ptr, Ref>& operator++() { item = item->next; return *this; }
 173   __list_iterator<T, Ptr, Ref> operator++(int) {
 174     auto tmp = *this;
 175     item = item->next;
 176     return tmp;
 177   }
 178   __list_iterator<T, Ptr, Ref> operator--() { item = item->prev; return *this; }
 179   __list_iterator<T, Ptr, Ref> operator--(int) {
 180     auto tmp = *this;
 181     item = item->prev;
 182     return tmp;
 183   }
 184
 185   Ref operator*() const { return item->data; }
 186   Ptr operator->() const { return &item->data; }
 187
 188   bool operator==(const iterator &rhs) const { return item == rhs->item; }
 189   bool operator==(const const_iterator &rhs) const { return item == rhs->item; }
 190
 191   bool operator!=(const iterator &rhs) const { return item != rhs->item; }
 192   bool operator!=(const const_iterator &rhs) const { return item != rhs->item; }
 193
 194   const T* &base() const { return item; }
 195
 196   template <typename UT, typename UPtr, typename URef>
 197   friend struct __list_iterator;
 198
 199 private:
 200   T* item;
 201 };
 202
 203 template <typename T, typename Ptr, typename Ref> struct __fwdl_iterator {
 204   typedef __fwdl_iterator<T, __typeof__(T::data) *, __typeof__(T::data) &> iterator;
 205   typedef __fwdl_iterator<T, const __typeof__(T::data) *, const __typeof__(T::data) &> const_iterator;
 206
 207   typedef ptrdiff_t difference_type;
 208   typedef T value_type;
 209   typedef Ptr pointer;
 210   typedef Ref reference;
 211   typedef std::forward_iterator_tag iterator_category;
 212
 213   __fwdl_iterator(T* it = 0) : item(it) {}
 214   __fwdl_iterator(const iterator &rhs): item(rhs.item) {}
 215   __fwdl_iterator<T, Ptr, Ref>& operator++() { item = item->next; return *this; }
 216   __fwdl_iterator<T, Ptr, Ref> operator++(int) {
 217     auto tmp = *this;
 218     item = item->next;
 219     return tmp;
 220   }
 221   Ref operator*() const { return item->data; }
 222   Ptr operator->() const { return &item->data; }
 223
 224   bool operator==(const iterator &rhs) const { return item == rhs->item; }
 225   bool operator==(const const_iterator &rhs) const { return item == rhs->item; }
 226
 227   bool operator!=(const iterator &rhs) const { return item != rhs->item; }
 228   bool operator!=(const const_iterator &rhs) const { return item != rhs->item; }
 229
 230   const T* &base() const { return item; }
 231
 232   template <typename UT, typename UPtr, typename URef>
 233   friend struct __fwdl_iterator;
 234
 235 private:
 236   T* item;
 237 };
 238
 239 namespace std {
 240   template <class T1, class T2>
 241   struct pair {
 242     T1 first;
 243     T2 second;
 244
 245     pair() : first(), second() {}
 246     pair(const T1 &a, const T2 &b) : first(a), second(b) {}
 247
 248     template<class U1, class U2>
 249     pair(const pair<U1, U2> &other) : first(other.first),
 250                                       second(other.second) {}
 251   };
 252
 253   typedef __typeof__(sizeof(int)) size_t;
 254
 255   template <class T> class initializer_list;
 256
 257   template< class T > struct remove_reference      {typedef T type;};
 258   template< class T > struct remove_reference<T&>  {typedef T type;};
 259   template< class T > struct remove_reference<T&&> {typedef T type;};
 260
 261   template<class T>
 262   typename remove_reference<T>::type&& move(T&& a) {
 263     typedef typename remove_reference<T>::type&& RvalRef;
 264     return static_cast<RvalRef>(a);
 265   }
 266
 267   template <class T>
 268   void swap(T &a, T &b) {
 269     T c(std::move(a));
 270     a = std::move(b);
 271     b = std::move(c);
 272   }
 273
 274   template<typename T>
 275   class vector {
 276     T *_start;
 277     T *_finish;
 278     T *_end_of_storage;
 279
 280   public:
 281     typedef T value_type;
 282     typedef size_t size_type;
 283     typedef __vector_iterator<T, T *, T &> iterator;
 284     typedef __vector_iterator<T, const T *, const T &> const_iterator;
 285
 286     vector() : _start(0), _finish(0), _end_of_storage(0) {}
 287     template <typename InputIterator>
 288     vector(InputIterator first, InputIterator last);
 289     vector(const vector &other);
 290     vector(vector &&other);
 291     ~vector();
 292
 293     size_t size() const {
 294       return size_t(_finish - _start);
 295     }
 296
 297     vector& operator=(const vector &other);
 298     vector& operator=(vector &&other);
 299     vector& operator=(std::initializer_list<T> ilist);
 300
 301     void assign(size_type count, const T &value);
 302     template <typename InputIterator >
 303     void assign(InputIterator first, InputIterator last);
 304     void assign(std::initializer_list<T> ilist);
 305
 306     void clear();
 307
 308     void push_back(const T &value);
 309     void push_back(T &&value);
 310     template<class... Args>
 311     void emplace_back(Args&&... args);
 312     void pop_back();
 313
 314     iterator insert(const_iterator position, const value_type &val);
 315     iterator insert(const_iterator position, size_type n,
 316                     const value_type &val);
 317     template <typename InputIterator>
 318     iterator insert(const_iterator position, InputIterator first,
 319                     InputIterator last);
 320     iterator insert(const_iterator position, value_type &&val);
 321     iterator insert(const_iterator position, initializer_list<value_type> il);
 322
 323     template <class... Args>
 324     iterator emplace(const_iterator position, Args&&... args);
 325
 326     iterator erase(const_iterator position);
 327     iterator erase(const_iterator first, const_iterator last);
 328
 329     T &operator[](size_t n) {
 330       return _start[n];
 331     }
 332
 333     const T &operator[](size_t n) const {
 334       return _start[n];
 335     }
 336
 337     iterator begin() { return iterator(_start); }
 338     const_iterator begin() const { return const_iterator(_start); }
 339     const_iterator cbegin() const { return const_iterator(_start); }
 340     iterator end() { return iterator(_finish); }
 341     const_iterator end() const { return const_iterator(_finish); }
 342     const_iterator cend() const { return const_iterator(_finish); }
 343     T& front() { return *begin(); }
 344     const T& front() const { return *begin(); }
 345     T& back() { return *(end() - 1); }
 346     const T& back() const { return *(end() - 1); }
 347   };
 348
 349   template<typename T>
 350   class list {
 351     struct __item {
 352       T data;
 353       __item *prev, *next;
 354     } *_start, *_finish;
 355
 356   public:
 357     typedef T value_type;
 358     typedef size_t size_type;
 359     typedef __list_iterator<__item, T *, T &> iterator;
 360     typedef __list_iterator<__item, const T *, const T &> const_iterator;
 361
 362     list() : _start(0), _finish(0) {}
 363     template <typename InputIterator>
 364     list(InputIterator first, InputIterator last);
 365     list(const list &other);
 366     list(list &&other);
 367     ~list();
 368
 369     list& operator=(const list &other);
 370     list& operator=(list &&other);
 371     list& operator=(std::initializer_list<T> ilist);
 372
 373     void assign(size_type count, const T &value);
 374     template <typename InputIterator >
 375     void assign(InputIterator first, InputIterator last);
 376     void assign(std::initializer_list<T> ilist);
 377
 378     void clear();
 379
 380     void push_back(const T &value);
 381     void push_back(T &&value);
 382     template<class... Args>
 383     void emplace_back(Args&&... args);
 384     void pop_back();
 385
 386     void push_front(const T &value);
 387     void push_front(T &&value);
 388     template<class... Args>
 389     void emplace_front(Args&&... args);
 390     void pop_front();
 391
 392     iterator insert(const_iterator position, const value_type &val);
 393     iterator insert(const_iterator position, size_type n,
 394                     const value_type &val);
 395     template <typename InputIterator>
 396     iterator insert(const_iterator position, InputIterator first,
 397                     InputIterator last);
 398     iterator insert(const_iterator position, value_type &&val);
 399     iterator insert(const_iterator position, initializer_list<value_type> il);
 400
 401     template <class... Args>
 402     iterator emplace(const_iterator position, Args&&... args);
 403
 404     iterator erase(const_iterator position);
 405     iterator erase(const_iterator first, const_iterator last);
 406
 407     iterator begin() { return iterator(_start); }
 408     const_iterator begin() const { return const_iterator(_start); }
 409     const_iterator cbegin() const { return const_iterator(_start); }
 410     iterator end() { return iterator(_finish); }
 411     const_iterator end() const { return const_iterator(_finish); }
 412     const_iterator cend() const { return const_iterator(_finish); }
 413
 414     T& front() { return *begin(); }
 415     const T& front() const { return *begin(); }
 416     T& back() { return *--end(); }
 417     const T& back() const { return *--end(); }
 418   };
 419
 420   template<typename T>
 421   class deque {
 422     T *_start;
 423     T *_finish;
 424     T *_end_of_storage;
 425
 426   public:
 427     typedef T value_type;
 428     typedef size_t size_type;
 429     typedef __deque_iterator<T, T *, T &> iterator;
 430     typedef __deque_iterator<T, const T *, const T &> const_iterator;
 431
 432     deque() : _start(0), _finish(0), _end_of_storage(0) {}
 433     template <typename InputIterator>
 434     deque(InputIterator first, InputIterator last);
 435     deque(const deque &other);
 436     deque(deque &&other);
 437     ~deque();
 438
 439     size_t size() const {
 440       return size_t(_finish - _start);
 441     }
 442
 443     deque& operator=(const deque &other);
 444     deque& operator=(deque &&other);
 445     deque& operator=(std::initializer_list<T> ilist);
 446
 447     void assign(size_type count, const T &value);
 448     template <typename InputIterator >
 449     void assign(InputIterator first, InputIterator last);
 450     void assign(std::initializer_list<T> ilist);
 451
 452     void clear();
 453
 454     void push_back(const T &value);
 455     void push_back(T &&value);
 456     template<class... Args>
 457     void emplace_back(Args&&... args);
 458     void pop_back();
 459
 460     void push_front(const T &value);
 461     void push_front(T &&value);
 462     template<class... Args>
 463     void emplace_front(Args&&... args);
 464     void pop_front();
 465
 466     iterator insert(const_iterator position, const value_type &val);
 467     iterator insert(const_iterator position, size_type n,
 468                     const value_type &val);
 469     template <typename InputIterator>
 470     iterator insert(const_iterator position, InputIterator first,
 471                     InputIterator last);
 472     iterator insert(const_iterator position, value_type &&val);
 473     iterator insert(const_iterator position, initializer_list<value_type> il);
 474
 475     template <class... Args>
 476     iterator emplace(const_iterator position, Args&&... args);
 477
 478     iterator erase(const_iterator position);
 479     iterator erase(const_iterator first, const_iterator last);
 480
 481     T &operator[](size_t n) {
 482       return _start[n];
 483     }
 484
 485     const T &operator[](size_t n) const {
 486       return _start[n];
 487     }
 488
 489     iterator begin() { return iterator(_start); }
 490     const_iterator begin() const { return const_iterator(_start); }
 491     const_iterator cbegin() const { return const_iterator(_start); }
 492     iterator end() { return iterator(_finish); }
 493     const_iterator end() const { return const_iterator(_finish); }
 494     const_iterator cend() const { return const_iterator(_finish); }
 495     T& front() { return *begin(); }
 496     const T& front() const { return *begin(); }
 497     T& back() { return *(end() - 1); }
 498     const T& back() const { return *(end() - 1); }
 499   };
 500
 501   template<typename T>
 502   class forward_list {
 503     struct __item {
 504       T data;
 505       __item *next;
 506     } *_start;
 507
 508   public:
 509     typedef T value_type;
 510     typedef size_t size_type;
 511     typedef __fwdl_iterator<__item, T *, T &> iterator;
 512     typedef __fwdl_iterator<__item, const T *, const T &> const_iterator;
 513
 514     forward_list() : _start(0) {}
 515     template <typename InputIterator>
 516     forward_list(InputIterator first, InputIterator last);
 517     forward_list(const forward_list &other);
 518     forward_list(forward_list &&other);
 519     ~forward_list();
 520
 521     forward_list& operator=(const forward_list &other);
 522     forward_list& operator=(forward_list &&other);
 523     forward_list& operator=(std::initializer_list<T> ilist);
 524
 525     void assign(size_type count, const T &value);
 526     template <typename InputIterator >
 527     void assign(InputIterator first, InputIterator last);
 528     void assign(std::initializer_list<T> ilist);
 529
 530     void clear();
 531
 532     void push_front(const T &value);
 533     void push_front(T &&value);
 534     template<class... Args>
 535     void emplace_front(Args&&... args);
 536     void pop_front();
 537
 538     iterator insert_after(const_iterator position, const value_type &val);
 539     iterator insert_after(const_iterator position, value_type &&val);
 540     iterator insert_after(const_iterator position, size_type n,
 541                           const value_type &val);
 542     template <typename InputIterator>
 543     iterator insert_after(const_iterator position, InputIterator first,
 544                           InputIterator last);
 545     iterator insert_after(const_iterator position,
 546                           initializer_list<value_type> il);
 547
 548     template <class... Args>
 549     iterator emplace_after(const_iterator position, Args&&... args);
 550
 551     iterator erase_after(const_iterator position);
 552     iterator erase_after(const_iterator first, const_iterator last);
 553
 554     iterator begin() { return iterator(_start); }
 555     const_iterator begin() const { return const_iterator(_start); }
 556     const_iterator cbegin() const { return const_iterator(_start); }
 557     iterator end() { return iterator(); }
 558     const_iterator end() const { return const_iterator(); }
 559     const_iterator cend() const { return const_iterator(); }
 560
 561     T& front() { return *begin(); }
 562     const T& front() const { return *begin(); }
 563   };
 564
 565   template <typename CharT>
 566   class basic_string {
 567     class Allocator {};
 568
 569   public:
 570     basic_string() : basic_string(Allocator()) {}
 571     explicit basic_string(const Allocator &alloc);
 572     basic_string(size_type count, CharT ch,
 573                  const Allocator &alloc = Allocator());
 574     basic_string(const basic_string &other,
 575                  size_type pos,
 576                  const Allocator &alloc = Allocator());
 577     basic_string(const basic_string &other,
 578                  size_type pos, size_type count,
 579                  const Allocator &alloc = Allocator());
 580     basic_string(const CharT *s, size_type count,
 581                  const Allocator &alloc = Allocator());
 582     basic_string(const CharT *s,
 583                  const Allocator &alloc = Allocator());
 584     template <class InputIt>
 585     basic_string(InputIt first, InputIt last,
 586                  const Allocator &alloc = Allocator());
 587     basic_string(const basic_string &other);
 588     basic_string(const basic_string &other,
 589                  const Allocator &alloc);
 590     basic_string(basic_string &&other);
 591     basic_string(basic_string &&other,
 592                  const Allocator &alloc);
 593     basic_string(std::initializer_list<CharT> ilist,
 594                  const Allocator &alloc = Allocator());
 595     template <class T>
 596     basic_string(const T &t, size_type pos, size_type n,
 597                  const Allocator &alloc = Allocator());
 598     // basic_string(std::nullptr_t) = delete;
 599
 600     ~basic_string();
 601     void clear();
 602
 603     basic_string &operator=(const basic_string &str);
 604     basic_string &operator+=(const basic_string &str);
 605
 606     const CharT *c_str() const;
 607     const CharT *data() const;
 608     CharT *data();
 609
 610     const char *begin() const;
 611     const char *end() const;
 612
 613     basic_string &append(size_type count, CharT ch);
 614     basic_string &assign(size_type count, CharT ch);
 615     basic_string &erase(size_type index, size_type count);
 616     basic_string &insert(size_type index, size_type count, CharT ch);
 617     basic_string &replace(size_type pos, size_type count, const basic_string &str);
 618     void pop_back();
 619     void push_back(CharT ch);
 620     void reserve(size_type new_cap);
 621     void resize(size_type count);
 622     void shrink_to_fit();
 623     void swap(basic_string &other);
 624   };
 625
 626   typedef basic_string<char> string;
 627   typedef basic_string<wchar_t> wstring;
 628 #if __cplusplus >= 201103L
 629   typedef basic_string<char16_t> u16string;
 630   typedef basic_string<char32_t> u32string;
 631 #endif
 632
 633   class exception {
 634   public:
 635     exception() throw();
 636     virtual ~exception() throw();
 637     virtual const char *what() const throw() {
 638       return 0;
 639     }
 640   };
 641
 642   class bad_alloc : public exception {
 643     public:
 644     bad_alloc() throw();
 645     bad_alloc(const bad_alloc&) throw();
 646     bad_alloc& operator=(const bad_alloc&) throw();
 647     virtual const char* what() const throw() {
 648       return 0;
 649     }
 650   };
 651
 652   struct nothrow_t {};
 653   extern const nothrow_t nothrow;
 654
 655   enum class align_val_t : size_t {};
 656
 657   // libc++'s implementation
 658   template <class _E>
 659   class initializer_list
 660   {
 661     const _E* __begin_;
 662     size_t    __size_;
 663
 664     initializer_list(const _E* __b, size_t __s)
 665       : __begin_(__b),
 666         __size_(__s)
 667     {}
 668
 669   public:
 670     typedef _E        value_type;
 671     typedef const _E& reference;
 672     typedef const _E& const_reference;
 673     typedef size_t    size_type;
 674
 675     typedef const _E* iterator;
 676     typedef const _E* const_iterator;
 677
 678     initializer_list() : __begin_(0), __size_(0) {}
 679
 680     size_t    size()  const {return __size_;}
 681     const _E* begin() const {return __begin_;}
 682     const _E* end()   const {return __begin_ + __size_;}
 683   };
 684
 685   template <bool, class _Tp = void> struct enable_if {};
 686   template <class _Tp> struct enable_if<true, _Tp> {typedef _Tp type;};
 687
 688   template <class _Tp, _Tp __v>
 689   struct integral_constant
 690   {
 691       static const _Tp      value = __v;
 692       typedef _Tp               value_type;
 693       typedef integral_constant type;
 694
 695      operator value_type() const {return value;}
 696
 697      value_type operator ()() const {return value;}
 698   };
 699
 700   template <class _Tp, _Tp __v>
 701   const _Tp integral_constant<_Tp, __v>::value;
 702
 703     template <class _Tp, class _Arg>
 704     struct is_trivially_assignable
 705       : integral_constant<bool, __is_trivially_assignable(_Tp, _Arg)>
 706     {
 707     };
 708
 709   typedef integral_constant<bool,true>  true_type;
 710   typedef integral_constant<bool,false> false_type;
 711
 712   template <class _Tp> struct is_const            : public false_type {};
 713   template <class _Tp> struct is_const<_Tp const> : public true_type {};
 714
 715   template <class _Tp> struct  is_reference        : public false_type {};
 716   template <class _Tp> struct  is_reference<_Tp&>  : public true_type {};
 717
 718   template <class _Tp, class _Up> struct  is_same           : public false_type {};
 719   template <class _Tp>            struct  is_same<_Tp, _Tp> : public true_type {};
 720
 721   template <class _Tp, bool = is_const<_Tp>::value || is_reference<_Tp>::value    >
 722   struct __add_const             {typedef _Tp type;};
 723
 724   template <class _Tp>
 725   struct __add_const<_Tp, false> {typedef const _Tp type;};
 726
 727   template <class _Tp> struct add_const {typedef typename __add_const<_Tp>::type type;};
 728
 729   template <class _Tp> struct  remove_const            {typedef _Tp type;};
 730   template <class _Tp> struct  remove_const<const _Tp> {typedef _Tp type;};
 731
 732   template <class _Tp> struct  add_lvalue_reference    {typedef _Tp& type;};
 733
 734   template <class _Tp> struct is_trivially_copy_assignable
 735       : public is_trivially_assignable<typename add_lvalue_reference<_Tp>::type,
 736             typename add_lvalue_reference<typename add_const<_Tp>::type>::type> {};
 737
 738     template<class InputIter, class OutputIter>
 739     OutputIter __copy(InputIter II, InputIter IE, OutputIter OI) {
 740       while (II != IE)
 741         *OI++ = *II++;
 742
 743       return OI;
 744     }
 745
 746   template <class _Tp, class _Up>
 747   inline
 748   typename enable_if
 749   <
 750       is_same<typename remove_const<_Tp>::type, _Up>::value &&
 751       is_trivially_copy_assignable<_Up>::value,
 752       _Up*
 753   >::type __copy(_Tp* __first, _Tp* __last, _Up* __result) {
 754       size_t __n = __last - __first;
 755
 756       if (__n > 0)
 757         memmove(__result, __first, __n * sizeof(_Up));
 758
 759       return __result + __n;
 760     }
 761
 762   template<class InputIter, class OutputIter>
 763   OutputIter copy(InputIter II, InputIter IE, OutputIter OI) {
 764     return __copy(II, IE, OI);
 765   }
 766
 767   template <class _BidirectionalIterator, class _OutputIterator>
 768   inline
 769   _OutputIterator
 770   __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last,
 771                   _OutputIterator __result)
 772   {
 773       while (__first != __last)
 774           *--__result = *--__last;
 775       return __result;
 776   }
 777
 778   template <class _Tp, class _Up>
 779   inline
 780   typename enable_if
 781   <
 782       is_same<typename remove_const<_Tp>::type, _Up>::value &&
 783       is_trivially_copy_assignable<_Up>::value,
 784       _Up*
 785   >::type __copy_backward(_Tp* __first, _Tp* __last, _Up* __result) {
 786       size_t __n = __last - __first;
 787
 788     if (__n > 0)
 789     {
 790         __result -= __n;
 791         memmove(__result, __first, __n * sizeof(_Up));
 792     }
 793     return __result;
 794   }
 795
 796   template<class InputIter, class OutputIter>
 797   OutputIter copy_backward(InputIter II, InputIter IE, OutputIter OI) {
 798     return __copy_backward(II, IE, OI);
 799   }
 800 }
 801
 802 template <class BidirectionalIterator, class Distance>
 803 void __advance(BidirectionalIterator& it, Distance n,
 804                std::bidirectional_iterator_tag)
 805 #if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 2
 806 {
 807   if (n >= 0) while(n-- > 0) ++it; else while (n++<0) --it;
 808 }
 809 #else
 810     ;
 811 #endif
 812
 813 template <class RandomAccessIterator, class Distance>
 814 void __advance(RandomAccessIterator& it, Distance n,
 815                std::random_access_iterator_tag)
 816 #if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 2
 817 {
 818   it += n;
 819 }
 820 #else
 821     ;
 822 #endif
 823
 824 namespace std {
 825
 826 template <class InputIterator, class Distance>
 827 void advance(InputIterator& it, Distance n)
 828 #if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 1
 829 {
 830   __advance(it, n, typename InputIterator::iterator_category());
 831 }
 832 #else
 833     ;
 834 #endif
 835
 836 template <class BidirectionalIterator>
 837 BidirectionalIterator
 838 prev(BidirectionalIterator it,
 839      typename iterator_traits<BidirectionalIterator>::difference_type n =
 840          1)
 841 #if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 0
 842 {
 843   advance(it, -n);
 844   return it;
 845 }
 846 #else
 847     ;
 848 #endif
 849
 850 template <class ForwardIterator>
 851 ForwardIterator
 852 next(ForwardIterator it,
 853      typename iterator_traits<ForwardIterator>::difference_type n =
 854          1)
 855 #if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 0
 856 {
 857   advance(it, n);
 858   return it;
 859 }
 860 #else
 861     ;
 862 #endif
 863
 864   template <class InputIt, class T>
 865   InputIt find(InputIt first, InputIt last, const T& value);
 866
 867   template <class ExecutionPolicy, class ForwardIt, class T>
 868   ForwardIt find(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
 869                  const T& value);
 870
 871   template <class InputIt, class UnaryPredicate>
 872   InputIt find_if (InputIt first, InputIt last, UnaryPredicate p);
 873
 874   template <class ExecutionPolicy, class ForwardIt, class UnaryPredicate>
 875   ForwardIt find_if (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
 876                      UnaryPredicate p);
 877
 878   template <class InputIt, class UnaryPredicate>
 879   InputIt find_if_not (InputIt first, InputIt last, UnaryPredicate q);
 880
 881   template <class ExecutionPolicy, class ForwardIt, class UnaryPredicate>
 882   ForwardIt find_if_not (ExecutionPolicy&& policy, ForwardIt first,
 883                          ForwardIt last, UnaryPredicate q);
 884
 885   template <class InputIt, class ForwardIt>
 886   InputIt find_first_of(InputIt first, InputIt last,
 887                          ForwardIt s_first, ForwardIt s_last);
 888
 889   template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
 890   ForwardIt1 find_first_of (ExecutionPolicy&& policy,
 891                             ForwardIt1 first, ForwardIt1 last,
 892                             ForwardIt2 s_first, ForwardIt2 s_last);
 893
 894   template <class InputIt, class ForwardIt, class BinaryPredicate>
 895   InputIt find_first_of (InputIt first, InputIt last,
 896                          ForwardIt s_first, ForwardIt s_last,
 897                          BinaryPredicate p );
 898
 899   template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
 900             class BinaryPredicate>
 901   ForwardIt1 find_first_of (ExecutionPolicy&& policy,
 902                             ForwardIt1 first, ForwardIt1 last,
 903                             ForwardIt2 s_first, ForwardIt2 s_last,
 904                             BinaryPredicate p );
 905
 906   template <class InputIt, class ForwardIt>
 907   InputIt find_end(InputIt first, InputIt last,
 908                    ForwardIt s_first, ForwardIt s_last);
 909
 910   template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
 911   ForwardIt1 find_end (ExecutionPolicy&& policy,
 912                        ForwardIt1 first, ForwardIt1 last,
 913                        ForwardIt2 s_first, ForwardIt2 s_last);
 914
 915   template <class InputIt, class ForwardIt, class BinaryPredicate>
 916   InputIt find_end (InputIt first, InputIt last,
 917                     ForwardIt s_first, ForwardIt s_last,
 918                     BinaryPredicate p );
 919
 920   template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
 921             class BinaryPredicate>
 922   ForwardIt1 find_end (ExecutionPolicy&& policy,
 923                        ForwardIt1 first, ForwardIt1 last,
 924                        ForwardIt2 s_first, ForwardIt2 s_last,
 925                        BinaryPredicate p );
 926
 927   template <class ForwardIt, class T>
 928   ForwardIt lower_bound (ForwardIt first, ForwardIt last, const T& value);
 929
 930   template <class ForwardIt, class T, class Compare>
 931   ForwardIt lower_bound (ForwardIt first, ForwardIt last, const T& value,
 932                          Compare comp);
 933
 934   template <class ForwardIt, class T>
 935   ForwardIt upper_bound (ForwardIt first, ForwardIt last, const T& value);
 936
 937   template <class ForwardIt, class T, class Compare>
 938   ForwardIt upper_bound (ForwardIt first, ForwardIt last, const T& value,
 939                          Compare comp);
 940
 941   template <class ForwardIt1, class ForwardIt2>
 942   ForwardIt1 search (ForwardIt1 first, ForwardIt1 last,
 943                      ForwardIt2 s_first, ForwardIt2 s_last);
 944
 945   template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
 946   ForwardIt1 search (ExecutionPolicy&& policy,
 947                      ForwardIt1 first, ForwardIt1 last,
 948                      ForwardIt2 s_first, ForwardIt2 s_last);
 949
 950   template <class ForwardIt1, class ForwardIt2, class BinaryPredicate>
 951   ForwardIt1 search (ForwardIt1 first, ForwardIt1 last,
 952                      ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p);
 953
 954   template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
 955             class BinaryPredicate >
 956   ForwardIt1 search (ExecutionPolicy&& policy,
 957                      ForwardIt1 first, ForwardIt1 last,
 958                      ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p);
 959
 960   template <class ForwardIt, class Searcher>
 961   ForwardIt search (ForwardIt first, ForwardIt last, const Searcher& searcher);
 962
 963   template <class ForwardIt, class Size, class T>
 964   ForwardIt search_n (ForwardIt first, ForwardIt last, Size count,
 965                       const T& value);
 966
 967   template <class ExecutionPolicy, class ForwardIt, class Size, class T>
 968   ForwardIt search_n (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
 969                       Size count, const T& value);
 970
 971   template <class ForwardIt, class Size, class T, class BinaryPredicate>
 972   ForwardIt search_n (ForwardIt first, ForwardIt last, Size count,
 973                       const T& value, BinaryPredicate p);
 974
 975   template <class ExecutionPolicy, class ForwardIt, class Size, class T,
 976             class BinaryPredicate>
 977   ForwardIt search_n (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
 978                       Size count, const T& value, BinaryPredicate p);
 979
 980   template <class InputIterator, class OutputIterator>
 981   OutputIterator copy(InputIterator first, InputIterator last,
 982                       OutputIterator result);
 983
 984 }
 985
 986 #if __cplusplus >= 201103L
 987 namespace std {
 988 template <typename T> // TODO: Implement the stub for deleter.
 989 class unique_ptr {
 990 public:
 991   unique_ptr() noexcept {}
 992   unique_ptr(T *) noexcept {}
 993   unique_ptr(const unique_ptr &) noexcept = delete;
 994   unique_ptr(unique_ptr &&) noexcept;
 995
 996   T *get() const noexcept;
 997   T *release() noexcept;
 998   void reset(T *p = nullptr) noexcept;
 999   void swap(unique_ptr<T> &p) noexcept;
1000
1001   typename std::add_lvalue_reference<T>::type operator*() const;
1002   T *operator->() const noexcept;
1003   operator bool() const noexcept;
1004   unique_ptr<T> &operator=(unique_ptr<T> &&p) noexcept;
1005   unique_ptr<T> &operator=(nullptr_t) noexcept;
1006 };
1007
1008 // TODO :: Once the deleter parameter is added update with additional template parameter.
1009 template <typename T>
1010 void swap(unique_ptr<T> &x, unique_ptr<T> &y) noexcept {
1011   x.swap(y);
1012 }
1013
1014 template <typename T1, typename T2>
1015 bool operator==(const unique_ptr<T1> &x, const unique_ptr<T2> &y);
1016
1017 template <typename T1, typename T2>
1018 bool operator!=(const unique_ptr<T1> &x, const unique_ptr<T2> &y);
1019
1020 template <typename T1, typename T2>
1021 bool operator<(const unique_ptr<T1> &x, const unique_ptr<T2> &y);
1022
1023 template <typename T1, typename T2>
1024 bool operator>(const unique_ptr<T1> &x, const unique_ptr<T2> &y);
1025
1026 template <typename T1, typename T2>
1027 bool operator<=(const unique_ptr<T1> &x, const unique_ptr<T2> &y);
1028
1029 template <typename T1, typename T2>
1030 bool operator>=(const unique_ptr<T1> &x, const unique_ptr<T2> &y);
1031
1032 template <typename T>
1033 bool operator==(const unique_ptr<T> &x, nullptr_t y);
1034
1035 template <typename T>
1036 bool operator!=(const unique_ptr<T> &x, nullptr_t y);
1037
1038 template <typename T>
1039 bool operator<(const unique_ptr<T> &x, nullptr_t y);
1040
1041 template <typename T>
1042 bool operator>(const unique_ptr<T> &x, nullptr_t y);
1043
1044 template <typename T>
1045 bool operator<=(const unique_ptr<T> &x, nullptr_t y);
1046
1047 template <typename T>
1048 bool operator>=(const unique_ptr<T> &x, nullptr_t y);
1049
1050 template <typename T>
1051 bool operator==(nullptr_t x, const unique_ptr<T> &y);
1052
1053 template <typename T>
1054 bool operator!=(nullptr_t x, const unique_ptr<T> &y);
1055
1056 template <typename T>
1057 bool operator>(nullptr_t x, const unique_ptr<T> &y);
1058
1059 template <typename T>
1060 bool operator<(nullptr_t x, const unique_ptr<T> &y);
1061
1062 template <typename T>
1063 bool operator>=(nullptr_t x, const unique_ptr<T> &y);
1064
1065 template <typename T>
1066 bool operator<=(nullptr_t x, const unique_ptr<T> &y);
1067
1068 template <class T, class... Args>
1069 unique_ptr<T> make_unique(Args &&...args);
1070
1071 #if __cplusplus >= 202002L
1072
1073 template <class T>
1074 unique_ptr<T> make_unique_for_overwrite();
1075
1076 #endif
1077
1078 } // namespace std
1079 #endif
1080
1081 namespace std {
1082 template <class CharT>
1083 class basic_ostream;
1084
1085 using ostream = basic_ostream<char>;
1086
1087 extern std::ostream cout;
1088
1089 ostream &operator<<(ostream &, const string &);
1090
1091 #if __cplusplus >= 202002L
1092 template <class T>
1093 ostream &operator<<(ostream &, const std::unique_ptr<T> &);
1094 #endif
1095 } // namespace std
1096
1097 #ifdef TEST_INLINABLE_ALLOCATORS
1098 namespace std {
1099   void *malloc(size_t);
1100   void free(void *);
1101 }
1102 void* operator new(std::size_t size, const std::nothrow_t&) throw() { return std::malloc(size); }
1103 void* operator new[](std::size_t size, const std::nothrow_t&) throw() { return std::malloc(size); }
1104 void operator delete(void* ptr, const std::nothrow_t&) throw() { std::free(ptr); }
1105 void operator delete[](void* ptr, const std::nothrow_t&) throw() { std::free(ptr); }
1106 #else
1107 // C++20 standard draft 17.6.1, from "Header <new> synopsis", but with throw()
1108 // instead of noexcept:
1109
1110 void *operator new(std::size_t size);
1111 void *operator new(std::size_t size, std::align_val_t alignment);
1112 void *operator new(std::size_t size, const std::nothrow_t &) throw();
1113 void *operator new(std::size_t size, std::align_val_t alignment,
1114                    const std::nothrow_t &) throw();
1115 void operator delete(void *ptr) throw();
1116 void operator delete(void *ptr, std::size_t size) throw();
1117 void operator delete(void *ptr, std::align_val_t alignment) throw();
1118 void operator delete(void *ptr, std::size_t size, std::align_val_t alignment) throw();
1119 void operator delete(void *ptr, const std::nothrow_t &)throw();
1120 void operator delete(void *ptr, std::align_val_t alignment,
1121                      const std::nothrow_t &)throw();
1122 void *operator new[](std::size_t size);
1123 void *operator new[](std::size_t size, std::align_val_t alignment);
1124 void *operator new[](std::size_t size, const std::nothrow_t &) throw();
1125 void *operator new[](std::size_t size, std::align_val_t alignment,
1126                      const std::nothrow_t &) throw();
1127 void operator delete[](void *ptr) throw();
1128 void operator delete[](void *ptr, std::size_t size) throw();
1129 void operator delete[](void *ptr, std::align_val_t alignment) throw();
1130 void operator delete[](void *ptr, std::size_t size, std::align_val_t alignment) throw();
1131 void operator delete[](void *ptr, const std::nothrow_t &) throw();
1132 void operator delete[](void *ptr, std::align_val_t alignment,
1133                        const std::nothrow_t &) throw();
1134 #endif
1135
1136 void* operator new (std::size_t size, void* ptr) throw() { return ptr; };
1137 void* operator new[] (std::size_t size, void* ptr) throw() { return ptr; };
1138 void operator delete (void* ptr, void*) throw() {};
1139 void operator delete[] (void* ptr, void*) throw() {};
1140
1141 namespace __cxxabiv1 {
1142 extern "C" {
1143 extern char *__cxa_demangle(const char *mangled_name,
1144                             char *output_buffer,
1145                             size_t *length,
1146                             int *status);
1147 }}
1148 namespace abi = __cxxabiv1;
1149
1150 namespace std {
1151   template<class ForwardIt>
1152   bool is_sorted(ForwardIt first, ForwardIt last);
1153
1154   template <class RandomIt>
1155   void nth_element(RandomIt first, RandomIt nth, RandomIt last);
1156
1157   template<class RandomIt>
1158   void partial_sort(RandomIt first, RandomIt middle, RandomIt last);
1159
1160   template<class RandomIt>
1161   void sort (RandomIt first, RandomIt last);
1162
1163   template<class RandomIt>
1164   void stable_sort(RandomIt first, RandomIt last);
1165
1166   template<class BidirIt, class UnaryPredicate>
1167   BidirIt partition(BidirIt first, BidirIt last, UnaryPredicate p);
1168
1169   template<class BidirIt, class UnaryPredicate>
1170   BidirIt stable_partition(BidirIt first, BidirIt last, UnaryPredicate p);
1171 }
1172
1173 namespace std {
1174
1175 template< class T = void >
1176 struct less;
1177
1178 template< class T >
1179 struct allocator;
1180
1181 template< class Key >
1182 struct hash;
1183
1184 template<
1185   class Key,
1186   class Compare = std::less<Key>,
1187   class Alloc = std::allocator<Key>
1188 > class set {
1189   public:
1190     set(initializer_list<Key> __list) {}
1191
1192     class iterator {
1193     public:
1194       iterator(Key *key): ptr(key) {}
1195       iterator& operator++() { ++ptr; return *this; }
1196       bool operator!=(const iterator &other) const { return ptr != other.ptr; }
1197       const Key &operator*() const { return *ptr; }
1198     private:
1199       Key *ptr;
1200     };
1201
1202   public:
1203     Key *val;
1204     iterator begin() const { return iterator(val); }
1205     iterator end() const { return iterator(val + 1); }
1206 };
1207
1208 template<
1209   class Key,
1210   class Hash = std::hash<Key>,
1211   class Compare = std::less<Key>,
1212   class Alloc = std::allocator<Key>
1213 > class unordered_set {
1214   public:
1215     unordered_set(initializer_list<Key> __list) {}
1216
1217     class iterator {
1218     public:
1219       iterator(Key *key): ptr(key) {}
1220       iterator& operator++() { ++ptr; return *this; }
1221       bool operator!=(const iterator &other) const { return ptr != other.ptr; }
1222       const Key &operator*() const { return *ptr; }
1223     private:
1224       Key *ptr;
1225     };
1226
1227   public:
1228     Key *val;
1229     iterator begin() const { return iterator(val); }
1230     iterator end() const { return iterator(val + 1); }
1231 };
1232
1233 namespace execution {
1234 class sequenced_policy {};
1235 }
1236
1237 template <class T = void> struct equal_to {};
1238
1239 template <class ForwardIt, class BinaryPredicate = std::equal_to<> >
1240 class default_searcher {
1241 public:
1242   default_searcher (ForwardIt pat_first,
1243                     ForwardIt pat_last,
1244                     BinaryPredicate pred = BinaryPredicate());
1245   template <class ForwardIt2>
1246   std::pair <ForwardIt2, ForwardIt2>
1247   operator()( ForwardIt2 first, ForwardIt2 last ) const;
1248 };
1249
1250 template <typename> class packaged_task;
1251 template <typename Ret, typename... Args> class packaged_task<Ret(Args...)> {
1252   // TODO: Add some actual implementation.
1253 };
1254
1255 } // namespace std