[dart/fuzzer] Further development DartFuzz
Rationale:
Adds a few more constructs, avoid situations that go out-of-memory
too easily, prepares library method format for automatic generation
of library tables.
https://github.com/dart-lang/sdk/issues/35406
Change-Id: I24b4656ea073fbe41175aa08952588e28d4363a1
Reviewed-on: https://dart-review.googlesource.com/c/90320
Reviewed-by: Alexander Thomas <athom@google.com>
Commit-Queue: Aart Bik <ajcbik@google.com>
diff --git a/runtime/tools/dartfuzz/dartfuzz.dart b/runtime/tools/dartfuzz/dartfuzz.dart
index 0ad5858..9843383 100644
--- a/runtime/tools/dartfuzz/dartfuzz.dart
+++ b/runtime/tools/dartfuzz/dartfuzz.dart
@@ -12,7 +12,7 @@
// 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.2';
+const String version = '1.3';
// Restriction on statement and expression depths.
const int stmtDepth = 5;
@@ -160,6 +160,33 @@
}
//
+ // 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.
//
@@ -167,7 +194,7 @@
bool emitAssign() {
DartType tp = getType();
emitLn('', newline: false);
- emitVar(tp);
+ emitVar(0, tp);
emitAssignOp(tp);
emitExpr(0, tp);
emit(';', newline: true);
@@ -202,10 +229,10 @@
emitExpr(0, DartType.BOOL);
emit(') {', newline: true);
indent += 2;
- bool b = emitStatements(depth + 1);
+ emitStatements(depth + 1);
indent -= 2;
emitLn('}');
- return b;
+ return true;
}
// Emit a two-way if statement.
@@ -257,13 +284,17 @@
// Emit a statement. Returns true if code may fall-through.
// TODO: add many more constructs
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(8)) {
- // favors assignment
+ // Favors assignment.
case 0:
return emitIf1(depth);
case 1:
@@ -310,10 +341,9 @@
void emitInt() {
switch (rand.nextInt(4)) {
- // favors small positive int
+ // Favors small positive int.
case 0:
- emit(
- '${DartFuzzValues.interestingIntegers[rand.nextInt(DartFuzzValues.interestingIntegers.length)]}');
+ emit('${oneOf(DartFuzzValues.interestingIntegers)}');
break;
case 1:
emitSmallNegativeInt();
@@ -325,22 +355,10 @@
}
void emitDouble() {
- switch (rand.nextInt(7)) {
- // favors small double
+ switch (rand.nextInt(10)) {
+ // Favors regular double.
case 0:
- emit('double.infinity');
- break;
- case 1:
- emit('double.maxFinite');
- break;
- case 2:
- emit('double.minPositive');
- break;
- case 3:
- emit('double.nan');
- break;
- case 4:
- emit('double.negativeInfinity');
+ emit(oneOf(DartFuzzValues.interestingDoubles));
break;
default:
emit('${rand.nextDouble()}');
@@ -350,15 +368,12 @@
void emitChar() {
switch (rand.nextInt(10)) {
- // favors regular char
+ // Favors regular char.
case 0:
- emit('\\u2665');
- break;
- case 1:
- emit('\\u{1f600}'); // rune
+ emit(oneOf(DartFuzzValues.interestingChars));
break;
default:
- emit(DartFuzzValues.interestingChars[
+ emit(DartFuzzValues.regularChars[
rand.nextInt(DartFuzzValues.interestingChars.length)]);
break;
}
@@ -442,18 +457,40 @@
emit('${choices[rand.nextInt(choices.length)]}');
}
- void emitVar(DartType tp) {
- // TODO: add subscripted var
- emitScalarVar(tp);
+ void emitSubscriptedVar(int depth, DartType tp) {
+ if (tp == DartType.INT) {
+ emitScalarVar(DartType.INT_LIST);
+ emit('[');
+ emitExpr(depth + 1, DartType.INT);
+ emit(']');
+ } else if (tp == DartType.STRING) {
+ emitScalarVar(DartType.INT_STRING_MAP);
+ emit('[');
+ emitExpr(depth + 1, DartType.INT);
+ emit(']');
+ } else {
+ emitScalarVar(tp); // resort to scalar
+ }
}
- void emitTerminal(DartType tp) {
+ void emitVar(int depth, DartType tp) {
+ switch (rand.nextInt(2)) {
+ case 0:
+ emitScalarVar(tp);
+ break;
+ default:
+ emitSubscriptedVar(depth, tp);
+ break;
+ }
+ }
+
+ void emitTerminal(int depth, DartType tp) {
switch (rand.nextInt(2)) {
case 0:
emitLiteral(tp);
break;
default:
- emitVar(tp);
+ emitVar(depth, tp);
break;
}
}
@@ -478,7 +515,7 @@
emitExpr(depth + 1, tp);
emit('))');
} else {
- emitTerminal(tp); // resort to terminal
+ emitTerminal(depth, tp); // resort to terminal
}
}
@@ -495,6 +532,16 @@
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(tp);
+ emit(')');
+ return;
}
emit('(');
emitExpr(depth + 1, tp);
@@ -524,32 +571,34 @@
if (r == 1) emitPreOrPostOp(tp);
emit(')');
} else {
- emitTerminal(tp); // resort to terminal
+ emitTerminal(depth, tp); // resort to terminal
}
}
// Emit library call.
void emitLibraryCall(int depth, DartType tp) {
- if (tp == DartType.INT_STRING_MAP) {
- emitTerminal(tp); // resort to terminal
- return;
- }
DartLib lib = getLibraryMethod(tp);
- List<DartType> proto = lib.proto;
+ String proto = lib.proto;
// Receiver.
- if (proto[0] != null) {
- DartType deeper_tp = proto[0];
+ if (proto[0] != 'V') {
emit('(');
- emitExpr(depth + 1, deeper_tp);
+ emitArg(depth + 1, proto[0]);
emit(').');
}
// Call.
emit('${lib.name}');
// Parameters.
- if (proto.length == 1) {
- emit('()');
- } else if (proto[1] != null) {
- emitExprList(depth + 1, proto);
+ 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(')');
}
}
@@ -586,14 +635,14 @@
return;
}
}
- emitTerminal(tp); // resort to terminal.
+ 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(tp);
+ emitTerminal(depth, tp);
return;
}
// Possibly nested expression.
@@ -617,7 +666,7 @@
emitMethodCall(depth, tp);
break;
default:
- emitTerminal(tp);
+ emitTerminal(depth, tp);
break;
}
}
@@ -725,11 +774,42 @@
return oneOf(DartLib.stringLibs);
} else if (tp == DartType.INT_LIST) {
return oneOf(DartLib.intListLibs);
+ } else if (tp == DartType.INT_STRING_MAP) {
+ return oneOf(DartLib.intStringMapLibs);
} 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, DartType.DOUBLE);
+ break;
+ case 'S':
+ emitExpr(depth, DartType.STRING);
+ break;
+ case 'L':
+ emitExpr(depth, DartType.INT_LIST);
+ break;
+ case 'M':
+ emitExpr(depth, DartType.INT_STRING_MAP);
+ break;
+ default:
+ assert(false);
+ }
+ }
+
//
// Types.
//
diff --git a/runtime/tools/dartfuzz/dartfuzz_values.dart b/runtime/tools/dartfuzz/dartfuzz_values.dart
index e19e301..c97249d 100644
--- a/runtime/tools/dartfuzz/dartfuzz_values.dart
+++ b/runtime/tools/dartfuzz/dartfuzz_values.dart
@@ -26,9 +26,24 @@
/// Class with interesting values for fuzzing.
class DartFuzzValues {
// Interesting characters.
- static const interestingChars =
+ static const List<String> interestingChars = [
+ '\\u2665',
+ '\\u{1f600}', // rune
+ ];
+
+ // Regular characters.
+ static const regularChars =
'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#&()+- ';
+ // Interesting doubles.
+ static const interestingDoubles = [
+ 'double.infinity',
+ 'double.maxFinite',
+ 'double.minPositive',
+ 'double.nan',
+ 'double.negativeInfinity',
+ ];
+
// Interesting integer values.
static const List<int> interestingIntegers = [
0x0000000000000000,
@@ -71,97 +86,111 @@
}
/// Class that represents Dart library methods.
+//
/// The invididual lists are organized by return type.
-/// Proto list:
-/// [ receiver-type (null denotes none),
-/// param1 type (null denotes getter),
-/// param2 type,
-/// ...
-/// ]
+/// The proto string has the following format:
+/// +-------> receiver type (V denotes none)
+/// |+------> param1 type (V denotes none, v denotes getter)
+/// ||+-----> param2 type
+/// |||+----> ....
+/// ||||
+/// "TTTT...."
+/// where:
+/// V void
+/// v void (special)
+/// B bool
+/// I int
+/// i int (small)
+/// D double
+/// S String
+/// L List<int>
+/// M Map<int, String>
///
/// TODO(ajcbik): generate these lists automatically
///
class DartLib {
final String name;
- final List<DartType> proto;
+ final String proto;
const DartLib(this.name, this.proto);
static const boolLibs = [
- DartLib('isEven', [DartType.INT, null]),
- DartLib('isOdd', [DartType.INT, null]),
- DartLib('isEmpty', [DartType.STRING, null]),
- DartLib('isEmpty', [DartType.INT_STRING_MAP, null]),
- DartLib('isNotEmpty', [DartType.STRING, null]),
- DartLib('isNotEmpty', [DartType.INT_STRING_MAP, null]),
- DartLib('endsWith', [DartType.STRING, DartType.STRING]),
- DartLib('remove', [DartType.INT_LIST, DartType.INT]),
- DartLib('containsValue', [DartType.INT_STRING_MAP, DartType.STRING]),
- DartLib('containsKey', [DartType.INT_STRING_MAP, DartType.INT]),
+ DartLib('isEven', "Iv"),
+ DartLib('isOdd', "Iv"),
+ DartLib('isEmpty', "Sv"),
+ DartLib('isEmpty', "Mv"),
+ DartLib('isNotEmpty', "Sv"),
+ DartLib('isNotEmpty', "Mv"),
+ DartLib('endsWith', "SS"),
+ DartLib('remove', "LI"),
+ DartLib('containsValue', "MS"),
+ DartLib('containsKey', "MI"),
];
static const intLibs = [
- DartLib('bitLength', [DartType.INT, null]),
- DartLib('sign', [DartType.INT, null]),
- DartLib('abs', [DartType.INT]),
- DartLib('round', [DartType.INT]),
- DartLib('round', [DartType.DOUBLE]),
- DartLib('floor', [DartType.INT]),
- DartLib('floor', [DartType.DOUBLE]),
- DartLib('ceil', [DartType.INT]),
- DartLib('ceil', [DartType.DOUBLE]),
- DartLib('truncate', [DartType.INT]),
- DartLib('truncate', [DartType.DOUBLE]),
- DartLib('toInt', [DartType.DOUBLE]),
- DartLib('toUnsigned', [DartType.INT, DartType.INT]),
- DartLib('toSigned', [DartType.INT, DartType.INT]),
- DartLib('modInverse', [DartType.INT, DartType.INT]),
- DartLib('modPow', [DartType.INT, DartType.INT, DartType.INT]),
- DartLib('length', [DartType.STRING, null]),
- DartLib('length', [DartType.INT_LIST, null]),
- DartLib('length', [DartType.INT_STRING_MAP, null]),
- DartLib('codeUnitAt', [DartType.STRING, DartType.INT]),
- DartLib('compareTo', [DartType.STRING, DartType.STRING]),
- DartLib('removeLast', [DartType.INT_LIST]),
- DartLib('removeAt', [DartType.INT_LIST, DartType.INT]),
- DartLib('indexOf', [DartType.INT_LIST, DartType.INT]),
- DartLib('lastIndexOf', [DartType.INT_LIST, DartType.INT]),
+ DartLib('bitLength', "Iv"),
+ DartLib('sign', "Iv"),
+ DartLib('abs', "IV"),
+ DartLib('round', "IV"),
+ DartLib('round', "DV"),
+ DartLib('floor', "IV"),
+ DartLib('floor', "DV"),
+ DartLib('ceil', "IV"),
+ DartLib('ceil', "DV"),
+ DartLib('truncate', "IV"),
+ DartLib('truncate', "DV"),
+ DartLib('toInt', "DV"),
+ DartLib('toUnsigned', "II"),
+ DartLib('toSigned', "II"),
+ DartLib('modInverse', "II"),
+ DartLib('modPow', "III"),
+ DartLib('length', "Sv"),
+ DartLib('length', "Lv"),
+ DartLib('length', "Mv"),
+ DartLib('codeUnitAt', "SI"),
+ DartLib('compareTo', "SS"),
+ DartLib('removeLast', "LV"),
+ DartLib('removeAt', "LI"),
+ DartLib('indexOf', "LI"),
+ DartLib('lastIndexOf', "LI"),
];
static const doubleLibs = [
- DartLib('sign', [DartType.DOUBLE, null]),
- DartLib('abs', [DartType.DOUBLE]),
- DartLib('toDouble', [DartType.INT]),
- DartLib('roundToDouble', [DartType.INT]),
- DartLib('roundToDouble', [DartType.DOUBLE]),
- DartLib('floorToDouble', [DartType.INT]),
- DartLib('floorToDouble', [DartType.DOUBLE]),
- DartLib('ceilToDouble', [DartType.INT]),
- DartLib('ceilToDouble', [DartType.DOUBLE]),
- DartLib('truncateToDouble', [DartType.INT]),
- DartLib('truncateToDouble', [DartType.DOUBLE]),
- DartLib('remainder', [DartType.DOUBLE, DartType.DOUBLE]),
+ DartLib('sign', "Dv"),
+ DartLib('abs', "DV"),
+ DartLib('toDouble', "IV"),
+ DartLib('roundToDouble', "IV"),
+ DartLib('roundToDouble', "DV"),
+ DartLib('floorToDouble', "IV"),
+ DartLib('floorToDouble', "DV"),
+ DartLib('ceilToDouble', "IV"),
+ DartLib('ceilToDouble', "DV"),
+ DartLib('truncateToDouble', "IV"),
+ DartLib('truncateToDouble', "DV"),
+ DartLib('remainder', "DD"),
];
static const stringLibs = [
- DartLib('toString', [DartType.BOOL]),
- DartLib('toString', [DartType.INT]),
- DartLib('toString', [DartType.DOUBLE]),
- DartLib('toRadixString', [DartType.INT, DartType.INT]),
- DartLib('trim', [DartType.STRING]),
- DartLib('trimLeft', [DartType.STRING]),
- DartLib('trimRight', [DartType.STRING]),
- DartLib('toLowerCase', [DartType.STRING]),
- DartLib('toUpperCase', [DartType.STRING]),
- DartLib('substring', [DartType.STRING, DartType.INT]),
- DartLib('replaceRange',
- [DartType.STRING, DartType.INT, DartType.INT, DartType.STRING]),
- DartLib('remove', [DartType.INT_STRING_MAP, DartType.INT]),
- // Avoid (OOM divergences, TODO(ajcbik): restrict parameters)
- // DartLib('padLeft', [DartType.STRING, DartType.INT]),
- // DartLib('padRight', [DartType.STRING, DartType.INT]),
+ DartLib('toString', "BV"),
+ DartLib('toString', "IV"),
+ DartLib('toString', "DV"),
+ DartLib('toRadixString', "II"),
+ DartLib('trim', "SV"),
+ DartLib('trimLeft', "SV"),
+ DartLib('trimRight', "SV"),
+ DartLib('toLowerCase', "SV"),
+ DartLib('toUpperCase', "SV"),
+ DartLib('substring', "SI"),
+ DartLib('replaceRange', "SIIS"),
+ DartLib('remove', "MI"),
+ DartLib('padLeft', "Si"), // restrict!
+ DartLib('padRight', "Si"), // restrict!
];
static const intListLibs = [
- DartLib('sublist', [DartType.INT_LIST, DartType.INT])
+ DartLib('sublist', "LI"),
+ ];
+
+ static const intStringMapLibs = [
+ DartLib('Map.from', "VM"),
];
}
