autocomplete_controller.cc revision 1320f92c476a1ad9d19dba2a48c72b75566198e9 
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_controller.h"
6
7#include <set>
8#include <string>
9
10#include "base/format_macros.h"
11#include "base/logging.h"
12#include "base/metrics/histogram.h"
13#include "base/strings/string_number_conversions.h"
14#include "base/strings/stringprintf.h"
15#include "base/time/time.h"
16#include "chrome/browser/autocomplete/autocomplete_controller_delegate.h"
17#include "chrome/browser/autocomplete/bookmark_provider.h"
18#include "chrome/browser/autocomplete/builtin_provider.h"
19#include "chrome/browser/autocomplete/chrome_autocomplete_provider_client.h"
20#include "chrome/browser/autocomplete/history_quick_provider.h"
21#include "chrome/browser/autocomplete/history_url_provider.h"
22#include "chrome/browser/autocomplete/shortcuts_provider.h"
23#include "chrome/browser/autocomplete/zero_suggest_provider.h"
24#include "chrome/browser/chrome_notification_types.h"
25#include "components/omnibox/keyword_provider.h"
26#include "components/omnibox/omnibox_field_trial.h"
27#include "components/omnibox/search_provider.h"
28#include "components/search_engines/template_url.h"
29#include "components/search_engines/template_url_service.h"
30#include "content/public/browser/notification_service.h"
31#include "grit/components_strings.h"
32#include "ui/base/l10n/l10n_util.h"
33
34#if defined(ENABLE_EXTENSIONS)
35#include "chrome/browser/autocomplete/keyword_extensions_delegate_impl.h"
36#endif
37
38namespace {
39
40// Converts the given match to a type (and possibly subtype) based on the AQS
41// specification. For more details, see
42// http://goto.google.com/binary-clients-logging.
43void AutocompleteMatchToAssistedQuery(
44    const AutocompleteMatch::Type& match,
45    const AutocompleteProvider* provider,
46    size_t* type,
47    size_t* subtype) {
48  // This type indicates a native chrome suggestion.
49  *type = 69;
50  // Default value, indicating no subtype.
51  *subtype = base::string16::npos;
52
53  // If provider is TYPE_ZERO_SUGGEST, set the subtype accordingly.
54  // Type will be set in the switch statement below where we'll enter one of
55  // SEARCH_SUGGEST or NAVSUGGEST. This subtype indicates context-aware zero
56  // suggest.
57  if (provider &&
58      (provider->type() == AutocompleteProvider::TYPE_ZERO_SUGGEST) &&
59      (match != AutocompleteMatchType::SEARCH_SUGGEST_PERSONALIZED)) {
60    DCHECK((match == AutocompleteMatchType::SEARCH_SUGGEST) ||
61           (match == AutocompleteMatchType::NAVSUGGEST));
62    *subtype = 66;
63  }
64
65  switch (match) {
66    case AutocompleteMatchType::SEARCH_SUGGEST: {
67      // Do not set subtype here; subtype may have been set above.
68      *type = 0;
69      return;
70    }
71    case AutocompleteMatchType::SEARCH_SUGGEST_ENTITY: {
72      *subtype = 46;
73      return;
74    }
75    case AutocompleteMatchType::SEARCH_SUGGEST_INFINITE: {
76      *subtype = 33;
77      return;
78    }
79    case AutocompleteMatchType::SEARCH_SUGGEST_PERSONALIZED: {
80      *subtype = 39;
81      return;
82    }
83    case AutocompleteMatchType::SEARCH_SUGGEST_PROFILE: {
84      *subtype = 44;
85      return;
86    }
87    case AutocompleteMatchType::SEARCH_SUGGEST_ANSWER: {
88      *subtype = 70;
89      return;
90    }
91    case AutocompleteMatchType::NAVSUGGEST: {
92      // Do not set subtype here; subtype may have been set above.
93      *type = 5;
94      return;
95    }
96    case AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED: {
97      *subtype = 57;
98      return;
99    }
100    case AutocompleteMatchType::URL_WHAT_YOU_TYPED: {
101      *subtype = 58;
102      return;
103    }
104    case AutocompleteMatchType::SEARCH_HISTORY: {
105      *subtype = 59;
106      return;
107    }
108    case AutocompleteMatchType::HISTORY_URL: {
109      *subtype = 60;
110      return;
111    }
112    case AutocompleteMatchType::HISTORY_TITLE: {
113      *subtype = 61;
114      return;
115    }
116    case AutocompleteMatchType::HISTORY_BODY: {
117      *subtype = 62;
118      return;
119    }
120    case AutocompleteMatchType::HISTORY_KEYWORD: {
121      *subtype = 63;
122      return;
123    }
124    case AutocompleteMatchType::BOOKMARK_TITLE: {
125      *subtype = 65;
126      return;
127    }
128    case AutocompleteMatchType::NAVSUGGEST_PERSONALIZED: {
129      *subtype = 39;
130      return;
131    }
132    default: {
133      // This value indicates a native chrome suggestion with no named subtype
134      // (yet).
135      *subtype = 64;
136    }
137  }
138}
139
140// Appends available autocompletion of the given type, subtype, and number to
141// the existing available autocompletions string, encoding according to the
142// spec.
143void AppendAvailableAutocompletion(size_t type,
144                                   size_t subtype,
145                                   int count,
146                                   std::string* autocompletions) {
147  if (!autocompletions->empty())
148    autocompletions->append("j");
149  base::StringAppendF(autocompletions, "%" PRIuS, type);
150  // Subtype is optional - base::string16::npos indicates no subtype.
151  if (subtype != base::string16::npos)
152    base::StringAppendF(autocompletions, "i%" PRIuS, subtype);
153  if (count > 1)
154    base::StringAppendF(autocompletions, "l%d", count);
155}
156
157// Returns whether the autocompletion is trivial enough that we consider it
158// an autocompletion for which the omnibox autocompletion code did not add
159// any value.
160bool IsTrivialAutocompletion(const AutocompleteMatch& match) {
161  return match.type == AutocompleteMatchType::SEARCH_WHAT_YOU_TYPED ||
162      match.type == AutocompleteMatchType::URL_WHAT_YOU_TYPED ||
163      match.type == AutocompleteMatchType::SEARCH_OTHER_ENGINE;
164}
165
166// Whether this autocomplete match type supports custom descriptions.
167bool AutocompleteMatchHasCustomDescription(const AutocompleteMatch& match) {
168  return match.type == AutocompleteMatchType::SEARCH_SUGGEST_ENTITY ||
169      match.type == AutocompleteMatchType::SEARCH_SUGGEST_PROFILE;
170}
171
172}  // namespace
173
174AutocompleteController::AutocompleteController(
175    Profile* profile,
176    TemplateURLService* template_url_service,
177    AutocompleteControllerDelegate* delegate,
178    int provider_types)
179    : delegate_(delegate),
180      history_url_provider_(NULL),
181      keyword_provider_(NULL),
182      search_provider_(NULL),
183      zero_suggest_provider_(NULL),
184      stop_timer_duration_(OmniboxFieldTrial::StopTimerFieldTrialDuration()),
185      done_(true),
186      in_start_(false),
187      template_url_service_(template_url_service) {
188  provider_types &= ~OmniboxFieldTrial::GetDisabledProviderTypes();
189  if (provider_types & AutocompleteProvider::TYPE_BOOKMARK)
190    providers_.push_back(new BookmarkProvider(profile));
191  if (provider_types & AutocompleteProvider::TYPE_BUILTIN)
192    providers_.push_back(new BuiltinProvider());
193  if (provider_types & AutocompleteProvider::TYPE_HISTORY_QUICK)
194    providers_.push_back(new HistoryQuickProvider(profile));
195  if (provider_types & AutocompleteProvider::TYPE_HISTORY_URL) {
196    history_url_provider_ = new HistoryURLProvider(this, profile);
197    providers_.push_back(history_url_provider_);
198  }
199  // "Tab to search" can be used on all platforms other than Android.
200#if !defined(OS_ANDROID)
201  if (provider_types & AutocompleteProvider::TYPE_KEYWORD) {
202    keyword_provider_ = new KeywordProvider(this, template_url_service);
203#if defined(ENABLE_EXTENSIONS)
204    keyword_provider_->set_extensions_delegate(
205        scoped_ptr<KeywordExtensionsDelegate>(
206            new KeywordExtensionsDelegateImpl(profile, keyword_provider_)));
207#endif
208    providers_.push_back(keyword_provider_);
209  }
210#endif
211  if (provider_types & AutocompleteProvider::TYPE_SEARCH) {
212    search_provider_ = new SearchProvider(
213        this, template_url_service, scoped_ptr<AutocompleteProviderClient>(
214            new ChromeAutocompleteProviderClient(profile)));
215    providers_.push_back(search_provider_);
216  }
217  if (provider_types & AutocompleteProvider::TYPE_SHORTCUTS)
218    providers_.push_back(new ShortcutsProvider(profile));
219  if (provider_types & AutocompleteProvider::TYPE_ZERO_SUGGEST) {
220    zero_suggest_provider_ = ZeroSuggestProvider::Create(
221        this, template_url_service, profile);
222    if (zero_suggest_provider_)
223      providers_.push_back(zero_suggest_provider_);
224  }
225}
226
227AutocompleteController::~AutocompleteController() {
228  // The providers may have tasks outstanding that hold refs to them.  We need
229  // to ensure they won't call us back if they outlive us.  (Practically,
230  // calling Stop() should also cancel those tasks and make it so that we hold
231  // the only refs.)  We also don't want to bother notifying anyone of our
232  // result changes here, because the notification observer is in the midst of
233  // shutdown too, so we don't ask Stop() to clear |result_| (and notify).
234  result_.Reset();  // Not really necessary.
235  Stop(false);
236}
237
238void AutocompleteController::Start(const AutocompleteInput& input) {
239  const base::string16 old_input_text(input_.text());
240  const bool old_want_asynchronous_matches = input_.want_asynchronous_matches();
241  input_ = input;
242
243  // See if we can avoid rerunning autocomplete when the query hasn't changed
244  // much.  When the user presses or releases the ctrl key, the desired_tld
245  // changes, and when the user finishes an IME composition, inline autocomplete
246  // may no longer be prevented.  In both these cases the text itself hasn't
247  // changed since the last query, and some providers can do much less work (and
248  // get matches back more quickly).  Taking advantage of this reduces flicker.
249  //
250  // NOTE: This comes after constructing |input_| above since that construction
251  // can change the text string (e.g. by stripping off a leading '?').
252  const bool minimal_changes = (input_.text() == old_input_text) &&
253      (input_.want_asynchronous_matches() == old_want_asynchronous_matches);
254
255  expire_timer_.Stop();
256  stop_timer_.Stop();
257
258  // Start the new query.
259  in_start_ = true;
260  base::TimeTicks start_time = base::TimeTicks::Now();
261  for (Providers::iterator i(providers_.begin()); i != providers_.end(); ++i) {
262    // TODO(mpearson): Remove timing code once bugs 178705 / 237703 / 168933
263    // are resolved.
264    base::TimeTicks provider_start_time = base::TimeTicks::Now();
265
266    // Call Start() on ZeroSuggestProvider with an INVALID AutocompleteInput
267    // to clear out zero-suggest |matches_|.
268    if (i->get() == zero_suggest_provider_)
269      (*i)->Start(AutocompleteInput(), minimal_changes);
270    else
271      (*i)->Start(input_, minimal_changes);
272
273    if (!input.want_asynchronous_matches())
274      DCHECK((*i)->done());
275    base::TimeTicks provider_end_time = base::TimeTicks::Now();
276    std::string name = std::string("Omnibox.ProviderTime.") + (*i)->GetName();
277    base::HistogramBase* counter = base::Histogram::FactoryGet(
278        name, 1, 5000, 20, base::Histogram::kUmaTargetedHistogramFlag);
279    counter->Add(static_cast<int>(
280        (provider_end_time - provider_start_time).InMilliseconds()));
281  }
282  if (input.want_asynchronous_matches() && (input.text().length() < 6)) {
283    base::TimeTicks end_time = base::TimeTicks::Now();
284    std::string name = "Omnibox.QueryTime." + base::IntToString(
285        input.text().length());
286    base::HistogramBase* counter = base::Histogram::FactoryGet(
287        name, 1, 1000, 50, base::Histogram::kUmaTargetedHistogramFlag);
288    counter->Add(static_cast<int>((end_time - start_time).InMilliseconds()));
289  }
290  in_start_ = false;
291  CheckIfDone();
292  // The second true forces saying the default match has changed.
293  // This triggers the edit model to update things such as the inline
294  // autocomplete state.  In particular, if the user has typed a key
295  // since the last notification, and we're now re-running
296  // autocomplete, then we need to update the inline autocompletion
297  // even if the current match is for the same URL as the last run's
298  // default match.  Likewise, the controller doesn't know what's
299  // happened in the edit since the last time it ran autocomplete.
300  // The user might have selected all the text and hit delete, then
301  // typed a new character.  The selection and delete won't send any
302  // signals to the controller so it doesn't realize that anything was
303  // cleared or changed.  Even if the default match hasn't changed, we
304  // need the edit model to update the display.
305  UpdateResult(false, true);
306
307  if (!done_) {
308    StartExpireTimer();
309    StartStopTimer();
310  }
311}
312
313void AutocompleteController::Stop(bool clear_result) {
314  for (Providers::const_iterator i(providers_.begin()); i != providers_.end();
315       ++i) {
316    (*i)->Stop(clear_result);
317  }
318
319  expire_timer_.Stop();
320  stop_timer_.Stop();
321  done_ = true;
322  if (clear_result && !result_.empty()) {
323    result_.Reset();
324    // NOTE: We pass in false since we're trying to only clear the popup, not
325    // touch the edit... this is all a mess and should be cleaned up :(
326    NotifyChanged(false);
327  }
328}
329
330void AutocompleteController::StartZeroSuggest(const AutocompleteInput& input) {
331  if (zero_suggest_provider_ == NULL)
332    return;
333
334  DCHECK(!in_start_);  // We should not be already running a query.
335
336  // Call Start() on all prefix-based providers with an INVALID
337  // AutocompleteInput to clear out cached |matches_|, which ensures that
338  // they aren't used with zero suggest.
339  for (Providers::iterator i(providers_.begin()); i != providers_.end(); ++i) {
340    if (i->get() == zero_suggest_provider_)
341      (*i)->Start(input, false);
342    else
343      (*i)->Start(AutocompleteInput(), false);
344  }
345
346  if (!zero_suggest_provider_->matches().empty())
347    UpdateResult(false, false);
348}
349
350void AutocompleteController::DeleteMatch(const AutocompleteMatch& match) {
351  DCHECK(match.SupportsDeletion());
352
353  // Delete duplicate matches attached to the main match first.
354  for (ACMatches::const_iterator it(match.duplicate_matches.begin());
355       it != match.duplicate_matches.end(); ++it) {
356    if (it->deletable)
357      it->provider->DeleteMatch(*it);
358  }
359
360  if (match.deletable)
361    match.provider->DeleteMatch(match);
362
363  OnProviderUpdate(true);
364
365  // If we're not done, we might attempt to redisplay the deleted match. Make
366  // sure we aren't displaying it by removing any old entries.
367  ExpireCopiedEntries();
368}
369
370void AutocompleteController::ExpireCopiedEntries() {
371  // The first true makes UpdateResult() clear out the results and
372  // regenerate them, thus ensuring that no results from the previous
373  // result set remain.
374  UpdateResult(true, false);
375}
376
377void AutocompleteController::OnProviderUpdate(bool updated_matches) {
378  CheckIfDone();
379  // Multiple providers may provide synchronous results, so we only update the
380  // results if we're not in Start().
381  if (!in_start_ && (updated_matches || done_))
382    UpdateResult(false, false);
383}
384
385void AutocompleteController::AddProvidersInfo(
386    ProvidersInfo* provider_info) const {
387  provider_info->clear();
388  for (Providers::const_iterator i(providers_.begin()); i != providers_.end();
389       ++i) {
390    // Add per-provider info, if any.
391    (*i)->AddProviderInfo(provider_info);
392
393    // This is also a good place to put code to add info that you want to
394    // add for every provider.
395  }
396}
397
398void AutocompleteController::ResetSession() {
399  for (Providers::const_iterator i(providers_.begin()); i != providers_.end();
400       ++i)
401    (*i)->ResetSession();
402}
403
404void AutocompleteController::UpdateMatchDestinationURLWithQueryFormulationTime(
405    base::TimeDelta query_formulation_time,
406    AutocompleteMatch* match) const {
407  if (!match->search_terms_args.get() ||
408      match->search_terms_args->assisted_query_stats.empty())
409    return;
410
411  // Append the query formulation time (time from when the user first typed a
412  // character into the omnibox to when the user selected a query) and whether
413  // a field trial has triggered to the AQS parameter.
414  TemplateURLRef::SearchTermsArgs search_terms_args(*match->search_terms_args);
415  search_terms_args.assisted_query_stats += base::StringPrintf(
416      ".%" PRId64 "j%dj%d",
417      query_formulation_time.InMilliseconds(),
418      (search_provider_ &&
419       search_provider_->field_trial_triggered_in_session()) ||
420      (zero_suggest_provider_ &&
421       zero_suggest_provider_->field_trial_triggered_in_session()),
422      input_.current_page_classification());
423  UpdateMatchDestinationURL(search_terms_args, match);
424}
425
426void AutocompleteController::UpdateMatchDestinationURL(
427    const TemplateURLRef::SearchTermsArgs& search_terms_args,
428    AutocompleteMatch* match) const {
429  TemplateURL* template_url = match->GetTemplateURL(
430      template_url_service_, false);
431  if (!template_url)
432    return;
433
434  match->destination_url = GURL(template_url->url_ref().ReplaceSearchTerms(
435      search_terms_args, template_url_service_->search_terms_data()));
436}
437
438void AutocompleteController::UpdateResult(
439    bool regenerate_result,
440    bool force_notify_default_match_changed) {
441  const bool last_default_was_valid = result_.default_match() != result_.end();
442  // The following three variables are only set and used if
443  // |last_default_was_valid|.
444  base::string16 last_default_fill_into_edit, last_default_keyword,
445      last_default_associated_keyword;
446  if (last_default_was_valid) {
447    last_default_fill_into_edit = result_.default_match()->fill_into_edit;
448    last_default_keyword = result_.default_match()->keyword;
449    if (result_.default_match()->associated_keyword != NULL)
450      last_default_associated_keyword =
451          result_.default_match()->associated_keyword->keyword;
452  }
453
454  if (regenerate_result)
455    result_.Reset();
456
457  AutocompleteResult last_result;
458  last_result.Swap(&result_);
459
460  for (Providers::const_iterator i(providers_.begin());
461       i != providers_.end(); ++i)
462    result_.AppendMatches((*i)->matches());
463
464  // Sort the matches and trim to a small number of "best" matches.
465  result_.SortAndCull(input_, template_url_service_);
466
467  // Need to validate before invoking CopyOldMatches as the old matches are not
468  // valid against the current input.
469#ifndef NDEBUG
470  result_.Validate();
471#endif
472
473  if (!done_) {
474    // This conditional needs to match the conditional in Start that invokes
475    // StartExpireTimer.
476    result_.CopyOldMatches(input_, last_result, template_url_service_);
477  }
478
479  UpdateKeywordDescriptions(&result_);
480  UpdateAssociatedKeywords(&result_);
481  UpdateAssistedQueryStats(&result_);
482  if (search_provider_)
483    search_provider_->RegisterDisplayedAnswers(result_);
484
485  const bool default_is_valid = result_.default_match() != result_.end();
486  base::string16 default_associated_keyword;
487  if (default_is_valid &&
488      (result_.default_match()->associated_keyword != NULL)) {
489    default_associated_keyword =
490        result_.default_match()->associated_keyword->keyword;
491  }
492  // We've gotten async results. Send notification that the default match
493  // updated if fill_into_edit, associated_keyword, or keyword differ.  (The
494  // second can change if we've just started Chrome and the keyword database
495  // finishes loading while processing this request.  The third can change
496  // if we swapped from interpreting the input as a search--which gets
497  // labeled with the default search provider's keyword--to a URL.)
498  // We don't check the URL as that may change for the default match
499  // even though the fill into edit hasn't changed (see SearchProvider
500  // for one case of this).
501  const bool notify_default_match =
502      (last_default_was_valid != default_is_valid) ||
503      (last_default_was_valid &&
504       ((result_.default_match()->fill_into_edit !=
505          last_default_fill_into_edit) ||
506        (default_associated_keyword != last_default_associated_keyword) ||
507        (result_.default_match()->keyword != last_default_keyword)));
508  if (notify_default_match)
509    last_time_default_match_changed_ = base::TimeTicks::Now();
510
511  NotifyChanged(force_notify_default_match_changed || notify_default_match);
512}
513
514void AutocompleteController::UpdateAssociatedKeywords(
515    AutocompleteResult* result) {
516  if (!keyword_provider_)
517    return;
518
519  // Determine if the user's input is an exact keyword match.
520  base::string16 exact_keyword = keyword_provider_->GetKeywordForText(
521      TemplateURLService::CleanUserInputKeyword(input_.text()));
522
523  std::set<base::string16> keywords;
524  for (ACMatches::iterator match(result->begin()); match != result->end();
525       ++match) {
526    base::string16 keyword(
527        match->GetSubstitutingExplicitlyInvokedKeyword(template_url_service_));
528    if (!keyword.empty()) {
529      keywords.insert(keyword);
530      continue;
531    }
532
533    // When the user has typed an exact keyword, we want tab-to-search on the
534    // default match to select that keyword, even if the match
535    // inline-autocompletes to a different keyword.  (This prevents inline
536    // autocompletions from blocking a user's attempts to use an explicitly-set
537    // keyword of their own creation.)  So use |exact_keyword| if it's
538    // available.
539    if (!exact_keyword.empty() && !keywords.count(exact_keyword)) {
540      keywords.insert(exact_keyword);
541      match->associated_keyword.reset(new AutocompleteMatch(
542          keyword_provider_->CreateVerbatimMatch(exact_keyword,
543                                                 exact_keyword, input_)));
544      continue;
545    }
546
547    // Otherwise, set a match's associated keyword based on the match's
548    // fill_into_edit, which should take inline autocompletions into account.
549    keyword = keyword_provider_->GetKeywordForText(match->fill_into_edit);
550
551    // Only add the keyword if the match does not have a duplicate keyword with
552    // a more relevant match.
553    if (!keyword.empty() && !keywords.count(keyword)) {
554      keywords.insert(keyword);
555      match->associated_keyword.reset(new AutocompleteMatch(
556          keyword_provider_->CreateVerbatimMatch(match->fill_into_edit,
557                                                 keyword, input_)));
558    } else {
559      match->associated_keyword.reset();
560    }
561  }
562}
563
564void AutocompleteController::UpdateKeywordDescriptions(
565    AutocompleteResult* result) {
566  base::string16 last_keyword;
567  for (AutocompleteResult::iterator i(result->begin()); i != result->end();
568       ++i) {
569    if (AutocompleteMatch::IsSearchType(i->type)) {
570      if (AutocompleteMatchHasCustomDescription(*i))
571        continue;
572      i->description.clear();
573      i->description_class.clear();
574      DCHECK(!i->keyword.empty());
575      if (i->keyword != last_keyword) {
576        const TemplateURL* template_url =
577            i->GetTemplateURL(template_url_service_, false);
578        if (template_url) {
579          // For extension keywords, just make the description the extension
580          // name -- don't assume that the normal search keyword description is
581          // applicable.
582          i->description = template_url->AdjustedShortNameForLocaleDirection();
583          if (template_url->GetType() != TemplateURL::OMNIBOX_API_EXTENSION) {
584            i->description = l10n_util::GetStringFUTF16(
585                IDS_AUTOCOMPLETE_SEARCH_DESCRIPTION, i->description);
586          }
587          i->description_class.push_back(
588              ACMatchClassification(0, ACMatchClassification::DIM));
589        }
590        last_keyword = i->keyword;
591      }
592    } else {
593      last_keyword.clear();
594    }
595  }
596}
597
598void AutocompleteController::UpdateAssistedQueryStats(
599    AutocompleteResult* result) {
600  if (result->empty())
601    return;
602
603  // Build the impressions string (the AQS part after ".").
604  std::string autocompletions;
605  int count = 0;
606  size_t last_type = base::string16::npos;
607  size_t last_subtype = base::string16::npos;
608  for (ACMatches::iterator match(result->begin()); match != result->end();
609       ++match) {
610    size_t type = base::string16::npos;
611    size_t subtype = base::string16::npos;
612    AutocompleteMatchToAssistedQuery(
613        match->type, match->provider, &type, &subtype);
614    if (last_type != base::string16::npos &&
615        (type != last_type || subtype != last_subtype)) {
616      AppendAvailableAutocompletion(
617          last_type, last_subtype, count, &autocompletions);
618      count = 1;
619    } else {
620      count++;
621    }
622    last_type = type;
623    last_subtype = subtype;
624  }
625  AppendAvailableAutocompletion(
626      last_type, last_subtype, count, &autocompletions);
627  // Go over all matches and set AQS if the match supports it.
628  for (size_t index = 0; index < result->size(); ++index) {
629    AutocompleteMatch* match = result->match_at(index);
630    const TemplateURL* template_url =
631        match->GetTemplateURL(template_url_service_, false);
632    if (!template_url || !match->search_terms_args.get())
633      continue;
634    std::string selected_index;
635    // Prevent trivial suggestions from getting credit for being selected.
636    if (!IsTrivialAutocompletion(*match))
637      selected_index = base::StringPrintf("%" PRIuS, index);
638    match->search_terms_args->assisted_query_stats =
639        base::StringPrintf("chrome.%s.%s",
640                           selected_index.c_str(),
641                           autocompletions.c_str());
642    match->destination_url = GURL(template_url->url_ref().ReplaceSearchTerms(
643        *match->search_terms_args, template_url_service_->search_terms_data()));
644  }
645}
646
647void AutocompleteController::NotifyChanged(bool notify_default_match) {
648  if (delegate_)
649    delegate_->OnResultChanged(notify_default_match);
650  if (done_) {
651    content::NotificationService::current()->Notify(
652        chrome::NOTIFICATION_AUTOCOMPLETE_CONTROLLER_RESULT_READY,
653        content::Source<AutocompleteController>(this),
654        content::NotificationService::NoDetails());
655  }
656}
657
658void AutocompleteController::CheckIfDone() {
659  for (Providers::const_iterator i(providers_.begin()); i != providers_.end();
660       ++i) {
661    if (!(*i)->done()) {
662      done_ = false;
663      return;
664    }
665  }
666  done_ = true;
667}
668
669void AutocompleteController::StartExpireTimer() {
670  // Amount of time (in ms) between when the user stops typing and
671  // when we remove any copied entries. We do this from the time the
672  // user stopped typing as some providers (such as SearchProvider)
673  // wait for the user to stop typing before they initiate a query.
674  const int kExpireTimeMS = 500;
675
676  if (result_.HasCopiedMatches())
677    expire_timer_.Start(FROM_HERE,
678                        base::TimeDelta::FromMilliseconds(kExpireTimeMS),
679                        this, &AutocompleteController::ExpireCopiedEntries);
680}
681
682void AutocompleteController::StartStopTimer() {
683  stop_timer_.Start(FROM_HERE,
684                    stop_timer_duration_,
685                    base::Bind(&AutocompleteController::Stop,
686                               base::Unretained(this),
687                               false));
688}
689