1 // 2 // gravity_ast.h 3 // gravity 4 // 5 // Created by Marco Bambini on 02/09/14. 6 // Copyright (c) 2014 CreoLabs. All rights reserved. 7 // 8 9 #ifndef __GRAVITY_AST__ 10 #define __GRAVITY_AST__ 11 12 #include "debug_macros.h" 13 #include "gravity_array.h" 14 #include "gravity_token.h" 15 16 /* 17 AST can be uniform (the same data struct is used for all expressions/statements/declarations) or 18 non-uniform. I choosed a non-uniform AST node implementation with a common base struct. 19 It requires more work but design and usage is much more cleaner and we benefit from static check. 20 */ 21 22 typedef enum { 23 // statements: 7 24 NODE_LIST_STAT, NODE_COMPOUND_STAT, NODE_LABEL_STAT, NODE_FLOW_STAT, NODE_JUMP_STAT, NODE_LOOP_STAT, NODE_EMPTY_STAT, 25 26 // declarations: 6 27 NODE_ENUM_DECL, NODE_FUNCTION_DECL, NODE_VARIABLE_DECL, NODE_CLASS_DECL, NODE_MODULE_DECL, NODE_VARIABLE, 28 29 // expressions: 8 30 NODE_BINARY_EXPR, NODE_UNARY_EXPR, NODE_FILE_EXPR, NODE_LIST_EXPR, NODE_LITERAL_EXPR, NODE_IDENTIFIER_EXPR, 31 NODE_POSTFIX_EXPR, NODE_KEYWORD_EXPR, 32 33 // postfix subexpression type 34 NODE_CALL_EXPR, NODE_SUBSCRIPT_EXPR, NODE_ACCESS_EXPR 35 } gnode_n; 36 37 typedef enum { 38 LOCATION_LOCAL, 39 LOCATION_GLOBAL, 40 LOCATION_UPVALUE, 41 LOCATION_CLASS_IVAR_SAME, 42 LOCATION_CLASS_IVAR_OUTER 43 } gnode_location_type; 44 45 // BASE NODE 46 typedef struct { 47 gnode_n tag; // node type from gnode_n enum 48 uint32_t refcount; // reference count to manage duplicated nodes 49 uint32_t block_length; // total length in bytes of the block (used in autocompletion) 50 gtoken_s token; // token type and location 51 bool is_assignment; // flag to check if it is an assignment node 52 void *decl; // enclosing declaration node 53 } gnode_t; 54 55 // UPVALUE STRUCT 56 typedef struct { 57 gnode_t *node; // reference to the original var node 58 uint32_t index; // can be an index in the stack or in the upvalue list (depending on the is_direct flag) 59 uint32_t selfindex; // always index inside uplist 60 bool is_direct; // flag to check if var is local to the direct enclosing func 61 } gupvalue_t; 62 63 // shortcut for array of common structs 64 typedef marray_t(gnode_t *) gnode_r; 65 typedef marray_t(gupvalue_t *) gupvalue_r; 66 67 #ifndef GRAVITY_SYMBOLTABLE_DEFINED 68 #define GRAVITY_SYMBOLTABLE_DEFINED 69 typedef struct symboltable_t symboltable_t; 70 #endif 71 72 // LOCATION 73 typedef struct { 74 gnode_location_type type; // location type 75 uint16_t index; // symbol index 76 uint16_t nup; // upvalue index or outer index 77 } gnode_location_t; 78 79 // STATEMENTS 80 typedef struct { 81 gnode_t base; // NODE_LIST_STAT | NODE_COMPOUND_STAT 82 symboltable_t *symtable; // node internal symbol table 83 gnode_r *stmts; // array of statements node 84 uint32_t nclose; // initialized to UINT32_MAX 85 } gnode_compound_stmt_t; 86 typedef gnode_compound_stmt_t gnode_list_stmt_t; 87 88 typedef struct { 89 gnode_t base; // CASE or DEFAULT 90 gnode_t *expr; // expression in case of CASE 91 gnode_t *stmt; // common statement 92 uint32_t label_case; // for switch to jump 93 } gnode_label_stmt_t; 94 95 typedef struct { 96 gnode_t base; // IF, SWITCH, TOK_OP_TERNARY 97 gnode_t *cond; // common condition (it's an expression) 98 gnode_t *stmt; // common statement 99 gnode_t *elsestmt; // optional else statement in case of IF 100 } gnode_flow_stmt_t; 101 102 typedef struct { 103 gnode_t base; // WHILE, REPEAT or FOR 104 gnode_t *cond; // used in WHILE and FOR 105 gnode_t *stmt; // common statement 106 gnode_t *expr; // used in REPEAT and FOR 107 uint32_t nclose; // initialized to UINT32_MAX 108 } gnode_loop_stmt_t; 109 110 typedef struct { 111 gnode_t base; // BREAK, CONTINUE or RETURN 112 gnode_t *expr; // optional expression in case of RETURN 113 } gnode_jump_stmt_t; 114 115 // DECLARATIONS 116 typedef struct { 117 gnode_t base; // FUNCTION_DECL or FUNCTION_EXPR 118 gnode_t *env; // shortcut to node where function is declared 119 gtoken_t access; // TOK_KEY_PRIVATE | TOK_KEY_INTERNAL | TOK_KEY_PUBLIC 120 gtoken_t storage; // TOK_KEY_STATIC | TOK_KEY_EXTERN 121 symboltable_t *symtable; // function internal symbol table 122 const char *identifier; // function name 123 gnode_r *params; // function params 124 gnode_compound_stmt_t *block; // internal function statements 125 uint16_t nlocals; // locals counter 126 uint16_t nparams; // formal parameters counter 127 bool has_defaults; // flag set if parmas has default values 128 bool is_closure; // flag to check if function is a closure 129 gupvalue_r *uplist; // list of upvalues used in function (can be empty) 130 } gnode_function_decl_t; 131 typedef gnode_function_decl_t gnode_function_expr_t; 132 133 typedef struct { 134 gnode_t base; // VARIABLE_DECL 135 gtoken_t type; // TOK_KEY_VAR | TOK_KEY_CONST 136 gtoken_t access; // TOK_KEY_PRIVATE | TOK_KEY_INTERNAL | TOK_KEY_PUBLIC 137 gtoken_t storage; // TOK_KEY_STATIC | TOK_KEY_EXTERN 138 gnode_r *decls; // variable declarations list (gnode_var_t) 139 } gnode_variable_decl_t; 140 141 typedef struct { 142 gnode_t base; // VARIABLE 143 gnode_t *env; // shortcut to node where variable is declared 144 const char *identifier; // variable name 145 const char *annotation_type; // optional annotation type 146 gnode_t *expr; // optional assignment expression/declaration 147 gtoken_t access; // optional access token (duplicated value from its gnode_variable_decl_t) 148 uint16_t index; // local variable index (if local) 149 bool upvalue; // flag set if this variable is used as an upvalue 150 bool iscomputed; // flag set is variable must not be backed 151 gnode_variable_decl_t *vdecl; // reference to enclosing variable declaration (in order to be able to have access to storage and access fields) 152 } gnode_var_t; 153 154 typedef struct { 155 gnode_t base; // ENUM_DECL 156 gnode_t *env; // shortcut to node where enum is declared 157 gtoken_t access; // TOK_KEY_PRIVATE | TOK_KEY_INTERNAL | TOK_KEY_PUBLIC 158 gtoken_t storage; // TOK_KEY_STATIC | TOK_KEY_EXTERN 159 symboltable_t *symtable; // enum internal hash table 160 const char *identifier; // enum name 161 } gnode_enum_decl_t; 162 163 typedef struct { 164 gnode_t base; // CLASS_DECL 165 bool bridge; // flag to check of a bridged class 166 bool is_struct; // flag to mark the class as a struct 167 gnode_t *env; // shortcut to node where class is declared 168 gtoken_t access; // TOK_KEY_PRIVATE | TOK_KEY_INTERNAL | TOK_KEY_PUBLIC 169 gtoken_t storage; // TOK_KEY_STATIC | TOK_KEY_EXTERN 170 const char *identifier; // class name 171 gnode_t *superclass; // super class ptr 172 bool super_extern; // flag set when a superclass is declared as extern 173 gnode_r *protocols; // array of protocols (currently unused) 174 gnode_r *decls; // class declarations list 175 symboltable_t *symtable; // class internal symbol table 176 void *data; // used to keep track of super classes 177 uint32_t nivar; // instance variables counter 178 uint32_t nsvar; // static variables counter 179 } gnode_class_decl_t; 180 181 typedef struct { 182 gnode_t base; // MODULE_DECL 183 gnode_t *env; // shortcut to node where module is declared 184 gtoken_t access; // TOK_KEY_PRIVATE | TOK_KEY_INTERNAL | TOK_KEY_PUBLIC 185 gtoken_t storage; // TOK_KEY_STATIC | TOK_KEY_EXTERN 186 const char *identifier; // module name 187 gnode_r *decls; // module declarations list 188 symboltable_t *symtable; // module internal symbol table 189 } gnode_module_decl_t; 190 191 // EXPRESSIONS 192 typedef struct { 193 gnode_t base; // BINARY_EXPR 194 gtoken_t op; // operation 195 gnode_t *left; // left node 196 gnode_t *right; // right node 197 } gnode_binary_expr_t; 198 199 typedef struct { 200 gnode_t base; // UNARY_EXPR 201 gtoken_t op; // operation 202 gnode_t *expr; // node 203 } gnode_unary_expr_t; 204 205 typedef struct { 206 gnode_t base; // FILE 207 cstring_r *identifiers; // identifier name 208 gnode_location_t location; // identifier location 209 } gnode_file_expr_t; 210 211 typedef struct { 212 gnode_t base; // LITERAL 213 gliteral_t type; // LITERAL_STRING, LITERAL_FLOAT, LITERAL_INT, LITERAL_BOOL, LITERAL_INTERPOLATION 214 uint32_t len; // used only for TYPE_STRING 215 union { 216 char *str; // LITERAL_STRING 217 double d; // LITERAL_FLOAT 218 int64_t n64; // LITERAL_INT or LITERAL_BOOL 219 gnode_r *r; // LITERAL_STRING_INTERPOLATED 220 } value; 221 } gnode_literal_expr_t; 222 223 typedef struct { 224 gnode_t base; // IDENTIFIER or ID 225 const char *value; // identifier name 226 const char *value2; // NULL for IDENTIFIER (check if just one value or an array) 227 gnode_t *symbol; // pointer to identifier declaration (if any) 228 gnode_location_t location; // location coordinates 229 gupvalue_t *upvalue; // upvalue location reference 230 } gnode_identifier_expr_t; 231 232 typedef struct { 233 gnode_t base; // KEYWORD token 234 } gnode_keyword_expr_t; 235 236 typedef gnode_keyword_expr_t gnode_empty_stmt_t; 237 typedef gnode_keyword_expr_t gnode_base_t; 238 239 typedef struct { 240 gnode_t base; // NODE_CALLFUNC_EXPR, NODE_SUBSCRIPT_EXPR, NODE_ACCESS_EXPR 241 gnode_t *id; // id(...) or id[...] or id. 242 gnode_r *list; // list of postfix_subexpr 243 } gnode_postfix_expr_t; 244 245 typedef struct { 246 gnode_t base; // NODE_CALLFUNC_EXPR, NODE_SUBSCRIPT_EXPR, NODE_ACCESS_EXPR 247 union { 248 gnode_t *expr; // used in case of NODE_SUBSCRIPT_EXPR or NODE_ACCESS_EXPR 249 gnode_r *args; // used in case of NODE_CALLFUNC_EXPR 250 }; 251 } gnode_postfix_subexpr_t; 252 253 typedef struct { 254 gnode_t base; // LIST_EXPR 255 bool ismap; // flag to check if the node represents a map (otherwise it is a list) 256 gnode_r *list1; // node items (cannot use a symtable here because order is mandatory in array) 257 gnode_r *list2; // used only in case of map 258 } gnode_list_expr_t; 259 260 gnode_t *gnode_block_stat_create (gnode_n type, gtoken_s token, gnode_r *stmts, gnode_t *decl, uint32_t block_length); 261 gnode_t *gnode_empty_stat_create (gtoken_s token, gnode_t *decl); 262 gnode_t *gnode_flow_stat_create (gtoken_s token, gnode_t *cond, gnode_t *stmt1, gnode_t *stmt2, gnode_t *decl, uint32_t block_length); 263 gnode_t *gnode_jump_stat_create (gtoken_s token, gnode_t *expr, gnode_t *decl); 264 gnode_t *gnode_label_stat_create (gtoken_s token, gnode_t *expr, gnode_t *stmt, gnode_t *decl); 265 gnode_t *gnode_loop_stat_create (gtoken_s token, gnode_t *cond, gnode_t *stmt, gnode_t *expr, gnode_t *decl, uint32_t block_length); 266 267 gnode_t *gnode_class_decl_create (gtoken_s token, const char *identifier, gtoken_t access_specifier, gtoken_t storage_specifier, gnode_t *superclass, gnode_r *protocols, gnode_r *declarations, bool is_struct, gnode_t *decl); 268 gnode_t *gnode_enum_decl_create (gtoken_s token, const char *identifier, gtoken_t access_specifier, gtoken_t storage_specifier, symboltable_t *symtable, gnode_t *decl); 269 gnode_t *gnode_module_decl_create (gtoken_s token, const char *identifier, gtoken_t access_specifier, gtoken_t storage_specifier, gnode_r *declarations, gnode_t *decl); 270 gnode_t *gnode_variable_create (gtoken_s token, const char *identifier, const char *annotation_type, gnode_t *expr, gnode_t *decl, gnode_variable_decl_t *vdecl); 271 gnode_t *gnode_variable_decl_create (gtoken_s token, gtoken_t type, gtoken_t access_specifier, gtoken_t storage_specifier, gnode_r *declarations, gnode_t *decl); 272 273 gnode_t *gnode_function_decl_create (gtoken_s token, const char *identifier, gtoken_t access_specifier, gtoken_t storage_specifier, gnode_r *params, gnode_compound_stmt_t *block, gnode_t *decl); 274 275 gnode_t *gnode_binary_expr_create (gtoken_t op, gnode_t *left, gnode_t *right, gnode_t *decl); 276 gnode_t *gnode_file_expr_create (gtoken_s token, cstring_r *list, gnode_t *decl); 277 gnode_t *gnode_identifier_expr_create (gtoken_s token, const char *identifier, const char *identifier2, gnode_t *decl); 278 gnode_t *gnode_keyword_expr_create (gtoken_s token, gnode_t *decl); 279 gnode_t *gnode_list_expr_create (gtoken_s token, gnode_r *list1, gnode_r *list2, bool ismap, gnode_t *decl); 280 gnode_t *gnode_literal_bool_expr_create (gtoken_s token, int32_t n, gnode_t *decl); 281 gnode_t *gnode_literal_float_expr_create (gtoken_s token, double f, gnode_t *decl); 282 gnode_t *gnode_literal_int_expr_create (gtoken_s token, int64_t n, gnode_t *decl); 283 gnode_t *gnode_literal_string_expr_create (gtoken_s token, char *s, uint32_t len, bool allocated, gnode_t *decl); 284 gnode_t *gnode_postfix_expr_create (gtoken_s token, gnode_t *id, gnode_r *list, gnode_t *decl); 285 gnode_t *gnode_postfix_subexpr_create (gtoken_s token, gnode_n type, gnode_t *expr, gnode_r *list, gnode_t *decl); 286 gnode_t *gnode_string_interpolation_create (gtoken_s token, gnode_r *r, gnode_t *decl); 287 gnode_t *gnode_unary_expr_create (gtoken_t op, gnode_t *expr, gnode_t *decl); 288 289 gnode_t *gnode_duplicate (gnode_t *node, bool deep); 290 const char *gnode_identifier (gnode_t *node); 291 292 gnode_r *gnode_array_create (void); 293 gnode_r *gnode_array_remove_byindex(gnode_r *list, size_t index); 294 void gnode_array_sethead(gnode_r *list, gnode_t *node); 295 gupvalue_t *gnode_function_add_upvalue(gnode_function_decl_t *f, gnode_var_t *symbol, uint16_t n); 296 gnode_t *gnode2class (gnode_t *node, bool *isextern); 297 cstring_r *cstring_array_create (void); 298 void_r *void_array_create (void); 299 300 void gnode_free (gnode_t *node); 301 bool gnode_is_equal (gnode_t *node1, gnode_t *node2); 302 bool gnode_is_expression (gnode_t *node); 303 bool gnode_is_literal (gnode_t *node); 304 bool gnode_is_literal_int (gnode_t *node); 305 bool gnode_is_literal_number (gnode_t *node); 306 bool gnode_is_literal_string (gnode_t *node); 307 void gnode_literal_dump (gnode_literal_expr_t *node, char *buffer, int buffersize); 308 309 // MARK: - 310 311 #define gnode_array_init(r) marray_init(*r) 312 #define gnode_array_size(r) ((r) ? marray_size(*r) : 0) 313 #define gnode_array_push(r, node) marray_push(gnode_t*,*r,node) 314 #define gnode_array_pop(r) (marray_size(*r) ? marray_pop(*r) : NULL) 315 #define gnode_array_get(r, i) (((i) >= 0 && (i) < marray_size(*r)) ? marray_get(*r, (i)) : NULL) 316 #define gnode_array_free(r) do {marray_destroy(*r); mem_free((void*)r);} while (0) 317 #define gtype_array_each(r, block, type) { size_t _len = gnode_array_size(r); \ 318 for (size_t _i=0; _i<_len; ++_i) { \ 319 type val = (type)gnode_array_get(r, _i); \ 320 block;} \ 321 } 322 #define gnode_array_each(r, block) gtype_array_each(r, block, gnode_t*) 323 #define gnode_array_eachbase(r, block) gtype_array_each(r, block, gnode_base_t*) 324 325 #define cstring_array_free(r) marray_destroy(*r) 326 #define cstring_array_push(r, s) marray_push(const char*,*r,s) 327 #define cstring_array_each(r, block) gtype_array_each(r, block, const char*) 328 329 #define NODE_TOKEN_TYPE(_node) _node->base.token.type 330 #define NODE_TAG(_node) ((gnode_base_t *)_node)->base.tag 331 #define NODE_ISA(_node,_tag) ((_node) && NODE_TAG(_node) == _tag) 332 #define NODE_ISA_FUNCTION(_node) (NODE_ISA(_node, NODE_FUNCTION_DECL)) 333 #define NODE_ISA_CLASS(_node) (NODE_ISA(_node, NODE_CLASS_DECL)) 334 335 #define NODE_SET_ENCLOSING(_node,_enc) (((gnode_base_t *)_node)->base.enclosing = _enc) 336 #define NODE_GET_ENCLOSING(_node) ((gnode_base_t *)_node)->base.enclosing 337 338 #endif 339