Omnibox: Make Keyword Provide More Generous with Matching

components/search_engines/template_url_service.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 "components/search_engines/template_url_service.h"
 
 #include <algorithm>
 #include <utility>
 
 #include "base/auto_reset.h"
 #include "base/command_line.h"
 #include "base/compiler_specific.h"
 #include "base/guid.h"
 #include "base/i18n/case_conversion.h"
 #include "base/memory/scoped_vector.h"
 #include "base/metrics/histogram_macros.h"
 #include "base/prefs/pref_service.h"
 #include "base/profiler/scoped_tracker.h"
 #include "base/stl_util.h"
 #include "base/strings/string_split.h"
 #include "base/strings/string_util.h"
 #include "base/strings/utf_string_conversions.h"
 #include "base/time/default_clock.h"
 #include "base/time/time.h"
+#include "components/omnibox/browser/omnibox_field_trial.h"
 #include "components/pref_registry/pref_registry_syncable.h"
 #include "components/rappor/rappor_service.h"
 #include "components/search_engines/search_engines_pref_names.h"
 #include "components/search_engines/search_host_to_urls_map.h"
 #include "components/search_engines/search_terms_data.h"
 #include "components/search_engines/template_url.h"
 #include "components/search_engines/template_url_prepopulate_data.h"
 #include "components/search_engines/template_url_service_client.h"
 #include "components/search_engines/template_url_service_observer.h"
 #include "components/search_engines/util.h"
@@ skipping 107 matching lines @@
   int num_dupes = 0;
   for (std::map<std::string, int>::const_iterator it = duplicates.begin();
       it != duplicates.end(); ++it) {
     if (it->second > 1)
       num_dupes++;
   }
 
   UMA_HISTOGRAM_COUNTS_100("Search.SearchEngineDuplicateCounts", num_dupes);
 }
 
+// Returns the length of the registry portion of a hostname.  For example,
+// www.google.co.uk will return 5 (the length of co.uk).
+size_t GetRegistryLength(const base::string16& host) {
+  return net::registry_controlled_domains::GetRegistryLength(
+      base::UTF16ToUTF8(host),
+      net::registry_controlled_domains::EXCLUDE_UNKNOWN_REGISTRIES,
+      net::registry_controlled_domains::EXCLUDE_PRIVATE_REGISTRIES);
+}
+
+// Returns the domain name (including registry) of a hostname.  For example,
+// www.google.co.uk will return google.co.uk.
+base::string16 GetDomainAndRegistry(const base::string16& host) {
+  return base::UTF8ToUTF16(
+      net::registry_controlled_domains::GetDomainAndRegistry(
+          base::UTF16ToUTF8(host),
+          net::registry_controlled_domains::EXCLUDE_PRIVATE_REGISTRIES));
+}
+
+// Returns the length of the important part of the |keyword|, assumed to be
+// associated with the TemplateURL.  For instance, for the keyword
+// google.co.uk, this can return 6 (the length of "google").
+size_t GetMeaningfulKeywordLength(const base::string16& keyword,
+                                  const TemplateURL* turl) {
+  if (OmniboxFieldTrial::KeywordRequiresRegistry())
+    return keyword.length();
+  const size_t registry_length = GetRegistryLength(keyword);
+  if (registry_length == std::string::npos)
+    return keyword.length();
+  DCHECK_LT(registry_length, keyword.length());
+  // The meaningful keyword length is the length of any portion before the
+  // registry ("co.uk") and its preceding dot.
+  return keyword.length() - (registry_length ? (registry_length + 1) : 0);
+
+}
+
 }  // namespace
 
-
 // TemplateURLService::LessWithPrefix -----------------------------------------
 
 class TemplateURLService::LessWithPrefix {
  public:
   // We want to find the set of keywords that begin with a prefix.  The STL
   // algorithms will return the set of elements that are "equal to" the
   // prefix, where "equal(x, y)" means "!(cmp(x, y) || cmp(y, x))".  When
   // cmp() is the typical std::less<>, this results in lexicographic equality;
   // we need to extend this to mark a prefix as "not less than" a keyword it
   // begins, which will cause the desired elements to be considered "equal to"
   // the prefix.  Note: this is still a strict weak ordering, as required by
   // equal_range() (though I will not prove that here).
   //
   // Unfortunately the calling convention is not "prefix and element" but
   // rather "two elements", so we pass the prefix as a fake "element" which has
   // a NULL KeywordDataElement pointer.
-  bool operator()(const KeywordToTemplateMap::value_type& elem1,
-                  const KeywordToTemplateMap::value_type& elem2) const {
-    return (elem1.second == NULL) ?
+  bool operator()(
+      const KeywordToTURLAndMeaningfulLength::value_type& elem1,
+      const KeywordToTURLAndMeaningfulLength::value_type& elem2) const {
+    return (elem1.second.first == NULL) ?
         (elem2.first.compare(0, elem1.first.length(), elem1.first) > 0) :
         (elem1.first < elem2.first);
   }
 };
 
 
 // TemplateURLService ---------------------------------------------------------
 
 TemplateURLService::TemplateURLService(
     PrefService* prefs,
@@ skipping 153 matching lines @@
   // We don't have a TemplateURL with keyword.  We still may not allow this
   // keyword if there's evidence we may have created this keyword before and
   // the user renamed it (because, for instance, the keyword is a common word
   // that may interfere with search queries).  An easy heuristic for this is
   // whether the user has a TemplateURL that has been manually modified (e.g.,
   // renamed) connected to the same host.
   return !url.is_valid() || url.host().empty() ||
       CanAddAutogeneratedKeywordForHost(url.host());
 }
 
-void TemplateURLService::FindMatchingKeywords(
+void TemplateURLService::AddMatchingKeywords(
     const base::string16& prefix,
-    bool support_replacement_only,
-    TemplateURLVector* matches) {
-  // Sanity check args.
-  if (prefix.empty())
-    return;
-  DCHECK(matches != NULL);
-  DCHECK(matches->empty());  // The code for exact matches assumes this.
+    bool supports_replacement_only,
+    TURLsAndMeaningfulLengths* matches) {
+  AddMatchingKeywordsHelper(
+      keyword_to_turl_and_length_, prefix, supports_replacement_only, matches);
+}
 
-  // Required for VS2010: http://connect.microsoft.com/VisualStudio/feedback/details/520043/error-converting-from-null-to-a-pointer-type-in-std-pair
-  TemplateURL* const kNullTemplateURL = NULL;
-
-  // Find matching keyword range.  Searches the element map for keywords
-  // beginning with |prefix| and stores the endpoints of the resulting set in
-  // |match_range|.
-  const std::pair<KeywordToTemplateMap::const_iterator,
-                  KeywordToTemplateMap::const_iterator> match_range(
-      std::equal_range(
-          keyword_to_template_map_.begin(), keyword_to_template_map_.end(),
-          KeywordToTemplateMap::value_type(prefix, kNullTemplateURL),
-          LessWithPrefix()));
-
-  // Return vector of matching keywords.
-  for (KeywordToTemplateMap::const_iterator i(match_range.first);
-       i != match_range.second; ++i) {
-    if (!support_replacement_only ||
-        i->second->url_ref().SupportsReplacement(search_terms_data()))
-      matches->push_back(i->second);
-  }
+void TemplateURLService::AddMatchingDomainKeywords(
+    const base::string16& prefix,
+    bool supports_replacement_only,
+    TURLsAndMeaningfulLengths* matches) {
+  AddMatchingKeywordsHelper(
+      keyword_domain_to_turl_and_length_, prefix, supports_replacement_only,
+      matches);
 }
 
 TemplateURL* TemplateURLService::GetTemplateURLForKeyword(
     const base::string16& keyword) {
-  KeywordToTemplateMap::const_iterator elem(
-      keyword_to_template_map_.find(keyword));
-  if (elem != keyword_to_template_map_.end())
-    return elem->second;
+  KeywordToTURLAndMeaningfulLength::const_iterator elem(
+      keyword_to_turl_and_length_.find(keyword));
+  if (elem != keyword_to_turl_and_length_.end())
+    return elem->second.first;
   return (!loaded_ &&
       initial_default_search_provider_.get() &&
       (initial_default_search_provider_->keyword() == keyword)) ?
       initial_default_search_provider_.get() : NULL;
 }
 
 TemplateURL* TemplateURLService::GetTemplateURLForGUID(
     const std::string& sync_guid) {
-  GUIDToTemplateMap::const_iterator elem(guid_to_template_map_.find(sync_guid));
-  if (elem != guid_to_template_map_.end())
+  GUIDToTURL::const_iterator elem(guid_to_turl_.find(sync_guid));
+  if (elem != guid_to_turl_.end())
     return elem->second;
   return (!loaded_ &&
       initial_default_search_provider_.get() &&
       (initial_default_search_provider_->sync_guid() == sync_guid)) ?
       initial_default_search_provider_.get() : NULL;
 }
 
 TemplateURL* TemplateURLService::GetTemplateURLForHost(
     const std::string& host) {
   if (loaded_)
@@ skipping 1001 matching lines @@
     }
   }
 
   // Request a server check for the correct Google URL if Google is the
   // default search engine.
   RequestGoogleURLTrackerServerCheckIfNecessary();
 }
 
 void TemplateURLService::RemoveFromMaps(TemplateURL* template_url) {
   const base::string16& keyword = template_url->keyword();
-  DCHECK_NE(0U, keyword_to_template_map_.count(keyword));
-  if (keyword_to_template_map_[keyword] == template_url) {
+  DCHECK_NE(0U, keyword_to_turl_and_length_.count(keyword));
+  if (keyword_to_turl_and_length_[keyword].first == template_url) {
     // We need to check whether the keyword can now be provided by another
     // TemplateURL.  See the comments in AddToMaps() for more information on
     // extension keywords and how they can coexist with non-extension keywords.
     // In the case of more than one extension, we use the most recently
     // installed (which will be the most recently added, which will have the
     // highest ID).
     TemplateURL* best_fallback = NULL;
     for (TemplateURLVector::const_iterator i(template_urls_.begin());
          i != template_urls_.end(); ++i) {
       TemplateURL* turl = *i;
       // This next statement relies on the fact that there can only be one
       // non-Omnibox API TemplateURL with a given keyword.
       if ((turl != template_url) && (turl->keyword() == keyword) &&
           (!best_fallback ||
            (best_fallback->GetType() != TemplateURL::OMNIBOX_API_EXTENSION) ||
            ((turl->GetType() == TemplateURL::OMNIBOX_API_EXTENSION) &&
             (turl->id() > best_fallback->id()))))
         best_fallback = turl;
     }
-    if (best_fallback)
-      keyword_to_template_map_[keyword] = best_fallback;
-    else
-      keyword_to_template_map_.erase(keyword);
+    RemoveFromDomainMap(template_url);
+    if (best_fallback) {
+      AddToMap(best_fallback);
+      AddToDomainMap(best_fallback);
+    } else {
+      keyword_to_turl_and_length_.erase(keyword);
+    }
   }
 
   if (template_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION)
     return;
 
   if (!template_url->sync_guid().empty())
-    guid_to_template_map_.erase(template_url->sync_guid());
+    guid_to_turl_.erase(template_url->sync_guid());
   // |provider_map_| is only initialized after loading has completed.
   if (loaded_) {
     provider_map_->Remove(template_url);
   }
 }
 
 void TemplateURLService::AddToMaps(TemplateURL* template_url) {
   bool template_url_is_omnibox_api =
       template_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION;
   const base::string16& keyword = template_url->keyword();
-  KeywordToTemplateMap::const_iterator i =
-      keyword_to_template_map_.find(keyword);
-  if (i == keyword_to_template_map_.end()) {
-    keyword_to_template_map_[keyword] = template_url;
+  KeywordToTURLAndMeaningfulLength::const_iterator i =
+      keyword_to_turl_and_length_.find(keyword);
+  if (i == keyword_to_turl_and_length_.end()) {
+    AddToMap(template_url);
+    AddToDomainMap(template_url);
   } else {
-    const TemplateURL* existing_url = i->second;
+    const TemplateURL* existing_url = i->second.first;
     // We should only have overlapping keywords when at least one comes from
     // an extension.  In that case, the ranking order is:
     //   Manually-modified keywords > extension keywords > replaceable keywords
     // When there are multiple extensions, the last-added wins.
     bool existing_url_is_omnibox_api =
         existing_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION;
     DCHECK(existing_url_is_omnibox_api || template_url_is_omnibox_api);
     if (existing_url_is_omnibox_api ?
-        !CanReplace(template_url) : CanReplace(existing_url))
-      keyword_to_template_map_[keyword] = template_url;
+        !CanReplace(template_url) : CanReplace(existing_url)) {
+      RemoveFromDomainMap(existing_url);
+      AddToMap(template_url);
+      AddToDomainMap(template_url);
+    }
   }
 
   if (template_url_is_omnibox_api)
     return;
 
   if (!template_url->sync_guid().empty())
-    guid_to_template_map_[template_url->sync_guid()] = template_url;
+    guid_to_turl_[template_url->sync_guid()] = template_url;
   // |provider_map_| is only initialized after loading has completed.
   if (loaded_)
     provider_map_->Add(template_url, search_terms_data());
 }
 
+void TemplateURLService::RemoveFromDomainMap(const TemplateURL* template_url) {
+  const base::string16 domain = GetDomainAndRegistry(template_url->keyword());
+  if (domain.empty())
+    return;
+
+  const auto match_range(
+      keyword_domain_to_turl_and_length_.equal_range(domain));
+  for (auto it(match_range.first); it != match_range.second; ) {
+    if (it->second.first == template_url)
+      it = keyword_domain_to_turl_and_length_.erase(it);
+    else
+      ++it;
+  }
+}
+
+void TemplateURLService::AddToDomainMap(TemplateURL* template_url) {
+  const base::string16 domain = GetDomainAndRegistry(template_url->keyword());
+  // Only bother adding an entry to the domain map if its key in the domain
+  // map would be different from the key in the regular map.
+  if (domain != template_url->keyword()) {
+    keyword_domain_to_turl_and_length_.insert(std::make_pair(
+        domain,
+        TURLAndMeaningfulLength(
+            template_url, GetMeaningfulKeywordLength(domain, template_url))));
+  }
+}
+
+void TemplateURLService::AddToMap(TemplateURL* template_url) {

[Mark P, 2015/11/13 06:06:49]

FYI, I had to revise this function.  To see my changes, compare this patchset
with 8 or 9 (the last patchset you reviewed).

Earlier, part of my earlier refactoring to make it shared between the regular
map and the domain map, I made it do .insert() on the map.  This doesn't work on
the regular map because I wanted the replace behavior and .insert() doesn't do
anything if the key already exists.  Hence, I changed this function to only be
used with the regular map and did the [] insert, and changed AddToDomainMap to
do the .insert() method.  It's too bad there isn't a common function that means
insert (if not existing, or if applied to a multimap) or replace (if existing
when applied to a non-multimap).

[Mark P, 2015/11/13 16:33:14]

For the record, I realized I could do something messy such
value = TemplateURLAndMeaningfulLength(...)
map->insert(std::make_pair(key, value)).second = value
but that seems unnecessarily messy, and the current approach (one helper for
each map) seems pretty clean to me.

+  const base::string16& keyword = template_url->keyword();
+  keyword_to_turl_and_length_[keyword] =
+      TURLAndMeaningfulLength(
+          template_url, GetMeaningfulKeywordLength(keyword, template_url));
+}
+
 // Helper for partition() call in next function.
 bool HasValidID(TemplateURL* t_url) {
   return t_url->id() != kInvalidTemplateURLID;
 }
 
 void TemplateURLService::SetTemplateURLs(TemplateURLVector* urls) {
   // Partition the URLs first, instead of implementing the loops below by simply
   // scanning the input twice.  While it's not supposed to happen normally, it's
   // possible for corrupt databases to return multiple entries with the same
   // keyword.  In this case, the first loop may delete the first entry when
@@ skipping 90 matching lines @@
 bool TemplateURLService::UpdateNoNotify(TemplateURL* existing_turl,
                                         const TemplateURL& new_values) {
   DCHECK(existing_turl);
   if (std::find(template_urls_.begin(), template_urls_.end(), existing_turl) ==
       template_urls_.end())
     return false;
 
   DCHECK_NE(TemplateURL::OMNIBOX_API_EXTENSION, existing_turl->GetType());
 
   base::string16 old_keyword(existing_turl->keyword());
-  keyword_to_template_map_.erase(old_keyword);
+  keyword_to_turl_and_length_.erase(old_keyword);
+  RemoveFromDomainMap(existing_turl);
   if (!existing_turl->sync_guid().empty())
-    guid_to_template_map_.erase(existing_turl->sync_guid());
+    guid_to_turl_.erase(existing_turl->sync_guid());
 
   // |provider_map_| is only initialized after loading has completed.
   if (loaded_)
     provider_map_->Remove(existing_turl);
 
   TemplateURLID previous_id = existing_turl->id();
   existing_turl->CopyFrom(new_values);
   existing_turl->data_.id = previous_id;
 
   if (loaded_) {
     provider_map_->Add(existing_turl, search_terms_data());
   }
 
   const base::string16& keyword = existing_turl->keyword();
-  KeywordToTemplateMap::const_iterator i =
-      keyword_to_template_map_.find(keyword);
-  if (i == keyword_to_template_map_.end()) {
-    keyword_to_template_map_[keyword] = existing_turl;
+  KeywordToTURLAndMeaningfulLength::const_iterator i =
+      keyword_to_turl_and_length_.find(keyword);
+  if (i == keyword_to_turl_and_length_.end()) {
+    AddToMap(existing_turl);
+    AddToDomainMap(existing_turl);
   } else {
     // We can theoretically reach here in two cases:
     //   * There is an existing extension keyword and sync brings in a rename of
     //     a non-extension keyword to match.  In this case we just need to pick
     //     which keyword has priority to update the keyword map.
     //   * Autogeneration of the keyword for a Google default search provider
     //     at load time causes it to conflict with an existing keyword.  In this
     //     case we delete the existing keyword if it's replaceable, or else undo
     //     the change in keyword for |existing_turl|.
-    TemplateURL* existing_keyword_turl = i->second;
+    TemplateURL* existing_keyword_turl = i->second.first;
     if (existing_keyword_turl->GetType() != TemplateURL::NORMAL) {
-      if (!CanReplace(existing_turl))
-        keyword_to_template_map_[keyword] = existing_turl;
+      if (!CanReplace(existing_turl)) {
+        AddToMap(existing_turl);
+        AddToDomainMap(existing_turl);
+      }
     } else {
       if (CanReplace(existing_keyword_turl)) {
         RemoveNoNotify(existing_keyword_turl);
       } else {
         existing_turl->data_.SetKeyword(old_keyword);
-        keyword_to_template_map_[old_keyword] = existing_turl;
+        AddToMap(existing_turl);
+        AddToDomainMap(existing_turl);
       }
     }
   }
   if (!existing_turl->sync_guid().empty())
-    guid_to_template_map_[existing_turl->sync_guid()] = existing_turl;
+    guid_to_turl_[existing_turl->sync_guid()] = existing_turl;
 
   if (web_data_service_.get())
     web_data_service_->UpdateKeyword(existing_turl->data());
 
   // Inform sync of the update.
   ProcessTemplateURLChange(
       FROM_HERE, existing_turl, syncer::SyncChange::ACTION_UPDATE);
 
   if (default_search_provider_ == existing_turl &&
       default_search_provider_source_ == DefaultSearchManager::FROM_USER) {
@@ skipping 96 matching lines @@
     return;
 
   KeywordWebDataService::BatchModeScoper scoper(web_data_service_.get());
   bool something_changed = false;
   for (TemplateURLVector::iterator i(template_urls_.begin());
        i != template_urls_.end(); ++i) {
     TemplateURL* t_url = *i;
     if (t_url->HasGoogleBaseURLs(search_terms_data())) {
       TemplateURL updated_turl(t_url->data());
       updated_turl.ResetKeywordIfNecessary(search_terms_data(), false);
-      KeywordToTemplateMap::const_iterator existing_entry =
-          keyword_to_template_map_.find(updated_turl.keyword());
-      if ((existing_entry != keyword_to_template_map_.end()) &&
-          (existing_entry->second != t_url)) {
+      KeywordToTURLAndMeaningfulLength::const_iterator existing_entry =
+          keyword_to_turl_and_length_.find(updated_turl.keyword());
+      if ((existing_entry != keyword_to_turl_and_length_.end()) &&
+          (existing_entry->second.first != t_url)) {
         // The new autogenerated keyword conflicts with another TemplateURL.
         // Overwrite it if it's replaceable; otherwise, leave |t_url| using its
         // current keyword.  (This will not prevent |t_url| from auto-updating
         // the keyword in the future if the conflicting TemplateURL disappears.)
         // Note that we must still update |t_url| in this case, or the
         // |provider_map_| will not be updated correctly.
-        if (CanReplace(existing_entry->second))
-          RemoveNoNotify(existing_entry->second);
+        if (CanReplace(existing_entry->second.first))
+          RemoveNoNotify(existing_entry->second.first);
         else
           updated_turl.data_.SetKeyword(t_url->keyword());
       }
       something_changed = true;
       // This will send the keyword change to sync.  Note that other clients
       // need to reset the keyword to an appropriate local value when this
       // change arrives; see CreateTemplateURLFromTemplateURLAndSyncData().
       UpdateNoNotify(t_url, updated_turl);
     }
   }
@@ skipping 178 matching lines @@
   }
   template_urls_.push_back(template_url);
   AddToMaps(template_url);
 
   if (newly_adding &&
       (template_url->GetType() == TemplateURL::NORMAL)) {
     if (web_data_service_.get())
       web_data_service_->AddKeyword(template_url->data());
 
     // Inform sync of the addition. Note that this will assign a GUID to
-    // template_url and add it to the guid_to_template_map_.
+    // template_url and add it to the guid_to_turl_.
     ProcessTemplateURLChange(FROM_HERE,
                              template_url,
                              syncer::SyncChange::ACTION_ADD);
   }
 
   return true;
 }
 
 void TemplateURLService::RemoveNoNotify(TemplateURL* template_url) {
   DCHECK(template_url != default_search_provider_);
@@ skipping 295 matching lines @@
   if (new_guid.empty()) {
     default_search_manager_.ClearUserSelectedDefaultSearchEngine();
     return;
   }
 
   TemplateURL* turl = GetTemplateURLForGUID(new_guid);
   if (turl)
     default_search_manager_.SetUserSelectedDefaultSearchEngine(turl->data());
 }
 
+template <typename Container>
+void TemplateURLService::AddMatchingKeywordsHelper(
+    const Container& keyword_to_turl_and_length,
+    const base::string16& prefix,
+    bool supports_replacement_only,
+    TURLsAndMeaningfulLengths* matches) {
+  // Sanity check args.
+  if (prefix.empty())
+    return;
+  DCHECK(matches);
+
+  // Find matching keyword range.  Searches the element map for keywords
+  // beginning with |prefix| and stores the endpoints of the resulting set in
+  // |match_range|.
+  const auto match_range(std::equal_range(
+      keyword_to_turl_and_length.begin(), keyword_to_turl_and_length.end(),
+      typename Container::value_type(prefix,
+                                     TURLAndMeaningfulLength(nullptr, 0)),
+      LessWithPrefix()));
+
+  // Add to vector of matching keywords.
+  for (typename Container::const_iterator i(match_range.first);
+    i != match_range.second; ++i) {
+    if (!supports_replacement_only ||
+        i->second.first->url_ref().SupportsReplacement(search_terms_data()))
+      matches->push_back(i->second);
+  }
+}
+
 TemplateURL* TemplateURLService::FindPrepopulatedTemplateURL(
     int prepopulated_id) {
   for (TemplateURLVector::const_iterator i = template_urls_.begin();
        i != template_urls_.end(); ++i) {
     if ((*i)->prepopulate_id() == prepopulated_id)
       return *i;
   }
   return NULL;
 }
 
@@ skipping 38 matching lines @@
 
   if (most_recently_intalled_default) {
     base::AutoReset<DefaultSearchChangeOrigin> change_origin(
         &dsp_change_origin_, DSP_CHANGE_OVERRIDE_SETTINGS_EXTENSION);
     default_search_manager_.SetExtensionControlledDefaultSearchEngine(
         most_recently_intalled_default->data());
   } else {
     default_search_manager_.ClearExtensionControlledDefaultSearchEngine();
   }
 }