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