libcxx/include/__string/char_traits.h

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef _LIBCPP___STRING_CHAR_TRAITS_H
  10 #define _LIBCPP___STRING_CHAR_TRAITS_H
  11
  12 #include <__algorithm/copy_n.h>
  13 #include <__algorithm/fill_n.h>
  14 #include <__algorithm/find_end.h>
  15 #include <__algorithm/find_first_of.h>
  16 #include <__algorithm/min.h>
  17 #include <__compare/ordering.h>
  18 #include <__config>
  19 #include <__functional/hash.h>
  20 #include <__iterator/iterator_traits.h>
  21 #include <__string/constexpr_c_functions.h>
  22 #include <__type_traits/is_constant_evaluated.h>
  23 #include <cstddef>
  24 #include <cstdint>
  25 #include <cstdio>
  26 #include <iosfwd>
  27
  28 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
  29 #   include <cwchar> // for wmemcpy
  30 #endif
  31
  32 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  33 #  pragma GCC system_header
  34 #endif
  35
  36 _LIBCPP_PUSH_MACROS
  37 #include <__undef_macros>
  38
  39 _LIBCPP_BEGIN_NAMESPACE_STD
  40
  41 template <class _CharT>
  42 struct char_traits;
  43 /*
  44 The Standard does not define the base template for char_traits because it is impossible to provide
  45 a correct definition for arbitrary character types. Instead, it requires implementations to provide
  46 specializations for predefined character types like `char`, `wchar_t` and others. We provide this as
  47 exposition-only to document what members a char_traits specialization should provide:
  48 {
  49     using char_type  = _CharT;
  50     using int_type   = ...;
  51     using off_type   = ...;
  52     using pos_type   = ...;
  53     using state_type = ...;
  54
  55     static void assign(char_type&, const char_type&);
  56     static bool eq(char_type, char_type);
  57     static bool lt(char_type, char_type);
  58
  59     static int              compare(const char_type*, const char_type*, size_t);
  60     static size_t           length(const char_type*);
  61     static const char_type* find(const char_type*, size_t, const char_type&);
  62     static char_type*       move(char_type*, const char_type*, size_t);
  63     static char_type*       copy(char_type*, const char_type*, size_t);
  64     static char_type*       assign(char_type*, size_t, char_type);
  65
  66     static int_type  not_eof(int_type);
  67     static char_type to_char_type(int_type);
  68     static int_type  to_int_type(char_type);
  69     static bool      eq_int_type(int_type, int_type);
  70     static int_type  eof();
  71 };
  72 */
  73
  74 //
  75 // Temporary extension to provide a base template for std::char_traits.
  76 // TODO(LLVM-19): Remove this class.
  77 //
  78 #if !defined(_LIBCPP_CHAR_TRAITS_REMOVE_BASE_SPECIALIZATION)
  79 template <class _CharT>
  80 struct _LIBCPP_DEPRECATED_("char_traits<T> for T not equal to char, wchar_t, char8_t, char16_t or char32_t is non-standard and is provided for a temporary period. It will be removed in LLVM 18, so please migrate off of it.")
  81     char_traits
  82 {
  83     using char_type  = _CharT;
  84     using int_type   = int;
  85     using off_type   = streamoff;
  86     using pos_type   = streampos;
  87     using state_type = mbstate_t;
  88
  89     static inline void _LIBCPP_CONSTEXPR_SINCE_CXX17 _LIBCPP_HIDE_FROM_ABI
  90         assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
  91     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
  92         {return __c1 == __c2;}
  93     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
  94         {return __c1 < __c2;}
  95
  96     static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17
  97     int compare(const char_type* __s1, const char_type* __s2, size_t __n) {
  98         for (; __n; --__n, ++__s1, ++__s2)
  99         {
 100             if (lt(*__s1, *__s2))
 101                 return -1;
 102             if (lt(*__s2, *__s1))
 103                 return 1;
 104         }
 105         return 0;
 106     }
 107     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_SINCE_CXX17
 108     size_t length(const char_type* __s) {
 109         size_t __len = 0;
 110         for (; !eq(*__s, char_type(0)); ++__s)
 111             ++__len;
 112         return __len;
 113     }
 114     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_SINCE_CXX17
 115     const char_type* find(const char_type* __s, size_t __n, const char_type& __a) {
 116         for (; __n; --__n)
 117         {
 118             if (eq(*__s, __a))
 119                 return __s;
 120             ++__s;
 121         }
 122         return nullptr;
 123     }
 124     static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 125     char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) {
 126         if (__n == 0) return __s1;
 127         char_type* __r = __s1;
 128         if (__s1 < __s2)
 129         {
 130             for (; __n; --__n, ++__s1, ++__s2)
 131                 assign(*__s1, *__s2);
 132         }
 133         else if (__s2 < __s1)
 134         {
 135             __s1 += __n;
 136             __s2 += __n;
 137             for (; __n; --__n)
 138                 assign(*--__s1, *--__s2);
 139         }
 140         return __r;
 141     }
 142     _LIBCPP_INLINE_VISIBILITY
 143     static _LIBCPP_CONSTEXPR_SINCE_CXX20
 144     char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) {
 145         if (!__libcpp_is_constant_evaluated()) {
 146             _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(
 147                 __s2 < __s1 || __s2 >= __s1 + __n, "char_traits::copy overlapped range");
 148         }
 149         char_type* __r = __s1;
 150         for (; __n; --__n, ++__s1, ++__s2)
 151             assign(*__s1, *__s2);
 152         return __r;
 153     }
 154     _LIBCPP_INLINE_VISIBILITY
 155     static _LIBCPP_CONSTEXPR_SINCE_CXX20
 156     char_type*       assign(char_type* __s, size_t __n, char_type __a) {
 157         char_type* __r = __s;
 158         for (; __n; --__n, ++__s)
 159             assign(*__s, __a);
 160         return __r;
 161     }
 162
 163     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
 164         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 165     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 166         {return char_type(__c);}
 167     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type  to_int_type(char_type __c) _NOEXCEPT
 168         {return int_type(__c);}
 169     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool      eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 170         {return __c1 == __c2;}
 171     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type  eof() _NOEXCEPT
 172         {return int_type(EOF);}
 173 };
 174 #endif // !defined(_LIBCPP_CHAR_TRAITS_REMOVE_BASE_SPECIALIZATION)
 175
 176 // char_traits<char>
 177
 178 template <>
 179 struct _LIBCPP_TEMPLATE_VIS char_traits<char>
 180 {
 181     using char_type           = char;
 182     using int_type            = int;
 183     using off_type            = streamoff;
 184     using pos_type            = streampos;
 185     using state_type          = mbstate_t;
 186 #if _LIBCPP_STD_VER >= 20
 187     using comparison_category = strong_ordering;
 188 #endif
 189
 190     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17
 191     void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 192
 193     // TODO: Make this _LIBCPP_HIDE_FROM_ABI
 194     static inline _LIBCPP_HIDDEN _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 195             {return __c1 == __c2;}
 196     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 197         {return (unsigned char)__c1 < (unsigned char)__c2;}
 198
 199     // __constexpr_memcmp requires a trivially lexicographically comparable type, but char is not when char is a signed type
 200     static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 int
 201     compare(const char_type* __lhs, const char_type* __rhs, size_t __count) _NOEXCEPT {
 202       if (__libcpp_is_constant_evaluated()) {
 203 #ifdef _LIBCPP_COMPILER_CLANG_BASED
 204         return __builtin_memcmp(__lhs, __rhs, __count);
 205 #else
 206         while (__count != 0) {
 207           if (lt(*__lhs, *__rhs))
 208             return -1;
 209           if (lt(*__rhs, *__lhs))
 210             return 1;
 211
 212           __count -= sizeof(char_type);
 213           ++__lhs;
 214           ++__rhs;
 215         }
 216         return 0;
 217 #endif // _LIBCPP_COMPILER_CLANG_BASED
 218       } else {
 219         return __builtin_memcmp(__lhs, __rhs, __count);
 220       }
 221     }
 222
 223     static inline _LIBCPP_HIDE_FROM_ABI size_t _LIBCPP_CONSTEXPR_SINCE_CXX17 length(const char_type* __s)  _NOEXCEPT {
 224       return std::__constexpr_strlen(__s);
 225     }
 226
 227     static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17
 228     const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
 229       if (__n == 0)
 230           return nullptr;
 231       return std::__constexpr_memchr(__s, __a, __n);
 232     }
 233
 234     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 235     char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 236         return std::__constexpr_memmove(__s1, __s2, __element_count(__n));
 237     }
 238
 239     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 240     char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 241         if (!__libcpp_is_constant_evaluated())
 242             _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(
 243                 __s2 < __s1 || __s2 >= __s1 + __n, "char_traits::copy overlapped range");
 244         std::copy_n(__s2, __n, __s1);
 245         return __s1;
 246     }
 247
 248     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 249     char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT {
 250         std::fill_n(__s, __n, __a);
 251         return __s;
 252     }
 253
 254     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
 255         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 256     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 257         {return char_type(__c);}
 258     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 259         {return int_type((unsigned char)__c);}
 260     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 261         {return __c1 == __c2;}
 262     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type  eof() _NOEXCEPT
 263         {return int_type(EOF);}
 264 };
 265
 266 // char_traits<wchar_t>
 267
 268 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 269 template <>
 270 struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t>
 271 {
 272     using char_type           = wchar_t;
 273     using int_type            = wint_t;
 274     using off_type            = streamoff;
 275     using pos_type            = streampos;
 276     using state_type          = mbstate_t;
 277 #if _LIBCPP_STD_VER >= 20
 278     using comparison_category = strong_ordering;
 279 #endif
 280
 281     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17
 282     void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 283     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 284         {return __c1 == __c2;}
 285     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 286         {return __c1 < __c2;}
 287
 288   static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 int
 289   compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 290     if (__n == 0)
 291       return 0;
 292     return std::__constexpr_wmemcmp(__s1, __s2, __n);
 293   }
 294
 295   static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t length(const char_type* __s) _NOEXCEPT {
 296     return std::__constexpr_wcslen(__s);
 297   }
 298
 299   static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17
 300   const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
 301     if (__n == 0)
 302         return nullptr;
 303     return std::__constexpr_wmemchr(__s, __a, __n);
 304   }
 305
 306     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 307     char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 308         return std::__constexpr_memmove(__s1, __s2, __element_count(__n));
 309     }
 310
 311     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 312     char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 313         if (!__libcpp_is_constant_evaluated())
 314             _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(
 315                 __s2 < __s1 || __s2 >= __s1 + __n, "char_traits::copy overlapped range");
 316         std::copy_n(__s2, __n, __s1);
 317         return __s1;
 318     }
 319
 320     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 321     char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT {
 322         std::fill_n(__s, __n, __a);
 323         return __s;
 324     }
 325
 326     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
 327         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 328     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 329         {return char_type(__c);}
 330     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 331         {return int_type(__c);}
 332     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 333         {return __c1 == __c2;}
 334     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
 335         {return int_type(WEOF);}
 336 };
 337 #endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS
 338
 339 #ifndef _LIBCPP_HAS_NO_CHAR8_T
 340
 341 template <>
 342 struct _LIBCPP_TEMPLATE_VIS char_traits<char8_t>
 343 {
 344     using char_type           = char8_t;
 345     using int_type            = unsigned int;
 346     using off_type            = streamoff;
 347     using pos_type            = u8streampos;
 348     using state_type          = mbstate_t;
 349 #if _LIBCPP_STD_VER >= 20
 350     using comparison_category = strong_ordering;
 351 #endif
 352
 353     static inline _LIBCPP_HIDE_FROM_ABI constexpr void assign(char_type& __c1, const char_type& __c2) noexcept
 354         {__c1 = __c2;}
 355     static inline _LIBCPP_HIDE_FROM_ABI constexpr bool eq(char_type __c1, char_type __c2) noexcept
 356         {return __c1 == __c2;}
 357     static inline _LIBCPP_HIDE_FROM_ABI constexpr bool lt(char_type __c1, char_type __c2) noexcept
 358         {return __c1 < __c2;}
 359
 360   static _LIBCPP_HIDE_FROM_ABI constexpr int
 361   compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 362       return std::__constexpr_memcmp(__s1, __s2, __element_count(__n));
 363   }
 364
 365     static _LIBCPP_HIDE_FROM_ABI constexpr
 366     size_t           length(const char_type* __s) _NOEXCEPT;
 367
 368     _LIBCPP_INLINE_VISIBILITY static constexpr
 369     const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 370
 371     static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 372     char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 373         return std::__constexpr_memmove(__s1, __s2, __element_count(__n));
 374     }
 375
 376     static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 377     char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 378         if (!__libcpp_is_constant_evaluated())
 379             _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(
 380                 __s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 381         std::copy_n(__s2, __n, __s1);
 382         return __s1;
 383     }
 384
 385     static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 386     char_type*       assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT {
 387         std::fill_n(__s, __n, __a);
 388         return __s;
 389     }
 390
 391     static inline _LIBCPP_HIDE_FROM_ABI constexpr int_type  not_eof(int_type __c) noexcept
 392         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 393     static inline _LIBCPP_HIDE_FROM_ABI constexpr char_type to_char_type(int_type __c) noexcept
 394         {return char_type(__c);}
 395     static inline _LIBCPP_HIDE_FROM_ABI constexpr int_type to_int_type(char_type __c) noexcept
 396         {return int_type(__c);}
 397     static inline _LIBCPP_HIDE_FROM_ABI constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept
 398         {return __c1 == __c2;}
 399     static inline _LIBCPP_HIDE_FROM_ABI constexpr int_type eof() noexcept
 400         {return int_type(EOF);}
 401 };
 402
 403 // TODO use '__builtin_strlen' if it ever supports char8_t ??
 404 inline constexpr
 405 size_t
 406 char_traits<char8_t>::length(const char_type* __s) _NOEXCEPT
 407 {
 408     size_t __len = 0;
 409     for (; !eq(*__s, char_type(0)); ++__s)
 410         ++__len;
 411     return __len;
 412 }
 413
 414 // TODO use '__builtin_char_memchr' if it ever supports char8_t ??
 415 inline constexpr
 416 const char8_t*
 417 char_traits<char8_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
 418 {
 419     for (; __n; --__n)
 420     {
 421         if (eq(*__s, __a))
 422             return __s;
 423         ++__s;
 424     }
 425     return nullptr;
 426 }
 427
 428 #endif // _LIBCPP_HAS_NO_CHAR8_T
 429
 430 template <>
 431 struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t>
 432 {
 433     using char_type           = char16_t;
 434     using int_type            = uint_least16_t;
 435     using off_type            = streamoff;
 436     using pos_type            = u16streampos;
 437     using state_type          = mbstate_t;
 438 #if _LIBCPP_STD_VER >= 20
 439     using comparison_category = strong_ordering;
 440 #endif
 441
 442     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17
 443     void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 444     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 445         {return __c1 == __c2;}
 446     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 447         {return __c1 < __c2;}
 448
 449     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_SINCE_CXX17
 450     int              compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 451     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_SINCE_CXX17
 452     size_t           length(const char_type* __s) _NOEXCEPT;
 453     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_SINCE_CXX17
 454     const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 455
 456     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 457     static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 458         return std::__constexpr_memmove(__s1, __s2, __element_count(__n));
 459     }
 460
 461     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 462     static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 463         if (!__libcpp_is_constant_evaluated())
 464             _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(
 465                 __s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 466         std::copy_n(__s2, __n, __s1);
 467         return __s1;
 468     }
 469
 470     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 471     static char_type*       assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT {
 472         std::fill_n(__s, __n, __a);
 473         return __s;
 474     }
 475
 476     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
 477         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 478     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 479         {return char_type(__c);}
 480     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 481         {return int_type(__c);}
 482     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 483         {return __c1 == __c2;}
 484     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
 485         {return int_type(0xFFFF);}
 486 };
 487
 488 inline _LIBCPP_CONSTEXPR_SINCE_CXX17
 489 int
 490 char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 491 {
 492     for (; __n; --__n, ++__s1, ++__s2)
 493     {
 494         if (lt(*__s1, *__s2))
 495             return -1;
 496         if (lt(*__s2, *__s1))
 497             return 1;
 498     }
 499     return 0;
 500 }
 501
 502 inline _LIBCPP_CONSTEXPR_SINCE_CXX17
 503 size_t
 504 char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT
 505 {
 506     size_t __len = 0;
 507     for (; !eq(*__s, char_type(0)); ++__s)
 508         ++__len;
 509     return __len;
 510 }
 511
 512 inline _LIBCPP_CONSTEXPR_SINCE_CXX17
 513 const char16_t*
 514 char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
 515 {
 516     for (; __n; --__n)
 517     {
 518         if (eq(*__s, __a))
 519             return __s;
 520         ++__s;
 521     }
 522     return nullptr;
 523 }
 524
 525 template <>
 526 struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t>
 527 {
 528     using char_type           = char32_t;
 529     using int_type            = uint_least32_t;
 530     using off_type            = streamoff;
 531     using pos_type            = u32streampos;
 532     using state_type          = mbstate_t;
 533 #if _LIBCPP_STD_VER >= 20
 534     using comparison_category = strong_ordering;
 535 #endif
 536
 537     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17
 538     void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 539     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 540         {return __c1 == __c2;}
 541     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 542         {return __c1 < __c2;}
 543
 544     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_SINCE_CXX17
 545     int              compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 546     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_SINCE_CXX17
 547     size_t           length(const char_type* __s) _NOEXCEPT;
 548     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_SINCE_CXX17
 549     const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 550
 551     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 552     static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 553         return std::__constexpr_memmove(__s1, __s2, __element_count(__n));
 554     }
 555
 556     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 557     static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 558         std::copy_n(__s2, __n, __s1);
 559         return __s1;
 560     }
 561
 562     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 563     static char_type*       assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT {
 564         std::fill_n(__s, __n, __a);
 565         return __s;
 566     }
 567
 568     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
 569         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 570     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 571         {return char_type(__c);}
 572     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 573         {return int_type(__c);}
 574     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 575         {return __c1 == __c2;}
 576     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
 577         {return int_type(0xFFFFFFFF);}
 578 };
 579
 580 inline _LIBCPP_CONSTEXPR_SINCE_CXX17
 581 int
 582 char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 583 {
 584     for (; __n; --__n, ++__s1, ++__s2)
 585     {
 586         if (lt(*__s1, *__s2))
 587             return -1;
 588         if (lt(*__s2, *__s1))
 589             return 1;
 590     }
 591     return 0;
 592 }
 593
 594 inline _LIBCPP_CONSTEXPR_SINCE_CXX17
 595 size_t
 596 char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT
 597 {
 598     size_t __len = 0;
 599     for (; !eq(*__s, char_type(0)); ++__s)
 600         ++__len;
 601     return __len;
 602 }
 603
 604 inline _LIBCPP_CONSTEXPR_SINCE_CXX17
 605 const char32_t*
 606 char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
 607 {
 608     for (; __n; --__n)
 609     {
 610         if (eq(*__s, __a))
 611             return __s;
 612         ++__s;
 613     }
 614     return nullptr;
 615 }
 616
 617 // helper fns for basic_string and string_view
 618
 619 // __str_find
 620 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 621 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_INLINE_VISIBILITY
 622 __str_find(const _CharT *__p, _SizeT __sz,
 623              _CharT __c, _SizeT __pos) _NOEXCEPT
 624 {
 625     if (__pos >= __sz)
 626         return __npos;
 627     const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
 628     if (__r == nullptr)
 629         return __npos;
 630     return static_cast<_SizeT>(__r - __p);
 631 }
 632
 633 template <class _CharT, class _Traits>
 634 _LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_SINCE_CXX14 const _CharT *
 635 __search_substring(const _CharT *__first1, const _CharT *__last1,
 636                    const _CharT *__first2, const _CharT *__last2) _NOEXCEPT {
 637   // Take advantage of knowing source and pattern lengths.
 638   // Stop short when source is smaller than pattern.
 639   const ptrdiff_t __len2 = __last2 - __first2;
 640   if (__len2 == 0)
 641     return __first1;
 642
 643   ptrdiff_t __len1 = __last1 - __first1;
 644   if (__len1 < __len2)
 645     return __last1;
 646
 647   // First element of __first2 is loop invariant.
 648   _CharT __f2 = *__first2;
 649   while (true) {
 650     __len1 = __last1 - __first1;
 651     // Check whether __first1 still has at least __len2 bytes.
 652     if (__len1 < __len2)
 653       return __last1;
 654
 655     // Find __f2 the first byte matching in __first1.
 656     __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
 657     if (__first1 == nullptr)
 658       return __last1;
 659
 660     // It is faster to compare from the first byte of __first1 even if we
 661     // already know that it matches the first byte of __first2: this is because
 662     // __first2 is most likely aligned, as it is user's "pattern" string, and
 663     // __first1 + 1 is most likely not aligned, as the match is in the middle of
 664     // the string.
 665     if (_Traits::compare(__first1, __first2, __len2) == 0)
 666       return __first1;
 667
 668     ++__first1;
 669   }
 670 }
 671
 672 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 673 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_INLINE_VISIBILITY
 674 __str_find(const _CharT *__p, _SizeT __sz,
 675        const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 676 {
 677     if (__pos > __sz)
 678         return __npos;
 679
 680     if (__n == 0) // There is nothing to search, just return __pos.
 681         return __pos;
 682
 683     const _CharT *__r = std::__search_substring<_CharT, _Traits>(
 684         __p + __pos, __p + __sz, __s, __s + __n);
 685
 686     if (__r == __p + __sz)
 687         return __npos;
 688     return static_cast<_SizeT>(__r - __p);
 689 }
 690
 691
 692 // __str_rfind
 693
 694 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 695 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_INLINE_VISIBILITY
 696 __str_rfind(const _CharT *__p, _SizeT __sz,
 697               _CharT __c, _SizeT __pos) _NOEXCEPT
 698 {
 699     if (__sz < 1)
 700         return __npos;
 701     if (__pos < __sz)
 702         ++__pos;
 703     else
 704         __pos = __sz;
 705     for (const _CharT* __ps = __p + __pos; __ps != __p;)
 706     {
 707         if (_Traits::eq(*--__ps, __c))
 708             return static_cast<_SizeT>(__ps - __p);
 709     }
 710     return __npos;
 711 }
 712
 713 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 714 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_INLINE_VISIBILITY
 715 __str_rfind(const _CharT *__p, _SizeT __sz,
 716         const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 717 {
 718     __pos = _VSTD::min(__pos, __sz);
 719     if (__n < __sz - __pos)
 720         __pos += __n;
 721     else
 722         __pos = __sz;
 723     const _CharT* __r = std::__find_end_classic(__p, __p + __pos, __s, __s + __n, _Traits::eq);
 724     if (__n > 0 && __r == __p + __pos)
 725         return __npos;
 726     return static_cast<_SizeT>(__r - __p);
 727 }
 728
 729 // __str_find_first_of
 730 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 731 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_INLINE_VISIBILITY
 732 __str_find_first_of(const _CharT *__p, _SizeT __sz,
 733                 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 734 {
 735     if (__pos >= __sz || __n == 0)
 736         return __npos;
 737     const _CharT* __r = _VSTD::__find_first_of_ce
 738         (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq );
 739     if (__r == __p + __sz)
 740         return __npos;
 741     return static_cast<_SizeT>(__r - __p);
 742 }
 743
 744
 745 // __str_find_last_of
 746 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 747 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_INLINE_VISIBILITY
 748 __str_find_last_of(const _CharT *__p, _SizeT __sz,
 749                const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 750     {
 751     if (__n != 0)
 752     {
 753         if (__pos < __sz)
 754             ++__pos;
 755         else
 756             __pos = __sz;
 757         for (const _CharT* __ps = __p + __pos; __ps != __p;)
 758         {
 759             const _CharT* __r = _Traits::find(__s, __n, *--__ps);
 760             if (__r)
 761                 return static_cast<_SizeT>(__ps - __p);
 762         }
 763     }
 764     return __npos;
 765 }
 766
 767
 768 // __str_find_first_not_of
 769 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 770 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_INLINE_VISIBILITY
 771 __str_find_first_not_of(const _CharT *__p, _SizeT __sz,
 772                     const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 773 {
 774     if (__pos < __sz)
 775     {
 776         const _CharT* __pe = __p + __sz;
 777         for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
 778             if (_Traits::find(__s, __n, *__ps) == nullptr)
 779                 return static_cast<_SizeT>(__ps - __p);
 780     }
 781     return __npos;
 782 }
 783
 784
 785 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 786 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_INLINE_VISIBILITY
 787 __str_find_first_not_of(const _CharT *__p, _SizeT __sz,
 788                           _CharT __c, _SizeT __pos) _NOEXCEPT
 789 {
 790     if (__pos < __sz)
 791     {
 792         const _CharT* __pe = __p + __sz;
 793         for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
 794             if (!_Traits::eq(*__ps, __c))
 795                 return static_cast<_SizeT>(__ps - __p);
 796     }
 797     return __npos;
 798 }
 799
 800
 801 // __str_find_last_not_of
 802 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 803 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_INLINE_VISIBILITY
 804 __str_find_last_not_of(const _CharT *__p, _SizeT __sz,
 805                    const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 806 {
 807     if (__pos < __sz)
 808         ++__pos;
 809     else
 810         __pos = __sz;
 811     for (const _CharT* __ps = __p + __pos; __ps != __p;)
 812         if (_Traits::find(__s, __n, *--__ps) == nullptr)
 813             return static_cast<_SizeT>(__ps - __p);
 814     return __npos;
 815 }
 816
 817
 818 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 819 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_INLINE_VISIBILITY
 820 __str_find_last_not_of(const _CharT *__p, _SizeT __sz,
 821                          _CharT __c, _SizeT __pos) _NOEXCEPT
 822 {
 823     if (__pos < __sz)
 824         ++__pos;
 825     else
 826         __pos = __sz;
 827     for (const _CharT* __ps = __p + __pos; __ps != __p;)
 828         if (!_Traits::eq(*--__ps, __c))
 829             return static_cast<_SizeT>(__ps - __p);
 830     return __npos;
 831 }
 832
 833 template<class _Ptr>
 834 inline _LIBCPP_INLINE_VISIBILITY
 835 size_t __do_string_hash(_Ptr __p, _Ptr __e)
 836 {
 837     typedef typename iterator_traits<_Ptr>::value_type value_type;
 838     return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type));
 839 }
 840
 841 _LIBCPP_END_NAMESPACE_STD
 842
 843 _LIBCPP_POP_MACROS
 844
 845 #endif // _LIBCPP___STRING_CHAR_TRAITS_H