| // Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| import 'dart:io'; |
| import 'dart:math'; |
| |
| import 'package:args/args.dart'; |
| |
| import 'dartfuzz_values.dart'; |
| import 'dartfuzz_api_table.dart'; |
| |
| // Version of DartFuzz. Increase this each time changes are made |
| // to preserve the property that a given version of DartFuzz yields |
| // the same fuzzed program for a deterministic random seed. |
| const String version = '1.19'; |
| |
| // Restriction on statements and expressions. |
| const int stmtLength = 2; |
| const int stmtDepth = 1; |
| const int exprDepth = 2; |
| |
| // Naming conventions. |
| const varName = 'var'; |
| const paramName = 'par'; |
| const localName = 'loc'; |
| const fieldName = 'fld'; |
| const methodName = 'foo'; |
| |
| /// Class that generates a random, but runnable Dart program for fuzz testing. |
| class DartFuzz { |
| DartFuzz(this.seed, this.fp, this.ffi, this.file); |
| |
| void run() { |
| // Initialize program variables. |
| rand = new Random(seed); |
| indent = 0; |
| nest = 0; |
| currentClass = null; |
| currentMethod = null; |
| // Setup the types. |
| localVars = new List<DartType>(); |
| iterVars = new List<String>(); |
| globalVars = fillTypes1(); |
| globalVars.addAll(DartType.allTypes); // always one each |
| globalMethods = fillTypes2(); |
| classFields = fillTypes2(); |
| classMethods = fillTypes3(classFields.length); |
| // Setup optional ffi methods and types. |
| List<bool> ffiStatus = new List<bool>(); |
| for (var m in globalMethods) { |
| ffiStatus.add(false); |
| } |
| if (ffi) { |
| List<List<DartType>> globalMethodsFfi = fillTypes2(isFfi: true); |
| for (var m in globalMethodsFfi) { |
| globalMethods.add(m); |
| ffiStatus.add(true); |
| } |
| } |
| // Generate. |
| emitHeader(); |
| emitVarDecls(varName, globalVars); |
| emitMethods(methodName, globalMethods, ffiStatus); |
| emitClasses(); |
| emitMain(); |
| // Sanity. |
| assert(currentClass == null); |
| assert(currentMethod == null); |
| assert(indent == 0); |
| assert(nest == 0); |
| assert(localVars.length == 0); |
| } |
| |
| // |
| // Program components. |
| // |
| |
| void emitHeader() { |
| emitLn('// The Dart Project Fuzz Tester ($version).'); |
| emitLn('// Program generated as:'); |
| emitLn('// dart dartfuzz.dart --seed $seed --${fp ? "" : "no-"}fp ' + |
| '--${ffi ? "" : "no-"}ffi'); |
| emitLn(''); |
| emitLn("import 'dart:async';"); |
| emitLn("import 'dart:cli';"); |
| emitLn("import 'dart:collection';"); |
| emitLn("import 'dart:convert';"); |
| emitLn("import 'dart:core';"); |
| emitLn("import 'dart:io';"); |
| emitLn("import 'dart:isolate';"); |
| emitLn("import 'dart:math';"); |
| emitLn("import 'dart:typed_data';"); |
| if (ffi) emitLn("import 'dart:ffi' as ffi;"); |
| } |
| |
| void emitFfiCast(String dartFuncName, String ffiFuncName, String typeName, |
| List<DartType> pars) { |
| emit("${pars[0].name} Function("); |
| for (int i = 1; i < pars.length; i++) { |
| DartType tp = pars[i]; |
| emit('${tp.name}'); |
| if (i != (pars.length - 1)) { |
| emit(', '); |
| } |
| } |
| emit(') ${dartFuncName} = ' + |
| 'ffi.Pointer.fromFunction<${typeName}>(${ffiFuncName}, '); |
| emitLiteral(0, pars[0]); |
| emitLn(').cast<ffi.NativeFunction<${typeName}>>().asFunction();'); |
| } |
| |
| void emitMethods(String name, List<List<DartType>> methods, |
| [List<bool> ffiStatus]) { |
| for (int i = 0; i < methods.length; i++) { |
| List<DartType> method = methods[i]; |
| currentMethod = i; |
| bool isFfiMethod = ffiStatus != null && ffiStatus[i]; |
| if (isFfiMethod) { |
| emitFfiTypedef("${name}Ffi${i}Type", method); |
| emitLn('${method[0].name} ${name}Ffi$i(', newline: false); |
| } else { |
| emitLn('${method[0].name} $name$i(', newline: false); |
| } |
| emitParDecls(method); |
| emit(') {', newline: true); |
| indent += 2; |
| assert(localVars.length == 0); |
| if (emitStatements(0)) { |
| emitReturn(); |
| } |
| assert(localVars.length == 0); |
| indent -= 2; |
| emitLn('}'); |
| if (isFfiMethod) { |
| emitFfiCast( |
| "${name}${i}", "${name}Ffi${i}", "${name}Ffi${i}Type", method); |
| } |
| emit('', newline: true); |
| currentMethod = null; |
| } |
| } |
| |
| void emitClasses() { |
| assert(classFields.length == classMethods.length); |
| for (int i = 0; i < classFields.length; i++) { |
| emitLn('class X$i ${i == 0 ? "" : "extends X${i - 1}"} {'); |
| indent += 2; |
| emitVarDecls('$fieldName${i}_', classFields[i]); |
| currentClass = i; |
| emitMethods('$methodName${i}_', classMethods[i]); |
| emitLn('void run() {'); |
| indent += 2; |
| if (i > 0) { |
| emitLn('super.run();'); |
| } |
| assert(localVars.length == 0); |
| emitStatements(0); |
| assert(localVars.length == 0); |
| indent -= 2; |
| emitLn('}'); |
| indent -= 2; |
| emitLn('}'); |
| emit('', newline: true); |
| currentClass = null; |
| } |
| } |
| |
| void emitMain() { |
| emitLn('main() {'); |
| indent += 2; |
| emitLn('try {'); |
| indent += 2; |
| emitLn('new X${classFields.length - 1}().run();'); |
| indent -= 2; |
| emitLn('} catch (exception, stackTrace) {'); |
| indent += 2; |
| emitLn("print('throws');"); |
| indent -= 2; |
| emitLn('} finally {'); |
| indent += 2; |
| emitLn("print('", newline: false); |
| for (int i = 0; i < globalVars.length; i++) { |
| emit('\$$varName$i\\n'); |
| } |
| emit("');", newline: true); |
| indent -= 2; |
| emitLn('}'); |
| indent -= 2; |
| emitLn('}'); |
| } |
| |
| // |
| // Declarations. |
| // |
| |
| void emitVarDecls(String name, List<DartType> vars) { |
| emit('', newline: true); |
| for (int i = 0; i < vars.length; i++) { |
| DartType tp = vars[i]; |
| emitLn('${tp.name} $name$i = ', newline: false); |
| emitLiteral(0, tp); |
| emit(';', newline: true); |
| } |
| emit('', newline: true); |
| } |
| |
| void emitParDecls(List<DartType> pars) { |
| for (int i = 1; i < pars.length; i++) { |
| DartType tp = pars[i]; |
| emit('${tp.name} $paramName$i'); |
| if (i != (pars.length - 1)) { |
| emit(', '); |
| } |
| } |
| } |
| |
| // |
| // Comments (for FE and analysis tools). |
| // |
| |
| void emitComment() { |
| switch (rand.nextInt(4)) { |
| case 0: |
| emitLn('// Single-line comment.'); |
| break; |
| case 1: |
| emitLn('/// Single-line documentation comment.'); |
| break; |
| case 2: |
| emitLn('/*'); |
| emitLn(' * Multi-line'); |
| emitLn(' * comment.'); |
| emitLn(' */'); |
| break; |
| default: |
| emitLn('/**'); |
| emitLn(' ** Multi-line'); |
| emitLn(' ** documentation comment.'); |
| emitLn(' */'); |
| break; |
| } |
| } |
| |
| // |
| // Statements. |
| // |
| |
| // Emit an assignment statement. |
| bool emitAssign() { |
| DartType tp = getType(); |
| emitLn('', newline: false); |
| emitVar(0, tp, isLhs: true); |
| emitAssignOp(tp); |
| emitExpr(0, tp); |
| emit(';', newline: true); |
| return true; |
| } |
| |
| // Emit a print statement. |
| bool emitPrint() { |
| DartType tp = getType(); |
| emitLn('print(', newline: false); |
| emitExpr(0, tp); |
| emit(');', newline: true); |
| return true; |
| } |
| |
| // Emit a return statement. |
| bool emitReturn() { |
| List<DartType> proto = getCurrentProto(); |
| if (proto == null) { |
| emitLn('return;'); |
| } else { |
| emitLn('return ', newline: false); |
| emitExpr(0, proto[0]); |
| emit(';', newline: true); |
| } |
| return false; |
| } |
| |
| // Emit a throw statement. |
| bool emitThrow() { |
| DartType tp = getType(); |
| emitLn('throw ', newline: false); |
| emitExpr(0, tp); |
| emit(';', newline: true); |
| return false; |
| } |
| |
| // Emit a one-way if statement. |
| bool emitIf1(int depth) { |
| emitLn('if (', newline: false); |
| emitExpr(0, DartType.BOOL); |
| emit(') {', newline: true); |
| indent += 2; |
| emitStatements(depth + 1); |
| indent -= 2; |
| emitLn('}'); |
| return true; |
| } |
| |
| // Emit a two-way if statement. |
| bool emitIf2(int depth) { |
| emitLn('if (', newline: false); |
| emitExpr(0, DartType.BOOL); |
| emit(') {', newline: true); |
| indent += 2; |
| bool b1 = emitStatements(depth + 1); |
| indent -= 2; |
| emitLn('} else {'); |
| indent += 2; |
| bool b2 = emitStatements(depth + 1); |
| indent -= 2; |
| emitLn('}'); |
| return b1 || b2; |
| } |
| |
| // Emit a simple increasing for-loop. |
| bool emitFor(int depth) { |
| int i = localVars.length; |
| emitLn('for (int $localName$i = 0; $localName$i < ', newline: false); |
| emitSmallPositiveInt(); |
| emit('; $localName$i++) {', newline: true); |
| indent += 2; |
| nest++; |
| iterVars.add("$localName$i"); |
| localVars.add(DartType.INT); |
| emitStatements(depth + 1); |
| localVars.removeLast(); |
| iterVars.removeLast(); |
| nest--; |
| indent -= 2; |
| emitLn('}'); |
| return true; |
| } |
| |
| // Emit a simple membership for-in-loop. |
| bool emitForIn(int depth) { |
| int i = localVars.length; |
| emitLn('for (int $localName$i in ', newline: false); |
| emitExpr(0, rand.nextBool() ? DartType.INT_LIST : DartType.INT_SET); |
| emit(') {', newline: true); |
| indent += 2; |
| nest++; |
| localVars.add(DartType.INT); |
| emitStatements(depth + 1); |
| localVars.removeLast(); |
| nest--; |
| indent -= 2; |
| emitLn('}'); |
| return true; |
| } |
| |
| // Emit a while-loop. |
| bool emitWhile(int depth) { |
| int i = localVars.length; |
| emitLn('{ int $localName$i = ', newline: false); |
| emitSmallPositiveInt(); |
| emit(';', newline: true); |
| indent += 2; |
| emitLn('while (--$localName$i > 0) {'); |
| indent += 2; |
| nest++; |
| iterVars.add("$localName$i"); |
| localVars.add(DartType.INT); |
| emitStatements(depth + 1); |
| localVars.removeLast(); |
| iterVars.removeLast(); |
| nest--; |
| indent -= 2; |
| emitLn('}'); |
| indent -= 2; |
| emitLn('}'); |
| return true; |
| } |
| |
| // Emit a do-while-loop. |
| bool emitDoWhile(int depth) { |
| int i = localVars.length; |
| emitLn('{ int $localName$i = 0;'); |
| indent += 2; |
| emitLn('do {'); |
| indent += 2; |
| nest++; |
| iterVars.add("$localName$i"); |
| localVars.add(DartType.INT); |
| emitStatements(depth + 1); |
| localVars.removeLast(); |
| iterVars.removeLast(); |
| nest--; |
| indent -= 2; |
| emitLn('} while (++$localName$i < ', newline: false); |
| emitSmallPositiveInt(); |
| emit(');', newline: true); |
| indent -= 2; |
| emitLn('}'); |
| return true; |
| } |
| |
| // Emit a break/continue when inside iteration. |
| bool emitBreakOrContinue(int depth) { |
| if (nest > 0) { |
| switch (rand.nextInt(2)) { |
| case 0: |
| emitLn('continue;'); |
| return false; |
| default: |
| emitLn('break;'); |
| return false; |
| } |
| } |
| return emitAssign(); // resort to assignment |
| } |
| |
| // Emit a switch statement. |
| bool emitSwitch(int depth) { |
| emitLn('switch (', newline: false); |
| emitExpr(0, DartType.INT); |
| emit(') {', newline: true); |
| int start = rand.nextInt(1 << 32); |
| int step = 1 + rand.nextInt(10); |
| for (int i = 0; i < 2; i++, start += step) { |
| indent += 2; |
| if (i == 2) { |
| emitLn('default: {'); |
| } else { |
| emitLn('case $start: {'); |
| } |
| indent += 2; |
| emitStatements(depth + 1); |
| indent -= 2; |
| emitLn('}'); |
| emitLn('break;'); // always generate, avoid FE complaints |
| indent -= 2; |
| } |
| emitLn('}'); |
| return true; |
| } |
| |
| // Emit a new program scope that introduces a new local variable. |
| bool emitScope(int depth) { |
| DartType tp = getType(); |
| emitLn('{ ${tp.name} $localName${localVars.length} = ', newline: false); |
| emitExpr(0, tp); |
| emit(';', newline: true); |
| indent += 2; |
| localVars.add(tp); |
| bool b = emitStatements(depth + 1); |
| localVars.removeLast(); |
| indent -= 2; |
| emitLn('}'); |
| return true; |
| } |
| |
| // Emit try/catch/finally. |
| bool emitTryCatch(int depth) { |
| emitLn('try {'); |
| indent += 2; |
| emitStatements(depth + 1); |
| indent -= 2; |
| emitLn('} catch (exception, stackTrace) {'); |
| indent += 2; |
| emitStatements(depth + 1); |
| indent -= 2; |
| if (rand.nextInt(2) == 0) { |
| emitLn('} finally {'); |
| indent += 2; |
| emitStatements(depth + 1); |
| indent -= 2; |
| } |
| emitLn('}'); |
| return true; |
| } |
| |
| // Emit a statement. Returns true if code *may* fall-through |
| // (not made too advanced to avoid FE complaints). |
| bool emitStatement(int depth) { |
| // Throw in a comment every once in a while. |
| if (rand.nextInt(10) == 0) { |
| emitComment(); |
| } |
| // Continuing nested statements becomes less likely as the depth grows. |
| if (rand.nextInt(depth + 1) > stmtDepth) { |
| return emitAssign(); |
| } |
| // Possibly nested statement. |
| switch (rand.nextInt(16)) { |
| // Favors assignment. |
| case 0: |
| return emitPrint(); |
| case 1: |
| return emitReturn(); |
| case 2: |
| return emitThrow(); |
| case 3: |
| return emitIf1(depth); |
| case 4: |
| return emitIf2(depth); |
| case 5: |
| return emitFor(depth); |
| case 6: |
| return emitForIn(depth); |
| case 7: |
| return emitWhile(depth); |
| case 8: |
| return emitDoWhile(depth); |
| case 9: |
| return emitBreakOrContinue(depth); |
| case 10: |
| return emitSwitch(depth); |
| case 11: |
| return emitScope(depth); |
| case 12: |
| return emitTryCatch(depth); |
| default: |
| return emitAssign(); |
| } |
| } |
| |
| // Emit statements. Returns true if code may fall-through. |
| bool emitStatements(int depth) { |
| int s = 1 + rand.nextInt(stmtLength); |
| for (int i = 0; i < s; i++) { |
| if (!emitStatement(depth)) { |
| return false; // rest would be dead code |
| } |
| } |
| return true; |
| } |
| |
| // |
| // Expressions. |
| // |
| |
| void emitBool() { |
| emit(rand.nextInt(2) == 0 ? 'true' : 'false'); |
| } |
| |
| void emitSmallPositiveInt() { |
| emit('${rand.nextInt(100)}'); |
| } |
| |
| void emitSmallNegativeInt() { |
| emit('-${rand.nextInt(100)}'); |
| } |
| |
| void emitInt() { |
| switch (rand.nextInt(7)) { |
| // Favors small ints. |
| case 0: |
| case 1: |
| case 2: |
| emitSmallPositiveInt(); |
| break; |
| case 3: |
| case 4: |
| case 5: |
| emitSmallNegativeInt(); |
| break; |
| default: |
| emit('${oneOf(DartFuzzValues.interestingIntegers)}'); |
| break; |
| } |
| } |
| |
| void emitDouble() { |
| emit('${rand.nextDouble()}'); |
| } |
| |
| void emitChar() { |
| switch (rand.nextInt(10)) { |
| // Favors regular char. |
| case 0: |
| emit(oneOf(DartFuzzValues.interestingChars)); |
| break; |
| default: |
| emit(DartFuzzValues |
| .regularChars[rand.nextInt(DartFuzzValues.regularChars.length)]); |
| break; |
| } |
| } |
| |
| void emitString({int length = 8}) { |
| emit("'"); |
| for (int i = 0, n = rand.nextInt(length); i < n; i++) { |
| emitChar(); |
| } |
| emit("'"); |
| } |
| |
| void emitElementExpr(int depth, DartType tp) { |
| if (currentMethod != null) { |
| emitExpr(depth, tp); |
| } else { |
| emitLiteral(depth, tp); |
| } |
| } |
| |
| void emitElement(int depth, DartType tp) { |
| if (tp == DartType.INT_STRING_MAP) { |
| emitSmallPositiveInt(); |
| emit(' : '); |
| emitElementExpr(depth, DartType.STRING); |
| } else { |
| emitElementExpr(depth, DartType.INT); |
| } |
| } |
| |
| void emitCollectionElement(int depth, DartType tp) { |
| int r = depth <= exprDepth ? rand.nextInt(10) : 10; |
| switch (r + 3) { |
| // TODO(ajcbik): enable when on by default |
| // Favors elements over control-flow collections. |
| case 0: |
| emit('...'); // spread |
| emitCollection(depth + 1, tp); |
| break; |
| case 1: |
| emit('if ('); |
| emitElementExpr(depth + 1, DartType.BOOL); |
| emit(') '); |
| emitCollectionElement(depth + 1, tp); |
| if (rand.nextBool()) { |
| emit(' else '); |
| emitCollectionElement(depth + 1, tp); |
| } |
| break; |
| case 2: |
| { |
| int i = localVars.length; |
| emit('for (int $localName$i '); |
| // For-loop (induction, list, set). |
| switch (rand.nextInt(3)) { |
| case 0: |
| emit('= 0; $localName$i < '); |
| emitSmallPositiveInt(); |
| emit('; $localName$i++) '); |
| break; |
| case 1: |
| emit('in '); |
| emitCollection(depth + 1, DartType.INT_LIST); |
| emit(') '); |
| break; |
| default: |
| emit('in '); |
| emitCollection(depth + 1, DartType.INT_SET); |
| emit(') '); |
| break; |
| } |
| nest++; |
| localVars.add(DartType.INT); |
| emitCollectionElement(depth + 1, tp); |
| localVars.removeLast(); |
| nest--; |
| break; |
| } |
| default: |
| emitElement(depth, tp); |
| break; |
| } |
| } |
| |
| void emitCollection(int depth, DartType tp) { |
| emit(tp == DartType.INT_LIST ? '[ ' : '{ '); |
| for (int i = 0, n = 1 + rand.nextInt(8); i < n; i++) { |
| emitCollectionElement(depth, tp); |
| if (i != (n - 1)) { |
| emit(', '); |
| } |
| } |
| emit(tp == DartType.INT_LIST ? ' ]' : ' }'); |
| } |
| |
| void emitLiteral(int depth, DartType tp) { |
| if (tp == DartType.BOOL) { |
| emitBool(); |
| } else if (tp == DartType.INT) { |
| emitInt(); |
| } else if (tp == DartType.DOUBLE) { |
| emitDouble(); |
| } else if (tp == DartType.STRING) { |
| emitString(); |
| } else if (tp == DartType.INT_LIST || |
| tp == DartType.INT_SET || |
| tp == DartType.INT_STRING_MAP) { |
| emitCollection(depth, tp); |
| } else { |
| assert(false); |
| } |
| } |
| |
| void emitScalarVar(DartType tp, {bool isLhs = false}) { |
| // Collect all choices from globals, fields, locals, and parameters. |
| Set<String> choices = new Set<String>(); |
| for (int i = 0; i < globalVars.length; i++) { |
| if (tp == globalVars[i]) choices.add('$varName$i'); |
| } |
| for (int i = 0; i < localVars.length; i++) { |
| if (tp == localVars[i]) choices.add('$localName$i'); |
| } |
| List<DartType> fields = getCurrentFields(); |
| if (fields != null) { |
| for (int i = 0; i < fields.length; i++) { |
| if (tp == fields[i]) choices.add('$fieldName${currentClass}_$i'); |
| } |
| } |
| List<DartType> proto = getCurrentProto(); |
| if (proto != null) { |
| for (int i = 1; i < proto.length; i++) { |
| if (tp == proto[i]) choices.add('$paramName$i'); |
| } |
| } |
| // Remove possible modification of the iteration variable from the loop |
| // body. |
| if (isLhs) { |
| if (rand.nextInt(10) != 0) { |
| Set<String> cleanChoices = choices.difference(Set.from(iterVars)); |
| if (cleanChoices.length > 0) { |
| choices = cleanChoices; |
| } |
| } |
| } |
| // Then pick one. |
| assert(choices.length > 0); |
| emit('${choices.elementAt(rand.nextInt(choices.length))}'); |
| } |
| |
| void emitSubscriptedVar(int depth, DartType tp, {bool isLhs = false}) { |
| if (tp == DartType.INT) { |
| emitScalarVar(DartType.INT_LIST, isLhs: isLhs); |
| emit('['); |
| emitExpr(depth + 1, DartType.INT); |
| emit(']'); |
| } else if (tp == DartType.STRING) { |
| emitScalarVar(DartType.INT_STRING_MAP, isLhs: isLhs); |
| emit('['); |
| emitExpr(depth + 1, DartType.INT); |
| emit(']'); |
| } else { |
| emitScalarVar(tp, isLhs: isLhs); // resort to scalar |
| } |
| } |
| |
| void emitVar(int depth, DartType tp, {bool isLhs = false}) { |
| switch (rand.nextInt(2)) { |
| case 0: |
| emitScalarVar(tp, isLhs: isLhs); |
| break; |
| default: |
| emitSubscriptedVar(depth, tp, isLhs: isLhs); |
| break; |
| } |
| } |
| |
| void emitTerminal(int depth, DartType tp) { |
| switch (rand.nextInt(2)) { |
| case 0: |
| emitLiteral(depth, tp); |
| break; |
| default: |
| emitVar(depth, tp); |
| break; |
| } |
| } |
| |
| void emitExprList(int depth, List<DartType> proto) { |
| emit('('); |
| for (int i = 1; i < proto.length; i++) { |
| emitExpr(depth, proto[i]); |
| if (i != (proto.length - 1)) { |
| emit(', '); |
| } |
| } |
| emit(')'); |
| } |
| |
| // Emit expression with unary operator: (~(x)) |
| void emitUnaryExpr(int depth, DartType tp) { |
| if (tp == DartType.BOOL || tp == DartType.INT || tp == DartType.DOUBLE) { |
| emit('('); |
| emitUnaryOp(tp); |
| emit('('); |
| emitExpr(depth + 1, tp); |
| emit('))'); |
| } else { |
| emitTerminal(depth, tp); // resort to terminal |
| } |
| } |
| |
| // Emit expression with binary operator: (x + y) |
| void emitBinaryExpr(int depth, DartType tp) { |
| if (tp == DartType.BOOL) { |
| // For boolean, allow type switch with relational op. |
| if (rand.nextInt(2) == 0) { |
| DartType deeper_tp = getType(); |
| emit('('); |
| emitExpr(depth + 1, deeper_tp); |
| emitRelOp(deeper_tp); |
| emitExpr(depth + 1, deeper_tp); |
| emit(')'); |
| return; |
| } |
| } else if (tp == DartType.STRING || tp == DartType.INT_LIST) { |
| // For strings and lists, a construct like x = x + x; inside a loop |
| // yields an exponentially growing data structure. We avoid this |
| // situation by forcing a literal on the rhs of each +. |
| emit('('); |
| emitExpr(depth + 1, tp); |
| emitBinaryOp(tp); |
| emitLiteral(depth + 1, tp); |
| emit(')'); |
| return; |
| } |
| emit('('); |
| emitExpr(depth + 1, tp); |
| emitBinaryOp(tp); |
| emitExpr(depth + 1, tp); |
| emit(')'); |
| } |
| |
| // Emit expression with ternary operator: (b ? x : y) |
| void emitTernaryExpr(int depth, DartType tp) { |
| emit('('); |
| emitExpr(depth + 1, DartType.BOOL); |
| emit(' ? '); |
| emitExpr(depth + 1, tp); |
| emit(' : '); |
| emitExpr(depth + 1, tp); |
| emit(')'); |
| } |
| |
| // Emit expression with pre/post-increment/decrement operator: (x++) |
| void emitPreOrPostExpr(int depth, DartType tp) { |
| if (tp == DartType.INT) { |
| int r = rand.nextInt(2); |
| emit('('); |
| if (r == 0) emitPreOrPostOp(tp); |
| emitScalarVar(tp, isLhs: true); |
| if (r == 1) emitPreOrPostOp(tp); |
| emit(')'); |
| } else { |
| emitTerminal(depth, tp); // resort to terminal |
| } |
| } |
| |
| // Emit library call. |
| void emitLibraryCall(int depth, DartType tp) { |
| DartLib lib = getLibraryMethod(tp); |
| String proto = lib.proto; |
| // Receiver. |
| if (proto[0] != 'V') { |
| emit('('); |
| emitArg(depth + 1, proto[0]); |
| emit(').'); |
| } |
| // Call. |
| emit('${lib.name}'); |
| // Parameters. |
| if (proto[1] != 'v') { |
| emit('('); |
| if (proto[1] != 'V') { |
| for (int i = 1; i < proto.length; i++) { |
| emitArg(depth + 1, proto[i]); |
| if (i != (proto.length - 1)) { |
| emit(', '); |
| } |
| } |
| } |
| emit(')'); |
| } |
| } |
| |
| // Helper for a method call. |
| bool pickedCall( |
| int depth, DartType tp, String name, List<List<DartType>> protos, int m) { |
| for (int i = m - 1; i >= 0; i--) { |
| if (tp == protos[i][0]) { |
| emit('$name$i'); |
| emitExprList(depth + 1, protos[i]); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| // Emit method call within the program. |
| void emitMethodCall(int depth, DartType tp) { |
| // Only call backward to avoid infinite recursion. |
| if (currentClass == null) { |
| // Outside a class but inside a method: call backward in global methods. |
| if (currentMethod != null && |
| pickedCall(depth, tp, methodName, globalMethods, currentMethod)) { |
| return; |
| } |
| } else { |
| // Inside a class: try to call backwards in class methods first. |
| int m1 = currentMethod == null |
| ? classMethods[currentClass].length |
| : currentMethod; |
| int m2 = globalMethods.length; |
| if (pickedCall(depth, tp, '$methodName${currentClass}_', |
| classMethods[currentClass], m1) || |
| pickedCall(depth, tp, methodName, globalMethods, m2)) { |
| return; |
| } |
| } |
| emitTerminal(depth, tp); // resort to terminal. |
| } |
| |
| // Emit expression. |
| void emitExpr(int depth, DartType tp) { |
| // Continuing nested expressions becomes less likely as the depth grows. |
| if (rand.nextInt(depth + 1) > exprDepth) { |
| emitTerminal(depth, tp); |
| return; |
| } |
| // Possibly nested expression. |
| switch (rand.nextInt(7)) { |
| case 0: |
| emitUnaryExpr(depth, tp); |
| break; |
| case 1: |
| emitBinaryExpr(depth, tp); |
| break; |
| case 2: |
| emitTernaryExpr(depth, tp); |
| break; |
| case 3: |
| emitPreOrPostExpr(depth, tp); |
| break; |
| case 4: |
| emitLibraryCall(depth, tp); |
| break; |
| case 5: |
| emitMethodCall(depth, tp); |
| break; |
| default: |
| emitTerminal(depth, tp); |
| break; |
| } |
| } |
| |
| // |
| // Operators. |
| // |
| |
| // Emit same type in-out assignment operator. |
| void emitAssignOp(DartType tp) { |
| if (tp == DartType.INT) { |
| emit(oneOf(const <String>[ |
| ' += ', |
| ' -= ', |
| ' *= ', |
| ' ~/= ', |
| ' %= ', |
| ' &= ', |
| ' |= ', |
| ' ^= ', |
| ' >>= ', |
| ' <<= ', |
| ' ??= ', |
| ' = ' |
| ])); |
| } else if (tp == DartType.DOUBLE) { |
| emit(oneOf( |
| const <String>[' += ', ' -= ', ' *= ', ' /= ', ' ??= ', ' = '])); |
| } else { |
| emit(oneOf(const <String>[' ??= ', ' = '])); |
| } |
| } |
| |
| // Emit same type in-out unary operator. |
| void emitUnaryOp(DartType tp) { |
| if (tp == DartType.BOOL) { |
| emit('!'); |
| } else if (tp == DartType.INT) { |
| emit(oneOf(const <String>['-', '~'])); |
| } else if (tp == DartType.DOUBLE) { |
| emit('-'); |
| } else { |
| assert(false); |
| } |
| } |
| |
| // Emit same type in-out binary operator. |
| void emitBinaryOp(DartType tp) { |
| if (tp == DartType.BOOL) { |
| emit(oneOf(const <String>[' && ', ' || '])); |
| } else if (tp == DartType.INT) { |
| emit(oneOf(const <String>[ |
| ' + ', |
| ' - ', |
| ' * ', |
| ' ~/ ', |
| ' % ', |
| ' & ', |
| ' | ', |
| ' ^ ', |
| ' >> ', |
| ' << ', |
| ' ?? ' |
| ])); |
| } else if (tp == DartType.DOUBLE) { |
| emit(oneOf(const <String>[' + ', ' - ', ' * ', ' / ', ' ?? '])); |
| } else if (tp == DartType.STRING || tp == DartType.INT_LIST) { |
| emit(oneOf(const <String>[' + ', ' ?? '])); |
| } else { |
| emit(' ?? '); |
| } |
| } |
| |
| // Emit same type in-out increment operator. |
| void emitPreOrPostOp(DartType tp) { |
| if (tp == DartType.INT) { |
| emit(oneOf(const <String>['++', '--'])); |
| } else { |
| assert(false); |
| } |
| } |
| |
| // Emit one type in, boolean out operator. |
| void emitRelOp(DartType tp) { |
| if (tp == DartType.INT || tp == DartType.DOUBLE) { |
| emit(oneOf(const <String>[' > ', ' >= ', ' < ', ' <= ', ' != ', ' == '])); |
| } else { |
| emit(oneOf(const <String>[' != ', ' == '])); |
| } |
| } |
| |
| // |
| // Library methods. |
| // |
| |
| // Get a library method that returns given type. |
| DartLib getLibraryMethod(DartType tp) { |
| if (tp == DartType.BOOL) { |
| return oneOf(DartLib.boolLibs); |
| } else if (tp == DartType.INT) { |
| return oneOf(DartLib.intLibs); |
| } else if (tp == DartType.DOUBLE) { |
| return oneOf(DartLib.doubleLibs); |
| } else if (tp == DartType.STRING) { |
| return oneOf(DartLib.stringLibs); |
| } else if (tp == DartType.INT_LIST) { |
| return oneOf(DartLib.listLibs); |
| } else if (tp == DartType.INT_SET) { |
| return oneOf(DartLib.setLibs); |
| } else if (tp == DartType.INT_STRING_MAP) { |
| return oneOf(DartLib.mapLibs); |
| } else { |
| assert(false); |
| } |
| } |
| |
| // Emit a library argument, possibly subject to restrictions. |
| void emitArg(int depth, String p) { |
| switch (p) { |
| case 'B': |
| emitExpr(depth, DartType.BOOL); |
| break; |
| case 'i': |
| emitSmallPositiveInt(); |
| break; |
| case 'I': |
| emitExpr(depth, DartType.INT); |
| break; |
| case 'D': |
| emitExpr(depth, fp ? DartType.DOUBLE : DartType.INT); |
| break; |
| case 'S': |
| emitExpr(depth, DartType.STRING); |
| break; |
| case 's': |
| // Emit string literal of 2 characters maximum length |
| // for 'small string' parameters to avoid recursively constructed |
| // strings which might lead to exponentially growing data structures |
| // e.g. loop { var = 'x'.padLeft(8, var); } |
| // TODO (felih): detect recursion to eliminate such cases specifically |
| emitString(length: 2); |
| break; |
| case 'L': |
| emitExpr(depth, DartType.INT_LIST); |
| break; |
| case 'X': |
| emitExpr(depth, DartType.INT_SET); |
| break; |
| case 'M': |
| emitExpr(depth, DartType.INT_STRING_MAP); |
| break; |
| default: |
| assert(false); |
| } |
| } |
| |
| // |
| // Types. |
| // |
| |
| // Get a random value type. |
| DartType getType() { |
| switch (rand.nextInt(7)) { |
| case 0: |
| return DartType.BOOL; |
| case 1: |
| return DartType.INT; |
| case 2: |
| return fp ? DartType.DOUBLE : DartType.INT; |
| case 3: |
| return DartType.STRING; |
| case 4: |
| return DartType.INT_LIST; |
| case 5: |
| return DartType.INT_SET; |
| case 6: |
| return DartType.INT_STRING_MAP; |
| } |
| } |
| |
| List<DartType> fillTypes1({bool isFfi = false}) { |
| List<DartType> list = new List<DartType>(); |
| for (int i = 0, n = 1 + rand.nextInt(4); i < n; i++) { |
| if (isFfi) |
| list.add(fp ? oneOf([DartType.INT, DartType.DOUBLE]) : DartType.INT); |
| else |
| list.add(getType()); |
| } |
| return list; |
| } |
| |
| List<List<DartType>> fillTypes2({bool isFfi = false}) { |
| List<List<DartType>> list = new List<List<DartType>>(); |
| for (int i = 0, n = 1 + rand.nextInt(4); i < n; i++) { |
| list.add(fillTypes1(isFfi: isFfi)); |
| } |
| return list; |
| } |
| |
| List<List<List<DartType>>> fillTypes3(int n) { |
| List<List<List<DartType>>> list = new List<List<List<DartType>>>(); |
| for (int i = 0; i < n; i++) { |
| list.add(fillTypes2()); |
| } |
| return list; |
| } |
| |
| List<DartType> getCurrentProto() { |
| if (currentClass != null) { |
| if (currentMethod != null) { |
| return classMethods[currentClass][currentMethod]; |
| } |
| } else if (currentMethod != null) { |
| return globalMethods[currentMethod]; |
| } |
| return null; |
| } |
| |
| List<DartType> getCurrentFields() { |
| if (currentClass != null) { |
| return classFields[currentClass]; |
| } |
| return null; |
| } |
| |
| String getFfiType(String name) { |
| switch (name) { |
| case 'int': |
| return 'ffi.Int32'; |
| case 'double': |
| return 'ffi.Double'; |
| default: |
| throw 'Invalid FFI type ${name}'; |
| } |
| } |
| |
| void emitFfiTypedef(String typeName, List<DartType> pars) { |
| emit("typedef ${typeName} = ${getFfiType(pars[0].name)} Function("); |
| for (int i = 1; i < pars.length; i++) { |
| DartType tp = pars[i]; |
| emit('${getFfiType(tp.name)}'); |
| if (i != (pars.length - 1)) { |
| emit(', '); |
| } |
| } |
| emitLn(');'); |
| } |
| |
| // |
| // Output. |
| // |
| |
| // Emits indented line to append to program. |
| void emitLn(String line, {bool newline = true}) { |
| file.writeStringSync(' ' * indent); |
| emit(line, newline: newline); |
| } |
| |
| // Emits text to append to program. |
| void emit(String txt, {bool newline = false}) { |
| file.writeStringSync(txt); |
| if (newline) { |
| file.writeStringSync('\n'); |
| } |
| } |
| |
| // Emits one of the given choices. |
| T oneOf<T>(List<T> choices) { |
| return choices[rand.nextInt(choices.length)]; |
| } |
| |
| // Random seed used to generate program. |
| final int seed; |
| |
| // Enables floating-point operations. |
| final bool fp; |
| |
| // Enables FFI method calls. |
| final bool ffi; |
| |
| // File used for output. |
| final RandomAccessFile file; |
| |
| // Program variables. |
| Random rand; |
| int indent; |
| int nest; |
| int currentClass; |
| int currentMethod; |
| |
| // Types of local variables currently in scope. |
| List<DartType> localVars; |
| |
| // Types of global variables. |
| List<DartType> globalVars; |
| |
| // Names of currenty active iterator variables. |
| // These are tracked to avoid modifications within the loop body, |
| // which can lead to infinite loops. |
| List<String> iterVars; |
| |
| // Prototypes of all global methods (first element is return type). |
| List<List<DartType>> globalMethods; |
| |
| // Types of fields over all classes. |
| List<List<DartType>> classFields; |
| |
| // Prototypes of all methods over all classes (first element is return type). |
| List<List<List<DartType>>> classMethods; |
| } |
| |
| // Generate seed. By default (no user-defined nonzero seed given), |
| // pick the system's best way of seeding randomness and then pick |
| // a user-visible nonzero seed. |
| int getSeed(String userSeed) { |
| int seed = int.parse(userSeed); |
| if (seed == 0) { |
| Random rand = new Random(); |
| while (seed == 0) { |
| seed = rand.nextInt(1 << 32); |
| } |
| } |
| return seed; |
| } |
| |
| /// Main driver when dartfuzz.dart is run stand-alone. |
| main(List<String> arguments) { |
| final parser = new ArgParser() |
| ..addOption('seed', |
| help: 'random seed (0 forces time-based seed)', defaultsTo: '0') |
| ..addFlag('fp', help: 'enables floating-point operations', defaultsTo: true) |
| ..addFlag('ffi', |
| help: 'enables FFI method calls (default: off)', defaultsTo: false); |
| try { |
| final results = parser.parse(arguments); |
| final seed = getSeed(results['seed']); |
| final fp = results['fp']; |
| final ffi = results['ffi']; |
| final file = new File(results.rest.single).openSync(mode: FileMode.write); |
| new DartFuzz(seed, fp, ffi, file).run(); |
| file.closeSync(); |
| } catch (e) { |
| print('Usage: dart dartfuzz.dart [OPTIONS] FILENAME\n${parser.usage}\n$e'); |
| exitCode = 255; |
| } |
| } |