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 "ui/app_list/search_provider.h"
  14 #include "ui/app_list/search_result.h"
  15
  16 namespace app_list {
  17
  18 namespace {
  19
  20 // Maximum number of results to show.
  21 const size_t kMaxResults = 6;
  22 const size_t kMaxMainGroupResults = 4;
  23 const size_t kMaxWebstoreResults = 2;
  24 const size_t kMaxPeopleResults = 2;
  25 const size_t kMaxSuggestionsResults = 6;
  26
  27 // A value to indicate no max number of results limit.
  28 const size_t kNoMaxResultsLimit = 0;
  29
  30 void UpdateResult(const SearchResult& source, SearchResult* target) {
  31   target->set_display_type(source.display_type());
  32   target->set_title(source.title());
  33   target->set_title_tags(source.title_tags());
  34   target->set_details(source.details());
  35   target->set_details_tags(source.details_tags());
  36 }
  37
  38 }  // namespace
  39
  40 Mixer::SortData::SortData() : result(NULL), score(0.0) {
  41 }
  42
  43 Mixer::SortData::SortData(SearchResult* result, double score)
  44     : result(result), score(score) {
  45 }
  46
  47 bool Mixer::SortData::operator<(const SortData& other) const {
  48   // This data precedes (less than) |other| if it has higher score.
  49   return score > other.score;
  50 }
  51
  52 // Used to group relevant providers together fox mixing their results.
  53 class Mixer::Group {
  54  public:
  55   Group(size_t max_results, double boost)
  56       : max_results_(max_results), boost_(boost) {}
  57   ~Group() {}
  58
  59   void AddProvider(SearchProvider* provider) { providers_.push_back(provider); }
  60
  61   void FetchResults(bool is_voice_query, const KnownResults& known_results) {
  62     results_.clear();
  63
  64     for (const SearchProvider* provider : providers_) {
  65       for (SearchResult* result : provider->results()) {
  66         DCHECK(!result->id().empty());
  67
  68         // We cannot rely on providers to give relevance scores in the range
  69         // [0.0, 1.0] (e.g., PeopleProvider directly gives values from the
  70         // Google+ API). Clamp to that range.
  71         double relevance = std::min(std::max(result->relevance(), 0.0), 1.0);
  72
  73         double boost = boost_;
  74         KnownResults::const_iterator known_it =
  75             known_results.find(result->id());
  76         if (known_it != known_results.end()) {
  77           switch (known_it->second) {
  78             case PERFECT_PRIMARY:
  79               boost = 4.0;
  80               break;
  81             case PREFIX_PRIMARY:
  82               boost = 3.75;
  83               break;
  84             case PERFECT_SECONDARY:
  85               boost = 3.25;
  86               break;
  87             case PREFIX_SECONDARY:
  88               boost = 3.0;
  89               break;
  90             case UNKNOWN_RESULT:
  91               NOTREACHED() << "Unknown result in KnownResults?";
  92               break;
  93           }
  94         }
  95
  96         // If this is a voice query, voice results receive a massive boost.
  97         if (is_voice_query && result->voice_result())
  98           boost += 4.0;
  99
 100         results_.push_back(SortData(result, relevance + boost));
 101       }
 102     }
 103
 104     std::sort(results_.begin(), results_.end());
 105     if (max_results_ != kNoMaxResultsLimit && results_.size() > max_results_)
 106       results_.resize(max_results_);
 107   }
 108
 109   const SortedResults& results() const { return results_; }
 110
 111  private:
 112   typedef std::vector<SearchProvider*> Providers;
 113   const size_t max_results_;
 114   const double boost_;
 115
 116   Providers providers_;  // Not owned.
 117   SortedResults results_;
 118
 119   DISALLOW_COPY_AND_ASSIGN(Group);
 120 };
 121
 122 Mixer::Mixer(AppListModel::SearchResults* ui_results)
 123     : ui_results_(ui_results) {
 124 }
 125 Mixer::~Mixer() {
 126 }
 127
 128 void Mixer::Init() {
 129   groups_[MAIN_GROUP].reset(new Group(kMaxMainGroupResults, 3.0));
 130   groups_[OMNIBOX_GROUP].reset(new Group(kNoMaxResultsLimit, 2.0));
 131   groups_[WEBSTORE_GROUP].reset(new Group(kMaxWebstoreResults, 1.0));
 132   groups_[PEOPLE_GROUP].reset(new Group(kMaxPeopleResults, 0.0));
 133   groups_[SUGGESTIONS_GROUP].reset(new Group(kMaxSuggestionsResults, 3.0));
 134 }
 135
 136 void Mixer::AddProviderToGroup(GroupId group, SearchProvider* provider) {
 137   groups_[group]->AddProvider(provider);
 138 }
 139
 140 void Mixer::MixAndPublish(bool is_voice_query,
 141                           const KnownResults& known_results) {
 142   FetchResults(is_voice_query, known_results);
 143
 144   SortedResults results;
 145   results.reserve(kMaxResults);
 146
 147   const Group& main_group = *groups_[MAIN_GROUP];
 148   const Group& omnibox_group = *groups_[OMNIBOX_GROUP];
 149   const Group& webstore_group = *groups_[WEBSTORE_GROUP];
 150   const Group& people_group = *groups_[PEOPLE_GROUP];
 151   const Group& suggestions_group = *groups_[SUGGESTIONS_GROUP];
 152
 153   // Adds main group and web store results first.
 154   results.insert(results.end(), main_group.results().begin(),
 155                  main_group.results().end());
 156   results.insert(results.end(), webstore_group.results().begin(),
 157                  webstore_group.results().end());
 158   results.insert(results.end(), people_group.results().begin(),
 159                  people_group.results().end());
 160   results.insert(results.end(), suggestions_group.results().begin(),
 161                  suggestions_group.results().end());
 162
 163   // Collapse duplicate apps from local and web store.
 164   RemoveDuplicates(&results);
 165
 166   // Fill the remaining slots with omnibox results. Always add at least one
 167   // omnibox result (even if there are no more slots; if we over-fill the
 168   // vector, the web store and people results will be removed in a later step).
 169   const size_t omnibox_results =
 170       std::min(omnibox_group.results().size(),
 171                results.size() < kMaxResults ? kMaxResults - results.size() : 1);
 172   results.insert(results.end(), omnibox_group.results().begin(),
 173                  omnibox_group.results().begin() + omnibox_results);
 174
 175   std::sort(results.begin(), results.end());
 176   RemoveDuplicates(&results);
 177   if (results.size() > kMaxResults)
 178     results.resize(kMaxResults);
 179
 180   Publish(results, ui_results_);
 181 }
 182
 183 void Mixer::Publish(const SortedResults& new_results,
 184                     AppListModel::SearchResults* ui_results) {
 185   typedef std::map<std::string, SearchResult*> IdToResultMap;
 186
 187   // The following algorithm is used:
 188   // 1. Transform the |ui_results| list into an unordered map from result ID
 189   // to item.
 190   // 2. Use the order of items in |new_results| to build an ordered list. If the
 191   // result IDs exist in the map, update and use the item in the map and delete
 192   // it from the map afterwards. Otherwise, clone new items from |new_results|.
 193   // 3. Delete the objects remaining in the map as they are unused.
 194
 195   // A map of the items in |ui_results| that takes ownership of the items.
 196   IdToResultMap ui_results_map;
 197   for (SearchResult* ui_result : *ui_results)
 198     ui_results_map[ui_result->id()] = ui_result;
 199   // We have to erase all results at once so that observers are notified with
 200   // meaningful indexes.
 201   ui_results->RemoveAll();
 202
 203   // Add items back to |ui_results| in the order of |new_results|.
 204   for (const SortData& sort_data : new_results) {
 205     const SearchResult& new_result = *sort_data.result;
 206     IdToResultMap::const_iterator ui_result_it =
 207         ui_results_map.find(new_result.id());
 208     if (ui_result_it != ui_results_map.end()) {
 209       // Update and use the old result if it exists.
 210       SearchResult* ui_result = ui_result_it->second;
 211       UpdateResult(new_result, ui_result);
 212       ui_result->set_relevance(sort_data.score);
 213
 214       // |ui_results| takes back ownership from |ui_results_map| here.
 215       ui_results->Add(ui_result);
 216
 217       // Remove the item from the map so that it ends up only with unused
 218       // results.
 219       ui_results_map.erase(ui_result->id());
 220     } else {
 221       scoped_ptr<SearchResult> result_copy = new_result.Duplicate();
 222       result_copy->set_relevance(sort_data.score);
 223       // Copy the result from |new_results| otherwise.
 224       ui_results->Add(result_copy.release());
 225     }
 226   }
 227
 228   // Delete the results remaining in the map as they are not in the new results.
 229   for (const auto& ui_result : ui_results_map) {
 230     delete ui_result.second;
 231   }
 232 }
 233
 234 void Mixer::RemoveDuplicates(SortedResults* results) {
 235   SortedResults final;
 236   final.reserve(results->size());
 237
 238   std::set<std::string> id_set;
 239   for (const SortData& sort_data : *results) {
 240     const std::string& id = sort_data.result->id();
 241     if (id_set.find(id) != id_set.end())
 242       continue;
 243
 244     id_set.insert(id);
 245     final.push_back(sort_data);
 246   }
 247
 248   results->swap(final);
 249 }
 250
 251 void Mixer::FetchResults(bool is_voice_query,
 252                          const KnownResults& known_results) {
 253   for (const auto& item : groups_)
 254     item.second->FetchResults(is_voice_query, known_results);
 255 }
 256
 257 }  // namespace app_list