hash function for abstract syntax trees

4 files changed, 93 insertions, 7 deletions

diff --git a/src/runtime/c/gu/string.c b/src/runtime/c/gu/string.c
index 7ffd43068..7655b32ab 100644
--- a/src/runtime/c/gu/string.c
+++ b/src/runtime/c/gu/string.c
@@ -367,15 +367,15 @@ gu_string_is_prefix(GuString s1, GuString s2)
 	return true;
 }
 
-GuWord
-gu_string_hash(GuString s)
+GuHash
+gu_string_hash(GuHash h, GuString s)
 {
 	if (s.w_ & 1) {
-		return s.w_;
+		return h*101 + s.w_;
 	}
 	size_t len = gu_string_length(s);
 	uint8_t* data = gu_string_long_data(s);
-	return gu_hash_bytes(0, data, len);
+	return gu_hash_bytes(h, data, len);
 }
 
 bool
@@ -403,7 +403,7 @@ gu_string_hasher_hash(GuHasher* self, const void* p)
 {
 	(void) self;
 	const GuString* sp = p;
-	return gu_string_hash(*sp);
+	return gu_string_hash(0, *sp);
 }
 
 static bool
diff --git a/src/runtime/c/gu/string.h b/src/runtime/c/gu/string.h
index 37cb56ac2..a8376d335 100644
--- a/src/runtime/c/gu/string.h
+++ b/src/runtime/c/gu/string.h
@@ -78,8 +78,8 @@ gu_string_is_prefix(GuString s1, GuString s2);
 #if defined(GU_HASH_H_) && !defined(GU_STRING_H_HASH_)
 #define GU_STRING_H_HASH_
 
-uintptr_t
-gu_string_hash(GuString s);
+GuHash
+gu_string_hash(GuHash h, GuString s);
 
 extern GuHasher gu_string_hasher[1];
 
diff --git a/src/runtime/c/pgf/expr.c b/src/runtime/c/pgf/expr.c
index bcbfa0d09..1394f7a91 100644
--- a/src/runtime/c/pgf/expr.c
+++ b/src/runtime/c/pgf/expr.c
@@ -830,6 +830,86 @@ pgf_expr_eq(PgfExpr e1, PgfExpr e2)
 	return false;
 }
 
+GuHash
+pgf_literal_hash(GuHash h, PgfLiteral lit)
+{
+	GuVariantInfo i = gu_variant_open(lit);
+
+	switch (i.tag) {
+	case PGF_LITERAL_STR: {
+		PgfLiteralStr* lit = i.data;
+        h = gu_string_hash(h, lit->val);
+        break;
+    }
+	case PGF_LITERAL_INT: {
+		PgfLiteralInt* lit = i.data;
+		h = gu_hash_byte(h, lit->val);
+		break;
+	}
+	case PGF_LITERAL_FLT: {
+		PgfLiteralFlt* lit = i.data;
+		h = gu_hash_byte(h, lit->val);
+		break;
+	}
+	default:
+		gu_impossible();
+	}
+
+	return h;
+}
+
+GuHash
+pgf_expr_hash(GuHash h, PgfExpr e)
+{
+	GuVariantInfo ei = gu_variant_open(e);
+	switch (ei.tag) {
+	case PGF_EXPR_ABS: {
+		PgfExprAbs* abs = ei.data;
+		h = gu_string_hash(h, abs->id);
+		h = pgf_expr_hash(h, abs->body);
+		break;
+	}
+	case PGF_EXPR_APP: {
+		PgfExprApp* app = ei.data;
+		h = pgf_expr_hash(h, app->fun);
+		h = pgf_expr_hash(h, app->arg);
+		break;
+	}
+	case PGF_EXPR_LIT: {
+		PgfExprLit* lit = ei.data;
+        h = pgf_literal_hash(h, lit->lit);
+		break;
+	}
+	case PGF_EXPR_META:
+		h = gu_hash_byte(h, '?');
+		break;
+	case PGF_EXPR_FUN: {
+		PgfExprFun* fun = ei.data;
+		h = gu_string_hash(h, fun->fun);
+		break;
+	}
+	case PGF_EXPR_VAR: {
+		PgfExprVar* evar = ei.data;
+		
+		h = gu_hash_byte(h, evar->var);
+		break;
+	}
+	case PGF_EXPR_TYPED: {
+		PgfExprTyped* typed = ei.data;
+		h = pgf_expr_hash(h, typed->expr);
+		break;
+	}
+	case PGF_EXPR_IMPL_ARG: {
+		PgfExprImplArg* impl = ei.data;
+		h = pgf_expr_hash(h, impl->expr);
+		break;
+	}
+	default:
+		gu_impossible();
+	}
+	return h;
+}
+
 void
 pgf_print_literal(PgfLiteral lit,
 			  GuWriter* wtr, GuExn* err)
diff --git a/src/runtime/c/pgf/expr.h b/src/runtime/c/pgf/expr.h
index 3d07ce863..bcfaee52c 100644
--- a/src/runtime/c/pgf/expr.h
+++ b/src/runtime/c/pgf/expr.h
@@ -166,6 +166,12 @@ pgf_expr_eq(PgfExpr e1, PgfExpr e2);
 bool
 pgf_type_eq(PgfType* t1, PgfType* t2);
 
+GuHash
+pgf_literal_hash(GuHash h, PgfLiteral lit);
+
+GuHash
+pgf_expr_hash(GuHash h, PgfExpr e);
+
 typedef struct PgfPrintContext PgfPrintContext;
 
 struct PgfPrintContext {