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 |