message_differencer.cc | Explore in Territory

// Protocol Buffers - Google's data interchange format
// Copyright 2008 Google Inc.  All rights reserved.
// https://developers.google.com/protocol-buffers/
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// Author: [email protected] (Joseph Schorr)
//  Based on original Protocol Buffers design by
//  Sanjay Ghemawat, Jeff Dean, and others.

#include <google/protobuf/util/message_differencer.h>

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <memory>
#include <utility>

#include <google/protobuf/stubs/logging.h>
#include <google/protobuf/stubs/common.h>
#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/descriptor.h>
#include <google/protobuf/dynamic_message.h>
#include <google/protobuf/generated_enum_reflection.h>
#include <google/protobuf/map_field.h>
#include <google/protobuf/message.h>
#include <google/protobuf/text_format.h>
#include <google/protobuf/stubs/strutil.h>
#include <google/protobuf/stubs/stringprintf.h>
#include <google/protobuf/util/field_comparator.h>

// Always include as last one, otherwise it can break compilation
#include <google/protobuf/port_def.inc>

namespace google {
namespace protobuf {

namespace util {

namespace {

std::string PrintShortTextFormat(const google::protobuf::Message& message) { … }

}  // namespace

// A reporter to report the total number of diffs.
// TODO(ykzhu): we can improve this to take into account the value differencers.
class NumDiffsReporter : public google::protobuf::util::MessageDifferencer::Reporter { … };

// When comparing a repeated field as map, MultipleFieldMapKeyComparator can
// be used to specify multiple fields as key for key comparison.
// Two elements of a repeated field will be regarded as having the same key
// iff they have the same value for every specified key field.
// Note that you can also specify only one field as key.
class MessageDifferencer::MultipleFieldsMapKeyComparator
    : public MessageDifferencer::MapKeyComparator { … };

// Preserve the order when treating repeated field as SMART_LIST. The current
// implementation is to find the longest matching sequence from the first
// element. The optimal solution requires to use //util/diff/lcs.h, which is
// not open sourced yet. Overwrite this method if you want to have that.
// TODO(ykzhu): change to use LCS once it is open sourced.
void MatchIndicesPostProcessorForSmartList(std::vector<int>* match_list1,
                                           std::vector<int>* match_list2) { … }

void AddSpecificIndex(
    google::protobuf::util::MessageDifferencer::SpecificField* specific_field,
    const Message& message, const FieldDescriptor* field, int index) { … }

void AddSpecificNewIndex(
    google::protobuf::util::MessageDifferencer::SpecificField* specific_field,
    const Message& message, const FieldDescriptor* field, int index) { … }

MessageDifferencer::MapEntryKeyComparator::MapEntryKeyComparator(
    MessageDifferencer* message_differencer)
    : … { … }

bool MessageDifferencer::MapEntryKeyComparator::IsMatch(
    const Message& message1, const Message& message2,
    const std::vector<SpecificField>& parent_fields) const { … }

bool MessageDifferencer::Equals(const Message& message1,
                                const Message& message2) { … }

bool MessageDifferencer::Equivalent(const Message& message1,
                                    const Message& message2) { … }

bool MessageDifferencer::ApproximatelyEquals(const Message& message1,
                                             const Message& message2) { … }

bool MessageDifferencer::ApproximatelyEquivalent(const Message& message1,
                                                 const Message& message2) { … }

// ===========================================================================

MessageDifferencer::MessageDifferencer()
    : … { … }

MessageDifferencer::~MessageDifferencer() { … }

void MessageDifferencer::set_field_comparator(FieldComparator* comparator) { … }

#ifdef PROTOBUF_FUTURE_BREAKING_CHANGES
void MessageDifferencer::set_field_comparator(
    DefaultFieldComparator* comparator) {
  GOOGLE_CHECK(comparator) << "Field comparator can't be NULL.";
  field_comparator_kind_ = kFCDefault;
  field_comparator_.default_impl = comparator;
}
#endif  // PROTOBUF_FUTURE_BREAKING_CHANGES

void MessageDifferencer::set_message_field_comparison(
    MessageFieldComparison comparison) { … }

MessageDifferencer::MessageFieldComparison
MessageDifferencer::message_field_comparison() const { … }

void MessageDifferencer::set_scope(Scope scope) { … }

MessageDifferencer::Scope MessageDifferencer::scope() const { … }

void MessageDifferencer::set_float_comparison(FloatComparison comparison) { … }

void MessageDifferencer::set_repeated_field_comparison(
    RepeatedFieldComparison comparison) { … }

MessageDifferencer::RepeatedFieldComparison
MessageDifferencer::repeated_field_comparison() const { … }

void MessageDifferencer::CheckRepeatedFieldComparisons(
    const FieldDescriptor* field,
    const RepeatedFieldComparison& new_comparison) { … }

void MessageDifferencer::TreatAsSet(const FieldDescriptor* field) { … }

void MessageDifferencer::TreatAsSmartSet(const FieldDescriptor* field) { … }

void MessageDifferencer::SetMatchIndicesForSmartListCallback(
    std::function<void(std::vector<int>*, std::vector<int>*)> callback) { … }

void MessageDifferencer::TreatAsList(const FieldDescriptor* field) { … }

void MessageDifferencer::TreatAsSmartList(const FieldDescriptor* field) { … }

void MessageDifferencer::TreatAsMap(const FieldDescriptor* field,
                                    const FieldDescriptor* key) { … }

void MessageDifferencer::TreatAsMapWithMultipleFieldsAsKey(
    const FieldDescriptor* field,
    const std::vector<const FieldDescriptor*>& key_fields) { … }

void MessageDifferencer::TreatAsMapWithMultipleFieldPathsAsKey(
    const FieldDescriptor* field,
    const std::vector<std::vector<const FieldDescriptor*> >& key_field_paths) { … }

void MessageDifferencer::TreatAsMapUsingKeyComparator(
    const FieldDescriptor* field, const MapKeyComparator* key_comparator) { … }

void MessageDifferencer::AddIgnoreCriteria(IgnoreCriteria* ignore_criteria) { … }

void MessageDifferencer::IgnoreField(const FieldDescriptor* field) { … }

void MessageDifferencer::SetFractionAndMargin(const FieldDescriptor* field,
                                              double fraction, double margin) { … }

void MessageDifferencer::ReportDifferencesToString(std::string* output) { … }

void MessageDifferencer::ReportDifferencesTo(Reporter* reporter) { … }

bool MessageDifferencer::FieldBefore(const FieldDescriptor* field1,
                                     const FieldDescriptor* field2) { … }

bool MessageDifferencer::Compare(const Message& message1,
                                 const Message& message2) { … }

bool MessageDifferencer::CompareWithFields(
    const Message& message1, const Message& message2,
    const std::vector<const FieldDescriptor*>& message1_fields_arg,
    const std::vector<const FieldDescriptor*>& message2_fields_arg) { … }

bool MessageDifferencer::Compare(const Message& message1,
                                 const Message& message2,
                                 std::vector<SpecificField>* parent_fields) { … }

FieldDescriptorArray MessageDifferencer::RetrieveFields(const Message& message,
                                                        bool base_message) { … }

bool MessageDifferencer::CompareRequestedFieldsUsingSettings(
    const Message& message1, const Message& message2,
    const FieldDescriptorArray& message1_fields,
    const FieldDescriptorArray& message2_fields,
    std::vector<SpecificField>* parent_fields) { … }

FieldDescriptorArray MessageDifferencer::CombineFields(
    const FieldDescriptorArray& fields1, Scope fields1_scope,
    const FieldDescriptorArray& fields2, Scope fields2_scope) { … }

bool MessageDifferencer::CompareWithFieldsInternal(
    const Message& message1, const Message& message2,
    const FieldDescriptorArray& message1_fields,
    const FieldDescriptorArray& message2_fields,
    std::vector<SpecificField>* 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,
    Reporter* reporter, int index1, int index2) { … }

bool MessageDifferencer::CompareMapFieldByMapReflection(
    const Message& message1, const Message& message2,
    const FieldDescriptor* map_field, std::vector<SpecificField>* parent_fields,
    DefaultFieldComparator* comparator) { … }

bool MessageDifferencer::CompareMapField(
    const Message& message1, const Message& message2,
    const FieldDescriptor* repeated_field,
    std::vector<SpecificField>* parent_fields) { … }

bool MessageDifferencer::CompareRepeatedField(
    const Message& message1, const Message& message2,
    const FieldDescriptor* repeated_field,
    std::vector<SpecificField>* parent_fields) { … }

bool MessageDifferencer::CompareRepeatedRep(
    const Message& message1, const Message& message2,
    const FieldDescriptor* repeated_field,
    std::vector<SpecificField>* parent_fields) { … }

bool MessageDifferencer::CompareFieldValue(const Message& message1,
                                           const Message& message2,
                                           const FieldDescriptor* field,
                                           int index1, int index2) { … }

bool MessageDifferencer::CompareFieldValueUsingParentFields(
    const Message& message1, const Message& message2,
    const FieldDescriptor* field, int index1, int index2,
    std::vector<SpecificField>* parent_fields) { … }

bool MessageDifferencer::CheckPathChanged(
    const std::vector<SpecificField>& field_path) { … }

bool MessageDifferencer::IsTreatedAsSet(const FieldDescriptor* field) { … }

bool MessageDifferencer::IsTreatedAsSmartSet(const FieldDescriptor* field) { … }

bool MessageDifferencer::IsTreatedAsSmartList(const FieldDescriptor* field) { … }

bool MessageDifferencer::IsTreatedAsSubset(const FieldDescriptor* field) { … }

bool MessageDifferencer::IsIgnored(
    const Message& message1, const Message& message2,
    const FieldDescriptor* field,
    const std::vector<SpecificField>& parent_fields) { … }

bool MessageDifferencer::IsUnknownFieldIgnored(
    const Message& message1, const Message& message2,
    const SpecificField& field,
    const std::vector<SpecificField>& parent_fields) { … }

const MessageDifferencer::MapKeyComparator*
MessageDifferencer ::GetMapKeyComparator(const FieldDescriptor* field) const { … }

namespace {

IndexUnknownFieldPair;

struct UnknownFieldOrdering { … };

}  // namespace

bool MessageDifferencer::UnpackAnyField::UnpackAny(
    const Message& any, std::unique_ptr<Message>* data) { … }

bool MessageDifferencer::CompareUnknownFields(
    const Message& message1, const Message& message2,
    const UnknownFieldSet& unknown_field_set1,
    const UnknownFieldSet& unknown_field_set2,
    std::vector<SpecificField>* parent_field) { … }

namespace {

// Find maximum bipartite matching using the argumenting path algorithm.
class MaximumMatcher { … };

MaximumMatcher::MaximumMatcher(int count1, int count2,
                               NodeMatchCallback callback,
                               std::vector<int>* match_list1,
                               std::vector<int>* match_list2)
    : … { … }

int MaximumMatcher::FindMaximumMatch(bool early_return) { … }

bool MaximumMatcher::Match(int left, int right) { … }

bool MaximumMatcher::FindArgumentPathDFS(int v, std::vector<bool>* visited) { … }

}  // namespace

bool MessageDifferencer::MatchRepeatedFieldIndices(
    const Message& message1, const Message& message2,
    const FieldDescriptor* repeated_field,
    const MapKeyComparator* key_comparator,
    const std::vector<SpecificField>& parent_fields,
    std::vector<int>* match_list1, std::vector<int>* match_list2) { … }

FieldComparator::ComparisonResult MessageDifferencer::GetFieldComparisonResult(
    const Message& message1, const Message& message2,
    const FieldDescriptor* field, int index1, int index2,
    const FieldContext* field_context) { … }

// ===========================================================================

MessageDifferencer::Reporter::Reporter() { … }
MessageDifferencer::Reporter::~Reporter() { … }

// ===========================================================================

MessageDifferencer::MapKeyComparator::MapKeyComparator() { … }
MessageDifferencer::MapKeyComparator::~MapKeyComparator() { … }

// ===========================================================================

MessageDifferencer::IgnoreCriteria::IgnoreCriteria() { … }
MessageDifferencer::IgnoreCriteria::~IgnoreCriteria() { … }

// ===========================================================================

// Note that the printer's delimiter is not used, because if we are given a
// printer, we don't know its delimiter.
MessageDifferencer::StreamReporter::StreamReporter(
    io::ZeroCopyOutputStream* output)
    : … { … }

MessageDifferencer::StreamReporter::StreamReporter(io::Printer* printer)
    : … { … }

MessageDifferencer::StreamReporter::~StreamReporter() { … }

void MessageDifferencer::StreamReporter::PrintPath(
    const std::vector<SpecificField>& field_path, bool left_side) { … }


void MessageDifferencer::StreamReporter::PrintValue(
    const Message& message, const std::vector<SpecificField>& field_path,
    bool left_side) { … }

void MessageDifferencer::StreamReporter::PrintUnknownFieldValue(
    const UnknownField* unknown_field) { … }

void MessageDifferencer::StreamReporter::Print(const std::string& str) { … }

void MessageDifferencer::StreamReporter::PrintMapKey(
    bool left_side, const SpecificField& specific_field) { … }

void MessageDifferencer::StreamReporter::ReportAdded(
    const Message& /*message1*/, const Message& message2,
    const std::vector<SpecificField>& field_path) { … }

void MessageDifferencer::StreamReporter::ReportDeleted(
    const Message& message1, const Message& /*message2*/,
    const std::vector<SpecificField>& field_path) { … }

void MessageDifferencer::StreamReporter::ReportModified(
    const Message& message1, const Message& message2,
    const std::vector<SpecificField>& field_path) { … }

void MessageDifferencer::StreamReporter::ReportMoved(
    const Message& message1, const Message& /*message2*/,
    const std::vector<SpecificField>& field_path) { … }

void MessageDifferencer::StreamReporter::ReportMatched(
    const Message& message1, const Message& /*message2*/,
    const std::vector<SpecificField>& field_path) { … }

void MessageDifferencer::StreamReporter::ReportIgnored(
    const Message& /*message1*/, const Message& /*message2*/,
    const std::vector<SpecificField>& field_path) { … }

void MessageDifferencer::StreamReporter::SetMessages(const Message& message1,
                                                     const Message& message2) { … }

void MessageDifferencer::StreamReporter::ReportUnknownFieldIgnored(
    const Message& /*message1*/, const Message& /*message2*/,
    const std::vector<SpecificField>& field_path) { … }

MessageDifferencer::MapKeyComparator*
MessageDifferencer::CreateMultipleFieldsMapKeyComparator(
    const std::vector<std::vector<const FieldDescriptor*> >& key_field_paths) { … }

}  // namespace util
}  // namespace protobuf
}  // namespace google
chromium/third_party/protobuf/src/google/protobuf/util/message_differencer.cc
