tests/gnu-maintenance.scm


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

;;; GNU Guix --- Functional package management for GNU
;;; Copyright © 2015, 2021 Ludovic Courtès <ludo@gnu.org>
;;; Copyright © 2022 Maxime Devos <maximedevos@telenet.be>
;;;
;;; This file is part of GNU Guix.
;;;
;;; GNU Guix is free software; you can redistribute it and/or modify it
;;; under the terms of the GNU General Public License as published by
;;; the Free Software Foundation; either version 3 of the License, or (at
;;; your option) any later version.
;;;
;;; GNU Guix is distributed in the hope that it will be useful, but
;;; WITHOUT ANY WARRANTY; without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;;; GNU General Public License for more details.
;;;
;;; You should have received a copy of the GNU General Public License
;;; along with GNU Guix.  If not, see <http://www.gnu.org/licenses/>.

(define-module (test-gnu-maintenance)
  #:use-module (guix gnu-maintenance)
  #:use-module (guix tests)
  #:use-module (guix tests http)
  #:use-module (guix upstream)
  #:use-module (guix utils)
  #:use-module (srfi srfi-1)
  #:use-module (srfi srfi-64)
  #:use-module (ice-9 match))

(test-begin "gnu-maintenance")

(test-assert "release-file?"
  (and (every (lambda (project+file)
                (apply release-file? project+file))
              '(("gcc" "gcc-5.3.0.tar.bz2")
                ("texmacs" "TeXmacs-1.0.7.9-src.tar.gz")
                ("icecat" "icecat-38.4.0-gnu1.tar.bz2")
                ("mit-scheme" "mit-scheme-9.2.tar.gz")
                ("mediainfo" "mediainfo_20.09.tar.xz")
                ("exiv2" "exiv2-0.27.3-Source.tar.gz")
                ("mpg321" "mpg321_0.3.2.orig.tar.gz")
                ("bvi" "bvi-1.4.1.src.tar.gz")
                ("hostscope" "hostscope-V2.1.tgz")))
       (every (lambda (project+file)
                (not (apply release-file? project+file)))
              '(("guile" "guile-www-1.1.1.tar.gz")
                ("guile" "guile-2.0.11.tar.gz.sig")
                ("mit-scheme" "mit-scheme-9.2-i386.tar.gz")
                ("mit-scheme" "mit-scheme-9.2-doc-pdf.tar.gz")
                ("gnutls" "gnutls-3.2.18-w32.zip")))))

(test-assert "tarball->version"
  (let ((tarball->version (@@ (guix gnu-maintenance) tarball->version)))
    (every (match-lambda
             ((file version)
              (equal? (tarball->version file) version)))
           '(("coreutils-8.32.tar.gz" "8.32")
             ("mediainfo_20.09.tar.xz" "20.09")
             ("exiv2-0.27.3-Source.tar.gz" "0.27.3")
             ("mpg321_0.3.2.orig.tar.gz" "0.3.2")
             ("bvi-1.4.1.src.tar.gz" "1.4.1")))))

(test-assert "latest-html-release, scheme-less URIs"
  (with-http-server
      `((200 "<html xmlns=\"http://www.w3.org/1999/xhtml\">
<head>
<title>Releases (on another domain)!</title>
</head>
<body
<a href=\"//another-site/foo-2.tar.gz\">version 1</a>
</body>
</html>"))
    (let ()
      (define package
        (dummy-package "foo"
          (source
           (dummy-origin
            (uri (string-append (%local-url) "/foo-1.tar.gz"))))
          (properties
           `((release-monitoring-url . ,(%local-url))))))
      (define update ((upstream-updater-latest %generic-html-updater) package))
      (define expected-new-url "http://another-site/foo-2.tar.gz")
      (and (pk 'u update)
           (equal? (upstream-source-version update) "2")
           (equal? (list expected-new-url) (upstream-source-urls update))))))

(test-assert "latest-html-release, no signature"
  (with-http-server
      `((200 "<html xmlns=\"http://www.w3.org/1999/xhtml\">
<head>
<title>Releases!</title>
</head>
<body>
<a href=\"bar/foo-1.tar.gz\">version 1</a>
<a href=\"bar/foo-2.tar.gz\">version 2</a>
</body>
</html>"))
    (let ()
      (define package
        (dummy-package "foo"
          (source
           (dummy-origin
            (uri (string-append (%local-url) "/foo-1.tar.gz"))))
          (properties
           `((release-monitoring-url . ,(%local-url))))))
      (define update ((upstream-updater-latest %generic-html-updater) package))
      (define expected-new-url
        (string-append (%local-url) "/foo-2.tar.gz"))
      (and (pk 'u update)
           (equal? (upstream-source-version update) "2")
           (equal? (list expected-new-url)
                   (upstream-source-urls update))
           (null? ;; both #false and the empty list are acceptable
            (or (upstream-source-signature-urls update) '()))))))

(test-assert "latest-html-release, signature"
  (with-http-server
      `((200 "<html xmlns=\"http://www.w3.org/1999/xhtml\">
<head>
<title>Signed releases!</title>
</head>
<body>
<a href=\"bar/foo-1.tar.gz\">version 1</a>
<a href=\"bar/foo-2.tar.gz\">version 2</a>
<a href=\"bar/foo-1.tar.gz.sig\">version 1 signature</a>
<a href=\"bar/foo-2.tar.gz.sig\">version 2 signature</a>
</body>
</html>"))
    (let ()
      (define package
        (dummy-package "foo"
          (source
           (dummy-origin
            (uri (string-append (%local-url) "/foo-1.tar.gz"))))
          (properties
           `((release-monitoring-url . ,(%local-url))))))
      (define update ((upstream-updater-latest %generic-html-updater) package))
      (define expected-new-url
        (string-append (%local-url) "/foo-2.tar.gz"))
      (define expected-signature-url
        (string-append (%local-url) "/foo-2.tar.gz.sig"))
      (and (pk 'u update)
           (equal? (upstream-source-version update) "2")
           (equal? (list expected-new-url)
                   (upstream-source-urls update))
           (equal? (list expected-signature-url)
                   (upstream-source-signature-urls update))))))

(test-end)
var crypto = require("crypto");
var U = require("..");
var List = U.List;
var os = require("os");
var sandbox = require("./sandbox");

// Reduce a 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 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.  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.

Error.stackTraceLimit = Infinity;
module.exports = function reduce_test(testcase, minify_options, reduce_options) {
    minify_options = minify_options || {};
    reduce_options = reduce_options || {};
    var print_options = {};
    [
        "ie8",
        "v8",
        "webkit",
    ].forEach(function(name) {
        var value = minify_options[name] || minify_options.output && minify_options.output[name];
        if (value) print_options[name] = value;
    });
    if (testcase instanceof U.AST_Node) testcase = testcase.print_to_string(print_options);
    var max_iterations = reduce_options.max_iterations || 1000;
    var max_timeout = reduce_options.max_timeout || 10000;
    var warnings = [];
    var log = reduce_options.log || function(msg) {
        warnings.push(msg);
    };
    var verbose = reduce_options.verbose;
    var minify_options_json = JSON.stringify(minify_options, null, 2);
    var result_cache = Object.create(null);
    var test_for_diff = compare_run_code;
    // the initial timeout to assess the viability of the test case must be large
    var differs = test_for_diff(testcase, minify_options, result_cache, max_timeout);

    if (verbose) {
        log("// Node.js " + process.version + " on " + os.platform() + " " + os.arch());
    }
    if (differs.error && [ "DefaultsError", "SyntaxError" ].indexOf(differs.error.name) < 0) {
        test_for_diff = test_minify;
        differs = test_for_diff(testcase, minify_options, result_cache, max_timeout);
    }
    if (!differs) {
        // same stdout result produced when minified
        return {
            code: [
                "// Can't reproduce test failure",
                "// minify options: " + to_comment(minify_options_json)
            ].join("\n"),
            warnings: warnings,
        };
    } else if (differs.timed_out) {
        return {
            code: [
                "// Can't reproduce test failure within " + max_timeout + "ms",
                "// minify options: " + to_comment(minify_options_json)
            ].join("\n"),
            warnings: warnings,
        };
    } else if (differs.error) {
        differs.warnings = warnings;
        return differs;
    } else if (sandbox.is_error(differs.unminified_result)
        && sandbox.is_error(differs.minified_result)
        && differs.unminified_result.name == differs.minified_result.name) {
        return {
            code: [
                "// No differences except in error message",
                "// minify options: " + to_comment(minify_options_json)
            ].join("\n"),
            warnings: warnings,
        };
    } else {
        max_timeout = Math.min(100 * differs.elapsed, max_timeout);
        // 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_Accessor) return;
            if (node instanceof U.AST_Directive) return;
            if (!in_list && node instanceof U.AST_EmptyStatement) return;
            if (node instanceof U.AST_Label) return;
            if (node instanceof U.AST_LabelRef) return;
            if (node instanceof U.AST_Toplevel) return;
            var parent = tt.parent();
            if (node instanceof U.AST_SymbolFunarg && parent instanceof U.AST_Accessor) return;
            if (!in_list && parent.rest !== node && node instanceof U.AST_SymbolDeclaration) 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;

            // ignore lvalues
            if (parent instanceof U.AST_Assign && parent.left === node) return;
            if (parent instanceof U.AST_DefaultValue && parent.name === node) return;
            if (parent instanceof U.AST_DestructuredKeyVal && parent.value === node) return;
            if (parent instanceof U.AST_Unary && parent.expression === node) switch (parent.operator) {
              case "++":
              case "--":
              case "delete":
                return;
            }
            if (parent instanceof U.AST_VarDef && parent.name === node) return;
            // preserve for (var xxx; ...)
            if (parent instanceof U.AST_For && parent.init === node && node instanceof U.AST_Definitions) return node;
            // preserve for (xxx in/of ...)
            if (parent instanceof U.AST_ForEnumeration && parent.init === node) return node;

            // node specific permutations with no parent logic

            if (node instanceof U.AST_Array) {
                var expr = node.elements[0];
                if (expr && !(expr instanceof U.AST_Hole)) {
                    node.start._permute++;
                    CHANGED = true;
                    return expr instanceof U.AST_Spread ? expr.expression : expr;
                }
            }
            else if (node instanceof U.AST_Binary) {
                var permute = ((node.start._permute += step) * steps | 0) % 4;
                var expr = [
                    node.left,
                    node.right,
                ][ permute & 1 ];
                if (expr instanceof U.AST_Destructured) expr = expr.transform(new U.TreeTransformer(function(node, descend) {
                    if (node instanceof U.AST_DefaultValue) return new U.AST_Assign({
                        operator: "=",
                        left: node.name.transform(this),
                        right: node.value,
                        start: {},
                    });
                    if (node instanceof U.AST_DestructuredKeyVal) return new U.AST_ObjectKeyVal(node);
                    if (node instanceof U.AST_Destructured) {
                        node = new (node instanceof U.AST_DestructuredArray ? U.AST_Array : U.AST_Object)(node);
                        descend(node, this);
                    }
                    return node;
                }));
                CHANGED = true;
                return permute < 2 ? expr : wrap_with_console_log(expr);
            }
            else if (node instanceof U.AST_BlockStatement) {
                if (in_list && node.body.filter(function(node) {
                    return node instanceof U.AST_Const;
                }).length == 0) {
                    node.start._permute++;
                    CHANGED = true;
                    return List.splice(node.body);
                }
            }
            else if (node instanceof U.AST_Call) {
                var expr = [
                    !(node.expression instanceof U.AST_Super) && node.expression,
                    node.args[0],
                    null,  // intentional
                ][ ((node.start._permute += step) * steps | 0) % 3 ];
                if (expr) {
                    CHANGED = true;
                    return expr instanceof U.AST_Spread ? expr.expression : expr;
                }
                if (node.expression instanceof U.AST_Arrow && node.expression.value) {
                    var seq = node.args.slice();
                    seq.push(node.expression.value);
                    CHANGED = true;
                    return to_sequence(seq);
                }
                if (node.expression instanceof U.AST_Function) {
                    // hoist and return expressions from the IIFE function expression
                    var body = node.expression.body;
                    node.expression.body = [];
                    var seq = [];
                    body.forEach(function(node) {
                        var expr = expr instanceof U.AST_Exit ? node.value : node.body;
                        if (expr instanceof U.AST_Node && !U.is_statement(expr)) {
                            // collect expressions from each statements' body
                            seq.push(expr);
                        }
                    });
                    CHANGED = true;
                    return to_sequence(seq);
                }
            }
            else if (node instanceof U.AST_Catch) {
                // drop catch 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_DefaultValue) {
                node.start._permute++;
                CHANGED = true;
                return node.name;
            }
            else if (node instanceof U.AST_DestructuredArray) {
                var expr = node.elements[0];
                if (expr && !(expr instanceof U.AST_Hole)) {
                    node.start._permute++;
                    CHANGED = true;
                    return expr;
                }
            }
            else if (node instanceof U.AST_DestructuredObject) {
                // first property's value
                var expr = node.properties[0];
                if (expr) {
                    node.start._permute++;
                    CHANGED = true;
                    return expr.value;
                }
            }
            else if (node instanceof U.AST_Defun) {
                switch (((node.start._permute += step) * steps | 0) % 2) {
                  case 0:
                    CHANGED = true;
                    return List.skip;
                  default:
                    if (!has_exit(node)) {
                        // hoist function declaration body
                        var body = node.body;
                        node.body = [];
                        body.push(node); // retain function with empty body to be dropped later
                        CHANGED = true;
                        return List.splice(body);
                    }
                }
            }
            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 List.skip;
                        }
                        expr = node.condition; // AST_While - fall through
                    }
                }
                if (expr && (expr !== node.body || !has_loopcontrol(expr, node, parent))) {
                    CHANGED = true;
                    return to_statement(expr);
                }
            }
            else if (node instanceof U.AST_Finally) {
                // drop finally block
                node.start._permute++;
                CHANGED = true;
                return null;
            }
            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 && (expr !== node.body || !has_loopcontrol(expr, node, parent))) {
                    CHANGED = true;
                    return to_statement_init(expr);
                }
            }
            else if (node instanceof U.AST_ForEnumeration) {
                var expr;
                switch ((node.start._permute * steps | 0) % 3) {
                  case 0:
                    if (!(node.init instanceof U.AST_Definitions
                        && node.init.definitions[0].name instanceof U.AST_Destructured)) {
                        expr = node.init;
                    }
                    break;
                  case 1:
                    expr = node.object;
                    break;
                  case 2:
                    if (!has_loopcontrol(node.body, node, parent)) expr = node.body;
                    break;
                }
                node.start._permute += step;
                if (expr) {
                    CHANGED = true;
                    return to_statement_init(expr);
                }
            }
            else if (node instanceof U.AST_If) {
                var expr = [
                    node.condition,
                    node.body,
                    node.alternative,
                ][ (node.start._permute * steps | 0) % 3 ];
                node.start._permute += step;
                if (expr) {
                    // replace if statement with its condition, then block or else block
                    CHANGED = true;
                    return to_statement(expr);
                }
            }
            else if (node instanceof U.AST_Object) {
                // first property's value
                var expr = node.properties[0];
                if (expr instanceof U.AST_ObjectKeyVal) {
                    expr = expr.value;
                } else if (expr instanceof U.AST_Spread) {
                    expr = expr.expression;
                } else if (expr && expr.key instanceof U.AST_Node) {
                    expr = expr.key;
                } else {
                    expr = null;
                }
                if (expr) {
                    node.start._permute++;
                    CHANGED = true;
                    return expr;
                }
            }
            else if (node instanceof U.AST_PropAccess) {
                var expr = [
                    !(node.expression instanceof U.AST_Super) && node.expression,
                    node.property instanceof U.AST_Node && !(parent instanceof U.AST_Destructured) && node.property,
                ][ node.start._permute++ % 2 ];
                if (expr) {
                    CHANGED = true;
                    return expr;
                }
            }
            else if (node instanceof U.AST_SimpleStatement) {
                if (node.body instanceof U.AST_Call && node.body.expression instanceof U.AST_Function) {
                    // hoist simple statement IIFE function expression body
                    node.start._permute++;
                    if (!has_exit(node.body.expression)) {
                        var body = node.body.expression.body;
                        node.body.expression.body = [];
                        CHANGED = true;
                        return List.splice(body);
                    }
                }
            }
            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],            // first case body or undefined
                ][ (node.start._permute * steps | 0) % 4 ];
                node.start._permute += step;
                if (expr && (!(expr instanceof U.AST_Statement) || !has_loopcontrol(expr, node, parent))) {
                    CHANGED = true;
                    return expr instanceof U.AST_SwitchBranch ? new U.AST_BlockStatement({
                        body: expr.body.slice(),
                        start: {},
                    }) : to_statement(expr);
                }
            }
            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;
            }
            else if (node instanceof U.AST_Var) {
                if (node.definitions.length == 1 && node.definitions[0].value) {
                    // first declaration value
                    node.start._permute++;
                    CHANGED = true;
                    return to_statement(node.definitions[0].value);
                }
            }
            else if (node instanceof U.AST_LabeledStatement) {
                if (node.body instanceof U.AST_Statement
                    && !has_loopcontrol(node.body, node.body, node)) {
                    // replace labelled statement with its non-labelled body
                    node.start._permute = REPLACEMENTS.length;
                    CHANGED = true;
                    return node.body;
                }
            }

            if (in_list) {
                // drop switch branches
                if (parent instanceof U.AST_Switch && parent.expression != node) {
                    node.start._permute++;
                    CHANGED = true;
                    return List.skip;
                }

                // replace or skip statement
                if (node instanceof U.AST_Statement) {
                    node.start._permute++;
                    CHANGED = true;
                    return List.skip;
                }

                // remove this node unless its the sole element of a (transient) sequence
                if (!(parent instanceof U.AST_Sequence) || parent.expressions.length > 1) {
                    node.start._permute++;
                    CHANGED = true;
                    return List.skip;
                }
            } else if (parent.rest === node) {
                node.start._permute++;
                CHANGED = true;
                return null;
            }

            // replace this node
            var newNode = U.is_statement(node) ? new U.AST_EmptyStatement({
                start: {},
            }) : U.parse(REPLACEMENTS[node.start._permute % REPLACEMENTS.length | 0], {
                expression: true,
            });
            newNode.start._permute = ++node.start._permute;
            CHANGED = true;
            return newNode;
        }, function(node, in_list) {
            if (node instanceof U.AST_Sequence) {
                // expand single-element sequence
                if (node.expressions.length == 1) return node.expressions[0];
            }
            else if (node instanceof U.AST_Try) {
                // expand orphaned try block
                if (!node.bcatch && !node.bfinally) return new U.AST_BlockStatement({
                    body: node.body,
                    start: {},
                });
            }
            else if (node instanceof U.AST_Definitions) {
                // remove empty var statement
                if (node.definitions.length == 0) return in_list ? List.skip : new U.AST_EmptyStatement({
                    start: {},
                });
            }
        });

        var diff_error_message;
        for (var pass = 1; pass <= 3; ++pass) {
            var testcase_ast = U.parse(testcase);
            if (diff_error_message === testcase) {
                // only difference detected is in error message, so expose that and try again
                testcase_ast.transform(new U.TreeTransformer(function(node, descend) {
                    if (node.TYPE == "Call" && node.expression.print_to_string() == "console.log") {
                        return to_sequence(node.args);
                    }
                    if (node instanceof U.AST_Catch && node.argname instanceof U.AST_SymbolCatch) {
                        descend(node, this);
                        node.body.unshift(new U.AST_SimpleStatement({
                            body: wrap_with_console_log(new U.AST_SymbolRef(node.argname)),
                            start: {},
                        }));
                        return node;
                    }
                }));
                var code = testcase_ast.print_to_string(print_options);
                var diff = test_for_diff(code, minify_options, result_cache, max_timeout);
                if (diff && !diff.timed_out && !diff.error) {
                    testcase = code;
                    differs = diff;
                } else {
                    testcase_ast = U.parse(testcase);
                }
            }
            diff_error_message = null;
            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;
            }));
            var before_iterations = testcase;
            for (var c = 0; c < max_iterations; ++c) {
                if (verbose && pass == 1 && c % 25 == 0) {
                    log("// 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(print_options);
                } catch (ex) {
                    // AST is not well formed.
                    // no harm done - just log the error, ignore latest change and continue iterating.
                    log("*** Error generating code from AST.");
                    log(ex.stack);
                    log("*** Discarding permutation and continuing.");
                    continue;
                }
                var diff = test_for_diff(code, minify_options, result_cache, max_timeout);
                if (diff) {
                    if (diff.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.
                    } else if (diff.error) {
                        // something went wrong during minify() - could be malformed AST or genuine bug.
                        // no harm done - just log code & error, ignore latest change and continue iterating.
                        log("*** Error during minification.");
                        log(code);
                        log(diff.error.stack);
                        log("*** Discarding permutation and continuing.");
                    } else if (sandbox.is_error(diff.unminified_result)
                        && sandbox.is_error(diff.minified_result)
                        && diff.unminified_result.name == diff.minified_result.name) {
                        // ignore difference in error messages caused by minification
                        diff_error_message = testcase;
                    } else {
                        // latest permutation is valid, so use it as the basis of new changes
                        testcase_ast = code_ast;
                        testcase = code;
                        differs = diff;
                    }
                }
            }
            if (before_iterations === testcase) break;
            if (verbose) {
                log("// reduce test pass " + pass + ": " + testcase.length + " bytes");
            }
        }
        var beautified = U.minify(testcase, {
            compress: false,
            mangle: false,
            output: function() {
                var options = JSON.parse(JSON.stringify(print_options));
                options.beautify = true;
                options.braces = true;
                options.comments = true;
                return options;
            }(),
        });
        testcase = {
            code: testcase,
        };
        if (!beautified.error) {
            diff = test_for_diff(beautified.code, minify_options, result_cache, max_timeout);
            if (diff && !diff.timed_out && !diff.error) {
                testcase = beautified;
                testcase.code = "// (beautified)\n" + testcase.code;
                differs = diff;
            }
        }
        var lines = [ "" ];
        if (isNaN(max_timeout)) {
            lines.push("// minify error: " + to_comment(differs.minified_result.stack));
        } else {
            var unminified_result = differs.unminified_result;
            var minified_result = differs.minified_result;
            if (trim_trailing_whitespace(unminified_result) == trim_trailing_whitespace(minified_result)) {
                lines.push(
                    "// (stringified)",
                    "// output: " + JSON.stringify(unminified_result),
                    "// minify: " + JSON.stringify(minified_result)
                );
            } else {
                lines.push(
                    "// output: " + to_comment(unminified_result),
                    "// minify: " + to_comment(minified_result)
                );
            }
        }
        lines.push("// options: " + to_comment(minify_options_json));
        testcase.code += lines.join("\n");
        testcase.warnings = warnings;
        return testcase;
    }
};

function to_comment(value) {
    return ("" + value).replace(/\n/g, "\n// ");
}

function trim_trailing_whitespace(value) {
    return ("" + value).replace(/\s+$/, "");
}

function has_exit(fn) {
    var found = false;
    var tw = new U.TreeWalker(function(node) {
        if (found) return found;
        if (node instanceof U.AST_Exit) {
            return found = true;
        }
        if (node instanceof U.AST_Scope && node !== fn) {
            return true; // don't descend into nested functions
        }
    });
    fn.walk(tw);
    return found;
}

function has_loopcontrol(body, loop, label) {
    var found = false;
    var tw = new U.TreeWalker(function(node) {
        if (found) return true;
        if (node instanceof U.AST_LoopControl && this.loopcontrol_target(node) === loop) {
            return found = true;
        }
    });
    if (label instanceof U.AST_LabeledStatement) tw.push(label);
    tw.push(loop);
    body.walk(tw);
    return found;
}

function is_timed_out(result) {
    return sandbox.is_error(result) && /timed out/.test(result.message);
}

function merge_sequence(array, node) {
    if (node instanceof U.AST_Sequence) {
        array.push.apply(array, node.expressions);
    } else {
        array.push(node);
    }
    return array;
}

function to_sequence(expressions) {
    if (expressions.length == 0) return new U.AST_Number({value: 0, start: {}});
    if (expressions.length == 1) return expressions[0];
    return new U.AST_Sequence({
        expressions: expressions.reduce(merge_sequence, []),
        start: {},
    });
}

function to_statement(node) {
    return U.is_statement(node) ? node : new U.AST_SimpleStatement({
        body: node,
        start: {},
    });
}

function to_statement_init(node) {
    return node instanceof U.AST_Const || node instanceof U.AST_Let ? new U.AST_BlockStatement({
        body: [ node ],
        start: {},
    }) : to_statement(node);;
}

function wrap_with_console_log(node) {
    // wrap with console.log()
    return new U.AST_Call({
        expression: new U.AST_Dot({
            expression: new U.AST_SymbolRef({
                name: "console",
                start: {},
            }),
            property: "log",
            start: {},
        }),
        args: [ node ],
        start: {},
    });
}

function run_code(code, toplevel, result_cache, timeout) {
    var key = crypto.createHash("sha1").update(code).digest("base64");
    var value = result_cache[key];
    if (!value) {
        var start = Date.now();
        result_cache[key] = value = {
            result: sandbox.run_code(code, toplevel, timeout),
            elapsed: Date.now() - start,
        };
    }
    return value;
}

function compare_run_code(code, minify_options, result_cache, max_timeout) {
    var minified = U.minify(code, minify_options);
    if (minified.error) return minified;

    var toplevel = sandbox.has_toplevel(minify_options);
    var unminified = run_code(code, toplevel, result_cache, max_timeout);
    var timeout = Math.min(100 * unminified.elapsed, max_timeout);
    var minified_result = run_code(minified.code, toplevel, result_cache, timeout).result;

    if (sandbox.same_stdout(unminified.result, minified_result)) {
        return is_timed_out(unminified.result) && is_timed_out(minified_result) && {
            timed_out: true,
        };
    }
    return {
        unminified_result: unminified.result,
        minified_result: minified_result,
        elapsed: unminified.elapsed,
    };
}

function test_minify(code, minify_options) {
    var minified = U.minify(code, minify_options);
    return minified.error && {
        minified_result: minified.error,
    };
}