Omnibox: Make Keyword Provide More Generous with Matching

components/search_engines/template_url_service.cc

Index: components/search_engines/template_url_service.cc
diff --git a/components/search_engines/template_url_service.cc b/components/search_engines/template_url_service.cc
index 3402ce32fa72b93e260f2fae4122be816b421df0..dfbbd94e394ebfa2f3c6c8190d445129e60458e0 100644
--- a/components/search_engines/template_url_service.cc
+++ b/components/search_engines/template_url_service.cc
@@ -22,6 +22,7 @@
 #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"
@@ -149,6 +150,41 @@ void LogDuplicatesHistogram(
   UMA_HISTOGRAM_COUNTS_100("Search.SearchEngineDuplicateCounts", num_dupes);
 }
 
+// Returns the length of the registry portion of a hostname.  e.g.,

[Peter Kasting, 2015/11/09 23:11:15]

Nit: e.g. -> E.g., or just write "For example," (2 places)

[Mark P, 2015/11/11 07:41:00]

Did both.

+// www.google.co.uk will return 5 (=length of co.uk).

[Peter Kasting, 2015/11/09 23:11:15]

Nit: (=length -> (the length (2 places)

[Mark P, 2015/11/11 07:41:00]

Did both.

+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.  e.g.,
+// 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 non-auto-generated template URLs,
+// this is simply the length of the keyword.  For auto-generated keyword URLs,
+// it is can be less.  For instance, for the keyword google.co.uk, this can

[Peter Kasting, 2015/11/09 23:11:15]

Nit: it is -> it

[Mark P, 2015/11/11 07:41:00]

I removed the relevant sentence.  This suggestion is now moot.

+// return 6 (=length of google).
+size_t GetEffectiveKeywordLength(const base::string16& keyword,
+                                 const TemplateURL* turl) {
+  if (!turl->safe_for_autoreplace() ||

[Peter Kasting, 2015/11/09 23:11:15]

I don't really think checking for this is right, conceptually.

If I edit the keyword for "en.wikipedia.org" to "wikipedia.org", that shouldn't
disable matching "wikipedia".  If I add a new TURL with keyword "google.com", I
should still matach against "google".

In other words, I think we should simply ignore the "autogenerated" requirement
here and everywhere else in your change and do this for all keywords.  The RCD
helper functions can deal with input strings that don't look like hostnames, so
that's not a problem.

[Mark P, 2015/11/11 07:41:00]

Removed the auto-generated restriction and revised comments throughout.  Let me
know if I missed some.

+      OmniboxFieldTrial::KeywordRequiresRegistry())
+    return keyword.length();
+  const size_t registry_length = GetRegistryLength(keyword);
+  // If there's a registry, subtract the length of the registry portion of the
+  // keyword (e.g., co.uk) and an addition one for the dot that preceeds the
+  // registry.
+  return keyword.length() - ((registry_length > 0) ? (registry_length + 1) : 0);

[Peter Kasting, 2015/11/09 23:11:15]

Make sure this doesn't return -1 if you feed in the string "co.uk".

You can convert "(registry_length > 0)" to just "registry_length".

[Mark P, 2015/11/11 07:41:00]

Good point.  Fixed.
Done.

+}
+
 }  // namespace
 
 
@@ -170,7 +206,7 @@ class TemplateURLService::LessWithPrefix {
   // 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);
   }
@@ -347,33 +383,18 @@ bool TemplateURLService::CanAddAutogeneratedKeyword(
 void TemplateURLService::FindMatchingKeywords(
     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.
-
-  // 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()));
+    TemplateURLMatchesVector* matches) {
+  FindMatchingKeywordsHelper(
+      keyword_to_template_map_, prefix, support_replacement_only, matches);
+}
 
-  // 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::FindMatchingDomainKeywords(
+    const base::string16& prefix,
+    bool support_replacement_only,
+    TemplateURLMatchesVector* matches) {
+  FindMatchingKeywordsHelper(
+      keyword_domain_to_template_map_, prefix, support_replacement_only,
+      matches);
 }
 
 TemplateURL* TemplateURLService::GetTemplateURLForKeyword(
@@ -381,7 +402,7 @@ TemplateURL* TemplateURLService::GetTemplateURLForKeyword(
   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)) ?
@@ -1414,7 +1435,7 @@ void TemplateURLService::Init(const Initializer* initializers,
 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.
@@ -1434,10 +1455,15 @@ void TemplateURLService::RemoveFromMaps(TemplateURL* template_url) {
             (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) {
+      keyword_to_template_map_[keyword] =
+          std::make_pair(best_fallback,
+                         GetEffectiveKeywordLength(keyword, best_fallback));
+      AddToDomainMap(best_fallback);

[Peter Kasting, 2015/11/09 23:11:15]

You do this sort of "add to |keyword_to_template_map_|, then call
AddToDomainMap()" thing several times; it's probably worth its own helper.

In fact, since AddToDomainMap() always seems to be called in this sort of way,
maybe just replace that with a function that also does this additional bit.

[Mark P, 2015/11/12 20:13:03]

Good idea.  I added the helper and it looks a lot clearer.
I now also use the helper in AddToDomainMap.

+    } else {
       keyword_to_template_map_.erase(keyword);
+    }
   }
 
   if (template_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION)
@@ -1458,9 +1484,12 @@ void TemplateURLService::AddToMaps(TemplateURL* template_url) {
   KeywordToTemplateMap::const_iterator i =
       keyword_to_template_map_.find(keyword);
   if (i == keyword_to_template_map_.end()) {
-    keyword_to_template_map_[keyword] = template_url;
+    keyword_to_template_map_[keyword] =
+        std::make_pair(template_url,
+                       GetEffectiveKeywordLength(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
@@ -1469,8 +1498,13 @@ void TemplateURLService::AddToMaps(TemplateURL* template_url) {
         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);
+      keyword_to_template_map_[keyword] =
+          std::make_pair(template_url,
+                         GetEffectiveKeywordLength(keyword, template_url));
+      AddToDomainMap(template_url);
+    }
   }
 
   if (template_url_is_omnibox_api)
@@ -1483,6 +1517,47 @@ void TemplateURLService::AddToMaps(TemplateURL* template_url) {
     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;
+
+  // Required for VS2010: http://connect.microsoft.com/VisualStudio/feedback/details/520043/error-converting-from-null-to-a-pointer-type-in-std-pair

[Peter Kasting, 2015/11/09 23:11:15]

Nit: We no longer compile with VS2010, so let's remove this while you're
touching it anyway, and use nullptr.

[Mark P, 2015/11/11 07:41:01]

Now unneeded in this location.
Done in the other location.

+  TemplateURL* const kNullTemplateURL = NULL;
+
+  // Find all entries with the same domain name.
+  const std::pair<KeywordDomainToTemplateMap::const_iterator,
+                  KeywordDomainToTemplateMap::const_iterator> match_range(
+      std::equal_range(
+          keyword_domain_to_template_map_.begin(),
+          keyword_domain_to_template_map_.end(),
+          KeywordDomainToTemplateMap::value_type(
+              domain, std::make_pair(kNullTemplateURL, 0))));

[Peter Kasting, 2015/11/09 23:11:15]

Nit: I feel like it should be possible to replace the explicit make_pair() call
here with just "TURLAndEffectiveLength()" or something.

[Mark P, 2015/11/11 07:41:00]

That's no shorter.

Also, I usually see make_pair in the codebase even when the pair has been
aliased to something else.

Regardless, this point is now moot; I've figured out a code simplification that
doesn't use this here
(though there is still a make_pair call in AddMatchingKeywordsHelper)

+
+  // Delete the template URL in question.
+  for (KeywordDomainToTemplateMap::const_iterator it(match_range.first);
+       it != match_range.second; ++it) {
+    if (it->second.first == template_url)
+      keyword_domain_to_template_map_.erase(it);

[Peter Kasting, 2015/11/09 23:11:15]

Nit: Prefer std::erase(std::remove_if()) with a lambda.

[Mark P, 2015/11/11 07:41:00]

I have simplified this in a different way that may satisfy you.

+  }
+}
+
+void TemplateURLService::AddToDomainMap(TemplateURL* template_url) {
+  // If this TemplateURL was auto-generated, consider adding it to the domain
+  // map.
+  if (template_url->safe_for_autoreplace()) {
+    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_template_map_.insert(std::make_pair(
+          domain,
+          std::make_pair(template_url,
+                         GetEffectiveKeywordLength(domain, template_url))));
+    }
+  }
+}
+
 // Helper for partition() call in next function.
 bool HasValidID(TemplateURL* t_url) {
   return t_url->id() != kInvalidTemplateURLID;
@@ -1594,6 +1669,7 @@ bool TemplateURLService::UpdateNoNotify(TemplateURL* existing_turl,
 
   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());
 
@@ -1613,7 +1689,10 @@ bool TemplateURLService::UpdateNoNotify(TemplateURL* existing_turl,
   KeywordToTemplateMap::const_iterator i =
       keyword_to_template_map_.find(keyword);
   if (i == keyword_to_template_map_.end()) {
-    keyword_to_template_map_[keyword] = existing_turl;
+    keyword_to_template_map_[keyword] =
+        std::make_pair(existing_turl,
+                       GetEffectiveKeywordLength(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
@@ -1623,16 +1702,24 @@ bool TemplateURLService::UpdateNoNotify(TemplateURL* existing_turl,
     //     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)) {
+        keyword_to_template_map_[keyword] =
+            std::make_pair(existing_turl,
+                           GetEffectiveKeywordLength(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;
+        keyword_to_template_map_[old_keyword] =
+            std::make_pair(existing_turl,
+                           GetEffectiveKeywordLength(old_keyword,
+                                                     existing_turl));
+        AddToDomainMap(existing_turl);
       }
     }
   }
@@ -1757,15 +1844,15 @@ void TemplateURLService::GoogleBaseURLChanged() {
       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());
       }
@@ -2280,6 +2367,40 @@ void TemplateURLService::OnSyncedDefaultSearchProviderGUIDChanged() {
     default_search_manager_.SetUserSelectedDefaultSearchEngine(turl->data());
 }
 
+template <typename Container>
+void TemplateURLService::FindMatchingKeywordsHelper(
+    const Container& keyword_to_template_map,
+    const base::string16& prefix,
+    bool support_replacement_only,
+    TemplateURLMatchesVector* matches) {
+  // Sanity check args.
+  if (prefix.empty())
+    return;
+  DCHECK(matches != NULL);

[Peter Kasting, 2015/11/09 23:11:15]

Nit: DCHECK(matches); would be shorter

[Mark P, 2015/11/11 07:41:00]

Done.

+
+  // 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;

[Peter Kasting, 2015/11/09 23:11:15]

Nit: See earlier comment

[Mark P, 2015/11/11 07:41:00]

Done.

+
+  // 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<typename Container::const_iterator,
+                  typename Container::const_iterator> match_range(
+      std::equal_range(
+          keyword_to_template_map.begin(), keyword_to_template_map.end(),
+          typename Container::value_type(prefix,
+                                         std::make_pair(kNullTemplateURL, 0)),

[Peter Kasting, 2015/11/09 23:11:15]

Nit: See earlier comment

[Mark P, 2015/11/11 07:41:00]

See earlier answer. :-)

[Peter Kasting, 2015/11/12 20:36:10]

It may not be shorter to write, but I think just writing
TURLAndMeaningfulLength() here is semantically clearer.  It means "I want the
default value of the mapped type for this container".  Using make_pair()
explicitly emphasizes the importance of the values inside the make_pair() call,
but you don't actually care about what those are, and if the definition of
TURLAndMeaningfulLength changed in the future, you'd want this code to Just Keep
Working.

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

You didn't reply to this.

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

Okay, it's plausible.  Done here and everywhere there's a similar make_pair
call.  Did not change the make_pair calls that require(string,
TURLAndMeaningfulLength), because there's no easy alias for that.

+          LessWithPrefix()));
+
+  // Return vector of matching keywords.
+  for (typename Container::const_iterator i(match_range.first);
+       i != match_range.second; ++i) {
+    if (!support_replacement_only ||
+        i->second.first->url_ref().SupportsReplacement(search_terms_data()))
+      matches->push_back(i->second);
+  }

[Peter Kasting, 2015/11/09 23:11:15]

Nit: Prefer std::copy_if() with a lambda

[Mark P, 2015/11/11 07:41:00]

Not done.  I couldn't figure out the magical incantation.  Here's the closest I
got:
  // Add to vector of matching keywords.
  const SearchTermsData& data = search_terms_data();
  std::copy_if(
      match_range.first, match_range.second, matches->begin(),
      [supports_replacement_only, &data]
          (const typename Container::value_type& keyword_turl_and_length) {
            return !supports_replacement_only ||
               
keyword_turl_and_length.second.first->url_ref().SupportsReplacement(data);
      });
}

before I realized that we actually need to convert between input range type (an
iterator over a map, i.e, an iterator over key, value pairs) to output range
types (a vector simply of value pairs).

I couldn't figure out how to make copy_if work when converting between different
types like this.

[Peter Kasting, 2015/11/12 20:36:10]

You're right.  I overlooked the difference in container types.

This is doable with separate transform() and copy_if() steps, but what you have
now is cleaner than that, so leave it.

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

Acknowledged.

+}
+
 TemplateURL* TemplateURLService::FindPrepopulatedTemplateURL(
     int prepopulated_id) {
   for (TemplateURLVector::const_iterator i = template_urls_.begin();