structured.js

/*
 * StructuredJS provides an API for static analysis of code based on an abstract
 * syntax tree generated by Esprima (compliant with the Mozilla Parser
 * API at https://developer.mozilla.org/en-US/docs/SpiderMonkey/Parser_API).
 *
 * Dependencies: esprima.js, underscore.js
 */
(function(global) {
    /* Detect npm versus browser usage */
    var exports;
    var esprima;
    var _;

    // Cache all the structure tests
    var structureCache = {};

    // Cache the most recently-parsed code and tree
    var cachedCode;
    var cachedCodeTree;

    if (typeof module !== "undefined" && module.exports) {
        exports = module.exports = {};
        esprima = require("esprima");
        _ = require("underscore");
    } else {
        exports = this.Structured = {};
        esprima = global.esprima;
        _ = global._;
    }

    if (!esprima || !_) {
        throw "Error: Both Esprima and UnderscoreJS are required dependencies.";
    }

    /*
     * Introspects a callback to determine it's parameters and then
     * produces a constraint that contains the appropriate variables and callbacks.
     *
     * This allows a much terser definition of callback function where you don't have to
     * explicitly state the parameters in a separate list
     */
    function makeConstraint(callback) {
        var paramText = /^function [^\(]*\(([^\)]*)\)/.exec(callback)[1];
        var params = paramText.match(/[$_a-zA-z0-9]+/g);

        for (var key in params) {
            if (params[key][0] !== "$") {
                console.warn("Invalid parameter in constraint (should begin with a '$'): ", params[key]);
                return null;
            }
        }
        return {
            variables: params,
            fn: callback
        };
    }
    
    /*
     * return true if n2 < n1 (according to relatively arbitrary criteria)
     */
    function shouldSwap(n1, n2) {
    if (n1.type < n2.type) { //Sort by node type if different
        return false;
    } else if (n1.type > n2.type) {
        return true;
    } else if (n1.type === "Literal") { //Sort by value if they're literals
        return n1.raw > n2.raw;
    } else { //Otherwise, loop through the properties until a difference is found and sort by that
        for (var k in n1) {
        if (n1[k].hasOwnProperty("type") && n1[k] !== n2[k]) {
            return shouldSwap(n1[k], n2[k]);
        }
        }
    }
    }
    function standardizeTree(tree) {
    if (!tree) {return tree;}
        var r = deepClone(tree);
        switch (tree.type) {
            case "BinaryExpression":
                if (_.contains(["*", "+", "===", "!==", "==", "!=", "&", "|", "^"], tree.operator)) {
            if (shouldSwap(tree.left, tree.right)) {
            r.left = standardizeTree(tree.right);
            r.right = standardizeTree(tree.left);
            } else {
                r.left = standardizeTree(tree.left);
                r.right = standardizeTree(tree.right);
            }
        } else if (tree.operator[0] === ">") {
            r.operator = "<" + tree.operator.slice(1);
            r.left = standardizeTree(tree.right);
            r.right = standardizeTree(tree.left);
        } break;
        case "LogicalExpression":
            if (_.contains(["&&", "||"], tree.operator) &&
            shouldSwap(tree.left, tree.right)) {
            r.left = standardizeTree(tree.right);
            r.right = standardizeTree(tree.left);
        } break;
        case "AssignmentExpression":
            if (_.contains(["+=", "-=", "*=", "/=", "%=", "<<=", ">>=", ">>>=", "&=", "^=", "|="], tree.operator)) {
            var l = standardizeTree(tree.left);
            r = {type: "AssignmentExpression",
             operator: "=",
             left: l,
             right: {type: "BinaryExpression",
                 operator: tree.operator.slice(0,-1),
                 left: l,
                 right: standardizeTree(tree.right)}};
        } else {
            r.left = standardizeTree(r.left);
            r.right = standardizeTree(r.right);
        } break;
        case "UpdateExpression":
            if (_.contains(["++", "--"], tree.operator)) {
            var l = standardizeTree(tree.argument);
            r = {type: "AssignmentExpression",
             operator: "=",
             left: l,
             right: {type: "BinaryExpression",
                 operator: tree.operator[0],
                 left: l,
                 right: {type: "Literal",
                     value: 1,
                     raw: "1"}}};
        } break;
        case "VariableDeclaration":
            if (tree.kind === "var") {
            r = [deepClone(tree)];
            for (var i in tree.declarations) {
            if (tree.declarations[i].type === "VariableDeclarator" &&
                tree.declarations[i].init !== null) {
                r.push({type: "ExpressionStatement",
                    expression: {type: "AssignmentExpression",
                         operator: "=",
                         left: tree.declarations[i].id,
                         right: standardizeTree(tree.declarations[i].init)}});
                r[0].declarations[i].init = null;
            }
            }
        } break;
        case "Literal":
            r.raw = tree.raw
                .replace(/^(?:\"(.*?)\"|\'(.*?)\')$/, function(match, p1, p2) {
                    return "\"" + ((p1 || "") + (p2 || ""))
                        .replace(/"|'/g, "\"") + "\"";
                });
            console.log(r.raw); break;
        default:
            for (var key in tree) {
            if (!tree.hasOwnProperty(key) || !_.isObject(tree[key])) {
            continue;
            }
            if (_.isArray(tree[key])) {
            var ar = [];
            for (var i in tree[key]) {  /* jshint forin:false */
                ar = ar.concat(standardizeTree(tree[key][i]));
            }
            r[key] = ar;
            } else {
            r[key] = standardizeTree(tree[key]);
            }
        }
        }
        return r;
    }

    /*
     * Returns true if the code (a string) matches the structure in rawStructure
     * Throws an exception if code is not parseable.
     *
     * Example:
     *     var code = "if (y > 30 && x > 13) {x += y;}";
     *     var rawStructure = function structure() { if (_) {} };
     *     match(code, rawStructure);
     *
     * options.varCallbacks is an object that maps user variable strings like
     *  "$myVar", "$a, $b, $c" etc to callbacks. These callbacks receive the
     *  potential Esprima structure values assigned to each of the user
     *  variables specified in the string, and can accept/reject that value
     *  by returning true/false. The callbacks can also specify a failure
     *  message instead by returning an object of the form
     *  {failure: "Your failure message"}, in which case the message will be
     *  returned as the property "failure" on the varCallbacks object if
     *  there is no valid match. A valid matching requires that every
     *  varCallback return true.
     *
     * Advanced Example:
     *   var varCallbacks = [
     *     function($foo) {
     *         return $foo.value > 92;
     *     },
     *     function($foo, $bar, $baz) {
     *         if ($foo.value > $bar.value) {
     *            return {failure: "Check the relationship between values."};
     *         }
     *         return $baz.value !== 48;
     *     }
     *   ];
     *   var code = "var a = 400; var b = 120; var c = 500; var d = 49;";
     *   var rawStructure = function structure() {
     *       var _ = $foo; var _ = $bar; var _ = $baz;
     *   };
     *   match(code, rawStructure, {varCallbacks: varCallbacks});
     */
    var originalVarCallbacks;
    function match(code, rawStructure, options) {
        options = options || {};
        // Many possible inputs formats are accepted for varCallbacks
        // Constraints can be:
        // 1. a function (from which we will extract the variables)  
        // 2. an objects (which already has separate .fn and .variables properties)
        //
        // It will also accept a list of either of the above (or a mix of the two).
        // Finally it can accept an object for which the keys are the variables and 
        // the values are the callbacks (This option is mainly for historical reasons)
        var varCallbacks = options.varCallbacks || [];
        // We need to keep a hold of the original varCallbacks object because 
        // When structured first came out it returned the failure message by 
        // changing the .failure property on the varCallbacks object and some uses rely on that.
        // We hope to get rid of this someday.
        // TODO: Change over the code so to have a better API
        originalVarCallbacks = varCallbacks;
        if (varCallbacks instanceof Function || (varCallbacks.fn && varCallbacks.variables)) {
            varCallbacks = [varCallbacks];
        }
        if (varCallbacks instanceof Array) {
            for (var key in varCallbacks) {
                if (varCallbacks[key] instanceof Function) {
                    varCallbacks[key] = makeConstraint(varCallbacks[key]);
                }
            }
        } else {
            var realCallbacks = [];
            for (var vars in varCallbacks) {
                if (varCallbacks.hasOwnProperty(vars) && vars !== "failure") {
                    realCallbacks.push({
                        variables: vars.match(/[$_a-zA-z0-9]+/g),
                        fn: varCallbacks[vars]
                    });
                }
            }
            varCallbacks = realCallbacks;
        }
        var wildcardVars = {
            order: [],
            skipData: {},
            values: {}
        };
        // Note: After the parse, structure contains object references into
        // wildcardVars[values] that must be maintained. So, beware of
        // JSON.parse(JSON.stringify), etc. as the tree is no longer static.
        var structure = parseStructureWithVars(rawStructure, wildcardVars);

        // Cache the parsed code tree, or pull from cache if it exists
        var codeTree = (cachedCode === code ?
            cachedCodeTree :
            typeof code === "object" ?
            deepClone(code) :
            esprima.parse(code));

        cachedCode = code;
        cachedCodeTree = codeTree;

        foldConstants(codeTree);
        var toFind = structure.body || structure;
        var peers = [];
        if (_.isArray(structure.body)) {
            toFind = structure.body[0];
            peers = structure.body.slice(1);
        }
        var result;
        var matchResult = {
            _: [],
            vars: {}
        };
    codeTree = standardizeTree(codeTree);
        if (wildcardVars.order.length === 0 || options.single) {
            // With no vars to match, our normal greedy approach works great.
            result = checkMatchTree(codeTree, toFind, peers, wildcardVars, matchResult, options);
        } else {
            // If there are variables to match, we must do a potentially
            // exhaustive search across the possible ways to match the vars.
            result = anyPossible(0, wildcardVars, varCallbacks, matchResult, options);
        }
        return result;

        /*
         * Checks whether any possible valid variable assignment for this i
         *  results in a valid match.
         *
         * We orchestrate this check by building skipData, which specifies
         *  for each variable how many possible matches it should skip before
         *  it guesses a match. The iteration over the tree is the same
         *  every time -- if the first guess fails, the next run will skip the
         *  first guess and instead take the second appearance, and so on.
         *
         * When there are multiple variables, changing an earlier (smaller i)
         *  variable guess means that we must redo the guessing for the later
         *  variables (larger i).
         *
         * Returning false involves exhausting all possibilities. In the worst
         *  case, this will mean exponentially many possibilities -- variables
         *  are expensive for all but small tests.
         *
         * wildcardVars = wVars:
         *     .values[varName] contains the guessed node value of each
         *     variable, or the empty object if none.
         *     .skipData[varName] contains the number of potential matches of
         *          this var to skip before choosing a guess to assign to values
         *     .leftToSkip[varName] stores the number of skips left to do
         *         (used during the match algorithm)
         *     .order[i] is the name of the ith occurring variable.
         */
        function anyPossible(i, wVars, varCallbacks, matchResults, options) {
            var order = wVars.order; // Just for ease-of-notation.
            wVars.skipData[order[i]] = 0;
            do {
                // Reset the skip # for all later variables.
                for (var rest = i + 1; rest < order.length; rest += 1) {
                    wVars.skipData[order[rest]] = 0;
                }
                // Check for a match only if we have reached the last var in
                // order (and so set skipData for all vars). Otherwise,
                // recurse to check all possible values of the next var.
                if (i === order.length - 1) {
                    // Reset the wildcard vars' guesses. Delete the properties
                    // rather than setting to {} in order to maintain shared
                    // object references in the structure tree (toFind, peers)
                    _.each(wVars.values, function(value, key) {
                        _.each(wVars.values[key], function(v, k) {
                            delete wVars.values[key][k];
                        });
                    });
                    wVars.leftToSkip = _.extend({}, wVars.skipData);
                    // Use a copy of peers because peers is destructively
                    // modified in checkMatchTree (via checkNodeArray).
                    if (checkMatchTree(codeTree, toFind, peers.slice(), wVars, matchResults, options) &&
                        checkUserVarCallbacks(wVars, varCallbacks)) {
                        return matchResults;
                    }
                } else if (anyPossible(i + 1, wVars, varCallbacks, matchResults, options)) {
                    return matchResults;
                }
                // This guess didn't work out -- skip it and try the next.
                wVars.skipData[order[i]] += 1;
                // The termination condition is when we have run out of values
                // to skip and values is no longer defined for this var after
                // the match algorithm. That means that there is no valid
                // assignment for this and later vars given the assignments to
                // previous vars (set by skipData).
            } while (!_.isEmpty(wVars.values[order[i]]));
            return false;
        }
    }

    /*
     * Checks the user-defined variable callbacks and returns a boolean for
     *   whether or not the wVars assignment of the wildcard variables results
     *   in every varCallback returning true as required.
     *
     * If any varCallback returns false, this function also returns false.
     *
     * Format of varCallbacks: An object containing:
     *     keys of the form: "$someVar" or "$foo, $bar, $baz" to mimic an
     *        array (as JS keys must be strings).
     *     values containing function callbacks. These callbacks must return
     *        true/false. They may alternately return an object of the form
     *        {failure: "The failure message."}. If the callback returns the
     *        failure object, then the relevant failure message will be returned
     *        via varCallbacks.failure.
     *        These callbacks are passed a parameter list corresponding to
     *         the Esprima parse structures assigned to the variables in
     *         the key (see example).
     *
     * Example varCallbacks object:
     *    {
     *     "$foo": function(fooObj) {
     *         return fooObj.value > 92;
     *     },
     *     "$foo, $bar, $baz": function(fooObj, barObj, bazObj) {
     *         if (fooObj.value > barObj.value) {
     *            return {failure: "Check the relationship between values."}
     *         }
     *         return bazObj !== 48;
     *     }
     *   }
     */
    function checkUserVarCallbacks(wVars, varCallbacks) {
        // Clear old failure message if needed
        delete originalVarCallbacks.failure;
        for (var key in varCallbacks) {  /* jshint forin:false */
            // Property strings may be "$foo, $bar, $baz" to mimic arrays.
            var varNames = varCallbacks[key].variables;
            var varValues = _.map(varNames, function(varName) {
                varName = stringLeftTrim(varName); // Trim whitespace
                // If the var name is in the structure, then it will always
                // exist in wVars.values after we find a match prior to
                // checking the var callbacks. So, if a variable name is not
                // defined here, it is because that var name does not exist in
                // the user-defined structure.
                if (!_.has(wVars.values, varName)) {
                    console.error("Callback var " + varName + " doesn't exist");
                    return undefined;
                }
                // Convert each var name to the Esprima structure it has
                // been assigned in the parse. Make a deep copy.
                return deepClone(wVars.values[varName]);
            });
            // Call the user-defined callback, passing in the var values as
            // parameters in the order that the vars were defined in the
            // property string.
            var result = varCallbacks[key].fn.apply(null, varValues);
            if (!result || _.has(result, "failure")) {
                // Set the failure message if the user callback provides one.
                if (_.has(result, "failure")) {
                    originalVarCallbacks.failure = result.failure;
                }
                return false;
            }
        }
        return true;

        /* Trim is only a string method in IE9+, so use a regex if needed. */
        function stringLeftTrim(str) {
            if (String.prototype.trim) {
                return str.trim();
            }
            return str.replace(/^\s+|\s+$/g, "");
        }
    }

    function parseStructure(structure) {
        if (typeof structure === "object") {
            return deepClone(structure);
        }

        if (structureCache[structure]) {
            return JSON.parse(structureCache[structure]);
        }

        // Wrapped in parentheses so function() {} becomes valid Javascript.
        var fullTree = esprima.parse("(" + structure + ")");

        if (fullTree.body[0].expression.type !== "FunctionExpression" ||
            !fullTree.body[0].expression.body) {
            throw "Poorly formatted structure code";
        }

        var tree = fullTree.body[0].expression.body;
        structureCache[structure] = JSON.stringify(tree);
        return tree;
    }

    /*
     * Returns a tree parsed out of the structure. The returned tree is an
     *    abstract syntax tree with wildcard properties set to undefined.
     *
     * structure is a specification looking something like:
     *        function structure() {if (_) { var _ = 3; }}
     *    where _ denotes a blank (anything can go there),
     *    and code can go before or after any statement (only the nesting and
     *        relative ordering matter).
     */
    function parseStructureWithVars(structure, wVars) {
        var tree = standardizeTree(parseStructure(structure));
        foldConstants(tree);
        simplifyTree(tree, wVars);
        return tree;
    }

    /*
     * Constant folds the syntax tree
     */
    function foldConstants(tree) {
        for (var key in tree) {  /* jshint forin:false */
            if (!tree.hasOwnProperty(key)) {
                continue; // Inherited property
            }

            var ast = tree[key];
            if (_.isObject(ast)) {
                foldConstants(ast);

                /*
                 * Currently, we only fold + and - applied to a number literal.
                 * This is easy to extend, but it means we lose the ability to match
                 * potentially useful expressions like 5 + 5 with a pattern like _ + _.
                 */
                /* jshint eqeqeq:false */
                if (ast.type == esprima.Syntax.UnaryExpression) {
                    var argument = ast.argument;
                    if (argument.type === esprima.Syntax.Literal &&
                        _.isNumber(argument.value)) {
                        if (ast.operator === "-") {
                            argument.value = -argument.value;
                            tree[key] = argument;
                        } else if (ast.operator === "+") {
                            argument.value = +argument.value;
                            tree[key] = argument;
                        }
                    }
                }
            }
        }
    }

    /*
     * Recursively traverses the tree and sets _ properties to undefined
     * and empty bodies to null.
     *
     *  Wildcards are explicitly set to undefined -- these undefined properties
     *  must exist and be non-null in order for code to match the structure.
     *
     *  Wildcard variables are set up such that the first occurrence of the
     *   variable in the structure tree is set to {wildcardVar: varName},
     *   and all later occurrences just refer to wVars.values[varName],
     *   which is an object assigned during the matching algorithm to have
     *   properties identical to our guess for the node matching the variable.
     *   (maintaining the reference). In effect, these later accesses
     *   to tree[key] mimic tree[key] simply being set to the variable value.
     *
     *  Empty statements are deleted from the tree -- they need not be matched.
     *
     *  If the subtree is an array, we just iterate over the array using
     *    for (var key in tree)
     *
     */
    function simplifyTree(tree, wVars) {
        for (var key in tree) {  /* jshint forin:false */
            if (!tree.hasOwnProperty(key)) {
                continue; // Inherited property
            }
            if (_.isObject(tree[key])) {
                if (isWildcard(tree[key])) {
                    tree[key] = undefined;
                } else if (isWildcardVar(tree[key])) {
                    var varName = tree[key].name;
                    if (!wVars.values[varName]) {
                        // Perform setup for the first occurrence.
                        wVars.values[varName] = {}; // Filled in later.
                        tree[key] = {
                            wildcardVar: varName
                        };
                        wVars.order.push(varName);
                        wVars.skipData[varName] = 0;
                    } else {
                        tree[key] = wVars.values[varName]; // Reference.
                    }
                } else if (tree[key].type === esprima.Syntax.EmptyStatement) {
                    // Arrays are objects, but delete tree[key] does not
                    //  update the array length property -- so, use splice.
                    _.isArray(tree) ? tree.splice(key, 1) : delete tree[key];
                } else {
                    simplifyTree(tree[key], wVars);
                }
            }
        }
    }

    /*
     * Returns whether the structure node is intended as a wildcard node, which
     * can be filled in by anything in others' code.
     */
    function isWildcard(node) {
        return node.name && node.name === "_";
    }

    /* Returns whether the structure node is intended as a wildcard variable. */
    function isWildcardVar(node) {
        return (node.name && _.isString(node.name) && node.name.length >= 2 &&
            node.name[0] === "$");
    }

    /*
     *
     */
    function isGlob(node) {
        return node && node.name &&
            ((node.name === "glob_" && "_") ||
                (node.name.indexOf("glob$") === 0 && node.name.slice(5))) ||
            node && node.expression && isGlob(node.expression);
    }

    /*
     * Returns true if currTree matches the wildcard structure toFind.
     *
     * currTree: The syntax node tracking our current place in the user's code.
     * toFind: The syntax node from the structure that we wish to find.
     * peersToFind: The remaining ordered syntax nodes that we must find after
     *     toFind (and on the same level as toFind).
     * modify: should it call RestructureTree()?
     */
    function checkMatchTree(currTree, toFind, peersToFind, wVars, matchResults, options) {
        if (_.isArray(toFind)) {
            console.error("toFind should never be an array.");
            console.error(toFind);
        }
        /* jshint -W041, -W116 */
        if (currTree == undefined) {
            if (toFind == undefined) {
                matchResults._.push(currTree);
                return matchResults;
            } else {
                return false;
            }
        }
        if (exactMatchNode(currTree, toFind, peersToFind, wVars, matchResults, options)) {
            return matchResults;
        }
        // Don't recurse if we're just checking a single node.
        if (options.single) {
            return false;
        }
        // Check children.
        for (var key in currTree) {  /* jshint forin:false */
            if (!currTree.hasOwnProperty(key) || !_.isObject(currTree[key])) {
                continue; // Skip inherited properties
            }
            // Recursively check for matches
            if ((_.isArray(currTree[key]) &&
                    checkNodeArray(currTree[key], toFind, peersToFind, wVars, matchResults, options, true)) ||
                (!_.isArray(currTree[key]) &&
                    checkMatchTree(currTree[key], toFind, peersToFind, wVars, matchResults, options, true))) {
                return matchResults;
            }
        }
        return false;
    }

    /*
     * Returns true if this level of nodeArr matches the node in
     * toFind, and also matches all the nodes in peersToFind in order.
     */
    function checkNodeArray(nodeArr, toFind, peersToFind, wVars, matchResults, options) {
        var curGlob;

        for (var i = 0; i < nodeArr.length; i += 1) {
            if (isGlob(toFind)) {
                if (!curGlob) {
                    curGlob = [];
                    var globName = isGlob(toFind);
                    if (globName === "_") {
                        matchResults._.push(curGlob);
                    } else {
                        matchResults.vars[globName] = curGlob;
                    }
                }
                curGlob.push(nodeArr[i]);
            } else if (checkMatchTree(nodeArr[i], toFind, peersToFind, wVars, matchResults, options)) {
                if (!peersToFind || peersToFind.length === 0) {
                    return matchResults;
                    // Found everything needed on this level.
                } else {
                    // We matched this node, but we still have more nodes on
                    // this level we need to match on subsequent iterations
                    toFind = peersToFind.shift(); // Destructive.
                }
            }
        }

        if (curGlob) {
            return matchResults;
        } else if (isGlob(toFind)) {
            var globName = isGlob(toFind);
            if (globName === "_") {
                matchResults._.push([]);
            } else {
                matchResults.vars[globName] = [];
            }
            return matchResults;
        }

        return false;
    }


    /*
     * This discards all wildcard vars that were part of a failed match
     * this provides an important speedup by stopping anyPossible from having to increment
     * every match on a doomed set of arguments.
     * If the any argument set fails no amount of incrementing can save it.
     */
    function discardWVarsOnFailureDecorator(callback) {
        return function(currTree, toFind, peersToFind, wVars, matchResults, options) {
            var lastWVar;
            for (lastWVar=0; lastWVar<wVars.order.length; lastWVar++) {
                var candidate = wVars.values[wVars.order[lastWVar]];
                if (_.isEmpty(candidate)) {
                    break;
                }
            }
            var result = callback(currTree, toFind, peersToFind, wVars, matchResults, options);
            if (!result) {
                for (; lastWVar<wVars.order.length; lastWVar++) {
                    var candidate = wVars.values[wVars.order[lastWVar]];
                    if (!_.isEmpty(candidate)) {
                        // Reset the wildcard vars' guesses. Delete the properties
                        // rather than setting to {} in order to maintain shared
                        // object references in the structure tree (toFind, peers)
                        _.each(candidate, function(v, k) {
                            delete candidate[k];
                        });
                    } else {
                        break;
                    }
                }
                wVars._last = lastWVar;
            }
            return result;
        };
    }

    /*
     * Returns true if and only if all arguments from the pattern match the corresponding
     * argument in the test code
     */
    var checkArgumentsArray = discardWVarsOnFailureDecorator(function(nodeArr, toFind, peersToFind, wVars, matchResults, options) {
        var curGlob;

        for (var i = 0; i < nodeArr.length; i += 1) {
            if (isGlob(toFind)) {
                if (!curGlob) {
                    curGlob = [];
                    var globName = isGlob(toFind);
                    if (globName === "_") {
                        matchResults._.push(curGlob);
                    } else {
                        matchResults.vars[globName] = curGlob;
                    }
                }
                curGlob.push(nodeArr[i]);
            } else {
                if (checkMatchTree(nodeArr[i], toFind, peersToFind, wVars, matchResults, options)) {
                    if (!peersToFind || peersToFind.length === 0) {
                        return matchResults;
                    } else {
                        toFind = peersToFind.shift();
                    }
                } else {
                    return false;
                }
            }
        }

        if (curGlob) {
            return matchResults;
        } else if (isGlob(toFind)) {
            var globName = isGlob(toFind);
            if (globName === "_") {
                matchResults._.push([]);
            } else {
                matchResults.vars[globName] = [];
            }
            return matchResults;
        }

        return false;
    });

    /*
     * Checks whether the currNode exactly matches the node toFind.
     *
     * A match is exact if for every non-null property on toFind, that
     * property exists on currNode and:
     *     0. If the property is undefined on toFind, it must exist on currNode.
     *     1. Otherwise, the values have the same type (ie, they match).
     *     2. If the values are numbers or strings, they match.
     *     3. If the values are arrays, checkNodeArray on the arrays returns true.
     *     4. If the values are objects, checkMatchTree on those objects
     *         returns true (the objects recursively match to the extent we
     *         care about, though they may not match exactly).
     */
    function exactMatchNode(currNode, toFind, peersToFind, wVars, matchResults, options) {
        var rootToSet;

        if (!matchResults.root && currNode.type !== "Program") {
            rootToSet = currNode;
        }

        for (var key in toFind) {  /* jshint forin:false */
            // Ignore inherited properties; also, null properties can be
            // anything and do not have to exist.
            if (!toFind.hasOwnProperty(key) || toFind[key] === null) {
                continue;
            }
            var subFind = toFind[key];
            var subCurr = currNode[key];
            // Undefined properties can be anything, but they must exist.
            if (subFind === undefined) {
                /* jshint -W116 */
                if (subCurr == undefined) {
                    return false;
                } else {
                    matchResults._.push(subCurr);
                    continue;
                }
            }
            // currNode does not have the key, but toFind does
            if (subCurr == null) {
                if (key === "wildcardVar") {
                    if (wVars.leftToSkip && wVars.leftToSkip[subFind] > 0) {
                        wVars.leftToSkip[subFind] -= 1;
                        return false; // Skip, this does not match our wildcard
                    }
                    // We have skipped the required number, so take this guess.
                    // Copy over all of currNode's properties into
                    //  wVars.values[subFind] so the var references set up in
                    //  simplifyTree behave like currNode. Shallow copy.
                    _.extend(wVars.values[subFind], currNode);
                    matchResults.vars[subFind.slice(1)] = currNode;
                    if (rootToSet) {
                        matchResults.root = rootToSet;
                    }
                    return matchResults; // This node is now our variable.
                }
                return false;
            }
            // Now handle arrays/objects/values
            if (_.isObject(subCurr) !== _.isObject(subFind) ||
                _.isArray(subCurr) !== _.isArray(subFind) ||
                (typeof(subCurr) !== typeof(subFind))) {
                return false;
            } else if (_.isArray(subCurr)) {
                // Both are arrays, do a recursive compare.
                // (Arrays are objects so do this check before the object check)
                if (subFind.length === 0) {
                    continue; // Empty arrays can match any array.
                }
                var newToFind = subFind[0];
                var peers = subFind.slice(1);
                if (key === "params" || key === "arguments") {
                    if (!checkArgumentsArray(subCurr, newToFind, peers, wVars, matchResults, options)) {
                        return false;
                    }
                } else if (!checkNodeArray(subCurr, newToFind, peers, wVars, matchResults, options)) {
                    return false;
                }
            } else if (_.isObject(subCurr)) {
                // Both are objects, so do a recursive compare.
                if (!checkMatchTree(subCurr, subFind, peersToFind, wVars, matchResults, options)) {
                    return false;
                }
            } else {
                // Check that the non-object (number/string) values match
                if (subCurr !== subFind) {
                    return false;
                }
            }
        }
        if (toFind === undefined) {
            matchResults._.push(currNode);
        }
        if (rootToSet) {
            matchResults.root = rootToSet;
        }
        return matchResults;
    }

    function deepClone(obj) {
        return JSON.parse(JSON.stringify(obj));
    }

    /*
     * Takes in a string for a structure and returns HTML for nice styling.
     * The blanks (_) are enclosed in span.structuredjs_blank, and the
     * structured.js variables ($someVar) are enclosed in span.structuredjs_var
     * for special styling.
     *
     * See pretty-display/index.html for a demo and sample stylesheet.
     *
     * Only works when RainbowJS (http://craig.is/making/rainbows) is
     * included on the page; if RainbowJS is not available, simply
     * returns the code string. RainbowJS is not available as an npm
     * module.
     */
    function prettyHtml(code, callback) {
        if (!Rainbow) {
            return code;
        }
        Rainbow.color(code, "javascript", function(formattedCode) {
            var output = ("<pre class='rainbowjs'>" +
                addStyling(formattedCode) + "</pre>");
            callback(output);
        });
    }

    /*
     * Helper function for prettyHtml that takes in a string (the formatted
     * output of RainbowJS) and inserts special StructuredJS spans for
     * blanks (_) and variables ($something).
     *
     * The optional parameter maintainStyles should be set to true if the
     * caller wishes to keep the class assignments from the previous call
     * to addStyling and continue where we left off. This parameter is
     * valuable for visual consistency across different structures that share
     * variables.
     */
    function addStyling(code, maintainStyles) {
        if (!maintainStyles) {
            addStyling.styleMap = {};
            addStyling.counter = 0;
        }
        // First replace underscores with empty structuredjs_blank spans
        // Regex: Match any underscore _ that is not preceded or followed by an
        // alphanumeric character.
        code = code.replace(/(^|[^A-Za-z0-9])_(?![A-Za-z0-9])/g,
            "$1<span class='structuredjs_blank'></span>");
        // Next replace variables with empty structuredjs_var spans numbered
        // with classes.
        // This regex is in two parts:
        //  Part 1, delimited by the non-capturing parentheses `(?: ...)`:
        //    (^|[^\w])\$(\w+)
        //    Match any $ that is preceded by either a 'start of line', or a
        //    non-alphanumeric character, and is followed by at least one
        //    alphanumeric character (the variable name).
        //  Part 2, also delimited by the non-capturing parentheses:
        //      ()\$<span class="function call">(\w+)<\/span>
        //      Match any function call immediately preceded by a dollar sign,
        //      where the Rainbow syntax highlighting separated a $foo()
        //      function call by placing the dollar sign outside.
        //      the function call span to create
        //      $<span class="function call">foo</span>.
        // We combine the two parts with an | (an OR) so that either matches.
        // The reason we do this all in one go rather than in two separate
        // calls to replace is so that we color the string in order,
        // rather than coloring all non-function calls and then going back
        // to do all function calls (a minor point, but otherwise the
        // interactive pretty display becomes jarring as previous
        // function call colors change when new variables are introduced.)
        // Finally, add the /g flag for global replacement.
        var regexVariables = /(?:(^|[^\w])\$(\w+))|(?:\$<span class="function call">(\w+)<\/span>)/g;
        return code.replace(regexVariables,
            function(m, prev, varName, fnVarName) {
                // Necessary to handle the fact we are essentially performing
                // two regexes at once as outlined above.
                prev = prev || "";
                varName = varName || fnVarName;
                var fn = addStyling;
                // Assign the next available class to this variable if it does
                // not yet exist in our style mapping.
                if (!(varName in fn.styleMap)) {
                    fn.styleMap[varName] = (fn.counter < fn.styles.length ?
                        fn.styles[fn.counter] : "extra");
                    fn.counter += 1;
                }
                return (prev + "<span class='structuredjs_var " +
                    fn.styleMap[varName] + "'>" + "</span>");
            }
        );
    }
    // Store some properties on the addStyling function to maintain the
    // styleMap between runs if desired.
    // Right now just support 7 different variables. Just add more if needed.
    addStyling.styles = ["one", "two", "three", "four", "five", "six",
        "seven"
    ];
    addStyling.styleMap = {};
    addStyling.counter = 0;

    function getSingleData(node, data) {
        if (!node || node.type !== "Identifier") {
            return;
        }

        if (node.name === "_") {
            if (!data._ || data._.length === 0) {
                throw "No _ data available.";
            }

            return data._.shift();
        } else if (node.name && node.name.indexOf("$") === 0) {
            var name = node.name.slice(1);

            if (!data.vars || !(name in data.vars)) {
                throw "No vars available.";
            }

            return data.vars[name];
        }
    }

    function getGlobData(node, data) {
        var check = node && node.expression || node;

        if (!check || check.type !== "Identifier") {
            return;
        }

        if (check.name === "glob_") {
            if (!data._ || data._.length === 0) {
                throw "No _ data available.";
            }

            return data._.shift();
        } else if (check.name && check.name.indexOf("glob$") === 0) {
            var name = check.name.slice(5);

            if (!data.vars || !(name in data.vars)) {
                throw "No vars available.";
            }

            return data.vars[name];
        }
    }

    function injectData(node, data) {
        if (!node) {
            return node;
        }

        for (var prop in node) {  /* jshint forin:false */
            if (!node.hasOwnProperty(prop)) {
                continue;
            }

            if (node[prop] && typeof node[prop] === "object" && "length" in node[prop]) {
                for (var i = 0; i < node[prop].length; i++) {
                    var globData = getGlobData(node[prop][i], data);

                    if (globData) {
                        node[prop].splice.apply(node[prop],
                            [i, 1].concat(globData));
                        break;
                    } else if (typeof node[prop][i] === "object") {
                        var singleData = getSingleData(node[prop][i], data);

                        if (singleData) {
                            node[prop][i] = singleData;
                        } else if (typeof node[prop][i] === "object") {
                            injectData(node[prop][i], data);
                        }
                    }
                }
            } else {
                var singleData = getSingleData(node[prop], data);

                if (singleData) {
                    node[prop] = singleData;
                } else if (typeof node[prop] === "object") {
                    injectData(node[prop], data);
                }
            }
        }

        return node;
    }

    exports.match = match;
    exports.matchNode = function(code, rawStructure, options) {
        options = options || {};
        options.single = true;
        return match(code, rawStructure, options);
    };
    exports.injectData = function(node, data) {
        node = parseStructure(node);
        data = deepClone(data);
        return injectData(node, data);
    };
    exports.prettify = prettyHtml;
})(typeof window !== "undefined" ? window : global);