path: root/lib/ast.js

/***********************************************************************

  A JavaScript tokenizer / parser / beautifier / compressor.
  https://github.com/mishoo/UglifyJS

  -------------------------------- (C) ---------------------------------

                           Author: Mihai Bazon
                         <mihai.bazon@gmail.com>
                       http://mihai.bazon.net/blog

  Distributed under the BSD license:

    Copyright 2012 (c) Mihai Bazon <mihai.bazon@gmail.com>

    Redistribution and use in source and binary forms, with or without
    modification, are permitted provided that the following conditions
    are met:

        * Redistributions of source code must retain the above
          copyright notice, this list of conditions and the following
          disclaimer.

        * Redistributions in binary form must reproduce the above
          copyright notice, this list of conditions and the following
          disclaimer in the documentation and/or other materials
          provided with the distribution.

    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER “AS IS” AND ANY
    EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
    PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE
    LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
    OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
    TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
    THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    SUCH DAMAGE.

 ***********************************************************************/

"use strict";

function DEFNODE(type, props, methods, base) {
    if (typeof base === "undefined") base = AST_Node;
    props = props ? props.split(/\s+/) : [];
    var self_props = props;
    if (base && base.PROPS) props = props.concat(base.PROPS);
    var code = [
        "return function AST_", type, "(props){",
        "if(props){",
    ];
    props.forEach(function(prop) {
        code.push("this.", prop, "=props.", prop, ";");
    });
    var proto = base && new base;
    if (proto && proto.initialize || methods && methods.initialize) code.push("this.initialize();");
    code.push("}}");
    var ctor = new Function(code.join(""))();
    if (proto) {
        ctor.prototype = proto;
        ctor.BASE = base;
    }
    if (base) base.SUBCLASSES.push(ctor);
    ctor.prototype.CTOR = ctor;
    ctor.PROPS = props || null;
    ctor.SELF_PROPS = self_props;
    ctor.SUBCLASSES = [];
    if (type) {
        ctor.prototype.TYPE = ctor.TYPE = type;
    }
    if (methods) for (var name in methods) if (HOP(methods, name)) {
        if (/^\$/.test(name)) {
            ctor[name.substr(1)] = methods[name];
        } else {
            ctor.prototype[name] = methods[name];
        }
    }
    ctor.DEFMETHOD = function(name, method) {
        this.prototype[name] = method;
    };
    if (typeof exports !== "undefined") {
        exports["AST_" + type] = ctor;
    }
    return ctor;
}

var AST_Token = DEFNODE("Token", "type value line col pos endline endcol endpos nlb comments_before comments_after file raw", {
}, null);

var AST_Node = DEFNODE("Node", "start end", {
    _clone: function(deep) {
        if (deep) {
            var self = this.clone();
            return self.transform(new TreeTransformer(function(node) {
                if (node !== self) {
                    return node.clone(true);
                }
            }));
        }
        return new this.CTOR(this);
    },
    clone: function(deep) {
        return this._clone(deep);
    },
    $documentation: "Base class of all AST nodes",
    $propdoc: {
        start: "[AST_Token] The first token of this node",
        end: "[AST_Token] The last token of this node"
    },
    walk: function(visitor) {
        visitor.visit(this);
    },
    _validate: noop,
    validate: function() {
        var ctor = this.CTOR;
        do {
            ctor.prototype._validate.call(this);
        } while (ctor = ctor.BASE);
    },
    validate_ast: function() {
        var marker = {};
        this.walk(new TreeWalker(function(node) {
            if (node.validate_visited === marker) {
                throw new Error(string_template("cannot reuse {type} from [{file}:{line},{col}]", {
                    type: "AST_" + node.TYPE,
                    file: node.start.file,
                    line: node.start.line,
                    col: node.start.col,
                }));
            }
            node.validate_visited = marker;
        }));
    },
}, null);

(AST_Node.log_function = function(fn, verbose) {
    var printed = Object.create(null);
    if (fn) {
        AST_Node.info = verbose ? function(text, props) {
            log("INFO: " + string_template(text, props));
        } : noop;
        AST_Node.warn = function(text, props) {
            log("WARN: " + string_template(text, props));
        };
    } else {
        AST_Node.info = AST_Node.warn = noop;
    }

    function log(msg) {
        if (printed[msg]) return;
        printed[msg] = true;
        fn(msg);
    }
})();

var restore_transforms = [];
AST_Node.enable_validation = function() {
    AST_Node.disable_validation();
    (function validate_transform(ctor) {
        var transform = ctor.prototype.transform;
        ctor.prototype.transform = function(tw, in_list) {
            var node = transform.call(this, tw, in_list);
            if (node instanceof AST_Node) {
                node.validate();
            } else if (!(node === null || in_list && List.is_op(node))) {
                throw new Error("invalid transformed value: " + node);
            }
            return node;
        };
        restore_transforms.push(function() {
            ctor.prototype.transform = transform;
        });
        ctor.SUBCLASSES.forEach(validate_transform);
    })(this);
};

AST_Node.disable_validation = function() {
    var restore;
    while (restore = restore_transforms.pop()) restore();
};

/* -----[ statements ]----- */

var AST_Statement = DEFNODE("Statement", null, {
    $documentation: "Base class of all statements",
});

var AST_Debugger = DEFNODE("Debugger", null, {
    $documentation: "Represents a debugger statement",
}, AST_Statement);

var AST_Directive = DEFNODE("Directive", "value quote", {
    $documentation: "Represents a directive, like \"use strict\";",
    $propdoc: {
        value: "[string] The value of this directive as a plain string (it's not an AST_String!)",
        quote: "[string] the original quote character"
    },
    _validate: function() {
        if (typeof this.value != "string") throw new Error("value must be string");
    },
}, AST_Statement);

function must_be_expression(node, prop) {
    if (!(node[prop] instanceof AST_Node)) throw new Error(prop + " must be AST_Node");
    if (node[prop] instanceof AST_Statement && !(node[prop] instanceof AST_Function)) {
        throw new Error(prop + " cannot be AST_Statement");
    }
}

var AST_SimpleStatement = DEFNODE("SimpleStatement", "body", {
    $documentation: "A statement consisting of an expression, i.e. a = 1 + 2",
    $propdoc: {
        body: "[AST_Node] an expression node (should not be instanceof AST_Statement)"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.body.walk(visitor);
        });
    },
    _validate: function() {
        must_be_expression(this, "body");
    },
}, AST_Statement);

function walk_body(node, visitor) {
    node.body.forEach(function(node) {
        node.walk(visitor);
    });
}

var AST_Block = DEFNODE("Block", "body", {
    $documentation: "A body of statements (usually braced)",
    $propdoc: {
        body: "[AST_Statement*] an array of statements"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            walk_body(node, visitor);
        });
    },
    _validate: function() {
        this.body.forEach(function(node) {
            if (!(node instanceof AST_Statement)) throw new Error("body must be AST_Statement[]");
            if (node instanceof AST_Function) throw new Error("body cannot contain AST_Function");
        });
    },
}, AST_Statement);

var AST_BlockStatement = DEFNODE("BlockStatement", null, {
    $documentation: "A block statement",
}, AST_Block);

var AST_EmptyStatement = DEFNODE("EmptyStatement", null, {
    $documentation: "The empty statement (empty block or simply a semicolon)"
}, AST_Statement);

var AST_StatementWithBody = DEFNODE("StatementWithBody", "body", {
    $documentation: "Base class for all statements that contain one nested body: `For`, `ForIn`, `Do`, `While`, `With`",
    $propdoc: {
        body: "[AST_Statement] the body; this should always be present, even if it's an AST_EmptyStatement"
    },
    _validate: function() {
        if (!(this.body instanceof AST_Statement)) throw new Error("body must be AST_Statement");
        if (this.body instanceof AST_Function) throw new Error("body cannot be AST_Function");
    },
}, AST_Statement);

var AST_LabeledStatement = DEFNODE("LabeledStatement", "label", {
    $documentation: "Statement with a label",
    $propdoc: {
        label: "[AST_Label] a label definition"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.label.walk(visitor);
            node.body.walk(visitor);
        });
    },
    clone: function(deep) {
        var node = this._clone(deep);
        if (deep) {
            var label = node.label;
            var def = this.label;
            node.walk(new TreeWalker(function(node) {
                if (node instanceof AST_LoopControl) {
                    if (!node.label || node.label.thedef !== def) return;
                    node.label.thedef = label;
                    label.references.push(node);
                    return true;
                }
                if (node instanceof AST_Scope) return true;
            }));
        }
        return node;
    },
    _validate: function() {
        if (!(this.label instanceof AST_Label)) throw new Error("label must be AST_Label");
    },
}, AST_StatementWithBody);

var AST_IterationStatement = DEFNODE("IterationStatement", null, {
    $documentation: "Internal class.  All loops inherit from it."
}, AST_StatementWithBody);

var AST_DWLoop = DEFNODE("DWLoop", "condition", {
    $documentation: "Base class for do/while statements",
    $propdoc: {
        condition: "[AST_Node] the loop condition.  Should not be instanceof AST_Statement"
    },
    _validate: function() {
        must_be_expression(this, "condition");
    },
}, AST_IterationStatement);

var AST_Do = DEFNODE("Do", null, {
    $documentation: "A `do` statement",
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.body.walk(visitor);
            node.condition.walk(visitor);
        });
    }
}, AST_DWLoop);

var AST_While = DEFNODE("While", null, {
    $documentation: "A `while` statement",
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.condition.walk(visitor);
            node.body.walk(visitor);
        });
    }
}, AST_DWLoop);

var AST_For = DEFNODE("For", "init condition step", {
    $documentation: "A `for` statement",
    $propdoc: {
        init: "[AST_Node?] the `for` initialization code, or null if empty",
        condition: "[AST_Node?] the `for` termination clause, or null if empty",
        step: "[AST_Node?] the `for` update clause, or null if empty"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            if (node.init) node.init.walk(visitor);
            if (node.condition) node.condition.walk(visitor);
            if (node.step) node.step.walk(visitor);
            node.body.walk(visitor);
        });
    },
    _validate: function() {
        if (this.init != null) {
            if (!(this.init instanceof AST_Node)) throw new Error("init must be AST_Node");
            if (this.init instanceof AST_Statement
                && !(this.init instanceof AST_Definitions || this.init instanceof AST_Function)) {
                throw new Error("init cannot be AST_Statement");
            }
        }
        if (this.condition != null) must_be_expression(this, "condition");
        if (this.step != null) must_be_expression(this, "step");
    },
}, AST_IterationStatement);

var AST_ForIn = DEFNODE("ForIn", "init object", {
    $documentation: "A `for ... in` statement",
    $propdoc: {
        init: "[AST_Node] the `for/in` initialization code",
        object: "[AST_Node] the object that we're looping through"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.init.walk(visitor);
            node.object.walk(visitor);
            node.body.walk(visitor);
        });
    },
    _validate: function() {
        if (this.init instanceof AST_Definitions) {
            if (this.init.definitions.length != 1) throw new Error("init must have single declaration");
        } else if (!(this.init instanceof AST_PropAccess || this.init instanceof AST_SymbolRef)) {
            throw new Error("init must be assignable");
        }
        must_be_expression(this, "object");
    },
}, AST_IterationStatement);

var AST_With = DEFNODE("With", "expression", {
    $documentation: "A `with` statement",
    $propdoc: {
        expression: "[AST_Node] the `with` expression"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.expression.walk(visitor);
            node.body.walk(visitor);
        });
    },
    _validate: function() {
        must_be_expression(this, "expression");
    },
}, AST_StatementWithBody);

/* -----[ scope and functions ]----- */

var AST_Scope = DEFNODE("Scope", "cname enclosed uses_eval uses_with parent_scope functions variables make_def", {
    $documentation: "Base class for all statements introducing a lexical scope",
    $propdoc: {
        cname: "[integer/S] current index for mangling variables (used internally by the mangler)",
        enclosed: "[SymbolDef*/S] a list of all symbol definitions that are accessed from this scope or any subscopes",
        uses_eval: "[boolean/S] tells whether this scope contains a direct call to the global `eval`",
        uses_with: "[boolean/S] tells whether this scope uses the `with` statement",
        parent_scope: "[AST_Scope?/S] link to the parent scope",
        functions: "[Object/S] like `variables`, but only lists function declarations",
        variables: "[Object/S] a map of name -> SymbolDef for all variables/functions defined in this scope",
    },
    clone: function(deep) {
        var node = this._clone(deep);
        if (this.variables) node.variables = this.variables.clone();
        if (this.functions) node.functions = this.functions.clone();
        if (this.enclosed) node.enclosed = this.enclosed.slice();
        return node;
    },
    pinned: function() {
        return this.uses_eval || this.uses_with;
    },
    _validate: function() {
        if (this.parent_scope != null) {
            if (!(this.parent_scope instanceof AST_Scope)) throw new Error("parent_scope must be AST_Scope");
        }
    },
}, AST_Block);

var AST_Toplevel = DEFNODE("Toplevel", "globals", {
    $documentation: "The toplevel scope",
    $propdoc: {
        globals: "[Object/S] a map of name -> SymbolDef for all undeclared names",
    },
    wrap: function(name) {
        var body = this.body;
        return parse([
            "(function(exports){'$ORIG';})(typeof ",
            name,
            "=='undefined'?(",
            name,
            "={}):",
            name,
            ");"
        ].join(""), {
            filename: "wrap=" + JSON.stringify(name)
        }).transform(new TreeTransformer(function(node) {
            if (node instanceof AST_Directive && node.value == "$ORIG") {
                return List.splice(body);
            }
        }));
    },
    enclose: function(args_values) {
        if (typeof args_values != "string") args_values = "";
        var index = args_values.indexOf(":");
        if (index < 0) index = args_values.length;
        var body = this.body;
        return parse([
            "(function(",
            args_values.slice(0, index),
            '){"$ORIG"})(',
            args_values.slice(index + 1),
            ")"
        ].join(""), {
            filename: "enclose=" + JSON.stringify(args_values)
        }).transform(new TreeTransformer(function(node) {
            if (node instanceof AST_Directive && node.value == "$ORIG") {
                return List.splice(body);
            }
        }));
    }
}, AST_Scope);

var AST_Lambda = DEFNODE("Lambda", "name argnames uses_arguments length_read", {
    $documentation: "Base class for functions",
    $propdoc: {
        name: "[AST_SymbolDeclaration?] the name of this function",
        argnames: "[AST_SymbolFunarg*] array of function arguments",
        uses_arguments: "[boolean/S] tells whether this function accesses the arguments array"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            if (node.name) node.name.walk(visitor);
            node.argnames.forEach(function(argname) {
                argname.walk(visitor);
            });
            walk_body(node, visitor);
        });
    },
    _validate: function() {
        this.argnames.forEach(function(node) {
            if (!(node instanceof AST_SymbolFunarg)) throw new Error("argnames must be AST_SymbolFunarg[]");
        });
    },
}, AST_Scope);

var AST_Accessor = DEFNODE("Accessor", null, {
    $documentation: "A setter/getter function.  The `name` property is always null.",
    _validate: function() {
        if (this.name != null) throw new Error("name must be null");
    },
}, AST_Lambda);

var AST_Function = DEFNODE("Function", "inlined", {
    $documentation: "A function expression",
    _validate: function() {
        if (this.name != null) {
            if (!(this.name instanceof AST_SymbolLambda)) throw new Error("name must be AST_SymbolLambda");
        }
    },
}, AST_Lambda);

var AST_Defun = DEFNODE("Defun", "inlined", {
    $documentation: "A function definition",
    _validate: function() {
        if (!(this.name instanceof AST_SymbolDefun)) throw new Error("name must be AST_SymbolDefun");
    },
}, AST_Lambda);

/* -----[ JUMPS ]----- */

var AST_Jump = DEFNODE("Jump", null, {
    $documentation: "Base class for “jumps” (for now that's `return`, `throw`, `break` and `continue`)"
}, AST_Statement);

var AST_Exit = DEFNODE("Exit", "value", {
    $documentation: "Base class for “exits” (`return` and `throw`)",
    $propdoc: {
        value: "[AST_Node?] the value returned or thrown by this statement; could be null for AST_Return"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            if (node.value) node.value.walk(visitor);
        });
    }
}, AST_Jump);

var AST_Return = DEFNODE("Return", null, {
    $documentation: "A `return` statement",
    _validate: function() {
        if (this.value != null) must_be_expression(this, "value");
    },
}, AST_Exit);

var AST_Throw = DEFNODE("Throw", null, {
    $documentation: "A `throw` statement",
    _validate: function() {
        must_be_expression(this, "value");
    },
}, AST_Exit);

var AST_LoopControl = DEFNODE("LoopControl", "label", {
    $documentation: "Base class for loop control statements (`break` and `continue`)",
    $propdoc: {
        label: "[AST_LabelRef?] the label, or null if none",
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            if (node.label) node.label.walk(visitor);
        });
    },
    _validate: function() {
        if (this.label != null) {
            if (!(this.label instanceof AST_LabelRef)) throw new Error("label must be AST_LabelRef");
        }
    },
}, AST_Jump);

var AST_Break = DEFNODE("Break", null, {
    $documentation: "A `break` statement"
}, AST_LoopControl);

var AST_Continue = DEFNODE("Continue", null, {
    $documentation: "A `continue` statement"
}, AST_LoopControl);

/* -----[ IF ]----- */

var AST_If = DEFNODE("If", "condition alternative", {
    $documentation: "A `if` statement",
    $propdoc: {
        condition: "[AST_Node] the `if` condition",
        alternative: "[AST_Statement?] the `else` part, or null if not present"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.condition.walk(visitor);
            node.body.walk(visitor);
            if (node.alternative) node.alternative.walk(visitor);
        });
    },
    _validate: function() {
        must_be_expression(this, "condition");
        if (this.alternative != null) {
            if (!(this.alternative instanceof AST_Statement)) throw new Error("alternative must be AST_Statement");
            if (this.alternative instanceof AST_Function) throw new error("alternative cannot be AST_Function");
        }
    },
}, AST_StatementWithBody);

/* -----[ SWITCH ]----- */

var AST_Switch = DEFNODE("Switch", "expression", {
    $documentation: "A `switch` statement",
    $propdoc: {
        expression: "[AST_Node] the `switch` “discriminant”"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.expression.walk(visitor);
            walk_body(node, visitor);
        });
    },
    _validate: function() {
        must_be_expression(this, "expression");
        this.body.forEach(function(node) {
            if (!(node instanceof AST_SwitchBranch)) throw new Error("body must be AST_SwitchBranch[]");
        });
    },
}, AST_Block);

var AST_SwitchBranch = DEFNODE("SwitchBranch", null, {
    $documentation: "Base class for `switch` branches",
}, AST_Block);

var AST_Default = DEFNODE("Default", null, {
    $documentation: "A `default` switch branch",
}, AST_SwitchBranch);

var AST_Case = DEFNODE("Case", "expression", {
    $documentation: "A `case` switch branch",
    $propdoc: {
        expression: "[AST_Node] the `case` expression"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.expression.walk(visitor);
            walk_body(node, visitor);
        });
    },
    _validate: function() {
        must_be_expression(this, "expression");
    },
}, AST_SwitchBranch);

/* -----[ EXCEPTIONS ]----- */

var AST_Try = DEFNODE("Try", "bcatch bfinally", {
    $documentation: "A `try` statement",
    $propdoc: {
        bcatch: "[AST_Catch?] the catch block, or null if not present",
        bfinally: "[AST_Finally?] the finally block, or null if not present"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            walk_body(node, visitor);
            if (node.bcatch) node.bcatch.walk(visitor);
            if (node.bfinally) node.bfinally.walk(visitor);
        });
    },
    _validate: function() {
        if (this.bcatch != null) {
            if (!(this.bcatch instanceof AST_Catch)) throw new Error("bcatch must be AST_Catch");
        }
        if (this.bfinally != null) {
            if (!(this.bfinally instanceof AST_Finally)) throw new Error("bfinally must be AST_Finally");
        }
    },
}, AST_Block);

var AST_Catch = DEFNODE("Catch", "argname", {
    $documentation: "A `catch` node; only makes sense as part of a `try` statement",
    $propdoc: {
        argname: "[AST_SymbolCatch] symbol for the exception"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.argname.walk(visitor);
            walk_body(node, visitor);
        });
    },
    _validate: function() {
        if (!(this.argname instanceof AST_SymbolCatch)) throw new Error("argname must be AST_SymbolCatch");
    },
}, AST_Block);

var AST_Finally = DEFNODE("Finally", null, {
    $documentation: "A `finally` node; only makes sense as part of a `try` statement"
}, AST_Block);

/* -----[ VAR ]----- */

var AST_Definitions = DEFNODE("Definitions", "definitions", {
    $documentation: "Base class for `var` nodes (variable declarations/initializations)",
    $propdoc: {
        definitions: "[AST_VarDef*] array of variable definitions"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.definitions.forEach(function(defn) {
                defn.walk(visitor);
            });
        });
    }
}, AST_Statement);

var AST_Var = DEFNODE("Var", null, {
    $documentation: "A `var` statement",
    _validate: function() {
        this.definitions.forEach(function(node) {
            if (!(node instanceof AST_VarDef)) throw new Error("definitions must be AST_VarDef[]");
        });
    },
}, AST_Definitions);

var AST_VarDef = DEFNODE("VarDef", "name value", {
    $documentation: "A variable declaration; only appears in a AST_Definitions node",
    $propdoc: {
        name: "[AST_SymbolVar] name of the variable",
        value: "[AST_Node?] initializer, or null of there's no initializer"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.name.walk(visitor);
            if (node.value) node.value.walk(visitor);
        });
    },
    _validate: function() {
        if (!(this.name instanceof AST_SymbolVar)) throw new Error("name must be AST_SymbolVar");
        if (this.value != null) must_be_expression(this, "value");
    },
});

/* -----[ OTHER ]----- */

function must_be_expressions(node, prop) {
    node[prop].forEach(function(node) {
        if (!(node instanceof AST_Node)) throw new Error(prop + " must be AST_Node[]");
        if (node instanceof AST_Statement && !(node instanceof AST_Function)) {
            throw new Error(prop + " cannot contain AST_Statement");
        }
    });
}

var AST_Call = DEFNODE("Call", "expression args pure", {
    $documentation: "A function call expression",
    $propdoc: {
        expression: "[AST_Node] expression to invoke as function",
        args: "[AST_Node*] array of arguments"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.expression.walk(visitor);
            node.args.forEach(function(arg) {
                arg.walk(visitor);
            });
        });
    },
    _validate: function() {
        must_be_expression(this, "expression");
        must_be_expressions(this, "args");
    },
});

var AST_New = DEFNODE("New", null, {
    $documentation: "An object instantiation.  Derives from a function call since it has exactly the same properties"
}, AST_Call);

var AST_Sequence = DEFNODE("Sequence", "expressions", {
    $documentation: "A sequence expression (comma-separated expressions)",
    $propdoc: {
        expressions: "[AST_Node*] array of expressions (at least two)"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.expressions.forEach(function(expr) {
                expr.walk(visitor);
            });
        });
    },
    _validate: function() {
        if (this.expressions.length < 2) throw new Error("expressions must contain multiple elements");
        must_be_expressions(this, "expressions");
    },
});

var AST_PropAccess = DEFNODE("PropAccess", "expression property", {
    $documentation: "Base class for property access expressions, i.e. `a.foo` or `a[\"foo\"]`",
    $propdoc: {
        expression: "[AST_Node] the “container” expression",
        property: "[AST_Node|string] the property to access.  For AST_Dot this is always a plain string, while for AST_Sub it's an arbitrary AST_Node"
    },
    getProperty: function() {
        var p = this.property;
        if (p instanceof AST_Constant) {
            return p.value;
        }
        if (p instanceof AST_UnaryPrefix
            && p.operator == "void"
            && p.expression instanceof AST_Constant) {
            return;
        }
        return p;
    },
    _validate: function() {
        must_be_expression(this, "expression");
    },
});

var AST_Dot = DEFNODE("Dot", null, {
    $documentation: "A dotted property access expression",
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.expression.walk(visitor);
        });
    },
    _validate: function() {
        if (typeof this.property != "string") throw new Error("property must be string");
    },
}, AST_PropAccess);

var AST_Sub = DEFNODE("Sub", null, {
    $documentation: "Index-style property access, i.e. `a[\"foo\"]`",
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.expression.walk(visitor);
            node.property.walk(visitor);
        });
    },
    _validate: function() {
        must_be_expression(this, "property");
    },
}, AST_PropAccess);

var AST_Unary = DEFNODE("Unary", "operator expression", {
    $documentation: "Base class for unary expressions",
    $propdoc: {
        operator: "[string] the operator",
        expression: "[AST_Node] expression that this unary operator applies to"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.expression.walk(visitor);
        });
    },
    _validate: function() {
        if (typeof this.operator != "string") throw new Error("operator must be string");
        must_be_expression(this, "expression");
    },
});

var AST_UnaryPrefix = DEFNODE("UnaryPrefix", null, {
    $documentation: "Unary prefix expression, i.e. `typeof i` or `++i`"
}, AST_Unary);

var AST_UnaryPostfix = DEFNODE("UnaryPostfix", null, {
    $documentation: "Unary postfix expression, i.e. `i++`"
}, AST_Unary);

var AST_Binary = DEFNODE("Binary", "operator left right", {
    $documentation: "Binary expression, i.e. `a + b`",
    $propdoc: {
        left: "[AST_Node] left-hand side expression",
        operator: "[string] the operator",
        right: "[AST_Node] right-hand side expression"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.left.walk(visitor);
            node.right.walk(visitor);
        });
    },
    _validate: function() {
        must_be_expression(this, "left");
        if (typeof this.operator != "string") throw new Error("operator must be string");
        must_be_expression(this, "right");
    },
});

var AST_Conditional = DEFNODE("Conditional", "condition consequent alternative", {
    $documentation: "Conditional expression using the ternary operator, i.e. `a ? b : c`",
    $propdoc: {
        condition: "[AST_Node]",
        consequent: "[AST_Node]",
        alternative: "[AST_Node]"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.condition.walk(visitor);
            node.consequent.walk(visitor);
            node.alternative.walk(visitor);
        });
    },
    _validate: function() {
        must_be_expression(this, "condition");
        must_be_expression(this, "consequent");
        must_be_expression(this, "alternative");
    },
});

var AST_Assign = DEFNODE("Assign", null, {
    $documentation: "An assignment expression — `a = b + 5`",
    _validate: function() {
        if (this.operator.indexOf("=") < 0) throw new Error('operator must contain "="');
    },
}, AST_Binary);

/* -----[ LITERALS ]----- */

var AST_Array = DEFNODE("Array", "elements", {
    $documentation: "An array literal",
    $propdoc: {
        elements: "[AST_Node*] array of elements"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.elements.forEach(function(element) {
                element.walk(visitor);
            });
        });
    },
    _validate: function() {
        must_be_expressions(this, "elements");
    },
});

var AST_Object = DEFNODE("Object", "properties", {
    $documentation: "An object literal",
    $propdoc: {
        properties: "[AST_ObjectProperty*] array of properties"
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.properties.forEach(function(prop) {
                prop.walk(visitor);
            });
        });
    },
    _validate: function() {
        this.properties.forEach(function(node) {
            if (!(node instanceof AST_ObjectProperty)) throw new Error("properties must be AST_ObjectProperty[]");
        });
    },
});

var AST_ObjectProperty = DEFNODE("ObjectProperty", "key value", {
    $documentation: "Base class for literal object properties",
    $propdoc: {
        key: "[string|AST_SymbolAccessor] property name. For ObjectKeyVal this is a string. For getters and setters this is an AST_SymbolAccessor.",
        value: "[AST_Node] property value.  For getters and setters this is an AST_Accessor."
    },
    walk: function(visitor) {
        var node = this;
        visitor.visit(node, function() {
            node.value.walk(visitor);
        });
    }
});

var AST_ObjectKeyVal = DEFNODE("ObjectKeyVal", "quote", {
    $documentation: "A key: value object property",
    $propdoc: {
        quote: "[string] the original quote character"
    },
    _validate: function() {
        if (typeof this.key != "string") throw new Error("key must be string");
        must_be_expression(this, "value");
    },
}, AST_ObjectProperty);

var AST_ObjectSetter = DEFNODE("ObjectSetter", null, {
    $documentation: "An object setter property",
    _validate: function() {
        if (!(this.key instanceof AST_SymbolAccessor)) throw new Error("key must be AST_SymbolAccessor");
        if (!(this.value instanceof AST_Accessor)) throw new Error("value must be AST_Accessor");
    },
}, AST_ObjectProperty);

var AST_ObjectGetter = DEFNODE("ObjectGetter", null, {
    $documentation: "An object getter property",
    _validate: function() {
        if (!(this.key instanceof AST_SymbolAccessor)) throw new Error("key must be AST_SymbolAccessor");
        if (!(this.value instanceof AST_Accessor)) throw new Error("value must be AST_Accessor");
    },
}, AST_ObjectProperty);

var AST_Symbol = DEFNODE("Symbol", "scope name thedef", {
    $propdoc: {
        name: "[string] name of this symbol",
        scope: "[AST_Scope/S] the current scope (not necessarily the definition scope)",
        thedef: "[SymbolDef/S] the definition of this symbol"
    },
    $documentation: "Base class for all symbols",
    _validate: function() {
        if (typeof this.name != "string") throw new Error("name must be string");
    },
});

var AST_SymbolAccessor = DEFNODE("SymbolAccessor", null, {
    $documentation: "The name of a property accessor (setter/getter function)"
}, AST_Symbol);

var AST_SymbolDeclaration = DEFNODE("SymbolDeclaration", "init", {
    $documentation: "A declaration symbol (symbol in var, function name or argument, symbol in catch)",
}, AST_Symbol);

var AST_SymbolVar = DEFNODE("SymbolVar", null, {
    $documentation: "Symbol defining a variable",
}, AST_SymbolDeclaration);

var AST_SymbolFunarg = DEFNODE("SymbolFunarg", null, {
    $documentation: "Symbol naming a function argument",
}, AST_SymbolVar);

var AST_SymbolDefun = DEFNODE("SymbolDefun", null, {
    $documentation: "Symbol defining a function",
}, AST_SymbolDeclaration);

var AST_SymbolLambda = DEFNODE("SymbolLambda", null, {
    $documentation: "Symbol naming a function expression",
}, AST_SymbolDeclaration);

var AST_SymbolCatch = DEFNODE("SymbolCatch", null, {
    $documentation: "Symbol naming the exception in catch",
}, AST_SymbolDeclaration);

var AST_Label = DEFNODE("Label", "references", {
    $documentation: "Symbol naming a label (declaration)",
    $propdoc: {
        references: "[AST_LoopControl*] a list of nodes referring to this label"
    },
    initialize: function() {
        this.references = [];
        this.thedef = this;
    }
}, AST_Symbol);

var AST_SymbolRef = DEFNODE("SymbolRef", "fixed", {
    $documentation: "Reference to some symbol (not definition/declaration)",
}, AST_Symbol);

var AST_LabelRef = DEFNODE("LabelRef", null, {
    $documentation: "Reference to a label symbol",
}, AST_Symbol);

var AST_This = DEFNODE("This", null, {
    $documentation: "The `this` symbol",
    _validate: function() {
        if (this.name !== "this") throw new Error('name must be "this"');
    },
}, AST_Symbol);

var AST_Constant = DEFNODE("Constant", null, {
    $documentation: "Base class for all constants",
});

var AST_String = DEFNODE("String", "value quote", {
    $documentation: "A string literal",
    $propdoc: {
        value: "[string] the contents of this string",
        quote: "[string] the original quote character"
    },
    _validate: function() {
        if (typeof this.value != "string") throw new Error("value must be string");
    },
}, AST_Constant);

var AST_Number = DEFNODE("Number", "value", {
    $documentation: "A number literal",
    $propdoc: {
        value: "[number] the numeric value",
    },
    _validate: function() {
        if (typeof this.value != "number") throw new Error("value must be number");
    },
}, AST_Constant);

var AST_RegExp = DEFNODE("RegExp", "value", {
    $documentation: "A regexp literal",
    $propdoc: {
        value: "[RegExp] the actual regexp"
    },
    _validate: function() {
        if (!(this.value instanceof RegExp)) throw new Error("value must be RegExp");
    },
}, AST_Constant);

var AST_Atom = DEFNODE("Atom", null, {
    $documentation: "Base class for atoms",
}, AST_Constant);

var AST_Null = DEFNODE("Null", null, {
    $documentation: "The `null` atom",
    value: null
}, AST_Atom);

var AST_NaN = DEFNODE("NaN", null, {
    $documentation: "The impossible value",
    value: 0/0
}, AST_Atom);

var AST_Undefined = DEFNODE("Undefined", null, {
    $documentation: "The `undefined` value",
    value: function(){}()
}, AST_Atom);

var AST_Hole = DEFNODE("Hole", null, {
    $documentation: "A hole in an array",
    value: function(){}()
}, AST_Atom);

var AST_Infinity = DEFNODE("Infinity", null, {
    $documentation: "The `Infinity` value",
    value: 1/0
}, AST_Atom);

var AST_Boolean = DEFNODE("Boolean", null, {
    $documentation: "Base class for booleans",
}, AST_Atom);

var AST_False = DEFNODE("False", null, {
    $documentation: "The `false` atom",
    value: false
}, AST_Boolean);

var AST_True = DEFNODE("True", null, {
    $documentation: "The `true` atom",
    value: true
}, AST_Boolean);

/* -----[ TreeWalker ]----- */

function TreeWalker(callback) {
    this.callback = callback;
    this.directives = Object.create(null);
    this.stack = [];
}
TreeWalker.prototype = {
    visit: function(node, descend) {
        this.push(node);
        var done = this.callback(node, descend || noop);
        if (!done && descend) descend();
        this.pop();
    },
    parent: function(n) {
        return this.stack[this.stack.length - 2 - (n || 0)];
    },
    push: function(node) {
        if (node instanceof AST_Lambda) {
            this.directives = Object.create(this.directives);
        } else if (node instanceof AST_Directive && !this.directives[node.value]) {
            this.directives[node.value] = node;
        }
        this.stack.push(node);
    },
    pop: function() {
        if (this.stack.pop() instanceof AST_Lambda) {
            this.directives = Object.getPrototypeOf(this.directives);
        }
    },
    self: function() {
        return this.stack[this.stack.length - 1];
    },
    find_parent: function(type) {
        var stack = this.stack;
        for (var i = stack.length; --i >= 0;) {
            var x = stack[i];
            if (x instanceof type) return x;
        }
    },
    has_directive: function(type) {
        var dir = this.directives[type];
        if (dir) return dir;
        var node = this.stack[this.stack.length - 1];
        if (node instanceof AST_Scope) {
            for (var i = 0; i < node.body.length; ++i) {
                var st = node.body[i];
                if (!(st instanceof AST_Directive)) break;
                if (st.value == type) return st;
            }
        }
    },
    loopcontrol_target: function(node) {
        var stack = this.stack;
        if (node.label) for (var i = stack.length; --i >= 0;) {
            var x = stack[i];
            if (x instanceof AST_LabeledStatement && x.label.name == node.label.name)
                return x.body;
        } else for (var i = stack.length; --i >= 0;) {
            var x = stack[i];
            if (x instanceof AST_IterationStatement
                || node instanceof AST_Break && x instanceof AST_Switch)
                return x;
        }
    },
    in_boolean_context: function() {
        var self = this.self();
        for (var i = 0, p; p = this.parent(i); i++) {
            if (p instanceof AST_Conditional && p.condition === self
                || p instanceof AST_DWLoop && p.condition === self
                || p instanceof AST_For && p.condition === self
                || p instanceof AST_If && p.condition === self
                || p instanceof AST_Return && p.in_bool
                || p instanceof AST_Sequence && p.tail_node() !== self
                || p instanceof AST_SimpleStatement
                || p instanceof AST_UnaryPrefix && p.operator == "!" && p.expression === self) {
                return true;
            }
            if (p instanceof AST_Binary && (p.operator == "&&" || p.operator == "||")
                || p instanceof AST_Conditional
                || p.tail_node() === self) {
                self = p;
            } else if (p instanceof AST_Return) {
                var fn;
                do {
                    fn = this.parent(++i);
                    if (!fn) return false;
                } while (!(fn instanceof AST_Lambda));
                if (fn.name) return false;
                self = this.parent(++i);
                if (!self || self.TYPE != "Call" || self.expression !== fn) return false;
            } else {
                return false;
            }
        }
    }
};