From c567868e1db3b01fe90b0dcecf7916f1cf5c9c0f Mon Sep 17 00:00:00 2001
From: Mart Lubbers <mart@martlubbers.net>
Date: Wed, 3 Mar 2021 09:57:30 +0100
Subject: [PATCH] reduce allocs from 2m to 700k

---
 Makefile                 |  4 +-
 ast.c                    | 44 +++++++++----------
 ast.h                    |  1 +
 ident.c                  | 82 ++++++++++++++++++++++++++++++++++++
 ident.h                  | 29 +++++++++++++
 list.c                   |  4 +-
 parse.y                  |  2 +-
 sem.c                    | 47 +++++++++++----------
 sem/hm.c                 | 16 +++----
 sem/hm.h                 |  3 +-
 sem/hm/gamma.c           | 28 ++++++-------
 sem/hm/gamma.h           |  7 ++--
 sem/hm/scheme.c          | 16 +++----
 sem/hm/scheme.h          |  3 +-
 sem/hm/subst.c           | 91 ++++++++++++++++++++++++++++------------
 sem/hm/subst.h           |  8 ++--
 sem/scc.c                | 11 +++--
 splc.c                   |  2 +-
 test/test_sem_hm_gamma.c |  2 +-
 type.c                   | 55 ++++++++++++++----------
 type.h                   | 11 +++--
 util.c                   |  2 +-
 util.h                   |  2 +
 23 files changed, 321 insertions(+), 149 deletions(-)
 create mode 100644 ident.c
 create mode 100644 ident.h

diff --git a/Makefile b/Makefile
index db8b684..be0b724 100644
--- a/Makefile
+++ b/Makefile
@@ -1,8 +1,8 @@
-CFLAGS+=-Wall -Wextra -std=c99 -pedantic -ggdb
+CFLAGS+=-Wall -Wextra -Werror -std=c99 -pedantic -ggdb
 YFLAGS+=-d --locations -v --defines=parse.h
 LFLAGS+=--header-file=scan.h
 
-OBJECTS:=scan.o parse.o ast.o type.o util.o list.o sem.o genc.o \
+OBJECTS:=scan.o parse.o ast.o type.o util.o list.o sem.o genc.o ident.o\
 	$(addprefix sem,.o /scc.o $(addprefix /hm, .o /gamma.o /subst.o /scheme.o))
 
 all: splc
diff --git a/ast.c b/ast.c
index e4c45a3..762a130 100644
--- a/ast.c
+++ b/ast.c
@@ -20,7 +20,7 @@ const char *unop_str[] = { [inverse] = "!", [negate] = "-", };
 
 struct ast *ast(struct list *decls, YYLTYPE l)
 {
-	struct ast *res = safe_malloc(sizeof(struct ast));
+	struct ast *res = xalloc(1, struct ast);
 	res->loc = l;
 	res->decls = (struct decl **)list_to_array(decls, &res->ndecls, true, 0);
 	return res;
@@ -28,7 +28,7 @@ struct ast *ast(struct list *decls, YYLTYPE l)
 
 struct vardecl *vardecl(struct type *type, char *ident, struct expr *expr, YYLTYPE l)
 {
-	struct vardecl *res = safe_malloc(sizeof(struct vardecl));
+	struct vardecl *res = xalloc(1, struct vardecl);
 	res->loc = l;
 	res->type = type;
 	res->ident = ident;
@@ -38,7 +38,7 @@ struct vardecl *vardecl(struct type *type, char *ident, struct expr *expr, YYLTY
 struct fundecl *fundecl(char *ident, struct list *args, struct list *atypes,
 	struct type *rtype, struct list *body, YYLTYPE l)
 {
-	struct fundecl *res = safe_malloc(sizeof(struct fundecl));
+	struct fundecl *res = xalloc(1, struct fundecl);
 	res->loc = l;
 	res->ident = ident;
 	res->args = (char **)list_to_array(args, &res->nargs, true, 0);
@@ -51,7 +51,7 @@ struct fundecl *fundecl(char *ident, struct list *args, struct list *atypes,
 
 struct decl *decl_fun(struct fundecl *fundecl, YYLTYPE l)
 {
-	struct decl *res = safe_malloc(sizeof(struct decl));
+	struct decl *res = xalloc(1, struct decl);
 	res->loc = l;
 	res->loc = l;
 	res->type = dfundecl;
@@ -61,7 +61,7 @@ struct decl *decl_fun(struct fundecl *fundecl, YYLTYPE l)
 
 struct decl *decl_var(struct vardecl *vardecl, YYLTYPE l)
 {
-	struct decl *res = safe_malloc(sizeof(struct decl));
+	struct decl *res = xalloc(1, struct decl);
 	res->loc = l;
 	res->loc = l;
 	res->type = dvardecl;
@@ -71,7 +71,7 @@ struct decl *decl_var(struct vardecl *vardecl, YYLTYPE l)
 
 struct stmt *stmt_assign(char *ident, struct list *fields, struct expr *expr, YYLTYPE l)
 {
-	struct stmt *res = safe_malloc(sizeof(struct stmt));
+	struct stmt *res = xalloc(1, struct stmt);
 	res->loc = l;
 	res->type = sassign;
 	res->data.sassign.ident = ident;
@@ -83,7 +83,7 @@ struct stmt *stmt_assign(char *ident, struct list *fields, struct expr *expr, YY
 
 struct stmt *stmt_if(struct expr *pred, struct list *then, struct list *els, YYLTYPE l)
 {
-	struct stmt *res = safe_malloc(sizeof(struct stmt));
+	struct stmt *res = xalloc(1, struct stmt);
 	res->loc = l;
 	res->type = sif;
 	res->data.sif.pred = pred;
@@ -96,7 +96,7 @@ struct stmt *stmt_if(struct expr *pred, struct list *then, struct list *els, YYL
 
 struct stmt *stmt_return(struct expr *rtrn, YYLTYPE l)
 {
-	struct stmt *res = safe_malloc(sizeof(struct stmt));
+	struct stmt *res = xalloc(1, struct stmt);
 	res->loc = l;
 	res->type = sreturn;
 	res->data.sreturn = rtrn;
@@ -105,7 +105,7 @@ struct stmt *stmt_return(struct expr *rtrn, YYLTYPE l)
 
 struct stmt *stmt_expr(struct expr *expr, YYLTYPE l)
 {
-	struct stmt *res = safe_malloc(sizeof(struct stmt));
+	struct stmt *res = xalloc(1, struct stmt);
 	res->loc = l;
 	res->type = sexpr;
 	res->data.sexpr = expr;
@@ -114,7 +114,7 @@ struct stmt *stmt_expr(struct expr *expr, YYLTYPE l)
 
 struct stmt *stmt_vardecl(struct vardecl *vardecl, YYLTYPE l)
 {
-	struct stmt *res = safe_malloc(sizeof(struct stmt));
+	struct stmt *res = xalloc(1, struct stmt);
 	res->loc = l;
 	res->type = svardecl;
 	res->data.svardecl = vardecl;
@@ -123,7 +123,7 @@ struct stmt *stmt_vardecl(struct vardecl *vardecl, YYLTYPE l)
 
 struct stmt *stmt_while(struct expr *pred, struct list *body, YYLTYPE l)
 {
-	struct stmt *res = safe_malloc(sizeof(struct stmt));
+	struct stmt *res = xalloc(1, struct stmt);
 	res->loc = l;
 	res->type = swhile;
 	res->data.swhile.pred = pred;
@@ -134,7 +134,7 @@ struct stmt *stmt_while(struct expr *pred, struct list *body, YYLTYPE l)
 
 struct expr *expr_binop(struct expr *left, enum binop op, struct expr *right, YYLTYPE l)
 {
-	struct expr *res = safe_malloc(sizeof(struct expr));
+	struct expr *res = xalloc(1, struct expr);
 	res->loc = l;
 	res->type = ebinop;
 	res->data.ebinop.l = left;
@@ -145,7 +145,7 @@ struct expr *expr_binop(struct expr *left, enum binop op, struct expr *right, YY
 
 struct expr *expr_bool(bool b, YYLTYPE l)
 {
-	struct expr *res = safe_malloc(sizeof(struct expr));
+	struct expr *res = xalloc(1, struct expr);
 	res->loc = l;
 	res->type = ebool;
 	res->data.ebool = b;
@@ -154,7 +154,7 @@ struct expr *expr_bool(bool b, YYLTYPE l)
 
 struct expr *expr_char(char *c, YYLTYPE l)
 {
-	struct expr *res = safe_malloc(sizeof(struct expr));
+	struct expr *res = xalloc(1, struct expr);
 	res->loc = l;
 	res->type = echar;
 	res->data.echar = unescape_char(c)[0];
@@ -183,7 +183,7 @@ bool is_builtin(char *t)
 
 struct expr *expr_funcall_real(char *ident, struct list *args, YYLTYPE l)
 {
-	struct expr *res = safe_malloc(sizeof(struct expr));
+	struct expr *res = xalloc(1, struct expr);
 	res->loc = l;
 	res->type = efuncall;
 	res->data.efuncall.ident = ident;
@@ -213,7 +213,7 @@ struct expr *expr_funcall(char *ident, struct list *args, struct list *fields, Y
 
 struct expr *expr_int(int integer, YYLTYPE l)
 {
-	struct expr *res = safe_malloc(sizeof(struct expr));
+	struct expr *res = xalloc(1, struct expr);
 	res->loc = l;
 	res->type = eint;
 	res->data.eint = integer;
@@ -222,7 +222,7 @@ struct expr *expr_int(int integer, YYLTYPE l)
 
 struct expr *expr_ident(char *ident, struct list *fields, YYLTYPE l)
 {
-	struct expr *res = safe_malloc(sizeof(struct expr));
+	struct expr *res = xalloc(1, struct expr);
 	res->loc = l;
 	res->type = eident;
 	res->data.eident = ident;
@@ -232,7 +232,7 @@ struct expr *expr_ident(char *ident, struct list *fields, YYLTYPE l)
 
 struct expr *expr_nil(YYLTYPE l)
 {
-	struct expr *res = safe_malloc(sizeof(struct expr));
+	struct expr *res = xalloc(1, struct expr);
 	res->loc = l;
 	res->type = enil;
 	return res;
@@ -240,7 +240,7 @@ struct expr *expr_nil(YYLTYPE l)
 
 struct expr *expr_tuple(struct expr *left, struct expr *right, YYLTYPE l)
 {
-	struct expr *res = safe_malloc(sizeof(struct expr));
+	struct expr *res = xalloc(1, struct expr);
 	res->loc = l;
 	res->type = etuple;
 	res->data.etuple.left = left;
@@ -250,11 +250,11 @@ struct expr *expr_tuple(struct expr *left, struct expr *right, YYLTYPE l)
 
 struct expr *expr_string(char *str, YYLTYPE l)
 {
-	struct expr *res = safe_malloc(sizeof(struct expr));
+	struct expr *res = xalloc(1, struct expr);
 	res->loc = l;
 	res->type = estring;
 	res->data.estring.nchars = 0;
-	res->data.estring.chars = safe_malloc(strlen(str)+1);
+	res->data.estring.chars = xalloc(strlen(str)+1, char);
 	res->loc = l;
 	char *p = res->data.estring.chars;
 	while(*str != '\0') {
@@ -268,7 +268,7 @@ struct expr *expr_string(char *str, YYLTYPE l)
 
 struct expr *expr_unop(enum unop op, struct expr *e, YYLTYPE l)
 {
-	struct expr *res = safe_malloc(sizeof(struct expr));
+	struct expr *res = xalloc(1, struct expr);
 	res->loc = l;
 	res->type = eunop;
 	res->data.eunop.op = op;
diff --git a/ast.h b/ast.h
index ae5db70..0410d11 100644
--- a/ast.h
+++ b/ast.h
@@ -12,6 +12,7 @@ struct ast;
 extern const char *fieldspec_str[];
 extern const char *binop_str[];
 extern const char *unop_str[];
+
 struct ast {
 	YYLTYPE loc;
 	int ndecls;
diff --git a/ident.c b/ident.c
new file mode 100644
index 0000000..966474a
--- /dev/null
+++ b/ident.c
@@ -0,0 +1,82 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include "util.h"
+#include "ident.h"
+
+struct ident ident_str(char *s)
+{
+	return (struct ident) {.type=istr, .data={.istr=s}};
+}
+
+struct ident ident_int(int i)
+{
+	return (struct ident) {.type=iint, .data={.iint=i}};
+}
+
+int ident_cmp(struct ident l, struct ident r)
+{
+	//int bigger than str
+	if (l.type == iint)
+		return r.type == iint ? l.data.iint - r.data.iint : 1;
+	else
+		return r.type == istr
+			? strcmp(l.data.istr, r.data.istr) : -1;
+}
+
+int ident_cmpv(void *l, void *r)
+{
+	return ident_cmp(*(struct ident *)l, *(struct ident *)r);
+}
+
+int ident_stricmp(char *l, struct ident r)
+{
+	return ident_cmp((struct ident){.type=istr, .data={.istr=l}}, r);
+}
+
+int ident_stricmpv(void *l, void *r)
+{
+	return ident_stricmp((char *)l, *(struct ident *)r);
+}
+
+int ident_istrcmp(struct ident l, char *r)
+{
+	return ident_cmp(l, (struct ident){.type=istr, .data={.istr=r}});
+}
+
+int ident_istrcmpv(void *l, void *r)
+{
+	return ident_istrcmp(*(struct ident *)l, (char *)r);
+}
+
+struct ident ident_dup(struct ident i)
+{
+	if (i.type == istr)
+		i.data.istr = safe_strdup(i.data.istr);
+	return i;
+}
+
+char *ident_tostr(struct ident i)
+{
+	if (i.type == istr)
+		return i.data.istr;
+	char buf[10] = {0};
+	sprintf(buf, "%d", i.data.iint);
+	return safe_strdup(buf);
+}
+
+void ident_print(struct ident i, FILE *out)
+{
+	if (i.type == istr)
+		fprintf(out, "%s", i.data.istr);
+	else
+		fprintf(out, "%d", i.data.iint);
+}
+
+void ident_free(struct ident i)
+{
+	if (i.type == istr)
+		free(i.data.istr);
+	(void)i;
+}
diff --git a/ident.h b/ident.h
new file mode 100644
index 0000000..8c9f0bd
--- /dev/null
+++ b/ident.h
@@ -0,0 +1,29 @@
+#ifndef IDENT_H
+#define IDENT_H
+
+#include <stdio.h>
+
+struct ident {
+	enum {istr, iint} type;
+	union {
+		int iint;
+		char *istr;
+	} data;
+};
+
+struct ident ident_str(char *istr);
+struct ident ident_int(int iint);
+
+int ident_cmp(struct ident, struct ident);
+int ident_cmpv(void *, void *);
+int ident_stricmp(char *, struct ident);
+int ident_stricmpv(void *, void *);
+int ident_istrcmp(struct ident, char *);
+int ident_istrcmpv(void *, void *);
+
+struct ident ident_dup(struct ident);
+char *ident_tostr(struct ident);
+void ident_print(struct ident, FILE *);
+void ident_free(struct ident);
+
+#endif
diff --git a/list.c b/list.c
index a18850b..84de358 100644
--- a/list.c
+++ b/list.c
@@ -17,7 +17,7 @@ struct list *list_append(void *el, struct list *head)
 
 struct list *list_cons(void *el, struct list *tail)
 {
-	struct list *res = safe_malloc(sizeof(struct list));
+	struct list *res = xalloc(1, struct list);
 	res->el = el;
 	res->tail = tail;
 	return res;
@@ -38,7 +38,7 @@ void **list_to_array(struct list *list, int *num, bool reverse, int extra)
 {
 	int i = list_length(list);
 	*num = i;
-	void **ptr = safe_malloc((i+extra)*sizeof(void *));
+	void **ptr = xalloc(i+extra, void *);
 
 	struct list *r = list;
 	while(i > 0) {
diff --git a/parse.y b/parse.y
index 2c4271b..1cdea96 100644
--- a/parse.y
+++ b/parse.y
@@ -92,7 +92,7 @@ type
 	;
 ftype
 	: type
-    | IDENT { $$ = type_var($1); }
+    | IDENT { $$ = type_var_str($1); free($1); }
 	;
 args
 	: /* empty */ { $$ = NULL; }
diff --git a/sem.c b/sem.c
index 6fe9385..5c14642 100644
--- a/sem.c
+++ b/sem.c
@@ -44,7 +44,7 @@ struct vardecl *type_vardecl(struct gamma *gamma, struct vardecl *vardecl)
 	struct subst *s = infer_expr(gamma, vardecl->expr, t);
 
 	vardecl->type = subst_apply_t(s, t);
-	gamma_insert(gamma, vardecl->ident, scheme_create(vardecl->type));
+	gamma_insert(gamma, ident_str(vardecl->ident), scheme_create(vardecl->type));
 
 	subst_free(s);
 
@@ -57,7 +57,7 @@ void type_fundecl(struct gamma *gamma, struct fundecl *decl)
 	struct subst *s1 = infer_fundecl(gamma, decl, f1);
 	f1 = subst_apply_t(s1, f1);
 
-	gamma_insert(gamma, decl->ident, scheme_generalise(gamma, f1));
+	gamma_insert(gamma, ident_str(decl->ident), scheme_generalise(gamma, f1));
 	subst_free(s1);
 	type_free(f1);
 }
@@ -65,14 +65,14 @@ void type_fundecl(struct gamma *gamma, struct fundecl *decl)
 void type_comp(struct gamma *gamma, int ndecls, struct fundecl **decl)
 {
 	//Create a fresh variable for every function in the component
-	struct type **fs = safe_malloc(ndecls*sizeof(struct type *));
+	struct type **fs = xalloc(ndecls, struct type *);
 	for (int i = 0; i<ndecls; i++) {
 		fs[i] = gamma_fresh(gamma);
 		for (int j = 0; j<decl[i]->nargs; j++) {
 			struct type *a = gamma_fresh(gamma);
 			fs[i] = type_arrow(a, fs[i]);
 		}
-		gamma_insert(gamma, decl[i]->ident, scheme_create(fs[i]));
+		gamma_insert(gamma, ident_str(decl[i]->ident), scheme_create(fs[i]));
 	}
 
 	//Infer each function
@@ -100,11 +100,11 @@ void type_comp(struct gamma *gamma, int ndecls, struct fundecl **decl)
 			type_free(dt);
 		}
 
-		gamma_insert(gamma, decl[i]->ident, scheme_generalise(gamma, t));
+		gamma_insert(gamma, ident_str(decl[i]->ident), scheme_generalise(gamma, t));
 
 		//Put the type in the ast
-		decl[i]->atypes = safe_realloc(decl[i]->atypes,
-			decl[i]->nargs*sizeof(struct type *));
+		decl[i]->atypes = xrealloc(decl[i]->atypes,
+			decl[i]->nargs, struct type *);
 		decl[i]->natypes = decl[i]->nargs;
 		for (int j = 0; j<decl[i]->nargs; j++, t = t->data.tarrow.r)
 			decl[i]->atypes[j] = type_dup(t->data.tarrow.l);
@@ -120,33 +120,33 @@ void type_comp(struct gamma *gamma, int ndecls, struct fundecl **decl)
 
 void gamma_preamble(struct gamma *gamma)
 {
-	struct type *t = type_arrow(type_tuple(type_var(safe_strdup("a"))
-		, type_var(safe_strdup("b"))) ,type_var(safe_strdup("a")));
-	gamma_insert(gamma, "fst", scheme_generalise(gamma, t));
+	struct type *t = type_arrow(type_tuple(type_var_str("a")
+		, type_var_str("b")) ,type_var_str("a"));
+	gamma_insert(gamma, ident_str("fst"), scheme_generalise(gamma, t));
 	type_free(t);
 
-	t = type_arrow(type_tuple(type_var(safe_strdup("a"))
-		, type_var(safe_strdup("b"))) ,type_var(safe_strdup("b")));
-	gamma_insert(gamma, "snd", scheme_generalise(gamma, t));
+	t = type_arrow(type_tuple(type_var_str("a")
+		, type_var_str("b")) ,type_var_str("b"));
+	gamma_insert(gamma, ident_str("snd"), scheme_generalise(gamma, t));
 	type_free(t);
 
-	t = type_arrow(type_list(type_var(safe_strdup("a"))),
-			type_var(safe_strdup("a")));
-	gamma_insert(gamma, "hd", scheme_generalise(gamma, t));
+	t = type_arrow(type_list(type_var_str("a")),
+			type_var_str("a"));
+	gamma_insert(gamma, ident_str("hd"), scheme_generalise(gamma, t));
 	type_free(t);
 
-	t = type_arrow(type_list(type_var(safe_strdup("a"))),
-			type_list(type_var(safe_strdup("a"))));
-	gamma_insert(gamma, "tl", scheme_generalise(gamma, t));
+	t = type_arrow(type_list(type_var_str("a")),
+			type_list(type_var_str("a")));
+	gamma_insert(gamma, ident_str("tl"), scheme_generalise(gamma, t));
 	type_free(t);
 
-	t = type_arrow(type_list(type_var(safe_strdup("a"))),
+	t = type_arrow(type_list(type_var_str("a")),
 			type_basic(btbool));
-	gamma_insert(gamma, "isEmpty", scheme_generalise(gamma, t));
+	gamma_insert(gamma, ident_str("isEmpty"), scheme_generalise(gamma, t));
 	type_free(t);
 
-	t = type_arrow(type_var(safe_strdup("a")), type_basic(btvoid));
-	gamma_insert(gamma, "print", scheme_generalise(gamma, t));
+	t = type_arrow(type_var_str("a"), type_basic(btvoid));
+	gamma_insert(gamma, ident_str("print"), scheme_generalise(gamma, t));
 	type_free(t);
 }
 
@@ -238,6 +238,7 @@ struct ast *sem(struct ast *ast)
 		}
 	}
 	gamma_free(gamma);
+	subst_free_queue();
 
 	return ast;
 }
diff --git a/sem/hm.c b/sem/hm.c
index d81902a..75587e6 100644
--- a/sem/hm.c
+++ b/sem/hm.c
@@ -8,14 +8,14 @@
 #include "../sem.h"
 #include "../ast.h"
 
-bool occurs_check(char *var, struct type *r)
+bool occurs_check(struct ident ident, struct type *r)
 {
 	int nftv = 0;
-	char **ftv = NULL;
+	struct ident *ftv = NULL;
 	bool res = false;
 	type_ftv(r, &nftv, &ftv);
 	for (int i = 0; i<nftv; i++) {
-		if (strcmp(ftv[i], var) == 0) {
+		if (ident_cmp(ftv[i], ident) == 0) {
 			res = true;
 			break;
 		}
@@ -47,7 +47,7 @@ struct subst *unify(YYLTYPE loc, struct type *l, struct type *r)
 			subst_apply_t(s1, r->data.ttuple.r));
 		return subst_union(s2, s1);
 	} else if (l->type == tvar) {
-		if (r->type == tvar && strcmp(l->data.tvar, r->data.tvar) == 0)
+		if (r->type == tvar && ident_cmp(l->data.tvar, r->data.tvar) == 0)
 			return subst_id();
 		else if (occurs_check(l->data.tvar, r))
 			type_error(loc, true, "Infinite type %s\n",
@@ -131,7 +131,7 @@ struct subst *infer_expr(struct gamma *gamma, struct expr *expr, struct type *ty
 	case echar:
 		return unify(expr->loc, &tychar, type);
 	case efuncall:
-		if ((s = gamma_lookup(gamma, expr->data.efuncall.ident)) == NULL)
+		if ((s = gamma_lookup(gamma, ident_str(expr->data.efuncall.ident))) == NULL)
 			type_error(expr->loc, true, "Unbound function: %s\n"
 				, expr->data.efuncall.ident);
 		struct type *ft = scheme_instantiate(gamma, s);
@@ -161,7 +161,7 @@ struct subst *infer_expr(struct gamma *gamma, struct expr *expr, struct type *ty
 	case eint:
 		return unify(expr->loc, &tyint, type);
 	case eident:
-		if ((s = gamma_lookup(gamma, expr->data.eident)) == NULL)
+		if ((s = gamma_lookup(gamma, ident_str(expr->data.eident))) == NULL)
 			type_error(expr->loc, true, "Unbound variable: %s\n"
 				, expr->data.eident);
 		f1 = scheme_instantiate(gamma, s);
@@ -245,7 +245,7 @@ struct subst *infer_stmt(struct gamma *gamma, struct stmt *stmt, struct type *ty
 		s0 = subst_union(s1, s0);
 		//TODO fielsd
 		//TODO
-		gamma_insert(gamma, stmt->data.svardecl->ident,
+		gamma_insert(gamma, ident_str(stmt->data.svardecl->ident),
 			scheme_create(subst_apply_t(s0, f1)));
 		type_free(f1);
 		return s0;
@@ -269,7 +269,7 @@ struct subst *infer_fundecl(struct gamma *gamma, struct fundecl *fundecl, struct
 	for (int i = 0; i<fundecl->nargs; i++) {
 		if (at->type != tarrow)
 			die("malformed ftype\n");
-		gamma_insert(gamma, fundecl->args[i],
+		gamma_insert(gamma, ident_str(fundecl->args[i]),
 			scheme_create(at->data.tarrow.l));
 		at = at->data.tarrow.r;
 	}
diff --git a/sem/hm.h b/sem/hm.h
index 932e508..d035e4c 100644
--- a/sem/hm.h
+++ b/sem/hm.h
@@ -5,10 +5,11 @@
 #include "hm/gamma.h"
 #include "hm/subst.h"
 #include "hm/scheme.h"
+#include "../ident.h"
 
 struct ast *infer(struct ast *ast);
 
-bool occurs_check(char *var, struct type *r);
+bool occurs_check(struct ident ident, struct type *r);
 struct subst *unify(YYLTYPE loc, struct type *l, struct type *r);
 struct subst *infer_expr(struct gamma *gamma, struct expr *expr, struct type *type);
 struct subst *infer_stmt(struct gamma *gamma, struct stmt *stmt, struct type *type);
diff --git a/sem/hm/gamma.c b/sem/hm/gamma.c
index 93de4ec..f6e66ad 100644
--- a/sem/hm/gamma.c
+++ b/sem/hm/gamma.c
@@ -7,19 +7,19 @@
 
 struct gamma *gamma_init()
 {
-	struct gamma *gamma = safe_malloc(sizeof(struct gamma));
+	struct gamma *gamma = xalloc(1, struct gamma);
 	gamma->capacity = IN_CAP;
 	gamma->fresh = 0;
 	gamma->nentries = 0;
 	gamma->scope = 0;
-	gamma->entries = safe_malloc(IN_CAP*sizeof(struct gamma_entry));
+	gamma->entries = xalloc(IN_CAP, struct gamma_entry);
 	return gamma;
 }
 
-void gamma_insert(struct gamma *gamma, char *ident, struct scheme *scheme)
+void gamma_insert(struct gamma *gamma, struct ident ident, struct scheme *scheme)
 {
 	for (int i = 0; i<gamma->nentries; i++) {
-		if(strcmp(gamma->entries[i].var, ident) == 0
+		if(ident_cmp(gamma->entries[i].var, ident) == 0
 				&& gamma->entries[i].scope == gamma->scope) {
 			scheme_free(gamma->entries[i].scheme);
 			gamma->entries[i].scheme = scheme;
@@ -29,11 +29,11 @@ void gamma_insert(struct gamma *gamma, char *ident, struct scheme *scheme)
 	gamma->nentries++;
 	if (gamma->nentries >= gamma->capacity) {
 		gamma->capacity += gamma->capacity;
-		gamma->entries = safe_realloc(gamma->entries,
-			gamma->capacity*sizeof(struct gamma_entry));
+		gamma->entries = xrealloc(gamma->entries,
+			gamma->capacity, struct gamma_entry);
 	}
 	gamma->entries[gamma->nentries-1].scope = gamma->scope;
-	gamma->entries[gamma->nentries-1].var = safe_strdup(ident);
+	gamma->entries[gamma->nentries-1].var = ident_dup(ident);
 	gamma->entries[gamma->nentries-1].scheme = scheme;
 }
 
@@ -51,7 +51,7 @@ void gamma_decrement_scope(struct gamma *gamma)
 	while (i<gamma->nentries) {
 		if (gamma->entries[i].scope == gamma->scope) {
 			scheme_free(gamma->entries[i].scheme);
-			free(gamma->entries[i].var);
+			ident_free(gamma->entries[i].var);
 			for (int j = i+1; j<gamma->nentries; j++)
 				gamma->entries[j-1] = gamma->entries[j];
 			gamma->nentries--;
@@ -62,12 +62,12 @@ void gamma_decrement_scope(struct gamma *gamma)
 	gamma->scope--;
 }
 
-struct scheme *gamma_lookup(struct gamma *gamma, char *ident)
+struct scheme *gamma_lookup(struct gamma *gamma, struct ident ident)
 {
 	struct scheme *res = NULL;
 	int maxscope = 0;
 	for (int i = 0; i<gamma->nentries; i++) {
-		if (strcmp(ident, gamma->entries[i].var) == 0) {
+		if (ident_cmp(ident, gamma->entries[i].var) == 0) {
 			if (gamma->entries[i].scope >= maxscope) {
 				maxscope = gamma->entries[i].scope;
 				res = gamma->entries[i].scheme;
@@ -81,15 +81,15 @@ struct type *gamma_fresh(struct gamma *gamma)
 {
 	char buf[10] = {0};
 	sprintf(buf, "%d", gamma->fresh++);
-	return type_var(safe_strdup(buf));
+	return type_var_int(gamma->fresh++);
 }
 
 void gamma_print(struct gamma *gamma, FILE *out)
 {
 	fprintf(out, "{");
 	for (int i = 0; i<gamma->nentries; i++) {
-		fprintf(out, "%s(%d) = ", gamma->entries[i].var,
-			gamma->entries[i].scope);
+		ident_print(gamma->entries[i].var, out);
+		fprintf(out, "(%d) = ", gamma->entries[i].scope);
 		scheme_print(gamma->entries[i].scheme, out);
 		if (i + 1 < gamma->nentries)
 			fprintf(out, ", ");
@@ -100,7 +100,7 @@ void gamma_print(struct gamma *gamma, FILE *out)
 void gamma_free(struct gamma *gamma)
 {
 	for (int i = 0; i<gamma->nentries; i++) {
-		free(gamma->entries[i].var);
+		ident_free(gamma->entries[i].var);
 		scheme_free(gamma->entries[i].scheme);
 	}
 	free(gamma->entries);
diff --git a/sem/hm/gamma.h b/sem/hm/gamma.h
index 9641dcc..b5f52a1 100644
--- a/sem/hm/gamma.h
+++ b/sem/hm/gamma.h
@@ -4,6 +4,7 @@
 #include <stdlib.h>
 
 #include "../hm.h"
+#include "../../ident.h"
 
 struct gamma {
 	int capacity;
@@ -12,17 +13,17 @@ struct gamma {
 	int nentries;
 	struct gamma_entry {
 		int scope;
-		char *var;
+		struct ident var;
 		struct scheme *scheme;
 	} *entries;
 };
 
 struct gamma *gamma_init();
-void gamma_insert(struct gamma *gamma, char *ident, struct scheme *scheme);
+void gamma_insert(struct gamma *gamma, struct ident ident, struct scheme *scheme);
 void gamma_increment_scope(struct gamma *gamma);
 void gamma_decrement_scope(struct gamma *gamma);
 
-struct scheme *gamma_lookup(struct gamma *gamma, char *ident);
+struct scheme *gamma_lookup(struct gamma *gamma, struct ident ident);
 struct type *gamma_fresh(struct gamma *gamma);
 
 void gamma_print(struct gamma *gamma, FILE *out);
diff --git a/sem/hm/scheme.c b/sem/hm/scheme.c
index 5715837..7769649 100644
--- a/sem/hm/scheme.c
+++ b/sem/hm/scheme.c
@@ -20,7 +20,7 @@ struct type *scheme_instantiate(struct gamma *gamma, struct scheme *sch)
 
 struct scheme *scheme_create(struct type *t)
 {
-	struct scheme *s = safe_malloc(sizeof(struct scheme));
+	struct scheme *s = xalloc(1, struct scheme);
 	s->type = type_dup(t);
 	s->nvar = 0;
 	s->var = NULL;
@@ -29,23 +29,23 @@ struct scheme *scheme_create(struct type *t)
 
 struct scheme *scheme_generalise(struct gamma *gamma, struct type *t)
 {
-	struct scheme *s = safe_malloc(sizeof(struct scheme));
+	struct scheme *s = xalloc(1, struct scheme);
 	int nftv = 0;
-	char **ftv = NULL;
+	struct ident *ftv = NULL;
 	type_ftv(t, &nftv, &ftv);
 
 	s->type = type_dup(t);
 	s->nvar = 0;
-	s->var = safe_malloc(nftv*sizeof(char *));
+	s->var = xalloc(nftv, struct ident);
 	for (int i = 0; i<nftv; i++) {
 		bool skip = false;
 		for (int j = 0; j<gamma->nentries; j++)
-			if (strcmp(gamma->entries[j].var, ftv[i]) == 0)
+			if (ident_cmp(gamma->entries[j].var, ftv[i]) == 0)
 				skip = true;
 		if (skip)
 			continue;
 		s->nvar++;
-		s->var[i] = safe_strdup(ftv[i]);
+		s->var[i] = ident_dup(ftv[i]);
 	}
 	free(ftv);
 	return s;
@@ -62,7 +62,7 @@ void scheme_print(struct scheme *scheme, FILE *out)
 		for (int i = 0; i<scheme->nvar; i++) {
 			if (i > 0)
 				fprintf(out, " ");
-			fprintf(out, "%s", scheme->var[i]);
+			ident_print(scheme->var[i], stderr);
 		}
 		fprintf(out, ": ");
 	}
@@ -73,7 +73,7 @@ void scheme_free(struct scheme *scheme)
 {
 	type_free(scheme->type);
 	for (int i = 0; i<scheme->nvar; i++)
-		free(scheme->var[i]);
+		ident_free(scheme->var[i]);
 	free(scheme->var);
 	free(scheme);
 }
diff --git a/sem/hm/scheme.h b/sem/hm/scheme.h
index eaab3fc..2228328 100644
--- a/sem/hm/scheme.h
+++ b/sem/hm/scheme.h
@@ -2,11 +2,12 @@
 #define SEM_HM_SCHEME_H
 
 #include "../hm.h"
+#include "../../ident.h"
 
 struct scheme {
 	struct type *type;
 	int nvar;
-	char **var;
+	struct ident *var;
 };
 
 struct type *scheme_instantiate(struct gamma *gamma, struct scheme *s);
diff --git a/sem/hm/subst.c b/sem/hm/subst.c
index 6725fc7..81c13c7 100644
--- a/sem/hm/subst.c
+++ b/sem/hm/subst.c
@@ -1,28 +1,44 @@
 #include <string.h>
 #include <stdlib.h>
 
-#include <search.h>
-
 #include "../hm.h"
+#include "../../list.h"
 
 #define INCAP 50
 
+#define KEEP_LIST
+
+#ifdef KEEP_LIST
+#define BUFCAP 100
+struct subst *buf[BUFCAP] = {NULL};
+int bufi = 0;
+#endif
+
 struct subst *subst_id()
 {
-	struct subst *res = safe_malloc(sizeof(struct subst));
-	res->capacity = INCAP;
-	res->nvar = 0;
-	res->entries = safe_malloc(INCAP*sizeof(struct subst_entry));
+	struct subst *res;
+
+#ifdef KEEP_LIST
+	if (bufi == 0 || bufi >= BUFCAP) {
+#endif
+		res = xalloc(1, struct subst);
+		res->capacity = INCAP;
+		res->nvar = 0;
+		res->entries = xalloc(INCAP, struct subst_entry);
+#ifdef KEEP_LIST
+	} else {
+		res = buf[--bufi];
+		res->nvar = 0;
+	}
+#endif
 	return res;
 }
 
-struct subst *subst_insert(struct subst *s, char *ident, struct type *t)
+struct subst *subst_insert(struct subst *s, struct ident ident, struct type *t)
 {
 	int i = 0;
 	while (i < s->nvar) {
-		if (strcmp(s->entries[i].var, ident) == 0) {
-	//		free(s->entries[i].var);
-	//		s->entries[i].var = safe_strdup(ident);
+		if (ident_cmp(s->entries[i].var, ident) == 0) {
 			type_free(s->entries[i].type);
 			s->entries[i].type = type_dup(t);
 			return s;
@@ -31,16 +47,16 @@ struct subst *subst_insert(struct subst *s, char *ident, struct type *t)
 	}
 	if (s->nvar >= s->capacity) {
 		s->capacity += s->capacity;
-		s->entries = safe_realloc(s->entries,
-			s->capacity*sizeof(struct subst_entry));
+		s->entries = xrealloc(s->entries,
+			s->capacity, struct subst_entry);
 	}
 	s->nvar++;
-	s->entries[i].var = safe_strdup(ident);
+	s->entries[i].var = ident_dup(ident);
 	s->entries[i].type = type_dup(t);
 	return s;
 }
 
-struct subst *subst_singleton(char *ident, struct type *t)
+struct subst *subst_singleton(struct ident ident, struct type *t)
 {
 	return subst_insert(subst_id(), ident, t);
 }
@@ -77,8 +93,8 @@ struct type *subst_apply_t(struct subst *subst, struct type *l)
 		break;
 	case tvar:
 		for (int i = 0; i<subst->nvar; i++) {
-			if (strcmp(subst->entries[i].var, l->data.tvar) == 0) {
-				free(l->data.tvar);
+			if (ident_cmp(subst->entries[i].var, l->data.tvar) == 0) {
+				ident_free(l->data.tvar);
 				struct type *r =
 					type_dup(subst->entries[i].type);
 				*l = *r;
@@ -97,11 +113,9 @@ struct scheme *subst_apply_s(struct subst *subst, struct scheme *scheme)
 	struct subst *s = subst_id();
 	for (int j = 0; j<subst->nvar; j++) {
 		bool found = false;
-		for (int i = 0; i<scheme->nvar; i++) {
-			if (strcmp(scheme->var[i], subst->entries[j].var) == 0) {
+		for (int i = 0; i<scheme->nvar; i++)
+			if (ident_cmp(scheme->var[i], subst->entries[j].var) == 0)
 				found = true;
-			}
-		}
 		if (!found)
 			subst_insert(s, subst->entries[j].var,
 				subst->entries[j].type);
@@ -125,7 +139,8 @@ void subst_print(struct subst *s, FILE *out)
 	} else {
 		fprintf(out, "[");
 		for (int i = 0; i<s->nvar; i++) {
-			fprintf(out, "%s->", s->entries[i].var);
+			ident_print(s->entries[i].var, out);
+			fprintf(out, "->");
 			type_print(s->entries[i].type, out);
 			if (i + 1 < s->nvar)
 				fprintf(out, ", ");
@@ -134,14 +149,38 @@ void subst_print(struct subst *s, FILE *out)
 	}
 }
 
-void subst_free(struct subst *s)
+static void subst_really_free(void *sp)
 {
+	struct subst *s = (struct subst *)sp;
 	if (s != NULL) {
-		for (int i = 0; i<s->nvar; i++) {
-			free(s->entries[i].var);
-			type_free(s->entries[i].type);
-		}
 		free(s->entries);
 		free(s);
 	}
 }
+
+void subst_free(struct subst *s)
+{
+	for (int i = 0; i<s->nvar; i++) {
+		ident_free(s->entries[i].var);
+		type_free(s->entries[i].type);
+	}
+#ifdef KEEP_LIST
+	if (bufi < BUFCAP) {
+		buf[bufi++] = s;
+	} else {
+		subst_really_free(s);
+	}
+#else
+	subst_really_free(s);
+#endif
+}
+
+void subst_free_queue()
+{
+#ifdef KEEP_LIST
+	while (--bufi >= 0) {
+		free(buf[bufi]->entries);
+		free(buf[bufi]);
+	}
+#endif
+}
diff --git a/sem/hm/subst.h b/sem/hm/subst.h
index d3661c2..5df635a 100644
--- a/sem/hm/subst.h
+++ b/sem/hm/subst.h
@@ -3,6 +3,7 @@
 
 #include "../../ast.h"
 #include "../hm.h"
+#include "../../ident.h"
 
 struct subst {
 	int nvar;
@@ -10,13 +11,13 @@ struct subst {
 	struct subst_entry *entries;
 };
 struct subst_entry {
-	char *var;
+	struct ident var;
 	struct type *type;
 };
 
 struct subst *subst_id();
-struct subst *subst_insert(struct subst *s, char *ident, struct type *t);
-struct subst *subst_singleton(char *ident, struct type *t);
+struct subst *subst_insert(struct subst *s, struct ident ident, struct type *t);
+struct subst *subst_singleton(struct ident ident, struct type *t);
 struct subst *subst_union(struct subst *l, struct subst *r);
 
 struct type *subst_apply_t(struct subst *subst, struct type *l);
@@ -25,5 +26,6 @@ struct gamma *subst_apply_g(struct subst *subst, struct gamma *gamma);
 
 void subst_print(struct subst *s, FILE *out);
 void subst_free(struct subst *s);
+void subst_free_queue();
 
 #endif
diff --git a/sem/scc.c b/sem/scc.c
index dd25ee7..48ec497 100644
--- a/sem/scc.c
+++ b/sem/scc.c
@@ -74,7 +74,7 @@ static int strongconnect(struct node *v, struct tjstate *tj)
 
 	/* If v is a root node, pop the stack and generate an SCC */
 	if (v->lowlink == v->index) {
-		struct components *ng = safe_malloc(sizeof(struct components));
+		struct components *ng = xalloc(1, struct components);
 		if (tj->tail == NULL)
 			tj->head = ng;
 		else
@@ -88,7 +88,7 @@ static int strongconnect(struct node *v, struct tjstate *tj)
 			w->onStack = false;
 			ng->nnodes++;
 		} while (w != v);
-		ng->nodes = safe_malloc(ng->nnodes*sizeof(void *));
+		ng->nodes = xalloc(ng->nnodes, void *);
 		for (int i = 0; i<ng->nnodes; i++)
 			ng->nodes[i] = tj->stack[tj->sp+i]->data;
 	}
@@ -175,7 +175,7 @@ struct list *edges_expr(int ndecls, struct decl **decls, void *parent,
 		for (int i = 0; i<ndecls && !found; i++) {
 			if (strcmp(decls[i]->data.dfun->ident,
 					expr->data.efuncall.ident) == 0) {
-				struct edge *edge = safe_malloc(sizeof(struct edge));
+				struct edge *edge = xalloc(1, struct edge);
 				edge->from = parent;
 				edge->to = (void *)decls[i];
 				l = list_cons(edge, l);
@@ -281,11 +281,10 @@ struct ast *ast_scc(struct ast *ast)
 
 	int i = ffun;
 	for (struct components *c = cs; c != NULL; c = c->next) {
-		struct decl *d = safe_malloc(sizeof(struct decl));
+		struct decl *d = xalloc(1, struct decl);
 		d->type = dcomp;
 		d->data.dcomp.ndecls = c->nnodes;
-		d->data.dcomp.decls = safe_malloc(
-			c->nnodes*sizeof(struct fundecl *));
+		d->data.dcomp.decls = xalloc(c->nnodes, struct fundecl *);
 		for (int j = 0; j<c->nnodes; j++)
 			d->data.dcomp.decls[j] =
 				((struct decl *)c->nodes[j])->data.dfun;
diff --git a/splc.c b/splc.c
index 6e5c5ab..cbe3a62 100644
--- a/splc.c
+++ b/splc.c
@@ -86,7 +86,7 @@ int main(int argc, char *argv[])
 
 	//Generate code
 	if (cfile == NULL)
-		sprintf(cfile = safe_malloc(10), "a.%s", suffix[lang]);
+		sprintf(cfile = xalloc(10, char), "a.%s", suffix[lang]);
 	cout = safe_fopen(cfile, "w+");
 	free(cfile);
 	switch(lang) {
diff --git a/test/test_sem_hm_gamma.c b/test/test_sem_hm_gamma.c
index 1665031..4005e38 100644
--- a/test/test_sem_hm_gamma.c
+++ b/test/test_sem_hm_gamma.c
@@ -39,7 +39,7 @@ START_TEST(test_scheme)
 
 	char **var = malloc(sizeof(char *));
 	var[0] = safe_strdup("a");
-	struct scheme scheme = {.type=type_var("a"), .nvar=1, .var=var};
+	struct scheme scheme = {.type=type_var_str("a"), .nvar=1, .var=var};
 
 	struct type *t = scheme_instantiate(gamma, &scheme);
 	ck_assert(t->type == tvar);
diff --git a/type.c b/type.c
index 18c8151..51e5bef 100644
--- a/type.c
+++ b/type.c
@@ -3,6 +3,7 @@
 
 #include "util.h"
 #include "type.h"
+#include "ident.h"
 
 static const char *basictype_str[] = {
 	[btbool] = "Bool", [btchar] = "Char", [btint] = "Int",
@@ -11,7 +12,7 @@ static const char *basictype_str[] = {
 
 struct type *type_arrow(struct type *l, struct type *r)
 {
-	struct type *res = safe_malloc(sizeof(struct type));
+	struct type *res = xalloc(1, struct type);
 	res->type = tarrow;
 	res->data.tarrow.l = l;
 	res->data.tarrow.r = r;
@@ -20,7 +21,7 @@ struct type *type_arrow(struct type *l, struct type *r)
 
 struct type *type_basic(enum basictype type)
 {
-	struct type *res = safe_malloc(sizeof(struct type));
+	struct type *res = xalloc(1, struct type);
 	res->type = tbasic;
 	res->data.tbasic = type;
 	return res;
@@ -28,7 +29,7 @@ struct type *type_basic(enum basictype type)
 
 struct type *type_list(struct type *type)
 {
-	struct type *res = safe_malloc(sizeof(struct type));
+	struct type *res = xalloc(1, struct type);
 	res->type = tlist;
 	res->data.tlist = type;
 	return res;
@@ -36,35 +37,45 @@ struct type *type_list(struct type *type)
 
 struct type *type_tuple(struct type *l, struct type *r)
 {
-	struct type *res = safe_malloc(sizeof(struct type));
+	struct type *res = xalloc(1, struct type);
 	res->type = ttuple;
 	res->data.ttuple.l = l;
 	res->data.ttuple.r = r;
 	return res;
 }
 
-struct type *type_var(char *ident)
+struct type *type_var_str(char *s)
 {
-	struct type *res = safe_malloc(sizeof(struct type));
-	if (strcmp(ident, "Int") == 0) {
+	return type_var((struct ident){.type=istr, .data={.istr=s}});
+}
+
+struct type *type_var_int(int i)
+{
+	return type_var((struct ident){.type=iint, .data={.iint=i}});
+}
+
+struct type *type_var(struct ident ident)
+{
+	struct type *res = xalloc(1, struct type);
+	if (ident_istrcmp(ident, "Int") == 0) {
 		res->type = tbasic;
 		res->data.tbasic = btint;
-		free(ident);
-	} else if (strcmp(ident, "Char") == 0) {
+		ident_free(ident);
+	} else if (ident_istrcmp(ident, "Char") == 0) {
 		res->type = tbasic;
 		res->data.tbasic = btchar;
-		free(ident);
-	} else if (strcmp(ident, "Bool") == 0) {
+		ident_free(ident);
+	} else if (ident_istrcmp(ident, "Bool") == 0) {
 		res->type = tbasic;
 		res->data.tbasic = btbool;
-		free(ident);
-	} else if (strcmp(ident, "Void") == 0) {
+		ident_free(ident);
+	} else if (ident_istrcmp(ident, "Void") == 0) {
 		res->type = tbasic;
 		res->data.tbasic = btvoid;
-		free(ident);
+		ident_free(ident);
 	} else {
 		res->type = tvar;
-		res->data.tvar = ident;
+		res->data.tvar = ident_dup(ident);
 	}
 	return res;
 }
@@ -97,7 +108,7 @@ void type_print(struct type *type, FILE *out)
 		safe_fprintf(out, ")");
 		break;
 	case tvar:
-		safe_fprintf(out, "%s", type->data.tvar);
+		ident_print(type->data.tvar, out);
 		break;
 	default:
 		die("Unsupported type node: %d\n", type->type);
@@ -123,7 +134,7 @@ void type_free(struct type *type)
 		type_free(type->data.ttuple.r);
 		break;
 	case tvar:
-		free(type->data.tvar);
+		ident_free(type->data.tvar);
 		break;
 	default:
 		die("Unsupported type node: %d\n", type->type);
@@ -133,7 +144,7 @@ void type_free(struct type *type)
 
 struct type *type_dup(struct type *r)
 {
-	struct type *res = safe_malloc(sizeof(struct type));
+	struct type *res = xalloc(1, struct type);
 	*res = *r;
 	switch (r->type) {
 	case tarrow:
@@ -150,7 +161,7 @@ struct type *type_dup(struct type *r)
 		res->data.ttuple.r = type_dup(r->data.ttuple.r);
 		break;
 	case tvar:
-		res->data.tvar = safe_strdup(r->data.tvar);
+		res->data.tvar = ident_dup(r->data.tvar);
 		break;
 	default:
 		die("Unsupported type node: %d\n", r->type);
@@ -158,7 +169,7 @@ struct type *type_dup(struct type *r)
 	return res;
 }
 
-void type_ftv(struct type *r, int *nftv, char ***ftv)
+void type_ftv(struct type *r, int *nftv, struct ident **ftv)
 {
 	switch (r->type) {
 	case tarrow:
@@ -176,9 +187,9 @@ void type_ftv(struct type *r, int *nftv, char ***ftv)
 		break;
 	case tvar:
 		for (int i = 0; i<*nftv; i++)
-			if (strcmp((*ftv)[i], r->data.tvar) == 0)
+			if (ident_cmp((*ftv)[i], r->data.tvar) == 0)
 				return;
-		*ftv = safe_realloc(*ftv, (*nftv+1)*sizeof(char *));
+		*ftv = xrealloc(*ftv, *nftv+1, struct ident);
 		(*ftv)[(*nftv)++] = r->data.tvar;
 		break;
 	default:
diff --git a/type.h b/type.h
index 65135aa..f8655d1 100644
--- a/type.h
+++ b/type.h
@@ -3,6 +3,7 @@
 
 #include <stdio.h>
 #include "ast.h"
+#include "ident.h"
 
 enum basictype {btbool, btchar, btint, btvoid};
 struct type {
@@ -18,7 +19,7 @@ struct type {
 			struct type *l;
 			struct type *r;
 		} ttuple;
-		char *tvar;
+		struct ident tvar;
 	} data;
 };
 
@@ -26,12 +27,14 @@ struct type *type_arrow(struct type *left, struct type *right);
 struct type *type_basic(enum basictype type);
 struct type *type_list(struct type *type);
 struct type *type_tuple(struct type *left, struct type *right);
-struct type *type_var(char *ident);
+struct type *type_var(struct ident ident);
+struct type *type_var_str(char *s);
+struct type *type_var_int(int i);
 
-void type_print(struct type *type, FILE *out);
+void type_print(struct type *type, FILE *stream);
 void type_free(struct type *type);
 
 struct type *type_dup(struct type *t);
-void type_ftv(struct type *r, int *nftv, char ***ftv);
+void type_ftv(struct type *r, int *nftv, struct ident **ftv);
 
 #endif
diff --git a/util.c b/util.c
index 1653cad..7f26aa3 100644
--- a/util.c
+++ b/util.c
@@ -19,7 +19,7 @@ int fromHex(char c)
 
 char *escape_char(char c, char *buf, bool str)
 {
-	buf = buf == NULL ? safe_malloc(10) : buf;
+	buf = buf == NULL ? xalloc(10, char) : buf;
 	switch (c) {
 	case '\0': strcpy(buf, "\\0"); break;
 	case '\a': strcpy(buf, "\\a"); break;
diff --git a/util.h b/util.h
index 6704cf4..547bedb 100644
--- a/util.h
+++ b/util.h
@@ -20,7 +20,9 @@ void pindent(int indent, FILE *out);
 
 void safe_fprintf(FILE *out, const char *msg, ...);
 void *safe_malloc(size_t size);
+#define xalloc(nmemb, type) ((type *)safe_malloc((nmemb)*sizeof(type)))
 void *safe_realloc(void *ptr, size_t size);
+#define xrealloc(ptr, nmemb, type) ((type *)safe_realloc(ptr, (nmemb)*sizeof(type)))
 void *safe_strdup(const char *c);
 FILE *safe_fopen(const char *path, const char *mode);
 void safe_fclose(FILE *file);
-- 
2.20.1