Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(101)

Side by Side Diff: components/omnibox/browser/autocomplete_result.cc

Issue 1877833002: Optimize shortcuts provider (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Reverted rename of ShortcutMatchToACMatch to ShortcutToACMatch Created 4 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
1 // Copyright 2014 The Chromium Authors. All rights reserved. 1 // Copyright 2014 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #include "components/omnibox/browser/autocomplete_result.h" 5 #include "components/omnibox/browser/autocomplete_result.h"
6 6
7 #include <algorithm> 7 #include <algorithm>
8 #include <iterator> 8 #include <iterator>
9 9
10 #include "base/command_line.h" 10 #include "base/command_line.h"
11 #include "base/logging.h" 11 #include "base/logging.h"
12 #include "base/strings/utf_string_conversions.h" 12 #include "base/strings/utf_string_conversions.h"
13 #include "components/metrics/proto/omnibox_event.pb.h" 13 #include "components/metrics/proto/omnibox_event.pb.h"
14 #include "components/metrics/proto/omnibox_input_type.pb.h" 14 #include "components/metrics/proto/omnibox_input_type.pb.h"
15 #include "components/omnibox/browser/autocomplete_input.h" 15 #include "components/omnibox/browser/autocomplete_input.h"
16 #include "components/omnibox/browser/autocomplete_match.h" 16 #include "components/omnibox/browser/autocomplete_match.h"
17 #include "components/omnibox/browser/autocomplete_provider.h" 17 #include "components/omnibox/browser/autocomplete_provider.h"
18 #include "components/omnibox/browser/match_compare.h"
18 #include "components/omnibox/browser/omnibox_field_trial.h" 19 #include "components/omnibox/browser/omnibox_field_trial.h"
19 #include "components/omnibox/browser/omnibox_switches.h" 20 #include "components/omnibox/browser/omnibox_switches.h"
20 #include "components/search/search.h" 21 #include "components/search/search.h"
21 #include "components/url_formatter/url_fixer.h" 22 #include "components/url_formatter/url_fixer.h"
22 23
23 using metrics::OmniboxEventProto;
24
25 namespace {
26
27 // This class implements a special version of AutocompleteMatch::MoreRelevant
28 // that allows matches of particular types to be demoted in AutocompleteResult.
29 class CompareWithDemoteByType {
30 public:
31 CompareWithDemoteByType(
32 OmniboxEventProto::PageClassification current_page_classification);
33
34 // Returns the relevance score of |match| demoted appropriately by
35 // |demotions_by_type_|.
36 int GetDemotedRelevance(const AutocompleteMatch& match);
37
38 // Comparison function.
39 bool operator()(const AutocompleteMatch& elem1,
40 const AutocompleteMatch& elem2);
41
42 private:
43 OmniboxFieldTrial::DemotionMultipliers demotions_;
44 };
45
46 CompareWithDemoteByType::CompareWithDemoteByType(
47 OmniboxEventProto::PageClassification current_page_classification) {
48 OmniboxFieldTrial::GetDemotionsByType(current_page_classification,
49 &demotions_);
50 }
51
52 int CompareWithDemoteByType::GetDemotedRelevance(
53 const AutocompleteMatch& match) {
54 OmniboxFieldTrial::DemotionMultipliers::const_iterator demotion_it =
55 demotions_.find(match.type);
56 return (demotion_it == demotions_.end()) ?
57 match.relevance : (match.relevance * demotion_it->second);
58 }
59
60 bool CompareWithDemoteByType::operator()(const AutocompleteMatch& elem1,
61 const AutocompleteMatch& elem2) {
62 // Compute demoted relevance scores for each match.
63 const int demoted_relevance1 = GetDemotedRelevance(elem1);
64 const int demoted_relevance2 = GetDemotedRelevance(elem2);
65 // For equal-relevance matches, we sort alphabetically, so that providers
66 // who return multiple elements at the same priority get a "stable" sort
67 // across multiple updates.
68 return (demoted_relevance1 == demoted_relevance2) ?
69 (elem1.contents < elem2.contents) :
70 (demoted_relevance1 > demoted_relevance2);
71 }
72
73 class DestinationSort {
74 public:
75 DestinationSort(
76 OmniboxEventProto::PageClassification current_page_classification);
77 bool operator()(const AutocompleteMatch& elem1,
78 const AutocompleteMatch& elem2);
79
80 private:
81 CompareWithDemoteByType demote_by_type_;
82 };
83
84 DestinationSort::DestinationSort(
85 OmniboxEventProto::PageClassification current_page_classification) :
86 demote_by_type_(current_page_classification) {}
87
88 bool DestinationSort::operator()(const AutocompleteMatch& elem1,
89 const AutocompleteMatch& elem2) {
90 // Sort identical destination_urls together. Place the most relevant matches
91 // first, so that when we call std::unique(), these are the ones that get
92 // preserved.
93 if (AutocompleteMatch::DestinationsEqual(elem1, elem2) ||
94 (elem1.stripped_destination_url.is_empty() &&
95 elem2.stripped_destination_url.is_empty())) {
96 return demote_by_type_(elem1, elem2);
97 }
98 return elem1.stripped_destination_url < elem2.stripped_destination_url;
99 }
100
101 }; // namespace
102
103 // static 24 // static
104 const size_t AutocompleteResult::kMaxMatches = 6; 25 const size_t AutocompleteResult::kMaxMatches = 6;
105 26
106 void AutocompleteResult::Selection::Clear() { 27 void AutocompleteResult::Selection::Clear() {
107 destination_url = GURL(); 28 destination_url = GURL();
108 provider_affinity = NULL; 29 provider_affinity = NULL;
109 is_history_what_you_typed_match = false; 30 is_history_what_you_typed_match = false;
110 } 31 }
111 32
112 AutocompleteResult::AutocompleteResult() { 33 AutocompleteResult::AutocompleteResult() {
(...skipping 89 matching lines...) Expand 10 before | Expand all | Expand 10 after
202 alternate_nav_url_ = GURL(); 123 alternate_nav_url_ = GURL();
203 } 124 }
204 125
205 void AutocompleteResult::SortAndCull( 126 void AutocompleteResult::SortAndCull(
206 const AutocompleteInput& input, 127 const AutocompleteInput& input,
207 const std::string& languages, 128 const std::string& languages,
208 TemplateURLService* template_url_service) { 129 TemplateURLService* template_url_service) {
209 for (ACMatches::iterator i(matches_.begin()); i != matches_.end(); ++i) 130 for (ACMatches::iterator i(matches_.begin()); i != matches_.end(); ++i)
210 i->ComputeStrippedDestinationURL(input, languages, template_url_service); 131 i->ComputeStrippedDestinationURL(input, languages, template_url_service);
211 132
212 DedupMatchesByDestination(input.current_page_classification(), true, 133 SortAndDedupMatches(input.current_page_classification(), &matches_);
213 &matches_);
214 134
215 // Sort and trim to the most relevant kMaxMatches matches. 135 // Sort and trim to the most relevant kMaxMatches matches.
216 size_t max_num_matches = std::min(kMaxMatches, matches_.size()); 136 size_t max_num_matches = std::min(kMaxMatches, matches_.size());
217 CompareWithDemoteByType comparing_object(input.current_page_classification()); 137 CompareWithDemoteByType<AutocompleteMatch>
138 comparing_object(input.current_page_classification());
218 std::sort(matches_.begin(), matches_.end(), comparing_object); 139 std::sort(matches_.begin(), matches_.end(), comparing_object);
219 if (!matches_.empty() && !matches_.begin()->allowed_to_be_default_match) { 140 if (!matches_.empty() && !matches_.begin()->allowed_to_be_default_match) {
220 // Top match is not allowed to be the default match. Find the most 141 // Top match is not allowed to be the default match. Find the most
221 // relevant legal match and shift it to the front. 142 // relevant legal match and shift it to the front.
222 for (AutocompleteResult::iterator it = matches_.begin() + 1; 143 for (AutocompleteResult::iterator it = matches_.begin() + 1;
223 it != matches_.end(); ++it) { 144 it != matches_.end(); ++it) {
224 if (it->allowed_to_be_default_match) { 145 if (it->allowed_to_be_default_match) {
225 std::rotate(matches_.begin(), it, it + 1); 146 std::rotate(matches_.begin(), it, it + 1);
226 break; 147 break;
227 } 148 }
(...skipping 133 matching lines...) Expand 10 before | Expand all | Expand 10 after
361 GURL AutocompleteResult::ComputeAlternateNavUrl( 282 GURL AutocompleteResult::ComputeAlternateNavUrl(
362 const AutocompleteInput& input, 283 const AutocompleteInput& input,
363 const AutocompleteMatch& match) { 284 const AutocompleteMatch& match) {
364 return ((input.type() == metrics::OmniboxInputType::UNKNOWN) && 285 return ((input.type() == metrics::OmniboxInputType::UNKNOWN) &&
365 (AutocompleteMatch::IsSearchType(match.type)) && 286 (AutocompleteMatch::IsSearchType(match.type)) &&
366 (match.transition != ui::PAGE_TRANSITION_KEYWORD) && 287 (match.transition != ui::PAGE_TRANSITION_KEYWORD) &&
367 (input.canonicalized_url() != match.destination_url)) ? 288 (input.canonicalized_url() != match.destination_url)) ?
368 input.canonicalized_url() : GURL(); 289 input.canonicalized_url() : GURL();
369 } 290 }
370 291
371 void AutocompleteResult::DedupMatchesByDestination( 292 void AutocompleteResult::SortAndDedupMatches(
372 OmniboxEventProto::PageClassification page_classification, 293 metrics::OmniboxEventProto::PageClassification page_classification,
373 bool set_duplicate_matches,
374 ACMatches* matches) { 294 ACMatches* matches) {
375 DestinationSort destination_sort(page_classification);
376 // Sort matches such that duplicate matches are consecutive. 295 // Sort matches such that duplicate matches are consecutive.
377 std::sort(matches->begin(), matches->end(), destination_sort); 296 std::sort(matches->begin(), matches->end(),
297 DestinationSort<AutocompleteMatch>(page_classification));
378 298
379 if (set_duplicate_matches) { 299 // Set duplicate_matches for the first match before erasing duplicate
380 // Set duplicate_matches for the first match before erasing duplicate 300 // matches.
381 // matches. 301 for (ACMatches::iterator i(matches->begin()); i != matches->end(); ++i) {
382 for (ACMatches::iterator i(matches->begin()); i != matches->end(); ++i) { 302 for (int j = 1; (i + j != matches->end()) &&
383 for (int j = 1; (i + j != matches->end()) && 303 AutocompleteMatch::DestinationsEqual(*i, *(i + j)); ++j) {
384 AutocompleteMatch::DestinationsEqual(*i, *(i + j)); ++j) { 304 AutocompleteMatch& dup_match(*(i + j));
385 AutocompleteMatch& dup_match(*(i + j)); 305 i->duplicate_matches.insert(i->duplicate_matches.end(),
386 i->duplicate_matches.insert(i->duplicate_matches.end(), 306 dup_match.duplicate_matches.begin(),
387 dup_match.duplicate_matches.begin(), 307 dup_match.duplicate_matches.end());
388 dup_match.duplicate_matches.end()); 308 dup_match.duplicate_matches.clear();
389 dup_match.duplicate_matches.clear(); 309 i->duplicate_matches.push_back(dup_match);
390 i->duplicate_matches.push_back(dup_match);
391 }
392 } 310 }
393 } 311 }
394 312
395 // Erase duplicate matches. 313 // Erase duplicate matches.
396 matches->erase(std::unique(matches->begin(), matches->end(), 314 matches->erase(std::unique(matches->begin(), matches->end(),
397 &AutocompleteMatch::DestinationsEqual), 315 &AutocompleteMatch::DestinationsEqual),
398 matches->end()); 316 matches->end());
399 } 317 }
400 318
401 void AutocompleteResult::CopyFrom(const AutocompleteResult& rhs) { 319 void AutocompleteResult::CopyFrom(const AutocompleteResult& rhs) {
(...skipping 19 matching lines...) Expand all
421 bool AutocompleteResult::HasMatchByDestination(const AutocompleteMatch& match, 339 bool AutocompleteResult::HasMatchByDestination(const AutocompleteMatch& match,
422 const ACMatches& matches) { 340 const ACMatches& matches) {
423 for (ACMatches::const_iterator i(matches.begin()); i != matches.end(); ++i) { 341 for (ACMatches::const_iterator i(matches.begin()); i != matches.end(); ++i) {
424 if (i->destination_url == match.destination_url) 342 if (i->destination_url == match.destination_url)
425 return true; 343 return true;
426 } 344 }
427 return false; 345 return false;
428 } 346 }
429 347
430 void AutocompleteResult::MergeMatchesByProvider( 348 void AutocompleteResult::MergeMatchesByProvider(
431 OmniboxEventProto::PageClassification page_classification, 349 metrics::OmniboxEventProto::PageClassification page_classification,
432 const ACMatches& old_matches, 350 const ACMatches& old_matches,
433 const ACMatches& new_matches) { 351 const ACMatches& new_matches) {
434 if (new_matches.size() >= old_matches.size()) 352 if (new_matches.size() >= old_matches.size())
435 return; 353 return;
436 354
437 // Prevent old matches from this provider from outranking new ones and 355 // Prevent old matches from this provider from outranking new ones and
438 // becoming the default match by capping old matches' scores to be less than 356 // becoming the default match by capping old matches' scores to be less than
439 // the highest-scoring allowed-to-be-default match from this provider. 357 // the highest-scoring allowed-to-be-default match from this provider.
440 ACMatches::const_iterator i = std::find_if( 358 ACMatches::const_iterator i = std::find_if(
441 new_matches.begin(), new_matches.end(), 359 new_matches.begin(), new_matches.end(),
(...skipping 22 matching lines...) Expand all
464 i != old_matches.rend() && delta > 0; ++i) { 382 i != old_matches.rend() && delta > 0; ++i) {
465 if (!HasMatchByDestination(*i, new_matches)) { 383 if (!HasMatchByDestination(*i, new_matches)) {
466 AutocompleteMatch match = *i; 384 AutocompleteMatch match = *i;
467 match.relevance = std::min(max_relevance, match.relevance); 385 match.relevance = std::min(max_relevance, match.relevance);
468 match.from_previous = true; 386 match.from_previous = true;
469 matches_.push_back(match); 387 matches_.push_back(match);
470 delta--; 388 delta--;
471 } 389 }
472 } 390 }
473 } 391 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698