Upd libc++ to 18 Jun 2022 ff3989e6ae740a9b3adaad0e2bf7691ffd6dad12

```
[libc++] Add Implemented Papers section
[libc++] Enable -Wweak-vtables
[libc++] Make sure we install libc++abi headers on Apple
[libc++] Don't force -O2 when building the benchmarks
[libc++] Mark standard-mandated includes as such
[libc++] Implement std::boyer_moore{, _horspool}_searcher
[libc++] Unwrap reverse_iterator<reverse_iterator<Iter>> in __unwrap_iter
[libc++] Simplify __config a bit
[libc++][ranges] Implement `ranges::sort`.
[libc++] Remove now-unused experimental/filesystem config file
[libc++] Robust against C++20-hostile iterators
[libc++] Implement ranges::lexicographical_compare
[libc++] Removes unneeded <iterator> includes.
[libcxx] Fix allocator<void>::pointer in C++20 with removed members
[libcxx] Remove extraneous '---' lines in .clang-format files
[libc++][NFCI] span: replace enable_if with concepts
[libc++] Find a clang-format everybody is happy with
[libc++] Use explicit module cache path in tests
[libc++] Remove macros for IBM compiler
```

6 files changed, 269 insertions, 32 deletions

diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/copy.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/copy.h
index 2a4e535c6f..886a1ac6ce 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/copy.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/copy.h
@@ -74,13 +74,6 @@ __copy_impl(reverse_iterator<_InIter> __first,
   return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first)));
 }
 
-template <class _InIter, class _Sent, class _OutIter>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
-pair<reverse_iterator<reverse_iterator<_InIter> >, reverse_iterator<reverse_iterator<_OutIter> > >
-__copy_impl(reverse_iterator<reverse_iterator<_InIter> > __first,
-            reverse_iterator<reverse_iterator<_Sent> > __last,
-            reverse_iterator<reverse_iterator<_OutIter> > __result);
-
 template <class _InIter, class _Sent, class _OutIter,
           __enable_if_t<!(is_copy_constructible<_InIter>::value
                        && is_copy_constructible<_Sent>::value
@@ -101,18 +94,6 @@ __copy(_InIter __first, _Sent __last, _OutIter __result) {
   return std::make_pair(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second));
 }
 
-// __unwrap_iter can't unwrap random_access_iterators, so we need to unwrap two reverse_iterators manually
-template <class _InIter, class _Sent, class _OutIter>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
-pair<reverse_iterator<reverse_iterator<_InIter> >, reverse_iterator<reverse_iterator<_OutIter> > >
-__copy_impl(reverse_iterator<reverse_iterator<_InIter> > __first,
-            reverse_iterator<reverse_iterator<_Sent> > __last,
-            reverse_iterator<reverse_iterator<_OutIter> > __result) {
-  auto __ret = std::__copy(__first.base().base(), __last.base().base(), __result.base().base());
-  return std::make_pair(reverse_iterator<reverse_iterator<_InIter> >(reverse_iterator<_InIter>(__ret.first)),
-                        reverse_iterator<reverse_iterator<_OutIter> >(reverse_iterator<_OutIter>(__ret.second)));
-}
-
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/make_projected.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/make_projected.h
new file mode 100644
index 0000000000..8141c4ed17
--- /dev/null
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/make_projected.h
@@ -0,0 +1,51 @@
+//===----------------------------------------------------------------------===//
+//
+// 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___ALGORITHM_MAKE_PROJECTED_H
+#define _LIBCPP___ALGORITHM_MAKE_PROJECTED_H
+
+#include <__concepts/same_as.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__utility/forward.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+
+template <class _Comp, class _Proj>
+_LIBCPP_HIDE_FROM_ABI constexpr static
+decltype(auto) __make_projected_comp(_Comp& __comp, _Proj& __proj) {
+  if constexpr (same_as<_Proj, identity>) {
+    // Avoid creating the lambda and just use the pristine comparator -- for certain algorithms, this would enable
+    // optimizations that rely on the type of the comparator.
+    return __comp;
+
+  } else {
+    return [&](auto&& __lhs, auto&& __rhs) {
+      return std::invoke(__comp,
+                        std::invoke(__proj, std::forward<decltype(__lhs)>(__lhs)),
+                        std::invoke(__proj, std::forward<decltype(__rhs)>(__rhs)));
+    };
+  }
+}
+
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_MAKE_PROJECTED_H
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_lexicographical_compare.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_lexicographical_compare.h
new file mode 100644
index 0000000000..fe709f7a7f
--- /dev/null
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_lexicographical_compare.h
@@ -0,0 +1,98 @@
+//===----------------------------------------------------------------------===//
+//
+// 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___ALGORITHM_RANGES_LEXICOGRAPHICAL_COMPARE_H
+#define _LIBCPP___ALGORITHM_RANGES_LEXICOGRAPHICAL_COMPARE_H
+
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __lexicographical_compare {
+struct __fn {
+
+  template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Proj1, class _Proj2, class _Comp>
+  _LIBCPP_HIDE_FROM_ABI constexpr static
+  bool __lexicographical_compare_impl(_Iter1 __first1, _Sent1 __last1,
+                                      _Iter2 __first2, _Sent2 __last2,
+                                      _Comp& __comp,
+                                      _Proj1& __proj1,
+                                      _Proj2& __proj2) {
+    while (__first2 != __last2) {
+      if (__first1 == __last1
+       || std::invoke(__comp, std::invoke(__proj1, *__first1), std::invoke(__proj2, *__first2)))
+        return true;
+      if (std::invoke(__comp, std::invoke(__proj2, *__first2), std::invoke(__proj1, *__first1)))
+        return false;
+      ++__first1;
+      ++__first2;
+    }
+    return false;
+  }
+
+  template <input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
+            input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
+            class _Proj1 = identity,
+            class _Proj2 = identity,
+            indirect_strict_weak_order<projected<_Iter1, _Proj1>, projected<_Iter2, _Proj2>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  bool operator()(_Iter1 __first1, _Sent1 __last1,
+                  _Iter2 __first2, _Sent2 __last2,
+                  _Comp __comp = {},
+                  _Proj1 __proj1 = {},
+                  _Proj2 __proj2 = {}) const {
+    return __lexicographical_compare_impl(std::move(__first1), std::move(__last1),
+                                          std::move(__first2), std::move(__last2),
+                                          __comp,
+                                          __proj1,
+                                          __proj2);
+  }
+
+  template <input_range _Range1,
+            input_range _Range2,
+            class _Proj1 = identity,
+            class _Proj2 = identity,
+            indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
+                                       projected<iterator_t<_Range2>, _Proj2>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  bool operator()(_Range1&& __range1, _Range2&& __range2, _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
+    return __lexicographical_compare_impl(ranges::begin(__range1), ranges::end(__range1),
+                                          ranges::begin(__range2), ranges::end(__range2),
+                                          __comp,
+                                          __proj1,
+                                          __proj2);
+  }
+
+};
+} // namespace __lexicographical_compare
+
+inline namespace __cpo {
+  inline constexpr auto lexicographical_compare = __lexicographical_compare::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_LEXICOGRAPHICAL_COMPARE_H
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_sort.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_sort.h
new file mode 100644
index 0000000000..a446a53e06
--- /dev/null
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_sort.h
@@ -0,0 +1,79 @@
+//===----------------------------------------------------------------------===//
+//
+// 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___ALGORITHM_RANGES_SORT_H
+#define _LIBCPP___ALGORITHM_RANGES_SORT_H
+
+#include <__algorithm/make_projected.h>
+#include <__algorithm/sort.h>
+#include <__concepts/same_as.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
+#include <__iterator/projected.h>
+#include <__iterator/sortable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __sort {
+
+struct __fn {
+  template <class _Iter, class _Sent, class _Comp, class _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr static
+  _Iter __sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
+    auto __last_iter = ranges::next(__first, __last);
+
+    auto&& __projected_comp = __make_projected_comp(__comp, __proj);
+    std::__sort_impl(std::move(__first), __last_iter, __projected_comp);
+
+    return __last_iter;
+  }
+
+  template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
+    requires sortable<_Iter, _Comp, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __sort_fn_impl(std::move(__first), std::move(__last), __comp, __proj);
+  }
+
+  template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity>
+    requires sortable<iterator_t<_Range>, _Comp, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __sort_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+  }
+};
+
+} // namespace __sort
+
+inline namespace __cpo {
+  inline constexpr auto sort = __sort::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_SORT_H
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h
index 0f463e14cc..f7406a5170 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h
@@ -18,6 +18,7 @@
 #include <__config>
 #include <__debug>
 #include <__functional/operations.h>
+#include <__functional/ranges_operations.h>
 #include <__iterator/iterator_traits.h>
 #include <__utility/swap.h>
 #include <climits>
@@ -115,6 +116,7 @@ _LIBCPP_HIDDEN unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _F
   return __r;
 }
 
+// The comparator being simple is a prerequisite for using the branchless optimization.
 template <class _Tp>
 struct __is_simple_comparator : false_type {};
 template <class _Tp>
@@ -123,6 +125,12 @@ template <class _Tp>
 struct __is_simple_comparator<less<_Tp>&> : true_type {};
 template <class _Tp>
 struct __is_simple_comparator<greater<_Tp>&> : true_type {};
+#if _LIBCPP_STD_VER > 17
+template <>
+struct __is_simple_comparator<ranges::less&> : true_type {};
+template <>
+struct __is_simple_comparator<ranges::greater&> : true_type {};
+#endif
 
 template <class _Compare, class _Iter, class _Tp = typename iterator_traits<_Iter>::value_type>
 using __use_branchless_sort =
@@ -571,22 +579,28 @@ extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long do
 
 extern template _LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&);
 
-template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void
-sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+template <class _RandomAccessIterator, class _Comp>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
   _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
-  typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+  using _Comp_ref = typename __comp_ref_type<_Comp>::type;
   if (__libcpp_is_constant_evaluated()) {
-    _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
+    std::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
   } else {
-    _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _Comp_ref(__comp));
+    std::__sort<_Comp_ref>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), _Comp_ref(__comp));
   }
 }
 
+template <class _RandomAccessIterator, class _Comp>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
+  std::__sort_impl(std::move(__first), std::move(__last), __comp);
+}
+
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void sort(_RandomAccessIterator __first,
-                                                                         _RandomAccessIterator __last) {
-  _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {
+  std::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/unwrap_iter.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/unwrap_iter.h
index be33194164..7d1807b7bb 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/unwrap_iter.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/unwrap_iter.h
@@ -63,6 +63,22 @@ __unwrap_iter(_Iter __i) _NOEXCEPT
     return _Impl::__apply(__i);
 }
 
+template <class _OrigIter, class _UnwrappedIter>
+struct __rewrap_iter_impl {
+  static _LIBCPP_CONSTEXPR _OrigIter __apply(_OrigIter __first, _UnwrappedIter __result) {
+    // Precondition: __result is reachable from __first
+    // Precondition: _OrigIter is a contiguous iterator
+    return __first + (__result - std::__unwrap_iter(__first));
+  }
+};
+
+template <class _OrigIter>
+struct __rewrap_iter_impl<_OrigIter, _OrigIter> {
+  static _LIBCPP_CONSTEXPR _OrigIter __apply(_OrigIter, _OrigIter __result) {
+    return __result;
+  }
+};
+
 template<class _OrigIter>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR
 _OrigIter __rewrap_iter(_OrigIter, _OrigIter __result)
@@ -70,13 +86,11 @@ _OrigIter __rewrap_iter(_OrigIter, _OrigIter __result)
     return __result;
 }
 
-template<class _OrigIter, class _UnwrappedIter>
+template<class _OrigIter, class _UnwrappedIter, class _Impl = __rewrap_iter_impl<_OrigIter, _UnwrappedIter> >
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR
 _OrigIter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result)
 {
-    // Precondition: __result is reachable from __first
-    // Precondition: _OrigIter is a contiguous iterator
-    return __first + (__result - _VSTD::__unwrap_iter(__first));
+  return _Impl::__apply(__first, __result);
 }
 
 _LIBCPP_END_NAMESPACE_STD