summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/tools/fuzzing/heap-types.cpp155
-rw-r--r--src/tools/fuzzing/heap-types.h23
-rw-r--r--src/tools/wasm-fuzz-types.cpp32
-rw-r--r--src/wasm-type.h4
-rw-r--r--src/wasm/wasm-type.cpp3
5 files changed, 126 insertions, 91 deletions
diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp
index 9992baf55..ce14d129f 100644
--- a/src/tools/fuzzing/heap-types.cpp
+++ b/src/tools/fuzzing/heap-types.cpp
@@ -23,17 +23,17 @@ namespace wasm {
namespace {
-struct HeapTypeGenerator {
+struct HeapTypeGeneratorImpl {
+ HeapTypeGenerator result;
+ TypeBuilder& builder;
+ std::vector<std::vector<Index>>& subtypeIndices;
+ std::vector<std::optional<Index>> supertypeIndices;
Random& rand;
FeatureSet features;
- TypeBuilder builder;
// Map the HeapTypes we are building to their indices in the builder.
std::unordered_map<HeapType, Index> typeIndices;
- // For each type we will build, the indices of its subtypes we will build.
- std::vector<std::vector<Index>> subtypeIndices;
-
// Abstract over all the types that may be assigned to a builder slot.
using Assignable =
std::variant<HeapType::BasicHeapType, Signature, Struct, Array>;
@@ -47,8 +47,74 @@ struct HeapTypeGenerator {
using HeapTypeKind = std::variant<BasicKind, SignatureKind, DataKind>;
std::vector<HeapTypeKind> typeKinds;
- HeapTypeGenerator(Random& rand, FeatureSet features, size_t n)
- : rand(rand), features(features), builder(n), subtypeIndices(n) {}
+ HeapTypeGeneratorImpl(Random& rand, FeatureSet features, size_t n)
+ : result{TypeBuilder(n),
+ std::vector<std::vector<Index>>(n),
+ std::vector<std::optional<Index>>(n)},
+ builder(result.builder), subtypeIndices(result.subtypeIndices),
+ supertypeIndices(n), rand(rand), features(features) {
+ // 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.
+ typeKinds.reserve(builder.size());
+ supertypeIndices.reserve(builder.size());
+ Index numRoots = 1 + rand.upTo(builder.size());
+ for (Index i = 0; i < builder.size(); ++i) {
+ typeIndices.insert({builder[i], i});
+ // Everything is a subtype of itself.
+ subtypeIndices[i].push_back(i);
+ if (i < numRoots) {
+ // This is a root type with no supertype. Choose a kind for this type.
+ typeKinds.emplace_back(generateHeapTypeKind());
+ } else {
+ // This is a subtype. Choose one of the previous types to be the
+ // supertype.
+ Index super = rand.upTo(i);
+ builder[i].subTypeOf(builder[super]);
+ supertypeIndices[i] = super;
+ subtypeIndices[super].push_back(i);
+ typeKinds.push_back(getSubKind(typeKinds[super]));
+ }
+ }
+
+ // Create the heap types.
+ for (Index i = 0; i < builder.size(); ++i) {
+ auto kind = typeKinds[i];
+ if (auto* basic = std::get_if<BasicKind>(&kind)) {
+ // The type is already determined.
+ builder[i] = *basic;
+ } else if (!supertypeIndices[i] ||
+ builder.isBasic(*supertypeIndices[i])) {
+ // No nontrivial supertype, so create a root type.
+ if (std::get_if<SignatureKind>(&kind)) {
+ builder[i] = generateSignature();
+ } else if (std::get_if<DataKind>(&kind)) {
+ if (rand.oneIn(2)) {
+ builder[i] = generateStruct();
+ } else {
+ builder[i] = generateArray();
+ }
+ } else {
+ WASM_UNREACHABLE("unexpected kind");
+ }
+ } else {
+ // We have a supertype, so create a subtype.
+ HeapType supertype = builder[*supertypeIndices[i]];
+ if (supertype.isSignature()) {
+ builder[i] = generateSubSignature(supertype.getSignature());
+ } else if (supertype.isStruct()) {
+ builder[i] = generateSubStruct(supertype.getStruct());
+ } else if (supertype.isArray()) {
+ builder[i] = generateSubArray(supertype.getArray());
+ } else {
+ WASM_UNREACHABLE("unexpected kind");
+ }
+ }
+ }
+ }
HeapType::BasicHeapType generateBasicHeapType() {
return rand.pick(HeapType::func,
@@ -404,82 +470,13 @@ struct HeapTypeGenerator {
return super;
}
}
-
- std::vector<HeapType> generate() {
- // 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.
- typeKinds.reserve(builder.size());
- std::vector<std::optional<Index>> supertypeIndices(builder.size());
- Index numRoots = 1 + rand.upTo(builder.size());
- for (Index i = 0; i < builder.size(); ++i) {
- typeIndices.insert({builder[i], i});
- // Everything is a subtype of itself.
- subtypeIndices[i].push_back(i);
- if (i < numRoots) {
- // This is a root type with no supertype. Choose a kind for this type.
- typeKinds.emplace_back(generateHeapTypeKind());
- } else {
- // This is a subtype. Choose one of the previous types to be the
- // supertype.
- Index super = rand.upTo(i);
- builder[i].subTypeOf(builder[super]);
- supertypeIndices[i] = super;
- subtypeIndices[super].push_back(i);
- typeKinds.push_back(getSubKind(typeKinds[super]));
- }
- }
-
- // Create the heap types.
- for (Index i = 0; i < builder.size(); ++i) {
- auto kind = typeKinds[i];
- if (auto* basic = std::get_if<BasicKind>(&kind)) {
- // The type is already determined.
- builder[i] = *basic;
- } else if (!supertypeIndices[i] ||
- builder.isBasic(*supertypeIndices[i])) {
- // No nontrivial supertype, so create a root type.
- if (std::get_if<SignatureKind>(&kind)) {
- builder[i] = generateSignature();
- } else if (std::get_if<DataKind>(&kind)) {
- if (rand.oneIn(2)) {
- builder[i] = generateStruct();
- } else {
- builder[i] = generateArray();
- }
- } else {
- WASM_UNREACHABLE("unexpected kind");
- }
- } else {
- // We have a supertype, so create a subtype.
- HeapType supertype = builder[*supertypeIndices[i]];
- if (supertype.isSignature()) {
- builder[i] = generateSubSignature(supertype.getSignature());
- } else if (supertype.isStruct()) {
- builder[i] = generateSubStruct(supertype.getStruct());
- } else if (supertype.isArray()) {
- builder[i] = generateSubArray(supertype.getArray());
- } else {
- WASM_UNREACHABLE("unexpected kind");
- }
- }
- }
- return builder.build();
- }
};
} // anonymous namespace
-namespace HeapTypeFuzzer {
-
-std::vector<HeapType>
-generateHeapTypes(Random& rand, FeatureSet features, size_t n) {
- return HeapTypeGenerator(rand, features, n).generate();
+HeapTypeGenerator
+HeapTypeGenerator::create(Random& rand, FeatureSet features, size_t n) {
+ return HeapTypeGeneratorImpl(rand, features, n).result;
}
-} // namespace HeapTypeFuzzer
-
} // namespace wasm
diff --git a/src/tools/fuzzing/heap-types.h b/src/tools/fuzzing/heap-types.h
index a9a580cf6..c54e3053d 100644
--- a/src/tools/fuzzing/heap-types.h
+++ b/src/tools/fuzzing/heap-types.h
@@ -19,14 +19,27 @@
#include "tools/fuzzing/random.h"
#include "wasm-type.h"
+#include "wasm.h"
+#include <optional>
#include <vector>
-namespace wasm::HeapTypeFuzzer {
+namespace wasm {
-// Generate a vector of `n` random HeapTypes with interesting subtyping.
-std::vector<HeapType>
-generateHeapTypes(Random& rand, FeatureSet features, size_t n);
+struct HeapTypeGenerator {
+ // The builder containing the randomly generated types.
+ TypeBuilder builder;
-} // namespace wasm::HeapTypeFuzzer
+ // The intended subtypes of each built type.
+ std::vector<std::vector<Index>> subtypeIndices;
+
+ // The intended supertype of each built type, if any.
+ std::vector<std::optional<Index>> supertypeIndices;
+
+ // Create a populated `HeapTypeGenerator` with `n` random HeapTypes with
+ // interesting subtyping.
+ static HeapTypeGenerator create(Random& rand, FeatureSet features, size_t n);
+};
+
+} // namespace wasm
#endif // wasm_tools_fuzzing_heap_types_h
diff --git a/src/tools/wasm-fuzz-types.cpp b/src/tools/wasm-fuzz-types.cpp
index 564bfa212..bea43e500 100644
--- a/src/tools/wasm-fuzz-types.cpp
+++ b/src/tools/wasm-fuzz-types.cpp
@@ -49,14 +49,34 @@ struct Fuzzer {
Random rand(std::move(bytes));
// TODO: Options to control the size or set it randomly.
- std::vector<HeapType> types =
- HeapTypeFuzzer::generateHeapTypes(rand, FeatureSet::All, 20);
+ HeapTypeGenerator generator =
+ HeapTypeGenerator::create(rand, FeatureSet::All, 20);
+ std::vector<HeapType> types = generator.builder.build();
- // TODO: Do some sort of checking or manipulation on the types
if (verbose) {
- std::cout << "Built " << types.size() << " types:\n";
- for (size_t i = 0; i < types.size(); ++i) {
- std::cout << i << ": " << types[i] << "\n";
+ printTypes(types);
+ }
+
+ checkSubtypes(types, generator.subtypeIndices);
+ }
+
+ void printTypes(const std::vector<HeapType>& types) {
+ std::cout << "Built " << types.size() << " types:\n";
+ for (size_t i = 0; i < types.size(); ++i) {
+ std::cout << i << ": " << types[i] << "\n";
+ }
+ }
+
+ void checkSubtypes(const std::vector<HeapType>& types,
+ const std::vector<std::vector<Index>>& subtypeIndices) {
+ for (size_t super = 0; super < types.size(); ++super) {
+ for (auto sub : subtypeIndices[super]) {
+ if (!HeapType::isSubType(types[sub], types[super])) {
+ Fatal() << "HeapType " << sub << " should be a subtype of HeapType "
+ << super << " but is not!\n"
+ << sub << ": " << types[sub] << "\n"
+ << super << ": " << types[super] << "\n";
+ }
}
}
}
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 2362a95aa..fc2a3b290 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -559,9 +559,11 @@ struct TypeBuilder {
~TypeBuilder();
TypeBuilder(TypeBuilder& other) = delete;
- TypeBuilder(TypeBuilder&& other) = delete;
TypeBuilder& operator=(TypeBuilder&) = delete;
+ TypeBuilder(TypeBuilder&& other);
+ TypeBuilder& operator=(TypeBuilder&& other);
+
// Append `n` new uninitialized HeapType slots to the end of the TypeBuilder.
void grow(size_t n);
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 443ab9da2..7dc336d87 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -2270,6 +2270,9 @@ TypeBuilder::TypeBuilder(size_t n) {
TypeBuilder::~TypeBuilder() = default;
+TypeBuilder::TypeBuilder(TypeBuilder&& other) = default;
+TypeBuilder& TypeBuilder::operator=(TypeBuilder&& other) = default;
+
void TypeBuilder::grow(size_t n) {
assert(size() + n > size());
impl->entries.resize(size() + n);
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-06 12:27:19 +0000