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#ifndef GOOGLE_PROTOBUF_MAP_ENTRY_LITE_H__
32#define GOOGLE_PROTOBUF_MAP_ENTRY_LITE_H__
33
34#include <assert.h>
35
36#include <algorithm>
37#include <string>
38#include <utility>
39
40#include <google/protobuf/stubs/casts.h>
41#include <google/protobuf/io/coded_stream.h>
42#include <google/protobuf/arena.h>
43#include <google/protobuf/port.h>
44#include <google/protobuf/arenastring.h>
45#include <google/protobuf/generated_message_util.h>
46#include <google/protobuf/map.h>
47#include <google/protobuf/map_type_handler.h>
48#include <google/protobuf/parse_context.h>
49#include <google/protobuf/wire_format_lite.h>
50
51// Must be included last.
52#include <google/protobuf/port_def.inc>
53#ifdef SWIG
54#error "You cannot SWIG proto headers"
55#endif
56
57namespace google {
58namespace protobuf {
59namespace internal {
60template <typename Derived, typename Key, typename Value,
61 WireFormatLite::FieldType kKeyFieldType,
62 WireFormatLite::FieldType kValueFieldType>
63class MapEntry;
64template <typename Derived, typename Key, typename Value,
65 WireFormatLite::FieldType kKeyFieldType,
66 WireFormatLite::FieldType kValueFieldType>
67class MapFieldLite;
68} // namespace internal
69} // namespace protobuf
70} // namespace google
71
72namespace google {
73namespace protobuf {
74namespace internal {
75
76// MoveHelper::Move is used to set *dest. It copies *src, or moves it (in
77// the C++11 sense), or swaps it. *src is left in a sane state for
78// subsequent destruction, but shouldn't be used for anything.
79template <bool is_enum, bool is_message, bool is_stringlike, typename T>
80struct MoveHelper { // primitives
81 static void Move(T* src, T* dest) { *dest = *src; }
82};
83
84template <bool is_message, bool is_stringlike, typename T>
85struct MoveHelper<true, is_message, is_stringlike, T> { // enums
86 static void Move(T* src, T* dest) { *dest = *src; }
87 // T is an enum here, so allow conversions to and from int.
88 static void Move(T* src, int* dest) { *dest = static_cast<int>(*src); }
89 static void Move(int* src, T* dest) { *dest = static_cast<T>(*src); }
90};
91
92template <bool is_stringlike, typename T>
93struct MoveHelper<false, true, is_stringlike, T> { // messages
94 static void Move(T* src, T* dest) { dest->Swap(src); }
95};
96
97template <typename T>
98struct MoveHelper<false, false, true, T> { // strings and similar
99 static void Move(T* src, T* dest) {
100 *dest = std::move(*src);
101 }
102};
103
104// MapEntryImpl is used to implement parsing and serialization of map entries.
105// It uses Curious Recursive Template Pattern (CRTP) to provide the type of
106// the eventual code to the template code.
107template <typename Derived, typename Base, typename Key, typename Value,
108 WireFormatLite::FieldType kKeyFieldType,
109 WireFormatLite::FieldType kValueFieldType>
110class MapEntryImpl : public Base {
111 public:
112 typedef MapEntryFuncs<Key, Value, kKeyFieldType, kValueFieldType> Funcs;
113
114 protected:
115 // Provide utilities to parse/serialize key/value. Provide utilities to
116 // manipulate internal stored type.
117 typedef MapTypeHandler<kKeyFieldType, Key> KeyTypeHandler;
118 typedef MapTypeHandler<kValueFieldType, Value> ValueTypeHandler;
119
120 // Define internal memory layout. Strings and messages are stored as
121 // pointers, while other types are stored as values.
122 typedef typename KeyTypeHandler::TypeOnMemory KeyOnMemory;
123 typedef typename ValueTypeHandler::TypeOnMemory ValueOnMemory;
124
125 // Enum type cannot be used for MapTypeHandler::Read. Define a type
126 // which will replace Enum with int.
127 typedef typename KeyTypeHandler::MapEntryAccessorType KeyMapEntryAccessorType;
128 typedef
129 typename ValueTypeHandler::MapEntryAccessorType ValueMapEntryAccessorType;
130
131 // Constants for field number.
132 static const int kKeyFieldNumber = 1;
133 static const int kValueFieldNumber = 2;
134
135 // Constants for field tag.
136 static const uint8_t kKeyTag =
137 GOOGLE_PROTOBUF_WIRE_FORMAT_MAKE_TAG(kKeyFieldNumber, KeyTypeHandler::kWireType);
138 static const uint8_t kValueTag = GOOGLE_PROTOBUF_WIRE_FORMAT_MAKE_TAG(
139 kValueFieldNumber, ValueTypeHandler::kWireType);
140 static const size_t kTagSize = 1;
141
142 public:
143 // Work-around for a compiler bug (see repeated_field.h).
144 typedef void MapEntryHasMergeTypeTrait;
145 typedef Derived EntryType;
146 typedef Key EntryKeyType;
147 typedef Value EntryValueType;
148 static const WireFormatLite::FieldType kEntryKeyFieldType = kKeyFieldType;
149 static const WireFormatLite::FieldType kEntryValueFieldType = kValueFieldType;
150
151 constexpr MapEntryImpl()
152 : key_(KeyTypeHandler::Constinit()),
153 value_(ValueTypeHandler::Constinit()),
154 _has_bits_{} {}
155
156 explicit MapEntryImpl(Arena* arena)
157 : Base(arena),
158 key_(KeyTypeHandler::Constinit()),
159 value_(ValueTypeHandler::Constinit()),
160 _has_bits_{} {}
161
162 ~MapEntryImpl() override {
163 if (Base::GetArenaForAllocation() != nullptr) return;
164 KeyTypeHandler::DeleteNoArena(key_);
165 ValueTypeHandler::DeleteNoArena(value_);
166 }
167
168 // accessors ======================================================
169
170 virtual inline const KeyMapEntryAccessorType& key() const {
171 return KeyTypeHandler::GetExternalReference(key_);
172 }
173 virtual inline const ValueMapEntryAccessorType& value() const {
174 return ValueTypeHandler::DefaultIfNotInitialized(value_);
175 }
176 inline KeyMapEntryAccessorType* mutable_key() {
177 set_has_key();
178 return KeyTypeHandler::EnsureMutable(&key_, Base::GetArenaForAllocation());
179 }
180 inline ValueMapEntryAccessorType* mutable_value() {
181 set_has_value();
182 return ValueTypeHandler::EnsureMutable(&value_,
183 Base::GetArenaForAllocation());
184 }
185
186 // implements MessageLite =========================================
187
188 // MapEntryImpl is for implementation only and this function isn't called
189 // anywhere. Just provide a fake implementation here for MessageLite.
190 std::string GetTypeName() const override { return ""; }
191
192 void CheckTypeAndMergeFrom(const MessageLite& other) override {
193 MergeFromInternal(from: *::google::protobuf::internal::DownCast<const Derived*>(&other));
194 }
195
196 const char* _InternalParse(const char* ptr, ParseContext* ctx) final {
197 while (!ctx->Done(ptr: &ptr)) {
198 uint32_t tag;
199 ptr = ReadTag(p: ptr, out: &tag);
200 GOOGLE_PROTOBUF_PARSER_ASSERT(ptr);
201 if (tag == kKeyTag) {
202 set_has_key();
203 KeyMapEntryAccessorType* key = mutable_key();
204 ptr = KeyTypeHandler::Read(ptr, ctx, key);
205 if (!Derived::ValidateKey(key)) return nullptr;
206 } else if (tag == kValueTag) {
207 set_has_value();
208 ValueMapEntryAccessorType* value = mutable_value();
209 ptr = ValueTypeHandler::Read(ptr, ctx, value);
210 if (!Derived::ValidateValue(value)) return nullptr;
211 } else {
212 if (tag == 0 || WireFormatLite::GetTagWireType(tag) ==
213 WireFormatLite::WIRETYPE_END_GROUP) {
214 ctx->SetLastTag(tag);
215 return ptr;
216 }
217 ptr = UnknownFieldParse(tag, unknown: static_cast<std::string*>(nullptr), ptr,
218 ctx);
219 }
220 GOOGLE_PROTOBUF_PARSER_ASSERT(ptr);
221 }
222 return ptr;
223 }
224
225 size_t ByteSizeLong() const override {
226 size_t size = 0;
227 size += kTagSize + static_cast<size_t>(KeyTypeHandler::ByteSize(key()));
228 size += kTagSize + static_cast<size_t>(ValueTypeHandler::ByteSize(value()));
229 return size;
230 }
231
232 ::uint8_t* _InternalSerialize(
233 ::uint8_t* ptr, io::EpsCopyOutputStream* stream) const override {
234 ptr = KeyTypeHandler::Write(kKeyFieldNumber, key(), ptr, stream);
235 return ValueTypeHandler::Write(kValueFieldNumber, value(), ptr, stream);
236 }
237
238 // Don't override SerializeWithCachedSizesToArray. Use MessageLite's.
239
240 int GetCachedSize() const override {
241 int size = 0;
242 size += has_key() ? static_cast<int>(kTagSize) +
243 KeyTypeHandler::GetCachedSize(key())
244 : 0;
245 size += has_value() ? static_cast<int>(kTagSize) +
246 ValueTypeHandler::GetCachedSize(value())
247 : 0;
248 return size;
249 }
250
251 bool IsInitialized() const override {
252 return ValueTypeHandler::IsInitialized(value_);
253 }
254
255 Base* New(Arena* arena) const override {
256 Derived* entry = Arena::CreateMessage<Derived>(arena);
257 return entry;
258 }
259
260 protected:
261 // We can't declare this function directly here as it would hide the other
262 // overload (const Message&).
263 void MergeFromInternal(const MapEntryImpl& from) {
264 if (from._has_bits_[0]) {
265 if (from.has_key()) {
266 KeyTypeHandler::EnsureMutable(&key_, Base::GetArenaForAllocation());
267 KeyTypeHandler::Merge(from.key(), &key_, Base::GetArenaForAllocation());
268 set_has_key();
269 }
270 if (from.has_value()) {
271 ValueTypeHandler::EnsureMutable(&value_, Base::GetArenaForAllocation());
272 ValueTypeHandler::Merge(from.value(), &value_,
273 Base::GetArenaForAllocation());
274 set_has_value();
275 }
276 }
277 }
278
279 public:
280 void Clear() override {
281 KeyTypeHandler::Clear(&key_, Base::GetArenaForAllocation());
282 ValueTypeHandler::Clear(&value_, Base::GetArenaForAllocation());
283 clear_has_key();
284 clear_has_value();
285 }
286
287 // Parsing using MergePartialFromCodedStream, above, is not as
288 // efficient as it could be. This helper class provides a speedier way.
289 template <typename MapField, typename Map>
290 class Parser {
291 public:
292 explicit Parser(MapField* mf) : mf_(mf), map_(mf->MutableMap()) {}
293 ~Parser() {
294 if (entry_ != nullptr && entry_->GetArenaForAllocation() == nullptr)
295 delete entry_;
296 }
297
298 const char* _InternalParse(const char* ptr, ParseContext* ctx) {
299 if (PROTOBUF_PREDICT_TRUE(!ctx->Done(&ptr) && *ptr == kKeyTag)) {
300 ptr = KeyTypeHandler::Read(ptr + 1, ctx, &key_);
301 if (PROTOBUF_PREDICT_FALSE(!ptr || !Derived::ValidateKey(&key_))) {
302 return nullptr;
303 }
304 if (PROTOBUF_PREDICT_TRUE(!ctx->Done(&ptr) && *ptr == kValueTag)) {
305 typename Map::size_type map_size = map_->size();
306 value_ptr_ = &(*map_)[key_];
307 if (PROTOBUF_PREDICT_TRUE(map_size != map_->size())) {
308 using T =
309 typename MapIf<ValueTypeHandler::kIsEnum, int*, Value*>::type;
310 ptr = ValueTypeHandler::Read(ptr + 1, ctx,
311 reinterpret_cast<T>(value_ptr_));
312 if (PROTOBUF_PREDICT_FALSE(!ptr ||
313 !Derived::ValidateValue(value_ptr_))) {
314 map_->erase(key_); // Failure! Undo insertion.
315 return nullptr;
316 }
317 if (PROTOBUF_PREDICT_TRUE(ctx->Done(&ptr))) return ptr;
318 if (!ptr) return nullptr;
319 NewEntry();
320 ValueMover::Move(value_ptr_, entry_->mutable_value());
321 map_->erase(key_);
322 goto move_key;
323 }
324 } else {
325 if (!ptr) return nullptr;
326 }
327 NewEntry();
328 move_key:
329 KeyMover::Move(&key_, entry_->mutable_key());
330 } else {
331 if (!ptr) return nullptr;
332 NewEntry();
333 }
334 ptr = entry_->_InternalParse(ptr, ctx);
335 if (ptr) UseKeyAndValueFromEntry();
336 return ptr;
337 }
338
339 template <typename UnknownType>
340 const char* ParseWithEnumValidation(const char* ptr, ParseContext* ctx,
341 bool (*is_valid)(int),
342 uint32_t field_num,
343 InternalMetadata* metadata) {
344 auto entry = NewEntry();
345 ptr = entry->_InternalParse(ptr, ctx);
346 if (!ptr) return nullptr;
347 if (is_valid(entry->value())) {
348 UseKeyAndValueFromEntry();
349 } else {
350 WriteLengthDelimited(field_num, entry->SerializeAsString(),
351 metadata->mutable_unknown_fields<UnknownType>());
352 }
353 return ptr;
354 }
355
356 MapEntryImpl* NewEntry() { return entry_ = mf_->NewEntry(); }
357
358 const Key& key() const { return key_; }
359 const Value& value() const { return *value_ptr_; }
360
361 const Key& entry_key() const { return entry_->key(); }
362 const Value& entry_value() const { return entry_->value(); }
363
364 private:
365 void UseKeyAndValueFromEntry() {
366 // Update key_ in case we need it later (because key() is called).
367 // This is potentially inefficient, especially if the key is
368 // expensive to copy (e.g., a long string), but this is a cold
369 // path, so it's not a big deal.
370 key_ = entry_->key();
371 value_ptr_ = &(*map_)[key_];
372 ValueMover::Move(entry_->mutable_value(), value_ptr_);
373 }
374
375 // After reading a key and value successfully, and inserting that data
376 // into map_, we are not at the end of the input. This is unusual, but
377 // allowed by the spec.
378 bool ReadBeyondKeyValuePair(io::CodedInputStream* input) PROTOBUF_COLD {
379 NewEntry();
380 ValueMover::Move(value_ptr_, entry_->mutable_value());
381 map_->erase(key_);
382 KeyMover::Move(&key_, entry_->mutable_key());
383 const bool result = entry_->MergePartialFromCodedStream(input);
384 if (result) UseKeyAndValueFromEntry();
385 return result;
386 }
387
388 typedef MoveHelper<KeyTypeHandler::kIsEnum, KeyTypeHandler::kIsMessage,
389 KeyTypeHandler::kWireType ==
390 WireFormatLite::WIRETYPE_LENGTH_DELIMITED,
391 Key>
392 KeyMover;
393 typedef MoveHelper<ValueTypeHandler::kIsEnum, ValueTypeHandler::kIsMessage,
394 ValueTypeHandler::kWireType ==
395 WireFormatLite::WIRETYPE_LENGTH_DELIMITED,
396 Value>
397 ValueMover;
398
399 MapField* const mf_;
400 Map* const map_;
401 Key key_;
402 Value* value_ptr_;
403 MapEntryImpl* entry_ = nullptr;
404 };
405
406 protected:
407 void set_has_key() { _has_bits_[0] |= 0x00000001u; }
408 bool has_key() const { return (_has_bits_[0] & 0x00000001u) != 0; }
409 void clear_has_key() { _has_bits_[0] &= ~0x00000001u; }
410 void set_has_value() { _has_bits_[0] |= 0x00000002u; }
411 bool has_value() const { return (_has_bits_[0] & 0x00000002u) != 0; }
412 void clear_has_value() { _has_bits_[0] &= ~0x00000002u; }
413
414 public:
415 inline Arena* GetArena() const { return Base::GetArena(); }
416
417 protected: // Needed for constructing tables
418 KeyOnMemory key_;
419 ValueOnMemory value_;
420 uint32_t _has_bits_[1];
421
422 private:
423 friend class ::PROTOBUF_NAMESPACE_ID::Arena;
424 typedef void InternalArenaConstructable_;
425 typedef void DestructorSkippable_;
426 template <typename C, typename K, typename V, WireFormatLite::FieldType,
427 WireFormatLite::FieldType>
428 friend class internal::MapEntry;
429 template <typename C, typename K, typename V, WireFormatLite::FieldType,
430 WireFormatLite::FieldType>
431 friend class internal::MapFieldLite;
432
433 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(MapEntryImpl);
434};
435
436template <typename T, typename Key, typename Value,
437 WireFormatLite::FieldType kKeyFieldType,
438 WireFormatLite::FieldType kValueFieldType>
439class MapEntryLite : public MapEntryImpl<T, MessageLite, Key, Value,
440 kKeyFieldType, kValueFieldType> {
441 public:
442 typedef MapEntryImpl<T, MessageLite, Key, Value, kKeyFieldType,
443 kValueFieldType>
444 SuperType;
445 constexpr MapEntryLite() {}
446 explicit MapEntryLite(Arena* arena) : SuperType(arena) {}
447 ~MapEntryLite() override {
448 MessageLite::_internal_metadata_.template Delete<std::string>();
449 }
450 void MergeFrom(const MapEntryLite& other) { MergeFromInternal(other); }
451
452 private:
453 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(MapEntryLite);
454};
455
456// Helpers for deterministic serialization =============================
457
458// Iterator base for MapSorterFlat and MapSorterPtr.
459template <typename storage_type>
460struct MapSorterIt {
461 storage_type* ptr;
462 MapSorterIt(storage_type* ptr) : ptr(ptr) {}
463 bool operator==(const MapSorterIt& other) const { return ptr == other.ptr; }
464 bool operator!=(const MapSorterIt& other) const { return !(*this == other); }
465 MapSorterIt& operator++() { ++ptr; return *this; }
466 MapSorterIt operator++(int) { auto other = *this; ++ptr; return other; }
467 MapSorterIt operator+(int v) { return MapSorterIt{ptr + v}; }
468};
469
470// MapSorterFlat stores keys inline with pointers to map entries, so that
471// keys can be compared without indirection. This type is used for maps with
472// keys that are not strings.
473template <typename MapT>
474class MapSorterFlat {
475 public:
476 using value_type = typename MapT::value_type;
477 using storage_type = std::pair<typename MapT::key_type, const value_type*>;
478
479 // This const_iterator dereferenes to the map entry stored in the sorting
480 // array pairs. This is the same interface as the Map::const_iterator type,
481 // and allows generated code to use the same loop body with either form:
482 // for (const auto& entry : map) { ... }
483 // for (const auto& entry : MapSorterFlat(map)) { ... }
484 struct const_iterator : public MapSorterIt<storage_type> {
485 using pointer = const typename MapT::value_type*;
486 using reference = const typename MapT::value_type&;
487 using MapSorterIt<storage_type>::MapSorterIt;
488
489 pointer operator->() const { return this->ptr->second; }
490 reference operator*() const { return *this->operator->(); }
491 };
492
493 explicit MapSorterFlat(const MapT& m)
494 : size_(m.size()), items_(size_ ? new storage_type[size_] : nullptr) {
495 if (!size_) return;
496 storage_type* it = &items_[0];
497 for (const auto& entry : m) {
498 *it++ = {entry.first, &entry};
499 }
500 std::sort(&items_[0], &items_[size_],
501 [](const storage_type& a, const storage_type& b) {
502 return a.first < b.first;
503 });
504 }
505 size_t size() const { return size_; }
506 const_iterator begin() const { return {items_.get()}; }
507 const_iterator end() const { return {items_.get() + size_}; }
508
509 private:
510 size_t size_;
511 std::unique_ptr<storage_type[]> items_;
512};
513
514// MapSorterPtr stores and sorts pointers to map entries. This type is used for
515// maps with keys that are strings.
516template <typename MapT>
517class MapSorterPtr {
518 public:
519 using value_type = typename MapT::value_type;
520 using storage_type = const typename MapT::value_type*;
521
522 // This const_iterator dereferenes the map entry pointer stored in the sorting
523 // array. This is the same interface as the Map::const_iterator type, and
524 // allows generated code to use the same loop body with either form:
525 // for (const auto& entry : map) { ... }
526 // for (const auto& entry : MapSorterPtr(map)) { ... }
527 struct const_iterator : public MapSorterIt<storage_type> {
528 using pointer = const typename MapT::value_type*;
529 using reference = const typename MapT::value_type&;
530 using MapSorterIt<storage_type>::MapSorterIt;
531
532 pointer operator->() const { return *this->ptr; }
533 reference operator*() const { return *this->operator->(); }
534 };
535
536 explicit MapSorterPtr(const MapT& m)
537 : size_(m.size()), items_(size_ ? new storage_type[size_] : nullptr) {
538 if (!size_) return;
539 storage_type* it = &items_[0];
540 for (const auto& entry : m) {
541 *it++ = &entry;
542 }
543 std::sort(&items_[0], &items_[size_],
544 [](const storage_type& a, const storage_type& b) {
545 return a->first < b->first;
546 });
547 }
548 size_t size() const { return size_; }
549 const_iterator begin() const { return {items_.get()}; }
550 const_iterator end() const { return {items_.get() + size_}; }
551
552 private:
553 size_t size_;
554 std::unique_ptr<storage_type[]> items_;
555};
556
557} // namespace internal
558} // namespace protobuf
559} // namespace google
560
561#include <google/protobuf/port_undef.inc>
562
563#endif // GOOGLE_PROTOBUF_MAP_ENTRY_LITE_H__
564