chrome/browser/autocomplete/autocomplete_result.cc

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