At a certain level nested generics cause causes the typechecker to get stuck

[deech]

trafficstars

What happened?

This is a contrived example but please bear with me, it was difficult to distill a more minimal reproduction for this bug, it seems at a certain level of generics nesting the typechecker stops being able to deduce any further types and is stuck:

type
  Payload[T] = object
    payload: T
  Carrier[T] = object
    val: T

type
  Payload0*[T] = object
    payload: Payload[T]
  Payload1*[T] = object
    payload: Payload[T]
  Payload2*[T] = object
    payload: Payload[T]
  Payload3*[T] = object
    payload: Payload[T]
  Payload4*[T] = object
    payload: Payload[T]
  Payload5*[T] = object
    payload: Payload[T]
  Payload6*[T] = object
    payload: Payload[T]
  Payload7*[T] = object
    payload: Payload[T]
  Payload8*[T] = object
    payload: Payload[T]
  Payload9*[T] = object
    payload: Payload[T]
  Payload10*[T] = object
    payload: Payload[T]
  Payload11*[T] = object
    payload: Payload[T]
  Payload12*[T] = object
    payload: Payload[T]
  Payload13*[T] = object
    payload: Payload[T]
  Payload14*[T] = object
    payload: Payload[T]
  Payload15*[T] = object
    payload: Payload[T]
  Payload16*[T] = object
    payload: Payload[T]
  Payload17*[T] = object
    payload: Payload[T]
  Payload18*[T] = object
    payload: Payload[T]
  Payload19*[T] = object
    payload: Payload[T]
  Payload20*[T] = object
    payload: Payload[T]
  Payload21*[T] = object
    payload: Payload[T]
  Payload22*[T] = object
    payload: Payload[T]
  Payload23*[T] = object
    payload: Payload[T]
  Payload24*[T] = object
    payload: Payload[T]
  Payload25*[T] = object
    payload: Payload[T]
  Payload26*[T] = object
    payload: Payload[T]
  Payload27*[T] = object
    payload: Payload[T]
  Payload28*[T] = object
    payload: Payload[T]
  Payload29*[T] = object
    payload: Payload[T]
  Payload30*[T] = object
    payload: Payload[T]
  Payload31*[T] = object
    payload: Payload[T]
  Payload32*[T] = object
    payload: Payload[T]
  Payload33*[T] = object
    payload: Payload[T]
  Payload34*[T] = object
    payload: Payload[T]

type
  Carriers*[T] = object
    c0*: Carrier[Payload0[T]]
    c1*: Carrier[Payload1[T]]
    c2*: Carrier[Payload2[T]]
    c3*: Carrier[Payload3[T]]
    c4*: Carrier[Payload4[T]]
    c5*: Carrier[Payload5[T]]
    c6*: Carrier[Payload6[T]]
    c7*: Carrier[Payload7[T]]
    c8*: Carrier[Payload8[T]]
    c9*: Carrier[Payload9[T]]
    c10*: Carrier[Payload10[T]]
    c11*: Carrier[Payload11[T]]
    c12*: Carrier[Payload12[T]]
    c13*: Carrier[Payload13[T]]
    c14*: Carrier[Payload14[T]]
    c15*: Carrier[Payload15[T]]
    c16*: Carrier[Payload16[T]]
    c17*: Carrier[Payload17[T]]
    c18*: Carrier[Payload18[T]]
    c19*: Carrier[Payload19[T]]
    c20*: Carrier[Payload20[T]]
    c21*: Carrier[Payload21[T]]
    c22*: Carrier[Payload22[T]]
    c23*: Carrier[Payload23[T]]
    c24*: Carrier[Payload24[T]]
    c25*: Carrier[Payload25[T]]
    c26*: Carrier[Payload26[T]]
    c27*: Carrier[Payload27[T]]
    c28*: Carrier[Payload28[T]]
    c29*: Carrier[Payload29[T]]
    c30*: Carrier[Payload30[T]]
    c31*: Carrier[Payload31[T]]
    c32*: Carrier[Payload32[T]]
    c33*: Carrier[Payload33[T]]
    c34*: Carrier[Payload34[T]]

var carriers : Carriers[int]

proc printPayload33[T](p:Payload33[T]) = echo p.payload.payload
proc printPayload34[T](p:Payload34[T]) = echo p.payload.payload

printPayload33(carriers.c33.val)
# printPayload34(carriers.c34.val)

printPayload33(carriers.c33.val) fails with:

> nim c -r --verbosity\:0 --hint\[Processing\]\:off --excessiveStackTrace\:on /tmp/test.nim
/tmp/test.nim(122, 15) Error: type mismatch: got <Payload32[system.int]>
but expected one of:
proc printPayload33[T](p: Payload33[T])
  first type mismatch at position: 1
  required type for p: Payload33[printPayload33.T]
  but expression 'carriers.c33.val' is of type: Payload32[system.int]

expression: printPayload33(carriers.c33.val)

but so does printPayload34(carriers.c34.val). At this point any further Carrier[Payload*[T]] fields added to the Carrier object are stuck at Payload32[system.int].

Nim Version

Nim Compiler Version 1.7.1 [Linux: amd64]
Compiled at 2022-09-13
Copyright (c) 2006-2022 by Andreas Rumpf

git hash: 7c85b500df69cf5c5856549dafe59d7b619e8b26
active boot switches: -d:release

Current Standard Output Logs

No response

Expected Standard Output Logs

No response

Possible Solution

No response

Additional Information

No response

[deech]

@Araq We talked about this yesterday but the repro shows it's not a type aliasing issue as we previously thought since objects are nominally typed.

[deech]

This is a more realistic repro but it's less contained:

import std/[options]
type
  F1*[T] = object
    call: proc(self:T,callback:proc(self:T))
  F2*[T] = object
    call: proc(self:T,callback:proc(self:T))
  F3*[T] = object
    call: proc(self:T,callback:proc(self:T))

type
  Functions*[T] = object
    a*: Option[F1[T]]
    b*: Option[F1[T]]
    c*: Option[F1[T]]
    d*: Option[F1[T]]
    e*: Option[F1[T]]
    f*: Option[F1[T]]
    g*: Option[F1[T]]
    h*: Option[F1[T]]
    i*: Option[F2[T]]
    j*: Option[F3[T]]

var fs : Functions[int]
fs.j.map(proc(f:F3[int]) = discard)

it fails with:

/tmp/test.nim(25, 4) template/generic instantiation of `map` from here
/home/deech/Nim/lib/pure/options.nim(250, 13) Error: type mismatch: got <F2[system.int]>
but expected one of:
proc (input: F3[system.int]){.closure.}

[deech]

This is happening due to the hardcoded recursionLimit. After it crosses the 100 threshold the previous instantiation of the generic type is retrieved from the cache causing the typechecker bug. I could use some guidance on how to address this.