implement enough type analysis for vector examplegnc

+ Big commit, scary
+ Some details still a bit up in the air, mainly about move checking
  structure member access ('register' types are freely copied I guess,
  same as in rust? How about user types?)

7 files changed, 846 insertions, 155 deletions

diff --git a/src/analyze.c b/src/analyze.c
index be52bfb..4f98ac6 100644
--- a/src/analyze.c
+++ b/src/analyze.c
@@ -3,7 +3,9 @@
 
 #include <fwd/compiler.h>
 #include <fwd/analyze.h>
+#include <fwd/rewrite.h>
 #include <fwd/mod.h>
+
 #include <stdlib.h>
 #include <stdarg.h>
 #include <string.h>
@@ -214,16 +216,36 @@ static int analyze_init(struct state *state, struct scope *scope,
 	if (analyze(state, scope, init_body(node)))
 		return -1;
 
-	/** @todo check that all parameters match, though that requires that the
-	 * type is defined in fwd and not in C++, so this might have to wait a
-	 * bit */
-	node->t = tgen_construct(strdup(init_id(node)), init_args(node),
-	                         node->loc);
-	if (!node->t) {
-		internal_error("failed allocating type for construct");
+	internal_error("init unimplemented");
+	return -1;
+}
+
+static int deduce_closure_types(struct scope *scope, struct ast *node, struct type *type)
+{
+	/* a bit of checking duplication here, hmm */
+	if (node->k != AST_CLOSURE)
+		return 0;
+
+	if (type->k != TYPE_CLOSURE && type->k != TYPE_PURE_CLOSURE) {
+		semantic_error(scope, node, "surprise closure");
+		return -1;
+	}
+
+	struct ast *param = closure_bindings(node);
+	struct type *t = tclosure_args(type);
+	if (ast_list_len(param) != type_list_len(t)) {
+		semantic_error(scope, node, "expected %zu closure parameters, got %zu",
+				type_list_len(t), ast_list_len(param));
 		return -1;
 	}
 
+	for (; param && t; param = param->n, t = t->n) {
+		if (var_type(param))
+			continue;
+
+		var_type(param) = t;
+	}
+
 	return 0;
 }
 
@@ -241,8 +263,6 @@ static int analyze_call(struct state *state, struct scope *scope,
 
 	struct type *types = callable_types(expr->t);
 	struct ast *args = call_args(node);
-	if (analyze_list(state, scope, args))
-		return -1;
 
 	size_t expected = type_list_len(types);
 	size_t got = ast_list_len(args);
@@ -253,18 +273,24 @@ static int analyze_call(struct state *state, struct scope *scope,
 	}
 
 	struct type *type = types;
-	foreach_node(arg, args) {
+	struct ast *arg = args;
+	for (; arg && type; type = type->n, arg = arg->n) {
+		if (deduce_closure_types(scope, arg, type))
+			return -1;
+
+		if (analyze(state, scope, arg))
+			return -1;
+
 		if (arg->k == AST_CLOSURE)
 			state->flags |= STATE_PROC_REQ_FRAME;
 
 		if (!types_match(type, arg->t)) {
-			type_mismatch(scope, node, type, arg->t);
+			type_mismatch(scope, arg, type, arg->t);
 			return -1;
 		}
 
 		/* clone group info */
 		arg->t->group = type->group;
-		type = type->n;
 	}
 
 	node->t = tgen_void(node->loc);
@@ -309,7 +335,7 @@ static int analyze_deref(struct state *state, struct scope *scope,
 		semantic_error(node->scope, node,
 		               "deref of raw ptr not allowed");
 		semantic_info(node->scope, node,
-		              "use fwd_null() to convert to ref");
+		              "use a nil check to convert to ref");
 		return -1;
 	}
 
@@ -319,7 +345,7 @@ static int analyze_deref(struct state *state, struct scope *scope,
 		return -1;
 	}
 
-	node->t = tptr_base(expr->t);
+	node->t = tref_base(expr->t);
 	return 0;
 }
 
@@ -432,6 +458,126 @@ static int analyze_str(struct state *state, struct scope *scope,
 	return 0;
 }
 
+static int analyze_template(struct state *state, struct scope *scope, struct ast *node)
+{
+	struct scope *template_scope = create_scope();
+	scope_add_scope(scope, template_scope);
+
+	/* enough for vec example since traits are as of yet unimplemented */
+
+	node->t = tgen_void(node->loc);
+	return 0;
+}
+
+static int analyze_instance(struct state *state, struct scope *scope, struct ast *node)
+{
+	(void)state;
+
+	struct ast *id = instance_templ(node);
+	struct ast *template = file_scope_find_template(scope, id_str(id));
+	if (!template) {
+		semantic_error(scope, node, "no such template: %s\n", id_str(id));
+		return -1;
+	}
+
+	/** @todo check that type implements trait */
+	struct ast *params = template_type_params(template);
+	struct type *args = instance_type_args(node);
+	if (ast_list_len(params) != type_list_len(args)) {
+		semantic_error(scope, node, "expected %zu types, got %zu\n",
+				ast_list_len(params), type_list_len(args));
+		return -1;
+	}
+
+	/* make a working copy that we modify */
+	struct ast *copy = clone_ast(template);
+	if (!copy) {
+		internal_error("failed copying template body");
+		return -1;
+	}
+
+	if (rewrite_holes(copy, instance_id(node)))
+		return -1;
+
+	/* replace type args */
+	struct ast *p = params;
+	struct type *a = args;
+	for (; p && a; p = p->n, a = a->n) {
+		if (rewrite_types(copy, var_id(p), tid_str(a)))
+			return -1;
+	}
+
+	printf("// --- instance %s ---\n", instance_id(node));
+	ast_dump(0, copy);
+
+	/* analyze newly initialized things (might not work for supertemplates?) */
+	if (analyze_root(scope, template_body(copy)))
+		return -1;
+
+	node->t = tgen_void(node->loc);
+	return 0;
+}
+
+static int analyze_struct(struct state *state, struct scope *scope, struct ast *node)
+{
+	struct scope *struct_scope = create_scope();
+	scope_add_scope(scope, struct_scope);
+	node->scope = struct_scope;
+
+	if (analyze_list(state, struct_scope, struct_body(node)))
+		return -1;
+
+	node->t = tgen_void(node->loc);
+	return 0;
+}
+
+static int analyze_construct(struct state *state, struct scope *scope, struct ast *node)
+{
+	struct ast *def = file_scope_find_type(scope, construct_id(node));
+	if (!def) {
+		semantic_error(scope, node, "no such type");
+		return -1;
+	}
+
+	if (def->k != AST_STRUCT_DEF) {
+		semantic_error(scope, node, "type is not a struct");
+		return -1;
+	}
+
+	struct ast *params = struct_body(def);
+	struct ast *args = construct_members(node);
+
+	if (ast_list_len(params) != ast_list_len(args)) {
+		semantic_error(scope, node, "expected %zu args, got %zu\n",
+				ast_list_len(params), ast_list_len(args));
+		return -1;
+	}
+
+	foreach_node(arg, args) {
+		struct ast *exists = scope_find_symbol(def->scope, construction_id(arg));
+		if (!exists) {
+			semantic_error(scope, arg, "no member %s in %s\n",
+					construction_id(arg), construct_id(node));
+			return -1;
+		}
+
+		struct ast *expr = construction_expr(arg);
+		if (analyze(state, scope, expr))
+			return -1;
+
+		if (!types_match(exists->t, expr->t)) {
+			type_mismatch(scope, arg, exists->t, expr->t);
+			return -1;
+		}
+
+		/** @todo check for duplicates, preferably not in O(n^2) or with
+		 * a memory allocation? */
+	}
+
+	node->t = tgen_id(strdup(construct_id(node)), node->loc);
+	return 0;
+}
+
 static int analyze_if(struct state *state, struct scope *scope,
                       struct ast *node)
 {
@@ -453,6 +599,212 @@ static int analyze_if(struct state *state, struct scope *scope,
 	return 0;
 }
 
+static int analyze_nil(struct state *state, struct scope *scope, struct ast *node)
+{
+	(void)state;
+	(void)scope;
+
+	node->t = tgen_nil(node->loc);
+	return 0;
+}
+
+static bool castable_type(struct type *type)
+{
+	switch (type->k) {
+	case TYPE_PTR:
+	case TYPE_FUNC_PTR:
+	case TYPE_I8:
+	case TYPE_I16:
+	case TYPE_I32:
+	case TYPE_I64:
+	case TYPE_U8:
+	case TYPE_U16:
+	case TYPE_U32:
+	case TYPE_U64:
+		return true;
+
+	default:
+		return false;
+	}
+
+	return false;
+}
+
+static int analyze_as(struct state *state, struct scope *scope, struct ast *node)
+{
+	if (analyze(state, scope, as_expr(node)))
+		return -1;
+
+	if (analyze_type(state, scope, as_type(node)))
+		return -1;
+
+	/* for now, any 'register' size type can be cast to any other. Might
+	 * restrict this, like signed to unsigned might be weird if its negative
+	 * etc and should be done via a helper function */
+	struct type *expr_type = (as_expr(node))->t;
+	struct type *type = as_type(node);
+	if (!castable_type(expr_type)) {
+		char *s = type_str(expr_type);
+		semantic_error(scope, as_expr(node), "can't cast from %s\n", s);
+		free(s);
+		return -1;
+	}
+
+	if (!castable_type(type)) {
+		char *s = type_str(type);
+		type_error(scope, type, "can't cast to %s\n", s);
+		free(s);
+		return -1;
+	}
+
+	node->t = type;
+	return 0;
+}
+
+static int analyze_assign(struct state *state, struct scope *scope, struct ast *node)
+{
+	struct ast *expr = assign_expr(node);
+	if (analyze(state, scope, expr))
+		return -1;
+
+	struct ast *target = assign_target(node);
+	if (analyze(state, scope, target))
+		return -1;
+
+
+	if (!types_match(expr->t, target->t)) {
+		type_mismatch(scope, node, target->t, expr->t);
+		return -1;
+	}
+
+	if (!is_lvalue(target)) {
+		semantic_error(scope, target, "not an lvalue");
+		return -1;
+	}
+
+	node->t = target->t;
+	return 0;
+}
+
+static int analyze_dot(struct state *state, struct scope *scope, struct ast *node)
+{
+	struct ast *expr = dot_expr(node);
+	if (analyze(state, scope, expr))
+		return -1;
+
+	struct type *type = expr->t;
+	if (type->k != TYPE_ID) {
+		char *s = type_str(type);
+		semantic_error(scope, node, "type %s does not have any members", s);
+		free(s);
+		return -1;
+	}
+
+	struct ast *def = file_scope_find_type(scope, tid_str(type));
+	if (!def) {
+		semantic_error(scope, node, "no such type: %s", tid_str(type));
+		return -1;
+	}
+
+	if (def->k != AST_STRUCT_DEF) {
+		semantic_error(scope, node, "not a struct type: %s", tid_str(type));
+		return -1;
+	}
+
+	struct ast *member = scope_find_symbol(def->scope, dot_id(node));
+	if (!member) {
+		semantic_error(scope, node, "no such member: %s", dot_id(node));
+		return -1;
+	}
+
+	node->t = member->t;
+	return 0;
+}
+
+static int analyze_sizeof(struct state *state, struct scope *scope, struct ast *node)
+{
+	if (analyze_type(state, scope, sizeof_type(node)))
+		return -1;
+
+	/* hmm, no built-in size_t */
+	node->t = tgen_type(TYPE_U64, NULL, NULL, node->loc);
+	return 0;
+}
+
+static int analyze_arr(struct state *state, struct scope *scope, struct ast *node)
+{
+	struct ast *base = arr_base(node);
+	if (analyze(state, scope, base))
+		return -1;
+
+	if (base->t->k != TYPE_ARR) {
+		char *s = type_str(base->t);
+		semantic_error(scope, base, "expected array type, got %s", s);
+		free(s);
+		return -1;
+	}
+
+	struct ast *idx = arr_idx(node);
+	if (analyze(state, scope, idx))
+		return -1;
+
+	if (!is_int_type(idx->t->k)) {
+		char *s = type_str(idx->t);
+		semantic_error(scope, idx, "expected int type, got %s", s);
+		free(s);
+		return -1;
+	}
+
+	node->t = tarr_base(base->t);
+	return 0;
+}
+
+static int analyze_nil_check(struct state *state, struct scope *scope, struct ast *node)
+{
+	struct ast *expr = nil_check_expr(node);
+	if (analyze(state, scope, expr))
+		return -1;
+
+	if (!is_ptr_type(expr->t->k)) {
+		char *s = type_str(expr->t);
+		semantic_error(scope, expr, "expected ptr type, got %s", s);
+		free(s);
+		return -1;
+	}
+
+	if (analyze(state, scope, nil_check_body(node)))
+		return -1;
+
+	struct ast *var = nil_check_ref(node);
+	struct type *base = tptr_base(expr->t);
+	struct type *ref = tgen_ref(clone_type(base), node->loc);
+	if (!var_type(var))
+		var_type(var) = ref;
+
+	if (analyze(state, scope, var))
+		return -1;
+
+	if (!types_match(ref, var->t)) {
+		type_mismatch(scope, var, ref, var->t);
+		return -1;
+	}
+
+	node->t = tgen_void(node->loc);
+	return 0;
+}
+
+static int analyze_forget(struct state *state, struct scope *scope, struct ast *node)
+{
+	struct ast *def = file_scope_find_symbol(scope, forget_id(node));
+	if (!def) {
+		semantic_error(scope, node, "no such symbol");
+		return -1;
+	}
+
+	node->t = tgen_void(node->loc);
+	return 0;
+}
+
 static int analyze(struct state *state, struct scope *scope, struct ast *node)
 {
 	if (!node)
@@ -502,9 +854,32 @@ static int analyze(struct state *state, struct scope *scope, struct ast *node)
 	case AST_ID: ret = analyze_id(state, scope, node); break;
 	case AST_IF: ret = analyze_if(state, scope, node); break;
 
+	case AST_NIL_CHECK: ret = analyze_nil_check(state, scope, node); break;
+
 	case AST_CONST_INT: ret = analyze_int(state, scope, node); break;
 	case AST_CONST_STR: ret = analyze_str(state, scope, node); break;
 
+	case AST_INSTANCE: ret = analyze_instance(state, scope, node); break;
+	case AST_TEMPLATE: ret = analyze_template(state, scope, node); break;
+
+	case AST_STRUCT_DEF: ret = analyze_struct(state, scope, node); break;
+	case AST_CONSTRUCT: ret = analyze_construct(state, scope, node); break;
+
+	case AST_SIZEOF: ret = analyze_sizeof(state, scope, node); break;
+	case AST_NIL: ret = analyze_nil(state, scope, node); break;
+	case AST_AS: ret = analyze_as(state, scope, node); break;
+
+	case AST_ASSIGN: ret = analyze_assign(state, scope, node); break;
+	case AST_ARR: ret = analyze_arr(state, scope, node); break;
+	case AST_DOT: ret = analyze_dot(state, scope, node); break;
+
+	case AST_FORGET: ret = analyze_forget(state, scope, node); break;
+
+	case AST_TRAIT_DEF:
+		node->t = tgen_void(node->loc);
+		ret = 0;
+		break;
+
 	case AST_EMPTY:
 		node->t = tgen_void(node->loc);
 		ret = 0;
@@ -548,39 +923,61 @@ static int analyze_type(struct state *state, struct scope *scope,
 		return -1;
 
 	/* temporary */
-	if (type->k != TYPE_ID)
+	if (!type->id)
 		return 0;
 
 	char *id = type->id;
 
-	if (strcmp(id, "i8") == 0)
+	/* handle primitives */
+	if (strcmp(id, "i8") == 0) {
 		type->k = TYPE_I8;
+		return 0;
+	}
 
-	else if (strcmp(id, "u8") == 0)
+	if (strcmp(id, "u8") == 0) {
 		type->k = TYPE_U8;
+		return 0;
+	}
 
-	else if (strcmp(id, "i16") == 0)
+	if (strcmp(id, "i16") == 0) {
 		type->k = TYPE_I16;
+		return 0;
+	}
 
-	else if (strcmp(id, "u16") == 0)
+	if (strcmp(id, "u16") == 0) {
 		type->k = TYPE_U16;
+		return 0;
+	}
 
-	else if (strcmp(id, "i32") == 0)
+	if (strcmp(id, "i32") == 0) {
 		type->k = TYPE_I32;
+		return 0;
+	}
 
-	else if (strcmp(id, "u32") == 0)
+	if (strcmp(id, "u32") == 0) {
 		type->k = TYPE_U32;
+		return 0;
+	}
 
-	else if (strcmp(id, "i64") == 0)
+	if (strcmp(id, "i64") == 0) {
 		type->k = TYPE_I64;
+		return 0;
+	}
 
-	else if (strcmp(id, "u64") == 0)
+	if (strcmp(id, "u64") == 0) {
 		type->k = TYPE_U64;
-	else {
-		internal_error("unhandled type id: %s", id);
-		abort();
+		return 0;
 	}
 
+	/* check for user-defined types */
+	struct ast *def = file_scope_find_type(scope, id);
+	if (!def) {
+		type_error(scope, type, "no such type: %s", id);
+		return -1;
+	}
+
+	/* don't change type->k since we might want to check up on this again
+	 * later */
 	return 0;
 }
 
@@ -609,27 +1006,39 @@ static int copy_scope(bool reexport, struct scope *to, struct scope *from)
 			return -1;
 	}
 
-	foreach(visible, symbol, &from->types) {
-		struct ast *def = symbol->data;
+	foreach(visible, type, &from->types) {
+		struct ast *def = type->data;
 		if (!reexport && def->scope != from)
 			continue;
 
 		if (!ast_flags(def, AST_FLAG_PUBLIC))
 			continue;
 
-		if (scope_add_symbol(to, def))
+		if (scope_add_type(to, def))
 			return -1;
 	}
 
-	foreach(visible, symbol, &from->traits) {
-		struct ast *def = symbol->data;
+	foreach(visible, trait, &from->traits) {
+		struct ast *def = trait->data;
 		if (!reexport && def->scope != from)
 			continue;
 
 		if (!ast_flags(def, AST_FLAG_PUBLIC))
 			continue;
 
-		if (scope_add_symbol(to, def))
+		if (scope_add_trait(to, def))
+			return -1;
+	}
+
+	foreach(visible, template, &from->templates) {
+		struct ast *def = template->data;
+		if (!reexport && def->scope != from)
+			continue;
+
+		if (!ast_flags(def, AST_FLAG_PUBLIC))
+			continue;
+
+		if (scope_add_template(to, def))
 			return -1;
 	}
 
@@ -677,9 +1086,10 @@ static struct type *fwd_type_kind(fwd_type_t type)
 	switch (type) {
 	case FWD_VOID: return tgen_void(NULL_LOC());
 	case FWD_I64: return tgen_type(TYPE_I64, NULL, NULL, NULL_LOC());
+	case FWD_U64: return tgen_type(TYPE_U64, NULL, NULL, NULL_LOC());
 	case FWD_PTR: {
-		struct type *base = tgen_void(NULL_LOC());
-		return tgen_ptr(base, NULL_LOC());
+		/* hack? */
+		return tgen_nil(NULL_LOC());
 	}
 
 	default:
@@ -697,20 +1107,42 @@ int fwd_register(struct fwd_state *state, const char *name, fwd_extern_t func, f
 
 	va_list args;
 	va_start(args, rtype);
+
+	size_t idx = 0;
 	while (1) {
 		fwd_type_t type = va_arg(args, enum fwd_type);
 		if (type == FWD_END)
 			break;
 
-		struct ast *new = gen_var(strdup("arg"), fwd_type_kind(type), NULL_LOC());
+		/* eight bytes is likely more than enough, since first three are
+		 * var, then we have four bytes for indexes and one trailing
+		 * NULL */
+		char *name = calloc(8, sizeof(char));
+		assert(name);
+
+		sprintf(name, "%s%zu", "var", idx);
+		struct ast *new = gen_var(name, fwd_type_kind(type), NULL_LOC());
 
 		if (vars)
-			vars->n = new;
-		else
-			vars = new;
+			new->n = vars;
+
+		vars = new;
+		idx++;
 	}
 	va_end(args);
 
+	/* append 'return' as a continuation */
+	if (rtype != FWD_VOID) {
+		char *name = strdup("ret");
+		struct ast *new = gen_var(name,
+				tgen_closure(fwd_type_kind(rtype), NULL_LOC()),
+				NULL_LOC());
+		if (vars)
+			new->n = vars;
+
+		vars = new;
+	}
+
 	vars = reverse_ast_list(vars);
 
 	struct ast *def = gen_proc(strdup(name), vars,
@@ -737,8 +1169,7 @@ int analyze_root(struct scope *scope, struct ast *root)
 		      break;
 
 		case AST_STRUCT_CONT:
-		      if (scope_add_chain(scope, node))
-			      return -1;
+		      abort();
 		      break;
 
 		case AST_TRAIT_DEF:
@@ -756,6 +1187,19 @@ int analyze_root(struct scope *scope, struct ast *root)
 			return -1;
 		}
 
+		case AST_TEMPLATE:
+		      if (scope_add_template(scope, node))
+			      return -1;
+		      break;
+
+		case AST_SUPERTEMPLATE:
+		      if (scope_add_template(scope, node))
+			      return -1;
+		      break;
+
+		case AST_INSTANCE:
+		      break;
+
 		default:
 		      abort();
 		}
diff --git a/src/ast.c b/src/ast.c
index 73599cb..f8b3447 100644
--- a/src/ast.c
+++ b/src/ast.c
@@ -243,6 +243,22 @@ void ast_dump(int depth, struct ast *n)
 	DUMP(AST_NOT);
 	DUMP(AST_REF);
 	DUMP(AST_DEREF);
+	DUMP(AST_NIL_CHECK);
+	DUMP(AST_BNEG);
+	DUMP(AST_SIZEOF);
+	DUMP(AST_AS);
+	DUMP(AST_ARR);
+	DUMP(AST_ASSIGN);
+	DUMP(AST_CONSTRUCTION);
+	DUMP(AST_CONSTRUCT);
+	DUMP(AST_SELF);
+	DUMP(AST_FORGET);
+	DUMP(AST_PASTE);
+	DUMP(AST_IMPLEMENTS);
+	DUMP(AST_TEMPLATE);
+	DUMP(AST_INSTANCE);
+	DUMP(AST_SUPERTEMPLATE);
+	DUMP(AST_INSTANCE_CONT);
 	DUMP(AST_CONST_INT);
 	DUMP(AST_CONST_CHAR);
 	DUMP(AST_CONST_BOOL);
@@ -320,6 +336,9 @@ struct ast *clone_ast(struct ast *n)
 	if (n->a3)
 		new->a3 = clone_ast_list(n->a3);
 
+	if (n->t2)
+		new->t2 = clone_type_list(n->t2);
+
 	/** @todo rebuild opt group? */
 
 	return new;
@@ -351,13 +370,14 @@ struct type *clone_type(struct type *type)
 		return NULL;
 
 	new->k = type->k;
-	if (type->id && !(new->id = strdup(type->id)))
-		return NULL;
+	if (type->id)
+		new->id = strdup(type->id);
 
-	if (type->t0 && !(new->t0 = clone_type_list(type->t0)))
-		return NULL;
+	if (type->t0)
+		new->t0 = clone_type_list(type->t0);
 
 	new->group = type->group;
+	new->loc = type->loc;
 	return new;
 }
 
@@ -589,6 +609,13 @@ bool types_match(struct type *a, struct type *b)
 	if (!a && b)
 		return false;
 
+	/* nil matches any kind of pointer */
+	if (is_ptr_type(a->k) && b->k == TYPE_NIL)
+		return true;
+
+	if (a->k == TYPE_NIL && is_ptr_type(b->k))
+		return true;
+
 	if (a->k != b->k)
 		return false;
 
@@ -662,6 +689,22 @@ const char *ast_str(enum ast_kind k)
 	CASE(AST_NOT);
 	CASE(AST_REF);
 	CASE(AST_DEREF);
+	CASE(AST_NIL_CHECK);
+	CASE(AST_BNEG);
+	CASE(AST_SIZEOF);
+	CASE(AST_AS);
+	CASE(AST_ARR);
+	CASE(AST_ASSIGN);
+	CASE(AST_CONSTRUCTION);
+	CASE(AST_CONSTRUCT);
+	CASE(AST_SELF);
+	CASE(AST_FORGET);
+	CASE(AST_PASTE);
+	CASE(AST_IMPLEMENTS);
+	CASE(AST_TEMPLATE);
+	CASE(AST_INSTANCE);
+	CASE(AST_SUPERTEMPLATE);
+	CASE(AST_INSTANCE_CONT);
 	CASE(AST_CONST_INT);
 	CASE(AST_CONST_CHAR);
 	CASE(AST_CONST_BOOL);
diff --git a/src/debug.c b/src/debug.c
index f3540f0..8ef4293 100644
--- a/src/debug.c
+++ b/src/debug.c
@@ -134,14 +134,27 @@ void semantic_error(struct scope *scope, struct ast *node,
 	va_end(args);
 }
 
+void type_error(struct scope *scope, struct type *type,
+                    const char *fmt, ...)
+{
+	va_list args;
+	va_start(args, fmt);
+	struct src_issue issue;
+	issue.level = SRC_ERROR;
+	issue.loc = type->loc;
+	issue.fctx = scope->fctx;
+	_issue(issue, fmt, args);
+	va_end(args);
+}
+
 void type_mismatch(struct scope *scope, struct ast *node,
                    struct type *l, struct type *r)
 {
-	const char *ls = type_str(l);
-	const char *rs = type_str(r);
+	char *ls = type_str(l);
+	char *rs = type_str(r);
 	semantic_error(scope, node, "type mismatch: %s vs %s\n", ls, rs);
-	free((void *)ls);
-	free((void *)rs);
+	free(ls);
+	free(rs);
 }
 
 void move_error(struct ast *new_use, struct ast *prev_use)
@@ -213,6 +226,16 @@ static void _type_str(FILE *f, struct type *type)
 		fprintf(f, "void");
 		break;
 
+	case TYPE_NIL:
+		fprintf(f, "nil");
+		break;
+
+	case TYPE_ARR:
+		/** @todo length? */
+		fprintf(f, "[]");
+		_type_list_str(f, tarr_base(type));
+		break;
+
 	case TYPE_PTR:
 		fprintf(f, "*");
 		_type_list_str(f, tptr_base(type));
@@ -244,16 +267,10 @@ static void _type_str(FILE *f, struct type *type)
 		_type_list_str(f, type->t0);
 		fprintf(f, ")");
 		break;
-
-	case TYPE_CONSTRUCT:
-		fprintf(f, "%s![", type->id);
-		_type_list_str(f, type->t0);
-		fprintf(f, "]");
-		break;
 	}
 }
 
-const char *type_str(struct type *t)
+char *type_str(struct type *t)
 {
 	if (!t)
 		return strdup("NULL");
diff --git a/src/lexer.l b/src/lexer.l
index 24bda93..4f6598a 100644
--- a/src/lexer.l
+++ b/src/lexer.l
@@ -38,8 +38,7 @@ INT		{HEX}|{DEC}|{OCT}|{BIN}
 HEXF		[+-]?0[xX][0-9a-fA-F]+([pP][+-]?[0-9]+)
 DECF		[+-]?[0-9]+[.]([eE]?[+-]?[0-9]+)?[fF]?
 
-ID		[_a-zA-Z][_a-zA-Z0-9]*
-APPLY		{ID}!
+ID		((<>)|[_a-zA-Z])[_a-zA-Z0-9]*
 
 STRING		\"(\\.|[^"\\])*\"
 
@@ -64,7 +63,6 @@ STRING		\"(\\.|[^"\\])*\"
 	\n {}
 }
 
-"::"		{return SCOPE;}
 "("		{return LPAREN;}
 ")"		{return RPAREN;}
 "{"		{return LBRACE;}
@@ -126,6 +124,7 @@ STRING		\"(\\.|[^"\\])*\"
 "<<"		{return LSHIFT;}
 ">>"		{return RSHIFT;}
 
+"as"		{return AS;}
 "if"		{return IF;}
 "else"		{return ELSE;}
 "nil"		{return NIL;}
@@ -138,9 +137,9 @@ STRING		\"(\\.|[^"\\])*\"
 
 "mut"		{return MUT;}
 
+"sizeof"	{return SIZEOF;}
+
 {STRING} {
-	/* seems risky, I know, but letting the parser choose when to allocate a
-	 * new string seems to help with syntax error cleanup */
 	yylval->str = strdup(yytext);
 	return STRING;
 }
@@ -155,16 +154,6 @@ STRING		\"(\\.|[^"\\])*\"
 	return ID;
 }
 
-{APPLY} {
-	/* strip trailing '!' */
-	char *s = yytext + strlen(yytext);
-	s[-1] = '\0';
-
-	yylval->str = strdup(yytext);
-	return APPLY;
-}
-
-
 [[:space:]]+	{/* skip whitespace */}
 
 . {
diff --git a/src/parser.y b/src/parser.y
index 6ec2eb2..023c10a 100644
--- a/src/parser.y
+++ b/src/parser.y
@@ -36,7 +36,6 @@
 %token <dbl> FLOAT
 %token <str> STRING
 %token <str> ID
-%token <str> APPLY
 
 %token QUESTION "?"
 %token SQUOTE "'"
@@ -70,6 +69,7 @@
 %token RBRACE "}"
 %token LBRACKET "["
 %token RBRACKET "]"
+%token AS "as"
 %token IF "if"
 %token ELSE "else"
 %token NIL "nil"
@@ -79,7 +79,6 @@
 %token IMPORT "import"
 %token ERROR "error"
 %token DOT "."
-%token SCOPE "::"
 %token FATARROW "=>"
 
 %right "[" "]"
@@ -95,19 +94,26 @@
 %left "*" "/" "%"
 %left "as" "sizeof"
 %right "'" "!" "~"
+%right ".."
 %left "." "=>" "(" ")"
-%left "::"
 
-%nterm <node> top unit proc proc_decl call closure var expr statement body
-%nterm <node> vars exprs statements closures trailing_closure
-%nterm <node> opt_vars opt_exprs opt_statements opt_trailing_closure
-%nterm <node> rev_vars rev_exprs rev_closures rev_statements
+%nterm <node> top unit proc proc_decl call closure expr statement body
+%nterm <node> exprs statements closures trailing_closure
+%nterm <node> opt_exprs opt_statements opt_trailing_closure
+%nterm <node> rev_exprs rev_closures rev_statements
 %nterm <node> let if nil unop binop construct import
 
+%nterm <node> opt_vars vars rev_vars var
+%nterm <node> opt_params params rev_params param
+
 %nterm <node> struct struct_cont trait
 %nterm <node> type_param type_params opt_type_params
 %nterm <node> behaviour behaviours opt_behaviours
 %nterm <node> member members opt_members
+%nterm <node> opt_elements elements rev_elements element
+%nterm <node> instance template supertemplate
+%nterm <node> opt_constructions constructions construction
+%nterm <node> id impl forget assign
 
 %nterm <type> type rev_types types opt_types
 
@@ -189,12 +195,29 @@ static char *strip(const char *s);
 
 %start input;
 %%
-var
+param
 	: type ID { $$ = gen_var($2, $1, src_loc(@$)); }
 
+rev_params
+	: rev_params "," param { $$ = $3; $$->n = $1; }
+	| rev_params "|" param { $$ = $3; $$->n = $1; opt_group($1, $3); }
+	| param
+
+params
+	: rev_params { $$ = reverse_ast_list($1); }
+	| rev_params "," { $$ = reverse_ast_list($1); }
+
+opt_params
+	: params
+	| {$$ = NULL;}
+
+
+var
+	: param
+	| ID { $$ = gen_var($1, NULL, src_loc(@$)); }
+
 rev_vars
 	: rev_vars "," var { $$ = $3; $$->n = $1; }
-	| rev_vars "|" var { $$ = $3; $$->n = $1; opt_group($1, $3); }
 	| var
 
 vars
@@ -206,13 +229,13 @@ opt_vars
 	| {$$ = NULL;}
 
 proc
-	: ID "(" opt_vars ")" body {
-		$$ = gen_proc($[ID], $[opt_vars], NULL, $[body], src_loc(@$));
+	: ID "(" opt_params ")" body {
+		$$ = gen_proc($[ID], $[opt_params], NULL, $[body], src_loc(@$));
 	}
 
 proc_decl
-	: ID "(" opt_vars ")" ";" {
-		$$ = gen_proc($[ID], $[opt_vars], NULL, NULL, src_loc(@$));
+	: ID "(" opt_params ")" ";" {
+		$$ = gen_proc($[ID], $[opt_params], NULL, NULL, src_loc(@$));
 	}
 
 binop
@@ -229,17 +252,20 @@ binop
 	| expr ">=" expr { $$ = gen_comparison(AST_GE, $1, $3, src_loc(@$));  }
 	| expr "!=" expr { $$ = gen_comparison(AST_NE, $1, $3, src_loc(@$));  }
 	| expr "==" expr { $$ = gen_comparison(AST_EQ, $1, $3, src_loc(@$));  }
+	| id "~" id { $$ = gen_paste($1, $3, src_loc(@$)); }
 
 unop
 	: "-" expr { $$ = gen_unop(AST_NEG, $2, src_loc(@$));  }
-	| "!" expr { $$ = gen_unop(AST_LNOT, $2, src_loc(@$));  }
+	| "!" expr { $$ = gen_unop(AST_LNOT, $2, src_loc(@$)); }
+	| "~" expr { $$ = gen_unop(AST_BNEG, $2, src_loc(@$)); }
 
 type
-	: ID { $$ = tgen_id($[ID], src_loc(@$)); }
-	| APPLY "[" opt_types "]" {
-		$$ = tgen_construct($[APPLY], $[opt_types], src_loc(@$));
-	}
+	: ID { $$ = tgen_id($1, src_loc(@$)); }
 	| "(" opt_types ")" { $$ = tgen_closure($2, src_loc(@$)); }
+	| "[" "]" type {
+		/* TODO static sizes? */
+		$$ = tgen_arr($3, NULL, src_loc(@$));
+	}
 	| "&&" type {
 		if ($2->k == TYPE_CLOSURE) {
 			$$ = $2; $$->k = TYPE_PURE_CLOSURE;
@@ -276,26 +302,43 @@ opt_types
 	: types
 	| { $$ = NULL; }
 
-construct
-	: APPLY "{" opt_exprs "}" {
-		$$ = gen_init($[APPLY], NULL, $[opt_exprs], src_loc(@$));
+construction
+	: expr "=>" ID {
+		$$ = gen_construction($3, $1, src_loc(@$));
 	}
-	| APPLY "[" opt_types "]" "{" opt_exprs "}" {
-		$$ = gen_init($[APPLY], $[opt_types], $[opt_exprs], src_loc(@$));
+
+constructions
+	: constructions "," construction { $$ = $3; $$->n = $1; }
+	| construction
+
+opt_constructions
+	: constructions
+	| { $$ = NULL; }
+
+construct
+	: "(" opt_constructions ")" ID {
+		$$ = gen_construct($4, $2, src_loc(@$));
 	}
 
+id
+	: ID { $$ = gen_id($1, src_loc(@$)); }
+
 expr
-	: expr "." ID { $$ = gen_dot($3, $1, src_loc(@$)); }
+	: "sizeof" "(" type ")" { $$ = gen_sizeof($3, src_loc(@$)); }
+	| expr "." ID { $$ = gen_dot($3, $1, src_loc(@$)); }
+	| expr "[" expr "]" { $$ = gen_arr($1, $3, src_loc(@$)); }
 	| STRING { $$ = gen_const_str(strip($1), src_loc(@$)); }
 	| FLOAT { $$ = gen_const_float($1, src_loc(@$)); }
 	| BOOL { $$ = gen_const_bool($1, src_loc(@$)); }
 	| CHAR { $$ = gen_const_char($1, src_loc(@$)); }
 	| INT { $$ = gen_const_int($1, src_loc(@$)); }
-	| ID { $$ = gen_id($1, src_loc(@$)); }
+	| "*" { $$ = gen_nil(src_loc(@$)); }
 	| "(" expr ")" { $$ = $2; }
 	| expr "&" { $$ = gen_ref($1, src_loc(@$)); }
 	| expr "*" { $$ = gen_deref($1, src_loc(@$)); }
+	| expr "as" type { $$ = gen_as($1, $3, src_loc(@$)); }
 	| construct
+	| id
 	| binop
 	| unop
 
@@ -369,12 +412,24 @@ if
 	| "if" expr body "else" if { $$ = gen_if($2, $3, $5, src_loc(@$)); }
 
 nil
-	: "nil" ID body "=>" var {
-		$$ = gen_nil($2, $3, $5, src_loc(@$));
+	: "nil" expr body "=>" var ";" {
+		$$ = gen_nil_check($2, $3, $5, src_loc(@$));
+	}
+
+forget
+	: "nil" ID ";" {
+		$$ = gen_forget($2, src_loc(@$));
+	}
+
+assign
+	: expr "=" expr ";" {
+		$$ = gen_assign($1, $3, src_loc(@$));
 	}
 
 statement
 	: call
+	| forget
+	| assign
 	| body
 	| let
 	| nil
@@ -398,9 +453,9 @@ body
 	}
 
 behaviour
-	: APPLY ";" { $$ = gen_trait_apply($1, src_loc(@$)); }
-	| proc_decl ";"
+	: proc_decl
 	| proc
+	| impl
 
 behaviours
 	: behaviours behaviour { $$ = $1; $1->n = $2; }
@@ -410,16 +465,18 @@ opt_behaviours
 	: behaviours
 	| { $$ = NULL; }
 
+impl
+	: ID "!" { $$ = gen_implements($1, src_loc(@$)); }
+
 member
-	: var ";"
-	| behaviour
+	: param
 
 members
-	: members member { $$ = $1; $1->n = $2; }
+	: members ";" member { $$ = $3; $$->n = $1; }
 	| member
 
 opt_members
-	: members
+	: members ";"
 	| { $$ = NULL; }
 
 type_param
@@ -438,19 +495,53 @@ opt_type_params
 	: type_params
 	| { $$ = NULL; }
 
+element
+	: proc
+	| struct
+	| impl
+	| var ";"
+
+rev_elements
+	: rev_elements element { $$ = $2; $$->n = $1; }
+	| element
+
+elements
+	: rev_elements { $$ = reverse_ast_list($1); }
+
+opt_elements
+	: elements
+	| { $$ = NULL; }
+
+template
+	: ID "[" opt_type_params "]" "(" opt_vars ")" "{" opt_elements "}" {
+		$$ = gen_template($1, $3, $6, $9, src_loc(@$));
+	}
+
+supertemplate
+	: ID "[" opt_type_params "]" "(" opt_vars ")" "="
+	  id "[" opt_types "]" "(" opt_exprs ")" "{" opt_elements "}" {
+		struct ast *pseudoinst = gen_instance(NULL, $9, $11, $14, src_loc(@$));
+		$$ = gen_supertemplate($1, $3, $6, pseudoinst, $17, src_loc(@$));
+	  }
+
 struct
-	: ID "[" opt_type_params "]" "{" opt_members "}" {
-		$$ = gen_struct($1, $3, $6, src_loc(@$));
+	: ID "{" opt_members "}" {
+		$$ = gen_struct($1, $3, src_loc(@$));
 	}
 
 struct_cont
-	: "continue" ID "[" opt_type_params "]" "{" opt_behaviours "}" {
-		$$ = gen_struct_cont($2, $4, $7, src_loc(@$));
+	: "continue" ID "{" opt_behaviours "}" {
+		$$ = gen_instance_cont($2, $4, src_loc(@$));
 	}
 
 trait
-	: ID "{" opt_behaviours "}" {
-		$$ = gen_trait($1, $3, src_loc(@$));
+	: ID "=" "{" opt_behaviours "}" {
+		$$ = gen_trait($1, $4, src_loc(@$));
+	}
+
+instance
+	: ID "=" id "[" opt_types "]" "(" opt_exprs ")" {
+		$$ = gen_instance($1, $3, $5, $8, src_loc(@$));
 	}
 
 import
@@ -464,11 +555,17 @@ top
 	| struct_cont
 	| import
 	| trait
-	| "pub" proc        { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); }
-	| "pub" struct      { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); }
-	| "pub" struct_cont { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); }
-	| "pub" import      { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); }
-	| "pub" trait       { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); }
+	| instance
+	| template
+	| supertemplate
+	| "pub" proc          { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); }
+	| "pub" struct        { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); }
+	| "pub" struct_cont   { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); }
+	| "pub" import        { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); }
+	| "pub" trait         { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); }
+	| "pub" instance      { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); }
+	| "pub" template      { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); }
+	| "pub" supertemplate { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); }
 	| error {
 	    $$ = gen_empty(src_loc(@$));
 	    parser->failed = true;
diff --git a/src/rewrite.c b/src/rewrite.c
new file mode 100644
index 0000000..e3cea01
--- /dev/null
+++ b/src/rewrite.c
@@ -0,0 +1,96 @@
+#include <fwd/rewrite.h>
+#include <stddef.h>
+#include <stdlib.h>
+
+struct type_helper {
+	char *orig;
+	char *new;
+};
+
+/* types are simple enough (for now) that this works fine */
+static int rewrite_type_ids(struct type *type, char *orig, char *new)
+{
+	if (type->k == TYPE_ID && strcmp(type->id, orig) == 0) {
+		char *r = strdup(new);
+		free(type->id);
+		type->id = r;
+	}
+
+	if (type->t0 && rewrite_type_ids(type->t0, orig, new))
+		return -1;
+
+	if (type->n && rewrite_type_ids(type->n, orig, new))
+		return -1;
+
+	return 0;
+}
+
+static int rewrite_type_visit(struct ast *node, struct type_helper *helper)
+{
+	if (node->t2)
+		return rewrite_type_ids(node->t2, helper->orig, helper->new);
+
+	return 0;
+}
+
+int rewrite_types(struct ast *node, char *orig, char *new)
+{
+	struct type_helper helper = {.orig = orig, .new = new};
+	return ast_visit((ast_callback_t)rewrite_type_visit, NULL, node, &helper);
+}
+
+/* not the fastest thing in the world but should work well enough for now */
+static char *rewrite_hole(char *old, char *new)
+{
+	/* skip "<>" */
+	size_t on = strlen(old) - 2;
+	size_t nn = strlen(new);
+
+	/* +1 for null terminator */
+	char *r = malloc(on + nn + 1);
+
+	memcpy(r, new, nn);
+
+	/* +2 to skip "<>", +1 for null terminator */
+	memcpy(r + nn, old + 2, on + 1);
+	return r;
+}
+
+static int rewrite_type_holes(struct type *type, char *new)
+{
+	if (type->id && strncmp(type->id, "<>", 2) == 0) {
+		char *r = rewrite_hole(type->id, new);
+		free(type->id);
+		type->id = r;
+	}
+
+	if (type->t0 && rewrite_type_holes(type->t0, new))
+		return -1;
+
+	if (type->n && rewrite_type_holes(type->n, new))
+		return -1;
+
+	return 0;
+}
+
+static int rewrite_holes_visit(struct ast *node, char *new)
+{
+	if (node->k == AST_CONST_STR)
+		return 0;
+
+	if (node->s && strncmp(node->s, "<>", 2) == 0) {
+		char *r = rewrite_hole(node->s, new);
+		free(node->s);
+		node->s = r;
+	}
+
+	if (node->t2 && rewrite_type_holes(node->t2, new))
+		return -1;
+
+	return 0;
+}
+
+int rewrite_holes(struct ast *node, char *new)
+{
+	return ast_visit((ast_callback_t)rewrite_holes_visit, NULL, node, new);
+}
diff --git a/src/scope.c b/src/scope.c
index 485b3a6..e49b828 100644
--- a/src/scope.c
+++ b/src/scope.c
@@ -30,8 +30,9 @@ struct scope *create_scope()
 
 	scope->number = counter++;
 	scope->symbols = visible_create(16); /* arbitrary number */
-	scope->traits = visible_create(1);
-	scope->types = visible_create(1);
+	scope->templates = visible_create(0);
+	scope->traits = visible_create(0);
+	scope->types = visible_create(0);
 	scope->mods = mod_vec_create(0);
 	return scope;
 }
@@ -47,12 +48,13 @@ void destroy_scope(struct scope *scope)
 	}
 
 	foreach(mod_vec, m, &scope->mods) {
-		dlclose(m);
+		dlclose(*m);
 	}
 
 	mod_vec_destroy(&scope->mods);
 
 	visible_destroy(&scope->symbols);
+	visible_destroy(&scope->templates);
 	visible_destroy(&scope->traits);
 	visible_destroy(&scope->types);
 
@@ -108,7 +110,7 @@ struct ast *file_scope_find_symbol(struct scope *scope, char *id)
 int scope_add_type(struct scope *scope, struct ast *type)
 {
 	assert(type->k == AST_STRUCT_DEF);
-	struct ast **exists = visible_insert(&scope->symbols, type->s, type);
+	struct ast **exists = visible_insert(&scope->types, type->s, type);
 	if (!exists) {
 		internal_error("failed inserting type into scope");
 		return -1;
@@ -123,42 +125,6 @@ int scope_add_type(struct scope *scope, struct ast *type)
 	return 0;
 }
 
-int scope_add_chain(struct scope *scope, struct ast *type)
-{
-	assert(type->k == AST_STRUCT_CONT);
-	struct ast *exists = file_scope_find_type(scope, type->s);
-	if (!exists) {
-		semantic_error(scope, type, "no previous definition");
-		return -1;
-	}
-
-	assert(exists->k == AST_STRUCT_DEF || exists->k == AST_STRUCT_CONT);
-	if (ast_flags(exists, AST_FLAG_PUBLIC) || !ast_flags(type, AST_FLAG_PUBLIC)) {
-		type->chain = exists;
-		struct ast **v = visible_insert(&scope->types, type->s, type);
-		if (!v) {
-			internal_error("failed inserting type into chain");
-			return -1;
-		}
-
-		/* overwrite root */
-		if (*v != type)
-			*v = type;
-
-		return 0;
-	}
-
-	struct ast *next = exists->chain;
-	while (next->k == AST_STRUCT_CONT && !ast_flags(next, AST_FLAG_PUBLIC)) {
-		exists = next;
-		next = next->chain;
-	}
-
-	exists->chain = type;
-	type->chain = exists;
-	return 0;
-}
-
 struct ast *scope_find_type(struct scope *scope, char *id)
 {
 	struct ast **v = visible_find(&scope->types, id);
@@ -183,7 +149,7 @@ struct ast *file_scope_find_type(struct scope *scope, char *id)
 int scope_add_trait(struct scope *scope, struct ast *trait)
 {
 	assert(trait->k == AST_TRAIT_DEF);
-	struct ast **exists = visible_insert(&scope->symbols, trait->s, trait);
+	struct ast **exists = visible_insert(&scope->traits, trait->s, trait);
 	if (!exists) {
 		internal_error("failed inserting trait into scope");
 		return -1;
@@ -197,6 +163,7 @@ int scope_add_trait(struct scope *scope, struct ast *trait)
 
 	return 0;
 }
+
 struct ast *scope_find_trait(struct scope *scope, char *id)
 {
 	struct ast **v = visible_find(&scope->traits, id);
@@ -218,6 +185,44 @@ struct ast *file_scope_find_trait(struct scope *scope, char *id)
 	return file_scope_find_trait(scope->parent, id);
 }
 
+int scope_add_template(struct scope *scope, struct ast *template)
+{
+	struct ast **exists = visible_insert(&scope->templates, template->s, template);
+	if (!exists) {
+		internal_error("failed inserting template into scope");
+		return -1;
+	}
+
+	if (*exists != template) {
+		semantic_error(scope, template, "template redefined");
+		semantic_info(scope, *exists, "previously here");
+		return -1;
+	}
+
+	return 0;
+}
+
+struct ast *scope_find_template(struct scope *scope, char *id)
+{
+	struct ast **v = visible_find(&scope->templates, id);
+	if (!v)
+		return NULL;
+
+	return *v;
+}
+
+struct ast *file_scope_find_template(struct scope *scope, char *id)
+{
+	if (!scope)
+		return NULL;
+
+	struct ast *found = scope_find_template(scope, id);
+	if (found)
+		return found;
+
+	return file_scope_find_template(scope->parent, id);
+}
+
 void scope_add_scope(struct scope *parent, struct scope *child)
 {
 	assert(parent);