1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2008 Google Inc. All rights reserved.
3 //
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file or at
6 // https://developers.google.com/open-source/licenses/bsd
7
8 #include "google/protobuf/map.h"
9
10 #include <array>
11 #include <cstddef>
12 #include <cstdint>
13 #include <memory>
14 #include <string>
15 #include <type_traits>
16 #include <utility>
17 #include <vector>
18
19 #include <gmock/gmock.h>
20 #include <gtest/gtest.h>
21 #include "absl/container/flat_hash_set.h"
22 #include "absl/strings/str_cat.h"
23 #include "google/protobuf/arena_test_util.h"
24 #include "google/protobuf/internal_visibility_for_testing.h"
25 #include "google/protobuf/map_field.h"
26 #include "google/protobuf/map_proto2_unittest.pb.h"
27 #include "google/protobuf/map_unittest.pb.h"
28 #include "google/protobuf/reflection_tester.h"
29 #include "google/protobuf/unittest.pb.h"
30 #include "google/protobuf/unittest_import.pb.h"
31
32
33 #define BRIDGE_UNITTEST ::google::protobuf::bridge_unittest
34 #define UNITTEST ::protobuf_unittest
35 #define UNITTEST_IMPORT ::protobuf_unittest_import
36 #define UNITTEST_PACKAGE_NAME "protobuf_unittest"
37
38 // Must include after defining UNITTEST, etc.
39 // clang-format off
40 #include "google/protobuf/test_util.inc"
41 #include "google/protobuf/map_test_util.inc"
42 #include "google/protobuf/map_test.inc"
43 // clang-format on
44
45 // Must be included last.
46 #include "google/protobuf/port_def.inc"
47
48 namespace google {
49 namespace protobuf {
50 namespace internal {
51
52 struct AlignedAsDefault {
53 int x;
54 };
55 struct alignas(8) AlignedAs8 {
56 int x;
57 };
58
59 template <>
60 struct is_internal_map_value_type<AlignedAsDefault> : std::true_type {};
61 template <>
62 struct is_internal_map_value_type<AlignedAs8> : std::true_type {};
63
64 namespace {
65
66 using ::testing::AllOf;
67 using ::testing::FieldsAre;
68 using ::testing::Ge;
69 using ::testing::Le;
70 using ::testing::UnorderedElementsAre;
71
72
TEST(MapTest,CopyConstructIntegers)73 TEST(MapTest, CopyConstructIntegers) {
74 auto token = internal::InternalVisibilityForTesting{};
75 using MapType = Map<int32_t, int32_t>;
76 MapType original;
77 original[1] = 2;
78 original[2] = 3;
79
80 MapType map1(original);
81 ASSERT_EQ(map1.size(), 2);
82 EXPECT_EQ(map1[1], 2);
83 EXPECT_EQ(map1[2], 3);
84
85 MapType map2(token, nullptr, original);
86 ASSERT_EQ(map2.size(), 2);
87 EXPECT_EQ(map2[1], 2);
88 EXPECT_EQ(map2[2], 3);
89 }
90
TEST(MapTest,CopyConstructStrings)91 TEST(MapTest, CopyConstructStrings) {
92 auto token = internal::InternalVisibilityForTesting{};
93 using MapType = Map<std::string, std::string>;
94 MapType original;
95 original["1"] = "2";
96 original["2"] = "3";
97
98 MapType map1(original);
99 ASSERT_EQ(map1.size(), 2);
100 EXPECT_EQ(map1["1"], "2");
101 EXPECT_EQ(map1["2"], "3");
102
103 MapType map2(token, nullptr, original);
104 ASSERT_EQ(map2.size(), 2);
105 EXPECT_EQ(map2["1"], "2");
106 EXPECT_EQ(map2["2"], "3");
107 }
108
TEST(MapTest,CopyConstructMessages)109 TEST(MapTest, CopyConstructMessages) {
110 auto token = internal::InternalVisibilityForTesting{};
111 using MapType = Map<std::string, TestAllTypes>;
112 MapType original;
113 original["1"].set_optional_int32(1);
114 original["2"].set_optional_int32(2);
115
116 MapType map1(original);
117 ASSERT_EQ(map1.size(), 2);
118 EXPECT_EQ(map1["1"].optional_int32(), 1);
119 EXPECT_EQ(map1["2"].optional_int32(), 2);
120
121 MapType map2(token, nullptr, original);
122 ASSERT_EQ(map2.size(), 2);
123 EXPECT_EQ(map2["1"].optional_int32(), 1);
124 EXPECT_EQ(map2["2"].optional_int32(), 2);
125 }
126
TEST(MapTest,CopyConstructIntegersWithArena)127 TEST(MapTest, CopyConstructIntegersWithArena) {
128 auto token = internal::InternalVisibilityForTesting{};
129 using MapType = Map<int32_t, int32_t>;
130 MapType original;
131 original[1] = 2;
132 original[2] = 3;
133
134 Arena arena;
135 alignas(MapType) char mem1[sizeof(MapType)];
136 MapType& map1 = *new (mem1) MapType(token, &arena, original);
137 ASSERT_EQ(map1.size(), 2);
138 EXPECT_EQ(map1[1], 2);
139 EXPECT_EQ(map1[2], 3);
140 EXPECT_EQ(map1[2], 3);
141 }
142
TEST(MapTest,CopyConstructStringsWithArena)143 TEST(MapTest, CopyConstructStringsWithArena) {
144 auto token = internal::InternalVisibilityForTesting{};
145 using MapType = Map<std::string, std::string>;
146 MapType original;
147 original["1"] = "2";
148 original["2"] = "3";
149
150 Arena arena;
151 alignas(MapType) char mem1[sizeof(MapType)];
152 MapType& map1 = *new (mem1) MapType(token, &arena, original);
153 ASSERT_EQ(map1.size(), 2);
154 EXPECT_EQ(map1["1"], "2");
155 EXPECT_EQ(map1["2"], "3");
156 }
157
TEST(MapTest,CopyConstructMessagesWithArena)158 TEST(MapTest, CopyConstructMessagesWithArena) {
159 auto token = internal::InternalVisibilityForTesting{};
160 using MapType = Map<std::string, TestAllTypes>;
161 MapType original;
162 original["1"].set_optional_int32(1);
163 original["2"].set_optional_int32(2);
164
165 Arena arena;
166 alignas(MapType) char mem1[sizeof(MapType)];
167 MapType& map1 = *new (mem1) MapType(token, &arena, original);
168 ASSERT_EQ(map1.size(), 2);
169 EXPECT_EQ(map1["1"].optional_int32(), 1);
170 EXPECT_EQ(map1["1"].GetArena(), &arena);
171 EXPECT_EQ(map1["2"].optional_int32(), 2);
172 EXPECT_EQ(map1["2"].GetArena(), &arena);
173 }
174
TEST(MapTest,AlwaysSerializesBothEntries)175 TEST(MapTest, AlwaysSerializesBothEntries) {
176 for (const Message* prototype :
177 {static_cast<const Message*>(
178 &protobuf_unittest::TestI32StrMap::default_instance()),
179 static_cast<const Message*>(
180 &proto3_unittest::TestI32StrMap::default_instance())}) {
181 const FieldDescriptor* map_field =
182 prototype->GetDescriptor()->FindFieldByName("m_32_str");
183 const FieldDescriptor* map_key = map_field->message_type()->map_key();
184 const FieldDescriptor* map_value = map_field->message_type()->map_value();
185 for (bool add_key : {true, false}) {
186 for (bool add_value : {true, false}) {
187 std::unique_ptr<Message> message(prototype->New());
188 Message* entry_message =
189 message->GetReflection()->AddMessage(message.get(), map_field);
190 // Add the fields, but leave them as the default to make it easier to
191 // match.
192 if (add_key) {
193 entry_message->GetReflection()->SetInt32(entry_message, map_key, 0);
194 }
195 if (add_value) {
196 entry_message->GetReflection()->SetString(entry_message, map_value,
197 "");
198 }
199 ASSERT_EQ(4, entry_message->ByteSizeLong());
200 EXPECT_EQ(entry_message->SerializeAsString(),
201 std::string({
202 '\010', '\0', // key, VARINT, value=0
203 '\022', '\0', // value, LEN, size=0
204 }));
205 ASSERT_EQ(6, message->ByteSizeLong());
206 EXPECT_EQ(message->SerializeAsString(),
207 std::string({
208 '\012', '\04', // field=1, LEN, size=4
209 '\010', '\0', // key, VARINT, value=0
210 '\022', '\0', // value, LEN, size=0
211 }));
212 }
213 }
214 }
215 }
216
TEST(MapTest,LoadFactorCalculationWorks)217 TEST(MapTest, LoadFactorCalculationWorks) {
218 // Three stages:
219 // - empty
220 // - small
221 // - large
222
223 const auto calculate = MapTestPeer::CalculateHiCutoff;
224 // empty
225 EXPECT_EQ(calculate(kGlobalEmptyTableSize), 0);
226
227 // small
228 EXPECT_EQ(calculate(2), 2);
229 EXPECT_EQ(calculate(4), 4);
230 EXPECT_EQ(calculate(8), 8);
231
232 // large
233 for (int i = 16; i < 10000; i *= 2) {
234 EXPECT_EQ(calculate(i), .75 * i) << "i=" << i;
235 }
236 }
237
TEST(MapTest,NaturalGrowthOnArenasReuseBlocks)238 TEST(MapTest, NaturalGrowthOnArenasReuseBlocks) {
239 Arena arena;
240 std::vector<Map<int, int>*> values;
241
242 static constexpr int kNumFields = 100;
243 static constexpr int kNumElems = 1000;
244 for (int i = 0; i < kNumFields; ++i) {
245 values.push_back(Arena::Create<Map<int, int>>(&arena));
246 auto& field = *values.back();
247 for (int j = 0; j < kNumElems; ++j) {
248 field[j] = j;
249 }
250 }
251
252 struct MockNode : internal::NodeBase {
253 std::pair<int, int> v;
254 };
255 size_t expected =
256 values.size() * (MapTestPeer::NumBuckets(*values[0]) * sizeof(void*) +
257 values[0]->size() * sizeof(MockNode));
258 // Use a 2% slack for other overhead. If we were not reusing the blocks, the
259 // actual value would be ~2x the cost of the bucket array.
260 EXPECT_THAT(arena.SpaceUsed(), AllOf(Ge(expected), Le(1.02 * expected)));
261 }
262
263 // We changed the internal implementation to use a smaller size type, but the
264 // public API will still use size_t to avoid changing the API. Test that.
TEST(MapTest,SizeTypeIsSizeT)265 TEST(MapTest, SizeTypeIsSizeT) {
266 using M = Map<int, int>;
267 EXPECT_TRUE((std::is_same<M::size_type, size_t>::value));
268 EXPECT_TRUE((std::is_same<decltype(M().size()), size_t>::value));
269 size_t x = 0;
270 x = std::max(M().size(), x);
271 (void)x;
272 }
273
TEST(MapTest,IteratorNodeFieldIsNullPtrAtEnd)274 TEST(MapTest, IteratorNodeFieldIsNullPtrAtEnd) {
275 Map<int, int> map;
276 EXPECT_EQ(internal::UntypedMapIterator::FromTyped(map.cbegin()).node_,
277 nullptr);
278 map.insert({1, 1});
279 // This behavior is depended on by Rust FFI.
280 EXPECT_NE(internal::UntypedMapIterator::FromTyped(map.cbegin()).node_,
281 nullptr);
282 EXPECT_EQ(internal::UntypedMapIterator::FromTyped(map.cend()).node_, nullptr);
283 }
284
285 template <typename Aligned, bool on_arena = false>
MapTest_Aligned()286 void MapTest_Aligned() {
287 Arena arena;
288 constexpr size_t align_mask = alignof(Aligned) - 1;
289 Map<int, Aligned> map(on_arena ? &arena : nullptr);
290 map.insert({1, Aligned{}});
291 auto it = map.find(1);
292 ASSERT_NE(it, map.end());
293 ASSERT_EQ(reinterpret_cast<intptr_t>(&it->second) & align_mask, 0);
294 map.clear();
295 }
296
TEST(MapTest,Aligned)297 TEST(MapTest, Aligned) { MapTest_Aligned<AlignedAsDefault>(); }
TEST(MapTest,AlignedOnArena)298 TEST(MapTest, AlignedOnArena) { MapTest_Aligned<AlignedAsDefault, true>(); }
TEST(MapTest,Aligned8)299 TEST(MapTest, Aligned8) { MapTest_Aligned<AlignedAs8>(); }
TEST(MapTest,Aligned8OnArena)300 TEST(MapTest, Aligned8OnArena) { MapTest_Aligned<AlignedAs8, true>(); }
301
302
303
304 } // namespace
305 } // namespace internal
306 } // namespace protobuf
307 } // namespace google
308
309 #include "google/protobuf/port_undef.inc"
310