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