[libc++][ranges] attempt to fix proxy iterator issues that cause Chromium to crash

[var-const]

Summary

[libc++][ranges] attempt to fix proxy iterator issues that cause Chromium to crash

The crash reported by Chrome v8 is related to sorting with v8::internal::AtomicSlot
According to https://chromium.googlesource.com/v8/v8/+/9bcb5eb590643db0c1f688fea316c7f1f4786a3c/src/objects/slots-atomic-inl.h
AtomicSlot is indeed a proxy iterator with a proxy type AtomicSlot::Reference

https://reviews.llvm.org/D130197 correctly spotted issues in __iter_move, but the fix does not fix the issue.
The reason is that AtomicSlot::operator* returns a prvalue Reference. After the fix in D130197, the return type
of __iter_move is Reference&&. But the rvalue reference is bond to the temporary value returned by operator*,
which will be dangling after __iter_move returns.

The idea of the fix in this change is borrowed from C++17's move_iterator
https://timsong-cpp.github.io/cppwp/n4659/move.iterators#move.iterator-1
When underlying reference is a prvalue, we just return it by value.

[var-const]

LGTM. It looks like the new tests still pass even without the fix, which means we still have work to do there. However, the tests are a great starting point, and I manually verified that the fix works, so I think it's good to go.

[var-const]

I'll commandeer this just to land this quicker -- @huixie90 I hope that's okay with you.

[var-const]

Rebase and reword the description.

libcxx/include/__algorithm/iterator_operations.h

struct _IterOps<_ClassicAlgPolicy> {
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
   static typename iterator_traits<_Iter>::difference_type distance(_Iter __first, _Iter __last) {
     return std::distance(__first, __last);
   }
 
   // iter_move
   template <class _Iter>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
       // Declaring the return type is necessary for C++03, so we basically mirror what `decltype(auto)` would deduce.
-  static typename remove_reference<
-      typename iterator_traits<__uncvref_t<_Iter> >::reference
-  >::type&& __iter_move(_Iter&& __i) {
+      static __enable_if_t<
+          is_reference<typename iterator_traits<__uncvref_t<_Iter> >::reference>::value,
+          typename remove_reference< typename iterator_traits<__uncvref_t<_Iter> >::reference >::type&&>
+      __iter_move(_Iter&& __i) {
     return std::move(*std::forward<_Iter>(__i));
   }
 
+  template <class _Iter>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+      // Declaring the return type is necessary for C++03, so we basically mirror what `decltype(auto)` would deduce.
+      static __enable_if_t<
+          !is_reference<typename iterator_traits<__uncvref_t<_Iter> >::reference>::value,
+          typename iterator_traits<__uncvref_t<_Iter> >::reference>
+      __iter_move(_Iter&& __i) {
+    return *std::forward<_Iter>(__i);
+  }
+
   // iter_swap
   template <class _Iter1, class _Iter2>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
   static void iter_swap(_Iter1&& __a, _Iter2&& __b) {
     std::iter_swap(std::forward<_Iter1>(__a), std::forward<_Iter2>(__b));
   }
 
   // next

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_proxy.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
 #include <algorithm>
 #include <cassert>
 #include <vector>
 
+struct Cpp17ProxyIterator {
+  struct Reference {
+    int* i_;
+    Reference(int& i) : i_(&i) {}
+
+    operator int() const { return *i_; }
+
+    Reference& operator=(int i) {
+      *i_ = i;
+      return *this;
+    }
+
+    friend bool operator<(const Reference& x, const Reference& y) { return *x.i_ < *y.i_; }
+
+    friend bool operator==(const Reference& x, const Reference& y) { return *x.i_ == *y.i_; }
+
+    friend void swap(Reference x, Reference y) { std::swap(*(x.i_), *(y.i_)); }
+  };
+
+  using difference_type   = int;
+  using value_type        = int;
+  using reference         = Reference;
+  using pointer           = void*;
+  using iterator_category = std::random_access_iterator_tag;
+
+  int* ptr_;
+
+  Cpp17ProxyIterator(int* ptr) : ptr_(ptr) {}
+
+  Reference operator*() const { return Reference(*ptr_); }
+
+  Cpp17ProxyIterator& operator++() {
+    ++ptr_;
+    return *this;
+  }
+
+  Cpp17ProxyIterator operator++(int) {
+    auto tmp = *this;
+    ++*this;
+    return tmp;
+  }
+
+  friend bool operator==(const Cpp17ProxyIterator& x, const Cpp17ProxyIterator& y) { return x.ptr_ == y.ptr_; }
+  friend bool operator!=(const Cpp17ProxyIterator& x, const Cpp17ProxyIterator& y) { return x.ptr_ != y.ptr_; }
+
+  Cpp17ProxyIterator& operator--() {
+    --ptr_;
+    return *this;
+  }
+
+  Cpp17ProxyIterator operator--(int) {
+    auto tmp = *this;
+    --*this;
+    return tmp;
+  }
+
+  Cpp17ProxyIterator& operator+=(difference_type n) {
+    ptr_ += n;
+    return *this;
+  }
+
+  Cpp17ProxyIterator& operator-=(difference_type n) {
+    ptr_ -= n;
+    return *this;
+  }
+
+  Reference operator[](difference_type i) const { return Reference(*(ptr_ + i)); }
+
+  friend bool operator<(const Cpp17ProxyIterator& x, const Cpp17ProxyIterator& y) { return x.ptr_ < y.ptr_; }
+
+  friend bool operator>(const Cpp17ProxyIterator& x, const Cpp17ProxyIterator& y) { return x.ptr_ > y.ptr_; }
+
+  friend bool operator<=(const Cpp17ProxyIterator& x, const Cpp17ProxyIterator& y) { return x.ptr_ <= y.ptr_; }
+
+  friend bool operator>=(const Cpp17ProxyIterator& x, const Cpp17ProxyIterator& y) { return x.ptr_ >= y.ptr_; }
+
+  friend Cpp17ProxyIterator operator+(const Cpp17ProxyIterator& x, difference_type n) {
+    return Cpp17ProxyIterator(x.ptr_ + n);
+  }
+
+  friend Cpp17ProxyIterator operator+(difference_type n, const Cpp17ProxyIterator& x) {
+    return Cpp17ProxyIterator(n + x.ptr_);
+  }
+
+  friend Cpp17ProxyIterator operator-(const Cpp17ProxyIterator& x, difference_type n) {
+    return Cpp17ProxyIterator(x.ptr_ - n);
+  }
+
+  friend difference_type operator-(Cpp17ProxyIterator x, Cpp17ProxyIterator y) {
+    return static_cast<int>(x.ptr_ - y.ptr_);
+  }
+};
+
 void test() {
   // TODO: use a custom proxy iterator instead of (or in addition to) `vector<bool>`.
   std::vector<bool> v(5, false);
-  v[1] = true; v[3] = true;
+  v[1] = true;
+  v[3] = true;
   std::sort(v.begin(), v.end());
   assert(std::is_sorted(v.begin(), v.end()));
 }
 
+void testCustomProxyIterator() {
+  int a[] = {5, 1, 3, 2, 4};
+  std::sort(Cpp17ProxyIterator(a), Cpp17ProxyIterator(a + 5));
+  assert(a[0] == 1);
+  assert(a[1] == 2);
+  assert(a[2] == 3);
+  assert(a[3] == 4);
+  assert(a[4] == 5);
+}
+
 int main(int, char**) {
   test();
-
+  testCustomProxyIterator();
   return 0;
 }