detecting cyclic references

297 переглядів
Перейти до першого непрочитаного повідомлення

arpad ryszka

не прочитано,
9 лист. 2020 р., 22:11:4109.11.20
Кому: golang-nuts
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

не прочитано,
10 лист. 2020 р., 02:38:2610.11.20
Кому: arpad ryszka, golang-nuts
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

не прочитано,
10 лист. 2020 р., 20:30:4910.11.20
Кому: golang-nuts
FYI, that does detect the simple case of l[0] = l, but not more complicated circular cases like l[1] = l[1:]

Axel Wagner

не прочитано,
11 лист. 2020 р., 02:13:5511.11.20
Кому: jake...@gmail.com, golang-nuts
The question was about detecting cyclic references. For that, the `l[0] = l` case is enough.

arpad ryszka

не прочитано,
11 лист. 2020 р., 07:59:1811.11.20
Кому: golang-nuts
`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

не прочитано,
11 лист. 2020 р., 10:42:5711.11.20
Кому: arpad ryszka, golang-nuts

`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.

Axel Wagner

не прочитано,
11 лист. 2020 р., 10:48:1911.11.20
Кому: arpad ryszka, golang-nuts
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:
You should keep in mind though, that this might break in the future, if the map-implementation ever changes.

Ian Lance Taylor

не прочитано,
11 лист. 2020 р., 14:55:1611.11.20
Кому: Axel Wagner, arpad ryszka, golang-nuts
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

не прочитано,
14 лист. 2020 р., 06:52:2714.11.20
Кому: golang-nuts
> 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:

Dan Kortschak

не прочитано,
14 лист. 2020 р., 15:43:3814.11.20
Кому: golang-nuts
Or github.com/kortschak/utter </shameless-self-plug>.

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

arpad ryszka

не прочитано,
22 лист. 2020 р., 17:43:1922.11.20
Кому: golang-nuts
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?

Відповісти всім
Відповісти автору
Переслати
0 нових повідомлень