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.

1 files changed, 196 insertions, 4 deletions

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