[Strings] Add string proposal types (#4755)

This starts to implement the Wasm Strings proposal

https://github.com/WebAssembly/stringref/blob/main/proposals/stringref/Overview.md

This just adds the types.

10 files changed, 139 insertions, 14 deletions

diff --git a/src/binaryen-c.cpp b/src/binaryen-c.cpp
index 8a5756f6e..233ff5e34 100644
--- a/src/binaryen-c.cpp
+++ b/src/binaryen-c.cpp
@@ -76,9 +76,8 @@ BinaryenLiteral toBinaryenLiteral(Literal x) {
       assert(x.isNull() && "unexpected non-null reference type literal");
       break;
     case Type::i31ref:
-      WASM_UNREACHABLE("TODO: i31ref");
     case Type::dataref:
-      WASM_UNREACHABLE("TODO: dataref");
+      WASM_UNREACHABLE("TODO: reftypes");
     case Type::none:
     case Type::unreachable:
       WASM_UNREACHABLE("unexpected type");
@@ -104,9 +103,8 @@ Literal fromBinaryenLiteral(BinaryenLiteral x) {
     case Type::eqref:
       return Literal::makeNull(Type(x.type).getHeapType());
     case Type::i31ref:
-      WASM_UNREACHABLE("TODO: i31ref");
     case Type::dataref:
-      WASM_UNREACHABLE("TODO: dataref");
+      WASM_UNREACHABLE("TODO: reftypes");
     case Type::none:
     case Type::unreachable:
       WASM_UNREACHABLE("unexpected type");
diff --git a/src/tools/fuzzing/fuzzing.cpp b/src/tools/fuzzing/fuzzing.cpp
index c828c84d0..5489e7638 100644
--- a/src/tools/fuzzing/fuzzing.cpp
+++ b/src/tools/fuzzing/fuzzing.cpp
@@ -3091,6 +3091,11 @@ HeapType TranslateToFuzzReader::getSubType(HeapType type) {
       case HeapType::data:
         // TODO: nontrivial types as well.
         return HeapType::data;
+      case HeapType::string:
+      case HeapType::stringview_wtf8:
+      case HeapType::stringview_wtf16:
+      case HeapType::stringview_iter:
+        WASM_UNREACHABLE("TODO: fuzz strings");
     }
   }
   // TODO: nontrivial types as well.
diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp
index 2e96087d7..77891ce53 100644
--- a/src/tools/fuzzing/heap-types.cpp
+++ b/src/tools/fuzzing/heap-types.cpp
@@ -303,6 +303,11 @@ struct HeapTypeGeneratorImpl {
           return generateSubEq();
         case HeapType::data:
           return generateSubData();
+        case HeapType::string:
+        case HeapType::stringview_wtf8:
+        case HeapType::stringview_wtf16:
+        case HeapType::stringview_iter:
+          WASM_UNREACHABLE("TODO: fuzz strings");
       }
       WASM_UNREACHABLE("unexpected index");
     }
@@ -390,6 +395,11 @@ struct HeapTypeGeneratorImpl {
           return HeapType::i31;
         case HeapType::data:
           return pickSubData();
+        case HeapType::string:
+        case HeapType::stringview_wtf8:
+        case HeapType::stringview_wtf16:
+        case HeapType::stringview_iter:
+          WASM_UNREACHABLE("TODO: fuzz strings");
       }
       WASM_UNREACHABLE("unexpected kind");
     }
@@ -503,6 +513,11 @@ struct HeapTypeGeneratorImpl {
           }
         case HeapType::data:
           return DataKind{};
+        case HeapType::string:
+        case HeapType::stringview_wtf8:
+        case HeapType::stringview_wtf16:
+        case HeapType::stringview_iter:
+          WASM_UNREACHABLE("TODO: fuzz strings");
       }
       WASM_UNREACHABLE("unexpected kind");
     } else {
diff --git a/src/tools/spec-wrapper.h b/src/tools/spec-wrapper.h
index 43c0e9353..c2a49c598 100644
--- a/src/tools/spec-wrapper.h
+++ b/src/tools/spec-wrapper.h
@@ -62,9 +62,8 @@ inline std::string generateSpecWrapper(Module& wasm) {
           ret += "(ref.null eq)";
           break;
         case Type::i31ref:
-          WASM_UNREACHABLE("TODO: i31ref");
         case Type::dataref:
-          WASM_UNREACHABLE("TODO: dataref");
+          WASM_UNREACHABLE("TODO: reftypes");
         case Type::none:
         case Type::unreachable:
           WASM_UNREACHABLE("unexpected type");
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index 659e0f58b..3b3fa30f6 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -375,8 +375,13 @@ enum EncodedType {
   // run-time type info type, with depth index n
   rtt_n = -0x17, // 0x69
   // run-time type info type, without depth index n
-  rtt = -0x18,     // 0x68
-  dataref = -0x19, // 0x67
+  rtt = -0x18, // 0x68
+  // gc and string reference types
+  dataref = -0x19,          // 0x67
+  stringref = -0x1c,        // 0x64
+  stringview_wtf8 = -0x1d,  // 0x63
+  stringview_wtf16 = -0x1e, // 0x62
+  stringview_iter = -0x1f,  // 0x61
   // type forms
   Func = -0x20,   // 0x60
   Struct = -0x21, // 0x5f
@@ -393,11 +398,18 @@ enum EncodedType {
 };
 
 enum EncodedHeapType {
-  func = -0x10, // 0x70
-  any = -0x11,  // 0x6f
-  eq = -0x13,   // 0x6d
-  i31 = -0x16,  // 0x6a
-  data = -0x19, // 0x67
+  func = -0x10,   // 0x70
+  any = -0x11,    // 0x6f
+  eq = -0x13,     // 0x6d
+  i31 = -0x16,    // 0x6a
+  data = -0x19,   // 0x67
+  string = -0x1c, // 0x64
+  // stringview/iter constants are identical to type, and cannot be duplicated
+  // here as that would be a compiler error, so add _heap suffixes. See
+  // https://github.com/WebAssembly/stringref/issues/12
+  stringview_wtf8_heap = -0x1d,  // 0x63
+  stringview_wtf16_heap = -0x1e, // 0x62
+  stringview_iter_heap = -0x1f,  // 0x61
 };
 
 namespace UserSections {
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 6b1608ddc..23e559aad 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -109,6 +109,7 @@ public:
     funcref,
     anyref,
     eqref,
+    // From here types are non-nullable.
     i31ref,
     dataref,
   };
@@ -342,8 +343,12 @@ public:
     eq,
     i31,
     data,
+    string,
+    stringview_wtf8,
+    stringview_wtf16,
+    stringview_iter,
   };
-  static constexpr BasicHeapType _last_basic_type = data;
+  static constexpr BasicHeapType _last_basic_type = stringview_iter;
 
   // BasicHeapType can be implicitly upgraded to HeapType
   constexpr HeapType(BasicHeapType id) : id(id) {}
diff --git a/src/wasm/literal.cpp b/src/wasm/literal.cpp
index 80af9535e..6c7689990 100644
--- a/src/wasm/literal.cpp
+++ b/src/wasm/literal.cpp
@@ -133,6 +133,10 @@ Literal::Literal(const Literal& other) : type(other.type) {
           return;
         case HeapType::func:
         case HeapType::data:
+        case HeapType::string:
+        case HeapType::stringview_wtf8:
+        case HeapType::stringview_wtf16:
+        case HeapType::stringview_iter:
           WASM_UNREACHABLE("invalid type");
       }
     }
@@ -536,6 +540,10 @@ std::ostream& operator<<(std::ostream& o, Literal literal) {
           break;
         case HeapType::func:
         case HeapType::data:
+        case HeapType::string:
+        case HeapType::stringview_wtf8:
+        case HeapType::stringview_wtf16:
+        case HeapType::stringview_iter:
           WASM_UNREACHABLE("type should have been handled above");
       }
     }
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index b74331aed..87ee00c8a 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -1351,6 +1351,18 @@ void WasmBinaryWriter::writeHeapType(HeapType type) {
       case HeapType::data:
         ret = BinaryConsts::EncodedHeapType::data;
         break;
+      case HeapType::string:
+        ret = BinaryConsts::EncodedHeapType::string;
+        break;
+      case HeapType::stringview_wtf8:
+        ret = BinaryConsts::EncodedHeapType::stringview_wtf8_heap;
+        break;
+      case HeapType::stringview_wtf16:
+        ret = BinaryConsts::EncodedHeapType::stringview_wtf16_heap;
+        break;
+      case HeapType::stringview_iter:
+        ret = BinaryConsts::EncodedHeapType::stringview_iter_heap;
+        break;
     }
   } else {
     WASM_UNREACHABLE("TODO: compound GC types");
@@ -1699,6 +1711,18 @@ bool WasmBinaryBuilder::getBasicType(int32_t code, Type& out) {
     case BinaryConsts::EncodedType::dataref:
       out = Type(HeapType::data, NonNullable);
       return true;
+    case BinaryConsts::EncodedType::stringref:
+      out = Type(HeapType::string, Nullable);
+      return true;
+    case BinaryConsts::EncodedType::stringview_wtf8:
+      out = Type(HeapType::stringview_wtf8, Nullable);
+      return true;
+    case BinaryConsts::EncodedType::stringview_wtf16:
+      out = Type(HeapType::stringview_wtf16, Nullable);
+      return true;
+    case BinaryConsts::EncodedType::stringview_iter:
+      out = Type(HeapType::stringview_iter, Nullable);
+      return true;
     default:
       return false;
   }
@@ -1721,6 +1745,18 @@ bool WasmBinaryBuilder::getBasicHeapType(int64_t code, HeapType& out) {
     case BinaryConsts::EncodedHeapType::data:
       out = HeapType::data;
       return true;
+    case BinaryConsts::EncodedHeapType::string:
+      out = HeapType::string;
+      return true;
+    case BinaryConsts::EncodedHeapType::stringview_wtf8_heap:
+      out = HeapType::stringview_wtf8;
+      return true;
+    case BinaryConsts::EncodedHeapType::stringview_wtf16_heap:
+      out = HeapType::stringview_wtf16;
+      return true;
+    case BinaryConsts::EncodedHeapType::stringview_iter_heap:
+      out = HeapType::stringview_iter;
+      return true;
     default:
       return false;
   }
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index b59319be2..22557a06d 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -1184,6 +1184,18 @@ Type SExpressionWasmBuilder::stringToType(const char* str,
   if (strncmp(str, "dataref", 7) == 0 && (prefix || str[7] == 0)) {
     return Type::dataref;
   }
+  if (strncmp(str, "stringref", 9) == 0 && (prefix || str[9] == 0)) {
+    return Type(HeapType::string, Nullable);
+  }
+  if (strncmp(str, "stringview_wtf8", 15) == 0 && (prefix || str[15] == 0)) {
+    return Type(HeapType::stringview_wtf8, Nullable);
+  }
+  if (strncmp(str, "stringview_wtf16", 16) == 0 && (prefix || str[16] == 0)) {
+    return Type(HeapType::stringview_wtf16, Nullable);
+  }
+  if (strncmp(str, "stringview_iter", 15) == 0 && (prefix || str[15] == 0)) {
+    return Type(HeapType::stringview_iter, Nullable);
+  }
   if (allowError) {
     return Type::none;
   }
@@ -1223,6 +1235,20 @@ HeapType SExpressionWasmBuilder::stringToHeapType(const char* str,
       return HeapType::data;
     }
   }
+  if (str[0] == 's') {
+    if (strncmp(str, "string", 6) == 0 && (prefix || str[6] == 0)) {
+      return HeapType::string;
+    }
+    if (strncmp(str, "stringview_wtf8", 15) == 0 && (prefix || str[15] == 0)) {
+      return HeapType::stringview_wtf8;
+    }
+    if (strncmp(str, "stringview_wtf16", 16) == 0 && (prefix || str[16] == 0)) {
+      return HeapType::stringview_wtf16;
+    }
+    if (strncmp(str, "stringview_iter", 15) == 0 && (prefix || str[15] == 0)) {
+      return HeapType::stringview_iter;
+    }
+  }
   throw ParseException(std::string("invalid wasm heap type: ") + str);
 }
 
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 0092f933d..b79080121 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -621,6 +621,10 @@ HeapType getBasicHeapTypeLUB(HeapType::BasicHeapType a,
       }
       return HeapType::any;
     case HeapType::data:
+    case HeapType::string:
+    case HeapType::stringview_wtf8:
+    case HeapType::stringview_wtf16:
+    case HeapType::stringview_iter:
       return HeapType::any;
   }
   WASM_UNREACHABLE("unexpected basic type");
@@ -679,6 +683,10 @@ std::optional<Type> TypeInfo::getCanonical() const {
             return Type::eqref;
           case HeapType::i31:
           case HeapType::data:
+          case HeapType::string:
+          case HeapType::stringview_wtf8:
+          case HeapType::stringview_wtf16:
+          case HeapType::stringview_iter:
             break;
         }
       } else {
@@ -1739,6 +1747,11 @@ bool SubTyper::isSubType(HeapType a, HeapType b) {
         return false;
       case HeapType::data:
         return a.isData();
+      case HeapType::string:
+      case HeapType::stringview_wtf8:
+      case HeapType::stringview_wtf16:
+      case HeapType::stringview_iter:
+        return false;
     }
   }
   if (a.isBasic()) {
@@ -2117,6 +2130,14 @@ std::ostream& TypePrinter::print(HeapType type) {
         return os << "i31";
       case HeapType::data:
         return os << "data";
+      case HeapType::string:
+        return os << "string";
+      case HeapType::stringview_wtf8:
+        return os << "stringview_wtf8";
+      case HeapType::stringview_wtf16:
+        return os << "stringview_wtf16";
+      case HeapType::stringview_iter:
+        return os << "stringview_iter";
     }
   }