Fuzzer: Avoid emitting massive nested structs (#5564)

The nesting limit of around 20 was enough to cause exponential blowup. A 20K
input file lead to a 2GB wasm in one case I saw (!) which takes many seconds to
fuzz.

Instead, reduce the limit, and also check if random tells us that the random
input is done; when that's done we should stop, which limits us to O(input size).

Also do this for non-nullable types, and handle that in globals (we cannot emit a
RefAsNulNull there, so switch the global type if necessary).

2 files changed, 59 insertions, 41 deletions

diff --git a/src/tools/fuzzing/fuzzing.cpp b/src/tools/fuzzing/fuzzing.cpp
index acc760f6b..89ff1b459 100644
--- a/src/tools/fuzzing/fuzzing.cpp
+++ b/src/tools/fuzzing/fuzzing.cpp
@@ -323,10 +323,18 @@ void TranslateToFuzzReader::setupGlobals() {
   }
   for (size_t index = upTo(MAX_GLOBALS); index > 0; --index) {
     auto type = getConcreteType();
-    auto global = builder.makeGlobal(Names::getValidGlobalName(wasm, "global$"),
-                                     type,
-                                     makeConst(type),
-                                     Builder::Mutable);
+    auto* init = makeConst(type);
+    if (!FindAll<RefAs>(init).list.empty()) {
+      // When creating this initial value we ended up emitting a RefAs, which
+      // means we had to stop in the middle of an overly-nested struct or array,
+      // which we can break out of using ref.as_non_null of a nullable ref. That
+      // traps in normal code, which is bad enough, but it does not even
+      // validate in a global. Switch to something safe instead.
+      type = getMVPType();
+      init = makeConst(type);
+    }
+    auto global = builder.makeGlobal(
+      Names::getValidGlobalName(wasm, "global$"), type, init, Builder::Mutable);
     globalsByType[type].push_back(global->name);
     wasm.addGlobal(std::move(global));
   }
@@ -2178,18 +2186,29 @@ Expression* TranslateToFuzzReader::makeConstCompoundRef(Type type) {
   // really have no choice and must emit a null (or else we could infinitely
   // recurse). For the nesting limit, use a bound that is higher than the normal
   // one, so that the normal mechanisms should prevent us from getting here;
-  // this limit is really a last resort we want to never reach.
+  // this limit is really a last resort we want to never reach. Also, increase
+  // the chance to emit a null as |nesting| rises, to avoid deep recursive
+  // structures.
   //
   // Note that we might have cycles of types where some are non-nullable. We
   // will only stop here when we exceed the nesting and reach a nullable one.
   // (This assumes there is a nullable one, that is, that the types are
   // inhabitable.)
-  const auto LIMIT = 2 * NESTING_LIMIT;
+  const auto LIMIT = NESTING_LIMIT + 1;
   AutoNester nester(*this);
-  if (type.isNullable() && (oneIn(10) || nesting >= LIMIT)) {
+  if (type.isNullable() &&
+      (random.finished() || nesting >= LIMIT || oneIn(LIMIT - nesting + 1))) {
     return builder.makeRefNull(heapType);
   }
 
+  // If the type is non-nullable, and we've run out of input, emit a cast to
+  // make this validate, but it will trap at runtime which is not ideal. This at
+  // least avoids infinite recursion here, and we emit a valid (but not that
+  // useful) wasm.
+  if (type.isNonNullable() && (random.finished() || nesting >= LIMIT)) {
+    return builder.makeRefAs(RefAsNonNull, builder.makeRefNull(heapType));
+  }
+
   if (heapType.isSignature()) {
     return makeRefFuncConst(type);
   } else if (type.isStruct()) {
diff --git a/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt b/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
index f3ab68180..04f0f6405 100644
--- a/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
+++ b/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
@@ -1,43 +1,42 @@
 total
- [exports]      : 7       
- [funcs]        : 10      
+ [exports]      : 5       
+ [funcs]        : 13      
  [globals]      : 5       
  [imports]      : 5       
  [memories]     : 1       
  [memory-data]  : 20      
- [table-data]   : 1       
+ [table-data]   : 0       
  [tables]       : 1       
  [tags]         : 1       
- [total]        : 849     
- [vars]         : 6       
- ArrayNew       : 2       
- ArrayNewFixed  : 5       
- Binary         : 97      
- Block          : 127     
- Break          : 15      
- Call           : 13      
- CallRef        : 3       
- Const          : 186     
- DataDrop       : 1       
- Drop           : 6       
- GlobalGet      : 58      
- GlobalSet      : 58      
+ [total]        : 460     
+ [vars]         : 23      
+ ArrayNewFixed  : 1       
+ AtomicCmpxchg  : 1       
+ AtomicRMW      : 1       
+ Binary         : 66      
+ Block          : 56      
+ Break          : 3       
+ Call           : 15      
+ Const          : 98      
+ Drop           : 8       
+ GlobalGet      : 26      
+ GlobalSet      : 26      
  I31New         : 2       
- If             : 38      
- Load           : 23      
- LocalGet       : 38      
- LocalSet       : 23      
- Loop           : 20      
- Nop            : 18      
- RefEq          : 1       
- RefFunc        : 7       
- RefNull        : 2       
- Return         : 1       
+ If             : 16      
+ Load           : 17      
+ LocalGet       : 33      
+ LocalSet       : 21      
+ Loop           : 3       
+ Nop            : 9       
+ RefAs          : 2       
+ RefFunc        : 2       
+ RefNull        : 5       
+ Return         : 3       
  SIMDExtract    : 1       
- Select         : 3       
- Store          : 8       
- StructNew      : 6       
- TupleExtract   : 3       
- TupleMake      : 6       
- Unary          : 48      
- Unreachable    : 30      
+ Select         : 1       
+ Store          : 1       
+ StructNew      : 4       
+ TupleExtract   : 2       
+ TupleMake      : 4       
+ Unary          : 17      
+ Unreachable    : 16