go/ssa/interp: Adds reflect.DeepEqual model for interp testing
Implements reflect.DeepEqual() for testing interp packages. Adds test that exercises this.
Fixes a nil pointer dereference in ext۰reflect۰Value۰Elem in interp.
Updates golang/go#48525
Change-Id: Ib32e96d37aa5c85cefe59e9514d4e162d7f7011e
Reviewed-on: https://go-review.googlesource.com/c/tools/+/391314
Reviewed-by: Robert Findley <rfindley@google.com>
Run-TryBot: Tim King <taking@google.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Trust: Tim King <taking@google.com>
diff --git a/go/ssa/interp/interp_test.go b/go/ssa/interp/interp_test.go
index 1b43742..1fba99f 100644
--- a/go/ssa/interp/interp_test.go
+++ b/go/ssa/interp/interp_test.go
@@ -111,6 +111,7 @@
"complit.go",
"convert.go",
"coverage.go",
+ "deepequal.go",
"defer.go",
"fieldprom.go",
"ifaceconv.go",
diff --git a/go/ssa/interp/reflect.go b/go/ssa/interp/reflect.go
index 0a4465b..9f2f9e1 100644
--- a/go/ssa/interp/reflect.go
+++ b/go/ssa/interp/reflect.go
@@ -407,7 +407,11 @@
case iface:
return makeReflectValue(x.t, x.v)
case *value:
- return makeReflectValue(rV2T(args[0]).t.Underlying().(*types.Pointer).Elem(), *x)
+ var v value
+ if x != nil {
+ v = *x
+ }
+ return makeReflectValue(rV2T(args[0]).t.Underlying().(*types.Pointer).Elem(), v)
default:
panic(fmt.Sprintf("reflect.(Value).Elem(%T)", x))
}
diff --git a/go/ssa/interp/testdata/deepequal.go b/go/ssa/interp/testdata/deepequal.go
new file mode 100644
index 0000000..4fad2d6
--- /dev/null
+++ b/go/ssa/interp/testdata/deepequal.go
@@ -0,0 +1,93 @@
+// This interpreter test is designed to test the test copy of DeepEqual.
+//
+// Validate this file with 'go run' after editing.
+
+package main
+
+import "reflect"
+
+func assert(cond bool) {
+ if !cond {
+ panic("failed")
+ }
+}
+
+type X int
+type Y struct {
+ y *Y
+ z [3]int
+}
+
+var (
+ a = []int{0, 1, 2, 3}
+ b = []X{0, 1, 2, 3}
+ c = map[int]string{0: "zero", 1: "one"}
+ d = map[X]string{0: "zero", 1: "one"}
+ e = &Y{}
+ f = (*Y)(nil)
+ g = &Y{y: e}
+ h *Y
+)
+
+func init() {
+ h = &Y{} // h->h
+ h.y = h
+}
+
+func main() {
+ assert(reflect.DeepEqual(nil, nil))
+ assert(reflect.DeepEqual((*int)(nil), (*int)(nil)))
+ assert(!reflect.DeepEqual(nil, (*int)(nil)))
+
+ assert(reflect.DeepEqual(0, 0))
+ assert(!reflect.DeepEqual(0, int64(0)))
+
+ assert(!reflect.DeepEqual("", 0))
+
+ assert(reflect.DeepEqual(a, []int{0, 1, 2, 3}))
+ assert(!reflect.DeepEqual(a, []int{0, 1, 2}))
+ assert(!reflect.DeepEqual(a, []int{0, 1, 0, 3}))
+
+ assert(reflect.DeepEqual(b, []X{0, 1, 2, 3}))
+ assert(!reflect.DeepEqual(b, []X{0, 1, 0, 3}))
+
+ assert(reflect.DeepEqual(c, map[int]string{0: "zero", 1: "one"}))
+ assert(!reflect.DeepEqual(c, map[int]string{0: "zero", 1: "one", 2: "two"}))
+ assert(!reflect.DeepEqual(c, map[int]string{1: "one", 2: "two"}))
+ assert(!reflect.DeepEqual(c, map[int]string{1: "one"}))
+
+ assert(reflect.DeepEqual(d, map[X]string{0: "zero", 1: "one"}))
+ assert(!reflect.DeepEqual(d, map[int]string{0: "zero", 1: "one"}))
+
+ assert(reflect.DeepEqual(e, &Y{}))
+ assert(reflect.DeepEqual(e, &Y{z: [3]int{0, 0, 0}}))
+ assert(!reflect.DeepEqual(e, &Y{z: [3]int{0, 1, 0}}))
+
+ assert(reflect.DeepEqual(f, (*Y)(nil)))
+ assert(!reflect.DeepEqual(f, nil))
+
+ // eq_h -> eq_h. Pointer structure and elements are equal so DeepEqual.
+ eq_h := &Y{}
+ eq_h.y = eq_h
+ assert(reflect.DeepEqual(h, eq_h))
+
+ // deepeq_h->h->h. Pointed to elem of (deepeq_h, h) are (h,h). (h,h) are deep equal so h and deepeq_h are DeepEqual.
+ deepeq_h := &Y{}
+ deepeq_h.y = h
+ assert(reflect.DeepEqual(h, deepeq_h))
+
+ distinct := []interface{}{a, b, c, d, e, f, g, h}
+ for x := range distinct {
+ for y := range distinct {
+ assert((x == y) == reflect.DeepEqual(distinct[x], distinct[y]))
+ }
+ }
+
+ // anonymous struct types.
+ assert(reflect.DeepEqual(struct{}{}, struct{}{}))
+ assert(reflect.DeepEqual(struct{ x int }{1}, struct{ x int }{1}))
+ assert(!reflect.DeepEqual(struct{ x int }{}, struct{ x int }{5}))
+ assert(!reflect.DeepEqual(struct{ x, y int }{0, 1}, struct{ x int }{0}))
+ assert(reflect.DeepEqual(struct{ x, y int }{2, 3}, struct{ x, y int }{2, 3}))
+ assert(!reflect.DeepEqual(struct{ x, y int }{4, 5}, struct{ x, y int }{4, 6}))
+}
diff --git a/go/ssa/interp/testdata/src/reflect/deepequal.go b/go/ssa/interp/testdata/src/reflect/deepequal.go
new file mode 100644
index 0000000..a48e4da
--- /dev/null
+++ b/go/ssa/interp/testdata/src/reflect/deepequal.go
@@ -0,0 +1,109 @@
+package reflect
+
+// Not an actual implementation of DeepEqual. This is a model that supports
+// the bare minimum needed to get through testing interp.
+//
+// Does not handle cycles.
+//
+// Note: unclear if reflect.go can support this.
+func DeepEqual(x, y interface{}) bool {
+ if x == nil || y == nil {
+ return x == y
+ }
+ v1 := ValueOf(x)
+ v2 := ValueOf(y)
+
+ return deepValueEqual(v1, v2, make(map[visit]bool))
+}
+
+// Key for the visitedMap in deepValueEqual.
+type visit struct {
+ a1, a2 uintptr
+ typ Type
+}
+
+func deepValueEqual(v1, v2 Value, visited map[visit]bool) bool {
+ if !v1.IsValid() || !v2.IsValid() {
+ return v1.IsValid() == v2.IsValid()
+ }
+ if v1.Type() != v2.Type() {
+ return false
+ }
+
+ // Short circuit on reference types that can lead to cycles in comparison.
+ switch v1.Kind() {
+ case Pointer, Map, Slice, Interface:
+ k := visit{v1.Pointer(), v2.Pointer(), v1.Type()} // Not safe for moving GC.
+ if visited[k] {
+ // The comparison algorithm assumes that all checks in progress are true when it reencounters them.
+ return true
+ }
+ visited[k] = true
+ }
+
+ switch v1.Kind() {
+ case Array:
+ for i := 0; i < v1.Len(); i++ {
+ if !deepValueEqual(v1.Index(i), v2.Index(i), visited) {
+ return false
+ }
+ }
+ return true
+ case Slice:
+ if v1.IsNil() != v2.IsNil() {
+ return false
+ }
+ if v1.Len() != v2.Len() {
+ return false
+ }
+ if v1.Pointer() == v2.Pointer() {
+ return true
+ }
+ for i := 0; i < v1.Len(); i++ {
+ if !deepValueEqual(v1.Index(i), v2.Index(i), visited) {
+ return false
+ }
+ }
+ return true
+ case Interface:
+ if v1.IsNil() || v2.IsNil() {
+ return v1.IsNil() == v2.IsNil()
+ }
+ return deepValueEqual(v1.Elem(), v2.Elem(), visited)
+ case Ptr:
+ if v1.Pointer() == v2.Pointer() {
+ return true
+ }
+ return deepValueEqual(v1.Elem(), v2.Elem(), visited)
+ case Struct:
+ for i, n := 0, v1.NumField(); i < n; i++ {
+ if !deepValueEqual(v1.Field(i), v2.Field(i), visited) {
+ return false
+ }
+ }
+ return true
+ case Map:
+ if v1.IsNil() != v2.IsNil() {
+ return false
+ }
+ if v1.Len() != v2.Len() {
+ return false
+ }
+ if v1.Pointer() == v2.Pointer() {
+ return true
+ }
+ for _, k := range v1.MapKeys() {
+ val1 := v1.MapIndex(k)
+ val2 := v2.MapIndex(k)
+ if !val1.IsValid() || !val2.IsValid() || !deepValueEqual(val1, val2, visited) {
+ return false
+ }
+ }
+ return true
+ case Func:
+ return v1.IsNil() && v2.IsNil()
+ default:
+ // Normal equality suffices
+ return v1.Interface() == v2.Interface() // try interface comparison as a fallback.
+ }
+}
diff --git a/go/ssa/interp/testdata/src/reflect/reflect.go b/go/ssa/interp/testdata/src/reflect/reflect.go
index 8a23d27..207e7dc 100644
--- a/go/ssa/interp/testdata/src/reflect/reflect.go
+++ b/go/ssa/interp/testdata/src/reflect/reflect.go
@@ -11,9 +11,20 @@
func (Value) String() string
-func (Value) Elem() string
+func (Value) Elem() Value
func (Value) Kind() Kind
func (Value) Int() int64
+func (Value) IsValid() bool
+func (Value) IsNil() bool
+func (Value) Len() int
+func (Value) Pointer() uintptr
+func (Value) Index(i int) Value
+func (Value) Type() Type
+func (Value) Field(int) Value
+func (Value) MapIndex(Value) Value
+func (Value) MapKeys() []Value
+func (Value) NumField() int
+func (Value) Interface() interface{}
func SliceOf(Type) Type
