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