[libc++] Implement ranges::iota (#68494)

# Overview

As a disclaimer, this is my first PR to LLVM and while I've tried to
ensure I've followed the LLVM and libc++ contributing guidelines,
there's probably a good chance I missed something. If I have, just let
me know and I'll try to correct it as soon as I can.

This PR implements `std::ranges::iota` and
`std::ranges::out_value_result` outlined in
[P2440r1](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2440r1.html).

As outlined in the paper above, I've:
- Implemented `out_value_result` and added to `<algorithm>`
- Added `out_value_result`, `iota_result`, and two overloads of `iota`
to `std::ranges` in `<numeric>`
- Updated the version macro `__cpp_lib_ranges_iota` in `<version>`

I've also added tests for `ranges::iota` and `ranges::out_value_result`.
Lastly, I added those structs to the appropriate module files.

Partially implements #105184

EDIT: Forgot to mention in the original post, thanks to @hawkinsw for
taking a look at a preliminary version of this PR!

# TODOs
- [x] Updating the range [status
doc](https://github.com/jamesETsmith/llvm-project/blob/main/libcxx/docs/Status/RangesMajorFeatures.csv)
- [x] Ensure all comments from https://reviews.llvm.org/D121436 are
addressed here
- [X] EDIT (I'll do this in a separate PR). ~~I'm open to implementing
the rest of P2440r1 (`ranges::shift_left` and `ranges::shift_right`) if
that's ok, I just wanted to get feedback on `ranges::iota` first~~
- [x] I've been having trouble building the modules locally and want to
make sure that's working properly

Closes: #134060

5 files changed, 170 insertions, 13 deletions

diff --git a/libcxx/test/std/algorithms/algorithms.results/no_unique_address.compile.pass.cpp b/libcxx/test/std/algorithms/algorithms.results/no_unique_address.compile.pass.cpp
index 34dbd64..70da332 100644
--- a/libcxx/test/std/algorithms/algorithms.results/no_unique_address.compile.pass.cpp
+++ b/libcxx/test/std/algorithms/algorithms.results/no_unique_address.compile.pass.cpp
@@ -53,7 +53,10 @@ static_assert(sizeof(std::ranges::in_out_out_result<Empty, Empty, char>) == 2);
 static_assert(sizeof(std::ranges::in_out_out_result<int, Empty, Empty2>) == sizeof(int));
 static_assert(sizeof(std::ranges::in_out_out_result<Empty, Empty, Empty>) == 3);
 
-#if TEST_STD_VER >= 23
+#if _LIBCPP_STD_VER >= 23
+static_assert(sizeof(std::ranges::out_value_result<Empty, int>) == sizeof(int));
+static_assert(sizeof(std::ranges::out_value_result<int, Empty>) == sizeof(int));
+static_assert(sizeof(std::ranges::out_value_result<Empty, Empty>) == 2);
 
 static_assert(sizeof(std::ranges::in_value_result<Empty, int>) == sizeof(int));
 static_assert(sizeof(std::ranges::in_value_result<int, Empty>) == sizeof(int));
diff --git a/libcxx/test/std/algorithms/algorithms.results/out_value_result.pass.cpp b/libcxx/test/std/algorithms/algorithms.results/out_value_result.pass.cpp
new file mode 100644
index 0000000..7bdbb7f
--- /dev/null
+++ b/libcxx/test/std/algorithms/algorithms.results/out_value_result.pass.cpp
@@ -0,0 +1,141 @@
+//===----------------------------------------------------------------------===//
+//
+// 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, c++20
+
+//  template <class O, class T>
+//    struct out_value_result;
+
+#include <algorithm>
+#include <cassert>
+#include <type_traits>
+
+#include "MoveOnly.h"
+
+using std::ranges::out_value_result;
+
+//
+// Helper structs
+//
+
+// only explicit construction
+struct IterTypeExplicit {
+  explicit IterTypeExplicit(int*);
+};
+
+// implicit construction
+struct IterTypeImplicit {
+  IterTypeImplicit(int*);
+};
+
+struct IterTypeImplicitRef {
+  IterTypeImplicitRef(int&);
+};
+
+struct NotConvertible {};
+
+template <class T>
+struct ConvertibleFrom {
+  constexpr ConvertibleFrom(T c) : content{c} {}
+  T content;
+};
+
+// Standard layout classes can't have virtual functions
+struct NonStandardLayoutTypeBase {
+  virtual ~NonStandardLayoutTypeBase();
+};
+struct NonStandardLayoutType : public NonStandardLayoutTypeBase {};
+
+//
+constexpr bool test_constraints() {
+  // requires convertible_to<const _OutIter1&, _OutIter2> && convertible_to<const _ValType1&, _ValType2>
+  static_assert(std::is_constructible_v<out_value_result<int*, int>, out_value_result<int*, int>>);
+
+  // test failure when implicit conversion isn't allowed
+  static_assert(!std::is_constructible_v<out_value_result<IterTypeExplicit, int>, out_value_result<int*, int>>);
+
+  // test success when implicit conversion is allowed, checking combinations of value, reference, and const
+  static_assert(std::is_constructible_v<out_value_result<IterTypeImplicit, int>, out_value_result<int*, int>>);
+  static_assert(std::is_constructible_v<out_value_result<IterTypeImplicit, int>, out_value_result<int*, int> const>);
+  static_assert(std::is_constructible_v<out_value_result<IterTypeImplicit, int>, out_value_result<int*, int>&>);
+  static_assert(std::is_constructible_v<out_value_result<IterTypeImplicit, int>, out_value_result<int*, int> const&>);
+
+  static_assert(!std::is_constructible_v<out_value_result<IterTypeImplicitRef, int>, out_value_result<int, int>&>);
+
+  // has to be convertible via const&
+  static_assert(std::is_convertible_v<out_value_result<int, int>&, out_value_result<long, long>>);
+  static_assert(std::is_convertible_v<const out_value_result<int, int>&, out_value_result<long, long>>);
+  static_assert(std::is_convertible_v<out_value_result<int, int>&&, out_value_result<long, long>>);
+  static_assert(std::is_convertible_v<const out_value_result<int, int>&&, out_value_result<long, long>>);
+
+  // should be move constructible
+  static_assert(std::is_move_constructible_v<out_value_result<MoveOnly, int>>);
+  static_assert(std::is_move_constructible_v<out_value_result<int, MoveOnly>>);
+
+  // conversions should not work if there is no conversion
+  static_assert(!std::is_convertible_v<out_value_result<NotConvertible, int>, out_value_result<int, NotConvertible>>);
+  static_assert(!std::is_convertible_v<out_value_result<int, NotConvertible>, out_value_result<NotConvertible, int>>);
+
+  // check standard layout
+  static_assert(std::is_standard_layout_v<out_value_result<int, int>>);
+  static_assert(!std::is_standard_layout_v<out_value_result<NonStandardLayoutType, int>>);
+
+  return true;
+}
+
+// Test results
+constexpr bool test() {
+  {
+    // Check that conversion operator works
+    out_value_result<double, int> res{10, 1};
+    assert(res.out == 10);
+    assert(res.value == 1);
+    out_value_result<ConvertibleFrom<double>, ConvertibleFrom<int>> res2 = res;
+    assert(res2.out.content == 10);
+    assert(res2.value.content == 1);
+  }
+  {
+    // Check that out_value_result isn't overconstrained w.r.t. move/copy constructors
+    out_value_result<MoveOnly, int> res{MoveOnly{}, 10};
+    assert(res.out.get() == 1);
+    assert(res.value == 10);
+    auto res2 = std::move(res);
+    assert(res.out.get() == 0);
+    assert(res.value == 10);
+    assert(res2.out.get() == 1);
+    assert(res2.value == 10);
+  }
+  {
+    // Check structured binding
+    auto [out, val] = out_value_result<int, int>{1, 2};
+    assert(out == 1);
+    assert(val == 2);
+  }
+  {
+    // Check default construction
+    out_value_result<int, double> res;
+    static_assert(std::is_same_v<int, decltype(res.out)>);
+    static_assert(std::is_same_v<double, decltype(res.value)>);
+  }
+  {
+    // Check aggregate initiazliation
+    out_value_result<int, int> res = {1, 2};
+    assert(res.out == 1);
+    assert(res.value == 2);
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test_constraints();
+  static_assert(test_constraints());
+  test();
+  static_assert(test());
+  return 0;
+}
diff --git a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp
index 6940b23..dcf2509 100644
--- a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp
@@ -13,6 +13,7 @@
 // ensure that all result alias declarations are defined
 
 #include <algorithm>
+#include <numeric>
 #include <memory>
 #include <type_traits>
 
@@ -62,9 +63,6 @@ static_assert(std::is_same_v<in_found_result<int>, next_permutation_result<int>>
 static_assert(std::is_same_v<in_found_result<int>, prev_permutation_result<int>>);
 
 #if TEST_STD_VER >= 23
-
 static_assert(std::is_same_v<in_value_result<int, long>, fold_left_with_iter_result<int, long>>);
-
-// static_assert(std::is_same_v<out_value_result<int>, iota_result<int>>);
-
+static_assert(std::is_same_v<out_value_result<int, int>, iota_result<int, int>>);
 #endif // TEST_STD_VER
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
index 2691269..e0a6aaa 100644
--- a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
@@ -18,11 +18,13 @@
 #include <concepts>
 #include <functional>
 #include <iterator>
+#include <numeric>
 #include <ranges>
 #include <random>
 #include <utility>
 
 #include "test_iterators.h"
+#include "test_macros.h"
 
 struct NonBorrowedRange {
   using Iter = int*;
@@ -78,6 +80,9 @@ constexpr bool test_all() {
   using std::ranges::move_result;
   using std::ranges::move_backward_result;
   using std::ranges::next_permutation_result;
+#if TEST_STD_VER >= 23
+  using std::ranges::out_value_result;
+#endif
   using std::ranges::partial_sort_copy_result;
   using std::ranges::partition_copy_result;
   using std::ranges::prev_permutation_result;
@@ -217,6 +222,10 @@ constexpr bool test_all() {
   dangling_1st<prev_permutation_result<dangling>>(std::ranges::prev_permutation, in);
   dangling_1st<next_permutation_result<dangling>>(std::ranges::next_permutation, in);
 
+#if TEST_STD_VER >= 23
+  dangling_1st<out_value_result<dangling, decltype(x)>>(std::ranges::iota, in, x);
+#endif
+
   return true;
 }
 
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
index bebaeb0..9d4b0d6 100644
--- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
@@ -14,6 +14,7 @@
 // a customization point) rather than plain `swap` (which might not work with certain valid iterators).
 
 #include <algorithm>
+#include <numeric>
 
 #include <array>
 #include <concepts>
@@ -28,22 +29,22 @@
 #include "test_macros.h"
 
 // (in, ...)
-template <class Func, std::ranges::range Input, class ...Args>
-constexpr void test(Func&& func, Input& in, Args&& ...args) {
+template <class Func, std::ranges::range Input, class... Args>
+constexpr void test(Func&& func, Input& in, Args&&... args) {
   (void)func(in.begin(), in.end(), std::forward<Args>(args)...);
   (void)func(in, std::forward<Args>(args)...);
 }
 
 // (in1, in2, ...)
-template <class Func, std::ranges::range Range1, std::ranges::range Range2, class ...Args>
-constexpr void test(Func&& func, Range1& r1, Range2& r2, Args&& ...args) {
+template <class Func, std::ranges::range Range1, std::ranges::range Range2, class... Args>
+constexpr void test(Func&& func, Range1& r1, Range2& r2, Args&&... args) {
   (void)func(r1.begin(), r1.end(), r2.begin(), r2.end(), std::forward<Args>(args)...);
   (void)func(r1, r2, std::forward<Args>(args)...);
 }
 
 // (in, mid, ...)
-template <class Func, std::ranges::range Input, class ...Args>
-constexpr void test_mid(Func&& func, Input& in, std::ranges::iterator_t<Input> mid, Args&& ...args) {
+template <class Func, std::ranges::range Input, class... Args>
+constexpr void test_mid(Func&& func, Input& in, std::ranges::iterator_t<Input> mid, Args&&... args) {
   (void)func(in.begin(), mid, in.end(), std::forward<Args>(args)...);
   (void)func(in, mid, std::forward<Args>(args)...);
 }
@@ -68,9 +69,9 @@ constexpr void run_tests() {
   Proxy<T&> x{num};
   int count = 1;
 
-  auto unary_pred = [](const Proxy<T&>&) { return true; };
+  auto unary_pred  = [](const Proxy<T&>&) { return true; };
   auto binary_func = [](const Proxy<T>&, const Proxy<T>&) -> Proxy<T> { return Proxy<T>(T()); };
-  auto gen = [] { return Proxy<T>(T{42}); };
+  auto gen         = [] { return Proxy<T>(T{42}); };
 
   test(std::ranges::any_of, in, unary_pred);
   test(std::ranges::all_of, in, unary_pred);
@@ -106,6 +107,11 @@ constexpr void run_tests() {
   test(std::ranges::search, in, in2);
   test(std::ranges::search_n, in, count, x);
   test(std::ranges::find_end, in, in2);
+#if TEST_STD_VER >= 23
+  if constexpr (std::weakly_incrementable<T>) {
+    test(std::ranges::iota, in, x);
+  }
+#endif
   test(std::ranges::is_partitioned, in, unary_pred);
   test(std::ranges::is_sorted, in);
   test(std::ranges::is_sorted_until, in);