implement CLI `--reduce-test` and reduce tests in ufuzz (#3705)

4 files changed, 410 insertions, 2 deletions

diff --git a/test/exports.js b/test/exports.js
index cb76d7e0..793c9e33 100644
--- a/test/exports.js
+++ b/test/exports.js
@@ -2,6 +2,7 @@ exports["Compressor"] = Compressor;
 exports["defaults"] = defaults;
 exports["JS_Parse_Error"] = JS_Parse_Error;
 exports["mangle_properties"] = mangle_properties;
+exports["MAP"] = MAP;
 exports["minify"] = minify;
 exports["OutputStream"] = OutputStream;
 exports["parse"] = parse;
diff --git a/test/reduce.js b/test/reduce.js
new file mode 100644
index 00000000..c4dc94bf
--- /dev/null
+++ b/test/reduce.js
@@ -0,0 +1,392 @@
+var U = require("./node");
+var MAP = U.MAP;
+var run_code = require("./sandbox").run_code;
+
+// Reduce a ufuzz-style `console.log` based test case by iteratively replacing
+// AST nodes with various permutations. Each AST_Statement in the tree is also
+// speculatively dropped to determine whether it is needed.  If the altered
+// tree and the last known good tree produce the same non-nil error-free output
+// after being run, then the permutation survives to the next generation and
+// is the basis for subsequent iterations.  The test case is reduced as a
+// consequence of complex expressions being replaced with simpler ones.
+// This function assumes that the testcase will not result in a parse or
+// runtime Error.  Note that a reduced test case will have different runtime
+// output - it is not functionally equivalent to the original. The only criteria
+// is that once the generated reduced test case is run without minification, it
+// will produce different output from the code minified with `minify_options`.
+// Returns a `minify` result object with an additonal boolean property `reduced`.
+
+module.exports = function reduce_test(testcase, minify_options, reduce_options) {
+    minify_options = minify_options || { compress: {}, mangle: false };
+    reduce_options = reduce_options || {};
+    var timeout = 1500; // start with a low timeout
+    var max_iterations = reduce_options.max_iterations || 1000;
+    var verbose = reduce_options.verbose;
+    var minify_options_json = JSON.stringify(minify_options);
+    var reduced = false;
+
+    if (testcase instanceof U.AST_Node) testcase = testcase.print_to_string();
+
+    // the initial timeout to assess the viability of the test case must be large
+    if (producesDifferentResultWhenMinified(testcase, minify_options, 5000)) {
+        // Replace expressions with constants that will be parsed into
+        // AST_Nodes as required.  Each AST_Node has its own permutation count,
+        // so these replacements can't be shared.
+        // Although simpler replacements are generally faster and better,
+        // feel free to experiment with a different replacement set.
+        var REPLACEMENTS = [
+            // "null", "''", "false", "'foo'", "undefined", "9",
+            "1", "0",
+        ];
+
+        // There's a relationship between each node's _permute counter and
+        // REPLACEMENTS.length which is why fractional _permutes were needed.
+        // One could scale all _permute operations by a factor of `steps`
+        // to only deal with integer operations, but this works well enough.
+        var steps = 4;        // must be a power of 2
+        var step = 1 / steps; // 0.25 is exactly representable in floating point
+
+        var tt = new U.TreeTransformer(function(node, descend, in_list) {
+            if (CHANGED) return;
+
+            // quick ignores
+            if (node instanceof U.AST_Toplevel) return;
+            if (node instanceof U.AST_Accessor) return;
+            if (node instanceof U.AST_Directive) return;
+            // if (node instanceof U.AST_Var) return;
+            // if (node instanceof U.AST_VarDef) return;
+
+            var parent = tt.parent();
+
+            // ignore call expressions
+            if (parent instanceof U.AST_Call && parent.expression === node) return;
+
+            // ensure that the _permute prop is a number.
+            // can not use `node.start._permute |= 0;` as it will erase fractional part.
+            if (typeof node.start._permute === "undefined") node.start._permute = 0;
+
+            // if node reached permutation limit - skip over it.
+            // no structural AST changes before this point.
+            if (node.start._permute >= REPLACEMENTS.length) return;
+
+            if (parent instanceof U.AST_Assign
+                    && parent.left === node
+                || parent instanceof U.AST_Unary
+                    && parent.expression === node
+                    && ["++", "--", "delete"].indexOf(parent.operator) >= 0) {
+                // ignore lvalues
+                return;
+            }
+            if (parent instanceof U.AST_If && parent.alternative === node) {
+                // retain the if statement and drop its else block
+                node.start._permute++;
+                CHANGED = true;
+                return null;
+            }
+
+            // node specific permutations with no parent logic
+
+            if (node instanceof U.AST_Array) {
+                var expr = node.elements[0];
+                if (expr) {
+                    node.start._permute++;
+                    CHANGED = true;
+                    return expr;
+                }
+            }
+            else if (node instanceof U.AST_Binary) {
+                CHANGED = true;
+                return [
+                    node.left,
+                    node.right,
+                ][ ((node.start._permute += step) * steps | 0) % 2 ];
+            }
+            else if (node instanceof U.AST_Catch || node instanceof U.AST_Finally) {
+                // drop catch or finally block
+                node.start._permute++;
+                CHANGED = true;
+                return null;
+            }
+            else if (node instanceof U.AST_Conditional) {
+                CHANGED = true;
+                return [
+                    node.condition,
+                    node.consequent,
+                    node.alternative,
+                ][ ((node.start._permute += step) * steps | 0) % 3 ];
+            }
+            else if (node instanceof U.AST_BlockStatement) {
+                if (node.body.length === 1) {
+                    node.start._permute++;
+                    CHANGED = true;
+                    return node.body[0];  // each child is an AST_Statement
+                }
+            }
+            else if (node instanceof U.AST_Call) {
+                if (/^console/.test(node.print_to_string())) return node;
+                var expr = [
+                    node.expression,
+                    node.args[0],
+                ][ node.start._permute++ % 2 ];
+                if (expr) {
+                    CHANGED = true;
+                    return expr;
+                }
+            }
+            else if (node instanceof U.AST_DWLoop) {
+                var expr = [
+                    node.condition,
+                    node.body,
+                    null,  // intentional
+                ][ (node.start._permute * steps | 0) % 3 ];
+                node.start._permute += step;
+                if (!expr) {
+                    if (node.body[0] instanceof U.AST_Break) {
+                        if (node instanceof U.AST_Do) {
+                            CHANGED = true;
+                            return MAP.skip;
+                        }
+                        expr = node.condition; // AST_While - fall through
+                    }
+                }
+                if (expr) {
+                    CHANGED = true;
+                    return expr instanceof U.AST_Statement ? expr : new U.AST_SimpleStatement({
+                        body: expr,
+                        start: {},
+                    });
+                }
+            }
+            else if (node instanceof U.AST_PropAccess) {
+                var expr = [
+                    node.expression,
+                    node.property instanceof U.AST_Node && node.property,
+                ][ node.start._permute++ % 2 ];
+                if (expr) {
+                    CHANGED = true;
+                    return expr;
+                }
+            }
+            else if (node instanceof U.AST_For) {
+                var expr = [
+                    node.init,
+                    node.condition,
+                    node.step,
+                    node.body,
+                ][ (node.start._permute * steps | 0) % 4 ];
+                node.start._permute += step;
+                if (expr) {
+                    CHANGED = true;
+                    return expr instanceof U.AST_Statement ? expr : new U.AST_SimpleStatement({
+                        body: expr,
+                        start: {},
+                    });
+                }
+            }
+            else if (node instanceof U.AST_ForIn) {
+                var expr = [
+                    node.init,
+                    node.object,
+                    node.body,
+                ][ (node.start._permute * steps | 0) % 3 ];
+                node.start._permute += step;
+                if (expr) {
+                    CHANGED = true;
+                    return expr instanceof U.AST_Statement ? expr : new U.AST_SimpleStatement({
+                        body: expr,
+                        start: {},
+                    });
+                }
+            }
+            else if (node instanceof U.AST_If) {
+                var body = [
+                    node.body,
+                    node.alternative,
+                ][ (node.start._permute++) % 2 ];
+                if (body) {
+                    // replace if statement with its then block or the else block
+                    CHANGED = true;
+                    return body;
+                }
+            }
+            else if (node instanceof U.AST_Object) {
+                // first property's value
+                var expr = node.properties[0] instanceof U.AST_ObjectKeyVal && node.properties[0].value;
+                if (expr) {
+                    node.start._permute++;
+                    CHANGED = true;
+                    return expr;
+                }
+            }
+            else if (node instanceof U.AST_Switch) {
+                var expr = [
+                    node.expression,                         // switch expression
+                    node.body[0] && node.body[0].expression, // first case expression or undefined
+                    node.body[0] && node.body[0].body[0],    // first case body statement or undefined
+                ][ (node.start._permute * steps | 0) % 3 ];
+                node.start._permute += step;
+                if (expr) {
+                    CHANGED = true;
+                    return expr instanceof U.AST_Statement ? expr : new U.AST_SimpleStatement({
+                        body: expr,
+                        start: {},
+                    });
+                }
+            }
+            else if (node instanceof U.AST_Try) {
+                var body = [
+                    node.body,
+                    node.bcatch && node.bcatch.body,
+                    node.bfinally && node.bfinally.body,
+                    null,  // intentional
+                ][ (node.start._permute * steps | 0) % 4 ];
+                node.start._permute += step;
+                if (body) {
+                    // replace try statement with try block, catch block, or finally block
+                    CHANGED = true;
+                    return new U.AST_BlockStatement({
+                        body: body,
+                        start: {},
+                    });
+                } else {
+                    // replace try with a break or return if first in try statement
+                    if (node.body[0] instanceof U.AST_Break
+                        || node.body[0] instanceof U.AST_Return) {
+                        CHANGED = true;
+                        return node.body[0];
+                    }
+                }
+            }
+            else if (node instanceof U.AST_Unary) {
+                node.start._permute++;
+                CHANGED = true;
+                return node.expression;
+            }
+
+            if (in_list) {
+                // special case to drop object properties and switch branches
+                if (parent instanceof U.AST_Object
+                    || parent instanceof U.AST_Switch && parent.expression != node) {
+                    node.start._permute++;
+                    CHANGED = true;
+                    return MAP.skip;
+                }
+
+                // replace or skip statement
+                if (node instanceof U.AST_Statement) {
+                    if (node instanceof U.AST_BlockStatement
+                        && ( parent instanceof U.AST_IterationStatement
+                            || parent instanceof U.AST_Switch)) {
+                        // don't drop the block of a switch or loop
+                        return;
+                    }
+                    if (node instanceof U.AST_LabeledStatement) {
+                        if (node.body instanceof U.AST_Statement) {
+                            // replace labelled statement with its non-labelled body
+                            node.start._permute = REPLACEMENTS.length;
+                            CHANGED = true;
+                            return node.body;
+                        }
+                    }
+                    node.start._permute++;
+                    CHANGED = true;
+                    return MAP.skip;
+                }
+            }
+
+            // replace or remove this node depending on whether it's in a list
+            var newNode = new U.parse(REPLACEMENTS[node.start._permute % REPLACEMENTS.length | 0], {
+                expression: true,
+            });
+            newNode.start._permute = ++node.start._permute;
+            CHANGED = true;
+            return in_list ? MAP.skip : newNode;
+        });
+
+        for (var pass = 1; pass <= 3; ++pass) {
+            var testcase_ast = U.parse(testcase);
+            testcase_ast.walk(new U.TreeWalker(function(node) {
+                // unshare start props to retain visit data between iterations
+                node.start = JSON.parse(JSON.stringify(node.start));
+                node.start._permute = 0;
+            }));
+            for (var c = 0; c < max_iterations; ++c) {
+                if (verbose) {
+                    if (pass == 1 && c % 25 == 0) {
+                        console.error("// reduce test pass "
+                            + pass + ", iteration " + c + ": " + testcase.length + " bytes");
+                    }
+                }
+                var CHANGED = false;
+                var code_ast = testcase_ast.clone(true).transform(tt);
+                if (!CHANGED) break;
+                try {
+                    var code = code_ast.print_to_string();
+                } catch (ex) {
+                    // AST is not well formed.
+                    // no harm done - just log the error, ignore latest change and continue iterating.
+                    console.error("*** Error generating code from AST.");
+                    console.error(ex.stack);
+                    console.error("*** Discarding permutation and continuing.");
+                }
+                if (code) {
+                    var differs = producesDifferentResultWhenMinified(code, minify_options, timeout);
+                    if (differs) {
+                        if (differs.timed_out) {
+                            // can't trust the validity of `code_ast` and `code` when timed out.
+                            // no harm done - just ignore latest change and continue iterating.
+                            if (timeout < 5000) timeout += 100;
+                        } else {
+                            // latest permutation is valid, so use it as the basis of new changes
+                            testcase_ast = code_ast;
+                            testcase = code;
+                            var testcase_unminified_result = differs.unminified_result;
+                            var testcase_minified_result = differs.minified_result;
+                        }
+                    }
+                }
+            }
+            if (c == 0) break;
+            if (verbose) {
+                console.error("// reduce test pass " + pass + ": " + testcase.length + " bytes");
+            }
+        }
+        reduced = true;
+        testcase += "\n// output: " + testcase_unminified_result
+            + "\n// minify: " + testcase_minified_result
+            + "\n// options: " + minify_options_json;
+    } else {
+        // same stdout result produced when minified
+        testcase = "// Can't reproduce test failure with minify options provided:"
+            + "\n// " + minify_options_json;
+    }
+    var result = U.minify(testcase, {
+        compress: false,
+        mangle: false,
+        output: {
+            beautify: true,
+            braces: true,
+            comments: true,
+        }
+    });
+    result.reduced = reduced;
+    return result;
+};
+
+function producesDifferentResultWhenMinified(code, minify_options, timeout) {
+    var toplevel = undefined;
+    var unminified_result = run_code(code, toplevel, timeout);
+    if (/timed out/i.test(unminified_result)) return false;
+    if (/^\s*$|Error/.test(unminified_result)) return false;
+
+    var minified_result = run_code(U.minify(code, minify_options).code, toplevel, timeout);
+    if (/timed out/i.test(minified_result)) return { timed_out: true };
+    if (/^\s*$/.test(minified_result)) return false;
+
+    return unminified_result !== minified_result ? {
+        unminified_result: unminified_result,
+        minified_result: minified_result,
+    } : false;
+}
+
+Error.stackTraceLimit = Infinity;
diff --git a/test/sandbox.js b/test/sandbox.js
index bafd3dba..32599c04 100644
--- a/test/sandbox.js
+++ b/test/sandbox.js
@@ -54,14 +54,15 @@ function createContext() {
     }
 }
 
-exports.run_code = function(code, toplevel) {
+exports.run_code = function(code, toplevel, timeout) {
+    timeout = timeout || 5000;
     var stdout = "";
     var original_write = process.stdout.write;
     process.stdout.write = function(chunk) {
         stdout += chunk;
     };
     try {
-        vm.runInContext(toplevel ? "(function(){" + code + "})()" : code, createContext(), { timeout: 5000 });
+        vm.runInContext(toplevel ? "(function(){" + code + "})()" : code, createContext(), { timeout: timeout });
         return stdout;
     } catch (ex) {
         return ex;
diff --git a/test/ufuzz/index.js b/test/ufuzz/index.js
index 36224667..7032fc3c 100644
--- a/test/ufuzz/index.js
+++ b/test/ufuzz/index.js
@@ -10,6 +10,7 @@ require("../../tools/exit");
 var UglifyJS = require("../..");
 var randomBytes = require("crypto").randomBytes;
 var sandbox = require("../sandbox");
+var reduce_test = require("../reduce");
 
 var MAX_GENERATED_TOPLEVELS_PER_RUN = 1;
 var MAX_GENERATION_RECURSION_DEPTH = 12;
@@ -1051,6 +1052,7 @@ function log_rename(options) {
 }
 
 function log(options) {
+    var options_copy = JSON.parse(options);
     options = JSON.parse(options);
     if (!ok) errorln("\n\n\n\n\n\n!!!!!!!!!!\n\n\n");
     errorln("//=============================================================");
@@ -1069,6 +1071,18 @@ function log(options) {
         errorln(original_result);
         errorln("uglified result:");
         errorln(uglify_result);
+        errorln("//-------------------------------------------------------------");
+        var reduced = reduce_test(original_code, options_copy, {
+            verbose: false,
+        }).code;
+        if (reduced) {
+            errorln();
+            errorln("// reduced test case (output will differ)");
+            errorln();
+            errorln(reduced);
+            errorln();
+            errorln("//-------------------------------------------------------------");
+        }
     } else {
         errorln("// !!! uglify failed !!!");
         errorln(uglify_code);