ast.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <string.h>
   4
   5 #include "util.h"
   6 #include "ast.h"
   7 #include "parse.h"
   8
   9 const char *binop_str[] = {
  10         [binor] = "||", [binand] = "&&", [eq] = "==", [neq] = "!=",
  11         [leq] = "<=", [le] = "<", [geq] = ">=", [ge] = ">", [cons] = ":",
  12         [plus] = "+", [minus] = "-", [times] = "*", [divide] = "/",
  13         [modulo] = "%", [power] = "^",
  14 };
  15 const char *fieldspec_str[] = {
  16         [fst] = "fst", [snd] = "snd", [hd] = "hd", [tl] = "tl"};
  17 const char *unop_str[] = { [inverse] = "!", [negate] = "-", };
  18 static const char *basictype_str[] = {
  19         [btbool] = "Bool", [btchar] = "Char", [btint] = "Int",
  20         [btvoid] = "Void",
  21 };
  22
  23 struct ast *ast(struct list *decls)
  24 {
  25         struct ast *res = safe_malloc(sizeof(struct ast));
  26         res->decls = (struct decl **)list_to_array(decls, &res->ndecls, true);
  27         return res;
  28 }
  29
  30 struct vardecl *vardecl(struct type *type, char *ident, struct expr *expr)
  31 {
  32         struct vardecl *res = safe_malloc(sizeof(struct vardecl));
  33         res->type = type;
  34         res->ident = ident;
  35         res->expr = expr;
  36         return res;
  37 }
  38
  39 struct decl *decl_fun(char *ident, struct list *args, struct list *atypes,
  40         struct type *rtype, struct list *body)
  41 {
  42         struct decl *res = safe_malloc(sizeof(struct decl));
  43         res->type = dfundecl;
  44         res->data.dfun.ident = ident;
  45         res->data.dfun.args = (char **)
  46                 list_to_array(args, &res->data.dfun.nargs, true);
  47         res->data.dfun.atypes = (struct type **)
  48                 list_to_array(atypes, &res->data.dfun.natypes, true);
  49         res->data.dfun.rtype = rtype;
  50         res->data.dfun.body = (struct stmt **)
  51                 list_to_array(body, &res->data.dfun.nbody, true);
  52         return res;
  53 }
  54
  55 struct decl *decl_var(struct vardecl *vardecl)
  56 {
  57         struct decl *res = safe_malloc(sizeof(struct decl));
  58         res->type = dvardecl;
  59         res->data.dvar = vardecl;
  60         return res;
  61 }
  62
  63 struct stmt *stmt_assign(char *ident, struct list *fields, struct expr *expr)
  64 {
  65         struct stmt *res = safe_malloc(sizeof(struct stmt));
  66         res->type = sassign;
  67         res->data.sassign.ident = ident;
  68         res->data.sassign.fields = (char **)
  69                 list_to_array(fields, &res->data.sassign.nfields, true);
  70         res->data.sassign.expr = expr;
  71         return res;
  72 }
  73
  74 struct stmt *stmt_if(struct expr *pred, struct list *then, struct list *els)
  75 {
  76         struct stmt *res = safe_malloc(sizeof(struct stmt));
  77         res->type = sif;
  78         res->data.sif.pred = pred;
  79         res->data.sif.then = (struct stmt **)
  80                 list_to_array(then, &res->data.sif.nthen, true);
  81         res->data.sif.els = (struct stmt **)
  82                 list_to_array(els, &res->data.sif.nels, true);
  83         return res;
  84 }
  85
  86 struct stmt *stmt_return(struct expr *rtrn)
  87 {
  88         struct stmt *res = safe_malloc(sizeof(struct stmt));
  89         res->type = sreturn;
  90         res->data.sreturn = rtrn;
  91         return res;
  92 }
  93
  94 struct stmt *stmt_expr(struct expr *expr)
  95 {
  96         struct stmt *res = safe_malloc(sizeof(struct stmt));
  97         res->type = sexpr;
  98         res->data.sexpr = expr;
  99         return res;
 100 }
 101
 102 struct stmt *stmt_vardecl(struct vardecl *vardecl)
 103 {
 104         struct stmt *res = safe_malloc(sizeof(struct stmt));
 105         res->type = svardecl;
 106         res->data.svardecl = vardecl;
 107         return res;
 108 }
 109
 110 struct stmt *stmt_while(struct expr *pred, struct list *body)
 111 {
 112         struct stmt *res = safe_malloc(sizeof(struct stmt));
 113         res->type = swhile;
 114         res->data.swhile.pred = pred;
 115         res->data.swhile.body = (struct stmt **)
 116                 list_to_array(body, &res->data.swhile.nbody, true);
 117         return res;
 118 }
 119
 120 struct expr *expr_binop(struct expr *l, enum binop op, struct expr *r)
 121 {
 122         struct expr *res = safe_malloc(sizeof(struct expr));
 123         res->type = ebinop;
 124         res->data.ebinop.l = l;
 125         res->data.ebinop.op = op;
 126         res->data.ebinop.r = r;
 127         return res;
 128 }
 129
 130 struct expr *expr_bool(bool b)
 131 {
 132         struct expr *res = safe_malloc(sizeof(struct expr));
 133         res->type = ebool;
 134         res->data.ebool = b;
 135         return res;
 136 }
 137
 138 struct expr *expr_char(char *c)
 139 {
 140         struct expr *res = safe_malloc(sizeof(struct expr));
 141         res->type = echar;
 142         res->data.echar = unescape_char(c)[0];
 143         return res;
 144 }
 145
 146 static void set_fields(enum fieldspec **farray, int *n, struct list *fields)
 147 {
 148         void **els = list_to_array(fields, n, true);
 149         *farray = (enum fieldspec *)safe_malloc(*n*sizeof(enum fieldspec));
 150         for (int i = 0; i<*n; i++) {
 151                 char *t = els[i];
 152                 if (strcmp(t, "fst") == 0)
 153                         (*farray)[i] = fst;
 154                 else if (strcmp(t, "snd") == 0)
 155                         (*farray)[i] = snd;
 156                 else if (strcmp(t, "hd") == 0)
 157                         (*farray)[i] = hd;
 158                 else if (strcmp(t, "tl") == 0)
 159                         (*farray)[i] = tl;
 160                 free(t);
 161         }
 162         free(els);
 163 }
 164
 165
 166 struct expr *expr_funcall(char *ident, struct list *args, struct list *fields)
 167 {
 168         struct expr *res = safe_malloc(sizeof(struct expr));
 169         res->type = efuncall;
 170         res->data.efuncall.ident = ident;
 171         res->data.efuncall.args = (struct expr **)
 172                 list_to_array(args, &res->data.efuncall.nargs, true);
 173         set_fields(&res->data.efuncall.fields,
 174                 &res->data.efuncall.nfields, fields);
 175         return res;
 176 }
 177
 178 struct expr *expr_int(int integer)
 179 {
 180         struct expr *res = safe_malloc(sizeof(struct expr));
 181         res->type = eint;
 182         res->data.eint = integer;
 183         return res;
 184 }
 185
 186 struct expr *expr_ident(char *ident, struct list *fields)
 187 {
 188         struct expr *res = safe_malloc(sizeof(struct expr));
 189         res->type = eident;
 190         res->data.eident.ident = ident;
 191         set_fields(&res->data.eident.fields, &res->data.eident.nfields, fields);
 192         return res;
 193 }
 194
 195 struct expr *expr_nil()
 196 {
 197         struct expr *res = safe_malloc(sizeof(struct expr));
 198         res->type = enil;
 199         return res;
 200 }
 201
 202 struct expr *expr_tuple(struct expr *left, struct expr *right)
 203 {
 204         struct expr *res = safe_malloc(sizeof(struct expr));
 205         res->type = etuple;
 206         res->data.etuple.left = left;
 207         res->data.etuple.right = right;
 208         return res;
 209 }
 210
 211 struct expr *expr_string(char *str)
 212 {
 213         struct expr *res = safe_malloc(sizeof(struct expr));
 214         res->type = estring;
 215         res->data.estring.nchars = 0;
 216         res->data.estring.chars = safe_malloc(strlen(str)+1);
 217         char *p = res->data.estring.chars;
 218         while(*str != '\0') {
 219                 str = unescape_char(str);
 220                 *p++ = *str++;
 221                 res->data.estring.nchars++;
 222         }
 223         *p = '\0';
 224         return res;
 225 }
 226
 227 struct expr *expr_unop(enum unop op, struct expr *l)
 228 {
 229         struct expr *res = safe_malloc(sizeof(struct expr));
 230         res->type = eunop;
 231         res->data.eunop.op = op;
 232         res->data.eunop.l = l;
 233         return res;
 234 }
 235
 236 struct type *type_basic(enum basictype type)
 237 {
 238         struct type *res = safe_malloc(sizeof(struct type));
 239         res->type = tbasic;
 240         res->data.tbasic = type;
 241         return res;
 242 }
 243
 244 struct type *type_list(struct type *type)
 245 {
 246         struct type *res = safe_malloc(sizeof(struct type));
 247         res->type = tlist;
 248         res->data.tlist = type;
 249         return res;
 250 }
 251
 252 struct type *type_tuple(struct type *l, struct type *r)
 253 {
 254         struct type *res = safe_malloc(sizeof(struct type));
 255         res->type = ttuple;
 256         res->data.ttuple.l = l;
 257         res->data.ttuple.r = r;
 258         return res;
 259 }
 260
 261 struct type *type_var(char *ident)
 262 {
 263         struct type *res = safe_malloc(sizeof(struct type));
 264         if (strcmp(ident, "Int") == 0) {
 265                 res->type = tbasic;
 266                 res->data.tbasic = btint;
 267                 free(ident);
 268         } else if (strcmp(ident, "Char") == 0) {
 269                 res->type = tbasic;
 270                 res->data.tbasic = btchar;
 271                 free(ident);
 272         } else if (strcmp(ident, "Bool") == 0) {
 273                 res->type = tbasic;
 274                 res->data.tbasic = btbool;
 275                 free(ident);
 276         } else if (strcmp(ident, "Void") == 0) {
 277                 res->type = tbasic;
 278                 res->data.tbasic = btvoid;
 279                 free(ident);
 280         } else {
 281                 res->type = tvar;
 282                 res->data.tvar = ident;
 283         }
 284         return res;
 285 }
 286
 287 void ast_print(struct ast *ast, FILE *out)
 288 {
 289         if (ast == NULL)
 290                 return;
 291         for (int i = 0; i<ast->ndecls; i++)
 292                 decl_print(ast->decls[i], out);
 293 }
 294
 295 void vardecl_print(struct vardecl *decl, int indent, FILE *out)
 296 {
 297         pindent(indent, out);
 298         if (decl->type == NULL)
 299                 safe_fprintf(out, "var");
 300         else
 301                 type_print(decl->type, out);
 302         safe_fprintf(out, " %s = ", decl->ident);
 303         expr_print(decl->expr, out);
 304         safe_fprintf(out, ";\n");
 305 }
 306
 307 void decl_print(struct decl *decl, FILE *out)
 308 {
 309         if (decl == NULL)
 310                 return;
 311         switch(decl->type) {
 312         case dfundecl:
 313                 safe_fprintf(out, "%s (", decl->data.dfun.ident);
 314                 for (int i = 0; i<decl->data.dfun.nargs; i++) {
 315                         safe_fprintf(out, "%s", decl->data.dfun.args[i]);
 316                         if (i < decl->data.dfun.nargs - 1)
 317                                 safe_fprintf(out, ", ");
 318                 }
 319                 safe_fprintf(out, ")");
 320                 if (decl->data.dfun.rtype != NULL) {
 321                         safe_fprintf(out, " :: ");
 322                         for (int i = 0; i<decl->data.dfun.natypes; i++) {
 323                                 type_print(decl->data.dfun.atypes[i], out);
 324                                 safe_fprintf(out, " ");
 325                         }
 326                         safe_fprintf(out, "-> ");
 327                         type_print(decl->data.dfun.rtype, out);
 328                 }
 329                 safe_fprintf(out, " {\n");
 330                 for (int i = 0; i<decl->data.dfun.nbody; i++)
 331                         stmt_print(decl->data.dfun.body[i], 1, out);
 332                 safe_fprintf(out, "}\n");
 333                 break;
 334         case dvardecl:
 335                 vardecl_print(decl->data.dvar, 0, out);
 336                 break;
 337         case dcomponent:
 338                 for (int i = 0; i<decl->data.dcomponent.ndecls; i++)
 339                         decl_print(decl, out);
 340                 break;
 341         default:
 342                 die("Unsupported decl node\n");
 343         }
 344 }
 345
 346 void stmt_print(struct stmt *stmt, int indent, FILE *out)
 347 {
 348         if (stmt == NULL)
 349                 return;
 350         switch(stmt->type) {
 351         case sassign:
 352                 pindent(indent, out);
 353                 fprintf(out, "%s", stmt->data.sassign.ident);
 354                 for (int i = 0; i<stmt->data.sassign.nfields; i++)
 355                         fprintf(out, ".%s", stmt->data.sassign.fields[i]);
 356                 safe_fprintf(out, " = ");
 357                 expr_print(stmt->data.sassign.expr, out);
 358                 safe_fprintf(out, ";\n");
 359                 break;
 360         case sif:
 361                 pindent(indent, out);
 362                 safe_fprintf(out, "if (");
 363                 expr_print(stmt->data.sif.pred, out);
 364                 safe_fprintf(out, ") {\n");
 365                 for (int i = 0; i<stmt->data.sif.nthen; i++)
 366                         stmt_print(stmt->data.sif.then[i], indent+1, out);
 367                 pindent(indent, out);
 368                 safe_fprintf(out, "} else {\n");
 369                 for (int i = 0; i<stmt->data.sif.nels; i++)
 370                         stmt_print(stmt->data.sif.els[i], indent+1, out);
 371                 pindent(indent, out);
 372                 safe_fprintf(out, "}\n");
 373                 break;
 374         case sreturn:
 375                 pindent(indent, out);
 376                 safe_fprintf(out, "return ");
 377                 expr_print(stmt->data.sreturn, out);
 378                 safe_fprintf(out, ";\n");
 379                 break;
 380         case sexpr:
 381                 pindent(indent, out);
 382                 expr_print(stmt->data.sexpr, out);
 383                 safe_fprintf(out, ";\n");
 384                 break;
 385         case svardecl:
 386                 vardecl_print(stmt->data.svardecl, indent, out);
 387                 break;
 388         case swhile:
 389                 pindent(indent, out);
 390                 safe_fprintf(out, "while (");
 391                 expr_print(stmt->data.swhile.pred, out);
 392                 safe_fprintf(out, ") {\n");
 393                 for (int i = 0; i<stmt->data.swhile.nbody; i++)
 394                         stmt_print(stmt->data.swhile.body[i], indent+1, out);
 395                 pindent(indent, out);
 396                 safe_fprintf(out, "}\n");
 397                 break;
 398         default:
 399                 die("Unsupported stmt node\n");
 400         }
 401 }
 402
 403 void expr_print(struct expr *expr, FILE *out)
 404 {
 405         if (expr == NULL)
 406                 return;
 407         char buf[] = "\\xff";
 408         switch(expr->type) {
 409         case ebinop:
 410                 safe_fprintf(out, "(");
 411                 expr_print(expr->data.ebinop.l, out);
 412                 safe_fprintf(out, "%s", binop_str[expr->data.ebinop.op]);
 413                 expr_print(expr->data.ebinop.r, out);
 414                 safe_fprintf(out, ")");
 415                 break;
 416         case ebool:
 417                 safe_fprintf(out, "%s", expr->data.ebool ? "true" : "false");
 418                 break;
 419         case echar:
 420                 safe_fprintf(out, "'%s'",
 421                         escape_char(expr->data.echar, buf, false));
 422                 break;
 423         case efuncall:
 424                 safe_fprintf(out, "%s(", expr->data.efuncall.ident);
 425                 for(int i = 0; i<expr->data.efuncall.nargs; i++) {
 426                         expr_print(expr->data.efuncall.args[i], out);
 427                         if (i+1 < expr->data.efuncall.nargs)
 428                                 safe_fprintf(out, ", ");
 429                 }
 430                 safe_fprintf(out, ")");
 431                 for (int i = 0; i<expr->data.efuncall.nfields; i++)
 432                         fprintf(out, ".%s",
 433                                 fieldspec_str[expr->data.efuncall.fields[i]]);
 434                 break;
 435         case eint:
 436                 safe_fprintf(out, "%d", expr->data.eint);
 437                 break;
 438         case eident:
 439                 fprintf(out, "%s", expr->data.eident.ident);
 440                 for (int i = 0; i<expr->data.eident.nfields; i++)
 441                         fprintf(out, ".%s",
 442                                 fieldspec_str[expr->data.eident.fields[i]]);
 443                 break;
 444         case enil:
 445                 safe_fprintf(out, "[]");
 446                 break;
 447         case etuple:
 448                 safe_fprintf(out, "(");
 449                 expr_print(expr->data.etuple.left, out);
 450                 safe_fprintf(out, ", ");
 451                 expr_print(expr->data.etuple.right, out);
 452                 safe_fprintf(out, ")");
 453                 break;
 454         case estring:
 455                 safe_fprintf(out, "\"");
 456                 for (int i = 0; i<expr->data.estring.nchars; i++)
 457                         safe_fprintf(out, "%s", escape_char(
 458                                 expr->data.estring.chars[i], buf, true));
 459                 safe_fprintf(out, "\"");
 460                 break;
 461         case eunop:
 462                 safe_fprintf(out, "(%s", unop_str[expr->data.eunop.op]);
 463                 expr_print(expr->data.eunop.l, out);
 464                 safe_fprintf(out, ")");
 465                 break;
 466         default:
 467                 die("Unsupported expr node\n");
 468         }
 469 }
 470
 471 void type_print(struct type *type, FILE *out)
 472 {
 473         if (type == NULL)
 474                 return;
 475         switch (type->type) {
 476         case tbasic:
 477                 safe_fprintf(out, "%s", basictype_str[type->data.tbasic]);
 478                 break;
 479         case tlist:
 480                 safe_fprintf(out, "[");
 481                 type_print(type->data.tlist, out);
 482                 safe_fprintf(out, "]");
 483                 break;
 484         case ttuple:
 485                 safe_fprintf(out, "(");
 486                 type_print(type->data.ttuple.l, out);
 487                 safe_fprintf(out, ",");
 488                 type_print(type->data.ttuple.r, out);
 489                 safe_fprintf(out, ")");
 490                 break;
 491         case tvar:
 492                 safe_fprintf(out, "%s", type->data.tvar);
 493                 break;
 494         default:
 495                 die("Unsupported type node\n");
 496         }
 497 }
 498
 499 void ast_free(struct ast *ast)
 500 {
 501         if (ast == NULL)
 502                 return;
 503         for (int i = 0; i<ast->ndecls; i++)
 504                 decl_free(ast->decls[i]);
 505         free(ast->decls);
 506         free(ast);
 507 }
 508
 509 void vardecl_free(struct vardecl *decl)
 510 {
 511         type_free(decl->type);
 512         free(decl->ident);
 513         expr_free(decl->expr);
 514         free(decl);
 515 }
 516
 517 void decl_free(struct decl *decl)
 518 {
 519         if (decl == NULL)
 520                 return;
 521         switch(decl->type) {
 522         case dcomponent:
 523                 for (int i = 0; i<decl->data.dcomponent.ndecls; i++)
 524                         decl_free(decl->data.dcomponent.decls[i]);
 525                 free(decl->data.dcomponent.decls);
 526                 break;
 527         case dfundecl:
 528                 free(decl->data.dfun.ident);
 529                 for (int i = 0; i<decl->data.dfun.nargs; i++)
 530                         free(decl->data.dfun.args[i]);
 531                 free(decl->data.dfun.args);
 532                 for (int i = 0; i<decl->data.dfun.natypes; i++)
 533                         type_free(decl->data.dfun.atypes[i]);
 534                 free(decl->data.dfun.atypes);
 535                 type_free(decl->data.dfun.rtype);
 536                 for (int i = 0; i<decl->data.dfun.nbody; i++)
 537                         stmt_free(decl->data.dfun.body[i]);
 538                 free(decl->data.dfun.body);
 539                 break;
 540         case dvardecl:
 541                 vardecl_free(decl->data.dvar);
 542                 break;
 543         default:
 544                 die("Unsupported decl node\n");
 545         }
 546         free(decl);
 547 }
 548
 549 void stmt_free(struct stmt *stmt)
 550 {
 551         if (stmt == NULL)
 552                 return;
 553         switch(stmt->type) {
 554         case sassign:
 555                 free(stmt->data.sassign.ident);
 556                 for (int i = 0; i<stmt->data.sassign.nfields; i++)
 557                         free(stmt->data.sassign.fields[i]);
 558                 free(stmt->data.sassign.fields);
 559                 expr_free(stmt->data.sassign.expr);
 560                 break;
 561         case sif:
 562                 expr_free(stmt->data.sif.pred);
 563                 for (int i = 0; i<stmt->data.sif.nthen; i++)
 564                         stmt_free(stmt->data.sif.then[i]);
 565                 free(stmt->data.sif.then);
 566                 for (int i = 0; i<stmt->data.sif.nels; i++)
 567                         stmt_free(stmt->data.sif.els[i]);
 568                 free(stmt->data.sif.els);
 569                 break;
 570         case sreturn:
 571                 expr_free(stmt->data.sreturn);
 572                 break;
 573         case sexpr:
 574                 expr_free(stmt->data.sexpr);
 575                 break;
 576         case swhile:
 577                 expr_free(stmt->data.swhile.pred);
 578                 for (int i = 0; i<stmt->data.swhile.nbody; i++)
 579                         stmt_free(stmt->data.swhile.body[i]);
 580                 free(stmt->data.swhile.body);
 581                 break;
 582         case svardecl:
 583                 vardecl_free(stmt->data.svardecl);
 584                 break;
 585         default:
 586                 die("Unsupported stmt node\n");
 587         }
 588         free(stmt);
 589 }
 590
 591 void expr_free(struct expr *expr)
 592 {
 593         if (expr == NULL)
 594                 return;
 595         switch(expr->type) {
 596         case ebinop:
 597                 expr_free(expr->data.ebinop.l);
 598                 expr_free(expr->data.ebinop.r);
 599                 break;
 600         case ebool:
 601                 break;
 602         case echar:
 603                 break;
 604         case efuncall:
 605                 free(expr->data.efuncall.ident);
 606                 for (int i = 0; i<expr->data.efuncall.nargs; i++)
 607                         expr_free(expr->data.efuncall.args[i]);
 608                 free(expr->data.efuncall.fields);
 609                 free(expr->data.efuncall.args);
 610                 break;
 611         case eint:
 612                 break;
 613         case eident:
 614                 free(expr->data.eident.ident);
 615                 free(expr->data.eident.fields);
 616                 break;
 617         case enil:
 618                 break;
 619         case etuple:
 620                 expr_free(expr->data.etuple.left);
 621                 expr_free(expr->data.etuple.right);
 622                 break;
 623         case estring:
 624                 free(expr->data.estring.chars);
 625                 break;
 626         case eunop:
 627                 expr_free(expr->data.eunop.l);
 628                 break;
 629         default:
 630                 die("Unsupported expr node\n");
 631         }
 632         free(expr);
 633 }
 634
 635 void type_free(struct type *type)
 636 {
 637         if (type == NULL)
 638                 return;
 639         switch (type->type) {
 640         case tbasic:
 641                 break;
 642         case tlist:
 643                 type_free(type->data.tlist);
 644                 break;
 645         case ttuple:
 646                 type_free(type->data.ttuple.l);
 647                 type_free(type->data.ttuple.r);
 648                 break;
 649         case tvar:
 650                 free(type->data.tvar);
 651                 break;
 652         default:
 653                 die("Unsupported type node\n");
 654         }
 655         free(type);
 656 }