nsz Git - cparser/blob - type.c

   1 /*
   2  * This file is part of cparser.
   3  * Copyright (C) 2007-2008 Matthias Braun <matze@braunis.de>
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  18  * 02111-1307, USA.
  19  */
  20 #include <config.h>
  21
  22 #include <stdio.h>
  23 #include <assert.h>
  24
  25 #include "type_t.h"
  26 #include "symbol_t.h"
  27 #include "type_hash.h"
  28 #include "adt/error.h"
  29 #include "lang_features.h"
  30
  31 static struct obstack   _type_obst;
  32 static FILE            *out;
  33 struct obstack         *type_obst                 = &_type_obst;
  34 static int              type_visited              = 0;
  35 static bool             print_implicit_array_size = false;
  36
  37 static void intern_print_type_pre(const type_t *type, bool top);
  38 static void intern_print_type_post(const type_t *type, bool top);
  39
  40 void init_types(void)
  41 {
  42         obstack_init(type_obst);
  43 }
  44
  45 void exit_types(void)
  46 {
  47         obstack_free(type_obst, NULL);
  48 }
  49
  50 void type_set_output(FILE *stream)
  51 {
  52         out = stream;
  53 }
  54
  55 void inc_type_visited(void)
  56 {
  57         type_visited++;
  58 }
  59
  60 void print_type_qualifiers(type_qualifiers_t qualifiers)
  61 {
  62         if(qualifiers & TYPE_QUALIFIER_CONST)    fputs("const ",    out);
  63         if(qualifiers & TYPE_QUALIFIER_VOLATILE) fputs("volatile ", out);
  64         if(qualifiers & TYPE_QUALIFIER_RESTRICT) fputs("restrict ", out);
  65 }
  66
  67 /**
  68  * Prints the name of a atomic type.
  69  *
  70  * @param type  The type.
  71  */
  72 static
  73 void print_atomic_type(const atomic_type_t *type)
  74 {
  75         print_type_qualifiers(type->type.qualifiers);
  76
  77         const char *s = "INVALIDATOMIC";
  78         switch((atomic_type_kind_t) type->akind) {
  79         case ATOMIC_TYPE_INVALID:     break;
  80         case ATOMIC_TYPE_VOID:                  s = "void";               break;
  81         case ATOMIC_TYPE_BOOL:                  s = "_Bool";              break;
  82         case ATOMIC_TYPE_CHAR:                  s = "char";               break;
  83         case ATOMIC_TYPE_SCHAR:                 s = "signed char";        break;
  84         case ATOMIC_TYPE_UCHAR:                 s = "unsigned char";      break;
  85         case ATOMIC_TYPE_INT:                   s = "int";                break;
  86         case ATOMIC_TYPE_UINT:                  s = "unsigned int";       break;
  87         case ATOMIC_TYPE_SHORT:                 s = "short";              break;
  88         case ATOMIC_TYPE_USHORT:                s = "unsigned short";     break;
  89         case ATOMIC_TYPE_LONG:                  s = "long";               break;
  90         case ATOMIC_TYPE_ULONG:                 s = "unsigned long";      break;
  91         case ATOMIC_TYPE_LONGLONG:              s = "long long";          break;
  92         case ATOMIC_TYPE_ULONGLONG:             s = "unsigned long long"; break;
  93         case ATOMIC_TYPE_LONG_DOUBLE:           s = "long double";        break;
  94         case ATOMIC_TYPE_FLOAT:                 s = "float";              break;
  95         case ATOMIC_TYPE_DOUBLE:                s = "double";             break;
  96         case ATOMIC_TYPE_FLOAT_COMPLEX:         s = "_Complex float";     break;
  97         case ATOMIC_TYPE_DOUBLE_COMPLEX:        s = "_Complex float";     break;
  98         case ATOMIC_TYPE_LONG_DOUBLE_COMPLEX:   s = "_Complex float";     break;
  99         case ATOMIC_TYPE_FLOAT_IMAGINARY:       s = "_Imaginary float";   break;
 100         case ATOMIC_TYPE_DOUBLE_IMAGINARY:      s = "_Imaginary float";   break;
 101         case ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY: s = "_Imaginary float";   break;
 102         }
 103         fputs(s, out);
 104 }
 105
 106 /**
 107  * Print the first part (the prefix) of a type.
 108  *
 109  * @param type   The type to print.
 110  * @param top    true, if this is the top type, false if it's an embedded type.
 111  */
 112 static void print_function_type_pre(const function_type_t *type, bool top)
 113 {
 114         print_type_qualifiers(type->type.qualifiers);
 115
 116         intern_print_type_pre(type->return_type, false);
 117
 118         /* don't emit braces if we're the toplevel type... */
 119         if(!top)
 120                 fputc('(', out);
 121 }
 122
 123 /**
 124  * Print the second part (the postfix) of a type.
 125  *
 126  * @param type   The type to print.
 127  * @param top    true, if this is the top type, false if it's an embedded type.
 128  */
 129 static void print_function_type_post(const function_type_t *type,
 130                                      const scope_t *scope, bool top)
 131 {
 132         intern_print_type_post(type->return_type, false);
 133         /* don't emit braces if we're the toplevel type... */
 134         if(!top)
 135                 fputc(')', out);
 136
 137         fputc('(', out);
 138
 139         int first = 1;
 140         if(scope == NULL) {
 141                 function_parameter_t *parameter = type->parameters;
 142                 for( ; parameter != NULL; parameter = parameter->next) {
 143                         if(first) {
 144                                 first = 0;
 145                         } else {
 146                                 fputs(", ", out);
 147                         }
 148                         print_type(parameter->type);
 149                 }
 150         } else {
 151                 declaration_t *parameter = scope->declarations;
 152                 for( ; parameter != NULL; parameter = parameter->next) {
 153                         if(first) {
 154                                 first = 0;
 155                         } else {
 156                                 fputs(", ", out);
 157                         }
 158                         print_type_ext(parameter->type, parameter->symbol,
 159                                        &parameter->scope);
 160                 }
 161         }
 162         if(type->variadic) {
 163                 if(first) {
 164                         first = 0;
 165                 } else {
 166                         fputs(", ", out);
 167                 }
 168                 fputs("...", out);
 169         }
 170         if(first && !type->unspecified_parameters) {
 171                 fputs("void", out);
 172         }
 173         fputc(')', out);
 174 }
 175
 176 /**
 177  * Prints the prefix part of a pointer type.
 178  *
 179  * @param type   The pointer type.
 180  */
 181 static void print_pointer_type_pre(const pointer_type_t *type)
 182 {
 183         intern_print_type_pre(type->points_to, false);
 184         fputs("*", out);
 185         print_type_qualifiers(type->type.qualifiers);
 186 }
 187
 188 /**
 189  * Prints the postfix part of a pointer type.
 190  *
 191  * @param type   The pointer type.
 192  */
 193 static void print_pointer_type_post(const pointer_type_t *type)
 194 {
 195         intern_print_type_post(type->points_to, false);
 196 }
 197
 198 /**
 199  * Prints the prefix part of an array type.
 200  *
 201  * @param type   The array type.
 202  */
 203 static void print_array_type_pre(const array_type_t *type)
 204 {
 205         intern_print_type_pre(type->element_type, false);
 206 }
 207
 208 /**
 209  * Prints the postfix part of an array type.
 210  *
 211  * @param type   The array type.
 212  */
 213 static void print_array_type_post(const array_type_t *type)
 214 {
 215         fputc('[', out);
 216         if(type->is_static) {
 217                 fputs("static ", out);
 218         }
 219         print_type_qualifiers(type->type.qualifiers);
 220         if(type->size_expression != NULL
 221                         && (print_implicit_array_size || !type->has_implicit_size)) {
 222                 print_expression(type->size_expression);
 223         }
 224         fputc(']', out);
 225         intern_print_type_post(type->element_type, false);
 226 }
 227
 228 /**
 229  * Prints the postfix part of a bitfield type.
 230  *
 231  * @param type   The array type.
 232  */
 233 static void print_bitfield_type_post(const bitfield_type_t *type)
 234 {
 235         fputs(" : ", out);
 236         print_expression(type->size);
 237         intern_print_type_post(type->base, false);
 238 }
 239
 240 /**
 241  * Prints an enum definition.
 242  *
 243  * @param declaration  The enum's type declaration.
 244  */
 245 void print_enum_definition(const declaration_t *declaration)
 246 {
 247         fputs("{\n", out);
 248
 249         change_indent(1);
 250
 251         declaration_t *entry = declaration->next;
 252         for( ; entry != NULL && entry->storage_class == STORAGE_CLASS_ENUM_ENTRY;
 253                entry = entry->next) {
 254
 255                 print_indent();
 256                 fprintf(out, "%s", entry->symbol->string);
 257                 if(entry->init.initializer != NULL) {
 258                         fprintf(out, " = ");
 259
 260                         /* skip the implicit cast */
 261                         expression_t *expression = entry->init.enum_value;
 262                         if(expression->kind == EXPR_UNARY_CAST_IMPLICIT) {
 263                                 expression = expression->unary.value;
 264                         }
 265                         print_expression(expression);
 266                 }
 267                 fprintf(out, ",\n");
 268         }
 269
 270         change_indent(-1);
 271         print_indent();
 272         fputs("}", out);
 273 }
 274
 275 /**
 276  * Prints an enum type.
 277  *
 278  * @param type  The enum type.
 279  */
 280 static void print_type_enum(const enum_type_t *type)
 281 {
 282         print_type_qualifiers(type->type.qualifiers);
 283         fputs("enum ", out);
 284
 285         declaration_t *declaration = type->declaration;
 286         symbol_t      *symbol      = declaration->symbol;
 287         if(symbol != NULL) {
 288                 fputs(symbol->string, out);
 289         } else {
 290                 print_enum_definition(declaration);
 291         }
 292 }
 293
 294 /**
 295  * Print the compound part of a compound type.
 296  *
 297  * @param declaration  The declaration of the compound type.
 298  */
 299 void print_compound_definition(const declaration_t *declaration)
 300 {
 301         fputs("{\n", out);
 302         change_indent(1);
 303
 304         declaration_t *iter = declaration->scope.declarations;
 305         for( ; iter != NULL; iter = iter->next) {
 306                 print_indent();
 307                 print_declaration(iter);
 308                 fputc('\n', out);
 309         }
 310
 311         change_indent(-1);
 312         print_indent();
 313         fputs("}", out);
 314 }
 315
 316 /**
 317  * Prints a compound type.
 318  *
 319  * @param type  The compound type.
 320  */
 321 static void print_compound_type(const compound_type_t *type)
 322 {
 323         print_type_qualifiers(type->type.qualifiers);
 324
 325         if(type->type.kind == TYPE_COMPOUND_STRUCT) {
 326                 fputs("struct ", out);
 327         } else {
 328                 assert(type->type.kind == TYPE_COMPOUND_UNION);
 329                 fputs("union ", out);
 330         }
 331
 332         declaration_t *declaration = type->declaration;
 333         symbol_t      *symbol      = declaration->symbol;
 334         if(symbol != NULL) {
 335                 fputs(symbol->string, out);
 336         } else {
 337                 print_compound_definition(declaration);
 338         }
 339 }
 340
 341 /**
 342  * Prints the prefix part of a typedef type.
 343  *
 344  * @param type   The typedef type.
 345  */
 346 static void print_typedef_type_pre(const typedef_type_t *const type)
 347 {
 348         print_type_qualifiers(type->type.qualifiers);
 349         fputs(type->declaration->symbol->string, out);
 350 }
 351
 352 /**
 353  * Prints the prefix part of a typeof type.
 354  *
 355  * @param type   The typeof type.
 356  */
 357 static void print_typeof_type_pre(const typeof_type_t *const type)
 358 {
 359         fputs("typeof(", out);
 360         if(type->expression != NULL) {
 361                 assert(type->typeof_type == NULL);
 362                 print_expression(type->expression);
 363         } else {
 364                 print_type(type->typeof_type);
 365         }
 366         fputc(')', out);
 367 }
 368
 369 /**
 370  * Prints the prefix part of a type.
 371  *
 372  * @param type   The type.
 373  * @param top    true if we print the toplevel type, false else.
 374  */
 375 static void intern_print_type_pre(const type_t *const type, const bool top)
 376 {
 377         switch(type->kind) {
 378         case TYPE_ERROR:
 379                 fputs("<error>", out);
 380         case TYPE_INVALID:
 381                 fputs("<invalid>", out);
 382                 return;
 383         case TYPE_ENUM:
 384                 print_type_enum(&type->enumt);
 385                 return;
 386         case TYPE_ATOMIC:
 387                 print_atomic_type(&type->atomic);
 388                 return;
 389         case TYPE_COMPOUND_STRUCT:
 390         case TYPE_COMPOUND_UNION:
 391                 print_compound_type(&type->compound);
 392                 return;
 393         case TYPE_BUILTIN:
 394                 fputs(type->builtin.symbol->string, out);
 395                 return;
 396         case TYPE_FUNCTION:
 397                 print_function_type_pre(&type->function, top);
 398                 return;
 399         case TYPE_POINTER:
 400                 print_pointer_type_pre(&type->pointer);
 401                 return;
 402         case TYPE_BITFIELD:
 403                 intern_print_type_pre(type->bitfield.base, top);
 404                 return;
 405         case TYPE_ARRAY:
 406                 print_array_type_pre(&type->array);
 407                 return;
 408         case TYPE_TYPEDEF:
 409                 print_typedef_type_pre(&type->typedeft);
 410                 return;
 411         case TYPE_TYPEOF:
 412                 print_typeof_type_pre(&type->typeoft);
 413                 return;
 414         }
 415         fputs("unknown", out);
 416 }
 417
 418 /**
 419  * Prints the postfix part of a type.
 420  *
 421  * @param type   The type.
 422  * @param top    true if we print the toplevel type, false else.
 423  */
 424 static void intern_print_type_post(const type_t *const type, const bool top)
 425 {
 426         switch(type->kind) {
 427         case TYPE_FUNCTION:
 428                 print_function_type_post(&type->function, NULL, top);
 429                 return;
 430         case TYPE_POINTER:
 431                 print_pointer_type_post(&type->pointer);
 432                 return;
 433         case TYPE_ARRAY:
 434                 print_array_type_post(&type->array);
 435                 return;
 436         case TYPE_BITFIELD:
 437                 print_bitfield_type_post(&type->bitfield);
 438                 return;
 439         case TYPE_ERROR:
 440         case TYPE_INVALID:
 441         case TYPE_ATOMIC:
 442         case TYPE_ENUM:
 443         case TYPE_COMPOUND_STRUCT:
 444         case TYPE_COMPOUND_UNION:
 445         case TYPE_BUILTIN:
 446         case TYPE_TYPEOF:
 447         case TYPE_TYPEDEF:
 448                 break;
 449         }
 450 }
 451
 452 /**
 453  * Prints a type.
 454  *
 455  * @param type   The type.
 456  */
 457 void print_type(const type_t *const type)
 458 {
 459         print_type_ext(type, NULL, NULL);
 460 }
 461
 462 void print_type_ext(const type_t *const type, const symbol_t *symbol,
 463                     const scope_t *scope)
 464 {
 465         if(type == NULL) {
 466                 fputs("nil type", out);
 467                 return;
 468         }
 469
 470         intern_print_type_pre(type, true);
 471         if(symbol != NULL) {
 472                 fputc(' ', out);
 473                 fputs(symbol->string, out);
 474         }
 475         if(type->kind == TYPE_FUNCTION) {
 476                 print_function_type_post(&type->function, scope, true);
 477         } else {
 478                 intern_print_type_post(type, true);
 479         }
 480 }
 481
 482 /**
 483  * Return the size of a type AST node.
 484  *
 485  * @param type  The type.
 486  */
 487 static size_t get_type_size(const type_t *type)
 488 {
 489         switch(type->kind) {
 490         case TYPE_ATOMIC:          return sizeof(atomic_type_t);
 491         case TYPE_COMPOUND_STRUCT:
 492         case TYPE_COMPOUND_UNION:  return sizeof(compound_type_t);
 493         case TYPE_ENUM:            return sizeof(enum_type_t);
 494         case TYPE_FUNCTION:        return sizeof(function_type_t);
 495         case TYPE_POINTER:         return sizeof(pointer_type_t);
 496         case TYPE_ARRAY:           return sizeof(array_type_t);
 497         case TYPE_BUILTIN:         return sizeof(builtin_type_t);
 498         case TYPE_TYPEDEF:         return sizeof(typedef_type_t);
 499         case TYPE_TYPEOF:          return sizeof(typeof_type_t);
 500         case TYPE_BITFIELD:        return sizeof(bitfield_type_t);
 501         case TYPE_ERROR:           panic("error type found");
 502         case TYPE_INVALID:         panic("invalid type found");
 503         }
 504         panic("unknown type found");
 505 }
 506
 507 /**
 508  * Duplicates a type.
 509  *
 510  * @param type  The type to copy.
 511  * @return A copy of the type.
 512  *
 513  * @note This does not produce a deep copy!
 514  */
 515 type_t *duplicate_type(const type_t *type)
 516 {
 517         size_t size = get_type_size(type);
 518
 519         type_t *copy = obstack_alloc(type_obst, size);
 520         memcpy(copy, type, size);
 521
 522         return copy;
 523 }
 524
 525 /**
 526  * Returns the unqualified type of a given type.
 527  *
 528  * @param type  The type.
 529  * @returns The unqualified type.
 530  */
 531 type_t *get_unqualified_type(type_t *type)
 532 {
 533         if(type->base.qualifiers == TYPE_QUALIFIER_NONE)
 534                 return type;
 535
 536         type_t *unqualified_type          = duplicate_type(type);
 537         unqualified_type->base.qualifiers = TYPE_QUALIFIER_NONE;
 538
 539         type_t *result = typehash_insert(unqualified_type);
 540         if(result != unqualified_type) {
 541                 obstack_free(type_obst, unqualified_type);
 542         }
 543
 544         return result;
 545 }
 546
 547 /**
 548  * Check if a type is valid.
 549  *
 550  * @param type  The type to check.
 551  * @return true if type represents a valid type.
 552  */
 553 bool type_valid(const type_t *type)
 554 {
 555         return type->kind != TYPE_INVALID;
 556 }
 557
 558 /**
 559  * Returns true if the given type is an integer type.
 560  *
 561  * @param type  The type to check.
 562  * @return True if type is an integer type.
 563  */
 564 bool is_type_integer(const type_t *type)
 565 {
 566         assert(!is_typeref(type));
 567
 568         if(type->kind == TYPE_ENUM)
 569                 return true;
 570
 571         if(type->kind != TYPE_ATOMIC)
 572                 return false;
 573
 574         switch((atomic_type_kind_t) type->atomic.akind) {
 575         case ATOMIC_TYPE_BOOL:
 576         case ATOMIC_TYPE_CHAR:
 577         case ATOMIC_TYPE_SCHAR:
 578         case ATOMIC_TYPE_UCHAR:
 579         case ATOMIC_TYPE_SHORT:
 580         case ATOMIC_TYPE_USHORT:
 581         case ATOMIC_TYPE_INT:
 582         case ATOMIC_TYPE_UINT:
 583         case ATOMIC_TYPE_LONG:
 584         case ATOMIC_TYPE_ULONG:
 585         case ATOMIC_TYPE_LONGLONG:
 586         case ATOMIC_TYPE_ULONGLONG:
 587                 return true;
 588
 589         case ATOMIC_TYPE_INVALID:
 590         case ATOMIC_TYPE_VOID:
 591         case ATOMIC_TYPE_FLOAT:
 592         case ATOMIC_TYPE_DOUBLE:
 593         case ATOMIC_TYPE_LONG_DOUBLE:
 594         case ATOMIC_TYPE_FLOAT_COMPLEX:
 595         case ATOMIC_TYPE_DOUBLE_COMPLEX:
 596         case ATOMIC_TYPE_LONG_DOUBLE_COMPLEX:
 597         case ATOMIC_TYPE_FLOAT_IMAGINARY:
 598         case ATOMIC_TYPE_DOUBLE_IMAGINARY:
 599         case ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY:
 600                 return false;
 601         }
 602
 603         panic("unexpected atomic type kind");
 604 }
 605
 606 /**
 607  * Returns true if the given type is an floating point type.
 608  *
 609  * @param type  The type to check.
 610  * @return True if type is a floating point type.
 611  */
 612 bool is_type_float(const type_t *type)
 613 {
 614         assert(!is_typeref(type));
 615
 616         if(type->kind != TYPE_ATOMIC)
 617                 return false;
 618
 619         switch((atomic_type_kind_t) type->atomic.akind) {
 620         case ATOMIC_TYPE_FLOAT:
 621         case ATOMIC_TYPE_DOUBLE:
 622         case ATOMIC_TYPE_LONG_DOUBLE:
 623         case ATOMIC_TYPE_FLOAT_COMPLEX:
 624         case ATOMIC_TYPE_DOUBLE_COMPLEX:
 625         case ATOMIC_TYPE_LONG_DOUBLE_COMPLEX:
 626         case ATOMIC_TYPE_FLOAT_IMAGINARY:
 627         case ATOMIC_TYPE_DOUBLE_IMAGINARY:
 628         case ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY:
 629                 return true;
 630
 631         case ATOMIC_TYPE_INVALID:
 632         case ATOMIC_TYPE_VOID:
 633         case ATOMIC_TYPE_BOOL:
 634         case ATOMIC_TYPE_CHAR:
 635         case ATOMIC_TYPE_SCHAR:
 636         case ATOMIC_TYPE_UCHAR:
 637         case ATOMIC_TYPE_SHORT:
 638         case ATOMIC_TYPE_USHORT:
 639         case ATOMIC_TYPE_INT:
 640         case ATOMIC_TYPE_UINT:
 641         case ATOMIC_TYPE_LONG:
 642         case ATOMIC_TYPE_ULONG:
 643         case ATOMIC_TYPE_LONGLONG:
 644         case ATOMIC_TYPE_ULONGLONG:
 645                 return false;
 646         }
 647
 648         panic("unexpected atomic type kind");
 649 }
 650
 651 /**
 652  * Returns true if the given type is a signed type.
 653  *
 654  * @param type  The type to check.
 655  * @return True if type is a signed type.
 656  */
 657 bool is_type_signed(const type_t *type)
 658 {
 659         assert(!is_typeref(type));
 660
 661         /* enum types are int for now */
 662         if(type->kind == TYPE_ENUM)
 663                 return true;
 664
 665         if(type->kind != TYPE_ATOMIC)
 666                 return false;
 667
 668         switch((atomic_type_kind_t) type->atomic.akind) {
 669         case ATOMIC_TYPE_CHAR:
 670         case ATOMIC_TYPE_SCHAR:
 671         case ATOMIC_TYPE_SHORT:
 672         case ATOMIC_TYPE_INT:
 673         case ATOMIC_TYPE_LONG:
 674         case ATOMIC_TYPE_LONGLONG:
 675         case ATOMIC_TYPE_FLOAT:
 676         case ATOMIC_TYPE_DOUBLE:
 677         case ATOMIC_TYPE_LONG_DOUBLE:
 678         case ATOMIC_TYPE_FLOAT_COMPLEX:
 679         case ATOMIC_TYPE_DOUBLE_COMPLEX:
 680         case ATOMIC_TYPE_LONG_DOUBLE_COMPLEX:
 681         case ATOMIC_TYPE_FLOAT_IMAGINARY:
 682         case ATOMIC_TYPE_DOUBLE_IMAGINARY:
 683         case ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY:
 684                 return true;
 685
 686         case ATOMIC_TYPE_BOOL:
 687         case ATOMIC_TYPE_UCHAR:
 688         case ATOMIC_TYPE_USHORT:
 689         case ATOMIC_TYPE_UINT:
 690         case ATOMIC_TYPE_ULONG:
 691         case ATOMIC_TYPE_ULONGLONG:
 692                 return false;
 693
 694         case ATOMIC_TYPE_VOID:
 695         case ATOMIC_TYPE_INVALID:
 696                 return false;
 697         }
 698
 699         panic("invalid atomic type found");
 700         return false;
 701 }
 702
 703 /**
 704  * Returns true if the given type represents an arithmetic type.
 705  *
 706  * @param type  The type to check.
 707  * @return True if type represents an arithmetic type.
 708  */
 709 bool is_type_arithmetic(const type_t *type)
 710 {
 711         assert(!is_typeref(type));
 712
 713         if(type->kind == TYPE_BITFIELD)
 714                 return true;
 715
 716         if(is_type_integer(type) || is_type_float(type))
 717                 return true;
 718
 719         return false;
 720 }
 721
 722 /**
 723  * Returns true if the given type represents a scalar type.
 724  *
 725  * @param type  The type to check.
 726  * @return True if type represents a scalar type.
 727  */
 728 bool is_type_scalar(const type_t *type)
 729 {
 730         assert(!is_typeref(type));
 731
 732         switch (type->kind) {
 733                 case TYPE_POINTER: return true;
 734                 case TYPE_BUILTIN: return is_type_scalar(type->builtin.real_type);
 735                 default:            break;
 736         }
 737
 738         return is_type_arithmetic(type);
 739 }
 740
 741 /**
 742  * Check if a given type is incomplete.
 743  *
 744  * @param type  The type to check.
 745  * @return True if the given type is incomplete (ie. just forward).
 746  */
 747 bool is_type_incomplete(const type_t *type)
 748 {
 749         assert(!is_typeref(type));
 750
 751         switch(type->kind) {
 752         case TYPE_COMPOUND_STRUCT:
 753         case TYPE_COMPOUND_UNION: {
 754                 const compound_type_t *compound_type = &type->compound;
 755                 declaration_t         *declaration   = compound_type->declaration;
 756                 return !declaration->init.is_defined;
 757         }
 758         case TYPE_ENUM: {
 759                 const enum_type_t *enum_type   = &type->enumt;
 760                 declaration_t     *declaration = enum_type->declaration;
 761                 return !declaration->init.is_defined;
 762         }
 763         case TYPE_BITFIELD:
 764         case TYPE_FUNCTION:
 765                 return true;
 766
 767         case TYPE_ARRAY:
 768                 return type->array.size_expression == NULL;
 769
 770         case TYPE_ATOMIC:
 771                 return type->atomic.akind == ATOMIC_TYPE_VOID;
 772
 773         case TYPE_POINTER:
 774         case TYPE_BUILTIN:
 775         case TYPE_ERROR:
 776                 return false;
 777
 778         case TYPE_TYPEDEF:
 779         case TYPE_TYPEOF:
 780                 panic("is_type_incomplete called without typerefs skipped");
 781         case TYPE_INVALID:
 782                 break;
 783         }
 784
 785         panic("invalid type found");
 786 }
 787
 788 /**
 789  * Check if two function types are compatible.
 790  */
 791 static bool function_types_compatible(const function_type_t *func1,
 792                                       const function_type_t *func2)
 793 {
 794         const type_t* const ret1 = skip_typeref(func1->return_type);
 795         const type_t* const ret2 = skip_typeref(func2->return_type);
 796         if (!types_compatible(ret1, ret2))
 797                 return false;
 798
 799         /* can parameters be compared? */
 800         if(func1->unspecified_parameters || func2->unspecified_parameters)
 801                 return true;
 802
 803         if(func1->variadic != func2->variadic)
 804                 return false;
 805
 806         /* TODO: handling of unspecified parameters not correct yet */
 807
 808         /* all argument types must be compatible */
 809         function_parameter_t *parameter1 = func1->parameters;
 810         function_parameter_t *parameter2 = func2->parameters;
 811         for( ; parameter1 != NULL && parameter2 != NULL;
 812                         parameter1 = parameter1->next, parameter2 = parameter2->next) {
 813                 type_t *parameter1_type = skip_typeref(parameter1->type);
 814                 type_t *parameter2_type = skip_typeref(parameter2->type);
 815
 816                 parameter1_type = get_unqualified_type(parameter1_type);
 817                 parameter2_type = get_unqualified_type(parameter2_type);
 818
 819                 if(!types_compatible(parameter1_type, parameter2_type))
 820                         return false;
 821         }
 822         /* same number of arguments? */
 823         if(parameter1 != NULL || parameter2 != NULL)
 824                 return false;
 825
 826         return true;
 827 }
 828
 829 /**
 830  * Check if two array types are compatible.
 831  */
 832 static bool array_types_compatible(const array_type_t *array1,
 833                                    const array_type_t *array2)
 834 {
 835         type_t *element_type1 = skip_typeref(array1->element_type);
 836         type_t *element_type2 = skip_typeref(array2->element_type);
 837         if(!types_compatible(element_type1, element_type2))
 838                 return false;
 839
 840         if(!array1->size_constant || !array2->size_constant)
 841                 return true;
 842
 843         return array1->size == array2->size;
 844 }
 845
 846 /**
 847  * Check if two types are compatible.
 848  */
 849 bool types_compatible(const type_t *type1, const type_t *type2)
 850 {
 851         assert(!is_typeref(type1));
 852         assert(!is_typeref(type2));
 853
 854         /* shortcut: the same type is always compatible */
 855         if(type1 == type2)
 856                 return true;
 857
 858         if(type1->base.qualifiers != type2->base.qualifiers)
 859                 return false;
 860         if(type1->kind != type2->kind)
 861                 return false;
 862
 863         switch(type1->kind) {
 864         case TYPE_FUNCTION:
 865                 return function_types_compatible(&type1->function, &type2->function);
 866         case TYPE_ATOMIC:
 867                 return type1->atomic.akind == type2->atomic.akind;
 868         case TYPE_ARRAY:
 869                 return array_types_compatible(&type1->array, &type2->array);
 870
 871         case TYPE_POINTER: {
 872                 const type_t *const to1 = skip_typeref(type1->pointer.points_to);
 873                 const type_t *const to2 = skip_typeref(type2->pointer.points_to);
 874                 return types_compatible(to1, to2);
 875         }
 876
 877         case TYPE_COMPOUND_STRUCT:
 878         case TYPE_COMPOUND_UNION:
 879         case TYPE_ENUM:
 880         case TYPE_BUILTIN:
 881                 /* TODO: not implemented */
 882                 break;
 883
 884         case TYPE_BITFIELD:
 885                 /* not sure if this makes sense or is even needed, implement it if you
 886                  * really need it! */
 887                 panic("type compatibility check for bitfield type");
 888
 889         case TYPE_ERROR:
 890                 /* Hmm, the error type should be compatible to all other types */
 891                 return true;
 892         case TYPE_INVALID:
 893                 panic("invalid type found in compatible types");
 894         case TYPE_TYPEDEF:
 895         case TYPE_TYPEOF:
 896                 panic("typerefs not skipped in compatible types?!?");
 897         }
 898
 899         /* TODO: incomplete */
 900         return false;
 901 }
 902
 903 /**
 904  * Check if two pointer types are compatible.
 905  */
 906 bool pointers_compatible(const type_t *type1, const type_t *type2)
 907 {
 908         assert(!is_typeref(type1));
 909         assert(!is_typeref(type2));
 910
 911         assert(type1->kind == TYPE_POINTER);
 912         assert(type2->kind == TYPE_POINTER);
 913         (void) type1;
 914         (void) type2;
 915         /* TODO */
 916         return true;
 917 }
 918
 919 /**
 920  * Skip all typerefs and return the underlying type.
 921  */
 922 type_t *skip_typeref(type_t *type)
 923 {
 924         unsigned qualifiers = TYPE_QUALIFIER_NONE;
 925
 926         while(true) {
 927                 switch(type->kind) {
 928                 case TYPE_ERROR:
 929                         return type;
 930                 case TYPE_TYPEDEF: {
 931                         qualifiers |= type->base.qualifiers;
 932                         const typedef_type_t *typedef_type = &type->typedeft;
 933                         if(typedef_type->resolved_type != NULL) {
 934                                 type = typedef_type->resolved_type;
 935                                 break;
 936                         }
 937                         type = typedef_type->declaration->type;
 938                         continue;
 939                 }
 940                 case TYPE_TYPEOF: {
 941                         const typeof_type_t *typeof_type = &type->typeoft;
 942                         if(typeof_type->typeof_type != NULL) {
 943                                 type = typeof_type->typeof_type;
 944                         } else {
 945                                 type = typeof_type->expression->base.type;
 946                         }
 947                         continue;
 948                 }
 949                 default:
 950                         break;
 951                 }
 952                 break;
 953         }
 954
 955         if (qualifiers != TYPE_QUALIFIER_NONE) {
 956                 type_t *const copy     = duplicate_type(type);
 957                 copy->base.qualifiers |= qualifiers;
 958
 959                 type = typehash_insert(copy);
 960                 if (type != copy) {
 961                         obstack_free(type_obst, copy);
 962                 }
 963         }
 964
 965         return type;
 966 }
 967
 968 unsigned get_atomic_type_size(atomic_type_kind_t kind)
 969 {
 970         switch(kind) {
 971         case ATOMIC_TYPE_CHAR:
 972         case ATOMIC_TYPE_SCHAR:
 973         case ATOMIC_TYPE_UCHAR:
 974                 return 1;
 975
 976         case ATOMIC_TYPE_SHORT:
 977         case ATOMIC_TYPE_USHORT:
 978                 return 2;
 979
 980         case ATOMIC_TYPE_BOOL:
 981         case ATOMIC_TYPE_INT:
 982         case ATOMIC_TYPE_UINT:
 983                 return machine_size >> 3;
 984
 985         case ATOMIC_TYPE_LONG:
 986         case ATOMIC_TYPE_ULONG:
 987                 return machine_size > 16 ? machine_size >> 3 : 4;
 988
 989         case ATOMIC_TYPE_LONGLONG:
 990         case ATOMIC_TYPE_ULONGLONG:
 991                 return machine_size > 16 ? 8 : 4;
 992
 993         case ATOMIC_TYPE_FLOAT_IMAGINARY:
 994         case ATOMIC_TYPE_FLOAT:
 995                 return 4;
 996
 997         case ATOMIC_TYPE_DOUBLE_IMAGINARY:
 998         case ATOMIC_TYPE_DOUBLE:
 999                 return 8;
1000
1001         case ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY:
1002         case ATOMIC_TYPE_LONG_DOUBLE:
1003                 return 12;
1004
1005         case ATOMIC_TYPE_VOID:
1006                 return 1;
1007
1008         case ATOMIC_TYPE_FLOAT_COMPLEX:
1009                 return 2 * get_atomic_type_size(ATOMIC_TYPE_FLOAT);
1010
1011         case ATOMIC_TYPE_DOUBLE_COMPLEX:
1012                 return 2 * get_atomic_type_size(ATOMIC_TYPE_DOUBLE);
1013
1014         case ATOMIC_TYPE_LONG_DOUBLE_COMPLEX:
1015                 return 2 * get_atomic_type_size(ATOMIC_TYPE_LONG_DOUBLE);
1016
1017         case ATOMIC_TYPE_INVALID:
1018                 break;
1019         }
1020         panic("Trying to determine size of invalid atomic type");
1021 }
1022
1023 /**
1024  * Find the atomic type kind representing a given size (signed).
1025  */
1026 atomic_type_kind_t find_signed_int_atomic_type_kind_for_size(unsigned size) {
1027         static atomic_type_kind_t kinds[32];
1028
1029         assert(size < 32);
1030         atomic_type_kind_t kind = kinds[size];
1031         if(kind == ATOMIC_TYPE_INVALID) {
1032                 static const atomic_type_kind_t possible_kinds[] = {
1033                         ATOMIC_TYPE_SCHAR,
1034                         ATOMIC_TYPE_SHORT,
1035                         ATOMIC_TYPE_INT,
1036                         ATOMIC_TYPE_LONG,
1037                         ATOMIC_TYPE_LONGLONG
1038                 };
1039                 for(unsigned i = 0; i < sizeof(possible_kinds)/sizeof(possible_kinds[0]); ++i) {
1040                         if(get_atomic_type_size(possible_kinds[i]) == size) {
1041                                 kind = possible_kinds[i];
1042                                 break;
1043                         }
1044                 }
1045                 kinds[size] = kind;
1046         }
1047         return kind;
1048 }
1049
1050 /**
1051  * Find the atomic type kind representing a given size (signed).
1052  */
1053 atomic_type_kind_t find_unsigned_int_atomic_type_kind_for_size(unsigned size) {
1054         static atomic_type_kind_t kinds[32];
1055
1056         assert(size < 32);
1057         atomic_type_kind_t kind = kinds[size];
1058         if(kind == ATOMIC_TYPE_INVALID) {
1059                 static const atomic_type_kind_t possible_kinds[] = {
1060                         ATOMIC_TYPE_UCHAR,
1061                         ATOMIC_TYPE_USHORT,
1062                         ATOMIC_TYPE_UINT,
1063                         ATOMIC_TYPE_ULONG,
1064                         ATOMIC_TYPE_ULONGLONG
1065                 };
1066                 for(unsigned i = 0; i < sizeof(possible_kinds)/sizeof(possible_kinds[0]); ++i) {
1067                         if(get_atomic_type_size(possible_kinds[i]) == size) {
1068                                 kind = possible_kinds[i];
1069                                 break;
1070                         }
1071                 }
1072                 kinds[size] = kind;
1073         }
1074         return kind;
1075 }
1076
1077 /**
1078  * Hash the given type and return the "singleton" version
1079  * of it.
1080  */
1081 static type_t *identify_new_type(type_t *type)
1082 {
1083         type_t *result = typehash_insert(type);
1084         if(result != type) {
1085                 obstack_free(type_obst, type);
1086         }
1087         return result;
1088 }
1089
1090 /**
1091  * Creates a new atomic type.
1092  *
1093  * @param akind       The kind of the atomic type.
1094  * @param qualifiers  Type qualifiers for the new type.
1095  */
1096 type_t *make_atomic_type(atomic_type_kind_t atype, type_qualifiers_t qualifiers)
1097 {
1098         type_t *type = obstack_alloc(type_obst, sizeof(atomic_type_t));
1099         memset(type, 0, sizeof(atomic_type_t));
1100
1101         type->kind            = TYPE_ATOMIC;
1102         type->base.qualifiers = qualifiers;
1103         type->base.alignment  = 0;
1104         type->atomic.akind    = atype;
1105
1106         /* TODO: set the alignment depending on the atype here */
1107
1108         return identify_new_type(type);
1109 }
1110
1111 /**
1112  * Creates a new pointer type.
1113  *
1114  * @param points_to   The points-to type for the new type.
1115  * @param qualifiers  Type qualifiers for the new type.
1116  */
1117 type_t *make_pointer_type(type_t *points_to, type_qualifiers_t qualifiers)
1118 {
1119         type_t *type = obstack_alloc(type_obst, sizeof(pointer_type_t));
1120         memset(type, 0, sizeof(pointer_type_t));
1121
1122         type->kind              = TYPE_POINTER;
1123         type->base.qualifiers   = qualifiers;
1124         type->base.alignment    = 0;
1125         type->pointer.points_to = points_to;
1126
1127         return identify_new_type(type);
1128 }
1129
1130 type_t *make_array_type(type_t *element_type, size_t size,
1131                         type_qualifiers_t qualifiers)
1132 {
1133         type_t *type = obstack_alloc(type_obst, sizeof(array_type_t));
1134         memset(type, 0, sizeof(array_type_t));
1135
1136         type->kind                = TYPE_ARRAY;
1137         type->base.qualifiers     = qualifiers;
1138         type->base.alignment      = 0;
1139         type->array.element_type  = element_type;
1140         type->array.size          = size;
1141         type->array.size_constant = true;
1142
1143         return identify_new_type(type);
1144 }
1145
1146 /**
1147  * Debug helper. Prints the given type to stdout.
1148  */
1149 static __attribute__((unused))
1150 void dbg_type(const type_t *type)
1151 {
1152         FILE *old_out = out;
1153         out = stderr;
1154         print_type(type);
1155         puts("\n");
1156         fflush(stderr);
1157         out = old_out;
1158 }