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