1 // Copyright (c) 2012 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.
5 #include "extensions/common/url_pattern_set.h"
10 #include "base/logging.h"
11 #include "base/memory/linked_ptr.h"
12 #include "base/stl_util.h"
13 #include "base/values.h"
14 #include "content/public/common/url_constants.h"
15 #include "extensions/common/error_utils.h"
16 #include "extensions/common/url_pattern.h"
19 namespace extensions {
23 const char kInvalidURLPatternError[] = "Invalid url pattern '*'";
28 void URLPatternSet::CreateDifference(const URLPatternSet& set1,
29 const URLPatternSet& set2,
32 out->patterns_ = base::STLSetDifference<std::set<URLPattern> >(
33 set1.patterns_, set2.patterns_);
37 void URLPatternSet::CreateIntersection(const URLPatternSet& set1,
38 const URLPatternSet& set2,
41 std::set_intersection(set1.patterns_.begin(), set1.patterns_.end(),
42 set2.patterns_.begin(), set2.patterns_.end(),
43 std::inserter<std::set<URLPattern> >(
44 out->patterns_, out->patterns_.begin()));
48 void URLPatternSet::CreateUnion(const URLPatternSet& set1,
49 const URLPatternSet& set2,
52 std::set_union(set1.patterns_.begin(), set1.patterns_.end(),
53 set2.patterns_.begin(), set2.patterns_.end(),
54 std::inserter<std::set<URLPattern> >(
55 out->patterns_, out->patterns_.begin()));
59 void URLPatternSet::CreateUnion(const std::vector<URLPatternSet>& sets,
65 // N-way union algorithm is basic O(nlog(n)) merge algorithm.
67 // Do the first merge step into a working set so that we don't mutate any of
69 std::vector<URLPatternSet> working;
70 for (size_t i = 0; i < sets.size(); i += 2) {
71 if (i + 1 < sets.size()) {
73 URLPatternSet::CreateUnion(sets[i], sets[i + 1], &u);
76 working.push_back(sets[i]);
80 for (size_t skip = 1; skip < working.size(); skip *= 2) {
81 for (size_t i = 0; i < (working.size() - skip); i += skip) {
83 URLPatternSet::CreateUnion(working[i], working[i + skip], &u);
84 working[i].patterns_.swap(u.patterns_);
88 out->patterns_.swap(working[0].patterns_);
91 URLPatternSet::URLPatternSet() {}
93 URLPatternSet::URLPatternSet(const URLPatternSet& rhs)
94 : patterns_(rhs.patterns_) {}
96 URLPatternSet::URLPatternSet(const std::set<URLPattern>& patterns)
97 : patterns_(patterns) {}
99 URLPatternSet::~URLPatternSet() {}
101 URLPatternSet& URLPatternSet::operator=(const URLPatternSet& rhs) {
102 patterns_ = rhs.patterns_;
106 bool URLPatternSet::operator==(const URLPatternSet& other) const {
107 return patterns_ == other.patterns_;
110 bool URLPatternSet::is_empty() const {
111 return patterns_.empty();
114 size_t URLPatternSet::size() const {
115 return patterns_.size();
118 bool URLPatternSet::AddPattern(const URLPattern& pattern) {
119 return patterns_.insert(pattern).second;
122 void URLPatternSet::AddPatterns(const URLPatternSet& set) {
123 patterns_.insert(set.patterns().begin(),
124 set.patterns().end());
127 void URLPatternSet::ClearPatterns() {
131 bool URLPatternSet::Contains(const URLPatternSet& other) const {
132 for (URLPatternSet::const_iterator it = other.begin();
133 it != other.end(); ++it) {
134 if (!ContainsPattern(*it))
141 bool URLPatternSet::ContainsPattern(const URLPattern& pattern) const {
142 for (URLPatternSet::const_iterator it = begin();
144 if (it->Contains(pattern))
150 bool URLPatternSet::MatchesURL(const GURL& url) const {
151 for (URLPatternSet::const_iterator pattern = patterns_.begin();
152 pattern != patterns_.end(); ++pattern) {
153 if (pattern->MatchesURL(url))
160 bool URLPatternSet::MatchesSecurityOrigin(const GURL& origin) const {
161 for (URLPatternSet::const_iterator pattern = patterns_.begin();
162 pattern != patterns_.end(); ++pattern) {
163 if (pattern->MatchesSecurityOrigin(origin))
170 bool URLPatternSet::OverlapsWith(const URLPatternSet& other) const {
171 // Two extension extents overlap if there is any one URL that would match at
172 // least one pattern in each of the extents.
173 for (URLPatternSet::const_iterator i = patterns_.begin();
174 i != patterns_.end(); ++i) {
175 for (URLPatternSet::const_iterator j = other.patterns().begin();
176 j != other.patterns().end(); ++j) {
177 if (i->OverlapsWith(*j))
185 scoped_ptr<base::ListValue> URLPatternSet::ToValue() const {
186 scoped_ptr<base::ListValue> value(new base::ListValue);
187 for (URLPatternSet::const_iterator i = patterns_.begin();
188 i != patterns_.end(); ++i)
189 value->AppendIfNotPresent(new base::StringValue(i->GetAsString()));
193 bool URLPatternSet::Populate(const std::vector<std::string>& patterns,
195 bool allow_file_access,
196 std::string* error) {
198 for (size_t i = 0; i < patterns.size(); ++i) {
199 URLPattern pattern(valid_schemes);
200 if (pattern.Parse(patterns[i]) != URLPattern::PARSE_SUCCESS) {
202 *error = ErrorUtils::FormatErrorMessage(kInvalidURLPatternError,
205 LOG(ERROR) << "Invalid url pattern: " << patterns[i];
209 if (!allow_file_access && pattern.MatchesScheme(content::kFileScheme)) {
210 pattern.SetValidSchemes(
211 pattern.valid_schemes() & ~URLPattern::SCHEME_FILE);
218 bool URLPatternSet::Populate(const base::ListValue& value,
220 bool allow_file_access,
221 std::string* error) {
222 std::vector<std::string> patterns;
223 for (size_t i = 0; i < value.GetSize(); ++i) {
225 if (!value.GetString(i, &item))
227 patterns.push_back(item);
229 return Populate(patterns, valid_schemes, allow_file_access, error);
232 } // namespace extensions