libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 // UNSUPPORTED: c++03, c++11, c++14, c++17
  10
  11 // <algorithm>
  12 //
  13 // Range algorithms should work with proxy iterators. For example, the implementations should use `iter_swap` (which is
  14 // a customization point) rather than plain `swap` (which might not work with certain valid iterators).
  15
  16 #include <algorithm>
  17
  18 #include <array>
  19 #include <concepts>
  20 #include <initializer_list>
  21 #include <iterator>
  22 #include <memory>
  23 #include <random>
  24 #include <ranges>
  25
  26 #include "MoveOnly.h"
  27 #include "test_iterators.h"
  28 #include "test_macros.h"
  29
  30 // (in, ...)
  31 template <class Func, std::ranges::range Input, class ...Args>
  32 constexpr void test(Func&& func, Input& in, Args&& ...args) {
  33   (void)func(in.begin(), in.end(), std::forward<Args>(args)...);
  34   (void)func(in, std::forward<Args>(args)...);
  35 }
  36
  37 // (in1, in2, ...)
  38 template <class Func, std::ranges::range Range1, std::ranges::range Range2, class ...Args>
  39 constexpr void test(Func&& func, Range1& r1, Range2& r2, Args&& ...args) {
  40   (void)func(r1.begin(), r1.end(), r2.begin(), r2.end(), std::forward<Args>(args)...);
  41   (void)func(r1, r2, std::forward<Args>(args)...);
  42 }
  43
  44 // (in, mid, ...)
  45 template <class Func, std::ranges::range Input, class ...Args>
  46 constexpr void test_mid(Func&& func, Input& in, std::ranges::iterator_t<Input> mid, Args&& ...args) {
  47   (void)func(in.begin(), mid, in.end(), std::forward<Args>(args)...);
  48   (void)func(in, mid, std::forward<Args>(args)...);
  49 }
  50
  51 std::mt19937 rand_gen() { return std::mt19937(); }
  52
  53 template <class T>
  54 constexpr void run_tests() {
  55   std::array input = {T{1}, T{2}, T{3}};
  56   ProxyRange in{input};
  57   std::array input2 = {T{4}, T{5}, T{6}};
  58   ProxyRange in2{input2};
  59
  60   auto mid = in.begin() + 1;
  61
  62   std::array output = {T{4}, T{5}, T{6}, T{7}, T{8}, T{9}};
  63   ProxyIterator out{output.begin()};
  64   ProxyIterator out2{output.begin() + 1};
  65   ProxyIterator out_end{output.end()};
  66
  67   T num{2};
  68   Proxy<T&> x{num};
  69   int count = 1;
  70
  71   auto unary_pred = [](const Proxy<T&>&) { return true; };
  72   auto binary_func = [](const Proxy<T>&, const Proxy<T>&) -> Proxy<T> { return Proxy<T>(T()); };
  73   auto gen = [] { return Proxy<T>(T{42}); };
  74
  75   test(std::ranges::any_of, in, unary_pred);
  76   test(std::ranges::all_of, in, unary_pred);
  77 #if TEST_STD_VER >= 23
  78   test(std::ranges::contains, in, x);
  79   test(std::ranges::ends_with, in, in2);
  80 #endif
  81   test(std::ranges::none_of, in, unary_pred);
  82   test(std::ranges::find, in, x);
  83   test(std::ranges::find_if, in, unary_pred);
  84   test(std::ranges::find_if_not, in, unary_pred);
  85 #if TEST_STD_VER >= 23
  86   test(std::ranges::find_last, in, x);
  87   test(std::ranges::find_last_if, in, unary_pred);
  88   test(std::ranges::find_last_if_not, in, unary_pred);
  89 #endif
  90   test(std::ranges::find_first_of, in, in2);
  91   test(std::ranges::adjacent_find, in);
  92   test(std::ranges::mismatch, in, in2);
  93   test(std::ranges::equal, in, in2);
  94   test(std::ranges::lexicographical_compare, in, in2);
  95   test(std::ranges::partition_point, in, unary_pred);
  96   test(std::ranges::lower_bound, in, x);
  97   test(std::ranges::upper_bound, in, x);
  98   test(std::ranges::equal_range, in, x);
  99   test(std::ranges::binary_search, in, x);
 100
 101   test(std::ranges::min_element, in);
 102   test(std::ranges::max_element, in);
 103   test(std::ranges::minmax_element, in);
 104   test(std::ranges::count, in, x);
 105   test(std::ranges::count_if, in, unary_pred);
 106   test(std::ranges::search, in, in2);
 107   test(std::ranges::search_n, in, count, x);
 108   test(std::ranges::find_end, in, in2);
 109   test(std::ranges::is_partitioned, in, unary_pred);
 110   test(std::ranges::is_sorted, in);
 111   test(std::ranges::is_sorted_until, in);
 112   test(std::ranges::includes, in, in2);
 113   test(std::ranges::is_heap, in);
 114   test(std::ranges::is_heap_until, in);
 115   test(std::ranges::is_permutation, in, in2);
 116   test(std::ranges::for_each, in, std::identity{});
 117   std::ranges::for_each_n(in.begin(), count, std::identity{});
 118   if constexpr (std::copyable<T>) {
 119     test(std::ranges::copy, in, out);
 120     std::ranges::copy_n(in.begin(), count, out);
 121     test(std::ranges::copy_if, in, out, unary_pred);
 122     test(std::ranges::copy_backward, in, out_end);
 123   }
 124   test(std::ranges::move, in, out);
 125   test(std::ranges::move_backward, in, out_end);
 126   if constexpr (std::copyable<T>) {
 127     test(std::ranges::fill, in, x);
 128     std::ranges::fill_n(in.begin(), count, x);
 129     test(std::ranges::transform, in, out, std::identity{});
 130     test(std::ranges::transform, in, in2, out, binary_func);
 131   }
 132   test(std::ranges::generate, in, gen);
 133   std::ranges::generate_n(in.begin(), count, gen);
 134   if constexpr (std::copyable<T>) {
 135     test(std::ranges::remove_copy, in, out, x);
 136     test(std::ranges::remove_copy_if, in, out, unary_pred);
 137     test(std::ranges::replace, in, x, x);
 138     test(std::ranges::replace_if, in, unary_pred, x);
 139     test(std::ranges::replace_copy, in, out, x, x);
 140     test(std::ranges::replace_copy_if, in, out, unary_pred, x);
 141   }
 142 #if TEST_STD_VER > 20
 143   test(std::ranges::starts_with, in, in2);
 144 #endif
 145   test(std::ranges::swap_ranges, in, in2);
 146   if constexpr (std::copyable<T>) {
 147     test(std::ranges::reverse_copy, in, out);
 148     test_mid(std::ranges::rotate_copy, in, mid, out);
 149     test(std::ranges::unique_copy, in, out);
 150     test(std::ranges::partition_copy, in, out, out2, unary_pred);
 151     test(std::ranges::partial_sort_copy, in, in2);
 152     test(std::ranges::merge, in, in2, out);
 153     test(std::ranges::set_difference, in, in2, out);
 154     test(std::ranges::set_intersection, in, in2, out);
 155     test(std::ranges::set_symmetric_difference, in, in2, out);
 156     test(std::ranges::set_union, in, in2, out);
 157   }
 158   test(std::ranges::remove, in, x);
 159   test(std::ranges::remove_if, in, unary_pred);
 160   test(std::ranges::reverse, in);
 161   test_mid(std::ranges::rotate, in, mid);
 162   if (!std::is_constant_evaluated()) // `shuffle` isn't `constexpr`.
 163     test(std::ranges::shuffle, in, rand_gen());
 164   if (!std::is_constant_evaluated()) {
 165     if constexpr (std::copyable<T>)
 166       test(std::ranges::sample, in, out, count, rand_gen());
 167   }
 168   test(std::ranges::unique, in);
 169   test(std::ranges::partition, in, unary_pred);
 170   if (!std::is_constant_evaluated())
 171     test(std::ranges::stable_partition, in, unary_pred);
 172   test(std::ranges::sort, in);
 173   if (!std::is_constant_evaluated())
 174     test(std::ranges::stable_sort, in);
 175   test_mid(std::ranges::partial_sort, in, mid);
 176   test_mid(std::ranges::nth_element, in, mid);
 177   if (!std::is_constant_evaluated())
 178     test_mid(std::ranges::inplace_merge, in, mid);
 179   test(std::ranges::make_heap, in);
 180   test(std::ranges::push_heap, in);
 181   test(std::ranges::pop_heap, in);
 182   test(std::ranges::sort_heap, in);
 183   test(std::ranges::prev_permutation, in);
 184   test(std::ranges::next_permutation, in);
 185
 186   // The algorithms that work on uninitialized memory have constraints that prevent proxy iterators from being used with
 187   // them.
 188 }
 189
 190 constexpr bool test_all() {
 191   run_tests<int>();
 192   run_tests<MoveOnly>();
 193
 194   return true;
 195 }
 196
 197 int main(int, char**) {
 198   test_all();
 199   static_assert(test_all());
 200
 201   return 0;
 202 }