Use upstream libaddressinput in Chrome.

third_party/libaddressinput/chromium/suggestions.cc

Index: third_party/libaddressinput/chromium/suggestions.cc
diff --git a/third_party/libaddressinput/chromium/suggestions.cc b/third_party/libaddressinput/chromium/suggestions.cc
new file mode 100644
index 0000000000000000000000000000000000000000..7005e701d9bd06b590623c031f9d1fd77ff09db8
--- /dev/null
+++ b/third_party/libaddressinput/chromium/suggestions.cc
@@ -0,0 +1,435 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "third_party/libaddressinput/chromium/suggestions.h"
+
+// Use "base/memory/scoped_ptr.h" instead.
+#define I18N_ADDRESSINPUT_UTIL_SCOPED_PTR_H_
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+#include "base/memory/scoped_ptr.h"
+#include "third_party/icu/source/common/unicode/errorcode.h"
+#include "third_party/icu/source/common/unicode/locid.h"
+#include "third_party/icu/source/common/unicode/unistr.h"
+#include "third_party/icu/source/common/unicode/utypes.h"
+#include "third_party/icu/source/i18n/unicode/coll.h"
+#include "third_party/libaddressinput/src/cpp/include/libaddressinput/address_data.h"
+#include "third_party/libaddressinput/src/cpp/include/libaddressinput/preload_supplier.h"
+#include "third_party/libaddressinput/src/cpp/include/libaddressinput/region_data.h"
+
+namespace autofill {
+
+using ::i18n::addressinput::ADMIN_AREA;
+using ::i18n::addressinput::DEPENDENT_LOCALITY;
+using ::i18n::addressinput::RegionData;
+
+typedef std::set<const RegionData*> RegionContainer;
+
+namespace {
+
+// Collects regions based on whether they have a parent in the given list.
+class ParentedRegionCollector {
+ public:
+  // Retains a reference to both of the parameters. Does not make a copy of
+  // |parent_regions|. Does not take ownership of |regions_with_parents|. The
+  // |regions_with_parents| parameter should not be NULL.
+  ParentedRegionCollector(const RegionContainer& parent_regions,
+                          RegionContainer* regions_with_parents)
+      : parent_regions_(parent_regions),
+        regions_with_parents_(regions_with_parents) {
+    DCHECK(regions_with_parents_);
+  }
+
+  ~ParentedRegionCollector() {}
+
+  // Adds |region_to_test| to the |regions_with_parents_| collection, if the
+  // given region has a parent in |parent_regions_|. The |region_to_test|
+  // parameter should not be NULL.
+  void operator()(const RegionData* region_to_test) {
+    DCHECK(region_to_test);
+    if (parent_regions_.find(&region_to_test->parent()) !=
+            parent_regions_.end()) {
+      regions_with_parents_->insert(region_to_test);
+    }
+  }
+
+ private:
+  const RegionContainer parent_regions_;
+  RegionContainer* regions_with_parents_;
+};
+
+}  // namespace
+
+class Suggestions::CanonicalizerImpl {
+ public:
+  CanonicalizerImpl() {
+    UErrorCode error_code = U_ZERO_ERROR;
+    collator_.reset(
+        icu::Collator::createInstance(icu::Locale::getRoot(), error_code));
+    DCHECK(U_SUCCESS(error_code));
+    collator_->setStrength(icu::Collator::PRIMARY);
+  }
+
+  ~CanonicalizerImpl() {}
+
+  // Returns a canonical version of the string that can be used for comparing
+  // strings regardless of diacritics and capitalization.
+  //    CanonicalizeString("Texas") == CanonicalizeString("T\u00E9xas");
+  //    CanonicalizeString("Texas") == CanonicalizeString("teXas");
+  //    CanonicalizeString("Texas") != CanonicalizeString("California");
+  //
+  // The output is not human-readable.
+  //    CanonicalizeString("Texas") != "Texas";
+  std::string CanonicalizeString(const std::string& original) {
+    icu::UnicodeString icu_str(
+        original.c_str(), static_cast<int32_t>(original.length()));
+    int32_t buffer_size = collator_->getSortKey(icu_str, NULL, 0);
+    scoped_ptr<uint8_t[]> buffer(new uint8_t[buffer_size]);
+    DCHECK(buffer.get());
+    int32_t filled_size =
+        collator_->getSortKey(icu_str, buffer.get(), buffer_size);
+    DCHECK_EQ(buffer_size, filled_size);
+    return std::string(reinterpret_cast<const char*>(buffer.get()));
+  }
+
+ private:
+  scoped_ptr<icu::Collator> collator_;
+
+  DISALLOW_COPY_AND_ASSIGN(CanonicalizerImpl);
+};
+
+Suggestions::Suggestions(const PreloadSupplier* supplier)
+    : supplier_(supplier),
+      canonicalizer_(new CanonicalizerImpl) {}
+
+Suggestions::~Suggestions() {
+  // Delete the maps and trie objects owned by |tries_| field.
+  for (RegionCodeMap::const_iterator region_it = tries_.begin();
+       region_it != tries_.end(); ++region_it) {
+    LanguageTagMap* lang_map = region_it->second;
+    DCHECK(lang_map);
+
+    for (LanguageTagMap::const_iterator lang_it = lang_map->begin();
+         lang_it != lang_map->end(); ++lang_it) {
+      AddressFieldMap* field_map = lang_it->second;
+      DCHECK(field_map);
+
+      for (AddressFieldMap::const_iterator field_it = field_map->begin();
+           field_it != field_map->end(); ++field_it) {
+        RegionIdMap* id_map = field_it->second;
+        DCHECK(id_map);
+
+        for (RegionIdMap::const_iterator id_it = id_map->begin();
+             id_it != id_map->end(); ++id_it) {
+          // The tries do not own the region objects.
+          Trie<const RegionData*>* trie = id_it->second;
+          delete trie;
+        }
+        delete id_map;
+      }
+      delete field_map;
+    }
+    delete lang_map;
+  }
+}
+
+void Suggestions::GetSuggestions(const AddressData& user_input,
+                                 AddressField focused_field,
+                                 size_t suggestions_limit,
+                                 std::vector<AddressData>* suggestions) {
+  /*
+  !!!TODO: IMPL!!!
+  DCHECK(suggestions);
+
+  std::map<std::string, Ruleset*>::const_iterator ruleset_it =
+      rules_.find(user_input.region_code);
+
+  if (ruleset_it == rules_.end()) {
+    return
+        loading_rules_.find(user_input.region_code) != loading_rules_.end()
+        ? RULES_NOT_READY
+        : RULES_UNAVAILABLE;
+  }
+
+  if (suggestions == NULL) {
+    return SUCCESS;
+  }
+  suggestions->clear();
+
+  assert(ruleset_it->second != NULL);
+
+  // Do not suggest anything if the user is typing in the field for which
+  // there's no validation data.
+  if (focused_field != POSTAL_CODE &&
+      (focused_field < ADMIN_AREA || focused_field > DEPENDENT_LOCALITY)) {
+    return SUCCESS;
+  }
+
+  // Do not suggest anything if the user input is empty.
+  if (user_input.GetFieldValue(focused_field).empty()) {
+    return SUCCESS;
+  }
+
+  const Ruleset& country_ruleset = *ruleset_it->second;
+  const Rule& country_rule =
+      country_ruleset.GetLanguageCodeRule(user_input.language_code);
+
+  // Do not suggest anything if the user is typing the postal code that is not
+  // valid for the country.
+  if (!user_input.postal_code.empty() &&
+      focused_field == POSTAL_CODE &&
+      !country_rule.GetPostalCodeFormat().empty() &&
+      !ValueMatchesPrefixRegex(
+          user_input.postal_code, country_rule.GetPostalCodeFormat())) {
+    return SUCCESS;
+  }
+
+  // Initialize the prefix search index lazily.
+  if (!ruleset_it->second->prefix_search_index_ready()) {
+    ruleset_it->second->BuildPrefixSearchIndex();
+  }
+
+  if (focused_field != POSTAL_CODE &&
+      focused_field > country_ruleset.deepest_ruleset_level()) {
+    return SUCCESS;
+  }
+
+  // Determine the most specific address field that can be suggested.
+  AddressField suggestion_field = focused_field != POSTAL_CODE
+      ? focused_field : DEPENDENT_LOCALITY;
+  if (suggestion_field > country_ruleset.deepest_ruleset_level()) {
+    suggestion_field = country_ruleset.deepest_ruleset_level();
+  }
+  if (focused_field != POSTAL_CODE) {
+    while (user_input.GetFieldValue(suggestion_field).empty() &&
+           suggestion_field > ADMIN_AREA) {
+      suggestion_field = static_cast<AddressField>(suggestion_field - 1);
+    }
+  }
+
+  // Find all rulesets that match user input.
+  AddressFieldRulesets rulesets;
+  for (int i = ADMIN_AREA; i <= suggestion_field; ++i) {
+    for (int j = Rule::KEY; j <= Rule::LATIN_NAME; ++j) {
+      AddressField address_field = static_cast<AddressField>(i);
+      Rule::IdentityField rule_field = static_cast<Rule::IdentityField>(j);
+
+      // Find all rulesets at |address_field| level whose |rule_field| starts
+      // with user input value.
+      country_ruleset.FindRulesetsByPrefix(
+          user_input.language_code, address_field, rule_field,
+          user_input.GetFieldValue(address_field),
+          &rulesets[address_field][rule_field]);
+
+      // Filter out the rulesets whose parents do not match the user input.
+      if (address_field > ADMIN_AREA) {
+        AddressField parent_field =
+            static_cast<AddressField>(address_field - 1);
+        Rulesets rulesets_with_parents;
+        std::for_each(
+            rulesets[address_field][rule_field].begin(),
+            rulesets[address_field][rule_field].end(),
+            ParentedRulesetCollector(rulesets[parent_field][rule_field],
+                                     &rulesets_with_parents));
+        rulesets[address_field][rule_field].swap(rulesets_with_parents);
+      }
+    }
+  }
+
+  // Determine the fields in the rules that match the user input. This
+  // operation converts a map of Rule::IdentityField value -> Ruleset into a
+  // map of Ruleset -> Rule::IdentityField bitset.
+  std::map<const Ruleset*, MatchingRuleFields> suggestion_rulesets;
+  for (IdentityFieldRulesets::const_iterator rule_field_it =
+           rulesets[suggestion_field].begin();
+       rule_field_it != rulesets[suggestion_field].end();
+       ++rule_field_it) {
+    const Rule::IdentityField rule_identity_field = rule_field_it->first;
+    for (Rulesets::const_iterator ruleset_it = rule_field_it->second.begin();
+         ruleset_it != rule_field_it->second.end();
+         ++ruleset_it) {
+      suggestion_rulesets[*ruleset_it].set(rule_identity_field);
+    }
+  }
+
+  // Generate suggestions based on the rulesets. Use a Rule::IdentityField
+  // from the bitset to generate address field values.
+  for (std::map<const Ruleset*, MatchingRuleFields>::const_iterator
+           suggestion_it = suggestion_rulesets.begin();
+       suggestion_it != suggestion_rulesets.end();
+       ++suggestion_it) {
+    const Ruleset& ruleset = *suggestion_it->first;
+    const Rule& rule = ruleset.GetLanguageCodeRule(user_input.language_code);
+    const MatchingRuleFields& matching_rule_fields = suggestion_it->second;
+
+    // Do not suggest this region if the postal code in user input does not
+    // match it.
+    if (!user_input.postal_code.empty() &&
+        !rule.GetPostalCodeFormat().empty() &&
+        !ValueMatchesPrefixRegex(
+            user_input.postal_code, rule.GetPostalCodeFormat())) {
+      continue;
+    }
+
+    // Do not add more suggestions than |suggestions_limit|.
+    if (suggestions->size() >= suggestions_limit) {
+      suggestions->clear();
+      return SUCCESS;
+    }
+
+    // If the user's language is not one of the supported languages of a
+    // country that has latinized names for its regions, then prefer to
+    // suggest the latinized region names. If the user types in local script
+    // instead, then the local script names will be suggested.
+    Rule::IdentityField rule_field = Rule::KEY;
+    if (!country_rule.GetLanguage().empty() &&
+        country_rule.GetLanguage() != user_input.language_code &&
+        !rule.GetLatinName().empty() &&
+        matching_rule_fields.test(Rule::LATIN_NAME)) {
+      rule_field = Rule::LATIN_NAME;
+    } else if (matching_rule_fields.test(Rule::KEY)) {
+      rule_field = Rule::KEY;
+    } else if (matching_rule_fields.test(Rule::NAME)) {
+      rule_field = Rule::NAME;
+    } else if (matching_rule_fields.test(Rule::LATIN_NAME)) {
+      rule_field = Rule::LATIN_NAME;
+    } else {
+      assert(false);
+    }
+
+    AddressData suggestion;
+    suggestion.region_code = user_input.region_code;
+    suggestion.postal_code = user_input.postal_code;
+
+    // Traverse the tree of rulesets from the most specific |ruleset| to the
+    // country-wide "root" of the tree. Use the region names found at each of
+    // the levels of the ruleset tree to build the |suggestion|.
+    for (const Ruleset* suggestion_ruleset = &ruleset;
+         suggestion_ruleset->parent() != NULL;
+         suggestion_ruleset = suggestion_ruleset->parent()) {
+      const Rule& suggestion_rule =
+          suggestion_ruleset->GetLanguageCodeRule(user_input.language_code);
+      suggestion.SetFieldValue(suggestion_ruleset->field(),
+                               suggestion_rule.GetIdentityField(rule_field));
+    }
+
+    suggestions->push_back(suggestion);
+  }
+
+  return SUCCESS;
+}
+
+void Ruleset::AddSubRegionRulesetsToTrie(const Ruleset& parent_ruleset) {
+  assert(field_ == COUNTRY);
+  assert(canonicalizer_ != NULL);
+
+  for (std::map<std::string, Ruleset*>::const_iterator sub_region_it =
+           parent_ruleset.sub_regions_.begin();
+       sub_region_it != parent_ruleset.sub_regions_.end();
+       ++sub_region_it) {
+    const Ruleset* ruleset = sub_region_it->second;
+    assert(ruleset != NULL);
+
+    if (deepest_ruleset_level_ < ruleset->field()) {
+      deepest_ruleset_level_ = ruleset->field();
+    }
+
+    for (LanguageCodeTries::const_iterator lang_it = tries_.begin();
+         lang_it != tries_.end(); ++lang_it) {
+      const std::string& language_code = lang_it->first;
+      const Rule& rule = ruleset->GetLanguageCodeRule(language_code);
+
+      AddressFieldTries* address_field_tries = lang_it->second;
+      assert(address_field_tries != NULL);
+
+      AddressFieldTries::const_iterator address_field_it =
+          address_field_tries->find(ruleset->field());
+      assert(address_field_it != address_field_tries->end());
+
+      IdentityFieldTries* identity_field_tries = address_field_it->second;
+      assert(identity_field_tries != NULL);
+
+      IdentityFieldTries::const_iterator identity_field_it =
+          identity_field_tries->find(Rule::KEY);
+      assert(identity_field_it != identity_field_tries->end());
+
+      Trie<const Ruleset*>* key_trie = identity_field_it->second;
+      assert(key_trie != NULL);
+
+      identity_field_it = identity_field_tries->find(Rule::NAME);
+      assert(identity_field_it != identity_field_tries->end());
+
+      Trie<const Ruleset*>* name_trie = identity_field_it->second;
+      assert(name_trie != NULL);
+
+      identity_field_it = identity_field_tries->find(Rule::LATIN_NAME);
+      assert(identity_field_it != identity_field_tries->end());
+
+      Trie<const Ruleset*>* latin_name_trie = identity_field_it->second;
+      assert(latin_name_trie != NULL);
+
+      if (!rule.GetKey().empty()) {
+        key_trie->AddDataForKey(
+            canonicalizer_->CanonicalizeString(rule.GetKey()), ruleset);
+      }
+
+      if (!rule.GetName().empty()) {
+        name_trie->AddDataForKey(
+             canonicalizer_->CanonicalizeString(rule.GetName()), ruleset);
+      }
+
+      if (!rule.GetLatinName().empty()) {
+        latin_name_trie->AddDataForKey(
+            canonicalizer_->CanonicalizeString(rule.GetLatinName()), ruleset);
+      }
+    }
+
+    AddSubRegionRulesetsToTrie(*ruleset);
+  }
+  */
+}
+
+void Suggestions::FindRegionsByPrefix(const std::string& region_code,
+                                      const std::string& language_tag,
+                                      AddressField address_field,
+                                      RegionIdentityField region_identity_field,
+                                      const std::string& canonicalized_prefix,
+                                      RegionContainer* result) const {
+  DCHECK_GE(address_field, ADMIN_AREA);
+  DCHECK_LE(address_field, DEPENDENT_LOCALITY);
+  DCHECK(result);
+
+  RegionCodeMap::const_iterator region_it = tries_.find(region_code);
+  if (region_it == tries_.end())
+    return;
+
+  const LanguageTagMap* lang_map = region_it->second;
+  DCHECK(lang_map);
+  LanguageTagMap::const_iterator lang_it = lang_map->find(language_tag);
+  if (lang_it == lang_map->end()) {
+    if (!lang_map->empty())
+      lang_it = lang_map->begin();
+    else
+      return;
+  }
+
+  const AddressFieldMap* field_map = lang_it->second;
+  DCHECK(field_map);
+  AddressFieldMap::const_iterator field_it = field_map->find(address_field);
+  if (field_it == field_map->end())
+    return;
+
+  const RegionIdMap* id_map = field_it->second;
+  DCHECK(id_map);
+  RegionIdMap::const_iterator id_it = id_map->find(region_identity_field);
+  if (id_it == id_map->end())
+    return;
+
+  const Trie<const RegionData*>* trie = id_it->second;
+  DCHECK(trie);
+  trie->FindDataForKeyPrefix(canonicalized_prefix, result);
+}
+
+}  // namespace autofill