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// Author: jschorr@google.com (Joseph Schorr)
32// Based on original Protocol Buffers design by
33// Sanjay Ghemawat, Jeff Dean, and others.
34
35#include <google/protobuf/util/message_differencer.h>
36
37#include <algorithm>
38#include <cstddef>
39#include <cstdint>
40#include <functional>
41#include <limits>
42#include <memory>
43#include <utility>
44
45#include <google/protobuf/stubs/logging.h>
46#include <google/protobuf/stubs/common.h>
47#include <google/protobuf/io/printer.h>
48#include <google/protobuf/io/zero_copy_stream.h>
49#include <google/protobuf/io/zero_copy_stream_impl.h>
50#include <google/protobuf/descriptor.pb.h>
51#include <google/protobuf/descriptor.h>
52#include <google/protobuf/dynamic_message.h>
53#include <google/protobuf/generated_enum_reflection.h>
54#include <google/protobuf/map_field.h>
55#include <google/protobuf/message.h>
56#include <google/protobuf/text_format.h>
57#include <google/protobuf/stubs/strutil.h>
58#include <google/protobuf/stubs/stringprintf.h>
59#include <google/protobuf/util/field_comparator.h>
60
61// Always include as last one, otherwise it can break compilation
62#include <google/protobuf/port_def.inc>
63
64namespace google {
65namespace protobuf {
66
67namespace util {
68
69namespace {
70
71std::string PrintShortTextFormat(const google::protobuf::Message& message) {
72 std::string debug_string;
73
74 google::protobuf::TextFormat::Printer printer;
75 printer.SetSingleLineMode(true);
76 printer.SetExpandAny(true);
77
78 printer.PrintToString(message, output: &debug_string);
79 // Single line mode currently might have an extra space at the end.
80 if (!debug_string.empty() && debug_string[debug_string.size() - 1] == ' ') {
81 debug_string.resize(n: debug_string.size() - 1);
82 }
83
84 return debug_string;
85}
86
87} // namespace
88
89// A reporter to report the total number of diffs.
90// TODO(ykzhu): we can improve this to take into account the value differencers.
91class NumDiffsReporter : public google::protobuf::util::MessageDifferencer::Reporter {
92 public:
93 NumDiffsReporter() : num_diffs_(0) {}
94
95 // Returns the total number of diffs.
96 int32_t GetNumDiffs() const { return num_diffs_; }
97 void Reset() { num_diffs_ = 0; }
98
99 // Report that a field has been added into Message2.
100 void ReportAdded(
101 const google::protobuf::Message& /* message1 */,
102 const google::protobuf::Message& /* message2 */,
103 const std::vector<google::protobuf::util::MessageDifferencer::SpecificField>&
104 /*field_path*/) override {
105 ++num_diffs_;
106 }
107
108 // Report that a field has been deleted from Message1.
109 void ReportDeleted(
110 const google::protobuf::Message& /* message1 */,
111 const google::protobuf::Message& /* message2 */,
112 const std::vector<google::protobuf::util::MessageDifferencer::SpecificField>&
113 /*field_path*/) override {
114 ++num_diffs_;
115 }
116
117 // Report that the value of a field has been modified.
118 void ReportModified(
119 const google::protobuf::Message& /* message1 */,
120 const google::protobuf::Message& /* message2 */,
121 const std::vector<google::protobuf::util::MessageDifferencer::SpecificField>&
122 /*field_path*/) override {
123 ++num_diffs_;
124 }
125
126 private:
127 int32_t num_diffs_;
128};
129
130// When comparing a repeated field as map, MultipleFieldMapKeyComparator can
131// be used to specify multiple fields as key for key comparison.
132// Two elements of a repeated field will be regarded as having the same key
133// iff they have the same value for every specified key field.
134// Note that you can also specify only one field as key.
135class MessageDifferencer::MultipleFieldsMapKeyComparator
136 : public MessageDifferencer::MapKeyComparator {
137 public:
138 MultipleFieldsMapKeyComparator(
139 MessageDifferencer* message_differencer,
140 const std::vector<std::vector<const FieldDescriptor*> >& key_field_paths)
141 : message_differencer_(message_differencer),
142 key_field_paths_(key_field_paths) {
143 GOOGLE_CHECK(!key_field_paths_.empty());
144 for (const auto& path : key_field_paths_) {
145 GOOGLE_CHECK(!path.empty());
146 }
147 }
148 MultipleFieldsMapKeyComparator(MessageDifferencer* message_differencer,
149 const FieldDescriptor* key)
150 : message_differencer_(message_differencer) {
151 std::vector<const FieldDescriptor*> key_field_path;
152 key_field_path.push_back(x: key);
153 key_field_paths_.push_back(x: key_field_path);
154 }
155 bool IsMatch(const Message& message1, const Message& message2,
156 const std::vector<SpecificField>& parent_fields) const override {
157 for (const auto& path : key_field_paths_) {
158 if (!IsMatchInternal(message1, message2, parent_fields, key_field_path: path, path_index: 0)) {
159 return false;
160 }
161 }
162 return true;
163 }
164
165 private:
166 bool IsMatchInternal(
167 const Message& message1, const Message& message2,
168 const std::vector<SpecificField>& parent_fields,
169 const std::vector<const FieldDescriptor*>& key_field_path,
170 int path_index) const {
171 const FieldDescriptor* field = key_field_path[path_index];
172 std::vector<SpecificField> current_parent_fields(parent_fields);
173 if (path_index == static_cast<int64_t>(key_field_path.size() - 1)) {
174 if (field->is_map()) {
175 return message_differencer_->CompareMapField(message1, message2, field,
176 parent_fields: &current_parent_fields);
177 } else if (field->is_repeated()) {
178 return message_differencer_->CompareRepeatedField(
179 message1, message2, field, parent_fields: &current_parent_fields);
180 } else {
181 return message_differencer_->CompareFieldValueUsingParentFields(
182 message1, message2, field, index1: -1, index2: -1, parent_fields: &current_parent_fields);
183 }
184 } else {
185 const Reflection* reflection1 = message1.GetReflection();
186 const Reflection* reflection2 = message2.GetReflection();
187 bool has_field1 = reflection1->HasField(message: message1, field);
188 bool has_field2 = reflection2->HasField(message: message2, field);
189 if (!has_field1 && !has_field2) {
190 return true;
191 }
192 if (has_field1 != has_field2) {
193 return false;
194 }
195 SpecificField specific_field;
196 specific_field.field = field;
197 current_parent_fields.push_back(x: specific_field);
198 return IsMatchInternal(message1: reflection1->GetMessage(message: message1, field),
199 message2: reflection2->GetMessage(message: message2, field),
200 parent_fields: current_parent_fields, key_field_path,
201 path_index: path_index + 1);
202 }
203 }
204 MessageDifferencer* message_differencer_;
205 std::vector<std::vector<const FieldDescriptor*> > key_field_paths_;
206 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(MultipleFieldsMapKeyComparator);
207};
208
209// Preserve the order when treating repeated field as SMART_LIST. The current
210// implementation is to find the longest matching sequence from the first
211// element. The optimal solution requires to use //util/diff/lcs.h, which is
212// not open sourced yet. Overwrite this method if you want to have that.
213// TODO(ykzhu): change to use LCS once it is open sourced.
214void MatchIndicesPostProcessorForSmartList(std::vector<int>* match_list1,
215 std::vector<int>* match_list2) {
216 int last_matched_index = -1;
217 for (size_t i = 0; i < match_list1->size(); ++i) {
218 if (match_list1->at(n: i) < 0) {
219 continue;
220 }
221 if (last_matched_index < 0 || match_list1->at(n: i) > last_matched_index) {
222 last_matched_index = match_list1->at(n: i);
223 } else {
224 match_list2->at(n: match_list1->at(n: i)) = -1;
225 match_list1->at(n: i) = -1;
226 }
227 }
228}
229
230void AddSpecificIndex(
231 google::protobuf::util::MessageDifferencer::SpecificField* specific_field,
232 const Message& message, const FieldDescriptor* field, int index) {
233 if (field->is_map()) {
234 const Reflection* reflection = message.GetReflection();
235 specific_field->map_entry1 =
236 &reflection->GetRepeatedMessage(message, field, index);
237 }
238 specific_field->index = index;
239}
240
241void AddSpecificNewIndex(
242 google::protobuf::util::MessageDifferencer::SpecificField* specific_field,
243 const Message& message, const FieldDescriptor* field, int index) {
244 if (field->is_map()) {
245 const Reflection* reflection = message.GetReflection();
246 specific_field->map_entry2 =
247 &reflection->GetRepeatedMessage(message, field, index);
248 }
249 specific_field->new_index = index;
250}
251
252MessageDifferencer::MapEntryKeyComparator::MapEntryKeyComparator(
253 MessageDifferencer* message_differencer)
254 : message_differencer_(message_differencer) {}
255
256bool MessageDifferencer::MapEntryKeyComparator::IsMatch(
257 const Message& message1, const Message& message2,
258 const std::vector<SpecificField>& parent_fields) const {
259 // Map entry has its key in the field with tag 1. See the comment for
260 // map_entry in MessageOptions.
261 const FieldDescriptor* key = message1.GetDescriptor()->FindFieldByNumber(number: 1);
262 // If key is not present in message1 and we're doing partial comparison or if
263 // map key is explicitly ignored treat the field as set instead,
264 const bool treat_as_set =
265 (message_differencer_->scope() == PARTIAL &&
266 !message1.GetReflection()->HasField(message: message1, field: key)) ||
267 message_differencer_->IsIgnored(message1, message2, field: key, parent_fields);
268
269 std::vector<SpecificField> current_parent_fields(parent_fields);
270 if (treat_as_set) {
271 return message_differencer_->Compare(message1, message2,
272 parent_fields: &current_parent_fields);
273 }
274 return message_differencer_->CompareFieldValueUsingParentFields(
275 message1, message2, field: key, index1: -1, index2: -1, parent_fields: &current_parent_fields);
276}
277
278bool MessageDifferencer::Equals(const Message& message1,
279 const Message& message2) {
280 MessageDifferencer differencer;
281
282 return differencer.Compare(message1, message2);
283}
284
285bool MessageDifferencer::Equivalent(const Message& message1,
286 const Message& message2) {
287 MessageDifferencer differencer;
288 differencer.set_message_field_comparison(MessageDifferencer::EQUIVALENT);
289
290 return differencer.Compare(message1, message2);
291}
292
293bool MessageDifferencer::ApproximatelyEquals(const Message& message1,
294 const Message& message2) {
295 MessageDifferencer differencer;
296 differencer.set_float_comparison(MessageDifferencer::APPROXIMATE);
297
298 return differencer.Compare(message1, message2);
299}
300
301bool MessageDifferencer::ApproximatelyEquivalent(const Message& message1,
302 const Message& message2) {
303 MessageDifferencer differencer;
304 differencer.set_message_field_comparison(MessageDifferencer::EQUIVALENT);
305 differencer.set_float_comparison(MessageDifferencer::APPROXIMATE);
306
307 return differencer.Compare(message1, message2);
308}
309
310// ===========================================================================
311
312MessageDifferencer::MessageDifferencer()
313 : reporter_(NULL),
314 message_field_comparison_(EQUAL),
315 scope_(FULL),
316 repeated_field_comparison_(AS_LIST),
317 map_entry_key_comparator_(this),
318 report_matches_(false),
319 report_moves_(true),
320 report_ignores_(true),
321 output_string_(nullptr),
322 match_indices_for_smart_list_callback_(
323 MatchIndicesPostProcessorForSmartList) {}
324
325MessageDifferencer::~MessageDifferencer() {
326 for (MapKeyComparator* comparator : owned_key_comparators_) {
327 delete comparator;
328 }
329 for (IgnoreCriteria* criteria : ignore_criteria_) {
330 delete criteria;
331 }
332}
333
334void MessageDifferencer::set_field_comparator(FieldComparator* comparator) {
335 GOOGLE_CHECK(comparator) << "Field comparator can't be NULL.";
336 field_comparator_kind_ = kFCBase;
337 field_comparator_.base = comparator;
338}
339
340#ifdef PROTOBUF_FUTURE_BREAKING_CHANGES
341void MessageDifferencer::set_field_comparator(
342 DefaultFieldComparator* comparator) {
343 GOOGLE_CHECK(comparator) << "Field comparator can't be NULL.";
344 field_comparator_kind_ = kFCDefault;
345 field_comparator_.default_impl = comparator;
346}
347#endif // PROTOBUF_FUTURE_BREAKING_CHANGES
348
349void MessageDifferencer::set_message_field_comparison(
350 MessageFieldComparison comparison) {
351 message_field_comparison_ = comparison;
352}
353
354MessageDifferencer::MessageFieldComparison
355MessageDifferencer::message_field_comparison() const {
356 return message_field_comparison_;
357}
358
359void MessageDifferencer::set_scope(Scope scope) { scope_ = scope; }
360
361MessageDifferencer::Scope MessageDifferencer::scope() const { return scope_; }
362
363void MessageDifferencer::set_float_comparison(FloatComparison comparison) {
364 default_field_comparator_.set_float_comparison(
365 comparison == EXACT ? DefaultFieldComparator::EXACT
366 : DefaultFieldComparator::APPROXIMATE);
367}
368
369void MessageDifferencer::set_repeated_field_comparison(
370 RepeatedFieldComparison comparison) {
371 repeated_field_comparison_ = comparison;
372}
373
374MessageDifferencer::RepeatedFieldComparison
375MessageDifferencer::repeated_field_comparison() const {
376 return repeated_field_comparison_;
377}
378
379void MessageDifferencer::CheckRepeatedFieldComparisons(
380 const FieldDescriptor* field,
381 const RepeatedFieldComparison& new_comparison) {
382 GOOGLE_CHECK(field->is_repeated())
383 << "Field must be repeated: " << field->full_name();
384 const MapKeyComparator* key_comparator = GetMapKeyComparator(field);
385 GOOGLE_CHECK(key_comparator == NULL)
386 << "Cannot treat this repeated field as both MAP and " << new_comparison
387 << " for comparison. Field name is: " << field->full_name();
388}
389
390void MessageDifferencer::TreatAsSet(const FieldDescriptor* field) {
391 CheckRepeatedFieldComparisons(field, new_comparison: AS_SET);
392 repeated_field_comparisons_[field] = AS_SET;
393}
394
395void MessageDifferencer::TreatAsSmartSet(const FieldDescriptor* field) {
396 CheckRepeatedFieldComparisons(field, new_comparison: AS_SMART_SET);
397 repeated_field_comparisons_[field] = AS_SMART_SET;
398}
399
400void MessageDifferencer::SetMatchIndicesForSmartListCallback(
401 std::function<void(std::vector<int>*, std::vector<int>*)> callback) {
402 match_indices_for_smart_list_callback_ = callback;
403}
404
405void MessageDifferencer::TreatAsList(const FieldDescriptor* field) {
406 CheckRepeatedFieldComparisons(field, new_comparison: AS_LIST);
407 repeated_field_comparisons_[field] = AS_LIST;
408}
409
410void MessageDifferencer::TreatAsSmartList(const FieldDescriptor* field) {
411 CheckRepeatedFieldComparisons(field, new_comparison: AS_SMART_LIST);
412 repeated_field_comparisons_[field] = AS_SMART_LIST;
413}
414
415void MessageDifferencer::TreatAsMap(const FieldDescriptor* field,
416 const FieldDescriptor* key) {
417 GOOGLE_CHECK_EQ(FieldDescriptor::CPPTYPE_MESSAGE, field->cpp_type())
418 << "Field has to be message type. Field name is: " << field->full_name();
419 GOOGLE_CHECK(key->containing_type() == field->message_type())
420 << key->full_name()
421 << " must be a direct subfield within the repeated field "
422 << field->full_name() << ", not " << key->containing_type()->full_name();
423 GOOGLE_CHECK(repeated_field_comparisons_.find(field) ==
424 repeated_field_comparisons_.end())
425 << "Cannot treat the same field as both "
426 << repeated_field_comparisons_[field]
427 << " and MAP. Field name is: " << field->full_name();
428 MapKeyComparator* key_comparator =
429 new MultipleFieldsMapKeyComparator(this, key);
430 owned_key_comparators_.push_back(x: key_comparator);
431 map_field_key_comparator_[field] = key_comparator;
432}
433
434void MessageDifferencer::TreatAsMapWithMultipleFieldsAsKey(
435 const FieldDescriptor* field,
436 const std::vector<const FieldDescriptor*>& key_fields) {
437 std::vector<std::vector<const FieldDescriptor*> > key_field_paths;
438 for (const FieldDescriptor* key_filed : key_fields) {
439 std::vector<const FieldDescriptor*> key_field_path;
440 key_field_path.push_back(x: key_filed);
441 key_field_paths.push_back(x: key_field_path);
442 }
443 TreatAsMapWithMultipleFieldPathsAsKey(field, key_field_paths);
444}
445
446void MessageDifferencer::TreatAsMapWithMultipleFieldPathsAsKey(
447 const FieldDescriptor* field,
448 const std::vector<std::vector<const FieldDescriptor*> >& key_field_paths) {
449 GOOGLE_CHECK(field->is_repeated())
450 << "Field must be repeated: " << field->full_name();
451 GOOGLE_CHECK_EQ(FieldDescriptor::CPPTYPE_MESSAGE, field->cpp_type())
452 << "Field has to be message type. Field name is: " << field->full_name();
453 for (const auto& key_field_path : key_field_paths) {
454 for (size_t j = 0; j < key_field_path.size(); ++j) {
455 const FieldDescriptor* parent_field =
456 j == 0 ? field : key_field_path[j - 1];
457 const FieldDescriptor* child_field = key_field_path[j];
458 GOOGLE_CHECK(child_field->containing_type() == parent_field->message_type())
459 << child_field->full_name()
460 << " must be a direct subfield within the field: "
461 << parent_field->full_name();
462 if (j != 0) {
463 GOOGLE_CHECK_EQ(FieldDescriptor::CPPTYPE_MESSAGE, parent_field->cpp_type())
464 << parent_field->full_name() << " has to be of type message.";
465 GOOGLE_CHECK(!parent_field->is_repeated())
466 << parent_field->full_name() << " cannot be a repeated field.";
467 }
468 }
469 }
470 GOOGLE_CHECK(repeated_field_comparisons_.find(field) ==
471 repeated_field_comparisons_.end())
472 << "Cannot treat the same field as both "
473 << repeated_field_comparisons_[field]
474 << " and MAP. Field name is: " << field->full_name();
475 MapKeyComparator* key_comparator =
476 new MultipleFieldsMapKeyComparator(this, key_field_paths);
477 owned_key_comparators_.push_back(x: key_comparator);
478 map_field_key_comparator_[field] = key_comparator;
479}
480
481void MessageDifferencer::TreatAsMapUsingKeyComparator(
482 const FieldDescriptor* field, const MapKeyComparator* key_comparator) {
483 GOOGLE_CHECK(field->is_repeated())
484 << "Field must be repeated: " << field->full_name();
485 GOOGLE_CHECK(repeated_field_comparisons_.find(field) ==
486 repeated_field_comparisons_.end())
487 << "Cannot treat the same field as both "
488 << repeated_field_comparisons_[field]
489 << " and MAP. Field name is: " << field->full_name();
490 map_field_key_comparator_[field] = key_comparator;
491}
492
493void MessageDifferencer::AddIgnoreCriteria(IgnoreCriteria* ignore_criteria) {
494 ignore_criteria_.push_back(x: ignore_criteria);
495}
496
497void MessageDifferencer::IgnoreField(const FieldDescriptor* field) {
498 ignored_fields_.insert(x: field);
499}
500
501void MessageDifferencer::SetFractionAndMargin(const FieldDescriptor* field,
502 double fraction, double margin) {
503 default_field_comparator_.SetFractionAndMargin(field, fraction, margin);
504}
505
506void MessageDifferencer::ReportDifferencesToString(std::string* output) {
507 GOOGLE_DCHECK(output) << "Specified output string was NULL";
508
509 output_string_ = output;
510 output_string_->clear();
511}
512
513void MessageDifferencer::ReportDifferencesTo(Reporter* reporter) {
514 // If an output string is set, clear it to prevent
515 // it superseding the specified reporter.
516 if (output_string_) {
517 output_string_ = NULL;
518 }
519
520 reporter_ = reporter;
521}
522
523bool MessageDifferencer::FieldBefore(const FieldDescriptor* field1,
524 const FieldDescriptor* field2) {
525 // Handle sentinel values (i.e. make sure NULLs are always ordered
526 // at the end of the list).
527 if (field1 == NULL) {
528 return false;
529 }
530
531 if (field2 == NULL) {
532 return true;
533 }
534
535 // Always order fields by their tag number
536 return (field1->number() < field2->number());
537}
538
539bool MessageDifferencer::Compare(const Message& message1,
540 const Message& message2) {
541 std::vector<SpecificField> parent_fields;
542
543 bool result = false;
544 // Setup the internal reporter if need be.
545 if (output_string_) {
546 io::StringOutputStream output_stream(output_string_);
547 StreamReporter reporter(&output_stream);
548 reporter.SetMessages(message1, message2);
549 reporter_ = &reporter;
550 result = Compare(message1, message2, parent_fields: &parent_fields);
551 reporter_ = NULL;
552 } else {
553 result = Compare(message1, message2, parent_fields: &parent_fields);
554 }
555 return result;
556}
557
558bool MessageDifferencer::CompareWithFields(
559 const Message& message1, const Message& message2,
560 const std::vector<const FieldDescriptor*>& message1_fields_arg,
561 const std::vector<const FieldDescriptor*>& message2_fields_arg) {
562 if (message1.GetDescriptor() != message2.GetDescriptor()) {
563 GOOGLE_LOG(DFATAL) << "Comparison between two messages with different "
564 << "descriptors.";
565 return false;
566 }
567
568 std::vector<SpecificField> parent_fields;
569
570 bool result = false;
571
572 FieldDescriptorArray message1_fields(message1_fields_arg.size() + 1);
573 FieldDescriptorArray message2_fields(message2_fields_arg.size() + 1);
574
575 std::copy(message1_fields_arg.cbegin(), message1_fields_arg.cend(),
576 message1_fields.begin());
577 std::copy(message2_fields_arg.cbegin(), message2_fields_arg.cend(),
578 message2_fields.begin());
579
580 // Append sentinel values.
581 message1_fields[message1_fields_arg.size()] = nullptr;
582 message2_fields[message2_fields_arg.size()] = nullptr;
583
584 std::sort(first: message1_fields.begin(), last: message1_fields.end(), comp: FieldBefore);
585 std::sort(first: message2_fields.begin(), last: message2_fields.end(), comp: FieldBefore);
586
587 // Setup the internal reporter if need be.
588 if (output_string_) {
589 io::StringOutputStream output_stream(output_string_);
590 StreamReporter reporter(&output_stream);
591 reporter_ = &reporter;
592 result = CompareRequestedFieldsUsingSettings(
593 message1, message2, message1_fields, message2_fields, parent_fields: &parent_fields);
594 reporter_ = NULL;
595 } else {
596 result = CompareRequestedFieldsUsingSettings(
597 message1, message2, message1_fields, message2_fields, parent_fields: &parent_fields);
598 }
599
600 return result;
601}
602
603bool MessageDifferencer::Compare(const Message& message1,
604 const Message& message2,
605 std::vector<SpecificField>* parent_fields) {
606 const Descriptor* descriptor1 = message1.GetDescriptor();
607 const Descriptor* descriptor2 = message2.GetDescriptor();
608 if (descriptor1 != descriptor2) {
609 GOOGLE_LOG(DFATAL) << "Comparison between two messages with different "
610 << "descriptors. " << descriptor1->full_name() << " vs "
611 << descriptor2->full_name();
612 return false;
613 }
614
615 // Expand google.protobuf.Any payload if possible.
616 if (descriptor1->full_name() == internal::kAnyFullTypeName) {
617 std::unique_ptr<Message> data1;
618 std::unique_ptr<Message> data2;
619 if (unpack_any_field_.UnpackAny(any: message1, data: &data1) &&
620 unpack_any_field_.UnpackAny(any: message2, data: &data2)) {
621 // Avoid DFATAL for different descriptors in google.protobuf.Any payloads.
622 if (data1->GetDescriptor() != data2->GetDescriptor()) {
623 return false;
624 }
625 return Compare(message1: *data1, message2: *data2, parent_fields);
626 }
627 }
628 const Reflection* reflection1 = message1.GetReflection();
629 const Reflection* reflection2 = message2.GetReflection();
630
631 bool unknown_compare_result = true;
632 // Ignore unknown fields in EQUIVALENT mode
633 if (message_field_comparison_ != EQUIVALENT) {
634 const UnknownFieldSet& unknown_field_set1 =
635 reflection1->GetUnknownFields(message: message1);
636 const UnknownFieldSet& unknown_field_set2 =
637 reflection2->GetUnknownFields(message: message2);
638 if (!CompareUnknownFields(message1, message2, unknown_field_set1,
639 unknown_field_set2, parent_fields)) {
640 if (reporter_ == NULL) {
641 return false;
642 }
643 unknown_compare_result = false;
644 }
645 }
646
647 FieldDescriptorArray message1_fields = RetrieveFields(message: message1, base_message: true);
648 FieldDescriptorArray message2_fields = RetrieveFields(message: message2, base_message: false);
649
650 return CompareRequestedFieldsUsingSettings(message1, message2,
651 message1_fields, message2_fields,
652 parent_fields) &&
653 unknown_compare_result;
654}
655
656FieldDescriptorArray MessageDifferencer::RetrieveFields(const Message& message,
657 bool base_message) {
658 const Descriptor* descriptor = message.GetDescriptor();
659
660 tmp_message_fields_.clear();
661 tmp_message_fields_.reserve(n: descriptor->field_count() + 1);
662
663 const Reflection* reflection = message.GetReflection();
664 if (descriptor->options().map_entry()) {
665 if (this->scope_ == PARTIAL && base_message) {
666 reflection->ListFields(message, output: &tmp_message_fields_);
667 } else {
668 // Map entry fields are always considered present.
669 for (int i = 0; i < descriptor->field_count(); i++) {
670 tmp_message_fields_.push_back(x: descriptor->field(index: i));
671 }
672 }
673 } else {
674 reflection->ListFields(message, output: &tmp_message_fields_);
675 }
676 // Add sentinel values to deal with the
677 // case where the number of the fields in
678 // each list are different.
679 tmp_message_fields_.push_back(x: nullptr);
680
681 FieldDescriptorArray message_fields(tmp_message_fields_.begin(),
682 tmp_message_fields_.end());
683
684 return message_fields;
685}
686
687bool MessageDifferencer::CompareRequestedFieldsUsingSettings(
688 const Message& message1, const Message& message2,
689 const FieldDescriptorArray& message1_fields,
690 const FieldDescriptorArray& message2_fields,
691 std::vector<SpecificField>* parent_fields) {
692 if (scope_ == FULL) {
693 if (message_field_comparison_ == EQUIVALENT) {
694 // We need to merge the field lists of both messages (i.e.
695 // we are merely checking for a difference in field values,
696 // rather than the addition or deletion of fields).
697 FieldDescriptorArray fields_union =
698 CombineFields(fields1: message1_fields, fields1_scope: FULL, fields2: message2_fields, fields2_scope: FULL);
699 return CompareWithFieldsInternal(message1, message2, message1_fields: fields_union,
700 message2_fields: fields_union, parent_fields);
701 } else {
702 // Simple equality comparison, use the unaltered field lists.
703 return CompareWithFieldsInternal(message1, message2, message1_fields,
704 message2_fields, parent_fields);
705 }
706 } else {
707 if (message_field_comparison_ == EQUIVALENT) {
708 // We use the list of fields for message1 for both messages when
709 // comparing. This way, extra fields in message2 are ignored,
710 // and missing fields in message2 use their default value.
711 return CompareWithFieldsInternal(message1, message2, message1_fields,
712 message2_fields: message1_fields, parent_fields);
713 } else {
714 // We need to consider the full list of fields for message1
715 // but only the intersection for message2. This way, any fields
716 // only present in message2 will be ignored, but any fields only
717 // present in message1 will be marked as a difference.
718 FieldDescriptorArray fields_intersection =
719 CombineFields(fields1: message1_fields, fields1_scope: PARTIAL, fields2: message2_fields, fields2_scope: PARTIAL);
720 return CompareWithFieldsInternal(message1, message2, message1_fields,
721 message2_fields: fields_intersection, parent_fields);
722 }
723 }
724}
725
726FieldDescriptorArray MessageDifferencer::CombineFields(
727 const FieldDescriptorArray& fields1, Scope fields1_scope,
728 const FieldDescriptorArray& fields2, Scope fields2_scope) {
729 size_t index1 = 0;
730 size_t index2 = 0;
731
732 tmp_message_fields_.clear();
733
734 while (index1 < fields1.size() && index2 < fields2.size()) {
735 const FieldDescriptor* field1 = fields1[index1];
736 const FieldDescriptor* field2 = fields2[index2];
737
738 if (FieldBefore(field1, field2)) {
739 if (fields1_scope == FULL) {
740 tmp_message_fields_.push_back(x: fields1[index1]);
741 }
742 ++index1;
743 } else if (FieldBefore(field1: field2, field2: field1)) {
744 if (fields2_scope == FULL) {
745 tmp_message_fields_.push_back(x: fields2[index2]);
746 }
747 ++index2;
748 } else {
749 tmp_message_fields_.push_back(x: fields1[index1]);
750 ++index1;
751 ++index2;
752 }
753 }
754
755 tmp_message_fields_.push_back(x: nullptr);
756
757 FieldDescriptorArray combined_fields(tmp_message_fields_.begin(),
758 tmp_message_fields_.end());
759
760 return combined_fields;
761}
762
763bool MessageDifferencer::CompareWithFieldsInternal(
764 const Message& message1, const Message& message2,
765 const FieldDescriptorArray& message1_fields,
766 const FieldDescriptorArray& message2_fields,
767 std::vector<SpecificField>* parent_fields) {
768 bool isDifferent = false;
769 int field_index1 = 0;
770 int field_index2 = 0;
771
772 const Reflection* reflection1 = message1.GetReflection();
773 const Reflection* reflection2 = message2.GetReflection();
774
775 while (true) {
776 const FieldDescriptor* field1 = message1_fields[field_index1];
777 const FieldDescriptor* field2 = message2_fields[field_index2];
778
779 // Once we have reached sentinel values, we are done the comparison.
780 if (field1 == NULL && field2 == NULL) {
781 break;
782 }
783
784 // Check for differences in the field itself.
785 if (FieldBefore(field1, field2)) {
786 // Field 1 is not in the field list for message 2.
787 if (IsIgnored(message1, message2, field: field1, parent_fields: *parent_fields)) {
788 // We are ignoring field1. Report the ignore and move on to
789 // the next field in message1_fields.
790 if (reporter_ != NULL) {
791 SpecificField specific_field;
792 specific_field.field = field1;
793 parent_fields->push_back(x: specific_field);
794 if (report_ignores_) {
795 reporter_->ReportIgnored(message1, message2, *parent_fields);
796 }
797 parent_fields->pop_back();
798 }
799 ++field_index1;
800 continue;
801 }
802
803 if (reporter_ != NULL) {
804 assert(field1 != NULL);
805 int count = field1->is_repeated()
806 ? reflection1->FieldSize(message: message1, field: field1)
807 : 1;
808
809 for (int i = 0; i < count; ++i) {
810 SpecificField specific_field;
811 specific_field.field = field1;
812 if (field1->is_repeated()) {
813 AddSpecificIndex(specific_field: &specific_field, message: message1, field: field1, index: i);
814 } else {
815 specific_field.index = -1;
816 }
817
818 parent_fields->push_back(x: specific_field);
819 reporter_->ReportDeleted(message1, message2, field_path: *parent_fields);
820 parent_fields->pop_back();
821 }
822
823 isDifferent = true;
824 } else {
825 return false;
826 }
827
828 ++field_index1;
829 continue;
830 } else if (FieldBefore(field1: field2, field2: field1)) {
831 // Field 2 is not in the field list for message 1.
832 if (IsIgnored(message1, message2, field: field2, parent_fields: *parent_fields)) {
833 // We are ignoring field2. Report the ignore and move on to
834 // the next field in message2_fields.
835 if (reporter_ != NULL) {
836 SpecificField specific_field;
837 specific_field.field = field2;
838 parent_fields->push_back(x: specific_field);
839 if (report_ignores_) {
840 reporter_->ReportIgnored(message1, message2, *parent_fields);
841 }
842 parent_fields->pop_back();
843 }
844 ++field_index2;
845 continue;
846 }
847
848 if (reporter_ != NULL) {
849 int count = field2->is_repeated()
850 ? reflection2->FieldSize(message: message2, field: field2)
851 : 1;
852
853 for (int i = 0; i < count; ++i) {
854 SpecificField specific_field;
855 specific_field.field = field2;
856 if (field2->is_repeated()) {
857 specific_field.index = i;
858 AddSpecificNewIndex(specific_field: &specific_field, message: message2, field: field2, index: i);
859 } else {
860 specific_field.index = -1;
861 specific_field.new_index = -1;
862 }
863
864 parent_fields->push_back(x: specific_field);
865 reporter_->ReportAdded(message1, message2, field_path: *parent_fields);
866 parent_fields->pop_back();
867 }
868
869 isDifferent = true;
870 } else {
871 return false;
872 }
873
874 ++field_index2;
875 continue;
876 }
877
878 // By this point, field1 and field2 are guaranteed to point to the same
879 // field, so we can now compare the values.
880 if (IsIgnored(message1, message2, field: field1, parent_fields: *parent_fields)) {
881 // Ignore this field. Report and move on.
882 if (reporter_ != NULL) {
883 SpecificField specific_field;
884 specific_field.field = field1;
885 parent_fields->push_back(x: specific_field);
886 if (report_ignores_) {
887 reporter_->ReportIgnored(message1, message2, *parent_fields);
888 }
889 parent_fields->pop_back();
890 }
891
892 ++field_index1;
893 ++field_index2;
894 continue;
895 }
896
897 bool fieldDifferent = false;
898 assert(field1 != NULL);
899 if (field1->is_map()) {
900 fieldDifferent =
901 !CompareMapField(message1, message2, field: field1, parent_fields);
902 } else if (field1->is_repeated()) {
903 fieldDifferent =
904 !CompareRepeatedField(message1, message2, field: field1, parent_fields);
905 } else {
906 fieldDifferent = !CompareFieldValueUsingParentFields(
907 message1, message2, field: field1, index1: -1, index2: -1, parent_fields);
908
909 if (reporter_ != nullptr) {
910 SpecificField specific_field;
911 specific_field.field = field1;
912 parent_fields->push_back(x: specific_field);
913 if (fieldDifferent) {
914 reporter_->ReportModified(message1, message2, field_path: *parent_fields);
915 isDifferent = true;
916 } else if (report_matches_) {
917 reporter_->ReportMatched(message1, message2, *parent_fields);
918 }
919 parent_fields->pop_back();
920 }
921 }
922 if (fieldDifferent) {
923 if (reporter_ == nullptr) return false;
924 isDifferent = true;
925 }
926 // Increment the field indices.
927 ++field_index1;
928 ++field_index2;
929 }
930
931 return !isDifferent;
932}
933
934bool MessageDifferencer::IsMatch(
935 const FieldDescriptor* repeated_field,
936 const MapKeyComparator* key_comparator, const Message* message1,
937 const Message* message2, const std::vector<SpecificField>& parent_fields,
938 Reporter* reporter, int index1, int index2) {
939 std::vector<SpecificField> current_parent_fields(parent_fields);
940 if (repeated_field->cpp_type() != FieldDescriptor::CPPTYPE_MESSAGE) {
941 return CompareFieldValueUsingParentFields(message1: *message1, message2: *message2,
942 field: repeated_field, index1, index2,
943 parent_fields: &current_parent_fields);
944 }
945 // Back up the Reporter and output_string_. They will be reset in the
946 // following code.
947 Reporter* backup_reporter = reporter_;
948 std::string* output_string = output_string_;
949 reporter_ = reporter;
950 output_string_ = NULL;
951 bool match;
952
953 if (key_comparator == NULL) {
954 match = CompareFieldValueUsingParentFields(message1: *message1, message2: *message2,
955 field: repeated_field, index1, index2,
956 parent_fields: &current_parent_fields);
957 } else {
958 const Reflection* reflection1 = message1->GetReflection();
959 const Reflection* reflection2 = message2->GetReflection();
960 const Message& m1 =
961 reflection1->GetRepeatedMessage(message: *message1, field: repeated_field, index: index1);
962 const Message& m2 =
963 reflection2->GetRepeatedMessage(message: *message2, field: repeated_field, index: index2);
964 SpecificField specific_field;
965 specific_field.field = repeated_field;
966 if (repeated_field->is_map()) {
967 specific_field.map_entry1 = &m1;
968 specific_field.map_entry2 = &m2;
969 }
970 specific_field.index = index1;
971 specific_field.new_index = index2;
972 current_parent_fields.push_back(x: specific_field);
973 match = key_comparator->IsMatch(m1, m2, current_parent_fields);
974 }
975
976 reporter_ = backup_reporter;
977 output_string_ = output_string;
978 return match;
979}
980
981bool MessageDifferencer::CompareMapFieldByMapReflection(
982 const Message& message1, const Message& message2,
983 const FieldDescriptor* map_field, std::vector<SpecificField>* parent_fields,
984 DefaultFieldComparator* comparator) {
985 GOOGLE_DCHECK_EQ(nullptr, reporter_);
986 GOOGLE_DCHECK(map_field->is_map());
987 GOOGLE_DCHECK(map_field_key_comparator_.find(map_field) ==
988 map_field_key_comparator_.end());
989 GOOGLE_DCHECK_EQ(repeated_field_comparison_, AS_LIST);
990 const Reflection* reflection1 = message1.GetReflection();
991 const Reflection* reflection2 = message2.GetReflection();
992 const int count1 = reflection1->MapSize(message: message1, field: map_field);
993 const int count2 = reflection2->MapSize(message: message2, field: map_field);
994 const bool treated_as_subset = IsTreatedAsSubset(field: map_field);
995 if (count1 != count2 && !treated_as_subset) {
996 return false;
997 }
998 if (count1 > count2) {
999 return false;
1000 }
1001
1002 // First pass: check whether the same keys are present.
1003 for (MapIterator it = reflection1->MapBegin(message: const_cast<Message*>(&message1),
1004 field: map_field),
1005 it_end = reflection1->MapEnd(message: const_cast<Message*>(&message1),
1006 field: map_field);
1007 it != it_end; ++it) {
1008 if (!reflection2->ContainsMapKey(message: message2, field: map_field, key: it.GetKey())) {
1009 return false;
1010 }
1011 }
1012
1013 // Second pass: compare values for matching keys.
1014 const FieldDescriptor* val_des = map_field->message_type()->map_value();
1015 switch (val_des->cpp_type()) {
1016#define HANDLE_TYPE(CPPTYPE, METHOD, COMPAREMETHOD) \
1017 case FieldDescriptor::CPPTYPE_##CPPTYPE: { \
1018 for (MapIterator it = reflection1->MapBegin( \
1019 const_cast<Message*>(&message1), map_field), \
1020 it_end = reflection1->MapEnd( \
1021 const_cast<Message*>(&message1), map_field); \
1022 it != it_end; ++it) { \
1023 MapValueConstRef value2; \
1024 reflection2->LookupMapValue(message2, map_field, it.GetKey(), &value2); \
1025 if (!comparator->Compare##COMPAREMETHOD(*val_des, \
1026 it.GetValueRef().Get##METHOD(), \
1027 value2.Get##METHOD())) { \
1028 return false; \
1029 } \
1030 } \
1031 break; \
1032 }
1033 HANDLE_TYPE(INT32, Int32Value, Int32);
1034 HANDLE_TYPE(INT64, Int64Value, Int64);
1035 HANDLE_TYPE(UINT32, UInt32Value, UInt32);
1036 HANDLE_TYPE(UINT64, UInt64Value, UInt64);
1037 HANDLE_TYPE(DOUBLE, DoubleValue, Double);
1038 HANDLE_TYPE(FLOAT, FloatValue, Float);
1039 HANDLE_TYPE(BOOL, BoolValue, Bool);
1040 HANDLE_TYPE(STRING, StringValue, String);
1041 HANDLE_TYPE(ENUM, EnumValue, Int32);
1042#undef HANDLE_TYPE
1043 case FieldDescriptor::CPPTYPE_MESSAGE: {
1044 for (MapIterator it = reflection1->MapBegin(
1045 message: const_cast<Message*>(&message1), field: map_field);
1046 it !=
1047 reflection1->MapEnd(message: const_cast<Message*>(&message1), field: map_field);
1048 ++it) {
1049 if (!reflection2->ContainsMapKey(message: message2, field: map_field, key: it.GetKey())) {
1050 return false;
1051 }
1052 bool compare_result;
1053 MapValueConstRef value2;
1054 reflection2->LookupMapValue(message: message2, field: map_field, key: it.GetKey(), val: &value2);
1055 // Append currently compared field to the end of parent_fields.
1056 SpecificField specific_value_field;
1057 specific_value_field.field = val_des;
1058 parent_fields->push_back(x: specific_value_field);
1059 compare_result = Compare(message1: it.GetValueRef().GetMessageValue(),
1060 message2: value2.GetMessageValue(), parent_fields);
1061 parent_fields->pop_back();
1062 if (!compare_result) {
1063 return false;
1064 }
1065 }
1066 break;
1067 }
1068 }
1069 return true;
1070}
1071
1072bool MessageDifferencer::CompareMapField(
1073 const Message& message1, const Message& message2,
1074 const FieldDescriptor* repeated_field,
1075 std::vector<SpecificField>* parent_fields) {
1076 GOOGLE_DCHECK(repeated_field->is_map());
1077
1078 // the input FieldDescriptor is guaranteed to be repeated field.
1079 const Reflection* reflection1 = message1.GetReflection();
1080 const Reflection* reflection2 = message2.GetReflection();
1081
1082 // When both map fields are on map, do not sync to repeated field.
1083 if (reflection1->GetMapData(message: message1, field: repeated_field)->IsMapValid() &&
1084 reflection2->GetMapData(message: message2, field: repeated_field)->IsMapValid() &&
1085 // TODO(jieluo): Add support for reporter
1086 reporter_ == nullptr &&
1087 // Users didn't set custom map field key comparator
1088 map_field_key_comparator_.find(x: repeated_field) ==
1089 map_field_key_comparator_.end() &&
1090 // Users didn't set repeated field comparison
1091 repeated_field_comparison_ == AS_LIST &&
1092 // Users didn't set their own FieldComparator implementation
1093 field_comparator_kind_ == kFCDefault) {
1094 const FieldDescriptor* key_des = repeated_field->message_type()->map_key();
1095 const FieldDescriptor* val_des =
1096 repeated_field->message_type()->map_value();
1097 std::vector<SpecificField> current_parent_fields(*parent_fields);
1098 SpecificField specific_field;
1099 specific_field.field = repeated_field;
1100 current_parent_fields.push_back(x: specific_field);
1101 if (!IsIgnored(message1, message2, field: key_des, parent_fields: current_parent_fields) &&
1102 !IsIgnored(message1, message2, field: val_des, parent_fields: current_parent_fields)) {
1103 return CompareMapFieldByMapReflection(message1, message2, map_field: repeated_field,
1104 parent_fields: &current_parent_fields,
1105 comparator: field_comparator_.default_impl);
1106 }
1107 }
1108
1109 return CompareRepeatedRep(message1, message2, field: repeated_field, parent_fields);
1110}
1111
1112bool MessageDifferencer::CompareRepeatedField(
1113 const Message& message1, const Message& message2,
1114 const FieldDescriptor* repeated_field,
1115 std::vector<SpecificField>* parent_fields) {
1116 GOOGLE_DCHECK(!repeated_field->is_map());
1117 return CompareRepeatedRep(message1, message2, field: repeated_field, parent_fields);
1118}
1119
1120bool MessageDifferencer::CompareRepeatedRep(
1121 const Message& message1, const Message& message2,
1122 const FieldDescriptor* repeated_field,
1123 std::vector<SpecificField>* parent_fields) {
1124 // the input FieldDescriptor is guaranteed to be repeated field.
1125 GOOGLE_DCHECK(repeated_field->is_repeated());
1126 const Reflection* reflection1 = message1.GetReflection();
1127 const Reflection* reflection2 = message2.GetReflection();
1128
1129 const int count1 = reflection1->FieldSize(message: message1, field: repeated_field);
1130 const int count2 = reflection2->FieldSize(message: message2, field: repeated_field);
1131 const bool treated_as_subset = IsTreatedAsSubset(field: repeated_field);
1132
1133 // If the field is not treated as subset and no detailed reports is needed,
1134 // we do a quick check on the number of the elements to avoid unnecessary
1135 // comparison.
1136 if (count1 != count2 && reporter_ == NULL && !treated_as_subset) {
1137 return false;
1138 }
1139 // A match can never be found if message1 has more items than message2.
1140 if (count1 > count2 && reporter_ == NULL) {
1141 return false;
1142 }
1143
1144 // These two list are used for store the index of the correspondent
1145 // element in peer repeated field.
1146 std::vector<int> match_list1;
1147 std::vector<int> match_list2;
1148
1149 const MapKeyComparator* key_comparator = GetMapKeyComparator(field: repeated_field);
1150 bool smart_list = IsTreatedAsSmartList(field: repeated_field);
1151 bool simple_list = key_comparator == nullptr &&
1152 !IsTreatedAsSet(field: repeated_field) &&
1153 !IsTreatedAsSmartSet(field: repeated_field) && !smart_list;
1154
1155 // For simple lists, we avoid matching repeated field indices, saving the
1156 // memory allocations that would otherwise be needed for match_list1 and
1157 // match_list2.
1158 if (!simple_list) {
1159 // Try to match indices of the repeated fields. Return false if match fails.
1160 if (!MatchRepeatedFieldIndices(message1, message2, repeated_field,
1161 key_comparator, parent_fields: *parent_fields, match_list1: &match_list1,
1162 match_list2: &match_list2) &&
1163 reporter_ == nullptr) {
1164 return false;
1165 }
1166 }
1167
1168 bool fieldDifferent = false;
1169 SpecificField specific_field;
1170 specific_field.field = repeated_field;
1171
1172 // At this point, we have already matched pairs of fields (with the reporting
1173 // to be done later). Now to check if the paired elements are different.
1174 int next_unmatched_index = 0;
1175 for (int i = 0; i < count1; i++) {
1176 if (simple_list && i >= count2) {
1177 break;
1178 }
1179 if (!simple_list && match_list1[i] == -1) {
1180 if (smart_list) {
1181 if (reporter_ == nullptr) return false;
1182 AddSpecificIndex(specific_field: &specific_field, message: message1, field: repeated_field, index: i);
1183 parent_fields->push_back(x: specific_field);
1184 reporter_->ReportDeleted(message1, message2, field_path: *parent_fields);
1185 parent_fields->pop_back();
1186 fieldDifferent = true;
1187 // Use -2 to mark this element has been reported.
1188 match_list1[i] = -2;
1189 }
1190 continue;
1191 }
1192 if (smart_list) {
1193 for (int j = next_unmatched_index; j < match_list1[i]; ++j) {
1194 GOOGLE_CHECK_LE(0, j);
1195 if (reporter_ == nullptr) return false;
1196 specific_field.index = j;
1197 AddSpecificNewIndex(specific_field: &specific_field, message: message2, field: repeated_field, index: j);
1198 parent_fields->push_back(x: specific_field);
1199 reporter_->ReportAdded(message1, message2, field_path: *parent_fields);
1200 parent_fields->pop_back();
1201 fieldDifferent = true;
1202 // Use -2 to mark this element has been reported.
1203 match_list2[j] = -2;
1204 }
1205 }
1206 AddSpecificIndex(specific_field: &specific_field, message: message1, field: repeated_field, index: i);
1207 if (simple_list) {
1208 AddSpecificNewIndex(specific_field: &specific_field, message: message2, field: repeated_field, index: i);
1209 } else {
1210 AddSpecificNewIndex(specific_field: &specific_field, message: message2, field: repeated_field,
1211 index: match_list1[i]);
1212 next_unmatched_index = match_list1[i] + 1;
1213 }
1214
1215 const bool result = CompareFieldValueUsingParentFields(
1216 message1, message2, field: repeated_field, index1: i, index2: specific_field.new_index,
1217 parent_fields);
1218
1219 // If we have found differences, either report them or terminate if
1220 // no reporter is present. Note that ReportModified, ReportMoved, and
1221 // ReportMatched are all mutually exclusive.
1222 if (!result) {
1223 if (reporter_ == NULL) return false;
1224 parent_fields->push_back(x: specific_field);
1225 reporter_->ReportModified(message1, message2, field_path: *parent_fields);
1226 parent_fields->pop_back();
1227 fieldDifferent = true;
1228 } else if (reporter_ != NULL &&
1229 specific_field.index != specific_field.new_index &&
1230 !specific_field.field->is_map() && report_moves_) {
1231 parent_fields->push_back(x: specific_field);
1232 reporter_->ReportMoved(message1, message2, *parent_fields);
1233 parent_fields->pop_back();
1234 } else if (report_matches_ && reporter_ != NULL) {
1235 parent_fields->push_back(x: specific_field);
1236 reporter_->ReportMatched(message1, message2, *parent_fields);
1237 parent_fields->pop_back();
1238 }
1239 }
1240
1241 // Report any remaining additions or deletions.
1242 for (int i = 0; i < count2; ++i) {
1243 if (!simple_list && match_list2[i] != -1) continue;
1244 if (simple_list && i < count1) continue;
1245 if (!treated_as_subset) {
1246 fieldDifferent = true;
1247 }
1248
1249 if (reporter_ == NULL) continue;
1250 specific_field.index = i;
1251 AddSpecificNewIndex(specific_field: &specific_field, message: message2, field: repeated_field, index: i);
1252 parent_fields->push_back(x: specific_field);
1253 reporter_->ReportAdded(message1, message2, field_path: *parent_fields);
1254 parent_fields->pop_back();
1255 }
1256
1257 for (int i = 0; i < count1; ++i) {
1258 if (!simple_list && match_list1[i] != -1) continue;
1259 if (simple_list && i < count2) continue;
1260 assert(reporter_ != NULL);
1261 AddSpecificIndex(specific_field: &specific_field, message: message1, field: repeated_field, index: i);
1262 parent_fields->push_back(x: specific_field);
1263 reporter_->ReportDeleted(message1, message2, field_path: *parent_fields);
1264 parent_fields->pop_back();
1265 fieldDifferent = true;
1266 }
1267 return !fieldDifferent;
1268}
1269
1270bool MessageDifferencer::CompareFieldValue(const Message& message1,
1271 const Message& message2,
1272 const FieldDescriptor* field,
1273 int index1, int index2) {
1274 return CompareFieldValueUsingParentFields(message1, message2, field, index1,
1275 index2, NULL);
1276}
1277
1278bool MessageDifferencer::CompareFieldValueUsingParentFields(
1279 const Message& message1, const Message& message2,
1280 const FieldDescriptor* field, int index1, int index2,
1281 std::vector<SpecificField>* parent_fields) {
1282 FieldContext field_context(parent_fields);
1283 FieldComparator::ComparisonResult result = GetFieldComparisonResult(
1284 message1, message2, field, index1, index2, field_context: &field_context);
1285
1286 if (field->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE &&
1287 result == FieldComparator::RECURSE) {
1288 // Get the nested messages and compare them using one of the Compare
1289 // methods.
1290 const Reflection* reflection1 = message1.GetReflection();
1291 const Reflection* reflection2 = message2.GetReflection();
1292 const Message& m1 =
1293 field->is_repeated()
1294 ? reflection1->GetRepeatedMessage(message: message1, field, index: index1)
1295 : reflection1->GetMessage(message: message1, field);
1296 const Message& m2 =
1297 field->is_repeated()
1298 ? reflection2->GetRepeatedMessage(message: message2, field, index: index2)
1299 : reflection2->GetMessage(message: message2, field);
1300
1301 // parent_fields is used in calls to Reporter methods.
1302 if (parent_fields != NULL) {
1303 // Append currently compared field to the end of parent_fields.
1304 SpecificField specific_field;
1305 specific_field.field = field;
1306 AddSpecificIndex(specific_field: &specific_field, message: message1, field, index: index1);
1307 AddSpecificNewIndex(specific_field: &specific_field, message: message2, field, index: index2);
1308 parent_fields->push_back(x: specific_field);
1309 const bool compare_result = Compare(message1: m1, message2: m2, parent_fields);
1310 parent_fields->pop_back();
1311 return compare_result;
1312 } else {
1313 // Recreates parent_fields as if m1 and m2 had no parents.
1314 return Compare(message1: m1, message2: m2);
1315 }
1316 } else {
1317 return (result == FieldComparator::SAME);
1318 }
1319}
1320
1321bool MessageDifferencer::CheckPathChanged(
1322 const std::vector<SpecificField>& field_path) {
1323 for (const SpecificField& specific_field : field_path) {
1324 // Don't check indexes for map entries -- maps are unordered.
1325 if (specific_field.field != nullptr && specific_field.field->is_map())
1326 continue;
1327 if (specific_field.index != specific_field.new_index) return true;
1328 }
1329 return false;
1330}
1331
1332bool MessageDifferencer::IsTreatedAsSet(const FieldDescriptor* field) {
1333 if (!field->is_repeated()) return false;
1334 if (repeated_field_comparisons_.find(x: field) !=
1335 repeated_field_comparisons_.end()) {
1336 return repeated_field_comparisons_[field] == AS_SET;
1337 }
1338 return GetMapKeyComparator(field) == nullptr &&
1339 repeated_field_comparison_ == AS_SET;
1340}
1341
1342bool MessageDifferencer::IsTreatedAsSmartSet(const FieldDescriptor* field) {
1343 if (!field->is_repeated()) return false;
1344 if (repeated_field_comparisons_.find(x: field) !=
1345 repeated_field_comparisons_.end()) {
1346 return repeated_field_comparisons_[field] == AS_SMART_SET;
1347 }
1348 return GetMapKeyComparator(field) == nullptr &&
1349 repeated_field_comparison_ == AS_SMART_SET;
1350}
1351
1352bool MessageDifferencer::IsTreatedAsSmartList(const FieldDescriptor* field) {
1353 if (!field->is_repeated()) return false;
1354 if (repeated_field_comparisons_.find(x: field) !=
1355 repeated_field_comparisons_.end()) {
1356 return repeated_field_comparisons_[field] == AS_SMART_LIST;
1357 }
1358 return GetMapKeyComparator(field) == nullptr &&
1359 repeated_field_comparison_ == AS_SMART_LIST;
1360}
1361
1362bool MessageDifferencer::IsTreatedAsSubset(const FieldDescriptor* field) {
1363 return scope_ == PARTIAL &&
1364 (IsTreatedAsSet(field) || GetMapKeyComparator(field) != NULL);
1365}
1366
1367bool MessageDifferencer::IsIgnored(
1368 const Message& message1, const Message& message2,
1369 const FieldDescriptor* field,
1370 const std::vector<SpecificField>& parent_fields) {
1371 if (ignored_fields_.find(x: field) != ignored_fields_.end()) {
1372 return true;
1373 }
1374 for (IgnoreCriteria* criteria : ignore_criteria_) {
1375 if (criteria->IsIgnored(message1, message2, field, parent_fields)) {
1376 return true;
1377 }
1378 }
1379 return false;
1380}
1381
1382bool MessageDifferencer::IsUnknownFieldIgnored(
1383 const Message& message1, const Message& message2,
1384 const SpecificField& field,
1385 const std::vector<SpecificField>& parent_fields) {
1386 for (IgnoreCriteria* criteria : ignore_criteria_) {
1387 if (criteria->IsUnknownFieldIgnored(message1, message2, field,
1388 parent_fields)) {
1389 return true;
1390 }
1391 }
1392 return false;
1393}
1394
1395const MessageDifferencer::MapKeyComparator*
1396MessageDifferencer ::GetMapKeyComparator(const FieldDescriptor* field) const {
1397 if (!field->is_repeated()) return NULL;
1398 FieldKeyComparatorMap::const_iterator it =
1399 map_field_key_comparator_.find(x: field);
1400 if (it != map_field_key_comparator_.end()) {
1401 return it->second;
1402 }
1403 if (field->is_map()) {
1404 // field cannot already be treated as list or set since TreatAsList() and
1405 // TreatAsSet() call GetMapKeyComparator() and fail if it returns non-NULL.
1406 return &map_entry_key_comparator_;
1407 }
1408 return NULL;
1409}
1410
1411namespace {
1412
1413typedef std::pair<int, const UnknownField*> IndexUnknownFieldPair;
1414
1415struct UnknownFieldOrdering {
1416 inline bool operator()(const IndexUnknownFieldPair& a,
1417 const IndexUnknownFieldPair& b) const {
1418 if (a.second->number() < b.second->number()) return true;
1419 if (a.second->number() > b.second->number()) return false;
1420 return a.second->type() < b.second->type();
1421 }
1422};
1423
1424} // namespace
1425
1426bool MessageDifferencer::UnpackAnyField::UnpackAny(
1427 const Message& any, std::unique_ptr<Message>* data) {
1428 const Reflection* reflection = any.GetReflection();
1429 const FieldDescriptor* type_url_field;
1430 const FieldDescriptor* value_field;
1431 if (!internal::GetAnyFieldDescriptors(message: any, type_url_field: &type_url_field, value_field: &value_field)) {
1432 return false;
1433 }
1434 const std::string& type_url = reflection->GetString(message: any, field: type_url_field);
1435 std::string full_type_name;
1436 if (!internal::ParseAnyTypeUrl(type_url, full_type_name: &full_type_name)) {
1437 return false;
1438 }
1439
1440 const Descriptor* desc =
1441 any.GetDescriptor()->file()->pool()->FindMessageTypeByName(
1442 name: full_type_name);
1443 if (desc == NULL) {
1444 GOOGLE_LOG(INFO) << "Proto type '" << full_type_name << "' not found";
1445 return false;
1446 }
1447
1448 if (dynamic_message_factory_ == NULL) {
1449 dynamic_message_factory_.reset(p: new DynamicMessageFactory());
1450 }
1451 data->reset(p: dynamic_message_factory_->GetPrototype(type: desc)->New());
1452 std::string serialized_value = reflection->GetString(message: any, field: value_field);
1453 if (!(*data)->ParsePartialFromString(data: serialized_value)) {
1454 GOOGLE_DLOG(ERROR) << "Failed to parse value for " << full_type_name;
1455 return false;
1456 }
1457 return true;
1458}
1459
1460bool MessageDifferencer::CompareUnknownFields(
1461 const Message& message1, const Message& message2,
1462 const UnknownFieldSet& unknown_field_set1,
1463 const UnknownFieldSet& unknown_field_set2,
1464 std::vector<SpecificField>* parent_field) {
1465 // Ignore unknown fields in EQUIVALENT mode.
1466 if (message_field_comparison_ == EQUIVALENT) return true;
1467
1468 if (unknown_field_set1.empty() && unknown_field_set2.empty()) {
1469 return true;
1470 }
1471
1472 bool is_different = false;
1473
1474 // We first sort the unknown fields by field number and type (in other words,
1475 // in tag order), making sure to preserve ordering of values with the same
1476 // tag. This allows us to report only meaningful differences between the
1477 // two sets -- that is, differing values for the same tag. We use
1478 // IndexUnknownFieldPairs to keep track of the field's original index for
1479 // reporting purposes.
1480 std::vector<IndexUnknownFieldPair> fields1; // unknown_field_set1, sorted
1481 std::vector<IndexUnknownFieldPair> fields2; // unknown_field_set2, sorted
1482 fields1.reserve(n: unknown_field_set1.field_count());
1483 fields2.reserve(n: unknown_field_set2.field_count());
1484
1485 for (int i = 0; i < unknown_field_set1.field_count(); i++) {
1486 fields1.push_back(x: std::make_pair(x&: i, y: &unknown_field_set1.field(index: i)));
1487 }
1488 for (int i = 0; i < unknown_field_set2.field_count(); i++) {
1489 fields2.push_back(x: std::make_pair(x&: i, y: &unknown_field_set2.field(index: i)));
1490 }
1491
1492 UnknownFieldOrdering is_before;
1493 std::stable_sort(first: fields1.begin(), last: fields1.end(), comp: is_before);
1494 std::stable_sort(first: fields2.begin(), last: fields2.end(), comp: is_before);
1495
1496 // In order to fill in SpecificField::index, we have to keep track of how
1497 // many values we've seen with the same field number and type.
1498 // current_repeated points at the first field in this range, and
1499 // current_repeated_start{1,2} are the indexes of the first field in the
1500 // range within fields1 and fields2.
1501 const UnknownField* current_repeated = NULL;
1502 int current_repeated_start1 = 0;
1503 int current_repeated_start2 = 0;
1504
1505 // Now that we have two sorted lists, we can detect fields which appear only
1506 // in one list or the other by traversing them simultaneously.
1507 size_t index1 = 0;
1508 size_t index2 = 0;
1509 while (index1 < fields1.size() || index2 < fields2.size()) {
1510 enum {
1511 ADDITION,
1512 DELETION,
1513 MODIFICATION,
1514 COMPARE_GROUPS,
1515 NO_CHANGE
1516 } change_type;
1517
1518 // focus_field is the field we're currently reporting on. (In the case
1519 // of a modification, it's the field on the left side.)
1520 const UnknownField* focus_field;
1521 bool match = false;
1522
1523 if (index2 == fields2.size() ||
1524 (index1 < fields1.size() &&
1525 is_before(fields1[index1], fields2[index2]))) {
1526 // fields1[index1] is not present in fields2.
1527 change_type = DELETION;
1528 focus_field = fields1[index1].second;
1529 } else if (index1 == fields1.size() ||
1530 is_before(fields2[index2], fields1[index1])) {
1531 // fields2[index2] is not present in fields1.
1532 if (scope_ == PARTIAL) {
1533 // Ignore.
1534 ++index2;
1535 continue;
1536 }
1537 change_type = ADDITION;
1538 focus_field = fields2[index2].second;
1539 } else {
1540 // Field type and number are the same. See if the values differ.
1541 change_type = MODIFICATION;
1542 focus_field = fields1[index1].second;
1543
1544 switch (focus_field->type()) {
1545 case UnknownField::TYPE_VARINT:
1546 match = fields1[index1].second->varint() ==
1547 fields2[index2].second->varint();
1548 break;
1549 case UnknownField::TYPE_FIXED32:
1550 match = fields1[index1].second->fixed32() ==
1551 fields2[index2].second->fixed32();
1552 break;
1553 case UnknownField::TYPE_FIXED64:
1554 match = fields1[index1].second->fixed64() ==
1555 fields2[index2].second->fixed64();
1556 break;
1557 case UnknownField::TYPE_LENGTH_DELIMITED:
1558 match = fields1[index1].second->length_delimited() ==
1559 fields2[index2].second->length_delimited();
1560 break;
1561 case UnknownField::TYPE_GROUP:
1562 // We must deal with this later, after building the SpecificField.
1563 change_type = COMPARE_GROUPS;
1564 break;
1565 }
1566 if (match && change_type != COMPARE_GROUPS) {
1567 change_type = NO_CHANGE;
1568 }
1569 }
1570
1571 if (current_repeated == NULL ||
1572 focus_field->number() != current_repeated->number() ||
1573 focus_field->type() != current_repeated->type()) {
1574 // We've started a new repeated field.
1575 current_repeated = focus_field;
1576 current_repeated_start1 = index1;
1577 current_repeated_start2 = index2;
1578 }
1579
1580 if (change_type == NO_CHANGE && reporter_ == NULL) {
1581 // Fields were already compared and matched and we have no reporter.
1582 ++index1;
1583 ++index2;
1584 continue;
1585 }
1586
1587 // Build the SpecificField. This is slightly complicated.
1588 SpecificField specific_field;
1589 specific_field.unknown_field_number = focus_field->number();
1590 specific_field.unknown_field_type = focus_field->type();
1591
1592 specific_field.unknown_field_set1 = &unknown_field_set1;
1593 specific_field.unknown_field_set2 = &unknown_field_set2;
1594
1595 if (change_type != ADDITION) {
1596 specific_field.unknown_field_index1 = fields1[index1].first;
1597 }
1598 if (change_type != DELETION) {
1599 specific_field.unknown_field_index2 = fields2[index2].first;
1600 }
1601
1602 // Calculate the field index.
1603 if (change_type == ADDITION) {
1604 specific_field.index = index2 - current_repeated_start2;
1605 specific_field.new_index = index2 - current_repeated_start2;
1606 } else {
1607 specific_field.index = index1 - current_repeated_start1;
1608 specific_field.new_index = index2 - current_repeated_start2;
1609 }
1610
1611 if (IsUnknownFieldIgnored(message1, message2, field: specific_field,
1612 parent_fields: *parent_field)) {
1613 if (report_ignores_ && reporter_ != NULL) {
1614 parent_field->push_back(x: specific_field);
1615 reporter_->ReportUnknownFieldIgnored(message1, message2, *parent_field);
1616 parent_field->pop_back();
1617 }
1618 if (change_type != ADDITION) ++index1;
1619 if (change_type != DELETION) ++index2;
1620 continue;
1621 }
1622
1623 if (change_type == ADDITION || change_type == DELETION ||
1624 change_type == MODIFICATION) {
1625 if (reporter_ == NULL) {
1626 // We found a difference and we have no reporter.
1627 return false;
1628 }
1629 is_different = true;
1630 }
1631
1632 parent_field->push_back(x: specific_field);
1633
1634 switch (change_type) {
1635 case ADDITION:
1636 reporter_->ReportAdded(message1, message2, field_path: *parent_field);
1637 ++index2;
1638 break;
1639 case DELETION:
1640 reporter_->ReportDeleted(message1, message2, field_path: *parent_field);
1641 ++index1;
1642 break;
1643 case MODIFICATION:
1644 reporter_->ReportModified(message1, message2, field_path: *parent_field);
1645 ++index1;
1646 ++index2;
1647 break;
1648 case COMPARE_GROUPS:
1649 if (!CompareUnknownFields(
1650 message1, message2, unknown_field_set1: fields1[index1].second->group(),
1651 unknown_field_set2: fields2[index2].second->group(), parent_field)) {
1652 if (reporter_ == NULL) return false;
1653 is_different = true;
1654 reporter_->ReportModified(message1, message2, field_path: *parent_field);
1655 }
1656 ++index1;
1657 ++index2;
1658 break;
1659 case NO_CHANGE:
1660 ++index1;
1661 ++index2;
1662 if (report_matches_) {
1663 reporter_->ReportMatched(message1, message2, *parent_field);
1664 }
1665 }
1666
1667 parent_field->pop_back();
1668 }
1669
1670 return !is_different;
1671}
1672
1673namespace {
1674
1675// Find maximum bipartite matching using the argumenting path algorithm.
1676class MaximumMatcher {
1677 public:
1678 typedef std::function<bool(int, int)> NodeMatchCallback;
1679 // MaximumMatcher takes ownership of the passed in callback and uses it to
1680 // determine whether a node on the left side of the bipartial graph matches
1681 // a node on the right side. count1 is the number of nodes on the left side
1682 // of the graph and count2 to is the number of nodes on the right side.
1683 // Every node is referred to using 0-based indices.
1684 // If a maximum match is found, the result will be stored in match_list1 and
1685 // match_list2. match_list1[i] == j means the i-th node on the left side is
1686 // matched to the j-th node on the right side and match_list2[x] == y means
1687 // the x-th node on the right side is matched to y-th node on the left side.
1688 // match_list1[i] == -1 means the node is not matched. Same with match_list2.
1689 MaximumMatcher(int count1, int count2, NodeMatchCallback callback,
1690 std::vector<int>* match_list1, std::vector<int>* match_list2);
1691 // Find a maximum match and return the number of matched node pairs.
1692 // If early_return is true, this method will return 0 immediately when it
1693 // finds that not all nodes on the left side can be matched.
1694 int FindMaximumMatch(bool early_return);
1695
1696 private:
1697 // Determines whether the node on the left side of the bipartial graph
1698 // matches the one on the right side.
1699 bool Match(int left, int right);
1700 // Find an argumenting path starting from the node v on the left side. If a
1701 // path can be found, update match_list2_ to reflect the path and return
1702 // true.
1703 bool FindArgumentPathDFS(int v, std::vector<bool>* visited);
1704
1705 int count1_;
1706 int count2_;
1707 NodeMatchCallback match_callback_;
1708 std::map<std::pair<int, int>, bool> cached_match_results_;
1709 std::vector<int>* match_list1_;
1710 std::vector<int>* match_list2_;
1711 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(MaximumMatcher);
1712};
1713
1714MaximumMatcher::MaximumMatcher(int count1, int count2,
1715 NodeMatchCallback callback,
1716 std::vector<int>* match_list1,
1717 std::vector<int>* match_list2)
1718 : count1_(count1),
1719 count2_(count2),
1720 match_callback_(std::move(callback)),
1721 match_list1_(match_list1),
1722 match_list2_(match_list2) {
1723 match_list1_->assign(n: count1, val: -1);
1724 match_list2_->assign(n: count2, val: -1);
1725}
1726
1727int MaximumMatcher::FindMaximumMatch(bool early_return) {
1728 int result = 0;
1729 for (int i = 0; i < count1_; ++i) {
1730 std::vector<bool> visited(count1_);
1731 if (FindArgumentPathDFS(v: i, visited: &visited)) {
1732 ++result;
1733 } else if (early_return) {
1734 return 0;
1735 }
1736 }
1737 // Backfill match_list1_ as we only filled match_list2_ when finding
1738 // argumenting paths.
1739 for (int i = 0; i < count2_; ++i) {
1740 if ((*match_list2_)[i] != -1) {
1741 (*match_list1_)[(*match_list2_)[i]] = i;
1742 }
1743 }
1744 return result;
1745}
1746
1747bool MaximumMatcher::Match(int left, int right) {
1748 std::pair<int, int> p(left, right);
1749 std::map<std::pair<int, int>, bool>::iterator it =
1750 cached_match_results_.find(x: p);
1751 if (it != cached_match_results_.end()) {
1752 return it->second;
1753 }
1754 cached_match_results_[p] = match_callback_(left, right);
1755 return cached_match_results_[p];
1756}
1757
1758bool MaximumMatcher::FindArgumentPathDFS(int v, std::vector<bool>* visited) {
1759 (*visited)[v] = true;
1760 // We try to match those un-matched nodes on the right side first. This is
1761 // the step that the naive greedy matching algorithm uses. In the best cases
1762 // where the greedy algorithm can find a maximum matching, we will always
1763 // find a match in this step and the performance will be identical to the
1764 // greedy algorithm.
1765 for (int i = 0; i < count2_; ++i) {
1766 int matched = (*match_list2_)[i];
1767 if (matched == -1 && Match(left: v, right: i)) {
1768 (*match_list2_)[i] = v;
1769 return true;
1770 }
1771 }
1772 // Then we try those already matched nodes and see if we can find an
1773 // alternative match for the node matched to them.
1774 // The greedy algorithm will stop before this and fail to produce the
1775 // correct result.
1776 for (int i = 0; i < count2_; ++i) {
1777 int matched = (*match_list2_)[i];
1778 if (matched != -1 && Match(left: v, right: i)) {
1779 if (!(*visited)[matched] && FindArgumentPathDFS(v: matched, visited)) {
1780 (*match_list2_)[i] = v;
1781 return true;
1782 }
1783 }
1784 }
1785 return false;
1786}
1787
1788} // namespace
1789
1790bool MessageDifferencer::MatchRepeatedFieldIndices(
1791 const Message& message1, const Message& message2,
1792 const FieldDescriptor* repeated_field,
1793 const MapKeyComparator* key_comparator,
1794 const std::vector<SpecificField>& parent_fields,
1795 std::vector<int>* match_list1, std::vector<int>* match_list2) {
1796 const int count1 =
1797 message1.GetReflection()->FieldSize(message: message1, field: repeated_field);
1798 const int count2 =
1799 message2.GetReflection()->FieldSize(message: message2, field: repeated_field);
1800 const bool is_treated_as_smart_set = IsTreatedAsSmartSet(field: repeated_field);
1801
1802 match_list1->assign(n: count1, val: -1);
1803 match_list2->assign(n: count2, val: -1);
1804 // Ensure that we don't report differences during the matching process. Since
1805 // field comparators could potentially use this message differencer object to
1806 // perform further comparisons, turn off reporting here and re-enable it
1807 // before returning.
1808 Reporter* reporter = reporter_;
1809 reporter_ = NULL;
1810 NumDiffsReporter num_diffs_reporter;
1811 std::vector<int32_t> num_diffs_list1;
1812 if (is_treated_as_smart_set) {
1813 num_diffs_list1.assign(n: count1, val: std::numeric_limits<int32_t>::max());
1814 }
1815
1816 bool success = true;
1817 // Find potential match if this is a special repeated field.
1818 if (scope_ == PARTIAL) {
1819 // When partial matching is enabled, Compare(a, b) && Compare(a, c)
1820 // doesn't necessarily imply Compare(b, c). Therefore a naive greedy
1821 // algorithm will fail to find a maximum matching.
1822 // Here we use the augmenting path algorithm.
1823 auto callback = [&](int i1, int i2) {
1824 return IsMatch(repeated_field, key_comparator, message1: &message1, message2: &message2,
1825 parent_fields, reporter: nullptr, index1: i1, index2: i2);
1826 };
1827 MaximumMatcher matcher(count1, count2, std::move(callback), match_list1,
1828 match_list2);
1829 // If diff info is not needed, we should end the matching process as
1830 // soon as possible if not all items can be matched.
1831 bool early_return = (reporter == nullptr);
1832 int match_count = matcher.FindMaximumMatch(early_return);
1833 if (match_count != count1 && early_return) return false;
1834 success = success && (match_count == count1);
1835 } else {
1836 int start_offset = 0;
1837 // If the two repeated fields are treated as sets, optimize for the case
1838 // where both start with same items stored in the same order.
1839 if (IsTreatedAsSet(field: repeated_field) || is_treated_as_smart_set ||
1840 IsTreatedAsSmartList(field: repeated_field)) {
1841 start_offset = std::min(count1, count2);
1842 for (int i = 0; i < count1 && i < count2; i++) {
1843 if (IsMatch(repeated_field, key_comparator, message1: &message1, message2: &message2,
1844 parent_fields, reporter: nullptr, index1: i, index2: i)) {
1845 match_list1->at(n: i) = i;
1846 match_list2->at(n: i) = i;
1847 } else {
1848 start_offset = i;
1849 break;
1850 }
1851 }
1852 }
1853 for (int i = start_offset; i < count1; ++i) {
1854 // Indicates any matched elements for this repeated field.
1855 bool match = false;
1856 int matched_j = -1;
1857
1858 for (int j = start_offset; j < count2; j++) {
1859 if (match_list2->at(n: j) != -1) {
1860 if (!is_treated_as_smart_set || num_diffs_list1[i] == 0 ||
1861 num_diffs_list1[match_list2->at(n: j)] == 0) {
1862 continue;
1863 }
1864 }
1865
1866 if (is_treated_as_smart_set) {
1867 num_diffs_reporter.Reset();
1868 match = IsMatch(repeated_field, key_comparator, message1: &message1, message2: &message2,
1869 parent_fields, reporter: &num_diffs_reporter, index1: i, index2: j);
1870 } else {
1871 match = IsMatch(repeated_field, key_comparator, message1: &message1, message2: &message2,
1872 parent_fields, reporter: nullptr, index1: i, index2: j);
1873 }
1874
1875 if (is_treated_as_smart_set) {
1876 if (match) {
1877 num_diffs_list1[i] = 0;
1878 } else if (repeated_field->cpp_type() ==
1879 FieldDescriptor::CPPTYPE_MESSAGE) {
1880 // Replace with the one with fewer diffs.
1881 const int32_t num_diffs = num_diffs_reporter.GetNumDiffs();
1882 if (num_diffs < num_diffs_list1[i]) {
1883 // If j has been already matched to some element, ensure the
1884 // current num_diffs is smaller.
1885 if (match_list2->at(n: j) == -1 ||
1886 num_diffs < num_diffs_list1[match_list2->at(n: j)]) {
1887 num_diffs_list1[i] = num_diffs;
1888 match = true;
1889 }
1890 }
1891 }
1892 }
1893
1894 if (match) {
1895 matched_j = j;
1896 if (!is_treated_as_smart_set || num_diffs_list1[i] == 0) {
1897 break;
1898 }
1899 }
1900 }
1901
1902 match = (matched_j != -1);
1903 if (match) {
1904 if (is_treated_as_smart_set && match_list2->at(n: matched_j) != -1) {
1905 // This is to revert the previously matched index in list2.
1906 match_list1->at(n: match_list2->at(n: matched_j)) = -1;
1907 match = false;
1908 }
1909 match_list1->at(n: i) = matched_j;
1910 match_list2->at(n: matched_j) = i;
1911 }
1912 if (!match && reporter == nullptr) return false;
1913 success = success && match;
1914 }
1915 }
1916
1917 if (IsTreatedAsSmartList(field: repeated_field)) {
1918 match_indices_for_smart_list_callback_(match_list1, match_list2);
1919 }
1920
1921 reporter_ = reporter;
1922
1923 return success;
1924}
1925
1926FieldComparator::ComparisonResult MessageDifferencer::GetFieldComparisonResult(
1927 const Message& message1, const Message& message2,
1928 const FieldDescriptor* field, int index1, int index2,
1929 const FieldContext* field_context) {
1930 FieldComparator* comparator = field_comparator_kind_ == kFCBase
1931 ? field_comparator_.base
1932 : field_comparator_.default_impl;
1933 return comparator->Compare(message_1: message1, message_2: message2, field, index_1: index1, index_2: index2,
1934 field_context);
1935}
1936
1937// ===========================================================================
1938
1939MessageDifferencer::Reporter::Reporter() {}
1940MessageDifferencer::Reporter::~Reporter() {}
1941
1942// ===========================================================================
1943
1944MessageDifferencer::MapKeyComparator::MapKeyComparator() {}
1945MessageDifferencer::MapKeyComparator::~MapKeyComparator() {}
1946
1947// ===========================================================================
1948
1949MessageDifferencer::IgnoreCriteria::IgnoreCriteria() {}
1950MessageDifferencer::IgnoreCriteria::~IgnoreCriteria() {}
1951
1952// ===========================================================================
1953
1954// Note that the printer's delimiter is not used, because if we are given a
1955// printer, we don't know its delimiter.
1956MessageDifferencer::StreamReporter::StreamReporter(
1957 io::ZeroCopyOutputStream* output)
1958 : printer_(new io::Printer(output, '$')),
1959 delete_printer_(true),
1960 report_modified_aggregates_(false),
1961 message1_(nullptr),
1962 message2_(nullptr) {}
1963
1964MessageDifferencer::StreamReporter::StreamReporter(io::Printer* printer)
1965 : printer_(printer),
1966 delete_printer_(false),
1967 report_modified_aggregates_(false),
1968 message1_(nullptr),
1969 message2_(nullptr) {}
1970
1971MessageDifferencer::StreamReporter::~StreamReporter() {
1972 if (delete_printer_) delete printer_;
1973}
1974
1975void MessageDifferencer::StreamReporter::PrintPath(
1976 const std::vector<SpecificField>& field_path, bool left_side) {
1977 for (size_t i = 0; i < field_path.size(); ++i) {
1978 SpecificField specific_field = field_path[i];
1979
1980 if (specific_field.field != nullptr &&
1981 specific_field.field->name() == "value") {
1982 // check to see if this the value label of a map value. If so, skip it
1983 // because it isn't meaningful
1984 if (i > 0 && field_path[i - 1].field->is_map()) {
1985 continue;
1986 }
1987 }
1988 if (i > 0) {
1989 printer_->Print(text: ".");
1990 }
1991 if (specific_field.field != NULL) {
1992 if (specific_field.field->is_extension()) {
1993 printer_->Print(text: "($name$)", args: "name", args: specific_field.field->full_name());
1994 } else {
1995 printer_->PrintRaw(data: specific_field.field->name());
1996 }
1997
1998 if (specific_field.field->is_map()) {
1999 PrintMapKey(left_side, specific_field);
2000 continue;
2001 }
2002 } else {
2003 printer_->PrintRaw(data: StrCat(a: specific_field.unknown_field_number));
2004 }
2005 if (left_side && specific_field.index >= 0) {
2006 printer_->Print(text: "[$name$]", args: "name", args: StrCat(a: specific_field.index));
2007 }
2008 if (!left_side && specific_field.new_index >= 0) {
2009 printer_->Print(text: "[$name$]", args: "name",
2010 args: StrCat(a: specific_field.new_index));
2011 }
2012 }
2013}
2014
2015
2016void MessageDifferencer::StreamReporter::PrintValue(
2017 const Message& message, const std::vector<SpecificField>& field_path,
2018 bool left_side) {
2019 const SpecificField& specific_field = field_path.back();
2020 const FieldDescriptor* field = specific_field.field;
2021 if (field != NULL) {
2022 std::string output;
2023 int index = left_side ? specific_field.index : specific_field.new_index;
2024 if (field->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) {
2025 const Reflection* reflection = message.GetReflection();
2026 const Message& field_message =
2027 field->is_repeated()
2028 ? reflection->GetRepeatedMessage(message, field, index)
2029 : reflection->GetMessage(message, field);
2030 const FieldDescriptor* fd = nullptr;
2031
2032 if (field->is_map() && message1_ != nullptr && message2_ != nullptr) {
2033 fd = field_message.GetDescriptor()->field(index: 1);
2034 if (fd->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) {
2035 output = PrintShortTextFormat(
2036 message: field_message.GetReflection()->GetMessage(message: field_message, field: fd));
2037 } else {
2038 TextFormat::PrintFieldValueToString(message: field_message, field: fd, index: -1, output: &output);
2039 }
2040 } else {
2041 output = PrintShortTextFormat(message: field_message);
2042 }
2043 if (output.empty()) {
2044 printer_->Print(text: "{ }");
2045 } else {
2046 if ((fd != nullptr) &&
2047 (fd->cpp_type() != FieldDescriptor::CPPTYPE_MESSAGE)) {
2048 printer_->PrintRaw(data: output);
2049 } else {
2050 printer_->Print(text: "{ $name$ }", args: "name", args: output);
2051 }
2052 }
2053 } else {
2054 TextFormat::PrintFieldValueToString(message, field, index, output: &output);
2055 printer_->PrintRaw(data: output);
2056 }
2057 } else {
2058 const UnknownFieldSet* unknown_fields =
2059 (left_side ? specific_field.unknown_field_set1
2060 : specific_field.unknown_field_set2);
2061 const UnknownField* unknown_field =
2062 &unknown_fields->field(index: left_side ? specific_field.unknown_field_index1
2063 : specific_field.unknown_field_index2);
2064 PrintUnknownFieldValue(unknown_field);
2065 }
2066}
2067
2068void MessageDifferencer::StreamReporter::PrintUnknownFieldValue(
2069 const UnknownField* unknown_field) {
2070 GOOGLE_CHECK(unknown_field != NULL) << " Cannot print NULL unknown_field.";
2071
2072 std::string output;
2073 switch (unknown_field->type()) {
2074 case UnknownField::TYPE_VARINT:
2075 output = StrCat(a: unknown_field->varint());
2076 break;
2077 case UnknownField::TYPE_FIXED32:
2078 output = StrCat(
2079 a: "0x", b: strings::Hex(unknown_field->fixed32(), strings::ZERO_PAD_8));
2080 break;
2081 case UnknownField::TYPE_FIXED64:
2082 output = StrCat(
2083 a: "0x", b: strings::Hex(unknown_field->fixed64(), strings::ZERO_PAD_16));
2084 break;
2085 case UnknownField::TYPE_LENGTH_DELIMITED:
2086 output = StringPrintf(
2087 format: "\"%s\"", CEscape(src: unknown_field->length_delimited()).c_str());
2088 break;
2089 case UnknownField::TYPE_GROUP:
2090 // TODO(kenton): Print the contents of the group like we do for
2091 // messages. Requires an equivalent of ShortDebugString() for
2092 // UnknownFieldSet.
2093 output = "{ ... }";
2094 break;
2095 }
2096 printer_->PrintRaw(data: output);
2097}
2098
2099void MessageDifferencer::StreamReporter::Print(const std::string& str) {
2100 printer_->Print(text: str.c_str());
2101}
2102
2103void MessageDifferencer::StreamReporter::PrintMapKey(
2104 bool left_side, const SpecificField& specific_field) {
2105 if (message1_ == nullptr || message2_ == nullptr) {
2106 GOOGLE_LOG(INFO) << "PrintPath cannot log map keys; "
2107 "use SetMessages to provide the messages "
2108 "being compared prior to any processing.";
2109 return;
2110 }
2111
2112 const Message* found_message =
2113 left_side ? specific_field.map_entry1 : specific_field.map_entry2;
2114 std::string key_string = "";
2115 if (found_message != nullptr) {
2116 // NB: the map key is always the first field
2117 const FieldDescriptor* fd = found_message->GetDescriptor()->field(index: 0);
2118 if (fd->cpp_type() == FieldDescriptor::CPPTYPE_STRING) {
2119 // Not using PrintFieldValueToString for strings to avoid extra
2120 // characters
2121 key_string = found_message->GetReflection()->GetString(
2122 message: *found_message, field: found_message->GetDescriptor()->field(index: 0));
2123 } else {
2124 TextFormat::PrintFieldValueToString(message: *found_message, field: fd, index: -1, output: &key_string);
2125 }
2126 if (key_string.empty()) {
2127 key_string = "''";
2128 }
2129 printer_->PrintRaw(data: StrCat(a: "[", b: key_string, c: "]"));
2130 }
2131}
2132
2133void MessageDifferencer::StreamReporter::ReportAdded(
2134 const Message& /*message1*/, const Message& message2,
2135 const std::vector<SpecificField>& field_path) {
2136 printer_->Print(text: "added: ");
2137 PrintPath(field_path, left_side: false);
2138 printer_->Print(text: ": ");
2139 PrintValue(message: message2, field_path, left_side: false);
2140 printer_->Print(text: "\n"); // Print for newlines.
2141}
2142
2143void MessageDifferencer::StreamReporter::ReportDeleted(
2144 const Message& message1, const Message& /*message2*/,
2145 const std::vector<SpecificField>& field_path) {
2146 printer_->Print(text: "deleted: ");
2147 PrintPath(field_path, left_side: true);
2148 printer_->Print(text: ": ");
2149 PrintValue(message: message1, field_path, left_side: true);
2150 printer_->Print(text: "\n"); // Print for newlines
2151}
2152
2153void MessageDifferencer::StreamReporter::ReportModified(
2154 const Message& message1, const Message& message2,
2155 const std::vector<SpecificField>& field_path) {
2156 if (!report_modified_aggregates_ && field_path.back().field == NULL) {
2157 if (field_path.back().unknown_field_type == UnknownField::TYPE_GROUP) {
2158 // Any changes to the subfields have already been printed.
2159 return;
2160 }
2161 } else if (!report_modified_aggregates_) {
2162 if (field_path.back().field->cpp_type() ==
2163 FieldDescriptor::CPPTYPE_MESSAGE) {
2164 // Any changes to the subfields have already been printed.
2165 return;
2166 }
2167 }
2168
2169 printer_->Print(text: "modified: ");
2170 PrintPath(field_path, left_side: true);
2171 if (CheckPathChanged(field_path)) {
2172 printer_->Print(text: " -> ");
2173 PrintPath(field_path, left_side: false);
2174 }
2175 printer_->Print(text: ": ");
2176 PrintValue(message: message1, field_path, left_side: true);
2177 printer_->Print(text: " -> ");
2178 PrintValue(message: message2, field_path, left_side: false);
2179 printer_->Print(text: "\n"); // Print for newlines.
2180}
2181
2182void MessageDifferencer::StreamReporter::ReportMoved(
2183 const Message& message1, const Message& /*message2*/,
2184 const std::vector<SpecificField>& field_path) {
2185 printer_->Print(text: "moved: ");
2186 PrintPath(field_path, left_side: true);
2187 printer_->Print(text: " -> ");
2188 PrintPath(field_path, left_side: false);
2189 printer_->Print(text: " : ");
2190 PrintValue(message: message1, field_path, left_side: true);
2191 printer_->Print(text: "\n"); // Print for newlines.
2192}
2193
2194void MessageDifferencer::StreamReporter::ReportMatched(
2195 const Message& message1, const Message& /*message2*/,
2196 const std::vector<SpecificField>& field_path) {
2197 printer_->Print(text: "matched: ");
2198 PrintPath(field_path, left_side: true);
2199 if (CheckPathChanged(field_path)) {
2200 printer_->Print(text: " -> ");
2201 PrintPath(field_path, left_side: false);
2202 }
2203 printer_->Print(text: " : ");
2204 PrintValue(message: message1, field_path, left_side: true);
2205 printer_->Print(text: "\n"); // Print for newlines.
2206}
2207
2208void MessageDifferencer::StreamReporter::ReportIgnored(
2209 const Message& /*message1*/, const Message& /*message2*/,
2210 const std::vector<SpecificField>& field_path) {
2211 printer_->Print(text: "ignored: ");
2212 PrintPath(field_path, left_side: true);
2213 if (CheckPathChanged(field_path)) {
2214 printer_->Print(text: " -> ");
2215 PrintPath(field_path, left_side: false);
2216 }
2217 printer_->Print(text: "\n"); // Print for newlines.
2218}
2219
2220void MessageDifferencer::StreamReporter::SetMessages(const Message& message1,
2221 const Message& message2) {
2222 message1_ = &message1;
2223 message2_ = &message2;
2224}
2225
2226void MessageDifferencer::StreamReporter::ReportUnknownFieldIgnored(
2227 const Message& /*message1*/, const Message& /*message2*/,
2228 const std::vector<SpecificField>& field_path) {
2229 printer_->Print(text: "ignored: ");
2230 PrintPath(field_path, left_side: true);
2231 if (CheckPathChanged(field_path)) {
2232 printer_->Print(text: " -> ");
2233 PrintPath(field_path, left_side: false);
2234 }
2235 printer_->Print(text: "\n"); // Print for newlines.
2236}
2237
2238MessageDifferencer::MapKeyComparator*
2239MessageDifferencer::CreateMultipleFieldsMapKeyComparator(
2240 const std::vector<std::vector<const FieldDescriptor*> >& key_field_paths) {
2241 return new MultipleFieldsMapKeyComparator(this, key_field_paths);
2242}
2243
2244} // namespace util
2245} // namespace protobuf
2246} // namespace google
2247