Fix stringview subtyping (#6440)

The stringview types (`stringview_wtf8`, `stringview_wtf16`, and
`stringview_iter`) are not subtypes of `any` even though they are supertypes of
`none`. This breaks the type system invariant that types share a bottom type iff
they share a top type, but we can work around that.

3 files changed, 77 insertions, 36 deletions

diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp
index 13ad01474..5c948e44d 100644
--- a/src/tools/fuzzing/heap-types.cpp
+++ b/src/tools/fuzzing/heap-types.cpp
@@ -454,12 +454,19 @@ struct HeapTypeGeneratorImpl {
         candidates.push_back(HeapType::any);
         break;
       case HeapType::string:
+        candidates.push_back(HeapType::any);
+        break;
       case HeapType::stringview_wtf8:
       case HeapType::stringview_wtf16:
       case HeapType::stringview_iter:
-        candidates.push_back(HeapType::any);
         break;
       case HeapType::none:
+        if (rand.oneIn(10)) {
+          candidates.push_back(HeapType::stringview_wtf8);
+          candidates.push_back(HeapType::stringview_wtf16);
+          candidates.push_back(HeapType::stringview_iter);
+          break;
+        }
         return pickSubAny();
       case HeapType::nofunc:
         return pickSubFunc();
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 5957f9388..32da64470 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -456,7 +456,7 @@ std::optional<HeapType> getBasicHeapTypeLUB(HeapType::BasicHeapType a,
   if (a == b) {
     return a;
   }
-  if (HeapType(a).getBottom() != HeapType(b).getBottom()) {
+  if (HeapType(a).getTop() != HeapType(b).getTop()) {
     return {};
   }
   if (HeapType(a).isBottom()) {
@@ -494,10 +494,12 @@ std::optional<HeapType> getBasicHeapTypeLUB(HeapType::BasicHeapType a,
       return {HeapType::any};
     case HeapType::array:
     case HeapType::string:
+      return {HeapType::any};
     case HeapType::stringview_wtf8:
     case HeapType::stringview_wtf16:
     case HeapType::stringview_iter:
-      return {HeapType::any};
+      // Only joinable with bottom or self, both already handled.
+      return std::nullopt;
     case HeapType::none:
     case HeapType::noext:
     case HeapType::nofunc:
@@ -1411,6 +1413,14 @@ HeapType::BasicHeapType HeapType::getBottom() const {
 }
 
 HeapType::BasicHeapType HeapType::getTop() const {
+  if (*this == HeapType::stringview_wtf8 ||
+      *this == HeapType::stringview_wtf16 ||
+      *this == HeapType::stringview_iter) {
+    // These types are their own top types even though they share a bottom type
+    // `none` with the anyref hierarchy. This means that technically there are
+    // multiple top types for `none`, but `any` is the canonical one.
+    return getBasic();
+  }
   switch (getBottom()) {
     case none:
       return any;
@@ -1418,7 +1428,20 @@ HeapType::BasicHeapType HeapType::getTop() const {
       return func;
     case noext:
       return ext;
-    default:
+    case noexn:
+      return exn;
+    case ext:
+    case func:
+    case any:
+    case eq:
+    case i31:
+    case struct_:
+    case array:
+    case exn:
+    case string:
+    case stringview_wtf8:
+    case stringview_wtf16:
+    case stringview_iter:
       break;
   }
   WASM_UNREACHABLE("unexpected type");
@@ -1693,13 +1716,13 @@ bool SubTyper::isSubType(HeapType a, HeapType b) {
   if (b.isBasic()) {
     switch (b.getBasic()) {
       case HeapType::ext:
-        return a.getBottom() == HeapType::noext;
+        return a.getTop() == HeapType::ext;
       case HeapType::func:
-        return a.getBottom() == HeapType::nofunc;
+        return a.getTop() == HeapType::func;
       case HeapType::exn:
-        return a.getBottom() == HeapType::noexn;
+        return a.getTop() == HeapType::exn;
       case HeapType::any:
-        return a.getBottom() == HeapType::none;
+        return a.getTop() == HeapType::any;
       case HeapType::eq:
         return a == HeapType::i31 || a == HeapType::none ||
                a == HeapType::struct_ || a == HeapType::array || a.isStruct() ||
diff --git a/test/gtest/type-builder.cpp b/test/gtest/type-builder.cpp
index 43e470a02..e8c24b06c 100644
--- a/test/gtest/type-builder.cpp
+++ b/test/gtest/type-builder.cpp
@@ -545,23 +545,34 @@ TEST_F(TypeTest, TestHeapTypeRelations) {
     if (a == b) {
       EXPECT_TRUE(HeapType::isSubType(a, b));
       EXPECT_TRUE(HeapType::isSubType(b, a));
+      EXPECT_EQ(a.getTop(), b.getTop());
       EXPECT_EQ(a.getBottom(), b.getBottom());
     } else if (lub && *lub == b) {
       EXPECT_TRUE(HeapType::isSubType(a, b));
       EXPECT_FALSE(HeapType::isSubType(b, a));
+      // This would hold except for the case of stringview types and none, where
+      // stringview types are their own top types, but we return `any` as the
+      // top type of none.
+      // EXPECT_EQ(a.getTop(), b.getTop());
       EXPECT_EQ(a.getBottom(), b.getBottom());
     } else if (lub && *lub == a) {
       EXPECT_FALSE(HeapType::isSubType(a, b));
       EXPECT_TRUE(HeapType::isSubType(b, a));
+      // EXPECT_EQ(a.getTop(), b.getTop());
       EXPECT_EQ(a.getBottom(), b.getBottom());
     } else if (lub) {
       EXPECT_FALSE(HeapType::isSubType(a, b));
       EXPECT_FALSE(HeapType::isSubType(b, a));
+      // EXPECT_EQ(a.getTop(), b.getTop());
       EXPECT_EQ(a.getBottom(), b.getBottom());
     } else {
       EXPECT_FALSE(HeapType::isSubType(a, b));
       EXPECT_FALSE(HeapType::isSubType(b, a));
-      EXPECT_NE(a.getBottom(), b.getBottom());
+      EXPECT_NE(a.getTop(), b.getTop());
+      // This would hold except for stringview types, which share a bottom with
+      // the anyref hierarchy despite having no shared upper bound with its
+      // types.
+      // EXPECT_NE(a.getBottom(), b.getBottom());
     }
   };
 
@@ -606,9 +617,9 @@ TEST_F(TypeTest, TestHeapTypeRelations) {
   assertLUB(any, struct_, any);
   assertLUB(any, array, any);
   assertLUB(any, string, any);
-  assertLUB(any, stringview_wtf8, any);
-  assertLUB(any, stringview_wtf16, any);
-  assertLUB(any, stringview_iter, any);
+  assertLUB(any, stringview_wtf8, {});
+  assertLUB(any, stringview_wtf16, {});
+  assertLUB(any, stringview_iter, {});
   assertLUB(any, none, any);
   assertLUB(any, noext, {});
   assertLUB(any, nofunc, {});
@@ -621,9 +632,9 @@ TEST_F(TypeTest, TestHeapTypeRelations) {
   assertLUB(eq, struct_, eq);
   assertLUB(eq, array, eq);
   assertLUB(eq, string, any);
-  assertLUB(eq, stringview_wtf8, any);
-  assertLUB(eq, stringview_wtf16, any);
-  assertLUB(eq, stringview_iter, any);
+  assertLUB(eq, stringview_wtf8, {});
+  assertLUB(eq, stringview_wtf16, {});
+  assertLUB(eq, stringview_iter, {});
   assertLUB(eq, none, eq);
   assertLUB(eq, noext, {});
   assertLUB(eq, nofunc, {});
@@ -635,9 +646,9 @@ TEST_F(TypeTest, TestHeapTypeRelations) {
   assertLUB(i31, struct_, eq);
   assertLUB(i31, array, eq);
   assertLUB(i31, string, any);
-  assertLUB(i31, stringview_wtf8, any);
-  assertLUB(i31, stringview_wtf16, any);
-  assertLUB(i31, stringview_iter, any);
+  assertLUB(i31, stringview_wtf8, {});
+  assertLUB(i31, stringview_wtf16, {});
+  assertLUB(i31, stringview_iter, {});
   assertLUB(i31, none, i31);
   assertLUB(i31, noext, {});
   assertLUB(i31, nofunc, {});
@@ -648,9 +659,9 @@ TEST_F(TypeTest, TestHeapTypeRelations) {
   assertLUB(struct_, struct_, struct_);
   assertLUB(struct_, array, eq);
   assertLUB(struct_, string, any);
-  assertLUB(struct_, stringview_wtf8, any);
-  assertLUB(struct_, stringview_wtf16, any);
-  assertLUB(struct_, stringview_iter, any);
+  assertLUB(struct_, stringview_wtf8, {});
+  assertLUB(struct_, stringview_wtf16, {});
+  assertLUB(struct_, stringview_iter, {});
   assertLUB(struct_, none, struct_);
   assertLUB(struct_, noext, {});
   assertLUB(struct_, nofunc, {});
@@ -660,9 +671,9 @@ TEST_F(TypeTest, TestHeapTypeRelations) {
 
   assertLUB(array, array, array);
   assertLUB(array, string, any);
-  assertLUB(array, stringview_wtf8, any);
-  assertLUB(array, stringview_wtf16, any);
-  assertLUB(array, stringview_iter, any);
+  assertLUB(array, stringview_wtf8, {});
+  assertLUB(array, stringview_wtf16, {});
+  assertLUB(array, stringview_iter, {});
   assertLUB(array, none, array);
   assertLUB(array, noext, {});
   assertLUB(array, nofunc, {});
@@ -671,9 +682,9 @@ TEST_F(TypeTest, TestHeapTypeRelations) {
   assertLUB(array, defArray, array);
 
   assertLUB(string, string, string);
-  assertLUB(string, stringview_wtf8, any);
-  assertLUB(string, stringview_wtf16, any);
-  assertLUB(string, stringview_iter, any);
+  assertLUB(string, stringview_wtf8, {});
+  assertLUB(string, stringview_wtf16, {});
+  assertLUB(string, stringview_iter, {});
   assertLUB(string, none, string);
   assertLUB(string, noext, {});
   assertLUB(string, nofunc, {});
@@ -682,31 +693,31 @@ TEST_F(TypeTest, TestHeapTypeRelations) {
   assertLUB(string, defArray, any);
 
   assertLUB(stringview_wtf8, stringview_wtf8, stringview_wtf8);
-  assertLUB(stringview_wtf8, stringview_wtf16, any);
-  assertLUB(stringview_wtf8, stringview_iter, any);
+  assertLUB(stringview_wtf8, stringview_wtf16, {});
+  assertLUB(stringview_wtf8, stringview_iter, {});
   assertLUB(stringview_wtf8, none, stringview_wtf8);
   assertLUB(stringview_wtf8, noext, {});
   assertLUB(stringview_wtf8, nofunc, {});
   assertLUB(stringview_wtf8, defFunc, {});
-  assertLUB(stringview_wtf8, defStruct, any);
-  assertLUB(stringview_wtf8, defArray, any);
+  assertLUB(stringview_wtf8, defStruct, {});
+  assertLUB(stringview_wtf8, defArray, {});
 
   assertLUB(stringview_wtf16, stringview_wtf16, stringview_wtf16);
-  assertLUB(stringview_wtf16, stringview_iter, any);
+  assertLUB(stringview_wtf16, stringview_iter, {});
   assertLUB(stringview_wtf16, none, stringview_wtf16);
   assertLUB(stringview_wtf16, noext, {});
   assertLUB(stringview_wtf16, nofunc, {});
   assertLUB(stringview_wtf16, defFunc, {});
-  assertLUB(stringview_wtf16, defStruct, any);
-  assertLUB(stringview_wtf16, defArray, any);
+  assertLUB(stringview_wtf16, defStruct, {});
+  assertLUB(stringview_wtf16, defArray, {});
 
   assertLUB(stringview_iter, stringview_iter, stringview_iter);
   assertLUB(stringview_iter, none, stringview_iter);
   assertLUB(stringview_iter, noext, {});
   assertLUB(stringview_iter, nofunc, {});
   assertLUB(stringview_iter, defFunc, {});
-  assertLUB(stringview_iter, defStruct, any);
-  assertLUB(stringview_iter, defArray, any);
+  assertLUB(stringview_iter, defStruct, {});
+  assertLUB(stringview_iter, defArray, {});
 
   assertLUB(none, none, none);
   assertLUB(none, noext, {});