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