Home | History | Annotate | Download | only in autocomplete
      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 
     38 namespace {
     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.
     43 void 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.
    143 void 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.
    160 bool 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.
    167 bool AutocompleteMatchHasCustomDescription(const AutocompleteMatch& match) {
    168   return match.type == AutocompleteMatchType::SEARCH_SUGGEST_ENTITY ||
    169       match.type == AutocompleteMatchType::SEARCH_SUGGEST_PROFILE;
    170 }
    171 
    172 }  // namespace
    173 
    174 AutocompleteController::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 
    227 AutocompleteController::~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 
    238 void 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 
    313 void 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 
    330 void 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 
    350 void 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 
    370 void 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 
    377 void 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 
    385 void 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 
    398 void AutocompleteController::ResetSession() {
    399   for (Providers::const_iterator i(providers_.begin()); i != providers_.end();
    400        ++i)
    401     (*i)->ResetSession();
    402 }
    403 
    404 void 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 
    426 void 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 
    438 void 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 
    514 void 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 
    564 void 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 
    598 void 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 
    647 void 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 
    658 void 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 
    669 void 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 
    682 void 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