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