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     MEM_VECTOR_INIT(&sy, out);
 576     MEM_VECTOR_INIT(&sy, ops);
 577
 578     while (true)
 579     {
 580         if (!wantop)
 581         {
 582             bool nextwant = true;
 583             if (parser->tok == TOKEN_IDENT)
 584             {
 585                 /* variable */
 586                 ast_expression *var = parser_find_var(parser, parser_tokval(parser));
 587                 if (!var) {
 588                     parseerror(parser, "unexpected ident: %s", parser_tokval(parser));
 589                     goto onerr;
 590                 }
 591                 if (!shunt_out_add(&sy, syexp(parser_ctx(parser), var))) {
 592                     parseerror(parser, "out of memory");
 593                     goto onerr;
 594                 }
 595             }
 596             else if (parser->tok == TOKEN_FLOATCONST) {
 597                 ast_value *val = parser_const_float(parser, (parser_token(parser)->constval.f));
 598                 if (!val)
 599                     return false;
 600                 if (!shunt_out_add(&sy, syexp(parser_ctx(parser), (ast_expression*)val))) {
 601                     parseerror(parser, "out of memory");
 602                     goto onerr;
 603                 }
 604             }
 605             else if (parser->tok == TOKEN_INTCONST) {
 606                 ast_value *val = parser_const_float(parser, (double)(parser_token(parser)->constval.i));
 607                 if (!val)
 608                     return false;
 609                 if (!shunt_out_add(&sy, syexp(parser_ctx(parser), (ast_expression*)val))) {
 610                     parseerror(parser, "out of memory");
 611                     goto onerr;
 612                 }
 613             }
 614             else if (parser->tok == TOKEN_STRINGCONST) {
 615                 ast_value *val = parser_const_string(parser, parser_tokval(parser));
 616                 if (!val)
 617                     return false;
 618                 if (!shunt_out_add(&sy, syexp(parser_ctx(parser), (ast_expression*)val))) {
 619                     parseerror(parser, "out of memory");
 620                     goto onerr;
 621                 }
 622             }
 623             else if (parser->tok == TOKEN_VECTORCONST) {
 624                 ast_value *val = parser_const_vector(parser, parser_token(parser)->constval.v);
 625                 if (!val)
 626                     return false;
 627                 if (!shunt_out_add(&sy, syexp(parser_ctx(parser), (ast_expression*)val))) {
 628                     parseerror(parser, "out of memory");
 629                     goto onerr;
 630                 }
 631             }
 632             else if (parser->tok == '(') {
 633                 nextwant = false; /* not expecting an operator next */
 634                 if (!shunt_ops_add(&sy, syparen(parser_ctx(parser), 1, 0))) {
 635                     parseerror(parser, "out of memory");
 636                     goto onerr;
 637                 }
 638             }
 639             else if (parser->tok == ')') {
 640                 /* allowed for function calls */
 641                 if (!parser_close_paren(parser, &sy, true))
 642                     goto onerr;
 643             }
 644             else {
 645                 /* TODO: prefix operators */
 646                 parseerror(parser, "expected statement");
 647                 goto onerr;
 648             }
 649             wantop = nextwant;
 650             parser->lex->flags.noops = !wantop;
 651         } else {
 652             if (parser->tok == '(') {
 653                 /* we expected an operator, this is the function-call operator */
 654                 if (!shunt_ops_add(&sy, syparen(parser_ctx(parser), 'f', sy.out_count-1))) {
 655                     parseerror(parser, "out of memory");
 656                     goto onerr;
 657                 }
 658             }
 659             else if (parser->tok == ')') {
 660                 /* we do expect an operator next */
 661                 /* closing an opening paren */
 662                 if (!parser_close_paren(parser, &sy, false))
 663                     goto onerr;
 664             }
 665             else if (parser->tok != TOKEN_OPERATOR) {
 666                 parseerror(parser, "expected operator or end of statement");
 667                 goto onerr;
 668             }
 669             else {
 670                 /* classify the operator */
 671                 /* TODO: suffix operators */
 672                 const oper_info *op;
 673                 const oper_info *olast = NULL;
 674                 size_t o;
 675                 for (o = 0; o < operator_count; ++o) {
 676                     if (!(operators[o].flags & OP_PREFIX) &&
 677                         !(operators[o].flags & OP_SUFFIX) && /* remove this */
 678                         !strcmp(parser_tokval(parser), operators[o].op))
 679                     {
 680                         break;
 681                     }
 682                 }
 683                 if (o == operator_count) {
 684                     /* no operator found... must be the end of the statement */
 685                     break;
 686                 }
 687                 /* found an operator */
 688                 op = &operators[o];
 689
 690                 if (sy.ops_count && !sy.ops[sy.ops_count-1].paren)
 691                     olast = &operators[sy.ops[sy.ops_count-1].etype-1];
 692
 693                 while (olast && (
 694                         (op->prec < olast->prec) ||
 695                         (op->assoc == ASSOC_LEFT && op->prec <= olast->prec) ) )
 696                 {
 697                     if (!parser_sy_pop(parser, &sy))
 698                         goto onerr;
 699                     if (sy.ops_count && !sy.ops[sy.ops_count-1].paren)
 700                         olast = &operators[sy.ops[sy.ops_count-1].etype-1];
 701                 }
 702
 703                 if (!shunt_ops_add(&sy, syop(parser_ctx(parser), op)))
 704                     goto onerr;
 705             }
 706             wantop = false;
 707             parser->lex->flags.noops = true;
 708         }
 709         if (!parser_next(parser)) {
 710             goto onerr;
 711         }
 712         if (parser->tok == ';') {
 713             break;
 714         }
 715     }
 716     if (!parser_next(parser)) {
 717         parseerror(parser, "Unexpected end of file");
 718         goto onerr;
 719     }
 720
 721     while (sy.ops_count) {
 722         if (!parser_sy_pop(parser, &sy))
 723             goto onerr;
 724     }
 725
 726     parser->lex->flags.noops = true;
 727     if (!sy.out_count) {
 728         parseerror(parser, "empty expression");
 729         expr = NULL;
 730     } else
 731         expr = sy.out[0].out;
 732     MEM_VECTOR_CLEAR(&sy, out);
 733     MEM_VECTOR_CLEAR(&sy, ops);
 734     return expr;
 735
 736 onerr:
 737     parser->lex->flags.noops = true;
 738     MEM_VECTOR_CLEAR(&sy, out);
 739     MEM_VECTOR_CLEAR(&sy, ops);
 740     return NULL;
 741 }
 742
 743 static bool parser_variable(parser_t *parser, ast_block *localblock);
 744 static bool parser_parse_statement(parser_t *parser, ast_block *block, ast_expression **out)
 745 {
 746     if (parser->tok == TOKEN_TYPENAME)
 747     {
 748         /* local variable */
 749         if (!block) {
 750             parseerror(parser, "cannot declare a variable from here");
 751             return false;
 752         }
 753         if (!parser_variable(parser, block))
 754             return false;
 755         *out = NULL;
 756         return true;
 757     }
 758     else if (parser->tok == TOKEN_KEYWORD)
 759     {
 760         if (!strcmp(parser_tokval(parser), "return"))
 761         {
 762             ast_expression *exp = NULL;
 763             ast_return     *ret = NULL;
 764             ast_value      *expected = parser->function->vtype;
 765
 766             if (!parser_next(parser)) {
 767                 parseerror(parser, "expected return expression");
 768                 return false;
 769             }
 770
 771             if (parser->tok != ';') {
 772                 exp = parser_expression(parser);
 773                 if (!exp)
 774                     return false;
 775
 776                 if (exp->expression.vtype != expected->expression.next->expression.vtype) {
 777                     parseerror(parser, "return with invalid expression");
 778                 }
 779
 780                 ret = ast_return_new(exp->expression.node.context, exp);
 781                 if (!ret) {
 782                     ast_delete(exp);
 783                     return false;
 784                 }
 785
 786                 *out = (ast_expression*)ret;
 787             } else if (!parser_next(parser)) {
 788                 parseerror(parser, "expected semicolon");
 789                 if (expected->expression.next->expression.vtype != TYPE_VOID) {
 790                     parseerror(parser, "return without value");
 791                 }
 792             }
 793             return true;
 794         }
 795         parseerror(parser, "Unexpected keyword");
 796         return false;
 797     }
 798     else if (parser->tok == '{')
 799     {
 800         /* a block */
 801         parseerror(parser, "TODO: inner blocks: %s", parser_tokval(parser));
 802         return false;
 803     }
 804     else
 805     {
 806         ast_expression *exp = parser_expression(parser);
 807         if (!exp)
 808             return false;
 809         *out = exp;
 810         return true;
 811     }
 812 }
 813
 814 static ast_block* parser_parse_block(parser_t *parser)
 815 {
 816     size_t oldblocklocal;
 817     ast_block *block = NULL;
 818
 819     oldblocklocal = parser->blocklocal;
 820     parser->blocklocal = parser->locals_count;
 821
 822     if (!parser_next(parser)) { /* skip the '{' */
 823         parseerror(parser, "expected function body");
 824         goto cleanup;
 825     }
 826
 827     block = ast_block_new(parser_ctx(parser));
 828
 829     while (parser->tok != TOKEN_EOF && parser->tok < TOKEN_ERROR)
 830     {
 831         ast_expression *expr;
 832         if (parser->tok == '}')
 833             break;
 834
 835         if (!parser_parse_statement(parser, block, &expr)) {
 836             ast_block_delete(block);
 837             block = NULL;
 838             goto cleanup;
 839         }
 840         if (!expr)
 841             continue;
 842         if (!ast_block_exprs_add(block, expr)) {
 843             ast_delete(expr);
 844             ast_block_delete(block);
 845             block = NULL;
 846             goto cleanup;
 847         }
 848     }
 849
 850     if (parser->tok != '}') {
 851         ast_block_delete(block);
 852         block = NULL;
 853     } else {
 854         (void)parser_next(parser);
 855     }
 856
 857 cleanup:
 858     parser->blocklocal = oldblocklocal;
 859     return block;
 860 }
 861
 862 static ast_expression* parser_parse_statement_or_block(parser_t *parser)
 863 {
 864     ast_expression *expr;
 865     if (parser->tok == '{')
 866         return (ast_expression*)parser_parse_block(parser);
 867     if (!parser_parse_statement(parser, NULL, &expr))
 868         return NULL;
 869     return expr;
 870 }
 871
 872 static void parser_pop_local(parser_t *parser)
 873 {
 874     parser->locals_count--;
 875     mem_d(parser->locals[parser->locals_count].name);
 876 }
 877
 878 static bool parser_variable(parser_t *parser, ast_block *localblock)
 879 {
 880     bool          isfunc = false;
 881     ast_function *func = NULL;
 882     lex_ctx       ctx;
 883     ast_value    *var;
 884     varentry_t    varent;
 885
 886     int basetype = parser_token(parser)->constval.t;
 887
 888     while (true)
 889     {
 890         if (!parser_next(parser)) { /* skip basetype or comma */
 891             parseerror(parser, "expected variable declaration");
 892             return false;
 893         }
 894
 895         isfunc = false;
 896         func = NULL;
 897         ctx = parser_ctx(parser);
 898         var = parser_parse_type(parser, basetype, &isfunc);
 899
 900         if (!var)
 901             return false;
 902
 903         if (parser->tok != TOKEN_IDENT) {
 904             parseerror(parser, "expected variable name\n");
 905             return false;
 906         }
 907
 908         if (!localblock && parser_find_global(parser, parser_tokval(parser))) {
 909             ast_value_delete(var);
 910             parseerror(parser, "global already exists: %s\n", parser_tokval(parser));
 911             return false;
 912         }
 913
 914         if (localblock && parser_find_local(parser, parser_tokval(parser), parser->blocklocal)) {
 915             ast_value_delete(var);
 916             parseerror(parser, "local variable already exists: %s\n", parser_tokval(parser));
 917             return false;
 918         }
 919
 920         if (!ast_value_set_name(var, parser_tokval(parser))) {
 921             parseerror(parser, "failed to set variable name\n");
 922             ast_value_delete(var);
 923             return false;
 924         }
 925
 926         if (isfunc) {
 927             /* a function was defined */
 928             ast_value *fval;
 929
 930             /* turn var into a value of TYPE_FUNCTION, with the old var
 931              * as return type
 932              */
 933             fval = ast_value_new(ctx, var->name, TYPE_FUNCTION);
 934             func = ast_function_new(ctx, var->name, fval);
 935             if (!fval || !func) {
 936                 ast_value_delete(var);
 937                 if (fval) ast_value_delete(fval);
 938                 if (func) ast_function_delete(func);
 939                 return false;
 940             }
 941
 942             fval->expression.next = (ast_expression*)var;
 943             MEM_VECTOR_MOVE(&var->expression, params, &fval->expression, params);
 944
 945             if (!parser_t_functions_add(parser, func)) {
 946                 ast_value_delete(var);
 947                 if (fval) ast_value_delete(fval);
 948                 if (func) ast_function_delete(func);
 949                 return false;
 950             }
 951
 952             var = fval;
 953         }
 954
 955         varent.name = util_strdup(var->name);
 956         varent.var = (ast_expression*)var;
 957         if (var->expression.vtype == TYPE_VECTOR)
 958         {
 959             size_t len = strlen(varent.name);
 960             varentry_t vx, vy, vz;
 961             vx.var = (ast_expression*)ast_member_new(var->expression.node.context, (ast_expression*)var, 0);
 962             vy.var = (ast_expression*)ast_member_new(var->expression.node.context, (ast_expression*)var, 1);
 963             vz.var = (ast_expression*)ast_member_new(var->expression.node.context, (ast_expression*)var, 2);
 964             vx.name = mem_a(len+3);
 965             vy.name = mem_a(len+3);
 966             vz.name = mem_a(len+3);
 967             strcpy(vx.name, varent.name);
 968             strcpy(vy.name, varent.name);
 969             strcpy(vz.name, varent.name);
 970             vx.name[len] = vy.name[len] = vz.name[len] = '_';
 971             vx.name[len+1] = 'x';
 972             vy.name[len+1] = 'y';
 973             vz.name[len+1] = 'z';
 974             vx.name[len+2] = vy.name[len+2] = vz.name[len+2] = 0;
 975
 976             if (!localblock) {
 977                 (void)!parser_t_globals_add(parser, varent);
 978                 (void)!parser_t_globals_add(parser, vx);
 979                 (void)!parser_t_globals_add(parser, vy);
 980                 (void)!parser_t_globals_add(parser, vz);
 981             } else {
 982                 (void)!parser_t_locals_add(parser, varent);
 983                 (void)!parser_t_locals_add(parser, vx);
 984                 (void)!parser_t_locals_add(parser, vy);
 985                 (void)!parser_t_locals_add(parser, vz);
 986             }
 987         }
 988         else
 989         {
 990             if ( (!localblock && !parser_t_globals_add(parser, varent)) ||
 991                  ( localblock && !parser_t_locals_add(parser, varent)) )
 992             {
 993                 ast_value_delete(var);
 994                 return false;
 995             }
 996         }
 997         if (localblock && !ast_block_locals_add(localblock, var))
 998         {
 999             parser_pop_local(parser);
1000             ast_value_delete(var);
1001             return false;
1002         }
1003
1004         if (!parser_next(parser)) {
1005             ast_value_delete(var);
1006             return false;
1007         }
1008
1009         if (parser->tok == ';') {
1010             if (!parser_next(parser))
1011                 return parser->tok == TOKEN_EOF;
1012             return true;
1013         }
1014
1015         if (parser->tok == ',') {
1016             /* another var */
1017             continue;
1018         }
1019
1020         if (parser->tok != '=') {
1021             parseerror(parser, "expected '=' or ';'");
1022             return false;
1023         }
1024
1025         if (!parser_next(parser))
1026             return false;
1027
1028         if (parser->tok == '#') {
1029             if (localblock) {
1030                 parseerror(parser, "cannot declare builtins within functions");
1031                 return false;
1032             }
1033             if (!isfunc || !func) {
1034                 parseerror(parser, "unexpected builtin number, '%s' is not a function", var->name);
1035                 return false;
1036             }
1037             if (!parser_next(parser)) {
1038                 parseerror(parser, "expected builtin number");
1039                 return false;
1040             }
1041             if (parser->tok != TOKEN_INTCONST) {
1042                 parseerror(parser, "builtin number must be an integer constant");
1043                 return false;
1044             }
1045             if (parser_token(parser)->constval.i <= 0) {
1046                 parseerror(parser, "builtin number must be positive integer greater than zero");
1047                 return false;
1048             }
1049
1050             func->builtin = -parser_token(parser)->constval.i;
1051         } else if (parser->tok == '{') {
1052             /* function body */
1053             ast_block *block;
1054             ast_function *old = parser->function;
1055
1056             if (localblock) {
1057                 parseerror(parser, "cannot declare functions within functions");
1058                 return false;
1059             }
1060
1061             parser->function = func;
1062             block = parser_parse_block(parser);
1063             parser->function = old;
1064
1065             if (!block)
1066                 return false;
1067
1068             if (!ast_function_blocks_add(func, block)) {
1069                 ast_block_delete(block);
1070                 return false;
1071             }
1072             return true;
1073         } else {
1074             parseerror(parser, "TODO, const assignment");
1075         }
1076
1077         if (!parser_next(parser))
1078             return false;
1079
1080         if (parser->tok == ',') {
1081             /* another */
1082             continue;
1083         }
1084
1085         if (parser->tok != ';') {
1086             parseerror(parser, "expected semicolon");
1087             return false;
1088         }
1089
1090         (void)parser_next(parser);
1091
1092         return true;
1093     }
1094 }
1095
1096 static bool parser_do(parser_t *parser)
1097 {
1098     if (parser->tok == TOKEN_TYPENAME)
1099     {
1100         return parser_variable(parser, NULL);
1101     }
1102     else if (parser->tok == TOKEN_KEYWORD)
1103     {
1104         /* handle 'var' and 'const' */
1105         return false;
1106     }
1107     else if (parser->tok == '.')
1108     {
1109         /* entity-member declaration */
1110         return false;
1111     }
1112     else
1113     {
1114         parseerror(parser, "unexpected token: %s", parser->lex->tok->value);
1115         return false;
1116     }
1117     return true;
1118 }
1119
1120 static parser_t *parser;
1121
1122 bool parser_init()
1123 {
1124     parser = (parser_t*)mem_a(sizeof(parser_t));
1125     if (!parser)
1126         return false;
1127
1128     memset(parser, 0, sizeof(parser));
1129
1130     MEM_VECTOR_INIT(parser, globals);
1131     MEM_VECTOR_INIT(parser, locals);
1132     return true;
1133 }
1134
1135 bool parser_compile(const char *filename)
1136 {
1137     parser->lex = lex_open(filename);
1138     if (!parser->lex) {
1139         printf("failed to open file \"%s\"\n", filename);
1140         return false;
1141     }
1142
1143     /* initial lexer/parser state */
1144     parser->lex->flags.noops = true;
1145
1146     if (parser_next(parser))
1147     {
1148         while (parser->tok != TOKEN_EOF && parser->tok < TOKEN_ERROR)
1149         {
1150             if (!parser_do(parser)) {
1151                 if (parser->tok == TOKEN_EOF)
1152                     parseerror(parser, "unexpected eof");
1153                 else
1154                     parseerror(parser, "parse error\n");
1155                 lex_close(parser->lex);
1156                 mem_d(parser);
1157                 return false;
1158             }
1159         }
1160     }
1161
1162     lex_close(parser->lex);
1163
1164     return !parser->errors;
1165 }
1166
1167 void parser_cleanup()
1168 {
1169     size_t i;
1170     for (i = 0; i < parser->functions_count; ++i) {
1171         ast_delete(parser->functions[i]);
1172     }
1173     for (i = 0; i < parser->imm_vector_count; ++i) {
1174         ast_delete(parser->imm_vector[i]);
1175     }
1176     for (i = 0; i < parser->imm_string_count; ++i) {
1177         ast_delete(parser->imm_string[i]);
1178     }
1179     for (i = 0; i < parser->imm_float_count; ++i) {
1180         ast_delete(parser->imm_float[i]);
1181     }
1182     for (i = 0; i < parser->globals_count; ++i) {
1183         ast_delete(parser->globals[i].var);
1184         mem_d(parser->globals[i].name);
1185     }
1186     MEM_VECTOR_CLEAR(parser, globals);
1187
1188     mem_d(parser);
1189 }
1190
1191 bool parser_finish(const char *output)
1192 {
1193     size_t i;
1194     ir_builder *ir;
1195
1196     if (!parser->errors)
1197     {
1198         ir = ir_builder_new("gmqcc_out");
1199         if (!ir) {
1200             printf("failed to allocate builder\n");
1201             return false;
1202         }
1203
1204         for (i = 0; i < parser->imm_float_count; ++i) {
1205             if (!ast_global_codegen(parser->imm_float[i], ir)) {
1206                 printf("failed to generate global %s\n", parser->imm_float[i]->name);
1207                 ir_builder_delete(ir);
1208                 return false;
1209             }
1210         }
1211         for (i = 0; i < parser->imm_string_count; ++i) {
1212             if (!ast_global_codegen(parser->imm_string[i], ir)) {
1213                 printf("failed to generate global %s\n", parser->imm_string[i]->name);
1214                 ir_builder_delete(ir);
1215                 return false;
1216             }
1217         }
1218         for (i = 0; i < parser->imm_vector_count; ++i) {
1219             if (!ast_global_codegen(parser->imm_vector[i], ir)) {
1220                 printf("failed to generate global %s\n", parser->imm_vector[i]->name);
1221                 ir_builder_delete(ir);
1222                 return false;
1223             }
1224         }
1225         for (i = 0; i < parser->globals_count; ++i) {
1226             if (!ast_istype(parser->globals[i].var, ast_value))
1227                 continue;
1228             if (!ast_global_codegen((ast_value*)(parser->globals[i].var), ir)) {
1229                 printf("failed to generate global %s\n", parser->globals[i].name);
1230                 ir_builder_delete(ir);
1231                 return false;
1232             }
1233         }
1234         for (i = 0; i < parser->functions_count; ++i) {
1235             if (!ast_function_codegen(parser->functions[i], ir)) {
1236                 printf("failed to generate function %s\n", parser->functions[i]->name);
1237                 ir_builder_delete(ir);
1238                 return false;
1239             }
1240             if (!ir_function_finalize(parser->functions[i]->ir_func)) {
1241                 printf("failed to finalize function %s\n", parser->functions[i]->name);
1242                 ir_builder_delete(ir);
1243                 return false;
1244             }
1245         }
1246
1247         ir_builder_dump(ir, printf);
1248
1249         if (!ir_builder_generate(ir, output)) {
1250             printf("*** failed to generate output file\n");
1251             ir_builder_delete(ir);
1252             return false;
1253         }
1254
1255         ir_builder_delete(ir);
1256         return true;
1257     }
1258
1259     printf("*** there were compile errors\n");
1260     return false;
1261 }