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___CXX03___STRING_CHAR_TRAITS_H 10 #define _LIBCPP___CXX03___STRING_CHAR_TRAITS_H 11 12 #include <__cxx03/__algorithm/fill_n.h> 13 #include <__cxx03/__algorithm/find.h> 14 #include <__cxx03/__algorithm/find_end.h> 15 #include <__cxx03/__algorithm/find_first_of.h> 16 #include <__cxx03/__algorithm/min.h> 17 #include <__cxx03/__assert> 18 #include <__cxx03/__config> 19 #include <__cxx03/__functional/hash.h> 20 #include <__cxx03/__functional/identity.h> 21 #include <__cxx03/__iterator/iterator_traits.h> 22 #include <__cxx03/__string/constexpr_c_functions.h> 23 #include <__cxx03/__type_traits/is_constant_evaluated.h> 24 #include <__cxx03/__utility/is_pointer_in_range.h> 25 #include <__cxx03/cstddef> 26 #include <__cxx03/cstdint> 27 #include <__cxx03/cstdio> 28 #include <__cxx03/iosfwd> 29 30 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 31 # include <__cxx03/cwchar> // for wmemcpy 32 #endif 33 34 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 35 # pragma GCC system_header 36 #endif 37 38 _LIBCPP_PUSH_MACROS 39 #include <__cxx03/__undef_macros> 40 41 _LIBCPP_BEGIN_NAMESPACE_STD 42 43 template <class _CharT> 44 struct char_traits; 45 /* 46 The Standard does not define the base template for char_traits because it is impossible to provide 47 a correct definition for arbitrary character types. Instead, it requires implementations to provide 48 specializations for predefined character types like `char`, `wchar_t` and others. We provide this as 49 exposition-only to document what members a char_traits specialization should provide: 50 { 51 using char_type = _CharT; 52 using int_type = ...; 53 using off_type = ...; 54 using pos_type = ...; 55 using state_type = ...; 56 57 static void assign(char_type&, const char_type&); 58 static bool eq(char_type, char_type); 59 static bool lt(char_type, char_type); 60 61 static int compare(const char_type*, const char_type*, size_t); 62 static size_t length(const char_type*); 63 static const char_type* find(const char_type*, size_t, const char_type&); 64 static char_type* move(char_type*, const char_type*, size_t); 65 static char_type* copy(char_type*, const char_type*, size_t); 66 static char_type* assign(char_type*, size_t, char_type); 67 68 static int_type not_eof(int_type); 69 static char_type to_char_type(int_type); 70 static int_type to_int_type(char_type); 71 static bool eq_int_type(int_type, int_type); 72 static int_type eof(); 73 }; 74 */ 75 76 // char_traits<char> 77 78 template <> 79 struct _LIBCPP_TEMPLATE_VIS char_traits<char> { 80 using char_type = char; 81 using int_type = int; 82 using off_type = streamoff; 83 using pos_type = streampos; 84 using state_type = mbstate_t; 85 86 static inline _LIBCPP_HIDE_FROM_ABI void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT { __c1 = __c2; } 87 88 // TODO: Make this _LIBCPP_HIDE_FROM_ABI 89 static inline _LIBCPP_HIDDEN bool eq(char_type __c1, char_type __c2) _NOEXCEPT { return __c1 == __c2; } 90 static inline _LIBCPP_HIDE_FROM_ABI bool lt(char_type __c1, char_type __c2) _NOEXCEPT { 91 return (unsigned char)__c1 < (unsigned char)__c2; 92 } 93 94 // __constexpr_memcmp requires a trivially lexicographically comparable type, but char is not when char is a signed 95 // type 96 static _LIBCPP_HIDE_FROM_ABI int compare(const char_type* __lhs, const char_type* __rhs, size_t __count) _NOEXCEPT { 97 if (__libcpp_is_constant_evaluated()) { 98 #ifdef _LIBCPP_COMPILER_CLANG_BASED 99 return __builtin_memcmp(__lhs, __rhs, __count); 100 #else 101 while (__count != 0) { 102 if (lt(*__lhs, *__rhs)) 103 return -1; 104 if (lt(*__rhs, *__lhs)) 105 return 1; 106 107 __count -= sizeof(char_type); 108 ++__lhs; 109 ++__rhs; 110 } 111 return 0; 112 #endif // _LIBCPP_COMPILER_CLANG_BASED 113 } else { 114 return __builtin_memcmp(__lhs, __rhs, __count); 115 } 116 } 117 118 static inline _LIBCPP_HIDE_FROM_ABI size_t length(const char_type* __s) _NOEXCEPT { 119 return std::__constexpr_strlen(__s); 120 } 121 122 static _LIBCPP_HIDE_FROM_ABI const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT { 123 if (__n == 0) 124 return nullptr; 125 return std::__constexpr_memchr(__s, __a, __n); 126 } 127 128 static inline _LIBCPP_HIDE_FROM_ABI char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT { 129 return std::__constexpr_memmove(__s1, __s2, __element_count(__n)); 130 } 131 132 static inline _LIBCPP_HIDE_FROM_ABI char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT { 133 _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(!std::__is_pointer_in_range(__s1, __s1 + __n, __s2), 134 "char_traits::copy: source and destination ranges overlap"); 135 std::__constexpr_memmove(__s1, __s2, __element_count(__n)); 136 return __s1; 137 } 138 139 static inline _LIBCPP_HIDE_FROM_ABI char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT { 140 std::fill_n(__s, __n, __a); 141 return __s; 142 } 143 144 static inline _LIBCPP_HIDE_FROM_ABI int_type not_eof(int_type __c) _NOEXCEPT { 145 return eq_int_type(__c, eof()) ? ~eof() : __c; 146 } 147 static inline _LIBCPP_HIDE_FROM_ABI char_type to_char_type(int_type __c) _NOEXCEPT { return char_type(__c); } 148 static inline _LIBCPP_HIDE_FROM_ABI int_type to_int_type(char_type __c) _NOEXCEPT { 149 return int_type((unsigned char)__c); 150 } 151 static inline _LIBCPP_HIDE_FROM_ABI bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT { return __c1 == __c2; } 152 static inline _LIBCPP_HIDE_FROM_ABI int_type eof() _NOEXCEPT { return int_type(EOF); } 153 }; 154 155 template <class _CharT, class _IntT, _IntT _EOFVal> 156 struct __char_traits_base { 157 using char_type = _CharT; 158 using int_type = _IntT; 159 using off_type = streamoff; 160 using state_type = mbstate_t; 161 162 // There are different aliases for the different char types, but they are all aliases to this type 163 using pos_type = fpos<mbstate_t>; 164 165 _LIBCPP_HIDE_FROM_ABI static inline void assign(char_type& __lhs, const char_type& __rhs) _NOEXCEPT { __lhs = __rhs; } 166 167 _LIBCPP_HIDE_FROM_ABI static bool eq(char_type __lhs, char_type __rhs) _NOEXCEPT { return __lhs == __rhs; } 168 169 _LIBCPP_HIDE_FROM_ABI static bool lt(char_type __lhs, char_type __rhs) _NOEXCEPT { return __lhs < __rhs; } 170 171 _LIBCPP_HIDE_FROM_ABI static char_type* move(char_type* __dest, const char_type* __src, size_t __n) _NOEXCEPT { 172 return std::__constexpr_memmove(__dest, __src, __element_count(__n)); 173 } 174 175 _LIBCPP_HIDE_FROM_ABI static char_type* copy(char_type* __dest, const char_type* __src, size_t __n) _NOEXCEPT { 176 _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(!std::__is_pointer_in_range(__dest, __dest + __n, __src), 177 "char_traits::copy: source and destination ranges overlap"); 178 return std::__constexpr_memmove(__dest, __src, __element_count(__n)); 179 } 180 181 _LIBCPP_HIDE_FROM_ABI static char_type* assign(char_type* __str, size_t __n, char_type __fill_char) _NOEXCEPT { 182 std::fill_n(__str, __n, __fill_char); 183 return __str; 184 } 185 186 _LIBCPP_HIDE_FROM_ABI static char_type to_char_type(int_type __c) _NOEXCEPT { return char_type(__c); } 187 188 _LIBCPP_HIDE_FROM_ABI static int_type to_int_type(char_type __c) _NOEXCEPT { return int_type(__c); } 189 190 _LIBCPP_HIDE_FROM_ABI static bool eq_int_type(int_type __lhs, int_type __rhs) _NOEXCEPT { return __lhs == __rhs; } 191 192 _LIBCPP_HIDE_FROM_ABI static int_type eof() _NOEXCEPT { return _EOFVal; } 193 194 _LIBCPP_HIDE_FROM_ABI static int_type not_eof(int_type __c) _NOEXCEPT { 195 return eq_int_type(__c, eof()) ? static_cast<int_type>(~eof()) : __c; 196 } 197 }; 198 199 // char_traits<wchar_t> 200 201 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 202 template <> 203 struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t> : __char_traits_base<wchar_t, wint_t, static_cast<wint_t>(WEOF)> { 204 static _LIBCPP_HIDE_FROM_ABI int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT { 205 if (__n == 0) 206 return 0; 207 return std::__constexpr_wmemcmp(__s1, __s2, __n); 208 } 209 210 static _LIBCPP_HIDE_FROM_ABI size_t length(const char_type* __s) _NOEXCEPT { return std::__constexpr_wcslen(__s); } 211 212 static _LIBCPP_HIDE_FROM_ABI const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT { 213 if (__n == 0) 214 return nullptr; 215 return std::__constexpr_wmemchr(__s, __a, __n); 216 } 217 }; 218 #endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS 219 220 #ifndef _LIBCPP_HAS_NO_CHAR8_T 221 222 template <> 223 struct _LIBCPP_TEMPLATE_VIS char_traits<char8_t> 224 : __char_traits_base<char8_t, unsigned int, static_cast<unsigned int>(EOF)> { 225 static _LIBCPP_HIDE_FROM_ABI constexpr int 226 compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept { 227 return std::__constexpr_memcmp(__s1, __s2, __element_count(__n)); 228 } 229 230 static _LIBCPP_HIDE_FROM_ABI constexpr size_t length(const char_type* __str) noexcept { 231 return std::__constexpr_strlen(__str); 232 } 233 234 _LIBCPP_HIDE_FROM_ABI static constexpr const char_type* 235 find(const char_type* __s, size_t __n, const char_type& __a) noexcept { 236 return std::__constexpr_memchr(__s, __a, __n); 237 } 238 }; 239 240 #endif // _LIBCPP_HAS_NO_CHAR8_T 241 242 template <> 243 struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t> 244 : __char_traits_base<char16_t, uint_least16_t, static_cast<uint_least16_t>(0xFFFF)> { 245 _LIBCPP_HIDE_FROM_ABI static int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 246 _LIBCPP_HIDE_FROM_ABI static size_t length(const char_type* __s) _NOEXCEPT; 247 248 _LIBCPP_HIDE_FROM_ABI static const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT { 249 __identity __proj; 250 const char_type* __match = std::__find(__s, __s + __n, __a, __proj); 251 if (__match == __s + __n) 252 return nullptr; 253 return __match; 254 } 255 }; 256 257 inline int char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT { 258 for (; __n; --__n, ++__s1, ++__s2) { 259 if (lt(*__s1, *__s2)) 260 return -1; 261 if (lt(*__s2, *__s1)) 262 return 1; 263 } 264 return 0; 265 } 266 267 inline size_t char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT { 268 size_t __len = 0; 269 for (; !eq(*__s, char_type(0)); ++__s) 270 ++__len; 271 return __len; 272 } 273 274 template <> 275 struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t> 276 : __char_traits_base<char32_t, uint_least32_t, static_cast<uint_least32_t>(0xFFFFFFFF)> { 277 _LIBCPP_HIDE_FROM_ABI static int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 278 _LIBCPP_HIDE_FROM_ABI static size_t length(const char_type* __s) _NOEXCEPT; 279 280 _LIBCPP_HIDE_FROM_ABI static const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT { 281 __identity __proj; 282 const char_type* __match = std::__find(__s, __s + __n, __a, __proj); 283 if (__match == __s + __n) 284 return nullptr; 285 return __match; 286 } 287 }; 288 289 inline int char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT { 290 for (; __n; --__n, ++__s1, ++__s2) { 291 if (lt(*__s1, *__s2)) 292 return -1; 293 if (lt(*__s2, *__s1)) 294 return 1; 295 } 296 return 0; 297 } 298 299 inline size_t char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT { 300 size_t __len = 0; 301 for (; !eq(*__s, char_type(0)); ++__s) 302 ++__len; 303 return __len; 304 } 305 306 // helper fns for basic_string and string_view 307 308 // __str_find 309 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> 310 inline _SizeT _LIBCPP_HIDE_FROM_ABI __str_find(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT { 311 if (__pos >= __sz) 312 return __npos; 313 const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c); 314 if (__r == nullptr) 315 return __npos; 316 return static_cast<_SizeT>(__r - __p); 317 } 318 319 template <class _CharT, class _Traits> 320 _LIBCPP_HIDE_FROM_ABI inline const _CharT* __search_substring( 321 const _CharT* __first1, const _CharT* __last1, const _CharT* __first2, const _CharT* __last2) _NOEXCEPT { 322 // Take advantage of knowing source and pattern lengths. 323 // Stop short when source is smaller than pattern. 324 const ptrdiff_t __len2 = __last2 - __first2; 325 if (__len2 == 0) 326 return __first1; 327 328 ptrdiff_t __len1 = __last1 - __first1; 329 if (__len1 < __len2) 330 return __last1; 331 332 // First element of __first2 is loop invariant. 333 _CharT __f2 = *__first2; 334 while (true) { 335 __len1 = __last1 - __first1; 336 // Check whether __first1 still has at least __len2 bytes. 337 if (__len1 < __len2) 338 return __last1; 339 340 // Find __f2 the first byte matching in __first1. 341 __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2); 342 if (__first1 == nullptr) 343 return __last1; 344 345 // It is faster to compare from the first byte of __first1 even if we 346 // already know that it matches the first byte of __first2: this is because 347 // __first2 is most likely aligned, as it is user's "pattern" string, and 348 // __first1 + 1 is most likely not aligned, as the match is in the middle of 349 // the string. 350 if (_Traits::compare(__first1, __first2, __len2) == 0) 351 return __first1; 352 353 ++__first1; 354 } 355 } 356 357 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> 358 inline _SizeT _LIBCPP_HIDE_FROM_ABI 359 __str_find(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT { 360 if (__pos > __sz) 361 return __npos; 362 363 if (__n == 0) // There is nothing to search, just return __pos. 364 return __pos; 365 366 const _CharT* __r = std::__search_substring<_CharT, _Traits>(__p + __pos, __p + __sz, __s, __s + __n); 367 368 if (__r == __p + __sz) 369 return __npos; 370 return static_cast<_SizeT>(__r - __p); 371 } 372 373 // __str_rfind 374 375 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> 376 inline _SizeT _LIBCPP_HIDE_FROM_ABI __str_rfind(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT { 377 if (__sz < 1) 378 return __npos; 379 if (__pos < __sz) 380 ++__pos; 381 else 382 __pos = __sz; 383 for (const _CharT* __ps = __p + __pos; __ps != __p;) { 384 if (_Traits::eq(*--__ps, __c)) 385 return static_cast<_SizeT>(__ps - __p); 386 } 387 return __npos; 388 } 389 390 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> 391 inline _SizeT _LIBCPP_HIDE_FROM_ABI 392 __str_rfind(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT { 393 __pos = std::min(__pos, __sz); 394 if (__n < __sz - __pos) 395 __pos += __n; 396 else 397 __pos = __sz; 398 const _CharT* __r = std::__find_end_classic(__p, __p + __pos, __s, __s + __n, _Traits::eq); 399 if (__n > 0 && __r == __p + __pos) 400 return __npos; 401 return static_cast<_SizeT>(__r - __p); 402 } 403 404 // __str_find_first_of 405 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> 406 inline _SizeT _LIBCPP_HIDE_FROM_ABI 407 __str_find_first_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT { 408 if (__pos >= __sz || __n == 0) 409 return __npos; 410 const _CharT* __r = std::__find_first_of_ce(__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq); 411 if (__r == __p + __sz) 412 return __npos; 413 return static_cast<_SizeT>(__r - __p); 414 } 415 416 // __str_find_last_of 417 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> 418 inline _SizeT _LIBCPP_HIDE_FROM_ABI 419 __str_find_last_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT { 420 if (__n != 0) { 421 if (__pos < __sz) 422 ++__pos; 423 else 424 __pos = __sz; 425 for (const _CharT* __ps = __p + __pos; __ps != __p;) { 426 const _CharT* __r = _Traits::find(__s, __n, *--__ps); 427 if (__r) 428 return static_cast<_SizeT>(__ps - __p); 429 } 430 } 431 return __npos; 432 } 433 434 // __str_find_first_not_of 435 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> 436 inline _SizeT _LIBCPP_HIDE_FROM_ABI 437 __str_find_first_not_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT { 438 if (__pos < __sz) { 439 const _CharT* __pe = __p + __sz; 440 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps) 441 if (_Traits::find(__s, __n, *__ps) == nullptr) 442 return static_cast<_SizeT>(__ps - __p); 443 } 444 return __npos; 445 } 446 447 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> 448 inline _SizeT _LIBCPP_HIDE_FROM_ABI 449 __str_find_first_not_of(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT { 450 if (__pos < __sz) { 451 const _CharT* __pe = __p + __sz; 452 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps) 453 if (!_Traits::eq(*__ps, __c)) 454 return static_cast<_SizeT>(__ps - __p); 455 } 456 return __npos; 457 } 458 459 // __str_find_last_not_of 460 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> 461 inline _SizeT _LIBCPP_HIDE_FROM_ABI 462 __str_find_last_not_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT { 463 if (__pos < __sz) 464 ++__pos; 465 else 466 __pos = __sz; 467 for (const _CharT* __ps = __p + __pos; __ps != __p;) 468 if (_Traits::find(__s, __n, *--__ps) == nullptr) 469 return static_cast<_SizeT>(__ps - __p); 470 return __npos; 471 } 472 473 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> 474 inline _SizeT _LIBCPP_HIDE_FROM_ABI 475 __str_find_last_not_of(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT { 476 if (__pos < __sz) 477 ++__pos; 478 else 479 __pos = __sz; 480 for (const _CharT* __ps = __p + __pos; __ps != __p;) 481 if (!_Traits::eq(*--__ps, __c)) 482 return static_cast<_SizeT>(__ps - __p); 483 return __npos; 484 } 485 486 template <class _Ptr> 487 inline _LIBCPP_HIDE_FROM_ABI size_t __do_string_hash(_Ptr __p, _Ptr __e) { 488 typedef typename iterator_traits<_Ptr>::value_type value_type; 489 return __murmur2_or_cityhash<size_t>()(__p, (__e - __p) * sizeof(value_type)); 490 } 491 492 _LIBCPP_END_NAMESPACE_STD 493 494 _LIBCPP_POP_MACROS 495 496 #endif // _LIBCPP___CXX03___STRING_CHAR_TRAITS_H 497