?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[PATCH] casts are not lvalues
[smatch.git] / evaluate.c
blob9f02471dc5c092f9f79df381563e08e0fc13fa46
1 /*
2 * sparse/evaluate.c
3 *
4 * Copyright (C) 2003 Transmeta Corp.
5 * 2003 Linus Torvalds
6 *
7 * Licensed under the Open Software License version 1.1
8 *
9 * Evaluate constant expressions.
10 */
11 #include <stdlib.h>
12 #include <stdarg.h>
13 #include <stddef.h>
14 #include <stdio.h>
15 #include <string.h>
16 #include <ctype.h>
17 #include <unistd.h>
18 #include <fcntl.h>
19 #include <limits.h>
20
21 #include "lib.h"
22 #include "parse.h"
23 #include "token.h"
24 #include "symbol.h"
25 #include "target.h"
26 #include "expression.h"
27
28 static struct symbol *current_fn;
29 static int current_context, current_contextmask;
30
31 static struct symbol *degenerate(struct expression *expr);
32
33 static struct symbol *evaluate_symbol_expression(struct expression *expr)
34 {
35 struct symbol *sym = expr->symbol;
36 struct symbol *base_type;
37
38 if (!sym) {
39 if (preprocessing) {
40 expr->ctype = &int_ctype;
41 return &int_ctype;
42 }
43 warn(expr->pos, "undefined identifier '%s'", show_ident(expr->symbol_name));
44 return NULL;
45 }
46
47 examine_symbol_type(sym);
48 if ((sym->ctype.context ^ current_context) & (sym->ctype.contextmask & current_contextmask))
49 warn(expr->pos, "Using symbol '%s' in wrong context", show_ident(expr->symbol_name));
50
51 base_type = sym->ctype.base_type;
52 if (!base_type) {
53 warn(expr->pos, "identifier '%s' has no type", show_ident(expr->symbol_name));
54 return NULL;
55 }
56
57 /* The type of a symbol is the symbol itself! */
58 expr->ctype = sym;
59
60 /* enum's can be turned into plain values */
61 if (sym->type != SYM_ENUM) {
62 struct expression *addr = alloc_expression(expr->pos, EXPR_SYMBOL);
63 addr->symbol = sym;
64 addr->symbol_name = expr->symbol_name;
65 addr->ctype = &lazy_ptr_ctype; /* Lazy evaluation: we need to do a proper job if somebody does &sym */
66 expr->type = EXPR_PREOP;
67 expr->op = '*';
68 expr->unop = addr;
69 return sym;
70 }
71 expr->type = EXPR_VALUE;
72 expr->value = sym->value;
73 expr->ctype = base_type;
74 return sym;
75 }
76
77 static struct symbol *evaluate_string(struct expression *expr)
78 {
79 struct symbol *sym = alloc_symbol(expr->pos, SYM_NODE);
80 struct symbol *array = alloc_symbol(expr->pos, SYM_ARRAY);
81 struct expression *addr = alloc_expression(expr->pos, EXPR_SYMBOL);
82 struct expression *initstr = alloc_expression(expr->pos, EXPR_STRING);
83 unsigned int length = expr->string->length;
84
85 sym->array_size = alloc_const_expression(expr->pos, length);
86 sym->bit_size = bits_in_char * length;
87 sym->ctype.alignment = 1;
88 sym->ctype.modifiers = MOD_STATIC;
89 sym->ctype.base_type = array;
90 sym->initializer = initstr;
91
92 initstr->ctype = sym;
93 initstr->string = expr->string;
94
95 array->array_size = sym->array_size;
96 array->bit_size = bits_in_char * length;
97 array->ctype.alignment = 1;
98 array->ctype.modifiers = MOD_STATIC;
99 array->ctype.base_type = &char_ctype;
100
101 addr->symbol = sym;
102 addr->ctype = &lazy_ptr_ctype;
103
104 expr->type = EXPR_PREOP;
105 expr->op = '*';
106 expr->unop = addr;
107 expr->ctype = sym;
108 return sym;
109 }
110
111 static inline struct symbol *integer_promotion(struct symbol *type)
112 {
113 unsigned long mod = type->ctype.modifiers;
114 int width;
115
116 if (type->type == SYM_ENUM)
117 return &int_ctype;
118 else if (type->type == SYM_BITFIELD) {
119 mod = type->ctype.base_type->ctype.modifiers;
120 width = type->fieldwidth;
121 } else if (mod & (MOD_CHAR | MOD_SHORT))
122 width = type->bit_size;
123 else
124 return type;
125 if (mod & MOD_UNSIGNED && width == bits_in_int)
126 return &uint_ctype;
127 return &int_ctype;
128 }
129
130 /*
131 * integer part of usual arithmetic conversions:
132 * integer promotions are applied
133 * if left and right are identical, we are done
134 * if signedness is the same, convert one with lower rank
135 * unless unsigned argument has rank lower than signed one, convert the
136 * signed one.
137 * if signed argument is bigger than unsigned one, convert the unsigned.
138 * otherwise, convert signed.
139 *
140 * Leaving aside the integer promotions, that is equivalent to
141 * if identical, don't convert
142 * if left is bigger than right, convert right
143 * if right is bigger than left, convert right
144 * otherwise, if signedness is the same, convert one with lower rank
145 * otherwise convert the signed one.
146 */
147 static struct symbol *bigger_int_type(struct symbol *left, struct symbol *right)
148 {
149 unsigned long lmod, rmod;
150
151 left = integer_promotion(left);
152 right = integer_promotion(right);
153
154 if (left == right)
155 goto left;
156
157 if (left->bit_size > right->bit_size)
158 goto left;
159
160 if (right->bit_size > left->bit_size)
161 goto right;
162
163 lmod = left->ctype.modifiers;
164 rmod = right->ctype.modifiers;
165 if ((lmod ^ rmod) & MOD_UNSIGNED) {
166 if (lmod & MOD_UNSIGNED)
167 goto left;
168 } else if ((lmod & ~rmod) & (MOD_LONG | MOD_LONGLONG))
169 goto left;
170 right:
171 left = right;
172 left:
173 return left;
174 }
175
176 static struct expression * cast_to(struct expression *old, struct symbol *type)
177 {
178 struct expression *expr = alloc_expression(old->pos, EXPR_CAST);
179 expr->ctype = type;
180 expr->cast_type = type;
181 expr->cast_expression = old;
182 return expr;
183 }
184
185 static int is_type_type(struct symbol *type)
186 {
187 return (type->ctype.modifiers & MOD_TYPE) != 0;
188 }
189
190 static int is_ptr_type(struct symbol *type)
191 {
192 if (type->type == SYM_NODE)
193 type = type->ctype.base_type;
194 return type->type == SYM_PTR || type->type == SYM_ARRAY || type->type == SYM_FN;
195 }
196
197 static inline int is_float_type(struct symbol *type)
198 {
199 if (type->type == SYM_NODE)
200 type = type->ctype.base_type;
201 return type->ctype.base_type == &fp_type;
202 }
203
204 static inline int is_byte_type(struct symbol *type)
205 {
206 return type->bit_size == bits_in_char && type->type != SYM_BITFIELD;
207 }
208
209 static inline int is_string_type(struct symbol *type)
210 {
211 if (type->type == SYM_NODE)
212 type = type->ctype.base_type;
213 return type->type == SYM_ARRAY && is_byte_type(type->ctype.base_type);
214 }
215
216 static struct symbol *bad_expr_type(struct expression *expr)
217 {
218 warn(expr->pos, "incompatible types for operation (%s)", show_special(expr->op));
219 switch (expr->type) {
220 case EXPR_BINOP:
221 case EXPR_COMPARE:
222 info(expr->pos, " left side has type %s", show_typename(expr->left->ctype));
223 info(expr->pos, " right side has type %s", show_typename(expr->right->ctype));
224 break;
225 case EXPR_PREOP:
226 case EXPR_POSTOP:
227 info(expr->pos, " argument has type %s", show_typename(expr->unop->ctype));
228 break;
229 default:
230 break;
231 }
232
233 return NULL;
234 }
235
236 static struct symbol *compatible_float_binop(struct expression **lp, struct expression **rp)
237 {
238 struct expression *left = *lp, *right = *rp;
239 struct symbol *ltype = left->ctype, *rtype = right->ctype;
240
241 if (ltype->type == SYM_NODE)
242 ltype = ltype->ctype.base_type;
243 if (rtype->type == SYM_NODE)
244 rtype = rtype->ctype.base_type;
245 if (is_float_type(ltype)) {
246 if (is_int_type(rtype))
247 goto Left;
248 if (is_float_type(rtype)) {
249 unsigned long lmod = ltype->ctype.modifiers;
250 unsigned long rmod = rtype->ctype.modifiers;
251 lmod &= MOD_LONG | MOD_LONGLONG;
252 rmod &= MOD_LONG | MOD_LONGLONG;
253 if (lmod == rmod)
254 return ltype;
255 if (lmod & ~rmod)
256 goto Left;
257 else
258 goto Right;
259 }
260 return NULL;
261 }
262 if (!is_float_type(rtype) || !is_int_type(ltype))
263 return NULL;
264 Right:
265 *lp = cast_to(left, rtype);
266 return rtype;
267 Left:
268 *rp = cast_to(right, ltype);
269 return ltype;
270 }
271
272 static struct symbol *compatible_integer_binop(struct expression **lp, struct expression **rp)
273 {
274 struct expression *left = *lp, *right = *rp;
275 struct symbol *ltype = left->ctype, *rtype = right->ctype;
276
277 if (ltype->type == SYM_NODE)
278 ltype = ltype->ctype.base_type;
279 if (rtype->type == SYM_NODE)
280 rtype = rtype->ctype.base_type;
281 if (is_int_type(ltype) && is_int_type(rtype)) {
282 struct symbol *ctype = bigger_int_type(ltype, rtype);
283
284 /* Don't bother promoting same-size entities, it only adds clutter */
285 if (ltype->bit_size != ctype->bit_size)
286 *lp = cast_to(left, ctype);
287 if (rtype->bit_size != ctype->bit_size)
288 *rp = cast_to(right, ctype);
289 return ctype;
290 }
291 return NULL;
292 }
293
294 static struct symbol *evaluate_arith(struct expression *expr, int float_ok)
295 {
296 struct symbol *ctype = compatible_integer_binop(&expr->left, &expr->right);
297 if (!ctype && float_ok)
298 ctype = compatible_float_binop(&expr->left, &expr->right);
299 if (ctype) {
300 expr->ctype = ctype;
301 return ctype;
302 }
303 return bad_expr_type(expr);
304 }
305
306 static inline int lvalue_expression(struct expression *expr)
307 {
308 return (expr->type == EXPR_PREOP && expr->op == '*') || expr->type == EXPR_BITFIELD;
309 }
310
311 static struct symbol *evaluate_ptr_add(struct expression *expr, struct expression *ptr, struct expression *i)
312 {
313 struct symbol *ctype;
314 struct symbol *ptr_type = ptr->ctype;
315 int bit_size;
316
317 if (ptr_type->type == SYM_NODE)
318 ptr_type = ptr_type->ctype.base_type;
319
320 if (!is_int_type(i->ctype))
321 return bad_expr_type(expr);
322
323 ctype = ptr->ctype;
324 examine_symbol_type(ctype);
325
326 ctype = degenerate(ptr);
327 if (!ctype->ctype.base_type) {
328 warn(expr->pos, "missing type information");
329 return NULL;
330 }
331
332 /* Get the size of whatever the pointer points to */
333 ptr_type = ctype;
334 if (ptr_type->type == SYM_NODE)
335 ptr_type = ptr_type->ctype.base_type;
336 if (ptr_type->type == SYM_PTR)
337 ptr_type = ptr_type->ctype.base_type;
338 bit_size = ptr_type->bit_size;
339
340 /* Special case: adding zero commonly happens as a result of 'array[0]' */
341 if (i->type == EXPR_VALUE && !i->value) {
342 *expr = *ptr;
343 } else if (bit_size > bits_in_char) {
344 struct expression *add = expr;
345 struct expression *mul = alloc_expression(expr->pos, EXPR_BINOP);
346 struct expression *val = alloc_expression(expr->pos, EXPR_VALUE);
347
348 val->ctype = size_t_ctype;
349 val->value = bit_size >> 3;
350
351 mul->op = '*';
352 mul->ctype = size_t_ctype;
353 mul->left = i;
354 mul->right = val;
355
356 /* Leave 'add->op' as 'expr->op' - either '+' or '-' */
357 add->left = ptr;
358 add->right = mul;
359 }
360
361 expr->ctype = ctype;
362 return ctype;
363 }
364
365 static struct symbol *evaluate_add(struct expression *expr)
366 {
367 struct expression *left = expr->left, *right = expr->right;
368 struct symbol *ltype = left->ctype, *rtype = right->ctype;
369
370 if (is_ptr_type(ltype))
371 return evaluate_ptr_add(expr, left, right);
372
373 if (is_ptr_type(rtype))
374 return evaluate_ptr_add(expr, right, left);
375
376 return evaluate_arith(expr, 1);
377 }
378
379 #define MOD_SIZE (MOD_CHAR | MOD_SHORT | MOD_LONG | MOD_LONGLONG)
380 #define MOD_IGNORE (MOD_TOPLEVEL | MOD_STORAGE | MOD_ADDRESSABLE | MOD_SIGNED | MOD_UNSIGNED | MOD_ASSIGNED | MOD_USERTYPE | MOD_FORCE | MOD_ACCESSED)
381
382 const char * type_difference(struct symbol *target, struct symbol *source,
383 unsigned long target_mod_ignore, unsigned long source_mod_ignore)
384 {
385 for (;;) {
386 unsigned long mod1, mod2, diff;
387 unsigned long as1, as2;
388 int type1, type2;
389 struct symbol *base1, *base2;
390
391 if (target == source)
392 break;
393 if (!target || !source)
394 return "different types";
395 /*
396 * Peel of per-node information.
397 * FIXME! Check alignment and context too here!
398 */
399 mod1 = target->ctype.modifiers;
400 as1 = target->ctype.as;
401 mod2 = source->ctype.modifiers;
402 as2 = source->ctype.as;
403 if (target->type == SYM_NODE) {
404 target = target->ctype.base_type;
405 if (!target)
406 return "bad types";
407 if (target->type == SYM_PTR) {
408 mod1 = 0;
409 as1 = 0;
410 }
411 mod1 |= target->ctype.modifiers;
412 as1 |= target->ctype.as;
413 }
414 if (source->type == SYM_NODE) {
415 source = source->ctype.base_type;
416 if (!source)
417 return "bad types";
418 if (source->type == SYM_PTR) {
419 mod2 = 0;
420 as2 = 0;
421 }
422 mod2 |= source->ctype.modifiers;
423 as2 |= source->ctype.as;
424 }
425
426 if (target == source)
427 break;
428 if (!target || !source)
429 return "different types";
430
431 type1 = target->type;
432 base1 = target->ctype.base_type;
433
434 type2 = source->type;
435 base2 = source->ctype.base_type;
436
437 /*
438 * Pointers to functions compare as the function itself
439 */
440 if (type1 == SYM_PTR && base1) {
441 switch (base1->type) {
442 case SYM_FN:
443 type1 = SYM_FN;
444 target = base1;
445 base1 = base1->ctype.base_type;
446 default:
447 /* nothing */;
448 }
449 }
450 if (type2 == SYM_PTR && base2) {
451 switch (base2->type) {
452 case SYM_FN:
453 type2 = SYM_FN;
454 source = base2;
455 base2 = base2->ctype.base_type;
456 default:
457 /* nothing */;
458 }
459 }
460
461 /* Arrays degenerate to pointers for type comparisons */
462 type1 = (type1 == SYM_ARRAY) ? SYM_PTR : type1;
463 type2 = (type2 == SYM_ARRAY) ? SYM_PTR : type2;
464
465 if (type1 != type2)
466 return "different base types";
467
468 /* Must be same address space to be comparable */
469 if (as1 != as2)
470 return "different address spaces";
471
472 /* Ignore differences in storage types, sign, or addressability */
473 diff = (mod1 ^ mod2) & ~MOD_IGNORE;
474 if (diff) {
475 mod1 &= diff & ~target_mod_ignore;
476 mod2 &= diff & ~source_mod_ignore;
477 if (mod1 | mod2) {
478 if ((mod1 | mod2) & MOD_SIZE)
479 return "different type sizes";
480 return "different modifiers";
481 }
482 }
483
484 if (type1 == SYM_FN) {
485 int i;
486 struct symbol *arg1, *arg2;
487 if (base1->variadic != base2->variadic)
488 return "incompatible variadic arguments";
489 PREPARE_PTR_LIST(target->arguments, arg1);
490 PREPARE_PTR_LIST(source->arguments, arg2);
491 i = 1;
492 for (;;) {
493 const char *diff;
494 diff = type_difference(arg1, arg2, 0, 0);
495 if (diff) {
496 static char argdiff[80];
497 sprintf(argdiff, "incompatible argument %d (%s)", i, diff);
498 return argdiff;
499 }
500 if (!arg1)
501 break;
502 NEXT_PTR_LIST(arg1);
503 NEXT_PTR_LIST(arg2);
504 i++;
505 }
506 FINISH_PTR_LIST(arg2);
507 FINISH_PTR_LIST(arg1);
508 }
509
510 target = base1;
511 source = base2;
512 }
513 return NULL;
514 }
515
516 static int is_null_ptr(struct expression *expr)
517 {
518 if (expr->type != EXPR_VALUE || expr->value)
519 return 0;
520 if (!is_ptr_type(expr->ctype))
521 warn(expr->pos, "Using plain integer as NULL pointer");
522 return 1;
523 }
524
525 static struct symbol *common_ptr_type(struct expression *l, struct expression *r)
526 {
527 /* NULL expression? Just return the type of the "other side" */
528 if (is_null_ptr(r))
529 return l->ctype;
530 if (is_null_ptr(l))
531 return r->ctype;
532 return NULL;
533 }
534
535 /*
536 * Ignore differences in "volatile" and "const"ness when
537 * subtracting pointers
538 */
539 #define MOD_IGN (MOD_VOLATILE | MOD_CONST)
540
541 static struct symbol *evaluate_ptr_sub(struct expression *expr, struct expression *l, struct expression *r)
542 {
543 const char *typediff;
544 struct symbol *ctype;
545 struct symbol *ltype, *rtype;
546
547 ltype = degenerate(l);
548 rtype = degenerate(r);
549
550 /*
551 * If it is an integer subtract: the ptr add case will do the
552 * right thing.
553 */
554 if (!is_ptr_type(rtype))
555 return evaluate_ptr_add(expr, l, r);
556
557 ctype = ltype;
558 typediff = type_difference(ltype, rtype, ~MOD_SIZE, ~MOD_SIZE);
559 if (typediff) {
560 ctype = common_ptr_type(l, r);
561 if (!ctype) {
562 warn(expr->pos, "subtraction of different types can't work (%s)", typediff);
563 return NULL;
564 }
565 }
566 examine_symbol_type(ctype);
567
568 /* Figure out the base type we point to */
569 if (ctype->type == SYM_NODE)
570 ctype = ctype->ctype.base_type;
571 if (ctype->type != SYM_PTR && ctype->type != SYM_ARRAY) {
572 warn(expr->pos, "subtraction of functions? Share your drugs");
573 return NULL;
574 }
575 ctype = ctype->ctype.base_type;
576
577 expr->ctype = ssize_t_ctype;
578 if (ctype->bit_size > bits_in_char) {
579 struct expression *sub = alloc_expression(expr->pos, EXPR_BINOP);
580 struct expression *div = expr;
581 struct expression *val = alloc_expression(expr->pos, EXPR_VALUE);
582
583 val->ctype = size_t_ctype;
584 val->value = ctype->bit_size >> 3;
585
586 sub->op = '-';
587 sub->ctype = ssize_t_ctype;
588 sub->left = l;
589 sub->right = r;
590
591 div->op = '/';
592 div->left = sub;
593 div->right = val;
594 }
595
596 return ssize_t_ctype;
597 }
598
599 static struct symbol *evaluate_sub(struct expression *expr)
600 {
601 struct expression *left = expr->left, *right = expr->right;
602 struct symbol *ltype = left->ctype;
603
604 if (is_ptr_type(ltype))
605 return evaluate_ptr_sub(expr, left, right);
606
607 return evaluate_arith(expr, 1);
608 }
609
610 #define is_safe_type(type) ((type)->ctype.modifiers & MOD_SAFE)
611
612 static struct symbol *evaluate_conditional(struct expression **p)
613 {
614 struct symbol *ctype;
615 struct expression *expr = *p;
616
617 if (!expr)
618 return NULL;
619
620 if (expr->type == EXPR_ASSIGNMENT)
621 warn(expr->pos, "assignment expression in conditional");
622
623 ctype = evaluate_expression(expr);
624 if (ctype) {
625 if (is_safe_type(ctype))
626 warn(expr->pos, "testing a 'safe expression'");
627 if (is_float_type(ctype)) {
628 struct expression *comp;
629 /*
630 * It's easier to handle here, rather than deal with
631 * FP all over the place. Floating point in boolean
632 * context is rare enough (and very often wrong),
633 * so price of explicit comparison with appropriate
634 * FP zero is not too high. And it simplifies things
635 * elsewhere.
636 */
637 comp = alloc_expression(expr->pos, EXPR_BINOP);
638 comp->op = SPECIAL_NOTEQUAL;
639 comp->left = expr;
640 comp->right = alloc_expression(expr->pos, EXPR_FVALUE);
641 comp->right->ctype = comp->left->ctype;
642 comp->right->fvalue = 0;
643 ctype = comp->ctype = &bool_ctype;
644 *p = comp;
645 }
646 }
647
648 return ctype;
649 }
650
651 static struct symbol *evaluate_logical(struct expression *expr)
652 {
653 if (!evaluate_conditional(&expr->left))
654 return NULL;
655 if (!evaluate_conditional(&expr->right))
656 return NULL;
657
658 expr->ctype = &bool_ctype;
659 return &bool_ctype;
660 }
661
662 static struct symbol *evaluate_shift(struct expression *expr)
663 {
664 struct expression *left = expr->left, *right = expr->right;
665 struct symbol *ltype = left->ctype, *rtype = right->ctype;
666
667 if (ltype->type == SYM_NODE)
668 ltype = ltype->ctype.base_type;
669 if (rtype->type == SYM_NODE)
670 rtype = rtype->ctype.base_type;
671 if (is_int_type(ltype) && is_int_type(rtype)) {
672 struct symbol *ctype = integer_promotion(ltype);
673 if (ltype->bit_size != ctype->bit_size)
674 expr->left = cast_to(expr->left, ctype);
675 expr->ctype = ctype;
676 ctype = integer_promotion(rtype);
677 if (rtype->bit_size != ctype->bit_size)
678 expr->right = cast_to(expr->right, ctype);
679 return expr->ctype;
680 }
681 return bad_expr_type(expr);
682 }
683
684 static struct symbol *evaluate_binop(struct expression *expr)
685 {
686 switch (expr->op) {
687 // addition can take ptr+int, fp and int
688 case '+':
689 return evaluate_add(expr);
690
691 // subtraction can take ptr-ptr, fp and int
692 case '-':
693 return evaluate_sub(expr);
694
695 // Arithmetic operations can take fp and int
696 case '*': case '/':
697 return evaluate_arith(expr, 1);
698
699 // shifts do integer promotions, but that's it.
700 case SPECIAL_LEFTSHIFT: case SPECIAL_RIGHTSHIFT:
701 return evaluate_shift(expr);
702
703 // The rest are integer operations
704 // '%', '&', '^', '|'
705 default:
706 return evaluate_arith(expr, 0);
707 }
708 }
709
710 static struct symbol *evaluate_comma(struct expression *expr)
711 {
712 expr->ctype = expr->right->ctype;
713 return expr->ctype;
714 }
715
716 static int modify_for_unsigned(int op)
717 {
718 if (op == '<')
719 op = SPECIAL_UNSIGNED_LT;
720 else if (op == '>')
721 op = SPECIAL_UNSIGNED_GT;
722 else if (op == SPECIAL_LTE)
723 op = SPECIAL_UNSIGNED_LTE;
724 else if (op == SPECIAL_GTE)
725 op = SPECIAL_UNSIGNED_GTE;
726 return op;
727 }
728
729 static struct symbol *evaluate_compare(struct expression *expr)
730 {
731 struct expression *left = expr->left, *right = expr->right;
732 struct symbol *ltype = left->ctype, *rtype = right->ctype;
733 struct symbol *ctype;
734
735 /* Type types? */
736 if (is_type_type(ltype) && is_type_type(rtype)) {
737 expr->ctype = &bool_ctype;
738 return &bool_ctype;
739 }
740
741 if (is_safe_type(ltype) || is_safe_type(rtype))
742 warn(expr->pos, "testing a 'safe expression'");
743
744 /* Pointer types? */
745 if (is_ptr_type(ltype) || is_ptr_type(rtype)) {
746 expr->ctype = &bool_ctype;
747 // FIXME! Check the types for compatibility
748 return &bool_ctype;
749 }
750
751 ctype = compatible_integer_binop(&expr->left, &expr->right);
752 if (ctype) {
753 if (ctype->ctype.modifiers & MOD_UNSIGNED)
754 expr->op = modify_for_unsigned(expr->op);
755 expr->ctype = &bool_ctype;
756 return &bool_ctype;
757 }
758 ctype = compatible_float_binop(&expr->left, &expr->right);
759 if (ctype) {
760 expr->ctype = &bool_ctype;
761 return &bool_ctype;
762 }
763
764 return bad_expr_type(expr);
765 }
766
767 /*
768 * FIXME!! This should do casts, array degeneration etc..
769 */
770 static struct symbol *compatible_ptr_type(struct expression *left, struct expression *right)
771 {
772 struct symbol *ltype = left->ctype, *rtype = right->ctype;
773
774 if (ltype->type == SYM_NODE)
775 ltype = ltype->ctype.base_type;
776
777 if (rtype->type == SYM_NODE)
778 rtype = rtype->ctype.base_type;
779
780 if (ltype->type == SYM_PTR) {
781 if (is_null_ptr(right) || rtype->ctype.base_type == &void_ctype)
782 return ltype;
783 }
784
785 if (rtype->type == SYM_PTR) {
786 if (is_null_ptr(left) || ltype->ctype.base_type == &void_ctype)
787 return rtype;
788 }
789 return NULL;
790 }
791
792 static struct symbol * evaluate_conditional_expression(struct expression *expr)
793 {
794 struct expression *cond, *true, *false;
795 struct symbol *ctype, *ltype, *rtype;
796 const char * typediff;
797
798 ctype = degenerate(expr->conditional);
799 cond = expr->conditional;
800
801 ltype = ctype;
802 true = cond;
803 if (expr->cond_true) {
804 ltype = degenerate(expr->cond_true);
805 true = expr->cond_true;
806 }
807
808 rtype = degenerate(expr->cond_false);
809 false = expr->cond_false;
810
811 ctype = ltype;
812 typediff = type_difference(ltype, rtype, MOD_IGN, MOD_IGN);
813 if (!typediff)
814 goto out;
815
816 ctype = compatible_integer_binop(&true, &expr->cond_false);
817 if (ctype)
818 goto out;
819 ctype = compatible_ptr_type(true, expr->cond_false);
820 if (ctype)
821 goto out;
822 ctype = compatible_float_binop(&true, &expr->cond_false);
823 if (ctype)
824 goto out;
825 warn(expr->pos, "incompatible types in conditional expression (%s)", typediff);
826 return NULL;
827
828 out:
829 expr->ctype = ctype;
830 return ctype;
831 }
832
833 static int compatible_assignment_types(struct expression *expr, struct symbol *target,
834 struct expression **rp, struct symbol *source, const char *where)
835 {
836 const char *typediff;
837 struct symbol *t;
838 int target_as;
839
840 /* It's ok if the target is more volatile or const than the source */
841 typediff = type_difference(target, source, MOD_VOLATILE | MOD_CONST, 0);
842 if (!typediff)
843 return 1;
844
845 if (is_int_type(target)) {
846 if (is_int_type(source)) {
847 if (target->bit_size != source->bit_size)
848 goto Cast;
849 return 1;
850 }
851 if (is_float_type(source))
852 goto Cast;
853 } else if (is_float_type(target)) {
854 if (is_int_type(source))
855 goto Cast;
856 if (is_float_type(source)) {
857 if (target->bit_size != source->bit_size)
858 goto Cast;
859 return 1;
860 }
861 }
862
863 /* Pointer destination? */
864 t = target;
865 target_as = t->ctype.as;
866 if (t->type == SYM_NODE) {
867 t = t->ctype.base_type;
868 target_as |= t->ctype.as;
869 }
870 if (t->type == SYM_PTR || t->type == SYM_FN || t->type == SYM_ARRAY) {
871 struct expression *right = *rp;
872 struct symbol *s = source;
873 int source_as;
874
875 // NULL pointer is always ok
876 if (is_null_ptr(right))
877 return 1;
878
879 /* "void *" matches anything as long as the address space is ok */
880 source_as = s->ctype.as;
881 if (s->type == SYM_NODE) {
882 s = s->ctype.base_type;
883 source_as |= s->ctype.as;
884 }
885 if (source_as == target_as && (s->type == SYM_PTR || s->type == SYM_ARRAY)) {
886 s = s->ctype.base_type;
887 t = t->ctype.base_type;
888 if (s == &void_ctype || t == &void_ctype)
889 return 1;
890 }
891 }
892
893 warn(expr->pos, "incorrect type in %s (%s)", where, typediff);
894 info(expr->pos, " expected %s", show_typename(target));
895 info(expr->pos, " got %s", show_typename(source));
896 *rp = cast_to(*rp, target);
897 return 0;
898 Cast:
899 *rp = cast_to(*rp, target);
900 return 1;
901 }
902
903 /*
904 * FIXME!! This is wrong from a double evaluation standpoint. We can't
905 * just expand the expression twice, that would make any side effects
906 * happen twice too.
907 */
908 static struct symbol *evaluate_binop_assignment(struct expression *expr, struct expression *left, struct expression *right)
909 {
910 int op = expr->op;
911 struct expression *subexpr = alloc_expression(expr->pos, EXPR_BINOP);
912 static const int op_trans[] = {
913 [SPECIAL_ADD_ASSIGN - SPECIAL_BASE] = '+',
914 [SPECIAL_SUB_ASSIGN - SPECIAL_BASE] = '-',
915 [SPECIAL_MUL_ASSIGN - SPECIAL_BASE] = '*',
916 [SPECIAL_DIV_ASSIGN - SPECIAL_BASE] = '/',
917 [SPECIAL_MOD_ASSIGN - SPECIAL_BASE] = '%',
918 [SPECIAL_SHL_ASSIGN - SPECIAL_BASE] = SPECIAL_LEFTSHIFT,
919 [SPECIAL_SHR_ASSIGN - SPECIAL_BASE] = SPECIAL_RIGHTSHIFT,
920 [SPECIAL_AND_ASSIGN - SPECIAL_BASE] = '&',
921 [SPECIAL_OR_ASSIGN - SPECIAL_BASE] = '|',
922 [SPECIAL_XOR_ASSIGN - SPECIAL_BASE] = '^'
923 };
924
925 subexpr->left = left;
926 subexpr->right = right;
927 subexpr->op = op_trans[op - SPECIAL_BASE];
928 expr->op = '=';
929 expr->right = subexpr;
930 return evaluate_binop(subexpr);
931 }
932
933 static void evaluate_assign_to(struct expression *left, struct symbol *type)
934 {
935 if (type->ctype.modifiers & MOD_CONST)
936 warn(left->pos, "assignment to const expression");
937 if (type->type == SYM_NODE)
938 type->ctype.modifiers |= MOD_ASSIGNED;
939 }
940
941 static struct symbol *evaluate_assignment(struct expression *expr)
942 {
943 struct expression *left = expr->left, *right = expr->right;
944 struct symbol *ltype, *rtype;
945
946 ltype = left->ctype;
947 rtype = right->ctype;
948 if (expr->op != '=') {
949 rtype = evaluate_binop_assignment(expr, left, right);
950 if (!rtype)
951 return NULL;
952 right = expr->right;
953 }
954
955 if (!lvalue_expression(left)) {
956 warn(expr->pos, "not an lvalue");
957 return NULL;
958 }
959
960 rtype = degenerate(right);
961
962 if (!compatible_assignment_types(expr, ltype, &expr->right, rtype, "assignment"))
963 return NULL;
964
965 evaluate_assign_to(left, ltype);
966
967 expr->ctype = ltype;
968 return ltype;
969 }
970
971 static void examine_fn_arguments(struct symbol *fn)
972 {
973 struct symbol *s;
974
975 FOR_EACH_PTR(fn->arguments, s) {
976 struct symbol *arg = evaluate_symbol(s);
977 /* Array/function arguments silently degenerate into pointers */
978 if (arg) {
979 struct symbol *ptr;
980 switch(arg->type) {
981 case SYM_ARRAY:
982 case SYM_FN:
983 ptr = alloc_symbol(s->pos, SYM_PTR);
984 if (arg->type == SYM_ARRAY)
985 ptr->ctype = arg->ctype;
986 else
987 ptr->ctype.base_type = arg;
988 ptr->ctype.as |= s->ctype.as;
989 ptr->ctype.modifiers |= s->ctype.modifiers;
990
991 s->ctype.base_type = ptr;
992 s->ctype.as = 0;
993 s->ctype.modifiers = 0;
994 examine_symbol_type(s);
995 break;
996 default:
997 /* nothing */
998 break;
999 }
1000 }
1001 } END_FOR_EACH_PTR;
1002 }
1003
1004 static struct symbol *convert_to_as_mod(struct symbol *sym, int as, int mod)
1005 {
1006 if (sym->ctype.as != as || sym->ctype.modifiers != mod) {
1007 struct symbol *newsym = alloc_symbol(sym->pos, SYM_NODE);
1008 *newsym = *sym;
1009 newsym->ctype.as = as;
1010 newsym->ctype.modifiers = mod;
1011 sym = newsym;
1012 }
1013 return sym;
1014 }
1015
1016 static struct symbol *create_pointer(struct expression *expr, struct symbol *sym, int degenerate)
1017 {
1018 struct symbol *node = alloc_symbol(expr->pos, SYM_NODE);
1019 struct symbol *ptr = alloc_symbol(expr->pos, SYM_PTR);
1020
1021 node->ctype.base_type = ptr;
1022 ptr->bit_size = bits_in_pointer;
1023 ptr->ctype.alignment = pointer_alignment;
1024
1025 node->bit_size = bits_in_pointer;
1026 node->ctype.alignment = pointer_alignment;
1027
1028 access_symbol(sym);
1029 sym->ctype.modifiers |= MOD_ADDRESSABLE;
1030 if (sym->ctype.modifiers & MOD_REGISTER) {
1031 warn(expr->pos, "taking address of 'register' variable '%s'", show_ident(sym->ident));
1032 sym->ctype.modifiers &= ~MOD_REGISTER;
1033 }
1034 if (sym->type == SYM_NODE) {
1035 ptr->ctype.as |= sym->ctype.as;
1036 ptr->ctype.modifiers |= sym->ctype.modifiers;
1037 sym = sym->ctype.base_type;
1038 }
1039 if (degenerate && sym->type == SYM_ARRAY) {
1040 ptr->ctype.as |= sym->ctype.as;
1041 ptr->ctype.modifiers |= sym->ctype.modifiers;
1042 sym = sym->ctype.base_type;
1043 }
1044 ptr->ctype.base_type = sym;
1045
1046 return node;
1047 }
1048
1049 /* Arrays degenerate into pointers on pointer arithmetic */
1050 static struct symbol *degenerate(struct expression *expr)
1051 {
1052 struct symbol *ctype, *base;
1053
1054 if (!expr)
1055 return NULL;
1056 ctype = expr->ctype;
1057 if (!ctype)
1058 return NULL;
1059 base = ctype;
1060 if (ctype->type == SYM_NODE)
1061 base = ctype->ctype.base_type;
1062 /*
1063 * Arrays degenerate into pointers to the entries, while
1064 * functions degenerate into pointers to themselves.
1065 * If array was part of non-lvalue compound, we create a copy
1066 * of that compound first and then act as if we were dealing with
1067 * the corresponding field in there.
1068 */
1069 switch (base->type) {
1070 case SYM_ARRAY:
1071 if (expr->type == EXPR_SLICE) {
1072 struct symbol *a = alloc_symbol(expr->pos, SYM_NODE);
1073 struct expression *e0, *e1, *e2, *e3, *e4;
1074
1075 a->ctype.base_type = expr->base->ctype;
1076 a->bit_size = expr->base->ctype->bit_size;
1077 a->array_size = expr->base->ctype->array_size;
1078
1079 e0 = alloc_expression(expr->pos, EXPR_SYMBOL);
1080 e0->symbol = a;
1081 e0->ctype = &lazy_ptr_ctype;
1082
1083 e1 = alloc_expression(expr->pos, EXPR_PREOP);
1084 e1->unop = e0;
1085 e1->op = '*';
1086 e1->ctype = expr->base->ctype; /* XXX */
1087
1088 e2 = alloc_expression(expr->pos, EXPR_ASSIGNMENT);
1089 e2->left = e1;
1090 e2->right = expr->base;
1091 e2->op = '=';
1092 e2->ctype = expr->base->ctype;
1093
1094 if (expr->r_bitpos) {
1095 e3 = alloc_expression(expr->pos, EXPR_BINOP);
1096 e3->op = '+';
1097 e3->left = e0;
1098 e3->right = alloc_const_expression(expr->pos,
1099 expr->r_bitpos >> 3);
1100 e3->ctype = &lazy_ptr_ctype;
1101 } else {
1102 e3 = e0;
1103 }
1104
1105 e4 = alloc_expression(expr->pos, EXPR_COMMA);
1106 e4->left = e2;
1107 e4->right = e3;
1108 e4->ctype = &lazy_ptr_ctype;
1109
1110 expr->unop = e4;
1111 expr->type = EXPR_PREOP;
1112 expr->op = '*';
1113 }
1114 case SYM_FN:
1115 if (expr->op != '*' || expr->type != EXPR_PREOP) {
1116 warn(expr->pos, "strange non-value function or array");
1117 return NULL;
1118 }
1119 *expr = *expr->unop;
1120 ctype = create_pointer(expr, ctype, 1);
1121 expr->ctype = ctype;
1122 default:
1123 /* nothing */;
1124 }
1125 return ctype;
1126 }
1127
1128 static struct symbol *evaluate_addressof(struct expression *expr)
1129 {
1130 struct expression *op = expr->unop;
1131 struct symbol *ctype;
1132
1133 if (op->op != '*' || op->type != EXPR_PREOP) {
1134 warn(expr->pos, "not addressable");
1135 return NULL;
1136 }
1137 ctype = op->ctype;
1138 *expr = *op->unop;
1139
1140 /*
1141 * symbol expression evaluation is lazy about the type
1142 * of the sub-expression, so we may have to generate
1143 * the type here if so..
1144 */
1145 if (expr->ctype == &lazy_ptr_ctype) {
1146 ctype = create_pointer(expr, ctype, 0);
1147 expr->ctype = ctype;
1148 }
1149 return expr->ctype;
1150 }
1151
1152
1153 static struct symbol *evaluate_dereference(struct expression *expr)
1154 {
1155 struct expression *op = expr->unop;
1156 struct symbol *ctype = op->ctype, *node, *target;
1157
1158 /* Simplify: *&(expr) => (expr) */
1159 if (op->type == EXPR_PREOP && op->op == '&') {
1160 *expr = *op->unop;
1161 return expr->ctype;
1162 }
1163
1164 /* Dereferencing a node drops all the node information. */
1165 if (ctype->type == SYM_NODE)
1166 ctype = ctype->ctype.base_type;
1167
1168 node = alloc_symbol(expr->pos, SYM_NODE);
1169 target = ctype->ctype.base_type;
1170
1171 switch (ctype->type) {
1172 default:
1173 warn(expr->pos, "cannot derefence this type");
1174 return NULL;
1175 case SYM_PTR:
1176 merge_type(node, ctype);
1177 if (ctype->type != SYM_ARRAY)
1178 break;
1179 /*
1180 * Dereferencing a pointer to an array results in a
1181 * degenerate dereference: the expression becomes
1182 * just a pointer to the entry, and the derefence
1183 * goes away.
1184 */
1185 *expr = *op;
1186
1187 target = alloc_symbol(expr->pos, SYM_PTR);
1188 target->bit_size = bits_in_pointer;
1189 target->ctype.alignment = pointer_alignment;
1190 merge_type(target, ctype->ctype.base_type);
1191 break;
1192
1193 case SYM_ARRAY:
1194 /*
1195 * When an array is dereferenced, we need to pick
1196 * up the attributes of the original node too..
1197 */
1198 merge_type(node, op->ctype);
1199 merge_type(node, ctype);
1200 break;
1201 }
1202
1203 node->bit_size = target->bit_size;
1204 node->array_size = target->array_size;
1205
1206 expr->ctype = node;
1207 return node;
1208 }
1209
1210 /*
1211 * Unary post-ops: x++ and x--
1212 */
1213 static struct symbol *evaluate_postop(struct expression *expr)
1214 {
1215 struct expression *op = expr->unop;
1216 struct symbol *ctype = op->ctype;
1217
1218 if (!lvalue_expression(expr->unop)) {
1219 warn(expr->pos, "need lvalue expression for ++/--");
1220 return NULL;
1221 }
1222
1223 evaluate_assign_to(op, ctype);
1224
1225 expr->ctype = ctype;
1226 return ctype;
1227 }
1228
1229 static struct symbol *evaluate_sign(struct expression *expr)
1230 {
1231 struct symbol *ctype = expr->unop->ctype;
1232 if (is_int_type(ctype)) {
1233 struct symbol *rtype = rtype = integer_promotion(ctype);
1234 if (rtype->bit_size != ctype->bit_size)
1235 expr->unop = cast_to(expr->unop, rtype);
1236 ctype = rtype;
1237 } else if (is_float_type(ctype) && expr->op != '%') {
1238 /* no conversions needed */
1239 } else {
1240 return bad_expr_type(expr);
1241 }
1242 if (expr->op == '+')
1243 *expr = *expr->unop;
1244 expr->ctype = ctype;
1245 return ctype;
1246 }
1247
1248 static struct symbol *evaluate_preop(struct expression *expr)
1249 {
1250 struct symbol *ctype = expr->unop->ctype;
1251
1252 switch (expr->op) {
1253 case '(':
1254 *expr = *expr->unop;
1255 return ctype;
1256
1257 case '+':
1258 case '-':
1259 case '~':
1260 return evaluate_sign(expr);
1261
1262 case '*':
1263 return evaluate_dereference(expr);
1264
1265 case '&':
1266 return evaluate_addressof(expr);
1267
1268 case SPECIAL_INCREMENT:
1269 case SPECIAL_DECREMENT:
1270 /*
1271 * From a type evaluation standpoint the pre-ops are
1272 * the same as the postops
1273 */
1274 return evaluate_postop(expr);
1275
1276 case '!':
1277 if (is_safe_type(ctype))
1278 warn(expr->pos, "testing a 'safe expression'");
1279 if (is_float_type(ctype)) {
1280 struct expression *arg = expr->unop;
1281 expr->type = EXPR_BINOP;
1282 expr->op = SPECIAL_EQUAL;
1283 expr->left = arg;
1284 expr->right = alloc_expression(expr->pos, EXPR_FVALUE);
1285 expr->right->ctype = ctype;
1286 expr->right->fvalue = 0;
1287 }
1288 ctype = &bool_ctype;
1289 break;
1290
1291 default:
1292 break;
1293 }
1294 expr->ctype = ctype;
1295 return &bool_ctype;
1296 }
1297
1298 struct symbol *find_identifier(struct ident *ident, struct symbol_list *_list, int *offset)
1299 {
1300 struct ptr_list *head = (struct ptr_list *)_list;
1301 struct ptr_list *list = head;
1302
1303 if (!head)
1304 return NULL;
1305 do {
1306 int i;
1307 for (i = 0; i < list->nr; i++) {
1308 struct symbol *sym = (struct symbol *) list->list[i];
1309 if (sym->ident) {
1310 if (sym->ident != ident)
1311 continue;
1312 *offset = sym->offset;
1313 return sym;
1314 } else {
1315 struct symbol *ctype = sym->ctype.base_type;
1316 struct symbol *sub;
1317 if (!ctype)
1318 continue;
1319 if (ctype->type != SYM_UNION && ctype->type != SYM_STRUCT)
1320 continue;
1321 sub = find_identifier(ident, ctype->symbol_list, offset);
1322 if (!sub)
1323 continue;
1324 *offset += sym->offset;
1325 return sub;
1326 }
1327 }
1328 } while ((list = list->next) != head);
1329 return NULL;
1330 }
1331
1332 static struct expression *evaluate_offset(struct expression *expr, unsigned long offset)
1333 {
1334 struct expression *add;
1335
1336 /*
1337 * Create a new add-expression
1338 *
1339 * NOTE! Even if we just add zero, we need a new node
1340 * for the member pointer, since it has a different
1341 * type than the original pointer. We could make that
1342 * be just a cast, but the fact is, a node is a node,
1343 * so we might as well just do the "add zero" here.
1344 */
1345 add = alloc_expression(expr->pos, EXPR_BINOP);
1346 add->op = '+';
1347 add->left = expr;
1348 add->right = alloc_expression(expr->pos, EXPR_VALUE);
1349 add->right->ctype = &int_ctype;
1350 add->right->value = offset;
1351
1352 /*
1353 * The ctype of the pointer will be lazily evaluated if
1354 * we ever take the address of this member dereference..
1355 */
1356 add->ctype = &lazy_ptr_ctype;
1357 return add;
1358 }
1359
1360 /* structure/union dereference */
1361 static struct symbol *evaluate_member_dereference(struct expression *expr)
1362 {
1363 int offset;
1364 struct symbol *ctype, *member;
1365 struct expression *deref = expr->deref, *add;
1366 struct ident *ident = expr->member;
1367 unsigned int mod;
1368 int address_space;
1369
1370 if (!evaluate_expression(deref))
1371 return NULL;
1372 if (!ident) {
1373 warn(expr->pos, "bad member name");
1374 return NULL;
1375 }
1376
1377 ctype = deref->ctype;
1378 address_space = ctype->ctype.as;
1379 mod = ctype->ctype.modifiers;
1380 if (ctype->type == SYM_NODE) {
1381 ctype = ctype->ctype.base_type;
1382 address_space |= ctype->ctype.as;
1383 mod |= ctype->ctype.modifiers;
1384 }
1385 if (!ctype || (ctype->type != SYM_STRUCT && ctype->type != SYM_UNION)) {
1386 warn(expr->pos, "expected structure or union");
1387 return NULL;
1388 }
1389 offset = 0;
1390 member = find_identifier(ident, ctype->symbol_list, &offset);
1391 if (!member) {
1392 const char *type = ctype->type == SYM_STRUCT ? "struct" : "union";
1393 const char *name = "<unnamed>";
1394 int namelen = 9;
1395 if (ctype->ident) {
1396 name = ctype->ident->name;
1397 namelen = ctype->ident->len;
1398 }
1399 warn(expr->pos, "no member '%s' in %s %.*s",
1400 show_ident(ident), type, namelen, name);
1401 return NULL;
1402 }
1403
1404 /*
1405 * The member needs to take on the address space and modifiers of
1406 * the "parent" type.
1407 */
1408 member = convert_to_as_mod(member, address_space, mod);
1409 ctype = member->ctype.base_type;
1410
1411 if (!lvalue_expression(deref)) {
1412 if (deref->type != EXPR_SLICE) {
1413 expr->base = deref;
1414 expr->r_bitpos = 0;
1415 } else {
1416 expr->base = deref->base;
1417 expr->r_bitpos = deref->r_bitpos;
1418 }
1419 expr->r_bitpos += offset << 3;
1420 expr->type = EXPR_SLICE;
1421 if (ctype->type == SYM_BITFIELD) {
1422 expr->r_bitpos += member->bit_offset;
1423 expr->r_nrbits = member->fieldwidth;
1424 } else {
1425 expr->r_nrbits = member->bit_size;
1426 }
1427 expr->ctype = member;
1428 return member;
1429 }
1430
1431 deref = deref->unop;
1432 expr->deref = deref;
1433
1434 add = evaluate_offset(deref, offset);
1435 if (ctype->type == SYM_BITFIELD) {
1436 expr->type = EXPR_BITFIELD;
1437 expr->bitpos = member->bit_offset;
1438 expr->nrbits = member->fieldwidth;
1439 expr->address = add;
1440 } else {
1441 expr->type = EXPR_PREOP;
1442 expr->op = '*';
1443 expr->unop = add;
1444 }
1445
1446 expr->ctype = member;
1447 return member;
1448 }
1449
1450 static struct symbol *evaluate_cast(struct expression *);
1451
1452 static struct symbol *evaluate_sizeof(struct expression *expr)
1453 {
1454 int size;
1455
1456 if (expr->cast_type) {
1457 if (expr->cast_expression) {
1458 struct symbol *sym = evaluate_cast(expr);
1459 size = sym->bit_size;
1460 } else {
1461 examine_symbol_type(expr->cast_type);
1462 size = expr->cast_type->bit_size;
1463 }
1464 } else {
1465 if (!evaluate_expression(expr->cast_expression))
1466 return NULL;
1467 size = expr->cast_expression->ctype->bit_size;
1468 }
1469 if (size & 7)
1470 warn(expr->pos, "cannot size expression");
1471 expr->type = EXPR_VALUE;
1472 expr->value = size >> 3;
1473 expr->ctype = size_t_ctype;
1474 return size_t_ctype;
1475 }
1476
1477 static struct symbol *evaluate_alignof(struct expression *expr)
1478 {
1479 struct symbol *type = expr->cast_type;
1480
1481 if (!type) {
1482 type = evaluate_expression(expr->cast_expression);
1483 if (!type)
1484 return NULL;
1485 }
1486 examine_symbol_type(type);
1487 expr->type = EXPR_VALUE;
1488 expr->value = type->ctype.alignment;
1489 expr->ctype = size_t_ctype;
1490 return size_t_ctype;
1491 }
1492
1493 static int context_clash(struct symbol *sym1, struct symbol *sym2)
1494 {
1495 unsigned long clash = (sym1->ctype.context ^ sym2->ctype.context);
1496 clash &= (sym1->ctype.contextmask & sym2->ctype.contextmask);
1497 return clash != 0;
1498 }
1499
1500 static int evaluate_arguments(struct symbol *f, struct symbol *fn, struct expression_list *head)
1501 {
1502 struct expression *expr;
1503 struct symbol_list *argument_types = fn->arguments;
1504 struct symbol *argtype;
1505 int i = 1;
1506
1507 PREPARE_PTR_LIST(argument_types, argtype);
1508 FOR_EACH_PTR (head, expr) {
1509 struct expression **p = THIS_ADDRESS(expr);
1510 struct symbol *ctype, *target;
1511 ctype = evaluate_expression(expr);
1512
1513 if (!ctype)
1514 return 0;
1515
1516 if (context_clash(f, ctype))
1517 warn(expr->pos, "argument %d used in wrong context", i);
1518
1519 ctype = degenerate(expr);
1520
1521 target = argtype;
1522 if (!target && ctype->bit_size < bits_in_int)
1523 target = &int_ctype;
1524 if (target) {
1525 static char where[30];
1526 examine_symbol_type(target);
1527 sprintf(where, "argument %d", i);
1528 compatible_assignment_types(expr, target, p, ctype, where);
1529 }
1530
1531 i++;
1532 NEXT_PTR_LIST(argtype);
1533 } END_FOR_EACH_PTR;
1534 FINISH_PTR_LIST(argtype);
1535 return 1;
1536 }
1537
1538 static int evaluate_initializer(struct symbol *ctype, struct expression **ep, unsigned long offset);
1539 static int evaluate_array_initializer(struct symbol *ctype, struct expression *expr, unsigned long offset)
1540 {
1541 struct expression *entry;
1542 int current = 0;
1543 int max = 0;
1544 int accept_string = is_byte_type(ctype);
1545
1546 FOR_EACH_PTR(expr->expr_list, entry) {
1547 struct expression **p = THIS_ADDRESS(entry);
1548 struct symbol *sym;
1549 int entries;
1550
1551 if (entry->type == EXPR_INDEX) {
1552 current = entry->idx_to;
1553 continue;
1554 }
1555 if (accept_string && entry->type == EXPR_STRING) {
1556 sym = evaluate_expression(entry);
1557 entries = get_expression_value(sym->array_size);
1558 } else {
1559 evaluate_initializer(ctype, p, offset + current*(ctype->bit_size>>3));
1560 entries = 1;
1561 }
1562 current += entries;
1563 if (current > max)
1564 max = current;
1565 } END_FOR_EACH_PTR;
1566 return max;
1567 }
1568
1569 /* A scalar initializer is allowed, and acts pretty much like an array of one */
1570 static int evaluate_scalar_initializer(struct symbol *ctype, struct expression *expr, unsigned long offset)
1571 {
1572 if (offset || expression_list_size(expr->expr_list) != 1) {
1573 warn(expr->pos, "unexpected compound initializer");
1574 return 0;
1575 }
1576 return evaluate_array_initializer(ctype, expr, 0);
1577 }
1578
1579 static int evaluate_struct_or_union_initializer(struct symbol *ctype, struct expression *expr, int multiple, unsigned long offset)
1580 {
1581 struct expression *entry;
1582 struct symbol *sym;
1583
1584 PREPARE_PTR_LIST(ctype->symbol_list, sym);
1585 FOR_EACH_PTR(expr->expr_list, entry) {
1586 struct expression **p = THIS_ADDRESS(entry);
1587
1588 if (entry->type == EXPR_IDENTIFIER) {
1589 struct ident *ident = entry->expr_ident;
1590 /* We special-case the "already right place" case */
1591 if (sym && sym->ident == ident)
1592 continue;
1593 RESET_PTR_LIST(sym);
1594 for (;;) {
1595 if (!sym) {
1596 warn(entry->pos, "unknown named initializer '%s'", show_ident(ident));
1597 return 0;
1598 }
1599 if (sym->ident == ident)
1600 break;
1601 NEXT_PTR_LIST(sym);
1602 }
1603 continue;
1604 }
1605
1606 if (!sym) {
1607 warn(expr->pos, "too many initializers for struct/union");
1608 return 0;
1609 }
1610
1611 evaluate_initializer(sym, p, offset + sym->offset);
1612
1613 NEXT_PTR_LIST(sym);
1614 } END_FOR_EACH_PTR;
1615 FINISH_PTR_LIST(sym);
1616
1617 return 0;
1618 }
1619
1620 /*
1621 * Initializers are kind of like assignments. Except
1622 * they can be a hell of a lot more complex.
1623 */
1624 static int evaluate_initializer(struct symbol *ctype, struct expression **ep, unsigned long offset)
1625 {
1626 struct expression *expr = *ep;
1627
1628 /*
1629 * Simple non-structure/array initializers are the simple
1630 * case, and look (and parse) largely like assignments.
1631 */
1632 if (expr->type != EXPR_INITIALIZER) {
1633 int size = 0, is_string = expr->type == EXPR_STRING;
1634 struct symbol *rtype = evaluate_expression(expr);
1635 if (rtype) {
1636 struct expression *pos;
1637
1638 /*
1639 * Special case:
1640 * char array[] = "string"
1641 * should _not_ degenerate.
1642 */
1643 if (is_string && is_string_type(ctype)) {
1644 struct expression *array_size = ctype->array_size;
1645 if (!array_size)
1646 array_size = ctype->array_size = rtype->array_size;
1647 size = get_expression_value(array_size);
1648 } else {
1649 rtype = degenerate(expr);
1650 size = 1;
1651 }
1652 compatible_assignment_types(expr, ctype, ep, rtype, "initializer");
1653
1654 /*
1655 * Don't bother creating a position expression for
1656 * the simple initializer cases that don't need it.
1657 *
1658 * We need a position if the initializer has a byte
1659 * offset, _or_ if we're initializing a bitfield.
1660 */
1661 if (offset || ctype->fieldwidth) {
1662 pos = alloc_expression(expr->pos, EXPR_POS);
1663 pos->init_offset = offset;
1664 pos->init_sym = ctype;
1665 pos->init_expr = *ep;
1666 pos->ctype = expr->ctype;
1667 *ep = pos;
1668 }
1669 }
1670 return size;
1671 }
1672
1673 expr->ctype = ctype;
1674 if (ctype->type == SYM_NODE)
1675 ctype = ctype->ctype.base_type;
1676
1677 switch (ctype->type) {
1678 case SYM_ARRAY:
1679 case SYM_PTR:
1680 return evaluate_array_initializer(ctype->ctype.base_type, expr, offset);
1681 case SYM_UNION:
1682 return evaluate_struct_or_union_initializer(ctype, expr, 0, offset);
1683 case SYM_STRUCT:
1684 return evaluate_struct_or_union_initializer(ctype, expr, 1, offset);
1685 default:
1686 return evaluate_scalar_initializer(ctype, expr, offset);
1687 }
1688 }
1689
1690 static int get_as(struct symbol *sym)
1691 {
1692 int as;
1693 unsigned long mod;
1694
1695 if (!sym)
1696 return 0;
1697 as = sym->ctype.as;
1698 mod = sym->ctype.modifiers;
1699 if (sym->type == SYM_NODE) {
1700 sym = sym->ctype.base_type;
1701 as |= sym->ctype.as;
1702 mod |= sym->ctype.modifiers;
1703 }
1704 /*
1705 * You can always throw a value away by casting to
1706 * "void" - that's an implicit "force". Note that
1707 * the same is _not_ true of "void *".
1708 */
1709 if (sym == &void_ctype)
1710 return -1;
1711
1712 /*
1713 * At least for now, allow casting to a "unsigned long".
1714 * That's how we do things like pointer arithmetic and
1715 * store pointers to registers.
1716 */
1717 if (sym == &ulong_ctype)
1718 return -1;
1719
1720 if (sym && sym->type == SYM_PTR) {
1721 sym = sym->ctype.base_type;
1722 as |= sym->ctype.as;
1723 mod |= sym->ctype.modifiers;
1724 }
1725 if (mod & MOD_FORCE)
1726 return -1;
1727 return as;
1728 }
1729
1730 static struct symbol *evaluate_cast(struct expression *expr)
1731 {
1732 struct expression *target = expr->cast_expression;
1733 struct symbol *ctype = examine_symbol_type(expr->cast_type);
1734
1735 expr->ctype = ctype;
1736 expr->cast_type = ctype;
1737
1738 /*
1739 * Special case: a cast can be followed by an
1740 * initializer, in which case we need to pass
1741 * the type value down to that initializer rather
1742 * than trying to evaluate it as an expression
1743 *
1744 * A more complex case is when the initializer is
1745 * dereferenced as part of a post-fix expression.
1746 * We need to produce an expression that can be dereferenced.
1747 */
1748 if (target->type == EXPR_INITIALIZER) {
1749 struct symbol *sym = expr->cast_type;
1750 struct expression *addr = alloc_expression(expr->pos, EXPR_SYMBOL);
1751
1752 sym->initializer = expr->cast_expression;
1753 evaluate_symbol(sym);
1754
1755 addr->ctype = &lazy_ptr_ctype; /* Lazy eval */
1756 addr->symbol = sym;
1757
1758 expr->type = EXPR_PREOP;
1759 expr->op = '*';
1760 expr->unop = addr;
1761 expr->ctype = sym;
1762
1763 return sym;
1764 }
1765
1766 evaluate_expression(target);
1767 degenerate(target);
1768
1769 if (!get_as(ctype) && get_as(target->ctype) > 0)
1770 warn(expr->pos, "cast removes address space of expression");
1771
1772 /*
1773 * Casts of constant values are special: they
1774 * can be NULL, and thus need to be simplified
1775 * early.
1776 */
1777 if (target->type == EXPR_VALUE)
1778 cast_value(expr, ctype, target, target->ctype);
1779
1780 return ctype;
1781 }
1782
1783 /*
1784 * Evaluate a call expression with a symbol. This
1785 * should expand inline functions, and evaluate
1786 * builtins.
1787 */
1788 static int evaluate_symbol_call(struct expression *expr)
1789 {
1790 struct expression *fn = expr->fn;
1791 struct symbol *ctype = fn->ctype;
1792
1793 if (fn->type != EXPR_PREOP)
1794 return 0;
1795
1796 if (ctype->op && ctype->op->evaluate)
1797 return ctype->op->evaluate(expr);
1798
1799 if (ctype->ctype.modifiers & MOD_INLINE) {
1800 int ret;
1801 struct symbol *curr = current_fn;
1802 unsigned long context = current_context;
1803 unsigned long mask = current_contextmask;
1804
1805 current_context |= ctype->ctype.context;
1806 current_contextmask |= ctype->ctype.contextmask;
1807 current_fn = ctype->ctype.base_type;
1808 examine_fn_arguments(current_fn);
1809
1810 ret = inline_function(expr, ctype);
1811
1812 /* restore the old function context */
1813 current_fn = curr;
1814 current_context = context;
1815 current_contextmask = mask;
1816 return ret;
1817 }
1818
1819 return 0;
1820 }
1821
1822 static struct symbol *evaluate_call(struct expression *expr)
1823 {
1824 int args, fnargs;
1825 struct symbol *ctype, *sym;
1826 struct expression *fn = expr->fn;
1827 struct expression_list *arglist = expr->args;
1828
1829 if (!evaluate_expression(fn))
1830 return NULL;
1831 sym = ctype = fn->ctype;
1832 if (ctype->type == SYM_NODE)
1833 ctype = ctype->ctype.base_type;
1834 if (ctype->type == SYM_PTR || ctype->type == SYM_ARRAY)
1835 ctype = ctype->ctype.base_type;
1836 if (!evaluate_arguments(sym, ctype, arglist))
1837 return NULL;
1838 if (ctype->type != SYM_FN) {
1839 warn(expr->pos, "not a function %s", show_ident(sym->ident));
1840 return NULL;
1841 }
1842 args = expression_list_size(expr->args);
1843 fnargs = symbol_list_size(ctype->arguments);
1844 if (args < fnargs)
1845 warn(expr->pos, "not enough arguments for function %s", show_ident(sym->ident));
1846 if (args > fnargs && !ctype->variadic)
1847 warn(expr->pos, "too many arguments for function %s", show_ident(sym->ident));
1848 if (sym->type == SYM_NODE) {
1849 if (evaluate_symbol_call(expr))
1850 return expr->ctype;
1851 }
1852 expr->ctype = ctype->ctype.base_type;
1853 return expr->ctype;
1854 }
1855
1856 struct symbol *evaluate_expression(struct expression *expr)
1857 {
1858 if (!expr)
1859 return NULL;
1860 if (expr->ctype)
1861 return expr->ctype;
1862
1863 switch (expr->type) {
1864 case EXPR_VALUE:
1865 case EXPR_FVALUE:
1866 warn(expr->pos, "value expression without a type");
1867 return NULL;
1868 case EXPR_STRING:
1869 return evaluate_string(expr);
1870 case EXPR_SYMBOL:
1871 return evaluate_symbol_expression(expr);
1872 case EXPR_BINOP:
1873 if (!evaluate_expression(expr->left))
1874 return NULL;
1875 if (!evaluate_expression(expr->right))
1876 return NULL;
1877 return evaluate_binop(expr);
1878 case EXPR_LOGICAL:
1879 return evaluate_logical(expr);
1880 case EXPR_COMMA:
1881 if (!evaluate_expression(expr->left))
1882 return NULL;
1883 if (!evaluate_expression(expr->right))
1884 return NULL;
1885 return evaluate_comma(expr);
1886 case EXPR_COMPARE:
1887 if (!evaluate_expression(expr->left))
1888 return NULL;
1889 if (!evaluate_expression(expr->right))
1890 return NULL;
1891 return evaluate_compare(expr);
1892 case EXPR_ASSIGNMENT:
1893 if (!evaluate_expression(expr->left))
1894 return NULL;
1895 if (!evaluate_expression(expr->right))
1896 return NULL;
1897 return evaluate_assignment(expr);
1898 case EXPR_PREOP:
1899 if (!evaluate_expression(expr->unop))
1900 return NULL;
1901 return evaluate_preop(expr);
1902 case EXPR_POSTOP:
1903 if (!evaluate_expression(expr->unop))
1904 return NULL;
1905 return evaluate_postop(expr);
1906 case EXPR_CAST:
1907 return evaluate_cast(expr);
1908 case EXPR_SIZEOF:
1909 return evaluate_sizeof(expr);
1910 case EXPR_ALIGNOF:
1911 return evaluate_alignof(expr);
1912 case EXPR_DEREF:
1913 return evaluate_member_dereference(expr);
1914 case EXPR_CALL:
1915 return evaluate_call(expr);
1916 case EXPR_BITFIELD:
1917 warn(expr->pos, "bitfield generated by parser");
1918 return NULL;
1919 case EXPR_SELECT:
1920 case EXPR_CONDITIONAL:
1921 if (!evaluate_conditional(&expr->conditional))
1922 return NULL;
1923 if (!evaluate_expression(expr->cond_false))
1924 return NULL;
1925 if (expr->cond_true && !evaluate_expression(expr->cond_true))
1926 return NULL;
1927 return evaluate_conditional_expression(expr);
1928 case EXPR_STATEMENT:
1929 expr->ctype = evaluate_statement(expr->statement);
1930 return expr->ctype;
1931
1932 case EXPR_LABEL:
1933 expr->ctype = &ptr_ctype;
1934 return &ptr_ctype;
1935
1936 case EXPR_TYPE:
1937 /* Evaluate the type of the symbol .. */
1938 evaluate_symbol(expr->symbol);
1939 /* .. but the type of the _expression_ is a "type" */
1940 expr->ctype = &type_ctype;
1941 return &type_ctype;
1942
1943 /* These can not exist as stand-alone expressions */
1944 case EXPR_INITIALIZER:
1945 case EXPR_IDENTIFIER:
1946 case EXPR_INDEX:
1947 case EXPR_POS:
1948 warn(expr->pos, "internal front-end error: initializer in expression");
1949 return NULL;
1950 case EXPR_SLICE:
1951 warn(expr->pos, "internal front-end error: SLICE re-evaluated");
1952 return NULL;
1953 }
1954 return NULL;
1955 }
1956
1957 void check_duplicates(struct symbol *sym)
1958 {
1959 struct symbol *next = sym;
1960
1961 while ((next = next->same_symbol) != NULL) {
1962 const char *typediff;
1963 evaluate_symbol(next);
1964 typediff = type_difference(sym, next, 0, 0);
1965 if (typediff) {
1966 warn(sym->pos, "symbol '%s' redeclared with different type (originally declared at %s:%d) - %s",
1967 show_ident(sym->ident),
1968 input_streams[next->pos.stream].name, next->pos.line, typediff);
1969 return;
1970 }
1971 }
1972 }
1973
1974 struct symbol *evaluate_symbol(struct symbol *sym)
1975 {
1976 struct symbol *base_type;
1977
1978 if (!sym)
1979 return sym;
1980
1981 sym = examine_symbol_type(sym);
1982 base_type = sym->ctype.base_type;
1983 if (!base_type)
1984 return NULL;
1985
1986 /* Evaluate the initializers */
1987 if (sym->initializer) {
1988 int count = evaluate_initializer(sym, &sym->initializer, 0);
1989 if (base_type->type == SYM_ARRAY && !base_type->array_size) {
1990 int bit_size = count * base_type->ctype.base_type->bit_size;
1991 base_type->array_size = alloc_const_expression(sym->pos, count);
1992 base_type->bit_size = bit_size;
1993 sym->array_size = base_type->array_size;
1994 sym->bit_size = bit_size;
1995 }
1996 }
1997
1998 /* And finally, evaluate the body of the symbol too */
1999 if (base_type->type == SYM_FN) {
2000 examine_fn_arguments(base_type);
2001 if (base_type->stmt) {
2002 current_fn = base_type;
2003 current_contextmask = sym->ctype.contextmask;
2004 current_context = sym->ctype.context;
2005 evaluate_statement(base_type->stmt);
2006 }
2007 }
2008
2009 return base_type;
2010 }
2011
2012 struct symbol *evaluate_return_expression(struct statement *stmt)
2013 {
2014 struct expression *expr = stmt->expression;
2015 struct symbol *ctype, *fntype;
2016
2017 evaluate_expression(expr);
2018 ctype = degenerate(expr);
2019 fntype = current_fn->ctype.base_type;
2020 if (!fntype || fntype == &void_ctype) {
2021 if (expr && ctype != &void_ctype)
2022 warn(expr->pos, "return expression in %s function", fntype?"void":"typeless");
2023 return NULL;
2024 }
2025
2026 if (!expr) {
2027 warn(stmt->pos, "return with no return value");
2028 return NULL;
2029 }
2030 if (!ctype)
2031 return NULL;
2032 compatible_assignment_types(expr, fntype, &stmt->expression, ctype, "return expression");
2033 return NULL;
2034 }
2035
2036 static void evaluate_if_statement(struct statement *stmt)
2037 {
2038 struct symbol *ctype;
2039
2040 if (!stmt->if_conditional)
2041 return;
2042
2043 ctype = evaluate_conditional(&stmt->if_conditional);
2044 if (!ctype)
2045 return;
2046
2047 evaluate_statement(stmt->if_true);
2048 evaluate_statement(stmt->if_false);
2049 }
2050
2051 struct symbol *evaluate_statement(struct statement *stmt)
2052 {
2053 if (!stmt)
2054 return NULL;
2055
2056 switch (stmt->type) {
2057 case STMT_RETURN:
2058 return evaluate_return_expression(stmt);
2059
2060 case STMT_EXPRESSION:
2061 evaluate_expression(stmt->expression);
2062 return degenerate(stmt->expression);
2063
2064 case STMT_COMPOUND: {
2065 struct statement *s;
2066 struct symbol *type = NULL;
2067 struct symbol *sym;
2068
2069 /* Evaluate each symbol in the compound statement */
2070 FOR_EACH_PTR(stmt->syms, sym) {
2071 evaluate_symbol(sym);
2072 } END_FOR_EACH_PTR;
2073 evaluate_symbol(stmt->ret);
2074
2075 /*
2076 * Then, evaluate each statement, making the type of the
2077 * compound statement be the type of the last statement
2078 */
2079 type = NULL;
2080 FOR_EACH_PTR(stmt->stmts, s) {
2081 type = evaluate_statement(s);
2082 } END_FOR_EACH_PTR;
2083 if (!type)
2084 type = &void_ctype;
2085 return type;
2086 }
2087 case STMT_IF:
2088 evaluate_if_statement(stmt);
2089 return NULL;
2090 case STMT_ITERATOR:
2091 evaluate_conditional(&stmt->iterator_pre_condition);
2092 evaluate_conditional(&stmt->iterator_post_condition);
2093 evaluate_statement(stmt->iterator_pre_statement);
2094 evaluate_statement(stmt->iterator_statement);
2095 evaluate_statement(stmt->iterator_post_statement);
2096 return NULL;
2097 case STMT_SWITCH:
2098 evaluate_expression(stmt->switch_expression);
2099 evaluate_statement(stmt->switch_statement);
2100 return NULL;
2101 case STMT_CASE:
2102 evaluate_expression(stmt->case_expression);
2103 evaluate_expression(stmt->case_to);
2104 evaluate_statement(stmt->case_statement);
2105 return NULL;
2106 case STMT_LABEL:
2107 return evaluate_statement(stmt->label_statement);
2108 case STMT_GOTO:
2109 evaluate_expression(stmt->goto_expression);
2110 return NULL;
2111 case STMT_NONE:
2112 break;
2113 case STMT_ASM:
2114 /* FIXME! Do the asm parameter evaluation! */
2115 break;
2116 }
2117 return NULL;
2118 }
Static analysis for C