Type recursion

[bathos]

This question began over at WebAssembly interface types, where I noticed the claim that “WebIDL [...] does not support recursive types.” I was surprised by that because I am fairly certain that it does (as currently specified) — but at the same time, I’m not actually certain that it is meant to, as I’m unaware of any APIs currently leveraging it.

Specifically, it appears that Web IDL currently permits recursion via most parametric types in some form or another, e.g.

typedef sequence<(DOMString or StringTree)> StringTree;

// Or “intertype”, e.g.:

typedef sequence<(DOMString or Bar)> Foo;
typedef record<DOMString, Foo> Bar;

The spec appears to forbid tautological typedefs (e.g. typedef Foo Foo;). It also forbids dictionaries from including themselves via parametric types per “includes a dictionary D”. The latter was cited as one of the reasons it had been concluded that Web IDL types do not permit recursion, but this constraint is unique to dictionaries.

I was never certain of the reason for the dictionary constraint apart from a suspicion that it related to default-dictionaries, which is somewhat supported by the context for this PR, though it’s still not clear to me why this would be problematic in the context of sequence or record types. Sequence conversion in particular could be infinite with or without these constraints.

The one clue that I can find suggesting an intent that recursion not be permitted is that “type names” for the parametric types that would otherwise appear to permit recursion do not account for it. While this does suggest the intent, though, the type names are sorta just hypothetical, so I’m not sure it counts for much that some would be infinitely long. The opposite intent is suggested by the special casing of dictionary, though: if recursion were never permitted, I’m unsure why this case would be singled out.

So — is all recursion meant to be prohibited? If so, is there actually anything in the spec prohibiting it? And if not, are there any APIs known to leverage it?

Edit: One possibility is that “The Type must not be the identifier of the same or another typedef” is really supposed to be something like “no Type appearing within TypeWithExtendedAttributes at any depth may reference a typedef” — which would forbid all recursion except dictionary recursion, providing an explanation for why dictionary would still require special casing associated with forbidding recursion. This possibility seems strong given Type doesn’t directly appear in the RHS of Typedef anyway, i.e. something looks weird here regardless.

[tabatkins]

Note that type names were removed in #1132, so that problem is no longer present.