build/lib/process.js

   1 /***********************************************************************
   2
   3   A JavaScript tokenizer / parser / beautifier / compressor.
   4
   5   This version is suitable for Node.js.  With minimal changes (the
   6   exports stuff) it should work on any JS platform.
   7
   8   This file implements some AST processors.  They work on data built
   9   by parse-js.
  10
  11   Exported functions:
  12
  13     - ast_mangle(ast, include_toplevel) -- mangles the
  14       variable/function names in the AST.  Returns an AST.  Pass true
  15       as second argument to mangle toplevel names too.
  16
  17     - ast_squeeze(ast) -- employs various optimizations to make the
  18       final generated code even smaller.  Returns an AST.
  19
  20     - gen_code(ast, beautify) -- generates JS code from the AST.  Pass
  21       true (or an object, see the code for some options) as second
  22       argument to get "pretty" (indented) code.
  23
  24   -------------------------------- (C) ---------------------------------
  25
  26                            Author: Mihai Bazon
  27                          <mihai.bazon@gmail.com>
  28                        http://mihai.bazon.net/blog
  29
  30   Distributed under the BSD license:
  31
  32     Copyright 2010 (c) Mihai Bazon <mihai.bazon@gmail.com>
  33
  34     Redistribution and use in source and binary forms, with or without
  35     modification, are permitted provided that the following conditions
  36     are met:
  37
  38         * Redistributions of source code must retain the above
  39           copyright notice, this list of conditions and the following
  40           disclaimer.
  41
  42         * Redistributions in binary form must reproduce the above
  43           copyright notice, this list of conditions and the following
  44           disclaimer in the documentation and/or other materials
  45           provided with the distribution.
  46
  47     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER “AS IS” AND ANY
  48     EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  49     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  50     PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE
  51     LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
  52     OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  53     PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  54     PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  55     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
  56     TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
  57     THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  58     SUCH DAMAGE.
  59
  60  ***********************************************************************/
  61
  62 var jsp = require("./parse-js"),
  63     slice = jsp.slice,
  64     member = jsp.member,
  65     PRECEDENCE = jsp.PRECEDENCE,
  66     OPERATORS = jsp.OPERATORS;
  67
  68 /* -----[ helper for AST traversal ]----- */
  69
  70 function ast_walker(ast) {
  71         function _vardefs(defs) {
  72                 return MAP(defs, function(def){
  73                         var a = [ def[0] ];
  74                         if (def.length > 1)
  75                                 a[1] = walk(def[1]);
  76                         return a;
  77                 });
  78         };
  79         var walkers = {
  80                 "string": function(str) {
  81                         return [ "string", str ];
  82                 },
  83                 "num": function(num) {
  84                         return [ "num", num ];
  85                 },
  86                 "name": function(name) {
  87                         return [ "name", name ];
  88                 },
  89                 "toplevel": function(statements) {
  90                         return [ "toplevel", MAP(statements, walk) ];
  91                 },
  92                 "block": function(statements) {
  93                         var out = [ "block" ];
  94                         if (statements != null)
  95                                 out.push(MAP(statements, walk));
  96                         return out;
  97                 },
  98                 "var": function(defs) {
  99                         return [ "var", _vardefs(defs) ];
 100                 },
 101                 "const": function(defs) {
 102                         return [ "const", _vardefs(defs) ];
 103                 },
 104                 "try": function(t, c, f) {
 105                         return [
 106                                 "try",
 107                                 MAP(t, walk),
 108                                 c != null ? [ c[0], MAP(c[1], walk) ] : null,
 109                                 f != null ? MAP(f, walk) : null
 110                         ];
 111                 },
 112                 "throw": function(expr) {
 113                         return [ "throw", walk(expr) ];
 114                 },
 115                 "new": function(ctor, args) {
 116                         return [ "new", walk(ctor), MAP(args, walk) ];
 117                 },
 118                 "switch": function(expr, body) {
 119                         return [ "switch", walk(expr), MAP(body, function(branch){
 120                                 return [ branch[0] ? walk(branch[0]) : null,
 121                                          MAP(branch[1], walk) ];
 122                         }) ];
 123                 },
 124                 "break": function(label) {
 125                         return [ "break", label ];
 126                 },
 127                 "continue": function(label) {
 128                         return [ "continue", label ];
 129                 },
 130                 "conditional": function(cond, t, e) {
 131                         return [ "conditional", walk(cond), walk(t), walk(e) ];
 132                 },
 133                 "assign": function(op, lvalue, rvalue) {
 134                         return [ "assign", op, walk(lvalue), walk(rvalue) ];
 135                 },
 136                 "dot": function(expr) {
 137                         return [ "dot", walk(expr) ].concat(slice(arguments, 1));
 138                 },
 139                 "call": function(expr, args) {
 140                         return [ "call", walk(expr), MAP(args, walk) ];
 141                 },
 142                 "function": function(name, args, body) {
 143                         return [ "function", name, args.slice(), MAP(body, walk) ];
 144                 },
 145                 "defun": function(name, args, body) {
 146                         return [ "defun", name, args.slice(), MAP(body, walk) ];
 147                 },
 148                 "if": function(conditional, t, e) {
 149                         return [ "if", walk(conditional), walk(t), walk(e) ];
 150                 },
 151                 "for": function(init, cond, step, block) {
 152                         return [ "for", walk(init), walk(cond), walk(step), walk(block) ];
 153                 },
 154                 "for-in": function(has_var, key, hash, block) {
 155                         return [ "for-in", has_var, key, walk(hash), walk(block) ];
 156                 },
 157                 "while": function(cond, block) {
 158                         return [ "while", walk(cond), walk(block) ];
 159                 },
 160                 "do": function(cond, block) {
 161                         return [ "do", walk(cond), walk(block) ];
 162                 },
 163                 "return": function(expr) {
 164                         return [ "return", walk(expr) ];
 165                 },
 166                 "binary": function(op, left, right) {
 167                         return [ "binary", op, walk(left), walk(right) ];
 168                 },
 169                 "unary-prefix": function(op, expr) {
 170                         return [ "unary-prefix", op, walk(expr) ];
 171                 },
 172                 "unary-postfix": function(op, expr) {
 173                         return [ "unary-postfix", op, walk(expr) ];
 174                 },
 175                 "sub": function(expr, subscript) {
 176                         return [ "sub", walk(expr), walk(subscript) ];
 177                 },
 178                 "object": function(props) {
 179                         return [ "object", MAP(props, function(p){
 180                                 return p.length == 2
 181                                         ? [ p[0], walk(p[1]) ]
 182                                         : [ p[0], walk(p[1]), p[2] ]; // get/set-ter
 183                         }) ];
 184                 },
 185                 "regexp": function(rx, mods) {
 186                         return [ "regexp", rx, mods ];
 187                 },
 188                 "array": function(elements) {
 189                         return [ "array", MAP(elements, walk) ];
 190                 },
 191                 "stat": function(stat) {
 192                         return [ "stat", walk(stat) ];
 193                 },
 194                 "seq": function() {
 195                         return [ "seq" ].concat(MAP(slice(arguments), walk));
 196                 },
 197                 "label": function(name, block) {
 198                         return [ "label", name, walk(block) ];
 199                 },
 200                 "with": function(expr, block) {
 201                         return [ "with", walk(expr), walk(block) ];
 202                 },
 203                 "atom": function(name) {
 204                         return [ "atom", name ];
 205                 }
 206         };
 207
 208         var user = {};
 209         var stack = [];
 210         function walk(ast) {
 211                 if (ast == null)
 212                         return null;
 213                 try {
 214                         stack.push(ast);
 215                         var type = ast[0];
 216                         var gen = user[type];
 217                         if (gen) {
 218                                 var ret = gen.apply(ast, ast.slice(1));
 219                                 if (ret != null)
 220                                         return ret;
 221                         }
 222                         gen = walkers[type];
 223                         return gen.apply(ast, ast.slice(1));
 224                 } finally {
 225                         stack.pop();
 226                 }
 227         };
 228
 229         function with_walkers(walkers, cont){
 230                 var save = {}, i;
 231                 for (i in walkers) if (HOP(walkers, i)) {
 232                         save[i] = user[i];
 233                         user[i] = walkers[i];
 234                 }
 235                 var ret = cont();
 236                 for (i in save) if (HOP(save, i)) {
 237                         if (!save[i]) delete user[i];
 238                         else user[i] = save[i];
 239                 }
 240                 return ret;
 241         };
 242
 243         return {
 244                 walk: walk,
 245                 with_walkers: with_walkers,
 246                 parent: function() {
 247                         return stack[stack.length - 2]; // last one is current node
 248                 },
 249                 stack: function() {
 250                         return stack;
 251                 }
 252         };
 253 };
 254
 255 /* -----[ Scope and mangling ]----- */
 256
 257 function Scope(parent) {
 258         this.names = {};        // names defined in this scope
 259         this.mangled = {};      // mangled names (orig.name => mangled)
 260         this.rev_mangled = {};  // reverse lookup (mangled => orig.name)
 261         this.cname = -1;        // current mangled name
 262         this.refs = {};         // names referenced from this scope
 263         this.uses_with = false; // will become TRUE if eval() is detected in this or any subscopes
 264         this.uses_eval = false; // will become TRUE if with() is detected in this or any subscopes
 265         this.parent = parent;   // parent scope
 266         this.children = [];     // sub-scopes
 267         if (parent) {
 268                 this.level = parent.level + 1;
 269                 parent.children.push(this);
 270         } else {
 271                 this.level = 0;
 272         }
 273 };
 274
 275 var base54 = (function(){
 276         var DIGITS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$_";
 277         return function(num) {
 278                 var ret = "";
 279                 do {
 280                         ret = DIGITS.charAt(num % 54) + ret;
 281                         num = Math.floor(num / 54);
 282                 } while (num > 0);
 283                 return ret;
 284         };
 285 })();
 286
 287 Scope.prototype = {
 288         has: function(name) {
 289                 for (var s = this; s; s = s.parent)
 290                         if (HOP(s.names, name))
 291                                 return s;
 292         },
 293         has_mangled: function(mname) {
 294                 for (var s = this; s; s = s.parent)
 295                         if (HOP(s.rev_mangled, mname))
 296                                 return s;
 297         },
 298         toJSON: function() {
 299                 return {
 300                         names: this.names,
 301                         uses_eval: this.uses_eval,
 302                         uses_with: this.uses_with
 303                 };
 304         },
 305
 306         next_mangled: function() {
 307                 // we must be careful that the new mangled name:
 308                 //
 309                 // 1. doesn't shadow a mangled name from a parent
 310                 //    scope, unless we don't reference the original
 311                 //    name from this scope OR from any sub-scopes!
 312                 //    This will get slow.
 313                 //
 314                 // 2. doesn't shadow an original name from a parent
 315                 //    scope, in the event that the name is not mangled
 316                 //    in the parent scope and we reference that name
 317                 //    here OR IN ANY SUBSCOPES!
 318                 //
 319                 // 3. doesn't shadow a name that is referenced but not
 320                 //    defined (possibly global defined elsewhere).
 321                 for (;;) {
 322                         var m = base54(++this.cname), prior;
 323
 324                         // case 1.
 325                         prior = this.has_mangled(m);
 326                         if (prior && this.refs[prior.rev_mangled[m]] === prior)
 327                                 continue;
 328
 329                         // case 2.
 330                         prior = this.has(m);
 331                         if (prior && prior !== this && this.refs[m] === prior && !prior.has_mangled(m))
 332                                 continue;
 333
 334                         // case 3.
 335                         if (HOP(this.refs, m) && this.refs[m] == null)
 336                                 continue;
 337
 338                         // I got "do" once. :-/
 339                         if (!is_identifier(m))
 340                                 continue;
 341
 342                         return m;
 343                 }
 344         },
 345         get_mangled: function(name, newMangle) {
 346                 if (this.uses_eval || this.uses_with) return name; // no mangle if eval or with is in use
 347                 var s = this.has(name);
 348                 if (!s) return name; // not in visible scope, no mangle
 349                 if (HOP(s.mangled, name)) return s.mangled[name]; // already mangled in this scope
 350                 if (!newMangle) return name;                      // not found and no mangling requested
 351
 352                 var m = s.next_mangled();
 353                 s.rev_mangled[m] = name;
 354                 return s.mangled[name] = m;
 355         },
 356         define: function(name) {
 357                 if (name != null)
 358                         return this.names[name] = name;
 359         }
 360 };
 361
 362 function ast_add_scope(ast) {
 363
 364         var current_scope = null;
 365         var w = ast_walker(), walk = w.walk;
 366         var having_eval = [];
 367
 368         function with_new_scope(cont) {
 369                 current_scope = new Scope(current_scope);
 370                 var ret = current_scope.body = cont();
 371                 ret.scope = current_scope;
 372                 current_scope = current_scope.parent;
 373                 return ret;
 374         };
 375
 376         function define(name) {
 377                 return current_scope.define(name);
 378         };
 379
 380         function reference(name) {
 381                 current_scope.refs[name] = true;
 382         };
 383
 384         function _lambda(name, args, body) {
 385                 return [ this[0], define(name), args, with_new_scope(function(){
 386                         MAP(args, define);
 387                         return MAP(body, walk);
 388                 })];
 389         };
 390
 391         return with_new_scope(function(){
 392                 // process AST
 393                 var ret = w.with_walkers({
 394                         "function": _lambda,
 395                         "defun": _lambda,
 396                         "with": function(expr, block) {
 397                                 for (var s = current_scope; s; s = s.parent)
 398                                         s.uses_with = true;
 399                         },
 400                         "var": function(defs) {
 401                                 MAP(defs, function(d){ define(d[0]) });
 402                         },
 403                         "const": function(defs) {
 404                                 MAP(defs, function(d){ define(d[0]) });
 405                         },
 406                         "try": function(t, c, f) {
 407                                 if (c != null) return [
 408                                         "try",
 409                                         MAP(t, walk),
 410                                         [ define(c[0]), MAP(c[1], walk) ],
 411                                         f != null ? MAP(f, walk) : null
 412                                 ];
 413                         },
 414                         "name": function(name) {
 415                                 if (name == "eval")
 416                                         having_eval.push(current_scope);
 417                                 reference(name);
 418                         },
 419                         "for-in": function(has_var, name) {
 420                                 if (has_var) define(name);
 421                                 else reference(name);
 422                         }
 423                 }, function(){
 424                         return walk(ast);
 425                 });
 426
 427                 // the reason why we need an additional pass here is
 428                 // that names can be used prior to their definition.
 429
 430                 // scopes where eval was detected and their parents
 431                 // are marked with uses_eval, unless they define the
 432                 // "eval" name.
 433                 MAP(having_eval, function(scope){
 434                         if (!scope.has("eval")) while (scope) {
 435                                 scope.uses_eval = true;
 436                                 scope = scope.parent;
 437                         }
 438                 });
 439
 440                 // for referenced names it might be useful to know
 441                 // their origin scope.  current_scope here is the
 442                 // toplevel one.
 443                 function fixrefs(scope, i) {
 444                         // do children first; order shouldn't matter
 445                         for (i = scope.children.length; --i >= 0;)
 446                                 fixrefs(scope.children[i]);
 447                         for (i in scope.refs) if (HOP(scope.refs, i)) {
 448                                 // find origin scope and propagate the reference to origin
 449                                 for (var origin = scope.has(i), s = scope; s; s = s.parent) {
 450                                         s.refs[i] = origin;
 451                                         if (s === origin) break;
 452                                 }
 453                         }
 454                 };
 455                 fixrefs(current_scope);
 456
 457                 return ret;
 458         });
 459
 460 };
 461
 462 /* -----[ mangle names ]----- */
 463
 464 function ast_mangle(ast, do_toplevel) {
 465         var w = ast_walker(), walk = w.walk, scope;
 466
 467         function get_mangled(name, newMangle) {
 468                 if (!do_toplevel && !scope.parent) return name; // don't mangle toplevel
 469                 return scope.get_mangled(name, newMangle);
 470         };
 471
 472         function _lambda(name, args, body) {
 473                 if (name) name = get_mangled(name);
 474                 body = with_scope(body.scope, function(){
 475                         args = MAP(args, function(name){ return get_mangled(name) });
 476                         return MAP(body, walk);
 477                 });
 478                 return [ this[0], name, args, body ];
 479         };
 480
 481         function with_scope(s, cont) {
 482                 var _scope = scope;
 483                 scope = s;
 484                 for (var i in s.names) if (HOP(s.names, i)) {
 485                         get_mangled(i, true);
 486                 }
 487                 var ret = cont();
 488                 ret.scope = s;
 489                 scope = _scope;
 490                 return ret;
 491         };
 492
 493         function _vardefs(defs) {
 494                 return MAP(defs, function(d){
 495                         return [ get_mangled(d[0]), walk(d[1]) ];
 496                 });
 497         };
 498
 499         return w.with_walkers({
 500                 "function": _lambda,
 501                 "defun": function() {
 502                         // move function declarations to the top when
 503                         // they are not in some block.
 504                         var ast = _lambda.apply(this, arguments);
 505                         switch (w.parent()[0]) {
 506                             case "toplevel":
 507                             case "function":
 508                             case "defun":
 509                                 return MAP.at_top(ast);
 510                         }
 511                         return ast;
 512                 },
 513                 "var": function(defs) {
 514                         return [ "var", _vardefs(defs) ];
 515                 },
 516                 "const": function(defs) {
 517                         return [ "const", _vardefs(defs) ];
 518                 },
 519                 "name": function(name) {
 520                         return [ "name", get_mangled(name) ];
 521                 },
 522                 "try": function(t, c, f) {
 523                         return [ "try",
 524                                  MAP(t, walk),
 525                                  c != null ? [ get_mangled(c[0]), MAP(c[1], walk) ] : null,
 526                                  f != null ? MAP(f, walk) : null ];
 527                 },
 528                 "toplevel": function(body) {
 529                         return with_scope(this.scope, function(){
 530                                 return [ "toplevel", MAP(body, walk) ];
 531                         });
 532                 },
 533                 "for-in": function(has_var, name, obj, stat) {
 534                         return [ "for-in", has_var, get_mangled(name), walk(obj), walk(stat) ];
 535                 }
 536         }, function() {
 537                 return walk(ast_add_scope(ast));
 538         });
 539 };
 540
 541 /* -----[
 542    - compress foo["bar"] into foo.bar,
 543    - remove block brackets {} where possible
 544    - join consecutive var declarations
 545    - various optimizations for IFs:
 546      - if (cond) foo(); else bar();  ==>  cond?foo():bar();
 547      - if (cond) foo();  ==>  cond&&foo();
 548      - if (foo) return bar(); else return baz();  ==> return foo?bar():baz(); // also for throw
 549      - if (foo) return bar(); else something();  ==> {if(foo)return bar();something()}
 550    ]----- */
 551
 552 var warn = function(){};
 553
 554 function best_of(ast1, ast2) {
 555         return gen_code(ast1).length > gen_code(ast2[0] == "stat" ? ast2[1] : ast2).length ? ast2 : ast1;
 556 };
 557
 558 function last_stat(b) {
 559         if (b[0] == "block" && b[1] && b[1].length > 0)
 560                 return b[1][b[1].length - 1];
 561         return b;
 562 }
 563
 564 function aborts(t) {
 565         if (t) {
 566                 t = last_stat(t);
 567                 if (t[0] == "return" || t[0] == "break" || t[0] == "continue" || t[0] == "throw")
 568                         return true;
 569         }
 570 };
 571
 572 function negate(c) {
 573         var not_c = [ "unary-prefix", "!", c ];
 574         switch (c[0]) {
 575             case "unary-prefix":
 576                 return c[1] == "!" ? c[2] : not_c;
 577             case "binary":
 578                 var op = c[1], left = c[2], right = c[3];
 579                 switch (op) {
 580                     case "<=": return [ "binary", ">", left, right ];
 581                     case "<": return [ "binary", ">=", left, right ];
 582                     case ">=": return [ "binary", "<", left, right ];
 583                     case ">": return [ "binary", "<=", left, right ];
 584                     case "==": return [ "binary", "!=", left, right ];
 585                     case "!=": return [ "binary", "==", left, right ];
 586                     case "===": return [ "binary", "!==", left, right ];
 587                     case "!==": return [ "binary", "===", left, right ];
 588                     case "&&": return best_of(not_c, [ "binary", "||", negate(left), negate(right) ]);
 589                     case "||": return best_of(not_c, [ "binary", "&&", negate(left), negate(right) ]);
 590                 }
 591                 break;
 592         }
 593         return not_c;
 594 };
 595
 596 function make_conditional(c, t, e) {
 597         if (c[0] == "unary-prefix" && c[1] == "!") {
 598                 return e ? [ "conditional", c[2], e, t ] : [ "binary", "||", c[2], t ];
 599         } else {
 600                 return e ? [ "conditional", c, t, e ] : [ "binary", "&&", c, t ];
 601         }
 602 };
 603
 604 function empty(b) {
 605         return !b || (b[0] == "block" && (!b[1] || b[1].length == 0));
 606 };
 607
 608 function ast_squeeze(ast, options) {
 609         options = defaults(options, {
 610                 make_seqs   : true,
 611                 dead_code   : true,
 612                 no_warnings : false,
 613                 extra       : false
 614         });
 615
 616         var w = ast_walker(), walk = w.walk, scope;
 617
 618         function with_scope(s, cont) {
 619                 var _scope = scope;
 620                 scope = s;
 621                 var ret = cont();
 622                 ret.scope = s;
 623                 scope = _scope;
 624                 return ret;
 625         };
 626
 627         function is_constant(node) {
 628                 return node[0] == "string" || node[0] == "num";
 629         };
 630
 631         function find_first_execute(node) {
 632                 if (!node)
 633                         return false;
 634
 635                 switch (node[0]) {
 636                         case "num":
 637                         case "string":
 638                         case "name":
 639                                 return node;
 640                         case "call":
 641                         case "conditional":
 642                         case "for":
 643                         case "if":
 644                         case "new":
 645                         case "return":
 646                         case "stat":
 647                         case "switch":
 648                         case "throw":
 649                                 return find_first_execute(node[1]);
 650                         case "binary":
 651                                 return find_first_execute(node[2]);
 652                         case "assign":
 653                                 if (node[1] === true)
 654                                         return find_first_execute(node[3]);
 655                                 break;
 656                         case "var":
 657                                 if (node[1][0].length > 1)
 658                                         return find_first_execute(node[1][0][1]);
 659                                 break;
 660                 }
 661                 return null;
 662         }
 663
 664         function find_assign_recursive(p, v) {
 665                 if (p[0] == "assign" && p[1] != true || p[0] == "unary-prefix") {
 666                         if (p[2][0] == "name" && v[0] == "name" && p[2][1] == v[1])
 667                                 return true;
 668                         return false;
 669                 }
 670
 671                 if (p[0] != "assign" || p[1] !== true)
 672                         return false;
 673
 674                 if ((is_constant(p[3]) && p[3][0] == v[0] && p[3][1] == v[1]) ||
 675                     (p[3][0] == "name" && v[0] == "name" && p[3][1] == v[1]) ||
 676                     (p[2][0] == "name" && v[0] == "name" && p[2][1] == v[1]))
 677                         return true;
 678
 679                 return find_assign_recursive(p[3], v);
 680         };
 681
 682         function rmblock(block) {
 683                 if (block != null && block[0] == "block" && block[1] && block[1].length == 1)
 684                         block = block[1][0];
 685                 return block;
 686         };
 687
 688         function clone(obj) {
 689                 if (obj && obj.constructor == Array)
 690                         return MAP(obj, clone);
 691                 return obj;
 692         };
 693
 694         function make_seq_to_statements(node) {
 695                 if (node[0] != "seq") {
 696                         switch (node[0]) {
 697                                 case "var":
 698                                 case "const":
 699                                         return [ node ];
 700                                 default:
 701                                         return [ [ "stat", node ] ];
 702                         }
 703                 }
 704
 705                 var ret = [];
 706                 for (var i = 1; i < node.length; i++)
 707                         ret.push.apply(ret, make_seq_to_statements(node[i]));
 708
 709                 return ret;
 710         };
 711
 712         function _lambda(name, args, body) {
 713                 return [ this[0], name, args, with_scope(body.scope, function(){
 714                         return tighten(MAP(body, walk), "lambda");
 715                 }) ];
 716         };
 717
 718         // we get here for blocks that have been already transformed.
 719         // this function does a few things:
 720         // 1. discard useless blocks
 721         // 2. join consecutive var declarations
 722         // 3. remove obviously dead code
 723         // 4. transform consecutive statements using the comma operator
 724         // 5. if block_type == "lambda" and it detects constructs like if(foo) return ... - rewrite like if (!foo) { ... }
 725         function tighten(statements, block_type) {
 726                 statements = statements.reduce(function(a, stat){
 727                         if (stat[0] == "block") {
 728                                 if (stat[1]) {
 729                                         a.push.apply(a, stat[1]);
 730                                 }
 731                         } else {
 732                                 a.push(stat);
 733                         }
 734                         return a;
 735                 }, []);
 736
 737                 if (options.extra) {
 738                         // Detightening things. We do this because then we can assume that the
 739                         // statements are structured in a specific way.
 740                         statements = (function(a, prev) {
 741                                 statements.forEach(function(cur) {
 742                                         switch (cur[0]) {
 743                                             case "for":
 744                                                 if (cur[1] != null) {
 745                                                         a.push.apply(a, make_seq_to_statements(cur[1]));
 746                                                         cur[1] = null;
 747                                                 }
 748                                                 a.push(cur);
 749                                                 break;
 750                                             case "stat":
 751                                                 var stats = make_seq_to_statements(cur[1]);
 752                                                 stats.forEach(function(s) {
 753                                                         if (s[1][0] == "unary-postfix")
 754                                                                 s[1][0] = "unary-prefix";
 755                                                 });
 756                                                 a.push.apply(a, stats);
 757                                                 break;
 758                                             default:
 759                                                 a.push(cur);
 760                                         }
 761                                 });
 762                                 return a;
 763                         })([]);
 764
 765                         statements = (function(a, prev) {
 766                                 statements.forEach(function(cur) {
 767                                         if (!(prev && prev[0] == "stat")) {
 768                                                 a.push(cur);
 769                                                 prev = cur;
 770                                                 return;
 771                                         }
 772
 773                                         var p = prev[1];
 774                                         var c = find_first_execute(cur);
 775                                         if (c && find_assign_recursive(p, c)) {
 776                                                 var old_cur = clone(cur);
 777                                                 c.splice(0, c.length);
 778                                                 c.push.apply(c, p);
 779                                                 var tmp_cur = best_of(cur, [ "toplevel", [ prev, old_cur ] ]);
 780                                                 if (tmp_cur == cur) {
 781                                                         a[a.length -1] = cur;
 782                                                 } else {
 783                                                         cur = old_cur;
 784                                                         a.push(cur);
 785                                                 }
 786                                         } else {
 787                                                 a.push(cur);
 788                                         }
 789                                         prev = cur;
 790                                 });
 791                                 return a;
 792                         })([]);
 793                 }
 794
 795                 statements = (function(a, prev){
 796                         statements.forEach(function(cur){
 797                                 if (prev && ((cur[0] == "var" && prev[0] == "var") ||
 798                                              (cur[0] == "const" && prev[0] == "const"))) {
 799                                         prev[1] = prev[1].concat(cur[1]);
 800                                 } else {
 801                                         a.push(cur);
 802                                         prev = cur;
 803                                 }
 804                         });
 805                         return a;
 806                 })([]);
 807
 808                 if (options.dead_code) statements = (function(a, has_quit){
 809                         statements.forEach(function(st){
 810                                 if (has_quit) {
 811                                         if (member(st[0], [ "function", "defun" , "var", "const" ])) {
 812                                                 a.push(st);
 813                                         }
 814                                         else if (!options.no_warnings)
 815                                                 warn("Removing unreachable code: " + gen_code(st, true));
 816                                 }
 817                                 else {
 818                                         a.push(st);
 819                                         if (member(st[0], [ "return", "throw", "break", "continue" ]))
 820                                                 has_quit = true;
 821                                 }
 822                         });
 823                         return a;
 824                 })([]);
 825
 826                 if (options.make_seqs) statements = (function(a, prev) {
 827                         statements.forEach(function(cur){
 828                                 if (prev && prev[0] == "stat" && cur[0] == "stat") {
 829                                         prev[1] = [ "seq", prev[1], cur[1] ];
 830                                 } else {
 831                                         a.push(cur);
 832                                         prev = cur;
 833                                 }
 834                         });
 835                         return a;
 836                 })([]);
 837
 838                 if (options.extra) {
 839                         statements = (function(a, prev){
 840                                 statements.forEach(function(cur){
 841                                         var replaced = false;
 842                                         if (prev && cur[0] == "for" && cur[1] == null && (prev[0] == "var" || prev[0] == "const" || prev[0] == "stat")) {
 843                                                 cur[1] = prev;
 844                                                 a[a.length - 1] = cur;
 845                                         } else {
 846                                                 a.push(cur);
 847                                         }
 848                                         prev = cur;
 849                                 });
 850                                 return a;
 851                         })([]);
 852                 }
 853
 854                 if (block_type == "lambda") statements = (function(i, a, stat){
 855                         while (i < statements.length) {
 856                                 stat = statements[i++];
 857                                 if (stat[0] == "if" && !stat[3]) {
 858                                         if (stat[2][0] == "return" && stat[2][1] == null) {
 859                                                 a.push(make_if(negate(stat[1]), [ "block", statements.slice(i) ]));
 860                                                 break;
 861                                         }
 862                                         var last = last_stat(stat[2]);
 863                                         if (last[0] == "return" && last[1] == null) {
 864                                                 a.push(make_if(stat[1], [ "block", stat[2][1].slice(0, -1) ], [ "block", statements.slice(i) ]));
 865                                                 break;
 866                                         }
 867                                 }
 868                                 a.push(stat);
 869                         }
 870                         return a;
 871                 })(0, []);
 872
 873                 return statements;
 874         };
 875
 876         function make_if(c, t, e) {
 877                 c = walk(c);
 878                 t = walk(t);
 879                 e = walk(e);
 880
 881                 if (empty(t)) {
 882                         c = negate(c);
 883                         t = e;
 884                         e = null;
 885                 } else if (empty(e)) {
 886                         e = null;
 887                 } else {
 888                         // if we have both else and then, maybe it makes sense to switch them?
 889                         (function(){
 890                                 var a = gen_code(c);
 891                                 var n = negate(c);
 892                                 var b = gen_code(n);
 893                                 if (b.length < a.length) {
 894                                         var tmp = t;
 895                                         t = e;
 896                                         e = tmp;
 897                                         c = n;
 898                                 }
 899                         })();
 900                 }
 901                 if (empty(e) && empty(t))
 902                         return [ "stat", c ];
 903                 var ret = [ "if", c, t, e ];
 904                 if (t[0] == "stat") {
 905                         if (e) {
 906                                 if (e[0] == "stat") {
 907                                         ret = best_of(ret, [ "stat", make_conditional(c, t[1], e[1]) ]);
 908                                 }
 909                         }
 910                         else {
 911                                 ret = best_of(ret, [ "stat", make_conditional(c, t[1]) ]);
 912                         }
 913                 }
 914                 else if (e && t[0] == e[0] && (t[0] == "return" || t[0] == "throw")) {
 915                         ret = best_of(ret, [ t[0], make_conditional(c, t[1], e[1] ) ]);
 916                 }
 917                 else if (e && aborts(t)) {
 918                         ret = [ [ "if", c, t ] ];
 919                         if (e[0] == "block") {
 920                                 if (e[1]) ret = ret.concat(e[1]);
 921                         }
 922                         else {
 923                                 ret.push(e);
 924                         }
 925                         ret = walk([ "block", ret ]);
 926                 }
 927                 else if (t && aborts(e)) {
 928                         ret = [ [ "if", negate(c), e ] ];
 929                         if (t[0] == "block") {
 930                                 if (t[1]) ret = ret.concat(t[1]);
 931                         } else {
 932                                 ret.push(t);
 933                         }
 934                         ret = walk([ "block", ret ]);
 935                 }
 936                 return ret;
 937         };
 938
 939         return w.with_walkers({
 940                 "sub": function(expr, subscript) {
 941                         if (subscript[0] == "string") {
 942                                 var name = subscript[1];
 943                                 if (is_identifier(name)) {
 944                                         return [ "dot", walk(expr), name ];
 945                                 }
 946                         }
 947                 },
 948                 "if": make_if,
 949                 "toplevel": function(body) {
 950                         return [ "toplevel", with_scope(this.scope, function(){
 951                                 return tighten(MAP(body, walk));
 952                         }) ];
 953                 },
 954                 "switch": function(expr, body) {
 955                         var last = body.length - 1;
 956                         return [ "switch", walk(expr), MAP(body, function(branch, i){
 957                                 var block = tighten(MAP(branch[1], walk));
 958                                 if (i == last && block.length > 0) {
 959                                         var node = block[block.length - 1];
 960                                         if (node[0] == "break" && !node[1])
 961                                                 block.pop();
 962                                 }
 963                                 return [ branch[0] ? walk(branch[0]) : null, block ];
 964                         }) ];
 965                 },
 966                 "function": _lambda,
 967                 "defun": _lambda,
 968                 "block": function(body) {
 969                         if (body) return rmblock([ "block", tighten(MAP(body, walk)) ]);
 970                 },
 971                 "binary": function(op, left, right) {
 972                         left = walk(left);
 973                         right = walk(right);
 974                         var best = [ "binary", op, left, right ];
 975                         if (is_constant(right)) {
 976                                 if (is_constant(left)) {
 977                                         var val = null;
 978                                         switch (op) {
 979                                             case "+": val = left[1] + right[1]; break;
 980                                             case "*": val = left[1] * right[1]; break;
 981                                             case "/": val = left[1] / right[1]; break;
 982                                             case "-": val = left[1] - right[1]; break;
 983                                             case "<<": val = left[1] << right[1]; break;
 984                                             case ">>": val = left[1] >> right[1]; break;
 985                                             case ">>>": val = left[1] >>> right[1]; break;
 986                                         }
 987                                         if (val != null) {
 988                                                 best = best_of(best, [ typeof val == "string" ? "string" : "num", val ]);
 989                                         }
 990                                 } else if (left[0] == "binary" && left[1] == "+" && left[3][0] == "string") {
 991                                         best = best_of(best, [ "binary", "+", left[2], [ "string", left[3][1] + right[1] ] ]);
 992                                 }
 993                         }
 994                         return best;
 995                 },
 996                 "conditional": function(c, t, e) {
 997                         return make_conditional(walk(c), walk(t), walk(e));
 998                 },
 999                 "try": function(t, c, f) {
1000                         return [
1001                                 "try",
1002                                 tighten(MAP(t, walk)),
1003                                 c != null ? [ c[0], tighten(MAP(c[1], walk)) ] : null,
1004                                 f != null ? tighten(MAP(f, walk)) : null
1005                         ];
1006                 },
1007                 "unary-prefix": function(op, cond) {
1008                         if (op == "!") {
1009                                 cond = walk(cond);
1010                                 if (cond[0] == "unary-prefix" && cond[1] == "!") {
1011                                         var p = w.parent();
1012                                         if (p[0] == "unary-prefix" && p[1] == "!")
1013                                                 return cond[2];
1014                                         return [ "unary-prefix", "!", cond ];
1015                                 }
1016                                 return best_of(this, negate(cond));
1017                         }
1018                 },
1019                 "name": function(name) {
1020                         switch (name) {
1021                             case "true": return [ "unary-prefix", "!", [ "num", 0 ]];
1022                             case "false": return [ "unary-prefix", "!", [ "num", 1 ]];
1023                         }
1024                 },
1025                 "new": function(ctor, args) {
1026                         if (ctor[0] == "name" && ctor[1] == "Array" && !scope.has("Array")) {
1027                                 if (args.length != 1) {
1028                                         return [ "array", args ];
1029                                 } else {
1030                                         return [ "call", [ "name", "Array" ], args ];
1031                                 }
1032                         }
1033                 },
1034                 "call": function(expr, args) {
1035                         if (expr[0] == "name" && expr[1] == "Array" && args.length != 1 && !scope.has("Array")) {
1036                                 return [ "array", args ];
1037                         }
1038                 }
1039         }, function() {
1040                 return walk(ast_add_scope(ast));
1041         });
1042 };
1043
1044 /* -----[ re-generate code from the AST ]----- */
1045
1046 var DOT_CALL_NO_PARENS = jsp.array_to_hash([
1047         "name",
1048         "array",
1049         "string",
1050         "dot",
1051         "sub",
1052         "call",
1053         "regexp"
1054 ]);
1055
1056 function make_string(str) {
1057         var dq = 0, sq = 0;
1058         str = str.replace(/[\\\b\f\n\r\t\x22\x27]/g, function(s){
1059                 switch (s) {
1060                     case "\\": return "\\\\";
1061                     case "\b": return "\\b";
1062                     case "\f": return "\\f";
1063                     case "\n": return "\\n";
1064                     case "\r": return "\\r";
1065                     case "\t": return "\\t";
1066                     case '"': ++dq; return '"';
1067                     case "'": ++sq; return "'";
1068                 }
1069                 return s;
1070         });
1071         if (dq > sq) {
1072                 return "'" + str.replace(/\x27/g, "\\'") + "'";
1073         } else {
1074                 return '"' + str.replace(/\x22/g, '\\"') + '"';
1075         }
1076 };
1077
1078 function gen_code(ast, beautify) {
1079         if (beautify) beautify = defaults(beautify, {
1080                 indent_start : 0,
1081                 indent_level : 4,
1082                 quote_keys   : false,
1083                 space_colon  : false
1084         });
1085         var indentation = 0,
1086             newline = beautify ? "\n" : "",
1087             space = beautify ? " " : "";
1088
1089         function indent(line) {
1090                 if (line == null)
1091                         line = "";
1092                 if (beautify)
1093                         line = repeat_string(" ", beautify.indent_start + indentation * beautify.indent_level) + line;
1094                 return line;
1095         };
1096
1097         function with_indent(cont, incr) {
1098                 if (incr == null) incr = 1;
1099                 indentation += incr;
1100                 try { return cont.apply(null, slice(arguments, 1)); }
1101                 finally { indentation -= incr; }
1102         };
1103
1104         function add_spaces(a) {
1105                 if (beautify)
1106                         return a.join(" ");
1107                 var b = [];
1108                 for (var i = 0; i < a.length; ++i) {
1109                         var next = a[i + 1];
1110                         b.push(a[i]);
1111                         if (next &&
1112                             ((/[a-z0-9_\x24]$/i.test(a[i].toString()) && /^[a-z0-9_\x24]/i.test(next.toString())) ||
1113                              (/[\+\-]$/.test(a[i].toString()) && /^[\+\-]/.test(next.toString())))) {
1114                                 b.push(" ");
1115                         }
1116                 }
1117                 return b.join("");
1118         };
1119
1120         function add_commas(a) {
1121                 return a.join("," + space);
1122         };
1123
1124         function parenthesize(expr) {
1125                 var gen = make(expr);
1126                 for (var i = 1; i < arguments.length; ++i) {
1127                         var el = arguments[i];
1128                         if ((el instanceof Function && el(expr)) || expr[0] == el)
1129                                 return "(" + gen + ")";
1130                 }
1131                 return gen;
1132         };
1133
1134         function best_of(a) {
1135                 if (a.length == 1) {
1136                         return a[0];
1137                 }
1138                 if (a.length == 2) {
1139                         var b = a[1];
1140                         a = a[0];
1141                         return a.length <= b.length ? a : b;
1142                 }
1143                 return best_of([ a[0], best_of(a.slice(1)) ]);
1144         };
1145
1146         function needs_parens(expr) {
1147                 if (expr[0] == "function") {
1148                         // dot/call on a literal function requires the
1149                         // function literal itself to be parenthesized
1150                         // only if it's the first "thing" in a
1151                         // statement.  This means that the parent is
1152                         // "stat", but it could also be a "seq" and
1153                         // we're the first in this "seq" and the
1154                         // parent is "stat", and so on.  Messy stuff,
1155                         // but it worths the trouble.
1156                         var a = slice($stack), self = a.pop(), p = a.pop();
1157                         while (p) {
1158                                 if (p[0] == "stat") return true;
1159                                 if ((p[0] == "seq" && p[1] === self) ||
1160                                     (p[0] == "call" && p[1] === self) ||
1161                                     (p[0] == "binary" && p[2] === self)) {
1162                                         self = p;
1163                                         p = a.pop();
1164                                 } else {
1165                                         return false;
1166                                 }
1167                         }
1168                 }
1169                 return !HOP(DOT_CALL_NO_PARENS, expr[0]);
1170         };
1171
1172         function make_num(num) {
1173                 var str = num.toString(10), a = [ str.replace(/^0\./, ".") ], m;
1174                 if (Math.floor(num) === num) {
1175                         a.push("0x" + num.toString(16).toLowerCase(), // probably pointless
1176                                "0" + num.toString(8)); // same.
1177                         if ((m = /^(.*?)(0+)$/.exec(num))) {
1178                                 a.push(m[1] + "e" + m[2].length);
1179                         }
1180                 } else if ((m = /^0?\.(0+)(.*)$/.exec(num))) {
1181                         a.push(m[2] + "e-" + (m[1].length + m[2].length),
1182                                str.substr(str.indexOf(".")));
1183                 }
1184                 return best_of(a);
1185         };
1186
1187         var generators = {
1188                 "string": make_string,
1189                 "num": make_num,
1190                 "name": make_name,
1191                 "toplevel": function(statements) {
1192                         return make_block_statements(statements)
1193                                 .join(newline + newline);
1194                 },
1195                 "block": make_block,
1196                 "var": function(defs) {
1197                         return "var " + add_commas(MAP(defs, make_1vardef)) + ";";
1198                 },
1199                 "const": function(defs) {
1200                         return "const " + add_commas(MAP(defs, make_1vardef)) + ";";
1201                 },
1202                 "try": function(tr, ca, fi) {
1203                         var out = [ "try", make_block(tr) ];
1204                         if (ca) out.push("catch", "(" + ca[0] + ")", make_block(ca[1]));
1205                         if (fi) out.push("finally", make_block(fi));
1206                         return add_spaces(out);
1207                 },
1208                 "throw": function(expr) {
1209                         return add_spaces([ "throw", make(expr) ]) + ";";
1210                 },
1211                 "new": function(ctor, args) {
1212                         args = args.length > 0 ? "(" + add_commas(MAP(args, make)) + ")" : "";
1213                         return add_spaces([ "new", parenthesize(ctor, "seq", "binary", "conditional", "assign", function(expr){
1214                                 var w = ast_walker(), has_call = {};
1215                                 try {
1216                                         w.with_walkers({
1217                                                 "call": function() { throw has_call },
1218                                                 "function": function() { return this }
1219                                         }, function(){
1220                                                 w.walk(expr);
1221                                         });
1222                                 } catch(ex) {
1223                                         if (ex === has_call)
1224                                                 return true;
1225                                         throw ex;
1226                                 }
1227                         }) + args ]);
1228                 },
1229                 "switch": function(expr, body) {
1230                         return add_spaces([ "switch", "(" + make(expr) + ")", make_switch_block(body) ]);
1231                 },
1232                 "break": function(label) {
1233                         var out = "break";
1234                         if (label != null)
1235                                 out += " " + make_name(label);
1236                         return out + ";";
1237                 },
1238                 "continue": function(label) {
1239                         var out = "continue";
1240                         if (label != null)
1241                                 out += " " + make_name(label);
1242                         return out + ";";
1243                 },
1244                 "conditional": function(co, th, el) {
1245                         return add_spaces([ parenthesize(co, "assign", "seq", "conditional"), "?",
1246                                             parenthesize(th, "seq"), ":",
1247                                             parenthesize(el, "seq") ]);
1248                 },
1249                 "assign": function(op, lvalue, rvalue) {
1250                         if (op && op !== true) op += "=";
1251                         else op = "=";
1252                         return add_spaces([ make(lvalue), op, parenthesize(rvalue, "seq") ]);
1253                 },
1254                 "dot": function(expr) {
1255                         var out = make(expr), i = 1;
1256                         if (expr[0] == "num")
1257                                 out += ".";
1258                         else if (needs_parens(expr))
1259                                 out = "(" + out + ")";
1260                         while (i < arguments.length)
1261                                 out += "." + make_name(arguments[i++]);
1262                         return out;
1263                 },
1264                 "call": function(func, args) {
1265                         var f = make(func);
1266                         if (needs_parens(func))
1267                                 f = "(" + f + ")";
1268                         return f + "(" + add_commas(MAP(args, function(expr){
1269                                 return parenthesize(expr, "seq");
1270                         })) + ")";
1271                 },
1272                 "function": make_function,
1273                 "defun": make_function,
1274                 "if": function(co, th, el) {
1275                         var out = [ "if", "(" + make(co) + ")", el ? make_then(th) : make(th) ];
1276                         if (el) {
1277                                 out.push("else", make(el));
1278                         }
1279                         return add_spaces(out);
1280                 },
1281                 "for": function(init, cond, step, block) {
1282                         var out = [ "for" ];
1283                         init = (init != null ? make(init) : "").replace(/;*\s*$/, ";" + space);
1284                         cond = (cond != null ? make(cond) : "").replace(/;*\s*$/, ";" + space);
1285                         step = (step != null ? make(step) : "").replace(/;*\s*$/, "");
1286                         var args = init + cond + step;
1287                         if (args == "; ; ") args = ";;";
1288                         out.push("(" + args + ")", make(block));
1289                         return add_spaces(out);
1290                 },
1291                 "for-in": function(has_var, key, hash, block) {
1292                         var out = add_spaces([ "for", "(" ]);
1293                         if (has_var)
1294                                 out += "var ";
1295                         out += add_spaces([ make_name(key) + " in " + make(hash) + ")", make(block) ]);
1296                         return out;
1297                 },
1298                 "while": function(condition, block) {
1299                         return add_spaces([ "while", "(" + make(condition) + ")", make(block) ]);
1300                 },
1301                 "do": function(condition, block) {
1302                         return add_spaces([ "do", make(block), "while", "(" + make(condition) + ")" ]) + ";";
1303                 },
1304                 "return": function(expr) {
1305                         var out = [ "return" ];
1306                         if (expr != null) out.push(make(expr));
1307                         return add_spaces(out) + ";";
1308                 },
1309                 "binary": function(operator, lvalue, rvalue) {
1310                         var left = make(lvalue), right = make(rvalue);
1311                         // XXX: I'm pretty sure other cases will bite here.
1312                         //      we need to be smarter.
1313                         //      adding parens all the time is the safest bet.
1314                         if (member(lvalue[0], [ "assign", "conditional", "seq" ]) ||
1315                             lvalue[0] == "binary" && PRECEDENCE[operator] > PRECEDENCE[lvalue[1]]) {
1316                                 left = "(" + left + ")";
1317                         }
1318                         if (member(rvalue[0], [ "assign", "conditional", "seq" ]) ||
1319                             rvalue[0] == "binary" && PRECEDENCE[operator] >= PRECEDENCE[rvalue[1]]) {
1320                                 right = "(" + right + ")";
1321                         }
1322                         return add_spaces([ left, operator, right ]);
1323                 },
1324                 "unary-prefix": function(operator, expr) {
1325                         var val = make(expr);
1326                         if (!(expr[0] == "num" || (expr[0] == "unary-prefix" && !HOP(OPERATORS, operator + expr[1])) || !needs_parens(expr)))
1327                                 val = "(" + val + ")";
1328                         return operator + (jsp.is_alphanumeric_char(operator.charAt(0)) ? " " : "") + val;
1329                 },
1330                 "unary-postfix": function(operator, expr) {
1331                         var val = make(expr);
1332                         if (!(expr[0] == "num" || (expr[0] == "unary-postfix" && !HOP(OPERATORS, operator + expr[1])) || !needs_parens(expr)))
1333                                 val = "(" + val + ")";
1334                         return val + operator;
1335                 },
1336                 "sub": function(expr, subscript) {
1337                         var hash = make(expr);
1338                         if (needs_parens(expr))
1339                                 hash = "(" + hash + ")";
1340                         return hash + "[" + make(subscript) + "]";
1341                 },
1342                 "object": function(props) {
1343                         if (props.length == 0)
1344                                 return "{}";
1345                         return "{" + newline + with_indent(function(){
1346                                 return MAP(props, function(p){
1347                                         if (p.length == 3) {
1348                                                 // getter/setter.  The name is in p[0], the arg.list in p[1][2], the
1349                                                 // body in p[1][3] and type ("get" / "set") in p[2].
1350                                                 return indent(make_function(p[0], p[1][2], p[1][3], p[2]));
1351                                         }
1352                                         var key = p[0], val = make(p[1]);
1353                                         if (beautify && beautify.quote_keys) {
1354                                                 key = make_string(key);
1355                                         } else if (typeof key == "number" || !beautify && +key + "" == key) {
1356                                                 key = make_num(+key);
1357                                         } else if (!is_identifier(key)) {
1358                                                 key = make_string(key);
1359                                         }
1360                                         return indent(add_spaces(beautify && beautify.space_colon
1361                                                                  ? [ key, ":", val ]
1362                                                                  : [ key + ":", val ]));
1363                                 }).join("," + newline);
1364                         }) + newline + indent("}");
1365                 },
1366                 "regexp": function(rx, mods) {
1367                         return "/" + rx + "/" + mods;
1368                 },
1369                 "array": function(elements) {
1370                         if (elements.length == 0) return "[]";
1371                         return add_spaces([ "[", add_commas(MAP(elements, function(el){
1372                                 return parenthesize(el, "seq");
1373                         })), "]" ]);
1374                 },
1375                 "stat": function(stmt) {
1376                         return make(stmt).replace(/;*\s*$/, ";");
1377                 },
1378                 "seq": function() {
1379                         return add_commas(MAP(slice(arguments), make));
1380                 },
1381                 "label": function(name, block) {
1382                         return add_spaces([ make_name(name), ":", make(block) ]);
1383                 },
1384                 "with": function(expr, block) {
1385                         return add_spaces([ "with", "(" + make(expr) + ")", make(block) ]);
1386                 },
1387                 "atom": function(name) {
1388                         return make_name(name);
1389                 },
1390                 "comment1": function(text) {
1391                         return "//" + text + "\n";
1392                 },
1393                 "comment2": function(text) {
1394                         return "/*" + text + "*/";
1395                 }
1396         };
1397
1398         // The squeezer replaces "block"-s that contain only a single
1399         // statement with the statement itself; technically, the AST
1400         // is correct, but this can create problems when we output an
1401         // IF having an ELSE clause where the THEN clause ends in an
1402         // IF *without* an ELSE block (then the outer ELSE would refer
1403         // to the inner IF).  This function checks for this case and
1404         // adds the block brackets if needed.
1405         function make_then(th) {
1406                 if (th[0] == "do") {
1407                         // https://github.com/mishoo/UglifyJS/issues/#issue/57
1408                         // IE croaks with "syntax error" on code like this:
1409                         //     if (foo) do ... while(cond); else ...
1410                         // we need block brackets around do/while
1411                         return make([ "block", [ th ]]);
1412                 }
1413                 var b = th;
1414                 while (true) {
1415                         var type = b[0];
1416                         if (type == "if") {
1417                                 if (!b[3])
1418                                         // no else, we must add the block
1419                                         return make([ "block", [ th ]]);
1420                                 b = b[3];
1421                         }
1422                         else if (type == "while" || type == "do") b = b[2];
1423                         else if (type == "for" || type == "for-in") b = b[4];
1424                         else break;
1425                 }
1426                 return make(th);
1427         };
1428
1429         function make_function(name, args, body, keyword) {
1430                 var out = keyword || "function";
1431                 if (name) {
1432                         out += " " + make_name(name);
1433                 }
1434                 out += "(" + add_commas(MAP(args, make_name)) + ")";
1435                 return add_spaces([ out, make_block(body) ]);
1436         };
1437
1438         function make_name(name) {
1439                 return name.toString();
1440         };
1441
1442         function make_block_statements(statements) {
1443                 for (var a = [], last = statements.length - 1, i = 0; i <= last; ++i) {
1444                         var stat = statements[i];
1445                         var code = make(stat);
1446                         if (code != ";") {
1447                                 if (!beautify && i == last)
1448                                         code = code.replace(/;+\s*$/, "");
1449                                 a.push(code);
1450                         }
1451                 }
1452                 return MAP(a, indent);
1453         };
1454
1455         function make_switch_block(body) {
1456                 var n = body.length;
1457                 if (n == 0) return "{}";
1458                 return "{" + newline + MAP(body, function(branch, i){
1459                         var has_body = branch[1].length > 0, code = with_indent(function(){
1460                                 return indent(branch[0]
1461                                               ? add_spaces([ "case", make(branch[0]) + ":" ])
1462                                               : "default:");
1463                         }, 0.5) + (has_body ? newline + with_indent(function(){
1464                                 return make_block_statements(branch[1]).join(newline);
1465                         }) : "");
1466                         if (!beautify && has_body && i < n - 1)
1467                                 code += ";";
1468                         return code;
1469                 }).join(newline) + newline + indent("}");
1470         };
1471
1472         function make_block(statements) {
1473                 if (!statements) return ";";
1474                 if (statements.length == 0) return "{}";
1475                 return "{" + newline + with_indent(function(){
1476                         return make_block_statements(statements).join(newline);
1477                 }) + newline + indent("}");
1478         };
1479
1480         function make_1vardef(def) {
1481                 var name = def[0], val = def[1];
1482                 if (val != null)
1483                         name = add_spaces([ name, "=", make(val) ]);
1484                 return name;
1485         };
1486
1487         var $stack = [];
1488
1489         function make(node) {
1490                 var type = node[0];
1491                 var gen = generators[type];
1492                 if (!gen)
1493                         throw new Error("Can't find generator for \"" + type + "\"");
1494                 $stack.push(node);
1495                 var ret = gen.apply(type, node.slice(1));
1496                 $stack.pop();
1497                 return ret;
1498         };
1499
1500         return make(ast);
1501 };
1502
1503 /* -----[ Utilities ]----- */
1504
1505 function repeat_string(str, i) {
1506         if (i <= 0) return "";
1507         if (i == 1) return str;
1508         var d = repeat_string(str, i >> 1);
1509         d += d;
1510         if (i & 1) d += str;
1511         return d;
1512 };
1513
1514 function defaults(args, defs) {
1515         var ret = {};
1516         if (args === true)
1517                 args = {};
1518         for (var i in defs) if (HOP(defs, i)) {
1519                 ret[i] = (args && HOP(args, i)) ? args[i] : defs[i];
1520         }
1521         return ret;
1522 };
1523
1524 function is_identifier(name) {
1525         return /^[a-z_$][a-z0-9_$]*$/i.test(name)
1526                 && name != "this"
1527                 && !HOP(jsp.KEYWORDS_ATOM, name)
1528                 && !HOP(jsp.RESERVED_WORDS, name)
1529                 && !HOP(jsp.KEYWORDS, name);
1530 };
1531
1532 function HOP(obj, prop) {
1533         return Object.prototype.hasOwnProperty.call(obj, prop);
1534 };
1535
1536 // some utilities
1537
1538 var MAP;
1539
1540 (function(){
1541         MAP = function(a, f, o) {
1542                 var ret = [];
1543                 for (var i = 0; i < a.length; ++i) {
1544                         var val = f.call(o, a[i], i);
1545                         if (val instanceof AtTop) ret.unshift(val.v);
1546                         else ret.push(val);
1547                 }
1548                 return ret;
1549         };
1550         MAP.at_top = function(val) { return new AtTop(val) };
1551         function AtTop(val) { this.v = val };
1552 })();
1553
1554 /* -----[ Exports ]----- */
1555
1556 exports.ast_walker = ast_walker;
1557 exports.ast_mangle = ast_mangle;
1558 exports.ast_squeeze = ast_squeeze;
1559 exports.gen_code = gen_code;
1560 exports.ast_add_scope = ast_add_scope;
1561 exports.ast_squeeze_more = require("./squeeze-more").ast_squeeze_more;
1562 exports.set_logger = function(logger) { warn = logger };