// -*- C++ -*-
//===-------------------------- __string ----------------------------------===//
//
// 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 _LIBCUDACXX___STRING
#define _LIBCUDACXX___STRING

/*
    string synopsis

namespace std
{

template <class charT>
struct char_traits
{
    typedef charT     char_type;
    typedef ...       int_type;
    typedef streamoff off_type;
    typedef streampos pos_type;
    typedef mbstate_t state_type;

    static constexpr void assign(char_type& c1, const char_type& c2) noexcept;
    static constexpr bool eq(char_type c1, char_type c2) noexcept;
    static constexpr bool lt(char_type c1, char_type c2) noexcept;

    static constexpr int    compare(const char_type* s1, const char_type* s2, size_t n);
    static constexpr size_t length(const char_type* s);
    static constexpr const char_type*
                            find(const char_type* s, size_t n, const char_type& a);
    static char_type*       move(char_type* s1, const char_type* s2, size_t n);
    static char_type*       copy(char_type* s1, const char_type* s2, size_t n);
    static char_type*       assign(char_type* s, size_t n, char_type a);

    static constexpr int_type  not_eof(int_type c) noexcept;
    static constexpr char_type to_char_type(int_type c) noexcept;
    static constexpr int_type  to_int_type(char_type c) noexcept;
    static constexpr bool      eq_int_type(int_type c1, int_type c2) noexcept;
    static constexpr int_type  eof() noexcept;
};

template <> struct char_traits<char>;
template <> struct char_traits<wchar_t>;
template <> struct char_traits<char8_t>;  // c++20

}  // std

*/

#include <cuda/std/detail/__config>

#if defined(_CCCL_IMPLICIT_SYSTEM_HEADER_GCC)
#  pragma GCC system_header
#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_CLANG)
#  pragma clang system_header
#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_MSVC)
#  pragma system_header
#endif // no system header

#include <cuda/std/__algorithm/copy.h>
#include <cuda/std/__algorithm/find_end.h>
#include <cuda/std/__algorithm/find_first_of.h>
#include <cuda/std/__algorithm/iterator_operations.h>
#include <cuda/std/__algorithm/min.h>
#include <cuda/std/__algorithm/search.h>
#include <cuda/std/__fwd/string.h>
#include <cuda/std/detail/libcxx/include/__assert> // all public C++ headers provide the assertion handler
#include <cuda/std/detail/libcxx/include/__debug>
#include <cuda/std/detail/libcxx/include/iosfwd>

_CCCL_PUSH_MACROS

_LIBCUDACXX_BEGIN_NAMESPACE_STD

// char_traits

template <class _CharT>
struct _CCCL_TYPE_VISIBILITY_DEFAULT char_traits
{
  typedef _CharT char_type;
  typedef int int_type;
  typedef streamoff off_type;
#ifndef _LIBCUDACXX_HAS_NO_WCHAR_H
  typedef streampos pos_type;
  typedef mbstate_t state_type;
#endif // !_LIBCUDACXX_HAS_NO_WCHAR_H

  _LIBCUDACXX_HIDE_FROM_ABI static void _CCCL_CONSTEXPR_CXX14 assign(char_type& __c1, const char_type& __c2) noexcept
  {
    __c1 = __c2;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool eq(char_type __c1, char_type __c2) noexcept
  {
    return __c1 == __c2;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool lt(char_type __c1, char_type __c2) noexcept
  {
    return __c1 < __c2;
  }

  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 int
  compare(const char_type* __s1, const char_type* __s2, size_t __n);
  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 size_t length(const char_type* __s);
  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 const char_type*
  find(const char_type* __s, size_t __n, const char_type& __a);
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* move(char_type* __s1, const char_type* __s2, size_t __n);
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n);
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* assign(char_type* __s, size_t __n, char_type __a);

#ifndef __cuda_std__
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type not_eof(int_type __c) noexcept
  {
    return eq_int_type(__c, eof()) ? ~eof() : __c;
  }
#endif // !__cuda_std__
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr char_type to_char_type(int_type __c) noexcept
  {
    return char_type(__c);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type to_int_type(char_type __c) noexcept
  {
    return int_type(__c);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept
  {
    return __c1 == __c2;
  }
#ifndef __cuda_std__
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type eof() noexcept
  {
    return int_type(EOF);
  }
#endif // !__cuda_std__
};

template <class _CharT>
_CCCL_CONSTEXPR_CXX14 int char_traits<_CharT>::compare(const char_type* __s1, const char_type* __s2, size_t __n)
{
  for (; __n; --__n, ++__s1, ++__s2)
  {
    if (lt(*__s1, *__s2))
    {
      return -1;
    }
    if (lt(*__s2, *__s1))
    {
      return 1;
    }
  }
  return 0;
}

template <class _CharT>
inline _CCCL_CONSTEXPR_CXX14 size_t char_traits<_CharT>::length(const char_type* __s)
{
  size_t __len = 0;
  for (; !eq(*__s, char_type(0)); ++__s)
  {
    ++__len;
  }
  return __len;
}

template <class _CharT>
inline _CCCL_CONSTEXPR_CXX14 const _CharT*
char_traits<_CharT>::find(const char_type* __s, size_t __n, const char_type& __a)
{
  for (; __n; --__n)
  {
    if (eq(*__s, __a))
    {
      return __s;
    }
    ++__s;
  }
  return 0;
}

template <class _CharT>
_LIBCUDACXX_HIDE_FROM_ABI _CharT* char_traits<_CharT>::move(char_type* __s1, const char_type* __s2, size_t __n)
{
  char_type* __r = __s1;
  if (__s1 < __s2)
  {
    for (; __n; --__n, ++__s1, ++__s2)
    {
      assign(*__s1, *__s2);
    }
  }
  else if (__s2 < __s1)
  {
    __s1 += __n;
    __s2 += __n;
    for (; __n; --__n)
    {
      assign(*--__s1, *--__s2);
    }
  }
  return __r;
}

template <class _CharT>
_LIBCUDACXX_HIDE_FROM_ABI _CharT* char_traits<_CharT>::copy(char_type* __s1, const char_type* __s2, size_t __n)
{
  _LIBCUDACXX_ASSERT(__s2 < __s1 || __s2 >= __s1 + __n, "char_traits::copy overlapped range");
  char_type* __r = __s1;
  for (; __n; --__n, ++__s1, ++__s2)
  {
    assign(*__s1, *__s2);
  }
  return __r;
}

template <class _CharT>
_LIBCUDACXX_HIDE_FROM_ABI _CharT* char_traits<_CharT>::assign(char_type* __s, size_t __n, char_type __a)
{
  char_type* __r = __s;
  for (; __n; --__n, ++__s)
  {
    assign(*__s, __a);
  }
  return __r;
}

// char_traits<char>

// GCC's builtin_strlen isn't reliable at constexpr time
// MSVC does not expose builtin_strlen before C++17
#if defined(_CCCL_COMPILER_GCC) || (defined(_CCCL_COMPILER_MSVC) && _CCCL_STD_VER < 2017)
#  define _CCCL_HAS_NO_BUILTIN_STRLEN
#endif

template <>
struct _CCCL_TYPE_VISIBILITY_DEFAULT char_traits<char>
{
  typedef char char_type;
  typedef int int_type;
  typedef streamoff off_type;
#ifndef _LIBCUDACXX_HAS_NO_WCHAR_H
  typedef streampos pos_type;
  typedef mbstate_t state_type;
#endif // !_LIBCUDACXX_HAS_NO_WCHAR_H

  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 void assign(char_type& __c1, const char_type& __c2) noexcept
  {
    __c1 = __c2;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool eq(char_type __c1, char_type __c2) noexcept
  {
    return __c1 == __c2;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool lt(char_type __c1, char_type __c2) noexcept
  {
    return (unsigned char) __c1 < (unsigned char) __c2;
  }

  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 int
  compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept;
  _LIBCUDACXX_HIDE_FROM_ABI static size_t _CCCL_CONSTEXPR_CXX14 length(const char_type* __s) noexcept
  {
#ifdef _CCCL_HAS_NO_BUILTIN_STRLEN
#  ifdef _LIBCUDACXX_IS_CONSTANT_EVALUATED // is_constant_evaluated only exists since GCC 9
    if (__libcpp_is_constant_evaluated())
#  endif // defined(_LIBCUDACXX_IS_CONSTANT_EVALUATED)
    {
      size_t __len = 0;
      for (; !eq(*__s, char(0)); ++__s)
      {
        ++__len;
      }
      return __len;
    }
#endif // defined(_CCCL_HAS_NO_BUILTIN_STRLEN)
#if !defined(_CCCL_HAS_NO_BUILTIN_STRLEN) || defined(_LIBCUDACXX_IS_CONSTANT_EVALUATED)
    NV_IF_ELSE_TARGET(NV_IS_DEVICE,
                      (size_t __len = 0; for (; !eq(*__s, char(0)); ++__s)++ __len; return __len;),
                      (return __builtin_strlen(__s);))
#endif // !defined(_CCCL_HAS_NO_BUILTIN_STRLEN) || defined(_LIBCUDACXX_IS_CONSTANT_EVALUATED)
  }
  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 const char_type*
  find(const char_type* __s, size_t __n, const char_type& __a) noexcept;
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) noexcept
  {
    return __n == 0 ? __s1 : (char_type*) __copy<_ClassicAlgPolicy>(__s2, __s2 + __n, __s1).first - __n;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) noexcept
  {
    _LIBCUDACXX_ASSERT(__s2 < __s1 || __s2 >= __s1 + __n, "char_traits::copy overlapped range");
    return __n == 0 ? __s1 : (char_type*) memcpy(__s1, __s2, __n);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* assign(char_type* __s, size_t __n, char_type __a) noexcept
  {
    return __n == 0 ? __s : (char_type*) memset(__s, to_int_type(__a), __n);
  }

#ifndef __cuda_std__
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type not_eof(int_type __c) noexcept
  {
    return eq_int_type(__c, eof()) ? ~eof() : __c;
  }
#endif // !__cuda_std__
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr char_type to_char_type(int_type __c) noexcept
  {
    return char_type(__c);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type to_int_type(char_type __c) noexcept
  {
    return int_type((unsigned char) __c);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept
  {
    return __c1 == __c2;
  }
#ifndef __cuda_std__
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type eof() noexcept
  {
    return int_type(EOF);
  }
#endif // !__cuda_std__
};

inline _CCCL_CONSTEXPR_CXX14 int
char_traits<char>::compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept
{
  if (__n == 0)
  {
    return 0;
  }
#if __has_feature(cxx_constexpr_string_builtins)
  return __builtin_memcmp(__s1, __s2, __n);
#else
  for (; __n; --__n, ++__s1, ++__s2)
  {
    if (lt(*__s1, *__s2))
    {
      return -1;
    }
    if (lt(*__s2, *__s1))
    {
      return 1;
    }
  }
  return 0;
#endif // !has_feature(constexpr_string_builtins)
}

inline _CCCL_CONSTEXPR_CXX14 const char*
char_traits<char>::find(const char_type* __s, size_t __n, const char_type& __a) noexcept
{
  if (__n == 0)
  {
    return nullptr;
  }
#if __has_feature(cxx_constexpr_string_builtins)
  return __builtin_char_memchr(__s, to_int_type(__a), __n);
#else
  for (; __n; --__n)
  {
    if (eq(*__s, __a))
    {
      return __s;
    }
    ++__s;
  }
  return nullptr;
#endif // !has_feature(constexpr_string_builtins)
}

// char_traits<wchar_t>

#ifndef _LIBCUDACXX_HAS_NO_WCHAR_H
template <>
struct _CCCL_TYPE_VISIBILITY_DEFAULT char_traits<wchar_t>
{
  typedef wchar_t char_type;
  typedef wint_t int_type;
  typedef streamoff off_type;
  typedef streampos pos_type;
  typedef mbstate_t state_type;

  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 void assign(char_type& __c1, const char_type& __c2) noexcept
  {
    __c1 = __c2;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool eq(char_type __c1, char_type __c2) noexcept
  {
    return __c1 == __c2;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool lt(char_type __c1, char_type __c2) noexcept
  {
    return __c1 < __c2;
  }

  static _CCCL_CONSTEXPR_CXX14 int compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept;
  static _CCCL_CONSTEXPR_CXX14 size_t length(const char_type* __s) noexcept;
  static _CCCL_CONSTEXPR_CXX14 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) noexcept;
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) noexcept
  {
    return __n == 0 ? __s1 : (char_type*) wmemmove(__s1, __s2, __n);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) noexcept
  {
    _LIBCUDACXX_ASSERT(__s2 < __s1 || __s2 >= __s1 + __n, "char_traits::copy overlapped range");
    return __n == 0 ? __s1 : (char_type*) wmemcpy(__s1, __s2, __n);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* assign(char_type* __s, size_t __n, char_type __a) noexcept
  {
    return __n == 0 ? __s : (char_type*) wmemset(__s, __a, __n);
  }

#  ifndef __cuda_std__
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type not_eof(int_type __c) noexcept
  {
    return eq_int_type(__c, eof()) ? ~eof() : __c;
  }
#  endif // !__cuda_std__
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr char_type to_char_type(int_type __c) noexcept
  {
    return char_type(__c);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type to_int_type(char_type __c) noexcept
  {
    return int_type(__c);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept
  {
    return __c1 == __c2;
  }
#  ifndef __cuda_std__
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type eof() noexcept
  {
    return int_type(WEOF);
  }
#  endif // !__cuda_std__
};

inline _CCCL_CONSTEXPR_CXX14 int
char_traits<wchar_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept
{
  if (__n == 0)
  {
    return 0;
  }
#  if __has_feature(cxx_constexpr_string_builtins)
  return __builtin_wmemcmp(__s1, __s2, __n);
#  elif _CCCL_STD_VER <= 2014
  return wmemcmp(__s1, __s2, __n);
#  else
  for (; __n; --__n, ++__s1, ++__s2)
  {
    if (lt(*__s1, *__s2))
    {
      return -1;
    }
    if (lt(*__s2, *__s1))
    {
      return 1;
    }
  }
  return 0;
#  endif
}
#endif // !_LIBCUDACXX_HAS_NO_WCHAR_H

template <class _Traits>
_LIBCUDACXX_HIDE_FROM_ABI constexpr size_t __char_traits_length_checked(const typename _Traits::char_type* __s) noexcept
{
#if _LIBCUDACXX_DEBUG_LEVEL >= 1
  return __s
         ? _Traits::length(__s)
         : (_CUDA_VSTD::__libcpp_debug_function(_CUDA_VSTD::__libcpp_debug_info(
              __FILE__, __LINE__, "p == nullptr", "null pointer pass to non-null argument of char_traits<...>::length")),
            0);
#else
  return _Traits::length(__s);
#endif
}

#ifndef _LIBCUDACXX_HAS_NO_WCHAR_H
inline _CCCL_CONSTEXPR_CXX14 size_t char_traits<wchar_t>::length(const char_type* __s) noexcept
{
#  if __has_feature(cxx_constexpr_string_builtins)
  return __builtin_wcslen(__s);
#  elif _CCCL_STD_VER <= 2014
  return wcslen(__s);
#  else
  size_t __len = 0;
  for (; !eq(*__s, char_type(0)); ++__s)
  {
    ++__len;
  }
  return __len;
#  endif
}

inline _CCCL_CONSTEXPR_CXX14 const wchar_t*
char_traits<wchar_t>::find(const char_type* __s, size_t __n, const char_type& __a) noexcept
{
  if (__n == 0)
  {
    return nullptr;
  }
#  if __has_feature(cxx_constexpr_string_builtins)
  return __builtin_wmemchr(__s, __a, __n);
#  else
  for (; __n; --__n)
  {
    if (eq(*__s, __a))
    {
      return __s;
    }
    ++__s;
  }
  return nullptr;
#  endif
}
#endif // !_LIBCUDACXX_HAS_NO_WCHAR_H

#ifndef _LIBCUDACXX_NO_HAS_CHAR8_T

template <>
struct _CCCL_TYPE_VISIBILITY_DEFAULT char_traits<char8_t>
{
  typedef char8_t char_type;
  typedef unsigned int int_type;
  typedef streamoff off_type;
#  ifndef _LIBCUDACXX_HAS_NO_WCHAR_H
  typedef u8streampos pos_type;
  typedef mbstate_t state_type;
#  endif // !_LIBCUDACXX_HAS_NO_WCHAR_H

  _LIBCUDACXX_HIDE_FROM_ABI static constexpr void assign(char_type& __c1, const char_type& __c2) noexcept
  {
    __c1 = __c2;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool eq(char_type __c1, char_type __c2) noexcept
  {
    return __c1 == __c2;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool lt(char_type __c1, char_type __c2) noexcept
  {
    return __c1 < __c2;
  }

  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int
  compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept;

  _LIBCUDACXX_HIDE_FROM_ABI static constexpr size_t length(const char_type* __s) noexcept;

  _LIBCUDACXX_HIDE_FROM_ABI static constexpr const char_type*
  find(const char_type* __s, size_t __n, const char_type& __a) noexcept;

  _LIBCUDACXX_HIDE_FROM_ABI static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) noexcept
  {
    return __n == 0 ? __s1 : (char_type*) __copy<_ClassicAlgPolicy>(__s2, __s2 + __n, __s1).first - __n;
  }

  _LIBCUDACXX_HIDE_FROM_ABI static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) noexcept
  {
    _LIBCUDACXX_ASSERT(__s2 < __s1 || __s2 >= __s1 + __n, "char_traits::copy overlapped range");
    return __n == 0 ? __s1 : (char_type*) memcpy(__s1, __s2, __n);
  }

  _LIBCUDACXX_HIDE_FROM_ABI static char_type* assign(char_type* __s, size_t __n, char_type __a) noexcept
  {
    return __n == 0 ? __s : (char_type*) memset(__s, to_int_type(__a), __n);
  }

#  ifndef __cuda_std__
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type not_eof(int_type __c) noexcept
  {
    return eq_int_type(__c, eof()) ? ~eof() : __c;
  }
#  endif // !__cuda_std__
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr char_type to_char_type(int_type __c) noexcept
  {
    return char_type(__c);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type to_int_type(char_type __c) noexcept
  {
    return int_type(__c);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept
  {
    return __c1 == __c2;
  }
#  ifndef __cuda_std__
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type eof() noexcept
  {
    return int_type(EOF);
  }
#  endif // !__cuda_std__
};

// TODO use '__builtin_strlen' if it ever supports char8_t ??
inline constexpr size_t char_traits<char8_t>::length(const char_type* __s) noexcept
{
  size_t __len = 0;
  for (; !eq(*__s, char_type(0)); ++__s)
  {
    ++__len;
  }
  return __len;
}

inline constexpr int char_traits<char8_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept
{
#  if __has_feature(cxx_constexpr_string_builtins)
  return __builtin_memcmp(__s1, __s2, __n);
#  else
  for (; __n; --__n, ++__s1, ++__s2)
  {
    if (lt(*__s1, *__s2))
    {
      return -1;
    }
    if (lt(*__s2, *__s1))
    {
      return 1;
    }
  }
  return 0;
#  endif
}

// TODO use '__builtin_char_memchr' if it ever supports char8_t ??
inline constexpr const char8_t*
char_traits<char8_t>::find(const char_type* __s, size_t __n, const char_type& __a) noexcept
{
  for (; __n; --__n)
  {
    if (eq(*__s, __a))
    {
      return __s;
    }
    ++__s;
  }
  return 0;
}

#endif // #_LIBCUDACXX_NO_HAS_CHAR8_T

#ifndef _LIBCUDACXX_HAS_NO_UNICODE_CHARS

template <>
struct _CCCL_TYPE_VISIBILITY_DEFAULT char_traits<char16_t>
{
  typedef char16_t char_type;
  typedef uint_least16_t int_type;
  typedef streamoff off_type;
#  ifndef _LIBCUDACXX_HAS_NO_WCHAR_H
  typedef u16streampos pos_type;
  typedef mbstate_t state_type;
#  endif // !_LIBCUDACXX_HAS_NO_WCHAR_H

  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 void assign(char_type& __c1, const char_type& __c2) noexcept
  {
    __c1 = __c2;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool eq(char_type __c1, char_type __c2) noexcept
  {
    return __c1 == __c2;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool lt(char_type __c1, char_type __c2) noexcept
  {
    return __c1 < __c2;
  }

  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 int
  compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept;
  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 size_t length(const char_type* __s) noexcept;
  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 const char_type*
  find(const char_type* __s, size_t __n, const char_type& __a) noexcept;
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) noexcept;
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) noexcept;
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* assign(char_type* __s, size_t __n, char_type __a) noexcept;

  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type not_eof(int_type __c) noexcept
  {
    return eq_int_type(__c, eof()) ? ~eof() : __c;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr char_type to_char_type(int_type __c) noexcept
  {
    return char_type(__c);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type to_int_type(char_type __c) noexcept
  {
    return int_type(__c);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept
  {
    return __c1 == __c2;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type eof() noexcept
  {
    return int_type(0xFFFF);
  }
};

inline _CCCL_CONSTEXPR_CXX14 int
char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept
{
  for (; __n; --__n, ++__s1, ++__s2)
  {
    if (lt(*__s1, *__s2))
    {
      return -1;
    }
    if (lt(*__s2, *__s1))
    {
      return 1;
    }
  }
  return 0;
}

inline _CCCL_CONSTEXPR_CXX14 size_t char_traits<char16_t>::length(const char_type* __s) noexcept
{
  size_t __len = 0;
  for (; !eq(*__s, char_type(0)); ++__s)
  {
    ++__len;
  }
  return __len;
}

inline _CCCL_CONSTEXPR_CXX14 const char16_t*
char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) noexcept
{
  for (; __n; --__n)
  {
    if (eq(*__s, __a))
    {
      return __s;
    }
    ++__s;
  }
  return 0;
}

_LIBCUDACXX_HIDE_FROM_ABI char16_t*
char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n) noexcept
{
  char_type* __r = __s1;
  if (__s1 < __s2)
  {
    for (; __n; --__n, ++__s1, ++__s2)
    {
      assign(*__s1, *__s2);
    }
  }
  else if (__s2 < __s1)
  {
    __s1 += __n;
    __s2 += __n;
    for (; __n; --__n)
    {
      assign(*--__s1, *--__s2);
    }
  }
  return __r;
}

_LIBCUDACXX_HIDE_FROM_ABI char16_t*
char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) noexcept
{
  _LIBCUDACXX_ASSERT(__s2 < __s1 || __s2 >= __s1 + __n, "char_traits::copy overlapped range");
  char_type* __r = __s1;
  for (; __n; --__n, ++__s1, ++__s2)
  {
    assign(*__s1, *__s2);
  }
  return __r;
}

_LIBCUDACXX_HIDE_FROM_ABI char16_t* char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a) noexcept
{
  char_type* __r = __s;
  for (; __n; --__n, ++__s)
  {
    assign(*__s, __a);
  }
  return __r;
}

template <>
struct _CCCL_TYPE_VISIBILITY_DEFAULT char_traits<char32_t>
{
  typedef char32_t char_type;
  typedef uint_least32_t int_type;
  typedef streamoff off_type;
#  ifndef _LIBCUDACXX_HAS_NO_WCHAR_H
  typedef u32streampos pos_type;
  typedef mbstate_t state_type;
#  endif // !_LIBCUDACXX_HAS_NO_WCHAR_H

  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 void assign(char_type& __c1, const char_type& __c2) noexcept
  {
    __c1 = __c2;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool eq(char_type __c1, char_type __c2) noexcept
  {
    return __c1 == __c2;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool lt(char_type __c1, char_type __c2) noexcept
  {
    return __c1 < __c2;
  }

  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 int
  compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept;
  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 size_t length(const char_type* __s) noexcept;
  _LIBCUDACXX_HIDE_FROM_ABI static _CCCL_CONSTEXPR_CXX14 const char_type*
  find(const char_type* __s, size_t __n, const char_type& __a) noexcept;
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) noexcept;
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) noexcept;
  _LIBCUDACXX_HIDE_FROM_ABI static char_type* assign(char_type* __s, size_t __n, char_type __a) noexcept;

  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type not_eof(int_type __c) noexcept
  {
    return eq_int_type(__c, eof()) ? ~eof() : __c;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr char_type to_char_type(int_type __c) noexcept
  {
    return char_type(__c);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type to_int_type(char_type __c) noexcept
  {
    return int_type(__c);
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept
  {
    return __c1 == __c2;
  }
  _LIBCUDACXX_HIDE_FROM_ABI static constexpr int_type eof() noexcept
  {
    return int_type(0xFFFFFFFF);
  }
};

inline _CCCL_CONSTEXPR_CXX14 int
char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept
{
  for (; __n; --__n, ++__s1, ++__s2)
  {
    if (lt(*__s1, *__s2))
    {
      return -1;
    }
    if (lt(*__s2, *__s1))
    {
      return 1;
    }
  }
  return 0;
}

inline _CCCL_CONSTEXPR_CXX14 size_t char_traits<char32_t>::length(const char_type* __s) noexcept
{
  size_t __len = 0;
  for (; !eq(*__s, char_type(0)); ++__s)
  {
    ++__len;
  }
  return __len;
}

inline _CCCL_CONSTEXPR_CXX14 const char32_t*
char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) noexcept
{
  for (; __n; --__n)
  {
    if (eq(*__s, __a))
    {
      return __s;
    }
    ++__s;
  }
  return 0;
}

_LIBCUDACXX_HIDE_FROM_ABI char32_t*
char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n) noexcept
{
  char_type* __r = __s1;
  if (__s1 < __s2)
  {
    for (; __n; --__n, ++__s1, ++__s2)
    {
      assign(*__s1, *__s2);
    }
  }
  else if (__s2 < __s1)
  {
    __s1 += __n;
    __s2 += __n;
    for (; __n; --__n)
    {
      assign(*--__s1, *--__s2);
    }
  }
  return __r;
}

_LIBCUDACXX_HIDE_FROM_ABI char32_t*
char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) noexcept
{
  _LIBCUDACXX_ASSERT(__s2 < __s1 || __s2 >= __s1 + __n, "char_traits::copy overlapped range");
  char_type* __r = __s1;
  for (; __n; --__n, ++__s1, ++__s2)
  {
    assign(*__s1, *__s2);
  }
  return __r;
}

_LIBCUDACXX_HIDE_FROM_ABI char32_t* char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a) noexcept
{
  char_type* __r = __s;
  for (; __n; --__n, ++__s)
  {
    assign(*__s, __a);
  }
  return __r;
}

#endif // _LIBCUDACXX_HAS_NO_UNICODE_CHARS

// helper fns for basic_string and string_view

// __str_find
template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 _SizeT
__str_find(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) noexcept
{
  if (__pos >= __sz)
  {
    return __npos;
  }
  const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
  if (__r == 0)
  {
    return __npos;
  }
  return static_cast<_SizeT>(__r - __p);
}

template <class _CharT, class _Traits>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 const _CharT*
__search_substring(const _CharT* __first1, const _CharT* __last1, const _CharT* __first2, const _CharT* __last2)
{
  // Take advantage of knowing source and pattern lengths.
  // Stop short when source is smaller than pattern.
  const ptrdiff_t __len2 = __last2 - __first2;
  if (__len2 == 0)
  {
    return __first1;
  }

  ptrdiff_t __len1 = __last1 - __first1;
  if (__len1 < __len2)
  {
    return __last1;
  }

  // First element of __first2 is loop invariant.
  _CharT __f2 = *__first2;
  while (true)
  {
    __len1 = __last1 - __first1;
    // Check whether __first1 still has at least __len2 bytes.
    if (__len1 < __len2)
    {
      return __last1;
    }

    // Find __f2 the first byte matching in __first1.
    __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
    if (__first1 == 0)
    {
      return __last1;
    }

    // It is faster to compare from the first byte of __first1 even if we
    // already know that it matches the first byte of __first2: this is because
    // __first2 is most likely aligned, as it is user's "pattern" string, and
    // __first1 + 1 is most likely not aligned, as the match is in the middle of
    // the string.
    if (_Traits::compare(__first1, __first2, __len2) == 0)
    {
      return __first1;
    }

    ++__first1;
  }
}

template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 _SizeT
__str_find(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) noexcept
{
  if (__pos > __sz)
  {
    return __npos;
  }

  if (__n == 0) // There is nothing to search, just return __pos.
  {
    return __pos;
  }

  const _CharT* __r = __search_substring<_CharT, _Traits>(__p + __pos, __p + __sz, __s, __s + __n);

  if (__r == __p + __sz)
  {
    return __npos;
  }
  return static_cast<_SizeT>(__r - __p);
}

// __str_rfind

template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 _SizeT
__str_rfind(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) noexcept
{
  if (__sz < 1)
  {
    return __npos;
  }
  if (__pos < __sz)
  {
    ++__pos;
  }
  else
  {
    __pos = __sz;
  }
  for (const _CharT* __ps = __p + __pos; __ps != __p;)
  {
    if (_Traits::eq(*--__ps, __c))
    {
      return static_cast<_SizeT>(__ps - __p);
    }
  }
  return __npos;
}

template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 _SizeT
__str_rfind(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) noexcept
{
  __pos = _CUDA_VSTD::min(__pos, __sz);
  if (__n < __sz - __pos)
  {
    __pos += __n;
  }
  else
  {
    __pos = __sz;
  }
  const _CharT* __r = _CUDA_VSTD::__find_end(
    __p, __p + __pos, __s, __s + __n, _Traits::eq, random_access_iterator_tag(), random_access_iterator_tag());
  if (__n > 0 && __r == __p + __pos)
  {
    return __npos;
  }
  return static_cast<_SizeT>(__r - __p);
}

// __str_find_first_of
template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 _SizeT
__str_find_first_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) noexcept
{
  if (__pos >= __sz || __n == 0)
  {
    return __npos;
  }
  const _CharT* __r = _CUDA_VSTD::__find_first_of_ce(__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq);
  if (__r == __p + __sz)
  {
    return __npos;
  }
  return static_cast<_SizeT>(__r - __p);
}

// __str_find_last_of
template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 _SizeT
__str_find_last_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) noexcept
{
  if (__n != 0)
  {
    if (__pos < __sz)
    {
      ++__pos;
    }
    else
    {
      __pos = __sz;
    }
    for (const _CharT* __ps = __p + __pos; __ps != __p;)
    {
      const _CharT* __r = _Traits::find(__s, __n, *--__ps);
      if (__r)
      {
        return static_cast<_SizeT>(__ps - __p);
      }
    }
  }
  return __npos;
}

// __str_find_first_not_of
template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 _SizeT
__str_find_first_not_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) noexcept
{
  if (__pos < __sz)
  {
    const _CharT* __pe = __p + __sz;
    for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
    {
      if (_Traits::find(__s, __n, *__ps) == 0)
      {
        return static_cast<_SizeT>(__ps - __p);
      }
    }
  }
  return __npos;
}

template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 _SizeT
__str_find_first_not_of(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) noexcept
{
  if (__pos < __sz)
  {
    const _CharT* __pe = __p + __sz;
    for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
    {
      if (!_Traits::eq(*__ps, __c))
      {
        return static_cast<_SizeT>(__ps - __p);
      }
    }
  }
  return __npos;
}

// __str_find_last_not_of
template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 _SizeT
__str_find_last_not_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) noexcept
{
  if (__pos < __sz)
  {
    ++__pos;
  }
  else
  {
    __pos = __sz;
  }
  for (const _CharT* __ps = __p + __pos; __ps != __p;)
  {
    if (_Traits::find(__s, __n, *--__ps) == 0)
    {
      return static_cast<_SizeT>(__ps - __p);
    }
  }
  return __npos;
}

template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
_LIBCUDACXX_HIDE_FROM_ABI _CCCL_CONSTEXPR_CXX14 _SizeT
__str_find_last_not_of(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) noexcept
{
  if (__pos < __sz)
  {
    ++__pos;
  }
  else
  {
    __pos = __sz;
  }
  for (const _CharT* __ps = __p + __pos; __ps != __p;)
  {
    if (!_Traits::eq(*--__ps, __c))
    {
      return static_cast<_SizeT>(__ps - __p);
    }
  }
  return __npos;
}

#ifndef __cuda_std__
template <class _Ptr>
_LIBCUDACXX_HIDE_FROM_ABI size_t __do_string_hash(_Ptr __p, _Ptr __e)
{
  typedef typename iterator_traits<_Ptr>::value_type value_type;
  return __murmur2_or_cityhash<size_t>()(__p, (__e - __p) * sizeof(value_type));
}
#endif // !__cuda_std__

template <class _CharT, class _Iter, class _Traits = char_traits<_CharT>>
struct __quoted_output_proxy
{
  _Iter __first;
  _Iter __last;
  _CharT __delim;
  _CharT __escape;

  _LIBCUDACXX_HIDE_FROM_ABI __quoted_output_proxy(_Iter __f, _Iter __l, _CharT __d, _CharT __e)
      : __first(__f)
      , __last(__l)
      , __delim(__d)
      , __escape(__e)
  {}
  //  This would be a nice place for a string_ref
};

_LIBCUDACXX_END_NAMESPACE_STD

_CCCL_POP_MACROS

#endif // _LIBCUDACXX___STRING
