[libc++][ranges] Add ranges::in_in_result

[philnik]

Summary

Add std::ranges::in_in_result

[philnik]

• Added <algorithm> changes

[• Quuxplusone]

libcxx/include/__algorithm/results.h

10–11 ↗

(On Diff #396194)

This is the right header guard, but the wrong everything else. ;) I'd like to see this in a file named __algorithm/in_in_result.h.
It would also be useful to see a dependent PR (as a "child revision" of this one) implementing some algorithm that actually uses this type. std::ranges::swap_ranges would be a good candidate.

libcxx/include/algorithm

20–38

Defer to @ldionne's opinion on this, but I wonder if it would suffice to replace lines 20–38 with

template <class I1, class I2>
  struct ranges::in_in_result;  // since C++20

Going into the full level of detail for every single result type here in this synopsis comment is going to take hundreds of lines, for very little benefit that I can discern.

libcxx/test/std/algorithms/algorithms.results/in_in_result.pass.cpp

39

Please make this simply

std::ranges::in_in_result<double, int> res2 = res;
assert(res2.in1 == 10);
assert(res2.in2 == 0);

For simplicity/realism, and also because you need to test that the conversion is non-explicit.

You're missing tests to verify (1) that convertible_to is not constructible_from, e.g.

struct A { explicit A(int); };
static_assert(!std::is_constructible_v<std::ranges::in_in_result<A, A>, std::ranges::in_in_result<int, int>>);

and (2) that the copy constructor can still be used when the move-constructor can't, e.g.

struct B { B(const int&); B(int&&) = delete; };
static_assert(std::is_constructible_v<std::ranges::in_in_result<B, B>, std::ranges::in_in_result<int, int>>);
static_assert(std::is_constructible_v<std::ranges::in_in_result<B, B>, std::ranges::in_in_result<int, int>&>);
static_assert(std::is_constructible_v<std::ranges::in_in_result<B, B>, const std::ranges::in_in_result<int, int>>);
static_assert(std::is_constructible_v<std::ranges::in_in_result<B, B>, const std::ranges::in_in_result<int, int>&>);

struct C { C(int&); };
static_assert(!std::is_constructible_v<std::ranges::in_in_result<C, C>, std::ranges::in_in_result<int, int>&>);

(Here I'm using !is_constructible to prove that there's not just "not an implicit ctor", but also not an explicit ctor either.)

50

I'd also like to see tests that the conversion operator is unconditionally noexcept(false).
(No conditional-explicit, no 4x overloads for perfect forwarding, no conditional noexcept... These result types are strangely old-school, compared to most Ranges stuff.)

[philnik]

• Renamed results.h to in_in_result.h
• Updated test

libcxx/include/__algorithm/results.h

10–11 ↗

(On Diff #396194)

I see you want me to do more work :). I'll add one soon.

libcxx/test/std/algorithms/algorithms.results/in_in_result.pass.cpp

39

You can't cast to std::ranges::in_in_result<double, int>, because that would be narrowing int to double and double to int, which is not allowed here IIUC.

50

Do you want more than checking that all const and & possibilities are checked to be noexcept(false) or is that enough?

[• Quuxplusone]

libcxx/test/std/algorithms/algorithms.results/in_in_result.pass.cpp

39

libstdc++ thinks in_in_result<int, double> is convertible to in_in_result<double, int> https://godbolt.org/z/WaeTMq6T5 and it makes intuitive sense to me that it should be convertible, because int is convertible to double and vice versa.
But Microsoft STL produces the SFINAE-unfriendly narrowing diagnostic you were worried about: https://godbolt.org/z/qTqsYKn9c
Do you feel like digging into libstdc++ and figuring out whether they're doing something blatantly problematic to make this work? libstdc++'s behavior certainly feels nicer to me: whenever the conversion operator exists, it ought to compile. If we followed MSVC's lead here, we'd basically be lying to std::is_convertible_v.

50

What you have below seems to me like enough.

[philnik]

libcxx/test/std/algorithms/algorithms.results/in_in_result.pass.cpp

39

It seems the only difference is that GCC disables conversion warnings: https://godbolt.org/z/TvfTsjP5d. The implementation itself is exactly the same.

[philnik]

ping @Quuxplusone

[philnik]

Rebased

[• Quuxplusone]

LGTM % nitpicks.

libcxx/include/CMakeLists.txt

29–31

Swap lines 30 and 31: inp < in_ < is_ seems good to me.

libcxx/include/__algorithm/in_in_result.h

14–15

Swap these two lines. (One of these days I'll make graph_header_deps.py just check for a-z order.)

libcxx/include/algorithm

20

This namespace formatting is going to be weird no matter what we do, but I suggest just adding a blank line between lines 19 and 20.

697

Swap with line 694: inp < in_ < is_ seems good to me.

libcxx/test/std/algorithms/algorithms.results/in_in_result.pass.cpp

15

Remove this #include of a private header. (The Modules build should be unhappy with this, right?)

[philnik]

• Addressed comments

libcxx/include/__algorithm/in_in_result.h

14–15

You know there is a clang-tidy check for that, right? Maybe we should just enforce the clang-tidy checks at some point?

[philnik]

• Added module test

[• Quuxplusone]

libcxx/include/__algorithm/in_in_result.h

14–15

Just posted D116809! If you have the ability to run clang-tidy locally, it'd be interesting to see what it says about that branch. Like, is clang-tidy happy with that branch, or would it still complain — and if so, do you think its remaining complaints are valid?

[philnik]

• Added UNSUPPORTED comments

[philnik]

• XFAIL on msvc

[• Quuxplusone]

libcxx/test/std/algorithms/algorithms.results/in_in_result.pass.cpp

14–15

I just checked the build results, and it looks like the only problem with this test is that it checks something like sizeof(in_in_result<Empty, int>) == sizeof(int), which we expect to fail on MSVC. So you should just guard that one test under an appropriate #if, or IMO even better, split that test case out into in_in_result.no_unique_address.pass.cpp and XFAIL only that file. At the same time you can expand the test coverage to test sizeof(in_in_result<int, Empty>) and sizeof(in_in_result<Empty, Empty>) too!

38

[philnik]

• Move [[no_unique_address]] test into its own file

[• Quuxplusone]

libcxx/test/std/algorithms/algorithms.results/in_in_result.pass.cpp

75–80

Nit: If you s/Empty/int/ on lines 75–77, then you don't need line 34 at all in this file anymore.

[philnik]

• Use MoveOnly.h

[ldionne]

libcxx/include/algorithm

20–38

Yeah, I think just mentioning the forward declaration of in_in_result is enough, like we appear to be doing in the current version of the patch.

[Mordante]

Mostly looks good, but there are some remaining issues.

libcxx/include/__algorithm/in_in_result.h

37

libcxx/include/module.modulemap

250

This should be one line below, like in the header.

libcxx/test/std/algorithms/algorithms.results/in_in_result.pass.cpp

61

Can you also test the contents of main as constexpr ?

75

libcxx/test/std/algorithms/algorithms.results/no_unique_address.compile.pass.cpp

18

Since this test is in std instead of libcxx I think it would be good to mention the class may only have the two members specified in the standard.
http://eel.is/c++draft/algorithms.results#1

25

Why 2 * sizeof(Empty)?

[• Quuxplusone]

libcxx/test/std/algorithms/algorithms.results/no_unique_address.compile.pass.cpp

18

@Mordante: Are you basically asking to replace line 16 with

// [algorithms.results]/1
//   Each of the class templates specified in this subclause has the template parameters,
//   data members, and special members specified below, and has no base classes or members
//   other than those specified.

? (If so: I like that idea!)

@philnik: The fact that the standard defines exactly two members, both public, probably means that we're mandated to support structured binding:

[[maybe_unused]] auto [in1, in2] = std::ranges::in_in_result<int, int>{1, 2};

Consider adding that simple test case to in_in_result.pass.cpp. (Attn: @var-const, re in_out_result.pass.cpp, for consistency.)

25

Because of the "empty-base exclusion principle".
FWIW, I would have just said == 2); since sizeof-an-empty-class is 1 by definition AFAIK.

[Mordante]

libcxx/test/std/algorithms/algorithms.results/no_unique_address.compile.pass.cpp

18

Yes and adding a structured bindings test is a good idea!

25

Seems there's always a blog post :-)
I thought [[no_unique_address]] allows it to be 1. Reading your blog and looking in the standard I see
the answer in [intro.object]/9 "Two objects with overlapping lifetimes that are not bit-fields may have the same address if one is nested within the other, or if at least one is a subobject of zero size and they are of different types; otherwise, they have distinct addresses and occupy disjoint bytes of storage."

Thanks.

[philnik]

• Address comments

[philnik]

libcxx/test/std/algorithms/algorithms.results/no_unique_address.compile.pass.cpp

25

I thought 2 * sizeof(Empty) would be clearer than just 2.

[Mordante]

LGTM with one suggestion.

libcxx/test/std/algorithms/algorithms.results/in_in_result.pass.cpp

73

Maybe remove the [[maybe_unused]] and test whether in1 and in2 have the proper values.

[philnik]

• Address comment

libcxx/include/CMakeLists.txt

set(files
   __algorithm/find_if_not.h
   __algorithm/find_if.h
   __algorithm/find.h
   __algorithm/for_each_n.h
   __algorithm/for_each.h
   __algorithm/generate_n.h
   __algorithm/generate.h
   __algorithm/half_positive.h
   __algorithm/includes.h
   __algorithm/inplace_merge.h
+  __algorithm/in_in_result.h
   __algorithm/is_heap_until.h
   __algorithm/is_heap.h
   __algorithm/is_partitioned.h
   __algorithm/is_permutation.h
   __algorithm/is_sorted_until.h
   __algorithm/is_sorted.h
   __algorithm/iter_swap.h
   __algorithm/lexicographical_compare.h

libcxx/include/__algorithm/in_in_result.h

+// -*- 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___ALGORITHM_IN_IN_RESULT_H
+#define _LIBCPP___ALGORITHM_IN_IN_RESULT_H
+
+#include <__concepts/convertible_to.h>
+#include <__config>
+#include <__utility/move.h>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#ifndef _LIBCPP_HAS_NO_RANGES
+
+namespace ranges {
+template <class _I1, class _I2>
+struct in_in_result {
+  [[no_unique_address]] _I1 in1;
+  [[no_unique_address]] _I2 in2;
+
+  template <class _II1, class _II2>
+    requires convertible_to<const _I1&, _II1> && convertible_to<const _I2&, _II2>
+  constexpr operator in_in_result<_II1, _II2>() const & {
+    return {in1, in2};
+  }
+
+  template <class _II1, class _II2>
+    requires convertible_to<_I1, _II1> && convertible_to<_I2, _II2>
+    constexpr operator in_in_result<_II1, _II2>() && { return {_VSTD::move(in1), _VSTD::move(in2)}; }
+};
+} // namespace ranges
+
+#endif // _LIBCPP_HAS_NO_RANGES
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_IN_IN_RESULT_H

libcxx/include/algorithm

 
 /*
     algorithm synopsis
 
 #include <initializer_list>
 
 namespace std
 {
 
+namespace ranges {
+  template <class I1, class I2>
+    struct in_in_result; // since C++20
+}
+
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     all_of(InputIterator first, InputIterator last, Predicate pred);
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     any_of(InputIterator first, InputIterator last, Predicate pred);
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     none_of(InputIterator first, InputIterator last, Predicate pred);
 
 template <class InputIterator, class Function>
     constexpr Function          // constexpr in C++20
     for_each(InputIterator first, InputIterator last, Function f);
 
 template<class InputIterator, class Size, class Function>
     constexpr InputIterator     // constexpr in C++20
     for_each_n(InputIterator first, Size n, Function f); // C++17
 
 template <class InputIterator, class T>

 #include <__algorithm/find_if_not.h>
 #include <__algorithm/for_each.h>
 #include <__algorithm/for_each_n.h>
 #include <__algorithm/generate_n.h>
 #include <__algorithm/generate.h>
 #include <__algorithm/half_positive.h>
 #include <__algorithm/includes.h>
 #include <__algorithm/inplace_merge.h>
+#include <__algorithm/in_in_result.h>
 #include <__algorithm/is_heap.h>
 #include <__algorithm/is_heap_until.h>
 #include <__algorithm/is_partitioned.h>
 #include <__algorithm/is_permutation.h>
 #include <__algorithm/is_sorted.h>
 #include <__algorithm/is_sorted_until.h>
 #include <__algorithm/iter_swap.h>
 #include <__algorithm/lexicographical_compare.h>
 #include <__algorithm/lower_bound.h>
 #include <__algorithm/make_heap.h>

libcxx/include/module.modulemap

module __algorithm {
       module find_if                  { private header "__algorithm/find_if.h" }
       module find_if_not              { private header "__algorithm/find_if_not.h" }
       module for_each                 { private header "__algorithm/for_each.h" }
       module for_each_n               { private header "__algorithm/for_each_n.h" }
       module generate                 { private header "__algorithm/generate.h" }
       module generate_n               { private header "__algorithm/generate_n.h" }
       module half_positive            { private header "__algorithm/half_positive.h" }
       module includes                 { private header "__algorithm/includes.h" }
       module inplace_merge            { private header "__algorithm/inplace_merge.h" }
+      module in_in_result             { private header "__algorithm/in_in_result.h" }
       module is_heap                  { private header "__algorithm/is_heap.h" }
       module is_heap_until            { private header "__algorithm/is_heap_until.h" }
       module is_partitioned           { private header "__algorithm/is_partitioned.h" }
       module is_permutation           { private header "__algorithm/is_permutation.h" }
       module is_sorted                { private header "__algorithm/is_sorted.h" }
       module is_sorted_until          { private header "__algorithm/is_sorted_until.h" }
       module iter_swap                { private header "__algorithm/iter_swap.h" }
       module lexicographical_compare  { private header "__algorithm/lexicographical_compare.h" }

libcxx/test/libcxx/diagnostics/detail.headers/algorithm/in_in_result.module.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
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: modules-build
+
+// WARNING: This test was generated by 'generate_private_header_tests.py'
+// and should not be edited manually.
+
+// expected-error@*:* {{use of private header from outside its module: '__algorithm/in_in_result.h'}}
+#include <__algorithm/in_in_result.h>

libcxx/test/std/algorithms/algorithms.results/in_in_result.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template <class I1, class I2>
+// struct in_in_result;
+
+#include <algorithm>
+#include <cassert>
+#include <type_traits>
+
+#include "MoveOnly.h"
+
+template <class T>
+struct ConstructibleFrom {
+  constexpr ConstructibleFrom(T c) : content{c} {}
+  T content;
+};
+
+struct A {
+  explicit A(int);
+};
+static_assert(!std::is_constructible_v<std::ranges::in_in_result<A, A>,
+                                       std::ranges::in_in_result<int, int>>);
+
+struct B {
+  B(const int&);
+  B(int&&);
+};
+static_assert(std::is_constructible_v<std::ranges::in_in_result<B, B>, std::ranges::in_in_result<int, int>>);
+static_assert(std::is_constructible_v<std::ranges::in_in_result<B, B>, std::ranges::in_in_result<int, int>&>);
+static_assert(std::is_constructible_v<std::ranges::in_in_result<B, B>, const std::ranges::in_in_result<int, int>>);
+static_assert(std::is_constructible_v<std::ranges::in_in_result<B, B>, const std::ranges::in_in_result<int, int>&>);
+
+struct C {
+  C(int&);
+};
+static_assert(!std::is_constructible_v<std::ranges::in_in_result<C, C>, std::ranges::in_in_result<int, int>&>);
+
+static_assert(std::is_convertible_v<         std::ranges::in_in_result<int, int>&, std::ranges::in_in_result<long, long>>);
+static_assert(!std::is_nothrow_convertible_v<std::ranges::in_in_result<int, int>&, std::ranges::in_in_result<long, long>>);
+static_assert(std::is_convertible_v<         const std::ranges::in_in_result<int, int>&, std::ranges::in_in_result<long, long>>);
+static_assert(!std::is_nothrow_convertible_v<const std::ranges::in_in_result<int, int>&, std::ranges::in_in_result<long, long>>);
+static_assert(std::is_convertible_v<         std::ranges::in_in_result<int, int>&&, std::ranges::in_in_result<long, long>>);
+static_assert(!std::is_nothrow_convertible_v<std::ranges::in_in_result<int, int>&&, std::ranges::in_in_result<long, long>>);
+static_assert(std::is_convertible_v<         const std::ranges::in_in_result<int, int>&&, std::ranges::in_in_result<long, long>>);
+static_assert(!std::is_nothrow_convertible_v<const std::ranges::in_in_result<int, int>&&, std::ranges::in_in_result<long, long>>);
+
+constexpr bool test() {
+  {
+    std::ranges::in_in_result<int, double> res{10L, 0.};
+    assert(res.in1 == 10);
+    assert(res.in2 == 0.);
+    std::ranges::in_in_result<ConstructibleFrom<int>, ConstructibleFrom<double>> res2 = res;
+    assert(res2.in1.content == 10);
+    assert(res2.in2.content == 0.);
+  }
+  {
+    std::ranges::in_in_result<MoveOnly, int> res{MoveOnly{}, 0};
+    assert(res.in1.get() == 1);
+    [[maybe_unused]] auto res2 = static_cast<std::ranges::in_in_result<MoveOnly, int>>(std::move(res));
+    assert(res.in1.get() == 0);
+  }
+  auto [in1, in2] = std::ranges::in_in_result<int, int>{1, 2};
+  assert(in1 == 1);
+  assert(in2 == 2);
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/algorithms.results/no_unique_address.compile.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// clang-cl and cl currently don't support [[no_unique_address]]
+// XFAIL: msvc
+
+// [algorithms.results]/1
+//   Each of the class templates specified in this subclause has the template parameters,
+//   data members, and special members specified below, and has no base classes or members
+//   other than those specified.
+
+#include <algorithm>
+
+struct Empty {};
+
+static_assert(sizeof(std::ranges::in_in_result<Empty, int>) == sizeof(int));
+static_assert(sizeof(std::ranges::in_in_result<int, Empty>) == sizeof(int));
+static_assert(sizeof(std::ranges::in_in_result<Empty, Empty>) == 2 * sizeof(Empty));