temp committing major c++ification
[xonotic/gmqcc.git] / parser.cpp
1 #include <string.h>
2 #include <math.h>
3
4 #include "intrin.h"
5 #include "fold.h"
6 #include "ast.h"
7 #include "parser.h"
8
9 #define PARSER_HT_LOCALS  2
10 #define PARSER_HT_SIZE    512
11 #define TYPEDEF_HT_SIZE   512
12
13 static void parser_enterblock(parser_t *parser);
14 static bool parser_leaveblock(parser_t *parser);
15 static void parser_addlocal(parser_t *parser, const char *name, ast_expression *e);
16 static void parser_addglobal(parser_t *parser, const char *name, ast_expression *e);
17 static bool parse_typedef(parser_t *parser);
18 static bool parse_variable(parser_t *parser, ast_block *localblock, bool nofields, int qualifier, ast_value *cached_typedef, bool noref, bool is_static, uint32_t qflags, char *vstring);
19 static ast_block* parse_block(parser_t *parser);
20 static bool parse_block_into(parser_t *parser, ast_block *block);
21 static bool parse_statement_or_block(parser_t *parser, ast_expression **out);
22 static bool parse_statement(parser_t *parser, ast_block *block, ast_expression **out, bool allow_cases);
23 static ast_expression* parse_expression_leave(parser_t *parser, bool stopatcomma, bool truthvalue, bool with_labels);
24 static ast_expression* parse_expression(parser_t *parser, bool stopatcomma, bool with_labels);
25 static ast_value* parser_create_array_setter_proto(parser_t *parser, ast_value *array, const char *funcname);
26 static ast_value* parser_create_array_getter_proto(parser_t *parser, ast_value *array, const ast_expression *elemtype, const char *funcname);
27 static ast_value *parse_typename(parser_t *parser, ast_value **storebase, ast_value *cached_typedef, bool *is_vararg);
28
29 static void parseerror(parser_t *parser, const char *fmt, ...)
30 {
31     va_list ap;
32     va_start(ap, fmt);
33     vcompile_error(parser->lex->tok.ctx, fmt, ap);
34     va_end(ap);
35 }
36
37 /* returns true if it counts as an error */
38 static bool GMQCC_WARN parsewarning(parser_t *parser, int warntype, const char *fmt, ...)
39 {
40     bool    r;
41     va_list ap;
42     va_start(ap, fmt);
43     r = vcompile_warning(parser->lex->tok.ctx, warntype, fmt, ap);
44     va_end(ap);
45     return r;
46 }
47
48 /**********************************************************************
49  * parsing
50  */
51
52 static bool parser_next(parser_t *parser)
53 {
54     /* lex_do kills the previous token */
55     parser->tok = lex_do(parser->lex);
56     if (parser->tok == TOKEN_EOF)
57         return true;
58     if (parser->tok >= TOKEN_ERROR) {
59         parseerror(parser, "lex error");
60         return false;
61     }
62     return true;
63 }
64
65 #define parser_tokval(p) ((p)->lex->tok.value)
66 #define parser_token(p)  (&((p)->lex->tok))
67
68 char *parser_strdup(const char *str)
69 {
70     if (str && !*str) {
71         /* actually dup empty strings */
72         char *out = (char*)mem_a(1);
73         *out = 0;
74         return out;
75     }
76     return util_strdup(str);
77 }
78
79 static ast_expression* parser_find_field(parser_t *parser, const char *name)
80 {
81     return ( ast_expression*)util_htget(parser->htfields, name);
82 }
83
84 static ast_expression* parser_find_label(parser_t *parser, const char *name)
85 {
86     for (auto &it : parser->labels)
87         if (!strcmp(it->name, name))
88             return (ast_expression*)it;
89     return nullptr;
90 }
91
92 ast_expression* parser_find_global(parser_t *parser, const char *name)
93 {
94     ast_expression *var = (ast_expression*)util_htget(parser->aliases, parser_tokval(parser));
95     if (var)
96         return var;
97     return (ast_expression*)util_htget(parser->htglobals, name);
98 }
99
100 static ast_expression* parser_find_param(parser_t *parser, const char *name)
101 {
102     ast_value *fun;
103     if (!parser->function)
104         return nullptr;
105     fun = parser->function->function_type;
106     for (auto &it : fun->type_params) {
107         if (!strcmp(it->name, name))
108             return (ast_expression*)it;
109     }
110     return nullptr;
111 }
112
113 static ast_expression* parser_find_local(parser_t *parser, const char *name, size_t upto, bool *isparam)
114 {
115     size_t          i, hash;
116     ast_expression *e;
117
118     hash = util_hthash(parser->htglobals, name);
119
120     *isparam = false;
121     for (i = vec_size(parser->variables); i > upto;) {
122         --i;
123         if ( (e = (ast_expression*)util_htgeth(parser->variables[i], name, hash)) )
124             return e;
125     }
126     *isparam = true;
127     return parser_find_param(parser, name);
128 }
129
130 static ast_expression* parser_find_var(parser_t *parser, const char *name)
131 {
132     bool dummy;
133     ast_expression *v;
134     v         = parser_find_local(parser, name, 0, &dummy);
135     if (!v) v = parser_find_global(parser, name);
136     return v;
137 }
138
139 static ast_value* parser_find_typedef(parser_t *parser, const char *name, size_t upto)
140 {
141     size_t     i, hash;
142     ast_value *e;
143     hash = util_hthash(parser->typedefs[0], name);
144
145     for (i = vec_size(parser->typedefs); i > upto;) {
146         --i;
147         if ( (e = (ast_value*)util_htgeth(parser->typedefs[i], name, hash)) )
148             return e;
149     }
150     return nullptr;
151 }
152
153 struct sy_elem {
154     size_t etype; /* 0 = expression, others are operators */
155     bool isparen;
156     size_t off;
157     ast_expression *out;
158     ast_block *block; /* for commas and function calls */
159     lex_ctx_t ctx;
160 };
161
162 enum {
163     PAREN_EXPR,
164     PAREN_FUNC,
165     PAREN_INDEX,
166     PAREN_TERNARY1,
167     PAREN_TERNARY2
168 };
169
170 struct shunt {
171     std::vector<sy_elem> out;
172     std::vector<sy_elem> ops;
173     std::vector<size_t> argc;
174     std::vector<unsigned int> paren;
175 };
176
177 static sy_elem syexp(lex_ctx_t ctx, ast_expression *v) {
178     sy_elem e;
179     e.etype = 0;
180     e.off   = 0;
181     e.out   = v;
182     e.block = nullptr;
183     e.ctx   = ctx;
184     e.isparen = false;
185     return e;
186 }
187
188 static sy_elem syblock(lex_ctx_t ctx, ast_block *v) {
189     sy_elem e;
190     e.etype = 0;
191     e.off   = 0;
192     e.out   = (ast_expression*)v;
193     e.block = v;
194     e.ctx   = ctx;
195     e.isparen = false;
196     return e;
197 }
198
199 static sy_elem syop(lex_ctx_t ctx, const oper_info *op) {
200     sy_elem e;
201     e.etype = 1 + (op - operators);
202     e.off   = 0;
203     e.out   = nullptr;
204     e.block = nullptr;
205     e.ctx   = ctx;
206     e.isparen = false;
207     return e;
208 }
209
210 static sy_elem syparen(lex_ctx_t ctx, size_t off) {
211     sy_elem e;
212     e.etype = 0;
213     e.off   = off;
214     e.out   = nullptr;
215     e.block = nullptr;
216     e.ctx   = ctx;
217     e.isparen = true;
218     return e;
219 }
220
221 /* With regular precedence rules, ent.foo[n] is the same as (ent.foo)[n],
222  * so we need to rotate it to become ent.(foo[n]).
223  */
224 static bool rotate_entfield_array_index_nodes(ast_expression **out)
225 {
226     ast_array_index *index, *oldindex;
227     ast_entfield    *entfield;
228
229     ast_value       *field;
230     ast_expression  *sub;
231     ast_expression  *entity;
232
233     lex_ctx_t ctx = ast_ctx(*out);
234
235     if (!ast_istype(*out, ast_array_index))
236         return false;
237     index = (ast_array_index*)*out;
238
239     if (!ast_istype(index->array, ast_entfield))
240         return false;
241     entfield = (ast_entfield*)index->array;
242
243     if (!ast_istype(entfield->field, ast_value))
244         return false;
245     field = (ast_value*)entfield->field;
246
247     sub    = index->index;
248     entity = entfield->entity;
249
250     oldindex = index;
251
252     index = ast_array_index_new(ctx, (ast_expression*)field, sub);
253     entfield = ast_entfield_new(ctx, entity, (ast_expression*)index);
254     *out = (ast_expression*)entfield;
255
256     oldindex->array = nullptr;
257     oldindex->index = nullptr;
258     ast_delete(oldindex);
259
260     return true;
261 }
262
263 static bool check_write_to(lex_ctx_t ctx, ast_expression *expr)
264 {
265     if (ast_istype(expr, ast_value)) {
266         ast_value *val = (ast_value*)expr;
267         if (val->cvq == CV_CONST) {
268             if (val->name[0] == '#') {
269                 compile_error(ctx, "invalid assignment to a literal constant");
270                 return false;
271             }
272             /*
273              * To work around quakeworld we must elide the error and make it
274              * a warning instead.
275              */
276             if (OPTS_OPTION_U32(OPTION_STANDARD) != COMPILER_QCC)
277                 compile_error(ctx, "assignment to constant `%s`", val->name);
278             else
279                 (void)!compile_warning(ctx, WARN_CONST_OVERWRITE, "assignment to constant `%s`", val->name);
280             return false;
281         }
282     }
283     return true;
284 }
285
286 static bool parser_sy_apply_operator(parser_t *parser, shunt *sy)
287 {
288     const oper_info *op;
289     lex_ctx_t ctx;
290     ast_expression *out = nullptr;
291     ast_expression *exprs[3];
292     ast_block      *blocks[3];
293     ast_binstore   *asbinstore;
294     size_t i, assignop, addop, subop;
295     qcint_t  generated_op = 0;
296
297     char ty1[1024];
298     char ty2[1024];
299
300     if (sy->ops.empty()) {
301         parseerror(parser, "internal error: missing operator");
302         return false;
303     }
304
305     if (sy->ops.back().isparen) {
306         parseerror(parser, "unmatched parenthesis");
307         return false;
308     }
309
310     op = &operators[sy->ops.back().etype - 1];
311     ctx = sy->ops.back().ctx;
312
313     if (sy->out.size() < op->operands) {
314         if (op->flags & OP_PREFIX)
315             compile_error(ctx, "expected expression after unary operator `%s`", op->op, (int)op->id);
316         else /* this should have errored previously already */
317             compile_error(ctx, "expected expression after operator `%s`", op->op, (int)op->id);
318         return false;
319     }
320
321     sy->ops.pop_back();
322
323     /* op(:?) has no input and no output */
324     if (!op->operands)
325         return true;
326
327     sy->out.erase(sy->out.end() - op->operands, sy->out.end());
328     for (i = 0; i < op->operands; ++i) {
329         exprs[i]  = sy->out[sy->out.size()+i].out;
330         blocks[i] = sy->out[sy->out.size()+i].block;
331
332         if (exprs[i]->vtype == TYPE_NOEXPR &&
333             !(i != 0 && op->id == opid2('?',':')) &&
334             !(i == 1 && op->id == opid1('.')))
335         {
336             if (ast_istype(exprs[i], ast_label))
337                 compile_error(ast_ctx(exprs[i]), "expected expression, got an unknown identifier");
338             else
339                 compile_error(ast_ctx(exprs[i]), "not an expression");
340             (void)!compile_warning(ast_ctx(exprs[i]), WARN_DEBUG, "expression %u\n", (unsigned int)i);
341         }
342     }
343
344     if (blocks[0] && blocks[0]->exprs.empty() && op->id != opid1(',')) {
345         compile_error(ctx, "internal error: operator cannot be applied on empty blocks");
346         return false;
347     }
348
349 #define NotSameType(T) \
350              (exprs[0]->vtype != exprs[1]->vtype || \
351               exprs[0]->vtype != T)
352
353     switch (op->id)
354     {
355         default:
356             compile_error(ctx, "internal error: unhandled operator: %s (%i)", op->op, (int)op->id);
357             return false;
358
359         case opid1('.'):
360             if (exprs[0]->vtype == TYPE_VECTOR &&
361                 exprs[1]->vtype == TYPE_NOEXPR)
362             {
363                 if      (exprs[1] == (ast_expression*)parser->const_vec[0])
364                     out = (ast_expression*)ast_member_new(ctx, exprs[0], 0, nullptr);
365                 else if (exprs[1] == (ast_expression*)parser->const_vec[1])
366                     out = (ast_expression*)ast_member_new(ctx, exprs[0], 1, nullptr);
367                 else if (exprs[1] == (ast_expression*)parser->const_vec[2])
368                     out = (ast_expression*)ast_member_new(ctx, exprs[0], 2, nullptr);
369                 else {
370                     compile_error(ctx, "access to invalid vector component");
371                     return false;
372                 }
373             }
374             else if (exprs[0]->vtype == TYPE_ENTITY) {
375                 if (exprs[1]->vtype != TYPE_FIELD) {
376                     compile_error(ast_ctx(exprs[1]), "type error: right hand of member-operand should be an entity-field");
377                     return false;
378                 }
379                 out = (ast_expression*)ast_entfield_new(ctx, exprs[0], exprs[1]);
380             }
381             else if (exprs[0]->vtype == TYPE_VECTOR) {
382                 compile_error(ast_ctx(exprs[1]), "vectors cannot be accessed this way");
383                 return false;
384             }
385             else {
386                 compile_error(ast_ctx(exprs[1]), "type error: member-of operator on something that is not an entity or vector");
387                 return false;
388             }
389             break;
390
391         case opid1('['):
392             if (exprs[0]->vtype != TYPE_ARRAY &&
393                 !(exprs[0]->vtype == TYPE_FIELD &&
394                   exprs[0]->next->vtype == TYPE_ARRAY))
395             {
396                 ast_type_to_string(exprs[0], ty1, sizeof(ty1));
397                 compile_error(ast_ctx(exprs[0]), "cannot index value of type %s", ty1);
398                 return false;
399             }
400             if (exprs[1]->vtype != TYPE_FLOAT) {
401                 ast_type_to_string(exprs[0], ty1, sizeof(ty1));
402                 compile_error(ast_ctx(exprs[1]), "index must be of type float, not %s", ty1);
403                 return false;
404             }
405             out = (ast_expression*)ast_array_index_new(ctx, exprs[0], exprs[1]);
406             rotate_entfield_array_index_nodes(&out);
407             break;
408
409         case opid1(','):
410             if (sy->paren.size() && sy->paren.back() == PAREN_FUNC) {
411                 sy->out.push_back(syexp(ctx, exprs[0]));
412                 sy->out.push_back(syexp(ctx, exprs[1]));
413                 sy->argc.back()++;
414                 return true;
415             }
416             if (blocks[0]) {
417                 if (!ast_block_add_expr(blocks[0], exprs[1]))
418                     return false;
419             } else {
420                 blocks[0] = ast_block_new(ctx);
421                 if (!ast_block_add_expr(blocks[0], exprs[0]) ||
422                     !ast_block_add_expr(blocks[0], exprs[1]))
423                 {
424                     return false;
425                 }
426             }
427             ast_block_set_type(blocks[0], exprs[1]);
428
429             sy->out.push_back(syblock(ctx, blocks[0]));
430             return true;
431
432         case opid2('+','P'):
433             out = exprs[0];
434             break;
435         case opid2('-','P'):
436             if ((out = parser->m_fold.op(op, exprs)))
437                 break;
438
439             if (exprs[0]->vtype != TYPE_FLOAT &&
440                 exprs[0]->vtype != TYPE_VECTOR) {
441                     compile_error(ctx, "invalid types used in unary expression: cannot negate type %s",
442                                   type_name[exprs[0]->vtype]);
443                 return false;
444             }
445             if (exprs[0]->vtype == TYPE_FLOAT)
446                 out = (ast_expression*)ast_unary_new(ctx, VINSTR_NEG_F, exprs[0]);
447             else
448                 out = (ast_expression*)ast_unary_new(ctx, VINSTR_NEG_V, exprs[0]);
449             break;
450
451         case opid2('!','P'):
452             if (!(out = parser->m_fold.op(op, exprs))) {
453                 switch (exprs[0]->vtype) {
454                     case TYPE_FLOAT:
455                         out = (ast_expression*)ast_unary_new(ctx, INSTR_NOT_F, exprs[0]);
456                         break;
457                     case TYPE_VECTOR:
458                         out = (ast_expression*)ast_unary_new(ctx, INSTR_NOT_V, exprs[0]);
459                         break;
460                     case TYPE_STRING:
461                         if (OPTS_FLAG(TRUE_EMPTY_STRINGS))
462                             out = (ast_expression*)ast_unary_new(ctx, INSTR_NOT_F, exprs[0]);
463                         else
464                             out = (ast_expression*)ast_unary_new(ctx, INSTR_NOT_S, exprs[0]);
465                         break;
466                     /* we don't constant-fold NOT for these types */
467                     case TYPE_ENTITY:
468                         out = (ast_expression*)ast_unary_new(ctx, INSTR_NOT_ENT, exprs[0]);
469                         break;
470                     case TYPE_FUNCTION:
471                         out = (ast_expression*)ast_unary_new(ctx, INSTR_NOT_FNC, exprs[0]);
472                         break;
473                     default:
474                     compile_error(ctx, "invalid types used in expression: cannot logically negate type %s",
475                                   type_name[exprs[0]->vtype]);
476                     return false;
477                 }
478             }
479             break;
480
481         case opid1('+'):
482             if (exprs[0]->vtype != exprs[1]->vtype ||
483                (exprs[0]->vtype != TYPE_VECTOR && exprs[0]->vtype != TYPE_FLOAT) )
484             {
485                 compile_error(ctx, "invalid types used in expression: cannot add type %s and %s",
486                               type_name[exprs[0]->vtype],
487                               type_name[exprs[1]->vtype]);
488                 return false;
489             }
490             if (!(out = parser->m_fold.op(op, exprs))) {
491                 switch (exprs[0]->vtype) {
492                     case TYPE_FLOAT:
493                         out = fold::binary(ctx, INSTR_ADD_F, exprs[0], exprs[1]);
494                         break;
495                     case TYPE_VECTOR:
496                         out = fold::binary(ctx, INSTR_ADD_V, exprs[0], exprs[1]);
497                         break;
498                     default:
499                         compile_error(ctx, "invalid types used in expression: cannot add type %s and %s",
500                                       type_name[exprs[0]->vtype],
501                                       type_name[exprs[1]->vtype]);
502                         return false;
503                 }
504             }
505             break;
506         case opid1('-'):
507             if  (exprs[0]->vtype != exprs[1]->vtype ||
508                 (exprs[0]->vtype != TYPE_VECTOR && exprs[0]->vtype != TYPE_FLOAT))
509             {
510                 compile_error(ctx, "invalid types used in expression: cannot subtract type %s from %s",
511                               type_name[exprs[1]->vtype],
512                               type_name[exprs[0]->vtype]);
513                 return false;
514             }
515             if (!(out = parser->m_fold.op(op, exprs))) {
516                 switch (exprs[0]->vtype) {
517                     case TYPE_FLOAT:
518                         out = fold::binary(ctx, INSTR_SUB_F, exprs[0], exprs[1]);
519                         break;
520                     case TYPE_VECTOR:
521                         out = fold::binary(ctx, INSTR_SUB_V, exprs[0], exprs[1]);
522                         break;
523                     default:
524                         compile_error(ctx, "invalid types used in expression: cannot subtract type %s from %s",
525                                       type_name[exprs[1]->vtype],
526                                       type_name[exprs[0]->vtype]);
527                         return false;
528                 }
529             }
530             break;
531         case opid1('*'):
532             if (exprs[0]->vtype != exprs[1]->vtype &&
533                 !(exprs[0]->vtype == TYPE_VECTOR &&
534                   exprs[1]->vtype == TYPE_FLOAT) &&
535                 !(exprs[1]->vtype == TYPE_VECTOR &&
536                   exprs[0]->vtype == TYPE_FLOAT)
537                 )
538             {
539                 compile_error(ctx, "invalid types used in expression: cannot multiply types %s and %s",
540                               type_name[exprs[1]->vtype],
541                               type_name[exprs[0]->vtype]);
542                 return false;
543             }
544             if (!(out = parser->m_fold.op(op, exprs))) {
545                 switch (exprs[0]->vtype) {
546                     case TYPE_FLOAT:
547                         if (exprs[1]->vtype == TYPE_VECTOR)
548                             out = fold::binary(ctx, INSTR_MUL_FV, exprs[0], exprs[1]);
549                         else
550                             out = fold::binary(ctx, INSTR_MUL_F, exprs[0], exprs[1]);
551                         break;
552                     case TYPE_VECTOR:
553                         if (exprs[1]->vtype == TYPE_FLOAT)
554                             out = fold::binary(ctx, INSTR_MUL_VF, exprs[0], exprs[1]);
555                         else
556                             out = fold::binary(ctx, INSTR_MUL_V, exprs[0], exprs[1]);
557                         break;
558                     default:
559                         compile_error(ctx, "invalid types used in expression: cannot multiply types %s and %s",
560                                       type_name[exprs[1]->vtype],
561                                       type_name[exprs[0]->vtype]);
562                         return false;
563                 }
564             }
565             break;
566
567         case opid1('/'):
568             if (exprs[1]->vtype != TYPE_FLOAT) {
569                 ast_type_to_string(exprs[0], ty1, sizeof(ty1));
570                 ast_type_to_string(exprs[1], ty2, sizeof(ty2));
571                 compile_error(ctx, "invalid types used in expression: cannot divide types %s and %s", ty1, ty2);
572                 return false;
573             }
574             if (!(out = parser->m_fold.op(op, exprs))) {
575                 if (exprs[0]->vtype == TYPE_FLOAT)
576                     out = fold::binary(ctx, INSTR_DIV_F, exprs[0], exprs[1]);
577                 else {
578                     ast_type_to_string(exprs[0], ty1, sizeof(ty1));
579                     ast_