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
21namespace {
22
23bool 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
34const char16 AutocompleteMatch::kInvalidChars[] = {
35  '\n', '\r', '\t',
36  0x2028,  // Line separator
37  0x2029,  // Paragraph separator
38  0
39};
40
41AutocompleteMatch::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
54AutocompleteMatch::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
70AutocompleteMatch::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
98AutocompleteMatch::~AutocompleteMatch() {
99}
100
101AutocompleteMatch& 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
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    // 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
162int 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
170bool 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
180bool 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
193bool 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
202void 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
212void 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
249AutocompleteMatch::ACMatchClassifications
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
280std::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
293ACMatchClassifications 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
314void 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
327base::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
337bool 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
344void 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
395void 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
403base::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
411TemplateURL* 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
427void 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
434void AutocompleteMatch::RecordAdditionalInfo(const std::string& property,
435                                             int value) {
436  RecordAdditionalInfo(property, base::IntToString(value));
437}
438
439void AutocompleteMatch::RecordAdditionalInfo(const std::string& property,
440                                             const base::Time& value) {
441  RecordAdditionalInfo(property,
442                       UTF16ToUTF8(base::TimeFormatShortDateAndTime(value)));
443}
444
445std::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
451bool 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
462void AutocompleteMatch::Validate() const {
463  ValidateClassifications(contents, contents_class);
464  ValidateClassifications(description, description_class);
465}
466
467void 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