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