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

[findleyr]

As mentioned in #60817 (comment)_:

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 #60817 (comment)

[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.

[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.

[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).

[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.

[gopherbot]

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