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