parser.c

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