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: missing type information in cycle detection #41669

Open
cuonglm opened this issue Sep 28, 2020 · 6 comments
Open

go/types: missing type information in cycle detection #41669

cuonglm opened this issue Sep 28, 2020 · 6 comments

Comments

@cuonglm
Copy link
Member

@cuonglm cuonglm commented Sep 28, 2020

What version of Go are you using (go version)?

$ go version
go version devel +816ff44479 Tue Oct 8 16:41:02 2019 +0000 linux/amd64

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output
$ go env

What did you do?

package p

type I1 = interface {
	I2
}

type I2 interface {
	I1
}

What did you expect to see?

Run gotype built with go1.13.x for above program print:

issue23823.go:13:6: illegal cycle in declaration of I2
issue23823.go:13:6: 	I2 refers to
issue23823.go:9:6: 	I1 refers to
issue23823.go:13:6: 	I2

What did you see instead?

With go1.14.x, go1.15.x and tip:

issue23823.go:13:6: illegal cycle in declaration of I2
issue23823.go:13:6: 	I2 refers to
issue23823.go:13:6: 	I2

git bisect points to 37a2290

cc @griesemer @mdempsky

@griesemer
Copy link
Contributor

@griesemer griesemer commented Sep 28, 2020

@andybons andybons added this to the Unplanned milestone Sep 29, 2020
@gopherbot
Copy link

@gopherbot gopherbot commented Sep 29, 2020

Change https://golang.org/cl/258177 mentions this issue: cmd/compile: report type loop for invalid recursive types

@griesemer
Copy link
Contributor

@griesemer griesemer commented Sep 29, 2020

For type aliases we don't keep the names around which is (likely) the cause for this issue. That is, for the type-checker, the type I2 looks like this:

type I2 interface {
    interface {
        I2
    }
}

and eventually like this

type I2 interface {
    I2
}

which explains the error message.

Fixing this (and other related issues) requires that we keep alias type names around in some way. That may be a fairly significant change.

gopherbot pushed a commit that referenced this issue Sep 29, 2020
Similar to how we report initialization loops in initorder.go and type
alias loops in typecheck.go, this CL updates align.go to warn about
invalid recursive types. The code is based on the loop code from
initorder.go, with minimal changes to adapt from detecting
variable/function initialization loops to detecting type declaration
loops.

Thanks to Cuong Manh Le for investigating this, helping come up with
test cases, and exploring solutions.

Fixes #41575
Updates #41669.

Change-Id: Idb2cb8c5e1d645e62900e178fcb50af33e1700a1
Reviewed-on: https://go-review.googlesource.com/c/go/+/258177
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Trust: Matthew Dempsky <mdempsky@google.com>
Trust: Cuong Manh Le <cuong.manhle.vn@gmail.com>
@cuonglm
Copy link
Member Author

@cuonglm cuonglm commented Sep 30, 2020

@griesemer Thanks for details explanation, I don't know that go/types also don't record alias name like cmd/compile. But my concern is that in go1.13.x, we does report alias name in the cycle. Is the behavior change intentional in go1.14.x and above?

@gopherbot
Copy link

@gopherbot gopherbot commented Oct 5, 2020

Change https://golang.org/cl/259447 mentions this issue: go/types: introduce an interstitial typeAlias Type

@findleyr
Copy link
Contributor

@findleyr findleyr commented Oct 5, 2020

https://golang.org/cl/259447 proposes one way to solve this: by preserving type alias information in the type graph until the last possible moment. This is achieved by introducing a typeAlias Type for internal use only, and 'collapsing' this type at API boundaries.

The other thing I tried was to preserve syntactic cycle information in, for example, a Checker.cycles map, so that we can accurately report all the edges in our cycle when it is later discovered to be invalid. This proved to be quite complex though, because it's not trivial to reverse-engineer the syntactic cycle that corresponds to a type cycle (consider the case where we have a deep, high degree graph of type aliases).

The downside of CL 259447 is that we have to be very careful not to leak the typeAlias type. There are some things we could do to make this safer, for example introducing a new type to mean "all Types plus aliases", but such a change would turn out to be quite large and I don't want to embark on this without discussing with @griesemer.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants