bool MessageDifferencer::MatchRepeatedFieldIndices()

in cdk/extra/protobuf/protobuf-3.19.6/src/google/protobuf/util/message_differencer.cc [1765:1899]
107 lines of code
35 McCabe index (conditional complexity)

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) {
  const int count1 =
      message1.GetReflection()->FieldSize(message1, repeated_field);
  const int count2 =
      message2.GetReflection()->FieldSize(message2, repeated_field);
  const bool is_treated_as_smart_set = IsTreatedAsSmartSet(repeated_field);

  match_list1->assign(count1, -1);
  match_list2->assign(count2, -1);
  // Ensure that we don't report differences during the matching process. Since
  // field comparators could potentially use this message differencer object to
  // perform further comparisons, turn off reporting here and re-enable it
  // before returning.
  Reporter* reporter = reporter_;
  reporter_ = NULL;
  NumDiffsReporter num_diffs_reporter;
  std::vector<int32_t> num_diffs_list1;
  if (is_treated_as_smart_set) {
    num_diffs_list1.assign(count1, std::numeric_limits<int32_t>::max());
  }

  bool success = true;
  // Find potential match if this is a special 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 augmenting path algorithm.
    auto callback = [&](int i1, int i2) {
      return IsMatch(repeated_field, key_comparator, &message1, &message2,
                     parent_fields, nullptr, i1, i2);
    };
    MaximumMatcher matcher(count1, count2, std::move(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 == nullptr);
    int match_count = matcher.FindMaximumMatch(early_return);
    if (match_count != count1 && early_return) 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) || is_treated_as_smart_set ||
        IsTreatedAsSmartList(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, nullptr, 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;
      int matched_j = -1;

      for (int j = start_offset; j < count2; j++) {
        if (match_list2->at(j) != -1) {
          if (!is_treated_as_smart_set || num_diffs_list1[i] == 0 ||
              num_diffs_list1[match_list2->at(j)] == 0) {
            continue;
          }
        }

        if (is_treated_as_smart_set) {
          num_diffs_reporter.Reset();
          match = IsMatch(repeated_field, key_comparator, &message1, &message2,
                          parent_fields, &num_diffs_reporter, i, j);
        } else {
          match = IsMatch(repeated_field, key_comparator, &message1, &message2,
                          parent_fields, nullptr, i, j);
        }

        if (is_treated_as_smart_set) {
          if (match) {
            num_diffs_list1[i] = 0;
          } else if (repeated_field->cpp_type() ==
                     FieldDescriptor::CPPTYPE_MESSAGE) {
            // Replace with the one with fewer diffs.
            const int32_t num_diffs = num_diffs_reporter.GetNumDiffs();
            if (num_diffs < num_diffs_list1[i]) {
              // If j has been already matched to some element, ensure the
              // current num_diffs is smaller.
              if (match_list2->at(j) == -1 ||
                  num_diffs < num_diffs_list1[match_list2->at(j)]) {
                num_diffs_list1[i] = num_diffs;
                match = true;
              }
            }
          }
        }

        if (match) {
          matched_j = j;
          if (!is_treated_as_smart_set || num_diffs_list1[i] == 0) {
            break;
          }
        }
      }

      match = (matched_j != -1);
      if (match) {
        if (is_treated_as_smart_set && match_list2->at(matched_j) != -1) {
          // This is to revert the previously matched index in list2.
          match_list1->at(match_list2->at(matched_j)) = -1;
          match = false;
        }
        match_list1->at(i) = matched_j;
        match_list2->at(matched_j) = i;
      }
      if (!match && reporter == nullptr) return false;
      success = success && match;
    }
  }

  if (IsTreatedAsSmartList(repeated_field)) {
    match_indices_for_smart_list_callback_(match_list1, match_list2);
  }

  reporter_ = reporter;

  return success;
}