From 673b993783f99bf4317215cf967d0db534112823 Mon Sep 17 00:00:00 2001 From: Leo Tenenbaum Date: Sun, 17 Nov 2019 00:05:35 -0500 Subject: moved constant param system to typing. --- allocator.c | 2 +- cgen.c | 88 +++++++++------ decls_cgen.c | 69 +----------- hash_tables.c | 321 ------------------------------------------------------- instance_table.c | 291 +++++++++++++++++++++++++++++++++++++++++++++++++ main.c | 3 +- parse.c | 5 + runv | 2 +- test.toc | 25 +++-- tests.c | 1 - toc.c | 2 +- tokenizer.c | 2 +- typedefs_cgen.c | 3 +- types.c | 58 ++++++++-- types.h | 22 ++-- 15 files changed, 441 insertions(+), 453 deletions(-) delete mode 100644 hash_tables.c create mode 100644 instance_table.c diff --git a/allocator.c b/allocator.c index f47cc97..e49ea3e 100644 --- a/allocator.c +++ b/allocator.c @@ -1,4 +1,4 @@ -/* #define NO_ALLOCATOR 0 /\* useful for debugging; valgrind checks writing past the end of a malloc, but that won't work with an allocator *\/ */ +#define NO_ALLOCATOR 1 /* useful for debugging; valgrind (maybe) checks writing past the end of a malloc, but that won't work with an allocator */ /* number of bytes a page hold, not including the header */ #define PAGE_BYTES (16384 - sizeof(Page)) #define PAGE_MAX_ALIGNS (PAGE_BYTES / sizeof(MaxAlign)) diff --git a/cgen.c b/cgen.c index 9f5b62c..ccc84ae 100644 --- a/cgen.c +++ b/cgen.c @@ -1,4 +1,3 @@ - static void cgen_create(CGenerator *g, FILE *out, Identifiers *ids, Evaluator *ev, Allocator *allocr) { g->outc = out; g->ident_counter = 1; /* some places use 0 to mean no id */ @@ -25,9 +24,10 @@ static bool cgen_val(CGenerator *g, Value v, Type *t, Location where); static bool cgen_val_pre(CGenerator *g, Value v, Type *t, Location where); static bool cgen_val_ptr(CGenerator *g, void *v, Type *t, Location where); static bool cgen_defs_block(CGenerator *g, Block *b); +static bool cgen_defs_decl(CGenerator *g, Declaration *d); -/* calls f on every sub-expression of e, and block_f on every sub-block. */ -#define cgen_recurse_subexprs(g, e, f, block_f) \ +/* calls f on every sub-expression of e, block_f on every sub-block, and decl_f on every sub-declaration. */ +#define cgen_recurse_subexprs(g, e, f, block_f, decl_f) \ switch (e->kind) { \ case EXPR_TYPE: \ case EXPR_VAL: \ @@ -112,6 +112,12 @@ static bool cgen_defs_block(CGenerator *g, Block *b); break; \ case EXPR_FN: \ if (!fn_enter(&e->fn, 0)) return false; \ + arr_foreach(e->fn.params, Declaration, param) \ + if (!decl_f(g, param)) \ + return false; \ + arr_foreach(e->fn.ret_decls, Declaration, r) \ + if (!decl_f(g, r)) \ + return false; \ if (!block_f(g, &e->fn.body)) \ return false; \ fn_exit(&e->fn); \ @@ -413,7 +419,7 @@ static inline void cgen_fn_name(CGenerator *g, FnExpr *f) { } /* unless f has const/semi-const args, instance and which_are_const can be set to 0 */ -static bool cgen_fn_header(CGenerator *g, FnExpr *f, Location where, I64 instance, U64 which_are_const) { +static bool cgen_fn_header(CGenerator *g, FnExpr *f, Location where, U64 instance, U64 which_are_const) { bool out_param = cgen_uses_ptr(&f->ret_type); bool any_params = false; if (!f->c.name) /* anonymous fn */ @@ -426,20 +432,22 @@ static bool cgen_fn_header(CGenerator *g, FnExpr *f, Location where, I64 instanc } cgen_fn_name(g, f); if (instance) { - cgen_write(g, "%"PRId64, instance); + cgen_write(g, "%"PRIu64, instance); } if (!out_param) { if (!cgen_type_post(g, &f->ret_type, where)) return false; } cgen_write(g, "("); int semi_const_idx = 0; + bool any_args = false; arr_foreach(f->params, Declaration, d) { if (!(d->flags & DECL_IS_CONST) && !((d->flags & DECL_SEMI_CONST) && (which_are_const & (((U64)1) << semi_const_idx++)))) { long idx = 0; arr_foreach(d->idents, Identifier, i) { - if (d != f->params || i != d->idents) + if (any_args) cgen_write(g, ", "); + any_args = true; Type *type = d->type.kind == TYPE_TUPLE ? &d->type.tuple[idx++] : &d->type; any_params = true; if (!cgen_type_pre(g, type, where)) @@ -451,7 +459,8 @@ static bool cgen_fn_header(CGenerator *g, FnExpr *f, Location where, I64 instanc } } } - if (out_param) { + if (out_param) { + any_args = true; if (f->ret_type.kind == TYPE_TUPLE) { /* multiple return variables */ for (size_t i = 0; i < arr_len(f->ret_type.tuple); i++) { @@ -472,7 +481,7 @@ static bool cgen_fn_header(CGenerator *g, FnExpr *f, Location where, I64 instanc return false; } } - if (!out_param && arr_len(f->params) == 0) + if (!any_args) cgen_write(g, "void"); cgen_write(g, ")"); return true; @@ -589,8 +598,8 @@ static bool cgen_set_tuple(CGenerator *g, Expression *exprs, Identifier *idents, case EXPR_CALL: { /* e.g. a, b = fn_which_returns_tuple(); */ if (!cgen_expr(g, to->call.fn)) return false; - if (to->call.c.instance) - cgen_write(g, "%"PRId64, to->call.c.instance); + if (to->call.instance) + cgen_write(g, "%"PRIu64, to->call.instance->c.id); cgen_write(g, "("); bool any_args = false; Constness *constness = to->call.fn->type.fn.constness; @@ -956,8 +965,8 @@ static bool cgen_expr_pre(CGenerator *g, Expression *e) { if (!cgen_type_post(g, &e->type, e->where)) return false; cgen_write(g, ";"); cgen_nl(g); if (!cgen_expr(g, e->call.fn)) return false; - if (e->call.c.instance) { - cgen_write(g, "%"PRId64, e->call.c.instance); + if (e->call.instance) { + cgen_write(g, "%"PRIu64, e->call.instance->c.id); } cgen_write(g, "("); bool any_args = false; @@ -1315,8 +1324,8 @@ static bool cgen_expr(CGenerator *g, Expression *e) { cgen_write(g, "("); if (!cgen_expr(g, e->call.fn)) return false; - if (e->call.c.instance) { - cgen_write(g, "%"PRId64, e->call.c.instance); + if (e->call.instance) { + cgen_write(g, "%"PRIu64, e->call.instance->c.id); } cgen_write(g, "("); bool first_arg = true; @@ -1455,7 +1464,7 @@ static void cgen_zero_value(CGenerator *g, Type *t) { } /* pass 0 for instance and NULL for compile_time_args if there are no compile time arguments. */ -static bool cgen_fn(CGenerator *g, FnExpr *f, Location where, I64 instance, Value *compile_time_args) { +static bool cgen_fn(CGenerator *g, FnExpr *f, Location where, U64 instance, Value *compile_time_args) { /* see also cgen_defs_expr */ FnExpr *prev_fn = g->fn; Block *prev_block = g->block; @@ -1482,15 +1491,26 @@ static bool cgen_fn(CGenerator *g, FnExpr *f, Location where, I64 instance, Valu arr_foreach(param->idents, Identifier, ident) { Type *type = param->type.kind == TYPE_TUPLE ? ¶m->type.tuple[i] : ¶m->type; - if (!cgen_val_pre(g, compile_time_args[carg_idx], type, where)) - return false; - if (!cgen_type_pre(g, type, where)) return false; - cgen_write(g, " const "); - cgen_ident(g, *ident); - if (!cgen_type_post(g, type, where)) return false; - cgen_write(g, " = "); - if (!cgen_val(g, compile_time_args[carg_idx], type, where)) - return false; + Value arg = compile_time_args[carg_idx]; + if (type->kind == TYPE_TYPE) { + cgen_write(g, "typedef "); + if (!cgen_type_pre(g, arg.type, where)) + return false; + cgen_write(g, " "); + cgen_ident(g, *ident); + if (!cgen_type_post(g, arg.type, where)) + return false; + } else { + if (!cgen_val_pre(g, arg, type, where)) + return false; + if (!cgen_type_pre(g, type, where)) return false; + cgen_write(g, " const "); + cgen_ident(g, *ident); + if (!cgen_type_post(g, type, where)) return false; + cgen_write(g, " = "); + if (!cgen_val(g, arg, type, where)) + return false; + } cgen_write(g, ";"); cgen_nl(g); carg_idx++; @@ -1812,16 +1832,14 @@ static bool cgen_defs_expr(CGenerator *g, Expression *e) { } } if (fn_type->constness) { - HashTable *instances = f->c.instances; - if (instances) { - /* generate each instance */ - ValNumPair *pairs = instances->data; - for (U64 i = 0; i < instances->cap; i++) { - if (instances->occupied[i]) { - /* generate this instance */ - if (!cgen_fn(g, f, e->where, pairs[i].num, pairs[i].val.tuple)) - return false; - } + HashTable *instances = &f->instances; + /* generate each instance */ + Instance **is = instances->data; + for (U64 i = 0; i < instances->cap; i++) { + if (instances->occupied[i]) { + /* generate this instance */ + if (!cgen_fn(g, f, e->where, is[i]->c.id, is[i]->val.tuple)) + return false; } } } @@ -1831,7 +1849,7 @@ static bool cgen_defs_expr(CGenerator *g, Expression *e) { } } - cgen_recurse_subexprs(g, e, cgen_defs_expr, cgen_defs_block); + cgen_recurse_subexprs(g, e, cgen_defs_expr, cgen_defs_block, cgen_defs_decl); return true; } diff --git a/decls_cgen.c b/decls_cgen.c index 6b52291..1df359d 100644 --- a/decls_cgen.c +++ b/decls_cgen.c @@ -1,75 +1,10 @@ static bool cgen_decls_stmt(CGenerator *g, Statement *s); static bool cgen_decls_block(CGenerator *g, Block *b); +static bool cgen_decls_decl(CGenerator *g, Declaration *d); static bool cgen_decls_expr(CGenerator *g, Expression *e) { - cgen_recurse_subexprs(g, e, cgen_decls_expr, cgen_decls_block); + cgen_recurse_subexprs(g, e, cgen_decls_expr, cgen_decls_block, cgen_decls_decl); switch (e->kind) { - case EXPR_CALL: { - e->call.c.instance = 0; - assert(e->call.fn->type.kind == TYPE_FN); - FnType *fn_type = &e->call.fn->type.fn; - if (fn_type->constness) { - Value fval; - /* e->call.fn had better be a compile-time constant if it has compile-time arguments */ - if (!eval_expr(g->evalr, e->call.fn, &fval)) - return false; - FnExpr *f = fval.fn; - /* directly calling a function; might need to generate a copy of this function */ - - /* OPTIM should we really be constructing a tuple & type every time? */ - Value *compile_time_args = NULL; - Type *tuple_types = NULL; - size_t nparams = arr_len(fn_type->types)-1; - Value *which_are_const_val = arr_add(&compile_time_args); - U64 *which_are_const = &which_are_const_val->u64; - Type *u64t = arr_add(&tuple_types); - u64t->kind = TYPE_BUILTIN; - u64t->flags = TYPE_IS_RESOLVED; - u64t->builtin = BUILTIN_U64; - *which_are_const = 0; - int semi_const_arg_index = 0; - for (size_t i = 0; i < nparams; i++) { - Expression *arg = &e->call.arg_exprs[i]; - if (arg_is_const(arg, fn_type->constness[i])) { - if (fn_type->constness[i] == CONSTNESS_SEMI) { - if (semi_const_arg_index >= 64) { - err_print(e->where, "You can't have more than 64 semi-constant parameters in a function at the moment."); - return false; - } - *which_are_const |= ((U64)1) << semi_const_arg_index; - semi_const_arg_index++; - } - assert(arg->kind == EXPR_VAL); /* should have been evaluated by types.c */ - *(Value *)arr_adda(&compile_time_args, g->allocr) = arg->val; - *(Type *)arr_add(&tuple_types) = arg->type; - i++; - } - } - if (compile_time_args) { - Value tuple; - Type tuple_type; - tuple.tuple = compile_time_args; - tuple_type.kind = TYPE_TUPLE; - tuple_type.flags = TYPE_IS_RESOLVED; - tuple_type.tuple = tuple_types; - if (!f->c.instances) { - f->c.instances = allocr_calloc(g->allocr, 1, sizeof *f->c.instances); - } - /* lookup compile time arguments */ - I64 instance_number = (I64)f->c.instances->n + 1; - bool already_generated_decl = val_hash_table_adda(g->allocr, f->c.instances, tuple, &tuple_type, &instance_number); - if (!already_generated_decl) { - /* generate a copy of this function */ - if (!cgen_fn_header(g, f, e->where, instance_number, *which_are_const)) - return false; - cgen_write(g, ";"); - cgen_nl(g); - } - arr_clear(&tuple_types); - e->call.c.instance = (U32)instance_number; - } - } - } break; case EXPR_FN: e->fn.c.name = NULL; if (!e->fn.c.id) diff --git a/hash_tables.c b/hash_tables.c deleted file mode 100644 index 58ccbfd..0000000 --- a/hash_tables.c +++ /dev/null @@ -1,321 +0,0 @@ -/* - hash tables are initialized by setting them to {0}, e.g. - HashTable x = {0}; -*/ -static void *val_get_ptr(Value *v, Type *t); -static U64 val_hash(Value v, Type *t); -static size_t compiler_sizeof(Type *t); -static bool val_eq(Value u, Value v, Type *t); -static bool type_eq(Type *t1, Type *t2); - -static U64 f32_hash(F32 f) { - /* OPTIM */ - U64 hash = 0; - if (f < 0) { - hash = 0x9a6db29edcba8af4; - f = -f; - } - F32 last = f; - int exponent = 0; - while (f > 1) { - exponent++; - f /= 10; - if (f == last) { - /* +/- infinity probably */ - hash ^= 0x78bf61a81e80b9f2; - return hash; - } - last = f; - } - for (int i = 0; i < F32_MANT_DIG; i++) { - f *= 10; - } - hash ^= (U64)exponent + (U64)F32_DIG * (U64)f; - return hash; -} - -static U64 f64_hash(F64 f) { - /* OPTIM */ - U64 hash = 0; - if (f < 0) { - hash = 0x9a6db29edcba8af4; - f = -f; - } - F64 last = f; - int exponent = 0; - while (f > 1) { - exponent++; - f /= 10; - if (f == last) { - /* +/- infinity probably */ - hash ^= 0x78bf61a81e80b9f2; - return hash; - } - last = f; - } - for (int i = 0; i < F64_MANT_DIG; i++) { - f *= 10; - } - hash ^= (U64)exponent + (U64)F64_DIG * (U64)f; - return hash; -} - -static void fprint_val(FILE *f, Value v, Type *t); /* DELME */ -static void fprint_type(FILE *out, Type *t); /* !! */ -/* Note that for these value hashing functions, values of different types may collide */ -static U64 val_ptr_hash(void *v, Type *t) { - switch (t->kind) { - case TYPE_VOID: return 0; - case TYPE_UNKNOWN: return 0; - case TYPE_BUILTIN: - switch (t->builtin) { - case BUILTIN_I8: return (U64)*(I8 *)v; - case BUILTIN_U8: return (U64)*(U8 *)v; - case BUILTIN_I16: return (U64)*(I16 *)v; - case BUILTIN_U16: return (U64)*(U16 *)v; - case BUILTIN_I32: return (U64)*(I32 *)v; - case BUILTIN_U32: return (U64)*(U32 *)v; - case BUILTIN_I64: return (U64)*(I64 *)v; - case BUILTIN_U64: return (U64)*(U64 *)v; - case BUILTIN_F32: return f32_hash(*(F32 *)v); - case BUILTIN_F64: return f64_hash(*(F64 *)v); - case BUILTIN_CHAR: return (U64)*(char *)v; - case BUILTIN_BOOL: return (U64)*(bool *)v; - } - assert(0); - return 0; - case TYPE_FN: return (U64)*(FnExpr **)v; - case TYPE_TUPLE: { - U64 hash = 0; - Value *elems = *(Value **)v; - U32 x = 1; - for (U64 i = 0; i < (U64)arr_len(t->tuple); i++) { - hash += (U64)x * val_hash(elems[i], &t->tuple[i]); - x = rand_u32(x); - } - return hash; - } - case TYPE_PTR: return (U64)*(void **)v; - case TYPE_TYPE: return (U64)*(Type **)v; - case TYPE_USER: return val_ptr_hash(v, type_inner(t)); - case TYPE_ARR: { - U32 x = 1; - U64 hash = 0; - U64 size = (U64)compiler_sizeof(t->arr.of); - for (U64 i = 0; i < (U64)t->arr.n; i++) { - hash += (U64)x * val_ptr_hash((char *)v + i * size, t->arr.of); - x = rand_u32(x); - } - return hash; - } - case TYPE_SLICE: { - U32 x = 1; - U64 hash = 0; - Slice *s = v; - U64 size = (U64)compiler_sizeof(t->slice); - for (U64 i = 0; i < (U64)s->n; i++) { - hash += (U64)x * val_ptr_hash((char *)s->data + i * size, t->slice); - x = rand_u32(x); - } - return hash; - } - case TYPE_STRUCT: { - U32 x = 1; - U64 hash = 0; - arr_foreach(t->struc.fields, Field, f) { - hash += (U64)x * val_ptr_hash((char *)v + f->offset, f->type); - x = rand_u32(x); - } - return hash; - } - } - assert(0); - return 0; -} - -static U64 val_hash(Value v, Type *t) { - return val_ptr_hash(val_get_ptr(&v, t), t); -} - -static bool val_ptr_eq(void *u, void *v, Type *t) { - switch (t->kind) { - case TYPE_BUILTIN: - switch (t->builtin) { - case BUILTIN_I8: return *(I8 *)u == *(I8 *)v; - case BUILTIN_U8: return *(U8 *)u == *(U8 *)v; - case BUILTIN_I16: return *(I16 *)u == *(I16 *)v; - case BUILTIN_U16: return *(U16 *)u == *(U16 *)v; - case BUILTIN_I32: return *(I32 *)u == *(I32 *)v; - case BUILTIN_U32: return *(U32 *)u == *(U32 *)v; - case BUILTIN_I64: return *(I64 *)u == *(I64 *)v; - case BUILTIN_U64: return *(U64 *)u == *(U64 *)v; - case BUILTIN_F32: return *(F32 *)u == *(F32 *)v; - case BUILTIN_F64: return *(F64 *)u == *(F64 *)v; - case BUILTIN_BOOL: return *(bool *)u == *(bool *)v; - case BUILTIN_CHAR: return *(char *)u == *(char *)v; - } - break; - case TYPE_VOID: - return true; - case TYPE_UNKNOWN: - return false; - case TYPE_FN: - return *(FnExpr **)u == *(FnExpr **)v; - case TYPE_USER: - return val_ptr_eq(u, v, type_inner(t)); - case TYPE_PTR: - return *(void **)u == *(void **)v; - case TYPE_TYPE: - return type_eq(*(Type **)u, *(Type **)v); - case TYPE_TUPLE: { - Value *us = *(Value **)u; - Value *vs = *(Value **)v; - for (size_t i = 0; i < arr_len(t->tuple); i++) { - if (!val_eq(us[i], vs[i], &t->tuple[i])) - return false; - } - return true; - } - case TYPE_ARR: { - U64 size = (U64)compiler_sizeof(t->arr.of); - char *uptr = u, *vptr = v; - for (U64 i = 0; i < t->arr.n; i++) { - if (!val_ptr_eq(uptr, vptr, t->arr.of)) - return false; - uptr += size; - vptr += size; - } - return true; - } - case TYPE_SLICE: { - U64 size = (U64)compiler_sizeof(t->arr.of); - Slice *r = u; - Slice *s = v; - if (r->n != s->n) return false; - char *sptr = r->data, *tptr = s->data; - for (U64 i = 0; i < (U64)s->n; i++) { - if (!val_ptr_eq(sptr, tptr, t->slice)) - return false; - sptr += size; - tptr += size; - } - return true; - } - case TYPE_STRUCT: - arr_foreach(t->struc.fields, Field, f) { - if (!val_ptr_eq((char *)u + f->offset, (char *)v + f->offset, f->type)) - return false; - } - return true; - } - assert(0); - return false; -} - -static bool val_eq(Value u, Value v, Type *t) { - return val_ptr_eq(val_get_ptr(&u, t), val_get_ptr(&v, t), t); -} - -/* - for a value hash table, you must either ALWAYS or NEVER use an allocator - all values in the hash table must have the same type. - returns true iff the value was already present, and sets associated_number accordingly. - otherwise, associates the value with associated_number, and returns false. -*/ -static bool val_hash_table_adda(Allocator *a, HashTable *h, Value v, Type *t, I64 *associated_number) { - if (h->n * 2 >= h->cap) { - U64 new_cap = h->cap * 2 + 2; - ValNumPair *new_data = a ? allocr_malloc(a, (size_t)new_cap * sizeof *new_data) - : malloc((size_t)new_cap * sizeof *new_data); - bool *new_occupied = a ? allocr_calloc(a, (size_t)new_cap, sizeof *new_occupied) - : calloc((size_t)new_cap, sizeof *new_occupied); - ValNumPair *old_data = h->data; - bool *old_occupied = h->occupied; - for (U64 i = 0; i < h->cap; i++) { - /* re-hash */ - if (old_occupied[i]) { - U64 index = val_hash(old_data[i].val, t) % new_cap; - while (new_occupied[index]) { - index++; - if (index >= new_cap) - index -= new_cap; - } - new_data[index] = old_data[i]; - new_occupied[index] = true; - } - } - h->data = new_data; - h->occupied = new_occupied; - if (a) { - allocr_free(a, old_occupied, h->cap * sizeof *old_occupied); - allocr_free(a, old_data, h->cap * sizeof *old_data); - } else { - free(old_occupied); - free(old_data); - } - h->cap = new_cap; - } - ValNumPair *data = h->data; - U64 index = val_hash(v, t) % h->cap; - while (1) { - if (h->occupied[index]) { - if (val_eq(v, data[index].val, t)) { - *associated_number = data[index].num; - return true; - } - } else break; - index++; - if (index >= h->cap) - index -= h->cap; - } - data[index].val = v; - data[index].num = *associated_number; - h->occupied[index] = true; - h->n++; - return false; -} - -/* see above */ -static bool val_hash_table_add(HashTable *h, Value v, Type *t, I64 *associated_number) { - return val_hash_table_adda(NULL, h, v, t, associated_number); -} - -/* only call if you're not using an allocator */ -static void hash_table_free(HashTable *h) { - free(h->data); - free(h->occupied); -} - -static void val_hash_table_test(void) { - HashTable h = {0}; - Type type; - type.kind = TYPE_BUILTIN; - type.builtin = BUILTIN_I64; - type.flags = TYPE_IS_RESOLVED; - for (I64 n = 0; n < 100; n++) { - Value v = {.i64 = n * n}; - if (val_hash_table_add(&h, v, &type, &n)) { - assert(!*"n*n already exists."); - } - } - for (I64 n = 0; n < 100; n++) { - Value v = {.i64 = n * n}; - I64 m = 0; - if (!val_hash_table_add(&h, v, &type, &m)) { - assert(!*"n*n does not exist."); - } - if (m != n) { - assert(!*"n*n exists, but has wrong associated value."); - } - } - I64 x = 100; - Value v = {.i64 = 8}; - if (val_hash_table_add(&h, v, &type, &x)) { - assert(!*"8 exists"); - } - hash_table_free(&h); -} - -static void hash_table_test(void) { - val_hash_table_test(); -} diff --git a/instance_table.c b/instance_table.c new file mode 100644 index 0000000..5da4a77 --- /dev/null +++ b/instance_table.c @@ -0,0 +1,291 @@ +/* + hash tables are initialized by setting them to {0}, e.g. + HashTable x = {0}; +*/ +static void *val_get_ptr(Value *v, Type *t); +static U64 val_hash(Value v, Type *t); +static size_t compiler_sizeof(Type *t); +static bool val_eq(Value u, Value v, Type *t); +static bool type_eq(Type *t1, Type *t2); + +static U64 f32_hash(F32 f) { + /* OPTIM */ + U64 hash = 0; + if (f < 0) { + hash = 0x9a6db29edcba8af4; + f = -f; + } + F32 last = f; + int exponent = 0; + while (f > 1) { + exponent++; + f /= 10; + if (f == last) { + /* +/- infinity probably */ + hash ^= 0x78bf61a81e80b9f2; + return hash; + } + last = f; + } + for (int i = 0; i < F32_MANT_DIG; i++) { + f *= 10; + } + hash ^= (U64)exponent + (U64)F32_DIG * (U64)f; + return hash; +} + +static U64 f64_hash(F64 f) { + /* OPTIM */ + U64 hash = 0; + if (f < 0) { + hash = 0x9a6db29edcba8af4; + f = -f; + } + F64 last = f; + int exponent = 0; + while (f > 1) { + exponent++; + f /= 10; + if (f == last) { + /* +/- infinity probably */ + hash ^= 0x78bf61a81e80b9f2; + return hash; + } + last = f; + } + for (int i = 0; i < F64_MANT_DIG; i++) { + f *= 10; + } + hash ^= (U64)exponent + (U64)F64_DIG * (U64)f; + return hash; +} + +static void fprint_val(FILE *f, Value v, Type *t); /* DELME */ +static void fprint_type(FILE *out, Type *t); /* !! */ +/* Note that for these value hashing functions, values of different types may collide */ +static U64 val_ptr_hash(void *v, Type *t) { + switch (t->kind) { + case TYPE_VOID: return 0; + case TYPE_UNKNOWN: return 0; + case TYPE_BUILTIN: + switch (t->builtin) { + case BUILTIN_I8: return (U64)*(I8 *)v; + case BUILTIN_U8: return (U64)*(U8 *)v; + case BUILTIN_I16: return (U64)*(I16 *)v; + case BUILTIN_U16: return (U64)*(U16 *)v; + case BUILTIN_I32: return (U64)*(I32 *)v; + case BUILTIN_U32: return (U64)*(U32 *)v; + case BUILTIN_I64: return (U64)*(I64 *)v; + case BUILTIN_U64: return (U64)*(U64 *)v; + case BUILTIN_F32: return f32_hash(*(F32 *)v); + case BUILTIN_F64: return f64_hash(*(F64 *)v); + case BUILTIN_CHAR: return (U64)*(char *)v; + case BUILTIN_BOOL: return (U64)*(bool *)v; + } + assert(0); + return 0; + case TYPE_FN: return (U64)*(FnExpr **)v; + case TYPE_TUPLE: { + U64 hash = 0; + Value *elems = *(Value **)v; + U32 x = 1; + for (U64 i = 0; i < (U64)arr_len(t->tuple); i++) { + hash += (U64)x * val_hash(elems[i], &t->tuple[i]); + x = rand_u32(x); + } + return hash; + } + case TYPE_PTR: return (U64)*(void **)v; + case TYPE_TYPE: return (U64)*(Type **)v; + case TYPE_USER: return val_ptr_hash(v, type_inner(t)); + case TYPE_ARR: { + U32 x = 1; + U64 hash = 0; + U64 size = (U64)compiler_sizeof(t->arr.of); + for (U64 i = 0; i < (U64)t->arr.n; i++) { + hash += (U64)x * val_ptr_hash((char *)v + i * size, t->arr.of); + x = rand_u32(x); + } + return hash; + } + case TYPE_SLICE: { + U32 x = 1; + U64 hash = 0; + Slice *s = v; + U64 size = (U64)compiler_sizeof(t->slice); + for (U64 i = 0; i < (U64)s->n; i++) { + hash += (U64)x * val_ptr_hash((char *)s->data + i * size, t->slice); + x = rand_u32(x); + } + return hash; + } + case TYPE_STRUCT: { + U32 x = 1; + U64 hash = 0; + arr_foreach(t->struc.fields, Field, f) { + hash += (U64)x * val_ptr_hash((char *)v + f->offset, f->type); + x = rand_u32(x); + } + return hash; + } + } + assert(0); + return 0; +} + +static U64 val_hash(Value v, Type *t) { + return val_ptr_hash(val_get_ptr(&v, t), t); +} + +static bool val_ptr_eq(void *u, void *v, Type *t) { + switch (t->kind) { + case TYPE_BUILTIN: + switch (t->builtin) { + case BUILTIN_I8: return *(I8 *)u == *(I8 *)v; + case BUILTIN_U8: return *(U8 *)u == *(U8 *)v; + case BUILTIN_I16: return *(I16 *)u == *(I16 *)v; + case BUILTIN_U16: return *(U16 *)u == *(U16 *)v; + case BUILTIN_I32: return *(I32 *)u == *(I32 *)v; + case BUILTIN_U32: return *(U32 *)u == *(U32 *)v; + case BUILTIN_I64: return *(I64 *)u == *(I64 *)v; + case BUILTIN_U64: return *(U64 *)u == *(U64 *)v; + case BUILTIN_F32: return *(F32 *)u == *(F32 *)v; + case BUILTIN_F64: return *(F64 *)u == *(F64 *)v; + case BUILTIN_BOOL: return *(bool *)u == *(bool *)v; + case BUILTIN_CHAR: return *(char *)u == *(char *)v; + } + break; + case TYPE_VOID: + return true; + case TYPE_UNKNOWN: + return false; + case TYPE_FN: + return *(FnExpr **)u == *(FnExpr **)v; + case TYPE_USER: + return val_ptr_eq(u, v, type_inner(t)); + case TYPE_PTR: + return *(void **)u == *(void **)v; + case TYPE_TYPE: + return type_eq(*(Type **)u, *(Type **)v); + case TYPE_TUPLE: { + Value *us = *(Value **)u; + Value *vs = *(Value **)v; + for (size_t i = 0; i < arr_len(t->tuple); i++) { + if (!val_eq(us[i], vs[i], &t->tuple[i])) + return false; + } + return true; + } + case TYPE_ARR: { + U64 size = (U64)compiler_sizeof(t->arr.of); + char *uptr = u, *vptr = v; + for (U64 i = 0; i < t->arr.n; i++) { + if (!val_ptr_eq(uptr, vptr, t->arr.of)) + return false; + uptr += size; + vptr += size; + } + return true; + } + case TYPE_SLICE: { + U64 size = (U64)compiler_sizeof(t->arr.of); + Slice *r = u; + Slice *s = v; + if (r->n != s->n) return false; + char *sptr = r->data, *tptr = s->data; + for (U64 i = 0; i < (U64)s->n; i++) { + if (!val_ptr_eq(sptr, tptr, t->slice)) + return false; + sptr += size; + tptr += size; + } + return true; + } + case TYPE_STRUCT: + arr_foreach(t->struc.fields, Field, f) { + if (!val_ptr_eq((char *)u + f->offset, (char *)v + f->offset, f->type)) + return false; + } + return true; + } + assert(0); + return false; +} + +static bool val_eq(Value u, Value v, Type *t) { + return val_ptr_eq(val_get_ptr(&u, t), val_get_ptr(&v, t), t); +} + +/* + if already_exists is not NULL, this will create the instance if it does not exist, + and set already_exists accordingly +*/ +/* OPTIM: store instances in a block array (remember that the pointers need to stay valid!) */ +static Instance *instance_table_adda(Allocator *a, HashTable *h, Value v, Type *t, + bool *already_exists) { + if (h->n * 2 >= h->cap) { + U64 new_cap = h->cap * 2 + 3; + Instance **new_data = a ? allocr_malloc(a, (size_t)new_cap * sizeof *new_data) + : malloc((size_t)new_cap * sizeof *new_data); + bool *new_occupied = a ? allocr_calloc(a, (size_t)new_cap, sizeof *new_occupied) + : calloc((size_t)new_cap, sizeof *new_occupied); + Instance **old_data = h->data; + bool *old_occupied = h->occupied; + for (U64 i = 0; i < h->cap; i++) { + /* re-hash */ + if (old_occupied[i]) { + U64 index = val_hash(old_data[i]->val, t) % new_cap; + while (new_occupied[index]) { + index++; + if (index >= new_cap) + index -= new_cap; + } + new_data[index] = old_data[i]; + new_occupied[index] = true; + } + } + h->data = new_data; + h->occupied = new_occupied; + if (a) { + allocr_free(a, old_occupied, h->cap * sizeof *old_occupied); + allocr_free(a, old_data, h->cap * sizeof *old_data); + } else { + free(old_occupied); + free(old_data); + } + h->cap = new_cap; + } + Instance **data = h->data; + U64 index = val_hash(v, t) % h->cap; + while (1) { + if (h->occupied[index]) { + if (val_eq(v, data[index]->val, t)) { + *already_exists = true; + return data[index]; + } + } else break; + index++; + if (index >= h->cap) + index -= h->cap; + } + if (already_exists) { + /* create, because it doesn't exist */ + *already_exists = false; + data[index] = a ? allocr_malloc(a, sizeof *data[index]) + : malloc(sizeof *data[index]); + data[index]->val = v; + h->occupied[index] = true; + h->n++; + return data[index]; + } + return NULL; +} + + +#if 0 +/* only call if you're not using an allocator */ +static void hash_table_free(HashTable *h) { + free(h->data); + free(h->occupied); +} +#endif diff --git a/main.c b/main.c index 4686fec..3726f67 100644 --- a/main.c +++ b/main.c @@ -1,6 +1,7 @@ /* TODO: -type parameters (e.g. fn(foo @ type) {x: foo;}) +declarations of things with constant params +deal with typing functions with type parameters (we need to type every single instance) struct parameters don't allow while {3; 5} (once break is added) diff --git a/parse.c b/parse.c index 24c56b5..6f6357a 100644 --- a/parse.c +++ b/parse.c @@ -389,6 +389,11 @@ static bool parse_type(Parser *p, Type *type) { } } /* Not a builtin */ + if (t->token->kw == KW_TYPE) { + type->kind = TYPE_TYPE; + t->token++; + break; + } switch (t->token->kw) { case KW_FN: { /* function type */ diff --git a/runv b/runv index c9e5a58..b0a02f7 100755 --- a/runv +++ b/runv @@ -1,5 +1,5 @@ #!/bin/sh -valgrind -q --track-origins=yes --error-exitcode=1 ./toc test.toc || exit 1 +valgrind -q --track-origins=yes --error-exitcode=1 --malloc-fill=0xcd ./toc test.toc || exit 1 if [ "$1" = "c" ]; then gcc out.c && ./a.out elif [ "$1" = "pc" ]; then diff --git a/test.toc b/test.toc index 5ae33fd..fbc7272 100644 --- a/test.toc +++ b/test.toc @@ -6,13 +6,24 @@ puti @= fn(x: int) { // #C("printf(\"%f\\n\", (double)x); // "); // }; -// f@= fn(x: int, y :@ int) int { -// x+y -// }; - -asdf @= fn(x :@= 18) int { x }; +f@= fn(x : int, y :@ int) int { + x+y +}; main @= fn() { - something := asdf; - puti(something(100)); + something := f(10, 20); + puti(something); + something2 @= f(10, 20); + puti(something2); + something3 := f(10, 10+10); + puti(something3); + something4 := f(10, 23); + puti(something4); + r := 20; + something5 := f(10, r); + puti(something5); +g := f; +something6 := g(10, r); +puti(something6); + }; diff --git a/tests.c b/tests.c index 43d3e50..3e08f4a 100644 --- a/tests.c +++ b/tests.c @@ -27,5 +27,4 @@ static void test_all(void) { arr_test(); block_arr_test(); idents_test(); - hash_table_test(); } diff --git a/toc.c b/toc.c index 9e4bc94..7c634c6 100644 --- a/toc.c +++ b/toc.c @@ -35,7 +35,7 @@ static Type *type_inner(Type *t) { #include "arr.c" #include "blockarr.c" #include "str.c" -#include "hash_tables.c" +#include "instance_table.c" #include "identifiers.c" #include "tokenizer.c" diff --git a/tokenizer.c b/tokenizer.c index 06ffdcc..342bbd7 100644 --- a/tokenizer.c +++ b/tokenizer.c @@ -7,7 +7,7 @@ static const char *keywords[KW_COUNT] = "if", "elif", "else", "while", "each", "return", "fn", "as", "new", "del", "struct", "int", "i8", "i16", "i32", "i64", - "u8", "u16", "u32", "u64", "float", "f32", "f64", + "u8", "u16", "u32", "u64", "float", "f32", "f64", "Type", "char", "bool", "true", "false"}; static inline const char *kw_to_str(Keyword k) { return keywords[k]; } diff --git a/typedefs_cgen.c b/typedefs_cgen.c index 77ea7f5..be2785d 100644 --- a/typedefs_cgen.c +++ b/typedefs_cgen.c @@ -1,4 +1,5 @@ static bool typedefs_stmt(CGenerator *g, Statement *s); +static bool typedefs_decl(CGenerator *g, Declaration *d); static bool typedefs_block(CGenerator *g, Block *b) { Block *prev = g->block; @@ -12,7 +13,7 @@ static bool typedefs_block(CGenerator *g, Block *b) { } static bool typedefs_expr(CGenerator *g, Expression *e) { - cgen_recurse_subexprs(g, e, typedefs_expr, typedefs_block); + cgen_recurse_subexprs(g, e, typedefs_expr, typedefs_block, typedefs_decl); if (e->kind == EXPR_FN) { /* needs to go before decls_cgen.c... */ e->fn.c.id = g->ident_counter++; diff --git a/types.c b/types.c index bf79774..295b53e 100644 --- a/types.c +++ b/types.c @@ -447,7 +447,7 @@ static bool type_resolve(Typer *tr, Type *t, Location where) { err_print(where, "Use of non-type identifier %s as type.", s); info_print(decl->where, "%s is declared here.", s); free(s); - return s; + return false; } /* resolve inner type */ Value *val = decl_val_at_index(decl, index); @@ -600,7 +600,10 @@ static bool types_expr(Typer *tr, Expression *e) { bool success = true; switch (e->kind) { case EXPR_FN: { - e->fn.c.instances = NULL; /* maybe this should be handled by cgen... oh well */ + { + HashTable z = {0}; + e->fn.instances = z; + } FnExpr *prev_fn = tr->fn; FnExpr *f = &e->fn; if (!type_of_fn(tr, e, t)) { @@ -933,6 +936,7 @@ static bool types_expr(Typer *tr, Expression *e) { } break; case EXPR_CALL: { CallExpr *c = &e->call; + c->instance = NULL; Expression *f = c->fn; if (f->kind == EXPR_IDENT) { /* allow calling a function before declaring it */ @@ -1062,13 +1066,28 @@ static bool types_expr(Typer *tr, Expression *e) { } } if (fn_type->constness) { - /* evaluate compile-time arguments */ + /* evaluate compile-time arguments + add an instance */ + Type table_index_type; + table_index_type.flags = TYPE_IS_RESOLVED; + table_index_type.kind = TYPE_TUPLE; + table_index_type.tuple = NULL; + Type *u64t = arr_add(&table_index_type.tuple); + u64t->flags = TYPE_IS_RESOLVED; + u64t->kind = TYPE_BUILTIN; + u64t->builtin = BUILTIN_U64; + Value table_index; + table_index.tuple = NULL; + /* we need to keep table_index's memory around because instance_table_add makes a copy of it to compare against. */ + Value *which_are_const_val = typer_arr_add(tr, &table_index.tuple); + U64 *which_are_const = &which_are_const_val->u64; + *which_are_const = 0; + int semi_const_index = 0; for (size_t i = 0; i < arr_len(fn_type->types)-1; i++) { bool should_be_evald = arg_is_const(&new_args[i], fn_type->constness[i]); if (should_be_evald) { - Value arg_val; - if (!eval_expr(tr->evalr, &new_args[i], &arg_val)) { + Value *arg_val = typer_arr_add(tr, &table_index.tuple); + if (!eval_expr(tr->evalr, &new_args[i], arg_val)) { if (tr->evalr->enabled) { info_print(new_args[i].where, "(error occured while trying to evaluate compile-time argument, argument #%lu)", (unsigned long)i); } @@ -1076,10 +1095,35 @@ static bool types_expr(Typer *tr, Expression *e) { } new_args[i].kind = EXPR_VAL; new_args[i].flags = 0; - new_args[i].val = arg_val; - i++; + new_args[i].val = *arg_val; + + Type *type = arr_add(&table_index_type.tuple); + *type = fn_type->types[i+1]; + + if (fn_type->constness[i] == CONSTNESS_SEMI) { + if (semi_const_index >= 64) { + err_print(new_args[i].where, "You can't have more than 64 semi-constant arguments to a function at the moment (sorry)."); + return false; + } + *which_are_const |= ((U64)1) << semi_const_index; + } + } + if (fn_type->constness[i] == CONSTNESS_SEMI) { + semi_const_index++; } } + + /* the function had better be a compile time constant if it has constant params */ + Value fn_val = {0}; + if (!eval_expr(tr->evalr, f, &fn_val)) + return false; + + FnExpr *fn = fn_val.fn; + + bool instance_already_exists; + c->instance = instance_table_adda(tr->allocr, &fn->instances, table_index, &table_index_type, &instance_already_exists); + c->instance->c.id = fn->instances.n; /* let's help cgen out and assign an ID to this */ + arr_clear(&table_index_type.tuple); } *t = *ret_type; c->arg_exprs = new_args; diff --git a/types.h b/types.h index 25a3dbe..3f398b8 100644 --- a/types.h +++ b/types.h @@ -222,6 +222,7 @@ typedef enum { KW_FLOAT, KW_F32, KW_F64, + KW_TYPE, KW_CHAR, KW_BOOL, KW_TRUE, @@ -429,15 +430,22 @@ typedef enum { BINARY_DOT } BinaryOp; +typedef struct { + Value val; + struct { + U64 id; + } c; +} Instance; + typedef struct { struct Expression *fn; union { struct Argument *args; struct Expression *arg_exprs; }; + Instance *instance; /* NULL = ordinary function, no compile time args */ struct { IdentID id; - U32 instance; /* 0 = ordinary function, no compile time args */ } c; } CallExpr; @@ -491,23 +499,19 @@ typedef struct { U64 cap; } HashTable; -/* these are found in value hash tables */ -typedef struct { - Value val; - I64 num; -} ValNumPair; - typedef struct FnExpr { struct Declaration *params; /* declarations of the parameters to this function */ struct Declaration *ret_decls; /* array of decls, if this has named return values. otherwise, NULL */ Type ret_type; Block body; + HashTable instances; /* for fns with constant parameters. the key is a tuple where + the first element is a u64 value whose ith bit (1<