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