// -*- 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_TYPEINFO
#define _LIBCPP_TYPEINFO

/*

    typeinfo synopsis

namespace std {

class type_info
{
public:
    virtual ~type_info();

    bool operator==(const type_info& rhs) const noexcept; // constexpr since C++23
    bool operator!=(const type_info& rhs) const noexcept; // removed in C++20

    bool before(const type_info& rhs) const noexcept;
    size_t hash_code() const noexcept;
    const char* name() const noexcept;

    type_info(const type_info& rhs) = delete;
    type_info& operator=(const type_info& rhs) = delete;
};

class bad_cast
    : public exception
{
public:
    bad_cast() noexcept;
    bad_cast(const bad_cast&) noexcept;
    bad_cast& operator=(const bad_cast&) noexcept;
    virtual const char* what() const noexcept;
};

class bad_typeid
    : public exception
{
public:
    bad_typeid() noexcept;
    bad_typeid(const bad_typeid&) noexcept;
    bad_typeid& operator=(const bad_typeid&) noexcept;
    virtual const char* what() const noexcept;
};

}  // std

*/

#include <__config>
#include <__exception/exception.h>
#include <__type_traits/is_constant_evaluated.h>
#include <__verbose_abort>
#include <cstddef>
#include <cstdint>

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

#if defined(_LIBCPP_ABI_VCRUNTIME)
#  include <vcruntime_typeinfo.h>
#else

namespace std // purposefully not using versioning namespace
{

#  if defined(_LIBCPP_ABI_MICROSOFT)

class _LIBCPP_EXPORTED_FROM_ABI type_info {
  type_info& operator=(const type_info&);
  type_info(const type_info&);

  mutable struct {
    const char* __undecorated_name;
    const char __decorated_name[1];
  } __data;

  int __compare(const type_info& __rhs) const _NOEXCEPT;

public:
  virtual ~type_info();

  const char* name() const _NOEXCEPT;

  _LIBCPP_HIDE_FROM_ABI bool before(const type_info& __arg) const _NOEXCEPT { return __compare(__arg) < 0; }

  size_t hash_code() const _NOEXCEPT;

  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool operator==(const type_info& __arg) const _NOEXCEPT {
    // When evaluated in a constant expression, both type infos simply can't come
    // from different translation units, so it is sufficient to compare their addresses.
    if (__libcpp_is_constant_evaluated()) {
      return this == &__arg;
    }
    return __compare(__arg) == 0;
  }

#    if _LIBCPP_STD_VER <= 17
  _LIBCPP_HIDE_FROM_ABI bool operator!=(const type_info& __arg) const _NOEXCEPT { return !operator==(__arg); }
#    endif
};

#  else // !defined(_LIBCPP_ABI_MICROSOFT)

// ========================================================================== //
//                           Implementations
// ========================================================================== //
// ------------------------------------------------------------------------- //
//                               Unique
//               (_LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION = 1)
// ------------------------------------------------------------------------- //
// This implementation of type_info assumes a unique copy of the RTTI for a
// given type inside a program. This is a valid assumption when abiding to the
// Itanium ABI (http://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-components).
// Under this assumption, we can always compare the addresses of the type names
// to implement equality-comparison of type_infos instead of having to perform
// a deep string comparison.
// -------------------------------------------------------------------------- //
//                             NonUnique
//               (_LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION = 2)
// -------------------------------------------------------------------------- //
// This implementation of type_info does not assume there is always a unique
// copy of the RTTI for a given type inside a program. For various reasons
// the linker may have failed to merge every copy of a types RTTI
// (For example: -Bsymbolic or llvm.org/PR37398). Under this assumption, two
// type_infos are equal if their addresses are equal or if a deep string
// comparison is equal.
// -------------------------------------------------------------------------- //
//                          NonUniqueARMRTTIBit
//               (_LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION = 3)
// -------------------------------------------------------------------------- //
// This implementation is specific to ARM64 on Apple platforms.
//
// This implementation of type_info does not assume always a unique copy of
// the RTTI for a given type inside a program. When constructing the type_info,
// the compiler packs the pointer to the type name into a uintptr_t and reserves
// the high bit of that pointer, which is assumed to be free for use under that
// ABI. If that high bit is set, that specific copy of the RTTI can't be assumed
// to be unique within the program. If the high bit is unset, then the RTTI can
// be assumed to be unique within the program.
//
// When comparing type_infos, if both RTTIs can be assumed to be unique, it
// suffices to compare their addresses. If both the RTTIs can't be assumed to
// be unique, we must perform a deep string comparison of the type names.
// However, if one of the RTTIs is guaranteed unique and the other one isn't,
// then both RTTIs are necessarily not to be considered equal.
//
// The intent of this design is to remove the need for weak symbols. Specifically,
// if a type would normally have a default-visibility RTTI emitted as a weak
// symbol, it is given hidden visibility instead and the non-unique bit is set.
// Otherwise, types declared with hidden visibility are always considered to have
// a unique RTTI: the RTTI is emitted with linkonce_odr linkage and is assumed
// to be deduplicated by the linker within the linked image. Across linked image
// boundaries, such types are thus considered different types.

// This value can be overriden in the __config_site. When it's not overriden,
// we pick a default implementation based on the platform here.
#    ifndef _LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION

// Windows and AIX binaries can't merge typeinfos, so use the NonUnique implementation.
#      if defined(_LIBCPP_OBJECT_FORMAT_COFF) || defined(_LIBCPP_OBJECT_FORMAT_XCOFF)
#        define _LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION 2

// On arm64 on Apple platforms, use the special NonUniqueARMRTTIBit implementation.
#      elif defined(__APPLE__) && defined(__LP64__) && !defined(__x86_64__)
#        define _LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION 3

// On all other platforms, assume the Itanium C++ ABI and use the Unique implementation.
#      else
#        define _LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION 1
#      endif
#    endif

struct __type_info_implementations {
  struct __string_impl_base {
    typedef const char* __type_name_t;
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_ALWAYS_INLINE _LIBCPP_CONSTEXPR static const char*
    __type_name_to_string(__type_name_t __v) _NOEXCEPT {
      return __v;
    }
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_ALWAYS_INLINE _LIBCPP_CONSTEXPR static __type_name_t
    __string_to_type_name(const char* __v) _NOEXCEPT {
      return __v;
    }
  };

  struct __unique_impl : __string_impl_base {
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_ALWAYS_INLINE static size_t __hash(__type_name_t __v) _NOEXCEPT {
      return reinterpret_cast<size_t>(__v);
    }
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_ALWAYS_INLINE static bool __eq(__type_name_t __lhs, __type_name_t __rhs) _NOEXCEPT {
      return __lhs == __rhs;
    }
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_ALWAYS_INLINE static bool __lt(__type_name_t __lhs, __type_name_t __rhs) _NOEXCEPT {
      return __lhs < __rhs;
    }
  };

  struct __non_unique_impl : __string_impl_base {
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_ALWAYS_INLINE static size_t __hash(__type_name_t __ptr) _NOEXCEPT {
      size_t __hash = 5381;
      while (unsigned char __c = static_cast<unsigned char>(*__ptr++))
        __hash = (__hash * 33) ^ __c;
      return __hash;
    }
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_ALWAYS_INLINE static bool __eq(__type_name_t __lhs, __type_name_t __rhs) _NOEXCEPT {
      return __lhs == __rhs || __builtin_strcmp(__lhs, __rhs) == 0;
    }
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_ALWAYS_INLINE static bool __lt(__type_name_t __lhs, __type_name_t __rhs) _NOEXCEPT {
      return __builtin_strcmp(__lhs, __rhs) < 0;
    }
  };

  struct __non_unique_arm_rtti_bit_impl {
    typedef uintptr_t __type_name_t;

    _LIBCPP_HIDE_FROM_ABI _LIBCPP_ALWAYS_INLINE static const char* __type_name_to_string(__type_name_t __v) _NOEXCEPT {
      return reinterpret_cast<const char*>(__v & ~__non_unique_rtti_bit::value);
    }
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_ALWAYS_INLINE static __type_name_t __string_to_type_name(const char* __v) _NOEXCEPT {
      return reinterpret_cast<__type_name_t>(__v);
    }

    _LIBCPP_HIDE_FROM_ABI _LIBCPP_ALWAYS_INLINE static size_t __hash(__type_name_t __v) _NOEXCEPT {
      if (__is_type_name_unique(__v))
        return __v;
      return __non_unique_impl::__hash(__type_name_to_string(__v));
    }
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_ALWAYS_INLINE static bool __eq(__type_name_t __lhs, __type_name_t __rhs) _NOEXCEPT {
      if (__lhs == __rhs)
        return true;
      if (__is_type_name_unique(__lhs) || __is_type_name_unique(__rhs))
        // Either both are unique and have a different address, or one of them
        // is unique and the other one isn't. In both cases they are unequal.
        return false;
      return __builtin_strcmp(__type_name_to_string(__lhs), __type_name_to_string(__rhs)) == 0;
    }
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_ALWAYS_INLINE static bool __lt(__type_name_t __lhs, __type_name_t __rhs) _NOEXCEPT {
      if (__is_type_name_unique(__lhs) || __is_type_name_unique(__rhs))
        return __lhs < __rhs;
      return __builtin_strcmp(__type_name_to_string(__lhs), __type_name_to_string(__rhs)) < 0;
    }

  private:
    // The unique bit is the top bit. It is expected that __type_name_t is 64 bits when
    // this implementation is actually used.
    typedef integral_constant<__type_name_t, (1ULL << ((__CHAR_BIT__ * sizeof(__type_name_t)) - 1))>
        __non_unique_rtti_bit;

    _LIBCPP_HIDE_FROM_ABI static bool __is_type_name_unique(__type_name_t __lhs) _NOEXCEPT {
      return !(__lhs & __non_unique_rtti_bit::value);
    }
  };

  typedef
#    if _LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION == 1
      __unique_impl
#    elif _LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION == 2
      __non_unique_impl
#    elif _LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION == 3
      __non_unique_arm_rtti_bit_impl
#    else
#      error invalid configuration for _LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION
#    endif
          __impl;
};

#    if defined(__arm64__) && __has_cpp_attribute(clang::ptrauth_vtable_pointer)
#      if __has_feature(ptrauth_type_info_discriminated_vtable_pointer)
#        define _LIBCPP_TYPE_INFO_VTABLE_POINTER_AUTH                                                                  \
          [[clang::ptrauth_vtable_pointer(process_independent, address_discrimination, type_discrimination)]]
#      else
#        define _LIBCPP_TYPE_INFO_VTABLE_POINTER_AUTH                                                                  \
          [[clang::ptrauth_vtable_pointer(process_independent, no_address_discrimination, no_extra_discrimination)]]
#      endif
#    else
#      define _LIBCPP_TYPE_INFO_VTABLE_POINTER_AUTH
#    endif

class _LIBCPP_EXPORTED_FROM_ABI _LIBCPP_TYPE_INFO_VTABLE_POINTER_AUTH type_info {
  type_info& operator=(const type_info&);
  type_info(const type_info&);

protected:
  typedef __type_info_implementations::__impl __impl;

  __impl::__type_name_t __type_name;

  _LIBCPP_HIDE_FROM_ABI explicit type_info(const char* __n) : __type_name(__impl::__string_to_type_name(__n)) {}

public:
  virtual ~type_info();

  _LIBCPP_HIDE_FROM_ABI const char* name() const _NOEXCEPT { return __impl::__type_name_to_string(__type_name); }

  _LIBCPP_HIDE_FROM_ABI bool before(const type_info& __arg) const _NOEXCEPT {
    return __impl::__lt(__type_name, __arg.__type_name);
  }

  _LIBCPP_HIDE_FROM_ABI size_t hash_code() const _NOEXCEPT { return __impl::__hash(__type_name); }

  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool operator==(const type_info& __arg) const _NOEXCEPT {
    // When evaluated in a constant expression, both type infos simply can't come
    // from different translation units, so it is sufficient to compare their addresses.
    if (__libcpp_is_constant_evaluated()) {
      return this == &__arg;
    }
    return __impl::__eq(__type_name, __arg.__type_name);
  }

#    if _LIBCPP_STD_VER <= 17
  _LIBCPP_HIDE_FROM_ABI bool operator!=(const type_info& __arg) const _NOEXCEPT { return !operator==(__arg); }
#    endif
};
#  endif // defined(_LIBCPP_ABI_MICROSOFT)

class _LIBCPP_EXPORTED_FROM_ABI bad_cast : public exception {
public:
  bad_cast() _NOEXCEPT;
  _LIBCPP_HIDE_FROM_ABI bad_cast(const bad_cast&) _NOEXCEPT            = default;
  _LIBCPP_HIDE_FROM_ABI bad_cast& operator=(const bad_cast&) _NOEXCEPT = default;
  ~bad_cast() _NOEXCEPT override;
  const char* what() const _NOEXCEPT override;
};

class _LIBCPP_EXPORTED_FROM_ABI bad_typeid : public exception {
public:
  bad_typeid() _NOEXCEPT;
  _LIBCPP_HIDE_FROM_ABI bad_typeid(const bad_typeid&) _NOEXCEPT            = default;
  _LIBCPP_HIDE_FROM_ABI bad_typeid& operator=(const bad_typeid&) _NOEXCEPT = default;
  ~bad_typeid() _NOEXCEPT override;
  const char* what() const _NOEXCEPT override;
};

} // namespace std

#endif // defined(_LIBCPP_ABI_VCRUNTIME)

#if defined(_LIBCPP_ABI_VCRUNTIME) && _HAS_EXCEPTIONS == 0

namespace std {

class bad_cast : public exception {
public:
  bad_cast() _NOEXCEPT : exception("bad cast") {}

private:
  bad_cast(const char* const __message) _NOEXCEPT : exception(__message) {}
};

class bad_typeid : public exception {
public:
  bad_typeid() _NOEXCEPT : exception("bad typeid") {}

private:
  bad_typeid(const char* const __message) _NOEXCEPT : exception(__message) {}
};

} // namespace std

#endif // defined(_LIBCPP_ABI_VCRUNTIME) && _HAS_EXCEPTIONS == 0

_LIBCPP_BEGIN_NAMESPACE_STD
_LIBCPP_NORETURN inline _LIBCPP_HIDE_FROM_ABI void __throw_bad_cast() {
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
  throw bad_cast();
#else
  _LIBCPP_VERBOSE_ABORT("bad_cast was thrown in -fno-exceptions mode");
#endif
}
_LIBCPP_END_NAMESPACE_STD

#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
#  include <cstdlib>
#  include <type_traits>
#endif

#endif // _LIBCPP_TYPEINFO