initial move checking

+ Missing implementations for most things, but it already highlights
  an oversight in my initial plan, namely that currently, a function
  might call multiple of its closures, meaning that a closure wouldn't
  be allowed to move a value. I'm debating whether to check that only
  one closure from a parameter list is called at a time or if I should
  do what Hylo does and add in some kind of 'subscript' that's like a
  function but has slightly different rules?

11 files changed, 645 insertions, 2 deletions

diff --git a/include/fwd/ast.h b/include/fwd/ast.h
index bcf4171..1da5b88 100644
--- a/include/fwd/ast.h
+++ b/include/fwd/ast.h
@@ -117,6 +117,8 @@ enum ast_kind {
 	AST_CONST_STR,
 };
 
+const char *ast_str(enum ast_kind k);
+
 enum ast_flag {
 	AST_FLAG_ANALYZED       = (1 << 0),
 	AST_FLAG_PREANALYZIS    = (1 << 1),
diff --git a/include/fwd/conts.h b/include/fwd/conts.h
new file mode 100644
index 0000000..862bd31
--- /dev/null
+++ b/include/fwd/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/fwd/debug.h b/include/fwd/debug.h
index 0794650..5123635 100644
--- a/include/fwd/debug.h
+++ b/include/fwd/debug.h
@@ -138,6 +138,8 @@ void src_issue(struct src_issue issue, const char *err_msg, ...);
 void type_mismatch(struct scope *scope, struct ast *node,
                    struct type *l, struct type *r);
 
+void move_error(struct ast *new_use, struct ast *prev_use);
+
 const char *type_str(struct type *t);
 
 #endif /* FWD_DEBUG_H */
diff --git a/include/fwd/move.h b/include/fwd/move.h
new file mode 100644
index 0000000..a23d016
--- /dev/null
+++ b/include/fwd/move.h
@@ -0,0 +1,9 @@
+#ifndef FWD_MOVE_H
+#define FWD_MOVE_H
+
+#include <fwd/ast.h>
+#include <fwd/scope.h>
+
+int mvcheck_root(struct ast *root);
+
+#endif /* FWD_MOVE_H */
diff --git a/include/fwd/sptree.h b/include/fwd/sptree.h
new file mode 100644
index 0000000..75b88fc
--- /dev/null
+++ b/include/fwd/sptree.h
@@ -0,0 +1,413 @@
+#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);
+}
+
+static inline void SPTREE(destroy)(struct SPROOT *s)
+{
+	while (s->root)
+		SPTREE(remove_found)(s, &s->root->data);
+}
+
+#undef SPTREE
+#undef SPNODE
+#undef SPROOT
diff --git a/scripts/makefile b/scripts/makefile
index 922497d..9b5ed1f 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/analyze.c b/src/analyze.c
index 37b2e65..077e7d8 100644
--- a/src/analyze.c
+++ b/src/analyze.c
@@ -418,7 +418,7 @@ static int analyze(struct state *state, struct scope *scope, struct ast *node)
 	case AST_CONST_STR:     ret = analyze_str       (state, scope, node);
 		break;
 	default:
-		internal_error("missing ast analysis");
+		internal_error("missing ast analysis for %s", ast_str(node->k));
 		return -1;
 	}
 
diff --git a/src/ast.c b/src/ast.c
index 119f943..81fa0b3 100644
--- a/src/ast.c
+++ b/src/ast.c
@@ -604,3 +604,47 @@ bool type_lists_match(struct type *al, struct type *bl)
 	}
 	return true;
 }
+
+const char *ast_str(enum ast_kind k)
+{
+#define CASE(x) case x: return #x;
+	switch (k) {
+	CASE(AST_CLOSURE);
+	CASE(AST_IF);
+	CASE(AST_LET);
+	CASE(AST_INIT);
+	CASE(AST_CALL);
+	CASE(AST_PROC_DEF);
+	CASE(AST_VAR_DEF);
+	CASE(AST_DOT);
+	CASE(AST_BLOCK);
+	CASE(AST_ID);
+	CASE(AST_EMPTY);
+	CASE(AST_ADD);
+	CASE(AST_SUB);
+	CASE(AST_MUL);
+	CASE(AST_DIV);
+	CASE(AST_REM);
+	CASE(AST_LAND);
+	CASE(AST_LOR);
+	CASE(AST_LSHIFT);
+	CASE(AST_RSHIFT);
+	CASE(AST_LT);
+	CASE(AST_GT);
+	CASE(AST_LE);
+	CASE(AST_GE);
+	CASE(AST_NE);
+	CASE(AST_EQ);
+	CASE(AST_NEG);
+	CASE(AST_LNOT);
+	CASE(AST_NOT);
+	CASE(AST_CONST_INT);
+	CASE(AST_CONST_CHAR);
+	CASE(AST_CONST_BOOL);
+	CASE(AST_CONST_FLOAT);
+	CASE(AST_CONST_STR);
+	}
+#undef CASE
+
+	return "UNKNOWN";
+}
diff --git a/src/compiler.c b/src/compiler.c
index d18e767..9f564d8 100644
--- a/src/compiler.c
+++ b/src/compiler.c
@@ -21,6 +21,7 @@
 #include <fwd/debug.h>
 #include <fwd/scope.h>
 #include <fwd/lower.h>
+#include <fwd/move.h>
 
 /**
  * Read whole file into a buffer and return pointer to buffer.
@@ -112,6 +113,9 @@ static int process(struct scope **parent, const char *file)
 	if (analyze_root(scope, tree))
 		return -1;
 
+	if (mvcheck_root(tree))
+		return -1;
+
 	return 0;
 }
 
diff --git a/src/debug.c b/src/debug.c
index cd0b8eb..f72fe9b 100644
--- a/src/debug.c
+++ b/src/debug.c
@@ -144,6 +144,12 @@ void type_mismatch(struct scope *scope, struct ast *node,
 	free((void *)rs);
 }
 
+void move_error(struct ast *new_use, struct ast *prev_use)
+{
+	semantic_error(new_use->scope, new_use, "using moved value");
+	semantic_info(prev_use->scope, prev_use, "previously moved here");
+}
+
 static void _type_str(FILE *f, struct type *t);
 
 static void _type_list_str(FILE *f, struct type *types)
diff --git a/src/move.c b/src/move.c
new file mode 100644
index 0000000..b09f745
--- /dev/null
+++ b/src/move.c
@@ -0,0 +1,149 @@
+#include <fwd/move.h>
+
+struct ast_pair {
+	struct ast *def;
+	struct ast *use;
+};
+
+#define SPTREE_TYPE struct ast_pair
+#define SPTREE_CMP(a, b) ((a).def - (b).def)
+#define SPTREE_NAME moved
+#include <fwd/sptree.h>
+
+struct state {
+	struct moved moved;
+	struct state *parent;
+};
+
+static struct state create_state(struct state *parent)
+{
+	struct state state = {};
+	state.parent = parent;
+	state.moved = moved_create();
+	return state;
+}
+
+static void destroy_state(struct state *state)
+{
+	moved_destroy(&state->moved);
+}
+
+static struct ast_pair *find_move(struct state *state, struct ast *def)
+{
+	if (!state)
+		return NULL;
+
+	struct ast_pair search = {.def = def};
+	struct ast_pair *found = moved_find(&state->moved, search);
+	if (found)
+		return found;
+
+	return find_move(state->parent, def);
+}
+
+static void insert_move(struct state *state, struct ast *def, struct ast *use)
+{
+	struct ast_pair pair =  {.def = def, .use = use};
+	moved_insert(&state->moved, pair);
+}
+
+static void push_up(struct state *state)
+{
+	struct state *parent = state->parent;
+	if (!parent)
+		return;
+
+	if (moved_len(&state->moved) == 0)
+		return;
+
+	foreach(moved, n, &state->moved) {
+		moved_insert(&parent->moved, *n);
+	}
+}
+
+static int mvcheck(struct state *state, struct ast *node);
+static int mvcheck_list(struct state *state, struct ast *nodes);
+
+static int mvcheck_proc(struct state *state, struct ast *node)
+{
+	/* extern, can't really do anything so just say it's fine */
+	if (!proc_body(node))
+		return 0;
+
+	struct state new_state = create_state(state);
+	/* we don't need to merge things into the parent state */
+	int ret = mvcheck(&new_state, proc_body(node));
+	destroy_state(&new_state);
+	return ret;
+}
+
+static int mvcheck_block(struct state *state, struct ast *node)
+{
+	return mvcheck_list(state, block_body(node));
+}
+
+static int mvcheck_list(struct state *state, struct ast *nodes)
+{
+	foreach_node(node, nodes) {
+		if (mvcheck(state, node))
+			return -1;
+	}
+
+	return 0;
+}
+
+static int mvcheck_call(struct state *state, struct ast *node)
+{
+	return mvcheck_list(state, call_args(node));
+}
+
+static int mvcheck_closure(struct state *state, struct ast *node)
+{
+	struct state new_state = create_state(state);
+	int ret = mvcheck(&new_state, closure_body(node));
+	push_up(&new_state);
+
+	destroy_state(&new_state);
+	return ret;
+}
+
+static int mvcheck_id(struct state *state, struct ast *node)
+{
+	struct ast *def = file_scope_find_symbol(node->scope, id_str(node));
+	assert(def);
+
+	struct ast_pair *prev = find_move(state, def);
+	if (prev) {
+		move_error(node, prev->use);
+		return -1;
+	}
+
+	insert_move(state, def, node);
+	return 0;
+}
+
+static int mvcheck(struct state *state, struct ast *node)
+{
+	switch (node->k) {
+	case AST_PROC_DEF:	return mvcheck_proc	(state, node);
+	case AST_BLOCK:		return mvcheck_block	(state, node);
+	case AST_CALL:		return mvcheck_call	(state, node);
+	case AST_CLOSURE:	return mvcheck_closure	(state, node);
+	case AST_ID:		return mvcheck_id	(state, node);
+	default: break;
+	}
+
+	internal_error("missing move check for %s", ast_str(node->k));
+	return -1;
+}
+
+int mvcheck_root(struct ast *root)
+{
+	foreach_node(node, root) {
+		struct state state = create_state(NULL);
+		if (mvcheck(&state, node))
+			return -1;
+	}
+
+	return 0;
+}