Add some initial code for the top sites service. This will be a replacement for

the thumbnail database, and will also replace the ThumbnailStore which was the
previous replacement we didn't ship. This component will be very much like the
ThumbnailStore wtih the addition of the actual most visited data (not just
thumbnails) and that it is threadsafe.

This class is designed to be called on any thread. When it is complete,
thumbnails will be added to it from the UI thread of the browser. Requests for
thumbnails and the most visited data can be serviced directly on the I/O thread
without going through the UI thread, and since the data is cached, the request
won't also have to go through the history thread.

The current state is that it cqan store and update the the most visited list and thumbnails. There are unit tests covering this behavior.

I also added support for redirect ranking to ThumbnailScore. This is to
duplicated the ranking function in history currently, where it prefers
thumbnails closer to the end of a redirect chain. Since we won't be using the
history service and are only storing thumbnails for the most visited items, we
have to track the redirect index ourselves.

BUG=none
TEST=covered by unit tests (hopefully!)
Review URL: http://codereview.chromium.org/251002

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@27824 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 104 insertions, 21 deletions

diff --git a/chrome/common/thumbnail_score.cc b/chrome/common/thumbnail_score.cc
index 339b7e0..dc7856d 100644
--- a/chrome/common/thumbnail_score.cc
+++ b/chrome/common/thumbnail_score.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -35,14 +35,16 @@ ThumbnailScore::ThumbnailScore()
     : boring_score(1.0),
       good_clipping(false),
       at_top(false),
-      time_at_snapshot(Time::Now()) {
+      time_at_snapshot(Time::Now()),
+      redirect_hops_from_dest(0) {
 }
 
 ThumbnailScore::ThumbnailScore(double score, bool clipping, bool top)
     : boring_score(score),
       good_clipping(clipping),
       at_top(top),
-      time_at_snapshot(Time::Now()) {
+      time_at_snapshot(Time::Now()),
+      redirect_hops_from_dest(0) {
 }
 
 ThumbnailScore::ThumbnailScore(double score, bool clipping, bool top,
@@ -50,7 +52,8 @@ ThumbnailScore::ThumbnailScore(double score, bool clipping, bool top,
     : boring_score(score),
       good_clipping(clipping),
       at_top(top),
-      time_at_snapshot(time) {
+      time_at_snapshot(time),
+      redirect_hops_from_dest(0) {
 }
 
 ThumbnailScore::~ThumbnailScore() {
@@ -63,7 +66,8 @@ bool ThumbnailScore::Equals(const ThumbnailScore& rhs) const {
   return boring_score == rhs.boring_score &&
       good_clipping == rhs.good_clipping &&
       at_top == rhs.at_top &&
-      time_at_snapshot.ToTimeT() == rhs.time_at_snapshot.ToTimeT();
+      time_at_snapshot.ToTimeT() == rhs.time_at_snapshot.ToTimeT() &&
+      redirect_hops_from_dest == rhs.redirect_hops_from_dest;
 }
 
 bool ShouldReplaceThumbnailWith(const ThumbnailScore& current,
@@ -77,22 +81,32 @@ bool ShouldReplaceThumbnailWith(const ThumbnailScore& current,
     return replacement.boring_score <
         ThumbnailScore::kThumbnailMaximumBoringness;
   } else if (replacement_type == current_type) {
-    if (replacement.boring_score < current.boring_score) {
-      // If we have a thumbnail that's straight up less boring, use it.
-      return true;
-    }
+    // It's much easier to do the scaling below when we're dealing with "higher
+    // is better." Then we can decrease the score by dividing by a fraction.
+    const double kThumbnailMinimumInterestingness =
+        1.0 - ThumbnailScore::kThumbnailMaximumBoringness;
+    double current_interesting_score = 1.0 - current.boring_score;
+    double replacement_interesting_score = 1.0 - replacement.boring_score;
+
+    // Degrade the score of each thumbnail to account for how many redirects
+    // they are away from the destination. 1/(x+1) gives a scaling factor of
+    // one for x = 0, and asymptotically approaches 0 for larger values of x.
+    current_interesting_score *=
+        1.0 / (current.redirect_hops_from_dest + 1);
+    replacement_interesting_score *=
+        1.0 / (replacement.redirect_hops_from_dest + 1);
 
-    // Slowly degrade the boring score of the current thumbnail
-    // so we take thumbnails which are slightly less good:
-    TimeDelta since_last_thumbnail =
+    // Degrade the score and prefer the newer one based on how long apart the
+    // two thumbnails were taken. This means we'll eventually replace an old
+    // good one with a new worse one assuming enough time has passed.
+    TimeDelta time_between_thumbnails =
         replacement.time_at_snapshot - current.time_at_snapshot;
-    double degraded_boring_score = current.boring_score +
-        (since_last_thumbnail.InHours() *
-         ThumbnailScore::kThumbnailDegradePerHour);
+    current_interesting_score -= time_between_thumbnails.InHours() *
+         ThumbnailScore::kThumbnailDegradePerHour;
 
-    if (degraded_boring_score > ThumbnailScore::kThumbnailMaximumBoringness)
-      degraded_boring_score = ThumbnailScore::kThumbnailMaximumBoringness;
-    if (replacement.boring_score < degraded_boring_score)
+    if (current_interesting_score < kThumbnailMinimumInterestingness)
+      current_interesting_score = kThumbnailMinimumInterestingness;
+    if (replacement_interesting_score > current_interesting_score)
       return true;
   }
 
diff --git a/chrome/common/thumbnail_score.h b/chrome/common/thumbnail_score.h
index 530f87e..c1ebb81 100644
--- a/chrome/common/thumbnail_score.h
+++ b/chrome/common/thumbnail_score.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -9,8 +9,9 @@
 
 // A set of metadata about a Thumbnail.
 struct ThumbnailScore {
-  // Initializes the ThumbnailScore to the absolute worst possible
-  // values except for time, which is set to Now().
+  // Initializes the ThumbnailScore to the absolute worst possible values
+  // except for time, which is set to Now(), and redirect_hops_from_dest which
+  // is set to 0.
   ThumbnailScore();
 
   // Builds a ThumbnailScore with the passed in values, and sets the
@@ -48,6 +49,20 @@ struct ThumbnailScore {
   // sure thumbnails are kept fresh.
   base::Time time_at_snapshot;
 
+  // The number of hops from the final destination page that this thumbnail was
+  // taken at. When a thumbnail is taken, this will always be the redirect
+  // destination (value of 0).
+  //
+  // For the most visited view, we'll sometimes get thumbnails for URLs in the
+  // middle of a redirect chain. In this case, the top sites component will set
+  // this value so the distance from the destination can be taken into account
+  // by the comparison function.
+  //
+  // If "http://google.com/" redirected to "http://www.google.com/", then
+  // a thumbnail for the first would have a redirect hop of 1, and the second
+  // would have a redirect hop of 0.
+  int redirect_hops_from_dest;
+
   // How bad a thumbnail needs to be before we completely ignore it.
   static const double kThumbnailMaximumBoringness;
 
diff --git a/chrome/common/thumbnail_score_unittest.cc b/chrome/common/thumbnail_score_unittest.cc
new file mode 100644
index 0000000..14d79dd
--- /dev/null
+++ b/chrome/common/thumbnail_score_unittest.cc
@@ -0,0 +1,54 @@
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "chrome/common/thumbnail_score.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+// Tests that the different types of thumbnails are compared properly.
+TEST(ThumbnailScoreTest, ShouldReplaceThumbnailWithType) {
+  base::Time now = base::Time::Now();
+
+  ThumbnailScore nothing_good(0.5, false, false, now);
+  ThumbnailScore not_at_top(0.5, false, true, now);
+  ThumbnailScore bad_clipping(0.5, true, false, now);
+  ThumbnailScore life_is_awesome(0.5, true, true, now);
+
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(nothing_good, not_at_top));
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(nothing_good, bad_clipping));
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(nothing_good, life_is_awesome));
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(not_at_top, bad_clipping));
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(not_at_top, life_is_awesome));
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(bad_clipping, life_is_awesome));
+}
+
+// Tests that we'll replace old thumbnails will crappier but newer ones.
+TEST(ThumbnailScoreTest, ShouldReplaceThumbnailWithTime) {
+  // Use a really long time for the difference so we aren't sensitive to the
+  // degrading schedule.
+  base::Time now = base::Time::Now();
+  base::Time last_year = now - base::TimeDelta::FromDays(365);
+
+  ThumbnailScore oldie_but_goodie(0.1, true, true, last_year);
+  ThumbnailScore newie_but_crappie(0.9, true, true, now);
+
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(oldie_but_goodie, newie_but_crappie));
+}
+
+// Having many redirects should age the thumbnail.
+TEST(ThumbnailScoreTest, RedirectCount) {
+  base::Time now = base::Time::Now();
+
+  ThumbnailScore no_redirects(0.5, true, true, now);
+  no_redirects.redirect_hops_from_dest = 0;
+  ThumbnailScore some_redirects(0.5, true, true, now);
+  some_redirects.redirect_hops_from_dest = 1;
+
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(some_redirects, no_redirects));
+
+  // This one has a lot of redirects but a better score. It should still be
+  // rejected.
+  ThumbnailScore lotsa_redirects(0.4, true, true, now);
+  lotsa_redirects.redirect_hops_from_dest = 4;
+  EXPECT_FALSE(ShouldReplaceThumbnailWith(no_redirects, lotsa_redirects));
+}