history_backend.cc revision a1401311d1ab56c4ed0a474bd38c108f75cb0cd9
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/history/history_backend.h"
6
7#include <algorithm>
8#include <functional>
9#include <list>
10#include <map>
11#include <set>
12#include <vector>
13
14#include "base/basictypes.h"
15#include "base/bind.h"
16#include "base/compiler_specific.h"
17#include "base/files/file_enumerator.h"
18#include "base/memory/scoped_ptr.h"
19#include "base/memory/scoped_vector.h"
20#include "base/message_loop/message_loop.h"
21#include "base/metrics/histogram.h"
22#include "base/rand_util.h"
23#include "base/strings/string_util.h"
24#include "base/strings/utf_string_conversions.h"
25#include "base/time/time.h"
26#include "chrome/browser/autocomplete/history_url_provider.h"
27#include "chrome/browser/bookmarks/bookmark_service.h"
28#include "chrome/browser/chrome_notification_types.h"
29#include "chrome/browser/favicon/favicon_changed_details.h"
30#include "chrome/browser/history/download_row.h"
31#include "chrome/browser/history/history_db_task.h"
32#include "chrome/browser/history/history_notifications.h"
33#include "chrome/browser/history/in_memory_history_backend.h"
34#include "chrome/browser/history/page_usage_data.h"
35#include "chrome/browser/history/select_favicon_frames.h"
36#include "chrome/browser/history/top_sites.h"
37#include "chrome/browser/history/typed_url_syncable_service.h"
38#include "chrome/browser/history/visit_filter.h"
39#include "chrome/common/chrome_constants.h"
40#include "chrome/common/importer/imported_favicon_usage.h"
41#include "chrome/common/url_constants.h"
42#include "grit/chromium_strings.h"
43#include "grit/generated_resources.h"
44#include "net/base/registry_controlled_domains/registry_controlled_domain.h"
45#include "sql/error_delegate_util.h"
46#include "url/gurl.h"
47
48#if defined(OS_ANDROID)
49#include "chrome/browser/history/android/android_provider_backend.h"
50#endif
51
52using base::Time;
53using base::TimeDelta;
54using base::TimeTicks;
55
56/* The HistoryBackend consists of a number of components:
57
58    HistoryDatabase (stores past 3 months of history)
59      URLDatabase (stores a list of URLs)
60      DownloadDatabase (stores a list of downloads)
61      VisitDatabase (stores a list of visits for the URLs)
62      VisitSegmentDatabase (stores groups of URLs for the most visited view).
63
64    ArchivedDatabase (stores history older than 3 months)
65      URLDatabase (stores a list of URLs)
66      DownloadDatabase (stores a list of downloads)
67      VisitDatabase (stores a list of visits for the URLs)
68
69      (this does not store visit segments as they expire after 3 mos.)
70
71    ExpireHistoryBackend (manages moving things from HistoryDatabase to
72                          the ArchivedDatabase and deleting)
73*/
74
75namespace history {
76
77// How long we keep segment data for in days. Currently 3 months.
78// This value needs to be greater or equal to
79// MostVisitedModel::kMostVisitedScope but we don't want to introduce a direct
80// dependency between MostVisitedModel and the history backend.
81const int kSegmentDataRetention = 90;
82
83// How long we'll wait to do a commit, so that things are batched together.
84const int kCommitIntervalSeconds = 10;
85
86// The amount of time before we re-fetch the favicon.
87const int kFaviconRefetchDays = 7;
88
89// The maximum number of items we'll allow in the redirect list before
90// deleting some.
91const int kMaxRedirectCount = 32;
92
93// The number of days old a history entry can be before it is considered "old"
94// and is archived.
95const int kArchiveDaysThreshold = 90;
96
97#if defined(OS_ANDROID)
98// The maximum number of top sites to track when recording top page visit stats.
99const size_t kPageVisitStatsMaxTopSites = 50;
100#endif
101
102// Converts from PageUsageData to MostVisitedURL. |redirects| is a
103// list of redirects for this URL. Empty list means no redirects.
104MostVisitedURL MakeMostVisitedURL(const PageUsageData& page_data,
105                                  const RedirectList& redirects) {
106  MostVisitedURL mv;
107  mv.url = page_data.GetURL();
108  mv.title = page_data.GetTitle();
109  if (redirects.empty()) {
110    // Redirects must contain at least the target url.
111    mv.redirects.push_back(mv.url);
112  } else {
113    mv.redirects = redirects;
114    if (mv.redirects[mv.redirects.size() - 1] != mv.url) {
115      // The last url must be the target url.
116      mv.redirects.push_back(mv.url);
117    }
118  }
119  return mv;
120}
121
122// This task is run on a timer so that commits happen at regular intervals
123// so they are batched together. The important thing about this class is that
124// it supports canceling of the task so the reference to the backend will be
125// freed. The problem is that when history is shutting down, there is likely
126// to be one of these commits still pending and holding a reference.
127//
128// The backend can call Cancel to have this task release the reference. The
129// task will still run (if we ever get to processing the event before
130// shutdown), but it will not do anything.
131//
132// Note that this is a refcounted object and is not a task in itself. It should
133// be assigned to a RunnableMethod.
134//
135// TODO(brettw): bug 1165182: This should be replaced with a
136// base::WeakPtrFactory which will handle everything automatically (like we do
137// in ExpireHistoryBackend).
138class CommitLaterTask : public base::RefCounted<CommitLaterTask> {
139 public:
140  explicit CommitLaterTask(HistoryBackend* history_backend)
141      : history_backend_(history_backend) {
142  }
143
144  // The backend will call this function if it is being destroyed so that we
145  // release our reference.
146  void Cancel() {
147    history_backend_ = NULL;
148  }
149
150  void RunCommit() {
151    if (history_backend_.get())
152      history_backend_->Commit();
153  }
154
155 private:
156  friend class base::RefCounted<CommitLaterTask>;
157
158  ~CommitLaterTask() {}
159
160  scoped_refptr<HistoryBackend> history_backend_;
161};
162
163// HistoryBackend --------------------------------------------------------------
164
165HistoryBackend::HistoryBackend(const base::FilePath& history_dir,
166                               Delegate* delegate,
167                               BookmarkService* bookmark_service)
168    : delegate_(delegate),
169      history_dir_(history_dir),
170      scheduled_kill_db_(false),
171      expirer_(this, bookmark_service),
172      recent_redirects_(kMaxRedirectCount),
173      backend_destroy_message_loop_(NULL),
174      segment_queried_(false),
175      bookmark_service_(bookmark_service) {
176}
177
178HistoryBackend::~HistoryBackend() {
179  DCHECK(!scheduled_commit_.get()) << "Deleting without cleanup";
180  ReleaseDBTasks();
181
182#if defined(OS_ANDROID)
183  // Release AndroidProviderBackend before other objects.
184  android_provider_backend_.reset();
185#endif
186
187  // First close the databases before optionally running the "destroy" task.
188  CloseAllDatabases();
189
190  if (!backend_destroy_task_.is_null()) {
191    // Notify an interested party (typically a unit test) that we're done.
192    DCHECK(backend_destroy_message_loop_);
193    backend_destroy_message_loop_->PostTask(FROM_HERE, backend_destroy_task_);
194  }
195
196#if defined(OS_ANDROID)
197  sql::Connection::Delete(GetAndroidCacheFileName());
198#endif
199}
200
201void HistoryBackend::Init(const std::string& languages, bool force_fail) {
202  if (!force_fail)
203    InitImpl(languages);
204  delegate_->DBLoaded();
205  typed_url_syncable_service_.reset(new TypedUrlSyncableService(this));
206  memory_pressure_listener_.reset(new base::MemoryPressureListener(
207      base::Bind(&HistoryBackend::OnMemoryPressure, base::Unretained(this))));
208#if defined(OS_ANDROID)
209  PopulateMostVisitedURLMap();
210#endif
211}
212
213void HistoryBackend::SetOnBackendDestroyTask(base::MessageLoop* message_loop,
214                                             const base::Closure& task) {
215  if (!backend_destroy_task_.is_null())
216    DLOG(WARNING) << "Setting more than one destroy task, overriding";
217  backend_destroy_message_loop_ = message_loop;
218  backend_destroy_task_ = task;
219}
220
221void HistoryBackend::Closing() {
222  // Any scheduled commit will have a reference to us, we must make it
223  // release that reference before we can be destroyed.
224  CancelScheduledCommit();
225
226  // Release our reference to the delegate, this reference will be keeping the
227  // history service alive.
228  delegate_.reset();
229}
230
231void HistoryBackend::NotifyRenderProcessHostDestruction(const void* host) {
232  tracker_.NotifyRenderProcessHostDestruction(host);
233}
234
235base::FilePath HistoryBackend::GetThumbnailFileName() const {
236  return history_dir_.Append(chrome::kThumbnailsFilename);
237}
238
239base::FilePath HistoryBackend::GetFaviconsFileName() const {
240  return history_dir_.Append(chrome::kFaviconsFilename);
241}
242
243base::FilePath HistoryBackend::GetArchivedFileName() const {
244  return history_dir_.Append(chrome::kArchivedHistoryFilename);
245}
246
247#if defined(OS_ANDROID)
248base::FilePath HistoryBackend::GetAndroidCacheFileName() const {
249  return history_dir_.Append(chrome::kAndroidCacheFilename);
250}
251#endif
252
253SegmentID HistoryBackend::GetLastSegmentID(VisitID from_visit) {
254  // Set is used to detect referrer loops.  Should not happen, but can
255  // if the database is corrupt.
256  std::set<VisitID> visit_set;
257  VisitID visit_id = from_visit;
258  while (visit_id) {
259    VisitRow row;
260    if (!db_->GetRowForVisit(visit_id, &row))
261      return 0;
262    if (row.segment_id)
263      return row.segment_id;  // Found a visit in this change with a segment.
264
265    // Check the referrer of this visit, if any.
266    visit_id = row.referring_visit;
267
268    if (visit_set.find(visit_id) != visit_set.end()) {
269      NOTREACHED() << "Loop in referer chain, giving up";
270      break;
271    }
272    visit_set.insert(visit_id);
273  }
274  return 0;
275}
276
277SegmentID HistoryBackend::UpdateSegments(
278    const GURL& url,
279    VisitID from_visit,
280    VisitID visit_id,
281    content::PageTransition transition_type,
282    const Time ts) {
283  if (!db_)
284    return 0;
285
286  // We only consider main frames.
287  if (!content::PageTransitionIsMainFrame(transition_type))
288    return 0;
289
290  SegmentID segment_id = 0;
291  content::PageTransition t =
292      content::PageTransitionStripQualifier(transition_type);
293
294  // Are we at the beginning of a new segment?
295  // Note that navigating to an existing entry (with back/forward) reuses the
296  // same transition type.  We are not adding it as a new segment in that case
297  // because if this was the target of a redirect, we might end up with
298  // 2 entries for the same final URL. Ex: User types google.net, gets
299  // redirected to google.com. A segment is created for google.net. On
300  // google.com users navigates through a link, then press back. That last
301  // navigation is for the entry google.com transition typed. We end up adding
302  // a segment for that one as well. So we end up with google.net and google.com
303  // in the segment table, showing as 2 entries in the NTP.
304  // Note also that we should still be updating the visit count for that segment
305  // which we are not doing now. It should be addressed when
306  // http://crbug.com/96860 is fixed.
307  if ((t == content::PAGE_TRANSITION_TYPED ||
308       t == content::PAGE_TRANSITION_AUTO_BOOKMARK) &&
309      (transition_type & content::PAGE_TRANSITION_FORWARD_BACK) == 0) {
310    // If so, create or get the segment.
311    std::string segment_name = db_->ComputeSegmentName(url);
312    URLID url_id = db_->GetRowForURL(url, NULL);
313    if (!url_id)
314      return 0;
315
316    if (!(segment_id = db_->GetSegmentNamed(segment_name))) {
317      if (!(segment_id = db_->CreateSegment(url_id, segment_name))) {
318        NOTREACHED();
319        return 0;
320      }
321    } else {
322      // Note: if we update an existing segment, we update the url used to
323      // represent that segment in order to minimize stale most visited
324      // images.
325      db_->UpdateSegmentRepresentationURL(segment_id, url_id);
326    }
327  } else {
328    // Note: it is possible there is no segment ID set for this visit chain.
329    // This can happen if the initial navigation wasn't AUTO_BOOKMARK or
330    // TYPED. (For example GENERATED). In this case this visit doesn't count
331    // toward any segment.
332    if (!(segment_id = GetLastSegmentID(from_visit)))
333      return 0;
334  }
335
336  // Set the segment in the visit.
337  if (!db_->SetSegmentID(visit_id, segment_id)) {
338    NOTREACHED();
339    return 0;
340  }
341
342  // Finally, increase the counter for that segment / day.
343  if (!db_->IncreaseSegmentVisitCount(segment_id, ts, 1)) {
344    NOTREACHED();
345    return 0;
346  }
347  return segment_id;
348}
349
350void HistoryBackend::UpdateWithPageEndTime(const void* host,
351                                           int32 page_id,
352                                           const GURL& url,
353                                           Time end_ts) {
354  // Will be filled with the URL ID and the visit ID of the last addition.
355  VisitID visit_id = tracker_.GetLastVisit(host, page_id, url);
356  UpdateVisitDuration(visit_id, end_ts);
357}
358
359void HistoryBackend::UpdateVisitDuration(VisitID visit_id, const Time end_ts) {
360  if (!db_)
361    return;
362
363  // Get the starting visit_time for visit_id.
364  VisitRow visit_row;
365  if (db_->GetRowForVisit(visit_id, &visit_row)) {
366    // We should never have a negative duration time even when time is skewed.
367    visit_row.visit_duration = end_ts > visit_row.visit_time ?
368        end_ts - visit_row.visit_time : TimeDelta::FromMicroseconds(0);
369    db_->UpdateVisitRow(visit_row);
370  }
371}
372
373void HistoryBackend::AddPage(const HistoryAddPageArgs& request) {
374  if (!db_)
375    return;
376
377  // Will be filled with the URL ID and the visit ID of the last addition.
378  std::pair<URLID, VisitID> last_ids(0, tracker_.GetLastVisit(
379      request.id_scope, request.page_id, request.referrer));
380
381  VisitID from_visit_id = last_ids.second;
382
383  // If a redirect chain is given, we expect the last item in that chain to be
384  // the final URL.
385  DCHECK(request.redirects.empty() ||
386         request.redirects.back() == request.url);
387
388  // If the user is adding older history, we need to make sure our times
389  // are correct.
390  if (request.time < first_recorded_time_)
391    first_recorded_time_ = request.time;
392
393  content::PageTransition request_transition = request.transition;
394  content::PageTransition stripped_transition =
395    content::PageTransitionStripQualifier(request_transition);
396  bool is_keyword_generated =
397      (stripped_transition == content::PAGE_TRANSITION_KEYWORD_GENERATED);
398
399  // If the user is navigating to a not-previously-typed intranet hostname,
400  // change the transition to TYPED so that the omnibox will learn that this is
401  // a known host.
402  bool has_redirects = request.redirects.size() > 1;
403  if (content::PageTransitionIsMainFrame(request_transition) &&
404      (stripped_transition != content::PAGE_TRANSITION_TYPED) &&
405      !is_keyword_generated) {
406    const GURL& origin_url(has_redirects ?
407        request.redirects[0] : request.url);
408    if (origin_url.SchemeIs(content::kHttpScheme) ||
409        origin_url.SchemeIs(content::kHttpsScheme) ||
410        origin_url.SchemeIs(content::kFtpScheme)) {
411      std::string host(origin_url.host());
412      size_t registry_length =
413          net::registry_controlled_domains::GetRegistryLength(
414              host,
415              net::registry_controlled_domains::EXCLUDE_UNKNOWN_REGISTRIES,
416              net::registry_controlled_domains::EXCLUDE_PRIVATE_REGISTRIES);
417      if (registry_length == 0 && !db_->IsTypedHost(host)) {
418        stripped_transition = content::PAGE_TRANSITION_TYPED;
419        request_transition =
420            content::PageTransitionFromInt(
421                stripped_transition |
422                content::PageTransitionGetQualifier(request_transition));
423      }
424    }
425  }
426
427  if (!has_redirects) {
428    // The single entry is both a chain start and end.
429    content::PageTransition t = content::PageTransitionFromInt(
430        request_transition |
431        content::PAGE_TRANSITION_CHAIN_START |
432        content::PAGE_TRANSITION_CHAIN_END);
433
434    // No redirect case (one element means just the page itself).
435    last_ids = AddPageVisit(request.url, request.time,
436                            last_ids.second, t, request.visit_source);
437
438    // Update the segment for this visit. KEYWORD_GENERATED visits should not
439    // result in changing most visited, so we don't update segments (most
440    // visited db).
441    if (!is_keyword_generated) {
442      UpdateSegments(request.url, from_visit_id, last_ids.second, t,
443                     request.time);
444
445      // Update the referrer's duration.
446      UpdateVisitDuration(from_visit_id, request.time);
447    }
448  } else {
449    // Redirect case. Add the redirect chain.
450
451    content::PageTransition redirect_info =
452        content::PAGE_TRANSITION_CHAIN_START;
453
454    RedirectList redirects = request.redirects;
455    if (redirects[0].SchemeIs(content::kAboutScheme)) {
456      // When the redirect source + referrer is "about" we skip it. This
457      // happens when a page opens a new frame/window to about:blank and then
458      // script sets the URL to somewhere else (used to hide the referrer). It
459      // would be nice to keep all these redirects properly but we don't ever
460      // see the initial about:blank load, so we don't know where the
461      // subsequent client redirect came from.
462      //
463      // In this case, we just don't bother hooking up the source of the
464      // redirects, so we remove it.
465      redirects.erase(redirects.begin());
466    } else if (request_transition & content::PAGE_TRANSITION_CLIENT_REDIRECT) {
467      redirect_info = content::PAGE_TRANSITION_CLIENT_REDIRECT;
468      // The first entry in the redirect chain initiated a client redirect.
469      // We don't add this to the database since the referrer is already
470      // there, so we skip over it but change the transition type of the first
471      // transition to client redirect.
472      //
473      // The referrer is invalid when restoring a session that features an
474      // https tab that redirects to a different host or to http. In this
475      // case we don't need to reconnect the new redirect with the existing
476      // chain.
477      if (request.referrer.is_valid()) {
478        DCHECK(request.referrer == redirects[0]);
479        redirects.erase(redirects.begin());
480
481        // If the navigation entry for this visit has replaced that for the
482        // first visit, remove the CHAIN_END marker from the first visit. This
483        // can be called a lot, for example, the page cycler, and most of the
484        // time we won't have changed anything.
485        VisitRow visit_row;
486        if (request.did_replace_entry &&
487            db_->GetRowForVisit(last_ids.second, &visit_row) &&
488            visit_row.transition & content::PAGE_TRANSITION_CHAIN_END) {
489          visit_row.transition = content::PageTransitionFromInt(
490              visit_row.transition & ~content::PAGE_TRANSITION_CHAIN_END);
491          db_->UpdateVisitRow(visit_row);
492        }
493      }
494    }
495
496    for (size_t redirect_index = 0; redirect_index < redirects.size();
497         redirect_index++) {
498      content::PageTransition t =
499          content::PageTransitionFromInt(stripped_transition | redirect_info);
500
501      // If this is the last transition, add a CHAIN_END marker
502      if (redirect_index == (redirects.size() - 1)) {
503        t = content::PageTransitionFromInt(
504            t | content::PAGE_TRANSITION_CHAIN_END);
505      }
506
507      // Record all redirect visits with the same timestamp. We don't display
508      // them anyway, and if we ever decide to, we can reconstruct their order
509      // from the redirect chain.
510      last_ids = AddPageVisit(redirects[redirect_index],
511                              request.time, last_ids.second,
512                              t, request.visit_source);
513      if (t & content::PAGE_TRANSITION_CHAIN_START) {
514        // Update the segment for this visit.
515        UpdateSegments(redirects[redirect_index],
516                       from_visit_id, last_ids.second, t, request.time);
517
518        // Update the visit_details for this visit.
519        UpdateVisitDuration(from_visit_id, request.time);
520      }
521
522      // Subsequent transitions in the redirect list must all be server
523      // redirects.
524      redirect_info = content::PAGE_TRANSITION_SERVER_REDIRECT;
525    }
526
527    // Last, save this redirect chain for later so we can set titles & favicons
528    // on the redirected pages properly.
529    recent_redirects_.Put(request.url, redirects);
530  }
531
532  // TODO(brettw) bug 1140015: Add an "add page" notification so the history
533  // views can keep in sync.
534
535  // Add the last visit to the tracker so we can get outgoing transitions.
536  // TODO(evanm): Due to http://b/1194536 we lose the referrers of a subframe
537  // navigation anyway, so last_visit_id is always zero for them.  But adding
538  // them here confuses main frame history, so we skip them for now.
539  if (stripped_transition != content::PAGE_TRANSITION_AUTO_SUBFRAME &&
540      stripped_transition != content::PAGE_TRANSITION_MANUAL_SUBFRAME &&
541      !is_keyword_generated) {
542    tracker_.AddVisit(request.id_scope, request.page_id, request.url,
543                      last_ids.second);
544  }
545
546  ScheduleCommit();
547}
548
549void HistoryBackend::InitImpl(const std::string& languages) {
550  DCHECK(!db_) << "Initializing HistoryBackend twice";
551  // In the rare case where the db fails to initialize a dialog may get shown
552  // the blocks the caller, yet allows other messages through. For this reason
553  // we only set db_ to the created database if creation is successful. That
554  // way other methods won't do anything as db_ is still NULL.
555
556  TimeTicks beginning_time = TimeTicks::Now();
557
558  // Compute the file names.
559  base::FilePath history_name = history_dir_.Append(chrome::kHistoryFilename);
560  base::FilePath thumbnail_name = GetFaviconsFileName();
561  base::FilePath archived_name = GetArchivedFileName();
562
563  // Delete the old index database files which are no longer used.
564  DeleteFTSIndexDatabases();
565
566  // History database.
567  db_.reset(new HistoryDatabase());
568
569  // Unretained to avoid a ref loop with db_.
570  db_->set_error_callback(
571      base::Bind(&HistoryBackend::DatabaseErrorCallback,
572                 base::Unretained(this)));
573
574  sql::InitStatus status = db_->Init(history_name);
575  switch (status) {
576    case sql::INIT_OK:
577      break;
578    case sql::INIT_FAILURE: {
579      // A NULL db_ will cause all calls on this object to notice this error
580      // and to not continue. If the error callback scheduled killing the
581      // database, the task it posted has not executed yet. Try killing the
582      // database now before we close it.
583      bool kill_db = scheduled_kill_db_;
584      if (kill_db)
585        KillHistoryDatabase();
586      UMA_HISTOGRAM_BOOLEAN("History.AttemptedToFixProfileError", kill_db);
587      delegate_->NotifyProfileError(status);
588      db_.reset();
589      return;
590    }
591    default:
592      NOTREACHED();
593  }
594
595  // Fill the in-memory database and send it back to the history service on the
596  // main thread.
597  {
598    scoped_ptr<InMemoryHistoryBackend> mem_backend(new InMemoryHistoryBackend);
599    if (mem_backend->Init(history_name, db_.get()))
600      delegate_->SetInMemoryBackend(mem_backend.Pass());
601  }
602  db_->BeginExclusiveMode();  // Must be after the mem backend read the data.
603
604  // Thumbnail database.
605  // TODO(shess): "thumbnail database" these days only stores
606  // favicons.  Thumbnails are stored in "top sites".  Consider
607  // renaming "thumbnail" references to "favicons" or something of the
608  // sort.
609  thumbnail_db_.reset(new ThumbnailDatabase());
610  if (thumbnail_db_->Init(thumbnail_name) != sql::INIT_OK) {
611    // Unlike the main database, we don't error out when the database is too
612    // new because this error is much less severe. Generally, this shouldn't
613    // happen since the thumbnail and main database versions should be in sync.
614    // We'll just continue without thumbnails & favicons in this case or any
615    // other error.
616    LOG(WARNING) << "Could not initialize the thumbnail database.";
617    thumbnail_db_.reset();
618  }
619
620  // Archived database.
621  if (db_->needs_version_17_migration()) {
622    // See needs_version_17_migration() decl for more. In this case, we want
623    // to delete the archived database and need to do so before we try to
624    // open the file. We can ignore any error (maybe the file doesn't exist).
625    sql::Connection::Delete(archived_name);
626  }
627  archived_db_.reset(new ArchivedDatabase());
628  if (!archived_db_->Init(archived_name)) {
629    LOG(WARNING) << "Could not initialize the archived database.";
630    archived_db_.reset();
631  }
632
633  // Generate the history and thumbnail database metrics only after performing
634  // any migration work.
635  if (base::RandInt(1, 100) == 50) {
636    // Only do this computation sometimes since it can be expensive.
637    db_->ComputeDatabaseMetrics(history_name);
638    if (thumbnail_db_)
639      thumbnail_db_->ComputeDatabaseMetrics();
640  }
641
642  // Tell the expiration module about all the nice databases we made. This must
643  // happen before db_->Init() is called since the callback ForceArchiveHistory
644  // may need to expire stuff.
645  //
646  // *sigh*, this can all be cleaned up when that migration code is removed.
647  // The main DB initialization should intuitively be first (not that it
648  // actually matters) and the expirer should be set last.
649  expirer_.SetDatabases(db_.get(), archived_db_.get(), thumbnail_db_.get());
650
651  // Open the long-running transaction.
652  db_->BeginTransaction();
653  if (thumbnail_db_)
654    thumbnail_db_->BeginTransaction();
655  if (archived_db_)
656    archived_db_->BeginTransaction();
657
658  // Get the first item in our database.
659  db_->GetStartDate(&first_recorded_time_);
660
661  // Start expiring old stuff.
662  expirer_.StartArchivingOldStuff(TimeDelta::FromDays(kArchiveDaysThreshold));
663
664#if defined(OS_ANDROID)
665  if (thumbnail_db_) {
666    android_provider_backend_.reset(new AndroidProviderBackend(
667        GetAndroidCacheFileName(), db_.get(), thumbnail_db_.get(),
668        bookmark_service_, delegate_.get()));
669  }
670#endif
671
672  HISTOGRAM_TIMES("History.InitTime",
673                  TimeTicks::Now() - beginning_time);
674}
675
676void HistoryBackend::OnMemoryPressure(
677    base::MemoryPressureListener::MemoryPressureLevel memory_pressure_level) {
678  bool trim_aggressively = memory_pressure_level ==
679      base::MemoryPressureListener::MEMORY_PRESSURE_CRITICAL;
680  if (db_)
681    db_->TrimMemory(trim_aggressively);
682  if (thumbnail_db_)
683    thumbnail_db_->TrimMemory(trim_aggressively);
684  if (archived_db_)
685    archived_db_->TrimMemory(trim_aggressively);
686}
687
688void HistoryBackend::CloseAllDatabases() {
689  if (db_) {
690    // Commit the long-running transaction.
691    db_->CommitTransaction();
692    db_.reset();
693    // Forget the first recorded time since the database is closed.
694    first_recorded_time_ = base::Time();
695  }
696  if (thumbnail_db_) {
697    thumbnail_db_->CommitTransaction();
698    thumbnail_db_.reset();
699  }
700  if (archived_db_) {
701    archived_db_->CommitTransaction();
702    archived_db_.reset();
703  }
704}
705
706std::pair<URLID, VisitID> HistoryBackend::AddPageVisit(
707    const GURL& url,
708    Time time,
709    VisitID referring_visit,
710    content::PageTransition transition,
711    VisitSource visit_source) {
712  // Top-level frame navigations are visible, everything else is hidden
713  bool new_hidden = !content::PageTransitionIsMainFrame(transition);
714
715  // NOTE: This code must stay in sync with
716  // ExpireHistoryBackend::ExpireURLsForVisits().
717  // TODO(pkasting): http://b/1148304 We shouldn't be marking so many URLs as
718  // typed, which would eliminate the need for this code.
719  int typed_increment = 0;
720  content::PageTransition transition_type =
721      content::PageTransitionStripQualifier(transition);
722  if ((transition_type == content::PAGE_TRANSITION_TYPED &&
723      !content::PageTransitionIsRedirect(transition)) ||
724      transition_type == content::PAGE_TRANSITION_KEYWORD_GENERATED)
725    typed_increment = 1;
726
727#if defined(OS_ANDROID)
728  // Only count the page visit if it came from user browsing and only count it
729  // once when cycling through a redirect chain.
730  if (visit_source == SOURCE_BROWSED &&
731      (transition & content::PAGE_TRANSITION_CHAIN_END) != 0) {
732    RecordTopPageVisitStats(url);
733  }
734#endif
735
736  // See if this URL is already in the DB.
737  URLRow url_info(url);
738  URLID url_id = db_->GetRowForURL(url, &url_info);
739  if (url_id) {
740    // Update of an existing row.
741    if (content::PageTransitionStripQualifier(transition) !=
742        content::PAGE_TRANSITION_RELOAD)
743      url_info.set_visit_count(url_info.visit_count() + 1);
744    if (typed_increment)
745      url_info.set_typed_count(url_info.typed_count() + typed_increment);
746    if (url_info.last_visit() < time)
747      url_info.set_last_visit(time);
748
749    // Only allow un-hiding of pages, never hiding.
750    if (!new_hidden)
751      url_info.set_hidden(false);
752
753    db_->UpdateURLRow(url_id, url_info);
754  } else {
755    // Addition of a new row.
756    url_info.set_visit_count(1);
757    url_info.set_typed_count(typed_increment);
758    url_info.set_last_visit(time);
759    url_info.set_hidden(new_hidden);
760
761    url_id = db_->AddURL(url_info);
762    if (!url_id) {
763      NOTREACHED() << "Adding URL failed.";
764      return std::make_pair(0, 0);
765    }
766    url_info.id_ = url_id;
767  }
768
769  // Add the visit with the time to the database.
770  VisitRow visit_info(url_id, time, referring_visit, transition, 0);
771  VisitID visit_id = db_->AddVisit(&visit_info, visit_source);
772  NotifyVisitObservers(visit_info);
773
774  if (visit_info.visit_time < first_recorded_time_)
775    first_recorded_time_ = visit_info.visit_time;
776
777  // Broadcast a notification of the visit.
778  if (visit_id) {
779    if (typed_url_syncable_service_.get())
780      typed_url_syncable_service_->OnUrlVisited(transition, &url_info);
781
782    scoped_ptr<URLVisitedDetails> details(new URLVisitedDetails);
783    details->transition = transition;
784    details->row = url_info;
785    // TODO(meelapshah) Disabled due to potential PageCycler regression.
786    // Re-enable this.
787    // GetMostRecentRedirectsTo(url, &details->redirects);
788    BroadcastNotifications(chrome::NOTIFICATION_HISTORY_URL_VISITED,
789                           details.PassAs<HistoryDetails>());
790  } else {
791    VLOG(0) << "Failed to build visit insert statement:  "
792            << "url_id = " << url_id;
793  }
794
795  return std::make_pair(url_id, visit_id);
796}
797
798void HistoryBackend::AddPagesWithDetails(const URLRows& urls,
799                                         VisitSource visit_source) {
800  if (!db_)
801    return;
802
803  scoped_ptr<URLsModifiedDetails> modified(new URLsModifiedDetails);
804  for (URLRows::const_iterator i = urls.begin(); i != urls.end(); ++i) {
805    DCHECK(!i->last_visit().is_null());
806
807    // We will add to either the archived database or the main one depending on
808    // the date of the added visit.
809    URLDatabase* url_database;
810    VisitDatabase* visit_database;
811    if (IsExpiredVisitTime(i->last_visit())) {
812      if (!archived_db_)
813        return;  // No archived database to save it to, just forget this.
814      url_database = archived_db_.get();
815      visit_database = archived_db_.get();
816    } else {
817      url_database = db_.get();
818      visit_database = db_.get();
819    }
820
821    URLRow existing_url;
822    URLID url_id = url_database->GetRowForURL(i->url(), &existing_url);
823    if (!url_id) {
824      // Add the page if it doesn't exist.
825      url_id = url_database->AddURL(*i);
826      if (!url_id) {
827        NOTREACHED() << "Could not add row to DB";
828        return;
829      }
830
831      if (i->typed_count() > 0) {
832        modified->changed_urls.push_back(*i);
833        modified->changed_urls.back().set_id(url_id);  // *i likely has |id_| 0.
834      }
835    }
836
837    // Sync code manages the visits itself.
838    if (visit_source != SOURCE_SYNCED) {
839      // Make up a visit to correspond to the last visit to the page.
840      VisitRow visit_info(url_id, i->last_visit(), 0,
841                          content::PageTransitionFromInt(
842                              content::PAGE_TRANSITION_LINK |
843                              content::PAGE_TRANSITION_CHAIN_START |
844                              content::PAGE_TRANSITION_CHAIN_END), 0);
845      if (!visit_database->AddVisit(&visit_info, visit_source)) {
846        NOTREACHED() << "Adding visit failed.";
847        return;
848      }
849      NotifyVisitObservers(visit_info);
850
851      if (visit_info.visit_time < first_recorded_time_)
852        first_recorded_time_ = visit_info.visit_time;
853    }
854  }
855
856  if (typed_url_syncable_service_.get())
857    typed_url_syncable_service_->OnUrlsModified(&modified->changed_urls);
858
859  // Broadcast a notification for typed URLs that have been modified. This
860  // will be picked up by the in-memory URL database on the main thread.
861  //
862  // TODO(brettw) bug 1140015: Add an "add page" notification so the history
863  // views can keep in sync.
864  BroadcastNotifications(chrome::NOTIFICATION_HISTORY_URLS_MODIFIED,
865                         modified.PassAs<HistoryDetails>());
866
867  ScheduleCommit();
868}
869
870bool HistoryBackend::IsExpiredVisitTime(const base::Time& time) {
871  return time < expirer_.GetCurrentArchiveTime();
872}
873
874void HistoryBackend::SetPageTitle(const GURL& url,
875                                  const base::string16& title) {
876  if (!db_)
877    return;
878
879  // Search for recent redirects which should get the same title. We make a
880  // dummy list containing the exact URL visited if there are no redirects so
881  // the processing below can be the same.
882  history::RedirectList dummy_list;
883  history::RedirectList* redirects;
884  RedirectCache::iterator iter = recent_redirects_.Get(url);
885  if (iter != recent_redirects_.end()) {
886    redirects = &iter->second;
887
888    // This redirect chain should have the destination URL as the last item.
889    DCHECK(!redirects->empty());
890    DCHECK(redirects->back() == url);
891  } else {
892    // No redirect chain stored, make up one containing the URL we want so we
893    // can use the same logic below.
894    dummy_list.push_back(url);
895    redirects = &dummy_list;
896  }
897
898  scoped_ptr<URLsModifiedDetails> details(new URLsModifiedDetails);
899  for (size_t i = 0; i < redirects->size(); i++) {
900    URLRow row;
901    URLID row_id = db_->GetRowForURL(redirects->at(i), &row);
902    if (row_id && row.title() != title) {
903      row.set_title(title);
904      db_->UpdateURLRow(row_id, row);
905      details->changed_urls.push_back(row);
906    }
907  }
908
909  // Broadcast notifications for any URLs that have changed. This will
910  // update the in-memory database and the InMemoryURLIndex.
911  if (!details->changed_urls.empty()) {
912    if (typed_url_syncable_service_.get())
913      typed_url_syncable_service_->OnUrlsModified(&details->changed_urls);
914    BroadcastNotifications(chrome::NOTIFICATION_HISTORY_URLS_MODIFIED,
915                           details.PassAs<HistoryDetails>());
916    ScheduleCommit();
917  }
918}
919
920void HistoryBackend::AddPageNoVisitForBookmark(const GURL& url,
921                                               const base::string16& title) {
922  if (!db_)
923    return;
924
925  URLRow url_info(url);
926  URLID url_id = db_->GetRowForURL(url, &url_info);
927  if (url_id) {
928    // URL is already known, nothing to do.
929    return;
930  }
931
932  if (!title.empty()) {
933    url_info.set_title(title);
934  } else {
935    url_info.set_title(base::UTF8ToUTF16(url.spec()));
936  }
937
938  url_info.set_last_visit(Time::Now());
939  // Mark the page hidden. If the user types it in, it'll unhide.
940  url_info.set_hidden(true);
941
942  db_->AddURL(url_info);
943}
944
945void HistoryBackend::IterateURLs(
946    const scoped_refptr<visitedlink::VisitedLinkDelegate::URLEnumerator>&
947    iterator) {
948  if (db_) {
949    HistoryDatabase::URLEnumerator e;
950    if (db_->InitURLEnumeratorForEverything(&e)) {
951      URLRow info;
952      while (e.GetNextURL(&info)) {
953        iterator->OnURL(info.url());
954      }
955      iterator->OnComplete(true);  // Success.
956      return;
957    }
958  }
959  iterator->OnComplete(false);  // Failure.
960}
961
962bool HistoryBackend::GetAllTypedURLs(URLRows* urls) {
963  if (db_)
964    return db_->GetAllTypedUrls(urls);
965  return false;
966}
967
968bool HistoryBackend::GetVisitsForURL(URLID id, VisitVector* visits) {
969  if (db_)
970    return db_->GetVisitsForURL(id, visits);
971  return false;
972}
973
974bool HistoryBackend::GetMostRecentVisitsForURL(URLID id,
975                                               int max_visits,
976                                               VisitVector* visits) {
977  if (db_)
978    return db_->GetMostRecentVisitsForURL(id, max_visits, visits);
979  return false;
980}
981
982bool HistoryBackend::UpdateURL(URLID id, const history::URLRow& url) {
983  if (db_)
984    return db_->UpdateURLRow(id, url);
985  return false;
986}
987
988bool HistoryBackend::AddVisits(const GURL& url,
989                               const std::vector<VisitInfo>& visits,
990                               VisitSource visit_source) {
991  if (db_) {
992    for (std::vector<VisitInfo>::const_iterator visit = visits.begin();
993         visit != visits.end(); ++visit) {
994      if (!AddPageVisit(
995              url, visit->first, 0, visit->second, visit_source).first) {
996        return false;
997      }
998    }
999    ScheduleCommit();
1000    return true;
1001  }
1002  return false;
1003}
1004
1005bool HistoryBackend::RemoveVisits(const VisitVector& visits) {
1006  if (!db_)
1007    return false;
1008
1009  expirer_.ExpireVisits(visits);
1010  ScheduleCommit();
1011  return true;
1012}
1013
1014bool HistoryBackend::GetVisitsSource(const VisitVector& visits,
1015                                     VisitSourceMap* sources) {
1016  if (!db_)
1017    return false;
1018
1019  db_->GetVisitsSource(visits, sources);
1020  return true;
1021}
1022
1023bool HistoryBackend::GetURL(const GURL& url, history::URLRow* url_row) {
1024  if (db_)
1025    return db_->GetRowForURL(url, url_row) != 0;
1026  return false;
1027}
1028
1029void HistoryBackend::QueryURL(scoped_refptr<QueryURLRequest> request,
1030                              const GURL& url,
1031                              bool want_visits) {
1032  if (request->canceled())
1033    return;
1034
1035  bool success = false;
1036  URLRow* row = &request->value.a;
1037  VisitVector* visits = &request->value.b;
1038  if (db_) {
1039    if (db_->GetRowForURL(url, row)) {
1040      // Have a row.
1041      success = true;
1042
1043      // Optionally query the visits.
1044      if (want_visits)
1045        db_->GetVisitsForURL(row->id(), visits);
1046    }
1047  }
1048  request->ForwardResult(request->handle(), success, row, visits);
1049}
1050
1051TypedUrlSyncableService* HistoryBackend::GetTypedUrlSyncableService() const {
1052  return typed_url_syncable_service_.get();
1053}
1054
1055// Segment usage ---------------------------------------------------------------
1056
1057void HistoryBackend::DeleteOldSegmentData() {
1058  if (db_)
1059    db_->DeleteSegmentData(Time::Now() -
1060                           TimeDelta::FromDays(kSegmentDataRetention));
1061}
1062
1063void HistoryBackend::QuerySegmentUsage(
1064    scoped_refptr<QuerySegmentUsageRequest> request,
1065    const Time from_time,
1066    int max_result_count) {
1067  if (request->canceled())
1068    return;
1069
1070  if (db_) {
1071    db_->QuerySegmentUsage(from_time, max_result_count, &request->value.get());
1072
1073    // If this is the first time we query segments, invoke
1074    // DeleteOldSegmentData asynchronously. We do this to cleanup old
1075    // entries.
1076    if (!segment_queried_) {
1077      segment_queried_ = true;
1078      base::MessageLoop::current()->PostTask(
1079          FROM_HERE,
1080          base::Bind(&HistoryBackend::DeleteOldSegmentData, this));
1081    }
1082  }
1083  request->ForwardResult(request->handle(), &request->value.get());
1084}
1085
1086// Keyword visits --------------------------------------------------------------
1087
1088void HistoryBackend::SetKeywordSearchTermsForURL(const GURL& url,
1089                                                 TemplateURLID keyword_id,
1090                                                 const base::string16& term) {
1091  if (!db_)
1092    return;
1093
1094  // Get the ID for this URL.
1095  URLID url_id = db_->GetRowForURL(url, NULL);
1096  if (!url_id) {
1097    // There is a small possibility the url was deleted before the keyword
1098    // was added. Ignore the request.
1099    return;
1100  }
1101
1102  db_->SetKeywordSearchTermsForURL(url_id, keyword_id, term);
1103
1104  BroadcastNotifications(
1105      chrome::NOTIFICATION_HISTORY_KEYWORD_SEARCH_TERM_UPDATED,
1106      scoped_ptr<HistoryDetails>(
1107          new KeywordSearchUpdatedDetails(url, keyword_id, term)));
1108  ScheduleCommit();
1109}
1110
1111void HistoryBackend::DeleteAllSearchTermsForKeyword(
1112    TemplateURLID keyword_id) {
1113  if (!db_)
1114    return;
1115
1116  db_->DeleteAllSearchTermsForKeyword(keyword_id);
1117  // TODO(sky): bug 1168470. Need to move from archive dbs too.
1118  ScheduleCommit();
1119}
1120
1121void HistoryBackend::GetMostRecentKeywordSearchTerms(
1122    scoped_refptr<GetMostRecentKeywordSearchTermsRequest> request,
1123    TemplateURLID keyword_id,
1124    const base::string16& prefix,
1125    int max_count) {
1126  if (request->canceled())
1127    return;
1128
1129  if (db_) {
1130    db_->GetMostRecentKeywordSearchTerms(keyword_id, prefix, max_count,
1131                                         &(request->value));
1132  }
1133  request->ForwardResult(request->handle(), &request->value);
1134}
1135
1136void HistoryBackend::DeleteKeywordSearchTermForURL(const GURL& url) {
1137  if (!db_)
1138    return;
1139
1140  URLID url_id = db_->GetRowForURL(url, NULL);
1141  if (!url_id)
1142    return;
1143  db_->DeleteKeywordSearchTermForURL(url_id);
1144
1145  BroadcastNotifications(
1146      chrome::NOTIFICATION_HISTORY_KEYWORD_SEARCH_TERM_DELETED,
1147      scoped_ptr<HistoryDetails>(new KeywordSearchDeletedDetails(url)));
1148  ScheduleCommit();
1149}
1150
1151void HistoryBackend::DeleteMatchingURLsForKeyword(TemplateURLID keyword_id,
1152                                                  const base::string16& term) {
1153  if (!db_)
1154    return;
1155
1156  std::vector<KeywordSearchTermRow> rows;
1157  if (db_->GetKeywordSearchTermRows(term, &rows)) {
1158    std::vector<GURL> items_to_delete;
1159    URLRow row;
1160    for (std::vector<KeywordSearchTermRow>::iterator it = rows.begin();
1161         it != rows.end(); ++it) {
1162      if ((it->keyword_id == keyword_id) && db_->GetURLRow(it->url_id, &row))
1163        items_to_delete.push_back(row.url());
1164    }
1165    DeleteURLs(items_to_delete);
1166  }
1167}
1168
1169// Downloads -------------------------------------------------------------------
1170
1171uint32 HistoryBackend::GetNextDownloadId() {
1172  return db_ ? db_->GetNextDownloadId() : content::DownloadItem::kInvalidId;
1173}
1174
1175// Get all the download entries from the database.
1176void HistoryBackend::QueryDownloads(std::vector<DownloadRow>* rows) {
1177  if (db_)
1178    db_->QueryDownloads(rows);
1179}
1180
1181// Update a particular download entry.
1182void HistoryBackend::UpdateDownload(const history::DownloadRow& data) {
1183  if (!db_)
1184    return;
1185  db_->UpdateDownload(data);
1186  ScheduleCommit();
1187}
1188
1189bool HistoryBackend::CreateDownload(const history::DownloadRow& history_info) {
1190  if (!db_)
1191    return false;
1192  bool success = db_->CreateDownload(history_info);
1193  ScheduleCommit();
1194  return success;
1195}
1196
1197void HistoryBackend::RemoveDownloads(const std::set<uint32>& ids) {
1198  if (!db_)
1199    return;
1200  size_t downloads_count_before = db_->CountDownloads();
1201  base::TimeTicks started_removing = base::TimeTicks::Now();
1202  // HistoryBackend uses a long-running Transaction that is committed
1203  // periodically, so this loop doesn't actually hit the disk too hard.
1204  for (std::set<uint32>::const_iterator it = ids.begin();
1205       it != ids.end(); ++it) {
1206    db_->RemoveDownload(*it);
1207  }
1208  ScheduleCommit();
1209  base::TimeTicks finished_removing = base::TimeTicks::Now();
1210  size_t downloads_count_after = db_->CountDownloads();
1211
1212  DCHECK_LE(downloads_count_after, downloads_count_before);
1213  if (downloads_count_after > downloads_count_before)
1214    return;
1215  size_t num_downloads_deleted = downloads_count_before - downloads_count_after;
1216  UMA_HISTOGRAM_COUNTS("Download.DatabaseRemoveDownloadsCount",
1217                        num_downloads_deleted);
1218  base::TimeDelta micros = (1000 * (finished_removing - started_removing));
1219  UMA_HISTOGRAM_TIMES("Download.DatabaseRemoveDownloadsTime", micros);
1220  if (num_downloads_deleted > 0) {
1221    UMA_HISTOGRAM_TIMES("Download.DatabaseRemoveDownloadsTimePerRecord",
1222                        (1000 * micros) / num_downloads_deleted);
1223  }
1224  DCHECK_GE(ids.size(), num_downloads_deleted);
1225  if (ids.size() < num_downloads_deleted)
1226    return;
1227  UMA_HISTOGRAM_COUNTS("Download.DatabaseRemoveDownloadsCountNotRemoved",
1228                        ids.size() - num_downloads_deleted);
1229}
1230
1231void HistoryBackend::QueryHistory(scoped_refptr<QueryHistoryRequest> request,
1232                                  const base::string16& text_query,
1233                                  const QueryOptions& options) {
1234  if (request->canceled())
1235    return;
1236
1237  TimeTicks beginning_time = TimeTicks::Now();
1238
1239  if (db_) {
1240    if (text_query.empty()) {
1241      // Basic history query for the main database.
1242      QueryHistoryBasic(db_.get(), db_.get(), options, &request->value);
1243
1244      // Now query the archived database. This is a bit tricky because we don't
1245      // want to query it if the queried time range isn't going to find anything
1246      // in it.
1247      // TODO(brettw) bug 1171036: do blimpie querying for the archived database
1248      // as well.
1249      // if (archived_db_.get() &&
1250      //     expirer_.GetCurrentArchiveTime() - TimeDelta::FromDays(7)) {
1251    } else {
1252      // Text history query.
1253      QueryHistoryText(db_.get(), db_.get(), text_query, options,
1254                       &request->value);
1255      if (archived_db_.get() &&
1256          expirer_.GetCurrentArchiveTime() >= options.begin_time) {
1257        QueryHistoryText(archived_db_.get(), archived_db_.get(), text_query,
1258                         options, &request->value);
1259      }
1260    }
1261  }
1262
1263  request->ForwardResult(request->handle(), &request->value);
1264
1265  UMA_HISTOGRAM_TIMES("History.QueryHistory",
1266                      TimeTicks::Now() - beginning_time);
1267}
1268
1269// Basic time-based querying of history.
1270void HistoryBackend::QueryHistoryBasic(URLDatabase* url_db,
1271                                       VisitDatabase* visit_db,
1272                                       const QueryOptions& options,
1273                                       QueryResults* result) {
1274  // First get all visits.
1275  VisitVector visits;
1276  bool has_more_results = visit_db->GetVisibleVisitsInRange(options, &visits);
1277  DCHECK(static_cast<int>(visits.size()) <= options.EffectiveMaxCount());
1278
1279  // Now add them and the URL rows to the results.
1280  URLResult url_result;
1281  for (size_t i = 0; i < visits.size(); i++) {
1282    const VisitRow visit = visits[i];
1283
1284    // Add a result row for this visit, get the URL info from the DB.
1285    if (!url_db->GetURLRow(visit.url_id, &url_result)) {
1286      VLOG(0) << "Failed to get id " << visit.url_id
1287              << " from history.urls.";
1288      continue;  // DB out of sync and URL doesn't exist, try to recover.
1289    }
1290
1291    if (!url_result.url().is_valid()) {
1292      VLOG(0) << "Got invalid URL from history.urls with id "
1293              << visit.url_id << ":  "
1294              << url_result.url().possibly_invalid_spec();
1295      continue;  // Don't report invalid URLs in case of corruption.
1296    }
1297
1298    // The archived database may be out of sync with respect to starring,
1299    // titles, last visit date, etc. Therefore, we query the main DB if the
1300    // current URL database is not the main one.
1301    if (url_db == db_.get()) {
1302      // Currently querying the archived DB, update with the main database to
1303      // catch any interesting stuff. This will update it if it exists in the
1304      // main DB, and do nothing otherwise.
1305      db_->GetRowForURL(url_result.url(), &url_result);
1306    }
1307
1308    url_result.set_visit_time(visit.visit_time);
1309
1310    // Set whether the visit was blocked for a managed user by looking at the
1311    // transition type.
1312    url_result.set_blocked_visit(
1313        (visit.transition & content::PAGE_TRANSITION_BLOCKED) != 0);
1314
1315    // We don't set any of the query-specific parts of the URLResult, since
1316    // snippets and stuff don't apply to basic querying.
1317    result->AppendURLBySwapping(&url_result);
1318  }
1319
1320  if (!has_more_results && options.begin_time <= first_recorded_time_)
1321    result->set_reached_beginning(true);
1322}
1323
1324// Text-based querying of history.
1325void HistoryBackend::QueryHistoryText(URLDatabase* url_db,
1326                                      VisitDatabase* visit_db,
1327                                      const base::string16& text_query,
1328                                      const QueryOptions& options,
1329                                      QueryResults* result) {
1330  URLRows text_matches;
1331  url_db->GetTextMatches(text_query, &text_matches);
1332
1333  std::vector<URLResult> matching_visits;
1334  VisitVector visits;    // Declare outside loop to prevent re-construction.
1335  for (size_t i = 0; i < text_matches.size(); i++) {
1336    const URLRow& text_match = text_matches[i];
1337    // Get all visits for given URL match.
1338    visit_db->GetVisibleVisitsForURL(text_match.id(), options, &visits);
1339    for (size_t j = 0; j < visits.size(); j++) {
1340      URLResult url_result(text_match);
1341      url_result.set_visit_time(visits[j].visit_time);
1342      matching_visits.push_back(url_result);
1343    }
1344  }
1345
1346  std::sort(matching_visits.begin(), matching_visits.end(),
1347            URLResult::CompareVisitTime);
1348
1349  size_t max_results = options.max_count == 0 ?
1350      std::numeric_limits<size_t>::max() : static_cast<int>(options.max_count);
1351  for (std::vector<URLResult>::iterator it = matching_visits.begin();
1352       it != matching_visits.end() && result->size() < max_results; ++it) {
1353    result->AppendURLBySwapping(&(*it));
1354  }
1355
1356  if (matching_visits.size() == result->size() &&
1357      options.begin_time <= first_recorded_time_)
1358    result->set_reached_beginning(true);
1359}
1360
1361// Frontend to GetMostRecentRedirectsFrom from the history thread.
1362void HistoryBackend::QueryRedirectsFrom(
1363    scoped_refptr<QueryRedirectsRequest> request,
1364    const GURL& url) {
1365  if (request->canceled())
1366    return;
1367  bool success = GetMostRecentRedirectsFrom(url, &request->value);
1368  request->ForwardResult(request->handle(), url, success, &request->value);
1369}
1370
1371void HistoryBackend::QueryRedirectsTo(
1372    scoped_refptr<QueryRedirectsRequest> request,
1373    const GURL& url) {
1374  if (request->canceled())
1375    return;
1376  bool success = GetMostRecentRedirectsTo(url, &request->value);
1377  request->ForwardResult(request->handle(), url, success, &request->value);
1378}
1379
1380void HistoryBackend::GetVisibleVisitCountToHost(
1381    scoped_refptr<GetVisibleVisitCountToHostRequest> request,
1382    const GURL& url) {
1383  if (request->canceled())
1384    return;
1385  int count = 0;
1386  Time first_visit;
1387  const bool success = db_.get() &&
1388      db_->GetVisibleVisitCountToHost(url, &count, &first_visit);
1389  request->ForwardResult(request->handle(), success, count, first_visit);
1390}
1391
1392void HistoryBackend::QueryTopURLsAndRedirects(
1393    scoped_refptr<QueryTopURLsAndRedirectsRequest> request,
1394    int result_count) {
1395  if (request->canceled())
1396    return;
1397
1398  if (!db_) {
1399    request->ForwardResult(request->handle(), false, NULL, NULL);
1400    return;
1401  }
1402
1403  std::vector<GURL>* top_urls = &request->value.a;
1404  history::RedirectMap* redirects = &request->value.b;
1405
1406  ScopedVector<PageUsageData> data;
1407  db_->QuerySegmentUsage(base::Time::Now() - base::TimeDelta::FromDays(90),
1408      result_count, &data.get());
1409
1410  for (size_t i = 0; i < data.size(); ++i) {
1411    top_urls->push_back(data[i]->GetURL());
1412    RefCountedVector<GURL>* list = new RefCountedVector<GURL>;
1413    GetMostRecentRedirectsFrom(top_urls->back(), &list->data);
1414    (*redirects)[top_urls->back()] = list;
1415  }
1416
1417  request->ForwardResult(request->handle(), true, top_urls, redirects);
1418}
1419
1420// Will replace QueryTopURLsAndRedirectsRequest.
1421void HistoryBackend::QueryMostVisitedURLs(
1422    scoped_refptr<QueryMostVisitedURLsRequest> request,
1423    int result_count,
1424    int days_back) {
1425  if (request->canceled())
1426    return;
1427
1428  if (!db_) {
1429    // No History Database - return an empty list.
1430    request->ForwardResult(request->handle(), MostVisitedURLList());
1431    return;
1432  }
1433
1434  MostVisitedURLList* result = &request->value;
1435  QueryMostVisitedURLsImpl(result_count, days_back, result);
1436  request->ForwardResult(request->handle(), *result);
1437}
1438
1439void HistoryBackend::QueryFilteredURLs(
1440      scoped_refptr<QueryFilteredURLsRequest> request,
1441      int result_count,
1442      const history::VisitFilter& filter,
1443      bool extended_info)  {
1444  if (request->canceled())
1445    return;
1446
1447  base::Time request_start = base::Time::Now();
1448
1449  if (!db_) {
1450    // No History Database - return an empty list.
1451    request->ForwardResult(request->handle(), FilteredURLList());
1452    return;
1453  }
1454
1455  VisitVector visits;
1456  db_->GetDirectVisitsDuringTimes(filter, 0, &visits);
1457
1458  std::map<URLID, double> score_map;
1459  for (size_t i = 0; i < visits.size(); ++i) {
1460    score_map[visits[i].url_id] += filter.GetVisitScore(visits[i]);
1461  }
1462
1463  // TODO(georgey): experiment with visit_segment database granularity (it is
1464  // currently 24 hours) to use it directly instead of using visits database,
1465  // which is considerably slower.
1466  ScopedVector<PageUsageData> data;
1467  data.reserve(score_map.size());
1468  for (std::map<URLID, double>::iterator it = score_map.begin();
1469       it != score_map.end(); ++it) {
1470    PageUsageData* pud = new PageUsageData(it->first);
1471    pud->SetScore(it->second);
1472    data.push_back(pud);
1473  }
1474
1475  // Limit to the top |result_count| results.
1476  std::sort(data.begin(), data.end(), PageUsageData::Predicate);
1477  if (result_count && implicit_cast<int>(data.size()) > result_count)
1478    data.resize(result_count);
1479
1480  for (size_t i = 0; i < data.size(); ++i) {
1481    URLRow info;
1482    if (db_->GetURLRow(data[i]->GetID(), &info)) {
1483      data[i]->SetURL(info.url());
1484      data[i]->SetTitle(info.title());
1485    }
1486  }
1487
1488  FilteredURLList& result = request->value;
1489  for (size_t i = 0; i < data.size(); ++i) {
1490    PageUsageData* current_data = data[i];
1491    FilteredURL url(*current_data);
1492
1493    if (extended_info) {
1494      VisitVector visits;
1495      db_->GetVisitsForURL(current_data->GetID(), &visits);
1496      if (visits.size() > 0) {
1497        url.extended_info.total_visits = visits.size();
1498        for (size_t i = 0; i < visits.size(); ++i) {
1499          url.extended_info.duration_opened +=
1500              visits[i].visit_duration.InSeconds();
1501          if (visits[i].visit_time > url.extended_info.last_visit_time) {
1502            url.extended_info.last_visit_time = visits[i].visit_time;
1503          }
1504        }
1505        // TODO(macourteau): implement the url.extended_info.visits stat.
1506      }
1507    }
1508    result.push_back(url);
1509  }
1510
1511  int delta_time = std::max(1, std::min(999,
1512      static_cast<int>((base::Time::Now() - request_start).InMilliseconds())));
1513  STATIC_HISTOGRAM_POINTER_BLOCK(
1514      "NewTabPage.SuggestedSitesLoadTime",
1515      Add(delta_time),
1516      base::LinearHistogram::FactoryGet("NewTabPage.SuggestedSitesLoadTime",
1517          1, 1000, 100, base::Histogram::kUmaTargetedHistogramFlag));
1518
1519  request->ForwardResult(request->handle(), result);
1520}
1521
1522void HistoryBackend::QueryMostVisitedURLsImpl(int result_count,
1523                                              int days_back,
1524                                              MostVisitedURLList* result) {
1525  if (!db_)
1526    return;
1527
1528  ScopedVector<PageUsageData> data;
1529  db_->QuerySegmentUsage(base::Time::Now() -
1530                         base::TimeDelta::FromDays(days_back),
1531                         result_count, &data.get());
1532
1533  for (size_t i = 0; i < data.size(); ++i) {
1534    PageUsageData* current_data = data[i];
1535    RedirectList redirects;
1536    GetMostRecentRedirectsFrom(current_data->GetURL(), &redirects);
1537    MostVisitedURL url = MakeMostVisitedURL(*current_data, redirects);
1538    result->push_back(url);
1539  }
1540}
1541
1542void HistoryBackend::GetRedirectsFromSpecificVisit(
1543    VisitID cur_visit, history::RedirectList* redirects) {
1544  // Follow any redirects from the given visit and add them to the list.
1545  // It *should* be impossible to get a circular chain here, but we check
1546  // just in case to avoid infinite loops.
1547  GURL cur_url;
1548  std::set<VisitID> visit_set;
1549  visit_set.insert(cur_visit);
1550  while (db_->GetRedirectFromVisit(cur_visit, &cur_visit, &cur_url)) {
1551    if (visit_set.find(cur_visit) != visit_set.end()) {
1552      NOTREACHED() << "Loop in visit chain, giving up";
1553      return;
1554    }
1555    visit_set.insert(cur_visit);
1556    redirects->push_back(cur_url);
1557  }
1558}
1559
1560void HistoryBackend::GetRedirectsToSpecificVisit(
1561    VisitID cur_visit,
1562    history::RedirectList* redirects) {
1563  // Follow redirects going to cur_visit. These are added to |redirects| in
1564  // the order they are found. If a redirect chain looks like A -> B -> C and
1565  // |cur_visit| = C, redirects will be {B, A} in that order.
1566  if (!db_)
1567    return;
1568
1569  GURL cur_url;
1570  std::set<VisitID> visit_set;
1571  visit_set.insert(cur_visit);
1572  while (db_->GetRedirectToVisit(cur_visit, &cur_visit, &cur_url)) {
1573    if (visit_set.find(cur_visit) != visit_set.end()) {
1574      NOTREACHED() << "Loop in visit chain, giving up";
1575      return;
1576    }
1577    visit_set.insert(cur_visit);
1578    redirects->push_back(cur_url);
1579  }
1580}
1581
1582bool HistoryBackend::GetMostRecentRedirectsFrom(
1583    const GURL& from_url,
1584    history::RedirectList* redirects) {
1585  redirects->clear();
1586  if (!db_)
1587    return false;
1588
1589  URLID from_url_id = db_->GetRowForURL(from_url, NULL);
1590  VisitID cur_visit = db_->GetMostRecentVisitForURL(from_url_id, NULL);
1591  if (!cur_visit)
1592    return false;  // No visits for URL.
1593
1594  GetRedirectsFromSpecificVisit(cur_visit, redirects);
1595  return true;
1596}
1597
1598bool HistoryBackend::GetMostRecentRedirectsTo(
1599    const GURL& to_url,
1600    history::RedirectList* redirects) {
1601  redirects->clear();
1602  if (!db_)
1603    return false;
1604
1605  URLID to_url_id = db_->GetRowForURL(to_url, NULL);
1606  VisitID cur_visit = db_->GetMostRecentVisitForURL(to_url_id, NULL);
1607  if (!cur_visit)
1608    return false;  // No visits for URL.
1609
1610  GetRedirectsToSpecificVisit(cur_visit, redirects);
1611  return true;
1612}
1613
1614void HistoryBackend::ScheduleAutocomplete(HistoryURLProvider* provider,
1615                                          HistoryURLProviderParams* params) {
1616  // ExecuteWithDB should handle the NULL database case.
1617  provider->ExecuteWithDB(this, db_.get(), params);
1618}
1619
1620void HistoryBackend::DeleteFTSIndexDatabases() {
1621  // Find files on disk matching the text databases file pattern so we can
1622  // quickly test for and delete them.
1623  base::FilePath::StringType filepattern =
1624      FILE_PATH_LITERAL("History Index *");
1625  base::FileEnumerator enumerator(
1626      history_dir_, false, base::FileEnumerator::FILES, filepattern);
1627  int num_databases_deleted = 0;
1628  base::FilePath current_file;
1629  while (!(current_file = enumerator.Next()).empty()) {
1630    if (sql::Connection::Delete(current_file))
1631      num_databases_deleted++;
1632  }
1633  UMA_HISTOGRAM_COUNTS("History.DeleteFTSIndexDatabases",
1634                       num_databases_deleted);
1635}
1636
1637void HistoryBackend::GetFavicons(
1638    const std::vector<GURL>& icon_urls,
1639    int icon_types,
1640    int desired_size_in_dip,
1641    const std::vector<ui::ScaleFactor>& desired_scale_factors,
1642    std::vector<chrome::FaviconBitmapResult>* bitmap_results) {
1643  UpdateFaviconMappingsAndFetchImpl(NULL, icon_urls, icon_types,
1644                                    desired_size_in_dip, desired_scale_factors,
1645                                    bitmap_results);
1646}
1647
1648void HistoryBackend::GetLargestFaviconForURL(
1649      const GURL& page_url,
1650      const std::vector<int>& icon_types,
1651      int minimum_size_in_pixels,
1652      chrome::FaviconBitmapResult* favicon_bitmap_result) {
1653  DCHECK(favicon_bitmap_result);
1654
1655  if (!db_ || !thumbnail_db_)
1656    return;
1657
1658  TimeTicks beginning_time = TimeTicks::Now();
1659
1660  std::vector<IconMapping> icon_mappings;
1661  if (!thumbnail_db_->GetIconMappingsForPageURL(page_url, &icon_mappings) ||
1662      icon_mappings.empty())
1663    return;
1664
1665  int required_icon_types = 0;
1666  for (std::vector<int>::const_iterator i = icon_types.begin();
1667       i != icon_types.end(); ++i) {
1668    required_icon_types |= *i;
1669  }
1670
1671  // Find the largest bitmap for each IconType placing in
1672  // |largest_favicon_bitmaps|.
1673  std::map<chrome::IconType, FaviconBitmap> largest_favicon_bitmaps;
1674  for (std::vector<IconMapping>::const_iterator i = icon_mappings.begin();
1675       i != icon_mappings.end(); ++i) {
1676    if (!(i->icon_type & required_icon_types))
1677      continue;
1678    std::vector<FaviconBitmapIDSize> bitmap_id_sizes;
1679    thumbnail_db_->GetFaviconBitmapIDSizes(i->icon_id, &bitmap_id_sizes);
1680    FaviconBitmap& largest = largest_favicon_bitmaps[i->icon_type];
1681    for (std::vector<FaviconBitmapIDSize>::const_iterator j =
1682             bitmap_id_sizes.begin(); j != bitmap_id_sizes.end(); ++j) {
1683      if (largest.bitmap_id == 0 ||
1684          (largest.pixel_size.width() < j->pixel_size.width() &&
1685           largest.pixel_size.height() < j->pixel_size.height())) {
1686        largest.icon_id = i->icon_id;
1687        largest.bitmap_id = j->bitmap_id;
1688        largest.pixel_size = j->pixel_size;
1689      }
1690    }
1691  }
1692  if (largest_favicon_bitmaps.empty())
1693    return;
1694
1695  // Find an icon which is larger than minimum_size_in_pixels in the order of
1696  // icon_types.
1697  FaviconBitmap largest_icon;
1698  for (std::vector<int>::const_iterator t = icon_types.begin();
1699       t != icon_types.end(); ++t) {
1700    for (std::map<chrome::IconType, FaviconBitmap>::const_iterator f =
1701            largest_favicon_bitmaps.begin(); f != largest_favicon_bitmaps.end();
1702        ++f) {
1703      if (f->first & *t &&
1704          (largest_icon.bitmap_id == 0 ||
1705           (largest_icon.pixel_size.height() < f->second.pixel_size.height() &&
1706            largest_icon.pixel_size.width() < f->second.pixel_size.width()))) {
1707        largest_icon = f->second;
1708      }
1709    }
1710    if (largest_icon.pixel_size.width() > minimum_size_in_pixels &&
1711        largest_icon.pixel_size.height() > minimum_size_in_pixels)
1712      break;
1713  }
1714
1715  GURL icon_url;
1716  chrome::IconType icon_type;
1717  if (!thumbnail_db_->GetFaviconHeader(largest_icon.icon_id, &icon_url,
1718                                       &icon_type)) {
1719    return;
1720  }
1721
1722  base::Time last_updated;
1723  chrome::FaviconBitmapResult bitmap_result;
1724  bitmap_result.icon_url = icon_url;
1725  bitmap_result.icon_type = icon_type;
1726  if (!thumbnail_db_->GetFaviconBitmap(largest_icon.bitmap_id,
1727                                       &last_updated,
1728                                       &bitmap_result.bitmap_data,
1729                                       &bitmap_result.pixel_size)) {
1730    return;
1731  }
1732
1733  bitmap_result.expired = (Time::Now() - last_updated) >
1734      TimeDelta::FromDays(kFaviconRefetchDays);
1735  if (bitmap_result.is_valid())
1736    *favicon_bitmap_result = bitmap_result;
1737
1738  HISTOGRAM_TIMES("History.GetLargestFaviconForURL",
1739                  TimeTicks::Now() - beginning_time);
1740}
1741
1742void HistoryBackend::GetFaviconsForURL(
1743    const GURL& page_url,
1744    int icon_types,
1745    int desired_size_in_dip,
1746    const std::vector<ui::ScaleFactor>& desired_scale_factors,
1747    std::vector<chrome::FaviconBitmapResult>* bitmap_results) {
1748  DCHECK(bitmap_results);
1749  GetFaviconsFromDB(page_url, icon_types, desired_size_in_dip,
1750                    desired_scale_factors, bitmap_results);
1751}
1752
1753void HistoryBackend::GetFaviconForID(
1754    chrome::FaviconID favicon_id,
1755    int desired_size_in_dip,
1756    ui::ScaleFactor desired_scale_factor,
1757    std::vector<chrome::FaviconBitmapResult>* bitmap_results) {
1758  std::vector<chrome::FaviconID> favicon_ids;
1759  favicon_ids.push_back(favicon_id);
1760  std::vector<ui::ScaleFactor> desired_scale_factors;
1761  desired_scale_factors.push_back(desired_scale_factor);
1762
1763  // Get results from DB.
1764  GetFaviconBitmapResultsForBestMatch(favicon_ids,
1765                                      desired_size_in_dip,
1766                                      desired_scale_factors,
1767                                      bitmap_results);
1768}
1769
1770void HistoryBackend::UpdateFaviconMappingsAndFetch(
1771    const GURL& page_url,
1772    const std::vector<GURL>& icon_urls,
1773    int icon_types,
1774    int desired_size_in_dip,
1775    const std::vector<ui::ScaleFactor>& desired_scale_factors,
1776    std::vector<chrome::FaviconBitmapResult>* bitmap_results) {
1777  UpdateFaviconMappingsAndFetchImpl(&page_url, icon_urls, icon_types,
1778                                    desired_size_in_dip, desired_scale_factors,
1779                                    bitmap_results);
1780}
1781
1782void HistoryBackend::MergeFavicon(
1783    const GURL& page_url,
1784    const GURL& icon_url,
1785    chrome::IconType icon_type,
1786    scoped_refptr<base::RefCountedMemory> bitmap_data,
1787    const gfx::Size& pixel_size) {
1788  if (!thumbnail_db_ || !db_)
1789    return;
1790
1791  chrome::FaviconID favicon_id =
1792      thumbnail_db_->GetFaviconIDForFaviconURL(icon_url, icon_type, NULL);
1793
1794  if (!favicon_id) {
1795    // There is no favicon at |icon_url|, create it.
1796    favicon_id = thumbnail_db_->AddFavicon(icon_url, icon_type);
1797  }
1798
1799  std::vector<FaviconBitmapIDSize> bitmap_id_sizes;
1800  thumbnail_db_->GetFaviconBitmapIDSizes(favicon_id, &bitmap_id_sizes);
1801
1802  // If there is already a favicon bitmap of |pixel_size| at |icon_url|,
1803  // replace it.
1804  bool bitmap_identical = false;
1805  bool replaced_bitmap = false;
1806  for (size_t i = 0; i < bitmap_id_sizes.size(); ++i) {
1807    if (bitmap_id_sizes[i].pixel_size == pixel_size) {
1808      if (IsFaviconBitmapDataEqual(bitmap_id_sizes[i].bitmap_id, bitmap_data)) {
1809        thumbnail_db_->SetFaviconBitmapLastUpdateTime(
1810            bitmap_id_sizes[i].bitmap_id, base::Time::Now());
1811        bitmap_identical = true;
1812      } else {
1813        thumbnail_db_->SetFaviconBitmap(bitmap_id_sizes[i].bitmap_id,
1814            bitmap_data, base::Time::Now());
1815        replaced_bitmap = true;
1816      }
1817      break;
1818    }
1819  }
1820
1821  // Create a vector of the pixel sizes of the favicon bitmaps currently at
1822  // |icon_url|.
1823  std::vector<gfx::Size> favicon_sizes;
1824  for (size_t i = 0; i < bitmap_id_sizes.size(); ++i)
1825    favicon_sizes.push_back(bitmap_id_sizes[i].pixel_size);
1826
1827  if (!replaced_bitmap && !bitmap_identical) {
1828    // Set the preexisting favicon bitmaps as expired as the preexisting favicon
1829    // bitmaps are not consistent with the merged in data.
1830    thumbnail_db_->SetFaviconOutOfDate(favicon_id);
1831
1832    // Delete an arbitrary favicon bitmap to avoid going over the limit of
1833    // |kMaxFaviconBitmapsPerIconURL|.
1834    if (bitmap_id_sizes.size() >= kMaxFaviconBitmapsPerIconURL) {
1835      thumbnail_db_->DeleteFaviconBitmap(bitmap_id_sizes[0].bitmap_id);
1836      favicon_sizes.erase(favicon_sizes.begin());
1837    }
1838    thumbnail_db_->AddFaviconBitmap(favicon_id, bitmap_data, base::Time::Now(),
1839                                    pixel_size);
1840    favicon_sizes.push_back(pixel_size);
1841  }
1842
1843  // A site may have changed the favicons that it uses for |page_url|.
1844  // Example Scenario:
1845  //   page_url = news.google.com
1846  //   Initial State: www.google.com/favicon.ico 16x16, 32x32
1847  //   MergeFavicon(news.google.com, news.google.com/news_specific.ico, ...,
1848  //                ..., 16x16)
1849  //
1850  // Difficulties:
1851  // 1. Sync requires that a call to GetFaviconsForURL() returns the
1852  //    |bitmap_data| passed into MergeFavicon().
1853  //    - It is invalid for the 16x16 bitmap for www.google.com/favicon.ico to
1854  //      stay mapped to news.google.com because it would be unclear which 16x16
1855  //      bitmap should be returned via GetFaviconsForURL().
1856  //
1857  // 2. www.google.com/favicon.ico may be mapped to more than just
1858  //    news.google.com (eg www.google.com).
1859  //    - The 16x16 bitmap cannot be deleted from www.google.com/favicon.ico
1860  //
1861  // To resolve these problems, we copy all of the favicon bitmaps previously
1862  // mapped to news.google.com (|page_url|) and add them to the favicon at
1863  // news.google.com/news_specific.ico (|icon_url|). The favicon sizes for
1864  // |icon_url| are set to default to indicate that |icon_url| has incomplete
1865  // / incorrect data.
1866  // Difficulty 1: All but news.google.com/news_specific.ico are unmapped from
1867  //              news.google.com
1868  // Difficulty 2: The favicon bitmaps for www.google.com/favicon.ico are not
1869  //               modified.
1870
1871  std::vector<IconMapping> icon_mappings;
1872  thumbnail_db_->GetIconMappingsForPageURL(page_url, icon_type, &icon_mappings);
1873
1874  // Copy the favicon bitmaps mapped to |page_url| to the favicon at |icon_url|
1875  // till the limit of |kMaxFaviconBitmapsPerIconURL| is reached.
1876  for (size_t i = 0; i < icon_mappings.size(); ++i) {
1877    if (favicon_sizes.size() >= kMaxFaviconBitmapsPerIconURL)
1878      break;
1879
1880    if (icon_mappings[i].icon_url == icon_url)
1881      continue;
1882
1883    std::vector<FaviconBitmap> bitmaps_to_copy;
1884    thumbnail_db_->GetFaviconBitmaps(icon_mappings[i].icon_id,
1885                                     &bitmaps_to_copy);
1886    for (size_t j = 0; j < bitmaps_to_copy.size(); ++j) {
1887      // Do not add a favicon bitmap at a pixel size for which there is already
1888      // a favicon bitmap mapped to |icon_url|. The one there is more correct
1889      // and having multiple equally sized favicon bitmaps for |page_url| is
1890      // ambiguous in terms of GetFaviconsForURL().
1891      std::vector<gfx::Size>::iterator it = std::find(favicon_sizes.begin(),
1892          favicon_sizes.end(), bitmaps_to_copy[j].pixel_size);
1893      if (it != favicon_sizes.end())
1894        continue;
1895
1896      // Add the favicon bitmap as expired as it is not consistent with the
1897      // merged in data.
1898      thumbnail_db_->AddFaviconBitmap(favicon_id,
1899          bitmaps_to_copy[j].bitmap_data, base::Time(),
1900          bitmaps_to_copy[j].pixel_size);
1901      favicon_sizes.push_back(bitmaps_to_copy[j].pixel_size);
1902
1903      if (favicon_sizes.size() >= kMaxFaviconBitmapsPerIconURL)
1904        break;
1905    }
1906  }
1907
1908  // Update the favicon mappings such that only |icon_url| is mapped to
1909  // |page_url|.
1910  bool mapping_changed = false;
1911  if (icon_mappings.size() != 1 || icon_mappings[0].icon_url != icon_url) {
1912    std::vector<chrome::FaviconID> favicon_ids;
1913    favicon_ids.push_back(favicon_id);
1914    SetFaviconMappingsForPageAndRedirects(page_url, icon_type, favicon_ids);
1915    mapping_changed = true;
1916  }
1917
1918  if (mapping_changed || !bitmap_identical)
1919    SendFaviconChangedNotificationForPageAndRedirects(page_url);
1920  ScheduleCommit();
1921}
1922
1923void HistoryBackend::SetFavicons(
1924    const GURL& page_url,
1925    chrome::IconType icon_type,
1926    const std::vector<chrome::FaviconBitmapData>& favicon_bitmap_data) {
1927  if (!thumbnail_db_ || !db_)
1928    return;
1929
1930  DCHECK(ValidateSetFaviconsParams(favicon_bitmap_data));
1931
1932  // Build map of FaviconBitmapData for each icon url.
1933  typedef std::map<GURL, std::vector<chrome::FaviconBitmapData> >
1934      BitmapDataByIconURL;
1935  BitmapDataByIconURL grouped_by_icon_url;
1936  for (size_t i = 0; i < favicon_bitmap_data.size(); ++i) {
1937    const GURL& icon_url = favicon_bitmap_data[i].icon_url;
1938    grouped_by_icon_url[icon_url].push_back(favicon_bitmap_data[i]);
1939  }
1940
1941  // Track whether the method modifies or creates any favicon bitmaps, favicons
1942  // or icon mappings.
1943  bool data_modified = false;
1944
1945  std::vector<chrome::FaviconID> icon_ids;
1946  for (BitmapDataByIconURL::const_iterator it = grouped_by_icon_url.begin();
1947       it != grouped_by_icon_url.end(); ++it) {
1948    const GURL& icon_url = it->first;
1949    chrome::FaviconID icon_id =
1950        thumbnail_db_->GetFaviconIDForFaviconURL(icon_url, icon_type, NULL);
1951
1952    if (!icon_id) {
1953      // TODO(pkotwicz): Remove the favicon sizes attribute from
1954      // ThumbnailDatabase::AddFavicon().
1955      icon_id = thumbnail_db_->AddFavicon(icon_url, icon_type);
1956      data_modified = true;
1957    }
1958    icon_ids.push_back(icon_id);
1959
1960    if (!data_modified)
1961      SetFaviconBitmaps(icon_id, it->second, &data_modified);
1962    else
1963      SetFaviconBitmaps(icon_id, it->second, NULL);
1964  }
1965
1966  data_modified |=
1967    SetFaviconMappingsForPageAndRedirects(page_url, icon_type, icon_ids);
1968
1969  if (data_modified) {
1970    // Send notification to the UI as an icon mapping, favicon, or favicon
1971    // bitmap was changed by this function.
1972    SendFaviconChangedNotificationForPageAndRedirects(page_url);
1973  }
1974  ScheduleCommit();
1975}
1976
1977void HistoryBackend::SetFaviconsOutOfDateForPage(const GURL& page_url) {
1978  std::vector<IconMapping> icon_mappings;
1979
1980  if (!thumbnail_db_ ||
1981      !thumbnail_db_->GetIconMappingsForPageURL(page_url,
1982                                                &icon_mappings))
1983    return;
1984
1985  for (std::vector<IconMapping>::iterator m = icon_mappings.begin();
1986       m != icon_mappings.end(); ++m) {
1987    thumbnail_db_->SetFaviconOutOfDate(m->icon_id);
1988  }
1989  ScheduleCommit();
1990}
1991
1992void HistoryBackend::CloneFavicons(const GURL& old_page_url,
1993                                   const GURL& new_page_url) {
1994  if (!thumbnail_db_)
1995    return;
1996
1997  // Prevent cross-domain cloning.
1998  if (old_page_url.GetOrigin() != new_page_url.GetOrigin())
1999    return;
2000
2001  thumbnail_db_->CloneIconMappings(old_page_url, new_page_url);
2002  ScheduleCommit();
2003}
2004
2005void HistoryBackend::SetImportedFavicons(
2006    const std::vector<ImportedFaviconUsage>& favicon_usage) {
2007  if (!db_ || !thumbnail_db_)
2008    return;
2009
2010  Time now = Time::Now();
2011
2012  // Track all URLs that had their favicons set or updated.
2013  std::set<GURL> favicons_changed;
2014
2015  for (size_t i = 0; i < favicon_usage.size(); i++) {
2016    chrome::FaviconID favicon_id = thumbnail_db_->GetFaviconIDForFaviconURL(
2017        favicon_usage[i].favicon_url, chrome::FAVICON, NULL);
2018    if (!favicon_id) {
2019      // This favicon doesn't exist yet, so we create it using the given data.
2020      // TODO(pkotwicz): Pass in real pixel size.
2021      favicon_id = thumbnail_db_->AddFavicon(
2022          favicon_usage[i].favicon_url,
2023          chrome::FAVICON,
2024          new base::RefCountedBytes(favicon_usage[i].png_data),
2025          now,
2026          gfx::Size());
2027    }
2028
2029    // Save the mapping from all the URLs to the favicon.
2030    BookmarkService* bookmark_service = GetBookmarkService();
2031    for (std::set<GURL>::const_iterator url = favicon_usage[i].urls.begin();
2032         url != favicon_usage[i].urls.end(); ++url) {
2033      URLRow url_row;
2034      if (!db_->GetRowForURL(*url, &url_row)) {
2035        // If the URL is present as a bookmark, add the url in history to
2036        // save the favicon mapping. This will match with what history db does
2037        // for regular bookmarked URLs with favicons - when history db is
2038        // cleaned, we keep an entry in the db with 0 visits as long as that
2039        // url is bookmarked.
2040        if (bookmark_service && bookmark_service_->IsBookmarked(*url)) {
2041          URLRow url_info(*url);
2042          url_info.set_visit_count(0);
2043          url_info.set_typed_count(0);
2044          url_info.set_last_visit(base::Time());
2045          url_info.set_hidden(false);
2046          db_->AddURL(url_info);
2047          thumbnail_db_->AddIconMapping(*url, favicon_id);
2048          favicons_changed.insert(*url);
2049        }
2050      } else {
2051        if (!thumbnail_db_->GetIconMappingsForPageURL(
2052                *url, chrome::FAVICON, NULL)) {
2053          // URL is present in history, update the favicon *only* if it is not
2054          // set already.
2055          thumbnail_db_->AddIconMapping(*url, favicon_id);
2056          favicons_changed.insert(*url);
2057        }
2058      }
2059    }
2060  }
2061
2062  if (!favicons_changed.empty()) {
2063    // Send the notification about the changed favicon URLs.
2064    scoped_ptr<FaviconChangedDetails> changed_details(
2065        new FaviconChangedDetails);
2066    changed_details->urls.swap(favicons_changed);
2067    BroadcastNotifications(chrome::NOTIFICATION_FAVICON_CHANGED,
2068                           changed_details.PassAs<HistoryDetails>());
2069  }
2070}
2071
2072void HistoryBackend::UpdateFaviconMappingsAndFetchImpl(
2073    const GURL* page_url,
2074    const std::vector<GURL>& icon_urls,
2075    int icon_types,
2076    int desired_size_in_dip,
2077    const std::vector<ui::ScaleFactor>& desired_scale_factors,
2078    std::vector<chrome::FaviconBitmapResult>* bitmap_results) {
2079  // If |page_url| is specified, |icon_types| must be either a single icon
2080  // type or icon types which are equivalent.
2081  DCHECK(!page_url ||
2082         icon_types == chrome::FAVICON ||
2083         icon_types == chrome::TOUCH_ICON ||
2084         icon_types == chrome::TOUCH_PRECOMPOSED_ICON ||
2085         icon_types == (chrome::TOUCH_ICON | chrome::TOUCH_PRECOMPOSED_ICON));
2086  bitmap_results->clear();
2087
2088  if (!thumbnail_db_) {
2089    return;
2090  }
2091
2092  std::vector<chrome::FaviconID> favicon_ids;
2093
2094  // The icon type for which the mappings will the updated and data will be
2095  // returned.
2096  chrome::IconType selected_icon_type = chrome::INVALID_ICON;
2097
2098  for (size_t i = 0; i < icon_urls.size(); ++i) {
2099    const GURL& icon_url = icon_urls[i];
2100    chrome::IconType icon_type_out;
2101    const chrome::FaviconID favicon_id =
2102        thumbnail_db_->GetFaviconIDForFaviconURL(
2103            icon_url, icon_types, &icon_type_out);
2104
2105    if (favicon_id) {
2106      // Return and update icon mappings only for the largest icon type. As
2107      // |icon_urls| is not sorted in terms of icon type, clear |favicon_ids|
2108      // if an |icon_url| with a larger icon type is found.
2109      if (icon_type_out > selected_icon_type) {
2110        selected_icon_type = icon_type_out;
2111        favicon_ids.clear();
2112      }
2113      if (icon_type_out == selected_icon_type)
2114        favicon_ids.push_back(favicon_id);
2115    }
2116  }
2117
2118  if (page_url && !favicon_ids.empty()) {
2119    bool mappings_updated =
2120        SetFaviconMappingsForPageAndRedirects(*page_url, selected_icon_type,
2121                                              favicon_ids);
2122    if (mappings_updated) {
2123      SendFaviconChangedNotificationForPageAndRedirects(*page_url);
2124      ScheduleCommit();
2125    }
2126  }
2127
2128  GetFaviconBitmapResultsForBestMatch(favicon_ids, desired_size_in_dip,
2129      desired_scale_factors, bitmap_results);
2130}
2131
2132void HistoryBackend::SetFaviconBitmaps(
2133    chrome::FaviconID icon_id,
2134    const std::vector<chrome::FaviconBitmapData>& favicon_bitmap_data,
2135    bool* favicon_bitmaps_changed) {
2136  if (favicon_bitmaps_changed)
2137    *favicon_bitmaps_changed = false;
2138
2139  std::vector<FaviconBitmapIDSize> bitmap_id_sizes;
2140  thumbnail_db_->GetFaviconBitmapIDSizes(icon_id, &bitmap_id_sizes);
2141
2142  std::vector<chrome::FaviconBitmapData> to_add = favicon_bitmap_data;
2143
2144  for (size_t i = 0; i < bitmap_id_sizes.size(); ++i) {
2145    const gfx::Size& pixel_size = bitmap_id_sizes[i].pixel_size;
2146    std::vector<chrome::FaviconBitmapData>::iterator match_it = to_add.end();
2147    for (std::vector<chrome::FaviconBitmapData>::iterator it = to_add.begin();
2148         it != to_add.end(); ++it) {
2149      if (it->pixel_size == pixel_size) {
2150        match_it = it;
2151        break;
2152      }
2153    }
2154
2155    FaviconBitmapID bitmap_id = bitmap_id_sizes[i].bitmap_id;
2156    if (match_it == to_add.end()) {
2157      thumbnail_db_->DeleteFaviconBitmap(bitmap_id);
2158
2159      if (favicon_bitmaps_changed)
2160        *favicon_bitmaps_changed = true;
2161    } else {
2162      if (favicon_bitmaps_changed &&
2163          !*favicon_bitmaps_changed &&
2164          IsFaviconBitmapDataEqual(bitmap_id, match_it->bitmap_data)) {
2165        thumbnail_db_->SetFaviconBitmapLastUpdateTime(
2166            bitmap_id, base::Time::Now());
2167      } else {
2168        thumbnail_db_->SetFaviconBitmap(bitmap_id, match_it->bitmap_data,
2169            base::Time::Now());
2170
2171        if (favicon_bitmaps_changed)
2172          *favicon_bitmaps_changed = true;
2173      }
2174      to_add.erase(match_it);
2175    }
2176  }
2177
2178  for (size_t i = 0; i < to_add.size(); ++i) {
2179    thumbnail_db_->AddFaviconBitmap(icon_id, to_add[i].bitmap_data,
2180        base::Time::Now(), to_add[i].pixel_size);
2181
2182    if (favicon_bitmaps_changed)
2183      *favicon_bitmaps_changed = true;
2184  }
2185}
2186
2187bool HistoryBackend::ValidateSetFaviconsParams(
2188    const std::vector<chrome::FaviconBitmapData>& favicon_bitmap_data) const {
2189  typedef std::map<GURL, size_t> BitmapsPerIconURL;
2190  BitmapsPerIconURL num_bitmaps_per_icon_url;
2191  for (size_t i = 0; i < favicon_bitmap_data.size(); ++i) {
2192    if (!favicon_bitmap_data[i].bitmap_data.get())
2193      return false;
2194
2195    const GURL& icon_url = favicon_bitmap_data[i].icon_url;
2196    if (!num_bitmaps_per_icon_url.count(icon_url))
2197      num_bitmaps_per_icon_url[icon_url] = 1u;
2198    else
2199      ++num_bitmaps_per_icon_url[icon_url];
2200  }
2201
2202  if (num_bitmaps_per_icon_url.size() > kMaxFaviconsPerPage)
2203    return false;
2204
2205  for (BitmapsPerIconURL::const_iterator it = num_bitmaps_per_icon_url.begin();
2206       it != num_bitmaps_per_icon_url.end(); ++it) {
2207    if (it->second > kMaxFaviconBitmapsPerIconURL)
2208      return false;
2209  }
2210  return true;
2211}
2212
2213bool HistoryBackend::IsFaviconBitmapDataEqual(
2214    FaviconBitmapID bitmap_id,
2215    const scoped_refptr<base::RefCountedMemory>& new_bitmap_data) {
2216  if (!new_bitmap_data.get())
2217    return false;
2218
2219  scoped_refptr<base::RefCountedMemory> original_bitmap_data;
2220  thumbnail_db_->GetFaviconBitmap(bitmap_id,
2221                                  NULL,
2222                                  &original_bitmap_data,
2223                                  NULL);
2224  return new_bitmap_data->Equals(original_bitmap_data);
2225}
2226
2227bool HistoryBackend::GetFaviconsFromDB(
2228    const GURL& page_url,
2229    int icon_types,
2230    int desired_size_in_dip,
2231    const std::vector<ui::ScaleFactor>& desired_scale_factors,
2232    std::vector<chrome::FaviconBitmapResult>* favicon_bitmap_results) {
2233  DCHECK(favicon_bitmap_results);
2234  favicon_bitmap_results->clear();
2235
2236  if (!db_ || !thumbnail_db_)
2237    return false;
2238
2239  // Time the query.
2240  TimeTicks beginning_time = TimeTicks::Now();
2241
2242  // Get FaviconIDs for |page_url| and one of |icon_types|.
2243  std::vector<IconMapping> icon_mappings;
2244  thumbnail_db_->GetIconMappingsForPageURL(page_url, icon_types,
2245                                           &icon_mappings);
2246  std::vector<chrome::FaviconID> favicon_ids;
2247  for (size_t i = 0; i < icon_mappings.size(); ++i)
2248    favicon_ids.push_back(icon_mappings[i].icon_id);
2249
2250  // Populate |favicon_bitmap_results| and |icon_url_sizes|.
2251  bool success = GetFaviconBitmapResultsForBestMatch(favicon_ids,
2252      desired_size_in_dip, desired_scale_factors, favicon_bitmap_results);
2253  UMA_HISTOGRAM_TIMES("History.GetFavIconFromDB",  // historical name
2254                      TimeTicks::Now() - beginning_time);
2255  return success && !favicon_bitmap_results->empty();
2256}
2257
2258bool HistoryBackend::GetFaviconBitmapResultsForBestMatch(
2259    const std::vector<chrome::FaviconID>& candidate_favicon_ids,
2260    int desired_size_in_dip,
2261    const std::vector<ui::ScaleFactor>& desired_scale_factors,
2262    std::vector<chrome::FaviconBitmapResult>* favicon_bitmap_results) {
2263  favicon_bitmap_results->clear();
2264
2265  if (candidate_favicon_ids.empty())
2266    return true;
2267
2268  // Find the FaviconID and the FaviconBitmapIDs which best match
2269  // |desired_size_in_dip| and |desired_scale_factors|.
2270  // TODO(pkotwicz): Select bitmap results from multiple favicons once
2271  // content::FaviconStatus supports multiple icon URLs.
2272  chrome::FaviconID best_favicon_id = 0;
2273  std::vector<FaviconBitmapID> best_bitmap_ids;
2274  float highest_score = kSelectFaviconFramesInvalidScore;
2275  for (size_t i = 0; i < candidate_favicon_ids.size(); ++i) {
2276    std::vector<FaviconBitmapIDSize> bitmap_id_sizes;
2277    thumbnail_db_->GetFaviconBitmapIDSizes(candidate_favicon_ids[i],
2278                                           &bitmap_id_sizes);
2279
2280    // Build vector of gfx::Size from |bitmap_id_sizes|.
2281    std::vector<gfx::Size> sizes;
2282    for (size_t j = 0; j < bitmap_id_sizes.size(); ++j)
2283      sizes.push_back(bitmap_id_sizes[j].pixel_size);
2284
2285    std::vector<size_t> candidate_bitmap_indices;
2286    float score = 0;
2287    SelectFaviconFrameIndices(sizes,
2288                              desired_scale_factors,
2289                              desired_size_in_dip,
2290                              &candidate_bitmap_indices,
2291                              &score);
2292    if (score > highest_score) {
2293      highest_score = score;
2294      best_favicon_id = candidate_favicon_ids[i],
2295      best_bitmap_ids.clear();
2296      for (size_t j = 0; j < candidate_bitmap_indices.size(); ++j) {
2297        size_t candidate_index = candidate_bitmap_indices[j];
2298        best_bitmap_ids.push_back(
2299            bitmap_id_sizes[candidate_index].bitmap_id);
2300      }
2301    }
2302  }
2303
2304  // Construct FaviconBitmapResults from |best_favicon_id| and
2305  // |best_bitmap_ids|.
2306  GURL icon_url;
2307  chrome::IconType icon_type;
2308  if (!thumbnail_db_->GetFaviconHeader(best_favicon_id, &icon_url,
2309                                       &icon_type)) {
2310    return false;
2311  }
2312
2313  for (size_t i = 0; i < best_bitmap_ids.size(); ++i) {
2314    base::Time last_updated;
2315    chrome::FaviconBitmapResult bitmap_result;
2316    bitmap_result.icon_url = icon_url;
2317    bitmap_result.icon_type = icon_type;
2318    if (!thumbnail_db_->GetFaviconBitmap(best_bitmap_ids[i],
2319                                         &last_updated,
2320                                         &bitmap_result.bitmap_data,
2321                                         &bitmap_result.pixel_size)) {
2322      return false;
2323    }
2324
2325    bitmap_result.expired = (Time::Now() - last_updated) >
2326        TimeDelta::FromDays(kFaviconRefetchDays);
2327    if (bitmap_result.is_valid())
2328      favicon_bitmap_results->push_back(bitmap_result);
2329  }
2330  return true;
2331}
2332
2333bool HistoryBackend::SetFaviconMappingsForPageAndRedirects(
2334    const GURL& page_url,
2335    chrome::IconType icon_type,
2336    const std::vector<chrome::FaviconID>& icon_ids) {
2337  if (!thumbnail_db_)
2338    return false;
2339
2340  // Find all the pages whose favicons we should set, we want to set it for
2341  // all the pages in the redirect chain if it redirected.
2342  history::RedirectList redirects;
2343  GetCachedRecentRedirects(page_url, &redirects);
2344
2345  bool mappings_changed = false;
2346
2347  // Save page <-> favicon associations.
2348  for (history::RedirectList::const_iterator i(redirects.begin());
2349       i != redirects.end(); ++i) {
2350    mappings_changed |= SetFaviconMappingsForPage(*i, icon_type, icon_ids);
2351  }
2352  return mappings_changed;
2353}
2354
2355bool HistoryBackend::SetFaviconMappingsForPage(
2356    const GURL& page_url,
2357    chrome::IconType icon_type,
2358    const std::vector<chrome::FaviconID>& icon_ids) {
2359  DCHECK_LE(icon_ids.size(), kMaxFaviconsPerPage);
2360  bool mappings_changed = false;
2361
2362  // Two icon types are considered 'equivalent' if one of the icon types is
2363  // TOUCH_ICON and the other is TOUCH_PRECOMPOSED_ICON.
2364  //
2365  // Sets the icon mappings from |page_url| for |icon_type| to the favicons
2366  // with |icon_ids|. Mappings for |page_url| to favicons of type |icon_type|
2367  // whose FaviconID is not in |icon_ids| are removed. All icon mappings for
2368  // |page_url| to favicons of a type equivalent to |icon_type| are removed.
2369  // Remove any favicons which are orphaned as a result of the removal of the
2370  // icon mappings.
2371
2372  std::vector<chrome::FaviconID> unmapped_icon_ids = icon_ids;
2373
2374  std::vector<IconMapping> icon_mappings;
2375  thumbnail_db_->GetIconMappingsForPageURL(page_url, &icon_mappings);
2376
2377  for (std::vector<IconMapping>::iterator m = icon_mappings.begin();
2378       m != icon_mappings.end(); ++m) {
2379    std::vector<chrome::FaviconID>::iterator icon_id_it = std::find(
2380        unmapped_icon_ids.begin(), unmapped_icon_ids.end(), m->icon_id);
2381
2382    // If the icon mapping already exists, avoid removing it and adding it back.
2383    if (icon_id_it != unmapped_icon_ids.end()) {
2384      unmapped_icon_ids.erase(icon_id_it);
2385      continue;
2386    }
2387
2388    if ((icon_type == chrome::TOUCH_ICON &&
2389         m->icon_type == chrome::TOUCH_PRECOMPOSED_ICON) ||
2390        (icon_type == chrome::TOUCH_PRECOMPOSED_ICON &&
2391         m->icon_type == chrome::TOUCH_ICON) || (icon_type == m->icon_type)) {
2392      thumbnail_db_->DeleteIconMapping(m->mapping_id);
2393
2394      // Removing the icon mapping may have orphaned the associated favicon so
2395      // we must recheck it. This is not super fast, but this case will get
2396      // triggered rarely, since normally a page will always map to the same
2397      // favicon IDs. It will mostly happen for favicons we import.
2398      if (!thumbnail_db_->HasMappingFor(m->icon_id))
2399        thumbnail_db_->DeleteFavicon(m->icon_id);
2400      mappings_changed = true;
2401    }
2402  }
2403
2404  for (size_t i = 0; i < unmapped_icon_ids.size(); ++i) {
2405    thumbnail_db_->AddIconMapping(page_url, unmapped_icon_ids[i]);
2406    mappings_changed = true;
2407  }
2408  return mappings_changed;
2409}
2410
2411void HistoryBackend::GetCachedRecentRedirects(
2412    const GURL& page_url,
2413    history::RedirectList* redirect_list) {
2414  RedirectCache::iterator iter = recent_redirects_.Get(page_url);
2415  if (iter != recent_redirects_.end()) {
2416    *redirect_list = iter->second;
2417
2418    // The redirect chain should have the destination URL as the last item.
2419    DCHECK(!redirect_list->empty());
2420    DCHECK(redirect_list->back() == page_url);
2421  } else {
2422    // No known redirects, construct mock redirect chain containing |page_url|.
2423    redirect_list->push_back(page_url);
2424  }
2425}
2426
2427void HistoryBackend::SendFaviconChangedNotificationForPageAndRedirects(
2428    const GURL& page_url) {
2429  history::RedirectList redirect_list;
2430  GetCachedRecentRedirects(page_url, &redirect_list);
2431
2432  scoped_ptr<FaviconChangedDetails> changed_details(new FaviconChangedDetails);
2433  for (size_t i = 0; i < redirect_list.size(); ++i)
2434    changed_details->urls.insert(redirect_list[i]);
2435
2436  BroadcastNotifications(chrome::NOTIFICATION_FAVICON_CHANGED,
2437                         changed_details.PassAs<HistoryDetails>());
2438}
2439
2440void HistoryBackend::Commit() {
2441  if (!db_)
2442    return;
2443
2444  // Note that a commit may not actually have been scheduled if a caller
2445  // explicitly calls this instead of using ScheduleCommit. Likewise, we
2446  // may reset the flag written by a pending commit. But this is OK! It
2447  // will merely cause extra commits (which is kind of the idea). We
2448  // could optimize more for this case (we may get two extra commits in
2449  // some cases) but it hasn't been important yet.
2450  CancelScheduledCommit();
2451
2452  db_->CommitTransaction();
2453  DCHECK(db_->transaction_nesting() == 0) << "Somebody left a transaction open";
2454  db_->BeginTransaction();
2455
2456  if (thumbnail_db_) {
2457    thumbnail_db_->CommitTransaction();
2458    DCHECK(thumbnail_db_->transaction_nesting() == 0) <<
2459        "Somebody left a transaction open";
2460    thumbnail_db_->BeginTransaction();
2461  }
2462
2463  if (archived_db_) {
2464    archived_db_->CommitTransaction();
2465    archived_db_->BeginTransaction();
2466  }
2467}
2468
2469void HistoryBackend::ScheduleCommit() {
2470  if (scheduled_commit_.get())
2471    return;
2472  scheduled_commit_ = new CommitLaterTask(this);
2473  base::MessageLoop::current()->PostDelayedTask(
2474      FROM_HERE,
2475      base::Bind(&CommitLaterTask::RunCommit, scheduled_commit_.get()),
2476      base::TimeDelta::FromSeconds(kCommitIntervalSeconds));
2477}
2478
2479void HistoryBackend::CancelScheduledCommit() {
2480  if (scheduled_commit_.get()) {
2481    scheduled_commit_->Cancel();
2482    scheduled_commit_ = NULL;
2483  }
2484}
2485
2486void HistoryBackend::ProcessDBTaskImpl() {
2487  if (!db_) {
2488    // db went away, release all the refs.
2489    ReleaseDBTasks();
2490    return;
2491  }
2492
2493  // Remove any canceled tasks.
2494  while (!db_task_requests_.empty() && db_task_requests_.front()->canceled()) {
2495    db_task_requests_.front()->Release();
2496    db_task_requests_.pop_front();
2497  }
2498  if (db_task_requests_.empty())
2499    return;
2500
2501  // Run the first task.
2502  HistoryDBTaskRequest* request = db_task_requests_.front();
2503  db_task_requests_.pop_front();
2504  if (request->value->RunOnDBThread(this, db_.get())) {
2505    // The task is done. Notify the callback.
2506    request->ForwardResult();
2507    // We AddRef'd the request before adding, need to release it now.
2508    request->Release();
2509  } else {
2510    // Tasks wants to run some more. Schedule it at the end of current tasks.
2511    db_task_requests_.push_back(request);
2512    // And process it after an invoke later.
2513    base::MessageLoop::current()->PostTask(
2514        FROM_HERE, base::Bind(&HistoryBackend::ProcessDBTaskImpl, this));
2515  }
2516}
2517
2518void HistoryBackend::ReleaseDBTasks() {
2519  for (std::list<HistoryDBTaskRequest*>::iterator i =
2520       db_task_requests_.begin(); i != db_task_requests_.end(); ++i) {
2521    (*i)->Release();
2522  }
2523  db_task_requests_.clear();
2524}
2525
2526////////////////////////////////////////////////////////////////////////////////
2527//
2528// Generic operations
2529//
2530////////////////////////////////////////////////////////////////////////////////
2531
2532void HistoryBackend::DeleteURLs(const std::vector<GURL>& urls) {
2533  expirer_.DeleteURLs(urls);
2534
2535  db_->GetStartDate(&first_recorded_time_);
2536  // Force a commit, if the user is deleting something for privacy reasons, we
2537  // want to get it on disk ASAP.
2538  Commit();
2539}
2540
2541void HistoryBackend::DeleteURL(const GURL& url) {
2542  expirer_.DeleteURL(url);
2543
2544  db_->GetStartDate(&first_recorded_time_);
2545  // Force a commit, if the user is deleting something for privacy reasons, we
2546  // want to get it on disk ASAP.
2547  Commit();
2548}
2549
2550void HistoryBackend::ExpireHistoryBetween(
2551    const std::set<GURL>& restrict_urls,
2552    Time begin_time,
2553    Time end_time) {
2554  if (!db_)
2555    return;
2556
2557  if (begin_time.is_null() && (end_time.is_null() || end_time.is_max()) &&
2558      restrict_urls.empty()) {
2559    // Special case deleting all history so it can be faster and to reduce the
2560    // possibility of an information leak.
2561    DeleteAllHistory();
2562  } else {
2563    // Clearing parts of history, have the expirer do the depend
2564    expirer_.ExpireHistoryBetween(restrict_urls, begin_time, end_time);
2565
2566    // Force a commit, if the user is deleting something for privacy reasons,
2567    // we want to get it on disk ASAP.
2568    Commit();
2569  }
2570
2571  if (begin_time <= first_recorded_time_)
2572    db_->GetStartDate(&first_recorded_time_);
2573}
2574
2575void HistoryBackend::ExpireHistoryForTimes(
2576    const std::set<base::Time>& times,
2577    base::Time begin_time, base::Time end_time) {
2578  if (times.empty() || !db_)
2579    return;
2580
2581  DCHECK(*times.begin() >= begin_time)
2582      << "Min time is before begin time: "
2583      << times.begin()->ToJsTime() << " v.s. " << begin_time.ToJsTime();
2584  DCHECK(*times.rbegin() < end_time)
2585      << "Max time is after end time: "
2586      << times.rbegin()->ToJsTime() << " v.s. " << end_time.ToJsTime();
2587
2588  history::QueryOptions options;
2589  options.begin_time = begin_time;
2590  options.end_time = end_time;
2591  options.duplicate_policy = QueryOptions::KEEP_ALL_DUPLICATES;
2592  QueryResults results;
2593  QueryHistoryBasic(db_.get(), db_.get(), options, &results);
2594
2595  // 1st pass: find URLs that are visited at one of |times|.
2596  std::set<GURL> urls;
2597  for (size_t i = 0; i < results.size(); ++i) {
2598    if (times.count(results[i].visit_time()) > 0)
2599      urls.insert(results[i].url());
2600  }
2601  if (urls.empty())
2602    return;
2603
2604  // 2nd pass: collect all visit times of those URLs.
2605  std::vector<base::Time> times_to_expire;
2606  for (size_t i = 0; i < results.size(); ++i) {
2607    if (urls.count(results[i].url()))
2608      times_to_expire.push_back(results[i].visit_time());
2609  }
2610
2611  // Put the times in reverse chronological order and remove
2612  // duplicates (for expirer_.ExpireHistoryForTimes()).
2613  std::sort(times_to_expire.begin(), times_to_expire.end(),
2614            std::greater<base::Time>());
2615  times_to_expire.erase(
2616      std::unique(times_to_expire.begin(), times_to_expire.end()),
2617      times_to_expire.end());
2618
2619  // Expires by times and commit.
2620  DCHECK(!times_to_expire.empty());
2621  expirer_.ExpireHistoryForTimes(times_to_expire);
2622  Commit();
2623
2624  DCHECK(times_to_expire.back() >= first_recorded_time_);
2625  // Update |first_recorded_time_| if we expired it.
2626  if (times_to_expire.back() == first_recorded_time_)
2627    db_->GetStartDate(&first_recorded_time_);
2628}
2629
2630void HistoryBackend::ExpireHistory(
2631    const std::vector<history::ExpireHistoryArgs>& expire_list) {
2632  if (db_) {
2633    bool update_first_recorded_time = false;
2634
2635    for (std::vector<history::ExpireHistoryArgs>::const_iterator it =
2636         expire_list.begin(); it != expire_list.end(); ++it) {
2637      expirer_.ExpireHistoryBetween(it->urls, it->begin_time, it->end_time);
2638
2639      if (it->begin_time < first_recorded_time_)
2640        update_first_recorded_time = true;
2641    }
2642    Commit();
2643
2644    // Update |first_recorded_time_| if any deletion might have affected it.
2645    if (update_first_recorded_time)
2646      db_->GetStartDate(&first_recorded_time_);
2647  }
2648}
2649
2650void HistoryBackend::URLsNoLongerBookmarked(const std::set<GURL>& urls) {
2651  if (!db_)
2652    return;
2653
2654  for (std::set<GURL>::const_iterator i = urls.begin(); i != urls.end(); ++i) {
2655    URLRow url_row;
2656    if (!db_->GetRowForURL(*i, &url_row))
2657      continue;  // The URL isn't in the db; nothing to do.
2658
2659    VisitVector visits;
2660    db_->GetVisitsForURL(url_row.id(), &visits);
2661
2662    if (visits.empty())
2663      expirer_.DeleteURL(*i);  // There are no more visits; nuke the URL.
2664  }
2665}
2666
2667void HistoryBackend::DatabaseErrorCallback(int error, sql::Statement* stmt) {
2668  if (!scheduled_kill_db_ && sql::IsErrorCatastrophic(error)) {
2669    scheduled_kill_db_ = true;
2670    // Don't just do the close/delete here, as we are being called by |db| and
2671    // that seems dangerous.
2672    // TODO(shess): Consider changing KillHistoryDatabase() to use
2673    // RazeAndClose().  Then it can be cleared immediately.
2674    base::MessageLoop::current()->PostTask(
2675        FROM_HERE,
2676        base::Bind(&HistoryBackend::KillHistoryDatabase, this));
2677  }
2678}
2679
2680void HistoryBackend::KillHistoryDatabase() {
2681  scheduled_kill_db_ = false;
2682  if (!db_)
2683    return;
2684
2685  // Rollback transaction because Raze() cannot be called from within a
2686  // transaction.
2687  db_->RollbackTransaction();
2688  bool success = db_->Raze();
2689  UMA_HISTOGRAM_BOOLEAN("History.KillHistoryDatabaseResult", success);
2690
2691#if defined(OS_ANDROID)
2692  // Release AndroidProviderBackend before other objects.
2693  android_provider_backend_.reset();
2694#endif
2695
2696  // The expirer keeps tabs on the active databases. Tell it about the
2697  // databases which will be closed.
2698  expirer_.SetDatabases(NULL, NULL, NULL);
2699
2700  // Reopen a new transaction for |db_| for the sake of CloseAllDatabases().
2701  db_->BeginTransaction();
2702  CloseAllDatabases();
2703}
2704
2705void HistoryBackend::ProcessDBTask(
2706    scoped_refptr<HistoryDBTaskRequest> request) {
2707  DCHECK(request.get());
2708  if (request->canceled())
2709    return;
2710
2711  bool task_scheduled = !db_task_requests_.empty();
2712  // Make sure we up the refcount of the request. ProcessDBTaskImpl will
2713  // release when done with the task.
2714  request->AddRef();
2715  db_task_requests_.push_back(request.get());
2716  if (!task_scheduled) {
2717    // No other tasks are scheduled. Process request now.
2718    ProcessDBTaskImpl();
2719  }
2720}
2721
2722void HistoryBackend::BroadcastNotifications(
2723    int type,
2724    scoped_ptr<HistoryDetails> details) {
2725  // |delegate_| may be NULL if |this| is in the process of closing (closed by
2726  // HistoryService -> HistoryBackend::Closing().
2727  if (delegate_)
2728    delegate_->BroadcastNotifications(type, details.Pass());
2729}
2730
2731void HistoryBackend::NotifySyncURLsDeleted(bool all_history,
2732                                           bool archived,
2733                                           URLRows* rows) {
2734  if (typed_url_syncable_service_.get())
2735    typed_url_syncable_service_->OnUrlsDeleted(all_history, archived, rows);
2736}
2737
2738// Deleting --------------------------------------------------------------------
2739
2740void HistoryBackend::DeleteAllHistory() {
2741  // Our approach to deleting all history is:
2742  //  1. Copy the bookmarks and their dependencies to new tables with temporary
2743  //     names.
2744  //  2. Delete the original tables. Since tables can not share pages, we know
2745  //     that any data we don't want to keep is now in an unused page.
2746  //  3. Renaming the temporary tables to match the original.
2747  //  4. Vacuuming the database to delete the unused pages.
2748  //
2749  // Since we are likely to have very few bookmarks and their dependencies
2750  // compared to all history, this is also much faster than just deleting from
2751  // the original tables directly.
2752
2753  // Get the bookmarked URLs.
2754  std::vector<BookmarkService::URLAndTitle> starred_urls;
2755  BookmarkService* bookmark_service = GetBookmarkService();
2756  if (bookmark_service)
2757    bookmark_service_->GetBookmarks(&starred_urls);
2758
2759  URLRows kept_urls;
2760  for (size_t i = 0; i < starred_urls.size(); i++) {
2761    URLRow row;
2762    if (!db_->GetRowForURL(starred_urls[i].url, &row))
2763      continue;
2764
2765    // Clear the last visit time so when we write these rows they are "clean."
2766    row.set_last_visit(Time());
2767    row.set_visit_count(0);
2768    row.set_typed_count(0);
2769    kept_urls.push_back(row);
2770  }
2771
2772  // Clear thumbnail and favicon history. The favicons for the given URLs will
2773  // be kept.
2774  if (!ClearAllThumbnailHistory(kept_urls)) {
2775    LOG(ERROR) << "Thumbnail history could not be cleared";
2776    // We continue in this error case. If the user wants to delete their
2777    // history, we should delete as much as we can.
2778  }
2779
2780  // ClearAllMainHistory will change the IDs of the URLs in kept_urls.
2781  // Therefore, we clear the list afterwards to make sure nobody uses this
2782  // invalid data.
2783  if (!ClearAllMainHistory(kept_urls))
2784    LOG(ERROR) << "Main history could not be cleared";
2785  kept_urls.clear();
2786
2787  // Delete archived history.
2788  if (archived_db_) {
2789    // Close the database and delete the file.
2790    archived_db_.reset();
2791    base::FilePath archived_file_name = GetArchivedFileName();
2792    sql::Connection::Delete(archived_file_name);
2793
2794    // Now re-initialize the database (which may fail).
2795    archived_db_.reset(new ArchivedDatabase());
2796    if (!archived_db_->Init(archived_file_name)) {
2797      LOG(WARNING) << "Could not initialize the archived database.";
2798      archived_db_.reset();
2799    } else {
2800      // Open our long-running transaction on this database.
2801      archived_db_->BeginTransaction();
2802    }
2803  }
2804
2805  db_->GetStartDate(&first_recorded_time_);
2806
2807  // Send out the notification that history is cleared. The in-memory database
2808  // will pick this up and clear itself.
2809  scoped_ptr<URLsDeletedDetails> details(new URLsDeletedDetails);
2810  details->all_history = true;
2811  NotifySyncURLsDeleted(true, false, NULL);
2812  BroadcastNotifications(chrome::NOTIFICATION_HISTORY_URLS_DELETED,
2813                         details.PassAs<HistoryDetails>());
2814}
2815
2816bool HistoryBackend::ClearAllThumbnailHistory(const URLRows& kept_urls) {
2817  if (!thumbnail_db_) {
2818    // When we have no reference to the thumbnail database, maybe there was an
2819    // error opening it. In this case, we just try to blow it away to try to
2820    // fix the error if it exists. This may fail, in which case either the
2821    // file doesn't exist or there's no more we can do.
2822    sql::Connection::Delete(GetFaviconsFileName());
2823
2824    // Older version of the database.
2825    sql::Connection::Delete(GetThumbnailFileName());
2826    return true;
2827  }
2828
2829  // Urls to retain mappings for.
2830  std::vector<GURL> urls_to_keep;
2831  for (URLRows::const_iterator i = kept_urls.begin();
2832       i != kept_urls.end(); ++i) {
2833    urls_to_keep.push_back(i->url());
2834  }
2835
2836  // Isolate from any long-running transaction.
2837  thumbnail_db_->CommitTransaction();
2838  thumbnail_db_->BeginTransaction();
2839
2840  // TODO(shess): If this fails, perhaps the database should be razed
2841  // or deleted.
2842  if (!thumbnail_db_->RetainDataForPageUrls(urls_to_keep)) {
2843    thumbnail_db_->RollbackTransaction();
2844    thumbnail_db_->BeginTransaction();
2845    return false;
2846  }
2847
2848#if defined(OS_ANDROID)
2849  // TODO (michaelbai): Add the unit test once AndroidProviderBackend is
2850  // avaliable in HistoryBackend.
2851  db_->ClearAndroidURLRows();
2852#endif
2853
2854  // Vacuum to remove all the pages associated with the dropped tables. There
2855  // must be no transaction open on the table when we do this. We assume that
2856  // our long-running transaction is open, so we complete it and start it again.
2857  DCHECK(thumbnail_db_->transaction_nesting() == 1);
2858  thumbnail_db_->CommitTransaction();
2859  thumbnail_db_->Vacuum();
2860  thumbnail_db_->BeginTransaction();
2861  return true;
2862}
2863
2864bool HistoryBackend::ClearAllMainHistory(const URLRows& kept_urls) {
2865  // Create the duplicate URL table. We will copy the kept URLs into this.
2866  if (!db_->CreateTemporaryURLTable())
2867    return false;
2868
2869  // Insert the URLs into the temporary table.
2870  for (URLRows::const_iterator i = kept_urls.begin(); i != kept_urls.end();
2871       ++i) {
2872    db_->AddTemporaryURL(*i);
2873  }
2874
2875  // Replace the original URL table with the temporary one.
2876  if (!db_->CommitTemporaryURLTable())
2877    return false;
2878
2879  // Delete the old tables and recreate them empty.
2880  db_->RecreateAllTablesButURL();
2881
2882  // Vacuum to reclaim the space from the dropped tables. This must be done
2883  // when there is no transaction open, and we assume that our long-running
2884  // transaction is currently open.
2885  db_->CommitTransaction();
2886  db_->Vacuum();
2887  db_->BeginTransaction();
2888  db_->GetStartDate(&first_recorded_time_);
2889
2890  return true;
2891}
2892
2893BookmarkService* HistoryBackend::GetBookmarkService() {
2894  if (bookmark_service_)
2895    bookmark_service_->BlockTillLoaded();
2896  return bookmark_service_;
2897}
2898
2899void HistoryBackend::NotifyVisitObservers(const VisitRow& visit) {
2900  BriefVisitInfo info;
2901  info.url_id = visit.url_id;
2902  info.time = visit.visit_time;
2903  info.transition = visit.transition;
2904  // If we don't have a delegate yet during setup or shutdown, we will drop
2905  // these notifications.
2906  if (delegate_)
2907    delegate_->NotifyVisitDBObserversOnAddVisit(info);
2908}
2909
2910#if defined(OS_ANDROID)
2911void HistoryBackend::PopulateMostVisitedURLMap() {
2912  MostVisitedURLList most_visited_urls;
2913  QueryMostVisitedURLsImpl(kPageVisitStatsMaxTopSites, kSegmentDataRetention,
2914                           &most_visited_urls);
2915
2916  DCHECK_LE(most_visited_urls.size(), kPageVisitStatsMaxTopSites);
2917  for (size_t i = 0; i < most_visited_urls.size(); ++i) {
2918    most_visited_urls_map_[most_visited_urls[i].url] = i;
2919    for (size_t j = 0; j < most_visited_urls[i].redirects.size(); ++j)
2920      most_visited_urls_map_[most_visited_urls[i].redirects[j]] = i;
2921  }
2922}
2923
2924void HistoryBackend::RecordTopPageVisitStats(const GURL& url) {
2925  int rank = kPageVisitStatsMaxTopSites;
2926  std::map<GURL, int>::const_iterator it = most_visited_urls_map_.find(url);
2927  if (it != most_visited_urls_map_.end())
2928    rank = (*it).second;
2929  UMA_HISTOGRAM_ENUMERATION("History.TopSitesVisitsByRank",
2930                            rank, kPageVisitStatsMaxTopSites + 1);
2931}
2932#endif
2933
2934}  // namespace history
2935