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