expand symbol space to improve compression (#2460)

- give globally distinct names to distinct variables
- improve ability to compress cross-scoped
- introduce `options.rename` to `minify()`
- default `true` if both `compress` & `mangle`

2 files changed, 85 insertions, 22 deletions

diff --git a/lib/minify.js b/lib/minify.js
index f9d726bf..806c3aeb 100644
--- a/lib/minify.js
+++ b/lib/minify.js
@@ -55,6 +55,7 @@ function minify(files, options) {
             nameCache: null,
             output: {},
             parse: {},
+            rename: undefined,
             sourceMap: false,
             timings: false,
             toplevel: false,
@@ -64,6 +65,9 @@ function minify(files, options) {
         var timings = options.timings && {
             start: Date.now()
         };
+        if (options.rename === undefined) {
+            options.rename = options.compress && options.mangle;
+        }
         set_shorthand("ie8", options, [ "compress", "mangle", "output" ]);
         set_shorthand("keep_fnames", options, [ "compress", "mangle" ]);
         set_shorthand("toplevel", options, [ "compress", "mangle" ]);
@@ -137,6 +141,11 @@ function minify(files, options) {
         if (options.wrap) {
             toplevel = toplevel.wrap_commonjs(options.wrap);
         }
+        if (timings) timings.rename = Date.now();
+        if (options.rename) {
+            toplevel.figure_out_scope(options.mangle);
+            toplevel.expand_names(options.mangle);
+        }
         if (timings) timings.compress = Date.now();
         if (options.compress) toplevel = new Compressor(options.compress).compress(toplevel);
         if (timings) timings.scope = Date.now();
@@ -197,7 +206,8 @@ function minify(files, options) {
         if (timings) {
             timings.end = Date.now();
             result.timings = {
-                parse: 1e-3 * (timings.compress - timings.parse),
+                parse: 1e-3 * (timings.rename - timings.parse),
+                rename: 1e-3 * (timings.compress - timings.rename),
                 compress: 1e-3 * (timings.scope - timings.compress),
                 scope: 1e-3 * (timings.mangle - timings.scope),
                 mangle: 1e-3 * (timings.properties - timings.mangle),
diff --git a/lib/scope.js b/lib/scope.js
index 0d2a7aeb..ea35c0bf 100644
--- a/lib/scope.js
+++ b/lib/scope.js
@@ -43,7 +43,7 @@
 
 "use strict";
 
-function SymbolDef(scope, index, orig) {
+function SymbolDef(scope, orig) {
     this.name = orig.name;
     this.orig = [ orig ];
     this.eliminated = 0;
@@ -53,7 +53,6 @@ function SymbolDef(scope, index, orig) {
     this.global = false;
     this.mangled_name = null;
     this.undeclared = false;
-    this.index = index;
     this.id = SymbolDef.next_id++;
 };
 
@@ -253,7 +252,7 @@ AST_Toplevel.DEFMETHOD("def_global", function(node){
     if (globals.has(name)) {
         return globals.get(name);
     } else {
-        var g = new SymbolDef(this, globals.size(), node);
+        var g = new SymbolDef(this, node);
         g.undeclared = true;
         g.global = true;
         globals.set(name, g);
@@ -314,7 +313,7 @@ AST_Scope.DEFMETHOD("def_function", function(symbol){
 AST_Scope.DEFMETHOD("def_variable", function(symbol){
     var def;
     if (!this.variables.has(symbol.name)) {
-        def = new SymbolDef(this, this.variables.size(), symbol);
+        def = new SymbolDef(this, symbol);
         this.variables.set(symbol.name, def);
         def.global = !this.parent_scope;
     } else {
@@ -332,7 +331,7 @@ AST_Scope.DEFMETHOD("next_mangled", function(options){
 
         // https://github.com/mishoo/UglifyJS2/issues/242 -- do not
         // shadow a name reserved from mangling.
-        if (options.reserved.indexOf(m) >= 0) continue;
+        if (member(m, options.reserved)) continue;
 
         // we must ensure that the mangled name does not shadow a name
         // from some parent scope that is referenced in this or in
@@ -384,7 +383,7 @@ AST_Symbol.DEFMETHOD("global", function(){
     return this.definition().global;
 });
 
-AST_Toplevel.DEFMETHOD("_default_mangler_options", function(options){
+AST_Toplevel.DEFMETHOD("_default_mangler_options", function(options) {
     options = defaults(options, {
         eval        : false,
         ie8         : false,
@@ -393,15 +392,14 @@ AST_Toplevel.DEFMETHOD("_default_mangler_options", function(options){
         toplevel    : false,
     });
     if (!Array.isArray(options.reserved)) options.reserved = [];
+    // Never mangle arguments
+    push_uniq(options.reserved, "arguments");
     return options;
 });
 
 AST_Toplevel.DEFMETHOD("mangle_names", function(options){
     options = this._default_mangler_options(options);
 
-    // Never mangle arguments
-    options.reserved.push('arguments');
-
     // We only need to mangle declaration nodes.  Special logic wired
     // into the code generator will display the mangled name if it's
     // present (and for AST_SymbolRef-s it'll use the mangled name of
@@ -410,11 +408,7 @@ AST_Toplevel.DEFMETHOD("mangle_names", function(options){
     var to_mangle = [];
 
     if (options.cache) {
-        this.globals.each(function(symbol){
-            if (options.reserved.indexOf(symbol.name) < 0) {
-                to_mangle.push(symbol);
-            }
-        });
+        this.globals.each(collect);
     }
 
     var tw = new TreeWalker(function(node, descend){
@@ -426,13 +420,7 @@ AST_Toplevel.DEFMETHOD("mangle_names", function(options){
             return true;        // don't descend again in TreeWalker
         }
         if (node instanceof AST_Scope) {
-            var p = tw.parent(), a = [];
-            node.variables.each(function(symbol){
-                if (options.reserved.indexOf(symbol.name) < 0) {
-                    a.push(symbol);
-                }
-            });
-            to_mangle.push.apply(to_mangle, a);
+            node.variables.each(collect);
             return;
         }
         if (node instanceof AST_Label) {
@@ -452,6 +440,71 @@ AST_Toplevel.DEFMETHOD("mangle_names", function(options){
     if (options.cache) {
         options.cache.cname = this.cname;
     }
+
+    function collect(symbol) {
+        if (!member(symbol.name, options.reserved)) {
+            to_mangle.push(symbol);
+        }
+    }
+});
+
+AST_Toplevel.DEFMETHOD("find_unique_prefix", function(options) {
+    var letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$_";
+    var cache = options.cache && options.cache.props;
+    var prefixes = Object.create(null);
+    options.reserved.forEach(add_prefix);
+    this.globals.each(add_def);
+    this.walk(new TreeWalker(function(node) {
+        if (node instanceof AST_Scope) node.variables.each(add_def);
+    }));
+    var prefix, i = 0;
+    do {
+        prefix = create_name(i++);
+    } while (prefixes[prefix]);
+    return prefix;
+
+    function add_prefix(name) {
+        if (/[0-9]$/.test(name)) {
+            prefixes[name.replace(/[0-9]+$/, "")] = true;
+        }
+    }
+
+    function add_def(def) {
+        var name = def.name;
+        if (def.global && cache && cache.has(name)) name = cache.get(name);
+        else if (!def.unmangleable(options)) return;
+        add_prefix(name);
+    }
+
+    function create_name(num) {
+        var name = "";
+        do {
+            name += letters[num % letters.length];
+            num = Math.floor(num / letters.length);
+        } while (num);
+        return name;
+    }
+});
+
+AST_Toplevel.DEFMETHOD("expand_names", function(options) {
+    options = this._default_mangler_options(options);
+    var prefix = this.find_unique_prefix(options);
+    this.globals.each(rename);
+    this.walk(new TreeWalker(function(node) {
+        if (node instanceof AST_Scope) node.variables.each(rename);
+    }));
+
+    function rename(def) {
+        if (def.global || def.unmangleable(options)) return;
+        if (member(def.name, options.reserved)) return;
+        var name = prefix + def.id;
+        def.orig.forEach(function(sym) {
+            sym.name = name;
+        });
+        def.references.forEach(function(sym) {
+            sym.name = name;
+        });
+    }
 });
 
 AST_Toplevel.DEFMETHOD("compute_char_frequency", function(options){