aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorAyke van Laethem <[email protected]>2020-10-29 17:39:11 +0100
committerRon Evans <[email protected]>2021-11-12 21:27:27 +0100
commit335fb71d2ff561fb02bf4d3dd16588b07a76abe6 (patch)
tree8a935c6d4adba5661d4c4b9dca137987d593be61
parent5866a47e77e2cecb794267fe2e0505187b7a31ca (diff)
downloadtinygo-335fb71d2ff561fb02bf4d3dd16588b07a76abe6.tar.gz
tinygo-335fb71d2ff561fb02bf4d3dd16588b07a76abe6.zip
reflect: add support for DeepEqual
The implementation has been mostly copied from the Go reference implementation with some small changes to fit TinyGo. Source: https://github.com/golang/go/blob/77a11c05d6a6f766c75f804ea9b8796f9a9f85a3/src/reflect/deepequal.go In addition, this commit also contains the following: - A set of tests copied from the Go reflect package. - An increased stack size for the riscv-qemu and hifive1-qemu targets (because they otherwise fail to run the tests). Because these targets are only used for testing, this seems fine to me.
-rw-r--r--Makefile4
-rw-r--r--src/reflect/all_test.go188
-rw-r--r--src/reflect/deepequal.go191
-rw-r--r--src/reflect/value.go14
-rw-r--r--targets/hifive1-qemu.json1
-rw-r--r--targets/riscv-qemu.json1
-rw-r--r--testdata/reflect.go40
7 files changed, 432 insertions, 7 deletions
diff --git a/Makefile b/Makefile
index 2f89585e1..68b66c10a 100644
--- a/Makefile
+++ b/Makefile
@@ -210,11 +210,13 @@ TEST_PACKAGES = \
index/suffixarray \
math \
math/cmplx \
+ net/mail \
+ reflect \
testing \
testing/iotest \
text/scanner \
- text/scanner \
unicode \
+ unicode/utf16 \
unicode/utf8 \
# Test known-working standard library packages.
diff --git a/src/reflect/all_test.go b/src/reflect/all_test.go
new file mode 100644
index 000000000..c928f7dcd
--- /dev/null
+++ b/src/reflect/all_test.go
@@ -0,0 +1,188 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package reflect_test
+
+import (
+ "math"
+ . "reflect"
+ "testing"
+)
+
+type Basic struct {
+ x int
+ y float32
+}
+
+type NotBasic Basic
+
+type DeepEqualTest struct {
+ a, b interface{}
+ eq bool
+}
+
+// Simple functions for DeepEqual tests.
+var (
+ fn1 func() // nil.
+ fn2 func() // nil.
+ fn3 = func() { fn1() } // Not nil.
+)
+
+type self struct{}
+
+type Loopy interface{}
+
+var loopy1, loopy2 Loopy
+var cycleMap1, cycleMap2, cycleMap3 map[string]interface{}
+
+type structWithSelfPtr struct {
+ p *structWithSelfPtr
+ s string
+}
+
+func init() {
+ loopy1 = &loopy2
+ loopy2 = &loopy1
+
+ cycleMap1 = map[string]interface{}{}
+ cycleMap1["cycle"] = cycleMap1
+ cycleMap2 = map[string]interface{}{}
+ cycleMap2["cycle"] = cycleMap2
+ cycleMap3 = map[string]interface{}{}
+ cycleMap3["different"] = cycleMap3
+}
+
+// Note: all tests involving maps have been commented out because they aren't
+// supported yet.
+var deepEqualTests = []DeepEqualTest{
+ // Equalities
+ {nil, nil, true},
+ {1, 1, true},
+ {int32(1), int32(1), true},
+ {0.5, 0.5, true},
+ {float32(0.5), float32(0.5), true},
+ {"hello", "hello", true},
+ {make([]int, 10), make([]int, 10), true},
+ {&[3]int{1, 2, 3}, &[3]int{1, 2, 3}, true},
+ {Basic{1, 0.5}, Basic{1, 0.5}, true},
+ {error(nil), error(nil), true},
+ //{map[int]string{1: "one", 2: "two"}, map[int]string{2: "two", 1: "one"}, true},
+ {fn1, fn2, true},
+ {[]byte{1, 2, 3}, []byte{1, 2, 3}, true},
+ {[]MyByte{1, 2, 3}, []MyByte{1, 2, 3}, true},
+ {MyBytes{1, 2, 3}, MyBytes{1, 2, 3}, true},
+
+ // Inequalities
+ {1, 2, false},
+ {int32(1), int32(2), false},
+ {0.5, 0.6, false},
+ {float32(0.5), float32(0.6), false},
+ {"hello", "hey", false},
+ {make([]int, 10), make([]int, 11), false},
+ {&[3]int{1, 2, 3}, &[3]int{1, 2, 4}, false},
+ {Basic{1, 0.5}, Basic{1, 0.6}, false},
+ {Basic{1, 0}, Basic{2, 0}, false},
+ //{map[int]string{1: "one", 3: "two"}, map[int]string{2: "two", 1: "one"}, false},
+ //{map[int]string{1: "one", 2: "txo"}, map[int]string{2: "two", 1: "one"}, false},
+ //{map[int]string{1: "one"}, map[int]string{2: "two", 1: "one"}, false},
+ //{map[int]string{2: "two", 1: "one"}, map[int]string{1: "one"}, false},
+ {nil, 1, false},
+ {1, nil, false},
+ {fn1, fn3, false},
+ {fn3, fn3, false},
+ {[][]int{{1}}, [][]int{{2}}, false},
+ {&structWithSelfPtr{p: &structWithSelfPtr{s: "a"}}, &structWithSelfPtr{p: &structWithSelfPtr{s: "b"}}, false},
+
+ // Fun with floating point.
+ {math.NaN(), math.NaN(), false},
+ {&[1]float64{math.NaN()}, &[1]float64{math.NaN()}, false},
+ {&[1]float64{math.NaN()}, self{}, true},
+ {[]float64{math.NaN()}, []float64{math.NaN()}, false},
+ {[]float64{math.NaN()}, self{}, true},
+ //{map[float64]float64{math.NaN(): 1}, map[float64]float64{1: 2}, false},
+ //{map[float64]float64{math.NaN(): 1}, self{}, true},
+
+ // Nil vs empty: not the same.
+ {[]int{}, []int(nil), false},
+ {[]int{}, []int{}, true},
+ {[]int(nil), []int(nil), true},
+ //{map[int]int{}, map[int]int(nil), false},
+ //{map[int]int{}, map[int]int{}, true},
+ //{map[int]int(nil), map[int]int(nil), true},
+
+ // Mismatched types
+ {1, 1.0, false},
+ {int32(1), int64(1), false},
+ {0.5, "hello", false},
+ {[]int{1, 2, 3}, [3]int{1, 2, 3}, false},
+ {&[3]interface{}{1, 2, 4}, &[3]interface{}{1, 2, "s"}, false},
+ {Basic{1, 0.5}, NotBasic{1, 0.5}, false},
+ {map[uint]string{1: "one", 2: "two"}, map[int]string{2: "two", 1: "one"}, false},
+ {[]byte{1, 2, 3}, []MyByte{1, 2, 3}, false},
+ {[]MyByte{1, 2, 3}, MyBytes{1, 2, 3}, false},
+ {[]byte{1, 2, 3}, MyBytes{1, 2, 3}, false},
+
+ // Possible loops.
+ {&loopy1, &loopy1, true},
+ {&loopy1, &loopy2, true},
+ //{&cycleMap1, &cycleMap2, true},
+ {&cycleMap1, &cycleMap3, false},
+}
+
+func TestDeepEqual(t *testing.T) {
+ for _, test := range deepEqualTests {
+ if test.b == (self{}) {
+ test.b = test.a
+ }
+ if r := DeepEqual(test.a, test.b); r != test.eq {
+ t.Errorf("DeepEqual(%#v, %#v) = %v, want %v", test.a, test.b, r, test.eq)
+ }
+ }
+}
+
+type Recursive struct {
+ x int
+ r *Recursive
+}
+
+func TestDeepEqualRecursiveStruct(t *testing.T) {
+ a, b := new(Recursive), new(Recursive)
+ *a = Recursive{12, a}
+ *b = Recursive{12, b}
+ if !DeepEqual(a, b) {
+ t.Error("DeepEqual(recursive same) = false, want true")
+ }
+}
+
+type _Complex struct {
+ a int
+ b [3]*_Complex
+ c *string
+ d map[float64]float64
+}
+
+func TestDeepEqualComplexStruct(t *testing.T) {
+ m := make(map[float64]float64)
+ stra, strb := "hello", "hello"
+ a, b := new(_Complex), new(_Complex)
+ *a = _Complex{5, [3]*_Complex{a, b, a}, &stra, m}
+ *b = _Complex{5, [3]*_Complex{b, a, a}, &strb, m}
+ if !DeepEqual(a, b) {
+ t.Error("DeepEqual(complex same) = false, want true")
+ }
+}
+
+func TestDeepEqualComplexStructInequality(t *testing.T) {
+ m := make(map[float64]float64)
+ stra, strb := "hello", "helloo" // Difference is here
+ a, b := new(_Complex), new(_Complex)
+ *a = _Complex{5, [3]*_Complex{a, b, a}, &stra, m}
+ *b = _Complex{5, [3]*_Complex{b, a, a}, &strb, m}
+ if DeepEqual(a, b) {
+ t.Error("DeepEqual(complex different) = true, want false")
+ }
+}
+
+type MyBytes []byte
+type MyByte byte
diff --git a/src/reflect/deepequal.go b/src/reflect/deepequal.go
index 32719c34d..5bd132d6c 100644
--- a/src/reflect/deepequal.go
+++ b/src/reflect/deepequal.go
@@ -1,9 +1,196 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Deep equality test via reflection
+
package reflect
+import "unsafe"
+
+// During deepValueEqual, must keep track of checks that are
+// in progress. The comparison algorithm assumes that all
+// checks in progress are true when it reencounters them.
+// Visited comparisons are stored in a map indexed by visit.
+type visit struct {
+ a1 unsafe.Pointer
+ a2 unsafe.Pointer
+ typ rawType
+}
+
+// Tests for deep equality using reflected types. The map argument tracks
+// comparisons that have already been seen, which allows short circuiting on
+// recursive types.
+func deepValueEqual(v1, v2 Value, visited map[visit]struct{}) bool {
+ if !v1.IsValid() || !v2.IsValid() {
+ return v1.IsValid() == v2.IsValid()
+ }
+ if v1.typecode != v2.typecode {
+ return false
+ }
+
+ // We want to avoid putting more in the visited map than we need to.
+ // For any possible reference cycle that might be encountered,
+ // hard(v1, v2) needs to return true for at least one of the types in the cycle,
+ // and it's safe and valid to get Value's internal pointer.
+ hard := func(v1, v2 Value) bool {
+ switch v1.Kind() {
+ case Map, Slice, Ptr, Interface:
+ // Nil pointers cannot be cyclic. Avoid putting them in the visited map.
+ return !v1.IsNil() && !v2.IsNil()
+ }
+ return false
+ }
+
+ if hard(v1, v2) {
+ addr1 := v1.pointer()
+ addr2 := v2.pointer()
+ if uintptr(addr1) > uintptr(addr2) {
+ // Canonicalize order to reduce number of entries in visited.
+ // Assumes non-moving garbage collector.
+ addr1, addr2 = addr2, addr1
+ }
+
+ // Short circuit if references are already seen.
+ v := visit{addr1, addr2, v1.typecode}
+ if _, ok := visited[v]; ok {
+ return true
+ }
+
+ // Remember for later.
+ visited[v] = struct{}{}
+ }
+
+ 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:
+ if v1.IsNil() && v2.IsNil() {
+ return true
+ }
+ // Can't do better than this:
+ return false
+ default:
+ // Normal equality suffices
+ return valueInterfaceUnsafe(v1) == valueInterfaceUnsafe(v2)
+ }
+}
+
+// DeepEqual reports whether x and y are ``deeply equal,'' defined as follows.
+// Two values of identical type are deeply equal if one of the following cases applies.
+// Values of distinct types are never deeply equal.
+//
+// Array values are deeply equal when their corresponding elements are deeply equal.
+//
+// Struct values are deeply equal if their corresponding fields,
+// both exported and unexported, are deeply equal.
+//
+// Func values are deeply equal if both are nil; otherwise they are not deeply equal.
+//
+// Interface values are deeply equal if they hold deeply equal concrete values.
+//
+// Map values are deeply equal when all of the following are true:
+// they are both nil or both non-nil, they have the same length,
+// and either they are the same map object or their corresponding keys
+// (matched using Go equality) map to deeply equal values.
+//
+// Pointer values are deeply equal if they are equal using Go's == operator
+// or if they point to deeply equal values.
+//
+// Slice values are deeply equal when all of the following are true:
+// they are both nil or both non-nil, they have the same length,
+// and either they point to the same initial entry of the same underlying array
+// (that is, &x[0] == &y[0]) or their corresponding elements (up to length) are deeply equal.
+// Note that a non-nil empty slice and a nil slice (for example, []byte{} and []byte(nil))
+// are not deeply equal.
+//
+// Other values - numbers, bools, strings, and channels - are deeply equal
+// if they are equal using Go's == operator.
+//
+// In general DeepEqual is a recursive relaxation of Go's == operator.
+// However, this idea is impossible to implement without some inconsistency.
+// Specifically, it is possible for a value to be unequal to itself,
+// either because it is of func type (uncomparable in general)
+// or because it is a floating-point NaN value (not equal to itself in floating-point comparison),
+// or because it is an array, struct, or interface containing
+// such a value.
+// On the other hand, pointer values are always equal to themselves,
+// even if they point at or contain such problematic values,
+// because they compare equal using Go's == operator, and that
+// is a sufficient condition to be deeply equal, regardless of content.
+// DeepEqual has been defined so that the same short-cut applies
+// to slices and maps: if x and y are the same slice or the same map,
+// they are deeply equal regardless of content.
+//
+// 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.
func DeepEqual(x, y interface{}) bool {
if x == nil || y == nil {
return x == y
}
-
- panic("unimplemented: reflect.DeepEqual()")
+ v1 := ValueOf(x)
+ v2 := ValueOf(y)
+ if v1.typecode != v2.typecode {
+ return false
+ }
+ return deepValueEqual(v1, v2, make(map[visit]struct{}))
}
diff --git a/src/reflect/value.go b/src/reflect/value.go
index abc35fb86..657751c84 100644
--- a/src/reflect/value.go
+++ b/src/reflect/value.go
@@ -140,10 +140,7 @@ func (v Value) IsNil() bool {
func (v Value) Pointer() uintptr {
switch v.Kind() {
case Chan, Map, Ptr, UnsafePointer:
- if v.isIndirect() {
- return *(*uintptr)(v.value)
- }
- return uintptr(v.value)
+ return uintptr(v.pointer())
case Slice:
slice := (*sliceHeader)(v.value)
return uintptr(slice.data)
@@ -154,6 +151,15 @@ func (v Value) Pointer() uintptr {
}
}
+// pointer returns the underlying pointer represented by v.
+// v.Kind() must be Ptr, Map, Chan, or UnsafePointer
+func (v Value) pointer() unsafe.Pointer {
+ if v.isIndirect() {
+ return *(*unsafe.Pointer)(v.value)
+ }
+ return v.value
+}
+
func (v Value) IsValid() bool {
return v.typecode != 0
}
diff --git a/targets/hifive1-qemu.json b/targets/hifive1-qemu.json
index 60fe27a4d..115189438 100644
--- a/targets/hifive1-qemu.json
+++ b/targets/hifive1-qemu.json
@@ -2,6 +2,7 @@
"inherits": ["fe310"],
"build-tags": ["hifive1b", "qemu"],
"serial": "uart",
+ "default-stack-size": 4096,
"linkerscript": "targets/hifive1-qemu.ld",
"emulator": ["qemu-system-riscv32", "-machine", "sifive_e", "-nographic", "-kernel"]
}
diff --git a/targets/riscv-qemu.json b/targets/riscv-qemu.json
index 0af2ef874..a8805dfd6 100644
--- a/targets/riscv-qemu.json
+++ b/targets/riscv-qemu.json
@@ -2,6 +2,7 @@
"inherits": ["riscv32"],
"features": "+a,+c,+m,-relax,-save-restore",
"build-tags": ["virt", "qemu"],
+ "default-stack-size": 4096,
"linkerscript": "targets/riscv-qemu.ld",
"emulator": ["qemu-system-riscv32", "-machine", "virt", "-nographic", "-bios", "none", "-kernel"]
}
diff --git a/testdata/reflect.go b/testdata/reflect.go
index ac5b7ee0b..7e21abdcb 100644
--- a/testdata/reflect.go
+++ b/testdata/reflect.go
@@ -27,6 +27,9 @@ type (
next *linkedList `description:"chain"`
foo int
}
+ selfref struct {
+ x *selfref
+ }
)
var (
@@ -326,6 +329,43 @@ func main() {
println("\nv.Interface() method")
testInterfaceMethod()
+
+ // Test reflect.DeepEqual.
+ var selfref1, selfref2 selfref
+ selfref1.x = &selfref1
+ selfref2.x = &selfref2
+ for i, tc := range []struct {
+ v1, v2 interface{}
+ equal bool
+ }{
+ {int(5), int(5), true},
+ {int(3), int(5), false},
+ {int(5), uint(5), false},
+ {struct {
+ a int
+ b string
+ }{3, "x"}, struct {
+ a int
+ b string
+ }{3, "x"}, true},
+ {struct {
+ a int
+ b string
+ }{3, "x"}, struct {
+ a int
+ b string
+ }{3, "y"}, false},
+ {selfref1, selfref2, true},
+ } {
+ result := reflect.DeepEqual(tc.v1, tc.v2)
+ if result != tc.equal {
+ if tc.equal {
+ println("reflect.DeepEqual() test", i, "not equal while it should be")
+ } else {
+ println("reflect.DeepEqual() test", i, "equal while it should not be")
+ }
+ }
+ }
}
func emptyFunc() {