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