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