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);
+  // The meaningful keyword length is the length of any portion before the
+  // registry ("co.uk") and its preceding dot.
+  return std::max<int>(
+      keyword.length() - (registry_length ? (registry_length + 1) : 0), 0);

[Peter Kasting, 2015/11/12 22:32:11]

Actually, I'm not convinced this will do the right thing.  The compiler
complaint about mismatched comparisons is highlighting that keyword.length() and
registry_length are unsigned and the result of subtracting may underflow. 
Forcing max() to <int> will _probably_ do what you want, but I'm not totally
sure of the vagaries of how the casts here work, so I'd rather avoid that.

However, thinking more closely about this, there's no actual need to safe the
code against the "co.uk" case.  GetRegistryLength() is guaranteed to return a
value less than the length of its input as long as the input is a valid host. 
Instead we need to safe against GetRegistryLength() returning npos, which it
will do if the input string is not a valid host.  So we can do something like:

  if (registry_length == std::string::npos)
    return keyword.length();
  return keyword.length() - (registry_length ? (registry_length + 1) : 0);

[Mark P, 2015/11/12 23:18:41]

I don't think so.  Suppose the user has a keyword "co.uk".  A plausible registry
length function will return 5 for this.  The length of the keyword is also 5. 
Then we'll return 5 - (5+1) = -1
(+1 for the preceding dot, which doesn't exist).

Corrected it again back to something like the earlier version that doesn't use
max() and guards against this -1, plus with an additional guard against npos.

[Peter Kasting, 2015/11/12 23:37:51]

No, it won't; the RCDS functions are all guaranteed not to act like this,
because it misleads callers.  "co.uk" is not a navigable hostname, so
GetRegistryLength() returns 0.  This part of the function contract is spelled
out in the comments for those APIs.

[Mark P, 2015/11/12 23:49:34]

Okay, revised and added a DCHECK to confirm your assertion.

+}
+
 }  // 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) ?
+    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_template_map_, 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_template_map_, 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;
+    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())
@@ skipping 1012 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) {
+  if (keyword_to_template_map_[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
+    RemoveFromDomainMap(template_url);
+    if (best_fallback) {
+      AddToMap(&keyword_to_template_map_, keyword, best_fallback);
+      AddToDomainMap(best_fallback);
+    } else {
       keyword_to_template_map_.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());
   // |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;
+    AddToMap(&keyword_to_template_map_, keyword, 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(&keyword_to_template_map_, keyword, 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;
   // |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;
+
+  // Cached for efficiency.
+  const KeywordDomainToTemplateMap::const_iterator upper_bound =
+      keyword_domain_to_template_map_.upper_bound(domain);
+  for (KeywordDomainToTemplateMap::const_iterator it(
+           keyword_domain_to_template_map_.lower_bound(domain));
+       it != upper_bound; ) {
+    if (it->second.first == template_url)
+      it = keyword_domain_to_template_map_.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())
+    AddToMap(&keyword_domain_to_template_map_, domain, template_url);
+}
+
+// static
+template <typename Container>
+void TemplateURLService::AddToMap(
+    Container* keyword_to_template_map,
+    const base::string16& keyword,
+    TemplateURL* template_url) {
+  keyword_to_template_map->insert(std::make_pair(
+      keyword,
+      std::make_pair(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 91 matching lines @@
                                         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);
+  RemoveFromDomainMap(existing_turl);
   if (!existing_turl->sync_guid().empty())
     guid_to_template_map_.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;
+    AddToMap(&keyword_to_template_map_, keyword, 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(&keyword_to_template_map_, keyword, 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(&keyword_to_template_map_, old_keyword, existing_turl);
+        AddToDomainMap(existing_turl);
       }
     }
   }
   if (!existing_turl->sync_guid().empty())
     guid_to_template_map_[existing_turl->sync_guid()] = existing_turl;
 
   if (web_data_service_.get())
     web_data_service_->UpdateKeyword(existing_turl->data());
 
   // Inform sync of the update.
@@ skipping 104 matching lines @@
   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)) {
+          (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 494 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_template_map,
+    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_template_map.begin(), keyword_to_template_map.end(),
+      typename Container::value_type(prefix,
+                                     std::make_pair(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();
   }
 }