Description
Original comment: #5236 (comment).
Currently, the compiler's type checker reject specializations of form X<...X<...>...>, i.e. a generic occurring anywhere inside its generic parameter. This seems too restrictive.
I think there are multiple things going on:
- The check seems to be introduced to avoid externs parametrized by themselves. I'm not sure what is the motivation for extern types being parametrized by extern types in general, but there might be some. Frankly both cases seem to me like something that should be an architecture-specific check, not a generic one.
- For structures (and headers), this could be allowed. The same way I can have
std::array<std::array<int, 4>, 4>in C++, I should be able to have a nested generic value type in P4.- I'm not sure what introduces the IR loop, that seems like a separate bug that would have to be fixed to allow things like
Foo<Foo<int>>.As far as I can see, the spec does not prohibit any of this.
See also: #819, #1296, #3291, #5236.
My proposal for fix is:
- Type checker should accept these types under normal type checking rule.
- Type specialization pass (for structs, headers) should be able to expand them.
- We may add a midend pass that rejects externs with self-nested externs, or externs with nested externs completely, but I would be much happier if backends did this (they have to validate type parameters for externs anyway as there are usually stronger requirements than just "not being recusively the same extern).
Note that these are not automatically recursive types. For example in Gen<Gen<Val>>, if Gen<Val> is a valid type, then there is no reason Gen<Gen<Val>> is not a valid type. Instead, these are inductively defined -- Val is a "base case" and "Gen" is the "induction case". Or you can see them as grammars, with Val being a terminal and Gen<...> being a rule. A recursive type would be something like:
struct Str {
int<4> x;
Str str;
}which is correctly rejected
test.p4(3): [--Werror=unsupported] error: Self-referencing types not supported: 'Str' within 'struct Str'
Str str;
^^^
test.p4(1)
struct Str {
^^^Note that you can't use generics to construct recursive type as self-referencing is forbidden also if I replace Str with Str<T> and without using the Str in its definition I cannot construct recursion1.
Of course, the problem with truly recursive types is that (in absence of pointers/boxing) they have infinite size, so they are useless. Our case is much different, we just refer to the same generic twice, but each time the generic creates a distinct type.
Footnotes
-
Unless I have type-level fixed-point operator, which of course I don't have in P4. ↩