initial generics for structs

+ Likely still very much full of bugs

6 files changed, 387 insertions, 44 deletions

diff --git a/src/actualize.c b/src/actualize.c
index 4fd6fc6..591333a 100644
--- a/src/actualize.c
+++ b/src/actualize.c
@@ -465,7 +465,7 @@ static struct ast *analyze_type_expand(struct scope *scope,
 	return body;
 }
 
-static int implements_trait(struct ast *body, char *id)
+static int has_trait(struct ast *body, char *id)
 {
 	foreach_node(n, body) {
 		/* traits don't currently take generic parameters I guess? */
@@ -509,8 +509,18 @@ int analyze_root(struct scope *scope, struct ast *tree)
 
 static int structs_match(struct type *a, struct type *b)
 {
-	/* dunno, let's go with this for now */
-	return a->d == b->d;
+	if (a->d != b->d)
+		return 0;
+
+	return type_lists_match(tstruct_params(a), tstruct_params(b));
+}
+
+static int traits_match(struct type *a, struct type *b)
+{
+	if (a->d != b->d)
+		return 0;
+
+	return type_lists_match(ttrait_params(a), ttrait_params(b));
 }
 
 int types_match(struct type *a, struct type *b)
@@ -528,6 +538,9 @@ int types_match(struct type *a, struct type *b)
 	if (is_void(a) && is_void(b))
 		return 1;
 
+	if (a->k == TYPE_TRAIT)
+		return traits_match(a, b);
+
 	if (a->k == TYPE_STRUCT)
 		return structs_match(a, b);
 
@@ -544,6 +557,20 @@ int types_match(struct type *a, struct type *b)
 	return 0;
 }
 
+int type_lists_match(struct type *a, struct type *b)
+{
+	while (a && b) {
+		if (!types_match(a, b))
+			return 0;
+
+		a = a->n;
+		b = b->n;
+	}
+
+	/* if we succesfully checked all types, lists match */
+	return a == NULL && b == NULL;
+}
+
 static int _replace_id(struct ast *node, void *data)
 {
 	if (!node)
@@ -580,6 +607,180 @@ static int replace_id(struct ast *body, struct ast *id,
 	return ast_visit(_replace_id, NULL, body, pair);
 }
 
+static int implements(struct type *trait, struct type *type)
+{
+	assert(type->d);
+	struct ast *def = type->d;
+
+	assert(trait->d);
+	struct ast *trait_def = trait->d;
+	assert(trait_def->k == AST_TRAIT_DEF);
+
+	/* empty traits are implemented implicitly */
+	if (!trait_body(trait_def))
+		return 1;
+
+	foreach_node(n, def) {
+		if (n->k != AST_TYPE_EXPAND)
+			continue;
+
+		if (!same_id(type_expand_id(n), trait_id(trait_def)))
+			continue;
+
+		assert(n->t);
+		if (n->t->d != trait_def)
+			continue;
+
+		return 1;
+	}
+
+	/** @todo look up possible continuations for type */
+	return 0;
+}
+
+static int should_implement_list(struct scope *scope, struct ast *params, struct src_loc loc, struct type *types)
+{
+	while (params && types) {
+		assert(params->k == AST_VAR_DEF);
+		struct type *t = var_type(params);
+		if (!implements(t, types)) {
+			char *type1 = type_str(types);
+			char *type2 = type_str(t);
+			type_error(scope->fctx, types,
+					"%s does not implement %s",
+					type1,
+					type2);
+			free(type1);
+			free(type2);
+			return 0;
+		}
+
+		params = params->n;
+		types = types->n;
+	}
+
+	if (params == NULL && types == NULL)
+		return 1;
+
+	if (params != NULL) {
+		loc_error(scope->fctx, loc,
+				"too few type params");
+		return 0;
+	}
+
+	if (types != NULL) {
+		loc_error(scope->fctx, loc,
+				"too many type params");
+		return 0;
+	}
+
+	return 0;
+}
+
+static int _reset(struct ast *node, void *data)
+{
+	UNUSED(data);
+	ast_clear_flags(node, AST_FLAG_INIT | AST_FLAG_ACTUAL);
+	/* clear type info */
+	node->t = NULL;
+	return 0;
+}
+
+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)
+{
+	/* we're getting expanded so remove our params to avoid redefining them
+	 * later */
+	if (expd->k == AST_STRUCT_DEF)
+		struct_params(expd) = NULL;
+	else
+		trait_params(expd) = NULL;
+
+	assert(expd->scope->parent);
+	struct scope *p = expd->scope->parent;
+
+	reset(expd);
+	
+	foreach_node(n, params) {
+		struct ast *p = clone_ast(n);
+		var_type(p) = clone_type(types);
+
+		if (expd->k == AST_STRUCT_DEF)
+			ast_append(&struct_params(expd), p);
+		else
+			ast_append(&trait_params(expd), p);
+
+		types = types->n;
+	}
+
+	/* if our trait system works, would theoretically already know that this
+	 * 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);
+	assert(ret == 0);
+	return ret;
+}
+
+static struct ast *maybe_expand_struct(struct scope *scope, struct ast *def, struct src_loc loc, struct type *args)
+{
+	assert(def->k == AST_STRUCT_DEF);
+	if (struct_params(def) == NULL) {
+		if (args == NULL)
+			return def;
+
+		loc_error(scope->fctx, loc,
+				"passing types to non-generic struct %s",
+				struct_id(def));
+		return NULL;
+	}
+
+	struct ast *exists = file_scope_find_expd_struct(scope, def, args);
+	if (exists)
+		return exists;
+
+	if (!should_implement_list(scope, struct_params(def), loc, args))
+		return NULL;
+
+	struct ast *expd = clone_ast(def);
+	if (expand_type(expd, struct_params(def), args))
+		return NULL;
+
+	scope_add_expd_struct(scope, def, args, expd);
+	return expd;
+}
+
+static struct ast *maybe_expand_trait(struct scope *scope, struct ast *def, struct src_loc loc, struct type *args)
+{
+	assert(def->k == AST_TRAIT_DEF);
+	if (trait_params(def) == NULL) {
+		if (args != NULL) {
+			loc_error(scope->fctx, loc,
+					"passing types to non-generic trait %s",
+					trait_id(def));
+			return NULL;
+		}
+
+		return def;
+	}
+
+	loc_error(scope->fctx, loc, "unimplemented trait expansion");
+	return NULL;
+}
+
+static struct ast *maybe_expand_type(struct scope *scope, struct ast *def, struct src_loc loc, struct type *args)
+{
+	assert(def->k == AST_STRUCT_DEF || def->k == AST_TRAIT_DEF);
+	if (def->k == AST_STRUCT_DEF)
+		return maybe_expand_struct(scope, def, loc, args);
+	else
+		return maybe_expand_trait(scope, def, loc, args);
+}
+
 static int actualize_macro_def(struct act_state *state,
                                struct scope *scope, struct ast *n)
 {
@@ -822,7 +1023,7 @@ static int actualize_proc_sign(struct scope *scope, struct ast *proc)
 			continue;
 		}
 
-		type_append(callable_ptypes(callable), p->t);
+		type_append(&callable_ptypes(callable), p->t);
 	}
 
 	set_type(proc, callable);
@@ -860,7 +1061,7 @@ static int actualize_proc(struct act_state *state,
 		struct ast *body = proc_body(proc);
 		struct ast *r = gen_return(NULL, NULL, NULL_LOC());
 		r->scope = body->scope;
-		ast_append(block_body(body), r);
+		ast_append(&block_body(body), r);
 	}
 	else if (ast_block_last(proc_body(proc))->k != AST_RETURN) {
 		/* TODO: something more sophisticated than this */
@@ -1005,8 +1206,11 @@ static int actualize_var(struct act_state *state,
 	if (init && actualize_list(state, scope, init))
 		return -1;
 
-	if (type && actualize_type_list(state, scope, type))
-		return -1;
+	if (type) {
+		type = clone_type(type);
+		if (actualize_type_list(state, scope, type))
+			return -1;
+	}
 
 	if (init && type) {
 		/* make sure the asked type and the actualized types match */
@@ -1182,6 +1386,29 @@ static int actualize_ttrait(struct act_state *state, struct scope *scope,
 	return 0;
 }
 
+static int actualize_tconstruct(struct act_state *state,
+		struct scope *scope,
+		struct type *t)
+{
+	assert(t->k == TYPE_CONSTRUCT);
+	struct ast *d = file_scope_find_type(scope, construct_id(t));
+	if (!d) {
+		type_error(scope->fctx, t, "no such type");
+		return -1;
+	}
+
+	if (actualize_type_list(state, scope, construct_atypes(t)))
+		return -1;
+
+	d = maybe_expand_type(scope, d, t->loc, construct_atypes(t));
+	if (!d)
+		return -1;
+
+	replace_type(t, d->t);
+	t->d = d;
+	return 0;
+}
+
 static int actualize_type(struct act_state *state,
                           struct scope *scope,
                           struct type *t)
@@ -1203,6 +1430,7 @@ static int actualize_type(struct act_state *state,
 	case TYPE_CALLABLE: return actualize_callable(state, scope, t);
 	case TYPE_STRUCT: return actualize_tstruct(state, scope, t);
 	case TYPE_TRAIT: return actualize_ttrait(state, scope, t);
+	case TYPE_CONSTRUCT: return actualize_tconstruct(state, scope, t);
 	case TYPE_VOID: return 0; /* void is by default actualized */
 
 	default:
@@ -1367,6 +1595,7 @@ static int actualize_alias(struct act_state *state, struct scope *scope,
 		return -1;
 	}
 
+	alias->t = alias_type(alias);
 	ast_set_flags(alias, AST_FLAG_ACTUAL);
 	return 0;
 }
@@ -1722,7 +1951,7 @@ static int actualize_trait(struct act_state *state, struct scope *scope,
 			continue;
 
 		/* don't re-expand already implemented traits */
-		if (implements_trait(trait_body(node), type_expand_id(n))) {
+		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;
@@ -1815,12 +2044,30 @@ static int actualize_struct(struct act_state *state,
 	else
 		node->t = tgen_struct(id, node, node->loc);
 
+	/* iterate over types and make aliases to them */
+	foreach_node(n, struct_params(node)) {
+		char *id = var_id(n);
+		struct type *type = var_type(n);
+		struct act_state type_state = {0};
+		if (actualize_type(&type_state, scope, type))
+			return -1;
+
+		type_append(&tstruct_params(node->t), type);
+
+		struct ast *alias = gen_alias(strdup(id), clone_type(type), n->loc);
+		if (analyze_visibility(struct_scope, alias))
+			return -1;
+
+		struct act_state state = {0};
+		if (actualize(&state, struct_scope, alias))
+			return -1;
+	}
 
 	foreach_node(n, struct_body(node)) {
 		if (n->k != AST_TYPE_EXPAND)
 			continue;
 
-		if (implements_trait(struct_body(node), type_expand_id(n))) {
+		if (has_trait(struct_body(node), type_expand_id(n))) {
 			n->k = AST_EMPTY;
 			continue;
 		}
@@ -1969,6 +2216,7 @@ static int init_sort(const struct init_helper *a, const struct init_helper *b)
 	return strcmp(a->id, b->id);
 }
 
+
 static int actualize_init(struct act_state *state,
                           struct scope *scope, struct ast *node)
 {
@@ -1980,6 +2228,13 @@ static int actualize_init(struct act_state *state,
 		return -1;
 	}
 
+	if (actualize_type_list(state, scope, init_args(node)))
+		return -1;
+
+	def = maybe_expand_type(scope, def, node->loc, init_args(node));
+	if (!def)
+		return -1;
+
 	struct vec init_args = vec_create(sizeof(struct init_helper));
 	struct vec struct_members = vec_create(sizeof(struct init_helper));
 
diff --git a/src/ast.c b/src/ast.c
index d734252..890196b 100644
--- a/src/ast.c
+++ b/src/ast.c
@@ -153,9 +153,14 @@ unsigned ast_flags(struct ast *node, enum ast_flags flags)
 	return node->f & flags;
 }
 
-void ast_append(struct ast *list, struct ast *elem)
+void ast_append(struct ast **list, struct ast *elem)
 {
-	struct ast *cur = list;
+	struct ast *cur = *list;
+	if (!cur) {
+		*list = elem;
+		return;
+	}
+
 	while (cur->n)
 		cur = cur->n;
 
@@ -168,9 +173,14 @@ struct ast *ast_prepend(struct ast *list, struct ast *elem)
 	return elem;
 }
 
-void type_append(struct type *list, struct type *elem)
+void type_append(struct type **list, struct type *elem)
 {
-	struct type *cur = list;
+	struct type *cur = *list;
+	if (!cur) {
+		*list = elem;
+		return;
+	}
+
 	while (cur->n)
 		cur = cur->n;
 
@@ -681,7 +691,7 @@ size_t align3k(size_t o)
 {
 	size_t rem = o % 3;
 	if (rem)
-		o += rem;
+		o += 3 - rem;
 
 	return o;
 }
diff --git a/src/debug.c b/src/debug.c
index 734ce0e..0d11473 100644
--- a/src/debug.c
+++ b/src/debug.c
@@ -146,6 +146,19 @@ void type_error(struct file_ctx fctx, struct type *node,
 	va_end(args);
 }
 
+void loc_error(struct file_ctx fctx, struct src_loc loc,
+		const char *fmt, ...)
+{
+	va_list args;
+	va_start(args, fmt);
+	struct src_issue issue;
+	issue.level = SRC_ERROR;
+	issue.loc = loc;
+	issue.fctx = fctx;
+	_issue(issue, fmt, args);
+	va_end(args);
+}
+
 void semantic_warn(struct file_ctx fctx, struct ast *node, const char *fmt,
                    ...)
 {
diff --git a/src/lower.c b/src/lower.c
index b9f9665..630cb1d 100644
--- a/src/lower.c
+++ b/src/lower.c
@@ -345,6 +345,8 @@ static int lower_var(struct lower_state *s, struct ast *v,
                      struct retval *retval)
 {
 	assert(v->k == AST_VAR_DEF);
+	assert(var_init(v));
+
 	struct retval input = retval_create();
 	if (lower_expr(s, var_init(v), &input)) {
 		retval_destroy(&input);
diff --git a/src/parser.y b/src/parser.y
index 06599f2..a9c4776 100644
--- a/src/parser.y
+++ b/src/parser.y
@@ -155,6 +155,7 @@
 /* optional stuff */
 %nterm <node> opt_exprs proc_decl member opt_members
 %nterm <type> opt_types opt_sign_decls sign_decls sign_decl sign_var_decl
+%nterm <node> opt_construct_args
 %nterm <node> opt_behaviours behaviours behaviour
 
 /* reverse lists */
@@ -512,7 +513,7 @@ macro
 		ast_set_flags($6, AST_FLAG_UNHYGIENIC);
 	}
 	| "define" ID "(" references "..." id ")" body {
-		ast_append($4, $6);
+		ast_append(&$4, $6);
 		$$ = gen_macro_def($[ID], $4, $8, src_loc(@$));
 		ast_set_flags($$, AST_FLAG_VARIADIC);
 		ast_set_flags($8, AST_FLAG_UNHYGIENIC);
@@ -544,12 +545,16 @@ construct_args
 	: rev_construct_args { $$ = reverse_ast_list($1); }
 	| rev_construct_args "," { $$ = reverse_ast_list($1); }
 
+opt_construct_args
+	: construct_args
+	| { $$ = NULL; }
+
 construct
-	: APPLY "{" construct_args "}" {
+	: APPLY "{" opt_construct_args "}" {
 		/** @todo add type info? */
 		$$ = gen_init($1, NULL, $3, src_loc(@$));
 	}
-	| APPLY "[" opt_types "]" "{" construct_args "}" {
+	| APPLY "[" opt_types "]" "{" opt_construct_args "}" {
 		$$ = gen_init($1, $3, $6, src_loc(@$));
 	}
 
diff --git a/src/scope.c b/src/scope.c
index 4316a40..5cd7075 100644
--- a/src/scope.c
+++ b/src/scope.c
@@ -32,13 +32,22 @@ struct scope *create_scope()
 	return scope;
 }
 
-void destroy_visible(struct visible *visible)
+static void destroy_visible(struct visible *visible)
 {
 	struct visible *prev = visible, *cur;
 	if (prev)
 		do {
 			cur = prev->next;
-			/* destroy AST nodes globally somewhere? */
+			free(prev);
+		} while ((prev = cur));
+}
+
+static void destroy_expanded(struct expanded *expanded)
+{
+	struct expanded *prev = expanded, *cur;
+	if (prev)
+		do {
+			cur = prev->next;
 			free(prev);
 		} while ((prev = cur));
 }
@@ -57,6 +66,8 @@ void destroy_scope(struct scope *scope)
 	destroy_visible(scope->macros);
 	destroy_visible(scope->types);
 
+	destroy_expanded(scope->expanded);
+
 	struct scope *prev = scope->children, *cur;
 	if (prev)
 		do {
@@ -82,6 +93,9 @@ unsigned scope_flags(struct scope *scope, enum scope_flags flags)
 static struct visible *create_visible(char *id, struct ast *node)
 {
 	struct visible *visible = calloc(1, sizeof(struct visible));
+	if (!visible)
+		return NULL;
+
 	visible->id = id;
 	visible->node = node;
 	return visible;
@@ -99,6 +113,22 @@ struct visible *create_type(struct scope *scope, char *id, struct ast *type)
 	return n;
 }
 
+struct expanded *create_expanded(struct scope *scope, struct ast *def, struct type *types, struct ast *expd)
+{
+	struct expanded *n = calloc(1, sizeof(struct expanded));
+	if (!n)
+		return NULL;
+
+	n->node = def;
+	n->types = types;
+	n->expd = expd;
+
+	n->next = scope->expanded;
+	scope->expanded = n;
+
+	return n;
+}
+
 struct visible *create_var(struct scope *scope, char *id, struct ast *var)
 {
 	struct visible *n = create_visible(id, var);
@@ -227,6 +257,19 @@ int scope_add_trait(struct scope *scope, struct ast *trait)
 	return 0;
 }
 
+int scope_add_expd_struct(struct scope *scope, struct ast *def, struct type *types, struct ast *expd)
+{
+	assert(def->k == AST_STRUCT_DEF);
+	assert(file_scope_find_expd_struct(scope, def, types) == NULL);
+
+	create_expanded(scope, def, types, expd);
+	if (scope->parent &&
+			scope_flags(scope, SCOPE_FILE) && ast_flags(def, AST_FLAG_PUBLIC))
+		return scope_add_expd_struct(scope->parent, def, types, expd);
+
+	return 0;
+}
+
 static struct ast *scope_find_visible(struct visible *v, char *id)
 {
 	if (!v)
@@ -241,6 +284,22 @@ static struct ast *scope_find_visible(struct visible *v, char *id)
 	return NULL;
 }
 
+static struct ast *scope_find_expanded(struct expanded *e, struct ast *def, struct type *types)
+{
+	if (!e)
+		return NULL;
+
+	foreach_expanded(n, e) {
+		if (n->node != def)
+			continue;
+
+		if (type_lists_match(n->types, types))
+			return n->expd;
+	}
+
+	return NULL;
+}
+
 struct ast *scope_find_type(struct scope *scope, char *id)
 {
 	return scope_find_visible(scope->types, id);
@@ -352,13 +411,36 @@ struct ast *file_scope_find_var(struct scope *scope, char *id)
 	return NULL;
 }
 
+struct ast *scope_find_expd_struct(struct scope *scope, struct ast *def, struct type *types)
+{
+	assert(def->k == AST_STRUCT_DEF);
+	struct ast *exists = scope_find_expanded(scope->expanded, def, types);
+	if (!exists)
+		return NULL;
+
+	assert(exists->k == AST_STRUCT_DEF);
+	return exists;
+}
+
+struct ast *file_scope_find_expd_struct(struct scope *scope, struct ast *def, struct type *types)
+{
+	assert(def->k == AST_STRUCT_DEF);
+	struct ast *found = scope_find_expd_struct(scope, def, types);
+	if (found)
+		return found;
+
+	if (!scope_flags(scope, SCOPE_FILE))
+		return file_scope_find_expd_struct(scope->parent, def, types);
+
+	return NULL;
+}
+
 void scope_add_scope(struct scope *parent, struct scope *child)
 {
 	assert(parent);
 	assert(child);
 
 	if (!scope_flags(child, SCOPE_FILE)) {
-		child->actuals = parent->actuals;
 		child->fctx = parent->fctx;
 	}
 
@@ -366,27 +448,3 @@ void scope_add_scope(struct scope *parent, struct scope *child)
 	child->next = parent->children;
 	parent->children = child;
 }
-
-static int add_actual(struct actual *actuals, struct ast *node)
-{
-	if (!actuals->node) {
-		/* fill empty first element */
-		actuals->node = node;
-		return 0;
-	}
-
-	/* TODO: check that there isn't already an actual like ours */
-	struct actual *actual = calloc(1, sizeof(struct actual));
-	if (!actual)
-		return -1;
-
-	actual->next = actuals->next;
-	actual->node = node;
-	actuals->next = actual;
-	return 0;
-}
-
-int scope_add_actual(struct scope *scope, struct ast *node)
-{
-	return add_actual(scope->actuals, node);
-}