libcxx/test/std/algorithms/ranges_robust_against_dangling.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 return `std::ranges::dangling` when given a dangling range.
  14
  15 #include <algorithm>
  16
  17 #include <array>
  18 #include <concepts>
  19 #include <functional>
  20 #include <iterator>
  21 #include <ranges>
  22 #include <random>
  23 #include <utility>
  24
  25 #include "test_iterators.h"
  26
  27 struct NonBorrowedRange {
  28   using Iter = int*;
  29   using Sent = sentinel_wrapper<Iter>;
  30
  31   int* data_;
  32   std::size_t size_;
  33
  34   template <std::size_t N>
  35   constexpr explicit NonBorrowedRange(std::array<int, N>& arr) : data_{arr.data()}, size_{arr.size()} {}
  36
  37   constexpr Iter begin() const { return data_; };
  38   constexpr Sent end() const { return Sent{data_ + size_}; };
  39 };
  40
  41 using R = NonBorrowedRange;
  42
  43 // (dangling_in, ...)
  44 template <class ExpectedT = std::ranges::dangling, class Func, std::ranges::range Input, class ...Args>
  45 constexpr void dangling_1st(Func&& func, Input& in, Args&& ...args) {
  46   decltype(auto) result = func(R(in), std::forward<Args>(args)...);
  47   static_assert(std::same_as<decltype(result), ExpectedT>);
  48 }
  49
  50 // (in, dangling_in, ...)
  51 template <class ExpectedT = std::ranges::dangling, class Func, std::ranges::range Input, class ...Args>
  52 constexpr void dangling_2nd(Func&& func, Input& in1, Input& in2, Args&& ...args) {
  53   decltype(auto) result = func(in1, R(in2), std::forward<Args>(args)...);
  54   static_assert(std::same_as<decltype(result), ExpectedT>);
  55 }
  56
  57 // (dangling_in1, dangling_in2, ...)
  58 template <class ExpectedT = std::ranges::dangling, class Func, std::ranges::range Input, class ...Args>
  59 constexpr void dangling_both(Func&& func, Input& in1, Input& in2, Args&& ...args) {
  60   decltype(auto) result = func(R(in1), R(in2), std::forward<Args>(args)...);
  61   static_assert(std::same_as<decltype(result), ExpectedT>);
  62 }
  63
  64 std::mt19937 rand_gen() { return std::mt19937(); }
  65
  66 // TODO: also check the iterator values for algorithms that return `*_result` types.
  67 constexpr bool test_all() {
  68   using std::ranges::dangling;
  69
  70   using std::ranges::binary_transform_result;
  71   using std::ranges::copy_result;
  72   using std::ranges::copy_backward_result;
  73   using std::ranges::copy_if_result;
  74   using std::ranges::for_each_result;
  75   using std::ranges::merge_result;
  76   using std::ranges::minmax_result;
  77   using std::ranges::mismatch_result;
  78   using std::ranges::move_result;
  79   using std::ranges::move_backward_result;
  80   using std::ranges::next_permutation_result;
  81   using std::ranges::partial_sort_copy_result;
  82   using std::ranges::partition_copy_result;
  83   using std::ranges::prev_permutation_result;
  84   using std::ranges::remove_copy_result;
  85   using std::ranges::remove_copy_if_result;
  86   using std::ranges::replace_copy_result;
  87   using std::ranges::replace_copy_if_result;
  88   using std::ranges::reverse_copy_result;
  89   using std::ranges::rotate_copy_result;
  90   using std::ranges::set_difference_result;
  91   using std::ranges::set_intersection_result;
  92   using std::ranges::set_symmetric_difference_result;
  93   using std::ranges::set_union_result;
  94   using std::ranges::swap_ranges_result;
  95   using std::ranges::unary_transform_result;
  96   using std::ranges::unique_copy_result;
  97
  98   auto unary_pred = [](int i) { return i > 0; };
  99   auto binary_pred = [](int i, int j) { return i < j; };
 100   auto gen = [] { return 42; };
 101
 102   std::array in = {1, 2, 3};
 103   std::array in2 = {4, 5, 6};
 104
 105   auto mid = in.begin() + 1;
 106
 107   std::array output = {7, 8, 9, 10, 11, 12};
 108   auto out = output.begin();
 109   auto out2 = output.begin() + 1;
 110
 111   int x = 2;
 112   std::size_t count = 1;
 113
 114   dangling_1st(std::ranges::find, in, x);
 115   dangling_1st(std::ranges::find_if, in, unary_pred);
 116   dangling_1st(std::ranges::find_if_not, in, unary_pred);
 117   dangling_1st(std::ranges::find_first_of, in, in2);
 118   dangling_1st(std::ranges::adjacent_find, in);
 119   dangling_1st<mismatch_result<dangling, int*>>(std::ranges::mismatch, in, in2);
 120   dangling_2nd<mismatch_result<int*, dangling>>(std::ranges::mismatch, in, in2);
 121   dangling_both<mismatch_result<dangling, dangling>>(std::ranges::mismatch, in, in2);
 122   dangling_1st(std::ranges::partition_point, in, unary_pred);
 123   dangling_1st(std::ranges::lower_bound, in, x);
 124   dangling_1st(std::ranges::upper_bound, in, x);
 125   dangling_1st(std::ranges::equal_range, in, x);
 126   dangling_1st(std::ranges::min_element, in);
 127   dangling_1st(std::ranges::max_element, in);
 128   dangling_1st<minmax_result<dangling>>(std::ranges::minmax_element, in);
 129   dangling_1st(std::ranges::search, in, in2);
 130   dangling_1st(std::ranges::search_n, in, count, x);
 131   dangling_1st(std::ranges::find_end, in, in2);
 132   dangling_1st(std::ranges::is_sorted_until, in);
 133   dangling_1st(std::ranges::is_heap_until, in);
 134   dangling_1st<for_each_result<dangling, decltype(unary_pred)>>(std::ranges::for_each, in, unary_pred);
 135   dangling_1st<copy_result<dangling, int*>>(std::ranges::copy, in, out);
 136   dangling_1st<copy_backward_result<dangling, int*>>(std::ranges::copy_backward, in, output.end());
 137   dangling_1st<copy_if_result<dangling, int*>>(std::ranges::copy_if, in, out, unary_pred);
 138   dangling_1st<move_result<dangling, int*>>(std::ranges::move, in, out);
 139   dangling_1st<move_backward_result<dangling, int*>>(std::ranges::move_backward, in, output.end());
 140   dangling_1st(std::ranges::fill, in, x);
 141   { // transform
 142     std::array out_transform = {false, true, true};
 143     dangling_1st<unary_transform_result<dangling, bool*>>(std::ranges::transform, in, out_transform.begin(), unary_pred);
 144     dangling_1st<binary_transform_result<dangling, int*, bool*>>(
 145         std::ranges::transform, in, in2, out_transform.begin(), binary_pred);
 146     dangling_2nd<binary_transform_result<int*, dangling, bool*>>(
 147         std::ranges::transform, in, in2, out_transform.begin(), binary_pred);
 148     dangling_both<binary_transform_result<dangling, dangling, bool*>>(
 149         std::ranges::transform, in, in2, out_transform.begin(), binary_pred);
 150   }
 151   dangling_1st(std::ranges::generate, in, gen);
 152   dangling_1st<remove_copy_result<dangling, int*>>(std::ranges::remove_copy, in, out, x);
 153   dangling_1st<remove_copy_if_result<dangling, int*>>(std::ranges::remove_copy_if, in, out, unary_pred);
 154   dangling_1st(std::ranges::replace, in, x, x);
 155   dangling_1st(std::ranges::replace_if, in, std::identity{}, x);
 156   dangling_1st<replace_copy_result<dangling, int*>>(std::ranges::replace_copy, in, out, x, x);
 157   dangling_1st<replace_copy_if_result<dangling, int*>>(std::ranges::replace_copy_if, in, out, unary_pred, x);
 158   dangling_1st<swap_ranges_result<dangling, int*>>(std::ranges::swap_ranges, in, in2);
 159   dangling_2nd<swap_ranges_result<int*, dangling>>(std::ranges::swap_ranges, in, in2);
 160   dangling_both<swap_ranges_result<dangling, dangling>>(std::ranges::swap_ranges, in, in2);
 161   dangling_1st<reverse_copy_result<dangling, int*>>(std::ranges::reverse_copy, in, out);
 162   dangling_1st<rotate_copy_result<dangling, int*>>(std::ranges::rotate_copy, in, mid, out);
 163   dangling_1st<unique_copy_result<dangling, int*>>(std::ranges::unique_copy, in, out);
 164   dangling_1st<partition_copy_result<dangling, int*, int*>>(std::ranges::partition_copy, in, out, out2, unary_pred);
 165   dangling_1st<partial_sort_copy_result<dangling, int*>>(std::ranges::partial_sort_copy, in, in2);
 166   dangling_2nd<partial_sort_copy_result<int*, dangling>>(std::ranges::partial_sort_copy, in, in2);
 167   dangling_both<partial_sort_copy_result<dangling, dangling>>(std::ranges::partial_sort_copy, in, in2);
 168   dangling_1st<merge_result<dangling, int*, int*>>(std::ranges::merge, in, in2, out);
 169   dangling_2nd<merge_result<int*, dangling, int*>>(std::ranges::merge, in, in2, out);
 170   dangling_both<merge_result<dangling, dangling, int*>>(std::ranges::merge, in, in2, out);
 171   dangling_1st<set_difference_result<dangling, int*>>(std::ranges::set_difference, in, in2, out);
 172   dangling_1st<set_intersection_result<dangling, int*, int*>>(std::ranges::set_intersection, in, in2, out);
 173   dangling_2nd<set_intersection_result<int*, dangling, int*>>(std::ranges::set_intersection, in, in2, out);
 174   dangling_both<set_intersection_result<dangling, dangling, int*>>(std::ranges::set_intersection, in, in2, out);
 175   dangling_1st<set_symmetric_difference_result<dangling, int*, int*>>(
 176       std::ranges::set_symmetric_difference, in, in2, out);
 177   dangling_2nd<set_symmetric_difference_result<int*, dangling, int*>>(
 178       std::ranges::set_symmetric_difference, in, in2, out);
 179   dangling_both<set_symmetric_difference_result<dangling, dangling, int*>>(
 180       std::ranges::set_symmetric_difference, in, in2, out);
 181   dangling_1st<set_union_result<dangling, int*, int*>>(std::ranges::set_union, in, in2, out);
 182   dangling_2nd<set_union_result<int*, dangling, int*>>(std::ranges::set_union, in, in2, out);
 183   dangling_both<set_union_result<dangling, dangling, int*>>(std::ranges::set_union, in, in2, out);
 184   dangling_1st(std::ranges::remove, in, x);
 185   dangling_1st(std::ranges::remove_if, in, unary_pred);
 186   dangling_1st(std::ranges::reverse, in);
 187   dangling_1st(std::ranges::rotate, in, mid);
 188   if (!std::is_constant_evaluated()) // `shuffle` isn't `constexpr`.
 189     dangling_1st(std::ranges::shuffle, in, rand_gen());
 190   dangling_1st(std::ranges::unique, in);
 191   dangling_1st(std::ranges::partition, in, unary_pred);
 192   if (!std::is_constant_evaluated())
 193     dangling_1st(std::ranges::stable_partition, in, unary_pred);
 194   dangling_1st(std::ranges::sort, in);
 195   if (!std::is_constant_evaluated())
 196     dangling_1st(std::ranges::stable_sort, in);
 197   dangling_1st(std::ranges::partial_sort, in, mid);
 198   dangling_1st(std::ranges::nth_element, in, mid);
 199   if (!std::is_constant_evaluated())
 200     dangling_1st(std::ranges::inplace_merge, in, mid);
 201   dangling_1st(std::ranges::make_heap, in);
 202   dangling_1st(std::ranges::push_heap, in);
 203   dangling_1st(std::ranges::pop_heap, in);
 204   dangling_1st(std::ranges::make_heap, in);
 205   dangling_1st(std::ranges::sort_heap, in);
 206   dangling_1st<prev_permutation_result<dangling>>(std::ranges::prev_permutation, in);
 207   dangling_1st<next_permutation_result<dangling>>(std::ranges::next_permutation, in);
 208
 209   return true;
 210 }
 211
 212 int main(int, char**) {
 213   test_all();
 214   static_assert(test_all());
 215
 216   return 0;
 217 }