plugin/boomerang/boomerang-1.0.0.js
/**
	 * Converts entries to a Trie (`splitAtPath=true`) or Radix
	 * Trie (`splitAtPath=false`):
	 * https://en.wikipedia.org/wiki/Trie
	 * https://en.wikipedia.org/wiki/Radix_tree
	 *
	 * Assumptions:
	 * 1) All entries have unique keys
	 * 2) Keys cannot have "|" in their name.
	 * 3) All key's values are strings
	 *
	 * Leaf nodes in the tree are the key's values.
	 *
	 * If key A is a prefix to key B, key A will be suffixed with "|".
	 *
	 * By default, the Trie is constructed "perfectly" (a Radix Trie) by looking
	 * at every letter of each URL.  If `splitAtPath` is specified, the URL is
	 * split up into groups based on the path separator. This will create a
	 * non-optimal Trie but will speed up the Trie construction significantly
	 * (taking less than a half or third of the time on large data sets).
	 *
	 * @param {object} entries Performance entries
	 * @param {boolean} [splitAtPath] Whether to split at path separator vs every character
	 *
	 * @returns {object} A trie
	 */


1) All entries have unique keys
2) Keys cannot have "|" in their name.
3) All key's values are strings

Leaf nodes in the tree are the key's values.

If key A is a prefix to key B, key A will be suffixed with "|".

By default, the Trie is constructed "perfectly" (a Radix Trie) by looking
at every letter of each URL.  If `splitAtPath` is specified, the URL is
split up into groups based on the path separator. This will create a
non-optimal Trie but will speed up the Trie construction significantly
(taking less than a half or third of the time on large data sets).

@param {object} entries Performance entries
@param {boolean} [splitAtPath] Whether to split at path separator vs every character

@returns {object} A trie
1 ) All entries have unique keys 2 ) Keys cannot have " | " in their name . 3 ) All key ' s values are strings Leaf nodes in the tree are the key ' s values . If key A is a prefix to key B key A will be suffixed with " | " . By default the Trie is constructed " perfectly " ( a Radix Trie ) by looking at every letter of each URL . If ` splitAtPath ` is specified the URL is split up into groups based on the path separator . This will create a non - optimal Trie but will speed up the Trie construction significantly ( taking less than a half or third of the time on large data sets ) . @param { object } entries Performance entries @param { boolean } [ splitAtPath ] Whether to split at path separator vs every character @returns { object } A trie
function convertToTrie(entries, splitAtPath) {
		var trie = {}, url, urlFixed, i, value, letters, letter, cur, node;
		function splitUrlPaths(addSlashUntil) {
			return function(accumulator, currentValue, currentIndex) {
				var parts, j;
				if (currentValue.indexOf(XSS_BREAK_DELIM) !== -1) {
					parts = currentValue.split(XSS_BREAK_DELIM);
					for (j = 0; j < parts.length - 1; j++) {
						accumulator.push(parts[j]);
						accumulator.push(XSS_BREAK_DELIM);
					}
					currentValue = parts.slice(-1);
				}
				if (typeof addSlashUntil === "number" && currentIndex < addSlashUntil) {
					currentValue += "/";
				}
				return accumulator.concat(currentValue);
			};
		}
		for (url in entries) {
			urlFixed = url;
			for (i = 0; i < impl.xssBreakWords.length; i++) {
				urlFixed = urlFixed.replace(impl.xssBreakWords[i], "$1" + XSS_BREAK_DELIM + "$2");
			}
			if (!entries.hasOwnProperty(url)) {
				continue;
			}
			value = entries[url];
			if (splitAtPath) {
				 Split the Trie based on the path (less CPU, less optimial result)
				letters = urlFixed.split("/");
				letters = [
					 protocol
					letters[0] + "",
					 hostname and optional slash
					letters[2] + (letters.length > 3 ? "/" : "")
				 all of the path parts
				].concat(letters.slice(3).reduce(splitUrlPaths(letters.length - 4), []));
			}
			else {
				 Split at every letter (more CPU, perfect result)
				letters = urlFixed.split("");
			}
			 start at the top of the Trie
			cur = trie;
			for (i = 0; i < letters.length; i++) {
				letter = letters[i];
				node = cur[letter];
				if (typeof node === "undefined") {
					 nothing exists yet, create either a leaf if this is the end of the word,
					 or a branch if there are letters to go
					cur = cur[letter] = (i === (letters.length - 1) ? value : {});
				}
				else if (typeof node === "string") {
					 this is a leaf, but we need to go further, so convert it into a branch
					cur = cur[letter] = { "|": node };
				}
				else {
					if (i === (letters.length - 1)) {
						 this is the end of our key, and we've hit an existing node.  Add our timings.
						cur[letter]["|"] = value;
					}
					else {
						 continue onwards
						cur = cur[letter];
					}
				}
			}
		}
		return trie;
	}
function convertToTrie ( entries , splitAtPath ) { var trie = { } , url , urlFixed , i , value , letters , letter , cur , node ; function splitUrlPaths ( addSlashUntil ) { return function ( accumulator , currentValue , currentIndex ) { var parts , j ; if ( currentValue . indexOf ( XSS_BREAK_DELIM ) !== - 1 ) { parts = currentValue . split ( XSS_BREAK_DELIM ) ; for ( j = 0 ; j < parts . length - 1 ; j ++ ) { accumulator . push ( parts [ j ] ) ; accumulator . push ( XSS_BREAK_DELIM ) ; } currentValue = parts . slice ( - 1 ) ; } if ( typeof addSlashUntil === "number" && currentIndex < addSlashUntil ) { currentValue += "/" ; } return accumulator . concat ( currentValue ) ; } ; } for ( url in entries ) { urlFixed = url ; for ( i = 0 ; i < impl . xssBreakWords . length ; i ++ ) { urlFixed = urlFixed . replace ( impl . xssBreakWords [ i ] , "$1" + XSS_BREAK_DELIM + "$2" ) ; } if ( ! entries . hasOwnProperty ( url ) ) { continue ; } value = entries [ url ] ; if ( splitAtPath ) { letters = urlFixed . split ( "/" ) ; letters = [ letters [ 0 ] + "//" , letters [ 2 ] + ( letters . length > 3 ? "/" : "" ) ] . concat ( letters . slice ( 3 ) . reduce ( splitUrlPaths ( letters . length - 4 ) , [ ] ) ) ; } else { letters = urlFixed . split ( "" ) ; } cur = trie ; for ( i = 0 ; i < letters . length ; i ++ ) { letter = letters [ i ] ; node = cur [ letter ] ; if ( typeof node === "undefined" ) { cur = cur [ letter ] = ( i === ( letters . length - 1 ) ? value : { } ) ; } else if ( typeof node === "string" ) { cur = cur [ letter ] = { "|" : node } ; } else { if ( i === ( letters . length - 1 ) ) { cur [ letter ] [ "|" ] = value ; } else { cur = cur [ letter ] ; } } } } return trie ; }
Converts entries to a Trie (`splitAtPath=true`) or Radix
 Trie (`splitAtPath=false`):
 https://en.wikipedia.org/wiki/Trie
 https://en.wikipedia.org/wiki/Radix_tree
Converts entries to a Trie ( ` splitAtPath = true ` ) or Radix Trie ( ` splitAtPath = false ` ) : https : // en . wikipedia . org / wiki / Trie https : // en . wikipedia . org / wiki / Radix_tree
/**
		 * Builds an array of path components.
		 *
		 * @param {number} addSlashUntil Length of path components
		 */ // if this component has the XSS_BREAK_DELIM character in it, we need // to break it up // break at that character // add everything but the last one with special XSS_BREAK_DELIM nodes // add this component // add back in the XSS_BREAK_DELIM // add the last part // add a '/' for everything but the last one // find any strings to break // Add a XSS_BREAK_DELIM character after the first letter.  optimizeTrie will // ensure this sequence doesn't get combined. // // Split the Trie based on the path (less CPU, less optimial result) // // protocol // hostname and optional slash // all of the path parts // // Split at every letter (more CPU, perfect result) // // start at the top of the Trie // nothing exists yet, create either a leaf if this is the end of the word, // or a branch if there are letters to go // this is a leaf, but we need to go further, so convert it into a branch // this is the end of our key, and we've hit an existing node.  Add our timings. // continue onwards