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

[griesemer]

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

[gopherbot]

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

[ianlancetaylor]

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]

@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).

[ianlancetaylor]

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]

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]

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

[mdempsky]

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]

On Thu, Jan 26, 2017 at 9:25 AM, Matthew Dempsky ***@***.***> wrote: 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.

This is a compelling argument and very elegant solution. Thanks! - gri

[griesemer]

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]

cc: @mdempsky

[gopherbot]

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

[griesemer]

Another test case (from #23055):

package p

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

[gopherbot]

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

[gopherbot]

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

[gopherbot]

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