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