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
3 // found in the LICENSE file.
4
5 #include "chrome/browser/autocomplete/autocomplete_match.h"
6
7 #include "base/i18n/time_formatting.h"
8 #include "base/logging.h"
9 #include "base/strings/string16.h"
10 #include "base/strings/string_number_conversions.h"
11 #include "base/strings/string_util.h"
12 #include "base/strings/utf_string_conversions.h"
13 #include "base/time/time.h"
14 #include "chrome/browser/autocomplete/autocomplete_provider.h"
15 #include "chrome/browser/search_engines/template_url.h"
16 #include "chrome/browser/search_engines/template_url_service.h"
17 #include "chrome/browser/search_engines/template_url_service_factory.h"
18 #include "chrome/browser/search_engines/ui_thread_search_terms_data.h"
19 #include "content/public/common/url_constants.h"
20 #include "grit/theme_resources.h"
21
22 namespace {
23
IsTrivialClassification(const ACMatchClassifications & classifications)24 bool IsTrivialClassification(const ACMatchClassifications& classifications) {
25 return classifications.empty() ||
26 ((classifications.size() == 1) &&
27 (classifications.back().style == ACMatchClassification::NONE));
28 }
29
30 } // namespace
31
32 // AutocompleteMatch ----------------------------------------------------------
33
34 // static
35 const base::char16 AutocompleteMatch::kInvalidChars[] = {
36 '\n', '\r', '\t',
37 0x2028, // Line separator
38 0x2029, // Paragraph separator
39 0
40 };
41
AutocompleteMatch()42 AutocompleteMatch::AutocompleteMatch()
43 : provider(NULL),
44 relevance(0),
45 typed_count(-1),
46 deletable(false),
47 allowed_to_be_default_match(false),
48 transition(content::PAGE_TRANSITION_GENERATED),
49 is_history_what_you_typed_match(false),
50 type(AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED),
51 starred(false),
52 from_previous(false) {
53 }
54
AutocompleteMatch(AutocompleteProvider * provider,int relevance,bool deletable,Type type)55 AutocompleteMatch::AutocompleteMatch(AutocompleteProvider* provider,
56 int relevance,
57 bool deletable,
58 Type type)
59 : provider(provider),
60 relevance(relevance),
61 typed_count(-1),
62 deletable(deletable),
63 allowed_to_be_default_match(false),
64 transition(content::PAGE_TRANSITION_TYPED),
65 is_history_what_you_typed_match(false),
66 type(type),
67 starred(false),
68 from_previous(false) {
69 }
70
AutocompleteMatch(const AutocompleteMatch & match)71 AutocompleteMatch::AutocompleteMatch(const AutocompleteMatch& match)
72 : provider(match.provider),
73 relevance(match.relevance),
74 typed_count(match.typed_count),
75 deletable(match.deletable),
76 fill_into_edit(match.fill_into_edit),
77 inline_autocompletion(match.inline_autocompletion),
78 allowed_to_be_default_match(match.allowed_to_be_default_match),
79 destination_url(match.destination_url),
80 stripped_destination_url(match.stripped_destination_url),
81 contents(match.contents),
82 contents_class(match.contents_class),
83 description(match.description),
84 description_class(match.description_class),
85 answer_contents(match.answer_contents),
86 answer_type(match.answer_type),
87 transition(match.transition),
88 is_history_what_you_typed_match(match.is_history_what_you_typed_match),
89 type(match.type),
90 associated_keyword(match.associated_keyword.get() ?
91 new AutocompleteMatch(*match.associated_keyword) : NULL),
92 keyword(match.keyword),
93 starred(match.starred),
94 from_previous(match.from_previous),
95 search_terms_args(match.search_terms_args.get() ?
96 new TemplateURLRef::SearchTermsArgs(*match.search_terms_args) :
97 NULL),
98 additional_info(match.additional_info),
99 duplicate_matches(match.duplicate_matches) {
100 }
101
~AutocompleteMatch()102 AutocompleteMatch::~AutocompleteMatch() {
103 }
104
operator =(const AutocompleteMatch & match)105 AutocompleteMatch& AutocompleteMatch::operator=(
106 const AutocompleteMatch& match) {
107 if (this == &match)
108 return *this;
109
110 provider = match.provider;
111 relevance = match.relevance;
112 typed_count = match.typed_count;
113 deletable = match.deletable;
114 fill_into_edit = match.fill_into_edit;
115 inline_autocompletion = match.inline_autocompletion;
116 allowed_to_be_default_match = match.allowed_to_be_default_match;
117 destination_url = match.destination_url;
118 stripped_destination_url = match.stripped_destination_url;
119 contents = match.contents;
120 contents_class = match.contents_class;
121 description = match.description;
122 description_class = match.description_class;
123 answer_contents = match.answer_contents;
124 answer_type = match.answer_type;
125 transition = match.transition;
126 is_history_what_you_typed_match = match.is_history_what_you_typed_match;
127 type = match.type;
128 associated_keyword.reset(match.associated_keyword.get() ?
129 new AutocompleteMatch(*match.associated_keyword) : NULL);
130 keyword = match.keyword;
131 starred = match.starred;
132 from_previous = match.from_previous;
133 search_terms_args.reset(match.search_terms_args.get() ?
134 new TemplateURLRef::SearchTermsArgs(*match.search_terms_args) : NULL);
135 additional_info = match.additional_info;
136 duplicate_matches = match.duplicate_matches;
137 return *this;
138 }
139
140 // static
TypeToIcon(Type type)141 int AutocompleteMatch::TypeToIcon(Type type) {
142 int icons[] = {
143 IDR_OMNIBOX_HTTP,
144 IDR_OMNIBOX_HTTP,
145 IDR_OMNIBOX_HTTP,
146 IDR_OMNIBOX_HTTP,
147 IDR_OMNIBOX_HTTP,
148 IDR_OMNIBOX_HTTP,
149 IDR_OMNIBOX_SEARCH,
150 IDR_OMNIBOX_SEARCH,
151 IDR_OMNIBOX_SEARCH,
152 IDR_OMNIBOX_SEARCH,
153 IDR_OMNIBOX_SEARCH,
154 IDR_OMNIBOX_SEARCH,
155 IDR_OMNIBOX_SEARCH,
156 IDR_OMNIBOX_SEARCH,
157 IDR_OMNIBOX_EXTENSION_APP,
158 IDR_OMNIBOX_SEARCH,
159 IDR_OMNIBOX_HTTP,
160 IDR_OMNIBOX_HTTP,
161 IDR_OMNIBOX_SEARCH,
162 };
163 COMPILE_ASSERT(arraysize(icons) == AutocompleteMatchType::NUM_TYPES,
164 icons_array_must_match_type_enum);
165 return icons[type];
166 }
167
168 // static
TypeToLocationBarIcon(Type type)169 int AutocompleteMatch::TypeToLocationBarIcon(Type type) {
170 int id = TypeToIcon(type);
171 if (id == IDR_OMNIBOX_HTTP)
172 return IDR_LOCATION_BAR_HTTP;
173 return id;
174 }
175
176 // static
MoreRelevant(const AutocompleteMatch & elem1,const AutocompleteMatch & elem2)177 bool AutocompleteMatch::MoreRelevant(const AutocompleteMatch& elem1,
178 const AutocompleteMatch& elem2) {
179 // For equal-relevance matches, we sort alphabetically, so that providers
180 // who return multiple elements at the same priority get a "stable" sort
181 // across multiple updates.
182 return (elem1.relevance == elem2.relevance) ?
183 (elem1.contents < elem2.contents) : (elem1.relevance > elem2.relevance);
184 }
185
186 // static
DestinationsEqual(const AutocompleteMatch & elem1,const AutocompleteMatch & elem2)187 bool AutocompleteMatch::DestinationsEqual(const AutocompleteMatch& elem1,
188 const AutocompleteMatch& elem2) {
189 if (elem1.stripped_destination_url.is_empty() &&
190 elem2.stripped_destination_url.is_empty())
191 return false;
192 return elem1.stripped_destination_url == elem2.stripped_destination_url;
193 }
194
195 // static
ClassifyMatchInString(const base::string16 & find_text,const base::string16 & text,int style,ACMatchClassifications * classification)196 void AutocompleteMatch::ClassifyMatchInString(
197 const base::string16& find_text,
198 const base::string16& text,
199 int style,
200 ACMatchClassifications* classification) {
201 ClassifyLocationInString(text.find(find_text), find_text.length(),
202 text.length(), style, classification);
203 }
204
205 // static
ClassifyLocationInString(size_t match_location,size_t match_length,size_t overall_length,int style,ACMatchClassifications * classification)206 void AutocompleteMatch::ClassifyLocationInString(
207 size_t match_location,
208 size_t match_length,
209 size_t overall_length,
210 int style,
211 ACMatchClassifications* classification) {
212 classification->clear();
213
214 // Don't classify anything about an empty string
215 // (AutocompleteMatch::Validate() checks this).
216 if (overall_length == 0)
217 return;
218
219 // Mark pre-match portion of string (if any).
220 if (match_location != 0) {
221 classification->push_back(ACMatchClassification(0, style));
222 }
223
224 // Mark matching portion of string.
225 if (match_location == base::string16::npos) {
226 // No match, above classification will suffice for whole string.
227 return;
228 }
229 // Classifying an empty match makes no sense and will lead to validation
230 // errors later.
231 DCHECK_GT(match_length, 0U);
232 classification->push_back(ACMatchClassification(match_location,
233 (style | ACMatchClassification::MATCH) & ~ACMatchClassification::DIM));
234
235 // Mark post-match portion of string (if any).
236 const size_t after_match(match_location + match_length);
237 if (after_match < overall_length) {
238 classification->push_back(ACMatchClassification(after_match, style));
239 }
240 }
241
242 // static
243 AutocompleteMatch::ACMatchClassifications
MergeClassifications(const ACMatchClassifications & classifications1,const ACMatchClassifications & classifications2)244 AutocompleteMatch::MergeClassifications(
245 const ACMatchClassifications& classifications1,
246 const ACMatchClassifications& classifications2) {
247 // We must return the empty vector only if both inputs are truly empty.
248 // The result of merging an empty vector with a single (0, NONE)
249 // classification is the latter one-entry vector.
250 if (IsTrivialClassification(classifications1))
251 return classifications2.empty() ? classifications1 : classifications2;
252 if (IsTrivialClassification(classifications2))
253 return classifications1;
254
255 ACMatchClassifications output;
256 for (ACMatchClassifications::const_iterator i = classifications1.begin(),
257 j = classifications2.begin(); i != classifications1.end();) {
258 AutocompleteMatch::AddLastClassificationIfNecessary(&output,
259 std::max(i->offset, j->offset), i->style | j->style);
260 const size_t next_i_offset = (i + 1) == classifications1.end() ?
261 static_cast<size_t>(-1) : (i + 1)->offset;
262 const size_t next_j_offset = (j + 1) == classifications2.end() ?
263 static_cast<size_t>(-1) : (j + 1)->offset;
264 if (next_i_offset >= next_j_offset)
265 ++j;
266 if (next_j_offset >= next_i_offset)
267 ++i;
268 }
269
270 return output;
271 }
272
273 // static
ClassificationsToString(const ACMatchClassifications & classifications)274 std::string AutocompleteMatch::ClassificationsToString(
275 const ACMatchClassifications& classifications) {
276 std::string serialized_classifications;
277 for (size_t i = 0; i < classifications.size(); ++i) {
278 if (i)
279 serialized_classifications += ',';
280 serialized_classifications += base::IntToString(classifications[i].offset) +
281 ',' + base::IntToString(classifications[i].style);
282 }
283 return serialized_classifications;
284 }
285
286 // static
ClassificationsFromString(const std::string & serialized_classifications)287 ACMatchClassifications AutocompleteMatch::ClassificationsFromString(
288 const std::string& serialized_classifications) {
289 ACMatchClassifications classifications;
290 std::vector<std::string> tokens;
291 Tokenize(serialized_classifications, ",", &tokens);
292 DCHECK(!(tokens.size() & 1)); // The number of tokens should be even.
293 for (size_t i = 0; i < tokens.size(); i += 2) {
294 int classification_offset = 0;
295 int classification_style = ACMatchClassification::NONE;
296 if (!base::StringToInt(tokens[i], &classification_offset) ||
297 !base::StringToInt(tokens[i + 1], &classification_style)) {
298 NOTREACHED();
299 return classifications;
300 }
301 classifications.push_back(ACMatchClassification(classification_offset,
302 classification_style));
303 }
304 return classifications;
305 }
306
307 // static
AddLastClassificationIfNecessary(ACMatchClassifications * classifications,size_t offset,int style)308 void AutocompleteMatch::AddLastClassificationIfNecessary(
309 ACMatchClassifications* classifications,
310 size_t offset,
311 int style) {
312 DCHECK(classifications);
313 if (classifications->empty() || classifications->back().style != style) {
314 DCHECK(classifications->empty() ||
315 (offset > classifications->back().offset));
316 classifications->push_back(ACMatchClassification(offset, style));
317 }
318 }
319
320 // static
SanitizeString(const base::string16 & text)321 base::string16 AutocompleteMatch::SanitizeString(const base::string16& text) {
322 // NOTE: This logic is mirrored by |sanitizeString()| in
323 // omnibox_custom_bindings.js.
324 base::string16 result;
325 base::TrimWhitespace(text, base::TRIM_LEADING, &result);
326 base::RemoveChars(result, kInvalidChars, &result);
327 return result;
328 }
329
330 // static
IsSearchType(Type type)331 bool AutocompleteMatch::IsSearchType(Type type) {
332 return type == AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED ||
333 type == AutocompleteMatchType::SEARCH_HISTORY ||
334 type == AutocompleteMatchType::SEARCH_SUGGEST ||
335 type == AutocompleteMatchType::SEARCH_OTHER_ENGINE ||
336 IsSpecializedSearchType(type);
337 }
338
339 // static
IsSpecializedSearchType(Type type)340 bool AutocompleteMatch::IsSpecializedSearchType(Type type) {
341 return type == AutocompleteMatchType::SEARCH_SUGGEST_ENTITY ||
342 type == AutocompleteMatchType::SEARCH_SUGGEST_INFINITE ||
343 type == AutocompleteMatchType::SEARCH_SUGGEST_PERSONALIZED ||
344 type == AutocompleteMatchType::SEARCH_SUGGEST_PROFILE ||
345 type == AutocompleteMatchType::SEARCH_SUGGEST_ANSWER;
346 }
347
ComputeStrippedDestinationURL(Profile * profile)348 void AutocompleteMatch::ComputeStrippedDestinationURL(Profile* profile) {
349 stripped_destination_url = destination_url;
350 if (!stripped_destination_url.is_valid())
351 return;
352
353 // If the destination URL looks like it was generated from a TemplateURL,
354 // remove all substitutions other than the search terms. This allows us
355 // to eliminate cases like past search URLs from history that differ only
356 // by some obscure query param from each other or from the search/keyword
357 // provider matches.
358 TemplateURL* template_url = GetTemplateURL(profile, true);
359 UIThreadSearchTermsData search_terms_data(profile);
360 if (template_url != NULL &&
361 template_url->SupportsReplacement(search_terms_data)) {
362 base::string16 search_terms;
363 if (template_url->ExtractSearchTermsFromURL(stripped_destination_url,
364 search_terms_data,
365 &search_terms)) {
366 stripped_destination_url =
367 GURL(template_url->url_ref().ReplaceSearchTerms(
368 TemplateURLRef::SearchTermsArgs(search_terms),
369 search_terms_data));
370 }
371 }
372
373 // |replacements| keeps all the substitions we're going to make to
374 // from {destination_url} to {stripped_destination_url}. |need_replacement|
375 // is a helper variable that helps us keep track of whether we need
376 // to apply the replacement.
377 bool needs_replacement = false;
378 GURL::Replacements replacements;
379
380 // Remove the www. prefix from the host.
381 static const char prefix[] = "www.";
382 static const size_t prefix_len = arraysize(prefix) - 1;
383 std::string host = stripped_destination_url.host();
384 if (host.compare(0, prefix_len, prefix) == 0) {
385 host = host.substr(prefix_len);
386 replacements.SetHostStr(host);
387 needs_replacement = true;
388 }
389
390 // Replace https protocol with http protocol.
391 if (stripped_destination_url.SchemeIs(url::kHttpsScheme)) {
392 replacements.SetScheme(url::kHttpScheme,
393 url::Component(0, strlen(url::kHttpScheme)));
394 needs_replacement = true;
395 }
396
397 if (needs_replacement)
398 stripped_destination_url = stripped_destination_url.ReplaceComponents(
399 replacements);
400 }
401
GetKeywordUIState(Profile * profile,base::string16 * keyword,bool * is_keyword_hint) const402 void AutocompleteMatch::GetKeywordUIState(Profile* profile,
403 base::string16* keyword,
404 bool* is_keyword_hint) const {
405 *is_keyword_hint = associated_keyword.get() != NULL;
406 keyword->assign(*is_keyword_hint ? associated_keyword->keyword :
407 GetSubstitutingExplicitlyInvokedKeyword(profile));
408 }
409
GetSubstitutingExplicitlyInvokedKeyword(Profile * profile) const410 base::string16 AutocompleteMatch::GetSubstitutingExplicitlyInvokedKeyword(
411 Profile* profile) const {
412 if (transition != content::PAGE_TRANSITION_KEYWORD)
413 return base::string16();
414 const TemplateURL* t_url = GetTemplateURL(profile, false);
415 return (t_url &&
416 t_url->SupportsReplacement(UIThreadSearchTermsData(profile))) ?
417 keyword : base::string16();
418 }
419
GetTemplateURL(Profile * profile,bool allow_fallback_to_destination_host) const420 TemplateURL* AutocompleteMatch::GetTemplateURL(
421 Profile* profile, bool allow_fallback_to_destination_host) const {
422 DCHECK(profile);
423 TemplateURLService* template_url_service =
424 TemplateURLServiceFactory::GetForProfile(profile);
425 if (template_url_service == NULL)
426 return NULL;
427 TemplateURL* template_url = keyword.empty() ? NULL :
428 template_url_service->GetTemplateURLForKeyword(keyword);
429 if (template_url == NULL && allow_fallback_to_destination_host) {
430 template_url = template_url_service->GetTemplateURLForHost(
431 destination_url.host());
432 }
433 return template_url;
434 }
435
RecordAdditionalInfo(const std::string & property,const std::string & value)436 void AutocompleteMatch::RecordAdditionalInfo(const std::string& property,
437 const std::string& value) {
438 DCHECK(!property.empty());
439 DCHECK(!value.empty());
440 additional_info[property] = value;
441 }
442
RecordAdditionalInfo(const std::string & property,int value)443 void AutocompleteMatch::RecordAdditionalInfo(const std::string& property,
444 int value) {
445 RecordAdditionalInfo(property, base::IntToString(value));
446 }
447
RecordAdditionalInfo(const std::string & property,const base::Time & value)448 void AutocompleteMatch::RecordAdditionalInfo(const std::string& property,
449 const base::Time& value) {
450 RecordAdditionalInfo(property,
451 base::UTF16ToUTF8(
452 base::TimeFormatShortDateAndTime(value)));
453 }
454
GetAdditionalInfo(const std::string & property) const455 std::string AutocompleteMatch::GetAdditionalInfo(
456 const std::string& property) const {
457 AdditionalInfo::const_iterator i(additional_info.find(property));
458 return (i == additional_info.end()) ? std::string() : i->second;
459 }
460
IsVerbatimType() const461 bool AutocompleteMatch::IsVerbatimType() const {
462 const bool is_keyword_verbatim_match =
463 (type == AutocompleteMatchType::SEARCH_OTHER_ENGINE &&
464 provider != NULL &&
465 provider->type() == AutocompleteProvider::TYPE_SEARCH);
466 return type == AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED ||
467 type == AutocompleteMatchType::URL_WHAT_YOU_TYPED ||
468 is_keyword_verbatim_match;
469 }
470
SupportsDeletion() const471 bool AutocompleteMatch::SupportsDeletion() const {
472 if (deletable)
473 return true;
474
475 for (ACMatches::const_iterator it(duplicate_matches.begin());
476 it != duplicate_matches.end(); ++it) {
477 if (it->deletable)
478 return true;
479 }
480 return false;
481 }
482
483 #ifndef NDEBUG
Validate() const484 void AutocompleteMatch::Validate() const {
485 ValidateClassifications(contents, contents_class);
486 ValidateClassifications(description, description_class);
487 }
488
ValidateClassifications(const base::string16 & text,const ACMatchClassifications & classifications) const489 void AutocompleteMatch::ValidateClassifications(
490 const base::string16& text,
491 const ACMatchClassifications& classifications) const {
492 if (text.empty()) {
493 DCHECK(classifications.empty());
494 return;
495 }
496
497 // The classifications should always cover the whole string.
498 DCHECK(!classifications.empty()) << "No classification for \"" << text << '"';
499 DCHECK_EQ(0U, classifications[0].offset)
500 << "Classification misses beginning for \"" << text << '"';
501 if (classifications.size() == 1)
502 return;
503
504 // The classifications should always be sorted.
505 size_t last_offset = classifications[0].offset;
506 for (ACMatchClassifications::const_iterator i(classifications.begin() + 1);
507 i != classifications.end(); ++i) {
508 const char* provider_name = provider ? provider->GetName() : "None";
509 DCHECK_GT(i->offset, last_offset)
510 << " Classification for \"" << text << "\" with offset of " << i->offset
511 << " is unsorted in relation to last offset of " << last_offset
512 << ". Provider: " << provider_name << ".";
513 DCHECK_LT(i->offset, text.length())
514 << " Classification of [" << i->offset << "," << text.length()
515 << "] is out of bounds for \"" << text << "\". Provider: "
516 << provider_name << ".";
517 last_offset = i->offset;
518 }
519 }
520 #endif
521