Home | History | Annotate | Download | only in history 
      1 // Copyright (c) 2013 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/top_sites_impl.h"
      6 
      7 #include <algorithm>
      8 #include <set>
      9 
     10 #include "base/bind.h"
     11 #include "base/bind_helpers.h"
     12 #include "base/logging.h"
     13 #include "base/md5.h"
     14 #include "base/memory/ref_counted_memory.h"
     15 #include "base/message_loop/message_loop_proxy.h"
     16 #include "base/prefs/pref_service.h"
     17 #include "base/strings/string_util.h"
     18 #include "base/strings/utf_string_conversions.h"
     19 #include "base/task_runner.h"
     20 #include "base/values.h"
     21 #include "chrome/browser/chrome_notification_types.h"
     22 #include "chrome/browser/history/history_backend.h"
     23 #include "chrome/browser/history/history_db_task.h"
     24 #include "chrome/browser/history/history_notifications.h"
     25 #include "chrome/browser/history/history_service_factory.h"
     26 #include "chrome/browser/history/page_usage_data.h"
     27 #include "chrome/browser/history/top_sites_cache.h"
     28 #include "chrome/browser/prefs/scoped_user_pref_update.h"
     29 #include "chrome/browser/profiles/profile.h"
     30 #include "chrome/browser/ui/webui/ntp/most_visited_handler.h"
     31 #include "chrome/browser/ui/webui/ntp/new_tab_ui.h"
     32 #include "chrome/common/pref_names.h"
     33 #include "chrome/common/thumbnail_score.h"
     34 #include "content/public/browser/browser_thread.h"
     35 #include "content/public/browser/navigation_controller.h"
     36 #include "content/public/browser/navigation_details.h"
     37 #include "content/public/browser/navigation_entry.h"
     38 #include "content/public/browser/notification_service.h"
     39 #include "content/public/browser/web_contents.h"
     40 #include "grit/locale_settings.h"
     41 #include "ui/base/l10n/l10n_util.h"
     42 #include "ui/base/layout.h"
     43 #include "ui/base/resource/resource_bundle.h"
     44 #include "ui/gfx/image/image_util.h"
     45 
     46 using base::DictionaryValue;
     47 using content::BrowserThread;
     48 using content::NavigationController;
     49 
     50 namespace history {
     51 
     52 namespace {
     53 
     54 void RunOrPostGetMostVisitedURLsCallback(
     55     base::TaskRunner* task_runner,
     56     const TopSitesImpl::GetMostVisitedURLsCallback& callback,
     57     const MostVisitedURLList& urls) {
     58   if (task_runner->RunsTasksOnCurrentThread())
     59     callback.Run(urls);
     60   else
     61     task_runner->PostTask(FROM_HERE, base::Bind(callback, urls));
     62 }
     63 
     64 }  // namespace
     65 
     66 // How many top sites to store in the cache.
     67 static const size_t kTopSitesNumber = 20;
     68 
     69 // Max number of temporary images we'll cache. See comment above
     70 // temp_images_ for details.
     71 static const size_t kMaxTempTopImages = 8;
     72 
     73 static const int kDaysOfHistory = 90;
     74 // Time from startup to first HistoryService query.
     75 static const int64 kUpdateIntervalSecs = 15;
     76 // Intervals between requests to HistoryService.
     77 static const int64 kMinUpdateIntervalMinutes = 1;
     78 static const int64 kMaxUpdateIntervalMinutes = 60;
     79 
     80 // Use 100 quality (highest quality) because we're very sensitive to
     81 // artifacts for these small sized, highly detailed images.
     82 static const int kTopSitesImageQuality = 100;
     83 
     84 namespace {
     85 
     86 // HistoryDBTask used during migration of thumbnails from history to top sites.
     87 // When run on the history thread it collects the top sites and the
     88 // corresponding thumbnails. When run back on the ui thread it calls into
     89 // TopSitesImpl::FinishHistoryMigration.
     90 class LoadThumbnailsFromHistoryTask : public HistoryDBTask {
     91  public:
     92   LoadThumbnailsFromHistoryTask(TopSites* top_sites,
     93                                 int result_count)
     94       : top_sites_(top_sites),
     95         result_count_(result_count) {
     96     // l10n_util isn't thread safe, so cache for use on the db thread.
     97     ignore_urls_.insert(l10n_util::GetStringUTF8(IDS_CHROME_WELCOME_URL));
     98     ignore_urls_.insert(l10n_util::GetStringUTF8(IDS_WEBSTORE_URL));
     99 #if defined(OS_ANDROID)
    100     ignore_urls_.insert(l10n_util::GetStringUTF8(IDS_MOBILE_WELCOME_URL));
    101 #endif
    102   }
    103 
    104   virtual bool RunOnDBThread(history::HistoryBackend* backend,
    105                              history::HistoryDatabase* db) OVERRIDE {
    106     // Get the most visited urls.
    107     backend->QueryMostVisitedURLsImpl(result_count_,
    108                                       kDaysOfHistory,
    109                                       &data_.most_visited);
    110 
    111     // And fetch the thumbnails.
    112     for (size_t i = 0; i < data_.most_visited.size(); ++i) {
    113       const GURL& url = data_.most_visited[i].url;
    114       if (ShouldFetchThumbnailFor(url)) {
    115         scoped_refptr<base::RefCountedBytes> data;
    116         backend->GetPageThumbnailDirectly(url, &data);
    117         data_.url_to_thumbnail_map[url] = data;
    118       }
    119     }
    120     return true;
    121   }
    122 
    123   virtual void DoneRunOnMainThread() OVERRIDE {
    124     top_sites_->FinishHistoryMigration(data_);
    125   }
    126 
    127  private:
    128   virtual ~LoadThumbnailsFromHistoryTask() {}
    129 
    130   bool ShouldFetchThumbnailFor(const GURL& url) {
    131     return ignore_urls_.find(url.spec()) == ignore_urls_.end();
    132   }
    133 
    134   // Set of URLs we don't load thumbnails for. This is created on the UI thread
    135   // and used on the history thread.
    136   std::set<std::string> ignore_urls_;
    137 
    138   scoped_refptr<TopSites> top_sites_;
    139 
    140   // Number of results to request from history.
    141   const int result_count_;
    142 
    143   ThumbnailMigration data_;
    144 
    145   DISALLOW_COPY_AND_ASSIGN(LoadThumbnailsFromHistoryTask);
    146 };
    147 
    148 }  // namespace
    149 
    150 TopSitesImpl::TopSitesImpl(Profile* profile)
    151     : backend_(NULL),
    152       cache_(new TopSitesCache()),
    153       thread_safe_cache_(new TopSitesCache()),
    154       profile_(profile),
    155       last_num_urls_changed_(0),
    156       history_state_(HISTORY_LOADING),
    157       top_sites_state_(TOP_SITES_LOADING),
    158       loaded_(false) {
    159   if (!profile_)
    160     return;
    161 
    162   if (content::NotificationService::current()) {
    163     registrar_.Add(this, chrome::NOTIFICATION_HISTORY_URLS_DELETED,
    164                    content::Source<Profile>(profile_));
    165     // Listen for any nav commits. We'll ignore those not related to this
    166     // profile when we get the notification.
    167     registrar_.Add(this, content::NOTIFICATION_NAV_ENTRY_COMMITTED,
    168                    content::NotificationService::AllSources());
    169   }
    170   for (size_t i = 0; i < arraysize(kPrepopulatedPages); i++) {
    171     int url_id = kPrepopulatedPages[i].url_id;
    172     prepopulated_page_urls_.push_back(
    173         GURL(l10n_util::GetStringUTF8(url_id)));
    174   }
    175 }
    176 
    177 void TopSitesImpl::Init(const base::FilePath& db_name) {
    178   // Create the backend here, rather than in the constructor, so that
    179   // unit tests that do not need the backend can run without a problem.
    180   backend_ = new TopSitesBackend;
    181   backend_->Init(db_name);
    182   backend_->GetMostVisitedThumbnails(
    183       base::Bind(&TopSitesImpl::OnGotMostVisitedThumbnails,
    184                  base::Unretained(this)),
    185       &cancelable_task_tracker_);
    186 
    187   // History may have already finished loading by the time we're created.
    188   HistoryService* history =
    189       HistoryServiceFactory::GetForProfileWithoutCreating(profile_);
    190   if (history && history->backend_loaded()) {
    191     if (history->needs_top_sites_migration())
    192       MigrateFromHistory();
    193     else
    194       history_state_ = HISTORY_LOADED;
    195   }
    196 }
    197 
    198 bool TopSitesImpl::SetPageThumbnail(const GURL& url,
    199                                     const gfx::Image& thumbnail,
    200                                     const ThumbnailScore& score) {
    201   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    202 
    203   if (!loaded_) {
    204     // TODO(sky): I need to cache these and apply them after the load
    205     // completes.
    206     return false;
    207   }
    208 
    209   bool add_temp_thumbnail = false;
    210   if (!IsKnownURL(url)) {
    211     if (!IsFull()) {
    212       add_temp_thumbnail = true;
    213     } else {
    214       return false;  // This URL is not known to us.
    215     }
    216   }
    217 
    218   if (!HistoryService::CanAddURL(url))
    219     return false;  // It's not a real webpage.
    220 
    221   scoped_refptr<base::RefCountedBytes> thumbnail_data;
    222   if (!EncodeBitmap(thumbnail, &thumbnail_data))
    223     return false;
    224 
    225   if (add_temp_thumbnail) {
    226     // Always remove the existing entry and then add it back. That way if we end
    227     // up with too many temp thumbnails we'll prune the oldest first.
    228     RemoveTemporaryThumbnailByURL(url);
    229     AddTemporaryThumbnail(url, thumbnail_data.get(), score);
    230     return true;
    231   }
    232 
    233   return SetPageThumbnailEncoded(url, thumbnail_data.get(), score);
    234 }
    235 
    236 bool TopSitesImpl::SetPageThumbnailToJPEGBytes(
    237     const GURL& url,
    238     const base::RefCountedMemory* memory,
    239     const ThumbnailScore& score) {
    240   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    241 
    242   if (!loaded_) {
    243     // TODO(sky): I need to cache these and apply them after the load
    244     // completes.
    245     return false;
    246   }
    247 
    248   bool add_temp_thumbnail = false;
    249   if (!IsKnownURL(url)) {
    250     if (!IsFull()) {
    251       add_temp_thumbnail = true;
    252     } else {
    253       return false;  // This URL is not known to us.
    254     }
    255   }
    256 
    257   if (!HistoryService::CanAddURL(url))
    258     return false;  // It's not a real webpage.
    259 
    260   if (add_temp_thumbnail) {
    261     // Always remove the existing entry and then add it back. That way if we end
    262     // up with too many temp thumbnails we'll prune the oldest first.
    263     RemoveTemporaryThumbnailByURL(url);
    264     AddTemporaryThumbnail(url, memory, score);
    265     return true;
    266   }
    267 
    268   return SetPageThumbnailEncoded(url, memory, score);
    269 }
    270 
    271 // WARNING: this function may be invoked on any thread.
    272 void TopSitesImpl::GetMostVisitedURLs(
    273     const GetMostVisitedURLsCallback& callback) {
    274   MostVisitedURLList filtered_urls;
    275   {
    276     base::AutoLock lock(lock_);
    277     if (!loaded_) {
    278       // A request came in before we finished loading. Store the callback and
    279       // we'll run it on current thread when we finish loading.
    280       pending_callbacks_.push_back(
    281           base::Bind(&RunOrPostGetMostVisitedURLsCallback,
    282                      base::MessageLoopProxy::current(),
    283                      callback));
    284       return;
    285     }
    286     filtered_urls = thread_safe_cache_->top_sites();
    287   }
    288   callback.Run(filtered_urls);
    289 }
    290 
    291 bool TopSitesImpl::GetPageThumbnail(
    292     const GURL& url, scoped_refptr<base::RefCountedMemory>* bytes) {
    293   // WARNING: this may be invoked on any thread.
    294   {
    295     base::AutoLock lock(lock_);
    296     if (thread_safe_cache_->GetPageThumbnail(url, bytes))
    297       return true;
    298   }
    299 
    300   // Resource bundle is thread safe.
    301   for (size_t i = 0; i < arraysize(kPrepopulatedPages); i++) {
    302     if (url == prepopulated_page_urls_[i]) {
    303       *bytes = ResourceBundle::GetSharedInstance().
    304           LoadDataResourceBytesForScale(
    305               kPrepopulatedPages[i].thumbnail_id,
    306               ui::SCALE_FACTOR_100P);
    307       return true;
    308     }
    309   }
    310 
    311   return false;
    312 }
    313 
    314 bool TopSitesImpl::GetPageThumbnailScore(const GURL& url,
    315                                          ThumbnailScore* score) {
    316   // WARNING: this may be invoked on any thread.
    317   base::AutoLock lock(lock_);
    318   return thread_safe_cache_->GetPageThumbnailScore(url, score);
    319 }
    320 
    321 bool TopSitesImpl::GetTemporaryPageThumbnailScore(const GURL& url,
    322                                                   ThumbnailScore* score) {
    323   for (TempImages::iterator i = temp_images_.begin(); i != temp_images_.end();
    324        ++i) {
    325     if (i->first == url) {
    326       *score = i->second.thumbnail_score;
    327       return true;
    328     }
    329   }
    330   return false;
    331 }
    332 
    333 
    334 // Returns the index of |url| in |urls|, or -1 if not found.
    335 static int IndexOf(const MostVisitedURLList& urls, const GURL& url) {
    336   for (size_t i = 0; i < urls.size(); i++) {
    337     if (urls[i].url == url)
    338       return i;
    339   }
    340   return -1;
    341 }
    342 
    343 void TopSitesImpl::MigrateFromHistory() {
    344   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    345 
    346   if (history_state_ != HISTORY_LOADING) {
    347     // This can happen if history was unloaded then loaded again.
    348     return;
    349   }
    350 
    351   history_state_ = HISTORY_MIGRATING;
    352   HistoryServiceFactory::GetForProfile(
    353       profile_, Profile::EXPLICIT_ACCESS)->ScheduleDBTask(
    354           new LoadThumbnailsFromHistoryTask(
    355               this,
    356               num_results_to_request_from_history()),
    357           &history_consumer_);
    358 }
    359 
    360 void TopSitesImpl::FinishHistoryMigration(const ThumbnailMigration& data) {
    361   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    362   DCHECK_EQ(history_state_, HISTORY_MIGRATING);
    363 
    364   history_state_ = HISTORY_LOADED;
    365 
    366   SetTopSites(data.most_visited);
    367 
    368   for (size_t i = 0; i < data.most_visited.size(); ++i) {
    369     URLToThumbnailMap::const_iterator image_i =
    370         data.url_to_thumbnail_map.find(data.most_visited[i].url);
    371     if (image_i != data.url_to_thumbnail_map.end()) {
    372       SetPageThumbnailEncoded(
    373           data.most_visited[i].url, image_i->second.get(), ThumbnailScore());
    374     }
    375   }
    376 
    377   MoveStateToLoaded();
    378 
    379   ResetThreadSafeImageCache();
    380 
    381   // We've scheduled all the thumbnails and top sites to be written to the top
    382   // sites db, but it hasn't happened yet. Schedule a request on the db thread
    383   // that notifies us when done. When done we'll know everything was written and
    384   // we can tell history to finish its part of migration.
    385   backend_->DoEmptyRequest(
    386       base::Bind(&TopSitesImpl::OnHistoryMigrationWrittenToDisk,
    387                  base::Unretained(this)),
    388       &cancelable_task_tracker_);
    389 }
    390 
    391 void TopSitesImpl::HistoryLoaded() {
    392   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    393 
    394   if (history_state_ != HISTORY_MIGRATING) {
    395     // No migration from history is needed.
    396     history_state_ = HISTORY_LOADED;
    397     if (top_sites_state_ == TOP_SITES_LOADED_WAITING_FOR_HISTORY) {
    398       // TopSites thought it needed migration, but it really didn't. This
    399       // typically happens the first time a profile is run with Top Sites
    400       // enabled
    401       SetTopSites(MostVisitedURLList());
    402       MoveStateToLoaded();
    403     }
    404   }
    405   // else case can happen if history is unloaded, then loaded again.
    406 }
    407 
    408 void TopSitesImpl::SyncWithHistory() {
    409   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    410   if (loaded_ && temp_images_.size()) {
    411     // If we have temporary thumbnails it means there isn't much data, and most
    412     // likely the user is first running Chrome. During this time we throttle
    413     // updating from history by 30 seconds. If the user creates a new tab page
    414     // during this window of time we force updating from history so that the new
    415     // tab page isn't so far out of date.
    416     timer_.Stop();
    417     StartQueryForMostVisited();
    418   }
    419 }
    420 
    421 bool TopSitesImpl::HasBlacklistedItems() const {
    422   const DictionaryValue* blacklist =
    423       profile_->GetPrefs()->GetDictionary(prefs::kNtpMostVisitedURLsBlacklist);
    424   return blacklist && !blacklist->empty();
    425 }
    426 
    427 void TopSitesImpl::AddBlacklistedURL(const GURL& url) {
    428   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    429 
    430   Value* dummy = Value::CreateNullValue();
    431   {
    432     DictionaryPrefUpdate update(profile_->GetPrefs(),
    433                                 prefs::kNtpMostVisitedURLsBlacklist);
    434     DictionaryValue* blacklist = update.Get();
    435     blacklist->SetWithoutPathExpansion(GetURLHash(url), dummy);
    436   }
    437 
    438   ResetThreadSafeCache();
    439   NotifyTopSitesChanged();
    440 }
    441 
    442 void TopSitesImpl::RemoveBlacklistedURL(const GURL& url) {
    443   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    444   {
    445     DictionaryPrefUpdate update(profile_->GetPrefs(),
    446                                 prefs::kNtpMostVisitedURLsBlacklist);
    447     DictionaryValue* blacklist = update.Get();
    448     blacklist->RemoveWithoutPathExpansion(GetURLHash(url), NULL);
    449   }
    450   ResetThreadSafeCache();
    451   NotifyTopSitesChanged();
    452 }
    453 
    454 bool TopSitesImpl::IsBlacklisted(const GURL& url) {
    455   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    456   const DictionaryValue* blacklist =
    457       profile_->GetPrefs()->GetDictionary(prefs::kNtpMostVisitedURLsBlacklist);
    458   return blacklist && blacklist->HasKey(GetURLHash(url));
    459 }
    460 
    461 void TopSitesImpl::ClearBlacklistedURLs() {
    462   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    463   {
    464     DictionaryPrefUpdate update(profile_->GetPrefs(),
    465                                 prefs::kNtpMostVisitedURLsBlacklist);
    466     DictionaryValue* blacklist = update.Get();
    467     blacklist->Clear();
    468   }
    469   ResetThreadSafeCache();
    470   NotifyTopSitesChanged();
    471 }
    472 
    473 void TopSitesImpl::Shutdown() {
    474   profile_ = NULL;
    475   // Cancel all requests so that the service doesn't callback to us after we've
    476   // invoked Shutdown (this could happen if we have a pending request and
    477   // Shutdown is invoked).
    478   history_consumer_.CancelAllRequests();
    479   backend_->Shutdown();
    480 }
    481 
    482 // static
    483 void TopSitesImpl::DiffMostVisited(const MostVisitedURLList& old_list,
    484                                    const MostVisitedURLList& new_list,
    485                                    TopSitesDelta* delta) {
    486   // Add all the old URLs for quick lookup. This maps URLs to the corresponding
    487   // index in the input.
    488   std::map<GURL, size_t> all_old_urls;
    489   for (size_t i = 0; i < old_list.size(); i++)
    490     all_old_urls[old_list[i].url] = i;
    491 
    492   // Check all the URLs in the new set to see which ones are new or just moved.
    493   // When we find a match in the old set, we'll reset its index to our special
    494   // marker. This allows us to quickly identify the deleted ones in a later
    495   // pass.
    496   const size_t kAlreadyFoundMarker = static_cast<size_t>(-1);
    497   for (size_t i = 0; i < new_list.size(); i++) {
    498     std::map<GURL, size_t>::iterator found = all_old_urls.find(new_list[i].url);
    499     if (found == all_old_urls.end()) {
    500       MostVisitedURLWithRank added;
    501       added.url = new_list[i];
    502       added.rank = i;
    503       delta->added.push_back(added);
    504     } else {
    505       if (found->second != i) {
    506         MostVisitedURLWithRank moved;
    507         moved.url = new_list[i];
    508         moved.rank = i;
    509         delta->moved.push_back(moved);
    510       }
    511       found->second = kAlreadyFoundMarker;
    512     }
    513   }
    514 
    515   // Any member without the special marker in the all_old_urls list means that
    516   // there wasn't a "new" URL that mapped to it, so it was deleted.
    517   for (std::map<GURL, size_t>::const_iterator i = all_old_urls.begin();
    518        i != all_old_urls.end(); ++i) {
    519     if (i->second != kAlreadyFoundMarker)
    520       delta->deleted.push_back(old_list[i->second]);
    521   }
    522 }
    523 
    524 CancelableRequestProvider::Handle TopSitesImpl::StartQueryForMostVisited() {
    525   DCHECK(loaded_);
    526   if (!profile_)
    527     return 0;
    528 
    529   HistoryService* hs = HistoryServiceFactory::GetForProfile(
    530       profile_, Profile::EXPLICIT_ACCESS);
    531   // |hs| may be null during unit tests.
    532   if (hs) {
    533     return hs->QueryMostVisitedURLs(
    534         num_results_to_request_from_history(),
    535         kDaysOfHistory,
    536         &history_consumer_,
    537         base::Bind(&TopSitesImpl::OnTopSitesAvailableFromHistory,
    538                    base::Unretained(this)));
    539   }
    540   return 0;
    541 }
    542 
    543 bool TopSitesImpl::IsKnownURL(const GURL& url) {
    544   return loaded_ && cache_->IsKnownURL(url);
    545 }
    546 
    547 const std::string& TopSitesImpl::GetCanonicalURLString(const GURL& url) const {
    548   return cache_->GetCanonicalURL(url).spec();
    549 }
    550 
    551 bool TopSitesImpl::IsFull() {
    552   return loaded_ && cache_->top_sites().size() >= kTopSitesNumber;
    553 }
    554 
    555 TopSitesImpl::~TopSitesImpl() {
    556 }
    557 
    558 bool TopSitesImpl::SetPageThumbnailNoDB(
    559     const GURL& url,
    560     const base::RefCountedMemory* thumbnail_data,
    561     const ThumbnailScore& score) {
    562   // This should only be invoked when we know about the url.
    563   DCHECK(cache_->IsKnownURL(url));
    564 
    565   const MostVisitedURL& most_visited =
    566       cache_->top_sites()[cache_->GetURLIndex(url)];
    567   Images* image = cache_->GetImage(url);
    568 
    569   // When comparing the thumbnail scores, we need to take into account the
    570   // redirect hops, which are not generated when the thumbnail is because the
    571   // redirects weren't known. We fill that in here since we know the redirects.
    572   ThumbnailScore new_score_with_redirects(score);
    573   new_score_with_redirects.redirect_hops_from_dest =
    574       GetRedirectDistanceForURL(most_visited, url);
    575 
    576   if (!ShouldReplaceThumbnailWith(image->thumbnail_score,
    577                                   new_score_with_redirects) &&
    578       image->thumbnail.get())
    579     return false;  // The one we already have is better.
    580 
    581   image->thumbnail = const_cast<base::RefCountedMemory*>(thumbnail_data);
    582   image->thumbnail_score = new_score_with_redirects;
    583 
    584   ResetThreadSafeImageCache();
    585   return true;
    586 }
    587 
    588 bool TopSitesImpl::SetPageThumbnailEncoded(
    589     const GURL& url,
    590     const base::RefCountedMemory* thumbnail,
    591     const ThumbnailScore& score) {
    592   if (!SetPageThumbnailNoDB(url, thumbnail, score))
    593     return false;
    594 
    595   // Update the database.
    596   if (!cache_->IsKnownURL(url))
    597     return false;
    598 
    599   size_t index = cache_->GetURLIndex(url);
    600   const MostVisitedURL& most_visited = cache_->top_sites()[index];
    601   backend_->SetPageThumbnail(most_visited,
    602                              index,
    603                              *(cache_->GetImage(most_visited.url)));
    604   return true;
    605 }
    606 
    607 // static
    608 bool TopSitesImpl::EncodeBitmap(const gfx::Image& bitmap,
    609                                 scoped_refptr<base::RefCountedBytes>* bytes) {
    610   if (bitmap.IsEmpty())
    611     return false;
    612   *bytes = new base::RefCountedBytes();
    613   std::vector<unsigned char> data;
    614   if (!gfx::JPEG1xEncodedDataFromImage(bitmap, kTopSitesImageQuality, &data))
    615     return false;
    616 
    617   // As we're going to cache this data, make sure the vector is only as big as
    618   // it needs to be, as JPEGCodec::Encode() over-allocates data.capacity().
    619   // (In a C++0x future, we can just call shrink_to_fit() in Encode())
    620   (*bytes)->data() = data;
    621   return true;
    622 }
    623 
    624 void TopSitesImpl::RemoveTemporaryThumbnailByURL(const GURL& url) {
    625   for (TempImages::iterator i = temp_images_.begin(); i != temp_images_.end();
    626        ++i) {
    627     if (i->first == url) {
    628       temp_images_.erase(i);
    629       return;
    630     }
    631   }
    632 }
    633 
    634 void TopSitesImpl::AddTemporaryThumbnail(
    635     const GURL& url,
    636     const base::RefCountedMemory* thumbnail,
    637     const ThumbnailScore& score) {
    638   if (temp_images_.size() == kMaxTempTopImages)
    639     temp_images_.erase(temp_images_.begin());
    640 
    641   TempImage image;
    642   image.first = url;
    643   image.second.thumbnail = const_cast<base::RefCountedMemory*>(thumbnail);
    644   image.second.thumbnail_score = score;
    645   temp_images_.push_back(image);
    646 }
    647 
    648 void TopSitesImpl::TimerFired() {
    649   StartQueryForMostVisited();
    650 }
    651 
    652 // static
    653 int TopSitesImpl::GetRedirectDistanceForURL(const MostVisitedURL& most_visited,
    654                                             const GURL& url) {
    655   for (size_t i = 0; i < most_visited.redirects.size(); i++) {
    656     if (most_visited.redirects[i] == url)
    657       return static_cast<int>(most_visited.redirects.size() - i - 1);
    658   }
    659   NOTREACHED() << "URL should always be found.";
    660   return 0;
    661 }
    662 
    663 MostVisitedURLList TopSitesImpl::GetPrepopulatePages() {
    664   MostVisitedURLList urls;
    665   urls.resize(arraysize(kPrepopulatedPages));
    666   for (size_t i = 0; i < urls.size(); ++i) {
    667     MostVisitedURL& url = urls[i];
    668     url.url = GURL(prepopulated_page_urls_[i]);
    669     url.redirects.push_back(url.url);
    670     url.title = l10n_util::GetStringUTF16(kPrepopulatedPages[i].title_id);
    671   }
    672   return urls;
    673 }
    674 
    675 bool TopSitesImpl::loaded() const {
    676   return loaded_;
    677 }
    678 
    679 bool TopSitesImpl::AddPrepopulatedPages(MostVisitedURLList* urls) {
    680   bool added = false;
    681   MostVisitedURLList prepopulate_urls = GetPrepopulatePages();
    682   for (size_t i = 0; i < prepopulate_urls.size(); ++i) {
    683     if (urls->size() < kTopSitesNumber &&
    684         IndexOf(*urls, prepopulate_urls[i].url) == -1) {
    685       urls->push_back(prepopulate_urls[i]);
    686       added = true;
    687     }
    688   }
    689   return added;
    690 }
    691 
    692 void TopSitesImpl::ApplyBlacklist(const MostVisitedURLList& urls,
    693                                   MostVisitedURLList* out) {
    694   for (size_t i = 0; i < urls.size() && i < kTopSitesNumber; ++i) {
    695     if (!IsBlacklisted(urls[i].url))
    696       out->push_back(urls[i]);
    697   }
    698 }
    699 
    700 std::string TopSitesImpl::GetURLHash(const GURL& url) {
    701   // We don't use canonical URLs here to be able to blacklist only one of
    702   // the two 'duplicate' sites, e.g. 'gmail.com' and 'mail.google.com'.
    703   return base::MD5String(url.spec());
    704 }
    705 
    706 base::TimeDelta TopSitesImpl::GetUpdateDelay() {
    707   if (cache_->top_sites().size() <= arraysize(kPrepopulatedPages))
    708     return base::TimeDelta::FromSeconds(30);
    709 
    710   int64 range = kMaxUpdateIntervalMinutes - kMinUpdateIntervalMinutes;
    711   int64 minutes = kMaxUpdateIntervalMinutes -
    712       last_num_urls_changed_ * range / cache_->top_sites().size();
    713   return base::TimeDelta::FromMinutes(minutes);
    714 }
    715 
    716 void TopSitesImpl::Observe(int type,
    717                            const content::NotificationSource& source,
    718                            const content::NotificationDetails& details) {
    719   if (!loaded_)
    720     return;
    721 
    722   if (type == chrome::NOTIFICATION_HISTORY_URLS_DELETED) {
    723     content::Details<history::URLsDeletedDetails> deleted_details(details);
    724     if (deleted_details->all_history) {
    725       SetTopSites(MostVisitedURLList());
    726       backend_->ResetDatabase();
    727     } else {
    728       std::set<size_t> indices_to_delete;  // Indices into top_sites_.
    729       for (URLRows::const_iterator i = deleted_details->rows.begin();
    730            i != deleted_details->rows.end(); ++i) {
    731         if (cache_->IsKnownURL(i->url()))
    732           indices_to_delete.insert(cache_->GetURLIndex(i->url()));
    733       }
    734 
    735       if (indices_to_delete.empty())
    736         return;
    737 
    738       MostVisitedURLList new_top_sites(cache_->top_sites());
    739       for (std::set<size_t>::reverse_iterator i = indices_to_delete.rbegin();
    740            i != indices_to_delete.rend(); i++) {
    741         new_top_sites.erase(new_top_sites.begin() + *i);
    742       }
    743       SetTopSites(new_top_sites);
    744     }
    745     StartQueryForMostVisited();
    746   } else if (type == content::NOTIFICATION_NAV_ENTRY_COMMITTED) {
    747     NavigationController* controller =
    748         content::Source<NavigationController>(source).ptr();
    749     Profile* profile = Profile::FromBrowserContext(
    750         controller->GetWebContents()->GetBrowserContext());
    751     if (profile == profile_ && !IsFull()) {
    752       content::LoadCommittedDetails* load_details =
    753           content::Details<content::LoadCommittedDetails>(details).ptr();
    754       if (!load_details)
    755         return;
    756       const GURL& url = load_details->entry->GetURL();
    757       if (!cache_->IsKnownURL(url) && HistoryService::CanAddURL(url)) {
    758         // To avoid slamming history we throttle requests when the url updates.
    759         // To do otherwise negatively impacts perf tests.
    760         RestartQueryForTopSitesTimer(GetUpdateDelay());
    761       }
    762     }
    763   }
    764 }
    765 
    766 void TopSitesImpl::SetTopSites(const MostVisitedURLList& new_top_sites) {
    767   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    768 
    769   MostVisitedURLList top_sites(new_top_sites);
    770   AddPrepopulatedPages(&top_sites);
    771 
    772   TopSitesDelta delta;
    773   DiffMostVisited(cache_->top_sites(), top_sites, &delta);
    774   if (!delta.deleted.empty() || !delta.added.empty() || !delta.moved.empty()) {
    775     backend_->UpdateTopSites(delta);
    776   }
    777 
    778   last_num_urls_changed_ = delta.added.size() + delta.moved.size();
    779 
    780   // We always do the following steps (setting top sites in cache, and resetting
    781   // thread safe cache ...) as this method is invoked during startup at which
    782   // point the caches haven't been updated yet.
    783   cache_->SetTopSites(top_sites);
    784 
    785   // See if we have any tmp thumbnails for the new sites.
    786   if (!temp_images_.empty()) {
    787     for (size_t i = 0; i < top_sites.size(); ++i) {
    788       const MostVisitedURL& mv = top_sites[i];
    789       GURL canonical_url = cache_->GetCanonicalURL(mv.url);
    790       // At the time we get the thumbnail redirects aren't known, so we have to
    791       // iterate through all the images.
    792       for (TempImages::iterator it = temp_images_.begin();
    793            it != temp_images_.end(); ++it) {
    794         if (canonical_url == cache_->GetCanonicalURL(it->first)) {
    795           SetPageThumbnailEncoded(
    796               mv.url, it->second.thumbnail.get(), it->second.thumbnail_score);
    797           temp_images_.erase(it);
    798           break;
    799         }
    800       }
    801     }
    802   }
    803 
    804   if (top_sites.size() >= kTopSitesNumber)
    805     temp_images_.clear();
    806 
    807   ResetThreadSafeCache();
    808   ResetThreadSafeImageCache();
    809   NotifyTopSitesChanged();
    810 
    811   // Restart the timer that queries history for top sites. This is done to
    812   // ensure we stay in sync with history.
    813   RestartQueryForTopSitesTimer(GetUpdateDelay());
    814 }
    815 
    816 int TopSitesImpl::num_results_to_request_from_history() const {
    817   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    818 
    819   const DictionaryValue* blacklist =
    820       profile_->GetPrefs()->GetDictionary(prefs::kNtpMostVisitedURLsBlacklist);
    821   return kTopSitesNumber + (blacklist ? blacklist->size() : 0);
    822 }
    823 
    824 void TopSitesImpl::MoveStateToLoaded() {
    825   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    826 
    827   MostVisitedURLList filtered_urls;
    828   PendingCallbacks pending_callbacks;
    829   {
    830     base::AutoLock lock(lock_);
    831 
    832     if (loaded_)
    833       return;  // Don't do anything if we're already loaded.
    834     loaded_ = true;
    835 
    836     // Now that we're loaded we can service the queued up callbacks. Copy them
    837     // here and service them outside the lock.
    838     if (!pending_callbacks_.empty()) {
    839       filtered_urls = thread_safe_cache_->top_sites();
    840       pending_callbacks.swap(pending_callbacks_);
    841     }
    842   }
    843 
    844   for (size_t i = 0; i < pending_callbacks.size(); i++)
    845     pending_callbacks[i].Run(filtered_urls);
    846 
    847   content::NotificationService::current()->Notify(
    848       chrome::NOTIFICATION_TOP_SITES_LOADED,
    849       content::Source<Profile>(profile_),
    850       content::Details<TopSites>(this));
    851 }
    852 
    853 void TopSitesImpl::ResetThreadSafeCache() {
    854   base::AutoLock lock(lock_);
    855   MostVisitedURLList cached;
    856   ApplyBlacklist(cache_->top_sites(), &cached);
    857   thread_safe_cache_->SetTopSites(cached);
    858 }
    859 
    860 void TopSitesImpl::ResetThreadSafeImageCache() {
    861   base::AutoLock lock(lock_);
    862   thread_safe_cache_->SetThumbnails(cache_->images());
    863 }
    864 
    865 void TopSitesImpl::NotifyTopSitesChanged() {
    866   content::NotificationService::current()->Notify(
    867       chrome::NOTIFICATION_TOP_SITES_CHANGED,
    868       content::Source<TopSites>(this),
    869       content::NotificationService::NoDetails());
    870 }
    871 
    872 void TopSitesImpl::RestartQueryForTopSitesTimer(base::TimeDelta delta) {
    873   if (timer_.IsRunning() && ((timer_start_time_ + timer_.GetCurrentDelay()) <
    874                              (base::TimeTicks::Now() + delta))) {
    875     return;
    876   }
    877 
    878   timer_start_time_ = base::TimeTicks::Now();
    879   timer_.Stop();
    880   timer_.Start(FROM_HERE, delta, this, &TopSitesImpl::TimerFired);
    881 }
    882 
    883 void TopSitesImpl::OnHistoryMigrationWrittenToDisk() {
    884   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    885 
    886   if (!profile_)
    887     return;
    888 
    889   HistoryService* history = HistoryServiceFactory::GetForProfile(
    890       profile_, Profile::EXPLICIT_ACCESS);
    891   if (history)
    892     history->OnTopSitesReady();
    893 }
    894 
    895 void TopSitesImpl::OnGotMostVisitedThumbnails(
    896     const scoped_refptr<MostVisitedThumbnails>& thumbnails,
    897     const bool* need_history_migration) {
    898   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    899   DCHECK_EQ(top_sites_state_, TOP_SITES_LOADING);
    900 
    901   if (!*need_history_migration) {
    902     top_sites_state_ = TOP_SITES_LOADED;
    903 
    904     // Set the top sites directly in the cache so that SetTopSites diffs
    905     // correctly.
    906     cache_->SetTopSites(thumbnails->most_visited);
    907     SetTopSites(thumbnails->most_visited);
    908     cache_->SetThumbnails(thumbnails->url_to_images_map);
    909 
    910     ResetThreadSafeImageCache();
    911 
    912     MoveStateToLoaded();
    913 
    914     // Start a timer that refreshes top sites from history.
    915     RestartQueryForTopSitesTimer(
    916         base::TimeDelta::FromSeconds(kUpdateIntervalSecs));
    917   } else {
    918     // The top sites file didn't exist or is the wrong version. We need to wait
    919     // for history to finish loading to know if we really needed to migrate.
    920     if (history_state_ == HISTORY_LOADED) {
    921       top_sites_state_ = TOP_SITES_LOADED;
    922       SetTopSites(MostVisitedURLList());
    923       MoveStateToLoaded();
    924     } else {
    925       top_sites_state_ = TOP_SITES_LOADED_WAITING_FOR_HISTORY;
    926       // Ask for history just in case it hasn't been loaded yet. When history
    927       // finishes loading we'll do migration and/or move to loaded.
    928       HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS);
    929     }
    930   }
    931 }
    932 
    933 void TopSitesImpl::OnTopSitesAvailableFromHistory(
    934     CancelableRequestProvider::Handle handle,
    935     MostVisitedURLList pages) {
    936   SetTopSites(pages);
    937 
    938   // Used only in testing.
    939   content::NotificationService::current()->Notify(
    940       chrome::NOTIFICATION_TOP_SITES_UPDATED,
    941       content::Source<TopSitesImpl>(this),
    942       content::Details<CancelableRequestProvider::Handle>(&handle));
    943 }
    944 
    945 }  // namespace history
    946