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