Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Open
findleyr opened this issue Sep 28, 2023 · 2 comments
Open

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

findleyr opened this issue Sep 28, 2023 · 2 comments
Assignees
@mdempsky @findleyr
Labels
NeedsFix The path to resolution is known, but the work has not been done.
Milestone
Go1.23

Comments

@findleyr
Copy link
Contributor

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
Copy link
Contributor Author

@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 findleyr added the NeedsFix The path to resolution is known, but the work has not been done. label Sep 28, 2023
@findleyr findleyr added this to the Go1.22 milestone Sep 28, 2023
@findleyr
Copy link
Contributor Author

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 findleyr modified the milestones: Go1.22, Go1.23 Nov 9, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@mdempsky mdempsky

@findleyr findleyr

Labels
NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Milestone
Go1.23
Development

No branches or pull requests
2 participants
@mdempsky @findleyr