Implementing URL prefix match for history thumbnail cache.

chrome/browser/history/top_sites_cache_unittest.cc

+// Copyright (c) 2013 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/browser/history/top_sites_cache.h"
+
+#include <set>
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+#include "base/scoped_ptr.h"
+#include "base/strings/string16.h"
+#include "base/strings/string_number_conversions.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace history {
+
+namespace {
+
+class TopSitesCacheTest : public testing::Test {
+ protected:
+  // Initializes |top_sites_| and |cache_| based on |spec|, which is a list of
+  // URL strings with optional indents: indentated URLs redirect to the last
+  // non-indented URL. Titles are assigned as "Title 1", "Title 2", etc., in the
+  // order of appearance. See |kTopSitesSpecBasic| for an example.
+  void InitTopSiteCache(char** spec, int size);
+
+  MostVisitedURLList top_sites_;
+  TopSitesCache cache_;
+};
+
+void TopSitesCacheTest::InitTopSiteCache(char** spec, int size) {
+  std::set<std::string> urls_seen;
+  for (int i = 0; i < size; ++i) {
+    char* spec_item = spec[i];
+    while (*spec_item && *spec_item == ' ')  // Eat indent.
+      ++spec_item;
+    ASSERT_EQ(urls_seen.find(spec_item), urls_seen.end())
+        << "Duplicate URL found: " << spec_item;
+    urls_seen.insert(spec_item);
+    if (spec_item == spec[i]) {  // No indent: add new MostVisitedURL.
+      string16 title(L"Title " + base::Uint64ToString16(top_sites_.size() + 1));
+      top_sites_.push_back(MostVisitedURL(GURL(spec_item), title));
+    }
+    ASSERT_TRUE(!top_sites_.empty());
+    // Set up redirect to canonical URL. Canonical URL redirects to itself, too.
+    top_sites_.back().redirects.push_back(GURL(spec_item));
+  }
+  cache_.SetTopSites(top_sites_);
+}
+
+TEST_F(TopSitesCacheTest, CanonicalURLComparator) {
+  // Comprehensive test by comparing each pair in sorted list. O(n^2).
+  const char* sorted_list[] = {
+    "http://www.gogle.com/redirects_to_google",
+    "http://www.google.com",
+    "http://www.google.com/",
+    "http://www.google.com/?q",
+    "http://www.google.com/A",
+    "http://www.google.com/index.html",
+    "http://www.google.com/test",
+    "http://www.google.com/test?q=3",
+    "http://www.google.com/test?r=3",
+    "http://www.google.com/test/zzzzz",
+    "http://www.google.com/test-case",
+    "http://www.google.com:80/",
+    "https://www.google.com",

[beaudoin, 2013/09/04 16:46:10]

Please throw in some weird characters that are valid in a path segment. For
example '%' that naturally compares lower than '/' in ASCII. List of valid
characters:
http://stackoverflow.com/questions/4669692/valid-characters-for-directory-par...

[huangs, 2013/09/04 23:27:39]

Done.

+  };
+  for (int i = 0; i < arraysize(sorted_list); ++i) {
+    EXPECT_FALSE(
+        CanonicalURLComparator::CompareString(sorted_list[i], sorted_list[i]))
+        << " for \"" << sorted_list[i] << "\" < \"" << sorted_list[i] << "\"";
+    // Every disjoint pair-wise comparison.
+    for (int j = i + 1; j < arraysize(sorted_list); ++j) {
+      EXPECT_TRUE(
+          CanonicalURLComparator::CompareString(sorted_list[i], sorted_list[j]))
+          << " for \"" << sorted_list[i] << "\" < \"" << sorted_list[j] << "\"";
+      EXPECT_FALSE(
+          CanonicalURLComparator::CompareString(sorted_list[j], sorted_list[i]))
+          << " for \"" << sorted_list[j] << "\" < \"" << sorted_list[i] << "\"";
+    }
+  }
+}
+
+char* kTopSitesSpecBasic[] = {

[beaudoin, 2013/09/04 16:46:10]

Add a comment indicating an indent implies a redirect.

[huangs, 2013/09/04 23:27:39]

Done.

+  "http://www.google.com",
+  "  http://www.gogle.com",
+  "  http://www.gooogle.com",
+  "http://www.youtube.com/a/b",
+  "  http://www.youtube.com/a/b?test=1",
+  "https://www.google.com",
+  "  https://www.gogle.com",
+  "http://www.example.com:3141",
+};
+
+TEST_F(TopSitesCacheTest, GetCanonicalURL) {
+  InitTopSiteCache(kTopSitesSpecBasic, arraysize(kTopSitesSpecBasic));
+  // Already is canonical: redirects.
+  EXPECT_EQ(GURL("http://www.google.com"),

[huangs, 2013/09/04 23:27:39]

Instead of comparing GURL(x) with GURL(y), it's more precise to compare x with
GURL(y).spec().

+            cache_.GetCanonicalURL(GURL("http://www.google.com")));
+  // Exact match with stored URL: redirects.
+  EXPECT_EQ(GURL("http://www.google.com"),
+            cache_.GetCanonicalURL(GURL("http://www.gooogle.com")));
+  // Recognizes despite trailing "/".
+  EXPECT_EQ(GURL("http://www.google.com"),
+            cache_.GetCanonicalURL(GURL("http://www.gooogle.com/")));
+  // Exact match with URL with query: redirects.
+  EXPECT_EQ(GURL("http://www.youtube.com/a/b"),
+            cache_.GetCanonicalURL(GURL("http://www.youtube.com/a/b?test=1")));
+  // No match with URL with query: as-is.
+  EXPECT_EQ(GURL("http://www.youtube.com/a/b?test"),
+            cache_.GetCanonicalURL(GURL("http://www.youtube.com/a/b?test")));
+  // Never-seen-before URL: as-is.
+  EXPECT_EQ(GURL("http://maps.google.com/"),
+            cache_.GetCanonicalURL(GURL("http://maps.google.com/")));
+  // Changing port number, does not match: as-is.
+  EXPECT_EQ(GURL("http://www.example.com:80"),
+            cache_.GetCanonicalURL(GURL("http://www.example.com:80")));

[beaudoin, 2013/09/04 16:46:10]

// Prefix doesn't work.
EXPECT_EQ(GURL("http://www.youtube.com/a"),
          cache_.GetCanonicalURL(GURL("http://www.youtube.com/a")));

[huangs, 2013/09/04 23:27:39]

Done.

+}
+
+TEST_F(TopSitesCacheTest, IsKnownUrl) {
+  InitTopSiteCache(kTopSitesSpecBasic, arraysize(kTopSitesSpecBasic));
+  // Matches.
+  EXPECT_TRUE(cache_.IsKnownURL(GURL("http://www.google.com")));
+  EXPECT_TRUE(cache_.IsKnownURL(GURL("http://www.gooogle.com")));
+  EXPECT_TRUE(cache_.IsKnownURL(GURL("http://www.google.com/")));
+
+  // Non-matches.
+  EXPECT_FALSE(cache_.IsKnownURL(GURL("http://www.google.com?")));
+  EXPECT_FALSE(cache_.IsKnownURL(GURL("http://www.google.net")));
+  EXPECT_FALSE(cache_.IsKnownURL(GURL("http://www.google.com/stuff")));
+  EXPECT_FALSE(cache_.IsKnownURL(GURL("https://www.gooogle.com")));

[beaudoin, 2013/09/04 16:46:10]

EXPECT_FALSE(cache_.IsKnownURL(GURL("http://www.youtube.com/a")));

[huangs, 2013/09/04 23:27:39]

Done.

+}
+
+char* kTopSitesSpecPrefix[] = {

[beaudoin, 2013/09/04 16:46:10]

Same short comment.

[huangs, 2013/09/04 23:27:39]

Done.

+  "http://www.g.com",
+  "  http://www.g.com/test?q=3",
+  "  http://www.g.com/test/y?b",
+  "http://www.g.com/2",
+  "  http://www.g.com/test/q",
+  "  http://www.g.com/test/y?a",
+  "http://www.g.com/3",
+  "  http://www.g.com/testing",
+  "http://www.g.com/test-hyphen",

[beaudoin, 2013/09/04 16:46:10]

I would add:
  "http://www.g.com/test",
Without any redirect. Then add a test to ensure that "http://www.g.com/test"
matches "http://www.g.com/test" and not "http://www.g.com".

[huangs, 2013/09/04 23:27:39]

Don't want to interfere with existing test, but added a view more tests to test
weird "shadowing" cases.

+};
+
+TEST_F(TopSitesCacheTest, GetCanonicalURLForPrefix) {
+  InitTopSiteCache(kTopSitesSpecPrefix, arraysize(kTopSitesSpecPrefix));
+  // Already is canonical: redirects.
+  EXPECT_EQ(GURL("http://www.g.com"),
+            cache_.GetCanonicalURLForPrefix(GURL("http://www.g.com")));
+  // Exact match with stored URL: redirects.
+  EXPECT_EQ(GURL("http://www.g.com"),
+            cache_.GetCanonicalURLForPrefix(GURL("http://www.g.com/test?q=3")));
+  // Prefix match: redirects.
+  EXPECT_EQ(GURL("http://www.g.com"),
+            cache_.GetCanonicalURLForPrefix(GURL("http://www.g.com/test")));
+  // Competing prefix match: redirects to closest.
+  EXPECT_EQ(GURL("http://www.g.com/2"),
+            cache_.GetCanonicalURLForPrefix(GURL("http://www.g.com/test/q")));
+  // Multiple prefix matches: redirects to first.
+  EXPECT_EQ(GURL("http://www.g.com/2"),
+            cache_.GetCanonicalURLForPrefix(GURL("http://www.g.com/test/y")));
+  // No prefix match: as-is
+  EXPECT_EQ(GURL("http://www.g.com/no-match"),
+            cache_.GetCanonicalURLForPrefix(GURL("http://www.g.com/no-match")));
+  // String prefix match but not URL-prefix match: as-is.
+  EXPECT_EQ(GURL("http://www.g.com/t"),
+            cache_.GetCanonicalURLForPrefix(GURL("http://www.g.com/t")));
+  // Different protocol: as-is.
+  EXPECT_EQ(GURL("https://www.g.com/test"),
+            cache_.GetCanonicalURLForPrefix(GURL("https://www.g.com/test")));
+}
+
+TEST_F(TopSitesCacheTest, UrlStringIsPrefix) {
+  struct {
+    const char* s1;
+    const char* s2;
+  } true_cases[] = {
+    {"http://www.google.com", "http://www.google.com"},
+    {"http://www.google.com/a/b", "http://www.google.com/a/b"},
+    {"http://www.google.com?test=3", "http://www.google.com/"},
+    {"http://www.google.com/", "http://www.google.com/test/with/dir/"},
+    {"http://www.google.com:360", "http://www.google.com:360/?q=1234"},
+    {"http://www.google.com:80", "http://www.google.com/gurl/is/smart"},

[beaudoin, 2013/09/04 16:46:10]

This case will work with UrlStringIsPrefix but may fail with
GetCanonicalURLForPrefix I believe... For example, consider the following sorted
list

http://www.google.com
http://www.google.com:80   <-- The query
http://www.googli.com

lower_bound will return "http://www.googli.com" which will fail to hit a
tumbnail...

We should maybe mention that as a limitation somewhere in the main algo?

[huangs, 2013/09/04 23:27:39]

It looks like GURL is smart enough:

GURL("http://www.google.com:80").spec() == "http://www.google.com/"

so we won't have to worry about this. Adding more tests though.

[beaudoin, 2013/09/05 01:41:19]

Ack.

+    {"http://www.google.com/test", "http://www.google.com/test/with/dir/"},
+    {"http://www.google.com/test/", "http://www.google.com/test/with/dir"},
+    {"http://www.google.com/test?", "http://www.google.com/test/with/dir/"},
+  };
+  for (int i = 0; i < arraysize(true_cases); ++i) {
+    EXPECT_TRUE(TopSitesCache::UrlIsPrefix(GURL(true_cases[i].s1),
+                                           GURL(true_cases[i].s2)))
+      << " for true_cases[" << i << "]";
+  }
+  struct {
+    const char* s1;
+    const char* s2;
+  } false_cases[] = {
+    {"http://www.google.com/test", "http://www.google.com"},
+    {"http://www.google.com/a/b/", "http://www.google.com/a/b"},  // Arguable.
+    {"http://www.google.co", "http://www.google.com"},
+    {"http://google.com", "http://www.google.com"},
+    {"http://www.google.com", "https://www.google.com"},
+    {"http://www.google.com/path", "http://www.google.com:137/path"},
+    {"http://www.google.com/same/dir", "http://www.youtube.com/same/dir"},
+    {"http://www.google.com/te", "http://www.google.com/test"},
+    {"http://www.google.com/test", "http://www.google.com/test-bed"},
+    {"http://www.google.com/test-", "http://www.google.com/test?"},
+  };
+  for (int i = 0; i < arraysize(false_cases); ++i) {
+    EXPECT_FALSE(TopSitesCache::UrlIsPrefix(GURL(false_cases[i].s1),
+                                            GURL(false_cases[i].s2)))
+      << " for false_cases[" << i << "]";
+  }
+}
+
+}  // namespace
+
+}  // namespace history