| OLD | NEW |
| 1 // Copyright 2013 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "ui/app_list/search/mixer.h" | 5 #include "ui/app_list/search/mixer.h" |
| 6 | 6 |
| 7 #include <algorithm> | 7 #include <algorithm> |
| 8 #include <map> | 8 #include <map> |
| 9 #include <set> | 9 #include <set> |
| 10 #include <string> | 10 #include <string> |
| 11 #include <vector> | 11 #include <vector> |
| 12 | 12 |
| 13 #include "base/command_line.h" | |
| 14 #include "base/macros.h" | 13 #include "base/macros.h" |
| 15 #include "base/metrics/field_trial.h" | |
| 16 #include "ui/app_list/app_list_switches.h" | |
| 17 #include "ui/app_list/search_provider.h" | 14 #include "ui/app_list/search_provider.h" |
| 18 #include "ui/app_list/search_result.h" | 15 #include "ui/app_list/search_result.h" |
| 19 | 16 |
| 20 namespace app_list { | 17 namespace app_list { |
| 21 | 18 |
| 22 namespace { | 19 namespace { |
| 23 | 20 |
| 24 // Maximum number of results to show. Ignored if the AppListMixer field trial is | 21 // Maximum number of results to show. |
| 25 // "Blended". | 22 const size_t kMinResults = 6; |
| 26 const size_t kMaxResults = 6; | |
| 27 | |
| 28 // The minimum number of results to show, if the AppListMixer field trial is | |
| 29 // "Blended". If this quota is not reached, the per-group limitations are | |
| 30 // removed and we try again. (We may still not reach the minumum, but at least | |
| 31 // we tried.) Ignored if the field trial is off. | |
| 32 const size_t kMinBlendedResults = 6; | |
| 33 | |
| 34 const char kAppListMixerFieldTrialName[] = "AppListMixer"; | |
| 35 const char kAppListMixerFieldTrialEnabled[] = "Blended"; | |
| 36 const char kAppListMixerFieldTrialDisabled[] = "Control"; | |
| 37 | 23 |
| 38 void UpdateResult(const SearchResult& source, SearchResult* target) { | 24 void UpdateResult(const SearchResult& source, SearchResult* target) { |
| 39 target->set_display_type(source.display_type()); | 25 target->set_display_type(source.display_type()); |
| 40 target->set_title(source.title()); | 26 target->set_title(source.title()); |
| 41 target->set_title_tags(source.title_tags()); | 27 target->set_title_tags(source.title_tags()); |
| 42 target->set_details(source.details()); | 28 target->set_details(source.details()); |
| 43 target->set_details_tags(source.details_tags()); | 29 target->set_details_tags(source.details_tags()); |
| 44 } | 30 } |
| 45 | 31 |
| 46 // Returns true if the "AppListMixer" trial is set to "Blended". This is an | |
| 47 // experiment on the new Mixer logic that allows results from different groups | |
| 48 // to be blended together, rather than stratified. | |
| 49 bool IsBlendedMixerTrialEnabled() { | |
| 50 // Note: It's important to query the field trial state first, to ensure that | |
| 51 // UMA reports the correct group. | |
| 52 const std::string group_name = | |
| 53 base::FieldTrialList::FindFullName(kAppListMixerFieldTrialName); | |
| 54 | |
| 55 // Respect command-line flags first. | |
| 56 if (base::CommandLine::ForCurrentProcess()->HasSwitch( | |
| 57 switches::kDisableNewAppListMixer)) { | |
| 58 return false; | |
| 59 } | |
| 60 | |
| 61 if (base::CommandLine::ForCurrentProcess()->HasSwitch( | |
| 62 switches::kEnableNewAppListMixer)) { | |
| 63 return true; | |
| 64 } | |
| 65 | |
| 66 // Next, respect field-trial groups. | |
| 67 if (group_name == kAppListMixerFieldTrialEnabled) | |
| 68 return true; | |
| 69 | |
| 70 if (group_name == kAppListMixerFieldTrialDisabled) | |
| 71 return false; | |
| 72 | |
| 73 // By default, enable the new logic if the experimental app list is enabled. | |
| 74 return app_list::switches::IsExperimentalAppListEnabled(); | |
| 75 } | |
| 76 | |
| 77 } // namespace | 32 } // namespace |
| 78 | 33 |
| 79 Mixer::SortData::SortData() : result(NULL), score(0.0) { | 34 Mixer::SortData::SortData() : result(NULL), score(0.0) { |
| 80 } | 35 } |
| 81 | 36 |
| 82 Mixer::SortData::SortData(SearchResult* result, double score) | 37 Mixer::SortData::SortData(SearchResult* result, double score) |
| 83 : result(result), score(score) { | 38 : result(result), score(score) { |
| 84 } | 39 } |
| 85 | 40 |
| 86 bool Mixer::SortData::operator<(const SortData& other) const { | 41 bool Mixer::SortData::operator<(const SortData& other) const { |
| 87 // This data precedes (less than) |other| if it has higher score. | 42 // This data precedes (less than) |other| if it has higher score. |
| 88 return score > other.score; | 43 return score > other.score; |
| 89 } | 44 } |
| 90 | 45 |
| 91 // Used to group relevant providers together for mixing their results. | 46 // Used to group relevant providers together for mixing their results. |
| 92 class Mixer::Group { | 47 class Mixer::Group { |
| 93 public: | 48 public: |
| 94 Group(size_t max_results, double boost, double multiplier) | 49 Group(size_t max_results, double multiplier) |
| 95 : max_results_(max_results), boost_(boost), multiplier_(multiplier) {} | 50 : max_results_(max_results), multiplier_(multiplier) {} |
| 96 ~Group() {} | 51 ~Group() {} |
| 97 | 52 |
| 98 void AddProvider(SearchProvider* provider) { providers_.push_back(provider); } | 53 void AddProvider(SearchProvider* provider) { providers_.push_back(provider); } |
| 99 | 54 |
| 100 void FetchResults(bool is_voice_query, const KnownResults& known_results) { | 55 void FetchResults(bool is_voice_query, const KnownResults& known_results) { |
| 101 results_.clear(); | 56 results_.clear(); |
| 102 | 57 |
| 103 for (const SearchProvider* provider : providers_) { | 58 for (const SearchProvider* provider : providers_) { |
| 104 for (SearchResult* result : provider->results()) { | 59 for (SearchResult* result : provider->results()) { |
| 105 DCHECK(!result->id().empty()); | 60 DCHECK(!result->id().empty()); |
| 106 | 61 |
| 107 // We cannot rely on providers to give relevance scores in the range | 62 // We cannot rely on providers to give relevance scores in the range |
| 108 // [0.0, 1.0] (e.g., PeopleProvider directly gives values from the | 63 // [0.0, 1.0] (e.g., PeopleProvider directly gives values from the |
| 109 // Google+ API). Clamp to that range. | 64 // Google+ API). Clamp to that range. |
| 110 double relevance = std::min(std::max(result->relevance(), 0.0), 1.0); | 65 double relevance = std::min(std::max(result->relevance(), 0.0), 1.0); |
| 111 | 66 |
| 112 double multiplier = multiplier_; | 67 double multiplier = multiplier_; |
| 113 double boost = boost_; | 68 double boost = 0.0; |
| 114 | 69 |
| 115 // Recommendations should not be affected by query-to-launch correlation | 70 // Recommendations should not be affected by query-to-launch correlation |
| 116 // from KnownResults as it causes recommendations to become dominated by | 71 // from KnownResults as it causes recommendations to become dominated by |
| 117 // previously clicked results. This happens because the recommendation | 72 // previously clicked results. This happens because the recommendation |
| 118 // query is the empty string and the clicked results get forever | 73 // query is the empty string and the clicked results get forever |
| 119 // boosted. | 74 // boosted. |
| 120 if (result->display_type() != SearchResult::DISPLAY_RECOMMENDATION) { | 75 if (result->display_type() != SearchResult::DISPLAY_RECOMMENDATION) { |
| 121 KnownResults::const_iterator known_it = | 76 KnownResults::const_iterator known_it = |
| 122 known_results.find(result->id()); | 77 known_results.find(result->id()); |
| 123 if (known_it != known_results.end()) { | 78 if (known_it != known_results.end()) { |
| (...skipping 28 matching lines...) Expand all Loading... |
| 152 std::sort(results_.begin(), results_.end()); | 107 std::sort(results_.begin(), results_.end()); |
| 153 } | 108 } |
| 154 | 109 |
| 155 const SortedResults& results() const { return results_; } | 110 const SortedResults& results() const { return results_; } |
| 156 | 111 |
| 157 size_t max_results() const { return max_results_; } | 112 size_t max_results() const { return max_results_; } |
| 158 | 113 |
| 159 private: | 114 private: |
| 160 typedef std::vector<SearchProvider*> Providers; | 115 typedef std::vector<SearchProvider*> Providers; |
| 161 const size_t max_results_; | 116 const size_t max_results_; |
| 162 const double boost_; | |
| 163 const double multiplier_; | 117 const double multiplier_; |
| 164 | 118 |
| 165 Providers providers_; // Not owned. | 119 Providers providers_; // Not owned. |
| 166 SortedResults results_; | 120 SortedResults results_; |
| 167 | 121 |
| 168 DISALLOW_COPY_AND_ASSIGN(Group); | 122 DISALLOW_COPY_AND_ASSIGN(Group); |
| 169 }; | 123 }; |
| 170 | 124 |
| 171 Mixer::Mixer(AppListModel::SearchResults* ui_results) | 125 Mixer::Mixer(AppListModel::SearchResults* ui_results) |
| 172 : ui_results_(ui_results) { | 126 : ui_results_(ui_results) { |
| 173 } | 127 } |
| 174 Mixer::~Mixer() { | 128 Mixer::~Mixer() { |
| 175 } | 129 } |
| 176 | 130 |
| 177 size_t Mixer::AddGroup(size_t max_results, double boost, double multiplier) { | 131 size_t Mixer::AddGroup(size_t max_results, double multiplier) { |
| 178 // Only consider |boost| if the AppListMixer field trial is default. | 132 groups_.push_back(new Group(max_results, multiplier)); |
| 179 // Only consider |multiplier| if the AppListMixer field trial is "Blended". | |
| 180 if (IsBlendedMixerTrialEnabled()) | |
| 181 boost = 0.0; | |
| 182 else | |
| 183 multiplier = 1.0; | |
| 184 groups_.push_back(new Group(max_results, boost, multiplier)); | |
| 185 return groups_.size() - 1; | 133 return groups_.size() - 1; |
| 186 } | 134 } |
| 187 | 135 |
| 188 size_t Mixer::AddOmniboxGroup(size_t max_results, | |
| 189 double boost, | |
| 190 double multiplier) { | |
| 191 // There should not already be an omnibox group. | |
| 192 DCHECK(!has_omnibox_group_); | |
| 193 size_t id = AddGroup(max_results, boost, multiplier); | |
| 194 omnibox_group_ = id; | |
| 195 has_omnibox_group_ = true; | |
| 196 return id; | |
| 197 } | |
| 198 | |
| 199 void Mixer::AddProviderToGroup(size_t group_id, SearchProvider* provider) { | 136 void Mixer::AddProviderToGroup(size_t group_id, SearchProvider* provider) { |
| 200 groups_[group_id]->AddProvider(provider); | 137 groups_[group_id]->AddProvider(provider); |
| 201 } | 138 } |
| 202 | 139 |
| 203 void Mixer::MixAndPublish(bool is_voice_query, | 140 void Mixer::MixAndPublish(bool is_voice_query, |
| 204 const KnownResults& known_results) { | 141 const KnownResults& known_results) { |
| 205 FetchResults(is_voice_query, known_results); | 142 FetchResults(is_voice_query, known_results); |
| 206 | 143 |
| 207 SortedResults results; | 144 SortedResults results; |
| 145 results.reserve(kMinResults); |
| 208 | 146 |
| 209 if (IsBlendedMixerTrialEnabled()) { | 147 // Add results from each group. Limit to the maximum number of results in each |
| 210 results.reserve(kMinBlendedResults); | 148 // group. |
| 149 for (const Group* group : groups_) { |
| 150 size_t num_results = |
| 151 std::min(group->results().size(), group->max_results()); |
| 152 results.insert(results.end(), group->results().begin(), |
| 153 group->results().begin() + num_results); |
| 154 } |
| 155 // Remove results with duplicate IDs before sorting. If two providers give a |
| 156 // result with the same ID, the result from the provider with the *lower group |
| 157 // number* will be kept (e.g., an app result takes priority over a web store |
| 158 // result with the same ID). |
| 159 RemoveDuplicates(&results); |
| 160 std::sort(results.begin(), results.end()); |
| 211 | 161 |
| 212 // Add results from each group. Limit to the maximum number of results in | 162 if (results.size() < kMinResults) { |
| 213 // each group. | 163 size_t original_size = results.size(); |
| 164 // We didn't get enough results. Insert all the results again, and this |
| 165 // time, do not limit the maximum number of results from each group. (This |
| 166 // will result in duplicates, which will be removed by RemoveDuplicates.) |
| 214 for (const Group* group : groups_) { | 167 for (const Group* group : groups_) { |
| 215 size_t num_results = | |
| 216 std::min(group->results().size(), group->max_results()); | |
| 217 results.insert(results.end(), group->results().begin(), | 168 results.insert(results.end(), group->results().begin(), |
| 218 group->results().begin() + num_results); | 169 group->results().end()); |
| 219 } | 170 } |
| 220 // Remove results with duplicate IDs before sorting. If two providers give a | |
| 221 // result with the same ID, the result from the provider with the *lower | |
| 222 // group number* will be kept (e.g., an app result takes priority over a web | |
| 223 // store result with the same ID). | |
| 224 RemoveDuplicates(&results); | 171 RemoveDuplicates(&results); |
| 225 std::sort(results.begin(), results.end()); | 172 // Sort just the newly added results. This ensures that, for example, if |
| 226 | 173 // there are 6 Omnibox results (score = 0.8) and 1 People result (score = |
| 227 if (results.size() < kMinBlendedResults) { | 174 // 0.4) that the People result will be 5th, not 7th, because the Omnibox |
| 228 size_t original_size = results.size(); | 175 // group has a soft maximum of 4 results. (Otherwise, the People result |
| 229 // We didn't get enough results. Insert all the results again, and this | 176 // would not be seen at all once the result list is truncated.) |
| 230 // time, do not limit the maximum number of results from each group. (This | 177 std::sort(results.begin() + original_size, results.end()); |
| 231 // will result in duplicates, which will be removed by RemoveDuplicates.) | |
| 232 for (const Group* group : groups_) { | |
| 233 results.insert(results.end(), group->results().begin(), | |
| 234 group->results().end()); | |
| 235 } | |
| 236 RemoveDuplicates(&results); | |
| 237 // Sort just the newly added results. This ensures that, for example, if | |
| 238 // there are 6 Omnibox results (score = 0.8) and 1 People result (score = | |
| 239 // 0.4) that the People result will be 5th, not 7th, because the Omnibox | |
| 240 // group has a soft maximum of 4 results. (Otherwise, the People result | |
| 241 // would not be seen at all once the result list is truncated.) | |
| 242 std::sort(results.begin() + original_size, results.end()); | |
| 243 } | |
| 244 } else { | |
| 245 results.reserve(kMaxResults); | |
| 246 | |
| 247 // Add results from non-omnibox groups first. Limit to the maximum number of | |
| 248 // results in each group. | |
| 249 for (size_t i = 0; i < groups_.size(); ++i) { | |
| 250 if (!has_omnibox_group_ || i != omnibox_group_) { | |
| 251 const Group& group = *groups_[i]; | |
| 252 size_t num_results = | |
| 253 std::min(group.results().size(), group.max_results()); | |
| 254 results.insert(results.end(), group.results().begin(), | |
| 255 group.results().begin() + num_results); | |
| 256 } | |
| 257 } | |
| 258 | |
| 259 // Collapse duplicate apps from local and web store. | |
| 260 RemoveDuplicates(&results); | |
| 261 | |
| 262 // Fill the remaining slots with omnibox results. Always add at least one | |
| 263 // omnibox result (even if there are no more slots; if we over-fill the | |
| 264 // vector, the web store and people results will be removed in a later | |
| 265 // step). Note: max_results() is ignored for the omnibox group. | |
| 266 if (has_omnibox_group_) { | |
| 267 CHECK_LT(omnibox_group_, groups_.size()); | |
| 268 const Group& omnibox_group = *groups_[omnibox_group_]; | |
| 269 const size_t omnibox_results = std::min( | |
| 270 omnibox_group.results().size(), | |
| 271 results.size() < kMaxResults ? kMaxResults - results.size() : 1); | |
| 272 results.insert(results.end(), omnibox_group.results().begin(), | |
| 273 omnibox_group.results().begin() + omnibox_results); | |
| 274 } | |
| 275 | |
| 276 std::sort(results.begin(), results.end()); | |
| 277 RemoveDuplicates(&results); | |
| 278 if (results.size() > kMaxResults) | |
| 279 results.resize(kMaxResults); | |
| 280 } | 178 } |
| 281 | 179 |
| 282 Publish(results, ui_results_); | 180 Publish(results, ui_results_); |
| 283 } | 181 } |
| 284 | 182 |
| 285 void Mixer::Publish(const SortedResults& new_results, | 183 void Mixer::Publish(const SortedResults& new_results, |
| 286 AppListModel::SearchResults* ui_results) { | 184 AppListModel::SearchResults* ui_results) { |
| 287 typedef std::map<std::string, SearchResult*> IdToResultMap; | 185 typedef std::map<std::string, SearchResult*> IdToResultMap; |
| 288 | 186 |
| 289 // The following algorithm is used: | 187 // The following algorithm is used: |
| (...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 350 results->swap(final); | 248 results->swap(final); |
| 351 } | 249 } |
| 352 | 250 |
| 353 void Mixer::FetchResults(bool is_voice_query, | 251 void Mixer::FetchResults(bool is_voice_query, |
| 354 const KnownResults& known_results) { | 252 const KnownResults& known_results) { |
| 355 for (auto* group : groups_) | 253 for (auto* group : groups_) |
| 356 group->FetchResults(is_voice_query, known_results); | 254 group->FetchResults(is_voice_query, known_results); |
| 357 } | 255 } |
| 358 | 256 |
| 359 } // namespace app_list | 257 } // namespace app_list |
| OLD | NEW |