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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
|
var crypto = require("crypto");
var U = require("..");
var List = U.List;
var os = require("os");
var sandbox = require("./sandbox");
// 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) {
if (testcase instanceof U.AST_Node) testcase = testcase.print_to_string();
minify_options = minify_options || {};
reduce_options = reduce_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);
// the initial timeout to assess the viability of the test case must be large
var differs = producesDifferentResultWhenMinified(result_cache, testcase, minify_options, max_timeout);
if (verbose) {
log("// Node.js " + process.version + " on " + os.platform() + " " + os.arch());
}
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 (is_error(differs.unminified_result)
&& 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 (!in_list && node instanceof U.AST_SymbolDeclaration) return;
if (node instanceof U.AST_Toplevel) return;
var parent = tt.parent();
if (node instanceof U.AST_SymbolFunarg && parent instanceof U.AST_Accessor) 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_For || parent instanceof U.AST_ForIn)
&& parent.init === node && node instanceof U.AST_Var) {
// preserve for (var ...)
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;
}
}
else if (node instanceof U.AST_Binary) {
var permute = ((node.start._permute += step) * steps | 0) % 4;
var expr = [
node.left,
node.right,
][ permute & 1 ];
CHANGED = true;
return permute < 2 ? expr : wrap_with_console_log(expr);
}
else if (node instanceof U.AST_BlockStatement) {
if (in_list) {
node.start._permute++;
CHANGED = true;
return List.splice(node.body);
}
}
else if (node instanceof U.AST_Call) {
var expr = [
node.expression,
node.args[0],
null, // intentional
][ ((node.start._permute += step) * steps | 0) % 3 ];
if (expr) {
CHANGED = true;
return expr;
}
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 && !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_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(expr);
}
}
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 && (expr !== node.body || !has_loopcontrol(expr, node, parent))) {
CHANGED = true;
return to_statement(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] instanceof U.AST_ObjectKeyVal && node.properties[0].value;
if (expr) {
node.start._permute++;
CHANGED = true;
return expr;
}
}
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_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) {
// 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 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;
}
}
// replace this node
var newNode = 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_Var) {
// 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) {
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();
if (diff = producesDifferentResultWhenMinified(result_cache, code, minify_options, max_timeout)) {
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;
}));
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();
} 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 = producesDifferentResultWhenMinified(result_cache, code, minify_options, 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 (is_error(diff.unminified_result)
&& 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 (c == 0) break;
if (verbose) {
log("// reduce test pass " + pass + ": " + testcase.length + " bytes");
}
}
testcase = try_beautify(result_cache, testcase, minify_options, differs.unminified_result, max_timeout);
var lines = [ "" ];
var unminified_result = strip_color_codes(differs.unminified_result);
var minified_result = strip_color_codes(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 strip_color_codes(value) {
return ("" + value).replace(/\u001b\[\d+m/g, "");
}
function to_comment(value) {
return ("" + value).replace(/\n/g, "\n// ");
}
function trim_trailing_whitespace(value) {
return ("" + value).replace(/\s+$/, "");
}
function try_beautify(result_cache, testcase, minify_options, expected, timeout) {
var result = U.minify(testcase, {
compress: false,
mangle: false,
output: {
beautify: true,
braces: true,
comments: true,
},
});
if (result.error) return {
code: testcase,
};
var toplevel = sandbox.has_toplevel(minify_options);
var actual = run_code(result_cache, result.code, toplevel, timeout);
if (!sandbox.same_stdout(expected, actual)) return {
code: testcase,
};
result.code = "// (beautified)\n" + result.code;
return result;
}
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_error(result) {
return typeof result == "object" && typeof result.name == "string" && typeof result.message == "string";
}
function is_timed_out(result) {
return is_error(result) && /timed out/.test(result);
}
function is_statement(node) {
return node instanceof U.AST_Statement && !(node instanceof U.AST_Function);
}
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 is_statement(node) ? node : new U.AST_SimpleStatement({
body: node,
start: {},
});
}
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(result_cache, code, toplevel, timeout) {
var key = crypto.createHash("sha1").update(code).digest("base64");
return result_cache[key] || (result_cache[key] = sandbox.run_code(code, toplevel, timeout));
}
function producesDifferentResultWhenMinified(result_cache, code, minify_options, max_timeout) {
var minified = U.minify(code, minify_options);
if (minified.error) return minified;
var toplevel = sandbox.has_toplevel(minify_options);
var elapsed = Date.now();
var unminified_result = run_code(result_cache, code, toplevel, max_timeout);
elapsed = Date.now() - elapsed;
var timeout = Math.min(100 * elapsed, max_timeout);
var minified_result = run_code(result_cache, minified.code, toplevel, timeout);
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: elapsed,
};
}
Error.stackTraceLimit = Infinity;
|