OLD | NEW |
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2012 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 "chrome/browser/autocomplete/shortcuts_provider.h" | 5 #include "chrome/browser/autocomplete/shortcuts_provider.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 #include <cmath> | 8 #include <cmath> |
9 #include <map> | 9 #include <map> |
10 #include <vector> | 10 #include <vector> |
(...skipping 116 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
127 initialized_ = true; | 127 initialized_ = true; |
128 } | 128 } |
129 | 129 |
130 void ShortcutsProvider::GetMatches(const AutocompleteInput& input) { | 130 void ShortcutsProvider::GetMatches(const AutocompleteInput& input) { |
131 scoped_refptr<history::ShortcutsBackend> backend = | 131 scoped_refptr<history::ShortcutsBackend> backend = |
132 ShortcutsBackendFactory::GetForProfileIfExists(profile_); | 132 ShortcutsBackendFactory::GetForProfileIfExists(profile_); |
133 if (!backend.get()) | 133 if (!backend.get()) |
134 return; | 134 return; |
135 // Get the URLs from the shortcuts database with keys that partially or | 135 // Get the URLs from the shortcuts database with keys that partially or |
136 // completely match the search term. | 136 // completely match the search term. |
137 string16 term_string(base::i18n::ToLower(input.text())); | 137 base::string16 term_string(base::i18n::ToLower(input.text())); |
138 DCHECK(!term_string.empty()); | 138 DCHECK(!term_string.empty()); |
139 | 139 |
140 int max_relevance; | 140 int max_relevance; |
141 if (!OmniboxFieldTrial::ShortcutsScoringMaxRelevance( | 141 if (!OmniboxFieldTrial::ShortcutsScoringMaxRelevance( |
142 input.current_page_classification(), &max_relevance)) | 142 input.current_page_classification(), &max_relevance)) |
143 max_relevance = AutocompleteResult::kLowestDefaultScore - 1; | 143 max_relevance = AutocompleteResult::kLowestDefaultScore - 1; |
144 | 144 |
145 for (history::ShortcutsBackend::ShortcutMap::const_iterator it = | 145 for (history::ShortcutsBackend::ShortcutMap::const_iterator it = |
146 FindFirstMatch(term_string, backend.get()); | 146 FindFirstMatch(term_string, backend.get()); |
147 it != backend->shortcuts_map().end() && | 147 it != backend->shortcuts_map().end() && |
(...skipping 28 matching lines...) Expand all Loading... |
176 max_relevance = std::min(max_relevance, it->relevance); | 176 max_relevance = std::min(max_relevance, it->relevance); |
177 it->relevance = max_relevance; | 177 it->relevance = max_relevance; |
178 if (max_relevance > 1) | 178 if (max_relevance > 1) |
179 --max_relevance; | 179 --max_relevance; |
180 } | 180 } |
181 } | 181 } |
182 } | 182 } |
183 | 183 |
184 AutocompleteMatch ShortcutsProvider::ShortcutToACMatch( | 184 AutocompleteMatch ShortcutsProvider::ShortcutToACMatch( |
185 int relevance, | 185 int relevance, |
186 const string16& term_string, | 186 const base::string16& term_string, |
187 const history::ShortcutsBackend::Shortcut& shortcut) { | 187 const history::ShortcutsBackend::Shortcut& shortcut) { |
188 DCHECK(!term_string.empty()); | 188 DCHECK(!term_string.empty()); |
189 AutocompleteMatch match(shortcut.match_core.ToMatch()); | 189 AutocompleteMatch match(shortcut.match_core.ToMatch()); |
190 match.provider = this; | 190 match.provider = this; |
191 match.relevance = relevance; | 191 match.relevance = relevance; |
192 match.deletable = true; | 192 match.deletable = true; |
193 DCHECK(match.destination_url.is_valid()); | 193 DCHECK(match.destination_url.is_valid()); |
194 match.RecordAdditionalInfo("number of hits", shortcut.number_of_hits); | 194 match.RecordAdditionalInfo("number of hits", shortcut.number_of_hits); |
195 match.RecordAdditionalInfo("last access time", shortcut.last_access_time); | 195 match.RecordAdditionalInfo("last access time", shortcut.last_access_time); |
196 match.RecordAdditionalInfo("original input text", UTF16ToUTF8(shortcut.text)); | 196 match.RecordAdditionalInfo("original input text", UTF16ToUTF8(shortcut.text)); |
197 | 197 |
198 // Try to mark pieces of the contents and description as matches if they | 198 // Try to mark pieces of the contents and description as matches if they |
199 // appear in |term_string|. | 199 // appear in |term_string|. |
200 WordMap terms_map(CreateWordMapForString(term_string)); | 200 WordMap terms_map(CreateWordMapForString(term_string)); |
201 if (!terms_map.empty()) { | 201 if (!terms_map.empty()) { |
202 match.contents_class = ClassifyAllMatchesInString(term_string, terms_map, | 202 match.contents_class = ClassifyAllMatchesInString(term_string, terms_map, |
203 match.contents, match.contents_class); | 203 match.contents, match.contents_class); |
204 match.description_class = ClassifyAllMatchesInString(term_string, terms_map, | 204 match.description_class = ClassifyAllMatchesInString(term_string, terms_map, |
205 match.description, match.description_class); | 205 match.description, match.description_class); |
206 } | 206 } |
207 return match; | 207 return match; |
208 } | 208 } |
209 | 209 |
210 // static | 210 // static |
211 ShortcutsProvider::WordMap ShortcutsProvider::CreateWordMapForString( | 211 ShortcutsProvider::WordMap ShortcutsProvider::CreateWordMapForString( |
212 const string16& text) { | 212 const base::string16& text) { |
213 // First, convert |text| to a vector of the unique words in it. | 213 // First, convert |text| to a vector of the unique words in it. |
214 WordMap word_map; | 214 WordMap word_map; |
215 base::i18n::BreakIterator word_iter(text, | 215 base::i18n::BreakIterator word_iter(text, |
216 base::i18n::BreakIterator::BREAK_WORD); | 216 base::i18n::BreakIterator::BREAK_WORD); |
217 if (!word_iter.Init()) | 217 if (!word_iter.Init()) |
218 return word_map; | 218 return word_map; |
219 std::vector<string16> words; | 219 std::vector<string16> words; |
220 while (word_iter.Advance()) { | 220 while (word_iter.Advance()) { |
221 if (word_iter.IsWord()) | 221 if (word_iter.IsWord()) |
222 words.push_back(word_iter.GetString()); | 222 words.push_back(word_iter.GetString()); |
(...skipping 10 matching lines...) Expand all Loading... |
233 // existing implementations that found that it was already true everywhere.) | 233 // existing implementations that found that it was already true everywhere.) |
234 std::reverse(words.begin(), words.end()); | 234 std::reverse(words.begin(), words.end()); |
235 for (std::vector<string16>::const_iterator i(words.begin()); i != words.end(); | 235 for (std::vector<string16>::const_iterator i(words.begin()); i != words.end(); |
236 ++i) | 236 ++i) |
237 word_map.insert(std::make_pair((*i)[0], *i)); | 237 word_map.insert(std::make_pair((*i)[0], *i)); |
238 return word_map; | 238 return word_map; |
239 } | 239 } |
240 | 240 |
241 // static | 241 // static |
242 ACMatchClassifications ShortcutsProvider::ClassifyAllMatchesInString( | 242 ACMatchClassifications ShortcutsProvider::ClassifyAllMatchesInString( |
243 const string16& find_text, | 243 const base::string16& find_text, |
244 const WordMap& find_words, | 244 const WordMap& find_words, |
245 const string16& text, | 245 const base::string16& text, |
246 const ACMatchClassifications& original_class) { | 246 const ACMatchClassifications& original_class) { |
247 DCHECK(!find_text.empty()); | 247 DCHECK(!find_text.empty()); |
248 DCHECK(!find_words.empty()); | 248 DCHECK(!find_words.empty()); |
249 | 249 |
250 // The code below assumes |text| is nonempty and therefore the resulting | 250 // The code below assumes |text| is nonempty and therefore the resulting |
251 // classification vector should always be nonempty as well. Returning early | 251 // classification vector should always be nonempty as well. Returning early |
252 // if |text| is empty assures we'll return the (correct) empty vector rather | 252 // if |text| is empty assures we'll return the (correct) empty vector rather |
253 // than a vector with a single (0, NONE) match. | 253 // than a vector with a single (0, NONE) match. |
254 if (text.empty()) | 254 if (text.empty()) |
255 return original_class; | 255 return original_class; |
256 | 256 |
257 // First check whether |text| begins with |find_text| and mark that whole | 257 // First check whether |text| begins with |find_text| and mark that whole |
258 // section as a match if so. | 258 // section as a match if so. |
259 string16 text_lowercase(base::i18n::ToLower(text)); | 259 base::string16 text_lowercase(base::i18n::ToLower(text)); |
260 ACMatchClassifications match_class; | 260 ACMatchClassifications match_class; |
261 size_t last_position = 0; | 261 size_t last_position = 0; |
262 if (StartsWith(text_lowercase, find_text, true)) { | 262 if (StartsWith(text_lowercase, find_text, true)) { |
263 match_class.push_back( | 263 match_class.push_back( |
264 ACMatchClassification(0, ACMatchClassification::MATCH)); | 264 ACMatchClassification(0, ACMatchClassification::MATCH)); |
265 last_position = find_text.length(); | 265 last_position = find_text.length(); |
266 // If |text_lowercase| is actually equal to |find_text|, we don't need to | 266 // If |text_lowercase| is actually equal to |find_text|, we don't need to |
267 // (and in fact shouldn't) put a trailing NONE classification after the end | 267 // (and in fact shouldn't) put a trailing NONE classification after the end |
268 // of the string. | 268 // of the string. |
269 if (last_position < text_lowercase.length()) { | 269 if (last_position < text_lowercase.length()) { |
(...skipping 13 matching lines...) Expand all Loading... |
283 // of |text_lowercase| beginning with |last_position|. Accept the first | 283 // of |text_lowercase| beginning with |last_position|. Accept the first |
284 // matching word found (which should be the longest possible match at this | 284 // matching word found (which should be the longest possible match at this |
285 // location, given the construction of |find_words|) and add a MATCH region to | 285 // location, given the construction of |find_words|) and add a MATCH region to |
286 // |match_class|, moving |last_position| to be after the matching word. If we | 286 // |match_class|, moving |last_position| to be after the matching word. If we |
287 // found no matching words, move to the next character and repeat. | 287 // found no matching words, move to the next character and repeat. |
288 while (last_position < text_lowercase.length()) { | 288 while (last_position < text_lowercase.length()) { |
289 std::pair<WordMap::const_iterator, WordMap::const_iterator> range( | 289 std::pair<WordMap::const_iterator, WordMap::const_iterator> range( |
290 find_words.equal_range(text_lowercase[last_position])); | 290 find_words.equal_range(text_lowercase[last_position])); |
291 size_t next_character = last_position + 1; | 291 size_t next_character = last_position + 1; |
292 for (WordMap::const_iterator i(range.first); i != range.second; ++i) { | 292 for (WordMap::const_iterator i(range.first); i != range.second; ++i) { |
293 const string16& word = i->second; | 293 const base::string16& word = i->second; |
294 size_t word_end = last_position + word.length(); | 294 size_t word_end = last_position + word.length(); |
295 if ((word_end <= text_lowercase.length()) && | 295 if ((word_end <= text_lowercase.length()) && |
296 !text_lowercase.compare(last_position, word.length(), word)) { | 296 !text_lowercase.compare(last_position, word.length(), word)) { |
297 // Collapse adjacent ranges into one. | 297 // Collapse adjacent ranges into one. |
298 if (match_class.back().offset == last_position) | 298 if (match_class.back().offset == last_position) |
299 match_class.pop_back(); | 299 match_class.pop_back(); |
300 | 300 |
301 AutocompleteMatch::AddLastClassificationIfNecessary(&match_class, | 301 AutocompleteMatch::AddLastClassificationIfNecessary(&match_class, |
302 last_position, ACMatchClassification::MATCH); | 302 last_position, ACMatchClassification::MATCH); |
303 if (word_end < text_lowercase.length()) { | 303 if (word_end < text_lowercase.length()) { |
304 match_class.push_back( | 304 match_class.push_back( |
305 ACMatchClassification(word_end, ACMatchClassification::NONE)); | 305 ACMatchClassification(word_end, ACMatchClassification::NONE)); |
306 } | 306 } |
307 last_position = word_end; | 307 last_position = word_end; |
308 break; | 308 break; |
309 } | 309 } |
310 } | 310 } |
311 last_position = std::max(last_position, next_character); | 311 last_position = std::max(last_position, next_character); |
312 } | 312 } |
313 | 313 |
314 return AutocompleteMatch::MergeClassifications(original_class, match_class); | 314 return AutocompleteMatch::MergeClassifications(original_class, match_class); |
315 } | 315 } |
316 | 316 |
317 history::ShortcutsBackend::ShortcutMap::const_iterator | 317 history::ShortcutsBackend::ShortcutMap::const_iterator |
318 ShortcutsProvider::FindFirstMatch(const string16& keyword, | 318 ShortcutsProvider::FindFirstMatch(const base::string16& keyword, |
319 history::ShortcutsBackend* backend) { | 319 history::ShortcutsBackend* backend) { |
320 DCHECK(backend); | 320 DCHECK(backend); |
321 history::ShortcutsBackend::ShortcutMap::const_iterator it = | 321 history::ShortcutsBackend::ShortcutMap::const_iterator it = |
322 backend->shortcuts_map().lower_bound(keyword); | 322 backend->shortcuts_map().lower_bound(keyword); |
323 // Lower bound not necessarily matches the keyword, check for item pointed by | 323 // Lower bound not necessarily matches the keyword, check for item pointed by |
324 // the lower bound iterator to at least start with keyword. | 324 // the lower bound iterator to at least start with keyword. |
325 return ((it == backend->shortcuts_map().end()) || | 325 return ((it == backend->shortcuts_map().end()) || |
326 StartsWith(it->first, keyword, true)) ? it : | 326 StartsWith(it->first, keyword, true)) ? it : |
327 backend->shortcuts_map().end(); | 327 backend->shortcuts_map().end(); |
328 } | 328 } |
329 | 329 |
330 int ShortcutsProvider::CalculateScore( | 330 int ShortcutsProvider::CalculateScore( |
331 const string16& terms, | 331 const base::string16& terms, |
332 const history::ShortcutsBackend::Shortcut& shortcut, | 332 const history::ShortcutsBackend::Shortcut& shortcut, |
333 int max_relevance) { | 333 int max_relevance) { |
334 DCHECK(!terms.empty()); | 334 DCHECK(!terms.empty()); |
335 DCHECK_LE(terms.length(), shortcut.text.length()); | 335 DCHECK_LE(terms.length(), shortcut.text.length()); |
336 | 336 |
337 // The initial score is based on how much of the shortcut the user has typed. | 337 // The initial score is based on how much of the shortcut the user has typed. |
338 // Using the square root of the typed fraction boosts the base score rapidly | 338 // Using the square root of the typed fraction boosts the base score rapidly |
339 // as characters are typed, compared with simply using the typed fraction | 339 // as characters are typed, compared with simply using the typed fraction |
340 // directly. This makes sense since the first characters typed are much more | 340 // directly. This makes sense since the first characters typed are much more |
341 // important for determining how likely it is a user wants a particular | 341 // important for determining how likely it is a user wants a particular |
(...skipping 14 matching lines...) Expand all Loading... |
356 // (1.0 / each 5 additional hits), up to a maximum of 5x as long. | 356 // (1.0 / each 5 additional hits), up to a maximum of 5x as long. |
357 const double kMaxDecaySpeedDivisor = 5.0; | 357 const double kMaxDecaySpeedDivisor = 5.0; |
358 const double kNumUsesPerDecaySpeedDivisorIncrement = 5.0; | 358 const double kNumUsesPerDecaySpeedDivisorIncrement = 5.0; |
359 double decay_divisor = std::min(kMaxDecaySpeedDivisor, | 359 double decay_divisor = std::min(kMaxDecaySpeedDivisor, |
360 (shortcut.number_of_hits + kNumUsesPerDecaySpeedDivisorIncrement - 1) / | 360 (shortcut.number_of_hits + kNumUsesPerDecaySpeedDivisorIncrement - 1) / |
361 kNumUsesPerDecaySpeedDivisorIncrement); | 361 kNumUsesPerDecaySpeedDivisorIncrement); |
362 | 362 |
363 return static_cast<int>((base_score / exp(decay_exponent / decay_divisor)) + | 363 return static_cast<int>((base_score / exp(decay_exponent / decay_divisor)) + |
364 0.5); | 364 0.5); |
365 } | 365 } |
OLD | NEW |