10 data_type_t *ast_data_table[AST_DATA_COUNT] = {
11 &(data_type_t) { TYPE_VOID, 0, true }, /* void */
12 &(data_type_t) { TYPE_BOOL, ARCH_TYPE_SIZE_INT, false}, /* _Bool */
13 &(data_type_t) { TYPE_LONG, ARCH_TYPE_SIZE_LONG, true }, /* long */
14 &(data_type_t) { TYPE_LLONG, ARCH_TYPE_SIZE_LLONG, true }, /* long long */
15 &(data_type_t) { TYPE_INT, ARCH_TYPE_SIZE_INT, true }, /* int */
16 &(data_type_t) { TYPE_SHORT, ARCH_TYPE_SIZE_SHORT, true }, /* short */
17 &(data_type_t) { TYPE_CHAR, ARCH_TYPE_SIZE_CHAR, true }, /* char */
18 &(data_type_t) { TYPE_FLOAT, ARCH_TYPE_SIZE_FLOAT, true }, /* float */
19 &(data_type_t) { TYPE_DOUBLE, ARCH_TYPE_SIZE_DOUBLE, true }, /* double */
20 &(data_type_t) { TYPE_LDOUBLE, ARCH_TYPE_SIZE_LDOUBLE, true }, /* long double */
21 &(data_type_t) { TYPE_LONG, ARCH_TYPE_SIZE_LONG, false }, /* unsigned long */
22 &(data_type_t) { TYPE_LLONG, ARCH_TYPE_SIZE_LLONG, false }, /* unsigned long long */
26 data_type_t *ast_data_function = NULL;
27 list_t *ast_locals = NULL;
28 list_t *ast_gotos = NULL;
29 table_t *ast_labels = NULL;
30 table_t *ast_globalenv = &SENTINEL_TABLE;
31 table_t *ast_localenv = &SENTINEL_TABLE;
32 table_t *ast_structures = &SENTINEL_TABLE;
33 table_t *ast_unions = &SENTINEL_TABLE;
35 bool ast_struct_compare(data_type_t *a, data_type_t *b) {
38 list_iterator_t *lait;
39 list_iterator_t *lbit;
41 if (a->type != b->type)
46 if (a->length == b->length)
47 return ast_struct_compare(a->pointer, b->pointer);
51 return ast_struct_compare(a->pointer, b->pointer);
54 if (a->isstruct != b->isstruct)
57 la = table_keys(a->fields);
58 lb = table_keys(b->fields);
60 if (list_length(la) != list_length(lb))
63 lait = list_iterator(la);
64 lbit = list_iterator(lb);
66 while (!list_iterator_end(lait))
67 if (!ast_struct_compare(list_iterator_next(lait), list_iterator_next(lbit)))
76 data_type_t *ast_result_type(int operation, data_type_t *type) {
84 return ast_data_table[AST_DATA_INT];
86 return conv_senority(type, type);
90 ast_t *ast_copy(ast_t *ast) {
91 ast_t *copy = memory_allocate(sizeof(ast_t));
96 ast_t *ast_structure_reference(data_type_t *type, ast_t *structure, char *name) {
97 return ast_copy(&(ast_t) {
98 .type = AST_TYPE_STRUCT,
100 .structure = structure,
105 ast_t *ast_new_unary(int type, data_type_t *data, ast_t *operand) {
106 return ast_copy(&(ast_t) {
109 .unary.operand = operand
113 ast_t *ast_new_binary(data_type_t *ctype, int type, ast_t *left, ast_t *right) {
114 ast_t *ast = ast_copy(&(ast_t){
123 ast_t *ast_new_integer(data_type_t *type, int value) {
124 return ast_copy(&(ast_t) {
125 .type = AST_TYPE_LITERAL,
131 ast_t *ast_new_floating(data_type_t *type, double value) {
132 return ast_copy(&(ast_t){
133 .type = AST_TYPE_LITERAL,
135 .floating.value = value,
136 .floating.label = NULL
140 ast_t *ast_new_string(char *value) {
141 return ast_copy(&(ast_t) {
142 .type = AST_TYPE_STRING,
143 .ctype = ast_array(ast_data_table[AST_DATA_CHAR], strlen(value) + 1),
144 .string.data = value,
149 ast_t *ast_variable_local(data_type_t *type, char *name) {
150 ast_t *ast = ast_copy(&(ast_t){
151 .type = AST_TYPE_VAR_LOCAL,
153 .variable.name = name
156 table_insert(ast_localenv, name, ast);
158 list_push(ast_locals, ast);
162 ast_t *ast_variable_global(data_type_t *type, char *name) {
163 ast_t *ast = ast_copy(&(ast_t){
164 .type = AST_TYPE_VAR_GLOBAL,
166 .variable.name = name,
167 .variable.label = name
169 table_insert(ast_globalenv, name, ast);
173 ast_t *ast_function(data_type_t *ret, char *name, list_t *params, ast_t *body, list_t *locals) {
174 return ast_copy(&(ast_t) {
175 .type = AST_TYPE_FUNCTION,
177 .function.name = name,
178 .function.params = params,
179 .function.locals = locals,
180 .function.body = body
184 ast_t *ast_designator(char *name, ast_t *func) {
185 return ast_copy(&(ast_t){
186 .type = AST_TYPE_DESIGNATOR,
187 .ctype = ast_data_table[AST_DATA_VOID],
188 .function.name = name,
189 .function.call.functionpointer = func
193 ast_t *ast_pointercall(ast_t *functionpointer, list_t *args) {
194 return ast_copy(&(ast_t) {
195 .type = AST_TYPE_POINTERCALL,
196 .ctype = functionpointer->ctype->pointer->returntype,
197 .function.call.functionpointer = functionpointer,
198 .function.call.args = args
202 ast_t *ast_call(data_type_t *type, char *name, list_t *arguments) {
203 return ast_copy(&(ast_t) {
204 .type = AST_TYPE_CALL,
205 .ctype = type->returntype,
206 .function.call.args = arguments,
207 .function.call.type = type,
208 .function.name = name,
212 ast_t *ast_va_start(ast_t *ap) {
213 return ast_copy(&(ast_t){
214 .type = AST_TYPE_VA_START,
215 .ctype = ast_data_table[AST_DATA_VOID],
220 ast_t *ast_va_arg(data_type_t *type, ast_t *ap) {
221 return ast_copy(&(ast_t){
222 .type = AST_TYPE_VA_ARG,
228 ast_t *ast_declaration(ast_t *var, list_t *init) {
229 return ast_copy(&(ast_t) {
230 .type = AST_TYPE_DECLARATION,
237 ast_t *ast_initializer(ast_t *value, data_type_t *to, int offset) {
238 return ast_copy(&(ast_t){
239 .type = AST_TYPE_INITIALIZER,
241 .init.offset = offset,
246 ast_t *ast_ternary(data_type_t *type, ast_t *cond, ast_t *then, ast_t *last) {
247 return ast_copy(&(ast_t){
248 .type = AST_TYPE_EXPRESSION_TERNARY,
256 static ast_t *ast_for_intermediate(int type, ast_t *init, ast_t *cond, ast_t *step, ast_t *body) {
257 return ast_copy(&(ast_t){
260 .forstmt.init = init,
261 .forstmt.cond = cond,
262 .forstmt.step = step,
267 ast_t *ast_switch(ast_t *expr, ast_t *body) {
268 return ast_copy(&(ast_t){
269 .type = AST_TYPE_STATEMENT_SWITCH,
270 .switchstmt.expr = expr,
271 .switchstmt.body = body
275 ast_t *ast_case(int begin, int end) {
276 return ast_copy(&(ast_t){
277 .type = AST_TYPE_STATEMENT_CASE,
283 ast_t *ast_make(int type) {
284 return ast_copy(&(ast_t){
289 ast_t *ast_if(ast_t *cond, ast_t *then, ast_t *last) {
290 return ast_copy(&(ast_t){
291 .type = AST_TYPE_STATEMENT_IF,
299 ast_t *ast_for(ast_t *init, ast_t *cond, ast_t *step, ast_t *body) {
300 return ast_for_intermediate(AST_TYPE_STATEMENT_FOR, init, cond, step, body);
302 ast_t *ast_while(ast_t *cond, ast_t *body) {
303 return ast_for_intermediate(AST_TYPE_STATEMENT_WHILE, NULL, cond, NULL, body);
305 ast_t *ast_do(ast_t *cond, ast_t *body) {
306 return ast_for_intermediate(AST_TYPE_STATEMENT_DO, NULL, cond, NULL, body);
309 ast_t *ast_goto(char *label) {
310 return ast_copy(&(ast_t){
311 .type = AST_TYPE_STATEMENT_GOTO,
312 .gotostmt.label = label,
313 .gotostmt.where = NULL
317 ast_t *ast_new_label(char *label) {
318 return ast_copy(&(ast_t){
319 .type = AST_TYPE_STATEMENT_LABEL,
320 .gotostmt.label = label,
321 .gotostmt.where = NULL
325 ast_t *ast_return(ast_t *value) {
326 return ast_copy(&(ast_t){
327 .type = AST_TYPE_STATEMENT_RETURN,
332 ast_t *ast_compound(list_t *statements) {
333 return ast_copy(&(ast_t){
334 .type = AST_TYPE_STATEMENT_COMPOUND,
336 .compound = statements
340 data_type_t *ast_structure_new(table_t *fields, int size, bool isstruct) {
341 return ast_type_copy(&(data_type_t) {
342 .type = TYPE_STRUCTURE,
349 char *ast_label(void) {
350 static int index = 0;
351 string_t *string = string_create();
352 string_catf(string, ".L%d", index++);
353 return string_buffer(string);
356 ast_t *ast_label_address(char *label) {
357 return ast_copy(&(ast_t){
358 .type = AST_TYPE_STATEMENT_LABEL_COMPUTED,
359 .ctype = ast_pointer(ast_data_table[AST_DATA_VOID]),
360 .gotostmt.label = label
364 ast_t *ast_goto_computed(ast_t *expression) {
365 return ast_copy(&(ast_t){
366 .type = AST_TYPE_STATEMENT_GOTO_COMPUTED,
367 .unary.operand = expression
371 bool ast_type_isinteger(data_type_t *type) {
372 switch (type->type) {
385 bool ast_type_isfloating(data_type_t *type) {
386 switch (type->type) {
396 bool ast_type_isstring(data_type_t *type) {
397 return type->type == TYPE_ARRAY && type->pointer->type == TYPE_CHAR;
400 data_type_t *ast_type_copy(data_type_t *type) {
401 return memcpy(memory_allocate(sizeof(data_type_t)), type, sizeof(data_type_t));
404 data_type_t *ast_type_copy_incomplete(data_type_t *type) {
407 return (type->length == -1)
408 ? ast_type_copy(type)
412 data_type_t *ast_type_create(type_t type, bool sign) {
414 data_type_t *t = memory_allocate(sizeof(data_type_t));
420 case TYPE_VOID: t->size = 0; break;
421 case TYPE_BOOL: t->size = ARCH_TYPE_SIZE_INT; break;
422 case TYPE_CHAR: t->size = ARCH_TYPE_SIZE_CHAR; break;
423 case TYPE_SHORT: t->size = ARCH_TYPE_SIZE_SHORT; break;
424 case TYPE_INT: t->size = ARCH_TYPE_SIZE_INT; break;
425 case TYPE_LONG: t->size = ARCH_TYPE_SIZE_LONG; break;
426 case TYPE_LLONG: t->size = ARCH_TYPE_SIZE_LLONG; break;
427 case TYPE_FLOAT: t->size = ARCH_TYPE_SIZE_FLOAT; break;
428 case TYPE_DOUBLE: t->size = ARCH_TYPE_SIZE_DOUBLE; break;
429 case TYPE_LDOUBLE: t->size = ARCH_TYPE_SIZE_LDOUBLE; break;
431 compile_error("ICE");
437 data_type_t *ast_type_stub(void) {
438 return ast_type_copy(&(data_type_t) {
444 ast_t *ast_type_convert(data_type_t *type, ast_t *ast) {
445 return ast_copy(&(ast_t){
446 .type = AST_TYPE_CONVERT,
452 data_type_t *ast_prototype(data_type_t *returntype, list_t *paramtypes, bool dots) {
453 return ast_type_copy(&(data_type_t){
454 .type = TYPE_FUNCTION,
455 .returntype = returntype,
456 .parameters = paramtypes,
461 data_type_t *ast_array(data_type_t *type, int length) {
462 return ast_type_copy(&(data_type_t){
465 .size = (length < 0) ? -1 : type->size * length,
470 data_type_t *ast_array_convert(data_type_t *type) {
471 if (type->type != TYPE_ARRAY)
473 return ast_pointer(type->pointer);
476 ast_t *ast_designator_convert(ast_t *ast) {
479 if (ast->type == AST_TYPE_DESIGNATOR) {
480 return ast_new_unary(
482 ast_pointer(ast->function.call.functionpointer->function.call.type),
483 ast->function.call.functionpointer
490 data_type_t *ast_pointer(data_type_t *type) {
491 return ast_type_copy(&(data_type_t){
492 .type = TYPE_POINTER,
494 .size = ARCH_TYPE_SIZE_POINTER
498 const char *ast_type_string(data_type_t *type) {
501 switch (type->type) {
502 case TYPE_VOID: return "void";
503 case TYPE_BOOL: return "_Bool";
504 case TYPE_INT: return "int";
505 case TYPE_CHAR: return "char";
506 case TYPE_LONG: return "long";
507 case TYPE_LLONG: return "long long";
508 case TYPE_SHORT: return "short";
509 case TYPE_FLOAT: return "float";
510 case TYPE_DOUBLE: return "double";
511 case TYPE_LDOUBLE: return "long double";
514 string = string_create();
515 string_cat(string, '(');
516 for (list_iterator_t *it = list_iterator(type->parameters); !list_iterator_end(it); ) {
517 data_type_t *next = list_iterator_next(it);
518 string_catf(string, "%s", ast_type_string(next));
519 if (!list_iterator_end(it))
520 string_cat(string, ',');
522 string_catf(string, ") -> %s", ast_type_string(type->returntype));
523 return string_buffer(string);
526 string = string_create();
527 string_catf(string, "%s*", ast_type_string(type->pointer));
528 return string_buffer(string);
531 string = string_create();
535 ast_type_string(type->pointer),
538 return string_buffer(string);
541 string = string_create();
542 string_catf(string, "(struct");
543 for (list_iterator_t *it = list_iterator(table_values(type->fields)); !list_iterator_end(it); ) {
544 data_type_t *ftype = list_iterator_next(it);
545 if (ftype->bitfield.size < 0) {
546 string_catf(string, " (%s)", ast_type_string(ftype));
551 ast_type_string(ftype),
552 ftype->bitfield.offset,
553 ftype->bitfield.offset + ftype->bitfield.size
557 string_cat(string, ')');
558 return string_buffer(string);
566 static void ast_string_unary(string_t *string, const char *op, ast_t *ast) {
567 string_catf(string, "(%s %s)", op, ast_string(ast->unary.operand));
570 static void ast_string_binary(string_t *string, const char *op, ast_t *ast) {
571 string_catf(string, "(%s %s %s)", op, ast_string(ast->left), ast_string(ast->right));
574 static void ast_string_initialization_declaration(string_t *string, list_t *initlist) {
578 for (list_iterator_t *it = list_iterator(initlist); !list_iterator_end(it); ) {
579 ast_t *init = list_iterator_next(it);
580 string_catf(string, "%s", ast_string(init));
581 if (!list_iterator_end(it))
582 string_cat(string, ' ');
586 static void ast_string_impl(string_t *string, ast_t *ast) {
591 string_catf(string, "(null)");
596 case AST_TYPE_LITERAL:
597 switch (ast->ctype->type) {
600 string_catf(string, "%d", ast->integer);
605 string_catf(string, "%f", ast->floating.value);
609 string_catf(string, "%ldL", ast->integer);
613 if (ast->integer == '\n')
614 string_catf(string, "'\n'");
615 else if (ast->integer == '\\')
616 string_catf(string, "'\\\\'");
617 else if (ast->integer == '\0')
618 string_catf(string, "'\\0'");
620 string_catf(string, "'%c'", ast->integer);
624 compile_ice("ast_string_impl");
629 case AST_TYPE_STRING:
630 string_catf(string, "\"%s\"", string_quote(ast->string.data));
633 case AST_TYPE_VAR_LOCAL:
634 string_catf(string, "%s", ast->variable.name);
635 if (ast->variable.init) {
636 string_cat(string, '(');
637 ast_string_initialization_declaration(string, ast->variable.init);
638 string_cat(string, ')');
642 case AST_TYPE_VAR_GLOBAL:
643 string_catf(string, "%s", ast->variable.name);
647 case AST_TYPE_POINTERCALL:
648 string_catf(string, "(%s)%s(", ast_type_string(ast->ctype),
649 (ast->type == AST_TYPE_CALL)
654 for (list_iterator_t *it = list_iterator(ast->function.call.args); !list_iterator_end(it); ) {
655 string_catf(string, "%s", ast_string(list_iterator_next(it)));
656 if (!list_iterator_end(it))
657 string_cat(string, ',');
659 string_cat(string, ')');
662 case AST_TYPE_FUNCTION:
663 string_catf(string, "(%s)%s(", ast_type_string(ast->ctype), ast->function.name);
664 for (list_iterator_t *it = list_iterator(ast->function.params); !list_iterator_end(it); ) {
665 ast_t *param = list_iterator_next(it);
666 string_catf(string, "%s %s", ast_type_string(param->ctype), ast_string(param));
667 if (!list_iterator_end(it))
668 string_cat(string, ',');
670 string_cat(string, ')');
671 ast_string_impl(string, ast->function.body);
674 case AST_TYPE_DECLARATION:
675 string_catf(string, "(decl %s %s ",
676 ast_type_string(ast->decl.var->ctype),
677 ast->decl.var->variable.name
679 ast_string_initialization_declaration(string, ast->decl.init);
680 string_cat(string, ')');
683 case AST_TYPE_INITIALIZER:
684 string_catf(string, "%s@%d", ast_string(ast->init.value), ast->init.offset);
687 case AST_TYPE_CONVERT:
688 string_catf(string, "(convert %s -> %s)", ast_string(ast->unary.operand), ast_type_string(ast->ctype));
691 case AST_TYPE_STATEMENT_COMPOUND:
692 string_cat(string, '{');
693 for (list_iterator_t *it = list_iterator(ast->compound); !list_iterator_end(it); ) {
694 ast_string_impl(string, list_iterator_next(it));
695 string_cat(string, ';');
697 string_cat(string, '}');
700 case AST_TYPE_STRUCT:
701 ast_string_impl(string, ast->structure);
702 string_cat(string, '.');
703 string_catf(string, ast->field);
706 case AST_TYPE_EXPRESSION_TERNARY:
707 string_catf(string, "(? %s %s %s)",
708 ast_string(ast->ifstmt.cond),
709 ast_string(ast->ifstmt.then),
710 ast_string(ast->ifstmt.last)
714 case AST_TYPE_STATEMENT_IF:
715 string_catf(string, "(if %s %s", ast_string(ast->ifstmt.cond), ast_string(ast->ifstmt.then));
716 if (ast->ifstmt.last)
717 string_catf(string, " %s", ast_string(ast->ifstmt.last));
718 string_cat(string, ')');
721 case AST_TYPE_STATEMENT_FOR:
722 string_catf(string, "(for %s %s %s %s)",
723 ast_string(ast->forstmt.init),
724 ast_string(ast->forstmt.cond),
725 ast_string(ast->forstmt.step),
726 ast_string(ast->forstmt.body)
730 case AST_TYPE_STATEMENT_WHILE:
731 string_catf(string, "(while %s %s)",
732 ast_string(ast->forstmt.cond),
733 ast_string(ast->forstmt.body)
737 case AST_TYPE_STATEMENT_DO:
738 string_catf(string, "(do %s %s)",
739 ast_string(ast->forstmt.cond),
740 ast_string(ast->forstmt.body)
744 case AST_TYPE_STATEMENT_RETURN:
745 string_catf(string, "(return %s)", ast_string(ast->returnstmt));
748 case AST_TYPE_LRSHIFT: ast_string_binary(string, ">>", ast); break;
749 case AST_TYPE_ADDRESS: ast_string_unary (string, "addr", ast); break;
750 case AST_TYPE_DEREFERENCE: ast_string_unary (string, "deref", ast); break;
753 case LEXER_TOKEN_COMPOUND_LSHIFT: ast_string_binary(string, "<<=", ast); break;
754 case LEXER_TOKEN_COMPOUND_RSHIFT: ast_string_binary(string, ">>=", ast); break;
755 case AST_TYPE_POST_INCREMENT: ast_string_unary (string, "postinc", ast); break;
756 case AST_TYPE_POST_DECREMENT: ast_string_unary (string, "postdec", ast); break;
757 case AST_TYPE_PRE_INCREMENT: ast_string_unary (string, "preinc", ast); break;
758 case AST_TYPE_PRE_DECREMENT: ast_string_unary (string, "predec", ast); break;
759 case AST_TYPE_NEGATE: ast_string_unary (string, "negate", ast); break;
760 case '!': ast_string_unary (string, "bitnot", ast); break;
761 case '&': ast_string_binary(string, "bitand", ast); break;
762 case '|': ast_string_binary(string, "bitor", ast); break;
763 case AST_TYPE_AND: ast_string_binary(string, "logand", ast); break;
764 case AST_TYPE_OR: ast_string_binary(string, "logor", ast); break;
765 case AST_TYPE_GEQUAL: ast_string_binary(string, "gteq", ast); break;
766 case AST_TYPE_LEQUAL: ast_string_binary(string, "lteq", ast); break;
767 case AST_TYPE_NEQUAL: ast_string_binary(string, "ne", ast); break;
768 case AST_TYPE_LSHIFT: ast_string_binary(string, "lshift", ast); break;
769 case AST_TYPE_RSHIFT: ast_string_binary(string, "rshift", ast); break;
771 case AST_TYPE_DESIGNATOR:
772 string_catf(string, "(designator %s)", ast_string(ast->function.call.functionpointer));
775 case AST_TYPE_EXPRESSION_CAST:
776 string_catf(string, "((%s) -> (%s) %s)",
777 ast_type_string(ast->unary.operand->ctype),
778 ast_type_string(ast->ctype),
779 ast_string(ast->unary.operand)
783 case AST_TYPE_STATEMENT_LABEL_COMPUTED:
784 string_catf(string, "(labeladdr %s)", ast->gotostmt.label);
788 if (!ast->left || !ast->right)
791 left = ast_string(ast->left);
792 right = ast_string(ast->right);
793 if (ast->type == LEXER_TOKEN_EQUAL)
794 string_catf(string, "(== %s %s)", left, right);
796 string_catf(string, "(%c %s %s)", ast->type, left, right);
800 char *ast_string(ast_t *ast) {
801 string_t *string = string_create();
802 ast_string_impl(string, ast);
803 return string_buffer(string);