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 };  // namespace
  68
  69 // static
  70 const size_t AutocompleteResult::kMaxMatches = 6;
  71 const int AutocompleteResult::kLowestDefaultScore = 1200;
  72
  73 void AutocompleteResult::Selection::Clear() {
  74   destination_url = GURL();
  75   provider_affinity = NULL;
  76   is_history_what_you_typed_match = false;
  77 }
  78
  79 AutocompleteResult::AutocompleteResult() {
  80   // Reserve space for the max number of matches we'll show.
  81   matches_.reserve(kMaxMatches);
  82
  83   // It's probably safe to do this in the initializer list, but there's little
  84   // penalty to doing it here and it ensures our object is fully constructed
  85   // before calling member functions.
  86   default_match_ = end();
  87 }
  88
  89 AutocompleteResult::~AutocompleteResult() {}
  90
  91 void AutocompleteResult::CopyOldMatches(const AutocompleteInput& input,
  92                                         const AutocompleteResult& old_matches,
  93                                         Profile* profile) {
  94   if (old_matches.empty())
  95     return;
  96
  97   if (empty()) {
  98     // If we've got no matches we can copy everything from the last result.
  99     CopyFrom(old_matches);
 100     for (ACMatches::iterator i(begin()); i != end(); ++i)
 101       i->from_previous = true;
 102     return;
 103   }
 104
 105   // In hopes of providing a stable popup we try to keep the number of matches
 106   // per provider consistent. Other schemes (such as blindly copying the most
 107   // relevant matches) typically result in many successive 'What You Typed'
 108   // results filling all the matches, which looks awful.
 109   //
 110   // Instead of starting with the current matches and then adding old matches
 111   // until we hit our overall limit, we copy enough old matches so that each
 112   // provider has at least as many as before, and then use SortAndCull() to
 113   // clamp globally. This way, old high-relevance matches will starve new
 114   // low-relevance matches, under the assumption that the new matches will
 115   // ultimately be similar.  If the assumption holds, this prevents seeing the
 116   // new low-relevance match appear and then quickly get pushed off the bottom;
 117   // if it doesn't, then once the providers are done and we expire the old
 118   // matches, the new ones will all become visible, so we won't have lost
 119   // anything permanently.
 120   ProviderToMatches matches_per_provider, old_matches_per_provider;
 121   BuildProviderToMatches(&matches_per_provider);
 122   old_matches.BuildProviderToMatches(&old_matches_per_provider);
 123   for (ProviderToMatches::const_iterator i(old_matches_per_provider.begin());
 124        i != old_matches_per_provider.end(); ++i) {
 125     MergeMatchesByProvider(input.current_page_classification(),
 126                            i->second, matches_per_provider[i->first]);
 127   }
 128
 129   SortAndCull(input, profile);
 130 }
 131
 132 void AutocompleteResult::AppendMatches(const ACMatches& matches) {
 133 #ifndef NDEBUG
 134   for (ACMatches::const_iterator i(matches.begin()); i != matches.end(); ++i) {
 135     DCHECK_EQ(AutocompleteMatch::SanitizeString(i->contents), i->contents);
 136     DCHECK_EQ(AutocompleteMatch::SanitizeString(i->description),
 137               i->description);
 138   }
 139 #endif
 140   std::copy(matches.begin(), matches.end(), std::back_inserter(matches_));
 141   default_match_ = end();
 142   alternate_nav_url_ = GURL();
 143 }
 144
 145 void AutocompleteResult::SortAndCull(const AutocompleteInput& input,
 146                                      Profile* profile) {
 147   for (ACMatches::iterator i(matches_.begin()); i != matches_.end(); ++i)
 148     i->ComputeStrippedDestinationURL(profile);
 149
 150   // Remove duplicates.
 151   std::sort(matches_.begin(), matches_.end(),
 152             &AutocompleteMatch::DestinationSortFunc);
 153   matches_.erase(std::unique(matches_.begin(), matches_.end(),
 154                              &AutocompleteMatch::DestinationsEqual),
 155                  matches_.end());
 156
 157   // Find the top match before possibly applying demotions.
 158   if (!matches_.empty())
 159     std::partial_sort(matches_.begin(), matches_.begin() +  1, matches_.end(),
 160                       &AutocompleteMatch::MoreRelevant);
 161   // Don't demote the top match if applicable.
 162   OmniboxFieldTrial::UndemotableTopMatchTypes undemotable_top_types =
 163       OmniboxFieldTrial::GetUndemotableTopTypes(
 164           input.current_page_classification());
 165   const bool preserve_top_match = !matches_.empty() &&
 166       (undemotable_top_types.count(matches_.begin()->type) != 0);
 167
 168   // Sort and trim to the most relevant kMaxMatches matches.
 169   size_t max_num_matches = std::min(kMaxMatches, matches_.size());
 170   CompareWithDemoteByType comparing_object(input.current_page_classification());
 171   std::sort(matches_.begin() + (preserve_top_match ? 1 : 0), matches_.end(),
 172             comparing_object);
 173   if (!matches_.empty() && !matches_.begin()->allowed_to_be_default_match &&
 174       OmniboxFieldTrial::ReorderForLegalDefaultMatch(
 175           input.current_page_classification())) {
 176     // Top match is not allowed to be the default match.  Find the most
 177     // relevant legal match and shift it to the front.
 178     for (AutocompleteResult::iterator it = matches_.begin() + 1;
 179          it != matches_.end(); ++it) {
 180       if (it->allowed_to_be_default_match) {
 181         std::rotate(matches_.begin(), it, it + 1);
 182         break;
 183       }
 184     }
 185   }
 186   // In the process of trimming, drop all matches with a demoted relevance
 187   // score of 0.
 188   size_t num_matches;
 189   for (num_matches = 0u; (num_matches < max_num_matches) &&
 190        (comparing_object.GetDemotedRelevance(*match_at(num_matches)) > 0);
 191        ++num_matches) {}
 192   matches_.resize(num_matches);
 193
 194   default_match_ = matches_.begin();
 195
 196   if (default_match_ != matches_.end()) {
 197     const base::string16 debug_info =
 198         base::ASCIIToUTF16("fill_into_edit=") +
 199         default_match_->fill_into_edit +
 200         base::ASCIIToUTF16(", provider=") +
 201         ((default_match_->provider != NULL)
 202             ? base::ASCIIToUTF16(default_match_->provider->GetName())
 203             : base::string16()) +
 204         base::ASCIIToUTF16(", input=") +
 205         input.text();
 206     DCHECK(default_match_->allowed_to_be_default_match) << debug_info;
 207     // We shouldn't get query matches for URL inputs, or non-query matches
 208     // for query inputs.
 209     if (AutocompleteMatch::IsSearchType(default_match_->type)) {
 210       DCHECK_NE(AutocompleteInput::URL, input.type()) << debug_info;
 211     } else {
 212       DCHECK_NE(AutocompleteInput::FORCED_QUERY, input.type()) << debug_info;
 213     }
 214   }
 215
 216   // Set the alternate nav URL.
 217   alternate_nav_url_ = (default_match_ == matches_.end()) ?
 218       GURL() : ComputeAlternateNavUrl(input, *default_match_);
 219 }
 220
 221 bool AutocompleteResult::HasCopiedMatches() const {
 222   for (ACMatches::const_iterator i(begin()); i != end(); ++i) {
 223     if (i->from_previous)
 224       return true;
 225   }
 226   return false;
 227 }
 228
 229 size_t AutocompleteResult::size() const {
 230   return matches_.size();
 231 }
 232
 233 bool AutocompleteResult::empty() const {
 234   return matches_.empty();
 235 }
 236
 237 AutocompleteResult::const_iterator AutocompleteResult::begin() const {
 238   return matches_.begin();
 239 }
 240
 241 AutocompleteResult::iterator AutocompleteResult::begin() {
 242   return matches_.begin();
 243 }
 244
 245 AutocompleteResult::const_iterator AutocompleteResult::end() const {
 246   return matches_.end();
 247 }
 248
 249 AutocompleteResult::iterator AutocompleteResult::end() {
 250   return matches_.end();
 251 }
 252
 253 // Returns the match at the given index.
 254 const AutocompleteMatch& AutocompleteResult::match_at(size_t index) const {
 255   DCHECK_LT(index, matches_.size());
 256   return matches_[index];
 257 }
 258
 259 AutocompleteMatch* AutocompleteResult::match_at(size_t index) {
 260   DCHECK_LT(index, matches_.size());
 261   return &matches_[index];
 262 }
 263
 264 bool AutocompleteResult::ShouldHideTopMatch() const {
 265   return chrome::ShouldHideTopVerbatimMatch() &&
 266       TopMatchIsStandaloneVerbatimMatch();
 267 }
 268
 269 bool AutocompleteResult::TopMatchIsStandaloneVerbatimMatch() const {
 270   return !empty() && match_at(0).IsVerbatimType() &&
 271       ((size() == 1) || !match_at(1).IsVerbatimType());
 272 }
 273
 274 void AutocompleteResult::Reset() {
 275   matches_.clear();
 276   default_match_ = end();
 277 }
 278
 279 void AutocompleteResult::Swap(AutocompleteResult* other) {
 280   const size_t default_match_offset = default_match_ - begin();
 281   const size_t other_default_match_offset =
 282       other->default_match_ - other->begin();
 283   matches_.swap(other->matches_);
 284   default_match_ = begin() + other_default_match_offset;
 285   other->default_match_ = other->begin() + default_match_offset;
 286   alternate_nav_url_.Swap(&(other->alternate_nav_url_));
 287 }
 288
 289 #ifndef NDEBUG
 290 void AutocompleteResult::Validate() const {
 291   for (const_iterator i(begin()); i != end(); ++i)
 292     i->Validate();
 293 }
 294 #endif
 295
 296 // static
 297 GURL AutocompleteResult::ComputeAlternateNavUrl(
 298     const AutocompleteInput& input,
 299     const AutocompleteMatch& match) {
 300   return ((input.type() == AutocompleteInput::UNKNOWN) &&
 301           (AutocompleteMatch::IsSearchType(match.type)) &&
 302           (match.transition != content::PAGE_TRANSITION_KEYWORD) &&
 303           (input.canonicalized_url() != match.destination_url)) ?
 304       input.canonicalized_url() : GURL();
 305 }
 306
 307 void AutocompleteResult::CopyFrom(const AutocompleteResult& rhs) {
 308   if (this == &rhs)
 309     return;
 310
 311   matches_ = rhs.matches_;
 312   // Careful!  You can't just copy iterators from another container, you have to
 313   // reconstruct them.
 314   default_match_ = (rhs.default_match_ == rhs.end()) ?
 315       end() : (begin() + (rhs.default_match_ - rhs.begin()));
 316
 317   alternate_nav_url_ = rhs.alternate_nav_url_;
 318 }
 319
 320 void AutocompleteResult::AddMatch(
 321     AutocompleteInput::PageClassification page_classification,
 322     const AutocompleteMatch& match) {
 323   DCHECK(default_match_ != end());
 324   DCHECK_EQ(AutocompleteMatch::SanitizeString(match.contents), match.contents);
 325   DCHECK_EQ(AutocompleteMatch::SanitizeString(match.description),
 326             match.description);
 327   // GetUndemotableTopTypes() is not used here because it's done in
 328   // SortAndCull(), and we depend on SortAndCull() to be called afterwards.
 329   CompareWithDemoteByType comparing_object(page_classification);
 330   ACMatches::iterator insertion_point =
 331       std::upper_bound(begin(), end(), match, comparing_object);
 332   matches_difference_type default_offset = default_match_ - begin();
 333   if ((insertion_point - begin()) <= default_offset)
 334     ++default_offset;
 335   matches_.insert(insertion_point, match);
 336   default_match_ = begin() + default_offset;
 337 }
 338
 339 void AutocompleteResult::BuildProviderToMatches(
 340     ProviderToMatches* provider_to_matches) const {
 341   for (ACMatches::const_iterator i(begin()); i != end(); ++i)
 342     (*provider_to_matches)[i->provider].push_back(*i);
 343 }
 344
 345 // static
 346 bool AutocompleteResult::HasMatchByDestination(const AutocompleteMatch& match,
 347                                                const ACMatches& matches) {
 348   for (ACMatches::const_iterator i(matches.begin()); i != matches.end(); ++i) {
 349     if (i->destination_url == match.destination_url)
 350       return true;
 351   }
 352   return false;
 353 }
 354
 355 void AutocompleteResult::MergeMatchesByProvider(
 356     AutocompleteInput::PageClassification page_classification,
 357     const ACMatches& old_matches,
 358     const ACMatches& new_matches) {
 359   if (new_matches.size() >= old_matches.size())
 360     return;
 361
 362   size_t delta = old_matches.size() - new_matches.size();
 363   const int max_relevance = (new_matches.empty() ?
 364       matches_.front().relevance : new_matches[0].relevance) - 1;
 365   // Because the goal is a visibly-stable popup, rather than one that preserves
 366   // the highest-relevance matches, we copy in the lowest-relevance matches
 367   // first. This means that within each provider's "group" of matches, any
 368   // synchronous matches (which tend to have the highest scores) will
 369   // "overwrite" the initial matches from that provider's previous results,
 370   // minimally disturbing the rest of the matches.
 371   for (ACMatches::const_reverse_iterator i(old_matches.rbegin());
 372        i != old_matches.rend() && delta > 0; ++i) {
 373     if (!HasMatchByDestination(*i, new_matches)) {
 374       AutocompleteMatch match = *i;
 375       match.relevance = std::min(max_relevance, match.relevance);
 376       match.from_previous = true;
 377       AddMatch(page_classification, match);
 378       delta--;
 379     }
 380   }
 381 }