App launcher: Added Finch experiment for the search ranking algorithm.

ui/app_list/search/mixer.cc

 // Copyright 2013 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 "ui/app_list/search/mixer.h"
 
 #include <algorithm>
 #include <map>
 #include <set>
 #include <string>
 #include <vector>
 
+#include "base/metrics/field_trial.h"
 #include "ui/app_list/search_provider.h"
 #include "ui/app_list/search_result.h"
 
 namespace app_list {
 
 namespace {
 
 // Maximum number of results to show.
+// NOTE: If the AppListMixer field trial is "Blended", this is actually the
+// minimum number of results to show. If this quota is not reached, the
+// per-group limitations are removed and we try again. (We may still not reach
+// the minumum, but at least we tried.)
 const size_t kMaxResults = 6;

[calamity, 2015/05/13 03:17:23]

I would just break out the semantic concept into a different variable.

kMinBlendedResults, say.

[Matt Giuca, 2015/05/13 04:02:00]

Done.

 
+const char kAppListMixerFieldTrialName[] = "AppListMixer";
+const char kAppListMixerFieldTrialEnabled[] = "Blended";
+
 void UpdateResult(const SearchResult& source, SearchResult* target) {
   target->set_display_type(source.display_type());
   target->set_title(source.title());
   target->set_title_tags(source.title_tags());
   target->set_details(source.details());
   target->set_details_tags(source.details_tags());
 }
 
+// Returns true if the "AppListMixer" trial is set to "Blended". This is an
+// experiment on the new Mixer logic that allows results from different groups
+// to be blended together, rather than stratified.
+bool IsBlendedMixerTrialEnabled() {
+  const std::string group_name =
+      base::FieldTrialList::FindFullName(kAppListMixerFieldTrialName);
+  return group_name == kAppListMixerFieldTrialEnabled;
+}
+
 }  // namespace
 
 Mixer::SortData::SortData() : result(NULL), score(0.0) {
 }
 
 Mixer::SortData::SortData(SearchResult* result, double score)
     : result(result), score(score) {
 }
 
 bool Mixer::SortData::operator<(const SortData& other) const {
   // This data precedes (less than) |other| if it has higher score.
   return score > other.score;
 }
 
 // Used to group relevant providers together for mixing their results.
 class Mixer::Group {
  public:
-  Group(size_t max_results, double boost)
-      : max_results_(max_results), boost_(boost) {}
+  Group(size_t max_results, double boost, double multiplier)
+      : max_results_(max_results), boost_(boost), multiplier_(multiplier) {}
   ~Group() {}
 
   void AddProvider(SearchProvider* provider) { providers_.push_back(provider); }
 
   void FetchResults(bool is_voice_query, const KnownResults& known_results) {
     results_.clear();
 
     for (const SearchProvider* provider : providers_) {
       for (SearchResult* result : provider->results()) {
         DCHECK(!result->id().empty());
 
         // We cannot rely on providers to give relevance scores in the range
         // [0.0, 1.0] (e.g., PeopleProvider directly gives values from the
         // Google+ API). Clamp to that range.
         double relevance = std::min(std::max(result->relevance(), 0.0), 1.0);
 
+        double multiplier = multiplier_;
         double boost = boost_;
         KnownResults::const_iterator known_it =
             known_results.find(result->id());
         if (known_it != known_results.end()) {
           switch (known_it->second) {
             case PERFECT_PRIMARY:
               boost = 4.0;
               break;
             case PREFIX_PRIMARY:
               boost = 3.75;
               break;
             case PERFECT_SECONDARY:
               boost = 3.25;
               break;
             case PREFIX_SECONDARY:
               boost = 3.0;
               break;
             case UNKNOWN_RESULT:
               NOTREACHED() << "Unknown result in KnownResults?";
               break;
           }
         }
 
         // If this is a voice query, voice results receive a massive boost.
         if (is_voice_query && result->voice_result())
           boost += 4.0;
 
-        results_.push_back(SortData(result, relevance + boost));
+        results_.push_back(SortData(result, relevance * multiplier + boost));
       }
     }
 
     std::sort(results_.begin(), results_.end());
   }
 
   const SortedResults& results() const { return results_; }
 
   const size_t max_results() const { return max_results_; }
 
  private:
   typedef std::vector<SearchProvider*> Providers;
   const size_t max_results_;
   const double boost_;
+  const double multiplier_;
 
   Providers providers_;  // Not owned.
   SortedResults results_;
 
   DISALLOW_COPY_AND_ASSIGN(Group);
 };
 
 Mixer::Mixer(AppListModel::SearchResults* ui_results)
     : ui_results_(ui_results) {
 }
 Mixer::~Mixer() {
 }
 
-size_t Mixer::AddGroup(size_t max_results, double boost) {
-  groups_.push_back(new Group(max_results, boost));
+size_t Mixer::AddGroup(size_t max_results, double boost, double multiplier) {
+  // Only consider |boost| if the AppListMixer field trial is default.
+  // Only consider |multiplier| if the AppListMixer field trial is "Blended".
+  if (IsBlendedMixerTrialEnabled())
+    boost = 0.0;
+  else
+    multiplier = 1.0;
+  groups_.push_back(new Group(max_results, boost, multiplier));
   return groups_.size() - 1;
 }
 
-size_t Mixer::AddOmniboxGroup(size_t max_results, double boost) {
+size_t Mixer::AddOmniboxGroup(size_t max_results,
+                              double boost,
+                              double multiplier) {
   // There should not already be an omnibox group.
   DCHECK(!has_omnibox_group_);
-  size_t id = AddGroup(max_results, boost);
+  size_t id = AddGroup(max_results, boost, multiplier);
   omnibox_group_ = id;
   has_omnibox_group_ = true;
   return id;
 }
 
 void Mixer::AddProviderToGroup(size_t group_id, SearchProvider* provider) {
   groups_[group_id]->AddProvider(provider);
 }
 
 void Mixer::MixAndPublish(bool is_voice_query,
                           const KnownResults& known_results) {
   FetchResults(is_voice_query, known_results);
 
   SortedResults results;
   results.reserve(kMaxResults);
 
-  // Add results from non-omnibox groups first. Limit to the maximum number of
-  // results in each group.
-  for (size_t i = 0; i < groups_.size(); ++i) {
-    if (!has_omnibox_group_ || i != omnibox_group_) {
-      const Group& group = *groups_[i];
+  if (IsBlendedMixerTrialEnabled()) {

[calamity, 2015/05/13 03:17:23]

These 2 blocks are a bit huge, consider breaking them into separate functions.

[Matt Giuca, 2015/05/13 04:02:00]

I think this will just create more churn now, and even more when we remove the
experiment. (There'd be no point keeping the function at that point, because
then MixAndPublish would do almost nothing.)

(churn = having to pass SortedResults by pointer would mean updating all . to ->
and then back again when removing the field trial.)

[calamity, 2015/05/13 05:12:25]

Alright.

+    // Add results from each group. Limit to the maximum number of results in
+    // each group.
+    for (const Group* group : groups_) {
       size_t num_results =
-          std::min(group.results().size(), group.max_results());
-      results.insert(results.end(), group.results().begin(),
-                     group.results().begin() + num_results);
+          std::min(group->results().size(), group->max_results());
+      results.insert(results.end(), group->results().begin(),
+                     group->results().begin() + num_results);
     }
+    // Remove results with duplicate IDs before sorting. If two providers give a
+    // result with the same ID, the result from the provider with the *lower
+    // group number* will be kept (e.g., an app result takes priority over a web
+    // store result with the same ID).
+    RemoveDuplicates(&results);
+    std::sort(results.begin(), results.end());
+
+    if (results.size() < kMaxResults) {
+      size_t original_size = results.size();
+      // We didn't get enough results. Insert all the results again, and this
+      // time, do not limit the maximum number of results from each group. (This
+      // will result in duplicates, which will be removed by RemoveDuplicates.)
+      for (const Group* group : groups_) {
+        results.insert(results.end(), group->results().begin(),
+                       group->results().end());
+      }
+      RemoveDuplicates(&results);
+      // Sort just the newly added results. This ensures that, for example, if
+      // there are 6 Omnibox results (score = 0.8) and 1 People result (score =
+      // 0.4) that the People result will be 5th, not 7th, because the Omnibox
+      // group has a soft maximum of 4 results. (Otherwise, the People result
+      // would not be seen at all once the result list is truncated.)
+      std::sort(results.begin() + original_size, results.end());
+    }
+  } else {
+    // Add results from non-omnibox groups first. Limit to the maximum number of
+    // results in each group.
+    for (size_t i = 0; i < groups_.size(); ++i) {
+      if (!has_omnibox_group_ || i != omnibox_group_) {
+        const Group& group = *groups_[i];
+        size_t num_results =
+            std::min(group.results().size(), group.max_results());
+        results.insert(results.end(), group.results().begin(),
+                       group.results().begin() + num_results);
+      }
+    }
+
+    // Collapse duplicate apps from local and web store.
+    RemoveDuplicates(&results);
+
+    // Fill the remaining slots with omnibox results. Always add at least one
+    // omnibox result (even if there are no more slots; if we over-fill the
+    // vector, the web store and people results will be removed in a later
+    // step). Note: max_results() is ignored for the omnibox group.
+    if (has_omnibox_group_) {
+      CHECK_LT(omnibox_group_, groups_.size());
+      const Group& omnibox_group = *groups_[omnibox_group_];
+      const size_t omnibox_results = std::min(
+          omnibox_group.results().size(),
+          results.size() < kMaxResults ? kMaxResults - results.size() : 1);
+      results.insert(results.end(), omnibox_group.results().begin(),
+                     omnibox_group.results().begin() + omnibox_results);
+    }
+
+    std::sort(results.begin(), results.end());
+    RemoveDuplicates(&results);
+    if (results.size() > kMaxResults)
+      results.resize(kMaxResults);
   }
 
-  // Collapse duplicate apps from local and web store.
-  RemoveDuplicates(&results);
-
-  // Fill the remaining slots with omnibox results. Always add at least one
-  // omnibox result (even if there are no more slots; if we over-fill the
-  // vector, the web store and people results will be removed in a later step).
-  // Note: max_results() is ignored for the omnibox group.
-  if (has_omnibox_group_) {
-    CHECK_LT(omnibox_group_, groups_.size());
-    const Group& omnibox_group = *groups_[omnibox_group_];
-    const size_t omnibox_results = std::min(
-        omnibox_group.results().size(),
-        results.size() < kMaxResults ? kMaxResults - results.size() : 1);
-    results.insert(results.end(), omnibox_group.results().begin(),
-                   omnibox_group.results().begin() + omnibox_results);
-  }
-
-  std::sort(results.begin(), results.end());
-  RemoveDuplicates(&results);
-  if (results.size() > kMaxResults)
-    results.resize(kMaxResults);
-
   Publish(results, ui_results_);
 }
 
 void Mixer::Publish(const SortedResults& new_results,
                     AppListModel::SearchResults* ui_results) {
   typedef std::map<std::string, SearchResult*> IdToResultMap;
 
   // The following algorithm is used:
   // 1. Transform the |ui_results| list into an unordered map from result ID
   // to item.
@@ skipping 58 matching lines @@
   results->swap(final);
 }
 
 void Mixer::FetchResults(bool is_voice_query,
                          const KnownResults& known_results) {
   for (auto* group : groups_)
     group->FetchResults(is_voice_query, known_results);
 }
 
 }  // namespace app_list