Restore the `extern` heap type (#4898)

The GC proposal has split `any` and `extern` back into two separate types, so
reintroduce `HeapType::ext` to represent `extern`. Before it was originally
removed in #4633, externref was a subtype of anyref, but now it is not. Now that
we have separate heaptype type hierarchies, make `HeapType::getLeastUpperBound`
fallible as well.

17 files changed, 206 insertions, 98 deletions

diff --git a/src/binaryen-c.cpp b/src/binaryen-c.cpp
index 869f3a92a..95569adfd 100644
--- a/src/binaryen-c.cpp
+++ b/src/binaryen-c.cpp
@@ -58,10 +58,11 @@ BinaryenLiteral toBinaryenLiteral(Literal x) {
         case HeapType::func:
           ret.func = x.isNull() ? nullptr : x.getFunc().c_str();
           break;
-        case HeapType::any:
+        case HeapType::ext:
         case HeapType::eq:
           assert(x.isNull() && "unexpected non-null reference type literal");
           break;
+        case HeapType::any:
         case HeapType::i31:
         case HeapType::data:
         case HeapType::string:
@@ -113,6 +114,7 @@ Literal fromBinaryenLiteral(BinaryenLiteral x) {
         case HeapType::data:
           assert(false && "Literals must have concrete types");
           WASM_UNREACHABLE("no fallthrough here");
+        case HeapType::ext:
         case HeapType::i31:
         case HeapType::string:
         case HeapType::stringview_wtf8:
@@ -158,7 +160,6 @@ extern "C" {
 //
 
 // Core types
-// TODO: Deprecate BinaryenTypeExternref?
 
 BinaryenType BinaryenTypeNone(void) { return Type::none; }
 BinaryenType BinaryenTypeInt32(void) { return Type::i32; }
@@ -170,7 +171,7 @@ BinaryenType BinaryenTypeFuncref(void) {
   return Type(HeapType::func, Nullable).getID();
 }
 BinaryenType BinaryenTypeExternref(void) {
-  return Type(HeapType::any, Nullable).getID();
+  return Type(HeapType::ext, Nullable).getID();
 }
 BinaryenType BinaryenTypeAnyref(void) {
   return Type(HeapType::any, Nullable).getID();
@@ -239,6 +240,9 @@ BinaryenPackedType BinaryenPackedTypeInt16(void) {
 
 // Heap types
 
+BinaryenHeapType BinaryenHeapTypeExt() {
+  return static_cast<BinaryenHeapType>(HeapType::BasicHeapType::ext);
+}
 BinaryenHeapType BinaryenHeapTypeFunc() {
   return static_cast<BinaryenHeapType>(HeapType::BasicHeapType::func);
 }
diff --git a/src/binaryen-c.h b/src/binaryen-c.h
index f5bb71eb9..f9d78e8c9 100644
--- a/src/binaryen-c.h
+++ b/src/binaryen-c.h
@@ -137,6 +137,7 @@ BINARYEN_API BinaryenPackedType BinaryenPackedTypeInt16(void);
 
 typedef uintptr_t BinaryenHeapType;
 
+BINARYEN_API BinaryenHeapType BinaryenHeapTypeExt(void);
 BINARYEN_API BinaryenHeapType BinaryenHeapTypeFunc(void);
 BINARYEN_API BinaryenHeapType BinaryenHeapTypeAny(void);
 BINARYEN_API BinaryenHeapType BinaryenHeapTypeEq(void);
diff --git a/src/ir/possible-constant.h b/src/ir/possible-constant.h
index b3272461d..21f1cfa65 100644
--- a/src/ir/possible-constant.h
+++ b/src/ir/possible-constant.h
@@ -114,8 +114,14 @@ public:
       auto type = getConstantLiteral().type.getHeapType();
       auto otherType = other.getConstantLiteral().type.getHeapType();
       auto lub = HeapType::getLeastUpperBound(type, otherType);
-      if (lub != type) {
-        value = Literal::makeNull(lub);
+      if (!lub) {
+        // TODO: Remove this workaround once we have bottom types to assign to
+        // null literals.
+        value = Many();
+        return true;
+      }
+      if (*lub != type) {
+        value = Literal::makeNull(*lub);
         return true;
       }
       return false;
diff --git a/src/ir/possible-contents.cpp b/src/ir/possible-contents.cpp
index 7079a9446..d9c608bda 100644
--- a/src/ir/possible-contents.cpp
+++ b/src/ir/possible-contents.cpp
@@ -56,7 +56,13 @@ void PossibleContents::combine(const PossibleContents& other) {
       assert(other.isNull());
       auto lub = HeapType::getLeastUpperBound(type.getHeapType(),
                                               otherType.getHeapType());
-      value = Literal::makeNull(lub);
+      if (!lub) {
+        // TODO: Remove this workaround once we have bottom types to assign to
+        // null literals.
+        value = Many();
+        return;
+      }
+      value = Literal::makeNull(*lub);
     }
     return;
   }
diff --git a/src/passes/InstrumentLocals.cpp b/src/passes/InstrumentLocals.cpp
index 761aac2a9..311d4a27b 100644
--- a/src/passes/InstrumentLocals.cpp
+++ b/src/passes/InstrumentLocals.cpp
@@ -57,7 +57,7 @@ Name get_f32("get_f32");
 Name get_f64("get_f64");
 Name get_v128("get_v128");
 Name get_funcref("get_funcref");
-Name get_anyref("get_anyref");
+Name get_externref("get_externref");
 
 Name set_i32("set_i32");
 Name set_i64("set_i64");
@@ -65,7 +65,7 @@ Name set_f32("set_f32");
 Name set_f64("set_f64");
 Name set_v128("set_v128");
 Name set_funcref("set_funcref");
-Name set_anyref("set_anyref");
+Name set_externref("set_externref");
 
 struct InstrumentLocals : public WalkerPass<PostWalker<InstrumentLocals>> {
   void visitLocalGet(LocalGet* curr) {
@@ -75,8 +75,8 @@ struct InstrumentLocals : public WalkerPass<PostWalker<InstrumentLocals>> {
       auto heapType = curr->type.getHeapType();
       if (heapType == HeapType::func && curr->type.isNullable()) {
         import = get_funcref;
-      } else if (heapType == HeapType::any && curr->type.isNullable()) {
-        import = get_anyref;
+      } else if (heapType == HeapType::ext && curr->type.isNullable()) {
+        import = get_externref;
       } else {
         WASM_UNREACHABLE("TODO: general reference types");
       }
@@ -128,8 +128,8 @@ struct InstrumentLocals : public WalkerPass<PostWalker<InstrumentLocals>> {
       auto heapType = type.getHeapType();
       if (heapType == HeapType::func && type.isNullable()) {
         import = set_funcref;
-      } else if (heapType == HeapType::any && type.isNullable()) {
-        import = set_anyref;
+      } else if (heapType == HeapType::ext && type.isNullable()) {
+        import = set_externref;
       } else {
         WASM_UNREACHABLE("TODO: general reference types");
       }
@@ -175,12 +175,12 @@ struct InstrumentLocals : public WalkerPass<PostWalker<InstrumentLocals>> {
 
     if (curr->features.hasReferenceTypes()) {
       Type func = Type(HeapType::func, Nullable);
-      Type any = Type(HeapType::any, Nullable);
+      Type ext = Type(HeapType::ext, Nullable);
 
       addImport(curr, get_funcref, {Type::i32, Type::i32, func}, func);
       addImport(curr, set_funcref, {Type::i32, Type::i32, func}, func);
-      addImport(curr, get_anyref, {Type::i32, Type::i32, any}, any);
-      addImport(curr, set_anyref, {Type::i32, Type::i32, any}, any);
+      addImport(curr, get_externref, {Type::i32, Type::i32, ext}, ext);
+      addImport(curr, set_externref, {Type::i32, Type::i32, ext}, ext);
     }
     if (curr->features.hasSIMD()) {
       addImport(curr, get_v128, {Type::i32, Type::i32, Type::v128}, Type::v128);
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index 87c33ed93..81ae1bfc6 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -88,6 +88,9 @@ static bool maybePrintRefShorthand(std::ostream& o, Type type) {
   if (heapType.isBasic()) {
     if (type.isNullable()) {
       switch (heapType.getBasic()) {
+        case HeapType::ext:
+          o << "externref";
+          return true;
         case HeapType::func:
           o << "funcref";
           return true;
@@ -115,6 +118,7 @@ static bool maybePrintRefShorthand(std::ostream& o, Type type) {
       }
     } else {
       switch (heapType.getBasic()) {
+        case HeapType::ext:
         case HeapType::func:
         case HeapType::any:
         case HeapType::eq:
diff --git a/src/tools/fuzzing/fuzzing.cpp b/src/tools/fuzzing/fuzzing.cpp
index cdefe29f1..cc64b3b6a 100644
--- a/src/tools/fuzzing/fuzzing.cpp
+++ b/src/tools/fuzzing/fuzzing.cpp
@@ -1968,6 +1968,10 @@ Expression* TranslateToFuzzReader::makeConstBasicRef(Type type) {
   assert(heapType.isBasic());
   assert(wasm.features.hasReferenceTypes());
   switch (heapType.getBasic()) {
+    case HeapType::ext: {
+      assert(type.isNullable() && "Cannot handle non-nullable externref");
+      return builder.makeRefNull(type);
+    }
     case HeapType::func: {
       return makeRefFuncConst(type);
     }
@@ -3089,13 +3093,14 @@ HeapType TranslateToFuzzReader::getSubType(HeapType type) {
       case HeapType::func:
         // TODO: Typed function references.
         return HeapType::func;
+      case HeapType::ext:
+        return HeapType::ext;
       case HeapType::any:
         // TODO: nontrivial types as well.
         return pick(
           FeatureOptions<HeapType>()
-            .add(FeatureSet::ReferenceTypes, HeapType::func, HeapType::any)
+            .add(FeatureSet::ReferenceTypes, HeapType::func /*, HeapType::ext*/)
             .add(FeatureSet::ReferenceTypes | FeatureSet::GC,
-                 HeapType::func,
                  HeapType::any,
                  HeapType::eq,
                  HeapType::i31,
diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp
index 364065b8b..5a8f0fc0e 100644
--- a/src/tools/fuzzing/heap-types.cpp
+++ b/src/tools/fuzzing/heap-types.cpp
@@ -153,6 +153,7 @@ struct HeapTypeGeneratorImpl {
 
   HeapType::BasicHeapType generateBasicHeapType() {
     return rand.pick(HeapType::func,
+                     HeapType::ext,
                      HeapType::any,
                      HeapType::eq,
                      HeapType::i31,
@@ -278,6 +279,7 @@ struct HeapTypeGeneratorImpl {
       return type;
     } else {
       switch (type) {
+        case HeapType::ext:
         case HeapType::i31:
           // No other subtypes.
           return type;
@@ -371,6 +373,8 @@ struct HeapTypeGeneratorImpl {
       // This is not a constructed type, so it must be a basic type.
       assert(type.isBasic());
       switch (type.getBasic()) {
+        case HeapType::ext:
+          return HeapType::ext;
         case HeapType::func:
           return pickSubFunc();
         case HeapType::any:
@@ -477,16 +481,31 @@ struct HeapTypeGeneratorImpl {
       switch (*basic) {
         case HeapType::func:
           return SignatureKind{};
+        case HeapType::ext:
         case HeapType::i31:
           return super;
         case HeapType::any:
-          return generateHeapTypeKind();
+          if (rand.oneIn(4)) {
+            switch (rand.upTo(3)) {
+              case 0:
+                return HeapType::eq;
+              case 1:
+                return HeapType::i31;
+              case 2:
+                return HeapType::data;
+            }
+          }
+          return DataKind{};
         case HeapType::eq:
           if (rand.oneIn(4)) {
-            return HeapType::i31;
-          } else {
-            return DataKind{};
+            switch (rand.upTo(2)) {
+              case 0:
+                return HeapType::i31;
+              case 1:
+                return HeapType::data;
+            }
           }
+          return DataKind{};
         case HeapType::data:
           return DataKind{};
         case HeapType::string:
diff --git a/src/tools/wasm-fuzz-types.cpp b/src/tools/wasm-fuzz-types.cpp
index d80c89ea8..bbf4967e3 100644
--- a/src/tools/wasm-fuzz-types.cpp
+++ b/src/tools/wasm-fuzz-types.cpp
@@ -152,46 +152,72 @@ void Fuzzer::checkLUBs() const {
       HeapType a = types[i], b = types[j];
       // Check that their LUB is stable when calculated multiple times and in
       // reverse order.
-      HeapType lub = HeapType::getLeastUpperBound(a, b);
-      if (lub != HeapType::getLeastUpperBound(b, a) ||
-          lub != HeapType::getLeastUpperBound(a, b)) {
-        Fatal() << "Could not calculate a stable LUB of HeapTypes " << i
-                << " and " << j << "!\n"
-                << i << ": " << a << "\n"
-                << j << ": " << b << "\n";
-      }
-      // Check that each type is a subtype of the LUB.
-      if (!HeapType::isSubType(a, lub)) {
-        Fatal() << "HeapType " << i
-                << " is not a subtype of its LUB with HeapType " << j << "!\n"
-                << i << ": " << a << "\n"
-                << j << ": " << b << "\n"
-                << "lub: " << lub << "\n";
-      }
-      if (!HeapType::isSubType(b, lub)) {
-        Fatal() << "HeapType " << j
-                << " is not a subtype of its LUB with HeapType " << i << "!\n"
-                << i << ": " << a << "\n"
-                << j << ": " << b << "\n"
-                << "lub: " << lub << "\n";
-      }
-      // Check that the LUB of each type and the original LUB is still the
-      // original LUB.
-      if (lub != HeapType::getLeastUpperBound(a, lub)) {
-        Fatal() << "The LUB of HeapType " << i << " and HeapType " << j
-                << " should be the LUB of itself and HeapType " << i
-                << ", but it is not!\n"
-                << i << ": " << a << "\n"
-                << j << ": " << b << "\n"
-                << "lub: " << lub << "\n";
-      }
-      if (lub != HeapType::getLeastUpperBound(lub, b)) {
-        Fatal() << "The LUB of HeapType " << i << " and HeapType " << j
-                << " should be the LUB of itself and HeapType " << j
-                << ", but it is not!\n"
-                << i << ": " << a << "\n"
-                << j << ": " << b << "\n"
-                << "lub: " << lub << "\n";
+      auto lub = HeapType::getLeastUpperBound(a, b);
+      if (lub) {
+        if (lub != HeapType::getLeastUpperBound(b, a) ||
+            lub != HeapType::getLeastUpperBound(a, b)) {
+          Fatal() << "Could not calculate a stable LUB of HeapTypes " << i
+                  << " and " << j << "!\n"
+                  << i << ": " << a << "\n"
+                  << j << ": " << b << "\n";
+        }
+        // Check that each type is a subtype of the LUB.
+        if (!HeapType::isSubType(a, *lub)) {
+          Fatal() << "HeapType " << i
+                  << " is not a subtype of its LUB with HeapType " << j << "!\n"
+                  << i << ": " << a << "\n"
+                  << j << ": " << b << "\n"
+                  << "lub: " << *lub << "\n";
+        }
+        if (!HeapType::isSubType(b, *lub)) {
+          Fatal() << "HeapType " << j
+                  << " is not a subtype of its LUB with HeapType " << i << "!\n"
+                  << i << ": " << a << "\n"
+                  << j << ": " << b << "\n"
+                  << "lub: " << *lub << "\n";
+        }
+        // Check that the LUB of each type and the original LUB is still the
+        // original LUB.
+        if (lub != HeapType::getLeastUpperBound(a, *lub)) {
+          Fatal() << "The LUB of HeapType " << i << " and HeapType " << j
+                  << " should be the LUB of itself and HeapType " << i
+                  << ", but it is not!\n"
+                  << i << ": " << a << "\n"
+                  << j << ": " << b << "\n"
+                  << "lub: " << *lub << "\n";
+        }
+        if (lub != HeapType::getLeastUpperBound(*lub, b)) {
+          Fatal() << "The LUB of HeapType " << i << " and HeapType " << j
+                  << " should be the LUB of itself and HeapType " << j
+                  << ", but it is not!\n"
+                  << i << ": " << a << "\n"
+                  << j << ": " << b << "\n"
+                  << "lub: " << *lub << "\n";
+        }
+      } else {
+        // No LUB. Check that this is symmetrical.
+        if (auto lub2 = HeapType::getLeastUpperBound(b, a)) {
+          Fatal() << "There is no LUB of HeapType " << i << " and HeapType "
+                  << j << ", but there is a LUB in the reverse direction!\n"
+                  << i << ": " << a << "\n"
+                  << j << ": " << b << "\n"
+                  << "lub: " << *lub2 << "\n";
+        }
+        // There also shouldn't be a subtype relation in this case.
+        if (HeapType::isSubType(a, b)) {
+          Fatal() << "There is no LUB of HeapType " << i << " and HeapType "
+                  << j << ", but HeapType " << i << " is a subtype of HeapType "
+                  << j << "!\n"
+                  << i << ": " << a << "\n"
+                  << j << ": " << b << "\n";
+        }
+        if (HeapType::isSubType(b, a)) {
+          Fatal() << "There is no LUB of HeapType " << i << " and HeapType "
+                  << j << ", but HeapType " << j << " is a subtype of HeapType "
+                  << i << "!\n"
+                  << i << ": " << a << "\n"
+                  << j << ": " << b << "\n";
+        }
       }
     }
   }
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index 9424f6fda..aef1767bb 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -363,8 +363,10 @@ enum EncodedType {
   i16 = -0x7,  // 0x79
   // function reference type
   funcref = -0x10, // 0x70
-  // top type of references, including host references
-  anyref = -0x11, // 0x6f
+  // external (host) references
+  externref = -0x11, // 0x6f
+  // top type of references to non-function Wasm data.
+  anyref = -0x12, // 0x6e
   // comparable reference type
   eqref = -0x13, // 0x6d
   // nullable typed function reference type, with parameter
@@ -396,7 +398,8 @@ enum EncodedType {
 
 enum EncodedHeapType {
   func = -0x10,   // 0x70
-  any = -0x11,    // 0x6f
+  ext = -0x11,    // 0x6f
+  any = -0x12,    // 0x6e
   eq = -0x13,     // 0x6d
   i31 = -0x16,    // 0x6a
   data = -0x19,   // 0x67
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 014e28646..7235cda8b 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -316,6 +316,7 @@ class HeapType {
 
 public:
   enum BasicHeapType : uint32_t {
+    ext,
     func,
     any,
     eq,
@@ -398,8 +399,8 @@ public:
   // exists.
   std::vector<HeapType> getReferencedHeapTypes() const;
 
-  // Return the LUB of two HeapTypes. The LUB always exists.
-  static HeapType getLeastUpperBound(HeapType a, HeapType b);
+  // Return the LUB of two HeapTypes, which may or may not exist.
+  static std::optional<HeapType> getLeastUpperBound(HeapType a, HeapType b);
 
   // Helper allowing the value of `print(...)` to be sent to an ostream. Stores
   // a `TypeID` because `Type` is incomplete at this point and using a reference
diff --git a/src/wasm/literal.cpp b/src/wasm/literal.cpp
index 05f9d93d5..684108581 100644
--- a/src/wasm/literal.cpp
+++ b/src/wasm/literal.cpp
@@ -101,6 +101,7 @@ Literal::Literal(const Literal& other) : type(other.type) {
     auto heapType = type.getHeapType();
     if (heapType.isBasic()) {
       switch (heapType.getBasic()) {
+        case HeapType::ext:
         case HeapType::any:
         case HeapType::eq:
           return; // null
@@ -464,6 +465,10 @@ std::ostream& operator<<(std::ostream& o, Literal literal) {
       }
     } else {
       switch (literal.type.getHeapType().getBasic()) {
+        case HeapType::ext:
+          assert(literal.isNull() && "unexpected non-null externref literal");
+          o << "externref(null)";
+          break;
         case HeapType::any:
           assert(literal.isNull() && "unexpected non-null anyref literal");
           o << "anyref(null)";
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index 7008d185c..fe827f291 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -1368,6 +1368,9 @@ void WasmBinaryWriter::writeType(Type type) {
     auto heapType = type.getHeapType();
     if (heapType.isBasic() && type.isNullable()) {
       switch (heapType.getBasic()) {
+        case HeapType::ext:
+          o << S32LEB(BinaryConsts::EncodedType::externref);
+          return;
         case HeapType::any:
           o << S32LEB(BinaryConsts::EncodedType::anyref);
           return;
@@ -1443,6 +1446,9 @@ void WasmBinaryWriter::writeHeapType(HeapType type) {
   int ret = 0;
   if (type.isBasic()) {
     switch (type.getBasic()) {
+      case HeapType::ext:
+        ret = BinaryConsts::EncodedHeapType::ext;
+        break;
       case HeapType::func:
         ret = BinaryConsts::EncodedHeapType::func;
         break;
@@ -1805,6 +1811,9 @@ bool WasmBinaryBuilder::getBasicType(int32_t code, Type& out) {
     case BinaryConsts::EncodedType::funcref:
       out = Type(HeapType::func, Nullable);
       return true;
+    case BinaryConsts::EncodedType::externref:
+      out = Type(HeapType::ext, Nullable);
+      return true;
     case BinaryConsts::EncodedType::anyref:
       out = Type(HeapType::any, Nullable);
       return true;
@@ -1839,6 +1848,9 @@ bool WasmBinaryBuilder::getBasicHeapType(int64_t code, HeapType& out) {
     case BinaryConsts::EncodedHeapType::func:
       out = HeapType::func;
       return true;
+    case BinaryConsts::EncodedHeapType::ext:
+      out = HeapType::ext;
+      return true;
     case BinaryConsts::EncodedHeapType::any:
       out = HeapType::any;
       return true;
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 55551ef58..86d7b27e9 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -1169,8 +1169,10 @@ Type SExpressionWasmBuilder::stringToType(const char* str,
   if (strncmp(str, "funcref", 7) == 0 && (prefix || str[7] == 0)) {
     return Type(HeapType::func, Nullable);
   }
-  if ((strncmp(str, "externref", 9) == 0 && (prefix || str[9] == 0)) ||
-      (strncmp(str, "anyref", 6) == 0 && (prefix || str[6] == 0))) {
+  if (strncmp(str, "externref", 9) == 0 && (prefix || str[9] == 0)) {
+    return Type(HeapType::ext, Nullable);
+  }
+  if (strncmp(str, "anyref", 6) == 0 && (prefix || str[6] == 0)) {
     return Type(HeapType::any, Nullable);
   }
   if (strncmp(str, "eqref", 5) == 0 && (prefix || str[5] == 0)) {
@@ -1214,7 +1216,7 @@ HeapType SExpressionWasmBuilder::stringToHeapType(const char* str,
     }
     if (str[1] == 'x' && str[2] == 't' && str[3] == 'e' && str[4] == 'r' &&
         str[5] == 'n' && (prefix || str[6] == 0)) {
-      return HeapType::any;
+      return HeapType::ext;
     }
   }
   if (str[0] == 'a') {
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 23d2877f7..f9ccea9f6 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -172,7 +172,7 @@ struct TypeBounder {
 
   bool hasLeastUpperBound(Type a, Type b);
   Type getLeastUpperBound(Type a, Type b);
-  HeapType getLeastUpperBound(HeapType a, HeapType b);
+  std::optional<HeapType> getLeastUpperBound(HeapType a, HeapType b);
 
 private:
   // Return the LUB iff a LUB was found. The HeapType and Struct overloads are
@@ -181,7 +181,7 @@ private:
   // Note that these methods can return temporary types, so they should never be
   // used directly.
   std::optional<Type> lub(Type a, Type b);
-  HeapType lub(HeapType a, HeapType b);
+  std::optional<HeapType> lub(HeapType a, HeapType b);
   std::optional<Tuple> lub(const Tuple& a, const Tuple& b);
   std::optional<Field> lub(const Field& a, const Field& b);
   std::optional<Signature> lub(const Signature& a, const Signature& b);
@@ -573,8 +573,8 @@ HeapType::BasicHeapType getBasicHeapSupertype(HeapType type) {
   WASM_UNREACHABLE("unexpected kind");
 };
 
-HeapType getBasicHeapTypeLUB(HeapType::BasicHeapType a,
-                             HeapType::BasicHeapType b) {
+std::optional<HeapType> getBasicHeapTypeLUB(HeapType::BasicHeapType a,
+                                            HeapType::BasicHeapType b) {
   if (a == b) {
     return a;
   }
@@ -583,25 +583,27 @@ HeapType getBasicHeapTypeLUB(HeapType::BasicHeapType a,
     std::swap(a, b);
   }
   switch (a) {
+    case HeapType::ext:
+      return {};
     case HeapType::func:
     case HeapType::any:
-      return HeapType::any;
+      return {HeapType::any};
     case HeapType::eq:
       if (b == HeapType::i31 || b == HeapType::data) {
-        return HeapType::eq;
+        return {HeapType::eq};
       }
-      return HeapType::any;
+      return {HeapType::any};
     case HeapType::i31:
       if (b == HeapType::data) {
-        return HeapType::eq;
+        return {HeapType::eq};
       }
-      return HeapType::any;
+      return {HeapType::any};
     case HeapType::data:
     case HeapType::string:
     case HeapType::stringview_wtf8:
     case HeapType::stringview_wtf16:
     case HeapType::stringview_iter:
-      return HeapType::any;
+      return {HeapType::any};
   }
   WASM_UNREACHABLE("unexpected basic type");
 }
@@ -1205,11 +1207,12 @@ Type Type::getLeastUpperBound(Type a, Type b) {
     return Type(elems);
   }
   if (a.isRef() && b.isRef()) {
-    auto nullability =
-      (a.isNullable() || b.isNullable()) ? Nullable : NonNullable;
-    auto heapType =
-      HeapType::getLeastUpperBound(a.getHeapType(), b.getHeapType());
-    return Type(heapType, nullability);
+    if (auto heapType =
+          HeapType::getLeastUpperBound(a.getHeapType(), b.getHeapType())) {
+      auto nullability =
+        (a.isNullable() || b.isNullable()) ? Nullable : NonNullable;
+      return Type(*heapType, nullability);
+    }
   }
   return Type::none;
   WASM_UNREACHABLE("unexpected type");
@@ -1411,7 +1414,7 @@ std::vector<HeapType> HeapType::getReferencedHeapTypes() const {
   return types;
 }
 
-HeapType HeapType::getLeastUpperBound(HeapType a, HeapType b) {
+std::optional<HeapType> HeapType::getLeastUpperBound(HeapType a, HeapType b) {
   if (a == b) {
     return a;
   }
@@ -1616,10 +1619,13 @@ bool SubTyper::isSubType(HeapType a, HeapType b) {
   }
   if (b.isBasic()) {
     switch (b.getBasic()) {
+      case HeapType::ext:
+        return a == HeapType::ext;
       case HeapType::func:
         return a.isSignature();
       case HeapType::any:
-        return true;
+        // TODO: exclude functions as well.
+        return a != HeapType::ext;
       case HeapType::eq:
         return a == HeapType::i31 || a.isData();
       case HeapType::i31:
@@ -1735,8 +1741,13 @@ Type TypeBounder::getLeastUpperBound(Type a, Type b) {
   return built.back().getArray().element.type;
 }
 
-HeapType TypeBounder::getLeastUpperBound(HeapType a, HeapType b) {
-  HeapType l = lub(a, b);
+std::optional<HeapType> TypeBounder::getLeastUpperBound(HeapType a,
+                                                        HeapType b) {
+  auto maybeLub = lub(a, b);
+  if (!maybeLub) {
+    return std::nullopt;
+  }
+  HeapType l = *maybeLub;
   if (!isTemp(l)) {
     // The LUB is already canonical, so we're done.
     return l;
@@ -1767,15 +1778,16 @@ std::optional<Type> TypeBounder::lub(Type a, Type b) {
     }
     return builder.getTempTupleType(*tuple);
   } else if (a.isRef() && b.isRef()) {
-    auto nullability =
-      (a.isNullable() || b.isNullable()) ? Nullable : NonNullable;
-    HeapType heapType = lub(a.getHeapType(), b.getHeapType());
-    return builder.getTempRefType(heapType, nullability);
+    if (auto heapType = lub(a.getHeapType(), b.getHeapType())) {
+      auto nullability =
+        (a.isNullable() || b.isNullable()) ? Nullable : NonNullable;
+      return builder.getTempRefType(*heapType, nullability);
+    }
   }
   return {};
 }
 
-HeapType TypeBounder::lub(HeapType a, HeapType b) {
+std::optional<HeapType> TypeBounder::lub(HeapType a, HeapType b) {
   if (a == b) {
     return a;
   }
@@ -1999,6 +2011,8 @@ std::ostream& TypePrinter::print(Type type) {
 std::ostream& TypePrinter::print(HeapType type) {
   if (type.isBasic()) {
     switch (type.getBasic()) {
+      case HeapType::ext:
+        return os << "extern";
       case HeapType::func:
         return os << "func";
       case HeapType::any:
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index 92f6c76bf..e837c2dd6 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -3099,7 +3099,7 @@ static void validateTables(Module& module, ValidationInfo& info) {
     }
   }
 
-  Type anyref = Type(HeapType::any, Nullable);
+  Type externref = Type(HeapType::ext, Nullable);
   Type funcref = Type(HeapType::func, Nullable);
   for (auto& table : module.tables) {
     info.shouldBeTrue(table->initial <= table->max,
@@ -3110,15 +3110,15 @@ static void validateTables(Module& module, ValidationInfo& info) {
       "table",
       "Non-nullable reference types are not yet supported for tables");
     if (!module.features.hasGC()) {
-      info.shouldBeTrue(table->type.isFunction() || table->type == anyref,
+      info.shouldBeTrue(table->type.isFunction() || table->type == externref,
                         "table",
                         "Only function reference types or externref are valid "
                         "for table type (when GC is disabled)");
     }
     if (!module.features.hasTypedFunctionReferences()) {
-      info.shouldBeTrue(table->type == funcref || table->type == anyref,
+      info.shouldBeTrue(table->type == funcref || table->type == externref,
                         "table",
-                        "Only funcref and anyref are valid for table type "
+                        "Only funcref and externref are valid for table type "
                         "(when typed-function references are disabled)");
     }
   }
diff --git a/src/wasm/wat-parser.cpp b/src/wasm/wat-parser.cpp
index 89eab3297..5455c0438 100644
--- a/src/wasm/wat-parser.cpp
+++ b/src/wasm/wat-parser.cpp
@@ -431,7 +431,7 @@ template<typename Ctx> struct TypeParserCtx {
 
   HeapTypeT makeFunc() { return HeapType::func; }
   HeapTypeT makeAny() { return HeapType::any; }
-  HeapTypeT makeExtern() { return HeapType::any; }
+  HeapTypeT makeExtern() { return HeapType::ext; }
   HeapTypeT makeEq() { return HeapType::eq; }
   HeapTypeT makeI31() { return HeapType::i31; }
   HeapTypeT makeData() { return HeapType::data; }