// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP_ANY
#define _LIBCPP_ANY

/*
   any synopsis

namespace std {

  class bad_any_cast : public bad_cast
  {
  public:
    virtual const char* what() const noexcept;
  };

  class any
  {
  public:

    // 6.3.1 any construct/destruct
    any() noexcept;

    any(const any& other);
    any(any&& other) noexcept;

    template <class ValueType>
      any(ValueType&& value);

    ~any();

    // 6.3.2 any assignments
    any& operator=(const any& rhs);
    any& operator=(any&& rhs) noexcept;

    template <class ValueType>
      any& operator=(ValueType&& rhs);

    // 6.3.3 any modifiers
    template <class ValueType, class... Args>
      decay_t<ValueType>& emplace(Args&&... args);
    template <class ValueType, class U, class... Args>
      decay_t<ValueType>& emplace(initializer_list<U>, Args&&...);
    void reset() noexcept;
    void swap(any& rhs) noexcept;

    // 6.3.4 any observers
    bool has_value() const noexcept;
    const type_info& type() const noexcept;
  };

   // 6.4 Non-member functions
  void swap(any& x, any& y) noexcept;

  template <class T, class ...Args>
    any make_any(Args&& ...args);
  template <class T, class U, class ...Args>
    any make_any(initializer_list<U>, Args&& ...args);

  template<class ValueType>
    ValueType any_cast(const any& operand);
  template<class ValueType>
    ValueType any_cast(any& operand);
  template<class ValueType>
    ValueType any_cast(any&& operand);

  template<class ValueType>
    const ValueType* any_cast(const any* operand) noexcept;
  template<class ValueType>
    ValueType* any_cast(any* operand) noexcept;

} // namespace std

*/

#include <__assert> // all public C++ headers provide the assertion handler
#include <__availability>
#include <__config>
#include <__memory/allocator.h>
#include <__memory/allocator_destructor.h>
#include <__memory/allocator_traits.h>
#include <__memory/unique_ptr.h>
#include <__type_traits/add_const.h>
#include <__type_traits/add_pointer.h>
#include <__type_traits/aligned_storage.h>
#include <__type_traits/alignment_of.h>
#include <__type_traits/conditional.h>
#include <__type_traits/decay.h>
#include <__type_traits/is_constructible.h>
#include <__type_traits/is_copy_constructible.h>
#include <__type_traits/is_function.h>
#include <__type_traits/is_nothrow_move_constructible.h>
#include <__type_traits/is_reference.h>
#include <__type_traits/is_same.h>
#include <__type_traits/remove_cv.h>
#include <__type_traits/remove_cvref.h>
#include <__type_traits/remove_reference.h>
#include <__utility/forward.h>
#include <__utility/in_place.h>
#include <__utility/move.h>
#include <__utility/unreachable.h>
#include <__verbose_abort>
#include <initializer_list>
#include <typeinfo>
#include <version>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#  pragma GCC system_header
#endif

namespace std {
class _LIBCPP_EXPORTED_FROM_ABI _LIBCPP_AVAILABILITY_BAD_ANY_CAST bad_any_cast : public bad_cast
{
public:
    const char* what() const _NOEXCEPT override;
};
} // namespace std

_LIBCPP_BEGIN_NAMESPACE_STD

#if _LIBCPP_STD_VER >= 17

_LIBCPP_NORETURN inline _LIBCPP_INLINE_VISIBILITY
_LIBCPP_AVAILABILITY_THROW_BAD_ANY_CAST
void __throw_bad_any_cast()
{
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
    throw bad_any_cast();
#else
    _LIBCPP_VERBOSE_ABORT("bad_any_cast was thrown in -fno-exceptions mode");
#endif
}

// Forward declarations
class _LIBCPP_TEMPLATE_VIS any;

template <class _ValueType>
_LIBCPP_INLINE_VISIBILITY
add_pointer_t<add_const_t<_ValueType>>
any_cast(any const *) _NOEXCEPT;

template <class _ValueType>
_LIBCPP_INLINE_VISIBILITY
add_pointer_t<_ValueType> any_cast(any *) _NOEXCEPT;

namespace __any_imp
{
  _LIBCPP_SUPPRESS_DEPRECATED_PUSH
  using _Buffer = aligned_storage_t<3*sizeof(void*), alignment_of<void*>::value>;
  _LIBCPP_SUPPRESS_DEPRECATED_POP

  template <class _Tp>
  using _IsSmallObject = integral_constant<bool
        , sizeof(_Tp) <= sizeof(_Buffer)
          && alignment_of<_Buffer>::value
             % alignment_of<_Tp>::value == 0
          && is_nothrow_move_constructible<_Tp>::value
        >;

  enum class _Action {
    _Destroy,
    _Copy,
    _Move,
    _Get,
    _TypeInfo
  };

  template <class _Tp> struct _SmallHandler;
  template <class _Tp> struct _LargeHandler;

  template <class _Tp>
  struct  _LIBCPP_TEMPLATE_VIS __unique_typeinfo { static constexpr int __id = 0; };
  template <class _Tp> constexpr int __unique_typeinfo<_Tp>::__id;

  template <class _Tp>
  inline _LIBCPP_INLINE_VISIBILITY
  constexpr const void* __get_fallback_typeid() {
      return &__unique_typeinfo<remove_cv_t<remove_reference_t<_Tp>>>::__id;
  }

  template <class _Tp>
  inline _LIBCPP_INLINE_VISIBILITY
  bool __compare_typeid(type_info const* __id, const void* __fallback_id)
  {
#if !defined(_LIBCPP_HAS_NO_RTTI)
      if (__id && *__id == typeid(_Tp))
          return true;
#endif
      if (!__id && __fallback_id == __any_imp::__get_fallback_typeid<_Tp>())
          return true;
      return false;
  }

  template <class _Tp>
  using _Handler = conditional_t<
    _IsSmallObject<_Tp>::value, _SmallHandler<_Tp>, _LargeHandler<_Tp>>;

} // namespace __any_imp

class _LIBCPP_TEMPLATE_VIS any
{
public:
  // construct/destruct
  _LIBCPP_INLINE_VISIBILITY
  constexpr any() _NOEXCEPT : __h_(nullptr) {}

  _LIBCPP_INLINE_VISIBILITY
  any(any const & __other) : __h_(nullptr)
  {
    if (__other.__h_) __other.__call(_Action::_Copy, this);
  }

  _LIBCPP_INLINE_VISIBILITY
  any(any && __other) _NOEXCEPT : __h_(nullptr)
  {
    if (__other.__h_) __other.__call(_Action::_Move, this);
  }

  template <
      class _ValueType
    , class _Tp = decay_t<_ValueType>
    , class = enable_if_t<
        !is_same<_Tp, any>::value &&
        !__is_inplace_type<_ValueType>::value &&
        is_copy_constructible<_Tp>::value>
    >
  _LIBCPP_INLINE_VISIBILITY
  any(_ValueType && __value);

  template <class _ValueType, class ..._Args,
    class _Tp = decay_t<_ValueType>,
    class = enable_if_t<
        is_constructible<_Tp, _Args...>::value &&
        is_copy_constructible<_Tp>::value
    >
  >
  _LIBCPP_INLINE_VISIBILITY
  explicit any(in_place_type_t<_ValueType>, _Args&&... __args);

  template <class _ValueType, class _Up, class ..._Args,
    class _Tp = decay_t<_ValueType>,
    class = enable_if_t<
        is_constructible<_Tp, initializer_list<_Up>&, _Args...>::value &&
        is_copy_constructible<_Tp>::value>
  >
  _LIBCPP_INLINE_VISIBILITY
  explicit any(in_place_type_t<_ValueType>, initializer_list<_Up>, _Args&&... __args);

  _LIBCPP_INLINE_VISIBILITY
  ~any() { this->reset(); }

  // assignments
  _LIBCPP_INLINE_VISIBILITY
  any & operator=(any const & __rhs) {
    any(__rhs).swap(*this);
    return *this;
  }

  _LIBCPP_INLINE_VISIBILITY
  any & operator=(any && __rhs) _NOEXCEPT {
    any(_VSTD::move(__rhs)).swap(*this);
    return *this;
  }

  template <
      class _ValueType
    , class _Tp = decay_t<_ValueType>
    , class = enable_if_t<
          !is_same<_Tp, any>::value
          && is_copy_constructible<_Tp>::value>
    >
  _LIBCPP_INLINE_VISIBILITY
  any & operator=(_ValueType && __rhs);

  template <class _ValueType, class ..._Args,
    class _Tp = decay_t<_ValueType>,
    class = enable_if_t<
        is_constructible<_Tp, _Args...>::value &&
        is_copy_constructible<_Tp>::value>
    >
  _LIBCPP_INLINE_VISIBILITY
  _Tp& emplace(_Args&&...);

  template <class _ValueType, class _Up, class ..._Args,
    class _Tp = decay_t<_ValueType>,
    class = enable_if_t<
        is_constructible<_Tp, initializer_list<_Up>&, _Args...>::value &&
        is_copy_constructible<_Tp>::value>
  >
  _LIBCPP_INLINE_VISIBILITY
  _Tp& emplace(initializer_list<_Up>, _Args&&...);

  // 6.3.3 any modifiers
  _LIBCPP_INLINE_VISIBILITY
  void reset() _NOEXCEPT { if (__h_) this->__call(_Action::_Destroy); }

  _LIBCPP_INLINE_VISIBILITY
  void swap(any & __rhs) _NOEXCEPT;

  // 6.3.4 any observers
  _LIBCPP_INLINE_VISIBILITY
  bool has_value() const _NOEXCEPT { return __h_ != nullptr; }

#if !defined(_LIBCPP_HAS_NO_RTTI)
  _LIBCPP_INLINE_VISIBILITY
  const type_info & type() const _NOEXCEPT {
    if (__h_) {
        return *static_cast<type_info const *>(this->__call(_Action::_TypeInfo));
    } else {
        return typeid(void);
    }
  }
#endif

private:
    typedef __any_imp::_Action _Action;
    using _HandleFuncPtr =  void* (*)(_Action, any const *, any *, const type_info *,
      const void* __fallback_info);

    union _Storage {
        _LIBCPP_HIDE_FROM_ABI constexpr _Storage() : __ptr(nullptr) {}
        void *  __ptr;
        __any_imp::_Buffer __buf;
    };

    _LIBCPP_INLINE_VISIBILITY
    void * __call(_Action __a, any * __other = nullptr,
                  type_info const * __info = nullptr,
                   const void* __fallback_info = nullptr) const
    {
        return __h_(__a, this, __other, __info, __fallback_info);
    }

    _LIBCPP_INLINE_VISIBILITY
    void * __call(_Action __a, any * __other = nullptr,
                  type_info const * __info = nullptr,
                  const void* __fallback_info = nullptr)
    {
        return __h_(__a, this, __other, __info, __fallback_info);
    }

    template <class>
    friend struct __any_imp::_SmallHandler;
    template <class>
    friend struct __any_imp::_LargeHandler;

    template <class _ValueType>
    friend add_pointer_t<add_const_t<_ValueType>>
    any_cast(any const *) _NOEXCEPT;

    template <class _ValueType>
    friend add_pointer_t<_ValueType>
    any_cast(any *) _NOEXCEPT;

    _HandleFuncPtr __h_ = nullptr;
    _Storage __s_;
};

namespace __any_imp
{
  template <class _Tp>
  struct _LIBCPP_TEMPLATE_VIS _SmallHandler
  {
     _LIBCPP_INLINE_VISIBILITY
     static void* __handle(_Action __act, any const * __this, any * __other,
                           type_info const * __info, const void* __fallback_info)
     {
        switch (__act)
        {
        case _Action::_Destroy:
          __destroy(const_cast<any &>(*__this));
          return nullptr;
        case _Action::_Copy:
            __copy(*__this, *__other);
            return nullptr;
        case _Action::_Move:
          __move(const_cast<any &>(*__this), *__other);
          return nullptr;
        case _Action::_Get:
            return __get(const_cast<any &>(*__this), __info, __fallback_info);
        case _Action::_TypeInfo:
          return __type_info();
        }
        __libcpp_unreachable();
    }

    template <class ..._Args>
    _LIBCPP_INLINE_VISIBILITY
    static _Tp& __create(any & __dest, _Args&&... __args) {
        typedef allocator<_Tp> _Alloc;
        typedef allocator_traits<_Alloc> _ATraits;
        _Alloc __a;
        _Tp * __ret = static_cast<_Tp*>(static_cast<void*>(&__dest.__s_.__buf));
        _ATraits::construct(__a, __ret, _VSTD::forward<_Args>(__args)...);
        __dest.__h_ = &_SmallHandler::__handle;
        return *__ret;
    }

  private:
    _LIBCPP_INLINE_VISIBILITY
    static void __destroy(any & __this) {
        typedef allocator<_Tp> _Alloc;
        typedef allocator_traits<_Alloc> _ATraits;
        _Alloc __a;
        _Tp * __p = static_cast<_Tp *>(static_cast<void*>(&__this.__s_.__buf));
        _ATraits::destroy(__a, __p);
        __this.__h_ = nullptr;
    }

    _LIBCPP_INLINE_VISIBILITY
    static void __copy(any const & __this, any & __dest) {
        _SmallHandler::__create(__dest, *static_cast<_Tp const *>(
            static_cast<void const *>(&__this.__s_.__buf)));
    }

    _LIBCPP_INLINE_VISIBILITY
    static void __move(any & __this, any & __dest) {
        _SmallHandler::__create(__dest, _VSTD::move(
            *static_cast<_Tp*>(static_cast<void*>(&__this.__s_.__buf))));
        __destroy(__this);
    }

    _LIBCPP_INLINE_VISIBILITY
    static void* __get(any & __this,
                       type_info const * __info,
                       const void* __fallback_id)
    {
        if (__any_imp::__compare_typeid<_Tp>(__info, __fallback_id))
            return static_cast<void*>(&__this.__s_.__buf);
        return nullptr;
    }

    _LIBCPP_INLINE_VISIBILITY
    static void* __type_info()
    {
#if !defined(_LIBCPP_HAS_NO_RTTI)
        return const_cast<void*>(static_cast<void const *>(&typeid(_Tp)));
#else
        return nullptr;
#endif
    }
  };

  template <class _Tp>
  struct _LIBCPP_TEMPLATE_VIS _LargeHandler
  {
    _LIBCPP_INLINE_VISIBILITY
    static void* __handle(_Action __act, any const * __this,
                          any * __other, type_info const * __info,
                          void const* __fallback_info)
    {
        switch (__act)
        {
        case _Action::_Destroy:
          __destroy(const_cast<any &>(*__this));
          return nullptr;
        case _Action::_Copy:
          __copy(*__this, *__other);
          return nullptr;
        case _Action::_Move:
          __move(const_cast<any &>(*__this), *__other);
          return nullptr;
        case _Action::_Get:
            return __get(const_cast<any &>(*__this), __info, __fallback_info);
        case _Action::_TypeInfo:
          return __type_info();
        }
        __libcpp_unreachable();
    }

    template <class ..._Args>
    _LIBCPP_INLINE_VISIBILITY
    static _Tp& __create(any & __dest, _Args&&... __args) {
        typedef allocator<_Tp> _Alloc;
        typedef allocator_traits<_Alloc> _ATraits;
        typedef __allocator_destructor<_Alloc> _Dp;
        _Alloc __a;
        unique_ptr<_Tp, _Dp> __hold(_ATraits::allocate(__a, 1), _Dp(__a, 1));
        _Tp * __ret = __hold.get();
        _ATraits::construct(__a, __ret, _VSTD::forward<_Args>(__args)...);
        __dest.__s_.__ptr = __hold.release();
        __dest.__h_ = &_LargeHandler::__handle;
        return *__ret;
    }

  private:

    _LIBCPP_INLINE_VISIBILITY
    static void __destroy(any & __this){
        typedef allocator<_Tp> _Alloc;
        typedef allocator_traits<_Alloc> _ATraits;
        _Alloc __a;
        _Tp * __p = static_cast<_Tp *>(__this.__s_.__ptr);
        _ATraits::destroy(__a, __p);
        _ATraits::deallocate(__a, __p, 1);
        __this.__h_ = nullptr;
    }

    _LIBCPP_INLINE_VISIBILITY
    static void __copy(any const & __this, any & __dest) {
        _LargeHandler::__create(__dest, *static_cast<_Tp const *>(__this.__s_.__ptr));
    }

    _LIBCPP_INLINE_VISIBILITY
    static void __move(any & __this, any & __dest) {
      __dest.__s_.__ptr = __this.__s_.__ptr;
      __dest.__h_ = &_LargeHandler::__handle;
      __this.__h_ = nullptr;
    }

    _LIBCPP_INLINE_VISIBILITY
    static void* __get(any & __this, type_info const * __info,
                       void const* __fallback_info)
    {
        if (__any_imp::__compare_typeid<_Tp>(__info, __fallback_info))
            return static_cast<void*>(__this.__s_.__ptr);
        return nullptr;

    }

    _LIBCPP_INLINE_VISIBILITY
    static void* __type_info()
    {
#if !defined(_LIBCPP_HAS_NO_RTTI)
        return const_cast<void*>(static_cast<void const *>(&typeid(_Tp)));
#else
        return nullptr;
#endif
    }
  };

} // namespace __any_imp


template <class _ValueType, class _Tp, class>
any::any(_ValueType && __v) : __h_(nullptr)
{
  __any_imp::_Handler<_Tp>::__create(*this, _VSTD::forward<_ValueType>(__v));
}

template <class _ValueType, class ..._Args, class _Tp, class>
any::any(in_place_type_t<_ValueType>, _Args&&... __args) {
  __any_imp::_Handler<_Tp>::__create(*this, _VSTD::forward<_Args>(__args)...);
}

template <class _ValueType, class _Up, class ..._Args, class _Tp, class>
any::any(in_place_type_t<_ValueType>, initializer_list<_Up> __il, _Args&&... __args) {
  __any_imp::_Handler<_Tp>::__create(*this, __il, _VSTD::forward<_Args>(__args)...);
}

template <class _ValueType, class, class>
inline _LIBCPP_INLINE_VISIBILITY
any & any::operator=(_ValueType && __v)
{
  any(_VSTD::forward<_ValueType>(__v)).swap(*this);
  return *this;
}

template <class _ValueType, class ..._Args, class _Tp, class>
inline _LIBCPP_INLINE_VISIBILITY
_Tp& any::emplace(_Args&&... __args) {
  reset();
  return __any_imp::_Handler<_Tp>::__create(*this, _VSTD::forward<_Args>(__args)...);
}

template <class _ValueType, class _Up, class ..._Args, class _Tp, class>
inline _LIBCPP_INLINE_VISIBILITY
_Tp& any::emplace(initializer_list<_Up> __il, _Args&&... __args) {
  reset();
  return __any_imp::_Handler<_Tp>::__create(*this, __il, _VSTD::forward<_Args>(__args)...);
}

inline _LIBCPP_INLINE_VISIBILITY
void any::swap(any & __rhs) _NOEXCEPT
{
    if (this == &__rhs)
      return;
    if (__h_ && __rhs.__h_) {
        any __tmp;
        __rhs.__call(_Action::_Move, &__tmp);
        this->__call(_Action::_Move, &__rhs);
        __tmp.__call(_Action::_Move, this);
    }
    else if (__h_) {
        this->__call(_Action::_Move, &__rhs);
    }
    else if (__rhs.__h_) {
        __rhs.__call(_Action::_Move, this);
    }
}

// 6.4 Non-member functions

inline _LIBCPP_INLINE_VISIBILITY
void swap(any & __lhs, any & __rhs) _NOEXCEPT
{
    __lhs.swap(__rhs);
}

template <class _Tp, class ..._Args>
inline _LIBCPP_INLINE_VISIBILITY
any make_any(_Args&&... __args) {
    return any(in_place_type<_Tp>, _VSTD::forward<_Args>(__args)...);
}

template <class _Tp, class _Up, class ..._Args>
inline _LIBCPP_INLINE_VISIBILITY
any make_any(initializer_list<_Up> __il, _Args&&... __args) {
    return any(in_place_type<_Tp>, __il, _VSTD::forward<_Args>(__args)...);
}

template <class _ValueType>
inline _LIBCPP_INLINE_VISIBILITY
_LIBCPP_AVAILABILITY_THROW_BAD_ANY_CAST
_ValueType any_cast(any const & __v)
{
    using _RawValueType = __remove_cvref_t<_ValueType>;
    static_assert(is_constructible<_ValueType, _RawValueType const &>::value,
                  "ValueType is required to be a const lvalue reference "
                  "or a CopyConstructible type");
    auto __tmp = _VSTD::any_cast<add_const_t<_RawValueType>>(&__v);
    if (__tmp == nullptr)
        __throw_bad_any_cast();
    return static_cast<_ValueType>(*__tmp);
}

template <class _ValueType>
inline _LIBCPP_INLINE_VISIBILITY
_LIBCPP_AVAILABILITY_THROW_BAD_ANY_CAST
_ValueType any_cast(any & __v)
{
    using _RawValueType = __remove_cvref_t<_ValueType>;
    static_assert(is_constructible<_ValueType, _RawValueType &>::value,
                  "ValueType is required to be an lvalue reference "
                  "or a CopyConstructible type");
    auto __tmp = _VSTD::any_cast<_RawValueType>(&__v);
    if (__tmp == nullptr)
        __throw_bad_any_cast();
    return static_cast<_ValueType>(*__tmp);
}

template <class _ValueType>
inline _LIBCPP_INLINE_VISIBILITY
_LIBCPP_AVAILABILITY_THROW_BAD_ANY_CAST
_ValueType any_cast(any && __v)
{
    using _RawValueType = __remove_cvref_t<_ValueType>;
    static_assert(is_constructible<_ValueType, _RawValueType>::value,
                  "ValueType is required to be an rvalue reference "
                  "or a CopyConstructible type");
    auto __tmp = _VSTD::any_cast<_RawValueType>(&__v);
    if (__tmp == nullptr)
        __throw_bad_any_cast();
    return static_cast<_ValueType>(_VSTD::move(*__tmp));
}

template <class _ValueType>
inline _LIBCPP_INLINE_VISIBILITY
add_pointer_t<add_const_t<_ValueType>>
any_cast(any const * __any) _NOEXCEPT
{
    static_assert(!is_reference<_ValueType>::value,
                  "_ValueType may not be a reference.");
    return _VSTD::any_cast<_ValueType>(const_cast<any *>(__any));
}

template <class _RetType>
inline _LIBCPP_INLINE_VISIBILITY
_RetType __pointer_or_func_cast(void* __p, /*IsFunction*/false_type) noexcept {
  return static_cast<_RetType>(__p);
}

template <class _RetType>
inline _LIBCPP_INLINE_VISIBILITY
_RetType __pointer_or_func_cast(void*, /*IsFunction*/true_type) noexcept {
  return nullptr;
}

template <class _ValueType>
_LIBCPP_HIDE_FROM_ABI
add_pointer_t<_ValueType>
any_cast(any * __any) _NOEXCEPT
{
    using __any_imp::_Action;
    static_assert(!is_reference<_ValueType>::value,
                  "_ValueType may not be a reference.");
    typedef add_pointer_t<_ValueType> _ReturnType;
    if (__any && __any->__h_) {
      void *__p = __any->__call(_Action::_Get, nullptr,
#if !defined(_LIBCPP_HAS_NO_RTTI)
                          &typeid(_ValueType),
#else
                          nullptr,
#endif
                          __any_imp::__get_fallback_typeid<_ValueType>());
        return _VSTD::__pointer_or_func_cast<_ReturnType>(
            __p, is_function<_ValueType>{});
    }
    return nullptr;
}

#endif // _LIBCPP_STD_VER >= 17

_LIBCPP_END_NAMESPACE_STD

#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 17
#  include <chrono>
#endif

#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
#  include <atomic>
#  include <concepts>
#  include <cstdlib>
#  include <iosfwd>
#  include <iterator>
#  include <memory>
#  include <stdexcept>
#  include <type_traits>
#  include <variant>
#endif

#endif // _LIBCPP_ANY
