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_ASSOCIATIVE_CONTAINERS_H 10 #define SUPPORT_FROM_RANGE_ASSOCIATIVE_CONTAINERS_H 11 12 #include <algorithm> 13 #include <cassert> 14 #include <cstddef> 15 #include <ranges> 16 #include <vector> 17 #include <utility> 18 19 #include "../exception_safety_helpers.h" 20 #include "../from_range_helpers.h" 21 #include "../test_compare.h" 22 #include "MoveOnly.h" 23 #include "almost_satisfies_types.h" 24 #include "count_new.h" 25 #include "test_macros.h" 26 27 template <class Container, class Range> 28 concept HasFromRangeCtr = requires (Range&& range) { 29 Container(std::from_range, std::forward<Range>(range)); 30 Container(std::from_range, std::forward<Range>(range), std::less<typename Container::key_type>()); 31 Container(std::from_range, std::forward<Range>(range), std::less<typename Container::key_type>(), 32 std::allocator<typename Container::value_type>()); 33 Container(std::from_range, std::forward<Range>(range), std::allocator<typename Container::value_type>()); 34 }; 35 36 template <template <class...> class Container, class K, class V, class K2, class V2> 37 constexpr bool test_map_constraints() { 38 using ValueType = std::pair<const K, V>; 39 40 // Input range with the same value type. 41 static_assert(HasFromRangeCtr<Container<K, V>, InputRange<ValueType>>); 42 // Input range with a convertible value type. 43 static_assert(HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const K2, V2>>>); 44 // Input range with a non-convertible value type. 45 static_assert(!HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const Empty, V>>>); 46 static_assert(!HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const K, Empty>>>); 47 // Not an input range. 48 static_assert(!HasFromRangeCtr<Container<K, V>, InputRangeNotDerivedFromGeneric<ValueType>>); 49 50 return true; 51 } 52 53 template <template <class ...> class Container, 54 class K, 55 class V, 56 class Iter, 57 class Sent, 58 class Comp, 59 class Alloc, 60 class ValueType = std::pair<const K, V>> 61 void test_associative_map_with_input(std::vector<ValueType>&& input) { 62 { // (range) 63 auto in = wrap_input<Iter, Sent>(input); 64 Container<K, V> c(std::from_range, in); 65 66 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 67 assert(std::ranges::is_permutation(input, c)); 68 } 69 70 { // (range, comp) 71 auto in = wrap_input<Iter, Sent>(input); 72 Comp comp; 73 Container<K, V, Comp> c(std::from_range, in, comp); 74 75 assert(c.key_comp() == comp); 76 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 77 assert(std::ranges::is_permutation(input, c)); 78 } 79 80 { // (range, allocator) 81 auto in = wrap_input<Iter, Sent>(input); 82 Alloc alloc; 83 Container<K, V, std::less<K>, Alloc> c(std::from_range, in, alloc); 84 85 assert(c.get_allocator() == alloc); 86 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 87 assert(std::ranges::is_permutation(input, c)); 88 } 89 90 { // (range, comp, allocator) 91 auto in = wrap_input<Iter, Sent>(input); 92 Comp comp; 93 Alloc alloc; 94 Container<K, V, Comp, Alloc> c(std::from_range, in, comp, alloc); 95 96 assert(c.key_comp() == comp); 97 assert(c.get_allocator() == alloc); 98 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 99 assert(std::ranges::is_permutation(input, c)); 100 } 101 } 102 103 template <template <class ...> class Container, 104 class K, 105 class V, 106 class Iter, 107 class Sent, 108 class Comp, 109 class Alloc> 110 void test_associative_map() { 111 auto test_with_input = &test_associative_map_with_input<Container, K, V, Iter, Sent, Comp, Alloc>; 112 113 // Normal input. 114 test_with_input({{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}}); 115 // Empty input. 116 test_with_input({}); 117 // Single-element input. 118 test_with_input({{1, 2}}); 119 } 120 121 template <template <class ...> class Container> 122 void test_associative_map_move_only() { 123 std::pair<const int, MoveOnly> input[5]; 124 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5}); 125 126 [[maybe_unused]] Container<int, MoveOnly> c(std::from_range, in); 127 } 128 129 template <template <class ...> class Container> 130 void test_map_exception_safety_throwing_copy() { 131 #if !defined(TEST_HAS_NO_EXCEPTIONS) 132 using K = int; 133 using V = ThrowingCopy<3>; 134 135 V::throwing_enabled = false; 136 std::pair<const K, V> in[5] = { 137 {1, {}}, {2, {}}, {3, {}}, {4, {}}, {5, {}} 138 }; 139 V::throwing_enabled = true; 140 V::reset(); 141 142 try { 143 Container<K, V> c(std::from_range, in); 144 assert(false); // The constructor call above should throw. 145 146 } catch (int) { 147 assert(V::created_by_copying == 3); 148 assert(V::destroyed == 2); // No destructor call for the partially-constructed element. 149 } 150 #endif 151 } 152 153 template <template <class ...> class Container, class K, class V> 154 void test_map_exception_safety_throwing_allocator() { 155 #if !defined(TEST_HAS_NO_EXCEPTIONS) 156 using ValueType = std::pair<const K, V>; 157 ValueType in[] = { 158 ValueType{K{1}, V{1}} 159 }; 160 161 try { 162 ThrowingAllocator<ValueType> alloc; 163 164 globalMemCounter.reset(); 165 Container<K, V, test_less<K>, ThrowingAllocator<ValueType>> c(std::from_range, in, alloc); 166 assert(false); // The constructor call above should throw. 167 168 } catch (int) { 169 assert(globalMemCounter.new_called == globalMemCounter.delete_called); 170 } 171 #endif 172 } 173 174 template <class Container, class Range> 175 concept SetHasFromRangeCtr = requires (Range&& range) { 176 Container(std::from_range, std::forward<Range>(range)); 177 Container(std::from_range, std::forward<Range>(range), std::less<typename Container::value_type>()); 178 Container(std::from_range, std::forward<Range>(range), std::less<typename Container::value_type>(), 179 std::allocator<typename Container::value_type>()); 180 Container(std::from_range, std::forward<Range>(range), std::allocator<typename Container::value_type>()); 181 }; 182 183 template <template <class...> class Container, class T, class U> 184 constexpr bool test_set_constraints() { 185 // Input range with the same value type. 186 static_assert(SetHasFromRangeCtr<Container<T>, InputRange<T>>); 187 // Input range with a convertible value type. 188 static_assert(SetHasFromRangeCtr<Container<T>, InputRange<U>>); 189 // Input range with a non-convertible value type. 190 static_assert(!SetHasFromRangeCtr<Container<T>, InputRange<Empty>>); 191 // Not an input range. 192 static_assert(!SetHasFromRangeCtr<Container<T>, InputRangeNotDerivedFromGeneric<T>>); 193 194 return true; 195 } 196 197 template <template <class ...> class Container, 198 class T, 199 class Iter, 200 class Sent, 201 class Comp, 202 class Alloc> 203 void test_associative_set_with_input(std::vector<T>&& input) { 204 { // (range) 205 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 206 Container<T> c(std::from_range, in); 207 208 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 209 assert(std::ranges::is_permutation(input, c)); 210 } 211 212 { // (range, comp) 213 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 214 Comp comp; 215 Container<T, Comp> c(std::from_range, in, comp); 216 217 assert(c.key_comp() == comp); 218 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 219 assert(std::ranges::is_permutation(input, c)); 220 } 221 222 { // (range, allocator) 223 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 224 Alloc alloc; 225 Container<T, std::less<T>, Alloc> c(std::from_range, in, alloc); 226 227 assert(c.get_allocator() == alloc); 228 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 229 assert(std::ranges::is_permutation(input, c)); 230 } 231 232 { // (range, comp, allocator) 233 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 234 Comp comp; 235 Alloc alloc; 236 Container<T, Comp, Alloc> c(std::from_range, in, comp, alloc); 237 238 assert(c.key_comp() == comp); 239 assert(c.get_allocator() == alloc); 240 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 241 assert(std::ranges::is_permutation(input, c)); 242 } 243 } 244 245 template <template <class ...> class Container, 246 class T, 247 class Iter, 248 class Sent, 249 class Comp, 250 class Alloc> 251 void test_associative_set() { 252 auto test_with_input = &test_associative_set_with_input<Container, T, Iter, Sent, Comp, Alloc>; 253 254 // Normal input. 255 test_with_input({0, 5, 12, 7, -1, 8, 26}); 256 // Empty input. 257 test_with_input({}); 258 // Single-element input. 259 test_with_input({5}); 260 } 261 262 template <template <class ...> class Container> 263 void test_associative_set_move_only() { 264 MoveOnly input[5]; 265 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5}); 266 267 [[maybe_unused]] Container<MoveOnly> c(std::from_range, in); 268 } 269 270 template <template <class ...> class Container> 271 void test_set_exception_safety_throwing_copy() { 272 #if !defined(TEST_HAS_NO_EXCEPTIONS) 273 using T = ThrowingCopy<3>; 274 T::reset(); 275 T in[5] = {{1}, {2}, {3}, {4}, {5}}; 276 277 try { 278 Container<T> c(std::from_range, in); 279 assert(false); // The constructor call above should throw. 280 281 } catch (int) { 282 assert(T::created_by_copying == 3); 283 assert(T::destroyed == 2); // No destructor call for the partially-constructed element. 284 } 285 #endif 286 } 287 288 template <template <class ...> class Container, class T> 289 void test_set_exception_safety_throwing_allocator() { 290 #if !defined(TEST_HAS_NO_EXCEPTIONS) 291 T in[] = {1, 2}; 292 293 try { 294 ThrowingAllocator<T> alloc; 295 296 globalMemCounter.reset(); 297 Container<T, test_less<T>, ThrowingAllocator<T>> c(std::from_range, in, alloc); 298 assert(false); // The constructor call above should throw. 299 300 } catch (int) { 301 assert(globalMemCounter.new_called == globalMemCounter.delete_called); 302 } 303 #endif 304 } 305 306 #endif // SUPPORT_FROM_RANGE_ASSOCIATIVE_CONTAINERS_H 307