cmd/compile/internal/importer: deadlock in recursion through type parameter

[findleyr]

As mentioned in https://github.com/golang/go/issues/60817#issuecomment-1728279951_:

I'm coming here from Stack Overflow, where someone has just reported what seems like a very similar compiler bug. I haven't had time to investigate/reduce the problem, but compilation (with Go 1.21.1, at the very least) of the following invalid program fails with a deadlock:

package main

import "whatever/vector"

func main() {
    s := vector.New[int]()
    println(s)
}
-- go.mod --
module whatever
-- iterator/iterator.go --
package iterator

type Iter[I any, T Iterator[I]] struct {
    Iter T
}

func New[I any, T Iterator[I]](iter T) Iter[I, T] {
    return Iter[I, T]{
        Iter: iter,
    }
}

type Iterator[Item any] interface {
    HasNext() bool
    Next() Item
    Iter() Iter[Item, Iterator[Item]]
}
-- vector/vector.go --
package vector

import "whatever/iterator"

type Vector[Item any] struct {
    data []Item

    // used by iterator.
    idx int
}

func (v *Vector[Item]) Get(pos int) Item {
    if pos < 0 || pos >= v.Size() {
        panic("ouf off range")
    }

    return v.data[pos]
}

func (v *Vector[Item]) HasNext() bool {
    return v.idx < v.Size()
}

func (v *Vector[Item]) Next() Item {
    v.idx = v.idx + 1

    return v.Get(v.idx - 1)
}

func (v *Vector[Item]) Iter() iterator.Iter[Item, iterator.Iterator[Item]] {
    return iterator.Iter[Item, iterator.Iterator[Item]]{
        Iter: v,
    }
}

Output:

fatal error: all goroutines are asleep - deadlock!

goroutine 1 [sync.Mutex.Lock]:
sync.runtime_SemacquireMutex(0xced180?, 0xd0?, 0xc0000bd3e5?)
    runtime/sema.go:77 +0x25
sync.(*Mutex).lockSlow(0xc00039e338)
    sync/mutex.go:171 +0x15d
sync.(*Mutex).Lock(...)
    sync/mutex.go:90
cmd/compile/internal/types2.(*Named).resolve(0xc00039e310)
    cmd/compile/internal/types2/named.go:164 +0x6c
cmd/compile/internal/types2.(*Named).TypeParams(...)
    cmd/compile/internal/types2/named.go:310
cmd/compile/internal/types2.(*subster).typ(0xc0000bdd10, {0xec6108?, 0xc00039e5b0?})
    cmd/compile/internal/types2/subst.go:223 +0xd72
cmd/compile/internal/types2.(*subster).var_(0x0?, 0xc00039e620)
    cmd/compile/internal/types2/subst.go:285 +0x2c
cmd/compile/internal/types2.(*subster).varList(0x2?, {0xc000044620, 0x1, 0x0?})
    cmd/compile/internal/types2/subst.go:311 +0x85
cmd/compile/internal/types2.(*subster).tuple(0xc0000bd908?, 0xc00036bc38)
    cmd/compile/internal/types2/subst.go:301 +0x2f
cmd/compile/internal/types2.(*subster).typ(0xc0000bdd10, {0xec60e0?, 0xc00039ca00?})
    cmd/compile/internal/types2/subst.go:143 +0x50c
cmd/compile/internal/types2.(*subster).func_(0x4075ee?, 0xc00039e690)
    cmd/compile/internal/types2/subst.go:328 +0x2c
cmd/compile/internal/types2.(*subster).funcList(0x462ccb?, {0xc00036bbd8, 0x3, 0xd34c80?})
    cmd/compile/internal/types2/subst.go:345 +0x85
cmd/compile/internal/types2.(*subster).typ(0xc0000bdd10, {0xec6270?, 0xc000394cd0?})
    cmd/compile/internal/types2/subst.go:167 +0x70f
cmd/compile/internal/types2.(*Checker).subst(0x0, {0x0?, 0x63780?, 0xc0?}, {0xec6270?, 0xc000394cd0}, 0xc000397020, 0xc00039e3f0, 0x0)
    cmd/compile/internal/types2/subst.go:78 +0x1ab
cmd/compile/internal/types2.(*Named).expandUnderlying(0xc00039e3f0)
    cmd/compile/internal/types2/named.go:623 +0x4e5
cmd/compile/internal/types2.(*Named).resolve(0xc00039e3f0)
    cmd/compile/internal/types2/named.go:177 +0x172
cmd/compile/internal/types2.(*Named).Underlying(...)
    cmd/compile/internal/types2/named.go:456
cmd/compile/internal/types2.(*Named).under(...)
    cmd/compile/internal/types2/named.go:484
cmd/compile/internal/types2.under({0xec6108?, 0xc00039e3f0?})
    cmd/compile/internal/types2/under.go:13 +0x5a
cmd/compile/internal/types2.(*TypeParam).iface(0xc000396d20)
    cmd/compile/internal/types2/typeparam.go:109 +0x31
cmd/compile/internal/types2.(*TypeParam).SetConstraint(...)
    cmd/compile/internal/types2/typeparam.go:86
cmd/compile/internal/importer.(*reader).typeParamNames(0xc000393260)
    cmd/compile/internal/importer/ureader.go:510 +0x214
cmd/compile/internal/importer.(*pkgReader).objIdx.func1.1(0x0?)
    cmd/compile/internal/importer/ureader.go:430 +0x25
cmd/compile/internal/types2.(*Named).resolve(0xc00039e310)
    cmd/compile/internal/types2/named.go:203 +0x10e
cmd/compile/internal/types2.(*Named).TypeParams(...)
    cmd/compile/internal/types2/named.go:310
cmd/compile/internal/types2.isGeneric({0xec6108?, 0xc00039e310?})
    cmd/compile/internal/types2/predicates.go:128 +0x46
cmd/compile/internal/types2.(*Checker).genericType(0xc0001241e0, {0xec84e0, 0xc000394640}, 0xc0000be438)
    cmd/compile/internal/types2/typexpr.go:196 +0xb1
cmd/compile/internal/types2.(*Checker).instantiatedType(0xc0001241e0, {0xec84e0?, 0xc000394640}, {0xc000063480?, 0x2, 0x2}, 0x0)
    cmd/compile/internal/types2/typexpr.go:415 +0x20a
cmd/compile/internal/types2.(*Checker).typInternal(0xc0001241e0, {0xec84a0?, 0xc000392660?}, 0x0)
    cmd/compile/internal/types2/typexpr.go:275 +0x1212
cmd/compile/internal/types2.(*Checker).definedType(0xc0001241e0, {0xec84a0?, 0xc000392660}, 0x1?)
    cmd/compile/internal/types2/typexpr.go:180 +0x3f
cmd/compile/internal/types2.(*Checker).varType(0xc0001241e0, {0xec84a0?, 0xc000392660})
    cmd/compile/internal/types2/typexpr.go:144 +0x33
cmd/compile/internal/types2.(*Checker).collectParams(0xc0001241e0, 0xc00039e1c0, {0xc0000444c0?, 0x1, 0xd40fc0?}, 0x0)
    cmd/compile/internal/types2/signature.go:284 +0x2ea
cmd/compile/internal/types2.(*Checker).funcType(0xc0001241e0, 0xc00039c5c0, 0xc00007bef0, {0x0?, 0x0, 0x0}, 0xc0000ab420)
    cmd/compile/internal/types2/signature.go:179 +0xaf1
cmd/compile/internal/types2.(*Checker).funcDecl(...)
    cmd/compile/internal/types2/decl.go:730
cmd/compile/internal/types2.(*Checker).objDecl(0xc0001241e0, {0xecca80, 0xc0000ab810}, 0x4f6edc?)
    cmd/compile/internal/types2/decl.go:203 +0xa1a
cmd/compile/internal/types2.(*Checker).packageObjects(0xc0001241e0)
    cmd/compile/internal/types2/resolver.go:705 +0x465
cmd/compile/internal/types2.(*Checker).checkFiles(0xc0001241e0, {0xc0000444d0, 0x1, 0x1})
    cmd/compile/internal/types2/check.go:371 +0x21e
cmd/compile/internal/types2.(*Checker).Files(...)
    cmd/compile/internal/types2/check.go:332
cmd/compile/internal/types2.(*Config).Check(0xc000392840, {0x7fff3cb4fc93?, 0x139f2e0?}, {0xc0000444d0, 0x1, 0x1}, 0xc0003928a0)
    cmd/compile/internal/types2/api.go:437 +0x14f
cmd/compile/internal/noder.checkFiles({0x0, {0x0, 0x0}}, {0xc000044450, 0x1, 0x18?})
    cmd/compile/internal/noder/irgen.go:70 +0x486
cmd/compile/internal/noder.writePkgStub({0x0?, {0x0?, 0x0?}}, {0xc000044450, 0x1, 0x1})
    cmd/compile/internal/noder/unified.go:210 +0x6a
cmd/compile/internal/noder.unified({0x0?, {0x0?, 0x0?}}, {0xc000044450?, 0xcb9f20?, 0xc0000bf8f8?})
    cmd/compile/internal/noder/unified.go:75 +0x85
cmd/compile/internal/noder.LoadPackage({0xc000022260, 0x1, 0x2})
    cmd/compile/internal/noder/noder.go:77 +0x450
cmd/compile/internal/gc.Main(0xda33e8)
    cmd/compile/internal/gc/main.go:198 +0xc17
main.main()
    cmd/compile/main.go:57 +0xf9

Go build failed.

Here is a Playground where you can reproduce the problem.

Originally posted by @jub0bs in https://github.com/golang/go/issues/60817#issuecomment-1728279951

[findleyr]

@mdempsky in this case I think there is a bug in the unified reader (in the compiler only): specifically here: https://cs.opensource.google/go/go/+/master:src/cmd/compile/internal/importer/ureader.go;l=510;drc=6cf6067d4eb20dfb3d31c0a8ccdbfdf0bf304b72

In this case, SetConstraint is called during the set-up of the parent named type, but (for better or worse) is documented that it should be called only after "the bound's underlying is fully defined". https://pkg.go.dev/cmd/compile/internal/types2#TypeParam.SetConstraint

The go/types unified importer calls SetConstraint in a later: https://cs.opensource.google/go/go/+/master:src/go/internal/gcimporter/ureader.go;l=618;drc=0cd309e12818f988693bf8e4d9f1453331dcf9f2

Can we do the same in the compiler? The obvious alternative is to make the bound calculation lazy, and that is liable to have a larger blast radius than pushing additional complexity into the importer.

[findleyr]

CC @griesemer as well.

Tentatively marked this for 1.22, as I think this bug has existed for a long time; if the fix proves to be safe, perhaps we can back-port.

[findleyr]

This didn't make 1.23, unfortunately. Moving to 1.24.