nsz Git - cparser/blob - 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(const type_t *type, bool top);
  15 static void intern_print_type_post(const 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 /**
  45  * Prints the name of a atomic type.
  46  *
  47  * @param type  The type.
  48  */
  49 static
  50 void print_atomic_type(const atomic_type_t *type)
  51 {
  52         print_type_qualifiers(type->type.qualifiers);
  53
  54         const char *s;
  55         switch(type->akind) {
  56         case ATOMIC_TYPE_INVALID:     s = "INVALIDATOMIC";      break;
  57         case ATOMIC_TYPE_VOID:        s = "void";               break;
  58         case ATOMIC_TYPE_BOOL:        s = "_Bool";              break;
  59         case ATOMIC_TYPE_CHAR:        s = "char";               break;
  60         case ATOMIC_TYPE_SCHAR:       s = "signed char";        break;
  61         case ATOMIC_TYPE_UCHAR:       s = "unsigned char";      break;
  62         case ATOMIC_TYPE_INT:         s = "int";                break;
  63         case ATOMIC_TYPE_UINT:        s = "unsigned int";       break;
  64         case ATOMIC_TYPE_SHORT:       s = "short";              break;
  65         case ATOMIC_TYPE_USHORT:      s = "unsigned short";     break;
  66         case ATOMIC_TYPE_LONG:        s = "long";               break;
  67         case ATOMIC_TYPE_ULONG:       s = "unsigned long";      break;
  68         case ATOMIC_TYPE_LONGLONG:    s = "long long";          break;
  69         case ATOMIC_TYPE_ULONGLONG:   s = "unsigned long long"; break;
  70         case ATOMIC_TYPE_LONG_DOUBLE: s = "long double";        break;
  71         case ATOMIC_TYPE_FLOAT:       s = "float";              break;
  72         case ATOMIC_TYPE_DOUBLE:      s = "double";             break;
  73         default:                      s = "UNKNOWNATOMIC";      break;
  74         }
  75         fputs(s, out);
  76 }
  77
  78 /**
  79  * Print the first part (the prefix) of a type.
  80  *
  81  * @param type   The type to print.
  82  * @param top    true, if this is the top type, false if it's an embedded type.
  83  */
  84 static void print_function_type_pre(const function_type_t *type, bool top)
  85 {
  86         print_type_qualifiers(type->type.qualifiers);
  87
  88         intern_print_type_pre(type->return_type, false);
  89
  90         /* don't emit braces if we're the toplevel type... */
  91         if(!top)
  92                 fputc('(', out);
  93 }
  94
  95 /**
  96  * Print the second part (the postfix) of a type.
  97  *
  98  * @param type   The type to print.
  99  * @param top    true, if this is the top type, false if it's an embedded type.
 100  */
 101 static void print_function_type_post(const function_type_t *type,
 102                                      const scope_t *scope, bool top)
 103 {
 104         intern_print_type_post(type->return_type, false);
 105         /* don't emit braces if we're the toplevel type... */
 106         if(!top)
 107                 fputc(')', out);
 108
 109         fputc('(', out);
 110
 111         int first = 1;
 112         if(scope == NULL) {
 113                 function_parameter_t *parameter = type->parameters;
 114                 for( ; parameter != NULL; parameter = parameter->next) {
 115                         if(first) {
 116                                 first = 0;
 117                         } else {
 118                                 fputs(", ", out);
 119                         }
 120                         print_type(parameter->type);
 121                 }
 122         } else {
 123                 declaration_t *parameter = scope->declarations;
 124                 for( ; parameter != NULL; parameter = parameter->next) {
 125                         if(first) {
 126                                 first = 0;
 127                         } else {
 128                                 fputs(", ", out);
 129                         }
 130                         print_type_ext(parameter->type, parameter->symbol,
 131                                        &parameter->scope);
 132                 }
 133         }
 134         if(type->variadic) {
 135                 if(first) {
 136                         first = 0;
 137                 } else {
 138                         fputs(", ", out);
 139                 }
 140                 fputs("...", out);
 141         }
 142         if(first && !type->unspecified_parameters) {
 143                 fputs("void", out);
 144         }
 145         fputc(')', out);
 146 }
 147
 148 /**
 149  * Prints the prefix part of a pointer type.
 150  *
 151  * @param type   The pointer type.
 152  */
 153 static void print_pointer_type_pre(const pointer_type_t *type)
 154 {
 155         intern_print_type_pre(type->points_to, false);
 156         fputs("*", out);
 157         print_type_qualifiers(type->type.qualifiers);
 158 }
 159
 160 /**
 161  * Prints the postfix part of a pointer type.
 162  *
 163  * @param type   The pointer type.
 164  */
 165 static void print_pointer_type_post(const pointer_type_t *type)
 166 {
 167         intern_print_type_post(type->points_to, false);
 168 }
 169
 170 /**
 171  * Prints the prefix part of an array type.
 172  *
 173  * @param type   The array type.
 174  */
 175 static void print_array_type_pre(const array_type_t *type)
 176 {
 177         intern_print_type_pre(type->element_type, false);
 178 }
 179
 180 /**
 181  * Prints the postfix part of an array type.
 182  *
 183  * @param type   The array type.
 184  */
 185 static void print_array_type_post(const array_type_t *type)
 186 {
 187         fputc('[', out);
 188         if(type->is_static) {
 189                 fputs("static ", out);
 190         }
 191         print_type_qualifiers(type->type.qualifiers);
 192         if(type->size != NULL) {
 193                 print_expression(type->size);
 194         }
 195         fputc(']', out);
 196         intern_print_type_post(type->element_type, false);
 197 }
 198
 199 /**
 200  * Prints the postfix part of a bitfield type.
 201  *
 202  * @param type   The array type.
 203  */
 204 static void print_bitfield_type_post(const bitfield_type_t *type)
 205 {
 206         fputs(" : ", out);
 207         print_expression(type->size);
 208         intern_print_type_post(type->base, false);
 209 }
 210
 211 /**
 212  * Prints an enum definition.
 213  *
 214  * @param declaration  The enum's type declaration.
 215  */
 216 void print_enum_definition(const declaration_t *declaration)
 217 {
 218         fputs("{\n", out);
 219
 220         change_indent(1);
 221
 222         declaration_t *entry = declaration->next;
 223         for( ; entry != NULL && entry->storage_class == STORAGE_CLASS_ENUM_ENTRY;
 224                entry = entry->next) {
 225
 226                 print_indent();
 227                 fprintf(out, "%s", entry->symbol->string);
 228                 if(entry->init.initializer != NULL) {
 229                         fprintf(out, " = ");
 230                         print_expression(entry->init.enum_value);
 231                 }
 232                 fprintf(out, ",\n");
 233         }
 234
 235         change_indent(-1);
 236         print_indent();
 237         fputs("}", out);
 238 }
 239
 240 /**
 241  * Prints an enum type.
 242  *
 243  * @param type  The enum type.
 244  */
 245 static void print_type_enum(const enum_type_t *type)
 246 {
 247         print_type_qualifiers(type->type.qualifiers);
 248         fputs("enum ", out);
 249
 250         declaration_t *declaration = type->declaration;
 251         symbol_t      *symbol      = declaration->symbol;
 252         if(symbol != NULL) {
 253                 fputs(symbol->string, out);
 254         } else {
 255                 print_enum_definition(declaration);
 256         }
 257 }
 258
 259 /**
 260  * Print the compound part of a compound type.
 261  *
 262  * @param declaration  The declaration of the compound type.
 263  */
 264 void print_compound_definition(const declaration_t *declaration)
 265 {
 266         fputs("{\n", out);
 267         change_indent(1);
 268
 269         declaration_t *iter = declaration->scope.declarations;
 270         for( ; iter != NULL; iter = iter->next) {
 271                 print_indent();
 272                 print_declaration(iter);
 273                 fputc('\n', out);
 274         }
 275
 276         change_indent(-1);
 277         print_indent();
 278         fputs("}", out);
 279 }
 280
 281 /**
 282  * Prints a compound type.
 283  *
 284  * @param type  The compound type.
 285  */
 286 static void print_compound_type(const compound_type_t *type)
 287 {
 288         print_type_qualifiers(type->type.qualifiers);
 289
 290         if(type->type.kind == TYPE_COMPOUND_STRUCT) {
 291                 fputs("struct ", out);
 292         } else {
 293                 assert(type->type.kind == TYPE_COMPOUND_UNION);
 294                 fputs("union ", out);
 295         }
 296
 297         declaration_t *declaration = type->declaration;
 298         symbol_t      *symbol      = declaration->symbol;
 299         if(symbol != NULL) {
 300                 fputs(symbol->string, out);
 301         } else {
 302                 print_compound_definition(declaration);
 303         }
 304 }
 305
 306 /**
 307  * Prints the prefix part of a typedef type.
 308  *
 309  * @param type   The typedef type.
 310  */
 311 static void print_typedef_type_pre(const typedef_type_t *const type)
 312 {
 313         print_type_qualifiers(type->type.qualifiers);
 314         fputs(type->declaration->symbol->string, out);
 315 }
 316
 317 /**
 318  * Prints the prefix part of a typeof type.
 319  *
 320  * @param type   The typeof type.
 321  */
 322 static void print_typeof_type_pre(const typeof_type_t *const type)
 323 {
 324         fputs("typeof(", out);
 325         if(type->expression != NULL) {
 326                 assert(type->typeof_type == NULL);
 327                 print_expression(type->expression);
 328         } else {
 329                 print_type(type->typeof_type);
 330         }
 331         fputc(')', out);
 332 }
 333
 334 /**
 335  * Prints the prefix part of a type.
 336  *
 337  * @param type   The type.
 338  * @param top    true if we print the toplevel type, false else.
 339  */
 340 static void intern_print_type_pre(const type_t *const type, const bool top)
 341 {
 342         switch(type->kind) {
 343         case TYPE_ERROR:
 344                 fputs("<error>", out);
 345         case TYPE_INVALID:
 346                 fputs("<invalid>", out);
 347                 return;
 348         case TYPE_ENUM:
 349                 print_type_enum(&type->enumt);
 350                 return;
 351         case TYPE_ATOMIC:
 352                 print_atomic_type(&type->atomic);
 353                 return;
 354         case TYPE_COMPOUND_STRUCT:
 355         case TYPE_COMPOUND_UNION:
 356                 print_compound_type(&type->compound);
 357                 return;
 358         case TYPE_BUILTIN:
 359                 fputs(type->builtin.symbol->string, out);
 360                 return;
 361         case TYPE_FUNCTION:
 362                 print_function_type_pre(&type->function, top);
 363                 return;
 364         case TYPE_POINTER:
 365                 print_pointer_type_pre(&type->pointer);
 366                 return;
 367         case TYPE_BITFIELD:
 368                 intern_print_type_pre(type->bitfield.base, top);
 369                 return;
 370         case TYPE_ARRAY:
 371                 print_array_type_pre(&type->array);
 372                 return;
 373         case TYPE_TYPEDEF:
 374                 print_typedef_type_pre(&type->typedeft);
 375                 return;
 376         case TYPE_TYPEOF:
 377                 print_typeof_type_pre(&type->typeoft);
 378                 return;
 379         }
 380         fputs("unknown", out);
 381 }
 382
 383 /**
 384  * Prints the postfix part of a type.
 385  *
 386  * @param type   The type.
 387  * @param top    true if we print the toplevel type, false else.
 388  */
 389 static void intern_print_type_post(const type_t *const type, const bool top)
 390 {
 391         switch(type->kind) {
 392         case TYPE_FUNCTION:
 393                 print_function_type_post(&type->function, NULL, top);
 394                 return;
 395         case TYPE_POINTER:
 396                 print_pointer_type_post(&type->pointer);
 397                 return;
 398         case TYPE_ARRAY:
 399                 print_array_type_post(&type->array);
 400                 return;
 401         case TYPE_BITFIELD:
 402                 print_bitfield_type_post(&type->bitfield);
 403                 return;
 404         case TYPE_ERROR:
 405         case TYPE_INVALID:
 406         case TYPE_ATOMIC:
 407         case TYPE_ENUM:
 408         case TYPE_COMPOUND_STRUCT:
 409         case TYPE_COMPOUND_UNION:
 410         case TYPE_BUILTIN:
 411         case TYPE_TYPEOF:
 412         case TYPE_TYPEDEF:
 413                 break;
 414         }
 415 }
 416
 417 /**
 418  * Prints a type.
 419  *
 420  * @param type   The type.
 421  */
 422 void print_type(const type_t *const type)
 423 {
 424         print_type_ext(type, NULL, NULL);
 425 }
 426
 427 void print_type_ext(const type_t *const type, const symbol_t *symbol,
 428                     const scope_t *scope)
 429 {
 430         if(type == NULL) {
 431                 fputs("nil type", out);
 432                 return;
 433         }
 434
 435         intern_print_type_pre(type, true);
 436         if(symbol != NULL) {
 437                 fputc(' ', out);
 438                 fputs(symbol->string, out);
 439         }
 440         if(type->kind == TYPE_FUNCTION) {
 441                 print_function_type_post(&type->function, scope, true);
 442         } else {
 443                 intern_print_type_post(type, true);
 444         }
 445 }
 446
 447 /**
 448  * Return the size of a type AST node.
 449  *
 450  * @param type  The type.
 451  */
 452 static size_t get_type_size(const type_t *type)
 453 {
 454         switch(type->kind) {
 455         case TYPE_ATOMIC:          return sizeof(atomic_type_t);
 456         case TYPE_COMPOUND_STRUCT:
 457         case TYPE_COMPOUND_UNION:  return sizeof(compound_type_t);
 458         case TYPE_ENUM:            return sizeof(enum_type_t);
 459         case TYPE_FUNCTION:        return sizeof(function_type_t);
 460         case TYPE_POINTER:         return sizeof(pointer_type_t);
 461         case TYPE_ARRAY:           return sizeof(array_type_t);
 462         case TYPE_BUILTIN:         return sizeof(builtin_type_t);
 463         case TYPE_TYPEDEF:         return sizeof(typedef_type_t);
 464         case TYPE_TYPEOF:          return sizeof(typeof_type_t);
 465         case TYPE_BITFIELD:        return sizeof(bitfield_type_t);
 466         case TYPE_ERROR:           panic("error type found");
 467         case TYPE_INVALID:         panic("invalid type found");
 468         }
 469         panic("unknown type found");
 470 }
 471
 472 /**
 473  * Duplicates a type.
 474  *
 475  * @param type  The type to copy.
 476  * @return A copy of the type.
 477  *
 478  * @note This does not produce a deep copy!
 479  */
 480 type_t *duplicate_type(const type_t *type)
 481 {
 482         size_t size = get_type_size(type);
 483
 484         type_t *copy = obstack_alloc(type_obst, size);
 485         memcpy(copy, type, size);
 486
 487         return copy;
 488 }
 489
 490 /**
 491  * Returns the unqualified type of a given type.
 492  *
 493  * @param type  The type.
 494  * @returns The unqualified type.
 495  */
 496 type_t *get_unqualified_type(type_t *type)
 497 {
 498         if(type->base.qualifiers == TYPE_QUALIFIER_NONE)
 499                 return type;
 500
 501         type_t *unqualified_type          = duplicate_type(type);
 502         unqualified_type->base.qualifiers = TYPE_QUALIFIER_NONE;
 503
 504         type_t *result = typehash_insert(unqualified_type);
 505         if(result != unqualified_type) {
 506                 obstack_free(type_obst, unqualified_type);
 507         }
 508
 509         return result;
 510 }
 511
 512 /**
 513  * Check if a type is valid.
 514  *
 515  * @param type  The type to check.
 516  * @return true if type represents a valid type.
 517  */
 518 bool type_valid(const type_t *type)
 519 {
 520         return type->kind != TYPE_INVALID;
 521 }
 522
 523 /**
 524  * Returns true if the given type is an integer type.
 525  *
 526  * @param type  The type to check.
 527  * @return True if type is an integer type.
 528  */
 529 bool is_type_integer(const type_t *type)
 530 {
 531         assert(!is_typeref(type));
 532
 533         if(type->kind == TYPE_ENUM)
 534                 return true;
 535
 536         if(type->kind != TYPE_ATOMIC)
 537                 return false;
 538
 539         switch(type->atomic.akind) {
 540         case ATOMIC_TYPE_BOOL:
 541         case ATOMIC_TYPE_CHAR:
 542         case ATOMIC_TYPE_SCHAR:
 543         case ATOMIC_TYPE_UCHAR:
 544         case ATOMIC_TYPE_SHORT:
 545         case ATOMIC_TYPE_USHORT:
 546         case ATOMIC_TYPE_INT:
 547         case ATOMIC_TYPE_UINT:
 548         case ATOMIC_TYPE_LONG:
 549         case ATOMIC_TYPE_ULONG:
 550         case ATOMIC_TYPE_LONGLONG:
 551         case ATOMIC_TYPE_ULONGLONG:
 552                 return true;
 553         default:
 554                 return false;
 555         }
 556 }
 557
 558 /**
 559  * Returns true if the given type is an floating point type.
 560  *
 561  * @param type  The type to check.
 562  * @return True if type is a floating point type.
 563  */
 564 bool is_type_float(const type_t *type)
 565 {
 566         assert(!is_typeref(type));
 567
 568         if(type->kind != TYPE_ATOMIC)
 569                 return false;
 570
 571         switch(type->atomic.akind) {
 572         case ATOMIC_TYPE_FLOAT:
 573         case ATOMIC_TYPE_DOUBLE:
 574         case ATOMIC_TYPE_LONG_DOUBLE:
 575 #ifdef PROVIDE_COMPLEX
 576         case ATOMIC_TYPE_FLOAT_COMPLEX:
 577         case ATOMIC_TYPE_DOUBLE_COMPLEX:
 578         case ATOMIC_TYPE_LONG_DOUBLE_COMPLEX:
 579         case ATOMIC_TYPE_FLOAT_IMAGINARY:
 580         case ATOMIC_TYPE_DOUBLE_IMAGINARY:
 581         case ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY:
 582 #endif
 583                 return true;
 584         default:
 585                 return false;
 586         }
 587 }
 588
 589 /**
 590  * Returns true if the given type is a signed type.
 591  *
 592  * @param type  The type to check.
 593  * @return True if type is a signed type.
 594  */
 595 bool is_type_signed(const type_t *type)
 596 {
 597         assert(!is_typeref(type));
 598
 599         /* enum types are int for now */
 600         if(type->kind == TYPE_ENUM)
 601                 return true;
 602
 603         if(type->kind != TYPE_ATOMIC)
 604                 return false;
 605
 606         switch(type->atomic.akind) {
 607         case ATOMIC_TYPE_CHAR:
 608         case ATOMIC_TYPE_SCHAR:
 609         case ATOMIC_TYPE_SHORT:
 610         case ATOMIC_TYPE_INT:
 611         case ATOMIC_TYPE_LONG:
 612         case ATOMIC_TYPE_LONGLONG:
 613         case ATOMIC_TYPE_FLOAT:
 614         case ATOMIC_TYPE_DOUBLE:
 615         case ATOMIC_TYPE_LONG_DOUBLE:
 616 #ifdef PROVIDE_COMPLEX
 617         case ATOMIC_TYPE_FLOAT_COMPLEX:
 618         case ATOMIC_TYPE_DOUBLE_COMPLEX:
 619         case ATOMIC_TYPE_LONG_DOUBLE_COMPLEX:
 620         case ATOMIC_TYPE_FLOAT_IMAGINARY:
 621         case ATOMIC_TYPE_DOUBLE_IMAGINARY:
 622         case ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY:
 623 #endif
 624                 return true;
 625
 626         case ATOMIC_TYPE_BOOL:
 627         case ATOMIC_TYPE_UCHAR:
 628         case ATOMIC_TYPE_USHORT:
 629         case ATOMIC_TYPE_UINT:
 630         case ATOMIC_TYPE_ULONG:
 631         case ATOMIC_TYPE_ULONGLONG:
 632                 return false;
 633
 634         case ATOMIC_TYPE_VOID:
 635         case ATOMIC_TYPE_INVALID:
 636         case ATOMIC_TYPE_LAST:
 637                 return false;
 638         }
 639
 640         panic("invalid atomic type found");
 641         return false;
 642 }
 643
 644 /**
 645  * Returns true if the given type represents an arithmetic type.
 646  *
 647  * @param type  The type to check.
 648  * @return True if type represents an arithmetic type.
 649  */
 650 bool is_type_arithmetic(const type_t *type)
 651 {
 652         assert(!is_typeref(type));
 653
 654         if(type->kind == TYPE_BITFIELD)
 655                 return true;
 656
 657         if(is_type_integer(type) || is_type_float(type))
 658                 return true;
 659
 660         return false;
 661 }
 662
 663 /**
 664  * Returns true if the given type represents a scalar type.
 665  *
 666  * @param type  The type to check.
 667  * @return True if type represents a scalar type.
 668  */
 669 bool is_type_scalar(const type_t *type)
 670 {
 671         assert(!is_typeref(type));
 672
 673         switch (type->kind) {
 674                 case TYPE_POINTER: return true;
 675                 case TYPE_BUILTIN: return is_type_scalar(type->builtin.real_type);
 676                 default:            break;
 677         }
 678
 679         return is_type_arithmetic(type);
 680 }
 681
 682 /**
 683  * Check if a given type is incomplete.
 684  *
 685  * @param type  The type to check.
 686  * @return True if the given type is incomplete (ie. just forward).
 687  */
 688 bool is_type_incomplete(const type_t *type)
 689 {
 690         assert(!is_typeref(type));
 691
 692         switch(type->kind) {
 693         case TYPE_COMPOUND_STRUCT:
 694         case TYPE_COMPOUND_UNION: {
 695                 const compound_type_t *compound_type = &type->compound;
 696                 declaration_t         *declaration   = compound_type->declaration;
 697                 return !declaration->init.is_defined;
 698         }
 699         case TYPE_ENUM: {
 700                 const enum_type_t *enum_type   = &type->enumt;
 701                 declaration_t     *declaration = enum_type->declaration;
 702                 return !declaration->init.is_defined;
 703         }
 704         case TYPE_BITFIELD:
 705         case TYPE_FUNCTION:
 706                 return true;
 707
 708         case TYPE_ARRAY:
 709                 return type->array.size == NULL;
 710
 711         case TYPE_ATOMIC:
 712                 return type->atomic.akind == ATOMIC_TYPE_VOID;
 713
 714         case TYPE_POINTER:
 715         case TYPE_BUILTIN:
 716         case TYPE_ERROR:
 717                 return false;
 718
 719         case TYPE_TYPEDEF:
 720         case TYPE_TYPEOF:
 721                 panic("is_type_incomplete called without typerefs skipped");
 722         case TYPE_INVALID:
 723                 break;
 724         }
 725
 726         panic("invalid type found");
 727 }
 728
 729 /**
 730  * Check if two function types are compatible.
 731  */
 732 static bool function_types_compatible(const function_type_t *func1,
 733                                       const function_type_t *func2)
 734 {
 735         const type_t* const ret1 = skip_typeref(func1->return_type);
 736         const type_t* const ret2 = skip_typeref(func2->return_type);
 737         if (!types_compatible(ret1, ret2))
 738                 return false;
 739
 740         /* can parameters be compared? */
 741         if(func1->unspecified_parameters || func2->unspecified_parameters)
 742                 return true;
 743
 744         if(func1->variadic != func2->variadic)
 745                 return false;
 746
 747         /* TODO: handling of unspecified parameters not correct yet */
 748
 749         /* all argument types must be compatible */
 750         function_parameter_t *parameter1 = func1->parameters;
 751         function_parameter_t *parameter2 = func2->parameters;
 752         for( ; parameter1 != NULL && parameter2 != NULL;
 753                         parameter1 = parameter1->next, parameter2 = parameter2->next) {
 754                 type_t *parameter1_type = skip_typeref(parameter1->type);
 755                 type_t *parameter2_type = skip_typeref(parameter2->type);
 756
 757                 parameter1_type = get_unqualified_type(parameter1_type);
 758                 parameter2_type = get_unqualified_type(parameter2_type);
 759
 760                 if(!types_compatible(parameter1_type, parameter2_type))
 761                         return false;
 762         }
 763         /* same number of arguments? */
 764         if(parameter1 != NULL || parameter2 != NULL)
 765                 return false;
 766
 767         return true;
 768 }
 769
 770 /**
 771  * Check if two array types are compatible.
 772  */
 773 static bool array_types_compatible(const array_type_t *array1,
 774                                    const array_type_t *array2)
 775 {
 776         type_t *element_type1 = skip_typeref(array1->element_type);
 777         type_t *element_type2 = skip_typeref(array2->element_type);
 778         if(!types_compatible(element_type1, element_type2))
 779                 return false;
 780
 781         if(array1->size != NULL && array2->size != NULL) {
 782                 /* TODO: check if size expression evaluate to the same value
 783                  * if they are constant */
 784         }
 785
 786         return true;
 787 }
 788
 789 /**
 790  * Check if two types are compatible.
 791  */
 792 bool types_compatible(const type_t *type1, const type_t *type2)
 793 {
 794         assert(!is_typeref(type1));
 795         assert(!is_typeref(type2));
 796
 797         /* shortcut: the same type is always compatible */
 798         if(type1 == type2)
 799                 return true;
 800
 801         if(type1->base.qualifiers != type2->base.qualifiers)
 802                 return false;
 803         if(type1->kind != type2->kind)
 804                 return false;
 805
 806         switch(type1->kind) {
 807         case TYPE_FUNCTION:
 808                 return function_types_compatible(&type1->function, &type2->function);
 809         case TYPE_ATOMIC:
 810                 return type1->atomic.akind == type2->atomic.akind;
 811         case TYPE_ARRAY:
 812                 return array_types_compatible(&type1->array, &type2->array);
 813
 814         case TYPE_POINTER: {
 815                 const type_t *const to1 = skip_typeref(type1->pointer.points_to);
 816                 const type_t *const to2 = skip_typeref(type2->pointer.points_to);
 817                 return types_compatible(to1, to2);
 818         }
 819
 820         case TYPE_COMPOUND_STRUCT:
 821         case TYPE_COMPOUND_UNION:
 822         case TYPE_ENUM:
 823         case TYPE_BUILTIN:
 824                 /* TODO: not implemented */
 825                 break;
 826
 827         case TYPE_BITFIELD:
 828                 /* not sure if this makes sense or is even needed, implement it if you
 829                  * really need it! */
 830                 panic("type compatibility check for bitfield type");
 831
 832         case TYPE_ERROR:
 833                 /* Hmm, the error type should be compatible to all other types */
 834                 return true;
 835         case TYPE_INVALID:
 836                 panic("invalid type found in compatible types");
 837         case TYPE_TYPEDEF:
 838         case TYPE_TYPEOF:
 839                 panic("typerefs not skipped in compatible types?!?");
 840         }
 841
 842         /* TODO: incomplete */
 843         return false;
 844 }
 845
 846 /**
 847  * Check if two pointer types are compatible.
 848  */
 849 bool pointers_compatible(const type_t *type1, const type_t *type2)
 850 {
 851         assert(!is_typeref(type1));
 852         assert(!is_typeref(type2));
 853
 854         assert(type1->kind == TYPE_POINTER);
 855         assert(type2->kind == TYPE_POINTER);
 856         /* TODO */
 857         return true;
 858 }
 859
 860 /**
 861  * Skip all typerefs and return the underlying type.
 862  */
 863 type_t *skip_typeref(type_t *type)
 864 {
 865         unsigned qualifiers = TYPE_QUALIFIER_NONE;
 866
 867         while(true) {
 868                 switch(type->kind) {
 869                 case TYPE_ERROR:
 870                         return type;
 871                 case TYPE_TYPEDEF: {
 872                         qualifiers |= type->base.qualifiers;
 873                         const typedef_type_t *typedef_type = &type->typedeft;
 874                         if(typedef_type->resolved_type != NULL) {
 875                                 type = typedef_type->resolved_type;
 876                                 break;
 877                         }
 878                         type = typedef_type->declaration->type;
 879                         continue;
 880                 }
 881                 case TYPE_TYPEOF: {
 882                         const typeof_type_t *typeof_type = &type->typeoft;
 883                         if(typeof_type->typeof_type != NULL) {
 884                                 type = typeof_type->typeof_type;
 885                         } else {
 886                                 type = typeof_type->expression->base.type;
 887                         }
 888                         continue;
 889                 }
 890                 default:
 891                         break;
 892                 }
 893                 break;
 894         }
 895
 896         if (qualifiers != TYPE_QUALIFIER_NONE) {
 897                 type_t *const copy     = duplicate_type(type);
 898                 copy->base.qualifiers |= qualifiers;
 899
 900                 type = typehash_insert(copy);
 901                 if (type != copy) {
 902                         obstack_free(type_obst, copy);
 903                 }
 904         }
 905
 906         return type;
 907 }
 908
 909 /**
 910  * Hash the given type and return the "singleton" version
 911  * of it.
 912  */
 913 static type_t *identify_new_type(type_t *type)
 914 {
 915         type_t *result = typehash_insert(type);
 916         if(result != type) {
 917                 obstack_free(type_obst, type);
 918         }
 919         return result;
 920 }
 921
 922 /**
 923  * Creates a new atomic type.
 924  *
 925  * @param akind       The kind of the atomic type.
 926  * @param qualifiers  Type qualifiers for the new type.
 927  */
 928 type_t *make_atomic_type(atomic_type_kind_t atype, type_qualifiers_t qualifiers)
 929 {
 930         type_t *type = obstack_alloc(type_obst, sizeof(atomic_type_t));
 931         memset(type, 0, sizeof(atomic_type_t));
 932
 933         type->kind            = TYPE_ATOMIC;
 934         type->base.qualifiers = qualifiers;
 935         type->atomic.akind    = atype;
 936
 937         return identify_new_type(type);
 938 }
 939
 940 /**
 941  * Creates a new pointer type.
 942  *
 943  * @param points_to   The points-to type for teh new type.
 944  * @param qualifiers  Type qualifiers for the new type.
 945  */
 946 type_t *make_pointer_type(type_t *points_to, type_qualifiers_t qualifiers)
 947 {
 948         type_t *type = obstack_alloc(type_obst, sizeof(pointer_type_t));
 949         memset(type, 0, sizeof(pointer_type_t));
 950
 951         type->kind              = TYPE_POINTER;
 952         type->base.qualifiers   = qualifiers;
 953         type->pointer.points_to = points_to;
 954
 955         return identify_new_type(type);
 956 }
 957
 958 /**
 959  * Debug helper. Prints the given type to stdout.
 960  */
 961 static __attribute__((unused))
 962 void dbg_type(const type_t *type)
 963 {
 964         FILE *old_out = out;
 965         out = stderr;
 966         print_type(type);
 967         puts("\n");
 968         fflush(stderr);
 969         out = old_out;
 970 }