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