much better circular dependency checking system for structs

8 files changed, 192 insertions, 150 deletions

diff --git a/README.md b/README.md
index e60fee7..ccc1d41 100644
--- a/README.md
+++ b/README.md
@@ -30,7 +30,7 @@ See `docs` for more information (in progress).
 
 To compile the compiler on a Unix-y system, just run `./build.sh release`. You can supply a compiler by running `CC=tcc ./build.sh release`, or build it in debug mode without the `release`. To disable compile time foreign function support (which you will need to do if you don't have ffcall/dl), prefix this with `COMPILE_TIME_FOREIGN_FN_SUPPORT=no`.
 
-On other systems, you can just compile main.c with a C compiler. `toc` uses several C99 and a couple of C11 features, so it might not work on all compilers. But it does compile on quite a few, including `clang`, `gcc`, and `tcc`. It can also be compiled as if it were C++, so, MSVC and `g++` can also compile it (it does rely on implicit casting of  `void *` though). The *outputted* code should be C99-compliant.
+On other systems, you can just compile main.c with a C compiler. `toc` uses several C99 and a couple of C11 features, so it might not work on all compilers. But it does compile on quite a few, including `clang`, `gcc`, and `tcc`. It can also be compiled as if it were C++, so and `g++` can also compile it (it does rely on implicit casting of  `void *` though). MSVC can also compile toc. The *outputted* code should be C99-compliant.
 
 #### Why it compiles to C
 
diff --git a/eval.c b/eval.c
index d5603f5..4162776 100644
--- a/eval.c
+++ b/eval.c
@@ -26,116 +26,6 @@ static inline void *evalr_calloc(Evaluator *ev, size_t n, size_t bytes) {
 	return allocr_calloc(ev->allocr, n, bytes);
 }
 
-
-static size_t compiler_sizeof_builtin(BuiltinType b) {
-	switch (b) {
-	case BUILTIN_I8: return sizeof(I8);
-	case BUILTIN_U8: return sizeof(U8);
-	case BUILTIN_I16: return sizeof(I16);
-	case BUILTIN_U16: return sizeof(U16);
-	case BUILTIN_I32: return sizeof(I32);
-	case BUILTIN_U32: return sizeof(U32);
-	case BUILTIN_I64: return sizeof(I64);
-	case BUILTIN_U64: return sizeof(U64);
-	case BUILTIN_F32: return sizeof(F32);
-	case BUILTIN_F64: return sizeof(F64);
-	case BUILTIN_CHAR: return sizeof(char); /* = 1 */
-	case BUILTIN_BOOL: return sizeof(bool);
-	case BUILTIN_TYPE: return sizeof(Type *);
-	case BUILTIN_NMS: return sizeof(Namespace *);
-	}
-	assert(0);
-	return 0;
-}
-
-/* finds offsets and size */
-static void eval_struct_find_offsets(StructDef *s) {
-	if (!(s->flags & STRUCT_DEF_FOUND_OFFSETS)) {
-		size_t bytes = 0;
-		size_t total_align = 0;
-		arr_foreach(s->fields, Field, f) {
-			size_t falign = compiler_alignof(&f->type);
-			if (falign > total_align)
-				total_align = falign;
-			/* align */
-			bytes += ((falign - bytes) % falign + falign) % falign; /* = -bytes mod falign */
-			assert(bytes % falign == 0);
-			f->offset = bytes;
-			/* add size */
-			bytes += compiler_sizeof(&f->type);
-		}
-		bytes += ((total_align - bytes) % total_align + total_align) % total_align; /* = -bytes mod align */
-		s->size = bytes;
-		s->align = total_align;
-		s->flags |= STRUCT_DEF_FOUND_OFFSETS;
-	}
-}
-
-static size_t compiler_alignof(Type *t) {
-	Value v;
-	assert(t->flags & TYPE_IS_RESOLVED);
-	switch (t->kind) {
-	case TYPE_BUILTIN:
-		return compiler_sizeof_builtin(t->builtin);
-	case TYPE_VOID:
-		return 1;
-	case TYPE_FN:
-		return sizeof v.fn;
-	case TYPE_PTR:
-		return sizeof v.ptr;
-	case TYPE_TUPLE:
-		return sizeof v.tuple;
-	case TYPE_ARR:
-		return compiler_alignof(t->arr.of);
-	case TYPE_SLICE:
-		if (sizeof(void *) > sizeof(size_t))
-			return sizeof(void *);
-		else
-			return sizeof(size_t);
-	case TYPE_STRUCT: {
-		/* assume the align of a struct is (at most) the greatest align out of its children's */
-		eval_struct_find_offsets(t->struc);
-		return t->struc->align;
-	}
-	case TYPE_UNKNOWN:
-	case TYPE_EXPR:
-		break;
-	}
-	assert(0);
-	return 0;
-}
-
-/* size of a type at compile time */
-static size_t compiler_sizeof(Type *t) {
-	Value v;
-	assert(t->flags & TYPE_IS_RESOLVED);
-	switch (t->kind) {
-	case TYPE_BUILTIN:
-		return compiler_sizeof_builtin(t->builtin);
-	case TYPE_FN:
-		return sizeof v.fn;
-	case TYPE_PTR:
-		return sizeof v.ptr;
-	case TYPE_ARR:
-		return t->arr.n * compiler_sizeof(t->arr.of);
-	case TYPE_TUPLE:
-		return sizeof v.tuple;
-	case TYPE_SLICE:
-		return sizeof v.slice;
-	case TYPE_STRUCT: {
-		eval_struct_find_offsets(t->struc);
-		return t->struc->size;
-	} break;
-	case TYPE_VOID:
-	case TYPE_UNKNOWN:
-		return 0;
-	case TYPE_EXPR:
-		break;
-	}
-	assert(0);
-	return 0;
-}
-
 static bool builtin_truthiness(Value *v, BuiltinType b) {
 	switch (b) {
 	case BUILTIN_I8: return v->i8 != 0;
@@ -796,8 +686,6 @@ static bool eval_ptr_to_struct_field(Evaluator *ev, Expression *dot_expr, void *
 		struct_type = struct_type->ptr;
 	}
 	if (struct_type->kind == TYPE_STRUCT) {
-		eval_struct_find_offsets(struct_type->struc);
-			
 		Value struc;
 		if (!eval_expr(ev, dot_expr->binary.lhs, &struc))
 			return NULL;
diff --git a/main.c b/main.c
index 503d80b..3a45225 100644
--- a/main.c
+++ b/main.c
@@ -38,6 +38,8 @@ do we need was_expr? (now that, presumably, we have struct arguments)
 any odd number of "s for a string
 make sure futurely/currently-declared types are only used by pointer/slice
 allow omission of trailing ; in foo ::= fn() {...} or foo ::= nms {...} or foo ::= struct { ... }?
+consider- should #sizeof always take a Type? it would be more verbose, but we might not actually need
+	#sizeof that much, given that we have new.
 */
 
 
diff --git a/parse.c b/parse.c
index 90f5fce..a521ae1 100644
--- a/parse.c
+++ b/parse.c
@@ -659,6 +659,7 @@ static bool parse_type(Parser *p, Type *type) {
 						Type *ftype = field_decl.type.kind == TYPE_TUPLE ? &field_decl.type.tuple[idx] : &field_decl.type;
 						Field *f = parser_arr_add(p, &struc->fields);
 						f->name = *fident;
+						f->where = field_decl.where;
 						f->type = *ftype;
 						++idx;
 					}
diff --git a/test.toc b/test.toc
index 11e2a24..88b4e63 100644
--- a/test.toc
+++ b/test.toc
@@ -2,18 +2,18 @@
 // #include "std/io.toc";
 // };
 
-// p ::= struct(x::Type,y::=3) {
-//   b:int;
-// };
-
-foo ::= fn(x::int) Type {
-	[x]int
+FOO ::= fn(t::Type) Type {
+	&ll(int)
 };
 
-z ::= fn(a::=,b:foo(a)) {
+ll ::= struct(t::Type) {
+   head: t;
+   tail: FOO(t);
 };
 
 main ::= fn() {
-	 n:foo(3);
-	 z(n);
+	 l:ll(int);
+	 m:ll(i16);
+	 x::=#alignof(l);
+	 y::=#alignof(m);
 };
\ No newline at end of file
diff --git a/toc.c b/toc.c
index b314187..c574731 100644
--- a/toc.c
+++ b/toc.c
@@ -33,14 +33,24 @@
 #endif
 #endif
 
-#if __STDC_VERSION__ >= 201112
+
+/* use toc_alignof only for non-structs. it may be incorrect for pre-C(++)11. */
+#if __STDC_VERSION__ >= 201112 || __cplusplus >= 201103L
+#include <stdalign.h>
+#define toc_alignof alignof
+
 #ifdef __GNUC__
 /* GCC supports non-string literals as the message for a static assertion */
 #define possibly_static_assert(cond) static_assert(cond, "Assertion " #cond " failed.")
 #else
 #define possibly_static_assert(cond) static_assert(cond, "Assertion failed")
 #endif
+
+
 #else
+
+#define toc_alignof sizeof
+
 #define possibly_static_assert(cond) assert(cond)
 #endif
 
diff --git a/types.c b/types.c
index d6a0d7b..5c154c2 100644
--- a/types.c
+++ b/types.c
@@ -29,6 +29,149 @@ static inline void typer_block_exit(Typer *tr) {
 	tr->block = *(Block **)arr_last(tr->blocks);
 }
 
+
+static size_t compiler_sizeof_builtin(BuiltinType b) {
+	switch (b) {
+	case BUILTIN_I8: return sizeof(I8);
+	case BUILTIN_U8: return sizeof(U8);
+	case BUILTIN_I16: return sizeof(I16);
+	case BUILTIN_U16: return sizeof(U16);
+	case BUILTIN_I32: return sizeof(I32);
+	case BUILTIN_U32: return sizeof(U32);
+	case BUILTIN_I64: return sizeof(I64);
+	case BUILTIN_U64: return sizeof(U64);
+	case BUILTIN_F32: return sizeof(F32);
+	case BUILTIN_F64: return sizeof(F64);
+	case BUILTIN_CHAR: return sizeof(char); /* = 1 */
+	case BUILTIN_BOOL: return sizeof(bool);
+	case BUILTIN_TYPE: return sizeof(Type *);
+	case BUILTIN_NMS: return sizeof(Namespace *);
+	}
+	assert(0);
+	return 0;
+}
+static size_t compiler_alignof_builtin(BuiltinType b) {
+	switch (b) {
+	case BUILTIN_I8: return toc_alignof(I8);
+	case BUILTIN_U8: return toc_alignof(U8);
+	case BUILTIN_I16: return toc_alignof(I16);
+	case BUILTIN_U16: return toc_alignof(U16);
+	case BUILTIN_I32: return toc_alignof(I32);
+	case BUILTIN_U32: return toc_alignof(U32);
+	case BUILTIN_I64: return toc_alignof(I64);
+	case BUILTIN_U64: return toc_alignof(U64);
+	case BUILTIN_F32: return toc_alignof(F32);
+	case BUILTIN_F64: return toc_alignof(F64);
+	case BUILTIN_CHAR: return toc_alignof(char);
+	case BUILTIN_BOOL: return toc_alignof(bool);
+	case BUILTIN_TYPE: return toc_alignof(Type *);
+	case BUILTIN_NMS: return toc_alignof(Namespace *);
+	}
+	assert(0);
+	return 0;
+}
+
+/* finds offsets and size */
+static bool struct_find_offsets(StructDef *s) {
+	/* assume the align of a struct is the greatest align out of its children's */
+	if (!(s->flags & STRUCT_DEF_FOUND_OFFSETS)) {
+		if (s->flags & STRUCT_DEF_FINDING_OFFSETS) {
+			err_print(s->where, "Circular dependency in struct!");
+			return false;
+		}
+		s->flags |= STRUCT_DEF_FINDING_OFFSETS;
+		size_t bytes = 0;
+		size_t total_align = 0;
+		arr_foreach(s->fields, Field, f) {
+			size_t size = compiler_sizeof(&f->type);
+			if (size == SIZE_MAX) {
+				info_print(f->where, "... while descending into this field of a struct.");
+				return false;
+			}
+			size_t falign = compiler_alignof(&f->type);
+			if (falign > total_align)
+				total_align = falign;
+			/* align */
+			bytes += ((falign - bytes) % falign + falign) % falign; /* = -bytes mod falign */
+			assert(bytes % falign == 0);
+			f->offset = bytes;
+			/* add size */
+			bytes += size;
+		}
+		bytes += ((total_align - bytes) % total_align + total_align) % total_align; /* = -bytes mod align */
+		s->size = bytes;
+		s->align = total_align;
+		s->flags |= STRUCT_DEF_FOUND_OFFSETS;
+	}
+	return true;
+}
+
+static size_t compiler_alignof(Type *t) {
+	Value v;
+	assert(t->flags & TYPE_IS_RESOLVED);
+	switch (t->kind) {
+	case TYPE_BUILTIN:
+		return compiler_sizeof_builtin(t->builtin);
+	case TYPE_VOID:
+		return 1;
+	case TYPE_FN:
+		return toc_alignof v.fn;
+	case TYPE_PTR:
+		return toc_alignof v.ptr;
+	case TYPE_TUPLE:
+		return toc_alignof v.tuple;
+	case TYPE_ARR:
+		return compiler_alignof(t->arr.of);
+	case TYPE_SLICE:
+		if (sizeof(void *) > sizeof(size_t))
+			return toc_alignof(void *);
+		else
+			return toc_alignof(size_t);
+	case TYPE_STRUCT:
+		if (!struct_find_offsets(t->struc))
+			return SIZE_MAX;
+		return t->struc->align;
+	case TYPE_UNKNOWN:
+	case TYPE_EXPR:
+		break;
+	}
+	assert(0);
+	return 0;
+}
+
+/* size of a type at compile time */
+static size_t compiler_sizeof(Type *t) {
+	Value v;
+	assert(t->flags & TYPE_IS_RESOLVED);
+	switch (t->kind) {
+	case TYPE_BUILTIN:
+		return compiler_sizeof_builtin(t->builtin);
+	case TYPE_FN:
+		return sizeof v.fn;
+	case TYPE_PTR:
+		return sizeof v.ptr;
+	case TYPE_ARR:
+		return t->arr.n * compiler_sizeof(t->arr.of);
+	case TYPE_TUPLE:
+		return sizeof v.tuple;
+	case TYPE_SLICE:
+		return sizeof v.slice;
+	case TYPE_STRUCT: {
+		if (!struct_find_offsets(t->struc))
+			return SIZE_MAX;
+		return t->struc->size;
+	} break;
+	case TYPE_VOID:
+	case TYPE_UNKNOWN:
+		return 0;
+	case TYPE_EXPR:
+		break;
+	}
+	assert(0);
+	return 0;
+}
+
+
 #define typer_arr_add(tr, a) typer_arr_add_(tr, (void **)(a), sizeof **(a))
 
 static bool type_eq(Type *a, Type *b) {
@@ -431,9 +574,7 @@ static bool type_of_ident(Typer *tr, Location where, Identifier *ident, Type *t)
 			err_print(where, "Variables cannot be captured into inner functions (but constants can).");
 			return false;
 		}
-		if (arr_len(tr->is_reference_stack)
-			&& *(bool *)arr_last(tr->is_reference_stack)
-			&& (d->flags & DECL_HAS_EXPR) && (d->expr.kind == EXPR_TYPE)) {
+		if ((d->flags & DECL_HAS_EXPR) && (d->expr.kind == EXPR_TYPE)) {
 			/* allow using a type before declaring it */
 			t->kind = TYPE_BUILTIN;
 			t->builtin = BUILTIN_TYPE;
@@ -519,7 +660,8 @@ static bool type_of_ident(Typer *tr, Location where, Identifier *ident, Type *t)
 	return true;
 }
 
-static bool type_resolve_(Typer *tr, Type *t, Location where, bool is_reference) {
+/* fixes the type (replaces [5+3]int with [8]int, etc.) */
+static bool type_resolve(Typer *tr, Type *t, Location where) {
 	Evaluator *ev = tr->evalr;
 	if (t->flags & TYPE_IS_RESOLVED) return true;
 	t->was_expr = NULL;
@@ -554,34 +696,34 @@ static bool type_resolve_(Typer *tr, Type *t, Location where, bool is_reference)
 			size = val_to_u64(&val, n_expr->type.builtin);
 		}
 		t->arr.n = (U64)size;
-		if (!type_resolve_(tr, t->arr.of, where, is_reference))
+		if (!type_resolve(tr, t->arr.of, where))
 			return false;
 	} break;
 	case TYPE_FN:
 		arr_foreach(t->fn.types, Type, child_type) {
-			if (!type_resolve_(tr, child_type, where, true))
+			if (!type_resolve(tr, child_type, where))
 				return false;
 		}
 		break;
 	case TYPE_TUPLE:
 		arr_foreach(t->tuple, Type, child_type) {
-			if (!type_resolve_(tr, child_type, where, is_reference))
+			if (!type_resolve(tr, child_type, where))
 				return false;
 		}
 		break;
 	case TYPE_PTR:
-		if (!type_resolve_(tr, t->ptr, where, true))
+		if (!type_resolve(tr, t->ptr, where))
 			return false;
 		break;
 	case TYPE_SLICE:
-		if (!type_resolve_(tr, t->slice, where, true))
+		if (!type_resolve(tr, t->slice, where))
 			return false;
 		break;
 	case TYPE_STRUCT: {
 		if (!(t->struc->flags & STRUCT_DEF_RESOLVED)) {
 			typer_block_enter(tr, &t->struc->scope);
 			arr_foreach(t->struc->fields, Field, f) {
-				if (!type_resolve_(tr, &f->type, where, is_reference)) {
+				if (!type_resolve(tr, &f->type, where)) {
 					typer_block_exit(tr);
 					return false;
 				}
@@ -594,10 +736,8 @@ static bool type_resolve_(Typer *tr, Type *t, Location where, bool is_reference)
 	} break;
 	case TYPE_EXPR: {
 		Value typeval;
-		*(bool *)arr_add(&tr->is_reference_stack) = is_reference;
-		bool success = types_expr(tr, t->expr);
-	    arr_remove_last(&tr->is_reference_stack);
-		if (!success) return false;
+		if (!types_expr(tr, t->expr))
+			return false;
 		if (t->expr->type.kind == TYPE_UNKNOWN && tr->err_ctx->have_errored)
 			return false; /* silently fail (e.g. if a function couldn't be typed) */
 		if (!type_is_builtin(&t->expr->type, BUILTIN_TYPE)) {
@@ -616,25 +756,27 @@ static bool type_resolve_(Typer *tr, Type *t, Location where, bool is_reference)
 				return false;
 			}
 		}
+		if (!(t->flags & TYPE_IS_RESOLVED)) {
+			/* this can happen with functions returning parameterized structs */
+			if (!type_resolve(tr, t, where))
+				return false;
+		}
 		t->was_expr = expr;
-		assert(t->flags & TYPE_IS_RESOLVED);
 	} break;
 	case TYPE_UNKNOWN:
 	case TYPE_VOID:
 	case TYPE_BUILTIN:
 		break;
 	}
+	if (t->kind == TYPE_STRUCT && !!(t->struc->params) == !!(t->struc->instance_id)) { /* don't want it to try to deal with templates */
+		if (!struct_find_offsets(t->struc))
+			return false;
+	}
 	assert(t->kind != TYPE_EXPR);
 	t->flags |= TYPE_IS_RESOLVED;
 	return true;
 }
 
-/* fixes the type (replaces [5+3]int with [8]int, etc.) */
-static bool type_resolve(Typer *tr, Type *t, Location where) {
-	return type_resolve_(tr, t, where, false);
-}
-
-
 
 static bool type_can_be_truthy(Type *t) {
 	assert(t->flags & TYPE_IS_RESOLVED);
@@ -2773,7 +2915,6 @@ static void typer_create(Typer *tr, Evaluator *ev, ErrCtx *err_ctx, Allocator *a
 	tr->in_exprs = NULL;
 	tr->allocr = allocr;
 	tr->globals = idents;
-	tr->is_reference_stack = NULL;
 	*(Block **)arr_adda(&tr->blocks, allocr) = NULL;
 }
 
diff --git a/types.h b/types.h
index f8a0716..2ed4b24 100644
--- a/types.h
+++ b/types.h
@@ -445,6 +445,7 @@ typedef struct Type {
 
 /* field of a struct */
 typedef struct Field {
+	Location where;
 	Identifier name;
 	Type type;
 	size_t offset; /* offset during compile time */
@@ -468,9 +469,10 @@ typedef struct Block {
 
 enum {
 	  STRUCT_DEF_FOUND_OFFSETS = 0x01,
-	  STRUCT_DEF_CGEN_DECLARED = 0x02,
-	  STRUCT_DEF_CGEN_DEFINED = 0x04,
-	  STRUCT_DEF_RESOLVED = 0x08
+	  STRUCT_DEF_FINDING_OFFSETS = 0x02,
+	  STRUCT_DEF_CGEN_DECLARED = 0x04,
+	  STRUCT_DEF_CGEN_DEFINED = 0x08,
+	  STRUCT_DEF_RESOLVED = 0x10
 };
 typedef struct StructDef {
 	Field *fields;
@@ -907,8 +909,6 @@ typedef struct Typer {
 	Block **blocks; /* dyn array of all the block's we're in ([0] = NULL for global scope) */
 	FnExpr *fn; /* the function we're currently parsing. */
 	ErrCtx *err_ctx;
-	/* for checking for problematic struct circular dependencies */
-	bool *is_reference_stack;
 	ParsedFile *parsed_file;
 	Namespace *nms;
 } Typer;