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

x/tools/go/types/typeutil: stack overflow when hashing mutually recursive pointers to type parameters #51314

Closed
dominikh opened this issue Feb 22, 2022 · 5 comments
Closed

x/tools/go/types/typeutil: stack overflow when hashing mutually recursive pointers to type parameters #51314

dominikh opened this issue Feb 22, 2022 · 5 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Soon This needs action soon. (recent regressions, service outages, unusual time-sensitive situations) Tools This label describes issues relating to any tools in the x/tools repository.
Milestone
Unreleased

Comments

@dominikh
Copy link
Member

Input:


-- foo.go --
package main

import (
	"fmt"
	"go/ast"
	"go/parser"
	"go/token"
	"go/types"

	"golang.org/x/tools/go/types/typeutil"
)

const src = `
package pkg

func Fn[T1 ~*T2, T2 ~*T1](t1 T1, t2 T2) {}
`

func main() {
	fset := token.NewFileSet()
	f, _ := parser.ParseFile(fset, "foo.go", src, 0)
	pkg := types.NewPackage("pkg", "pkg")
	c := types.NewChecker(nil, fset, pkg, nil)
	c.Files([]*ast.File{f})

	obj := pkg.Scope().Lookup("Fn")
	fmt.Println(obj.Type())

	h := typeutil.MakeHasher()
	h.Hash(obj.Type())
}
-- go.mod --
module example.com

go 1.18

require golang.org/x/tools v0.1.10-0.20220218145154-897bd77cd717

(Truncated) output:

$ go run foo.go 
func[T1 ~*T2, T2 ~*T1](t1 T1, t2 T2)
runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0xc020180388 stack=[0xc020180000, 0xc040180000]
fatal error: stack overflow

runtime stack:
runtime.throw({0x5a061e?, 0x6ab720?})
	/home/dominikh/prj/go/src/runtime/panic.go:992 +0x71
runtime.newstack()
	/home/dominikh/prj/go/src/runtime/stack.go:1101 +0x5cc
runtime.morestack()
	/home/dominikh/prj/go/src/runtime/asm_amd64.s:547 +0x8b

goroutine 1 [running]:
runtime.typehash(0x594140, 0xc020180460, 0x756ea16a56a621?)
	/home/dominikh/prj/go/src/runtime/alg.go:144 +0x2d2 fp=0xc020180398 sp=0xc020180390 pc=0x403672
runtime.interhash(0x0?, 0x0?)
	/home/dominikh/prj/go/src/runtime/alg.go:111 +0x56 fp=0xc0201803d0 sp=0xc020180398 pc=0x4031b6
runtime.mapaccess2(0x0?, 0x0?, 0x0?)
	/home/dominikh/prj/go/src/runtime/map.go:471 +0xf9 fp=0xc020180410 sp=0xc0201803d0 pc=0x40dd79
golang.org/x/tools/go/types/typeutil.Hasher.Hash({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, {0x5dc400, 0xc0000b6720})
	/home/dominikh/prj/pkg/mod/golang.org/x/tools@v0.1.10-0.20220218145154-897bd77cd717/go/types/typeutil/map.go:244 +0x67 fp=0xc020180478 sp=0xc020180410 pc=0x561ac7
golang.org/x/tools/go/types/typeutil.Hasher.hashTypeParam({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, 0x1?)
	/home/dominikh/prj/pkg/mod/golang.org/x/tools@v0.1.10-0.20220218145154-897bd77cd717/go/types/typeutil/map.go:426 +0x66 fp=0xc0201804b8 sp=0xc020180478 pc=0x562966
golang.org/x/tools/go/types/typeutil.Hasher.hashFor({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, {0x5dc540?, 0xc0000ca7e0?})
	/home/dominikh/prj/pkg/mod/golang.org/x/tools@v0.1.10-0.20220218145154-897bd77cd717/go/types/typeutil/map.go:370 +0x4e7 fp=0xc020180698 sp=0xc0201804b8 pc=0x562067
golang.org/x/tools/go/types/typeutil.Hasher.Hash({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, {0x5dc540, 0xc0000ca7e0})
	/home/dominikh/prj/pkg/mod/golang.org/x/tools@v0.1.10-0.20220218145154-897bd77cd717/go/types/typeutil/map.go:246 +0x91 fp=0xc020180700 sp=0xc020180698 pc=0x561af1
golang.org/x/tools/go/types/typeutil.Hasher.hashFor({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, {0x5dc478?, 0xc000010450?})
	/home/dominikh/prj/pkg/mod/golang.org/x/tools@v0.1.10-0.20220218145154-897bd77cd717/go/types/typeutil/map.go:289 +0x525 fp=0xc0201808e0 sp=0xc020180700 pc=0x5620a5
golang.org/x/tools/go/types/typeutil.Hasher.Hash({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, {0x5dc478, 0xc000010450})
	/home/dominikh/prj/pkg/mod/golang.org/x/tools@v0.1.10-0.20220218145154-897bd77cd717/go/types/typeutil/map.go:246 +0x91 fp=0xc020180948 sp=0xc0201808e0 pc=0x561af1
golang.org/x/tools/go/types/typeutil.Hasher.hashTermSet({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, {0xc002b04f70, 0x1, 0x0?})
	/home/dominikh/prj/pkg/mod/golang.org/x/tools@v0.1.10-0.20220218145154-897bd77cd717/go/types/typeutil/map.go:404 +0x76 fp=0xc0201809b0 sp=0xc020180948 pc=0x562856
golang.org/x/tools/go/types/typeutil.Hasher.hashFor({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, {0x5dc400?, 0xc0000b66c0?})
	/home/dominikh/prj/pkg/mod/golang.org/x/tools@v0.1.10-0.20220218145154-897bd77cd717/go/types/typeutil/map.go:349 +0x7a5 fp=0xc020180b90 sp=0xc0201809b0 pc=0x562325
golang.org/x/tools/go/types/typeutil.Hasher.Hash({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, {0x5dc400, 0xc0000b66c0})
	/home/dominikh/prj/pkg/mod/golang.org/x/tools@v0.1.10-0.20220218145154-897bd77cd717/go/types/typeutil/map.go:246 +0x91 fp=0xc020180bf8 sp=0xc020180b90 pc=0x561af1
golang.org/x/tools/go/types/typeutil.Hasher.hashTypeParam({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, 0x1?)
	/home/dominikh/prj/pkg/mod/golang.org/x/tools@v0.1.10-0.20220218145154-897bd77cd717/go/types/typeutil/map.go:426 +0x66 fp=0xc020180c38 sp=0xc020180bf8 pc=0x562966
golang.org/x/tools/go/types/typeutil.Hasher.hashFor({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, {0x5dc540?, 0xc0000ca780?})
	/home/dominikh/prj/pkg/mod/golang.org/x/tools@v0.1.10-0.20220218145154-897bd77cd717/go/types/typeutil/map.go:370 +0x4e7 fp=0xc020180e18 sp=0xc020180c38 pc=0x562067
golang.org/x/tools/go/types/typeutil.Hasher.Hash({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, {0x5dc540, 0xc0000ca780})
	/home/dominikh/prj/pkg/mod/golang.org/x/tools@v0.1.10-0.20220218145154-897bd77cd717/go/types/typeutil/map.go:246 +0x91 fp=0xc020180e80 sp=0xc020180e18 pc=0x561af1
golang.org/x/tools/go/types/typeutil.Hasher.hashFor({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, {0x5dc478?, 0xc000010490?})
	/home/dominikh/prj/pkg/mod/golang.org/x/tools@v0.1.10-0.20220218145154-897bd77cd717/go/types/typeutil/map.go:289 +0x525 fp=0xc020181060 sp=0xc020180e80 pc=0x5620a5
golang.org/x/tools/go/types/typeutil.Hasher.Hash({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, {0x5dc478, 0xc000010490})
	/home/dominikh/prj/pkg/mod/golang.org/x/tools@v0.1.10-0.20220218145154-897bd77cd717/go/types/typeutil/map.go:246 +0x91 fp=0xc0201810c8 sp=0xc020181060 pc=0x561af1
golang.org/x/tools/go/types/typeutil.Hasher.hashTermSet({0xc04017fbe8?, 0xc04017fdb0?, 0xc00000c120?}, {0xc002b04f48, 0x1, 0x0?})
...additional frames elided...
exit status 2

/cc @findleyr
@gopherbot gopherbot added the Tools This label describes issues relating to any tools in the x/tools repository. label Feb 22, 2022
@gopherbot gopherbot added this to the Unreleased milestone Feb 22, 2022
@findleyr findleyr added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Feb 22, 2022
@findleyr
Copy link
Member

CC @timothy-king

@findleyr findleyr added the Soon This needs action soon. (recent regressions, service outages, unusual time-sensitive situations) label Feb 23, 2022
@findleyr findleyr self-assigned this Feb 23, 2022
@dominikh
Copy link
Member Author

Another example:

type Constraint[T any] interface{}

func Foo[T Constraint[T]]() {}

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/387754 mentions this issue: go/types/typeutil: don't recurse into constraints when hashing tparams

@timothy-king
Copy link
Contributor

Thanks for the report @dominikh. I also encountered this on gotip/test/typeparam/issue48137.go

type Constraint[T any] interface {
	~func() T
}

func Foo[T Constraint[T]]() T {
	var t T

	t = func() T {
		return t
	}
	return t
}

Looks like the same core issue to me.

@dominikh
Copy link
Member Author

My second example was in fact extracted from issue48137.go.

@golang golang locked and limited conversation to collaborators Jun 22, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Soon This needs action soon. (recent regressions, service outages, unusual time-sensitive situations) Tools This label describes issues relating to any tools in the x/tools repository.
Projects
None yet
Milestone
Unreleased
Development

No branches or pull requests
4 participants
@dominikh @timothy-king @gopherbot @findleyr