evaluate.c

   1 /*
   2  * sparse/evaluate.c
   3  *
   4  * Copyright (C) 2003 Transmeta Corp, all rights reserved.
   5  *
   6  * Evaluate constant expressions.
   7  */
   8 #include <stdlib.h>
   9 #include <stdarg.h>
  10 #include <stddef.h>
  11 #include <string.h>
  12 #include <ctype.h>
  13 #include <unistd.h>
  14 #include <fcntl.h>
  15 #include <limits.h>
  16
  17 #include "lib.h"
  18 #include "parse.h"
  19 #include "token.h"
  20 #include "symbol.h"
  21 #include "target.h"
  22 #include "expression.h"
  23
  24 static int current_context, current_contextmask;
  25
  26 static struct symbol *evaluate_symbol_expression(struct expression *expr)
  27 {
  28         struct symbol *sym = expr->symbol;
  29         struct symbol *base_type;
  30
  31         if (!sym) {
  32                 warn(expr->pos, "undefined identifier '%s'", show_ident(expr->symbol_name));
  33                 return NULL;
  34         }
  35
  36         examine_symbol_type(sym);
  37         if ((sym->ctype.context ^ current_context) & (sym->ctype.contextmask & current_contextmask))
  38                 warn(expr->pos, "Using symbol '%s' in wrong context", show_ident(expr->symbol_name));
  39
  40         base_type = sym->ctype.base_type;
  41         if (!base_type) {
  42                 warn(sym->pos, "identifier '%s' has no type", show_ident(expr->symbol_name));
  43                 return NULL;
  44         }
  45
  46         /* The type of a symbol is the symbol itself! */
  47         expr->ctype = sym;
  48
  49         /* enum's can be turned into plain values */
  50         if (base_type->type == SYM_ENUM) {
  51                 expr->type = EXPR_VALUE;
  52                 expr->value = sym->value;
  53         }
  54         return sym;
  55 }
  56
  57 static struct symbol *evaluate_string(struct expression *expr)
  58 {
  59         struct symbol *sym = alloc_symbol(expr->pos, SYM_ARRAY);
  60         int length = expr->string->length;
  61
  62         sym->array_size = length;
  63         sym->bit_size = BITS_IN_CHAR * length;
  64         sym->ctype.alignment = 1;
  65         sym->ctype.modifiers = MOD_CONST;
  66         sym->ctype.base_type = &char_ctype;
  67         expr->ctype = sym;
  68         return sym;
  69 }
  70
  71 static struct symbol *bigger_int_type(struct symbol *left, struct symbol *right)
  72 {
  73         unsigned long lmod, rmod, mod;
  74
  75         if (left == right)
  76                 return left;
  77
  78         if (left->bit_size > right->bit_size)
  79                 return left;
  80
  81         if (right->bit_size > left->bit_size)
  82                 return right;
  83
  84         /* Same size integers - promote to unsigned, promote to long */
  85         lmod = left->ctype.modifiers;
  86         rmod = right->ctype.modifiers;
  87         mod = lmod | rmod;
  88         if (mod == lmod)
  89                 return left;
  90         if (mod == rmod)
  91                 return right;
  92         return ctype_integer(mod);
  93 }
  94
  95 static struct symbol * cast_value(struct expression *expr, struct symbol *newtype,
  96                         struct expression *old, struct symbol *oldtype)
  97 {
  98         int old_size = oldtype->bit_size;
  99         int new_size = newtype->bit_size;
 100         long long value, mask, ormask, andmask;
 101         int is_signed;
 102
 103         // FIXME! We don't handle FP casts of constant values yet
 104         if (newtype->ctype.base_type == &fp_type)
 105                 return NULL;
 106         if (oldtype->ctype.base_type == &fp_type)
 107                 return NULL;
 108
 109         // For pointers and integers, we can just move the value around
 110         expr->type = EXPR_VALUE;
 111         if (old_size == new_size) {
 112                 expr->value = old->value;
 113                 return newtype;
 114         }
 115
 116         // expand it to the full "long long" value
 117         is_signed = !(oldtype->ctype.modifiers & MOD_UNSIGNED);
 118         mask = 1ULL << (old_size-1);
 119         value = old->value;
 120         if (!(value & mask))
 121                 is_signed = 0;
 122         andmask = mask | (mask-1);
 123         ormask = ~andmask;
 124         if (!is_signed)
 125                 ormask = 0;
 126         value = (value & andmask) | ormask;
 127
 128         // Truncate it to the new size
 129         mask = 1ULL << (new_size-1);
 130         mask = mask | (mask-1);
 131         expr->value = value & mask;
 132         return newtype;
 133 }
 134
 135 static struct expression * cast_to(struct expression *old, struct symbol *type)
 136 {
 137         struct expression *expr = alloc_expression(old->pos, EXPR_CAST);
 138         expr->ctype = type;
 139         expr->cast_type = type;
 140         expr->cast_expression = old;
 141         if (old->type == EXPR_VALUE)
 142                 cast_value(expr, type, old, old->ctype);
 143         return expr;
 144 }
 145
 146 static int is_ptr_type(struct symbol *type)
 147 {
 148         if (type->type == SYM_NODE)
 149                 type = type->ctype.base_type;
 150         return type->type == SYM_PTR || type->type == SYM_ARRAY || type->type == SYM_FN;
 151 }
 152
 153 static int is_int_type(struct symbol *type)
 154 {
 155         if (type->type == SYM_NODE)
 156                 type = type->ctype.base_type;
 157         return type->ctype.base_type == &int_type;
 158 }
 159
 160 static struct symbol *bad_expr_type(struct expression *expr)
 161 {
 162         warn(expr->pos, "incompatible types for operation");
 163         return NULL;
 164 }
 165
 166 static struct symbol * compatible_integer_binop(struct expression *expr, struct expression **lp, struct expression **rp)
 167 {
 168         struct expression *left = *lp, *right = *rp;
 169         struct symbol *ltype = left->ctype, *rtype = right->ctype;
 170
 171         if (ltype->type == SYM_NODE)
 172                 ltype = ltype->ctype.base_type;
 173         if (rtype->type == SYM_NODE)
 174                 rtype = rtype->ctype.base_type;
 175         /* Integer promotion? */
 176         if (ltype->type == SYM_ENUM)
 177                 ltype = &int_ctype;
 178         if (rtype->type == SYM_ENUM)
 179                 rtype = &int_ctype;
 180         if (is_int_type(ltype) && is_int_type(rtype)) {
 181                 struct symbol *ctype = bigger_int_type(ltype, rtype);
 182
 183                 /* Don't bother promoting same-size entities, it only adds clutter */
 184                 if (ltype->bit_size != ctype->bit_size)
 185                         *lp = cast_to(left, ctype);
 186                 if (rtype->bit_size != ctype->bit_size)
 187                         *rp = cast_to(right, ctype);
 188                 return ctype;
 189         }
 190         return NULL;
 191 }
 192
 193 static struct symbol *evaluate_int_binop(struct expression *expr)
 194 {
 195         struct symbol *ctype = compatible_integer_binop(expr, &expr->left, &expr->right);
 196         if (ctype) {
 197                 expr->ctype = ctype;
 198                 return ctype;
 199         }
 200         return bad_expr_type(expr);
 201 }
 202
 203 /* Arrays degenerate into pointers on pointer arithmetic */
 204 static struct symbol *degenerate(struct expression *expr, struct symbol *ctype)
 205 {
 206         if (ctype->type == SYM_ARRAY) {
 207                 struct symbol *sym = alloc_symbol(expr->pos, SYM_PTR);
 208                 sym->ctype = ctype->ctype;
 209                 sym->bit_size = BITS_IN_POINTER;
 210                 sym->ctype.alignment = POINTER_ALIGNMENT;
 211                 ctype = sym;
 212         }
 213         return ctype;
 214 }
 215
 216 static struct symbol *evaluate_ptr_add(struct expression *expr, struct expression *ptr, struct expression *i)
 217 {
 218         struct symbol *ctype;
 219         struct symbol *ptr_type = ptr->ctype;
 220         struct symbol *i_type = i->ctype;
 221
 222         if (i_type->type == SYM_NODE)
 223                 i_type = i_type->ctype.base_type;
 224         if (ptr_type->type == SYM_NODE)
 225                 ptr_type = ptr_type->ctype.base_type;
 226
 227         if (i_type->type == SYM_ENUM)
 228                 i_type = &int_ctype;
 229         if (!is_int_type(i_type))
 230                 return bad_expr_type(expr);
 231
 232         ctype = ptr_type->ctype.base_type;
 233         examine_symbol_type(ctype);
 234
 235         expr->ctype = degenerate(expr, ptr_type);
 236         if (ctype->bit_size > BITS_IN_CHAR) {
 237                 struct expression *add = expr;
 238                 struct expression *mul = alloc_expression(expr->pos, EXPR_BINOP);
 239                 struct expression *val = alloc_expression(expr->pos, EXPR_VALUE);
 240
 241                 val->ctype = size_t_ctype;
 242                 val->value = ctype->bit_size >> 3;
 243
 244                 mul->op = '*';
 245                 mul->ctype = size_t_ctype;
 246                 mul->left = i;
 247                 mul->right = val;
 248
 249                 /* Leave 'add->op' as 'expr->op' - either '+' or '-' */
 250                 add->left = ptr;
 251                 add->right = mul;
 252         }
 253
 254         return expr->ctype;
 255 }
 256
 257 static struct symbol *evaluate_add(struct expression *expr)
 258 {
 259         struct expression *left = expr->left, *right = expr->right;
 260         struct symbol *ltype = left->ctype, *rtype = right->ctype;
 261
 262         if (is_ptr_type(ltype))
 263                 return evaluate_ptr_add(expr, left, right);
 264
 265         if (is_ptr_type(rtype))
 266                 return evaluate_ptr_add(expr, right, left);
 267
 268         // FIXME! FP promotion
 269         return evaluate_int_binop(expr);
 270 }
 271
 272 static int same_type(struct symbol *target, struct symbol *source)
 273 {
 274         int dropped_modifiers = 0;
 275         for (;;) {
 276                 unsigned long mod1, mod2;
 277                 unsigned long as1, as2;
 278
 279                 if (target == source)
 280                         break;
 281                 if (!target || !source)
 282                         return 0;
 283                 /*
 284                  * Peel of per-node information.
 285                  * FIXME! Check alignment, address space, and context too here!
 286                  */
 287                 mod1 = target->ctype.modifiers;
 288                 as1 = target->ctype.as;
 289                 mod2 = source->ctype.modifiers;
 290                 as2 = source->ctype.as;
 291                 if (target->type == SYM_NODE) {
 292                         target = target->ctype.base_type;
 293                         mod1 |= target->ctype.modifiers;
 294                         as1 |= target->ctype.as;
 295                 }
 296                 if (source->type == SYM_NODE) {
 297                         source = source->ctype.base_type;
 298                         mod2 |= source->ctype.modifiers;
 299                         as2 |= source->ctype.as;
 300                 }
 301
 302                 /* Ignore differences in storage types */
 303                 if ((mod1 ^ mod2) & ~MOD_STORAGE)
 304                         return 0;
 305
 306                 /* Must be same address space to be comparable */
 307                 if (as1 != as2)
 308                         return 0;
 309
 310                 if (target->type != source->type) {
 311                         int type1 = target->type;
 312                         int type2 = source->type;
 313
 314                         /* Ignore ARRAY/PTR differences, as long as they point to the same type */
 315                         type1 = type1 == SYM_ARRAY ? SYM_PTR : type1;
 316                         type2 = type2 == SYM_ARRAY ? SYM_PTR : type2;
 317                         if (type1 != type2)
 318                                 return 0;
 319                 }
 320
 321                 target = target->ctype.base_type;
 322                 source = source->ctype.base_type;
 323         }
 324         if (dropped_modifiers)
 325                 warn(target->pos, "assignment drops modifiers");
 326         return 1;
 327 }
 328
 329 static struct symbol *common_ptr_type(struct expression *l, struct expression *r)
 330 {
 331         /* NULL expression? Just return the type of the "other side" */
 332         if (r->type == EXPR_VALUE && !r->value)
 333                 return l->ctype;
 334         if (l->type == EXPR_VALUE && !l->value)
 335                 return r->ctype;
 336         return NULL;
 337 }
 338
 339 static struct symbol *evaluate_ptr_sub(struct expression *expr, struct expression *l, struct expression *r)
 340 {
 341         struct symbol *ctype;
 342         struct symbol *ltype = l->ctype, *rtype = r->ctype;
 343
 344         /*
 345          * If it is an integer subtract: the ptr add case will do the
 346          * right thing.
 347          */
 348         if (!is_ptr_type(rtype))
 349                 return evaluate_ptr_add(expr, l, r);
 350
 351         ctype = ltype;
 352         if (!same_type(ltype, rtype)) {
 353                 ctype = common_ptr_type(l, r);
 354                 if (!ctype) {
 355                         warn(expr->pos, "subtraction of different types can't work");
 356                         return NULL;
 357                 }
 358         }
 359         examine_symbol_type(ctype);
 360
 361         /* Figure out the base type we point to */
 362         if (ctype->type == SYM_NODE)
 363                 ctype = ctype->ctype.base_type;
 364         if (ctype->type != SYM_PTR && ctype->type != SYM_ARRAY) {
 365                 warn(expr->pos, "subtraction of functions? Share your drugs");
 366                 return NULL;
 367         }
 368         ctype = ctype->ctype.base_type;
 369
 370         expr->ctype = ssize_t_ctype;
 371         if (ctype->bit_size > BITS_IN_CHAR) {
 372                 struct expression *sub = alloc_expression(expr->pos, EXPR_BINOP);
 373                 struct expression *div = expr;
 374                 struct expression *val = alloc_expression(expr->pos, EXPR_VALUE);
 375
 376                 val->ctype = size_t_ctype;
 377                 val->value = ctype->bit_size >> 3;
 378
 379                 sub->op = '-';
 380                 sub->ctype = ssize_t_ctype;
 381                 sub->left = l;
 382                 sub->right = r;
 383
 384                 div->op = '/';
 385                 div->left = sub;
 386                 div->right = val;
 387         }
 388
 389         return ssize_t_ctype;
 390 }
 391
 392 static struct symbol *evaluate_sub(struct expression *expr)
 393 {
 394         struct expression *left = expr->left, *right = expr->right;
 395         struct symbol *ltype = left->ctype;
 396
 397         if (is_ptr_type(ltype))
 398                 return evaluate_ptr_sub(expr, left, right);
 399
 400         // FIXME! FP promotion
 401         return evaluate_int_binop(expr);
 402 }
 403
 404 static struct symbol *evaluate_logical(struct expression *expr)
 405 {
 406         // FIXME! Short-circuit, FP and pointers!
 407         expr->ctype = &bool_ctype;
 408         return &bool_ctype;
 409 }
 410
 411 static struct symbol *evaluate_arithmetic(struct expression *expr)
 412 {
 413         // FIXME! Floating-point promotion!
 414         return evaluate_int_binop(expr);
 415 }
 416
 417 static struct symbol *evaluate_binop(struct expression *expr)
 418 {
 419         switch (expr->op) {
 420         // addition can take ptr+int, fp and int
 421         case '+':
 422                 return evaluate_add(expr);
 423
 424         // subtraction can take ptr-ptr, fp and int
 425         case '-':
 426                 return evaluate_sub(expr);
 427
 428         // Logical ops can take a lot of special stuff and have early-out
 429         case SPECIAL_LOGICAL_AND:
 430         case SPECIAL_LOGICAL_OR:
 431                 return evaluate_logical(expr);
 432
 433         // Arithmetic operations can take fp and int
 434         case '*': case '/': case '%':
 435                 return evaluate_arithmetic(expr);
 436
 437         // The rest are integer operations (bitops)
 438         // SPECIAL_LEFTSHIFT, SPECIAL_RIGHTSHIFT
 439         // '&', '^', '|'
 440         default:
 441                 return evaluate_int_binop(expr);
 442         }
 443 }
 444
 445 static struct symbol *evaluate_comma(struct expression *expr)
 446 {
 447         expr->ctype = expr->right->ctype;
 448         return expr->ctype;
 449 }
 450
 451 static struct symbol *evaluate_compare(struct expression *expr)
 452 {
 453         struct expression *left = expr->left, *right = expr->right;
 454         struct symbol *ltype = left->ctype, *rtype = right->ctype;
 455
 456         /* Pointer types? */
 457         if (is_ptr_type(ltype) || is_ptr_type(rtype)) {
 458                 expr->ctype = &bool_ctype;
 459                 // FIXME! Check the types for compatibility
 460                 return &bool_ctype;
 461         }
 462
 463         if (compatible_integer_binop(expr, &expr->left, &expr->right)) {
 464                 expr->ctype = &bool_ctype;
 465                 return &bool_ctype;
 466         }
 467
 468         return bad_expr_type(expr);
 469 }
 470
 471 static int compatible_integer_types(struct symbol *ltype, struct symbol *rtype)
 472 {
 473         /* Integer promotion? */
 474         if (ltype->type == SYM_ENUM)
 475                 ltype = &int_ctype;
 476         if (rtype->type == SYM_ENUM)
 477                 rtype = &int_ctype;
 478         return (is_int_type(ltype) && is_int_type(rtype));
 479 }
 480
 481 static int is_void_ptr(struct expression *expr)
 482 {
 483         return (expr->type == EXPR_VALUE &&
 484                 expr->value == 0);
 485 }
 486
 487 /*
 488  * FIXME!! This shoul ddo casts, array degeneration etc..
 489  */
 490 static struct symbol *compatible_ptr_type(struct expression *left, struct expression *right)
 491 {
 492         struct symbol *ltype = left->ctype, *rtype = right->ctype;
 493
 494         if (ltype->type == SYM_PTR) {
 495                 if (is_void_ptr(right))
 496                         return ltype;
 497         }
 498
 499         if (rtype->type == SYM_PTR) {
 500                 if (is_void_ptr(left))
 501                         return rtype;
 502         }
 503         return NULL;
 504 }
 505
 506 static struct symbol * evaluate_conditional(struct expression *expr)
 507 {
 508         struct symbol *ctype;
 509         struct symbol *ltype = expr->cond_true->ctype;
 510         struct symbol *rtype = expr->cond_false->ctype;
 511
 512         if (same_type(ltype, rtype)) {
 513                 expr->ctype = ltype;
 514                 return ltype;
 515         }
 516
 517         ctype = compatible_integer_binop(expr, &expr->cond_true, &expr->cond_false);
 518         if (ctype) {
 519                 expr->ctype = ctype;
 520                 return ctype;
 521         }
 522
 523         ctype = compatible_ptr_type(expr->cond_true, expr->cond_false);
 524         if (ctype) {
 525                 expr->ctype = ctype;
 526                 return ctype;
 527         }
 528
 529         warn(expr->pos, "incompatible types in conditional expression");
 530         return NULL;
 531 }
 532
 533 static int compatible_assignment_types(struct expression *expr, struct symbol *target,
 534         struct expression **rp, struct symbol *source)
 535 {
 536         if (same_type(target, source))
 537                 return 1;
 538
 539         if (compatible_integer_types(target, source)) {
 540                 if (target->bit_size != source->bit_size)
 541                         *rp = cast_to(*rp, target);
 542                 return 1;
 543         }
 544
 545         /* Pointer destination? */
 546         if (target->type == SYM_NODE)
 547                 target = target->ctype.base_type;
 548         if (source->type == SYM_NODE)
 549                 source = source->ctype.base_type;
 550         if (target->type == SYM_PTR) {
 551                 struct expression *right = *rp;
 552                 struct symbol *source_base = source->ctype.base_type;
 553                 struct symbol *target_base = target->ctype.base_type;
 554
 555                 if (source->type == SYM_NODE) {
 556                         source = source_base;
 557                         source_base = source->ctype.base_type;
 558                 }
 559                 if (target->type == SYM_NODE) {
 560                         target = target_base;
 561                         target_base = target->ctype.base_type;
 562                 }
 563                 if (source->type == SYM_ARRAY && same_type(target_base, source_base))
 564                         return 1;
 565                 if (source->type == SYM_FN && same_type(target_base, source))
 566                         return 1;
 567
 568                 // NULL pointer?
 569                 if (right->type == EXPR_VALUE && !right->value)
 570                         return 1;
 571
 572                 // void pointer ?
 573                 if (target->type == SYM_PTR) {
 574                         struct symbol *source_base = source->ctype.base_type;
 575                         struct symbol *target_base = target->ctype.base_type;
 576                         if (source_base == &void_ctype || target_base == &void_ctype)
 577                                 return 1;
 578                         warn(expr->pos, "assignment from incompatible pointer types");
 579                         return 1;
 580                 }
 581
 582                 // FIXME!! Cast it!
 583                 warn(expr->pos, "assignment from different types");
 584                 return 0;
 585         }
 586
 587         // FIXME!! Cast it!
 588         warn(expr->pos, "assignment from bad type");
 589         return 0;
 590 }
 591
 592 static struct symbol *evaluate_binop_assignment(struct expression *expr, struct expression *left, struct expression *right)
 593 {
 594         int op = expr->op;
 595         struct expression *subexpr = alloc_expression(expr->pos, EXPR_BINOP);
 596         static const int op_trans[] = {
 597                 [SPECIAL_ADD_ASSIGN - SPECIAL_BASE] = '+',
 598                 [SPECIAL_SUB_ASSIGN - SPECIAL_BASE] = '-',
 599                 [SPECIAL_MUL_ASSIGN - SPECIAL_BASE] = '*',
 600                 [SPECIAL_DIV_ASSIGN - SPECIAL_BASE] = '/',
 601                 [SPECIAL_MOD_ASSIGN - SPECIAL_BASE] = '%',
 602                 [SPECIAL_SHL_ASSIGN - SPECIAL_BASE] = SPECIAL_LEFTSHIFT,
 603                 [SPECIAL_SHR_ASSIGN - SPECIAL_BASE] = SPECIAL_RIGHTSHIFT,
 604                 [SPECIAL_AND_ASSIGN - SPECIAL_BASE] = '&',
 605                 [SPECIAL_OR_ASSIGN - SPECIAL_BASE] = '&',
 606                 [SPECIAL_XOR_ASSIGN - SPECIAL_BASE] = '^'
 607         };
 608
 609         subexpr->left = left;
 610         subexpr->right = right;
 611         subexpr->op = op_trans[op - SPECIAL_BASE];
 612         expr->op = '=';
 613         expr->right = subexpr;
 614         return evaluate_binop(subexpr);
 615 }
 616
 617 static struct symbol *evaluate_assignment(struct expression *expr)
 618 {
 619         struct expression *left = expr->left, *right = expr->right;
 620         struct symbol *ltype, *rtype;
 621
 622         ltype = left->ctype;
 623         rtype = right->ctype;
 624         if (expr->op != '=') {
 625                 rtype = evaluate_binop_assignment(expr, left, right);
 626                 if (!rtype)
 627                         return 0;
 628                 right = expr->right;
 629         }
 630
 631         if (!ltype) {
 632                 warn(expr->pos, "what? no ltype");
 633                 return 0;
 634         }
 635         if (!rtype) {
 636                 warn(expr->pos, "what? no rtype");
 637                 return 0;
 638         }
 639
 640         if (!compatible_assignment_types(expr, ltype, &expr->right, rtype))
 641                 return 0;
 642
 643         expr->ctype = expr->left->ctype;
 644         return expr->ctype;
 645 }
 646
 647 static struct symbol *evaluate_preop(struct expression *expr)
 648 {
 649         struct symbol *ctype = expr->unop->ctype;
 650         unsigned long mod;
 651
 652         switch (expr->op) {
 653         case '(':
 654                 *expr = *expr->unop;
 655                 return ctype;
 656
 657         case '*':
 658                 mod = ctype->ctype.modifiers;
 659                 if (ctype->type == SYM_NODE) {
 660                         ctype = ctype->ctype.base_type;
 661                         mod |= ctype->ctype.modifiers;
 662                 }
 663                 if (ctype->type != SYM_PTR && ctype->type != SYM_ARRAY) {
 664                         warn(expr->pos, "cannot derefence this type");
 665                         return 0;
 666                 }
 667                 if (mod & MOD_NODEREF)
 668                         warn(expr->pos, "bad dereference");
 669                 ctype = ctype->ctype.base_type;
 670                 if (!ctype) {
 671                         warn(expr->pos, "undefined type");
 672                         return 0;
 673                 }
 674                 examine_symbol_type(ctype);
 675                 expr->ctype = ctype;
 676                 return ctype;
 677
 678         case '&': {
 679                 struct symbol *symbol = alloc_symbol(expr->pos, SYM_PTR);
 680                 symbol->ctype.base_type = ctype;
 681                 symbol->ctype.alignment = POINTER_ALIGNMENT;
 682                 symbol->bit_size = BITS_IN_POINTER;
 683                 expr->ctype = symbol;
 684                 return symbol;
 685         }
 686
 687         case '!':
 688                 expr->ctype = &bool_ctype;
 689                 return &bool_ctype;
 690
 691         default:
 692                 expr->ctype = ctype;
 693                 return ctype;
 694         }
 695 }
 696
 697 /*
 698  * Unary post-ops: x++ and x--
 699  */
 700 static struct symbol *evaluate_postop(struct expression *expr)
 701 {
 702         struct symbol *ctype = expr->unop->ctype;
 703         expr->ctype = ctype;
 704         return ctype;
 705 }
 706
 707 struct symbol *find_identifier(struct ident *ident, struct symbol_list *_list, int *offset)
 708 {
 709         struct ptr_list *head = (struct ptr_list *)_list;
 710         struct ptr_list *list = head;
 711
 712         if (!head)
 713                 return NULL;
 714         do {
 715                 int i;
 716                 for (i = 0; i < list->nr; i++) {
 717                         struct symbol *sym = (struct symbol *) list->list[i];
 718                         if (sym->ident) {
 719                                 if (sym->ident != ident)
 720                                         continue;
 721                                 *offset = sym->offset;
 722                                 return sym;
 723                         } else {
 724                                 struct symbol *ctype = sym->ctype.base_type;
 725                                 struct symbol *sub;
 726                                 if (!ctype)
 727                                         continue;
 728                                 if (ctype->type != SYM_UNION && ctype->type != SYM_STRUCT)
 729                                         continue;
 730                                 sub = find_identifier(ident, ctype->symbol_list, offset);
 731                                 if (!sub)
 732                                         continue;
 733                                 *offset += sym->offset;
 734                                 return sub;
 735                         }
 736                 }
 737         } while ((list = list->next) != head);
 738         return NULL;
 739 }
 740
 741 /* structure/union dereference */
 742 static struct symbol *evaluate_dereference(struct expression *expr)
 743 {
 744         int offset;
 745         struct symbol *ctype, *member;
 746         struct expression *deref = expr->deref, *add;
 747         struct ident *ident = expr->member;
 748         unsigned int mod;
 749
 750         if (!evaluate_expression(deref))
 751                 return NULL;
 752         if (!ident) {
 753                 warn(expr->pos, "bad member name");
 754                 return NULL;
 755         }
 756
 757         ctype = deref->ctype;
 758         mod = ctype->ctype.modifiers;
 759         if (ctype->type == SYM_NODE) {
 760                 ctype = ctype->ctype.base_type;
 761                 mod |= ctype->ctype.modifiers;
 762         }
 763         if (expr->op == SPECIAL_DEREFERENCE) {
 764                 /* Arrays will degenerate into pointers for '->' */
 765                 if (ctype->type != SYM_PTR && ctype->type != SYM_ARRAY) {
 766                         warn(expr->pos, "expected a pointer to a struct/union");
 767                         return NULL;
 768                 }
 769                 ctype = ctype->ctype.base_type;
 770                 mod |= ctype->ctype.modifiers;
 771                 if (ctype->type == SYM_NODE) {
 772                         ctype = ctype->ctype.base_type;
 773                         mod |= ctype->ctype.modifiers;
 774                 }
 775         }
 776         if (mod & MOD_NODEREF)
 777                 warn(expr->pos, "bad dereference");
 778         if (!ctype || (ctype->type != SYM_STRUCT && ctype->type != SYM_UNION)) {
 779                 warn(expr->pos, "expected structure or union");
 780                 return NULL;
 781         }
 782         offset = 0;
 783         member = find_identifier(ident, ctype->symbol_list, &offset);
 784         if (!member) {
 785                 warn(expr->pos, "no such struct/union member");
 786                 return NULL;
 787         }
 788
 789         add = deref;
 790         if (offset != 0) {
 791                 add = alloc_expression(expr->pos, EXPR_BINOP);
 792                 add->op = '+';
 793                 add->ctype = &ptr_ctype;
 794                 add->left = deref;
 795                 add->right = alloc_expression(expr->pos, EXPR_VALUE);
 796                 add->right->ctype = &int_ctype;
 797                 add->right->value = offset;
 798         }
 799
 800         ctype = member->ctype.base_type;
 801         if (ctype->type == SYM_BITFIELD) {
 802                 ctype = ctype->ctype.base_type;
 803                 expr->type = EXPR_BITFIELD;
 804                 expr->bitpos = member->bit_offset;
 805                 expr->nrbits = member->fieldwidth;
 806                 expr->address = add;
 807         } else {
 808                 expr->type = EXPR_PREOP;
 809                 expr->op = '*';
 810                 expr->unop = add;
 811         }
 812
 813         expr->ctype = ctype;
 814         return ctype;
 815 }
 816
 817 static struct symbol *evaluate_sizeof(struct expression *expr)
 818 {
 819         int size;
 820
 821         if (expr->cast_type) {
 822                 examine_symbol_type(expr->cast_type);
 823                 size = expr->cast_type->bit_size;
 824         } else {
 825                 if (!evaluate_expression(expr->cast_expression))
 826                         return 0;
 827                 size = expr->cast_expression->ctype->bit_size;
 828         }
 829         if (size & 7) {
 830                 warn(expr->pos, "cannot size expression");
 831                 return 0;
 832         }
 833         expr->type = EXPR_VALUE;
 834         expr->value = size >> 3;
 835         expr->ctype = size_t_ctype;
 836         return size_t_ctype;
 837 }
 838
 839 static struct symbol *evaluate_lvalue_expression(struct expression *expr)
 840 {
 841         // FIXME!
 842         return evaluate_expression(expr);
 843 }
 844
 845 static int evaluate_expression_list(struct expression_list *head)
 846 {
 847         if (head) {
 848                 struct ptr_list *list = (struct ptr_list *)head;
 849                 do {
 850                         int i;
 851                         for (i = 0; i < list->nr; i++) {
 852                                 struct expression *expr = (struct expression *)list->list[i];
 853                                 evaluate_expression(expr);
 854                         }
 855                 } while ((list = list->next) != (struct ptr_list *)head);
 856         }
 857         // FIXME!
 858         return 1;
 859 }
 860
 861 /*
 862  * FIXME! This is bogus: we need to take array index
 863  * entries into account when calculating the size of
 864  * the array.
 865  */
 866 static int count_array_initializer(struct expression *expr)
 867 {
 868         struct expression_list *list;
 869
 870         if (expr->type != EXPR_INITIALIZER)
 871                 return 1;
 872         list = expr->expr_list;
 873         return expression_list_size(list);
 874 }
 875
 876 /*
 877  * Initializers are kind of like assignments. Except
 878  * they can be a hell of a lot more complex.
 879  */
 880 static int evaluate_initializer(struct symbol *ctype, struct expression **ep)
 881 {
 882         struct expression *expr = *ep;
 883         /*
 884          * Simple non-structure/array initializers are the simple
 885          * case, and look (and parse) largely like assignments.
 886          */
 887         if (expr->type != EXPR_INITIALIZER) {
 888                 struct symbol *rtype = evaluate_expression(expr);
 889                 if (rtype)
 890                         compatible_assignment_types(expr, ctype, ep, rtype);
 891                 return 0;
 892         }
 893
 894         /*
 895          * FIXME!! Check type compatibility, and look up any named
 896          * initializers and index expressions!
 897          */
 898         expr->ctype = ctype;
 899         return count_array_initializer(expr);
 900 }
 901
 902 static struct symbol *evaluate_cast(struct expression *expr)
 903 {
 904         struct expression *target = expr->cast_expression;
 905         struct symbol *ctype = examine_symbol_type(expr->cast_type);
 906
 907         expr->ctype = ctype;
 908         expr->cast_type = ctype;
 909
 910         /*
 911          * Special case: a cast can be followed by an
 912          * initializer, in which case we need to pass
 913          * the type value down to that initializer rather
 914          * than trying to evaluate it as an expression
 915          */
 916         if (target->type == EXPR_INITIALIZER) {
 917                 evaluate_initializer(ctype, &expr->cast_expression);
 918                 return ctype;
 919         }
 920
 921         evaluate_expression(target);
 922
 923         /* Simplify normal integer casts.. */
 924         if (target->type == EXPR_VALUE)
 925                 cast_value(expr, ctype, target, target->ctype);
 926         return ctype;
 927 }
 928
 929 static struct symbol *evaluate_call(struct expression *expr)
 930 {
 931         int args, fnargs;
 932         struct symbol *ctype;
 933         struct expression *fn = expr->fn;
 934         struct expression_list *arglist = expr->args;
 935
 936         if (!evaluate_expression(fn))
 937                 return NULL;
 938         if (!evaluate_expression_list(arglist))
 939                 return NULL;
 940         ctype = fn->ctype;
 941         if (ctype->type == SYM_NODE)
 942                 ctype = ctype->ctype.base_type;
 943         if (ctype->type == SYM_PTR || ctype->type == SYM_ARRAY)
 944                 ctype = ctype->ctype.base_type;
 945         if (ctype->type != SYM_FN) {
 946                 warn(expr->pos, "not a function");
 947                 return NULL;
 948         }
 949         args = expression_list_size(expr->args);
 950         fnargs = symbol_list_size(ctype->arguments);
 951         if (args < fnargs)
 952                 warn(expr->pos, "not enough arguments for function");
 953         if (args > fnargs && !ctype->variadic)
 954                 warn(expr->pos, "too many arguments for function");
 955         expr->ctype = ctype->ctype.base_type;
 956         return expr->ctype;
 957 }
 958
 959 struct symbol *evaluate_expression(struct expression *expr)
 960 {
 961         if (!expr)
 962                 return NULL;
 963         if (expr->ctype)
 964                 return expr->ctype;
 965
 966         switch (expr->type) {
 967         case EXPR_VALUE:
 968                 warn(expr->pos, "value expression without a type");
 969                 return NULL;
 970         case EXPR_STRING:
 971                 return evaluate_string(expr);
 972         case EXPR_SYMBOL:
 973                 return evaluate_symbol_expression(expr);
 974         case EXPR_BINOP:
 975                 if (!evaluate_expression(expr->left))
 976                         return NULL;
 977                 if (!evaluate_expression(expr->right))
 978                         return NULL;
 979                 return evaluate_binop(expr);
 980         case EXPR_COMMA:
 981                 if (!evaluate_expression(expr->left))
 982                         return NULL;
 983                 if (!evaluate_expression(expr->right))
 984                         return NULL;
 985                 return evaluate_comma(expr);
 986         case EXPR_COMPARE:
 987                 if (!evaluate_expression(expr->left))
 988                         return NULL;
 989                 if (!evaluate_expression(expr->right))
 990                         return NULL;
 991                 return evaluate_compare(expr);
 992         case EXPR_ASSIGNMENT:
 993                 if (!evaluate_lvalue_expression(expr->left))
 994                         return NULL;
 995                 if (!evaluate_expression(expr->right))
 996                         return NULL;
 997                 return evaluate_assignment(expr);
 998         case EXPR_PREOP:
 999                 if (!evaluate_expression(expr->unop))
1000                         return NULL;
1001                 return evaluate_preop(expr);
1002         case EXPR_POSTOP:
1003                 if (!evaluate_expression(expr->unop))
1004                         return NULL;
1005                 return evaluate_postop(expr);
1006         case EXPR_CAST:
1007                 return evaluate_cast(expr);
1008         case EXPR_SIZEOF:
1009                 return evaluate_sizeof(expr);
1010         case EXPR_DEREF:
1011                 return evaluate_dereference(expr);
1012         case EXPR_CALL:
1013                 return evaluate_call(expr);
1014         case EXPR_BITFIELD:
1015                 warn(expr->pos, "bitfield generated by parser");
1016                 return NULL;
1017         case EXPR_CONDITIONAL:
1018                 if (!evaluate_expression(expr->conditional) ||
1019                     !evaluate_expression(expr->cond_true) ||
1020                     !evaluate_expression(expr->cond_false))
1021                         return NULL;
1022                 return evaluate_conditional(expr);
1023         case EXPR_STATEMENT:
1024                 expr->ctype = evaluate_statement(expr->statement);
1025                 return expr->ctype;
1026
1027         /* These can not exist as stand-alone expressions */
1028         case EXPR_INITIALIZER:
1029         case EXPR_IDENTIFIER:
1030         case EXPR_INDEX:
1031                 warn(expr->pos, "internal front-end error: initializer in expression");
1032                 return NULL;
1033         }
1034         return NULL;
1035 }
1036
1037 static void evaluate_one_statement(struct statement *stmt, void *_last, int flags)
1038 {
1039         struct symbol **last = _last;
1040         struct symbol *type = evaluate_statement(stmt);
1041
1042         if (flags & ITERATE_LAST)
1043                 *last = type;
1044 }
1045
1046 static void evaluate_one_symbol(struct symbol *sym, void *unused, int flags)
1047 {
1048         evaluate_symbol(sym);
1049 }
1050
1051 struct symbol *evaluate_symbol(struct symbol *sym)
1052 {
1053         struct symbol *base_type;
1054
1055         examine_symbol_type(sym);
1056         base_type = sym->ctype.base_type;
1057         if (!base_type)
1058                 return NULL;
1059         sym->ctype.base_type = base_type;
1060
1061         /* Evaluate the initializers */
1062         if (sym->initializer) {
1063                 int count = evaluate_initializer(base_type, &sym->initializer);
1064                 if (base_type->type == SYM_ARRAY && base_type->array_size < 0) {
1065                         int bit_size = count * base_type->ctype.base_type->bit_size;
1066                         base_type->array_size = count;
1067                         base_type->bit_size = bit_size;
1068                         sym->array_size = count;
1069                         sym->bit_size = bit_size;
1070                 }
1071         }
1072
1073         /* And finally, evaluate the body of the symbol too */
1074         if (base_type->type == SYM_FN) {
1075                 symbol_iterate(base_type->arguments, evaluate_one_symbol, NULL);
1076                 if (base_type->stmt) {
1077                         current_contextmask = sym->ctype.contextmask;
1078                         current_context = sym->ctype.context;
1079                         evaluate_statement(base_type->stmt);
1080                 }
1081         }
1082
1083         return base_type;
1084 }
1085
1086 struct symbol *evaluate_statement(struct statement *stmt)
1087 {
1088         if (!stmt)
1089                 return NULL;
1090
1091         switch (stmt->type) {
1092         case STMT_RETURN:
1093         case STMT_EXPRESSION:
1094                 return evaluate_expression(stmt->expression);
1095
1096         case STMT_COMPOUND: {
1097                 struct symbol *type = NULL;
1098                 symbol_iterate(stmt->syms, evaluate_one_symbol, NULL);
1099                 statement_iterate(stmt->stmts, evaluate_one_statement, &type);
1100                 return type;
1101         }
1102         case STMT_IF:
1103                 evaluate_expression(stmt->if_conditional);
1104                 evaluate_statement(stmt->if_true);
1105                 evaluate_statement(stmt->if_false);
1106                 return NULL;
1107         case STMT_ITERATOR:
1108                 evaluate_expression(stmt->iterator_pre_condition);
1109                 evaluate_expression(stmt->iterator_post_condition);
1110                 evaluate_statement(stmt->iterator_pre_statement);
1111                 evaluate_statement(stmt->iterator_statement);
1112                 evaluate_statement(stmt->iterator_post_statement);
1113                 return NULL;
1114         case STMT_SWITCH:
1115                 evaluate_expression(stmt->switch_expression);
1116                 evaluate_statement(stmt->switch_statement);
1117                 return NULL;
1118         case STMT_CASE:
1119                 evaluate_expression(stmt->case_expression);
1120                 evaluate_expression(stmt->case_to);
1121                 evaluate_statement(stmt->case_statement);
1122                 return NULL;
1123         case STMT_LABEL:
1124                 evaluate_statement(stmt->label_statement);
1125                 return NULL;
1126         case STMT_GOTO:
1127                 evaluate_expression(stmt->goto_expression);
1128                 return NULL;
1129         case STMT_NONE:
1130         case STMT_BREAK:
1131         case STMT_CONTINUE:
1132                 break;
1133         case STMT_ASM:
1134                 /* FIXME! Do the asm parameter evaluation! */
1135                 break;
1136         }
1137         return NULL;
1138 }
1139
1140 long long get_expression_value(struct expression *expr)
1141 {
1142         long long left, middle, right;
1143
1144         switch (expr->type) {
1145         case EXPR_SIZEOF:
1146                 if (expr->cast_type) {
1147                         examine_symbol_type(expr->cast_type);
1148                         if (expr->cast_type->bit_size & 7) {
1149                                 warn(expr->pos, "type has no size");
1150                                 return 0;
1151                         }
1152                         return expr->cast_type->bit_size >> 3;
1153                 }
1154                 warn(expr->pos, "expression sizes not yet supported");
1155                 return 0;
1156         case EXPR_VALUE:
1157                 return expr->value;
1158         case EXPR_SYMBOL: {
1159                 struct symbol *sym = expr->symbol;
1160                 if (!sym || !sym->ctype.base_type || sym->ctype.base_type->type != SYM_ENUM) {
1161                         warn(expr->pos, "undefined identifier '%s' in constant expression", show_ident(expr->symbol_name));
1162                         return 0;
1163                 }
1164                 return sym->value;
1165         }
1166
1167 #define OP(x,y) case x: return left y right;
1168         case EXPR_BINOP:
1169         case EXPR_COMPARE:
1170                 left = get_expression_value(expr->left);
1171                 if (!left && expr->op == SPECIAL_LOGICAL_AND)
1172                         return 0;
1173                 if (left && expr->op == SPECIAL_LOGICAL_OR)
1174                         return 1;
1175                 right = get_expression_value(expr->right);
1176                 switch (expr->op) {
1177                         OP('+',+); OP('-',-); OP('*',*); OP('/',/);
1178                         OP('%',%); OP('<',<); OP('>',>);
1179                         OP('&',&);OP('|',|);OP('^',^);
1180                         OP(SPECIAL_EQUAL,==); OP(SPECIAL_NOTEQUAL,!=);
1181                         OP(SPECIAL_LTE,<=); OP(SPECIAL_LEFTSHIFT,<<);
1182                         OP(SPECIAL_RIGHTSHIFT,>>); OP(SPECIAL_GTE,>=);
1183                         OP(SPECIAL_LOGICAL_AND,&&);OP(SPECIAL_LOGICAL_OR,||);
1184                 }
1185                 break;
1186
1187 #undef OP
1188 #define OP(x,y) case x: return y left;
1189         case EXPR_PREOP:
1190                 left = get_expression_value(expr->unop);
1191                 switch (expr->op) {
1192                         OP('+', +); OP('-', -); OP('!', !); OP('~', ~); OP('(', );
1193                 }
1194                 break;
1195
1196         case EXPR_CONDITIONAL:
1197                 left = get_expression_value(expr->conditional);
1198                 if (!expr->cond_true)
1199                         middle = left;
1200                 else
1201                         middle = get_expression_value(expr->cond_true);
1202                 right = get_expression_value(expr->cond_false);
1203                 return left ? middle : right;
1204
1205         default:
1206                 break;
1207         }
1208         error(expr->pos, "bad constant expression");
1209         return 0;
1210 }