The other method above is "canonicalize" but it both canonicalizes and inserts. Perhaps it could be renamed to be more consistent with this name? canonicalizeAndInsert vs just insert perhaps?

canonicalize does not take ownership of anything because it copies the type info object, so I think it's current name describes its intended interface. I got rid of this new method, though.

Can we do the same for all types? I understand this is needed for recursive types, but if it's possible for non-recursive ones as well that could be simpler.

If we end up partially or wholly switching to nominal types, it would make sense to move ownership of the nominal types from the canonicalizing global stores to the individual Modules. But for structural types, deduplication is a matter of correctness. If the proposal keeps fully structural typing, we will have to implement canonicalization of recursive types at some point as well.

Oh, I see, I didn't get that before. So this does not canonicalize recursive types despite it being technically incorrect, but it may be good enough for now? (Why is it good enough for now?)

This should be good enough for now because producers will generally emit one type declaration per source type and not deduplicate or mix the two. Because producers don’t treat the types as interchangeable, it’s ok that Binaryen doesn’t either. Another piece is that for now neither Binaryen nor the producers are dealing with systems of multiple modules. If they were, it would be important for Binaryen to recognize when the same type is declared in multiple modules, which would require properly canonicalizing recursive types.

Also capturing kv.second to a local would give it a name which could be more readable I think.

Can this loop be on fixedPoint? Basically the set we care about is { x \in children(x) | x \in AllThings } so I'm not sure why this starts with builder.impl->entries.

If we looped over fixedPoint, we would have to first traverse it to collect a set of all TypeIDs it references and at some point we would also have to check whether each TypeID corresponded to a HeapType. In contrast, the HeapTypes correspond 1:1 to builder entries, so it takes less code find them that way.

I see, sounds good.

I don't know if this matters much, but for performance I suspect the reversed loops might be faster. I am assuming that most types are not self-referential - does that sound reasonable?

If so, then cache locality would benefit from having the inner loop be on the smaller thing, selfReferentialHeapTypes. But then you'd need two loops to avoid iterator invalidation I guess,

for (auto& kv : childrenDAG) {
  kv.second.erase(selfReferentialHeapTypes.begin(), selfReferentialHeapTypes.end());
}
childrenDAG.erase(selfReferentialHeapTypes.begin(), selfReferentialHeapTypes.end());

IIUC, the variant of the erase method that takes iterators only accepts iterators into the collection it is being called on. So I don't think it's valid to pass iterators of selfReferentialHeapTypes to the erase method of the sets in childrenDAG. I could still invert the loops, but then there would be more loops overall :( Overall I prefer the current version.

  for (TypeID id : selfReferentialHeapTypes) {
    childrenDAG.erase(id);
  }
  for (auto& kv : childrenDAG) {
    for (TypeID id : selfReferentialHeapTypes) {
      kv.second.erase(id);
    }
  }

Oh right, I mixed up that API...

Given it's more code it's not worth doing this possible optimization now, I agree. Maybe a TODO to investigate? Then if we profile in the future and see this function is slow, we'd have a hint.