improve generics expansion

15 files changed, 810 insertions, 280 deletions

diff --git a/include/ek/ast.h b/include/ek/ast.h
index 2ee9f6f..f6e83cb 100644
--- a/include/ek/ast.h
+++ b/include/ek/ast.h
@@ -194,6 +194,9 @@ enum ast_flags {
 	AST_FLAG_NOMANGLE = (1 << 14),
 	AST_FLAG_DOEXPR = (1 << 15),
 	AST_FLAG_LOWERED = (1 << 16),
+	AST_FLAG_UFCS_SIMPLE = (1 << 17),
+	AST_FLAG_UFCS_REF = (1 << 18),
+	AST_FLAG_UFCS_TRIVIAL = (1 << 19),
 };
 
 struct ast;
@@ -578,13 +581,15 @@ static inline bool is_primitive(struct type *t)
 
 #define struct_id(x) return_s(x, AST_STRUCT_DEF)
 #define struct_params(x) return_a0(x, AST_STRUCT_DEF)
-#define struct_body(x) return_a1(x, AST_STRUCT_DEF)
+#define struct_body(x) return_a2(x, AST_STRUCT_DEF)
+#define struct_raw_body(x) return_a1(x, AST_STRUCT_DEF)
 #define gen_struct(id, params, body, loc) \
 	gen_str2(AST_STRUCT_DEF, id, params, body, loc)
 
 #define struct_cont_id(x) return_s(x, AST_STRUCT_CONT_DEF)
 #define struct_cont_params(x) return_a0(x, AST_STRUCT_CONT_DEF)
-#define struct_cont_body(x) return_a1(x, AST_STRUCT_CONT_DEF)
+#define struct_cont_body(x) return_a2(x, AST_STRUCT_CONT_DEF)
+#define struct_cont_raw_body(x) return_a1(x, AST_STRUCT_CONT_DEF)
 #define gen_struct_cont(id, params, body, loc)                              \
 	gen_ast(AST_STRUCT_CONT_DEF, params, body, NULL, NULL, NULL, id, 0, \
 		loc)
diff --git a/include/ek/conts.h b/include/ek/conts.h
new file mode 100644
index 0000000..c1e4d24
--- /dev/null
+++ b/include/ek/conts.h
@@ -0,0 +1,14 @@
+#ifndef CONTS_H
+#define CONTS_H
+
+#define CONTS_JOIN2(a, b) a##_##b
+#define CONTS_JOIN(a, b) CONTS_JOIN2(a, b)
+
+#define CONTAINER_OF(ptr, type, member) \
+	(type *)((char *)(ptr) - offsetof(type, member))
+
+#define foreach(name, i, s)                       \
+	for (auto i = CONTS_JOIN(name, begin)(s); \
+	     !CONTS_JOIN(name, end)(s, i);        \
+	     i = CONTS_JOIN(name, next)(i))
+#endif /* CONTS_H */
diff --git a/include/ek/map.h b/include/ek/map.h
new file mode 100644
index 0000000..5a6a22d
--- /dev/null
+++ b/include/ek/map.h
@@ -0,0 +1,105 @@
+#ifndef MAP_KEY
+#error "Need map key"
+#endif
+
+#ifndef MAP_TYPE
+#error "Need map type"
+#endif
+
+#ifndef MAP_CMP
+#error "Need map cmp"
+#endif
+
+#ifndef MAP_NAME
+#error "Need map name"
+#endif
+
+#include "conts.h"
+
+#define MAP(a) CONTS_JOIN(MAP_NAME, a)
+
+#define MAP_NODE MAP(node)
+#define MAP_ROOT MAP_NAME
+
+struct MAP_NODE {
+	MAP_KEY key;
+	MAP_TYPE data;
+};
+
+static inline int MAP(cmp)(struct MAP_NODE a, struct MAP_NODE b)
+{
+	return MAP_CMP(a.key, b.key);
+}
+
+#define BASE(a) CONTS_JOIN(MAP(map_base), a)
+
+#define SPTREE_TYPE struct MAP_NODE
+#define SPTREE_CMP MAP(cmp)
+#define SPTREE_NAME MAP(map_base)
+#include "sptree.h"
+
+struct MAP_ROOT {
+	struct MAP(map_base) root;
+};
+
+static inline struct MAP_ROOT MAP(create)()
+{
+	return (struct MAP_ROOT){.root = BASE(create)()};
+}
+
+static inline void MAP(destroy)(struct MAP_ROOT *root)
+{
+	BASE(destroy)(&root->root);
+}
+
+static inline MAP_TYPE *MAP(insert)(struct MAP_ROOT *root, MAP_KEY key,
+                                    MAP_TYPE data)
+{
+	struct MAP_NODE node = {.key = key, .data = data};
+	struct MAP_NODE *res = BASE(insert)(&root->root, node);
+	if (!res)
+		return NULL;
+
+	return &res->data;
+}
+
+static inline MAP_TYPE *MAP(find)(struct MAP_ROOT *root, MAP_KEY key)
+{
+	struct MAP_NODE node = {.key = key};
+	struct MAP_NODE *res = BASE(find)(&root->root, node);
+	if (!res)
+		return NULL;
+
+	return &res->data;
+}
+
+static inline void MAP(remove)(struct MAP_ROOT *root, MAP_KEY key)
+{
+	struct MAP_NODE node = {.key = key};
+	BASE(remove)(&root->root, node);
+}
+
+static inline struct MAP_NODE *MAP(begin)(struct MAP_ROOT *root)
+{
+	return BASE(begin)(&root->root);
+}
+
+static inline struct MAP_NODE *MAP(next)(struct MAP_NODE *n)
+{
+	return BASE(next)(n);
+}
+
+static inline bool MAP(end)(struct MAP_ROOT *root, struct MAP_NODE *n)
+{
+	return BASE(end)(&root->root, n);
+}
+
+static inline size_t MAP(len)(struct MAP_ROOT *root)
+{
+	return BASE(len)(&root->root);
+}
+
+#undef MAP_KEY
+#undef MAP_TYPE
+#undef MAP_CMP
+#undef MAP_NAME
diff --git a/include/ek/sptree.h b/include/ek/sptree.h
new file mode 100644
index 0000000..4718c26
--- /dev/null
+++ b/include/ek/sptree.h
@@ -0,0 +1,422 @@
+#include <stdint.h>
+#include <stdlib.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+#ifndef SPTREE_TYPE
+#error "Need sptree type"
+#endif
+
+#ifndef SPTREE_CMP
+#error "Need sptree cmp"
+#endif
+
+#ifndef SPTREE_NAME
+#error "Need sptree name"
+#endif
+
+#include "conts.h"
+
+#define SPTREE(a) CONTS_JOIN(SPTREE_NAME, a)
+
+#define SPNODE SPTREE(node)
+#define SPROOT SPTREE_NAME
+
+#ifndef SPTREE_H
+#define SPTREE_H
+
+#define sp_left(n) ((n)->left)
+#define sp_right(n) ((n)->right)
+#define sp_paren(n) ((n)->parent)
+#define sp_lparen(n) (sp_left(n)->parent)
+#define sp_rparen(n) (sp_right(n)->parent)
+
+#endif /* SPTREE_H */
+
+struct SPNODE {
+	int_fast16_t hint;
+	struct SPNODE *left, *right, *parent;
+	SPTREE_TYPE data;
+};
+
+struct SPROOT {
+	size_t n;
+	struct SPNODE *root;
+};
+
+static inline struct SPROOT SPTREE(create)()
+{
+	return (struct SPROOT){.n = 0, .root = NULL};
+}
+
+static inline size_t SPTREE(len)(struct SPROOT *s)
+{
+	return s->n;
+}
+
+static inline struct SPNODE *SPTREE(first)(struct SPNODE *n)
+{
+	while (sp_left(n))
+		n = sp_left(n);
+
+	return n;
+}
+
+static inline struct SPNODE *SPTREE(last)(struct SPNODE *n)
+{
+	while (sp_right(n))
+		n = sp_right(n);
+
+	return n;
+}
+
+static inline SPTREE_TYPE *SPTREE(begin)(struct SPROOT *s)
+{
+	return &SPTREE(first)(s->root)->data;
+}
+
+static inline SPTREE_TYPE *SPTREE(next)(SPTREE_TYPE *prev)
+{
+	struct SPNODE *n = CONTAINER_OF(prev, struct SPNODE, data);
+	if (sp_right(n)) {
+		n = sp_right(n);
+		while (sp_left(n))
+			n = sp_left(n);
+
+		return &n->data;
+	}
+
+	while (n) {
+		struct SPNODE *p = sp_paren(n);
+		if (!p)
+			return NULL;
+
+		if (sp_left(p) == n)
+			return &p->data;
+
+		n = p;
+	}
+
+	return NULL;
+}
+
+static inline bool SPTREE(end)(struct SPROOT *s, SPTREE_TYPE *prev)
+{
+	(void)s;
+	return prev == NULL;
+}
+
+static inline void SPTREE(turn_left)(struct SPNODE *n)
+{
+	struct SPNODE *l = sp_left(n);
+	struct SPNODE *p = sp_paren(n);
+
+	assert(l);
+
+	sp_paren(l) = sp_paren(n);
+	sp_left(n) = sp_right(l);
+	sp_paren(n) = l;
+	sp_right(l) = n;
+
+	if (p && sp_left(p) == n)
+		sp_left(p) = l;
+	else if (p)
+		sp_right(p) = l;
+
+	if (sp_left(n))
+		sp_lparen(n) = n;
+}
+
+static inline void SPTREE(turn_right)(struct SPNODE *n)
+{
+	struct SPNODE *r = sp_right(n);
+	struct SPNODE *p = sp_paren(n);
+
+	assert(r);
+
+	sp_paren(r) = sp_paren(n);
+	sp_right(n) = sp_left(r);
+	sp_paren(n) = r;
+	sp_left(r) = n;
+
+	if (p && sp_left(p) == n)
+		sp_left(p) = r;
+	else if (p)
+		sp_right(p) = r;
+
+	if (sp_right(n))
+		sp_rparen(n) = n;
+}
+
+static inline int_fast16_t SPTREE(leaning)(struct SPNODE *n)
+{
+	int_fast16_t l = 0;
+	int_fast16_t r = 0;
+
+	if (sp_left(n))
+		l = sp_left(n)->hint + 1;
+
+	if (sp_right(n))
+		r = sp_right(n)->hint + 1;
+
+	return l - r;
+}
+
+static inline int_fast16_t SPTREE(max_hint)(struct SPNODE *n)
+{
+	int_fast16_t l = 0;
+	int_fast16_t r = 0;
+
+	if (sp_left(n))
+		l = sp_left(n)->hint + 1;
+
+	if (sp_right(n))
+		r = sp_right(n)->hint + 1;
+
+	if (l > r)
+		return l;
+	else
+		return r;
+}
+
+static inline void SPTREE(update)(struct SPROOT *r, struct SPNODE *n)
+{
+	while (n) {
+		int b = SPTREE(leaning)(n);
+		int prev_hint = n->hint;
+		struct SPNODE *p = sp_paren(n);
+
+		if (b < -1) {
+			/* leaning to the right */
+			if (n == r->root)
+				r->root = sp_right(n);
+
+			SPTREE(turn_right)(n);
+		}
+
+		else if (b > 1) {
+			/* leaning to the left */
+			if (n == r->root)
+				r->root = sp_left(n);
+
+			SPTREE(turn_left)(n);
+		}
+
+		n->hint = SPTREE(max_hint)(n);
+		if (n->hint == 0 || n->hint != prev_hint)
+			n = p;
+		else
+			return;
+	}
+}
+
+static inline SPTREE_TYPE *SPTREE(insert)(struct SPROOT *s, SPTREE_TYPE data)
+{
+	if (!s->root) {
+		assert(s->n == 0);
+		struct SPNODE *new = malloc(sizeof(struct SPNODE));
+		if (!new)
+			return NULL;
+
+		new->left = new->right = new->parent = NULL;
+		new->data = data;
+		new->hint = 0;
+
+		s->root = new;
+		s->n = 1;
+		return &new->data;
+	}
+
+	bool insert_left = false;
+
+	struct SPNODE *n = s->root;
+	struct SPNODE *p = NULL;
+	while (n) {
+		p = n;
+		int c = SPTREE_CMP(n->data, data);
+		if (c < 0) {
+			n = sp_left(n);
+			insert_left = true;
+			continue;
+		}
+		if (c > 0) {
+			n = sp_right(n);
+			insert_left = false;
+			continue;
+		}
+
+		/* we already have a node like this */
+		return &n->data;
+	}
+
+	struct SPNODE *new = malloc(sizeof(struct SPNODE));
+	if (!new)
+		return NULL;
+
+	new->left = new->right = NULL;
+	new->parent = p;
+	new->data = data;
+	new->hint = 0;
+
+	if (insert_left)
+		sp_left(p) = new;
+	else
+		sp_right(p) = new;
+
+	SPTREE(update)(s, new);
+	s->n++;
+	return &new->data;
+}
+
+static inline void SPTREE(replace_right)(struct SPNODE *n, struct SPNODE *r)
+{
+	struct SPNODE *p = sp_paren(n);
+	struct SPNODE *rp = sp_paren(r);
+
+	if (sp_left(rp) == r) {
+		sp_left(rp) = sp_right(r);
+		if (sp_right(r))
+			sp_rparen(r) = rp;
+	}
+
+	if (sp_paren(rp) == n)
+		sp_paren(rp) = r;
+
+	sp_paren(r) = p;
+	sp_left(r) = sp_left(n);
+
+	if (sp_right(n) != r) {
+		sp_right(r) = sp_right(n);
+		sp_rparen(n) = r;
+	}
+
+	if (p && sp_left(p) == n)
+		sp_left(p) = r;
+	else if (p)
+		sp_right(p) = r;
+
+	if (sp_left(n))
+		sp_lparen(n) = r;
+}
+
+static inline void SPTREE(replace_left)(struct SPNODE *n, struct SPNODE *l)
+{
+	struct SPNODE *p = sp_paren(n);
+	struct SPNODE *lp = sp_paren(l);
+
+	if (sp_right(lp) == l) {
+		sp_right(lp) = sp_left(l);
+		if (sp_left(l))
+			sp_lparen(l) = lp;
+	}
+
+	if (sp_paren(lp) == n)
+		sp_paren(lp) = l;
+
+	sp_paren(l) = p;
+	sp_right(l) = sp_right(n);
+
+	if (sp_left(n) != l) {
+		sp_left(l) = sp_left(n);
+		sp_lparen(n) = l;
+	}
+
+	if (p && sp_left(p) == n)
+		sp_left(p) = l;
+	else if (p)
+		sp_right(p) = l;
+
+	if (sp_right(n))
+		sp_rparen(n) = l;
+}
+
+static inline SPTREE_TYPE *SPTREE(find)(struct SPROOT *s, SPTREE_TYPE data)
+{
+	struct SPNODE *n = s->root;
+	while (n) {
+		int c = SPTREE_CMP(n->data, data);
+		if (c < 0) {
+			n = n->left;
+			continue;
+		}
+
+		if (c > 0) {
+			n = n->right;
+			continue;
+		}
+
+		return &n->data;
+	}
+
+	return NULL;
+}
+
+static inline void SPTREE(remove_found)(struct SPROOT *s, SPTREE_TYPE *found)
+{
+	s->n--;
+	struct SPNODE *del = CONTAINER_OF(found, struct SPNODE, data);
+	if (sp_right(del)) {
+		struct SPNODE *least = SPTREE(first)(sp_right(del));
+
+		if (del == s->root)
+			s->root = least;
+
+		SPTREE(replace_right)(del, least);
+		SPTREE(update)(s, sp_right(least));
+		return;
+	}
+
+	if (sp_left(del)) {
+		struct SPNODE *most = SPTREE(last)(sp_left(del));
+
+		if (del == s->root)
+			s->root = most;
+
+		SPTREE(replace_left)(del, most);
+		SPTREE(update)(s, sp_left(most));
+		return;
+	}
+
+	if (del == s->root) {
+		s->root = NULL;
+		return;
+	}
+
+	/* empty node */
+	struct SPNODE *paren = sp_paren(del);
+
+	if (sp_left(paren) == del)
+		sp_left(paren) = NULL;
+	else
+		sp_right(paren) = NULL;
+
+	SPTREE(update)(s, paren);
+}
+
+static inline void SPTREE(remove)(struct SPROOT *s, SPTREE_TYPE data)
+{
+	SPTREE_TYPE *found = SPTREE(find)(s, data);
+	if (!found)
+		return;
+
+	SPTREE(remove_found)(s, found);
+	struct SPNODE *del = CONTAINER_OF(found, struct SPNODE, data);
+	free(del);
+}
+
+static inline void SPTREE(destroy)(struct SPROOT *s)
+{
+	while (s->root) {
+		SPTREE_TYPE *top = &s->root->data;
+		SPTREE(remove_found)(s, top);
+		struct SPNODE *del = CONTAINER_OF(top, struct SPNODE, data);
+		free(del);
+	}
+}
+
+#undef SPTREE
+#undef SPNODE
+#undef SPROOT
+#undef SPTREE_NAME
+#undef SPTREE_TYPE
+#undef SPTREE_CMP
diff --git a/scripts/makefile b/scripts/makefile
index 75631b7..0ee0e7d 100644
--- a/scripts/makefile
+++ b/scripts/makefile
@@ -42,7 +42,7 @@ COMPILER	!= [ -n "$(CROSS_COMPILE)" ]						\
 			|| echo $(CC)
 
 
-OBFLAGS		:= -g
+OBFLAGS		:= -g -std=gnu23
 WARNFLAGS	:= -Wall -Wextra
 
 COMPILE_FLAGS	:= $(CFLAGS) $(WARNFLAGS) $(OPTFLAGS) $(OBFLAGS) $(ASSERTFLAGS) \
diff --git a/src/actualize.c b/src/actualize.c
index 9e36553..11c8db7 100644
--- a/src/actualize.c
+++ b/src/actualize.c
@@ -491,14 +491,19 @@ static struct ast *analyze_type_expand(struct scope *scope,
 	return body;
 }
 
-static int has_trait(struct ast *body, char *id)
+static int has_trait(struct ast *body, struct ast *expand)
 {
+	assert(expand->k == AST_TYPE_EXPAND);
 	foreach_node(n, body) {
-		/* traits don't currently take generic parameters I guess? */
-		if (n->k != AST_ID)
+		/* ignore trait parameters for now */
+		if (n->k != AST_TYPE_EXPAND)
+			continue;
+
+		/* ignore ourselves */
+		if (n == expand)
 			continue;
 
-		if (same_id(id_str(n), id))
+		if (same_id(type_expand_id(n), type_expand_id(expand)))
 			return -1;
 	}
 
@@ -739,7 +744,8 @@ static int reset(struct ast *body)
 	return ast_visit(_reset, NULL, body, NULL);
 }
 
-static int expand_type(struct ast *expd, struct ast *params, struct type *types)
+static int expand_type(struct scope *scope, struct ast *expd,
+                       struct ast *params, struct type *types)
 {
 	/* we're getting expanded so remove our params to avoid redefining them
 	 * later */
@@ -750,9 +756,6 @@ static int expand_type(struct ast *expd, struct ast *params, struct type *types)
 	default: abort();
 	}
 
-	assert(expd->scope->parent);
-	struct scope *p = expd->scope->parent;
-
 	reset(expd);
 
 	foreach_node(n, params) {
@@ -782,7 +785,7 @@ static int expand_type(struct ast *expd, struct ast *params, struct type *types)
 	 * will succeed (and I guess we wouldn't need to actualize anything) but
 	 * this seems like the simplest solution for now */
 	struct act_state state = {0};
-	int ret = actualize(&state, p, expd);
+	int ret = actualize(&state, scope, expd);
 	assert(ret == 0);
 
 	printf("\n//expanded:\n");
@@ -812,43 +815,27 @@ static struct ast *maybe_expand_struct(struct scope *scope, struct ast *def,
 		return NULL;
 
 	struct ast *expd = clone_ast(def);
-	if (expand_type(expd, struct_params(def), args))
+	if (scope_add_expd_struct(scope, def, args, expd))
+		return NULL;
+
+	if (expand_type(scope, expd, struct_params(def), args))
 		return NULL;
 
 	return expd;
 }
 
-static int expand_chain(struct ast *expd, struct ast *params,
+static int expand_chain(struct scope *scope, struct ast *expd,
+                        struct ast *params,
                         struct type *types)
 {
 	/* bit of a hack for the moment, but start at the bottom of the chain to
 	 * ensure everything gets actualized in the 'correct' order. Might be a
 	 * good idea to instead do some preparations for each node in the chain
 	 * so we can avoid recursion if need be */
-	if (expd->chain && expand_chain(expd->chain, params, types))
+	if (expd->chain && expand_chain(scope, expd->chain, params, types))
 		return -1;
 
-	return expand_type(expd, params, types);
-}
-
-static struct ast *chain_graft(struct ast *exists, struct ast *def,
-                               struct ast *params, struct type *types)
-{
-	if (same_src(exists, def))
-		return exists;
-
-	assert(def->chain);
-	struct ast *graft = chain_graft(exists, def->chain, params, types);
-	if (!graft)
-		return NULL;
-
-	struct ast *new = clone_ast(def);
-	new->chain = graft;
-
-	if (expand_type(new, params, types))
-		return NULL;
-
-	return new;
+	return expand_type(scope, expd, params, types);
 }
 
 static struct ast *maybe_expand_struct_cont(struct scope *scope,
@@ -868,15 +855,18 @@ static struct ast *maybe_expand_struct_cont(struct scope *scope,
 		return NULL;
 	}
 
-	struct ast *exists = file_scope_find_expd_struct(scope, base, args);
+	struct ast *exists = file_scope_find_expd_struct(scope, def, args);
 	if (exists)
-		return chain_graft(exists, def, struct_params(base), args);
+		return exists;
 
 	if (!should_implement_list(scope, struct_params(base), loc, args))
 		return NULL;
 
 	struct ast *expd = clone_chain(def);
-	if (expand_chain(expd, struct_params(base), args))
+	if (scope_add_expd_chain(scope, def, args, expd))
+		return NULL;
+
+	if (expand_chain(scope, expd, struct_params(base), args))
 		return NULL;
 
 	return expd;
@@ -1017,48 +1007,36 @@ static int simplify_refderef(struct act_state *state, struct scope *scope,
 	return 0;
 }
 
-/* not really ufcs at the moment */
-static int maybe_ufcs(struct act_state *state, struct scope *scope,
-                      struct ast *call)
+static int use_ufcs(struct ast *call)
 {
 	assert(call->k == AST_CALL);
 	struct ast *dot = call_expr(call);
 	if (dot->k != AST_DOT)
-		return 0;
+		return false;
 
-	struct type *ptypes = callable_ptypes(dot->t);
+	/** @todo does this still work with function pointers? */
 	struct ast *expr = dot_expr(dot);
-	char *id = strdup(dot_id(dot));
-	call_expr(call) = gen_fetch(id, clone_type(expr->t), dot->loc);
-	(call_expr(call))->t = clone_type(dot->t);
-	(call_expr(call))->scope = scope;
-
-	struct ast *ref = NULL;
+	struct type *type = expr->t;
+	if (dot->t->k != TYPE_CALLABLE)
+		return false;
 
+	struct type *ptypes = callable_ptypes(dot->t);
 	if (!ptypes) {
-		ref = NULL;
+		ast_set_flags(call, AST_FLAG_UFCS_TRIVIAL);
+		return true;
 	}
-	else if (ptypes->k == TYPE_PTR) {
-		/* is ufcs expects reference to member, try to take address */
-		ref = gen_unop(AST_REF, expr, dot->loc);
-		ref->t = tgen_ptr(clone_type(expr->t), dot->loc);
-		if (actualize_type(state, scope, ref->t))
-			return -1;
 
-		ref->scope = scope;
-	}
-	else {
-		/* otherwise, try to pass expr as is */
-		ref = expr;
+	if (types_match(ptypes, type)) {
+		ast_set_flags(call, AST_FLAG_UFCS_SIMPLE);
+		return true;
 	}
 
-	if (ref && simplify_refderef(state, scope, ref))
-		return -1;
-
-	if (ref)
-		call_args(call) = ast_prepend(call_args(call), ref);
+	if (ptypes->k == TYPE_PTR && types_match(ptr_base(ptypes), type)) {
+		ast_set_flags(call, AST_FLAG_UFCS_REF);
+		return true;
+	}
 
-	return 0;
+	return false;
 }
 
 static int actualize_call(struct act_state *state,
@@ -1073,23 +1051,28 @@ static int actualize_call(struct act_state *state,
 		return -1;
 
 	struct ast *expr = call_expr(call);
-	if (expr->t->k != TYPE_CALLABLE) {
-		char *tstr = type_str(expr->t);
+	struct type *type = expr->t;
+	if (type->k == TYPE_PTR)
+		type = ptr_base(type);
+
+	if (type->k != TYPE_CALLABLE) {
+		char *tstr = type_str(type);
 		semantic_error(scope->fctx, call, "not a callable type: %s",
 		               tstr);
 		free(tstr);
 		return -1;
 	}
 
-	if (maybe_ufcs(state, scope, call))
-		return -1;
-
-	struct type *callable = expr->t;
+	struct type *callable = type;
 	struct type *ptypes = callable_ptypes(callable);
 	struct ast *arg = call_args(call);
+
+	if (use_ufcs(call) && ptypes)
+		ptypes = ptypes->n;
+
 	foreach_type(p, ptypes) {
 		if (!arg) {
-			semantic_error(scope->fctx, call, "too many arguments");
+			semantic_error(scope->fctx, call, "too few arguments");
 			return -1;
 		}
 
@@ -2040,25 +2023,28 @@ static int _replace_type_id(struct type *type, void *data)
 		break;
 	}
 
-	case TYPE_TRAIT: {
-		struct ast *def = type->d;
-		assert(def);
+	/* these shouldn't actually even be here?
+	   case TYPE_TRAIT: {
+	        struct ast *def = type->d;
+	        assert(def);
 
-		char *name = trait_id(def);
-		if (same_id(id, name))
-			replace_type(type, clone_type(replacement));
-		break;
-	}
+	        char *name = trait_id(def);
+	        if (same_id(id, name))
+	                replace_type(type, clone_type(replacement));
 
-	case TYPE_STRUCT: {
-		struct ast *def = type->d;
-		assert(def);
+	        break;
+	   }
 
-		char *name = struct_id(def);
-		if (same_id(id, name))
-			replace_type(type, clone_type(replacement));
-		break;
-	}
+	   case TYPE_STRUCT: {
+	        struct ast *def = type->d;
+	        assert(def);
+
+	        char *name = struct_id(def);
+	        if (same_id(id, name))
+	                replace_type(type, clone_type(replacement));
+	        break;
+	   }
+	 */
 
 	default:
 		break;
@@ -2103,107 +2089,6 @@ static int clear_scope(struct ast *nodes)
 	return ast_visit(_clear_scope, NULL, nodes, NULL);
 }
 
-
-/* lots of overlap with actualize_struct, kind of ugly... */
-static int actualize_trait(struct act_state *state, struct scope *scope,
-                           struct ast *node)
-{
-	UNUSED(state);
-	assert(node->k == AST_TRAIT_DEF);
-	struct ast *params = trait_params(node);
-	struct scope *trait_scope = create_scope();
-	if (!trait_scope)
-		return -1;
-
-	scope_add_scope(node->scope, trait_scope);
-	node->scope = trait_scope;
-
-	/** @todo should probably add in aliases for the traits in scope? */
-	if (params)
-		ast_set_flags(node, AST_FLAG_GENERIC);
-
-	char *id = trait_id(node);
-	node->t = tgen_trait(strdup(id), node, node->loc);
-
-	/* copy body */
-	node->a2 = clone_ast(trait_raw_body(node));
-
-	/* do type expansions */
-	foreach_node(n, trait_body(node)) {
-		if (n->k != AST_TYPE_EXPAND)
-			continue;
-
-		/* don't re-expand already implemented traits */
-		if (has_trait(trait_body(node), type_expand_id(n))) {
-			/* not sure about this, but at least we don't have stray
-			 * type expands everywhere */
-			n->k = AST_EMPTY;
-			continue;
-		}
-
-		if (same_id(trait_id(node), type_expand_id(n))) {
-			semantic_error(scope->fctx, n,
-			               "recursive trait implementations not allowed");
-			return -1;
-		}
-
-		struct ast *body = analyze_type_expand(scope, n);
-		if (!body) {
-			n->k = AST_EMPTY;
-			continue;
-		}
-
-		replace_type_id(body, type_expand_id(n), node->t);
-		clear_scope(body);
-
-		ast_last(body)->n = n->n;
-		n->n = body;
-	}
-
-
-	/** @todo I should really check that there's just one prototype and one
-	 * implementation of that prototype, not sure what the best approach
-	 * would be. Add a prototypes -list to scopes? */
-
-	/* add all prototypes that don't have matching definition to scope */
-	foreach_node(n, trait_body(node)) {
-		if (n->k == AST_TYPE_EXPAND)
-			continue;
-
-		if (n->k == AST_PROC_DEF && !proc_body(n))
-			continue;
-
-		if (analyze_visibility(trait_scope, n))
-			return -1;
-
-		struct act_state state = {0};
-		if (actualize(&state, trait_scope, n))
-			return -1;
-	}
-
-	foreach_node(n, trait_body(node)) {
-		/* 'actualize' prototypes to make them appear in scope searches
-		 * */
-		if (n->k != AST_PROC_DEF)
-			continue;
-
-		if (proc_body(n))
-			continue;
-
-		struct ast *exists = scope_find_proc(trait_scope, proc_id(n));
-		if (exists)
-			continue;
-
-		if (analyze_visibility(trait_scope, n))
-			return -1;
-
-		if (actualize_proc_sign(trait_scope, n))
-			return -1;
-	}
-
-	return node->t == NULL;
-}
-
 static struct ast *chain_lookup(struct act_state *state, struct ast *def,
                                 char *id)
 {
@@ -2262,8 +2147,14 @@ static int expand_struct_body(struct act_state *state,
 	if (params)
 		ast_set_flags(node, AST_FLAG_GENERIC);
 
+	/* clone raw body */
+	node->a2 = clone_ast_list(body);
+	body = node->a2;
+
 	/* do type setting first to make sure body checking works */
-	if (same_id(id, "i27"))
+	if (node->k == AST_TRAIT_DEF)
+		node->t = tgen_trait(strdup(id), node, node->loc);
+	else if (same_id(id, "i27"))
 		node->t = tgen_primitive(TYPE_I27, strdup(id), node, node->loc);
 	else if (same_id(id, "i9"))
 		node->t = tgen_primitive(TYPE_I9, strdup(id), node, node->loc);
@@ -2306,23 +2197,19 @@ static int expand_struct_body(struct act_state *state,
 	if (node->t->k == TYPE_STRUCT)
 		tstruct_params(node->t) = types;
 
-	struct ast *def = file_scope_find_type(scope, id);
-	struct ast *base = chain_base(def);
-
 	int ret = 0;
-	if (node->k == AST_STRUCT_DEF)
-		ret = scope_add_expd_struct(scope, base, types, node);
-	else if (node->k == AST_STRUCT_CONT_DEF)
-		ret = scope_add_expd_chain(scope, base, types, node);
-	else
-		abort();
+	switch (node->k) {
+	case AST_STRUCT_DEF: ret = scope_add_expd_struct(scope, node, types,
+		                                         node); break;
+	case AST_STRUCT_CONT_DEF: ret = scope_add_expd_chain(scope, node, types,
+		                                             node); break;
+	case AST_TRAIT_DEF: break;
+	default: abort();
+	}
 
 	assert(ret == 0);
 
 	foreach_node(n, body) {
-		if (n->k != AST_TYPE_EXPAND)
-			continue;
-
 		/** @todo when I eventually implement continuing structure
 		 * definitions I might add the primitive types by default to
 		 * structs, that way we don't need this check or the above type
@@ -2333,9 +2220,13 @@ static int expand_struct_body(struct act_state *state,
 			return -1;
 		}
 
-		if (has_trait(body, type_expand_id(n))) {
-			n->k = AST_EMPTY;
+		if (n->k != AST_TYPE_EXPAND)
 			continue;
+
+		if (has_trait(body, n)) {
+			semantic_error(scope->fctx, n,
+			               "reimplementation of trait");
+			return -1;
 		}
 
 		if (same_id(id, type_expand_id(n))) {
@@ -2357,6 +2248,16 @@ static int expand_struct_body(struct act_state *state,
 		n->n = body;
 	}
 
+	/* add prototypes */
+	foreach_node(n, body) {
+		if (!(n->k == AST_PROC_DEF && !proc_body(n)))
+			continue;
+
+		if (analyze_visibility(struct_scope, n))
+			return -1;
+	}
+
+	/* add implementations/variables */
 	foreach_node(n, body) {
 		/* don't actually actualize type expansion for now, it's just
 		 * sticking around to make it easier to check if a type
@@ -2365,11 +2266,10 @@ static int expand_struct_body(struct act_state *state,
 		if (n->k == AST_TYPE_EXPAND)
 			continue;
 
-		/* prototypes are handled separately */
 		if (n->k == AST_PROC_DEF && !proc_body(n))
 			continue;
 
-		if (n->k == AST_PROC_DEF) {
+		if (n->k == AST_PROC_DEF && proc_body(n)) {
 			struct ast *prev = chain_lookup(state, node->chain,
 			                                proc_id(n));
 			if (prev) {
@@ -2388,15 +2288,14 @@ static int expand_struct_body(struct act_state *state,
 		if (n->k == AST_TYPE_EXPAND)
 			continue;
 
-		/* prototypes are (still) handled separately */
-		if (n->k == AST_PROC_DEF && !proc_body(n))
-			continue;
-
 		struct act_state state = {0};
 		if (actualize(&state, struct_scope, n))
 			return -1;
 	}
 
+	if (node->k == AST_TRAIT_DEF)
+		return 0;
+
 	/* check that all prototypes are implemented */
 	foreach_node(n, body) {
 		if (n->k != AST_PROC_DEF)
@@ -2422,8 +2321,6 @@ static int expand_struct_body(struct act_state *state,
 		}
 	}
 
-	/** @todo there is the possibility that two different traits add the
-	 * same prototype, which is reported in traits but not structs? */
 	return 0;
 }
 
@@ -2433,29 +2330,15 @@ static int actualize_struct(struct act_state *state,
 	UNUSED(state);
 	assert(node->k == AST_STRUCT_DEF);
 	return expand_struct_body(state, scope, node,
-	                          struct_id(node), struct_params(node),
-	                          struct_body(node));
+	                          struct_id(node),
+	                          struct_params(node),
+	                          struct_raw_body(node));
 }
 
 static int actualize_struct_cont(struct act_state *state,
                                  struct scope *scope, struct ast *node)
 {
 	assert(node->k == AST_STRUCT_CONT_DEF);
-	struct ast *base = chain_base(node);
-	assert(base);
-
-	/** @todo this is arguably kind of a hack to sidestep issues
-	 * with 'which implementation of this trait should be used', but
-	 * it kind of has some nice properties in and of itself, will
-	 * have to think about this a bit more. */
-	if (ast_flags(node, AST_FLAG_PUBLIC) != ast_flags(base, AST_FLAG_PUBLIC)) {
-		/** @todo should the error report mention that this is possibly
-		 * a temporary hack? */
-		semantic_error(scope->fctx, node, "different publicity flags than base");
-		semantic_info(scope->fctx, base, "previous here");
-		return -1;
-	}
-
 	struct ast *up = node->chain;
 	assert(up);
 
@@ -2465,7 +2348,17 @@ static int actualize_struct_cont(struct act_state *state,
 	return expand_struct_body(state, scope, node,
 	                          struct_cont_id(node),
 	                          struct_cont_params(node),
-	                          struct_cont_body(node));
+	                          struct_cont_raw_body(node));
+}
+
+static int actualize_trait(struct act_state *state, struct scope *scope,
+                           struct ast *node)
+{
+	assert(node->k == AST_TRAIT_DEF);
+	return expand_struct_body(state, scope, node,
+	                          trait_id(node),
+	                          trait_params(node),
+	                          trait_raw_body(node));
 }
 
 static int actualize_dot(struct act_state *state,
@@ -2516,8 +2409,8 @@ static int actualize_dot(struct act_state *state,
 
 	char *tstr = type_str(type);
 	semantic_error(scope->fctx, node,
-	               "%s does not have member",
-	               tstr);
+	               "%s does not have member '%s'",
+	               tstr, id);
 	free(tstr);
 	return -1;
 }
diff --git a/src/compiler.c b/src/compiler.c
index c29f6c7..f7e6a14 100644
--- a/src/compiler.c
+++ b/src/compiler.c
@@ -123,6 +123,50 @@ static int process(struct scope **parent, int public, const char *file)
 	return 0;
 }
 
+#define MAP_KEY char *
+#define MAP_TYPE struct scope *
+#define MAP_CMP(a, b) strcmp((a), (b))
+#define MAP_NAME scopes
+#include "ek/map.h"
+
+static int copy_scope(struct scope *to, struct scope *from)
+{
+	/** @todo handle duplicates */
+	foreach_visible(n, from->symbols) {
+		struct ast *def = n->node;
+		if (!ast_flags(def, AST_FLAG_PUBLIC))
+			continue;
+
+		switch (def->k) {
+		case AST_PROC_DEF:
+			if (scope_add_proc(to, def))
+				return -1;
+			break;
+
+		case AST_VAR_DEF:
+			if (scope_add_var(to, def))
+				return -1;
+			break;
+
+		default: abort();
+		}
+	}
+
+	return 0;
+}
+
+/* ugly global for now */
+static struct scopes scopes;
+
+static void destroy_scopes()
+{
+	foreach(scopes, n, &scopes) {
+		free(n->key);
+	}
+
+	scopes_destroy(&scopes);
+}
+
 int process_file(struct scope **scope, int public, const char *file)
 {
 	int res = -1;
@@ -141,7 +185,7 @@ int process_file(struct scope **scope, int public, const char *file)
 	if (!dir)
 		goto out;
 
-	/* TODO: iterate through include paths */
+	/* TODO: iterate through include paths? */
 	const char *cwd = ek_cwdname();
 	res_add(r, (void *)cwd);
 	if (!cwd)
@@ -153,8 +197,20 @@ int process_file(struct scope **scope, int public, const char *file)
 		goto out;
 	}
 
-	if (process(scope, public, base))
-		goto out;
+	char *real = realpath(base, NULL);
+	assert(real);
+
+	struct scope **exists = scopes_find(&scopes, real);
+	if (exists) {
+		if (copy_scope(*scope, *exists))
+			goto out;
+
+	} else {
+		if (process(scope, public, base))
+			goto out;
+
+		scopes_insert(&scopes, real, *scope);
+	}
 
 	if (chdir(cwd)) {
 		error("couldn't change back to directory %s: %s\n", cwd,
@@ -170,11 +226,14 @@ out:
 }
 
 int compile(const char *input) {
+	scopes = scopes_create();
+
 	int ret = -1;
 	struct scope *root = NULL;
 	if (process_file(&root, 0, input)) {
 		destroy_scope(root);
 		destroy_allocs();
+		destroy_scopes();
 		error("compilation of %s stopped due to errors", input);
 		return ret;
 	}
@@ -182,11 +241,13 @@ int compile(const char *input) {
 	if ((ret = lower(root))) {
 		destroy_scope(root);
 		destroy_allocs();
+		destroy_scopes();
 		error("compilation of %s stopped due to errors", input);
 		return ret;
 	}
 
 	destroy_scope(root);
 	destroy_allocs();
+	destroy_scopes();
 	return 0;
 }
diff --git a/src/lower.c b/src/lower.c
index e6c147f..8aefd68 100644
--- a/src/lower.c
+++ b/src/lower.c
@@ -196,6 +196,11 @@ typedef int (*visit_struct_t)(struct lower_state *s, struct ast *n, size_t o,
 static ssize_t visit_struct(struct lower_state *s, struct ast *def, size_t base,
                             visit_struct_t cb, void *data)
 {
+	/* I believe we're only interested in the variables, so find them at the
+	 * root of the chain */
+	if (def->chain)
+		return visit_struct(s, def->chain, base, cb, data);
+
 	size_t offset = (size_t)base;
 	foreach_node(n, struct_body(def)) {
 		if (n->k != AST_VAR_DEF)
@@ -879,12 +884,49 @@ static int lower_call(struct lower_state *s, struct ast *c,
 	assert(c->k == AST_CALL);
 
 	struct retval call = retval_create();
+	if (ast_flags(c, AST_FLAG_UFCS_SIMPLE)
+	    || ast_flags(c, AST_FLAG_UFCS_REF)
+	    || ast_flags(c, AST_FLAG_UFCS_TRIVIAL)) {
+		struct ast *dot = call_expr(c);
+		assert(dot && dot->k == AST_DOT);
+
+		struct ast *expr = dot_expr(dot);
+
+		char *id = strdup(dot_id(dot));
+		assert(id);
+
+		struct ast *fetch = gen_fetch(id, clone_type(expr->t),
+		                              dot->loc);
+		assert(fetch);
+
+		fetch->t = clone_type(dot->t);
+		call_expr(c) = fetch;
+
+		if (!ast_flags(c, AST_FLAG_UFCS_TRIVIAL)) {
+			struct ast *arg = expr;
+			if (ast_flags(c, AST_FLAG_UFCS_REF)) {
+				arg = gen_unop(AST_REF, expr, dot->loc);
+				arg->t = clone_type(expr->t);
+				/** @todo should simplify refderef here */
+			}
+
+			/* prepend new arg to list */
+			arg->n = call_args(c);
+			call_args(c) = arg;
+		}
+	}
+
 	if (lower_expr(s, call_expr(c), &call)) {
 		retval_destroy(&call);
 		return -1;
 	}
 
-	struct type *rtype = callable_rtype((call_expr(c))->t);
+	struct ast *expr = call_expr(c);
+	struct type *callable = expr->t;
+	if (callable->k == TYPE_PTR)
+		callable = ptr_base(callable);
+
+	struct type *rtype = callable_rtype(callable);
 	char *rbuf = NULL;
 	if (rtype->k == TYPE_STRUCT) {
 		rbuf = build_str("rbuf_%zd", s->uniq++);
diff --git a/src/parser.y b/src/parser.y
index 3808807..18de0e1 100644
--- a/src/parser.y
+++ b/src/parser.y
@@ -643,13 +643,15 @@ opt_sign_decls
 
 type
 	: ID { $$ = tgen_id($1, src_loc(@$)); }
-	| "^" "(" opt_sign_decls "=>" opt_type ")" {
+	| "*" "(" opt_sign_decls "=>" opt_type ")" {
 		/* still not entirely sold on this signature, but it's not terrible I
 		 * guess */
 		$$ = tgen_callable($[opt_sign_decls], $[opt_type], src_loc(@$));
+		$$ = tgen_ptr($$, src_loc(@$));
 	}
-	| "^" "(" opt_sign_decls ")" {
+	| "*" "(" opt_sign_decls ")" {
 		$$ = tgen_callable($[opt_sign_decls], NULL, src_loc(@$));
+		$$ = tgen_ptr($$, src_loc(@$));
 	}
 	| "*" type {
 		$$ = tgen_ptr($2, src_loc(@$));
diff --git a/src/scope.c b/src/scope.c
index 6687d98..8ffe2f9 100644
--- a/src/scope.c
+++ b/src/scope.c
@@ -297,7 +297,7 @@ int scope_add_proc(struct scope *scope, struct ast *proc)
 {
 	assert(proc->k == AST_PROC_DEF);
 	struct ast *exists = file_scope_find_symbol(scope, proc_id(proc));
-	if (exists) {
+	if (exists && proc_body(exists) == proc_body(proc)) {
 		semantic_error(proc->scope->fctx, proc, "proc redefined");
 		semantic_info(exists->scope->fctx, exists, "previously here");
 		return -1;
@@ -361,44 +361,14 @@ static struct expanded *scope_find_expanded(struct expanded *e, struct ast *def,
 	return NULL;
 }
 
-static void insert_expd_chain(struct scope *scope, struct ast *def,
-                              struct type *types, struct ast *expd)
-{
-	struct expanded *e = scope_find_expanded(scope->expanded, def, types);
-	assert(e);
-
-	struct ast *n = e->expd;
-	assert(n);
-
-	if (ast_flags(n, AST_FLAG_PUBLIC)
-	    || !ast_flags(expd, AST_FLAG_PUBLIC)) {
-		expd->chain = e->expd;
-		e->expd = expd;
-		/* types should be identical, we checked that earlier */
-		return;
-	}
-
-	/* find first public continuation in chain and insert just before it */
-	struct ast *next = n->chain;
-	while (next->k == AST_STRUCT_CONT_DEF &&
-	       !ast_flags(next, AST_FLAG_PUBLIC)) {
-		n = next;
-		next = n->chain;
-	}
-
-	n->chain = expd;
-	expd->chain = next;
-}
-
 int scope_add_expd_chain(struct scope *scope, struct ast *def,
                          struct type *types, struct ast *expd)
 {
-	assert(def->k == AST_STRUCT_DEF);
+	assert(def->k == AST_STRUCT_CONT_DEF);
 	assert(expd->k == AST_STRUCT_CONT_DEF);
-	assert(file_scope_find_expd_struct(scope, def, types) != NULL);
-
-	insert_expd_chain(scope, def, types, expd);
+	assert(file_scope_find_expd_struct(scope, def, types) == NULL);
 
+	create_expanded(scope, def, types, expd);
 	if (scope_add_recurse(scope, expd))
 		return scope_add_expd_chain(scope->parent, def, types, expd);
 
@@ -537,7 +507,7 @@ struct ast *file_scope_find_var(struct scope *scope, char *id)
 struct ast *scope_find_expd_struct(struct scope *scope, struct ast *def,
                                    struct type *types)
 {
-	assert(def->k == AST_STRUCT_DEF);
+	assert(def->k == AST_STRUCT_DEF || def->k == AST_STRUCT_CONT_DEF);
 	struct expanded *expd = scope_find_expanded(scope->expanded, def,
 	                                            types);
 	if (!expd)
diff --git a/tests/callbacks/callbacks.ek b/tests/callbacks/callbacks.ek
index 927c122..9e16627 100644
--- a/tests/callbacks/callbacks.ek
+++ b/tests/callbacks/callbacks.ek
@@ -1,6 +1,7 @@
 typedef i27 {}
+typedef ptr {}
 
-do_stuff(^(i27 => i27) proc => i27)
+do_stuff(*(i27 => i27) proc => i27)
 {
 	return proc(20);
 }
@@ -12,5 +13,5 @@ other_proc(i27 a => i27)
 
 main()
 {
-	do_stuff(other_proc);
+	do_stuff(other_proc&);
 }
diff --git a/tests/struct_func_ptr/source.mk b/tests/struct_func_ptr/source.mk
new file mode 100644
index 0000000..96deda8
--- /dev/null
+++ b/tests/struct_func_ptr/source.mk
@@ -0,0 +1 @@
+SIMPLE	+= struct_func_ptr
diff --git a/tests/struct_func_ptr/struct_func_ptr.ek b/tests/struct_func_ptr/struct_func_ptr.ek
new file mode 100644
index 0000000..43da6cc
--- /dev/null
+++ b/tests/struct_func_ptr/struct_func_ptr.ek
@@ -0,0 +1,14 @@
+typedef ptr {}
+typedef i27 {}
+
+typedef struct {
+	*() f;
+}
+
+do_something(){}
+
+main()
+{
+	mut p = struct!{.f = do_something&};
+	p.f();
+}
diff --git a/tests/struct_priv_trait_cont/source.mk b/tests/struct_priv_trait_cont/source.mk
index cff75f9..5bd36f0 100644
--- a/tests/struct_priv_trait_cont/source.mk
+++ b/tests/struct_priv_trait_cont/source.mk
@@ -1 +1 @@
-SIMPLE_XFAIL	+= struct_priv_trait_cont
+SIMPLE	+= struct_priv_trait_cont
diff --git a/tests/trait_multiple_expand/source.mk b/tests/trait_multiple_expand/source.mk
index f4e9516..6d1bcbb 100644
--- a/tests/trait_multiple_expand/source.mk
+++ b/tests/trait_multiple_expand/source.mk
@@ -1 +1 @@
-SIMPLE += trait_multiple_expand
+SIMPLE_XFAIL += trait_multiple_expand