Home | History | Annotate | Download | only in predictors 
      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/autocomplete/autocomplete_match.h"
     19 #include "chrome/browser/autocomplete/autocomplete_result.h"
     20 #include "chrome/browser/chrome_notification_types.h"
     21 #include "chrome/browser/history/history_notifications.h"
     22 #include "chrome/browser/history/history_service.h"
     23 #include "chrome/browser/history/history_service_factory.h"
     24 #include "chrome/browser/history/in_memory_database.h"
     25 #include "chrome/browser/omnibox/omnibox_log.h"
     26 #include "chrome/browser/predictors/autocomplete_action_predictor_factory.h"
     27 #include "chrome/browser/predictors/predictor_database.h"
     28 #include "chrome/browser/predictors/predictor_database_factory.h"
     29 #include "chrome/browser/prerender/prerender_field_trial.h"
     30 #include "chrome/browser/prerender/prerender_handle.h"
     31 #include "chrome/browser/prerender/prerender_manager.h"
     32 #include "chrome/browser/prerender/prerender_manager_factory.h"
     33 #include "chrome/browser/profiles/profile.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 COMPILE_ASSERT(arraysize(kConfidenceCutoff) ==
     47                predictors::AutocompleteActionPredictor::LAST_PREDICT_ACTION,
     48                ConfidenceCutoff_count_mismatch);
     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   if (profile_->IsOffTheRecord()) {
     73     main_profile_predictor_ = AutocompleteActionPredictorFactory::GetForProfile(
     74         profile_->GetOriginalProfile());
     75     DCHECK(main_profile_predictor_);
     76     main_profile_predictor_->incognito_predictor_ = this;
     77     if (main_profile_predictor_->initialized_)
     78       CopyFromMainProfile();
     79   } else {
     80     // Request the in-memory database from the history to force it to load so
     81     // it's available as soon as possible.
     82     HistoryService* history_service = HistoryServiceFactory::GetForProfile(
     83         profile_, Profile::EXPLICIT_ACCESS);
     84     if (history_service)
     85       history_service->InMemoryDatabase();
     86 
     87     table_ =
     88         PredictorDatabaseFactory::GetForProfile(profile_)->autocomplete_table();
     89 
     90     // Observe all main frame loads so we can wait for the first to complete
     91     // before accessing DB and IO threads to build the local cache.
     92     notification_registrar_.Add(this,
     93                                 content::NOTIFICATION_LOAD_COMPLETED_MAIN_FRAME,
     94                                 content::NotificationService::AllSources());
     95   }
     96 }
     97 
     98 AutocompleteActionPredictor::~AutocompleteActionPredictor() {
     99   if (main_profile_predictor_)
    100     main_profile_predictor_->incognito_predictor_ = NULL;
    101   else if (incognito_predictor_)
    102     incognito_predictor_->main_profile_predictor_ = NULL;
    103   if (prerender_handle_.get())
    104     prerender_handle_->OnCancel();
    105 }
    106 
    107 void AutocompleteActionPredictor::RegisterTransitionalMatches(
    108     const base::string16& user_text,
    109     const AutocompleteResult& result) {
    110   if (user_text.length() < kMinimumUserTextLength)
    111     return;
    112   const base::string16 lower_user_text(base::i18n::ToLower(user_text));
    113 
    114   // Merge this in to an existing match if we already saw |user_text|
    115   std::vector<TransitionalMatch>::iterator match_it =
    116       std::find(transitional_matches_.begin(), transitional_matches_.end(),
    117                 lower_user_text);
    118 
    119   if (match_it == transitional_matches_.end()) {
    120     TransitionalMatch transitional_match;
    121     transitional_match.user_text = lower_user_text;
    122     match_it = transitional_matches_.insert(transitional_matches_.end(),
    123                                             transitional_match);
    124   }
    125 
    126   for (AutocompleteResult::const_iterator i(result.begin()); i != result.end();
    127        ++i) {
    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::StartPrerendering(
    140     const GURL& url,
    141     const content::SessionStorageNamespaceMap& session_storage_namespace_map,
    142     const gfx::Size& size) {
    143   // Only cancel the old prerender after starting the new one, so if the URLs
    144   // are the same, the underlying prerender will be reused.
    145   scoped_ptr<prerender::PrerenderHandle> old_prerender_handle(
    146       prerender_handle_.release());
    147   if (prerender::PrerenderManager* prerender_manager =
    148           prerender::PrerenderManagerFactory::GetForProfile(profile_)) {
    149     content::SessionStorageNamespace* session_storage_namespace = NULL;
    150     content::SessionStorageNamespaceMap::const_iterator it =
    151         session_storage_namespace_map.find(std::string());
    152     if (it != session_storage_namespace_map.end())
    153       session_storage_namespace = it->second.get();
    154     prerender_handle_.reset(prerender_manager->AddPrerenderFromOmnibox(
    155         url, session_storage_namespace, size));
    156   }
    157   if (old_prerender_handle)
    158     old_prerender_handle->OnCancel();
    159 }
    160 
    161 // Given a match, return a recommended action.
    162 AutocompleteActionPredictor::Action
    163     AutocompleteActionPredictor::RecommendAction(
    164         const base::string16& user_text,
    165         const AutocompleteMatch& match) const {
    166   bool is_in_db = false;
    167   const double confidence = CalculateConfidence(user_text, match, &is_in_db);
    168   DCHECK(confidence >= 0.0 && confidence <= 1.0);
    169 
    170   UMA_HISTOGRAM_BOOLEAN("AutocompleteActionPredictor.MatchIsInDb", is_in_db);
    171 
    172   if (is_in_db) {
    173     // Multiple enties with the same URL are fine as the confidence may be
    174     // different.
    175     tracked_urls_.push_back(std::make_pair(match.destination_url, confidence));
    176     UMA_HISTOGRAM_COUNTS_100("AutocompleteActionPredictor.Confidence",
    177                              confidence * 100);
    178   }
    179 
    180   // Map the confidence to an action.
    181   Action action = ACTION_NONE;
    182   for (int i = 0; i < LAST_PREDICT_ACTION; ++i) {
    183     if (confidence >= kConfidenceCutoff[i]) {
    184       action = static_cast<Action>(i);
    185       break;
    186     }
    187   }
    188 
    189   // Downgrade prerender to preconnect if this is a search match or if omnibox
    190   // prerendering is disabled. There are cases when Instant will not handle a
    191   // search suggestion and in those cases it would be good to prerender the
    192   // search results, however search engines have not been set up to correctly
    193   // handle being prerendered and until they are we should avoid it.
    194   // http://crbug.com/117495
    195   if (action == ACTION_PRERENDER &&
    196       (AutocompleteMatch::IsSearchType(match.type) ||
    197        !prerender::IsOmniboxEnabled(profile_))) {
    198     action = ACTION_PRECONNECT;
    199   }
    200 
    201   return action;
    202 }
    203 
    204 // Return true if the suggestion type warrants a TCP/IP preconnection.
    205 // i.e., it is now quite likely that the user will select the related domain.
    206 // static
    207 bool AutocompleteActionPredictor::IsPreconnectable(
    208     const AutocompleteMatch& match) {
    209   return AutocompleteMatch::IsSearchType(match.type);
    210 }
    211 
    212 void AutocompleteActionPredictor::Observe(
    213     int type,
    214     const content::NotificationSource& source,
    215     const content::NotificationDetails& details) {
    216   switch (type) {
    217     case content::NOTIFICATION_LOAD_COMPLETED_MAIN_FRAME:
    218       CreateLocalCachesFromDatabase();
    219       notification_registrar_.Remove(
    220           this,
    221           content::NOTIFICATION_LOAD_COMPLETED_MAIN_FRAME,
    222           content::NotificationService::AllSources());
    223       break;
    224 
    225     case chrome::NOTIFICATION_HISTORY_URLS_DELETED: {
    226       DCHECK(initialized_);
    227       const content::Details<const history::URLsDeletedDetails>
    228           urls_deleted_details =
    229               content::Details<const history::URLsDeletedDetails>(details);
    230       if (urls_deleted_details->all_history)
    231         DeleteAllRows();
    232       else
    233         DeleteRowsWithURLs(urls_deleted_details->rows);
    234       break;
    235     }
    236 
    237     // This notification does not catch all instances of the user navigating
    238     // from the Omnibox, but it does catch the cases where the dropdown is open
    239     // and those are the events we're most interested in.
    240     case chrome::NOTIFICATION_OMNIBOX_OPENED_URL: {
    241       DCHECK(initialized_);
    242 
    243       // TODO(dominich): This doesn't need to be synchronous. Investigate
    244       // posting it as a task to be run later.
    245       OnOmniboxOpenedUrl(*content::Details<OmniboxLog>(details).ptr());
    246       break;
    247     }
    248 
    249     case chrome::NOTIFICATION_HISTORY_LOADED: {
    250       TryDeleteOldEntries(content::Details<HistoryService>(details).ptr());
    251 
    252       notification_registrar_.Remove(this,
    253                                      chrome::NOTIFICATION_HISTORY_LOADED,
    254                                      content::Source<Profile>(profile_));
    255       break;
    256     }
    257 
    258     default:
    259       NOTREACHED() << "Unexpected notification observed.";
    260       break;
    261   }
    262 }
    263 
    264 void AutocompleteActionPredictor::CreateLocalCachesFromDatabase() {
    265   // Create local caches using the database as loaded. We will garbage collect
    266   // rows from the caches and the database once the history service is
    267   // available.
    268   std::vector<AutocompleteActionPredictorTable::Row>* rows =
    269       new std::vector<AutocompleteActionPredictorTable::Row>();
    270   content::BrowserThread::PostTaskAndReply(content::BrowserThread::DB,
    271       FROM_HERE,
    272       base::Bind(&AutocompleteActionPredictorTable::GetAllRows, table_, rows),
    273       base::Bind(&AutocompleteActionPredictor::CreateCaches, AsWeakPtr(),
    274                  base::Owned(rows)));
    275 }
    276 
    277 void AutocompleteActionPredictor::DeleteAllRows() {
    278   if (!initialized_)
    279     return;
    280 
    281   db_cache_.clear();
    282   db_id_cache_.clear();
    283 
    284   if (table_.get()) {
    285     content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE,
    286         base::Bind(&AutocompleteActionPredictorTable::DeleteAllRows,
    287                    table_));
    288   }
    289 
    290   UMA_HISTOGRAM_ENUMERATION("AutocompleteActionPredictor.DatabaseAction",
    291                             DATABASE_ACTION_DELETE_ALL, DATABASE_ACTION_COUNT);
    292 }
    293 
    294 void AutocompleteActionPredictor::DeleteRowsWithURLs(
    295     const history::URLRows& rows) {
    296   if (!initialized_)
    297     return;
    298 
    299   std::vector<AutocompleteActionPredictorTable::Row::Id> id_list;
    300 
    301   for (DBCacheMap::iterator it = db_cache_.begin(); it != db_cache_.end();) {
    302     if (std::find_if(rows.begin(), rows.end(),
    303         history::URLRow::URLRowHasURL(it->first.url)) != rows.end()) {
    304       const DBIdCacheMap::iterator id_it = db_id_cache_.find(it->first);
    305       DCHECK(id_it != db_id_cache_.end());
    306       id_list.push_back(id_it->second);
    307       db_id_cache_.erase(id_it);
    308       db_cache_.erase(it++);
    309     } else {
    310       ++it;
    311     }
    312   }
    313 
    314   if (table_.get()) {
    315     content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE,
    316         base::Bind(&AutocompleteActionPredictorTable::DeleteRows, table_,
    317                    id_list));
    318   }
    319 
    320   UMA_HISTOGRAM_ENUMERATION("AutocompleteActionPredictor.DatabaseAction",
    321                             DATABASE_ACTION_DELETE_SOME, DATABASE_ACTION_COUNT);
    322 }
    323 
    324 void AutocompleteActionPredictor::OnOmniboxOpenedUrl(const OmniboxLog& log) {
    325   if (log.text.length() < kMinimumUserTextLength)
    326     return;
    327 
    328   const AutocompleteMatch& match = log.result.match_at(log.selected_index);
    329 
    330   UMA_HISTOGRAM_BOOLEAN(
    331       base::StringPrintf("Prerender.OmniboxNavigationsCouldPrerender%s",
    332                          prerender::PrerenderManager::GetModeString()).c_str(),
    333       prerender::IsOmniboxEnabled(profile_));
    334 
    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 =
    452       HistoryServiceFactory::GetForProfile(profile_, Profile::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     notification_registrar_.Add(this, chrome::NOTIFICATION_HISTORY_LOADED,
    457                                 content::Source<Profile>(profile_));
    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   notification_registrar_.Add(this, chrome::NOTIFICATION_HISTORY_URLS_DELETED,
    546       content::Source<Profile>(profile_->GetOriginalProfile()));
    547   initialized_ = true;
    548 }
    549 
    550 double AutocompleteActionPredictor::CalculateConfidence(
    551     const base::string16& user_text,
    552     const AutocompleteMatch& match,
    553     bool* is_in_db) const {
    554   const DBCacheKey key = { user_text, match.destination_url };
    555 
    556   *is_in_db = false;
    557   if (user_text.length() < kMinimumUserTextLength)
    558     return 0.0;
    559 
    560   const DBCacheMap::const_iterator iter = db_cache_.find(key);
    561   if (iter == db_cache_.end())
    562     return 0.0;
    563 
    564   *is_in_db = true;
    565   return CalculateConfidenceForDbEntry(iter);
    566 }
    567 
    568 double AutocompleteActionPredictor::CalculateConfidenceForDbEntry(
    569     DBCacheMap::const_iterator iter) const {
    570   const DBCacheValue& value = iter->second;
    571   if (value.number_of_hits < kMinimumNumberOfHits)
    572     return 0.0;
    573 
    574   const double number_of_hits = static_cast<double>(value.number_of_hits);
    575   return number_of_hits / (number_of_hits + value.number_of_misses);
    576 }
    577 
    578 AutocompleteActionPredictor::TransitionalMatch::TransitionalMatch() {
    579 }
    580 
    581 AutocompleteActionPredictor::TransitionalMatch::~TransitionalMatch() {
    582 }
    583 
    584 }  // namespace predictors
    585