the last bug involving type hashes

R=ken
OCL=34244
CL=34249

8 files changed, 394 insertions, 58 deletions

diff --git a/src/cmd/gc/Makefile b/src/cmd/gc/Makefile
index c7fa3d6d7..1e116a9ac 100644
--- a/src/cmd/gc/Makefile
+++ b/src/cmd/gc/Makefile
@@ -10,6 +10,7 @@ LIB=\
 HFILES=\
 	go.h\
 	y.tab.h\
+	md5.h\
 
 YFILES=\
 	go.y\
@@ -25,6 +26,7 @@ OFILES=\
 	gen.$O\
 	init.$O\
 	lex.$O\
+	md5.$O\
 	mparith1.$O\
 	mparith2.$O\
 	mparith3.$O\
diff --git a/src/cmd/gc/go.h b/src/cmd/gc/go.h
index bcbc5f84c..b4cf07a75 100644
--- a/src/cmd/gc/go.h
+++ b/src/cmd/gc/go.h
@@ -814,7 +814,7 @@ int	cvttype(Type*, Type*);
 int	eqtypenoname(Type*, Type*);
 void	argtype(Node*, Type*);
 int	eqargs(Type*, Type*);
-uint32	typehash(Type*, int, int);
+uint32	typehash(Type*);
 void	frame(int);
 Node*	nodintconst(int64);
 void	nodconst(Node*, Type*, int64);
diff --git a/src/cmd/gc/md5.c b/src/cmd/gc/md5.c
new file mode 100644
index 000000000..7cea1a6cf
--- /dev/null
+++ b/src/cmd/gc/md5.c
@@ -0,0 +1,290 @@
+// 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.
+
+// 64-bit MD5 (does full MD5 but returns 64 bits only).
+// Translation of ../../pkg/crypto/md5/md5*.go.
+
+#include "go.h"
+#include "md5.h"
+
+static int md5block(MD5 *dig, uchar *p, int nn);
+
+enum {
+	_Chunk = 64
+};
+
+#define _Init0 0x67452301
+#define _Init1 0xEFCDAB89
+#define _Init2 0x98BADCFE
+#define _Init3 0x10325476
+
+void
+md5reset(MD5 *d)
+{
+	d->s[0] = _Init0;
+	d->s[1] = _Init1;
+	d->s[2] = _Init2;
+	d->s[3] = _Init3;
+	d->nx = 0;
+	d->len = 0;
+}
+
+void
+md5write(MD5 *d, uchar *p, int nn)
+{
+	int i, n;
+
+	d->len += nn;
+	if(d->nx > 0) {
+		n = nn;
+		if(n > _Chunk - d->nx)
+			n = _Chunk - d->nx;
+		for(i=0; i<n; i++)
+			d->x[d->nx+i] = p[i];
+		d->nx += n;
+		if(d->nx == _Chunk) {
+			md5block(d, d->x, _Chunk);
+			d->nx = 0;
+		}
+		p += n;
+		nn -= n;
+	}
+	n = md5block(d, p, nn);
+	p += n;
+	nn -= n;
+	if(nn > 0) {
+		for(i=0; i<nn; i++)
+			d->x[i] = p[i];
+		d->nx = nn;
+	}
+}
+
+uint64
+md5sum(MD5 *d)
+{
+	uchar tmp[64];
+	int i;
+	uint64 len;
+
+	// Padding.  Add a 1 bit and 0 bits until 56 bytes mod 64.
+	len = d->len;
+	memset(tmp, 0, sizeof tmp);
+	tmp[0] = 0x80;
+	if(len%64 < 56)
+		md5write(d, tmp, 56-len%64);
+	else
+		md5write(d, tmp, 64+56-len%64);
+
+	// Length in bits.
+	len <<= 3;
+	for(i=0; i<8; i++)
+		tmp[i] = len>>(8*i);
+	md5write(d, tmp, 8);
+
+	if(d->nx != 0)
+		fatal("md5sum");
+
+	return d->s[0] | ((uint64)d->s[1]<<32);
+}
+
+
+// MD5 block step.
+// In its own file so that a faster assembly or C version
+// can be substituted easily.
+
+// table[i] = int((1<<32) * abs(sin(i+1 radians))).
+static uint32 table[64] = {
+	// round 1
+	0xd76aa478,
+	0xe8c7b756,
+	0x242070db,
+	0xc1bdceee,
+	0xf57c0faf,
+	0x4787c62a,
+	0xa8304613,
+	0xfd469501,
+	0x698098d8,
+	0x8b44f7af,
+	0xffff5bb1,
+	0x895cd7be,
+	0x6b901122,
+	0xfd987193,
+	0xa679438e,
+	0x49b40821,
+
+	// round 2
+	0xf61e2562,
+	0xc040b340,
+	0x265e5a51,
+	0xe9b6c7aa,
+	0xd62f105d,
+	0x2441453,
+	0xd8a1e681,
+	0xe7d3fbc8,
+	0x21e1cde6,
+	0xc33707d6,
+	0xf4d50d87,
+	0x455a14ed,
+	0xa9e3e905,
+	0xfcefa3f8,
+	0x676f02d9,
+	0x8d2a4c8a,
+
+	// round3
+	0xfffa3942,
+	0x8771f681,
+	0x6d9d6122,
+	0xfde5380c,
+	0xa4beea44,
+	0x4bdecfa9,
+	0xf6bb4b60,
+	0xbebfbc70,
+	0x289b7ec6,
+	0xeaa127fa,
+	0xd4ef3085,
+	0x4881d05,
+	0xd9d4d039,
+	0xe6db99e5,
+	0x1fa27cf8,
+	0xc4ac5665,
+
+	// round 4
+	0xf4292244,
+	0x432aff97,
+	0xab9423a7,
+	0xfc93a039,
+	0x655b59c3,
+	0x8f0ccc92,
+	0xffeff47d,
+	0x85845dd1,
+	0x6fa87e4f,
+	0xfe2ce6e0,
+	0xa3014314,
+	0x4e0811a1,
+	0xf7537e82,
+	0xbd3af235,
+	0x2ad7d2bb,
+	0xeb86d391,
+};
+
+static uint32 shift1[] = { 7, 12, 17, 22 };
+static uint32 shift2[] = { 5, 9, 14, 20 };
+static uint32 shift3[] = { 4, 11, 16, 23 };
+static uint32 shift4[] = { 6, 10, 15, 21 };
+
+static int
+md5block(MD5 *dig, uchar *p, int nn)
+{
+	uint32 a, b, c, d, aa, bb, cc, dd;
+	int i, j, n;
+	uint32 X[16];
+
+	a = dig->s[0];
+	b = dig->s[1];
+	c = dig->s[2];
+	d = dig->s[3];
+	n = 0;
+
+	while(nn >= _Chunk) {
+		aa = a;
+		bb = b;
+		cc = c;
+		dd = d;
+
+		for(i=0; i<16; i++) {
+			j = i*4;
+			X[i] = p[j] | (p[j+1]<<8) | (p[j+2]<<16) | (p[j+3]<<24);
+		}
+
+		// Round 1.
+		for(i=0; i<16; i++) {
+			uint32 x, t, s, f;
+			x = i;
+			t = i;
+			s = shift1[i%4];
+			f = ((c ^ d) & b) ^ d;
+			a += f + X[x] + table[t];
+			a = a<<s | a>>(32-s);
+			a += b;
+
+			t = d;
+			d = c;
+			c = b;
+			b = a;
+			a = t;
+		}
+
+		// Round 2.
+		for(i=0; i<16; i++) {
+			uint32 x, t, s, g;
+
+			x = (1+5*i)%16;
+			t = 16+i;
+			s = shift2[i%4];
+			g = ((b ^ c) & d) ^ c;
+			a += g + X[x] + table[t];
+			a = a<<s | a>>(32-s);
+			a += b;
+
+			t = d;
+			d = c;
+			c = b;
+			b = a;
+			a = t;
+		}
+
+		// Round 3.
+		for(i=0; i<16; i++) {
+			uint32 x, t, s, h;
+
+			x = (5+3*i)%16;
+			t = 32+i;
+			s = shift3[i%4];
+			h = b ^ c ^ d;
+			a += h + X[x] + table[t];
+			a = a<<s | a>>(32-s);
+			a += b;
+
+			t = d;
+			d = c;
+			c = b;
+			b = a;
+			a = t;
+		}
+
+		// Round 4.
+		for(i=0; i<16; i++) {
+			uint32 x, s, t, ii;
+
+			x = (7*i)%16;
+			s = shift4[i%4];
+			t = 48+i;
+			ii = c ^ (b | ~d);
+			a += ii + X[x] + table[t];
+			a = a<<s | a>>(32-s);
+			a += b;
+
+			t = d;
+			d = c;
+			c = b;
+			b = a;
+			a = t;
+		}
+
+		a += aa;
+		b += bb;
+		c += cc;
+		d += dd;
+
+		p += _Chunk;
+		n += _Chunk;
+		nn -= _Chunk;
+	}
+
+	dig->s[0] = a;
+	dig->s[1] = b;
+	dig->s[2] = c;
+	dig->s[3] = d;
+	return n;
+}
diff --git a/src/cmd/gc/md5.h b/src/cmd/gc/md5.h
new file mode 100644
index 000000000..f153e30f2
--- /dev/null
+++ b/src/cmd/gc/md5.h
@@ -0,0 +1,16 @@
+// 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.
+
+typedef struct MD5 MD5;
+struct MD5
+{
+	uint32 s[4];
+	uchar x[64];
+	int nx;
+	uint64 len;
+};
+
+void md5reset(MD5*);
+void md5write(MD5*, uchar*, int);
+uint64 md5sum(MD5*);
diff --git a/src/cmd/gc/reflect.c b/src/cmd/gc/reflect.c
index c82875ca8..da63cd0d7 100644
--- a/src/cmd/gc/reflect.c
+++ b/src/cmd/gc/reflect.c
@@ -172,7 +172,7 @@ methods(Type *t)
 		a = b;
 
 		a->name = method->name;
-		a->hash = PRIME8*stringhash(a->name) + PRIME9*typehash(f->type, 0, 0);
+		a->hash = PRIME8*stringhash(a->name) + PRIME9*typehash(f->type);
 		if(!exportname(a->name)) {
 			a->package = method->package;
 			a->hash += PRIME10*stringhash(a->package);
@@ -248,7 +248,7 @@ imethods(Type *t)
 		a = b;
 
 		a->name = f->sym->name;
-		a->hash = PRIME8*stringhash(a->name) + PRIME9*typehash(f->type, 0, 0);
+		a->hash = PRIME8*stringhash(a->name) + PRIME9*typehash(f->type);
 		if(!exportname(a->name)) {
 			a->package = f->sym->package;
 			a->hash += PRIME10*stringhash(a->package);
@@ -411,7 +411,7 @@ dcommontype(Sym *s, int ot, Type *t)
 	//		*nameInfo;
 	//	}
 	ot = duintptr(s, ot, t->width);
-	ot = duint32(s, ot, typehash(t, 1, 0));
+	ot = duint32(s, ot, typehash(t));
 	ot = duint8(s, ot, algtype(t));
 	elem = t;
 	while(elem->etype == TARRAY && elem->bound >= 0)
diff --git a/src/cmd/gc/subr.c b/src/cmd/gc/subr.c
index 0c436de0b..9f160d456 100644
--- a/src/cmd/gc/subr.c
+++ b/src/cmd/gc/subr.c
@@ -3,6 +3,7 @@
 // license that can be found in the LICENSE file.
 
 #include	"go.h"
+#include	"md5.h"
 #include	"y.tab.h"
 #include	"opnames.h"
 
@@ -1892,53 +1893,35 @@ eqargs(Type *t1, Type *t2)
 	return 1;
 }
 
+/*
+ * compute a hash value for type t.
+ * if t is a method type, ignore the receiver
+ * so that the hash can be used in interface checks.
+ * %#-T (which calls Tpretty, above) already contains
+ * all the necessary logic to generate a representation
+ * of the type that completely describes it.
+ * using smprint here avoids duplicating that code.
+ * using md5 here is overkill, but i got tired of
+ * accidental collisions making the runtime think
+ * two types are equal when they really aren't.
+ */
 uint32
-typehash(Type *at, int addsym, int d)
+typehash(Type *t)
 {
-	uint32 h;
-	Type *t;
-
-	if(at == T)
-		return PRIME2;
-	if(d >= 5)
-		return PRIME3;
-
-	h = at->etype*PRIME4;
-
-	if(addsym && at->sym != S)
-		h += stringhash(at->sym->name);
-
-	switch(at->etype) {
-	default:
-		h += PRIME5 * typehash(at->type, addsym, d+1);
-		break;
-
-	case TINTER:
-		// botch -- should be sorted?
-		for(t=at->type; t!=T; t=t->down)
-			h += PRIME6 * typehash(t, addsym, d+1);
-		break;
-
-	case TSTRUCT:
-		for(t=at->type; t!=T; t=t->down) {
-			if(at->funarg)	// walk into TFIELD in function argument struct
-				h += PRIME7 * typehash(t->type, addsym, d+1);
-			else
-				h += PRIME7 * typehash(t, addsym, d+1);
-		}
-		break;
-
-	case TFUNC:
-		t = at->type;
-		// skip this (receiver) argument
-		if(t != T)
-			t = t->down;
-		for(; t!=T; t=t->down)
-			h += PRIME7 * typehash(t, addsym, d+1);
-		break;
-	}
+	char *p;
+	MD5 d;
 
-	return h;
+	if(t->thistuple) {
+		// hide method receiver from Tpretty
+		t->thistuple = 0;
+		p = smprint("%#-T", t);
+		t->thistuple = 1;
+	}else
+		p = smprint("%#-T", t);
+	md5reset(&d);
+	md5write(&d, (uchar*)p, strlen(p));
+	free(p);
+	return md5sum(&d);
 }
 
 Type*
@@ -2747,7 +2730,7 @@ ifacelookdot(Sym *s, Type *t, int *followptr)
 // check whether non-interface type t
 // satisifes inteface type iface.
 int
-ifaceokT2I(Type *t0, Type *iface, Type **m)
+ifaceokT2I(Type *t0, Type *iface, Type **m, Type **samename)
 {
 	Type *t, *im, *tm, *rcvr;
 	int imhash, followptr;
@@ -2766,10 +2749,11 @@ ifaceokT2I(Type *t0, Type *iface, Type **m)
 	// so we can both be wrong together.
 
 	for(im=iface->type; im; im=im->down) {
-		imhash = typehash(im, 0, 0);
+		imhash = typehash(im->type);
 		tm = ifacelookdot(im->sym, t, &followptr);
-		if(tm == T || typehash(tm, 0, 0) != imhash) {
+		if(tm == T || typehash(tm->type) != imhash) {
 			*m = im;
+			*samename = tm;
 			return 0;
 		}
 		// if pointer receiver in method,
@@ -2779,6 +2763,7 @@ ifaceokT2I(Type *t0, Type *iface, Type **m)
 			if(debug['r'])
 				yyerror("interface pointer mismatch");
 			*m = im;
+			*samename = nil;
 			return 0;
 		}
 	}
@@ -2797,7 +2782,7 @@ ifaceokI2I(Type *i1, Type *i2, Type **m)
 
 	for(m2=i2->type; m2; m2=m2->down) {
 		for(m1=i1->type; m1; m1=m1->down)
-			if(m1->sym == m2->sym && typehash(m1, 0, 0) == typehash(m2, 0, 0))
+			if(m1->sym == m2->sym && typehash(m1) == typehash(m2))
 				goto found;
 		*m = m2;
 		return 0;
@@ -2811,7 +2796,7 @@ runifacechecks(void)
 {
 	Icheck *p;
 	int lno, wrong, needexplicit;
-	Type *m, *t, *iface;
+	Type *m, *t, *iface, *samename;
 
 	lno = lineno;
 	for(p=icheck; p; p=p->next) {
@@ -2819,6 +2804,7 @@ runifacechecks(void)
 		wrong = 0;
 		needexplicit = 0;
 		m = nil;
+		samename = nil;
 		if(isinter(p->dst) && isinter(p->src)) {
 			iface = p->dst;
 			t = p->src;
@@ -2827,20 +2813,26 @@ runifacechecks(void)
 		else if(isinter(p->dst)) {
 			t = p->src;
 			iface = p->dst;
-			wrong = !ifaceokT2I(t, iface, &m);
+			wrong = !ifaceokT2I(t, iface, &m, &samename);
 		} else {
 			t = p->dst;
 			iface = p->src;
-			wrong = !ifaceokT2I(t, iface, &m);
+			wrong = !ifaceokT2I(t, iface, &m, &samename);
 			needexplicit = 1;
 		}
-		if(wrong)
+		if(wrong) {
 			yyerror("%T is not %T\n\tmissing %S%hhT",
 				t, iface, m->sym, m->type);
+			if(samename)
+				print("\tdo have %S%hhT\n", samename->sym, samename->type);
+		}
 		else if(!p->explicit && needexplicit) {
-			if(m)
+			if(m) {
 				yyerror("need type assertion to use %T as %T\n\tmissing %S%hhT",
 					p->src, p->dst, m->sym, m->type);
+				if(samename)
+					print("\tdo have %S%hhT\n", samename->sym, samename->type);
+			}
 			else
 				yyerror("need type assertion to use %T as %T",
 					p->src, p->dst);
diff --git a/src/cmd/gc/swt.c b/src/cmd/gc/swt.c
index 0754d18f5..002bd4ed5 100644
--- a/src/cmd/gc/swt.c
+++ b/src/cmd/gc/swt.c
@@ -357,7 +357,7 @@ mkcaselist(Node *sw, int arg)
 				continue;
 			}
 
-			c->hash = typehash(n->left->left->type, 1, 0);
+			c->hash = typehash(n->left->left->type);
 			c->type = Ttypeconst;
 			continue;
 
diff --git a/test/fixedbugs/bug201.go b/test/fixedbugs/bug201.go
new file mode 100644
index 000000000..81989ffa3
--- /dev/null
+++ b/test/fixedbugs/bug201.go
@@ -0,0 +1,36 @@
+// $G $D/$F.go && $L $F.$A && ./$A.out
+
+// 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 main
+
+type T1 struct { x, y int; }
+type T2 struct { z, w byte; }
+type T3 T1
+
+type MyInt int
+func (MyInt) m(*T1) { }
+
+func main() {
+	{
+		var i interface{} = new(T1);
+		v1, ok1 := i.(*T1);
+		v2, ok2 := i.(*T2);
+		v3, ok3 := i.(*T3);
+		if !ok1 || ok2 || ok3 {
+			panicln("*T1", ok1, ok2, ok3);
+		}
+	}
+	{
+		var i interface{} = MyInt(0);
+		v1, ok1 := i.(interface{ m(*T1) });
+		v2, ok2 := i.(interface{ m(*T2) });
+		v3, ok3 := i.(interface{ m(*T3) });
+		if !ok1 || ok2 || ok3 {
+			panicln("T", ok1, ok2, ok3);
+		}
+	}
+}
+