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 <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