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