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 <algorithm> 8 #include <iterator> 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 "content/public/common/url_constants.h" 15 #include "extensions/common/error_utils.h" 16 #include "extensions/common/url_pattern.h" 17 #include "url/gurl.h" 18 19 namespace extensions { 20 21 namespace { 22 23 const char kInvalidURLPatternError[] = "Invalid url pattern '*'"; 24 25 } // namespace 26 27 // static 28 void URLPatternSet::CreateDifference(const URLPatternSet& set1, 29 const URLPatternSet& set2, 30 URLPatternSet* out) { 31 out->ClearPatterns(); 32 out->patterns_ = base::STLSetDifference<std::set<URLPattern> >( 33 set1.patterns_, set2.patterns_); 34 } 35 36 // static 37 void URLPatternSet::CreateIntersection(const URLPatternSet& set1, 38 const URLPatternSet& set2, 39 URLPatternSet* out) { 40 out->ClearPatterns(); 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())); 45 } 46 47 // static 48 void URLPatternSet::CreateUnion(const URLPatternSet& set1, 49 const URLPatternSet& set2, 50 URLPatternSet* out) { 51 out->ClearPatterns(); 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())); 56 } 57 58 // static 59 void URLPatternSet::CreateUnion(const std::vector<URLPatternSet>& sets, 60 URLPatternSet* out) { 61 out->ClearPatterns(); 62 if (sets.empty()) 63 return; 64 65 // N-way union algorithm is basic O(nlog(n)) merge algorithm. 66 // 67 // Do the first merge step into a working set so that we don't mutate any of 68 // the input. 69 std::vector<URLPatternSet> working; 70 for (size_t i = 0; i < sets.size(); i += 2) { 71 if (i + 1 < sets.size()) { 72 URLPatternSet u; 73 URLPatternSet::CreateUnion(sets[i], sets[i + 1], &u); 74 working.push_back(u); 75 } else { 76 working.push_back(sets[i]); 77 } 78 } 79 80 for (size_t skip = 1; skip < working.size(); skip *= 2) { 81 for (size_t i = 0; i < (working.size() - skip); i += skip) { 82 URLPatternSet u; 83 URLPatternSet::CreateUnion(working[i], working[i + skip], &u); 84 working[i].patterns_.swap(u.patterns_); 85 } 86 } 87 88 out->patterns_.swap(working[0].patterns_); 89 } 90 91 URLPatternSet::URLPatternSet() {} 92 93 URLPatternSet::URLPatternSet(const URLPatternSet& rhs) 94 : patterns_(rhs.patterns_) {} 95 96 URLPatternSet::URLPatternSet(const std::set<URLPattern>& patterns) 97 : patterns_(patterns) {} 98 99 URLPatternSet::~URLPatternSet() {} 100 101 URLPatternSet& URLPatternSet::operator=(const URLPatternSet& rhs) { 102 patterns_ = rhs.patterns_; 103 return *this; 104 } 105 106 bool URLPatternSet::operator==(const URLPatternSet& other) const { 107 return patterns_ == other.patterns_; 108 } 109 110 bool URLPatternSet::is_empty() const { 111 return patterns_.empty(); 112 } 113 114 size_t URLPatternSet::size() const { 115 return patterns_.size(); 116 } 117 118 bool URLPatternSet::AddPattern(const URLPattern& pattern) { 119 return patterns_.insert(pattern).second; 120 } 121 122 void URLPatternSet::AddPatterns(const URLPatternSet& set) { 123 patterns_.insert(set.patterns().begin(), 124 set.patterns().end()); 125 } 126 127 void URLPatternSet::ClearPatterns() { 128 patterns_.clear(); 129 } 130 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)) 135 return false; 136 } 137 138 return true; 139 } 140 141 bool URLPatternSet::ContainsPattern(const URLPattern& pattern) const { 142 for (URLPatternSet::const_iterator it = begin(); 143 it != end(); ++it) { 144 if (it->Contains(pattern)) 145 return true; 146 } 147 return false; 148 } 149 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)) 154 return true; 155 } 156 157 return false; 158 } 159 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)) 164 return true; 165 } 166 167 return false; 168 } 169 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)) 178 return true; 179 } 180 } 181 182 return false; 183 } 184 185 scoped_ptr<base::ListValue> URLPatternSet::ToValue() const { 186 scoped_ptr<ListValue> value(new ListValue); 187 for (URLPatternSet::const_iterator i = patterns_.begin(); 188 i != patterns_.end(); ++i) 189 value->AppendIfNotPresent(Value::CreateStringValue(i->GetAsString())); 190 return value.Pass(); 191 } 192 193 bool URLPatternSet::Populate(const std::vector<std::string>& patterns, 194 int valid_schemes, 195 bool allow_file_access, 196 std::string* error) { 197 ClearPatterns(); 198 for (size_t i = 0; i < patterns.size(); ++i) { 199 URLPattern pattern(valid_schemes); 200 if (pattern.Parse(patterns[i]) != URLPattern::PARSE_SUCCESS) { 201 if (error) { 202 *error = ErrorUtils::FormatErrorMessage(kInvalidURLPatternError, 203 patterns[i]); 204 } else { 205 LOG(ERROR) << "Invalid url pattern: " << patterns[i]; 206 } 207 return false; 208 } 209 if (!allow_file_access && pattern.MatchesScheme(chrome::kFileScheme)) { 210 pattern.SetValidSchemes( 211 pattern.valid_schemes() & ~URLPattern::SCHEME_FILE); 212 } 213 AddPattern(pattern); 214 } 215 return true; 216 } 217 218 bool URLPatternSet::Populate(const base::ListValue& value, 219 int valid_schemes, 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) { 224 std::string item; 225 if (!value.GetString(i, &item)) 226 return false; 227 patterns.push_back(item); 228 } 229 return Populate(patterns, valid_schemes, allow_file_access, error); 230 } 231 232 } // namespace extensions 233