/common/patterns_query_tree.js - Diff - Haketilo - Hydrilla issue tracker

« Previous | Next »

Revision e1282a63

Added by koszko almost 2 years ago

ID e1282a63d6e41d437dd1b14a08baf89b78ab56cc
Parent 44bb618a
Child c8fa3926

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.

      * 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,
-...
         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);
-...
+        }
+    }
     /*
      * 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
-...
          */
         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
+    }
     /*

Also available in: Unified diff