How can a slice contain itself?

Question

I'm trying to learn Golang using "The Go Programming Language" and I've reached the section on slices. They make the comparison between arrays and slices in that two arrays can be compared with == where two slices can not. The text reads as the following:

"== operator for arrays of strings, it may be puzzling that slice
comparisons do not also work this way. There are two reasons why deep 
equivalence is problematic. First, unlike array elements, the elements
of a slice are indirect, making it possible for a slice to contain 
itself. Although there are ways to deal with such cases, none is 
simple, efficient, and most importantly, obvious."

What is meant by it's possible for a slice to contain itself due to the elements being indirect?

Solarism

Answer 1

Slice containing itself

Besides a recursive type (such as type Foo []Foo, see ANisus's answer) which is good for nothing besides demonstration, a slice may contain itself if for example the element type of the slice is interface{}:

s := []interface{}{"one", nil}
s[1] = s

In this example the slice s will have 2 interface values, the first "wrapping" a simple string "one", and another interface value wrapping the slice value itself. When an interface value is created, a copy of the value will be wrapped which in case of slices means a copy of the slice header/descriptor, which contains the pointer to the underlying array, so the copy will have the same pointer value pointing to the same underlying array. (For more details about the representation of interfaces, see The Laws of Reflection: The representation of an interface.)

If you were quickly on to print it:

fmt.Println(s)

You would get a fatal error, something like:

runtime: goroutine stack exceeds 250000000-byte limit
fatal error: stack overflow

Because fmt.Println() tries to print the content recursively, and since the 2nd element is a slice pointing to the same array of the the slice being printed, it runs into an infinite loop.

Another way to see if it really is the slice itself:

s := []interface{}{"one", nil}
s[1] = s
fmt.Println(s[0])

s2 := s[1].([]interface{})
fmt.Println(s2[0])

s3 := s2[1].([]interface{})
fmt.Println(s3[0])

Output (try it on the Go Playground):

one
one
one

No matter how deep we go, the 2nd element will always be the slice value pointing to the same array as s, wrapped in an interface{} value.

The indirection plays the important role as a copy will be wrapped in the interface{} but the copy will contain the same pointer.

Array can't contain itself

Changing the type to be an array:

s := [2]interface{}{"one", nil}
s[1] = s
fmt.Println(s[0])

s2 := s[1].([2]interface{})
fmt.Println(s2[0])

s3 := s2[1].([2]interface{})
fmt.Println(s3[0])

Output (try it on the Go Playground):

one
one
panic: interface conversion: interface is nil, not [2]interface {}

This is because when the array is wrapped into an interface{}, a copy will be wrapped - and a copy is not the original array. So s will have a second value, an interface{} wrapping an array, but that is a different array whose 2nd value is not set and therefore will be nil (the zero value of type interface{}), so attempting to "go into" this array will panic because it is nil (type assertion fails because not the special "comma, ok" form was used).

Since this s array does not contain itself, a simple fmt.Println() will reveal its full content:

fmt.Println(s)

Output:

[one [one <nil>]]

Further interface{} wrapping analysis

If you wrap an array in an interface{} and modify the content of the original array, the value wrapped in the interface{} is not affected:

arr := [2]int{1, 2}
var f interface{} = arr
arr[0] = 11

fmt.Println("Original array:    ", arr)
fmt.Println("Array in interface:", f)

Output:

Original array:     [11 2]
Array in interface: [1 2]

If you do the same with a slice, the wrapped slice (since points to the same underlying array) is also affected:

s := []int{1, 2}
f = s
s[0] = 11

fmt.Println("Original slice:    ", s)
fmt.Println("Slice in interface:", f)

Output:

Original slice:     [11 2]
Slice in interface: [11 2]

Try these on the Go Playground.

Illuminator

Great explanation. Quite something that the book makes such a frivolous remark which requires this much unpacking.. – Lynlyncean

thanks for the explanation. but I still didn't understand and I think the guy who asked didn't pick it up as an answer. so, let me tell why, simply because the book didn't introduce interfaces before this remark :) – Flux

Answer 2

The below example creates a slice that contains itself:

type Foo []Foo  
bar := make(Foo, 1)
bar[0] = bar

This can be done because the slice value internally contains a pointer to an array, a length, and a capacity.

An array on the other hand is a value. It can, at best, contain pointers to itself.

Eunuchoidism

This example is really fun, it makes me think a lot about the go slice type. Why downvote? @downvoter – Kirstinkirstyn

@H.W.Du :) recursive types can surely be useful sometimes. Maybe not in this example, but still. I thought downvoter just didn't know about them. – Eunuchoidism

Answer 3

a slice contains a pointer to the memory holding the elements, a length for available elements count, and a capability for how big the memory. so it like:

typedef struct { void *data; GoInt len; GoInt cap; } GoSlice;

I think it is indirect, because the elements are referenced by pointer. and of course we can have the slice itself in void *data.

Bowel