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