TypeBuilder by tlively · Pull Request #3418 · WebAssembly/binaryen

tlively · 2020-12-03T03:53:35Z

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 using new
TypeInfo variants that contain pointers to HeapTypes rather than HeapType
values. That lets the TypeBuilder create temporary types that can refer to
uninitialized heap types owned by the TypeBuilder. Those temporary types can in
turn be used to initialize the very heap types they refer to. Since temporary
types are only valid for the lifetime of their TypeBuilder, there is a
canonicalization step that converts the temporary types reachable from the
TypeBuilder's heap types into globally interned canonical types. Only after that
canonicalization step can the heap types be used to construct non-temporary
types.

This PR allows Types to be built in terms of as of yet undefined heap types, 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 recursive types would
infinitely recurse.

cc @dcodeIO

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 using new TypeInfo variants that contain pointers to HeapTypes rather than HeapType values. That lets the TypeBuilder create temporary types that can refer to uninitialized heap types owned by the TypeBuilder. Those temporary types can in turn be used to initialize the very heap types they refer to. Since temporary types are only valid for the lifetime of their TypeBuilder, there is a canonicalization step that converts the temporary types reachable from the TypeBuilder's heap types into globally interned canonical types. Only after that canonicalization step can the heap types be used to construct non-temporary types. This PR allows Types to be built in terms of as of yet undefined heap types, 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 recursive types would infinitely recurse.

kripken

Oh, and just to make sure about the overall plan: This PR does not modify module-utils.h, but your next PR would?

kripken · 2020-12-03T17:28:04Z

+  struct TempRtt {
+    uint32_t depth;
+    HeapType* heapType;
+  };


This makes me wonder once again if maybe HeapTypes should always be by a pointer. That is, that on line 37/40 we'd have HeapType* instead of HeapType.

I may be missing something, but it seems like that would make it simpler to implement the TypeBuilder, as we wouldn't need to add TempRef and TempRtt. And, separately, it would also avoid the risk of copies being passed around.

If memory safety is a concern here, then our usage pattern is very simple - allocate types when creating a wasm, and then use them. We could just store them in a global arena that is freed on process exit, like strings are. Note that that is a separate question from whether we intern them or not (which I am not sure about either way).

One of my concerns about TempRef and TempRtt, more specifically, is that they end up intruding in various places throughout this file. If somehow the TypeBuilder could encapsulate that complexity into itself then that would be another option to think about.

I'll experiment with this.

tlively · 2020-12-03T17:52:01Z

Oh, and just to make sure about the overall plan: This PR does not modify module-utils.h, but your next PR would?

The next PR would use TypeBuilder in the binary and text parsers. The PR after that would update the type finding code in module-utils.h to do a full type traversal and would remove the code that does the almost-topographical sort of the types.

Interns HeapTypes using the same patterns and utilities already used to intern Types. This allows HeapTypes to efficiently be compared for equality and hashed, which may be important for very large struct types in the future. This change also has the benefit of increasing symmetry between the APIs of Type and HeapType, which will make the developer experience more consistent. Finally, this change will make TypeBuilder (WebAssembly#3418) much simpler because it will no longer have to introduce TypeInfo variants to refer to HeapTypes indirectly.

Interns HeapTypes using the same patterns and utilities already used to intern Types. This allows HeapTypes to efficiently be compared for equality and hashed, which may be important for very large struct types in the future. This change also has the benefit of increasing symmetry between the APIs of Type and HeapType, which will make the developer experience more consistent. Finally, this change will make TypeBuilder (#3418) much simpler because it will no longer have to introduce TypeInfo variants to refer to HeapTypes indirectly.

tlively · 2020-12-09T03:14:55Z

@kripken I rewrote this on top of #3428 and expanded many of the comments. I think it's much cleaner now 👍 PTAL!

kripken · 2020-12-09T16:17:54Z

+  void setHeapType(size_t i, Signature signature);
+  void setHeapType(size_t i, const Struct& struct_);
+  void setHeapType(size_t i, Struct&& struct_);
+  void setHeapType(size_t i, Array array);


The struct/array asymmetry feels a little wrong to me each time I see it. May be worth thinking more about this eventually.

kripken · 2020-12-09T16:19:49Z

 HeapTypeStore globalHeapTypeStore;

+// Specialized to simplify programming generically over Types and HeapTypes.
+template<typename T> struct MetaTypeInfo {};


Not in this PR, but I am wondering more and more if we shouldn't merge Type and HeapType perhaps.

I think it is useful to maintain the distinction between them, despite their similarities. They're certainly not interchangeable in the public API.

That's a fair point that they matter in the public API. But OTOH, the public API also differentiates struct from array types, but we don't have a StructType or ArrayType. In other words, we could have a single Type, with a isHeap() like we have isTuple(),isRef(),isRtt() etc. Maybe I'm overthinking this though.

I personally think having them separately is clearer. They represent fundamentally different kinds of type: Type is what every value and expression has, and HeapType is what we list in the type section, and they cannot be used interchangeably and one is not a subtype of the other. On the other hand, all of tuple, ref, and rtt are subtypes of Type.

kripken · 2020-12-09T19:48:43Z

+  };
+
+  // IDs of scanned Types and HeapTypes, used to prevent repeated scanning.
+  std::unordered_set<uint64_t> scanned;


maybe an ID type for uint64_t?

kripken · 2020-12-09T19:52:41Z

+
+  struct Entry {
+    bool initialized = false;
+    HeapTypeInfo info = Signature();


Why is there Signature here?

HeapTypeInfo does not have a default initializer, but we want to be able to default initialize Entry, so we have to give info an explicit default value. I'll add a comment clarifying that it is arbitrary.

kripken · 2020-12-09T19:54:19Z

+// replacing and deduplicating the temporary type and heaptypes backed by
+// storage owned by the TypeBuilder into normal types and heap types backed by
+// the global stores.
+struct Canonicalizer {


This could maybe be in an anonymous namespace?

kripken · 2020-12-09T20:10:16Z

+  }
+}
+
+void Canonicalizer::makeReachabilityFixpoint() {


Isn't "Fixed Point" the term? Or is "fixpoint" a common shorthand?

Suggested change

void Canonicalizer::makeReachabilityFixpoint() {

void Canonicalizer::makeReachabilityFixedPoint() {

That wikipedia article starts "In mathematics, a fixed point (sometimes shortened to fixpoint" so I think we could go either way.

Oh, sorry, not sure how I missed that in the link...

no problem :) I'll go with your suggestion since it is indeed the more standard name.

kripken · 2020-12-09T20:12:02Z

+  void scanType(Type* child);
+  void makeReachabilityFixpoint();
+  template<typename T>
+  void canonicalize(T* type, std::unordered_map<T, T>& canonicals);


maybe a comment on this method? the out param is not immediately obvious.

kripken · 2020-12-09T20:56:00Z

+}
+
+Type TypeBuilder::getTempTupleType(const Tuple& tuple) {
+  return impl->typeStore.canonicalize(tuple);


How does this work? For a Ref type there is an index i, which gives us the necessary indirection, but here the Tuple contains actual Types..? (There also doesn't seem to be a test for getTempTupleType.)

This is for when you need to create a tuple of temporary types, for example when constructing a function signature. You can't create a normal tuple type for that because that would allow references to the temporary types to leak out into the global type store. In the worst case, a signature type created later could be canonicalized to a type that refers to the original temporary types which have long since become invalid.

I think I see. Is this an internal API then (and therefore not tested as part of the public API)?

No, wait, the user needs to create those tuples, for each function..?

Right, users need to do this. I forgot to say that I will add a test for this 👍

Hmm, why are tuples different than everything else, though? The others all get size_t i.

Tuples don't have associated HeapTypes, so they don't need to take a heap type index. They still need to be backed by the TypeBuilder's TypeStore, though.

aheejin

Haven't finished reading, but some initial basic questions.. I might be missing some key understanding.

aheejin · 2020-12-10T05:24:41Z

+(ref $sig) => (ref (func (param (ref (struct (field (ref null (array (mut externref))) (mut (ref extern)))))) (result (ref (array (mut externref))) i32)))
+(ref $struct) => (ref (struct (field (ref null (array (mut externref))) (mut (ref extern)))))
+(ref $array) => (ref (array (mut externref)))
+(ref null $array) => (ref null (array (mut externref)))


What does 'building types" do? These seems to be the same as "After setting heap types" already. Also I wonder how can refStruct be already referring to the array type at this point, given that it was constructed with a dummy empty refArray?

The "building" step replaces the temporary types and heap types with permanent types and heap types. There is no way to differentiate between temporary and permanent types while printing, unfortunately.

refStruct was initialized by line builder.setHeapType(1, struct_);, which replaces the HeapTypeInfo backing the HeapType that refStruct refers to. This mutability of HeapTypeInfos is the key feature of the TypeBuilder that allows it to create types before the types they depend on have been created.

aheejin · 2020-12-10T05:41:12Z

+  Type refStruct = builder.getTempRefType(1, false);
+  Type refArray = builder.getTempRefType(2, false);
+  Type refNullArray = builder.getTempRefType(2, true);
+  Type refExt(HeapType::ext, false);


Unrelated to this PR, but why is this not extern and ext? I think it would be less confusing to follow the spec's names.. (Not necessarily in this PR though)

Unfortunately we can't use extern because it is a keyword. Between the alternatives extern_ and ext I thought ext looked better, but perhaps the ugliness of extern would be worth the clarity. @kripken, what do you think about this? I'd be happy to change it if we collectively think extern_ would be better.

I have a slight preference to extern_.

Sounds good. I'll make this change in a followup 👍

aheejin · 2020-12-10T09:56:03Z

+Type TypeBuilder::getTempRttType(size_t i, uint32_t depth) {
+  assert(i < impl->entries.size() && "Index out of bounds");
+  return impl->typeStore.canonicalize(Rtt(depth, impl->entries[i].get()));
+}


Maybe add tests that use this method too?

aheejin · 2020-12-10T10:04:19Z

+  assert(refSig != newRefSig);
+  assert(refStruct != newRefStruct);
+  assert(refArray != newRefArray);
+  assert(refNullArray != newRefNullArray);


Why should these be different? The printing results in type-builder.txt look the same..

The types on the left are temporary types whose lifetime ends with the TypeBuilder and the types on the right are permanent globally canonical types.

aheejin · 2020-12-10T10:14:48Z

+// temporary types.
+struct TypeBuilder {
+  struct Impl;
+  std::unique_ptr<Impl> impl;


Why not just Impl impl;?

We need to hide the definition of Impl in the .cpp file because it depends on implementation details like HeapTypeInfo. We can't do that and have Impl impl; because hiding the definition necessarily makes Impl and incomplete type at this point. This is the classic PImpl idiom.

aheejin · 2020-12-10T10:19:41Z

+      Type* type;
+      HeapType* heapType;
+    };
+    Item(Type* type) : kind(TypeKind), type(type) {}


Do we use this for Type too?

Yes, notice that scanHeapType records Type*s to scan in the future and scanType records both HeapType* and Type* (the latter in the tuple case).

aheejin · 2020-12-10T10:24:03Z

+  // The work list of Types and HeapTypes remaining to be scanned.
+  std::vector<Item> scanList;
+
+  // The list of Types and HeapTypes to visit (in forward preorder).


Different comments say different things, such as postorder, reverse postorder, and forward preorder. Are they referring to the same thing or different things?

Yeah sorry I can clear that up. The list stored in forward preorder as this comment says, but then it is finally traversed from back to front, giving reverse postorder. I'll clarify that here and use "reverse postorder" everywhere I am currently just using "postorder."

aheejin · 2020-12-10T10:27:24Z

+  };
+
+  // IDs of scanned Types and HeapTypes, used to prevent repeated scanning.
+  std::unordered_set<TypeID> scanned;


Why not just Type instead of TypeID? TypeID or the fact that Type is an interned ID seems to be an implementation detail of Type class. The same for reaches map below.

Because it needs to refer to HeapTypes as well. This gives a simple way to store both in the same collection where we don't need to be able to differentiate them because we know that no compound Type and HeapType will ever have the same ID. I used the same trick in reaches.

aheejin · 2020-12-10T11:27:38Z

+  // (type $struct (struct (field (ref null $array) (mut ref extern))))
+  // (type $array (array (mut ref null extern)))


Suggested change

// (type $struct (struct (field (ref null $array) (mut ref extern))))

// (type $array (array (mut ref null extern)))

// (type $struct (struct (field (ref null $array) (mut externref))))

// (type $array (array (mut externref)))

Nit: For simplicity (and also to match the output below)

Good catch, thanks! I'll replace the second one (ref null extern), but the first one ref extern is not the same as externref because it is non-nullable.

tlively · 2020-12-10T19:31:35Z

I believe I have addressed all of the feedback so far 👍

kripken · 2020-12-10T20:01:32Z

Nice work!

I have some thoughts for possible followups as mentioned earlier, but nothing urgent, and we can discuss those separately.

tlively requested review from aheejin and kripken December 3, 2020 03:53

kripken reviewed Dec 3, 2020

View reviewed changes

tlively mentioned this pull request Dec 5, 2020

Intern HeapTypes and clean up types code #3428

Merged

tlively added 3 commits December 8, 2020 19:06

Merge remote-tracking branch 'origin/master' into type-builder

675d24e

NFC tweaks

ed3d6a6

Expand on another comment

1da4ccb

kripken reviewed Dec 9, 2020

View reviewed changes

tlively added 2 commits December 9, 2020 15:51

Merge remote-tracking branch 'origin/master' into type-builder

f87508d

Address comments

a38b630

aheejin reviewed Dec 10, 2020

View reviewed changes

tlively added 2 commits December 10, 2020 08:28

Test temporary RTTs

826333d

Fix pre/post-order comments

4e9e4ee

kripken approved these changes Dec 10, 2020

View reviewed changes

tlively merged commit e1978e0 into WebAssembly:master Dec 11, 2020

tlively deleted the type-builder branch December 11, 2020 00:42

tlively mentioned this pull request Feb 2, 2021

Recursive Types #3063

Closed

	void Canonicalizer::makeReachabilityFixpoint() {
	void Canonicalizer::makeReachabilityFixedPoint() {

		// (type $struct (struct (field (ref null $array) (mut ref extern))))
		// (type $array (array (mut ref null extern)))

Conversation

tlively commented Dec 3, 2020

Uh oh!

kripken left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

tlively commented Dec 3, 2020

Uh oh!

tlively commented Dec 9, 2020

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

aheejin left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tlively Dec 10, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

aheejin left a comment •

edited

Loading

tlively Dec 10, 2020 •

edited

Loading