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

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

Comment From: 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.

Comment From: 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.

Comment From: findleyr

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

Comment From: mrkfrmn

Reading through some of the code, I think I have to agree with @findleyr above — SetConstraint specifically documents that the bound must be fully resolved.

Yet, examining the stack trace, it's clear that the type parameters are still just Named types — hence their instantiation information is still nil. We get back around to the same Named instance and try to lock again on the same mutex, deadlocking.

It seems that we did ensure SetUnderlying was called prior for go/types but didn't do the same for types2.

Comment From: mrkfrmn

I messed with the reproducer above to try and distill it, reaching this. Notably, Bar does need to be generic for this to deadlock, which is a bit interesting.

Similarly, if we move the definition of Foo / Bar around, we can see that errors do change (per #68025).

Comment From: mrkfrmn

Tried out a somewhat trivial port of the later functionality into the compiler — we get some new issues that I believe are related to differences in how object types get imported. Looks like around August 2022 we implemented some simplifications to handling IR in the standard library, but not the compiler.

In short, we might need to bring over a bit more than initially suspected.

Comment From: gopherbot

Change https://go.dev/cl/667215 mentions this issue: go/types2: reduce gap between uimporter implementations

Comment From: mrkfrmn

I spent a bit of time tracing this. Here is a slightly better reproducer. I'll paste the important bit here:

type A[_ B[any]] struct {}

type B[_ any] interface {
  f() A[B[any]]
}

What happens: 1. resolve() is called on A; A is now locked. 2. Because A is coming from an importer, the lazy loader for A is called. 3. The loader examines the type parameters for A, finding an instantiation B[any]. 4. SetConstraint is called on B[any] despite it being merely instantiated, not expanded (also lazy). 5. expandUnderlying is called on B[any]. 6. resolve() is called on the origin, B (an Interface). It sees the result A[B[any]], which is a Named. 7. TypeParameters is called on A — the origin for A[B[any]]. 8. resolve() is called on A, deadlocking.

And so the issue is indeed on step 4. The later mechanism solves this by establishing 2 different phases. In the first phase, we set up origin and instantiated types. In the second, we expand the instantiations.

Perhaps naive, but I don't immediately see why we couldn't use the same lifecycle within a loader function.

Comment From: mrkfrmn

I've thought about it more; it's quite a subtle issue.

The same exact lifecycle won't work, but a modification will. - In eager loading, no locks are held when SetConstraint is called. - In lazy loading, a lock is held on an unresolved type when SetConstraint is called.

Instead, I think A should advance its state between the loader returning and any calls to SetConstraint. We will still loop back around to A, but simply return rather than deadlock.

The loader needs a way to tell the caller "run these functions after you set up this type", but that seems basic. We can use the same approach in the eager loader for ubiquity.

Thus the flow becomes: 1. resolve() called on A, A is locked. 2. Lazy loader for A called. 3. Examines instantiation B[any]. 4. Shelves the SetConstraint call for B[any]. 5. Loader returns. 6. A advances state. 7. Shelved SetConstraint calls invoked. 8. expandUnderlying called on B[any]. 9. resolve() called on B, result A[B[any]] spotted. 10. TypeParameters called on A. 11. resolve() called on A, returns. 12. B advances state. 13. A advances state.

I'll put this together and run some tests, but I don't see why this wouldn't work.