ast.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <string.h>
   4
   5 #include "util.h"
   6 #include "ast.h"
   7
   8 #ifdef DEBUG
   9 static const char *ast_type_str[] = {
  10         [an_assign] = "assign", [an_bool] = "bool", [an_binop] = "binop",
  11         [an_char] = "char", [an_cons] = "cons", [an_funcall] = "funcall",
  12         [an_fundecl] = "fundecl", [an_ident] = "ident", [an_if] = "if",
  13         [an_int] = "int", [an_nil] = "nil", [an_list] = "list",
  14         [an_return] = "return", [an_stmt_expr] = "stmt_expr",
  15         [an_tuple] = "tuple", [an_unop] = "unop", [an_vardecl] = "vardecl",
  16         [an_while] = "while",
  17 };
  18 #endif
  19 static const char *binop_str[] = {
  20         [binor] = "||", [binand] = "&&", [eq] = "==", [neq] = "!=",
  21         [leq] = "<=", [le] = "<", [geq] = ">=", [ge] = ">", [cons] = ":",
  22         [plus] = "+", [minus] = "-", [times] = "*", [divide] = "/",
  23         [modulo] = "%", [power] = "^",
  24 };
  25 static const char *fieldspec_str[] = {
  26         [fst] = "fst", [snd] = "snd", [hd] = "hd", [tl] = "tl"};
  27 static const char *unop_str[] = { [inverse] = "!", [negate] = "-", };
  28
  29 #ifdef DEBUG
  30 #define must_be(node, ntype, msg) {\
  31         if ((node)->type != (ntype)) {\
  32                 fprintf(stderr, "%s can't be %s\n",\
  33                         msg, ast_type_str[node->type]);\
  34                 exit(1);\
  35         }\
  36 }
  37 #else
  38 #define must_be(node, ntype, msg) ;
  39 #endif
  40
  41 #define ast_alloc() ((struct ast *)safe_malloc(sizeof(struct ast)))
  42
  43 struct ast *ast_assign(struct ast *ident, struct ast *expr)
  44 {
  45         struct ast *res = ast_alloc();
  46         res->type = an_assign;
  47         res->data.an_assign.ident = ident;
  48         res->data.an_assign.expr = expr;
  49         return res;
  50 }
  51
  52 struct ast *ast_binop(struct ast *l, enum binop op, struct ast *r)
  53 {
  54         struct ast *res = ast_alloc();
  55         res->type = an_binop;
  56         res->data.an_binop.l = l;
  57         res->data.an_binop.op = op;
  58         res->data.an_binop.r = r;
  59         return res;
  60 }
  61
  62 struct ast *ast_bool(bool b)
  63 {
  64         struct ast *res = ast_alloc();
  65         res->type = an_bool;
  66         res->data.an_bool = b;
  67         return res;
  68 }
  69
  70 int fromHex(char c)
  71 {
  72         if (c >= '0' && c <= '9')
  73                 return c-'0';
  74         if (c >= 'a' && c <= 'f')
  75                 return c-'a'+10;
  76         if (c >= 'A' && c <= 'F')
  77                 return c-'A'+10;
  78         return -1;
  79 }
  80
  81 struct ast *ast_char(const char *c)
  82 {
  83         struct ast *res = ast_alloc();
  84         res->type = an_char;
  85         //regular char
  86         if (strlen(c) == 3)
  87                 res->data.an_char = c[1];
  88         //escape
  89         if (strlen(c) == 4)
  90                 switch(c[2]) {
  91                 case '0': res->data.an_char = '\0'; break;
  92                 case 'a': res->data.an_char = '\a'; break;
  93                 case 'b': res->data.an_char = '\b'; break;
  94                 case 't': res->data.an_char = '\t'; break;
  95                 case 'v': res->data.an_char = '\v'; break;
  96                 case 'f': res->data.an_char = '\f'; break;
  97                 case 'r': res->data.an_char = '\r'; break;
  98                 }
  99         //hex escape
 100         if (strlen(c) == 6)
 101                 res->data.an_char = (fromHex(c[3])<<4)+fromHex(c[4]);
 102         return res;
 103 }
 104
 105 struct ast *ast_cons(struct ast *el, struct ast *tail)
 106 {
 107         struct ast *res = ast_alloc();
 108         res->type = an_cons;
 109         res->data.an_cons.el = el;
 110         res->data.an_cons.tail = tail;
 111         return res;
 112 }
 113
 114 struct ast *ast_funcall(struct ast *ident, struct ast *args)
 115 {
 116         struct ast *res = ast_alloc();
 117         res->type = an_funcall;
 118
 119         //ident
 120         must_be(ident, an_ident, "ident of a funcall");
 121         res->data.an_funcall.ident = ident->data.an_ident.ident;
 122         free(ident->data.an_ident.fields);
 123         free(ident);
 124
 125         //args
 126         must_be(args, an_list, "args of a funcall");
 127         res->data.an_funcall.nargs = args->data.an_list.n;
 128         res->data.an_funcall.args = args->data.an_list.ptr;
 129         free(args);
 130         return res;
 131 }
 132
 133 struct ast *ast_fundecl(struct ast *ident, struct ast *args, struct ast *body)
 134 {
 135         struct ast *res = ast_alloc();
 136         res->type = an_fundecl;
 137
 138         //ident
 139         must_be(ident, an_ident, "ident of a fundecl");
 140         res->data.an_fundecl.ident = ident->data.an_ident.ident;
 141         free(ident->data.an_ident.fields);
 142         free(ident);
 143
 144         //args
 145         must_be(args, an_list, "args of a fundecl");
 146         res->data.an_fundecl.nargs = args->data.an_list.n;
 147         res->data.an_fundecl.args = (char **)args->data.an_list.ptr;
 148         for (int i = 0; i<args->data.an_list.n; i++) {
 149                 struct ast *e = args->data.an_list.ptr[i];
 150                 must_be(e, an_ident, "arg of a fundecl")
 151                 res->data.an_fundecl.args[i] = e->data.an_ident.ident;
 152                 free(e->data.an_ident.fields);
 153                 free(e);
 154         }
 155         free(args);
 156
 157         //body
 158         must_be(body, an_list, "body of a fundecl");
 159         res->data.an_fundecl.nbody = body->data.an_list.n;
 160         res->data.an_fundecl.body = body->data.an_list.ptr;
 161         free(body);
 162
 163         return res;
 164 }
 165
 166 struct ast *ast_if(struct ast *pred, struct ast *then, struct ast *els)
 167 {
 168         struct ast *res = ast_alloc();
 169         res->type = an_if;
 170         res->data.an_if.pred = pred;
 171
 172         must_be(then, an_list, "body of a then");
 173         res->data.an_if.nthen = then->data.an_list.n;
 174         res->data.an_if.then = then->data.an_list.ptr;
 175         free(then);
 176
 177         must_be(els, an_list, "body of a els");
 178         res->data.an_if.nels = els->data.an_list.n;
 179         res->data.an_if.els = els->data.an_list.ptr;
 180         free(els);
 181
 182         return res;
 183 }
 184
 185 struct ast *ast_int(int integer)
 186 {
 187         struct ast *res = ast_alloc();
 188         res->type = an_int;
 189         res->data.an_int = integer;
 190         return res;
 191 }
 192
 193 struct ast *ast_identc(char *ident)
 194 {
 195         struct ast *res = ast_alloc();
 196         res->type = an_ident;
 197         res->data.an_ident.ident = safe_strdup(ident);
 198         res->data.an_ident.nfields = 0;
 199         res->data.an_ident.fields = NULL;
 200         return res;
 201 }
 202
 203 struct ast *ast_ident(struct ast *ident, struct ast *fields)
 204 {
 205         struct ast *res = ast_alloc();
 206         res->type = an_ident;
 207         must_be(fields, an_ident, "ident of an ident");
 208         res->data.an_ident.ident = ident->data.an_ident.ident;
 209         free(ident);
 210
 211         must_be(fields, an_list, "fields of an ident");
 212         res->data.an_ident.nfields = fields->data.an_list.n;
 213         res->data.an_ident.fields = (enum fieldspec *)safe_malloc(
 214                 fields->data.an_list.n*sizeof(enum fieldspec));
 215         for (int i = 0; i<fields->data.an_list.n; i++) {
 216                 struct ast *t = fields->data.an_list.ptr[i];
 217                 must_be(t, an_ident, "field of an ident");
 218                 if (strcmp(t->data.an_ident.ident, "fst") == 0)
 219                         res->data.an_ident.fields[i] = fst;
 220                 else if (strcmp(t->data.an_ident.ident, "snd") == 0)
 221                         res->data.an_ident.fields[i] = snd;
 222                 else if (strcmp(t->data.an_ident.ident, "hd") == 0)
 223                         res->data.an_ident.fields[i] = hd;
 224                 else if (strcmp(t->data.an_ident.ident, "tl") == 0)
 225                         res->data.an_ident.fields[i] = tl;
 226                 free(t->data.an_ident.ident);
 227                 free(t);
 228         }
 229         free(fields->data.an_list.ptr);
 230         free(fields);
 231         return res;
 232 }
 233
 234 struct ast *ast_list(struct ast *llist)
 235 {
 236         struct ast *res = ast_alloc();
 237         res->type = an_list;
 238         res->data.an_list.n = 0;
 239
 240         int i = ast_llistlength(llist);
 241
 242         //Allocate array
 243         res->data.an_list.n = i;
 244         res->data.an_list.ptr = (struct ast **)safe_malloc(
 245                 res->data.an_list.n*sizeof(struct ast *));
 246
 247         struct ast *r = llist;
 248         while(i > 0) {
 249                 res->data.an_list.ptr[--i] = r->data.an_cons.el;
 250                 struct ast *t = r;
 251                 r = r->data.an_cons.tail;
 252                 free(t);
 253         }
 254         return res;
 255 }
 256
 257 struct ast *ast_nil()
 258 {
 259         struct ast *res = ast_alloc();
 260         res->type = an_nil;
 261         return res;
 262 }
 263
 264 struct ast *ast_return(struct ast *r)
 265 {
 266         struct ast *res = ast_alloc();
 267         res->type = an_return;
 268         res->data.an_return = r;
 269         return res;
 270 }
 271
 272 struct ast *ast_stmt_expr(struct ast *expr)
 273 {
 274         struct ast *res = ast_alloc();
 275         res->type = an_stmt_expr;
 276         res->data.an_stmt_expr = expr;
 277         return res;
 278 }
 279
 280 struct ast *ast_tuple(struct ast *left, struct ast *right)
 281 {
 282         struct ast *res = ast_alloc();
 283         res->type = an_tuple;
 284         res->data.an_tuple.left = left;
 285         res->data.an_tuple.right = right;
 286         return res;
 287 }
 288
 289
 290 struct ast *ast_unop(enum unop op, struct ast *l)
 291 {
 292         struct ast *res = ast_alloc();
 293         res->type = an_unop;
 294         res->data.an_unop.op = op;
 295         res->data.an_unop.l = l;
 296         return res;
 297 }
 298
 299 struct ast *ast_vardecl(struct ast *ident, struct ast *l)
 300 {
 301         struct ast *res = ast_alloc();
 302         res->type = an_vardecl;
 303         must_be(ident, an_ident, "ident of a vardecl");
 304
 305         res->data.an_vardecl.ident = ident->data.an_ident.ident;
 306         free(ident->data.an_ident.fields);
 307         free(ident);
 308         res->data.an_vardecl.l = l;
 309         return res;
 310 }
 311
 312 struct ast *ast_while(struct ast *pred, struct ast *body)
 313 {
 314         struct ast *res = ast_alloc();
 315         res->type = an_while;
 316         res->data.an_while.pred = pred;
 317         must_be(body, an_list, "body of a while");
 318         res->data.an_while.nbody = body->data.an_list.n;
 319         res->data.an_while.body = body->data.an_list.ptr;
 320         free(body);
 321         return res;
 322 }
 323
 324 int ast_llistlength(struct ast *r)
 325 {
 326         int i = 0;
 327         while(r != NULL) {
 328                 i++;
 329                 if (r->type != an_cons) {
 330                         return 1;
 331                 }
 332                 r = r->data.an_cons.tail;
 333         }
 334         return i;
 335 }
 336
 337 const char *cescapes[] = {
 338         [0] = "\\0", [1] = "\\x01", [2] = "\\x02", [3] = "\\x03",
 339         [4] = "\\x04", [5] = "\\x05", [6] = "\\x06", [7] = "\\a", [8] = "\\b",
 340         [9] = "\\t", [10] = "\\n", [11] = "\\v", [12] = "\\f", [13] = "\\r",
 341         [14] = "\\x0E", [15] = "\\x0F", [16] = "\\x10", [17] = "\\x11",
 342         [18] = "\\x12", [19] = "\\x13", [20] = "\\x14", [21] = "\\x15",
 343         [22] = "\\x16", [23] = "\\x17", [24] = "\\x18", [25] = "\\x19",
 344         [26] = "\\x1A", [27] = "\\x1B", [28] = "\\x1C", [29] = "\\x1D",
 345         [30] = "\\x1E", [31] = "\\x1F",
 346         [127] = "\\x7F"
 347 };
 348
 349 void ast_print(struct ast *ast, int indent, FILE *out)
 350 {
 351         if (ast == NULL)
 352                 return;
 353 #ifdef DEBUG
 354         fprintf(stderr, "ast_free(%s)\n", ast_type_str[ast->type]);
 355 #endif
 356         switch(ast->type) {
 357         case an_assign:
 358                 pindent(indent, out);
 359                 ast_print(ast->data.an_assign.ident, indent, out);
 360                 safe_fprintf(out, " = ");
 361                 ast_print(ast->data.an_assign.expr, indent, out);
 362                 safe_fprintf(out, ";\n");
 363                 break;
 364         case an_binop:
 365                 safe_fprintf(out, "(");
 366                 ast_print(ast->data.an_binop.l, indent, out);
 367                 safe_fprintf(out, "%s", binop_str[ast->data.an_binop.op]);
 368                 ast_print(ast->data.an_binop.r, indent, out);
 369                 safe_fprintf(out, ")");
 370                 break;
 371         case an_bool:
 372                 safe_fprintf(out, "%s", ast->data.an_bool ? "true" : "false");
 373                 break;
 374         case an_char:
 375                 if (ast->data.an_char < 0)
 376                         safe_fprintf(out, "'?'");
 377                 if (ast->data.an_char < ' ' || ast->data.an_char == 127)
 378                         safe_fprintf(out, "'%s'",
 379                                 cescapes[(int)ast->data.an_char]);
 380                 else
 381                         safe_fprintf(out, "'%c'", ast->data.an_char);
 382                 break;
 383         case an_funcall:
 384                 safe_fprintf(out, "%s(", ast->data.an_funcall.ident);
 385                 for(int i = 0; i<ast->data.an_fundecl.nargs; i++) {
 386                         ast_print(ast->data.an_funcall.args[i], indent, out);
 387                         if (i+1 < ast->data.an_fundecl.nargs)
 388                                 safe_fprintf(out, ", ");
 389                 }
 390                 safe_fprintf(out, ")");
 391                 break;
 392         case an_fundecl:
 393                 pindent(indent, out);
 394                 safe_fprintf(out, "%s (", ast->data.an_fundecl.ident);
 395                 for (int i = 0; i<ast->data.an_fundecl.nargs; i++) {
 396                         safe_fprintf(out, "%s", ast->data.an_fundecl.args[i]);
 397                         if (i < ast->data.an_fundecl.nargs - 1)
 398                                 safe_fprintf(out, ", ");
 399                 }
 400                 safe_fprintf(out, ") {\n");
 401                 for (int i = 0; i<ast->data.an_fundecl.nbody; i++)
 402                         ast_print(ast->data.an_fundecl.body[i], indent+1, out);
 403                 pindent(indent, out);
 404                 safe_fprintf(out, "}\n");
 405                 break;
 406         case an_if:
 407                 pindent(indent, out);
 408                 safe_fprintf(out, "if (");
 409                 ast_print(ast->data.an_if.pred, indent, out);
 410                 safe_fprintf(out, ") {\n");
 411                 for (int i = 0; i<ast->data.an_if.nthen; i++)
 412                         ast_print(ast->data.an_if.then[i], indent+1, out);
 413                 pindent(indent, out);
 414                 safe_fprintf(out, "} else {\n");
 415                 for (int i = 0; i<ast->data.an_if.nels; i++)
 416                         ast_print(ast->data.an_if.els[i], indent+1, out);
 417                 pindent(indent, out);
 418                 safe_fprintf(out, "}\n");
 419                 break;
 420         case an_int:
 421                 safe_fprintf(out, "%d", ast->data.an_int);
 422                 break;
 423         case an_ident:
 424                 fprintf(out, "%s", ast->data.an_ident.ident);
 425                 for (int i = 0; i<ast->data.an_ident.nfields; i++)
 426                         fprintf(out, ".%s",
 427                                 fieldspec_str[ast->data.an_ident.fields[i]]);
 428                 break;
 429         case an_cons:
 430                 ast_print(ast->data.an_cons.el, indent, out);
 431                 ast_print(ast->data.an_cons.tail, indent, out);
 432                 break;
 433         case an_list:
 434                 for (int i = 0; i<ast->data.an_list.n; i++)
 435                         ast_print(ast->data.an_list.ptr[i], indent, out);
 436                 break;
 437         case an_nil:
 438                 safe_fprintf(out, "[]");
 439                 break;
 440         case an_return:
 441                 pindent(indent, out);
 442                 safe_fprintf(out, "return ");
 443                 ast_print(ast->data.an_return, indent, out);
 444                 safe_fprintf(out, ";\n");
 445                 break;
 446         case an_stmt_expr:
 447                 pindent(indent, out);
 448                 ast_print(ast->data.an_stmt_expr, indent, out);
 449                 safe_fprintf(out, ";\n");
 450                 break;
 451         case an_tuple:
 452                 safe_fprintf(out, "(");
 453                 ast_print(ast->data.an_tuple.left, indent, out);
 454                 safe_fprintf(out, ", ");
 455                 ast_print(ast->data.an_tuple.right, indent, out);
 456                 safe_fprintf(out, ")");
 457                 break;
 458         case an_unop:
 459                 safe_fprintf(out, "(%s", unop_str[ast->data.an_unop.op]);
 460                 ast_print(ast->data.an_unop.l, indent, out);
 461                 safe_fprintf(out, ")");
 462                 break;
 463         case an_vardecl:
 464                 pindent(indent, out);
 465                 safe_fprintf(out, "var %s = ", ast->data.an_vardecl.ident);
 466                 ast_print(ast->data.an_vardecl.l, indent, out);
 467                 safe_fprintf(out, ";\n");
 468                 break;
 469         case an_while:
 470                 pindent(indent, out);
 471                 safe_fprintf(out, "while (");
 472                 ast_print(ast->data.an_while.pred, indent, out);
 473                 safe_fprintf(out, ") {\n");
 474                 for (int i = 0; i<ast->data.an_while.nbody; i++) {
 475                         ast_print(ast->data.an_while.body[i], indent+1, out);
 476                 }
 477                 pindent(indent, out);
 478                 safe_fprintf(out, "}\n");
 479                 break;
 480         default:
 481                 die("Unsupported AST node\n");
 482         }
 483 }
 484
 485 void ast_free(struct ast *ast)
 486 {
 487         if (ast == NULL)
 488                 return;
 489 #ifdef DEBUG
 490         fprintf(stderr, "ast_free(%s)\n", ast_type_str[ast->type]);
 491 #endif
 492         switch(ast->type) {
 493         case an_assign:
 494                 ast_free(ast->data.an_assign.ident);
 495                 ast_free(ast->data.an_assign.expr);
 496                 break;
 497         case an_binop:
 498                 ast_free(ast->data.an_binop.l);
 499                 ast_free(ast->data.an_binop.r);
 500                 break;
 501         case an_bool:
 502                 break;
 503         case an_char:
 504                 break;
 505         case an_cons:
 506                 ast_free(ast->data.an_cons.el);
 507                 ast_free(ast->data.an_cons.tail);
 508                 break;
 509         case an_funcall:
 510                 free(ast->data.an_funcall.ident);
 511                 for (int i = 0; i<ast->data.an_fundecl.nargs; i++)
 512                         ast_free(ast->data.an_funcall.args[i]);
 513                 free(ast->data.an_funcall.args);
 514                 break;
 515         case an_fundecl:
 516                 free(ast->data.an_fundecl.ident);
 517                 for (int i = 0; i<ast->data.an_fundecl.nargs; i++)
 518                         free(ast->data.an_fundecl.args[i]);
 519                 free(ast->data.an_fundecl.args);
 520                 for (int i = 0; i<ast->data.an_fundecl.nbody; i++)
 521                         ast_free(ast->data.an_fundecl.body[i]);
 522                 free(ast->data.an_fundecl.body);
 523                 break;
 524         case an_if:
 525                 ast_free(ast->data.an_if.pred);
 526                 for (int i = 0; i<ast->data.an_if.nthen; i++)
 527                         ast_free(ast->data.an_if.then[i]);
 528                 free(ast->data.an_if.then);
 529                 for (int i = 0; i<ast->data.an_if.nels; i++)
 530                         ast_free(ast->data.an_if.els[i]);
 531                 free(ast->data.an_if.els);
 532                 break;
 533         case an_int:
 534                 break;
 535         case an_ident:
 536                 free(ast->data.an_ident.ident);
 537                 free(ast->data.an_ident.fields);
 538                 break;
 539         case an_list:
 540                 for (int i = 0; i<ast->data.an_list.n; i++)
 541                         ast_free(ast->data.an_list.ptr[i]);
 542                 free(ast->data.an_list.ptr);
 543                 break;
 544         case an_nil:
 545                 break;
 546         case an_return:
 547                 ast_free(ast->data.an_return);
 548                 break;
 549         case an_stmt_expr:
 550                 ast_free(ast->data.an_stmt_expr);
 551                 break;
 552         case an_tuple:
 553                 ast_free(ast->data.an_tuple.left);
 554                 ast_free(ast->data.an_tuple.right);
 555                 break;
 556         case an_unop:
 557                 ast_free(ast->data.an_unop.l);
 558                 break;
 559         case an_vardecl:
 560                 free(ast->data.an_vardecl.ident);
 561                 ast_free(ast->data.an_vardecl.l);
 562                 break;
 563         case an_while:
 564                 ast_free(ast->data.an_while.pred);
 565                 for (int i = 0; i<ast->data.an_while.nbody; i++)
 566                         ast_free(ast->data.an_while.body[i]);
 567                 free(ast->data.an_while.body);
 568                 break;
 569         default:
 570                 die("Unsupported AST node: %d\n", ast->type);
 571         }
 572         free(ast);
 573 }