summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorWojtek Kosior <koszko@koszko.org>2021-12-04 19:31:43 +0100
committerWojtek Kosior <koszko@koszko.org>2021-12-04 19:31:43 +0100
commite1282a63d6e41d437dd1b14a08baf89b78ab56cc (patch)
tree623f6682b70c7eb304d47506bf465bc77ab2cda6
parent44bb618aa99fa99a6df81e6a2b1dbec7a720f442 (diff)
downloadbrowser-extension-e1282a63d6e41d437dd1b14a08baf89b78ab56cc.tar.gz
browser-extension-e1282a63d6e41d437dd1b14a08baf89b78ab56cc.zip
finish implementing more efficient querying of URL patterns
The algorithm is implemented and tested. However, it is yet to be hooked into the actual extension.
-rw-r--r--common/patterns.js4
-rw-r--r--common/patterns_query_tree.js165
-rwxr-xr-xtest/profiles.py39
-rw-r--r--test/unit/conftest.py12
-rw-r--r--test/unit/test_patterns.py39
-rw-r--r--test/unit/test_patterns_query_tree.py200
6 files changed, 357 insertions, 102 deletions
diff --git a/common/patterns.js b/common/patterns.js
index 5d84a73..7d28dfe 100644
--- a/common/patterns.js
+++ b/common/patterns.js
@@ -96,7 +96,7 @@ function deconstruct_url(url, use_limits=true)
throw `unsupported protocol in url '${url}'`;
}
- deco.trailing_dash = deco.path[deco.path.length - 1] === "/";
+ deco.trailing_slash = deco.path[deco.path.length - 1] === "/";
if (deco.domain) {
if (deco.domain.length > max.DOMAIN_CHARS) {
@@ -151,7 +151,7 @@ function* each_path_pattern(deco)
const path_part = ["", ...deco.path.slice(0, slice)].join("/");
const path_wildcards = [];
if (slice === deco.path.length && !deco.path_truncated) {
- if (deco.trailing_dash)
+ if (deco.trailing_slash)
yield path_part + "/";
if (slice > 0 || deco.proto !== "file")
yield path_part;
diff --git a/common/patterns_query_tree.js b/common/patterns_query_tree.js
index 326c7b7..49205c5 100644
--- a/common/patterns_query_tree.js
+++ b/common/patterns_query_tree.js
@@ -47,17 +47,12 @@
* IMPORTS_END
*/
-/*
- * This is a javascript rewrite of Python implementation of the algorithm here:
- * https://git.koszko.org/pydrilla/tree/src/pydrilla/pydrilla.py?id=f4edcbe7f4739d6f82a2e1bb180960b003b30862#n205
- */
-
/* "Pattern Tree" is how we refer to the data structure used for querying
* Haketilo patterns. Those look like 'https://*.example.com/ab/***'. The goal
* is to make it possible for given URL to quickly retrieve all known patterns
* that match it.
*/
-function make_tree_node() {
+function empty_node() {
return {
wildcard_matches: [null, null, null],
literal_match: null,
@@ -141,7 +136,7 @@ function modify_sequence(tree_node, segments, item_modifier)
for (var current_segment of segments) {
wildcards = tree_node.wildcard_matches;
- const child = tree_node.children[current_segment] || make_tree_node();
+ const child = tree_node.children[current_segment] || empty_node();
tree_node.children[current_segment] = child;
tree_node = child;
nodes.push(tree_node);
@@ -171,11 +166,26 @@ function modify_sequence(tree_node, segments, item_modifier)
}
}
-/*
- * Make item queryable through the Pattern Tree that starts with the protocols
- * dictionary object passed in the first argument.
- */
-function pattern_tree_register(patterns_by_proto, pattern, item_name, item)
+/* Helper function for modify_tree(). */
+function modify_path(tree_node, deco, item_modifier)
+{
+ tree_node = tree_node || empty_node();
+ modify_sequence(tree_node, deco.path, item_modifier);
+ return is_empty_node(tree_node) ? null : tree_node;
+}
+
+/* Helper function for modify_tree(). */
+function modify_domain(tree_node, deco, item_modifier)
+{
+ const path_modifier = branch => modify_path(branch, deco, item_modifier);
+ tree_node = tree_node || empty_node();
+ /* We need an array of domain labels ordered most-significant-first. */
+ modify_sequence(tree_node, [...deco.domain].reverse(), path_modifier);
+ return is_empty_node(tree_node) ? null : tree_node;
+}
+
+/* Helper function for pattern_tree_register() and pattern_tree_deregister(). */
+function modify_tree(patterns_by_proto, pattern, item_modifier)
{
/*
* We pass 'false' to disable length limits on URL parts. Length limits are
@@ -184,84 +194,99 @@ function pattern_tree_register(patterns_by_proto, pattern, item_name, item)
*/
const deco = deconstruct_url(pattern, false);
- const tree = patterns_by_proto[deco.proto] || make_tree_node();
- patterns_by_proto[deco.proto] = tree;
+ let tree_for_proto = patterns_by_proto[deco.proto];
- let path_trees;
+ tree_for_proto = deco.domain === undefined ?
+ modify_path(tree_for_proto, deco, item_modifier) :
+ modify_domain(tree_for_proto, deco, item_modifier);
- if (deco.proto === "file") {
- path_trees = [tree];
- } else {
- /* We need an aray of domain labels ordered most-significant-first. */
- const domain = [...deco.domain].reverse();
- path_trees = add_sequence(tree, domain, make_tree_node);
- }
+ patterns_by_proto[deco.proto] = tree_for_proto;
+ if (tree_for_proto === null)
+ delete patterns_by_proto[deco.proto];
+}
- for (const path_tree of path_trees) {
- for (const match_obj of add_sequence(path_tree, deco.path, () => {}))
- match_obj[item_name] = item;
- }
+/*
+ * Make item queryable through the Pattern Tree that starts with the protocols
+ * dictionary object passed in the first argument.
+ */
+function pattern_tree_register(patterns_by_proto, pattern, item_name, item)
+{
+ const key_prefix = pattern[pattern.length - 1] === '/' ? '/' : '_';
+ item_name = key_prefix + item_name;
+ const add_item = obj => Object.assign(obj || {}, {[item_name]: item});
+ modify_tree(patterns_by_proto, pattern, add_item);
+}
+
+/* Helper function for pattern_tree_deregister(). */
+function _remove_item(obj, item_name)
+{
+ obj = obj || {};
+ delete obj[item_name];
+ for (const key in obj)
+ return obj;
+ return null;
}
-// /*
-// * Remove registered item from the Pattern Tree that starts with the protocols
-// * dictionary object passed in the first argument. The remaining 2 arguments
-// * should be pattern and name that have been earlier passed to
-// * pattern_tree_register().
-// */
-// function pattern_tree_deregister(patterns_by_proto, pattern, item_name)
-// {
-// const deco = deconstruct_url(pattern, false);
-
-// const tree = patterns_by_proto[deco.proto] || make_tree_node();
-// patterns_by_proto[deco.proto] = tree;
-
-// let path_trees;
-
-// if (deco.proto === "file") {
-// path_trees = [tree];
-// } else {
-// /* We need an aray of domain labels ordered most-significant-first. */
-// const domain = [...deco.domain].reverse();
-// ..........................
-// path_trees = add_sequence(tree, domain, make_tree_node);
-// }
-// }
+/*
+ * Remove registered item from the Pattern Tree that starts with the protocols
+ * dictionary object passed in the first argument. The remaining 2 arguments
+ * should be pattern and name that have been earlier passed to
+ * pattern_tree_register().
+ */
+function pattern_tree_deregister(patterns_by_proto, pattern, item_name)
+{
+ const key_prefix = pattern[pattern.length - 1] === '/' ? '/' : '_';
+ item_name = key_prefix + item_name;
+ const remove_item = obj => _remove_item(obj, item_name);
+ modify_tree(patterns_by_proto, pattern, remove_item);
+}
/*
- * Yield registered items (as [item_name, item] arrays) that match url. For
- * cosistent behavior, please don't modify the pattern tree while iterating over
- * the results.
+ * Yield registered items that match url. Each yielded value is an object with
+ * key being matched item names and values being the items. One such object
+ * shall contain all items matched with given pattern specificity. Objects are
+ * yielded in order from greatest to lowest pattern specificity.
*/
function* pattern_tree_search(patterns_by_proto, url)
{
const deco = deconstruct_url(url, false);
- tree = patterns_by_proto[deco.proto] || make_tree_node();
+ const tree_for_proto = patterns_by_proto[deco.proto] || empty_node();
+ let by_path = [tree_for_proto];
- let path_trees;
-
- if (deco.proto === "file") {
- path_trees = [tree];
- } else {
- /* We need an aray of domain labels ordered most-significant-first. */
- const domain = [...deco.domain].reverse();
- path_trees = search_sequence(tree, domain);
- }
+ /* We need an array of domain labels ordered most-significant-first. */
+ if (deco.domain !== undefined)
+ by_path = search_sequence(tree_for_proto, [...deco.domain].reverse());
- for (const path_tree of path_trees) {
+ for (const path_tree of by_path) {
for (const match_obj of search_sequence(path_tree, deco.path)) {
- for (const entry of Object.entries(match_obj))
- yield entry;
+ let result_obj_slash = null;
+ let result_obj_no_slash = null;
+
+ for (const [key, item] of Object.entries(match_obj)) {
+ if (deco.trailing_slash && key[0] === '/') {
+ result_obj_slash = result_obj_slash || {};
+ result_obj_slash[key.substring(1)] = item;
+ } else if (key[0] !== '/') {
+ result_obj_no_slash = result_obj_no_slash || {};
+ result_obj_no_slash[key.substring(1)] = item;
+ }
+ }
+
+ if (deco.trailing_slash && result_obj_slash)
+ yield result_obj_slash;
+
+ if (result_obj_no_slash)
+ yield result_obj_no_slash;
}
}
}
const pattern_tree = {
- make: () => {},
- register: pattern_tree_register,
- // deregister: pattern_tree_deregister,
- search: pattern_tree_search
+ make: () => ({}),
+ register: pattern_tree_register,
+ deregister: pattern_tree_deregister,
+ search: pattern_tree_search
}
/*
diff --git a/test/profiles.py b/test/profiles.py
index d6a4efc..1530aea 100755
--- a/test/profiles.py
+++ b/test/profiles.py
@@ -31,7 +31,28 @@ import time
from .misc_constants import *
+class HaketiloFirefox(webdriver.Firefox):
+ """
+ This wrapper class around selenium.webdriver.Firefox adds a `loaded_scripts`
+ instance property that gets resetted to an empty array every time the
+ `get()` method is called.
+ """
+ def __init__(self, *args, **kwargs):
+ super().__init__(*args, **kwargs)
+ self.reset_loaded_scripts()
+
+ def reset_loaded_scripts(self):
+ self.loaded_scripts = []
+
+ def get(self, *args, **kwargs):
+ self.reset_loaded_scripts()
+ super().get(*args, **kwargs)
+
def set_profile_proxy(profile, proxy_host, proxy_port):
+ """
+ Create a Firefox profile that uses the specified HTTP proxy for all
+ protocols.
+ """
# proxy type 1 designates "manual"
profile.set_preference('network.proxy.type', 1)
profile.set_preference('network.proxy.no_proxies_on', '')
@@ -49,6 +70,10 @@ def set_profile_console_logging(profile):
def firefox_safe_mode(firefox_binary=default_firefox_binary,
proxy_host=default_proxy_host,
proxy_port=default_proxy_port):
+ """
+ Initialize a Firefox instance controlled by selenium. The instance is
+ started in safe mode.
+ """
profile = webdriver.FirefoxProfile()
set_profile_proxy(profile, proxy_host, proxy_port)
set_profile_console_logging(profile)
@@ -56,16 +81,22 @@ def firefox_safe_mode(firefox_binary=default_firefox_binary,
options = Options()
options.add_argument('--safe-mode')
- return webdriver.Firefox(options=options, firefox_profile=profile,
- firefox_binary=firefox_binary)
+ return HaketiloFirefox(options=options, firefox_profile=profile,
+ firefox_binary=firefox_binary)
def firefox_with_profile(firefox_binary=default_firefox_binary,
profile_dir=default_clean_profile_dir,
proxy_host=default_proxy_host,
proxy_port=default_proxy_port):
+ """
+ Initialize a Firefox instance controlled by selenium. The instance is
+ started using an empty profile (either the default one or the one passed to
+ `configure` script). The empty profile is meant to make Firefox start with
+ globally-installed extensions disabled.
+ """
profile = webdriver.FirefoxProfile(profile_dir)
set_profile_proxy(profile, proxy_host, proxy_port)
set_profile_console_logging(profile)
- return webdriver.Firefox(firefox_profile=profile,
- firefox_binary=firefox_binary)
+ return HaketiloFirefox(firefox_profile=profile,
+ firefox_binary=firefox_binary)
diff --git a/test/unit/conftest.py b/test/unit/conftest.py
index 62cc1a0..1500006 100644
--- a/test/unit/conftest.py
+++ b/test/unit/conftest.py
@@ -78,13 +78,19 @@ return window.haketilo_selenium_return_value;
def _execute_in_page_context(driver, script, args):
script = script + '\n;\nwindow.haketilo_selenium_exception = false;'
+ driver.loaded_scripts.append(script)
try:
return driver.execute_script(script_injecting_script, script, args)
except Exception as e:
import sys
- lines = enumerate(script.split('\n'), 1)
- for err_info in [('Failing script\n',), *lines]:
- print(*err_info, file=sys.stderr)
+
+ print("Scripts loaded since driver's last get() method call:",
+ file=sys.stderr)
+
+ for script in driver.loaded_scripts:
+ lines = enumerate(script.split('\n'), 1)
+ for err_info in [('===',), *lines]:
+ print(*err_info, file=sys.stderr)
raise e from None
diff --git a/test/unit/test_patterns.py b/test/unit/test_patterns.py
index 4cfc10c..802bf4e 100644
--- a/test/unit/test_patterns.py
+++ b/test/unit/test_patterns.py
@@ -100,41 +100,42 @@ def test_deconstruct_url(execute_in_page, patterns_code):
deco = execute_in_page('returnval(deconstruct_url(arguments[0]));',
'https://eXaMpLe.com/a/b?ver=1.2.3#heading2')
assert deco
- assert deco['trailing_dash'] == False
- assert deco['proto'] == 'https'
- assert deco['domain'] == ['example', 'com']
- assert deco['path'] == ['a', 'b']
+ assert deco['trailing_slash'] == False
+ assert deco['proto'] == 'https'
+ assert deco['domain'] == ['example', 'com']
+ assert deco['path'] == ['a', 'b']
deco = execute_in_page('returnval(deconstruct_url(arguments[0]));',
'http://**.example.com/')
assert deco
- assert deco['trailing_dash'] == True
- assert deco['proto'] == 'http'
- assert deco['domain'] == ['**', 'example', 'com']
- assert deco['path'] == []
+ assert deco['trailing_slash'] == True
+ assert deco['proto'] == 'http'
+ assert deco['domain'] == ['**', 'example', 'com']
+ assert deco['path'] == []
deco = execute_in_page('returnval(deconstruct_url(arguments[0]));',
'ftp://user@ftp.example.com/all///passwords.txt/')
assert deco
- assert deco['trailing_dash'] == True
- assert deco['proto'] == 'ftp'
- assert deco['domain'] == ['ftp', 'example', 'com']
- assert deco['path'] == ['all', 'passwords.txt']
+ assert deco['trailing_slash'] == True
+ assert deco['proto'] == 'ftp'
+ assert deco['domain'] == ['ftp', 'example', 'com']
+ assert deco['path'] == ['all', 'passwords.txt']
deco = execute_in_page('returnval(deconstruct_url(arguments[0]));',
'ftp://mirror.edu.pl.eu.org')
assert deco
- assert deco['trailing_dash'] == False
- assert deco['proto'] == 'ftp'
- assert deco['domain'] == ['mirror', 'edu', 'pl', 'eu', 'org']
- assert deco['path'] == []
+ assert deco['trailing_slash'] == False
+ assert deco['proto'] == 'ftp'
+ assert deco['domain'] == ['mirror', 'edu', 'pl', 'eu', 'org']
+ assert deco['path'] == []
deco = execute_in_page('returnval(deconstruct_url(arguments[0]));',
'file:///mnt/parabola_chroot///etc/passwd')
assert deco
- assert deco['trailing_dash'] == False
- assert deco['proto'] == 'file'
- assert deco['path'] == ['mnt', 'parabola_chroot', 'etc', 'passwd']
+ assert deco['trailing_slash'] == False
+ assert deco['proto'] == 'file'
+ assert deco['path'] == ['mnt', 'parabola_chroot', 'etc', 'passwd']
+ assert 'domain' not in deco
for bad_url in [
'://bad-url.missing/protocol',
diff --git a/test/unit/test_patterns_query_tree.py b/test/unit/test_patterns_query_tree.py
index 9fbc0c3..e282592 100644
--- a/test/unit/test_patterns_query_tree.py
+++ b/test/unit/test_patterns_query_tree.py
@@ -27,7 +27,7 @@ def patterns_tree_code():
def test_modify_branch(execute_in_page, patterns_tree_code):
"""
- patterns_query_tree.js contains Patterns Tree data structure that allows
+ patterns_query_tree.js contains Pattern Tree data structure that allows
arrays of string labels to be mapped to items.
Verify operations modifying a single branch of such tree work properly.
"""
@@ -68,7 +68,7 @@ def test_modify_branch(execute_in_page, patterns_tree_code):
# the right result.
branch = execute_in_page(
'''{
- const branch = make_tree_node();
+ const branch = empty_node();
modify_sequence(branch, ['com', 'example'], item_adder('some_item'));
returnval(branch);
}''')
@@ -197,7 +197,7 @@ def test_modify_branch(execute_in_page, patterns_tree_code):
def test_search_branch(execute_in_page, patterns_tree_code):
"""
- patterns_query_tree.js contains Patterns Tree data structure that allows
+ patterns_query_tree.js contains Pattern Tree data structure that allows
arrays of string labels to be mapped to items.
Verify searching a single branch of such tree work properly.
"""
@@ -210,7 +210,7 @@ def test_search_branch(execute_in_page, patterns_tree_code):
# Let's construct some tree branch to test on.
execute_in_page(
'''
- var branch = make_tree_node();
+ var branch = empty_node();
for (const [item, sequence] of [
['(root)', []],
@@ -281,3 +281,195 @@ def test_search_branch(execute_in_page, patterns_tree_code):
print('sequence:', sequence, '\nexpected:', expected,
'\nresult:', result, file=sys.stderr)
raise e from None
+
+def test_pattern_tree(execute_in_page, patterns_tree_code):
+ """
+ patterns_query_tree.js contains Pattern Tree data structure that allows
+ arrays of string labels to be mapped to items.
+ Verify operations on entire such tree work properly.
+ """
+ execute_in_page(patterns_tree_code, page='https://gotmyowndoma.in')
+
+ # Perform tests with all possible patterns for a simple URL.
+ url = 'https://example.com'
+ patterns = [
+ 'https://example.com',
+ 'https://example.com/***',
+ 'https://***.example.com',
+ 'https://***.example.com/***'
+ ]
+ bad_patterns = [
+ 'http://example.com',
+ 'https://a.example.com',
+ 'https://*.example.com',
+ 'https://**.example.com',
+ 'https://example.com/a',
+ 'https://example.com/*',
+ 'https://example.com/**',
+ ]
+
+ expected = [{'key': p} for p in patterns]
+
+ tree, result = execute_in_page(
+ '''{
+ const tree = pattern_tree.make();
+ for (const pattern of arguments[0].concat(arguments[1])) {
+ pattern_tree.register(tree, pattern, 'key', pattern);
+ pattern_tree.register(tree, pattern + '/', 'key', pattern + '/');
+ }
+ returnval([tree, [...pattern_tree.search(tree, arguments[2])]]);
+ }''',
+ patterns, bad_patterns, url)
+ assert expected == result
+
+ # Also verify that deregistering half of the good patterns works correctly.
+ patterns_removed = [pattern for i, pattern in enumerate(patterns) if i % 2]
+ patterns = [pattern for i, pattern in enumerate(patterns) if not (i % 2)]
+ expected = [{'key': p} for p in patterns]
+ tree, result = execute_in_page(
+ '''{
+ const tree = arguments[0];
+ for (const pattern of arguments[1]) {
+ pattern_tree.deregister(tree, pattern, 'key');
+ pattern_tree.deregister(tree, pattern + '/', 'key');
+ }
+ returnval([tree, [...pattern_tree.search(tree, arguments[2])]]);
+ }''',
+ tree, patterns_removed, url)
+ assert expected == result
+
+ # Also verify that deregistering all the patterns works correctly.
+ tree = execute_in_page(
+ '''{
+ const tree = arguments[0];
+ for (const pattern of arguments[1].concat(arguments[2])) {
+ pattern_tree.deregister(tree, pattern, 'key');
+ pattern_tree.deregister(tree, pattern + '/', 'key');
+ }
+ returnval(tree);
+ }''',
+ tree, patterns, bad_patterns)
+ assert tree == {}
+
+ # Perform tests with all possible patterns for a complex URL.
+ url = 'http://settings.query.example.com/google/tries/destroy/adblockers//'
+ patterns = [
+ 'http://settings.query.example.com/google/tries/destroy/adblockers',
+ 'http://settings.query.example.com/google/tries/destroy/adblockers/***',
+ 'http://settings.query.example.com/google/tries/destroy/*',
+ 'http://settings.query.example.com/google/tries/destroy/***',
+ 'http://settings.query.example.com/google/tries/**',
+ 'http://settings.query.example.com/google/tries/***',
+ 'http://settings.query.example.com/google/**',
+ 'http://settings.query.example.com/google/***',
+ 'http://settings.query.example.com/**',
+ 'http://settings.query.example.com/***',
+
+ 'http://***.settings.query.example.com/google/tries/destroy/adblockers',
+ 'http://***.settings.query.example.com/google/tries/destroy/adblockers/***',
+ 'http://***.settings.query.example.com/google/tries/destroy/*',
+ 'http://***.settings.query.example.com/google/tries/destroy/***',
+ 'http://***.settings.query.example.com/google/tries/**',
+ 'http://***.settings.query.example.com/google/tries/***',
+ 'http://***.settings.query.example.com/google/**',
+ 'http://***.settings.query.example.com/google/***',
+ 'http://***.settings.query.example.com/**',
+ 'http://***.settings.query.example.com/***',
+ 'http://*.query.example.com/google/tries/destroy/adblockers',
+ 'http://*.query.example.com/google/tries/destroy/adblockers/***',
+ 'http://*.query.example.com/google/tries/destroy/*',
+ 'http://*.query.example.com/google/tries/destroy/***',
+ 'http://*.query.example.com/google/tries/**',
+ 'http://*.query.example.com/google/tries/***',
+ 'http://*.query.example.com/google/**',
+ 'http://*.query.example.com/google/***',
+ 'http://*.query.example.com/**',
+ 'http://*.query.example.com/***',
+ 'http://***.query.example.com/google/tries/destroy/adblockers',
+ 'http://***.query.example.com/google/tries/destroy/adblockers/***',
+ 'http://***.query.example.com/google/tries/destroy/*',
+ 'http://***.query.example.com/google/tries/destroy/***',
+ 'http://***.query.example.com/google/tries/**',
+ 'http://***.query.example.com/google/tries/***',
+ 'http://***.query.example.com/google/**',
+ 'http://***.query.example.com/google/***',
+ 'http://***.query.example.com/**',
+ 'http://***.query.example.com/***',
+ 'http://**.example.com/google/tries/destroy/adblockers',
+ 'http://**.example.com/google/tries/destroy/adblockers/***',
+ 'http://**.example.com/google/tries/destroy/*',
+ 'http://**.example.com/google/tries/destroy/***',
+ 'http://**.example.com/google/tries/**',
+ 'http://**.example.com/google/tries/***',
+ 'http://**.example.com/google/**',
+ 'http://**.example.com/google/***',
+ 'http://**.example.com/**',
+ 'http://**.example.com/***',
+ 'http://***.example.com/google/tries/destroy/adblockers',
+ 'http://***.example.com/google/tries/destroy/adblockers/***',
+ 'http://***.example.com/google/tries/destroy/*',
+ 'http://***.example.com/google/tries/destroy/***',
+ 'http://***.example.com/google/tries/**',
+ 'http://***.example.com/google/tries/***',
+ 'http://***.example.com/google/**',
+ 'http://***.example.com/google/***',
+ 'http://***.example.com/**',
+ 'http://***.example.com/***'
+ ]
+ bad_patterns = [
+ 'https://settings.query.example.com/google/tries/destroy/adblockers',
+ 'http://settings.query.example.com/google/tries/destroy/adblockers/a',
+ 'http://settings.query.example.com/google/tries/destroy/adblockers/*',
+ 'http://settings.query.example.com/google/tries/destroy/adblockers/**',
+ 'http://settings.query.example.com/google/tries/destroy/a',
+ 'http://settings.query.example.com/google/tries/destroy/**',
+ 'http://settings.query.example.com/google/tries/*',
+ 'http://a.settings.query.example.com/google/tries/destroy/adblockers',
+ 'http://*.settings.query.example.com/google/tries/destroy/adblockers',
+ 'http://**.settings.query.example.com/google/tries/destroy/adblockers',
+ 'http://a.query.example.com/google/tries/destroy/adblockers',
+ 'http://**.query.example.com/google/tries/destroy/adblockers',
+ 'http://*.example.com/google/tries/destroy/adblockers'
+ ]
+
+ expected = [{'key': p + s} for p in patterns for s in ['/', '']]
+
+ tree, result = execute_in_page(
+ '''{
+ const tree = pattern_tree.make();
+ for (const pattern of arguments[0].concat(arguments[1])) {
+ pattern_tree.register(tree, pattern, 'key', pattern);
+ pattern_tree.register(tree, pattern + '/', 'key', pattern + '/');
+ }
+ returnval([tree, [...pattern_tree.search(tree, arguments[2])]]);
+ }''',
+ patterns, bad_patterns, url)
+ assert expected == result
+
+ # Also verify that deregistering all patterns with trailing slash works
+ # correctly.
+ expected = [{'key': p} for p in patterns]
+ tree, result = execute_in_page(
+ '''{
+ const tree = arguments[0];
+ for (const pattern of arguments[1])
+ pattern_tree.deregister(tree, pattern + '/', 'key');
+ returnval([tree, [...pattern_tree.search(tree, arguments[2])]]);
+ }''',
+ tree, patterns, url)
+ assert expected == result
+
+ # Also verify that deregistering all the patterns works correctly.
+ tree = execute_in_page(
+ '''{
+ const tree = arguments[0];
+ for (const pattern of arguments[1])
+ pattern_tree.deregister(tree, pattern, 'key');
+ for (const pattern of arguments[2]) {
+ pattern_tree.deregister(tree, pattern, 'key');
+ pattern_tree.deregister(tree, pattern + '/', 'key');
+ }
+ returnval(tree);
+ }''',
+ tree, patterns, bad_patterns)
+ assert tree == {}