shithub: mc

Download patch

ref: 12b66049f3881fa6b36ed803358c659a96071e16
parent: 6b42532ddf1b3ebfd1c5b9b369f8478a7d8711ea
author: Ori Bernstein <ori@eigenstate.org>
date: Sat Aug 26 15:17:20 EDT 2017 

Add monotonically increasing equality check.

	Because unlike the bit sets, nothing gets removed from
	here, we should either converge on equality, or error out.


--- a/parse/parse.h
+++ b/parse/parse.h
@@ -120,7 +120,7 @@
 
 struct Type {
 	Ty type;
-	int tid;
+	uint32_t tid;
 	Srcloc loc;
 	Vis vis;
 
--- a/parse/type.c
+++ b/parse/type.c
@@ -15,6 +15,7 @@
 #include "parse.h"
 
 typedef struct Typename Typename;
+typedef struct Typair Typair;
 Type **tytab = NULL;
 Type **types = NULL;
 size_t ntypes;
@@ -22,7 +23,14 @@
 size_t ntraittab;
 Node **impltab;
 size_t nimpltab;
+Htab *eqcache;
 
+struct Typair {
+	uint32_t atid;
+	uint32_t btid;
+};
+	
+
 static Htab *tydeduptab;
 /* Built in type constraints */
 static int tybfmt(char *buf, size_t len, Bitset *visted, Type *t);
@@ -715,7 +723,44 @@
 	return hash;
 }
 
+ulong
+typairhash(void *pp)
+{
+	Typair *p;
+
+	p = pp;
+	return inthash(p->atid) ^ inthash(p->btid);
+}
+
 int
+typaireq(void *a, void *b)
+{
+	Typair *pa, *pb;
+	pa = a;
+	pb = b;
+	return pa->atid == pb->atid && pa->btid == pb->btid;
+}
+
+void
+equate(int32_t ta, int32_t tb)
+{
+	Typair *pa, *pb;
+
+	/*
+	 * unfortunately, we can't negatively cache
+	 * here because tyvars may unify down and
+	 * eventually make the negative result inaccurate.
+	 */
+	pa = zalloc(sizeof(Typair));
+	*pa = (Typair){ta, tb};
+	pb = zalloc(sizeof(Typair));
+	*pb = (Typair){ta, tb};
+
+	htput(eqcache, pa, pa);
+	htput(eqcache, pb, pb);
+}
+
+int
 tyeq_rec(Type *a, Type *b, Bitset *avisited, Bitset *bvisited, int search)
 {
 	Type *x, *y;
@@ -736,6 +781,8 @@
 		return 0;
 	if (a->nmemb != b->nmemb)
 		return 0;
+	if (hthas(eqcache, &(Typair){a->tid, b->tid}))
+		return 1;
 
 	if (a->tid == b->tid)
 		return 1;
@@ -784,16 +831,22 @@
 				break;
 		}
 		break;
+	case Tygeneric:
+		if (!nameeq(a->name, b->name))
+			ret = 0;
+		for (i = 0; i < a->ngparam; i++) {
+			ret = ret && tyeq_rec(a->gparam[i], b->gparam[i], avisited, bvisited, search);
+			if (!ret)
+				break;
+		}
+		break;
 	case Tyname:
 		if (!nameeq(a->name, b->name))
 			ret = 0;
 		for (i = 0; i < a->narg; i++) {
-			x = a->arg[i];
-			y = b->arg[i];
-			if (!tyeq_rec(x, y, avisited, bvisited, search)) {
-				ret = 0;
+			ret = ret && tyeq_rec(a->arg[i], b->arg[i], avisited, bvisited, search);
+			if (!ret)
 				break;
-			}
 		}
 		break;
 	case Tyarray:
@@ -813,6 +866,8 @@
 			}
 		}
 	}
+	if (ret) {
+	}
 	bsdel(avisited, a->tid);
 	bsdel(bvisited, b->tid);
 
@@ -1026,6 +1081,7 @@
 	Type *ty;
 	Trait *tr;
 
+	eqcache = mkht(typairhash, typaireq);
 	tydeduptab = mkht(tyhash, tystricteq);
 	/* this must be done after all the types are created, otherwise we will
 	 * clobber the memoized bunch of types with the type params. */