summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ir/module-splitting.cpp13
-rw-r--r--src/ir/module-utils.h7
-rw-r--r--src/passes/Print.cpp245
-rw-r--r--src/support/hash.h13
-rw-r--r--src/wasm-type.h14
-rw-r--r--src/wasm/wasm-type.cpp451
6 files changed, 453 insertions, 290 deletions
diff --git a/src/ir/module-splitting.cpp b/src/ir/module-splitting.cpp
index b8abbb42e..7215629e4 100644
--- a/src/ir/module-splitting.cpp
+++ b/src/ir/module-splitting.cpp
@@ -80,19 +80,6 @@
#include "wasm-builder.h"
#include "wasm.h"
-namespace std {
-
-// Used in ModuleSplitter::shareImportableItems
-template<> struct hash<pair<wasm::ExternalKind, wasm::Name>> {
- size_t operator()(const pair<wasm::ExternalKind, wasm::Name>& p) const {
- auto digest = wasm::hash(p.first);
- wasm::rehash(digest, p.second);
- return digest;
- }
-};
-
-} // namespace std
-
namespace wasm {
namespace ModuleSplitting {
diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h
index 84ef3a508..4792c5d23 100644
--- a/src/ir/module-utils.h
+++ b/src/ir/module-utils.h
@@ -485,11 +485,8 @@ inline void collectHeapTypes(Module& wasm,
for (auto& curr : wasm.functions) {
counts.note(curr->sig);
for (auto type : curr->vars) {
- counts.maybeNote(type);
- if (type.isTuple()) {
- for (auto t : type) {
- counts.maybeNote(t);
- }
+ for (auto t : type) {
+ counts.maybeNote(t);
}
}
}
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index 445021bcf..8c32642b4 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -67,70 +67,56 @@ static std::ostream& printLocal(Index index, Function* func, std::ostream& o) {
return printName(name, o);
}
-static void printHeapTypeName(std::ostream& os,
- HeapType type,
- Module* wasm = nullptr,
- bool first = true);
+namespace {
+
+// Helper for printing the name of a type. This output is guaranteed to not
+// contain spaces.
+struct TypeNamePrinter {
+ // Optional. If present, the module's HeapType names will be used.
+ Module* wasm;
+
+ // Keep track of the first depth at which we see each HeapType so if we see it
+ // again, we can unambiguously refer to it without infinitely recursing.
+ size_t currHeapTypeDepth = 0;
+ std::unordered_map<HeapType, size_t> heapTypeDepths;
+
+ // The stream we are printing to.
+ std::ostream& os;
+
+ TypeNamePrinter(std::ostream& os, Module* wasm = nullptr)
+ : wasm(wasm), os(os) {}
+
+ void print(Type type);
+ void print(HeapType heapType);
+ void print(const Tuple& tuple);
+ void print(const Field& field);
+ void print(const Signature& sig);
+ void print(const Struct& struct_);
+ void print(const Array& array);
+ void print(const Rtt& rtt);
+};
-// Prints the name of a type. This output is guaranteed to not contain spaces.
-static void printTypeName(std::ostream& os, Type type, Module* wasm = nullptr) {
+void TypeNamePrinter::print(Type type) {
if (type.isBasic()) {
os << type;
- return;
- }
- if (type.isRtt()) {
- auto rtt = type.getRtt();
- os << "rtt_";
- if (rtt.hasDepth()) {
- os << rtt.depth << '_';
- }
- printHeapTypeName(os, rtt.heapType, wasm);
- return;
- }
- if (type.isTuple()) {
- auto sep = "";
- for (auto t : type) {
- os << sep;
- sep = "_";
- printTypeName(os, t, wasm);
- }
- return;
- }
- if (type.isRef()) {
+ } else if (type.isTuple()) {
+ print(type.getTuple());
+ } else if (type.isRtt()) {
+ print(type.getRtt());
+ } else if (type.isRef()) {
os << "ref";
if (type.isNullable()) {
os << "?";
}
- os << "|";
- printHeapTypeName(os, type.getHeapType(), wasm, false);
- os << "|";
- return;
- }
- WASM_UNREACHABLE("unsupported print type");
-}
-
-static void
-printFieldName(std::ostream& os, const Field& field, Module* wasm = nullptr) {
- if (field.mutable_) {
- os << "mut:";
- }
- if (field.type == Type::i32 && field.packedType != Field::not_packed) {
- if (field.packedType == Field::i8) {
- os << "i8";
- } else if (field.packedType == Field::i16) {
- os << "i16";
- } else {
- WASM_UNREACHABLE("invalid packed type");
- }
+ os << '|';
+ print(type.getHeapType());
+ os << '|';
} else {
- printTypeName(os, field.type, wasm);
+ WASM_UNREACHABLE("unexpected type");
}
}
-// Prints the name of a heap type. As with printTypeName, this output is
-// guaranteed to not contain spaces.
-static void
-printHeapTypeName(std::ostream& os, HeapType type, Module* wasm, bool first) {
+void TypeNamePrinter::print(HeapType type) {
if (type.isBasic()) {
os << type;
return;
@@ -144,37 +130,104 @@ printHeapTypeName(std::ostream& os, HeapType type, Module* wasm, bool first) {
os << '$' << wasm->typeNames[type].name;
return;
}
- if (first) {
- os << '$';
+ // If we have seen this HeapType before, just print its relative depth instead
+ // of infinitely recursing.
+ auto it = heapTypeDepths.find(type);
+ if (it != heapTypeDepths.end()) {
+ assert(it->second <= currHeapTypeDepth);
+ size_t relativeDepth = currHeapTypeDepth - it->second;
+ os << "..." << relativeDepth;
+ return;
+ }
+
+ // If this is the top-level heap type, add a $
+ if (currHeapTypeDepth == 0) {
+ os << "$";
}
+
+ // Update the context for the current HeapType before recursing.
+ heapTypeDepths[type] = ++currHeapTypeDepth;
+
if (type.isSignature()) {
- auto sig = type.getSignature();
- printTypeName(os, sig.params, wasm);
- if (first) {
- os << "_=>_";
- } else {
- os << "_->_";
- }
- printTypeName(os, sig.results, wasm);
+ print(type.getSignature());
} else if (type.isStruct()) {
- auto struct_ = type.getStruct();
- os << "{";
- auto sep = "";
- for (auto& field : struct_.fields) {
- os << sep;
- sep = "_";
- printFieldName(os, field, wasm);
- }
- os << "}";
+ print(type.getStruct());
} else if (type.isArray()) {
- os << "[";
- printFieldName(os, type.getArray().element, wasm);
- os << "]";
+ print(type.getArray());
} else {
- os << type;
+ WASM_UNREACHABLE("unexpected type");
+ }
+
+ // Restore the previous context after the recursion.
+ heapTypeDepths.erase(type);
+ --currHeapTypeDepth;
+}
+
+void TypeNamePrinter::print(const Tuple& tuple) {
+ auto sep = "";
+ for (auto type : tuple.types) {
+ os << sep;
+ sep = "_";
+ print(type);
}
}
+void TypeNamePrinter::print(const Field& field) {
+ if (field.mutable_) {
+ os << "mut:";
+ }
+ if (field.type == Type::i32 && field.packedType != Field::not_packed) {
+ if (field.packedType == Field::i8) {
+ os << "i8";
+ } else if (field.packedType == Field::i16) {
+ os << "i16";
+ } else {
+ WASM_UNREACHABLE("invalid packed type");
+ }
+ } else {
+ print(field.type);
+ }
+}
+
+void TypeNamePrinter::print(const Signature& sig) {
+ // TODO: Switch to using an unambiguous delimiter rather than differentiating
+ // only the top level with a different arrow.
+ print(sig.params);
+ if (currHeapTypeDepth == 1) {
+ os << "_=>_";
+ } else {
+ os << "_->_";
+ }
+ print(sig.results);
+}
+
+void TypeNamePrinter::print(const Struct& struct_) {
+ os << '{';
+ auto sep = "";
+ for (const auto& field : struct_.fields) {
+ os << sep;
+ sep = "_";
+ print(field);
+ }
+ os << '}';
+}
+
+void TypeNamePrinter::print(const Array& array) {
+ os << '[';
+ print(array.element);
+ os << ']';
+}
+
+void TypeNamePrinter::print(const Rtt& rtt) {
+ os << "rtt_";
+ if (rtt.hasDepth()) {
+ os << rtt.depth << '_';
+ }
+ print(rtt.heapType);
+}
+
+} // anonymous namespace
+
// Unlike the default format, tuple types in s-expressions should not have
// commas.
struct SExprType {
@@ -186,7 +239,9 @@ static std::ostream& printSExprType(std::ostream& o,
const SExprType& sType,
Module* wasm = nullptr) {
Type type = sType.type;
- if (type.isTuple()) {
+ if (type.isBasic()) {
+ o << type;
+ } else if (type.isTuple()) {
o << '(';
auto sep = "";
for (const auto& t : type) {
@@ -201,17 +256,17 @@ static std::ostream& printSExprType(std::ostream& o,
if (rtt.hasDepth()) {
o << rtt.depth << ' ';
}
- printHeapTypeName(o, rtt.heapType, wasm);
+ TypeNamePrinter(o, wasm).print(rtt.heapType);
o << ')';
} else if (type.isRef() && !type.isBasic()) {
o << "(ref ";
if (type.isNullable()) {
o << "null ";
}
- printHeapTypeName(o, type.getHeapType(), wasm);
+ TypeNamePrinter(o, wasm).print(type.getHeapType());
o << ')';
} else {
- printTypeName(o, sType.type, wasm);
+ WASM_UNREACHABLE("unexpected type");
}
return o;
}
@@ -356,7 +411,7 @@ struct PrintExpressionContents
o << '(';
printMinor(o, "type ");
- printHeapTypeName(o, curr->sig, wasm);
+ TypeNamePrinter(o, wasm).print(HeapType(curr->sig));
o << ')';
}
void visitLocalGet(LocalGet* curr) {
@@ -1793,7 +1848,7 @@ struct PrintExpressionContents
void visitMemoryGrow(MemoryGrow* curr) { printMedium(o, "memory.grow"); }
void visitRefNull(RefNull* curr) {
printMedium(o, "ref.null ");
- printHeapTypeName(o, curr->type.getHeapType(), wasm);
+ TypeNamePrinter(o, wasm).print(curr->type.getHeapType());
}
void visitRefIs(RefIs* curr) {
switch (curr->op) {
@@ -1864,11 +1919,11 @@ struct PrintExpressionContents
}
void visitRefTest(RefTest* curr) {
printMedium(o, "ref.test ");
- printHeapTypeName(o, curr->getCastType().getHeapType(), wasm);
+ TypeNamePrinter(o, wasm).print(curr->getCastType().getHeapType());
}
void visitRefCast(RefCast* curr) {
printMedium(o, "ref.cast ");
- printHeapTypeName(o, curr->getCastType().getHeapType(), wasm);
+ TypeNamePrinter(o, wasm).print(curr->getCastType().getHeapType());
}
void visitBrOn(BrOn* curr) {
switch (curr->op) {
@@ -1894,11 +1949,11 @@ struct PrintExpressionContents
}
void visitRttCanon(RttCanon* curr) {
printMedium(o, "rtt.canon ");
- printHeapTypeName(o, curr->type.getRtt().heapType, wasm);
+ TypeNamePrinter(o, wasm).print(curr->type.getRtt().heapType);
}
void visitRttSub(RttSub* curr) {
printMedium(o, "rtt.sub ");
- printHeapTypeName(o, curr->type.getRtt().heapType, wasm);
+ TypeNamePrinter(o, wasm).print(curr->type.getRtt().heapType);
}
void visitStructNew(StructNew* curr) {
printMedium(o, "struct.new_");
@@ -1906,7 +1961,7 @@ struct PrintExpressionContents
o << "default_";
}
o << "with_rtt ";
- printHeapTypeName(o, curr->rtt->type.getHeapType(), wasm);
+ TypeNamePrinter(o, wasm).print(curr->rtt->type.getHeapType());
}
void printUnreachableReplacement() {
// If we cannot print a valid unreachable instruction (say, a struct.get,
@@ -1940,7 +1995,7 @@ struct PrintExpressionContents
} else {
printMedium(o, "struct.get ");
}
- printHeapTypeName(o, heapType, wasm);
+ TypeNamePrinter(o, wasm).print(heapType);
o << ' ';
printFieldName(heapType, curr->index);
}
@@ -1951,7 +2006,7 @@ struct PrintExpressionContents
}
printMedium(o, "struct.set ");
auto heapType = curr->ref->type.getHeapType();
- printHeapTypeName(o, heapType, wasm);
+ TypeNamePrinter(o, wasm).print(heapType);
o << ' ';
printFieldName(heapType, curr->index);
}
@@ -1961,7 +2016,7 @@ struct PrintExpressionContents
o << "default_";
}
o << "with_rtt ";
- printHeapTypeName(o, curr->rtt->type.getHeapType(), wasm);
+ TypeNamePrinter(o, wasm).print(curr->rtt->type.getHeapType());
}
void visitArrayGet(ArrayGet* curr) {
const auto& element = curr->ref->type.getHeapType().getArray().element;
@@ -1974,15 +2029,15 @@ struct PrintExpressionContents
} else {
printMedium(o, "array.get ");
}
- printHeapTypeName(o, curr->ref->type.getHeapType(), wasm);
+ TypeNamePrinter(o, wasm).print(curr->ref->type.getHeapType());
}
void visitArraySet(ArraySet* curr) {
printMedium(o, "array.set ");
- printHeapTypeName(o, curr->ref->type.getHeapType(), wasm);
+ TypeNamePrinter(o, wasm).print(curr->ref->type.getHeapType());
}
void visitArrayLen(ArrayLen* curr) {
printMedium(o, "array.len ");
- printHeapTypeName(o, curr->ref->type.getHeapType(), wasm);
+ TypeNamePrinter(o, wasm).print(curr->ref->type.getHeapType());
}
void visitRefAs(RefAs* curr) {
switch (curr->op) {
@@ -3251,7 +3306,7 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
doIndent(o, indent);
o << '(';
printMedium(o, "type") << ' ';
- printHeapTypeName(o, type, curr);
+ TypeNamePrinter(o, curr).print(type);
o << ' ';
handleHeapType(type);
o << ")" << maybeNewLine;
@@ -3432,7 +3487,7 @@ printStackInst(StackInst* inst, std::ostream& o, Function* func) {
case StackInst::TryEnd: {
printMedium(o, "end");
o << " ;; type: ";
- printTypeName(o, inst->type);
+ TypeNamePrinter(o).print(inst->type);
break;
}
case StackInst::IfElse: {
diff --git a/src/support/hash.h b/src/support/hash.h
index 1af462b7e..d3a858698 100644
--- a/src/support/hash.h
+++ b/src/support/hash.h
@@ -50,4 +50,17 @@ template<typename T> inline void rehash(std::size_t& digest, const T& value) {
} // namespace wasm
+namespace std {
+
+// Hashing pairs is often useful
+template<typename T1, typename T2> struct hash<pair<T1, T2>> {
+ size_t operator()(const pair<T1, T2>& p) const {
+ auto digest = wasm::hash(p.first);
+ wasm::rehash(digest, p.second);
+ return digest;
+ }
+};
+
+} // namespace std
+
#endif // wasm_support_hash_h
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 3dcd53d0e..d0008d357 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -171,7 +171,7 @@ public:
bool operator!=(const Type& other) const { return id != other.id; }
bool operator!=(const BasicType& other) const { return id != other; }
- // Order types by some notion of simplicity
+ // Order types by some notion of simplicity.
bool operator<(const Type& other) const;
// Returns the type size in bytes. Only single types are supported.
@@ -184,6 +184,10 @@ public:
// Returns the feature set required to use this type.
FeatureSet getFeatures() const;
+ // Returns the tuple, assuming that this is a tuple type. Note that it is
+ // normally simpler to use operator[] and size() on the Type directly.
+ const Tuple& getTuple() const;
+
// Gets the heap type corresponding to this type, assuming that it is a
// reference or Rtt type.
HeapType getHeapType() const;
@@ -349,6 +353,7 @@ public:
bool operator!=(const HeapType& other) const { return id != other.id; }
bool operator!=(const BasicHeapType& other) const { return id != other; }
+ // Order heap types by some notion of simplicity.
bool operator<(const HeapType& other) const;
std::string toString() const;
@@ -368,7 +373,6 @@ struct Tuple {
Tuple(TypeList&& types) : types(std::move(types)) { validate(); }
bool operator==(const Tuple& other) const { return types == other.types; }
bool operator!=(const Tuple& other) const { return !(*this == other); }
- bool operator<(const Tuple& other) const { return types < other.types; }
std::string toString() const;
// Prevent accidental copies
@@ -424,7 +428,6 @@ struct Field {
mutable_ == other.mutable_;
}
bool operator!=(const Field& other) const { return !(*this == other); }
- bool operator<(const Field& other) const;
std::string toString() const;
};
@@ -439,7 +442,6 @@ struct Struct {
Struct(FieldList&& fields) : fields(std::move(fields)) {}
bool operator==(const Struct& other) const { return fields == other.fields; }
bool operator!=(const Struct& other) const { return !(*this == other); }
- bool operator<(const Struct& other) const { return fields < other.fields; }
std::string toString() const;
// Prevent accidental copies
@@ -452,7 +454,6 @@ struct Array {
Array(Field element) : element(element) {}
bool operator==(const Array& other) const { return element == other.element; }
bool operator!=(const Array& other) const { return !(*this == other); }
- bool operator<(const Array& other) const { return element < other.element; }
std::string toString() const;
};
@@ -467,8 +468,7 @@ struct Rtt {
return depth == other.depth && heapType == other.heapType;
}
bool operator!=(const Rtt& other) const { return !(*this == other); }
- bool operator<(const Rtt& other) const;
- bool hasDepth() { return depth != uint32_t(NoDepth); }
+ bool hasDepth() const { return depth != uint32_t(NoDepth); }
std::string toString() const;
};
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index b920dd587..a2132d09a 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -64,7 +64,6 @@ struct TypeInfo {
bool operator==(const TypeInfo& other) const;
bool operator!=(const TypeInfo& other) const { return !(*this == other); }
- bool operator<(const TypeInfo& other) const;
};
struct HeapTypeInfo {
@@ -96,7 +95,41 @@ struct HeapTypeInfo {
HeapTypeInfo& operator=(const HeapTypeInfo& other);
bool operator==(const HeapTypeInfo& other) const;
bool operator!=(const HeapTypeInfo& other) const { return !(*this == other); }
- bool operator<(const HeapTypeInfo& other) const;
+};
+
+// Helper for coinductively comparing Types and HeapTypes according to some
+// arbitrary notion of complexity.
+struct TypeComparator {
+ // Set of HeapTypes we are assuming satisfy the relation as long as we cannot
+ // prove otherwise.
+ std::unordered_set<std::pair<HeapType, HeapType>> seen;
+ bool lessThan(Type a, Type b);
+ bool lessThan(HeapType a, HeapType b);
+ bool lessThan(const TypeInfo& a, const TypeInfo& b);
+ bool lessThan(const HeapTypeInfo& a, const HeapTypeInfo& b);
+ bool lessThan(const Tuple& a, const Tuple& b);
+ bool lessThan(const Field& a, const Field& b);
+ bool lessThan(const Signature& a, const Signature& b);
+ bool lessThan(const Struct& a, const Struct& b);
+ bool lessThan(const Array& a, const Array& b);
+ bool lessThan(const Rtt& a, const Rtt& b);
+};
+
+// Helper for coinductively checking whether a pair of Types or HeapTypes are in
+// a subtype relation.
+struct SubTyper {
+ // Set of HeapTypes we are assuming satisfy the relation as long as we cannot
+ // prove otherwise.
+ std::unordered_set<std::pair<HeapType, HeapType>> seen;
+ bool isSubType(Type a, Type b);
+ bool isSubType(HeapType a, HeapType b);
+ bool isSubType(const Tuple& a, const Tuple& b);
+ bool isSubType(const Field& a, const Field& b);
+ bool isSubType(const HeapTypeInfo& a, const HeapTypeInfo& b);
+ bool isSubType(const Signature& a, const Signature& b);
+ bool isSubType(const Struct& a, const Struct& b);
+ bool isSubType(const Array& a, const Array& b);
+ bool isSubType(const Rtt& a, const Rtt& b);
};
} // anonymous namespace
@@ -176,24 +209,6 @@ bool TypeInfo::operator==(const TypeInfo& other) const {
WASM_UNREACHABLE("unexpected kind");
}
-bool TypeInfo::operator<(const TypeInfo& other) const {
- if (kind != other.kind) {
- return kind < other.kind;
- }
- switch (kind) {
- case TupleKind:
- return tuple < other.tuple;
- case RefKind:
- if (ref.nullable != other.ref.nullable) {
- return ref.nullable < other.ref.nullable;
- }
- return ref.heapType < other.ref.heapType;
- case RttKind:
- return rtt < other.rtt;
- }
- WASM_UNREACHABLE("unexpected kind");
-}
-
HeapTypeInfo::HeapTypeInfo(const HeapTypeInfo& other) {
kind = other.kind;
switch (kind) {
@@ -248,21 +263,6 @@ bool HeapTypeInfo::operator==(const HeapTypeInfo& other) const {
WASM_UNREACHABLE("unexpected kind");
}
-bool HeapTypeInfo::operator<(const HeapTypeInfo& other) const {
- if (kind != other.kind) {
- return kind < other.kind;
- }
- switch (kind) {
- case SignatureKind:
- return signature < other.signature;
- case StructKind:
- return struct_ < other.struct_;
- case ArrayKind:
- return array < other.array;
- }
- WASM_UNREACHABLE("unexpected kind");
-}
-
template<typename Info> struct Store {
std::mutex mutex;
@@ -423,20 +423,8 @@ bool Type::isDefaultable() const {
}
bool Type::operator<(const Type& other) const {
- if (*this == other) {
- return false;
- }
- if (isBasic() && other.isBasic()) {
- return getBasic() < other.getBasic();
- }
- if (isBasic()) {
- return true;
- }
- if (other.isBasic()) {
- return false;
- }
- return *getTypeInfo(*this) < *getTypeInfo(other);
-};
+ return TypeComparator().lessThan(*this, other);
+}
unsigned Type::getByteSize() const {
// TODO: alignment?
@@ -536,6 +524,11 @@ FeatureSet Type::getFeatures() const {
return getSingleFeatures(*this);
}
+const Tuple& Type::getTuple() const {
+ assert(isTuple());
+ return getTypeInfo(*this)->tuple;
+}
+
HeapType Type::getHeapType() const {
if (isBasic()) {
switch (getBasic()) {
@@ -597,39 +590,7 @@ Type Type::get(unsigned byteSize, bool float_) {
}
bool Type::isSubType(Type left, Type right) {
- if (left == right) {
- return true;
- }
- if (left.isRef() && right.isRef()) {
- // Consider HeapType subtyping as well, and also that a non-nullable type is
- // potentially a supertype of a nullable one.
- if (HeapType::isSubType(left.getHeapType(), right.getHeapType()) &&
- (left.isNullable() == right.isNullable() || !left.isNullable())) {
- return true;
- }
- return false;
- }
- if (left.isTuple() && right.isTuple()) {
- if (left.size() != right.size()) {
- return false;
- }
- for (size_t i = 0; i < left.size(); ++i) {
- if (!isSubType(left[i], right[i])) {
- return false;
- }
- }
- return true;
- }
- if (left.isRtt() && right.isRtt()) {
- auto leftRtt = left.getRtt();
- auto rightRtt = right.getRtt();
- // (rtt n $x) is a subtype of (rtt $x), that is, if the only difference in
- // information is that the left side specifies a depth while the right side
- // allows any depth.
- return leftRtt.heapType == rightRtt.heapType && leftRtt.hasDepth() &&
- !rightRtt.hasDepth();
- }
- return false;
+ return SubTyper().isSubType(left, right);
}
Type Type::getLeastUpperBound(Type a, Type b) {
@@ -774,19 +735,7 @@ bool HeapType::isArray() const {
}
bool HeapType::operator<(const HeapType& other) const {
- if (*this == other) {
- return false;
- }
- if (isBasic() && other.isBasic()) {
- return getBasic() < other.getBasic();
- }
- if (isBasic()) {
- return true;
- }
- if (other.isBasic()) {
- return false;
- }
- return *getHeapTypeInfo(*this) < *getHeapTypeInfo(other);
+ return TypeComparator().lessThan(*this, other);
}
Signature HeapType::getSignature() const {
@@ -804,85 +753,12 @@ Array HeapType::getArray() const {
return getHeapTypeInfo(*this)->array;
}
-static bool isFieldSubType(const Field& left, const Field& right) {
- if (left == right) {
- return true;
- }
- // Immutable fields can be subtypes.
- if (left.mutable_ == Immutable && right.mutable_ == Immutable) {
- return left.packedType == right.packedType &&
- Type::isSubType(left.type, right.type);
- }
- return false;
-}
-
bool HeapType::isSubType(HeapType left, HeapType right) {
- // See:
- // https://github.com/WebAssembly/function-references/blob/master/proposals/function-references/Overview.md#subtyping
- // https://github.com/WebAssembly/gc/blob/master/proposals/gc/MVP.md#defined-types
- if (left == right) {
- return true;
- }
- // Everything is a subtype of any.
- if (right == HeapType::any) {
- return true;
- }
- // Various things are subtypes of eq.
- if ((left == HeapType::i31 || left.isArray() || left.isStruct()) &&
- right == HeapType::eq) {
- return true;
- }
- // All typed function signatures are subtypes of funcref.
- // Note: signatures may get covariance at some point, but do not yet.
- if (left.isSignature() && right == HeapType::func) {
- return true;
- }
- if (left.isArray() && right.isArray()) {
- auto leftField = left.getArray().element;
- auto rightField = left.getArray().element;
- // Array types support depth subtyping.
- return isFieldSubType(leftField, rightField);
- }
- if (left.isStruct() && right.isStruct()) {
- // Structure types support width and depth subtyping.
- auto leftFields = left.getStruct().fields;
- auto rightFields = left.getStruct().fields;
- // There may be more fields on the left, but not less.
- if (leftFields.size() < rightFields.size()) {
- return false;
- }
- for (size_t i = 0; i < rightFields.size(); i++) {
- if (!isFieldSubType(leftFields[i], rightFields[i])) {
- return false;
- }
- }
- return true;
- }
- return false;
+ return SubTyper().isSubType(left, right);
}
bool Signature::operator<(const Signature& other) const {
- if (results != other.results) {
- return results < other.results;
- }
- return params < other.params;
-}
-
-bool Field::operator<(const Field& other) const {
- if (mutable_ != other.mutable_) {
- return mutable_ < other.mutable_;
- }
- if (type == Type::i32 && other.type == Type::i32) {
- return packedType < other.packedType;
- }
- return type < other.type;
-}
-
-bool Rtt::operator<(const Rtt& other) const {
- if (depth != other.depth) {
- return depth < other.depth;
- }
- return heapType < other.heapType;
+ return TypeComparator().lessThan(*this, other);
}
namespace {
@@ -1087,6 +963,241 @@ std::ostream& operator<<(std::ostream& os, HeapTypeInfo info) {
WASM_UNREACHABLE("unexpected kind");
}
+namespace {
+
+bool TypeComparator::lessThan(Type a, Type b) {
+ if (a == b) {
+ return false;
+ }
+ if (a.isBasic() && b.isBasic()) {
+ return a.getBasic() < b.getBasic();
+ }
+ if (a.isBasic()) {
+ return true;
+ }
+ if (b.isBasic()) {
+ return false;
+ }
+ return lessThan(*getTypeInfo(a), *getTypeInfo(b));
+}
+
+bool TypeComparator::lessThan(HeapType a, HeapType b) {
+ if (a == b) {
+ return false;
+ }
+ if (seen.count({a, b})) {
+ // We weren't able to disprove that a < b since we last saw them, so the
+ // relation holds coinductively.
+ return true;
+ }
+ if (a.isBasic() && b.isBasic()) {
+ return a.getBasic() < b.getBasic();
+ }
+ if (a.isBasic()) {
+ return true;
+ }
+ if (b.isBasic()) {
+ return false;
+ }
+ // As we recurse, we will coinductively assume that a < b unless proven
+ // otherwise.
+ seen.insert({a, b});
+ return lessThan(*getHeapTypeInfo(a), *getHeapTypeInfo(b));
+}
+
+bool TypeComparator::lessThan(const TypeInfo& a, const TypeInfo& b) {
+ if (a.kind != b.kind) {
+ return a.kind < b.kind;
+ }
+ switch (a.kind) {
+ case TypeInfo::TupleKind:
+ return lessThan(a.tuple, b.tuple);
+ case TypeInfo::RefKind:
+ if (a.ref.nullable != b.ref.nullable) {
+ return a.ref.nullable < b.ref.nullable;
+ }
+ return lessThan(a.ref.heapType, b.ref.heapType);
+ case TypeInfo::RttKind:
+ return lessThan(a.rtt, b.rtt);
+ }
+ WASM_UNREACHABLE("unexpected kind");
+}
+
+bool TypeComparator::lessThan(const HeapTypeInfo& a, const HeapTypeInfo& b) {
+ if (a.kind != b.kind) {
+ return a.kind < b.kind;
+ }
+ switch (a.kind) {
+ case HeapTypeInfo::SignatureKind:
+ return lessThan(a.signature, b.signature);
+ case HeapTypeInfo::StructKind:
+ return lessThan(a.struct_, b.struct_);
+ case HeapTypeInfo::ArrayKind:
+ return lessThan(a.array, b.array);
+ }
+ WASM_UNREACHABLE("unexpected kind");
+}
+
+bool TypeComparator::lessThan(const Tuple& a, const Tuple& b) {
+ return std::lexicographical_compare(
+ a.types.begin(),
+ a.types.end(),
+ b.types.begin(),
+ b.types.end(),
+ [&](Type ta, Type tb) { return lessThan(ta, tb); });
+}
+
+bool TypeComparator::lessThan(const Field& a, const Field& b) {
+ if (a.mutable_ != b.mutable_) {
+ return a.mutable_ < b.mutable_;
+ }
+ if (a.type == Type::i32 && b.type == Type::i32) {
+ return a.packedType < b.packedType;
+ }
+ return lessThan(a.type, b.type);
+}
+
+bool TypeComparator::lessThan(const Signature& a, const Signature& b) {
+ if (a.results != b.results) {
+ return lessThan(a.results, b.results);
+ }
+ return lessThan(a.params, b.params);
+}
+
+bool TypeComparator::lessThan(const Struct& a, const Struct& b) {
+ return std::lexicographical_compare(
+ a.fields.begin(),
+ a.fields.end(),
+ b.fields.begin(),
+ b.fields.end(),
+ [&](const Field& fa, const Field& fb) { return lessThan(fa, fb); });
+}
+
+bool TypeComparator::lessThan(const Array& a, const Array& b) {
+ return lessThan(a.element, b.element);
+}
+
+bool TypeComparator::lessThan(const Rtt& a, const Rtt& b) {
+ if (a.depth != b.depth) {
+ return a.depth < b.depth;
+ }
+ return lessThan(a.heapType, b.heapType);
+}
+
+bool SubTyper::isSubType(Type a, Type b) {
+ if (a == b) {
+ return true;
+ }
+ if (a.isRef() && b.isRef()) {
+ return (a.isNullable() == b.isNullable() || !a.isNullable()) &&
+ isSubType(a.getHeapType(), b.getHeapType());
+ }
+ if (a.isTuple() && b.isTuple()) {
+ return isSubType(a.getTuple(), b.getTuple());
+ }
+ if (a.isRtt() && b.isRtt()) {
+ return isSubType(a.getRtt(), b.getRtt());
+ }
+ return false;
+}
+
+bool SubTyper::isSubType(HeapType a, HeapType b) {
+ // See:
+ // https://github.com/WebAssembly/function-references/blob/master/proposals/function-references/Overview.md#subtyping
+ // https://github.com/WebAssembly/gc/blob/master/proposals/gc/MVP.md#defined-types
+ if (a == b) {
+ return true;
+ }
+ if (seen.count({a, b})) {
+ // We weren't able to disprove that a is a subtype of b since we last saw
+ // them, so the relation holds coinductively.
+ return true;
+ }
+ // Everything is a subtype of any.
+ if (b == HeapType::any) {
+ return true;
+ }
+ // Various things are subtypes of eq.
+ if (b == HeapType::eq) {
+ return a == HeapType::i31 || a.isArray() || a.isStruct();
+ }
+ // Some are also subtypes of data.
+ if (b == HeapType::data) {
+ return a.isData();
+ }
+ // Signatures are subtypes of funcref.
+ if (b == HeapType::func) {
+ return a.isSignature();
+ }
+ // As we recurse, we will coinductively assume that a is a subtype of b unless
+ // proven otherwise.
+ seen.insert({a, b});
+ if (a.isSignature() && b.isSignature()) {
+ return isSubType(a.getSignature(), b.getSignature());
+ }
+ if (a.isArray() && b.isArray()) {
+ return isSubType(a.getArray(), b.getArray());
+ }
+ if (a.isStruct() && b.isStruct()) {
+ return isSubType(a.getStruct(), b.getStruct());
+ }
+ return false;
+}
+
+bool SubTyper::isSubType(const Tuple& a, const Tuple& b) {
+ if (a.types.size() != b.types.size()) {
+ return false;
+ }
+ for (size_t i = 0; i < a.types.size(); ++i) {
+ if (!isSubType(a.types[i], b.types[i])) {
+ return false;
+ }
+ }
+ return true;
+}
+
+bool SubTyper::isSubType(const Field& a, const Field& b) {
+ if (a == b) {
+ return true;
+ }
+ // Immutable fields can be subtypes.
+ return a.mutable_ == Immutable && b.mutable_ == Immutable &&
+ a.packedType == b.packedType && isSubType(a.type, b.type);
+}
+
+bool SubTyper::isSubType(const Signature& a, const Signature& b) {
+ // TODO: Implement proper signature subtyping, covariant in results and
+ // contravariant in params, once V8 implements it.
+ // return isSubType(b.params, a.params) && isSubType(a.results, b.results);
+ return a == b;
+}
+
+bool SubTyper::isSubType(const Struct& a, const Struct& b) {
+ // There may be more fields on the left, but not fewer.
+ if (a.fields.size() < b.fields.size()) {
+ return false;
+ }
+ for (size_t i = 0; i < b.fields.size(); ++i) {
+ if (!isSubType(a.fields[i], b.fields[i])) {
+ return false;
+ }
+ }
+ return true;
+}
+
+bool SubTyper::isSubType(const Array& a, const Array& b) {
+ return isSubType(a.element, b.element);
+}
+
+bool SubTyper::isSubType(const Rtt& a, const Rtt& b) {
+ // (rtt n $x) is a subtype of (rtt $x), that is, if the only difference in
+ // information is that the left side specifies a depth while the right side
+ // allows any depth.
+ return a.heapType == b.heapType && a.hasDepth() && !b.hasDepth();
+}
+
+} // anonymous namespace
+
struct TypeBuilder::Impl {
TypeStore typeStore;
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-06 13:11:40 +0000