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/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 "googleurl/src/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& set) const {
 133   return std::includes(patterns_.begin(), patterns_.end(),
 134                        set.patterns_.begin(), set.patterns_.end());
 135 }
 136
 137 bool URLPatternSet::MatchesURL(const GURL& url) const {
 138   for (URLPatternSet::const_iterator pattern = patterns_.begin();
 139        pattern != patterns_.end(); ++pattern) {
 140     if (pattern->MatchesURL(url))
 141       return true;
 142   }
 143
 144   return false;
 145 }
 146
 147 bool URLPatternSet::MatchesSecurityOrigin(const GURL& origin) const {
 148   for (URLPatternSet::const_iterator pattern = patterns_.begin();
 149        pattern != patterns_.end(); ++pattern) {
 150     if (pattern->MatchesSecurityOrigin(origin))
 151       return true;
 152   }
 153
 154   return false;
 155 }
 156
 157 bool URLPatternSet::OverlapsWith(const URLPatternSet& other) const {
 158   // Two extension extents overlap if there is any one URL that would match at
 159   // least one pattern in each of the extents.
 160   for (URLPatternSet::const_iterator i = patterns_.begin();
 161        i != patterns_.end(); ++i) {
 162     for (URLPatternSet::const_iterator j = other.patterns().begin();
 163          j != other.patterns().end(); ++j) {
 164       if (i->OverlapsWith(*j))
 165         return true;
 166     }
 167   }
 168
 169   return false;
 170 }
 171
 172 scoped_ptr<base::ListValue> URLPatternSet::ToValue() const {
 173   scoped_ptr<ListValue> value(new ListValue);
 174   for (URLPatternSet::const_iterator i = patterns_.begin();
 175        i != patterns_.end(); ++i)
 176     value->AppendIfNotPresent(Value::CreateStringValue(i->GetAsString()));
 177   return value.Pass();
 178 }
 179
 180 bool URLPatternSet::Populate(const std::vector<std::string>& patterns,
 181                              int valid_schemes,
 182                              bool allow_file_access,
 183                              std::string* error) {
 184   ClearPatterns();
 185   for (size_t i = 0; i < patterns.size(); ++i) {
 186     URLPattern pattern(valid_schemes);
 187     if (pattern.Parse(patterns[i]) != URLPattern::PARSE_SUCCESS) {
 188       if (error) {
 189         *error = ErrorUtils::FormatErrorMessage(kInvalidURLPatternError,
 190                                                 patterns[i]);
 191       } else {
 192         LOG(ERROR) << "Invalid url pattern: " << patterns[i];
 193       }
 194       return false;
 195     }
 196     if (!allow_file_access && pattern.MatchesScheme(chrome::kFileScheme)) {
 197       pattern.SetValidSchemes(
 198           pattern.valid_schemes() & ~URLPattern::SCHEME_FILE);
 199     }
 200     AddPattern(pattern);
 201   }
 202   return true;
 203 }
 204
 205 bool URLPatternSet::Populate(const base::ListValue& value,
 206                              int valid_schemes,
 207                              bool allow_file_access,
 208                              std::string* error) {
 209   std::vector<std::string> patterns;
 210   for (size_t i = 0; i < value.GetSize(); ++i) {
 211     std::string item;
 212     if (!value.GetString(i, &item))
 213       return false;
 214     patterns.push_back(item);
 215   }
 216   return Populate(patterns, valid_schemes, allow_file_access, error);
 217 }
 218
 219 }  // namespace extensions