start sketching out type system

7 files changed, 268 insertions, 128 deletions

diff --git a/include/fwd/ast.h b/include/fwd/ast.h
index a253901..36aa8c8 100644
--- a/include/fwd/ast.h
+++ b/include/fwd/ast.h
@@ -56,8 +56,18 @@ struct type {
 
 /** Possible AST node types. We reserve node 0 as an illegal value. */
 enum ast_kind {
-	/** Creating new variable. */
-	AST_LET = 1,
+	/** Trait definition */
+	AST_TRAIT_DEF = 1,
+	/** Trait application */
+	AST_TRAIT_APPLY,
+	/** Structure definition */
+	AST_STRUCT_DEF,
+	/** Structure continuation */
+	AST_STRUCT_CONT,
+	/** Import */
+	AST_IMPORT,
+	/** Creating new variable */
+	AST_LET,
 	/** If statement */
 	AST_IF,
 	/** Nil check */
@@ -141,6 +151,7 @@ enum ast_flag {
 	AST_FLAG_ANALYZED       = (1 << 0),
 	AST_FLAG_PREANALYZIS    = (1 << 1),
 	AST_FLAG_NOMOVES        = (1 << 2),
+	AST_FLAG_PUBLIC		= (1 << 3),
 };
 
 struct ast {
@@ -161,6 +172,8 @@ struct ast {
 	struct type *t;
 	enum ast_flag flags;
 
+	struct ast *chain;
+
 	/* optional group */
 	struct ast *ol;
 	struct ast *or;
@@ -412,6 +425,31 @@ static inline bool is_trivially_copyable(struct type *type)
 #define gen_block(body, err, loc) \
 	gen2(AST_BLOCK, body, err, loc)
 
+#define trait_id(x) return_s(x, AST_TRAIT_DEF)
+#define trait_body(x) return_a1(x, AST_TRAIT_DEF)
+#define gen_trait(id, body, loc) \
+	gen_str1(AST_TRAIT_DEF, id, body, loc)
+
+#define trait_apply_id(x) return_s(x, AST_TRAIT_APPLY)
+#define gen_trait_apply(id, loc) \
+	gen_str(AST_TRAIT_DEF, id, loc)
+
+#define struct_id(x) return_s(x, AST_STRUCT_DEF)
+#define struct_params(x) return_a0(x, AST_STRUCT_DEF)
+#define struct_body(x) return_a1(x, AST_STRUCT_DEF)
+#define gen_struct(id, params, body, loc) \
+	gen_str2(AST_STRUCT_DEF, id, params, body, loc)
+
+#define import_file(x) return_s(x, AST_IMPORT)
+#define gen_import(file, loc) \
+	gen_str(AST_IMPORT, file, loc)
+
+#define struct_cont_id(x) return_s(x, AST_STRUCT_CONT)
+#define struct_cont_params(x) return_a0(x, AST_STRUCT_CONT)
+#define struct_cont_body(x) return_a1(x, AST_STRUCT_CONT)
+#define gen_struct_cont(id, params, body, loc) \
+	gen_str2(AST_STRUCT_CONT, id, params, body, loc)
+
 #define str_val(x) return_s(x, AST_CONST_STR)
 #define gen_const_str(s, loc) \
 	gen_ast(AST_CONST_STR, NULL, NULL, NULL, NULL, NULL, s, 0, 0., loc)
diff --git a/include/fwd/scope.h b/include/fwd/scope.h
index e49eb0a..ebe0261 100644
--- a/include/fwd/scope.h
+++ b/include/fwd/scope.h
@@ -52,6 +52,8 @@ struct scope {
 	struct scope *children;
 
 	struct visible symbols;
+	struct visible traits;
+	struct visible types;
 
 	enum scope_flags flags;
 };
@@ -106,80 +108,18 @@ int scope_add_scratch(struct scope *scope, struct ast *scratch);
  */
 void scope_add_scope(struct scope *parent, struct scope *child);
 
-/**
- * Add variable to scope.
- * Propagates public variables up the file scope chain as references.
- *
- * @param scope Scope to add variable to.
- * @param var Variable to add to scope.
- * @return \c 0 when succesful, non-zero otherwise.
- */
-int scope_add_var(struct scope *scope, struct ast *var);
-
-/**
- * Add type to scope.
- * Propagates public types up the file scope chain as references.
- *
- * @param scope Scope to add type to.
- * @param type Type to add to scope.
- * @return \c 0 when succesful, non-zero otherwise.
- */
-int scope_add_type(struct scope *scope, char *id, struct ast *type);
 
-/**
- * Add procedure to scope.
- * Propagates public procedures up the file scope chain as references.
- *
- * @param scope Scope to add procedure to.
- * @param proc Procedure to add to scope.
- * @return \c 0 when succesful, non-zero otherwise.
- */
-int scope_add_proc(struct scope *scope, struct ast *proc);
-
-/**
- * Find a variable with ID in \p scope.
- * @note Only looks in the current scope, so doesn't see anything outside
- * of it. See file_scope_find_var().
- *
- * @param scope Scope to look in.
- * @param id ID of variable to find.
- * @return Pointer to the AST node corresponding to \p id if found,
- * otherwise \c NULL.
- */
-struct ast *scope_find_var(struct scope *scope, char *id);
+int scope_add_symbol(struct scope *scope, struct ast *symbol);
 struct ast *scope_find_symbol(struct scope *scope, char *id);
-
-/**
- * Find a procedure with ID in \p scope.
- * @note Only looks in the current scope, so doesn't see anything outside
- * of it. See file_scope_find_proc().
- *
- * @param scope Scope to look in.
- * @param id ID of procedure to find.
- * @return Pointer to the AST node corresponding to \p id if found,
- * otherwise \c NULL.
- */
-struct ast *scope_find_proc(struct scope *scope, char *id);
-
-/**
- * Find a variable with ID visible to \p scope.
- *
- * @param scope Scope to look in.
- * @param id ID of variable to find.
- * @return Pointer to the AST node corresponding to \p id if found,
- * otherwise \c NULL.
- */
-struct ast *file_scope_find_var(struct scope *scope, char *id);
 struct ast *file_scope_find_symbol(struct scope *scope, char *id);
 
-/**
- * Find a procedure with ID visible to \p scope.
- *
- * @param scope Scope to look in.
- * @param id ID of procedure to find.
- * @return Pointer to the AST node corresponding to \p id if found,
- * otherwise \c NULL.
- */
-struct ast *file_scope_find_proc(struct scope *scope, char *id);
+int scope_add_type(struct scope *scope, struct ast *type);
+int scope_add_chain(struct scope *scope, struct ast *type);
+struct ast *scope_find_type(struct scope *scope, char *id);
+struct ast *file_scope_find_type(struct scope *scope, char *id);
+
+int scope_add_trait(struct scope *scope, struct ast *trait);
+struct ast *scope_find_trait(struct scope *scope, char *id);
+struct ast *file_scope_find_trait(struct scope *scope, char *id);
 
 #endif /* SCOPE_H */
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)