OLD | NEW |
| (Empty) |
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 #include "chrome/browser/autocomplete/network_action_predictor.h" | |
6 | |
7 #include <math.h> | |
8 | |
9 #include <vector> | |
10 | |
11 #include "base/bind.h" | |
12 #include "base/i18n/case_conversion.h" | |
13 #include "base/metrics/histogram.h" | |
14 #include "base/string_util.h" | |
15 #include "base/stringprintf.h" | |
16 #include "base/utf_string_conversions.h" | |
17 #include "chrome/browser/autocomplete/autocomplete.h" | |
18 #include "chrome/browser/autocomplete/autocomplete_match.h" | |
19 #include "chrome/browser/autocomplete/network_action_predictor_database.h" | |
20 #include "chrome/browser/history/history.h" | |
21 #include "chrome/browser/history/history_notifications.h" | |
22 #include "chrome/browser/history/in_memory_database.h" | |
23 #include "chrome/browser/prerender/prerender_field_trial.h" | |
24 #include "chrome/browser/prerender/prerender_manager.h" | |
25 #include "chrome/browser/prerender/prerender_manager_factory.h" | |
26 #include "chrome/browser/profiles/profile.h" | |
27 #include "chrome/common/chrome_notification_types.h" | |
28 #include "chrome/common/guid.h" | |
29 #include "content/public/browser/browser_thread.h" | |
30 #include "content/public/browser/notification_details.h" | |
31 #include "content/public/browser/notification_service.h" | |
32 #include "content/public/browser/notification_source.h" | |
33 | |
34 namespace { | |
35 | |
36 const float kConfidenceCutoff[] = { | |
37 0.8f, | |
38 0.5f | |
39 }; | |
40 | |
41 const size_t kMinimumUserTextLength = 1; | |
42 const int kMinimumNumberOfHits = 3; | |
43 | |
44 COMPILE_ASSERT(arraysize(kConfidenceCutoff) == | |
45 NetworkActionPredictor::LAST_PREDICT_ACTION, | |
46 ConfidenceCutoff_count_mismatch); | |
47 | |
48 enum DatabaseAction { | |
49 DATABASE_ACTION_ADD, | |
50 DATABASE_ACTION_UPDATE, | |
51 DATABASE_ACTION_DELETE_SOME, | |
52 DATABASE_ACTION_DELETE_ALL, | |
53 DATABASE_ACTION_COUNT | |
54 }; | |
55 | |
56 } | |
57 | |
58 const int NetworkActionPredictor::kMaximumDaysToKeepEntry = 14; | |
59 | |
60 double NetworkActionPredictor::hit_weight_ = 1.0; | |
61 | |
62 NetworkActionPredictor::NetworkActionPredictor(Profile* profile) | |
63 : profile_(profile), | |
64 db_(new NetworkActionPredictorDatabase(profile)), | |
65 initialized_(false) { | |
66 content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE, | |
67 base::Bind(&NetworkActionPredictorDatabase::Initialize, db_)); | |
68 | |
69 // Request the in-memory database from the history to force it to load so it's | |
70 // available as soon as possible. | |
71 HistoryService* history_service = | |
72 profile_->GetHistoryService(Profile::EXPLICIT_ACCESS); | |
73 if (history_service) | |
74 history_service->InMemoryDatabase(); | |
75 | |
76 // Create local caches using the database as loaded. We will garbage collect | |
77 // rows from the caches and the database once the history service is | |
78 // available. | |
79 std::vector<NetworkActionPredictorDatabase::Row>* rows = | |
80 new std::vector<NetworkActionPredictorDatabase::Row>(); | |
81 content::BrowserThread::PostTaskAndReply( | |
82 content::BrowserThread::DB, FROM_HERE, | |
83 base::Bind(&NetworkActionPredictorDatabase::GetAllRows, db_, rows), | |
84 base::Bind(&NetworkActionPredictor::CreateCaches, AsWeakPtr(), | |
85 base::Owned(rows))); | |
86 | |
87 } | |
88 | |
89 NetworkActionPredictor::~NetworkActionPredictor() { | |
90 } | |
91 | |
92 void NetworkActionPredictor::RegisterTransitionalMatches( | |
93 const string16& user_text, | |
94 const AutocompleteResult& result) { | |
95 if (user_text.length() < kMinimumUserTextLength) | |
96 return; | |
97 const string16 lower_user_text(base::i18n::ToLower(user_text)); | |
98 | |
99 // Merge this in to an existing match if we already saw |user_text| | |
100 std::vector<TransitionalMatch>::iterator match_it = | |
101 std::find(transitional_matches_.begin(), transitional_matches_.end(), | |
102 lower_user_text); | |
103 | |
104 if (match_it == transitional_matches_.end()) { | |
105 TransitionalMatch transitional_match; | |
106 transitional_match.user_text = lower_user_text; | |
107 match_it = transitional_matches_.insert(transitional_matches_.end(), | |
108 transitional_match); | |
109 } | |
110 | |
111 for (AutocompleteResult::const_iterator it = result.begin(); | |
112 it != result.end(); ++it) { | |
113 if (std::find(match_it->urls.begin(), match_it->urls.end(), | |
114 it->destination_url) == match_it->urls.end()) { | |
115 match_it->urls.push_back(it->destination_url); | |
116 } | |
117 } | |
118 } | |
119 | |
120 void NetworkActionPredictor::ClearTransitionalMatches() { | |
121 transitional_matches_.clear(); | |
122 } | |
123 | |
124 // Given a match, return a recommended action. | |
125 NetworkActionPredictor::Action NetworkActionPredictor::RecommendAction( | |
126 const string16& user_text, | |
127 const AutocompleteMatch& match) const { | |
128 bool is_in_db = false; | |
129 const double confidence = CalculateConfidence(user_text, match, &is_in_db); | |
130 DCHECK(confidence >= 0.0 && confidence <= 1.0); | |
131 | |
132 UMA_HISTOGRAM_BOOLEAN("NetworkActionPredictor.MatchIsInDb", is_in_db); | |
133 | |
134 if (is_in_db) { | |
135 // Multiple enties with the same URL are fine as the confidence may be | |
136 // different. | |
137 tracked_urls_.push_back(std::make_pair(match.destination_url, confidence)); | |
138 UMA_HISTOGRAM_COUNTS_100("NetworkActionPredictor.Confidence", | |
139 confidence * 100); | |
140 } | |
141 | |
142 // Map the confidence to an action. | |
143 Action action = ACTION_NONE; | |
144 for (int i = 0; i < LAST_PREDICT_ACTION; ++i) { | |
145 if (confidence >= kConfidenceCutoff[i]) { | |
146 action = static_cast<Action>(i); | |
147 break; | |
148 } | |
149 } | |
150 | |
151 // Downgrade prerender to preconnect if this is a search match or if omnibox | |
152 // prerendering is disabled. | |
153 if (action == ACTION_PRERENDER && !prerender::IsOmniboxEnabled(profile_)) | |
154 action = ACTION_PRECONNECT; | |
155 | |
156 return action; | |
157 } | |
158 | |
159 // Return true if the suggestion type warrants a TCP/IP preconnection. | |
160 // i.e., it is now quite likely that the user will select the related domain. | |
161 // static | |
162 bool NetworkActionPredictor::IsPreconnectable(const AutocompleteMatch& match) { | |
163 switch (match.type) { | |
164 // Matches using the user's default search engine. | |
165 case AutocompleteMatch::SEARCH_WHAT_YOU_TYPED: | |
166 case AutocompleteMatch::SEARCH_HISTORY: | |
167 case AutocompleteMatch::SEARCH_SUGGEST: | |
168 // A match that uses a non-default search engine (e.g. for tab-to-search). | |
169 case AutocompleteMatch::SEARCH_OTHER_ENGINE: | |
170 return true; | |
171 | |
172 default: | |
173 return false; | |
174 } | |
175 } | |
176 | |
177 void NetworkActionPredictor::Shutdown() { | |
178 db_->OnPredictorDestroyed(); | |
179 } | |
180 | |
181 void NetworkActionPredictor::Observe( | |
182 int type, | |
183 const content::NotificationSource& source, | |
184 const content::NotificationDetails& details) { | |
185 switch (type) { | |
186 case chrome::NOTIFICATION_HISTORY_URLS_DELETED: { | |
187 DCHECK(initialized_); | |
188 const content::Details<const history::URLsDeletedDetails> | |
189 urls_deleted_details = | |
190 content::Details<const history::URLsDeletedDetails>(details); | |
191 if (urls_deleted_details->all_history) | |
192 DeleteAllRows(); | |
193 else | |
194 DeleteRowsWithURLs(urls_deleted_details->urls); | |
195 break; | |
196 } | |
197 | |
198 // This notification does not catch all instances of the user navigating | |
199 // from the Omnibox, but it does catch the cases where the dropdown is open | |
200 // and those are the events we're most interested in. | |
201 case chrome::NOTIFICATION_OMNIBOX_OPENED_URL: { | |
202 DCHECK(initialized_); | |
203 | |
204 // TODO(dominich): This doesn't need to be synchronous. Investigate | |
205 // posting it as a task to be run later. | |
206 OnOmniboxOpenedUrl(*content::Details<AutocompleteLog>(details).ptr()); | |
207 break; | |
208 } | |
209 | |
210 case chrome::NOTIFICATION_HISTORY_LOADED: { | |
211 DCHECK(!initialized_); | |
212 TryDeleteOldEntries(content::Details<HistoryService>(details).ptr()); | |
213 | |
214 notification_registrar_.Remove(this, | |
215 chrome::NOTIFICATION_HISTORY_LOADED, | |
216 content::Source<Profile>(profile_)); | |
217 break; | |
218 } | |
219 | |
220 default: | |
221 NOTREACHED() << "Unexpected notification observed."; | |
222 break; | |
223 } | |
224 } | |
225 | |
226 void NetworkActionPredictor::OnOmniboxOpenedUrl(const AutocompleteLog& log) { | |
227 if (log.text.length() < kMinimumUserTextLength) | |
228 return; | |
229 | |
230 const AutocompleteMatch& match = log.result.match_at(log.selected_index); | |
231 | |
232 UMA_HISTOGRAM_BOOLEAN( | |
233 StringPrintf("Prerender.OmniboxNavigationsCouldPrerender_%.1f", | |
234 get_hit_weight()).c_str(), | |
235 prerender::IsOmniboxEnabled(profile_)); | |
236 | |
237 const GURL& opened_url = match.destination_url; | |
238 | |
239 // If the Omnibox triggered a prerender but the URL doesn't match the one the | |
240 // user is navigating to, cancel the prerender. | |
241 prerender::PrerenderManager* prerender_manager = | |
242 prerender::PrerenderManagerFactory::GetForProfile(profile_); | |
243 // |prerender_manager| can be NULL in incognito mode or if prerendering is | |
244 // otherwise disabled. | |
245 if (prerender_manager && !prerender_manager->IsPrerendering(opened_url)) | |
246 prerender_manager->CancelOmniboxPrerenders(); | |
247 | |
248 const string16 lower_user_text(base::i18n::ToLower(log.text)); | |
249 | |
250 BeginTransaction(); | |
251 // Traverse transitional matches for those that have a user_text that is a | |
252 // prefix of |lower_user_text|. | |
253 for (std::vector<TransitionalMatch>::const_iterator it = | |
254 transitional_matches_.begin(); it != transitional_matches_.end(); | |
255 ++it) { | |
256 if (!StartsWith(lower_user_text, it->user_text, true)) | |
257 continue; | |
258 | |
259 // Add entries to the database for those matches. | |
260 for (std::vector<GURL>::const_iterator url_it = it->urls.begin(); | |
261 url_it != it->urls.end(); ++url_it) { | |
262 DCHECK(it->user_text.length() >= kMinimumUserTextLength); | |
263 const DBCacheKey key = { it->user_text, *url_it }; | |
264 const bool is_hit = (*url_it == opened_url); | |
265 | |
266 NetworkActionPredictorDatabase::Row row; | |
267 row.user_text = key.user_text; | |
268 row.url = key.url; | |
269 | |
270 DBCacheMap::iterator it = db_cache_.find(key); | |
271 if (it == db_cache_.end()) { | |
272 row.id = guid::GenerateGUID(); | |
273 row.number_of_hits = is_hit ? 1 : 0; | |
274 row.number_of_misses = is_hit ? 0 : 1; | |
275 | |
276 AddRow(key, row); | |
277 } else { | |
278 DCHECK(db_id_cache_.find(key) != db_id_cache_.end()); | |
279 row.id = db_id_cache_.find(key)->second; | |
280 row.number_of_hits = it->second.number_of_hits + (is_hit ? 1 : 0); | |
281 row.number_of_misses = it->second.number_of_misses + (is_hit ? 0 : 1); | |
282 | |
283 UpdateRow(it, row); | |
284 } | |
285 } | |
286 } | |
287 CommitTransaction(); | |
288 | |
289 ClearTransitionalMatches(); | |
290 | |
291 // Check against tracked urls and log accuracy for the confidence we | |
292 // predicted. | |
293 for (std::vector<std::pair<GURL, double> >::const_iterator it = | |
294 tracked_urls_.begin(); it != tracked_urls_.end(); | |
295 ++it) { | |
296 if (opened_url == it->first) { | |
297 UMA_HISTOGRAM_COUNTS_100("NetworkActionPredictor.AccurateCount", | |
298 it->second * 100); | |
299 } | |
300 } | |
301 tracked_urls_.clear(); | |
302 } | |
303 | |
304 void NetworkActionPredictor::DeleteOldIdsFromCaches( | |
305 history::URLDatabase* url_db, | |
306 std::vector<NetworkActionPredictorDatabase::Row::Id>* id_list) { | |
307 CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::UI)); | |
308 DCHECK(url_db); | |
309 DCHECK(id_list); | |
310 id_list->clear(); | |
311 for (DBCacheMap::iterator it = db_cache_.begin(); it != db_cache_.end();) { | |
312 history::URLRow url_row; | |
313 | |
314 if ((url_db->GetRowForURL(it->first.url, &url_row) == 0) || | |
315 ((base::Time::Now() - url_row.last_visit()).InDays() > | |
316 kMaximumDaysToKeepEntry)) { | |
317 const DBIdCacheMap::iterator id_it = db_id_cache_.find(it->first); | |
318 DCHECK(id_it != db_id_cache_.end()); | |
319 id_list->push_back(id_it->second); | |
320 db_id_cache_.erase(id_it); | |
321 db_cache_.erase(it++); | |
322 } else { | |
323 ++it; | |
324 } | |
325 } | |
326 } | |
327 | |
328 void NetworkActionPredictor::DeleteOldEntries(history::URLDatabase* url_db) { | |
329 CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::UI)); | |
330 DCHECK(!initialized_); | |
331 | |
332 std::vector<NetworkActionPredictorDatabase::Row::Id> ids_to_delete; | |
333 DeleteOldIdsFromCaches(url_db, &ids_to_delete); | |
334 | |
335 content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE, | |
336 base::Bind(&NetworkActionPredictorDatabase::DeleteRows, db_, | |
337 ids_to_delete)); | |
338 | |
339 // Register for notifications and set the |initialized_| flag. | |
340 notification_registrar_.Add(this, chrome::NOTIFICATION_OMNIBOX_OPENED_URL, | |
341 content::Source<Profile>(profile_)); | |
342 notification_registrar_.Add(this, chrome::NOTIFICATION_HISTORY_URLS_DELETED, | |
343 content::Source<Profile>(profile_)); | |
344 initialized_ = true; | |
345 } | |
346 | |
347 void NetworkActionPredictor::CreateCaches( | |
348 std::vector<NetworkActionPredictorDatabase::Row>* rows) { | |
349 CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::UI)); | |
350 DCHECK(!initialized_); | |
351 DCHECK(db_cache_.empty()); | |
352 DCHECK(db_id_cache_.empty()); | |
353 | |
354 for (std::vector<NetworkActionPredictorDatabase::Row>::const_iterator it = | |
355 rows->begin(); it != rows->end(); ++it) { | |
356 const DBCacheKey key = { it->user_text, it->url }; | |
357 const DBCacheValue value = { it->number_of_hits, it->number_of_misses }; | |
358 db_cache_[key] = value; | |
359 db_id_cache_[key] = it->id; | |
360 } | |
361 | |
362 // If the history service is ready, delete any old or invalid entries. | |
363 HistoryService* history_service = | |
364 profile_->GetHistoryService(Profile::EXPLICIT_ACCESS); | |
365 if (!TryDeleteOldEntries(history_service)) { | |
366 // Wait for the notification that the history service is ready and the URL | |
367 // DB is loaded. | |
368 notification_registrar_.Add(this, chrome::NOTIFICATION_HISTORY_LOADED, | |
369 content::Source<Profile>(profile_)); | |
370 } | |
371 } | |
372 | |
373 bool NetworkActionPredictor::TryDeleteOldEntries(HistoryService* service) { | |
374 if (!service) | |
375 return false; | |
376 | |
377 history::URLDatabase* url_db = service->InMemoryDatabase(); | |
378 if (!url_db) | |
379 return false; | |
380 | |
381 DeleteOldEntries(url_db); | |
382 return true; | |
383 } | |
384 | |
385 double NetworkActionPredictor::CalculateConfidence( | |
386 const string16& user_text, | |
387 const AutocompleteMatch& match, | |
388 bool* is_in_db) const { | |
389 const DBCacheKey key = { user_text, match.destination_url }; | |
390 | |
391 *is_in_db = false; | |
392 if (user_text.length() < kMinimumUserTextLength) | |
393 return 0.0; | |
394 | |
395 const DBCacheMap::const_iterator iter = db_cache_.find(key); | |
396 if (iter == db_cache_.end()) | |
397 return 0.0; | |
398 | |
399 *is_in_db = true; | |
400 return CalculateConfidenceForDbEntry(iter); | |
401 } | |
402 | |
403 double NetworkActionPredictor::CalculateConfidenceForDbEntry( | |
404 DBCacheMap::const_iterator iter) const { | |
405 const DBCacheValue& value = iter->second; | |
406 if (value.number_of_hits < kMinimumNumberOfHits) | |
407 return 0.0; | |
408 | |
409 const double number_of_hits = value.number_of_hits * hit_weight_; | |
410 return number_of_hits / (number_of_hits + value.number_of_misses); | |
411 } | |
412 | |
413 void NetworkActionPredictor::AddRow( | |
414 const DBCacheKey& key, | |
415 const NetworkActionPredictorDatabase::Row& row) { | |
416 if (!initialized_) | |
417 return; | |
418 | |
419 DBCacheValue value = { row.number_of_hits, row.number_of_misses }; | |
420 db_cache_[key] = value; | |
421 db_id_cache_[key] = row.id; | |
422 content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE, | |
423 base::Bind(&NetworkActionPredictorDatabase::AddRow, db_, row)); | |
424 | |
425 UMA_HISTOGRAM_ENUMERATION("NetworkActionPredictor.DatabaseAction", | |
426 DATABASE_ACTION_ADD, DATABASE_ACTION_COUNT); | |
427 } | |
428 | |
429 void NetworkActionPredictor::UpdateRow( | |
430 DBCacheMap::iterator it, | |
431 const NetworkActionPredictorDatabase::Row& row) { | |
432 if (!initialized_) | |
433 return; | |
434 | |
435 DCHECK(it != db_cache_.end()); | |
436 it->second.number_of_hits = row.number_of_hits; | |
437 it->second.number_of_misses = row.number_of_misses; | |
438 content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE, | |
439 base::Bind(&NetworkActionPredictorDatabase::UpdateRow, db_, row)); | |
440 UMA_HISTOGRAM_ENUMERATION("NetworkActionPredictor.DatabaseAction", | |
441 DATABASE_ACTION_UPDATE, DATABASE_ACTION_COUNT); | |
442 } | |
443 | |
444 void NetworkActionPredictor::DeleteAllRows() { | |
445 if (!initialized_) | |
446 return; | |
447 | |
448 db_cache_.clear(); | |
449 db_id_cache_.clear(); | |
450 content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE, | |
451 base::Bind(&NetworkActionPredictorDatabase::DeleteAllRows, db_)); | |
452 UMA_HISTOGRAM_ENUMERATION("NetworkActionPredictor.DatabaseAction", | |
453 DATABASE_ACTION_DELETE_ALL, DATABASE_ACTION_COUNT); | |
454 } | |
455 | |
456 void NetworkActionPredictor::DeleteRowsWithURLs(const std::set<GURL>& urls) { | |
457 if (!initialized_) | |
458 return; | |
459 | |
460 std::vector<NetworkActionPredictorDatabase::Row::Id> id_list; | |
461 | |
462 for (DBCacheMap::iterator it = db_cache_.begin(); it != db_cache_.end();) { | |
463 if (urls.find(it->first.url) != urls.end()) { | |
464 const DBIdCacheMap::iterator id_it = db_id_cache_.find(it->first); | |
465 DCHECK(id_it != db_id_cache_.end()); | |
466 id_list.push_back(id_it->second); | |
467 db_id_cache_.erase(id_it); | |
468 db_cache_.erase(it++); | |
469 } else { | |
470 ++it; | |
471 } | |
472 } | |
473 | |
474 content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE, | |
475 base::Bind(&NetworkActionPredictorDatabase::DeleteRows, db_, id_list)); | |
476 UMA_HISTOGRAM_ENUMERATION("NetworkActionPredictor.DatabaseAction", | |
477 DATABASE_ACTION_DELETE_SOME, DATABASE_ACTION_COUNT); | |
478 } | |
479 | |
480 void NetworkActionPredictor::BeginTransaction() { | |
481 if (!initialized_) | |
482 return; | |
483 | |
484 content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE, | |
485 base::Bind(&NetworkActionPredictorDatabase::BeginTransaction, db_)); | |
486 } | |
487 | |
488 void NetworkActionPredictor::CommitTransaction() { | |
489 if (!initialized_) | |
490 return; | |
491 | |
492 content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE, | |
493 base::Bind(&NetworkActionPredictorDatabase::CommitTransaction, db_)); | |
494 } | |
495 | |
496 NetworkActionPredictor::TransitionalMatch::TransitionalMatch() { | |
497 } | |
498 | |
499 NetworkActionPredictor::TransitionalMatch::~TransitionalMatch() { | |
500 } | |
OLD | NEW |