From 5c583de820c0d5f666a830ca1e8205fe7d55e61e Mon Sep 17 00:00:00 2001 From: Wojtek Kosior Date: Wed, 1 Dec 2021 21:08:03 +0100 Subject: start implementing more efficient querying of URL patterns --- test/unit/conftest.py | 2 +- test/unit/test_patterns.py | 62 ++++++++ test/unit/test_patterns_query_tree.py | 283 ++++++++++++++++++++++++++++++++++ 3 files changed, 346 insertions(+), 1 deletion(-) create mode 100644 test/unit/test_patterns_query_tree.py (limited to 'test') 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 -- cgit v1.2.3