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