libcxx/test/std/containers/insert_range_maps_sets.h

   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_INSERT_RANGE_MAPS_SETS_H
  10 #define SUPPORT_INSERT_RANGE_MAPS_SETS_H
  11
  12 #include <algorithm>
  13 #include <array>
  14 #include <cassert>
  15 #include <concepts>
  16 #include <ranges>
  17 #include <type_traits>
  18 #include <vector>
  19
  20 #include "MoveOnly.h"
  21 #include "almost_satisfies_types.h"
  22 #include "count_new.h"
  23 #include "exception_safety_helpers.h"
  24 #include "insert_range_helpers.h"
  25 #include "min_allocator.h"
  26 #include "test_allocator.h"
  27 #include "test_compare.h"
  28 #include "test_hash.h"
  29 #include "test_iterators.h"
  30 #include "test_macros.h"
  31 #include "type_algorithms.h"
  32
  33 template <class Container, class Range>
  34 concept HasInsertRange = requires (Container& c, Range&& range) {
  35   c.insert_range(range);
  36 };
  37
  38 template <template <class...> class Container, class T, class U>
  39 constexpr bool test_set_constraints_insert_range() {
  40   // Input range with the same value type.
  41   static_assert(HasInsertRange<Container<T>, InputRange<T>>);
  42   // Input range with a convertible value type.
  43   static_assert(HasInsertRange<Container<T>, InputRange<U>>);
  44   // Input range with a non-convertible value type.
  45   static_assert(!HasInsertRange<Container<T>, InputRange<Empty>>);
  46   // Not an input range.
  47   static_assert(!HasInsertRange<Container<T>, InputRangeNotDerivedFrom>);
  48   static_assert(!HasInsertRange<Container<T>, InputRangeNotIndirectlyReadable>);
  49   static_assert(!HasInsertRange<Container<T>, InputRangeNotInputOrOutputIterator>);
  50
  51   return true;
  52 }
  53
  54 template <template <class...> class Container, class K, class V, class K2, class V2>
  55 constexpr bool test_map_constraints_insert_range() {
  56   using ValueType = std::pair<const K, V>;
  57
  58   // Input range with the same value type.
  59   static_assert(HasInsertRange<Container<K, V>, InputRange<ValueType>>);
  60   // Input range with a convertible value type.
  61   static_assert(HasInsertRange<Container<K, V>, InputRange<std::pair<const K2, V2>>>);
  62   // Input range with a non-convertible value type.
  63   static_assert(!HasInsertRange<Container<K, V>, InputRange<std::pair<const K, Empty>>>);
  64   static_assert(!HasInsertRange<Container<K, V>, InputRange<std::pair<const Empty, V>>>);
  65   // Not an input range.
  66   static_assert(!HasInsertRange<Container<K, V>, InputRangeNotDerivedFromGeneric<ValueType>>);
  67
  68   return true;
  69 }
  70
  71 template <class T>
  72 struct TestCaseMapSet {
  73   Buffer<T> initial;
  74   Buffer<T> input;
  75   Buffer<T> expected;
  76   Buffer<T> expected_multi;
  77 };
  78
  79 // Empty container.
  80
  81 template <class T>
  82 TestCaseMapSet<T> constexpr EmptyContainer_EmptyRange {
  83   .initial = {}, .input = {}, .expected = {}
  84 };
  85
  86 template <class T>
  87 TestCaseMapSet<T> constexpr EmptyContainer_OneElementRange {
  88   .initial = {}, .input = {1}, .expected = {1}
  89 };
  90 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
  91 constexpr EmptyContainer_OneElementRange<std::pair<K, V>> {
  92   .initial = {}, .input = {{1, 'a'}}, .expected = {{1, 'a'}}
  93 };
  94
  95 template <class T>
  96 TestCaseMapSet<T> constexpr EmptyContainer_RangeNoDuplicates {
  97   .initial = {}, .input = {5, 1, 3, 8, 6}, .expected = {5, 1, 3, 8, 6}
  98 };
  99 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
 100 constexpr EmptyContainer_RangeNoDuplicates<std::pair<K, V>> {
 101   .initial = {}, .input = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}},
 102   .expected = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}}
 103 };
 104
 105 template <class T>
 106 TestCaseMapSet<T> constexpr EmptyContainer_RangeWithDuplicates {
 107   .initial = {},
 108   .input = {5, 1, 1, 3, 5, 8, 5, 6, 10},
 109   .expected = {5, 1, 3, 8, 6, 10},
 110   .expected_multi = {5, 1, 1, 3, 5, 8, 5, 6, 10}
 111 };
 112 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
 113 constexpr EmptyContainer_RangeWithDuplicates<std::pair<K, V>> {
 114   .initial = {},
 115   .input = {{5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'b'}},
 116   .expected = {{5, 'a'}, {1, 'a'}, {3, 'a'}, {8, 'a'}, {6, 'a'}, {10, 'b'}},
 117   .expected_multi = {{5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'b'}}
 118 };
 119
 120 // One-element container.
 121
 122 template <class T>
 123 TestCaseMapSet<T> constexpr OneElementContainer_EmptyRange {
 124   .initial = {10}, .input = {}, .expected = {10}
 125 };
 126 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
 127 constexpr OneElementContainer_EmptyRange<std::pair<K, V>> {
 128   .initial = {{10, 'A'}}, .input = {}, .expected = {{10, 'A'}}
 129 };
 130
 131 template <class T>
 132 TestCaseMapSet<T> constexpr OneElementContainer_OneElementRange {
 133   .initial = {10}, .input = {1}, .expected = {1, 10}
 134 };
 135 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
 136 constexpr OneElementContainer_OneElementRange<std::pair<K, V>> {
 137   .initial = {{10, 'A'}}, .input = {{1, 'a'}}, .expected = {{1, 'a'}, {10, 'A'}}
 138 };
 139
 140 template <class T>
 141 TestCaseMapSet<T> constexpr OneElementContainer_RangeNoDuplicates {
 142   .initial = {10}, .input = {5, 1, 3, 8, 6}, .expected = {5, 1, 3, 8, 6, 10}
 143 };
 144 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
 145 constexpr OneElementContainer_RangeNoDuplicates<std::pair<K, V>> {
 146   .initial = {{10, 'A'}}, .input = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}},
 147   .expected = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}, {10, 'A'}}
 148 };
 149
 150 template <class T>
 151 TestCaseMapSet<T> constexpr OneElementContainer_RangeWithDuplicates {
 152   .initial = {10},
 153   .input = {5, 1, 1, 3, 5, 8, 5, 6, 10},
 154   .expected = {5, 1, 3, 8, 6, 10},
 155   .expected_multi = {5, 1, 1, 3, 5, 8, 5, 6, 10, 10}
 156 };
 157 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
 158 constexpr OneElementContainer_RangeWithDuplicates<std::pair<K, V>> {
 159   .initial = {{10, 'A'}},
 160   .input = {{5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'b'}},
 161   .expected = {{5, 'a'}, {1, 'a'}, {3, 'a'}, {8, 'a'}, {6, 'a'}, {10, 'A'}},
 162   .expected_multi = {
 163     {5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'A'}, {10, 'b'}
 164   }
 165 };
 166
 167 // N-elements container.
 168
 169 template <class T>
 170 TestCaseMapSet<T> constexpr NElementsContainer_EmptyRange {
 171   .initial = {10, 15, 19, 16}, .input = {}, .expected = {10, 15, 19, 16}
 172 };
 173 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
 174 constexpr NElementsContainer_EmptyRange<std::pair<K, V>> {
 175   .initial = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}, .input = {},
 176   .expected = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}
 177 };
 178
 179 template <class T>
 180 TestCaseMapSet<T> constexpr NElementsContainer_OneElementRange {
 181   .initial = {10, 15, 19, 16}, .input = {1}, .expected = {1, 10, 15, 19, 16}
 182 };
 183 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
 184 constexpr NElementsContainer_OneElementRange<std::pair<K, V>> {
 185   .initial = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}, .input = {{1, 'a'}},
 186   .expected = {{1, 'a'}, {10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}
 187 };
 188
 189 template <class T>
 190 TestCaseMapSet<T> constexpr NElementsContainer_RangeNoDuplicates {
 191   .initial = {10, 15, 19, 16}, .input = {5, 1, 3, 8, 6}, .expected = {5, 1, 3, 8, 6, 10, 15, 19, 16}
 192 };
 193 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
 194 constexpr NElementsContainer_RangeNoDuplicates<std::pair<K, V>> {
 195   .initial = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}},
 196   .input = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}},
 197   .expected = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}, {10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}
 198 };
 199
 200 template <class T>
 201 TestCaseMapSet<T> constexpr NElementsContainer_RangeWithDuplicates {
 202   .initial = {10, 15, 19, 16},
 203   .input = {5, 1, 1, 3, 5, 8, 5, 6, 10},
 204   .expected = {5, 1, 3, 8, 6, 10, 15, 19, 16},
 205   .expected_multi = {5, 1, 1, 3, 5, 8, 5, 6, 10, 10, 15, 19, 16}
 206 };
 207 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
 208 constexpr NElementsContainer_RangeWithDuplicates<std::pair<K, V>> {
 209   .initial = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}},
 210   .input = {{5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'b'}},
 211   .expected = {{5, 'a'}, {1, 'a'}, {3, 'a'}, {8, 'a'}, {6, 'a'}, {10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}},
 212   .expected_multi = {
 213     {5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'b'},
 214     {10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}
 215   }
 216 };
 217
 218 template <class Container, class T, class Iter, class Sent>
 219 void test_map_set_insert_range(bool allow_duplicates = false) {
 220   auto test = [&](const TestCaseMapSet<T>& test_case, bool check_multi = false) {
 221     Container c(test_case.initial.begin(), test_case.initial.end());
 222     auto in = wrap_input<Iter, Sent>(test_case.input);
 223
 224     c.insert_range(in);
 225     if (check_multi) {
 226       return std::ranges::is_permutation(c, test_case.expected_multi);
 227     } else {
 228       return std::ranges::is_permutation(c, test_case.expected);
 229     }
 230   };
 231
 232   { // Empty container.
 233     // empty_c.insert_range(empty_range)
 234     assert(test(EmptyContainer_EmptyRange<T>));
 235     // empty_c.insert_range(one_element_range)
 236     assert(test(EmptyContainer_OneElementRange<T>));
 237     // empty_c.insert_range(range_no_duplicates)
 238     assert(test(EmptyContainer_RangeNoDuplicates<T>));
 239     // empty_c.insert_range(range_with_duplicates)
 240     assert(test(EmptyContainer_RangeWithDuplicates<T>, allow_duplicates));
 241   }
 242
 243   { // One-element container.
 244     // one_element_c.insert_range(empty_range)
 245     assert(test(OneElementContainer_EmptyRange<T>));
 246     // one_element_c.insert_range(one_element_range)
 247     assert(test(OneElementContainer_OneElementRange<T>));
 248     // one_element_c.insert_range(range_no_duplicates)
 249     assert(test(OneElementContainer_RangeNoDuplicates<T>));
 250     // one_element_c.insert_range(range_with_duplicates)
 251     assert(test(OneElementContainer_RangeWithDuplicates<T>, allow_duplicates));
 252   }
 253
 254   { // N-elements container.
 255     // n_elements_c.insert_range(empty_range)
 256     assert(test(NElementsContainer_EmptyRange<T>));
 257     // n_elements_c.insert_range(one_element_range)
 258     assert(test(NElementsContainer_OneElementRange<T>));
 259     // n_elements_c.insert_range(range_no_duplicates)
 260     assert(test(NElementsContainer_RangeNoDuplicates<T>));
 261     // n_elements_c.insert_range(range_with_duplicates)
 262     assert(test(NElementsContainer_RangeWithDuplicates<T>, allow_duplicates));
 263   }
 264 }
 265
 266 // Move-only types.
 267
 268 template <template <class ...> class Container>
 269 void test_set_insert_range_move_only() {
 270   MoveOnly input[5];
 271   std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});
 272
 273   Container<MoveOnly> c;
 274   c.insert_range(in);
 275 }
 276
 277 template <template <class ...> class Container>
 278 void test_map_insert_range_move_only() {
 279   using Value = std::pair<const int, MoveOnly>;
 280   Value input[5];
 281   std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});
 282
 283   Container<int, MoveOnly> c;
 284   c.insert_range(in);
 285 }
 286
 287 // Exception safety.
 288
 289 template <template <class ...> class Container>
 290 void test_set_insert_range_exception_safety_throwing_copy() {
 291 #if !defined(TEST_HAS_NO_EXCEPTIONS)
 292   using T = ThrowingCopy<3>;
 293   T::reset();
 294   T in[5] = {{1}, {2}, {3}, {4}, {5}};
 295
 296   try {
 297     Container<T> c;
 298     c.insert_range(in);
 299     assert(false); // The constructor call above should throw.
 300
 301   } catch (int) {
 302     assert(T::created_by_copying == 3);
 303     assert(T::destroyed == 2); // No destructor call for the partially-constructed element.
 304   }
 305 #endif
 306 }
 307
 308 template <template <class ...> class Container>
 309 void test_map_insert_range_exception_safety_throwing_copy() {
 310 #if !defined(TEST_HAS_NO_EXCEPTIONS)
 311   using K = int;
 312   using V = ThrowingCopy<3>;
 313
 314   V::throwing_enabled = false;
 315   std::pair<const K, V> in[5] = {
 316     {1, {}}, {2, {}}, {3, {}}, {4, {}}, {5, {}}
 317   };
 318   V::throwing_enabled = true;
 319   V::reset();
 320
 321   try {
 322     Container<K, V> c;
 323     c.insert_range(in);
 324     assert(false); // The function call above should throw.
 325
 326   } catch (int) {
 327     assert(V::created_by_copying == 3);
 328     assert(V::destroyed == 2); // No destructor call for the partially-constructed element.
 329   }
 330 #endif
 331 }
 332
 333 template <template <class ...> class Container, class T>
 334 void test_assoc_set_insert_range_exception_safety_throwing_allocator() {
 335 #if !defined(TEST_HAS_NO_EXCEPTIONS)
 336   T in[] = {1, 2};
 337
 338   try {
 339     ThrowingAllocator<T> alloc;
 340
 341     globalMemCounter.reset();
 342     Container<T, test_less<T>, ThrowingAllocator<T>> c(alloc);
 343     c.insert_range(in);
 344     assert(false); // The function call above should throw.
 345
 346   } catch (int) {
 347     assert(globalMemCounter.new_called == globalMemCounter.delete_called);
 348   }
 349 #endif
 350 }
 351
 352 template <template <class ...> class Container, class T>
 353 void test_unord_set_insert_range_exception_safety_throwing_allocator() {
 354 #if !defined(TEST_HAS_NO_EXCEPTIONS)
 355   T in[] = {1, 2};
 356
 357   try {
 358     ThrowingAllocator<T> alloc;
 359
 360     globalMemCounter.reset();
 361     Container<T, test_hash<T>, test_equal_to<T>, ThrowingAllocator<T>> c(alloc);
 362     c.insert_range(in);
 363     assert(false); // The function call above should throw.
 364
 365   } catch (int) {
 366     assert(globalMemCounter.new_called == globalMemCounter.delete_called);
 367   }
 368 #endif
 369 }
 370
 371 template <template <class ...> class Container, class K, class V>
 372 void test_assoc_map_insert_range_exception_safety_throwing_allocator() {
 373 #if !defined(TEST_HAS_NO_EXCEPTIONS)
 374   using ValueType = std::pair<const K, V>;
 375   ValueType in[] = {
 376     ValueType{K{1}, V{1}}
 377   };
 378
 379   try {
 380     ThrowingAllocator<ValueType> alloc;
 381
 382     globalMemCounter.reset();
 383     Container<K, V, test_less<K>, ThrowingAllocator<ValueType>> c(alloc);
 384     c.insert_range(in);
 385     assert(false); // The function call above should throw.
 386
 387   } catch (int) {
 388     assert(globalMemCounter.new_called == globalMemCounter.delete_called);
 389   }
 390 #endif
 391 }
 392
 393 template <template <class ...> class Container, class K, class V>
 394 void test_unord_map_insert_range_exception_safety_throwing_allocator() {
 395 #if !defined(TEST_HAS_NO_EXCEPTIONS)
 396   using ValueType = std::pair<const K, V>;
 397   ValueType in[] = {
 398     ValueType{K{1}, V{1}}
 399   };
 400
 401   try {
 402     ThrowingAllocator<ValueType> alloc;
 403
 404     globalMemCounter.reset();
 405     Container<K, V, test_hash<K>, test_equal_to<K>, ThrowingAllocator<ValueType>> c(alloc);
 406     c.insert_range(in);
 407     assert(false); // The function call above should throw.
 408
 409   } catch (int) {
 410     assert(globalMemCounter.new_called == globalMemCounter.delete_called);
 411   }
 412 #endif
 413 }
 414
 415 #endif // SUPPORT_INSERT_RANGE_MAPS_SETS_H