summaryrefslogtreecommitdiff
path: root/parse
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2017-08-26 19:17:20 -0700
committerOri Bernstein <ori@eigenstate.org>2017-08-26 19:17:20 -0700
commit12b66049f3881fa6b36ed803358c659a96071e16 (patch)
tree598178d8d4d3c47a7f5c33e3fc61b093b2cbf848 /parse
parent6b42532ddf1b3ebfd1c5b9b369f8478a7d8711ea (diff)
downloadmc-12b66049f3881fa6b36ed803358c659a96071e16.tar.gz
Add monotonically increasing equality check.
Because unlike the bit sets, nothing gets removed from here, we should either converge on equality, or error out.
Diffstat (limited to 'parse')
-rw-r--r--parse/parse.h2
-rw-r--r--parse/type.c66
2 files changed, 62 insertions, 6 deletions
diff --git a/parse/parse.h b/parse/parse.h
index 3b4e21e..afed7ef 100644
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -120,7 +120,7 @@ struct Tyenv {
struct Type {
Ty type;
- int tid;
+ uint32_t tid;
Srcloc loc;
Vis vis;
diff --git a/parse/type.c b/parse/type.c
index 2de0add..4d17c37 100644
--- 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,6 +23,13 @@ Trait **traittab;
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 */
@@ -715,6 +723,43 @@ tyhash(void *ty)
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)
{
@@ -736,6 +781,8 @@ tyeq_rec(Type *a, Type *b, Bitset *avisited, Bitset *bvisited, int search)
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 @@ tyeq_rec(Type *a, Type *b, Bitset *avisited, Bitset *bvisited, int search)
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 @@ tyeq_rec(Type *a, Type *b, Bitset *avisited, Bitset *bvisited, int search)
}
}
}
+ if (ret) {
+ }
bsdel(avisited, a->tid);
bsdel(bvisited, b->tid);
@@ -1026,6 +1081,7 @@ tyinit(Stab *st)
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. */