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