aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/google/protobuf/util/message_differencer.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/google/protobuf/util/message_differencer.cc')
-rw-r--r--src/google/protobuf/util/message_differencer.cc318
1 files changed, 200 insertions, 118 deletions
diff --git a/src/google/protobuf/util/message_differencer.cc b/src/google/protobuf/util/message_differencer.cc
index 03a334b6..9842f64c 100644
--- a/src/google/protobuf/util/message_differencer.cc
+++ b/src/google/protobuf/util/message_differencer.cc
@@ -40,9 +40,6 @@
#include <algorithm>
#include <memory>
-#ifndef _SHARED_PTR_H
-#include <google/protobuf/stubs/shared_ptr.h>
-#endif
#include <utility>
#include <google/protobuf/stubs/callback.h>
@@ -53,6 +50,7 @@
#include <google/protobuf/io/printer.h>
#include <google/protobuf/io/zero_copy_stream.h>
#include <google/protobuf/io/zero_copy_stream_impl.h>
+#include <google/protobuf/descriptor.pb.h>
#include <google/protobuf/dynamic_message.h>
#include <google/protobuf/text_format.h>
#include <google/protobuf/util/field_comparator.h>
@@ -73,7 +71,7 @@ class MessageDifferencer::MultipleFieldsMapKeyComparator
public:
MultipleFieldsMapKeyComparator(
MessageDifferencer* message_differencer,
- const vector<vector<const FieldDescriptor*> >& key_field_paths)
+ const std::vector<std::vector<const FieldDescriptor*> >& key_field_paths)
: message_differencer_(message_differencer),
key_field_paths_(key_field_paths) {
GOOGLE_CHECK(!key_field_paths_.empty());
@@ -85,14 +83,14 @@ class MessageDifferencer::MultipleFieldsMapKeyComparator
MessageDifferencer* message_differencer,
const FieldDescriptor* key)
: message_differencer_(message_differencer) {
- vector<const FieldDescriptor*> key_field_path;
+ std::vector<const FieldDescriptor*> key_field_path;
key_field_path.push_back(key);
key_field_paths_.push_back(key_field_path);
}
virtual bool IsMatch(
const Message& message1,
const Message& message2,
- const vector<SpecificField>& parent_fields) const {
+ const std::vector<SpecificField>& parent_fields) const {
for (int i = 0; i < key_field_paths_.size(); ++i) {
if (!IsMatchInternal(message1, message2, parent_fields,
key_field_paths_[i], 0)) {
@@ -105,11 +103,11 @@ class MessageDifferencer::MultipleFieldsMapKeyComparator
bool IsMatchInternal(
const Message& message1,
const Message& message2,
- const vector<SpecificField>& parent_fields,
- const vector<const FieldDescriptor*>& key_field_path,
+ const std::vector<SpecificField>& parent_fields,
+ const std::vector<const FieldDescriptor*>& key_field_path,
int path_index) const {
const FieldDescriptor* field = key_field_path[path_index];
- vector<SpecificField> current_parent_fields(parent_fields);
+ std::vector<SpecificField> current_parent_fields(parent_fields);
if (path_index == key_field_path.size() - 1) {
if (field->is_repeated()) {
if (!message_differencer_->CompareRepeatedField(
@@ -146,10 +144,36 @@ class MessageDifferencer::MultipleFieldsMapKeyComparator
}
}
MessageDifferencer* message_differencer_;
- vector<vector<const FieldDescriptor*> > key_field_paths_;
+ std::vector<std::vector<const FieldDescriptor*> > key_field_paths_;
GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(MultipleFieldsMapKeyComparator);
};
+MessageDifferencer::MapEntryKeyComparator::MapEntryKeyComparator(
+ MessageDifferencer* message_differencer)
+ : message_differencer_(message_differencer) {}
+
+bool MessageDifferencer::MapEntryKeyComparator::IsMatch(
+ const Message& message1, const Message& message2,
+ const std::vector<SpecificField>& parent_fields) const {
+ // Map entry has its key in the field with tag 1. See the comment for
+ // map_entry in MessageOptions.
+ const FieldDescriptor* key = message1.GetDescriptor()->FindFieldByNumber(1);
+ // If key is not present in message1 and we're doing partial comparison or if
+ // map key is explicitly ignored treat the field as set instead,
+ const bool treat_as_set =
+ (message_differencer_->scope() == PARTIAL &&
+ !message1.GetReflection()->HasField(message1, key)) ||
+ message_differencer_->IsIgnored(message1, message2, key, parent_fields);
+
+ std::vector<SpecificField> current_parent_fields(parent_fields);
+ if (treat_as_set) {
+ return message_differencer_->Compare(message1, message2,
+ &current_parent_fields);
+ }
+ return message_differencer_->CompareFieldValueUsingParentFields(
+ message1, message2, key, -1, -1, &current_parent_fields);
+}
+
bool MessageDifferencer::Equals(const Message& message1,
const Message& message2) {
MessageDifferencer differencer;
@@ -191,8 +215,10 @@ MessageDifferencer::MessageDifferencer()
message_field_comparison_(EQUAL),
scope_(FULL),
repeated_field_comparison_(AS_LIST),
+ map_entry_key_comparator_(this),
report_matches_(false),
- output_string_(NULL) { }
+ report_moves_(true),
+ output_string_(NULL) {}
MessageDifferencer::~MessageDifferencer() {
for (int i = 0; i < owned_key_comparators_.size(); ++i) {
@@ -283,10 +309,10 @@ void MessageDifferencer::TreatAsMap(const FieldDescriptor* field,
void MessageDifferencer::TreatAsMapWithMultipleFieldsAsKey(
const FieldDescriptor* field,
- const vector<const FieldDescriptor*>& key_fields) {
- vector<vector<const FieldDescriptor*> > key_field_paths;
+ const std::vector<const FieldDescriptor*>& key_fields) {
+ std::vector<std::vector<const FieldDescriptor*> > key_field_paths;
for (int i = 0; i < key_fields.size(); ++i) {
- vector<const FieldDescriptor*> key_field_path;
+ std::vector<const FieldDescriptor*> key_field_path;
key_field_path.push_back(key_fields[i]);
key_field_paths.push_back(key_field_path);
}
@@ -295,14 +321,15 @@ void MessageDifferencer::TreatAsMapWithMultipleFieldsAsKey(
void MessageDifferencer::TreatAsMapWithMultipleFieldPathsAsKey(
const FieldDescriptor* field,
- const vector<vector<const FieldDescriptor*> >& key_field_paths) {
+ const std::vector<std::vector<const FieldDescriptor*> >& key_field_paths) {
GOOGLE_CHECK(field->is_repeated()) << "Field must be repeated: "
<< field->full_name();
GOOGLE_CHECK_EQ(FieldDescriptor::CPPTYPE_MESSAGE, field->cpp_type())
<< "Field has to be message type. Field name is: "
<< field->full_name();
for (int i = 0; i < key_field_paths.size(); ++i) {
- const vector<const FieldDescriptor*>& key_field_path = key_field_paths[i];
+ const std::vector<const FieldDescriptor*>& key_field_path =
+ key_field_paths[i];
for (int j = 0; j < key_field_path.size(); ++j) {
const FieldDescriptor* parent_field =
j == 0 ? field : key_field_path[j - 1];
@@ -333,9 +360,6 @@ void MessageDifferencer::TreatAsMapUsingKeyComparator(
const MapKeyComparator* key_comparator) {
GOOGLE_CHECK(field->is_repeated()) << "Field must be repeated: "
<< field->full_name();
- GOOGLE_CHECK_EQ(FieldDescriptor::CPPTYPE_MESSAGE, field->cpp_type())
- << "Field has to be message type. Field name is: "
- << field->full_name();
GOOGLE_CHECK(set_fields_.find(field) == set_fields_.end())
<< "Cannot treat this repeated field as both Map and Set for "
<< "comparison.";
@@ -390,7 +414,7 @@ bool MessageDifferencer::FieldBefore(const FieldDescriptor* field1,
bool MessageDifferencer::Compare(const Message& message1,
const Message& message2) {
- vector<SpecificField> parent_fields;
+ std::vector<SpecificField> parent_fields;
bool result = false;
@@ -411,20 +435,20 @@ bool MessageDifferencer::Compare(const Message& message1,
bool MessageDifferencer::CompareWithFields(
const Message& message1,
const Message& message2,
- const vector<const FieldDescriptor*>& message1_fields_arg,
- const vector<const FieldDescriptor*>& message2_fields_arg) {
+ const std::vector<const FieldDescriptor*>& message1_fields_arg,
+ const std::vector<const FieldDescriptor*>& message2_fields_arg) {
if (message1.GetDescriptor() != message2.GetDescriptor()) {
GOOGLE_LOG(DFATAL) << "Comparison between two messages with different "
<< "descriptors.";
return false;
}
- vector<SpecificField> parent_fields;
+ std::vector<SpecificField> parent_fields;
bool result = false;
- vector<const FieldDescriptor*> message1_fields(message1_fields_arg);
- vector<const FieldDescriptor*> message2_fields(message2_fields_arg);
+ std::vector<const FieldDescriptor*> message1_fields(message1_fields_arg);
+ std::vector<const FieldDescriptor*> message2_fields(message2_fields_arg);
std::sort(message1_fields.begin(), message1_fields.end(), FieldBefore);
std::sort(message2_fields.begin(), message2_fields.end(), FieldBefore);
@@ -451,7 +475,7 @@ bool MessageDifferencer::CompareWithFields(
bool MessageDifferencer::Compare(
const Message& message1,
const Message& message2,
- vector<SpecificField>* parent_fields) {
+ std::vector<SpecificField>* parent_fields) {
const Descriptor* descriptor1 = message1.GetDescriptor();
const Descriptor* descriptor2 = message2.GetDescriptor();
if (descriptor1 != descriptor2) {
@@ -463,9 +487,13 @@ bool MessageDifferencer::Compare(
}
// Expand google.protobuf.Any payload if possible.
if (descriptor1->full_name() == internal::kAnyFullTypeName) {
- google::protobuf::scoped_ptr<Message> data1;
- google::protobuf::scoped_ptr<Message> data2;
+ std::unique_ptr<Message> data1;
+ std::unique_ptr<Message> data2;
if (UnpackAny(message1, &data1) && UnpackAny(message2, &data2)) {
+ // Avoid DFATAL for different descriptors in google.protobuf.Any payloads.
+ if (data1->GetDescriptor() != data2->GetDescriptor()) {
+ return false;
+ }
return Compare(*data1, *data2, parent_fields);
}
}
@@ -473,14 +501,28 @@ bool MessageDifferencer::Compare(
const Reflection* reflection2 = message2.GetReflection();
// Retrieve all the set fields, including extensions.
- vector<const FieldDescriptor*> message1_fields;
+ std::vector<const FieldDescriptor*> message1_fields;
message1_fields.reserve(1 + message1.GetDescriptor()->field_count());
- vector<const FieldDescriptor*> message2_fields;
+ std::vector<const FieldDescriptor*> message2_fields;
message2_fields.reserve(1 + message2.GetDescriptor()->field_count());
- reflection1->ListFields(message1, &message1_fields);
- reflection2->ListFields(message2, &message2_fields);
+ if (descriptor1->options().map_entry()) {
+ if (scope_ == PARTIAL) {
+ reflection1->ListFields(message1, &message1_fields);
+ } else {
+ // Map entry fields are always considered present.
+ for (int i = 0; i < descriptor1->field_count(); i++) {
+ message1_fields.push_back(descriptor1->field(i));
+ }
+ }
+ for (int i = 0; i < descriptor1->field_count(); i++) {
+ message2_fields.push_back(descriptor1->field(i));
+ }
+ } else {
+ reflection1->ListFields(message1, &message1_fields);
+ reflection2->ListFields(message2, &message2_fields);
+ }
// Add sentinel values to deal with the
// case where the number of the fields in
@@ -514,15 +556,15 @@ bool MessageDifferencer::Compare(
bool MessageDifferencer::CompareRequestedFieldsUsingSettings(
const Message& message1,
const Message& message2,
- const vector<const FieldDescriptor*>& message1_fields,
- const vector<const FieldDescriptor*>& message2_fields,
- vector<SpecificField>* parent_fields) {
+ const std::vector<const FieldDescriptor*>& message1_fields,
+ const std::vector<const FieldDescriptor*>& message2_fields,
+ std::vector<SpecificField>* parent_fields) {
if (scope_ == FULL) {
if (message_field_comparison_ == EQUIVALENT) {
// We need to merge the field lists of both messages (i.e.
// we are merely checking for a difference in field values,
// rather than the addition or deletion of fields).
- vector<const FieldDescriptor*> fields_union;
+ std::vector<const FieldDescriptor*> fields_union;
CombineFields(message1_fields, FULL, message2_fields, FULL,
&fields_union);
return CompareWithFieldsInternal(message1, message2, fields_union,
@@ -544,7 +586,7 @@ bool MessageDifferencer::CompareRequestedFieldsUsingSettings(
// but only the intersection for message2. This way, any fields
// only present in message2 will be ignored, but any fields only
// present in message1 will be marked as a difference.
- vector<const FieldDescriptor*> fields_intersection;
+ std::vector<const FieldDescriptor*> fields_intersection;
CombineFields(message1_fields, PARTIAL, message2_fields, PARTIAL,
&fields_intersection);
return CompareWithFieldsInternal(message1, message2, message1_fields,
@@ -554,11 +596,11 @@ bool MessageDifferencer::CompareRequestedFieldsUsingSettings(
}
void MessageDifferencer::CombineFields(
- const vector<const FieldDescriptor*>& fields1,
+ const std::vector<const FieldDescriptor*>& fields1,
Scope fields1_scope,
- const vector<const FieldDescriptor*>& fields2,
+ const std::vector<const FieldDescriptor*>& fields2,
Scope fields2_scope,
- vector<const FieldDescriptor*>* combined_fields) {
+ std::vector<const FieldDescriptor*>* combined_fields) {
int index1 = 0;
int index2 = 0;
@@ -588,9 +630,9 @@ void MessageDifferencer::CombineFields(
bool MessageDifferencer::CompareWithFieldsInternal(
const Message& message1,
const Message& message2,
- const vector<const FieldDescriptor*>& message1_fields,
- const vector<const FieldDescriptor*>& message2_fields,
- vector<SpecificField>* parent_fields) {
+ const std::vector<const FieldDescriptor*>& message1_fields,
+ const std::vector<const FieldDescriptor*>& message2_fields,
+ std::vector<SpecificField>* parent_fields) {
bool isDifferent = false;
int field_index1 = 0;
int field_index2 = 0;
@@ -626,6 +668,7 @@ bool MessageDifferencer::CompareWithFieldsInternal(
}
if (reporter_ != NULL) {
+ assert(field1 != NULL);
int count = field1->is_repeated() ?
reflection1->FieldSize(message1, field1) : 1;
@@ -706,6 +749,7 @@ bool MessageDifferencer::CompareWithFieldsInternal(
}
bool fieldDifferent = false;
+ assert(field1 != NULL);
if (field1->is_repeated()) {
fieldDifferent = !CompareRepeatedField(message1, message2, field1,
parent_fields);
@@ -744,13 +788,12 @@ bool MessageDifferencer::CompareWithFieldsInternal(
return !isDifferent;
}
-bool MessageDifferencer::IsMatch(const FieldDescriptor* repeated_field,
- const MapKeyComparator* key_comparator,
- const Message* message1,
- const Message* message2,
- const vector<SpecificField>& parent_fields,
- int index1, int index2) {
- vector<SpecificField> current_parent_fields(parent_fields);
+bool MessageDifferencer::IsMatch(
+ const FieldDescriptor* repeated_field,
+ const MapKeyComparator* key_comparator, const Message* message1,
+ const Message* message2, const std::vector<SpecificField>& parent_fields,
+ int index1, int index2) {
+ std::vector<SpecificField> current_parent_fields(parent_fields);
if (repeated_field->cpp_type() != FieldDescriptor::CPPTYPE_MESSAGE) {
return CompareFieldValueUsingParentFields(
*message1, *message2, repeated_field, index1, index2,
@@ -777,6 +820,8 @@ bool MessageDifferencer::IsMatch(const FieldDescriptor* repeated_field,
reflection2->GetRepeatedMessage(*message2, repeated_field, index2);
SpecificField specific_field;
specific_field.field = repeated_field;
+ specific_field.index = index1;
+ specific_field.new_index = index2;
current_parent_fields.push_back(specific_field);
match = key_comparator->IsMatch(m1, m2, current_parent_fields);
}
@@ -790,7 +835,7 @@ bool MessageDifferencer::CompareRepeatedField(
const Message& message1,
const Message& message2,
const FieldDescriptor* repeated_field,
- vector<SpecificField>* parent_fields) {
+ std::vector<SpecificField>* parent_fields) {
// the input FieldDescriptor is guaranteed to be repeated field.
const Reflection* reflection1 = message1.GetReflection();
const Reflection* reflection2 = message2.GetReflection();
@@ -811,8 +856,8 @@ bool MessageDifferencer::CompareRepeatedField(
// These two list are used for store the index of the correspondent
// element in peer repeated field.
- vector<int> match_list1;
- vector<int> match_list2;
+ std::vector<int> match_list1;
+ std::vector<int> match_list2;
// Try to match indices of the repeated fields. Return false if match fails
// and there's no detailed report needed.
@@ -847,7 +892,8 @@ bool MessageDifferencer::CompareRepeatedField(
parent_fields->pop_back();
fieldDifferent = true;
} else if (reporter_ != NULL &&
- specific_field.index != specific_field.new_index) {
+ specific_field.index != specific_field.new_index &&
+ !specific_field.field->is_map() && report_moves_) {
parent_fields->push_back(specific_field);
reporter_->ReportMoved(message1, message2, *parent_fields);
parent_fields->pop_back();
@@ -875,6 +921,7 @@ bool MessageDifferencer::CompareRepeatedField(
for (int i = 0; i < count1; ++i) {
if (match_list1[i] != -1) continue;
+ assert(reporter_ != NULL);
specific_field.index = i;
parent_fields->push_back(specific_field);
reporter_->ReportDeleted(message1, message2, *parent_fields);
@@ -896,7 +943,7 @@ bool MessageDifferencer::CompareFieldValue(const Message& message1,
bool MessageDifferencer::CompareFieldValueUsingParentFields(
const Message& message1, const Message& message2,
const FieldDescriptor* field, int index1, int index2,
- vector<SpecificField>* parent_fields) {
+ std::vector<SpecificField>* parent_fields) {
FieldContext field_context(parent_fields);
FieldComparator::ComparisonResult result = GetFieldComparisonResult(
message1, message2, field, index1, index2, &field_context);
@@ -935,8 +982,10 @@ bool MessageDifferencer::CompareFieldValueUsingParentFields(
}
bool MessageDifferencer::CheckPathChanged(
- const vector<SpecificField>& field_path) {
+ const std::vector<SpecificField>& field_path) {
for (int i = 0; i < field_path.size(); ++i) {
+ // Don't check indexes for map entries -- maps are unordered.
+ if (field_path[i].field != NULL && field_path[i].field->is_map()) continue;
if (field_path[i].index != field_path[i].new_index) return true;
}
return false;
@@ -944,7 +993,6 @@ bool MessageDifferencer::CheckPathChanged(
bool MessageDifferencer::IsTreatedAsSet(const FieldDescriptor* field) {
if (!field->is_repeated()) return false;
- if (field->is_map()) return true;
if (repeated_field_comparison_ == AS_SET)
return list_fields_.find(field) == list_fields_.end();
return (set_fields_.find(field) != set_fields_.end());
@@ -959,7 +1007,7 @@ bool MessageDifferencer::IsIgnored(
const Message& message1,
const Message& message2,
const FieldDescriptor* field,
- const vector<SpecificField>& parent_fields) {
+ const std::vector<SpecificField>& parent_fields) {
if (ignored_fields_.find(field) != ignored_fields_.end()) {
return true;
}
@@ -974,7 +1022,8 @@ bool MessageDifferencer::IsIgnored(
bool MessageDifferencer::IsUnknownFieldIgnored(
const Message& message1, const Message& message2,
- const SpecificField& field, const vector<SpecificField>& parent_fields) {
+ const SpecificField& field,
+ const std::vector<SpecificField>& parent_fields) {
for (int i = 0; i < ignore_criteria_.size(); ++i) {
if (ignore_criteria_[i]->IsUnknownFieldIgnored(message1, message2, field,
parent_fields)) {
@@ -984,19 +1033,25 @@ bool MessageDifferencer::IsUnknownFieldIgnored(
return false;
}
-const MessageDifferencer::MapKeyComparator* MessageDifferencer
- ::GetMapKeyComparator(const FieldDescriptor* field) {
+const MessageDifferencer::MapKeyComparator*
+MessageDifferencer ::GetMapKeyComparator(const FieldDescriptor* field) const {
if (!field->is_repeated()) return NULL;
- if (map_field_key_comparator_.find(field) !=
- map_field_key_comparator_.end()) {
- return map_field_key_comparator_[field];
+ FieldKeyComparatorMap::const_iterator it =
+ map_field_key_comparator_.find(field);
+ if (it != map_field_key_comparator_.end()) {
+ return it->second;
+ }
+ if (field->is_map()) {
+ // field cannot already be treated as list or set since TreatAsList() and
+ // TreatAsSet() call GetMapKeyComparator() and fail if it returns non-NULL.
+ return &map_entry_key_comparator_;
}
return NULL;
}
namespace {
-typedef pair<int, const UnknownField*> IndexUnknownFieldPair;
+typedef std::pair<int, const UnknownField*> IndexUnknownFieldPair;
struct UnknownFieldOrdering {
inline bool operator()(const IndexUnknownFieldPair& a,
@@ -1010,7 +1065,7 @@ struct UnknownFieldOrdering {
} // namespace
bool MessageDifferencer::UnpackAny(const Message& any,
- google::protobuf::scoped_ptr<Message>* data) {
+ std::unique_ptr<Message>* data) {
const Reflection* reflection = any.GetReflection();
const FieldDescriptor* type_url_field;
const FieldDescriptor* value_field;
@@ -1047,7 +1102,7 @@ bool MessageDifferencer::CompareUnknownFields(
const Message& message1, const Message& message2,
const google::protobuf::UnknownFieldSet& unknown_field_set1,
const google::protobuf::UnknownFieldSet& unknown_field_set2,
- vector<SpecificField>* parent_field) {
+ std::vector<SpecificField>* parent_field) {
// Ignore unknown fields in EQUIVALENT mode.
if (message_field_comparison_ == EQUIVALENT) return true;
@@ -1063,8 +1118,8 @@ bool MessageDifferencer::CompareUnknownFields(
// two sets -- that is, differing values for the same tag. We use
// IndexUnknownFieldPairs to keep track of the field's original index for
// reporting purposes.
- vector<IndexUnknownFieldPair> fields1; // unknown_field_set1, sorted
- vector<IndexUnknownFieldPair> fields2; // unknown_field_set2, sorted
+ std::vector<IndexUnknownFieldPair> fields1; // unknown_field_set1, sorted
+ std::vector<IndexUnknownFieldPair> fields2; // unknown_field_set2, sorted
fields1.reserve(unknown_field_set1.field_count());
fields2.reserve(unknown_field_set2.field_count());
@@ -1267,7 +1322,7 @@ class MaximumMatcher {
// the x-th node on the right side is matched to y-th node on the left side.
// match_list1[i] == -1 means the node is not matched. Same with match_list2.
MaximumMatcher(int count1, int count2, NodeMatchCallback* callback,
- vector<int>* match_list1, vector<int>* match_list2);
+ std::vector<int>* match_list1, std::vector<int>* match_list2);
// Find a maximum match and return the number of matched node pairs.
// If early_return is true, this method will return 0 immediately when it
// finds that not all nodes on the left side can be matched.
@@ -1279,21 +1334,21 @@ class MaximumMatcher {
// Find an argumenting path starting from the node v on the left side. If a
// path can be found, update match_list2_ to reflect the path and return
// true.
- bool FindArgumentPathDFS(int v, vector<bool>* visited);
+ bool FindArgumentPathDFS(int v, std::vector<bool>* visited);
int count1_;
int count2_;
- google::protobuf::scoped_ptr<NodeMatchCallback> match_callback_;
- map<pair<int, int>, bool> cached_match_results_;
- vector<int>* match_list1_;
- vector<int>* match_list2_;
+ std::unique_ptr<NodeMatchCallback> match_callback_;
+ std::map<std::pair<int, int>, bool> cached_match_results_;
+ std::vector<int>* match_list1_;
+ std::vector<int>* match_list2_;
GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(MaximumMatcher);
};
MaximumMatcher::MaximumMatcher(int count1, int count2,
NodeMatchCallback* callback,
- vector<int>* match_list1,
- vector<int>* match_list2)
+ std::vector<int>* match_list1,
+ std::vector<int>* match_list2)
: count1_(count1), count2_(count2), match_callback_(callback),
match_list1_(match_list1), match_list2_(match_list2) {
match_list1_->assign(count1, -1);
@@ -1303,7 +1358,7 @@ MaximumMatcher::MaximumMatcher(int count1, int count2,
int MaximumMatcher::FindMaximumMatch(bool early_return) {
int result = 0;
for (int i = 0; i < count1_; ++i) {
- vector<bool> visited(count1_);
+ std::vector<bool> visited(count1_);
if (FindArgumentPathDFS(i, &visited)) {
++result;
} else if (early_return) {
@@ -1321,8 +1376,9 @@ int MaximumMatcher::FindMaximumMatch(bool early_return) {
}
bool MaximumMatcher::Match(int left, int right) {
- pair<int, int> p(left, right);
- map<pair<int, int>, bool>::iterator it = cached_match_results_.find(p);
+ std::pair<int, int> p(left, right);
+ std::map<std::pair<int, int>, bool>::iterator it =
+ cached_match_results_.find(p);
if (it != cached_match_results_.end()) {
return it->second;
}
@@ -1330,7 +1386,7 @@ bool MaximumMatcher::Match(int left, int right) {
return cached_match_results_[p];
}
-bool MaximumMatcher::FindArgumentPathDFS(int v, vector<bool>* visited) {
+bool MaximumMatcher::FindArgumentPathDFS(int v, std::vector<bool>* visited) {
(*visited)[v] = true;
// We try to match those un-matched nodes on the right side first. This is
// the step that the navie greedy matching algorithm uses. In the best cases
@@ -1366,9 +1422,9 @@ bool MessageDifferencer::MatchRepeatedFieldIndices(
const Message& message1,
const Message& message2,
const FieldDescriptor* repeated_field,
- const vector<SpecificField>& parent_fields,
- vector<int>* match_list1,
- vector<int>* match_list2) {
+ const std::vector<SpecificField>& parent_fields,
+ std::vector<int>* match_list1,
+ std::vector<int>* match_list2) {
const int count1 =
message1.GetReflection()->FieldSize(message1, repeated_field);
const int count2 =
@@ -1378,9 +1434,6 @@ bool MessageDifferencer::MatchRepeatedFieldIndices(
match_list1->assign(count1, -1);
match_list2->assign(count2, -1);
- SpecificField specific_field;
- specific_field.field = repeated_field;
-
bool success = true;
// Find potential match if this is a special repeated field.
if (key_comparator != NULL || IsTreatedAsSet(repeated_field)) {
@@ -1389,7 +1442,8 @@ bool MessageDifferencer::MatchRepeatedFieldIndices(
// doesn't necessarily imply Compare(b, c). Therefore a naive greedy
// algorithm will fail to find a maximum matching.
// Here we use the argumenting path algorithm.
- MaximumMatcher::NodeMatchCallback* callback = NewPermanentCallback(
+ MaximumMatcher::NodeMatchCallback* callback =
+ ::google::protobuf::NewPermanentCallback(
this, &MessageDifferencer::IsMatch,
repeated_field, key_comparator,
&message1, &message2, parent_fields);
@@ -1402,24 +1456,35 @@ bool MessageDifferencer::MatchRepeatedFieldIndices(
if (match_count != count1 && reporter_ == NULL) return false;
success = success && (match_count == count1);
} else {
- for (int i = 0; i < count1; ++i) {
+ int start_offset = 0;
+ // If the two repeated fields are treated as sets, optimize for the case
+ // where both start with same items stored in the same order.
+ if (IsTreatedAsSet(repeated_field)) {
+ start_offset = std::min(count1, count2);
+ for (int i = 0; i < count1 && i < count2; i++) {
+ if (IsMatch(repeated_field, key_comparator, &message1, &message2,
+ parent_fields, i, i)) {
+ match_list1->at(i) = i;
+ match_list2->at(i) = i;
+ } else {
+ start_offset = i;
+ break;
+ }
+ }
+ }
+ for (int i = start_offset; i < count1; ++i) {
// Indicates any matched elements for this repeated field.
bool match = false;
- specific_field.index = i;
- specific_field.new_index = i;
-
- for (int j = 0; j < count2; j++) {
+ for (int j = start_offset; j < count2; j++) {
if (match_list2->at(j) != -1) continue;
- specific_field.index = i;
- specific_field.new_index = j;
match = IsMatch(repeated_field, key_comparator,
&message1, &message2, parent_fields, i, j);
if (match) {
- match_list1->at(specific_field.index) = specific_field.new_index;
- match_list2->at(specific_field.new_index) = specific_field.index;
+ match_list1->at(i) = j;
+ match_list2->at(j) = i;
break;
}
}
@@ -1482,7 +1547,7 @@ MessageDifferencer::StreamReporter::~StreamReporter() {
}
void MessageDifferencer::StreamReporter::PrintPath(
- const vector<SpecificField>& field_path, bool left_side) {
+ const std::vector<SpecificField>& field_path, bool left_side) {
for (int i = 0; i < field_path.size(); ++i) {
if (i > 0) {
printer_->Print(".");
@@ -1497,6 +1562,10 @@ void MessageDifferencer::StreamReporter::PrintPath(
} else {
printer_->PrintRaw(specific_field.field->name());
}
+ if (specific_field.field->is_map()) {
+ // Don't print index in a map field; they are semantically unordered.
+ continue;
+ }
} else {
printer_->PrintRaw(SimpleItoa(specific_field.unknown_field_number));
}
@@ -1509,9 +1578,15 @@ void MessageDifferencer::StreamReporter::PrintPath(
}
}
+void MessageDifferencer::StreamReporter::PrintPath(
+ const std::vector<SpecificField>& field_path, bool left_side,
+ const Message& message) {
+ PrintPath(field_path, left_side);
+}
+
void MessageDifferencer::
StreamReporter::PrintValue(const Message& message,
- const vector<SpecificField>& field_path,
+ const std::vector<SpecificField>& field_path,
bool left_side) {
const SpecificField& specific_field = field_path.back();
const FieldDescriptor* field = specific_field.field;
@@ -1584,9 +1659,9 @@ void MessageDifferencer::StreamReporter::Print(const string& str) {
void MessageDifferencer::StreamReporter::ReportAdded(
const Message& message1,
const Message& message2,
- const vector<SpecificField>& field_path) {
+ const std::vector<SpecificField>& field_path) {
printer_->Print("added: ");
- PrintPath(field_path, false);
+ PrintPath(field_path, false, message2);
printer_->Print(": ");
PrintValue(message2, field_path, false);
printer_->Print("\n"); // Print for newlines.
@@ -1595,9 +1670,9 @@ void MessageDifferencer::StreamReporter::ReportAdded(
void MessageDifferencer::StreamReporter::ReportDeleted(
const Message& message1,
const Message& message2,
- const vector<SpecificField>& field_path) {
+ const std::vector<SpecificField>& field_path) {
printer_->Print("deleted: ");
- PrintPath(field_path, true);
+ PrintPath(field_path, true, message1);
printer_->Print(": ");
PrintValue(message1, field_path, true);
printer_->Print("\n"); // Print for newlines
@@ -1606,7 +1681,7 @@ void MessageDifferencer::StreamReporter::ReportDeleted(
void MessageDifferencer::StreamReporter::ReportModified(
const Message& message1,
const Message& message2,
- const vector<SpecificField>& field_path) {
+ const std::vector<SpecificField>& field_path) {
if (!report_modified_aggregates_ && field_path.back().field == NULL) {
if (field_path.back().unknown_field_type == UnknownField::TYPE_GROUP) {
// Any changes to the subfields have already been printed.
@@ -1621,10 +1696,10 @@ void MessageDifferencer::StreamReporter::ReportModified(
}
printer_->Print("modified: ");
- PrintPath(field_path, true);
+ PrintPath(field_path, true, message1);
if (CheckPathChanged(field_path)) {
printer_->Print(" -> ");
- PrintPath(field_path, false);
+ PrintPath(field_path, false, message2);
}
printer_->Print(": ");
PrintValue(message1, field_path, true);
@@ -1636,11 +1711,11 @@ void MessageDifferencer::StreamReporter::ReportModified(
void MessageDifferencer::StreamReporter::ReportMoved(
const Message& message1,
const Message& message2,
- const vector<SpecificField>& field_path) {
+ const std::vector<SpecificField>& field_path) {
printer_->Print("moved: ");
- PrintPath(field_path, true);
+ PrintPath(field_path, true, message1);
printer_->Print(" -> ");
- PrintPath(field_path, false);
+ PrintPath(field_path, false, message2);
printer_->Print(" : ");
PrintValue(message1, field_path, true);
printer_->Print("\n"); // Print for newlines.
@@ -1649,12 +1724,12 @@ void MessageDifferencer::StreamReporter::ReportMoved(
void MessageDifferencer::StreamReporter::ReportMatched(
const Message& message1,
const Message& message2,
- const vector<SpecificField>& field_path) {
+ const std::vector<SpecificField>& field_path) {
printer_->Print("matched: ");
- PrintPath(field_path, true);
+ PrintPath(field_path, true, message1);
if (CheckPathChanged(field_path)) {
printer_->Print(" -> ");
- PrintPath(field_path, false);
+ PrintPath(field_path, false, message2);
}
printer_->Print(" : ");
PrintValue(message1, field_path, true);
@@ -1664,28 +1739,35 @@ void MessageDifferencer::StreamReporter::ReportMatched(
void MessageDifferencer::StreamReporter::ReportIgnored(
const Message& message1,
const Message& message2,
- const vector<SpecificField>& field_path) {
+ const std::vector<SpecificField>& field_path) {
printer_->Print("ignored: ");
- PrintPath(field_path, true);
+ PrintPath(field_path, true, message1);
if (CheckPathChanged(field_path)) {
printer_->Print(" -> ");
- PrintPath(field_path, false);
+ PrintPath(field_path, false, message2);
}
printer_->Print("\n"); // Print for newlines.
}
void MessageDifferencer::StreamReporter::ReportUnknownFieldIgnored(
const Message& message1, const Message& message2,
- const vector<SpecificField>& field_path) {
+ const std::vector<SpecificField>& field_path) {
printer_->Print("ignored: ");
- PrintPath(field_path, true);
+ PrintPath(field_path, true, message1);
if (CheckPathChanged(field_path)) {
printer_->Print(" -> ");
- PrintPath(field_path, false);
+ PrintPath(field_path, false, message2);
}
printer_->Print("\n"); // Print for newlines.
}
+MessageDifferencer::MapKeyComparator*
+MessageDifferencer::CreateMultipleFieldsMapKeyComparator(
+ const std::vector<std::vector<const FieldDescriptor*> >& key_field_paths) {
+ return new MultipleFieldsMapKeyComparator(this, key_field_paths);
+}
+
+
} // namespace util
} // namespace protobuf
} // namespace google
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-09 16:19:43 +0000