Go: reflect: DeepEqual panics when encountering a pointer cycle

[huandu]

What version of Go are you using (go version)?

$ go version
go version go1.12.7 darwin/amd64

Does this issue reproduce with the latest release?

Yes.

What operating system and processor architecture are you using (go env)?

go env Output

$ go env

GOARCH="amd64"

GOBIN=""

GOCACHE="/Users/huandu/Library/Caches/go-build"

GOEXE=""

GOFLAGS=""

GOHOSTARCH="amd64"

GOHOSTOS="darwin"

GOOS="darwin"

GOPATH="/Users/huandu/.gopkg"

GORACE=""

GOROOT="/usr/local/Cellar/go/1.12.7/libexec"

GOTMPDIR=""

GOTOOLDIR="/usr/local/Cellar/go/1.12.7/libexec/pkg/tool/darwin_amd64"

GCCGO="gccgo"

CC="clang"

CXX="clang++"

CGO_ENABLED="1"

GOMOD="/dev/null"

CGO_CFLAGS="-g -O2"

CGO_CPPFLAGS=""

CGO_CXXFLAGS="-g -O2"

CGO_FFLAGS="-g -O2"

CGO_LDFLAGS="-g -O2"

PKG_CONFIG="pkg-config"

GOGCCFLAGS="-fPIC -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/w5/42dq8w6922z_2p0v7ssfmmkr0000gn/T/go-build443570034=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

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

package main

import (
    "fmt"
    "reflect"
)

func main() {
    nested := func() interface{} {
        nested := map[string]interface{}{}
        nested["foo"] = nested
        return nested
    }

    v1 := nested()
    v2 := nested()
    fmt.Println(reflect.DeepEqual(v1, v2))
}

What did you expect to see?

No stack overflow. reflect.DeepEqual should return true.

What did you see instead?

reflect.DeepEqual fails with stack overflow.

[mvdan]

I think you mean it panics when it encounters a cycle. A nested map would be something like map[int]map[int]int.

I agree DeepEqual shouldn't reach a stack overflow in this case. If you want to work on a fix, that's welcome.

[av86743]

There is no well-defined constructive equality over the infinite objects like in the given example.

Good luck with "working on a fix" for this.

[mvdan]

@av86743 please be nice; there's no need to tell new Go contributors "good luck with this".

This is documented, though:

As DeepEqual traverses the data values it may find a cycle. The second and subsequent times that DeepEqual compares two pointer values that have been compared before, it treats the values as equal rather than examining the values to which they point. This ensures that DeepEqual terminates.

So I think it's reasonable to follow this rule and also make this case terminate.

[av86743]

... This ensures that DeepEqual terminates.

That's just a wishful thinking.

[av86743]

... This ensures that DeepEqual terminates.

This is not true.

[mvdan]

@av86743 please only leave comments if you're going to provide useful input or constructive criticism. For example, why is this not true? If you think it isn't, file a new issue. It seems to me like the case reported here can be fixed, following the rule already documented, so there's no reason to continue insisting in this thread.

Also, a second reminder about https://golang.org/conduct.

[av86743]

@mvdan You are abusing your position of moderator in order to silence me.

[andybons]

Hi folks. Let’s please keep this friendly and constructive. Comments unrelated to the issue itself (or that don’t provide any actionable/constructive content) will be hidden. Thanks.

@av86743 can you please explain why you believe that @mvdan’s suggested solution will not terminate?

[huandu]

I have a quick fix on this. The root cause is simple: Value#Elem() method always returns a reflect.Value with RO flag, which causes CanSet returns false and shadows the visited map.

--- deepequal.old       2019-08-28 20:48:58.000000000 +0800
+++ deepequal.go        2019-08-28 21:26:13.000000000 +0800
@@ -34,17 +34,19 @@
        // We want to avoid putting more in the visited map than we need to.
        // For any possible reference cycle that might be encountered,
        // hard(t) needs to return true for at least one of the types in the cycle.
-       hard := func(k Kind) bool {
+       hard := func(k Kind, v1, v2 Value) bool {
                switch k {
-               case Map, Slice, Ptr, Interface:
+               case Map, Slice, Ptr:
                        return true
+               case Interface:
+                       return v1.CanSet() && v2.CanSet()
                }
                return false
        }

-       if v1.CanAddr() && v2.CanAddr() && hard(v1.Kind()) {
-               addr1 := unsafe.Pointer(v1.UnsafeAddr())
-               addr2 := unsafe.Pointer(v2.UnsafeAddr())
+       if hard(v1.Kind(), v1, v2) {
+               addr1 := v1.ptr
+               addr2 := v2.ptr
                if uintptr(addr1) > uintptr(addr2) {
                        // Canonicalize order to reduce number of entries in visited.
                        // Assumes non-moving garbage collector.

[mvdan]

@huandu Great! Please send a CL (see https://tip.golang.org/doc/contribute.html) and we can take it from there.

[av86743]

... can you please explain why you believe that @mvdan’s suggested solution will not terminate?

@andybons What "suggested solution"?

[gopherbot]

Change https://golang.org/cl/191940 mentions this issue: reflect: fix panic in DeepEqual when checking a pointer cycle.