// <experimental/internet> -*- C++ -*-

// Copyright (C) 2015-2021 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file experimental/internet
 *  This is a TS C++ Library header.
 *  @ingroup networking-ts
 */

#ifndef _GLIBCXX_EXPERIMENTAL_INTERNET
#define _GLIBCXX_EXPERIMENTAL_INTERNET

#pragma GCC system_header

#if __cplusplus >= 201402L

#include <experimental/netfwd>
#include <experimental/io_context>
#include <experimental/bits/net.h>
#include <array>
#include <forward_list>
#include <sstream>
#include <cstdint>
#include <experimental/string_view>
#ifdef _GLIBCXX_HAVE_UNISTD_H
# include <unistd.h>
#endif
#ifdef _GLIBCXX_HAVE_SYS_SOCKET_H
# include <sys/socket.h>	// AF_INET, AF_INET6, SOCK_DGRAM, SOCK_STREAM
#endif
#ifdef _GLIBCXX_HAVE_ARPA_INET_H
# include <arpa/inet.h>		// inet_ntop
#endif
#ifdef _GLIBCXX_HAVE_NETINET_IN_H
# include <netinet/in.h>	// IPPROTO_IP, IPPROTO_IPV6, in_addr, in6_addr
#endif
#ifdef _GLIBCXX_HAVE_NETINET_TCP_H
# include <netinet/tcp.h>	// TCP_NODELAY
#endif
#ifdef _GLIBCXX_HAVE_NETDB_H
# include <netdb.h>		// getaddrinfo etc.
#endif

#if defined _WIN32 && __has_include(<ws2tcpip.h>)
# include <ws2tcpip.h>
#endif

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
namespace experimental
{
namespace net
{
inline namespace v1
{
namespace ip
{
  /** @addtogroup networking-ts
   *  @{
   */

  /** Error codes for resolver errors.
   * @{
   */

  enum class resolver_errc : int {
#ifdef _GLIBCXX_HAVE_NETDB_H
    host_not_found = EAI_NONAME,
    host_not_found_try_again = EAI_AGAIN,
    service_not_found = EAI_SERVICE
#endif
  };

  /// Error category for resolver errors.
  inline const error_category& resolver_category() noexcept // TODO non-inline
  {
    struct __cat : error_category
    {
      const char* name() const noexcept { return "resolver"; }
      std::string message(int __e) const {
#ifdef _GLIBCXX_HAVE_NETDB_H
	  return ::gai_strerror(__e);
#else
	  return "name resolution requires <netdb.h>";
#endif
      }
      virtual void __message(int) { } // TODO dual ABI XXX
    };
    static __cat __c;
    return __c;
  }

  inline error_code make_error_code(resolver_errc __e) noexcept
  { return error_code(static_cast<int>(__e), resolver_category()); }

  inline error_condition make_error_condition(resolver_errc __e) noexcept
  { return error_condition(static_cast<int>(__e), resolver_category()); }

  /// @}

  using port_type = uint_least16_t;	///< Type used for port numbers.
  using scope_id_type = uint_least32_t;	///< Type used for IPv6 scope IDs.

  /// Convenience alias for constraining allocators for strings.
  template<typename _Alloc>
    using __string_with
      = enable_if_t<std::is_same<typename _Alloc::value_type, char>::value,
		    std::basic_string<char, std::char_traits<char>, _Alloc>>;

  constexpr errc
  __unsupported_err() noexcept
  {
#if defined EAFNOSUPPORT
    return std::errc::address_family_not_supported;
#else
    return std::errc::operation_not_supported;
#endif
  }

  /** Tag indicating conversion between IPv4 and IPv4-mapped IPv6 addresses.
   * @{
   */

  struct v4_mapped_t {};
  constexpr v4_mapped_t v4_mapped;

  /// @}

  /// An IPv4 address.
  class address_v4
  {
  public:
    // types:
    using uint_type = uint_least32_t;

    struct bytes_type : array<unsigned char, 4>
    {
      template<typename... _Tp>
	explicit constexpr
	bytes_type(_Tp... __tp)
	: array<unsigned char, 4>{{static_cast<unsigned char>(__tp)...}}
	{
#if UCHAR_MAX > 0xFF
	  for (auto __b : *this)
	    if (__b > 0xFF)
	      __throw_out_of_range("invalid address_v4::bytes_type value");
#endif
	}
    };

    // constructors:
    constexpr address_v4() noexcept : _M_addr(0) { }

    constexpr address_v4(const address_v4& a) noexcept = default;

    constexpr
    address_v4(const bytes_type& __b)
    : _M_addr((__b[0] << 24) | (__b[1] << 16) | (__b[2] << 8) | __b[3])
    { }

    explicit constexpr
    address_v4(uint_type __val) : _M_addr(_S_hton_32(__val))
    {
#if UINT_LEAST32_MAX > 0xFFFFFFFF
      if (__val > 0xFFFFFFFF)
	__throw_out_of_range("invalid address_v4::uint_type value");
#endif
    }

    // assignment:
    address_v4& operator=(const address_v4& a) noexcept = default;

    // members:
    constexpr bool is_unspecified() const noexcept { return to_uint() == 0; }

    constexpr bool
    is_loopback() const noexcept
    { return (to_uint() & 0xFF000000) == 0x7F000000; }

    constexpr bool
    is_multicast() const noexcept
    { return (to_uint() & 0xF0000000) == 0xE0000000; }

    constexpr bytes_type
    to_bytes() const noexcept
    {
      return bytes_type{
	  (_M_addr >> 24) & 0xFF,
	  (_M_addr >> 16) & 0xFF,
	  (_M_addr >> 8) & 0xFF,
	  _M_addr & 0xFF
      };
    }

    constexpr uint_type
    to_uint() const noexcept { return _S_ntoh_32(_M_addr); }

    template<typename _Allocator = allocator<char>>
      __string_with<_Allocator>
      to_string(const _Allocator& __a = _Allocator()) const
      {
#ifdef _GLIBCXX_HAVE_ARPA_INET_H
	__string_with<_Allocator> __str(__a);
	__str.resize(INET_ADDRSTRLEN);
	if (inet_ntop(AF_INET, &_M_addr, &__str.front(), __str.size()))
	  __str.erase(__str.find('\0'));
	else
	  __str.resize(0);
	return __str;
#else
	std::__throw_system_error((int)__unsupported_err());
#endif
      }

    // static members:
    static constexpr address_v4 any() noexcept { return address_v4{}; }

    static constexpr
    address_v4 loopback() noexcept { return address_v4{0x7F000001}; }

    static constexpr
    address_v4 broadcast() noexcept { return address_v4{0xFFFFFFFF}; }

  private:
    template<typename _InternetProtocol>
      friend class basic_endpoint;

    friend address_v4 make_address_v4(const char*, error_code&) noexcept;

#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
    static constexpr uint16_t _S_hton_16(uint16_t __h) { return __h; }
    static constexpr uint16_t _S_ntoh_16(uint16_t __n) { return __n; }
    static constexpr uint32_t _S_hton_32(uint32_t __h) { return __h; }
    static constexpr uint32_t _S_ntoh_32(uint32_t __n) { return __n; }
#else
    static constexpr uint16_t
    _S_hton_16(uint16_t __h) { return __builtin_bswap16(__h); }

    static constexpr uint16_t
    _S_ntoh_16(uint16_t __n) { return __builtin_bswap16(__n); }

    static constexpr uint32_t
    _S_hton_32(uint32_t __h) { return __builtin_bswap32(__h); }

    static constexpr uint32_t
    _S_ntoh_32(uint32_t __n) { return __builtin_bswap32(__n); }
#endif

#ifdef _GLIBCXX_HAVE_ARPA_INET_H
    in_addr_t _M_addr; // network byte order
#else
    uint32_t _M_addr;
#endif
  };

  /// An IPv6 address.
  class address_v6
  {
  public:
    // types:
    struct bytes_type : array<unsigned char, 16>
    {
      template<typename... _Tp>
	explicit constexpr
	bytes_type(_Tp... __t)
	: array<unsigned char, 16>{{static_cast<unsigned char>(__t)...}}
	{ }
    };

    // constructors:
    constexpr address_v6() noexcept : _M_bytes(), _M_scope_id() { }

    constexpr address_v6(const address_v6& __a) noexcept = default;

    constexpr
    address_v6(const bytes_type& __bytes, scope_id_type __scope = 0)
    : _M_bytes(__bytes), _M_scope_id(__scope)
    { }

    // assignment:
    address_v6& operator=(const address_v6& __a) noexcept = default;

    // members:
    void scope_id(scope_id_type __id) noexcept { _M_scope_id = __id; }

    constexpr scope_id_type scope_id() const noexcept { return _M_scope_id; }

    constexpr bool
    is_unspecified() const noexcept
    {
      for (int __i = 0; __i < 16; ++__i)
	if (_M_bytes[__i] != 0x00)
	  return false;
      return _M_scope_id == 0;
    }

    constexpr bool
    is_loopback() const noexcept
    {
      for (int __i = 0; __i < 15; ++__i)
	if (_M_bytes[__i] != 0x00)
	  return false;
      return _M_bytes[15] == 0x01 && _M_scope_id == 0;
    }

    constexpr bool
    is_multicast() const noexcept { return _M_bytes[0] == 0xFF; }

    constexpr bool
    is_link_local() const noexcept
    { return _M_bytes[0] == 0xFE && (_M_bytes[1] & 0xC0) == 0x80; }

    constexpr bool
    is_site_local() const noexcept
    { return _M_bytes[0] == 0xFE && (_M_bytes[1] & 0xC0) == 0xC0; }

    constexpr bool
    is_v4_mapped() const noexcept
    {
      const bytes_type& __b = _M_bytes;
      return __b[0] == 0 && __b[1] == 0 && __b[ 2] == 0    && __b[ 3] == 0
	  && __b[4] == 0 && __b[5] == 0 && __b[ 6] == 0    && __b[ 7] == 0
	  && __b[8] == 0 && __b[9] == 0 && __b[10] == 0xFF && __b[11] == 0xFF;
    }

    constexpr bool
    is_multicast_node_local() const noexcept
    { return is_multicast() && (_M_bytes[1] & 0x0F) == 0x01; }

    constexpr bool
    is_multicast_link_local() const noexcept
    { return is_multicast() && (_M_bytes[1] & 0x0F) == 0x02; }

    constexpr bool
    is_multicast_site_local() const noexcept
    { return is_multicast() && (_M_bytes[1] & 0x0F) == 0x05; }

    constexpr bool
    is_multicast_org_local() const noexcept
    { return is_multicast() && (_M_bytes[1] & 0x0F) == 0x08; }

    constexpr bool
    is_multicast_global() const noexcept
    { return is_multicast() && (_M_bytes[1] & 0x0F) == 0x0b; }

    constexpr bytes_type to_bytes() const noexcept { return _M_bytes; }

    template<typename _Allocator = allocator<char>>
      __string_with<_Allocator>
      to_string(const _Allocator& __a = _Allocator()) const
      {
#ifdef _GLIBCXX_HAVE_ARPA_INET_H
	__string_with<_Allocator> __str(__a);
	__str.resize(INET6_ADDRSTRLEN + (_M_scope_id ? 11 : 0));
	char* const __p = &__str.front();
	if (inet_ntop(AF_INET6, &_M_bytes, __p, __str.size()))
	  {
	    auto __end = __str.find('\0');
	    if (unsigned long __scope = _M_scope_id)
	      {
		__end +=
#if _GLIBCXX_USE_C99_STDIO
		  __builtin_snprintf(__p + __end, __str.size() - __end,
				     "%%%lu", __scope);
#else
		  __builtin_sprintf(__p + __end, "%%%lu", __scope);
#endif
	      }
	    __str.erase(__end);
	  }
	else
	  __str.resize(0);
	return __str;
#else
	std::__throw_system_error((int)__unsupported_err());
#endif
      }

    // static members:

    static constexpr address_v6
    any() noexcept
    {
      return {};
    }

    static constexpr address_v6
    loopback() noexcept
    {
      return {bytes_type{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}};
    }

  private:
    template<typename _InternetProtocol>
      friend class basic_endpoint;

    friend constexpr bool
    operator==(const address_v6&, const address_v6&) noexcept;

    friend constexpr bool
    operator< (const address_v6&, const address_v6&) noexcept;

    bytes_type _M_bytes;
    scope_id_type _M_scope_id;
  };

  /// Exception type thrown on misuse of IPv4 addresses as IPv6 or vice versa.
  class bad_address_cast : public bad_cast
  {
  public:
    bad_address_cast() { }

    const char* what() const noexcept { return "bad address cast"; }
  };

  /// An IPv4 or IPv6 address.
  class address
  {
  public:
    // constructors:
    constexpr address() noexcept : _M_v4(), _M_is_v4(true) { }

#if __cpp_constexpr_dynamic_alloc
    constexpr
#endif
    address(const address& __a) noexcept : _M_uninit(), _M_is_v4(__a._M_is_v4)
    {
      if (_M_is_v4)
	std::_Construct(std::addressof(_M_v4), __a.to_v4());
      else
	std::_Construct(std::addressof(_M_v6), __a.to_v6());
    }

    constexpr
    address(const address_v4& __a) noexcept : _M_v4(__a), _M_is_v4(true) { }

    constexpr
    address(const address_v6& __a) noexcept : _M_v6(__a), _M_is_v4(false) { }

    // assignment:
    address&
    operator=(const address& __a) noexcept
    {
      if (__a._M_is_v4)
	*this = __a.to_v4();
      else
	*this = __a.to_v6();
      return *this;
    }

    address&
    operator=(const address_v4& __a) noexcept
    {
      std::_Construct(std::addressof(_M_v4), __a);
      _M_is_v4 = true;
      return *this;
    }

    address&
    operator=(const address_v6& __a) noexcept
    {
      std::_Construct(std::addressof(_M_v6), __a);
      _M_is_v4 = false;
      return *this;
    }

    // members:

    constexpr bool is_v4() const noexcept { return _M_is_v4; }
    constexpr bool is_v6() const noexcept { return !_M_is_v4; }

    constexpr address_v4
    to_v4() const
    {
      if (!is_v4())
	_GLIBCXX_THROW_OR_ABORT(bad_address_cast());
      return _M_v4;
    }

    constexpr address_v6
    to_v6() const
    {
      if (!is_v6())
	_GLIBCXX_THROW_OR_ABORT(bad_address_cast());
      return _M_v6;
    }

    constexpr bool
    is_unspecified() const noexcept
    { return _M_is_v4 ? _M_v4.is_unspecified() : _M_v6.is_unspecified(); }

    constexpr bool
    is_loopback() const noexcept
    { return _M_is_v4 ? _M_v4.is_loopback() : _M_v6.is_loopback(); }

    constexpr bool
    is_multicast() const noexcept
    { return _M_is_v4 ? _M_v4.is_multicast() : _M_v6.is_multicast(); }

    template<typename _Allocator = allocator<char>>
      __string_with<_Allocator>
      to_string(const _Allocator& __a = _Allocator()) const
      {
	if (_M_is_v4)
	  return to_v4().to_string(__a);
	return to_v6().to_string(__a);
      }

  private:
    template<typename _InternetProtocol>
      friend class basic_endpoint;

    friend constexpr bool
    operator==(const address&, const address&) noexcept;

    friend constexpr bool
    operator<(const address&, const address&) noexcept;

    union {
      address_v4 _M_v4;
      address_v6 _M_v6;
      bool	 _M_uninit;
    };
    bool _M_is_v4;
  };

  /** ip::address_v4 comparisons
   * @{
   */

  constexpr bool
  operator==(const address_v4& __a, const address_v4& __b) noexcept
  { return __a.to_uint() == __b.to_uint(); }

  constexpr bool
  operator!=(const address_v4& __a, const address_v4& __b) noexcept
  { return !(__a == __b); }

  constexpr bool
  operator< (const address_v4& __a, const address_v4& __b) noexcept
  { return __a.to_uint() < __b.to_uint(); }

  constexpr bool
  operator> (const address_v4& __a, const address_v4& __b) noexcept
  { return __b < __a; }

  constexpr bool
  operator<=(const address_v4& __a, const address_v4& __b) noexcept
  { return !(__b < __a); }

  constexpr bool
  operator>=(const address_v4& __a, const address_v4& __b) noexcept
  { return !(__a < __b); }

  /// @}

  /** ip::address_v6 comparisons
   * @{
   */

  constexpr bool
  operator==(const address_v6& __a, const address_v6& __b) noexcept
  {
    const auto& __aa = __a._M_bytes;
    const auto& __bb = __b._M_bytes;
    int __i = 0;
    for (; __i < 16 && __aa[__i] == __bb[__i]; ++__i)
      ;
    return __i == 16 ? __a.scope_id() == __b.scope_id() : false;
  }

  constexpr bool
  operator!=(const address_v6& __a, const address_v6& __b) noexcept
  { return !(__a == __b); }

  constexpr bool
  operator< (const address_v6& __a, const address_v6& __b) noexcept
  {
    const auto& __aa = __a._M_bytes;
    const auto& __bb = __b._M_bytes;
    int __i = 0;
    for (; __i < 16 && __aa[__i] == __bb[__i]; ++__i)
      ;
    return __i == 16 ? __a.scope_id() < __b.scope_id() : __aa[__i] < __bb[__                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   