src/google/protobuf/util/message_differencer.cc

// 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: jschorr@google.com (Joseph Schorr)
//  Based on original Protocol Buffers design by
//  Sanjay Ghemawat, Jeff Dean, and others.
//
// This file defines static methods and classes for comparing Protocol
// Messages (see //google/protobuf/util/message_differencer.h for more
// information).

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

#include <algorithm>
#include <memory>
#include <utility>

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

namespace google {
namespace protobuf {

namespace util {

// 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 {
 public:
  MultipleFieldsMapKeyComparator(
      MessageDifferencer* message_differencer,
      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());
    for (int i = 0; i < key_field_paths_.size(); ++i) {
      GOOGLE_CHECK(!key_field_paths_[i].empty());
    }
  }
  MultipleFieldsMapKeyComparator(
      MessageDifferencer* message_differencer,
      const FieldDescriptor* key)
        : message_differencer_(message_differencer) {
    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 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)) {
        return false;
      }
    }
    return true;
  }
 private:
  bool IsMatchInternal(
      const Message& message1,
      const Message& message2,
      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];
    std::vector<SpecificField> current_parent_fields(parent_fields);
    if (path_index == key_field_path.size() - 1) {
      if (field->is_repeated()) {
        if (!message_differencer_->CompareRepeatedField(
            message1, message2, field, &current_parent_fields)) {
          return false;
        }
      } else {
        if (!message_differencer_->CompareFieldValueUsingParentFields(
            message1, message2, field, -1, -1, &current_parent_fields)) {
          return false;
        }
      }
      return true;
    } else {
      const Reflection* reflection1 = message1.GetReflection();
      const Reflection* reflection2 = message2.GetReflection();
      bool has_field1 = reflection1->HasField(message1, field);
      bool has_field2 = reflection2->HasField(message2, field);
      if (!has_field1 && !has_field2) {
        return true;
      }
      if (has_field1 != has_field2) {
        return false;
      }
      SpecificField specific_field;
      specific_field.field = field;
      current_parent_fields.push_back(specific_field);
      return IsMatchInternal(
          reflection1->GetMessage(message1, field),
          reflection2->GetMessage(message2, field),
          current_parent_fields,
          key_field_path,
          path_index + 1);
    }
  }
  MessageDifferencer* message_differencer_;
  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;

  return differencer.Compare(message1, message2);
}

bool MessageDifferencer::Equivalent(const Message& message1,
                                    const Message& message2) {
  MessageDifferencer differencer;
  differencer.set_message_field_comparison(MessageDifferencer::EQUIVALENT);

  return differencer.Compare(message1, message2);
}

bool MessageDifferencer::ApproximatelyEquals(const Message& message1,
                                             const Message& message2) {
  MessageDifferencer differencer;
  differencer.set_float_comparison(
      MessageDifferencer::APPROXIMATE);

  return differencer.Compare(message1, message2);
}

bool MessageDifferencer::ApproximatelyEquivalent(const Message& message1,
                                                 const Message& message2) {
  MessageDifferencer differencer;
  differencer.set_message_field_comparison(MessageDifferencer::EQUIVALENT);
  differencer.set_float_comparison(MessageDifferencer::APPROXIMATE);

  return differencer.Compare(message1, message2);
}

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

MessageDifferencer::MessageDifferencer()
    : reporter_(NULL),
      field_comparator_(NULL),
      message_field_comparison_(EQUAL),
      scope_(FULL),
      repeated_field_comparison_(AS_LIST),
      map_entry_key_comparator_(this),
      report_matches_(false),
      report_moves_(true),
      output_string_(NULL) {}

MessageDifferencer::~MessageDifferencer() {
  for (int i = 0; i < owned_key_comparators_.size(); ++i) {
    delete owned_key_comparators_[i];
  }
  for (int i = 0; i < ignore_criteria_.size(); ++i) {
    delete ignore_criteria_[i];
  }
}

void MessageDifferencer::set_field_comparator(FieldComparator* comparator) {
  GOOGLE_CHECK(comparator) << "Field comparator can't be NULL.";
  field_comparator_ = comparator;
}

void MessageDifferencer::set_message_field_comparison(
    MessageFieldComparison comparison) {
  message_field_comparison_ = comparison;
}

void MessageDifferencer::set_scope(Scope scope) {
  scope_ = scope;
}

MessageDifferencer::Scope MessageDifferencer::scope() {
  return scope_;
}

void MessageDifferencer::set_float_comparison(FloatComparison comparison) {
  default_field_comparator_.set_float_comparison(
      comparison == EXACT ?
      DefaultFieldComparator::EXACT : DefaultFieldComparator::APPROXIMATE);
}

void MessageDifferencer::set_repeated_field_comparison(
    RepeatedFieldComparison comparison) {
  repeated_field_comparison_ = comparison;
}

void MessageDifferencer::TreatAsSet(const FieldDescriptor* field) {
  GOOGLE_CHECK(field->is_repeated()) << "Field must be repeated: "
                               << field->full_name();
  const MapKeyComparator* key_comparator = GetMapKeyComparator(field);
  GOOGLE_CHECK(key_comparator == NULL)
      << "Cannot treat this repeated field as both Map and Set for"
      << " comparison.  Field name is: " << field->full_name();
  GOOGLE_CHECK(list_fields_.find(field) == list_fields_.end())
      << "Cannot treat the same field as both SET and LIST. Field name is: "
      << field->full_name();
  set_fields_.insert(field);
}

void MessageDifferencer::TreatAsList(const FieldDescriptor* field) {
  GOOGLE_CHECK(field->is_repeated()) << "Field must be repeated: "
                              << field->full_name();
  const MapKeyComparator* key_comparator = GetMapKeyComparator(field);
  GOOGLE_CHECK(key_comparator == NULL)
      << "Cannot treat this repeated field as both Map and Set for"
      << " comparison.  Field name is: " << field->full_name();
  GOOGLE_CHECK(set_fields_.find(field) == set_fields_.end())
      << "Cannot treat the same field as both SET and LIST. Field name is: "
      << field->full_name();
  list_fields_.insert(field);
}

void MessageDifferencer::TreatAsMap(const FieldDescriptor* field,
                                    const FieldDescriptor* key) {
  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(key->containing_type() == field->message_type())
      << key->full_name()
      << " must be a direct subfield within the repeated field "
      << field->full_name() << ", not " << key->containing_type()->full_name();
  GOOGLE_CHECK(set_fields_.find(field) == set_fields_.end())
      << "Cannot treat this repeated field as both Map and Set for "
      << "comparison.";
  GOOGLE_CHECK(list_fields_.find(field) == list_fields_.end())
      << "Cannot treat this repeated field as both Map and List for "
      << "comparison.";
  MapKeyComparator* key_comparator =
      new MultipleFieldsMapKeyComparator(this, key);
  owned_key_comparators_.push_back(key_comparator);
  map_field_key_comparator_[field] = key_comparator;
}

void MessageDifferencer::TreatAsMapWithMultipleFieldsAsKey(
    const FieldDescriptor* field,
    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) {
    std::vector<const FieldDescriptor*> key_field_path;
    key_field_path.push_back(key_fields[i]);
    key_field_paths.push_back(key_field_path);
  }
  TreatAsMapWithMultipleFieldPathsAsKey(field, key_field_paths);
}

void MessageDifferencer::TreatAsMapWithMultipleFieldPathsAsKey(
    const FieldDescriptor* field,
    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 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];
      const FieldDescriptor* child_field = key_field_path[j];
      GOOGLE_CHECK(child_field->containing_type() == parent_field->message_type())
          << child_field->full_name()
          << " must be a direct subfield within the field: "
          << parent_field->full_name();
      if (j != 0) {
        GOOGLE_CHECK_EQ(FieldDescriptor::CPPTYPE_MESSAGE, parent_field->cpp_type())
            << parent_field->full_name() << " has to be of type message.";
        GOOGLE_CHECK(!parent_field->is_repeated())
            << parent_field->full_name() << " cannot be a repeated field.";
      }
    }
  }
  GOOGLE_CHECK(set_fields_.find(field) == set_fields_.end())
      << "Cannot treat this repeated field as both Map and Set for "
      << "comparison.";
  MapKeyComparator* key_comparator =
      new MultipleFieldsMapKeyComparator(this, key_field_paths);
  owned_key_comparators_.push_back(key_comparator);
  map_field_key_comparator_[field] = key_comparator;
}

void MessageDifferencer::TreatAsMapUsingKeyComparator(
    const FieldDescriptor* field,
    const MapKeyComparator* key_comparator) {
  GOOGLE_CHECK(field->is_repeated()) << "Field must be repeated: "
                               << field->full_name();
  GOOGLE_CHECK(set_fields_.find(field) == set_fields_.end())
      << "Cannot treat this repeated field as both Map and Set for "
      << "comparison.";
  map_field_key_comparator_[field] = key_comparator;
}

void MessageDifferencer::AddIgnoreCriteria(IgnoreCriteria* ignore_criteria) {
  ignore_criteria_.push_back(ignore_criteria);
}

void MessageDifferencer::IgnoreField(const FieldDescriptor* field) {
  ignored_fields_.insert(field);
}

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

void MessageDifferencer::ReportDifferencesToString(string* output) {
  GOOGLE_DCHECK(output) << "Specified output string was NULL";

  output_string_ = output;
  output_string_->clear();
}

void MessageDifferencer::ReportDifferencesTo(Reporter* reporter) {
  // If an output string is set, clear it to prevent
  // it superceding the specified reporter.
  if (output_string_) {
    output_string_ = NULL;
  }

  reporter_ = reporter;
}

bool MessageDifferencer::FieldBefore(const FieldDescriptor* field1,
                                     const FieldDescriptor* field2) {
  // Handle sentinel values (i.e. make sure NULLs are always ordered
  // at the end of the list).
  if (field1 == NULL) {
    return false;
  }

  if (field2 == NULL) {
    return true;
  }

  // Always order fields by their tag number
  return (field1->number() < field2->number());
}

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

  bool result = false;

  // Setup the internal reporter if need be.
  if (output_string_) {
    io::StringOutputStream output_stream(output_string_);
    StreamReporter reporter(&output_stream);
    reporter_ = &reporter;
    result = Compare(message1, message2, &parent_fields);
    reporter_ = NULL;
  } else {
    result = Compare(message1, message2, &parent_fields);
  }

  return result;
}

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) {
  if (message1.GetDescriptor() != message2.GetDescriptor()) {
    GOOGLE_LOG(DFATAL) << "Comparison between two messages with different "
                << "descriptors.";
    return false;
  }

  std::vector<SpecificField> parent_fields;

  bool result = false;

  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);
  // Append NULL sentinel values.
  message1_fields.push_back(NULL);
  message2_fields.push_back(NULL);

  // Setup the internal reporter if need be.
  if (output_string_) {
    io::StringOutputStream output_stream(output_string_);
    StreamReporter reporter(&output_stream);
    reporter_ = &reporter;
    result = CompareRequestedFieldsUsingSettings(
        message1, message2, message1_fields, message2_fields, &parent_fields);
    reporter_ = NULL;
  } else {
    result = CompareRequestedFieldsUsingSettings(
        message1, message2, message1_fields, message2_fields, &parent_fields);
  }

  return result;
}

bool MessageDifferencer::Compare(
    const Message& message1,
    const Message& message2,
    std::vector<SpecificField>* parent_fields) {
  const Descriptor* descriptor1 = message1.GetDescriptor();
  const Descriptor* descriptor2 = message2.GetDescriptor();
  if (descriptor1 != descriptor2) {
    GOOGLE_LOG(DFATAL) << "Comparison between two messages with different "
                << "descriptors. "
                << descriptor1->full_name() << " vs "
                << descriptor2->full_name();
    return false;
  }
  // Expand google.protobuf.Any payload if possible.
  if (descriptor1->full_name() == internal::kAnyFullTypeName) {
    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);
    }
  }
  const Reflection* reflection1 = message1.GetReflection();
  const Reflection* reflection2 = message2.GetReflection();

  // Retrieve all the set fields, including extensions.
  std::vector<const FieldDescriptor*> message1_fields;
  message1_fields.reserve(1 + message1.GetDescriptor()->field_count());

  std::vector<const FieldDescriptor*> message2_fields;
  message2_fields.reserve(1 + message2.GetDescriptor()->field_count());

  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
  // each list are different.
  message1_fields.push_back(NULL);
  message2_fields.push_back(NULL);

  bool unknown_compare_result = true;
  // Ignore unknown fields in EQUIVALENT mode
  if (message_field_comparison_ != EQUIVALENT) {
    const google::protobuf::UnknownFieldSet* unknown_field_set1 =
        &reflection1->GetUnknownFields(message1);
    const google::protobuf::UnknownFieldSet* unknown_field_set2 =
        &reflection2->GetUnknownFields(message2);
    if (!CompareUnknownFields(message1, message2,
                              *unknown_field_set1, *unknown_field_set2,
                              parent_fields)) {
      if (reporter_ == NULL) {
        return false;
      };
      unknown_compare_result = false;
    }
  }

  return CompareRequestedFieldsUsingSettings(
      message1, message2,
      message1_fields, message2_fields,
      parent_fields) && unknown_compare_result;
}

bool MessageDifferencer::CompareRequestedFieldsUsingSettings(
    const Message& message1,
    const Message& message2,
    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).
      std::vector<const FieldDescriptor*> fields_union;
      CombineFields(message1_fields, FULL, message2_fields, FULL,
                    &fields_union);
      return CompareWithFieldsInternal(message1, message2, fields_union,
                                       fields_union, parent_fields);
    } else {
      // Simple equality comparison, use the unaltered field lists.
      return CompareWithFieldsInternal(message1, message2, message1_fields,
                                       message2_fields, parent_fields);
    }
  } else {
    if (message_field_comparison_ == EQUIVALENT) {
      // We use the list of fields for message1 for both messages when
      // comparing.  This way, extra fields in message2 are ignored,
      // and missing fields in message2 use their default value.
      return CompareWithFieldsInternal(message1, message2, message1_fields,
                                       message1_fields, parent_fields);
    } else {
      // We need to consider the full list of fields for message1
      // 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.
      std::vector<const FieldDescriptor*> fields_intersection;
      CombineFields(message1_fields, PARTIAL, message2_fields, PARTIAL,
                    &fields_intersection);
      return CompareWithFieldsInternal(message1, message2, message1_fields,
                                       fields_intersection, parent_fields);
    }
  }
}

void MessageDifferencer::CombineFields(
    const std::vector<const FieldDescriptor*>& fields1,
    Scope fields1_scope,
    const std::vector<const FieldDescriptor*>& fields2,
    Scope fields2_scope,
    std::vector<const FieldDescriptor*>* combined_fields) {

  int index1 = 0;
  int index2 = 0;

  while (index1 < fields1.size() && index2 < fields2.size()) {
    const FieldDescriptor* field1 = fields1[index1];
    const FieldDescriptor* field2 = fields2[index2];

    if (FieldBefore(field1, field2)) {
      if (fields1_scope == FULL) {
        combined_fields->push_back(fields1[index1]);
      }
      ++index1;
    } else if (FieldBefore(field2, field1)) {
      if (fields2_scope == FULL) {
        combined_fields->push_back(fields2[index2]);
      }
      ++index2;
    } else {
      combined_fields->push_back(fields1[index1]);
      ++index1;
      ++index2;
    }
  }
}

bool MessageDifferencer::CompareWithFieldsInternal(
    const Message& message1,
    const Message& message2,
    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;

  const Reflection* reflection1 = message1.GetReflection();
  const Reflection* reflection2 = message2.GetReflection();

  while (true) {
    const FieldDescriptor* field1 = message1_fields[field_index1];
    const FieldDescriptor* field2 = message2_fields[field_index2];

    // Once we have reached sentinel values, we are done the comparison.
    if (field1 == NULL && field2 == NULL) {
      break;
    }

    // Check for differences in the field itself.
    if (FieldBefore(field1, field2)) {
      // Field 1 is not in the field list for message 2.
      if (IsIgnored(message1, message2, field1, *parent_fields)) {
        // We are ignoring field1. Report the ignore and move on to
        // the next field in message1_fields.
        if (reporter_ != NULL) {
          SpecificField specific_field;
          specific_field.field = field1;

          parent_fields->push_back(specific_field);
          reporter_->ReportIgnored(message1, message2, *parent_fields);
          parent_fields->pop_back();
        }
        ++field_index1;
        continue;
      }

      if (reporter_ != NULL) {
        assert(field1 != NULL);
        int count = field1->is_repeated() ?
            reflection1->FieldSize(message1, field1) : 1;

        for (int i = 0; i < count; ++i) {
          SpecificField specific_field;
          specific_field.field = field1;
          specific_field.index = field1->is_repeated() ? i : -1;

          parent_fields->push_back(specific_field);
          reporter_->ReportDeleted(message1, message2, *parent_fields);
          parent_fields->pop_back();
        }

        isDifferent = true;
      } else {
        return false;
      }

      ++field_index1;
      continue;
    } else if (FieldBefore(field2, field1)) {
      // Field 2 is not in the field list for message 1.
      if (IsIgnored(message1, message2, field2, *parent_fields)) {
        // We are ignoring field2. Report the ignore and move on to
        // the next field in message2_fields.
        if (reporter_ != NULL) {
          SpecificField specific_field;
          specific_field.field = field2;

          parent_fields->push_back(specific_field);
          reporter_->ReportIgnored(message1, message2, *parent_fields);
          parent_fields->pop_back();
        }
        ++field_index2;
        continue;
      }

      if (reporter_ != NULL) {
        int count = field2->is_repeated() ?
            reflection2->FieldSize(message2, field2) : 1;

        for (int i = 0; i < count; ++i) {
          SpecificField specific_field;
          specific_field.field = field2;
          specific_field.index = field2->is_repeated() ? i : -1;
          specific_field.new_index = specific_field.index;

          parent_fields->push_back(specific_field);
          reporter_->ReportAdded(message1, message2, *parent_fields);
          parent_fields->pop_back();
        }

        isDifferent = true;
      } else {
        return false;
      }

      ++field_index2;
      continue;
    }

    // By this point, field1 and field2 are guarenteed to point to the same
    // field, so we can now compare the values.
    if (IsIgnored(message1, message2, field1, *parent_fields)) {
      // Ignore this field. Report and move on.
      if (reporter_ != NULL) {
        SpecificField specific_field;
        specific_field.field = field1;

        parent_fields->push_back(specific_field);
        reporter_->ReportIgnored(message1, message2, *parent_fields);
        parent_fields->pop_back();
      }

      ++field_index1;
      ++field_index2;
      continue;
    }

    bool fieldDifferent = false;
    assert(field1 != NULL);
    if (field1->is_repeated()) {
      fieldDifferent = !CompareRepeatedField(message1, message2, field1,
                                             parent_fields);
      if (fieldDifferent) {
        if (reporter_ == NULL) return false;
        isDifferent = true;
      }
    } else {
      fieldDifferent = !CompareFieldValueUsingParentFields(
          message1, message2, field1, -1, -1, parent_fields);

      // If we have found differences, either report them or terminate if
      // no reporter is present.
      if (fieldDifferent && reporter_ == NULL) {
        return false;
      }

      if (reporter_ != NULL) {
        SpecificField specific_field;
        specific_field.field = field1;
        parent_fields->push_back(specific_field);
        if (fieldDifferent) {
          reporter_->ReportModified(message1, message2, *parent_fields);
          isDifferent = true;
        } else if (report_matches_) {
          reporter_->ReportMatched(message1, message2, *parent_fields);
        }
        parent_fields->pop_back();
      }
    }
    // Increment the field indicies.
    ++field_index1;
    ++field_index2;
  }

  return !isDifferent;
}

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,
        &current_parent_fields);
  }
  // Back up the Reporter and output_string_.  They will be reset in the
  // following code.
  Reporter* backup_reporter = reporter_;
  string* output_string = output_string_;
  reporter_ = NULL;
  output_string_ = NULL;
  bool match;

  if (key_comparator == NULL) {
    match = CompareFieldValueUsingParentFields(
        *message1, *message2, repeated_field, index1, index2,
        &current_parent_fields);
  } else {
    const Reflection* reflection1 = message1->GetReflection();
    const Reflection* reflection2 = message2->GetReflection();
    const Message& m1 =
        reflection1->GetRepeatedMessage(*message1, repeated_field, index1);
    const Message& m2 =
        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);
  }

  reporter_ = backup_reporter;
  output_string_ = output_string;
  return match;
}

bool MessageDifferencer::CompareRepeatedField(
    const Message& message1,
    const Message& message2,
    const FieldDescriptor* repeated_field,
    std::vector<SpecificField>* parent_fields) {
  // the input FieldDescriptor is guaranteed to be repeated field.
  const Reflection* reflection1 = message1.GetReflection();
  const Reflection* reflection2 = message2.GetReflection();
  const int count1 = reflection1->FieldSize(message1, repeated_field);
  const int count2 = reflection2->FieldSize(message2, repeated_field);
  const bool treated_as_subset = IsTreatedAsSubset(repeated_field);

  // If the field is not treated as subset and no detailed reports is needed,
  // we do a quick check on the number of the elements to avoid unnecessary
  // comparison.
  if (count1 != count2 && reporter_ == NULL && !treated_as_subset) {
    return false;
  }
  // A match can never be found if message1 has more items than message2.
  if (count1 > count2 && reporter_ == NULL) {
    return false;
  }

  // These two list are used for store the index of the correspondent
  // element in peer repeated field.
  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.
  if (!MatchRepeatedFieldIndices(message1, message2, repeated_field,
                                 *parent_fields, &match_list1, &match_list2) &&
      reporter_ == NULL) {
    return false;
  }

  bool fieldDifferent = false;
  SpecificField specific_field;
  specific_field.field = repeated_field;

  // At this point, we have already matched pairs of fields (with the reporting
  // to be done later). Now to check if the paired elements are different.
  for (int i = 0; i < count1; i++) {
    if (match_list1[i] == -1) continue;
    specific_field.index = i;
    specific_field.new_index = match_list1[i];

    const bool result = CompareFieldValueUsingParentFields(
        message1, message2, repeated_field, i, specific_field.new_index,
        parent_fields);

    // If we have found differences, either report them or terminate if
    // no reporter is present. Note that ReportModified, ReportMoved, and
    // ReportMatched are all mutually exclusive.
    if (!result) {
      if (reporter_ == NULL) return false;
      parent_fields->push_back(specific_field);
      reporter_->ReportModified(message1, message2, *parent_fields);
      parent_fields->pop_back();
      fieldDifferent = true;
    } else if (reporter_ != NULL &&
               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();
    } else if (report_matches_ && reporter_ != NULL) {
      parent_fields->push_back(specific_field);
      reporter_->ReportMatched(message1, message2, *parent_fields);
      parent_fields->pop_back();
    }
  }

  // Report any remaining additions or deletions.
  for (int i = 0; i < count2; ++i) {
    if (match_list2[i] != -1) continue;
    if (!treated_as_subset) {
      fieldDifferent = true;
    }

    if (reporter_ == NULL) continue;
    specific_field.index = i;
    specific_field.new_index = i;
    parent_fields->push_back(specific_field);
    reporter_->ReportAdded(message1, message2, *parent_fields);
    parent_fields->pop_back();
  }

  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);
    parent_fields->pop_back();
    fieldDifferent = true;
  }
  return !fieldDifferent;
}

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

bool MessageDifferencer::CompareFieldValueUsingParentFields(
    const Message& message1, const Message& message2,
    const FieldDescriptor* field, int index1, int index2,
    std::vector<SpecificField>* parent_fields) {
  FieldContext field_context(parent_fields);
  FieldComparator::ComparisonResult result = GetFieldComparisonResult(
      message1, message2, field, index1, index2, &field_context);

  if (field->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE &&
      result == FieldComparator::RECURSE) {
    // Get the nested messages and compare them using one of the Compare
    // methods.
    const Reflection* reflection1 = message1.GetReflection();
    const Reflection* reflection2 = message2.GetReflection();
    const Message& m1 = field->is_repeated() ?
        reflection1->GetRepeatedMessage(message1, field, index1) :
        reflection1->GetMessage(message1, field);
    const Message& m2 = field->is_repeated() ?
        reflection2->GetRepeatedMessage(message2, field, index2) :
        reflection2->GetMessage(message2, field);

    // parent_fields is used in calls to Reporter methods.
    if (parent_fields != NULL) {
      // Append currently compared field to the end of parent_fields.
      SpecificField specific_field;
      specific_field.field = field;
      specific_field.index = index1;
      specific_field.new_index = index2;
      parent_fields->push_back(specific_field);
      const bool compare_result = Compare(m1, m2, parent_fields);
      parent_fields->pop_back();
      return compare_result;
    } else {
      // Recreates parent_fields as if m1 and m2 had no parents.
      return Compare(m1, m2);
    }
  } else {
    return (result == FieldComparator::SAME);
  }
}

bool MessageDifferencer::CheckPathChanged(
    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;
}

bool MessageDifferencer::IsTreatedAsSet(const FieldDescriptor* field) {
  if (!field->is_repeated()) return false;
  if (repeated_field_comparison_ == AS_SET)
    return list_fields_.find(field) == list_fields_.end();
  return (set_fields_.find(field) != set_fields_.end());
}

bool MessageDifferencer::IsTreatedAsSubset(const FieldDescriptor* field) {
  return scope_ == PARTIAL &&
      (IsTreatedAsSet(field) || GetMapKeyComparator(field) != NULL);
}

bool MessageDifferencer::IsIgnored(
    const Message& message1,
    const Message& message2,
    const FieldDescriptor* field,
    const std::vector<SpecificField>& parent_fields) {
  if (ignored_fields_.find(field) != ignored_fields_.end()) {
    return true;
  }
  for (int i = 0; i < ignore_criteria_.size(); ++i) {
    if (ignore_criteria_[i]->IsIgnored(message1, message2, field,
                                       parent_fields)) {
      return true;
    }
  }
  return false;
}

bool MessageDifferencer::IsUnknownFieldIgnored(
    const Message& message1, const Message& message2,
    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)) {
      return true;
    }
  }
  return false;
}

const MessageDifferencer::MapKeyComparator*
MessageDifferencer ::GetMapKeyComparator(const FieldDescriptor* field) const {
  if (!field->is_repeated()) return NULL;
  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 std::pair<int, const UnknownField*> IndexUnknownFieldPair;

struct UnknownFieldOrdering {
  inline bool operator()(const IndexUnknownFieldPair& a,
                         const IndexUnknownFieldPair& b) const {
    if (a.second->number() < b.second->number()) return true;
    if (a.second->number() > b.second->number()) return false;
    return a.second->type() < b.second->type();
  }
};

}  // namespace

bool MessageDifferencer::UnpackAny(const Message& any,
                                   std::unique_ptr<Message>* data) {
  const Reflection* reflection = any.GetReflection();
  const FieldDescriptor* type_url_field;
  const FieldDescriptor* value_field;
  if (!internal::GetAnyFieldDescriptors(any, &type_url_field, &value_field)) {
    return false;
  }
  const string& type_url = reflection->GetString(any, type_url_field);
  string full_type_name;
  if (!internal::ParseAnyTypeUrl(type_url, &full_type_name)) {
    return false;
  }

  const google::protobuf::Descriptor* desc =
      any.GetDescriptor()->file()->pool()->FindMessageTypeByName(
          full_type_name);
  if (desc == NULL) {
    GOOGLE_DLOG(ERROR) << "Proto type '" << full_type_name << "' not found";
    return false;
  }

  if (dynamic_message_factory_ == NULL) {
    dynamic_message_factory_.reset(new DynamicMessageFactory());
  }
  data->reset(dynamic_message_factory_->GetPrototype(desc)->New());
  string serialized_value = reflection->GetString(any, value_field);
  if (!(*data)->ParseFromString(serialized_value)) {
    GOOGLE_DLOG(ERROR) << "Failed to parse value for " << full_type_name;
    return false;
  }
  return true;
}

bool MessageDifferencer::CompareUnknownFields(
    const Message& message1, const Message& message2,
    const google::protobuf::UnknownFieldSet& unknown_field_set1,
    const google::protobuf::UnknownFieldSet& unknown_field_set2,
    std::vector<SpecificField>* parent_field) {
  // Ignore unknown fields in EQUIVALENT mode.
  if (message_field_comparison_ == EQUIVALENT) return true;

  if (unknown_field_set1.empty() && unknown_field_set2.empty()) {
    return true;
  }

  bool is_different = false;

  // We first sort the unknown fields by field number and type (in other words,
  // in tag order), making sure to preserve ordering of values with the same
  // tag.  This allows us to report only meaningful differences between the
  // 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.
  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());

  for (int i = 0; i < unknown_field_set1.field_count(); i++) {
    fields1.push_back(std::make_pair(i, &unknown_field_set1.field(i)));
  }
  for (int i = 0; i < unknown_field_set2.field_count(); i++) {
    fields2.push_back(std::make_pair(i, &unknown_field_set2.field(i)));
  }

  UnknownFieldOrdering is_before;
  std::stable_sort(fields1.begin(), fields1.end(), is_before);
  std::stable_sort(fields2.begin(), fields2.end(), is_before);

  // In order to fill in SpecificField::index, we have to keep track of how
  // many values we've seen with the same field number and type.
  // current_repeated points at the first field in this range, and
  // current_repeated_start{1,2} are the indexes of the first field in the
  // range within fields1 and fields2.
  const UnknownField* current_repeated = NULL;
  int current_repeated_start1 = 0;
  int current_repeated_start2 = 0;

  // Now that we have two sorted lists, we can detect fields which appear only
  // in one list or the other by traversing them simultaneously.
  int index1 = 0;
  int index2 = 0;
  while (index1 < fields1.size() || index2 < fields2.size()) {
    enum { ADDITION, DELETION, MODIFICATION, COMPARE_GROUPS,
      NO_CHANGE } change_type;

    // focus_field is the field we're currently reporting on.  (In the case
    // of a modification, it's the field on the left side.)
    const UnknownField* focus_field;
    bool match = false;

    if (index2 == fields2.size() ||
        (index1 < fields1.size() &&
          is_before(fields1[index1], fields2[index2]))) {
      // fields1[index1] is not present in fields2.
      change_type = DELETION;
      focus_field = fields1[index1].second;
    } else if (index1 == fields1.size() ||
               is_before(fields2[index2], fields1[index1])) {
      // fields2[index2] is not present in fields1.
      if (scope_ == PARTIAL) {
        // Ignore.
        ++index2;
        continue;
      }
      change_type = ADDITION;
      focus_field = fields2[index2].second;
    } else {
      // Field type and number are the same.  See if the values differ.
      change_type = MODIFICATION;
      focus_field = fields1[index1].second;

      switch (focus_field->type()) {
        case UnknownField::TYPE_VARINT:
          match = fields1[index1].second->varint() ==
                  fields2[index2].second->varint();
          break;
        case UnknownField::TYPE_FIXED32:
          match = fields1[index1].second->fixed32() ==
                  fields2[index2].second->fixed32();
          break;
        case UnknownField::TYPE_FIXED64:
          match = fields1[index1].second->fixed64() ==
                  fields2[index2].second->fixed64();
          break;
        case UnknownField::TYPE_LENGTH_DELIMITED:
          match = fields1[index1].second->length_delimited() ==
                  fields2[index2].second->length_delimited();
          break;
        case UnknownField::TYPE_GROUP:
          // We must deal with this later, after building the SpecificField.
          change_type = COMPARE_GROUPS;
          break;
      }
      if (match && change_type != COMPARE_GROUPS) {
        change_type = NO_CHANGE;
      }
    }

    if (current_repeated == NULL ||
        focus_field->number() != current_repeated->number() ||
        focus_field->type() != current_repeated->type()) {
      // We've started a new repeated field.
      current_repeated = focus_field;
      current_repeated_start1 = index1;
      current_repeated_start2 = index2;
    }

    if (change_type == NO_CHANGE && reporter_ == NULL) {
      // Fields were already compared and matched and we have no reporter.
      ++index1;
      ++index2;
      continue;
    }

    // Build the SpecificField.  This is slightly complicated.
    SpecificField specific_field;
    specific_field.unknown_field_number = focus_field->number();
    specific_field.unknown_field_type = focus_field->type();

    specific_field.unknown_field_set1 = &unknown_field_set1;
    specific_field.unknown_field_set2 = &unknown_field_set2;

    if (change_type != ADDITION) {
      specific_field.unknown_field_index1 = fields1[index1].first;
    }
    if (change_type != DELETION) {
      specific_field.unknown_field_index2 = fields2[index2].first;
    }

    // Calculate the field index.
    if (change_type == ADDITION) {
      specific_field.index = index2 - current_repeated_start2;
      specific_field.new_index = index2 - current_repeated_start2;
    } else {
      specific_field.index = index1 - current_repeated_start1;
      specific_field.new_index = index2 - current_repeated_start2;
    }

    if (IsUnknownFieldIgnored(message1, message2, specific_field,
                              *parent_field)) {
      if (reporter_ != NULL) {
        parent_field->push_back(specific_field);
        reporter_->ReportUnknownFieldIgnored(message1, message2, *parent_field);
        parent_field->pop_back();
      }
      return true;
    }

    if (change_type == ADDITION || change_type == DELETION ||
        change_type == MODIFICATION) {
      if (reporter_ == NULL) {
        // We found a difference and we have no reproter.
        return false;
      }
      is_different = true;
    }

    parent_field->push_back(specific_field);

    switch (change_type) {
      case ADDITION:
        reporter_->ReportAdded(message1, message2, *parent_field);
        ++index2;
        break;
      case DELETION:
        reporter_->ReportDeleted(message1, message2, *parent_field);
        ++index1;
        break;
      case MODIFICATION:
        reporter_->ReportModified(message1, message2, *parent_field);
        ++index1;
        ++index2;
        break;
      case COMPARE_GROUPS:
        if (!CompareUnknownFields(message1, message2,
                                  fields1[index1].second->group(),
                                  fields2[index2].second->group(),
                                  parent_field)) {
          if (reporter_ == NULL) return false;
          is_different = true;
          reporter_->ReportModified(message1, message2, *parent_field);
        }
        ++index1;
        ++index2;
        break;
      case NO_CHANGE:
        ++index1;
        ++index2;
        if (report_matches_) {
          reporter_->ReportMatched(message1, message2, *parent_field);
        }
    }

    parent_field->pop_back();
  }

  return !is_different;
}

namespace {

// Find maximum bipartite matching using the argumenting path algorithm.
class MaximumMatcher {
 public:
  typedef ResultCallback2<bool, int, int> NodeMatchCallback;
  // MaximumMatcher takes ownership of the passed in callback and uses it to
  // determine whether a node on the left side of the bipartial graph matches
  // a node on the right side. count1 is the number of nodes on the left side
  // of the graph and count2 to is the number of nodes on the right side.
  // Every node is referred to using 0-based indices.
  // If a maximum match is found, the result will be stored in match_list1 and
  // match_list2. match_list1[i] == j means the i-th node on the left side is
  // matched to the j-th node on the right side and match_list2[x] == y means
  // 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,
                 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.
  int FindMaximumMatch(bool early_return);
 private:
  // Determines whether the node on the left side of the bipartial graph
  // matches the one on the right side.
  bool Match(int left, int right);
  // 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, std::vector<bool>* visited);

  int count1_;
  int count2_;
  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,
                               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);
  match_list2_->assign(count2, -1);
}

int MaximumMatcher::FindMaximumMatch(bool early_return) {
  int result = 0;
  for (int i = 0; i < count1_; ++i) {
    std::vector<bool> visited(count1_);
    if (FindArgumentPathDFS(i, &visited)) {
      ++result;
    } else if (early_return) {
      return 0;
    }
  }
  // Backfill match_list1_ as we only filled match_list2_ when finding
  // argumenting pathes.
  for (int i = 0; i < count2_; ++i) {
    if ((*match_list2_)[i] != -1) {
      (*match_list1_)[(*match_list2_)[i]] = i;
    }
  }
  return result;
}

bool MaximumMatcher::Match(int left, int right) {
  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;
  }
  cached_match_results_[p] = match_callback_->Run(left, right);
  return cached_match_results_[p];
}

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
  // where the greedy algorithm can find a maximum matching, we will always
  // find a match in this step and the performance will be identical to the
  // greedy algorithm.
  for (int i = 0; i < count2_; ++i) {
    int matched = (*match_list2_)[i];
    if (matched == -1 && Match(v, i)) {
      (*match_list2_)[i] = v;
      return true;
    }
  }
  // Then we try those already matched nodes and see if we can find an
  // alternaive match for the node matched to them.
  // The greedy algorithm will stop before this and fail to produce the
  // correct result.
  for (int i = 0; i < count2_; ++i) {
    int matched = (*match_list2_)[i];
    if (matched != -1 && Match(v, i)) {
      if (!(*visited)[matched] && FindArgumentPathDFS(matched, visited)) {
        (*match_list2_)[i] = v;
        return true;
      }
    }
  }
  return false;
}

}  // namespace

bool MessageDifferencer::MatchRepeatedFieldIndices(
    const Message& message1,
    const Message& message2,
    const FieldDescriptor* repeated_field,
    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 =
      message2.GetReflection()->FieldSize(message2, repeated_field);
  const MapKeyComparator* key_comparator = GetMapKeyComparator(repeated_field);

  match_list1->assign(count1, -1);
  match_list2->assign(count2, -1);

  bool success = true;
  // Find potential match if this is a special repeated field.
  if (key_comparator != NULL || IsTreatedAsSet(repeated_field)) {
    if (scope_ == PARTIAL) {
      // When partial matching is enabled, Compare(a, b) && Compare(a, c)
      // 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 =
          ::google::protobuf::NewPermanentCallback(
              this, &MessageDifferencer::IsMatch,
              repeated_field, key_comparator,
              &message1, &message2, parent_fields);
      MaximumMatcher matcher(count1, count2, callback, match_list1,
                             match_list2);
      // If diff info is not needed, we should end the matching process as
      // soon as possible if not all items can be matched.
      bool early_return = (reporter_ == NULL);
      int match_count = matcher.FindMaximumMatch(early_return);
      if (match_count != count1 && reporter_ == NULL) return false;
      success = success && (match_count == count1);
    } else {
      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;

        for (int j = start_offset; j < count2; j++) {
          if (match_list2->at(j) != -1) continue;

          match = IsMatch(repeated_field, key_comparator,
                          &message1, &message2, parent_fields, i, j);

          if (match) {
            match_list1->at(i) = j;
            match_list2->at(j) = i;
            break;
          }
        }
        if (!match && reporter_ == NULL) return false;
        success = success && match;
      }
    }
  } else {
    // If this field should be treated as list, just label the match_list.
    for (int i = 0; i < count1 && i < count2; i++) {
      match_list1->at(i) = i;
      match_list2->at(i) = i;
    }
  }

  return success;
}

FieldComparator::ComparisonResult MessageDifferencer::GetFieldComparisonResult(
    const Message& message1, const Message& message2,
    const FieldDescriptor* field, int index1, int index2,
    const FieldContext* field_context) {
  FieldComparator* comparator = field_comparator_ != NULL ?
      field_comparator_ : &default_field_comparator_;
  return comparator->Compare(message1, message2, field,
                             index1, index2, 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) : printer_(new io::Printer(output, '$')),
                                        delete_printer_(true),
                                        report_modified_aggregates_(false) { }

MessageDifferencer::StreamReporter::StreamReporter(
    io::Printer* printer) : printer_(printer),
                            delete_printer_(false),
                            report_modified_aggregates_(false) { }

MessageDifferencer::StreamReporter::~StreamReporter() {
  if (delete_printer_) delete printer_;
}

void MessageDifferencer::StreamReporter::PrintPath(
    const std::vector<SpecificField>& field_path, bool left_side) {
  for (int i = 0; i < field_path.size(); ++i) {
    if (i > 0) {
      printer_->Print(".");
    }

    SpecificField specific_field = field_path[i];

    if (specific_field.field != NULL) {
      if (specific_field.field->is_extension()) {
        printer_->Print("($name$)", "name",
                        specific_field.field->full_name());
      } 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));
    }
    if (left_side && specific_field.index >= 0) {
      printer_->Print("[$name$]", "name", SimpleItoa(specific_field.index));
    }
    if (!left_side && specific_field.new_index >= 0) {
      printer_->Print("[$name$]", "name", SimpleItoa(specific_field.new_index));
    }
  }
}

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 std::vector<SpecificField>& field_path,
                           bool left_side) {
  const SpecificField& specific_field = field_path.back();
  const FieldDescriptor* field = specific_field.field;
  if (field != NULL) {
    string output;
    int index = left_side ? specific_field.index : specific_field.new_index;
    if (field->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) {
      const Reflection* reflection = message.GetReflection();
      const Message& field_message = field->is_repeated() ?
          reflection->GetRepeatedMessage(message, field, index) :
          reflection->GetMessage(message, field);
      output = field_message.ShortDebugString();
      if (output.empty()) {
        printer_->Print("{ }");
      } else {
        printer_->Print("{ $name$ }", "name", output);
      }
    } else {
      TextFormat::PrintFieldValueToString(message, field, index, &output);
      printer_->PrintRaw(output);
    }
  } else {
    const UnknownFieldSet* unknown_fields =
        (left_side ?
         specific_field.unknown_field_set1 :
         specific_field.unknown_field_set2);
    const UnknownField* unknown_field = &unknown_fields->field(
        left_side ?
        specific_field.unknown_field_index1 :
        specific_field.unknown_field_index2);
    PrintUnknownFieldValue(unknown_field);
  }
}

void MessageDifferencer::
StreamReporter::PrintUnknownFieldValue(const UnknownField* unknown_field) {
  GOOGLE_CHECK(unknown_field != NULL) << " Cannot print NULL unknown_field.";

  string output;
  switch (unknown_field->type()) {
    case UnknownField::TYPE_VARINT:
      output = SimpleItoa(unknown_field->varint());
      break;
    case UnknownField::TYPE_FIXED32:
      output = StrCat("0x", strings::Hex(unknown_field->fixed32(),
                                         strings::ZERO_PAD_8));
      break;
    case UnknownField::TYPE_FIXED64:
      output = StrCat("0x", strings::Hex(unknown_field->fixed64(),
                                         strings::ZERO_PAD_16));
      break;
    case UnknownField::TYPE_LENGTH_DELIMITED:
      output = StringPrintf("\"%s\"",
          CEscape(unknown_field->length_delimited()).c_str());
      break;
    case UnknownField::TYPE_GROUP:
      // TODO(kenton):  Print the contents of the group like we do for
      //   messages.  Requires an equivalent of ShortDebugString() for
      //   UnknownFieldSet.
      output = "{ ... }";
      break;
  }
  printer_->PrintRaw(output);
}

void MessageDifferencer::StreamReporter::Print(const string& str) {
  printer_->Print(str.c_str());
}

void MessageDifferencer::StreamReporter::ReportAdded(
    const Message& message1,
    const Message& message2,
    const std::vector<SpecificField>& field_path) {
  printer_->Print("added: ");
  PrintPath(field_path, false, message2);
  printer_->Print(": ");
  PrintValue(message2, field_path, false);
  printer_->Print("\n");  // Print for newlines.
}

void MessageDifferencer::StreamReporter::ReportDeleted(
    const Message& message1,
    const Message& message2,
    const std::vector<SpecificField>& field_path) {
  printer_->Print("deleted: ");
  PrintPath(field_path, true, message1);
  printer_->Print(": ");
  PrintValue(message1, field_path, true);
  printer_->Print("\n");  // Print for newlines
}

void MessageDifferencer::StreamReporter::ReportModified(
    const Message& message1,
    const Message& message2,
    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.
      return;
    }
  } else if (!report_modified_aggregates_) {
    if (field_path.back().field->cpp_type() ==
        FieldDescriptor::CPPTYPE_MESSAGE) {
      // Any changes to the subfields have already been printed.
      return;
    }
  }

  printer_->Print("modified: ");
  PrintPath(field_path, true, message1);
  if (CheckPathChanged(field_path)) {
    printer_->Print(" -> ");
    PrintPath(field_path, false, message2);
  }
  printer_->Print(": ");
  PrintValue(message1, field_path, true);
  printer_->Print(" -> ");
  PrintValue(message2, field_path, false);
  printer_->Print("\n");  // Print for newlines.
}

void MessageDifferencer::StreamReporter::ReportMoved(
    const Message& message1,
    const Message& message2,
    const std::vector<SpecificField>& field_path) {
  printer_->Print("moved: ");
  PrintPath(field_path, true, message1);
  printer_->Print(" -> ");
  PrintPath(field_path, false, message2);
  printer_->Print(" : ");
  PrintValue(message1, field_path, true);
  printer_->Print("\n");  // Print for newlines.
}

void MessageDifferencer::StreamReporter::ReportMatched(
    const Message& message1,
    const Message& message2,
    const std::vector<SpecificField>& field_path) {
  printer_->Print("matched: ");
  PrintPath(field_path, true, message1);
  if (CheckPathChanged(field_path)) {
    printer_->Print(" -> ");
    PrintPath(field_path, false, message2);
  }
  printer_->Print(" : ");
  PrintValue(message1, field_path, true);
  printer_->Print("\n");  // Print for newlines.
}

void MessageDifferencer::StreamReporter::ReportIgnored(
    const Message& message1,
    const Message& message2,
    const std::vector<SpecificField>& field_path) {
  printer_->Print("ignored: ");
  PrintPath(field_path, true, message1);
  if (CheckPathChanged(field_path)) {
    printer_->Print(" -> ");
    PrintPath(field_path, false, message2);
  }
  printer_->Print("\n");  // Print for newlines.
}

void MessageDifferencer::StreamReporter::ReportUnknownFieldIgnored(
    const Message& message1, const Message& message2,
    const std::vector<SpecificField>& field_path) {
  printer_->Print("ignored: ");
  PrintPath(field_path, true, message1);
  if (CheckPathChanged(field_path)) {
    printer_->Print(" -> ");
    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