diff options
-rw-r--r-- | src/tools/fuzzing/fuzzing.cpp | 2 | ||||
-rw-r--r-- | src/tools/fuzzing/heap-types.cpp | 237 | ||||
-rw-r--r-- | src/wasm/wasm-type.cpp | 10 | ||||
-rw-r--r-- | test/lit/fuzz-types/isorecursive.test | 20 | ||||
-rw-r--r-- | test/lit/fuzz-types/nominal.test | 24 | ||||
-rw-r--r-- | test/lit/isorecursive-good.wast | 38 | ||||
-rw-r--r-- | test/lit/recursive-types.wast | 19 |
7 files changed, 261 insertions, 89 deletions
diff --git a/src/tools/fuzzing/fuzzing.cpp b/src/tools/fuzzing/fuzzing.cpp index 98f9ea733..d91266d49 100644 --- a/src/tools/fuzzing/fuzzing.cpp +++ b/src/tools/fuzzing/fuzzing.cpp @@ -1967,7 +1967,7 @@ Expression* TranslateToFuzzReader::makeRefFuncConst(Type type) { } // TODO: randomize the order for (auto& func : wasm.functions) { - if (Type::isSubType(type, Type(func->type, NonNullable))) { + if (Type::isSubType(Type(func->type, NonNullable), type)) { return builder.makeRefFunc(func->name, func->type); } } diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp index 8b9d824d1..a356e8b5b 100644 --- a/src/tools/fuzzing/heap-types.cpp +++ b/src/tools/fuzzing/heap-types.cpp @@ -240,70 +240,115 @@ struct HeapTypeGeneratorImpl { Array generateArray() { return {generateField()}; } - template<typename Kind> std::optional<HeapType> pickKind() { - std::vector<Index> candidateIndices; + template<typename Kind> std::vector<HeapType> getKindCandidates() { + std::vector<HeapType> candidates; // 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])) { - candidateIndices.push_back(i); + candidates.push_back(builder[i]); } } - if (candidateIndices.size()) { - return builder[rand.pick(candidateIndices)]; + return candidates; + } + + template<typename Kind> std::optional<HeapType> pickKind() { + auto candidates = getKindCandidates<Kind>(); + if (candidates.size()) { + return rand.pick(candidates); } else { return std::nullopt; } } HeapType pickSubFunc() { - if (auto type = pickKind<SignatureKind>()) { - return *type; - } else if (rand.oneIn(2)) { - return HeapType::nofunc; - } else { - return HeapType::func; + auto choice = rand.upTo(8); + switch (choice) { + case 0: + return HeapType::func; + case 1: + return HeapType::nofunc; + default: + if (auto type = pickKind<SignatureKind>()) { + return *type; + } + return (choice % 2) ? HeapType::func : HeapType::nofunc; } } HeapType pickSubStruct() { - if (auto type = pickKind<StructKind>()) { - return *type; - } else if (rand.oneIn(2)) { - return HeapType::none; - } else { - return HeapType::struct_; + auto choice = rand.upTo(8); + switch (choice) { + case 0: + return HeapType::struct_; + case 1: + return HeapType::none; + default: + if (auto type = pickKind<StructKind>()) { + return *type; + } + return (choice % 2) ? HeapType::struct_ : HeapType::none; } } HeapType pickSubArray() { - if (auto type = pickKind<ArrayKind>()) { - return *type; - } else if (rand.oneIn(2)) { - return HeapType::none; - } else { - return HeapType::array; + auto choice = rand.upTo(8); + switch (choice) { + case 0: + return HeapType::array; + case 1: + return HeapType::none; + default: + if (auto type = pickKind<ArrayKind>()) { + return *type; + } + return (choice % 2) ? HeapType::array : HeapType::none; } } HeapType pickSubEq() { - switch (rand.upTo(3)) { + auto choice = rand.upTo(16); + switch (choice) { case 0: - return HeapType::i31; + return HeapType::eq; case 1: - return pickSubStruct(); + return HeapType::array; case 2: - return pickSubArray(); + return HeapType::struct_; + case 3: + return HeapType::none; + default: { + auto candidates = getKindCandidates<StructKind>(); + auto arrayCandidates = getKindCandidates<ArrayKind>(); + candidates.insert( + candidates.end(), arrayCandidates.begin(), arrayCandidates.end()); + if (candidates.size()) { + return rand.pick(candidates); + } + switch (choice >> 2) { + case 0: + return HeapType::eq; + case 1: + return HeapType::array; + case 2: + return HeapType::struct_; + case 3: + return HeapType::none; + default: + WASM_UNREACHABLE("unexpected index"); + } + } } - WASM_UNREACHABLE("unexpected index"); } HeapType pickSubAny() { - switch (rand.upTo(2)) { + switch (rand.upTo(8)) { case 0: - return HeapType::eq; + return HeapType::any; case 1: + return HeapType::none; + default: return pickSubEq(); } WASM_UNREACHABLE("unexpected index"); @@ -315,13 +360,26 @@ struct HeapTypeGeneratorImpl { // 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; + std::vector<HeapType> candidates; for (auto i : subtypeIndices[it->second]) { if (i < recGroupEnds[index]) { - candidateIndices.push_back(i); + candidates.push_back(builder[i]); + } + } + // Very rarely choose the relevant bottom type instead. We can't just use + // `type.getBottom()` because `type` may not have been initialized yet in + // the builder. + if (rand.oneIn(candidates.size() * 8)) { + auto* kind = &typeKinds[it->second]; + if (auto* basic = std::get_if<BasicKind>(kind)) { + return HeapType(*basic).getBottom(); + } else if (std::get_if<SignatureKind>(kind)) { + return HeapType::nofunc; + } else { + return HeapType::none; } } - return builder[rand.pick(candidateIndices)]; + return rand.pick(candidates); } else { // This is not a constructed type, so it must be a basic type. assert(type.isBasic()); @@ -352,10 +410,76 @@ struct HeapTypeGeneratorImpl { case HeapType::nofunc: return type; } - WASM_UNREACHABLE("unexpected kind"); + WASM_UNREACHABLE("unexpected type"); } } + HeapType pickSuperHeapType(HeapType type) { + std::vector<HeapType> candidates; + auto it = typeIndices.find(type); + if (it != typeIndices.end()) { + // This is a constructed type, so we know its supertypes. Collect the + // supertype chain as well as basic supertypes. We can't inspect `type` + // directly because it may not have been initialized yet in the builder. + for (std::optional<Index> curr = it->second; curr; + curr = supertypeIndices[*curr]) { + candidates.push_back(builder[*curr]); + } + auto* kind = &typeKinds[it->second]; + if (std::get_if<StructKind>(kind)) { + candidates.push_back(HeapType::struct_); + candidates.push_back(HeapType::eq); + candidates.push_back(HeapType::any); + return rand.pick(candidates); + } else if (std::get_if<ArrayKind>(kind)) { + candidates.push_back(HeapType::array); + candidates.push_back(HeapType::eq); + candidates.push_back(HeapType::any); + return rand.pick(candidates); + } else if (std::get_if<SignatureKind>(kind)) { + candidates.push_back(HeapType::func); + return rand.pick(candidates); + } else { + // A constructed basic type. Fall through to add all of the basic + // supertypes as well. + type = *std::get_if<BasicKind>(kind); + } + } + // This is not a constructed type, so it must be a basic type. + assert(type.isBasic()); + candidates.push_back(type); + switch (type.getBasic()) { + case HeapType::ext: + case HeapType::func: + case HeapType::any: + break; + case HeapType::eq: + candidates.push_back(HeapType::any); + break; + case HeapType::i31: + case HeapType::struct_: + case HeapType::array: + candidates.push_back(HeapType::eq); + candidates.push_back(HeapType::any); + break; + case HeapType::string: + case HeapType::stringview_wtf8: + case HeapType::stringview_wtf16: + case HeapType::stringview_iter: + candidates.push_back(HeapType::any); + break; + case HeapType::none: + return pickSubAny(); + case HeapType::nofunc: + return pickSubFunc(); + case HeapType::noext: + candidates.push_back(HeapType::ext); + break; + } + assert(!candidates.empty()); + return rand.pick(candidates); + } + // TODO: Make this part of the wasm-type.h API struct Ref { HeapType type; @@ -369,8 +493,22 @@ struct HeapTypeGeneratorImpl { return {pickSubHeapType(super.type), nullability}; } + Ref generateSuperRef(Ref sub) { + auto nullability = sub.nullability == Nullable ? Nullable + : rand.oneIn(2) ? Nullable + : NonNullable; + return {pickSuperHeapType(sub.type), nullability}; + } + Type generateSubtype(Type type) { - if (type.isRef()) { + if (type.isTuple()) { + std::vector<Type> types; + types.reserve(type.size()); + for (auto t : type) { + types.push_back(generateSubtype(t)); + } + return builder.getTempTupleType(types); + } else if (type.isRef()) { auto ref = generateSubRef({type.getHeapType(), type.getNullability()}); return builder.getTempRefType(ref.type, ref.nullability); } else if (type.isBasic()) { @@ -381,9 +519,28 @@ struct HeapTypeGeneratorImpl { } } + Type generateSupertype(Type type) { + if (type.isTuple()) { + std::vector<Type> types; + types.reserve(type.size()); + for (auto t : type) { + types.push_back(generateSupertype(t)); + } + return builder.getTempTupleType(types); + } else if (type.isRef()) { + auto ref = generateSuperRef({type.getHeapType(), type.getNullability()}); + return builder.getTempRefType(ref.type, ref.nullability); + } else if (type.isBasic()) { + // Non-reference basic types do not have supertypes. + return type; + } else { + WASM_UNREACHABLE("unexpected type kind"); + } + } + Signature generateSubSignature(Signature super) { - // TODO: Update this once we support nontrivial function subtyping. - return super; + return Signature(generateSupertype(super.params), + generateSubtype(super.results)); } Field generateSubField(Field super) { @@ -399,9 +556,6 @@ struct HeapTypeGeneratorImpl { } Struct generateSubStruct(const Struct& super) { - if (rand.oneIn(2)) { - return super; - } std::vector<Field> fields; // Depth subtyping for (auto field : super.fields) { @@ -416,9 +570,6 @@ struct HeapTypeGeneratorImpl { } Array generateSubArray(Array super) { - if (rand.oneIn(2)) { - return super; - } return {generateSubField(super.element)}; } diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp index d06bfcbe7..64fd07759 100644 --- a/src/wasm/wasm-type.cpp +++ b/src/wasm/wasm-type.cpp @@ -1728,10 +1728,7 @@ bool SubTyper::isSubType(const Field& a, const Field& b) { } bool SubTyper::isSubType(const Signature& a, const Signature& b) { - // TODO: Implement proper signature subtyping, covariant in results and - // contravariant in params, once V8 implements it. - // return isSubType(b.params, a.params) && isSubType(a.results, b.results); - return a == b; + return isSubType(b.params, a.params) && isSubType(a.results, b.results); } bool SubTyper::isSubType(const Struct& a, const Struct& b) { @@ -2906,11 +2903,6 @@ TypeBuilder::BuildResult TypeBuilder::build() { state.newInfos.emplace_back(std::move(info)); } -#if TRACE_CANONICALIZATION - std::cerr << "Before replacing basic heap types:\n"; - state.dump(); -#endif - // Eagerly replace references to built basic heap types so the more // complicated canonicalization algorithms don't need to consider them. canonicalizeBasicTypes(state); diff --git a/test/lit/fuzz-types/isorecursive.test b/test/lit/fuzz-types/isorecursive.test index f670104f5..4ba564193 100644 --- a/test/lit/fuzz-types/isorecursive.test +++ b/test/lit/fuzz-types/isorecursive.test @@ -1,7 +1,7 @@ ;; RUN: wasm-fuzz-types --hybrid -v --seed=1 | filecheck %s ;; CHECK: (type $0 (struct)) -;; CHECK-NEXT: (rec +;; CHECK-NEXT: (rec ;; CHECK-NEXT: (type $1 (struct)) ;; CHECK-NEXT: (type $2 (array i16)) ;; CHECK-NEXT: (type $3 (func)) @@ -13,20 +13,20 @@ ;; CHECK-NEXT: (type $7 (func (param f64) (result i64))) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (rec -;; CHECK-NEXT: (type $8 (struct_subtype $1)) -;; CHECK-NEXT: (type $9 (func_subtype (param (ref $5) i32 i64 f64 f64 (ref eq) v128) (result i64) $4)) +;; CHECK-NEXT: (type $8 (struct_subtype (field f64 (ref $2) f64 (mut (ref null $9))) $1)) +;; CHECK-NEXT: (type $9 (func_subtype (param (ref array) i32 i64 f64 f64 anyref v128) (result i64) $4)) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (rec -;; CHECK-NEXT: (type $10 (func_subtype (param (ref $5) i32 i64 f64 f64 (ref eq) v128) (result i64) $9)) +;; CHECK-NEXT: (type $10 (func_subtype (param (ref eq) i32 i64 f64 f64 anyref v128) (result i64) $9)) ;; CHECK-NEXT: (type $11 (array_subtype (mut funcref) $6)) -;; CHECK-NEXT: (type $12 (array f64)) +;; CHECK-NEXT: (type $12 (array nullref)) ;; CHECK-NEXT: (type $13 none) -;; CHECK-NEXT: (type $14 (array arrayref)) -;; CHECK-NEXT: (type $15 (array (mut i8))) +;; CHECK-NEXT: (type $14 (array (ref $6))) +;; CHECK-NEXT: (type $15 (array i32)) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (rec -;; CHECK-NEXT: (type $16 (array_subtype f64 $12)) -;; CHECK-NEXT: (type $17 (func (param (ref $5) (ref null $3) (ref null $0) (ref null $2) (ref $8) v128) (result v128))) +;; CHECK-NEXT: (type $16 (array_subtype (ref none) $12)) +;; CHECK-NEXT: (type $17 (func (param (ref null $9)) (result f32 structref))) ;; CHECK-NEXT: (type $18 none) ;; CHECK-NEXT: ) -;; CHECK-NEXT: (type $19 (func_subtype (param (ref $5) i32 i64 f64 f64 (ref eq) v128) (result i64) $9)) +;; CHECK-NEXT: (type $19 (func_subtype (param (ref any) i32 i64 f64 f64 anyref v128) (result i64) $9)) diff --git a/test/lit/fuzz-types/nominal.test b/test/lit/fuzz-types/nominal.test index c127105bb..27d6a969c 100644 --- a/test/lit/fuzz-types/nominal.test +++ b/test/lit/fuzz-types/nominal.test @@ -4,19 +4,19 @@ ;; CHECK-NEXT: (type $1 (func (param f64 v128))) ;; CHECK-NEXT: (type $2 (struct (field (mut (ref null $19)) f64 arrayref))) ;; CHECK-NEXT: (type $3 (struct_subtype (field (mut i16) (ref i31) f32 f32 f64) $0)) -;; CHECK-NEXT: (type $4 (struct (field (mut (ref null $11)) (mut i8)))) +;; CHECK-NEXT: (type $4 (struct)) ;; CHECK-NEXT: (type $5 none) -;; CHECK-NEXT: (type $6 (array (ref null $18))) +;; CHECK-NEXT: (type $6 (array (mut eqref))) ;; CHECK-NEXT: (type $7 (func_subtype (param f64 v128) $1)) -;; CHECK-NEXT: (type $8 (array (mut (ref null $19)))) -;; CHECK-NEXT: (type $9 (array (mut f64))) -;; CHECK-NEXT: (type $10 (struct_subtype (field (mut i16) i31ref f32 f32 f64) $0)) -;; CHECK-NEXT: (type $11 (func (param i32 f64) (result (ref null $8)))) +;; CHECK-NEXT: (type $8 (array anyref)) +;; CHECK-NEXT: (type $9 (array f32)) +;; CHECK-NEXT: (type $10 (struct_subtype (field (mut i16) (ref i31) f32 f32 f64) $0)) +;; CHECK-NEXT: (type $11 (func (result f64))) ;; CHECK-NEXT: (type $12 (func_subtype (param f64 v128) $1)) ;; CHECK-NEXT: (type $13 (func_subtype (param f64 v128) $12)) -;; CHECK-NEXT: (type $14 (func_subtype (param i32 f64) (result (ref null $8)) $11)) -;; CHECK-NEXT: (type $15 (func_subtype (param i32 f64) (result (ref null $8)) $14)) -;; CHECK-NEXT: (type $16 (func (result v128))) -;; CHECK-NEXT: (type $17 (array f32)) -;; CHECK-NEXT: (type $18 (array i64)) -;; CHECK-NEXT: (type $19 (struct_subtype (field (mut i16) (ref none) f32 f32 f64 (ref $2)) $0)) +;; CHECK-NEXT: (type $14 (func_subtype (result f64) $11)) +;; CHECK-NEXT: (type $15 (func_subtype (result f64) $14)) +;; CHECK-NEXT: (type $16 (func (param (ref struct)) (result structref))) +;; CHECK-NEXT: (type $17 (array (mut (ref $2)))) +;; CHECK-NEXT: (type $18 (array (ref $10))) +;; CHECK-NEXT: (type $19 (struct_subtype (field (mut i16) (ref i31) f32 f32 f64 (mut f32)) $0)) diff --git a/test/lit/isorecursive-good.wast b/test/lit/isorecursive-good.wast index 350aabcf9..c7c9569eb 100644 --- a/test/lit/isorecursive-good.wast +++ b/test/lit/isorecursive-good.wast @@ -5,11 +5,13 @@ ;; RUN: wasm-opt %s -all --nominal -S -o - | filecheck %s --check-prefix NOMINAL (module - - (rec ;; HYBRID: (rec ;; HYBRID-NEXT: (type $super-struct (struct (field i32))) + ;; NOMINAL: (type $super-array (array (ref $super-struct))) + + ;; NOMINAL: (type $sub-array (array_subtype (ref $sub-struct) $super-array)) + ;; NOMINAL: (type $super-struct (struct (field i32))) (type $super-struct (struct i32)) ;; HYBRID: (type $sub-struct (struct_subtype (field i32) (field i64) $super-struct)) @@ -20,13 +22,21 @@ (rec ;; HYBRID: (rec ;; HYBRID-NEXT: (type $super-array (array (ref $super-struct))) - ;; NOMINAL: (type $super-array (array (ref $super-struct))) (type $super-array (array (ref $super-struct))) ;; HYBRID: (type $sub-array (array_subtype (ref $sub-struct) $super-array)) - ;; NOMINAL: (type $sub-array (array_subtype (ref $sub-struct) $super-array)) (type $sub-array (array_subtype (ref $sub-struct) $super-array)) ) + (rec + ;; HYBRID: (rec + ;; HYBRID-NEXT: (type $super-func (func (param (ref $sub-array)) (result (ref $super-array)))) + ;; NOMINAL: (type $super-func (func (param (ref $sub-array)) (result (ref $super-array)))) + (type $super-func (func (param (ref $sub-array)) (result (ref $super-array)))) + ;; HYBRID: (type $sub-func (func_subtype (param (ref $super-array)) (result (ref $sub-array)) $super-func)) + ;; NOMINAL: (type $sub-func (func_subtype (param (ref $super-array)) (result (ref $sub-array)) $super-func)) + (type $sub-func (func_subtype (param (ref $super-array)) (result (ref $sub-array)) $super-func)) + ) + ;; HYBRID: (func $make-super-struct (type $none_=>_ref|$super-struct|) (result (ref $super-struct)) ;; HYBRID-NEXT: (call $make-sub-struct) ;; HYBRID-NEXT: ) @@ -66,4 +76,24 @@ (func $make-sub-array (result (ref $sub-array)) (unreachable) ) + + ;; HYBRID: (func $make-super-func (type $none_=>_ref|$super-func|) (result (ref $super-func)) + ;; HYBRID-NEXT: (call $make-sub-func) + ;; HYBRID-NEXT: ) + ;; NOMINAL: (func $make-super-func (type $none_=>_ref|$super-func|) (result (ref $super-func)) + ;; NOMINAL-NEXT: (call $make-sub-func) + ;; NOMINAL-NEXT: ) + (func $make-super-func (result (ref $super-func)) + (call $make-sub-func) + ) + + ;; HYBRID: (func $make-sub-func (type $none_=>_ref|$sub-func|) (result (ref $sub-func)) + ;; HYBRID-NEXT: (unreachable) + ;; HYBRID-NEXT: ) + ;; NOMINAL: (func $make-sub-func (type $none_=>_ref|$sub-func|) (result (ref $sub-func)) + ;; NOMINAL-NEXT: (unreachable) + ;; NOMINAL-NEXT: ) + (func $make-sub-func (result (ref $sub-func)) + (unreachable) + ) ) diff --git a/test/lit/recursive-types.wast b/test/lit/recursive-types.wast index 30fd13db9..883756f7a 100644 --- a/test/lit/recursive-types.wast +++ b/test/lit/recursive-types.wast @@ -8,16 +8,15 @@ (type (func (param (ref null 1)) (result (ref null 1)))) (type (func (param (ref null 0)) (result (ref null 1)))) (rec - (type (func (param (ref null 3)) (result (ref null 4)))) - (type (func (param (ref null 4)) (result (ref null 3)))) - ) - - ;; CHECK: (type $type$0 (func (param (ref null $type$0)) (result (ref null $type$0)))) + ;; CHECK: (type $type$0 (func (param (ref null $type$0)) (result (ref null $type$0)))) - ;; CHECK: (rec - ;; CHECK-NEXT: (type $type$2 (func (param (ref null $type$2)) (result (ref null $type$3)))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $f3 (func (param (ref null $type$2)) (result (ref null $f3)))) + (type $f3 (func (param (ref null 4)) (result (ref null 3)))) + (type (func_subtype (param (ref null 3)) (result (ref null 4)) $f3)) + ) - ;; CHECK: (type $type$3 (func (param (ref null $type$3)) (result (ref null $type$2)))) + ;; CHECK: (type $type$2 (func_subtype (param (ref null $f3)) (result (ref null $type$2)) $f3)) ;; CHECK: (type $type$1 (func (param (ref null $type$0)) (result (ref null $type$0)))) @@ -42,14 +41,14 @@ (unreachable) ) - ;; CHECK: (func $qux (type $type$2) (param $0 (ref null $type$2)) (result (ref null $type$3)) + ;; CHECK: (func $qux (type $f3) (param $0 (ref null $type$2)) (result (ref null $f3)) ;; CHECK-NEXT: (unreachable) ;; CHECK-NEXT: ) (func $qux (type 3) (unreachable) ) - ;; CHECK: (func $quux (type $type$3) (param $0 (ref null $type$3)) (result (ref null $type$2)) + ;; CHECK: (func $quux (type $type$2) (param $0 (ref null $f3)) (result (ref null $type$2)) ;; CHECK-NEXT: (unreachable) ;; CHECK-NEXT: ) (func $quux (type 4) |