simple visitor API and code to figure out scope and references

5 files changed, 444 insertions, 90 deletions

diff --git a/lib/ast.js b/lib/ast.js
index 8ee58686..561cc4b9 100644
--- a/lib/ast.js
+++ b/lib/ast.js
@@ -8,12 +8,14 @@ function DEFNODE(type, props, methods, base) {
     for (var i = props.length; --i >= 0;) {
         code += "this." + props[i] + " = props." + props[i] + ";";
     }
-    if (methods && methods.initialize)
+    var proto = base && new base;
+    if (proto && proto.initialize || (methods && methods.initialize))
         code += "this.initialize();";
     code += " } }";
     var ctor = new Function(code)();
-    if (base) {
-        ctor.prototype = new base;
+    if (proto) {
+        ctor.prototype = proto;
+        ctor.BASE = base;
     }
     ctor.prototype.CTOR = ctor;
     ctor.PROPS = props || null;
@@ -30,45 +32,69 @@ function DEFNODE(type, props, methods, base) {
 };
 
 var AST_Token = DEFNODE("Token", "type value line col pos endpos nlb comments_before", {
-
 }, null);
 
 var AST_Node = DEFNODE("Node", "start end", {
-    clone: function() {
-        return new this.CTOR(this);
+    _walk: function(visitor) {
+        return visitor._visit(this);
+    },
+    walk: function(visitor) {
+        return this._walk(visitor); // not sure the indirection will be any help
     }
 }, null);
 
-var AST_Directive = DEFNODE("Directive", "value", {
-
-});
-
 var AST_Debugger = DEFNODE("Debugger", null, {
+});
 
+var AST_Directive = DEFNODE("Directive", "value", {
 });
 
 /* -----[ loops ]----- */
 
 var AST_LabeledStatement = DEFNODE("LabeledStatement", "label statement", {
-
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.label._walk(visitor);
+            this.statement._walk(visitor);
+        });
+    }
 });
 
 var AST_Statement = DEFNODE("Statement", "body", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.body._walk(visitor);
+        });
+    }
 });
 
 var AST_SimpleStatement = DEFNODE("SimpleStatement", null, {
-
 }, AST_Statement);
 
 var AST_BlockStatement = DEFNODE("BlockStatement", null, {
-
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            var a = this.body, i = 0, n = a.length;
+            while (i < n) {
+                a[i++]._walk(visitor);
+            }
+        });
+    }
 }, AST_Statement);
 
 var AST_EmptyStatement = DEFNODE("EmptyStatement", null, {
-
+    _walk: function(visitor) {
+        return visitor._visit(this);
+    }
 }, AST_Statement);
 
 var AST_DWLoop = DEFNODE("DWLoop", "condition", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.condition._walk(visitor);
+            this.body._walk(visitor);
+        });
+    }
 }, AST_Statement);
 
 var AST_Do = DEFNODE("Do", null, {
@@ -78,189 +104,376 @@ var AST_While = DEFNODE("While", null, {
 }, AST_DWLoop);
 
 var AST_For = DEFNODE("For", "init condition step", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            if (this.init) this.init._walk(visitor);
+            if (this.condition) this.condition._walk(visitor);
+            if (this.step) this.step._walk(visitor);
+        });
+    }
 }, AST_Statement);
 
 var AST_ForIn = DEFNODE("ForIn", "init name object", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            if (this.init) this.init._walk(visitor);
+            if (this.name) this.name._walk(visitor);
+            if (this.object) this.object._walk(visitor);
+        });
+    }
 }, AST_Statement);
 
 var AST_With = DEFNODE("With", "expression", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.expression._walk(visitor);
+            this.body._walk(visitor);
+        });
+    }
 }, AST_Statement);
 
-/* -----[ functions ]----- */
+/* -----[ scope and functions ]----- */
 
-var AST_Scope = DEFNODE("Scope", "identifiers", {
-}, AST_Statement);
+var AST_Scope = DEFNODE("Scope", null, {
+    initialize: function() {
+        this.labels = {};
+        this.variables = {};
+        this.functions = {};
+        this.uses_with = false;
+        this.uses_eval = false;
+        this.parent_scope = null;
+    }
+}, AST_BlockStatement);
 
 var AST_Toplevel = DEFNODE("Toplevel", null, {
-
 }, AST_Scope);
 
 var AST_Lambda = DEFNODE("Lambda", "name argnames", {
+    initialize: function() {
+        AST_Scope.prototype.initialize.call(this);
+        this.uses_arguments = false;
+    },
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            if (this.name) this.name._walk(visitor);
+            this.argnames.forEach(function(arg){
+                arg._walk(visitor);
+            });
+            this.body._walk(visitor);
+        });
+    }
 }, AST_Scope);
 
 var AST_Function = DEFNODE("Function", null, {
-
 }, AST_Lambda);
 
 var AST_Defun = DEFNODE("Defun", null, {
-
-}, AST_Function);
+}, AST_Lambda);
 
 /* -----[ JUMPS ]----- */
 
 var AST_Jump = DEFNODE("Jump", null, {
-
 });
 
 var AST_Exit = DEFNODE("Exit", "value", {
+    _walk: function(visitor) {
+        return visitor._visit(this, this.value && function(){
+            this.value._walk(visitor);
+        });
+    }
 }, AST_Jump);
 
 var AST_Return = DEFNODE("Return", null, {
-
 }, AST_Exit);
 
 var AST_Throw = DEFNODE("Throw", null, {
-
 }, AST_Exit);
 
 var AST_LoopControl = DEFNODE("LoopControl", "label", {
+    _walk: function(visitor) {
+        return visitor._visit(this, this.label && function(){
+            this.label._walk(visitor);
+        });
+    }
 }, AST_Jump);
 
 var AST_Break = DEFNODE("Break", null, {
-
 }, AST_LoopControl);
 
 var AST_Continue = DEFNODE("Continue", null, {
-
 }, AST_LoopControl);
 
 /* -----[ IF ]----- */
 
 var AST_If = DEFNODE("If", "condition consequent alternative", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.condition._walk(visitor);
+            this.consequent._walk(visitor);
+            if (this.alternative) this.alternative._walk(visitor);
+        });
+    }
 });
 
 /* -----[ SWITCH ]----- */
 
 var AST_Switch = DEFNODE("Switch", "expression", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.expression._walk(visitor);
+            this.body._walk(visitor);
+        });
+    }
 }, AST_Statement);
 
 var AST_SwitchBlock = DEFNODE("SwitchBlock", null, {
 }, AST_BlockStatement);
 
-var AST_SwitchBranch = DEFNODE("SwitchBranch", "body", {
-});
+var AST_SwitchBranch = DEFNODE("SwitchBranch", null, {
+}, AST_BlockStatement);
 
 var AST_Default = DEFNODE("Default", null, {
-
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            AST_BlockStatement.prototype._walk.call(this, visitor);
+        });
+    }
 }, AST_SwitchBranch);
 
 var AST_Case = DEFNODE("Case", "expression", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.expression._walk(visitor);
+            AST_BlockStatement.prototype._walk.call(this, visitor);
+        });
+    }
 }, AST_SwitchBranch);
 
 /* -----[ EXCEPTIONS ]----- */
 
 var AST_Try = DEFNODE("Try", "btry bcatch bfinally", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.btry._walk(visitor);
+            if (this.bcatch) this.bcatch._walk(visitor);
+            if (this.bfinally) this.bfinally._walk(visitor);
+        });
+    }
 });
 
-var AST_Catch = DEFNODE("Catch", "argname body", {
-});
+// XXX: this is wrong according to ECMA-262 (12.4).  the catch block
+// should introduce another scope, as the argname should be visible
+// only inside the catch block.  However, doing it this way because of
+// IE which simply introduces the name in the surrounding scope.  If
+// we ever want to fix this then AST_Catch should inherit from
+// AST_Scope.
+var AST_Catch = DEFNODE("Catch", "argname", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.argname._walk(visitor);
+            this.body._walk(visitor);
+        });
+    }
+}, AST_BlockStatement);
 
-var AST_Finally = DEFNODE("Finally", "body", {
-});
+var AST_Finally = DEFNODE("Finally", null, {
+}, AST_BlockStatement);
 
 /* -----[ VAR/CONST ]----- */
 
 var AST_Definitions = DEFNODE("Definitions", "definitions", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.definitions.forEach(function(def){
+                def._walk(visitor);
+            });
+        });
+    }
 });
 
 var AST_Var = DEFNODE("Var", null, {
-
 }, AST_Definitions);
 
 var AST_Const = DEFNODE("Const", null, {
-
 }, AST_Definitions);
 
 var AST_VarDef = DEFNODE("VarDef", "name value", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.name._walk(visitor);
+            if (this.value) this.value._walk(visitor);
+        });
+    }
 });
 
 /* -----[ OTHER ]----- */
 
 var AST_Call = DEFNODE("Call", "expression args", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.expression._walk(visitor);
+            this.args.forEach(function(arg){
+                arg._walk(visitor);
+            });
+        });
+    }
 });
 
 var AST_New = DEFNODE("New", null, {
-
 }, AST_Call);
 
 var AST_Seq = DEFNODE("Seq", "first second", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.first._walk(visitor);
+            this.second._walk(visitor);
+        });
+    }
 });
 
 var AST_PropAccess = DEFNODE("PropAccess", "expression property", {
-
 });
 
 var AST_Dot = DEFNODE("Dot", null, {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.expression._walk(visitor);
+        });
+    }
 }, AST_PropAccess);
 
 var AST_Sub = DEFNODE("Sub", null, {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.expression._walk(visitor);
+            this.property._walk(visitor);
+        });
+    }
 }, AST_PropAccess);
 
 var AST_Unary = DEFNODE("Unary", "operator expression", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.expression._walk(visitor);
+        });
+    }
 });
 
 var AST_UnaryPrefix = DEFNODE("UnaryPrefix", null, {
-
 }, AST_Unary);
 
 var AST_UnaryPostfix = DEFNODE("UnaryPostfix", null, {
-
 }, AST_Unary);
 
 var AST_Binary = DEFNODE("Binary", "left operator right", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.left._walk(visitor);
+            this.right._walk(visitor);
+        });
+    }
 });
 
 var AST_Conditional = DEFNODE("Conditional", "condition consequent alternative", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.condition._walk(visitor);
+            this.consequent._walk(visitor);
+            this.alternative._walk(visitor);
+        });
+    }
 });
 
 var AST_Assign = DEFNODE("Assign", "left operator right", {
-
 }, AST_Binary);
 
 /* -----[ LITERALS ]----- */
 
 var AST_Array = DEFNODE("Array", "elements", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.elements.forEach(function(el){
+                el._walk(visitor);
+            });
+        });
+    }
 });
 
 var AST_Object = DEFNODE("Object", "properties", {
+    _walk: function(visitor) {
+        return visitor._visit(this, function(){
+            this.properties.forEach(function(prop){
+                prop._walk(visitor);
+            });
+        });
+    }
 });
 
-var AST_ObjectProperty = DEFNODE("ObjectProperty");
+var AST_ObjectProperty = DEFNODE("ObjectProperty", "key value");
 
-var AST_ObjectKeyVal = DEFNODE("ObjectKeyval", "key value", {
+var AST_ObjectKeyVal = DEFNODE("ObjectKeyval", null, {
 }, AST_ObjectProperty);
 
-var AST_ObjectSetter = DEFNODE("ObjectSetter", "name func", {
+var AST_ObjectSetter = DEFNODE("ObjectSetter", null, {
 }, AST_ObjectProperty);
 
-var AST_ObjectGetter = DEFNODE("ObjectGetter", "name func", {
+var AST_ObjectGetter = DEFNODE("ObjectGetter", null, {
 }, AST_ObjectProperty);
 
-var AST_Symbol = DEFNODE("Symbol", "name", {
+var AST_Symbol = DEFNODE("Symbol", "scope name", {
 });
 
-var AST_This = DEFNODE("This", null, {
-
+var AST_SymbolDeclaration = DEFNODE("SymbolDeclaration", "references", {
+    initialize: function() {
+        this.references = [];
+    }
 }, AST_Symbol);
 
-var AST_SymbolRef = DEFNODE("SymbolRef", "scope symbol", {
+var AST_SymbolVar = DEFNODE("SymbolVar", null, {
+    $documentation: "Symbol defining a variable or constant"
+}, AST_SymbolDeclaration);
 
-}, AST_Symbol);
+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", null, {
+    $documentation: "Symbol naming a label (declaration)"
+}, AST_SymbolDeclaration);
+
+var AST_SymbolRef = DEFNODE("SymbolRef", "symbol", {
+    $documentation: "Reference to some symbol (not definition/declaration)",
+    reference: function(symbol) {
+        if (symbol) {
+            this.symbol = symbol;
+            symbol.references.push(this);
+            this.global = symbol.scope.parent_scope == null;
+        } else {
+            this.undeclared = true;
+            this.global = true;
+        }
+    }
+}, AST_Symbol);
 
+var AST_LabelRef = DEFNODE("LabelRef", null, {
+    $documentation: "Reference to a label symbol"
 }, AST_SymbolRef);
 
+var AST_This = DEFNODE("This", null, {
+}, AST_Symbol);
+
 var AST_Constant = DEFNODE("Constant", null, {
     getValue: function() {
         return this.value;
@@ -268,11 +481,9 @@ var AST_Constant = DEFNODE("Constant", null, {
 });
 
 var AST_String = DEFNODE("String", "value", {
-
 }, AST_Constant);
 
 var AST_Number = DEFNODE("Number", "value", {
-
 }, AST_Constant);
 
 var AST_RegExp = DEFNODE("Regexp", "pattern mods", {
@@ -282,7 +493,6 @@ var AST_RegExp = DEFNODE("Regexp", "pattern mods", {
 }, AST_Constant);
 
 var AST_Atom = DEFNODE("Atom", null, {
-
 }, AST_Constant);
 
 var AST_Null = DEFNODE("Null", null, {
@@ -300,3 +510,21 @@ var AST_False = DEFNODE("False", null, {
 var AST_True = DEFNODE("True", null, {
     value: true
 }, AST_Atom);
+
+/* -----[ TreeWalker ]----- */
+
+function TreeWalker(callback) {
+    this.visit = callback;
+    this.stack = [];
+};
+TreeWalker.prototype = {
+    _visit: function(node, descend) {
+        this.stack.push(node);
+        var ret = this.visit(node, descend);
+        if (!ret && descend) {
+            descend.call(node);
+        }
+        this.stack.pop(node);
+        return ret;
+    }
+};
diff --git a/lib/output.js b/lib/output.js
index 893ab05a..e14c649f 100644
--- a/lib/output.js
+++ b/lib/output.js
@@ -12,8 +12,6 @@ function OutputStream(options) {
         scope_style   : "negate"
     });
 
-    function noop() {};
-
     var indentation = 0;
     var current_col = 0;
     var current_line = 0;
@@ -254,7 +252,7 @@ function OutputStream(options) {
 
     // a function expression needs parens around it when it's provably
     // the first token to appear in a statement.
-    PARENS(AST_Lambda, function(output){
+    PARENS(AST_Function, function(output){
         return first_in_statement(output);
     });
 
@@ -264,11 +262,6 @@ function OutputStream(options) {
         return first_in_statement(output);
     });
 
-    // Defun inherits from Lambda, but we don't want parens here.
-    PARENS(AST_Defun, function(){
-        return false;
-    });
-
     PARENS(AST_Seq, function(output){
         var p = output.parent();
         return p instanceof AST_Call             // (foo, bar)() —or— foo(1, (2, 3), 4)
@@ -377,12 +370,11 @@ function OutputStream(options) {
     };
 
     DEFPRINT(AST_Statement, function(self, output){
-        if (self.body instanceof AST_Node) {
-            self.body.print(output);
-            output.semicolon();
-        } else {
-            display_body(self.body, self instanceof AST_Toplevel, output);
-        }
+        self.body.print(output);
+        output.semicolon();
+    });
+    DEFPRINT(AST_Toplevel, function(self, output){
+        display_body(self.body, true, output);
     });
     DEFPRINT(AST_LabeledStatement, function(self, output){
         self.label.print(output);
@@ -459,7 +451,9 @@ function OutputStream(options) {
             } else {
                 self.name.print(output);
             }
-            output.print(" in ");
+            output.space();
+            output.print("in");
+            output.space();
             self.object.print(output);
         });
         output.space();
@@ -800,12 +794,12 @@ function OutputStream(options) {
     DEFPRINT(AST_ObjectSetter, function(self, output){
         output.print("set");
         output.space();
-        self.func._do_print(output, true);
+        self.value._do_print(output, true);
     });
     DEFPRINT(AST_ObjectGetter, function(self, output){
         output.print("get");
         output.space();
-        self.func._do_print(output, true);
+        self.value._do_print(output, true);
     });
     DEFPRINT(AST_Symbol, function(self, output){
         output.print_name(self.name);
diff --git a/lib/parse.js b/lib/parse.js
index f5796b0f..78b8bb7c 100644
--- a/lib/parse.js
+++ b/lib/parse.js
@@ -836,7 +836,14 @@ function parse($TEXT, exigent_mode) {
     });
 
     function labeled_statement() {
-        var label = as_symbol(true);
+        var label = as_symbol(AST_Label);
+        if (find_if(function(l){ return l.name == label.name }, S.labels)) {
+            // ECMA-262, 12.12: An ECMAScript program is considered
+            // syntactically incorrect if it contains a
+            // LabelledStatement that is enclosed by a
+            // LabelledStatement with the same Identifier as label.
+            croak("Label " + label.name + " defined twice");
+        }
         expect(":");
         S.labels.push(label);
         var start = S.token, stat = statement();
@@ -849,16 +856,13 @@ function parse($TEXT, exigent_mode) {
     };
 
     function break_cont(type) {
-        var name = null, label = null;
+        var label = null;
         if (!can_insert_semicolon()) {
-            name = is("name") ? S.token.value : null;
+            label = as_symbol(AST_LabelRef, true);
         }
-        if (name != null) {
-            next();
-            label = find_if(function(l){ return l.name == name }, S.labels);
-            if (!label)
-                croak("Label " + name + " without matching loop or statement");
-            label = new AST_Label({ name: name, symbol: label });
+        if (label != null) {
+            if (!find_if(function(l){ return l.name == label.name }, S.labels))
+                croak("Undefined label " + label.name);
         }
         else if (S.in_loop == 0)
             croak(type.TYPE + " not inside a loop or switch");
@@ -910,7 +914,9 @@ function parse($TEXT, exigent_mode) {
     };
 
     var function_ = function(in_statement) {
-        var name = is("name") ? as_symbol(true) : null;
+        var name = is("name") ? as_symbol(in_statement
+                                          ? AST_SymbolDefun
+                                          : AST_SymbolLambda) : null;
         if (in_statement && !name)
             unexpected();
         expect("(");
@@ -920,7 +926,7 @@ function parse($TEXT, exigent_mode) {
             argnames: (function(first, a){
                 while (!is("punc", ")")) {
                     if (first) first = false; else expect(",");
-                    a.push(as_symbol(true));
+                    a.push(as_symbol(AST_SymbolFunarg));
                 }
                 next();
                 return a;
@@ -1010,7 +1016,7 @@ function parse($TEXT, exigent_mode) {
             var start = S.token;
             next();
             expect("(");
-            var name = as_symbol(true);
+            var name = as_symbol(AST_SymbolCatch);
             expect(")");
             bcatch = new AST_Catch({
                 start   : start,
@@ -1050,7 +1056,7 @@ function parse($TEXT, exigent_mode) {
         for (;;) {
             a.push(new AST_VarDef({
                 start : S.token,
-                name  : as_symbol(true),
+                name  : as_symbol(AST_SymbolVar),
                 value : is("operator", "=") ? (next(), expression(false, no_in)) : null,
                 end   : prev()
             }));
@@ -1099,7 +1105,7 @@ function parse($TEXT, exigent_mode) {
         var tok = S.token, ret;
         switch (tok.type) {
           case "name":
-            return as_symbol();
+            return as_symbol(AST_SymbolRef);
           case "num":
             ret = new AST_Number({ start: tok, end: tok, value: tok.value });
             break;
@@ -1198,8 +1204,8 @@ function parse($TEXT, exigent_mode) {
                 if (name == "get") {
                     a.push(new AST_ObjectGetter({
                         start : start,
-                        name  : name,
-                        func  : function_(false),
+                        key   : name,
+                        value : function_(false),
                         end   : prev()
                     }));
                     continue;
@@ -1207,8 +1213,8 @@ function parse($TEXT, exigent_mode) {
                 if (name == "set") {
                     a.push(new AST_ObjectSetter({
                         start : start,
-                        name  : name,
-                        func  : function_(false),
+                        key   : name,
+                        value : function_(false),
                         end   : prev()
                     }));
                     continue;
@@ -1252,10 +1258,13 @@ function parse($TEXT, exigent_mode) {
         }
     };
 
-    function as_symbol(def) {
-        if (!is("name")) croak("Name expected");
+    function as_symbol(type, noerror) {
+        if (!is("name")) {
+            if (!noerror) croak("Name expected");
+            return null;
+        }
         var name = S.token.value;
-        var sym = new (name == "this" ? AST_This : def ? AST_Symbol : AST_SymbolRef)({
+        var sym = new (name == "this" ? AST_This : type)({
             name  : String(S.token.value),
             start : S.token,
             end   : S.token
diff --git a/lib/scope.js b/lib/scope.js
new file mode 100644
index 00000000..f8bdb2e8
--- /dev/null
+++ b/lib/scope.js
@@ -0,0 +1,88 @@
+AST_Scope.DEFMETHOD("figure_out_scope", function(){
+    // step 1: handle definitions
+    var scope = null;
+    var tw = new TreeWalker(function(node, descend){
+        if (node instanceof AST_Scope) {
+            var save_scope = node.parent_scope = scope;
+            scope = node;
+            descend.call(node);
+            scope = save_scope;
+            return true;        // don't descend again in TreeWalker
+        }
+        if (node instanceof AST_With) {
+            for (var s = scope; s; s = s.parent_scope)
+                s.uses_with = true;
+            return;
+        }
+        if (node instanceof AST_SymbolDeclaration && !scope.parent_scope) {
+            node.global = true;
+        }
+        if (node instanceof AST_SymbolVar) {
+            scope.def_variable(node);
+        }
+        else if (node instanceof AST_SymbolLambda) {
+            scope.def_function(node);
+        }
+        else if (node instanceof AST_SymbolDefun) {
+            scope.parent_scope.def_function(node);
+        }
+        else if (node instanceof AST_Label) {
+            scope.def_label(node);
+        }
+        else if (node instanceof AST_SymbolCatch) {
+            // XXX: this is wrong according to ECMA-262 (12.4).  the
+            // `catch` argument name should be visible only inside the
+            // catch block.  For a quick fix AST_Catch should inherit
+            // from AST_Scope.
+            scope.def_variable(node);
+        }
+        else if (node instanceof AST_SymbolRef) {
+            node.scope = scope;
+        }
+    });
+    this.walk(tw);
+    // step 2: find back references and eval/with
+    var tw = new TreeWalker(function(node){
+        if (node instanceof AST_LabelRef) {
+            var sym = node.scope.find_label(node);
+            if (!sym) throw new Error("Undefined label " + node.name);
+            node.reference(sym);
+        }
+        else if (node instanceof AST_SymbolRef) {
+            var sym = node.scope.find_variable(node);
+            if (!sym) {
+                if (node.name == "eval") {
+                    for (var s = scope; s; s = s.parent_scope)
+                        s.uses_eval = true;
+                }
+            } else {
+                node.reference(sym);
+            }
+        }
+    });
+    this.walk(tw);
+});
+AST_Scope.DEFMETHOD("find_variable", function(name){
+    if (name instanceof AST_Symbol) name = name.name;
+    return this.variables[name] ||
+        (this.name && this.name.name == name && this.name) ||
+        (this.parent_scope && this.parent_scope.find_variable(name));
+});
+AST_Scope.DEFMETHOD("find_label", function(name){
+    if (name instanceof AST_Symbol) name = name.name;
+    return this.labels[name];
+});
+AST_Scope.DEFMETHOD("def_function", function(symbol){
+    this.def_variable(symbol);
+    this.functions[symbol.name] = symbol;
+    symbol.scope = this;
+});
+AST_Scope.DEFMETHOD("def_variable", function(symbol){
+    this.variables[symbol.name] = symbol;
+    delete this.functions[symbol.name];
+    symbol.scope = this;
+});
+AST_Scope.DEFMETHOD("def_label", function(symbol){
+    this.labels[symbol.name] = symbol;
+    symbol.scope = this;
+});
diff --git a/lib/utils.js b/lib/utils.js
index 4e4f58fc..c7d6932c 100644
--- a/lib/utils.js
+++ b/lib/utils.js
@@ -62,3 +62,38 @@ function defaults(args, defs) {
     }
     return ret;
 };
+
+function noop() {};
+
+var MAP = (function(){
+    function MAP(a, f, o) {
+        var ret = [], top = [], i;
+        function doit() {
+            var val = f.call(o, a[i], i);
+            if (val instanceof AtTop) {
+                val = val.v;
+                if (val instanceof Splice) {
+                    top.push.apply(top, val.v);
+                } else {
+                    top.push(val);
+                }
+            }
+            else if (val !== skip) {
+                if (val instanceof Splice) {
+                    ret.push.apply(ret, val.v);
+                } else {
+                    ret.push(val);
+                }
+            }
+        };
+        if (a instanceof Array) for (i = 0; i < a.length; ++i) doit();
+        else for (i in a) if (HOP(a, i)) doit();
+        return top.concat(ret);
+    };
+    MAP.at_top = function(val) { return new AtTop(val) };
+    MAP.splice = function(val) { return new Splice(val) };
+    var skip = MAP.skip = {};
+    function AtTop(val) { this.v = val };
+    function Splice(val) { this.v = val };
+    return MAP;
+})();