url_pattern_set.cc 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311
  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. #include "extensions/common/url_pattern_set.h"
  5. #include <iterator>
  6. #include <ostream>
  7. #include "base/containers/contains.h"
  8. #include "base/logging.h"
  9. #include "base/stl_util.h"
  10. #include "base/values.h"
  11. #include "extensions/common/error_utils.h"
  12. #include "extensions/common/url_pattern.h"
  13. #include "url/gurl.h"
  14. #include "url/origin.h"
  15. #include "url/url_constants.h"
  16. namespace extensions {
  17. namespace {
  18. const char kInvalidURLPatternError[] = "Invalid url pattern '*'";
  19. } // namespace
  20. // static
  21. URLPatternSet URLPatternSet::CreateDifference(const URLPatternSet& set1,
  22. const URLPatternSet& set2) {
  23. return URLPatternSet(base::STLSetDifference<std::set<URLPattern>>(
  24. set1.patterns_, set2.patterns_));
  25. }
  26. // static
  27. URLPatternSet URLPatternSet::CreateIntersection(
  28. const URLPatternSet& set1,
  29. const URLPatternSet& set2,
  30. IntersectionBehavior intersection_behavior) {
  31. // Note: leverage return value optimization; always return the same object.
  32. URLPatternSet result;
  33. if (intersection_behavior == IntersectionBehavior::kStringComparison) {
  34. // String comparison just relies on STL set behavior, which looks at the
  35. // string representation.
  36. result = URLPatternSet(base::STLSetIntersection<std::set<URLPattern>>(
  37. set1.patterns_, set2.patterns_));
  38. return result;
  39. }
  40. // Look for a semantic intersection.
  41. // Step 1: Iterate over each set. Find any patterns that are completely
  42. // contained by the other (thus being necessarily present in any intersection)
  43. // and add them, collecting the others in a set of unique items.
  44. // Note: Use a collection of pointers for the uniques to avoid excessive
  45. // copies. Since these are owned by the URLPatternSet passed in, which is
  46. // const, this should be safe.
  47. std::vector<const URLPattern*> unique_set1;
  48. for (const URLPattern& pattern : set1) {
  49. if (set2.ContainsPattern(pattern))
  50. result.patterns_.insert(pattern);
  51. else
  52. unique_set1.push_back(&pattern);
  53. }
  54. std::vector<const URLPattern*> unique_set2;
  55. for (const URLPattern& pattern : set2) {
  56. if (set1.ContainsPattern(pattern))
  57. result.patterns_.insert(pattern);
  58. else
  59. unique_set2.push_back(&pattern);
  60. }
  61. // If we're just looking for patterns contained by both, we're done.
  62. if (intersection_behavior == IntersectionBehavior::kPatternsContainedByBoth)
  63. return result;
  64. DCHECK_EQ(IntersectionBehavior::kDetailed, intersection_behavior);
  65. // Step 2: Iterate over all the unique patterns and find the intersections
  66. // they have with the other patterns.
  67. for (const auto* pattern : unique_set1) {
  68. for (const auto* pattern2 : unique_set2) {
  69. absl::optional<URLPattern> intersection =
  70. pattern->CreateIntersection(*pattern2);
  71. if (intersection)
  72. result.patterns_.insert(std::move(*intersection));
  73. }
  74. }
  75. return result;
  76. }
  77. // static
  78. URLPatternSet URLPatternSet::CreateUnion(const URLPatternSet& set1,
  79. const URLPatternSet& set2) {
  80. return URLPatternSet(
  81. base::STLSetUnion<std::set<URLPattern>>(set1.patterns_, set2.patterns_));
  82. }
  83. URLPatternSet::URLPatternSet() = default;
  84. URLPatternSet::URLPatternSet(URLPatternSet&& rhs) = default;
  85. URLPatternSet::URLPatternSet(const std::set<URLPattern>& patterns)
  86. : patterns_(patterns) {}
  87. URLPatternSet::~URLPatternSet() = default;
  88. URLPatternSet& URLPatternSet::operator=(URLPatternSet&& rhs) = default;
  89. bool URLPatternSet::operator==(const URLPatternSet& other) const {
  90. return patterns_ == other.patterns_;
  91. }
  92. std::ostream& operator<<(std::ostream& out,
  93. const URLPatternSet& url_pattern_set) {
  94. out << "{ ";
  95. auto iter = url_pattern_set.patterns().cbegin();
  96. if (!url_pattern_set.patterns().empty()) {
  97. out << *iter;
  98. ++iter;
  99. }
  100. for (;iter != url_pattern_set.patterns().end(); ++iter)
  101. out << ", " << *iter;
  102. if (!url_pattern_set.patterns().empty())
  103. out << " ";
  104. out << "}";
  105. return out;
  106. }
  107. URLPatternSet URLPatternSet::Clone() const {
  108. return URLPatternSet(patterns_);
  109. }
  110. bool URLPatternSet::is_empty() const {
  111. return patterns_.empty();
  112. }
  113. size_t URLPatternSet::size() const {
  114. return patterns_.size();
  115. }
  116. bool URLPatternSet::AddPattern(const URLPattern& pattern) {
  117. return patterns_.insert(pattern).second;
  118. }
  119. void URLPatternSet::AddPatterns(const URLPatternSet& set) {
  120. patterns_.insert(set.patterns().begin(),
  121. set.patterns().end());
  122. }
  123. void URLPatternSet::ClearPatterns() {
  124. patterns_.clear();
  125. }
  126. bool URLPatternSet::AddOrigin(int valid_schemes, const GURL& origin) {
  127. if (origin.is_empty())
  128. return false;
  129. const url::Origin real_origin = url::Origin::Create(origin);
  130. DCHECK(real_origin.IsSameOriginWith(
  131. url::Origin::Create(origin.DeprecatedGetOriginAsURL())));
  132. // TODO(devlin): Implement this in terms of the `AddOrigin()` call that takes
  133. // an url::Origin? It's interesting because this doesn't currently supply an
  134. // extra path, so if the GURL has not path ("https://example.com"), it would
  135. // fail to add - which is probably a bug.
  136. URLPattern origin_pattern(valid_schemes);
  137. // Origin adding could fail if |origin| does not match |valid_schemes|.
  138. if (origin_pattern.Parse(origin.spec()) !=
  139. URLPattern::ParseResult::kSuccess) {
  140. return false;
  141. }
  142. origin_pattern.SetPath("/*");
  143. return AddPattern(origin_pattern);
  144. }
  145. bool URLPatternSet::AddOrigin(int valid_schemes, const url::Origin& origin) {
  146. DCHECK(!origin.opaque());
  147. URLPattern origin_pattern(valid_schemes);
  148. // Origin adding could fail if |origin| does not match |valid_schemes|.
  149. std::string string_pattern = origin.Serialize() + "/*";
  150. if (origin_pattern.Parse(string_pattern) !=
  151. URLPattern::ParseResult::kSuccess) {
  152. return false;
  153. }
  154. return AddPattern(origin_pattern);
  155. }
  156. bool URLPatternSet::Contains(const URLPatternSet& other) const {
  157. for (auto it = other.begin(); it != other.end(); ++it) {
  158. if (!ContainsPattern(*it))
  159. return false;
  160. }
  161. return true;
  162. }
  163. bool URLPatternSet::ContainsPattern(const URLPattern& pattern) const {
  164. for (auto it = begin(); it != end(); ++it) {
  165. if (it->Contains(pattern))
  166. return true;
  167. }
  168. return false;
  169. }
  170. bool URLPatternSet::MatchesURL(const GURL& url) const {
  171. for (auto pattern = patterns_.cbegin(); pattern != patterns_.cend();
  172. ++pattern) {
  173. if (pattern->MatchesURL(url))
  174. return true;
  175. }
  176. return false;
  177. }
  178. bool URLPatternSet::MatchesAllURLs() const {
  179. for (auto host = begin(); host != end(); ++host) {
  180. if (host->match_all_urls() ||
  181. (host->match_subdomains() && host->host().empty()))
  182. return true;
  183. }
  184. return false;
  185. }
  186. bool URLPatternSet::MatchesSecurityOrigin(const GURL& origin) const {
  187. for (auto pattern = patterns_.begin(); pattern != patterns_.end();
  188. ++pattern) {
  189. if (pattern->MatchesSecurityOrigin(origin))
  190. return true;
  191. }
  192. return false;
  193. }
  194. bool URLPatternSet::OverlapsWith(const URLPatternSet& other) const {
  195. // Two extension extents overlap if there is any one URL that would match at
  196. // least one pattern in each of the extents.
  197. for (auto i = patterns_.cbegin(); i != patterns_.cend(); ++i) {
  198. for (auto j = other.patterns().cbegin(); j != other.patterns().cend();
  199. ++j) {
  200. if (i->OverlapsWith(*j))
  201. return true;
  202. }
  203. }
  204. return false;
  205. }
  206. std::unique_ptr<base::ListValue> URLPatternSet::ToValue() const {
  207. std::unique_ptr<base::ListValue> value(new base::ListValue);
  208. for (auto i = patterns_.cbegin(); i != patterns_.cend(); ++i) {
  209. base::Value pattern_str_value(i->GetAsString());
  210. if (!base::Contains(value->GetList(), pattern_str_value))
  211. value->Append(std::move(pattern_str_value));
  212. }
  213. return value;
  214. }
  215. bool URLPatternSet::Populate(const std::vector<std::string>& patterns,
  216. int valid_schemes,
  217. bool allow_file_access,
  218. std::string* error) {
  219. ClearPatterns();
  220. for (size_t i = 0; i < patterns.size(); ++i) {
  221. URLPattern pattern(valid_schemes);
  222. if (pattern.Parse(patterns[i]) != URLPattern::ParseResult::kSuccess) {
  223. if (error) {
  224. *error = ErrorUtils::FormatErrorMessage(kInvalidURLPatternError,
  225. patterns[i]);
  226. } else {
  227. LOG(ERROR) << "Invalid url pattern: " << patterns[i];
  228. }
  229. return false;
  230. }
  231. if (!allow_file_access && pattern.MatchesScheme(url::kFileScheme)) {
  232. pattern.SetValidSchemes(
  233. pattern.valid_schemes() & ~URLPattern::SCHEME_FILE);
  234. }
  235. AddPattern(pattern);
  236. }
  237. return true;
  238. }
  239. std::unique_ptr<std::vector<std::string>> URLPatternSet::ToStringVector()
  240. const {
  241. std::unique_ptr<std::vector<std::string>> value(new std::vector<std::string>);
  242. for (auto i = patterns_.cbegin(); i != patterns_.cend(); ++i) {
  243. value->push_back(i->GetAsString());
  244. }
  245. return value;
  246. }
  247. bool URLPatternSet::Populate(const base::ListValue& value,
  248. int valid_schemes,
  249. bool allow_file_access,
  250. std::string* error) {
  251. std::vector<std::string> patterns;
  252. for (const base::Value& pattern : value.GetList()) {
  253. const std::string* item = pattern.GetIfString();
  254. if (!item)
  255. return false;
  256. patterns.push_back(*item);
  257. }
  258. return Populate(patterns, valid_schemes, allow_file_access, error);
  259. }
  260. } // namespace extensions