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