fixed output of function types
[cparser] / type.c
1 #include <config.h>
2
3 #include <stdio.h>
4 #include <assert.h>
5 #include "type_t.h"
6 #include "type_hash.h"
7 #include "adt/error.h"
8
9 static struct obstack   _type_obst;
10 struct obstack         *type_obst = &_type_obst;
11 static FILE            *out;
12 static int              type_visited = 0;
13
14 static void intern_print_type_pre(type_t *type, bool top);
15 static void intern_print_type_post(type_t *type, bool top);
16
17 void init_types(void)
18 {
19         obstack_init(type_obst);
20 }
21
22 void exit_types(void)
23 {
24         obstack_free(type_obst, NULL);
25 }
26
27 void type_set_output(FILE *stream)
28 {
29         out = stream;
30 }
31
32 void inc_type_visited(void)
33 {
34         type_visited++;
35 }
36
37 void print_type_qualifiers(type_qualifiers_t qualifiers)
38 {
39         if(qualifiers & TYPE_QUALIFIER_CONST)    fputs("const ",    out);
40         if(qualifiers & TYPE_QUALIFIER_VOLATILE) fputs("volatile ", out);
41         if(qualifiers & TYPE_QUALIFIER_RESTRICT) fputs("restrict ", out);
42 }
43
44 static
45 void print_atomic_type(const atomic_type_t *type)
46 {
47         print_type_qualifiers(type->type.qualifiers);
48
49         const char *s;
50         switch(type->atype) {
51         case ATOMIC_TYPE_INVALID:     s = "INVALIDATOMIC";      break;
52         case ATOMIC_TYPE_VOID:        s = "void";               break;
53         case ATOMIC_TYPE_BOOL:        s = "_Bool";              break;
54         case ATOMIC_TYPE_CHAR:        s = "char";               break;
55         case ATOMIC_TYPE_SCHAR:       s = "signed char";        break;
56         case ATOMIC_TYPE_UCHAR:       s = "unsigned char";      break;
57         case ATOMIC_TYPE_INT:         s = "int";                break;
58         case ATOMIC_TYPE_UINT:        s = "unsigned int";       break;
59         case ATOMIC_TYPE_SHORT:       s = "short";              break;
60         case ATOMIC_TYPE_USHORT:      s = "unsigned short";     break;
61         case ATOMIC_TYPE_LONG:        s = "long";               break;
62         case ATOMIC_TYPE_ULONG:       s = "unsigned long";      break;
63         case ATOMIC_TYPE_LONGLONG:    s = "long long";          break;
64         case ATOMIC_TYPE_ULONGLONG:   s = "unsigned long long"; break;
65         case ATOMIC_TYPE_LONG_DOUBLE: s = "long double";        break;
66         case ATOMIC_TYPE_FLOAT:       s = "float";              break;
67         case ATOMIC_TYPE_DOUBLE:      s = "double";             break;
68         default:                      s = "UNKNOWNATOMIC";      break;
69         }
70         fputs(s, out);
71 }
72
73 static void print_function_type_pre(const function_type_t *type, bool top)
74 {
75         print_type_qualifiers(type->type.qualifiers);
76
77         intern_print_type_pre(type->return_type, false);
78
79         /* don't emit braces if we're the toplevel type... */
80         if(!top)
81                 fputc('(', out);
82 }
83
84 static void print_function_type_post(const function_type_t *type,
85                                      const context_t *context, bool top)
86 {
87         intern_print_type_post(type->return_type, false);
88         /* don't emit braces if we're the toplevel type... */
89         if(!top)
90                 fputc(')', out);
91
92         fputc('(', out);
93
94         int                 first     = 1;
95         if(context == NULL) {
96                 function_parameter_t *parameter = type->parameters;
97                 for( ; parameter != NULL; parameter = parameter->next) {
98                         if(first) {
99                                 first = 0;
100                         } else {
101                                 fputs(", ", out);
102                         }
103                         print_type(parameter->type);
104                 }
105         } else {
106                 declaration_t *parameter = context->declarations;
107                 for( ; parameter != NULL; parameter = parameter->next) {
108                         if(first) {
109                                 first = 0;
110                         } else {
111                                 fputs(", ", out);
112                         }
113                         print_type_ext(parameter->type, parameter->symbol,
114                                        &parameter->context);
115                 }
116         }
117         if(type->variadic) {
118                 if(first) {
119                         first = 0;
120                 } else {
121                         fputs(", ", out);
122                 }
123                 fputs("...", out);
124         }
125         if(first && !type->unspecified_parameters) {
126                 fputs("void", out);
127         }
128         fputc(')', out);
129 }
130
131 static void print_pointer_type_pre(const pointer_type_t *type)
132 {
133         intern_print_type_pre(type->points_to, false);
134         fputs("*", out);
135         print_type_qualifiers(type->type.qualifiers);
136 }
137
138 static void print_pointer_type_post(const pointer_type_t *type)
139 {
140         intern_print_type_post(type->points_to, false);
141 }
142
143 static void print_array_type_pre(const array_type_t *type)
144 {
145         intern_print_type_pre(type->element_type, false);
146 }
147
148 static void print_array_type_post(const array_type_t *type)
149 {
150         fputc('[', out);
151         if(type->is_static) {
152                 fputs("static ", out);
153         }
154         print_type_qualifiers(type->type.qualifiers);
155         if(type->size != NULL) {
156                 print_expression(type->size);
157         }
158         fputc(']', out);
159         intern_print_type_post(type->element_type, false);
160 }
161
162 void print_enum_definition(const declaration_t *declaration)
163 {
164         fputs("{\n", out);
165
166         change_indent(1);
167
168         declaration_t *entry = declaration->next;
169         for( ; entry != NULL && entry->storage_class == STORAGE_CLASS_ENUM_ENTRY;
170                entry = entry->next) {
171
172                 print_indent();
173                 fprintf(out, "%s", entry->symbol->string);
174                 if(entry->init.initializer != NULL) {
175                         fprintf(out, " = ");
176                         print_expression(entry->init.enum_value);
177                 }
178                 fprintf(out, ",\n");
179         }
180
181         change_indent(-1);
182         print_indent();
183         fputs("}", out);
184 }
185
186 static void print_type_enum(const enum_type_t *type)
187 {
188         print_type_qualifiers(type->type.qualifiers);
189         fputs("enum ", out);
190
191         declaration_t *declaration = type->declaration;
192         symbol_t      *symbol      = declaration->symbol;
193         if(symbol != NULL) {
194                 fputs(symbol->string, out);
195         } else {
196                 print_enum_definition(declaration);
197         }
198 }
199
200 void print_compound_definition(const declaration_t *declaration)
201 {
202         fputs("{\n", out);
203         change_indent(1);
204
205         declaration_t *iter = declaration->context.declarations;
206         for( ; iter != NULL; iter = iter->next) {
207                 print_indent();
208                 print_declaration(iter);
209                 fputc('\n', out);
210         }
211
212         change_indent(-1);
213         print_indent();
214         fputs("}", out);
215 }
216
217 static void print_compound_type(const compound_type_t *type)
218 {
219         print_type_qualifiers(type->type.qualifiers);
220
221         if(type->type.type == TYPE_COMPOUND_STRUCT) {
222                 fputs("struct ", out);
223         } else {
224                 assert(type->type.type == TYPE_COMPOUND_UNION);
225                 fputs("union ", out);
226         }
227
228         declaration_t *declaration = type->declaration;
229         symbol_t      *symbol      = declaration->symbol;
230         if(symbol != NULL) {
231                 fputs(symbol->string, out);
232         } else {
233                 print_compound_definition(declaration);
234         }
235 }
236
237 static void print_typedef_type_pre(typedef_type_t *type)
238 {
239         fputs(type->declaration->symbol->string, out);
240 }
241
242 static void print_typeof_type_pre(typeof_type_t *type)
243 {
244         fputs("typeof(", out);
245         if(type->expression != NULL) {
246                 assert(type->typeof_type == NULL);
247                 print_expression(type->expression);
248         } else {
249                 print_type(type->typeof_type);
250         }
251         fputc(')', out);
252 }
253
254 static void intern_print_type_pre(type_t *type, bool top)
255 {
256         switch(type->type) {
257         case TYPE_INVALID:
258                 fputs("invalid", out);
259                 return;
260         case TYPE_ENUM:
261                 print_type_enum(&type->enumt);
262                 return;
263         case TYPE_ATOMIC:
264                 print_atomic_type(&type->atomic);
265                 return;
266         case TYPE_COMPOUND_STRUCT:
267         case TYPE_COMPOUND_UNION:
268                 print_compound_type(&type->compound);
269                 return;
270         case TYPE_BUILTIN:
271                 fputs(type->builtin.symbol->string, out);
272                 return;
273         case TYPE_FUNCTION:
274                 print_function_type_pre(&type->function, top);
275                 return;
276         case TYPE_POINTER:
277                 print_pointer_type_pre(&type->pointer);
278                 return;
279         case TYPE_ARRAY:
280                 print_array_type_pre(&type->array);
281                 return;
282         case TYPE_TYPEDEF:
283                 print_typedef_type_pre(&type->typedeft);
284                 return;
285         case TYPE_TYPEOF:
286                 print_typeof_type_pre(&type->typeoft);
287                 return;
288         }
289         fputs("unknown", out);
290 }
291
292 static void intern_print_type_post(type_t *type, bool top)
293 {
294         switch(type->type) {
295         case TYPE_FUNCTION:
296                 print_function_type_post(&type->function, NULL, top);
297                 return;
298         case TYPE_POINTER:
299                 print_pointer_type_post(&type->pointer);
300                 return;
301         case TYPE_ARRAY:
302                 print_array_type_post(&type->array);
303                 return;
304         case TYPE_INVALID:
305         case TYPE_ATOMIC:
306         case TYPE_ENUM:
307         case TYPE_COMPOUND_STRUCT:
308         case TYPE_COMPOUND_UNION:
309         case TYPE_BUILTIN:
310         case TYPE_TYPEOF:
311         case TYPE_TYPEDEF:
312                 break;
313         }
314 }
315
316 void print_type(type_t *type)
317 {
318         print_type_ext(type, NULL, NULL);
319 }
320
321 void print_type_ext(type_t *type, const symbol_t *symbol,
322                     const context_t *context)
323 {
324         if(type == NULL) {
325                 fputs("nil type", out);
326                 return;
327         }
328
329         intern_print_type_pre(type, true);
330         if(symbol != NULL) {
331                 fputc(' ', out);
332                 fputs(symbol->string, out);
333         }
334         if(type->type == TYPE_FUNCTION) {
335                 print_function_type_post(&type->function, context, true);
336         } else {
337                 intern_print_type_post(type, true);
338         }
339 }
340
341 static size_t get_type_size(type_t *type)
342 {
343         switch(type->type) {
344         case TYPE_ATOMIC:          return sizeof(atomic_type_t);
345         case TYPE_COMPOUND_STRUCT:
346         case TYPE_COMPOUND_UNION:  return sizeof(compound_type_t);
347         case TYPE_ENUM:            return sizeof(enum_type_t);
348         case TYPE_FUNCTION:        return sizeof(function_type_t);
349         case TYPE_POINTER:         return sizeof(pointer_type_t);
350         case TYPE_ARRAY:           return sizeof(array_type_t);
351         case TYPE_BUILTIN:         return sizeof(builtin_type_t);
352         case TYPE_TYPEDEF:         return sizeof(typedef_type_t);
353         case TYPE_TYPEOF:          return sizeof(typeof_type_t);
354         case TYPE_INVALID:         panic("invalid type found");
355         }
356         panic("unknown type found");
357 }
358
359 /**
360  * duplicates a type
361  * note that this does not produce a deep copy!
362  */
363 type_t *duplicate_type(type_t *type)
364 {
365         size_t size = get_type_size(type);
366
367         type_t *copy = obstack_alloc(type_obst, size);
368         memcpy(copy, type, size);
369
370         return copy;
371 }
372
373 type_t *get_unqualified_type(type_t *type)
374 {
375         if(type->base.qualifiers == TYPE_QUALIFIER_NONE)
376                 return type;
377
378         type_t *unqualified_type          = duplicate_type(type);
379         unqualified_type->base.qualifiers = TYPE_QUALIFIER_NONE;
380
381         type_t *result = typehash_insert(unqualified_type);
382         if(result != unqualified_type) {
383                 obstack_free(type_obst, unqualified_type);
384         }
385
386         return result;
387 }
388
389 bool type_valid(const type_t *type)
390 {
391         return type->type != TYPE_INVALID;
392 }
393
394 bool is_type_integer(const type_t *type)
395 {
396         assert(!is_typeref(type));
397
398         if(type->type == TYPE_ENUM)
399                 return true;
400
401         if(type->type != TYPE_ATOMIC)
402                 return false;
403
404         switch(type->atomic.atype) {
405         case ATOMIC_TYPE_BOOL:
406         case ATOMIC_TYPE_CHAR:
407         case ATOMIC_TYPE_SCHAR:
408         case ATOMIC_TYPE_UCHAR:
409         case ATOMIC_TYPE_SHORT:
410         case ATOMIC_TYPE_USHORT:
411         case ATOMIC_TYPE_INT:
412         case ATOMIC_TYPE_UINT:
413         case ATOMIC_TYPE_LONG:
414         case ATOMIC_TYPE_ULONG:
415         case ATOMIC_TYPE_LONGLONG:
416         case ATOMIC_TYPE_ULONGLONG:
417                 return true;
418         default:
419                 return false;
420         }
421 }
422
423 bool is_type_floating(const type_t *type)
424 {
425         assert(!is_typeref(type));
426
427         if(type->type != TYPE_ATOMIC)
428                 return false;
429
430         switch(type->atomic.atype) {
431         case ATOMIC_TYPE_FLOAT:
432         case ATOMIC_TYPE_DOUBLE:
433         case ATOMIC_TYPE_LONG_DOUBLE:
434 #ifdef PROVIDE_COMPLEX
435         case ATOMIC_TYPE_FLOAT_COMPLEX:
436         case ATOMIC_TYPE_DOUBLE_COMPLEX:
437         case ATOMIC_TYPE_LONG_DOUBLE_COMPLEX:
438         case ATOMIC_TYPE_FLOAT_IMAGINARY:
439         case ATOMIC_TYPE_DOUBLE_IMAGINARY:
440         case ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY:
441 #endif
442                 return true;
443         default:
444                 return false;
445         }
446 }
447
448 bool is_type_signed(const type_t *type)
449 {
450         assert(!is_typeref(type));
451
452         /* enum types are int for now */
453         if(type->type == TYPE_ENUM)
454                 return true;
455
456         if(type->type != TYPE_ATOMIC)
457                 return false;
458
459         switch(type->atomic.atype) {
460         case ATOMIC_TYPE_CHAR:
461         case ATOMIC_TYPE_SCHAR:
462         case ATOMIC_TYPE_SHORT:
463         case ATOMIC_TYPE_INT:
464         case ATOMIC_TYPE_LONG:
465         case ATOMIC_TYPE_LONGLONG:
466         case ATOMIC_TYPE_FLOAT:
467         case ATOMIC_TYPE_DOUBLE:
468         case ATOMIC_TYPE_LONG_DOUBLE:
469 #ifdef PROVIDE_COMPLEX
470         case ATOMIC_TYPE_FLOAT_COMPLEX:
471         case ATOMIC_TYPE_DOUBLE_COMPLEX:
472         case ATOMIC_TYPE_LONG_DOUBLE_COMPLEX:
473         case ATOMIC_TYPE_FLOAT_IMAGINARY:
474         case ATOMIC_TYPE_DOUBLE_IMAGINARY:
475         case ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY:
476 #endif
477                 return true;
478
479         case ATOMIC_TYPE_BOOL:
480         case ATOMIC_TYPE_UCHAR:
481         case ATOMIC_TYPE_USHORT:
482         case ATOMIC_TYPE_UINT:
483         case ATOMIC_TYPE_ULONG:
484         case ATOMIC_TYPE_ULONGLONG:
485                 return false;
486
487         case ATOMIC_TYPE_VOID:
488         case ATOMIC_TYPE_INVALID:
489         case ATOMIC_TYPE_LAST:
490                 return false;
491         }
492
493         panic("invalid atomic type found");
494         return false;
495 }
496
497 bool is_type_arithmetic(const type_t *type)
498 {
499         assert(!is_typeref(type));
500
501         if(is_type_integer(type) || is_type_floating(type))
502                 return true;
503
504         return false;
505 }
506
507 bool is_type_scalar(const type_t *type)
508 {
509         assert(!is_typeref(type));
510
511         switch (type->type) {
512                 case TYPE_POINTER: return true;
513                 case TYPE_BUILTIN: return is_type_scalar(type->builtin.real_type);
514                 default:           break;
515         }
516
517         return is_type_arithmetic(type);
518 }
519
520 bool is_type_incomplete(const type_t *type)
521 {
522         assert(!is_typeref(type));
523
524         switch(type->type) {
525         case TYPE_COMPOUND_STRUCT:
526         case TYPE_COMPOUND_UNION: {
527                 const compound_type_t *compound_type = &type->compound;
528                 declaration_t         *declaration   = compound_type->declaration;
529                 return !declaration->init.is_defined;
530         }
531         case TYPE_FUNCTION:
532                 return true;
533
534         case TYPE_ARRAY:
535                 return type->array.size == NULL;
536
537         case TYPE_ATOMIC:
538         case TYPE_POINTER:
539         case TYPE_ENUM:
540         case TYPE_BUILTIN:
541                 return false;
542
543         case TYPE_TYPEDEF:
544         case TYPE_TYPEOF:
545                 panic("is_type_incomplete called without typerefs skipped");
546         case TYPE_INVALID:
547                 break;
548         }
549
550         panic("invalid type found");
551 }
552
553 static bool function_types_compatible(const function_type_t *func1,
554                                       const function_type_t *func2)
555 {
556         if(!types_compatible(func1->return_type, func2->return_type))
557                 return false;
558
559         /* can parameters be compared? */
560         if(func1->unspecified_parameters || func2->unspecified_parameters)
561                 return true;
562
563         if(func1->variadic != func2->variadic)
564                 return false;
565
566         /* TODO: handling of unspecified parameters not correct yet */
567
568         /* all argument types must be compatible */
569         function_parameter_t *parameter1 = func1->parameters;
570         function_parameter_t *parameter2 = func2->parameters;
571         for( ; parameter1 != NULL && parameter2 != NULL;
572                         parameter1 = parameter1->next, parameter2 = parameter2->next) {
573                 type_t *parameter1_type = skip_typeref(parameter1->type);
574                 type_t *parameter2_type = skip_typeref(parameter2->type);
575
576                 parameter1_type = get_unqualified_type(parameter1_type);
577                 parameter2_type = get_unqualified_type(parameter2_type);
578
579                 if(!types_compatible(parameter1_type, parameter2_type))
580                         return false;
581         }
582         /* same number of arguments? */
583         if(parameter1 != NULL || parameter2 != NULL)
584                 return false;
585
586         return true;
587 }
588
589 static bool array_types_compatible(const array_type_t *array1,
590                                    const array_type_t *array2)
591 {
592         type_t *element_type1 = skip_typeref(array1->element_type);
593         type_t *element_type2 = skip_typeref(array2->element_type);
594         if(!types_compatible(element_type1, element_type2))
595                 return false;
596
597         if(array1->size != NULL && array2->size != NULL) {
598                 /* TODO: check if size expression evaulate to the same value
599                  * if they are constant */
600         }
601
602         return true;
603 }
604
605 bool types_compatible(const type_t *type1, const type_t *type2)
606 {
607         assert(!is_typeref(type1));
608         assert(!is_typeref(type2));
609
610         /* shortcut: the same type is always compatible */
611         if(type1 == type2)
612                 return true;
613
614         if(type1->base.qualifiers != type2->base.qualifiers)
615                 return false;
616         if(type1->type != type2->type)
617                 return false;
618
619         switch(type1->type) {
620         case TYPE_FUNCTION:
621                 return function_types_compatible(&type1->function, &type2->function);
622         case TYPE_ATOMIC:
623                 return type1->atomic.atype == type2->atomic.atype;
624         case TYPE_ARRAY:
625                 return array_types_compatible(&type1->array, &type2->array);
626         case TYPE_POINTER:
627                 return types_compatible(type1->pointer.points_to,
628                                         type2->pointer.points_to);
629         case TYPE_COMPOUND_STRUCT:
630         case TYPE_COMPOUND_UNION:
631         case TYPE_ENUM:
632         case TYPE_BUILTIN:
633                 /* TODO: not implemented */
634                 break;
635
636         case TYPE_INVALID:
637                 panic("invalid type found in compatible types");
638         case TYPE_TYPEDEF:
639         case TYPE_TYPEOF:
640                 panic("typerefs not skipped in compatible types?!?");
641         }
642
643         /* TODO: incomplete */
644         return false;
645 }
646
647 bool pointers_compatible(const type_t *type1, const type_t *type2)
648 {
649         assert(!is_typeref(type1));
650         assert(!is_typeref(type2));
651
652         assert(type1->type == TYPE_POINTER);
653         assert(type2->type == TYPE_POINTER);
654         /* TODO */
655         return true;
656 }
657
658 type_t *skip_typeref(type_t *type)
659 {
660         unsigned qualifiers = type->base.qualifiers;
661
662         while(1) {
663                 switch(type->type) {
664                 case TYPE_TYPEDEF: {
665                         qualifiers |= type->base.qualifiers;
666                         const typedef_type_t *typedef_type = &type->typedeft;
667                         if(typedef_type->resolved_type != NULL) {
668                                 type = typedef_type->resolved_type;
669                                 break;
670                         }
671                         type = typedef_type->declaration->type;
672                         continue;
673                 }
674                 case TYPE_TYPEOF: {
675                         const typeof_type_t *typeof_type = &type->typeoft;
676                         if(typeof_type->typeof_type != NULL) {
677                                 type = typeof_type->typeof_type;
678                         } else {
679                                 type = typeof_type->expression->base.datatype;
680                         }
681                         continue;
682                 }
683                 default:
684                         break;
685                 }
686                 break;
687         }
688
689         return type;
690 }
691
692
693
694 static type_t *identify_new_type(type_t *type)
695 {
696         type_t *result = typehash_insert(type);
697         if(result != type) {
698                 obstack_free(type_obst, type);
699         }
700         return result;
701 }
702
703 type_t *make_atomic_type(atomic_type_type_t atype, type_qualifiers_t qualifiers)
704 {
705         type_t *type = obstack_alloc(type_obst, sizeof(atomic_type_t));
706         memset(type, 0, sizeof(atomic_type_t));
707
708         type->type            = TYPE_ATOMIC;
709         type->base.qualifiers = qualifiers;
710         type->atomic.atype    = atype;
711
712         return identify_new_type(type);
713 }
714
715 type_t *make_pointer_type(type_t *points_to, type_qualifiers_t qualifiers)
716 {
717         type_t *type = obstack_alloc(type_obst, sizeof(pointer_type_t));
718         memset(type, 0, sizeof(pointer_type_t));
719
720         type->type              = TYPE_POINTER;
721         type->base.qualifiers   = qualifiers;
722         type->pointer.points_to = points_to;
723
724         return identify_new_type(type);
725 }
726
727 static __attribute__((unused))
728 void dbg_type(type_t *type)
729 {
730         FILE *old_out = out;
731         out = stderr;
732         print_type(type);
733         puts("\n");
734         fflush(stderr);
735         out = old_out;
736 }