summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/tools/fuzzing/heap-types.cpp96
-rw-r--r--src/tools/wasm-fuzz-types.cpp8
-rw-r--r--src/wasm/wasm-type.cpp6
-rw-r--r--test/lit/fuzz-types/isorecursive.test24
-rw-r--r--test/lit/help/wasm-fuzz-types.test2
5 files changed, 110 insertions, 26 deletions
diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp
index ce14d129f..e918aa8b5 100644
--- a/src/tools/fuzzing/heap-types.cpp
+++ b/src/tools/fuzzing/heap-types.cpp
@@ -47,6 +47,14 @@ struct HeapTypeGeneratorImpl {
using HeapTypeKind = std::variant<BasicKind, SignatureKind, DataKind>;
std::vector<HeapTypeKind> typeKinds;
+ // For each type, the index one past the end of its recursion group, used to
+ // determine what types could be valid children. Alternatively, the cumulative
+ // size of the current and prior rec groups at each type index.
+ std::vector<Index> recGroupEnds;
+
+ // The index of the type we are currently generating.
+ Index index = 0;
+
HeapTypeGeneratorImpl(Random& rand, FeatureSet features, size_t n)
: result{TypeBuilder(n),
std::vector<std::vector<Index>>(n),
@@ -56,9 +64,8 @@ struct HeapTypeGeneratorImpl {
// Set up the subtype relationships. Start with some number of root types,
// then after that start creating subtypes of existing types. Determine the
// top-level kind of each type in advance so that we can appropriately use
- // types we haven't constructed yet.
- // TODO: Determine individually whether each HeapType is nominal once
- // mixing type systems is expected to work.
+ // types we haven't constructed yet. For simplicity, always choose a
+ // supertype to bea previous type, which is valid in all type systems.
typeKinds.reserve(builder.size());
supertypeIndices.reserve(builder.size());
Index numRoots = 1 + rand.upTo(builder.size());
@@ -80,35 +87,63 @@ struct HeapTypeGeneratorImpl {
}
}
+ // Initialize the recursion groups.
+ recGroupEnds.reserve(builder.size());
+ if (getTypeSystem() != TypeSystem::Isorecursive) {
+ // Recursion groups don't matter and we can choose children as though we
+ // had a single large recursion group.
+ for (Index i = 0; i < builder.size(); ++i) {
+ recGroupEnds.push_back(builder.size());
+ }
+ } else {
+ // We are using isorecursive types, so create groups. Choose an expected
+ // group size uniformly at random, then create groups with random sizes on
+ // a geometric distribution based on that expected size.
+ size_t expectedSize = 1 + rand.upTo(builder.size());
+ Index groupStart = 0;
+ for (Index i = 0; i < builder.size(); ++i) {
+ if (i == builder.size() - 1 || rand.oneIn(expectedSize)) {
+ // End the old group and create a new group.
+ Index newGroupStart = i + 1;
+ builder.createRecGroup(groupStart, newGroupStart - groupStart);
+ for (Index j = groupStart; j < newGroupStart; ++j) {
+ recGroupEnds.push_back(newGroupStart);
+ }
+ groupStart = newGroupStart;
+ }
+ }
+ assert(recGroupEnds.size() == builder.size());
+ }
+
// Create the heap types.
- for (Index i = 0; i < builder.size(); ++i) {
- auto kind = typeKinds[i];
+ for (; index < builder.size(); ++index) {
+ auto kind = typeKinds[index];
if (auto* basic = std::get_if<BasicKind>(&kind)) {
// The type is already determined.
- builder[i] = *basic;
- } else if (!supertypeIndices[i] ||
- builder.isBasic(*supertypeIndices[i])) {
+ builder[index] = *basic;
+ } else if (!supertypeIndices[index] ||
+ builder.isBasic(*supertypeIndices[index])) {
// No nontrivial supertype, so create a root type.
if (std::get_if<SignatureKind>(&kind)) {
- builder[i] = generateSignature();
+ builder[index] = generateSignature();
} else if (std::get_if<DataKind>(&kind)) {
if (rand.oneIn(2)) {
- builder[i] = generateStruct();
+ builder[index] = generateStruct();
} else {
- builder[i] = generateArray();
+ builder[index] = generateArray();
}
} else {
WASM_UNREACHABLE("unexpected kind");
}
} else {
// We have a supertype, so create a subtype.
- HeapType supertype = builder[*supertypeIndices[i]];
+ HeapType supertype = builder[*supertypeIndices[index]];
if (supertype.isSignature()) {
- builder[i] = generateSubSignature(supertype.getSignature());
+ builder[index] = generateSubSignature(supertype.getSignature());
} else if (supertype.isStruct()) {
- builder[i] = generateSubStruct(supertype.getStruct());
+ builder[index] = generateSubStruct(supertype.getStruct());
} else if (supertype.isArray()) {
- builder[i] = generateSubArray(supertype.getArray());
+ builder[index] = generateSubArray(supertype.getArray());
} else {
WASM_UNREACHABLE("unexpected kind");
}
@@ -143,7 +178,8 @@ struct HeapTypeGeneratorImpl {
if (rand.oneIn(4)) {
return generateBasicHeapType();
} else {
- return builder[rand.upTo(builder.size())];
+ Index i = rand.upTo(recGroupEnds[index]);
+ return builder[i];
}
}
@@ -276,17 +312,19 @@ struct HeapTypeGeneratorImpl {
}
template<typename Kind> std::optional<HeapType> pickKind() {
- std::vector<HeapType> candidates;
- // Iterate through the top level kinds, finding matches for `Kind`.
- for (Index i = 0; i < typeKinds.size(); ++i) {
+ std::vector<Index> candidateIndices;
+ // Iterate through the top level kinds, finding matches for `Kind`. Since we
+ // are constructing a child, we can only look through the end of the current
+ // recursion group.
+ for (Index i = 0, end = recGroupEnds[index]; i < end; ++i) {
if (std::get_if<Kind>(&typeKinds[i])) {
- candidates.push_back(builder[i]);
+ candidateIndices.push_back(i);
}
}
- if (candidates.size()) {
- return rand.pick(candidates);
+ if (candidateIndices.size()) {
+ return builder[rand.pick(candidateIndices)];
} else {
- return {};
+ return std::nullopt;
}
}
@@ -331,8 +369,16 @@ struct HeapTypeGeneratorImpl {
HeapType pickSubHeapType(HeapType type) {
auto it = typeIndices.find(type);
if (it != typeIndices.end()) {
- // This is a constructed type, so we know where its subtypes are.
- return builder[rand.pick(subtypeIndices[typeIndices[type]])];
+ // This is a constructed type, so we know where its subtypes are, but we
+ // can only choose those defined before the end of the current recursion
+ // group.
+ std::vector<Index> candidateIndices;
+ for (auto i : subtypeIndices[typeIndices[type]]) {
+ if (i < recGroupEnds[index]) {
+ candidateIndices.push_back(i);
+ }
+ }
+ return builder[rand.pick(candidateIndices)];
} else {
// This is not a constructed type, so it must be a basic type.
assert(type.isBasic());
diff --git a/src/tools/wasm-fuzz-types.cpp b/src/tools/wasm-fuzz-types.cpp
index e736c8977..9e1c7a83e 100644
--- a/src/tools/wasm-fuzz-types.cpp
+++ b/src/tools/wasm-fuzz-types.cpp
@@ -184,6 +184,14 @@ int main(int argc, const char* argv[]) {
[&](Options*, const std::string& arg) {
system = TypeSystem::Equirecursive;
});
+ options.add("--hybrid",
+ "",
+ "Use the isorecursive hybrid type system",
+ WasmFuzzTypesOption,
+ Options::Arguments::Zero,
+ [&](Options*, const std::string& arg) {
+ system = TypeSystem::Isorecursive;
+ });
options.parse(argc, argv);
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 89592fc37..9e9a9603d 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -1763,7 +1763,8 @@ HeapType TypeBounder::lub(HeapType a, HeapType b) {
return getBasicLUB();
}
- if (typeSystem == TypeSystem::Nominal) {
+ if (typeSystem == TypeSystem::Nominal ||
+ typeSystem == TypeSystem::Isorecursive) {
// Walk up the subtype tree to find the LUB. Ascend the tree from both `a`
// and `b` in lockstep. The first type we see for a second time must be the
// LUB because there are no cycles and the only way to encounter a type
@@ -3675,6 +3676,9 @@ std::optional<TypeBuilder::Error> canonicalizeIsorecursive(
for (size_t index = 0; index < state.results.size(); ++index) {
HeapType type = state.results[index];
+ if (type.isBasic()) {
+ continue;
+ }
// Validate the supertype. Supertypes must precede their subtypes.
if (auto super = type.getSuperType()) {
if (!indexOfType.count(*super)) {
diff --git a/test/lit/fuzz-types/isorecursive.test b/test/lit/fuzz-types/isorecursive.test
new file mode 100644
index 000000000..60eabec39
--- /dev/null
+++ b/test/lit/fuzz-types/isorecursive.test
@@ -0,0 +1,24 @@
+;; RUN: wasm-fuzz-types --hybrid -v --seed=0 | filecheck %s
+
+;; CHECK: Running with seed 0
+;; CHECK-NEXT: Built 20 types:
+;; CHECK-NEXT: 0: (struct)
+;; CHECK-NEXT: 1: (func (param i31ref) (result (ref extern)))
+;; CHECK-NEXT: 2: (array (mut (rtt 0 extern)))
+;; CHECK-NEXT: 3: (array (mut (rtt 0 extern)))
+;; CHECK-NEXT: 4: (array (mut (rtt 0 extern)))
+;; CHECK-NEXT: 5: (array (mut (rtt 0 extern)))
+;; CHECK-NEXT: 6: (array (mut (rtt 0 extern)))
+;; CHECK-NEXT: 7: (struct (field (mut (ref (struct (field i16 (mut i32) (mut i16)))))))
+;; CHECK-NEXT: 8: (struct (field i16 (mut i32) (mut i16)))
+;; CHECK-NEXT: 9: (array (mut (rtt 0 extern)))
+;; CHECK-NEXT: 10: (struct)
+;; CHECK-NEXT: 11: (array (mut (rtt 0 extern)))
+;; CHECK-NEXT: 12: (struct (field (mut i8) (rtt (struct))))
+;; CHECK-NEXT: 13: (array (mut (rtt 0 extern)))
+;; CHECK-NEXT: 14: (struct (field funcref f64 (mut (rtt (struct))) (ref null (func (param i31ref) (result (ref extern)))) i8 (ref null (struct (field (mut (ref (struct (field i16 (mut i32) (mut i16))))))))))
+;; CHECK-NEXT: 15: (func (param i31ref) (result (ref extern)))
+;; CHECK-NEXT: 16: (array (mut (rtt 0 extern)))
+;; CHECK-NEXT: 17: (struct (field funcref f64 (mut (rtt (struct))) (ref null (func (param i31ref) (result (ref extern)))) i8 (ref null (struct (field (mut (ref (struct (field i16 (mut i32) (mut i16))))))))))
+;; CHECK-NEXT: 18: (struct (field (mut i8) (rtt (struct))))
+;; CHECK-NEXT: 19: (func (param i31ref) (result (ref extern)))
diff --git a/test/lit/help/wasm-fuzz-types.test b/test/lit/help/wasm-fuzz-types.test
index 684b2a677..a282aa4a6 100644
--- a/test/lit/help/wasm-fuzz-types.test
+++ b/test/lit/help/wasm-fuzz-types.test
@@ -17,6 +17,8 @@
;; CHECK-NEXT:
;; CHECK-NEXT: --structural Use the equirecursive type system
;; CHECK-NEXT:
+;; CHECK-NEXT: --hybrid Use the isorecursive hybrid type system
+;; CHECK-NEXT:
;; CHECK-NEXT:
;; CHECK-NEXT: General options:
;; CHECK-NEXT: ----------------
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-08 02:42:44 +0000