| // 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_api_table.dart'; |
| import 'dartfuzz_ffi_api.dart'; |
| import 'dartfuzz_type_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.93'; |
| |
| // Restriction on statements and expressions. |
| const int stmtDepth = 1; |
| const int exprDepth = 2; |
| const int nestDepth = 1; |
| const int numStatements = 2; |
| const int numGlobalVars = 4; |
| const int numLocalVars = 4; |
| const int numGlobalMethods = 4; |
| const int numMethodParams = 4; |
| const int numClasses = 4; |
| const int numExtensionMethodsPerClass = 3; |
| const int numDartTypeExtensions = 5; |
| |
| // Naming conventions. |
| const varName = 'var'; |
| const paramName = 'par'; |
| const localName = 'loc'; |
| const fieldName = 'fld'; |
| const methodName = 'foo'; |
| |
| /// Enum for the different types of methods generated by the fuzzer. |
| enum MethodType { |
| globalMethod, |
| ffiMethod, |
| instanceMethod, |
| callMethod, |
| extensionMethod |
| } |
| |
| /// Base class for all methods in the program generated by DartFuzz. |
| abstract class Method { |
| Method(this.name, this.parameters, this.fuzzer) |
| : recursionAllowed = fuzzer.coinFlip() { |
| if (recursionAllowed) { |
| // Add the recursion depth parameter. |
| parameters.add(DartType.INT); |
| } |
| } |
| |
| String get recursionDepthParamName => '$paramName${parameters.length - 1}'; |
| DartType get returnType => parameters[0]; |
| |
| void emitCallParameters(int depth, bool isRecursiveCall, |
| {RhsFilter? rhsFilter}) { |
| if (isRecursiveCall && !recursionAllowed) { |
| throw StateError('Did not expect a recursive call in $name'); |
| } |
| fuzzer.emitParenWrapped(() => fuzzer.emitCommaSeparated((int i) { |
| // If this function can be called recursively, the last parameter is the |
| // recursion depth parameter. |
| if (i == parameters.length - 1 && recursionAllowed) { |
| if (isRecursiveCall) { |
| // This is a recursive call, so we increase the recursion depth |
| // parameter. |
| fuzzer.emit('$recursionDepthParamName + 1'); |
| } else { |
| // This isn't a recursive call. Our recursion depth is 0. |
| fuzzer.emit('0'); |
| } |
| } else { |
| fuzzer.emitExpr(depth, parameters[i], rhsFilter: rhsFilter); |
| } |
| }, parameters.length, start: 1)); |
| } |
| |
| void disableRecursionScope(Function callback) { |
| final originalState = recursionAllowed; |
| recursionAllowed = false; |
| callback(); |
| recursionAllowed = originalState; |
| } |
| |
| void emitRecursionBaseCase() { |
| fuzzer.emitIfStatement(() { |
| fuzzer.emit('$recursionDepthParamName >= '); |
| fuzzer.emitSmallPositiveInt(); |
| }, () { |
| // Temporarily set recursionAllowed to false so that we don't have a |
| // recursive call in the return statement of the base case. |
| disableRecursionScope(fuzzer.emitReturn); |
| return false; |
| }); |
| } |
| |
| void emitFunctionBody() { |
| if (!recursionAllowed && fuzzer.rollDice(10)) { |
| // Emit a method using "=>" syntax. |
| fuzzer.emit(' => '); |
| fuzzer.emitExpr(0, returnType, includeSemicolon: true); |
| } else { |
| fuzzer.emitBraceWrapped(() { |
| assert(fuzzer.localVars.isEmpty); |
| if (recursionAllowed) { |
| emitRecursionBaseCase(); |
| } |
| if (fuzzer.emitStatements(0)) { |
| fuzzer.emitReturn(); |
| } |
| assert(fuzzer.localVars.isEmpty); |
| }); |
| } |
| } |
| |
| void emitFunctionDefinition() { |
| final type = returnType.dartName; |
| fuzzer.emitLn('$type $name', newline: false); |
| fuzzer.emitParenWrapped(() => fuzzer.emitParDecls(parameters)); |
| emitFunctionBody(); |
| fuzzer.emitNewline(); |
| fuzzer.emitNewline(); |
| } |
| |
| String emitCall(int depth, |
| {RhsFilter? rhsFilter, |
| bool includeSemicolon = false, |
| bool isRecursiveCall = false}) { |
| var outputName = name; |
| fuzzer.emitLn(outputName, newline: false); |
| emitCallParameters(depth + 1, isRecursiveCall, rhsFilter: rhsFilter); |
| if (includeSemicolon) { |
| fuzzer.emit(';'); |
| } |
| return outputName; |
| } |
| |
| // Main emitter for a method. |
| void emit() { |
| emitFunctionDefinition(); |
| } |
| |
| final String name; |
| final List<DartType> parameters; |
| final DartFuzz fuzzer; |
| bool recursionAllowed; |
| } |
| |
| /// Class for global methods generated by DartFuzz. |
| class GlobalMethod extends Method { |
| GlobalMethod(String name, List<DartType> parameters, DartFuzz fuzzer) |
| : super(name, parameters, fuzzer); |
| } |
| |
| /// Class for ffi methods generated by DartFuzz. |
| class FfiMethod extends Method { |
| FfiMethod( |
| String namePrefix, int index, List<DartType> parameters, DartFuzz fuzzer) |
| : ffiCastName = '${namePrefix}FfiCast$index', |
| super('${namePrefix}Ffi$index', parameters, fuzzer); |
| |
| @override |
| void emitFunctionBody() { |
| fuzzer.emitBraceWrapped(() { |
| assert(fuzzer.localVars.isEmpty); |
| if (recursionAllowed) { |
| emitRecursionBaseCase(); |
| } |
| if (fuzzer.emitStatements(0)) { |
| fuzzer.emitReturn(); |
| } |
| assert(fuzzer.localVars.isEmpty); |
| }); |
| } |
| |
| @override |
| void emit() { |
| fuzzer.emitFfiTypedef(this); |
| emitFunctionDefinition(); |
| fuzzer.emitFfiCast('$ffiCastName', '$name', '${name}Type', parameters); |
| fuzzer.emitNewline(); |
| fuzzer.emitNewline(); |
| } |
| |
| final String ffiCastName; |
| } |
| |
| /// Class for instance methods generated by DartFuzz. |
| class InstanceMethod extends Method { |
| InstanceMethod( |
| String name, List<DartType> parameters, DartFuzz fuzzer, this.className) |
| : super(name, parameters, fuzzer); |
| |
| @override |
| String emitCall(int depth, |
| {RhsFilter? rhsFilter, |
| bool includeSemicolon = false, |
| bool isRecursiveCall = false}) { |
| var outputName = name; |
| if (fuzzer.currentClassIndex == null) { |
| // If we're calling an instance method from outside the class, then we |
| // should construct an object of that class first. |
| outputName = '$className().$name'; |
| } |
| fuzzer.emitLn(outputName, newline: false); |
| emitCallParameters(depth + 1, isRecursiveCall, rhsFilter: rhsFilter); |
| if (includeSemicolon) { |
| fuzzer.emit(';'); |
| } |
| return outputName; |
| } |
| |
| final String className; |
| } |
| |
| class CallMethod extends Method { |
| CallMethod(List<DartType> parameters, DartFuzz fuzzer, this.className) |
| : super('call', parameters, fuzzer); |
| |
| @override |
| String emitCall(int depth, |
| {RhsFilter? rhsFilter, |
| bool includeSemicolon = false, |
| bool isRecursiveCall = false}) { |
| String outputName; |
| outputName = '$className()'; |
| fuzzer.emitLn(outputName, newline: false); |
| emitCallParameters(depth + 1, isRecursiveCall, rhsFilter: rhsFilter); |
| if (includeSemicolon) { |
| fuzzer.emit(';'); |
| } |
| return outputName; |
| } |
| |
| @override |
| void emit() { |
| // Override the parent class' call method. |
| fuzzer.emit('@override'); |
| fuzzer.emitNewline(); |
| emitFunctionDefinition(); |
| } |
| |
| final String className; |
| } |
| |
| // Class for extension methods generated by DartFuzz. |
| class ExtensionMethod extends Method { |
| ExtensionMethod(String name, List<DartType> parameters, DartFuzz fuzzer, |
| this.className, this.extensionName, this.type) |
| : super(name, parameters, fuzzer); |
| @override |
| String emitCall( |
| int depth, { |
| RhsFilter? rhsFilter, |
| bool includeSemicolon = false, |
| bool isRecursiveCall = false, |
| }) { |
| var outputName = name; |
| |
| // If we're calling an extension method on a class from outside the class, |
| // we must call it using an object of the class or using explicit extension |
| // application. Extension methods on Dart types are presently always called |
| // using a variable of the Dart type or using explicit extension |
| // application. |
| if (fuzzer.currentClassIndex == null || type != null) { |
| var invokingObject = type != null |
| ? fuzzer.pickScalarVar(type!.toNonNullable()) |
| : '$className()'; |
| |
| if (extensionName != null && fuzzer.coinFlip()) { |
| outputName = '$extensionName($invokingObject).$name'; |
| } else { |
| outputName = '$invokingObject.$name'; |
| } |
| } |
| fuzzer.emitLn(outputName, newline: false); |
| emitCallParameters(depth + 1, isRecursiveCall, rhsFilter: rhsFilter); |
| if (includeSemicolon) { |
| fuzzer.emit(';'); |
| } |
| return outputName; |
| } |
| |
| final String className; |
| final String extensionName; |
| final DartType? type; |
| } |
| |
| // Class that tracks the state of the filter applied to the |
| // right-hand-side of an assignment in order to avoid generating |
| // left-hand-side variables. |
| class RhsFilter { |
| RhsFilter(this._remaining, this.lhsVar); |
| static RhsFilter? fromDartType(DartType tp, String lhsVar) { |
| if (DartType.isGrowableType(tp)) { |
| return RhsFilter(1, lhsVar); |
| } |
| return null; |
| } |
| |
| // Clone the current RhsFilter instance and set remaining to 0. |
| // This is used for parameter expressions. |
| static RhsFilter? cloneEmpty(RhsFilter? rhsFilter) => |
| rhsFilter == null ? null : RhsFilter(0, rhsFilter.lhsVar); |
| void consume() => _remaining--; |
| bool get shouldFilter => _remaining <= 0; |
| // Number of times the lhs variable can still be used on the rhs. |
| int _remaining; |
| // The name of the lhs variable to be filtered from the rhs. |
| final String lhsVar; |
| } |
| |
| /// Class that specifies the api for calling library and ffi functions (if |
| /// enabled). |
| class DartApi { |
| DartApi(bool ffi) : typeToLibraryMethods = DartLib.typeToLibraryMethods { |
| if (ffi) { |
| typeToLibraryMethods[DartType.INT] = [ |
| ...[ |
| DartLib('intComputation', |
| [DartType.VOID, ...List<DartType>.filled(4, DartType.INT)], true), |
| DartLib('takeMaxUint16', [DartType.VOID, DartType.INT], true), |
| DartLib( |
| 'sumPlus42', [DartType.VOID, DartType.INT, DartType.INT], true), |
| DartLib('returnMaxUint8', [DartType.VOID, DartType.VOID], true), |
| DartLib('returnMaxUint16', [DartType.VOID, DartType.VOID], true), |
| DartLib('returnMaxUint32', [DartType.VOID, DartType.VOID], true), |
| DartLib('returnMinInt8', [DartType.VOID, DartType.VOID], true), |
| DartLib('returnMinInt16', [DartType.VOID, DartType.VOID], true), |
| DartLib('returnMinInt32', [DartType.VOID, DartType.VOID], true), |
| DartLib('takeMinInt16', [DartType.VOID, DartType.INT], true), |
| DartLib('takeMinInt32', [DartType.VOID, DartType.INT], true), |
| DartLib('uintComputation', |
| [DartType.VOID, ...List<DartType>.filled(4, DartType.INT)], true), |
| DartLib('sumSmallNumbers', |
| [DartType.VOID, ...List<DartType>.filled(6, DartType.INT)], true), |
| DartLib('takeMinInt8', [DartType.VOID, DartType.INT], true), |
| DartLib('takeMaxUint32', [DartType.VOID, DartType.INT], true), |
| DartLib('takeMaxUint8', [DartType.VOID, DartType.INT], true), |
| DartLib('minInt64', [DartType.VOID, DartType.VOID], true), |
| DartLib('minInt32', [DartType.VOID, DartType.VOID], true), |
| // Use small int to avoid overflow divergences due to size |
| // differences in intptr_t on 32-bit and 64-bit platforms. |
| DartLib('sumManyIntsOdd', |
| [DartType.VOID, ...List<DartType>.filled(11, DartType.INT)], true, |
| restrictions: [ |
| Restriction.none, |
| ...List<Restriction>.filled(11, Restriction.small) |
| ]), |
| DartLib('sumManyInts', |
| [DartType.VOID, ...List<DartType>.filled(10, DartType.INT)], true, |
| restrictions: [ |
| Restriction.none, |
| ...List<Restriction>.filled(10, Restriction.small) |
| ]), |
| DartLib('regress37069', |
| [DartType.VOID, ...List<DartType>.filled(11, DartType.INT)], true, |
| restrictions: [ |
| Restriction.none, |
| ...List<Restriction>.filled(11, Restriction.small) |
| ]), |
| ], |
| ...DartLib.intLibs, |
| ]; |
| |
| typeToLibraryMethods[DartType.DOUBLE] = [ |
| if (ffi) ...[ |
| DartLib('times1_337Float', [DartType.VOID, DartType.DOUBLE], true), |
| DartLib( |
| 'sumManyDoubles', |
| [DartType.VOID, ...List<DartType>.filled(10, DartType.DOUBLE)], |
| true), |
| DartLib('times1_337Double', [DartType.VOID, DartType.DOUBLE], true), |
| DartLib( |
| 'sumManyNumbers', |
| [ |
| DartType.VOID, |
| DartType.INT, |
| DartType.DOUBLE, |
| DartType.INT, |
| DartType.DOUBLE, |
| DartType.INT, |
| DartType.DOUBLE, |
| DartType.INT, |
| DartType.DOUBLE, |
| DartType.INT, |
| DartType.DOUBLE, |
| DartType.INT, |
| DartType.DOUBLE, |
| DartType.INT, |
| DartType.DOUBLE, |
| DartType.INT, |
| DartType.DOUBLE, |
| DartType.INT, |
| DartType.DOUBLE, |
| DartType.INT, |
| DartType.DOUBLE |
| ], |
| true), |
| DartLib('inventFloatValue', [DartType.VOID, DartType.VOID], true), |
| DartLib('smallDouble', [DartType.VOID, DartType.VOID], true), |
| ], |
| ...DartLib.doubleLibs, |
| ]; |
| } |
| } |
| |
| final typeToLibraryMethods; |
| } |
| |
| /// Class that generates a random, but runnable Dart program for fuzz testing. |
| class DartFuzz { |
| DartFuzz(this.seed, this.fp, this.ffi, this.flatTp, this.file, |
| {this.minimize = false, this.smask, this.emask}); |
| |
| void run() { |
| // Initialize program variables. |
| rand = Random(seed); |
| currentClassIndex = null; |
| currentMethod = null; |
| currentMethodIndex = null; |
| // Setup Dart types. |
| dartType = DartType.fromDartConfig(enableFp: fp, disableNesting: flatTp); |
| // Setup minimization parameters. |
| initMinimization(); |
| // Setup the library and ffi api. |
| api = DartApi(ffi); |
| // Setup the types. |
| localVars = <DartType?>[]; |
| iterVars = <String>[]; |
| globalVars = fillTypes1(limit: numGlobalVars); |
| globalVars.addAll(dartType.allTypes); |
| globalMethods = getMethods( |
| numGlobalMethods, numMethodParams, MethodType.globalMethod, |
| namePrefix: methodName); |
| classFields = fillTypes2(limit2: numClasses, limit1: numLocalVars); |
| final numClassMethods = 1 + numClasses - classFields.length; |
| classMethods = getClassMethods(classFields.length, numClassMethods, |
| numMethodParams, fillTypes1(limit: numMethodParams)); |
| virtualClassMethods = <Map<int, List<int>>>[]; |
| classParents = <int>[]; |
| // Setup optional ffi methods and types. |
| if (ffi) { |
| globalMethods.addAll(getMethods( |
| numGlobalMethods, numMethodParams, MethodType.ffiMethod, |
| namePrefix: methodName)); |
| } |
| // Generate. |
| emitHeader(); |
| emitVariableDeclarations(varName, globalVars); |
| emitMethods(globalMethods); |
| for (var i = 0; i < numDartTypeExtensions; ++i) { |
| var type = oneOfSet(dartType.allTypes); |
| emitAndAddExtensionMethods(globalMethods, type.name, '${methodName}E$i', |
| '$methodName${i}_Extension', |
| type: type); |
| } |
| emitClasses(); |
| emitMain(); |
| // Sanity. |
| assert(currentClassIndex == null); |
| assert(currentMethod == null); |
| assert(currentMethodIndex == null); |
| assert(indent == 0); |
| assert(nest == 0); |
| assert(localVars.isEmpty); |
| } |
| |
| List<Method> getMethods(int maxMethods, int maxParams, MethodType methodType, |
| {String? className, |
| String? extensionName, |
| String? namePrefix, |
| DartType? type}) { |
| final list = <Method>[]; |
| for (var i = 0, n = chooseOneUpTo(maxMethods); i < n; i++) { |
| final params = fillTypes1( |
| limit: maxParams, isFfi: methodType == MethodType.ffiMethod); |
| switch (methodType) { |
| case MethodType.globalMethod: |
| list.add(GlobalMethod('$namePrefix$i', params, this)); |
| break; |
| case MethodType.ffiMethod: |
| list.add(FfiMethod(namePrefix!, i, params, this)); |
| break; |
| case MethodType.instanceMethod: |
| list.add(InstanceMethod('$namePrefix$i', params, this, className!)); |
| break; |
| case MethodType.extensionMethod: |
| list.add(ExtensionMethod( |
| '$namePrefix$i', params, this, className!, extensionName!, type)); |
| break; |
| default: |
| break; |
| } |
| } |
| return list; |
| } |
| |
| List<List<Method>> getClassMethods(int numClasses, int maxMethods, |
| int maxParams, List<DartType> callMethodParams) { |
| final methodsForAllClasses = <List<Method>>[]; |
| for (var i = 0; i < numClasses; i++) { |
| final methodsForCurrentClass = getMethods( |
| maxMethods, maxParams, MethodType.instanceMethod, |
| className: 'X$i', namePrefix: '$methodName${i}_'); |
| // Add the call method for the current class. The prototype for the call |
| // method is pre-decided. This is because we are possibly overriding the |
| // parent class' call method, in which case the prototype should be the |
| // same. To simplify the dartfuzz logic, all call methods have the same |
| // prototype. |
| methodsForCurrentClass.add(CallMethod(callMethodParams, this, 'X$i')); |
| methodsForAllClasses.add(methodsForCurrentClass); |
| } |
| return methodsForAllClasses; |
| } |
| |
| // |
| // General Helpers. |
| // |
| |
| BigInt genMask(int m) => BigInt.from(1) << m; |
| int choose(int c) => rand.nextInt(c); |
| int chooseOneUpTo(int c) => choose(c) + 1; |
| bool coinFlip() => rand.nextBool(); |
| bool rollDice(int c) => (choose(c) == 0); |
| double uniform() => rand.nextDouble(); |
| |
| // Picks one of the given choices. |
| T oneOf<T>(List<T> choices) => choices[choose(choices.length)]; |
| T oneOfSet<T>(Set<T> choices) => choices.elementAt(choose(choices.length)); |
| |
| // |
| // Code Structure Helpers. |
| // |
| |
| void incIndent() => indent += 2; |
| void decIndent() => indent -= 2; |
| |
| void emitZero() => emit('0'); |
| |
| void emitTryCatchFinally(Function tryBody, Function catchBody, |
| {Function? finallyBody}) { |
| emitLn('try ', newline: false); |
| emitBraceWrapped(() => tryBody()); |
| emit(' on OutOfMemoryError '); |
| emitBraceWrapped(() => emitLn('exit($oomExitCode);', newline: false)); |
| emit(' on StackOverflowError '); |
| emitBraceWrapped(() => emitLn('exit($oomExitCode);', newline: false)); |
| emit(' catch (e, st) '); |
| emitBraceWrapped(catchBody); |
| if (finallyBody != null) { |
| emit(' finally '); |
| emitBraceWrapped(finallyBody); |
| } |
| } |
| |
| dynamic emitWrapped(List<String> pair, Function exprEmitter, |
| {bool shouldIndent = true}) { |
| assert(pair.length == 2); |
| emit(pair[0]); |
| if (shouldIndent) { |
| incIndent(); |
| emitNewline(); |
| } |
| final result = exprEmitter(); |
| if (shouldIndent) { |
| decIndent(); |
| emitNewline(); |
| emitLn(pair[1], newline: false); |
| } else { |
| emit(pair[1]); |
| } |
| return result; |
| } |
| |
| dynamic emitParenWrapped(Function exprEmitter, |
| {bool includeSemicolon = false}) { |
| final result = |
| emitWrapped(const ['(', ')'], exprEmitter, shouldIndent: false); |
| if (includeSemicolon) { |
| emit(';'); |
| } |
| return result; |
| } |
| |
| dynamic emitBraceWrapped(Function exprEmitter, {bool shouldIndent = true}) => |
| emitWrapped(const ['{', '}'], exprEmitter, shouldIndent: shouldIndent); |
| |
| dynamic emitSquareBraceWrapped(Function exprEmitter) => |
| emitWrapped(const ['[', ']'], exprEmitter, shouldIndent: false); |
| |
| dynamic emitCommaSeparated(Function(int) elementBuilder, int length, |
| {int start = 0, bool newline = false}) { |
| for (var i = start; i < length; ++i) { |
| elementBuilder(i); |
| if (i + 1 != length) { |
| emit(',', newline: newline); |
| if (!newline) { |
| emit(' '); |
| } |
| } |
| } |
| } |
| |
| void emitFunctionDefinition(String name, Function body, {String? retType}) { |
| emitIndentation(); |
| if (retType != null) { |
| emit(retType + ' '); |
| } |
| emit(name); |
| emit('() '); // TODO(bkonyi): handle params |
| |
| emitBraceWrapped(body); |
| } |
| |
| bool emitIfStatement( |
| Function ifConditionEmitter, bool Function() ifBodyEmitter, |
| {bool Function()? elseBodyEmitter}) { |
| emitLn('if ', newline: false); |
| emitParenWrapped(ifConditionEmitter); |
| emit(' '); |
| final bool ifMayFallThrough = emitBraceWrapped(ifBodyEmitter); |
| var elseMayFallThrough = true; |
| if (elseBodyEmitter != null) { |
| emit(' else '); |
| elseMayFallThrough = emitBraceWrapped(elseBodyEmitter); |
| } |
| return ifMayFallThrough || elseMayFallThrough; |
| } |
| |
| void emitImport(String library, {String? asName}) => (asName == null) |
| ? emitLn("import '$library';") |
| : emitLn("import '$library' as $asName;"); |
| |
| void emitBinaryComparison(Function e1, String op, Function e2, |
| {bool includeSemicolon = false}) { |
| e1(); |
| emit(' $op '); |
| e2(); |
| if (includeSemicolon) { |
| emit(';'); |
| } |
| } |
| |
| // Randomly specialize interface if possible. E.g. num to int. |
| DartType maybeSpecializeInterface(DartType tp) { |
| if (!dartType.isSpecializable(tp)) return tp; |
| var resolvedTp = oneOfSet(dartType.interfaces(tp)); |
| return resolvedTp; |
| } |
| |
| // |
| // Minimization components. |
| // |
| |
| void initMinimization() { |
| stmtCntr = 0; |
| exprCntr = 0; |
| skipStmt = false; |
| skipExpr = false; |
| } |
| |
| void emitMinimizedLiteral(DartType tp) { |
| switch (tp) { |
| case DartType.BOOL: |
| emit('true'); |
| break; |
| case DartType.INT: |
| emit('1'); |
| break; |
| case DartType.DOUBLE: |
| emit('1.0'); |
| break; |
| case DartType.STRING: |
| emit('"a"'); |
| break; |
| case DartType.LIST_INT: |
| emit('[1]'); |
| break; |
| case DartType.SET_INT: |
| emit('{1}'); |
| break; |
| case DartType.MAP_INT_STRING: |
| emit('{1: "a"}'); |
| break; |
| default: |
| throw 'Unknown DartType $tp'; |
| } |
| } |
| |
| // Process the opening of a statement. |
| // Determine whether the statement should be skipped based on the |
| // statement index stored in stmtCntr and the statement mask stored |
| // in smask. |
| // Returns true if the statement should be skipped. |
| bool processStmtOpen() { |
| // Do nothing if we are not in minimization mode. |
| if (!minimize) { |
| return false; |
| } |
| // Check whether the bit for the current statement number is set in the |
| // statement bitmap. If so skip this statement. |
| final newMask = genMask(stmtCntr); |
| final maskBitSet = (smask! & newMask) != BigInt.zero; |
| // Statements are nested, therefore masking one statement like e.g. |
| // a for loop leads to other statements being omitted. |
| // Here we update the statement mask to include the additionally |
| // omitted statements. |
| if (skipStmt) { |
| smask = smask! | newMask; |
| } |
| // Increase the statement counter. |
| stmtCntr++; |
| if (!skipStmt && maskBitSet) { |
| skipStmt = true; |
| return true; |
| } |
| return false; |
| } |
| |
| // Process the closing of a statement. |
| // The variable resetSkipStmt indicates whether this |
| // statement closes the sequence of skipped statement. |
| // E.g. the end of a loop where all contained statements |
| // were skipped. |
| void processStmtClose(bool resetSkipStmt) { |
| if (!minimize) { |
| return; |
| } |
| if (resetSkipStmt) { |
| skipStmt = false; |
| } |
| } |
| |
| // Process the opening of an expression. |
| // Determine whether the expression should be skipped based on the |
| // expression index stored in exprCntr and the expression mask stored |
| // in emask. |
| // Returns true is the expression is skipped. |
| bool processExprOpen(DartType tp) { |
| // Do nothing if we are not in minimization mode. |
| if (!minimize) { |
| return false; |
| } |
| // Check whether the bit for the current expression number is set in the |
| // expression bitmap. If so skip this expression. |
| final newMask = genMask(exprCntr); |
| final maskBitSet = (emask! & newMask) != BigInt.zero; |
| // Expressions are nested, therefore masking one expression like e.g. |
| // a for loop leads to other expressions being omitted. |
| // Similarly, if the whole statement is skipped, all the expressions |
| // within that statement are implicitly masked. |
| // Here we update the expression mask to include the additionally |
| // omitted expressions. |
| if (skipExpr || skipStmt) { |
| emask = emask! | newMask; |
| } |
| exprCntr++; |
| if (skipStmt) { |
| return false; |
| } |
| if (!skipExpr && maskBitSet) { |
| emitMinimizedLiteral(tp); |
| skipExpr = true; |
| return true; |
| } |
| return false; |
| } |
| |
| void processExprClose(bool resetExprStmt) { |
| if (!minimize || skipStmt) { |
| return; |
| } |
| if (resetExprStmt) { |
| skipExpr = false; |
| } |
| } |
| |
| // |
| // 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 --${flatTp ? "" : "no-"}flat'); |
| emitLn('// @dart=2.14'); |
| emitNewline(); |
| emitImport('dart:async'); |
| emitImport('dart:cli'); |
| emitImport('dart:collection'); |
| emitImport('dart:convert'); |
| emitImport('dart:core'); |
| emitImport('dart:io'); |
| emitImport('dart:isolate'); |
| emitImport('dart:math'); |
| emitImport('dart:typed_data'); |
| if (ffi) { |
| emitImport('dart:ffi', asName: 'ffi'); |
| emitLn(DartFuzzFfiApi.ffiapi); |
| } |
| emitNewline(); |
| } |
| |
| void emitFfiCast(String dartFuncName, String ffiFuncName, String typeName, |
| List<DartType> pars) { |
| emit('${pars[0].name} Function'); |
| emitParenWrapped(() => emitCommaSeparated( |
| (int i) => emit('${pars[i].name}'), pars.length, |
| start: 1)); |
| emit(' $dartFuncName = ffi.Pointer.fromFunction<$typeName>'); |
| emitParenWrapped(() { |
| emit('$ffiFuncName, '); |
| emitLiteral(0, pars[0], smallPositiveValue: true); |
| }); |
| emit('.cast<ffi.NativeFunction<$typeName>>().asFunction();'); |
| emitNewline(); |
| } |
| |
| void emitMethods(List<Method> methods) { |
| for (var i = 0; i < methods.length; i++) { |
| currentMethod = methods[i]; |
| currentMethodIndex = i; |
| currentMethod!.emit(); |
| currentMethod = null; |
| currentMethodIndex = null; |
| } |
| } |
| |
| // Randomly overwrite some methods from the parent classes. |
| void emitVirtualMethods() { |
| final currentClassTmp = currentClassIndex; |
| var parentClass = classParents[currentClassIndex!]; |
| final vcm = <int, List<int>>{}; |
| // Chase randomly up in class hierarchy. |
| while (parentClass >= 0) { |
| vcm[parentClass] = <int>[]; |
| for (var j = 0, n = classMethods[parentClass].length; j < n; j++) { |
| // Call methods are presently always already overridden, so we |
| // shouldn't override them here. |
| if (rollDice(8) && !(classMethods[parentClass][j] is CallMethod)) { |
| currentClassIndex = parentClass; |
| currentMethod = classMethods[parentClass][j]; |
| currentMethodIndex = j; |
| classMethods[parentClass][j].emit(); |
| vcm[parentClass]!.add(currentMethodIndex!); |
| currentClassIndex = null; |
| currentMethod = null; |
| currentMethodIndex = null; |
| } |
| } |
| if (coinFlip() || classParents.length > parentClass) { |
| break; |
| } else { |
| parentClass = classParents[parentClass]; |
| } |
| } |
| currentClassIndex = currentClassTmp; |
| virtualClassMethods.add(vcm); |
| } |
| |
| void emitClasses() { |
| assert(classFields.length == classMethods.length); |
| for (var i = 0; i < classFields.length; i++) { |
| if (i == 0) { |
| classParents.add(-1); |
| emit('class X0 '); |
| } else { |
| final parentClass = choose(i); |
| classParents.add(parentClass); |
| if (coinFlip()) { |
| // Inheritance |
| emit('class X$i extends X$parentClass '); |
| } else { |
| // Mixin |
| if (classParents[parentClass] >= 0) { |
| emit( |
| 'class X$i extends X${classParents[parentClass]} with X$parentClass '); |
| } else { |
| emit('class X$i with X$parentClass '); |
| } |
| } |
| } |
| emitBraceWrapped(() { |
| emitVariableDeclarations('$fieldName${i}_', classFields[i]); |
| currentClassIndex = i; |
| emitVirtualMethods(); |
| emitMethods(classMethods[currentClassIndex!]); |
| emitFunctionDefinition('run', () { |
| if (i > 0) { |
| // FIXME(bkonyi): fix potential issue where we try to apply a class |
| // as a mixin when it calls super. |
| emitLn('super.run();'); |
| } |
| assert(localVars.isEmpty); |
| emitStatements(0); |
| assert(localVars.isEmpty); |
| }, retType: 'void'); |
| }); |
| emitNewline(); |
| emitNewline(); |
| emitAndAddExtensionMethods( |
| classMethods[currentClassIndex!], |
| 'X$currentClassIndex', |
| 'XE$currentClassIndex', |
| '$methodName${currentClassIndex}_Extension'); |
| currentClassIndex = null; |
| } |
| } |
| |
| void emitAndAddExtensionMethods( |
| List<Method> methodList, className, extensionName, namePrefix, |
| {DartType? type}) { |
| var endIndex = methodList.length; |
| methodList.addAll(getMethods(numExtensionMethodsPerClass, numMethodParams, |
| MethodType.extensionMethod, |
| className: className, |
| // Randomly select between named and anonymous extensions. |
| extensionName: coinFlip() ? extensionName : '', |
| namePrefix: namePrefix, |
| type: type)); |
| emit('extension $extensionName on $className '); |
| emitBraceWrapped(() { |
| // Emit the newly added methods. |
| for (var i = endIndex; i < methodList.length; i++) { |
| currentMethod = methodList[i]; |
| currentMethodIndex = i; |
| methodList[i].emit(); |
| currentMethod = null; |
| currentMethodIndex = null; |
| } |
| }); |
| emitNewline(); |
| emitNewline(); |
| } |
| |
| void emitLoadFfiLib() { |
| if (ffi) { |
| emitLn('// The following throws an uncaught exception if the ffi library ' |
| 'is not found.'); |
| emitLn('// By not catching this exception, we terminate the program with ' |
| 'a full stack trace'); |
| emitLn('// which, in turn, flags the problem prominently'); |
| emitIfStatement(() => emit('ffiTestFunctions == null'), |
| () => emitPrint('Did not load ffi test functions')); |
| emitNewline(); |
| } |
| } |
| |
| void emitMain() => emitFunctionDefinition('main', () { |
| emitLoadFfiLib(); |
| |
| // Call each global method once. |
| for (var i = 0; i < globalMethods.length; i++) { |
| late String outputName; |
| emitTryCatchFinally( |
| () => outputName = |
| globalMethods[i].emitCall(1, includeSemicolon: true), |
| () => emitPrint('${outputName}() throws')); |
| emitNewline(); |
| } |
| |
| // Call each class method once. |
| for (var i = 0; i < classMethods.length; i++) { |
| for (var j = 0; j < classMethods[i].length; j++) { |
| late String outputName; |
| emitNewline(); |
| emitTryCatchFinally( |
| () => outputName = |
| classMethods[i][j].emitCall(1, includeSemicolon: true), |
| () => emitPrint('$outputName throws')); |
| } |
| // Call each virtual class method once. |
| var parentClass = classParents[i]; |
| while (parentClass >= 0) { |
| if (virtualClassMethods[i].containsKey(parentClass)) { |
| for (var j = 0; |
| j < virtualClassMethods[i][parentClass]!.length; |
| j++) { |
| late String outputName; |
| emitNewline(); |
| emitTryCatchFinally( |
| () => outputName = classMethods[parentClass][j] |
| .emitCall(1, includeSemicolon: true), |
| () => emitPrint('$outputName throws')); |
| } |
| } |
| parentClass = classParents[parentClass]; |
| } |
| } |
| |
| emitNewline(); |
| emitTryCatchFinally(() { |
| emitLn('X${classFields.length - 1}().run();', newline: false); |
| }, () { |
| emitPrint('X${classFields.length - 1}().run() throws'); |
| }); |
| |
| emitNewline(); |
| emitTryCatchFinally(() { |
| for (var i = 0; i < globalVars.length; i++) { |
| emitPrint('$varName$i: \$$varName$i'); |
| emitNewline(); |
| } |
| }, () => emitPrint('print() throws')); |
| }); |
| |
| // |
| // Declarations. |
| // |
| |
| void emitVariableDeclarations(String name, List<DartType> vars) { |
| for (var i = 0; i < vars.length; i++) { |
| var tp = vars[i]; |
| final varName = '$name$i'; |
| emitVariableDeclaration(varName, tp, |
| initializerEmitter: () => emitConstructorOrLiteral(0, tp)); |
| } |
| emitNewline(); |
| } |
| |
| void emitVariableDeclaration(String name, DartType tp, |
| {Function? initializerEmitter, |
| bool indent = true, |
| bool newline = true, |
| bool includeSemicolon = true}) { |
| final typeName = tp.dartName; |
| if (indent) { |
| emitIndentation(); |
| } |
| emit('$typeName $name', newline: false); |
| if (initializerEmitter != null) { |
| emit(' = '); |
| initializerEmitter(); |
| } |
| if (includeSemicolon) { |
| emit(';', newline: newline); |
| } |
| } |
| |
| void emitParDecls(List<DartType> pars) => emitCommaSeparated((int i) { |
| var tp = pars[i]; |
| emit('${tp.dartName} $paramName$i'); |
| }, pars.length, start: 1); |
| |
| // |
| // Comments (for FE and analysis tools). |
| // |
| |
| void emitComment() { |
| switch (choose(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() { |
| final tp = oneOfSet(dartType.allTypes); |
| String assignOp; |
| if (DartType.isGrowableType(tp)) { |
| // Assignments like *= and += on growable types (String, List, ...) |
| // may lead to OOM, especially within loops. |
| // TODO: Implement a more specific heuristic that selectively allows |
| // modifying assignment operators (like += *=) for growable types. |
| assignOp = '='; |
| } else { |
| // Select one of the assign operations for the given type. |
| var assignOps = dartType.assignOps(tp); |
| if (assignOps.isEmpty) { |
| throw 'No assign operation for $tp'; |
| } |
| assignOp = oneOfSet(assignOps); |
| } |
| emitIndentation(); |
| // Emit a variable of the lhs type. |
| final emittedVar = emitVar(0, tp, isLhs: true, assignOp: assignOp)!; |
| var rhsFilter = RhsFilter.fromDartType(tp, emittedVar); |
| emit(' $assignOp '); |
| // Select one of the possible rhs types for the given lhs type and assign |
| // operation. |
| var rhsTypes = dartType.assignOpRhs(tp, assignOp); |
| if (rhsTypes.isEmpty) { |
| throw 'No rhs type for assign $tp $assignOp'; |
| } |
| var rhsType = oneOfSet(rhsTypes); |
| emitExpr(0, rhsType, rhsFilter: rhsFilter, includeSemicolon: true); |
| return true; |
| } |
| |
| // Emit a print statement. |
| bool emitPrint([String? body]) { |
| emitLn('print', newline: false); |
| emitParenWrapped(() { |
| if (body != null) { |
| emit("'$body'"); |
| } else { |
| var tp = oneOfSet(dartType.allTypes); |
| emitExpr(0, tp); |
| } |
| }, includeSemicolon: true); |
| return true; |
| } |
| |
| // Emit a return statement. |
| bool emitReturn() { |
| var proto = getCurrentProto(); |
| if (proto == null || proto[0] == DartType.VOID) { |
| emitLn('return;'); |
| } else { |
| emitLn('return ', newline: false); |
| emitExpr(0, proto[0], includeSemicolon: true); |
| } |
| return false; |
| } |
| |
| // Emit a throw statement. |
| bool emitThrow() { |
| var tp; |
| do { |
| tp = oneOfSet(dartType.allTypes).toNonNullable(); |
| } while (tp == DartType.NULL); |
| emitLn('throw ', newline: false); |
| emitExpr(0, tp, includeSemicolon: true); |
| return false; |
| } |
| |
| // Emit a one-way if statement. |
| bool emitIf1(int depth) => emitIfStatement( |
| () => emitExpr(0, DartType.BOOL), () => emitStatements(depth + 1)); |
| |
| // Emit a two-way if statement. |
| bool emitIf2(int depth) => emitIfStatement( |
| () => emitExpr(0, DartType.BOOL), () => emitStatements(depth + 1), |
| elseBodyEmitter: () => emitStatements(depth + 1)); |
| |
| // Emit a simple increasing for-loop. |
| bool emitFor(int depth) { |
| // Make deep nesting of loops increasingly unlikely. |
| if (choose(nest + 1) > nestDepth) { |
| return emitAssign(); |
| } |
| final i = localVars.length; |
| emitLn('for ', newline: false); |
| emitParenWrapped(() { |
| final name = '$localName$i'; |
| emitVariableDeclaration(name, DartType.INT, |
| initializerEmitter: emitZero, newline: false, indent: false); |
| emitBinaryComparison(() => emit(name), '<', emitSmallPositiveInt, |
| includeSemicolon: true); |
| emit('$name++'); |
| }); |
| emitBraceWrapped(() { |
| nest++; |
| iterVars.add('$localName$i'); |
| localVars.add(DartType.INT); |
| emitStatements(depth + 1); |
| localVars.removeLast(); |
| iterVars.removeLast(); |
| nest--; |
| }); |
| return true; |
| } |
| |
| // Emit a simple membership for-in-loop. |
| bool emitForIn(int depth) { |
| // Make deep nesting of loops increasingly unlikely. |
| if (choose(nest + 1) > nestDepth) { |
| return emitAssign(); |
| } |
| final i = localVars.length; |
| // Select one iterable type to be used in 'for in' statement. |
| final iterType = oneOfSet(dartType.iterableTypes1); |
| // Get the element type contained within the iterable type. |
| final elementType = dartType.elementType(iterType); |
| if (elementType == null) { |
| throw 'No element type for iteration type ${iterType.name}'; |
| } |
| emitLn('for ', newline: false); |
| emitParenWrapped(() { |
| emit('${elementType.dartName} $localName$i in '); |
| localVars.add(null); // declared, but don't use |
| emitExpr(0, iterType.toNonNullable()); |
| localVars.removeLast(); // will get type |
| }); |
| emitBraceWrapped(() { |
| nest++; |
| localVars.add(elementType); |
| emitStatements(depth + 1); |
| localVars.removeLast(); |
| nest--; |
| }); |
| return true; |
| } |
| |
| // Emit a simple membership forEach loop. |
| bool emitForEach(int depth) { |
| // Make deep nesting of loops increasingly unlikely. |
| if (choose(nest + 1) > nestDepth) { |
| return emitAssign(); |
| } |
| emitIndentation(); |
| |
| // Select one map type to be used in forEach loop. |
| final mapType = oneOfSet(dartType.mapTypes); |
| final emittedVar = emitScalarVar(mapType.toNonNullable(), isLhs: false); |
| iterVars.add(emittedVar); |
| emit('.forEach'); |
| final i = localVars.length; |
| final j = i + 1; |
| emitParenWrapped(() { |
| emitParenWrapped(() => emit('$localName$i, $localName$j')); |
| emitBraceWrapped(() { |
| // Reset, since forEach cannot break out of own or enclosing context. |
| final nestTmp = nest; |
| nest = 0; |
| // Reset, since return type of forEach is void. |
| final currentMethodIndexTemp = currentMethodIndex; |
| currentMethodIndex = null; |
| |
| // Get the type of the map key and add it to the local variables. |
| localVars.add(dartType.indexType(mapType)); |
| // Get the type of the map values and add it to the local variables. |
| localVars.add(dartType.elementType(mapType)); |
| emitStatements(depth + 1); |
| localVars.removeLast(); |
| localVars.removeLast(); |
| |
| currentMethodIndex = currentMethodIndexTemp; |
| nest = nestTmp; |
| }); |
| }, includeSemicolon: true); |
| return true; |
| } |
| |
| // Emit a while-loop. |
| bool emitWhile(int depth) { |
| // Make deep nesting of loops increasingly unlikely. |
| if (choose(nest + 1) > nestDepth) { |
| return emitAssign(); |
| } |
| final i = localVars.length; |
| emitIndentation(); |
| emitBraceWrapped(() { |
| final name = '$localName$i'; |
| emitVariableDeclaration(name, DartType.INT, |
| initializerEmitter: () => emitSmallPositiveInt()); |
| emitLn('while ', newline: false); |
| emitParenWrapped( |
| () => emitBinaryComparison(() => emit('--$name'), '>', emitZero)); |
| emitBraceWrapped(() { |
| nest++; |
| iterVars.add(name); |
| localVars.add(DartType.INT); |
| emitStatements(depth + 1); |
| localVars.removeLast(); |
| iterVars.removeLast(); |
| nest--; |
| }); |
| }); |
| return true; |
| } |
| |
| // Emit a do-while-loop. |
| bool emitDoWhile(int depth) { |
| // Make deep nesting of loops increasingly unlikely. |
| if (choose(nest + 1) > nestDepth) { |
| return emitAssign(); |
| } |
| final i = localVars.length; |
| emitIndentation(); |
| emitBraceWrapped(() { |
| final name = '$localName$i'; |
| emitVariableDeclaration(name, DartType.INT, initializerEmitter: emitZero); |
| emitLn('do ', newline: false); |
| emitBraceWrapped(() { |
| nest++; |
| iterVars.add(name); |
| localVars.add(DartType.INT); |
| emitStatements(depth + 1); |
| localVars.removeLast(); |
| iterVars.removeLast(); |
| nest--; |
| }); |
| emit(' while '); |
| emitParenWrapped( |
| () => emitBinaryComparison( |
| () => emit('++$name'), '<', emitSmallPositiveInt), |
| includeSemicolon: true); |
| }); |
| emitNewline(); |
| return true; |
| } |
| |
| // Emit a break/continue when inside iteration. |
| bool emitBreakOrContinue(int depth) { |
| if (nest > 0) { |
| switch (choose(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) { |
| void emitCase(Function bodyEmitter, {int? kase}) { |
| if (kase == null) { |
| emitLn('default: ', newline: false); |
| } else { |
| emitLn('case $kase: ', newline: false); |
| } |
| emitBraceWrapped(() { |
| bodyEmitter(); |
| emitNewline(); |
| emitLn('break;', |
| newline: false); // always generate, avoid FE complaints |
| }); |
| } |
| |
| emitLn('switch ', newline: false); |
| emitParenWrapped(() => emitExpr(0, DartType.INT)); |
| emitBraceWrapped(() { |
| var start = choose(1 << 32); |
| var step = chooseOneUpTo(10); |
| final maxCases = 3; |
| for (var i = 0; i < maxCases; i++, start += step) { |
| emitCase(() => emitStatement(depth + 1), |
| kase: (i == 2 && coinFlip()) ? null : start); |
| if (i + 1 != maxCases) { |
| emitNewline(); |
| } |
| } |
| }); |
| return true; |
| } |
| |
| // Emit a new program scope that introduces a new local variable. |
| bool emitScope(int depth) { |
| emitIndentation(); |
| emitBraceWrapped(() { |
| var tp = oneOfSet(dartType.allTypes); |
| final i = localVars.length; |
| final name = '$localName$i'; |
| emitVariableDeclaration(name, tp, initializerEmitter: () { |
| localVars.add(null); // declared, but don't use |
| emitExpr(0, tp); |
| localVars.removeLast(); // will get type |
| }); |
| localVars.add(tp); |
| emitStatements(depth + 1); |
| localVars.removeLast(); |
| }); |
| return true; |
| } |
| |
| // Emit try/catch/finally. |
| bool emitTryCatch(int depth) { |
| final emitStatementsClosure = () => emitStatements(depth + 1); |
| emitLn('try ', newline: false); |
| emitBraceWrapped(emitStatementsClosure); |
| emit(' on OutOfMemoryError '); |
| emitBraceWrapped(() => emitLn('exit($oomExitCode);', newline: false)); |
| emit(' on StackOverflowError '); |
| emitBraceWrapped(() => emitLn('exit($oomExitCode);', newline: false)); |
| emit(' catch (exception, stackTrace) ', newline: false); |
| emitBraceWrapped(emitStatementsClosure); |
| if (coinFlip()) { |
| emit(' finally ', newline: false); |
| emitBraceWrapped(emitStatementsClosure); |
| } |
| return true; |
| } |
| |
| // Emit a single statement. |
| bool emitSingleStatement(int depth) { |
| // Throw in a comment every once in a while. |
| if (rollDice(10)) { |
| emitComment(); |
| } |
| // Continuing nested statements becomes less likely as the depth grows. |
| if (choose(depth + 1) > stmtDepth) { |
| return emitAssign(); |
| } |
| // Possibly nested statement. |
| switch (choose(17)) { |
| // 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); |
| case 13: |
| return emitForEach(depth); |
| case 14: |
| emitLibraryCall(depth, DartType.VOID, includeSemicolon: true); |
| return true; |
| default: |
| return emitAssign(); |
| } |
| } |
| |
| // Emit a statement (main entry). |
| // Returns true if code *may* fall-through |
| // (not made too advanced to avoid FE complaints). |
| bool emitStatement(int depth) { |
| final resetSkipStmt = processStmtOpen(); |
| var ret = emitSingleStatement(depth); |
| processStmtClose(resetSkipStmt); |
| return ret; |
| } |
| |
| // Emit statements. Returns true if code may fall-through. |
| bool emitStatements(int depth) { |
| var s = chooseOneUpTo(numStatements); |
| for (var i = 0; i < s; i++) { |
| if (!emitStatement(depth)) { |
| return false; // rest would be dead code |
| } |
| if (i + 1 != s) { |
| emitNewline(); |
| } |
| } |
| return true; |
| } |
| |
| // |
| // Expressions. |
| // |
| |
| void emitBool() => emit(coinFlip() ? 'true' : 'false'); |
| |
| void emitNull() => emit('null'); |
| |
| void emitSmallPositiveInt({int limit = 50, bool includeSemicolon = false}) { |
| emit('${choose(limit)}'); |
| if (includeSemicolon) { |
| emit(';'); |
| } |
| } |
| |
| void emitSmallNegativeInt() => emit('-${choose(100)}'); |
| |
| void emitInt() { |
| switch (choose(7)) { |
| // Favors small ints. |
| case 0: |
| case 1: |
| case 2: |
| emitSmallPositiveInt(); |
| break; |
| case 3: |
| case 4: |
| case 5: |
| emitSmallNegativeInt(); |
| break; |
| default: |
| emit('${oneOf(interestingIntegers)}'); |
| break; |
| } |
| } |
| |
| void emitDouble() => emit('${uniform()}'); |
| |
| void emitNum({bool smallPositiveValue = false}) { |
| if (!fp || coinFlip()) { |
| if (smallPositiveValue) { |
| emitSmallPositiveInt(); |
| } else { |
| emitInt(); |
| } |
| } else { |
| emitDouble(); |
| } |
| } |
| |
| void emitChar() { |
| switch (choose(10)) { |
| // Favors regular char. |
| case 0: |
| emit(oneOf(interestingChars)); |
| break; |
| default: |
| emit(regularChars[choose(regularChars.length)]); |
| break; |
| } |
| } |
| |
| void emitString({int length = 8}) { |
| final n = choose(length); |
| emit("'"); |
| for (var i = 0; i < n; i++) { |
| emitChar(); |
| } |
| emit("'"); |
| } |
| |
| void emitElementExpr(int depth, DartType tp, |
| {RhsFilter? rhsFilter, bool isConst = false}) { |
| // Inside a constant collection, keep collection elements constants too. |
| if (isConst) { |
| if (DartType.isCollectionType(tp)) { |
| emitConstCollection(depth + 1, tp, rhsFilter: rhsFilter); |
| return; |
| } |
| } |
| // Use literals outside a class or inside a constant collection. |
| if (currentMethodIndex == null || isConst) { |
| emitLiteral(depth, tp, rhsFilter: rhsFilter); |
| } else { |
| emitExpr(depth, tp, rhsFilter: rhsFilter); |
| } |
| } |
| |
| void emitElement(int depth, DartType tp, |
| {RhsFilter? rhsFilter, bool isConst = false}) { |
| // Get the element type contained in type tp. |
| // E.g. element type of List<String> is String. |
| final elementType = dartType.elementType(tp); |
| // Decide whether we need to generate Map or List/Set type elements. |
| if (DartType.isMapType(tp)) { |
| // Emit construct for the map key type. |
| final indexType = dartType.indexType(tp); |
| emitIndentation(); |
| emitElementExpr(depth, indexType, rhsFilter: rhsFilter, isConst: isConst); |
| emit(' : '); |
| // Emit construct for the map value type. |
| emitElementExpr(depth, elementType, |
| rhsFilter: rhsFilter, isConst: isConst); |
| } else { |
| // List and Set types. |
| emitElementExpr(depth, elementType, |
| rhsFilter: rhsFilter, isConst: isConst); |
| } |
| } |
| |
| void emitCollectionElement(int depth, DartType tp, {RhsFilter? rhsFilter}) { |
| var r = (depth <= exprDepth) ? choose(10) : 10; |
| // TODO (felih): disable complex collection constructs for new types for |
| // now. |
| if (!{DartType.MAP_INT_STRING, DartType.LIST_INT, DartType.SET_INT} |
| .contains(tp)) { |
| emitElement(depth, tp, rhsFilter: rhsFilter); |
| return; |
| } |
| switch (r) { |
| // Favors elements over control-flow collections. |
| case 0: |
| emitLn('...', newline: false); // spread |
| emitCollection(depth + 1, tp, rhsFilter: rhsFilter); |
| break; |
| case 1: |
| emitLn('if ', newline: false); |
| emitParenWrapped(() => |
| emitElementExpr(depth + 1, DartType.BOOL, rhsFilter: rhsFilter)); |
| emitCollectionElement(depth + 1, tp, rhsFilter: rhsFilter); |
| if (coinFlip()) { |
| emitNewline(); |
| emitLn('else ', newline: false); |
| emitCollectionElement(depth + 1, tp, rhsFilter: rhsFilter); |
| } |
| break; |
| case 2: |
| { |
| final i = localVars.length; |
| // TODO (felih): update to use new type system. Add types like |
| // LIST_STRING etc. |
| emitLn('for ', newline: false); |
| emitParenWrapped(() { |
| final local = '$localName$i'; |
| iterVars.add(local); |
| // For-loop (induction, list, set). |
| localVars.add(null); // declared, but don't use |
| switch (choose(3)) { |
| case 0: |
| emitVariableDeclaration(local, DartType.INT, |
| initializerEmitter: emitZero, indent: false); |
| emitBinaryComparison(() => emit(local), '<', |
| () => emitSmallPositiveInt(limit: 16), |
| includeSemicolon: true); |
| emit('$local++'); |
| break; |
| case 1: |
| emitVariableDeclaration(local, DartType.INT, |
| includeSemicolon: false, indent: false); |
| emit(' in '); |
| emitCollection(depth + 1, DartType.LIST_INT, |
| rhsFilter: rhsFilter); |
| break; |
| default: |
| emitVariableDeclaration(local, DartType.INT, |
| includeSemicolon: false, indent: false); |
| emit(' in '); |
| emitCollection(depth + 1, DartType.SET_INT, |
| rhsFilter: rhsFilter); |
| break; |
| } |
| localVars.removeLast(); // will get type |
| }); |
| nest++; |
| localVars.add(DartType.INT); |
| emitNewline(); |
| emitCollectionElement(depth + 1, tp, rhsFilter: rhsFilter); |
| localVars.removeLast(); |
| iterVars.removeLast(); |
| nest--; |
| break; |
| } |
| default: |
| emitElement(depth, tp, rhsFilter: rhsFilter); |
| break; |
| } |
| } |
| |
| void emitCollection(int depth, DartType tp, {RhsFilter? rhsFilter}) { |
| var l, r; |
| if (DartType.isListType(tp)) { |
| var elementType = dartType.elementType(tp); |
| l = '<${elementType.dartName}>['; |
| r = ']'; |
| } else if (DartType.isSetType(tp)) { |
| var elementType = dartType.elementType(tp); |
| l = '<${elementType.dartName}>{'; |
| r = '}'; |
| } else if (DartType.isMapType(tp)) { |
| var indexType = dartType.indexType(tp); |
| var elementType = dartType.elementType(tp); |
| l = '<${indexType.dartName},${elementType.dartName}>{'; |
| r = '}'; |
| } else { |
| throw "Unrecognized collection type $tp"; |
| } |
| emitWrapped([l, r], () { |
| // Collection length decreases as depth increases. |
| var collectionLength = max(1, 8 - depth); |
| emitCommaSeparated( |
| (int _) => emitCollectionElement(depth, tp, rhsFilter: rhsFilter), |
| chooseOneUpTo(collectionLength), |
| newline: DartType.isMapType(tp)); |
| }, shouldIndent: DartType.isMapType(tp)); |
| } |
| |
| void emitConstCollection(int depth, DartType tp, {RhsFilter? rhsFilter}) { |
| var l, r, canHaveElements; |
| if (DartType.isListType(tp)) { |
| var elementType = dartType.elementType(tp); |
| l = 'const <${elementType.dartName}>['; |
| r = ']'; |
| canHaveElements = true; |
| } else if (DartType.isSetType(tp)) { |
| var elementType = dartType.elementType(tp); |
| l = 'const <${elementType.dartName}>{'; |
| r = '}'; |
| canHaveElements = (elementType != DartType.DOUBLE) && |
| (elementType != DartType.DOUBLE_NULLABLE); |
| } else if (DartType.isMapType(tp)) { |
| var indexType = dartType.indexType(tp); |
| var elementType = dartType.elementType(tp); |
| l = 'const <${indexType.dartName},${elementType.dartName}>{'; |
| r = '}'; |
| canHaveElements = (indexType != DartType.DOUBLE) && |
| (indexType != DartType.DOUBLE_NULLABLE); |
| } else { |
| throw "Unrecognized collection type $tp"; |
| } |
| if (!canHaveElements) { |
| // Dart does not like floating-point elements. A key would, for |
| // example, yield "The key does not have a primitive operator '=='". |
| // So emit an empty collection. |
| emit(l); |
| emit(r); |
| return; |
| } |
| emitWrapped([l, r], |
| () => emitElement(depth, tp, rhsFilter: rhsFilter, isConst: true), |
| shouldIndent: DartType.isMapType(tp)); |
| } |
| |
| void emitLiteral(int depth, DartType tp, |
| {bool smallPositiveValue = false, RhsFilter? rhsFilter}) { |
| if (tp.isNullable) { |
| if (choose(20) == 0) { |
| emitNull(); |
| return; |
| } |
| tp = tp.toNonNullable(); |
| } |
| // Randomly specialize interface if possible. E.g. num to int. |
| tp = maybeSpecializeInterface(tp); |
| if (tp == DartType.NULL) { |
| emitNull(); |
| } else if (tp == DartType.BOOL) { |
| emitBool(); |
| } else if (tp == DartType.INT) { |
| if (smallPositiveValue) { |
| emitSmallPositiveInt(); |
| } else { |
| emitInt(); |
| } |
| } else if (tp == DartType.DOUBLE) { |
| emitDouble(); |
| } else if (tp == DartType.NUM) { |
| emitNum(smallPositiveValue: smallPositiveValue); |
| } else if (tp == DartType.STRING) { |
| emitString(); |
| } else if (tp == DartType.ENDIAN) { |
| // The Endian type doesn't have a public constructor, so we emit a |
| // library call instead. |
| emitLibraryCall(depth, tp); |
| } else if (dartType.constructors(tp).isNotEmpty) { |
| // Constructors serve as literals for non trivially constructable types. |
| // Important note: We have to test for existence of a non trivial |
| // constructor before testing for list type assiciation, since some types |
| // like ListInt32 are of list type but can not be constructed |
| // from a literal. |
| emitConstructorOrLiteral(depth + 1, tp, rhsFilter: rhsFilter); |
| } else if (DartType.isCollectionType(tp)) { |
| final resetExprStmt = processExprOpen(tp); |
| emitCollection(depth + 1, tp, rhsFilter: rhsFilter); |
| processExprClose(resetExprStmt); |
| } else { |
| throw 'Can not emit literal for $tp'; |
| } |
| } |
| |
| // Emit a constructor for a type, this can either be a trivial constructor |
| // (i.e. parsed from a literal) or an actual function invocation. |
| void emitConstructorOrLiteral(int depth, DartType tp, |
| {RhsFilter? rhsFilter, bool includeSemicolon = false}) { |
| // If there is at least one non trivial constructor for the type tp |
| // select one of these constructors. |
| if (dartType.hasConstructor(tp)) { |
| var constructor = oneOfSet(dartType.constructors(tp)); |
| // There are two types of constructors, named constructors and 'empty' |
| // constructors (e.g. X.fromList(...) and new X(...) respectively). |
| // Empty constructors are invoked with new + type name, non-empty |
| // constructors are static functions of the type. |
| if (constructor.isNotEmpty) { |
| emit('${tp.name}.$constructor'); |
| } else { |
| // New is no longer necessary as of Dart 2, but is still supported. |
| // Emit a `new` once in a while to ensure it's covered. |
| emit('${rollDice(10) ? "new " : ""}${tp.name}'); |
| } |
| emitParenWrapped(() { |
| // Iterate over constructor parameters. |
| var constructorParameters = |
| dartType.constructorParameters(tp, constructor); |
| if (constructorParameters == null) { |
| throw 'No constructor parameters for ${tp.name}.$constructor'; |
| } |
| emitCommaSeparated((int i) { |
| // If we are emitting a constructor parameter, we want to use small |
| // values to avoid programs that run out of memory. |
| // TODO (felih): maybe allow occasionally? |
| emitLiteral(depth + 1, constructorParameters[i], |
| smallPositiveValue: true, rhsFilter: rhsFilter); |
| }, constructorParameters.length); |
| }); |
| } else { |
| // Otherwise type can be constructed from a literal. |
| emitLiteral(depth + 1, tp, rhsFilter: rhsFilter); |
| } |
| if (includeSemicolon) { |
| emit(';'); |
| } |
| } |
| |
| // Pick an existing variable of the given type. |
| String? pickScalarVar(DartType tp, |
| {bool isLhs = false, RhsFilter? rhsFilter}) { |
| // Randomly specialize interface type, unless emitting left hand side. |
| if (!isLhs) tp = maybeSpecializeInterface(tp); |
| // Collect all choices from globals, fields, locals, and parameters. |
| var choices = <String>{}; |
| for (var i = 0; i < globalVars.length; i++) { |
| if (tp == globalVars[i]) choices.add('$varName$i'); |
| } |
| for (var i = 0; i < localVars.length; i++) { |
| if (tp == localVars[i]) choices.add('$localName$i'); |
| } |
| var fields = getCurrentFields(); |
| if (fields != null) { |
| for (var i = 0; i < fields.length; i++) { |
| if (tp == fields[i]) choices.add('$fieldName${currentClassIndex}_$i'); |
| } |
| } |
| var proto = getCurrentProto(); |
| if (proto != null) { |
| // If recursion is allowed on the current method, the last parameter is |
| // the recursion depth parameter. We should avoid reassigning the |
| // recursion depth parameter to prevent infinite recursion. |
| final endIndex = |
| currentMethod!.recursionAllowed ? proto.length - 1 : proto.length; |
| for (var i = 1; i < endIndex; i++) { |
| if (tp == proto[i]) choices.add('$paramName$i'); |
| } |
| } |
| // Make modification of the iteration variable from the loop |
| // body less likely. |
| if (isLhs) { |
| if (!rollDice(100)) { |
| var cleanChoices = choices.difference(Set.from(iterVars)); |
| if (cleanChoices.isNotEmpty) { |
| choices = cleanChoices; |
| } |
| } |
| } |
| // Filter out the current lhs of the expression to avoid recursive |
| // assignments of the form x = x * x. |
| if (rhsFilter != null && rhsFilter.shouldFilter) { |
| var cleanChoices = choices.difference({rhsFilter.lhsVar}); |
| // If we have other choices of variables, use those. |
| if (cleanChoices.isNotEmpty) { |
| choices = cleanChoices; |
| } else if (!isLhs) { |
| // If we are emitting an rhs variable, we can emit a terminal. |
| // note that if the variable type is a collection, this might |
| // still result in a recursion. |
| emitLiteral(0, tp); |
| return null; |
| } |
| // Otherwise we have to risk creating a recursion. |
| } |
| // Then pick one. |
| if (choices.isEmpty) { |
| throw 'No variable to emit for type ${tp.name}'; |
| } |
| |
| return '${choices.elementAt(choose(choices.length))}'; |
| } |
| |
| String? emitScalarVar(DartType tp, |
| {bool isLhs = false, RhsFilter? rhsFilter}) { |
| final emittedVar = pickScalarVar(tp, isLhs: isLhs, rhsFilter: rhsFilter); |
| if (emittedVar != null) { |
| if (rhsFilter != null && (emittedVar == rhsFilter.lhsVar)) { |
| rhsFilter.consume(); |
| } |
| emit(emittedVar); |
| } |
| return emittedVar; |
| } |
| |
| String? emitSubscriptedVar(int depth, DartType tp, |
| {bool isLhs = false, String? assignOp, RhsFilter? rhsFilter}) { |
| String? ret; |
| // Check if type tp is an indexable element of some other type. |
| if (dartType.isIndexableElementType(tp)) { |
| // Select a list or map type that contains elements of type tp. |
| var iterType = oneOfSet(dartType.indexableElementTypes(tp)); |
| // For `collection[key] <op>= value` to work, collection must not be a |
| // Map or Expando because their subscript operators return a nullable |
| // type. |
| if (assignOp != null && assignOp != "=") { |
| while (!DartType.isListType(iterType)) { |
| iterType = oneOfSet(dartType.indexableElementTypes(tp)); |
| } |
| } |
| // Get the index type for the respective list or map type. |
| final indexType = dartType.indexType(iterType); |
| // Emit a variable of the selected list or map type. |
| ret = emitScalarVar(iterType, isLhs: isLhs, rhsFilter: rhsFilter); |
| emitSquareBraceWrapped(() => |
| // Emit an expression resolving into the index type. For |
| // collection type, only constant collections are used |
| // to avoid rehashing the same value into many entries. |
| DartType.isCollectionType(indexType) |
| ? emitConstCollection(depth + 1, indexType) |
| : emitExpr(depth + 1, indexType)); |
| // Map.[] and Expando.[] have a nullable result, but we should not write |
| // map[key]! = value. |
| if (!tp.isNullable && !isLhs) { |
| emit('!'); |
| } |
| } else { |
| ret = emitScalarVar(tp, |
| isLhs: isLhs, rhsFilter: rhsFilter); // resort to scalar |
| } |
| return ret; |
| } |
| |
| String? emitVar(int depth, DartType tp, |
| {bool isLhs = false, String? assignOp, RhsFilter? rhsFilter}) { |
| switch (choose(2)) { |
| case 0: |
| return emitScalarVar(tp, isLhs: isLhs, rhsFilter: rhsFilter); |
| default: |
| return emitSubscriptedVar(depth, tp, |
| isLhs: isLhs, assignOp: assignOp, rhsFilter: rhsFilter); |
| } |
| } |
| |
| void emitTerminal(int depth, DartType tp, {RhsFilter? rhsFilter}) { |
| switch (choose(2)) { |
| case 0: |
| emitLiteral(depth, tp, rhsFilter: rhsFilter); |
| break; |
| default: |
| emitVar(depth, tp, rhsFilter: rhsFilter); |
| break; |
| } |
| } |
| |
| // Emit expression with unary operator: (~(x)) |
| void emitUnaryExpr(int depth, DartType tp, {RhsFilter? rhsFilter}) { |
| if (dartType.uniOps(tp).isEmpty) { |
| return emitTerminal(depth, tp, rhsFilter: rhsFilter); |
| } |
| emitParenWrapped(() { |
| emit(oneOfSet(dartType.uniOps(tp))); |
| var uniOpParam = tp.toNonNullable(); |
| emitParenWrapped( |
| () => emitExpr(depth + 1, uniOpParam, rhsFilter: rhsFilter)); |
| }); |
| } |
| |
| // Emit expression with binary operator: (x + y) |
| void emitBinaryExpr(int depth, DartType tp, {RhsFilter? rhsFilter}) { |
| if (dartType.binOps(tp).isEmpty) { |
| return emitLiteral(depth, tp); |
| } |
| |
| var binop = oneOfSet(dartType.binOps(tp)); |
| var binOpParams = oneOfSet(dartType.binOpParameters(tp, binop)); |
| |
| // Avoid recursive assignments of the form a = a * 100. |
| if (binop == '*') { |
| rhsFilter?.consume(); |
| } |
| |
| // Reduce the number of operations of type growable * large value |
| // as these might lead to timeouts and/or oom errors. |
| if (binop == '*' && |
| DartType.isGrowableType(binOpParams[0]) && |
| dartType.isInterfaceOfType(binOpParams[1], DartType.NUM)) { |
| emitParenWrapped(() { |
| emitExpr(depth + 1, binOpParams[0], rhsFilter: rhsFilter); |
| emit(' $binop '); |
| emitLiteral(depth + 1, binOpParams[1], smallPositiveValue: true); |
| }); |
| } else if (binop == '*' && |
| DartType.isGrowableType(binOpParams[1]) && |
| dartType.isInterfaceOfType(binOpParams[0], DartType.NUM)) { |
| emitParenWrapped(() { |
| emitLiteral(depth + 1, binOpParams[0], smallPositiveValue: true); |
| emit(' $binop '); |
| emitExpr(depth + 1, binOpParams[1], rhsFilter: rhsFilter); |
| }); |
| } else { |
| emitParenWrapped(() { |
| emitExpr(depth + 1, binOpParams[0], rhsFilter: rhsFilter); |
| emit(' $binop '); |
| emitExpr(depth + 1, binOpParams[1], rhsFilter: rhsFilter); |
| }); |
| } |
| } |
| |
| // Emit expression with ternary operator: (b ? x : y) |
| void emitTernaryExpr(int depth, DartType tp, {RhsFilter? rhsFilter}) => |
| emitParenWrapped(() { |
| emitExpr(depth + 1, DartType.BOOL, rhsFilter: rhsFilter); |
| emit(' ? '); |
| emitExpr(depth + 1, tp, rhsFilter: rhsFilter); |
| emit(' : '); |
| emitExpr(depth + 1, tp, rhsFilter: rhsFilter); |
| }); |
| |
| // Emit expression with pre/post-increment/decrement operator: (x++) |
| void emitPreOrPostExpr(int depth, DartType tp, {RhsFilter? rhsFilter}) { |
| if (tp == DartType.INT) { |
| emitParenWrapped(() { |
| var pre = coinFlip(); |
| if (pre) { |
| emitPreOrPostOp(tp); |
| } |
| emitScalarVar(tp, isLhs: true); |
| if (!pre) { |
| emitPreOrPostOp(tp); |
| } |
| }); |
| } else { |
| emitTerminal(depth, tp, rhsFilter: rhsFilter); // resort to terminal |
| } |
| } |
| |
| bool isTypedDataFloatType(List<DartType> proto) { |
| for (var i = 0; i < proto.length; ++i) { |
| if (DartLib.typedDataFloatTypes.contains(proto[i])) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| // Emit library call. |
| void emitLibraryCall(int depth, DartType tp, |
| {RhsFilter? rhsFilter, bool includeSemicolon = false}) { |
| var lib = getLibraryMethod(tp); |
| if (lib == null || (!fp && isTypedDataFloatType(lib.proto))) { |
| // We cannot find a library method, or we found a library method but its |
| // prototype has a floating point type, and fp is disabled. This can only |
| // happen for non-void types. In those cases, we resort to a literal. |
| assert(tp != DartType.VOID); |
| emitLiteral(depth + 1, tp, rhsFilter: rhsFilter); |
| return; |
| } |
| emitParenWrapped(() { |
| var prototype = lib.proto; |
| // Receiver. |
| if (prototype[0] != DartType.VOID) { |
| emitParenWrapped(() => emitArg( |
| depth + 1, prototype[0], lib.getRestriction(0), |
| rhsFilter: rhsFilter)); |
| emit('.'); |
| } |
| // Call. |
| emit('${lib.name}'); |
| // Parameters. |
| if (lib.isMethod) { |
| emitParenWrapped(() { |
| if (prototype[1] != DartType.VOID) { |
| emitCommaSeparated( |
| (int i) => emitArg( |
| depth + 1, prototype[i], lib.getRestriction(i), |
| rhsFilter: rhsFilter), |
| prototype.length, |
| start: 1); |
| } |
| }); |
| } |
| // Add cast to avoid error of double or int being interpreted as num. |
| if (dartType.isInterfaceOfType(tp, DartType.NUM)) { |
| emit(' as ${tp.name}'); |
| } |
| }); |
| if (includeSemicolon) { |
| emit(';'); |
| } |
| } |
| |
| // Helper for a method call. |
| bool pickedCall(int depth, DartType tp, List<Method> methods, int m, |
| {RhsFilter? rhsFilter}) { |
| for (var i = m - 1; i >= 0; i--) { |
| if (tp == methods[i].returnType) { |
| var isRecursiveCall = (currentMethod == methods[i]); |
| if (isRecursiveCall && !methods[i].recursionAllowed) { |
| continue; |
| } |
| methods[i].emitCall(depth + 1, |
| rhsFilter: rhsFilter, isRecursiveCall: isRecursiveCall); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| // Emit method call within the program. |
| void emitMethodCall(int depth, DartType tp, {RhsFilter? rhsFilter}) { |
| // Only call an already emitted method or the current method to avoid mutual recursion. |
| if (currentClassIndex == null) { |
| // Outside a class but inside a method: call backward in global methods. |
| if (currentMethodIndex != null && |
| pickedCall(depth, tp, globalMethods, currentMethodIndex! + 1, |
| rhsFilter: rhsFilter)) { |
| return; |
| } |
| } else { |
| var classIndex = currentClassIndex; |
| // Chase randomly up in class hierarchy. |
| while (classParents[classIndex!] > 0) { |
| if (coinFlip()) { |
| break; |
| } |
| classIndex = classParents[classIndex]; |
| } |
| var m1 = 0; |
| // Inside a class: try to call backwards into current or parent class |
| // methods first. |
| if (currentMethodIndex == null || classIndex != currentClassIndex) { |
| // If currently emitting the 'run' method or calling into a parent class |
| // pick any of the current or parent class methods respectively. |
| m1 = classMethods[classIndex].length; |
| } else { |
| // If calling into the current class from any method other than 'run' |
| // pick one of the already emitted methods or the current method. |
| // We allow simple recursion but avoid mutual recursion. |
| // (to avoid infinite recursions). |
| m1 = currentMethodIndex! + 1; |
| } |
| final m2 = globalMethods.length; |
| if (pickedCall(depth, tp, classMethods[classIndex], m1, |
| rhsFilter: rhsFilter) || |
| pickedCall(depth, tp, globalMethods, m2, rhsFilter: rhsFilter)) { |
| return; |
| } |
| } |
| emitTerminal(depth, tp, rhsFilter: rhsFilter); // resort to terminal. |
| } |
| |
| // Emit expression. |
| void emitExpr(int depth, DartType tp, |
| {RhsFilter? rhsFilter, bool includeSemicolon = false}) { |
| final resetExprStmt = processExprOpen(tp); |
| // Continuing nested expressions becomes less likely as the depth grows. |
| if (choose(depth + 1) > exprDepth) { |
| emitTerminal(depth, tp, rhsFilter: rhsFilter); |
| } else { |
| // Possibly nested expression. |
| switch (choose(7)) { |
| case 0: |
| emitUnaryExpr(depth, tp, rhsFilter: rhsFilter); |
| break; |
| case 1: |
| emitBinaryExpr(depth, tp, rhsFilter: rhsFilter); |
| break; |
| case 2: |
| emitTernaryExpr(depth, tp, rhsFilter: rhsFilter); |
| break; |
| case 3: |
| emitPreOrPostExpr(depth, tp, rhsFilter: rhsFilter); |
| break; |
| case 4: |
| emitLibraryCall(depth, tp, |
| rhsFilter: RhsFilter.cloneEmpty(rhsFilter)); |
| break; |
| case 5: |
| emitMethodCall(depth, tp, rhsFilter: RhsFilter.cloneEmpty(rhsFilter)); |
| break; |
| default: |
| emitTerminal(depth, tp, rhsFilter: rhsFilter); |
| break; |
| } |
| } |
| processExprClose(resetExprStmt); |
| if (includeSemicolon) { |
| emit(';'); |
| } |
| } |
| |
| // |
| // Operators. |
| // |
| |
| // Emit same type in-out increment operator. |
| void emitPreOrPostOp(DartType tp) { |
| assert(tp == DartType.INT); |
| emit(oneOf(const <String>['++', '--'])); |
| } |
| |
| // 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) => |
| api.typeToLibraryMethods.containsKey(tp) |
| ? oneOf(api.typeToLibraryMethods[tp]!) |
| : null; |
| |
| // Emit a library argument, possibly subject to restrictions. |
| void emitArg(int depth, DartType type, Restriction restriction, |
| {RhsFilter? rhsFilter}) { |
| if ((type == DartType.INT) && (restriction == Restriction.small)) { |
| emitSmallPositiveInt(); |
| } else if ((type == DartType.DOUBLE) && !fp) { |
| // resort to INT if floating point is disabled. |
| emitExpr(depth, DartType.INT, rhsFilter: rhsFilter); |
| } else if ((type == DartType.STRING) && |
| (restriction == Restriction.small)) { |
| emitString(length: 2); |
| } else { |
| emitExpr(depth, type, rhsFilter: rhsFilter); |
| } |
| } |
| |
| // |
| // Types. |
| // |
| |
| List<DartType> fillTypes1({int limit = 4, bool isFfi = false}) { |
| final list = <DartType>[]; |
| for (var i = 0, n = chooseOneUpTo(limit); i < n; i++) { |
| if (isFfi) { |
| list.add(fp ? oneOf([DartType.INT, DartType.DOUBLE]) : DartType.INT); |
| } else { |
| list.add(oneOfSet(dartType.allTypes)); |
| } |
| } |
| return list; |
| } |
| |
| List<List<DartType>> fillTypes2( |
| {bool isFfi = false, int limit2 = 4, int limit1 = 4}) { |
| final list = <List<DartType>>[]; |
| for (var i = 0, n = chooseOneUpTo(limit2); i < n; i++) { |
| list.add(fillTypes1(limit: limit1, isFfi: isFfi)); |
| } |
| return list; |
| } |
| |
| List<DartType>? getCurrentProto() { |
| if (currentClassIndex != null) { |
| if (currentMethodIndex != null) { |
| return classMethods[currentClassIndex!][currentMethodIndex!].parameters; |
| } |
| } else if (currentMethodIndex != null) { |
| return globalMethods[currentMethodIndex!].parameters; |
| } |
| return null; |
| } |
| |
| List<DartType>? getCurrentFields() { |
| if (currentClassIndex != null) { |
| return classFields[currentClassIndex!]; |
| } |
| return null; |
| } |
| |
| void emitFfiType(DartType tp) { |
| if (tp == DartType.INT) { |
| emit(oneOf( |
| const <String>['ffi.Int8', 'ffi.Int16', 'ffi.Int32', 'ffi.Int64'])); |
| } else if (tp == DartType.DOUBLE) { |
| emit(oneOf(const <String>['ffi.Float', 'ffi.Double'])); |
| } else { |
| throw 'Invalid FFI type ${tp.name}'; |
| } |
| } |
| |
| void emitFfiTypedef(Method method) { |
| var pars = method.parameters; |
| emit('typedef ${method.name}Type = '); |
| emitFfiType(pars[0]); |
| emit(' Function'); |
| emitParenWrapped( |
| () => emitCommaSeparated((int i) => emitFfiType(pars[i]), pars.length, |
| start: 1), |
| includeSemicolon: true); |
| emitNewline(); |
| emitNewline(); |
| } |
| |
| // |
| // Output. |
| // |
| |
| // Emits a newline to the program. |
| void emitNewline() => emit('', newline: true); |
| |
| // Emits indentation based on the current indentation count. |
| void emitIndentation() => file.writeStringSync(' ' * indent); |
| |
| // Emits indented line to append to program. |
| void emitLn(String line, {bool newline = true}) { |
| emitIndentation(); |
| emit(line, newline: newline); |
| } |
| |
| // Emits text to append to program. |
| void emit(String txt, {bool newline = false}) { |
| if (skipStmt || skipExpr) { |
| return; |
| } |
| file.writeStringSync(txt); |
| if (newline) { |
| file.writeStringSync('\n'); |
| } |
| } |
| |
| // Special return code to handle oom errors. |
| static const oomExitCode = 254; |
| |
| // Random seed used to generate program. |
| final int seed; |
| |
| // Enables floating-point operations. |
| final bool fp; |
| |
| // Enables FFI method calls. |
| final bool ffi; |
| |
| // Disables nested types. |
| final bool flatTp; |
| |
| // File used for output. |
| final RandomAccessFile file; |
| |
| // Library and ffi api. |
| late DartApi api; |
| |
| // Program variables. |
| late Random rand; |
| int indent = 0; |
| int nest = 0; |
| int? currentClassIndex; |
| Method? currentMethod; |
| int? currentMethodIndex; |
| |
| // DartType instance. |
| late DartType dartType; |
| |
| // Types of local variables currently in scope. |
| late List<DartType?> localVars; |
| |
| // Types of global variables. |
| late List<DartType> globalVars; |
| |
| // Names of currently active iterator variables. |
| // These are tracked to avoid modifications within the loop body, |
| // which can lead to infinite loops. |
| late List<String?> iterVars; |
| |
| // List of all global methods. |
| late List<Method> globalMethods; |
| |
| // Types of fields over all classes. |
| late List<List<DartType>> classFields; |
| |
| // List of methods over all classes. |
| late List<List<Method>> classMethods; |
| |
| // List of virtual functions per class. Map is from parent class index to List |
| // of overloaded functions from that parent. |
| late List<Map<int, List<int>>> virtualClassMethods; |
| |
| // Parent class indices for all classes. |
| late List<int> classParents; |
| |
| // Minimization mode extensions. |
| final bool minimize; |
| BigInt? smask; |
| BigInt? emask; |
| bool skipStmt = false; |
| bool skipExpr = false; |
| bool skipExprCntr = false; |
| int stmtCntr = 0; |
| int exprCntr = 0; |
| |
| // Interesting characters. |
| static const List<String> interestingChars = [ |
| '\\u2665', |
| '\\u{1f600}', // rune |
| ]; |
| |
| // Regular characters. |
| static const regularChars = |
| 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#&()+- '; |
| |
| // Interesting integer values. |
| static const List<int> interestingIntegers = [ |
| 0x0000000000000000, |
| 0x0000000000000001, |
| 0x000000007fffffff, |
| 0x0000000080000000, |
| 0x0000000080000001, |
| 0x00000000ffffffff, |
| 0x0000000100000000, |
| 0x0000000100000001, |
| 0x000000017fffffff, |
| 0x0000000180000000, |
| 0x0000000180000001, |
| 0x00000001ffffffff, |
| 0x7fffffff00000000, |
| 0x7fffffff00000001, |
| 0x7fffffff7fffffff, |
| 0x7fffffff80000000, |
| 0x7fffffff80000001, |
| 0x7fffffffffffffff, |
| 0x8000000000000000, |
| 0x8000000000000001, |
| 0x800000007fffffff, |
| 0x8000000080000000, |
| 0x8000000080000001, |
| 0x80000000ffffffff, |
| 0x8000000100000000, |
| 0x8000000100000001, |
| 0x800000017fffffff, |
| 0x8000000180000000, |
| 0x8000000180000001, |
| 0x80000001ffffffff, |
| 0xffffffff00000000, |
| 0xffffffff00000001, |
| 0xffffffff7fffffff, |
| 0xffffffff80000000, |
| 0xffffffff80000001, |
| 0xffffffffffffffff |
| ]; |
| } |
| |
| // 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) { |
| var seed = int.parse(userSeed); |
| if (seed == 0) { |
| final rand = Random(); |
| while (seed == 0) { |
| seed = rand.nextInt(1 << 32); |
| } |
| } |
| return seed; |
| } |
| |
| /// Main driver when dartfuzz.dart is run stand-alone. |
| void main(List<String> arguments) { |
| const kSeed = 'seed'; |
| const kFp = 'fp'; |
| const kFfi = 'ffi'; |
| const kFlat = 'flat'; |
| const kMini = 'mini'; |
| const kSMask = 'smask'; |
| const kEMask = 'emask'; |
| final parser = ArgParser() |
| ..addOption(kSeed, |
| help: 'random seed (0 forces time-based seed)', defaultsTo: '0') |
| ..addFlag(kFp, help: 'enables floating-point operations', defaultsTo: true) |
| ..addFlag(kFfi, |
| help: 'enables FFI method calls (default: off)', defaultsTo: false) |
| ..addFlag(kFlat, |
| help: 'enables flat types (default: off)', defaultsTo: false) |
| // Minimization mode extensions. |
| ..addFlag(kMini, |
| help: 'enables minimization mode (default: off)', defaultsTo: false) |
| ..addOption(kSMask, |
| help: 'Bitmask indicating which statements to omit' |
| '(Bit=1 omits)', |
| defaultsTo: '0') |
| ..addOption(kEMask, |
| help: 'Bitmask indicating which expressions to omit' |
| '(Bit=1 omits)', |
| defaultsTo: '0'); |
| var results; |
| try { |
| results = parser.parse(arguments); |
| } catch (e) { |
| print('Usage: dart dartfuzz.dart [OPTIONS] FILENAME\n${parser.usage}\n$e'); |
| exitCode = 255; |
| } |
| final seed = getSeed(results[kSeed]); |
| final fp = results[kFp]; |
| final ffi = results[kFfi]; |
| final flatTp = results[kFlat]; |
| final file = File(results.rest.single).openSync(mode: FileMode.write); |
| final minimize = results[kMini]; |
| final smask = BigInt.parse(results[kSMask]); |
| final emask = BigInt.parse(results[kEMask]); |
| final dartFuzz = DartFuzz(seed, fp, ffi, flatTp, file, |
| minimize: minimize, smask: smask, emask: emask); |
| dartFuzz.run(); |
| file.closeSync(); |
| // Print information that will be parsed by minimize.py |
| if (minimize) { |
| // Updated statement mask. |
| // This might be different from the input parameter --smask |
| // since masking a statement that contains nested statements leads to |
| // those being masked as well. |
| print(dartFuzz.smask!.toRadixString(10)); |
| // Total number of statements in the generated program. |
| print(dartFuzz.stmtCntr); |
| // Updated expression mask. |
| // This might be different from the input parameter --emask |
| // since masking a statement that contains expressions or |
| // an expression that contains nested expressions leads to |
| // those being masked as well. |
| print(dartFuzz.emask!.toRadixString(10)); |
| // Total number of expressions in the generated program. |
| print(dartFuzz.exprCntr); |
| } |
| } |
