OLD | NEW |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 } |
OLD | NEW |