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.

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 == {}