1402 lines · c
1// Like the compiler, the static analyzer treats some functions differently if2// they come from a system header -- for example, it is assumed that system3// functions do not arbitrarily free() their parameters, and that some bugs4// found in system headers cannot be fixed by the user and should be5// suppressed.6#pragma clang system_header7 8typedef unsigned char uint8_t;9 10typedef __typeof__(sizeof(int)) size_t;11typedef __typeof__((char*)0-(char*)0) ptrdiff_t;12void *memmove(void *s1, const void *s2, size_t n);13 14namespace std {15 typedef size_t size_type;16#if __cplusplus >= 201103L17 using nullptr_t = decltype(nullptr);18#endif19}20 21namespace 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 37template <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 96private:97 Ptr ptr;98};99 100template <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 156private:157 Ptr ptr;158};159 160template <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 199private:200 T* item;201};202 203template <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 235private:236 T* item;237};238 239namespace 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 template<class T2, class T1>254 T2& get(pair<T1, T2>& p) ;255 template<class T1, class T2>256 T1& get(const pair<T1, T2>& p) ;257 258 typedef __typeof__(sizeof(int)) size_t;259 260 template <class T> class initializer_list;261 262 template< class T > struct remove_reference {typedef T type;};263 template< class T > struct remove_reference<T&> {typedef T type;};264 template< class T > struct remove_reference<T&&> {typedef T type;};265 266 template<typename T> typename remove_reference<T>::type&& move(T&& a);267 template <typename T> T *__addressof(T &x);268 template <typename T> T *addressof(T &x);269 template <typename T> const T& as_const(T& x);270 template <typename T> T&& forward(T&& x);271 // FIXME: Declare forward_like272 // FIXME: Declare move_if_noexcept273 274 template< class T >275 using remove_reference_t = typename remove_reference<T>::type;276 277 template <class T>278 void swap(T &a, T &b) {279 T c(std::move(a));280 a = std::move(b);281 b = std::move(c);282 }283 284 template<typename T>285 class vector {286 T *_start;287 T *_finish;288 T *_end_of_storage;289 290 public:291 typedef T value_type;292 typedef size_t size_type;293 typedef __vector_iterator<T, T *, T &> iterator;294 typedef __vector_iterator<T, const T *, const T &> const_iterator;295 296 vector() : _start(0), _finish(0), _end_of_storage(0) {}297 template <typename InputIterator>298 vector(InputIterator first, InputIterator last);299 vector(const vector &other);300 vector(vector &&other);301 ~vector();302 303 size_t size() const {304 return size_t(_finish - _start);305 }306 307 vector& operator=(const vector &other);308 vector& operator=(vector &&other);309 vector& operator=(std::initializer_list<T> ilist);310 311 void assign(size_type count, const T &value);312 template <typename InputIterator >313 void assign(InputIterator first, InputIterator last);314 void assign(std::initializer_list<T> ilist);315 316 void clear();317 318 void push_back(const T &value);319 void push_back(T &&value);320 template<class... Args>321 void emplace_back(Args&&... args);322 void pop_back();323 324 iterator insert(const_iterator position, const value_type &val);325 iterator insert(const_iterator position, size_type n,326 const value_type &val);327 template <typename InputIterator>328 iterator insert(const_iterator position, InputIterator first,329 InputIterator last);330 iterator insert(const_iterator position, value_type &&val);331 iterator insert(const_iterator position, initializer_list<value_type> il);332 333 template <class... Args>334 iterator emplace(const_iterator position, Args&&... args);335 336 iterator erase(const_iterator position);337 iterator erase(const_iterator first, const_iterator last);338 339 T &operator[](size_t n) {340 return _start[n];341 }342 343 const T &operator[](size_t n) const {344 return _start[n];345 }346 347 iterator begin() { return iterator(_start); }348 const_iterator begin() const { return const_iterator(_start); }349 const_iterator cbegin() const { return const_iterator(_start); }350 iterator end() { return iterator(_finish); }351 const_iterator end() const { return const_iterator(_finish); }352 const_iterator cend() const { return const_iterator(_finish); }353 T& front() { return *begin(); }354 const T& front() const { return *begin(); }355 T& back() { return *(end() - 1); }356 const T& back() const { return *(end() - 1); }357 };358 359 template<typename T>360 class list {361 struct __item {362 T data;363 __item *prev, *next;364 } *_start, *_finish;365 366 public:367 typedef T value_type;368 typedef size_t size_type;369 typedef __list_iterator<__item, T *, T &> iterator;370 typedef __list_iterator<__item, const T *, const T &> const_iterator;371 372 list() : _start(0), _finish(0) {}373 template <typename InputIterator>374 list(InputIterator first, InputIterator last);375 list(const list &other);376 list(list &&other);377 ~list();378 379 list& operator=(const list &other);380 list& operator=(list &&other);381 list& operator=(std::initializer_list<T> ilist);382 383 void assign(size_type count, const T &value);384 template <typename InputIterator >385 void assign(InputIterator first, InputIterator last);386 void assign(std::initializer_list<T> ilist);387 388 void clear();389 390 void push_back(const T &value);391 void push_back(T &&value);392 template<class... Args>393 void emplace_back(Args&&... args);394 void pop_back();395 396 void push_front(const T &value);397 void push_front(T &&value);398 template<class... Args>399 void emplace_front(Args&&... args);400 void pop_front();401 402 iterator insert(const_iterator position, const value_type &val);403 iterator insert(const_iterator position, size_type n,404 const value_type &val);405 template <typename InputIterator>406 iterator insert(const_iterator position, InputIterator first,407 InputIterator last);408 iterator insert(const_iterator position, value_type &&val);409 iterator insert(const_iterator position, initializer_list<value_type> il);410 411 template <class... Args>412 iterator emplace(const_iterator position, Args&&... args);413 414 iterator erase(const_iterator position);415 iterator erase(const_iterator first, const_iterator last);416 417 iterator begin() { return iterator(_start); }418 const_iterator begin() const { return const_iterator(_start); }419 const_iterator cbegin() const { return const_iterator(_start); }420 iterator end() { return iterator(_finish); }421 const_iterator end() const { return const_iterator(_finish); }422 const_iterator cend() const { return const_iterator(_finish); }423 424 T& front() { return *begin(); }425 const T& front() const { return *begin(); }426 T& back() { return *--end(); }427 const T& back() const { return *--end(); }428 };429 430 template<typename T>431 class deque {432 T *_start;433 T *_finish;434 T *_end_of_storage;435 436 public:437 typedef T value_type;438 typedef size_t size_type;439 typedef __deque_iterator<T, T *, T &> iterator;440 typedef __deque_iterator<T, const T *, const T &> const_iterator;441 442 deque() : _start(0), _finish(0), _end_of_storage(0) {}443 template <typename InputIterator>444 deque(InputIterator first, InputIterator last);445 deque(const deque &other);446 deque(deque &&other);447 ~deque();448 449 size_t size() const {450 return size_t(_finish - _start);451 }452 453 deque& operator=(const deque &other);454 deque& operator=(deque &&other);455 deque& operator=(std::initializer_list<T> ilist);456 457 void assign(size_type count, const T &value);458 template <typename InputIterator >459 void assign(InputIterator first, InputIterator last);460 void assign(std::initializer_list<T> ilist);461 462 void clear();463 464 void push_back(const T &value);465 void push_back(T &&value);466 template<class... Args>467 void emplace_back(Args&&... args);468 void pop_back();469 470 void push_front(const T &value);471 void push_front(T &&value);472 template<class... Args>473 void emplace_front(Args&&... args);474 void pop_front();475 476 iterator insert(const_iterator position, const value_type &val);477 iterator insert(const_iterator position, size_type n,478 const value_type &val);479 template <typename InputIterator>480 iterator insert(const_iterator position, InputIterator first,481 InputIterator last);482 iterator insert(const_iterator position, value_type &&val);483 iterator insert(const_iterator position, initializer_list<value_type> il);484 485 template <class... Args>486 iterator emplace(const_iterator position, Args&&... args);487 488 iterator erase(const_iterator position);489 iterator erase(const_iterator first, const_iterator last);490 491 T &operator[](size_t n) {492 return _start[n];493 }494 495 const T &operator[](size_t n) const {496 return _start[n];497 }498 499 iterator begin() { return iterator(_start); }500 const_iterator begin() const { return const_iterator(_start); }501 const_iterator cbegin() const { return const_iterator(_start); }502 iterator end() { return iterator(_finish); }503 const_iterator end() const { return const_iterator(_finish); }504 const_iterator cend() const { return const_iterator(_finish); }505 T& front() { return *begin(); }506 const T& front() const { return *begin(); }507 T& back() { return *(end() - 1); }508 const T& back() const { return *(end() - 1); }509 };510 511 template<typename T>512 class forward_list {513 struct __item {514 T data;515 __item *next;516 } *_start;517 518 public:519 typedef T value_type;520 typedef size_t size_type;521 typedef __fwdl_iterator<__item, T *, T &> iterator;522 typedef __fwdl_iterator<__item, const T *, const T &> const_iterator;523 524 forward_list() : _start(0) {}525 template <typename InputIterator>526 forward_list(InputIterator first, InputIterator last);527 forward_list(const forward_list &other);528 forward_list(forward_list &&other);529 ~forward_list();530 531 forward_list& operator=(const forward_list &other);532 forward_list& operator=(forward_list &&other);533 forward_list& operator=(std::initializer_list<T> ilist);534 535 void assign(size_type count, const T &value);536 template <typename InputIterator >537 void assign(InputIterator first, InputIterator last);538 void assign(std::initializer_list<T> ilist);539 540 void clear();541 542 void push_front(const T &value);543 void push_front(T &&value);544 template<class... Args>545 void emplace_front(Args&&... args);546 void pop_front();547 548 iterator insert_after(const_iterator position, const value_type &val);549 iterator insert_after(const_iterator position, value_type &&val);550 iterator insert_after(const_iterator position, size_type n,551 const value_type &val);552 template <typename InputIterator>553 iterator insert_after(const_iterator position, InputIterator first,554 InputIterator last);555 iterator insert_after(const_iterator position,556 initializer_list<value_type> il);557 558 template <class... Args>559 iterator emplace_after(const_iterator position, Args&&... args);560 561 iterator erase_after(const_iterator position);562 iterator erase_after(const_iterator first, const_iterator last);563 564 iterator begin() { return iterator(_start); }565 const_iterator begin() const { return const_iterator(_start); }566 const_iterator cbegin() const { return const_iterator(_start); }567 iterator end() { return iterator(); }568 const_iterator end() const { return const_iterator(); }569 const_iterator cend() const { return const_iterator(); }570 571 T& front() { return *begin(); }572 const T& front() const { return *begin(); }573 };574 575 template <typename CharT>576 class basic_string {577 class Allocator {};578 579 public:580 basic_string() : basic_string(Allocator()) {}581 explicit basic_string(const Allocator &alloc);582 basic_string(size_type count, CharT ch,583 const Allocator &alloc = Allocator());584 basic_string(const basic_string &other,585 size_type pos,586 const Allocator &alloc = Allocator());587 basic_string(const basic_string &other,588 size_type pos, size_type count,589 const Allocator &alloc = Allocator());590 basic_string(const CharT *s, size_type count,591 const Allocator &alloc = Allocator());592 basic_string(const CharT *s,593 const Allocator &alloc = Allocator());594 template <class InputIt>595 basic_string(InputIt first, InputIt last,596 const Allocator &alloc = Allocator());597 basic_string(const basic_string &other);598 basic_string(const basic_string &other,599 const Allocator &alloc);600 basic_string(basic_string &&other);601 basic_string(basic_string &&other,602 const Allocator &alloc);603 basic_string(std::initializer_list<CharT> ilist,604 const Allocator &alloc = Allocator());605 template <class T>606 basic_string(const T &t, size_type pos, size_type n,607 const Allocator &alloc = Allocator());608 // basic_string(std::nullptr_t) = delete;609 610 ~basic_string();611 void clear();612 613 basic_string &operator=(const basic_string &str);614 basic_string &operator+=(const basic_string &str);615 616 const CharT *c_str() const;617 const CharT *data() const;618 CharT *data();619 620 const char *begin() const;621 const char *end() const;622 623 basic_string &append(size_type count, CharT ch);624 basic_string &assign(size_type count, CharT ch);625 basic_string &erase(size_type index, size_type count);626 basic_string &insert(size_type index, size_type count, CharT ch);627 basic_string &replace(size_type pos, size_type count, const basic_string &str);628 void pop_back();629 void push_back(CharT ch);630 void reserve(size_type new_cap);631 void resize(size_type count);632 void shrink_to_fit();633 void swap(basic_string &other);634 };635 636 typedef basic_string<char> string;637 typedef basic_string<wchar_t> wstring;638#if __cplusplus >= 201103L639 typedef basic_string<char16_t> u16string;640 typedef basic_string<char32_t> u32string;641#endif642 643 class exception {644 public:645 exception() throw();646 virtual ~exception() throw();647 virtual const char *what() const throw() {648 return 0;649 }650 };651 652 class bad_alloc : public exception {653 public:654 bad_alloc() throw();655 bad_alloc(const bad_alloc&) throw();656 bad_alloc& operator=(const bad_alloc&) throw();657 virtual const char* what() const throw() {658 return 0;659 }660 };661 662 struct nothrow_t {};663 extern const nothrow_t nothrow;664 665 enum class align_val_t : size_t {};666 667 // libc++'s implementation668 template <class _E>669 class initializer_list670 {671 const _E* __begin_;672 size_t __size_;673 674 initializer_list(const _E* __b, size_t __s)675 : __begin_(__b),676 __size_(__s)677 {}678 679 public:680 typedef _E value_type;681 typedef const _E& reference;682 typedef const _E& const_reference;683 typedef size_t size_type;684 685 typedef const _E* iterator;686 typedef const _E* const_iterator;687 688 initializer_list() : __begin_(0), __size_(0) {}689 690 size_t size() const {return __size_;}691 const _E* begin() const {return __begin_;}692 const _E* end() const {return __begin_ + __size_;}693 };694 695 template <bool, class _Tp = void> struct enable_if {};696 template <class _Tp> struct enable_if<true, _Tp> {typedef _Tp type;};697 698 template <class _Tp, _Tp __v>699 struct integral_constant700 {701 static const _Tp value = __v;702 typedef _Tp value_type;703 typedef integral_constant type;704 705 operator value_type() const {return value;}706 707 value_type operator ()() const {return value;}708 };709 710 template <class _Tp, _Tp __v>711 const _Tp integral_constant<_Tp, __v>::value;712 713 template <class _Tp, class _Arg>714 struct is_trivially_assignable715 : integral_constant<bool, __is_trivially_assignable(_Tp, _Arg)>716 {717 };718 719 typedef integral_constant<bool,true> true_type;720 typedef integral_constant<bool,false> false_type;721 722 template <class _Tp> struct is_const : public false_type {};723 template <class _Tp> struct is_const<_Tp const> : public true_type {};724 725 template <class _Tp> struct is_reference : public false_type {};726 template <class _Tp> struct is_reference<_Tp&> : public true_type {};727 728 template <class _Tp, class _Up> struct is_same : public false_type {};729 template <class _Tp> struct is_same<_Tp, _Tp> : public true_type {};730 731 #if __cplusplus >= 201703L732 template< class T, class U >733 inline constexpr bool is_same_v = is_same<T, U>::value;734 #endif735 736 template <class _Tp, bool = is_const<_Tp>::value || is_reference<_Tp>::value >737 struct __add_const {typedef _Tp type;};738 739 template <class _Tp>740 struct __add_const<_Tp, false> {typedef const _Tp type;};741 742 template <class _Tp> struct add_const {typedef typename __add_const<_Tp>::type type;};743 744 template <class _Tp> struct remove_const {typedef _Tp type;};745 template <class _Tp> struct remove_const<const _Tp> {typedef _Tp type;};746 747 template< class T >748 using remove_const_t = typename remove_const<T>::type;749 750 template <class _Tp> struct add_lvalue_reference {typedef _Tp& type;};751 752 template <class _Tp> struct is_trivially_copy_assignable753 : public is_trivially_assignable<typename add_lvalue_reference<_Tp>::type,754 typename add_lvalue_reference<typename add_const<_Tp>::type>::type> {};755 756 template<class InputIter, class OutputIter>757 OutputIter __copy(InputIter II, InputIter IE, OutputIter OI) {758 while (II != IE)759 *OI++ = *II++; // #system_header_simulator_cxx_std_copy_impl_loop760 761 return OI;762 }763 764 template <class _Tp, class _Up>765 inline766 typename enable_if767 <768 is_same<typename remove_const<_Tp>::type, _Up>::value &&769 is_trivially_copy_assignable<_Up>::value,770 _Up*771 >::type __copy(_Tp* __first, _Tp* __last, _Up* __result) {772 size_t __n = __last - __first;773 774 if (__n > 0)775 memmove(__result, __first, __n * sizeof(_Up));776 777 return __result + __n;778 }779 780 template<class InputIter, class OutputIter>781 OutputIter copy(InputIter II, InputIter IE, OutputIter OI) {782 return __copy(II, IE, OI);783 }784 785 template <class _BidirectionalIterator, class _OutputIterator>786 inline787 _OutputIterator788 __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last,789 _OutputIterator __result)790 {791 while (__first != __last)792 *--__result = *--__last;793 return __result;794 }795 796 template <class _Tp, class _Up>797 inline798 typename enable_if799 <800 is_same<typename remove_const<_Tp>::type, _Up>::value &&801 is_trivially_copy_assignable<_Up>::value,802 _Up*803 >::type __copy_backward(_Tp* __first, _Tp* __last, _Up* __result) {804 size_t __n = __last - __first;805 806 if (__n > 0)807 {808 __result -= __n;809 memmove(__result, __first, __n * sizeof(_Up));810 }811 return __result;812 }813 814 template< bool B, class T = void >815 using enable_if_t = typename enable_if<B,T>::type;816 817 template<class InputIter, class OutputIter>818 OutputIter copy_backward(InputIter II, InputIter IE, OutputIter OI) {819 return __copy_backward(II, IE, OI);820 }821}822 823template <class BidirectionalIterator, class Distance>824void __advance(BidirectionalIterator& it, Distance n,825 std::bidirectional_iterator_tag)826#if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 2827{828 if (n >= 0) while(n-- > 0) ++it; else while (n++<0) --it;829}830#else831 ;832#endif833 834template <class RandomAccessIterator, class Distance>835void __advance(RandomAccessIterator& it, Distance n,836 std::random_access_iterator_tag)837#if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 2838{839 it += n;840}841#else842 ;843#endif844 845namespace std {846 847template <class InputIterator, class Distance>848void advance(InputIterator& it, Distance n)849#if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 1850{851 __advance(it, n, typename InputIterator::iterator_category());852}853#else854 ;855#endif856 857template <class BidirectionalIterator>858BidirectionalIterator859prev(BidirectionalIterator it,860 typename iterator_traits<BidirectionalIterator>::difference_type n =861 1)862#if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 0863{864 advance(it, -n);865 return it;866}867#else868 ;869#endif870 871template <class ForwardIterator>872ForwardIterator873next(ForwardIterator it,874 typename iterator_traits<ForwardIterator>::difference_type n =875 1)876#if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 0877{878 advance(it, n);879 return it;880}881#else882 ;883#endif884 885 template <class InputIt, class T>886 InputIt find(InputIt first, InputIt last, const T& value);887 888 template <class ExecutionPolicy, class ForwardIt, class T>889 ForwardIt find(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,890 const T& value);891 892 template <class InputIt, class UnaryPredicate>893 InputIt find_if (InputIt first, InputIt last, UnaryPredicate p);894 895 template <class ExecutionPolicy, class ForwardIt, class UnaryPredicate>896 ForwardIt find_if (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,897 UnaryPredicate p);898 899 template <class InputIt, class UnaryPredicate>900 InputIt find_if_not (InputIt first, InputIt last, UnaryPredicate q);901 902 template <class ExecutionPolicy, class ForwardIt, class UnaryPredicate>903 ForwardIt find_if_not (ExecutionPolicy&& policy, ForwardIt first,904 ForwardIt last, UnaryPredicate q);905 906 template <class InputIt, class ForwardIt>907 InputIt find_first_of(InputIt first, InputIt last,908 ForwardIt s_first, ForwardIt s_last);909 910 template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>911 ForwardIt1 find_first_of (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_first_of (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_first_of (ExecutionPolicy&& policy,923 ForwardIt1 first, ForwardIt1 last,924 ForwardIt2 s_first, ForwardIt2 s_last,925 BinaryPredicate p );926 927 template <class InputIt, class ForwardIt>928 InputIt find_end(InputIt first, InputIt last,929 ForwardIt s_first, ForwardIt s_last);930 931 template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>932 ForwardIt1 find_end (ExecutionPolicy&& policy,933 ForwardIt1 first, ForwardIt1 last,934 ForwardIt2 s_first, ForwardIt2 s_last);935 936 template <class InputIt, class ForwardIt, class BinaryPredicate>937 InputIt find_end (InputIt first, InputIt last,938 ForwardIt s_first, ForwardIt s_last,939 BinaryPredicate p );940 941 template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2,942 class BinaryPredicate>943 ForwardIt1 find_end (ExecutionPolicy&& policy,944 ForwardIt1 first, ForwardIt1 last,945 ForwardIt2 s_first, ForwardIt2 s_last,946 BinaryPredicate p );947 948 template <class ForwardIt, class T>949 ForwardIt lower_bound (ForwardIt first, ForwardIt last, const T& value);950 951 template <class ForwardIt, class T, class Compare>952 ForwardIt lower_bound (ForwardIt first, ForwardIt last, const T& value,953 Compare comp);954 955 template <class ForwardIt, class T>956 ForwardIt upper_bound (ForwardIt first, ForwardIt last, const T& value);957 958 template <class ForwardIt, class T, class Compare>959 ForwardIt upper_bound (ForwardIt first, ForwardIt last, const T& value,960 Compare comp);961 962 template <class ForwardIt1, class ForwardIt2>963 ForwardIt1 search (ForwardIt1 first, ForwardIt1 last,964 ForwardIt2 s_first, ForwardIt2 s_last);965 966 template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>967 ForwardIt1 search (ExecutionPolicy&& policy,968 ForwardIt1 first, ForwardIt1 last,969 ForwardIt2 s_first, ForwardIt2 s_last);970 971 template <class ForwardIt1, class ForwardIt2, class BinaryPredicate>972 ForwardIt1 search (ForwardIt1 first, ForwardIt1 last,973 ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p);974 975 template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2,976 class BinaryPredicate >977 ForwardIt1 search (ExecutionPolicy&& policy,978 ForwardIt1 first, ForwardIt1 last,979 ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p);980 981 template <class ForwardIt, class Searcher>982 ForwardIt search (ForwardIt first, ForwardIt last, const Searcher& searcher);983 984 template <class ForwardIt, class Size, class T>985 ForwardIt search_n (ForwardIt first, ForwardIt last, Size count,986 const T& value);987 988 template <class ExecutionPolicy, class ForwardIt, class Size, class T>989 ForwardIt search_n (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,990 Size count, const T& value);991 992 template <class ForwardIt, class Size, class T, class BinaryPredicate>993 ForwardIt search_n (ForwardIt first, ForwardIt last, Size count,994 const T& value, BinaryPredicate p);995 996 template <class ExecutionPolicy, class ForwardIt, class Size, class T,997 class BinaryPredicate>998 ForwardIt search_n (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,999 Size count, const T& value, BinaryPredicate p);1000 1001 template <class InputIterator, class OutputIterator>1002 OutputIterator copy(InputIterator first, InputIterator last,1003 OutputIterator result);1004 1005}1006 1007#if __cplusplus >= 201103L1008namespace std {1009template <typename T> // TODO: Implement the stub for deleter.1010class unique_ptr {1011public:1012 unique_ptr() noexcept {}1013 unique_ptr(T *) noexcept {}1014 unique_ptr(const unique_ptr &) noexcept = delete;1015 unique_ptr(unique_ptr &&) noexcept;1016 1017 T *get() const noexcept;1018 T *release() noexcept;1019 void reset(T *p = nullptr) noexcept;1020 void swap(unique_ptr<T> &p) noexcept;1021 1022 typename std::add_lvalue_reference<T>::type operator*() const;1023 T *operator->() const noexcept;1024 operator bool() const noexcept;1025 unique_ptr<T> &operator=(unique_ptr<T> &&p) noexcept;1026 unique_ptr<T> &operator=(nullptr_t) noexcept;1027};1028 1029// TODO :: Once the deleter parameter is added update with additional template parameter.1030template <typename T>1031void swap(unique_ptr<T> &x, unique_ptr<T> &y) noexcept {1032 x.swap(y);1033}1034 1035template <typename T1, typename T2>1036bool operator==(const unique_ptr<T1> &x, const unique_ptr<T2> &y);1037 1038template <typename T1, typename T2>1039bool operator!=(const unique_ptr<T1> &x, const unique_ptr<T2> &y);1040 1041template <typename T1, typename T2>1042bool operator<(const unique_ptr<T1> &x, const unique_ptr<T2> &y);1043 1044template <typename T1, typename T2>1045bool operator>(const unique_ptr<T1> &x, const unique_ptr<T2> &y);1046 1047template <typename T1, typename T2>1048bool operator<=(const unique_ptr<T1> &x, const unique_ptr<T2> &y);1049 1050template <typename T1, typename T2>1051bool operator>=(const unique_ptr<T1> &x, const unique_ptr<T2> &y);1052 1053template <typename T>1054bool operator==(const unique_ptr<T> &x, nullptr_t y);1055 1056template <typename T>1057bool operator!=(const unique_ptr<T> &x, nullptr_t y);1058 1059template <typename T>1060bool operator<(const unique_ptr<T> &x, nullptr_t y);1061 1062template <typename T>1063bool operator>(const unique_ptr<T> &x, nullptr_t y);1064 1065template <typename T>1066bool operator<=(const unique_ptr<T> &x, nullptr_t y);1067 1068template <typename T>1069bool operator>=(const unique_ptr<T> &x, nullptr_t y);1070 1071template <typename T>1072bool operator==(nullptr_t x, const unique_ptr<T> &y);1073 1074template <typename T>1075bool operator!=(nullptr_t x, const unique_ptr<T> &y);1076 1077template <typename T>1078bool operator>(nullptr_t x, const unique_ptr<T> &y);1079 1080template <typename T>1081bool operator<(nullptr_t x, const unique_ptr<T> &y);1082 1083template <typename T>1084bool operator>=(nullptr_t x, const unique_ptr<T> &y);1085 1086template <typename T>1087bool operator<=(nullptr_t x, const unique_ptr<T> &y);1088 1089template <class T, class... Args>1090unique_ptr<T> make_unique(Args &&...args);1091 1092#if __cplusplus >= 202002L1093 1094template <class T>1095unique_ptr<T> make_unique_for_overwrite();1096 1097#endif1098 1099} // namespace std1100#endif1101 1102namespace std {1103template <class CharT>1104class basic_ostream;1105 1106using ostream = basic_ostream<char>;1107 1108extern std::ostream cout;1109 1110ostream &operator<<(ostream &, const string &);1111 1112#if __cplusplus >= 202002L1113template <class T>1114ostream &operator<<(ostream &, const std::unique_ptr<T> &);1115#endif1116 1117template <class CharT>1118class basic_istream;1119 1120using istream = basic_istream<char>;1121 1122extern std::istream cin;1123 1124istream &getline(istream &, string &, char);1125istream &getline(istream &, string &);1126} // namespace std1127 1128namespace std {1129 void *malloc(size_t);1130 void free(void *);1131} // namespace std1132 1133#ifdef TEST_INLINABLE_ALLOCATORS1134void* operator new(std::size_t size, const std::nothrow_t&) throw() { return std::malloc(size); }1135void* operator new[](std::size_t size, const std::nothrow_t&) throw() { return std::malloc(size); }1136void operator delete(void* ptr, const std::nothrow_t&) throw() { std::free(ptr); }1137void operator delete[](void* ptr, const std::nothrow_t&) throw() { std::free(ptr); }1138#else1139// C++20 standard draft 17.6.1, from "Header <new> synopsis", but with throw()1140// instead of noexcept:1141 1142void *operator new(std::size_t size);1143void *operator new(std::size_t size, std::align_val_t alignment);1144void *operator new(std::size_t size, const std::nothrow_t &) throw();1145void *operator new(std::size_t size, std::align_val_t alignment,1146 const std::nothrow_t &) throw();1147void operator delete(void *ptr) throw();1148void operator delete(void *ptr, std::size_t size) throw();1149void operator delete(void *ptr, std::align_val_t alignment) throw();1150void operator delete(void *ptr, std::size_t size, std::align_val_t alignment) throw();1151void operator delete(void *ptr, const std::nothrow_t &)throw();1152void operator delete(void *ptr, std::align_val_t alignment,1153 const std::nothrow_t &)throw();1154void *operator new[](std::size_t size);1155void *operator new[](std::size_t size, std::align_val_t alignment);1156void *operator new[](std::size_t size, const std::nothrow_t &) throw();1157void *operator new[](std::size_t size, std::align_val_t alignment,1158 const std::nothrow_t &) throw();1159void operator delete[](void *ptr) throw();1160void operator delete[](void *ptr, std::size_t size) throw();1161void operator delete[](void *ptr, std::align_val_t alignment) throw();1162void operator delete[](void *ptr, std::size_t size, std::align_val_t alignment) throw();1163void operator delete[](void *ptr, const std::nothrow_t &) throw();1164void operator delete[](void *ptr, std::align_val_t alignment,1165 const std::nothrow_t &) throw();1166#endif1167 1168void* operator new (std::size_t size, void* ptr) throw() { return ptr; };1169void* operator new[] (std::size_t size, void* ptr) throw() { return ptr; };1170void operator delete (void* ptr, void*) throw() {};1171void operator delete[] (void* ptr, void*) throw() {};1172 1173namespace __cxxabiv1 {1174extern "C" {1175extern char *__cxa_demangle(const char *mangled_name,1176 char *output_buffer,1177 size_t *length,1178 int *status);1179}}1180namespace abi = __cxxabiv1;1181 1182namespace std {1183 template<class ForwardIt>1184 bool is_sorted(ForwardIt first, ForwardIt last);1185 1186 template <class RandomIt>1187 void nth_element(RandomIt first, RandomIt nth, RandomIt last);1188 1189 template<class RandomIt>1190 void partial_sort(RandomIt first, RandomIt middle, RandomIt last);1191 1192 template<class RandomIt>1193 void sort (RandomIt first, RandomIt last);1194 1195 template<class RandomIt>1196 void stable_sort(RandomIt first, RandomIt last);1197 1198 template<class BidirIt, class UnaryPredicate>1199 BidirIt partition(BidirIt first, BidirIt last, UnaryPredicate p);1200 1201 template<class BidirIt, class UnaryPredicate>1202 BidirIt stable_partition(BidirIt first, BidirIt last, UnaryPredicate p);1203}1204 1205namespace std {1206 1207template< class T = void >1208struct less;1209 1210template< class T >1211struct allocator;1212 1213template< class Key >1214struct hash;1215 1216template<1217 class Key,1218 class Compare = std::less<Key>,1219 class Alloc = std::allocator<Key>1220> class set {1221 public:1222 set(initializer_list<Key> __list) {}1223 1224 class iterator {1225 public:1226 iterator(Key *key): ptr(key) {}1227 iterator& operator++() { ++ptr; return *this; }1228 bool operator!=(const iterator &other) const { return ptr != other.ptr; }1229 const Key &operator*() const { return *ptr; }1230 private:1231 Key *ptr;1232 };1233 1234 public:1235 Key *val;1236 iterator begin() const { return iterator(val); }1237 iterator end() const { return iterator(val + 1); }1238};1239 1240template<1241 class Key,1242 class Hash = std::hash<Key>,1243 class Compare = std::less<Key>,1244 class Alloc = std::allocator<Key>1245> class unordered_set {1246 public:1247 unordered_set() {}1248 unordered_set(initializer_list<Key> __list) {}1249 1250 class iterator {1251 public:1252 iterator(Key *key): ptr(key) {}1253 iterator& operator++() { ++ptr; return *this; }1254 bool operator!=(const iterator &other) const { return ptr != other.ptr; }1255 const Key &operator*() const { return *ptr; }1256 private:1257 Key *ptr;1258 };1259 1260 public:1261 Key *val;1262 iterator begin() const { return iterator(val); }1263 iterator end() const { return iterator(val + 1); }1264 1265 template< class InputIt >1266 void insert( InputIt first, InputIt last );1267};1268 1269template <typename T>1270class atomic {1271public:1272 T operator++();1273 T operator--();1274};1275 1276namespace execution {1277class sequenced_policy {};1278}1279 1280template <class T = void> struct equal_to {};1281 1282template <class ForwardIt, class BinaryPredicate = std::equal_to<> >1283class default_searcher {1284public:1285 default_searcher (ForwardIt pat_first,1286 ForwardIt pat_last,1287 BinaryPredicate pred = BinaryPredicate());1288 template <class ForwardIt2>1289 std::pair <ForwardIt2, ForwardIt2>1290 operator()( ForwardIt2 first, ForwardIt2 last ) const;1291};1292 1293template <typename> class packaged_task;1294template <typename Ret, typename... Args> class packaged_task<Ret(Args...)> {1295 // TODO: Add some actual implementation.1296};1297 1298 #if __cplusplus >= 201703L1299 1300 namespace detail1301 {1302 template<class T>1303 struct type_identity { using type = T; }; // or use std::type_identity (since C++20)1304 1305 template<class T>1306 auto try_add_pointer(int) -> type_identity<typename std::remove_reference<T>::type*>;1307 template<class T>1308 auto try_add_pointer(...) -> type_identity<T>;1309 } // namespace detail1310 1311 template<class T>1312 struct add_pointer : decltype(detail::try_add_pointer<T>(0)) {};1313 1314 template< class T >1315 using add_pointer_t = typename add_pointer<T>::type;1316 1317 template<class T> struct remove_cv { typedef T type; };1318 template<class T> struct remove_cv<const T> { typedef T type; };1319 template<class T> struct remove_cv<volatile T> { typedef T type; };1320 template<class T> struct remove_cv<const volatile T> { typedef T type; };1321 1322 template< class T >1323 using remove_cv_t = typename remove_cv<T>::type;1324 1325 // This decay does not behave exactly like std::decay, but this is enough1326 // for testing the std::variant checker1327 template<class T>1328 struct decay{typedef remove_cv_t<remove_reference_t<T>> type;};1329 template<class T>1330 using decay_t = typename decay<T>::type;1331 1332 // variant1333 template <class... Types> class variant;1334 // variant helper classes1335 template <class T> struct variant_size;1336 template <class T> struct variant_size<const T>;1337 template <class T> struct variant_size<volatile T>;1338 template <class T> struct variant_size<const volatile T>;1339 template <class T> inline constexpr size_t variant_size_v = variant_size<T>::value;1340 template <class... Types>1341 struct variant_size<variant<Types...>>;1342 template <size_t I, class T> struct variant_alternative;1343 template <size_t I, class T> struct variant_alternative<I, const T>;1344 template <size_t I, class T> struct variant_alternative<I, volatile T>;1345 template <size_t I, class T> struct variant_alternative<I, const volatile T>;1346 template <size_t I, class T>1347 using variant_alternative_t = typename variant_alternative<I, T>::type;1348 template <size_t I, class... Types>1349 struct variant_alternative<I, variant<Types...>>;1350 inline constexpr size_t variant_npos = -1;1351 template <size_t I, class... Types>1352 constexpr variant_alternative_t<I, variant<Types...>>&1353 get(variant<Types...>&);1354 template <size_t I, class... Types>1355 constexpr variant_alternative_t<I, variant<Types...>>&&1356 get(variant<Types...>&&);1357 template <size_t I, class... Types>1358 constexpr const variant_alternative_t<I, variant<Types...>>&1359 get(const variant<Types...>&);1360 template <size_t I, class... Types>1361 constexpr const variant_alternative_t<I, variant<Types...>>&&1362 get(const variant<Types...>&&);1363 template <class T, class... Types>1364 constexpr T& get(variant<Types...>&);1365 template <class T, class... Types>1366 constexpr T&& get(variant<Types...>&&);1367 template <class T, class... Types>1368 constexpr const T& get(const variant<Types...>&);1369 template <class T, class... Types>1370 constexpr const T&& get(const variant<Types...>&&);1371 template <size_t I, class... Types>1372 constexpr add_pointer_t<variant_alternative_t<I, variant<Types...>>>1373 get_if(variant<Types...>*) noexcept;1374 template <size_t I, class... Types>1375 constexpr add_pointer_t<const variant_alternative_t<I, variant<Types...>>>1376 get_if(const variant<Types...>*) noexcept;1377 template <class T, class... Types>1378 constexpr add_pointer_t<T> get_if(variant<Types...>*) noexcept;1379 template <class T, class... Types>1380 constexpr add_pointer_t<const T> get_if(const variant<Types...>*) noexcept;1381 1382 template <class... Types>1383 class variant {1384 public:1385 // constructors1386 constexpr variant()= default ;1387 constexpr variant(const variant&);1388 constexpr variant(variant&&);1389 template<typename T,1390 typename = std::enable_if_t<!is_same_v<std::variant<Types...>, decay_t<T>>>>1391 constexpr variant(T&&);1392 // assignment1393 variant& operator=(const variant&);1394 variant& operator=(variant&&) ;1395 template<typename T,1396 typename = std::enable_if_t<!is_same_v<std::variant<Types...>, decay_t<T>>>>1397 variant& operator=(T&&);1398 };1399 #endif1400 1401} // namespace std1402