chrome/browser/predictors/autocomplete_action_predictor.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/predictors/autocomplete_action_predictor.h"
   6
   7 #include <math.h>
   8
   9 #include <vector>
  10
  11 #include "base/bind.h"
  12 #include "base/guid.h"
  13 #include "base/i18n/case_conversion.h"
  14 #include "base/metrics/histogram.h"
  15 #include "base/strings/string_util.h"
  16 #include "base/strings/stringprintf.h"
  17 #include "base/strings/utf_string_conversions.h"
  18 #include "chrome/browser/chrome_notification_types.h"
  19 #include "chrome/browser/history/history_service.h"
  20 #include "chrome/browser/history/history_service_factory.h"
  21 #include "chrome/browser/omnibox/omnibox_log.h"
  22 #include "chrome/browser/predictors/autocomplete_action_predictor_factory.h"
  23 #include "chrome/browser/predictors/predictor_database.h"
  24 #include "chrome/browser/predictors/predictor_database_factory.h"
  25 #include "chrome/browser/prerender/prerender_field_trial.h"
  26 #include "chrome/browser/prerender/prerender_handle.h"
  27 #include "chrome/browser/prerender/prerender_manager.h"
  28 #include "chrome/browser/prerender/prerender_manager_factory.h"
  29 #include "chrome/browser/profiles/profile.h"
  30 #include "chrome/browser/ui/omnibox/omnibox_popup_model.h"
  31 #include "components/history/core/browser/in_memory_database.h"
  32 #include "components/omnibox/autocomplete_match.h"
  33 #include "components/omnibox/autocomplete_result.h"
  34 #include "content/public/browser/browser_thread.h"
  35 #include "content/public/browser/notification_details.h"
  36 #include "content/public/browser/notification_service.h"
  37 #include "content/public/browser/notification_source.h"
  38
  39 namespace {
  40
  41 const float kConfidenceCutoff[] = {
  42   0.8f,
  43   0.5f
  44 };
  45
  46 static_assert(arraysize(kConfidenceCutoff) ==
  47               predictors::AutocompleteActionPredictor::LAST_PREDICT_ACTION,
  48               "kConfidenceCutoff count should match LAST_PREDICT_ACTION");
  49
  50 const size_t kMinimumUserTextLength = 1;
  51 const int kMinimumNumberOfHits = 3;
  52
  53 enum DatabaseAction {
  54   DATABASE_ACTION_ADD,
  55   DATABASE_ACTION_UPDATE,
  56   DATABASE_ACTION_DELETE_SOME,
  57   DATABASE_ACTION_DELETE_ALL,
  58   DATABASE_ACTION_COUNT
  59 };
  60
  61 }  // namespace
  62
  63 namespace predictors {
  64
  65 const int AutocompleteActionPredictor::kMaximumDaysToKeepEntry = 14;
  66
  67 AutocompleteActionPredictor::AutocompleteActionPredictor(Profile* profile)
  68     : profile_(profile),
  69       main_profile_predictor_(NULL),
  70       incognito_predictor_(NULL),
  71       initialized_(false),
  72       history_service_observer_(this) {
  73   if (profile_->IsOffTheRecord()) {
  74     main_profile_predictor_ = AutocompleteActionPredictorFactory::GetForProfile(
  75         profile_->GetOriginalProfile());
  76     DCHECK(main_profile_predictor_);
  77     main_profile_predictor_->incognito_predictor_ = this;
  78     if (main_profile_predictor_->initialized_)
  79       CopyFromMainProfile();
  80   } else {
  81     // Request the in-memory database from the history to force it to load so
  82     // it's available as soon as possible.
  83     HistoryService* history_service = HistoryServiceFactory::GetForProfile(
  84         profile_, ServiceAccessType::EXPLICIT_ACCESS);
  85     if (history_service)
  86       history_service->InMemoryDatabase();
  87
  88     table_ =
  89         PredictorDatabaseFactory::GetForProfile(profile_)->autocomplete_table();
  90
  91     // Observe all main frame loads so we can wait for the first to complete
  92     // before accessing DB and IO threads to build the local cache.
  93     notification_registrar_.Add(this,
  94                                 content::NOTIFICATION_LOAD_COMPLETED_MAIN_FRAME,
  95                                 content::NotificationService::AllSources());
  96   }
  97 }
  98
  99 AutocompleteActionPredictor::~AutocompleteActionPredictor() {
 100   if (main_profile_predictor_)
 101     main_profile_predictor_->incognito_predictor_ = NULL;
 102   else if (incognito_predictor_)
 103     incognito_predictor_->main_profile_predictor_ = NULL;
 104   if (prerender_handle_.get())
 105     prerender_handle_->OnCancel();
 106 }
 107
 108 void AutocompleteActionPredictor::RegisterTransitionalMatches(
 109     const base::string16& user_text,
 110     const AutocompleteResult& result) {
 111   if (user_text.length() < kMinimumUserTextLength)
 112     return;
 113   const base::string16 lower_user_text(base::i18n::ToLower(user_text));
 114
 115   // Merge this in to an existing match if we already saw |user_text|
 116   std::vector<TransitionalMatch>::iterator match_it =
 117       std::find(transitional_matches_.begin(), transitional_matches_.end(),
 118                 lower_user_text);
 119
 120   if (match_it == transitional_matches_.end()) {
 121     TransitionalMatch transitional_match;
 122     transitional_match.user_text = lower_user_text;
 123     match_it = transitional_matches_.insert(transitional_matches_.end(),
 124                                             transitional_match);
 125   }
 126
 127   for (const auto& i : result) {
 128     if (std::find(match_it->urls.begin(), match_it->urls.end(),
 129                   i.destination_url) == match_it->urls.end()) {
 130       match_it->urls.push_back(i.destination_url);
 131     }
 132   }
 133 }
 134
 135 void AutocompleteActionPredictor::ClearTransitionalMatches() {
 136   transitional_matches_.clear();
 137 }
 138
 139 void AutocompleteActionPredictor::CancelPrerender() {
 140   // If the prerender has already been abandoned, leave it to its own timeout;
 141   // this normally gets called immediately after OnOmniboxOpenedUrl.
 142   if (prerender_handle_ && !prerender_handle_->IsAbandoned()) {
 143     prerender_handle_->OnCancel();
 144     prerender_handle_.reset();
 145   }
 146 }
 147
 148 void AutocompleteActionPredictor::StartPrerendering(
 149     const GURL& url,
 150     content::SessionStorageNamespace* session_storage_namespace,
 151     const gfx::Size& size) {
 152   // Only cancel the old prerender after starting the new one, so if the URLs
 153   // are the same, the underlying prerender will be reused.
 154   scoped_ptr<prerender::PrerenderHandle> old_prerender_handle(
 155       prerender_handle_.release());
 156   if (prerender::PrerenderManager* prerender_manager =
 157           prerender::PrerenderManagerFactory::GetForProfile(profile_)) {
 158     prerender_handle_.reset(prerender_manager->AddPrerenderFromOmnibox(
 159         url, session_storage_namespace, size));
 160   }
 161   if (old_prerender_handle)
 162     old_prerender_handle->OnCancel();
 163 }
 164
 165 // Given a match, return a recommended action.
 166 AutocompleteActionPredictor::Action
 167     AutocompleteActionPredictor::RecommendAction(
 168         const base::string16& user_text,
 169         const AutocompleteMatch& match) const {
 170   bool is_in_db = false;
 171   const double confidence = CalculateConfidence(user_text, match, &is_in_db);
 172   DCHECK(confidence >= 0.0 && confidence <= 1.0);
 173
 174   UMA_HISTOGRAM_BOOLEAN("AutocompleteActionPredictor.MatchIsInDb", is_in_db);
 175
 176   if (is_in_db) {
 177     // Multiple enties with the same URL are fine as the confidence may be
 178     // different.
 179     tracked_urls_.push_back(std::make_pair(match.destination_url, confidence));
 180     UMA_HISTOGRAM_COUNTS_100("AutocompleteActionPredictor.Confidence",
 181                              confidence * 100);
 182   }
 183
 184   // Map the confidence to an action.
 185   Action action = ACTION_NONE;
 186   for (int i = 0; i < LAST_PREDICT_ACTION; ++i) {
 187     if (confidence >= kConfidenceCutoff[i]) {
 188       action = static_cast<Action>(i);
 189       break;
 190     }
 191   }
 192
 193   // Downgrade prerender to preconnect if this is a search match or if omnibox
 194   // prerendering is disabled. There are cases when Instant will not handle a
 195   // search suggestion and in those cases it would be good to prerender the
 196   // search results, however search engines have not been set up to correctly
 197   // handle being prerendered and until they are we should avoid it.
 198   // http://crbug.com/117495
 199   if (action == ACTION_PRERENDER &&
 200       (AutocompleteMatch::IsSearchType(match.type) ||
 201        !prerender::IsOmniboxEnabled(profile_))) {
 202     action = ACTION_PRECONNECT;
 203   }
 204
 205   return action;
 206 }
 207
 208 // Return true if the suggestion type warrants a TCP/IP preconnection.
 209 // i.e., it is now quite likely that the user will select the related domain.
 210 // static
 211 bool AutocompleteActionPredictor::IsPreconnectable(
 212     const AutocompleteMatch& match) {
 213   return AutocompleteMatch::IsSearchType(match.type);
 214 }
 215
 216 bool AutocompleteActionPredictor::IsPrerenderAbandonedForTesting() {
 217   return prerender_handle_ && prerender_handle_->IsAbandoned();
 218 }
 219
 220 void AutocompleteActionPredictor::Observe(
 221     int type,
 222     const content::NotificationSource& source,
 223     const content::NotificationDetails& details) {
 224   switch (type) {
 225     case content::NOTIFICATION_LOAD_COMPLETED_MAIN_FRAME:
 226       CreateLocalCachesFromDatabase();
 227       notification_registrar_.Remove(
 228           this,
 229           content::NOTIFICATION_LOAD_COMPLETED_MAIN_FRAME,
 230           content::NotificationService::AllSources());
 231       break;
 232     case chrome::NOTIFICATION_OMNIBOX_OPENED_URL: {
 233       DCHECK(initialized_);
 234
 235       // TODO(dominich): This doesn't need to be synchronous. Investigate
 236       // posting it as a task to be run later.
 237       OnOmniboxOpenedUrl(*content::Details<OmniboxLog>(details).ptr());
 238       break;
 239     }
 240
 241     default:
 242       NOTREACHED() << "Unexpected notification observed.";
 243       break;
 244   }
 245 }
 246
 247 void AutocompleteActionPredictor::CreateLocalCachesFromDatabase() {
 248   // Create local caches using the database as loaded. We will garbage collect
 249   // rows from the caches and the database once the history service is
 250   // available.
 251   std::vector<AutocompleteActionPredictorTable::Row>* rows =
 252       new std::vector<AutocompleteActionPredictorTable::Row>();
 253   content::BrowserThread::PostTaskAndReply(content::BrowserThread::DB,
 254       FROM_HERE,
 255       base::Bind(&AutocompleteActionPredictorTable::GetAllRows, table_, rows),
 256       base::Bind(&AutocompleteActionPredictor::CreateCaches, AsWeakPtr(),
 257                  base::Owned(rows)));
 258 }
 259
 260 void AutocompleteActionPredictor::DeleteAllRows() {
 261   if (!initialized_)
 262     return;
 263
 264   db_cache_.clear();
 265   db_id_cache_.clear();
 266
 267   if (table_.get()) {
 268     content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE,
 269         base::Bind(&AutocompleteActionPredictorTable::DeleteAllRows,
 270                    table_));
 271   }
 272
 273   UMA_HISTOGRAM_ENUMERATION("AutocompleteActionPredictor.DatabaseAction",
 274                             DATABASE_ACTION_DELETE_ALL, DATABASE_ACTION_COUNT);
 275 }
 276
 277 void AutocompleteActionPredictor::DeleteRowsWithURLs(
 278     const history::URLRows& rows) {
 279   if (!initialized_)
 280     return;
 281
 282   std::vector<AutocompleteActionPredictorTable::Row::Id> id_list;
 283
 284   for (DBCacheMap::iterator it = db_cache_.begin(); it != db_cache_.end();) {
 285     if (std::find_if(rows.begin(), rows.end(),
 286         history::URLRow::URLRowHasURL(it->first.url)) != rows.end()) {
 287       const DBIdCacheMap::iterator id_it = db_id_cache_.find(it->first);
 288       DCHECK(id_it != db_id_cache_.end());
 289       id_list.push_back(id_it->second);
 290       db_id_cache_.erase(id_it);
 291       db_cache_.erase(it++);
 292     } else {
 293       ++it;
 294     }
 295   }
 296
 297   if (table_.get()) {
 298     content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE,
 299         base::Bind(&AutocompleteActionPredictorTable::DeleteRows, table_,
 300                    id_list));
 301   }
 302
 303   UMA_HISTOGRAM_ENUMERATION("AutocompleteActionPredictor.DatabaseAction",
 304                             DATABASE_ACTION_DELETE_SOME, DATABASE_ACTION_COUNT);
 305 }
 306
 307 void AutocompleteActionPredictor::OnOmniboxOpenedUrl(const OmniboxLog& log) {
 308   if (log.text.length() < kMinimumUserTextLength)
 309     return;
 310
 311   // Do not attempt to learn from omnibox interactions where the omnibox
 312   // dropdown is closed.  In these cases the user text (|log.text|) that we
 313   // learn from is either empty or effectively identical to the destination
 314   // string.  In either case, it can't teach us much.  Also do not attempt
 315   // to learn from paste-and-go actions even if the popup is open because
 316   // the paste-and-go destination has no relation to whatever text the user
 317   // may have typed.
 318   if (!log.is_popup_open || log.is_paste_and_go)
 319     return;
 320
 321   // Abandon the current prerender. If it is to be used, it will be used very
 322   // soon, so use the lower timeout.
 323   if (prerender_handle_) {
 324     prerender_handle_->OnNavigateAway();
 325     // Don't release |prerender_handle_| so it is canceled if it survives to the
 326     // next StartPrerendering call.
 327   }
 328
 329   UMA_HISTOGRAM_BOOLEAN(
 330       base::StringPrintf("Prerender.OmniboxNavigationsCouldPrerender%s",
 331                          prerender::PrerenderManager::GetModeString()).c_str(),
 332       prerender::IsOmniboxEnabled(profile_));
 333
 334   const AutocompleteMatch& match = log.result.match_at(log.selected_index);
 335   const GURL& opened_url = match.destination_url;
 336   const base::string16 lower_user_text(base::i18n::ToLower(log.text));
 337
 338   // Traverse transitional matches for those that have a user_text that is a
 339   // prefix of |lower_user_text|.
 340   std::vector<AutocompleteActionPredictorTable::Row> rows_to_add;
 341   std::vector<AutocompleteActionPredictorTable::Row> rows_to_update;
 342
 343   for (std::vector<TransitionalMatch>::const_iterator it =
 344         transitional_matches_.begin(); it != transitional_matches_.end();
 345         ++it) {
 346     if (!StartsWith(lower_user_text, it->user_text, true))
 347       continue;
 348
 349     // Add entries to the database for those matches.
 350     for (std::vector<GURL>::const_iterator url_it = it->urls.begin();
 351           url_it != it->urls.end(); ++url_it) {
 352       DCHECK(it->user_text.length() >= kMinimumUserTextLength);
 353       const DBCacheKey key = { it->user_text, *url_it };
 354       const bool is_hit = (*url_it == opened_url);
 355
 356       AutocompleteActionPredictorTable::Row row;
 357       row.user_text = key.user_text;
 358       row.url = key.url;
 359
 360       DBCacheMap::iterator it = db_cache_.find(key);
 361       if (it == db_cache_.end()) {
 362         row.id = base::GenerateGUID();
 363         row.number_of_hits = is_hit ? 1 : 0;
 364         row.number_of_misses = is_hit ? 0 : 1;
 365
 366         rows_to_add.push_back(row);
 367       } else {
 368         DCHECK(db_id_cache_.find(key) != db_id_cache_.end());
 369         row.id = db_id_cache_.find(key)->second;
 370         row.number_of_hits = it->second.number_of_hits + (is_hit ? 1 : 0);
 371         row.number_of_misses = it->second.number_of_misses + (is_hit ? 0 : 1);
 372
 373         rows_to_update.push_back(row);
 374       }
 375     }
 376   }
 377   if (rows_to_add.size() > 0 || rows_to_update.size() > 0)
 378     AddAndUpdateRows(rows_to_add, rows_to_update);
 379
 380   ClearTransitionalMatches();
 381
 382   // Check against tracked urls and log accuracy for the confidence we
 383   // predicted.
 384   for (std::vector<std::pair<GURL, double> >::const_iterator it =
 385        tracked_urls_.begin(); it != tracked_urls_.end();
 386        ++it) {
 387     if (opened_url == it->first) {
 388       UMA_HISTOGRAM_COUNTS_100("AutocompleteActionPredictor.AccurateCount",
 389                                it->second * 100);
 390     }
 391   }
 392   tracked_urls_.clear();
 393 }
 394
 395 void AutocompleteActionPredictor::AddAndUpdateRows(
 396     const AutocompleteActionPredictorTable::Rows& rows_to_add,
 397     const AutocompleteActionPredictorTable::Rows& rows_to_update) {
 398   if (!initialized_)
 399     return;
 400
 401   for (AutocompleteActionPredictorTable::Rows::const_iterator it =
 402        rows_to_add.begin(); it != rows_to_add.end(); ++it) {
 403     const DBCacheKey key = { it->user_text, it->url };
 404     DBCacheValue value = { it->number_of_hits, it->number_of_misses };
 405
 406     DCHECK(db_cache_.find(key) == db_cache_.end());
 407
 408     db_cache_[key] = value;
 409     db_id_cache_[key] = it->id;
 410     UMA_HISTOGRAM_ENUMERATION("AutocompleteActionPredictor.DatabaseAction",
 411                               DATABASE_ACTION_ADD, DATABASE_ACTION_COUNT);
 412   }
 413   for (AutocompleteActionPredictorTable::Rows::const_iterator it =
 414        rows_to_update.begin(); it != rows_to_update.end(); ++it) {
 415     const DBCacheKey key = { it->user_text, it->url };
 416
 417     DBCacheMap::iterator db_it = db_cache_.find(key);
 418     DCHECK(db_it != db_cache_.end());
 419     DCHECK(db_id_cache_.find(key) != db_id_cache_.end());
 420
 421     db_it->second.number_of_hits = it->number_of_hits;
 422     db_it->second.number_of_misses = it->number_of_misses;
 423     UMA_HISTOGRAM_ENUMERATION("AutocompleteActionPredictor.DatabaseAction",
 424                               DATABASE_ACTION_UPDATE, DATABASE_ACTION_COUNT);
 425   }
 426
 427   if (table_.get()) {
 428     content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE,
 429         base::Bind(&AutocompleteActionPredictorTable::AddAndUpdateRows,
 430                    table_, rows_to_add, rows_to_update));
 431   }
 432 }
 433
 434 void AutocompleteActionPredictor::CreateCaches(
 435     std::vector<AutocompleteActionPredictorTable::Row>* rows) {
 436   CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::UI));
 437   DCHECK(!profile_->IsOffTheRecord());
 438   DCHECK(!initialized_);
 439   DCHECK(db_cache_.empty());
 440   DCHECK(db_id_cache_.empty());
 441
 442   for (std::vector<AutocompleteActionPredictorTable::Row>::const_iterator it =
 443        rows->begin(); it != rows->end(); ++it) {
 444     const DBCacheKey key = { it->user_text, it->url };
 445     const DBCacheValue value = { it->number_of_hits, it->number_of_misses };
 446     db_cache_[key] = value;
 447     db_id_cache_[key] = it->id;
 448   }
 449
 450   // If the history service is ready, delete any old or invalid entries.
 451   HistoryService* history_service = HistoryServiceFactory::GetForProfile(
 452       profile_, ServiceAccessType::EXPLICIT_ACCESS);
 453   if (!TryDeleteOldEntries(history_service)) {
 454     // Wait for the notification that the history service is ready and the URL
 455     // DB is loaded.
 456     if (history_service)
 457       history_service_observer_.Add(history_service);
 458   }
 459 }
 460
 461 bool AutocompleteActionPredictor::TryDeleteOldEntries(HistoryService* service) {
 462   CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::UI));
 463   DCHECK(!profile_->IsOffTheRecord());
 464   DCHECK(!initialized_);
 465
 466   if (!service)
 467     return false;
 468
 469   history::URLDatabase* url_db = service->InMemoryDatabase();
 470   if (!url_db)
 471     return false;
 472
 473   DeleteOldEntries(url_db);
 474   return true;
 475 }
 476
 477 void AutocompleteActionPredictor::DeleteOldEntries(
 478     history::URLDatabase* url_db) {
 479   CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::UI));
 480   DCHECK(!profile_->IsOffTheRecord());
 481   DCHECK(!initialized_);
 482   DCHECK(table_.get());
 483
 484   std::vector<AutocompleteActionPredictorTable::Row::Id> ids_to_delete;
 485   DeleteOldIdsFromCaches(url_db, &ids_to_delete);
 486
 487   content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE,
 488       base::Bind(&AutocompleteActionPredictorTable::DeleteRows, table_,
 489                  ids_to_delete));
 490
 491   FinishInitialization();
 492   if (incognito_predictor_)
 493     incognito_predictor_->CopyFromMainProfile();
 494 }
 495
 496 void AutocompleteActionPredictor::DeleteOldIdsFromCaches(
 497     history::URLDatabase* url_db,
 498     std::vector<AutocompleteActionPredictorTable::Row::Id>* id_list) {
 499   CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::UI));
 500   DCHECK(!profile_->IsOffTheRecord());
 501   DCHECK(!initialized_);
 502   DCHECK(url_db);
 503   DCHECK(id_list);
 504
 505   id_list->clear();
 506   for (DBCacheMap::iterator it = db_cache_.begin(); it != db_cache_.end();) {
 507     history::URLRow url_row;
 508
 509     if ((url_db->GetRowForURL(it->first.url, &url_row) == 0) ||
 510         ((base::Time::Now() - url_row.last_visit()).InDays() >
 511          kMaximumDaysToKeepEntry)) {
 512       const DBIdCacheMap::iterator id_it = db_id_cache_.find(it->first);
 513       DCHECK(id_it != db_id_cache_.end());
 514       id_list->push_back(id_it->second);
 515       db_id_cache_.erase(id_it);
 516       db_cache_.erase(it++);
 517     } else {
 518       ++it;
 519     }
 520   }
 521 }
 522
 523 void AutocompleteActionPredictor::CopyFromMainProfile() {
 524   CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::UI));
 525   DCHECK(profile_->IsOffTheRecord());
 526   DCHECK(!initialized_);
 527   DCHECK(main_profile_predictor_);
 528   DCHECK(main_profile_predictor_->initialized_);
 529
 530   db_cache_ = main_profile_predictor_->db_cache_;
 531   db_id_cache_ = main_profile_predictor_->db_id_cache_;
 532   FinishInitialization();
 533 }
 534
 535 void AutocompleteActionPredictor::FinishInitialization() {
 536   CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::UI));
 537   DCHECK(!initialized_);
 538
 539   // Incognito and normal profiles should listen only to omnibox notifications
 540   // from their own profile, but both should listen to history deletions from
 541   // the main profile, since opening the history page in either case actually
 542   // opens the non-incognito history (and lets users delete from there).
 543   notification_registrar_.Add(this, chrome::NOTIFICATION_OMNIBOX_OPENED_URL,
 544                               content::Source<Profile>(profile_));
 545   initialized_ = true;
 546 }
 547
 548 double AutocompleteActionPredictor::CalculateConfidence(
 549     const base::string16& user_text,
 550     const AutocompleteMatch& match,
 551     bool* is_in_db) const {
 552   const DBCacheKey key = { user_text, match.destination_url };
 553
 554   *is_in_db = false;
 555   if (user_text.length() < kMinimumUserTextLength)
 556     return 0.0;
 557
 558   const DBCacheMap::const_iterator iter = db_cache_.find(key);
 559   if (iter == db_cache_.end())
 560     return 0.0;
 561
 562   *is_in_db = true;
 563   return CalculateConfidenceForDbEntry(iter);
 564 }
 565
 566 double AutocompleteActionPredictor::CalculateConfidenceForDbEntry(
 567     DBCacheMap::const_iterator iter) const {
 568   const DBCacheValue& value = iter->second;
 569   if (value.number_of_hits < kMinimumNumberOfHits)
 570     return 0.0;
 571
 572   const double number_of_hits = static_cast<double>(value.number_of_hits);
 573   return number_of_hits / (number_of_hits + value.number_of_misses);
 574 }
 575
 576 void AutocompleteActionPredictor::Shutdown() {
 577   history_service_observer_.RemoveAll();
 578 }
 579
 580 void AutocompleteActionPredictor::OnURLsDeleted(
 581     HistoryService* history_service,
 582     bool all_history,
 583     bool expired,
 584     const history::URLRows& deleted_rows,
 585     const std::set<GURL>& favicon_urls) {
 586   if (!initialized_)
 587     return;
 588
 589   if (all_history)
 590     DeleteAllRows();
 591   else
 592     DeleteRowsWithURLs(deleted_rows);
 593 }
 594
 595 void AutocompleteActionPredictor::OnHistoryServiceLoaded(
 596     HistoryService* history_service) {
 597   TryDeleteOldEntries(history_service);
 598   history_service_observer_.Remove(history_service);
 599 }
 600
 601 AutocompleteActionPredictor::TransitionalMatch::TransitionalMatch() {
 602 }
 603
 604 AutocompleteActionPredictor::TransitionalMatch::~TransitionalMatch() {
 605 }
 606
 607 }  // namespace predictors