components/omnibox/browser/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/browser/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/browser/autocomplete_input.h"
  16 #include "components/omnibox/browser/autocomplete_match.h"
  17 #include "components/omnibox/browser/autocomplete_provider.h"
  18 #include "components/omnibox/browser/omnibox_field_trial.h"
  19 #include "components/omnibox/browser/omnibox_switches.h"
  20 #include "components/search/search.h"
  21 #include "components/url_formatter/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 std::string& languages,
 127     const AutocompleteResult& old_matches,
 128     TemplateURLService* template_url_service) {
 129   if (old_matches.empty())
 130     return;
 131
 132   if (empty()) {
 133     // If we've got no matches we can copy everything from the last result.
 134     CopyFrom(old_matches);
 135     for (ACMatches::iterator i(begin()); i != end(); ++i)
 136       i->from_previous = true;
 137     return;
 138   }
 139
 140   // In hopes of providing a stable popup we try to keep the number of matches
 141   // per provider consistent. Other schemes (such as blindly copying the most
 142   // relevant matches) typically result in many successive 'What You Typed'
 143   // results filling all the matches, which looks awful.
 144   //
 145   // Instead of starting with the current matches and then adding old matches
 146   // until we hit our overall limit, we copy enough old matches so that each
 147   // provider has at least as many as before, and then use SortAndCull() to
 148   // clamp globally. This way, old high-relevance matches will starve new
 149   // low-relevance matches, under the assumption that the new matches will
 150   // ultimately be similar.  If the assumption holds, this prevents seeing the
 151   // new low-relevance match appear and then quickly get pushed off the bottom;
 152   // if it doesn't, then once the providers are done and we expire the old
 153   // matches, the new ones will all become visible, so we won't have lost
 154   // anything permanently.
 155   ProviderToMatches matches_per_provider, old_matches_per_provider;
 156   BuildProviderToMatches(&matches_per_provider);
 157   old_matches.BuildProviderToMatches(&old_matches_per_provider);
 158   for (ProviderToMatches::const_iterator i(old_matches_per_provider.begin());
 159        i != old_matches_per_provider.end(); ++i) {
 160     MergeMatchesByProvider(input.current_page_classification(),
 161                            i->second, matches_per_provider[i->first]);
 162   }
 163
 164   SortAndCull(input, languages, template_url_service);
 165 }
 166
 167 void AutocompleteResult::AppendMatches(const AutocompleteInput& input,
 168                                        const ACMatches& matches) {
 169   for (const auto& i : matches) {
 170 #ifndef NDEBUG
 171     DCHECK_EQ(AutocompleteMatch::SanitizeString(i.contents), i.contents);
 172     DCHECK_EQ(AutocompleteMatch::SanitizeString(i.description),
 173               i.description);
 174 #endif
 175     matches_.push_back(i);
 176     if (!AutocompleteMatch::IsSearchType(i.type) && !i.description.empty() &&
 177         base::CommandLine::ForCurrentProcess()->
 178             HasSwitch(switches::kEmphasizeTitlesInOmniboxDropdown) &&
 179         ((input.type() == metrics::OmniboxInputType::QUERY) ||
 180          (input.type() == metrics::OmniboxInputType::FORCED_QUERY)) &&
 181         AutocompleteMatch::HasMatchStyle(i.description_class)) {
 182       matches_.back().swap_contents_and_description = true;
 183     }
 184   }
 185   default_match_ = end();
 186   alternate_nav_url_ = GURL();
 187 }
 188
 189 void AutocompleteResult::SortAndCull(
 190     const AutocompleteInput& input,
 191     const std::string& languages,
 192     TemplateURLService* template_url_service) {
 193   for (ACMatches::iterator i(matches_.begin()); i != matches_.end(); ++i)
 194     i->ComputeStrippedDestinationURL(input, languages, template_url_service);
 195
 196   DedupMatchesByDestination(input.current_page_classification(), true,
 197                             &matches_);
 198
 199   // Sort and trim to the most relevant kMaxMatches matches.
 200   size_t max_num_matches = std::min(kMaxMatches, matches_.size());
 201   CompareWithDemoteByType comparing_object(input.current_page_classification());
 202   std::sort(matches_.begin(), matches_.end(), comparing_object);
 203   if (!matches_.empty() && !matches_.begin()->allowed_to_be_default_match) {
 204     // Top match is not allowed to be the default match.  Find the most
 205     // relevant legal match and shift it to the front.
 206     for (AutocompleteResult::iterator it = matches_.begin() + 1;
 207          it != matches_.end(); ++it) {
 208       if (it->allowed_to_be_default_match) {
 209         std::rotate(matches_.begin(), it, it + 1);
 210         break;
 211       }
 212     }
 213   }
 214   // In the process of trimming, drop all matches with a demoted relevance
 215   // score of 0.
 216   size_t num_matches;
 217   for (num_matches = 0u; (num_matches < max_num_matches) &&
 218        (comparing_object.GetDemotedRelevance(*match_at(num_matches)) > 0);
 219        ++num_matches) {}
 220   matches_.resize(num_matches);
 221
 222   default_match_ = matches_.begin();
 223
 224   if (default_match_ != matches_.end()) {
 225     const base::string16 debug_info =
 226         base::ASCIIToUTF16("fill_into_edit=") +
 227         default_match_->fill_into_edit +
 228         base::ASCIIToUTF16(", provider=") +
 229         ((default_match_->provider != NULL)
 230             ? base::ASCIIToUTF16(default_match_->provider->GetName())
 231             : base::string16()) +
 232         base::ASCIIToUTF16(", input=") +
 233         input.text();
 234     DCHECK(default_match_->allowed_to_be_default_match) << debug_info;
 235     // If the default match is valid (i.e., not a prompt/placeholder), make
 236     // sure the type of destination is what the user would expect given the
 237     // input.
 238     if (default_match_->destination_url.is_valid()) {
 239       // We shouldn't get query matches for URL inputs, or non-query matches
 240       // for query inputs.
 241       if (AutocompleteMatch::IsSearchType(default_match_->type)) {
 242         DCHECK_NE(metrics::OmniboxInputType::URL, input.type()) << debug_info;
 243       } else {
 244         DCHECK_NE(metrics::OmniboxInputType::FORCED_QUERY, input.type())
 245             << debug_info;
 246         // If the user explicitly typed a scheme, the default match should
 247         // have the same scheme.
 248         if ((input.type() == metrics::OmniboxInputType::URL) &&
 249             input.parts().scheme.is_nonempty()) {
 250           const std::string& in_scheme = base::UTF16ToUTF8(input.scheme());
 251           const std::string& dest_scheme =
 252               default_match_->destination_url.scheme();
 253           DCHECK(url_formatter::IsEquivalentScheme(in_scheme, dest_scheme))
 254               << debug_info;
 255         }
 256       }
 257     }
 258   }
 259
 260   // Set the alternate nav URL.
 261   alternate_nav_url_ = (default_match_ == matches_.end()) ?
 262       GURL() : ComputeAlternateNavUrl(input, *default_match_);
 263 }
 264
 265 bool AutocompleteResult::HasCopiedMatches() const {
 266   for (ACMatches::const_iterator i(begin()); i != end(); ++i) {
 267     if (i->from_previous)
 268       return true;
 269   }
 270   return false;
 271 }
 272
 273 size_t AutocompleteResult::size() const {
 274   return matches_.size();
 275 }
 276
 277 bool AutocompleteResult::empty() const {
 278   return matches_.empty();
 279 }
 280
 281 AutocompleteResult::const_iterator AutocompleteResult::begin() const {
 282   return matches_.begin();
 283 }
 284
 285 AutocompleteResult::iterator AutocompleteResult::begin() {
 286   return matches_.begin();
 287 }
 288
 289 AutocompleteResult::const_iterator AutocompleteResult::end() const {
 290   return matches_.end();
 291 }
 292
 293 AutocompleteResult::iterator AutocompleteResult::end() {
 294   return matches_.end();
 295 }
 296
 297 // Returns the match at the given index.
 298 const AutocompleteMatch& AutocompleteResult::match_at(size_t index) const {
 299   DCHECK_LT(index, matches_.size());
 300   return matches_[index];
 301 }
 302
 303 AutocompleteMatch* AutocompleteResult::match_at(size_t index) {
 304   DCHECK_LT(index, matches_.size());
 305   return &matches_[index];
 306 }
 307
 308 bool AutocompleteResult::TopMatchIsStandaloneVerbatimMatch() const {
 309   if (empty() || !match_at(0).IsVerbatimType())
 310     return false;
 311
 312   // Skip any copied matches, under the assumption that they'll be expired and
 313   // disappear.  We don't want this disappearance to cause the visibility of the
 314   // top match to change.
 315   for (const_iterator i(begin() + 1); i != end(); ++i) {
 316     if (!i->from_previous)
 317       return !i->IsVerbatimType();
 318   }
 319   return true;
 320 }
 321
 322 void AutocompleteResult::Reset() {
 323   matches_.clear();
 324   default_match_ = end();
 325 }
 326
 327 void AutocompleteResult::Swap(AutocompleteResult* other) {
 328   const size_t default_match_offset = default_match_ - begin();
 329   const size_t other_default_match_offset =
 330       other->default_match_ - other->begin();
 331   matches_.swap(other->matches_);
 332   default_match_ = begin() + other_default_match_offset;
 333   other->default_match_ = other->begin() + default_match_offset;
 334   alternate_nav_url_.Swap(&(other->alternate_nav_url_));
 335 }
 336
 337 #ifndef NDEBUG
 338 void AutocompleteResult::Validate() const {
 339   for (const_iterator i(begin()); i != end(); ++i)
 340     i->Validate();
 341 }
 342 #endif
 343
 344 // static
 345 GURL AutocompleteResult::ComputeAlternateNavUrl(
 346     const AutocompleteInput& input,
 347     const AutocompleteMatch& match) {
 348   return ((input.type() == metrics::OmniboxInputType::UNKNOWN) &&
 349           (AutocompleteMatch::IsSearchType(match.type)) &&
 350           (match.transition != ui::PAGE_TRANSITION_KEYWORD) &&
 351           (input.canonicalized_url() != match.destination_url)) ?
 352       input.canonicalized_url() : GURL();
 353 }
 354
 355 void AutocompleteResult::DedupMatchesByDestination(
 356       OmniboxEventProto::PageClassification page_classification,
 357       bool set_duplicate_matches,
 358       ACMatches* matches) {
 359   DestinationSort destination_sort(page_classification);
 360   // Sort matches such that duplicate matches are consecutive.
 361   std::sort(matches->begin(), matches->end(), destination_sort);
 362
 363   if (set_duplicate_matches) {
 364     // Set duplicate_matches for the first match before erasing duplicate
 365     // matches.
 366     for (ACMatches::iterator i(matches->begin()); i != matches->end(); ++i) {
 367       for (int j = 1; (i + j != matches->end()) &&
 368                AutocompleteMatch::DestinationsEqual(*i, *(i + j)); ++j) {
 369         AutocompleteMatch& dup_match(*(i + j));
 370         i->duplicate_matches.insert(i->duplicate_matches.end(),
 371                                     dup_match.duplicate_matches.begin(),
 372                                     dup_match.duplicate_matches.end());
 373         dup_match.duplicate_matches.clear();
 374         i->duplicate_matches.push_back(dup_match);
 375       }
 376     }
 377   }
 378
 379   // Erase duplicate matches.
 380   matches->erase(std::unique(matches->begin(), matches->end(),
 381                              &AutocompleteMatch::DestinationsEqual),
 382                  matches->end());
 383 }
 384
 385 void AutocompleteResult::CopyFrom(const AutocompleteResult& rhs) {
 386   if (this == &rhs)
 387     return;
 388
 389   matches_ = rhs.matches_;
 390   // Careful!  You can't just copy iterators from another container, you have to
 391   // reconstruct them.
 392   default_match_ = (rhs.default_match_ == rhs.end()) ?
 393       end() : (begin() + (rhs.default_match_ - rhs.begin()));
 394
 395   alternate_nav_url_ = rhs.alternate_nav_url_;
 396 }
 397
 398 void AutocompleteResult::BuildProviderToMatches(
 399     ProviderToMatches* provider_to_matches) const {
 400   for (ACMatches::const_iterator i(begin()); i != end(); ++i)
 401     (*provider_to_matches)[i->provider].push_back(*i);
 402 }
 403
 404 // static
 405 bool AutocompleteResult::HasMatchByDestination(const AutocompleteMatch& match,
 406                                                const ACMatches& matches) {
 407   for (ACMatches::const_iterator i(matches.begin()); i != matches.end(); ++i) {
 408     if (i->destination_url == match.destination_url)
 409       return true;
 410   }
 411   return false;
 412 }
 413
 414 void AutocompleteResult::MergeMatchesByProvider(
 415     OmniboxEventProto::PageClassification page_classification,
 416     const ACMatches& old_matches,
 417     const ACMatches& new_matches) {
 418   if (new_matches.size() >= old_matches.size())
 419     return;
 420
 421   // Prevent old matches from this provider from outranking new ones and
 422   // becoming the default match by capping old matches' scores to be less than
 423   // the highest-scoring allowed-to-be-default match from this provider.
 424   ACMatches::const_iterator i = std::find_if(
 425       new_matches.begin(), new_matches.end(),
 426       [] (const AutocompleteMatch& m) {
 427         return m.allowed_to_be_default_match;
 428       });
 429
 430   // If the provider doesn't have any matches that are allowed-to-be-default,
 431   // cap scores below the global allowed-to-be-default match.
 432   // AutocompleteResult maintains the invariant that the first item in
 433   // |matches_| is always such a match.
 434   if (i == new_matches.end())
 435     i = matches_.begin();
 436
 437   DCHECK(i->allowed_to_be_default_match);
 438   const int max_relevance = i->relevance - 1;
 439
 440   // Because the goal is a visibly-stable popup, rather than one that preserves
 441   // the highest-relevance matches, we copy in the lowest-relevance matches
 442   // first. This means that within each provider's "group" of matches, any
 443   // synchronous matches (which tend to have the highest scores) will
 444   // "overwrite" the initial matches from that provider's previous results,
 445   // minimally disturbing the rest of the matches.
 446   size_t delta = old_matches.size() - new_matches.size();
 447   for (ACMatches::const_reverse_iterator i(old_matches.rbegin());
 448        i != old_matches.rend() && delta > 0; ++i) {
 449     if (!HasMatchByDestination(*i, new_matches)) {
 450       AutocompleteMatch match = *i;
 451       match.relevance = std::min(max_relevance, match.relevance);
 452       match.from_previous = true;
 453       matches_.push_back(match);
 454       delta--;
 455     }
 456   }
 457 }