[Wasm GC] Fuzz struct.new and array.new (#5622)

Repurpose makeBasicRef, makeCompoundRef to generate not just "constant"
refs but any reference, and use those to create StructNew/ArrayNew.

The key changes are to add makeCompoundRef to make(), and to make
the function call make() for children, where possible, instead of just
makeTrivial(). We also replace the i31-specific path with a call to
makeBasicRef which handles i31 among other things.

3 files changed, 83 insertions, 70 deletions

diff --git a/src/tools/fuzzing.h b/src/tools/fuzzing.h
index ebc77ab43..e53665e14 100644
--- a/src/tools/fuzzing.h
+++ b/src/tools/fuzzing.h
@@ -148,11 +148,18 @@ public:
 
   struct AutoNester {
     TranslateToFuzzReader& parent;
+    size_t amount = 1;
 
     AutoNester(TranslateToFuzzReader& parent) : parent(parent) {
       parent.nesting++;
     }
-    ~AutoNester() { parent.nesting--; }
+    ~AutoNester() { parent.nesting -= amount; }
+
+    // Add more nesting manually.
+    void add(size_t more) {
+      parent.nesting += more;
+      amount += more;
+    }
   };
 
 private:
@@ -289,10 +296,10 @@ private:
   // we may add a GC cast to fixup the type.
   Expression* makeConst(Type type);
 
-  // Like makeConst, but for a type that is a reference type. One function
-  // handles basic types, and the other compound ones.
-  Expression* makeConstBasicRef(Type type);
-  Expression* makeConstCompoundRef(Type type);
+  // Generate reference values. One function handles basic types, and the other
+  // compound ones.
+  Expression* makeBasicRef(Type type);
+  Expression* makeCompoundRef(Type type);
 
   Expression* buildUnary(const UnaryArgs& args);
   Expression* makeUnary(Type type);
@@ -319,7 +326,6 @@ private:
   Expression* makeRefEq(Type type);
   Expression* makeRefTest(Type type);
   Expression* makeRefCast(Type type);
-  Expression* makeI31New(Type type);
   Expression* makeI31Get(Type type);
   Expression* makeMemoryInit();
   Expression* makeDataDrop();
diff --git a/src/tools/fuzzing/fuzzing.cpp b/src/tools/fuzzing/fuzzing.cpp
index 4a611345d..d904fd7bd 100644
--- a/src/tools/fuzzing/fuzzing.cpp
+++ b/src/tools/fuzzing/fuzzing.cpp
@@ -824,6 +824,7 @@ void TranslateToFuzzReader::mutate(Function* func) {
         // not, changing an offset, etc.
         // Perform a general replacement. (This is not always valid due to
         // nesting of labels, but we'll fix that up later.)
+        // TODO: pick a subtype of the current type
         replaceCurrent(parent.make(curr->type));
       }
     }
@@ -1090,9 +1091,13 @@ Expression* TranslateToFuzzReader::_makeConcrete(Type type) {
     options.add(FeatureSet::Multivalue, &Self::makeTupleMake);
   }
   if (type.isRef()) {
-    if (type.getHeapType() == HeapType::i31) {
+    auto heapType = type.getHeapType();
+    if (heapType.isBasic()) {
       options.add(FeatureSet::ReferenceTypes | FeatureSet::GC,
-                  &Self::makeI31New);
+                  &Self::makeBasicRef);
+    } else {
+      options.add(FeatureSet::ReferenceTypes | FeatureSet::GC,
+                  &Self::makeCompoundRef);
     }
     options.add(FeatureSet::ReferenceTypes | FeatureSet::GC,
                 &Self::makeRefCast);
@@ -2096,9 +2101,9 @@ Expression* TranslateToFuzzReader::makeConst(Type type) {
       return builder.makeRefNull(type.getHeapType());
     }
     if (type.getHeapType().isBasic()) {
-      return makeConstBasicRef(type);
+      return makeBasicRef(type);
     } else {
-      return makeConstCompoundRef(type);
+      return makeCompoundRef(type);
     }
   } else if (type.isTuple()) {
     std::vector<Expression*> operands;
@@ -2112,7 +2117,7 @@ Expression* TranslateToFuzzReader::makeConst(Type type) {
   }
 }
 
-Expression* TranslateToFuzzReader::makeConstBasicRef(Type type) {
+Expression* TranslateToFuzzReader::makeBasicRef(Type type) {
   assert(type.isRef());
   auto heapType = type.getHeapType();
   assert(heapType.isBasic());
@@ -2216,7 +2221,7 @@ Expression* TranslateToFuzzReader::makeConstBasicRef(Type type) {
   WASM_UNREACHABLE("invalid basic ref type");
 }
 
-Expression* TranslateToFuzzReader::makeConstCompoundRef(Type type) {
+Expression* TranslateToFuzzReader::makeCompoundRef(Type type) {
   assert(type.isRef());
   auto heapType = type.getHeapType();
   assert(!heapType.isBasic());
@@ -2250,28 +2255,43 @@ Expression* TranslateToFuzzReader::makeConstCompoundRef(Type type) {
     return builder.makeRefAs(RefAsNonNull, builder.makeRefNull(heapType));
   }
 
+  // When we make children, they must be trivial if we are not in a function
+  // context.
+  auto makeChild = [&](Type type) {
+    return funcContext ? make(type) : makeTrivial(type);
+  };
+
   if (heapType.isSignature()) {
     return makeRefFuncConst(type);
   } else if (type.isStruct()) {
     auto& fields = heapType.getStruct().fields;
     std::vector<Expression*> values;
-    // TODO: use non-default values randomly even when not necessary, sometimes
-    if (std::any_of(fields.begin(), fields.end(), [&](const Field& field) {
-          return !field.type.isDefaultable();
-        })) {
-      // There is a nondefaultable field, which we must create.
+    // If there is a nondefaultable field, we must provide the value and not
+    // depend on defaults. Also do that randomly half the time.
+    if (std::any_of(
+          fields.begin(),
+          fields.end(),
+          [&](const Field& field) { return !field.type.isDefaultable(); }) ||
+        oneIn(2)) {
       for (auto& field : fields) {
-        // TODO: when in a function context, we don't need to be trivial.
-        values.push_back(makeTrivial(field.type));
+        values.push_back(makeChild(field.type));
+      }
+      // Add more nesting manually, as we can easily get exponential blowup
+      // here. This nesting makes it much less likely for a recursive data
+      // structure to end up as a massive tree of struct.news, since the nesting
+      // limitation code at the top of this function will kick in.
+      if (!values.empty()) {
+        // Subtract 1 since if there is a single value there cannot be
+        // exponential blowup.
+        nester.add(values.size() - 1);
       }
     }
     return builder.makeStructNew(heapType, values);
   } else if (type.isArray()) {
     auto element = heapType.getArray().element;
     Expression* init = nullptr;
-    if (!element.type.isDefaultable()) {
-      // TODO: when in a function context, we don't need to be trivial.
-      init = makeTrivial(element.type);
+    if (!element.type.isDefaultable() || oneIn(2)) {
+      init = makeChild(element.type);
     }
     auto* count = builder.makeConst(int32_t(upTo(MAX_ARRAY_SIZE)));
     return builder.makeArrayNew(type.getHeapType(), count, init);
@@ -3177,13 +3197,6 @@ Expression* TranslateToFuzzReader::makeRefCast(Type type) {
   return builder.makeRefCast(make(refType), type, RefCast::Safe);
 }
 
-Expression* TranslateToFuzzReader::makeI31New(Type type) {
-  assert(type.isRef() && type.getHeapType() == HeapType::i31);
-  assert(wasm.features.hasReferenceTypes() && wasm.features.hasGC());
-  auto* value = make(Type::i32);
-  return builder.makeI31New(value);
-}
-
 Expression* TranslateToFuzzReader::makeI31Get(Type type) {
   assert(type == Type::i32);
   assert(wasm.features.hasReferenceTypes() && wasm.features.hasGC());
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 0e4351b47..e5923831d 100644
--- a/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
+++ b/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
@@ -1,49 +1,43 @@
 total
- [exports]      : 6       
- [funcs]        : 10      
+ [exports]      : 5       
+ [funcs]        : 18      
  [globals]      : 16      
  [imports]      : 5       
  [memories]     : 1       
  [memory-data]  : 20      
- [table-data]   : 2       
+ [table-data]   : 4       
  [tables]       : 1       
- [tags]         : 0       
- [total]        : 563     
- [vars]         : 7       
- ArrayNew       : 6       
- ArrayNewFixed  : 6       
+ [tags]         : 2       
+ [total]        : 746     
+ [vars]         : 33      
+ ArrayNew       : 7       
+ AtomicFence    : 1       
  AtomicRMW      : 1       
- Binary         : 78      
- Block          : 63      
- Break          : 5       
- Call           : 18      
+ Binary         : 84      
+ Block          : 91      
+ Break          : 3       
+ Call           : 32      
  CallIndirect   : 1       
- CallRef        : 1       
- Const          : 119     
- DataDrop       : 1       
- Drop           : 6       
- GlobalGet      : 28      
- GlobalSet      : 26      
- I31Get         : 1       
- I31New         : 2       
- If             : 21      
- Load           : 22      
- LocalGet       : 43      
- LocalSet       : 26      
- Loop           : 4       
- MemoryInit     : 1       
- Nop            : 10      
- RefAs          : 2       
- RefCast        : 1       
- RefEq          : 2       
- RefFunc        : 7       
- RefNull        : 6       
- RefTest        : 1       
- Return         : 8       
- SIMDExtract    : 1       
- Select         : 1       
- Store          : 3       
- StructNew      : 2       
- TupleMake      : 6       
- Unary          : 20      
- Unreachable    : 14      
+ CallRef        : 2       
+ Const          : 153     
+ Drop           : 11      
+ GlobalGet      : 48      
+ GlobalSet      : 46      
+ I31New         : 1       
+ If             : 29      
+ Load           : 25      
+ LocalGet       : 48      
+ LocalSet       : 30      
+ Loop           : 7       
+ Nop            : 5       
+ RefFunc        : 18      
+ RefIsNull      : 3       
+ RefNull        : 14      
+ Return         : 6       
+ SIMDExtract    : 2       
+ Select         : 4       
+ StructNew      : 3       
+ TupleExtract   : 1       
+ TupleMake      : 12      
+ Unary          : 32      
+ Unreachable    : 26