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