Require continuation types to come after the referenced signature type?

[titzer]

I think that without loss of generality we can require (in the binary format) that the definition of continuation types come after the definition of the signature type they reference. This would make a minor simplification in canonicalization of recursive continuation types.

We do have precedent for this in that, for all heap type definitions, we require their supertype definition, if any, to appear before them.

[fgmccabe]

continuation types & the signature types they reference can be mutually recursive. So, what sort of simplification are you referring to?

[tlively]

In all other instances where we disallow forward references, it's because we specifically wish to disallow cycles. I think it's right that we could make this change, but I don't think it's worth it. In particular, there are a few places in Binaryen's code base that have to topologically sort types, either to optimize the assigned indexes for code size or to ensure uniqueness of a minimized rec group by iterating through all valid orders of its types. Unnecessarily constraining the order of types both requires updating this code to consider more kinds of edges and potentially decreases the quality of the results.

[titzer]

@fgmccabe Yes, they can be recursive, but continuation types are defined by referring to a previous heap type index that is required to be a signature. Continutation types can only recurse through signature declarations, not directly. By requiring the continuation type declaration to come after the signature, it means that well-formedness check (i.e. that the index refers to a signature and not a struct or an array) can be performed immediately, rather than when resolving forward references. Concretely, its a little less forward-substitution logic in the validator, and avoids introducing another check when doing those substitutions[1].

I don't think requiring a backward index is a big burden on producers; a continuation type can always be declared right after its corresponding signature, within the same recursion group if necessary.

[1] With current Wasm, the similar well-formedness check for struct and array declarations (that supertypes are structs and compatible structs) be done during canonicalization, and at the forward substitution stage.

[fgmccabe]

I see. In fact, I complained to Andreas about this exact issue :)
I had to add in an extra loop in the type decoder.

It does, however, mess up the neat syntax though: requiring the special ordering.