path: root/src/move.c

#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 merge(struct state *to, struct state *from)
{
	if (moved_len(&from->moved) == 0)
		return;

	foreach(moved, n, &from->moved) {
		moved_insert(&to->moved, *n);
	}
}

static void push_up(struct state *state)
{
	struct state *parent = state->parent;
	if (!parent)
		return;

	merge(parent, state);
}

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_call(struct state *state, struct ast *node)
{
	if (mvcheck(state, call_expr(node)))
		return -1;

	struct ast *args = call_args(node);
	if (!args)
		return 0;

	int ret = 0;
	long prev_group = args->t->group;
	struct state group_state = create_state(state);

	foreach_node(arg, call_args(node)) {
		struct state arg_state = create_state(state);
		ret = mvcheck(&arg_state, arg);

		long group = arg->t->group;
		if (prev_group != group) {
			/* previous group ended, push states up */
			push_up(&group_state);

			/* something like reset_state would maybe me more clear? */
			destroy_state(&group_state);
			group_state = create_state(state);
		}

		merge(&group_state, &arg_state);
		destroy_state(&arg_state);
		prev_group = group;
		if (ret)
			break;
	}

	destroy_state(&group_state);
	return ret;
}

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 void opt_group_left(struct state *state, struct ast *def,
                           struct ast *node)
{
	if (!def)
		return;

	insert_move(state, def, node);
	opt_group_left(state, def->ol, node);
}

static void opt_group_right(struct state *state, struct ast *def,
                            struct ast *node)
{
	if (!def)
		return;

	insert_move(state, def, node);
	opt_group_right(state, def->or, node);
}

static int mvcheck_id(struct state *state, struct ast *node)
{
	struct ast *def = file_scope_find_symbol(node->scope, id_str(node));
	assert(def);

	/* moves only apply to variables, functions are 'eternal' */
	if (def->k != AST_VAR_DEF)
		return 0;

	struct ast_pair *prev = find_move(state, def);
	if (prev) {
		/* error messages for opt groups could be improved */
		move_error(node, prev->use);
		return -1;
	}

	insert_move(state, def, node);

	if (def->or || def->ol) {
		/* we're part of an opt group, add all other members as if they
		 * were moved as well  */
		opt_group_left(state, def->ol, node);
		opt_group_right(state, def->or, node);
	}

	return 0;
}

static int mvcheck_let(struct state *state, struct ast *node)
{
	return mvcheck(state, let_expr(node));
}

static int mvcheck_init(struct state *state, struct ast *node)
{
	return mvcheck_list(state, init_body(node));
}

static int mvcheck_if(struct state *state, struct ast *node)
{
	if (mvcheck(state, if_cond(node)))
		return -1;

	struct state body_state = create_state(state);
	struct state else_state = create_state(state);

	if (mvcheck(&body_state, if_body(node))) {
		destroy_state(&body_state);
		destroy_state(&else_state);
		return -1;
	}

	if (mvcheck(&else_state, if_else(node))) {
		destroy_state(&body_state);
		destroy_state(&else_state);
		return -1;
	}

	push_up(&body_state);
	push_up(&else_state);

	destroy_state(&body_state);
	destroy_state(&else_state);
	return 0;
}

static int mvcheck_unop(struct state *state, struct ast *node)
{
	return mvcheck(state, unop_expr(node));
}

static int mvcheck_binop(struct state *state, struct ast *node)
{
	if (mvcheck(state, binop_left(node)))
		return -1;

	return mvcheck(state, binop_right(node));
}

static int mvcheck_comparison(struct state *state, struct ast *node)
{
	if (mvcheck(state, comparison_left(node)))
		return -1;

	return mvcheck(state, comparison_right(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(struct state *state, struct ast *node)
{
	if (is_unop(node))
		return mvcheck_unop(state, node);

	if (is_binop(node))
		return mvcheck_binop(state, node);

	if (is_comparison(node))
		return mvcheck_comparison(state, 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_LET:           return mvcheck_let      (state, node);
	case AST_ID:            return mvcheck_id       (state, node);
	case AST_INIT:          return mvcheck_init     (state, node);
	case AST_IF:            return mvcheck_if       (state, node);
	case AST_CONST_INT:
	case AST_CONST_STR:
	case AST_CONST_FLOAT:
	case AST_CONST_CHAR:
		return 0;
	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;

		destroy_state(&state);
	}

	return 0;
}