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 #ifndef SUPPORT_FROM_RANGE_CONTAINER_ADAPTORS_H 10 #define SUPPORT_FROM_RANGE_CONTAINER_ADAPTORS_H 11 12 #include <algorithm> 13 #include <cassert> 14 #include <cstddef> 15 #include <queue> 16 #include <ranges> 17 #include <utility> 18 #include <vector> 19 20 #include "../exception_safety_helpers.h" 21 #include "../from_range_helpers.h" 22 #include "MoveOnly.h" 23 #include "almost_satisfies_types.h" 24 #include "count_new.h" 25 #include "test_macros.h" 26 #include "unwrap_container_adaptor.h" 27 28 template <class Container, class Range> 29 concept HasFromRangeCtr = requires (Range&& range) { 30 Container(std::from_range, std::forward<Range>(range)); 31 Container(std::from_range, std::forward<Range>(range), std::allocator<typename Container::value_type>()); 32 }; 33 34 template <template <class...> class Container, class T, class U> 35 constexpr bool test_constraints() { 36 // Input range with the same value type. 37 static_assert(HasFromRangeCtr<Container<T>, InputRange<T>>); 38 // Input range with a convertible value type. 39 static_assert(HasFromRangeCtr<Container<T>, InputRange<U>>); 40 // Input range with a non-convertible value type. 41 static_assert(!HasFromRangeCtr<Container<T>, InputRange<Empty>>); 42 // Not an input range. 43 static_assert(!HasFromRangeCtr<Container<T>, InputRangeNotDerivedFrom>); 44 static_assert(!HasFromRangeCtr<Container<T>, InputRangeNotIndirectlyReadable>); 45 static_assert(!HasFromRangeCtr<Container<T>, InputRangeNotInputOrOutputIterator>); 46 47 return true; 48 } 49 50 template <template <class ...> class Adaptor, 51 template <class ...> class UnderlyingContainer, 52 class T, 53 class Iter, 54 class Sent, 55 class Alloc> 56 constexpr void test_container_adaptor_with_input(std::vector<T>&& input) { 57 { // (range) 58 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 59 Adaptor<T> adaptor(std::from_range, in); 60 UnwrapAdaptor<Adaptor<T>> unwrap_adaptor(std::move(adaptor)); 61 auto& c = unwrap_adaptor.get_container(); 62 63 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 64 assert(std::ranges::equal(input, c)); 65 LIBCPP_ASSERT(c.__invariants()); 66 } 67 68 { // (range, allocator) 69 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 70 using C = UnderlyingContainer<T, Alloc>; 71 Alloc alloc; 72 Adaptor<T, C> adaptor(std::from_range, in, alloc); 73 UnwrapAdaptor<Adaptor<T, C>> unwrap_adaptor(std::move(adaptor)); 74 auto& c = unwrap_adaptor.get_container(); 75 76 assert(c.get_allocator() == alloc); 77 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 78 assert(std::ranges::equal(input, c)); 79 LIBCPP_ASSERT(c.__invariants()); 80 } 81 } 82 83 template <template <class ...> class UnderlyingContainer, 84 class T, 85 class Iter, 86 class Sent, 87 class Comp, 88 class Alloc> 89 constexpr void test_priority_queue_with_input(std::vector<T>&& input) { 90 { // (range) 91 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 92 std::priority_queue<T> adaptor(std::from_range, in); 93 UnwrapAdaptor<std::priority_queue<T>> unwrap_adaptor(std::move(adaptor)); 94 auto& c = unwrap_adaptor.get_container(); 95 96 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 97 assert(std::ranges::is_permutation(input, c)); 98 LIBCPP_ASSERT(c.__invariants()); 99 } 100 101 { // (range, comp) 102 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 103 using C = UnderlyingContainer<T>; 104 Comp comp; 105 106 std::priority_queue<T, C, Comp> adaptor(std::from_range, in, comp); 107 UnwrapAdaptor<std::priority_queue<T, C, Comp>> unwrap_adaptor(std::move(adaptor)); 108 auto& c = unwrap_adaptor.get_container(); 109 110 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 111 assert(std::ranges::is_permutation(input, c)); 112 LIBCPP_ASSERT(c.__invariants()); 113 assert(unwrap_adaptor.get_comparator() == comp); 114 } 115 116 { // (range, allocator) 117 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 118 using C = UnderlyingContainer<T, Alloc>; 119 Alloc alloc; 120 121 std::priority_queue<T, C> adaptor(std::from_range, in, alloc); 122 UnwrapAdaptor<std::priority_queue<T, C>> unwrap_adaptor(std::move(adaptor)); 123 auto& c = unwrap_adaptor.get_container(); 124 125 assert(c.get_allocator() == alloc); 126 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 127 assert(std::ranges::is_permutation(input, c)); 128 LIBCPP_ASSERT(c.__invariants()); 129 } 130 131 { // (range, comp, alloc) 132 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 133 using C = UnderlyingContainer<T, Alloc>; 134 Comp comp; 135 Alloc alloc; 136 137 std::priority_queue<T, C, Comp> adaptor(std::from_range, in, comp, alloc); 138 UnwrapAdaptor<std::priority_queue<T, C, Comp>> unwrap_adaptor(std::move(adaptor)); 139 auto& c = unwrap_adaptor.get_container(); 140 141 assert(c.get_allocator() == alloc); 142 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 143 assert(std::ranges::is_permutation(input, c)); 144 LIBCPP_ASSERT(c.__invariants()); 145 assert(unwrap_adaptor.get_comparator() == comp); 146 } 147 } 148 149 template <template <class ...> class Adaptor, 150 template <class ...> class UnderlyingContainer, 151 class T, 152 class Iter, 153 class Sent, 154 class Alloc> 155 constexpr void test_container_adaptor() { 156 auto test_with_input = &test_container_adaptor_with_input<Adaptor, UnderlyingContainer, T, Iter, Sent, Alloc>; 157 158 // Normal input. 159 test_with_input({0, 5, 12, 7, -1, 8, 26}); 160 // Empty input. 161 test_with_input({}); 162 // Single-element input. 163 test_with_input({5}); 164 } 165 166 template <template <class ...> class UnderlyingContainer, 167 class T, 168 class Iter, 169 class Sent, 170 class Comp, 171 class Alloc> 172 constexpr void test_priority_queue() { 173 auto test_with_input = &test_priority_queue_with_input<UnderlyingContainer, T, Iter, Sent, Comp, Alloc>; 174 175 // Normal input. 176 test_with_input({0, 5, 12, 7, -1, 8, 26}); 177 // Empty input. 178 test_with_input({}); 179 // Single-element input. 180 test_with_input({5}); 181 } 182 183 template <template <class ...> class Container> 184 constexpr void test_container_adaptor_move_only() { 185 MoveOnly input[5]; 186 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5}); 187 188 [[maybe_unused]] Container<MoveOnly> c(std::from_range, in); 189 } 190 191 template <template <class ...> class Adaptor> 192 void test_exception_safety_throwing_copy() { 193 #if !defined(TEST_HAS_NO_EXCEPTIONS) 194 constexpr int ThrowOn = 3; 195 using T = ThrowingCopy<ThrowOn>; 196 test_exception_safety_throwing_copy<ThrowOn, /*Size=*/5>([](T* from, T* to) { 197 [[maybe_unused]] Adaptor<T, std::vector<T>> c(std::from_range, std::ranges::subrange(from, to)); 198 }); 199 #endif 200 } 201 202 template <template <class ...> class Adaptor, class T> 203 void test_exception_safety_throwing_allocator() { 204 #if !defined(TEST_HAS_NO_EXCEPTIONS) 205 T in[] = {0, 1}; 206 207 try { 208 using C = std::vector<T, ThrowingAllocator<T>>; 209 ThrowingAllocator<T> alloc; 210 211 globalMemCounter.reset(); 212 Adaptor<T, C> c(std::from_range, in, alloc); 213 assert(false); // The constructor call should throw. 214 215 } catch (int) { 216 assert(globalMemCounter.new_called == globalMemCounter.delete_called); 217 } 218 #endif 219 } 220 221 #endif // SUPPORT_FROM_RANGE_CONTAINER_ADAPTORS_H 222