Omnibox: Create DemoteByType Experiment

chrome/browser/autocomplete/autocomplete_result.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/autocomplete/autocomplete_result.h"
 
 #include <algorithm>
 #include <iterator>
 
 #include "base/logging.h"
 #include "chrome/browser/autocomplete/autocomplete_input.h"
 #include "chrome/browser/autocomplete/autocomplete_match.h"
+#include "chrome/browser/omnibox/omnibox_field_trial.h"
+
+namespace {
+
+// This class implements a special version of AutocompleteMatch::MoreRelevant
+// that allows match of particular types to be demoted in AutocompleteResult.

[Peter Kasting, 2013/08/06 19:33:50]

Nit: match -> matches?  AutocompleteResult -> AutocompleteResult::SortAndCull()?

[Mark P, 2013/08/06 22:00:15]

Done.
Not done because this comparison operator is used in two places in this file,
only one of which is SortAndCull.  The key is that this MoreRelevant should be
used as the comparison function everywhere here, that's why I don't want to name
function(s).

+class CompareWithDemoteByType {
+ public:
+  CompareWithDemoteByType(
+      AutocompleteInput::PageClassification current_page_classification);
+
+  // Returns the relevance score of |match| demoted appropriately by
+  // |demotions_by_type_|.
+  int GetDemotedRelevance(const AutocompleteMatch& match);
+
+  // Comparison function.
+  bool operator()(const AutocompleteMatch& elem1,
+                  const AutocompleteMatch& elem2);
+
+ private:
+  OmniboxFieldTrial::DemotionMultiplierByType demotions_by_type_;
+};
+
+CompareWithDemoteByType::CompareWithDemoteByType(
+    AutocompleteInput::PageClassification current_page_classification) {
+  OmniboxFieldTrial::GetDemotionsByType(current_page_classification,
+                                        &demotions_by_type_);
+}
+
+int CompareWithDemoteByType::GetDemotedRelevance(
+    const AutocompleteMatch& match) {
+  return (demotions_by_type_.find(match.type) != demotions_by_type_.end()) ?
+      match.relevance * demotions_by_type_[match.type] : match.relevance;

[Peter Kasting, 2013/08/06 19:33:50]

Nit: How about:

  OmniboxFieldTrial::DemotionMultiplierByType::const_iterator demotion =
      demotions_by_type_.find(match.type);
  return (demotion == demotions_by_type_.end()) ?
      match.relevance : (match.relevance * *demotion));

This is longer, but it avoids the double-lookup (probably no meaningful perf
impact, but if we've got the iterator anyway...)

[Mark P, 2013/08/06 22:00:15]

Done, with a bit of cleanup.

+}
+
+bool CompareWithDemoteByType::operator()(const AutocompleteMatch& elem1,
+                                         const AutocompleteMatch& elem2) {
+  // Compute demoted relevance scores for each match.
+  const int demoted_relevance1 = GetDemotedRelevance(elem1);
+  const int demoted_relevance2 = GetDemotedRelevance(elem2);
+  // For equal-relevance matches, we sort alphabetically, so that providers
+  // who return multiple elements at the same priority get a "stable" sort
+  // across multiple updates.
+  return (demoted_relevance1 == demoted_relevance2) ?
+      (elem1.contents < elem2.contents) :
+      (demoted_relevance1 > demoted_relevance2);
+}
+
+};  // namespace
 
 // static
 const size_t AutocompleteResult::kMaxMatches = 6;
 const int AutocompleteResult::kLowestDefaultScore = 1200;
 
 void AutocompleteResult::Selection::Clear() {
   destination_url = GURL();
   provider_affinity = NULL;
   is_history_what_you_typed_match = false;
 }
@@ skipping 37 matching lines @@
   // ultimately be similar.  If the assumption holds, this prevents seeing the
   // new low-relevance match appear and then quickly get pushed off the bottom;
   // if it doesn't, then once the providers are done and we expire the old
   // matches, the new ones will all become visible, so we won't have lost
   // anything permanently.
   ProviderToMatches matches_per_provider, old_matches_per_provider;
   BuildProviderToMatches(&matches_per_provider);
   old_matches.BuildProviderToMatches(&old_matches_per_provider);
   for (ProviderToMatches::const_iterator i(old_matches_per_provider.begin());
        i != old_matches_per_provider.end(); ++i) {
-    MergeMatchesByProvider(i->second, matches_per_provider[i->first]);
+    MergeMatchesByProvider(input, i->second, matches_per_provider[i->first]);
   }
 
   SortAndCull(input, profile);
 }
 
 void AutocompleteResult::AppendMatches(const ACMatches& matches) {
 #ifndef NDEBUG
   for (ACMatches::const_iterator i(matches.begin()); i != matches.end(); ++i) {
     DCHECK_EQ(AutocompleteMatch::SanitizeString(i->contents), i->contents);
     DCHECK_EQ(AutocompleteMatch::SanitizeString(i->description),
@@ skipping 11 matching lines @@
     i->ComputeStrippedDestinationURL(profile);
 
   // Remove duplicates.
   std::sort(matches_.begin(), matches_.end(),
             &AutocompleteMatch::DestinationSortFunc);
   matches_.erase(std::unique(matches_.begin(), matches_.end(),
                              &AutocompleteMatch::DestinationsEqual),
                  matches_.end());
 
   // Sort and trim to the most relevant kMaxMatches matches.
-  const size_t num_matches = std::min(kMaxMatches, matches_.size());
-  std::partial_sort(matches_.begin(), matches_.begin() + num_matches,
-                    matches_.end(), &AutocompleteMatch::MoreRelevant);
+  size_t max_num_matches = std::min(kMaxMatches, matches_.size());
+  CompareWithDemoteByType comparing_object(input.current_page_classification());
+  std::partial_sort(matches_.begin(), matches_.begin() + max_num_matches,
+                    matches_.end(), comparing_object);
+  // In the process of trimming, drop all matches with a demoted relevance
+  // score of 0.
+  size_t num_matches;
+  for (num_matches = 0u; (num_matches < max_num_matches) &&

[Peter Kasting, 2013/08/06 19:33:50]

Nit: Simpler and (to me) clearer:

  matches_.resize(std::count_if(matches_.begin(),
                                matches_.begin() + max_num_matches,
                                comparing_object.GetDemotedRelevance));

(You might have to fiddle with some adapters if the compiler complains)

[Mark P, 2013/08/06 22:00:15]

I took your suggestion in the simplest way I could get it to work.  I'm not sure
if you'll like it.

Rather than the operator() which is in this patchset, I could instead pass in
something like 
std::bind(&CompareWithDemoteByType::GetDemotedRelevance, &comparing_object,
std::placeholders::_1)
as the third parameter to the count_if.

I'm not sure if either of these are better than what I already had.

[Peter Kasting, 2013/08/06 22:19:40]

It's clever, but I think semantically confusing.  Reading "count if (comparing
object)" doesn't really make any sense.
I think std::bind() is C++11, no?  We don't support that (yet) in Chromium.

The only way I can think of to do this is to write another functor that takes a
CompareWithDemoteByType object and provides an operator().  This is probably
uglier than just doing what you had originally, so I'd probably give up.

[Mark P, 2013/08/06 22:44:49]

Okay, reverted back to original code.

+       (comparing_object.GetDemotedRelevance(*match_at(num_matches)) > 0);
+       ++num_matches) {}
   matches_.resize(num_matches);
 
   default_match_ = begin();
 
   // Set the alternate nav URL.
   alternate_nav_url_ = (default_match_ == end()) ?
       GURL() : ComputeAlternateNavUrl(input, *default_match_);
 }
 
 bool AutocompleteResult::HasCopiedMatches() const {
@@ skipping 78 matching lines @@
 
   matches_ = rhs.matches_;
   // Careful!  You can't just copy iterators from another container, you have to
   // reconstruct them.
   default_match_ = (rhs.default_match_ == rhs.end()) ?
       end() : (begin() + (rhs.default_match_ - rhs.begin()));
 
   alternate_nav_url_ = rhs.alternate_nav_url_;
 }
 
-void AutocompleteResult::AddMatch(const AutocompleteMatch& match) {
+void AutocompleteResult::AddMatch(const AutocompleteInput& input,
+                                  const AutocompleteMatch& match) {
   DCHECK(default_match_ != end());
   DCHECK_EQ(AutocompleteMatch::SanitizeString(match.contents), match.contents);
   DCHECK_EQ(AutocompleteMatch::SanitizeString(match.description),
             match.description);
+  CompareWithDemoteByType comparing_object(input.current_page_classification());
   ACMatches::iterator insertion_point =
-      std::upper_bound(begin(), end(), match, &AutocompleteMatch::MoreRelevant);
+      std::upper_bound(begin(), end(), match, comparing_object);
   matches_difference_type default_offset = default_match_ - begin();
   if ((insertion_point - begin()) <= default_offset)
     ++default_offset;
   matches_.insert(insertion_point, match);
   default_match_ = begin() + default_offset;
 }
 
 void AutocompleteResult::BuildProviderToMatches(
     ProviderToMatches* provider_to_matches) const {
   for (ACMatches::const_iterator i(begin()); i != end(); ++i)
     (*provider_to_matches)[i->provider].push_back(*i);
 }
 
 // static
 bool AutocompleteResult::HasMatchByDestination(const AutocompleteMatch& match,
                                                const ACMatches& matches) {
   for (ACMatches::const_iterator i(matches.begin()); i != matches.end(); ++i) {
     if (i->destination_url == match.destination_url)
       return true;
   }
   return false;
 }
 
-void AutocompleteResult::MergeMatchesByProvider(const ACMatches& old_matches,
+void AutocompleteResult::MergeMatchesByProvider(const AutocompleteInput& input,
+                                                const ACMatches& old_matches,
                                                 const ACMatches& new_matches) {
   if (new_matches.size() >= old_matches.size())
     return;
 
   size_t delta = old_matches.size() - new_matches.size();
   const int max_relevance = (new_matches.empty() ?
       matches_.front().relevance : new_matches[0].relevance) - 1;
   // Because the goal is a visibly-stable popup, rather than one that preserves
   // the highest-relevance matches, we copy in the lowest-relevance matches
   // first. This means that within each provider's "group" of matches, any
   // synchronous matches (which tend to have the highest scores) will
   // "overwrite" the initial matches from that provider's previous results,
   // minimally disturbing the rest of the matches.
   for (ACMatches::const_reverse_iterator i(old_matches.rbegin());
        i != old_matches.rend() && delta > 0; ++i) {
     if (!HasMatchByDestination(*i, new_matches)) {
       AutocompleteMatch match = *i;
       match.relevance = std::min(max_relevance, match.relevance);
       match.from_previous = true;
-      AddMatch(match);
+      AddMatch(input, match);
       delta--;
     }
   }
 }