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