// Copyright 2022 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "components/autofill/core/browser/form_structure_rationalizer.h"

#include <stddef.h>

#include <algorithm>
#include <array>
#include <iterator>
#include <map>
#include <memory>
#include <string>
#include <utility>
#include <vector>

#include "base/check.h"
#include "base/check_op.h"
#include "base/compiler_specific.h"
#include "base/containers/fixed_flat_map.h"
#include "base/containers/map_util.h"
#include "base/containers/span.h"
#include "base/feature_list.h"
#include "build/buildflag.h"
#include "components/autofill/core/browser/autofill_field.h"
#include "components/autofill/core/browser/autofill_format_string.h"
#include "components/autofill/core/browser/autofill_type.h"
#include "components/autofill/core/browser/country_type.h"
#include "components/autofill/core/browser/data_model/data_model_utils.h"
#include "components/autofill/core/browser/field_type_utils.h"
#include "components/autofill/core/browser/field_types.h"
#include "components/autofill/core/browser/form_parsing/autofill_parsing_utils.h"
#include "components/autofill/core/browser/form_parsing/credit_card_field_parser.h"
#include "components/autofill/core/browser/form_parsing/regex_patterns.h"
#include "components/autofill/core/browser/form_structure_rationalization_engine.h"
#include "components/autofill/core/browser/logging/log_manager.h"
#include "components/autofill/core/browser/proto/server.pb.h"
#include "components/autofill/core/common/autofill_features.h"
#include "components/autofill/core/common/autofill_internals/log_message.h"
#include "components/autofill/core/common/autofill_internals/logging_scope.h"
#include "components/autofill/core/common/autofill_regexes.h"
#include "components/autofill/core/common/form_field_data.h"
#include "components/autofill/core/common/html_field_types.h"
#include "components/autofill/core/common/language_code.h"
#include "components/autofill/core/common/logging/log_buffer.h"
#include "components/autofill/core/common/logging/log_macros.h"
#include "url/origin.h"

namespace autofill {

namespace {

void RationalizePhoneNumbersForFilling(std::vector<AutofillField*>& fields) {
  // A whole phone number can be structured in the following ways:
  // - whole number
  // - country code, city and number
  // - country code, city code, number field
  // - country code, city code, number field, second number field
  // In this function more or less anything ending in a local number field
  // (see `phone_number_found` below) is accepted as a valid phone number. Any
  // phone number fields after that number are labeled as
  // set_only_fill_when_focused(true) so that they don't get filled.
  AutofillField* found_number_field = nullptr;
  AutofillField* found_number_field_second = nullptr;
  AutofillField* found_city_code_field = nullptr;
  AutofillField* found_country_code_field = nullptr;
  AutofillField* found_city_and_number_field = nullptr;
  AutofillField* found_whole_number_field = nullptr;
  // The "number" here refers to the local part of a phone number (i.e.,
  // the part after a country code and a city code). It can be found as a
  // dedicated field or as part of a bigger scope (e.g. a whole number
  // field contains a "number"). The naming is sad but a relict from the past.
  bool phone_number_found = false;
  // Whether the number field (i.e. the local part) is split into two pieces.
  // This can be observed in the US, where 650 234-5678 would be a phone
  // number whose local parts are 234 and 5678.
  bool phone_number_separate_fields = false;
  // Iterate through all given fields. Iteration stops when it first finds a
  // field that indicates the end of a phone number (this can be the local
  // part of a phone number or a whole number). The |found_*| pointers will be
  // set to that set of fields when iteration finishes.
  for (AutofillField* field : fields) {
    if (!field->is_visible()) {
      continue;
    }
    // This phone number rationalization marks all but the first phone number as
    // `set_only_fill_when_focused(true)`. Since it doesn't change the types, it
    // intentionally uses the rationalized `Type()` (over the `ComputedType()`).
    const FieldType current_field_type = field->Type().GetAddressType();
    switch (current_field_type) {
      case PHONE_HOME_NUMBER:
        found_number_field = field;
        phone_number_found = true;
        break;
      case PHONE_HOME_NUMBER_PREFIX:
        if (!found_number_field) {
          found_number_field = field;
          // phone_number_found is not set to true because the suffix needs to
          // be found first.
          phone_number_separate_fields = true;
        }
        break;
      case PHONE_HOME_NUMBER_SUFFIX:
        if (phone_number_separate_fields) {
          found_number_field_second = field;
          phone_number_found = true;
        }
        break;
      case PHONE_HOME_CITY_CODE_WITH_TRUNK_PREFIX:
      case PHONE_HOME_CITY_CODE:
        if (!found_city_code_field) {
          found_city_code_field = field;
        }
        break;
      case PHONE_HOME_COUNTRY_CODE:
        if (!found_country_code_field) {
          found_country_code_field = field;
        }
        break;
      case PHONE_HOME_CITY_AND_NUMBER:
      case PHONE_HOME_CITY_AND_NUMBER_WITHOUT_TRUNK_PREFIX:
        DCHECK(!phone_number_found && !found_city_and_number_field);
        found_city_and_number_field = field;
        phone_number_found = true;
        break;
      case PHONE_HOME_WHOLE_NUMBER:
        DCHECK(!phone_number_found && !found_whole_number_field);
        found_whole_number_field = field;
        phone_number_found = true;
        break;
      default:
        break;
    }
    // Break here if the local part of a phone number was found because we
    // assume an order over the fields, where the local part comes last.
    if (phone_number_found) {
      break;
    }
  }

  // The first number of found may be the whole number field, the
  // city and number field, or neither. But it cannot be both.
  DCHECK(!(found_whole_number_field && found_city_and_number_field));

  // Prefer to fill the first complete phone number found. The whole_number
  // and city_and_number fields are only set if they occur before the local
  // part of a phone number. If we see the local part of a complete phone
  // number, we assume that the complete phone number is represented as a
  // sequence of fields (country code, city code, local part). These scenarios
  // are mutually exclusive, so clean up any inconsistencies.
  if (found_whole_number_field) {
    found_number_field = nullptr;
    found_number_field_second = nullptr;
    found_city_code_field = nullptr;
    found_country_code_field = nullptr;
  } else if (found_city_and_number_field) {
    found_number_field = nullptr;
    found_number_field_second = nullptr;
    found_city_code_field = nullptr;
  }

  // A second update pass.
  // At this point, either |phone_number_found| is false and we should do a
  // best-effort filling for the field whose types we have seen a first time.
  // Or |phone_number_found| is true and the pointers to the fields that
  // compose the first phone number are set to not-NULL. Specifically we hope
  // to find the following:
  // 1. |found_whole_number_field| is not NULL, other pointers set to NULL, or
  // 2. |found_city_and_number_field| is not NULL, |found_country_code_field|
  // is
  //    probably not NULL, and other pointers set to NULL, or
  // 3. |found_city_code_field| and |found_number_field| are not NULL,
  //    |found_country_code_field| is probably not NULL, and other pointers
  //    are NULL.
  // 4. |found_city_code_field|, |found_number_field| and
  //    |found_number_field_second| are not NULL, |found_country_code_field|
  //    is probably not NULL, and other pointers are NULL.
  //
  // We currently don't guarantee these values. E.g. it is possible that
  // |found_city_code_field| is NULL but |found_number_field| is not NULL.

  // For all above cases, in the update pass, if one field is phone
  // number related but not one of the found fields from first pass, set their
  // |only_fill_when_focused| field to true.
  for (AutofillField* field : fields) {
    // It is important to reset `AutofillField::only_fill_when_focused_` before
    // updating it accordingly for consistent cache updates (see
    // AutofillManager::UpdateFormCache() for more details).
    field->set_only_fill_when_focused(false);
    // As above, using the rationalized `Type()` is intentional.
    const FieldType current_field_type = field->Type().GetAddressType();
    switch (current_field_type) {
      case PHONE_HOME_NUMBER:
      case PHONE_HOME_NUMBER_PREFIX:
      case PHONE_HOME_NUMBER_SUFFIX:
        if (field != found_number_field && field != found_number_field_second) {
          field->set_only_fill_when_focused(true);
        }
        break;
      case PHONE_HOME_CITY_CODE:
      case PHONE_HOME_CITY_CODE_WITH_TRUNK_PREFIX:
        if (field != found_city_code_field) {
          field->set_only_fill_when_focused(true);
        }
        break;
      case PHONE_HOME_COUNTRY_CODE:
        if (field != found_country_code_field) {
          field->set_only_fill_when_focused(true);
        }
        break;
      case PHONE_HOME_CITY_AND_NUMBER:
      case PHONE_HOME_CITY_AND_NUMBER_WITHOUT_TRUNK_PREFIX:
        if (field != found_city_and_number_field) {
          field->set_only_fill_when_focused(true);
        }
        break;
      case PHONE_HOME_WHOLE_NUMBER:
        if (field != found_whole_number_field) {
          field->set_only_fill_when_focused(true);
        }
        break;
      default:
        break;
    }
  }
}

}  // namespace

FormStructureRationalizer::FormStructureRationalizer(
    base::span<const std::unique_ptr<AutofillField>> fields)
    : fields_(fields) {}
FormStructureRationalizer::~FormStructureRationalizer() = default;

void FormStructureRationalizer::RationalizeAutocompleteAttributes(
    LogManager* log_manager) {
  for (const auto& field : fields_) {
    auto set_html_type = [&field](HtmlFieldType type) {
      field->SetHtmlType(type, field->html_mode());
    };
    // Some of the following rationalization operates only on text fields.
    bool is_text_field =
        field->IsTextInputElement() ||
        field->form_control_type() == FormControlType::kTextArea;
    switch (field->html_type()) {
      case HtmlFieldType::kAdditionalName:
        if (!is_text_field) {
          continue;
        }
        if (field->max_length() == 1) {
          set_html_type(HtmlFieldType::kAdditionalNameInitial);
        }
        break;
      // We look at kCreditCardExpDate2DigitYear and
      // kCreditCardExpDate4DigitYear as well (not just kCreditCardExp which
      // is generated by the autocomplete attribute parser) because the server
      // hints can have changed (they may not have been available during the
      // first rationalization). In that case we want to rationalize again.
      case HtmlFieldType::kCreditCardExp:
      case HtmlFieldType::kCreditCardExpDate2DigitYear:
      case HtmlFieldType::kCreditCardExpDate4DigitYear:
        if (!is_text_field) {
          continue;
        }
        if (base::FeatureList::IsEnabled(
                features::kAutofillEnableExpirationDateImprovements)) {
          FieldType server_hint = field->server_type();
          FieldType forced_field_type =
              field->PredictionSource() ==
                      AutofillPredictionSource::kServerOverride
                  ? field->server_type()
                  : NO_SERVER_DATA;
          CreditCardFieldParser::ExpirationDateFormat format =
              CreditCardFieldParser::DetermineExpirationDateFormat(
                  *field, /*fallback_type=*/CREDIT_CARD_EXP_DATE_4_DIGIT_YEAR,
                  /*server_hint=*/server_hint,
                  /*forced_field_type=*/forced_field_type);
          set_html_type(format.digits_in_expiration_year == 4
                            ? HtmlFieldType::kCreditCardExpDate4DigitYear
                            : HtmlFieldType::kCreditCardExpDate2DigitYear);
        } else {
          if (field->max_length() == 5) {
            set_html_type(HtmlFieldType::kCreditCardExpDate2DigitYear);
          } else if (field->max_length() == 7) {
            set_html_type(HtmlFieldType::kCreditCardExpDate4DigitYear);
          }
        }
        break;
      case HtmlFieldType::kCreditCardExpYear:
      case HtmlFieldType::kCreditCardExp2DigitYear:
      case HtmlFieldType::kCreditCardExp4DigitYear:
        if (!is_text_field & !field->IsSelectElement()) {
          continue;
        }
        if (base::FeatureList::IsEnabled(
                features::kAutofillEnableExpirationDateImprovements)) {
          FieldType server_hint = field->server_type();
          FieldType forced_field_type =
              field->PredictionSource() ==
                      AutofillPredictionSource::kServerOverride
                  ? field->server_type()
                  : NO_SERVER_DATA;
          // The default for select or list elements does not really matter
          // because it's practically always chosen from the select options.
          // The default for text elements was chosen base on statistics from
          // server side classifications (go/iqwtu).
          // Keep this in sync with
          // CreditCardFieldParser::GetExpirationYearType().
          FieldType overall_type =
              CreditCardFieldParser::DetermineExpirationYearType(
                  *field,
                  /*fallback_type=*/CREDIT_CARD_EXP_4_DIGIT_YEAR,
                  /*server_hint=*/server_hint,
                  /*forced_field_type=*/forced_field_type);
          set_html_type(overall_type == CREDIT_CARD_EXP_4_DIGIT_YEAR
                            ? HtmlFieldType::kCreditCardExp4DigitYear
                            : HtmlFieldType::kCreditCardExp2DigitYear);
        } else {
          if (field->max_length() == 2) {
            set_html_type(HtmlFieldType::kCreditCardExp2DigitYear);
          } else if (field->max_length() == 4) {
            set_html_type(HtmlFieldType::kCreditCardExp4DigitYear);
          }
        }
        break;
      default:
        break;
    }
  }
}

void FormStructureRationalizer::RationalizeContentEditables(
    LogManager* log_manager) {
  for (const auto& field : fields_) {
    if (field->form_control_type() == FormControlType::kContentEditable) {
      field->SetTypeTo(AutofillType(UNKNOWN_TYPE),
                       AutofillPredictionSource::kRationalization);
    }
  }
}

void FormStructureRationalizer::RationalizeCreditCardFieldPredictions(
    LogManager* log_manager) {
  bool cc_first_name_found = false;
  bool cc_last_name_found = false;
  bool cc_num_found = false;
  bool cc_month_found = false;
  bool cc_year_found = false;
  bool cc_type_found = false;
  bool cc_cvc_found = false;
  bool email_address_found = false;
  size_t num_months_found = 0;
  size_t num_other_fields_found = 0;
  for (const auto& field : fields_) {
    bool is_other_field = false;
    for (FieldType current_field_type : field->ComputedType().GetTypes()) {
      switch (current_field_type) {
        case CREDIT_CARD_NAME_FIRST:
          cc_first_name_found = true;
          break;
        case CREDIT_CARD_NAME_LAST:
          cc_last_name_found = true;
          break;
        case CREDIT_CARD_NAME_FULL:
          cc_first_name_found = true;
          cc_last_name_found = true;
          break;
        case CREDIT_CARD_NUMBER:
          cc_num_found = true;
          break;
        case CREDIT_CARD_EXP_MONTH:
          cc_month_found = true;
          ++num_months_found;
          break;
        case CREDIT_CARD_EXP_2_DIGIT_YEAR:
        case CREDIT_CARD_EXP_4_DIGIT_YEAR:
          cc_year_found = true;
          break;
        case CREDIT_CARD_EXP_DATE_2_DIGIT_YEAR:
        case CREDIT_CARD_EXP_DATE_4_DIGIT_YEAR:
          cc_month_found = true;
          cc_year_found = true;
          ++num_months_found;
          break;
        case CREDIT_CARD_TYPE:
          cc_type_found = true;
          break;
        case CREDIT_CARD_VERIFICATION_CODE:
          cc_cvc_found = true;
          break;
        case ADDRESS_HOME_ZIP:
          // Zip/Postal code often appears as part of a Credit Card form. Do
          // not count it as a non-cc-related field.
          break;
        case EMAIL_ADDRESS:
          email_address_found = true;
          [[fallthrough]];
        case CREDIT_CARD_STANDALONE_VERIFICATION_CODE:
          // We do not count standalone CVCs as credit card fields.
          // Whether that's a bug (crbug.com/434916381) or a feature is not
          // obvious.
          [[fallthrough]];
        default:
          is_other_field = true;
          break;
      }
    }
    if (is_other_field) {
      ++num_other_fields_found;
    }
  }

  // A partial CC name is unlikely. Prefer to consider these profile names
  // when partial.
  bool cc_name_found = cc_first_name_found && cc_last_name_found;

  // A partial CC expiry date should not be filled. These are often confused
  // with quantity/height fields and/or generic year fields.
  bool cc_date_found = cc_month_found && cc_year_found;

  // Count the credit card related fields in the form.
  size_t num_cc_fields_found =
      static_cast<int>(cc_name_found) + static_cast<int>(cc_num_found) +
      static_cast<int>(cc_date_found) + static_cast<int>(cc_type_found) +
      static_cast<int>(cc_cvc_found);

  // Retain credit card related fields if the form has multiple fields or has
  // no unrelated fields (useful for single cc-field forms). Credit card number
  // is permitted to be alone in an otherwise unrelated form because some
  // dynamic forms reveal the remainder of the fields only after the credit
  // card number is entered and identified as a credit card by the site.
  bool keep_cc_fields =
      cc_num_found || num_cc_fields_found >= 3 || num_other_fields_found == 0;

  if (!keep_cc_fields && num_cc_fields_found > 0) {
    LOG_AF(log_manager)
        << LoggingScope::kRationalization << LogMessage::kRationalization
        << "Credit card rationalization: Did not find credit card number, did "
           "not find >= 3 credit card fields ("
        << num_cc_fields_found << "), and had non-cc fields ("
        << num_other_fields_found << ").";
  }

  // Do an update pass over the fields to rewrite the types if credit card
  // fields are not to be retained. Some special handling is given to expiry
  // dates if the full date is not found or multiple expiry date fields are
  // found. See comments inline below.
  for (auto it = fields_.begin(); it != fields_.end(); ++it) {
    auto& field = *it;
    FieldType current_field_type = field->ComputedType().GetCreditCardType();
    switch (current_field_type) {
      case CREDIT_CARD_NAME_FIRST:
        if (!keep_cc_fields) {
          field->SetTypeTo(AutofillType(NAME_FIRST),
                           AutofillPredictionSource::kRationalization);
        }
        break;
      case CREDIT_CARD_NAME_LAST:
        if (!keep_cc_fields) {
          field->SetTypeTo(AutofillType(NAME_LAST),
                           AutofillPredictionSource::kRationalization);
        }
        break;
      case CREDIT_CARD_NAME_FULL:
        if (!keep_cc_fields) {
          field->SetTypeTo(AutofillType(NAME_FULL),
                           AutofillPredictionSource::kRationalization);
        }
        break;
      case CREDIT_CARD_NUMBER:
      case CREDIT_CARD_TYPE:
      case CREDIT_CARD_EXP_DATE_2_DIGIT_YEAR:
      case CREDIT_CARD_EXP_DATE_4_DIGIT_YEAR:
        if (!keep_cc_fields) {
          field->SetTypeTo(AutofillType(UNKNOWN_TYPE),
                           AutofillPredictionSource::kRationalization);
        }
        break;
      case CREDIT_CARD_EXP_MONTH:
        // Do not preserve an expiry month prediction if any of the following
        // are true:
        //   (1) the form is determined to be be non-cc related, so all cc
        //       field predictions are to be discarded
        //   (2) the expiry month was found without a corresponding year
        //   (3) multiple month fields were found in a form having a full
        //       expiry date. This usually means the form is a checkout form
        //       that also has one or more quantity fields. Suppress the expiry
        //       month field(s) not immediately preceding an expiry year field.
        if (!keep_cc_fields || !cc_date_found) {
          if (!cc_date_found) {
            LOG_AF(log_manager)
                << LoggingScope::kRationalization
                << LogMessage::kRationalization
                << "Credit card rationalization: Found CC expiration month but "
                   "not a full date.";
          }
          field->SetTypeTo(AutofillType(UNKNOWN_TYPE),
                           AutofillPredictionSource::kRationalization);
        } else if (num_months_found > 1) {
          auto it2 = it + 1;
          if (it2 == fields_.end()) {
            LOG_AF(log_manager)
                << LoggingScope::kRationalization
                << LogMessage::kRationalization
                << "Credit card rationalization: Found multiple expiration "
                   "months and the last field was an expiration month";
            field->SetTypeTo(AutofillType(UNKNOWN_TYPE),
                             AutofillPredictionSource::kRationalization);
          } else {
            FieldType next_field_type =
                (*it2)->ComputedType().GetCreditCardType();
            if (next_field_type != CREDIT_CARD_EXP_2_DIGIT_YEAR &&
                next_field_type != CREDIT_CARD_EXP_4_DIGIT_YEAR) {
              LOG_AF(log_manager)
                  << LoggingScope::kRationalization
                  << LogMessage::kRationalization
                  << "Credit card rationalization: Found multiple expiration "
                     "months and the field following one is not an "
                     "expiration year but "
                  << FieldTypeToStringView(next_field_type) << ".";
              field->SetTypeTo(AutofillType(UNKNOWN_TYPE),
                               AutofillPredictionSource::kRationalization);
            }
          }
        }
        break;
      case CREDIT_CARD_EXP_2_DIGIT_YEAR:
      case CREDIT_CARD_EXP_4_DIGIT_YEAR:
        if (!keep_cc_fields || !cc_date_found) {
          field->SetTypeTo(AutofillType(UNKNOWN_TYPE),
                           AutofillPredictionSource::kRationalization);
          if (!cc_date_found) {
            LOG_AF(log_manager)
                << LoggingScope::kRationalization
                << LogMessage::kRationalization
                << "Credit card rationalization: Found expiration year but no "
                   "full expiration date.";
          }
        }
        break;
      case CREDIT_CARD_VERIFICATION_CODE: {
        bool is_standalone_cvc_field = !cc_name_found && !cc_num_found &&
                                       !cc_date_found && !email_address_found;
        if (is_standalone_cvc_field) {
          // If there aren't any other credit card fields and no email address
          // field, than we presume this is a credit card saved on file of a
          // merchant webpage.
          field->SetTypeTo(
              AutofillType(CREDIT_CARD_STANDALONE_VERIFICATION_CODE),
              AutofillPredictionSource::kRationalization);
          LOG_AF(log_manager)
              << LoggingScope::kRationalization << LogMessage::kRationalization
              << "Credit card rationalization: Found CVC field but no other "
                 "credit card fields or email address field. Changed to "
                 "standalone CVC field.";
        } else if (!keep_cc_fields) {
          field->SetTypeTo(AutofillType(UNKNOWN_TYPE),
                           AutofillPredictionSource::kRationalization);
        }
        break;
      }
      default:
        break;
    }
  }

  // If after rationalization we have an expiration date field, we consider
  // once more whether we should make this a field with a 2 or 4 digit
  // expiration year based on server information.
  if (base::FeatureList::IsEnabled(
          features::kAutofillEnableExpirationDateImprovements)) {
    for (const auto& field : fields_) {
      // Here we look at the type after rationalization.
      FieldType current_field_type = field->Type().GetCreditCardType();
      if (current_field_type == CREDIT_CARD_EXP_DATE_2_DIGIT_YEAR ||
          current_field_type == CREDIT_CARD_EXP_DATE_4_DIGIT_YEAR) {
        FieldType server_hint = field->server_type();
        FieldType forced_field_type =
            field->PredictionSource() ==
                    AutofillPredictionSource::kServerOverride
                ? server_hint
                : NO_SERVER_DATA;
        CreditCardFieldParser::ExpirationDateFormat format =
            CreditCardFieldParser::DetermineExpirationDateFormat(
                *field, /*fallback_type=*/CREDIT_CARD_EXP_DATE_4_DIGIT_YEAR,
                /*server_hint=*/server_hint,
                /*forced_field_type=*/forced_field_type);
        FieldType new_field_type = format.digits_in_expiration_year == 4
                                       ? CREDIT_CARD_EXP_DATE_4_DIGIT_YEAR
                                       : CREDIT_CARD_EXP_DATE_2_DIGIT_YEAR;
        if (new_field_type != current_field_type) {
          LOG_AF(log_manager)
              << LoggingScope::kRationalization << LogMessage::kRationalization
              << "Credit card rationalization: Updated expiration date format "
                 "with server hints or via patterns found in the labels.";
          field->SetTypeTo(AutofillType(new_field_type),
                           AutofillPredictionSource::kRationalization);
        }
      }
    }
  }
}

void FormStructureRationalizer::RationalizeMultiOriginCreditCardFields(
    const url::Origin& main_origin,
    LogManager* log_manager) {
  auto is_in_subframe = [&main_origin](const FormFieldData& field) {
    return field.origin() != main_origin;
  };
  auto rationalize = [&](FieldType relevant_type) {
    auto is_relevant = [relevant_type](const AutofillField& field) {
      return field.ComputedType().GetCreditCardType() == relevant_type;
    };
    auto is_relevant_in_subframe = [&](const auto& field) {
      return is_relevant(*field) && is_in_subframe(*field);
    };
    // If a relevant field exists in a sub-frame, we can ignore the
    // corresponding field in the main frame as it is probably a
    // misclassification.
    if (std::ranges::any_of(fields_, is_relevant_in_subframe)) {
      for (auto& field : fields_) {
        if (is_relevant(*field) && !is_in_subframe(*field)) {
          field->SetTypeTo(AutofillType(UNKNOWN_TYPE),
                           AutofillPredictionSource::kRationalization);
          LOG_AF(log_manager)
              << LoggingScope::kRationalization << LogMessage::kRationalization
              << "Multi-origin Credit Card Rationalization: Converting type of "
              << field->global_id() << " from "
              << FieldTypeToStringView(relevant_type) << " to UNKNOWN_TYPE";
        }
      }
    }
  };
  // These fields do usually not occur on the main frame's origin due to
  // PCI-DSS. By contrast, cardholder name and expiration dates do commonly
  // appear in the main frame and in cross-origin iframes.
  rationalize(CREDIT_CARD_NUMBER);
  rationalize(CREDIT_CARD_VERIFICATION_CODE);
}

void FormStructureRationalizer::RationalizeCreditCardNumberOffsets(
    LogManager* log_manager) {
  // Credit card numbers are 8 to 19 digits in length.
  // [Ref: http://en.wikipedia.org/wiki/Bank_card_number]
  constexpr size_t kMinValidCardNumberSize = 8;
  constexpr size_t kMaxValidCardNumberSize = 19;
  constexpr size_t kMaxGroupElementLength = 8;
  using Group = base::span<const std::unique_ptr<AutofillField>>;

  // `may_be_group({f, f + 1}) && ... && may_be_group({f, f + N + 1})` is true
  // iff all fields in the range
  // 1. `{f, f + N + 1}` are credit card number fields, and
  // 2. `{f, f + N + 1}` originate from the same form in the same frame, and
  // 3. `{f, f + N + 1}` are all focusable or all unfocusable,
  // 4. `{f, f + N}` have the same `FormFieldData::max_length <
  //    kMaxGroupElementLength`.
  //
  // `may_be_group({f, f + N + 1})` is valid only if `may_be_group({f, f + N})`
  // is true. This is because each call only looks at the first and last
  // element.
  auto may_be_group = [](Group group) {
    DCHECK_GE(group.size(), 1u);
    DCHECK(
        std::ranges::all_of(group.first(group.size() - 1), [](const auto& f) {
          return f->ComputedType().GetCreditCardType() == CREDIT_CARD_NUMBER;
        }));
    return group.front()->max_length() <= kMaxGroupElementLength &&
           group.back()->ComputedType().GetCreditCardType() ==
               CREDIT_CARD_NUMBER &&
           group.front()->renderer_form_id() ==
               group.back()->renderer_form_id() &&
           group.front()->is_focusable() == group.back()->is_focusable() &&
           (group.size() == 1 || group.front()->max_length() ==
                                     group[group.size() - 2]->max_length());
  };

  // `has_reasonable_length({f, f + N + 1})` is true iff
  // 1. the cumulative FormFieldData::max_length
  //    (a) is long enough for the shortest credit cards, and
  //    (b) minus the overflow field (if present) isn't longer than the longest
  //        credit card, and
  // 2. there are at least 2 non-overflow fields.
  auto has_reasonable_length = [](Group group) {
    DCHECK(!group.empty());
    DCHECK(std::ranges::all_of(
        group.first(group.size() - 1), [group](const auto& f) {
          return f->max_length() == group.front()->max_length();
        }));
    bool last_is_overflow = group.back()->max_length() > kMaxGroupElementLength;
    size_t length = group.front()->max_length() * (group.size() - 1) +
                    group.back()->max_length();
    size_t length_without_overflow =
        length - last_is_overflow * group.back()->max_length();
    return length >= kMinValidCardNumberSize &&
           length_without_overflow <= kMaxValidCardNumberSize &&
           group.size() >= 2 + last_is_overflow;
  };

  // Returns the end (exclusive) of the credit card number field group starting
  // with `begin`.
  auto find_end_of_group = [&](auto begin) {
    auto end = begin;
    while (end != fields_.end() && may_be_group({begin, end + 1})) {
      ++end;
    }
    return end;
  };

  for (const auto& field : fields_) {
    // It is important to reset `AutofillField::credit_card_number_offset_`
    // before updating it accordingly for consistent cache updates (see
    // AutofillManager::UpdateFormCache() for more details).
    field->set_credit_card_number_offset(0);
  }
  for (auto begin = fields_.begin(); begin != fields_.end();) {
    auto end = find_end_of_group(begin);
    if (begin == end) {
      begin = end + 1;
      continue;
    }
    // SAFETY: The iterators are from the same container.
    Group fields = base::span(fields_).subspan(
        static_cast<size_t>(std::distance(fields_.begin(), begin)),
        static_cast<size_t>(std::distance(begin, end)));
    if (has_reasonable_length(fields)) {
      size_t offset = 0;
      for (auto& field : fields) {
        field->set_credit_card_number_offset(offset);
        offset += field->max_length();
      }
    }
    DCHECK(begin != end);
    begin = end;
  }
}

void FormStructureRationalizer::RationalizeDateFormatStrings(
    LogManager* log_manager) {
  if (!base::FeatureList::IsEnabled(features::kAutofillAiWithDataSchema)) {
    return;
  }

  auto set_format = [&](AutofillField& field, std::u16string format_string) {
    LOG_AF(log_manager) << LoggingScope::kRationalization
                        << LogMessage::kRationalization
                        << "Set format string of " << field.global_id()
                        << " to " << format_string;
    field.set_format_string_unless_overruled(
        AutofillFormatString(std::move(format_string),
                             FormatString_Type::FormatString_Type_DATE),
        AutofillFormatStringSource::kHeuristics);
  };

  auto get_autofill_ai_date_types = [](const AutofillField& field) {
    FieldTypeSet field_types = field.Type().GetAutofillAiTypes();
    for (const FieldType field_type : field_types) {
      if (!IsDateFieldType(field_type)) {
        field_types.erase(field_type);
      }
    }
    return field_types;
  };

  for (auto it = fields_.begin(); it != fields_.end(); ++it) {
    AutofillField& field = **it;
    const FieldTypeSet autofill_ai_date_types =
        get_autofill_ai_date_types(field);
    if (autofill_ai_date_types.empty()) {
      continue;
    }
    switch (field.format_string_source()) {
      case AutofillFormatStringSource::kUnset:
      case AutofillFormatStringSource::kHeuristics:
        break;  // Breaks the switch, not the loop.
      case AutofillFormatStringSource::kModelResult:
      case AutofillFormatStringSource::kServer:
        continue;
    }

    std::u16string format;
    if (data_util::IsValidDateFormat(field.placeholder())) {
      set_format(field, field.placeholder());
      continue;
    } else if (data_util::IsValidDateFormat(field.initial_value())) {
      set_format(field, field.initial_value());
      continue;
    }

    // A regex that covers all date formats (with false positives).
    // The first, second, third capture groups correspond to the different
    // components.
    static constexpr char16_t kRegex[] =
        u"\\b"
        u"(YYYY|YY|MM|M|DD|D)\\s?([/\\.-])?\\s?"
        u"(YYYY|YY|MM|M|DD|D)\\s?([/\\.-])?\\s?"
        u"(YYYY|YY|MM|M|DD|D)?\\b";

    // Contains the match groups of `kRegex`. For example:
    // - full() == u"YYYY-MM-DD"
    // - part(0) == u"YYYY"
    // - part(1) == u"MM"
    // - part(2) == u"DD"
    // - separator(0) == u"/"
    // - separator(1) == u"/"
    struct {
      const std::u16string& full() const { return groups[0]; }

      const std::u16string& part(size_t i) const {
        DCHECK_EQ(groups.size(), 6u);
        DCHECK_LT(i, 3u);
        return groups[i * 2 + 1];
      }

      const std::u16string& separator(size_t i) const {
        DCHECK_EQ(groups.size(), 6u);
        DCHECK_LT(i, 2u);
        return groups[(i + 1) * 2];
      }

      std::vector<std::u16string> groups;
    } match;

    if (MatchesRegex<kRegex>(field.label(), &match.groups) &&
        data_util::IsValidDateFormat(match.full())) {
      // Returns the n-th next field if it has the same FieldType.
      auto successor = [&](int n) -> AutofillField* {
        if (n >= std::distance(it, fields_.end())) {
          return nullptr;
        }
        AutofillField& successor = **std::next(it, n);
        if (get_autofill_ai_date_types(successor) != autofill_ai_date_types) {
          return nullptr;
        }
        if (successor.label() != field.label() && !successor.label().empty()) {
          return nullptr;
        }
        return &successor;
      };

      AutofillField* fields[] = {&field, successor(1), successor(2)};
      DCHECK(fields[1] || !fields[2]);

      // Split the parts of the date format over `fields`.
      if (!fields[1]) {
        set_format(*fields[0], match.full());
      } else if (fields[1] && !fields[2] && match.part(2).empty()) {
        set_format(*fields[0], match.part(0));
        set_format(*fields[1], match.part(1));
        it += 1;
      } else if (fields[1] && fields[2] && !match.part(2).empty()) {
        set_format(*fields[0], match.part(0));
        set_format(*fields[1], match.part(1));
        set_format(*fields[2], match.part(2));
        it += 2;
      } else {
        set_format(*fields[0], match.full());
      }
    }
  }
}

void FormStructureRationalizer::RationalizeStreetAddressAndAddressLine(
    LogManager* log_manager) {
  if (fields_.size() < 2) {
    return;
  }
  for (auto field = fields_.begin() + 1; field != fields_.end(); ++field) {
    if ((*field)->ComputedType().GetAddressType() != ADDRESS_HOME_LINE2) {
      continue;
    }
    // Rationalize a preceding street address belonging to the same section
    // unless it's a server override.
    AutofillField& previous_field = **(field - 1);
    if (previous_field.ComputedType().GetAddressType() !=
            ADDRESS_HOME_STREET_ADDRESS ||
        previous_field.section() != (*field)->section() ||
        previous_field.PredictionSource() ==
            AutofillPredictionSource::kServerOverride) {
      continue;
    }
    LOG_AF(log_manager)
        << LoggingScope::kRationalization << LogMessage::kRationalization
        << "Street Address Rationalization: Converting sequence of (street "
           "address, address line 2) to (address line 1, address line 2)";
    previous_field.SetTypeTo(AutofillType(ADDRESS_HOME_LINE1),
                             AutofillPredictionSource::kRationalization);
  }
}

void FormStructureRationalizer::RationalizeBetweenStreetFields(
    LogManager* log_manager) {
  if (fields_.size() < 2) {
    return;
  }
  for (auto field = fields_.begin(); field != fields_.end() - 1; ++field) {
    const bool first_is_between_streets =
        (*field)->ComputedType().GetAddressType() ==
        ADDRESS_HOME_BETWEEN_STREETS;
    if (!first_is_between_streets) {
      continue;
    }

    // Rationalize a preceding street address belonging to the same section
    // unless it's a server override.
    AutofillField& next_field = **(field + 1);
    const bool second_is_between_streets_1_or_2 =
        next_field.ComputedType().GetAddressType() ==
            ADDRESS_HOME_BETWEEN_STREETS_1 ||
        next_field.ComputedType().GetAddressType() ==
            ADDRESS_HOME_BETWEEN_STREETS_2;
    if (!second_is_between_streets_1_or_2) {
      continue;
    }
    LOG_AF(log_manager) << LoggingScope::kRationalization
                        << LogMessage::kRationalization
                        << "Address Home Between Streets Rationalization: "
                           "Converting sequence of (home_between_street,  "
                           "home_between_street_1) or (home_between_street, "
                           "home_between_street_2) to (home_between_street_1, "
                           "home_between_street_2)";
    (**field).SetTypeTo(AutofillType(ADDRESS_HOME_BETWEEN_STREETS_1),
                        AutofillPredictionSource::kRationalization);
    next_field.SetTypeTo(AutofillType(ADDRESS_HOME_BETWEEN_STREETS_2),
                         AutofillPredictionSource::kRationalization);
    break;
  }
}

void FormStructureRationalizer::RationalizePhoneNumberTrunkTypes(
    LogManager* log_manager) {
  // These two maps contain the pair of `(old_type, new_type)` such that
  // `old_type` should be converted to `new_type` if a field is preceded by a
  // `PHONE_HOME_COUNTRY_CODE` field or not respectively.
  static constexpr auto kPhoneNumberConversionAfterCountryCodeField =
      base::MakeFixedFlatMap<FieldType, FieldType>(
          {{PHONE_HOME_WHOLE_NUMBER,
            PHONE_HOME_CITY_AND_NUMBER_WITHOUT_TRUNK_PREFIX},
           {PHONE_HOME_CITY_AND_NUMBER,
            PHONE_HOME_CITY_AND_NUMBER_WITHOUT_TRUNK_PREFIX},
           {PHONE_HOME_CITY_CODE_WITH_TRUNK_PREFIX, PHONE_HOME_CITY_CODE}});
  static constexpr auto kPhoneNumberConversionNotAfterCountryCodeField =
      base::MakeFixedFlatMap<FieldType, FieldType>(
          {{PHONE_HOME_CITY_AND_NUMBER_WITHOUT_TRUNK_PREFIX,
            PHONE_HOME_CITY_AND_NUMBER},
           {PHONE_HOME_CITY_CODE, PHONE_HOME_CITY_CODE_WITH_TRUNK_PREFIX}});

  // Indicates whether the previous field was a phone country code.
  bool preceding_phone_country_code = false;
  for (const std::unique_ptr<AutofillField>& field : fields_) {
    const FieldType type = field->ComputedType().GetAddressType();
    const FieldType* new_type =
        preceding_phone_country_code
            ? base::FindOrNull(kPhoneNumberConversionAfterCountryCodeField,
                               type)
            : base::FindOrNull(kPhoneNumberConversionNotAfterCountryCodeField,
                               type);
    if (new_type) {
      field->SetTypeTo(AutofillType(*new_type),
                       AutofillPredictionSource::kRationalization);
      LOG_AF(log_manager)
          << LoggingScope::kRationalization << LogMessage::kRationalization
          << "Converting " << FieldTypeToStringView(type) << " to "
          << FieldTypeToStringView(*new_type)
          << " as part of phone number trunk type rationalization";
    }
    preceding_phone_country_code = type == PHONE_HOME_COUNTRY_CODE;
  }
}

void FormStructureRationalizer::RationalizePhoneNumbersForFilling() {
  std::map<Section, std::vector<AutofillField*>> section_fields;
  for (const std::unique_ptr<AutofillField>& field : fields_) {
    section_fields[field->section()].push_back(field.get());
  }
  for (auto& [section, fields] : section_fields) {
    autofill::RationalizePhoneNumbersForFilling(fields);
  }
}

void FormStructureRationalizer::RationalizeRepeatedStreetAddressFields(
    LogManager* log_manager) {
  // Group ADDRESS_HOME_STREET_ADDRESS `fields_` by section.
  std::map<Section, std::vector<AutofillField*>> street_address_fields;
  for (const std::unique_ptr<AutofillField>& field : fields_) {
    if (field->is_focusable() &&
        field->ComputedType().GetAddressType() == ADDRESS_HOME_STREET_ADDRESS) {
      street_address_fields[field->section()].push_back(field.get());
    }
  }

  constexpr static std::array<FieldType, 3> kAddressLineTypes = {
      ADDRESS_HOME_LINE1, ADDRESS_HOME_LINE2, ADDRESS_HOME_LINE3};
  // Rationalise the street address fields in every section.
  for (auto& [section, fields] : street_address_fields) {
    if (fields.size() != 2 && fields.size() != 3) {
      continue;
    }
    auto next_type = kAddressLineTypes.begin();
    for (AutofillField* field : fields) {
      LOG_AF(log_manager)
          << LoggingScope::kRationalization << LogMessage::kRationalization
          << "RationalizeAddressLineFields ADDRESS_HOME_STREET_ADDRESS to "
          << FieldTypeToString(*next_type);
      field->SetTypeTo(AutofillType(*next_type),
                       AutofillPredictionSource::kRationalization);
      ++next_type;
    }
  }
}

void FormStructureRationalizer::RationalizeRepeatedZipCodeFields(
    LogManager* log_manager) {
  // The max split zip code part length is 5.
  // The prefix length is equal 5 in US, BR.
  // The suffix length can be equal 5 in IR, LT.
  // [Ref: https://en.wikipedia.org/wiki/List_of_postal_codes]
  constexpr size_t kMaxZipCodePartLength = 5;
  auto has_zip_type = [](const std::unique_ptr<AutofillField>& field) {
    FieldType type = field->ComputedType().GetAddressType();
    return field->is_visible() &&
           (type == ADDRESS_HOME_ZIP || type == ADDRESS_HOME_ZIP_PREFIX ||
            type == ADDRESS_HOME_ZIP_SUFFIX);
  };
  // Invariant: All fields in [begin, end[ are ADDRESS_HOME_ZIP,
  // ADDRESS_HOME_ZIP_PREFIX or ADDRESS_HOME_ZIP_SUFFIX.
  auto begin = fields_.begin();
  auto end = begin;
  while ((begin = std::find_if(end, fields_.end(), has_zip_type)) !=
         fields_.end()) {
    end = std::find_if_not(begin + 1, fields_.end(), has_zip_type);
    if (end - begin != 2) {
      continue;
    }
    AutofillField& first_zip = **begin;
    AutofillField& second_zip = **(begin + 1);
    const bool is_max_length_small =
        first_zip.max_length() <= kMaxZipCodePartLength &&
        second_zip.max_length() <= kMaxZipCodePartLength;
    const bool is_first_prefix =
        first_zip.Type().GetAddressType() == ADDRESS_HOME_ZIP_PREFIX;
    const bool is_second_suffix =
        second_zip.Type().GetAddressType() == ADDRESS_HOME_ZIP_SUFFIX;
    if (is_first_prefix && is_second_suffix) {
      continue;
    }
    if (is_first_prefix) {
      LOG_AF(log_manager)
          << LoggingScope::kRationalization << LogMessage::kRationalization
          << "Zip Code Rationalization: Converting sequence of (zip_prefix, "
             "zip) to (zip_prefix, zip_suffix)";
      second_zip.SetTypeTo(AutofillType(ADDRESS_HOME_ZIP_SUFFIX),
                           AutofillPredictionSource::kRationalization);
    } else if (is_second_suffix) {
      LOG_AF(log_manager)
          << LoggingScope::kRationalization << LogMessage::kRationalization
          << "Zip Code Rationalization: Converting sequence of (zip, "
             "zip_suffix) to (zip_prefix, zip_suffix)";
      first_zip.SetTypeTo(AutofillType(ADDRESS_HOME_ZIP_PREFIX),
                          AutofillPredictionSource::kRationalization);
    } else if (is_max_length_small) {
      LOG_AF(log_manager)
          << LoggingScope::kRationalization << LogMessage::kRationalization
          << "Zip Code Rationalization: Converting sequence of (zip, "
             "zip) to (zip_prefix, zip_suffix)";
      first_zip.SetTypeTo(AutofillType(ADDRESS_HOME_ZIP_PREFIX),
                          AutofillPredictionSource::kRationalization);
      second_zip.SetTypeTo(AutofillType(ADDRESS_HOME_ZIP_SUFFIX),
                           AutofillPredictionSource::kRationalization);
    } else if (second_zip.PredictionSource() ==
               AutofillPredictionSource::kHeuristics) {
      // Prevents filling the full zip code twice when repeated zip fields don't
      // qualify as a prefix/suffix pair. This only applies to heuristics, since
      // the confidence in other prediction sources is higher.
      LOG_AF(log_manager)
          << LoggingScope::kRationalization << LogMessage::kRationalization
          << "Zip Code Rationalization: Converting sequence of (zip, "
             "zip) to (zip, unknown)";
      second_zip.SetTypeTo(AutofillType(UNKNOWN_TYPE),
                           AutofillPredictionSource::kRationalization);
    }
  }
}

void FormStructureRationalizer::RationalizeZipCodeSuffixFields(
    LogManager* log_manager) {
  FieldType prev_type = UNKNOWN_TYPE;
  for (const std::unique_ptr<AutofillField>& field : fields_) {
    FieldType type = field->Type().GetAddressType();
    if (type == ADDRESS_HOME_ZIP_SUFFIX &&
        prev_type != ADDRESS_HOME_ZIP_PREFIX) {
      field->SetTypeTo(AutofillType(ADDRESS_HOME_ZIP),
                       AutofillPredictionSource::kRationalization);
      LOG_AF(log_manager)
          << "Zip Code Rationalization: Converting "
             "ADDRESS_HOME_ZIP_SUFFIX field to ADDRESS_HOME_ZIP"
             "since previous field is not ADDRESS_HOME_ZIP_PREFIX.";
    }
    prev_type = type;
  }
}

void FormStructureRationalizer::RationalizeFieldTypePredictions(
    const url::Origin& main_origin,
    const GeoIpCountryCode& client_country,
    const LanguageCode& language_code,
    LogManager* log_manager) {
  RationalizeCreditCardFieldPredictions(log_manager);
  RationalizeMultiOriginCreditCardFields(main_origin, log_manager);
  RationalizeCreditCardNumberOffsets(log_manager);
  RationalizeDateFormatStrings(log_manager);
  RationalizeRepeatedStreetAddressFields(log_manager);
  if (base::FeatureList::IsEnabled(features::kAutofillSupportSplitZipCode)) {
    RationalizeRepeatedZipCodeFields(log_manager);
    RationalizeZipCodeSuffixFields(log_manager);
  }
  RationalizeStreetAddressAndAddressLine(log_manager);
  RationalizeBetweenStreetFields(log_manager);
  RationalizePhoneNumberTrunkTypes(log_manager);
  RationalizePhoneCountryCode(log_manager);
  RationalizeByRationalizationEngine(client_country, language_code,
                                     log_manager);
}

void FormStructureRationalizer::RationalizePhoneCountryCode(
    LogManager* log_manager) {
  constexpr static FieldTypeSet kRelevantPhoneTypes{
      PHONE_HOME_NUMBER, PHONE_HOME_NUMBER_PREFIX, PHONE_HOME_CITY_AND_NUMBER,
      PHONE_HOME_CITY_AND_NUMBER_WITHOUT_TRUNK_PREFIX};
  if (std::ranges::any_of(fields_, [&](const auto& field) {
        FieldType computed_type = field->ComputedType().GetAddressType();
        FieldType rationalized_type =
            field->PredictionSource() ==
                    AutofillPredictionSource::kRationalization
                ? field->Type().GetAddressType()
                : computed_type;
        // Some rationalization rule changes `PHONE_HOME_WHOLE_NUMBER` (not in
        // `kRelevantPhoneTypes`) to
        // `PHONE_HOME_CITY_AND_NUMBER_WITHOUT_TRUNK_PREFIX` (in
        // `kRelevantPhoneTypes`). Which is why we need to look at both
        // `computed_type` and `rationalized_type`.
        return (kRelevantPhoneTypes.contains(computed_type) ||
                kRelevantPhoneTypes.contains(rationalized_type));
      })) {
    return;
  }
  for (const std::unique_ptr<AutofillField>& field : fields_) {
    if (field->ComputedType().GetAddressType() == PHONE_HOME_COUNTRY_CODE) {
      field->SetTypeTo(AutofillType(UNKNOWN_TYPE),
                       AutofillPredictionSource::kRationalization);
      LOG_AF(log_manager)
          << "RationalizeTypeRelationships: Fields of type "
             "PHONE_HOME_COUNTRY_CODE can only coexist with other"
             "phone number types.";
    }
  }
}

void FormStructureRationalizer::RationalizeByRationalizationEngine(
    const GeoIpCountryCode& client_country,
    const LanguageCode& language_code,
    LogManager* log_manager) {
  ParsingContext context(fields_, client_country, language_code,
#if BUILDFLAG(USE_INTERNAL_AUTOFILL_PATTERNS)
                         PatternFile::kDefault,
#else
                         PatternFile::kLegacy,
#endif
                         GetActiveRegexFeatures(), /*log_manager=*/nullptr);

  rationalization::ApplyRationalizationEngineRules(context, fields_,
                                                   log_manager);
}

}  // namespace autofill