Merge branch 'master' into cooking
[xonotic/gmqcc.git] / ast.h
1 /*
2  * Copyright (C) 2012, 2013
3  *     Wolfgang Bumiller
4  *     Dale Weiler
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a copy of
7  * this software and associated documentation files (the "Software"), to deal in
8  * the Software without restriction, including without limitation the rights to
9  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
10  * of the Software, and to permit persons to whom the Software is furnished to do
11  * so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in all
14  * copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22  * SOFTWARE.
23  */
24 #ifndef GMQCC_AST_HDR
25 #define GMQCC_AST_HDR
26 #include "ir.h"
27
28 typedef uint16_t ast_flag_t;
29
30 /* Note: I will not be using a _t suffix for the
31  * "main" ast node types for now.
32  */
33
34 typedef struct ast_node_common       ast_node;
35 typedef struct ast_expression_common ast_expression;
36
37 typedef struct ast_value_s       ast_value;
38 typedef struct ast_function_s    ast_function;
39 typedef struct ast_block_s       ast_block;
40 typedef struct ast_binary_s      ast_binary;
41 typedef struct ast_store_s       ast_store;
42 typedef struct ast_binstore_s    ast_binstore;
43 typedef struct ast_entfield_s    ast_entfield;
44 typedef struct ast_ifthen_s      ast_ifthen;
45 typedef struct ast_ternary_s     ast_ternary;
46 typedef struct ast_loop_s        ast_loop;
47 typedef struct ast_call_s        ast_call;
48 typedef struct ast_unary_s       ast_unary;
49 typedef struct ast_return_s      ast_return;
50 typedef struct ast_member_s      ast_member;
51 typedef struct ast_array_index_s ast_array_index;
52 typedef struct ast_breakcont_s   ast_breakcont;
53 typedef struct ast_switch_s      ast_switch;
54 typedef struct ast_label_s       ast_label;
55 typedef struct ast_goto_s        ast_goto;
56 typedef struct ast_argpipe_s     ast_argpipe;
57
58 enum {
59     AST_FLAG_VARIADIC      = 1 << 0,
60     AST_FLAG_NORETURN      = 1 << 1,
61     AST_FLAG_INLINE        = 1 << 2,
62     AST_FLAG_INITIALIZED   = 1 << 3,
63     AST_FLAG_DEPRECATED    = 1 << 4,
64     AST_FLAG_INCLUDE_DEF   = 1 << 5,
65     AST_FLAG_IS_VARARG     = 1 << 6,
66     AST_FLAG_ALIAS         = 1 << 7,
67     AST_FLAG_ERASEABLE     = 1 << 8,
68     AST_FLAG_ACCUMULATE    = 1 << 9,
69
70     /*
71      * An array declared as []
72      * so that the size is taken from the initializer
73      */
74     AST_FLAG_ARRAY_INIT    = 1 << 10,
75
76     AST_FLAG_LAST,
77     AST_FLAG_TYPE_MASK     = (AST_FLAG_VARIADIC | AST_FLAG_NORETURN)
78 };
79
80 enum {
81     TYPE_ast_node,        /*  0 */
82     TYPE_ast_expression,  /*  1 */
83     TYPE_ast_value,       /*  2 */
84     TYPE_ast_function,    /*  3 */
85     TYPE_ast_block,       /*  4 */
86     TYPE_ast_binary,      /*  5 */
87     TYPE_ast_store,       /*  6 */
88     TYPE_ast_binstore,    /*  7 */
89     TYPE_ast_entfield,    /*  8 */
90     TYPE_ast_ifthen,      /*  9 */
91     TYPE_ast_ternary,     /* 10 */
92     TYPE_ast_loop,        /* 11 */
93     TYPE_ast_call,        /* 12 */
94     TYPE_ast_unary,       /* 13 */
95     TYPE_ast_return,      /* 14 */
96     TYPE_ast_member,      /* 15 */
97     TYPE_ast_array_index, /* 16 */
98     TYPE_ast_breakcont,   /* 17 */
99     TYPE_ast_switch,      /* 18 */
100     TYPE_ast_label,       /* 19 */
101     TYPE_ast_goto,        /* 20 */
102     TYPE_ast_argpipe      /* 21 */
103 };
104
105 #define ast_istype(x, t) ( ((ast_node*)x)->nodetype == (TYPE_##t) )
106 #define ast_ctx(node) (((ast_node*)(node))->context)
107 #define ast_side_effects(node) (((ast_node*)(node))->side_effects)
108
109 /* Node interface with common components
110  */
111 typedef void ast_node_delete(ast_node*);
112 struct ast_node_common
113 {
114     lex_ctx_t          context;
115     /* I don't feel comfortable using keywords like 'delete' as names... */
116     ast_node_delete *destroy;
117     int              nodetype;
118     /* keep: if a node contains this node, 'keep'
119      * prevents its dtor from destroying this node as well.
120      */
121     bool             keep;
122     bool             side_effects;
123 };
124
125 #define ast_delete(x) (*( ((ast_node*)(x))->destroy ))((ast_node*)(x))
126 #define ast_unref(x) do                \
127 {                                      \
128     if (! (((ast_node*)(x))->keep) ) { \
129         ast_delete(x);                 \
130     }                                  \
131 } while(0)
132
133 /* Expression interface
134  *
135  * Any expression or block returns an ir_value, and needs
136  * to know the current function.
137  */
138 typedef bool ast_expression_codegen(ast_expression*,
139                                     ast_function*,
140                                     bool lvalue,
141                                     ir_value**);
142 /* TODO: the codegen function should take an output-type parameter
143  * indicating whether a variable, type, label etc. is expected, and
144  * an environment!
145  * Then later an ast_ident could have a codegen using this to figure
146  * out what to look for.
147  * eg. in code which uses a not-yet defined variable, the expression
148  * would take an ast_ident, and the codegen would be called with
149  * type `expression`, so the ast_ident's codegen would search for
150  * variables through the environment (or functions, constants...).
151  */
152 struct ast_expression_common
153 {
154     ast_node                node;
155     ast_expression_codegen *codegen;
156     int                     vtype;
157     ast_expression         *next;
158     /* arrays get a member-count */
159     size_t                  count;
160     ast_value*             *params;
161     ast_flag_t              flags;
162     /* void foo(string...) gets varparam set as a restriction
163      * for variadic parameters
164      */
165     ast_expression         *varparam;
166     /* The codegen functions should store their output values
167      * so we can call it multiple times without re-evaluating.
168      * Store lvalue and rvalue seperately though. So that
169      * ast_entfield for example can generate both if required.
170      */
171     ir_value               *outl;
172     ir_value               *outr;
173 };
174
175 /* Value
176  *
177  * Types are also values, both have a type and a name.
178  * especially considering possible constructs like typedefs.
179  * typedef float foo;
180  * is like creating a 'float foo', foo serving as the type's name.
181  */
182 typedef union {
183     qcfloat_t     vfloat;
184     int           vint;
185     vec3_t        vvec;
186     const char   *vstring;
187     int           ventity;
188     ast_function *vfunc;
189     ast_value    *vfield;
190 } basic_value_t;
191
192 struct ast_value_s
193 {
194     ast_expression        expression;
195
196     const char *name;
197     const char *desc;
198
199     const char *argcounter;
200
201     int  cvq;     /* const/var qualifier */
202     bool isfield; /* this declares a field */
203     bool isimm;   /* an immediate, not just const */
204     bool hasvalue;
205     basic_value_t constval;
206     /* for TYPE_ARRAY we have an optional vector
207      * of constants when an initializer list
208      * was provided.
209      */
210     basic_value_t *initlist;
211
212     /* usecount for the parser */
213     size_t uses;
214
215     ir_value *ir_v;
216     ir_value **ir_values;
217     size_t   ir_value_count;
218
219     /* ONLY for arrays in progs version up to 6 */
220     ast_value *setter;
221     ast_value *getter;
222
223
224     bool      intrinsic; /* true if associated with intrinsic */
225 };
226
227 ast_value* ast_value_new(lex_ctx_t ctx, const char *name, int qctype);
228 ast_value* ast_value_copy(const ast_value *self);
229 /* This will NOT delete an underlying ast_function */
230 void ast_value_delete(ast_value*);
231
232 bool ast_value_set_name(ast_value*, const char *name);
233
234 /*
235 bool ast_value_codegen(ast_value*, ast_function*, bool lvalue, ir_value**);
236 bool ast_local_codegen(ast_value *self, ir_function *func, bool isparam);
237 */
238
239 bool ast_global_codegen(ast_value *self, ir_builder *ir, bool isfield);
240
241 void ast_value_params_add(ast_value*, ast_value*);
242
243 bool ast_compare_type(ast_expression *a, ast_expression *b);
244 ast_expression* ast_type_copy(lex_ctx_t ctx, const ast_expression *ex);
245 #define ast_type_adopt(a, b) ast_type_adopt_impl((ast_expression*)(a), (ast_expression*)(b))
246 void ast_type_adopt_impl(ast_expression *self, const ast_expression *other);
247 void ast_type_to_string(ast_expression *e, char *buf, size_t bufsize);
248
249 typedef enum ast_binary_ref_s {
250     AST_REF_NONE  = 0,
251     AST_REF_LEFT  = 1 << 1,
252     AST_REF_RIGHT = 1 << 2,
253     AST_REF_ALL   = (AST_REF_LEFT | AST_REF_RIGHT)
254 } ast_binary_ref;
255
256
257 /* Binary
258  *
259  * A value-returning binary expression.
260  */
261 struct ast_binary_s
262 {
263     ast_expression        expression;
264
265     int             op;
266     ast_expression *left;
267     ast_expression *right;
268     ast_binary_ref  refs;
269     bool            right_first;
270 };
271 ast_binary* ast_binary_new(lex_ctx_t    ctx,
272                            int        op,
273                            ast_expression *left,
274                            ast_expression *right);
275
276 /* Binstore
277  *
278  * An assignment including a binary expression with the source as left operand.
279  * Eg. a += b; is a binstore { INSTR_STORE, INSTR_ADD, a, b }
280  */
281 struct ast_binstore_s
282 {
283     ast_expression        expression;
284
285     int             opstore;
286     int             opbin;
287     ast_expression *dest;
288     ast_expression *source;
289     /* for &~= which uses the destination in a binary in source we can use this */
290     bool            keep_dest;
291 };
292 ast_binstore* ast_binstore_new(lex_ctx_t    ctx,
293                                int        storeop,
294                                int        op,
295                                ast_expression *left,
296                                ast_expression *right);
297
298 /* Unary
299  *
300  * Regular unary expressions: not,neg
301  */
302 struct ast_unary_s
303 {
304     ast_expression        expression;
305
306     int             op;
307     ast_expression *operand;
308 };
309 ast_unary* ast_unary_new(lex_ctx_t    ctx,
310                          int        op,
311                          ast_expression *expr);
312
313 /* Return
314  *
315  * Make sure 'return' only happens at the end of a block, otherwise the IR
316  * will refuse to create further instructions.
317  * This should be honored by the parser.
318  */
319 struct ast_return_s
320 {
321     ast_expression        expression;
322     ast_expression *operand;
323 };
324 ast_return* ast_return_new(lex_ctx_t    ctx,
325                            ast_expression *expr);
326
327 /* Entity-field
328  *
329  * This must do 2 things:
330  * -) Provide a way to fetch an entity field value. (Rvalue)
331  * -) Provide a pointer to an entity field. (Lvalue)
332  * The problem:
333  * In original QC, there's only a STORE via pointer, but
334  * no LOAD via pointer.
335  * So we must know beforehand if we are going to read or assign
336  * the field.
337  * For this we will have to extend the codegen() functions with
338  * a flag saying whether or not we need an L or an R-value.
339  */
340 struct ast_entfield_s
341 {
342     ast_expression        expression;
343     /* The entity can come from an expression of course. */
344     ast_expression *entity;
345     /* As can the field, it just must result in a value of TYPE_FIELD */
346     ast_expression *field;
347 };
348 ast_entfield* ast_entfield_new(lex_ctx_t ctx, ast_expression *entity, ast_expression *field);
349 ast_entfield* ast_entfield_new_force(lex_ctx_t ctx, ast_expression *entity, ast_expression *field, const ast_expression *outtype);
350
351 /* Member access:
352  *
353  * For now used for vectors. If we get structs or unions
354  * we can have them handled here as well.
355  */
356 struct ast_member_s
357 {
358     ast_expression  expression;
359     ast_expression *owner;
360     unsigned int    field;
361     const char     *name;
362     bool            rvalue;
363 };
364 ast_member* ast_member_new(lex_ctx_t ctx, ast_expression *owner, unsigned int field, const char *name);
365 void ast_member_delete(ast_member*);
366 bool ast_member_set_name(ast_member*, const char *name);
367
368
369 /* Array index access:
370  *
371  * QC forces us to take special action on arrays:
372  * an ast_store on an ast_array_index must not codegen the index,
373  * but call its setter - unless we have an instruction set which supports
374  * what we need.
375  * Any other array index access will be codegened to a call to the getter.
376  * In any case, accessing an element via a compiletime-constant index will
377  * result in quick access to that variable.
378  */
379 struct ast_array_index_s
380 {
381     ast_expression  expression;
382     ast_expression *array;
383     ast_expression *index;
384 };
385 ast_array_index* ast_array_index_new(lex_ctx_t ctx, ast_expression *array, ast_expression *index);
386
387 /* Vararg pipe node:
388  *
389  * copy all varargs starting from a specific index
390  */
391 struct ast_argpipe_s
392 {
393     ast_expression  expression;
394     ast_expression *index;
395 };
396 ast_argpipe* ast_argpipe_new(lex_ctx_t ctx, ast_expression *index);
397
398 /* Store
399  *
400  * Stores left<-right and returns left.
401  * Specialized binary expression node
402  */
403 struct ast_store_s
404 {
405     ast_expression  expression;
406     int             op;
407     ast_expression *dest;
408     ast_expression *source;
409 };
410 ast_store* ast_store_new(lex_ctx_t ctx, int op,
411                          ast_expression *d, ast_expression *s);
412
413 /* If
414  *
415  * A general 'if then else' statement, either side can be NULL and will
416  * thus be omitted. It is an error for *both* cases to be NULL at once.
417  *
418  * During its 'codegen' it'll be changing the ast_function's block.
419  *
420  * An if is also an "expression". Its codegen will put NULL into the
421  * output field though. For ternary expressions an ast_ternary will be
422  * added.
423  */
424 struct ast_ifthen_s
425 {
426     ast_expression  expression;
427     ast_expression *cond;
428     /* It's all just 'expressions', since an ast_block is one too. */
429     ast_expression *on_true;
430     ast_expression *on_false;
431 };
432 ast_ifthen* ast_ifthen_new(lex_ctx_t ctx, ast_expression *cond, ast_expression *ontrue, ast_expression *onfalse);
433
434 /* Ternary expressions...
435  *
436  * Contrary to 'if-then-else' nodes, ternary expressions actually
437  * return a value, otherwise they behave the very same way.
438  * The difference in 'codegen' is that it'll return the value of
439  * a PHI node.
440  *
441  * The other difference is that in an ast_ternary, NEITHER side
442  * must be NULL, there's ALWAYS an else branch.
443  *
444  * This is the only ast_node beside ast_value which contains
445  * an ir_value. Theoretically we don't need to remember it though.
446  */
447 struct ast_ternary_s
448 {
449     ast_expression  expression;
450     ast_expression *cond;
451     /* It's all just 'expressions', since an ast_block is one too. */
452     ast_expression *on_true;
453     ast_expression *on_false;
454 };
455 ast_ternary* ast_ternary_new(lex_ctx_t ctx, ast_expression *cond, ast_expression *ontrue, ast_expression *onfalse);
456
457 /* A general loop node
458  *
459  * For convenience it contains 4 parts:
460  * -) (ini) = initializing expression
461  * -) (pre) = pre-loop condition
462  * -) (pst) = post-loop condition
463  * -) (inc) = "increment" expression
464  * The following is a psudo-representation of this loop
465  * note that '=>' bears the logical meaning of "implies".
466  * (a => b) equals (!a || b)
467
468 {ini};
469 while (has_pre => {pre})
470 {
471     {body};
472
473 continue:      // a 'continue' will jump here
474     if (has_pst => {pst})
475         break;
476
477     {inc};
478 }
479  */
480 struct ast_loop_s
481 {
482     ast_expression  expression;
483     ast_expression *initexpr;
484     ast_expression *precond;
485     ast_expression *postcond;
486     ast_expression *increment;
487     ast_expression *body;
488     /* For now we allow a seperate flag on whether or not the condition
489      * is supposed to be true or false.
490      * That way, the parser can generate a 'while not(!x)' for `while(x)`
491      * if desired, which is useful for the new -f{true,false}-empty-strings
492      * flag.
493      */
494     bool pre_not;
495     bool post_not;
496 };
497 ast_loop* ast_loop_new(lex_ctx_t ctx,
498                        ast_expression *initexpr,
499                        ast_expression *precond, bool pre_not,
500                        ast_expression *postcond, bool post_not,
501                        ast_expression *increment,
502                        ast_expression *body);
503
504 /* Break/Continue
505  */
506 struct ast_breakcont_s
507 {
508     ast_expression expression;
509     bool           is_continue;
510     unsigned int   levels;
511 };
512 ast_breakcont* ast_breakcont_new(lex_ctx_t ctx, bool iscont, unsigned int levels);
513
514 /* Switch Statements
515  *
516  * A few notes about this: with the original QCVM, no real optimization
517  * is possible. The SWITCH instruction set isn't really helping a lot, since
518  * it only collapes the EQ and IF instructions into one.
519  * Note: Declaring local variables inside caseblocks is normal.
520  * Since we don't have to deal with a stack there's no unnatural behaviour to
521  * be expected from it.
522  * TODO: Ticket #20
523  */
524 typedef struct {
525     ast_expression *value; /* #20 will replace this */
526     ast_expression *code;
527 } ast_switch_case;
528 struct ast_switch_s
529 {
530     ast_expression   expression;
531
532     ast_expression  *operand;
533     ast_switch_case *cases;
534 };
535
536 ast_switch* ast_switch_new(lex_ctx_t ctx, ast_expression *op);
537
538 /* Label nodes
539  *
540  * Introduce a label which can be used together with 'goto'
541  */
542 struct ast_label_s
543 {
544     ast_expression  expression;
545     const char     *name;
546     ir_block       *irblock;
547     ast_goto      **gotos;
548
549     /* means it has not yet been defined */
550     bool           undefined;
551 };
552
553 ast_label* ast_label_new(lex_ctx_t ctx, const char *name, bool undefined);
554
555 /* GOTO nodes
556  *
557  * Go to a label, the label node is filled in at a later point!
558  */
559 struct ast_goto_s
560 {
561     ast_expression expression;
562     const char    *name;
563     ast_label     *target;
564     ir_block      *irblock_from;
565 };
566
567 ast_goto* ast_goto_new(lex_ctx_t ctx, const char *name);
568 void ast_goto_set_label(ast_goto*, ast_label*);
569
570 /* CALL node
571  *
572  * Contains an ast_expression as target, rather than an ast_function/value.
573  * Since it's how QC works, every ast_function has an ast_value
574  * associated anyway - in other words, the VM contains function
575  * pointers for every function anyway. Thus, this node will call
576  * expression.
577  * Additionally it contains a list of ast_expressions as parameters.
578  * Since calls can return values, an ast_call is also an ast_expression.
579  */
580 struct ast_call_s
581 {
582     ast_expression  expression;
583     ast_expression *func;
584     ast_expression **params;
585     ast_expression *va_count;
586 };
587 ast_call* ast_call_new(lex_ctx_t ctx,
588                        ast_expression *funcexpr);
589 bool ast_call_check_types(ast_call*, ast_expression *this_func_va_type);
590
591 /* Blocks
592  *
593  */
594 struct ast_block_s
595 {
596     ast_expression   expression;
597
598     ast_value*      *locals;
599     ast_expression* *exprs;
600     ast_expression* *collect;
601 };
602 ast_block* ast_block_new(lex_ctx_t ctx);
603 void ast_block_delete(ast_block*);
604 void ast_block_set_type(ast_block*, ast_expression *from);
605 void ast_block_collect(ast_block*, ast_expression*);
606
607 bool GMQCC_WARN ast_block_add_expr(ast_block*, ast_expression*);
608
609 /* Function
610  *
611  * Contains a list of blocks... at least in theory.
612  * Usually there's just the main block, other blocks are inside that.
613  *
614  * Technically, functions don't need to be an AST node, since we have
615  * neither functions inside functions, nor lambdas, and function
616  * pointers could just work with a name. However, this way could be
617  * more flexible, and adds no real complexity.
618  */
619 struct ast_function_s
620 {
621     ast_node    node;
622
623     ast_value  *vtype;
624     const char *name;
625
626     int builtin;
627
628     /* list of used-up names for statics without the count suffix */
629     char       **static_names;
630     /* number of static variables, by convention this includes the
631      * ones without the count-suffix - remember this when dealing
632      * with savegames. uint instead of size_t as %zu in printf is
633      * C99, so no windows support. */
634     unsigned int static_count;
635
636     ir_function *ir_func;
637     ir_block    *curblock;
638     ir_block    **breakblocks;
639     ir_block    **continueblocks;
640
641 #if 0
642     /* In order for early-out logic not to go over
643      * excessive jumps, we remember their target
644      * blocks...
645      */
646     ir_block    *iftrue;
647     ir_block    *iffalse;
648 #endif
649
650     size_t       labelcount;
651     /* in order for thread safety - for the optional
652      * channel abesed multithreading... keeping a buffer
653      * here to use in ast_function_label.
654      */
655     char         labelbuf[64];
656
657     ast_block* *blocks;
658
659     ast_value   *varargs;
660     ast_value   *argc;
661     ast_value   *fixedparams;
662     ast_value   *return_value;
663 };
664 ast_function* ast_function_new(lex_ctx_t ctx, const char *name, ast_value *vtype);
665 /* This will NOT delete the underlying ast_value */
666 void ast_function_delete(ast_function*);
667 /* For "optimized" builds this can just keep returning "foo"...
668  * or whatever...
669  */
670 const char* ast_function_label(ast_function*, const char *prefix);
671
672 bool ast_function_codegen(ast_function *self, ir_builder *builder);
673 bool ast_generate_accessors(ast_value *asvalue, ir_builder *ir);
674
675 /*
676  * If the condition creates a situation where this becomes -1 size it means there are
677  * more AST_FLAGs than the type ast_flag_t is capable of holding. So either eliminate
678  * the AST flag count or change the ast_flag_t typedef to a type large enough to accomodate
679  * all the flags.
680  */
681 typedef int static_assert_is_ast_flag_safe [((AST_FLAG_LAST) <= (ast_flag_t)(-1)) ? 1 : -1];
682 #endif