235 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_FLAT_MAP_HELPERS_H10#define SUPPORT_FLAT_MAP_HELPERS_H11 12#include <algorithm>13#include <cassert>14#include <string>15#include <vector>16#include <flat_map>17#include <ranges>18#include <type_traits>19 20#include "../flat_helpers.h"21#include "test_allocator.h"22#include "test_macros.h"23 24template <class... Args>25constexpr void check_invariant(const std::flat_map<Args...>& m) {26 assert(m.keys().size() == m.values().size());27 const auto& keys = m.keys();28 assert(std::is_sorted(keys.begin(), keys.end(), m.key_comp()));29 auto key_equal = [&](const auto& x, const auto& y) {30 const auto& c = m.key_comp();31 return !c(x, y) && !c(y, x);32 };33 assert(std::adjacent_find(keys.begin(), keys.end(), key_equal) == keys.end());34}35 36constexpr void check_possible_values(const auto& actual, const auto& expected) {37 assert(std::ranges::size(actual) == std::ranges::size(expected));38 39 for (const auto& [actual_value, possible_values] : std::views::zip(actual, expected)) {40 assert(std::ranges::find(possible_values, actual_value) != std::ranges::end(possible_values));41 }42}43 44template <class F>45void test_emplace_exception_guarantee([[maybe_unused]] F&& emplace_function) {46#ifndef TEST_HAS_NO_EXCEPTIONS47 using C = TransparentComparator;48 {49 // Throw on emplace the key, and underlying has strong exception guarantee50 using KeyContainer = std::vector<int, test_allocator<int>>;51 using M = std::flat_map<int, int, C, KeyContainer>;52 53 LIBCPP_STATIC_ASSERT(std::__container_traits<KeyContainer>::__emplacement_has_strong_exception_safety_guarantee);54 55 test_allocator_statistics stats;56 57 KeyContainer a({1, 2, 3, 4}, test_allocator<int>{&stats});58 std::vector<int> b = {5, 6, 7, 8};59 [[maybe_unused]] auto expected_keys = a;60 [[maybe_unused]] auto expected_values = b;61 M m(std::sorted_unique, std::move(a), std::move(b));62 63 stats.throw_after = 1;64 try {65 emplace_function(m, 0, 0);66 assert(false);67 } catch (const std::bad_alloc&) {68 check_invariant(m);69 // In libc++, the flat_map is unchanged70 LIBCPP_ASSERT(m.size() == 4);71 LIBCPP_ASSERT(m.keys() == expected_keys);72 LIBCPP_ASSERT(m.values() == expected_values);73 }74 }75 {76 // Throw on emplace the key, and underlying has no strong exception guarantee77 using KeyContainer = EmplaceUnsafeContainer<int>;78 using M = std::flat_map<int, int, C, KeyContainer>;79 80 LIBCPP_STATIC_ASSERT(!std::__container_traits<KeyContainer>::__emplacement_has_strong_exception_safety_guarantee);81 KeyContainer a = {1, 2, 3, 4};82 std::vector<int> b = {5, 6, 7, 8};83 M m(std::sorted_unique, std::move(a), std::move(b));84 try {85 emplace_function(m, 0, 0);86 assert(false);87 } catch (int) {88 check_invariant(m);89 // In libc++, the flat_map is cleared90 LIBCPP_ASSERT(m.size() == 0);91 }92 }93 {94 // Throw on emplace the value, and underlying has strong exception guarantee95 using ValueContainer = std::vector<int, test_allocator<int>>;96 ;97 using M = std::flat_map<int, int, C, std::vector<int>, ValueContainer>;98 99 LIBCPP_STATIC_ASSERT(std::__container_traits<ValueContainer>::__emplacement_has_strong_exception_safety_guarantee);100 101 std::vector<int> a = {1, 2, 3, 4};102 test_allocator_statistics stats;103 ValueContainer b({1, 2, 3, 4}, test_allocator<int>{&stats});104 105 [[maybe_unused]] auto expected_keys = a;106 [[maybe_unused]] auto expected_values = b;107 M m(std::sorted_unique, std::move(a), std::move(b));108 109 stats.throw_after = 1;110 try {111 emplace_function(m, 0, 0);112 assert(false);113 } catch (const std::bad_alloc&) {114 check_invariant(m);115 // In libc++, the emplaced key is erased and the flat_map is unchanged116 LIBCPP_ASSERT(m.size() == 4);117 LIBCPP_ASSERT(m.keys() == expected_keys);118 LIBCPP_ASSERT(m.values() == expected_values);119 }120 }121 {122 // Throw on emplace the value, and underlying has no strong exception guarantee123 using ValueContainer = EmplaceUnsafeContainer<int>;124 using M = std::flat_map<int, int, C, std::vector<int>, ValueContainer>;125 126 LIBCPP_STATIC_ASSERT(!std::__container_traits<ValueContainer>::__emplacement_has_strong_exception_safety_guarantee);127 std::vector<int> a = {1, 2, 3, 4};128 ValueContainer b = {1, 2, 3, 4};129 130 M m(std::sorted_unique, std::move(a), std::move(b));131 132 try {133 emplace_function(m, 0, 0);134 assert(false);135 } catch (int) {136 check_invariant(m);137 // In libc++, the flat_map is cleared138 LIBCPP_ASSERT(m.size() == 0);139 }140 }141 {142 // Throw on emplace the value, then throw again on erasing the key143 using KeyContainer = ThrowOnEraseContainer<int>;144 using ValueContainer = std::vector<int, test_allocator<int>>;145 using M = std::flat_map<int, int, C, KeyContainer, ValueContainer>;146 147 LIBCPP_STATIC_ASSERT(std::__container_traits<ValueContainer>::__emplacement_has_strong_exception_safety_guarantee);148 149 KeyContainer a = {1, 2, 3, 4};150 test_allocator_statistics stats;151 ValueContainer b({1, 2, 3, 4}, test_allocator<int>{&stats});152 153 M m(std::sorted_unique, std::move(a), std::move(b));154 stats.throw_after = 1;155 try {156 emplace_function(m, 0, 0);157 assert(false);158 } catch (const std::bad_alloc&) {159 check_invariant(m);160 // In libc++, we try to erase the key after value emplacement failure.161 // and after erasure failure, we clear the flat_map162 LIBCPP_ASSERT(m.size() == 0);163 }164 }165#endif166}167 168template <class F>169void test_insert_range_exception_guarantee([[maybe_unused]] F&& insert_function) {170#ifndef TEST_HAS_NO_EXCEPTIONS171 using KeyContainer = EmplaceUnsafeContainer<int>;172 using ValueContainer = std::vector<int>;173 using M = std::flat_map<int, int, std::ranges::less, KeyContainer, ValueContainer>;174 test_allocator_statistics stats;175 KeyContainer a{1, 2, 3, 4};176 ValueContainer b{1, 2, 3, 4};177 M m(std::sorted_unique, std::move(a), std::move(b));178 179 std::vector<std::pair<int, int>> newValues = {{0, 0}, {1, 1}, {5, 5}, {6, 6}, {7, 7}, {8, 8}};180 stats.throw_after = 1;181 try {182 insert_function(m, newValues);183 assert(false);184 } catch (int) {185 check_invariant(m);186 // In libc++, we clear if anything goes wrong when inserting a range187 LIBCPP_ASSERT(m.size() == 0);188 }189#endif190}191 192template <class F>193void test_erase_exception_guarantee([[maybe_unused]] F&& erase_function) {194#ifndef TEST_HAS_NO_EXCEPTIONS195 {196 // key erase throws197 using KeyContainer = ThrowOnEraseContainer<int>;198 using ValueContainer = std::vector<int>;199 using M = std::flat_map<int, int, TransparentComparator, KeyContainer, ValueContainer>;200 201 KeyContainer a{1, 2, 3, 4};202 ValueContainer b{1, 2, 3, 4};203 M m(std::sorted_unique, std::move(a), std::move(b));204 try {205 erase_function(m, 3);206 assert(false);207 } catch (int) {208 check_invariant(m);209 // In libc++, we clear if anything goes wrong when erasing210 LIBCPP_ASSERT(m.size() == 0);211 }212 }213 {214 // key erase throws215 using KeyContainer = std::vector<int>;216 using ValueContainer = ThrowOnEraseContainer<int>;217 using M = std::flat_map<int, int, TransparentComparator, KeyContainer, ValueContainer>;218 219 KeyContainer a{1, 2, 3, 4};220 ValueContainer b{1, 2, 3, 4};221 M m(std::sorted_unique, std::move(a), std::move(b));222 try {223 erase_function(m, 3);224 assert(false);225 } catch (int) {226 check_invariant(m);227 // In libc++, we clear if anything goes wrong when erasing228 LIBCPP_ASSERT(m.size() == 0);229 }230 }231#endif232}233 234#endif // SUPPORT_FLAT_MAP_HELPERS_H235