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 using InIter = std::array<int, 3>::iterator; 98 using OutIter = std::array<int, 6>::iterator; 99 100 auto unary_pred = [](int i) { return i > 0; }; 101 auto binary_pred = [](int i, int j) { return i < j; }; 102 auto gen = [] { return 42; }; 103 104 std::array in = {1, 2, 3}; 105 std::array in2 = {4, 5, 6}; 106 107 auto mid = in.data() + 1; 108 109 std::array output = {7, 8, 9, 10, 11, 12}; 110 auto out = output.begin(); 111 auto out2 = output.begin() + 1; 112 113 int x = 2; 114 std::size_t count = 1; 115 116 dangling_1st(std::ranges::find, in, x); 117 dangling_1st(std::ranges::find_if, in, unary_pred); 118 dangling_1st(std::ranges::find_if_not, in, unary_pred); 119 #if TEST_STD_VER >= 23 120 dangling_1st(std::ranges::find_last, in, x); 121 dangling_1st(std::ranges::find_last_if, in, unary_pred); 122 dangling_1st(std::ranges::find_last_if_not, in, unary_pred); 123 #endif 124 dangling_1st(std::ranges::find_first_of, in, in2); 125 dangling_1st(std::ranges::adjacent_find, in); 126 dangling_1st<mismatch_result<dangling, InIter>>(std::ranges::mismatch, in, in2); 127 dangling_2nd<mismatch_result<InIter, dangling>>(std::ranges::mismatch, in, in2); 128 dangling_both<mismatch_result<dangling, dangling>>(std::ranges::mismatch, in, in2); 129 dangling_1st(std::ranges::partition_point, in, unary_pred); 130 dangling_1st(std::ranges::lower_bound, in, x); 131 dangling_1st(std::ranges::upper_bound, in, x); 132 dangling_1st(std::ranges::equal_range, in, x); 133 dangling_1st(std::ranges::min_element, in); 134 dangling_1st(std::ranges::max_element, in); 135 dangling_1st<minmax_result<dangling>>(std::ranges::minmax_element, in); 136 dangling_1st(std::ranges::search, in, in2); 137 dangling_1st(std::ranges::search_n, in, count, x); 138 dangling_1st(std::ranges::find_end, in, in2); 139 dangling_1st(std::ranges::is_sorted_until, in); 140 dangling_1st(std::ranges::is_heap_until, in); 141 dangling_1st<for_each_result<dangling, decltype(unary_pred)>>(std::ranges::for_each, in, unary_pred); 142 dangling_1st<copy_result<dangling, OutIter>>(std::ranges::copy, in, out); 143 dangling_1st<copy_backward_result<dangling, OutIter>>(std::ranges::copy_backward, in, output.end()); 144 dangling_1st<copy_if_result<dangling, OutIter>>(std::ranges::copy_if, in, out, unary_pred); 145 dangling_1st<move_result<dangling, OutIter>>(std::ranges::move, in, out); 146 dangling_1st<move_backward_result<dangling, OutIter>>(std::ranges::move_backward, in, output.end()); 147 dangling_1st(std::ranges::fill, in, x); 148 { // transform 149 using OutTransformIter = std::array<bool, 3>::iterator; 150 std::array out_transform = {false, true, true}; 151 dangling_1st<unary_transform_result<dangling, OutTransformIter>>(std::ranges::transform, in, out_transform.begin(), unary_pred); 152 dangling_1st<binary_transform_result<dangling, InIter, OutTransformIter>>( 153 std::ranges::transform, in, in2, out_transform.begin(), binary_pred); 154 dangling_2nd<binary_transform_result<InIter, dangling, OutTransformIter>>( 155 std::ranges::transform, in, in2, out_transform.begin(), binary_pred); 156 dangling_both<binary_transform_result<dangling, dangling, OutTransformIter>>( 157 std::ranges::transform, in, in2, out_transform.begin(), binary_pred); 158 } 159 dangling_1st(std::ranges::generate, in, gen); 160 dangling_1st<remove_copy_result<dangling, OutIter>>(std::ranges::remove_copy, in, out, x); 161 dangling_1st<remove_copy_if_result<dangling, OutIter>>(std::ranges::remove_copy_if, in, out, unary_pred); 162 dangling_1st(std::ranges::replace, in, x, x); 163 dangling_1st(std::ranges::replace_if, in, std::identity{}, x); 164 dangling_1st<replace_copy_result<dangling, OutIter>>(std::ranges::replace_copy, in, out, x, x); 165 dangling_1st<replace_copy_if_result<dangling, OutIter>>(std::ranges::replace_copy_if, in, out, unary_pred, x); 166 dangling_1st<swap_ranges_result<dangling, InIter>>(std::ranges::swap_ranges, in, in2); 167 dangling_2nd<swap_ranges_result<InIter, dangling>>(std::ranges::swap_ranges, in, in2); 168 dangling_both<swap_ranges_result<dangling, dangling>>(std::ranges::swap_ranges, in, in2); 169 dangling_1st<reverse_copy_result<dangling, OutIter>>(std::ranges::reverse_copy, in, out); 170 dangling_1st<rotate_copy_result<dangling, OutIter>>(std::ranges::rotate_copy, in, mid, out); 171 dangling_1st<unique_copy_result<dangling, OutIter>>(std::ranges::unique_copy, in, out); 172 dangling_1st<partition_copy_result<dangling, OutIter, OutIter>>(std::ranges::partition_copy, in, out, out2, unary_pred); 173 dangling_1st<partial_sort_copy_result<dangling, InIter>>(std::ranges::partial_sort_copy, in, in2); 174 dangling_2nd<partial_sort_copy_result<InIter, dangling>>(std::ranges::partial_sort_copy, in, in2); 175 dangling_both<partial_sort_copy_result<dangling, dangling>>(std::ranges::partial_sort_copy, in, in2); 176 dangling_1st<merge_result<dangling, InIter, OutIter>>(std::ranges::merge, in, in2, out); 177 dangling_2nd<merge_result<InIter, dangling, OutIter>>(std::ranges::merge, in, in2, out); 178 dangling_both<merge_result<dangling, dangling, OutIter>>(std::ranges::merge, in, in2, out); 179 dangling_1st<set_difference_result<dangling, OutIter>>(std::ranges::set_difference, in, in2, out); 180 dangling_1st<set_intersection_result<dangling, InIter, OutIter>>(std::ranges::set_intersection, in, in2, out); 181 dangling_2nd<set_intersection_result<InIter, dangling, OutIter>>(std::ranges::set_intersection, in, in2, out); 182 dangling_both<set_intersection_result<dangling, dangling, OutIter>>(std::ranges::set_intersection, in, in2, out); 183 dangling_1st<set_symmetric_difference_result<dangling, InIter, OutIter>>( 184 std::ranges::set_symmetric_difference, in, in2, out); 185 dangling_2nd<set_symmetric_difference_result<InIter, dangling, OutIter>>( 186 std::ranges::set_symmetric_difference, in, in2, out); 187 dangling_both<set_symmetric_difference_result<dangling, dangling, OutIter>>( 188 std::ranges::set_symmetric_difference, in, in2, out); 189 dangling_1st<set_union_result<dangling, InIter, OutIter>>(std::ranges::set_union, in, in2, out); 190 dangling_2nd<set_union_result<InIter, dangling, OutIter>>(std::ranges::set_union, in, in2, out); 191 dangling_both<set_union_result<dangling, dangling, OutIter>>(std::ranges::set_union, in, in2, out); 192 dangling_1st(std::ranges::remove, in, x); 193 dangling_1st(std::ranges::remove_if, in, unary_pred); 194 dangling_1st(std::ranges::reverse, in); 195 dangling_1st(std::ranges::rotate, in, mid); 196 if (!std::is_constant_evaluated()) // `shuffle` isn't `constexpr`. 197 dangling_1st(std::ranges::shuffle, in, rand_gen()); 198 dangling_1st(std::ranges::unique, in); 199 dangling_1st(std::ranges::partition, in, unary_pred); 200 if (!std::is_constant_evaluated()) 201 dangling_1st(std::ranges::stable_partition, in, unary_pred); 202 dangling_1st(std::ranges::sort, in); 203 if (!std::is_constant_evaluated()) 204 dangling_1st(std::ranges::stable_sort, in); 205 dangling_1st(std::ranges::partial_sort, in, mid); 206 dangling_1st(std::ranges::nth_element, in, mid); 207 if (!std::is_constant_evaluated()) 208 dangling_1st(std::ranges::inplace_merge, in, mid); 209 dangling_1st(std::ranges::make_heap, in); 210 dangling_1st(std::ranges::push_heap, in); 211 dangling_1st(std::ranges::pop_heap, in); 212 dangling_1st(std::ranges::make_heap, in); 213 dangling_1st(std::ranges::sort_heap, in); 214 dangling_1st<prev_permutation_result<dangling>>(std::ranges::prev_permutation, in); 215 dangling_1st<next_permutation_result<dangling>>(std::ranges::next_permutation, in); 216 217 return true; 218 } 219 220 int main(int, char**) { 221 test_all(); 222 static_assert(test_all()); 223 224 return 0; 225 } 226