1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2008 Google Inc. All rights reserved.
3 // https://developers.google.com/protocol-buffers/
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
7 // met:
8 //
9 // * Redistributions of source code must retain the above copyright
10 // notice, this list of conditions and the following disclaimer.
11 // * Redistributions in binary form must reproduce the above
12 // copyright notice, this list of conditions and the following disclaimer
13 // in the documentation and/or other materials provided with the
14 // distribution.
15 // * Neither the name of Google Inc. nor the names of its
16 // contributors may be used to endorse or promote products derived from
17 // this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31 #include <map>
32 #include <memory>
33 #include <unordered_map>
34
35 #include <google/protobuf/stubs/logging.h>
36 #include <google/protobuf/stubs/common.h>
37 #include <google/protobuf/arena_test_util.h>
38 #include <google/protobuf/map_test_util.h>
39 #include <google/protobuf/map_unittest.pb.h>
40 #include <google/protobuf/unittest.pb.h>
41 #include <google/protobuf/arena.h>
42 #include <google/protobuf/map.h>
43 #include <google/protobuf/map_field_inl.h>
44 #include <google/protobuf/message.h>
45 #include <google/protobuf/repeated_field.h>
46 #include <gtest/gtest.h>
47
48 // Must be included last.
49 #include <google/protobuf/port_def.inc>
50
51 namespace google {
52 namespace protobuf {
53
54 namespace internal {
55
56 using unittest::TestAllTypes;
57
58 class MapFieldBaseStub : public MapFieldBase {
59 public:
60 typedef void InternalArenaConstructable_;
61 typedef void DestructorSkippable_;
MapFieldBaseStub()62 MapFieldBaseStub() {}
MapFieldBaseStub(Arena * arena)63 explicit MapFieldBaseStub(Arena* arena) : MapFieldBase(arena) {}
64 // Get underlined repeated field without synchronizing map.
InternalRepeatedField()65 RepeatedPtrField<Message>* InternalRepeatedField() { return repeated_field_; }
IsMapClean()66 bool IsMapClean() {
67 return state_.load(std::memory_order_relaxed) != STATE_MODIFIED_MAP;
68 }
IsRepeatedClean()69 bool IsRepeatedClean() {
70 return state_.load(std::memory_order_relaxed) != STATE_MODIFIED_REPEATED;
71 }
SetMapDirty()72 void SetMapDirty() {
73 state_.store(STATE_MODIFIED_MAP, std::memory_order_relaxed);
74 }
SetRepeatedDirty()75 void SetRepeatedDirty() {
76 state_.store(STATE_MODIFIED_REPEATED, std::memory_order_relaxed);
77 }
ContainsMapKey(const MapKey & map_key) const78 bool ContainsMapKey(const MapKey& map_key) const override { return false; }
InsertOrLookupMapValue(const MapKey & map_key,MapValueRef * val)79 bool InsertOrLookupMapValue(const MapKey& map_key,
80 MapValueRef* val) override {
81 return false;
82 }
LookupMapValue(const MapKey & map_key,MapValueConstRef * val) const83 bool LookupMapValue(const MapKey& map_key,
84 MapValueConstRef* val) const override {
85 return false;
86 }
DeleteMapValue(const MapKey & map_key)87 bool DeleteMapValue(const MapKey& map_key) override { return false; }
EqualIterator(const MapIterator & a,const MapIterator & b) const88 bool EqualIterator(const MapIterator& a,
89 const MapIterator& b) const override {
90 return false;
91 }
size() const92 int size() const override { return 0; }
Clear()93 void Clear() override {}
MapBegin(MapIterator * map_iter) const94 void MapBegin(MapIterator* map_iter) const override {}
MapEnd(MapIterator * map_iter) const95 void MapEnd(MapIterator* map_iter) const override {}
MergeFrom(const MapFieldBase & other)96 void MergeFrom(const MapFieldBase& other) override {}
Swap(MapFieldBase * other)97 void Swap(MapFieldBase* other) override {}
InitializeIterator(MapIterator * map_iter) const98 void InitializeIterator(MapIterator* map_iter) const override {}
DeleteIterator(MapIterator * map_iter) const99 void DeleteIterator(MapIterator* map_iter) const override {}
CopyIterator(MapIterator * this_iterator,const MapIterator & other_iterator) const100 void CopyIterator(MapIterator* this_iterator,
101 const MapIterator& other_iterator) const override {}
IncreaseIterator(MapIterator * map_iter) const102 void IncreaseIterator(MapIterator* map_iter) const override {}
103
GetArenaForInternalRepeatedField()104 Arena* GetArenaForInternalRepeatedField() {
105 auto* repeated_field = MutableRepeatedField();
106 return repeated_field->GetArena();
107 }
108 };
109
110 class MapFieldBasePrimitiveTest : public testing::TestWithParam<bool> {
111 protected:
112 typedef unittest::TestMap_MapInt32Int32Entry_DoNotUse EntryType;
113 typedef MapField<EntryType, int32, int32, WireFormatLite::TYPE_INT32,
114 WireFormatLite::TYPE_INT32>
115 MapFieldType;
116
MapFieldBasePrimitiveTest()117 MapFieldBasePrimitiveTest()
118 : arena_(GetParam() ? new Arena() : nullptr),
119 map_field_(arena_.get()),
120 map_field_base_(map_field_.get()) {
121 // Get descriptors
122 map_descriptor_ = unittest::TestMap::descriptor()
123 ->FindFieldByName("map_int32_int32")
124 ->message_type();
125 key_descriptor_ = map_descriptor_->map_key();
126 value_descriptor_ = map_descriptor_->map_value();
127
128 // Build map field
129 map_field_base_ = map_field_.get();
130 map_ = map_field_->MutableMap();
131 initial_value_map_[0] = 100;
132 initial_value_map_[1] = 101;
133 map_->insert(initial_value_map_.begin(), initial_value_map_.end());
134 EXPECT_EQ(2, map_->size());
135 }
136
137 std::unique_ptr<Arena> arena_;
138 ArenaHolder<MapFieldType> map_field_;
139 MapFieldBase* map_field_base_;
140 Map<int32, int32>* map_;
141 const Descriptor* map_descriptor_;
142 const FieldDescriptor* key_descriptor_;
143 const FieldDescriptor* value_descriptor_;
144 std::map<int32, int32> initial_value_map_; // copy of initial values inserted
145 };
146
147 INSTANTIATE_TEST_SUITE_P(MapFieldBasePrimitiveTestInstance,
148 MapFieldBasePrimitiveTest,
149 testing::Values(true, false));
150
TEST_P(MapFieldBasePrimitiveTest,SpaceUsedExcludingSelf)151 TEST_P(MapFieldBasePrimitiveTest, SpaceUsedExcludingSelf) {
152 EXPECT_LT(0, map_field_base_->SpaceUsedExcludingSelf());
153 }
154
TEST_P(MapFieldBasePrimitiveTest,GetRepeatedField)155 TEST_P(MapFieldBasePrimitiveTest, GetRepeatedField) {
156 const RepeatedPtrField<Message>& repeated =
157 reinterpret_cast<const RepeatedPtrField<Message>&>(
158 map_field_base_->GetRepeatedField());
159 EXPECT_EQ(2, repeated.size());
160 for (int i = 0; i < repeated.size(); i++) {
161 const Message& message = repeated.Get(i);
162 int key = message.GetReflection()->GetInt32(message, key_descriptor_);
163 int value = message.GetReflection()->GetInt32(message, value_descriptor_);
164 EXPECT_EQ(value, initial_value_map_[key]);
165 }
166 }
167
TEST_P(MapFieldBasePrimitiveTest,MutableRepeatedField)168 TEST_P(MapFieldBasePrimitiveTest, MutableRepeatedField) {
169 RepeatedPtrField<Message>* repeated =
170 reinterpret_cast<RepeatedPtrField<Message>*>(
171 map_field_base_->MutableRepeatedField());
172 EXPECT_EQ(2, repeated->size());
173 for (int i = 0; i < repeated->size(); i++) {
174 const Message& message = repeated->Get(i);
175 int key = message.GetReflection()->GetInt32(message, key_descriptor_);
176 int value = message.GetReflection()->GetInt32(message, value_descriptor_);
177 EXPECT_EQ(value, initial_value_map_[key]);
178 }
179 }
180
TEST_P(MapFieldBasePrimitiveTest,Arena)181 TEST_P(MapFieldBasePrimitiveTest, Arena) {
182 // Allocate a large initial block to avoid mallocs during hooked test.
183 std::vector<char> arena_block(128 * 1024);
184 ArenaOptions options;
185 options.initial_block = &arena_block[0];
186 options.initial_block_size = arena_block.size();
187 Arena arena(options);
188
189 {
190 // TODO(liujisi): Re-write the test to ensure the memory for the map and
191 // repeated fields are allocated from arenas.
192 // NoHeapChecker no_heap;
193
194 MapFieldType* map_field = Arena::CreateMessage<MapFieldType>(&arena);
195
196 // Set content in map
197 (*map_field->MutableMap())[100] = 101;
198
199 // Trigger conversion to repeated field.
200 map_field->GetRepeatedField();
201 }
202
203 {
204 // TODO(liujisi): Re-write the test to ensure the memory for the map and
205 // repeated fields are allocated from arenas.
206 // NoHeapChecker no_heap;
207
208 MapFieldBaseStub* map_field =
209 Arena::CreateMessage<MapFieldBaseStub>(&arena);
210
211 // Trigger conversion to repeated field.
212 EXPECT_TRUE(map_field->MutableRepeatedField() != NULL);
213
214 EXPECT_EQ(map_field->GetArenaForInternalRepeatedField(), &arena);
215 }
216 }
217
TEST_P(MapFieldBasePrimitiveTest,EnforceNoArena)218 TEST_P(MapFieldBasePrimitiveTest, EnforceNoArena) {
219 std::unique_ptr<MapFieldBaseStub> map_field(
220 Arena::CreateMessage<MapFieldBaseStub>(nullptr));
221 EXPECT_EQ(map_field->GetArenaForInternalRepeatedField(), nullptr);
222 }
223
224 namespace {
225 enum State { CLEAN, MAP_DIRTY, REPEATED_DIRTY };
226 } // anonymous namespace
227
228 class MapFieldStateTest
229 : public testing::TestWithParam<std::tuple<State, bool>> {
230 protected:
231 typedef unittest::TestMap_MapInt32Int32Entry_DoNotUse EntryType;
232 typedef MapField<EntryType, int32, int32, WireFormatLite::TYPE_INT32,
233 WireFormatLite::TYPE_INT32>
234 MapFieldType;
MapFieldStateTest()235 MapFieldStateTest()
236 : arena_(std::get<1>(GetParam()) ? new Arena() : nullptr),
237 map_field_(arena_.get()),
238 map_field_base_(map_field_.get()),
239 state_(std::get<0>(GetParam())) {
240 // Build map field
241 Expect(map_field_.get(), MAP_DIRTY, 0, 0, true);
242 switch (state_) {
243 case CLEAN:
244 AddOneStillClean(map_field_.get());
245 break;
246 case MAP_DIRTY:
247 MakeMapDirty(map_field_.get());
248 break;
249 case REPEATED_DIRTY:
250 MakeRepeatedDirty(map_field_.get());
251 break;
252 default:
253 break;
254 }
255 }
256
AddOneStillClean(MapFieldType * map_field)257 void AddOneStillClean(MapFieldType* map_field) {
258 MapFieldBase* map_field_base = map_field;
259 Map<int32, int32>* map = map_field->MutableMap();
260 (*map)[0] = 0;
261 map_field_base->GetRepeatedField();
262 Expect(map_field, CLEAN, 1, 1, false);
263 }
264
MakeMapDirty(MapFieldType * map_field)265 void MakeMapDirty(MapFieldType* map_field) {
266 Map<int32, int32>* map = map_field->MutableMap();
267 (*map)[0] = 0;
268 Expect(map_field, MAP_DIRTY, 1, 0, true);
269 }
270
MakeRepeatedDirty(MapFieldType * map_field)271 void MakeRepeatedDirty(MapFieldType* map_field) {
272 MakeMapDirty(map_field);
273 MapFieldBase* map_field_base = map_field;
274 map_field_base->MutableRepeatedField();
275 // We use MutableMap on impl_ because we don't want to disturb the syncing
276 Map<int32, int32>* map = map_field->impl_.MutableMap();
277 map->clear();
278
279 Expect(map_field, REPEATED_DIRTY, 0, 1, false);
280 }
281
Expect(MapFieldType * map_field,State state,int map_size,int repeated_size,bool is_repeated_null)282 void Expect(MapFieldType* map_field, State state, int map_size,
283 int repeated_size, bool is_repeated_null) {
284 MapFieldBase* map_field_base = map_field;
285 MapFieldBaseStub* stub =
286 reinterpret_cast<MapFieldBaseStub*>(map_field_base);
287
288 // We use MutableMap on impl_ because we don't want to disturb the syncing
289 Map<int32, int32>* map = map_field->impl_.MutableMap();
290 RepeatedPtrField<Message>* repeated_field = stub->InternalRepeatedField();
291
292 switch (state) {
293 case MAP_DIRTY:
294 EXPECT_FALSE(stub->IsMapClean());
295 EXPECT_TRUE(stub->IsRepeatedClean());
296 break;
297 case REPEATED_DIRTY:
298 EXPECT_TRUE(stub->IsMapClean());
299 EXPECT_FALSE(stub->IsRepeatedClean());
300 break;
301 case CLEAN:
302 EXPECT_TRUE(stub->IsMapClean());
303 EXPECT_TRUE(stub->IsRepeatedClean());
304 break;
305 default:
306 FAIL();
307 }
308
309 EXPECT_EQ(map_size, map->size());
310 if (is_repeated_null) {
311 EXPECT_TRUE(repeated_field == NULL);
312 } else {
313 if (repeated_field == nullptr) {
314 EXPECT_EQ(repeated_size, 0);
315 } else {
316 EXPECT_EQ(repeated_size, repeated_field->size());
317 }
318 }
319 }
320
321 std::unique_ptr<Arena> arena_;
322 ArenaHolder<MapFieldType> map_field_;
323 MapFieldBase* map_field_base_;
324 State state_;
325 };
326
327 INSTANTIATE_TEST_SUITE_P(MapFieldStateTestInstance, MapFieldStateTest,
328 testing::Combine(testing::Values(CLEAN, MAP_DIRTY,
329 REPEATED_DIRTY),
330 testing::Values(true, false)));
331
TEST_P(MapFieldStateTest,GetMap)332 TEST_P(MapFieldStateTest, GetMap) {
333 map_field_->GetMap();
334 if (state_ != MAP_DIRTY) {
335 Expect(map_field_.get(), CLEAN, 1, 1, false);
336 } else {
337 Expect(map_field_.get(), MAP_DIRTY, 1, 0, true);
338 }
339 }
340
TEST_P(MapFieldStateTest,MutableMap)341 TEST_P(MapFieldStateTest, MutableMap) {
342 map_field_->MutableMap();
343 if (state_ != MAP_DIRTY) {
344 Expect(map_field_.get(), MAP_DIRTY, 1, 1, false);
345 } else {
346 Expect(map_field_.get(), MAP_DIRTY, 1, 0, true);
347 }
348 }
349
TEST_P(MapFieldStateTest,MergeFromClean)350 TEST_P(MapFieldStateTest, MergeFromClean) {
351 ArenaHolder<MapFieldType> other(arena_.get());
352 AddOneStillClean(other.get());
353
354 map_field_->MergeFrom(*other);
355
356 if (state_ != MAP_DIRTY) {
357 Expect(map_field_.get(), MAP_DIRTY, 1, 1, false);
358 } else {
359 Expect(map_field_.get(), MAP_DIRTY, 1, 0, true);
360 }
361
362 Expect(other.get(), CLEAN, 1, 1, false);
363 }
364
TEST_P(MapFieldStateTest,MergeFromMapDirty)365 TEST_P(MapFieldStateTest, MergeFromMapDirty) {
366 ArenaHolder<MapFieldType> other(arena_.get());
367 MakeMapDirty(other.get());
368
369 map_field_->MergeFrom(*other);
370
371 if (state_ != MAP_DIRTY) {
372 Expect(map_field_.get(), MAP_DIRTY, 1, 1, false);
373 } else {
374 Expect(map_field_.get(), MAP_DIRTY, 1, 0, true);
375 }
376
377 Expect(other.get(), MAP_DIRTY, 1, 0, true);
378 }
379
TEST_P(MapFieldStateTest,MergeFromRepeatedDirty)380 TEST_P(MapFieldStateTest, MergeFromRepeatedDirty) {
381 ArenaHolder<MapFieldType> other(arena_.get());
382 MakeRepeatedDirty(other.get());
383
384 map_field_->MergeFrom(*other);
385
386 if (state_ != MAP_DIRTY) {
387 Expect(map_field_.get(), MAP_DIRTY, 1, 1, false);
388 } else {
389 Expect(map_field_.get(), MAP_DIRTY, 1, 0, true);
390 }
391
392 Expect(other.get(), CLEAN, 1, 1, false);
393 }
394
TEST_P(MapFieldStateTest,SwapClean)395 TEST_P(MapFieldStateTest, SwapClean) {
396 ArenaHolder<MapFieldType> other(arena_.get());
397 AddOneStillClean(other.get());
398
399 map_field_->Swap(other.get());
400
401 Expect(map_field_.get(), CLEAN, 1, 1, false);
402
403 switch (state_) {
404 case CLEAN:
405 Expect(other.get(), CLEAN, 1, 1, false);
406 break;
407 case MAP_DIRTY:
408 Expect(other.get(), MAP_DIRTY, 1, 0, true);
409 break;
410 case REPEATED_DIRTY:
411 Expect(other.get(), REPEATED_DIRTY, 0, 1, false);
412 break;
413 default:
414 break;
415 }
416 }
417
TEST_P(MapFieldStateTest,SwapMapDirty)418 TEST_P(MapFieldStateTest, SwapMapDirty) {
419 ArenaHolder<MapFieldType> other(arena_.get());
420 MakeMapDirty(other.get());
421
422 map_field_->Swap(other.get());
423
424 Expect(map_field_.get(), MAP_DIRTY, 1, 0, true);
425
426 switch (state_) {
427 case CLEAN:
428 Expect(other.get(), CLEAN, 1, 1, false);
429 break;
430 case MAP_DIRTY:
431 Expect(other.get(), MAP_DIRTY, 1, 0, true);
432 break;
433 case REPEATED_DIRTY:
434 Expect(other.get(), REPEATED_DIRTY, 0, 1, false);
435 break;
436 default:
437 break;
438 }
439 }
440
TEST_P(MapFieldStateTest,SwapRepeatedDirty)441 TEST_P(MapFieldStateTest, SwapRepeatedDirty) {
442 ArenaHolder<MapFieldType> other(arena_.get());
443 MakeRepeatedDirty(other.get());
444
445 map_field_->Swap(other.get());
446
447 Expect(map_field_.get(), REPEATED_DIRTY, 0, 1, false);
448
449 switch (state_) {
450 case CLEAN:
451 Expect(other.get(), CLEAN, 1, 1, false);
452 break;
453 case MAP_DIRTY:
454 Expect(other.get(), MAP_DIRTY, 1, 0, true);
455 break;
456 case REPEATED_DIRTY:
457 Expect(other.get(), REPEATED_DIRTY, 0, 1, false);
458 break;
459 default:
460 break;
461 }
462 }
463
TEST_P(MapFieldStateTest,Clear)464 TEST_P(MapFieldStateTest, Clear) {
465 map_field_->Clear();
466
467 Expect(map_field_.get(), MAP_DIRTY, 0, 0, false);
468 }
469
TEST_P(MapFieldStateTest,SpaceUsedExcludingSelf)470 TEST_P(MapFieldStateTest, SpaceUsedExcludingSelf) {
471 map_field_base_->SpaceUsedExcludingSelf();
472
473 switch (state_) {
474 case CLEAN:
475 Expect(map_field_.get(), CLEAN, 1, 1, false);
476 break;
477 case MAP_DIRTY:
478 Expect(map_field_.get(), MAP_DIRTY, 1, 0, true);
479 break;
480 case REPEATED_DIRTY:
481 Expect(map_field_.get(), REPEATED_DIRTY, 0, 1, false);
482 break;
483 default:
484 break;
485 }
486 }
487
TEST_P(MapFieldStateTest,GetMapField)488 TEST_P(MapFieldStateTest, GetMapField) {
489 map_field_base_->GetRepeatedField();
490
491 if (state_ != REPEATED_DIRTY) {
492 Expect(map_field_.get(), CLEAN, 1, 1, false);
493 } else {
494 Expect(map_field_.get(), REPEATED_DIRTY, 0, 1, false);
495 }
496 }
497
TEST_P(MapFieldStateTest,MutableMapField)498 TEST_P(MapFieldStateTest, MutableMapField) {
499 map_field_base_->MutableRepeatedField();
500
501 if (state_ != REPEATED_DIRTY) {
502 Expect(map_field_.get(), REPEATED_DIRTY, 1, 1, false);
503 } else {
504 Expect(map_field_.get(), REPEATED_DIRTY, 0, 1, false);
505 }
506 }
507
508 class MyMapField
509 : public MapField<unittest::TestMap_MapInt32Int32Entry_DoNotUse, int32,
510 int32, internal::WireFormatLite::TYPE_INT32,
511 internal::WireFormatLite::TYPE_INT32> {
512 public:
MyMapField()513 constexpr MyMapField()
514 : MyMapField::MapField(internal::ConstantInitialized{}) {}
515 };
516
TEST(MapFieldTest,ConstInit)517 TEST(MapFieldTest, ConstInit) {
518 // This tests that `MapField` and all its base classes can be constant
519 // initialized.
520 PROTOBUF_CONSTINIT static MyMapField field; // NOLINT
521 EXPECT_EQ(field.size(), 0);
522 }
523
524
525 } // namespace internal
526 } // namespace protobuf
527 } // namespace google
528