[libc++] Implement `std::ranges::merge`

[huixie90]

Summary

Implement std::ranges::merge. added unit tests

[huixie90]

rebase

[huixie90]

removed cartesian_product utility

[huixie90]

reduce the number of output iterator types in the tests

[ldionne]

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

219

Typo!

[huixie90]

fix typo

[var-const]

Thanks a lot for working on this!

libcxx/include/__algorithm/ranges_merge.h

49

Nit: I don't think you need to qualify the ranges namespace on merge_result. Applies in a few places below as well. In general, we only qualify function calls due to ADL.

50

Question: why not place this function in the internal __merge namespace?

75

Formatting nit: namespace contents don't have to be indented in LLVM style. We generally follow that, and I think avoiding extra indentation where possible makes code more readable.

84

Ultranit: in __merge_impl, there is no space before the closing > angle brace, can you please make this consistent?

95

Move the iterators / possibly the other arguments as well?

111

Weird formatting here -- can you split the line after the template argument list?

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

38–39

FWIW:

• personally, I'd also change the HasFoo pattern -- it seems like there should be a name that's a bit more descriptive. I don't feel too strongly about it, though;
• the table looks very nice, but I'm concerned that it might require disproportionate effort to write and maintain.

109–112

FWIW, I also think that testing each type gets into the area of diminishing returns pretty quickly.

113

Question: what's the reason to take the arrays by lvalue reference?

116

Nit: it looks like this line should be split into two.

123

Optional: consider adding a typedef for merge_result -- it's pretty verbose and makes this line harder to parse.

153

Nit: consider removing this comment. This function doesn't directly deal with different iterator types (its caller does), so this comment seems a little confusing.

155

Can you add a brief comment to each test case to explain what is being tested? It makes quickly skimming through the file much easier.

171

Can you please also add tests for the following cases?

• range 1, range 2, or both range 1 and range 2 are empty;
• range 2 is shorter than range 1;
• all elements in range 1 are larger than in range 2 and vice versa;
• all elements are the same (in both ranges).

175

Nit: s/Borrow/Borrowed/.

193

Nit: using would be helpful here as well for the merge_result type.

211

Question: what does In1In2 stand for?

256

Hmm, the preconditions section in the standard doesn't indicate that the output range should be large enough to hold the result. Do you know if this precondition comes from some other section implicitly?

265

This needs to be asserted, right? (Alternatively, you could assert in the implementation of TracedCopy).

291

Nit: s/merged/be merged/ (or s/merged/merge/).

343

Is defining a custom struct necessary? It seems that passing something like ranges::greater would achieve the same goal with less test code.

399

Optional: s/std::ranges::equal_to{}/{}/ to decrease verbosity and make it more obvious that this argument is unimportant.

400

FWIW, I called the equivalent class for testing stable_sort OrderedValue (and used doubles for ordering because it allows for nice "syntax" to number duplicates, like {6, 6.1}, {6, 6.2}, etc.). But feel free to keep as is.

423

A couple of questions:

• do these tests add any coverage beyond the proj test case above?
• if we decide to keep them, should they also be written for both the range overload and the iterator overload?

470

Should this be tested for the iterator version as well? (applies to the ConvertibleToBool test case below as well)

553

Optional: I'm not sure this check buys us much. Consider moving these test cases into the "general" section in testImpl.

[huixie90]

address feedback

libcxx/include/__algorithm/ranges_merge.h

75

fixed. I used the .clang-format file under the libcxx folder and it is done by clang-format. Perhaps we should update the .clang-format file to do this?

95

the impl takes iterators by reference and use them as l-values, std::move them don't actually have any effects. or do I miss anything?

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

38–39

The main reason I dislike having default argument is, for example if I do

template <class InIter1, class InIter2, class OutIter, class Sent1 = sentinel_wrapper<InIter1>, class Sent2 = sentinel_wrapper<InIter2>>
concept hasMerge = ...;

Then in the test if I write

static_assert(hasMerge<Iter1, Iter2, Iter3, Iter4, Iter5>);

As I reader of the test (without scrolling to the top to see the definition of the hasMerge), I would expect the order of these 5 arguments would match the order of the arguments in std::ranges::merge, i.e.

InIter1 (Iter1), Sent1 (Iter2), InIter2 (Iter3), Sent2 (Iter4), OutIter (Iter5)

But, in fact, because of the default arguments, the actual order it is testing is

InIter1 (Iter1), InIter2 (Iter2), OutIter (Iter3), Sent1 (Iter4), Sent2 (Iter5)

The change of the order might lead to unnecessary confusion IMO.

Regarding the name, I don't like canMerge or hasMerge. I realised that I don't need to name it. there is already a thing I need in the standard std::invocable, so I changed it to use invocable.

Regarding the maintain of the table, another idea I have is to have inline comments to indicate what they are

static_assert( std::invocable<MergeFn, 
          int* /*InIter1*/,   int* /*Sent1*/,   int* /*InIter2*/,  int* /*Sent2*/,   int* /*OutIter*/>);

But I don't like it much

Alternatively, we can format arguments in different lines and the order of lines matches the order of the original argument lists in std::ranges::merge (because I use std::invocable)

static_assert( std::invocable<MergeFn, 
          int*,
          int*,
          int*,
          int*,
          int*>);

This should be relatively low effort to maintain

What do you think?

113

The type of input iterators I am testing has the reference type of non-const l-value reference to int. .e.g
The reference type of cpp20_input_iterator<int*> is int&. Originally I was passing by const & (which naturally is because we don't want to change the inputs), but that doesn't compile because the reference type doesn't match (const int& as oppose to int&)
Or do you have any other suggestion?

171

added suggested cases.
for empty range cases were already tested below. i didn't reuse the function because the function constructed the output array as std::array<int, N1+N2> and it would error if N1+N2 == 0;

211

renamed In1 -> InIter1
renamed In2 -> InIter2
I am not sure how to call these function.

For withAllIn1Iterators, given the type InIter2 and OutIter, it instantiates the tests for different types for InIter1
For withAllIn1In2Iterators, given the type OutIter, it calls withAllIn1Iterators with different types of InIter2, so effectively the cartesian product of InIter1 and InIter2.
For withAllIteratorPermutations, it instantiates withAllIn1In2Iterators for different types of OutIter, so effectively the cartesian product of (InIter1, InIter2, OutIter)

Any suggestions for these names?

256

In https://eel.is/c++draft/alg.merge#3

Effects: Copies all the elements of the two ranges [first1, last1) and [first2, last2) into the range [result, result_­last)

[result, result_­last) has to be a range. If in this case array is not large enough [result, result_­last) does not denote a range

343

right. I used it for a couple of more tests. e.g. testing when a comparator is a member function pointer or the projection is a member variable pointer. (to test it is calling std::invoke rather than calling operator().

This test is suggested by @philnik

423

This test is suggested by @philnik , this is to make sure we are calling std::invoke rather than opeartor() in the implementation as member pointers won't work with operator()

553

this checks that when both inputs are empty, we don't assign the output. Or did I miss anything?

The general testImpl works on array/std::array and this one cannot because array/std::array cannot be zero size. also the output has slightly different configuration. in the testImpl, the output array size is N1 + N2. but here N1 + N2 == 0 and we cannot have empty array.

what do you think?

[philnik]

libcxx/include/__algorithm/ranges_merge.h

95

In the other ranges algorithms the _impl function takes the iterators by value. Is there a reason you don't do this here?

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

38–39

Do you have any objections to using one concept per range argument? That would allow you to keep the definition of the concepts close to the tests for increased readability and remove a lot of noise. I don't care much for the name, except that it is consistent between algorithm tests.

113

Why not take it by value? We have to care about correctness and not performance in the tests.

553

You've got it the other way around. std::array<int, 0> is well-formed: https://eel.is/c++draft/array.zero. int a[0]; is a compiler-extension.

[huixie90]

libcxx/include/__algorithm/ranges_merge.h

95

It also puzzled me a lot why those algorithms have impl function by value.

My original revision doesn't have the impl function at all, the range overload delegate to iterator overload, and you pointed out that having an impl function could save extra "moves" of the comparator.
which makes sense so I did it.

But if you take the iterator by value, then you have to move these 5 iterators. Then I am confused by the purpose of the impl function, saving the 3 extra moves of the comparator+projection, at the cost of having extra 5 moves of iterators. (note that the default comparator/projections are stateless and cheaper than moving the iterators, which can be expensive, e.g. zip_iterator)

If we don't care about moves, why do we need this impl and not revert it to my original implementations?

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

38–39

I don't have objections. in my latest revision, I don't have any concepts defined, I just used std::invocable. I feel that it is more obvious the intent of the test. I am ok to create 2 extra concepts if std::invocable isn't as readable as a good name (any name suggestions?)

regarding the argument lists, i think the problem is the nature of this algorithm takes 5 iterators and it is very easy to get lost which iterator is what. Having default arguments of types in my opinion is fine only if we don't change the order of the arguments. but unfortunately the type we want the default are the 2nd and the 4th argument, which will result in changing the order.

I do understand having this table format will increase the formatting cost. so what do you think about the other alternatives I suggested?

113

I don't have strong feelings and happy to change it to either. by reference or by value sound the same as long as it is not const. any reasons to prefer one not the other?

[huixie90]

move empty test cases

[huixie90]

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

38–39

anyway, i think we should agree on the disagreement and move on. since you are the main reader of the test, I applied all your suggestions and hopefully it is the most readable form to you.

I followed the pattern in ranges move test, this line has a bug
https://github.com/llvm/llvm-project/blob/main/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move.pass.cpp#L33

If you have a test for move only input iterator, your test would fail because you are passing lvalue to ranges::move in the concept, but actually it is OK to call ranges::move with prvalue move only input iterators

[huixie90]

address feedback

[var-const]

At this point it looks good to me (I'll leave the final approval to the other reviewers). Once again, thanks a lot for working on this, and also for starting the discussion on different approaches to testing.

libcxx/include/__algorithm/ranges_merge.h

51

Question: can you give an example where decay_t makes an observable difference in this case?

75

Yes, I suspect it's the NamespaceIndentation: Inner setting.

95

Sorry, I got used to the pattern of passing by value and missed that it's actually forwarding references. I think that pattern was following the assumption that iterators are always cheap to copy, which might be somewhat outdated at this point (like the example you give with zip_iterator). Switching to references in impl functions seems like a good idea to me.

99

Nit: there are still a few unnecessary namespace qualifications -- e.g. here, std::weakly_incrementable and std::mergeable below, etc.

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

38–39

Some random thoughts: I feel like the best possible syntax for this would be named template arguments if those existed. Toying around with the idea, I came up with the following. I'm not sure if the complexity is worth it, but perhaps it might be useful to discuss.

The basic idea is to make it possible to define a list of valid arguments, then override just a single argument with an invalid type. There should be no need to write out each valid argument again, and it should be clear which argument is being overridden. The syntax would look like:

using ValidArguments = ArgumentList<int*, int*, int*, int*, int*>;
using BadIter = int;
using BadSentinel = int;

static_assert( is_invocable<ValidArguments>);
static_assert(!is_invocable<Override1st<BadIter,     ValidArguments>>);
static_assert(!is_invocable<Override2nd<BadSentinel, ValidArguments>>);
// In theory, this is even chainable:
static_assert(!is_invocable<Override1st<BadIter,     Override2nd<BadSentinel, ValidArguments>>>);

I'm not sure if it's worth the extra boilerplate, but it could use names instead of numbers for the arguments as well:

template <class T> using OverrideInIter1 = Override1st<T, ValidArguments>;
template <class T> using OverrideSent1 = Override2nd<T, ValidArguments>;
static_assert(!is_invocable<OverrideInIter1<BadIter>>);
static_assert(!is_invocable<OverrideSent1<BadSentinel>>);

It would require a bunch of boilerplate, though it would be shared across many tests, making it perhaps more palatable. Draft (can definitely be simplified):

template <class T1, class T2, class T3, class T4, class T5>
struct ArgumentList5 {
  using _1st = T1;
  using _2nd = T2;
  using _3rd = T3;
  using _4th = T4;
  using _5th = T5;
};
// Or:
template <class T1, class T2, class T3, class T4, class T5>
struct ArgumentList5 : ArgumentList4<T1, T2, T3, T4> {
  using _5th = T5;
};

template <class T, class Arguments>
struct Override1st : Arguments {
  using _1st = T;
};
template <class T, class Arguments>
struct Override2nd : Arguments {
  using _2nd = T;
};
// ...and so on for each argument...

template <class Func, class ArgList>
concept is_invocable2 = std::invocable<Func, typename ArgList::_1st, typename ArgList::_2nd>;
// ...
template <class Func, class ArgList>
concept is_invocable5 = std::invocable<Func, typename ArgList::_1st, typename ArgList::_2nd,
    typename ArgList::_3rd, typename ArgList::_4th, typename ArgList::_5th>;

// In the test file:
template <class ArgList>
concept is_invocable = is_invocable5<std::ranges::merge, ArgList>;

See toy example: https://wandbox.org/permlink/jveUh8rCiI7fExpi

To be clear, this is just for discussion, not to be addressed in the current patch.

113

I think passing by value is more readable in this case -- it makes it clear that the value can only change within this function's scope and never affects the caller, and it avoids giving the (misleading) impression that the caller expects to get an updated value from the function. The overhead from doing an extra copy is negligible given that it's a test and the value is pretty cheap to copy anyway.

171

std::array<T, 0> should be fine (if I'm understanding the issue correctly). Anyway, the new state looks good.

211

Thanks, it's clearer now with the renaming.

I don't have a great suggestion. A perhaps more readable, but even more verbose name could be something like withAllPermutationsOfInIter1 (which leads to withAllPermutationsOfInIter2 and withAllPermutationsOfInIter1AndInIter2). But feel free to keep as is, unless you happen to like this name (or it gives you an idea for a better name).

256

Just curious -- do you happen to have the quote handy that says that a range has to be a certain size to be considered a range?

[var-const]

libcxx/docs/Status/RangesAlgorithms.csv

63–67

Please add a link to this patch.

[huixie90]

addressing more issues

[huixie90]

libcxx/include/__algorithm/ranges_merge.h

51

since the they are passed by reference, _InIter2 can be references (the caller passed lvalue references) and we need to decay the result

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

38–39

Thanks for sending the example. Yeah I think this is the right direction we can explore for testing algorithms that take so many arguments, which hopefully can make those tests easier to read. (all the set algorithms and merge algorithm take (InputIterator1, Sentinel1, InputIterator2, Sentinel2, OutputIterator)

By slightly tweak your example and use the text book's Name Template Argument approach, chaining arguments can be made linear instead of nested
https://godbolt.org/z/761c7q61E

Barry has a different way of naming the arguments with designated initializers and wrap types with values
https://godbolt.org/z/Wvc4hPP4j

211

thanks I adopted the names you suggested

256

I think it is not the "size" that important. it is because result_last isn't reachable if the array isn't large enough I think
https://eel.is/c++draft/iterator.requirements.general#10

say out array is std::array<int ,3>
result is out.data().begin(), if result_­last is out.data().begin() + 5. calling a sequence of ++i cannot reach result_last because it is UB to ++ passed the end of the array.

let me know what do you think of this. I can ask around in sg9 to be sure

[philnik]

LGTM with my comments addressed.

libcxx/include/__algorithm/ranges_merge.h

51

Then shouldn't you use remove_reference_t?

99

I don't think we qualify the concepts anywhere else.

106

I don't think we qualify iterator_t anywhere else.

125

You don't forward in __merge_impl and you didn't move the parameters in the iterator overload. Why are you moving them here?

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

82

Why are you forwarding here? I doesn't look like you are making use of that. (Also the iterator version)

99

We normally avoid using declarations in the tests. For types I don't really care though.

103–108

Could you branch locally and rebase that branch on top of D129040 to ensure you don't have any bugs with contiguous iterators? You can download a patch with arc patch D129040.

208–222

Is this in any way different than ranges::owning_view with regards to borrowed-ness?

254–256

Why isn't this checked with forward_iterator, bidirectional_iterator etc.?

264

Is there a reason you don't use a bool and assert that it's not been copy-constructed? That makes the backtrace a lot nicer than using ranges::all_of, since it's crashing/failing to compile right at the source of the problem.

291

I think checking the return type here again is a bit redundant. You're already checking it in testImpl thoroughly. Removing the check makes the test a bit nicer to read.

[huixie90]

address issues in the review

[huixie90]

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

82

The forwarding is needed, otherwise the tests are not testing what you'd expect.
The tests are passing rvalue types, but here the variables are lvalues. Without forwarding ranges/iterators are passed by lvalue to the std::ranges::merge.

For example, if test is testing HasMergeIter<MoveOnlyInputIter>, it is actually OK to call the algorithm because the algorithm takes it by value. But without forwarding, this helper concept is checking if it is possible to "COPY" the lvalue and call the algorithm, which would fail,

99

I think this is suggested by var-const since the fully qualified name makes the tests less readable due to its long name (plus three template arguments), if I understand his comment correctly.

208–222

ranges::owning_view does not help here. It is a template and you need a concrete container to create a ranges::owning_view

With this helper struct , it is very easy to control the iterator type and sentinel type

254–256

Adding more types here make the CI fail because of the execution limits of the compile time execution. These tests are parameterized in three dimensions. The number of permutations grow in cubic. I can enable the runtime tests with those additional iterators with the guard of is_constant_time_evaluated() though

264

The test is testing the elements are copied exactly once. But only assert the test could still pass if it is copy-assigned zero times. Then we need to test all_of the bools are true, which is essentially the same code here?

[philnik]

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

254–256

You can avoid that by static_asserting in withAllPermutationsOfInIter1AndInIter2 for example. The execution step count is limited per static_assert.

264

You are already checking data, which guarantees that every element has been copied to. If every element is copied from at most once the logical consequence is that every element has been copied exactly once.

[huixie90]

remove unused typedef in the test

[huixie90]

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

103–108

applied D129040 and removed the workarounds in this test and verified that the tests are passing

254–256

This is good to know. Just to clarify, are you suggesting to add static_assert(true) so that

template <class OutIter>
constexpr void withAllPermutationsOfInIter1AndInIter2() {
  withAllPermutationsOfInIter1<cpp20_input_iterator<int*>, OutIter>();
  withAllPermutationsOfInIter1<forward_iterator<int*>, OutIter>();
  withAllPermutationsOfInIter1<bidirectional_iterator<int*>, OutIter>();
  withAllPermutationsOfInIter1<random_access_iterator<int*>, OutIter>();
  withAllPermutationsOfInIter1<contiguous_iterator<int*>, OutIter>();
  static_assert(true); // workaround of constant execution step count
}

264

I will consider it in the next patch when I refactored this class into a common place to be reused in the set* tests. To confirm, I think we need to assert in both copy constructor and copy assignment operator. To be honest, I still prefer to an explicit line in the test to say "all of the elements are copied exactly once"

what about adding a member function

bool copiedOnce() const { return copy_assign == 1;}

assert(std::ranges::all_of(out, &TracedCopy::copiedOnce));

or if you use the bool approach

bool copiedOnce() const { return copied;}

then
assert(std::ranges::all_of(out, &TracedCopy::copiedOnce));

[philnik]

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

254–256

No, unfortunately you have to do:

template <class OutIter>
void withAllPermutationsOfInIter1AndInIter2() {
  withAllPermutationsOfInIter1<cpp20_input_iterator<int*>, OutIter>();
  withAllPermutationsOfInIter1<forward_iterator<int*>, OutIter>();
  withAllPermutationsOfInIter1<bidirectional_iterator<int*>, OutIter>();
  withAllPermutationsOfInIter1<random_access_iterator<int*>, OutIter>();
  withAllPermutationsOfInIter1<contiguous_iterator<int*>, OutIter>();

  static_assert(withAllPermutationsOfInIter1<cpp20_input_iterator<int*>, OutIter>());
  static_assert(withAllPermutationsOfInIter1<forward_iterator<int*>, OutIter>());
  static_assert(withAllPermutationsOfInIter1<bidirectional_iterator<int*>, OutIter>());
  static_assert(withAllPermutationsOfInIter1<random_access_iterator<int*>, OutIter>());
  static_assert(withAllPermutationsOfInIter1<contiguous_iterator<int*>, OutIter>());
}

264

We can decide that later. It would probably be a good idea to put a few of these things in support. For example CopyOnce is used in quite a few tests and all of them have their own (differing) versions.

[huixie90]

split permutation tests into several functions to work around constexpr step limit

[var-const]

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

99

I was suggesting a type alias (using Foo = Bar;), but FWIW, a using declaration is fine by me.

[ldionne]

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

55–73

In my opinion, this provides the most readability. It makes what we're testing really obvious and avoids the need for more sophisticated tools that would not provide as much clarity as this. The long lines are kind of annoying, but we could use shorter aliases to alleviate that.

[huixie90]

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp

55–73

I think I also like this format.
Could you please take a look at this revision
https://reviews.llvm.org/D128611?vs=440098&id=440284#toc
which is pretty much this format

I dropped it because in the review there were concerns that the cost to maintain this format might outweigh the benefits

libcxx/docs/Status/RangesAlgorithms.csv

 Write,replace_copy_if,Nikolas Klauser,n/a,Not started
 Write,swap_ranges,Nikolas Klauser,`D116303 <https://llvm.org/D116303>`_,✅
 Write,reverse_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,Under review
 Write,rotate_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,Under review
 Write,sample,Not assigned,n/a,Not started
 Write,unique_copy,Not assigned,n/a,Not started
 Write,partition_copy,Not assigned,n/a,Not started
 Write,partial_sort_copy,Not assigned,n/a,Not started
-Merge,merge,Not assigned,n/a,Not started
-Merge,set_difference,Not assigned,n/a,Not started
-Merge,set_intersection,Not assigned,n/a,Not started
-Merge,set_symmetric_difference,Not assigned,n/a,Not started
-Merge,set_union,Not assigned,n/a,Not started
+Merge,merge,Hui Xie,`D128611 <https://llvm.org/D128611>`_,✅
+Merge,set_difference,Hui Xie,n/a,Not started
+Merge,set_intersection,Hui Xie,n/a,Not started
+Merge,set_symmetric_difference,Hui Xie,n/a,Not started
+Merge,set_union,Not assigned,Hui Xie,Not started
 Permutation,remove,Not assigned,n/a,Not started
 Permutation,remove_if,Not assigned,n/a,Not started
 Permutation,reverse,Nikolas Klauser,`D125752 <https://llvm.org/D125752>`_,✅
 Permutation,rotate,Nikolas Klauser,`D124122 <https://llvm.org/D124122>`_,Under review
 Permutation,shuffle,Not assigned,n/a,Not started
 Permutation,unique,Not assigned,n/a,Not started
 Permutation,partition,Not assigned,n/a,Not started
 Permutation,stable_partition,Not assigned,n/a,Not started

libcxx/include/CMakeLists.txt

set(files
   __algorithm/ranges_for_each_n.h
   __algorithm/ranges_is_partitioned.h
   __algorithm/ranges_is_sorted.h
   __algorithm/ranges_is_sorted_until.h
   __algorithm/ranges_lexicographical_compare.h
   __algorithm/ranges_lower_bound.h
   __algorithm/ranges_max.h
   __algorithm/ranges_max_element.h
+  __algorithm/ranges_merge.h
   __algorithm/ranges_min.h
   __algorithm/ranges_min_element.h
   __algorithm/ranges_minmax.h
   __algorithm/ranges_minmax_element.h
   __algorithm/ranges_mismatch.h
   __algorithm/ranges_move.h
   __algorithm/ranges_move_backward.h
   __algorithm/ranges_none_of.h

libcxx/include/__algorithm/ranges_merge.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_RANGES_MERGE_H
+#define _LIBCPP___ALGORITHM_RANGES_MERGE_H
+
+#include <__algorithm/in_in_out_result.h>
+#include <__algorithm/ranges_copy.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/mergeable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/move.h>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+
+template <class _InIter1, class _InIter2, class _OutIter>
+using merge_result = in_in_out_result<_InIter1, _InIter2, _OutIter>;
+
+namespace __merge {
+
+template <
+    class _InIter1,
+    class _Sent1,
+    class _InIter2,
+    class _Sent2,
+    class _OutIter,
+    class _Comp,
+    class _Proj1,
+    class _Proj2>
+_LIBCPP_HIDE_FROM_ABI constexpr merge_result<__uncvref_t<_InIter1>, __uncvref_t<_InIter2>, __uncvref_t<_OutIter>>
+__merge_impl(
+    _InIter1&& __first1,
+    _Sent1&& __last1,
+    _InIter2&& __first2,
+    _Sent2&& __last2,
+    _OutIter&& __result,
+    _Comp&& __comp,
+    _Proj1&& __proj1,
+    _Proj2&& __proj2) {
+  for (; __first1 != __last1 && __first2 != __last2; ++__result) {
+    if (std::invoke(__comp, std::invoke(__proj2, *__first2), std::invoke(__proj1, *__first1))) {
+      *__result = *__first2;
+      ++__first2;
+    } else {
+      *__result = *__first1;
+      ++__first1;
+    }
+  }
+  auto __ret1 = ranges::copy(std::move(__first1), std::move(__last1), std::move(__result));
+  auto __ret2 = ranges::copy(std::move(__first2), std::move(__last2), std::move(__ret1.out));
+  return {std::move(__ret1.in), std::move(__ret2.in), std::move(__ret2.out)};
+}
+
+struct __fn {
+  template <
+      input_iterator _InIter1,
+      sentinel_for<_InIter1> _Sent1,
+      input_iterator _InIter2,
+      sentinel_for<_InIter2> _Sent2,
+      weakly_incrementable _OutIter,
+      class _Comp  = less,
+      class _Proj1 = identity,
+      class _Proj2 = identity>
+    requires mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2>
+  _LIBCPP_HIDE_FROM_ABI constexpr merge_result<_InIter1, _InIter2, _OutIter> operator()(
+      _InIter1 __first1,
+      _Sent1 __last1,
+      _InIter2 __first2,
+      _Sent2 __last2,
+      _OutIter __result,
+      _Comp __comp   = {},
+      _Proj1 __proj1 = {},
+      _Proj2 __proj2 = {}) const {
+    return __merge::__merge_impl(__first1, __last1, __first2, __last2, __result, __comp, __proj1, __proj2);
+  }
+
+  template <
+      input_range _Range1,
+      input_range _Range2,
+      weakly_incrementable _OutIter,
+      class _Comp  = less,
+      class _Proj1 = identity,
+      class _Proj2 = identity>
+    requires mergeable<
+        iterator_t<_Range1>,
+        iterator_t<_Range2>,
+        _OutIter,
+        _Comp,
+        _Proj1,
+        _Proj2> 
+  _LIBCPP_HIDE_FROM_ABI constexpr merge_result<borrowed_iterator_t<_Range1>, borrowed_iterator_t<_Range2>, _OutIter>
+        operator()(
+            _Range1&& __range1,
+            _Range2&& __range2,
+            _OutIter __result,
+            _Comp __comp   = {},
+            _Proj1 __proj1 = {},
+            _Proj2 __proj2 = {}) const {
+    return __merge::__merge_impl(
+        ranges::begin(__range1),
+        ranges::end(__range1),
+        ranges::begin(__range2),
+        ranges::end(__range2),
+        __result,
+        __comp,
+        __proj1,
+        __proj2);
+  }
+};
+
+} // namespace __merge
+
+inline namespace __cpo {
+  inline constexpr auto merge = __merge::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_MERGE_H

libcxx/include/algorithm

template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
     constexpr ranges::move_result<I, O>
       ranges::move(I first, S last, O result);                                                      // since C++20
 
   template<input_range R, weakly_incrementable O>
     requires indirectly_movable<iterator_t<R>, O>
     constexpr ranges::move_result<borrowed_iterator_t<R>, O>
       ranges::move(R&& r, O result);                                                                // since C++20
 
+  template<class I1, class I2, class O>
+    using merge_result = in_in_out_result<I1, I2, O>;                                               // since C++20
+
+  template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
+           weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity,
+           class Proj2 = identity>
+    requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+    constexpr merge_result<I1, I2, O>
+      merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
+            Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                                    // since C++20
+
+  template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ranges::less,
+           class Proj1 = identity, class Proj2 = identity>
+    requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+    constexpr merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
+      merge(R1&& r1, R2&& r2, O result,
+            Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                                    // since C++20
 
 }
 
     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

 #include <__algorithm/ranges_for_each_n.h>
 #include <__algorithm/ranges_is_partitioned.h>
 #include <__algorithm/ranges_is_sorted.h>
 #include <__algorithm/ranges_is_sorted_until.h>
 #include <__algorithm/ranges_lexicographical_compare.h>
 #include <__algorithm/ranges_lower_bound.h>
 #include <__algorithm/ranges_max.h>
 #include <__algorithm/ranges_max_element.h>
+#include <__algorithm/ranges_merge.h>
 #include <__algorithm/ranges_min.h>
 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_minmax.h>
 #include <__algorithm/ranges_minmax_element.h>
 #include <__algorithm/ranges_mismatch.h>
 #include <__algorithm/ranges_move.h>
 #include <__algorithm/ranges_move_backward.h>
 #include <__algorithm/ranges_none_of.h>

libcxx/include/module.modulemap.in

module __algorithm {
       module ranges_for_each_n               { private header "__algorithm/ranges_for_each_n.h" }
       module ranges_is_partitioned           { private header "__algorithm/ranges_is_partitioned.h" }
       module ranges_is_sorted                { private header "__algorithm/ranges_is_sorted.h" }
       module ranges_is_sorted_until          { private header "__algorithm/ranges_is_sorted_until.h" }
       module ranges_lexicographical_compare  { private header "__algorithm/ranges_lexicographical_compare.h" }
       module ranges_lower_bound              { private header "__algorithm/ranges_lower_bound.h" }
       module ranges_max                      { private header "__algorithm/ranges_max.h" }
       module ranges_max_element              { private header "__algorithm/ranges_max_element.h" }
+      module ranges_merge                    { private header "__algorithm/ranges_merge.h" }
       module ranges_min                      { private header "__algorithm/ranges_min.h" }
       module ranges_min_element              { private header "__algorithm/ranges_min_element.h" }
       module ranges_minmax                   { private header "__algorithm/ranges_minmax.h" }
       module ranges_minmax_element           { private header "__algorithm/ranges_minmax_element.h" }
       module ranges_mismatch                 { private header "__algorithm/ranges_mismatch.h" }
       module ranges_move                     { private header "__algorithm/ranges_move.h" }
       module ranges_move_backward            { private header "__algorithm/ranges_move_backward.h" }
       module ranges_none_of                  { private header "__algorithm/ranges_none_of.h" }

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

struct BinaryTransform {
     constexpr BinaryTransform& operator=(const BinaryTransform&) = default;
     constexpr std::nullptr_t operator()(void*, void*) const { return nullptr; }
 };
 
 constexpr bool all_the_algorithms()
 {
     void *a[10] = {};
     void *b[10] = {};
-    //void *half[5] = {};
+    void *half[5] = {};
     void **first = a;
     void **mid = a+5;
     void **last = a+10;
     void **first2 = b;
     //void **mid2 = b+5;
     void **last2 = b+10;
     void *value = nullptr;
     int count = 1;
#endif
     (void)std::ranges::lower_bound(a, value, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::make_heap(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::make_heap(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::max(value, value, Less(&copies)); assert(copies == 0);
     (void)std::ranges::max({ value, value }, Less(&copies)); assert(copies == 0);
     (void)std::ranges::max(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::max_element(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::max_element(a, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::merge(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::merge(half, half, b, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::merge(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::merge(half, half, b, Less(&copies)); assert(copies == 0);
     (void)std::ranges::min(value, value, Less(&copies)); assert(copies == 0);
     (void)std::ranges::min({ value, value }, Less(&copies)); assert(copies == 0);
     (void)std::ranges::min(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::min_element(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::min_element(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::minmax(value, value, Less(&copies)); assert(copies == 0);
     (void)std::ranges::minmax({ value, value }, Less(&copies)); assert(copies == 0);
     (void)std::ranges::minmax(a, Less(&copies)); assert(copies == 0);

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp

 struct BinaryTransform {
     constexpr T operator()(void*, void*) const { return T(); }
 };
 
 constexpr bool all_the_algorithms()
 {
     T a[10] = {};
     T b[10] = {};
-    //T half[5] = {};
+    T half[5] = {};
     T *first = a;
     T *mid = a+5;
     T *last = a+10;
     T *first2 = b;
     //T *mid2 = b+5;
     T *last2 = b+10;
     void *value = nullptr;
     int count = 1;
#endif
     //(void)std::ranges::lower_bound(a, value, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::make_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::make_heap(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::max(T(), T(), Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::max({ T(), T() }, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::max(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::max_element(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::max_element(a, Less(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::merge(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::merge(half, half, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::merge(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::merge(half, half, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::min(T(), T(), Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::min({ T(), T() }, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::min(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::min_element(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::min_element(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::minmax(T(), T(), Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::minmax({ T(), T() }, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::minmax(a, Less(), Proj(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/ranges_for_each_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each_n.h'}}
 #include <__algorithm/ranges_is_partitioned.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_partitioned.h'}}
 #include <__algorithm/ranges_is_sorted.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_sorted.h'}}
 #include <__algorithm/ranges_is_sorted_until.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_sorted_until.h'}}
 #include <__algorithm/ranges_lexicographical_compare.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_lexicographical_compare.h'}}
 #include <__algorithm/ranges_lower_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_lower_bound.h'}}
 #include <__algorithm/ranges_max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max.h'}}
 #include <__algorithm/ranges_max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max_element.h'}}
+#include <__algorithm/ranges_merge.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_merge.h'}}
 #include <__algorithm/ranges_min.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min.h'}}
 #include <__algorithm/ranges_min_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min_element.h'}}
 #include <__algorithm/ranges_minmax.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax.h'}}
 #include <__algorithm/ranges_minmax_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax_element.h'}}
 #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}}
 #include <__algorithm/ranges_move.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move.h'}}
 #include <__algorithm/ranges_move_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move_backward.h'}}
 #include <__algorithm/ranges_none_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_none_of.h'}}

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<input_­iterator I1, sentinel_­for<I1> S1, input_­iterator I2, sentinel_­for<I2> S2,
+//          weakly_­incrementable O, class Comp = ranges::less, class Proj1 = identity,
+//          class Proj2 = identity>
+//   requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+//   constexpr merge_result<I1, I2, O>
+//     merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
+//           Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                                    // since C++20
+//
+// template<input_­range R1, input_­range R2, weakly_­incrementable O, class Comp = ranges::less,
+//          class Proj1 = identity, class Proj2 = identity>
+//   requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+//   constexpr merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
+//     merge(R1&& r1, R2&& r2, O result,
+//           Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                                    // since C++20
+
+#include <algorithm>
+#include <array>
+#include <concepts>
+
+#include "almost_satisfies_types.h"
+#include "MoveOnly.h"
+#include "test_iterators.h"
+
+// Test iterator overload's constraints:
+// =====================================
+template <
+    class InIter1,
+    class InIter2,
+    class OutIter,
+    class Sent1 = sentinel_wrapper<InIter1>,
+    class Sent2 = sentinel_wrapper<InIter2>>
+concept HasMergeIter =
+    requires(InIter1&& inIter1, InIter2&& inIter2, OutIter&& outIter, Sent1&& sent1, Sent2&& sent2) {
+      std::ranges::merge(
+          std::forward<InIter1>(inIter1),
+          std::forward<Sent1>(sent1),
+          std::forward<InIter2>(inIter2),
+          std::forward<Sent2>(sent2),
+          std::forward<OutIter>(outIter));
+    };
+
+static_assert(HasMergeIter<int*, int*, int*, int*, int*>);
+
+// !std::input_iterator<I1>
+static_assert(!HasMergeIter<InputIteratorNotDerivedFrom, int*, int*>);
+
+// !std::sentinel_for<S1, I1>
+static_assert(!HasMergeIter<int*, int*, int*, SentinelForNotSemiregular>);
+
+// !std::input_iterator<I2>
+static_assert(!HasMergeIter<int*, InputIteratorNotDerivedFrom, int*>);
+
+// !std::sentinel_for<S2, I2>
+static_assert(!HasMergeIter<int*, int*, int*, int*, SentinelForNotSemiregular>);
+
+// !std::weakly_incrementable<O>
+static_assert(!HasMergeIter<int*, int*, WeaklyIncrementableNotMovable>);
+
+// !std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
+static_assert(!HasMergeIter<MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly*>);
+
+// Test range overload's constraints:
+// =====================================
+
+template <class Range1, class Range2, class OutIter>
+concept HasMergeRange =
+    requires(Range1&& range1, Range2&& range2, OutIter&& outIter) {
+      std::ranges::merge(std::forward<Range1>(range1), std::forward<Range2>(range2), std::forward<OutIter>(outIter));
+    };
+
+static_assert(HasMergeRange<UncheckedRange<int*>, UncheckedRange<int*>, int* >);
+
+// !std::input_range<R2>
+static_assert(!HasMergeRange<UncheckedRange<InputIteratorNotDerivedFrom>, UncheckedRange<int*>, int*>);
+
+// !std::input_range<R2>
+static_assert(!HasMergeRange<UncheckedRange<int*>, UncheckedRange<InputIteratorNotDerivedFrom>, int*>);
+
+// !std::weakly_incrementable<O>
+static_assert(!HasMergeRange<UncheckedRange<int*>, UncheckedRange<int*>, WeaklyIncrementableNotMovable >);
+
+// !mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+static_assert(!HasMergeRange< UncheckedRange<MoveOnly*>, UncheckedRange<MoveOnly*>, MoveOnly*>);
+
+using std::ranges::merge_result;
+
+template <class In1, class In2, class Out, std::size_t N1, std::size_t N2>
+constexpr void testMergeImpl(std::array<int, N1> in1, std::array<int, N2> in2, const auto& expected) {
+  // TODO: std::ranges::merge calls std::ranges::copy
+  // std::ranges::copy(contiguous_iterator<int*>, sentinel_wrapper<contiguous_iterator<int*>>, contiguous_iterator<int*>) doesn't seem to work.
+  // It seems that std::ranges::copy calls std::copy, which unwraps contiguous_iterator<int*> into int*,
+  // and then it failed because there is no == between int* and sentinel_wrapper<contiguous_iterator<int*>>
+  using Sent1 = std::conditional_t<std::contiguous_iterator<In1>, In1, sentinel_wrapper<In1>>;
+  using Sent2 = std::conditional_t<std::contiguous_iterator<In2>, In2, sentinel_wrapper<In2>>;
+
+  // iterator overload
+  {
+    std::array<int, N1 + N2> out;
+    std::same_as<merge_result<In1, In2, Out>> decltype(auto) result = std::ranges::merge(
+        In1{in1.data()},
+        Sent1{In1{in1.data() + in1.size()}},
+        In2{in2.data()},
+        Sent2{In2{in2.data() + in2.size()}},
+        Out{out.data()});
+    assert(std::ranges::equal(out, expected));
+
+    assert(base(result.in1) == in1.data() + in1.size());
+    assert(base(result.in2) == in2.data() + in2.size());
+    assert(base(result.out) == out.data() + out.size());
+  }
+
+  // range overload
+  {
+    std::array<int, N1 + N2> out;
+    std::ranges::subrange r1{In1{in1.data()}, Sent1{In1{in1.data() + in1.size()}}};
+    std::ranges::subrange r2{In2{in2.data()}, Sent2{In2{in2.data() + in2.size()}}};
+    std::same_as<merge_result<In1, In2, Out>> decltype(auto) result = std::ranges::merge(r1, r2, Out{out.data()});
+    assert(std::ranges::equal(out, expected));
+
+    assert(base(result.in1) == in1.data() + in1.size());
+    assert(base(result.in2) == in2.data() + in2.size());
+    assert(base(result.out) == out.data() + out.size());
+  }
+}
+
+template <class In1, class In2, class Out>
+constexpr void testImpl() {
+  // range 1 shorter than range2
+  {
+    std::array in1{0, 1, 5, 6, 9, 10};
+    std::array in2{3, 6, 7, 9, 13, 15, 100};
+    std::array expected{0, 1, 3, 5, 6, 6, 7, 9, 9, 10, 13, 15, 100};
+    testMergeImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 2 shorter than range 1
+  {
+    std::array in1{2, 6, 8, 12};
+    std::array in2{0, 1, 2};
+    std::array expected{0, 1, 2, 2, 6, 8, 12};
+    testMergeImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 1 == range 2
+  {
+    std::array in1{0, 1, 2};
+    std::array in2{0, 1, 2};
+    std::array expected{0, 0, 1, 1, 2, 2};
+    testMergeImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // All elements in range 1 are greater than every element in range 2
+  {
+    std::array in1{8, 8, 10, 12};
+    std::array in2{0, 0, 1};
+    std::array expected{0, 0, 1, 8, 8, 10, 12};
+    testMergeImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // All elements in range 2 are greater than every element in range 1
+  {
+    std::array in1{0, 1, 1};
+    std::array in2{7, 7};
+    std::array expected{0, 1, 1, 7, 7};
+    testMergeImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 1 is empty
+  {
+    std::array<int, 0> in1{};
+    std::array in2{3, 4, 5};
+    std::array expected{3, 4, 5};
+    testMergeImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 2 is empty
+  {
+    std::array in1{3, 4, 5};
+    std::array<int, 0> in2{};
+    std::array expected{3, 4, 5};
+    testMergeImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // both ranges are empty
+  {
+    std::array<int, 0> in1{};
+    std::array<int, 0> in2{};
+    std::array<int, 0> expected{};
+    testMergeImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // check that ranges::dangling is returned for non-borrowed_range and iterator_t is returned for borrowed_range
+  {
+    struct NonBorrowedRange {
+      int* data_;
+      size_t size_;
+
+      // TODO: std::ranges::merge calls std::ranges::copy
+      // std::ranges::copy(contiguous_iterator<int*>, sentinel_wrapper<contiguous_iterator<int*>>, contiguous_iterator<int*>) doesn't seem to work.
+      // It seems that std::ranges::copy calls std::copy, which unwraps contiguous_iterator<int*> into int*,
+      // and then it failed because there is no == between int* and sentinel_wrapper<contiguous_iterator<int*>>
+      using Sent = std::conditional_t<std::contiguous_iterator<In2>, In2, sentinel_wrapper<In2>>;
+
+      constexpr NonBorrowedRange(int* d, size_t s) : data_{d}, size_{s} {}
+
+      constexpr In2 begin() const { return In2{data_}; };
+      constexpr Sent end() const { return Sent{In2{data_ + size_}}; };
+    };
+
+    std::array r1{3, 6, 7, 9};
+    std::array r2{2, 3, 4};
+    std::array<int, 7> out;
+    std::same_as<merge_result<std::array<int, 4>::iterator, std::ranges::dangling, int*>> decltype(auto) result =
+        std::ranges::merge(r1, NonBorrowedRange{r2.data(), r2.size()}, out.data());
+    assert(base(result.in1) == r1.end());
+    assert(base(result.out) == out.data() + out.size());
+    assert(std::ranges::equal(out, std::array{2, 3, 3, 4, 6, 7, 9}));
+  }
+}
+
+template <class InIter2, class OutIter>
+constexpr void withAllPermutationsOfInIter1() {
+  testImpl<cpp20_input_iterator<int*>, InIter2, OutIter>();
+  testImpl<forward_iterator<int*>, InIter2, OutIter>();
+  testImpl<bidirectional_iterator<int*>, InIter2, OutIter>();
+  testImpl<random_access_iterator<int*>, InIter2, OutIter>();
+  testImpl<contiguous_iterator<int*>, InIter2, OutIter>();
+}
+
+template <class OutIter>
+constexpr bool withAllPermutationsOfInIter1AndInIter2() {
+  withAllPermutationsOfInIter1<cpp20_input_iterator<int*>, OutIter>();
+  withAllPermutationsOfInIter1<forward_iterator<int*>, OutIter>();
+  withAllPermutationsOfInIter1<bidirectional_iterator<int*>, OutIter>();
+  withAllPermutationsOfInIter1<random_access_iterator<int*>, OutIter>();
+  withAllPermutationsOfInIter1<contiguous_iterator<int*>, OutIter>();
+  return true;
+}
+
+constexpr void runAllIteratorPermutationsTests() {
+  withAllPermutationsOfInIter1AndInIter2<cpp17_output_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<cpp20_output_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<forward_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<bidirectional_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<random_access_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<contiguous_iterator<int*>>();
+
+  static_assert(withAllPermutationsOfInIter1AndInIter2<cpp17_output_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<cpp20_output_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<forward_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<bidirectional_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<random_access_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<contiguous_iterator<int*>>());
+}
+
+constexpr bool test() {
+  // check that every element is copied exactly once
+  struct TracedCopy {
+    int copy_assign = 0;
+    int data        = 0;
+
+    constexpr TracedCopy() = default;
+    constexpr TracedCopy(int i) : data(i) {}
+    constexpr TracedCopy(const TracedCopy& other) : copy_assign(other.copy_assign), data(other.data) {}
+
+    constexpr TracedCopy(TracedCopy&& other)            = delete;
+    constexpr TracedCopy& operator=(TracedCopy&& other) = delete;
+
+    constexpr TracedCopy& operator=(const TracedCopy& other) {
+      copy_assign = other.copy_assign + 1;
+      data        = other.data;
+      return *this;
+    }
+
+    constexpr bool operator==(const TracedCopy& o) const { return data == o.data; }
+    constexpr auto operator<=>(const TracedCopy& o) const { return data <=> o.data; }
+  };
+  {
+    std::array<TracedCopy, 3> r1{3, 5, 8};
+    std::array<TracedCopy, 3> r2{1, 3, 8};
+
+    // iterator overload
+    {
+      std::array<TracedCopy, 6> out;
+      auto result = std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+      assert(std::ranges::equal(out, std::array<TracedCopy, 6>{1, 3, 3, 5, 8, 8}));
+
+      assert(std::ranges::all_of(out, [](const TracedCopy& e) { return e.copy_assign == 1; }));
+    }
+
+    // range overload
+    {
+      std::array<TracedCopy, 6> out;
+      auto result = std::ranges::merge(r1, r2, out.data());
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+      assert(std::ranges::equal(out, std::array<TracedCopy, 6>{1, 3, 3, 5, 8, 8}));
+
+      assert(std::ranges::all_of(out, [](const TracedCopy& e) { return e.copy_assign == 1; }));
+    }
+  }
+
+  struct IntAndID {
+    int data;
+    int id;
+
+    constexpr auto operator==(const IntAndID& o) const { return data == o.data; }
+    constexpr auto operator<=>(const IntAndID& o) const { return data <=> o.data; }
+  };
+
+  // Algorithm is stable: equal elements should be merged in the original order
+  {
+    std::array<IntAndID, 3> r1{{{0, 0}, {0, 1}, {0, 2}}};
+    std::array<IntAndID, 3> r2{{{1, 0}, {1, 1}, {1, 2}}};
+
+    // iterator overload
+    {
+      std::array<IntAndID, 6> out;
+      std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
+
+      assert(std::ranges::equal(out, std::array{0, 0, 0, 1, 1, 1}, {}, &IntAndID::data));
+      // ID should be in their original order
+      assert(std::ranges::equal(out, std::array{0, 1, 2, 0, 1, 2}, {}, &IntAndID::id));
+    }
+
+    // range overload
+    {
+      std::array<IntAndID, 6> out;
+      std::ranges::merge(r1, r2, out.data());
+
+      assert(std::ranges::equal(out, std::array{0, 0, 0, 1, 1, 1}, {}, &IntAndID::data));
+      // ID should be in their original order
+      assert(std::ranges::equal(out, std::array{0, 1, 2, 0, 1, 2}, {}, &IntAndID::id));
+    }
+  }
+
+  // Equal elements in R1 should be merged before equal elements in R2
+  {
+    std::array<IntAndID, 3> r1{{{0, 1}, {1, 1}, {2, 1}}};
+    std::array<IntAndID, 3> r2{{{0, 2}, {1, 2}, {2, 2}}};
+
+    // iterator overload
+    {
+      std::array<IntAndID, 6> out;
+      std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
+
+      assert(std::ranges::equal(out, std::array{0, 0, 1, 1, 2, 2}, {}, &IntAndID::data));
+      // ID 1 (from R1) should be in front of ID 2 (from R2)
+      assert(std::ranges::equal(out, std::array{1, 2, 1, 2, 1, 2}, {}, &IntAndID::id));
+    }
+
+    // range overload
+    {
+      std::array<IntAndID, 6> out;
+      std::ranges::merge(r1, r2, out.data());
+
+      assert(std::ranges::equal(out, std::array{0, 0, 1, 1, 2, 2}, {}, &IntAndID::data));
+      // ID 1 (from R1) should be in front of ID 2 (from R2)
+      assert(std::ranges::equal(out, std::array{1, 2, 1, 2, 1, 2}, {}, &IntAndID::id));
+    }
+  }
+
+  struct Data {
+    int data;
+
+    constexpr bool smallerThan(const Data& o) const { return data < o.data; }
+  };
+
+  // Test custom comparator
+  {
+    std::array r1{Data{4}, Data{8}, Data{12}};
+    std::array r2{Data{5}, Data{9}};
+    using Iter1 = std::array<Data, 3>::iterator;
+    using Iter2 = std::array<Data, 2>::iterator;
+
+    // iterator overload
+    {
+      std::array<Data, 5> out;
+      std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
+          std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), [](const Data& x, const Data& y) {
+            return x.data < y.data;
+          });
+
+      assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+
+    // range overload
+    {
+      std::array<Data, 5> out;
+      std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
+          std::ranges::merge(r1, r2, out.data(), [](const Data& x, const Data& y) { return x.data < y.data; });
+
+      assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+
+    // member pointer Comparator iterator overload
+    {
+      std::array<Data, 5> out;
+      std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
+          std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), &Data::smallerThan);
+
+      assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+
+    // member pointer Comparator range overload
+    {
+      std::array<Data, 5> out;
+      std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
+          std::ranges::merge(r1, r2, out.data(), &Data::smallerThan);
+
+      assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+  }
+
+  // Test Projection
+  {
+    std::array r1{Data{4}, Data{8}, Data{12}};
+    std::array r2{Data{5}, Data{9}};
+    using Iter1 = std::array<Data, 3>::iterator;
+    using Iter2 = std::array<Data, 2>::iterator;
+
+    const auto proj = [](const Data& d) { return d.data; };
+
+    // iterator overload
+    {
+      std::array<Data, 5> out;
+      std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
+          std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), std::ranges::less{}, proj, proj);
+
+      assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+
+    // range overload
+    {
+      std::array<Data, 5> out;
+      std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
+          std::ranges::merge(r1, r2, out.data(), std::ranges::less{}, proj, proj);
+
+      assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+
+    // member pointer Projection iterator overload
+    {
+      std::array<Data, 5> out;
+      std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
+          std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), {}, &Data::data, &Data::data);
+
+      assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+
+    // member pointer Projection range overload
+    {
+      std::array<Data, 5> out;
+      std::same_as<merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
+          std::ranges::merge(r1, r2, out.data(), std::ranges::less{}, &Data::data, &Data::data);
+
+      assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+  }
+
+  // Complexity: at most N - 1 comparisons and applications of each projection.
+  {
+    Data r1[] = {{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}};
+    Data r2[] = {{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}};
+    std::array expected{0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9};
+
+    // iterator overload
+    {
+      std::array<Data, 20> out;
+      std::size_t numberOfComp  = 0;
+      std::size_t numberOfProj1 = 0;
+      std::size_t numberOfProj2 = 0;
+
+      const auto comp = [&numberOfComp](int x, int y) {
+        ++numberOfComp;
+        return x < y;
+      };
+
+      const auto proj1 = [&numberOfProj1](const Data& d) {
+        ++numberOfProj1;
+        return d.data;
+      };
+
+      const auto proj2 = [&numberOfProj2](const Data& d) {
+        ++numberOfProj2;
+        return d.data;
+      };
+
+      std::ranges::merge(r1, r1 + 10, r2, r2 + 10, out.data(), comp, proj1, proj2);
+      assert(std::ranges::equal(out, expected, {}, &Data::data));
+      assert(numberOfComp < out.size());
+      assert(numberOfProj1 < out.size());
+      assert(numberOfProj2 < out.size());
+    }
+
+    // range overload
+    {
+      std::array<Data, 20> out;
+      std::size_t numberOfComp  = 0;
+      std::size_t numberOfProj1 = 0;
+      std::size_t numberOfProj2 = 0;
+
+      const auto comp = [&numberOfComp](int x, int y) {
+        ++numberOfComp;
+        return x < y;
+      };
+
+      const auto proj1 = [&numberOfProj1](const Data& d) {
+        ++numberOfProj1;
+        return d.data;
+      };
+
+      const auto proj2 = [&numberOfProj2](const Data& d) {
+        ++numberOfProj2;
+        return d.data;
+      };
+
+      std::ranges::merge(r1, r2, out.data(), comp, proj1, proj2);
+      assert(std::ranges::equal(out, expected, {}, &Data::data));
+      assert(numberOfComp < out.size());
+      assert(numberOfProj1 < out.size());
+      assert(numberOfProj2 < out.size());
+    }
+  }
+
+  // Comparator convertible to bool
+  {
+    struct ConvertibleToBool {
+      bool b;
+      constexpr operator bool() const { return b; }
+    };
+    Data r1[] = {{2}, {4}};
+    Data r2[] = {{3}, {4}, {5}};
+
+    const auto comp = [](const Data& x, const Data& y) { return ConvertibleToBool{x.data < y.data}; };
+
+    // iterator overload
+    {
+      std::array<Data, 5> out;
+      std::ranges::merge(r1, r1 + 2, r2, r2 + 3, out.data(), comp);
+      assert(std::ranges::equal(out, std::array{2, 3, 4, 4, 5}, {}, &Data::data));
+    }
+
+    // range overload
+    {
+      std::array<Data, 5> out;
+      std::ranges::merge(r1, r2, out.data(), comp);
+      assert(std::ranges::equal(out, std::array{2, 3, 4, 4, 5}, {}, &Data::data));
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  runAllIteratorPermutationsTests();
+
+  return 0;
+}

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 //static_assert(test(std::ranges::is_permutation, a, a));
 static_assert(test(std::ranges::is_sorted, a));
 static_assert(test(std::ranges::is_sorted_until, a));
 static_assert(test(std::ranges::lexicographical_compare, a, a));
 static_assert(test(std::ranges::lower_bound, a, 42));
 //static_assert(test(std::ranges::make_heap, a));
 static_assert(test(std::ranges::max, a));
 static_assert(test(std::ranges::max_element, a));
-//static_assert(test(std::ranges::merge, a, a, a));
+static_assert(test(std::ranges::merge, a, a, a));
 static_assert(test(std::ranges::min, a));
 static_assert(test(std::ranges::min_element, a));
 static_assert(test(std::ranges::minmax, a));
 static_assert(test(std::ranges::minmax_element, a));
 static_assert(test(std::ranges::mismatch, a, a));
 static_assert(test(std::ranges::move, a, a));
 static_assert(test(std::ranges::move_backward, a, a));
 //static_assert(test(std::ranges::next_permutation, a));