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