[libc++] [test] Add "robust_re_difference_type.compile.pass.cpp" for all the algorithms.
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`.
Differential Revision: https://reviews.llvm.org/D113906
GitOrigin-RevId: 4a8734deb7d54cf15f28b87cdb8a4f601852c10d
diff --git a/test/std/algorithms/robust_against_adl.compile.pass.cpp b/test/std/algorithms/robust_against_adl.compile.pass.cpp
new file mode 100644
index 0000000..0da9257
--- /dev/null
+++ b/test/std/algorithms/robust_against_adl.compile.pass.cpp
@@ -0,0 +1,222 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+}
diff --git a/test/std/algorithms/robust_against_adl.pass.cpp b/test/std/algorithms/robust_against_adl.pass.cpp
deleted file mode 100644
index fca6f98..0000000
--- a/test/std/algorithms/robust_against_adl.pass.cpp
+++ /dev/null
@@ -1,183 +0,0 @@
-//===----------------------------------------------------------------------===//
-//
-// 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;
-}
diff --git a/test/std/algorithms/robust_against_adl_on_new.pass.cpp b/test/std/algorithms/robust_against_adl_on_new.pass.cpp
index 333f11d..5dcfde3 100644
--- a/test/std/algorithms/robust_against_adl_on_new.pass.cpp
+++ b/test/std/algorithms/robust_against_adl_on_new.pass.cpp
@@ -6,17 +6,15 @@
//
//===----------------------------------------------------------------------===//
-// 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; }
};
@@ -25,11 +23,15 @@
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;
}
diff --git a/test/std/algorithms/robust_re_difference_type.compile.pass.cpp b/test/std/algorithms/robust_re_difference_type.compile.pass.cpp
new file mode 100644
index 0000000..cf33967
--- /dev/null
+++ b/test/std/algorithms/robust_re_difference_type.compile.pass.cpp
@@ -0,0 +1,257 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+}
diff --git a/test/support/test_macros.h b/test/support/test_macros.h
index 53fb990..afc04b2 100644
--- a/test/support/test_macros.h
+++ b/test/support/test_macros.h
@@ -145,6 +145,12 @@
# 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
