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