• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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  
CompareWithDemoteByType(AutocompleteInput::PageClassification current_page_classification)40  CompareWithDemoteByType::CompareWithDemoteByType(
41      AutocompleteInput::PageClassification current_page_classification) {
42    OmniboxFieldTrial::GetDemotionsByType(current_page_classification,
43                                          &demotions_);
44  }
45  
GetDemotedRelevance(const AutocompleteMatch & match)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  
operator ()(const AutocompleteMatch & elem1,const AutocompleteMatch & elem2)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  
Clear()73  void AutocompleteResult::Selection::Clear() {
74    destination_url = GURL();
75    provider_affinity = NULL;
76    is_history_what_you_typed_match = false;
77  }
78  
AutocompleteResult()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  
~AutocompleteResult()89  AutocompleteResult::~AutocompleteResult() {}
90  
CopyOldMatches(const AutocompleteInput & input,const AutocompleteResult & old_matches,Profile * profile)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  
AppendMatches(const ACMatches & matches)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  
SortAndCull(const AutocompleteInput & input,Profile * profile)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 = ASCIIToUTF16("fill_into_edit=") +
198          default_match_->fill_into_edit + ASCIIToUTF16(", provider=") +
199          ((default_match_->provider != NULL) ?
200           ASCIIToUTF16(default_match_->provider->GetName()) : base::string16()) +
201          ASCIIToUTF16(", input=") + input.text();
202      DCHECK(default_match_->allowed_to_be_default_match) << debug_info;
203      // We shouldn't get query matches for URL inputs, or non-query matches
204      // for query inputs.
205      if (AutocompleteMatch::IsSearchType(default_match_->type)) {
206        DCHECK_NE(AutocompleteInput::URL, input.type()) << debug_info;
207      } else {
208        DCHECK_NE(AutocompleteInput::FORCED_QUERY, input.type()) << debug_info;
209      }
210    }
211  
212    // Set the alternate nav URL.
213    alternate_nav_url_ = (default_match_ == matches_.end()) ?
214        GURL() : ComputeAlternateNavUrl(input, *default_match_);
215  }
216  
HasCopiedMatches() const217  bool AutocompleteResult::HasCopiedMatches() const {
218    for (ACMatches::const_iterator i(begin()); i != end(); ++i) {
219      if (i->from_previous)
220        return true;
221    }
222    return false;
223  }
224  
size() const225  size_t AutocompleteResult::size() const {
226    return matches_.size();
227  }
228  
empty() const229  bool AutocompleteResult::empty() const {
230    return matches_.empty();
231  }
232  
begin() const233  AutocompleteResult::const_iterator AutocompleteResult::begin() const {
234    return matches_.begin();
235  }
236  
begin()237  AutocompleteResult::iterator AutocompleteResult::begin() {
238    return matches_.begin();
239  }
240  
end() const241  AutocompleteResult::const_iterator AutocompleteResult::end() const {
242    return matches_.end();
243  }
244  
end()245  AutocompleteResult::iterator AutocompleteResult::end() {
246    return matches_.end();
247  }
248  
249  // Returns the match at the given index.
match_at(size_t index) const250  const AutocompleteMatch& AutocompleteResult::match_at(size_t index) const {
251    DCHECK_LT(index, matches_.size());
252    return matches_[index];
253  }
254  
match_at(size_t index)255  AutocompleteMatch* AutocompleteResult::match_at(size_t index) {
256    DCHECK_LT(index, matches_.size());
257    return &matches_[index];
258  }
259  
ShouldHideTopMatch() const260  bool AutocompleteResult::ShouldHideTopMatch() const {
261    // Gate on our field trial flag.
262    return chrome::ShouldHideTopVerbatimMatch() &&
263        TopMatchIsVerbatimAndHasNoConsecutiveVerbatimMatches();
264  }
265  
TopMatchIsVerbatimAndHasNoConsecutiveVerbatimMatches() const266  bool AutocompleteResult::TopMatchIsVerbatimAndHasNoConsecutiveVerbatimMatches()
267      const {
268    if (empty() || !match_at(0).IsVerbatimType())
269      return false;
270    return !(size() > 1) || !match_at(1).IsVerbatimType();
271  }
272  
Reset()273  void AutocompleteResult::Reset() {
274    matches_.clear();
275    default_match_ = end();
276  }
277  
Swap(AutocompleteResult * other)278  void AutocompleteResult::Swap(AutocompleteResult* other) {
279    const size_t default_match_offset = default_match_ - begin();
280    const size_t other_default_match_offset =
281        other->default_match_ - other->begin();
282    matches_.swap(other->matches_);
283    default_match_ = begin() + other_default_match_offset;
284    other->default_match_ = other->begin() + default_match_offset;
285    alternate_nav_url_.Swap(&(other->alternate_nav_url_));
286  }
287  
288  #ifndef NDEBUG
Validate() const289  void AutocompleteResult::Validate() const {
290    for (const_iterator i(begin()); i != end(); ++i)
291      i->Validate();
292  }
293  #endif
294  
295  // static
ComputeAlternateNavUrl(const AutocompleteInput & input,const AutocompleteMatch & match)296  GURL AutocompleteResult::ComputeAlternateNavUrl(
297      const AutocompleteInput& input,
298      const AutocompleteMatch& match) {
299    return ((input.type() == AutocompleteInput::UNKNOWN) &&
300            (AutocompleteMatch::IsSearchType(match.type)) &&
301            (match.transition != content::PAGE_TRANSITION_KEYWORD) &&
302            (input.canonicalized_url() != match.destination_url)) ?
303        input.canonicalized_url() : GURL();
304  }
305  
CopyFrom(const AutocompleteResult & rhs)306  void AutocompleteResult::CopyFrom(const AutocompleteResult& rhs) {
307    if (this == &rhs)
308      return;
309  
310    matches_ = rhs.matches_;
311    // Careful!  You can't just copy iterators from another container, you have to
312    // reconstruct them.
313    default_match_ = (rhs.default_match_ == rhs.end()) ?
314        end() : (begin() + (rhs.default_match_ - rhs.begin()));
315  
316    alternate_nav_url_ = rhs.alternate_nav_url_;
317  }
318  
AddMatch(AutocompleteInput::PageClassification page_classification,const AutocompleteMatch & match)319  void AutocompleteResult::AddMatch(
320      AutocompleteInput::PageClassification page_classification,
321      const AutocompleteMatch& match) {
322    DCHECK(default_match_ != end());
323    DCHECK_EQ(AutocompleteMatch::SanitizeString(match.contents), match.contents);
324    DCHECK_EQ(AutocompleteMatch::SanitizeString(match.description),
325              match.description);
326    // GetUndemotableTopTypes() is not used here because it's done in
327    // SortAndCull(), and we depend on SortAndCull() to be called afterwards.
328    CompareWithDemoteByType comparing_object(page_classification);
329    ACMatches::iterator insertion_point =
330        std::upper_bound(begin(), end(), match, comparing_object);
331    matches_difference_type default_offset = default_match_ - begin();
332    if ((insertion_point - begin()) <= default_offset)
333      ++default_offset;
334    matches_.insert(insertion_point, match);
335    default_match_ = begin() + default_offset;
336  }
337  
BuildProviderToMatches(ProviderToMatches * provider_to_matches) const338  void AutocompleteResult::BuildProviderToMatches(
339      ProviderToMatches* provider_to_matches) const {
340    for (ACMatches::const_iterator i(begin()); i != end(); ++i)
341      (*provider_to_matches)[i->provider].push_back(*i);
342  }
343  
344  // static
HasMatchByDestination(const AutocompleteMatch & match,const ACMatches & matches)345  bool AutocompleteResult::HasMatchByDestination(const AutocompleteMatch& match,
346                                                 const ACMatches& matches) {
347    for (ACMatches::const_iterator i(matches.begin()); i != matches.end(); ++i) {
348      if (i->destination_url == match.destination_url)
349        return true;
350    }
351    return false;
352  }
353  
MergeMatchesByProvider(AutocompleteInput::PageClassification page_classification,const ACMatches & old_matches,const ACMatches & new_matches)354  void AutocompleteResult::MergeMatchesByProvider(
355      AutocompleteInput::PageClassification page_classification,
356      const ACMatches& old_matches,
357      const ACMatches& new_matches) {
358    if (new_matches.size() >= old_matches.size())
359      return;
360  
361    size_t delta = old_matches.size() - new_matches.size();
362    const int max_relevance = (new_matches.empty() ?
363        matches_.front().relevance : new_matches[0].relevance) - 1;
364    // Because the goal is a visibly-stable popup, rather than one that preserves
365    // the highest-relevance matches, we copy in the lowest-relevance matches
366    // first. This means that within each provider's "group" of matches, any
367    // synchronous matches (which tend to have the highest scores) will
368    // "overwrite" the initial matches from that provider's previous results,
369    // minimally disturbing the rest of the matches.
370    for (ACMatches::const_reverse_iterator i(old_matches.rbegin());
371         i != old_matches.rend() && delta > 0; ++i) {
372      if (!HasMatchByDestination(*i, new_matches)) {
373        AutocompleteMatch match = *i;
374        match.relevance = std::min(max_relevance, match.relevance);
375        match.from_previous = true;
376        AddMatch(page_classification, match);
377        delta--;
378      }
379    }
380  }
381