[libc++] [test] Add "robust_re_difference_type.compile.pass.cpp" for all the algorithms.

[• Quuxplusone]

Summary

This is my suggested regression test for D113868, plus some matching improvements to my existing "robust_against_adl" test.

Also, mark these tests as compile-only. They actually are safe to run — notice that the code "runs" at constexpr-time in C++20, without error — because both of the input ranges are entirely filled with nullptr, so no matter how you shuffle the elements, they remain sorted and partitioned and heapified and everything. But there's no real reason to run them at runtime, so let's just avoid the distraction.

Test cases that fail in trunk right now are commented out with TODO FIXME. D113868 currently fixes some-but-not-all of them.

[Mordante]

In general looks good, but some questions.

libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp

8

My concern with this test is a bit, how can we keep it up-to-date when newer versions of the Standard add new algorithms.
I don't see this as a blocker, but if you have any suggestions I'd like to hear them.

58

Is there a reason to change from our usual pattern of #if TEST_STD_VER > 14?
IIRC this question was raised in a review not that long ago, but I don't recall that we wanted to move to this style.

libcxx/test/std/algorithms/robust_re_difference_type.compile.pass.cpp

88

Any idea why this one fails?

[philnik]

libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp

3

Since these are new tests maybe clang-format them to LLVM style?

23

I think a better name would be ConvertibleToInt.

libcxx/test/std/algorithms/robust_re_difference_type.compile.pass.cpp

29

In D110598 I define a TEST_IS_CONSTANT_EVALUATED. The TEST_IS_CONSTANT_EVALUATED is more verbose but I think it is the more general approach. And maybe feature test with __cpp_lib_is_constant_evaluated instead of assuming it in C++20 if you still want to go with NOT_CONSTEVAL.

[• Quuxplusone]

libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp

8

The ideal is, whenever someone implements a new algorithm (like shift_left), they do a quick git grep shift_left for all the places in the codebase that mention it, and fix up the places that need fixing up. Also, they do a quick git grep inplace_merge or whatever, on an algorithm that's similar to the one they're adding, and again fix up the places that need fixing up.
Obviously this ideal was not followed in practice even for shift_left, because there were still TODO comments left in this code. But I can't think of any protocol that would be better than the existing ideal. Just have to work on communicating the best practices and reminding people in code reviews.

23

Veto; sure it's only used once in the whole file, but still I see no reason to make the name longer and more technical.

58

Well, this isn't a "change" for this particular piece of code; I did it with >= in D92776 for some reason.
I don't object to changing it from >= to > in this same PR, as long as we're confusing Phab anyway. :)

libcxx/test/std/algorithms/robust_re_difference_type.compile.pass.cpp

29

I remembered something like that, but was unable to find it via git grep. Apparently because it wasn't checked in yet. :)

I'll merge that "test_macros.h" diff in here and start using it.

Btw, a problem I foresee, both here and (probably) there, is that very soon we'll need a macro that expresses "Test this only if !is_constant_evaluated(), or if the surrounding function isn't constexpr, or if TEST_STD_VER > 20," because some algorithms will be "non-constexpr-friendly in C++20 but constexpr-friendly in C++23". We're going to need something like if (TEST_IS_RUNTIME_OR_CXX20), if (TEST_IS_RUNTIME_OR_CXX23), etc. We don't need to solve that yet, but it's worth seeing that the problem is coming.

88

Yes: we fail to cast count to the difference_type. (The spec of the _n algorithms is quite weird; they don't accept something of difference_type right off the bat, they accept an arbitrary type and then convert it to "an" integral type.)

[• Quuxplusone]

Switch >= 20 to > 17.
Use TEST_IS_CONSTANT_EVALUATED.

[var-const]

libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp

10

Question: why doesn't this test apply to C++03?

34

Optional nit: maybe initialize data inside the struct instead?

45

Optional nit: functors are repeated a lot across the test, maybe create variables for them as well? It would also be consistent with how the test uses named variables like first and last instead of t.data, t.data + 10, etc.:

(void)std::all_of(first, last, pred);
(void)std::for_each(first, last, apply);
(void)std::generate(first, last, generator);
(void)std::is_sorted(first, last, less);
// ...

46

Do these tests not apply to any of the algorithms in <numeric>?

61

Ultranit: omit the empty parentheses?

83

Just checking: random_shuffle is omitted deliberately, right?

147

Optional: having "with comparators" and "without comparators" as two separate lists makes it harder to notice if the lists happen to go out of sync. I'd prefer having the both versions right next to each other, so that it's easier to spot if one version is accidentally omitted (because the overloads are always next to each other, rather than arbitrarily far away):

(void)std::adjacent_find(first, last);
(void)std::adjacent_find(first, last, std::equal_to<void*>());
(void)std::binary_search(first, last, value, std::less<void*>());
(void)std::equal(first, last, first2);
(void)std::equal(first, last, first2, std::equal_to<void*>());

This is purely a matter of taste, though -- feel free to ignore.

libcxx/test/std/algorithms/robust_re_difference_type.compile.pass.cpp

21

Question: is <utillity> used?

26

Can you please add a comment with a brief explanation of what is special about this iterator class?

29

Nit: include <iterator>?

[ldionne]

LGTM despite some suggestions.

libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp

23

Honestly, Intable is a poor name IMO. I would actually do:

template <class T>
struct ConvertibleTo { TEST_CONSTEXPR operator T() const { return T(); } };

[• Quuxplusone]

libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp

10

Lambdas and braced-initializer-lists (for std::min/max), but really probably just I didn't originally feel like going through and ifdeffing all the algos that were "new in C++11." It was easier just to unsupport the test pre-C++11.

23

Well, I definitely wouldn't make it a template. Tell you what, I'll change it to ConvertibleToIntegral. (That's the phrase in https://eel.is/c++draft/alg.copy#11 )

46

I suppose they could apply to all of the algorithms in <numeric>. I'll do that as a separate PR, since it opens a new can of worms (namely, whether it should be a new test or part of this test).

61

Definitely not. :)

83

I don't remember my original logic, but yeah, since it's deprecated/removed, I think it's fine to omit.
std::shuffle is also omitted, and I think my logic in that case was just that it was too awkward to define a URBG just for that one call.

147

My original logic was that separate lists made it easier to detect when one of the calls was accidentally omitting (or accidentally including) the comparator.
However, when updating these lists in this PR, I did find it pretty awkward to figure out which algos belonged in which list(s); so yeah, I think I'll combine the lists.

libcxx/test/std/algorithms/robust_re_difference_type.compile.pass.cpp

21

I'd thought so, but I guess not. Added <iterator>, removed <utility>.

[• Quuxplusone]

Review comments. Merged the three lists of algorithms into one. (Turned out I was even missing at least one: std::find!)

[• Quuxplusone]

Oops, reupload with git diff -U999 context.

[ldionne]

libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp

10

I know this is annoying, but we don't go the easy way "just because". If this can reasonably be tested in C++03, we should.

[ldionne]

libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp

10

(When I did my review for some reason I thought this test didn't apply to C++03, but I looked too quickly.)

[• Quuxplusone]

Enable the "robust_xxx" tests in C++03 too.
(This means switching from lambdas to named class types, and ifdef'ing out a surprisingly low number of lines.)

[var-const]

libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp

61

Just curious, what's your rationale? I've always seen them as unnecessary boilerplate, so I'm interested to know why you prefer to keep them. To be clear, I'm absolutely fine with keeping them, just interested in your perspective.

83

Can you please add a brief comment to that effect?

[• Quuxplusone]

libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp

61

I've always seen the extra parser codepath that says "Lambdas look like this, except that if the function parameter list is empty, you can omit it" (specially for lambdas — ordinary functions' parameter lists can't be omitted) as unnecessary complication added to an otherwise relatively clean design.
I don't teach people that the special case exists, and my impression is that nobody ever discovers it on their own. (Because why would anyone ever try omitting a function's parameter-list? nobody should expect that to work!)

(The other lambda snafu of which I'm aware is that [x, y, &]() { } is ill-formed — the correct syntax places the default first, not last: [&, x, y]() { }. That's marginally more discoverable by newbies, but still a relative corner case, because 99% of the time, you want [&], and if the compiler stops you from writing [x,&] or [&x,=] with a cryptic error message, well, strewing the road with nails is one way to discourage people from going down it. ;)

[Mordante]

One nit for me left.

libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp

58

There are still some >='s left.

[• Quuxplusone]

libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp

58

My intent is that the only >=s left are for >= 11, where that seems to be our style:

$ git grep -ho 'TEST_STD_VER >[=]* [0-9]*' ../libcxx/test/ | sort | uniq -c | sort -n
  15 TEST_STD_VER > 3
  20 TEST_STD_VER > 03
  37 TEST_STD_VER >= 17
  92 TEST_STD_VER >= 20
 110 TEST_STD_VER > 20
 181 TEST_STD_VER >= 14
 309 TEST_STD_VER > 11
 381 TEST_STD_VER > 14
 474 TEST_STD_VER > 17
1259 TEST_STD_VER >= 11

[var-const]

LGTM (with one optional comment re. random_shuffle).

[philnik]

libcxx/test/std/algorithms/robust_re_difference_type.compile.pass.cpp

75

You didn't format this file

[Mordante]

LGTM when the CI is green.

[• Quuxplusone]

Add missing TEST_CONSTEXPRs to the new callable struct types. This should make CI happy.

libcxx/test/std/algorithms/robust_against_adl.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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+#include <algorithm>
+#include <functional>
+
+#include "test_macros.h"
+
+struct Incomplete;
+template<class T> struct Holder { T t; };
+
+template<class>
+struct ConvertibleToIntegral {
+    TEST_CONSTEXPR operator int() const { return 1; }
+};
+
+struct Tester {
+    using Element = Holder<Incomplete>*;
+    Element data[10] = {};
+};
+
+struct UnaryVoid { TEST_CONSTEXPR_CXX14 void operator()(void*) const {} };
+struct UnaryTrue { TEST_CONSTEXPR bool operator()(void*) const { return true; } };
+struct NullaryValue { TEST_CONSTEXPR decltype(nullptr) operator()() const { return nullptr; } };
+struct UnaryTransform { TEST_CONSTEXPR decltype(nullptr) operator()(void*) const { return nullptr; } };
+struct BinaryTransform { TEST_CONSTEXPR decltype(nullptr) operator()(void*, void*) const { return nullptr; } };
+
+TEST_CONSTEXPR_CXX20 bool all_the_algorithms()
+{
+    Tester t;
+    Tester u;
+    Holder<Incomplete> **first = t.data;
+    Holder<Incomplete> **mid = t.data+5;
+    Holder<Incomplete> **last = t.data+10;
+    Holder<Incomplete> **first2 = u.data;
+    Holder<Incomplete> **mid2 = u.data+5;
+    Holder<Incomplete> **last2 = u.data+10;
+    Tester::Element value = nullptr;
+    ConvertibleToIntegral<Tester::Element> count;
+
+    (void)std::adjacent_find(first, last);
+    (void)std::adjacent_find(first, last, std::equal_to<void*>());
+#if TEST_STD_VER >= 11
+    (void)std::all_of(first, last, UnaryTrue());
+    (void)std::any_of(first, last, UnaryTrue());
+#endif
+    (void)std::binary_search(first, last, value);
+    (void)std::binary_search(first, last, value, std::less<void*>());
+#if TEST_STD_VER > 17
+    (void)std::clamp(value, value, value);
+    (void)std::clamp(value, value, value, std::less<void*>());
+#endif
+    (void)std::copy(first, last, first2);
+    (void)std::copy_backward(first, last, last2);
+    // TODO FIXME (void)std::copy_n(first, count, first2);
+    (void)std::count(first, last, value);
+    (void)std::count_if(first, last, UnaryTrue());
+    (void)std::distance(first, last);
+    (void)std::equal(first, last, first2);
+    (void)std::equal(first, last, first2, std::equal_to<void*>());
+#if TEST_STD_VER > 11
+    (void)std::equal(first, last, first2, last2);
+    (void)std::equal(first, last, first2, last2, std::equal_to<void*>());
+#endif
+    (void)std::equal_range(first, last, value);
+    (void)std::equal_range(first, last, value, std::less<void*>());
+    (void)std::fill(first, last, value);
+    (void)std::fill_n(first, count, value);
+    (void)std::find(first, last, value);
+    // TODO FIXME (void)std::find_end(first, last, first2, mid2);
+    // TODO FIXME (void)std::find_end(first, last, first2, mid2, std::equal_to<void*>());
+    (void)std::find_if(first, last, UnaryTrue());
+    (void)std::find_if_not(first, last, UnaryTrue());
+    (void)std::for_each(first, last, UnaryVoid());
+#if TEST_STD_VER > 14
+    (void)std::for_each_n(first, count, UnaryVoid());
+#endif
+    (void)std::generate(first, last, NullaryValue());
+    (void)std::generate_n(first, count, NullaryValue());
+    (void)std::includes(first, last, first2, last2);
+    (void)std::includes(first, last, first2, last2, std::less<void*>());
+    (void)std::is_heap(first, last);
+    (void)std::is_heap(first, last, std::less<void*>());
+    (void)std::is_heap_until(first, last);
+    (void)std::is_heap_until(first, last, std::less<void*>());
+    (void)std::is_partitioned(first, last, UnaryTrue());
+    (void)std::is_permutation(first, last, first2);
+    (void)std::is_permutation(first, last, first2, std::equal_to<void*>());
+#if TEST_STD_VER > 11
+    (void)std::is_permutation(first, last, first2, last2);
+    (void)std::is_permutation(first, last, first2, last2, std::equal_to<void*>());
+#endif
+    (void)std::is_sorted(first, last);
+    (void)std::is_sorted(first, last, std::less<void*>());
+    (void)std::is_sorted_until(first, last);
+    (void)std::is_sorted_until(first, last, std::less<void*>());
+    // RELIES ON ADL SWAP (void)std::inplace_merge(first, mid, last);
+    // RELIES ON ADL SWAP (void)std::inplace_merge(first, mid, last, std::less<void*>());
+    // RELIES ON ADL SWAP (void)std::iter_swap(first, mid);
+    (void)std::lexicographical_compare(first, last, first2, last2);
+    (void)std::lexicographical_compare(first, last, first2, last2, std::less<void*>());
+    // TODO: lexicographical_compare_three_way
+    (void)std::lower_bound(first, last, value);
+    (void)std::lower_bound(first, last, value, std::less<void*>());
+    // RELIES ON ADL SWAP (void)std::make_heap(first, last);
+    // RELIES ON ADL SWAP (void)std::make_heap(first, last, std::less<void*>());
+    (void)std::max(value, value);
+    (void)std::max(value, value, std::less<void*>());
+#if TEST_STD_VER >= 11
+    (void)std::max({ value, value });
+    (void)std::max({ value, value }, std::less<void*>());
+#endif
+    (void)std::max_element(first, last);
+    (void)std::max_element(first, last, std::less<void*>());
+    (void)std::merge(first, mid, mid, last, first2);
+    (void)std::merge(first, mid, mid, last, first2, std::less<void*>());
+    (void)std::min(value, value);
+    (void)std::min(value, value, std::less<void*>());
+#if TEST_STD_VER >= 11
+    (void)std::min({ value, value });
+    (void)std::min({ value, value }, std::less<void*>());
+#endif
+    (void)std::min_element(first, last);
+    (void)std::min_element(first, last, std::less<void*>());
+    (void)std::minmax(value, value);
+    (void)std::minmax(value, value, std::less<void*>());
+#if TEST_STD_VER >= 11
+    (void)std::minmax({ value, value });
+    (void)std::minmax({ value, value }, std::less<void*>());
+#endif
+    (void)std::minmax_element(first, last);
+    (void)std::minmax_element(first, last, std::less<void*>());
+    (void)std::mismatch(first, last, first2);
+    (void)std::mismatch(first, last, first2, std::equal_to<void*>());
+#if TEST_STD_VER > 11
+    (void)std::mismatch(first, last, first2, last2);
+    (void)std::mismatch(first, last, first2, last2, std::equal_to<void*>());
+#endif
+    (void)std::move(first, last, first2);
+    (void)std::move_backward(first, last, last2);
+    // RELIES ON ADL SWAP (void)std::next_permutation(first, last);
+    // RELIES ON ADL SWAP (void)std::next_permutation(first, last, std::less<void*>());
+#if TEST_STD_VER >= 11
+    (void)std::none_of(first, last, UnaryTrue());
+#endif
+    // RELIES ON ADL SWAP (void)std::nth_element(first, mid, last);
+    // RELIES ON ADL SWAP (void)std::nth_element(first, mid, last, std::less<void*>());
+    // RELIES ON ADL SWAP (void)std::partial_sort(first, mid, last);
+    // RELIES ON ADL SWAP (void)std::partial_sort(first, mid, last, std::less<void*>());
+    // RELIES ON ADL SWAP (void)std::partial_sort_copy(first, last, first2, mid2);
+    // RELIES ON ADL SWAP (void)std::partial_sort_copy(first, last, first2, mid2, std::less<void*>());
+    // RELIES ON ADL SWAP (void)std::partition(first, last, UnaryTrue());
+    (void)std::partition_copy(first, last, first2, last2, UnaryTrue());
+    (void)std::partition_point(first, last, UnaryTrue());
+    // RELIES ON ADL SWAP (void)std::pop_heap(first, last);
+    // RELIES ON ADL SWAP (void)std::pop_heap(first, last, std::less<void*>());
+    // RELIES ON ADL SWAP (void)std::prev_permutation(first, last);
+    // RELIES ON ADL SWAP (void)std::prev_permutation(first, last, std::less<void*>());
+    // RELIES ON ADL SWAP (void)std::push_heap(first, last);
+    // RELIES ON ADL SWAP (void)std::push_heap(first, last, std::less<void*>());
+    (void)std::remove(first, last, value);
+    (void)std::remove_copy(first, last, first2, value);
+    (void)std::remove_copy_if(first, last, first2, UnaryTrue());
+    (void)std::remove_if(first, last, UnaryTrue());
+    (void)std::replace(first, last, value, value);
+    (void)std::replace_copy(first, last, first2, value, value);
+    (void)std::replace_copy_if(first, last, first2, UnaryTrue(), value);
+    (void)std::replace_if(first, last, UnaryTrue(), value);
+    // RELIES ON ADL SWAP (void)std::reverse(first, last);
+    // RELIES ON ADL SWAP (void)std::reverse_copy(first, last, first2);
+    // RELIES ON ADL SWAP (void)std::rotate(first, mid, last);
+    (void)std::rotate_copy(first, mid, last, first2);
+    (void)std::search(first, last, first2, mid2);
+    (void)std::search(first, last, first2, mid2, std::equal_to<void*>());
+    (void)std::search_n(first, last, count, value);
+    (void)std::search_n(first, last, count, value, std::equal_to<void*>());
+    (void)std::set_difference(first, mid, mid, last, first2);
+    (void)std::set_difference(first, mid, mid, last, first2, std::less<void*>());
+    (void)std::set_intersection(first, mid, mid, last, first2);
+    (void)std::set_intersection(first, mid, mid, last, first2, std::less<void*>());
+    (void)std::set_symmetric_difference(first, mid, mid, last, first2);
+    (void)std::set_symmetric_difference(first, mid, mid, last, first2, std::less<void*>());
+    (void)std::set_union(first, mid, mid, last, first2);
+    (void)std::set_union(first, mid, mid, last, first2, std::less<void*>());
+#if TEST_STD_VER > 17
+    (void)std::shift_left(first, last, count);
+    (void)std::shift_right(first, last, count);
+#endif
+    // RELIES ON ADL SWAP (void)std::sort(first, last);
+    // RELIES ON ADL SWAP (void)std::sort(first, last, std::less<void*>());
+    // RELIES ON ADL SWAP (void)std::sort_heap(first, last);
+    // RELIES ON ADL SWAP (void)std::sort_heap(first, last, std::less<void*>());
+    // RELIES ON ADL SWAP (void)std::stable_partition(first, last, UnaryTrue());
+    // RELIES ON ADL SWAP (void)std::stable_sort(first, last);
+    // RELIES ON ADL SWAP (void)std::stable_sort(first, last, std::less<void*>());
+    // RELIES ON ADL SWAP (void)std::swap_ranges(first, last, first2);
+    (void)std::transform(first, last, first2, UnaryTransform());
+    (void)std::transform(first, mid, mid, first2, BinaryTransform());
+    (void)std::unique(first, last);
+    (void)std::unique(first, last, std::equal_to<void*>());
+    (void)std::unique_copy(first, last, first2);
+    (void)std::unique_copy(first, last, first2, std::equal_to<void*>());
+    (void)std::upper_bound(first, last, value);
+    (void)std::upper_bound(first, last, value, std::less<void*>());
+
+    return true;
+}
+
+void test()
+{
+    all_the_algorithms();
+#if TEST_STD_VER > 17
+    static_assert(all_the_algorithms());
+#endif
+}

libcxx/test/std/algorithms/robust_against_adl.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
-
-// <algorithm>
-
-#include <algorithm>
-#include <functional>
-
-#include "test_macros.h"
-
-struct Incomplete;
-template<class T> struct Holder { T t; };
-
-template<class>
-struct Intable {
-    TEST_CONSTEXPR operator int() const { return 1; }
-};
-
-struct Tester {
-    using Element = Holder<Incomplete>*;
-    Element data[10];
-};
-
-TEST_CONSTEXPR_CXX20 bool test()
-{
-    Tester t {};
-    Tester u {};
-    Tester::Element value = nullptr;
-    Intable<Tester::Element> count;
-
-    // THESE RELY ON ADL SWAP IN PRACTICE:
-    // swap_ranges, iter_swap, reverse, rotate, partition
-    // sort, nth_element
-    // pop_heap, sort_heap, partial_sort, partial_sort_copy
-    // next_permutation, prev_permutation
-    // stable_partition, stable_sort, inplace_merge
-    // THESE RELY ON ADL SWAP IN THEORY:
-    // push_heap, make_heap
-
-    (void)std::all_of(t.data, t.data+10, [](void*){ return true; });
-    (void)std::any_of(t.data, t.data+10, [](void*){ return true; });
-    (void)std::copy(t.data, t.data+10, u.data);
-    (void)std::copy_n(t.data, count, u.data);
-    (void)std::copy_backward(t.data, t.data+10, u.data+10);
-    (void)std::count(t.data, t.data+10, value);
-    (void)std::count_if(t.data, t.data+10, [](void*){ return true; });
-    (void)std::distance(t.data, t.data+10);
-    (void)std::fill(t.data, t.data+10, value);
-    (void)std::fill_n(t.data, count, value);
-    (void)std::find_if(t.data, t.data+10, [](void*){ return true; });
-    (void)std::find_if_not(t.data, t.data+10, [](void*){ return true; });
-    (void)std::for_each(t.data, t.data+10, [](void*){});
-#if TEST_STD_VER >= 17
-    (void)std::for_each_n(t.data, count, [](void*){});
-#endif
-    (void)std::generate(t.data, t.data+10, [](){ return nullptr; });
-    (void)std::generate_n(t.data, count, [](){ return nullptr; });
-    (void)std::is_partitioned(t.data, t.data+10, [](void*){ return true; });
-    (void)std::move(t.data, t.data+10, u.data);
-    (void)std::move_backward(t.data, t.data+10, u.data+10);
-    (void)std::none_of(t.data, t.data+10, [](void*){ return true; });
-    (void)std::partition_copy(t.data, t.data+5, u.data, u.data+5, [](void*){ return true; });
-    (void)std::partition_point(t.data, t.data+10, [](void*){ return true; });
-    (void)std::remove(t.data, t.data+10, value);
-    (void)std::remove_copy(t.data, t.data+10, u.data, value);
-    (void)std::remove_copy_if(t.data, t.data+10, u.data, [](void*){ return true; });
-    (void)std::remove_if(t.data, t.data+10, [](void*){ return true; });
-    (void)std::replace(t.data, t.data+10, value, value);
-    (void)std::replace_copy(t.data, t.data+10, u.data, value, value);
-    (void)std::replace_copy_if(t.data, t.data+10, u.data, [](void*){ return true; }, value);
-    (void)std::replace_if(t.data, t.data+10, [](void*){ return true; }, value);
-    (void)std::reverse_copy(t.data, t.data+10, u.data);
-    (void)std::rotate_copy(t.data, t.data+5, t.data+10, u.data);
-    // TODO: shift_left
-    // TODO: shift_right
-    (void)std::transform(t.data, t.data+10, u.data, [](void*){ return nullptr; });
-
-    // WITHOUT COMPARATORS
-    (void)std::adjacent_find(t.data, t.data+10);
-    (void)std::binary_search(t.data, t.data+10, t.data[5]);
-    (void)std::equal(t.data, t.data+10, u.data);
-    (void)std::equal_range(t.data, t.data+10, t.data[5]);
-    (void)std::find_end(t.data, t.data+10, u.data, u.data+5);
-    (void)std::includes(t.data, t.data+10, u.data, u.data+10);
-    (void)std::is_heap(t.data, t.data+10);
-    (void)std::is_heap_until(t.data, t.data+10);
-    (void)std::is_permutation(t.data, t.data+10, u.data);
-    (void)std::is_sorted(t.data, t.data+10);
-    (void)std::is_sorted_until(t.data, t.data+10);
-    (void)std::lexicographical_compare(t.data, t.data+10, u.data, u.data+10);
-    // TODO: lexicographical_compare_three_way
-    (void)std::lower_bound(t.data, t.data+10, t.data[5]);
-    (void)std::max(value, value);
-    (void)std::max({ value, value });
-    (void)std::max_element(t.data, t.data+10);
-    (void)std::merge(t.data, t.data+5, t.data+5, t.data+10, u.data);
-    (void)std::min(value, value);
-    (void)std::min({ value, value });
-    (void)std::min_element(t.data, t.data+10);
-    (void)std::minmax(value, value);
-    (void)std::minmax({ value, value });
-    (void)std::minmax_element(t.data, t.data+10);
-    (void)std::mismatch(t.data, t.data+10, u.data);
-    (void)std::search(t.data, t.data+10, u.data, u.data+5);
-    (void)std::search_n(t.data, t.data+10, count, value);
-    (void)std::set_difference(t.data, t.data+5, t.data+5, t.data+10, u.data);
-    (void)std::set_intersection(t.data, t.data+5, t.data+5, t.data+10, u.data);
-    (void)std::set_symmetric_difference(t.data, t.data+5, t.data+5, t.data+10, u.data);
-    (void)std::set_union(t.data, t.data+5, t.data+5, t.data+10, u.data);
-    (void)std::unique(t.data, t.data+10);
-    (void)std::unique_copy(t.data, t.data+10, u.data);
-    (void)std::upper_bound(t.data, t.data+10, t.data[5]);
-#if TEST_STD_VER >= 14
-    (void)std::equal(t.data, t.data+10, u.data, u.data+10);
-    (void)std::is_permutation(t.data, t.data+10, u.data, u.data+10);
-    (void)std::mismatch(t.data, t.data+10, u.data, u.data+10);
-#endif
-#if TEST_STD_VER >= 20
-    (void)std::clamp(value, value, value);
-#endif
-
-    // WITH COMPARATORS
-    (void)std::adjacent_find(t.data, t.data+10, std::equal_to<void*>());
-    (void)std::binary_search(t.data, t.data+10, value, std::less<void*>());
-    (void)std::equal(t.data, t.data+10, u.data, std::equal_to<void*>());
-    (void)std::equal_range(t.data, t.data+10, value, std::less<void*>());
-    (void)std::find_end(t.data, t.data+10, u.data, u.data+5, std::equal_to<void*>());
-    (void)std::includes(t.data, t.data+10, u.data, u.data+10, std::less<void*>());
-    (void)std::is_heap(t.data, t.data+10, std::less<void*>());
-    (void)std::is_heap_until(t.data, t.data+10, std::less<void*>());
-    (void)std::is_permutation(t.data, t.data+10, u.data, std::equal_to<void*>());
-    (void)std::is_sorted(t.data, t.data+10, std::less<void*>());
-    (void)std::is_sorted_until(t.data, t.data+10, std::less<void*>());
-    (void)std::lexicographical_compare(t.data, t.data+10, u.data, u.data+10, std::less<void*>());
-    // TODO: lexicographical_compare_three_way
-    (void)std::lower_bound(t.data, t.data+10, value, std::less<void*>());
-    (void)std::max(value, value, std::less<void*>());
-    (void)std::max({ value, value }, std::less<void*>());
-    (void)std::max_element(t.data, t.data+10, std::less<void*>());
-    (void)std::merge(t.data, t.data+5, t.data+5, t.data+10, u.data, std::less<void*>());
-    (void)std::min(value, value, std::less<void*>());
-    (void)std::min({ value, value }, std::less<void*>());
-    (void)std::min_element(t.data, t.data+10, std::less<void*>());
-    (void)std::minmax(value, value, std::less<void*>());
-    (void)std::minmax({ value, value }, std::less<void*>());
-    (void)std::minmax_element(t.data, t.data+10, std::less<void*>());
-    (void)std::mismatch(t.data, t.data+10, u.data, std::equal_to<void*>());
-    (void)std::search(t.data, t.data+10, u.data, u.data+5, std::equal_to<void*>());
-    (void)std::search_n(t.data, t.data+10, count, value, std::equal_to<void*>());
-    (void)std::set_difference(t.data, t.data+5, t.data+5, t.data+10, u.data, std::less<void*>());
-    (void)std::set_intersection(t.data, t.data+5, t.data+5, t.data+10, u.data, std::less<void*>());
-    (void)std::set_symmetric_difference(t.data, t.data+5, t.data+5, t.data+10, u.data, std::less<void*>());
-    (void)std::set_union(t.data, t.data+5, t.data+5, t.data+10, u.data, std::less<void*>());
-    (void)std::unique(t.data, t.data+10, std::equal_to<void*>());
-    (void)std::unique_copy(t.data, t.data+10, u.data, std::equal_to<void*>());
-    (void)std::upper_bound(t.data, t.data+10, value, std::less<void*>());
-#if TEST_STD_VER >= 14
-    (void)std::equal(t.data, t.data+10, u.data, u.data+10, std::equal_to<void*>());
-    (void)std::is_permutation(t.data, t.data+10, u.data, u.data+10, std::equal_to<void*>());
-    (void)std::mismatch(t.data, t.data+10, u.data, u.data+10, std::equal_to<void*>());
-#endif
-#if TEST_STD_VER >= 20
-    (void)std::clamp(value, value, value, std::less<void*>());
-#endif
-
-    return true;
-}
-
-int main(int, char**)
-{
-    test();
-#if TEST_STD_VER >= 20
-    static_assert(test());
-#endif
-    return 0;
-}

libcxx/test/std/algorithms/robust_against_adl_on_new.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
-
 // <algorithm>
 
 #include <algorithm>
+#include <functional>
 
 #include "test_macros.h"
 
 struct A {
-    int i;
-    A(int v) : i(v) {}
+    int i = 0;
     bool operator<(const A& rhs) const { return i < rhs.i; }
     static bool isEven(const A& a) { return a.i % 2 == 0; }
 };
 
 void *operator new(size_t, A*) = delete;
 
 int main(int, char**)
 {
-    A a[4] = { 1,2,3,4 };
+    A a[4] = {};
     std::sort(a, a+4);
+    std::sort(a, a+4, std::less<A>());
     std::partition(a, a+4, A::isEven);
     std::stable_sort(a, a+4);
+    std::stable_sort(a, a+4, std::less<A>());
     std::stable_partition(a, a+4, A::isEven);
+    std::inplace_merge(a, a+2, a+4);
+    std::inplace_merge(a, a+2, a+4, std::less<A>());
 
     return 0;
 }

libcxx/test/std/algorithms/robust_re_difference_type.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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+//   In the description of the algorithms,
+//   given an iterator a whose difference type is D,
+//   and an expression n of integer-like type other than cv D,
+//   the semantics of a + n and a - n are, respectively,
+//   those of a + D(n) and a - D(n).
+
+#include <algorithm>
+#include <functional>
+#include <iterator>
+
+#include "test_macros.h"
+
+// This iterator rejects expressions like (a + n) and (a - n)
+// whenever n is of any type other than difference_type.
+//
+template<class It, class DifferenceType>
+class PickyIterator {
+    It it_;
+public:
+    using iterator_category = std::random_access_iterator_tag;
+    using value_type = typename std::iterator_traits<It>::value_type;
+    using difference_type = DifferenceType;
+    using pointer = It;
+    using reference = typename std::iterator_traits<It>::reference;
+
+    TEST_CONSTEXPR_CXX14 PickyIterator() = default;
+    TEST_CONSTEXPR_CXX14 explicit PickyIterator(It it) : it_(it) {}
+    TEST_CONSTEXPR_CXX14 reference operator*() const {return *it_;}
+    TEST_CONSTEXPR_CXX14 pointer operator->() const {return it_;}
+    TEST_CONSTEXPR_CXX14 reference operator[](difference_type n) const {return it_[n];}
+
+    friend TEST_CONSTEXPR_CXX14 bool operator==(PickyIterator a, PickyIterator b) { return a.it_ == b.it_; }
+    friend TEST_CONSTEXPR_CXX14 bool operator!=(PickyIterator a, PickyIterator b) { return a.it_ != b.it_; }
+    friend TEST_CONSTEXPR_CXX14 bool operator<(PickyIterator a, PickyIterator b) { return a.it_ < b.it_; }
+    friend TEST_CONSTEXPR_CXX14 bool operator>(PickyIterator a, PickyIterator b) { return a.it_ > b.it_; }
+    friend TEST_CONSTEXPR_CXX14 bool operator<=(PickyIterator a, PickyIterator b) { return a.it_ <= b.it_; }
+    friend TEST_CONSTEXPR_CXX14 bool operator>=(PickyIterator a, PickyIterator b) { return a.it_ >= b.it_; }
+
+    TEST_CONSTEXPR_CXX14 PickyIterator& operator++() {++it_; return *this;}
+    TEST_CONSTEXPR_CXX14 PickyIterator operator++(int) {auto tmp = *this; ++(*this); return tmp;}
+    TEST_CONSTEXPR_CXX14 PickyIterator& operator--() {--it_; return *this;}
+    TEST_CONSTEXPR_CXX14 PickyIterator operator--(int) {auto tmp = *this; --(*this); return tmp;}
+
+    TEST_CONSTEXPR_CXX14 PickyIterator& operator+=(difference_type n) {it_ += n; return *this;}
+    TEST_CONSTEXPR_CXX14 PickyIterator& operator-=(difference_type n) {it_ -= n; return *this;}
+    friend TEST_CONSTEXPR_CXX14 PickyIterator operator+(PickyIterator it, difference_type n) {it += n; return it;}
+    friend TEST_CONSTEXPR_CXX14 PickyIterator operator+(difference_type n, PickyIterator it) {it += n; return it;}
+    friend TEST_CONSTEXPR_CXX14 PickyIterator operator-(PickyIterator it, difference_type n) {it -= n; return it;}
+    friend TEST_CONSTEXPR_CXX14 difference_type operator-(PickyIterator it, PickyIterator jt) {return it.it_ - jt.it_;}
+
+    template<class X> void operator+=(X) = delete;
+    template<class X> void operator-=(X) = delete;
+    template<class X> friend void operator+(PickyIterator, X) = delete;
+    template<class X> friend void operator+(X, PickyIterator) = delete;
+    template<class X> friend void operator-(PickyIterator, X) = delete;
+};
+
+struct UnaryVoid { TEST_CONSTEXPR_CXX14 void operator()(void*) const {} };
+struct UnaryTrue { TEST_CONSTEXPR bool operator()(void*) const { return true; } };
+struct NullaryValue { TEST_CONSTEXPR decltype(nullptr) operator()() const { return nullptr; } };
+struct UnaryTransform { TEST_CONSTEXPR decltype(nullptr) operator()(void*) const { return nullptr; } };
+struct BinaryTransform { TEST_CONSTEXPR decltype(nullptr) operator()(void*, void*) const { return nullptr; } };
+
+TEST_CONSTEXPR_CXX20 bool all_the_algorithms()
+{
+    void *a[10] = {};
+    void *b[10] = {};
+    auto first = PickyIterator<void**, long>(a);
+    auto mid = PickyIterator<void**, long>(a+5);
+    auto last = PickyIterator<void**, long>(a+10);
+    auto first2 = PickyIterator<void**, long long>(b);
+    auto last2 = PickyIterator<void**, long long>(b+10);
+    void *value = nullptr;
+    int count = 1;
+
+    (void)std::adjacent_find(first, last);
+    (void)std::adjacent_find(first, last, std::equal_to<void*>());
+#if TEST_STD_VER >= 11
+    (void)std::all_of(first, last, UnaryTrue());
+    (void)std::any_of(first, last, UnaryTrue());
+#endif
+    (void)std::binary_search(first, last, value);
+    (void)std::binary_search(first, last, value, std::less<void*>());
+#if TEST_STD_VER > 17
+    (void)std::clamp(value, value, value);
+    (void)std::clamp(value, value, value, std::less<void*>());
+#endif
+    (void)std::copy(first, last, first2);
+    (void)std::copy_backward(first, last, last2);
+    // TODO FIXME (void)std::copy_n(first, count, first2);
+    (void)std::count(first, last, value);
+    (void)std::count_if(first, last, UnaryTrue());
+    (void)std::distance(first, last);
+    (void)std::equal(first, last, first2);
+    (void)std::equal(first, last, first2, std::equal_to<void*>());
+#if TEST_STD_VER > 11
+    (void)std::equal(first, last, first2, last2);
+    (void)std::equal(first, last, first2, last2, std::equal_to<void*>());
+#endif
+    (void)std::equal_range(first, last, value);
+    (void)std::equal_range(first, last, value, std::less<void*>());
+    (void)std::fill(first, last, value);
+    (void)std::fill_n(first, count, value);
+    (void)std::find(first, last, value);
+    // TODO FIXME (void)std::find_end(first, last, first2, mid2);
+    // TODO FIXME (void)std::find_end(first, last, first2, mid2, std::equal_to<void*>());
+    (void)std::find_if(first, last, UnaryTrue());
+    (void)std::find_if_not(first, last, UnaryTrue());
+    (void)std::for_each(first, last, UnaryVoid());
+#if TEST_STD_VER > 14
+    (void)std::for_each_n(first, count, UnaryVoid());
+#endif
+    (void)std::generate(first, last, NullaryValue());
+    (void)std::generate_n(first, count, NullaryValue());
+    (void)std::includes(first, last, first2, last2);
+    (void)std::includes(first, last, first2, last2, std::less<void*>());
+    (void)std::is_heap(first, last);
+    (void)std::is_heap(first, last, std::less<void*>());
+    (void)std::is_heap_until(first, last);
+    (void)std::is_heap_until(first, last, std::less<void*>());
+    (void)std::is_partitioned(first, last, UnaryTrue());
+    (void)std::is_permutation(first, last, first2);
+    (void)std::is_permutation(first, last, first2, std::equal_to<void*>());
+#if TEST_STD_VER > 11
+    (void)std::is_permutation(first, last, first2, last2);
+    (void)std::is_permutation(first, last, first2, last2, std::equal_to<void*>());
+#endif
+    (void)std::is_sorted(first, last);
+    (void)std::is_sorted(first, last, std::less<void*>());
+    (void)std::is_sorted_until(first, last);
+    (void)std::is_sorted_until(first, last, std::less<void*>());
+    if (!TEST_IS_CONSTANT_EVALUATED) (void)std::inplace_merge(first, mid, last);
+    if (!TEST_IS_CONSTANT_EVALUATED) (void)std::inplace_merge(first, mid, last, std::less<void*>());
+    (void)std::iter_swap(first, mid);
+    (void)std::lexicographical_compare(first, last, first2, last2);
+    (void)std::lexicographical_compare(first, last, first2, last2, std::less<void*>());
+    // TODO: lexicographical_compare_three_way
+    (void)std::lower_bound(first, last, value);
+    (void)std::lower_bound(first, last, value, std::less<void*>());
+    // TODO FIXME (void)std::make_heap(first, last);
+    // TODO FIXME (void)std::make_heap(first, last, std::less<void*>());
+    (void)std::max(value, value);
+    (void)std::max(value, value, std::less<void*>());
+#if TEST_STD_VER >= 11
+    (void)std::max({ value, value });
+    (void)std::max({ value, value }, std::less<void*>());
+#endif
+    (void)std::max_element(first, last);
+    (void)std::max_element(first, last, std::less<void*>());
+    (void)std::merge(first, mid, mid, last, first2);
+    (void)std::merge(first, mid, mid, last, first2, std::less<void*>());
+    (void)std::min(value, value);
+    (void)std::min(value, value, std::less<void*>());
+#if TEST_STD_VER >= 11
+    (void)std::min({ value, value });
+    (void)std::min({ value, value }, std::less<void*>());
+#endif
+    (void)std::min_element(first, last);
+    (void)std::min_element(first, last, std::less<void*>());
+    (void)std::minmax(value, value);
+    (void)std::minmax(value, value, std::less<void*>());
+#if TEST_STD_VER >= 11
+    (void)std::minmax({ value, value });
+    (void)std::minmax({ value, value }, std::less<void*>());
+#endif
+    (void)std::minmax_element(first, last);
+    (void)std::minmax_element(first, last, std::less<void*>());
+    (void)std::mismatch(first, last, first2);
+    (void)std::mismatch(first, last, first2, std::equal_to<void*>());
+#if TEST_STD_VER > 11
+    (void)std::mismatch(first, last, first2, last2);
+    (void)std::mismatch(first, last, first2, last2, std::equal_to<void*>());
+#endif
+    (void)std::move(first, last, first2);
+    (void)std::move_backward(first, last, last2);
+    (void)std::next_permutation(first, last);
+    (void)std::next_permutation(first, last, std::less<void*>());
+    (void)std::none_of(first, last, UnaryTrue());
+    (void)std::nth_element(first, mid, last);
+    (void)std::nth_element(first, mid, last, std::less<void*>());
+    // TODO FIXME (void)std::partial_sort(first, mid, last);
+    // TODO FIXME (void)std::partial_sort(first, mid, last, std::less<void*>());
+    // TODO FIXME (void)std::partial_sort_copy(first, last, first2, mid2);
+    // TODO FIXME (void)std::partial_sort_copy(first, last, first2, mid2, std::less<void*>());
+    (void)std::partition(first, last, UnaryTrue());
+    (void)std::partition_copy(first, last, first2, last2, UnaryTrue());
+    (void)std::partition_point(first, last, UnaryTrue());
+    // TODO FIXME (void)std::pop_heap(first, last);
+    // TODO FIXME (void)std::pop_heap(first, last, std::less<void*>());
+    (void)std::prev_permutation(first, last);
+    (void)std::prev_permutation(first, last, std::less<void*>());
+    (void)std::push_heap(first, last);
+    (void)std::push_heap(first, last, std::less<void*>());
+    (void)std::remove(first, last, value);
+    (void)std::remove_copy(first, last, first2, value);
+    (void)std::remove_copy_if(first, last, first2, UnaryTrue());
+    (void)std::remove_if(first, last, UnaryTrue());
+    (void)std::replace(first, last, value, value);
+    (void)std::replace_copy(first, last, first2, value, value);
+    (void)std::replace_copy_if(first, last, first2, UnaryTrue(), value);
+    (void)std::replace_if(first, last, UnaryTrue(), value);
+    (void)std::reverse(first, last);
+    (void)std::reverse_copy(first, last, first2);
+    (void)std::rotate(first, mid, last);
+    (void)std::rotate_copy(first, mid, last, first2);
+    // TODO FIXME (void)std::search(first, last, first2, mid2);
+    // TODO FIXME (void)std::search(first, last, first2, mid2, std::equal_to<void*>());
+    // TODO FIXME (void)std::search_n(first, last, count, value);
+    // TODO FIXME (void)std::search_n(first, last, count, value, std::equal_to<void*>());
+    (void)std::set_difference(first, mid, mid, last, first2);
+    (void)std::set_difference(first, mid, mid, last, first2, std::less<void*>());
+    (void)std::set_intersection(first, mid, mid, last, first2);
+    (void)std::set_intersection(first, mid, mid, last, first2, std::less<void*>());
+    (void)std::set_symmetric_difference(first, mid, mid, last, first2);
+    (void)std::set_symmetric_difference(first, mid, mid, last, first2, std::less<void*>());
+    (void)std::set_union(first, mid, mid, last, first2);
+    (void)std::set_union(first, mid, mid, last, first2, std::less<void*>());
+#if TEST_STD_VER > 17
+    (void)std::shift_left(first, last, count);
+    (void)std::shift_right(first, last, count);
+#endif
+    // TODO FIXME (void)std::sort(first, last);
+    // TODO FIXME (void)std::sort(first, last, std::less<void*>());
+    // TODO FIXME (void)std::sort_heap(first, last);
+    // TODO FIXME (void)std::sort_heap(first, last, std::less<void*>());
+    if (!TEST_IS_CONSTANT_EVALUATED) (void)std::stable_partition(first, last, UnaryTrue());
+    if (!TEST_IS_CONSTANT_EVALUATED) (void)std::stable_sort(first, last);
+    if (!TEST_IS_CONSTANT_EVALUATED) (void)std::stable_sort(first, last, std::less<void*>());
+    (void)std::swap_ranges(first, last, first2);
+    (void)std::transform(first, last, first2, UnaryTransform());
+    (void)std::transform(first, mid, mid, first2, BinaryTransform());
+    (void)std::unique(first, last);
+    (void)std::unique(first, last, std::equal_to<void*>());
+    (void)std::unique_copy(first, last, first2);
+    (void)std::unique_copy(first, last, first2, std::equal_to<void*>());
+    (void)std::upper_bound(first, last, value);
+    (void)std::upper_bound(first, last, value, std::less<void*>());
+
+    return true;
+}
+
+void test()
+{
+    all_the_algorithms();
+#if TEST_STD_VER > 17
+    static_assert(all_the_algorithms());
+#endif
+}

libcxx/test/support/test_macros.h

 #endif
 
 #if TEST_STD_VER >= 11
 # define TEST_THROW_SPEC(...)
 #else
 # define TEST_THROW_SPEC(...) throw(__VA_ARGS__)
 #endif
 
+#if defined(__cpp_lib_is_constant_evaluated) && __cpp_lib_is_constant_evaluated >= 201811L
+#  define TEST_IS_CONSTANT_EVALUATED std::is_constant_evaluated()
+#else
+#  define TEST_IS_CONSTANT_EVALUATED false
+#endif
+
 #if TEST_STD_VER >= 14
 # define TEST_CONSTEXPR_CXX14 constexpr
 #else
 # define TEST_CONSTEXPR_CXX14
 #endif
 
 #if TEST_STD_VER >= 17
 # define TEST_CONSTEXPR_CXX17 constexpr