[libc++][ranges] Implement `std::mergeable`.

[var-const]

Rebase, use the correct link to the patch on the status page.

[• Quuxplusone]

Looks pretty reasonable to me, mod comments.

libcxx/include/__iterator/mergeable.h

17

Here you need __iterator/projected.h and maybe some others; but the Modular CI build should tell you about it.

27–28

Please put the linebreak before class _Comp. (At least not between Proj1 and Proj2.)

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.compile.pass.cpp

19

Why is <compare> needed?

50

int& operator*() const; ?

59

Grammar nit: AssignableOnlyFromInt

74

Because invocable<BadComp, int&, int&> is false, right? I think it would be cleaner to replace lines 73–79 with just

static_assert( std::mergeable<InputIterator, InputIterator, OutputIterator, bool(*)(int, int)>);
static_assert(!std::mergeable<InputIterator, InputIterator, OutputIterator, bool(*)(int*, int*)>);

90

I might not be parsing this correctly, but isn't decltype(BadProjection()(InputIterator(std::declval<int*>()))) simply Empty?

Here I think it would be cleaner to replace lines 81–92 with something like

static_assert( std::mergeable<const int*, const int*, int*, bool(*)(int, int), std::identity, std::identity>);
static_assert( std::mergeable<const int*, const int*, int*, bool(*)(int, int), int(*)(int), int(*)(int)>);
static_assert(!std::mergeable<const int*, const int*, int*, bool(*)(int, int), int*(*)(int), int(*)(int)>);
static_assert(!std::mergeable<const int*, const int*, int*, bool(*)(int, int), int(*)(int), int*(*)(int)>);
static_assert(!std::mergeable<const int*, const int*, int*, bool(*)(int*, int), int*(*)(int), int(*)(int)>);
static_assert(!std::mergeable<const int*, const int*, int*, bool(*)(int, int*), int(*)(int), int*(*)(int)>);

This doesn't cover anything about value categories / ref-qualification, though, so maybe think about whether we expect something like

struct Projection {
    bool operator(int&, int&) const;
    bool operator(int&&, int&&) const = delete;
};

to work, not-work, or be IFNDR; and whether removing the const from operator() would break anything.

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.subsumption.compile.pass.cpp

21–28

Please add blank lines between these definitions to keep them from all running together visually (since they don't fit on a single line each).

I see clang-format thinks line 25 is a "continuation line" rather than a "separate line"? :P

[var-const]

Address feedback and rebase.

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.compile.pass.cpp

59

Done.

(I'm not a native speaker, but I thought both are fine? At least, I've definitely seen "only" used at the end of a sentence quite a bit, e.g. https://en.wikipedia.org/wiki/For_Your_Eyes_Only)

74

Done. I still think it's good to check whether the comparator defines a strict weak order because it makes the intention of the test clearer (and I created aliases for the function types).

90

Replaced with the tests you provided, thanks (also added some type aliases).

struct Projection is intended to be used as a comparator, right? It does work in practice (also when operator() is not const). It's a good question whether it should work, though. From a glance, I feel like we shouldn't demand the invocation operator to be const (we take it by value and don't have to make our copy const, after all). I think the pre-ranges algorithms allow functors to take their arguments by a non-const reference, but if the functor modifies the values, it's undefined behavior, and I suppose an argument could be made that ranges algorithms should also support this for ease of conversion. As for rvalue arguments, I'm not sure. I don't think we need to solve this in this patch, though.

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.subsumption.compile.pass.cpp

21–28

Done. This was formatted manually, clang-format actually merges these into a single line.

[• Quuxplusone]

LGTM mod comments, but I think someone else should also take a look.

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.compile.pass.cpp

32

Huh, I didn't notice until now that mergeable does not actually require that O be an output_iterator — i.e. mergeable<A,B,O> doesn't subsume output_iterator<O, iter_value_t<I>>.
Perhaps you should define your own struct Output here that satisfies only the very minimal requirements and is not actually an output iterator; is that physically possible?

82–83

How about naming these ToInt and ToPtr?
(Or of course eliminating all the typedefs. Implicit in my suggestions here is that I find simple types like int* much easier to parse at a glance, than typedefs like Input and Output where it's not even clear that they're iterators, let alone that their value type is int. So anywhere that the iterator type is "uninteresting," I'd much prefer to see a boring type like int* instead of a typedef. This even extends to the function types: I find bool(*)(int, int) easier to parse than GoodComp.)

90

struct Projection is intended to be used as a comparator, right?

Oops, yeah. I think I started my thought thinking "projection," but then muscle memory turned it into a comparator halfway through. I think the interesting case I was trying to get at was

struct Projection {
    int operator(int&) const;
    int operator(int&&) const = delete;
};

i.e. making sure that the projection was called as proj(*first) with *first as a mutable lvalue.

[var-const]

Address feedback (in particular, add a test case for WeaklyIncrementable
that's not an output iterator).

[var-const]

Add a comment to WeaklyIncrementable, rebase.

[var-const]

Fix and expand comment.

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.compile.pass.cpp

32

Yes, it's possible (the way I found is this: weakly_incrementable only requires it++ to be defined, while output_iterator requires it to return something dereferenceable, thus making it return void does the trick). Added a test case for that.

82–83

Thanks, I like these names more.

(I think this depends a lot on personal preference. I'm the other way round -- I find a wall of pointer types with small variations throughout to be quite unreadable, and I think "parsing" natural language is easier than special symbols. Also, using typedefs makes it easier to change the types throughout the file)

90

Projection also works with the current implementation (also with libstdc++ and MSVC implementations).

I think this should work -- mergeable requires the underlying type to be copyable, not just movable between the iterators. If the implementation deals with a copy of the value, restricting the projection to e.g. only const references seems to go against that contract.

Do you want to add Projection as a test case (i.e., do we want to explicitly commit to supporting this)?

[• Quuxplusone]

Continues to LGTM; continue to want one other person to rubber-stamp it at least.

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.compile.pass.cpp

90

Do you want to add Projection as a test case (i.e., do we want to explicitly commit to supporting this)?

Yes, my reading of the standard is that we have to support this. (In fact, we have to support Projection even when its operator() is not const-qualified!) Now, probably when we get to the actual ranges::merge algorithm we'll find it's not so clear-cut, at least in theory; but for concept mergeable, the chain of logic/code seems pretty unassailable.

98–99

Drive-by grammar nit ;) but also, mainly, adjusted the line-break point.

[var-const]

Address feedback

[ldionne]

LGTM with ultra nit.

libcxx/include/iterator

155–158

This is a nit, but can we match the order of the synopsis in the Standard: indirectly_swappable, indirectly_comparable, permutable, mergeable?

[var-const]

Address feedback, fix the CI, rebase on main.

[var-const]

Rebase on main.

[• Quuxplusone]

libcxx/include/iterator

532

Nit: This blank line looks unnecessary.

[var-const]

Remove an accidental empty line, rebase on main.

[var-const]

Guard mergeable with _LIBCPP_HAS_NO_INCOMPLETE_RANGES (because it depends on
ranges::less which is guarded by it).

[var-const]

Rebase, mark the subsumption test as not supporting incomplete ranges.

[var-const]

Add a test case for non-default projections.

[var-const]

The CI error looks unrelated (in AIX 32-bit):

Failed Tests (1):
  ibm-libc++-shared.cfg.in ::
std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/try_lock_shared.pass.cpp

libcxx/docs/Status/RangesPaper.csv

 `[alg.req] <https://wg21.link/alg.req>`_: pt. 1,"| `indirectly_movable <https://llvm.org/D102639>`_
 | `indirectly_movable_storable <https://llvm.org/D102639>`_
 | `indirectly_copyable <https://llvm.org/D118432>`_
 | `indirectly_copyable_storable <https://llvm.org/D118432>`_",[iterator.concepts],Zoe Carver and Konstantin Varlamov,✅
 `[alg.req] <https://wg21.link/alg.req>`_: pt. 2,`indirectly_swappable <https://llvm.org/D105304>`_,"| [iterator.concepts]
 | [iterator.cust.swap]",Zoe Carver,✅
 `[alg.req] <https://wg21.link/alg.req>`_: pt. 3,`indirectly_comparable <https://llvm.org/D116268>`_,[projected],Nikolas Klauser,✅
 `[alg.req] <https://wg21.link/alg.req>`_: pt. 4,"| `permutable <https://llvm.org/D119222>`_
-| mergeable
+| `mergeable <https://llvm.org/D119489>`_
 | sortable",[iterator.concepts],Konstantin Varlamov,In progress
 `[std.iterator.tags] <https://wg21.link/std.iterator.tags>`_,"| `contiguous_iterator_tag <https://llvm.org/rG45d048c20440989df2b4e1be1f9343225e7741ab>`_
 | `iterator_concept specialization for pointers <https://llvm.org/rG45d048c20440989df2b4e1be1f9343225e7741ab>`_
 ",[iterator.traits],Eric Fiselier,✅
 `[range.iter.ops] <https://wg21.link/range.iter.ops>`_,"| `ranges::advance <https://llvm.org/D101922>`_
 | `ranges::distance <https://llvm.org/D102789>`_
 | `ranges::next <https://llvm.org/D102563>`_
 | `ranges::prev <https://llvm.org/D102564>`_",[iterator.concepts],Christopher Di Bella and Arthur O'Dwyer,✅

libcxx/include/CMakeLists.txt

set(files
   __iterator/indirectly_comparable.h
   __iterator/insert_iterator.h
   __iterator/istream_iterator.h
   __iterator/istreambuf_iterator.h
   __iterator/iter_move.h
   __iterator/iter_swap.h
   __iterator/iterator.h
   __iterator/iterator_traits.h
+  __iterator/mergeable.h
   __iterator/move_iterator.h
   __iterator/next.h
   __iterator/ostream_iterator.h
   __iterator/ostreambuf_iterator.h
   __iterator/permutable.h
   __iterator/prev.h
   __iterator/projected.h
   __iterator/readable_traits.h

libcxx/include/__iterator/mergeable.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___ITERATOR_MERGEABLE_H
+#define _LIBCPP___ITERATOR_MERGEABLE_H
+
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+template <class _Input1, class _Input2, class _Output,
+          class _Comp = ranges::less, class _Proj1 = identity, class _Proj2 = identity>
+concept mergeable =
+    input_iterator<_Input1> &&
+    input_iterator<_Input2> &&
+    weakly_incrementable<_Output> &&
+    indirectly_copyable<_Input1, _Output> &&
+    indirectly_copyable<_Input2, _Output> &&
+    indirect_strict_weak_order<_Comp, projected<_Input1, _Proj1>, projected<_Input2, _Proj2>>;
+
+#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ITERATOR_MERGEABLE_H

libcxx/include/iterator

 
 template<class In, class Out>
   concept indirectly_copyable_storable = see below;         // since C++20
 
 // [alg.req.ind.swap], concept indirectly_swappable
 template<class I1, class I2 = I1>
   concept indirectly_swappable = see below;                // since C++20
 
-// [alg.req.permutable], concept permutable                // since C++20
-template<class I>
-  concept permutable = see below;
-
 template<class I1, class I2, class R, class P1 = identity,
          class P2 = identity>
   concept indirectly_comparable =
     indirect_binary_predicate<R, projected<I1, P1>, projected<I2, P2>>; // since C++20
 
+// [alg.req.permutable], concept permutable                // since C++20
+template<class I>
+  concept permutable = see below;
+
+ // [alg.req.mergeable], concept mergeable
+template<class I1, class I2, class Out,
+    class R = ranges::less, class P1 = identity, class P2 = identity>
+  concept mergeable = see below;                           // since C++20
+
 template<input_or_output_iterator I, sentinel_for<I> S>
   requires (!same_as<I, S> && copyable<I>)
 class common_iterator;                                     // since C++20
 
 template<class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T*, class Reference = T&>
 struct iterator                                            // deprecated in C++17
 {
public:
     istreambuf_iterator(a-private-type) noexcept;
 
     charT                operator*() const;
     pointer operator->() const;
     istreambuf_iterator& operator++();
     a-private-type       operator++(int);
 
     bool equal(const istreambuf_iterator& b) const;
     friend bool operator==(const istreambuf_iterator& i, default_sentinel_t s); // since C++20
 };
 
 template <class charT, class traits>
 bool operator==(const istreambuf_iterator<charT,traits>& a,
                 const istreambuf_iterator<charT,traits>& b);
 template <class charT, class traits>
 bool operator!=(const istreambuf_iterator<charT,traits>& a,
                 const istreambuf_iterator<charT,traits>& b); // until C++20

 #include <__iterator/indirectly_comparable.h>
 #include <__iterator/insert_iterator.h>
 #include <__iterator/istream_iterator.h>
 #include <__iterator/istreambuf_iterator.h>
 #include <__iterator/iter_move.h>
 #include <__iterator/iter_swap.h>
 #include <__iterator/iterator.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/mergeable.h>
 #include <__iterator/move_iterator.h>
 #include <__iterator/next.h>
 #include <__iterator/ostream_iterator.h>
 #include <__iterator/ostreambuf_iterator.h>
 #include <__iterator/permutable.h>
 #include <__iterator/prev.h>
 #include <__iterator/projected.h>
 #include <__iterator/readable_traits.h>

libcxx/include/module.modulemap

module __iterator {
       module indirectly_comparable { private header "__iterator/indirectly_comparable.h" }
       module insert_iterator       { private header "__iterator/insert_iterator.h" }
       module istream_iterator      { private header "__iterator/istream_iterator.h" }
       module istreambuf_iterator   { private header "__iterator/istreambuf_iterator.h" }
       module iter_move             { private header "__iterator/iter_move.h" }
       module iter_swap             { private header "__iterator/iter_swap.h" }
       module iterator              { private header "__iterator/iterator.h" }
       module iterator_traits       { private header "__iterator/iterator_traits.h" }
+      module mergeable             { private header "__iterator/mergeable.h" }
       module move_iterator         { private header "__iterator/move_iterator.h" }
       module next                  { private header "__iterator/next.h" }
       module ostream_iterator      { private header "__iterator/ostream_iterator.h" }
       module ostreambuf_iterator   { private header "__iterator/ostreambuf_iterator.h" }
       module permutable            { private header "__iterator/permutable.h" }
       module prev                  { private header "__iterator/prev.h" }
       module projected             { private header "__iterator/projected.h" }
       module readable_traits       { private header "__iterator/readable_traits.h" }

libcxx/test/libcxx/diagnostics/detail.headers/iterator/mergeable.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: '__iterator/mergeable.h'}}
+#include <__iterator/mergeable.h>

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.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
+
+// template<class I1, class I2, class Out,
+//     class R = ranges::less, class P1 = identity, class P2 = identity>
+//   concept mergeable = see below;                           // since C++20
+
+#include <iterator>
+
+#include <functional>
+
+#include "test_iterators.h"
+#include "test_macros.h"
+
+using Comp = std::ranges::less;
+
+using Input = cpp20_input_iterator<int*>;
+static_assert( std::input_iterator<Input>);
+using InputLong = cpp20_input_iterator<long*>;
+static_assert( std::input_iterator<InputLong>);
+
+using Output = cpp17_output_iterator<int*>;
+static_assert( std::weakly_incrementable<Output>);
+
+static_assert( std::indirectly_copyable<Input, Output>);
+static_assert( std::indirectly_copyable<InputLong, Output>);
+static_assert( std::indirect_strict_weak_order<Comp, Input, Input>);
+static_assert( std::indirect_strict_weak_order<Comp, Input, InputLong>);
+
+// All requirements satisfied.
+static_assert( std::mergeable<Input, Input, Output>);
+
+// I1 or I2 is not an input iterator.
+static_assert(!std::input_iterator<Output>);
+static_assert(!std::mergeable<Output, Input, Output>);
+static_assert(!std::mergeable<Input, Output, Output>);
+
+// O is not weakly incrementable.
+struct NotWeaklyIncrementable {
+  int& operator*() const;
+};
+
+static_assert(!std::weakly_incrementable<NotWeaklyIncrementable>);
+static_assert( std::indirectly_copyable<Input, NotWeaklyIncrementable>);
+static_assert( std::indirect_strict_weak_order<Comp, Input, Input>);
+static_assert(!std::mergeable<Input, Input, NotWeaklyIncrementable>);
+
+// I1 or I2 is not indirectly copyable into O.
+struct AssignableOnlyFromInt {
+  AssignableOnlyFromInt& operator=(int);
+  template <class T>
+  AssignableOnlyFromInt& operator=(T) = delete;
+};
+using OutputOnlyInt = cpp17_output_iterator<AssignableOnlyFromInt*>;
+static_assert( std::weakly_incrementable<OutputOnlyInt>);
+
+static_assert( std::indirectly_copyable<Input, OutputOnlyInt>);
+static_assert(!std::indirectly_copyable<InputLong, OutputOnlyInt>);
+static_assert( std::indirect_strict_weak_order<Comp, Input, InputLong>);
+static_assert( std::mergeable<Input, Input, OutputOnlyInt>);
+static_assert(!std::mergeable<Input, InputLong, OutputOnlyInt>);
+static_assert(!std::mergeable<InputLong, Input, OutputOnlyInt>);
+
+// No indirect strict weak order between I1 and I2 (bad comparison functor).
+using GoodComp = bool(*)(int, int);
+static_assert( std::indirect_strict_weak_order<GoodComp, Input, Input>);
+static_assert( std::mergeable<Input, Input, Output, GoodComp>);
+using BadComp = bool(*)(int*, int*);
+static_assert(!std::indirect_strict_weak_order<BadComp, Input, Input>);
+static_assert(!std::mergeable<Input, Input, Output, BadComp>);
+
+// No indirect strict weak order between I1 and I2 (bad projection).
+using ToInt = int(*)(int);
+using ToPtr = int*(*)(int);
+static_assert( std::mergeable<Input, Input, Output, GoodComp, std::identity, std::identity>);
+static_assert( std::mergeable<Input, Input, Output, GoodComp, ToInt, ToInt>);
+static_assert(!std::mergeable<Input, Input, Output, GoodComp, ToPtr, ToInt>);
+static_assert(!std::mergeable<Input, Input, Output, GoodComp, ToInt, ToPtr>);
+static_assert(!std::mergeable<Input, Input, Output, bool(*)(int*, int), ToPtr, ToInt>);
+static_assert(!std::mergeable<Input, Input, Output, bool(*)(int, int*), ToInt, ToPtr>);
+
+// A projection that only supports non-const references and has a non-const `operator()` still has to work.
+struct ProjectionOnlyMutable {
+  int operator()(int&);
+  int operator()(int&&) const = delete;
+};
+static_assert( std::mergeable<Input, Input, Output, Comp, ProjectionOnlyMutable, ProjectionOnlyMutable>);
+
+// The output is weakly incrementable but not an output iterator.
+struct WeaklyIncrementable {
+  using value_type = int;
+  using difference_type = int;
+
+  int& operator*() const;
+  WeaklyIncrementable& operator++();
+  // `output_iterator` requires `i++` to return an iterator,
+  // while `weakly_incrementable` requires only that `i++` be well-formed.
+  void operator++(int);
+};
+static_assert( std::weakly_incrementable<WeaklyIncrementable>);
+static_assert( std::indirectly_copyable<int*, WeaklyIncrementable>);
+static_assert(!std::output_iterator<WeaklyIncrementable, int>);
+static_assert( std::mergeable<Input, Input, WeaklyIncrementable>);

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.subsumption.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
+
+// template<class I1, class I2, class Out,
+//     class R = ranges::less, class P1 = identity, class P2 = identity>
+//   concept mergeable = see below;                           // since C++20
+
+#include <iterator>
+
+#include "test_macros.h"
+
+template <class I1, class I2, class O>
+void test_subsumption() requires std::input_iterator<I1> && std::input_iterator<I2>;
+
+template <class I1, class I2, class O>
+void test_subsumption() requires std::weakly_incrementable<O>;
+
+template <class I1, class I2, class O>
+void test_subsumption() requires std::indirectly_copyable<I1, O> && std::indirectly_copyable<I2, O>;
+
+template <class I1, class I2, class O>
+void test_subsumption() requires std::indirect_strict_weak_order<I1, I2>;
+
+template <class I1, class I2, class O>
+constexpr bool test_subsumption() requires std::mergeable<I1, I2, O> {
+  return true;
+}
+
+static_assert(test_subsumption<int*, int*, int*>());