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
27struct 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
41using R = NonBorrowedRange;
42
43// (dangling_in, ...)
44template <class ExpectedT = std::ranges::dangling, class Func, std::ranges::range Input, class ...Args>
45constexpr 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, ...)
51template <class ExpectedT = std::ranges::dangling, class Func, std::ranges::range Input, class ...Args>
52constexpr 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, ...)
58template <class ExpectedT = std::ranges::dangling, class Func, std::ranges::range Input, class ...Args>
59constexpr 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
64std::mt19937 rand_gen() { return std::mt19937(); }
65
66// TODO: also check the iterator values for algorithms that return `*_result` types.
67constexpr 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 dangling_1st(std::ranges::find_first_of, in, in2);
120 dangling_1st(std::ranges::adjacent_find, in);
121 dangling_1st<mismatch_result<dangling, InIter>>(std::ranges::mismatch, in, in2);
122 dangling_2nd<mismatch_result<InIter, dangling>>(std::ranges::mismatch, in, in2);
123 dangling_both<mismatch_result<dangling, dangling>>(std::ranges::mismatch, in, in2);
124 dangling_1st(std::ranges::partition_point, in, unary_pred);
125 dangling_1st(std::ranges::lower_bound, in, x);
126 dangling_1st(std::ranges::upper_bound, in, x);
127 dangling_1st(std::ranges::equal_range, in, x);
128 dangling_1st(std::ranges::min_element, in);
129 dangling_1st(std::ranges::max_element, in);
130 dangling_1st<minmax_result<dangling>>(std::ranges::minmax_element, in);
131 dangling_1st(std::ranges::search, in, in2);
132 dangling_1st(std::ranges::search_n, in, count, x);
133 dangling_1st(std::ranges::find_end, in, in2);
134 dangling_1st(std::ranges::is_sorted_until, in);
135 dangling_1st(std::ranges::is_heap_until, in);
136 dangling_1st<for_each_result<dangling, decltype(unary_pred)>>(std::ranges::for_each, in, unary_pred);
137 dangling_1st<copy_result<dangling, OutIter>>(std::ranges::copy, in, out);
138 dangling_1st<copy_backward_result<dangling, OutIter>>(std::ranges::copy_backward, in, output.end());
139 dangling_1st<copy_if_result<dangling, OutIter>>(std::ranges::copy_if, in, out, unary_pred);
140 dangling_1st<move_result<dangling, OutIter>>(std::ranges::move, in, out);
141 dangling_1st<move_backward_result<dangling, OutIter>>(std::ranges::move_backward, in, output.end());
142 dangling_1st(std::ranges::fill, in, x);
143 { // transform
144 using OutTransformIter = std::array<bool, 3>::iterator;
145 std::array out_transform = {false, true, true};
146 dangling_1st<unary_transform_result<dangling, OutTransformIter>>(std::ranges::transform, in, out_transform.begin(), unary_pred);
147 dangling_1st<binary_transform_result<dangling, InIter, OutTransformIter>>(
148 std::ranges::transform, in, in2, out_transform.begin(), binary_pred);
149 dangling_2nd<binary_transform_result<InIter, dangling, OutTransformIter>>(
150 std::ranges::transform, in, in2, out_transform.begin(), binary_pred);
151 dangling_both<binary_transform_result<dangling, dangling, OutTransformIter>>(
152 std::ranges::transform, in, in2, out_transform.begin(), binary_pred);
153 }
154 dangling_1st(std::ranges::generate, in, gen);
155 dangling_1st<remove_copy_result<dangling, OutIter>>(std::ranges::remove_copy, in, out, x);
156 dangling_1st<remove_copy_if_result<dangling, OutIter>>(std::ranges::remove_copy_if, in, out, unary_pred);
157 dangling_1st(std::ranges::replace, in, x, x);
158 dangling_1st(std::ranges::replace_if, in, std::identity{}, x);
159 dangling_1st<replace_copy_result<dangling, OutIter>>(std::ranges::replace_copy, in, out, x, x);
160 dangling_1st<replace_copy_if_result<dangling, OutIter>>(std::ranges::replace_copy_if, in, out, unary_pred, x);
161 dangling_1st<swap_ranges_result<dangling, InIter>>(std::ranges::swap_ranges, in, in2);
162 dangling_2nd<swap_ranges_result<InIter, dangling>>(std::ranges::swap_ranges, in, in2);
163 dangling_both<swap_ranges_result<dangling, dangling>>(std::ranges::swap_ranges, in, in2);
164 dangling_1st<reverse_copy_result<dangling, OutIter>>(std::ranges::reverse_copy, in, out);
165 dangling_1st<rotate_copy_result<dangling, OutIter>>(std::ranges::rotate_copy, in, mid, out);
166 dangling_1st<unique_copy_result<dangling, OutIter>>(std::ranges::unique_copy, in, out);
167 dangling_1st<partition_copy_result<dangling, OutIter, OutIter>>(std::ranges::partition_copy, in, out, out2, unary_pred);
168 dangling_1st<partial_sort_copy_result<dangling, InIter>>(std::ranges::partial_sort_copy, in, in2);
169 dangling_2nd<partial_sort_copy_result<InIter, dangling>>(std::ranges::partial_sort_copy, in, in2);
170 dangling_both<partial_sort_copy_result<dangling, dangling>>(std::ranges::partial_sort_copy, in, in2);
171 dangling_1st<merge_result<dangling, InIter, OutIter>>(std::ranges::merge, in, in2, out);
172 dangling_2nd<merge_result<InIter, dangling, OutIter>>(std::ranges::merge, in, in2, out);
173 dangling_both<merge_result<dangling, dangling, OutIter>>(std::ranges::merge, in, in2, out);
174 dangling_1st<set_difference_result<dangling, OutIter>>(std::ranges::set_difference, in, in2, out);
175 dangling_1st<set_intersection_result<dangling, InIter, OutIter>>(std::ranges::set_intersection, in, in2, out);
176 dangling_2nd<set_intersection_result<InIter, dangling, OutIter>>(std::ranges::set_intersection, in, in2, out);
177 dangling_both<set_intersection_result<dangling, dangling, OutIter>>(std::ranges::set_intersection, in, in2, out);
178 dangling_1st<set_symmetric_difference_result<dangling, InIter, OutIter>>(
179 std::ranges::set_symmetric_difference, in, in2, out);
180 dangling_2nd<set_symmetric_difference_result<InIter, dangling, OutIter>>(
181 std::ranges::set_symmetric_difference, in, in2, out);
182 dangling_both<set_symmetric_difference_result<dangling, dangling, OutIter>>(
183 std::ranges::set_symmetric_difference, in, in2, out);
184 dangling_1st<set_union_result<dangling, InIter, OutIter>>(std::ranges::set_union, in, in2, out);
185 dangling_2nd<set_union_result<InIter, dangling, OutIter>>(std::ranges::set_union, in, in2, out);
186 dangling_both<set_union_result<dangling, dangling, OutIter>>(std::ranges::set_union, in, in2, out);
187 dangling_1st(std::ranges::remove, in, x);
188 dangling_1st(std::ranges::remove_if, in, unary_pred);
189 dangling_1st(std::ranges::reverse, in);
190 dangling_1st(std::ranges::rotate, in, mid);
191 if (!std::is_constant_evaluated()) // `shuffle` isn't `constexpr`.
192 dangling_1st(std::ranges::shuffle, in, rand_gen());
193 dangling_1st(std::ranges::unique, in);
194 dangling_1st(std::ranges::partition, in, unary_pred);
195 if (!std::is_constant_evaluated())
196 dangling_1st(std::ranges::stable_partition, in, unary_pred);
197 dangling_1st(std::ranges::sort, in);
198 if (!std::is_constant_evaluated())
199 dangling_1st(std::ranges::stable_sort, in);
200 dangling_1st(std::ranges::partial_sort, in, mid);
201 dangling_1st(std::ranges::nth_element, in, mid);
202 if (!std::is_constant_evaluated())
203 dangling_1st(std::ranges::inplace_merge, in, mid);
204 dangling_1st(std::ranges::make_heap, in);
205 dangling_1st(std::ranges::push_heap, in);
206 dangling_1st(std::ranges::pop_heap, in);
207 dangling_1st(std::ranges::make_heap, in);
208 dangling_1st(std::ranges::sort_heap, in);
209 dangling_1st<prev_permutation_result<dangling>>(std::ranges::prev_permutation, in);
210 dangling_1st<next_permutation_result<dangling>>(std::ranges::next_permutation, in);
211
212 return true;
213}
214
215int main(int, char**) {
216 test_all();
217 static_assert(test_all());
218
219 return 0;
220}
221

source code of libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp