1 // -*- C++ -*-
2 //===----------------------------------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #ifndef _LIBCPP___FUNCTIONAL_FUNCTION_H
11 #define _LIBCPP___FUNCTIONAL_FUNCTION_H
12 
13 #include <__assert>
14 #include <__config>
15 #include <__functional/binary_function.h>
16 #include <__functional/invoke.h>
17 #include <__functional/unary_function.h>
18 #include <__iterator/iterator_traits.h>
19 #include <__memory/addressof.h>
20 #include <__memory/allocator.h>
21 #include <__memory/allocator_destructor.h>
22 #include <__memory/allocator_traits.h>
23 #include <__memory/builtin_new_allocator.h>
24 #include <__memory/compressed_pair.h>
25 #include <__memory/unique_ptr.h>
26 #include <__type_traits/strip_signature.h>
27 #include <__utility/forward.h>
28 #include <__utility/move.h>
29 #include <__utility/piecewise_construct.h>
30 #include <__utility/swap.h>
31 #include <exception>
32 #include <new>
33 #include <tuple>
34 #include <type_traits>
35 #include <typeinfo>
36 
37 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
38 #  pragma GCC system_header
39 #endif
40 
41 #ifndef _LIBCPP_CXX03_LANG
42 
43 _LIBCPP_BEGIN_NAMESPACE_STD
44 
45 // bad_function_call
46 
47 _LIBCPP_DIAGNOSTIC_PUSH
48 _LIBCPP_CLANG_DIAGNOSTIC_IGNORED("-Wweak-vtables")
49 class _LIBCPP_EXCEPTION_ABI bad_function_call
50     : public exception
51 {
52 public:
53 // Note that when a key function is not used, every translation unit that uses
54 // bad_function_call will end up containing a weak definition of the vtable and
55 // typeinfo.
56 #ifdef _LIBCPP_ABI_BAD_FUNCTION_CALL_KEY_FUNCTION
57     ~bad_function_call() _NOEXCEPT override;
58 #else
59     ~bad_function_call() _NOEXCEPT override {}
60 #endif
61 
62 #ifdef _LIBCPP_ABI_BAD_FUNCTION_CALL_GOOD_WHAT_MESSAGE
63     const char* what() const _NOEXCEPT override;
64 #endif
65 };
66 _LIBCPP_DIAGNOSTIC_POP
67 
68 _LIBCPP_NORETURN inline _LIBCPP_INLINE_VISIBILITY
69 void __throw_bad_function_call()
70 {
71 #ifndef _LIBCPP_NO_EXCEPTIONS
72     throw bad_function_call();
73 #else
74     _VSTD::abort();
75 #endif
76 }
77 
78 template<class _Fp> class _LIBCPP_TEMPLATE_VIS function; // undefined
79 
80 namespace __function
81 {
82 
83 template<class _Rp>
84 struct __maybe_derive_from_unary_function
85 {
86 };
87 
88 template<class _Rp, class _A1>
89 struct __maybe_derive_from_unary_function<_Rp(_A1)>
90     : public __unary_function<_A1, _Rp>
91 {
92 };
93 
94 template<class _Rp>
95 struct __maybe_derive_from_binary_function
96 {
97 };
98 
99 template<class _Rp, class _A1, class _A2>
100 struct __maybe_derive_from_binary_function<_Rp(_A1, _A2)>
101     : public __binary_function<_A1, _A2, _Rp>
102 {
103 };
104 
105 template <class _Fp>
106 _LIBCPP_INLINE_VISIBILITY
107 bool __not_null(_Fp const&) { return true; }
108 
109 template <class _Fp>
110 _LIBCPP_INLINE_VISIBILITY
111 bool __not_null(_Fp* __ptr) { return __ptr; }
112 
113 template <class _Ret, class _Class>
114 _LIBCPP_INLINE_VISIBILITY
115 bool __not_null(_Ret _Class::*__ptr) { return __ptr; }
116 
117 template <class _Fp>
118 _LIBCPP_INLINE_VISIBILITY
119 bool __not_null(function<_Fp> const& __f) { return !!__f; }
120 
121 #ifdef _LIBCPP_HAS_EXTENSION_BLOCKS
122 template <class _Rp, class ..._Args>
123 _LIBCPP_INLINE_VISIBILITY
124 bool __not_null(_Rp (^__p)(_Args...)) { return __p; }
125 #endif
126 
127 } // namespace __function
128 
129 namespace __function {
130 
131 // __alloc_func holds a functor and an allocator.
132 
133 template <class _Fp, class _Ap, class _FB> class __alloc_func;
134 template <class _Fp, class _FB>
135 class __default_alloc_func;
136 
137 template <class _Fp, class _Ap, class _Rp, class... _ArgTypes>
138 class __alloc_func<_Fp, _Ap, _Rp(_ArgTypes...)>
139 {
140     __compressed_pair<_Fp, _Ap> __f_;
141 
142   public:
143     typedef _LIBCPP_NODEBUG _Fp _Target;
144     typedef _LIBCPP_NODEBUG _Ap _Alloc;
145 
146     _LIBCPP_INLINE_VISIBILITY
147     const _Target& __target() const { return __f_.first(); }
148 
149     // WIN32 APIs may define __allocator, so use __get_allocator instead.
150     _LIBCPP_INLINE_VISIBILITY
151     const _Alloc& __get_allocator() const { return __f_.second(); }
152 
153     _LIBCPP_INLINE_VISIBILITY
154     explicit __alloc_func(_Target&& __f)
155         : __f_(piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__f)),
156                _VSTD::forward_as_tuple())
157     {
158     }
159 
160     _LIBCPP_INLINE_VISIBILITY
161     explicit __alloc_func(const _Target& __f, const _Alloc& __a)
162         : __f_(piecewise_construct, _VSTD::forward_as_tuple(__f),
163                _VSTD::forward_as_tuple(__a))
164     {
165     }
166 
167     _LIBCPP_INLINE_VISIBILITY
168     explicit __alloc_func(const _Target& __f, _Alloc&& __a)
169         : __f_(piecewise_construct, _VSTD::forward_as_tuple(__f),
170                _VSTD::forward_as_tuple(_VSTD::move(__a)))
171     {
172     }
173 
174     _LIBCPP_INLINE_VISIBILITY
175     explicit __alloc_func(_Target&& __f, _Alloc&& __a)
176         : __f_(piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__f)),
177                _VSTD::forward_as_tuple(_VSTD::move(__a)))
178     {
179     }
180 
181     _LIBCPP_INLINE_VISIBILITY
182     _Rp operator()(_ArgTypes&&... __arg)
183     {
184         typedef __invoke_void_return_wrapper<_Rp> _Invoker;
185         return _Invoker::__call(__f_.first(),
186                                 _VSTD::forward<_ArgTypes>(__arg)...);
187     }
188 
189     _LIBCPP_INLINE_VISIBILITY
190     __alloc_func* __clone() const
191     {
192         typedef allocator_traits<_Alloc> __alloc_traits;
193         typedef __rebind_alloc<__alloc_traits, __alloc_func> _AA;
194         _AA __a(__f_.second());
195         typedef __allocator_destructor<_AA> _Dp;
196         unique_ptr<__alloc_func, _Dp> __hold(__a.allocate(1), _Dp(__a, 1));
197         ::new ((void*)__hold.get()) __alloc_func(__f_.first(), _Alloc(__a));
198         return __hold.release();
199     }
200 
201     _LIBCPP_INLINE_VISIBILITY
202     void destroy() _NOEXCEPT { __f_.~__compressed_pair<_Target, _Alloc>(); }
203 
204     static void __destroy_and_delete(__alloc_func* __f) {
205       typedef allocator_traits<_Alloc> __alloc_traits;
206       typedef __rebind_alloc<__alloc_traits, __alloc_func> _FunAlloc;
207       _FunAlloc __a(__f->__get_allocator());
208       __f->destroy();
209       __a.deallocate(__f, 1);
210     }
211 };
212 
213 template <class _Fp, class _Rp, class... _ArgTypes>
214 class __default_alloc_func<_Fp, _Rp(_ArgTypes...)> {
215   _Fp __f_;
216 
217 public:
218   typedef _LIBCPP_NODEBUG _Fp _Target;
219 
220   _LIBCPP_INLINE_VISIBILITY
221   const _Target& __target() const { return __f_; }
222 
223   _LIBCPP_INLINE_VISIBILITY
224   explicit __default_alloc_func(_Target&& __f) : __f_(_VSTD::move(__f)) {}
225 
226   _LIBCPP_INLINE_VISIBILITY
227   explicit __default_alloc_func(const _Target& __f) : __f_(__f) {}
228 
229   _LIBCPP_INLINE_VISIBILITY
230   _Rp operator()(_ArgTypes&&... __arg) {
231     typedef __invoke_void_return_wrapper<_Rp> _Invoker;
232     return _Invoker::__call(__f_, _VSTD::forward<_ArgTypes>(__arg)...);
233   }
234 
235   _LIBCPP_INLINE_VISIBILITY
236   __default_alloc_func* __clone() const {
237       __builtin_new_allocator::__holder_t __hold =
238         __builtin_new_allocator::__allocate_type<__default_alloc_func>(1);
239     __default_alloc_func* __res =
240         ::new ((void*)__hold.get()) __default_alloc_func(__f_);
241     (void)__hold.release();
242     return __res;
243   }
244 
245   _LIBCPP_INLINE_VISIBILITY
246   void destroy() _NOEXCEPT { __f_.~_Target(); }
247 
248   static void __destroy_and_delete(__default_alloc_func* __f) {
249     __f->destroy();
250       __builtin_new_allocator::__deallocate_type<__default_alloc_func>(__f, 1);
251   }
252 };
253 
254 // __base provides an abstract interface for copyable functors.
255 
256 template<class _Fp> class _LIBCPP_TEMPLATE_VIS __base;
257 
258 template<class _Rp, class ..._ArgTypes>
259 class __base<_Rp(_ArgTypes...)>
260 {
261     __base(const __base&);
262     __base& operator=(const __base&);
263 public:
264     _LIBCPP_INLINE_VISIBILITY __base() {}
265     _LIBCPP_HIDE_FROM_ABI_VIRTUAL virtual ~__base() {}
266     virtual __base* __clone() const = 0;
267     virtual void __clone(__base*) const = 0;
268     virtual void destroy() _NOEXCEPT = 0;
269     virtual void destroy_deallocate() _NOEXCEPT = 0;
270     virtual _Rp operator()(_ArgTypes&& ...) = 0;
271 #ifndef _LIBCPP_HAS_NO_RTTI
272     virtual const void* target(const type_info&) const _NOEXCEPT = 0;
273     virtual const std::type_info& target_type() const _NOEXCEPT = 0;
274 #endif // _LIBCPP_HAS_NO_RTTI
275 };
276 
277 // __func implements __base for a given functor type.
278 
279 template<class _FD, class _Alloc, class _FB> class __func;
280 
281 template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
282 class __func<_Fp, _Alloc, _Rp(_ArgTypes...)>
283     : public  __base<_Rp(_ArgTypes...)>
284 {
285     __alloc_func<_Fp, _Alloc, _Rp(_ArgTypes...)> __f_;
286 public:
287     _LIBCPP_INLINE_VISIBILITY
288     explicit __func(_Fp&& __f)
289         : __f_(_VSTD::move(__f)) {}
290 
291     _LIBCPP_INLINE_VISIBILITY
292     explicit __func(const _Fp& __f, const _Alloc& __a)
293         : __f_(__f, __a) {}
294 
295     _LIBCPP_INLINE_VISIBILITY
296     explicit __func(const _Fp& __f, _Alloc&& __a)
297         : __f_(__f, _VSTD::move(__a)) {}
298 
299     _LIBCPP_INLINE_VISIBILITY
300     explicit __func(_Fp&& __f, _Alloc&& __a)
301         : __f_(_VSTD::move(__f), _VSTD::move(__a)) {}
302 
303     virtual __base<_Rp(_ArgTypes...)>* __clone() const;
304     virtual void __clone(__base<_Rp(_ArgTypes...)>*) const;
305     virtual void destroy() _NOEXCEPT;
306     virtual void destroy_deallocate() _NOEXCEPT;
307     virtual _Rp operator()(_ArgTypes&&... __arg);
308 #ifndef _LIBCPP_HAS_NO_RTTI
309     virtual const void* target(const type_info&) const _NOEXCEPT;
310     virtual const std::type_info& target_type() const _NOEXCEPT;
311 #endif // _LIBCPP_HAS_NO_RTTI
312 };
313 
314 template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
315 __base<_Rp(_ArgTypes...)>*
316 __func<_Fp, _Alloc, _Rp(_ArgTypes...)>::__clone() const
317 {
318     typedef allocator_traits<_Alloc> __alloc_traits;
319     typedef __rebind_alloc<__alloc_traits, __func> _Ap;
320     _Ap __a(__f_.__get_allocator());
321     typedef __allocator_destructor<_Ap> _Dp;
322     unique_ptr<__func, _Dp> __hold(__a.allocate(1), _Dp(__a, 1));
323     ::new ((void*)__hold.get()) __func(__f_.__target(), _Alloc(__a));
324     return __hold.release();
325 }
326 
327 template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
328 void
329 __func<_Fp, _Alloc, _Rp(_ArgTypes...)>::__clone(__base<_Rp(_ArgTypes...)>* __p) const
330 {
331     ::new ((void*)__p) __func(__f_.__target(), __f_.__get_allocator());
332 }
333 
334 template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
335 void
336 __func<_Fp, _Alloc, _Rp(_ArgTypes...)>::destroy() _NOEXCEPT
337 {
338     __f_.destroy();
339 }
340 
341 template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
342 void
343 __func<_Fp, _Alloc, _Rp(_ArgTypes...)>::destroy_deallocate() _NOEXCEPT
344 {
345     typedef allocator_traits<_Alloc> __alloc_traits;
346     typedef __rebind_alloc<__alloc_traits, __func> _Ap;
347     _Ap __a(__f_.__get_allocator());
348     __f_.destroy();
349     __a.deallocate(this, 1);
350 }
351 
352 template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
353 _Rp
354 __func<_Fp, _Alloc, _Rp(_ArgTypes...)>::operator()(_ArgTypes&& ... __arg)
355 {
356     return __f_(_VSTD::forward<_ArgTypes>(__arg)...);
357 }
358 
359 #ifndef _LIBCPP_HAS_NO_RTTI
360 
361 template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
362 const void*
363 __func<_Fp, _Alloc, _Rp(_ArgTypes...)>::target(const type_info& __ti) const _NOEXCEPT
364 {
365     if (__ti == typeid(_Fp))
366         return _VSTD::addressof(__f_.__target());
367     return nullptr;
368 }
369 
370 template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
371 const std::type_info&
372 __func<_Fp, _Alloc, _Rp(_ArgTypes...)>::target_type() const _NOEXCEPT
373 {
374     return typeid(_Fp);
375 }
376 
377 #endif // _LIBCPP_HAS_NO_RTTI
378 
379 // __value_func creates a value-type from a __func.
380 
381 template <class _Fp> class __value_func;
382 
383 template <class _Rp, class... _ArgTypes> class __value_func<_Rp(_ArgTypes...)>
384 {
385     _LIBCPP_SUPPRESS_DEPRECATED_PUSH
386     typename aligned_storage<3 * sizeof(void*)>::type __buf_;
387     _LIBCPP_SUPPRESS_DEPRECATED_POP
388 
389     typedef __base<_Rp(_ArgTypes...)> __func;
390     __func* __f_;
391 
392     _LIBCPP_NO_CFI static __func* __as_base(void* __p)
393     {
394         return reinterpret_cast<__func*>(__p);
395     }
396 
397   public:
398     _LIBCPP_INLINE_VISIBILITY
399     __value_func() _NOEXCEPT : __f_(nullptr) {}
400 
401     template <class _Fp, class _Alloc>
402     _LIBCPP_INLINE_VISIBILITY __value_func(_Fp&& __f, const _Alloc& __a)
403         : __f_(nullptr)
404     {
405         typedef allocator_traits<_Alloc> __alloc_traits;
406         typedef __function::__func<_Fp, _Alloc, _Rp(_ArgTypes...)> _Fun;
407         typedef __rebind_alloc<__alloc_traits, _Fun> _FunAlloc;
408 
409         if (__function::__not_null(__f))
410         {
411             _FunAlloc __af(__a);
412             if (sizeof(_Fun) <= sizeof(__buf_) &&
413                 is_nothrow_copy_constructible<_Fp>::value &&
414                 is_nothrow_copy_constructible<_FunAlloc>::value)
415             {
416                 __f_ =
417                     ::new ((void*)&__buf_) _Fun(_VSTD::move(__f), _Alloc(__af));
418             }
419             else
420             {
421                 typedef __allocator_destructor<_FunAlloc> _Dp;
422                 unique_ptr<__func, _Dp> __hold(__af.allocate(1), _Dp(__af, 1));
423                 ::new ((void*)__hold.get()) _Fun(_VSTD::move(__f), _Alloc(__a));
424                 __f_ = __hold.release();
425             }
426         }
427     }
428 
429     template <class _Fp,
430         class = typename enable_if<!is_same<typename decay<_Fp>::type, __value_func>::value>::type>
431     _LIBCPP_INLINE_VISIBILITY explicit __value_func(_Fp&& __f)
432         : __value_func(_VSTD::forward<_Fp>(__f), allocator<_Fp>()) {}
433 
434     _LIBCPP_INLINE_VISIBILITY
435     __value_func(const __value_func& __f)
436     {
437         if (__f.__f_ == nullptr)
438             __f_ = nullptr;
439         else if ((void*)__f.__f_ == &__f.__buf_)
440         {
441             __f_ = __as_base(&__buf_);
442             __f.__f_->__clone(__f_);
443         }
444         else
445             __f_ = __f.__f_->__clone();
446     }
447 
448     _LIBCPP_INLINE_VISIBILITY
449     __value_func(__value_func&& __f) _NOEXCEPT
450     {
451         if (__f.__f_ == nullptr)
452             __f_ = nullptr;
453         else if ((void*)__f.__f_ == &__f.__buf_)
454         {
455             __f_ = __as_base(&__buf_);
456             __f.__f_->__clone(__f_);
457         }
458         else
459         {
460             __f_ = __f.__f_;
461             __f.__f_ = nullptr;
462         }
463     }
464 
465     _LIBCPP_INLINE_VISIBILITY
466     ~__value_func()
467     {
468         if ((void*)__f_ == &__buf_)
469             __f_->destroy();
470         else if (__f_)
471             __f_->destroy_deallocate();
472     }
473 
474     _LIBCPP_INLINE_VISIBILITY
475     __value_func& operator=(__value_func&& __f)
476     {
477         *this = nullptr;
478         if (__f.__f_ == nullptr)
479             __f_ = nullptr;
480         else if ((void*)__f.__f_ == &__f.__buf_)
481         {
482             __f_ = __as_base(&__buf_);
483             __f.__f_->__clone(__f_);
484         }
485         else
486         {
487             __f_ = __f.__f_;
488             __f.__f_ = nullptr;
489         }
490         return *this;
491     }
492 
493     _LIBCPP_INLINE_VISIBILITY
494     __value_func& operator=(nullptr_t)
495     {
496         __func* __f = __f_;
497         __f_ = nullptr;
498         if ((void*)__f == &__buf_)
499             __f->destroy();
500         else if (__f)
501             __f->destroy_deallocate();
502         return *this;
503     }
504 
505     _LIBCPP_INLINE_VISIBILITY
506     _Rp operator()(_ArgTypes&&... __args) const
507     {
508         if (__f_ == nullptr)
509             __throw_bad_function_call();
510         return (*__f_)(_VSTD::forward<_ArgTypes>(__args)...);
511     }
512 
513     _LIBCPP_INLINE_VISIBILITY
514     void swap(__value_func& __f) _NOEXCEPT
515     {
516         if (&__f == this)
517             return;
518         if ((void*)__f_ == &__buf_ && (void*)__f.__f_ == &__f.__buf_)
519         {
520             _LIBCPP_SUPPRESS_DEPRECATED_PUSH
521             typename aligned_storage<sizeof(__buf_)>::type __tempbuf;
522             _LIBCPP_SUPPRESS_DEPRECATED_POP
523             __func* __t = __as_base(&__tempbuf);
524             __f_->__clone(__t);
525             __f_->destroy();
526             __f_ = nullptr;
527             __f.__f_->__clone(__as_base(&__buf_));
528             __f.__f_->destroy();
529             __f.__f_ = nullptr;
530             __f_ = __as_base(&__buf_);
531             __t->__clone(__as_base(&__f.__buf_));
532             __t->destroy();
533             __f.__f_ = __as_base(&__f.__buf_);
534         }
535         else if ((void*)__f_ == &__buf_)
536         {
537             __f_->__clone(__as_base(&__f.__buf_));
538             __f_->destroy();
539             __f_ = __f.__f_;
540             __f.__f_ = __as_base(&__f.__buf_);
541         }
542         else if ((void*)__f.__f_ == &__f.__buf_)
543         {
544             __f.__f_->__clone(__as_base(&__buf_));
545             __f.__f_->destroy();
546             __f.__f_ = __f_;
547             __f_ = __as_base(&__buf_);
548         }
549         else
550             _VSTD::swap(__f_, __f.__f_);
551     }
552 
553     _LIBCPP_INLINE_VISIBILITY
554     explicit operator bool() const _NOEXCEPT { return __f_ != nullptr; }
555 
556 #ifndef _LIBCPP_HAS_NO_RTTI
557     _LIBCPP_INLINE_VISIBILITY
558     const std::type_info& target_type() const _NOEXCEPT
559     {
560         if (__f_ == nullptr)
561             return typeid(void);
562         return __f_->target_type();
563     }
564 
565     template <typename _Tp>
566     _LIBCPP_INLINE_VISIBILITY const _Tp* target() const _NOEXCEPT
567     {
568         if (__f_ == nullptr)
569             return nullptr;
570         return (const _Tp*)__f_->target(typeid(_Tp));
571     }
572 #endif // _LIBCPP_HAS_NO_RTTI
573 };
574 
575 // Storage for a functor object, to be used with __policy to manage copy and
576 // destruction.
577 union __policy_storage
578 {
579     mutable char __small[sizeof(void*) * 2];
580     void* __large;
581 };
582 
583 // True if _Fun can safely be held in __policy_storage.__small.
584 template <typename _Fun>
585 struct __use_small_storage
586     : public integral_constant<
587           bool, sizeof(_Fun) <= sizeof(__policy_storage) &&
588                     _LIBCPP_ALIGNOF(_Fun) <= _LIBCPP_ALIGNOF(__policy_storage) &&
589                     is_trivially_copy_constructible<_Fun>::value &&
590                     is_trivially_destructible<_Fun>::value> {};
591 
592 // Policy contains information about how to copy, destroy, and move the
593 // underlying functor. You can think of it as a vtable of sorts.
594 struct __policy
595 {
596     // Used to copy or destroy __large values. null for trivial objects.
597     void* (*const __clone)(const void*);
598     void (*const __destroy)(void*);
599 
600     // True if this is the null policy (no value).
601     const bool __is_null;
602 
603     // The target type. May be null if RTTI is disabled.
604     const std::type_info* const __type_info;
605 
606     // Returns a pointer to a static policy object suitable for the functor
607     // type.
608     template <typename _Fun>
609     _LIBCPP_INLINE_VISIBILITY static const __policy* __create()
610     {
611         return __choose_policy<_Fun>(__use_small_storage<_Fun>());
612     }
613 
614     _LIBCPP_INLINE_VISIBILITY
615     static const __policy* __create_empty()
616     {
617         static const _LIBCPP_CONSTEXPR __policy __policy_ = {nullptr, nullptr,
618                                                              true,
619 #ifndef _LIBCPP_HAS_NO_RTTI
620                                                              &typeid(void)
621 #else
622                                                              nullptr
623 #endif
624         };
625         return &__policy_;
626     }
627 
628   private:
629     template <typename _Fun> static void* __large_clone(const void* __s)
630     {
631         const _Fun* __f = static_cast<const _Fun*>(__s);
632         return __f->__clone();
633     }
634 
635     template <typename _Fun>
636     static void __large_destroy(void* __s) {
637       _Fun::__destroy_and_delete(static_cast<_Fun*>(__s));
638     }
639 
640     template <typename _Fun>
641     _LIBCPP_INLINE_VISIBILITY static const __policy*
642     __choose_policy(/* is_small = */ false_type) {
643       static const _LIBCPP_CONSTEXPR __policy __policy_ = {
644           &__large_clone<_Fun>, &__large_destroy<_Fun>, false,
645 #ifndef _LIBCPP_HAS_NO_RTTI
646           &typeid(typename _Fun::_Target)
647 #else
648           nullptr
649 #endif
650       };
651         return &__policy_;
652     }
653 
654     template <typename _Fun>
655     _LIBCPP_INLINE_VISIBILITY static const __policy*
656         __choose_policy(/* is_small = */ true_type)
657     {
658         static const _LIBCPP_CONSTEXPR __policy __policy_ = {
659             nullptr, nullptr, false,
660 #ifndef _LIBCPP_HAS_NO_RTTI
661             &typeid(typename _Fun::_Target)
662 #else
663             nullptr
664 #endif
665         };
666         return &__policy_;
667     }
668 };
669 
670 // Used to choose between perfect forwarding or pass-by-value. Pass-by-value is
671 // faster for types that can be passed in registers.
672 template <typename _Tp>
673 using __fast_forward = __conditional_t<is_scalar<_Tp>::value, _Tp, _Tp&&>;
674 
675 // __policy_invoker calls an instance of __alloc_func held in __policy_storage.
676 
677 template <class _Fp> struct __policy_invoker;
678 
679 template <class _Rp, class... _ArgTypes>
680 struct __policy_invoker<_Rp(_ArgTypes...)>
681 {
682     typedef _Rp (*__Call)(const __policy_storage*,
683                           __fast_forward<_ArgTypes>...);
684 
685     __Call __call_;
686 
687     // Creates an invoker that throws bad_function_call.
688     _LIBCPP_INLINE_VISIBILITY
689     __policy_invoker() : __call_(&__call_empty) {}
690 
691     // Creates an invoker that calls the given instance of __func.
692     template <typename _Fun>
693     _LIBCPP_INLINE_VISIBILITY static __policy_invoker __create()
694     {
695         return __policy_invoker(&__call_impl<_Fun>);
696     }
697 
698   private:
699     _LIBCPP_INLINE_VISIBILITY
700     explicit __policy_invoker(__Call __c) : __call_(__c) {}
701 
702     static _Rp __call_empty(const __policy_storage*,
703                             __fast_forward<_ArgTypes>...)
704     {
705         __throw_bad_function_call();
706     }
707 
708     template <typename _Fun>
709     static _Rp __call_impl(const __policy_storage* __buf,
710                            __fast_forward<_ArgTypes>... __args)
711     {
712         _Fun* __f = reinterpret_cast<_Fun*>(__use_small_storage<_Fun>::value
713                                                 ? &__buf->__small
714                                                 : __buf->__large);
715         return (*__f)(_VSTD::forward<_ArgTypes>(__args)...);
716     }
717 };
718 
719 // __policy_func uses a __policy and __policy_invoker to create a type-erased,
720 // copyable functor.
721 
722 template <class _Fp> class __policy_func;
723 
724 template <class _Rp, class... _ArgTypes> class __policy_func<_Rp(_ArgTypes...)>
725 {
726     // Inline storage for small objects.
727     __policy_storage __buf_;
728 
729     // Calls the value stored in __buf_. This could technically be part of
730     // policy, but storing it here eliminates a level of indirection inside
731     // operator().
732     typedef __function::__policy_invoker<_Rp(_ArgTypes...)> __invoker;
733     __invoker __invoker_;
734 
735     // The policy that describes how to move / copy / destroy __buf_. Never
736     // null, even if the function is empty.
737     const __policy* __policy_;
738 
739   public:
740     _LIBCPP_INLINE_VISIBILITY
741     __policy_func() : __policy_(__policy::__create_empty()) {}
742 
743     template <class _Fp, class _Alloc>
744     _LIBCPP_INLINE_VISIBILITY __policy_func(_Fp&& __f, const _Alloc& __a)
745         : __policy_(__policy::__create_empty())
746     {
747         typedef __alloc_func<_Fp, _Alloc, _Rp(_ArgTypes...)> _Fun;
748         typedef allocator_traits<_Alloc> __alloc_traits;
749         typedef __rebind_alloc<__alloc_traits, _Fun> _FunAlloc;
750 
751         if (__function::__not_null(__f))
752         {
753             __invoker_ = __invoker::template __create<_Fun>();
754             __policy_ = __policy::__create<_Fun>();
755 
756             _FunAlloc __af(__a);
757             if (__use_small_storage<_Fun>())
758             {
759                 ::new ((void*)&__buf_.__small)
760                     _Fun(_VSTD::move(__f), _Alloc(__af));
761             }
762             else
763             {
764                 typedef __allocator_destructor<_FunAlloc> _Dp;
765                 unique_ptr<_Fun, _Dp> __hold(__af.allocate(1), _Dp(__af, 1));
766                 ::new ((void*)__hold.get())
767                     _Fun(_VSTD::move(__f), _Alloc(__af));
768                 __buf_.__large = __hold.release();
769             }
770         }
771     }
772 
773     template <class _Fp, class = typename enable_if<!is_same<typename decay<_Fp>::type, __policy_func>::value>::type>
774     _LIBCPP_INLINE_VISIBILITY explicit __policy_func(_Fp&& __f)
775         : __policy_(__policy::__create_empty()) {
776       typedef __default_alloc_func<_Fp, _Rp(_ArgTypes...)> _Fun;
777 
778       if (__function::__not_null(__f)) {
779         __invoker_ = __invoker::template __create<_Fun>();
780         __policy_ = __policy::__create<_Fun>();
781         if (__use_small_storage<_Fun>()) {
782           ::new ((void*)&__buf_.__small) _Fun(_VSTD::move(__f));
783         } else {
784           __builtin_new_allocator::__holder_t __hold =
785               __builtin_new_allocator::__allocate_type<_Fun>(1);
786           __buf_.__large = ::new ((void*)__hold.get()) _Fun(_VSTD::move(__f));
787           (void)__hold.release();
788         }
789       }
790     }
791 
792     _LIBCPP_INLINE_VISIBILITY
793     __policy_func(const __policy_func& __f)
794         : __buf_(__f.__buf_), __invoker_(__f.__invoker_),
795           __policy_(__f.__policy_)
796     {
797         if (__policy_->__clone)
798             __buf_.__large = __policy_->__clone(__f.__buf_.__large);
799     }
800 
801     _LIBCPP_INLINE_VISIBILITY
802     __policy_func(__policy_func&& __f)
803         : __buf_(__f.__buf_), __invoker_(__f.__invoker_),
804           __policy_(__f.__policy_)
805     {
806         if (__policy_->__destroy)
807         {
808             __f.__policy_ = __policy::__create_empty();
809             __f.__invoker_ = __invoker();
810         }
811     }
812 
813     _LIBCPP_INLINE_VISIBILITY
814     ~__policy_func()
815     {
816         if (__policy_->__destroy)
817             __policy_->__destroy(__buf_.__large);
818     }
819 
820     _LIBCPP_INLINE_VISIBILITY
821     __policy_func& operator=(__policy_func&& __f)
822     {
823         *this = nullptr;
824         __buf_ = __f.__buf_;
825         __invoker_ = __f.__invoker_;
826         __policy_ = __f.__policy_;
827         __f.__policy_ = __policy::__create_empty();
828         __f.__invoker_ = __invoker();
829         return *this;
830     }
831 
832     _LIBCPP_INLINE_VISIBILITY
833     __policy_func& operator=(nullptr_t)
834     {
835         const __policy* __p = __policy_;
836         __policy_ = __policy::__create_empty();
837         __invoker_ = __invoker();
838         if (__p->__destroy)
839             __p->__destroy(__buf_.__large);
840         return *this;
841     }
842 
843     _LIBCPP_INLINE_VISIBILITY
844     _Rp operator()(_ArgTypes&&... __args) const
845     {
846         return __invoker_.__call_(_VSTD::addressof(__buf_),
847                                   _VSTD::forward<_ArgTypes>(__args)...);
848     }
849 
850     _LIBCPP_INLINE_VISIBILITY
851     void swap(__policy_func& __f)
852     {
853         _VSTD::swap(__invoker_, __f.__invoker_);
854         _VSTD::swap(__policy_, __f.__policy_);
855         _VSTD::swap(__buf_, __f.__buf_);
856     }
857 
858     _LIBCPP_INLINE_VISIBILITY
859     explicit operator bool() const _NOEXCEPT
860     {
861         return !__policy_->__is_null;
862     }
863 
864 #ifndef _LIBCPP_HAS_NO_RTTI
865     _LIBCPP_INLINE_VISIBILITY
866     const std::type_info& target_type() const _NOEXCEPT
867     {
868         return *__policy_->__type_info;
869     }
870 
871     template <typename _Tp>
872     _LIBCPP_INLINE_VISIBILITY const _Tp* target() const _NOEXCEPT
873     {
874         if (__policy_->__is_null || typeid(_Tp) != *__policy_->__type_info)
875             return nullptr;
876         if (__policy_->__clone) // Out of line storage.
877             return reinterpret_cast<const _Tp*>(__buf_.__large);
878         else
879             return reinterpret_cast<const _Tp*>(&__buf_.__small);
880     }
881 #endif // _LIBCPP_HAS_NO_RTTI
882 };
883 
884 #if defined(_LIBCPP_HAS_BLOCKS_RUNTIME)
885 
886 extern "C" void *_Block_copy(const void *);
887 extern "C" void _Block_release(const void *);
888 
889 template<class _Rp1, class ..._ArgTypes1, class _Alloc, class _Rp, class ..._ArgTypes>
890 class __func<_Rp1(^)(_ArgTypes1...), _Alloc, _Rp(_ArgTypes...)>
891     : public  __base<_Rp(_ArgTypes...)>
892 {
893     typedef _Rp1(^__block_type)(_ArgTypes1...);
894     __block_type __f_;
895 
896 public:
897     _LIBCPP_INLINE_VISIBILITY
898     explicit __func(__block_type const& __f)
899 #ifdef _LIBCPP_HAS_OBJC_ARC
900         : __f_(__f)
901 #else
902         : __f_(reinterpret_cast<__block_type>(__f ? _Block_copy(__f) : nullptr))
903 #endif
904     { }
905 
906     // [TODO] add && to save on a retain
907 
908     _LIBCPP_INLINE_VISIBILITY
909     explicit __func(__block_type __f, const _Alloc& /* unused */)
910 #ifdef _LIBCPP_HAS_OBJC_ARC
911         : __f_(__f)
912 #else
913         : __f_(reinterpret_cast<__block_type>(__f ? _Block_copy(__f) : nullptr))
914 #endif
915     { }
916 
917     virtual __base<_Rp(_ArgTypes...)>* __clone() const {
918         _LIBCPP_ASSERT(false,
919             "Block pointers are just pointers, so they should always fit into "
920             "std::function's small buffer optimization. This function should "
921             "never be invoked.");
922         return nullptr;
923     }
924 
925     virtual void __clone(__base<_Rp(_ArgTypes...)>* __p) const {
926         ::new ((void*)__p) __func(__f_);
927     }
928 
929     virtual void destroy() _NOEXCEPT {
930 #ifndef _LIBCPP_HAS_OBJC_ARC
931         if (__f_)
932             _Block_release(__f_);
933 #endif
934         __f_ = 0;
935     }
936 
937     virtual void destroy_deallocate() _NOEXCEPT {
938         _LIBCPP_ASSERT(false,
939             "Block pointers are just pointers, so they should always fit into "
940             "std::function's small buffer optimization. This function should "
941             "never be invoked.");
942     }
943 
944     virtual _Rp operator()(_ArgTypes&& ... __arg) {
945         return _VSTD::__invoke(__f_, _VSTD::forward<_ArgTypes>(__arg)...);
946     }
947 
948 #ifndef _LIBCPP_HAS_NO_RTTI
949     virtual const void* target(type_info const& __ti) const _NOEXCEPT {
950         if (__ti == typeid(__func::__block_type))
951             return &__f_;
952         return (const void*)nullptr;
953     }
954 
955     virtual const std::type_info& target_type() const _NOEXCEPT {
956         return typeid(__func::__block_type);
957     }
958 #endif // _LIBCPP_HAS_NO_RTTI
959 };
960 
961 #endif // _LIBCPP_HAS_EXTENSION_BLOCKS
962 
963 } // namespace __function
964 
965 template<class _Rp, class ..._ArgTypes>
966 class _LIBCPP_TEMPLATE_VIS function<_Rp(_ArgTypes...)>
967     : public __function::__maybe_derive_from_unary_function<_Rp(_ArgTypes...)>,
968       public __function::__maybe_derive_from_binary_function<_Rp(_ArgTypes...)>
969 {
970 #ifndef _LIBCPP_ABI_OPTIMIZED_FUNCTION
971     typedef __function::__value_func<_Rp(_ArgTypes...)> __func;
972 #else
973     typedef __function::__policy_func<_Rp(_ArgTypes...)> __func;
974 #endif
975 
976     __func __f_;
977 
978     template <class _Fp, bool = _And<
979         _IsNotSame<__remove_cvref_t<_Fp>, function>,
980         __invokable<_Fp, _ArgTypes...>
981     >::value>
982     struct __callable;
983     template <class _Fp>
984         struct __callable<_Fp, true>
985         {
986             static const bool value = is_void<_Rp>::value ||
987                 __is_core_convertible<typename __invoke_of<_Fp, _ArgTypes...>::type,
988                                       _Rp>::value;
989         };
990     template <class _Fp>
991         struct __callable<_Fp, false>
992         {
993             static const bool value = false;
994         };
995 
996   template <class _Fp>
997   using _EnableIfLValueCallable = typename enable_if<__callable<_Fp&>::value>::type;
998 public:
999     typedef _Rp result_type;
1000 
1001     // construct/copy/destroy:
1002     _LIBCPP_INLINE_VISIBILITY
1003     function() _NOEXCEPT { }
1004     _LIBCPP_INLINE_VISIBILITY
1005     function(nullptr_t) _NOEXCEPT {}
1006     function(const function&);
1007     function(function&&) _NOEXCEPT;
1008     template<class _Fp, class = _EnableIfLValueCallable<_Fp>>
1009     function(_Fp);
1010 
1011 #if _LIBCPP_STD_VER <= 14
1012     template<class _Alloc>
1013       _LIBCPP_INLINE_VISIBILITY
1014       function(allocator_arg_t, const _Alloc&) _NOEXCEPT {}
1015     template<class _Alloc>
1016       _LIBCPP_INLINE_VISIBILITY
1017       function(allocator_arg_t, const _Alloc&, nullptr_t) _NOEXCEPT {}
1018     template<class _Alloc>
1019       function(allocator_arg_t, const _Alloc&, const function&);
1020     template<class _Alloc>
1021       function(allocator_arg_t, const _Alloc&, function&&);
1022     template<class _Fp, class _Alloc, class = _EnableIfLValueCallable<_Fp>>
1023       function(allocator_arg_t, const _Alloc& __a, _Fp __f);
1024 #endif
1025 
1026     function& operator=(const function&);
1027     function& operator=(function&&) _NOEXCEPT;
1028     function& operator=(nullptr_t) _NOEXCEPT;
1029     template<class _Fp, class = _EnableIfLValueCallable<typename decay<_Fp>::type>>
1030     function& operator=(_Fp&&);
1031 
1032     ~function();
1033 
1034     // function modifiers:
1035     void swap(function&) _NOEXCEPT;
1036 
1037 #if _LIBCPP_STD_VER <= 14
1038     template<class _Fp, class _Alloc>
1039       _LIBCPP_INLINE_VISIBILITY
1040       void assign(_Fp&& __f, const _Alloc& __a)
1041         {function(allocator_arg, __a, _VSTD::forward<_Fp>(__f)).swap(*this);}
1042 #endif
1043 
1044     // function capacity:
1045     _LIBCPP_INLINE_VISIBILITY
1046     explicit operator bool() const _NOEXCEPT {
1047       return static_cast<bool>(__f_);
1048     }
1049 
1050     // deleted overloads close possible hole in the type system
1051     template<class _R2, class... _ArgTypes2>
1052       bool operator==(const function<_R2(_ArgTypes2...)>&) const = delete;
1053     template<class _R2, class... _ArgTypes2>
1054       bool operator!=(const function<_R2(_ArgTypes2...)>&) const = delete;
1055 public:
1056     // function invocation:
1057     _Rp operator()(_ArgTypes...) const;
1058 
1059 #ifndef _LIBCPP_HAS_NO_RTTI
1060     // function target access:
1061     const std::type_info& target_type() const _NOEXCEPT;
1062     template <typename _Tp> _Tp* target() _NOEXCEPT;
1063     template <typename _Tp> const _Tp* target() const _NOEXCEPT;
1064 #endif // _LIBCPP_HAS_NO_RTTI
1065 };
1066 
1067 #if _LIBCPP_STD_VER >= 17
1068 template<class _Rp, class ..._Ap>
1069 function(_Rp(*)(_Ap...)) -> function<_Rp(_Ap...)>;
1070 
1071 template<class _Fp, class _Stripped = typename __strip_signature<decltype(&_Fp::operator())>::type>
1072 function(_Fp) -> function<_Stripped>;
1073 #endif // _LIBCPP_STD_VER >= 17
1074 
1075 template<class _Rp, class ..._ArgTypes>
1076 function<_Rp(_ArgTypes...)>::function(const function& __f) : __f_(__f.__f_) {}
1077 
1078 #if _LIBCPP_STD_VER <= 14
1079 template<class _Rp, class ..._ArgTypes>
1080 template <class _Alloc>
1081 function<_Rp(_ArgTypes...)>::function(allocator_arg_t, const _Alloc&,
1082                                      const function& __f) : __f_(__f.__f_) {}
1083 #endif
1084 
1085 template <class _Rp, class... _ArgTypes>
1086 function<_Rp(_ArgTypes...)>::function(function&& __f) _NOEXCEPT
1087     : __f_(_VSTD::move(__f.__f_)) {}
1088 
1089 #if _LIBCPP_STD_VER <= 14
1090 template<class _Rp, class ..._ArgTypes>
1091 template <class _Alloc>
1092 function<_Rp(_ArgTypes...)>::function(allocator_arg_t, const _Alloc&,
1093                                       function&& __f)
1094     : __f_(_VSTD::move(__f.__f_)) {}
1095 #endif
1096 
1097 template <class _Rp, class... _ArgTypes>
1098 template <class _Fp, class>
1099 function<_Rp(_ArgTypes...)>::function(_Fp __f) : __f_(_VSTD::move(__f)) {}
1100 
1101 #if _LIBCPP_STD_VER <= 14
1102 template <class _Rp, class... _ArgTypes>
1103 template <class _Fp, class _Alloc, class>
1104 function<_Rp(_ArgTypes...)>::function(allocator_arg_t, const _Alloc& __a,
1105                                       _Fp __f)
1106     : __f_(_VSTD::move(__f), __a) {}
1107 #endif
1108 
1109 template<class _Rp, class ..._ArgTypes>
1110 function<_Rp(_ArgTypes...)>&
1111 function<_Rp(_ArgTypes...)>::operator=(const function& __f)
1112 {
1113     function(__f).swap(*this);
1114     return *this;
1115 }
1116 
1117 template<class _Rp, class ..._ArgTypes>
1118 function<_Rp(_ArgTypes...)>&
1119 function<_Rp(_ArgTypes...)>::operator=(function&& __f) _NOEXCEPT
1120 {
1121     __f_ = _VSTD::move(__f.__f_);
1122     return *this;
1123 }
1124 
1125 template<class _Rp, class ..._ArgTypes>
1126 function<_Rp(_ArgTypes...)>&
1127 function<_Rp(_ArgTypes...)>::operator=(nullptr_t) _NOEXCEPT
1128 {
1129     __f_ = nullptr;
1130     return *this;
1131 }
1132 
1133 template<class _Rp, class ..._ArgTypes>
1134 template <class _Fp, class>
1135 function<_Rp(_ArgTypes...)>&
1136 function<_Rp(_ArgTypes...)>::operator=(_Fp&& __f)
1137 {
1138     function(_VSTD::forward<_Fp>(__f)).swap(*this);
1139     return *this;
1140 }
1141 
1142 template<class _Rp, class ..._ArgTypes>
1143 function<_Rp(_ArgTypes...)>::~function() {}
1144 
1145 template<class _Rp, class ..._ArgTypes>
1146 void
1147 function<_Rp(_ArgTypes...)>::swap(function& __f) _NOEXCEPT
1148 {
1149     __f_.swap(__f.__f_);
1150 }
1151 
1152 template<class _Rp, class ..._ArgTypes>
1153 _Rp
1154 function<_Rp(_ArgTypes...)>::operator()(_ArgTypes... __arg) const
1155 {
1156     return __f_(_VSTD::forward<_ArgTypes>(__arg)...);
1157 }
1158 
1159 #ifndef _LIBCPP_HAS_NO_RTTI
1160 
1161 template<class _Rp, class ..._ArgTypes>
1162 const std::type_info&
1163 function<_Rp(_ArgTypes...)>::target_type() const _NOEXCEPT
1164 {
1165     return __f_.target_type();
1166 }
1167 
1168 template<class _Rp, class ..._ArgTypes>
1169 template <typename _Tp>
1170 _Tp*
1171 function<_Rp(_ArgTypes...)>::target() _NOEXCEPT
1172 {
1173     return (_Tp*)(__f_.template target<_Tp>());
1174 }
1175 
1176 template<class _Rp, class ..._ArgTypes>
1177 template <typename _Tp>
1178 const _Tp*
1179 function<_Rp(_ArgTypes...)>::target() const _NOEXCEPT
1180 {
1181     return __f_.template target<_Tp>();
1182 }
1183 
1184 #endif // _LIBCPP_HAS_NO_RTTI
1185 
1186 template <class _Rp, class... _ArgTypes>
1187 inline _LIBCPP_INLINE_VISIBILITY
1188 bool
1189 operator==(const function<_Rp(_ArgTypes...)>& __f, nullptr_t) _NOEXCEPT {return !__f;}
1190 
1191 template <class _Rp, class... _ArgTypes>
1192 inline _LIBCPP_INLINE_VISIBILITY
1193 bool
1194 operator==(nullptr_t, const function<_Rp(_ArgTypes...)>& __f) _NOEXCEPT {return !__f;}
1195 
1196 template <class _Rp, class... _ArgTypes>
1197 inline _LIBCPP_INLINE_VISIBILITY
1198 bool
1199 operator!=(const function<_Rp(_ArgTypes...)>& __f, nullptr_t) _NOEXCEPT {return (bool)__f;}
1200 
1201 template <class _Rp, class... _ArgTypes>
1202 inline _LIBCPP_INLINE_VISIBILITY
1203 bool
1204 operator!=(nullptr_t, const function<_Rp(_ArgTypes...)>& __f) _NOEXCEPT {return (bool)__f;}
1205 
1206 template <class _Rp, class... _ArgTypes>
1207 inline _LIBCPP_INLINE_VISIBILITY
1208 void
1209 swap(function<_Rp(_ArgTypes...)>& __x, function<_Rp(_ArgTypes...)>& __y) _NOEXCEPT
1210 {return __x.swap(__y);}
1211 
1212 _LIBCPP_END_NAMESPACE_STD
1213 
1214 #endif // _LIBCPP_CXX03_LANG
1215 
1216 #endif // _LIBCPP___FUNCTIONAL_FUNCTION_H
1217