From e1282a63d6e41d437dd1b14a08baf89b78ab56cc Mon Sep 17 00:00:00 2001 From: Wojtek Kosior Date: Sat, 4 Dec 2021 19:31:43 +0100 Subject: 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. --- test/unit/test_patterns_query_tree.py | 200 +++++++++++++++++++++++++++++++++- 1 file changed, 196 insertions(+), 4 deletions(-) (limited to 'test/unit/test_patterns_query_tree.py') 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 == {} -- cgit v1.2.3