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

cmd/compile: valid type using type aliases reported as invalid #18640

Closed
griesemer opened this issue Jan 12, 2017 · 15 comments
Closed

cmd/compile: valid type using type aliases reported as invalid #18640

griesemer opened this issue Jan 12, 2017 · 15 comments
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@griesemer
Copy link
Contributor

In Go1.9, with type alias support (currently on dev.typealias branch):

type (
	a = b
	b struct {
		*a
	}
)

produces:

x.go:19: invalid recursive type alias a
	x.go:19: a uses b
	x.go:20: b uses <T>
	x.go:22: <T> uses a

There are a couple of issues:

  • we'd like to have the struct be represented more sensibly (rather than just <T>)
  • the code is actually correct
@griesemer griesemer added this to the Go1.9 milestone Jan 12, 2017
@griesemer griesemer self-assigned this Jan 12, 2017
@gopherbot
Copy link

CL https://golang.org/cl/35129 mentions this issue.

@ianlancetaylor
Copy link
Contributor

Why do you say that this code is actually correct? According to "Type Cycles" in https://github.com/golang/proposal/blob/master/design/18130-type-alias.md this is forbidden.

@griesemer
Copy link
Contributor Author

@ianlancetaylor It's correct because

type (
	a = b
	b struct {
		*a
	}
)

is the same as

type (
	a struct {
		*a
	}
)

because a and b are the same type, and the latter declaration declares a valid type (note that there's no = for the declaration of b).

gopherbot pushed a commit that referenced this issue Jan 12, 2017
…ng type aliases

Known issue: #18640 (requires a bit more work, I believe).

For #18130.

Change-Id: I53dc26012070e0c79f63b7c76266732190a83d47
Reviewed-on: https://go-review.googlesource.com/35129
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
@ianlancetaylor
Copy link
Contributor

Interesting. So you are saying that in type T1 = T2 T2 is not permitted to have any textual reference to T1, but it is permitted to use other types that use T1. I think the current spec is unclear; it says " T2 must never refer, directly or indirectly, to T1." In the above example it seems to me that T2 has an indirect reference to T1. If it does not, then I have no idea what the spec means by "indirectly."

@griesemer
Copy link
Contributor Author

griesemer commented Jan 13, 2017

The current spec as in the proposal may well be unclear. I think one way to think about it is:

A type containing alias type names is valid if and only if it is valid after all the alias type names are substituted with the type the alias type names refer to, recursively.

For the above examples:

type a = b
type b struct {
	*a
}

becomes

type b struct {
	*b
}

after type alias a is substituted with what it denotes; and b is a valid type.
Similarly,

type a = *a

would be invalid because we end up in an endless expansion for a

********....

(which one might represent inside the compiler via a pointer cycle, but since it's not going through a named (new) type, one cannot print it w/o introducing artificial names).

@gopherbot
Copy link

CL https://golang.org/cl/35831 mentions this issue.

@mdempsky
Copy link
Member

mdempsky commented Jan 26, 2017

Intuitively: any legitimate type cycle must involve a non-alias type, otherwise it would infinitely recursively expand. Also, it's always safe to start typechecking at a non-alias type, because they use TFORW placeholder Types to resolve cycles.

So I think this issue is fixed by CL 35831, which simply skips over top-level type alias declarations during phase 1. The result is we start typechecking from b instead of a, which works okay.

@griesemer
Copy link
Contributor Author

griesemer commented Jan 26, 2017 via email

@griesemer
Copy link
Contributor Author

Unfortunately the fix (CL 35831) is incorrect: Even if we ignore type aliases in a first pass, it's sufficient for a type to refer to a type alias containing a valid cycle to get an incorrect cycle error:

type (
	b = c
	c struct{ *b }
)

is valid. But

type (
	a struct{ *b }
	b = c
	c struct{ *b }
)

reports an error for b

x.go:5:2: invalid recursive type alias b
	x.go:5:2: b uses c
	x.go:6:2: c uses <T>
	x.go:6:4: <T> uses b

even though we have just established that b alone is valid.

@griesemer griesemer reopened this May 9, 2018
@griesemer griesemer added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. and removed FrozenDueToAge labels May 9, 2018
@griesemer griesemer modified the milestones: Go1.9, Go1.11 May 9, 2018
@griesemer
Copy link
Contributor Author

cc: @mdempsky

@gopherbot
Copy link

Change https://golang.org/cl/115455 mentions this issue: go/types: use color-marking based cycle detection at package level

@griesemer
Copy link
Contributor Author

Another test case (from #23055):

package p

type a struct { b }
type b = c
type c struct { *b }

@gopherbot
Copy link

Change https://golang.org/cl/118078 mentions this issue: cmd/compile: correct alias cycle detection

dna2github pushed a commit to dna2fork/go that referenced this issue Jun 14, 2018
The original fix (https://go-review.googlesource.com/c/go/+/35831)
for this issue was incorrect as it reported cycles in cases where
it shouldn't.

Instead, use a different approach: A type cycle containing aliases
is only a cycle if there are no type definitions. As soon as there
is a type definition, alias expansion terminates and there is no
cycle.

Approach: Split sprint_depchain into two non-recursive and more
easily understandable functions (cycleFor and cycleTrace),
and use those instead for cycle reporting. Analyze the cycle
returned by cycleFor before issueing an alias cycle error.

Also: Removed original fix (main.go) which introduced a separate
crash (golang#23823).

Fixes golang#18640.
Fixes golang#23823.
Fixes golang#24939.

Change-Id: Ic3707a9dec40a71dc928a3e49b4868c5fac3d3b7
Reviewed-on: https://go-review.googlesource.com/118078
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
@gopherbot
Copy link

Change https://golang.org/cl/147286 mentions this issue: cmd/compile: reintroduce work-around for cyclic alias declarations

@gopherbot
Copy link

Change https://golang.org/cl/151339 mentions this issue: [release-branch.go1.11] cmd/compile: reintroduce work-around for cyclic alias declarations

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Development

No branches or pull requests

4 participants