components/omnibox/browser/autocomplete_controller.cc

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