spec: Document rules for recursive type and other self-referential decls

[nico]

The spec says "An interface type T may not embed itself or any interface type that
embeds T, recursively.", but nothing like this is mentioned for structs.

(A struct containing itself would obviously need infty memory, but the spec should
probably still explicitly mention that these are illegal while a struct containing a
pointer to itself is fine

[robpike]

Comment 1:

It could embed a pointer to itself, though, and that works just fine. It's pointless to
embed a non-pointer recursively this way. Is that really worth explaining in the spec?

[griesemer]

Comment 2:

This applies also to named fields for structs, and arrays, too.
In general, all "composite value types" cannot contain themselves directly or indirectly
unless there's a reference type between.
It's somewhat obvious but it probably should be spec'ed out explicitly, after all it's
something that typecheckers go though some length to check.

Labels changed: added documentation.

Owner changed to @griesemer.

Status changed to Accepted.

[rsc]

Comment 3:

Labels changed: added go1.3maybe.

[rsc]

Comment 4:

Labels changed: added release-none, removed go1.3maybe.

[rsc]

Comment 5:

Labels changed: added repo-main.

[jub0bs]

Any update on this issue? As a Go trainer, I'd like to be able to point participants to an authoritative passage of the spec that would elucidate the restriction.

[griesemer]

No, this has not been addressed yet, sorry.

But the rules are fairly simple:

1. Array and struct types are invalid if they require infinite amounts of memory.
2. For interface types the rule is written down in the spec.
3. For all other types, there are no restrictions on self-reference.

There's a rule of thumb for 1):
Is it possible to write down a corresponding composite literal in a finite amount of source text, without using a variable of the type in question? If not, the type is invalid.

For example, given:

type S struct {
   a S
}

there is no way to write down a composite literal for S in a finite amount of source text:

var s = S{a: S{a: S{a: ... // never ends

(and note that you're not allowed to use a variable of type S inside the composite literal to "shortcut": var t = S{s} is not permitted because it's using s of type S).

This may be a reasonable and intuitive way to teach this restrictions to new Go programmers. It's also accurately reflecting the reason for the restriction (the type checker does exactly this test).