lib: establish Zircon libc++ and KTL foundation

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