Skip to content

Commit e1978e0

Browse files
tlivelytlively
authored
TypeBuilder (WebAssembly#3418)
Introduce TypeBuilder, a utility for constructing heap types in terms of other heap types that may have not yet been defined. Internally, it works by creating HeapTypes backed by mutable HeapTypeInfos owned by the TypeBuilder. That lets the TypeBuilder create temporary Types that can refer to the TypeBuilder-managed HeapTypes. Those temporary Types can in turn be used to initialize the very HeapTypes they refer to. Since the TypeBuilder-managed HeapTypes are only valid for the lifetime of their TypeBuilder, there is a canonicalization step that converts them into globally interned canonical HeapTypes. This PR allows HeapTypes to be built in terms of as of yet undefined HeapTypes, but it currently errors out in the presence of recursive types. Supporting recursive types will require further work to canonicalize them into finite, acyclic representations. Currently any attempt to compare, print, or otherwise manipulate recursive types would infinitely recurse.
1 parent c93da3d commit e1978e0

4 files changed

Lines changed: 518 additions & 8 deletions

File tree

‎src/wasm-type.h‎

Lines changed: 48 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -44,12 +44,18 @@ struct Struct;
4444
struct Array;
4545
struct Rtt;
4646

47+
// The type used for interning IDs in the public interfaces of Type and
48+
// HeapType.
49+
using TypeID = uint64_t;
50+
4751
class Type {
4852
// The `id` uniquely represents each type, so type equality is just a
4953
// comparison of the ids. For basic types the `id` is just the `BasicType`
5054
// enum value below, and for constructed types the `id` is the address of the
5155
// canonical representation of the type, making lookups cheap for all types.
5256
// Since `Type` is really just a single integer, it should be passed by value.
57+
// This is a uintptr_t rather than a TypeID (uint64_t) to save memory on
58+
// 32-bit platforms.
5359
uintptr_t id;
5460

5561
public:
@@ -75,8 +81,8 @@ class Type {
7581
// BasicType can be implicitly upgraded to Type
7682
constexpr Type(BasicType id) : id(id) {}
7783

78-
// But converting raw uint64_t is more dangerous, so make it explicit
79-
explicit Type(uint64_t id) : id(id) {}
84+
// But converting raw TypeID is more dangerous, so make it explicit
85+
explicit Type(TypeID id) : id(id) {}
8086

8187
// Construct tuple from a list of single types
8288
Type(std::initializer_list<Type>);
@@ -147,7 +153,7 @@ class Type {
147153
bool hasVector() { return hasPredicate<&Type::isVector>(); }
148154
bool hasRef() { return hasPredicate<&Type::isRef>(); }
149155

150-
constexpr uint64_t getID() const { return id; }
156+
constexpr TypeID getID() const { return id; }
151157
constexpr BasicType getBasic() const {
152158
assert(isBasic() && "Basic type expected");
153159
return static_cast<BasicType>(id);
@@ -293,8 +299,8 @@ class HeapType {
293299
// BasicHeapType can be implicitly upgraded to HeapType
294300
constexpr HeapType(BasicHeapType id) : id(id) {}
295301

296-
// But converting raw uint64_t is more dangerous, so make it explicit
297-
explicit HeapType(uint64_t id) : id(id) {}
302+
// But converting raw TypeID is more dangerous, so make it explicit
303+
explicit HeapType(TypeID id) : id(id) {}
298304

299305
HeapType(Signature signature);
300306
HeapType(const Struct& struct_);
@@ -312,7 +318,7 @@ class HeapType {
312318
const Struct& getStruct() const;
313319
Array getArray() const;
314320

315-
constexpr uint64_t getID() const { return id; }
321+
constexpr TypeID getID() const { return id; }
316322
constexpr BasicHeapType getBasic() const {
317323
assert(isBasic() && "Basic heap type expected");
318324
return static_cast<BasicHeapType>(id);
@@ -449,6 +455,42 @@ struct Rtt {
449455
std::string toString() const;
450456
};
451457

458+
// TypeBuilder - allows for the construction of recursive types. Contains a
459+
// table of `n` mutable HeapTypes and can construct temporary types that are
460+
// backed by those HeapTypes, refering to them by reference. Those temporary
461+
// types are owned by the TypeBuilder and should only be used in the
462+
// construction of HeapTypes to insert into the TypeBuilder. Temporary types
463+
// should never be used in the construction of normal Types, only other
464+
// temporary types.
465+
struct TypeBuilder {
466+
struct Impl;
467+
std::unique_ptr<Impl> impl;
468+
469+
TypeBuilder(size_t n);
470+
~TypeBuilder();
471+
472+
TypeBuilder(TypeBuilder& other) = delete;
473+
TypeBuilder(TypeBuilder&& other) = delete;
474+
TypeBuilder& operator=(TypeBuilder&) = delete;
475+
476+
// Sets the heap type at index `i`. May only be called before `build`.
477+
void setHeapType(size_t i, Signature signature);
478+
void setHeapType(size_t i, const Struct& struct_);
479+
void setHeapType(size_t i, Struct&& struct_);
480+
void setHeapType(size_t i, Array array);
481+
482+
// Gets a temporary type or heap type for use in initializing the
483+
// TypeBuilder's HeapTypes. Temporary Ref and Rtt types are backed by the
484+
// HeapType at index `i`.
485+
Type getTempTupleType(const Tuple&);
486+
Type getTempRefType(size_t i, bool nullable);
487+
Type getTempRttType(size_t i, uint32_t depth);
488+
489+
// Canonicalizes and returns all of the heap types. May only be called once
490+
// all of the heap types have been initialized with `setHeapType`.
491+
std::vector<HeapType> build();
492+
};
493+
452494
std::ostream& operator<<(std::ostream&, Type);
453495
std::ostream& operator<<(std::ostream&, ParamType);
454496
std::ostream& operator<<(std::ostream&, ResultType);

0 commit comments

Comments
 (0)