libcxx/include/__string

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