[libc++] Add std::ranges::iter_move and std::iter_rvalue_reference_t

Original patch by @cjdb, modified by @ldionne.

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

8 files changed, 442 insertions, 4 deletions

diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index 917fd03e0e39..d95d70b3b103 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -12,8 +12,9 @@ set(files
   __functional_base_03
   __hash_table
   __iterator/concepts.h
-  __iterator/iterator_traits.h
   __iterator/incrementable_traits.h
+  __iterator/iter_move.h
+  __iterator/iterator_traits.h
   __iterator/readable_traits.h
   __libcpp_version
   __locale
diff --git a/libcxx/include/__iterator/iter_move.h b/libcxx/include/__iterator/iter_move.h
new file mode 100644
index 000000000000..02cdf56724df
--- /dev/null
+++ b/libcxx/include/__iterator/iter_move.h
@@ -0,0 +1,90 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// 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___ITERATOR_ITER_MOVE_H
+#define _LIBCPP___ITERATOR_ITER_MOVE_H
+
+#include <__config>
+#include <__iterator/concepts.h>
+#include <concepts> // __class_or_enum
+#include <type_traits>
+#include <utility>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+
+namespace ranges::__iter_move {
+void iter_move();
+
+template<class _Ip>
+concept __unqualified_iter_move = requires(_Ip&& __i) {
+    iter_move(_VSTD::forward<_Ip>(__i));
+};
+
+// [iterator.cust.move]/1
+// The name ranges::iter_move denotes a customization point object.
+// The expression ranges::iter_move(E) for a subexpression E is
+// expression-equivalent to:
+struct __fn {
+  // [iterator.cust.move]/1.1
+  // iter_move(E), if E has class or enumeration type and iter_move(E) is a
+  // well-formed expression when treated as an unevaluated operand, [...]
+  template<class _Ip>
+    requires __class_or_enum<remove_cvref_t<_Ip>> && __unqualified_iter_move<_Ip>
+  [[nodiscard]] constexpr decltype(auto) operator()(_Ip&& __i) const
+    noexcept(noexcept(iter_move(_VSTD::forward<_Ip>(__i))))
+  {
+    return iter_move(_VSTD::forward<_Ip>(__i));
+  }
+
+  // [iterator.cust.move]/1.2
+  // Otherwise, if the expression *E is well-formed:
+  //  1.2.1 if *E is an lvalue, std::move(*E);
+  //  1.2.2 otherwise, *E.
+  template<class _Ip>
+    requires (!(__class_or_enum<remove_cvref_t<_Ip>> && __unqualified_iter_move<_Ip>)) &&
+    requires(_Ip&& __i) { *_VSTD::forward<_Ip>(__i); }
+  [[nodiscard]] constexpr decltype(auto) operator()(_Ip&& __i) const
+    noexcept(noexcept(*_VSTD::forward<_Ip>(__i)))
+  {
+    if constexpr (is_lvalue_reference_v<decltype(*_VSTD::forward<_Ip>(__i))>) {
+      return _VSTD::move(*_VSTD::forward<_Ip>(__i));
+    } else {
+      return *_VSTD::forward<_Ip>(__i);
+    }
+  }
+
+  // [iterator.cust.move]/1.3
+  // Otherwise, ranges::iter_move(E) is ill-formed.
+};
+} // namespace ranges::__iter_move
+
+namespace ranges::inline __cpo {
+  inline constexpr auto iter_move = __iter_move::__fn{};
+}
+
+template<__dereferenceable _Tp>
+requires requires(_Tp& __t) { { ranges::iter_move(__t) } -> __referenceable; }
+using iter_rvalue_reference_t = decltype(ranges::iter_move(declval<_Tp&>()));
+
+#endif // !_LIBCPP_HAS_NO_RANGES
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ITERATOR_ITER_MOVE_H
diff --git a/libcxx/include/concepts b/libcxx/include/concepts
index 295733b82a84..39c1f63f90a2 100644
--- a/libcxx/include/concepts
+++ b/libcxx/include/concepts
@@ -246,14 +246,16 @@ concept copy_constructible =
   constructible_from<_Tp, const _Tp&> && convertible_to<const _Tp&, _Tp> &&
   constructible_from<_Tp, const _Tp> && convertible_to<const _Tp, _Tp>;
 
+// Whether a type is a class type or enumeration type according to the Core wording.
+template<class _Tp>
+concept __class_or_enum = is_class_v<_Tp> || is_union_v<_Tp> || is_enum_v<_Tp>;
+
 // [concept.swappable]
 namespace ranges::__swap {
   // Deleted to inhibit ADL
   template<class _Tp>
   void swap(_Tp&, _Tp&) = delete;
 
-  template<class _Tp>
-  concept __class_or_enum = is_class_v<_Tp> || is_union_v<_Tp> || is_enum_v<_Tp>;
 
   // [1]
   template<class _Tp, class _Up>
@@ -440,7 +442,7 @@ concept equivalence_relation = relation<_Rp, _Tp, _Up>;
 template<class _Rp, class _Tp, class _Up>
 concept strict_weak_order = relation<_Rp, _Tp, _Up>;
 
-#endif //_LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
 
 _LIBCPP_END_NAMESPACE_STD
 
diff --git a/libcxx/include/iterator b/libcxx/include/iterator
index 2785fec9f756..34244358d75c 100644
--- a/libcxx/include/iterator
+++ b/libcxx/include/iterator
@@ -35,6 +35,14 @@ struct iterator_traits<T*>;
 template<dereferenceable T>
   using iter_reference_t = decltype(*declval<T&>());
 
+namespace ranges::inline unspecified {
+    inline constexpr unspecified iter_move = unspecified; // since C++20, nodiscard as an extension
+}}
+
+template<dereferenceable T>
+  requires ...
+using iter_rvalue_reference_t = decltype(ranges::iter_move(declval<T&>())); // since C++20
+
 template<class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T*, class Reference = T&>
 struct iterator
@@ -422,6 +430,7 @@ template <class E> constexpr const E* data(initializer_list<E> il) noexcept;
 #include <cstddef>
 #include <initializer_list>
 #include <__iterator/incrementable_traits.h>
+#include <__iterator/iter_move.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/readable_traits.h>
 #include <__memory/addressof.h>
diff --git a/libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.nodiscard.verify.cpp b/libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.nodiscard.verify.cpp
new file mode 100644
index 000000000000..747e76c4d1a7
--- /dev/null
+++ b/libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.nodiscard.verify.cpp
@@ -0,0 +1,38 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// Test the [[nodiscard]] extension in libc++.
+// REQUIRES: libc++
+
+// template<class I>
+// unspecified iter_move;
+
+#include <iterator>
+
+struct WithADL {
+  WithADL() = default;
+  constexpr decltype(auto) operator*() const noexcept;
+  constexpr WithADL& operator++() noexcept;
+  constexpr void operator++(int) noexcept;
+  constexpr bool operator==(WithADL const&) const noexcept;
+  friend constexpr auto iter_move(WithADL&) { return 0; }
+};
+
+int main(int, char**) {
+  int* noADL = nullptr;
+  std::ranges::iter_move(noADL); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}}
+
+  WithADL adl;
+  std::ranges::iter_move(adl); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}}
+
+  return 0;
+}
diff --git a/libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp b/libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp
new file mode 100644
index 000000000000..4f5d0eb7e182
--- /dev/null
+++ b/libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp
@@ -0,0 +1,212 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// template<class I>
+// unspecified iter_move;
+
+#include <iterator>
+
+#include <array>
+#include <algorithm>
+#include <cassert>
+#include <utility>
+
+#include "../unqualified_lookup_wrapper.h"
+
+// Wrapper around an iterator for testing `iter_move` when an unqualified call to `iter_move` isn't
+// possible.
+template <typename I>
+class iterator_wrapper {
+public:
+  iterator_wrapper() = default;
+
+  constexpr explicit iterator_wrapper(I i) noexcept : base_(std::move(i)) {}
+
+  // `noexcept(false)` is used to check that this operator is called.
+  [[nodiscard]] constexpr decltype(auto) operator*() const& noexcept(false) { return *base_; }
+
+  // `noexcept` is used to check that this operator is called.
+  [[nodiscard]] constexpr auto&& operator*() && noexcept { return std::move(*base_); }
+
+  constexpr iterator_wrapper& operator++() noexcept {
+    ++base_;
+    return *this;
+  }
+
+  constexpr void operator++(int) noexcept { ++base_; }
+
+  [[nodiscard]] constexpr bool operator==(iterator_wrapper const& other) const noexcept { return base_ == other.base_; }
+
+private:
+  I base_ = I{};
+};
+
+class move_tracker {
+public:
+  move_tracker() = default;
+
+  constexpr move_tracker(move_tracker&& other) noexcept : moves_{other.moves_ + 1} { other.moves_ = 0; }
+
+  constexpr move_tracker& operator=(move_tracker&& other) noexcept {
+    moves_ = other.moves_ + 1;
+    other.moves_ = 0;
+    return *this;
+  }
+
+  constexpr move_tracker(move_tracker const& other) = delete;
+  constexpr move_tracker& operator=(move_tracker const& other) = delete;
+
+  [[nodiscard]] constexpr int moves() const noexcept { return moves_; }
+
+private:
+  int moves_ = 0;
+};
+
+template <typename I>
+constexpr void unqualified_lookup_move(I first_, I last_, I result_first_, I result_last_) {
+  auto first = ::check_unqualified_lookup::unqualified_lookup_wrapper{std::move(first_)};
+  auto last = ::check_unqualified_lookup::unqualified_lookup_wrapper{std::move(last_)};
+  auto result_first = ::check_unqualified_lookup::unqualified_lookup_wrapper{std::move(result_first_)};
+  auto result_last = ::check_unqualified_lookup::unqualified_lookup_wrapper{std::move(result_last_)};
+
+  static_assert(!noexcept(std::ranges::iter_move(first)), "unqualified-lookup case not being chosen");
+
+  for (; first != last && result_first != result_last; (void)++first, ++result_first) {
+    *result_first = std::ranges::iter_move(first);
+  }
+}
+
+template <typename I>
+constexpr void lvalue_move(I first_, I last_, I result_first_, I result_last_) {
+  auto first = iterator_wrapper{std::move(first_)};
+  auto last = ::iterator_wrapper{std::move(last_)};
+  auto result_first = iterator_wrapper{std::move(result_first_)};
+  auto result_last = iterator_wrapper{std::move(result_last_)};
+
+  static_assert(!noexcept(std::ranges::iter_move(first)), "`operator*() const&` is not noexcept, and there's no hidden "
+                                                          "friend iter_move.");
+
+  for (; first != last && result_first != result_last; (void)++first, ++result_first) {
+    *result_first = std::ranges::iter_move(first);
+  }
+}
+
+template <typename I>
+constexpr void rvalue_move(I first_, I last_, I result_first_, I result_last_) {
+  auto first = iterator_wrapper{std::move(first_)};
+  auto last = iterator_wrapper{std::move(last_)};
+  auto result_first = iterator_wrapper{std::move(result_first_)};
+  auto result_last = iterator_wrapper{std::move(result_last_)};
+
+  static_assert(noexcept(std::ranges::iter_move(std::move(first))),
+                "`operator*() &&` is noexcept, and there's no hidden friend iter_move.");
+
+  for (; first != last && result_first != result_last; (void)++first, ++result_first) {
+    auto i = first;
+    *result_first = std::ranges::iter_move(std::move(i));
+  }
+}
+
+template <bool NoExcept>
+struct WithADL {
+  WithADL() = default;
+  constexpr int operator*() const { return 0; }
+  constexpr WithADL& operator++();
+  constexpr void operator++(int);
+  constexpr bool operator==(WithADL const&) const;
+  friend constexpr int iter_move(WithADL&&) noexcept(NoExcept) { return 0; }
+};
+
+template <bool NoExcept>
+struct WithoutADL {
+  WithoutADL() = default;
+  constexpr int operator*() const noexcept(NoExcept) { return 0; }
+  constexpr WithoutADL& operator++();
+  constexpr void operator++(int);
+  constexpr bool operator==(WithoutADL const&) const;
+};
+
+constexpr bool check_iter_move() {
+  constexpr int full_size = 100;
+  constexpr int half_size = full_size / 2;
+  constexpr int reset = 0;
+  auto v1 = std::array<move_tracker, full_size>{};
+
+  auto move_counter_is = [](auto const n) { return [n](auto const& x) { return x.moves() == n; }; };
+
+  auto v2 = std::array<move_tracker, half_size>{};
+  unqualified_lookup_move(v1.begin(), v1.end(), v2.begin(), v2.end());
+  assert(std::all_of(v1.cbegin(), v1.cend(), move_counter_is(reset)));
+  assert(std::all_of(v2.cbegin(), v2.cend(), move_counter_is(1)));
+
+  auto v3 = std::array<move_tracker, half_size>{};
+  unqualified_lookup_move(v1.begin() + half_size, v1.end(), v3.begin(), v3.end());
+  assert(std::all_of(v1.cbegin(), v1.cend(), move_counter_is(reset)));
+  assert(std::all_of(v3.cbegin(), v3.cend(), move_counter_is(1)));
+
+  auto v4 = std::array<move_tracker, half_size>{};
+  unqualified_lookup_move(v3.begin(), v3.end(), v4.begin(), v4.end());
+  assert(std::all_of(v3.cbegin(), v3.cend(), move_counter_is(reset)));
+  assert(std::all_of(v4.cbegin(), v4.cend(), move_counter_is(2)));
+
+  lvalue_move(v2.begin(), v2.end(), v1.begin() + half_size, v1.end());
+  assert(std::all_of(v2.cbegin(), v2.cend(), move_counter_is(reset)));
+  assert(std::all_of(v1.cbegin() + half_size, v1.cend(), move_counter_is(2)));
+
+  lvalue_move(v4.begin(), v4.end(), v1.begin(), v1.end());
+  assert(std::all_of(v4.cbegin(), v4.cend(), move_counter_is(reset)));
+  assert(std::all_of(v1.cbegin(), v1.cbegin() + half_size, move_counter_is(3)));
+
+  rvalue_move(v1.begin(), v1.end(), v2.begin(), v2.end());
+  assert(std::all_of(v1.cbegin(), v1.cbegin() + half_size, move_counter_is(reset)));
+  assert(std::all_of(v2.cbegin(), v2.cend(), move_counter_is(4)));
+
+  rvalue_move(v1.begin() + half_size, v1.end(), v3.begin(), v3.end());
+  assert(std::all_of(v1.cbegin(), v1.cend(), move_counter_is(reset)));
+  assert(std::all_of(v3.cbegin(), v3.cend(), move_counter_is(3)));
+
+  auto unscoped = check_unqualified_lookup::unscoped_enum::a;
+  assert(std::ranges::iter_move(unscoped) == check_unqualified_lookup::unscoped_enum::a);
+  assert(!noexcept(std::ranges::iter_move(unscoped)));
+
+  auto scoped = check_unqualified_lookup::scoped_enum::a;
+  assert(std::ranges::iter_move(scoped) == nullptr);
+  assert(noexcept(std::ranges::iter_move(scoped)));
+
+  auto some_union = check_unqualified_lookup::some_union{0};
+  assert(std::ranges::iter_move(some_union) == 0);
+  assert(!noexcept(std::ranges::iter_move(some_union)));
+
+  // Check noexcept-correctness
+  static_assert(noexcept(std::ranges::iter_move(std::declval<WithADL<true>>())));
+  static_assert(!noexcept(std::ranges::iter_move(std::declval<WithADL<false>>())));
+  static_assert(noexcept(std::ranges::iter_move(std::declval<WithoutADL<true>>())));
+  static_assert(!noexcept(std::ranges::iter_move(std::declval<WithoutADL<false>>())));
+
+  return true;
+}
+
+template <typename T>
+concept can_iter_move = requires (T t) { std::ranges::iter_move(t); };
+
+int main(int, char**) {
+  static_assert(check_iter_move());
+  check_iter_move();
+
+  // Make sure that `iter_move` SFINAEs away when the type can't be iter_move'd
+  {
+    struct NoIterMove { };
+    static_assert(!can_iter_move<NoIterMove>);
+  }
+
+  return 0;
+}
diff --git a/libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_rvalue_reference_t.pass.cpp b/libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_rvalue_reference_t.pass.cpp
new file mode 100644
index 000000000000..66da57e64427
--- /dev/null
+++ b/libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_rvalue_reference_t.pass.cpp
@@ -0,0 +1,26 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// template<class I>
+// using iter_rvalue_reference;
+
+#include <iterator>
+
+#include <concepts>
+#include <list>
+#include <vector>
+
+static_assert(std::same_as<std::iter_rvalue_reference_t<std::vector<int>::iterator&>, int&&>);
+static_assert(std::same_as<std::iter_rvalue_reference_t<std::vector<int>::const_iterator>, int const&&>);
+static_assert(std::same_as<std::iter_rvalue_reference_t<std::list<int const>::iterator>, int const&&>);
+
+int main(int, char**) { return 0; }
diff --git a/libcxx/test/std/iterators/iterator.requirements/iterator.cust/unqualified_lookup_wrapper.h b/libcxx/test/std/iterators/iterator.requirements/iterator.cust/unqualified_lookup_wrapper.h
new file mode 100644
index 000000000000..0f28f21e9b7d
--- /dev/null
+++ b/libcxx/test/std/iterators/iterator.requirements/iterator.cust/unqualified_lookup_wrapper.h
@@ -0,0 +1,60 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_TEST_STD_ITERATOR_UNQUALIFIED_LOOKUP_WRAPPER
+#define LIBCPP_TEST_STD_ITERATOR_UNQUALIFIED_LOOKUP_WRAPPER
+
+#include <iterator>
+#include <utility>
+
+namespace check_unqualified_lookup {
+// Wrapper around an iterator for testing unqualified calls to `iter_move` and `iter_swap`.
+template <typename I>
+class unqualified_lookup_wrapper {
+public:
+  unqualified_lookup_wrapper() = default;
+
+  constexpr explicit unqualified_lookup_wrapper(I i) noexcept : base_(std::move(i)) {}
+
+  [[nodiscard]] constexpr decltype(auto) operator*() const noexcept { return *base_; }
+
+  constexpr unqualified_lookup_wrapper& operator++() noexcept {
+    ++base_;
+    return *this;
+  }
+
+  constexpr void operator++(int) noexcept { ++base_; }
+
+  [[nodiscard]] constexpr bool operator==(unqualified_lookup_wrapper const& other) const noexcept {
+    return base_ == other.base_;
+  }
+
+  // Delegates `std::ranges::iter_move` for the underlying iterator. `noexcept(false)` will be used
+  // to ensure that the unqualified-lookup overload is chosen.
+  [[nodiscard]] friend constexpr decltype(auto) iter_move(unqualified_lookup_wrapper& i) noexcept(false) {
+    return std::ranges::iter_move(i.base_);
+  }
+
+private:
+  I base_ = I{};
+};
+
+enum unscoped_enum { a, b, c };
+constexpr unscoped_enum iter_move(unscoped_enum& e) noexcept(false) { return e; }
+
+enum class scoped_enum { a, b, c };
+constexpr scoped_enum* iter_move(scoped_enum&) noexcept { return nullptr; }
+
+union some_union {
+  int x;
+  double y;
+};
+constexpr int iter_move(some_union& u) noexcept(false) { return u.x; }
+
+} // namespace check_unqualified_lookup
+
+#endif // LIBCPP_TEST_STD_ITERATOR_UNQUALIFIED_LOOKUP_WRAPPER