parser.c

   1 #include <stdio.h>
   2 #include <stdarg.h>
   3
   4 #include "gmqcc.h"
   5 #include "lexer.h"
   6
   7 typedef struct {
   8     lex_file *lex;
   9     int      tok;
  10
  11     MEM_VECTOR_MAKE(ast_value*, globals);
  12     MEM_VECTOR_MAKE(ast_function*, functions);
  13     MEM_VECTOR_MAKE(ast_value*, imm_float);
  14     MEM_VECTOR_MAKE(ast_value*, imm_string);
  15     MEM_VECTOR_MAKE(ast_value*, imm_vector);
  16
  17     ast_function *function;
  18     MEM_VECTOR_MAKE(ast_value*, locals);
  19     size_t blocklocal;
  20
  21     size_t errors;
  22 } parser_t;
  23
  24 MEM_VEC_FUNCTIONS(parser_t, ast_value*, globals)
  25 MEM_VEC_FUNCTIONS(parser_t, ast_value*, imm_float)
  26 MEM_VEC_FUNCTIONS(parser_t, ast_value*, imm_string)
  27 MEM_VEC_FUNCTIONS(parser_t, ast_value*, imm_vector)
  28 MEM_VEC_FUNCTIONS(parser_t, ast_value*, locals)
  29 MEM_VEC_FUNCTIONS(parser_t, ast_function*, functions)
  30
  31 void parseerror(parser_t *parser, const char *fmt, ...)
  32 {
  33         va_list ap;
  34
  35         parser->errors++;
  36
  37     if (parser)
  38             printf("error %s:%lu: ", parser->lex->tok->ctx.file, (unsigned long)parser->lex->tok->ctx.line);
  39         else
  40             printf("error: ");
  41
  42         va_start(ap, fmt);
  43         vprintf(fmt, ap);
  44         va_end(ap);
  45
  46         printf("\n");
  47 }
  48
  49 bool parser_next(parser_t *parser)
  50 {
  51     /* lex_do kills the previous token */
  52     parser->tok = lex_do(parser->lex);
  53     if (parser->tok == TOKEN_EOF || parser->tok >= TOKEN_ERROR)
  54         return false;
  55     return true;
  56 }
  57
  58 /* lift a token out of the parser so it's not destroyed by parser_next */
  59 token *parser_lift(parser_t *parser)
  60 {
  61     token *tok = parser->lex->tok;
  62     parser->lex->tok = NULL;
  63     return tok;
  64 }
  65
  66 #define parser_tokval(p) (p->lex->tok->value)
  67 #define parser_token(p)  (p->lex->tok)
  68 #define parser_ctx(p)    (p->lex->tok->ctx)
  69
  70 ast_value* parser_const_float(parser_t *parser, double d)
  71 {
  72     size_t i;
  73     ast_value *out;
  74     for (i = 0; i < parser->imm_float_count; ++i) {
  75         if (parser->imm_float[i]->constval.vfloat == d)
  76             return parser->imm_float[i];
  77     }
  78     out = ast_value_new(parser_ctx(parser), "#IMMEDIATE", TYPE_FLOAT);
  79     out->isconst = true;
  80     out->constval.vfloat = d;
  81     if (!parser_t_imm_float_add(parser, out)) {
  82         ast_value_delete(out);
  83         return NULL;
  84     }
  85     return out;
  86 }
  87
  88 ast_value* parser_const_string(parser_t *parser, const char *str)
  89 {
  90     size_t i;
  91     ast_value *out;
  92     for (i = 0; i < parser->imm_string_count; ++i) {
  93         if (!strcmp(parser->imm_string[i]->constval.vstring, str))
  94             return parser->imm_string[i];
  95     }
  96     out = ast_value_new(parser_ctx(parser), "#IMMEDIATE", TYPE_STRING);
  97     out->isconst = true;
  98     out->constval.vstring = util_strdup(str);
  99     if (!parser_t_imm_string_add(parser, out)) {
 100         ast_value_delete(out);
 101         return NULL;
 102     }
 103     return out;
 104 }
 105
 106 ast_value* parser_const_vector(parser_t *parser, vector v)
 107 {
 108     size_t i;
 109     ast_value *out;
 110     for (i = 0; i < parser->imm_vector_count; ++i) {
 111         if (!memcmp(&parser->imm_vector[i]->constval.vvec, &v, sizeof(v)))
 112             return parser->imm_vector[i];
 113     }
 114     out = ast_value_new(parser_ctx(parser), "#IMMEDIATE", TYPE_VECTOR);
 115     out->isconst = true;
 116     out->constval.vvec = v;
 117     if (!parser_t_imm_vector_add(parser, out)) {
 118         ast_value_delete(out);
 119         return NULL;
 120     }
 121     return out;
 122 }
 123
 124 ast_value* parser_find_global(parser_t *parser, const char *name)
 125 {
 126     size_t i;
 127     for (i = 0; i < parser->globals_count; ++i) {
 128         if (!strcmp(parser->globals[i]->name, name))
 129             return parser->globals[i];
 130     }
 131     return NULL;
 132 }
 133
 134 ast_value* parser_find_local(parser_t *parser, const char *name, size_t upto)
 135 {
 136     size_t i;
 137     ast_value *fun;
 138     for (i = parser->locals_count; i > upto;) {
 139         --i;
 140         if (!strcmp(parser->locals[i]->name, name))
 141             return parser->locals[i];
 142     }
 143     fun = parser->function->vtype;
 144     for (i = 0; i < fun->expression.params_count; ++i) {
 145         if (!strcmp(fun->expression.params[i]->name, name))
 146             return fun->expression.params[i];
 147     }
 148     return NULL;
 149 }
 150
 151 ast_value* parser_find_var(parser_t *parser, const char *name)
 152 {
 153     ast_value *v;
 154     v         = parser_find_local(parser, name, 0);
 155     if (!v) v = parser_find_global(parser, name);
 156     return v;
 157 }
 158
 159 typedef struct {
 160     MEM_VECTOR_MAKE(ast_value*, p);
 161 } paramlist_t;
 162 MEM_VEC_FUNCTIONS(paramlist_t, ast_value*, p)
 163
 164 static ast_value *parser_parse_type(parser_t *parser, int basetype, bool *isfunc)
 165 {
 166     paramlist_t params;
 167     ast_value *var;
 168     lex_ctx   ctx = parser_ctx(parser);
 169     int vtype = basetype;
 170     int temptype;
 171     size_t i;
 172
 173     MEM_VECTOR_INIT(&params, p);
 174
 175     *isfunc = false;
 176
 177     if (parser->tok == '(') {
 178         *isfunc = true;
 179         while (true) {
 180             ast_value *param;
 181             bool dummy;
 182
 183             if (!parser_next(parser))
 184                 goto on_error;
 185
 186             if (parser->tok == ')')
 187                 break;
 188
 189             temptype = parser_token(parser)->constval.t;
 190             if (!parser_next(parser))
 191                 goto on_error;
 192
 193             param = parser_parse_type(parser, temptype, &dummy);
 194             (void)dummy;
 195
 196             if (!param)
 197                 goto on_error;
 198
 199             if (parser->tok == TOKEN_IDENT) {
 200                 /* named parameter */
 201                 if (!ast_value_set_name(param, parser_tokval(parser)))
 202                     goto on_error;
 203                 if (!parser_next(parser))
 204                     goto on_error;
 205             }
 206
 207             if (!paramlist_t_p_add(&params, param)) {
 208                 parseerror(parser, "Out of memory while parsing typename");
 209                 goto on_error;
 210             }
 211
 212             if (parser->tok == ',')
 213                 continue;
 214             if (parser->tok == ')')
 215                 break;
 216             parseerror(parser, "Unexpected token");
 217             goto on_error;
 218         }
 219         if (!parser_next(parser))
 220             goto on_error;
 221     }
 222
 223     var = ast_value_new(ctx, "<unnamed>", vtype);
 224     if (!var)
 225         goto on_error;
 226     MEM_VECTOR_MOVE(&params, p, &var->expression, params);
 227     return var;
 228 on_error:
 229     for (i = 0; i < params.p_count; ++i)
 230         ast_value_delete(params.p[i]);
 231     MEM_VECTOR_CLEAR(&params, p);
 232     return NULL;
 233 }
 234
 235 typedef struct
 236 {
 237     size_t etype; /* 0 = expression, others are operators */
 238     int             paren;
 239     size_t          off;
 240     ast_expression *out;
 241     ast_value      *value; /* need to know if we can assign */
 242     ast_block      *block; /* for commas and function calls */
 243     lex_ctx ctx;
 244 } sy_elem;
 245 typedef struct
 246 {
 247     MEM_VECTOR_MAKE(sy_elem, out);
 248     MEM_VECTOR_MAKE(sy_elem, ops);
 249 } shunt;
 250 MEM_VEC_FUNCTIONS(shunt, sy_elem, out)
 251 MEM_VEC_FUNCTIONS(shunt, sy_elem, ops)
 252
 253 static sy_elem syexp(lex_ctx ctx, ast_expression *v) {
 254     sy_elem e;
 255     e.etype = 0;
 256     e.out   = v;
 257     e.value = NULL;
 258     e.block = NULL;
 259     e.ctx   = ctx;
 260     e.paren = 0;
 261     return e;
 262 }
 263 static sy_elem syval(lex_ctx ctx, ast_value *v) {
 264     sy_elem e;
 265     e.etype = 0;
 266     e.out   = (ast_expression*)v;
 267     e.value = v;
 268     e.block = NULL;
 269     e.ctx   = ctx;
 270     e.paren = 0;
 271     return e;
 272 }
 273
 274 static sy_elem syblock(lex_ctx ctx, ast_block *v) {
 275     sy_elem e;
 276     e.etype = 0;
 277     e.out   = (ast_expression*)v;
 278     e.value = NULL;
 279     e.block = v;
 280     e.ctx   = ctx;
 281     e.paren = 0;
 282     return e;
 283 }
 284
 285 static sy_elem syop(lex_ctx ctx, const oper_info *op) {
 286     sy_elem e;
 287     e.etype = 1 + (op - operators);
 288     e.out   = NULL;
 289     e.value = NULL;
 290     e.block = NULL;
 291     e.ctx   = ctx;
 292     e.paren = 0;
 293     return e;
 294 }
 295
 296 static sy_elem syparen(lex_ctx ctx, int p, size_t off) {
 297     sy_elem e;
 298     e.etype = 0;
 299     e.off   = off;
 300     e.out   = NULL;
 301     e.value = NULL;
 302     e.block = NULL;
 303     e.ctx   = ctx;
 304     e.paren = p;
 305     return e;
 306 }
 307
 308 static bool parser_sy_pop(parser_t *parser, shunt *sy)
 309 {
 310     const oper_info *op;
 311     lex_ctx ctx;
 312     ast_expression *out = NULL;
 313     ast_expression *exprs[3];
 314     ast_value      *vars[3];
 315     ast_block      *blocks[3];
 316     size_t i;
 317
 318     if (!sy->ops_count) {
 319         parseerror(parser, "internal error: missing operator");
 320         return false;
 321     }
 322
 323     if (sy->ops[sy->ops_count-1].paren) {
 324         parseerror(parser, "unmatched parenthesis");
 325         return false;
 326     }
 327
 328     op = &operators[sy->ops[sy->ops_count-1].etype - 1];
 329     ctx = sy->ops[sy->ops_count-1].ctx;
 330
 331     if (sy->out_count < op->operands) {
 332         parseerror(parser, "internal error: not enough operands: %i", sy->out_count);
 333         return false;
 334     }
 335
 336     sy->ops_count--;
 337
 338     sy->out_count -= op->operands;
 339     for (i = 0; i < op->operands; ++i) {
 340         exprs[i]  = sy->out[sy->out_count+i].out;
 341         vars[i]   = sy->out[sy->out_count+i].value;
 342         blocks[i] = sy->out[sy->out_count+i].block;
 343     }
 344
 345     if (blocks[0] && !blocks[0]->exprs_count && op->id != opid1(',')) {
 346         parseerror(parser, "internal error: operator cannot be applied on empty blocks");
 347         return false;
 348     }
 349
 350     switch (op->id)
 351     {
 352         default:
 353             parseerror(parser, "internal error: unhandled operand");
 354             return false;
 355
 356         case opid1(','):
 357             if (blocks[0]) {
 358                 if (!ast_block_exprs_add(blocks[0], exprs[1]))
 359                     return false;
 360             } else {
 361                 blocks[0] = ast_block_new(ctx);
 362                 if (!ast_block_exprs_add(blocks[0], exprs[0]) ||
 363                     !ast_block_exprs_add(blocks[0], exprs[1]))
 364                 {
 365                     return false;
 366                 }
 367             }
 368             if (!ast_block_set_type(blocks[0], exprs[1]))
 369                 return false;
 370
 371             sy->out[sy->out_count++] = syblock(ctx, blocks[0]);
 372             return true;
 373
 374         case opid1('+'):
 375             if (exprs[0]->expression.vtype != exprs[1]->expression.vtype) {
 376                 parseerror(parser, "Cannot add type %s and %s",
 377                            type_name[exprs[0]->expression.vtype],
 378                            type_name[exprs[1]->expression.vtype]);
 379                 return false;
 380             }
 381             switch (exprs[0]->expression.vtype) {
 382                 case TYPE_FLOAT:
 383                     out = (ast_expression*)ast_binary_new(ctx, INSTR_ADD_F, exprs[0], exprs[1]);
 384                     break;
 385                 case TYPE_VECTOR:
 386                     out = (ast_expression*)ast_binary_new(ctx, INSTR_ADD_V, exprs[0], exprs[1]);
 387                     break;
 388                 default:
 389                     parseerror(parser, "Cannot add type %s and %s",
 390                                type_name[exprs[0]->expression.vtype],
 391                                type_name[exprs[1]->expression.vtype]);
 392                     return false;
 393             };
 394             break;
 395         case opid1('-'):
 396             if (exprs[0]->expression.vtype != exprs[1]->expression.vtype) {
 397                 parseerror(parser, "Cannot subtract type %s from %s",
 398                            type_name[exprs[1]->expression.vtype],
 399                            type_name[exprs[0]->expression.vtype]);
 400                 return false;
 401             }
 402             switch (exprs[0]->expression.vtype) {
 403                 case TYPE_FLOAT:
 404                     out = (ast_expression*)ast_binary_new(ctx, INSTR_SUB_F, exprs[0], exprs[1]);
 405                     break;
 406                 case TYPE_VECTOR:
 407                     out = (ast_expression*)ast_binary_new(ctx, INSTR_SUB_V, exprs[0], exprs[1]);
 408                     break;
 409                 default:
 410                     parseerror(parser, "Cannot add type %s from %s",
 411                                type_name[exprs[1]->expression.vtype],
 412                                type_name[exprs[0]->expression.vtype]);
 413                     return false;
 414             };
 415             break;
 416         case opid1('*'):
 417             if (exprs[0]->expression.vtype != exprs[1]->expression.vtype &&
 418                 exprs[0]->expression.vtype != TYPE_VECTOR &&
 419                 exprs[0]->expression.vtype != TYPE_FLOAT &&
 420                 exprs[1]->expression.vtype != TYPE_VECTOR &&
 421                 exprs[1]->expression.vtype != TYPE_FLOAT)
 422             {
 423                 parseerror(parser, "Cannot multiply type %s from %s",
 424                            type_name[exprs[1]->expression.vtype],
 425                            type_name[exprs[0]->expression.vtype]);
 426                 return false;
 427             }
 428             switch (exprs[0]->expression.vtype) {
 429                 case TYPE_FLOAT:
 430                     if (exprs[1]->expression.vtype == TYPE_VECTOR)
 431                         out = (ast_expression*)ast_binary_new(ctx, INSTR_MUL_FV, exprs[0], exprs[1]);
 432                     else
 433                         out = (ast_expression*)ast_binary_new(ctx, INSTR_MUL_F, exprs[0], exprs[1]);
 434                     break;
 435                 case TYPE_VECTOR:
 436                     if (exprs[1]->expression.vtype == TYPE_FLOAT)
 437                         out = (ast_expression*)ast_binary_new(ctx, INSTR_MUL_VF, exprs[0], exprs[1]);
 438                     else
 439                         out = (ast_expression*)ast_binary_new(ctx, INSTR_MUL_V, exprs[0], exprs[1]);
 440                     break;
 441                 default:
 442                     parseerror(parser, "Cannot add type %s from %s",
 443                                type_name[exprs[1]->expression.vtype],
 444                                type_name[exprs[0]->expression.vtype]);
 445                     return false;
 446             };
 447             break;
 448         case opid1('/'):
 449             if (exprs[0]->expression.vtype != exprs[1]->expression.vtype ||
 450                 exprs[0]->expression.vtype != TYPE_FLOAT)
 451             {
 452                 parseerror(parser, "Cannot divide types %s and %s",
 453                            type_name[exprs[0]->expression.vtype],
 454                            type_name[exprs[1]->expression.vtype]);
 455                 return false;
 456             }
 457             out = (ast_expression*)ast_binary_new(ctx, INSTR_DIV_F, exprs[0], exprs[1]);
 458             break;
 459
 460
 461         case opid1('='):
 462             if (!vars[0]) {
 463                 parseerror(parser, "Cannot assign to non-variable");
 464                 return false;
 465             }
 466             out = (ast_expression*)ast_store_new(ctx,
 467                                                  type_store_instr[vars[0]->expression.vtype],
 468                                                  vars[0], exprs[1]);
 469             break;
 470     }
 471
 472     if (!out) {
 473         parseerror(parser, "failed to apply operand %s", op->op);
 474         return false;
 475     }
 476
 477     sy->out[sy->out_count++] = syexp(ctx, out);
 478     return true;
 479 }
 480
 481 static bool parser_close_call(parser_t *parser, shunt *sy)
 482 {
 483     /* was a function call */
 484     ast_expression *fun;
 485     ast_call       *call;
 486
 487     size_t          fid;
 488     size_t          paramcount;
 489
 490     sy->ops_count--;
 491     fid = sy->ops[sy->ops_count].off;
 492
 493     /* out[fid] is the function
 494      * everything above is parameters...
 495      * 0 params = nothing
 496      * 1 params = ast_expression
 497      * more = ast_block
 498      */
 499
 500     if (sy->out_count < 1 || sy->out_count <= fid) {
 501         parseerror(parser, "internal error: function call needs function and parameter list...");
 502         return false;
 503     }
 504
 505     fun = sy->out[fid].out;
 506
 507     call = ast_call_new(sy->ops[sy->ops_count].ctx, fun);
 508     if (!call) {
 509         parseerror(parser, "out of memory");
 510         return false;
 511     }
 512
 513     if (fid+1 == sy->out_count) {
 514         /* no arguments */
 515         paramcount = 0;
 516     } else if (fid+2 == sy->out_count) {
 517         ast_block *params;
 518         sy->out_count--;
 519         params = sy->out[sy->out_count].block;
 520         if (!params) {
 521             /* 1 param */
 522             paramcount = 1;
 523             if (!ast_call_params_add(call, sy->out[sy->out_count].out)) {
 524                 ast_delete(sy->out[sy->out_count].out);
 525                 parseerror(parser, "out of memory");
 526                 return false;
 527             }
 528         } else {
 529             paramcount = params->exprs_count;
 530             MEM_VECTOR_MOVE(params, exprs, call, params);
 531             ast_delete(params);
 532         }
 533     } else {
 534         parseerror(parser, "invalid function call");
 535         return false;
 536     }
 537
 538     /* overwrite fid, the function, with a call */
 539     sy->out[fid] = syexp(call->expression.node.context, (ast_expression*)call);
 540
 541     if (fun->expression.vtype != TYPE_FUNCTION) {
 542         parseerror(parser, "not a function");
 543         return false;
 544     }
 545
 546     if (!fun->expression.next) {
 547         parseerror(parser, "could not determine function return type");
 548         return false;
 549     } else {
 550         if (fun->expression.params_count != paramcount) {
 551             parseerror(parser, "expected %i parameters, got %i", (int)fun->expression.params_count, paramcount);
 552             return false;
 553         }
 554     }
 555
 556     return true;
 557 }
 558
 559 static bool parser_close_paren(parser_t *parser, shunt *sy, bool functions_only)
 560 {
 561     if (!sy->ops_count) {
 562         parseerror(parser, "unmatched closing paren");
 563         return false;
 564     }
 565     if (sy->ops[sy->ops_count-1].paren == 1) {
 566         parseerror(parser, "empty parenthesis expression");
 567         return false;
 568     }
 569     while (sy->ops_count) {
 570         if (sy->ops[sy->ops_count-1].paren == 'f') {
 571             if (!parser_close_call(parser, sy))
 572                 return false;
 573             break;
 574         }
 575         if (sy->ops[sy->ops_count-1].paren == 1) {
 576             sy->ops_count--;
 577             return !functions_only;
 578         }
 579         if (!parser_sy_pop(parser, sy))
 580             return false;
 581     }
 582     return true;
 583 }
 584
 585 static ast_expression* parser_expression(parser_t *parser)
 586 {
 587     ast_expression *expr = NULL;
 588     shunt sy;
 589     bool wantop = false;
 590
 591     MEM_VECTOR_INIT(&sy, out);
 592     MEM_VECTOR_INIT(&sy, ops);
 593
 594     while (true)
 595     {
 596         if (!wantop)
 597         {
 598             bool nextwant = true;
 599             if (parser->tok == TOKEN_IDENT)
 600             {
 601                 /* variable */
 602                 ast_value *var = parser_find_var(parser, parser_tokval(parser));
 603                 if (!var) {
 604                     parseerror(parser, "unexpected ident: %s", parser_tokval(parser));
 605                     goto onerr;
 606                 }
 607                 if (!shunt_out_add(&sy, syval(parser_ctx(parser), var))) {
 608                     parseerror(parser, "out of memory");
 609                     goto onerr;
 610                 }
 611             }
 612             else if (parser->tok == TOKEN_FLOATCONST) {
 613                 ast_value *val = parser_const_float(parser, (parser_token(parser)->constval.f));
 614                 if (!val)
 615                     return false;
 616                 if (!shunt_out_add(&sy, syexp(parser_ctx(parser), (ast_expression*)val))) {
 617                     parseerror(parser, "out of memory");
 618                     goto onerr;
 619                 }
 620             }
 621             else if (parser->tok == TOKEN_INTCONST) {
 622                 ast_value *val = parser_const_float(parser, (double)(parser_token(parser)->constval.i));
 623                 if (!val)
 624                     return false;
 625                 if (!shunt_out_add(&sy, syexp(parser_ctx(parser), (ast_expression*)val))) {
 626                     parseerror(parser, "out of memory");
 627                     goto onerr;
 628                 }
 629             }
 630             else if (parser->tok == TOKEN_STRINGCONST) {
 631                 ast_value *val = parser_const_string(parser, parser_tokval(parser));
 632                 if (!val)
 633                     return false;
 634                 if (!shunt_out_add(&sy, syexp(parser_ctx(parser), (ast_expression*)val))) {
 635                     parseerror(parser, "out of memory");
 636                     goto onerr;
 637                 }
 638             }
 639             else if (parser->tok == TOKEN_VECTORCONST) {
 640                 ast_value *val = parser_const_vector(parser, parser_token(parser)->constval.v);
 641                 if (!val)
 642                     return false;
 643                 if (!shunt_out_add(&sy, syexp(parser_ctx(parser), (ast_expression*)val))) {
 644                     parseerror(parser, "out of memory");
 645                     goto onerr;
 646                 }
 647             }
 648             else if (parser->tok == '(') {
 649                 nextwant = false; /* not expecting an operator next */
 650                 if (!shunt_ops_add(&sy, syparen(parser_ctx(parser), 1, 0))) {
 651                     parseerror(parser, "out of memory");
 652                     goto onerr;
 653                 }
 654             }
 655             else if (parser->tok == ')') {
 656                 /* allowed for function calls */
 657                 if (!parser_close_paren(parser, &sy, true))
 658                     goto onerr;
 659             }
 660             else {
 661                 /* TODO: prefix operators */
 662                 parseerror(parser, "expected statement");
 663                 goto onerr;
 664             }
 665             wantop = nextwant;
 666             parser->lex->flags.noops = !wantop;
 667         } else {
 668             if (parser->tok == '(') {
 669                 /* we expected an operator, this is the function-call operator */
 670                 if (!shunt_ops_add(&sy, syparen(parser_ctx(parser), 'f', sy.out_count-1))) {
 671                     parseerror(parser, "out of memory");
 672                     goto onerr;
 673                 }
 674             }
 675             else if (parser->tok == ')') {
 676                 /* we do expect an operator next */
 677                 /* closing an opening paren */
 678                 if (!parser_close_paren(parser, &sy, false))
 679                     goto onerr;
 680             }
 681             else if (parser->tok != TOKEN_OPERATOR) {
 682                 parseerror(parser, "expected operator or end of statement");
 683                 goto onerr;
 684             }
 685             else {
 686                 /* classify the operator */
 687                 /* TODO: suffix operators */
 688                 const oper_info *op;
 689                 const oper_info *olast = NULL;
 690                 size_t o;
 691                 for (o = 0; o < operator_count; ++o) {
 692                     if (!(operators[o].flags & OP_PREFIX) &&
 693                         !(operators[o].flags & OP_SUFFIX) && /* remove this */
 694                         !strcmp(parser_tokval(parser), operators[o].op))
 695                     {
 696                         break;
 697                     }
 698                 }
 699                 if (o == operator_count) {
 700                     /* no operator found... must be the end of the statement */
 701                     break;
 702                 }
 703                 /* found an operator */
 704                 op = &operators[o];
 705
 706                 if (sy.ops_count && !sy.ops[sy.ops_count-1].paren)
 707                     olast = &operators[sy.ops[sy.ops_count-1].etype-1];
 708
 709                 while (olast && (
 710                         (op->prec < olast->prec) ||
 711                         (op->assoc == ASSOC_LEFT && op->prec <= olast->prec) ) )
 712                 {
 713                     if (!parser_sy_pop(parser, &sy))
 714                         goto onerr;
 715                     if (sy.ops_count && !sy.ops[sy.ops_count-1].paren)
 716                         olast = &operators[sy.ops[sy.ops_count-1].etype-1];
 717                 }
 718
 719                 if (!shunt_ops_add(&sy, syop(parser_ctx(parser), op)))
 720                     goto onerr;
 721             }
 722             wantop = false;
 723             parser->lex->flags.noops = true;
 724         }
 725         if (!parser_next(parser)) {
 726             goto onerr;
 727         }
 728         if (parser->tok == ';') {
 729             break;
 730         }
 731     }
 732     if (!parser_next(parser)) {
 733         parseerror(parser, "Unexpected end of file");
 734         goto onerr;
 735     }
 736
 737     while (sy.ops_count) {
 738         if (!parser_sy_pop(parser, &sy))
 739             goto onerr;
 740     }
 741
 742     parser->lex->flags.noops = true;
 743     if (!sy.out_count) {
 744         parseerror(parser, "empty expression");
 745         expr = NULL;
 746     } else
 747         expr = sy.out[0].out;
 748     MEM_VECTOR_CLEAR(&sy, out);
 749     MEM_VECTOR_CLEAR(&sy, ops);
 750     return expr;
 751
 752 onerr:
 753     parser->lex->flags.noops = true;
 754     MEM_VECTOR_CLEAR(&sy, out);
 755     MEM_VECTOR_CLEAR(&sy, ops);
 756     return NULL;
 757 }
 758
 759 static bool parser_variable(parser_t *parser, ast_block *localblock);
 760 static bool parser_body_do(parser_t *parser, ast_block *block)
 761 {
 762     if (parser->tok == TOKEN_TYPENAME)
 763     {
 764         /* local variable */
 765         if (!parser_variable(parser, block))
 766             return false;
 767         return true;
 768     }
 769     else if (parser->tok == TOKEN_KEYWORD)
 770     {
 771         if (!strcmp(parser_tokval(parser), "return"))
 772         {
 773             ast_expression *exp = NULL;
 774             ast_return     *ret = NULL;
 775             ast_value      *expected = parser->function->vtype;
 776
 777             if (!parser_next(parser)) {
 778                 parseerror(parser, "expected return expression");
 779                 return false;
 780             }
 781
 782             if (parser->tok != ';') {
 783                 exp = parser_expression(parser);
 784                 if (!exp)
 785                     return false;
 786
 787                 if (exp->expression.vtype != expected->expression.next->expression.vtype) {
 788                     parseerror(parser, "return with invalid expression");
 789                 }
 790
 791                 ret = ast_return_new(exp->expression.node.context, exp);
 792                 if (!ret) {
 793                     ast_delete(exp);
 794                     return false;
 795                 }
 796
 797                 if (!ast_block_exprs_add(block, (ast_expression*)ret)) {
 798                     ast_delete(ret);
 799                     return false;
 800                 }
 801             } else if (!parser_next(parser)) {
 802                 parseerror(parser, "expected semicolon");
 803                 if (expected->expression.next->expression.vtype != TYPE_VOID) {
 804                     parseerror(parser, "return without value");
 805                 }
 806             }
 807             return true;
 808         }
 809         parseerror(parser, "Unexpected keyword");
 810         return false;
 811     }
 812     else if (parser->tok == '{')
 813     {
 814         /* a block */
 815         parseerror(parser, "TODO: inner blocks: %s", parser_tokval(parser));
 816         return false;
 817     }
 818     else
 819     {
 820         ast_expression *exp = parser_expression(parser);
 821         if (!exp)
 822             return false;
 823         if (!ast_block_exprs_add(block, exp)) {
 824             ast_delete(exp);
 825             return false;
 826         }
 827         return true;
 828     }
 829 }
 830
 831 static ast_block* parser_parse_block(parser_t *parser)
 832 {
 833     size_t oldblocklocal;
 834     ast_block *block = NULL;
 835
 836     oldblocklocal = parser->blocklocal;
 837     parser->blocklocal = parser->locals_count;
 838
 839     if (!parser_next(parser)) { /* skip the '{' */
 840         parseerror(parser, "expected function body");
 841         goto cleanup;
 842     }
 843
 844     block = ast_block_new(parser_ctx(parser));
 845
 846     while (parser->tok != TOKEN_EOF && parser->tok < TOKEN_ERROR)
 847     {
 848         if (parser->tok == '}')
 849             break;
 850
 851         if (!parser_body_do(parser, block)) {
 852             ast_block_delete(block);
 853             block = NULL;
 854             goto cleanup;
 855         }
 856     }
 857
 858     if (parser->tok != '}') {
 859         ast_block_delete(block);
 860         block = NULL;
 861     } else {
 862         (void)parser_next(parser);
 863     }
 864
 865 cleanup:
 866     parser->blocklocal = oldblocklocal;
 867     return block;
 868 }
 869
 870 static bool parser_variable(parser_t *parser, ast_block *localblock)
 871 {
 872     bool          isfunc = false;
 873     ast_function *func = NULL;
 874     lex_ctx       ctx;
 875     ast_value    *var;
 876
 877     int basetype = parser_token(parser)->constval.t;
 878
 879     while (true)
 880     {
 881         if (!parser_next(parser)) { /* skip basetype or comma */
 882             parseerror(parser, "expected variable declaration");
 883             return false;
 884         }
 885
 886         isfunc = false;
 887         func = NULL;
 888         ctx = parser_ctx(parser);
 889         var = parser_parse_type(parser, basetype, &isfunc);
 890
 891         if (!var)
 892             return false;
 893
 894         if (parser->tok != TOKEN_IDENT) {
 895             parseerror(parser, "expected variable name\n");
 896             return false;
 897         }
 898
 899         if (!localblock && parser_find_global(parser, parser_tokval(parser))) {
 900             ast_value_delete(var);
 901             parseerror(parser, "global already exists: %s\n", parser_tokval(parser));
 902             return false;
 903         }
 904
 905         if (localblock && parser_find_local(parser, parser_tokval(parser), parser->blocklocal)) {
 906             ast_value_delete(var);
 907             parseerror(parser, "local variable already exists: %s\n", parser_tokval(parser));
 908             return false;
 909         }
 910
 911         if (!ast_value_set_name(var, parser_tokval(parser))) {
 912             parseerror(parser, "failed to set variable name\n");
 913             ast_value_delete(var);
 914             return false;
 915         }
 916
 917         if (isfunc) {
 918             /* a function was defined */
 919             ast_value *fval;
 920
 921             /* turn var into a value of TYPE_FUNCTION, with the old var
 922              * as return type
 923              */
 924             fval = ast_value_new(ctx, var->name, TYPE_FUNCTION);
 925             func = ast_function_new(ctx, var->name, fval);
 926             if (!fval || !func) {
 927                 ast_value_delete(var);
 928                 if (fval) ast_value_delete(fval);
 929                 if (func) ast_function_delete(func);
 930                 return false;
 931             }
 932
 933             fval->expression.next = (ast_expression*)var;
 934             MEM_VECTOR_MOVE(&var->expression, params, &fval->expression, params);
 935
 936             if (!parser_t_functions_add(parser, func)) {
 937                 ast_value_delete(var);
 938                 if (fval) ast_value_delete(fval);
 939                 if (func) ast_function_delete(func);
 940                 return false;
 941             }
 942
 943             var = fval;
 944         }
 945
 946         if ( (!localblock && !parser_t_globals_add(parser, var)) ||
 947              ( localblock && !parser_t_locals_add(parser, var)) )
 948         {
 949             ast_value_delete(var);
 950             return false;
 951         }
 952         if (localblock && !ast_block_locals_add(localblock, var))
 953         {
 954             parser->locals_count--;
 955             ast_value_delete(var);
 956             return false;
 957         }
 958
 959         if (!parser_next(parser)) {
 960             ast_value_delete(var);
 961             return false;
 962         }
 963
 964         if (parser->tok == ';') {
 965             if (!parser_next(parser))
 966                 return parser->tok == TOKEN_EOF;
 967             return true;
 968         }
 969
 970         if (parser->tok == ',') {
 971             /* another var */
 972             continue;
 973         }
 974
 975         if (parser->tok != '=') {
 976             parseerror(parser, "expected '=' or ';'");
 977             return false;
 978         }
 979
 980         if (!parser_next(parser))
 981             return false;
 982
 983         if (parser->tok == '#') {
 984             if (localblock) {
 985                 parseerror(parser, "cannot declare builtins within functions");
 986                 return false;
 987             }
 988             if (!isfunc || !func) {
 989                 parseerror(parser, "unexpected builtin number, '%s' is not a function", var->name);
 990                 return false;
 991             }
 992             if (!parser_next(parser)) {
 993                 parseerror(parser, "expected builtin number");
 994                 return false;
 995             }
 996             if (parser->tok != TOKEN_INTCONST) {
 997                 parseerror(parser, "builtin number must be an integer constant");
 998                 return false;
 999             }
1000             if (parser_token(parser)->constval.i <= 0) {
1001                 parseerror(parser, "builtin number must be positive integer greater than zero");
1002                 return false;
1003             }
1004
1005             func->builtin = -parser_token(parser)->constval.i;
1006         } else if (parser->tok == '{') {
1007             /* function body */
1008             ast_block *block;
1009             ast_function *old = parser->function;
1010
1011             if (localblock) {
1012                 parseerror(parser, "cannot declare functions within functions");
1013                 return false;
1014             }
1015
1016             parser->function = func;
1017             block = parser_parse_block(parser);
1018             parser->function = old;
1019
1020             if (!block)
1021                 return false;
1022
1023             if (!ast_function_blocks_add(func, block)) {
1024                 ast_block_delete(block);
1025                 return false;
1026             }
1027             return true;
1028         } else {
1029             parseerror(parser, "TODO, const assignment");
1030         }
1031
1032         if (!parser_next(parser))
1033             return false;
1034
1035         if (parser->tok == ',') {
1036             /* another */
1037             continue;
1038         }
1039
1040         if (parser->tok != ';') {
1041             parseerror(parser, "expected semicolon");
1042             return false;
1043         }
1044
1045         (void)parser_next(parser);
1046
1047         return true;
1048     }
1049 }
1050
1051 static bool parser_do(parser_t *parser)
1052 {
1053     if (parser->tok == TOKEN_TYPENAME)
1054     {
1055         return parser_variable(parser, NULL);
1056     }
1057     else if (parser->tok == TOKEN_KEYWORD)
1058     {
1059         /* handle 'var' and 'const' */
1060         return false;
1061     }
1062     else if (parser->tok == '.')
1063     {
1064         /* entity-member declaration */
1065         return false;
1066     }
1067     else
1068     {
1069         parseerror(parser, "unexpected token: %s", parser->lex->tok->value);
1070         return false;
1071     }
1072     return true;
1073 }
1074
1075 bool parser_compile(const char *filename, const char *datfile)
1076 {
1077     size_t i;
1078     parser_t *parser;
1079     ir_builder *ir;
1080
1081     parser = (parser_t*)mem_a(sizeof(parser_t));
1082     if (!parser)
1083         return false;
1084
1085     memset(parser, 0, sizeof(parser));
1086
1087     MEM_VECTOR_INIT(parser, globals);
1088     MEM_VECTOR_INIT(parser, locals);
1089     parser->lex = lex_open(filename);
1090
1091     if (!parser->lex) {
1092         printf("failed to open file \"%s\"\n", filename);
1093         return false;
1094     }
1095
1096     /* initial lexer/parser state */
1097     parser->lex->flags.noops = true;
1098
1099     if (parser_next(parser))
1100     {
1101         while (parser->tok != TOKEN_EOF && parser->tok < TOKEN_ERROR)
1102         {
1103             if (!parser_do(parser)) {
1104                 if (parser->tok == TOKEN_EOF)
1105                     parseerror(parser, "unexpected eof");
1106                 else
1107                     parseerror(parser, "parse error\n");
1108                 lex_close(parser->lex);
1109                 mem_d(parser);
1110                 return false;
1111             }
1112         }
1113     }
1114
1115     lex_close(parser->lex);
1116
1117     if (!parser->errors)
1118     {
1119         ir = ir_builder_new("gmqcc_out");
1120         if (!ir) {
1121             printf("failed to allocate builder\n");
1122             goto cleanup;
1123         }
1124
1125         for (i = 0; i < parser->imm_float_count; ++i) {
1126             if (!ast_global_codegen(parser->imm_float[i], ir)) {
1127                 printf("failed to generate global %s\n", parser->imm_float[i]->name);
1128             }
1129         }
1130         for (i = 0; i < parser->imm_string_count; ++i) {
1131             if (!ast_global_codegen(parser->imm_string[i], ir)) {
1132                 printf("failed to generate global %s\n", parser->imm_string[i]->name);
1133             }
1134         }
1135         for (i = 0; i < parser->imm_vector_count; ++i) {
1136             if (!ast_global_codegen(parser->imm_vector[i], ir)) {
1137                 printf("failed to generate global %s\n", parser->imm_vector[i]->name);
1138             }
1139         }
1140         for (i = 0; i < parser->globals_count; ++i) {
1141             if (!ast_global_codegen(parser->globals[i], ir)) {
1142                 printf("failed to generate global %s\n", parser->globals[i]->name);
1143             }
1144         }
1145         for (i = 0; i < parser->functions_count; ++i) {
1146             if (!ast_function_codegen(parser->functions[i], ir)) {
1147                 printf("failed to generate function %s\n", parser->functions[i]->name);
1148             }
1149             if (!ir_function_finalize(parser->functions[i]->ir_func)) {
1150                 printf("failed to finalize function %s\n", parser->functions[i]->name);
1151             }
1152         }
1153
1154         ir_builder_dump(ir, printf);
1155
1156         if (!ir_builder_generate(ir, datfile))
1157             printf("*** failed to generate output file\n");
1158
1159         ir_builder_delete(ir);
1160     } else {
1161         printf("*** there were compile errors\n");
1162     }
1163
1164 cleanup:
1165     for (i = 0; i < parser->functions_count; ++i) {
1166         ast_delete(parser->functions[i]);
1167     }
1168     for (i = 0; i < parser->imm_vector_count; ++i) {
1169         ast_delete(parser->imm_vector[i]);
1170     }
1171     for (i = 0; i < parser->imm_string_count; ++i) {
1172         ast_delete(parser->imm_string[i]);
1173     }
1174     for (i = 0; i < parser->imm_float_count; ++i) {
1175         ast_delete(parser->imm_float[i]);
1176     }
1177     for (i = 0; i < parser->globals_count; ++i) {
1178         ast_delete(parser->globals[i]);
1179     }
1180     MEM_VECTOR_CLEAR(parser, globals);
1181
1182     mem_d(parser);
1183     return true;
1184 }