Optimize shortcuts provider

components/omnibox/browser/autocomplete_result.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/autocomplete_result.h"
 
 #include <algorithm>
 #include <iterator>
 
 #include "base/command_line.h"
 #include "base/logging.h"
 #include "base/strings/utf_string_conversions.h"
 #include "components/metrics/proto/omnibox_event.pb.h"
 #include "components/metrics/proto/omnibox_input_type.pb.h"
 #include "components/omnibox/browser/autocomplete_input.h"
 #include "components/omnibox/browser/autocomplete_match.h"
 #include "components/omnibox/browser/autocomplete_provider.h"
+#include "components/omnibox/browser/match_compare.h"
 #include "components/omnibox/browser/omnibox_field_trial.h"
 #include "components/omnibox/browser/omnibox_switches.h"
 #include "components/search/search.h"
 #include "components/url_formatter/url_fixer.h"
 
-using metrics::OmniboxEventProto;
-
-namespace {
-
-// This class implements a special version of AutocompleteMatch::MoreRelevant
-// that allows matches of particular types to be demoted in AutocompleteResult.
-class CompareWithDemoteByType {
- public:
-  CompareWithDemoteByType(
-      OmniboxEventProto::PageClassification current_page_classification);
-
-  // Returns the relevance score of |match| demoted appropriately by
-  // |demotions_by_type_|.
-  int GetDemotedRelevance(const AutocompleteMatch& match);
-
-  // Comparison function.
-  bool operator()(const AutocompleteMatch& elem1,
-                  const AutocompleteMatch& elem2);
-
- private:
-  OmniboxFieldTrial::DemotionMultipliers demotions_;
-};
-
-CompareWithDemoteByType::CompareWithDemoteByType(
-    OmniboxEventProto::PageClassification current_page_classification) {
-  OmniboxFieldTrial::GetDemotionsByType(current_page_classification,
-                                        &demotions_);
-}
-
-int CompareWithDemoteByType::GetDemotedRelevance(
-    const AutocompleteMatch& match) {
-  OmniboxFieldTrial::DemotionMultipliers::const_iterator demotion_it =
-      demotions_.find(match.type);
-  return (demotion_it == demotions_.end()) ?
-      match.relevance : (match.relevance * demotion_it->second);
-}
-
-bool CompareWithDemoteByType::operator()(const AutocompleteMatch& elem1,
-                                         const AutocompleteMatch& elem2) {
-  // Compute demoted relevance scores for each match.
-  const int demoted_relevance1 = GetDemotedRelevance(elem1);
-  const int demoted_relevance2 = GetDemotedRelevance(elem2);
-  // For equal-relevance matches, we sort alphabetically, so that providers
-  // who return multiple elements at the same priority get a "stable" sort
-  // across multiple updates.
-  return (demoted_relevance1 == demoted_relevance2) ?
-      (elem1.contents < elem2.contents) :
-      (demoted_relevance1 > demoted_relevance2);
-}
-
-class DestinationSort {
- public:
-  DestinationSort(
-      OmniboxEventProto::PageClassification current_page_classification);
-  bool operator()(const AutocompleteMatch& elem1,
-                  const AutocompleteMatch& elem2);
-
- private:
-  CompareWithDemoteByType demote_by_type_;
-};
-
-DestinationSort::DestinationSort(
-    OmniboxEventProto::PageClassification current_page_classification) :
-    demote_by_type_(current_page_classification) {}
-
-bool DestinationSort::operator()(const AutocompleteMatch& elem1,
-                                 const AutocompleteMatch& elem2) {
-  // Sort identical destination_urls together.  Place the most relevant matches
-  // first, so that when we call std::unique(), these are the ones that get
-  // preserved.
-  if (AutocompleteMatch::DestinationsEqual(elem1, elem2) ||
-      (elem1.stripped_destination_url.is_empty() &&
-       elem2.stripped_destination_url.is_empty())) {
-    return demote_by_type_(elem1, elem2);
-  }
-  return elem1.stripped_destination_url < elem2.stripped_destination_url;
-}
-
-};  // namespace
-
 // static
 const size_t AutocompleteResult::kMaxMatches = 6;
 
 void AutocompleteResult::Selection::Clear() {
   destination_url = GURL();
   provider_affinity = NULL;
   is_history_what_you_typed_match = false;
 }
 
 AutocompleteResult::AutocompleteResult() {
@@ skipping 87 matching lines @@
   default_match_ = end();
   alternate_nav_url_ = GURL();
 }
 
 void AutocompleteResult::SortAndCull(
     const AutocompleteInput& input,
     TemplateURLService* template_url_service) {
   for (ACMatches::iterator i(matches_.begin()); i != matches_.end(); ++i)
     i->ComputeStrippedDestinationURL(input, template_url_service);
 
-  DedupMatchesByDestination(input.current_page_classification(), true,
-                            &matches_);
+  SortAndDedupMatches(input.current_page_classification(), &matches_);
 
   // Sort and trim to the most relevant kMaxMatches matches.
   size_t max_num_matches = std::min(kMaxMatches, matches_.size());
-  CompareWithDemoteByType comparing_object(input.current_page_classification());
+  CompareWithDemoteByType<AutocompleteMatch> comparing_object(
+      input.current_page_classification());
   std::sort(matches_.begin(), matches_.end(), comparing_object);
   if (!matches_.empty() && !matches_.begin()->allowed_to_be_default_match) {
     // Top match is not allowed to be the default match.  Find the most
     // relevant legal match and shift it to the front.
     for (AutocompleteResult::iterator it = matches_.begin() + 1;
          it != matches_.end(); ++it) {
       if (it->allowed_to_be_default_match) {
         std::rotate(matches_.begin(), it, it + 1);
         break;
       }
@@ skipping 133 matching lines @@
 GURL AutocompleteResult::ComputeAlternateNavUrl(
     const AutocompleteInput& input,
     const AutocompleteMatch& match) {
   return ((input.type() == metrics::OmniboxInputType::UNKNOWN) &&
           (AutocompleteMatch::IsSearchType(match.type)) &&
           (match.transition != ui::PAGE_TRANSITION_KEYWORD) &&
           (input.canonicalized_url() != match.destination_url)) ?
       input.canonicalized_url() : GURL();
 }
 
-void AutocompleteResult::DedupMatchesByDestination(
-      OmniboxEventProto::PageClassification page_classification,
-      bool set_duplicate_matches,
-      ACMatches* matches) {
-  DestinationSort destination_sort(page_classification);
+void AutocompleteResult::SortAndDedupMatches(
+    metrics::OmniboxEventProto::PageClassification page_classification,
+    ACMatches* matches) {
   // Sort matches such that duplicate matches are consecutive.
-  std::sort(matches->begin(), matches->end(), destination_sort);
+  std::sort(matches->begin(), matches->end(),
+            DestinationSort<AutocompleteMatch>(page_classification));
 
-  if (set_duplicate_matches) {
-    // Set duplicate_matches for the first match before erasing duplicate
-    // matches.
-    for (ACMatches::iterator i(matches->begin()); i != matches->end(); ++i) {
-      for (int j = 1; (i + j != matches->end()) &&
-               AutocompleteMatch::DestinationsEqual(*i, *(i + j)); ++j) {
-        AutocompleteMatch& dup_match(*(i + j));
-        i->duplicate_matches.insert(i->duplicate_matches.end(),
-                                    dup_match.duplicate_matches.begin(),
-                                    dup_match.duplicate_matches.end());
-        dup_match.duplicate_matches.clear();
-        i->duplicate_matches.push_back(dup_match);
-      }
+  // Set duplicate_matches for the first match before erasing duplicate
+  // matches.
+  for (ACMatches::iterator i(matches->begin()); i != matches->end(); ++i) {
+    for (int j = 1; (i + j != matches->end()) &&
+                    AutocompleteMatch::DestinationsEqual(*i, *(i + j));
+         ++j) {
+      AutocompleteMatch& dup_match(*(i + j));
+      i->duplicate_matches.insert(i->duplicate_matches.end(),
+                                  dup_match.duplicate_matches.begin(),
+                                  dup_match.duplicate_matches.end());
+      dup_match.duplicate_matches.clear();
+      i->duplicate_matches.push_back(dup_match);
     }
   }
 
   // Erase duplicate matches.
   matches->erase(std::unique(matches->begin(), matches->end(),
                              &AutocompleteMatch::DestinationsEqual),
                  matches->end());
 }
 
 void AutocompleteResult::CopyFrom(const AutocompleteResult& rhs) {
@@ skipping 19 matching lines @@
 bool AutocompleteResult::HasMatchByDestination(const AutocompleteMatch& match,
                                                const ACMatches& matches) {
   for (ACMatches::const_iterator i(matches.begin()); i != matches.end(); ++i) {
     if (i->destination_url == match.destination_url)
       return true;
   }
   return false;
 }
 
 void AutocompleteResult::MergeMatchesByProvider(
-    OmniboxEventProto::PageClassification page_classification,
+    metrics::OmniboxEventProto::PageClassification page_classification,
     const ACMatches& old_matches,
     const ACMatches& new_matches) {
   if (new_matches.size() >= old_matches.size())
     return;
 
   // Prevent old matches from this provider from outranking new ones and
   // becoming the default match by capping old matches' scores to be less than
   // the highest-scoring allowed-to-be-default match from this provider.
   ACMatches::const_iterator i = std::find_if(
       new_matches.begin(), new_matches.end(),
@@ skipping 22 matching lines @@
        i != old_matches.rend() && delta > 0; ++i) {
     if (!HasMatchByDestination(*i, new_matches)) {
       AutocompleteMatch match = *i;
       match.relevance = std::min(max_relevance, match.relevance);
       match.from_previous = true;
       matches_.push_back(match);
       delta--;
     }
   }
 }