recursive generic type results in wrong type

[zerbina]

Using a recursive generic type as a type operand while it's still being instantiated results in the generic cache yielding the wrong instance.

Example

type
  Other[U] = object
  Type[T] = object
    a: Other[T]
    b: Other[Type[T]] # valid, no recursion in the physical type layout

var x: Type[int]
doAssert x.a is Other[int]
doAssert x.b is Other[Type[int]]

Actual Output

Error: unhandled exception: test.nim(12, 10) `x.b is Other[Type[int]]`  [AssertionDefect]

Expected Output

Compiles and runs successfully.

Additional Information

The reason this happens is due to how generic type instantiation works.

When evaluating an generic invocation (e.g., Other[int]), the generic type cache is first consulted on an instance of Other with argument int already exists. If it doesn't a new tyGenericInst is created and added to the cache.

A proper tyGenericInst is structured as follows:

1. the first slot stores the generic type that is applied to the operands
2. the following slots (excluding the last slot) store the concrete operands
3. the last slot stores the resolved type

When first creating the tyGenericInst type and adding it to the cache, the resolved type is not yet known, meaning that it cannot be added already. This temporarily leaves the tyGenericInst in an improper state.

When performing a generic type instance cache lookup, the operands of the cached instances are compared against the resolved operands of the looked-up invocation. Since compareTypes (the procedure used to compare types in this case) assumes tyGenericInst types to be proper, it treats the tyGenericInst as the type in the last slot, which is normally the resolved type, but for improper instance types, it's the last operand.

This means that - using the example snippet from above - for the Other[Type[T]] invocation, the lookup happens with Type[int] as the operand, which at this time is still improper. An instance of Other with the operand int exists already, and since skipping Type[int] at this stage results in int, the cache lookup succeeds, leaving b as having type Other[int] (instead of Other[Type[int]]).

Note that while tyGenericInst types have unique IDs, the cache lookup cannot simply use an ID comparison, as it is interested in whether the operands are equal, not whether they're the same.

Potential solutions are complicated due to the existence of ref object and ptr object type definitions, which prevent the instantiation logic from making a clear structural vs. nominal distinction (partial completion of nominal types is possible and would help in most cases, but not all).