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 <stddef.h>
8 
9 #include <sstream>
10 
11 #include "base/stl_util.h"
12 #include "base/strings/string_util.h"
13 #include "base/strings/stringprintf.h"
14 #include "base/values.h"
15 #include "testing/gmock/include/gmock/gmock.h"
16 #include "testing/gtest/include/gtest/gtest.h"
17 #include "url/gurl.h"
18 
19 namespace extensions {
20 
21 namespace {
22 
AddPattern(URLPatternSet * set,const std::string & pattern)23 void AddPattern(URLPatternSet* set, const std::string& pattern) {
24   int schemes = URLPattern::SCHEME_ALL;
25   set->AddPattern(URLPattern(schemes, pattern));
26 }
27 
Patterns(const std::string & pattern)28 URLPatternSet Patterns(const std::string& pattern) {
29   URLPatternSet set;
30   AddPattern(&set, pattern);
31   return set;
32 }
33 
Patterns(const std::string & pattern1,const std::string & pattern2)34 URLPatternSet Patterns(const std::string& pattern1,
35                        const std::string& pattern2) {
36   URLPatternSet set;
37   AddPattern(&set, pattern1);
38   AddPattern(&set, pattern2);
39   return set;
40 }
41 
42 }  // namespace
43 
TEST(URLPatternSetTest,Empty)44 TEST(URLPatternSetTest, Empty) {
45   URLPatternSet set;
46   EXPECT_FALSE(set.MatchesURL(GURL("http://www.foo.com/bar")));
47   EXPECT_FALSE(set.MatchesURL(GURL()));
48   EXPECT_FALSE(set.MatchesURL(GURL("invalid")));
49 }
50 
TEST(URLPatternSetTest,One)51 TEST(URLPatternSetTest, One) {
52   URLPatternSet set;
53   AddPattern(&set, "http://www.google.com/*");
54 
55   EXPECT_TRUE(set.MatchesURL(GURL("http://www.google.com/")));
56   EXPECT_TRUE(set.MatchesURL(GURL("http://www.google.com/monkey")));
57   EXPECT_FALSE(set.MatchesURL(GURL("https://www.google.com/")));
58   EXPECT_FALSE(set.MatchesURL(GURL("https://www.microsoft.com/")));
59 }
60 
TEST(URLPatternSetTest,Two)61 TEST(URLPatternSetTest, Two) {
62   URLPatternSet set;
63   AddPattern(&set, "http://www.google.com/*");
64   AddPattern(&set, "http://www.yahoo.com/*");
65 
66   EXPECT_TRUE(set.MatchesURL(GURL("http://www.google.com/monkey")));
67   EXPECT_TRUE(set.MatchesURL(GURL("http://www.yahoo.com/monkey")));
68   EXPECT_FALSE(set.MatchesURL(GURL("https://www.apple.com/monkey")));
69 }
70 
TEST(URLPatternSetTest,StreamOperatorEmpty)71 TEST(URLPatternSetTest, StreamOperatorEmpty) {
72   URLPatternSet set;
73 
74   std::ostringstream stream;
75   stream << set;
76   EXPECT_EQ("{ }", stream.str());
77 }
78 
TEST(URLPatternSetTest,StreamOperatorOne)79 TEST(URLPatternSetTest, StreamOperatorOne) {
80   URLPatternSet set;
81   AddPattern(&set, "http://www.google.com/*");
82 
83   std::ostringstream stream;
84   stream << set;
85   EXPECT_EQ("{ \"http://www.google.com/*\" }", stream.str());
86 }
87 
TEST(URLPatternSetTest,StreamOperatorTwo)88 TEST(URLPatternSetTest, StreamOperatorTwo) {
89   URLPatternSet set;
90   AddPattern(&set, "http://www.google.com/*");
91   AddPattern(&set, "http://www.yahoo.com/*");
92 
93   std::ostringstream stream;
94   stream << set;
95   EXPECT_EQ("{ \"http://www.google.com/*\", \"http://www.yahoo.com/*\" }",
96             stream.str());
97 }
98 
TEST(URLPatternSetTest,OverlapsWith)99 TEST(URLPatternSetTest, OverlapsWith) {
100   URLPatternSet set1;
101   AddPattern(&set1, "http://www.google.com/f*");
102   AddPattern(&set1, "http://www.yahoo.com/b*");
103 
104   URLPatternSet set2;
105   AddPattern(&set2, "http://www.reddit.com/f*");
106   AddPattern(&set2, "http://www.yahoo.com/z*");
107 
108   URLPatternSet set3;
109   AddPattern(&set3, "http://www.google.com/q/*");
110   AddPattern(&set3, "http://www.yahoo.com/b/*");
111 
112   EXPECT_FALSE(set1.OverlapsWith(set2));
113   EXPECT_FALSE(set2.OverlapsWith(set1));
114 
115   EXPECT_TRUE(set1.OverlapsWith(set3));
116   EXPECT_TRUE(set3.OverlapsWith(set1));
117 }
118 
TEST(URLPatternSetTest,CreateDifference)119 TEST(URLPatternSetTest, CreateDifference) {
120   URLPatternSet expected;
121   URLPatternSet set1;
122   URLPatternSet set2;
123   AddPattern(&set1, "http://www.google.com/f*");
124   AddPattern(&set1, "http://www.yahoo.com/b*");
125 
126   // Subtract an empty set.
127   URLPatternSet result = URLPatternSet::CreateDifference(set1, set2);
128   EXPECT_EQ(set1, result);
129 
130   // Subtract a real set.
131   AddPattern(&set2, "http://www.reddit.com/f*");
132   AddPattern(&set2, "http://www.yahoo.com/z*");
133   AddPattern(&set2, "http://www.google.com/f*");
134 
135   AddPattern(&expected, "http://www.yahoo.com/b*");
136 
137   result = URLPatternSet::CreateDifference(set1, set2);
138   EXPECT_EQ(expected, result);
139   EXPECT_FALSE(result.is_empty());
140   EXPECT_TRUE(set1.Contains(result));
141   EXPECT_FALSE(result.Contains(set2));
142   EXPECT_FALSE(set2.Contains(result));
143 
144   URLPatternSet intersection = URLPatternSet::CreateIntersection(
145       result, set2, URLPatternSet::IntersectionBehavior::kStringComparison);
146   EXPECT_TRUE(intersection.is_empty());
147 }
148 
TEST(URLPatternSetTest,CreateIntersection_StringComparison)149 TEST(URLPatternSetTest, CreateIntersection_StringComparison) {
150   URLPatternSet empty_set;
151   URLPatternSet expected;
152   URLPatternSet set1;
153   AddPattern(&set1, "http://www.google.com/f*");
154   AddPattern(&set1, "http://www.yahoo.com/b*");
155 
156   // Intersection with an empty set.
157   URLPatternSet result = URLPatternSet::CreateIntersection(
158       set1, empty_set, URLPatternSet::IntersectionBehavior::kStringComparison);
159   EXPECT_EQ(expected, result);
160   EXPECT_TRUE(result.is_empty());
161   EXPECT_TRUE(empty_set.Contains(result));
162   EXPECT_TRUE(result.Contains(empty_set));
163   EXPECT_TRUE(set1.Contains(result));
164 
165   // Intersection with a real set.
166   URLPatternSet set2;
167   AddPattern(&set2, "http://www.reddit.com/f*");
168   AddPattern(&set2, "http://www.yahoo.com/z*");
169   AddPattern(&set2, "http://www.google.com/f*");
170 
171   AddPattern(&expected, "http://www.google.com/f*");
172 
173   result = URLPatternSet::CreateIntersection(
174       set1, set2, URLPatternSet::IntersectionBehavior::kStringComparison);
175   EXPECT_EQ(expected, result);
176   EXPECT_FALSE(result.is_empty());
177   EXPECT_TRUE(set1.Contains(result));
178   EXPECT_TRUE(set2.Contains(result));
179 }
180 
TEST(URLPatternSetTest,CreateIntersection_PatternsContainedByBoth)181 TEST(URLPatternSetTest, CreateIntersection_PatternsContainedByBoth) {
182   {
183     URLPatternSet set1;
184     AddPattern(&set1, "http://*.google.com/*");
185     AddPattern(&set1, "http://*.yahoo.com/*");
186 
187     URLPatternSet set2;
188     AddPattern(&set2, "http://google.com/*");
189 
190     // The semantic intersection should contain only those patterns that are in
191     // both set 1 and set 2, or "http://google.com/*".
192     URLPatternSet intersection = URLPatternSet::CreateIntersection(
193         set1, set2,
194         URLPatternSet::IntersectionBehavior::kPatternsContainedByBoth);
195     ASSERT_EQ(1u, intersection.size());
196     EXPECT_EQ("http://google.com/*", intersection.begin()->GetAsString());
197   }
198 
199   {
200     // IntersectionBehavior::kPatternsContainedByBoth doesn't handle funny
201     // intersections, where the resultant pattern is neither of the two
202     // compared patterns. So the intersection of these two is not
203     // http://www.google.com/*, but rather nothing.
204     URLPatternSet set1;
205     AddPattern(&set1, "http://*/*");
206     URLPatternSet set2;
207     AddPattern(&set2, "*://www.google.com/*");
208     EXPECT_TRUE(
209         URLPatternSet::CreateIntersection(
210             set1, set2,
211             URLPatternSet::IntersectionBehavior::kPatternsContainedByBoth)
212             .is_empty());
213   }
214 }
215 
TEST(URLPatternSetTest,CreateIntersection_Detailed)216 TEST(URLPatternSetTest, CreateIntersection_Detailed) {
217   struct {
218     std::vector<std::string> set1;
219     std::vector<std::string> set2;
220     std::vector<std::string> expected_intersection;
221   } test_cases[] = {
222       {{"https://*.google.com/*", "https://chromium.org/*"},
223        {"*://maps.google.com/*", "*://chromium.org/foo"},
224        {"https://maps.google.com/*", "https://chromium.org/foo"}},
225       {{"https://*/*", "http://*/*"},
226        {"*://google.com/*", "*://chromium.org/*"},
227        {"https://google.com/*", "http://google.com/*", "https://chromium.org/*",
228         "http://chromium.org/*"}},
229       {{"<all_urls>"},
230        {"https://chromium.org/*", "*://google.com/*"},
231        {"https://chromium.org/*", "*://google.com/*"}},
232       {{"*://*/maps", "*://*.example.com/*"},
233        {"https://*.google.com/*", "https://www.example.com/*"},
234        {"https://*.google.com/maps", "https://www.example.com/*"}},
235       {{"https://*/maps", "https://*.google.com/*"},
236        {"https://*.google.com/*"},
237        {"https://*.google.com/*"}},
238       {{"http://*/*"}, {"https://*/*"}, {}},
239       {{"https://*.google.com/*", "https://maps.google.com/*"},
240        {"https://*.google.com/*", "https://*/*"},
241        // NOTE: We don't currently do any additional "collapsing" step after
242        // finding the intersection. We potentially could, to reduce the number
243        // of patterns we need to store.
244        {"https://*.google.com/*", "https://maps.google.com/*"}},
245   };
246 
247   constexpr int kValidSchemes = URLPattern::SCHEME_ALL;
248   constexpr char kTestCaseDescriptionTemplate[] =
249       "Running Test Case:\n"
250       "    Set1:            %s\n"
251       "    Set2:            %s\n"
252       "    Expected Result: %s";
253   for (const auto& test_case : test_cases) {
254     SCOPED_TRACE(base::StringPrintf(
255         kTestCaseDescriptionTemplate,
256         base::JoinString(test_case.set1, ", ").c_str(),
257         base::JoinString(test_case.set2, ", ").c_str(),
258         base::JoinString(test_case.expected_intersection, ", ").c_str()));
259 
260     URLPatternSet set1;
261     for (const auto& pattern_str : test_case.set1) {
262       URLPattern pattern(kValidSchemes);
263       ASSERT_EQ(URLPattern::ParseResult::kSuccess, pattern.Parse(pattern_str))
264           << "Failed to parse: " << pattern_str;
265       set1.AddPattern(pattern);
266     }
267 
268     URLPatternSet set2;
269     for (const auto& pattern_str : test_case.set2) {
270       URLPattern pattern(kValidSchemes);
271       ASSERT_EQ(URLPattern::ParseResult::kSuccess, pattern.Parse(pattern_str))
272           << "Failed to parse: " << pattern_str;
273       set2.AddPattern(pattern);
274     }
275 
276     URLPatternSet intersection1 = URLPatternSet::CreateIntersection(
277         set1, set2, URLPatternSet::IntersectionBehavior::kDetailed);
278     URLPatternSet intersection2 = URLPatternSet::CreateIntersection(
279         set2, set1, URLPatternSet::IntersectionBehavior::kDetailed);
280 
281     EXPECT_THAT(
282         *intersection1.ToStringVector(),
283         testing::UnorderedElementsAreArray(test_case.expected_intersection));
284     EXPECT_THAT(
285         *intersection2.ToStringVector(),
286         testing::UnorderedElementsAreArray(test_case.expected_intersection));
287   }
288 }
289 
TEST(URLPatternSetTest,CreateUnion)290 TEST(URLPatternSetTest, CreateUnion) {
291   URLPatternSet empty_set;
292 
293   URLPatternSet set1;
294   AddPattern(&set1, "http://www.google.com/f*");
295   AddPattern(&set1, "http://www.yahoo.com/b*");
296 
297   URLPatternSet expected;
298   AddPattern(&expected, "http://www.google.com/f*");
299   AddPattern(&expected, "http://www.yahoo.com/b*");
300 
301   // Union with an empty set.
302   URLPatternSet result = URLPatternSet::CreateUnion(set1, empty_set);
303   EXPECT_EQ(expected, result);
304 
305   // Union with a real set.
306   URLPatternSet set2;
307   AddPattern(&set2, "http://www.reddit.com/f*");
308   AddPattern(&set2, "http://www.yahoo.com/z*");
309   AddPattern(&set2, "http://www.google.com/f*");
310 
311   AddPattern(&expected, "http://www.reddit.com/f*");
312   AddPattern(&expected, "http://www.yahoo.com/z*");
313 
314   result = URLPatternSet::CreateUnion(set1, set2);
315   EXPECT_EQ(expected, result);
316 }
317 
TEST(URLPatternSetTest,Contains)318 TEST(URLPatternSetTest, Contains) {
319   URLPatternSet set1;
320   URLPatternSet set2;
321   URLPatternSet empty_set;
322 
323   AddPattern(&set1, "http://www.google.com/*");
324   AddPattern(&set1, "http://www.yahoo.com/*");
325 
326   AddPattern(&set2, "http://www.reddit.com/*");
327 
328   EXPECT_FALSE(set1.Contains(set2));
329   EXPECT_TRUE(set1.Contains(empty_set));
330   EXPECT_FALSE(empty_set.Contains(set1));
331 
332   AddPattern(&set2, "http://www.yahoo.com/*");
333 
334   EXPECT_FALSE(set1.Contains(set2));
335   EXPECT_FALSE(set2.Contains(set1));
336 
337   AddPattern(&set2, "http://www.google.com/*");
338 
339   EXPECT_FALSE(set1.Contains(set2));
340   EXPECT_TRUE(set2.Contains(set1));
341 
342   // Note that this checks if individual patterns contain other patterns, not
343   // just equality. For example:
344   AddPattern(&set1, "http://*.reddit.com/*");
345   EXPECT_TRUE(set1.Contains(set2));
346   EXPECT_FALSE(set2.Contains(set1));
347 }
348 
TEST(URLPatternSetTest,Duplicates)349 TEST(URLPatternSetTest, Duplicates) {
350   URLPatternSet set1;
351   URLPatternSet set2;
352 
353   AddPattern(&set1, "http://www.google.com/*");
354   AddPattern(&set2, "http://www.google.com/*");
355 
356   AddPattern(&set1, "http://www.google.com/*");
357 
358   // The sets should still be equal after adding a duplicate.
359   EXPECT_EQ(set2, set1);
360 }
361 
TEST(URLPatternSetTest,ToValueAndPopulate)362 TEST(URLPatternSetTest, ToValueAndPopulate) {
363   URLPatternSet set1;
364   URLPatternSet set2;
365 
366   std::vector<std::string> patterns;
367   patterns.push_back("http://www.google.com/*");
368   patterns.push_back("http://www.yahoo.com/*");
369 
370   for (size_t i = 0; i < patterns.size(); ++i)
371     AddPattern(&set1, patterns[i]);
372 
373   std::string error;
374   bool allow_file_access = false;
375   std::unique_ptr<base::ListValue> value(set1.ToValue());
376   set2.Populate(*value, URLPattern::SCHEME_ALL, allow_file_access, &error);
377   EXPECT_EQ(set1, set2);
378 
379   set2.ClearPatterns();
380   set2.Populate(patterns, URLPattern::SCHEME_ALL, allow_file_access, &error);
381   EXPECT_EQ(set1, set2);
382 }
383 
TEST(URLPatternSetTest,NwayUnion)384 TEST(URLPatternSetTest, NwayUnion) {
385   std::string google_a = "http://www.google.com/a*";
386   std::string google_b = "http://www.google.com/b*";
387   std::string google_c = "http://www.google.com/c*";
388   std::string yahoo_a = "http://www.yahoo.com/a*";
389   std::string yahoo_b = "http://www.yahoo.com/b*";
390   std::string yahoo_c = "http://www.yahoo.com/c*";
391   std::string reddit_a = "http://www.reddit.com/a*";
392   std::string reddit_b = "http://www.reddit.com/b*";
393   std::string reddit_c = "http://www.reddit.com/c*";
394 
395   // Empty list.
396   {
397     std::vector<URLPatternSet> empty;
398 
399     URLPatternSet result = URLPatternSet::CreateUnion(empty);
400 
401     URLPatternSet expected;
402     EXPECT_EQ(expected, result);
403   }
404 
405   // Singleton list.
406   {
407     std::vector<URLPatternSet> test;
408     test.push_back(Patterns(google_a));
409 
410     URLPatternSet result = URLPatternSet::CreateUnion(test);
411 
412     URLPatternSet expected = Patterns(google_a);
413     EXPECT_EQ(expected, result);
414   }
415 
416   // List with 2 elements.
417   {
418     std::vector<URLPatternSet> test;
419     test.push_back(Patterns(google_a, google_b));
420     test.push_back(Patterns(google_b, google_c));
421 
422     URLPatternSet result = URLPatternSet::CreateUnion(test);
423 
424     URLPatternSet expected;
425     AddPattern(&expected, google_a);
426     AddPattern(&expected, google_b);
427     AddPattern(&expected, google_c);
428     EXPECT_EQ(expected, result);
429   }
430 
431   // List with 3 elements.
432   {
433     std::vector<URLPatternSet> test;
434     test.push_back(Patterns(google_a, google_b));
435     test.push_back(Patterns(google_b, google_c));
436     test.push_back(Patterns(yahoo_a, yahoo_b));
437 
438     URLPatternSet result = URLPatternSet::CreateUnion(test);
439 
440     URLPatternSet expected;
441     AddPattern(&expected, google_a);
442     AddPattern(&expected, google_b);
443     AddPattern(&expected, google_c);
444     AddPattern(&expected, yahoo_a);
445     AddPattern(&expected, yahoo_b);
446     EXPECT_EQ(expected, result);
447   }
448 
449   // List with 7 elements.
450   {
451     std::vector<URLPatternSet> test;
452     test.push_back(Patterns(google_a));
453     test.push_back(Patterns(google_b));
454     test.push_back(Patterns(google_c));
455     test.push_back(Patterns(yahoo_a));
456     test.push_back(Patterns(yahoo_b));
457     test.push_back(Patterns(yahoo_c));
458     test.push_back(Patterns(reddit_a));
459 
460     URLPatternSet result = URLPatternSet::CreateUnion(test);
461 
462     URLPatternSet expected;
463     AddPattern(&expected, google_a);
464     AddPattern(&expected, google_b);
465     AddPattern(&expected, google_c);
466     AddPattern(&expected, yahoo_a);
467     AddPattern(&expected, yahoo_b);
468     AddPattern(&expected, yahoo_c);
469     AddPattern(&expected, reddit_a);
470     EXPECT_EQ(expected, result);
471   }
472 
473   // List with 8 elements.
474   {
475     std::vector<URLPatternSet> test;
476     test.push_back(Patterns(google_a));
477     test.push_back(Patterns(google_b));
478     test.push_back(Patterns(google_c));
479     test.push_back(Patterns(yahoo_a));
480     test.push_back(Patterns(yahoo_b));
481     test.push_back(Patterns(yahoo_c));
482     test.push_back(Patterns(reddit_a));
483     test.push_back(Patterns(reddit_b));
484 
485     URLPatternSet result = URLPatternSet::CreateUnion(test);
486 
487     URLPatternSet expected;
488     AddPattern(&expected, google_a);
489     AddPattern(&expected, google_b);
490     AddPattern(&expected, google_c);
491     AddPattern(&expected, yahoo_a);
492     AddPattern(&expected, yahoo_b);
493     AddPattern(&expected, yahoo_c);
494     AddPattern(&expected, reddit_a);
495     AddPattern(&expected, reddit_b);
496     EXPECT_EQ(expected, result);
497   }
498 
499   // List with 9 elements.
500   {
501     std::vector<URLPatternSet> test;
502     test.push_back(Patterns(google_a));
503     test.push_back(Patterns(google_b));
504     test.push_back(Patterns(google_c));
505     test.push_back(Patterns(yahoo_a));
506     test.push_back(Patterns(yahoo_b));
507     test.push_back(Patterns(yahoo_c));
508     test.push_back(Patterns(reddit_a));
509     test.push_back(Patterns(reddit_b));
510     test.push_back(Patterns(reddit_c));
511 
512     URLPatternSet result = URLPatternSet::CreateUnion(test);
513 
514     URLPatternSet expected;
515     AddPattern(&expected, google_a);
516     AddPattern(&expected, google_b);
517     AddPattern(&expected, google_c);
518     AddPattern(&expected, yahoo_a);
519     AddPattern(&expected, yahoo_b);
520     AddPattern(&expected, yahoo_c);
521     AddPattern(&expected, reddit_a);
522     AddPattern(&expected, reddit_b);
523     AddPattern(&expected, reddit_c);
524     EXPECT_EQ(expected, result);
525   }
526 }
527 
TEST(URLPatternSetTest,AddOrigin)528 TEST(URLPatternSetTest, AddOrigin) {
529   URLPatternSet set;
530   EXPECT_TRUE(set.AddOrigin(
531       URLPattern::SCHEME_ALL, GURL("https://www.google.com/")));
532   EXPECT_TRUE(set.MatchesURL(GURL("https://www.google.com/foo/bar")));
533   EXPECT_FALSE(set.MatchesURL(GURL("http://www.google.com/foo/bar")));
534   EXPECT_FALSE(set.MatchesURL(GURL("https://en.google.com/foo/bar")));
535   set.ClearPatterns();
536 
537   EXPECT_TRUE(set.AddOrigin(
538       URLPattern::SCHEME_ALL, GURL("https://google.com/")));
539   EXPECT_FALSE(set.MatchesURL(GURL("https://www.google.com/foo/bar")));
540   EXPECT_TRUE(set.MatchesURL(GURL("https://google.com/foo/bar")));
541 
542   EXPECT_FALSE(set.AddOrigin(
543       URLPattern::SCHEME_HTTP, GURL("https://google.com/")));
544 }
545 
TEST(URLPatternSet,AddOriginIPv6)546 TEST(URLPatternSet, AddOriginIPv6) {
547   {
548     URLPatternSet set;
549     EXPECT_TRUE(set.AddOrigin(URLPattern::SCHEME_HTTP,
550                               GURL("http://[2607:f8b0:4005:805::200e]/*")));
551   }
552   {
553     URLPatternSet set;
554     EXPECT_TRUE(set.AddOrigin(URLPattern::SCHEME_HTTP,
555                               GURL("http://[2607:f8b0:4005:805::200e]/")));
556   }
557 }
558 
TEST(URLPatternSetTest,ToStringVector)559 TEST(URLPatternSetTest, ToStringVector) {
560   URLPatternSet set;
561   AddPattern(&set, "https://google.com/");
562   AddPattern(&set, "https://google.com/");
563   AddPattern(&set, "https://yahoo.com/");
564 
565   std::unique_ptr<std::vector<std::string>> string_vector(set.ToStringVector());
566 
567   EXPECT_EQ(2UL, string_vector->size());
568 
569   EXPECT_TRUE(base::Contains(*string_vector, "https://google.com/"));
570   EXPECT_TRUE(base::Contains(*string_vector, "https://yahoo.com/"));
571 }
572 
573 }  // namespace extensions
574