Use upstream libaddressinput in Chrome.

third_party/libaddressinput/chromium/input_suggester.cc

+// 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/input_suggester.h"
+
+#include <map>
+#include <set>
+#include <utility>
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/memory/scoped_vector.h"
+#include "base/stl_util.h"
+#include "third_party/icu/source/i18n/unicode/coll.h"
+#include "third_party/libaddressinput/chromium/trie.h"
+#include "third_party/libaddressinput/src/cpp/include/libaddressinput/address_data.h"
+#include "third_party/libaddressinput/src/cpp/include/libaddressinput/region_data.h"
+#include "third_party/libaddressinput/src/cpp/include/libaddressinput/region_data_builder.h"
+
+namespace autofill {
+
+using ::i18n::addressinput::AddressData;
+using ::i18n::addressinput::AddressField;
+using ::i18n::addressinput::PreloadSupplier;
+using ::i18n::addressinput::RegionData;
+using ::i18n::addressinput::RegionDataBuilder;
+
+using ::i18n::addressinput::ADMIN_AREA;
+using ::i18n::addressinput::COUNTRY;
+using ::i18n::addressinput::DEPENDENT_LOCALITY;
+using ::i18n::addressinput::LOCALITY;
+using ::i18n::addressinput::POSTAL_CODE;
+
+namespace {
+
+// Canonicalizes strings for fast case and diacritic insensitive comparison.
+class StringCanonicalizer {
+ public:
+  StringCanonicalizer() {
+    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);
+  }
+
+  ~StringCanonicalizer() {}
+
+  // Returns a canonical version of the string that can be used for comparing
+  // strings regardless of diacritics and capitalization.
+  //    Canonicalize("Texas") == Canonicalize("T\u00E9xas");
+  //    Canonicalize("Texas") == Canonicalize("teXas");
+  //    Canonicalize("Texas") != Canonicalize("California");
+  //
+  // The output is not human-readable.
+  //    Canonicalize("Texas") != "Texas";
+  std::string Canonicalize(const std::string& original) const {
+    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(StringCanonicalizer);
+};
+
+// A region and its metadata useful for constructing a suggestion.
+class Suggestion {
+ public:
+  // Does not take ownership of |region_to_suggest|, which cannot be NULL. At
+  // least one of |region_key_matches| and |region_name_names| must be true.
+  Suggestion(const RegionData* region_to_suggest,
+             AddressField matching_address_field,
+             bool region_key_matches,
+             bool region_name_matches)
+      : region_to_suggest_(region_to_suggest),
+        matching_address_field_(matching_address_field),
+        region_key_matches_(region_key_matches),
+        region_name_matches_(region_name_matches) {
+    DCHECK(region_to_suggest);
+    DCHECK(region_key_matches || region_name_matches);
+  }
+
+  ~Suggestion() {}
+
+  const RegionData& region_to_suggest() const { return *region_to_suggest_; }
+
+  AddressField matching_address_field() const {
+    return matching_address_field_;
+  }
+
+  bool region_key_matches() const { return region_key_matches_; }
+
+  bool region_name_matches() const { return region_name_matches_; }
+
+ private:
+  const RegionData* const region_to_suggest_;
+  const AddressField matching_address_field_;
+  bool region_key_matches_;
+  bool region_name_matches_;
+
+  DISALLOW_COPY_AND_ASSIGN(Suggestion);
+};
+
+// Suggestions for a country.
+class CountrySuggestions {
+ public:
+  CountrySuggestions()
+      : all_administrative_areas_match_(false), all_localities_match_(false) {}
+
+  ~CountrySuggestions() {}
+
+  // Should be called when user input for |field| is empty. The |field|
+  // parameter should be either ADMIN_AREA, LOCALITY, DEPENDENT_LOCALITY. Don't
+  // call this method with LOCALITY if you did not call this method with
+  // ADMIN_AREA: if only a subset of ADMIN_AREA regions match, then all LOLALITY
+  // regions cannot possibly match.
+  void AllRegionsMatchForField(AddressField field) {
+    switch (field) {
+      case ADMIN_AREA:
+        all_administrative_areas_match_ = true;
+        return;
+      case LOCALITY:
+        DCHECK(all_administrative_areas_match_);
+        all_localities_match_ = true;
+        return;
+      case DEPENDENT_LOCALITY:
+        // No-op.
+        return;
+      default:
+        break;
+    }
+    NOTREACHED();
+  }
+
+  // The |address_field| parameter should be ADMIN_AREA, LOCALITY, or
+  // DEPENDENT_LOCALITY. If |address_field| is LOCALITY or DEPENDENT_LOCALITY,
+  // then the method assumes that either this method or
+  // AllRegionsMatchForField() were previously invoked with |address_field-1|.
+  //
+  // Returns true if added suggestions for the regions.
+  bool AddRegions(AddressField address_field,
+                  const std::set<const RegionData*>& regions_match_key,
+                  const std::set<const RegionData*>& regions_match_name) {
+    AddressField parent_address_field =
+        static_cast<AddressField>(address_field - 1);
+
+    // Cannot build locality suggestions if none of the administrative areas
+    // match.
+    if (address_field == LOCALITY && !all_administrative_areas_match_ &&
+        administrative_area_key_regions_.empty() &&
+        administrative_area_name_regions_.empty()) {
+      return false;
+    }
+
+    // Cannot build dependent locality suggestions if none of the localities
+    // match.
+    if (address_field == DEPENDENT_LOCALITY && !all_localities_match_ &&
+        locality_key_regions_.empty() && locality_name_regions_.empty()) {
+      return false;
+    }
+
+    bool all_parents_match =
+        (parent_address_field == ADMIN_AREA &&
+         all_administrative_areas_match_) ||
+        (parent_address_field == LOCALITY && all_localities_match_);
+
+    ScopedVector<Suggestion>* suggestions = NULL;
+    switch (address_field) {
+      case ADMIN_AREA:
+        suggestions = &administrative_area_;
+        break;
+      case LOCALITY:
+        suggestions = &locality_;
+        break;
+      case DEPENDENT_LOCALITY:
+        suggestions = &dependent_locality_;
+        break;
+      default:
+        NOTREACHED();
+        break;
+    }
+
+    std::set<const RegionData*>* key_parents = NULL;
+    std::set<const RegionData*>* name_parents = NULL;
+    std::set<const RegionData*>* key_regions = NULL;
+    std::set<const RegionData*>* name_regions = NULL;
+    switch (address_field) {
+      case ADMIN_AREA:
+        key_parents = NULL;
+        name_parents = NULL;
+        key_regions = &administrative_area_key_regions_;
+        name_regions = &administrative_area_name_regions_;
+        break;
+      case LOCALITY:
+        key_parents = &administrative_area_key_regions_;
+        name_parents = &administrative_area_name_regions_;
+        key_regions = &locality_key_regions_;
+        name_regions = &locality_name_regions_;
+        break;
+      case DEPENDENT_LOCALITY:
+        key_parents = &locality_key_regions_;
+        name_parents = &locality_name_regions_;
+        key_regions = NULL;
+        name_regions = NULL;
+        break;
+      default:
+        NOTREACHED();
+        break;
+    }
+
+    bool added_suggestions = false;
+    for (std::set<const RegionData*>::const_iterator
+             key_it = regions_match_key.begin(),
+             name_it = regions_match_name.begin();
+         key_it != regions_match_key.end() ||
+             name_it != regions_match_name.end();) {
+      const RegionData* key_region =
+          key_it != regions_match_key.end() ? *key_it : NULL;
+
+      const RegionData* name_region =
+          name_it != regions_match_name.end() ? *name_it : NULL;
+
+      const RegionData* key_parent = NULL;
+      const RegionData* name_parent = NULL;
+      if (key_parents && !all_parents_match) {
+        if (key_region) {
+          DCHECK(key_region->has_parent());
+
+          std::set<const RegionData*>::const_iterator key_parent_it =
+              key_parents->find(&key_region->parent());
+
+          if (key_parent_it != key_parents->end())
+            key_parent = *key_parent_it;
+        }
+
+        if (name_region) {
+          DCHECK(name_region->has_parent());
+
+          std::set<const RegionData*>::const_iterator name_parent_it =
+              name_parents->find(&name_region->parent());
+
+          if (name_parent_it != name_parents->end())
+            name_parent = *name_parent_it;
+        }
+      }
+
+      // This algorithm assumes that iterating over a set is sorted.

[Evan Stade, 2014/06/20 22:32:27]

comment doesn't make sense (to me at least)

[please use gerrit instead, 2014/06/24 21:23:42]

Improved the comments and reduced the number of lines.

+      if (name_region && (!key_region || name_region < key_region)) {
+        if (!name_parents || name_parent || all_parents_match) {
+          added_suggestions = true;
+          suggestions->push_back(
+              new Suggestion(name_region, address_field, false, true));
+
+          if (name_regions)
+            name_regions->insert(name_region);
+        }
+
+        ++name_it;
+      } else if (key_region && (!name_region || key_region < name_region)) {
+        if (!key_parents || key_parent || all_parents_match) {
+          added_suggestions = true;
+          suggestions->push_back(
+              new Suggestion(key_region, address_field, true, false));
+
+          if (key_regions)
+            key_regions->insert(key_region);
+        }
+
+        ++key_it;
+      } else if (key_region == name_region) {
+        if (!key_parents || key_parent || all_parents_match) {
+          added_suggestions = true;
+          suggestions->push_back(
+              new Suggestion(key_region, address_field, true, true));
+
+          if (key_regions) {
+            key_regions->insert(key_region);
+            name_regions->insert(name_region);
+          }
+        }
+
+        ++key_it;
+        ++name_it;
+      }
+    }
+
+    return added_suggestions;
+  }
+
+  // Swaps in the result into |suggestions|. This object is not usable after
+  // this call due to using the swap() operation.
+  //
+  // Assumes that the number of sub-regions at each level is larger than the
+  // suggestion limit. Therefore, does not return anything when all regions
+  // match for a field.
+  void GetSuggestions(ScopedVector<Suggestion>* suggestions) {
+    DCHECK(suggestions);
+
+    if (!dependent_locality_.empty())
+      suggestions->swap(dependent_locality_);
+    else if (!locality_.empty())
+      suggestions->swap(locality_);
+    else
+      suggestions->swap(administrative_area_);
+  }
+
+ private:
+  // Sets of non-owned regions for fast lookup of parent regions.
+  std::set<const RegionData*> administrative_area_key_regions_;
+  std::set<const RegionData*> administrative_area_name_regions_;
+  std::set<const RegionData*> locality_key_regions_;
+  std::set<const RegionData*> locality_name_regions_;
+
+  bool all_administrative_areas_match_;
+  bool all_localities_match_;
+
+  ScopedVector<Suggestion> administrative_area_;
+  ScopedVector<Suggestion> locality_;
+  ScopedVector<Suggestion> dependent_locality_;
+
+  DISALLOW_COPY_AND_ASSIGN(CountrySuggestions);
+};
+
+// Region data for a field.
+class FieldData {
+ public:
+  explicit FieldData(AddressField field) : field_(field) {
+    DCHECK(field >= ADMIN_AREA);
+    DCHECK(field <= DEPENDENT_LOCALITY);
+  }
+
+  ~FieldData() {}
+
+  // Returns the field for all of the regions.
+  AddressField field() const { return field_; }
+
+  // Returns true if no data was added in AddRegionData().
+  bool empty() const { return keys_.empty() && names_.empty(); }
+
+  // Adds |region_data| with specified |key| and |name|. Does not use the key
+  // and name from |region_data| to allow for string canonicalization. Does not
+  // take ownership of |region_data|.
+  void AddRegionData(const std::string& key,
+                     const std::string& name,
+                     const RegionData* region_data) {
+    DCHECK(region_data);
+    if (!key.empty())
+      keys_.AddDataForKey(key, region_data);
+    if (!name.empty())
+      names_.AddDataForKey(name, region_data);
+  }
+
+  // Looks up |search_term| in the regions that were previously added via
+  // AddRegionData(). Saves the regions that match the |search_term| by key into
+  // |regions_match_key| and by name into |regions_match_name|, which should not
+  // be NULL. The caller does not own the RegionData objects.
+  void FindRegionData(const std::string& search_term,
+                      std::set<const RegionData*>* regions_match_key,
+                      std::set<const RegionData*>* regions_match_name) const {
+    DCHECK(regions_match_key);
+    DCHECK(regions_match_name);
+    keys_.FindDataForKeyPrefix(search_term, regions_match_key);
+    names_.FindDataForKeyPrefix(search_term, regions_match_name);
+  }
+
+ private:
+  const AddressField field_;
+  Trie<const RegionData*> keys_;
+  Trie<const RegionData*> names_;
+
+  DISALLOW_COPY_AND_ASSIGN(FieldData);
+};
+
+// Region data for a country.
+class CountryData {
+ public:
+  CountryData(const RegionData& country_region,
+              const StringCanonicalizer& shared_canonicalizer)
+      : administrative_area_(ADMIN_AREA),
+        locality_(LOCALITY),
+        dependent_locality_(DEPENDENT_LOCALITY),
+        canonicalizer_(shared_canonicalizer) {
+    DCHECK(!country_region.has_parent());
+
+    if (!country_region.sub_regions().empty())
+      AddSubRegionsOf(country_region, COUNTRY);
+
+    if (!dependent_locality_.empty())
+      min_region_size_ = DEPENDENT_LOCALITY;
+    else if (!locality_.empty())
+      min_region_size_ = LOCALITY;
+    else if (!administrative_area_.empty())
+      min_region_size_ = ADMIN_AREA;
+    else
+      min_region_size_ = COUNTRY;
+  }
+
+  ~CountryData() {}
+
+  void GetSuggestions(const AddressData& user_input,
+                      AddressField focused_field,
+                      ScopedVector<Suggestion>* results) const {
+    // Do not suggest anything if there's no suggestion data for any fields.
+    if (administrative_area_.empty())
+      return;
+
+    // Do not suggest anything if there's no suggestion data for the focused
+    // field.
+    if (focused_field != POSTAL_CODE && min_region_size_ < focused_field)
+      return;
+
+    // Canonicalized user input data for lookup in the tries.
+    AddressData canonical_input = user_input;
+    for (int i = ADMIN_AREA; i <= DEPENDENT_LOCALITY; ++i) {
+      AddressField address_field = static_cast<AddressField>(i);
+      const std::string& field_value = user_input.GetFieldValue(address_field);
+      if (!field_value.empty()) {
+        canonical_input.SetFieldValue(address_field,
+                                      canonicalizer_.Canonicalize(field_value));
+      }
+    }
+
+    // Non-owned regions that match a field value in user input by region key or
+    // name.
+    std::set<const RegionData*> regions_match_key;
+    std::set<const RegionData*> regions_match_name;
+
+    CountrySuggestions suggestions;
+    for (int i = ADMIN_AREA; i <= focused_field && i <= DEPENDENT_LOCALITY;
+         ++i) {
+      AddressField address_field = static_cast<AddressField>(i);
+      AddressField parent_address_field = static_cast<AddressField>(i - 1);
+
+      const std::string& canonical_field_value =
+          canonical_input.GetFieldValue(address_field);
+
+      if (canonical_field_value.empty() &&
+          (address_field == ADMIN_AREA ||
+           canonical_input.GetFieldValue(parent_address_field).empty())) {
+        suggestions.AllRegionsMatchForField(address_field);
+        continue;
+      }
+
+      regions_match_key.clear();
+      regions_match_name.clear();
+
+      GetRegionDataForField(address_field).FindRegionData(
+          canonical_field_value, &regions_match_key, &regions_match_name);
+
+      bool added_suggestions = suggestions.AddRegions(
+          address_field, regions_match_key, regions_match_name);
+
+      // Do not suggest anything if the focused field does not have suggestions.
+      if (address_field == focused_field && !added_suggestions) {
+        return;
+      }
+    }
+
+    suggestions.GetSuggestions(results);
+  }
+
+ private:
+  // Returns the regions for |field|, which should be either ADMIN_AREA,
+  // LOCALITY, or DEPENDENT_LOCALITY.
+  FieldData& GetRegionDataForField(AddressField field) {
+    switch (field) {
+      case ADMIN_AREA:
+        return administrative_area_;
+      case LOCALITY:
+        return locality_;
+      case DEPENDENT_LOCALITY:
+        return dependent_locality_;
+      default:
+        break;
+    }
+    NOTREACHED();
+    return administrative_area_;
+  }
+
+  const FieldData& GetRegionDataForField(AddressField field) const {
+    return const_cast<CountryData*>(this)->GetRegionDataForField(field);
+  }
+
+  void AddSubRegionsOf(const RegionData& parent_region,
+                       AddressField parent_field) {
+    DCHECK(!parent_region.sub_regions().empty());
+
+    AddressField field = static_cast<AddressField>(parent_field + 1);
+    DCHECK(field >= ADMIN_AREA);
+    DCHECK(field <= DEPENDENT_LOCALITY);
+
+    FieldData& field_regions = GetRegionDataForField(field);
+    for (std::vector<const RegionData*>::const_iterator it =
+             parent_region.sub_regions().begin();
+         it != parent_region.sub_regions().end();
+         ++it) {
+      const RegionData* region = *it;
+      DCHECK(region);
+
+      field_regions.AddRegionData(canonicalizer_.Canonicalize(region->key()),
+                                  canonicalizer_.Canonicalize(region->name()),
+                                  region);
+      if (!region->sub_regions().empty())
+        AddSubRegionsOf(*region, field);
+    }
+  }
+
+  FieldData administrative_area_;
+  FieldData locality_;
+  FieldData dependent_locality_;
+  AddressField min_region_size_;
+  const StringCanonicalizer& canonicalizer_;
+
+  DISALLOW_COPY_AND_ASSIGN(CountryData);
+};
+
+}  // namespace
+
+// Region data for all countries.
+class InputSuggester::AllCountries {
+ public:
+  AllCountries(PreloadSupplier* supplier) : region_data_builder_(supplier) {}
+
+  ~AllCountries() { STLDeleteValues(&regions_); }
+
+  void GetSuggestions(const AddressData& user_input,
+                      AddressField focused_field,
+                      ScopedVector<Suggestion>* suggestions) {
+    // Lazily initialize the mapping from fields to Trie objects.
+    std::string unused_best_language;
+    const RegionData& region_data =
+        region_data_builder_.Build(user_input.region_code,
+                                   user_input.language_code,
+                                   &unused_best_language);
+
+    std::map<const RegionData*, const CountryData*>::iterator country_data_it =
+        regions_.find(&region_data);
+    if (country_data_it == regions_.end()) {
+      country_data_it =
+          regions_.insert(std::make_pair(
+                              &region_data,
+                              new CountryData(region_data, canonicalizer_)))
+              .first;
+    }
+    DCHECK(country_data_it->second);
+
+    country_data_it->second->GetSuggestions(
+        user_input, focused_field, suggestions);
+  }
+
+ private:
+  // A mapping from a COUNTRY level region to a collection of all of its
+  // sub-regions.
+  std::map<const RegionData*, const CountryData*> regions_;
+
+  // Data source for region data.
+  RegionDataBuilder region_data_builder_;
+
+  // Canonicalizes strings for case and diacritic insensitive search.
+  const StringCanonicalizer canonicalizer_;
+
+  DISALLOW_COPY_AND_ASSIGN(AllCountries);
+};
+
+InputSuggester::InputSuggester(PreloadSupplier* supplier)
+    : all_regions_(new AllCountries(supplier)) {
+}
+
+InputSuggester::~InputSuggester() {
+}
+
+void InputSuggester::GetSuggestions(const AddressData& user_input,
+                                    AddressField focused_field,
+                                    size_t suggestions_limit,
+                                    std::vector<AddressData>* suggestions) {
+  DCHECK(suggestions);
+  DCHECK(focused_field == POSTAL_CODE ||
+         (focused_field >= ADMIN_AREA && focused_field <= DEPENDENT_LOCALITY));
+
+  // Do not suggest anything if the user input is empty.
+  if (user_input.IsFieldEmpty(focused_field))
+    return;
+
+  // Build the list of regions that match |user_input| when the user is typing
+  // in the |focused_field|.
+  ScopedVector<Suggestion> suggested_regions;
+  all_regions_->GetSuggestions(user_input, focused_field, &suggested_regions);
+
+  // Generate suggestions based on the regions.
+  for (ScopedVector<Suggestion>::const_iterator suggestion_it =
+           suggested_regions.begin();
+       suggestion_it != suggested_regions.end();
+       ++suggestion_it) {
+    Suggestion* suggested_region = *suggestion_it;
+
+    // Do not add more suggestions than |suggestions_limit|.
+    if (suggestions->size() >= suggestions_limit) {
+      suggestions->clear();
+      return;
+    }
+
+    AddressData address;
+    address.region_code = user_input.region_code;
+    address.postal_code = user_input.postal_code;
+
+    // Traverse the tree of regions from the most specific |region| 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|.
+    AddressField address_field = suggested_region->matching_address_field();
+    for (const RegionData* region = &suggested_region->region_to_suggest();
+         region->has_parent();
+         region = &region->parent()) {
+      address.SetFieldValue(address_field,
+                            suggested_region->region_key_matches()
+                                ? region->key()
+                                : region->name());
+      address_field = static_cast<AddressField>(address_field - 1);
+    }
+
+    suggestions->push_back(address);
+  }
+}
+
+}  // namespace autofill