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