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.

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

go/types,types2: unification reached recursion depth limit #59740

Closed
rprtr258 opened this issue Apr 20, 2023 · 7 comments
Closed

go/types,types2: unification reached recursion depth limit #59740

rprtr258 opened this issue Apr 20, 2023 · 7 comments
Assignees
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. release-blocker Tools This label describes issues relating to any tools in the x/tools repository.
Milestone

Comments

@rprtr258
Copy link

gopls version

Build info
----------
golang.org/x/tools/gopls v0.11.0
    golang.org/x/tools/gopls@v0.11.0 h1:/nvKHdTtePQmrv9XN3gIUN9MOdUrKzO/dcqgbG6x8EY=
    github.com/BurntSushi/toml@v1.2.1 h1:9F2/+DoOYIOksmaJFPw1tGFy1eDnIJXg+UHjuD8lTak=
    github.com/google/go-cmp@v0.5.9 h1:O2Tfq5qg4qc4AmwVlvv0oLiVAGB7enBSJ2x2DqQFi38=
    github.com/sergi/go-diff@v1.1.0 h1:we8PVUC3FE2uYfodKH/nBHMSetSfHDR6scGdBi+erh0=
    golang.org/x/exp@v0.0.0-20221031165847-c99f073a8326 h1:QfTh0HpN6hlw6D3vu8DAwC8pBIwikq0AI1evdm+FksE=
    golang.org/x/exp/typeparams@v0.0.0-20221031165847-c99f073a8326 h1:fl8k2zg28yA23264d82M4dp+YlJ3ngDcpuB1bewkQi4=
    golang.org/x/mod@v0.7.0 h1:LapD9S96VoQRhi/GrNTqeBJFrUjs5UHCAtTlgwA5oZA=
    golang.org/x/sync@v0.1.0 h1:wsuoTGHzEhffawBOhz5CYhcrV4IdKZbEyZjBMuTp12o=
    golang.org/x/sys@v0.2.0 h1:ljd4t30dBnAvMZaQCevtY0xLLD0A+bRZXbgLMLU1F/A=
    golang.org/x/text@v0.4.0 h1:BrVqGRd7+k1DiOgtnFvAkoQEWQvBc25ouMJM6429SFg=
    golang.org/x/tools@v0.3.1-0.20221213193459-ca17b2c27ca8 h1:7/HkGkN/2ktghBCSRRgp31wAww4syfsW52tj7yirjWk=
    golang.org/x/vuln@v0.0.0-20221109205719-3af8368ee4fe h1:qptQiQwEpETwDiz85LKtChqif9xhVkAm8Nhxs0xnTww=
    honnef.co/go/tools@v0.3.3 h1:oDx7VAwstgpYpb3wv0oxiZlxY+foCpRAwY7Vk6XpAgA=
    mvdan.cc/gofumpt@v0.4.0 h1:JVf4NN1mIpHogBj7ABpgOyZc65/UUOkKQFkoURsz4MM=
    mvdan.cc/xurls/v2@v2.4.0 h1:tzxjVAj+wSBmDcF6zBB7/myTy3gX9xvi8Tyr28AuQgc=
go: go1.19.5

What did you do?

https://go.dev/play/p/iI-wIjV_gpS

What did you expect to see?

compilation error like stack overflow

What did you see instead?

go run main.go prints:

# command-line-arguments
<unknown line number>: internal compiler error: panic: unification reached recursion depth limit

gopls crashes with following error:

[Error - 7:59:30 PM] Request textDocument/codeAction failed.
  Message: context canceled
  Code: 0 
panic: unification reached recursion depth limit [recovered]
	panic: unification reached recursion depth limit

goroutine 1039 [running]:
go/types.(*Checker).handleBailout(0xc000e8a000, 0xc0027555e8)
	/home/rprtr258/.gvm/gos/go1.19.5/src/go/types/check.go:302 +0x8b
panic({0xd20680, 0x10d6ee0})
	/home/rprtr258/.gvm/gos/go1.19.5/src/runtime/panic.go:884 +0x212
go/types.(*unifier).nify(0x0?, {0x10dce78?, 0xc00037c6d8?}, {0x10dce78?, 0xc00037c828?}, 0x0?)
	/home/rprtr258/.gvm/gos/go1.19.5/src/go/types/unify.go:298 +0x1745
go/types.(*unifier).nify(0xc002bf25a0, {0x10dce00?, 0xc0020b3dc0?}, {0x10dce00?, 0xc0020f2380?}, 0x0)
	/home/rprtr258/.gvm/gos/go1.19.5/src/go/types/unify.go:471 +0x8e7
go/types.(*unifier).nify(0xc002bf25a0, {0x10dcdb0?, 0xc000022700?}, {0x10dce00?, 0xc0020f2380?}, 0x0)
.....
(last two rows are repeated many many times with different numbers)

Editor and settings

VSCode with Go plugin

@gopherbot gopherbot added Tools This label describes issues relating to any tools in the x/tools repository. gopls Issues related to the Go language server, gopls. labels Apr 20, 2023
@gopherbot gopherbot added this to the Unreleased milestone Apr 20, 2023
@findleyr
Copy link
Contributor

Thank you for the repro! This appears to still affect go at master.

CC @griesemer

@findleyr findleyr modified the milestones: Unreleased, Go1.21 Apr 20, 2023
@findleyr findleyr added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. release-blocker labels Apr 20, 2023
@findleyr findleyr changed the title x/tools/gopls: unification reached recursion depth limit go/types,types2: unification reached recursion depth limit Apr 20, 2023
@findleyr
Copy link
Contributor

Recategorizing as go/types, types2, as this bug is not specific to gopls.

@suzmue suzmue removed the gopls Issues related to the Go language server, gopls. label Apr 20, 2023
@griesemer griesemer self-assigned this Apr 20, 2023
@griesemer
Copy link
Contributor

griesemer commented Apr 20, 2023

Simpler reproducer:

type F[T any] func(func(F[T]))

func f(F[int]) {}
func g[T any](F[T]) {}

func _() {
	g(f)
}

@griesemer
Copy link
Contributor

griesemer commented Apr 20, 2023

Inference trace (with cut-off beyond depth 10):

== infer : [T₃](F[T₃]) ➞ []
== function parameters: (p.F[T₃])
-- function arguments : [f (value of type func(p.F[int]))]
.  p.F[T₃] ≡ func(p.F[int])
.  func(p.F[int]) ≡ p.F[T₃] (swap)
.  func(p.F[int]) ≡ under p.F[T₃]
.  .  (p.F[int]) ≡ (func(p.F[T₃]))
>>>  .  p.F[int] ≡ func(p.F[T₃])
.  .  .  func(p.F[T₃]) ≡ p.F[int] (swap)
.  .  .  func(p.F[T₃]) ≡ under p.F[int]
.  .  .  .  (p.F[T₃]) ≡ (func(p.F[int]))
.  .  .  .  .  p.F[T₃] ≡ func(p.F[int])
.  .  .  .  .  func(p.F[int]) ≡ p.F[T₃] (swap)
.  .  .  .  .  func(p.F[int]) ≡ under p.F[T₃]
.  .  .  .  .  .  (p.F[int]) ≡ (func(p.F[T₃]))
>>>  .  .  .  .  .  p.F[int] ≡ func(p.F[T₃])
.  .  .  .  .  .  .  func(p.F[T₃]) ≡ p.F[int] (swap)
.  .  .  .  .  .  .  func(p.F[T₃]) ≡ under p.F[int]
.  .  .  .  .  .  .  .  (p.F[T₃]) ≡ (func(p.F[int]))
.  .  .  .  .  .  .  .  .  p.F[T₃] ≡ func(p.F[int])
.  .  .  .  .  .  .  .  .  func(p.F[int]) ≡ p.F[T₃] (swap)
.  .  .  .  .  .  .  .  .  func(p.F[int]) ≡ under p.F[T₃]
.  .  .  .  .  .  .  .  .  .  (p.F[int]) ≡ (func(p.F[T₃]))
>>>  .  .  .  .  .  .  .  .  .  p.F[int] ≡ func(p.F[T₃])
.  .  .  .  .  .  .  .  .  .  .  depth 11 >= 10 => abort/panic

>>> marks identical unification attempts.

@griesemer
Copy link
Contributor

griesemer commented Apr 20, 2023

Better trace:

== infer : [T₃](F[T₃]) ➞ []
== function parameters: (p.F[T₃])
-- function arguments : [f (value of type func(p.F[int]))]
.  p.F[T₃] ≡ func(p.F[int])
.  func(p.F[int]) ≡ p.F[T₃] (swap)
.  func(p.F[int]) ≡ func(func(p.F[T₃])) (under)
.  .  (p.F[int]) ≡ (func(p.F[T₃]))
>>>  .  p.F[int] ≡ func(p.F[T₃])
.  .  .  func(p.F[T₃]) ≡ p.F[int] (swap)
.  .  .  func(p.F[T₃]) ≡ func(func(p.F[int])) (under)
.  .  .  .  (p.F[T₃]) ≡ (func(p.F[int]))
.  .  .  .  .  p.F[T₃] ≡ func(p.F[int])
.  .  .  .  .  func(p.F[int]) ≡ p.F[T₃] (swap)
.  .  .  .  .  func(p.F[int]) ≡ func(func(p.F[T₃])) (under)
.  .  .  .  .  .  (p.F[int]) ≡ (func(p.F[T₃]))
>>>  .  .  .  .  .  p.F[int] ≡ func(p.F[T₃])
.  .  .  .  .  .  .  func(p.F[T₃]) ≡ p.F[int] (swap)
.  .  .  .  .  .  .  func(p.F[T₃]) ≡ func(func(p.F[int])) (under)
.  .  .  .  .  .  .  .  (p.F[T₃]) ≡ (func(p.F[int]))
.  .  .  .  .  .  .  .  .  p.F[T₃] ≡ func(p.F[int])
.  .  .  .  .  .  .  .  .  func(p.F[int]) ≡ p.F[T₃] (swap)
.  .  .  .  .  .  .  .  .  func(p.F[int]) ≡ func(func(p.F[T₃])) (under)
.  .  .  .  .  .  .  .  .  .  (p.F[int]) ≡ (func(p.F[T₃]))
>>>  .  .  .  .  .  .  .  .  .  p.F[int] ≡ func(p.F[T₃])
.  .  .  .  .  .  .  .  .  .  .  depth 11 >= 10 => abort/panic

The question is: should func(p.F[T₃]) ≡ func(func(p.F[int])) be considered structurally equivalent?

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/487197 mentions this issue: go/types, types2: abort type unification if no progress is made

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/498895 mentions this issue: go/types, types2: use exact unification for component types

gopherbot pushed a commit that referenced this issue May 30, 2023
This change defines two unification modes used to control unification:

- assign  set when unifying types involved in an assignment
- exact   if set, types unify if they can be made identical

Currently, unification is inexact: when a defined type is compared
against a type literal, the underlying type of the defined type is
considered. When channel types are compared, the channel direction
is ignored. And when defined types are compared where one (or both)
are interfaces, interface unification is used.

By contrast, exact unification requires types to match exactly:
if they can be unified, the types must be identical (with suitable
type arguments).

Exact unification is required when comparing component types.
For instance, when unifying func(x P) with func(x Q), the two
signatures unify only if P is identical to Q per Go's assignment
rules.

Until now we have ignored exact unification and made due with inexact
unification everywhere, even for component types. In some cases this
led to infinite recursions in the unifier, which we guarded against
with a depth limit (and unification failure).

Go's assignmemt rules allow inexact matching at the top-level but
require exact matching for element types.

This change passes 'assign' to the unifier when unifying parameter
against argument types because those follow assignment rules.
When comparing constraints, inexact unification is used as before.

In 'assign' mode, when comparing element types, the unifyier is
called recursively, this time with the 'exact' mode set, causing
element types to be compared exactly. If unification succeeds for
element types, they are identical (with suitable type arguments).

This change fixes #60460. It also fixes a bug in the test for
issue #60377. We also don't need to rely anymore on the recursion
depth limit (a temporary fix) for #59740. Finally, because we use
exact unification when comparing element types which are channels,
errors caused by assignment failures (due to inexact inference which
succeeded when it shouldn't have) now produce the correct inference
error.

Fixes #60460.
For #60377.
For #59740.

Change-Id: Icb6a9b4dbd34294f99328a06d52135cb499cab85
Reviewed-on: https://go-review.googlesource.com/c/go/+/498895
Reviewed-by: Robert Findley <rfindley@google.com>
Auto-Submit: Robert Griesemer <gri@google.com>
Run-TryBot: Robert Griesemer <gri@google.com>
Reviewed-by: Robert Griesemer <gri@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
@golang golang locked and limited conversation to collaborators May 26, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. release-blocker Tools This label describes issues relating to any tools in the x/tools repository.
Projects
None yet
Development

No branches or pull requests

5 participants