Source code
Revision control
Copy as Markdown
Other Tools
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
*
* Copyright 2021 Mozilla Foundation
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef wasm_type_def_h
#define wasm_type_def_h
#include "mozilla/Assertions.h"
#include "mozilla/CheckedInt.h"
#include "mozilla/HashTable.h"
#include "js/RefCounted.h"
#include "wasm/WasmCodegenConstants.h"
#include "wasm/WasmCompileArgs.h"
#include "wasm/WasmConstants.h"
#include "wasm/WasmSerialize.h"
#include "wasm/WasmUtility.h"
#include "wasm/WasmValType.h"
namespace js {
namespace wasm {
using mozilla::CheckedInt32;
using mozilla::MallocSizeOf;
class RecGroup;
//=========================================================================
// Function types
// The FuncType class represents a WebAssembly function signature which takes a
// list of value types and returns an expression type. The engine uses two
// in-memory representations of the argument Vector's memory (when elements do
// not fit inline): normal malloc allocation (via SystemAllocPolicy) and
// allocation in a LifoAlloc (via LifoAllocPolicy). The former FuncType objects
// can have any lifetime since they own the memory. The latter FuncType objects
// must not outlive the associated LifoAlloc mark/release interval (which is
// currently the duration of module validation+compilation). Thus, long-lived
// objects like WasmModule must use malloced allocation.
class FuncType {
ValTypeVector args_;
ValTypeVector results_;
// A packed structural type identifier for use in the call_indirect type
// check in the prologue of functions. If this function type cannot fit in
// this immediate, it will be NO_IMMEDIATE_TYPE_ID.
//
// This is initialized in DecodeTypeSection once we have the full recursion
// group around.
uint32_t immediateTypeId_ = NO_IMMEDIATE_TYPE_ID;
// This function type cannot be packed into an immediate for call_indirect
// signature checks.
static const uint32_t NO_IMMEDIATE_TYPE_ID = UINT32_MAX;
// Entry from JS to wasm via the JIT is currently unimplemented for
// functions that return multiple values.
bool temporarilyUnsupportedResultCountForJitEntry() const {
return results().length() > MaxResultsForJitEntry;
}
// Calls out from wasm to JS that return multiple values is currently
// unsupported.
bool temporarilyUnsupportedResultCountForJitExit() const {
return results().length() > MaxResultsForJitExit;
}
// For JS->wasm jit entries, temporarily disallow certain types until the
// stubs generator is improved.
// * ref params may be nullable externrefs
// * ref results may not be type indices
// V128 types are excluded per spec but are guarded against separately.
bool temporarilyUnsupportedReftypeForEntry() const {
for (ValType arg : args()) {
if (arg.isRefType() && (!arg.isExternRef() || !arg.isNullable())) {
return true;
}
}
for (ValType result : results()) {
if (result.isTypeRef()) {
return true;
}
}
return false;
}
// For wasm->JS jit exits, temporarily disallow certain types until
// the stubs generator is improved.
// * ref results may be nullable externrefs
// Unexposable types must be guarded against separately.
bool temporarilyUnsupportedReftypeForExit() const {
for (ValType result : results()) {
if (result.isRefType() &&
(!result.isExternRef() || !result.isNullable())) {
return true;
}
}
return false;
}
public:
FuncType() = default;
FuncType(ValTypeVector&& args, ValTypeVector&& results)
: args_(std::move(args)), results_(std::move(results)) {}
FuncType(FuncType&&) = default;
FuncType& operator=(FuncType&&) = default;
[[nodiscard]] bool clone(const FuncType& src) {
MOZ_ASSERT(args_.empty());
MOZ_ASSERT(results_.empty());
immediateTypeId_ = src.immediateTypeId_;
return args_.appendAll(src.args_) && results_.appendAll(src.results_);
}
ValType arg(unsigned i) const { return args_[i]; }
const ValTypeVector& args() const { return args_; }
ValType result(unsigned i) const { return results_[i]; }
const ValTypeVector& results() const { return results_; }
void initImmediateTypeId(bool gcEnabled, bool isFinal,
const TypeDef* superTypeDef,
uint32_t recGroupLength);
bool hasImmediateTypeId() const {
return immediateTypeId_ != NO_IMMEDIATE_TYPE_ID;
}
uint32_t immediateTypeId() const {
MOZ_ASSERT(hasImmediateTypeId());
return immediateTypeId_;
}
// The lsb for every immediate type id is set to distinguish an immediate type
// id from a type id represented by a pointer to the global hash type set.
static const uint32_t ImmediateBit = 0x1;
HashNumber hash(const RecGroup* recGroup) const {
HashNumber hn = 0;
for (const ValType& vt : args_) {
hn = mozilla::AddToHash(hn, vt.forMatch(recGroup).hash());
}
for (const ValType& vt : results_) {
hn = mozilla::AddToHash(hn, vt.forMatch(recGroup).hash());
}
return hn;
}
// Matches two function types for isorecursive equality. See
// "Matching type definitions" in WasmValType.h for more background.
static bool matches(const RecGroup* lhsRecGroup, const FuncType& lhs,
const RecGroup* rhsRecGroup, const FuncType& rhs) {
if (lhs.args_.length() != rhs.args_.length() ||
lhs.results_.length() != rhs.results_.length()) {
return false;
}
for (uint32_t i = 0; i < lhs.args_.length(); i++) {
if (lhs.args_[i].forMatch(lhsRecGroup) !=
rhs.args_[i].forMatch(rhsRecGroup)) {
return false;
}
}
for (uint32_t i = 0; i < lhs.results_.length(); i++) {
if (lhs.results_[i].forMatch(lhsRecGroup) !=
rhs.results_[i].forMatch(rhsRecGroup)) {
return false;
}
}
return true;
}
// Checks if every arg and result of the specified function types are bitwise
// equal. Type references must therefore point to exactly the same type
// definition instance.
static bool strictlyEquals(const FuncType& lhs, const FuncType& rhs) {
return EqualContainers(lhs.args(), rhs.args()) &&
EqualContainers(lhs.results(), rhs.results());
}
// Checks if two function types are compatible in a given subtyping
// relationship.
static bool canBeSubTypeOf(const FuncType& subType,
const FuncType& superType) {
// A subtype must have exactly as many arguments as its supertype
if (subType.args().length() != superType.args().length()) {
return false;
}
// A subtype must have exactly as many returns as its supertype
if (subType.results().length() != superType.results().length()) {
return false;
}
// Function result types are covariant
for (uint32_t i = 0; i < superType.results().length(); i++) {
if (!ValType::isSubTypeOf(subType.results()[i], superType.results()[i])) {
return false;
}
}
// Function argument types are contravariant
for (uint32_t i = 0; i < superType.args().length(); i++) {
if (!ValType::isSubTypeOf(superType.args()[i], subType.args()[i])) {
return false;
}
}
return true;
}
bool canHaveJitEntry() const;
bool canHaveJitExit() const;
bool hasInt64Arg() const {
for (ValType arg : args()) {
if (arg.kind() == ValType::Kind::I64) {
return true;
}
}
return false;
}
bool hasUnexposableArgOrRet() const {
for (ValType arg : args()) {
if (!arg.isExposable()) {
return true;
}
}
for (ValType result : results()) {
if (!result.isExposable()) {
return true;
}
}
return false;
}
size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
WASM_DECLARE_FRIEND_SERIALIZE(FuncType);
};
//=========================================================================
// Structure types
// The Module owns a dense array of StructType values that represent the
// structure types that the module knows about. It is created from the sparse
// array of types in the ModuleEnvironment when the Module is created.
struct StructField {
StorageType type;
uint32_t offset;
bool isMutable;
HashNumber hash(const RecGroup* recGroup) const {
HashNumber hn = 0;
hn = mozilla::AddToHash(hn, type.forMatch(recGroup).hash());
hn = mozilla::AddToHash(hn, HashNumber(isMutable));
return hn;
}
// Checks if two struct fields are compatible in a given subtyping
// relationship.
static bool canBeSubTypeOf(const StructField& subType,
const StructField& superType) {
// Mutable fields are invariant w.r.t. field types
if (subType.isMutable && superType.isMutable) {
return subType.type == superType.type;
}
// Immutable fields are covariant w.r.t. field types
if (!subType.isMutable && !superType.isMutable) {
return StorageType::isSubTypeOf(subType.type, superType.type);
}
return false;
}
};
using StructFieldVector = Vector<StructField, 0, SystemAllocPolicy>;
using InlineTraceOffsetVector = Vector<uint32_t, 2, SystemAllocPolicy>;
using OutlineTraceOffsetVector = Vector<uint32_t, 0, SystemAllocPolicy>;
class StructType {
public:
StructFieldVector fields_; // Field type, offset, and mutability
uint32_t size_; // The size of the type in bytes.
InlineTraceOffsetVector inlineTraceOffsets_;
OutlineTraceOffsetVector outlineTraceOffsets_;
public:
StructType() : size_(0) {}
explicit StructType(StructFieldVector&& fields)
: fields_(std::move(fields)), size_(0) {}
StructType(StructType&&) = default;
StructType& operator=(StructType&&) = default;
[[nodiscard]] bool clone(const StructType& src) {
if (!fields_.appendAll(src.fields_)) {
return false;
}
size_ = src.size_;
return true;
}
[[nodiscard]] bool init();
bool isDefaultable() const {
for (auto& field : fields_) {
if (!field.type.isDefaultable()) {
return false;
}
}
return true;
}
HashNumber hash(const RecGroup* recGroup) const {
HashNumber hn = 0;
for (const StructField& field : fields_) {
hn = mozilla::AddToHash(hn, field.hash(recGroup));
}
return hn;
}
// Matches two struct types for isorecursive equality. See
// "Matching type definitions" in WasmValType.h for more background.
static bool matches(const RecGroup* lhsRecGroup, const StructType& lhs,
const RecGroup* rhsRecGroup, const StructType& rhs) {
if (lhs.fields_.length() != rhs.fields_.length()) {
return false;
}
for (uint32_t i = 0; i < lhs.fields_.length(); i++) {
const StructField& lhsField = lhs.fields_[i];
const StructField& rhsField = rhs.fields_[i];
if (lhsField.isMutable != rhsField.isMutable ||
lhsField.type.forMatch(lhsRecGroup) !=
rhsField.type.forMatch(rhsRecGroup)) {
return false;
}
}
return true;
}
// Checks if two struct types are compatible in a given subtyping
// relationship.
static bool canBeSubTypeOf(const StructType& subType,
const StructType& superType) {
// A subtype must have at least as many fields as its supertype
if (subType.fields_.length() < superType.fields_.length()) {
return false;
}
// Every field that is in both superType and subType must be compatible
for (uint32_t i = 0; i < superType.fields_.length(); i++) {
if (!StructField::canBeSubTypeOf(subType.fields_[i],
superType.fields_[i])) {
return false;
}
}
return true;
}
static bool createImmutable(const ValTypeVector& types, StructType* struct_);
size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
WASM_DECLARE_FRIEND_SERIALIZE(StructType);
};
using StructTypeVector = Vector<StructType, 0, SystemAllocPolicy>;
// Utility for computing field offset and alignments, and total size for
// structs and tags. This is complicated by fact that a WasmStructObject has
// an inline area, which is used first, and if that fills up an optional
// C++-heap-allocated outline area is used. We need to be careful not to
// split any data item across the boundary. This is ensured as follows:
//
// (1) the possible field sizes are 1, 2, 4, 8 and 16 only.
// (2) each field is "naturally aligned" -- aligned to its size.
// (3) MaxInlineBytes (the size of the inline area) % 16 == 0.
//
// From (1) and (2), it follows that all fields are placed so that their first
// and last bytes fall within the same 16-byte chunk. That is,
// offset_of_first_byte_of_field / 16 == offset_of_last_byte_of_field / 16.
//
// Given that, it follows from (3) that all fields fall completely within
// either the inline or outline areas; no field crosses the boundary.
class StructLayout {
CheckedInt32 sizeSoFar = 0;
uint32_t structAlignment = 1;
public:
// The field adders return the offset of the the field.
CheckedInt32 addField(StorageType type);
// The close method rounds up the structure size to the appropriate
// alignment and returns that size.
CheckedInt32 close();
};
//=========================================================================
// Array types
class ArrayType {
public:
// The kind of value stored in this array
StorageType elementType_;
// Whether this array is mutable or not
bool isMutable_;
public:
ArrayType() : isMutable_(false) {}
ArrayType(StorageType elementType, bool isMutable)
: elementType_(elementType), isMutable_(isMutable) {}
ArrayType(const ArrayType&) = default;
ArrayType& operator=(const ArrayType&) = default;
ArrayType(ArrayType&&) = default;
ArrayType& operator=(ArrayType&&) = default;
[[nodiscard]] bool clone(const ArrayType& src) {
elementType_ = src.elementType_;
isMutable_ = src.isMutable_;
return true;
}
bool isDefaultable() const { return elementType_.isDefaultable(); }
HashNumber hash(const RecGroup* recGroup) const {
HashNumber hn = 0;
hn = mozilla::AddToHash(hn, elementType_.forMatch(recGroup).hash());
hn = mozilla::AddToHash(hn, HashNumber(isMutable_));
return hn;
}
// Matches two array types for isorecursive equality. See
// "Matching type definitions" in WasmValType.h for more background.
static bool matches(const RecGroup* lhsRecGroup, const ArrayType& lhs,
const RecGroup* rhsRecGroup, const ArrayType& rhs) {
return lhs.isMutable_ == rhs.isMutable_ &&
lhs.elementType_.forMatch(lhsRecGroup) ==
rhs.elementType_.forMatch(rhsRecGroup);
}
// Checks if two arrays are compatible in a given subtyping relationship.
static bool canBeSubTypeOf(const ArrayType& subType,
const ArrayType& superType) {
// Mutable fields are invariant w.r.t. field types
if (subType.isMutable_ && superType.isMutable_) {
return subType.elementType_ == superType.elementType_;
}
// Immutable fields are covariant w.r.t. field types
if (!subType.isMutable_ && !superType.isMutable_) {
return StorageType::isSubTypeOf(subType.elementType_,
superType.elementType_);
}
return true;
}
size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
};
WASM_DECLARE_CACHEABLE_POD(ArrayType);
using ArrayTypeVector = Vector<ArrayType, 0, SystemAllocPolicy>;
//=========================================================================
// SuperTypeVector
// [SMDOC] Super type vector
//
// A super type vector is a vector representation of the linked list of super
// types that a type definition has. Every element is a raw pointer to another
// super type vector - they are one-to-one with type definitions, so they are
// functionally equivalent. It is possible to form a vector here because
// subtypes in wasm form trees, not DAGs, with every type having at most one
// super type.
//
// The first element in the vector is the 'root' type definition without a
// super type. The last element is to the type definition itself.
//
// ## Subtype checking
//
// The only purpose of a super type vector is to support constant time
// subtyping checks. This is not free, it comes at the cost of worst case N^2
// metadata size growth. We limit the max subtyping depth to counter this.
//
// To perform a subtype check we rely on the following:
// (1) a type A is a subtype (<:) of type B iff:
// type A == type B OR
// type B is reachable by following declared super types of type A
// (2) we order super type vectors from least to most derived types
// (3) the 'subtyping depth' of all type definitions is statically known
//
// With the above, we know that if type B is a super type of type A, that it
// must be in A's super type vector at type B's subtyping depth. We can
// therefore just do an index and comparison to determine if that's the case.
//
// ## Example
//
// For the following type section:
// ..
// 12: (type (struct))
// ..
// 34: (type (sub 12 (struct)))
// ..
// 56: (type (sub 34 (struct)))
// ..
// 78: (type (sub 56 (struct)))
// ..
//
// (type 12) would have the following super type vector:
// [(type 12)]
//
// (type 78) would have the following super type vector:
// [(type 12), (type 34), (type 56), (type 78)]
//
// Checking that (type 78) <: (type 12) can use the fact that (type 12) will
// always be present at depth 0 of any super type vector it is in, and
// therefore check the vector at that index.
//
// ## Minimum sizing
//
// As a further optimization to avoid bounds checking, we guarantee that all
// super type vectors are at least `MinSuperTypeVectorLength`. All checks
// against indices that we know statically are at/below that can skip bounds
// checking. Extra entries added to reach the minimum size are initialized to
// null.
class SuperTypeVector {
SuperTypeVector() : typeDef_(nullptr), length_(0) {}
// The TypeDef for which this is the supertype vector. That TypeDef should
// point back to this SuperTypeVector.
const TypeDef* typeDef_;
// A cached copy of subTypingDepth from TypeDef.
uint32_t subTypingDepth_;
// The length of types stored inline below.
uint32_t length_;
public:
// Raw pointers to the super types of this type definition. Ordered from
// least-derived to most-derived. Do not add any fields after this point.
const SuperTypeVector* types_[0];
// Batch allocate super type vectors for all the types in a recursion group.
// Returns a pointer to the first super type vector, which can be used to
// free all vectors.
[[nodiscard]] static const SuperTypeVector* createMultipleForRecGroup(
RecGroup* recGroup);
const TypeDef* typeDef() const { return typeDef_; }
uint32_t length() const { return length_; }
const SuperTypeVector* type(size_t index) const {
MOZ_ASSERT(index < length_);
return types_[index];
}
// The length of a super type vector for a specific type def.
static size_t lengthForTypeDef(const TypeDef& typeDef);
// The byte size of a super type vector for a specific type def.
static size_t byteSizeForTypeDef(const TypeDef& typeDef);
static size_t offsetOfSubTypingDepth() {
return offsetof(SuperTypeVector, subTypingDepth_);
}
static size_t offsetOfLength() { return offsetof(SuperTypeVector, length_); }
static size_t offsetOfSelfTypeDef() {
return offsetof(SuperTypeVector, typeDef_);
};
static size_t offsetOfSTVInVector(uint32_t subTypingDepth);
};
// Ensure it is safe to use `sizeof(SuperTypeVector)` to find the offset of
// `types_[0]`.
static_assert(offsetof(SuperTypeVector, types_) == sizeof(SuperTypeVector));
//=========================================================================
// TypeDef and supporting types
// A tagged container for the various types that can be present in a wasm
// module's type section.
enum class TypeDefKind : uint8_t {
None = 0,
Func,
Struct,
Array,
};
class TypeDef {
uint32_t offsetToRecGroup_;
// The supertype vector for this TypeDef. That SuperTypeVector should point
// back to this TypeDef.
const SuperTypeVector* superTypeVector_;
const TypeDef* superTypeDef_;
uint16_t subTypingDepth_;
bool isFinal_;
TypeDefKind kind_;
union {
FuncType funcType_;
StructType structType_;
ArrayType arrayType_;
};
void setRecGroup(RecGroup* recGroup) {
uintptr_t recGroupAddr = (uintptr_t)recGroup;
uintptr_t typeDefAddr = (uintptr_t)this;
MOZ_ASSERT(typeDefAddr > recGroupAddr);
MOZ_ASSERT(typeDefAddr - recGroupAddr <= UINT32_MAX);
offsetToRecGroup_ = typeDefAddr - recGroupAddr;
}
public:
explicit TypeDef(RecGroup* recGroup)
: offsetToRecGroup_(0),
superTypeVector_(nullptr),
superTypeDef_(nullptr),
subTypingDepth_(0),
isFinal_(true),
kind_(TypeDefKind::None) {
setRecGroup(recGroup);
}
~TypeDef() {
switch (kind_) {
case TypeDefKind::Func:
funcType_.~FuncType();
break;
case TypeDefKind::Struct:
structType_.~StructType();
break;
case TypeDefKind::Array:
arrayType_.~ArrayType();
break;
case TypeDefKind::None:
break;
}
}
TypeDef& operator=(FuncType&& that) noexcept {
MOZ_ASSERT(isNone());
kind_ = TypeDefKind::Func;
new (&funcType_) FuncType(std::move(that));
return *this;
}
TypeDef& operator=(StructType&& that) noexcept {
MOZ_ASSERT(isNone());
kind_ = TypeDefKind::Struct;
new (&structType_) StructType(std::move(that));
return *this;
}
TypeDef& operator=(ArrayType&& that) noexcept {
MOZ_ASSERT(isNone());
kind_ = TypeDefKind::Array;
new (&arrayType_) ArrayType(std::move(that));
return *this;
}
const SuperTypeVector* superTypeVector() const { return superTypeVector_; }
void setSuperTypeVector(const SuperTypeVector* superTypeVector) {
superTypeVector_ = superTypeVector;
}
static size_t offsetOfKind() { return offsetof(TypeDef, kind_); }
static size_t offsetOfSuperTypeVector() {
return offsetof(TypeDef, superTypeVector_);
}
static size_t offsetOfSubTypingDepth() {
return offsetof(TypeDef, subTypingDepth_);
}
const TypeDef* superTypeDef() const { return superTypeDef_; }
bool isFinal() const { return isFinal_; }
uint16_t subTypingDepth() const { return subTypingDepth_; }
const RecGroup& recGroup() const {
uintptr_t typeDefAddr = (uintptr_t)this;
uintptr_t recGroupAddr = typeDefAddr - offsetToRecGroup_;
return *(const RecGroup*)recGroupAddr;
}
TypeDefKind kind() const { return kind_; }
bool isNone() const { return kind_ == TypeDefKind::None; }
bool isFuncType() const { return kind_ == TypeDefKind::Func; }
bool isStructType() const { return kind_ == TypeDefKind::Struct; }
bool isArrayType() const { return kind_ == TypeDefKind::Array; }
const FuncType& funcType() const {
MOZ_ASSERT(isFuncType());
return funcType_;
}
FuncType& funcType() {
MOZ_ASSERT(isFuncType());
return funcType_;
}
const StructType& structType() const {
MOZ_ASSERT(isStructType());
return structType_;
}
StructType& structType() {
MOZ_ASSERT(isStructType());
return structType_;
}
const ArrayType& arrayType() const {
MOZ_ASSERT(isArrayType());
return arrayType_;
}
ArrayType& arrayType() {
MOZ_ASSERT(isArrayType());
return arrayType_;
}
// Get a value that can be used for matching type definitions across
// different recursion groups.
static inline uintptr_t forMatch(const TypeDef* typeDef,
const RecGroup* recGroup);
HashNumber hash() const {
HashNumber hn = HashNumber(kind_);
hn = mozilla::AddToHash(hn, TypeDef::forMatch(superTypeDef_, &recGroup()));
hn = mozilla::AddToHash(hn, isFinal_);
switch (kind_) {
case TypeDefKind::Func:
hn = mozilla::AddToHash(hn, funcType_.hash(&recGroup()));
break;
case TypeDefKind::Struct:
hn = mozilla::AddToHash(hn, structType_.hash(&recGroup()));
break;
case TypeDefKind::Array:
hn = mozilla::AddToHash(hn, arrayType_.hash(&recGroup()));
break;
case TypeDefKind::None:
break;
}
return hn;
}
// Matches two type definitions for isorecursive equality. See
// "Matching type definitions" in WasmValType.h for more background.
static bool matches(const TypeDef& lhs, const TypeDef& rhs) {
if (lhs.kind_ != rhs.kind_) {
return false;
}
if (lhs.isFinal_ != rhs.isFinal_) {
return false;
}
if (TypeDef::forMatch(lhs.superTypeDef_, &lhs.recGroup()) !=
TypeDef::forMatch(rhs.superTypeDef_, &rhs.recGroup())) {
return false;
}
switch (lhs.kind_) {
case TypeDefKind::Func:
return FuncType::matches(&lhs.recGroup(), lhs.funcType_,
&rhs.recGroup(), rhs.funcType_);
case TypeDefKind::Struct:
return StructType::matches(&lhs.recGroup(), lhs.structType_,
&rhs.recGroup(), rhs.structType_);
case TypeDefKind::Array:
return ArrayType::matches(&lhs.recGroup(), lhs.arrayType_,
&rhs.recGroup(), rhs.arrayType_);
case TypeDefKind::None:
MOZ_CRASH("can't match TypeDefKind::None");
}
return false;
}
// Checks if two type definitions are compatible in a given subtyping
// relationship.
static bool canBeSubTypeOf(const TypeDef* subType, const TypeDef* superType) {
if (subType->kind() != superType->kind()) {
return false;
}
// A subtype can't declare a final super type.
if (superType->isFinal()) {
return false;
}
switch (subType->kind_) {
case TypeDefKind::Func:
return FuncType::canBeSubTypeOf(subType->funcType_,
superType->funcType_);
case TypeDefKind::Struct:
return StructType::canBeSubTypeOf(subType->structType_,
superType->structType_);
case TypeDefKind::Array:
return ArrayType::canBeSubTypeOf(subType->arrayType_,
superType->arrayType_);
case TypeDefKind::None:
MOZ_CRASH();
}
return false;
}
void setSuperTypeDef(const TypeDef* superTypeDef) {
superTypeDef_ = superTypeDef;
subTypingDepth_ = superTypeDef_->subTypingDepth_ + 1;
}
void setFinal(const bool value) { isFinal_ = value; }
// Checks if `subTypeDef` is a declared sub type of `superTypeDef`.
static bool isSubTypeOf(const TypeDef* subTypeDef,
const TypeDef* superTypeDef) {
// Fast path for when the types are equal
if (MOZ_LIKELY(subTypeDef == superTypeDef)) {
return true;
}
const SuperTypeVector* subSTV = subTypeDef->superTypeVector();
// During construction of a recursion group, the super type vector may not
// have been computed yet, in which case we need to fall back to a linear
// search.
if (!subSTV) {
while (subTypeDef) {
if (subTypeDef == superTypeDef) {
return true;
}
subTypeDef = subTypeDef->superTypeDef();
}
return false;
}
// The supertype vector does exist. So check it points back here.
MOZ_ASSERT(subSTV->typeDef() == subTypeDef);
// We need to check if `superTypeDef` is one of `subTypeDef`s super types
// by checking in `subTypeDef`s super type vector. We can use the static
// information of the depth of `superTypeDef` to index directly into the
// vector.
uint32_t subTypingDepth = superTypeDef->subTypingDepth();
if (subTypingDepth >= subSTV->length()) {
return false;
}
const SuperTypeVector* superSTV = superTypeDef->superTypeVector();
MOZ_ASSERT(superSTV);
MOZ_ASSERT(superSTV->typeDef() == superTypeDef);
return subSTV->type(subTypingDepth) == superSTV;
}
size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
WASM_DECLARE_FRIEND_SERIALIZE(TypeDef);
};
using SharedTypeDef = RefPtr<const TypeDef>;
using MutableTypeDef = RefPtr<TypeDef>;
using TypeDefVector = Vector<TypeDef, 0, SystemAllocPolicy>;
using TypeDefPtrVector = Vector<const TypeDef*, 0, SystemAllocPolicy>;
using TypeDefPtrToIndexMap =
HashMap<const TypeDef*, uint32_t, PointerHasher<const TypeDef*>,
SystemAllocPolicy>;
//=========================================================================
// RecGroup
// A recursion group is a set of type definitions that may refer to each other
// or to type definitions in another recursion group. There is an ordering
// restriction on type references such that references across recursion groups
// must be acyclic.
//
// Type definitions are stored inline in their containing recursion group, and
// have an offset to their containing recursion group. Recursion groups are
// atomically refcounted and hold strong references to other recursion groups
// they depend on.
//
// Type equality is structural in WebAssembly, and we canonicalize recursion
// groups while building them so that pointer equality of types implies
// equality of types. There is a global hash set of weak pointers to recursion
// groups that holds the current canonical instance of a recursion group.
class RecGroup : public AtomicRefCounted<RecGroup> {
// Whether this recursion group has been finished and acquired strong
// references to external recursion groups.
bool finalizedTypes_;
// The number of types stored in this recursion group.
uint32_t numTypes_;
// The batch allocated super type vectors for all type definitions in this
// recursion group.
const SuperTypeVector* vectors_;
// The first type definition stored inline in this recursion group.
TypeDef types_[0];
friend class TypeContext;
explicit RecGroup(uint32_t numTypes)
: finalizedTypes_(false), numTypes_(numTypes), vectors_(nullptr) {}
// Compute the size in bytes of a recursion group with the specified amount
// of types.
static constexpr size_t sizeOfRecGroup(uint32_t numTypes) {
static_assert(MaxTypes <= SIZE_MAX / sizeof(TypeDef));
return sizeof(RecGroup) + sizeof(TypeDef) * numTypes;
}
// Allocate a recursion group with the specified amount of types. The type
// definitions will be ready to be filled in. Users must call `finish` once
// type definitions are initialized so that strong references to external
// recursion groups are taken.
static RefPtr<RecGroup> allocate(uint32_t numTypes) {
// Allocate the recursion group with the correct size
RecGroup* recGroup = (RecGroup*)js_malloc(sizeOfRecGroup(numTypes));
if (!recGroup) {
return nullptr;
}
// Construct the recursion group and types that are stored inline
new (recGroup) RecGroup(numTypes);
for (uint32_t i = 0; i < numTypes; i++) {
new (recGroup->types_ + i) TypeDef(recGroup);
}
return recGroup;
}
// Finish initialization by acquiring strong references to groups referenced
// by type definitions.
[[nodiscard]] bool finalizeDefinitions() {
MOZ_ASSERT(!finalizedTypes_);
// Super type vectors are only needed for GC and have a size/time impact
// that we don't want to encur until we're ready for it. Only use them when
// GC is built into the binary.
vectors_ = SuperTypeVector::createMultipleForRecGroup(this);
if (!vectors_) {
return false;
}
visitReferencedGroups([](const RecGroup* recGroup) { recGroup->AddRef(); });
finalizedTypes_ = true;
return true;
}
// Visit every external recursion group that is referenced by the types in
// this recursion group.
template <typename Visitor>
void visitReferencedGroups(Visitor visitor) const {
auto visitValType = [this, visitor](ValType type) {
if (type.isTypeRef() && &type.typeDef()->recGroup() != this) {
visitor(&type.typeDef()->recGroup());
}
};
auto visitStorageType = [this, visitor](StorageType type) {
if (type.isTypeRef() && &type.typeDef()->recGroup() != this) {
visitor(&type.typeDef()->recGroup());
}
};
for (uint32_t i = 0; i < numTypes_; i++) {
const TypeDef& typeDef = types_[i];
if (typeDef.superTypeDef() &&
&typeDef.superTypeDef()->recGroup() != this) {
visitor(&typeDef.superTypeDef()->recGroup());
}
switch (typeDef.kind()) {
case TypeDefKind::Func: {
const FuncType& funcType = typeDef.funcType();
for (auto type : funcType.args()) {
visitValType(type);
}
for (auto type : funcType.results()) {
visitValType(type);
}
break;
}
case TypeDefKind::Struct: {
const StructType& structType = typeDef.structType();
for (const auto& field : structType.fields_) {
visitStorageType(field.type);
}
break;
}
case TypeDefKind::Array: {
const ArrayType& arrayType = typeDef.arrayType();
visitStorageType(arrayType.elementType_);
break;
}
case TypeDefKind::None: {
MOZ_CRASH();
}
}
}
}
public:
~RecGroup() {
// Release the referenced recursion groups if we acquired references to
// them. Do this before the type definitions are destroyed below.
if (finalizedTypes_) {
finalizedTypes_ = false;
visitReferencedGroups(
[](const RecGroup* recGroup) { recGroup->Release(); });
}
if (vectors_) {
js_free((void*)vectors_);
vectors_ = nullptr;
}
// Call destructors on all the type definitions.
for (uint32_t i = 0; i < numTypes_; i++) {
type(i).~TypeDef();
}
}
// Recursion groups cannot be copied or moved
RecGroup& operator=(const RecGroup&) = delete;
RecGroup& operator=(RecGroup&&) = delete;
// Get the type definition at the group type index (not module type index).
TypeDef& type(uint32_t groupTypeIndex) {
// We cannot mutate type definitions after we've finalized them
MOZ_ASSERT(!finalizedTypes_);
return types_[groupTypeIndex];
}
const TypeDef& type(uint32_t groupTypeIndex) const {
return types_[groupTypeIndex];
}
// The number of types stored in this recursion group.
uint32_t numTypes() const { return numTypes_; }
// Get the index of a type definition that's in this recursion group.
uint32_t indexOf(const TypeDef* typeDef) const {
MOZ_ASSERT(typeDef >= types_);
size_t groupTypeIndex = (size_t)(typeDef - types_);
MOZ_ASSERT(groupTypeIndex < numTypes());
return (uint32_t)groupTypeIndex;
}
HashNumber hash() const {
HashNumber hn = 0;
for (uint32_t i = 0; i < numTypes(); i++) {
hn = mozilla::AddToHash(hn, types_[i].hash());
}
return hn;
}
// Matches two recursion groups for isorecursive equality. See
// "Matching type definitions" in WasmValType.h for more background.
static bool matches(const RecGroup& lhs, const RecGroup& rhs) {
if (lhs.numTypes() != rhs.numTypes()) {
return false;
}
for (uint32_t i = 0; i < lhs.numTypes(); i++) {
if (!TypeDef::matches(lhs.type(i), rhs.type(i))) {
return false;
}
}
return true;
}
};
// Remove all types from the canonical type set that are not referenced from
// outside the type set.
extern void PurgeCanonicalTypes();
using SharedRecGroup = RefPtr<const RecGroup>;
using MutableRecGroup = RefPtr<RecGroup>;
using SharedRecGroupVector = Vector<SharedRecGroup, 0, SystemAllocPolicy>;
//=========================================================================
// TypeContext
// A type context holds the recursion groups and corresponding type definitions
// defined in a module.
class TypeContext : public AtomicRefCounted<TypeContext> {
FeatureArgs features_;
// The pending recursion group that is currently being constructed
MutableRecGroup pendingRecGroup_;
// An in-order list of all the recursion groups defined in this module
SharedRecGroupVector recGroups_;
// An in-order list of the type definitions in the module. Each type is
// stored in a recursion group.
TypeDefPtrVector types_;
// A map from type definition to the original module index.
TypeDefPtrToIndexMap moduleIndices_;
static SharedRecGroup canonicalizeGroup(SharedRecGroup recGroup);
public:
TypeContext() = default;
explicit TypeContext(const FeatureArgs& features) : features_(features) {}
~TypeContext();
size_t sizeOfExcludingThis(MallocSizeOf mallocSizeOf) const {
return types_.sizeOfExcludingThis(mallocSizeOf) +
moduleIndices_.shallowSizeOfExcludingThis(mallocSizeOf);
}
// Disallow copy, allow move initialization
TypeContext(const TypeContext&) = delete;
TypeContext& operator=(const TypeContext&) = delete;
TypeContext(TypeContext&&) = delete;
TypeContext& operator=(TypeContext&&) = delete;
// Begin creating a recursion group with the specified number of types.
// Returns a recursion group to be filled in with type definitions. This must
// be paired with `endGroup`.
[[nodiscard]] MutableRecGroup startRecGroup(uint32_t numTypes) {
// We must not have a pending group
MOZ_ASSERT(!pendingRecGroup_);
// Create the group and add it to the list of groups
MutableRecGroup recGroup = RecGroup::allocate(numTypes);
if (!recGroup || !addRecGroup(recGroup)) {
return nullptr;
}
// Store this group for later use in endRecGroup
pendingRecGroup_ = recGroup;
return recGroup;
}
// Finish creation of a recursion group after type definitions have been
// initialized. This must be paired with `startGroup`.
[[nodiscard]] bool endRecGroup() {
// We must have started a recursion group
MOZ_ASSERT(pendingRecGroup_);
MutableRecGroup recGroup = pendingRecGroup_;
pendingRecGroup_ = nullptr;
// Finalize the type definitions in the recursion group
if (!recGroup->finalizeDefinitions()) {
return false;
}
// Canonicalize the recursion group
SharedRecGroup canonicalRecGroup = canonicalizeGroup(recGroup);
if (!canonicalRecGroup) {
return false;
}
// Nothing left to do if this group became the canonical group
if (canonicalRecGroup == recGroup) {
return true;
}
// Store the canonical group into the list
recGroups_.back() = canonicalRecGroup;
// Overwrite all the entries we stored into the index space maps when we
// started this group.
MOZ_ASSERT(recGroup->numTypes() == canonicalRecGroup->numTypes());
for (uint32_t groupTypeIndex = 0; groupTypeIndex < recGroup->numTypes();
groupTypeIndex++) {
uint32_t typeIndex = length() - recGroup->numTypes() + groupTypeIndex;
const TypeDef* oldTypeDef = types_[typeIndex];
const TypeDef* canonTypeDef = &canonicalRecGroup->type(groupTypeIndex);
types_[typeIndex] = canonTypeDef;
moduleIndices_.remove(oldTypeDef);
// Ensure there is an module index entry pointing to the canonical type
// definition. Don't overwrite it if it already exists, serialization
// relies on the module index map pointing to the first occurrence of a
// type definition to avoid creating forward references that didn't exist
// in the original module.
auto canonTypeIndexEntry = moduleIndices_.lookupForAdd(canonTypeDef);
if (!canonTypeIndexEntry &&
!moduleIndices_.add(canonTypeIndexEntry, canonTypeDef, typeIndex)) {
return false;
}
}
return true;
}
// Finish creation of a recursion group after type definitions have been
// initialized. This must be paired with `startGroup`.
[[nodiscard]] bool addRecGroup(SharedRecGroup recGroup) {
// We must not have a pending group
MOZ_ASSERT(!pendingRecGroup_);
// Add it to the list of groups
if (!recGroups_.append(recGroup)) {
return false;
}
// Store the types of the group into our index space maps. These may get
// overwritten if this group is being added by `startRecGroup` and we
// overwrite it with a canonical group in `endRecGroup`. We need to do
// this before finishing though, because these entries will be used by
// decoding and error printing.
for (uint32_t groupTypeIndex = 0; groupTypeIndex < recGroup->numTypes();
groupTypeIndex++) {
const TypeDef* typeDef = &recGroup->type(groupTypeIndex);
uint32_t typeIndex = types_.length();
if (!types_.append(typeDef) || !moduleIndices_.put(typeDef, typeIndex)) {
return false;
}
}
return true;
}
template <typename T>
[[nodiscard]] const TypeDef* addType(T&& type) {
MutableRecGroup recGroup = startRecGroup(1);
if (!recGroup) {
return nullptr;
}
recGroup->type(0) = std::move(type);
if (!endRecGroup()) {
return nullptr;
}
return &this->type(length() - 1);
}
const TypeDef& type(uint32_t index) const { return *types_[index]; }
const TypeDef& operator[](uint32_t index) const { return *types_[index]; }
bool empty() const { return types_.empty(); }
uint32_t length() const { return types_.length(); }
const SharedRecGroupVector& groups() const { return recGroups_; }
// Map from type definition to index
uint32_t indexOf(const TypeDef& typeDef) const {
auto moduleIndex = moduleIndices_.readonlyThreadsafeLookup(&typeDef);
MOZ_RELEASE_ASSERT(moduleIndex.found());
return moduleIndex->value();
}
};
using SharedTypeContext = RefPtr<const TypeContext>;
using MutableTypeContext = RefPtr<TypeContext>;
//=========================================================================
// TypeHandle
// An unambiguous strong reference to a type definition in a specific type
// context.
class TypeHandle {
private:
SharedTypeContext context_;
uint32_t index_;
public:
TypeHandle(SharedTypeContext context, uint32_t index)
: context_(context), index_(index) {
MOZ_ASSERT(index_ < context_->length());
}
TypeHandle(SharedTypeContext context, const TypeDef& def)
: context_(context), index_(context->indexOf(def)) {}
TypeHandle(const TypeHandle&) = default;
TypeHandle& operator=(const TypeHandle&) = default;
const SharedTypeContext& context() const { return context_; }
uint32_t index() const { return index_; }
const TypeDef& def() const { return context_->type(index_); }
};
//=========================================================================
// misc
/* static */
inline uintptr_t TypeDef::forMatch(const TypeDef* typeDef,
const RecGroup* recGroup) {
// TypeDef is aligned sufficiently to allow a tag to distinguish a local type
// reference (index) from a non-local type reference (pointer).
static_assert(alignof(TypeDef) > 1);
MOZ_ASSERT((uintptr_t(typeDef) & 0x1) == 0);
// Return a tagged index for local type references
if (typeDef && &typeDef->recGroup() == recGroup) {
return uintptr_t(recGroup->indexOf(typeDef)) | 0x1;
}
// Return an untagged pointer for non-local type references
return uintptr_t(typeDef);
}
/* static */
inline MatchTypeCode MatchTypeCode::forMatch(PackedTypeCode ptc,
const RecGroup* recGroup) {
MatchTypeCode mtc = {};
mtc.typeCode = PackedRepr(ptc.typeCode());
mtc.typeRef = TypeDef::forMatch(ptc.typeDef(), recGroup);
mtc.nullable = ptc.isNullable();
return mtc;
}
template <class T>
void PackedType<T>::AddRef() const {
if (!isRefType()) {
return;
}
refType().AddRef();
}
template <class T>
void PackedType<T>::Release() const {
if (!isRefType()) {
return;
}
refType().Release();
}
void RefType::AddRef() const {
if (!isTypeRef()) {
return;
}
typeDef()->recGroup().AddRef();
}
void RefType::Release() const {
if (!isTypeRef()) {
return;
}
typeDef()->recGroup().Release();
}
inline RefTypeHierarchy RefType::hierarchy() const {
switch (kind()) {
case RefType::Func:
case RefType::NoFunc:
return RefTypeHierarchy::Func;
case RefType::Extern:
case RefType::NoExtern:
return RefTypeHierarchy::Extern;
case RefType::Exn:
return RefTypeHierarchy::Exn;
case RefType::Any:
case RefType::None:
case RefType::I31:
case RefType::Eq:
case RefType::Struct:
case RefType::Array:
return RefTypeHierarchy::Any;
case RefType::TypeRef:
switch (typeDef()->kind()) {
case TypeDefKind::Struct:
case TypeDefKind::Array:
return RefTypeHierarchy::Any;
case TypeDefKind::Func:
return RefTypeHierarchy::Func;
case TypeDefKind::None:
MOZ_CRASH();
}
}
MOZ_CRASH("switch is exhaustive");
}
inline TableRepr RefType::tableRepr() const {
switch (hierarchy()) {
case RefTypeHierarchy::Any:
case RefTypeHierarchy::Extern:
case RefTypeHierarchy::Exn:
return TableRepr::Ref;
case RefTypeHierarchy::Func:
return TableRepr::Func;
}
MOZ_CRASH("switch is exhaustive");
}
inline bool RefType::isFuncHierarchy() const {
return hierarchy() == RefTypeHierarchy::Func;
}
inline bool RefType::isExternHierarchy() const {
return hierarchy() == RefTypeHierarchy::Extern;
}
inline bool RefType::isAnyHierarchy() const {
return hierarchy() == RefTypeHierarchy::Any;
}
inline bool RefType::isExnHierarchy() const {
return hierarchy() == RefTypeHierarchy::Exn;
}
/* static */
inline bool RefType::isSubTypeOf(RefType subType, RefType superType) {
// Anything is a subtype of itself.
if (subType == superType) {
return true;
}
// A subtype must have the same nullability as the supertype or the
// supertype must be nullable.
if (subType.isNullable() && !superType.isNullable()) {
return false;
}
// Non type-index references are subtypes if they have the same kind
if (!subType.isTypeRef() && !superType.isTypeRef() &&
subType.kind() == superType.kind()) {
return true;
}
// eqref is a subtype of anyref
if (subType.isEq() && superType.isAny()) {
return true;
}
// i31ref is a subtype of eqref
if (subType.isI31() && (superType.isAny() || superType.isEq())) {
return true;
}
// structref/arrayref are subtypes of eqref and anyref
if ((subType.isStruct() || subType.isArray()) &&
(superType.isAny() || superType.isEq())) {
return true;
}
// Structs are subtypes of structref, eqref and anyref
if (subType.isTypeRef() && subType.typeDef()->isStructType() &&
(superType.isAny() || superType.isEq() || superType.isStruct())) {
return true;
}
// Arrays are subtypes of arrayref, eqref and anyref
if (subType.isTypeRef() && subType.typeDef()->isArrayType() &&
(superType.isAny() || superType.isEq() || superType.isArray())) {
return true;
}
// Funcs are subtypes of funcref
if (subType.isTypeRef() && subType.typeDef()->isFuncType() &&
superType.isFunc()) {
return true;
}
// Type references can be subtypes
if (subType.isTypeRef() && superType.isTypeRef()) {
return TypeDef::isSubTypeOf(subType.typeDef(), superType.typeDef());
}
// No func is the bottom type of the func hierarchy
if (subType.isNoFunc() && superType.hierarchy() == RefTypeHierarchy::Func) {
return true;
}
// No extern is the bottom type of the extern hierarchy
if (subType.isNoExtern() &&
superType.hierarchy() == RefTypeHierarchy::Extern) {
return true;
}
// None is the bottom type of the any hierarchy
if (subType.isNone() && superType.hierarchy() == RefTypeHierarchy::Any) {
return true;
}
return false;
}
/* static */
inline bool RefType::castPossible(RefType sourceType, RefType destType) {
// Nullable types always have null in common.
if (sourceType.isNullable() && destType.isNullable()) {
return true;
}
// At least one of the types is non-nullable, so the only common values can be
// non-null. Therefore, if either type is a bottom type, common values are
// impossible.
if (sourceType.isRefBottom() || destType.isRefBottom()) {
return false;
}
// After excluding bottom types, our type hierarchy is a tree, and after
// excluding nulls, subtype relationships are sufficient to tell if the types
// share any values. If neither type is a subtype of the other, then they are
// on different branches of the tree and completely disjoint.
RefType sourceNonNull = sourceType.withIsNullable(false);
RefType destNonNull = destType.withIsNullable(false);
return RefType::isSubTypeOf(sourceNonNull, destNonNull) ||
RefType::isSubTypeOf(destNonNull, sourceNonNull);
}
//=========================================================================
// [SMDOC] Signatures and runtime types
//
// TypeIdDesc describes the runtime representation of a TypeDef suitable for
// type equality checks. The kind of representation depends on whether the type
// is a function or a GC type. This design is in flux and will evolve.
//
// # Function types
//
// For functions in the general case, a FuncType is allocated and stored in a
// process-wide hash table, so that pointer equality implies structural
// equality. This process does not correctly handle type references (which would
// require hash-consing of infinite-trees), but that's okay while
// function-references and gc-types are experimental.
//
// A pointer to the hash table entry is stored in the global data
// area for each instance, and TypeIdDesc gives the offset to this entry.
//
// ## Immediate function types
//
// As an optimization for the 99% case where the FuncType has a small number of
// parameters, the FuncType is bit-packed into a uint32 immediate value so that
// integer equality implies structural equality. Both cases can be handled with
// a single comparison by always setting the LSB for the immediates
// (the LSB is necessarily 0 for allocated FuncType pointers due to alignment).
//
// # GC types
//
// For GC types, an entry is always created in the global data area and a
// unique RttValue (see wasm/WasmGcObject.h) is stored there. This RttValue
// is the value given by 'rtt.canon $t' for each type definition. As each entry
// is given a unique value and no canonicalization is done (which would require
// hash-consing of infinite-trees), this is not yet spec compliant.
//
// # wasm::Instance and the global type context
//
// As GC objects may outlive the module they are created in, types are
// additionally transferred to a wasm::Context (which is part of JSContext) upon
// instantiation. This wasm::Context contains the 'global type context' that
// RTTValues refer to by type index. Types are never freed from the global type
// context as that would shift the index space. In the future, this will be
// fixed.
} // namespace wasm
} // namespace js
#endif // wasm_type_def_h