5 files changed, 306 insertions, 47 deletions

diff --git a/include/cu/actualize.h b/include/cu/actualize.h
index ea736ac..94a4d30 100644
--- a/include/cu/actualize.h
+++ b/include/cu/actualize.h
@@ -29,5 +29,6 @@ struct ast_node *extract_typeof(struct ast_node *type);
 int analyze_root(struct scope *scope, struct ast_node *tree);
 int actualize_main(struct scope *scope);
 int actualize_temp_type(struct scope *scope, struct ast_node *type);
+struct ast_node *actual_type(struct ast_node *type);
 
 #endif /* ANALYZE_H */
diff --git a/src/actualize.c b/src/actualize.c
index a210c9b..0c7a378 100644
--- a/src/actualize.c
+++ b/src/actualize.c
@@ -401,21 +401,21 @@ static int analyze_procs(struct scope *scope)
 {
 	struct visible *procs = scope->procs;
 	/*
-	struct act_state state = {0};
-	act_set_flags(&state, ACT_ONLY_TYPES);
-	if (procs)
-		do {
-			if (procs->owner != scope)
-				goto skip_actualize;
+	   struct act_state state = {0};
+	   act_set_flags(&state, ACT_ONLY_TYPES);
+	   if (procs)
+	        do {
+	                if (procs->owner != scope)
+	                        goto skip_actualize;
 
-			struct ast_node *proc = procs->node;
-			if (actualize(&state, scope, proc))
-				return -1;
+	                struct ast_node *proc = procs->node;
+	                if (actualize(&state, scope, proc))
+	                        return -1;
 
-skip_actualize:
-			procs = procs->next;
-		} while (procs);
-	*/
+	   skip_actualize:
+	                procs = procs->next;
+	        } while (procs);
+	 */
 
 	/* reinsert procs with actualized signatures, should make sure we don't
 	 * have duplicates after all aliases etc. have been eliminated */
@@ -498,13 +498,68 @@ static int typeof_match(struct ast_node *a, struct ast_node *b)
 	while (a && a->_type.kind == AST_TYPE_TYPEOF)
 		a = a->_type.typeo.actual;
 
-
 	while (b && b->_type.kind == AST_TYPE_TYPEOF)
 		b = b->_type.typeo.actual;
 
 	return types_match(a, b);
 }
 
+static int struct_match(struct ast_node *a, struct ast_node *b)
+{
+	if (!identical_ast_nodes(0, a->_type.struc.id, b->_type.struc.id))
+		return 0;
+
+	/* note a slight asymmetry, in that types on the right will match if
+	 * they don't have impls, but structs on the left will not. */
+	if (!b->_type.struc.impls)
+		return 1;
+
+	if (!a->_type.struc.impls)
+		return 0;
+
+	struct ast_node *a_impls = a->_type.struc.impls;
+	struct ast_node *b_impls = b->_type.struc.impls;
+	while (a_impls && b_impls) {
+		if (!types_match(a_impls, b_impls))
+			return 0;
+
+		b_impls = b_impls->next;
+		a_impls = a_impls->next;
+	}
+
+	if (a_impls || b_impls)
+		return 0;
+
+	return 1;
+}
+
+static int union_match(struct ast_node *a, struct ast_node *b)
+{
+	assert(a->_type.kind == AST_TYPE_UNION);
+	assert(b->_type.kind == AST_TYPE_UNION);
+
+	if (!identical_ast_nodes(0, a->_type.unio.id, b->_type.unio.id))
+		return 0;
+
+	if (!a->_type.unio.impls || !b->_type.unio.impls)
+		return 1;
+
+	struct ast_node *a_impls = a->_type.unio.impls;
+	struct ast_node *b_impls = b->_type.unio.impls;
+	while (a_impls && b_impls) {
+		a_impls = a_impls->next;
+		if (!types_match(a_impls, b_impls))
+			return 0;
+
+		b_impls = b_impls->next;
+	}
+
+	if (a_impls || b_impls)
+		return 0;
+
+	return 1;
+}
+
 int types_match(struct ast_node *a, struct ast_node *b)
 {
 	if (!a && !b)
@@ -539,6 +594,8 @@ int types_match(struct ast_node *a, struct ast_node *b)
 		return 0;
 	}
 
+	/* aliases etc. resolved, not if the kinds are different we must not
+	 * match */
 	if (a->_type.kind != b->_type.kind)
 		return 0;
 
@@ -550,6 +607,22 @@ int types_match(struct ast_node *a, struct ast_node *b)
 		return 0;
 	}
 
+	if (a->_type.kind == AST_TYPE_STRUCT ||
+	    b->_type.kind == AST_TYPE_STRUCT) {
+		if (struct_match(a, b))
+			return 1;
+
+		return 0;
+	}
+
+	if (a->_type.kind == AST_TYPE_UNION ||
+	    b->_type.kind == AST_TYPE_UNION) {
+		if (union_match(a, b))
+			return 1;
+
+		return 0;
+	}
+
 	/* from here on, we know that both types are identical */
 	if (!identical_ast_nodes(0, a, b))
 		return 0;
@@ -1120,6 +1193,7 @@ static int actualize_var(struct act_state *state,
 	if (var->_var.id && !ast_flags(var, AST_FLAG_MEMBER))
 		return scope_add_var(scope, var);
 
+	/* TODO: we should make sure the type is fully qualified in bodies */
 	return 0;
 }
 
@@ -1283,6 +1357,8 @@ static int actualize_type(struct act_state *state,
 		struct ast_node *types = type->_type.struc.impls;
 		if (actualize(state, scope, types))
 			EXIT_ACT(-1);
+
+		/* TODO: check that all params are fully qualified */
 		break;
 	}
 
@@ -1532,7 +1608,7 @@ static int init_struct(struct act_state *state, struct scope *scope,
 	return ret;
 }
 
-static struct ast_node *actual_type(struct ast_node *type)
+struct ast_node *actual_type(struct ast_node *type)
 {
 	assert(type->node_type == AST_TYPE);
 	if (type->_type.kind == AST_TYPE_ALIAS)
diff --git a/src/debug.c b/src/debug.c
index 6aa4283..b929876 100644
--- a/src/debug.c
+++ b/src/debug.c
@@ -198,10 +198,12 @@ static void _type_str(FILE *fp, struct ast_node *type)
 
 		struct ast_node *impls = type->_type.struc.impls;
 		if (impls) {
-			fprintf(fp, " (");
+			fprintf(fp, "(");
 			while (impls) {
 				_type_str(fp, impls);
 				impls = impls->next;
+				if (impls)
+					fprintf(fp, ", ");
 			}
 			fprintf(fp, ")");
 		}
diff --git a/src/scope.c b/src/scope.c
index e9cf75c..b560e5f 100644
--- a/src/scope.c
+++ b/src/scope.c
@@ -11,26 +11,27 @@
 #include <cu/scope.h>
 #include <cu/actualize.h>
 
+static int generics_trait_type(struct ast_node *generics)
+{
+	if (!generics)
+		return 0;
+
+	if (actual_type(generics)->_type.kind == AST_TYPE_TEMPLATE)
+		return 1;
+
+	return generics_trait_type(generics->_type.next);
+}
+
 static int generic_type(struct scope *scope, struct ast_node *type)
 {
 	if (!type)
 		return 0;
 
-	if (type->_type.kind == AST_TYPE_STRUCT) {
-		/* check if the structure takes template parameters */
-		struct ast_node *struc = file_scope_find_type(scope, type);
-		assert(struc);
-		assert(struc->node_type == AST_STRUCT);
-		return struc->_struct.generics != NULL;
-	}
+	if (type->_type.kind == AST_TYPE_STRUCT)
+		return generics_trait_type(type->_type.struc.impls);
 
 	if (type->_type.kind == AST_TYPE_UNION) {
-		/* check if the structure takes template parameters */
-		struct ast_node *unio = file_scope_find_type(scope,
-		                                             type->_type.unio.id);
-		assert(unio);
-		assert(unio->node_type == AST_UNION);
-		return unio->_union.generics != NULL;
+		return generics_trait_type(type->_type.unio.impls);
 	}
 
 	if (type->_type.kind == AST_TYPE_TEMPLATE)
@@ -67,11 +68,69 @@ static int primitive_type(struct scope *scope, struct ast_node *type)
 	return 1;
 }
 
-static struct param_node *find_primitive(struct scope *scope, struct proc_node *node,
+static int fully_qualified(struct ast_node *type)
+{
+	if (!type)
+		return 1;
+
+	assert(type->_type.kind != AST_TYPE_TEMPLATE);
+	if (type->_type.kind == AST_TYPE_STRUCT) {
+		if (type->_type.struc.impls)
+			return fully_qualified(type->_type.struc.impls);
+
+		return 0;
+	}
+
+	if (type->_type.kind == AST_TYPE_UNION) {
+		if (type->_type.unio.impls)
+			return fully_qualified(type->_type.unio.impls);
+
+		return 0;
+	}
+
+	return fully_qualified(type->_type.next);
+}
+
+static struct param_node *find_primitive(struct scope *scope,
+                                         struct proc_node *node,
                                          struct ast_node *type)
 {
 	struct param_node *param = node->primitives;
 	while (param) {
+		if (types_match(type, param->type))
+			return param;
+
+		param = param->next;
+	}
+
+	return NULL;
+}
+
+static int compare_primitives(struct ast_node *a, struct ast_node *b);
+
+/* match also checks qualification status of the types, since we can
+ * differentiate between fully qualified types and not fully qualified types
+ * by placing qualified types towards the front of the primitive list.
+ * This is analoguous to the fallback thing in traits, but we want to be able to
+ * support multiple not fully qualified primitives, for example
+ *
+ * add(some_generic_struct)
+ * add(some_other_generic_struct)
+ *
+ * since they are easily distinguishable from eachother, in contract to traits.
+ *
+ * Therefore, use this when checking if a primitive should be added to the list,
+ * otherwise use find_primitive() to get which primitive matches.
+ * (are these names inverted from their intention? I'm not sure)
+ */
+static struct param_node *match_primitive(struct scope *scope, struct proc_node *node,
+		struct ast_node *type)
+{
+	struct param_node *param = node->primitives;
+	while (param) {
+		/* note very subtle change in that we pass param->type first
+		 * here, but second in find_primitive. This could easily be
+		 * confusing... */
 		if (types_match(param->type, type))
 			return param;
 
@@ -87,6 +146,100 @@ static int match_generic(struct scope *scope, struct ast_node *a,
 	return implements(0, scope, a, b);
 }
 
+static int compare_impls(struct ast_node *a, struct ast_node *b)
+{
+	if (!a)
+		return 1;
+
+	if (!b)
+		return 0;
+
+	while (a && b) {
+		if (compare_primitives(a, b) == 0)
+			return 0;
+
+		a = a->next;
+		b = b->next;
+	}
+
+	return 1;
+}
+
+/* return 1 if a should come after b, 0 if a should come before b */
+static int compare_primitives(struct ast_node *a, struct ast_node *b)
+{
+	assert(a);
+	if (!b)
+		return 0;
+
+	/* fully qualified types go first */
+	if (fully_qualified(a))
+		return 0;
+
+	if (fully_qualified(b))
+		return 1;
+
+	/* TODO: figure out what kind of unqualified type we're dealing with,
+	 * i.e. some_generic(u32, some_other_generic) should come before
+	 * some_generic */
+
+	/* if we're dealing with different unqualified types, push stuff
+	 * backwards, so we don't end up with something like
+	 * 1. some_generic_type
+	 * 2. some_generic_union
+	 * 3. some_generic_type(u32)
+	 */
+
+	if (a->_type.kind != b->_type.kind)
+		return 1;
+
+	if (a->_type.kind == AST_TYPE_STRUCT)
+		return compare_impls(a->_type.struc.impls, b->_type.struc.impls);
+
+	if (a->_type.kind == AST_TYPE_UNION)
+		return compare_impls(a->_type.unio.impls, b->_type.unio.impls);
+
+	return 1;
+}
+
+static struct proc_node *insert_primitive(struct proc_node *node,
+                                          struct ast_node *type)
+{
+	struct param_node *new = calloc(1, sizeof(struct param_node));
+	if (!new) {
+		return NULL;
+	}
+	new->type = type;
+
+	struct proc_node *next = calloc(1, sizeof(struct proc_node));
+	if (!next) {
+		free(new);
+		return NULL;
+	}
+	new->proc = next;
+
+	if (!node->primitives) {
+		node->primitives = new;
+		return next;
+	}
+
+	struct param_node *iter = node->primitives, *prev = NULL;
+	while (iter && compare_primitives(type, iter->type)) {
+		prev = iter;
+		iter = iter->next;
+	}
+
+	if (prev)
+		prev->next = new;
+
+	new->next = iter;
+
+	if (iter == node->primitives)
+		node->primitives = new;
+
+	return next;
+}
+
 static int add_next_resolve(struct scope *scope, struct ast_node *proc,
                             struct proc_node *node, struct ast_node *params)
 {
@@ -110,18 +263,16 @@ static int add_next_resolve(struct scope *scope, struct ast_node *proc,
 
 	assert(params->node_type == AST_VAR);
 	if (primitive_type(scope, params->type)) {
-		struct param_node *found = find_primitive(scope, node, params->type);
-		if (found)
-			return add_next_resolve(scope, proc, found->proc,
+		struct param_node *match = match_primitive(scope, node,
+		                                          params->type);
+		if (match)
+			return add_next_resolve(scope, proc, match->proc,
 			                        params->next);
 
-		found = calloc(1, sizeof(struct param_node));
-		found->type = params->type;
-		found->next = node->primitives;
-		node->primitives = found;
+		struct proc_node *next = insert_primitive(node, params->type);
+		if (!next)
+			return -1;
 
-		struct proc_node *next = calloc(1, sizeof(struct proc_node));
-		found->proc = next;
 		return add_next_resolve(scope, proc, next, params->next);
 	}
 
@@ -129,13 +280,16 @@ static int add_next_resolve(struct scope *scope, struct ast_node *proc,
 		/* TODO: I don't think there's a good way to check if the
 		 * referential types are identical, but could be worth a shot */
 		if (!node->referential) {
-			node->referential = calloc(1, sizeof(struct param_node));
+			node->referential =
+				calloc(1, sizeof(struct param_node));
 			node->referential->type = params->type;
 
-			struct proc_node *next = calloc(1, sizeof(struct proc_node));
+			struct proc_node *next =
+				calloc(1, sizeof(struct proc_node));
 			node->referential->proc = next;
 
-			return add_next_resolve(scope, proc, next, params->next);
+			return add_next_resolve(scope, proc, next,
+			                        params->next);
 		}
 
 		if (!types_match(node->referential->type, params->type)) {
@@ -150,7 +304,8 @@ static int add_next_resolve(struct scope *scope, struct ast_node *proc,
 		destroy_ast_tree(params->type);
 		params->_var.type = NULL;
 		params->type = node->referential->type;
-		return add_next_resolve(scope, proc, node->referential->proc, params->next);
+		return add_next_resolve(scope, proc, node->referential->proc,
+		                        params->next);
 	}
 
 	/* otherwise try to use type as fallback */
diff --git a/tests/resolve.cu b/tests/resolve.cu
index abe9fe5..aee8bc4 100644
--- a/tests/resolve.cu
+++ b/tests/resolve.cu
@@ -1,10 +1,35 @@
 typedef A {}
 
+struct generic (T1 A, T2 A) {
+	a T1;
+	b T2;
+}
+
+struct other_generic(T1 A) {
+	a T1;
+	b T1;
+}
+
 /* wow this works pretty good */
-some_func(c A, d typeof c, e i64){c;}
-some_func(c A, d typeof c, e typeof d){d;}
-some_func(c A, d typeof c, e A){e;}
+//some_func(a A, b typeof a, c i64){1;}
+//some_func(a A, b typeof a, c typeof b){2;}
+//some_func(a A, b typeof a, c A){3;}
+//some_func(a generic(u32, u32)) {5;}
+//some_func(a other_generic){6;}
+// TODO: partial templates shouldn't be allowed
+//some_func(a generic(u32)){6;}
+//some_func(a generic) {4;}
+// illegal
+// TODO: traits shouldn't be allowed in template instantiation
+//some_func(a generic(A, A)){6;}
+//some_func(generic(generic, generic)){1;}
+some_func(generic(generic, i64)){2;}
+some_func(generic(i64, generic)){3;}
+//some_func(generic(i64, i64)){4;}
+some_func(generic){5;}
 
 main(){
-	some_func(20 as f32, 20 as f32, 20 as f64);
+	// TODO: not fully qualified types in bodies should cause an error
+	a generic(i64, u32);
+	some_func(a);
 }