1 files changed, 176 insertions, 8 deletions
diff --git a/contrib/llvm-project/libcxx/include/__iterator/reverse_iterator.h b/contrib/llvm-project/libcxx/include/__iterator/reverse_iterator.h
index 7f4ef3c3d503..5c344c2ee310 100644
--- a/contrib/llvm-project/libcxx/include/__iterator/reverse_iterator.h
+++ b/contrib/llvm-project/libcxx/include/__iterator/reverse_iterator.h
@@ -197,6 +197,12 @@ public:
 #endif // _LIBCPP_STD_VER > 17
 };
 
+template <class _Iter>
+struct __is_reverse_iterator : false_type {};
+
+template <class _Iter>
+struct __is_reverse_iterator<reverse_iterator<_Iter> > : true_type {};
+
 template <class _Iter1, class _Iter2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 bool
@@ -327,20 +333,162 @@ reverse_iterator<_Iter> make_reverse_iterator(_Iter __i)
 }
 #endif
 
+#if _LIBCPP_STD_VER <= 17
 template <class _Iter>
-using _ReverseWrapper = reverse_iterator<reverse_iterator<_Iter> >;
+using __unconstrained_reverse_iterator = reverse_iterator<_Iter>;
+#else
 
-template <class _Iter, bool __b>
-struct __unwrap_iter_impl<_ReverseWrapper<_Iter>, __b> {
+// __unconstrained_reverse_iterator allows us to use reverse iterators in the implementation of algorithms by working
+// around a language issue in C++20.
+// In C++20, when a reverse iterator wraps certain C++20-hostile iterators, calling comparison operators on it will
+// result in a compilation error. However, calling comparison operators on the pristine hostile iterator is not
+// an error. Thus, we cannot use reverse_iterators in the implementation of an algorithm that accepts a
+// C++20-hostile iterator. This class is an internal workaround -- it is a copy of reverse_iterator with
+// tweaks to make it support hostile iterators.
+//
+// A C++20-hostile iterator is one that defines a comparison operator where one of the arguments is an exact match
+// and the other requires an implicit conversion, for example:
+//   friend bool operator==(const BaseIter&, const DerivedIter&);
+//
+// C++20 rules for rewriting equality operators create another overload of this function with parameters reversed:
+//   friend bool operator==(const DerivedIter&, const BaseIter&);
+//
+// This creates an ambiguity in overload resolution.
+//
+// Clang treats this ambiguity differently in different contexts. When operator== is actually called in the function
+// body, the code is accepted with a warning. When a concept requires operator== to be a valid expression, however,
+// it evaluates to false. Thus, the implementation of reverse_iterator::operator== can actually call operator== on its
+// base iterators, but the constraints on reverse_iterator::operator== prevent it from being considered during overload
+// resolution. This class simply removes the problematic constraints from comparison functions.
+template <class _Iter>
+class __unconstrained_reverse_iterator {
+  _Iter __iter_;
+
+public:
+  static_assert(__is_cpp17_bidirectional_iterator<_Iter>::value);
+
+  using iterator_type = _Iter;
+  using iterator_category =
+      _If<__is_cpp17_random_access_iterator<_Iter>::value, random_access_iterator_tag, __iterator_category_type<_Iter>>;
+  using pointer = __iterator_pointer_type<_Iter>;
+  using value_type = iter_value_t<_Iter>;
+  using difference_type = iter_difference_t<_Iter>;
+  using reference = iter_reference_t<_Iter>;
+
+  _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator() = default;
+  _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator(const __unconstrained_reverse_iterator&) = default;
+  _LIBCPP_HIDE_FROM_ABI constexpr explicit __unconstrained_reverse_iterator(_Iter __iter) : __iter_(__iter) {}
+
+  _LIBCPP_HIDE_FROM_ABI constexpr _Iter base() const { return __iter_; }
+  _LIBCPP_HIDE_FROM_ABI constexpr reference operator*() const {
+    auto __tmp = __iter_;
+    return *--__tmp;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr pointer operator->() const {
+    if constexpr (is_pointer_v<_Iter>) {
+      return std::prev(__iter_);
+    } else {
+      return std::prev(__iter_).operator->();
+    }
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator& operator++() {
+    --__iter_;
+    return *this;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator operator++(int) {
+    auto __tmp = *this;
+    --__iter_;
+    return __tmp;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator& operator--() {
+    ++__iter_;
+    return *this;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator operator--(int) {
+    auto __tmp = *this;
+    ++__iter_;
+    return __tmp;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator& operator+=(difference_type __n) {
+    __iter_ -= __n;
+    return *this;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator& operator-=(difference_type __n) {
+    __iter_ += __n;
+    return *this;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator operator+(difference_type __n) const {
+    return __unconstrained_reverse_iterator(__iter_ - __n);
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator operator-(difference_type __n) const {
+    return __unconstrained_reverse_iterator(__iter_ + __n);
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr difference_type operator-(const __unconstrained_reverse_iterator& __other) const {
+    return __other.__iter_ - __iter_;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr auto operator[](difference_type __n) const { return *(*this + __n); }
+
+  // Deliberately unconstrained unlike the comparison functions in `reverse_iterator` -- see the class comment for the
+  // rationale.
+  _LIBCPP_HIDE_FROM_ABI friend constexpr bool
+  operator==(const __unconstrained_reverse_iterator& __lhs, const __unconstrained_reverse_iterator& __rhs) {
+    return __lhs.base() == __rhs.base();
+  }
+
+  _LIBCPP_HIDE_FROM_ABI friend constexpr bool
+  operator!=(const __unconstrained_reverse_iterator& __lhs, const __unconstrained_reverse_iterator& __rhs) {
+    return __lhs.base() != __rhs.base();
+  }
+
+  _LIBCPP_HIDE_FROM_ABI friend constexpr bool
+  operator<(const __unconstrained_reverse_iterator& __lhs, const __unconstrained_reverse_iterator& __rhs) {
+    return __lhs.base() > __rhs.base();
+  }
+
+  _LIBCPP_HIDE_FROM_ABI friend constexpr bool
+  operator>(const __unconstrained_reverse_iterator& __lhs, const __unconstrained_reverse_iterator& __rhs) {
+    return __lhs.base() < __rhs.base();
+  }
+
+  _LIBCPP_HIDE_FROM_ABI friend constexpr bool
+  operator<=(const __unconstrained_reverse_iterator& __lhs, const __unconstrained_reverse_iterator& __rhs) {
+    return __lhs.base() >= __rhs.base();
+  }
+
+  _LIBCPP_HIDE_FROM_ABI friend constexpr bool
+  operator>=(const __unconstrained_reverse_iterator& __lhs, const __unconstrained_reverse_iterator& __rhs) {
+    return __lhs.base() <= __rhs.base();
+  }
+};
+
+template <class _Iter>
+struct __is_reverse_iterator<__unconstrained_reverse_iterator<_Iter>> : true_type {};
+
+#endif // _LIBCPP_STD_VER <= 17
+
+template <template <class> class _RevIter1, template <class> class _RevIter2, class _Iter>
+struct __unwrap_reverse_iter_impl {
   using _UnwrappedIter = decltype(__unwrap_iter_impl<_Iter>::__unwrap(std::declval<_Iter>()));
+  using _ReverseWrapper = _RevIter1<_RevIter2<_Iter> >;
 
-  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _ReverseWrapper<_Iter>
-  __rewrap(_ReverseWrapper<_Iter> __orig_iter, _UnwrappedIter __unwrapped_iter) {
-    return _ReverseWrapper<_Iter>(
-        reverse_iterator<_Iter>(__unwrap_iter_impl<_Iter>::__rewrap(__orig_iter.base().base(), __unwrapped_iter)));
+  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _ReverseWrapper
+  __rewrap(_ReverseWrapper __orig_iter, _UnwrappedIter __unwrapped_iter) {
+    return _ReverseWrapper(
+        _RevIter2<_Iter>(__unwrap_iter_impl<_Iter>::__rewrap(__orig_iter.base().base(), __unwrapped_iter)));
   }
 
-  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _UnwrappedIter __unwrap(_ReverseWrapper<_Iter> __i) _NOEXCEPT {
+  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _UnwrappedIter __unwrap(_ReverseWrapper __i) _NOEXCEPT {
     return __unwrap_iter_impl<_Iter>::__unwrap(__i.base().base());
   }
 };
@@ -355,6 +503,26 @@ _LIBCPP_HIDE_FROM_ABI constexpr ranges::
 }
 #endif
 
+template <class _Iter, bool __b>
+struct __unwrap_iter_impl<reverse_iterator<reverse_iterator<_Iter> >, __b>
+    : __unwrap_reverse_iter_impl<reverse_iterator, reverse_iterator, _Iter> {};
+
+#if _LIBCPP_STD_VER > 17
+
+template <class _Iter, bool __b>
+struct __unwrap_iter_impl<reverse_iterator<__unconstrained_reverse_iterator<_Iter>>, __b>
+    : __unwrap_reverse_iter_impl<reverse_iterator, __unconstrained_reverse_iterator, _Iter> {};
+
+template <class _Iter, bool __b>
+struct __unwrap_iter_impl<__unconstrained_reverse_iterator<reverse_iterator<_Iter>>, __b>
+    : __unwrap_reverse_iter_impl<__unconstrained_reverse_iterator, reverse_iterator, _Iter> {};
+
+template <class _Iter, bool __b>
+struct __unwrap_iter_impl<__unconstrained_reverse_iterator<__unconstrained_reverse_iterator<_Iter>>, __b>
+    : __unwrap_reverse_iter_impl<__unconstrained_reverse_iterator, __unconstrained_reverse_iterator, _Iter> {};
+
+#endif // _LIBCPP_STD_VER > 17
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_REVERSE_ITERATOR_H