start implementing more efficient querying of URL patterns

3 files changed, 346 insertions, 1 deletions

diff --git a/test/unit/conftest.py b/test/unit/conftest.py
index 6877b7a..62cc1a0 100644
--- a/test/unit/conftest.py
+++ b/test/unit/conftest.py
@@ -76,7 +76,7 @@ try {
 return window.haketilo_selenium_return_value;
 '''
 
-def _execute_in_page_context(driver, script, *args):
+def _execute_in_page_context(driver, script, args):
     script = script + '\n;\nwindow.haketilo_selenium_exception = false;'
     try:
         return driver.execute_script(script_injecting_script, script, args)
diff --git a/test/unit/test_patterns.py b/test/unit/test_patterns.py
index 4162fc0..4cfc10c 100644
--- a/test/unit/test_patterns.py
+++ b/test/unit/test_patterns.py
@@ -89,3 +89,65 @@ def test_regexes(execute_in_page, patterns_code):
     match = execute_in_page('returnval(ftp_regex.exec(arguments[0]));',
                             '@bad.url/')
     assert match is None
+
+def test_deconstruct_url(execute_in_page, patterns_code):
+    """
+    patterns.js contains deconstruct_url() function that handles URL parsing.
+    Verify it works properly.
+    """
+    execute_in_page(patterns_code, page='https://gotmyowndoma.in')
+
+    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']
+
+    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']          == []
+
+    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']
+
+    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']          == []
+
+    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']
+
+    for bad_url in [
+            '://bad-url.missing/protocol',
+            'http:/example.com/a/b',
+            'unknown://example.com/a/b',
+            'idontfancypineapple',
+            'ftp://@example.org/',
+            'https:///some/path/',
+            'file://non-absolute/path'
+    ]:
+        with pytest.raises(Exception, match=r'Error in injected script'):
+            deco = execute_in_page('returnval(deconstruct_url(arguments[0]));',
+                                   bad_url)
+
+    # at some point we might also consider testing url deconstruction with
+    # length limits...
diff --git a/test/unit/test_patterns_query_tree.py b/test/unit/test_patterns_query_tree.py
new file mode 100644
index 0000000..9fbc0c3
--- /dev/null
+++ b/test/unit/test_patterns_query_tree.py
@@ -0,0 +1,283 @@
+# SPDX-License-Identifier: CC0-1.0
+
+"""
+Haketilo unit tests - URL patterns
+"""
+
+# This file is part of Haketilo
+#
+# Copyright (C) 2021, Wojtek Kosior
+#
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the CC0 1.0 Universal License as published by
+# the Creative Commons Corporation.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# CC0 1.0 Universal License for more details.
+
+import pytest
+
+from ..script_loader import load_script
+
+@pytest.fixture(scope="session")
+def patterns_tree_code():
+    yield load_script('common/patterns_query_tree.js', ['common'])
+
+def test_modify_branch(execute_in_page, patterns_tree_code):
+    """
+    patterns_query_tree.js contains Patterns 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.
+    """
+    execute_in_page(patterns_tree_code, page='https://gotmyowndoma.in')
+    execute_in_page(
+        '''
+        let items_added;
+        let items_removed;
+
+        function _item_adder(item, array)
+        {
+            items_added++;
+            return [...(array || []), item];
+        }
+
+        function item_adder(item)
+        {
+            items_added = 0;
+            return array => _item_adder(item, array);
+        }
+
+        function _item_remover(array)
+        {
+            if (array !== null) {
+                items_removed++;
+                array.pop();
+            }
+            return (array && array.length > 0) ? array : null;
+        }
+
+        function item_remover()
+        {
+            items_removed = 0;
+            return _item_remover;
+        }''')
+
+    # Let's construct some tree branch while checking that each addition gives
+    # the right result.
+    branch = execute_in_page(
+        '''{
+        const branch = make_tree_node();
+        modify_sequence(branch, ['com', 'example'], item_adder('some_item'));
+        returnval(branch);
+        }''')
+    assert branch == {
+        'literal_match': None,
+        'wildcard_matches': [None, None, None],
+        'children': {
+            'com': {
+                'literal_match': None,
+                'wildcard_matches': [None, None, None],
+                'children': {
+                    'example': {
+                        'literal_match': ['some_item'],
+                        'wildcard_matches': [None, None, None],
+                        'children': {
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    branch, items_added = execute_in_page(
+        '''{
+        const branch = arguments[0];
+        modify_sequence(branch, ['com', 'example'], item_adder('other_item'));
+        returnval([branch, items_added]);
+        }''', branch)
+    assert items_added == 1
+    assert branch['children']['com']['children']['example']['literal_match'] \
+            == ['some_item', 'other_item']
+
+    for i in range(3):
+        for expected_array in [['third_item'], ['third_item', '4th_item']]:
+            wildcard = '*' * (i + 1)
+            branch, items_added = execute_in_page(
+                '''{
+                const branch = arguments[0];
+                modify_sequence(branch, ['com', 'sample', arguments[1]],
+                                item_adder(arguments[2]));
+                returnval([branch, items_added]);
+                }''',
+                branch, wildcard, expected_array[-1])
+            assert items_added == 2
+            sample = branch['children']['com']['children']['sample']
+            assert sample['wildcard_matches'][i] == expected_array
+            assert sample['children'][wildcard]['literal_match'] \
+                == expected_array
+
+    branch, items_added = execute_in_page(
+        '''{
+        const branch = arguments[0];
+        modify_sequence(branch, ['org', 'koszko', '***', '123'],
+                        item_adder('5th_item'));
+        returnval([branch, items_added]);
+        }''',
+        branch)
+    assert items_added == 1
+    assert branch['children']['org']['children']['koszko']['children']['***']\
+        ['children']['123']['literal_match'] == ['5th_item']
+
+    # Let's verify that removing a nonexistent element doesn't modify the tree.
+    branch2, items_removed = execute_in_page(
+        '''{
+        const branch = arguments[0];
+        modify_sequence(branch, ['com', 'not', 'registered', '*'],
+                        item_remover());
+        returnval([branch, items_removed]);
+        }''',
+        branch)
+    assert branch == branch2
+    assert items_removed == 0
+
+    # Let's remove all elements in the tree branch while checking that each
+    # removal gives the right result.
+    branch, items_removed = execute_in_page(
+        '''{
+        const branch = arguments[0];
+        modify_sequence(branch, ['org', 'koszko', '***', '123'],
+                        item_remover());
+        returnval([branch, items_removed]);
+        }''',
+        branch)
+    assert items_removed == 1
+    assert 'org' not in branch['children']
+
+    for i in range(3):
+        for expected_array in [['third_item'], None]:
+            wildcard = '*' * (i + 1)
+            branch, items_removed = execute_in_page(
+                '''{
+                const branch = arguments[0];
+                modify_sequence(branch, ['com', 'sample', arguments[1]],
+                                item_remover());
+                returnval([branch, items_removed]);
+                }''',
+                branch, wildcard)
+            assert items_removed == 2
+            if i == 2 and expected_array == []:
+                break
+            sample = branch['children']['com']['children'].get('sample', {})
+            assert sample.get('wildcard_matches', [None, None, None])[i] \
+                == expected_array
+            assert sample.get('children', {}).get(wildcard, {})\
+                .get('literal_match') == expected_array
+
+    for i in range(2):
+        branch, items_removed = execute_in_page(
+            '''{
+            const branch = arguments[0];
+            modify_sequence(branch, ['com', 'example'], item_remover());
+            returnval([branch, items_removed]);
+            }''',
+            branch)
+        assert items_removed == 1
+        if i == 0:
+            assert branch['children']['com']['children']['example']\
+                ['literal_match'] == ['some_item']
+        else:
+            assert branch == {
+                'literal_match': None,
+                'wildcard_matches': [None, None, None],
+                'children': {
+                }
+            }
+
+def test_search_branch(execute_in_page, patterns_tree_code):
+    """
+    patterns_query_tree.js contains Patterns Tree data structure that allows
+    arrays of string labels to be mapped to items.
+    Verify searching a single branch of such tree work properly.
+    """
+    execute_in_page(patterns_tree_code, page='https://gotmyowndoma.in')
+    execute_in_page(
+        '''
+        const item_adder = item => (array => [...(array || []), item]);
+        ''')
+
+    # Let's construct some tree branch to test on.
+    execute_in_page(
+        '''
+        var branch = make_tree_node();
+
+        for (const [item, sequence] of [
+            ['(root)', []],
+            ['***',    ['***']],
+            ['**',     ['**']],
+            ['*',      ['*']],
+
+            ['a',      ['a']],
+            ['A',      ['a']],
+            ['b',      ['b']],
+
+            ['a/***',  ['a', '***']],
+            ['A/***',  ['a', '***']],
+            ['a/**',   ['a', '**']],
+            ['A/**',   ['a', '**']],
+            ['a/*',    ['a', '*']],
+            ['A/*',    ['a', '*']],
+            ['a/sth',  ['a', 'sth']],
+            ['A/sth',  ['a', 'sth']],
+
+            ['b/***',  ['b', '***']],
+            ['b/**',   ['b', '**']],
+            ['b/*',    ['b', '*']],
+            ['b/sth',  ['b', 'sth']],
+        ])
+            modify_sequence(branch, sequence, item_adder(item));
+        ''')
+
+    # Let's make the actual searches on our testing branch.
+    for sequence, expected in [
+            ([],      [{'(root)'},                            {'***'}]),
+            (['a'],   [{'a', 'A'}, {'a/***', 'A/***'}, {'*'}, {'***'}]),
+            (['b'],   [{'b'},      {'b/***'},          {'*'}, {'***'}]),
+            (['c'],   [                                {'*'}, {'***'}]),
+            (['***'], [{'***'},                        {'*'}         ]),
+            (['**'],  [{'**'},                         {'*'}, {'***'}]),
+            (['**'],  [{'**'},                         {'*'}, {'***'}]),
+            (['*'],   [{'*'},                                 {'***'}]),
+
+            (['a', 'sth'], [{'a/sth', 'A/sth'}, {'a/*', 'A/*'}, {'a/***', 'A/***'}, {'**'}, {'***'}]),
+            (['b', 'sth'], [{'b/sth'},          {'b/*'},        {'b/***'},          {'**'}, {'***'}]),
+            (['a', 'hts'], [                    {'a/*', 'A/*'}, {'a/***', 'A/***'}, {'**'}, {'***'}]),
+            (['b', 'hts'], [                    {'b/*'},        {'b/***'},          {'**'}, {'***'}]),
+            (['a', '***'], [{'a/***', 'A/***'}, {'a/*', 'A/*'},                     {'**'}, {'***'}]),
+            (['b', '***'], [{'b/***'},          {'b/*'},                            {'**'}, {'***'}]),
+            (['a', '**'],  [{'a/**', 'A/**'},   {'a/*', 'A/*'}, {'a/***', 'A/***'}, {'**'}, {'***'}]),
+            (['b', '**'],  [{'b/**'},           {'b/*'},        {'b/***'},          {'**'}, {'***'}]),
+            (['a', '*'],   [{'a/*', 'A/*'},                     {'a/***', 'A/***'}, {'**'}, {'***'}]),
+            (['b', '*'],   [{'b/*'},                            {'b/***'},          {'**'}, {'***'}]),
+
+            (['a', 'c', 'd'], [{'a/**', 'A/**'}, {'a/***', 'A/***'}, {'**'}, {'***'}]),
+            (['b', 'c', 'd'], [{'b/**'},         {'b/***'},          {'**'}, {'***'}])
+    ]:
+        result = execute_in_page(
+            '''
+            returnval([...search_sequence(branch, arguments[0])]);
+            ''',
+            sequence)
+
+        try:
+            assert len(result) == len(expected)
+
+            for expected_set, result_array in zip(expected, result):
+                assert len(expected_set) == len(result_array)
+                assert expected_set      == set(result_array)
+        except Exception as e:
+            import sys
+            print('sequence:', sequence, '\nexpected:', expected,
+                  '\nresult:', result, file=sys.stderr)
+            raise e from None