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 void 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
  36 void 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
  44 void 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
  52 void 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
  84 URLPatternSet::URLPatternSet() {}
  85
  86 URLPatternSet::URLPatternSet(const URLPatternSet& rhs)
  87     : patterns_(rhs.patterns_) {}
  88
  89 URLPatternSet::URLPatternSet(const std::set<URLPattern>& patterns)
  90     : patterns_(patterns) {}
  91
  92 URLPatternSet::~URLPatternSet() {}
  93
  94 URLPatternSet& URLPatternSet::operator=(const URLPatternSet& rhs) {
  95   patterns_ = rhs.patterns_;
  96   return *this;
  97 }
  98
  99 bool URLPatternSet::operator==(const URLPatternSet& other) const {
 100   return patterns_ == other.patterns_;
 101 }
 102
 103 std::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
 124 bool URLPatternSet::is_empty() const {
 125   return patterns_.empty();
 126 }
 127
 128 size_t URLPatternSet::size() const {
 129   return patterns_.size();
 130 }
 131
 132 bool URLPatternSet::AddPattern(const URLPattern& pattern) {
 133   return patterns_.insert(pattern).second;
 134 }
 135
 136 void URLPatternSet::AddPatterns(const URLPatternSet& set) {
 137   patterns_.insert(set.patterns().begin(),
 138                    set.patterns().end());
 139 }
 140
 141 void URLPatternSet::ClearPatterns() {
 142   patterns_.clear();
 143 }
 144
 145 bool 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
 157 bool 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
 167 bool 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
 176 bool 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
 186 bool 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
 195 bool 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
 205 bool 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
 220 scoped_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
 228 bool 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
 253 scoped_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
 264 bool 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