1// Copyright (c) 2011 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/keyword_provider.h"
6
7#include <algorithm>
8#include <vector>
9
10#include "base/string16.h"
11#include "base/utf_string_conversions.h"
12#include "chrome/browser/autocomplete/autocomplete_match.h"
13#include "chrome/browser/extensions/extension_omnibox_api.h"
14#include "chrome/browser/extensions/extension_service.h"
15#include "chrome/browser/profiles/profile.h"
16#include "chrome/browser/search_engines/template_url.h"
17#include "chrome/browser/search_engines/template_url_model.h"
18#include "content/common/notification_details.h"
19#include "content/common/notification_source.h"
20#include "grit/generated_resources.h"
21#include "net/base/escape.h"
22#include "net/base/net_util.h"
23#include "ui/base/l10n/l10n_util.h"
24
25// Helper functor for Start(), for ending keyword mode unless explicitly told
26// otherwise.
27class KeywordProvider::ScopedEndExtensionKeywordMode {
28 public:
29  explicit ScopedEndExtensionKeywordMode(KeywordProvider* provider)
30      : provider_(provider) { }
31  ~ScopedEndExtensionKeywordMode() {
32    if (provider_)
33      provider_->MaybeEndExtensionKeywordMode();
34  }
35
36  void StayInKeywordMode() {
37    provider_ = NULL;
38  }
39 private:
40  KeywordProvider* provider_;
41};
42
43// static
44string16 KeywordProvider::SplitReplacementStringFromInput(
45    const string16& input,
46    bool trim_leading_whitespace) {
47  // The input may contain leading whitespace, strip it.
48  string16 trimmed_input;
49  TrimWhitespace(input, TRIM_LEADING, &trimmed_input);
50
51  // And extract the replacement string.
52  string16 remaining_input;
53  SplitKeywordFromInput(trimmed_input, trim_leading_whitespace,
54                        &remaining_input);
55  return remaining_input;
56}
57
58KeywordProvider::KeywordProvider(ACProviderListener* listener, Profile* profile)
59    : AutocompleteProvider(listener, profile, "Keyword"),
60      model_(NULL),
61      current_input_id_(0) {
62  // Extension suggestions always come from the original profile, since that's
63  // where extensions run. We use the input ID to distinguish whether the
64  // suggestions are meant for us.
65  registrar_.Add(this, NotificationType::EXTENSION_OMNIBOX_SUGGESTIONS_READY,
66                 Source<Profile>(profile->GetOriginalProfile()));
67  registrar_.Add(this,
68                 NotificationType::EXTENSION_OMNIBOX_DEFAULT_SUGGESTION_CHANGED,
69                 Source<Profile>(profile->GetOriginalProfile()));
70  registrar_.Add(this, NotificationType::EXTENSION_OMNIBOX_INPUT_ENTERED,
71                 Source<Profile>(profile));
72}
73
74KeywordProvider::KeywordProvider(ACProviderListener* listener,
75                                 TemplateURLModel* model)
76    : AutocompleteProvider(listener, NULL, "Keyword"),
77      model_(model),
78      current_input_id_(0) {
79}
80
81
82namespace {
83
84// Helper functor for Start(), for sorting keyword matches by quality.
85class CompareQuality {
86 public:
87  // A keyword is of higher quality when a greater fraction of it has been
88  // typed, that is, when it is shorter.
89  //
90  // TODO(pkasting): http://b/740691 Most recent and most frequent keywords are
91  // probably better rankings than the fraction of the keyword typed.  We should
92  // always put any exact matches first no matter what, since the code in
93  // Start() assumes this (and it makes sense).
94  bool operator()(const string16& keyword1,
95                  const string16& keyword2) const {
96    return keyword1.length() < keyword2.length();
97  }
98};
99
100// We need our input IDs to be unique across all profiles, so we keep a global
101// UID that each provider uses.
102static int global_input_uid_;
103
104}  // namespace
105
106// static
107const TemplateURL* KeywordProvider::GetSubstitutingTemplateURLForInput(
108    Profile* profile,
109    const AutocompleteInput& input,
110    string16* remaining_input) {
111  if (!input.allow_exact_keyword_match())
112    return NULL;
113
114  string16 keyword;
115  if (!ExtractKeywordFromInput(input, &keyword, remaining_input))
116    return NULL;
117
118  // Make sure the model is loaded. This is cheap and quickly bails out if
119  // the model is already loaded.
120  TemplateURLModel* model = profile->GetTemplateURLModel();
121  DCHECK(model);
122  model->Load();
123
124  const TemplateURL* template_url = model->GetTemplateURLForKeyword(keyword);
125  return TemplateURL::SupportsReplacement(template_url) ? template_url : NULL;
126}
127
128void KeywordProvider::Start(const AutocompleteInput& input,
129                            bool minimal_changes) {
130  // This object ensures we end keyword mode if we exit the function without
131  // toggling keyword mode to on.
132  ScopedEndExtensionKeywordMode keyword_mode_toggle(this);
133
134  matches_.clear();
135
136  if (!minimal_changes) {
137    done_ = true;
138
139    // Input has changed. Increment the input ID so that we can discard any
140    // stale extension suggestions that may be incoming.
141    current_input_id_ = ++global_input_uid_;
142  }
143
144  // Split user input into a keyword and some query input.
145  //
146  // We want to suggest keywords even when users have started typing URLs, on
147  // the assumption that they might not realize they no longer need to go to a
148  // site to be able to search it.  So we call CleanUserInputKeyword() to strip
149  // any initial scheme and/or "www.".  NOTE: Any heuristics or UI used to
150  // automatically/manually create keywords will need to be in sync with
151  // whatever we do here!
152  //
153  // TODO(pkasting): http://b/1112681 If someday we remember usage frequency for
154  // keywords, we might suggest keywords that haven't even been partially typed,
155  // if the user uses them enough and isn't obviously typing something else.  In
156  // this case we'd consider all input here to be query input.
157  string16 keyword, remaining_input;
158  if (!ExtractKeywordFromInput(input, &keyword, &remaining_input))
159    return;
160
161  // Make sure the model is loaded. This is cheap and quickly bails out if
162  // the model is already loaded.
163  TemplateURLModel* model = profile_ ? profile_->GetTemplateURLModel() : model_;
164  DCHECK(model);
165  model->Load();
166
167  // Get the best matches for this keyword.
168  //
169  // NOTE: We could cache the previous keywords and reuse them here in the
170  // |minimal_changes| case, but since we'd still have to recalculate their
171  // relevances and we can just recreate the results synchronously anyway, we
172  // don't bother.
173  //
174  // TODO(pkasting): http://b/893701 We should remember the user's use of a
175  // search query both from the autocomplete popup and from web pages
176  // themselves.
177  std::vector<string16> keyword_matches;
178  model->FindMatchingKeywords(keyword,
179                              !remaining_input.empty(),
180                              &keyword_matches);
181
182  // Prune any extension keywords that are disallowed in incognito mode (if
183  // we're incognito), or disabled.
184  for (std::vector<string16>::iterator i(keyword_matches.begin());
185       i != keyword_matches.end(); ) {
186    const TemplateURL* template_url(model->GetTemplateURLForKeyword(*i));
187    if (profile_ &&
188        input.matches_requested() == AutocompleteInput::ALL_MATCHES &&
189        template_url->IsExtensionKeyword()) {
190      ExtensionService* service = profile_->GetExtensionService();
191      const Extension* extension = service->GetExtensionById(
192          template_url->GetExtensionId(), false);
193      bool enabled =
194          extension && (!profile_->IsOffTheRecord() ||
195                        service->IsIncognitoEnabled(extension->id()));
196      if (!enabled) {
197        i = keyword_matches.erase(i);
198        continue;
199      }
200    }
201    ++i;
202  }
203  if (keyword_matches.empty())
204    return;
205  std::sort(keyword_matches.begin(), keyword_matches.end(), CompareQuality());
206
207  // Limit to one exact or three inexact matches, and mark them up for display
208  // in the autocomplete popup.
209  // Any exact match is going to be the highest quality match, and thus at the
210  // front of our vector.
211  if (keyword_matches.front() == keyword) {
212    const TemplateURL* template_url(model->GetTemplateURLForKeyword(keyword));
213    // TODO(pkasting): We should probably check that if the user explicitly
214    // typed a scheme, that scheme matches the one in |template_url|.
215    matches_.push_back(CreateAutocompleteMatch(model, keyword, input,
216                                               keyword.length(),
217                                               remaining_input, -1));
218
219    if (profile_ &&
220        input.matches_requested() == AutocompleteInput::ALL_MATCHES &&
221        template_url->IsExtensionKeyword()) {
222      if (template_url->GetExtensionId() != current_keyword_extension_id_)
223        MaybeEndExtensionKeywordMode();
224      if (current_keyword_extension_id_.empty())
225        EnterExtensionKeywordMode(template_url->GetExtensionId());
226      keyword_mode_toggle.StayInKeywordMode();
227
228      ApplyDefaultSuggestionForExtensionKeyword(profile_, template_url,
229                                                remaining_input,
230                                                &matches_[0]);
231
232      if (minimal_changes) {
233        // If the input hasn't significantly changed, we can just use the
234        // suggestions from last time. We need to readjust the relevance to
235        // ensure it is less than the main match's relevance.
236        for (size_t i = 0; i < extension_suggest_matches_.size(); ++i) {
237          matches_.push_back(extension_suggest_matches_[i]);
238          matches_.back().relevance = matches_[0].relevance - (i + 1);
239        }
240      } else {
241        extension_suggest_last_input_ = input;
242        extension_suggest_matches_.clear();
243
244        bool have_listeners = ExtensionOmniboxEventRouter::OnInputChanged(
245            profile_, template_url->GetExtensionId(),
246            UTF16ToUTF8(remaining_input), current_input_id_);
247
248        // We only have to wait for suggest results if there are actually
249        // extensions listening for input changes.
250        if (have_listeners)
251          done_ = false;
252      }
253    }
254  } else {
255    if (keyword_matches.size() > kMaxMatches) {
256      keyword_matches.erase(keyword_matches.begin() + kMaxMatches,
257                            keyword_matches.end());
258    }
259    for (std::vector<string16>::const_iterator i(keyword_matches.begin());
260         i != keyword_matches.end(); ++i) {
261      matches_.push_back(CreateAutocompleteMatch(model, *i,
262                                                 input, keyword.length(),
263                                                 remaining_input, -1));
264    }
265  }
266}
267
268void KeywordProvider::Stop() {
269  done_ = true;
270  MaybeEndExtensionKeywordMode();
271}
272
273KeywordProvider::~KeywordProvider() {}
274
275// static
276bool KeywordProvider::ExtractKeywordFromInput(const AutocompleteInput& input,
277                                              string16* keyword,
278                                              string16* remaining_input) {
279  if ((input.type() == AutocompleteInput::INVALID) ||
280      (input.type() == AutocompleteInput::FORCED_QUERY))
281    return false;
282
283  *keyword = TemplateURLModel::CleanUserInputKeyword(
284      SplitKeywordFromInput(input.text(), true, remaining_input));
285  return !keyword->empty();
286}
287
288// static
289string16 KeywordProvider::SplitKeywordFromInput(
290    const string16& input,
291    bool trim_leading_whitespace,
292    string16* remaining_input) {
293  // Find end of first token.  The AutocompleteController has trimmed leading
294  // whitespace, so we need not skip over that.
295  const size_t first_white(input.find_first_of(kWhitespaceUTF16));
296  DCHECK_NE(0U, first_white);
297  if (first_white == string16::npos)
298    return input;  // Only one token provided.
299
300  // Set |remaining_input| to everything after the first token.
301  DCHECK(remaining_input != NULL);
302  const size_t remaining_start = trim_leading_whitespace ?
303    input.find_first_not_of(kWhitespaceUTF16, first_white) : first_white + 1;
304
305  if (remaining_start < input.length())
306    remaining_input->assign(input.begin() + remaining_start, input.end());
307
308  // Return first token as keyword.
309  return input.substr(0, first_white);
310}
311
312// static
313void KeywordProvider::FillInURLAndContents(
314    const string16& remaining_input,
315    const TemplateURL* element,
316    AutocompleteMatch* match) {
317  DCHECK(!element->short_name().empty());
318  DCHECK(element->url());
319  DCHECK(element->url()->IsValid());
320  int message_id = element->IsExtensionKeyword() ?
321      IDS_EXTENSION_KEYWORD_COMMAND : IDS_KEYWORD_SEARCH;
322  if (remaining_input.empty()) {
323    // Allow extension keyword providers to accept empty string input. This is
324    // useful to allow extensions to do something in the case where no input is
325    // entered.
326    if (element->url()->SupportsReplacement() &&
327        !element->IsExtensionKeyword()) {
328      // No query input; return a generic, no-destination placeholder.
329      match->contents.assign(
330          l10n_util::GetStringFUTF16(message_id,
331              element->AdjustedShortNameForLocaleDirection(),
332              l10n_util::GetStringUTF16(IDS_EMPTY_KEYWORD_VALUE)));
333      match->contents_class.push_back(
334          ACMatchClassification(0, ACMatchClassification::DIM));
335    } else {
336      // Keyword that has no replacement text (aka a shorthand for a URL).
337      match->destination_url = GURL(element->url()->url());
338      match->contents.assign(element->short_name());
339      AutocompleteMatch::ClassifyLocationInString(0, match->contents.length(),
340          match->contents.length(), ACMatchClassification::NONE,
341          &match->contents_class);
342    }
343  } else {
344    // Create destination URL by escaping user input and substituting into
345    // keyword template URL.  The escaping here handles whitespace in user
346    // input, but we rely on later canonicalization functions to do more
347    // fixup to make the URL valid if necessary.
348    DCHECK(element->url()->SupportsReplacement());
349    match->destination_url = GURL(element->url()->ReplaceSearchTerms(
350        *element, remaining_input,
351        TemplateURLRef::NO_SUGGESTIONS_AVAILABLE, string16()));
352    std::vector<size_t> content_param_offsets;
353    match->contents.assign(l10n_util::GetStringFUTF16(message_id,
354                                                      element->short_name(),
355                                                      remaining_input,
356                                                      &content_param_offsets));
357    if (content_param_offsets.size() == 2) {
358      AutocompleteMatch::ClassifyLocationInString(content_param_offsets[1],
359          remaining_input.length(), match->contents.length(),
360          ACMatchClassification::NONE, &match->contents_class);
361    } else {
362      // See comments on an identical NOTREACHED() in search_provider.cc.
363      NOTREACHED();
364    }
365  }
366}
367
368// static
369int KeywordProvider::CalculateRelevance(AutocompleteInput::Type type,
370                                        bool complete,
371                                        bool supports_replacement,
372                                        bool prefer_keyword,
373                                        bool allow_exact_keyword_match) {
374  if (!complete)
375    return (type == AutocompleteInput::URL) ? 700 : 450;
376  if (!supports_replacement || (allow_exact_keyword_match && prefer_keyword))
377    return 1500;
378  return (allow_exact_keyword_match && (type == AutocompleteInput::QUERY)) ?
379      1450 : 1100;
380}
381
382AutocompleteMatch KeywordProvider::CreateAutocompleteMatch(
383    TemplateURLModel* model,
384    const string16& keyword,
385    const AutocompleteInput& input,
386    size_t prefix_length,
387    const string16& remaining_input,
388    int relevance) {
389  DCHECK(model);
390  // Get keyword data from data store.
391  const TemplateURL* element(
392      model->GetTemplateURLForKeyword(keyword));
393  DCHECK(element && element->url());
394  const bool supports_replacement = element->url()->SupportsReplacement();
395
396  // Create an edit entry of "[keyword] [remaining input]".  This is helpful
397  // even when [remaining input] is empty, as the user can select the popup
398  // choice and immediately begin typing in query input.
399  const bool keyword_complete = (prefix_length == keyword.length());
400  if (relevance < 0) {
401    relevance =
402        CalculateRelevance(input.type(), keyword_complete,
403                           // When the user wants keyword matches to take
404                           // preference, score them highly regardless of
405                           // whether the input provides query text.
406                           supports_replacement, input.prefer_keyword(),
407                           input.allow_exact_keyword_match());
408  }
409  AutocompleteMatch result(this, relevance, false,
410      supports_replacement ? AutocompleteMatch::SEARCH_OTHER_ENGINE :
411                             AutocompleteMatch::HISTORY_KEYWORD);
412  result.fill_into_edit.assign(keyword);
413  if (!remaining_input.empty() || !keyword_complete || supports_replacement)
414    result.fill_into_edit.push_back(L' ');
415  result.fill_into_edit.append(remaining_input);
416  // If we wanted to set |result.inline_autocomplete_offset| correctly, we'd
417  // need CleanUserInputKeyword() to return the amount of adjustment it's made
418  // to the user's input.  Because right now inexact keyword matches can't score
419  // more highly than a "what you typed" match from one of the other providers,
420  // we just don't bother to do this, and leave inline autocompletion off.
421  result.inline_autocomplete_offset = string16::npos;
422
423  // Create destination URL and popup entry content by substituting user input
424  // into keyword templates.
425  FillInURLAndContents(remaining_input, element, &result);
426
427  if (supports_replacement)
428    result.template_url = element;
429  result.transition = PageTransition::KEYWORD;
430
431  // Create popup entry description based on the keyword name.
432  if (!element->IsExtensionKeyword()) {
433    result.description.assign(l10n_util::GetStringFUTF16(
434        IDS_AUTOCOMPLETE_KEYWORD_DESCRIPTION, keyword));
435    string16 keyword_desc(
436        l10n_util::GetStringUTF16(IDS_AUTOCOMPLETE_KEYWORD_DESCRIPTION));
437    AutocompleteMatch::ClassifyLocationInString(
438        keyword_desc.find(ASCIIToUTF16("%s")),
439        prefix_length,
440        result.description.length(),
441        ACMatchClassification::DIM,
442        &result.description_class);
443  }
444
445  return result;
446}
447
448void KeywordProvider::Observe(NotificationType type,
449                              const NotificationSource& source,
450                              const NotificationDetails& details) {
451  TemplateURLModel* model = profile_ ? profile_->GetTemplateURLModel() : model_;
452  const AutocompleteInput& input = extension_suggest_last_input_;
453
454  switch (type.value) {
455    case NotificationType::EXTENSION_OMNIBOX_INPUT_ENTERED:
456      // Input has been accepted, so we're done with this input session. Ensure
457      // we don't send the OnInputCancelled event.
458      current_keyword_extension_id_.clear();
459      return;
460
461    case NotificationType::EXTENSION_OMNIBOX_DEFAULT_SUGGESTION_CHANGED: {
462      // It's possible to change the default suggestion while not in an editing
463      // session.
464      string16 keyword, remaining_input;
465      if (matches_.empty() || current_keyword_extension_id_.empty() ||
466          !ExtractKeywordFromInput(input, &keyword, &remaining_input))
467        return;
468
469      const TemplateURL* template_url(
470          model->GetTemplateURLForKeyword(keyword));
471      ApplyDefaultSuggestionForExtensionKeyword(profile_, template_url,
472                                                remaining_input,
473                                                &matches_[0]);
474      listener_->OnProviderUpdate(true);
475      return;
476    }
477
478    case NotificationType::EXTENSION_OMNIBOX_SUGGESTIONS_READY: {
479      const ExtensionOmniboxSuggestions& suggestions =
480        *Details<ExtensionOmniboxSuggestions>(details).ptr();
481      if (suggestions.request_id != current_input_id_)
482        return;  // This is an old result. Just ignore.
483
484      string16 keyword, remaining_input;
485      if (!ExtractKeywordFromInput(input, &keyword, &remaining_input)) {
486        NOTREACHED();
487        return;
488      }
489
490      // TODO(mpcomplete): consider clamping the number of suggestions to
491      // AutocompleteProvider::kMaxMatches.
492      for (size_t i = 0; i < suggestions.suggestions.size(); ++i) {
493        const ExtensionOmniboxSuggestion& suggestion =
494            suggestions.suggestions[i];
495        // We want to order these suggestions in descending order, so start with
496        // the relevance of the first result (added synchronously in Start()),
497        // and subtract 1 for each subsequent suggestion from the extension.
498        // We know that |complete| is true, because we wouldn't get results from
499        // the extension unless the full keyword had been typed.
500        int first_relevance = CalculateRelevance(input.type(), true, true,
501            input.prefer_keyword(), input.allow_exact_keyword_match());
502        extension_suggest_matches_.push_back(CreateAutocompleteMatch(
503            model, keyword, input, keyword.length(),
504            suggestion.content, first_relevance - (i + 1)));
505
506        AutocompleteMatch* match = &extension_suggest_matches_.back();
507        match->contents.assign(suggestion.description);
508        match->contents_class = suggestion.description_styles;
509        match->description.clear();
510        match->description_class.clear();
511      }
512
513      done_ = true;
514      matches_.insert(matches_.end(), extension_suggest_matches_.begin(),
515                      extension_suggest_matches_.end());
516      listener_->OnProviderUpdate(!extension_suggest_matches_.empty());
517      return;
518    }
519
520    default:
521      NOTREACHED();
522      return;
523  }
524}
525
526void KeywordProvider::EnterExtensionKeywordMode(
527    const std::string& extension_id) {
528  DCHECK(current_keyword_extension_id_.empty());
529  current_keyword_extension_id_ = extension_id;
530
531  ExtensionOmniboxEventRouter::OnInputStarted(
532      profile_, current_keyword_extension_id_);
533}
534
535void KeywordProvider::MaybeEndExtensionKeywordMode() {
536  if (!current_keyword_extension_id_.empty()) {
537    ExtensionOmniboxEventRouter::OnInputCancelled(
538        profile_, current_keyword_extension_id_);
539
540    current_keyword_extension_id_.clear();
541  }
542}
543