diff options
Diffstat (limited to 'third_party/libcxx/include/c++/v1/__string')
3 files changed, 887 insertions, 0 deletions
diff --git a/third_party/libcxx/include/c++/v1/__string/char_traits.h b/third_party/libcxx/include/c++/v1/__string/char_traits.h new file mode 100644 index 0000000..d985950 --- /dev/null +++ b/third_party/libcxx/include/c++/v1/__string/char_traits.h @@ -0,0 +1,557 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___STRING_CHAR_TRAITS_H +#define _LIBCPP___STRING_CHAR_TRAITS_H + +#include <__algorithm/fill_n.h> +#include <__algorithm/find.h> +#include <__algorithm/find_end.h> +#include <__algorithm/find_first_of.h> +#include <__algorithm/min.h> +#include <__assert> +#include <__compare/ordering.h> +#include <__config> +#include <__cstddef/ptrdiff_t.h> +#include <__functional/hash.h> +#include <__functional/identity.h> +#include <__iterator/iterator_traits.h> +#include <__std_mbstate_t.h> +#include <__string/constexpr_c_functions.h> +#include <__type_traits/is_constant_evaluated.h> +#include <__utility/is_pointer_in_range.h> +#include <cstdint> +#include <cstdio> +#include <iosfwd> + +#if _LIBCPP_HAS_WIDE_CHARACTERS +# include <cwchar> // for wmemcpy +#endif + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template <class _CharT> +struct char_traits; +/* +The Standard does not define the base template for char_traits because it is impossible to provide +a correct definition for arbitrary character types. Instead, it requires implementations to provide +specializations for predefined character types like `char`, `wchar_t` and others. We provide this as +exposition-only to document what members a char_traits specialization should provide: +{ + using char_type = _CharT; + using int_type = ...; + using off_type = ...; + using pos_type = ...; + using state_type = ...; + + static void assign(char_type&, const char_type&); + static bool eq(char_type, char_type); + static bool lt(char_type, char_type); + + static int compare(const char_type*, const char_type*, size_t); + static size_t length(const char_type*); + static const char_type* find(const char_type*, size_t, const char_type&); + static char_type* move(char_type*, const char_type*, size_t); + static char_type* copy(char_type*, const char_type*, size_t); + static char_type* assign(char_type*, size_t, char_type); + + static int_type not_eof(int_type); + static char_type to_char_type(int_type); + static int_type to_int_type(char_type); + static bool eq_int_type(int_type, int_type); + static int_type eof(); +}; +*/ + +// char_traits<char> + +template <> +struct char_traits<char> { + using char_type = char; + using int_type = int; + using off_type = streamoff; + using pos_type = streampos; + using state_type = mbstate_t; +#if _LIBCPP_STD_VER >= 20 + using comparison_category = strong_ordering; +#endif + + static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 void + assign(char_type& __c1, const char_type& __c2) _NOEXCEPT { + __c1 = __c2; + } + + // TODO: Make this _LIBCPP_HIDE_FROM_ABI + [[__nodiscard__]] static inline _LIBCPP_HIDDEN _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT { + return __c1 == __c2; + } + [[__nodiscard__]] static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool + lt(char_type __c1, char_type __c2) _NOEXCEPT { + return (unsigned char)__c1 < (unsigned char)__c2; + } + + // __constexpr_memcmp requires a trivially lexicographically comparable type, but char is not when char is a signed + // type + [[__nodiscard__]] static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 int + compare(const char_type* __lhs, const char_type* __rhs, size_t __count) _NOEXCEPT { + if (__libcpp_is_constant_evaluated()) { +#ifdef _LIBCPP_COMPILER_CLANG_BASED + return __builtin_memcmp(__lhs, __rhs, __count); +#else + while (__count != 0) { + if (lt(*__lhs, *__rhs)) + return -1; + if (lt(*__rhs, *__lhs)) + return 1; + + __count -= sizeof(char_type); + ++__lhs; + ++__rhs; + } + return 0; +#endif // _LIBCPP_COMPILER_CLANG_BASED + } else { + return __builtin_memcmp(__lhs, __rhs, __count); + } + } + + [[__nodiscard__]] static inline _LIBCPP_HIDE_FROM_ABI size_t _LIBCPP_CONSTEXPR_SINCE_CXX17 + length(const char_type* __s) _NOEXCEPT { + return std::__constexpr_strlen(__s); + } + + [[__nodiscard__]] static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 const char_type* + find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT { + return std::__constexpr_memchr(__s, __a, __n); + } + + static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type* + move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT { + return std::__constexpr_memmove(__s1, __s2, __element_count(__n)); + } + + static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type* + copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT { + _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(!std::__is_pointer_in_range(__s1, __s1 + __n, __s2), + "char_traits::copy: source and destination ranges overlap"); + std::__constexpr_memmove(__s1, __s2, __element_count(__n)); + return __s1; + } + + static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type* + assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT { + std::fill_n(__s, __n, __a); + return __s; + } + + [[__nodiscard__]] static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT { + return eq_int_type(__c, eof()) ? ~eof() : __c; + } + [[__nodiscard__]] static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR char_type + to_char_type(int_type __c) _NOEXCEPT { + return char_type(__c); + } + [[__nodiscard__]] static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type + to_int_type(char_type __c) _NOEXCEPT { + return int_type((unsigned char)__c); + } + [[__nodiscard__]] static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool + eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT { + return __c1 == __c2; + } + [[__nodiscard__]] static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT { + return int_type(EOF); + } +}; + +template <class _CharT, class _IntT, _IntT _EOFVal> +struct __char_traits_base { + using char_type = _CharT; + using int_type = _IntT; + using off_type = streamoff; + using state_type = mbstate_t; +#if _LIBCPP_STD_VER >= 20 + using comparison_category = strong_ordering; +#endif + + // There are different aliases for the different char types, but they are all aliases to this type + using pos_type = fpos<mbstate_t>; + + _LIBCPP_HIDE_FROM_ABI static inline _LIBCPP_CONSTEXPR_SINCE_CXX17 void + assign(char_type& __lhs, const char_type& __rhs) _NOEXCEPT { + __lhs = __rhs; + } + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR bool eq(char_type __lhs, char_type __rhs) _NOEXCEPT { + return __lhs == __rhs; + } + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR bool lt(char_type __lhs, char_type __rhs) _NOEXCEPT { + return __lhs < __rhs; + } + + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type* + move(char_type* __dest, const char_type* __src, size_t __n) _NOEXCEPT { + return std::__constexpr_memmove(__dest, __src, __element_count(__n)); + } + + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type* + copy(char_type* __dest, const char_type* __src, size_t __n) _NOEXCEPT { + _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(!std::__is_pointer_in_range(__dest, __dest + __n, __src), + "char_traits::copy: source and destination ranges overlap"); + return std::__constexpr_memmove(__dest, __src, __element_count(__n)); + } + + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type* + assign(char_type* __str, size_t __n, char_type __fill_char) _NOEXCEPT { + std::fill_n(__str, __n, __fill_char); + return __str; + } + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT { + return char_type(__c); + } + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT { + return int_type(__c); + } + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR bool + eq_int_type(int_type __lhs, int_type __rhs) _NOEXCEPT { + return __lhs == __rhs; + } + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT { return _EOFVal; } + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT { + return eq_int_type(__c, eof()) ? static_cast<int_type>(~eof()) : __c; + } +}; + +// char_traits<wchar_t> + +#if _LIBCPP_HAS_WIDE_CHARACTERS +template <> +struct char_traits<wchar_t> : __char_traits_base<wchar_t, wint_t, static_cast<wint_t>(WEOF)> { + [[__nodiscard__]] static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 int + compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT { + if (__n == 0) + return 0; + return std::__constexpr_wmemcmp(__s1, __s2, __n); + } + + [[__nodiscard__]] static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t + length(const char_type* __s) _NOEXCEPT { + return std::__constexpr_wcslen(__s); + } + + [[__nodiscard__]] static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 const char_type* + find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT { + return std::__constexpr_wmemchr(__s, __a, __n); + } +}; +#endif // _LIBCPP_HAS_WIDE_CHARACTERS + +#if _LIBCPP_HAS_CHAR8_T + +template <> +struct char_traits<char8_t> : __char_traits_base<char8_t, unsigned int, static_cast<unsigned int>(EOF)> { + [[nodiscard]] static _LIBCPP_HIDE_FROM_ABI constexpr int + compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept { + return std::__constexpr_memcmp(__s1, __s2, __element_count(__n)); + } + + [[nodiscard]] static _LIBCPP_HIDE_FROM_ABI constexpr size_t length(const char_type* __str) noexcept { + return std::__constexpr_strlen(__str); + } + + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr const char_type* + find(const char_type* __s, size_t __n, const char_type& __a) noexcept { + return std::__constexpr_memchr(__s, __a, __n); + } +}; + +#endif // _LIBCPP_HAS_CHAR8_T + +template <> +struct char_traits<char16_t> : __char_traits_base<char16_t, uint_least16_t, static_cast<uint_least16_t>(0xFFFF)> { + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 int + compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t length(const char_type* __s) _NOEXCEPT; + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 const char_type* + find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT { + __identity __proj; + const char_type* __match = std::__find(__s, __s + __n, __a, __proj); + if (__match == __s + __n) + return nullptr; + return __match; + } +}; + +[[__nodiscard__]] inline _LIBCPP_CONSTEXPR_SINCE_CXX17 int +char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT { + for (; __n; --__n, ++__s1, ++__s2) { + if (lt(*__s1, *__s2)) + return -1; + if (lt(*__s2, *__s1)) + return 1; + } + return 0; +} + +[[__nodiscard__]] inline _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t +char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT { + size_t __len = 0; + for (; !eq(*__s, char_type(0)); ++__s) + ++__len; + return __len; +} + +template <> +struct char_traits<char32_t> : __char_traits_base<char32_t, uint_least32_t, static_cast<uint_least32_t>(0xFFFFFFFF)> { + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 int + compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t length(const char_type* __s) _NOEXCEPT; + + [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 const char_type* + find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT { + __identity __proj; + const char_type* __match = std::__find(__s, __s + __n, __a, __proj); + if (__match == __s + __n) + return nullptr; + return __match; + } +}; + +[[__nodiscard__]] inline _LIBCPP_CONSTEXPR_SINCE_CXX17 int +char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT { + for (; __n; --__n, ++__s1, ++__s2) { + if (lt(*__s1, *__s2)) + return -1; + if (lt(*__s2, *__s1)) + return 1; + } + return 0; +} + +[[__nodiscard__]] inline _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t +char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT { + size_t __len = 0; + for (; !eq(*__s, char_type(0)); ++__s) + ++__len; + return __len; +} + +// helper fns for basic_string and string_view + +// __str_find +template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> +inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI +__str_find(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT { + if (__pos > __sz) + return __npos; + const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c); + if (__r == nullptr) + return __npos; + return static_cast<_SizeT>(__r - __p); +} + +template <class _CharT, class _Traits> +_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_SINCE_CXX14 const _CharT* __search_substring( + const _CharT* __first1, const _CharT* __last1, const _CharT* __first2, const _CharT* __last2) _NOEXCEPT { + // Take advantage of knowing source and pattern lengths. + // Stop short when source is smaller than pattern. + const ptrdiff_t __len2 = __last2 - __first2; + if (__len2 == 0) + return __first1; + + ptrdiff_t __len1 = __last1 - __first1; + if (__len1 < __len2) + return __last1; + + if (__builtin_constant_p(__len2 == 1) && __len2 == 1) { + auto __res = _Traits::find(__first1, __len1, *__first2); + if (__res == nullptr) + return __last1; + return __res; + } + + // First element of __first2 is loop invariant. + _CharT __f2 = *__first2; + while (true) { + __len1 = __last1 - __first1; + // Check whether __first1 still has at least __len2 bytes. + if (__len1 < __len2) + return __last1; + + // Find __f2 the first byte matching in __first1. + __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2); + if (__first1 == nullptr) + return __last1; + + // It is faster to compare from the first byte of __first1 even if we + // already know that it matches the first byte of __first2: this is because + // __first2 is most likely aligned, as it is user's "pattern" string, and + // __first1 + 1 is most likely not aligned, as the match is in the middle of + // the string. + if (_Traits::compare(__first1, __first2, __len2) == 0) + return __first1; + + ++__first1; + } +} + +template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> +inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI +__str_find(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT { + if (__pos > __sz) + return __npos; + + if (__n == 0) // There is nothing to search, just return __pos. + return __pos; + + const _CharT* __r = std::__search_substring<_CharT, _Traits>(__p + __pos, __p + __sz, __s, __s + __n); + + if (__r == __p + __sz) + return __npos; + return static_cast<_SizeT>(__r - __p); +} + +// __str_rfind + +template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> +inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI +__str_rfind(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT { + if (__sz < 1) + return __npos; + if (__pos < __sz) + ++__pos; + else + __pos = __sz; + for (const _CharT* __ps = __p + __pos; __ps != __p;) { + if (_Traits::eq(*--__ps, __c)) + return static_cast<_SizeT>(__ps - __p); + } + return __npos; +} + +template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> +inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI +__str_rfind(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT { + __pos = std::min(__pos, __sz); + if (__n < __sz - __pos) + __pos += __n; + else + __pos = __sz; + const _CharT* __r = std::__find_end_classic(__p, __p + __pos, __s, __s + __n, _Traits::eq); + if (__n > 0 && __r == __p + __pos) + return __npos; + return static_cast<_SizeT>(__r - __p); +} + +// __str_find_first_of +template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> +inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI +__str_find_first_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT { + if (__pos >= __sz || __n == 0) + return __npos; + const _CharT* __r = std::__find_first_of_ce(__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq); + if (__r == __p + __sz) + return __npos; + return static_cast<_SizeT>(__r - __p); +} + +// __str_find_last_of +template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> +inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI +__str_find_last_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT { + if (__n != 0) { + if (__pos < __sz) + ++__pos; + else + __pos = __sz; + for (const _CharT* __ps = __p + __pos; __ps != __p;) { + const _CharT* __r = _Traits::find(__s, __n, *--__ps); + if (__r) + return static_cast<_SizeT>(__ps - __p); + } + } + return __npos; +} + +// __str_find_first_not_of +template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> +inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI +__str_find_first_not_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT { + if (__pos < __sz) { + const _CharT* __pe = __p + __sz; + for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps) + if (_Traits::find(__s, __n, *__ps) == nullptr) + return static_cast<_SizeT>(__ps - __p); + } + return __npos; +} + +template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> +inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI +__str_find_first_not_of(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT { + if (__pos < __sz) { + const _CharT* __pe = __p + __sz; + for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps) + if (!_Traits::eq(*__ps, __c)) + return static_cast<_SizeT>(__ps - __p); + } + return __npos; +} + +// __str_find_last_not_of +template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> +inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI +__str_find_last_not_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT { + if (__pos < __sz) + ++__pos; + else + __pos = __sz; + for (const _CharT* __ps = __p + __pos; __ps != __p;) + if (_Traits::find(__s, __n, *--__ps) == nullptr) + return static_cast<_SizeT>(__ps - __p); + return __npos; +} + +template <class _CharT, class _SizeT, class _Traits, _SizeT __npos> +inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI +__str_find_last_not_of(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT { + if (__pos < __sz) + ++__pos; + else + __pos = __sz; + for (const _CharT* __ps = __p + __pos; __ps != __p;) + if (!_Traits::eq(*--__ps, __c)) + return static_cast<_SizeT>(__ps - __p); + return __npos; +} + +template <class _Ptr> +inline _LIBCPP_HIDE_FROM_ABI size_t __do_string_hash(_Ptr __p, _Ptr __e) { + typedef typename iterator_traits<_Ptr>::value_type value_type; + return std::__hash_memory(__p, (__e - __p) * sizeof(value_type)); +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___STRING_CHAR_TRAITS_H diff --git a/third_party/libcxx/include/c++/v1/__string/constexpr_c_functions.h b/third_party/libcxx/include/c++/v1/__string/constexpr_c_functions.h new file mode 100644 index 0000000..4b05e86 --- /dev/null +++ b/third_party/libcxx/include/c++/v1/__string/constexpr_c_functions.h @@ -0,0 +1,236 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___STRING_CONSTEXPR_C_FUNCTIONS_H +#define _LIBCPP___STRING_CONSTEXPR_C_FUNCTIONS_H + +#include <__config> +#include <__cstddef/size_t.h> +#include <__memory/addressof.h> +#include <__memory/construct_at.h> +#include <__type_traits/datasizeof.h> +#include <__type_traits/enable_if.h> +#include <__type_traits/is_always_bitcastable.h> +#include <__type_traits/is_assignable.h> +#include <__type_traits/is_constant_evaluated.h> +#include <__type_traits/is_constructible.h> +#include <__type_traits/is_equality_comparable.h> +#include <__type_traits/is_integral.h> +#include <__type_traits/is_same.h> +#include <__type_traits/is_trivially_lexicographically_comparable.h> +#include <__type_traits/remove_cv.h> +#include <__utility/element_count.h> +#include <__utility/is_pointer_in_range.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template <class _Tp> +inline const bool __is_char_type = false; + +template <> +inline const bool __is_char_type<char> = true; + +#if _LIBCPP_HAS_CHAR8_T +template <> +inline const bool __is_char_type<char8_t> = true; +#endif + +template <class _Tp> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 size_t __constexpr_strlen(const _Tp* __str) _NOEXCEPT { + static_assert(__is_char_type<_Tp>, "__constexpr_strlen only works with char and char8_t"); + // GCC currently doesn't support __builtin_strlen for heap-allocated memory during constant evaluation. + // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=70816 + if (__libcpp_is_constant_evaluated()) { +#if _LIBCPP_STD_VER >= 17 && defined(_LIBCPP_COMPILER_CLANG_BASED) + if constexpr (is_same_v<_Tp, char>) + return __builtin_strlen(__str); +#endif + size_t __i = 0; + for (; __str[__i] != '\0'; ++__i) + ; + return __i; + } + return __builtin_strlen(reinterpret_cast<const char*>(__str)); +} + +// Because of __is_trivially_lexicographically_comparable_v we know that comparing the object representations is +// equivalent to a std::memcmp. Since we have multiple objects contiguously in memory, we can call memcmp once instead +// of invoking it on every object individually. +template <class _Tp, class _Up> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 int +__constexpr_memcmp(const _Tp* __lhs, const _Up* __rhs, __element_count __n) { + static_assert(__is_trivially_lexicographically_comparable_v<_Tp, _Up>, + "_Tp and _Up have to be trivially lexicographically comparable"); + + auto __count = static_cast<size_t>(__n); + + if (__libcpp_is_constant_evaluated()) { +#ifdef _LIBCPP_COMPILER_CLANG_BASED + if (sizeof(_Tp) == 1 && !is_same<_Tp, bool>::value) + return __builtin_memcmp(__lhs, __rhs, __count * sizeof(_Tp)); +#endif + + while (__count != 0) { + if (*__lhs < *__rhs) + return -1; + if (*__rhs < *__lhs) + return 1; + + --__count; + ++__lhs; + ++__rhs; + } + return 0; + } else { + return __builtin_memcmp(__lhs, __rhs, __count * sizeof(_Tp)); + } +} + +// Because of __is_trivially_equality_comparable_v we know that comparing the object representations is equivalent +// to a std::memcmp(...) == 0. Since we have multiple objects contiguously in memory, we can call memcmp once instead +// of invoking it on every object individually. +template <class _Tp, class _Up> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool +__constexpr_memcmp_equal(const _Tp* __lhs, const _Up* __rhs, __element_count __n) { + static_assert(__is_trivially_equality_comparable_v<_Tp, _Up>, "_Tp and _Up have to be trivially equality comparable"); + + auto __count = static_cast<size_t>(__n); + + if (__libcpp_is_constant_evaluated()) { +#ifdef _LIBCPP_COMPILER_CLANG_BASED + if (sizeof(_Tp) == 1 && is_integral<_Tp>::value && !is_same<_Tp, bool>::value) + return __builtin_memcmp(__lhs, __rhs, __count * sizeof(_Tp)) == 0; +#endif + while (__count != 0) { + if (*__lhs != *__rhs) + return false; + + --__count; + ++__lhs; + ++__rhs; + } + return true; + } else { + return ::__builtin_memcmp(__lhs, __rhs, __count * sizeof(_Tp)) == 0; + } +} + +template <class _Tp, class _Up> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp* __constexpr_memchr(_Tp* __str, _Up __value, size_t __count) { + static_assert(sizeof(_Tp) == 1 && __is_trivially_equality_comparable_v<_Tp, _Up>, + "Calling memchr on non-trivially equality comparable types is unsafe."); + + if (__libcpp_is_constant_evaluated()) { +// use __builtin_char_memchr to optimize constexpr evaluation if we can +#if _LIBCPP_STD_VER >= 17 && __has_builtin(__builtin_char_memchr) + if constexpr (is_same_v<remove_cv_t<_Tp>, char> && is_same_v<remove_cv_t<_Up>, char>) + return __builtin_char_memchr(__str, __value, __count); +#endif + + for (; __count; --__count) { + if (*__str == __value) + return __str; + ++__str; + } + return nullptr; + } else { + char __value_buffer = 0; + __builtin_memcpy(&__value_buffer, std::addressof(__value), sizeof(char)); + return static_cast<_Tp*>(__builtin_memchr(__str, __value_buffer, __count)); + } +} + +// This function performs an assignment to an existing, already alive TriviallyCopyable object +// from another TriviallyCopyable object. +// +// It basically works around the fact that TriviallyCopyable objects are not required to be +// syntactically copy/move constructible or copy/move assignable. Technically, only one of the +// four operations is required to be syntactically valid -- but at least one definitely has to +// be valid. +// +// This is necessary in order to implement __constexpr_memmove below in a way that mirrors as +// closely as possible what the compiler's __builtin_memmove is able to do. +template <class _Tp, class _Up, __enable_if_t<is_assignable<_Tp&, _Up const&>::value, int> = 0> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp& __assign_trivially_copyable(_Tp& __dest, _Up const& __src) { + __dest = __src; + return __dest; +} + +// clang-format off +template <class _Tp, class _Up, __enable_if_t<!is_assignable<_Tp&, _Up const&>::value && + is_assignable<_Tp&, _Up&&>::value, int> = 0> +// clang-format on +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp& __assign_trivially_copyable(_Tp& __dest, _Up& __src) { + __dest = + static_cast<_Up&&>(__src); // this is safe, we're not actually moving anything since the assignment is trivial + return __dest; +} + +// clang-format off +template <class _Tp, class _Up, __enable_if_t<!is_assignable<_Tp&, _Up const&>::value && + !is_assignable<_Tp&, _Up&&>::value && + is_constructible<_Tp, _Up const&>::value, int> = 0> +// clang-format on +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Tp& __assign_trivially_copyable(_Tp& __dest, _Up const& __src) { + // _Tp is trivially destructible, so we don't need to call its destructor to end the lifetime of the object + // that was there previously + std::__construct_at(std::addressof(__dest), __src); + return __dest; +} + +// clang-format off +template <class _Tp, class _Up, __enable_if_t<!is_assignable<_Tp&, _Up const&>::value && + !is_assignable<_Tp&, _Up&&>::value && + !is_constructible<_Tp, _Up const&>::value && + is_constructible<_Tp, _Up&&>::value, int> = 0> +// clang-format on +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Tp& __assign_trivially_copyable(_Tp& __dest, _Up& __src) { + // _Tp is trivially destructible, so we don't need to call its destructor to end the lifetime of the object + // that was there previously + std::__construct_at( + std::addressof(__dest), + static_cast<_Up&&>(__src)); // this is safe, we're not actually moving anything since the constructor is trivial + return __dest; +} + +template <class _Tp, class _Up> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp* +__constexpr_memmove(_Tp* __dest, _Up* __src, __element_count __n) { + static_assert(__is_always_bitcastable<_Up, _Tp>::value); + size_t __count = static_cast<size_t>(__n); + if (__libcpp_is_constant_evaluated()) { +#ifdef _LIBCPP_COMPILER_CLANG_BASED + if _LIBCPP_CONSTEXPR (is_same<__remove_cv_t<_Tp>, __remove_cv_t<_Up> >::value) { + ::__builtin_memmove(__dest, __src, __count * sizeof(_Tp)); + return __dest; + } else +#endif + { + if (std::__is_pointer_in_range(__src, __src + __count, __dest)) { + for (; __count > 0; --__count) + std::__assign_trivially_copyable(__dest[__count - 1], __src[__count - 1]); + } else { + for (size_t __i = 0; __i != __count; ++__i) + std::__assign_trivially_copyable(__dest[__i], __src[__i]); + } + } + } else if _LIBCPP_CONSTEXPR (sizeof(_Tp) == __datasizeof_v<_Tp>) { + ::__builtin_memmove(__dest, __src, __count * sizeof(_Tp)); + } else if (__count > 0) { + ::__builtin_memmove(__dest, __src, (__count - 1) * sizeof(_Tp) + __datasizeof_v<_Tp>); + } + return __dest; +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___STRING_CONSTEXPR_C_FUNCTIONS_H diff --git a/third_party/libcxx/include/c++/v1/__string/extern_template_lists.h b/third_party/libcxx/include/c++/v1/__string/extern_template_lists.h new file mode 100644 index 0000000..18f0ff9 --- /dev/null +++ b/third_party/libcxx/include/c++/v1/__string/extern_template_lists.h @@ -0,0 +1,94 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___STRING_EXTERN_TEMPLATE_LISTS_H +#define _LIBCPP___STRING_EXTERN_TEMPLATE_LISTS_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +// clang-format off + +// We maintain multiple ABI lists: +// - _LIBCPP_STRING_COMMON_EXTERN_TEMPLATE_LIST +// - _LIBCPP_STRING_V1_EXTERN_TEMPLATE_LIST +// - _LIBCPP_STRING_UNSTABLE_EXTERN_TEMPLATE_LIST +// As the name implies, the ABI lists define a common subset, the V1 (Stable) and unstable ABI. +// +// For unstable, we may explicitly remove function that are external in V1. +// +// For stable, the ABI list should rarely change, except for adding new +// functions supporting new c++ version / API changes. Typically entries +// must never be removed from the stable list. +#define _LIBCPP_STRING_COMMON_EXTERN_TEMPLATE_LIST(Func, CharT) \ + Func(void basic_string<CharT>::__init(const value_type*, size_type)) \ + Func(void basic_string<CharT>::__init(size_type, value_type)) \ + Func(basic_string<CharT>::basic_string(const basic_string&, size_type, size_type, const allocator<CharT>&)) \ + Func(basic_string<CharT>::~basic_string()) \ + Func(basic_string<CharT>& basic_string<CharT>::operator=(value_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::assign(size_type, value_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::assign(const basic_string&, size_type, size_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::append(size_type, value_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::append(const value_type*)) \ + Func(basic_string<CharT>& basic_string<CharT>::append(const value_type*, size_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::append(const basic_string&, size_type, size_type)) \ + Func(void basic_string<CharT>::push_back(value_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::insert(size_type, const value_type*)) \ + Func(basic_string<CharT>& basic_string<CharT>::insert(size_type, size_type, value_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::insert(size_type, const value_type*, size_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::insert(size_type, const basic_string&, size_type, size_type)) \ + Func(basic_string<CharT>::iterator basic_string<CharT>::insert(basic_string::const_iterator, value_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::replace(size_type, size_type, const value_type*)) \ + Func(basic_string<CharT>& basic_string<CharT>::replace(size_type, size_type, size_type, value_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::replace(size_type, size_type, const value_type*, size_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::replace(size_type, size_type, const basic_string&, size_type, size_type)) \ + Func(void basic_string<CharT>::__grow_by_and_replace(size_type, size_type, size_type, size_type, size_type, size_type, const value_type*)) \ + Func(void basic_string<CharT>::resize(size_type, value_type)) \ + Func(void basic_string<CharT>::reserve(size_type)) \ + Func(basic_string<CharT>::size_type basic_string<CharT>::copy(value_type*, size_type, size_type) const) \ + Func(basic_string<CharT>::size_type basic_string<CharT>::find(value_type, size_type) const) \ + Func(basic_string<CharT>::size_type basic_string<CharT>::find(const value_type*, size_type, size_type) const) \ + Func(basic_string<CharT>::size_type basic_string<CharT>::rfind(value_type, size_type) const) \ + Func(basic_string<CharT>::size_type basic_string<CharT>::rfind(const value_type*, size_type, size_type) const) \ + Func(basic_string<CharT>::size_type basic_string<CharT>::find_first_of(const value_type*, size_type, size_type) const) \ + Func(basic_string<CharT>::size_type basic_string<CharT>::find_last_of(const value_type*, size_type, size_type) const) \ + Func(basic_string<CharT>::size_type basic_string<CharT>::find_first_not_of(const value_type*, size_type, size_type) const) \ + Func(basic_string<CharT>::size_type basic_string<CharT>::find_last_not_of(const value_type*, size_type, size_type) const) \ + Func(CharT& basic_string<CharT>::at(size_type)) \ + Func(const CharT& basic_string<CharT>::at(size_type) const) \ + Func(int basic_string<CharT>::compare(const value_type*) const) \ + Func(int basic_string<CharT>::compare(size_type, size_type, const value_type*) const) \ + Func(int basic_string<CharT>::compare(size_type, size_type, const value_type*, size_type) const) \ + Func(int basic_string<CharT>::compare(size_type, size_type, const basic_string&, size_type, size_type) const) \ + Func(const basic_string<CharT>::size_type basic_string<CharT>::npos) \ + +#define _LIBCPP_STRING_V1_EXTERN_TEMPLATE_LIST(Func, CharT) \ + _LIBCPP_STRING_COMMON_EXTERN_TEMPLATE_LIST(Func, CharT) \ + Func(basic_string<CharT>::basic_string(const basic_string&)) \ + Func(basic_string<CharT>::basic_string(const basic_string&, const allocator<CharT>&)) \ + Func(basic_string<CharT>& basic_string<CharT>::assign(const value_type*)) \ + Func(basic_string<CharT>& basic_string<CharT>::assign(const value_type*, size_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::operator=(basic_string const&)) \ + Func(void basic_string<CharT>::__grow_by(size_type, size_type, size_type, size_type, size_type, size_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::erase(size_type, size_type)) \ + +#define _LIBCPP_STRING_UNSTABLE_EXTERN_TEMPLATE_LIST(Func, CharT) \ + _LIBCPP_STRING_COMMON_EXTERN_TEMPLATE_LIST(Func, CharT) \ + Func(void basic_string<CharT>::__init_copy_ctor_external(const value_type*, size_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::__assign_external(const value_type*, size_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::__assign_external(const value_type*)) \ + Func(basic_string<CharT>& basic_string<CharT>::__assign_no_alias<false>(const value_type*, size_type)) \ + Func(basic_string<CharT>& basic_string<CharT>::__assign_no_alias<true>(const value_type*, size_type)) \ + Func(void basic_string<CharT>::__erase_external_with_move(size_type, size_type)) + +// clang-format on + +#endif // _LIBCPP___STRING_EXTERN_TEMPLATE_LISTS_H |