components/omnibox/autocomplete_result.cc

   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
   3 // found in the LICENSE file.
   4
   5 #include "components/omnibox/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 }