in-place `tigten_body()` (#2111)

By reducing copies of `AST_Node` arrays, we should be able to reduce:
- memory pressure
- potential bugs caused by multiple references in AST
- duplicated executions of `OPT()`

1 files changed, 153 insertions, 164 deletions

diff --git a/lib/compress.js b/lib/compress.js
index a4552e85..3bf54da0 100644
--- a/lib/compress.js
+++ b/lib/compress.js
@@ -668,26 +668,24 @@ merge(Compressor.prototype, {
         var CHANGED, max_iter = 10;
         do {
             CHANGED = false;
-            statements = eliminate_spurious_blocks(statements);
+            eliminate_spurious_blocks(statements);
             if (compressor.option("dead_code")) {
-                statements = eliminate_dead_code(statements, compressor);
+                eliminate_dead_code(statements, compressor);
             }
             if (compressor.option("if_return")) {
-                statements = handle_if_return(statements, compressor);
+                handle_if_return(statements, compressor);
             }
             if (compressor.sequences_limit > 0) {
-                statements = sequencesize(statements, compressor);
+                sequencesize(statements, compressor);
             }
             if (compressor.option("join_vars")) {
-                statements = join_consecutive_vars(statements, compressor);
+                join_consecutive_vars(statements, compressor);
             }
             if (compressor.option("collapse_vars")) {
-                statements = collapse(statements, compressor);
+                collapse(statements, compressor);
             }
         } while (CHANGED && max_iter-- > 0);
 
-        return statements;
-
         // Search from right to left for assignment-like expressions:
         // - `var a = x;`
         // - `a = x;`
@@ -789,7 +787,6 @@ merge(Compressor.prototype, {
                     if (replaced && !remove_candidate(candidate)) statements.splice(stat_index, 1);
                 }
             }
-            return statements;
 
             function extract_candidates(expr) {
                 if (expr instanceof AST_Assign && !expr.left.has_side_effects(compressor)
@@ -891,59 +888,60 @@ merge(Compressor.prototype, {
 
         function eliminate_spurious_blocks(statements) {
             var seen_dirs = [];
-            return statements.reduce(function(a, stat){
+            for (var i = 0; i < statements.length;) {
+                var stat = statements[i];
                 if (stat instanceof AST_BlockStatement) {
                     CHANGED = true;
-                    a.push.apply(a, eliminate_spurious_blocks(stat.body));
+                    eliminate_spurious_blocks(stat.body);
+                    [].splice.apply(statements, [i, 1].concat(stat.body));
+                    i += stat.body.length;
                 } else if (stat instanceof AST_EmptyStatement) {
                     CHANGED = true;
+                    statements.splice(i, 1);
                 } else if (stat instanceof AST_Directive) {
                     if (seen_dirs.indexOf(stat.value) < 0) {
-                        a.push(stat);
+                        i++;
                         seen_dirs.push(stat.value);
                     } else {
                         CHANGED = true;
+                        statements.splice(i, 1);
                     }
-                } else {
-                    a.push(stat);
-                }
-                return a;
-            }, []);
-        };
+                } else i++;
+            }
+        }
 
         function handle_if_return(statements, compressor) {
             var self = compressor.self();
             var multiple_if_returns = has_multiple_if_returns(statements);
             var in_lambda = self instanceof AST_Lambda;
-            var ret = []; // Optimized statements, build from tail to front
-            loop: for (var i = statements.length; --i >= 0;) {
+            for (var i = statements.length; --i >= 0;) {
                 var stat = statements[i];
-                switch (true) {
-                  case (in_lambda && stat instanceof AST_Return && !stat.value && ret.length == 0):
+                var next = statements[i + 1];
+
+                if (in_lambda && stat instanceof AST_Return && !stat.value && !next) {
                     CHANGED = true;
-                    // note, ret.length is probably always zero
-                    // because we drop unreachable code before this
-                    // step.  nevertheless, it's good to check.
-                    continue loop;
-                  case stat instanceof AST_If:
+                    statements.length--;
+                    continue;
+                }
+
+                if (stat instanceof AST_If) {
                     var ab = aborts(stat.body);
                     if (can_merge_flow(ab)) {
                         if (ab.label) {
                             remove(ab.label.thedef.references, ab);
                         }
                         CHANGED = true;
-                        var funs = extract_functions_from_statement_array(ret);
-                        var body = as_statement_array_with_return(stat.body, ab);
                         stat = stat.clone();
                         stat.condition = stat.condition.negate(compressor);
+                        var body = as_statement_array_with_return(stat.body, ab);
                         stat.body = make_node(AST_BlockStatement, stat, {
-                            body: as_statement_array(stat.alternative).concat(ret)
+                            body: as_statement_array(stat.alternative).concat(extract_functions())
                         });
                         stat.alternative = make_node(AST_BlockStatement, stat, {
                             body: body
                         });
-                        ret = [ stat.transform(compressor) ].concat(funs);
-                        continue loop;
+                        statements[i] = stat.transform(compressor);
+                        continue;
                     }
 
                     var ab = aborts(stat.alternative);
@@ -952,81 +950,71 @@ merge(Compressor.prototype, {
                             remove(ab.label.thedef.references, ab);
                         }
                         CHANGED = true;
-                        var funs = extract_functions_from_statement_array(ret);
                         stat = stat.clone();
                         stat.body = make_node(AST_BlockStatement, stat.body, {
-                            body: as_statement_array(stat.body).concat(ret)
+                            body: as_statement_array(stat.body).concat(extract_functions())
                         });
                         var body = as_statement_array_with_return(stat.alternative, ab);
                         stat.alternative = make_node(AST_BlockStatement, stat.alternative, {
                             body: body
                         });
-                        ret = [ stat.transform(compressor) ].concat(funs);
-                        continue loop;
+                        statements[i] = stat.transform(compressor);
+                        continue;
                     }
+                }
 
-                    if (stat.body instanceof AST_Return) {
-                        var value = stat.body.value;
-                        //---
-                        // pretty silly case, but:
-                        // if (foo()) return; return; ==> foo(); return;
-                        if ((in_lambda && ret.length == 0 || ret[0] instanceof AST_Return && !ret[0].value)
-                            && !value && !stat.alternative) {
-                            CHANGED = true;
-                            var cond = make_node(AST_SimpleStatement, stat.condition, {
-                                body: stat.condition
-                            });
-                            ret.unshift(cond);
-                            continue loop;
-                        }
-                        //---
-                        // if (foo()) return x; return y; ==> return foo() ? x : y;
-                        if (ret[0] instanceof AST_Return && value && ret[0].value && !stat.alternative) {
-                            CHANGED = true;
-                            stat = stat.clone();
-                            stat.alternative = ret[0];
-                            ret[0] = stat.transform(compressor);
-                            continue loop;
-                        }
-                        //---
-                        // if (foo()) return x; [ return ; ] ==> return foo() ? x : undefined;
-                        if (multiple_if_returns && (ret.length == 0 || ret[0] instanceof AST_Return)
-                            && value && !stat.alternative && in_lambda) {
-                            CHANGED = true;
-                            stat = stat.clone();
-                            stat.alternative = ret[0] || make_node(AST_Return, stat, {
-                                value: null
-                            });
-                            ret[0] = stat.transform(compressor);
-                            continue loop;
-                        }
-                        //---
-                        // if (a) return b; if (c) return d; e; ==> return a ? b : c ? d : void e;
-                        //
-                        // if sequences is not enabled, this can lead to an endless loop (issue #866).
-                        // however, with sequences on this helps producing slightly better output for
-                        // the example code.
-                        if (compressor.option("sequences")
-                            && i > 0 && statements[i - 1] instanceof AST_If && statements[i - 1].body instanceof AST_Return
-                            && ret.length == 1 && in_lambda && ret[0] instanceof AST_SimpleStatement
-                            && !stat.alternative) {
-                            CHANGED = true;
-                            ret.push(make_node(AST_Return, ret[0], {
-                                value: null
-                            }).transform(compressor));
-                            ret.unshift(stat);
-                            continue loop;
-                        }
+                if (stat instanceof AST_If && stat.body instanceof AST_Return) {
+                    var value = stat.body.value;
+                    //---
+                    // pretty silly case, but:
+                    // if (foo()) return; return; ==> foo(); return;
+                    if (!value && !stat.alternative
+                        && (in_lambda && !next || next instanceof AST_Return && !next.value)) {
+                        CHANGED = true;
+                        statements[i] = make_node(AST_SimpleStatement, stat.condition, {
+                            body: stat.condition
+                        });
+                        continue;
+                    }
+                    //---
+                    // if (foo()) return x; return y; ==> return foo() ? x : y;
+                    if (value && !stat.alternative && next instanceof AST_Return && next.value) {
+                        CHANGED = true;
+                        stat = stat.clone();
+                        stat.alternative = next;
+                        statements.splice(i, 2, stat.transform(compressor));
+                        continue;
+                    }
+                    //---
+                    // if (foo()) return x; [ return ; ] ==> return foo() ? x : undefined;
+                    if (multiple_if_returns && in_lambda && value && !stat.alternative
+                        && (!next || next instanceof AST_Return)) {
+                        CHANGED = true;
+                        stat = stat.clone();
+                        stat.alternative = next || make_node(AST_Return, stat, {
+                            value: null
+                        });
+                        statements.splice(i, next ? 2 : 1, stat.transform(compressor));
+                        continue;
+                    }
+                    //---
+                    // if (a) return b; if (c) return d; e; ==> return a ? b : c ? d : void e;
+                    //
+                    // if sequences is not enabled, this can lead to an endless loop (issue #866).
+                    // however, with sequences on this helps producing slightly better output for
+                    // the example code.
+                    var prev = statements[i - 1];
+                    if (compressor.option("sequences") && in_lambda && !stat.alternative
+                        && prev instanceof AST_If && prev.body instanceof AST_Return
+                        && i + 2 == statements.length && next instanceof AST_SimpleStatement) {
+                        CHANGED = true;
+                        statements.push(make_node(AST_Return, next, {
+                            value: null
+                        }).transform(compressor));
+                        continue;
                     }
-
-                    ret.unshift(stat);
-                    break;
-                  default:
-                    ret.unshift(stat);
-                    break;
                 }
             }
-            return ret;
 
             function has_multiple_if_returns(statements) {
                 var n = 0;
@@ -1051,6 +1039,18 @@ merge(Compressor.prototype, {
                     || ab instanceof AST_Break && lct instanceof AST_BlockStatement && self === lct;
             }
 
+            function extract_functions() {
+                var tail = statements.slice(i + 1);
+                statements.length = i + 1;
+                return tail.filter(function(stat) {
+                    if (stat instanceof AST_Defun) {
+                        statements.push(stat);
+                        return false;
+                    }
+                    return true;
+                });
+            }
+
             function as_statement_array_with_return(node, ab) {
                 var body = as_statement_array(node).slice(0, -1);
                 if (ab.value) {
@@ -1060,49 +1060,52 @@ merge(Compressor.prototype, {
                 }
                 return body;
             }
-        };
+        }
 
         function eliminate_dead_code(statements, compressor) {
-            var has_quit = false;
-            var orig = statements.length;
+            var has_quit;
             var self = compressor.self();
-            statements = statements.reduce(function(a, stat){
-                if (has_quit) {
-                    extract_declarations_from_unreachable_code(compressor, stat, a);
-                } else {
-                    if (stat instanceof AST_LoopControl) {
-                        var lct = compressor.loopcontrol_target(stat);
-                        if ((stat instanceof AST_Break
-                             && !(lct instanceof AST_IterationStatement)
-                             && loop_body(lct) === self) || (stat instanceof AST_Continue
-                                                             && loop_body(lct) === self)) {
-                            if (stat.label) {
-                                remove(stat.label.thedef.references, stat);
-                            }
-                        } else {
-                            a.push(stat);
+            for (var i = 0, n = 0, len = statements.length; i < len; i++) {
+                var stat = statements[i];
+                if (stat instanceof AST_LoopControl) {
+                    var lct = compressor.loopcontrol_target(stat);
+                    if (stat instanceof AST_Break
+                            && !(lct instanceof AST_IterationStatement)
+                            && loop_body(lct) === self
+                        || stat instanceof AST_Continue
+                            && loop_body(lct) === self) {
+                        if (stat.label) {
+                            remove(stat.label.thedef.references, stat);
                         }
                     } else {
-                        a.push(stat);
+                        statements[n++] = stat;
                     }
-                    if (aborts(stat)) has_quit = true;
+                } else {
+                    statements[n++] = stat;
                 }
-                return a;
-            }, []);
-            CHANGED = statements.length != orig;
-            return statements;
-        };
+                if (aborts(stat)) {
+                    has_quit = statements.slice(i + 1);
+                    break;
+                }
+            }
+            statements.length = n;
+            CHANGED = n != len;
+            if (has_quit) has_quit.forEach(function(stat) {
+                extract_declarations_from_unreachable_code(compressor, stat, statements);
+            });
+        }
 
         function sequencesize(statements, compressor) {
-            if (statements.length < 2) return statements;
-            var seq = [], ret = [];
+            if (statements.length < 2) return;
+            var seq = [], n = 0;
             function push_seq() {
                 if (!seq.length) return;
                 var body = make_sequence(seq[0], seq);
-                ret.push(make_node(AST_SimpleStatement, body, { body: body }));
+                statements[n++] = make_node(AST_SimpleStatement, body, { body: body });
                 seq = [];
-            };
-            statements.forEach(function(stat){
+            }
+            for (var i = 0, len = statements.length; i < len; i++) {
+                var stat = statements[i];
                 if (stat instanceof AST_SimpleStatement) {
                     if (seq.length >= compressor.sequences_limit) push_seq();
                     var body = stat.body;
@@ -1110,18 +1113,18 @@ merge(Compressor.prototype, {
                     if (body) merge_sequence(seq, body);
                 } else {
                     push_seq();
-                    ret.push(stat);
+                    statements[n++] = stat;
                 }
-            });
+            }
             push_seq();
-            ret = sequencesize_2(ret, compressor);
-            CHANGED = ret.length != statements.length;
-            return ret;
-        };
+            statements.length = n;
+            sequencesize_2(statements, compressor);
+            CHANGED = statements.length != len;
+        }
 
         function sequencesize_2(statements, compressor) {
             function cons_seq(right) {
-                ret.pop();
+                n--;
                 var left = prev.body;
                 if (!(left instanceof AST_Sequence)) {
                     left = make_node(AST_Sequence, left, {
@@ -1131,8 +1134,9 @@ merge(Compressor.prototype, {
                 merge_sequence(left.expressions, right);
                 return left.transform(compressor);
             };
-            var ret = [], prev = null;
-            statements.forEach(function(stat){
+            var n = 0, prev;
+            for (var i = 0, len = statements.length; i < len; i++) {
+                var stat = statements[i];
                 if (prev) {
                     if (stat instanceof AST_For) {
                         try {
@@ -1145,7 +1149,7 @@ merge(Compressor.prototype, {
                             }
                             else if (!stat.init) {
                                 stat.init = prev.body.drop_side_effect_free(compressor);
-                                ret.pop();
+                                n--;
                             }
                         } catch(ex) {
                             if (ex !== cons_seq) throw ex;
@@ -1167,15 +1171,16 @@ merge(Compressor.prototype, {
                         stat.expression = cons_seq(stat.expression);
                     }
                 }
-                ret.push(stat);
+                statements[n++] = stat;
                 prev = stat instanceof AST_SimpleStatement ? stat : null;
-            });
-            return ret;
-        };
+            }
+            statements.length = n;
+        }
 
         function join_consecutive_vars(statements, compressor) {
-            var prev = null;
-            return statements.reduce(function(a, stat){
+            for (var i = 0, j = -1, len = statements.length; i < len; i++) {
+                var stat = statements[i];
+                var prev = statements[j];
                 if (stat instanceof AST_Definitions && prev && prev.TYPE == stat.TYPE) {
                     prev.definitions = prev.definitions.concat(stat.definitions);
                     CHANGED = true;
@@ -1184,35 +1189,19 @@ merge(Compressor.prototype, {
                          && prev instanceof AST_Var
                          && (!stat.init || stat.init.TYPE == prev.TYPE)) {
                     CHANGED = true;
-                    a.pop();
                     if (stat.init) {
                         stat.init.definitions = prev.definitions.concat(stat.init.definitions);
                     } else {
                         stat.init = prev;
                     }
-                    a.push(stat);
-                    prev = stat;
+                    statements[j] = stat;
                 }
                 else {
-                    prev = stat;
-                    a.push(stat);
+                    statements[++j] = stat;
                 }
-                return a;
-            }, []);
-        };
-
-    };
-
-    function extract_functions_from_statement_array(statements) {
-        var funs = [];
-        for (var i = statements.length - 1; i >= 0; --i) {
-            var stat = statements[i];
-            if (stat instanceof AST_Defun) {
-                statements.splice(i, 1);
-                funs.unshift(stat);
             }
-        }
-        return funs;
+            statements.length = j + 1;
+        };
     }
 
     function extract_declarations_from_unreachable_code(compressor, stat, target) {
@@ -1989,12 +1978,12 @@ merge(Compressor.prototype, {
     });
 
     OPT(AST_Block, function(self, compressor){
-        self.body = tighten_body(self.body, compressor);
+        tighten_body(self.body, compressor);
         return self;
     });
 
     OPT(AST_BlockStatement, function(self, compressor){
-        self.body = tighten_body(self.body, compressor);
+        tighten_body(self.body, compressor);
         switch (self.body.length) {
           case 1: return self.body[0];
           case 0: return make_node(AST_EmptyStatement, self);
@@ -2901,7 +2890,7 @@ merge(Compressor.prototype, {
     });
 
     OPT(AST_Try, function(self, compressor){
-        self.body = tighten_body(self.body, compressor);
+        tighten_body(self.body, compressor);
         if (self.bcatch && self.bfinally && all(self.bfinally.body, is_empty)) self.bfinally = null;
         if (all(self.body, is_empty)) {
             var body = [];