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

[var-const]

Summary

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.

[jloser]

I don't personally love changing the code here for a regression that caught user code UB, but I understand.

In any case, can we add a test for the "invalid proxy iterator" case to bind this support to avoid future regressions in this area, please?

[philnik]

Are you absolutely certain that this won't break anything else? I'm definitely not, so I'd say rather break invalid code than valid code.

[ldionne]

I like this new approach regardless of the issues raised in D129823 because it is closer to decltype(auto), and that's what we're trying to achieve at the end of the day.

However, the truth is that any iterator that lies about its iterator_traits::reference is a potential issue just waiting to explode, and since we can easily diagnose it, I think we should. That's why I've suggested adding a static_assert as a QOI thing.

Is it going to break some code? Probably, but that will actually point out potential bugs in people's code, which is a nice property to have.

libcxx/include/__algorithm/iterator_operations.h

68

This way, we'll match the definition of iter_reference_t.

71

IMO that's easier to read, since I don't have to substitute __deref_t in my head and work through the additional declval<T>() layer.

77–80

84–85

(suggested message, feel free to change)

The full link is http://eel.is/c++draft/input.iterators#tab:inputiterator.

Also, please add a libc++ specific test to ensure that we do trigger the static_assert at least when we call std::sort with a mis-behaving iterator.

[var-const]

Address feedback.

[var-const]

In D130538#3678928, @philnik wrote:

Are you absolutely certain that this won't break anything else? I'm definitely not, so I'd say rather break invalid code than valid code.

I'm not absolutely certain, but the same can be said of any change of non-trivial complexity. Even completely ignoring the MySQL issue, this change is arguably an improvement because it brings this implementation closer to how the actual C++20 iter_move is specified, and at the end of the day we are trying to emulate that. I believe we would have used decltype here from the start, but we had the (incorrect) assumption that it's not supported in C++03. If you have a specific concern, I'm of course happy to address it.

libcxx/include/__algorithm/iterator_operations.h

84–85

Done (with a slight tweak to the wording).

I created a helper function and added this assertion to both specializations of __iter_move.

[var-const]

For future context, the issue of incorrect iterator_traits came up from a breakage in MySQL; more context here: https://reviews.llvm.org/D129823#3677969.

[var-const]

For future context, the issue of incorrect iterator_traits came up from a breakage in MySQL; more context here: https://reviews.llvm.org/D129823#3677969.

[ldionne]

LGTM pending CI.

[var-const]

Rebase.

[huixie90]

libcxx/include/__algorithm/iterator_operations.h

76–77

nit: i think the comments no long apply anymore. The return type also has sfinae logic in it

93

extra nit: perhaps we don't need to forward it, because the __deref_t and _move_t are defined in terms of lvalue of _Iter

[var-const]

Fix the CI (a constexpr function can only return void starting from C++14).

[var-const]

Address feedback.

[var-const]

libcxx/include/__algorithm/iterator_operations.h

76–77

Rephrased the comment to make it clearer that we can't use decltype(auto) or auto as the return type, regardless of the SFINAE.

93

Discussed offline -- this makes it closer to how iter_reference_t and iter_move are defined in C++20, and there doesn't seem to be an observable difference.

libcxx/include/__algorithm/iterator_operations.h

 //===----------------------------------------------------------------------===//
 //
 // 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_ITERATOR_OPERATIONS_H
 #define _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H
 
 #include <__algorithm/iter_swap.h>
 #include <__config>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iter_move.h>
 #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>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
struct _IterOps<_ClassicAlgPolicy> {
 
   // distance
   template <class _Iter>
   _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>
+  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> >
+    __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> >
+    __validate_iter_reference<_Iter>();
+
     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
   template <class _Iterator>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
   _Iterator next(_Iterator, _Iterator __last) {
     return __last;
   }
 
   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);
   }
 
   template <class _Iter>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
   void __advance_to(_Iter& __first, _Iter __last) {
     __first = __last;
   }
 };
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H

libcxx/test/libcxx/algorithms/bad_iterator_traits.verify.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
+//
+//===----------------------------------------------------------------------===//
+
+// 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}}
+}