Re-implement app overlap detection with new extent syntax.

BUG=47445

Review URL: http://codereview.chromium.org/2876009

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

6 files changed, 112 insertions, 19 deletions

diff --git a/chrome/common/extensions/extension_extent.cc b/chrome/common/extensions/extension_extent.cc
index b479c5b..fe670b6 100644
--- a/chrome/common/extensions/extension_extent.cc
+++ b/chrome/common/extensions/extension_extent.cc
@@ -13,3 +13,18 @@ bool ExtensionExtent::ContainsURL(const GURL& url) const {
 
   return false;
 }
+
+bool ExtensionExtent::OverlapsWith(const ExtensionExtent& other) const {
+  // Two extension extents overlap if there is any one URL that would match at
+  // least one pattern in each of the extents.
+  for (PatternList::const_iterator i = patterns_.begin();
+       i != patterns_.end(); ++i) {
+    for (PatternList::const_iterator j = other.patterns().begin();
+         j != other.patterns().end(); ++j) {
+      if (i->OverlapsWith(*j))
+        return true;
+    }
+  }
+
+  return false;
+}
diff --git a/chrome/common/extensions/extension_extent.h b/chrome/common/extensions/extension_extent.h
index df8d02d..a0117c5 100644
--- a/chrome/common/extensions/extension_extent.h
+++ b/chrome/common/extensions/extension_extent.h
@@ -22,8 +22,12 @@ class ExtensionExtent {
   void AddPattern(const URLPattern& pattern) { patterns_.push_back(pattern); }
   void ClearPaths() { patterns_.clear(); }
 
+  // Test if the extent contains a URL.
   bool ContainsURL(const GURL& url) const;
 
+  // Returns true if there is a single URL that would be in two extents.
+  bool OverlapsWith(const ExtensionExtent& other) const;
+
  private:
   // The list of URL patterns that comprise the extent.
   PatternList patterns_;
diff --git a/chrome/common/extensions/extension_extent_unittest.cc b/chrome/common/extensions/extension_extent_unittest.cc
index 509d83c..89f1f83 100644
--- a/chrome/common/extensions/extension_extent_unittest.cc
+++ b/chrome/common/extensions/extension_extent_unittest.cc
@@ -33,3 +33,23 @@ TEST(ExtensionExtentTest, Two) {
   EXPECT_TRUE(extent.ContainsURL(GURL("http://www.yahoo.com/monkey")));
   EXPECT_FALSE(extent.ContainsURL(GURL("https://www.apple.com/monkey")));
 }
+
+TEST(ExtensionExtentTest, OverlapsWith) {
+  ExtensionExtent extent1;
+  extent1.AddPattern(URLPattern("http://www.google.com/f*"));
+  extent1.AddPattern(URLPattern("http://www.yahoo.com/b*"));
+
+  ExtensionExtent extent2;
+  extent2.AddPattern(URLPattern("http://www.reddit.com/f*"));
+  extent2.AddPattern(URLPattern("http://www.yahoo.com/z*"));
+
+  ExtensionExtent extent3;
+  extent3.AddPattern(URLPattern("http://www.google.com/q/*"));
+  extent3.AddPattern(URLPattern("http://www.yahoo.com/b/*"));
+
+  EXPECT_FALSE(extent1.OverlapsWith(extent2));
+  EXPECT_FALSE(extent2.OverlapsWith(extent1));
+
+  EXPECT_TRUE(extent1.OverlapsWith(extent3));
+  EXPECT_TRUE(extent3.OverlapsWith(extent1));
+}
diff --git a/chrome/common/extensions/url_pattern.cc b/chrome/common/extensions/url_pattern.cc
index 41a5f6e..2b1e4ce 100644
--- a/chrome/common/extensions/url_pattern.cc
+++ b/chrome/common/extensions/url_pattern.cc
@@ -98,7 +98,7 @@ bool URLPattern::MatchesUrl(const GURL &test) const {
   if (!MatchesHost(test))
     return false;
 
-  if (!MatchesPath(test))
+  if (!MatchesPath(test.PathForRequest()))
     return false;
 
   return true;
@@ -143,14 +143,14 @@ bool URLPattern::MatchesHost(const GURL& test) const {
   return test.host()[test.host().length() - host_.length() - 1] == '.';
 }
 
-bool URLPattern::MatchesPath(const GURL& test) const {
+bool URLPattern::MatchesPath(const std::string& test) const {
   if (path_escaped_.empty()) {
     path_escaped_ = path_;
     ReplaceSubstringsAfterOffset(&path_escaped_, 0, "\\", "\\\\");
     ReplaceSubstringsAfterOffset(&path_escaped_, 0, "?", "\\?");
   }
 
-  if (!MatchPatternASCII(test.PathForRequest(), path_escaped_))
+  if (!MatchPatternASCII(test, path_escaped_))
     return false;
 
   return true;
@@ -173,3 +173,25 @@ std::string URLPattern::GetAsString() const {
 
   return spec;
 }
+
+bool URLPattern::OverlapsWith(const URLPattern& other) const {
+  if (scheme_ != other.scheme())
+    return false;
+
+  if (!MatchesHost(other.host()) && !other.MatchesHost(host_))
+    return false;
+
+  // We currently only use OverlapsWith() for the patterns inside
+  // ExtensionExtent. In those cases, we know that the path will have only a
+  // single wildcard at the end. This makes figuring out overlap much easier. It
+  // seems like there is probably a computer-sciency way to solve the general
+  // case, but we don't need that yet.
+  DCHECK(path_.find('*') == path_.size() - 1);
+  DCHECK(other.path().find('*') == other.path().size() - 1);
+
+  if (!MatchesPath(other.path().substr(0, other.path().size() - 1)) &&
+      !other.MatchesPath(path_.substr(0, path_.size() - 1)))
+    return false;
+
+  return true;
+}
diff --git a/chrome/common/extensions/url_pattern.h b/chrome/common/extensions/url_pattern.h
index 30f2c0f..d74520d7 100644
--- a/chrome/common/extensions/url_pattern.h
+++ b/chrome/common/extensions/url_pattern.h
@@ -80,22 +80,6 @@ class URLPattern {
   // Parse() instead, which returns success or failure.
   explicit URLPattern(const std::string& pattern);
 
-  // Initializes this instance by parsing the provided string. On failure, the
-  // instance will have some intermediate values and is in an invalid state.
-  bool Parse(const std::string& pattern_str);
-
-  // Returns true if this instance matches the specified URL.
-  bool MatchesUrl(const GURL& url) const;
-
-  // Returns true if |test| matches our host.
-  bool MatchesHost(const std::string& host) const;
-  bool MatchesHost(const GURL& test) const;
-
-  // Returns true if |test| matches our path.
-  bool MatchesPath(const GURL& test) const;
-
-  std::string GetAsString() const;
-
   // Get the scheme the pattern matches. This will always return a valid scheme
   // if is_valid() returns true.
   std::string scheme() const { return scheme_; }
@@ -118,6 +102,28 @@ class URLPattern {
     path_escaped_ = "";
   }
 
+  // Initializes this instance by parsing the provided string. On failure, the
+  // instance will have some intermediate values and is in an invalid state.
+  bool Parse(const std::string& pattern_str);
+
+  // Returns true if this instance matches the specified URL.
+  bool MatchesUrl(const GURL& url) const;
+
+  // Returns true if |test| matches our host.
+  bool MatchesHost(const std::string& test) const;
+  bool MatchesHost(const GURL& test) const;
+
+  // Returns true if |test| matches our path.
+  bool MatchesPath(const std::string& test) const;
+
+  // Returns a string representing this instance.
+  std::string GetAsString() const;
+
+  // Determine whether there is a URL that would match this instance and another
+  // instance. This method is symmetrical: Calling other.OverlapsWith(this)
+  // would result in the same answer.
+  bool OverlapsWith(const URLPattern& other) const;
+
  private:
   // The scheme for the pattern.
   std::string scheme_;
diff --git a/chrome/common/extensions/url_pattern_unittest.cc b/chrome/common/extensions/url_pattern_unittest.cc
index 8686a0f..c4395bc 100644
--- a/chrome/common/extensions/url_pattern_unittest.cc
+++ b/chrome/common/extensions/url_pattern_unittest.cc
@@ -2,6 +2,7 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include "base/scoped_ptr.h"
 #include "chrome/common/extensions/url_pattern.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
@@ -132,3 +133,28 @@ TEST(URLPatternTest, Match9) {
   EXPECT_TRUE(pattern.MatchesUrl(GURL("chrome://favicon/https://google.com")));
   EXPECT_FALSE(pattern.MatchesUrl(GURL("chrome://history")));
 };
+
+void TestPatternOverlap(const URLPattern& pattern1, const URLPattern& pattern2,
+                        bool expect_overlap) {
+  EXPECT_EQ(expect_overlap, pattern1.OverlapsWith(pattern2))
+      << pattern1.GetAsString() << ", " << pattern2.GetAsString();
+  EXPECT_EQ(expect_overlap, pattern2.OverlapsWith(pattern1))
+      << pattern2.GetAsString() << ", " << pattern1.GetAsString();
+}
+
+TEST(URLPatternTest, OverlapsWith) {
+  URLPattern pattern1("http://www.google.com/foo/*");
+  URLPattern pattern2("https://www.google.com/foo/*");
+  URLPattern pattern3("http://*.google.com/foo/*");
+  URLPattern pattern4("http://*.yahooo.com/foo/*");
+  URLPattern pattern5("http://www.yahooo.com/bar/*");
+  URLPattern pattern6("http://www.yahooo.com/bar/baz/*");
+
+  TestPatternOverlap(pattern1, pattern1, true);
+  TestPatternOverlap(pattern1, pattern2, false);
+  TestPatternOverlap(pattern1, pattern3, true);
+  TestPatternOverlap(pattern1, pattern4, false);
+  TestPatternOverlap(pattern3, pattern4, false);
+  TestPatternOverlap(pattern4, pattern5, false);
+  TestPatternOverlap(pattern5, pattern6, true);
+}