start sketching out type system

5 files changed, 217 insertions, 55 deletions

diff --git a/src/analyze.c b/src/analyze.c
index c33a901..0c06096 100644
--- a/src/analyze.c
+++ b/src/analyze.c
@@ -189,7 +189,7 @@ static int analyze_var(struct state *state, struct scope *scope,
 		return -1;
 
 	node->t = var_type(node);
-	return scope_add_var(scope, node);
+	return scope_add_symbol(scope, node);
 }
 
 static int analyze_let(struct state *state, struct scope *scope,
@@ -478,7 +478,7 @@ static int analyze_err_branch(struct state *state, struct scope *scope, struct a
 	struct ast *var = gen_var(strdup(err_branch_id(node)), NULL, node->loc);
 	struct type *err_type = tgen_err(node->loc);
 	var->t = err_type;
-	scope_add_var(branch_scope, var);
+	scope_add_symbol(branch_scope, var);
 	return analyze(state, branch_scope, err_branch_body(node));
 }
 
@@ -607,9 +607,30 @@ static int analyze_type_list(struct state *state, struct scope *scope,
 int analyze_root(struct scope *scope, struct ast *root)
 {
 	foreach_node(node, root) {
-		assert(node->k == AST_PROC_DEF);
-		if (scope_add_proc(scope, node))
-			return -1;
+		switch (node->k) {
+		case AST_PROC_DEF:
+		      if (scope_add_symbol(scope, node))
+			      return -1;
+		      break;
+
+		case AST_STRUCT_DEF:
+		      if (scope_add_type(scope, node))
+			      return -1;
+		      break;
+
+		case AST_STRUCT_CONT:
+		      if (scope_add_chain(scope, node))
+			      return -1;
+		      break;
+
+		case AST_TRAIT_DEF:
+		      if (scope_add_trait(scope, node))
+			      return -1;
+		      break;
+
+		default:
+		      abort();
+		}
 	}
 
 	foreach_node(node, root) {
diff --git a/src/ast.c b/src/ast.c
index c236445..427c4c4 100644
--- a/src/ast.c
+++ b/src/ast.c
@@ -206,6 +206,11 @@ void ast_dump(int depth, struct ast *n)
 
 #define DUMP(x) case x: dump(depth, #x); break;
 	switch (n->k) {
+	DUMP(AST_IMPORT);
+	DUMP(AST_TRAIT_DEF);
+	DUMP(AST_TRAIT_APPLY);
+	DUMP(AST_STRUCT_DEF);
+	DUMP(AST_STRUCT_CONT);
 	DUMP(AST_CLOSURE);
 	DUMP(AST_IF);
 	DUMP(AST_NIL);
@@ -636,6 +641,11 @@ const char *ast_str(enum ast_kind k)
 {
 #define CASE(x) case x: return #x;
 	switch (k) {
+	CASE(AST_IMPORT);
+	CASE(AST_TRAIT_DEF);
+	CASE(AST_TRAIT_APPLY);
+	CASE(AST_STRUCT_DEF);
+	CASE(AST_STRUCT_CONT);
 	CASE(AST_CLOSURE);
 	CASE(AST_IF);
 	CASE(AST_NIL);
diff --git a/src/lexer.l b/src/lexer.l
index e11b51e..e6a3f22 100644
--- a/src/lexer.l
+++ b/src/lexer.l
@@ -131,6 +131,10 @@ STRING		\"(\\.|[^"\\])*\"
 "else"		{return ELSE;}
 "nil"		{return NIL;}
 "own"		{return OWN;}
+"pub"		{return PUB;}
+
+"import"	{return IMPORT;}
+"continue"	{return CONTINUE;}
 
 "error"		{return ERROR;}
 
diff --git a/src/parser.y b/src/parser.y
index 68725a8..7b2c651 100644
--- a/src/parser.y
+++ b/src/parser.y
@@ -74,7 +74,10 @@
 %token ELSE "else"
 %token NIL "nil"
 %token OWN "own"
+%token PUB "pub"
 %token MUT "mut"
+%token CONTINUE "continue"
+%token IMPORT "import"
 %token ERROR "error"
 %token DOT "."
 %token SCOPE "::"
@@ -97,11 +100,16 @@
 %left "." "=>" "(" ")"
 %left "::"
 
-%nterm <node> top unit proc call closure var expr statement body
+%nterm <node> top unit proc proc_decl call closure var expr statement body
 %nterm <node> vars exprs statements closures err trailing_closure
 %nterm <node> opt_vars opt_exprs opt_statements opt_trailing_closure opt_err opt_error
 %nterm <node> rev_vars rev_exprs rev_closures rev_statements
-%nterm <node> let if nil own unop binop construct
+%nterm <node> let if nil own unop binop construct import
+
+%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 <type> type rev_types types opt_types
 
@@ -203,7 +211,9 @@ proc
 	: ID "(" opt_vars ")" body {
 		$$ = gen_proc($[ID], $[opt_vars], NULL, $[body], src_loc(@$));
 	}
-	| ID "(" opt_vars ")" ";" {
+
+proc_decl
+	: ID "(" opt_vars ")" ";" {
 		$$ = gen_proc($[ID], $[opt_vars], NULL, NULL, src_loc(@$));
 	}
 
@@ -413,8 +423,80 @@ body
 		$$ = gen_block($2, $3, src_loc(@$));
 	}
 
+behaviour
+	: APPLY ";" { $$ = gen_trait_apply($1, src_loc(@$)); }
+	| proc_decl ";"
+	| proc
+
+behaviours
+	: behaviours behaviour { $$ = $1; $1->n = $2; }
+	| behaviour
+
+opt_behaviours
+	: behaviours
+	| { $$ = NULL; }
+
+member
+	: var ";"
+	| behaviour
+
+members
+	: members member { $$ = $1; $1->n = $2; }
+	| member
+
+opt_members
+	: members
+	| { $$ = NULL; }
+
+type_param
+	: ID ID {
+		struct type *t = tgen_id($1, src_loc(@1));
+		$$ = gen_var($2, t, src_loc(@$));
+	}
+
+type_params
+	: type_param "," type_params {
+		$$ = $1; $1->n = $3;
+	}
+	| type_param
+
+opt_type_params
+	: type_params
+	| { $$ = NULL; }
+
+struct
+	: ID "[" opt_type_params "]" "{" opt_members "}" {
+		$$ = gen_struct($1, $3, $6, src_loc(@$));
+	}
+
+struct_cont
+	: "continue" ID "[" opt_type_params "]" "{" opt_behaviours "}" {
+		$$ = gen_struct_cont($2, $4, $7, src_loc(@$));
+	}
+
+trait
+	: ID "{" opt_behaviours "}" {
+		$$ = gen_trait($1, $3, src_loc(@$));
+	}
+
+import
+	: "import" STRING {
+		$$ = gen_import($2, src_loc(@$));
+	}
+
 top
 	: proc
+	| proc_decl
+	| struct
+	| struct_cont
+	| import
+	| trait
+	| "pub" proc        { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); }
+	| "pub" proc_decl   { $$ = $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); }
 	| error {
 	    $$ = gen_empty(src_loc(@$));
 	    parser->failed = true;
diff --git a/src/scope.c b/src/scope.c
index 367384a..fe35d58 100644
--- a/src/scope.c
+++ b/src/scope.c
@@ -29,6 +29,8 @@ struct scope *create_scope()
 
 	scope->number = counter++;
 	scope->symbols = visible_create(16); /* arbitrary number */
+	scope->traits = visible_create(1);
+	scope->types = visible_create(1);
 	return scope;
 }
 
@@ -43,6 +45,8 @@ void destroy_scope(struct scope *scope)
 	}
 
 	visible_destroy(&scope->symbols);
+	visible_destroy(&scope->traits);
+	visible_destroy(&scope->types);
 
 	struct scope *prev = scope->children, *cur;
 	if (prev)
@@ -54,17 +58,17 @@ void destroy_scope(struct scope *scope)
 	free(scope);
 }
 
-int scope_add_var(struct scope *scope, struct ast *var)
+int scope_add_symbol(struct scope *scope, struct ast *symbol)
 {
-	assert(var->k == AST_VAR_DEF);
-	struct ast **exists = visible_insert(&scope->symbols, var_id(var), var);
+	assert(symbol->k == AST_VAR_DEF || symbol->k == AST_PROC_DEF);
+	struct ast **exists = visible_insert(&scope->symbols, symbol->s, symbol);
 	if (!exists) {
-		internal_error("failed inserting var into scope");
+		internal_error("failed inserting symbol into scope");
 		return -1;
 	}
 
-	if (*exists != var) {
-		semantic_error(scope, var, "var redefined");
+	if (*exists != symbol) {
+		semantic_error(scope, symbol, "symbol redefined");
 		semantic_info(scope, *exists, "previously here");
 		return -1;
 	}
@@ -72,17 +76,38 @@ int scope_add_var(struct scope *scope, struct ast *var)
 	return 0;
 }
 
-int scope_add_proc(struct scope *scope, struct ast *proc)
+struct ast *scope_find_symbol(struct scope *scope, char *id)
+{
+	struct ast **v = visible_find(&scope->symbols, id);
+	if (!v)
+		return NULL;
+
+	return *v;
+}
+
+struct ast *file_scope_find_symbol(struct scope *scope, char *id)
+{
+	if (!scope)
+		return NULL;
+
+	struct ast *found = scope_find_symbol(scope, id);
+	if (found)
+		return found;
+
+	return file_scope_find_symbol(scope->parent, id);
+}
+
+int scope_add_type(struct scope *scope, struct ast *type)
 {
-	assert(proc->k == AST_PROC_DEF);
-	struct ast **exists = visible_insert(&scope->symbols, proc_id(proc), proc);
+	assert(type->k == AST_STRUCT_DEF);
+	struct ast **exists = visible_insert(&scope->symbols, type->s, type);
 	if (!exists) {
-		internal_error("failed inserting proc into scope");
+		internal_error("failed inserting type into scope");
 		return -1;
 	}
 
-	if (*exists != proc) {
-		semantic_error(scope, proc, "proc redefined");
+	if (*exists != type) {
+		semantic_error(scope, type, "type redefined");
 		semantic_info(scope, *exists, "previously here");
 		return -1;
 	}
@@ -90,79 +115,99 @@ int scope_add_proc(struct scope *scope, struct ast *proc)
 	return 0;
 }
 
-struct ast *scope_find_proc(struct scope *scope, char *id)
+int scope_add_chain(struct scope *scope, struct ast *type)
 {
-	struct ast **v = visible_find(&scope->symbols, id);
-	if (!v)
-		return NULL;
+	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;
+	}
 
-	struct ast *n = *v;
-	assert(n);
+	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;
+		}
 
-	if (n->k != AST_PROC_DEF)
-		return NULL;
+		/* overwrite root */
+		if (*v != type)
+			*v = type;
 
-	return n;
-}
-
-struct ast *file_scope_find_proc(struct scope *scope, char *id)
-{
-	struct ast *n = file_scope_find_symbol(scope, id);
-	if (!n)
-		return NULL;
+		return 0;
+	}
 
-	if (n->k != AST_PROC_DEF)
-		return NULL;
+	struct ast *next = exists->chain;
+	while (next->k == AST_STRUCT_CONT && !ast_flags(next, AST_FLAG_PUBLIC)) {
+		exists = next;
+		next = next->chain;
+	}
 
-	return n;
+	exists->chain = type;
+	type->chain = exists;
+	return 0;
 }
 
-struct ast *scope_find_symbol(struct scope *scope, char *id)
+struct ast *scope_find_type(struct scope *scope, char *id)
 {
-	struct ast **v = visible_find(&scope->symbols, id);
+	struct ast **v = visible_find(&scope->types, id);
 	if (!v)
 		return NULL;
 
 	return *v;
 }
 
-struct ast *file_scope_find_symbol(struct scope *scope, char *id)
+struct ast *file_scope_find_type(struct scope *scope, char *id)
 {
 	if (!scope)
 		return NULL;
 
-	struct ast *found = scope_find_symbol(scope, id);
+	struct ast *found = scope_find_type(scope, id);
 	if (found)
 		return found;
 
-	return file_scope_find_symbol(scope->parent, id);
+	return file_scope_find_type(scope->parent, id);
 }
 
-struct ast *scope_find_var(struct scope *scope, char *id)
+int scope_add_trait(struct scope *scope, struct ast *trait)
 {
-	struct ast **v = visible_find(&scope->symbols, id);
-	if (!v)
-		return NULL;
+	assert(trait->k == AST_TRAIT_DEF);
+	struct ast **exists = visible_insert(&scope->symbols, trait->s, trait);
+	if (!exists) {
+		internal_error("failed inserting trait into scope");
+		return -1;
+	}
 
-	struct ast *n = *v;
-	assert(n);
+	if (*exists != trait) {
+		semantic_error(scope, trait, "trait redefined");
+		semantic_info(scope, *exists, "previously here");
+		return -1;
+	}
 
-	if (n->k != AST_VAR_DEF)
+	return 0;
+}
+struct ast *scope_find_trait(struct scope *scope, char *id)
+{
+	struct ast **v = visible_find(&scope->traits, id);
+	if (!v)
 		return NULL;
 
-	return n;
+	return *v;
 }
 
-struct ast *file_scope_find_var(struct scope *scope, char *id)
+struct ast *file_scope_find_trait(struct scope *scope, char *id)
 {
 	if (!scope)
 		return NULL;
 
-	struct ast *found = scope_find_var(scope, id);
+	struct ast *found = scope_find_trait(scope, id);
 	if (found)
 		return found;
 
-	return file_scope_find_var(scope->parent, id);
+	return file_scope_find_trait(scope->parent, id);
 }
 
 void scope_add_scope(struct scope *parent, struct scope *child)