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?

5 files changed, 440 insertions, 0 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