ui/app_list/search/mixer.cc

   1 // Copyright 2013 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 "ui/app_list/search/mixer.h"
   6
   7 #include <algorithm>
   8 #include <map>
   9 #include <set>
  10 #include <string>
  11 #include <vector>
  12
  13 #include "base/command_line.h"
  14 #include "base/metrics/field_trial.h"
  15 #include "ui/app_list/app_list_switches.h"
  16 #include "ui/app_list/search_provider.h"
  17 #include "ui/app_list/search_result.h"
  18
  19 namespace app_list {
  20
  21 namespace {
  22
  23 // Maximum number of results to show. Ignored if the AppListMixer field trial is
  24 // "Blended".
  25 const size_t kMaxResults = 6;
  26
  27 // The minimum number of results to show, if the AppListMixer field trial is
  28 // "Blended". If this quota is not reached, the per-group limitations are
  29 // removed and we try again. (We may still not reach the minumum, but at least
  30 // we tried.) Ignored if the field trial is off.
  31 const size_t kMinBlendedResults = 6;
  32
  33 const char kAppListMixerFieldTrialName[] = "AppListMixer";
  34 const char kAppListMixerFieldTrialEnabled[] = "Blended";
  35
  36 void UpdateResult(const SearchResult& source, SearchResult* target) {
  37   target->set_display_type(source.display_type());
  38   target->set_title(source.title());
  39   target->set_title_tags(source.title_tags());
  40   target->set_details(source.details());
  41   target->set_details_tags(source.details_tags());
  42 }
  43
  44 // Returns true if the "AppListMixer" trial is set to "Blended". This is an
  45 // experiment on the new Mixer logic that allows results from different groups
  46 // to be blended together, rather than stratified.
  47 bool IsBlendedMixerTrialEnabled() {
  48   // Note: It's important to query the field trial state first, to ensure that
  49   // UMA reports the correct group.
  50   const std::string group_name =
  51       base::FieldTrialList::FindFullName(kAppListMixerFieldTrialName);
  52
  53   if (base::CommandLine::ForCurrentProcess()->HasSwitch(
  54           switches::kDisableNewAppListMixer)) {
  55     return false;
  56   }
  57
  58   if (base::CommandLine::ForCurrentProcess()->HasSwitch(
  59           switches::kEnableNewAppListMixer)) {
  60     return true;
  61   }
  62
  63   return group_name == kAppListMixerFieldTrialEnabled;
  64 }
  65
  66 }  // namespace
  67
  68 Mixer::SortData::SortData() : result(NULL), score(0.0) {
  69 }
  70
  71 Mixer::SortData::SortData(SearchResult* result, double score)
  72     : result(result), score(score) {
  73 }
  74
  75 bool Mixer::SortData::operator<(const SortData& other) const {
  76   // This data precedes (less than) |other| if it has higher score.
  77   return score > other.score;
  78 }
  79
  80 // Used to group relevant providers together for mixing their results.
  81 class Mixer::Group {
  82  public:
  83   Group(size_t max_results, double boost, double multiplier)
  84       : max_results_(max_results), boost_(boost), multiplier_(multiplier) {}
  85   ~Group() {}
  86
  87   void AddProvider(SearchProvider* provider) { providers_.push_back(provider); }
  88
  89   void FetchResults(bool is_voice_query, const KnownResults& known_results) {
  90     results_.clear();
  91
  92     for (const SearchProvider* provider : providers_) {
  93       for (SearchResult* result : provider->results()) {
  94         DCHECK(!result->id().empty());
  95
  96         // We cannot rely on providers to give relevance scores in the range
  97         // [0.0, 1.0] (e.g., PeopleProvider directly gives values from the
  98         // Google+ API). Clamp to that range.
  99         double relevance = std::min(std::max(result->relevance(), 0.0), 1.0);
 100
 101         double multiplier = multiplier_;
 102         double boost = boost_;
 103         KnownResults::const_iterator known_it =
 104             known_results.find(result->id());
 105         if (known_it != known_results.end()) {
 106           switch (known_it->second) {
 107             case PERFECT_PRIMARY:
 108               boost = 4.0;
 109               break;
 110             case PREFIX_PRIMARY:
 111               boost = 3.75;
 112               break;
 113             case PERFECT_SECONDARY:
 114               boost = 3.25;
 115               break;
 116             case PREFIX_SECONDARY:
 117               boost = 3.0;
 118               break;
 119             case UNKNOWN_RESULT:
 120               NOTREACHED() << "Unknown result in KnownResults?";
 121               break;
 122           }
 123         }
 124
 125         // If this is a voice query, voice results receive a massive boost.
 126         if (is_voice_query && result->voice_result())
 127           boost += 4.0;
 128
 129         results_.push_back(SortData(result, relevance * multiplier + boost));
 130       }
 131     }
 132
 133     std::sort(results_.begin(), results_.end());
 134   }
 135
 136   const SortedResults& results() const { return results_; }
 137
 138   size_t max_results() const { return max_results_; }
 139
 140  private:
 141   typedef std::vector<SearchProvider*> Providers;
 142   const size_t max_results_;
 143   const double boost_;
 144   const double multiplier_;
 145
 146   Providers providers_;  // Not owned.
 147   SortedResults results_;
 148
 149   DISALLOW_COPY_AND_ASSIGN(Group);
 150 };
 151
 152 Mixer::Mixer(AppListModel::SearchResults* ui_results)
 153     : ui_results_(ui_results) {
 154 }
 155 Mixer::~Mixer() {
 156 }
 157
 158 size_t Mixer::AddGroup(size_t max_results, double boost, double multiplier) {
 159   // Only consider |boost| if the AppListMixer field trial is default.
 160   // Only consider |multiplier| if the AppListMixer field trial is "Blended".
 161   if (IsBlendedMixerTrialEnabled())
 162     boost = 0.0;
 163   else
 164     multiplier = 1.0;
 165   groups_.push_back(new Group(max_results, boost, multiplier));
 166   return groups_.size() - 1;
 167 }
 168
 169 size_t Mixer::AddOmniboxGroup(size_t max_results,
 170                               double boost,
 171                               double multiplier) {
 172   // There should not already be an omnibox group.
 173   DCHECK(!has_omnibox_group_);
 174   size_t id = AddGroup(max_results, boost, multiplier);
 175   omnibox_group_ = id;
 176   has_omnibox_group_ = true;
 177   return id;
 178 }
 179
 180 void Mixer::AddProviderToGroup(size_t group_id, SearchProvider* provider) {
 181   groups_[group_id]->AddProvider(provider);
 182 }
 183
 184 void Mixer::MixAndPublish(bool is_voice_query,
 185                           const KnownResults& known_results) {
 186   FetchResults(is_voice_query, known_results);
 187
 188   SortedResults results;
 189
 190   if (IsBlendedMixerTrialEnabled()) {
 191     results.reserve(kMinBlendedResults);
 192
 193     // Add results from each group. Limit to the maximum number of results in
 194     // each group.
 195     for (const Group* group : groups_) {
 196       size_t num_results =
 197           std::min(group->results().size(), group->max_results());
 198       results.insert(results.end(), group->results().begin(),
 199                      group->results().begin() + num_results);
 200     }
 201     // Remove results with duplicate IDs before sorting. If two providers give a
 202     // result with the same ID, the result from the provider with the *lower
 203     // group number* will be kept (e.g., an app result takes priority over a web
 204     // store result with the same ID).
 205     RemoveDuplicates(&results);
 206     std::sort(results.begin(), results.end());
 207
 208     if (results.size() < kMinBlendedResults) {
 209       size_t original_size = results.size();
 210       // We didn't get enough results. Insert all the results again, and this
 211       // time, do not limit the maximum number of results from each group. (This
 212       // will result in duplicates, which will be removed by RemoveDuplicates.)
 213       for (const Group* group : groups_) {
 214         results.insert(results.end(), group->results().begin(),
 215                        group->results().end());
 216       }
 217       RemoveDuplicates(&results);
 218       // Sort just the newly added results. This ensures that, for example, if
 219       // there are 6 Omnibox results (score = 0.8) and 1 People result (score =
 220       // 0.4) that the People result will be 5th, not 7th, because the Omnibox
 221       // group has a soft maximum of 4 results. (Otherwise, the People result
 222       // would not be seen at all once the result list is truncated.)
 223       std::sort(results.begin() + original_size, results.end());
 224     }
 225   } else {
 226     results.reserve(kMaxResults);
 227
 228     // Add results from non-omnibox groups first. Limit to the maximum number of
 229     // results in each group.
 230     for (size_t i = 0; i < groups_.size(); ++i) {
 231       if (!has_omnibox_group_ || i != omnibox_group_) {
 232         const Group& group = *groups_[i];
 233         size_t num_results =
 234             std::min(group.results().size(), group.max_results());
 235         results.insert(results.end(), group.results().begin(),
 236                        group.results().begin() + num_results);
 237       }
 238     }
 239
 240     // Collapse duplicate apps from local and web store.
 241     RemoveDuplicates(&results);
 242
 243     // Fill the remaining slots with omnibox results. Always add at least one
 244     // omnibox result (even if there are no more slots; if we over-fill the
 245     // vector, the web store and people results will be removed in a later
 246     // step). Note: max_results() is ignored for the omnibox group.
 247     if (has_omnibox_group_) {
 248       CHECK_LT(omnibox_group_, groups_.size());
 249       const Group& omnibox_group = *groups_[omnibox_group_];
 250       const size_t omnibox_results = std::min(
 251           omnibox_group.results().size(),
 252           results.size() < kMaxResults ? kMaxResults - results.size() : 1);
 253       results.insert(results.end(), omnibox_group.results().begin(),
 254                      omnibox_group.results().begin() + omnibox_results);
 255     }
 256
 257     std::sort(results.begin(), results.end());
 258     RemoveDuplicates(&results);
 259     if (results.size() > kMaxResults)
 260       results.resize(kMaxResults);
 261   }
 262
 263   Publish(results, ui_results_);
 264 }
 265
 266 void Mixer::Publish(const SortedResults& new_results,
 267                     AppListModel::SearchResults* ui_results) {
 268   typedef std::map<std::string, SearchResult*> IdToResultMap;
 269
 270   // The following algorithm is used:
 271   // 1. Transform the |ui_results| list into an unordered map from result ID
 272   // to item.
 273   // 2. Use the order of items in |new_results| to build an ordered list. If the
 274   // result IDs exist in the map, update and use the item in the map and delete
 275   // it from the map afterwards. Otherwise, clone new items from |new_results|.
 276   // 3. Delete the objects remaining in the map as they are unused.
 277
 278   // A map of the items in |ui_results| that takes ownership of the items.
 279   IdToResultMap ui_results_map;
 280   for (SearchResult* ui_result : *ui_results)
 281     ui_results_map[ui_result->id()] = ui_result;
 282   // We have to erase all results at once so that observers are notified with
 283   // meaningful indexes.
 284   ui_results->RemoveAll();
 285
 286   // Add items back to |ui_results| in the order of |new_results|.
 287   for (const SortData& sort_data : new_results) {
 288     const SearchResult& new_result = *sort_data.result;
 289     IdToResultMap::const_iterator ui_result_it =
 290         ui_results_map.find(new_result.id());
 291     if (ui_result_it != ui_results_map.end()) {
 292       // Update and use the old result if it exists.
 293       SearchResult* ui_result = ui_result_it->second;
 294       UpdateResult(new_result, ui_result);
 295       ui_result->set_relevance(sort_data.score);
 296
 297       // |ui_results| takes back ownership from |ui_results_map| here.
 298       ui_results->Add(ui_result);
 299
 300       // Remove the item from the map so that it ends up only with unused
 301       // results.
 302       ui_results_map.erase(ui_result->id());
 303     } else {
 304       scoped_ptr<SearchResult> result_copy = new_result.Duplicate();
 305       result_copy->set_relevance(sort_data.score);
 306       // Copy the result from |new_results| otherwise.
 307       ui_results->Add(result_copy.release());
 308     }
 309   }
 310
 311   // Delete the results remaining in the map as they are not in the new results.
 312   for (const auto& ui_result : ui_results_map) {
 313     delete ui_result.second;
 314   }
 315 }
 316
 317 void Mixer::RemoveDuplicates(SortedResults* results) {
 318   SortedResults final;
 319   final.reserve(results->size());
 320
 321   std::set<std::string> id_set;
 322   for (const SortData& sort_data : *results) {
 323     const std::string& id = sort_data.result->id();
 324     if (id_set.find(id) != id_set.end())
 325       continue;
 326
 327     id_set.insert(id);
 328     final.push_back(sort_data);
 329   }
 330
 331   results->swap(final);
 332 }
 333
 334 void Mixer::FetchResults(bool is_voice_query,
 335                          const KnownResults& known_results) {
 336   for (auto* group : groups_)
 337     group->FetchResults(is_voice_query, known_results);
 338 }
 339
 340 }  // namespace app_list