detecting cyclic references

[arpad ryszka]

Hi,

is there a way to detect the cyclic reference in the following example somehow? Either via reflection or by other means? My understanding is that slices cannot be compared with == (unless to nil), or used as keys in maps. Is there a different way?

l := []interface{}{"foo"}

l[0] = l

fmt.Println(l)

or here it is as a playground link: https://play.golang.org/p/T0qZlF8m-vi

Cheers,

Arpad

[Axel Wagner]

If the slice is empty, it doesn't reference anything.

If it is not empty, &x[0] can be used to identify the slice (potentially also using len/cap, if it's interesting).

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/b2cb6b5e-febc-407f-b5b3-d9ca196ce68bn%40googlegroups.com.

[jake...@gmail.com]

FYI, that does detect the simple case of l[0] = l, but not more complicated circular cases like l[1] = l[1:]

[Axel Wagner]

The question was about detecting cyclic references. For that, the `l[0] = l` case is enough.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/250107e9-f688-4205-ae52-728221eb2e4cn%40googlegroups.com.

[arpad ryszka]

`l[0] = l` would be fine for me, indeed. Though I am not sure I understand the suggested solution. Notice that the type of the slice is `[]interface{}`. This...

ll := l[0].([]interface{})

println(&l == &ll)

...would print `false`.

I think the main challenge is that l and ll, or l[0] for that matter, are not the same values. I tried with reflection, too, but couldn't figure a way.

PS: I am quite aware how unearthy this problem is, and how it should not ever happen in case of actual programs. My use case is that I want to pretty print in-memory objects for debug purposes during testing, and one of the features would be to point out such cycles as this.

[Axel Wagner]

https://play.golang.org/p/qTBiAdR9djt

`a` is the address of the first element of `l`.

`b` is the address of the first element of `l[0]`, which is of type `[]interface{}` after the assignment.

Both `l` and `l[0]` refer to the same underlying array, so their first elements have the same address.

In practice, you probably want to walk the value with a depth-first search and use `reflect` to extract the addresses and check for slices and the like and use a `map[reflect.Value]bool` with pointers to keep track which values you've already seen. The code isn't trivial enough for me to just write it down at the moment, but once the idea is clear, it should be doable.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/7714670d-823a-4486-a89e-a1c636051005n%40googlegroups.com.

[Axel Wagner]

BTW, the same idea doesn't work for maps, of course. For maps, you could exploit the fact that they are pointer-shaped in the current implementation and use unsafe to compare those pointers:

https://play.golang.org/p/JCeXmoUctT2

You should keep in mind though, that this might break in the future, if the map-implementation ever changes.

[Ian Lance Taylor]

On Wed, Nov 11, 2020 at 7:42 AM 'Axel Wagner' via golang-nuts
<golan...@googlegroups.com> wrote:
>
> https://play.golang.org/p/qTBiAdR9djt
>
> `a` is the address of the first element of `l`.
> `b` is the address of the first element of `l[0]`, which is of type `[]interface{}` after the assignment.
>
> Both `l` and `l[0]` refer to the same underlying array, so their first elements have the same address.
>
> In practice, you probably want to walk the value with a depth-first search and use `reflect` to extract the addresses and check for slices and the like and use a `map[reflect.Value]bool` with pointers to keep track which values you've already seen. The code isn't trivial enough for me to just write it down at the moment, but once the idea is clear, it should be doable.

It might help to look at the implementation of reflect.DeepEqual,
which uses this approach to avoid infinite recursion on memory cycles.

Ian

[twp...@gmail.com]

> My use case is that I want to pretty print in-memory objects for debug purposes during testing, and one of the features would be to point out such cycles as this.

Consider using an existing library for this, for example:

  https://github.com/sanity-io/litter

  https://github.com/davecgh/go-spew

[Dan Kortschak]

Or github.com/kortschak/utter </shameless-self-plug>.

This package does an arguably better job at dealing with self-
referencing structures.

[arpad ryszka]

Thanks a lot for the help! Seems like I could sort it out based on the reflect.DeepEqual code. Do you have any testing tips?

Out of general curiosity, I am wondering why the type is part of the key for the visited map here: https://golang.org/src/reflect/deepequal.go#L15. If I remove it, the tests of the reflect package still pass. Is it some kind of an optimization?