From 843b5bedcc3558f809282adc77402d5060ce6f11 Mon Sep 17 00:00:00 2001 From: Mart Lubbers Date: Tue, 9 Mar 2021 09:02:49 +0100 Subject: [PATCH] convert to arrays instead of lists --- array.c | 53 +++++++++++++++++ array.h | 47 +++++++++++++++ ast.c | 149 ++++++++++++++++++++++-------------------------- ast.h | 44 ++++++-------- genc.c | 54 ++++++++++-------- parse.y | 49 ++++++++-------- sem.c | 107 ++++++++++++++++------------------ sem/hm.c | 40 ++++++------- sem/hm/gamma.c | 26 ++++----- sem/hm/scheme.c | 36 ++++++------ sem/scc.c | 42 +++++++------- splc.c | 9 ++- 12 files changed, 367 insertions(+), 289 deletions(-) create mode 100644 array.c create mode 100644 array.h diff --git a/array.c b/array.c new file mode 100644 index 0000000..5ca6654 --- /dev/null +++ b/array.c @@ -0,0 +1,53 @@ +#include +#include + +#include "util.h" +#include "array.h" + +struct array array_null = {.nel=0, .cap=0, .el=NULL}; + +void array_init(struct array *array, size_t cap) +{ + array->nel = 0; + array->cap = cap; + array->el = xalloc(cap, void *); +} + +struct array array_resize(struct array a, size_t cap) +{ + if (cap > a.cap) + a.el = xrealloc(a.el, a.cap = cap, void *); + return a; +} + +struct array array_append(struct array a, void *x) +{ + if (a.nel >= a.cap) + a = array_resize(a, a.cap == 0 ? 8 : 2*a.cap); + a.el[a.nel++] = x; + return a; +} + +//struct array array_insert(struct array a, size_t idx, void *x) +//{ +// a = array_append(a, NULL); +// for (size_t i = a.nel; i>idx; i--) +// a.el[i] = a.el[i-1]; +// a.el[idx] = x; +// return a; +//} + +void array_free(struct array a, void (*freefun)(void *)) +{ + array_clean(a, freefun); + free(a.el); +} + +struct array array_clean(struct array a, void (*freefun)(void *)) +{ + if (freefun != NULL) + ARRAY_ITERI(i, a) + freefun(a.el[i]); + a.nel = 0; + return a; +} diff --git a/array.h b/array.h new file mode 100644 index 0000000..a0dac15 --- /dev/null +++ b/array.h @@ -0,0 +1,47 @@ +#ifndef ARRAY_H +#define ARRAY_H + +#include + +#define ARRAY_EL(type, array, idx)\ + ((type)(array.el[idx])) + +#define ARRAY_ITERI(iter, a)\ + for (size_t (iter) = 0; (iter)<(a).nel; (iter)++) + +#define ARRAY_ITER(type, x, iter, a)\ + ARRAY_ITERI (iter, a) {\ + type (x) = ARRAY_EL(type, a, iter); +#define AIEND } + +#define ARRAY_SIZE(a) (a).nel +#define ARRAY_ELS(type, a) ((type *)(a).el) + + +extern struct array array_null; + +struct array { + size_t nel; + size_t cap; + void **el; +}; + +//* Initialise an array +void array_init(struct array *array, size_t cap); + +//* Resize an array to hold at least a certain capacity +struct array array_resize(struct array a, size_t cap); + +//* Create an array with the given capacity +struct array *array_new(size_t cap); + +//* Append an item to the array +struct array array_append(struct array a, void *x); + +//* free all elements and free the array +void array_free(struct array, void (*freefun)(void *)); + +//* free all element and keep the array +struct array array_clean(struct array array, void (*freefun)(void *)); + +#endif diff --git a/ast.c b/ast.c index f74f43e..2a2780c 100644 --- a/ast.c +++ b/ast.c @@ -2,6 +2,7 @@ #include #include +#include "array.h" #include "util.h" #include "ast.h" #include "type.h" @@ -16,11 +17,12 @@ const char *binop_str[] = { }; const char *unop_str[] = { [inverse] = "!", [negate] = "-", }; -struct ast *ast(struct list *decls, YYLTYPE l) +struct ast *ast(struct array decls, YYLTYPE l) { struct ast *res = xalloc(1, struct ast); res->loc = l; - res->decls = (struct decl **)list_to_array(decls, &res->ndecls, true, 0); + res->ndecls = ARRAY_SIZE(decls); + res->decls = ARRAY_ELS(struct decl *, decls); return res; } @@ -33,17 +35,17 @@ struct vardecl *vardecl(struct type *type, char *ident, struct expr *expr, YYLTY res->expr = expr; return res; } -struct fundecl *fundecl(char *ident, struct list *args, struct list *atypes, - struct type *rtype, struct list *body, YYLTYPE l) + +struct fundecl *fundecl(char *ident, struct array args, struct array atypes, + struct type *rtype, struct array body, YYLTYPE l) { struct fundecl *res = xalloc(1, struct fundecl); res->loc = l; res->ident = ident; - res->args = (char **)list_to_array(args, &res->nargs, true, 0); - res->atypes = (struct type **)list_to_array(atypes, &res->natypes, true, 0); + res->args = args; + res->atypes = atypes; res->rtype = rtype; - //Reserve room for an optional extra return inserted by the compiler - res->body = (struct stmt **)list_to_array(body, &res->nbody, true, 1); + res->body = body; return res; } @@ -65,28 +67,25 @@ struct decl *decl_var(struct vardecl *vardecl, YYLTYPE l) return res; } -struct stmt *stmt_assign(char *ident, struct list *fields, struct expr *expr, YYLTYPE l) +struct stmt *stmt_assign(char *ident, struct array fields, struct expr *expr, YYLTYPE l) { struct stmt *res = xalloc(1, struct stmt); res->loc = l; res->type = sassign; res->data.sassign.ident = ident; - res->data.sassign.fields = (char **) - list_to_array(fields, &res->data.sassign.nfields, true, 0); + res->data.sassign.fields = fields; res->data.sassign.expr = expr; return res; } -struct stmt *stmt_if(struct expr *pred, struct list *then, struct list *els, YYLTYPE l) +struct stmt *stmt_if(struct expr *pred, struct array then, struct array els, YYLTYPE l) { struct stmt *res = xalloc(1, struct stmt); res->loc = l; res->type = sif; res->data.sif.pred = pred; - res->data.sif.then = (struct stmt **) - list_to_array(then, &res->data.sif.nthen, true, 0); - res->data.sif.els = (struct stmt **) - list_to_array(els, &res->data.sif.nels, true, 0); + res->data.sif.then = then; + res->data.sif.els = els; return res; } @@ -117,14 +116,13 @@ struct stmt *stmt_vardecl(struct vardecl *vardecl, YYLTYPE l) return res; } -struct stmt *stmt_while(struct expr *pred, struct list *body, YYLTYPE l) +struct stmt *stmt_while(struct expr *pred, struct array body, YYLTYPE l) { struct stmt *res = xalloc(1, struct stmt); res->loc = l; res->type = swhile; res->data.swhile.pred = pred; - res->data.swhile.body = (struct stmt **) - list_to_array(body, &res->data.swhile.nbody, true, 0); + res->data.swhile.body = body; return res; } @@ -177,30 +175,31 @@ bool is_builtin(char *t) || strcmp(t, "print") == 0; } -struct expr *expr_funcall_real(char *ident, struct list *args, YYLTYPE l) +struct expr *expr_funcall_real(char *ident, struct array args, YYLTYPE l) { struct expr *res = xalloc(1, struct expr); res->loc = l; res->type = efuncall; res->data.efuncall.ident = ident; - res->data.efuncall.args = (struct expr **) - list_to_array(args, &res->data.efuncall.nargs, true, 0); + res->data.efuncall.args = args; return res; } -static struct expr *expr_apply_fields(struct expr *r, struct list *fields, YYLTYPE l) +static struct expr *expr_apply_fields(struct expr *r, struct array fields, YYLTYPE l) { - FOREACH(field, fields) { - if (is_valid_field(field->el)) { - struct list *as = list_cons(r, NULL); - r = expr_funcall_real(field->el, as, l); + ARRAY_ITER(char *, f, i, fields) { + if (is_valid_field(f)) { + struct array as; + array_init(&as, 1); + as = array_append(as, r); + r = expr_funcall_real(f, as, l); } - } - list_free(fields, NULL); + } AIEND + array_free(fields, NULL); return r; } -struct expr *expr_funcall(char *ident, struct list *args, struct list *fields, YYLTYPE l) +struct expr *expr_funcall(char *ident, struct array args, struct array fields, YYLTYPE l) { struct expr *res = expr_funcall_real(ident, args, l); res = expr_apply_fields(res, fields, l); @@ -216,7 +215,7 @@ struct expr *expr_int(int integer, YYLTYPE l) return res; } -struct expr *expr_ident(char *ident, struct list *fields, YYLTYPE l) +struct expr *expr_ident(char *ident, struct array fields, YYLTYPE l) { struct expr *res = xalloc(1, struct expr); res->loc = l; @@ -295,24 +294,25 @@ void vardecl_print(struct vardecl *decl, int indent, FILE *out) void fundecl_print(struct fundecl *decl, FILE *out) { safe_fprintf(out, "%s (", decl->ident); - for (int i = 0; inargs; i++) { - safe_fprintf(out, "%s", decl->args[i]); - if (i < decl->nargs - 1) + ARRAY_ITER(char *, arg, i, decl->args) { + safe_fprintf(out, "%s", arg); + if (i < ARRAY_SIZE(decl->args) - 1) safe_fprintf(out, ", "); - } + } AIEND safe_fprintf(out, ")"); if (decl->rtype != NULL) { safe_fprintf(out, " :: "); - for (int i = 0; inatypes; i++) { - type_print(decl->atypes[i], out); + ARRAY_ITER(struct type *, atype, i, decl->atypes) { + type_print(atype, out); safe_fprintf(out, " "); - } + } AIEND safe_fprintf(out, "-> "); type_print(decl->rtype, out); } safe_fprintf(out, " {\n"); - for (int i = 0; inbody; i++) - stmt_print(decl->body[i], 1, out); + ARRAY_ITER(struct stmt *, stmt, i, decl->body) + stmt_print(stmt, 1, out); + AIEND safe_fprintf(out, "}\n"); } @@ -329,8 +329,9 @@ void decl_print(struct decl *decl, FILE *out) break; case dcomp: fprintf(out, "//<<data.dcomp.ndecls; i++) - fundecl_print(decl->data.dcomp.decls[i], out); + ARRAY_ITER(struct fundecl *, d, i, decl->data.dcomp) + fundecl_print(d, out); + AIEND fprintf(out, "//>>>comp\n"); break; default: @@ -346,8 +347,9 @@ void stmt_print(struct stmt *stmt, int indent, FILE *out) case sassign: pindent(indent, out); fprintf(out, "%s", stmt->data.sassign.ident); - for (int i = 0; idata.sassign.nfields; i++) - fprintf(out, ".%s", stmt->data.sassign.fields[i]); + ARRAY_ITER(char *, f, i, stmt->data.sassign.fields) + fprintf(out, ".%s", f); + AIEND safe_fprintf(out, " = "); expr_print(stmt->data.sassign.expr, out); safe_fprintf(out, ";\n"); @@ -357,12 +359,14 @@ void stmt_print(struct stmt *stmt, int indent, FILE *out) safe_fprintf(out, "if ("); expr_print(stmt->data.sif.pred, out); safe_fprintf(out, ") {\n"); - for (int i = 0; idata.sif.nthen; i++) - stmt_print(stmt->data.sif.then[i], indent+1, out); + ARRAY_ITER(struct stmt *, s, i, stmt->data.sif.then) + stmt_print(s, indent+1, out); + AIEND pindent(indent, out); safe_fprintf(out, "} else {\n"); - for (int i = 0; idata.sif.nels; i++) - stmt_print(stmt->data.sif.els[i], indent+1, out); + ARRAY_ITER(struct stmt *, s, i, stmt->data.sif.els) + stmt_print(s, indent+1, out); + AIEND pindent(indent, out); safe_fprintf(out, "}\n"); break; @@ -385,8 +389,9 @@ void stmt_print(struct stmt *stmt, int indent, FILE *out) safe_fprintf(out, "while ("); expr_print(stmt->data.swhile.pred, out); safe_fprintf(out, ") {\n"); - for (int i = 0; idata.swhile.nbody; i++) - stmt_print(stmt->data.swhile.body[i], indent+1, out); + ARRAY_ITER(struct stmt *, s, i, stmt->data.swhile.body) + stmt_print(s, indent+1, out); + AIEND pindent(indent, out); safe_fprintf(out, "}\n"); break; @@ -417,11 +422,11 @@ void expr_print(struct expr *expr, FILE *out) break; case efuncall: safe_fprintf(out, "%s(", expr->data.efuncall.ident); - for(int i = 0; idata.efuncall.nargs; i++) { - expr_print(expr->data.efuncall.args[i], out); - if (i+1 < expr->data.efuncall.nargs) + ARRAY_ITER(struct expr *, e, i, expr->data.efuncall.args) { + expr_print(e, out); + if (i+1 < ARRAY_SIZE(expr->data.efuncall.args)) safe_fprintf(out, ", "); - } + } AIEND safe_fprintf(out, ")"); break; case eint: @@ -478,16 +483,10 @@ void vardecl_free(struct vardecl *decl) void fundecl_free(struct fundecl *decl) { free(decl->ident); - for (int i = 0; inargs; i++) - free(decl->args[i]); - free(decl->args); - for (int i = 0; inatypes; i++) - type_free(decl->atypes[i]); - free(decl->atypes); + array_free(decl->args, free); + array_free(decl->atypes, (void (*)(void *))type_free); type_free(decl->rtype); - for (int i = 0; inbody; i++) - stmt_free(decl->body[i]); - free(decl->body); + array_free(decl->body, (void (*)(void *))stmt_free); free(decl); } @@ -497,9 +496,7 @@ void decl_free(struct decl *decl) return; switch(decl->type) { case dcomp: - for (int i = 0; idata.dcomp.ndecls; i++) - fundecl_free(decl->data.dcomp.decls[i]); - free(decl->data.dcomp.decls); + array_free(decl->data.dcomp, (void (*)(void *))fundecl_free); break; case dfundecl: fundecl_free(decl->data.dfun); @@ -520,19 +517,13 @@ void stmt_free(struct stmt *stmt) switch(stmt->type) { case sassign: free(stmt->data.sassign.ident); - for (int i = 0; idata.sassign.nfields; i++) - free(stmt->data.sassign.fields[i]); - free(stmt->data.sassign.fields); + array_free(stmt->data.sassign.fields, free); expr_free(stmt->data.sassign.expr); break; case sif: expr_free(stmt->data.sif.pred); - for (int i = 0; idata.sif.nthen; i++) - stmt_free(stmt->data.sif.then[i]); - free(stmt->data.sif.then); - for (int i = 0; idata.sif.nels; i++) - stmt_free(stmt->data.sif.els[i]); - free(stmt->data.sif.els); + array_free(stmt->data.sif.then, (void (*)(void *))stmt_free); + array_free(stmt->data.sif.els, (void (*)(void *))stmt_free); break; case sreturn: expr_free(stmt->data.sreturn); @@ -542,9 +533,7 @@ void stmt_free(struct stmt *stmt) break; case swhile: expr_free(stmt->data.swhile.pred); - for (int i = 0; idata.swhile.nbody; i++) - stmt_free(stmt->data.swhile.body[i]); - free(stmt->data.swhile.body); + array_free(stmt->data.swhile.body, (void (*)(void *))stmt_free); break; case svardecl: vardecl_free(stmt->data.svardecl); @@ -570,9 +559,7 @@ void expr_free(struct expr *expr) break; case efuncall: free(expr->data.efuncall.ident); - for (int i = 0; idata.efuncall.nargs; i++) - expr_free(expr->data.efuncall.args[i]); - free(expr->data.efuncall.args); + array_free(expr->data.efuncall.args, (void (*)(void *))expr_free); break; case eint: break; diff --git a/ast.h b/ast.h index 557ccc0..1a27550 100644 --- a/ast.h +++ b/ast.h @@ -4,6 +4,7 @@ #include #include +#include "array.h" #include "util.h" #include "type.h" struct ast; @@ -27,13 +28,10 @@ struct vardecl { struct fundecl { YYLTYPE loc; char *ident; - int nargs; - char **args; - int natypes; - struct type **atypes; + struct array args; // char * + struct array atypes; // struct type * struct type *rtype; - int nbody; - struct stmt **body; + struct array body; //struct stmt * }; struct decl { @@ -41,10 +39,7 @@ struct decl { //NOTE: DON'T CHANGE THIS ORDER enum {dcomp, dvardecl, dfundecl} type; union { - struct { - int ndecls; - struct fundecl **decls; - } dcomp; + struct array dcomp; //struct fundecl * struct fundecl *dfun; struct vardecl *dvar; } data; @@ -56,24 +51,20 @@ struct stmt { union { struct { char *ident; - int nfields; - char **fields; + struct array fields; //char * struct expr *expr; } sassign; struct { struct expr *pred; - int nthen; - struct stmt **then; - int nels; - struct stmt **els; + struct array then; //struct stmt * + struct array els; //struct stmt * } sif; struct vardecl *svardecl; struct expr *sreturn; struct expr *sexpr; struct { struct expr *pred; - int nbody; - struct stmt **body; + struct array body; //struct stmt * } swhile; } data; }; @@ -99,8 +90,7 @@ struct expr { char echar; struct { char *ident; - int nargs; - struct expr **args; + struct array args; // struct expr * } efuncall; int eint; char *eident; @@ -119,27 +109,27 @@ struct expr { } data; }; -struct ast *ast(struct list *decls, YYLTYPE l); +struct ast *ast(struct array decls, YYLTYPE l); struct vardecl *vardecl(struct type *type, char *ident, struct expr *expr, YYLTYPE l); -struct fundecl *fundecl(char *ident, struct list *args, struct list *atypes, struct type *rtype, struct list *body, YYLTYPE l); +struct fundecl *fundecl(char *ident, struct array args, struct array atypes, struct type *rtype, struct array body, YYLTYPE l); struct decl *decl_fun(struct fundecl *fundecl, YYLTYPE l); struct decl *decl_var(struct vardecl *vardecl, YYLTYPE l); -struct stmt *stmt_assign(char *ident, struct list *fields, struct expr *expr, YYLTYPE l); -struct stmt *stmt_if(struct expr *pred, struct list *then, struct list *els, YYLTYPE l); +struct stmt *stmt_assign(char *ident, struct array fields, struct expr *expr, YYLTYPE l); +struct stmt *stmt_if(struct expr *pred, struct array then, struct array els, YYLTYPE l); struct stmt *stmt_return(struct expr *rtrn, YYLTYPE l); struct stmt *stmt_expr(struct expr *expr, YYLTYPE l); struct stmt *stmt_vardecl(struct vardecl *vardecl, YYLTYPE l); -struct stmt *stmt_while(struct expr *pred, struct list *body, YYLTYPE l); +struct stmt *stmt_while(struct expr *pred, struct array body, YYLTYPE l); struct expr *expr_binop(struct expr *left, enum binop op, struct expr *right, YYLTYPE l); struct expr *expr_bool(bool b, YYLTYPE l); struct expr *expr_char(char *c, YYLTYPE l); -struct expr *expr_funcall(char *ident, struct list *args, struct list *fields, YYLTYPE l); +struct expr *expr_funcall(char *ident, struct array args, struct array fields, YYLTYPE l); struct expr *expr_int(int integer, YYLTYPE l); -struct expr *expr_ident(char *ident, struct list *fields, YYLTYPE l); +struct expr *expr_ident(char *ident, struct array fields, YYLTYPE l); struct expr *expr_nil(YYLTYPE l); struct expr *expr_tuple(struct expr *left, struct expr *right, YYLTYPE l); struct expr *expr_string(char *str, YYLTYPE l); diff --git a/genc.c b/genc.c index 821a5c0..6acf9e1 100644 --- a/genc.c +++ b/genc.c @@ -43,11 +43,11 @@ void expr_genc(struct expr *expr, FILE *cout) break; case efuncall: safe_fprintf(cout, "%s(", expr->data.efuncall.ident); - for(int i = 0; idata.efuncall.nargs; i++) { - expr_genc(expr->data.efuncall.args[i], cout); - if (i+1 < expr->data.efuncall.nargs) + ARRAY_ITER(struct expr *, e, i, expr->data.efuncall.args) { + expr_genc(e, cout); + if (i+1 < ARRAY_SIZE(expr->data.efuncall.args)) safe_fprintf(cout, ", "); - } + } AIEND safe_fprintf(cout, ")"); break; case eint: @@ -124,8 +124,9 @@ void stmt_genc(struct stmt *stmt, int indent, FILE *cout) case sassign: pindent(indent, cout); fprintf(cout, "%s", stmt->data.sassign.ident); - for (int i = 0; idata.sassign.nfields; i++) - fprintf(cout, "->%s", stmt->data.sassign.fields[i]); + ARRAY_ITER(char *, f, i, stmt->data.sassign.fields) + fprintf(cout, "->%s", f); + AIEND safe_fprintf(cout, " = "); expr_genc(stmt->data.sassign.expr, cout); safe_fprintf(cout, ";\n"); @@ -135,12 +136,14 @@ void stmt_genc(struct stmt *stmt, int indent, FILE *cout) safe_fprintf(cout, "if ("); expr_genc(stmt->data.sif.pred, cout); safe_fprintf(cout, ") {\n"); - for (int i = 0; idata.sif.nthen; i++) - stmt_genc(stmt->data.sif.then[i], indent+1, cout); + ARRAY_ITER(struct stmt *, s, i, stmt->data.sif.then) + stmt_genc(s, indent+1, cout); + AIEND pindent(indent, cout); safe_fprintf(cout, "} else {\n"); - for (int i = 0; idata.sif.nels; i++) - stmt_genc(stmt->data.sif.els[i], indent+1, cout); + ARRAY_ITER(struct stmt *, s, i, stmt->data.sif.els) + stmt_genc(s, indent+1, cout); + AIEND pindent(indent, cout); safe_fprintf(cout, "}\n"); break; @@ -163,8 +166,9 @@ void stmt_genc(struct stmt *stmt, int indent, FILE *cout) safe_fprintf(cout, "while ("); expr_genc(stmt->data.swhile.pred, cout); safe_fprintf(cout, ") {\n"); - for (int i = 0; idata.swhile.nbody; i++) - stmt_genc(stmt->data.swhile.body[i], indent+1, cout); + ARRAY_ITER(struct stmt *, s, i, stmt->data.swhile.body) + stmt_genc(s, indent+1, cout); + AIEND pindent(indent, cout); safe_fprintf(cout, "}\n"); break; @@ -177,26 +181,27 @@ void fundecl_genc(struct fundecl *decl, FILE *cout) { type_genc(decl->rtype, cout); safe_fprintf(cout, "%s (", decl->ident); - for (int i = 0; inargs; i++) { - if (i < decl->natypes) + ARRAY_ITER(char *, a, i, decl->args) { + if (i >= ARRAY_SIZE(decl->atypes)) die("function with unmatched type\n"); - safe_fprintf(cout, "%s", decl->args[i]); - if (i < decl->nargs - 1) + safe_fprintf(cout, "%s", a); + if (i < ARRAY_SIZE(decl->args) - 1) safe_fprintf(cout, ", "); - } + } AIEND safe_fprintf(cout, ") /*"); if (decl->rtype != NULL) { safe_fprintf(cout, " :: "); - for (int i = 0; inatypes; i++) { - type_print(decl->atypes[i], cout); + ARRAY_ITER(struct type *, t, i, decl->atypes) { + type_print(t, cout); safe_fprintf(cout, " "); - } + } AIEND safe_fprintf(cout, "-> "); type_print(decl->rtype, cout); } safe_fprintf(cout, "*/ {\n"); - for (int i = 0; inbody; i++) - stmt_genc(decl->body[i], 1, cout); + ARRAY_ITER(struct stmt *, s, i, decl->body) + stmt_genc(s, 1, cout); + AIEND safe_fprintf(cout, "}\n"); } @@ -205,8 +210,9 @@ void decl_genc(struct decl *decl, FILE *cout) switch (decl->type) { case dcomp: //TODO generate prototypes? - for (int i = 0; idata.dcomp.ndecls; i++) - fundecl_genc(decl->data.dcomp.decls[i], cout); + ARRAY_ITER(struct fundecl *, d, i, decl->data.dcomp) + fundecl_genc(d, cout); + AIEND break; case dfundecl: fundecl_genc(decl->data.dfun, cout); diff --git a/parse.y b/parse.y index 16f236c..40b4b1d 100644 --- a/parse.y +++ b/parse.y @@ -1,6 +1,7 @@ %{ #include +#include "array.h" #include "ast.h" #include "list.h" #include "parse.h" @@ -26,14 +27,14 @@ int yywrap() //%expect 1 // Tuples and parenthesis //%expect-rr 1 -%glr-parser +//%glr-parser %locations %parse-param { struct ast **result } %union { struct expr *expr; struct stmt *stmt; - struct list *list; + struct array array; struct vardecl *vardecl; struct fundecl *fundecl; struct type *type; @@ -56,7 +57,7 @@ int yywrap() %type start %type expr tuply -%type args body decls fargs field fnargs nargs funtype bbody +%type decls funtype args nargs body bbody fargs fnargs field %type stmt %type type ftype %type vardecl @@ -66,23 +67,23 @@ int yywrap() start : decls { *result = ast($1, @$); } ; decls - : /* empty */ { $$ = NULL; } - | decls vardecl { $$ = list_cons(decl_var($2, @2), $1); } - | decls fundecl { $$ = list_cons(decl_fun($2, @2), $1); } + : /* empty */ { $$ = array_null; } + | decls vardecl { $$ = array_append($1, decl_var($2, @2)); } + | decls fundecl { $$ = array_append($1, decl_fun($2, @2)); } ; vardecl : VAR IDENT ASSIGN expr SEMICOLON { $$ = vardecl(NULL, $2, $4, @$); } | type IDENT ASSIGN expr SEMICOLON { $$ = vardecl($1, $2, $4, @$); } ; fundecl - : IDENT BOPEN args BCLOSE COPEN body CCLOSE - { $$ = fundecl($1, $3, NULL, NULL, $6, @$); } - | IDENT BOPEN args BCLOSE CONS CONS funtype ARROW ftype COPEN body CCLOSE - { $$ = fundecl($1, $3, $7, $9, $11, @$); } + : IDENT BOPEN args BCLOSE bbody + { $$ = fundecl($1, $3, array_null, NULL, $5, @$); } + | IDENT BOPEN args BCLOSE CONS CONS funtype ARROW ftype bbody + { $$ = fundecl($1, $3, $7, $9, $10, @$); } ; funtype - : /* empty */ { $$ = NULL; } - | funtype ftype { $$ = list_cons($2, $1); } + : /* empty */ { $$ = array_null; } + | funtype ftype { $$ = array_append($1, $2); } ; /* don't allow vardecls to be fully polymorph, this complicates parsing a lot */ type @@ -98,35 +99,35 @@ ftype | IDENT { $$ = type_var_str($1); free($1); } ; args - : /* empty */ { $$ = NULL; } + : /* empty */ { $$ = array_null; } | nargs ; nargs - : nargs COMMA IDENT { $$ = list_cons($3, $1); } - | IDENT { $$ = list_cons($1, NULL); } + : nargs COMMA IDENT { $$ = array_append($1, $3); } + | IDENT { array_init(&$$, 8); $$ = array_append($$, $1); } ; fargs - : /* empty */ { $$ = NULL; } + : /* empty */ { $$ = array_null; } | fnargs ; fnargs - : fnargs COMMA expr { $$ = list_cons($3, $1); } - | expr { $$ = list_cons($1, NULL); } + : fnargs COMMA expr { $$ = array_append($1, $3); } + | expr { array_init(&$$, 8); $$ = array_append($$, $1); } ; body - : /* empty */ { $$ = NULL; } - | body stmt { $$ = list_cons($2, $1); } + : /* empty */ { $$ = array_null; } + | body stmt { $$ = array_append($1, $2); } ; field - : /* empty */ { $$ = NULL; } - | field DOT IDENT { $$ = list_cons($3, $1); } + : /* empty */ { $$ = array_null; } + | field DOT IDENT { $$ = array_append($1, $3); } ; bbody : COPEN body CCLOSE { $$ = $2; } - | stmt { $$ = list_cons($1, NULL); } + | stmt { array_init(&$$, 1); $$ = array_append($$, $1); } ; stmt - : IF BOPEN expr BCLOSE bbody { $$ = stmt_if($3, $5, NULL, @$); } + : IF BOPEN expr BCLOSE bbody { $$ = stmt_if($3, $5, array_null, @$); } | IF BOPEN expr BCLOSE bbody ELSE bbody { $$ = stmt_if($3, $5, $7, @$); } | WHILE BOPEN expr BCLOSE bbody { $$ = stmt_while($3, $5, @$); } | IDENT field ASSIGN expr SEMICOLON { $$ = stmt_assign($1, $2, $4, @$); } diff --git a/sem.c b/sem.c index 18425d2..ea77d8e 100644 --- a/sem.c +++ b/sem.c @@ -1,5 +1,6 @@ #include #include +#include #include "list.h" #include "sem/scc.h" @@ -52,57 +53,60 @@ struct vardecl *type_vardecl(struct gamma *gamma, struct vardecl *vardecl) return vardecl; } -void type_comp(struct gamma *gamma, int ndecls, struct fundecl **decl) +void type_comp(struct gamma *gamma, struct array decl) { //Create a fresh variable for every function in the component - struct type **fs = xalloc(ndecls, struct type *); - for (int i = 0; inargs; j++) { + ARRAY_ITERI(j, d->args) { struct type *a = gamma_fresh(gamma); fs[i] = type_arrow(a, fs[i]); } - gamma_insert(gamma, ident_str(decl[i]->ident), scheme_create(fs[i])); - } + gamma_insert(gamma, ident_str(d->ident), scheme_create(fs[i])); + } AIEND //Infer each function struct subst *s0 = subst_id(); - for (int i = 0; irtype != NULL) { - struct type *dt = decl[i]->rtype; - for (int j = decl[i]->natypes-1; j>=0; j--) { - dt = type_arrow(decl[i]->atypes[j], dt); - } - struct subst *s1 = unify(decl[i]->loc, dt, t); + if (d->rtype != NULL) { + struct type *dt = d->rtype; + for (int j = (int)ARRAY_SIZE(d->atypes)-1; j>=0; j--) + dt = type_arrow(ARRAY_EL(struct type *, + d->atypes, j), dt); + struct subst *s1 = unify(d->loc, dt, t); subst_apply_t(s1, fs[i]); subst_free(s1); type_free(dt); } - gamma_insert(gamma, ident_str(decl[i]->ident), scheme_generalise(gamma, t)); + gamma_insert(gamma, ident_str(d->ident), scheme_generalise(gamma, t)); //Put the type in the ast - decl[i]->atypes = xrealloc(decl[i]->atypes, - decl[i]->nargs, struct type *); - decl[i]->natypes = decl[i]->nargs; - for (int j = 0; jnargs; j++, t = t->data.tarrow.r) - decl[i]->atypes[j] = type_dup(t->data.tarrow.l); - decl[i]->rtype = type_dup(t); - } + d->atypes = array_clean(d->atypes, NULL); + d->atypes = array_resize(d->atypes, ARRAY_SIZE(d->args)); + + ARRAY_ITERI(j, d->args) { + d->atypes = array_append(d->atypes, (void *)type_dup(t->data.tarrow.l)); + t = t->data.tarrow.r; + } + d->rtype = type_dup(t); + } AIEND //Free all types - for (int i = 0; idata.sif.nthen, stmt->data.sif.then) - && check_return_body(stmt->data.sif.nels, stmt->data.sif.els); + return check_return_body(stmt->data.sif.then) + && check_return_body(stmt->data.sif.els); case swhile: - return check_return_body(stmt->data.swhile.nbody, - stmt->data.swhile.body); + return check_return_body(stmt->data.swhile.body); case sreturn: return true; default: @@ -168,28 +172,23 @@ bool check_return_stmt(struct stmt *stmt) } } -void check_return_comp(int ndecl, struct fundecl **decls) +void check_return_comp(struct array decl) { - for (int i = 0; irtype->type == tbasic && - decls[i]->rtype->data.tbasic == btvoid) + ARRAY_ITER(struct fundecl *, d, i, decl) { + if (d->rtype->type == tbasic && d->rtype->data.tbasic == btvoid) continue; - if (!check_return_body(decls[i]->nbody, decls[i]->body)) - type_error(decls[i]->loc, true, - "%s doesn't return properly", decls[i]->ident); - } + if (!check_return_body(d->body)) + type_error(d->loc, true, + "%s doesn't return properly", d->ident); + } AIEND } -void add_return_if_none(int ndecl, struct fundecl **decl) +void add_return_if_none(struct array decl) { - for (int i = 0; irtype == NULL && !check_return_body( - decl[i]->nbody, decl[i]->body)) { - //Room for this was reserved in ast.c - decl[i]->body[decl[i]->nbody++] = - stmt_return(NULL, decl[i]->loc); - } - } + ARRAY_ITER(struct fundecl *, d, i, decl) + if (d->rtype == NULL && !check_return_body(d->body)) + d->body = array_append(d->body, stmt_return(NULL, d->loc)); + AIEND } struct ast *sem(struct ast *ast) @@ -199,9 +198,6 @@ struct ast *sem(struct ast *ast) struct gamma *gamma = gamma_init(); gamma_preamble(gamma); - fprintf(stderr, "start with gamma: "); - gamma_print(gamma, stderr); - fprintf(stderr, "\n"); //Check all vardecls for (int i = 0; indecls; i++) { @@ -215,12 +211,9 @@ struct ast *sem(struct ast *ast) break; case dcomp: //Infer function as singleton component - add_return_if_none(decl->data.dcomp.ndecls, - decl->data.dcomp.decls); - type_comp(gamma, decl->data.dcomp.ndecls, - decl->data.dcomp.decls); - check_return_comp(decl->data.dcomp.ndecls, - decl->data.dcomp.decls); + add_return_if_none(decl->data.dcomp); + type_comp(gamma, decl->data.dcomp); + check_return_comp(decl->data.dcomp); break; case dfundecl: die("fundecls should be gone by now\n"); diff --git a/sem/hm.c b/sem/hm.c index 75587e6..eb3f5c6 100644 --- a/sem/hm.c +++ b/sem/hm.c @@ -138,16 +138,15 @@ struct subst *infer_expr(struct gamma *gamma, struct expr *expr, struct type *ty struct type *t = ft; struct subst *s0 = subst_id(); //Infer args - for (int i = 0; idata.efuncall.nargs; i++) { + ARRAY_ITER(struct expr *, a, i, expr->data.efuncall.args) { if (t->type != tarrow) type_error(expr->loc, true, "too many arguments to %s\n", expr->data.efuncall.ident); - s1 = infer_expr(gamma, - expr->data.efuncall.args[i], t->data.tarrow.l); + s1 = infer_expr(gamma, a, t->data.tarrow.l); s0 = subst_union(s1, s0); t = t->data.tarrow.r; - } + } AIEND if (t->type == tarrow) type_error(expr->loc, true, "not enough arguments to %s\n", @@ -196,15 +195,15 @@ struct subst *infer_expr(struct gamma *gamma, struct expr *expr, struct type *ty return NULL; } -struct subst *infer_body(struct gamma *gamma, int nstmt, struct stmt **stmts, struct type *type) +struct subst *infer_body(struct gamma *gamma, struct array stmts, struct type *type) { gamma_increment_scope(gamma); struct subst *s0 = subst_id(), *s1; - for (int i = 0; idata.sif.pred, &tybool); //subst_apply_g(s0, gamma); - s0 = subst_union(s0, infer_body(gamma, - stmt->data.sif.nthen, stmt->data.sif.then, type)); + s0 = subst_union(s0, + infer_body(gamma, stmt->data.sif.then, type)); - s0 = subst_union(s0, infer_body(gamma, - stmt->data.sif.nels, stmt->data.sif.els, type)); + s0 = subst_union(s0, + infer_body(gamma, stmt->data.sif.els, type)); return s0; case sreturn: return stmt->data.sreturn == NULL @@ -253,8 +252,8 @@ struct subst *infer_stmt(struct gamma *gamma, struct stmt *stmt, struct type *ty s0 = infer_expr(gamma, stmt->data.swhile.pred, &tybool); //subst_apply_g(s0, gamma); - s0 = subst_union(s0, infer_body(gamma, - stmt->data.swhile.nbody, stmt->data.swhile.body, type)); + s0 = subst_union(s0, + infer_body(gamma, stmt->data.swhile.body, type)); return s0; } @@ -266,22 +265,21 @@ struct subst *infer_fundecl(struct gamma *gamma, struct fundecl *fundecl, struct // Put arguments in gamma gamma_increment_scope(gamma); struct type *at = ftype; - for (int i = 0; inargs; i++) { + ARRAY_ITER(char *, a, i, fundecl->args) { if (at->type != tarrow) die("malformed ftype\n"); - gamma_insert(gamma, ident_str(fundecl->args[i]), - scheme_create(at->data.tarrow.l)); + gamma_insert(gamma, ident_str(a), scheme_create(at->data.tarrow.l)); at = at->data.tarrow.r; - } + } AIEND if (at->type == tarrow) die("malformed ftype\n"); struct subst *s = subst_id(); - for (int i = 0; inbody; i++) { - struct subst *s1 = infer_stmt(gamma, fundecl->body[i], at); + ARRAY_ITER(struct stmt *, st, i, fundecl->body) { + struct subst *s1 = infer_stmt(gamma, st, at); s = subst_union(s1, s); subst_apply_g(s, gamma); - } + } AIEND // Remove arguments from gamma gamma_decrement_scope(gamma); diff --git a/sem/hm/gamma.c b/sem/hm/gamma.c index 1dcad70..db69ec1 100644 --- a/sem/hm/gamma.c +++ b/sem/hm/gamma.c @@ -103,19 +103,19 @@ struct type *gamma_fresh(struct gamma *gamma) return type_var_int(gamma->fresh++); } -void gamma_print(struct gamma *gamma, FILE *out) -{ - fprintf(out, "{"); - for (int i = 0; inentries; i++) { - ident_print(gamma->entries[i].var, out); - fprintf(out, "(%d) = ", gamma->entries[i].scope); - scheme_print(gamma->entries[i].scheme, out); - if (i + 1 < gamma->nentries) - fprintf(out, ", "); - } - fprintf(out, "}"); -} - +//void gamma_print(struct gamma *gamma, FILE *out) +//{ +// fprintf(out, "{"); +// for (int i = 0; inentries; i++) { +// ident_print(gamma->entries[i].var, out); +// fprintf(out, "(%d) = ", gamma->entries[i].scope); +// scheme_print(gamma->entries[i].scheme, out); +// if (i + 1 < gamma->nentries) +// fprintf(out, ", "); +// } +// fprintf(out, "}"); +//} +// void gamma_free(struct gamma *gamma) { for (int i = 0; inentries; i++) { diff --git a/sem/hm/scheme.c b/sem/hm/scheme.c index ee10c7d..eed2e32 100644 --- a/sem/hm/scheme.c +++ b/sem/hm/scheme.c @@ -47,24 +47,24 @@ struct scheme *scheme_generalise(struct gamma *gamma, struct type *t) return s; } -void scheme_print(struct scheme *scheme, FILE *out) -{ - if (scheme == NULL) { - fprintf(out, "NULLSCHEME"); - return; - } - if (scheme->nvar > 0) { - fprintf(out, "A."); - for (int i = 0; invar; i++) { - if (i > 0) - fprintf(out, " "); - ident_print(scheme->var[i], stderr); - } - fprintf(out, ": "); - } - type_print(scheme->type, out); -} - +//void scheme_print(struct scheme *scheme, FILE *out) +//{ +// if (scheme == NULL) { +// fprintf(out, "NULLSCHEME"); +// return; +// } +// if (scheme->nvar > 0) { +// fprintf(out, "A."); +// for (int i = 0; invar; i++) { +// if (i > 0) +// fprintf(out, " "); +// ident_print(scheme->var[i], stderr); +// } +// fprintf(out, ": "); +// } +// type_print(scheme->type, out); +//} +// void scheme_free(struct scheme *scheme) { type_free(scheme->type); diff --git a/sem/scc.c b/sem/scc.c index dd685d3..2a53f7c 100644 --- a/sem/scc.c +++ b/sem/scc.c @@ -162,9 +162,9 @@ struct list *edges_expr(int ndecls, struct decl **decls, void *parent, case echar: break; case efuncall: - for(int i = 0; idata.efuncall.nargs; i++) - l = edges_expr(ndecls, decls, parent, - expr->data.efuncall.args[i], l); + ARRAY_ITER(struct expr *, e, i, expr->data.efuncall.args ) + l = edges_expr(ndecls, decls, parent, e, l); + AIEND bool found = false; for (int i = 0; idata.dfun->ident, @@ -212,12 +212,12 @@ struct list *edges_stmt(int ndecls, struct decl **decls, void *parent, break; case sif: l = edges_expr(ndecls, decls, parent, stmt->data.sif.pred, l); - for (int i = 0; idata.sif.nthen; i++) - l = edges_stmt(ndecls, decls, parent, - stmt->data.sif.then[i], l); - for (int i = 0; idata.sif.nels; i++) - l = edges_stmt(ndecls, decls, parent, - stmt->data.sif.els[i], l); + ARRAY_ITER(struct stmt *, s, i, stmt->data.sif.then) + l = edges_stmt(ndecls, decls, parent, s, l); + AIEND + ARRAY_ITER(struct stmt *, s, i, stmt->data.sif.els) + l = edges_stmt(ndecls, decls, parent, s, l); + AIEND break; case sreturn: l = edges_expr(ndecls, decls, parent, stmt->data.sreturn, l); @@ -232,9 +232,9 @@ struct list *edges_stmt(int ndecls, struct decl **decls, void *parent, case swhile: l = edges_expr(ndecls, decls, parent, stmt->data.swhile.pred, l); - for (int i = 0; idata.swhile.nbody; i++) - l = edges_stmt(ndecls, decls, parent, - stmt->data.swhile.body[i], l); + ARRAY_ITER(struct stmt *, s, i, stmt->data.swhile.body) + l = edges_stmt(ndecls, decls, parent, s, l); + AIEND break; default: die("Unsupported stmt node\n"); @@ -257,15 +257,16 @@ struct ast *ast_scc(struct ast *ast) if (ast->decls[ffun]->type == dfundecl) break; //Number of functions - int nfun = ast->ndecls-ffun; + size_t nfun = ast->ndecls-ffun; //Calculate the edges struct decl **fundecls = ast->decls+ffun; struct list *edges = NULL; - for (int i = 0; idata.dfun->nbody; j++) - edges = edges_stmt(nfun, fundecls, fundecls[i], - fundecls[i]->data.dfun->body[j], edges); + for (size_t i = 0; idata.dfun->body) + edges = edges_stmt(nfun, fundecls, fundecls[i], s, edges); + AIEND + } int nedges; struct edge **edata = (struct edge **) list_to_array(edges, &nedges, false, 0); @@ -277,11 +278,10 @@ struct ast *ast_scc(struct ast *ast) for (struct components *c = cs; c != NULL; c = c->next) { struct decl *d = xalloc(1, struct decl); d->type = dcomp; - d->data.dcomp.ndecls = c->nnodes; - d->data.dcomp.decls = xalloc(c->nnodes, struct fundecl *); + array_init(&d->data.dcomp, c->nnodes); for (int j = 0; jnnodes; j++) - d->data.dcomp.decls[j] = - ((struct decl *)c->nodes[j])->data.dfun; + d->data.dcomp = array_append(d->data.dcomp, + ((struct decl *)c->nodes[j])->data.dfun); ast->decls[i++] = d; } ast->ndecls = i; diff --git a/splc.c b/splc.c index 7ea51b2..419d13a 100644 --- a/splc.c +++ b/splc.c @@ -69,18 +69,20 @@ int main(int argc, char *argv[]) //Parse r = yyparse(&result); + if (yyin != stdin) safe_fclose(yyin); yylex_destroy(); if (r != 0) return r; + fprintf(stderr, "lexical and syntactical done\n"); if (pparse) ast_print(result, stdout); //Typecheck - if ((result = sem(result)) == NULL) { + if ((result = sem(result)) == NULL) return 1; - } + fprintf(stderr, "semantic analyses done\n"); if (ptype) ast_print(result, stdout); @@ -91,12 +93,13 @@ int main(int argc, char *argv[]) free(cfile); switch(lang) { case langc: - genc(result, cout); +// genc(result, cout); break; default: die("unsupported language\n"); } safe_fclose(cout); + fprintf(stderr, "code generation* done\n"); ast_free(result); return r; } -- 2.20.1