Make final types the default (#5918)

Match the spec and parse the shorthand binary and text formats as final and emit
final types without supertypes using the shorthands as well. This is a
potentially-breaking change, since the text and binary shorthands can no longer
be used to define types that have subtypes.

Also make TypeBuilder entries final by default to better match the spec and
update the internal APIs to use the "open" terminology rather than "final"
terminology. Future changes will update the text format to use the standard "sub
open" rather than the current "sub final" keywords. The exception is the new wat
parser, which supporst "sub open" as of this change, since it didn't support
final types at all previously.

12 files changed, 47 insertions, 35 deletions

diff --git a/src/binaryen-c.cpp b/src/binaryen-c.cpp
index 59b01032d..fd00c25c0 100644
--- a/src/binaryen-c.cpp
+++ b/src/binaryen-c.cpp
@@ -6413,6 +6413,9 @@ void TypeBuilderSetSubType(TypeBuilderRef builder,
                            BinaryenHeapType superType) {
   ((TypeBuilder*)builder)->setSubType(index, HeapType(superType));
 }
+void TypeBuilderSetOpen(TypeBuilderRef builder, BinaryenIndex index) {
+  ((TypeBuilder*)builder)->setOpen(index);
+}
 void TypeBuilderCreateRecGroup(TypeBuilderRef builder,
                                BinaryenIndex index,
                                BinaryenIndex length) {
diff --git a/src/binaryen-c.h b/src/binaryen-c.h
index 2288eb5ca..f4f4f2d74 100644
--- a/src/binaryen-c.h
+++ b/src/binaryen-c.h
@@ -3572,6 +3572,9 @@ BINARYEN_API BinaryenType TypeBuilderGetTempRefType(TypeBuilderRef builder,
 BINARYEN_API void TypeBuilderSetSubType(TypeBuilderRef builder,
                                         BinaryenIndex index,
                                         BinaryenHeapType superType);
+// Sets the type at `index` to be open (i.e. non-final).
+BINARYEN_API void TypeBuilderSetOpen(TypeBuilderRef builder,
+                                     BinaryenIndex index);
 // Creates a new recursion group in the range `index` inclusive to `index +
 // length` exclusive. Recursion groups must not overlap.
 BINARYEN_API void TypeBuilderCreateRecGroup(TypeBuilderRef builder,
diff --git a/src/ir/type-updating.cpp b/src/ir/type-updating.cpp
index 0bc14763b..cca0d2360 100644
--- a/src/ir/type-updating.cpp
+++ b/src/ir/type-updating.cpp
@@ -72,7 +72,7 @@ GlobalTypeRewriter::TypeMap GlobalTypeRewriter::rebuildTypes() {
   // Create the temporary heap types.
   i = 0;
   for (auto [type, _] : typeIndices) {
-    typeBuilder[i].setFinal(type.isFinal());
+    typeBuilder[i].setOpen(type.isOpen());
     if (type.isSignature()) {
       auto sig = type.getSignature();
       TypeList newParams, newResults;
diff --git a/src/passes/TypeMerging.cpp b/src/passes/TypeMerging.cpp
index ea1fa7916..3d7a032b5 100644
--- a/src/passes/TypeMerging.cpp
+++ b/src/passes/TypeMerging.cpp
@@ -538,7 +538,7 @@ bool shapeEq(HeapType a, HeapType b) {
   // Check whether `a` and `b` have the same top-level structure, including the
   // position and identity of any children that are not included as transitions
   // in the DFA, i.e. any children that are not nontrivial references.
-  if (a.isFinal() != b.isFinal()) {
+  if (a.isOpen() != b.isOpen()) {
     return false;
   }
   if (a.isStruct() && b.isStruct()) {
@@ -554,7 +554,7 @@ bool shapeEq(HeapType a, HeapType b) {
 }
 
 size_t shapeHash(HeapType a) {
-  size_t digest = hash(a.isFinal());
+  size_t digest = hash(a.isOpen());
   if (a.isStruct()) {
     rehash(digest, 0);
     hash_combine(digest, shapeHash(a.getStruct()));
diff --git a/src/passes/TypeSSA.cpp b/src/passes/TypeSSA.cpp
index f44df96e1..cb8f0f049 100644
--- a/src/passes/TypeSSA.cpp
+++ b/src/passes/TypeSSA.cpp
@@ -110,7 +110,7 @@ std::vector<HeapType> ensureTypesAreInNewRecGroup(RecGroup recGroup,
         if (auto super = type.getSuperType()) {
           builder[i].subTypeOf(*super);
         }
-        builder[i].setFinal(type.isFinal());
+        builder[i].setOpen(type.isOpen());
       }
 
       // Implement the hash as a struct with "random" fields, and add it.
@@ -255,6 +255,7 @@ struct TypeSSA : public Pass {
         builder[i] = oldType.getArray();
       }
       builder[i].subTypeOf(oldType);
+      builder[i].setOpen();
     }
     builder.createRecGroup(0, num);
     auto result = builder.build();
@@ -311,7 +312,7 @@ struct TypeSSA : public Pass {
       return false;
     }
 
-    if (curr->type.getHeapType().isFinal()) {
+    if (!curr->type.getHeapType().isOpen()) {
       // We can't create new subtypes of a final type anyway.
       return false;
     }
diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp
index 2f77c5765..c8980cbe8 100644
--- a/src/tools/fuzzing/heap-types.cpp
+++ b/src/tools/fuzzing/heap-types.cpp
@@ -87,9 +87,7 @@ struct HeapTypeGeneratorImpl {
 
     // Types without nontrivial subtypes may be marked final.
     for (Index i = 0; i < builder.size(); ++i) {
-      if (subtypeIndices[i].size() == 1 && rand.oneIn(2)) {
-        builder[i].setFinal();
-      }
+      builder[i].setOpen(subtypeIndices[i].size() > 1 || rand.oneIn(2));
     }
 
     // Initialize the recursion groups.
@@ -894,7 +892,7 @@ std::vector<HeapType> Inhabitator::build() {
         builder[i].subTypeOf(*super);
       }
     }
-    builder[i].setFinal(types[i].isFinal());
+    builder[i].setOpen(types[i].isOpen());
   }
 
   auto built = builder.build();
diff --git a/src/tools/wasm-fuzz-types.cpp b/src/tools/wasm-fuzz-types.cpp
index 50f1e1e3c..2be8aa5e7 100644
--- a/src/tools/wasm-fuzz-types.cpp
+++ b/src/tools/wasm-fuzz-types.cpp
@@ -264,7 +264,7 @@ void Fuzzer::checkCanonicalization() {
 
       // Set finality
       for (size_t i = 0; i < types.size(); ++i) {
-        builder[i].setFinal(types[i].isFinal());
+        builder[i].setOpen(types[i].isOpen());
       }
 
       // Set up recursion groups and record group ends to ensure we only select
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 0d41d0cc2..927e37845 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -361,7 +361,7 @@ public:
   bool isArray() const;
   bool isString() const;
   bool isBottom() const;
-  bool isFinal() const;
+  bool isOpen() const;
 
   Signature getSignature() const;
   const Struct& getStruct() const;
@@ -587,7 +587,7 @@ struct TypeBuilder {
   // not overlap or go out of bounds.
   void createRecGroup(size_t i, size_t length);
 
-  void setFinal(size_t i, bool final = true);
+  void setOpen(size_t i, bool open = true);
 
   enum class ErrorReason {
     // There is a cycle in the supertype relation.
@@ -650,8 +650,8 @@ struct TypeBuilder {
       builder.setSubType(index, other);
       return *this;
     }
-    Entry& setFinal(bool final = true) {
-      builder.setFinal(index, final);
+    Entry& setOpen(bool open = true) {
+      builder.setOpen(index, open);
       return *this;
     }
   };
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index 51325e7dd..d43640e26 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -265,13 +265,11 @@ void WasmBinaryWriter::writeTypes() {
     // Emit the type definition.
     BYN_TRACE("write " << type << std::endl);
     auto super = type.getSuperType();
-    // TODO: Use the binary shorthand for final types once we parse MVP
-    // signatures as final.
-    if (type.isFinal() || super || hasSubtypes[i]) {
-      if (type.isFinal()) {
-        o << S32LEB(BinaryConsts::EncodedType::SubFinal);
-      } else {
+    if (super || type.isOpen()) {
+      if (type.isOpen()) {
         o << S32LEB(BinaryConsts::EncodedType::Sub);
+      } else {
+        o << S32LEB(BinaryConsts::EncodedType::SubFinal);
       }
       if (super) {
         o << U32LEB(1);
@@ -2268,9 +2266,8 @@ void WasmBinaryReader::readTypes() {
     std::optional<uint32_t> superIndex;
     if (form == BinaryConsts::EncodedType::Sub ||
         form == BinaryConsts::EncodedType::SubFinal) {
-      if (form == BinaryConsts::EncodedType::SubFinal) {
-        // TODO: Interpret type definitions without any `sub` as final as well.
-        builder[i].setFinal();
+      if (form == BinaryConsts::EncodedType::Sub) {
+        builder[i].setOpen();
       }
       uint32_t supers = getU32LEB();
       if (supers > 0) {
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index b6b9a40fb..e30901c5b 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -929,8 +929,9 @@ void SExpressionWasmBuilder::preParseHeapTypes(Element& module) {
     if (kind == SUB) {
       Index i = 1;
       if (*def[i] == FINAL) {
-        builder[index].setFinal();
         ++i;
+      } else {
+        builder[index].setOpen();
       }
       if (def[i]->dollared()) {
         super = def[i];
@@ -959,6 +960,7 @@ void SExpressionWasmBuilder::preParseHeapTypes(Element& module) {
       if (kind == FUNC) {
         builder[index] = parseSignatureDef(def, 0);
       } else if (kind == FUNC_SUBTYPE) {
+        builder[index].setOpen();
         builder[index] = parseSignatureDef(def, 1);
         super = def[def.size() - 1];
         if (!super->dollared() && super->str() == FUNC) {
@@ -968,6 +970,7 @@ void SExpressionWasmBuilder::preParseHeapTypes(Element& module) {
       } else if (kind == STRUCT) {
         builder[index] = parseStructDef(def, index, 0);
       } else if (kind == STRUCT_SUBTYPE) {
+        builder[index].setOpen();
         builder[index] = parseStructDef(def, index, 1);
         super = def[def.size() - 1];
         if (!super->dollared() && super->str() == DATA) {
@@ -977,6 +980,7 @@ void SExpressionWasmBuilder::preParseHeapTypes(Element& module) {
       } else if (kind == ARRAY) {
         builder[index] = parseArrayDef(def);
       } else if (kind == ARRAY_SUBTYPE) {
+        builder[index].setOpen();
         builder[index] = parseArrayDef(def);
         super = def[def.size() - 1];
         if (!super->dollared() && super->str() == DATA) {
@@ -993,6 +997,7 @@ void SExpressionWasmBuilder::preParseHeapTypes(Element& module) {
       }
     } else if (elementStartsWith(elem[elem.size() - 1], EXTENDS)) {
       // '(' 'extends' $supertype ')'
+      builder[index].setOpen();
       Element& extends = *elem[elem.size() - 1];
       super = extends[1];
     }
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 0c4e7b049..ba38231b6 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -85,7 +85,7 @@ struct HeapTypeInfo {
   // Used in assertions to ensure that temporary types don't leak into the
   // global store.
   bool isTemp = false;
-  bool isFinal = false;
+  bool isOpen = false;
   // The supertype of this HeapType, if it exists.
   HeapTypeInfo* supertype = nullptr;
   // The recursion group of this type or null if the recursion group is trivial
@@ -1180,11 +1180,11 @@ bool HeapType::isBottom() const {
   return false;
 }
 
-bool HeapType::isFinal() const {
+bool HeapType::isOpen() const {
   if (isBasic()) {
     return false;
   } else {
-    return getHeapTypeInfo(*this)->isFinal;
+    return getHeapTypeInfo(*this)->isOpen;
   }
 }
 
@@ -1771,13 +1771,12 @@ std::ostream& TypePrinter::print(HeapType type) {
     os << "(; temp ;) ";
   }
 
-  // TODO: Use shorthand for final types once we parse MVP signatures as final.
   bool useSub = false;
   auto super = type.getSuperType();
-  if (super || type.isFinal()) {
+  if (super || type.isOpen()) {
     useSub = true;
     os << "(sub ";
-    if (type.isFinal()) {
+    if (!type.isOpen()) {
       os << "final ";
     }
     if (super) {
@@ -1946,7 +1945,7 @@ size_t RecGroupHasher::hash(const HeapTypeInfo& info) const {
   if (info.supertype) {
     hash_combine(digest, hash(HeapType(uintptr_t(info.supertype))));
   }
-  wasm::rehash(digest, info.isFinal);
+  wasm::rehash(digest, info.isOpen);
   wasm::rehash(digest, info.kind);
   switch (info.kind) {
     case HeapTypeInfo::SignatureKind:
@@ -2069,7 +2068,7 @@ bool RecGroupEquator::eq(const HeapTypeInfo& a, const HeapTypeInfo& b) const {
       return false;
     }
   }
-  if (a.isFinal != b.isFinal) {
+  if (a.isOpen != b.isOpen) {
     return false;
   }
   if (a.kind != b.kind) {
@@ -2325,15 +2324,15 @@ void TypeBuilder::createRecGroup(size_t index, size_t length) {
     {RecGroup(uintptr_t(groupInfo.get())), std::move(groupInfo)});
 }
 
-void TypeBuilder::setFinal(size_t i, bool final) {
+void TypeBuilder::setOpen(size_t i, bool open) {
   assert(i < size() && "index out of bounds");
-  impl->entries[i].info->isFinal = final;
+  impl->entries[i].info->isOpen = open;
 }
 
 namespace {
 
 bool isValidSupertype(const HeapTypeInfo& sub, const HeapTypeInfo& super) {
-  if (super.isFinal) {
+  if (!super.isOpen) {
     return false;
   }
   if (sub.kind != super.kind) {
diff --git a/src/wasm/wat-parser.cpp b/src/wasm/wat-parser.cpp
index 3961cbb7f..bdd1af0d8 100644
--- a/src/wasm/wat-parser.cpp
+++ b/src/wasm/wat-parser.cpp
@@ -849,6 +849,7 @@ struct ParseDeclsCtx : NullTypeParserCtx, NullInstrParserCtx {
   void addFuncType(SignatureT) {}
   void addStructType(StructT) {}
   void addArrayType(ArrayT) {}
+  void setOpen() {}
   Result<> addSubtype(Index) { return Ok{}; }
   void finishSubtype(Name name, Index pos) {
     subtypeDefs.push_back({name, pos, Index(subtypeDefs.size())});
@@ -1078,6 +1079,8 @@ struct ParseTypeDefsCtx : TypeParserCtx<ParseTypeDefsCtx> {
 
   void addArrayType(ArrayT& type) { builder[index] = type; }
 
+  void setOpen() { builder[index].setOpen(); }
+
   Result<> addSubtype(Index super) {
     if (super >= builder.size()) {
       return in.err("supertype index out of bounds");
@@ -3463,6 +3466,9 @@ template<typename Ctx> MaybeResult<> subtype(Ctx& ctx) {
   }
 
   if (ctx.in.takeSExprStart("sub"sv)) {
+    if (ctx.in.takeKeyword("open"sv)) {
+      ctx.setOpen();
+    }
     if (auto super = maybeTypeidx(ctx)) {
       CHECK_ERR(super);
       CHECK_ERR(ctx.addSubtype(*super));