From 427b5bddcd0b0a565c82fe79edc7a8b563b8ea76 Mon Sep 17 00:00:00 2001
From: Russ Cox <rsc@golang.org>
Date: Mon, 23 Jan 2012 09:19:02 -0500
Subject: [PATCH] gc: fix recursion loop in interface comparison

iant's idea.

Fixes #2745.

R=iant, dsymonds
CC=golang-dev
https://golang.org/cl/5536085
---
 src/cmd/gc/subr.c        | 67 ++++++++++++++++++++++++++++++++++------
 test/fixedbugs/bug398.go | 24 ++++++++++++++
 2 files changed, 81 insertions(+), 10 deletions(-)
 create mode 100644 test/fixedbugs/bug398.go

diff --git a/src/cmd/gc/subr.c b/src/cmd/gc/subr.c
index 3b53b97adc..4e9f9e05fd 100644
--- a/src/cmd/gc/subr.c
+++ b/src/cmd/gc/subr.c
@@ -986,6 +986,25 @@ eqnote(Strlit *a, Strlit *b)
 	return memcmp(a->s, b->s, a->len) == 0;
 }
 
+typedef struct TypePairList TypePairList;
+struct TypePairList
+{
+	Type *t1;
+	Type *t2;
+	TypePairList *next;
+};
+
+static int
+onlist(TypePairList *l, Type *t1, Type *t2) 
+{
+	for(; l; l=l->next)
+		if((l->t1 == t1 && l->t2 == t2) || (l->t1 == t2 && l->t2 == t1))
+			return 1;
+	return 0;
+}
+
+static int eqtype1(Type*, Type*, TypePairList*);
+
 // Return 1 if t1 and t2 are identical, following the spec rules.
 //
 // Any cyclic type must go through a named type, and if one is
@@ -995,6 +1014,14 @@ eqnote(Strlit *a, Strlit *b)
 int
 eqtype(Type *t1, Type *t2)
 {
+	return eqtype1(t1, t2, nil);
+}
+
+static int
+eqtype1(Type *t1, Type *t2, TypePairList *assumed_equal)
+{
+	TypePairList l;
+
 	if(t1 == t2)
 		return 1;
 	if(t1 == T || t2 == T || t1->etype != t2->etype)
@@ -1016,16 +1043,24 @@ eqtype(Type *t1, Type *t2)
 		return 0;
 	}
 
+	if(onlist(assumed_equal, t1, t2))
+		return 1;
+	l.next = assumed_equal;
+	l.t1 = t1;
+	l.t2 = t2;
+
 	switch(t1->etype) {
 	case TINTER:
 	case TSTRUCT:
 		for(t1=t1->type, t2=t2->type; t1 && t2; t1=t1->down, t2=t2->down) {
 			if(t1->etype != TFIELD || t2->etype != TFIELD)
 				fatal("struct/interface missing field: %T %T", t1, t2);
-			if(t1->sym != t2->sym || t1->embedded != t2->embedded || !eqtype(t1->type, t2->type) || !eqnote(t1->note, t2->note))
-				return 0;
+			if(t1->sym != t2->sym || t1->embedded != t2->embedded || !eqtype1(t1->type, t2->type, &l) || !eqnote(t1->note, t2->note))
+				goto no;
 		}
-		return t1 == T && t2 == T;
+		if(t1 == T && t2 == T)
+			goto yes;
+		goto no;
 
 	case TFUNC:
 		// Loop over structs: receiver, in, out.
@@ -1039,26 +1074,38 @@ eqtype(Type *t1, Type *t2)
 			for(ta=t1->type, tb=t2->type; ta && tb; ta=ta->down, tb=tb->down) {
 				if(ta->etype != TFIELD || tb->etype != TFIELD)
 					fatal("func struct missing field: %T %T", ta, tb);
-				if(ta->isddd != tb->isddd || !eqtype(ta->type, tb->type))
-					return 0;
+				if(ta->isddd != tb->isddd || !eqtype1(ta->type, tb->type, &l))
+					goto no;
 			}
 			if(ta != T || tb != T)
-				return 0;
+				goto no;
 		}
-		return t1 == T && t2 == T;
+		if(t1 == T && t2 == T)
+			goto yes;
+		goto no;
 	
 	case TARRAY:
 		if(t1->bound != t2->bound)
-			return 0;
+			goto no;
 		break;
 	
 	case TCHAN:
 		if(t1->chan != t2->chan)
-			return 0;
+			goto no;
 		break;
 	}
 
-	return eqtype(t1->down, t2->down) && eqtype(t1->type, t2->type);
+	if(eqtype1(t1->down, t2->down, &l) && eqtype1(t1->type, t2->type, &l))
+		goto yes;
+	goto no;
+
+yes:
+	assumed_equal = l.next;
+	return 1;
+
+no:
+	assumed_equal = l.next;
+	return 0;
 }
 
 // Are t1 and t2 equal struct types when field names are ignored?
diff --git a/test/fixedbugs/bug398.go b/test/fixedbugs/bug398.go
new file mode 100644
index 0000000000..1eee2292c2
--- /dev/null
+++ b/test/fixedbugs/bug398.go
@@ -0,0 +1,24 @@
+// $G $D/$F.go
+
+// Copyright 2012 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.
+
+// Used to crash compiler in interface type equality check.
+
+package p
+
+type I1 interface {
+      F() interface{I1}
+}
+
+type I2 interface {
+      F() interface{I2}
+}       
+
+var v1 I1
+var v2 I2
+
+func f() bool {
+       return v1 == v2
+}
-- 
2.50.0