libcxx/include/__string

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef _LIBCPP___STRING
  11 #define _LIBCPP___STRING
  12
  13 #include <__algorithm/copy.h>
  14 #include <__algorithm/copy_backward.h>
  15 #include <__algorithm/copy_n.h>
  16 #include <__algorithm/fill_n.h>
  17 #include <__algorithm/find_end.h>
  18 #include <__algorithm/find_first_of.h>
  19 #include <__algorithm/min.h>
  20 #include <__config>
  21 #include <__functional/hash.h>     // for __murmur2_or_cityhash
  22 #include <__iterator/iterator_traits.h>
  23 #include <cstdint>     // for uint_least16_t
  24 #include <cstdio>      // for EOF
  25 #include <cstring>     // for memcpy
  26 #include <iosfwd>      // for streampos & friends
  27 #include <type_traits> // for __libcpp_is_constant_evaluated
  28
  29 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
  30 #   include <cwchar> // for wmemcpy
  31 #endif
  32
  33 #include <__debug>
  34
  35 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  36 #pragma GCC system_header
  37 #endif
  38
  39 _LIBCPP_PUSH_MACROS
  40 #include <__undef_macros>
  41
  42
  43 _LIBCPP_BEGIN_NAMESPACE_STD
  44
  45 // The extern template ABI lists are kept outside of <string> to improve the
  46 // readability of that header. We maintain 2 ABI lists:
  47 // - _LIBCPP_STRING_V1_EXTERN_TEMPLATE_LIST
  48 // - _LIBCPP_STRING_UNSTABLE_EXTERN_TEMPLATE_LIST
  49 // As the name implies, the ABI lists define the V1 (Stable) and unstable ABI.
  50 //
  51 // For unstable, we may explicitly remove function that are external in V1,
  52 // and add (new) external functions to better control inlining and compiler
  53 // optimization opportunities.
  54 //
  55 // For stable, the ABI list should rarely change, except for adding new
  56 // functions supporting new c++ version / API changes. Typically entries
  57 // must never be removed from the stable list.
  58 #define _LIBCPP_STRING_V1_EXTERN_TEMPLATE_LIST(_Func, _CharType) \
  59   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, value_type const*, size_type)) \
  60   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::rfind(value_type const*, size_type, size_type) const) \
  61   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(value_type const*, size_type, size_type)) \
  62   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::basic_string(basic_string const&)) \
  63   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, value_type const*)) \
  64   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::basic_string(basic_string const&, allocator<_CharType> const&)) \
  65   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_last_not_of(value_type const*, size_type, size_type) const) \
  66   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::~basic_string()) \
  67   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_first_not_of(value_type const*, size_type, size_type) const) \
  68   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, size_type, value_type)) \
  69   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::operator=(value_type)) \
  70   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(value_type const*, size_type)) \
  71   _Func(_LIBCPP_FUNC_VIS const _CharType& basic_string<_CharType>::at(size_type) const) \
  72   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*, size_type)) \
  73   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_first_of(value_type const*, size_type, size_type) const) \
  74   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, size_type, value_type)) \
  75   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(value_type const*, size_type)) \
  76   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::reserve(size_type)) \
  77   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*, size_type)) \
  78   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(basic_string const&, size_type, size_type)) \
  79   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::copy(value_type*, size_type, size_type) const) \
  80   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::basic_string(basic_string const&, size_type, size_type, allocator<_CharType> const&)) \
  81   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type, size_type) const) \
  82   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(size_type, value_type)) \
  83   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*)) \
  84   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_last_of(value_type const*, size_type, size_type) const) \
  85   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__grow_by(size_type, size_type, size_type, size_type, size_type, size_type)) \
  86   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__grow_by_and_replace(size_type, size_type, size_type, size_type, size_type, size_type, value_type const*)) \
  87   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::push_back(value_type)) \
  88   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(size_type, value_type)) \
  89   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::rfind(value_type, size_type) const) \
  90   _Func(_LIBCPP_FUNC_VIS const basic_string<_CharType>::size_type basic_string<_CharType>::npos) \
  91   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(size_type, value_type)) \
  92   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::erase(size_type, size_type)) \
  93   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(basic_string const&, size_type, size_type)) \
  94   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(value_type const*) const) \
  95   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*) const) \
  96   _Func(_LIBCPP_FUNC_VIS _CharType& basic_string<_CharType>::at(size_type)) \
  97   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(value_type const*)) \
  98   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type const*, size_type, size_type) const) \
  99   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, basic_string const&, size_type, size_type) const) \
 100   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*, size_type) const) \
 101   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::operator=(basic_string const&)) \
 102   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*)) \
 103   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, basic_string const&, size_type, size_type)) \
 104   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::iterator basic_string<_CharType>::insert(basic_string::const_iterator, value_type)) \
 105   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::resize(size_type, value_type)) \
 106   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, basic_string const&, size_type, size_type))
 107
 108 #define _LIBCPP_STRING_UNSTABLE_EXTERN_TEMPLATE_LIST(_Func, _CharType) \
 109   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, value_type const*, size_type)) \
 110   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::rfind(value_type const*, size_type, size_type) const) \
 111   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(value_type const*, size_type, size_type)) \
 112   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, value_type const*)) \
 113   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_last_not_of(value_type const*, size_type, size_type) const) \
 114   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::~basic_string()) \
 115   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_first_not_of(value_type const*, size_type, size_type) const) \
 116   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, size_type, value_type)) \
 117   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::operator=(value_type)) \
 118   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(value_type const*, size_type)) \
 119   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init_copy_ctor_external(value_type const*, size_type)) \
 120   _Func(_LIBCPP_FUNC_VIS const _CharType& basic_string<_CharType>::at(size_type) const) \
 121   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*, size_type)) \
 122   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_first_of(value_type const*, size_type, size_type) const) \
 123   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, size_type, value_type)) \
 124   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_external(value_type const*, size_type)) \
 125   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_external(value_type const*)) \
 126   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::reserve(size_type)) \
 127   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*, size_type)) \
 128   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(basic_string const&, size_type, size_type)) \
 129   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::copy(value_type*, size_type, size_type) const) \
 130   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::basic_string(basic_string const&, size_type, size_type, allocator<_CharType> const&)) \
 131   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type, size_type) const) \
 132   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(size_type, value_type)) \
 133   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*)) \
 134   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_last_of(value_type const*, size_type, size_type) const) \
 135   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__grow_by(size_type, size_type, size_type, size_type, size_type, size_type)) \
 136   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__grow_by_and_replace(size_type, size_type, size_type, size_type, size_type, size_type, value_type const*)) \
 137   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_no_alias<false>(value_type const*, size_type)) \
 138   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_no_alias<true>(value_type const*, size_type)) \
 139   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::push_back(value_type)) \
 140   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(size_type, value_type)) \
 141   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::rfind(value_type, size_type) const) \
 142   _Func(_LIBCPP_FUNC_VIS const basic_string<_CharType>::size_type basic_string<_CharType>::npos) \
 143   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(size_type, value_type)) \
 144   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__erase_external_with_move(size_type, size_type)) \
 145   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(basic_string const&, size_type, size_type)) \
 146   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(value_type const*) const) \
 147   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*) const) \
 148   _Func(_LIBCPP_FUNC_VIS _CharType& basic_string<_CharType>::at(size_type)) \
 149   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type const*, size_type, size_type) const) \
 150   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, basic_string const&, size_type, size_type) const) \
 151   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*, size_type) const) \
 152   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*)) \
 153   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, basic_string const&, size_type, size_type)) \
 154   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::iterator basic_string<_CharType>::insert(basic_string::const_iterator, value_type)) \
 155   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::resize(size_type, value_type)) \
 156   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, basic_string const&, size_type, size_type))
 157
 158
 159 // char_traits
 160
 161 template <class _CharT>
 162 struct _LIBCPP_TEMPLATE_VIS char_traits
 163 {
 164     typedef _CharT    char_type;
 165     typedef int       int_type;
 166     typedef streamoff off_type;
 167     typedef streampos pos_type;
 168     typedef mbstate_t state_type;
 169
 170     static inline void _LIBCPP_CONSTEXPR_AFTER_CXX14
 171         assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 172     static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 173         {return __c1 == __c2;}
 174     static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 175         {return __c1 < __c2;}
 176
 177     static _LIBCPP_CONSTEXPR_AFTER_CXX14
 178     int compare(const char_type* __s1, const char_type* __s2, size_t __n);
 179     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 180     size_t length(const char_type* __s);
 181     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 182     const char_type* find(const char_type* __s, size_t __n, const char_type& __a);
 183     static _LIBCPP_CONSTEXPR_AFTER_CXX17
 184     char_type*       move(char_type* __s1, const char_type* __s2, size_t __n);
 185     _LIBCPP_INLINE_VISIBILITY
 186     static _LIBCPP_CONSTEXPR_AFTER_CXX17
 187     char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n);
 188     _LIBCPP_INLINE_VISIBILITY
 189     static _LIBCPP_CONSTEXPR_AFTER_CXX17
 190     char_type*       assign(char_type* __s, size_t __n, char_type __a);
 191
 192     static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
 193         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 194     static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 195         {return char_type(__c);}
 196     static inline _LIBCPP_CONSTEXPR int_type  to_int_type(char_type __c) _NOEXCEPT
 197         {return int_type(__c);}
 198     static inline _LIBCPP_CONSTEXPR bool      eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 199         {return __c1 == __c2;}
 200     static inline _LIBCPP_CONSTEXPR int_type  eof() _NOEXCEPT
 201         {return int_type(EOF);}
 202 };
 203
 204 template <class _CharT>
 205 _LIBCPP_CONSTEXPR_AFTER_CXX14 int
 206 char_traits<_CharT>::compare(const char_type* __s1, const char_type* __s2, size_t __n)
 207 {
 208     for (; __n; --__n, ++__s1, ++__s2)
 209     {
 210         if (lt(*__s1, *__s2))
 211             return -1;
 212         if (lt(*__s2, *__s1))
 213             return 1;
 214     }
 215     return 0;
 216 }
 217
 218 template <class _CharT>
 219 inline
 220 _LIBCPP_CONSTEXPR_AFTER_CXX14 size_t
 221 char_traits<_CharT>::length(const char_type* __s)
 222 {
 223     size_t __len = 0;
 224     for (; !eq(*__s, char_type(0)); ++__s)
 225         ++__len;
 226     return __len;
 227 }
 228
 229 template <class _CharT>
 230 inline
 231 _LIBCPP_CONSTEXPR_AFTER_CXX14 const _CharT*
 232 char_traits<_CharT>::find(const char_type* __s, size_t __n, const char_type& __a)
 233 {
 234     for (; __n; --__n)
 235     {
 236         if (eq(*__s, __a))
 237             return __s;
 238         ++__s;
 239     }
 240     return nullptr;
 241 }
 242
 243 template <class _CharT>
 244 _LIBCPP_CONSTEXPR_AFTER_CXX17 _CharT*
 245 char_traits<_CharT>::move(char_type* __s1, const char_type* __s2, size_t __n)
 246 {
 247     if (__n == 0) return __s1;
 248     char_type* __r = __s1;
 249     if (__s1 < __s2)
 250     {
 251         for (; __n; --__n, ++__s1, ++__s2)
 252             assign(*__s1, *__s2);
 253     }
 254     else if (__s2 < __s1)
 255     {
 256         __s1 += __n;
 257         __s2 += __n;
 258         for (; __n; --__n)
 259             assign(*--__s1, *--__s2);
 260     }
 261     return __r;
 262 }
 263
 264 template <class _CharT>
 265 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 266 _CharT*
 267 char_traits<_CharT>::copy(char_type* __s1, const char_type* __s2, size_t __n)
 268 {
 269     if (!__libcpp_is_constant_evaluated()) {
 270         _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 271     }
 272     char_type* __r = __s1;
 273     for (; __n; --__n, ++__s1, ++__s2)
 274         assign(*__s1, *__s2);
 275     return __r;
 276 }
 277
 278 template <class _CharT>
 279 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 280 _CharT*
 281 char_traits<_CharT>::assign(char_type* __s, size_t __n, char_type __a)
 282 {
 283     char_type* __r = __s;
 284     for (; __n; --__n, ++__s)
 285         assign(*__s, __a);
 286     return __r;
 287 }
 288
 289 // constexpr versions of move/copy/assign.
 290
 291 template <class _CharT>
 292 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 293 _CharT* __copy_constexpr(_CharT* __dest, const _CharT* __source, size_t __n) _NOEXCEPT
 294 {
 295   _LIBCPP_ASSERT(__libcpp_is_constant_evaluated(), "__copy_constexpr() should always be constant evaluated");
 296   _VSTD::copy_n(__source, __n, __dest);
 297   return __dest;
 298 }
 299
 300 template <class _CharT>
 301 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 302 _CharT* __move_constexpr(_CharT* __dest, const _CharT* __source, size_t __n) _NOEXCEPT
 303 {
 304   _LIBCPP_ASSERT(__libcpp_is_constant_evaluated(), "__move_constexpr() should always be constant evaluated");
 305   if (__n == 0)
 306     return __dest;
 307   _CharT* __allocation = new _CharT[__n];
 308   _VSTD::__copy_constexpr(__allocation, __source, __n);
 309   _VSTD::__copy_constexpr(__dest, static_cast<const _CharT*>(__allocation), __n);
 310   delete[] __allocation;
 311   return __dest;
 312 }
 313
 314 template <class _CharT>
 315 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 316 _CharT* __assign_constexpr(_CharT* __s, size_t __n, _CharT __a) _NOEXCEPT
 317 {
 318   _LIBCPP_ASSERT(__libcpp_is_constant_evaluated(), "__assign_constexpr() should always be constant evaluated");
 319   _VSTD::fill_n(__s, __n, __a);
 320   return __s;
 321 }
 322
 323 // char_traits<char>
 324
 325 template <>
 326 struct _LIBCPP_TEMPLATE_VIS char_traits<char>
 327 {
 328     typedef char      char_type;
 329     typedef int       int_type;
 330     typedef streamoff off_type;
 331     typedef streampos pos_type;
 332     typedef mbstate_t state_type;
 333
 334     static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 335     void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 336     static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 337             {return __c1 == __c2;}
 338     static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 339         {return (unsigned char)__c1 < (unsigned char)__c2;}
 340
 341     static _LIBCPP_CONSTEXPR_AFTER_CXX14
 342     int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 343
 344     static inline size_t _LIBCPP_CONSTEXPR_AFTER_CXX14 length(const char_type* __s)  _NOEXCEPT {
 345       // GCC currently does not support __builtin_strlen during constant evaluation.
 346       // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=70816
 347 #ifdef _LIBCPP_COMPILER_GCC
 348       if (__libcpp_is_constant_evaluated()) {
 349         size_t __i = 0;
 350         for (; __s[__i] != char_type('\0'); ++__i)
 351             ;
 352         return __i;
 353       }
 354 #endif
 355       return __builtin_strlen(__s);
 356     }
 357
 358     static _LIBCPP_CONSTEXPR_AFTER_CXX14
 359     const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 360     static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 361     char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 362         {
 363             return __libcpp_is_constant_evaluated()
 364                        ? _VSTD::__move_constexpr(__s1, __s2, __n)
 365                        : __n == 0 ? __s1 : (char_type*)_VSTD::memmove(__s1, __s2, __n);
 366         }
 367     static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 368     char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 369         {
 370             if (!__libcpp_is_constant_evaluated()) {
 371                 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 372             }
 373             return __libcpp_is_constant_evaluated()
 374                        ? _VSTD::__copy_constexpr(__s1, __s2, __n)
 375                        : __n == 0 ? __s1 : (char_type*)_VSTD::memcpy(__s1, __s2, __n);
 376         }
 377     static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 378     char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
 379         {
 380             return __libcpp_is_constant_evaluated()
 381                        ? _VSTD::__assign_constexpr(__s, __n, __a)
 382                        : __n == 0 ? __s : (char_type*)_VSTD::memset(__s, to_int_type(__a), __n);
 383         }
 384
 385     static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
 386         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 387     static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 388         {return char_type(__c);}
 389     static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 390         {return int_type((unsigned char)__c);}
 391     static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 392         {return __c1 == __c2;}
 393     static inline _LIBCPP_CONSTEXPR int_type  eof() _NOEXCEPT
 394         {return int_type(EOF);}
 395 };
 396
 397 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 398 int
 399 char_traits<char>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 400 {
 401     if (__n == 0)
 402         return 0;
 403 #if __has_feature(cxx_constexpr_string_builtins)
 404     return __builtin_memcmp(__s1, __s2, __n);
 405 #elif _LIBCPP_STD_VER <= 14
 406     return _VSTD::memcmp(__s1, __s2, __n);
 407 #else
 408     for (; __n; --__n, ++__s1, ++__s2)
 409     {
 410         if (lt(*__s1, *__s2))
 411             return -1;
 412         if (lt(*__s2, *__s1))
 413             return 1;
 414     }
 415     return 0;
 416 #endif
 417 }
 418
 419 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 420 const char*
 421 char_traits<char>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
 422 {
 423     if (__n == 0)
 424         return nullptr;
 425 #if __has_feature(cxx_constexpr_string_builtins)
 426     return __builtin_char_memchr(__s, to_int_type(__a), __n);
 427 #elif _LIBCPP_STD_VER <= 14
 428     return (const char_type*) _VSTD::memchr(__s, to_int_type(__a), __n);
 429 #else
 430     for (; __n; --__n)
 431     {
 432         if (eq(*__s, __a))
 433             return __s;
 434         ++__s;
 435     }
 436     return nullptr;
 437 #endif
 438 }
 439
 440
 441 // char_traits<wchar_t>
 442
 443 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 444 template <>
 445 struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t>
 446 {
 447     typedef wchar_t   char_type;
 448     typedef wint_t    int_type;
 449     typedef streamoff off_type;
 450     typedef streampos pos_type;
 451     typedef mbstate_t state_type;
 452
 453     static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 454     void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 455     static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 456         {return __c1 == __c2;}
 457     static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 458         {return __c1 < __c2;}
 459
 460     static _LIBCPP_CONSTEXPR_AFTER_CXX14
 461     int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 462     static _LIBCPP_CONSTEXPR_AFTER_CXX14
 463     size_t length(const char_type* __s) _NOEXCEPT;
 464     static _LIBCPP_CONSTEXPR_AFTER_CXX14
 465     const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 466     static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 467     char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 468         {
 469             return __libcpp_is_constant_evaluated()
 470                        ? _VSTD::__move_constexpr(__s1, __s2, __n)
 471                        : __n == 0 ? __s1 : _VSTD::wmemmove(__s1, __s2, __n);
 472         }
 473     static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 474     char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 475         {
 476             if (!__libcpp_is_constant_evaluated()) {
 477                 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 478             }
 479             return __libcpp_is_constant_evaluated()
 480                        ? _VSTD::__copy_constexpr(__s1, __s2, __n)
 481                        : __n == 0 ? __s1 : _VSTD::wmemcpy(__s1, __s2, __n);
 482         }
 483     static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 484     char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
 485         {
 486             return __libcpp_is_constant_evaluated()
 487                        ? _VSTD::__assign_constexpr(__s, __n, __a)
 488                        : __n == 0 ? __s : _VSTD::wmemset(__s, __a, __n);
 489         }
 490     static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
 491         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 492     static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 493         {return char_type(__c);}
 494     static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 495         {return int_type(__c);}
 496     static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 497         {return __c1 == __c2;}
 498     static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
 499         {return int_type(WEOF);}
 500 };
 501
 502 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 503 int
 504 char_traits<wchar_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 505 {
 506     if (__n == 0)
 507         return 0;
 508 #if __has_feature(cxx_constexpr_string_builtins)
 509     return __builtin_wmemcmp(__s1, __s2, __n);
 510 #elif _LIBCPP_STD_VER <= 14
 511     return _VSTD::wmemcmp(__s1, __s2, __n);
 512 #else
 513     for (; __n; --__n, ++__s1, ++__s2)
 514     {
 515         if (lt(*__s1, *__s2))
 516             return -1;
 517         if (lt(*__s2, *__s1))
 518             return 1;
 519     }
 520     return 0;
 521 #endif
 522 }
 523
 524 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 525 size_t
 526 char_traits<wchar_t>::length(const char_type* __s) _NOEXCEPT
 527 {
 528 #if __has_feature(cxx_constexpr_string_builtins)
 529     return __builtin_wcslen(__s);
 530 #elif _LIBCPP_STD_VER <= 14
 531     return _VSTD::wcslen(__s);
 532 #else
 533     size_t __len = 0;
 534     for (; !eq(*__s, char_type(0)); ++__s)
 535         ++__len;
 536     return __len;
 537 #endif
 538 }
 539
 540 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 541 const wchar_t*
 542 char_traits<wchar_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
 543 {
 544     if (__n == 0)
 545         return nullptr;
 546 #if __has_feature(cxx_constexpr_string_builtins)
 547     return __builtin_wmemchr(__s, __a, __n);
 548 #elif _LIBCPP_STD_VER <= 14
 549     return _VSTD::wmemchr(__s, __a, __n);
 550 #else
 551     for (; __n; --__n)
 552     {
 553         if (eq(*__s, __a))
 554             return __s;
 555         ++__s;
 556     }
 557     return nullptr;
 558 #endif
 559 }
 560 #endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS
 561
 562 template <class _Traits>
 563 _LIBCPP_INLINE_VISIBILITY
 564 _LIBCPP_CONSTEXPR
 565 inline size_t __char_traits_length_checked(const typename _Traits::char_type* __s) _NOEXCEPT {
 566 #if _LIBCPP_DEBUG_LEVEL >= 1
 567   return __s ? _Traits::length(__s) : (_VSTD::__libcpp_debug_function(_VSTD::__libcpp_debug_info(__FILE__, __LINE__, "p == nullptr", "null pointer pass to non-null argument of char_traits<...>::length")), 0);
 568 #else
 569   return _Traits::length(__s);
 570 #endif
 571 }
 572
 573 #ifndef _LIBCPP_HAS_NO_CHAR8_T
 574
 575 template <>
 576 struct _LIBCPP_TEMPLATE_VIS char_traits<char8_t>
 577 {
 578     typedef char8_t        char_type;
 579     typedef unsigned int   int_type;
 580     typedef streamoff      off_type;
 581     typedef u8streampos    pos_type;
 582     typedef mbstate_t      state_type;
 583
 584     static inline constexpr void assign(char_type& __c1, const char_type& __c2) noexcept
 585         {__c1 = __c2;}
 586     static inline constexpr bool eq(char_type __c1, char_type __c2) noexcept
 587         {return __c1 == __c2;}
 588     static inline constexpr bool lt(char_type __c1, char_type __c2) noexcept
 589         {return __c1 < __c2;}
 590
 591     static constexpr
 592     int              compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 593
 594     static constexpr
 595     size_t           length(const char_type* __s) _NOEXCEPT;
 596
 597     _LIBCPP_INLINE_VISIBILITY static constexpr
 598     const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 599
 600     static _LIBCPP_CONSTEXPR_AFTER_CXX17
 601     char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 602         {
 603             return __libcpp_is_constant_evaluated()
 604                        ? _VSTD::__move_constexpr(__s1, __s2, __n)
 605                        : __n == 0 ? __s1 : (char_type*)_VSTD::memmove(__s1, __s2, __n);
 606         }
 607
 608     static _LIBCPP_CONSTEXPR_AFTER_CXX17
 609     char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 610         {
 611             if (!__libcpp_is_constant_evaluated()) {
 612                 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 613             }
 614             return __libcpp_is_constant_evaluated()
 615                        ? _VSTD::__copy_constexpr(__s1, __s2, __n)
 616                        : __n == 0 ? __s1 : (char_type*)_VSTD::memcpy(__s1, __s2, __n);
 617         }
 618
 619     static _LIBCPP_CONSTEXPR_AFTER_CXX17
 620     char_type*       assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
 621         {
 622             return __libcpp_is_constant_evaluated()
 623                        ? _VSTD::__assign_constexpr(__s, __n, __a)
 624                        : __n == 0 ? __s : (char_type*)_VSTD::memset(__s, to_int_type(__a), __n);
 625         }
 626
 627     static inline constexpr int_type  not_eof(int_type __c) noexcept
 628         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 629     static inline constexpr char_type to_char_type(int_type __c) noexcept
 630         {return char_type(__c);}
 631     static inline constexpr int_type to_int_type(char_type __c) noexcept
 632         {return int_type(__c);}
 633     static inline constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept
 634         {return __c1 == __c2;}
 635     static inline constexpr int_type eof() noexcept
 636         {return int_type(EOF);}
 637 };
 638
 639 // TODO use '__builtin_strlen' if it ever supports char8_t ??
 640 inline constexpr
 641 size_t
 642 char_traits<char8_t>::length(const char_type* __s) _NOEXCEPT
 643 {
 644     size_t __len = 0;
 645     for (; !eq(*__s, char_type(0)); ++__s)
 646         ++__len;
 647     return __len;
 648 }
 649
 650 inline constexpr
 651 int
 652 char_traits<char8_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 653 {
 654 #if __has_feature(cxx_constexpr_string_builtins)
 655     return __builtin_memcmp(__s1, __s2, __n);
 656 #else
 657     for (; __n; --__n, ++__s1, ++__s2)
 658     {
 659         if (lt(*__s1, *__s2))
 660             return -1;
 661         if (lt(*__s2, *__s1))
 662             return 1;
 663     }
 664     return 0;
 665 #endif
 666 }
 667
 668 // TODO use '__builtin_char_memchr' if it ever supports char8_t ??
 669 inline constexpr
 670 const char8_t*
 671 char_traits<char8_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
 672 {
 673     for (; __n; --__n)
 674     {
 675         if (eq(*__s, __a))
 676             return __s;
 677         ++__s;
 678     }
 679     return nullptr;
 680 }
 681
 682 #endif // #_LIBCPP_HAS_NO_CHAR8_T
 683
 684 #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
 685
 686 template <>
 687 struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t>
 688 {
 689     typedef char16_t       char_type;
 690     typedef uint_least16_t int_type;
 691     typedef streamoff      off_type;
 692     typedef u16streampos   pos_type;
 693     typedef mbstate_t      state_type;
 694
 695     static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 696     void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 697     static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 698         {return __c1 == __c2;}
 699     static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 700         {return __c1 < __c2;}
 701
 702     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 703     int              compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 704     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 705     size_t           length(const char_type* __s) _NOEXCEPT;
 706     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 707     const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 708     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 709     static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 710     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 711     static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 712     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 713     static char_type*       assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
 714
 715     static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
 716         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 717     static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 718         {return char_type(__c);}
 719     static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 720         {return int_type(__c);}
 721     static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 722         {return __c1 == __c2;}
 723     static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
 724         {return int_type(0xFFFF);}
 725 };
 726
 727 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 728 int
 729 char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 730 {
 731     for (; __n; --__n, ++__s1, ++__s2)
 732     {
 733         if (lt(*__s1, *__s2))
 734             return -1;
 735         if (lt(*__s2, *__s1))
 736             return 1;
 737     }
 738     return 0;
 739 }
 740
 741 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 742 size_t
 743 char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT
 744 {
 745     size_t __len = 0;
 746     for (; !eq(*__s, char_type(0)); ++__s)
 747         ++__len;
 748     return __len;
 749 }
 750
 751 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 752 const char16_t*
 753 char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
 754 {
 755     for (; __n; --__n)
 756     {
 757         if (eq(*__s, __a))
 758             return __s;
 759         ++__s;
 760     }
 761     return nullptr;
 762 }
 763
 764 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 765 char16_t*
 766 char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 767 {
 768     if (__n == 0) return __s1;
 769     char_type* __r = __s1;
 770     if (__s1 < __s2)
 771     {
 772         for (; __n; --__n, ++__s1, ++__s2)
 773             assign(*__s1, *__s2);
 774     }
 775     else if (__s2 < __s1)
 776     {
 777         __s1 += __n;
 778         __s2 += __n;
 779         for (; __n; --__n)
 780             assign(*--__s1, *--__s2);
 781     }
 782     return __r;
 783 }
 784
 785 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 786 char16_t*
 787 char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 788 {
 789     if (!__libcpp_is_constant_evaluated()) {
 790         _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 791     }
 792     char_type* __r = __s1;
 793     for (; __n; --__n, ++__s1, ++__s2)
 794         assign(*__s1, *__s2);
 795     return __r;
 796 }
 797
 798 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 799 char16_t*
 800 char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
 801 {
 802     char_type* __r = __s;
 803     for (; __n; --__n, ++__s)
 804         assign(*__s, __a);
 805     return __r;
 806 }
 807
 808 template <>
 809 struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t>
 810 {
 811     typedef char32_t       char_type;
 812     typedef uint_least32_t int_type;
 813     typedef streamoff      off_type;
 814     typedef u32streampos   pos_type;
 815     typedef mbstate_t      state_type;
 816
 817     static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 818     void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 819     static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 820         {return __c1 == __c2;}
 821     static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 822         {return __c1 < __c2;}
 823
 824     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 825     int              compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 826     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 827     size_t           length(const char_type* __s) _NOEXCEPT;
 828     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 829     const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 830     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 831     static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 832     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 833     static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 834     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 835     static char_type*       assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
 836
 837     static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
 838         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 839     static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 840         {return char_type(__c);}
 841     static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 842         {return int_type(__c);}
 843     static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 844         {return __c1 == __c2;}
 845     static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
 846         {return int_type(0xFFFFFFFF);}
 847 };
 848
 849 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 850 int
 851 char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 852 {
 853     for (; __n; --__n, ++__s1, ++__s2)
 854     {
 855         if (lt(*__s1, *__s2))
 856             return -1;
 857         if (lt(*__s2, *__s1))
 858             return 1;
 859     }
 860     return 0;
 861 }
 862
 863 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 864 size_t
 865 char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT
 866 {
 867     size_t __len = 0;
 868     for (; !eq(*__s, char_type(0)); ++__s)
 869         ++__len;
 870     return __len;
 871 }
 872
 873 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 874 const char32_t*
 875 char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
 876 {
 877     for (; __n; --__n)
 878     {
 879         if (eq(*__s, __a))
 880             return __s;
 881         ++__s;
 882     }
 883     return nullptr;
 884 }
 885
 886 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 887 char32_t*
 888 char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 889 {
 890     if (__n == 0) return __s1;
 891     char_type* __r = __s1;
 892     if (__s1 < __s2)
 893     {
 894         for (; __n; --__n, ++__s1, ++__s2)
 895             assign(*__s1, *__s2);
 896     }
 897     else if (__s2 < __s1)
 898     {
 899         __s1 += __n;
 900         __s2 += __n;
 901         for (; __n; --__n)
 902             assign(*--__s1, *--__s2);
 903     }
 904     return __r;
 905 }
 906
 907 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 908 char32_t*
 909 char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 910 {
 911     if (!__libcpp_is_constant_evaluated()) {
 912         _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 913     }
 914     char_type* __r = __s1;
 915     for (; __n; --__n, ++__s1, ++__s2)
 916         assign(*__s1, *__s2);
 917     return __r;
 918 }
 919
 920 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
 921 char32_t*
 922 char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
 923 {
 924     char_type* __r = __s;
 925     for (; __n; --__n, ++__s)
 926         assign(*__s, __a);
 927     return __r;
 928 }
 929
 930 #endif // _LIBCPP_HAS_NO_UNICODE_CHARS
 931
 932 // helper fns for basic_string and string_view
 933
 934 // __str_find
 935 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 936 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 937 __str_find(const _CharT *__p, _SizeT __sz,
 938              _CharT __c, _SizeT __pos) _NOEXCEPT
 939 {
 940     if (__pos >= __sz)
 941         return __npos;
 942     const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
 943     if (__r == nullptr)
 944         return __npos;
 945     return static_cast<_SizeT>(__r - __p);
 946 }
 947
 948 template <class _CharT, class _Traits>
 949 inline _LIBCPP_CONSTEXPR_AFTER_CXX11 const _CharT *
 950 __search_substring(const _CharT *__first1, const _CharT *__last1,
 951                    const _CharT *__first2, const _CharT *__last2) _NOEXCEPT {
 952   // Take advantage of knowing source and pattern lengths.
 953   // Stop short when source is smaller than pattern.
 954   const ptrdiff_t __len2 = __last2 - __first2;
 955   if (__len2 == 0)
 956     return __first1;
 957
 958   ptrdiff_t __len1 = __last1 - __first1;
 959   if (__len1 < __len2)
 960     return __last1;
 961
 962   // First element of __first2 is loop invariant.
 963   _CharT __f2 = *__first2;
 964   while (true) {
 965     __len1 = __last1 - __first1;
 966     // Check whether __first1 still has at least __len2 bytes.
 967     if (__len1 < __len2)
 968       return __last1;
 969
 970     // Find __f2 the first byte matching in __first1.
 971     __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
 972     if (__first1 == nullptr)
 973       return __last1;
 974
 975     // It is faster to compare from the first byte of __first1 even if we
 976     // already know that it matches the first byte of __first2: this is because
 977     // __first2 is most likely aligned, as it is user's "pattern" string, and
 978     // __first1 + 1 is most likely not aligned, as the match is in the middle of
 979     // the string.
 980     if (_Traits::compare(__first1, __first2, __len2) == 0)
 981       return __first1;
 982
 983     ++__first1;
 984   }
 985 }
 986
 987 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 988 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 989 __str_find(const _CharT *__p, _SizeT __sz,
 990        const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 991 {
 992     if (__pos > __sz)
 993         return __npos;
 994
 995     if (__n == 0) // There is nothing to search, just return __pos.
 996         return __pos;
 997
 998     const _CharT *__r = __search_substring<_CharT, _Traits>(
 999         __p + __pos, __p + __sz, __s, __s + __n);
1000
1001     if (__r == __p + __sz)
1002         return __npos;
1003     return static_cast<_SizeT>(__r - __p);
1004 }
1005
1006
1007 // __str_rfind
1008
1009 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1010 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1011 __str_rfind(const _CharT *__p, _SizeT __sz,
1012               _CharT __c, _SizeT __pos) _NOEXCEPT
1013 {
1014     if (__sz < 1)
1015         return __npos;
1016     if (__pos < __sz)
1017         ++__pos;
1018     else
1019         __pos = __sz;
1020     for (const _CharT* __ps = __p + __pos; __ps != __p;)
1021     {
1022         if (_Traits::eq(*--__ps, __c))
1023             return static_cast<_SizeT>(__ps - __p);
1024     }
1025     return __npos;
1026 }
1027
1028 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1029 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1030 __str_rfind(const _CharT *__p, _SizeT __sz,
1031         const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
1032 {
1033     __pos = _VSTD::min(__pos, __sz);
1034     if (__n < __sz - __pos)
1035         __pos += __n;
1036     else
1037         __pos = __sz;
1038     const _CharT* __r = _VSTD::__find_end(
1039                   __p, __p + __pos, __s, __s + __n, _Traits::eq,
1040                         random_access_iterator_tag(), random_access_iterator_tag());
1041     if (__n > 0 && __r == __p + __pos)
1042         return __npos;
1043     return static_cast<_SizeT>(__r - __p);
1044 }
1045
1046 // __str_find_first_of
1047 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1048 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1049 __str_find_first_of(const _CharT *__p, _SizeT __sz,
1050                 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
1051 {
1052     if (__pos >= __sz || __n == 0)
1053         return __npos;
1054     const _CharT* __r = _VSTD::__find_first_of_ce
1055         (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq );
1056     if (__r == __p + __sz)
1057         return __npos;
1058     return static_cast<_SizeT>(__r - __p);
1059 }
1060
1061
1062 // __str_find_last_of
1063 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1064 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1065 __str_find_last_of(const _CharT *__p, _SizeT __sz,
1066                const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
1067     {
1068     if (__n != 0)
1069     {
1070         if (__pos < __sz)
1071             ++__pos;
1072         else
1073             __pos = __sz;
1074         for (const _CharT* __ps = __p + __pos; __ps != __p;)
1075         {
1076             const _CharT* __r = _Traits::find(__s, __n, *--__ps);
1077             if (__r)
1078                 return static_cast<_SizeT>(__ps - __p);
1079         }
1080     }
1081     return __npos;
1082 }
1083
1084
1085 // __str_find_first_not_of
1086 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1087 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1088 __str_find_first_not_of(const _CharT *__p, _SizeT __sz,
1089                     const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
1090 {
1091     if (__pos < __sz)
1092     {
1093         const _CharT* __pe = __p + __sz;
1094         for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
1095             if (_Traits::find(__s, __n, *__ps) == nullptr)
1096                 return static_cast<_SizeT>(__ps - __p);
1097     }
1098     return __npos;
1099 }
1100
1101
1102 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1103 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1104 __str_find_first_not_of(const _CharT *__p, _SizeT __sz,
1105                           _CharT __c, _SizeT __pos) _NOEXCEPT
1106 {
1107     if (__pos < __sz)
1108     {
1109         const _CharT* __pe = __p + __sz;
1110         for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
1111             if (!_Traits::eq(*__ps, __c))
1112                 return static_cast<_SizeT>(__ps - __p);
1113     }
1114     return __npos;
1115 }
1116
1117
1118 // __str_find_last_not_of
1119 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1120 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1121 __str_find_last_not_of(const _CharT *__p, _SizeT __sz,
1122                    const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
1123 {
1124     if (__pos < __sz)
1125         ++__pos;
1126     else
1127         __pos = __sz;
1128     for (const _CharT* __ps = __p + __pos; __ps != __p;)
1129         if (_Traits::find(__s, __n, *--__ps) == nullptr)
1130             return static_cast<_SizeT>(__ps - __p);
1131     return __npos;
1132 }
1133
1134
1135 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1136 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1137 __str_find_last_not_of(const _CharT *__p, _SizeT __sz,
1138                          _CharT __c, _SizeT __pos) _NOEXCEPT
1139 {
1140     if (__pos < __sz)
1141         ++__pos;
1142     else
1143         __pos = __sz;
1144     for (const _CharT* __ps = __p + __pos; __ps != __p;)
1145         if (!_Traits::eq(*--__ps, __c))
1146             return static_cast<_SizeT>(__ps - __p);
1147     return __npos;
1148 }
1149
1150 template<class _Ptr>
1151 inline _LIBCPP_INLINE_VISIBILITY
1152 size_t __do_string_hash(_Ptr __p, _Ptr __e)
1153 {
1154     typedef typename iterator_traits<_Ptr>::value_type value_type;
1155     return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type));
1156 }
1157
1158 template <class _CharT, class _Iter, class _Traits=char_traits<_CharT> >
1159 struct __quoted_output_proxy
1160 {
1161     _Iter  __first;
1162     _Iter  __last;
1163     _CharT  __delim;
1164     _CharT  __escape;
1165
1166     __quoted_output_proxy(_Iter __f, _Iter __l, _CharT __d, _CharT __e)
1167     : __first(__f), __last(__l), __delim(__d), __escape(__e) {}
1168     //  This would be a nice place for a string_ref
1169 };
1170
1171 _LIBCPP_END_NAMESPACE_STD
1172
1173 _LIBCPP_POP_MACROS
1174
1175 #endif // _LIBCPP___STRING