[libc++] Make `_IterOps::__iter_move` more similar to `std::ranges::iter_move`.

Avoid relying on `iterator_traits` and instead deduce the return type of
dereferencing the iterator. Additionally, add a static check to reject
iterators with incorrect `iterator_traits` at compile time.

Differential Revision: https://reviews.llvm.org/D130538

(cherry picked from commit b3afea1ce0bd3c9293edae67c1839318eecdd7bf)

2 files changed, 97 insertions, 13 deletions

diff --git a/libcxx/include/__algorithm/iterator_operations.h b/libcxx/include/__algorithm/iterator_operations.h
index 8307d71214e5..6ac5170b4a0e 100644
--- a/libcxx/include/__algorithm/iterator_operations.h
+++ b/libcxx/include/__algorithm/iterator_operations.h
@@ -17,6 +17,7 @@
 #include <__iterator/iter_swap.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
+#include <__utility/declval.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 #include <type_traits>
@@ -63,24 +64,46 @@ struct _IterOps<_ClassicAlgPolicy> {
     return std::distance(__first, __last);
   }
 
-  // iter_move
+  template <class _Iter>
+  using __deref_t = decltype(*std::declval<_Iter&>());
+
+  template <class _Iter>
+  using __move_t = decltype(std::move(*std::declval<_Iter&>()));
+
   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 remove_reference< typename iterator_traits<__uncvref_t<_Iter> >::reference >::type&&>
-      __iter_move(_Iter&& __i) {
+  static void __validate_iter_reference() {
+    static_assert(is_same<__deref_t<_Iter>, typename iterator_traits<__uncvref_t<_Iter> >::reference>::value,
+        "It looks like your iterator's `iterator_traits<It>::reference` does not match the return type of "
+        "dereferencing the iterator, i.e., calling `*it`. This is undefined behavior according to [input.iterators] "
+        "and can lead to dangling reference issues at runtime, so we are flagging this.");
+  }
+
+  // iter_move
+  template <class _Iter>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 static
+  // If the result of dereferencing `_Iter` is a reference type, deduce the result of calling `std::move` on it. Note
+  // that the C++03 mode doesn't support `decltype(auto)` as the return type.
+  __enable_if_t<
+      is_reference<__deref_t<_Iter> >::value,
+      __move_t<_Iter> >
+  __iter_move(_Iter&& __i) {
+    __validate_iter_reference<_Iter>();
+
     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) {
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 static
+  // If the result of dereferencing `_Iter` is a value type, deduce the return value of this function to also be a
+  // value -- otherwise, after `operator*` returns a temporary, this function would return a dangling reference to that
+  // temporary. Note that the C++03 mode doesn't support `auto` as the return type.
+  __enable_if_t<
+      !is_reference<__deref_t<_Iter> >::value,
+      __deref_t<_Iter> >
+  __iter_move(_Iter&& __i) {
+    __validate_iter_reference<_Iter>();
+
     return *std::forward<_Iter>(__i);
   }
 
@@ -100,7 +123,7 @@ struct _IterOps<_ClassicAlgPolicy> {
 
   template <class _Iter>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
-  __uncvref_t<_Iter> next(_Iter&& __it, 
+  __uncvref_t<_Iter> next(_Iter&& __it,
                           typename iterator_traits<__uncvref_t<_Iter> >::difference_type __n = 1){
     return std::next(std::forward<_Iter>(__it), __n);
   }
diff --git a/libcxx/test/libcxx/algorithms/bad_iterator_traits.verify.cpp b/libcxx/test/libcxx/algorithms/bad_iterator_traits.verify.cpp
new file mode 100644
index 000000000000..61e1712987e7
--- /dev/null
+++ b/libcxx/test/libcxx/algorithms/bad_iterator_traits.verify.cpp
@@ -0,0 +1,61 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// std::sort
+
+#include <algorithm>
+#include <iterator>
+#include <type_traits>
+#include <utility>
+
+struct BadIter {
+  struct Value {
+    friend bool operator==(const Value& x, const Value& y);
+    friend bool operator!=(const Value& x, const Value& y);
+    friend bool operator< (const Value& x, const Value& y);
+    friend bool operator<=(const Value& x, const Value& y);
+    friend bool operator> (const Value& x, const Value& y);
+    friend bool operator>=(const Value& x, const Value& y);
+    friend void swap(Value, Value);
+  };
+
+  using iterator_category = std::random_access_iterator_tag;
+  using value_type = Value;
+  using reference = Value&;
+  using difference_type = long;
+  using pointer = Value*;
+
+  Value operator*() const; // Not `Value&`.
+  reference operator[](difference_type n) const;
+
+  BadIter& operator++();
+  BadIter& operator--();
+  BadIter operator++(int);
+  BadIter operator--(int);
+
+  BadIter& operator+=(difference_type n);
+  BadIter& operator-=(difference_type n);
+  friend BadIter operator+(BadIter x, difference_type n);
+  friend BadIter operator+(difference_type n, BadIter x);
+  friend BadIter operator-(BadIter x, difference_type n);
+  friend difference_type operator-(BadIter x, BadIter y);
+
+  friend bool operator==(const BadIter& x, const BadIter& y);
+  friend bool operator!=(const BadIter& x, const BadIter& y);
+  friend bool operator< (const BadIter& x, const BadIter& y);
+  friend bool operator<=(const BadIter& x, const BadIter& y);
+  friend bool operator> (const BadIter& x, const BadIter& y);
+  friend bool operator>=(const BadIter& x, const BadIter& y);
+};
+
+// Verify that iterators with incorrect `iterator_traits` are rejected. This protects against potential undefined
+// behavior when these iterators are passed to standard algorithms.
+void test() {
+  std::sort(BadIter(), BadIter());
+  //expected-error-re@*:* {{{{(static_assert|static assertion)}} failed {{.*}}It looks like your iterator's `iterator_traits<It>::reference` does not match the return type of dereferencing the iterator}}
+}