url_pattern_set.cc revision 6e8cce623b6e4fe0c9e4af605d675dd9d0338c38 
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.
4
5#include "extensions/common/url_pattern_set.h"
6
7#include <iterator>
8#include <ostream>
9
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 "extensions/common/error_utils.h"
15#include "extensions/common/url_pattern.h"
16#include "url/gurl.h"
17#include "url/url_constants.h"
18
19namespace extensions {
20
21namespace {
22
23const char kInvalidURLPatternError[] = "Invalid url pattern '*'";
24
25}  // namespace
26
27// static
28void URLPatternSet::CreateDifference(const URLPatternSet& set1,
29                                     const URLPatternSet& set2,
30                                     URLPatternSet* out) {
31  out->patterns_ = base::STLSetDifference<std::set<URLPattern> >(
32      set1.patterns_, set2.patterns_);
33}
34
35// static
36void URLPatternSet::CreateIntersection(const URLPatternSet& set1,
37                                       const URLPatternSet& set2,
38                                       URLPatternSet* out) {
39  out->patterns_ = base::STLSetIntersection<std::set<URLPattern> >(
40      set1.patterns_, set2.patterns_);
41}
42
43// static
44void URLPatternSet::CreateUnion(const URLPatternSet& set1,
45                                const URLPatternSet& set2,
46                                URLPatternSet* out) {
47  out->patterns_ = base::STLSetUnion<std::set<URLPattern> >(
48      set1.patterns_, set2.patterns_);
49}
50
51// static
52void URLPatternSet::CreateUnion(const std::vector<URLPatternSet>& sets,
53                                URLPatternSet* out) {
54  out->ClearPatterns();
55  if (sets.empty())
56    return;
57
58  // N-way union algorithm is basic O(nlog(n)) merge algorithm.
59  //
60  // Do the first merge step into a working set so that we don't mutate any of
61  // the input.
62  std::vector<URLPatternSet> working;
63  for (size_t i = 0; i < sets.size(); i += 2) {
64    if (i + 1 < sets.size()) {
65      URLPatternSet u;
66      URLPatternSet::CreateUnion(sets[i], sets[i + 1], &u);
67      working.push_back(u);
68    } else {
69      working.push_back(sets[i]);
70    }
71  }
72
73  for (size_t skip = 1; skip < working.size(); skip *= 2) {
74    for (size_t i = 0; i < (working.size() - skip); i += skip) {
75      URLPatternSet u;
76      URLPatternSet::CreateUnion(working[i], working[i + skip], &u);
77      working[i].patterns_.swap(u.patterns_);
78    }
79  }
80
81  out->patterns_.swap(working[0].patterns_);
82}
83
84URLPatternSet::URLPatternSet() {}
85
86URLPatternSet::URLPatternSet(const URLPatternSet& rhs)
87    : patterns_(rhs.patterns_) {}
88
89URLPatternSet::URLPatternSet(const std::set<URLPattern>& patterns)
90    : patterns_(patterns) {}
91
92URLPatternSet::~URLPatternSet() {}
93
94URLPatternSet& URLPatternSet::operator=(const URLPatternSet& rhs) {
95  patterns_ = rhs.patterns_;
96  return *this;
97}
98
99bool URLPatternSet::operator==(const URLPatternSet& other) const {
100  return patterns_ == other.patterns_;
101}
102
103std::ostream& operator<<(std::ostream& out,
104                         const URLPatternSet& url_pattern_set) {
105  out << "{ ";
106
107  std::set<URLPattern>::const_iterator iter =
108      url_pattern_set.patterns().begin();
109  if (!url_pattern_set.patterns().empty()) {
110    out << *iter;
111    ++iter;
112  }
113
114  for (;iter != url_pattern_set.patterns().end(); ++iter)
115    out << ", " << *iter;
116
117  if (!url_pattern_set.patterns().empty())
118    out << " ";
119
120  out << "}";
121  return out;
122}
123
124bool URLPatternSet::is_empty() const {
125  return patterns_.empty();
126}
127
128size_t URLPatternSet::size() const {
129  return patterns_.size();
130}
131
132bool URLPatternSet::AddPattern(const URLPattern& pattern) {
133  return patterns_.insert(pattern).second;
134}
135
136void URLPatternSet::AddPatterns(const URLPatternSet& set) {
137  patterns_.insert(set.patterns().begin(),
138                   set.patterns().end());
139}
140
141void URLPatternSet::ClearPatterns() {
142  patterns_.clear();
143}
144
145bool URLPatternSet::AddOrigin(int valid_schemes, const GURL& origin) {
146  DCHECK_EQ(origin.GetOrigin(), origin);
147  URLPattern origin_pattern(valid_schemes);
148  // Origin adding could fail if |origin| does not match |valid_schemes|.
149  if (origin_pattern.Parse(origin.GetOrigin().spec()) !=
150      URLPattern::PARSE_SUCCESS) {
151    return false;
152  }
153  origin_pattern.SetPath("/*");
154  return AddPattern(origin_pattern);
155}
156
157bool URLPatternSet::Contains(const URLPatternSet& other) const {
158  for (URLPatternSet::const_iterator it = other.begin();
159       it != other.end(); ++it) {
160    if (!ContainsPattern(*it))
161      return false;
162  }
163
164  return true;
165}
166
167bool URLPatternSet::ContainsPattern(const URLPattern& pattern) const {
168  for (URLPatternSet::const_iterator it = begin();
169       it != end(); ++it) {
170    if (it->Contains(pattern))
171      return true;
172  }
173  return false;
174}
175
176bool URLPatternSet::MatchesURL(const GURL& url) const {
177  for (URLPatternSet::const_iterator pattern = patterns_.begin();
178       pattern != patterns_.end(); ++pattern) {
179    if (pattern->MatchesURL(url))
180      return true;
181  }
182
183  return false;
184}
185
186bool URLPatternSet::MatchesAllURLs() const {
187  for (URLPatternSet::const_iterator host = begin(); host != end(); ++host) {
188    if (host->match_all_urls() ||
189        (host->match_subdomains() && host->host().empty()))
190      return true;
191  }
192  return false;
193}
194
195bool URLPatternSet::MatchesSecurityOrigin(const GURL& origin) const {
196  for (URLPatternSet::const_iterator pattern = patterns_.begin();
197       pattern != patterns_.end(); ++pattern) {
198    if (pattern->MatchesSecurityOrigin(origin))
199      return true;
200  }
201
202  return false;
203}
204
205bool URLPatternSet::OverlapsWith(const URLPatternSet& other) const {
206  // Two extension extents overlap if there is any one URL that would match at
207  // least one pattern in each of the extents.
208  for (URLPatternSet::const_iterator i = patterns_.begin();
209       i != patterns_.end(); ++i) {
210    for (URLPatternSet::const_iterator j = other.patterns().begin();
211         j != other.patterns().end(); ++j) {
212      if (i->OverlapsWith(*j))
213        return true;
214    }
215  }
216
217  return false;
218}
219
220scoped_ptr<base::ListValue> URLPatternSet::ToValue() const {
221  scoped_ptr<base::ListValue> value(new base::ListValue);
222  for (URLPatternSet::const_iterator i = patterns_.begin();
223       i != patterns_.end(); ++i)
224    value->AppendIfNotPresent(new base::StringValue(i->GetAsString()));
225  return value.Pass();
226}
227
228bool URLPatternSet::Populate(const std::vector<std::string>& patterns,
229                             int valid_schemes,
230                             bool allow_file_access,
231                             std::string* error) {
232  ClearPatterns();
233  for (size_t i = 0; i < patterns.size(); ++i) {
234    URLPattern pattern(valid_schemes);
235    if (pattern.Parse(patterns[i]) != URLPattern::PARSE_SUCCESS) {
236      if (error) {
237        *error = ErrorUtils::FormatErrorMessage(kInvalidURLPatternError,
238                                                patterns[i]);
239      } else {
240        LOG(ERROR) << "Invalid url pattern: " << patterns[i];
241      }
242      return false;
243    }
244    if (!allow_file_access && pattern.MatchesScheme(url::kFileScheme)) {
245      pattern.SetValidSchemes(
246          pattern.valid_schemes() & ~URLPattern::SCHEME_FILE);
247    }
248    AddPattern(pattern);
249  }
250  return true;
251}
252
253scoped_ptr<std::vector<std::string> > URLPatternSet::ToStringVector() const {
254  scoped_ptr<std::vector<std::string> > value(new std::vector<std::string>);
255  for (URLPatternSet::const_iterator i = patterns_.begin();
256       i != patterns_.end();
257       ++i) {
258    value->push_back(i->GetAsString());
259  }
260  std::unique(value->begin(), value->end());
261  return value.Pass();
262}
263
264bool URLPatternSet::Populate(const base::ListValue& value,
265                             int valid_schemes,
266                             bool allow_file_access,
267                             std::string* error) {
268  std::vector<std::string> patterns;
269  for (size_t i = 0; i < value.GetSize(); ++i) {
270    std::string item;
271    if (!value.GetString(i, &item))
272      return false;
273    patterns.push_back(item);
274  }
275  return Populate(patterns, valid_schemes, allow_file_access, error);
276}
277
278}  // namespace extensions
279