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