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