Omnibox: Make Keyword Provide More Generous with Matching

components/omnibox/browser/keyword_provider.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/omnibox/browser/keyword_provider.h"
 
 #include <algorithm>
 #include <vector>
 
 #include "base/strings/string16.h"
 #include "base/strings/string_util.h"
 #include "base/strings/utf_string_conversions.h"
 #include "components/metrics/proto/omnibox_input_type.pb.h"
 #include "components/omnibox/browser/autocomplete_match.h"
 #include "components/omnibox/browser/autocomplete_provider_client.h"
 #include "components/omnibox/browser/autocomplete_provider_listener.h"
 #include "components/omnibox/browser/keyword_extensions_delegate.h"
+#include "components/omnibox/browser/omnibox_field_trial.h"
 #include "components/search_engines/template_url.h"
 #include "components/search_engines/template_url_service.h"
 #include "grit/components_strings.h"
 #include "net/base/escape.h"
 #include "net/base/net_util.h"
 #include "ui/base/l10n/l10n_util.h"
 
 namespace {
 
 // Helper functor for Start(), for sorting keyword matches by quality.
 class CompareQuality {
  public:
-  // A keyword is of higher quality when a greater fraction of it has been
-  // typed, that is, when it is shorter.
+  // A keyword is of higher quality when a greater fraction of the important
+  // part of it has been typed, that is, when the effective keyword length is
+  // shorter.
   //
   // TODO(pkasting): Most recent and most frequent keywords are probably
   // better rankings than the fraction of the keyword typed.  We should
   // always put any exact matches first no matter what, since the code in
   // Start() assumes this (and it makes sense).
-  bool operator()(const TemplateURL* t_url1, const TemplateURL* t_url2) const {
-    return t_url1->keyword().length() < t_url2->keyword().length();
+  bool operator()(
+      const TemplateURLService::TemplateURLAndEffectiveKeywordLength
+      t_url_match1,
+      const TemplateURLService::TemplateURLAndEffectiveKeywordLength
+      t_url_match2) const {
+    return t_url_match1.second < t_url_match2.second;
   }
 };
 
 // Helper for KeywordProvider::Start(), for ending keyword mode unless
 // explicitly told otherwise.
 class ScopedEndExtensionKeywordMode {
  public:
   explicit ScopedEndExtensionKeywordMode(KeywordExtensionsDelegate* delegate);
   ~ScopedEndExtensionKeywordMode();
 
@@ skipping 140 matching lines @@
 
   return keyword;
 }
 
 AutocompleteMatch KeywordProvider::CreateVerbatimMatch(
     const base::string16& text,
     const base::string16& keyword,
     const AutocompleteInput& input) {
   // A verbatim match is allowed to be the default match.
   return CreateAutocompleteMatch(
-      GetTemplateURLService()->GetTemplateURLForKeyword(keyword), input,
-      keyword.length(), SplitReplacementStringFromInput(text, true), true, 0);
+      GetTemplateURLService()->GetTemplateURLForKeyword(keyword),
+      keyword.length(), input, keyword.length(),
+      SplitReplacementStringFromInput(text, true), true, 0);
 }
 
 void KeywordProvider::Start(const AutocompleteInput& input,
                             bool minimal_changes) {
   // This object ensures we end keyword mode if we exit the function without
   // toggling keyword mode to on.
   ScopedEndExtensionKeywordMode keyword_mode_toggle(extensions_delegate_.get());
 
   matches_.clear();
 
@@ skipping 25 matching lines @@
   base::string16 keyword, remaining_input;
   if (!ExtractKeywordFromInput(input, &keyword, &remaining_input))
     return;
 
   // Get the best matches for this keyword.
   //
   // NOTE: We could cache the previous keywords and reuse them here in the
   // |minimal_changes| case, but since we'd still have to recalculate their
   // relevances and we can just recreate the results synchronously anyway, we
   // don't bother.
-  TemplateURLService::TemplateURLVector matches;
+  TemplateURLService::TemplateURLMatchesVector matches;
   GetTemplateURLService()->FindMatchingKeywords(
       keyword, !remaining_input.empty(), &matches);
+  if (!OmniboxFieldTrial::KeywordRequiresPrefixBeforeDomain()) {
+    GetTemplateURLService()->FindMatchingDomainKeywords(
+        keyword, !remaining_input.empty(), &matches);

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

As written this seems to imply that the functions here merely add to the vector
outparam instead of resetting its contents, but the functions are not named that
way (AddMatchingXXX()), have no comments to that effect in the .h, and that
would be atypical behavior for a function.  You should either not assume that
here, or make it clear in the function names/comments that they behave this way.

[Mark P, 2015/11/11 07:40:59]

Revised to AddMatching...() and changed all comments appropriately.

+  }
 
-  for (TemplateURLService::TemplateURLVector::iterator i(matches.begin());
-       i != matches.end(); ) {
-    const TemplateURL* template_url = *i;
+  for (TemplateURLService::TemplateURLMatchesVector::iterator
+           i(matches.begin()); i != matches.end(); ) {
+    const TemplateURL* template_url = i->first;
 
     // Prune any extension keywords that are disallowed in incognito mode (if
     // we're incognito), or disabled.
     if (template_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION &&
         extensions_delegate_ &&
         !extensions_delegate_->IsEnabledExtension(
             template_url->GetExtensionId())) {
       i = matches.erase(i);
       continue;
     }
@@ skipping 10 matching lines @@
     ++i;
   }
   if (matches.empty())
     return;
   std::sort(matches.begin(), matches.end(), CompareQuality());
 
   // Limit to one exact or three inexact matches, and mark them up for display
   // in the autocomplete popup.
   // Any exact match is going to be the highest quality match, and thus at the
   // front of our vector.
-  if (matches.front()->keyword() == keyword) {
-    const TemplateURL* template_url = matches.front();
+  if (matches.front().first->keyword() == keyword) {
+    const TemplateURL* template_url = matches.front().first;
+    const size_t effective_keyword_length = matches.front().second;
     const bool is_extension_keyword =
         template_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION;
 
     // Only create an exact match if |remaining_input| is empty or if
     // this is an extension keyword.  If |remaining_input| is a
     // non-empty non-extension keyword (i.e., a regular keyword that
     // supports replacement and that has extra text following it),
     // then SearchProvider creates the exact (a.k.a. verbatim) match.
     if (!remaining_input.empty() && !is_extension_keyword)
       return;
 
     // TODO(pkasting): We should probably check that if the user explicitly
     // typed a scheme, that scheme matches the one in |template_url|.
 
     // When creating an exact match (either for the keyword itself, no
     // remaining query or an extension keyword, possibly with remaining
     // input), allow the match to be the default match.
     matches_.push_back(CreateAutocompleteMatch(
-        template_url, input, keyword.length(), remaining_input, true, -1));
+        template_url, effective_keyword_length, input, keyword.length(),
+        remaining_input, true, -1));
 
     if (is_extension_keyword && extensions_delegate_) {
       if (extensions_delegate_->Start(input, minimal_changes, template_url,
                                       remaining_input))
         keyword_mode_toggle.StayInKeywordMode();
     }
   } else {
-    if (matches.size() > kMaxMatches)
-      matches.erase(matches.begin() + kMaxMatches, matches.end());
-    for (TemplateURLService::TemplateURLVector::const_iterator i(
-         matches.begin()); i != matches.end(); ++i) {
-      matches_.push_back(CreateAutocompleteMatch(
-          *i, input, keyword.length(), remaining_input, false, -1));
+    for (TemplateURLService::TemplateURLMatchesVector::const_iterator i(
+             matches.begin());
+         (i != matches.end()) && (matches.size() <= kMaxMatches); ++i) {
+      // Skip keywords that we've already added.  It's possible we may have
+      // retrieved the same keyword twice.  For example, the keyword'

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

Nit: Mismatched '

[Mark P, 2015/11/11 07:40:59]

Done.

+      // abc.abc.com, may be retrieved for the input abc from the full keyword

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

Nit: No comma (but consider adding quotes around keyword names and input
strings).

[Mark P, 2015/11/11 07:40:59]

Did both.

+      // matching and the domain matching passes.
+      bool found_duplicate = false;
+      for (ACMatches::const_iterator j = matches_.begin();
+           (j != matches_.end()) && !found_duplicate; ++j) {
+        if (j->keyword == i->first->keyword())
+          found_duplicate = true;
+      }

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

Nit: Use std::find_if() with a lambda instead of this loop.

Alternately you could sort/unique/erase on a dupe-containing vector but that's
probably going to be much more annoying here.

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

Done.
Yes, and more expensive.  For short inputs such as "w", there may be a ton of
matches.  We don't have to add them all then unique them all just to get the top
X.  Stuck with the find_if.

+      if (!found_duplicate) {
+        matches_.push_back(CreateAutocompleteMatch(
+            i->first, i->second, input, keyword.length(), remaining_input,
+            false, -1));
+      }
     }
   }
 }
 
 void KeywordProvider::Stop(bool clear_cached_results,
                            bool due_to_user_inactivity) {
   done_ = true;
   // Only end an extension's request if the user did something to explicitly
   // cancel it; mere inactivity shouldn't terminate long-running extension
   // operations since the user likely explicitly requested them.
@@ skipping 12 matching lines @@
     return false;
 
   *keyword = TemplateURLService::CleanUserInputKeyword(
       SplitKeywordFromInput(input.text(), true, remaining_input));
   return !keyword->empty();
 }
 
 // static
 int KeywordProvider::CalculateRelevance(metrics::OmniboxInputType::Type type,
                                         bool complete,
+                                        bool nearly_complete,
                                         bool supports_replacement,
                                         bool prefer_keyword,
                                         bool allow_exact_keyword_match) {
   // This function is responsible for scoring suggestions of keywords
   // themselves and the suggestion of the verbatim query on an
   // extension keyword.  SearchProvider::CalculateRelevanceForKeywordVerbatim()
   // scores verbatim query suggestions for non-extension keywords.
-  // These two functions are currently in sync, but there's no reason
-  // we couldn't decide in the future to score verbatim matches
+  // These two functions are currently in sync except for the code at the
+  // beginning for this function that handles scoring not-fully-typed keywords.
+  // (SearchProvider does not make such suggestions and so has no need to
+  // score them.)  Other than that, they're currently in sync.  There's no
+  // reason we couldn't decide in the future to score verbatim matches
   // differently for extension and non-extension keywords.  If you
   // make such a change, however, you should update this comment to
   // describe it, so it's clear why the functions diverge.

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

Instead of this long comment about what's in sync and why, why not just do the
incomplete matching part and then call the other scoring function for the other
cases?  Then you can eliminate the whole last 2/3 of this comment.

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

Done.  Now search_provider.{cc,h} is part of this changelist as well.

-  if (!complete)
+  if (!complete) {
+    const int nearly_complete_score =
+        OmniboxFieldTrial::KeywordScoreForNearlyCompleteMatch();
+    // If we have a special score to apply for nearly-complete matches, do so.
+    if (nearly_complete && (nearly_complete_score > -1))
+      return nearly_complete_score;
     return (type == metrics::OmniboxInputType::URL) ? 700 : 450;
+  }
   if (!supports_replacement || (allow_exact_keyword_match && prefer_keyword))
     return 1500;
   return (allow_exact_keyword_match &&
           (type == metrics::OmniboxInputType::QUERY)) ?
       1450 : 1100;
 }
 
 AutocompleteMatch KeywordProvider::CreateAutocompleteMatch(
     const TemplateURL* template_url,
+    const size_t effective_keyword_length,
     const AutocompleteInput& input,
     size_t prefix_length,
     const base::string16& remaining_input,
     bool allowed_to_be_default_match,
     int relevance) {
   DCHECK(template_url);
   const bool supports_replacement =
       template_url->url_ref().SupportsReplacement(
           GetTemplateURLService()->search_terms_data());
 
   // Create an edit entry of "[keyword] [remaining input]".  This is helpful
   // even when [remaining input] is empty, as the user can select the popup
   // choice and immediately begin typing in query input.
   const base::string16& keyword = template_url->keyword();
   const bool keyword_complete = (prefix_length == keyword.length());
+  const bool nearly_complete = (prefix_length >= effective_keyword_length);
   if (relevance < 0) {
     relevance =
-        CalculateRelevance(input.type(), keyword_complete,
+        CalculateRelevance(input.type(), keyword_complete, nearly_complete,
                            // When the user wants keyword matches to take
                            // preference, score them highly regardless of
                            // whether the input provides query text.
                            supports_replacement, input.prefer_keyword(),
                            input.allow_exact_keyword_match());
   }
   AutocompleteMatch match(this, relevance, false,
       supports_replacement ? AutocompleteMatchType::SEARCH_OTHER_ENGINE :
                              AutocompleteMatchType::HISTORY_KEYWORD);
   match.allowed_to_be_default_match = allowed_to_be_default_match;
@@ skipping 71 matching lines @@
         ACMatchClassification::NONE, &match->contents_class);
   }
 }
 
 TemplateURLService* KeywordProvider::GetTemplateURLService() const {
   // Make sure the model is loaded. This is cheap and quickly bails out if
   // the model is already loaded.
   model_->Load();
   return model_;
 }