extensions/common/url_pattern_set.cc

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