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.
5 #include "chrome/browser/autocomplete/autocomplete_controller.h"
10 #include "base/command_line.h"
11 #include "base/format_macros.h"
12 #include "base/logging.h"
13 #include "base/metrics/histogram.h"
14 #include "base/strings/string_number_conversions.h"
15 #include "base/strings/stringprintf.h"
16 #include "base/time/time.h"
17 #include "chrome/browser/autocomplete/autocomplete_controller_delegate.h"
18 #include "chrome/browser/autocomplete/bookmark_provider.h"
19 #include "chrome/browser/autocomplete/builtin_provider.h"
20 #include "chrome/browser/autocomplete/extension_app_provider.h"
21 #include "chrome/browser/autocomplete/history_quick_provider.h"
22 #include "chrome/browser/autocomplete/history_url_provider.h"
23 #include "chrome/browser/autocomplete/keyword_provider.h"
24 #include "chrome/browser/autocomplete/search_provider.h"
25 #include "chrome/browser/autocomplete/shortcuts_provider.h"
26 #include "chrome/browser/autocomplete/zero_suggest_provider.h"
27 #include "chrome/browser/chrome_notification_types.h"
28 #include "chrome/browser/omnibox/omnibox_field_trial.h"
29 #include "chrome/browser/profiles/profile.h"
30 #include "chrome/browser/search/search.h"
31 #include "chrome/browser/search_engines/template_url.h"
32 #include "chrome/common/chrome_switches.h"
33 #include "content/public/browser/notification_service.h"
34 #include "grit/generated_resources.h"
35 #include "grit/theme_resources.h"
36 #include "ui/base/l10n/l10n_util.h"
38 #if defined(OS_CHROMEOS)
39 #include "chrome/browser/autocomplete/contact_provider_chromeos.h"
40 #include "chrome/browser/chromeos/contacts/contact_manager.h"
45 // Converts the given match to a type (and possibly subtype) based on the AQS
46 // specification. For more details, see
47 // http://goto.google.com/binary-clients-logging.
48 void AutocompleteMatchToAssistedQuery(
49 const AutocompleteMatch::Type& match, size_t* type, size_t* subtype) {
50 // This type indicates a native chrome suggestion.
52 // Default value, indicating no subtype.
53 *subtype = string16::npos;
56 case AutocompleteMatchType::SEARCH_SUGGEST: {
60 case AutocompleteMatchType::NAVSUGGEST: {
64 case AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED: {
68 case AutocompleteMatchType::URL_WHAT_YOU_TYPED: {
72 case AutocompleteMatchType::SEARCH_HISTORY: {
76 case AutocompleteMatchType::HISTORY_URL: {
80 case AutocompleteMatchType::HISTORY_TITLE: {
84 case AutocompleteMatchType::HISTORY_BODY: {
88 case AutocompleteMatchType::HISTORY_KEYWORD: {
92 case AutocompleteMatchType::BOOKMARK_TITLE: {
97 // This value indicates a native chrome suggestion with no named subtype
104 // Appends available autocompletion of the given type, subtype, and number to
105 // the existing available autocompletions string, encoding according to the
107 void AppendAvailableAutocompletion(size_t type,
110 std::string* autocompletions) {
111 if (!autocompletions->empty())
112 autocompletions->append("j");
113 base::StringAppendF(autocompletions, "%" PRIuS, type);
114 // Subtype is optional - string16::npos indicates no subtype.
115 if (subtype != string16::npos)
116 base::StringAppendF(autocompletions, "i%" PRIuS, subtype);
118 base::StringAppendF(autocompletions, "l%d", count);
121 // Returns whether the autocompletion is trivial enough that we consider it
122 // an autocompletion for which the omnibox autocompletion code did not add
124 bool IsTrivialAutocompletion(const AutocompleteMatch& match) {
125 return match.type == AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED ||
126 match.type == AutocompleteMatchType::URL_WHAT_YOU_TYPED ||
127 match.type == AutocompleteMatchType::SEARCH_OTHER_ENGINE;
132 const int AutocompleteController::kNoItemSelected = -1;
134 AutocompleteController::AutocompleteController(
136 AutocompleteControllerDelegate* delegate,
138 : delegate_(delegate),
139 history_url_provider_(NULL),
140 keyword_provider_(NULL),
141 search_provider_(NULL),
142 zero_suggest_provider_(NULL),
143 in_stop_timer_field_trial_(
144 OmniboxFieldTrial::InStopTimerFieldTrialExperimentGroup()),
147 in_zero_suggest_(false),
149 // AND with the disabled providers, if any.
150 provider_types &= ~OmniboxFieldTrial::GetDisabledProviderTypes();
151 bool use_hqp = !!(provider_types & AutocompleteProvider::TYPE_HISTORY_QUICK);
152 // TODO(mrossetti): Permanently modify the HistoryURLProvider to not search
153 // titles once HQP is turned on permanently.
155 if (provider_types & AutocompleteProvider::TYPE_BUILTIN)
156 providers_.push_back(new BuiltinProvider(this, profile));
157 #if defined(OS_CHROMEOS)
158 if (provider_types & AutocompleteProvider::TYPE_CONTACT)
159 providers_.push_back(new ContactProvider(this, profile,
160 contacts::ContactManager::GetInstance()->GetWeakPtr()));
162 if (provider_types & AutocompleteProvider::TYPE_EXTENSION_APP)
163 providers_.push_back(new ExtensionAppProvider(this, profile));
165 providers_.push_back(new HistoryQuickProvider(this, profile));
166 if (provider_types & AutocompleteProvider::TYPE_HISTORY_URL) {
167 history_url_provider_ = new HistoryURLProvider(this, profile);
168 providers_.push_back(history_url_provider_);
170 // Search provider/"tab to search" can be used on all platforms other than
172 #if !defined(OS_ANDROID)
173 if (provider_types & AutocompleteProvider::TYPE_KEYWORD) {
174 keyword_provider_ = new KeywordProvider(this, profile);
175 providers_.push_back(keyword_provider_);
178 if (provider_types & AutocompleteProvider::TYPE_SEARCH) {
179 search_provider_ = new SearchProvider(this, profile);
180 providers_.push_back(search_provider_);
182 if (provider_types & AutocompleteProvider::TYPE_SHORTCUTS)
183 providers_.push_back(new ShortcutsProvider(this, profile));
185 // Create ZeroSuggest if it is enabled.
186 if (provider_types & AutocompleteProvider::TYPE_ZERO_SUGGEST) {
187 zero_suggest_provider_ = ZeroSuggestProvider::Create(this, profile);
188 if (zero_suggest_provider_)
189 providers_.push_back(zero_suggest_provider_);
192 if ((provider_types & AutocompleteProvider::TYPE_BOOKMARK) &&
193 !CommandLine::ForCurrentProcess()->HasSwitch(
194 switches::kDisableBookmarkAutocompleteProvider))
195 providers_.push_back(new BookmarkProvider(this, profile));
197 for (ACProviders::iterator i(providers_.begin()); i != providers_.end(); ++i)
201 AutocompleteController::~AutocompleteController() {
202 // The providers may have tasks outstanding that hold refs to them. We need
203 // to ensure they won't call us back if they outlive us. (Practically,
204 // calling Stop() should also cancel those tasks and make it so that we hold
205 // the only refs.) We also don't want to bother notifying anyone of our
206 // result changes here, because the notification observer is in the midst of
207 // shutdown too, so we don't ask Stop() to clear |result_| (and notify).
208 result_.Reset(); // Not really necessary.
211 for (ACProviders::iterator i(providers_.begin()); i != providers_.end(); ++i)
214 providers_.clear(); // Not really necessary.
217 void AutocompleteController::Start(const AutocompleteInput& input) {
218 const string16 old_input_text(input_.text());
219 const AutocompleteInput::MatchesRequested old_matches_requested =
220 input_.matches_requested();
223 // See if we can avoid rerunning autocomplete when the query hasn't changed
224 // much. When the user presses or releases the ctrl key, the desired_tld
225 // changes, and when the user finishes an IME composition, inline autocomplete
226 // may no longer be prevented. In both these cases the text itself hasn't
227 // changed since the last query, and some providers can do much less work (and
228 // get matches back more quickly). Taking advantage of this reduces flicker.
230 // NOTE: This comes after constructing |input_| above since that construction
231 // can change the text string (e.g. by stripping off a leading '?').
232 const bool minimal_changes = (input_.text() == old_input_text) &&
233 (input_.matches_requested() == old_matches_requested);
235 expire_timer_.Stop();
238 // Start the new query.
239 in_zero_suggest_ = false;
241 base::TimeTicks start_time = base::TimeTicks::Now();
242 for (ACProviders::iterator i(providers_.begin()); i != providers_.end();
244 // TODO(mpearson): Remove timing code once bugs 178705 / 237703 / 168933
246 base::TimeTicks provider_start_time = base::TimeTicks::Now();
247 (*i)->Start(input_, minimal_changes);
248 if (input.matches_requested() != AutocompleteInput::ALL_MATCHES)
249 DCHECK((*i)->done());
250 base::TimeTicks provider_end_time = base::TimeTicks::Now();
251 std::string name = std::string("Omnibox.ProviderTime.") + (*i)->GetName();
252 base::HistogramBase* counter = base::Histogram::FactoryGet(
253 name, 1, 5000, 20, base::Histogram::kUmaTargetedHistogramFlag);
254 counter->Add(static_cast<int>(
255 (provider_end_time - provider_start_time).InMilliseconds()));
257 if (input.matches_requested() == AutocompleteInput::ALL_MATCHES &&
258 (input.text().length() < 6)) {
259 base::TimeTicks end_time = base::TimeTicks::Now();
260 std::string name = "Omnibox.QueryTime." + base::IntToString(
261 input.text().length());
262 base::HistogramBase* counter = base::Histogram::FactoryGet(
263 name, 1, 1000, 50, base::Histogram::kUmaTargetedHistogramFlag);
264 counter->Add(static_cast<int>((end_time - start_time).InMilliseconds()));
268 // The second true forces saying the default match has changed.
269 // This triggers the edit model to update things such as the inline
270 // autocomplete state. In particular, if the user has typed a key
271 // since the last notification, and we're now re-running
272 // autocomplete, then we need to update the inline autocompletion
273 // even if the current match is for the same URL as the last run's
274 // default match. Likewise, the controller doesn't know what's
275 // happened in the edit since the last time it ran autocomplete.
276 // The user might have selected all the text and hit delete, then
277 // typed a new character. The selection and delete won't send any
278 // signals to the controller so it doesn't realize that anything was
279 // cleared or changed. Even if the default match hasn't changed, we
280 // need the edit model to update the display.
281 UpdateResult(false, true);
289 void AutocompleteController::Stop(bool clear_result) {
290 for (ACProviders::const_iterator i(providers_.begin()); i != providers_.end();
292 (*i)->Stop(clear_result);
295 expire_timer_.Stop();
298 if (clear_result && !result_.empty()) {
300 // NOTE: We pass in false since we're trying to only clear the popup, not
301 // touch the edit... this is all a mess and should be cleaned up :(
302 NotifyChanged(false);
306 void AutocompleteController::StartZeroSuggest(
308 AutocompleteInput::PageClassification page_classification,
309 const string16& permanent_text) {
310 if (zero_suggest_provider_ != NULL) {
311 DCHECK(!in_start_); // We should not be already running a query.
312 in_zero_suggest_ = true;
313 zero_suggest_provider_->StartZeroSuggest(
314 url, page_classification, permanent_text);
318 void AutocompleteController::StopZeroSuggest() {
319 if (zero_suggest_provider_ != NULL) {
320 DCHECK(!in_start_); // We should not be already running a query.
321 zero_suggest_provider_->Stop(false);
325 void AutocompleteController::DeleteMatch(const AutocompleteMatch& match) {
326 DCHECK(match.deletable);
327 match.provider->DeleteMatch(match); // This may synchronously call back to
328 // OnProviderUpdate().
329 // If DeleteMatch resulted in a callback to OnProviderUpdate and we're
330 // not done, we might attempt to redisplay the deleted match. Make sure
331 // we aren't displaying it by removing any old entries.
332 ExpireCopiedEntries();
335 void AutocompleteController::ExpireCopiedEntries() {
336 // The first true makes UpdateResult() clear out the results and
337 // regenerate them, thus ensuring that no results from the previous
338 // result set remain.
339 UpdateResult(true, false);
342 void AutocompleteController::OnProviderUpdate(bool updated_matches) {
343 if (in_zero_suggest_) {
344 // We got ZeroSuggest results before Start(). Show only those results,
345 // because results from other providers are stale.
347 result_.AppendMatches(zero_suggest_provider_->matches());
348 result_.SortAndCull(input_, profile_);
349 UpdateAssistedQueryStats(&result_);
353 // Multiple providers may provide synchronous results, so we only update the
354 // results if we're not in Start().
355 if (!in_start_ && (updated_matches || done_))
356 UpdateResult(false, false);
360 void AutocompleteController::AddProvidersInfo(
361 ProvidersInfo* provider_info) const {
362 provider_info->clear();
363 for (ACProviders::const_iterator i(providers_.begin()); i != providers_.end();
365 // Add per-provider info, if any.
366 (*i)->AddProviderInfo(provider_info);
368 // This is also a good place to put code to add info that you want to
369 // add for every provider.
373 void AutocompleteController::ResetSession() {
374 for (ACProviders::const_iterator i(providers_.begin()); i != providers_.end();
376 (*i)->ResetSession();
377 in_zero_suggest_ = false;
380 GURL AutocompleteController::GetDestinationURL(
381 const AutocompleteMatch& match,
382 base::TimeDelta query_formulation_time) const {
383 GURL destination_url(match.destination_url);
384 TemplateURL* template_url = match.GetTemplateURL(profile_, false);
386 // Append the query formulation time (time from when the user first typed a
387 // character into the omnibox to when the user selected a query) and whether
388 // a field trial has triggered to the AQS parameter, if other AQS parameters
389 // were already populated.
390 if (template_url && match.search_terms_args.get() &&
391 !match.search_terms_args->assisted_query_stats.empty()) {
392 TemplateURLRef::SearchTermsArgs search_terms_args(*match.search_terms_args);
393 search_terms_args.assisted_query_stats += base::StringPrintf(
394 ".%" PRId64 "j%dj%d",
395 query_formulation_time.InMilliseconds(),
397 search_provider_->field_trial_triggered_in_session()) ||
398 (zero_suggest_provider_ &&
399 zero_suggest_provider_->field_trial_triggered_in_session()),
400 input_.current_page_classification());
401 destination_url = GURL(template_url->url_ref().
402 ReplaceSearchTerms(search_terms_args));
404 return destination_url;
407 void AutocompleteController::UpdateResult(
408 bool regenerate_result,
409 bool force_notify_default_match_changed) {
410 const bool last_default_was_valid = result_.default_match() != result_.end();
411 // The following three variables are only set and used if
412 // |last_default_was_valid|.
413 string16 last_default_fill_into_edit, last_default_keyword,
414 last_default_associated_keyword;
415 if (last_default_was_valid) {
416 last_default_fill_into_edit = result_.default_match()->fill_into_edit;
417 last_default_keyword = result_.default_match()->keyword;
418 if (result_.default_match()->associated_keyword != NULL)
419 last_default_associated_keyword =
420 result_.default_match()->associated_keyword->keyword;
423 if (regenerate_result)
426 AutocompleteResult last_result;
427 last_result.Swap(&result_);
429 for (ACProviders::const_iterator i(providers_.begin()); i != providers_.end();
431 result_.AppendMatches((*i)->matches());
433 // Sort the matches and trim to a small number of "best" matches.
434 result_.SortAndCull(input_, profile_);
436 // Need to validate before invoking CopyOldMatches as the old matches are not
437 // valid against the current input.
443 // This conditional needs to match the conditional in Start that invokes
445 result_.CopyOldMatches(input_, last_result, profile_);
448 UpdateKeywordDescriptions(&result_);
449 UpdateAssociatedKeywords(&result_);
450 UpdateAssistedQueryStats(&result_);
452 const bool default_is_valid = result_.default_match() != result_.end();
453 string16 default_associated_keyword;
454 if (default_is_valid &&
455 (result_.default_match()->associated_keyword != NULL)) {
456 default_associated_keyword =
457 result_.default_match()->associated_keyword->keyword;
459 // We've gotten async results. Send notification that the default match
460 // updated if fill_into_edit, associated_keyword, or keyword differ. (The
461 // second can change if we've just started Chrome and the keyword database
462 // finishes loading while processing this request. The third can change
463 // if we swapped from interpreting the input as a search--which gets
464 // labeled with the default search provider's keyword--to a URL.)
465 // We don't check the URL as that may change for the default match
466 // even though the fill into edit hasn't changed (see SearchProvider
467 // for one case of this).
468 const bool notify_default_match =
469 (last_default_was_valid != default_is_valid) ||
470 (last_default_was_valid &&
471 ((result_.default_match()->fill_into_edit !=
472 last_default_fill_into_edit) ||
473 (default_associated_keyword != last_default_associated_keyword) ||
474 (result_.default_match()->keyword != last_default_keyword)));
475 if (notify_default_match)
476 last_time_default_match_changed_ = base::TimeTicks::Now();
478 NotifyChanged(force_notify_default_match_changed || notify_default_match);
481 void AutocompleteController::UpdateAssociatedKeywords(
482 AutocompleteResult* result) {
483 if (!keyword_provider_)
486 std::set<string16> keywords;
487 for (ACMatches::iterator match(result->begin()); match != result->end();
489 string16 keyword(match->GetSubstitutingExplicitlyInvokedKeyword(profile_));
490 if (!keyword.empty()) {
491 keywords.insert(keyword);
495 // Only add the keyword if the match does not have a duplicate keyword with
496 // a more relevant match.
497 keyword = match->associated_keyword.get() ?
498 match->associated_keyword->keyword :
499 keyword_provider_->GetKeywordForText(match->fill_into_edit);
500 if (!keyword.empty() && !keywords.count(keyword)) {
501 keywords.insert(keyword);
503 if (!match->associated_keyword.get())
504 match->associated_keyword.reset(new AutocompleteMatch(
505 keyword_provider_->CreateVerbatimMatch(match->fill_into_edit,
508 match->associated_keyword.reset();
513 void AutocompleteController::UpdateKeywordDescriptions(
514 AutocompleteResult* result) {
515 string16 last_keyword;
516 for (AutocompleteResult::iterator i(result->begin()); i != result->end();
518 if ((i->provider->type() == AutocompleteProvider::TYPE_KEYWORD &&
519 !i->keyword.empty()) ||
520 (i->provider->type() == AutocompleteProvider::TYPE_SEARCH &&
521 AutocompleteMatch::IsSearchType(i->type))) {
522 i->description.clear();
523 i->description_class.clear();
524 DCHECK(!i->keyword.empty());
525 if (i->keyword != last_keyword) {
526 const TemplateURL* template_url = i->GetTemplateURL(profile_, false);
528 // For extension keywords, just make the description the extension
529 // name -- don't assume that the normal search keyword description is
531 i->description = template_url->AdjustedShortNameForLocaleDirection();
532 if (template_url->GetType() != TemplateURL::OMNIBOX_API_EXTENSION) {
533 i->description = l10n_util::GetStringFUTF16(
534 IDS_AUTOCOMPLETE_SEARCH_DESCRIPTION, i->description);
536 i->description_class.push_back(
537 ACMatchClassification(0, ACMatchClassification::DIM));
539 last_keyword = i->keyword;
542 last_keyword.clear();
547 void AutocompleteController::UpdateAssistedQueryStats(
548 AutocompleteResult* result) {
552 // Build the impressions string (the AQS part after ".").
553 std::string autocompletions;
555 size_t last_type = string16::npos;
556 size_t last_subtype = string16::npos;
557 for (ACMatches::iterator match(result->begin()); match != result->end();
559 size_t type = string16::npos;
560 size_t subtype = string16::npos;
561 AutocompleteMatchToAssistedQuery(match->type, &type, &subtype);
562 if (last_type != string16::npos &&
563 (type != last_type || subtype != last_subtype)) {
564 AppendAvailableAutocompletion(
565 last_type, last_subtype, count, &autocompletions);
571 last_subtype = subtype;
573 AppendAvailableAutocompletion(
574 last_type, last_subtype, count, &autocompletions);
575 // Go over all matches and set AQS if the match supports it.
576 for (size_t index = 0; index < result->size(); ++index) {
577 AutocompleteMatch* match = result->match_at(index);
578 const TemplateURL* template_url = match->GetTemplateURL(profile_, false);
579 if (!template_url || !match->search_terms_args.get())
581 std::string selected_index;
582 // Prevent trivial suggestions from getting credit for being selected.
583 if (!IsTrivialAutocompletion(*match))
584 selected_index = base::StringPrintf("%" PRIuS, index);
585 match->search_terms_args->assisted_query_stats =
586 base::StringPrintf("chrome.%s.%s",
587 selected_index.c_str(),
588 autocompletions.c_str());
589 match->destination_url = GURL(template_url->url_ref().ReplaceSearchTerms(
590 *match->search_terms_args));
594 void AutocompleteController::NotifyChanged(bool notify_default_match) {
596 delegate_->OnResultChanged(notify_default_match);
598 content::NotificationService::current()->Notify(
599 chrome::NOTIFICATION_AUTOCOMPLETE_CONTROLLER_RESULT_READY,
600 content::Source<AutocompleteController>(this),
601 content::NotificationService::NoDetails());
605 void AutocompleteController::CheckIfDone() {
606 for (ACProviders::const_iterator i(providers_.begin()); i != providers_.end();
616 void AutocompleteController::StartExpireTimer() {
617 // Amount of time (in ms) between when the user stops typing and
618 // when we remove any copied entries. We do this from the time the
619 // user stopped typing as some providers (such as SearchProvider)
620 // wait for the user to stop typing before they initiate a query.
621 const int kExpireTimeMS = 500;
623 if (result_.HasCopiedMatches())
624 expire_timer_.Start(FROM_HERE,
625 base::TimeDelta::FromMilliseconds(kExpireTimeMS),
626 this, &AutocompleteController::ExpireCopiedEntries);
629 void AutocompleteController::StartStopTimer() {
630 if (!in_stop_timer_field_trial_)
633 // Amount of time (in ms) between when the user stops typing and
634 // when we send Stop() to every provider. This is intended to avoid
635 // the disruptive effect of belated omnibox updates, updates that
636 // come after the user has had to time to read the whole dropdown
637 // and doesn't expect it to change.
638 const int kStopTimeMS = 1500;
639 stop_timer_.Start(FROM_HERE,
640 base::TimeDelta::FromMilliseconds(kStopTimeMS),
641 base::Bind(&AutocompleteController::Stop,
642 base::Unretained(this),