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