Optimize shortcuts provider

components/omnibox/browser/shortcuts_provider.cc

 // Copyright (c) 2012 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/shortcuts_provider.h"
 
 #include <stddef.h>
 
 #include <algorithm>
 #include <cmath>
@@ skipping 10 matching lines @@
 #include "base/time/time.h"
 #include "base/trace_event/trace_event.h"
 #include "components/history/core/browser/history_service.h"
 #include "components/metrics/proto/omnibox_input_type.pb.h"
 #include "components/omnibox/browser/autocomplete_i18n.h"
 #include "components/omnibox/browser/autocomplete_input.h"
 #include "components/omnibox/browser/autocomplete_match.h"
 #include "components/omnibox/browser/autocomplete_provider_client.h"
 #include "components/omnibox/browser/autocomplete_result.h"
 #include "components/omnibox/browser/history_provider.h"
+#include "components/omnibox/browser/match_compare.h"
 #include "components/omnibox/browser/omnibox_field_trial.h"
+#include "components/omnibox/browser/shortcut_match.h"
 #include "components/omnibox/browser/url_prefix.h"
 #include "components/prefs/pref_service.h"
 #include "components/url_formatter/url_fixer.h"
 #include "url/third_party/mozilla/url_parse.h"
 
 namespace {
 
 class DestinationURLEqualsURL {
  public:
   explicit DestinationURLEqualsURL(const GURL& url) : url_(url) {}
@@ skipping 89 matching lines @@
   // completely match the search term.
   base::string16 term_string(base::i18n::ToLower(input.text()));
   DCHECK(!term_string.empty());
 
   int max_relevance;
   if (!OmniboxFieldTrial::ShortcutsScoringMaxRelevance(
           input.current_page_classification(), &max_relevance))
     max_relevance = kShortcutsProviderDefaultMaxRelevance;
   TemplateURLService* template_url_service = client_->GetTemplateURLService();
   const base::string16 fixed_up_input(FixupUserInput(input).second);
+
+  ShortcutMatches shortcut_matches;
   for (ShortcutsBackend::ShortcutMap::const_iterator it =
            FindFirstMatch(term_string, backend.get());
        it != backend->shortcuts_map().end() &&
            base::StartsWith(it->first, term_string,
                             base::CompareCase::SENSITIVE);
        ++it) {
     // Don't return shortcuts with zero relevance.
     int relevance = CalculateScore(term_string, it->second, max_relevance);
     if (relevance) {
-      matches_.push_back(
-          ShortcutToACMatch(it->second, relevance, input, fixed_up_input));
-      matches_.back().ComputeStrippedDestinationURL(
-          input, client_->GetAcceptLanguages(), template_url_service);
+      const ShortcutsDatabase::Shortcut& shortcut = it->second;
+      GURL stripped_destination_url(AutocompleteMatch::GURLToStrippedGURL(
+          shortcut.match_core.destination_url,
+          input,
+          languages_,
+          template_url_service,
+          shortcut.match_core.keyword));
+      shortcut_matches.push_back(ShortcutMatch(relevance,
+                                               stripped_destination_url,
+                                               &(it->second)));

[Peter Kasting, 2016/04/12 23:29:50]

Nit: Shorter:

      shortcut_matches.push_back(
          ShortcutMatch(relevance, stripped_destination_url, &(it->second)));

[Alexander Yashkin, 2016/04/13 09:29:36]

Done.

     }
   }
   // Remove duplicates.  This is important because it's common to have multiple
   // shortcuts pointing to the same URL, e.g., ma, mai, and mail all pointing
   // to mail.google.com, so typing "m" will return them all.  If we then simply
   // clamp to kMaxMatches and let the AutocompleteResult take care of
   // collapsing the duplicates, we'll effectively only be returning one match,
   // instead of several possibilities.
   //
   // Note that while removing duplicates, we don't populate a match's
   // |duplicate_matches| field--duplicates don't need to be preserved in the
   // matches because they are only used for deletions, and this provider
   // deletes matches based on the URL.
-  AutocompleteResult::DedupMatchesByDestination(
-      input.current_page_classification(), false, &matches_);
+  DedupShortcutMatchesByDestination(input.current_page_classification(),
+                                    &shortcut_matches);

[Peter Kasting, 2016/04/12 23:29:50]

After removing the call to AutocompleteResult::DedupMatchesByDestination(), that
function's lone non-test caller passes |true| for the second argument, so that
function should be simplified to eliminate the second arg (assuming it's always
true) and the unittest location that calls it updated to not rely on the |false|
behavior.

[Alexander Yashkin, 2016/04/13 09:29:36]

Done.

   // Find best matches.
   std::partial_sort(
-      matches_.begin(),
-      matches_.begin() +
-          std::min(AutocompleteProvider::kMaxMatches, matches_.size()),
-      matches_.end(), &AutocompleteMatch::MoreRelevant);
-  if (matches_.size() > AutocompleteProvider::kMaxMatches) {
-    matches_.erase(matches_.begin() + AutocompleteProvider::kMaxMatches,
-                   matches_.end());
+      shortcut_matches.begin(),
+      shortcut_matches.begin() +
+          std::min(AutocompleteProvider::kMaxMatches, shortcut_matches.size()),
+      shortcut_matches.end(),
+      ShortcutMatch::MoreRelevant);
+  if (shortcut_matches.size() > AutocompleteProvider::kMaxMatches) {
+    shortcut_matches.erase(
+        shortcut_matches.begin() + AutocompleteProvider::kMaxMatches,
+        shortcut_matches.end());
   }
-  // Guarantee that all scores are decreasing (but do not assign any scores
-  // below 1).
-  for (ACMatches::iterator it = matches_.begin(); it != matches_.end(); ++it) {
-    max_relevance = std::min(max_relevance, it->relevance);
-    it->relevance = max_relevance;
+  // Create and initialize autocomplete matches from shortcut matches.
+  // Also guarantee that all relevance scores are decreasing
+  // (but do not assign any scores below 1).
+  WordMap terms_map(CreateWordMapForString(term_string));
+  matches_.reserve(shortcut_matches.size());
+  for (ShortcutMatch& match : shortcut_matches) {
+    max_relevance = std::min(max_relevance, match.relevance);
+    match.relevance = max_relevance;
     if (max_relevance > 1)
       --max_relevance;
+    matches_.push_back(ShortcutMatchToACMatch(match, input, fixed_up_input,
+                                              term_string, terms_map));
   }
 }
 
-AutocompleteMatch ShortcutsProvider::ShortcutToACMatch(
-    const ShortcutsDatabase::Shortcut& shortcut,
-    int relevance,
+AutocompleteMatch ShortcutsProvider::ShortcutMatchToACMatch(
+    const ShortcutMatch& shortcut_match,
     const AutocompleteInput& input,
-    const base::string16& fixed_up_input_text) {
+    const base::string16& fixed_up_input_text,
+    const base::string16 term_string,
+    const WordMap& terms_map) {
   DCHECK(!input.text().empty());
+  const ShortcutsDatabase::Shortcut& shortcut = *shortcut_match.shortcut;
   AutocompleteMatch match;
   match.provider = this;
-  match.relevance = relevance;
+  match.relevance = shortcut_match.relevance;
   match.deletable = true;
   match.fill_into_edit = shortcut.match_core.fill_into_edit;
   match.destination_url = shortcut.match_core.destination_url;
   DCHECK(match.destination_url.is_valid());
   match.contents = shortcut.match_core.contents;
   match.contents_class = AutocompleteMatch::ClassificationsFromString(
       shortcut.match_core.contents_class);
   match.description = shortcut.match_core.description;
   match.description_class = AutocompleteMatch::ClassificationsFromString(
       shortcut.match_core.description_class);
   match.transition = ui::PageTransitionFromInt(shortcut.match_core.transition);
   match.type = static_cast<AutocompleteMatch::Type>(shortcut.match_core.type);
   match.keyword = shortcut.match_core.keyword;
+  match.stripped_destination_url = shortcut_match.stripped_destination_url;
   match.RecordAdditionalInfo("number of hits", shortcut.number_of_hits);
   match.RecordAdditionalInfo("last access time", shortcut.last_access_time);
   match.RecordAdditionalInfo("original input text",
                              base::UTF16ToUTF8(shortcut.text));
 
   // Set |inline_autocompletion| and |allowed_to_be_default_match| if possible.
   // If the match is a search query this is easy: simply check whether the
   // user text is a prefix of the query.  If the match is a navigation, we
   // assume the fill_into_edit looks something like a URL, so we use
   // URLPrefix::GetInlineAutocompleteOffset() to try and strip off any prefixes
@@ skipping 19 matching lines @@
             input.text(), fixed_up_input_text, true, match.fill_into_edit);
     if (inline_autocomplete_offset != base::string16::npos) {
       match.inline_autocompletion =
           match.fill_into_edit.substr(inline_autocomplete_offset);
       match.allowed_to_be_default_match =
           !HistoryProvider::PreventInlineAutocomplete(input) ||
           match.inline_autocompletion.empty();
     }
   }
   match.EnsureUWYTIsAllowedToBeDefault(input,
-                                       client_->GetAcceptLanguages(),
+                                       languages_,
                                        client_->GetTemplateURLService());
 
   // Try to mark pieces of the contents and description as matches if they
   // appear in |input.text()|.
-  const base::string16 term_string = base::i18n::ToLower(input.text());
-  WordMap terms_map(CreateWordMapForString(term_string));
   if (!terms_map.empty()) {
     match.contents_class = ClassifyAllMatchesInString(
         term_string, terms_map, match.contents, match.contents_class);
     match.description_class = ClassifyAllMatchesInString(
         term_string, terms_map, match.description, match.description_class);
   }
   return match;
 }
 
 // static
@@ skipping 149 matching lines @@
   const double kMaxDecaySpeedDivisor = 5.0;
   const double kNumUsesPerDecaySpeedDivisorIncrement = 5.0;
   double decay_divisor = std::min(
       kMaxDecaySpeedDivisor,
       (shortcut.number_of_hits + kNumUsesPerDecaySpeedDivisorIncrement - 1) /
           kNumUsesPerDecaySpeedDivisorIncrement);
 
   return static_cast<int>((base_score / exp(decay_exponent / decay_divisor)) +
                           0.5);
 }
+
+// static
+void ShortcutsProvider::DedupShortcutMatchesByDestination(
+    OmniboxEventProto::PageClassification page_classification,
+    std::vector<ShortcutMatch>* matches) {
+  DestinationSort<ShortcutMatch> destination_sort(page_classification);

[Peter Kasting, 2016/04/12 23:29:50]

Nit: Seems like we could just inline this into the sort() call.

[Alexander Yashkin, 2016/04/13 09:29:36]

Done.

+  // Sort matches such that duplicate matches are consecutive.
+  std::sort(matches->begin(), matches->end(), destination_sort);
+
+  // Erase duplicate matches.
+  matches->erase(
+      std::unique(matches->begin(),
+                  matches->end(),
+                  &ShortcutMatch::DestinationsEqual),
+                  matches->end());
+}