summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/tools/CMakeLists.txt2
-rw-r--r--src/tools/fuzzing.h94
-rw-r--r--src/tools/fuzzing/fuzzing.cpp56
-rw-r--r--src/tools/fuzzing/heap-types.cpp499
-rw-r--r--src/tools/fuzzing/heap-types.h32
-rw-r--r--src/tools/fuzzing/parameters.h73
-rw-r--r--src/tools/fuzzing/random.cpp3
-rw-r--r--src/tools/fuzzing/random.h90
-rw-r--r--src/tools/wasm-fuzz-types.cpp122
-rw-r--r--src/wasm-type.h7
-rw-r--r--src/wasm/wasm-type.cpp17
-rw-r--r--test/lit/fuzz-types/nominal.test24
-rw-r--r--test/lit/fuzz-types/structural.test47
13 files changed, 946 insertions, 120 deletions
diff --git a/src/tools/CMakeLists.txt b/src/tools/CMakeLists.txt
index cda38a369..ac8927d54 100644
--- a/src/tools/CMakeLists.txt
+++ b/src/tools/CMakeLists.txt
@@ -12,6 +12,7 @@ include_directories(fuzzing)
FILE(GLOB fuzzing_HEADERS fuzzing/*h)
set(fuzzing_SOURCES
fuzzing/fuzzing.cpp
+ fuzzing/heap-types.cpp
fuzzing/random.cpp
${fuzzing_HEADERS}
)
@@ -25,5 +26,6 @@ binaryen_add_executable(wasm-as wasm-as.cpp)
binaryen_add_executable(wasm-dis wasm-dis.cpp)
binaryen_add_executable(wasm-ctor-eval wasm-ctor-eval.cpp)
binaryen_add_executable(wasm-reduce wasm-reduce.cpp)
+binaryen_add_executable(wasm-fuzz-types "${fuzzing_SOURCES};wasm-fuzz-types.cpp")
add_subdirectory(wasm-split)
diff --git a/src/tools/fuzzing.h b/src/tools/fuzzing.h
index bc3516d4c..a9cc9eec0 100644
--- a/src/tools/fuzzing.h
+++ b/src/tools/fuzzing.h
@@ -142,6 +142,19 @@ private:
bool oneIn(Index x) { return random.oneIn(x); }
Index upToSquared(Index x) { return random.upToSquared(x); }
+ // Pick from a vector-like container or a fixed list.
+ template<typename T> const typename T::value_type& pick(const T& vec) {
+ return random.pick(vec);
+ }
+ template<typename T, typename... Args> T pick(T first, Args... args) {
+ return random.pick(first, args...);
+ }
+ // Pick from options associated with features.
+ template<typename T> using FeatureOptions = Random::FeatureOptions<T>;
+ template<typename T> const T pick(FeatureOptions<T>& picker) {
+ return random.pick(picker);
+ }
+
// Setup methods
void setupMemory();
void setupHeapTypes();
@@ -296,87 +309,6 @@ private:
Index logify(Index x) {
return std::floor(std::log(std::max(Index(1) + x, Index(1))));
}
-
- // Pick from a vector-like container
- template<typename T> const typename T::value_type& pick(const T& vec) {
- assert(!vec.empty());
- auto index = upTo(vec.size());
- return vec[index];
- }
-
- // pick from a fixed list
- template<typename T, typename... Args> T pick(T first, Args... args) {
- auto num = sizeof...(Args) + 1;
- auto temp = upTo(num);
- return pickGivenNum<T>(temp, first, args...);
- }
-
- template<typename T> T pickGivenNum(size_t num, T first) {
- assert(num == 0);
- return first;
- }
-
-// Trick to avoid a bug in GCC 7.x.
-// Upstream bug report: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82800
-#define GCC_VERSION \
- (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__)
-#if GCC_VERSION > 70000 && GCC_VERSION < 70300
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
-#endif
-
- template<typename T, typename... Args>
- T pickGivenNum(size_t num, T first, Args... args) {
- if (num == 0) {
- return first;
- }
- return pickGivenNum<T>(num - 1, args...);
- }
-
-#if GCC_VERSION > 70000 && GCC_VERSION < 70300
-#pragma GCC diagnostic pop
-#endif
-
- template<typename T> struct FeatureOptions {
- template<typename... Ts>
- FeatureOptions<T>& add(FeatureSet feature, T option, Ts... rest) {
- options[feature].push_back(option);
- return add(feature, rest...);
- }
-
- struct WeightedOption {
- T option;
- size_t weight;
- };
-
- template<typename... Ts>
- FeatureOptions<T>&
- add(FeatureSet feature, WeightedOption weightedOption, Ts... rest) {
- for (size_t i = 0; i < weightedOption.weight; i++) {
- options[feature].push_back(weightedOption.option);
- }
- return add(feature, rest...);
- }
-
- FeatureOptions<T>& add(FeatureSet feature) { return *this; }
-
- std::map<FeatureSet, std::vector<T>> options;
- };
-
- template<typename T> std::vector<T> items(FeatureOptions<T>& picker) {
- std::vector<T> matches;
- for (const auto& item : picker.options) {
- if (wasm.features.has(item.first)) {
- matches.reserve(matches.size() + item.second.size());
- matches.insert(matches.end(), item.second.begin(), item.second.end());
- }
- }
- return matches;
- }
-
- template<typename T> const T pick(FeatureOptions<T>& picker) {
- return pick(items(picker));
- }
};
} // namespace wasm
diff --git a/src/tools/fuzzing/fuzzing.cpp b/src/tools/fuzzing/fuzzing.cpp
index 1f745f1ee..84b0e2c5c 100644
--- a/src/tools/fuzzing/fuzzing.cpp
+++ b/src/tools/fuzzing/fuzzing.cpp
@@ -1,53 +1,35 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
#include "tools/fuzzing.h"
+#include "tools/fuzzing/heap-types.h"
+#include "tools/fuzzing/parameters.h"
namespace wasm {
-// Constants that control fuzzing.
namespace {
-// The maximum amount of params to each function.
-constexpr int MAX_PARAMS = 10;
-
-// The maximum amount of vars in each function.
-constexpr int MAX_VARS = 20;
-
-// The maximum number of globals in a module.
-constexpr int MAX_GLOBALS = 20;
-
-// The maximum number of tuple elements.
-constexpr int MAX_TUPLE_SIZE = 6;
-
-// The maximum rtt depth.
-constexpr int MAX_RTT_DEPTH = 3;
-
-// some things require luck, try them a few times
-constexpr int TRIES = 10;
-
-// beyond a nesting limit, greatly decrease the chance to continue to nest
-constexpr int NESTING_LIMIT = 11;
-
-// the maximum size of a block
-constexpr int BLOCK_FACTOR = 5;
-
-// the memory that we use, a small portion so that we have a good chance of
-// looking at writes (we also look outside of this region with small
-// probability) this should be a power of 2
-constexpr Address USABLE_MEMORY = 16;
-
-// the number of runtime iterations (function calls, loop backbranches) we
-// allow before we stop execution with a trap, to prevent hangs. 0 means
-// no hang protection.
-constexpr int HANG_LIMIT = 10;
// Weighting for the core make* methods. Some nodes are important enough that
// we should do them quite often.
-constexpr size_t VeryImportant = 4;
-constexpr size_t Important = 2;
} // anonymous namespace
TranslateToFuzzReader::TranslateToFuzzReader(Module& wasm,
std::vector<char>&& input)
- : wasm(wasm), builder(wasm), random(std::move(input)) {
+ : wasm(wasm), builder(wasm), random(std::move(input), wasm.features) {
// - funcref cannot be logged because referenced functions can be inlined or
// removed during optimization
// - there's no point in logging externref or anyref because these are opaque
diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp
new file mode 100644
index 000000000..71f701860
--- /dev/null
+++ b/src/tools/fuzzing/heap-types.cpp
@@ -0,0 +1,499 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <variant>
+
+#include "tools/fuzzing/heap-types.h"
+#include "tools/fuzzing/parameters.h"
+
+namespace wasm {
+
+namespace {
+
+struct HeapTypeGenerator {
+ 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>;
+
+ // Top-level kinds, chosen before the types are actually constructed. This
+ // allows us to choose HeapTypes that we know will be subtypes of data or func
+ // before we actually generate the types.
+ using BasicKind = HeapType::BasicHeapType;
+ struct SignatureKind {};
+ struct DataKind {};
+ 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) {}
+
+ HeapType::BasicHeapType generateBasicHeapType() {
+ return rand.pick(HeapType::func,
+ HeapType::ext,
+ HeapType::any,
+ HeapType::eq,
+ HeapType::i31,
+ HeapType::data);
+ }
+
+ Type::BasicType generateBasicType() {
+ return rand.pick(
+ Random::FeatureOptions<Type::BasicType>{}
+ .add(FeatureSet::MVP, Type::i32, Type::i64, Type::f32, Type::f64)
+ .add(FeatureSet::SIMD, Type::v128)
+ .add(FeatureSet::ReferenceTypes | FeatureSet::GC,
+ Type::funcref,
+ Type::externref,
+ Type::anyref,
+ Type::eqref,
+ Type::i31ref,
+ Type::dataref));
+ }
+
+ HeapType generateHeapType() {
+ if (rand.oneIn(4)) {
+ return generateBasicHeapType();
+ } else {
+ return builder[rand.upTo(builder.size())];
+ }
+ }
+
+ // TODO: Create an enum for `Defaultable, NonDefaultable` in wasm-type.h.
+ Type generateRefType(bool defaultable = false) {
+ auto heapType = generateHeapType();
+ auto nullability = (defaultable || rand.oneIn(2)) ? Nullable : NonNullable;
+ return builder.getTempRefType(heapType, nullability);
+ }
+
+ Type generateRttType() {
+ auto heapType = generateHeapType();
+ auto depth = rand.oneIn(2) ? Rtt::NoDepth : rand.upTo(MAX_RTT_DEPTH);
+ return builder.getTempRttType(Rtt(depth, heapType));
+ }
+
+ Type generateSingleType(bool defaultable = false) {
+ switch (rand.upTo(defaultable ? 2 : 3)) {
+ case 0:
+ return generateBasicType();
+ case 1:
+ return generateRefType(defaultable);
+ case 2:
+ return generateRttType();
+ }
+ WASM_UNREACHABLE("unexpected");
+ }
+
+ Type generateTupleType() {
+ std::vector<Type> types(2 + rand.upTo(MAX_TUPLE_SIZE - 1));
+ for (auto& type : types) {
+ // Make sure tuples are defaultable. See comment in
+ // TranslateToFuzzReader::getTupleType.
+ type = generateSingleType(/*defaultable=*/true);
+ }
+ return builder.getTempTupleType(Tuple(types));
+ }
+
+ Type generateReturnType() {
+ // This is similar to TranslateToFuzzreader::getControlFlowType.
+ if (rand.oneIn(10)) {
+ return Type::none;
+ } else if (features.hasMultivalue() && rand.oneIn(5)) {
+ return generateTupleType();
+ } else {
+ return generateSingleType(/*defaultable=*/true);
+ }
+ }
+
+ Signature generateSignature() {
+ std::vector<Type> types(rand.upToSquared(MAX_PARAMS));
+ for (auto& type : types) {
+ type = generateSingleType();
+ }
+ auto params = builder.getTempTupleType(types);
+ return {params, generateReturnType()};
+ }
+
+ Field generateField() {
+ auto mutability = rand.oneIn(2) ? Mutable : Immutable;
+ if (rand.oneIn(6)) {
+ return {rand.oneIn(2) ? Field::i8 : Field::i16, mutability};
+ } else {
+ return {generateSingleType(), mutability};
+ }
+ }
+
+ Struct generateStruct() {
+ std::vector<Field> fields(rand.upTo(MAX_STRUCT_SIZE + 1));
+ for (auto& field : fields) {
+ field = generateField();
+ }
+ return {fields};
+ }
+
+ Array generateArray() { return {generateField()}; }
+
+ Assignable generateSubData() {
+ switch (rand.upTo(2)) {
+ case 0:
+ return generateStruct();
+ case 1:
+ return generateArray();
+ }
+ WASM_UNREACHABLE("unexpected index");
+ }
+
+ Assignable generateSubEq() {
+ switch (rand.upTo(3)) {
+ case 0:
+ return HeapType::i31;
+ case 1:
+ return HeapType::data;
+ case 2:
+ return generateSubData();
+ }
+ WASM_UNREACHABLE("unexpected index");
+ }
+
+ Assignable generateSubAny() {
+ switch (rand.upTo(4)) {
+ case 0:
+ return HeapType::eq;
+ case 1:
+ return HeapType::func;
+ case 2:
+ return generateSubEq();
+ case 3:
+ return generateSignature();
+ }
+ WASM_UNREACHABLE("unexpected index");
+ }
+
+ Assignable generateSubBasic(HeapType::BasicHeapType type) {
+ if (rand.oneIn(2)) {
+ return type;
+ } else {
+ switch (type) {
+ case HeapType::ext:
+ case HeapType::i31:
+ // No other subtypes.
+ return type;
+ case HeapType::func:
+ return generateSignature();
+ case HeapType::any:
+ return generateSubAny();
+ case HeapType::eq:
+ return generateSubEq();
+ case HeapType::data:
+ return generateSubData();
+ }
+ WASM_UNREACHABLE("unexpected index");
+ }
+ }
+
+ 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) {
+ if (std::get_if<Kind>(&typeKinds[i])) {
+ candidates.push_back(builder[i]);
+ }
+ }
+ if (candidates.size()) {
+ return rand.pick(candidates);
+ } else {
+ return {};
+ }
+ }
+
+ HeapType pickSubFunc() {
+ if (auto type = pickKind<SignatureKind>()) {
+ return *type;
+ } else {
+ return HeapType::func;
+ }
+ }
+
+ HeapType pickSubData() {
+ if (auto type = pickKind<DataKind>()) {
+ return *type;
+ } else {
+ return HeapType::data;
+ }
+ }
+
+ HeapType pickSubEq() {
+ if (rand.oneIn(2)) {
+ return HeapType::i31;
+ } else {
+ return pickSubData();
+ }
+ }
+
+ HeapType pickSubAny() {
+ switch (rand.upTo(4)) {
+ case 0:
+ return HeapType::func;
+ case 1:
+ return HeapType::eq;
+ case 2:
+ return pickSubFunc();
+ case 3:
+ return pickSubEq();
+ }
+ WASM_UNREACHABLE("unexpected index");
+ }
+
+ 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]])];
+ } else {
+ // This is not a constructed type, so it must be a basic type.
+ assert(type.isBasic());
+ switch (type.getBasic()) {
+ case HeapType::func:
+ return pickSubFunc();
+ case HeapType::ext:
+ return HeapType::ext;
+ case HeapType::any:
+ return pickSubAny();
+ case HeapType::eq:
+ return pickSubEq();
+ case HeapType::i31:
+ return HeapType::i31;
+ case HeapType::data:
+ return pickSubData();
+ }
+ WASM_UNREACHABLE("unexpected kind");
+ }
+ }
+
+ // TODO: Make this part of the wasm-type.h API
+ struct Ref {
+ HeapType type;
+ Nullability nullability;
+ };
+
+ Ref generateSubRef(Ref super) {
+ auto nullability = super.nullability == NonNullable
+ ? NonNullable
+ : rand.oneIn(2) ? Nullable : NonNullable;
+ return {pickSubHeapType(super.type), nullability};
+ }
+
+ Rtt generateSubRtt(Rtt super) {
+ auto depth = super.hasDepth()
+ ? super.depth
+ : rand.oneIn(2) ? Rtt::NoDepth : rand.upTo(MAX_RTT_DEPTH);
+ return {depth, super.heapType};
+ }
+
+ Type generateSubtype(Type type) {
+ if (type.isBasic()) {
+ // We do not construct types with basic reference types (we go through the
+ // TypeBuilder for those instead), so this must be a non-reference basic
+ // type, which means it has no other subtypes.
+ return type;
+ } else if (type.isRef()) {
+ auto ref = generateSubRef({type.getHeapType(), type.getNullability()});
+ return builder.getTempRefType(ref.type, ref.nullability);
+ } else if (type.isRtt()) {
+ auto rtt = generateSubRtt(type.getRtt());
+ return builder.getTempRttType(rtt);
+ } else {
+ WASM_UNREACHABLE("unexpected type kind");
+ }
+ }
+
+ Signature generateSubSignature(Signature super) {
+ // TODO: Update this once we support nontrivial function subtyping.
+ return super;
+ }
+
+ Field generateSubField(Field super) {
+ if (super.mutable_ == Mutable) {
+ // Only immutable fields support subtyping.
+ return super;
+ }
+ if (super.isPacked()) {
+ // No other subtypes of i8 or i16.
+ return super;
+ }
+ return {generateSubtype(super.type), Immutable};
+ }
+
+ Struct generateSubStruct(const Struct& super) {
+ if (rand.oneIn(2)) {
+ return super;
+ }
+ std::vector<Field> fields;
+ // Depth subtyping
+ for (auto field : super.fields) {
+ fields.push_back(generateSubField(field));
+ }
+ // Width subtyping
+ Index extra = rand.upTo(MAX_STRUCT_SIZE + 1 - fields.size());
+ for (Index i = 0; i < extra; ++i) {
+ fields.push_back(generateField());
+ }
+ return {fields};
+ }
+
+ Array generateSubArray(Array super) {
+ if (rand.oneIn(2)) {
+ return super;
+ }
+ return {generateSubField(super.element)};
+ }
+
+ HeapTypeKind generateHeapTypeKind() {
+ // Building basic heap types is only allowed in equirecursive mode.
+ // TODO: Relax this.
+ size_t options = 2;
+ if (getTypeSystem() == TypeSystem::Equirecursive) {
+ ++options;
+ }
+ switch (rand.upTo(options)) {
+ case 0:
+ return SignatureKind{};
+ case 1:
+ return DataKind{};
+ case 2:
+ return BasicKind{generateBasicHeapType()};
+ }
+ WASM_UNREACHABLE("unexpected index");
+ }
+
+ HeapTypeKind getSubKind(HeapTypeKind super) {
+ if (auto* basic = std::get_if<BasicKind>(&super)) {
+ if (rand.oneIn(8)) {
+ return super;
+ }
+ switch (*basic) {
+ case HeapType::func:
+ return SignatureKind{};
+ case HeapType::ext:
+ case HeapType::i31:
+ return super;
+ case HeapType::any:
+ return generateHeapTypeKind();
+ case HeapType::eq:
+ if (rand.oneIn(4)) {
+ return HeapType::i31;
+ } else {
+ return DataKind{};
+ }
+ case HeapType::data:
+ return DataKind{};
+ }
+ WASM_UNREACHABLE("unexpected kind");
+ } else {
+ // Signature and Data types can only have Signature and Data subtypes.
+ 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) {
+ if (!supertypeIndices[i]) {
+ // Create a root type.
+ auto kind = typeKinds[i];
+ if (auto* basic = std::get_if<BasicKind>(&kind)) {
+ builder[i] = *basic;
+ } else 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.
+ Index super = *supertypeIndices[i];
+ HeapType supertype = builder[super];
+ if (builder.isBasic(super)) {
+ auto assignable = generateSubBasic(builder.getBasic(super));
+ std::visit([&](auto&& arg) { builder[i] = arg; }, assignable);
+ } else 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();
+}
+
+} // namespace HeapTypeFuzzer
+
+} // namespace wasm
diff --git a/src/tools/fuzzing/heap-types.h b/src/tools/fuzzing/heap-types.h
new file mode 100644
index 000000000..a9a580cf6
--- /dev/null
+++ b/src/tools/fuzzing/heap-types.h
@@ -0,0 +1,32 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef wasm_tools_fuzzing_heap_types_h
+#define wasm_tools_fuzzing_heap_types_h
+
+#include "tools/fuzzing/random.h"
+#include "wasm-type.h"
+#include <vector>
+
+namespace wasm::HeapTypeFuzzer {
+
+// Generate a vector of `n` random HeapTypes with interesting subtyping.
+std::vector<HeapType>
+generateHeapTypes(Random& rand, FeatureSet features, size_t n);
+
+} // namespace wasm::HeapTypeFuzzer
+
+#endif // wasm_tools_fuzzing_heap_types_h
diff --git a/src/tools/fuzzing/parameters.h b/src/tools/fuzzing/parameters.h
new file mode 100644
index 000000000..6618ce6db
--- /dev/null
+++ b/src/tools/fuzzing/parameters.h
@@ -0,0 +1,73 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// Constants that control fuzzing.
+
+#ifndef wasm_tools_fuzzing_parameters_h
+#define wasm_tools_fuzzing_parameters_h
+
+#include "wasm.h"
+
+namespace wasm {
+
+// The maximum amount of params to each function.
+constexpr int MAX_PARAMS = 10;
+
+// The maximum amount of vars in each function.
+constexpr int MAX_VARS = 20;
+
+// The maximum number of globals in a module.
+constexpr int MAX_GLOBALS = 20;
+
+// The maximum number of tuple elements.
+constexpr int MAX_TUPLE_SIZE = 6;
+
+// The maximum number of struct fields.
+static const int MAX_STRUCT_SIZE = 6;
+
+// The maximum rtt depth.
+constexpr int MAX_RTT_DEPTH = 3;
+
+// The number of nontrivial heap types to generate.
+constexpr int MIN_HEAPTYPES = 4;
+constexpr int MAX_HEAPTYPES = 20;
+
+// some things require luck, try them a few times
+constexpr int TRIES = 10;
+
+// beyond a nesting limit, greatly decrease the chance to continue to nest
+constexpr int NESTING_LIMIT = 11;
+
+// the maximum size of a block
+constexpr int BLOCK_FACTOR = 5;
+
+// the memory that we use, a small portion so that we have a good chance of
+// looking at writes (we also look outside of this region with small
+// probability) this should be a power of 2
+constexpr Address USABLE_MEMORY = 16;
+
+// the number of runtime iterations (function calls, loop backbranches) we
+// allow before we stop execution with a trap, to prevent hangs. 0 means
+// no hang protection.
+constexpr int HANG_LIMIT = 10;
+
+//
+constexpr size_t VeryImportant = 4;
+constexpr size_t Important = 2;
+
+} // namespace wasm
+
+#endif // wasm_tools_fuzzing_parameters_h
diff --git a/src/tools/fuzzing/random.cpp b/src/tools/fuzzing/random.cpp
index 38a86924e..3d8297c15 100644
--- a/src/tools/fuzzing/random.cpp
+++ b/src/tools/fuzzing/random.cpp
@@ -20,7 +20,8 @@
namespace wasm {
-Random::Random(std::vector<char>&& bytes) : bytes(std::move(bytes)) {
+Random::Random(std::vector<char>&& bytes, FeatureSet features)
+ : bytes(std::move(bytes)), features(features) {
// Ensure there is *some* input to be read.
if (bytes.empty()) {
bytes.push_back(0);
diff --git a/src/tools/fuzzing/random.h b/src/tools/fuzzing/random.h
index 156f248ca..845aa2fa5 100644
--- a/src/tools/fuzzing/random.h
+++ b/src/tools/fuzzing/random.h
@@ -18,8 +18,11 @@
#define wasm_tools_fuzzing_random_h
#include <cstdint>
+#include <map>
#include <vector>
+#include "wasm-features.h"
+
namespace wasm {
class Random {
@@ -33,9 +36,13 @@ class Random {
// After we finish the input, we start going through it again, but xoring
// so it's not identical.
int xorFactor = 0;
+ // Features used for picking among FeatureOptions.
+ FeatureSet features;
public:
- Random(std::vector<char>&& bytes);
+ Random(std::vector<char>&& bytes, FeatureSet features);
+ Random(std::vector<char>&& bytes)
+ : Random(std::move(bytes), FeatureSet::All) {}
// Methods for getting random data.
int8_t get();
@@ -55,6 +62,87 @@ public:
uint32_t upToSquared(uint32_t x) { return upTo(upTo(x)); }
bool finished() { return finishedInput; }
+
+ // Pick from a vector-like container
+ template<typename T> const typename T::value_type& pick(const T& vec) {
+ assert(!vec.empty());
+ auto index = upTo(vec.size());
+ return vec[index];
+ }
+
+ // Pick from a fixed list
+ template<typename T, typename... Args> T pick(T first, Args... args) {
+ auto num = sizeof...(Args) + 1;
+ auto temp = upTo(num);
+ return pickGivenNum<T>(temp, first, args...);
+ }
+
+ template<typename T> T pickGivenNum(size_t num, T first) {
+ assert(num == 0);
+ return first;
+ }
+
+// Trick to avoid a bug in GCC 7.x.
+// Upstream bug report: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82800
+#define GCC_VERSION \
+ (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__)
+#if GCC_VERSION > 70000 && GCC_VERSION < 70300
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
+#endif
+
+ template<typename T, typename... Args>
+ T pickGivenNum(size_t num, T first, Args... args) {
+ if (num == 0) {
+ return first;
+ }
+ return pickGivenNum<T>(num - 1, args...);
+ }
+
+#if GCC_VERSION > 70000 && GCC_VERSION < 70300
+#pragma GCC diagnostic pop
+#endif
+
+ template<typename T> struct FeatureOptions {
+ template<typename... Ts>
+ FeatureOptions<T>& add(FeatureSet feature, T option, Ts... rest) {
+ options[feature].push_back(option);
+ return add(feature, rest...);
+ }
+
+ struct WeightedOption {
+ T option;
+ size_t weight;
+ };
+
+ template<typename... Ts>
+ FeatureOptions<T>&
+ add(FeatureSet feature, WeightedOption weightedOption, Ts... rest) {
+ for (size_t i = 0; i < weightedOption.weight; i++) {
+ options[feature].push_back(weightedOption.option);
+ }
+ return add(feature, rest...);
+ }
+
+ FeatureOptions<T>& add(FeatureSet feature) { return *this; }
+
+ std::map<FeatureSet, std::vector<T>> options;
+ };
+
+ template<typename T> std::vector<T> items(FeatureOptions<T>& picker) {
+ std::vector<T> matches;
+ for (const auto& item : picker.options) {
+ if (features.has(item.first)) {
+ matches.reserve(matches.size() + item.second.size());
+ matches.insert(matches.end(), item.second.begin(), item.second.end());
+ }
+ }
+ return matches;
+ }
+
+ template<typename T> const T pick(FeatureOptions<T>& picker) {
+ return pick(items(picker));
+ }
};
} // namespace wasm
diff --git a/src/tools/wasm-fuzz-types.cpp b/src/tools/wasm-fuzz-types.cpp
new file mode 100644
index 000000000..5df0c50ba
--- /dev/null
+++ b/src/tools/wasm-fuzz-types.cpp
@@ -0,0 +1,122 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <optional>
+#include <random>
+#include <string>
+
+#include "support/command-line.h"
+#include "tools/fuzzing/heap-types.h"
+#include "tools/fuzzing/random.h"
+
+namespace wasm {
+
+using RandEngine = std::mt19937_64;
+
+uint64_t getSeed() {
+ // Return a (truly) random 64-bit value.
+ std::random_device rand;
+ return std::uniform_int_distribution<uint64_t>{}(rand);
+}
+
+struct Fuzzer {
+ bool verbose;
+
+ void run(uint64_t seed) {
+ // TODO: Reset the global type state to avoid monotonically increasing
+ // memory use.
+ RandEngine getRand(seed);
+ std::cout << "Running with seed " << seed << "\n";
+
+ // 4kb of random bytes should be enough for anyone!
+ std::vector<char> bytes(4096);
+ for (size_t i = 0; i < bytes.size(); i += sizeof(uint64_t)) {
+ *(uint64_t*)(bytes.data() + i) = getRand();
+ }
+ 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);
+
+ // TODO: Do some sort of checking or manipulation on the types
+ if (verbose) {
+ std::cerr << "Built " << types.size() << " types:\n";
+ for (size_t i = 0; i < types.size(); ++i) {
+ std::cerr << i << ": " << types[i] << "\n";
+ }
+ }
+ }
+};
+
+} // namespace wasm
+
+int main(int argc, const char* argv[]) {
+ using namespace wasm;
+
+ Options options("wasm-fuzz-types",
+ "Fuzz type construction, canonicalization, and operations");
+
+ std::optional<uint64_t> seed;
+ options.add("--seed",
+ "",
+ "Run a single workload generated by the given seed",
+ Options::Arguments::One,
+ [&](Options*, const std::string& arg) {
+ seed = uint64_t(std::stoull(arg));
+ });
+
+ bool verbose = false;
+ options.add("--verbose",
+ "-v",
+ "Print extra information",
+ Options::Arguments::Zero,
+ [&](Options*, const std::string& arg) { verbose = true; });
+
+ TypeSystem system = TypeSystem::Nominal;
+ options.add(
+ "--nominal",
+ "",
+ "Use the nominal type system (default)",
+ Options::Arguments::Zero,
+ [&](Options*, const std::string& arg) { system = TypeSystem::Nominal; });
+ options.add("--structural",
+ "",
+ "Use the equirecursive type system",
+ Options::Arguments::Zero,
+ [&](Options*, const std::string& arg) {
+ system = TypeSystem::Equirecursive;
+ });
+
+ options.parse(argc, argv);
+
+ setTypeSystem(system);
+
+ Fuzzer fuzzer{verbose};
+ if (seed) {
+ // Run just a single workload with the given seed.
+ fuzzer.run(*seed);
+ } else {
+ // Continuously run workloads with new randomly generated seeds.
+ size_t i = 0;
+ RandEngine nextSeed(getSeed());
+ while (true) {
+ std::cout << "Iteration " << ++i << "\n";
+ fuzzer.run(nextSeed());
+ }
+ }
+ return 0;
+}
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 1f6c5a7de..2362a95aa 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -576,6 +576,13 @@ struct TypeBuilder {
void setHeapType(size_t i, Struct&& struct_);
void setHeapType(size_t i, Array array);
+ // This is an ugly hack around the fact that temp heap types initialized with
+ // BasicHeapTypes are not themselves considered basic, so `HeapType::isBasic`
+ // and `HeapType::getBasic` do not work as expected with them. Call these
+ // methods instead.
+ bool isBasic(size_t i);
+ HeapType::BasicHeapType getBasic(size_t i);
+
// Gets the temporary HeapType at index `i`. This HeapType should only be used
// to construct temporary Types using the methods below.
HeapType getTempHeapType(size_t i);
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 002b401b5..1df14848c 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -2313,6 +2313,16 @@ void TypeBuilder::setHeapType(size_t i, Array array) {
impl->entries[i].set(array);
}
+bool TypeBuilder::isBasic(size_t i) {
+ assert(i < size() && "index out of bounds");
+ return impl->entries[i].info->kind == HeapTypeInfo::BasicKind;
+}
+
+HeapType::BasicHeapType TypeBuilder::getBasic(size_t i) {
+ assert(isBasic(i));
+ return impl->entries[i].info->basic;
+}
+
HeapType TypeBuilder::getTempHeapType(size_t i) {
assert(i < size() && "index out of bounds");
return impl->entries[i].get();
@@ -3136,6 +3146,13 @@ std::vector<HeapType> buildNominal(TypeBuilder& builder) {
auto afterMove = std::chrono::steady_clock::now();
#endif
+#if TRACE_CANONICALIZATION
+ std::cerr << "After building:\n";
+ for (size_t i = 0; i < heapTypes.size(); ++i) {
+ std::cerr << i << ": " << heapTypes[i] << "\n";
+ }
+#endif // TRACE_CANONICALIZATION
+
validateNominalSubTyping(heapTypes);
#if TIME_CANONICALIZATION
diff --git a/test/lit/fuzz-types/nominal.test b/test/lit/fuzz-types/nominal.test
new file mode 100644
index 000000000..14dd80ac6
--- /dev/null
+++ b/test/lit/fuzz-types/nominal.test
@@ -0,0 +1,24 @@
+;; RUN: wasm-fuzz-types --nominal -v --seed=0
+
+;; CHECK: Running with seed 0
+;; CHECK-NEXT: Built 20 types:
+;; CHECK-NEXT: 0: (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32)))
+;; CHECK-NEXT: 1: (array (mut (ref null data)))
+;; CHECK-NEXT: 2: (func (result (ref null (func (result ...1 i32 (ref null (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32))))))) i32 (ref null (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32))))))
+;; CHECK-NEXT: 3: (func (result (ref null (func (result ...1 i32 (ref null (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32))))))) i32 (ref null (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32))))))
+;; CHECK-NEXT: 4: (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32)))
+;; CHECK-NEXT: 5: (func (result (ref null (func (result ...1 i32 (ref null (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32))))))) i32 (ref null (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32))))))
+;; CHECK-NEXT: 6: (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32) (rtt (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32)))) (mut (ref null i31)) (mut dataref)))
+;; CHECK-NEXT: 7: (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32)))
+;; CHECK-NEXT: 8: (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32)))
+;; CHECK-NEXT: 9: (func (result (ref null ...1) i32 (ref null (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32))))))
+;; CHECK-NEXT: 10: (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32)))
+;; CHECK-NEXT: 11: (array (mut (ref null data)))
+;; CHECK-NEXT: 12: (struct (field (ref ...1) (mut f32)))
+;; CHECK-NEXT: 13: (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32) (rtt (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32)))) (mut (ref null i31)) (mut dataref)))
+;; CHECK-NEXT: 14: (func (result (ref null (func (result ...1 i32 (ref null (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32))))))) i32 (ref null (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32))))))
+;; CHECK-NEXT: 15: (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32)))
+;; CHECK-NEXT: 16: (func (result (ref null (func (result ...1 i32 (ref null (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32))))))) i32 (ref null (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32))))))
+;; CHECK-NEXT: 17: (array (mut (ref null data)))
+;; CHECK-NEXT: 18: (array (mut (ref null data)))
+;; CHECK-NEXT: 19: (struct (field (ref (struct (field ...1 (mut f32)))) (mut f32)))
diff --git a/test/lit/fuzz-types/structural.test b/test/lit/fuzz-types/structural.test
new file mode 100644
index 000000000..efb605740
--- /dev/null
+++ b/test/lit/fuzz-types/structural.test
@@ -0,0 +1,47 @@
+;; RUN: wasm-fuzz-types --structural -v --seed=0
+
+;; CHECK: Running with seed 0
+;; CHECK-NEXT: Built 20 types:
+;; CHECK-NEXT: 0: (struct (field anyref (mut f32)))
+;; CHECK-NEXT: 1: (func (result i64))
+;; CHECK-NEXT: 2: (struct (field (rtt 0 ...1) (ref (func (result i64))) (mut (ref null (struct (field anyref (mut f32))))) (mut i8) i64 (mut (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq))))))))
+;; CHECK-NEXT: 3: (struct (field (rtt 0 ...1) (ref (func (result i64))) (mut (ref null (struct (field anyref (mut f32))))) (mut i8) i64 (mut (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq))))))))
+;; CHECK-NEXT: 4: (struct (field (rtt 0 ...1) (ref (func (result i64))) (mut (ref null (struct (field anyref (mut f32))))) (mut i8) i64 (mut (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq))))))))
+;; CHECK-NEXT: 5: (struct (field (rtt 0 ...1) (ref (func (result i64))) (mut (ref null (struct (field anyref (mut f32))))) (mut i8) i64 (mut (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq))))))))
+;; CHECK-NEXT: 6: (struct (field (rtt 0 ...1) (ref (func (result i64))) (mut (ref null (struct (field anyref (mut f32))))) (mut i8) i64 (mut (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq))))))))
+;; CHECK-NEXT: 7: (struct (field anyref (mut f32)))
+;; CHECK-NEXT: 8: (struct (field anyref (mut f32) f64 i8 v128 (mut i8)))
+;; CHECK-NEXT: 9: (struct (field (rtt 0 ...1) (ref (func (result i64))) (mut (ref null (struct (field anyref (mut f32))))) (mut i8) i64 (mut (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq))))))))
+;; CHECK-NEXT: 10: (struct (field anyref (mut f32) (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq))))) (ref (struct (field (rtt 0 ...1) (ref (func (result i64))) (mut (ref null (struct (field anyref (mut f32))))) (mut i8) i64 (mut (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq))))))))) (rtt 1 (struct (field anyref (mut f32) (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq)) i16))) (ref (struct (field (rtt 0 ...1) (ref (func (result i64))) (mut (ref null (struct (field anyref (mut f32))))) (mut i8) i64 (mut (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq))))))))) ...1)))))
+;; CHECK-NEXT: 11: (struct (field (rtt 0 ...1) (ref (func (result i64))) (mut (ref null (struct (field anyref (mut f32))))) (mut i8) i64 (mut (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq))))))))
+;; CHECK-NEXT: 12: (struct (field anyref (mut f32) (mut (rtt 2 eq))))
+;; CHECK-NEXT: 13: (struct (field (rtt 0 ...1) (ref (func (result i64))) (mut (ref null (struct (field anyref (mut f32))))) (mut i8) i64 (mut (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq))))))))
+;; CHECK-NEXT: 14: (struct (field anyref (mut f32) (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq)) i16))) (ref (struct (field (rtt 0 ...1) (ref (func (result i64))) (mut (ref null (struct (field anyref (mut f32))))) (mut i8) i64 (mut (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq))))))))) (rtt 1 ...1)))
+;; CHECK-NEXT: 15: (func (result i64))
+;; CHECK-NEXT: 16: (struct (field (rtt 0 ...1) (ref (func (result i64))) (mut (ref null (struct (field anyref (mut f32))))) (mut i8) i64 (mut (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq))))))))
+;; CHECK-NEXT: 17: (struct (field anyref (mut f32) (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq)) i16))) (ref (struct (field (rtt 0 ...1) (ref (func (result i64))) (mut (ref null (struct (field anyref (mut f32))))) (mut i8) i64 (mut (ref null (struct (field anyref (mut f32) (mut (rtt 2 eq))))))))) (rtt 1 ...1)))
+;; CHECK-NEXT: 18: (struct (field anyref (mut f32) (mut (rtt 2 eq)) i16))
+;; CHECK-NEXT: 19: (func (result i64))
+
+;; CHECK: Running with seed 0
+;; CHECK-NEXT: Built 20 types:
+;; CHECK-NEXT: 0: (struct (field (ref null (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...3) (ref (struct (field (mut (ref func)) (mut ...3)))) (mut (ref (func (param (rtt 0 ...7))))) (mut (rtt 2 (struct (field (mut (ref func)) (mut ...3))))) (rtt 2 ...3))))) i64 (mut (rtt (func (param (rtt 0 ...5))))) (rtt 1 (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...5) (ref ...3) (mut (ref (func (param (rtt 0 ...9))))) (mut (rtt 2 ...3)) (rtt 2 ...5)))))))) (mut (ref ...3))))) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 ...9))))) (rtt 1 ...5) (mut (ref ...7))))) ...3 (mut (ref (func (param (rtt 0 ...7))))) (mut (rtt 2 ...3)) (rtt 2 (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 ...9))))) (rtt 1 ...5) (mut (ref ...7))))))))))))))
+;; CHECK-NEXT: 1: (func (param (rtt 0 (struct (field (ref null (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...3) (ref (struct (field (mut (ref func)) (mut ...3)))) (mut (ref ...7)) (mut (rtt 2 (struct (field (mut (ref func)) (mut ...3))))) (rtt 2 ...3))))) i64 (mut (rtt ...5)) (rtt 1 (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...5) (ref ...3) (mut (ref ...9)) (mut (rtt 2 ...3)) (rtt 2 ...5)))))))) (mut (ref ...3))))) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt ...9)) (rtt 1 ...5) (mut (ref ...7))))) ...3 (mut (ref ...7)) (mut (rtt 2 ...3)) (rtt 2 (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt ...9)) (rtt 1 ...5) (mut (ref ...7)))))))))))))))))
+;; CHECK-NEXT: 2: (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref ...9)))))))) (rtt 1 ...5) (mut (ref (struct (field (ref null ...3) (ref ...7)))))))) (ref ...3) (mut (ref (func (param (rtt 0 (struct (field (ref null (struct (field (mut (ref func)) (mut ...7) i64 (mut (rtt ...5)) (rtt 1 ...9) (mut (ref ...3))))) (ref ...7)))))))) (mut (rtt 2 ...3)) (rtt 2 (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref ...9)))))))) (rtt 1 ...5) (mut (ref (struct (field (ref null ...3) (ref ...7))))))))))))))
+;; CHECK-NEXT: 3: (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref ...9)))))))) (rtt 1 ...5) (mut (ref (struct (field (ref null ...3) (ref ...7)))))))) (ref ...3) (mut (ref (func (param (rtt 0 (struct (field (ref null (struct (field (mut (ref func)) (mut ...7) i64 (mut (rtt ...5)) (rtt 1 ...9) (mut (ref ...3))))) (ref ...7)))))))) (mut (rtt 2 ...3)) (rtt 2 (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref ...9)))))))) (rtt 1 ...5) (mut (ref (struct (field (ref null ...3) (ref ...7))))))))))))))
+;; CHECK-NEXT: 4: (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref ...9)))))))) (rtt 1 ...5) (mut (ref (struct (field (ref null ...3) (ref ...7)))))))) (ref ...3) (mut (ref (func (param (rtt 0 (struct (field (ref null (struct (field (mut (ref func)) (mut ...7) i64 (mut (rtt ...5)) (rtt 1 ...9) (mut (ref ...3))))) (ref ...7)))))))) (mut (rtt 2 ...3)) (rtt 2 (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref ...9)))))))) (rtt 1 ...5) (mut (ref (struct (field (ref null ...3) (ref ...7))))))))))))))
+;; CHECK-NEXT: 5: (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref ...9)))))))) (rtt 1 ...5) (mut (ref (struct (field (ref null ...3) (ref ...7)))))))) (ref ...3) (mut (ref (func (param (rtt 0 (struct (field (ref null (struct (field (mut (ref func)) (mut ...7) i64 (mut (rtt ...5)) (rtt 1 ...9) (mut (ref ...3))))) (ref ...7)))))))) (mut (rtt 2 ...3)) (rtt 2 (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref ...9)))))))) (rtt 1 ...5) (mut (ref (struct (field (ref null ...3) (ref ...7))))))))))))))
+;; CHECK-NEXT: 6: (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...3) (ref (struct (field (mut (ref func)) (mut ...3)))) (mut (ref (func (param (rtt 0 (struct (field (ref null ...7) (ref (struct (field (mut (ref func)) (mut ...7))))))))))) (mut (rtt 2 (struct (field (mut (ref func)) (mut ...3))))) (rtt 2 ...3))))) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...9) ...3 (mut (ref ...7)) (mut (rtt 2 ...3)) (rtt 2 ...9))))))))))))))) (rtt 1 (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...5) (ref ...3) (mut (ref (func (param (rtt 0 (struct (field (ref null ...9) (ref ...7)))))))) (mut (rtt 2 ...3)) (rtt 2 ...5)))))))) (mut (ref (struct (field (ref null ...3) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...7) ...3 (mut (ref (func (param (rtt 0 ...7))))) (mut (rtt 2 ...3)) (rtt 2 ...7))))))))))))))
+;; CHECK-NEXT: 7: (struct (field (ref null (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...3) (ref (struct (field (mut (ref func)) (mut ...3)))) (mut (ref (func (param (rtt 0 ...7))))) (mut (rtt 2 (struct (field (mut (ref func)) (mut ...3))))) (rtt 2 ...3))))) i64 (mut (rtt (func (param (rtt 0 ...5))))) (rtt 1 (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...5) (ref ...3) (mut (ref (func (param (rtt 0 ...9))))) (mut (rtt 2 ...3)) (rtt 2 ...5)))))))) (mut (ref ...3))))) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 ...9))))) (rtt 1 ...5) (mut (ref ...7))))) ...3 (mut (ref (func (param (rtt 0 ...7))))) (mut (rtt 2 ...3)) (rtt 2 (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 ...9))))) (rtt 1 ...5) (mut (ref ...7))))))))))))))
+;; CHECK-NEXT: 8: (struct (field (ref null (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...3) (ref (struct (field (mut (ref func)) (mut ...3)))) (mut (ref (func (param (rtt 0 ...7))))) (mut (rtt 2 (struct (field (mut (ref func)) (mut ...3))))) (rtt 2 ...3))))) i64 (mut (rtt (func (param (rtt 0 ...5))))) (rtt 1 (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...5) (ref ...3) (mut (ref (func (param (rtt 0 ...9))))) (mut (rtt 2 ...3)) (rtt 2 ...5)))))))) (mut (ref ...3))))) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 ...9))))) (rtt 1 ...5) (mut (ref ...7))))) ...3 (mut (ref (func (param (rtt 0 ...7))))) (mut (rtt 2 ...3)) (rtt 2 (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 ...9))))) (rtt 1 ...5) (mut (ref ...7))))))))))))))
+;; CHECK-NEXT: 9: (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...3) (ref (struct (field (mut (ref func)) (mut ...3)))) (mut (ref (func (param (rtt 0 (struct (field (ref null ...7) (ref (struct (field (mut (ref func)) (mut ...7))))))))))) (mut (rtt 2 (struct (field (mut (ref func)) (mut ...3))))) (rtt 2 ...3))))) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...9) ...3 (mut (ref ...7)) (mut (rtt 2 ...3)) (rtt 2 ...9))))))))))))))) (rtt 1 (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...5) (ref ...3) (mut (ref (func (param (rtt 0 (struct (field (ref null ...9) (ref ...7)))))))) (mut (rtt 2 ...3)) (rtt 2 ...5)))))))) (mut (ref (struct (field (ref null ...3) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...7) ...3 (mut (ref (func (param (rtt 0 ...7))))) (mut (rtt 2 ...3)) (rtt 2 ...7))))))))))))))
+;; CHECK-NEXT: 10: (struct (field (ref (struct (field (mut (ref func)) (mut (ref ...3)) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref (struct (field (mut (ref func)) (mut (ref ...9)))))))))))) (rtt 1 (struct (field (mut (ref func)) (mut (ref ...5))))) (mut (ref (struct (field (ref null ...3) (ref (struct (field (mut (ref func)) (mut (ref ...7)))))))))))) (ref (struct (field (mut (ref func)) (mut (ref ...3))))) (mut (ref (func (param (rtt 0 (struct (field (ref null (struct (field (mut (ref func)) (mut (ref ...7)) i64 (mut (rtt ...5)) (rtt 1 (struct (field (mut (ref func)) (mut (ref ...9))))) (mut (ref ...3))))) (ref (struct (field (mut (ref func)) (mut (ref ...7)))))))))))) (mut (rtt 2 (struct (field (mut (ref func)) (mut (ref ...3)))))) (rtt 2 (struct (field (mut (ref func)) (mut (ref ...3)) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref (struct (field (mut (ref func)) (mut (ref ...9)))))))))))) (rtt 1 (struct (field (mut (ref func)) (mut (ref ...5))))) (mut (ref (struct (field (ref null ...3) (ref (struct (field (mut (ref func)) (mut (ref ...7))))))))))))))
+;; CHECK-NEXT: 11: (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref ...9)))))))) (rtt 1 ...5) (mut (ref (struct (field (ref null ...3) (ref ...7)))))))) (ref ...3) (mut (ref (func (param (rtt 0 (struct (field (ref null (struct (field (mut (ref func)) (mut ...7) i64 (mut (rtt ...5)) (rtt 1 ...9) (mut (ref ...3))))) (ref ...7)))))))) (mut (rtt 2 ...3)) (rtt 2 (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref ...9)))))))) (rtt 1 ...5) (mut (ref (struct (field (ref null ...3) (ref ...7))))))))))))))
+;; CHECK-NEXT: 12: (struct (field (ref null (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...3) (ref (struct (field (mut (ref func)) (mut ...3)))) (mut (ref (func (param (rtt 0 ...7))))) (mut (rtt 2 (struct (field (mut (ref func)) (mut ...3))))) (rtt 2 ...3))))) i64 (mut (rtt (func (param (rtt 0 ...5))))) (rtt 1 (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...5) (ref ...3) (mut (ref (func (param (rtt 0 ...9))))) (mut (rtt 2 ...3)) (rtt 2 ...5)))))))) (mut (ref ...3))))) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 ...9))))) (rtt 1 ...5) (mut (ref ...7))))) ...3 (mut (ref (func (param (rtt 0 ...7))))) (mut (rtt 2 ...3)) (rtt 2 (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 ...9))))) (rtt 1 ...5) (mut (ref ...7))))))))))))))
+;; CHECK-NEXT: 13: (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...3) (ref (struct (field (mut (ref func)) (mut ...3)))) (mut (ref (func (param (rtt 0 (struct (field (ref null ...7) (ref (struct (field (mut (ref func)) (mut ...7))))))))))) (mut (rtt 2 (struct (field (mut (ref func)) (mut ...3))))) (rtt 2 ...3))))) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...9) ...3 (mut (ref ...7)) (mut (rtt 2 ...3)) (rtt 2 ...9))))))))))))))) (rtt 1 (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...5) (ref ...3) (mut (ref (func (param (rtt 0 (struct (field (ref null ...9) (ref ...7)))))))) (mut (rtt 2 ...3)) (rtt 2 ...5)))))))) (mut (ref (struct (field (ref null ...3) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...7) ...3 (mut (ref (func (param (rtt 0 ...7))))) (mut (rtt 2 ...3)) (rtt 2 ...7))))))))))))))
+;; CHECK-NEXT: 14: (struct (field (ref (struct (field (mut (ref func)) (mut (ref ...3)) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref (struct (field (mut (ref func)) (mut (ref ...9)))))))))))) (rtt 1 (struct (field (mut (ref func)) (mut (ref ...5))))) (mut (ref (struct (field (ref null ...3) (ref (struct (field (mut (ref func)) (mut (ref ...7)))))))))))) (ref (struct (field (mut (ref func)) (mut (ref ...3))))) (mut (ref (func (param (rtt 0 (struct (field (ref null (struct (field (mut (ref func)) (mut (ref ...7)) i64 (mut (rtt ...5)) (rtt 1 (struct (field (mut (ref func)) (mut (ref ...9))))) (mut (ref ...3))))) (ref (struct (field (mut (ref func)) (mut (ref ...7)))))))))))) (mut (rtt 2 (struct (field (mut (ref func)) (mut (ref ...3)))))) (rtt 2 (struct (field (mut (ref func)) (mut (ref ...3)) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref (struct (field (mut (ref func)) (mut (ref ...9)))))))))))) (rtt 1 (struct (field (mut (ref func)) (mut (ref ...5))))) (mut (ref (struct (field (ref null ...3) (ref (struct (field (mut (ref func)) (mut (ref ...7))))))))))))))
+;; CHECK-NEXT: 15: (func (param (rtt 0 (struct (field (ref null (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...3) (ref (struct (field (mut (ref func)) (mut ...3)))) (mut (ref ...7)) (mut (rtt 2 (struct (field (mut (ref func)) (mut ...3))))) (rtt 2 ...3))))) i64 (mut (rtt ...5)) (rtt 1 (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...5) (ref ...3) (mut (ref ...9)) (mut (rtt 2 ...3)) (rtt 2 ...5)))))))) (mut (ref ...3))))) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt ...9)) (rtt 1 ...5) (mut (ref ...7))))) ...3 (mut (ref ...7)) (mut (rtt 2 ...3)) (rtt 2 (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt ...9)) (rtt 1 ...5) (mut (ref ...7)))))))))))))))))
+;; CHECK-NEXT: 16: (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref (struct (field (mut (ref func)) (mut ...9))))))))))) (rtt 1 (struct (field (mut (ref func)) (mut ...5)))) (mut (ref (struct (field (ref null ...3) (ref (struct (field (mut (ref func)) (mut ...7))))))))))) (ref (struct (field (mut (ref func)) (mut ...3)))) (mut (ref (func (param (rtt 0 (struct (field (ref null (struct (field (mut (ref func)) (mut ...7) i64 (mut (rtt ...5)) (rtt 1 (struct (field (mut (ref func)) (mut ...9)))) (mut (ref ...3))))) (ref (struct (field (mut (ref func)) (mut ...7))))))))))) (mut (rtt 2 (struct (field (mut (ref func)) (mut ...3))))) (rtt 2 (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref (struct (field (mut (ref func)) (mut ...9))))))))))) (rtt 1 (struct (field (mut (ref func)) (mut ...5)))) (mut (ref (struct (field (ref null ...3) (ref (struct (field (mut (ref func)) (mut ...7))))))))))))))) (mut (ref (struct (field (mut (ref func)) (mut (ref (struct (field ...3 (ref (struct (field (mut (ref func)) (mut ...3)))) (mut (ref (func (param (rtt 0 (struct (field (ref null ...7) ..!))))))) (mut ..!) ..!)))) i64 (mut ..!) ..! (mut ..!)))))))
+;; CHECK-NEXT: 17: (struct (field (ref (struct (field (mut (ref func)) (mut (ref (struct (field ...3 (ref (struct (field (mut (ref func)) (mut ...3)))) (mut (ref (func (param (rtt 0 (struct (field (ref null ...7) (ref (struct (field (mut (ref func)) (mut ...7))))))))))) (mut (rtt 2 (struct (field (mut (ref func)) (mut ...3))))) (rtt 2 ...3))))) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) (ref (struct (field (mut (ref func)) (mut (ref (struct (field ...9 ...3 (mut (ref ...7)) (mut (rtt 2 ...3)) (rtt 2 ...9))))))))))))))) (rtt 1 (struct (field (mut (ref func)) (mut (ref (struct (field ...5 (ref ...3) (mut (ref (func (param (rtt 0 (struct (field (ref null ...9) (ref ...7)))))))) (mut (rtt 2 ...3)) (rtt 2 ...5)))))))) (mut (ref (struct (field (ref null ...3) (ref (struct (field (mut (ref func)) (mut (ref (struct (field ...7 ...3 (mut (ref (func (param (rtt 0 ...7))))) (mut (rtt 2 ...3)) (rtt 2 ...7))))))))))))))) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 (struct (field (ref null ...5) ..!))))))) ..! (mut ..!)))) ..! (mut ..!) (mut ..!) ..!))))))) (mut ..!) (mut ..!) ..! ..!))
+;; CHECK-NEXT: 18: (struct (field (ref null (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...3) (ref (struct (field (mut (ref func)) (mut ...3)))) (mut (ref (func (param (rtt 0 ...7))))) (mut (rtt 2 (struct (field (mut (ref func)) (mut ...3))))) (rtt 2 ...3))))) i64 (mut (rtt (func (param (rtt 0 ...5))))) (rtt 1 (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...5) (ref ...3) (mut (ref (func (param (rtt 0 ...9))))) (mut (rtt 2 ...3)) (rtt 2 ...5)))))))) (mut (ref ...3))))) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 ...9))))) (rtt 1 ...5) (mut (ref ...7))))) ...3 (mut (ref (func (param (rtt 0 ...7))))) (mut (rtt 2 ...3)) (rtt 2 (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt (func (param (rtt 0 ...9))))) (rtt 1 ...5) (mut (ref ...7))))))))))))))
+;; CHECK-NEXT: 19: (func (param (rtt 0 (struct (field (ref null (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...3) (ref (struct (field (mut (ref func)) (mut ...3)))) (mut (ref ...7)) (mut (rtt 2 (struct (field (mut (ref func)) (mut ...3))))) (rtt 2 ...3))))) i64 (mut (rtt ...5)) (rtt 1 (struct (field (mut (ref func)) (mut (ref (struct (field (ref ...5) (ref ...3) (mut (ref ...9)) (mut (rtt 2 ...3)) (rtt 2 ...5)))))))) (mut (ref ...3))))) (ref (struct (field (mut (ref func)) (mut (ref (struct (field (ref (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt ...9)) (rtt 1 ...5) (mut (ref ...7))))) ...3 (mut (ref ...7)) (mut (rtt 2 ...3)) (rtt 2 (struct (field (mut (ref func)) (mut ...3) i64 (mut (rtt ...9)) (rtt 1 ...5) (mut (ref ...7)))))))))))))))))
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-08 17:17:11 +0000