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 · 3 comments
Open

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

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

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
@findleyr findleyr modified the milestones: Go1.23, Go1.24 May 14, 2024
@findleyr
Copy link
Contributor Author

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

@cuonglm cuonglm mentioned this issue Jul 17, 2024
Closed
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.24
Development

No branches or pull requests
2 participants
@mdempsky @findleyr