1 /*
2 * Copyright 2016, The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <random>
18
19 #include <inttypes.h>
20 #include <stdlib.h>
21 #include <stdio.h>
22 #include <string.h>
23 #include <unistd.h>
24
25 #include <sys/time.h>
26
27 namespace {
28
29 /*
30 * Operators.
31 */
32
33 #define EMIT(x) fputs((x)[random0(sizeof(x)/sizeof(const char*))], out_);
34
35 static constexpr const char* kIncDecOps[] = { "++", "--" };
36 static constexpr const char* kIntUnaryOps[] = { "+", "-", "~" };
37 static constexpr const char* kFpUnaryOps[] = { "+", "-" };
38
39 static constexpr const char* kBoolBinOps[] = { "&&", "||", "&", "|", "^" }; // few less common
40 static constexpr const char* kIntBinOps[] = { "+", "-", "*", "/", "%",
41 ">>", ">>>", "<<", "&", "|", "^" };
42 static constexpr const char* kFpBinOps[] = { "+", "-", "*", "/" };
43
44 static constexpr const char* kBoolAssignOps[] = { "=", "&=" , "|=", "^=" }; // few less common
45 static constexpr const char* kIntAssignOps[] = { "=", "+=", "-=", "*=", "/=", "%=",
46 ">>=", ">>>=", "<<=", "&=", "|=", "^=" };
47 static constexpr const char* kFpAssignOps[] = { "=", "+=", "-=", "*=", "/=" };
48
49 static constexpr const char* kBoolRelOps[] = { "==", "!=" };
50 static constexpr const char* kRelOps[] = { "==", "!=", ">", ">=", "<", "<=" };
51
52 /*
53 * Version of JFuzz. Increase this each time changes are made to the program
54 * to preserve the property that a given version of JFuzz yields the same
55 * fuzzed program for a deterministic random seed.
56 */
57 const char* VERSION = "1.2";
58
59 /*
60 * Maximum number of array dimensions, together with corresponding maximum size
61 * within each dimension (to keep memory/runtime requirements roughly the same).
62 */
63 static const uint32_t kMaxDim = 10;
64 static const uint32_t kMaxDimSize[kMaxDim + 1] = { 0, 1000, 32, 10, 6, 4, 3, 3, 2, 2, 2 };
65
66 /**
67 * A class that generates a random program that compiles correctly. The program
68 * is generated using rules that generate various programming constructs. Each rule
69 * has a fixed probability to "fire". Running a generated program yields deterministic
70 * output, making it suited to test various modes of execution (e.g an interpreter vs.
71 * an compiler or two different run times) for divergences.
72 */
73 class JFuzz {
74 public:
JFuzz(FILE * out,uint32_t seed,uint32_t expr_depth,uint32_t stmt_length,uint32_t if_nest,uint32_t loop_nest)75 JFuzz(FILE* out,
76 uint32_t seed,
77 uint32_t expr_depth,
78 uint32_t stmt_length,
79 uint32_t if_nest,
80 uint32_t loop_nest)
81 : out_(out),
82 fuzz_random_engine_(seed),
83 fuzz_seed_(seed),
84 fuzz_expr_depth_(expr_depth),
85 fuzz_stmt_length_(stmt_length),
86 fuzz_if_nest_(if_nest),
87 fuzz_loop_nest_(loop_nest),
88 return_type_(randomType()),
89 array_type_(randomType()),
90 array_dim_(random1(kMaxDim)),
91 array_size_(random1(kMaxDimSize[array_dim_])),
92 indentation_(0),
93 expr_depth_(0),
94 stmt_length_(0),
95 if_nest_(0),
96 loop_nest_(0),
97 switch_nest_(0),
98 do_nest_(0),
99 boolean_local_(0),
100 int_local_(0),
101 long_local_(0),
102 float_local_(0),
103 double_local_(0),
104 in_inner_(false) { }
105
~JFuzz()106 ~JFuzz() { }
107
emitProgram()108 void emitProgram() {
109 emitHeader();
110 emitTestClassWithMain();
111 }
112
113 private:
114 //
115 // Types.
116 //
117
118 // Current type of each expression during generation.
119 enum Type {
120 kBoolean,
121 kInt,
122 kLong,
123 kFloat,
124 kDouble
125 };
126
127 // Test for an integral type.
isInteger(Type tp)128 static bool isInteger(Type tp) {
129 return tp == kInt || tp == kLong;
130 }
131
132 // Test for a floating-point type.
isFP(Type tp)133 static bool isFP(Type tp) {
134 return tp == kFloat || tp == kDouble;
135 }
136
137 // Emit type.
emitType(Type tp) const138 void emitType(Type tp) const {
139 switch (tp) {
140 case kBoolean: fputs("boolean", out_); break;
141 case kInt: fputs("int", out_); break;
142 case kLong: fputs("long", out_); break;
143 case kFloat: fputs("float", out_); break;
144 case kDouble: fputs("double", out_); break;
145 }
146 }
147
148 // Emit type class.
emitTypeClass(Type tp) const149 void emitTypeClass(Type tp) const {
150 switch (tp) {
151 case kBoolean: fputs("Boolean", out_); break;
152 case kInt: fputs("Integer", out_); break;
153 case kLong: fputs("Long", out_); break;
154 case kFloat: fputs("Float", out_); break;
155 case kDouble: fputs("Double", out_); break;
156 }
157 }
158
159 // Return a random type.
randomType()160 Type randomType() {
161 switch (random1(5)) {
162 case 1: return kBoolean;
163 case 2: return kInt;
164 case 3: return kLong;
165 case 4: return kFloat;
166 default: return kDouble;
167 }
168 }
169
170 //
171 // Expressions.
172 //
173
174 // Emit an unary operator (same type in-out).
emitUnaryOp(Type tp)175 void emitUnaryOp(Type tp) {
176 if (tp == kBoolean) {
177 fputc('!', out_);
178 } else if (isInteger(tp)) {
179 EMIT(kIntUnaryOps);
180 } else { // isFP(tp)
181 EMIT(kFpUnaryOps);
182 }
183 }
184
185 // Emit a pre/post-increment/decrement operator (same type in-out).
emitIncDecOp(Type tp)186 void emitIncDecOp(Type tp) {
187 if (tp == kBoolean) {
188 // Not applicable, just leave "as is".
189 } else { // isInteger(tp) || isFP(tp)
190 EMIT(kIncDecOps);
191 }
192 }
193
194 // Emit a binary operator (same type in-out).
emitBinaryOp(Type tp)195 void emitBinaryOp(Type tp) {
196 if (tp == kBoolean) {
197 EMIT(kBoolBinOps);
198 } else if (isInteger(tp)) {
199 EMIT(kIntBinOps);
200 } else { // isFP(tp)
201 EMIT(kFpBinOps);
202 }
203 }
204
205 // Emit an assignment operator (same type in-out).
emitAssignmentOp(Type tp)206 void emitAssignmentOp(Type tp) {
207 if (tp == kBoolean) {
208 EMIT(kBoolAssignOps);
209 } else if (isInteger(tp)) {
210 EMIT(kIntAssignOps);
211 } else { // isFP(tp)
212 EMIT(kFpAssignOps);
213 }
214 }
215
216 // Emit a relational operator (one type in, boolean out).
emitRelationalOp(Type tp)217 void emitRelationalOp(Type tp) {
218 if (tp == kBoolean) {
219 EMIT(kBoolRelOps);
220 } else { // isInteger(tp) || isFP(tp)
221 EMIT(kRelOps);
222 }
223 }
224
225 // Emit a type conversion operator sequence (out type given, new suitable in type picked).
emitTypeConversionOp(Type tp)226 Type emitTypeConversionOp(Type tp) {
227 if (tp == kInt) {
228 switch (random1(5)) {
229 case 1: fputs("(int)", out_); return kLong;
230 case 2: fputs("(int)", out_); return kFloat;
231 case 3: fputs("(int)", out_); return kDouble;
232 // Narrowing-widening.
233 case 4: fputs("(int)(byte)(int)", out_); return kInt;
234 case 5: fputs("(int)(short)(int)", out_); return kInt;
235 }
236 } else if (tp == kLong) {
237 switch (random1(6)) {
238 case 1: /* implicit */ return kInt;
239 case 2: fputs("(long)", out_); return kFloat;
240 case 3: fputs("(long)", out_); return kDouble;
241 // Narrowing-widening.
242 case 4: fputs("(long)(byte)(long)", out_); return kLong;
243 case 5: fputs("(long)(short)(long)", out_); return kLong;
244 case 6: fputs("(long)(int)(long)", out_); return kLong;
245 }
246 } else if (tp == kFloat) {
247 switch (random1(4)) {
248 case 1: fputs("(float)", out_); return kInt;
249 case 2: fputs("(float)", out_); return kLong;
250 case 3: fputs("(float)", out_); return kDouble;
251 // Narrowing-widening.
252 case 4: fputs("(float)(int)(float)", out_); return kFloat;
253 }
254 } else if (tp == kDouble) {
255 switch (random1(5)) {
256 case 1: fputs("(double)", out_); return kInt;
257 case 2: fputs("(double)", out_); return kLong;
258 case 3: fputs("(double)", out_); return kFloat;
259 // Narrowing-widening.
260 case 4: fputs("(double)(int)(double)", out_); return kDouble;
261 case 5: fputs("(double)(float)(double)", out_); return kDouble;
262 }
263 }
264 return tp; // nothing suitable, just keep type
265 }
266
267 // Emit a type conversion (out type given, new suitable in type picked).
emitTypeConversion(Type tp)268 void emitTypeConversion(Type tp) {
269 if (tp == kBoolean) {
270 Type tp = randomType();
271 emitExpression(tp);
272 fputc(' ', out_);
273 emitRelationalOp(tp);
274 fputc(' ', out_);
275 emitExpression(tp);
276 } else {
277 tp = emitTypeConversionOp(tp);
278 fputc(' ', out_);
279 emitExpression(tp);
280 }
281 }
282
283 // Emit an unary intrinsic (out type given, new suitable in type picked).
emitIntrinsic1(Type tp)284 Type emitIntrinsic1(Type tp) {
285 if (tp == kBoolean) {
286 switch (random1(6)) {
287 case 1: fputs("Float.isNaN", out_); return kFloat;
288 case 2: fputs("Float.isFinite", out_); return kFloat;
289 case 3: fputs("Float.isInfinite", out_); return kFloat;
290 case 4: fputs("Double.isNaN", out_); return kDouble;
291 case 5: fputs("Double.isFinite", out_); return kDouble;
292 case 6: fputs("Double.isInfinite", out_); return kDouble;
293 }
294 } else if (isInteger(tp)) {
295 const char* prefix = tp == kLong ? "Long" : "Integer";
296 switch (random1(13)) {
297 case 1: fprintf(out_, "%s.highestOneBit", prefix); break;
298 case 2: fprintf(out_, "%s.lowestOneBit", prefix); break;
299 case 3: fprintf(out_, "%s.numberOfLeadingZeros", prefix); break;
300 case 4: fprintf(out_, "%s.numberOfTrailingZeros", prefix); break;
301 case 5: fprintf(out_, "%s.bitCount", prefix); break;
302 case 6: fprintf(out_, "%s.signum", prefix); break;
303 case 7: fprintf(out_, "%s.reverse", prefix); break;
304 case 8: fprintf(out_, "%s.reverseBytes", prefix); break;
305 case 9: fputs("Math.incrementExact", out_); break;
306 case 10: fputs("Math.decrementExact", out_); break;
307 case 11: fputs("Math.negateExact", out_); break;
308 case 12: fputs("Math.abs", out_); break;
309 case 13: fputs("Math.round", out_);
310 return tp == kLong ? kDouble : kFloat;
311 }
312 } else { // isFP(tp)
313 switch (random1(6)) {
314 case 1: fputs("Math.abs", out_); break;
315 case 2: fputs("Math.ulp", out_); break;
316 case 3: fputs("Math.signum", out_); break;
317 case 4: fputs("Math.nextUp", out_); break;
318 case 5: fputs("Math.nextDown", out_); break;
319 case 6: if (tp == kDouble) {
320 fputs("Double.longBitsToDouble", out_);
321 return kLong;
322 } else {
323 fputs("Float.intBitsToFloat", out_);
324 return kInt;
325 }
326 }
327 }
328 return tp; // same type in-out
329 }
330
331 // Emit a binary intrinsic (out type given, new suitable in type picked).
emitIntrinsic2(Type tp)332 Type emitIntrinsic2(Type tp) {
333 if (tp == kBoolean) {
334 switch (random1(3)) {
335 case 1: fputs("Boolean.logicalAnd", out_); break;
336 case 2: fputs("Boolean.logicalOr", out_); break;
337 case 3: fputs("Boolean.logicalXor", out_); break;
338 }
339 } else if (isInteger(tp)) {
340 const char* prefix = tp == kLong ? "Long" : "Integer";
341 switch (random1(11)) {
342 case 1: fprintf(out_, "%s.compare", prefix); break;
343 case 2: fprintf(out_, "%s.sum", prefix); break;
344 case 3: fprintf(out_, "%s.min", prefix); break;
345 case 4: fprintf(out_, "%s.max", prefix); break;
346 case 5: fputs("Math.min", out_); break;
347 case 6: fputs("Math.max", out_); break;
348 case 7: fputs("Math.floorDiv", out_); break;
349 case 8: fputs("Math.floorMod", out_); break;
350 case 9: fputs("Math.addExact", out_); break;
351 case 10: fputs("Math.subtractExact", out_); break;
352 case 11: fputs("Math.multiplyExact", out_); break;
353 }
354 } else { // isFP(tp)
355 const char* prefix = tp == kDouble ? "Double" : "Float";
356 switch (random1(5)) {
357 case 1: fprintf(out_, "%s.sum", prefix); break;
358 case 2: fprintf(out_, "%s.min", prefix); break;
359 case 3: fprintf(out_, "%s.max", prefix); break;
360 case 4: fputs("Math.min", out_); break;
361 case 5: fputs("Math.max", out_); break;
362 }
363 }
364 return tp; // same type in-out
365 }
366
367 // Emit an intrinsic (out type given, new suitable in type picked).
emitIntrinsic(Type tp)368 void emitIntrinsic(Type tp) {
369 if (random1(2) == 1) {
370 tp = emitIntrinsic1(tp);
371 fputc('(', out_);
372 emitExpression(tp);
373 fputc(')', out_);
374 } else {
375 tp = emitIntrinsic2(tp);
376 fputc('(', out_);
377 emitExpression(tp);
378 fputs(", ", out_);
379 emitExpression(tp);
380 fputc(')', out_);
381 }
382 }
383
384 // Emit a method call (out type given).
emitMethodCall(Type tp)385 void emitMethodCall(Type tp) {
386 if (tp != kBoolean && !in_inner_) {
387 // Accept all numerical types (implicit conversion) and when not
388 // declaring inner classes (to avoid infinite recursion).
389 switch (random1(8)) {
390 case 1: fputs("mA.a()", out_); break;
391 case 2: fputs("mB.a()", out_); break;
392 case 3: fputs("mB.x()", out_); break;
393 case 4: fputs("mBX.x()", out_); break;
394 case 5: fputs("mC.s()", out_); break;
395 case 6: fputs("mC.c()", out_); break;
396 case 7: fputs("mC.x()", out_); break;
397 case 8: fputs("mCX.x()", out_); break;
398 }
399 } else {
400 // Fall back to intrinsic.
401 emitIntrinsic(tp);
402 }
403 }
404
405 // Emit unboxing boxed object.
emitUnbox(Type tp)406 void emitUnbox(Type tp) {
407 fputc('(', out_);
408 emitType(tp);
409 fputs(") new ", out_);
410 emitTypeClass(tp);
411 fputc('(', out_);
412 emitExpression(tp);
413 fputc(')', out_);
414 }
415
416 // Emit miscellaneous constructs.
emitMisc(Type tp)417 void emitMisc(Type tp) {
418 if (tp == kBoolean) {
419 fprintf(out_, "this instanceof %s", in_inner_ ? "X" : "Test");
420 } else if (isInteger(tp)) {
421 const char* prefix = tp == kLong ? "Long" : "Integer";
422 switch (random1(2)) {
423 case 1: fprintf(out_, "%s.MIN_VALUE", prefix); break;
424 case 2: fprintf(out_, "%s.MAX_VALUE", prefix); break;
425 }
426 } else { // isFP(tp)
427 const char* prefix = tp == kDouble ? "Double" : "Float";
428 switch (random1(6)) {
429 case 1: fprintf(out_, "%s.MIN_NORMAL", prefix); break;
430 case 2: fprintf(out_, "%s.MIN_VALUE", prefix); break;
431 case 3: fprintf(out_, "%s.MAX_VALUE", prefix); break;
432 case 4: fprintf(out_, "%s.POSITIVE_INFINITY", prefix); break;
433 case 5: fprintf(out_, "%s.NEGATIVE_INFINITY", prefix); break;
434 case 6: fprintf(out_, "%s.NaN", prefix); break;
435 }
436 }
437 }
438
439 // Adjust local of given type and return adjusted value.
adjustLocal(Type tp,int32_t a)440 uint32_t adjustLocal(Type tp, int32_t a) {
441 switch (tp) {
442 case kBoolean: boolean_local_ += a; return boolean_local_;
443 case kInt: int_local_ += a; return int_local_;
444 case kLong: long_local_ += a; return long_local_;
445 case kFloat: float_local_ += a; return float_local_;
446 default: double_local_ += a; return double_local_;
447 }
448 }
449
450 // Emit an expression that is a strict upper bound for an array index.
emitUpperBound()451 void emitUpperBound() {
452 if (random1(8) == 1) {
453 fputs("mArray.length", out_);
454 } else if (random1(8) == 1) {
455 fprintf(out_, "%u", random1(array_size_)); // random in range
456 } else {
457 fprintf(out_, "%u", array_size_);
458 }
459 }
460
461 // Emit an array index, usually within proper range.
emitArrayIndex()462 void emitArrayIndex() {
463 if (loop_nest_ > 0 && random1(2) == 1) {
464 fprintf(out_, "i%u", random0(loop_nest_));
465 } else if (random1(8) == 1) {
466 fputs("mArray.length - 1", out_);
467 } else {
468 fprintf(out_, "%u", random0(array_size_)); // random in range
469 }
470 // Introduce potential off by one errors with low probability.
471 if (random1(100) == 1) {
472 if (random1(2) == 1) {
473 fputs(" - 1", out_);
474 } else {
475 fputs(" + 1", out_);
476 }
477 }
478 }
479
480 // Emit a literal.
emitLiteral(Type tp)481 void emitLiteral(Type tp) {
482 switch (tp) {
483 case kBoolean: fputs(random1(2) == 1 ? "true" : "false", out_); break;
484 case kInt: fprintf(out_, "%d", random()); break;
485 case kLong: fprintf(out_, "%dL", random()); break;
486 case kFloat: fprintf(out_, "%d.0f", random()); break;
487 case kDouble: fprintf(out_, "%d.0", random()); break;
488 }
489 }
490
491 // Emit array variable, if available.
emitArrayVariable(Type tp)492 bool emitArrayVariable(Type tp) {
493 if (tp == array_type_) {
494 fputs("mArray", out_);
495 for (uint32_t i = 0; i < array_dim_; i++) {
496 fputc('[', out_);
497 emitArrayIndex();
498 fputc(']', out_);
499 }
500 return true;
501 }
502 return false;
503 }
504
505 // Emit a local variable, if available.
emitLocalVariable(Type tp)506 bool emitLocalVariable(Type tp) {
507 uint32_t locals = adjustLocal(tp, 0);
508 if (locals > 0) {
509 uint32_t local = random0(locals);
510 switch (tp) {
511 case kBoolean: fprintf(out_, "lZ%u", local); break;
512 case kInt: fprintf(out_, "lI%u", local); break;
513 case kLong: fprintf(out_, "lJ%u", local); break;
514 case kFloat: fprintf(out_, "lF%u", local); break;
515 case kDouble: fprintf(out_, "lD%u", local); break;
516 }
517 return true;
518 }
519 return false;
520 }
521
522 // Emit a field variable.
emitFieldVariable(Type tp)523 void emitFieldVariable(Type tp) {
524 switch (tp) {
525 case kBoolean:fputs("mZ", out_); break;
526 case kInt: fputs("mI", out_); break;
527 case kLong: fputs("mJ", out_); break;
528 case kFloat: fputs("mF", out_); break;
529 case kDouble: fputs("mD", out_); break;
530 }
531 }
532
533 // Emit a variable.
emitVariable(Type tp)534 void emitVariable(Type tp) {
535 switch (random1(4)) {
536 case 1:
537 if (emitArrayVariable(tp))
538 return;
539 // FALL-THROUGH
540 case 2:
541 if (emitLocalVariable(tp))
542 return;
543 // FALL-THROUGH
544 default:
545 emitFieldVariable(tp);
546 break;
547 }
548 }
549
550 // Emit an expression.
emitExpression(Type tp)551 void emitExpression(Type tp) {
552 // Continuing expression becomes less likely as the depth grows.
553 if (random1(expr_depth_ + 1) > fuzz_expr_depth_) {
554 if (random1(2) == 1) {
555 emitLiteral(tp);
556 } else {
557 emitVariable(tp);
558 }
559 return;
560 }
561
562 expr_depth_++;
563
564 fputc('(', out_);
565 switch (random1(12)) { // favor binary operations
566 case 1:
567 // Unary operator: ~ x
568 emitUnaryOp(tp);
569 fputc(' ', out_);
570 emitExpression(tp);
571 break;
572 case 2:
573 // Pre-increment: ++x
574 emitIncDecOp(tp);
575 emitVariable(tp);
576 break;
577 case 3:
578 // Post-increment: x++
579 emitVariable(tp);
580 emitIncDecOp(tp);
581 break;
582 case 4:
583 // Ternary operator: b ? x : y
584 emitExpression(kBoolean);
585 fputs(" ? ", out_);
586 emitExpression(tp);
587 fputs(" : ", out_);
588 emitExpression(tp);
589 break;
590 case 5:
591 // Type conversion: (float) x
592 emitTypeConversion(tp);
593 break;
594 case 6:
595 // Intrinsic: foo(x)
596 emitIntrinsic(tp);
597 break;
598 case 7:
599 // Method call: mA.a()
600 emitMethodCall(tp);
601 break;
602 case 8:
603 // Emit unboxing boxed value: (int) Integer(x)
604 emitUnbox(tp);
605 break;
606 case 9:
607 // Miscellaneous constructs: a.length
608 emitMisc(tp);
609 break;
610 default:
611 // Binary operator: x + y
612 emitExpression(tp);
613 fputc(' ', out_);
614 emitBinaryOp(tp);
615 fputc(' ', out_);
616 emitExpression(tp);
617 break;
618 }
619 fputc(')', out_);
620
621 --expr_depth_;
622 }
623
624 //
625 // Statements.
626 //
627
628 // Emit current indentation.
emitIndentation() const629 void emitIndentation() const {
630 for (uint32_t i = 0; i < indentation_; i++) {
631 fputc(' ', out_);
632 }
633 }
634
635 // Emit a return statement.
emitReturn(bool mustEmit)636 bool emitReturn(bool mustEmit) {
637 // Only emit when we must, or with low probability inside ifs/loops,
638 // but outside do-while to avoid confusing the may follow status.
639 if (mustEmit || ((if_nest_ + loop_nest_) > 0 && do_nest_ == 0 && random1(10) == 1)) {
640 fputs("return ", out_);
641 emitExpression(return_type_);
642 fputs(";\n", out_);
643 return false;
644 }
645 // Fall back to assignment.
646 return emitAssignment();
647 }
648
649 // Emit a continue statement.
emitContinue()650 bool emitContinue() {
651 // Only emit with low probability inside loops.
652 if (loop_nest_ > 0 && random1(10) == 1) {
653 fputs("continue;\n", out_);
654 return false;
655 }
656 // Fall back to assignment.
657 return emitAssignment();
658 }
659
660 // Emit a break statement.
emitBreak()661 bool emitBreak() {
662 // Only emit with low probability inside loops, but outside switches
663 // to avoid confusing the may follow status.
664 if (loop_nest_ > 0 && switch_nest_ == 0 && random1(10) == 1) {
665 fputs("break;\n", out_);
666 return false;
667 }
668 // Fall back to assignment.
669 return emitAssignment();
670 }
671
672 // Emit a new scope with a local variable declaration statement.
emitScope()673 bool emitScope() {
674 Type tp = randomType();
675 fputs("{\n", out_);
676 indentation_ += 2;
677 emitIndentation();
678 emitType(tp);
679 switch (tp) {
680 case kBoolean: fprintf(out_, " lZ%u = ", boolean_local_); break;
681 case kInt: fprintf(out_, " lI%u = ", int_local_); break;
682 case kLong: fprintf(out_, " lJ%u = ", long_local_); break;
683 case kFloat: fprintf(out_, " lF%u = ", float_local_); break;
684 case kDouble: fprintf(out_, " lD%u = ", double_local_); break;
685 }
686 emitExpression(tp);
687 fputs(";\n", out_);
688
689 adjustLocal(tp, 1); // local now visible
690
691 bool mayFollow = emitStatementList();
692
693 adjustLocal(tp, -1); // local no longer visible
694
695 indentation_ -= 2;
696 emitIndentation();
697 fputs("}\n", out_);
698 return mayFollow;
699 }
700
701 // Emit a for loop.
emitForLoop()702 bool emitForLoop() {
703 // Continuing loop nest becomes less likely as the depth grows.
704 if (random1(loop_nest_ + 1) > fuzz_loop_nest_) {
705 return emitAssignment(); // fall back
706 }
707
708 bool goesUp = random1(2) == 1;
709 fprintf(out_, "for (int i%u = ", loop_nest_);
710 if (goesUp) {
711 fprintf(out_, "0; i%u < ", loop_nest_);
712 emitUpperBound();
713 fprintf(out_, "; i%u++) {\n", loop_nest_);
714 } else {
715 emitUpperBound();
716 fprintf(out_, " - 1; i%d >= 0", loop_nest_);
717 fprintf(out_, "; i%d--) {\n", loop_nest_);
718 }
719
720 ++loop_nest_; // now in loop
721
722 indentation_ += 2;
723 emitStatementList();
724
725 --loop_nest_; // no longer in loop
726
727 indentation_ -= 2;
728 emitIndentation();
729 fprintf(out_, "}\n");
730 return true; // loop-body does not block flow
731 }
732
733 // Emit while or do-while loop.
emitDoLoop()734 bool emitDoLoop() {
735 // Continuing loop nest becomes less likely as the depth grows.
736 if (random1(loop_nest_ + 1) > fuzz_loop_nest_) {
737 return emitAssignment(); // fall back
738 }
739
740 // TODO: remove this
741 // The jack bug b/28862040 prevents generating while/do-while loops because otherwise
742 // we get dozens of reports on the same issue per nightly/ run.
743 if (true) {
744 return emitAssignment();
745 }
746
747 bool isWhile = random1(2) == 1;
748 fputs("{\n", out_);
749 indentation_ += 2;
750 emitIndentation();
751 fprintf(out_, "int i%u = %d;", loop_nest_, isWhile ? -1 : 0);
752 emitIndentation();
753 if (isWhile) {
754 fprintf(out_, "while (++i%u < ", loop_nest_);
755 emitUpperBound();
756 fputs(") {\n", out_);
757 } else {
758 fputs("do {\n", out_);
759 do_nest_++;
760 }
761
762 ++loop_nest_; // now in loop
763
764 indentation_ += 2;
765 emitStatementList();
766
767 --loop_nest_; // no longer in loop
768
769 indentation_ -= 2;
770 emitIndentation();
771 if (isWhile) {
772 fputs("}\n", out_);
773 } else {
774 fprintf(out_, "} while (++i%u < ", loop_nest_);
775 emitUpperBound();
776 fputs(");\n", out_);
777 --do_nest_;
778 }
779 indentation_ -= 2;
780 emitIndentation();
781 fputs("}\n", out_);
782 return true; // loop-body does not block flow
783 }
784
785 // Emit an if statement.
emitIfStmt()786 bool emitIfStmt() {
787 // Continuing if nest becomes less likely as the depth grows.
788 if (random1(if_nest_ + 1) > fuzz_if_nest_) {
789 return emitAssignment(); // fall back
790 }
791
792 fputs("if (", out_);
793 emitExpression(kBoolean);
794 fputs(") {\n", out_);
795
796 ++if_nest_; // now in if
797
798 indentation_ += 2;
799 bool mayFollowTrue = emitStatementList();
800 indentation_ -= 2;
801 emitIndentation();
802 fprintf(out_, "} else {\n");
803 indentation_ += 2;
804 bool mayFollowFalse = emitStatementList();
805
806 --if_nest_; // no longer in if
807
808 indentation_ -= 2;
809 emitIndentation();
810 fprintf(out_, "}\n");
811 return mayFollowTrue || mayFollowFalse;
812 }
813
814 // Emit a switch statement.
emitSwitch()815 bool emitSwitch() {
816 // Continuing if nest becomes less likely as the depth grows.
817 if (random1(if_nest_ + 1) > fuzz_if_nest_) {
818 return emitAssignment(); // fall back
819 }
820
821 bool mayFollow = false;
822 fputs("switch (", out_);
823 emitArrayIndex(); // restrict its range
824 fputs(") {\n", out_);
825
826 ++if_nest_;
827 ++switch_nest_; // now in switch
828
829 indentation_ += 2;
830 for (uint32_t i = 0; i < 2; i++) {
831 emitIndentation();
832 if (i == 0) {
833 fprintf(out_, "case %u: {\n", random0(array_size_));
834 } else {
835 fprintf(out_, "default: {\n");
836 }
837 indentation_ += 2;
838 if (emitStatementList()) {
839 // Must end with break.
840 emitIndentation();
841 fputs("break;\n", out_);
842 mayFollow = true;
843 }
844 indentation_ -= 2;
845 emitIndentation();
846 fputs("}\n", out_);
847 }
848
849 --if_nest_;
850 --switch_nest_; // no longer in switch
851
852 indentation_ -= 2;
853 emitIndentation();
854 fprintf(out_, "}\n");
855 return mayFollow;
856 }
857
858 // Emit an assignment statement.
emitAssignment()859 bool emitAssignment() {
860 Type tp = randomType();
861 emitVariable(tp);
862 fputc(' ', out_);
863 emitAssignmentOp(tp);
864 fputc(' ', out_);
865 emitExpression(tp);
866 fputs(";\n", out_);
867 return true;
868 }
869
870 // Emit a single statement. Returns true if statements may follow.
emitStatement()871 bool emitStatement() {
872 switch (random1(16)) { // favor assignments
873 case 1: return emitReturn(false); break;
874 case 2: return emitContinue(); break;
875 case 3: return emitBreak(); break;
876 case 4: return emitScope(); break;
877 case 5: return emitForLoop(); break;
878 case 6: return emitDoLoop(); break;
879 case 7: return emitIfStmt(); break;
880 case 8: return emitSwitch(); break;
881 default: return emitAssignment(); break;
882 }
883 }
884
885 // Emit a statement list. Returns true if statements may follow.
emitStatementList()886 bool emitStatementList() {
887 while (stmt_length_ < 1000) { // avoid run-away
888 stmt_length_++;
889 emitIndentation();
890 if (!emitStatement()) {
891 return false; // rest would be dead code
892 }
893 // Continuing this list becomes less likely as the total statement list grows.
894 if (random1(stmt_length_) > fuzz_stmt_length_) {
895 break;
896 }
897 }
898 return true;
899 }
900
901 // Emit interface and class declarations.
emitClassDecls()902 void emitClassDecls() {
903 in_inner_ = true;
904 fputs(" private interface X {\n", out_);
905 fputs(" int x();\n", out_);
906 fputs(" }\n\n", out_);
907 fputs(" private class A {\n", out_);
908 fputs(" public int a() {\n", out_);
909 fputs(" return ", out_);
910 emitExpression(kInt);
911 fputs(";\n }\n", out_);
912 fputs(" }\n\n", out_);
913 fputs(" private class B extends A implements X {\n", out_);
914 fputs(" public int a() {\n", out_);
915 fputs(" return super.a() + ", out_);
916 emitExpression(kInt);
917 fputs(";\n }\n", out_);
918 fputs(" public int x() {\n", out_);
919 fputs(" return ", out_);
920 emitExpression(kInt);
921 fputs(";\n }\n", out_);
922 fputs(" }\n\n", out_);
923 fputs(" private static class C implements X {\n", out_);
924 fputs(" public static int s() {\n", out_);
925 fputs(" return ", out_);
926 emitLiteral(kInt);
927 fputs(";\n }\n", out_);
928 fputs(" public int c() {\n", out_);
929 fputs(" return ", out_);
930 emitLiteral(kInt);
931 fputs(";\n }\n", out_);
932 fputs(" public int x() {\n", out_);
933 fputs(" return ", out_);
934 emitLiteral(kInt);
935 fputs(";\n }\n", out_);
936 fputs(" }\n\n", out_);
937 in_inner_ = false;
938 }
939
940 // Emit field declarations.
emitFieldDecls()941 void emitFieldDecls() {
942 fputs(" private A mA = new B();\n", out_);
943 fputs(" private B mB = new B();\n", out_);
944 fputs(" private X mBX = new B();\n", out_);
945 fputs(" private C mC = new C();\n", out_);
946 fputs(" private X mCX = new C();\n\n", out_);
947 fputs(" private boolean mZ = false;\n", out_);
948 fputs(" private int mI = 0;\n", out_);
949 fputs(" private long mJ = 0;\n", out_);
950 fputs(" private float mF = 0;\n", out_);
951 fputs(" private double mD = 0;\n\n", out_);
952 }
953
954 // Emit array declaration.
emitArrayDecl()955 void emitArrayDecl() {
956 fputs(" private ", out_);
957 emitType(array_type_);
958 for (uint32_t i = 0; i < array_dim_; i++) {
959 fputs("[]", out_);
960 }
961 fputs(" mArray = new ", out_);
962 emitType(array_type_);
963 for (uint32_t i = 0; i < array_dim_; i++) {
964 fprintf(out_, "[%d]", array_size_);
965 }
966 fputs(";\n\n", out_);
967 }
968
969 // Emit test constructor.
emitTestConstructor()970 void emitTestConstructor() {
971 fputs(" private Test() {\n", out_);
972 indentation_ += 2;
973 emitIndentation();
974 emitType(array_type_);
975 fputs(" a = ", out_);
976 emitLiteral(array_type_);
977 fputs(";\n", out_);
978 for (uint32_t i = 0; i < array_dim_; i++) {
979 emitIndentation();
980 fprintf(out_, "for (int i%u = 0; i%u < %u; i%u++) {\n", i, i, array_size_, i);
981 indentation_ += 2;
982 }
983 emitIndentation();
984 fputs("mArray", out_);
985 for (uint32_t i = 0; i < array_dim_; i++) {
986 fprintf(out_, "[i%u]", i);
987 }
988 fputs(" = a;\n", out_);
989 emitIndentation();
990 if (array_type_ == kBoolean) {
991 fputs("a = !a;\n", out_);
992 } else {
993 fputs("a++;\n", out_);
994 }
995 for (uint32_t i = 0; i < array_dim_; i++) {
996 indentation_ -= 2;
997 emitIndentation();
998 fputs("}\n", out_);
999 }
1000 indentation_ -= 2;
1001 fputs(" }\n\n", out_);
1002 }
1003
1004 // Emit test method.
emitTestMethod()1005 void emitTestMethod() {
1006 fputs(" private ", out_);
1007 emitType(return_type_);
1008 fputs(" testMethod() {\n", out_);
1009 indentation_ += 2;
1010 if (emitStatementList()) {
1011 // Must end with return.
1012 emitIndentation();
1013 emitReturn(true);
1014 }
1015 indentation_ -= 2;
1016 fputs(" }\n\n", out_);
1017 }
1018
1019 // Emit main method driver.
emitMainMethod()1020 void emitMainMethod() {
1021 fputs(" public static void main(String[] args) {\n", out_);
1022 indentation_ += 2;
1023 fputs(" Test t = new Test();\n ", out_);
1024 emitType(return_type_);
1025 fputs(" r = ", out_);
1026 emitLiteral(return_type_);
1027 fputs(";\n", out_);
1028 fputs(" try {\n", out_);
1029 fputs(" r = t.testMethod();\n", out_);
1030 fputs(" } catch (Exception e) {\n", out_);
1031 fputs(" // Arithmetic, null pointer, index out of bounds, etc.\n", out_);
1032 fputs(" System.out.println(\"An exception was caught.\");\n", out_);
1033 fputs(" }\n", out_);
1034 fputs(" System.out.println(\"r = \" + r);\n", out_);
1035 fputs(" System.out.println(\"mZ = \" + t.mZ);\n", out_);
1036 fputs(" System.out.println(\"mI = \" + t.mI);\n", out_);
1037 fputs(" System.out.println(\"mJ = \" + t.mJ);\n", out_);
1038 fputs(" System.out.println(\"mF = \" + t.mF);\n", out_);
1039 fputs(" System.out.println(\"mD = \" + t.mD);\n", out_);
1040 fputs(" System.out.println(\"mArray = \" + ", out_);
1041 if (array_dim_ == 1) {
1042 fputs("Arrays.toString(t.mArray)", out_);
1043 } else {
1044 fputs("Arrays.deepToString(t.mArray)", out_);
1045 }
1046 fputs(");\n", out_);
1047 indentation_ -= 2;
1048 fputs(" }\n", out_);
1049 }
1050
1051 // Emit program header. Emit command line options in the comments.
emitHeader()1052 void emitHeader() {
1053 fputs("\n/**\n * AOSP JFuzz Tester.\n", out_);
1054 fputs(" * Automatically generated program.\n", out_);
1055 fprintf(out_,
1056 " * jfuzz -s %u -d %u -l %u -i %u -n %u (version %s)\n */\n\n",
1057 fuzz_seed_,
1058 fuzz_expr_depth_,
1059 fuzz_stmt_length_,
1060 fuzz_if_nest_,
1061 fuzz_loop_nest_,
1062 VERSION);
1063 fputs("import java.util.Arrays;\n\n", out_);
1064 }
1065
1066 // Emit single test class with main driver.
emitTestClassWithMain()1067 void emitTestClassWithMain() {
1068 fputs("public class Test {\n\n", out_);
1069 indentation_ += 2;
1070 emitClassDecls();
1071 emitFieldDecls();
1072 emitArrayDecl();
1073 emitTestConstructor();
1074 emitTestMethod();
1075 emitMainMethod();
1076 indentation_ -= 2;
1077 fputs("}\n\n", out_);
1078 }
1079
1080 //
1081 // Random integers.
1082 //
1083
1084 // Return random integer.
random()1085 int32_t random() {
1086 return fuzz_random_engine_();
1087 }
1088
1089 // Return random integer in range [0,max).
random0(uint32_t max)1090 uint32_t random0(uint32_t max) {
1091 std::uniform_int_distribution<uint32_t> gen(0, max - 1);
1092 return gen(fuzz_random_engine_);
1093 }
1094
1095 // Return random integer in range [1,max].
random1(uint32_t max)1096 uint32_t random1(uint32_t max) {
1097 std::uniform_int_distribution<uint32_t> gen(1, max);
1098 return gen(fuzz_random_engine_);
1099 }
1100
1101 // Fuzzing parameters.
1102 FILE* out_;
1103 std::mt19937 fuzz_random_engine_;
1104 const uint32_t fuzz_seed_;
1105 const uint32_t fuzz_expr_depth_;
1106 const uint32_t fuzz_stmt_length_;
1107 const uint32_t fuzz_if_nest_;
1108 const uint32_t fuzz_loop_nest_;
1109
1110 // Return and array setup.
1111 const Type return_type_;
1112 const Type array_type_;
1113 const uint32_t array_dim_;
1114 const uint32_t array_size_;
1115
1116 // Current context.
1117 uint32_t indentation_;
1118 uint32_t expr_depth_;
1119 uint32_t stmt_length_;
1120 uint32_t if_nest_;
1121 uint32_t loop_nest_;
1122 uint32_t switch_nest_;
1123 uint32_t do_nest_;
1124 uint32_t boolean_local_;
1125 uint32_t int_local_;
1126 uint32_t long_local_;
1127 uint32_t float_local_;
1128 uint32_t double_local_;
1129 bool in_inner_;
1130 };
1131
1132 } // anonymous namespace
1133
main(int32_t argc,char ** argv)1134 int32_t main(int32_t argc, char** argv) {
1135 // Time-based seed.
1136 struct timeval tp;
1137 gettimeofday(&tp, NULL);
1138
1139 // Defaults.
1140 uint32_t seed = (tp.tv_sec * 1000000 + tp.tv_usec);
1141 uint32_t expr_depth = 1;
1142 uint32_t stmt_length = 8;
1143 uint32_t if_nest = 2;
1144 uint32_t loop_nest = 3;
1145
1146 // Parse options.
1147 while (1) {
1148 int32_t option = getopt(argc, argv, "s:d:l:i:n:vh");
1149 if (option < 0) {
1150 break; // done
1151 }
1152 switch (option) {
1153 case 's':
1154 seed = strtoul(optarg, nullptr, 0); // deterministic seed
1155 break;
1156 case 'd':
1157 expr_depth = strtoul(optarg, nullptr, 0);
1158 break;
1159 case 'l':
1160 stmt_length = strtoul(optarg, nullptr, 0);
1161 break;
1162 case 'i':
1163 if_nest = strtoul(optarg, nullptr, 0);
1164 break;
1165 case 'n':
1166 loop_nest = strtoul(optarg, nullptr, 0);
1167 break;
1168 case 'v':
1169 fprintf(stderr, "jfuzz version %s\n", VERSION);
1170 return 0;
1171 case 'h':
1172 default:
1173 fprintf(stderr,
1174 "usage: %s [-s seed] "
1175 "[-d expr-depth] [-l stmt-length] "
1176 "[-i if-nest] [-n loop-nest] [-v] [-h]\n",
1177 argv[0]);
1178 return 1;
1179 }
1180 }
1181
1182 // Seed global random generator.
1183 srand(seed);
1184
1185 // Generate fuzzed program.
1186 JFuzz fuzz(stdout, seed, expr_depth, stmt_length, if_nest, loop_nest);
1187 fuzz.emitProgram();
1188 return 0;
1189 }
1190