Move extension_error_utils.* and url_pattern_set.* into

top-level extensions dir.

BUG=159265
TBR=ben@chromium.org
NOTRY=true

Review URL: https://codereview.chromium.org/11312228

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

6 files changed, 828 insertions, 1 deletions

diff --git a/extensions/DEPS b/extensions/DEPS
index fd6200f..3a88773 100644
--- a/extensions/DEPS
+++ b/extensions/DEPS
@@ -1,4 +1,5 @@
 include_rules = [
   "+base",
-  "+googleurl"
+  "+googleurl",
+  "+testing"
 ]
diff --git a/extensions/common/error_utils.cc b/extensions/common/error_utils.cc
new file mode 100644
index 0000000..2979184
--- /dev/null
+++ b/extensions/common/error_utils.cc
@@ -0,0 +1,66 @@
+// Copyright (c) 2011 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 "extensions/common/error_utils.h"
+
+#include "base/string_util.h"
+#include "base/utf_string_conversions.h"
+
+namespace extensions {
+
+std::string ErrorUtils::FormatErrorMessage(const std::string& format,
+                                           const std::string& s1) {
+  std::string ret_val = format;
+  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s1);
+  return ret_val;
+}
+
+std::string ErrorUtils::FormatErrorMessage(const std::string& format,
+                                           const std::string& s1,
+                                           const std::string& s2) {
+  std::string ret_val = format;
+  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s1);
+  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s2);
+  return ret_val;
+}
+
+std::string ErrorUtils::FormatErrorMessage(const std::string& format,
+                                           const std::string& s1,
+                                           const std::string& s2,
+                                           const std::string& s3) {
+  std::string ret_val = format;
+  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s1);
+  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s2);
+  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s3);
+  return ret_val;
+}
+
+string16 ErrorUtils::FormatErrorMessageUTF16(const std::string& format,
+                                             const std::string& s1) {
+  std::string ret_val = format;
+  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s1);
+  return UTF8ToUTF16(ret_val);
+}
+
+string16 ErrorUtils::FormatErrorMessageUTF16(const std::string& format,
+                                             const std::string& s1,
+                                             const std::string& s2) {
+  std::string ret_val = format;
+  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s1);
+  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s2);
+  return UTF8ToUTF16(ret_val);
+}
+
+string16 ErrorUtils::FormatErrorMessageUTF16(const std::string& format,
+                                             const std::string& s1,
+                                             const std::string& s2,
+                                             const std::string& s3) {
+  std::string ret_val = format;
+  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s1);
+  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s2);
+  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s3);
+  return UTF8ToUTF16(ret_val);
+}
+
+}  // namespace
diff --git a/extensions/common/error_utils.h b/extensions/common/error_utils.h
new file mode 100644
index 0000000..f63f4da
--- /dev/null
+++ b/extensions/common/error_utils.h
@@ -0,0 +1,44 @@
+// Copyright (c) 2011 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.
+
+#ifndef EXTENSIONS_COMMON_ERROR_UTILS_H_
+#define EXTENSIONS_COMMON_ERROR_UTILS_H_
+
+#include <string>
+
+#include "base/string16.h"
+
+namespace extensions {
+
+class ErrorUtils {
+ public:
+  // Creates an error messages from a pattern.
+  static std::string FormatErrorMessage(const std::string& format,
+                                        const std::string& s1);
+
+  static std::string FormatErrorMessage(const std::string& format,
+                                        const std::string& s1,
+                                        const std::string& s2);
+
+  static std::string FormatErrorMessage(const std::string& format,
+                                        const std::string& s1,
+                                        const std::string& s2,
+                                        const std::string& s3);
+
+  static string16 FormatErrorMessageUTF16(const std::string& format,
+                                          const std::string& s1);
+
+  static string16 FormatErrorMessageUTF16(const std::string& format,
+                                          const std::string& s1,
+                                          const std::string& s2);
+
+  static string16 FormatErrorMessageUTF16(const std::string& format,
+                                          const std::string& s1,
+                                          const std::string& s2,
+                                          const std::string& s3);
+};
+
+}  // namespace extensions
+
+#endif  // EXTENSIONS_COMMON_ERROR_UTILS_H_
diff --git a/extensions/common/url_pattern_set.cc b/extensions/common/url_pattern_set.cc
new file mode 100644
index 0000000..4066320
--- /dev/null
+++ b/extensions/common/url_pattern_set.cc
@@ -0,0 +1,219 @@
+// Copyright (c) 2012 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 "extensions/common/url_pattern_set.h"
+
+#include <algorithm>
+#include <iterator>
+
+#include "base/logging.h"
+#include "base/memory/linked_ptr.h"
+#include "base/values.h"
+#include "content/public/common/url_constants.h"
+#include "extensions/common/error_utils.h"
+#include "extensions/common/url_pattern.h"
+#include "googleurl/src/gurl.h"
+
+namespace extensions {
+
+namespace {
+
+const char kInvalidURLPatternError[] = "Invalid url pattern '*'";
+
+}  // namespace
+
+// static
+void URLPatternSet::CreateDifference(const URLPatternSet& set1,
+                                     const URLPatternSet& set2,
+                                     URLPatternSet* out) {
+  out->ClearPatterns();
+  std::set_difference(set1.patterns_.begin(), set1.patterns_.end(),
+                      set2.patterns_.begin(), set2.patterns_.end(),
+                      std::inserter<std::set<URLPattern> >(
+                          out->patterns_, out->patterns_.begin()));
+}
+
+// static
+void URLPatternSet::CreateIntersection(const URLPatternSet& set1,
+                                       const URLPatternSet& set2,
+                                       URLPatternSet* out) {
+  out->ClearPatterns();
+  std::set_intersection(set1.patterns_.begin(), set1.patterns_.end(),
+                        set2.patterns_.begin(), set2.patterns_.end(),
+                        std::inserter<std::set<URLPattern> >(
+                            out->patterns_, out->patterns_.begin()));
+}
+
+// static
+void URLPatternSet::CreateUnion(const URLPatternSet& set1,
+                                const URLPatternSet& set2,
+                                URLPatternSet* out) {
+  out->ClearPatterns();
+  std::set_union(set1.patterns_.begin(), set1.patterns_.end(),
+                 set2.patterns_.begin(), set2.patterns_.end(),
+                 std::inserter<std::set<URLPattern> >(
+                     out->patterns_, out->patterns_.begin()));
+}
+
+// static
+void URLPatternSet::CreateUnion(const std::vector<URLPatternSet>& sets,
+                                URLPatternSet* out) {
+  out->ClearPatterns();
+  if (sets.empty())
+    return;
+
+  // N-way union algorithm is basic O(nlog(n)) merge algorithm.
+  //
+  // Do the first merge step into a working set so that we don't mutate any of
+  // the input.
+  std::vector<URLPatternSet> working;
+  for (size_t i = 0; i < sets.size(); i += 2) {
+    if (i + 1 < sets.size()) {
+      URLPatternSet u;
+      URLPatternSet::CreateUnion(sets[i], sets[i + 1], &u);
+      working.push_back(u);
+    } else {
+      working.push_back(sets[i]);
+    }
+  }
+
+  for (size_t skip = 1; skip < working.size(); skip *= 2) {
+    for (size_t i = 0; i < (working.size() - skip); i += skip) {
+      URLPatternSet u;
+      URLPatternSet::CreateUnion(working[i], working[i + skip], &u);
+      working[i].patterns_.swap(u.patterns_);
+    }
+  }
+
+  out->patterns_.swap(working[0].patterns_);
+}
+
+URLPatternSet::URLPatternSet() {}
+
+URLPatternSet::URLPatternSet(const URLPatternSet& rhs)
+    : patterns_(rhs.patterns_) {}
+
+URLPatternSet::URLPatternSet(const std::set<URLPattern>& patterns)
+    : patterns_(patterns) {}
+
+URLPatternSet::~URLPatternSet() {}
+
+URLPatternSet& URLPatternSet::operator=(const URLPatternSet& rhs) {
+  patterns_ = rhs.patterns_;
+  return *this;
+}
+
+bool URLPatternSet::operator==(const URLPatternSet& other) const {
+  return patterns_ == other.patterns_;
+}
+
+bool URLPatternSet::is_empty() const {
+  return patterns_.empty();
+}
+
+size_t URLPatternSet::size() const {
+  return patterns_.size();
+}
+
+bool URLPatternSet::AddPattern(const URLPattern& pattern) {
+  return patterns_.insert(pattern).second;
+}
+
+void URLPatternSet::AddPatterns(const URLPatternSet& set) {
+  patterns_.insert(set.patterns().begin(),
+                   set.patterns().end());
+}
+
+void URLPatternSet::ClearPatterns() {
+  patterns_.clear();
+}
+
+bool URLPatternSet::Contains(const URLPatternSet& set) const {
+  return std::includes(patterns_.begin(), patterns_.end(),
+                       set.patterns_.begin(), set.patterns_.end());
+}
+
+bool URLPatternSet::MatchesURL(const GURL& url) const {
+  for (URLPatternSet::const_iterator pattern = patterns_.begin();
+       pattern != patterns_.end(); ++pattern) {
+    if (pattern->MatchesURL(url))
+      return true;
+  }
+
+  return false;
+}
+
+bool URLPatternSet::MatchesSecurityOrigin(const GURL& origin) const {
+  for (URLPatternSet::const_iterator pattern = patterns_.begin();
+       pattern != patterns_.end(); ++pattern) {
+    if (pattern->MatchesSecurityOrigin(origin))
+      return true;
+  }
+
+  return false;
+}
+
+bool URLPatternSet::OverlapsWith(const URLPatternSet& 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 (URLPatternSet::const_iterator i = patterns_.begin();
+       i != patterns_.end(); ++i) {
+    for (URLPatternSet::const_iterator j = other.patterns().begin();
+         j != other.patterns().end(); ++j) {
+      if (i->OverlapsWith(*j))
+        return true;
+    }
+  }
+
+  return false;
+}
+
+scoped_ptr<base::ListValue> URLPatternSet::ToValue() const {
+  scoped_ptr<ListValue> value(new ListValue);
+  for (URLPatternSet::const_iterator i = patterns_.begin();
+       i != patterns_.end(); ++i)
+    value->AppendIfNotPresent(Value::CreateStringValue(i->GetAsString()));
+  return value.Pass();
+}
+
+bool URLPatternSet::Populate(const std::vector<std::string>& patterns,
+                             int valid_schemes,
+                             bool allow_file_access,
+                             std::string* error) {
+  ClearPatterns();
+  for (size_t i = 0; i < patterns.size(); ++i) {
+    URLPattern pattern(valid_schemes);
+    if (pattern.Parse(patterns[i]) != URLPattern::PARSE_SUCCESS) {
+      if (error) {
+        *error = ErrorUtils::FormatErrorMessage(kInvalidURLPatternError,
+                                                patterns[i]);
+      } else {
+        LOG(ERROR) << "Invalid url pattern: " << patterns[i];
+      }
+      return false;
+    }
+    if (!allow_file_access && pattern.MatchesScheme(chrome::kFileScheme)) {
+      pattern.SetValidSchemes(
+          pattern.valid_schemes() & ~URLPattern::SCHEME_FILE);
+    }
+    AddPattern(pattern);
+  }
+  return true;
+}
+
+bool URLPatternSet::Populate(const base::ListValue& value,
+                             int valid_schemes,
+                             bool allow_file_access,
+                             std::string* error) {
+  std::vector<std::string> patterns;
+  for (size_t i = 0; i < value.GetSize(); ++i) {
+    std::string item;
+    if (!value.GetString(i, &item))
+      return false;
+    patterns.push_back(item);
+  }
+  return Populate(patterns, valid_schemes, allow_file_access, error);
+}
+
+}  // namespace extensions
diff --git a/extensions/common/url_pattern_set.h b/extensions/common/url_pattern_set.h
new file mode 100644
index 0000000..2f71139
--- /dev/null
+++ b/extensions/common/url_pattern_set.h
@@ -0,0 +1,101 @@
+// Copyright (c) 2012 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.
+
+#ifndef EXTENSIONS_COMMMON_URL_PATTERN_SET_H_
+#define EXTENSIONS_COMMMON_URL_PATTERN_SET_H_
+
+#include <set>
+
+#include "base/memory/scoped_ptr.h"
+#include "extensions/common/url_pattern.h"
+
+class GURL;
+
+namespace base {
+class ListValue;
+class Value;
+}
+
+namespace extensions {
+
+// Represents the set of URLs an extension uses for web content.
+class URLPatternSet {
+ public:
+  typedef std::set<URLPattern>::const_iterator const_iterator;
+  typedef std::set<URLPattern>::iterator iterator;
+
+  // Clears |out| and populates the set with |set1| - |set2|.
+  static void CreateDifference(const URLPatternSet& set1,
+                               const URLPatternSet& set2,
+                               URLPatternSet* out);
+
+  // Clears |out| and populates the set with the intersection of |set1|
+  // and |set2|.
+  static void CreateIntersection(const URLPatternSet& set1,
+                                 const URLPatternSet& set2,
+                                 URLPatternSet* out);
+
+  // Clears |out| and populates the set with the union of |set1| and |set2|.
+  static void CreateUnion(const URLPatternSet& set1,
+                          const URLPatternSet& set2,
+                          URLPatternSet* out);
+
+  // Clears |out| and populates it with the union of all sets in |sets|.
+  static void CreateUnion(const std::vector<URLPatternSet>& sets,
+                          URLPatternSet* out);
+
+  URLPatternSet();
+  URLPatternSet(const URLPatternSet& rhs);
+  explicit URLPatternSet(const std::set<URLPattern>& patterns);
+  ~URLPatternSet();
+
+  URLPatternSet& operator=(const URLPatternSet& rhs);
+  bool operator==(const URLPatternSet& rhs) const;
+
+  bool is_empty() const;
+  size_t size() const;
+  const std::set<URLPattern>& patterns() const { return patterns_; }
+  const_iterator begin() const { return patterns_.begin(); }
+  const_iterator end() const { return patterns_.end(); }
+
+  // Adds a pattern to the set. Returns true if a new pattern was inserted,
+  // false if the pattern was already in the set.
+  bool AddPattern(const URLPattern& pattern);
+
+  // Adds all patterns from |set| into this.
+  void AddPatterns(const URLPatternSet& set);
+
+  void ClearPatterns();
+
+  // Returns true if the permission |set| is a subset of this.
+  bool Contains(const URLPatternSet& set) const;
+
+  // Test if the extent contains a URL.
+  bool MatchesURL(const GURL& url) const;
+
+  bool MatchesSecurityOrigin(const GURL& origin) const;
+
+  // Returns true if there is a single URL that would be in two extents.
+  bool OverlapsWith(const URLPatternSet& other) const;
+
+  // Converts to and from Value for serialization to preferences.
+  scoped_ptr<base::ListValue> ToValue() const;
+  bool Populate(const base::ListValue& value,
+                int valid_schemes,
+                bool allow_file_access,
+                std::string* error);
+
+  bool Populate(const std::vector<std::string>& patterns,
+                int valid_schemes,
+                bool allow_file_access,
+                std::string* error);
+
+ private:
+  // The list of URL patterns that comprise the extent.
+  std::set<URLPattern> patterns_;
+};
+
+}  // namespace extensions
+
+#endif  // EXTENSIONS_COMMMON_URL_PATTERN_SET_H_
diff --git a/extensions/common/url_pattern_set_unittest.cc b/extensions/common/url_pattern_set_unittest.cc
new file mode 100644
index 0000000..55564cf
--- /dev/null
+++ b/extensions/common/url_pattern_set_unittest.cc
@@ -0,0 +1,396 @@
+// Copyright (c) 2012 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 "extensions/common/url_pattern_set.h"
+
+#include "base/values.h"
+#include "googleurl/src/gurl.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace extensions {
+
+namespace {
+
+void AddPattern(URLPatternSet* set, const std::string& pattern) {
+  int schemes = URLPattern::SCHEME_ALL;
+  set->AddPattern(URLPattern(schemes, pattern));
+}
+
+URLPatternSet Patterns(const std::string& pattern) {
+  URLPatternSet set;
+  AddPattern(&set, pattern);
+  return set;
+}
+
+URLPatternSet Patterns(const std::string& pattern1,
+                       const std::string& pattern2) {
+  URLPatternSet set;
+  AddPattern(&set, pattern1);
+  AddPattern(&set, pattern2);
+  return set;
+}
+
+}
+
+TEST(URLPatternSetTest, Empty) {
+  URLPatternSet set;
+  EXPECT_FALSE(set.MatchesURL(GURL("http://www.foo.com/bar")));
+  EXPECT_FALSE(set.MatchesURL(GURL()));
+  EXPECT_FALSE(set.MatchesURL(GURL("invalid")));
+}
+
+TEST(URLPatternSetTest, One) {
+  URLPatternSet set;
+  AddPattern(&set, "http://www.google.com/*");
+
+  EXPECT_TRUE(set.MatchesURL(GURL("http://www.google.com/")));
+  EXPECT_TRUE(set.MatchesURL(GURL("http://www.google.com/monkey")));
+  EXPECT_FALSE(set.MatchesURL(GURL("https://www.google.com/")));
+  EXPECT_FALSE(set.MatchesURL(GURL("https://www.microsoft.com/")));
+}
+
+TEST(URLPatternSetTest, Two) {
+  URLPatternSet set;
+  AddPattern(&set, "http://www.google.com/*");
+  AddPattern(&set, "http://www.yahoo.com/*");
+
+  EXPECT_TRUE(set.MatchesURL(GURL("http://www.google.com/monkey")));
+  EXPECT_TRUE(set.MatchesURL(GURL("http://www.yahoo.com/monkey")));
+  EXPECT_FALSE(set.MatchesURL(GURL("https://www.apple.com/monkey")));
+}
+
+TEST(URLPatternSetTest, OverlapsWith) {
+  URLPatternSet set1;
+  AddPattern(&set1, "http://www.google.com/f*");
+  AddPattern(&set1, "http://www.yahoo.com/b*");
+
+  URLPatternSet set2;
+  AddPattern(&set2, "http://www.reddit.com/f*");
+  AddPattern(&set2, "http://www.yahoo.com/z*");
+
+  URLPatternSet set3;
+  AddPattern(&set3, "http://www.google.com/q/*");
+  AddPattern(&set3, "http://www.yahoo.com/b/*");
+
+  EXPECT_FALSE(set1.OverlapsWith(set2));
+  EXPECT_FALSE(set2.OverlapsWith(set1));
+
+  EXPECT_TRUE(set1.OverlapsWith(set3));
+  EXPECT_TRUE(set3.OverlapsWith(set1));
+}
+
+TEST(URLPatternSetTest, CreateDifference) {
+  URLPatternSet expected;
+  URLPatternSet set1;
+  URLPatternSet set2;
+  AddPattern(&set1, "http://www.google.com/f*");
+  AddPattern(&set1, "http://www.yahoo.com/b*");
+
+  // Subtract an empty set.
+  URLPatternSet result;
+  URLPatternSet::CreateDifference(set1, set2, &result);
+  EXPECT_EQ(set1, result);
+
+  // Subtract a real set.
+  AddPattern(&set2, "http://www.reddit.com/f*");
+  AddPattern(&set2, "http://www.yahoo.com/z*");
+  AddPattern(&set2, "http://www.google.com/f*");
+
+  AddPattern(&expected, "http://www.yahoo.com/b*");
+
+  result.ClearPatterns();
+  URLPatternSet::CreateDifference(set1, set2, &result);
+  EXPECT_EQ(expected, result);
+  EXPECT_FALSE(result.is_empty());
+  EXPECT_TRUE(set1.Contains(result));
+  EXPECT_FALSE(result.Contains(set2));
+  EXPECT_FALSE(set2.Contains(result));
+
+  URLPatternSet intersection;
+  URLPatternSet::CreateIntersection(result, set2, &intersection);
+  EXPECT_TRUE(intersection.is_empty());
+}
+
+TEST(URLPatternSetTest, CreateIntersection) {
+  URLPatternSet empty_set;
+  URLPatternSet expected;
+  URLPatternSet set1;
+  AddPattern(&set1, "http://www.google.com/f*");
+  AddPattern(&set1, "http://www.yahoo.com/b*");
+
+  // Intersection with an empty set.
+  URLPatternSet result;
+  URLPatternSet::CreateIntersection(set1, empty_set, &result);
+  EXPECT_EQ(expected, result);
+  EXPECT_TRUE(result.is_empty());
+  EXPECT_TRUE(empty_set.Contains(result));
+  EXPECT_TRUE(result.Contains(empty_set));
+  EXPECT_TRUE(set1.Contains(result));
+
+  // Intersection with a real set.
+  URLPatternSet set2;
+  AddPattern(&set2, "http://www.reddit.com/f*");
+  AddPattern(&set2, "http://www.yahoo.com/z*");
+  AddPattern(&set2, "http://www.google.com/f*");
+
+  AddPattern(&expected, "http://www.google.com/f*");
+
+  result.ClearPatterns();
+  URLPatternSet::CreateIntersection(set1, set2, &result);
+  EXPECT_EQ(expected, result);
+  EXPECT_FALSE(result.is_empty());
+  EXPECT_TRUE(set1.Contains(result));
+  EXPECT_TRUE(set2.Contains(result));
+}
+
+TEST(URLPatternSetTest, CreateUnion) {
+  URLPatternSet empty_set;
+
+  URLPatternSet set1;
+  AddPattern(&set1, "http://www.google.com/f*");
+  AddPattern(&set1, "http://www.yahoo.com/b*");
+
+  URLPatternSet expected;
+  AddPattern(&expected, "http://www.google.com/f*");
+  AddPattern(&expected, "http://www.yahoo.com/b*");
+
+  // Union with an empty set.
+  URLPatternSet result;
+  URLPatternSet::CreateUnion(set1, empty_set, &result);
+  EXPECT_EQ(expected, result);
+
+  // Union with a real set.
+  URLPatternSet set2;
+  AddPattern(&set2, "http://www.reddit.com/f*");
+  AddPattern(&set2, "http://www.yahoo.com/z*");
+  AddPattern(&set2, "http://www.google.com/f*");
+
+  AddPattern(&expected, "http://www.reddit.com/f*");
+  AddPattern(&expected, "http://www.yahoo.com/z*");
+
+  result.ClearPatterns();
+  URLPatternSet::CreateUnion(set1, set2, &result);
+  EXPECT_EQ(expected, result);
+}
+
+TEST(URLPatternSetTest, Contains) {
+  URLPatternSet set1;
+  URLPatternSet set2;
+  URLPatternSet empty_set;
+
+  AddPattern(&set1, "http://www.google.com/*");
+  AddPattern(&set1, "http://www.yahoo.com/*");
+
+  AddPattern(&set2, "http://www.reddit.com/*");
+
+  EXPECT_FALSE(set1.Contains(set2));
+  EXPECT_TRUE(set1.Contains(empty_set));
+  EXPECT_FALSE(empty_set.Contains(set1));
+
+  AddPattern(&set2, "http://www.yahoo.com/*");
+
+  EXPECT_FALSE(set1.Contains(set2));
+  EXPECT_FALSE(set2.Contains(set1));
+
+  AddPattern(&set2, "http://www.google.com/*");
+
+  EXPECT_FALSE(set1.Contains(set2));
+  EXPECT_TRUE(set2.Contains(set1));
+
+  // Note that this just checks pattern equality, and not if individual patterns
+  // contain other patterns. For example:
+  AddPattern(&set1, "http://*.reddit.com/*");
+  EXPECT_FALSE(set1.Contains(set2));
+  EXPECT_FALSE(set2.Contains(set1));
+}
+
+TEST(URLPatternSetTest, Duplicates) {
+  URLPatternSet set1;
+  URLPatternSet set2;
+
+  AddPattern(&set1, "http://www.google.com/*");
+  AddPattern(&set2, "http://www.google.com/*");
+
+  AddPattern(&set1, "http://www.google.com/*");
+
+  // The sets should still be equal after adding a duplicate.
+  EXPECT_EQ(set2, set1);
+}
+
+TEST(URLPatternSetTest, ToValueAndPopulate) {
+  URLPatternSet set1;
+  URLPatternSet set2;
+
+  std::vector<std::string> patterns;
+  patterns.push_back("http://www.google.com/*");
+  patterns.push_back("http://www.yahoo.com/*");
+
+  for (size_t i = 0; i < patterns.size(); ++i)
+    AddPattern(&set1, patterns[i]);
+
+  std::string error;
+  bool allow_file_access = false;
+  scoped_ptr<base::ListValue> value(set1.ToValue());
+  set2.Populate(*value, URLPattern::SCHEME_ALL, allow_file_access, &error);
+  EXPECT_EQ(set1, set2);
+
+  set2.ClearPatterns();
+  set2.Populate(patterns, URLPattern::SCHEME_ALL, allow_file_access, &error);
+  EXPECT_EQ(set1, set2);
+}
+
+TEST(URLPatternSetTest, NwayUnion) {
+  std::string google_a = "http://www.google.com/a*";
+  std::string google_b = "http://www.google.com/b*";
+  std::string google_c = "http://www.google.com/c*";
+  std::string yahoo_a = "http://www.yahoo.com/a*";
+  std::string yahoo_b = "http://www.yahoo.com/b*";
+  std::string yahoo_c = "http://www.yahoo.com/c*";
+  std::string reddit_a = "http://www.reddit.com/a*";
+  std::string reddit_b = "http://www.reddit.com/b*";
+  std::string reddit_c = "http://www.reddit.com/c*";
+
+  // Empty list.
+  {
+    std::vector<URLPatternSet> empty;
+
+    URLPatternSet result;
+    URLPatternSet::CreateUnion(empty, &result);
+
+    URLPatternSet expected;
+    EXPECT_EQ(expected, result);
+  }
+
+  // Singleton list.
+  {
+    std::vector<URLPatternSet> test;
+    test.push_back(Patterns(google_a));
+
+    URLPatternSet result;
+    URLPatternSet::CreateUnion(test, &result);
+
+    URLPatternSet expected = Patterns(google_a);
+    EXPECT_EQ(expected, result);
+  }
+
+  // List with 2 elements.
+  {
+
+    std::vector<URLPatternSet> test;
+    test.push_back(Patterns(google_a, google_b));
+    test.push_back(Patterns(google_b, google_c));
+
+    URLPatternSet result;
+    URLPatternSet::CreateUnion(test, &result);
+
+    URLPatternSet expected;
+    AddPattern(&expected, google_a);
+    AddPattern(&expected, google_b);
+    AddPattern(&expected, google_c);
+    EXPECT_EQ(expected, result);
+  }
+
+  // List with 3 elements.
+  {
+    std::vector<URLPatternSet> test;
+    test.push_back(Patterns(google_a, google_b));
+    test.push_back(Patterns(google_b, google_c));
+    test.push_back(Patterns(yahoo_a, yahoo_b));
+
+    URLPatternSet result;
+    URLPatternSet::CreateUnion(test, &result);
+
+    URLPatternSet expected;
+    AddPattern(&expected, google_a);
+    AddPattern(&expected, google_b);
+    AddPattern(&expected, google_c);
+    AddPattern(&expected, yahoo_a);
+    AddPattern(&expected, yahoo_b);
+    EXPECT_EQ(expected, result);
+  }
+
+  // List with 7 elements.
+  {
+    std::vector<URLPatternSet> test;
+    test.push_back(Patterns(google_a));
+    test.push_back(Patterns(google_b));
+    test.push_back(Patterns(google_c));
+    test.push_back(Patterns(yahoo_a));
+    test.push_back(Patterns(yahoo_b));
+    test.push_back(Patterns(yahoo_c));
+    test.push_back(Patterns(reddit_a));
+
+    URLPatternSet result;
+    URLPatternSet::CreateUnion(test, &result);
+
+    URLPatternSet expected;
+    AddPattern(&expected, google_a);
+    AddPattern(&expected, google_b);
+    AddPattern(&expected, google_c);
+    AddPattern(&expected, yahoo_a);
+    AddPattern(&expected, yahoo_b);
+    AddPattern(&expected, yahoo_c);
+    AddPattern(&expected, reddit_a);
+    EXPECT_EQ(expected, result);
+  }
+
+  // List with 8 elements.
+  {
+    std::vector<URLPatternSet> test;
+    test.push_back(Patterns(google_a));
+    test.push_back(Patterns(google_b));
+    test.push_back(Patterns(google_c));
+    test.push_back(Patterns(yahoo_a));
+    test.push_back(Patterns(yahoo_b));
+    test.push_back(Patterns(yahoo_c));
+    test.push_back(Patterns(reddit_a));
+    test.push_back(Patterns(reddit_b));
+
+    URLPatternSet result;
+    URLPatternSet::CreateUnion(test, &result);
+
+    URLPatternSet expected;
+    AddPattern(&expected, google_a);
+    AddPattern(&expected, google_b);
+    AddPattern(&expected, google_c);
+    AddPattern(&expected, yahoo_a);
+    AddPattern(&expected, yahoo_b);
+    AddPattern(&expected, yahoo_c);
+    AddPattern(&expected, reddit_a);
+    AddPattern(&expected, reddit_b);
+    EXPECT_EQ(expected, result);
+  }
+
+  // List with 9 elements.
+  {
+
+    std::vector<URLPatternSet> test;
+    test.push_back(Patterns(google_a));
+    test.push_back(Patterns(google_b));
+    test.push_back(Patterns(google_c));
+    test.push_back(Patterns(yahoo_a));
+    test.push_back(Patterns(yahoo_b));
+    test.push_back(Patterns(yahoo_c));
+    test.push_back(Patterns(reddit_a));
+    test.push_back(Patterns(reddit_b));
+    test.push_back(Patterns(reddit_c));
+
+    URLPatternSet result;
+    URLPatternSet::CreateUnion(test, &result);
+
+    URLPatternSet expected;
+    AddPattern(&expected, google_a);
+    AddPattern(&expected, google_b);
+    AddPattern(&expected, google_c);
+    AddPattern(&expected, yahoo_a);
+    AddPattern(&expected, yahoo_b);
+    AddPattern(&expected, yahoo_c);
+    AddPattern(&expected, reddit_a);
+    AddPattern(&expected, reddit_b);
+    AddPattern(&expected, reddit_c);
+    EXPECT_EQ(expected, result);
+  }
+}
+
+}  // namespace extensions