1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "chrome/browser/autocomplete/autocomplete_result.h" 6 7 #include <algorithm> 8 #include <iterator> 9 10 #include "base/logging.h" 11 #include "base/metrics/histogram.h" 12 #include "base/strings/utf_string_conversions.h" 13 #include "chrome/browser/autocomplete/autocomplete_input.h" 14 #include "chrome/browser/autocomplete/autocomplete_match.h" 15 #include "chrome/browser/autocomplete/autocomplete_provider.h" 16 #include "chrome/browser/omnibox/omnibox_field_trial.h" 17 #include "chrome/browser/search/search.h" 18 #include "chrome/common/autocomplete_match_type.h" 19 #include "components/metrics/proto/omnibox_event.pb.h" 20 #include "components/metrics/proto/omnibox_input_type.pb.h" 21 22 using metrics::OmniboxEventProto; 23 24 namespace { 25 26 // This class implements a special version of AutocompleteMatch::MoreRelevant 27 // that allows matches of particular types to be demoted in AutocompleteResult. 28 class CompareWithDemoteByType { 29 public: 30 CompareWithDemoteByType( 31 OmniboxEventProto::PageClassification current_page_classification); 32 33 // Returns the relevance score of |match| demoted appropriately by 34 // |demotions_by_type_|. 35 int GetDemotedRelevance(const AutocompleteMatch& match); 36 37 // Comparison function. 38 bool operator()(const AutocompleteMatch& elem1, 39 const AutocompleteMatch& elem2); 40 41 private: 42 OmniboxFieldTrial::DemotionMultipliers demotions_; 43 }; 44 45 CompareWithDemoteByType::CompareWithDemoteByType( 46 OmniboxEventProto::PageClassification current_page_classification) { 47 OmniboxFieldTrial::GetDemotionsByType(current_page_classification, 48 &demotions_); 49 } 50 51 int CompareWithDemoteByType::GetDemotedRelevance( 52 const AutocompleteMatch& match) { 53 OmniboxFieldTrial::DemotionMultipliers::const_iterator demotion_it = 54 demotions_.find(match.type); 55 return (demotion_it == demotions_.end()) ? 56 match.relevance : (match.relevance * demotion_it->second); 57 } 58 59 bool CompareWithDemoteByType::operator()(const AutocompleteMatch& elem1, 60 const AutocompleteMatch& elem2) { 61 // Compute demoted relevance scores for each match. 62 const int demoted_relevance1 = GetDemotedRelevance(elem1); 63 const int demoted_relevance2 = GetDemotedRelevance(elem2); 64 // For equal-relevance matches, we sort alphabetically, so that providers 65 // who return multiple elements at the same priority get a "stable" sort 66 // across multiple updates. 67 return (demoted_relevance1 == demoted_relevance2) ? 68 (elem1.contents < elem2.contents) : 69 (demoted_relevance1 > demoted_relevance2); 70 } 71 72 class DestinationSort { 73 public: 74 DestinationSort( 75 OmniboxEventProto::PageClassification current_page_classification); 76 bool operator()(const AutocompleteMatch& elem1, 77 const AutocompleteMatch& elem2); 78 79 private: 80 CompareWithDemoteByType demote_by_type_; 81 }; 82 83 DestinationSort::DestinationSort( 84 OmniboxEventProto::PageClassification current_page_classification) : 85 demote_by_type_(current_page_classification) {} 86 87 bool DestinationSort::operator()(const AutocompleteMatch& elem1, 88 const AutocompleteMatch& elem2) { 89 // Sort identical destination_urls together. Place the most relevant matches 90 // first, so that when we call std::unique(), these are the ones that get 91 // preserved. 92 if (AutocompleteMatch::DestinationsEqual(elem1, elem2) || 93 (elem1.stripped_destination_url.is_empty() && 94 elem2.stripped_destination_url.is_empty())) { 95 return demote_by_type_(elem1, elem2); 96 } 97 return elem1.stripped_destination_url < elem2.stripped_destination_url; 98 } 99 100 // Returns true if |match| is allowed to the default match taking into account 101 // whether we're supposed to (and able to) demote all matches with inline 102 // autocompletions. 103 bool AllowedToBeDefaultMatchAccountingForDisableInliningExperiment( 104 const AutocompleteMatch& match, 105 const bool has_legal_default_match_without_completion) { 106 return match.allowed_to_be_default_match && 107 (!OmniboxFieldTrial::DisableInlining() || 108 !has_legal_default_match_without_completion || 109 match.inline_autocompletion.empty()); 110 } 111 112 }; // namespace 113 114 // static 115 const size_t AutocompleteResult::kMaxMatches = 6; 116 117 void AutocompleteResult::Selection::Clear() { 118 destination_url = GURL(); 119 provider_affinity = NULL; 120 is_history_what_you_typed_match = false; 121 } 122 123 AutocompleteResult::AutocompleteResult() { 124 // Reserve space for the max number of matches we'll show. 125 matches_.reserve(kMaxMatches); 126 127 // It's probably safe to do this in the initializer list, but there's little 128 // penalty to doing it here and it ensures our object is fully constructed 129 // before calling member functions. 130 default_match_ = end(); 131 } 132 133 AutocompleteResult::~AutocompleteResult() {} 134 135 void AutocompleteResult::CopyOldMatches(const AutocompleteInput& input, 136 const AutocompleteResult& old_matches, 137 Profile* profile) { 138 if (old_matches.empty()) 139 return; 140 141 if (empty()) { 142 // If we've got no matches we can copy everything from the last result. 143 CopyFrom(old_matches); 144 for (ACMatches::iterator i(begin()); i != end(); ++i) 145 i->from_previous = true; 146 return; 147 } 148 149 // In hopes of providing a stable popup we try to keep the number of matches 150 // per provider consistent. Other schemes (such as blindly copying the most 151 // relevant matches) typically result in many successive 'What You Typed' 152 // results filling all the matches, which looks awful. 153 // 154 // Instead of starting with the current matches and then adding old matches 155 // until we hit our overall limit, we copy enough old matches so that each 156 // provider has at least as many as before, and then use SortAndCull() to 157 // clamp globally. This way, old high-relevance matches will starve new 158 // low-relevance matches, under the assumption that the new matches will 159 // ultimately be similar. If the assumption holds, this prevents seeing the 160 // new low-relevance match appear and then quickly get pushed off the bottom; 161 // if it doesn't, then once the providers are done and we expire the old 162 // matches, the new ones will all become visible, so we won't have lost 163 // anything permanently. 164 ProviderToMatches matches_per_provider, old_matches_per_provider; 165 BuildProviderToMatches(&matches_per_provider); 166 old_matches.BuildProviderToMatches(&old_matches_per_provider); 167 for (ProviderToMatches::const_iterator i(old_matches_per_provider.begin()); 168 i != old_matches_per_provider.end(); ++i) { 169 MergeMatchesByProvider(input.current_page_classification(), 170 i->second, matches_per_provider[i->first]); 171 } 172 173 SortAndCull(input, profile); 174 } 175 176 void AutocompleteResult::AppendMatches(const ACMatches& matches) { 177 #ifndef NDEBUG 178 for (ACMatches::const_iterator i(matches.begin()); i != matches.end(); ++i) { 179 DCHECK_EQ(AutocompleteMatch::SanitizeString(i->contents), i->contents); 180 DCHECK_EQ(AutocompleteMatch::SanitizeString(i->description), 181 i->description); 182 } 183 #endif 184 std::copy(matches.begin(), matches.end(), std::back_inserter(matches_)); 185 default_match_ = end(); 186 alternate_nav_url_ = GURL(); 187 } 188 189 void AutocompleteResult::SortAndCull(const AutocompleteInput& input, 190 Profile* profile) { 191 for (ACMatches::iterator i(matches_.begin()); i != matches_.end(); ++i) 192 i->ComputeStrippedDestinationURL(profile); 193 194 DedupMatchesByDestination(input.current_page_classification(), true, 195 &matches_); 196 197 // If the result set has at least one legal default match without an inline 198 // autocompletion, then in the disable inlining experiment it will be okay 199 // to demote all matches with inline autocompletions. On the other hand, if 200 // the experiment is active but there is no legal match without an inline 201 // autocompletion, then we'll pretend the experiment is not active and not 202 // demote the matches with an inline autocompletion. In other words, an 203 // alternate name for this variable is 204 // allowed_to_demote_matches_with_inline_autocompletion. 205 bool has_legal_default_match_without_completion = false; 206 for (AutocompleteResult::iterator it = matches_.begin(); 207 (it != matches_.end()) && !has_legal_default_match_without_completion; 208 ++it) { 209 if (it->allowed_to_be_default_match && it->inline_autocompletion.empty()) 210 has_legal_default_match_without_completion = true; 211 } 212 UMA_HISTOGRAM_BOOLEAN("Omnibox.HasLegalDefaultMatchWithoutCompletion", 213 has_legal_default_match_without_completion); 214 215 // Sort and trim to the most relevant kMaxMatches matches. 216 size_t max_num_matches = std::min(kMaxMatches, matches_.size()); 217 CompareWithDemoteByType comparing_object(input.current_page_classification()); 218 std::sort(matches_.begin(), matches_.end(), comparing_object); 219 if (!matches_.empty() && 220 !AllowedToBeDefaultMatchAccountingForDisableInliningExperiment( 221 *matches_.begin(), has_legal_default_match_without_completion)) { 222 // Top match is not allowed to be the default match. Find the most 223 // relevant legal match and shift it to the front. 224 for (AutocompleteResult::iterator it = matches_.begin() + 1; 225 it != matches_.end(); ++it) { 226 if (AllowedToBeDefaultMatchAccountingForDisableInliningExperiment( 227 *it, has_legal_default_match_without_completion)) { 228 std::rotate(matches_.begin(), it, it + 1); 229 break; 230 } 231 } 232 } 233 // In the process of trimming, drop all matches with a demoted relevance 234 // score of 0. 235 size_t num_matches; 236 for (num_matches = 0u; (num_matches < max_num_matches) && 237 (comparing_object.GetDemotedRelevance(*match_at(num_matches)) > 0); 238 ++num_matches) {} 239 matches_.resize(num_matches); 240 241 default_match_ = matches_.begin(); 242 243 if (default_match_ != matches_.end()) { 244 const base::string16 debug_info = 245 base::ASCIIToUTF16("fill_into_edit=") + 246 default_match_->fill_into_edit + 247 base::ASCIIToUTF16(", provider=") + 248 ((default_match_->provider != NULL) 249 ? base::ASCIIToUTF16(default_match_->provider->GetName()) 250 : base::string16()) + 251 base::ASCIIToUTF16(", input=") + 252 input.text(); 253 DCHECK(default_match_->allowed_to_be_default_match) << debug_info; 254 // If the default match is valid (i.e., not a prompt/placeholder), make 255 // sure the type of destination is what the user would expect given the 256 // input. 257 if (default_match_->destination_url.is_valid()) { 258 // We shouldn't get query matches for URL inputs, or non-query matches 259 // for query inputs. 260 if (AutocompleteMatch::IsSearchType(default_match_->type)) { 261 DCHECK_NE(metrics::OmniboxInputType::URL, input.type()) << debug_info; 262 } else { 263 DCHECK_NE(metrics::OmniboxInputType::FORCED_QUERY, input.type()) 264 << debug_info; 265 } 266 } 267 } 268 269 // Set the alternate nav URL. 270 alternate_nav_url_ = (default_match_ == matches_.end()) ? 271 GURL() : ComputeAlternateNavUrl(input, *default_match_); 272 } 273 274 bool AutocompleteResult::HasCopiedMatches() const { 275 for (ACMatches::const_iterator i(begin()); i != end(); ++i) { 276 if (i->from_previous) 277 return true; 278 } 279 return false; 280 } 281 282 size_t AutocompleteResult::size() const { 283 return matches_.size(); 284 } 285 286 bool AutocompleteResult::empty() const { 287 return matches_.empty(); 288 } 289 290 AutocompleteResult::const_iterator AutocompleteResult::begin() const { 291 return matches_.begin(); 292 } 293 294 AutocompleteResult::iterator AutocompleteResult::begin() { 295 return matches_.begin(); 296 } 297 298 AutocompleteResult::const_iterator AutocompleteResult::end() const { 299 return matches_.end(); 300 } 301 302 AutocompleteResult::iterator AutocompleteResult::end() { 303 return matches_.end(); 304 } 305 306 // Returns the match at the given index. 307 const AutocompleteMatch& AutocompleteResult::match_at(size_t index) const { 308 DCHECK_LT(index, matches_.size()); 309 return matches_[index]; 310 } 311 312 AutocompleteMatch* AutocompleteResult::match_at(size_t index) { 313 DCHECK_LT(index, matches_.size()); 314 return &matches_[index]; 315 } 316 317 bool AutocompleteResult::ShouldHideTopMatch() const { 318 return chrome::ShouldHideTopVerbatimMatch() && 319 TopMatchIsStandaloneVerbatimMatch(); 320 } 321 322 bool AutocompleteResult::TopMatchIsStandaloneVerbatimMatch() const { 323 if (empty() || !match_at(0).IsVerbatimType()) 324 return false; 325 326 // Skip any copied matches, under the assumption that they'll be expired and 327 // disappear. We don't want this disappearance to cause the visibility of the 328 // top match to change. 329 for (const_iterator i(begin() + 1); i != end(); ++i) { 330 if (!i->from_previous) 331 return !i->IsVerbatimType(); 332 } 333 return true; 334 } 335 336 void AutocompleteResult::Reset() { 337 matches_.clear(); 338 default_match_ = end(); 339 } 340 341 void AutocompleteResult::Swap(AutocompleteResult* other) { 342 const size_t default_match_offset = default_match_ - begin(); 343 const size_t other_default_match_offset = 344 other->default_match_ - other->begin(); 345 matches_.swap(other->matches_); 346 default_match_ = begin() + other_default_match_offset; 347 other->default_match_ = other->begin() + default_match_offset; 348 alternate_nav_url_.Swap(&(other->alternate_nav_url_)); 349 } 350 351 #ifndef NDEBUG 352 void AutocompleteResult::Validate() const { 353 for (const_iterator i(begin()); i != end(); ++i) 354 i->Validate(); 355 } 356 #endif 357 358 // static 359 GURL AutocompleteResult::ComputeAlternateNavUrl( 360 const AutocompleteInput& input, 361 const AutocompleteMatch& match) { 362 return ((input.type() == metrics::OmniboxInputType::UNKNOWN) && 363 (AutocompleteMatch::IsSearchType(match.type)) && 364 (match.transition != content::PAGE_TRANSITION_KEYWORD) && 365 (input.canonicalized_url() != match.destination_url)) ? 366 input.canonicalized_url() : GURL(); 367 } 368 369 void AutocompleteResult::DedupMatchesByDestination( 370 OmniboxEventProto::PageClassification page_classification, 371 bool set_duplicate_matches, 372 ACMatches* matches) { 373 DestinationSort destination_sort(page_classification); 374 // Sort matches such that duplicate matches are consecutive. 375 std::sort(matches->begin(), matches->end(), destination_sort); 376 377 if (set_duplicate_matches) { 378 // Set duplicate_matches for the first match before erasing duplicate 379 // matches. 380 for (ACMatches::iterator i(matches->begin()); i != matches->end(); ++i) { 381 for (int j = 1; (i + j != matches->end()) && 382 AutocompleteMatch::DestinationsEqual(*i, *(i + j)); ++j) { 383 AutocompleteMatch& dup_match(*(i + j)); 384 i->duplicate_matches.insert(i->duplicate_matches.end(), 385 dup_match.duplicate_matches.begin(), 386 dup_match.duplicate_matches.end()); 387 dup_match.duplicate_matches.clear(); 388 i->duplicate_matches.push_back(dup_match); 389 } 390 } 391 } 392 393 // Erase duplicate matches. 394 matches->erase(std::unique(matches->begin(), matches->end(), 395 &AutocompleteMatch::DestinationsEqual), 396 matches->end()); 397 } 398 399 void AutocompleteResult::CopyFrom(const AutocompleteResult& rhs) { 400 if (this == &rhs) 401 return; 402 403 matches_ = rhs.matches_; 404 // Careful! You can't just copy iterators from another container, you have to 405 // reconstruct them. 406 default_match_ = (rhs.default_match_ == rhs.end()) ? 407 end() : (begin() + (rhs.default_match_ - rhs.begin())); 408 409 alternate_nav_url_ = rhs.alternate_nav_url_; 410 } 411 412 void AutocompleteResult::BuildProviderToMatches( 413 ProviderToMatches* provider_to_matches) const { 414 for (ACMatches::const_iterator i(begin()); i != end(); ++i) 415 (*provider_to_matches)[i->provider].push_back(*i); 416 } 417 418 // static 419 bool AutocompleteResult::HasMatchByDestination(const AutocompleteMatch& match, 420 const ACMatches& matches) { 421 for (ACMatches::const_iterator i(matches.begin()); i != matches.end(); ++i) { 422 if (i->destination_url == match.destination_url) 423 return true; 424 } 425 return false; 426 } 427 428 void AutocompleteResult::MergeMatchesByProvider( 429 OmniboxEventProto::PageClassification page_classification, 430 const ACMatches& old_matches, 431 const ACMatches& new_matches) { 432 if (new_matches.size() >= old_matches.size()) 433 return; 434 435 size_t delta = old_matches.size() - new_matches.size(); 436 const int max_relevance = (new_matches.empty() ? 437 matches_.front().relevance : new_matches[0].relevance) - 1; 438 // Because the goal is a visibly-stable popup, rather than one that preserves 439 // the highest-relevance matches, we copy in the lowest-relevance matches 440 // first. This means that within each provider's "group" of matches, any 441 // synchronous matches (which tend to have the highest scores) will 442 // "overwrite" the initial matches from that provider's previous results, 443 // minimally disturbing the rest of the matches. 444 for (ACMatches::const_reverse_iterator i(old_matches.rbegin()); 445 i != old_matches.rend() && delta > 0; ++i) { 446 if (!HasMatchByDestination(*i, new_matches)) { 447 AutocompleteMatch match = *i; 448 match.relevance = std::min(max_relevance, match.relevance); 449 match.from_previous = true; 450 matches_.push_back(match); 451 delta--; 452 } 453 } 454 } 455