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