| #include "ir/possible-contents.h" |
| #include "ir/subtypes.h" |
| #include "parser/wat-parser.h" |
| #include "wasm.h" |
| #include "gtest/gtest.h" |
| |
| using namespace wasm; |
| |
| // Asserts a == b, in any order. |
| template<typename T> void assertEqualSymmetric(const T& a, const T& b) { |
| EXPECT_EQ(a, b); |
| EXPECT_EQ(b, a); |
| EXPECT_PRED2([](const T& a, const T& b) { return !(a != b); }, a, b); |
| EXPECT_PRED2([](const T& a, const T& b) { return !(b != a); }, a, b); |
| } |
| |
| // Asserts a != b, in any order. |
| template<typename T> void assertNotEqualSymmetric(const T& a, const T& b) { |
| EXPECT_NE(a, b); |
| EXPECT_NE(b, a); |
| EXPECT_PRED2([](const T& a, const T& b) { return !(a == b); }, a, b); |
| EXPECT_PRED2([](const T& a, const T& b) { return !(b == a); }, a, b); |
| } |
| |
| // Asserts a combined with b (in any order) is equal to c. |
| template<typename T> |
| void assertCombination(const T& a, const T& b, const T& c) { |
| T temp1 = PossibleContents::combine(a, b); |
| assertEqualSymmetric(temp1, c); |
| // Also check the type, as nulls will compare equal even if their types |
| // differ. We want to make sure even the types are identical. |
| assertEqualSymmetric(temp1.getType(), c.getType()); |
| |
| T temp2 = PossibleContents::combine(b, a); |
| assertEqualSymmetric(temp2, c); |
| assertEqualSymmetric(temp2.getType(), c.getType()); |
| |
| // Verify the shorthand API works like the static one. |
| T temp3 = a; |
| temp3.combine(b); |
| assertEqualSymmetric(temp3, temp1); |
| |
| T temp4 = b; |
| temp4.combine(a); |
| assertEqualSymmetric(temp4, temp2); |
| } |
| |
| // Parse a module from text and return it. |
| static std::unique_ptr<Module> parse(std::string module) { |
| auto wasm = std::make_unique<Module>(); |
| wasm->features = FeatureSet::All; |
| auto parsed = WATParser::parseModule(*wasm, module); |
| if (auto* err = parsed.getErr()) { |
| Fatal() << err->msg << "\n"; |
| } |
| return wasm; |
| }; |
| |
| // We want to declare a bunch of globals that are used in various tests. Doing |
| // so in the global scope is risky, as their constructors use types, and the |
| // type system itself uses global constructors. Instead, we use a fixture for |
| // that. |
| class PossibleContentsTest : public testing::Test { |
| protected: |
| Type anyref = Type(HeapType::any, Nullable); |
| Type funcref = Type(HeapType::func, Nullable); |
| Type i31ref = Type(HeapType::i31, Nullable); |
| Type structref = Type(HeapType::struct_, Nullable); |
| |
| PossibleContents none = PossibleContents::none(); |
| |
| PossibleContents i32Zero = PossibleContents::literal(Literal(int32_t(0))); |
| PossibleContents i32One = PossibleContents::literal(Literal(int32_t(1))); |
| PossibleContents f64One = PossibleContents::literal(Literal(double(1))); |
| PossibleContents anyNull = |
| PossibleContents::literal(Literal::makeNull(HeapType::any)); |
| PossibleContents funcNull = |
| PossibleContents::literal(Literal::makeNull(HeapType::func)); |
| PossibleContents i31Null = |
| PossibleContents::literal(Literal::makeNull(HeapType::i31)); |
| |
| PossibleContents i32Global1 = |
| PossibleContents::global("i32Global1", Type::i32); |
| PossibleContents i32Global2 = |
| PossibleContents::global("i32Global2", Type::i32); |
| PossibleContents f64Global = PossibleContents::global("f64Global", Type::f64); |
| PossibleContents anyGlobal = PossibleContents::global("anyGlobal", anyref); |
| PossibleContents funcGlobal = PossibleContents::global("funcGlobal", funcref); |
| PossibleContents nonNullFuncGlobal = |
| PossibleContents::global("funcGlobal", Type(HeapType::func, NonNullable)); |
| |
| PossibleContents nonNullFunc = PossibleContents::literal( |
| Literal("func", Signature(Type::none, Type::none))); |
| |
| PossibleContents exactI32 = PossibleContents::exactType(Type::i32); |
| PossibleContents exactAnyref = PossibleContents::exactType(anyref); |
| PossibleContents exactFuncref = PossibleContents::exactType(funcref); |
| PossibleContents exactStructref = PossibleContents::exactType(structref); |
| PossibleContents exactI31ref = PossibleContents::exactType(i31ref); |
| PossibleContents exactNonNullAnyref = |
| PossibleContents::exactType(Type(HeapType::any, NonNullable)); |
| PossibleContents exactNonNullFuncref = |
| PossibleContents::exactType(Type(HeapType::func, NonNullable)); |
| PossibleContents exactNonNullI31ref = |
| PossibleContents::exactType(Type(HeapType::i31, NonNullable)); |
| |
| PossibleContents exactFuncSignatureType = PossibleContents::exactType( |
| Type(Signature(Type::none, Type::none), Nullable)); |
| PossibleContents exactNonNullFuncSignatureType = PossibleContents::exactType( |
| Type(Signature(Type::none, Type::none), NonNullable)); |
| |
| PossibleContents many = PossibleContents::many(); |
| |
| PossibleContents coneAnyref = PossibleContents::fullConeType(anyref); |
| PossibleContents coneFuncref = PossibleContents::fullConeType(funcref); |
| PossibleContents coneFuncref1 = PossibleContents::coneType(funcref, 1); |
| }; |
| |
| TEST_F(PossibleContentsTest, TestComparisons) { |
| assertEqualSymmetric(none, none); |
| assertNotEqualSymmetric(none, i32Zero); |
| assertNotEqualSymmetric(none, i32Global1); |
| assertNotEqualSymmetric(none, exactI32); |
| assertNotEqualSymmetric(none, many); |
| |
| assertEqualSymmetric(i32Zero, i32Zero); |
| assertNotEqualSymmetric(i32Zero, i32One); |
| assertNotEqualSymmetric(i32Zero, f64One); |
| assertNotEqualSymmetric(i32Zero, i32Global1); |
| assertNotEqualSymmetric(i32Zero, exactI32); |
| assertNotEqualSymmetric(i32Zero, many); |
| |
| assertEqualSymmetric(i32Global1, i32Global1); |
| assertNotEqualSymmetric(i32Global1, i32Global2); |
| assertNotEqualSymmetric(i32Global1, exactI32); |
| assertNotEqualSymmetric(i32Global1, many); |
| |
| assertEqualSymmetric(exactI32, exactI32); |
| assertNotEqualSymmetric(exactI32, exactAnyref); |
| assertNotEqualSymmetric(exactI32, many); |
| |
| assertEqualSymmetric(many, many); |
| |
| // Nulls |
| |
| assertNotEqualSymmetric(i32Zero, anyNull); |
| assertNotEqualSymmetric(anyNull, funcNull); |
| assertEqualSymmetric(anyNull, anyNull); |
| |
| assertEqualSymmetric(exactNonNullAnyref, exactNonNullAnyref); |
| assertNotEqualSymmetric(exactNonNullAnyref, exactAnyref); |
| } |
| |
| TEST_F(PossibleContentsTest, TestHash) { |
| // Hashes should be deterministic. |
| EXPECT_EQ(none.hash(), none.hash()); |
| EXPECT_EQ(many.hash(), many.hash()); |
| |
| // Hashes should be different. (In theory hash collisions could appear here, |
| // but if such simple things collide and the test fails then we should really |
| // rethink our hash functions!) |
| EXPECT_NE(none.hash(), many.hash()); |
| EXPECT_NE(none.hash(), i32Zero.hash()); |
| EXPECT_NE(none.hash(), i32One.hash()); |
| EXPECT_NE(none.hash(), anyGlobal.hash()); |
| EXPECT_NE(none.hash(), funcGlobal.hash()); |
| EXPECT_NE(none.hash(), exactAnyref.hash()); |
| EXPECT_NE(none.hash(), exactFuncSignatureType.hash()); |
| EXPECT_NE(none.hash(), coneAnyref.hash()); |
| EXPECT_NE(none.hash(), coneFuncref.hash()); |
| EXPECT_NE(none.hash(), coneFuncref1.hash()); |
| |
| EXPECT_NE(i32Zero.hash(), i32One.hash()); |
| EXPECT_NE(anyGlobal.hash(), funcGlobal.hash()); |
| EXPECT_NE(exactAnyref.hash(), exactFuncSignatureType.hash()); |
| EXPECT_NE(coneAnyref.hash(), coneFuncref.hash()); |
| EXPECT_NE(coneAnyref.hash(), coneFuncref1.hash()); |
| EXPECT_NE(coneFuncref.hash(), coneFuncref1.hash()); |
| } |
| |
| TEST_F(PossibleContentsTest, TestCombinations) { |
| // None with anything else becomes the other thing. |
| assertCombination(none, none, none); |
| assertCombination(none, i32Zero, i32Zero); |
| assertCombination(none, i32Global1, i32Global1); |
| assertCombination(none, exactI32, exactI32); |
| assertCombination(none, many, many); |
| |
| // i32(0) will become Many, unless the value or the type is identical. |
| assertCombination(i32Zero, i32Zero, i32Zero); |
| assertCombination(i32Zero, i32One, exactI32); |
| assertCombination(i32Zero, f64One, many); |
| assertCombination(i32Zero, i32Global1, exactI32); |
| assertCombination(i32Zero, f64Global, many); |
| assertCombination(i32Zero, exactI32, exactI32); |
| assertCombination(i32Zero, exactAnyref, many); |
| assertCombination(i32Zero, many, many); |
| |
| assertCombination(i32Global1, i32Global1, i32Global1); |
| assertCombination(i32Global1, i32Global2, exactI32); |
| assertCombination(i32Global1, f64Global, many); |
| assertCombination(i32Global1, exactI32, exactI32); |
| assertCombination(i32Global1, exactAnyref, many); |
| assertCombination(i32Global1, many, many); |
| |
| assertCombination(exactI32, exactI32, exactI32); |
| assertCombination(exactI32, exactAnyref, many); |
| assertCombination(exactI32, many, many); |
| |
| assertCombination(many, many, many); |
| |
| // Exact references: An exact reference only stays exact when combined with |
| // the same heap type (nullability may be added, but nothing else). Otherwise |
| // we go to a cone type or to many. |
| assertCombination(exactFuncref, exactAnyref, many); |
| assertCombination(exactFuncref, anyGlobal, many); |
| assertCombination(exactFuncref, nonNullFunc, coneFuncref1); |
| assertCombination(exactFuncref, exactFuncref, exactFuncref); |
| assertCombination(exactFuncref, exactNonNullFuncref, exactFuncref); |
| |
| // Nulls. |
| |
| assertCombination(anyNull, i32Zero, many); |
| assertCombination(anyNull, anyNull, anyNull); |
| assertCombination(anyNull, exactAnyref, exactAnyref); |
| |
| // Two nulls go to the lub. |
| assertCombination(anyNull, i31Null, anyNull); |
| |
| // Incompatible nulls go to Many. |
| assertCombination(anyNull, funcNull, many); |
| |
| assertCombination(exactNonNullAnyref, exactNonNullAnyref, exactNonNullAnyref); |
| |
| // If one is a null and the other is not, it makes the one that is not a |
| // null be a nullable type - but keeps the heap type of the other (since the |
| // type of the null does not matter, all nulls compare equal). |
| assertCombination(anyNull, exactNonNullAnyref, exactAnyref); |
| assertCombination(anyNull, exactNonNullI31ref, exactI31ref); |
| |
| // Funcrefs |
| |
| // A function reference + a null becomes an exact type (of that sig), plus |
| // nullability. |
| assertCombination(nonNullFunc, funcNull, exactFuncSignatureType); |
| assertCombination(exactFuncSignatureType, funcNull, exactFuncSignatureType); |
| assertCombination( |
| exactNonNullFuncSignatureType, funcNull, exactFuncSignatureType); |
| assertCombination( |
| nonNullFunc, exactFuncSignatureType, exactFuncSignatureType); |
| assertCombination( |
| nonNullFunc, exactNonNullFuncSignatureType, exactNonNullFuncSignatureType); |
| assertCombination(nonNullFunc, exactI32, many); |
| |
| // Globals vs nulls. The result is either the global or a null, so all we can |
| // say is that it is something of the global's type, or a null: a cone. |
| |
| assertCombination(anyGlobal, anyNull, coneAnyref); |
| assertCombination(anyGlobal, i31Null, coneAnyref); |
| } |
| |
| static PassOptions options; |
| |
| TEST_F(PossibleContentsTest, TestOracleMinimal) { |
| // A minimal test of the public API of PossibleTypesOracle. See the lit test |
| // for coverage of all the internals (using lit makes the result more |
| // fuzzable). |
| auto wasm = parse(R"( |
| (module |
| (global $null (ref null any) (ref.null any)) |
| (global $something i32 (i32.const 42)) |
| ) |
| )"); |
| ContentOracle oracle(*wasm, options); |
| |
| // This will be a null constant. |
| EXPECT_TRUE(oracle.getContents(GlobalLocation{"null"}).isNull()); |
| |
| // This will be 42. |
| EXPECT_EQ(oracle.getContents(GlobalLocation{"something"}).getLiteral(), |
| Literal(int32_t(42))); |
| } |
| |
| // Asserts a and b have an intersection (or do not), and checks both orderings. |
| void assertHaveIntersection(PossibleContents a, PossibleContents b) { |
| EXPECT_TRUE(PossibleContents::haveIntersection(a, b)); |
| EXPECT_TRUE(PossibleContents::haveIntersection(b, a)); |
| #if BINARYEN_TEST_DEBUG |
| if (!PossibleContents::haveIntersection(a, b) || |
| !PossibleContents::haveIntersection(b, a)) { |
| std::cout << "\nFailure: no intersection:\n" << a << '\n' << b << '\n'; |
| abort(); |
| } |
| #endif |
| } |
| void assertLackIntersection(PossibleContents a, PossibleContents b) { |
| EXPECT_FALSE(PossibleContents::haveIntersection(a, b)); |
| EXPECT_FALSE(PossibleContents::haveIntersection(b, a)); |
| } |
| |
| TEST_F(PossibleContentsTest, TestIntersection) { |
| // None has no contents, so nothing to intersect. |
| assertLackIntersection(none, none); |
| assertLackIntersection(none, i32Zero); |
| assertLackIntersection(none, many); |
| |
| // Many intersects with anything (but none). |
| assertHaveIntersection(many, many); |
| assertHaveIntersection(many, i32Zero); |
| |
| // Different exact types cannot intersect. |
| assertLackIntersection(exactI32, exactAnyref); |
| assertLackIntersection(i32Zero, exactAnyref); |
| |
| // But nullable ones can - the null can be the intersection, if they are not |
| // in separate hierarchies. |
| assertHaveIntersection(exactFuncSignatureType, funcNull); |
| |
| assertLackIntersection(exactFuncSignatureType, exactAnyref); |
| assertLackIntersection(anyNull, funcNull); |
| |
| // Identical types might. |
| assertHaveIntersection(exactI32, exactI32); |
| assertHaveIntersection(i32Zero, i32Zero); |
| assertHaveIntersection(exactFuncSignatureType, exactFuncSignatureType); |
| assertLackIntersection(i32Zero, i32One); |
| |
| // Exact types only differing by nullability can intersect (not on the null, |
| // but on something else). |
| assertHaveIntersection(exactAnyref, exactNonNullAnyref); |
| |
| // Due to subtyping, an intersection might exist. |
| assertHaveIntersection(funcGlobal, funcGlobal); |
| assertHaveIntersection(funcGlobal, exactFuncSignatureType); |
| assertHaveIntersection(nonNullFuncGlobal, exactFuncSignatureType); |
| assertHaveIntersection(funcGlobal, exactNonNullFuncSignatureType); |
| assertHaveIntersection(nonNullFuncGlobal, exactNonNullFuncSignatureType); |
| |
| // Separate hierarchies. |
| assertLackIntersection(funcGlobal, anyGlobal); |
| } |
| |
| TEST_F(PossibleContentsTest, TestIntersectWithCombinations) { |
| // Whenever we combine C = A + B, both A and B must intersect with C. This |
| // helper function gets a set of things and checks that property on them. It |
| // returns the set of all contents it ever observed (see below for how we use |
| // that). |
| auto doTest = [](std::unordered_set<PossibleContents> set) { |
| std::vector<PossibleContents> vec(set.begin(), set.end()); |
| |
| // Find the maximum depths for the normalized cone tests later down. |
| std::unordered_set<HeapType> heapTypes; |
| for (auto& contents : set) { |
| auto type = contents.getType(); |
| if (type.isRef()) { |
| auto heapType = type.getHeapType(); |
| if (!heapType.isBasic()) { |
| heapTypes.insert(heapType); |
| } |
| } |
| } |
| std::vector<HeapType> heapTypesVec(heapTypes.begin(), heapTypes.end()); |
| SubTypes subTypes(heapTypesVec); |
| auto maxDepths = subTypes.getMaxDepths(); |
| |
| // Go over all permutations up to a certain size (this quickly becomes |
| // extremely slow, obviously, so keep this low). |
| size_t max = 3; |
| |
| auto n = set.size(); |
| |
| // |indexes| contains the indexes of the items in vec for the current |
| // permutation. |
| std::vector<size_t> indexes(max); |
| std::fill(indexes.begin(), indexes.end(), 0); |
| while (1) { |
| // Test the current permutation: Combine all the relevant things, and then |
| // check they all have an intersection. |
| PossibleContents combination; |
| for (auto index : indexes) { |
| combination.combine(vec[index]); |
| } |
| // Note the combination in the set. |
| set.insert(combination); |
| #if BINARYEN_TEST_DEBUG |
| for (auto index : indexes) { |
| std::cout << index << ' '; |
| combination.combine(vec[index]); |
| } |
| std::cout << '\n'; |
| #endif |
| for (auto index : indexes) { |
| auto item = vec[index]; |
| if (item.isNone()) { |
| assertLackIntersection(combination, item); |
| continue; |
| } |
| #if BINARYEN_TEST_DEBUG |
| if (!PossibleContents::haveIntersection(combination, item)) { |
| std::cout << "\nFailure: no expected intersection. Indexes:\n"; |
| for (auto index : indexes) { |
| std::cout << index << "\n "; |
| vec[index].dump(std::cout); |
| std::cout << '\n'; |
| } |
| std::cout << "combo:\n"; |
| combination.dump(std::cout); |
| std::cout << "\ncompared item (index " << index << "):\n"; |
| item.dump(std::cout); |
| std::cout << '\n'; |
| abort(); |
| } |
| #endif |
| assertHaveIntersection(combination, item); |
| |
| auto type = combination.getType(); |
| if (type.isRef()) { |
| // If we normalize the combination's depth, the item must still have |
| // an intersection. That is, normalization must not have a bug that |
| // results in cones that are too shallow. |
| auto normalizedDepth = maxDepths[type.getHeapType()]; |
| auto normalizedCone = |
| PossibleContents::coneType(type, normalizedDepth); |
| assertHaveIntersection(normalizedCone, item); |
| } |
| |
| // Test intersect() method, which is supported with a full cone type. |
| // In that case we can test that the intersection of A with A + B is |
| // simply A. |
| if (combination.isFullConeType()) { |
| auto intersection = item; |
| intersection.intersect(combination); |
| EXPECT_EQ(intersection, item); |
| #if BINARYEN_TEST_DEBUG |
| if (intersection != item) { |
| std::cout << "\nFailure: wrong intersection.\n"; |
| std::cout << "item: " << item << '\n'; |
| std::cout << "combination: " << combination << '\n'; |
| std::cout << "intersection: " << intersection << '\n'; |
| abort(); |
| } |
| #endif |
| |
| // The intersection is contained in each of the things we intersected |
| // (but we can only compare to the full cone, as the API is restricted |
| // to that). |
| EXPECT_TRUE( |
| PossibleContents::isSubContents(intersection, combination)); |
| } |
| } |
| |
| // Move to the next permutation. |
| size_t i = 0; |
| while (1) { |
| indexes[i]++; |
| if (indexes[i] == n) { |
| // Overflow. |
| indexes[i] = 0; |
| i++; |
| if (i == max) { |
| // All done. |
| return set; |
| } |
| } else { |
| break; |
| } |
| } |
| } |
| |
| WASM_UNREACHABLE("loop above returns manually"); |
| }; |
| |
| // Start from an initial set of the hardcoded contents we have in our test |
| // fixture. |
| std::unordered_set<PossibleContents> initial = {none, |
| f64One, |
| anyNull, |
| funcNull, |
| i31Null, |
| i32Global1, |
| i32Global2, |
| f64Global, |
| anyGlobal, |
| funcGlobal, |
| nonNullFuncGlobal, |
| nonNullFunc, |
| exactI32, |
| exactAnyref, |
| exactFuncref, |
| exactStructref, |
| exactI31ref, |
| exactNonNullAnyref, |
| exactNonNullFuncref, |
| exactNonNullI31ref, |
| exactFuncSignatureType, |
| exactNonNullFuncSignatureType, |
| many, |
| coneAnyref, |
| coneFuncref, |
| coneFuncref1}; |
| |
| // Add some additional interesting types. |
| auto structType = |
| Type(HeapType(Struct({Field(Type::i32, Immutable)})), NonNullable); |
| initial.insert(PossibleContents::coneType(structType, 0)); |
| auto arrayType = |
| Type(HeapType(Array(Field(Type::i32, Immutable))), NonNullable); |
| initial.insert(PossibleContents::coneType(arrayType, 0)); |
| |
| // After testing on the initial contents, also test using anything new that |
| // showed up while combining them. |
| auto subsequent = doTest(initial); |
| while (subsequent.size() > initial.size()) { |
| initial = subsequent; |
| subsequent = doTest(subsequent); |
| } |
| } |
| |
| void assertIntersection(PossibleContents a, |
| PossibleContents b, |
| PossibleContents result) { |
| auto intersection = a; |
| intersection.intersect(b); |
| EXPECT_EQ(intersection, result); |
| EXPECT_EQ(PossibleContents::haveIntersection(a, b), !result.isNone()); |
| } |
| |
| TEST_F(PossibleContentsTest, TestStructCones) { |
| /* |
| A E |
| / \ |
| B C |
| \ |
| D |
| */ |
| TypeBuilder builder(5); |
| builder.createRecGroup(0, 5); |
| builder[0].setOpen() = Struct(FieldList{}); |
| builder[1].setOpen().subTypeOf(builder[0]) = Struct(FieldList{}); |
| builder[2].setOpen().subTypeOf(builder[0]) = Struct(FieldList{}); |
| builder[3].setOpen().subTypeOf(builder[2]) = Struct(FieldList{}); |
| builder[4].setOpen() = Struct(FieldList{}); |
| auto result = builder.build(); |
| ASSERT_TRUE(result); |
| auto types = *result; |
| auto A = types[0]; |
| auto B = types[1]; |
| auto C = types[2]; |
| auto D = types[3]; |
| auto E = types[4]; |
| ASSERT_FALSE(A.getDeclaredSuperType()); |
| ASSERT_EQ(B.getDeclaredSuperType(), A); |
| ASSERT_EQ(C.getDeclaredSuperType(), A); |
| ASSERT_EQ(D.getDeclaredSuperType(), C); |
| |
| auto nullA = Type(A, Nullable); |
| auto nullB = Type(B, Nullable); |
| auto nullC = Type(C, Nullable); |
| auto nullD = Type(D, Nullable); |
| auto nullE = Type(E, Nullable); |
| |
| auto exactA = PossibleContents::exactType(nullA); |
| auto exactB = PossibleContents::exactType(nullB); |
| auto exactC = PossibleContents::exactType(nullC); |
| auto exactD = PossibleContents::exactType(nullD); |
| auto exactE = PossibleContents::exactType(nullE); |
| |
| auto nnA = Type(A, NonNullable); |
| auto nnB = Type(B, NonNullable); |
| auto nnC = Type(C, NonNullable); |
| auto nnD = Type(D, NonNullable); |
| auto nnE = Type(E, NonNullable); |
| |
| auto nnExactA = PossibleContents::exactType(nnA); |
| auto nnExactB = PossibleContents::exactType(nnB); |
| auto nnExactC = PossibleContents::exactType(nnC); |
| auto nnExactD = PossibleContents::exactType(nnD); |
| auto nnExactE = PossibleContents::exactType(nnE); |
| |
| assertCombination(exactA, exactA, exactA); |
| assertCombination(exactA, exactA, PossibleContents::coneType(nullA, 0)); |
| assertCombination(exactA, exactB, PossibleContents::coneType(nullA, 1)); |
| assertCombination(exactA, exactC, PossibleContents::coneType(nullA, 1)); |
| assertCombination(exactA, exactD, PossibleContents::coneType(nullA, 2)); |
| assertCombination(exactA, exactE, PossibleContents::coneType(structref, 1)); |
| assertCombination( |
| exactA, exactStructref, PossibleContents::coneType(structref, 1)); |
| |
| assertCombination(exactB, exactB, exactB); |
| assertCombination(exactB, exactC, PossibleContents::coneType(nullA, 1)); |
| assertCombination(exactB, exactD, PossibleContents::coneType(nullA, 2)); |
| assertCombination(exactB, exactE, PossibleContents::coneType(structref, 2)); |
| assertCombination( |
| exactB, exactStructref, PossibleContents::coneType(structref, 2)); |
| |
| assertCombination(exactC, exactC, exactC); |
| assertCombination(exactC, exactD, PossibleContents::coneType(nullC, 1)); |
| assertCombination(exactC, exactE, PossibleContents::coneType(structref, 2)); |
| assertCombination( |
| exactC, exactStructref, PossibleContents::coneType(structref, 2)); |
| |
| assertCombination(exactD, exactD, exactD); |
| assertCombination(exactD, exactE, PossibleContents::coneType(structref, 3)); |
| assertCombination( |
| exactD, exactStructref, PossibleContents::coneType(structref, 3)); |
| |
| assertCombination(exactE, exactE, exactE); |
| assertCombination( |
| exactE, exactStructref, PossibleContents::coneType(structref, 1)); |
| |
| assertCombination(exactStructref, exactStructref, exactStructref); |
| |
| assertCombination( |
| exactStructref, exactAnyref, PossibleContents::coneType(anyref, 2)); |
| |
| // Combinations of cones. |
| assertCombination(PossibleContents::coneType(nullA, 5), |
| PossibleContents::coneType(nullA, 7), |
| PossibleContents::coneType(nullA, 7)); |
| |
| // Increment the cone of D as we go here, until it matters. |
| assertCombination(PossibleContents::coneType(nullA, 5), |
| PossibleContents::coneType(nullD, 2), |
| PossibleContents::coneType(nullA, 5)); |
| assertCombination(PossibleContents::coneType(nullA, 5), |
| PossibleContents::coneType(nullD, 3), |
| PossibleContents::coneType(nullA, 5)); |
| assertCombination(PossibleContents::coneType(nullA, 5), |
| PossibleContents::coneType(nullD, 4), |
| PossibleContents::coneType(nullA, 6)); |
| |
| assertCombination(PossibleContents::coneType(nullA, 5), |
| PossibleContents::coneType(nullE, 7), |
| PossibleContents::coneType(structref, 8)); |
| |
| assertCombination(PossibleContents::coneType(nullB, 4), |
| PossibleContents::coneType(structref, 1), |
| PossibleContents::coneType(structref, 6)); |
| |
| // Combinations of cones and exact types. |
| assertCombination(exactA, |
| PossibleContents::coneType(nullA, 3), |
| PossibleContents::coneType(nullA, 3)); |
| assertCombination(exactA, |
| PossibleContents::coneType(nullD, 3), |
| PossibleContents::coneType(nullA, 5)); |
| assertCombination(exactD, |
| PossibleContents::coneType(nullA, 3), |
| PossibleContents::coneType(nullA, 3)); |
| assertCombination(exactA, |
| PossibleContents::coneType(nullE, 2), |
| PossibleContents::coneType(structref, 3)); |
| |
| assertCombination(exactA, |
| PossibleContents::coneType(structref, 1), |
| PossibleContents::coneType(structref, 1)); |
| assertCombination(exactA, |
| PossibleContents::coneType(structref, 2), |
| PossibleContents::coneType(structref, 2)); |
| |
| assertCombination(exactStructref, |
| PossibleContents::coneType(nullB, 3), |
| PossibleContents::coneType(structref, 5)); |
| |
| // Full cones. |
| assertCombination(PossibleContents::fullConeType(nullA), |
| exactA, |
| PossibleContents::fullConeType(nullA)); |
| assertCombination(PossibleContents::fullConeType(nullA), |
| PossibleContents::coneType(nullA, 2), |
| PossibleContents::fullConeType(nullA)); |
| |
| // All full cones with A remain full cones, except for E. |
| assertCombination(PossibleContents::fullConeType(nullA), |
| PossibleContents::fullConeType(nullA), |
| PossibleContents::fullConeType(nullA)); |
| assertCombination(PossibleContents::fullConeType(nullA), |
| PossibleContents::fullConeType(nullB), |
| PossibleContents::fullConeType(nullA)); |
| assertCombination(PossibleContents::fullConeType(nullA), |
| PossibleContents::fullConeType(nullC), |
| PossibleContents::fullConeType(nullA)); |
| assertCombination(PossibleContents::fullConeType(nullA), |
| PossibleContents::fullConeType(nullD), |
| PossibleContents::fullConeType(nullA)); |
| assertCombination(PossibleContents::fullConeType(nullA), |
| PossibleContents::fullConeType(nullE), |
| PossibleContents::fullConeType(structref)); |
| |
| // Intersections. Test with non-nullable types to avoid the null being a |
| // possible intersection. |
| assertHaveIntersection(nnExactA, nnExactA); |
| assertLackIntersection(nnExactA, nnExactB); |
| assertLackIntersection(nnExactA, nnExactC); |
| assertLackIntersection(nnExactA, nnExactD); |
| assertLackIntersection(nnExactA, nnExactE); |
| |
| assertHaveIntersection(PossibleContents::coneType(nnA, 1), nnExactB); |
| assertHaveIntersection(PossibleContents::coneType(nnA, 1), nnExactC); |
| assertHaveIntersection(PossibleContents::coneType(nnA, 2), nnExactD); |
| |
| assertLackIntersection(PossibleContents::coneType(nnA, 1), nnExactD); |
| assertLackIntersection(PossibleContents::coneType(nnA, 1), nnExactE); |
| assertLackIntersection(PossibleContents::coneType(nnA, 2), nnExactE); |
| |
| assertHaveIntersection(PossibleContents::coneType(nnA, 1), |
| PossibleContents::coneType(nnC, 100)); |
| assertLackIntersection(PossibleContents::coneType(nnA, 1), |
| PossibleContents::coneType(nnD, 100)); |
| |
| // Neither is a subtype of the other, but nulls are possible, so a null can be |
| // the intersection. |
| assertHaveIntersection(PossibleContents::fullConeType(nullA), |
| PossibleContents::fullConeType(nullE)); |
| |
| // Without null on one side, we cannot intersect. |
| assertLackIntersection(PossibleContents::fullConeType(nnA), |
| PossibleContents::fullConeType(nullE)); |
| |
| // Computing intersections is supported with a full cone type. |
| assertIntersection(none, PossibleContents::fullConeType(nnA), none); |
| assertIntersection(many, |
| PossibleContents::fullConeType(nnA), |
| PossibleContents::fullConeType(nnA)); |
| assertIntersection(many, |
| PossibleContents::fullConeType(nullA), |
| PossibleContents::fullConeType(nullA)); |
| |
| assertIntersection(exactA, PossibleContents::fullConeType(nullA), exactA); |
| assertIntersection(nnExactA, PossibleContents::fullConeType(nullA), nnExactA); |
| assertIntersection(exactA, PossibleContents::fullConeType(nnA), nnExactA); |
| |
| assertIntersection(exactB, PossibleContents::fullConeType(nullA), exactB); |
| assertIntersection(nnExactB, PossibleContents::fullConeType(nullA), nnExactB); |
| assertIntersection(exactB, PossibleContents::fullConeType(nnA), nnExactB); |
| |
| auto literalNullA = PossibleContents::literal(Literal::makeNull(A)); |
| |
| assertIntersection( |
| literalNullA, PossibleContents::fullConeType(nullA), literalNullA); |
| assertIntersection(literalNullA, PossibleContents::fullConeType(nnA), none); |
| |
| assertIntersection( |
| literalNullA, PossibleContents::fullConeType(nullB), literalNullA); |
| assertIntersection(literalNullA, PossibleContents::fullConeType(nnB), none); |
| |
| assertIntersection( |
| literalNullA, PossibleContents::fullConeType(nullE), literalNullA); |
| assertIntersection(literalNullA, PossibleContents::fullConeType(nnE), none); |
| |
| assertIntersection(exactA, |
| PossibleContents::fullConeType(nullB), |
| PossibleContents::literal(Literal::makeNull(B))); |
| assertIntersection(nnExactA, PossibleContents::fullConeType(nullB), none); |
| assertIntersection(exactA, PossibleContents::fullConeType(nnB), none); |
| |
| // A and E have no intersection, so the only possibility is a null, and that |
| // null must be the bottom type. |
| assertIntersection( |
| exactA, |
| PossibleContents::fullConeType(nullE), |
| PossibleContents::literal(Literal::makeNull(HeapType::none))); |
| |
| assertIntersection(PossibleContents::coneType(nnA, 1), |
| PossibleContents::fullConeType(nnB), |
| nnExactB); |
| assertIntersection(PossibleContents::coneType(nnB, 1), |
| PossibleContents::fullConeType(nnA), |
| PossibleContents::coneType(nnB, 1)); |
| assertIntersection(PossibleContents::coneType(nnD, 2), |
| PossibleContents::fullConeType(nnA), |
| PossibleContents::coneType(nnD, 2)); |
| assertIntersection(PossibleContents::coneType(nnA, 5), |
| PossibleContents::fullConeType(nnD), |
| PossibleContents::coneType(nnD, 3)); |
| |
| assertIntersection(PossibleContents::coneType(nnA, 1), |
| PossibleContents::fullConeType(nnD), |
| none); |
| |
| // Globals stay as globals, but their type might get refined. |
| assertIntersection( |
| funcGlobal, PossibleContents::fullConeType(funcref), funcGlobal); |
| |
| // No global filtering. |
| auto signature = Type(Signature(Type::none, Type::none), Nullable); |
| assertIntersection( |
| nonNullFunc, PossibleContents::fullConeType(signature), nonNullFunc); |
| |
| // Filter a global to a more specific type. |
| assertIntersection(funcGlobal, |
| PossibleContents::fullConeType(signature), |
| PossibleContents::global("funcGlobal", signature)); |
| |
| // Filter a global's nullability only. |
| auto nonNullFuncRef = Type(HeapType::func, NonNullable); |
| assertIntersection(funcGlobal, |
| PossibleContents::fullConeType(nonNullFuncRef), |
| nonNullFuncGlobal); |
| |
| // Incompatible global and cone types have no intersection. |
| assertIntersection(funcGlobal, PossibleContents::fullConeType(nullE), none); |
| |
| // Incompatible hierarchies have no intersection. |
| assertIntersection( |
| literalNullA, PossibleContents::fullConeType(funcref), none); |
| |
| // Computing intersections is also supported with a Literal. |
| assertIntersection(i32Zero, i32Zero, i32Zero); |
| assertIntersection(i32One, i32Zero, none); |
| assertIntersection(i32Global1, i32Zero, i32Zero); |
| assertIntersection(funcGlobal, i32Zero, none); |
| assertIntersection( |
| PossibleContents::fullConeType(Type::i32), i32Zero, i32Zero); |
| assertIntersection(PossibleContents::fullConeType(Type::f64), i32Zero, none); |
| |
| // Computing intersections is also supported with empty contents. |
| assertIntersection(none, none, none); |
| assertIntersection(literalNullA, none, none); |
| assertIntersection(funcGlobal, none, none); |
| assertIntersection(PossibleContents::fullConeType(signature), none, none); |
| |
| // Subcontents. This API only supports the case where one of the inputs is a |
| // full cone type. |
| // First, compare exact types to such a cone. |
| EXPECT_TRUE(PossibleContents::isSubContents( |
| exactA, PossibleContents::fullConeType(nullA))); |
| EXPECT_TRUE(PossibleContents::isSubContents( |
| nnExactA, PossibleContents::fullConeType(nnA))); |
| EXPECT_TRUE(PossibleContents::isSubContents( |
| nnExactA, PossibleContents::fullConeType(nullA))); |
| EXPECT_TRUE(PossibleContents::isSubContents( |
| nnExactD, PossibleContents::fullConeType(nullA))); |
| |
| EXPECT_FALSE(PossibleContents::isSubContents( |
| exactA, PossibleContents::fullConeType(nnA))); |
| EXPECT_FALSE(PossibleContents::isSubContents( |
| exactA, PossibleContents::fullConeType(nullB))); |
| |
| // Next, compare cones. |
| EXPECT_TRUE( |
| PossibleContents::isSubContents(PossibleContents::fullConeType(nullA), |
| PossibleContents::fullConeType(nullA))); |
| EXPECT_TRUE( |
| PossibleContents::isSubContents(PossibleContents::fullConeType(nnA), |
| PossibleContents::fullConeType(nullA))); |
| EXPECT_TRUE(PossibleContents::isSubContents( |
| PossibleContents::fullConeType(nnA), PossibleContents::fullConeType(nnA))); |
| EXPECT_TRUE( |
| PossibleContents::isSubContents(PossibleContents::fullConeType(nullD), |
| PossibleContents::fullConeType(nullA))); |
| |
| EXPECT_FALSE( |
| PossibleContents::isSubContents(PossibleContents::fullConeType(nullA), |
| PossibleContents::fullConeType(nnA))); |
| EXPECT_FALSE( |
| PossibleContents::isSubContents(PossibleContents::fullConeType(nullA), |
| PossibleContents::fullConeType(nullD))); |
| |
| // Trivial values. |
| EXPECT_TRUE(PossibleContents::isSubContents( |
| PossibleContents::none(), PossibleContents::fullConeType(nullA))); |
| EXPECT_FALSE(PossibleContents::isSubContents( |
| PossibleContents::many(), PossibleContents::fullConeType(nullA))); |
| |
| EXPECT_TRUE(PossibleContents::isSubContents( |
| anyNull, PossibleContents::fullConeType(nullA))); |
| EXPECT_FALSE(PossibleContents::isSubContents( |
| anyNull, PossibleContents::fullConeType(nnA))); |
| |
| // Tests cases with a full cone only on the left. Such a cone is only a sub- |
| // contents of Many. |
| EXPECT_FALSE(PossibleContents::isSubContents( |
| PossibleContents::fullConeType(nullA), exactA)); |
| EXPECT_FALSE(PossibleContents::isSubContents( |
| PossibleContents::fullConeType(nullA), nnExactA)); |
| |
| EXPECT_FALSE(PossibleContents::isSubContents( |
| PossibleContents::fullConeType(nullA), PossibleContents::none())); |
| EXPECT_TRUE(PossibleContents::isSubContents( |
| PossibleContents::fullConeType(nullA), PossibleContents::many())); |
| |
| EXPECT_FALSE(PossibleContents::isSubContents( |
| PossibleContents::fullConeType(nullA), anyNull)); |
| EXPECT_FALSE(PossibleContents::isSubContents( |
| PossibleContents::fullConeType(nnA), anyNull)); |
| } |
| |
| TEST_F(PossibleContentsTest, TestOracleManyTypes) { |
| // Test for a node with many possible types. The pass limits how many it |
| // notices to not use excessive memory, so even though 4 are possible here, |
| // we'll just report that more than one is possible, a cone of data. |
| auto wasm = parse(R"( |
| (module |
| (type $A (sub (struct (field i32)))) |
| (type $B (sub (struct (field i64)))) |
| (type $C (sub (struct (field f32)))) |
| (type $D (sub (struct (field f64)))) |
| (func $foo (result (ref any)) |
| (select (result (ref any)) |
| (select (result (ref any)) |
| (struct.new_default $A) |
| (struct.new_default $B) |
| (i32.const 0) |
| ) |
| (select (result (ref any)) |
| (struct.new_default $C) |
| (struct.new_default $D) |
| (i32.const 0) |
| ) |
| (i32.const 0) |
| ) |
| ) |
| ) |
| )"); |
| ContentOracle oracle(*wasm, options); |
| // The body's contents must be a cone of data with depth 1. |
| auto bodyContents = |
| oracle.getContents(ResultLocation{wasm->getFunction("foo"), 0}); |
| ASSERT_TRUE(bodyContents.isConeType()); |
| EXPECT_EQ(bodyContents.getType().getHeapType(), HeapType::struct_); |
| EXPECT_EQ(bodyContents.getCone().depth, Index(1)); |
| } |
| |
| TEST_F(PossibleContentsTest, TestOracleNoFullCones) { |
| // PossibleContents should be normalized, so we never have full cones (depth |
| // infinity). |
| auto wasm = parse(R"( |
| (module |
| (type $A (sub (struct (field i32)))) |
| (type $B (sub $A (struct (field i32)))) |
| (type $C (sub $B (struct (field i32)))) |
| (func $foo (export "foo") |
| ;; Note we must declare $C so that $B and $C have uses and are not |
| ;; removed automatically from consideration. |
| (param $a (ref $A)) (param $c (ref $C)) |
| (result (ref any)) |
| (local.get $a) |
| ) |
| ) |
| )"); |
| ContentOracle oracle(*wasm, options); |
| // The function is exported, and all we know about the parameter $a is that it |
| // is some subtype of $A. This is normalized to depth 2 because that is the |
| // actual depth of subtypes. |
| auto bodyContents = |
| oracle.getContents(ResultLocation{wasm->getFunction("foo"), 0}); |
| ASSERT_TRUE(bodyContents.isConeType()); |
| EXPECT_EQ(bodyContents.getCone().depth, Index(2)); |
| } |
