From a439f6622812865898d1a07a3ee66dc0cfda1cc0 Mon Sep 17 00:00:00 2001
From: Russ Cox <rsc@golang.org>
Date: Wed, 1 Jul 2009 16:45:09 -0700
Subject: [PATCH] add test, fix bug: structs that differ in their first field
 were not being handled correctly because the visited map did not include the
 type.

R=r
OCL=31006
CL=31006
---
 src/pkg/reflect/all_test.go  |  3 +++
 src/pkg/reflect/deepequal.go | 42 ++++++++++++++++++++++++++++--------
 src/pkg/reflect/value.go     |  2 +-
 3 files changed, 37 insertions(+), 10 deletions(-)

diff --git a/src/pkg/reflect/all_test.go b/src/pkg/reflect/all_test.go
index 9cfc7e2688..fcbe473bef 100644
--- a/src/pkg/reflect/all_test.go
+++ b/src/pkg/reflect/all_test.go
@@ -420,6 +420,7 @@ var deepEqualTests = []DeepEqualTest {
 	DeepEqualTest{ &[3]int{ 1, 2, 3 }, &[3]int{ 1, 2, 3 }, true },
 	DeepEqualTest{ Basic{ 1, 0.5 }, Basic{ 1, 0.5 }, true },
 	DeepEqualTest{ os.Error(nil), os.Error(nil), true },
+
 	// Inequalities
 	DeepEqualTest{ 1, 2, false },
 	DeepEqualTest{ int32(1), int32(2), false },
@@ -429,6 +430,8 @@ var deepEqualTests = []DeepEqualTest {
 	DeepEqualTest{ make([]int, 10), make([]int, 11), false },
 	DeepEqualTest{ &[3]int{ 1, 2, 3 }, &[3]int{ 1, 2, 4 }, false },
 	DeepEqualTest{ Basic{ 1, 0.5 }, Basic{ 1, 0.6 }, false },
+	DeepEqualTest{ Basic{ 1, 0 }, Basic{ 2, 0 }, false },
+
 	// Mismatched types
 	DeepEqualTest{ 1, 1.0, false },
 	DeepEqualTest{ int32(1), int64(1), false },
diff --git a/src/pkg/reflect/deepequal.go b/src/pkg/reflect/deepequal.go
index 0195a43a63..d4299edb57 100644
--- a/src/pkg/reflect/deepequal.go
+++ b/src/pkg/reflect/deepequal.go
@@ -8,33 +8,57 @@ package reflect
 
 import "reflect"
 
+// 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 are stored in a map indexed by 17 * a1 + a2;
+type visit struct {
+	a1 uintptr;
+	a2 uintptr;
+	typ Type;
+	next *visit;
+}
+
 // 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[Addr]Addr, depth int) bool {
+func deepValueEqual(v1, v2 Value, visited map[uintptr]*visit, depth int) bool {
 	if v1 == nil {
 		return v2 == nil
 	}
 	if v2 == nil {
 		return false
 	}
-	if v1.Kind() != v2.Kind() {
+	if !equalType(v1.Type(), v2.Type()) {
 		return false;
 	}
 
 	// if depth > 10 { panic("deepValueEqual") }	// for debugging
 
-	// Short circuit if references are identical or already seen
-	addr1 := v1.Addr();
-	addr2 := v2.Addr();
+	addr1 := uintptr(v1.Addr());
+	addr2 := uintptr(v2.Addr());
+	if addr1 > addr2 {
+		// Canonicalize order to reduce number of entries in visited.
+		addr1, addr2 = addr2, addr1;
+	}
 
+	// Short circuit if references are identical ...
 	if addr1 == addr2 {
 		return true;
 	}
-	if vaddr, ok := visited[addr1]; ok && vaddr == addr2 {
-		return true;
+
+	// ... or already seen
+	h := 17 * addr1 + addr2;
+	seen, ok := visited[h];
+	typ := v1.Type();
+	for p := seen; p != nil; p = p.next {
+		if p.a1 == addr1 && p.a2 == addr2 && p.typ == typ {
+			return true;
+		}
 	}
-	visited[addr1] = addr2;
+
+	// Remember for later.
+	visited[h] = &visit{addr1, addr2, typ, seen};
 
 	switch v1.Kind() {
 	case ArrayKind:
@@ -91,5 +115,5 @@ func DeepEqual(a1, a2 interface{}) bool {
 	if !equalType(v1.Type(), v2.Type()) {
 		return false;
 	}
-	return deepValueEqual(v1, v2, make(map[Addr]Addr), 0);
+	return deepValueEqual(v1, v2, make(map[uintptr]*visit), 0);
 }
diff --git a/src/pkg/reflect/value.go b/src/pkg/reflect/value.go
index 61410af997..f59e3a2729 100644
--- a/src/pkg/reflect/value.go
+++ b/src/pkg/reflect/value.go
@@ -16,7 +16,7 @@ import (
 type Addr unsafe.Pointer
 
 func equalType(a, b Type) bool {
-	return a.String() == b.String()
+	return a.Kind() == b.Kind() && a.String() == b.String()
 }
 
 // Value is the generic interface to reflection values.  Once its Kind is known,
-- 
2.48.1