| OLD | NEW |
|---|
| (Empty) |
| 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 "components/metrics/proto/omnibox_event.pb.h" | |
| 14 #include "components/metrics/proto/omnibox_input_type.pb.h" | |
| 15 #include "components/omnibox/autocomplete_input.h" | |
| 16 #include "components/omnibox/autocomplete_match.h" | |
| 17 #include "components/omnibox/autocomplete_provider.h" | |
| 18 #include "components/omnibox/omnibox_field_trial.h" | |
| 19 #include "components/search/search.h" | |
| 20 #include "components/url_fixer/url_fixer.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( | |
| 136 const AutocompleteInput& input, | |
| 137 const AutocompleteResult& old_matches, | |
| 138 TemplateURLService* template_url_service) { | |
| 139 if (old_matches.empty()) | |
| 140 return; | |
| 141 | |
| 142 if (empty()) { | |
| 143 // If we've got no matches we can copy everything from the last result. | |
| 144 CopyFrom(old_matches); | |
| 145 for (ACMatches::iterator i(begin()); i != end(); ++i) | |
| 146 i->from_previous = true; | |
| 147 return; | |
| 148 } | |
| 149 | |
| 150 // In hopes of providing a stable popup we try to keep the number of matches | |
| 151 // per provider consistent. Other schemes (such as blindly copying the most | |
| 152 // relevant matches) typically result in many successive 'What You Typed' | |
| 153 // results filling all the matches, which looks awful. | |
| 154 // | |
| 155 // Instead of starting with the current matches and then adding old matches | |
| 156 // until we hit our overall limit, we copy enough old matches so that each | |
| 157 // provider has at least as many as before, and then use SortAndCull() to | |
| 158 // clamp globally. This way, old high-relevance matches will starve new | |
| 159 // low-relevance matches, under the assumption that the new matches will | |
| 160 // ultimately be similar. If the assumption holds, this prevents seeing the | |
| 161 // new low-relevance match appear and then quickly get pushed off the bottom; | |
| 162 // if it doesn't, then once the providers are done and we expire the old | |
| 163 // matches, the new ones will all become visible, so we won't have lost | |
| 164 // anything permanently. | |
| 165 ProviderToMatches matches_per_provider, old_matches_per_provider; | |
| 166 BuildProviderToMatches(&matches_per_provider); | |
| 167 old_matches.BuildProviderToMatches(&old_matches_per_provider); | |
| 168 for (ProviderToMatches::const_iterator i(old_matches_per_provider.begin()); | |
| 169 i != old_matches_per_provider.end(); ++i) { | |
| 170 MergeMatchesByProvider(input.current_page_classification(), | |
| 171 i->second, matches_per_provider[i->first]); | |
| 172 } | |
| 173 | |
| 174 SortAndCull(input, template_url_service); | |
| 175 } | |
| 176 | |
| 177 void AutocompleteResult::AppendMatches(const ACMatches& matches) { | |
| 178 #ifndef NDEBUG | |
| 179 for (ACMatches::const_iterator i(matches.begin()); i != matches.end(); ++i) { | |
| 180 DCHECK_EQ(AutocompleteMatch::SanitizeString(i->contents), i->contents); | |
| 181 DCHECK_EQ(AutocompleteMatch::SanitizeString(i->description), | |
| 182 i->description); | |
| 183 } | |
| 184 #endif | |
| 185 std::copy(matches.begin(), matches.end(), std::back_inserter(matches_)); | |
| 186 default_match_ = end(); | |
| 187 alternate_nav_url_ = GURL(); | |
| 188 } | |
| 189 | |
| 190 void AutocompleteResult::SortAndCull( | |
| 191 const AutocompleteInput& input, | |
| 192 TemplateURLService* template_url_service) { | |
| 193 for (ACMatches::iterator i(matches_.begin()); i != matches_.end(); ++i) | |
| 194 i->ComputeStrippedDestinationURL(template_url_service); | |
| 195 | |
| 196 DedupMatchesByDestination(input.current_page_classification(), true, | |
| 197 &matches_); | |
| 198 | |
| 199 // If the result set has at least one legal default match without an inline | |
| 200 // autocompletion, then in the disable inlining experiment it will be okay | |
| 201 // to demote all matches with inline autocompletions. On the other hand, if | |
| 202 // the experiment is active but there is no legal match without an inline | |
| 203 // autocompletion, then we'll pretend the experiment is not active and not | |
| 204 // demote the matches with an inline autocompletion. In other words, an | |
| 205 // alternate name for this variable is | |
| 206 // allowed_to_demote_matches_with_inline_autocompletion. | |
| 207 bool has_legal_default_match_without_completion = false; | |
| 208 for (AutocompleteResult::iterator it = matches_.begin(); | |
| 209 (it != matches_.end()) && !has_legal_default_match_without_completion; | |
| 210 ++it) { | |
| 211 if (it->allowed_to_be_default_match && it->inline_autocompletion.empty()) | |
| 212 has_legal_default_match_without_completion = true; | |
| 213 } | |
| 214 UMA_HISTOGRAM_BOOLEAN("Omnibox.HasLegalDefaultMatchWithoutCompletion", | |
| 215 has_legal_default_match_without_completion); | |
| 216 | |
| 217 // Sort and trim to the most relevant kMaxMatches matches. | |
| 218 size_t max_num_matches = std::min(kMaxMatches, matches_.size()); | |
| 219 CompareWithDemoteByType comparing_object(input.current_page_classification()); | |
| 220 std::sort(matches_.begin(), matches_.end(), comparing_object); | |
| 221 if (!matches_.empty() && | |
| 222 !AllowedToBeDefaultMatchAccountingForDisableInliningExperiment( | |
| 223 *matches_.begin(), has_legal_default_match_without_completion)) { | |
| 224 // Top match is not allowed to be the default match. Find the most | |
| 225 // relevant legal match and shift it to the front. | |
| 226 for (AutocompleteResult::iterator it = matches_.begin() + 1; | |
| 227 it != matches_.end(); ++it) { | |
| 228 if (AllowedToBeDefaultMatchAccountingForDisableInliningExperiment( | |
| 229 *it, has_legal_default_match_without_completion)) { | |
| 230 std::rotate(matches_.begin(), it, it + 1); | |
| 231 break; | |
| 232 } | |
| 233 } | |
| 234 } | |
| 235 // In the process of trimming, drop all matches with a demoted relevance | |
| 236 // score of 0. | |
| 237 size_t num_matches; | |
| 238 for (num_matches = 0u; (num_matches < max_num_matches) && | |
| 239 (comparing_object.GetDemotedRelevance(*match_at(num_matches)) > 0); | |
| 240 ++num_matches) {} | |
| 241 matches_.resize(num_matches); | |
| 242 | |
| 243 default_match_ = matches_.begin(); | |
| 244 | |
| 245 if (default_match_ != matches_.end()) { | |
| 246 const base::string16 debug_info = | |
| 247 base::ASCIIToUTF16("fill_into_edit=") + | |
| 248 default_match_->fill_into_edit + | |
| 249 base::ASCIIToUTF16(", provider=") + | |
| 250 ((default_match_->provider != NULL) | |
| 251 ? base::ASCIIToUTF16(default_match_->provider->GetName()) | |
| 252 : base::string16()) + | |
| 253 base::ASCIIToUTF16(", input=") + | |
| 254 input.text(); | |
| 255 DCHECK(default_match_->allowed_to_be_default_match) << debug_info; | |
| 256 // If the default match is valid (i.e., not a prompt/placeholder), make | |
| 257 // sure the type of destination is what the user would expect given the | |
| 258 // input. | |
| 259 if (default_match_->destination_url.is_valid()) { | |
| 260 // We shouldn't get query matches for URL inputs, or non-query matches | |
| 261 // for query inputs. | |
| 262 if (AutocompleteMatch::IsSearchType(default_match_->type)) { | |
| 263 DCHECK_NE(metrics::OmniboxInputType::URL, input.type()) << debug_info; | |
| 264 } else { | |
| 265 DCHECK_NE(metrics::OmniboxInputType::FORCED_QUERY, input.type()) | |
| 266 << debug_info; | |
| 267 // If the user explicitly typed a scheme, the default match should | |
| 268 // have the same scheme. | |
| 269 if ((input.type() == metrics::OmniboxInputType::URL) && | |
| 270 input.parts().scheme.is_nonempty()) { | |
| 271 const std::string& in_scheme = base::UTF16ToUTF8(input.scheme()); | |
| 272 const std::string& dest_scheme = | |
| 273 default_match_->destination_url.scheme(); | |
| 274 DCHECK(url_fixer::IsEquivalentScheme(in_scheme, dest_scheme)) | |
| 275 << debug_info; | |
| 276 } | |
| 277 } | |
| 278 } | |
| 279 } | |
| 280 | |
| 281 // Set the alternate nav URL. | |
| 282 alternate_nav_url_ = (default_match_ == matches_.end()) ? | |
| 283 GURL() : ComputeAlternateNavUrl(input, *default_match_); | |
| 284 } | |
| 285 | |
| 286 bool AutocompleteResult::HasCopiedMatches() const { | |
| 287 for (ACMatches::const_iterator i(begin()); i != end(); ++i) { | |
| 288 if (i->from_previous) | |
| 289 return true; | |
| 290 } | |
| 291 return false; | |
| 292 } | |
| 293 | |
| 294 size_t AutocompleteResult::size() const { | |
| 295 return matches_.size(); | |
| 296 } | |
| 297 | |
| 298 bool AutocompleteResult::empty() const { | |
| 299 return matches_.empty(); | |
| 300 } | |
| 301 | |
| 302 AutocompleteResult::const_iterator AutocompleteResult::begin() const { | |
| 303 return matches_.begin(); | |
| 304 } | |
| 305 | |
| 306 AutocompleteResult::iterator AutocompleteResult::begin() { | |
| 307 return matches_.begin(); | |
| 308 } | |
| 309 | |
| 310 AutocompleteResult::const_iterator AutocompleteResult::end() const { | |
| 311 return matches_.end(); | |
| 312 } | |
| 313 | |
| 314 AutocompleteResult::iterator AutocompleteResult::end() { | |
| 315 return matches_.end(); | |
| 316 } | |
| 317 | |
| 318 // Returns the match at the given index. | |
| 319 const AutocompleteMatch& AutocompleteResult::match_at(size_t index) const { | |
| 320 DCHECK_LT(index, matches_.size()); | |
| 321 return matches_[index]; | |
| 322 } | |
| 323 | |
| 324 AutocompleteMatch* AutocompleteResult::match_at(size_t index) { | |
| 325 DCHECK_LT(index, matches_.size()); | |
| 326 return &matches_[index]; | |
| 327 } | |
| 328 | |
| 329 bool AutocompleteResult::ShouldHideTopMatch() const { | |
| 330 return chrome::ShouldHideTopVerbatimMatch() && | |
| 331 TopMatchIsStandaloneVerbatimMatch(); | |
| 332 } | |
| 333 | |
| 334 bool AutocompleteResult::TopMatchIsStandaloneVerbatimMatch() const { | |
| 335 if (empty() || !match_at(0).IsVerbatimType()) | |
| 336 return false; | |
| 337 | |
| 338 // Skip any copied matches, under the assumption that they'll be expired and | |
| 339 // disappear. We don't want this disappearance to cause the visibility of the | |
| 340 // top match to change. | |
| 341 for (const_iterator i(begin() + 1); i != end(); ++i) { | |
| 342 if (!i->from_previous) | |
| 343 return !i->IsVerbatimType(); | |
| 344 } | |
| 345 return true; | |
| 346 } | |
| 347 | |
| 348 void AutocompleteResult::Reset() { | |
| 349 matches_.clear(); | |
| 350 default_match_ = end(); | |
| 351 } | |
| 352 | |
| 353 void AutocompleteResult::Swap(AutocompleteResult* other) { | |
| 354 const size_t default_match_offset = default_match_ - begin(); | |
| 355 const size_t other_default_match_offset = | |
| 356 other->default_match_ - other->begin(); | |
| 357 matches_.swap(other->matches_); | |
| 358 default_match_ = begin() + other_default_match_offset; | |
| 359 other->default_match_ = other->begin() + default_match_offset; | |
| 360 alternate_nav_url_.Swap(&(other->alternate_nav_url_)); | |
| 361 } | |
| 362 | |
| 363 #ifndef NDEBUG | |
| 364 void AutocompleteResult::Validate() const { | |
| 365 for (const_iterator i(begin()); i != end(); ++i) | |
| 366 i->Validate(); | |
| 367 } | |
| 368 #endif | |
| 369 | |
| 370 // static | |
| 371 GURL AutocompleteResult::ComputeAlternateNavUrl( | |
| 372 const AutocompleteInput& input, | |
| 373 const AutocompleteMatch& match) { | |
| 374 return ((input.type() == metrics::OmniboxInputType::UNKNOWN) && | |
| 375 (AutocompleteMatch::IsSearchType(match.type)) && | |
| 376 (match.transition != content::PAGE_TRANSITION_KEYWORD) && | |
| 377 (input.canonicalized_url() != match.destination_url)) ? | |
| 378 input.canonicalized_url() : GURL(); | |
| 379 } | |
| 380 | |
| 381 void AutocompleteResult::DedupMatchesByDestination( | |
| 382 OmniboxEventProto::PageClassification page_classification, | |
| 383 bool set_duplicate_matches, | |
| 384 ACMatches* matches) { | |
| 385 DestinationSort destination_sort(page_classification); | |
| 386 // Sort matches such that duplicate matches are consecutive. | |
| 387 std::sort(matches->begin(), matches->end(), destination_sort); | |
| 388 | |
| 389 if (set_duplicate_matches) { | |
| 390 // Set duplicate_matches for the first match before erasing duplicate | |
| 391 // matches. | |
| 392 for (ACMatches::iterator i(matches->begin()); i != matches->end(); ++i) { | |
| 393 for (int j = 1; (i + j != matches->end()) && | |
| 394 AutocompleteMatch::DestinationsEqual(*i, *(i + j)); ++j) { | |
| 395 AutocompleteMatch& dup_match(*(i + j)); | |
| 396 i->duplicate_matches.insert(i->duplicate_matches.end(), | |
| 397 dup_match.duplicate_matches.begin(), | |
| 398 dup_match.duplicate_matches.end()); | |
| 399 dup_match.duplicate_matches.clear(); | |
| 400 i->duplicate_matches.push_back(dup_match); | |
| 401 } | |
| 402 } | |
| 403 } | |
| 404 | |
| 405 // Erase duplicate matches. | |
| 406 matches->erase(std::unique(matches->begin(), matches->end(), | |
| 407 &AutocompleteMatch::DestinationsEqual), | |
| 408 matches->end()); | |
| 409 } | |
| 410 | |
| 411 void AutocompleteResult::CopyFrom(const AutocompleteResult& rhs) { | |
| 412 if (this == &rhs) | |
| 413 return; | |
| 414 | |
| 415 matches_ = rhs.matches_; | |
| 416 // Careful! You can't just copy iterators from another container, you have to | |
| 417 // reconstruct them. | |
| 418 default_match_ = (rhs.default_match_ == rhs.end()) ? | |
| 419 end() : (begin() + (rhs.default_match_ - rhs.begin())); | |
| 420 | |
| 421 alternate_nav_url_ = rhs.alternate_nav_url_; | |
| 422 } | |
| 423 | |
| 424 void AutocompleteResult::BuildProviderToMatches( | |
| 425 ProviderToMatches* provider_to_matches) const { | |
| 426 for (ACMatches::const_iterator i(begin()); i != end(); ++i) | |
| 427 (*provider_to_matches)[i->provider].push_back(*i); | |
| 428 } | |
| 429 | |
| 430 // static | |
| 431 bool AutocompleteResult::HasMatchByDestination(const AutocompleteMatch& match, | |
| 432 const ACMatches& matches) { | |
| 433 for (ACMatches::const_iterator i(matches.begin()); i != matches.end(); ++i) { | |
| 434 if (i->destination_url == match.destination_url) | |
| 435 return true; | |
| 436 } | |
| 437 return false; | |
| 438 } | |
| 439 | |
| 440 void AutocompleteResult::MergeMatchesByProvider( | |
| 441 OmniboxEventProto::PageClassification page_classification, | |
| 442 const ACMatches& old_matches, | |
| 443 const ACMatches& new_matches) { | |
| 444 if (new_matches.size() >= old_matches.size()) | |
| 445 return; | |
| 446 | |
| 447 size_t delta = old_matches.size() - new_matches.size(); | |
| 448 const int max_relevance = (new_matches.empty() ? | |
| 449 matches_.front().relevance : new_matches[0].relevance) - 1; | |
| 450 // Because the goal is a visibly-stable popup, rather than one that preserves | |
| 451 // the highest-relevance matches, we copy in the lowest-relevance matches | |
| 452 // first. This means that within each provider's "group" of matches, any | |
| 453 // synchronous matches (which tend to have the highest scores) will | |
| 454 // "overwrite" the initial matches from that provider's previous results, | |
| 455 // minimally disturbing the rest of the matches. | |
| 456 for (ACMatches::const_reverse_iterator i(old_matches.rbegin()); | |
| 457 i != old_matches.rend() && delta > 0; ++i) { | |
| 458 if (!HasMatchByDestination(*i, new_matches)) { | |
| 459 AutocompleteMatch match = *i; | |
| 460 match.relevance = std::min(max_relevance, match.relevance); | |
| 461 match.from_previous = true; | |
| 462 matches_.push_back(match); | |
| 463 delta--; | |
| 464 } | |
| 465 } | |
| 466 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 470523002:
Componentize AutocompleteResult (Closed)
Base URL: svn://svn.chromium.org/chrome/trunk/src