?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[PATCH] missing builtin - memcmp()
[smatch.git] / evaluate.c
blob272a41970388e709de3e4d0103d02c123fb5332d
1 /*
2 * sparse/evaluate.c
3 *
4 * Copyright (C) 2003 Transmeta Corp.
5 * 2003-2004 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 "allocate.h"
23 #include "parse.h"
24 #include "token.h"
25 #include "symbol.h"
26 #include "target.h"
27 #include "expression.h"
28
29 struct symbol *current_fn;
30
31 static struct symbol *degenerate(struct expression *expr);
32 static struct symbol *evaluate_symbol(struct symbol *sym);
33
34 static struct symbol *evaluate_symbol_expression(struct expression *expr)
35 {
36 struct expression *addr;
37 struct symbol *sym = expr->symbol;
38 struct symbol *base_type;
39
40 if (!sym) {
41 sparse_error(expr->pos, "undefined identifier '%s'", show_ident(expr->symbol_name));
42 return NULL;
43 }
44
45 examine_symbol_type(sym);
46
47 base_type = get_base_type(sym);
48 if (!base_type) {
49 sparse_error(expr->pos, "identifier '%s' has no type", show_ident(expr->symbol_name));
50 return NULL;
51 }
52
53 addr = alloc_expression(expr->pos, EXPR_SYMBOL);
54 addr->symbol = sym;
55 addr->symbol_name = expr->symbol_name;
56 addr->ctype = &lazy_ptr_ctype; /* Lazy evaluation: we need to do a proper job if somebody does &sym */
57 expr->type = EXPR_PREOP;
58 expr->op = '*';
59 expr->unop = addr;
60
61 /* The type of a symbol is the symbol itself! */
62 expr->ctype = sym;
63 return sym;
64 }
65
66 static struct symbol *evaluate_string(struct expression *expr)
67 {
68 struct symbol *sym = alloc_symbol(expr->pos, SYM_NODE);
69 struct symbol *array = alloc_symbol(expr->pos, SYM_ARRAY);
70 struct expression *addr = alloc_expression(expr->pos, EXPR_SYMBOL);
71 struct expression *initstr = alloc_expression(expr->pos, EXPR_STRING);
72 unsigned int length = expr->string->length;
73
74 sym->array_size = alloc_const_expression(expr->pos, length);
75 sym->bit_size = bits_in_char * length;
76 sym->ctype.alignment = 1;
77 sym->ctype.modifiers = MOD_STATIC;
78 sym->ctype.base_type = array;
79 sym->initializer = initstr;
80
81 initstr->ctype = sym;
82 initstr->string = expr->string;
83
84 array->array_size = sym->array_size;
85 array->bit_size = bits_in_char * length;
86 array->ctype.alignment = 1;
87 array->ctype.modifiers = MOD_STATIC;
88 array->ctype.base_type = &char_ctype;
89
90 addr->symbol = sym;
91 addr->ctype = &lazy_ptr_ctype;
92
93 expr->type = EXPR_PREOP;
94 expr->op = '*';
95 expr->unop = addr;
96 expr->ctype = sym;
97 return sym;
98 }
99
100 static inline struct symbol *integer_promotion(struct symbol *type)
101 {
102 struct symbol *orig_type = type;
103 unsigned long mod = type->ctype.modifiers;
104 int width;
105
106 if (type->type == SYM_NODE)
107 type = type->ctype.base_type;
108 if (type->type == SYM_ENUM)
109 type = type->ctype.base_type;
110 width = type->bit_size;
111
112 /*
113 * Bitfields always promote to the base type,
114 * even if the bitfield might be bigger than
115 * an "int".
116 */
117 if (type->type == SYM_BITFIELD) {
118 type = type->ctype.base_type;
119 orig_type = type;
120 }
121 mod = type->ctype.modifiers;
122 if (width < bits_in_int)
123 return &int_ctype;
124
125 /* If char/short has as many bits as int, it still gets "promoted" */
126 if (mod & (MOD_CHAR | MOD_SHORT)) {
127 if (mod & MOD_UNSIGNED)
128 return &uint_ctype;
129 return &int_ctype;
130 }
131 return orig_type;
132 }
133
134 /*
135 * integer part of usual arithmetic conversions:
136 * integer promotions are applied
137 * if left and right are identical, we are done
138 * if signedness is the same, convert one with lower rank
139 * unless unsigned argument has rank lower than signed one, convert the
140 * signed one.
141 * if signed argument is bigger than unsigned one, convert the unsigned.
142 * otherwise, convert signed.
143 *
144 * Leaving aside the integer promotions, that is equivalent to
145 * if identical, don't convert
146 * if left is bigger than right, convert right
147 * if right is bigger than left, convert right
148 * otherwise, if signedness is the same, convert one with lower rank
149 * otherwise convert the signed one.
150 */
151 static struct symbol *bigger_int_type(struct symbol *left, struct symbol *right)
152 {
153 unsigned long lmod, rmod;
154
155 left = integer_promotion(left);
156 right = integer_promotion(right);
157
158 if (left == right)
159 goto left;
160
161 if (left->bit_size > right->bit_size)
162 goto left;
163
164 if (right->bit_size > left->bit_size)
165 goto right;
166
167 lmod = left->ctype.modifiers;
168 rmod = right->ctype.modifiers;
169 if ((lmod ^ rmod) & MOD_UNSIGNED) {
170 if (lmod & MOD_UNSIGNED)
171 goto left;
172 } else if ((lmod & ~rmod) & (MOD_LONG | MOD_LONGLONG))
173 goto left;
174 right:
175 left = right;
176 left:
177 return left;
178 }
179
180 static int same_cast_type(struct symbol *orig, struct symbol *new)
181 {
182 return orig->bit_size == new->bit_size && orig->bit_offset == orig->bit_offset;
183 }
184
185 static struct symbol *base_type(struct symbol *node, unsigned long *modp, unsigned long *asp)
186 {
187 unsigned long mod, as;
188
189 mod = 0; as = 0;
190 while (node) {
191 mod |= node->ctype.modifiers;
192 as |= node->ctype.as;
193 if (node->type == SYM_NODE) {
194 node = node->ctype.base_type;
195 continue;
196 }
197 break;
198 }
199 *modp = mod & ~MOD_IGNORE;
200 *asp = as;
201 return node;
202 }
203
204 static int is_same_type(struct expression *expr, struct symbol *new)
205 {
206 struct symbol *old = expr->ctype;
207 unsigned long oldmod, newmod, oldas, newas;
208
209 old = base_type(old, &oldmod, &oldas);
210 new = base_type(new, &newmod, &newas);
211
212 /* Same base type, same address space? */
213 if (old == new && oldas == newas) {
214 unsigned long difmod;
215
216 /* Check the modifier bits. */
217 difmod = (oldmod ^ newmod) & ~MOD_NOCAST;
218
219 /* Exact same type? */
220 if (!difmod)
221 return 1;
222
223 /*
224 * Not the same type, but differs only in "const".
225 * Don't warn about MOD_NOCAST.
226 */
227 if (difmod == MOD_CONST)
228 return 0;
229 }
230 if ((oldmod | newmod) & MOD_NOCAST) {
231 const char *tofrom = "to/from";
232 if (!(newmod & MOD_NOCAST))
233 tofrom = "from";
234 if (!(oldmod & MOD_NOCAST))
235 tofrom = "to";
236 warning(expr->pos, "implicit cast %s nocast type", tofrom);
237 }
238 return 0;
239 }
240
241 /*
242 * This gets called for implicit casts in assignments and
243 * integer promotion. We often want to try to move the
244 * cast down, because the ops involved may have been
245 * implicitly cast up, and we can get rid of the casts
246 * early.
247 */
248 static struct expression * cast_to(struct expression *old, struct symbol *type)
249 {
250 struct expression *expr;
251
252 if (is_same_type(old, type))
253 return old;
254
255 /*
256 * See if we can simplify the op. Move the cast down.
257 */
258 switch (old->type) {
259 case EXPR_PREOP:
260 if (old->op == '~') {
261 old->ctype = type;
262 old->unop = cast_to(old->unop, type);
263 return old;
264 }
265 break;
266
267 case EXPR_IMPLIED_CAST:
268 if (old->ctype->bit_size >= type->bit_size) {
269 struct expression *orig = old->cast_expression;
270 if (same_cast_type(orig->ctype, type))
271 return orig;
272 if (old->ctype->bit_offset == type->bit_offset) {
273 old->ctype = type;
274 old->cast_type = type;
275 return old;
276 }
277 }
278 break;
279
280 default:
281 /* nothing */;
282 }
283
284 expr = alloc_expression(old->pos, EXPR_IMPLIED_CAST);
285 expr->ctype = type;
286 expr->cast_type = type;
287 expr->cast_expression = old;
288 return expr;
289 }
290
291 static int is_type_type(struct symbol *type)
292 {
293 return (type->ctype.modifiers & MOD_TYPE) != 0;
294 }
295
296 int is_ptr_type(struct symbol *type)
297 {
298 if (type->type == SYM_NODE)
299 type = type->ctype.base_type;
300 return type->type == SYM_PTR || type->type == SYM_ARRAY || type->type == SYM_FN;
301 }
302
303 static inline int is_float_type(struct symbol *type)
304 {
305 if (type->type == SYM_NODE)
306 type = type->ctype.base_type;
307 return type->ctype.base_type == &fp_type;
308 }
309
310 static inline int is_byte_type(struct symbol *type)
311 {
312 return type->bit_size == bits_in_char && type->type != SYM_BITFIELD;
313 }
314
315 static inline int is_string_type(struct symbol *type)
316 {
317 if (type->type == SYM_NODE)
318 type = type->ctype.base_type;
319 return type->type == SYM_ARRAY && is_byte_type(type->ctype.base_type);
320 }
321
322 static struct symbol *bad_expr_type(struct expression *expr)
323 {
324 sparse_error(expr->pos, "incompatible types for operation (%s)", show_special(expr->op));
325 switch (expr->type) {
326 case EXPR_BINOP:
327 case EXPR_COMPARE:
328 info(expr->pos, " left side has type %s", show_typename(expr->left->ctype));
329 info(expr->pos, " right side has type %s", show_typename(expr->right->ctype));
330 break;
331 case EXPR_PREOP:
332 case EXPR_POSTOP:
333 info(expr->pos, " argument has type %s", show_typename(expr->unop->ctype));
334 break;
335 default:
336 break;
337 }
338
339 return NULL;
340 }
341
342 static struct symbol *compatible_float_binop(struct expression **lp, struct expression **rp)
343 {
344 struct expression *left = *lp, *right = *rp;
345 struct symbol *ltype = left->ctype, *rtype = right->ctype;
346
347 if (ltype->type == SYM_NODE)
348 ltype = ltype->ctype.base_type;
349 if (rtype->type == SYM_NODE)
350 rtype = rtype->ctype.base_type;
351 if (is_float_type(ltype)) {
352 if (is_int_type(rtype))
353 goto Left;
354 if (is_float_type(rtype)) {
355 unsigned long lmod = ltype->ctype.modifiers;
356 unsigned long rmod = rtype->ctype.modifiers;
357 lmod &= MOD_LONG | MOD_LONGLONG;
358 rmod &= MOD_LONG | MOD_LONGLONG;
359 if (lmod == rmod)
360 return ltype;
361 if (lmod & ~rmod)
362 goto Left;
363 else
364 goto Right;
365 }
366 return NULL;
367 }
368 if (!is_float_type(rtype) || !is_int_type(ltype))
369 return NULL;
370 Right:
371 *lp = cast_to(left, rtype);
372 return rtype;
373 Left:
374 *rp = cast_to(right, ltype);
375 return ltype;
376 }
377
378 static struct symbol *compatible_integer_binop(struct expression **lp, struct expression **rp)
379 {
380 struct expression *left = *lp, *right = *rp;
381 struct symbol *ltype = left->ctype, *rtype = right->ctype;
382
383 if (ltype->type == SYM_NODE)
384 ltype = ltype->ctype.base_type;
385 if (rtype->type == SYM_NODE)
386 rtype = rtype->ctype.base_type;
387 if (is_int_type(ltype) && is_int_type(rtype)) {
388 struct symbol *ctype = bigger_int_type(ltype, rtype);
389
390 *lp = cast_to(left, ctype);
391 *rp = cast_to(right, ctype);
392 return ctype;
393 }
394 return NULL;
395 }
396
397 static int restricted_value(struct expression *v, struct symbol *type)
398 {
399 if (v->type != EXPR_VALUE)
400 return 1;
401 if (v->value != 0)
402 return 1;
403 return 0;
404 }
405
406 static int restricted_binop(int op, struct symbol *type)
407 {
408 switch (op) {
409 case '&':
410 case '|':
411 case '^':
412 case '?':
413 case '=':
414 case SPECIAL_EQUAL:
415 case SPECIAL_NOTEQUAL:
416 case SPECIAL_AND_ASSIGN:
417 case SPECIAL_OR_ASSIGN:
418 case SPECIAL_XOR_ASSIGN:
419 return 0;
420 default:
421 return 1;
422 }
423 }
424
425 static int restricted_unop(int op, struct symbol *type)
426 {
427 if (op == '~' && type->bit_size >= bits_in_int)
428 return 0;
429 if (op == '+')
430 return 0;
431 return 1;
432 }
433
434 static struct symbol *compatible_restricted_binop(int op, struct expression **lp, struct expression **rp)
435 {
436 struct expression *left = *lp, *right = *rp;
437 struct symbol *ltype = left->ctype, *rtype = right->ctype;
438 struct symbol *type = NULL;
439
440 if (ltype->type == SYM_NODE)
441 ltype = ltype->ctype.base_type;
442 if (ltype->type == SYM_ENUM)
443 ltype = ltype->ctype.base_type;
444 if (rtype->type == SYM_NODE)
445 rtype = rtype->ctype.base_type;
446 if (rtype->type == SYM_ENUM)
447 rtype = rtype->ctype.base_type;
448 if (is_restricted_type(ltype)) {
449 if (is_restricted_type(rtype)) {
450 if (ltype == rtype)
451 type = ltype;
452 } else {
453 if (!restricted_value(right, ltype))
454 type = ltype;
455 }
456 } else if (is_restricted_type(rtype)) {
457 if (!restricted_value(left, rtype))
458 type = rtype;
459 }
460 if (!type)
461 return NULL;
462 if (restricted_binop(op, type))
463 return NULL;
464 return type;
465 }
466
467 static struct symbol *evaluate_arith(struct expression *expr, int float_ok)
468 {
469 struct symbol *ctype = compatible_integer_binop(&expr->left, &expr->right);
470 if (!ctype && float_ok)
471 ctype = compatible_float_binop(&expr->left, &expr->right);
472 if (!ctype)
473 ctype = compatible_restricted_binop(expr->op, &expr->left, &expr->right);
474 if (ctype) {
475 expr->ctype = ctype;
476 return ctype;
477 }
478 return bad_expr_type(expr);
479 }
480
481 static inline int lvalue_expression(struct expression *expr)
482 {
483 return expr->type == EXPR_PREOP && expr->op == '*';
484 }
485
486 static int ptr_object_size(struct symbol *ptr_type)
487 {
488 if (ptr_type->type == SYM_NODE)
489 ptr_type = ptr_type->ctype.base_type;
490 if (ptr_type->type == SYM_PTR)
491 ptr_type = get_base_type(ptr_type);
492 return ptr_type->bit_size;
493 }
494
495 static struct symbol *evaluate_ptr_add(struct expression *expr, struct symbol *ctype, struct expression **ip)
496 {
497 struct expression *i = *ip;
498 struct symbol *ptr_type = ctype;
499 int bit_size;
500
501 if (ptr_type->type == SYM_NODE)
502 ptr_type = ptr_type->ctype.base_type;
503
504 if (!is_int_type(i->ctype))
505 return bad_expr_type(expr);
506
507 examine_symbol_type(ctype);
508
509 if (!ctype->ctype.base_type) {
510 sparse_error(expr->pos, "missing type information");
511 return NULL;
512 }
513
514 /* Get the size of whatever the pointer points to */
515 bit_size = ptr_object_size(ctype);
516
517 if (bit_size > bits_in_char) {
518 int multiply = bit_size >> 3;
519 struct expression *val = alloc_expression(expr->pos, EXPR_VALUE);
520
521 if (i->type == EXPR_VALUE) {
522 val->value = i->value * multiply;
523 val->ctype = size_t_ctype;
524 *ip = val;
525 } else {
526 struct expression *mul = alloc_expression(expr->pos, EXPR_BINOP);
527
528 val->ctype = size_t_ctype;
529 val->value = bit_size >> 3;
530
531 mul->op = '*';
532 mul->ctype = size_t_ctype;
533 mul->left = i;
534 mul->right = val;
535
536 *ip = mul;
537 }
538 }
539
540 expr->ctype = ctype;
541 return ctype;
542 }
543
544 static struct symbol *evaluate_add(struct expression *expr)
545 {
546 struct expression *left = expr->left, *right = expr->right;
547 struct symbol *ltype = left->ctype, *rtype = right->ctype;
548
549 if (is_ptr_type(ltype))
550 return evaluate_ptr_add(expr, degenerate(left), &expr->right);
551
552 if (is_ptr_type(rtype))
553 return evaluate_ptr_add(expr, degenerate(right), &expr->left);
554
555 return evaluate_arith(expr, 1);
556 }
557
558 const char * type_difference(struct symbol *target, struct symbol *source,
559 unsigned long target_mod_ignore, unsigned long source_mod_ignore)
560 {
561 for (;;) {
562 unsigned long mod1, mod2, diff;
563 unsigned long as1, as2;
564 int type1, type2;
565 struct symbol *base1, *base2;
566
567 if (target == source)
568 break;
569 if (!target || !source)
570 return "different types";
571 /*
572 * Peel of per-node information.
573 * FIXME! Check alignment and context too here!
574 */
575 mod1 = target->ctype.modifiers;
576 as1 = target->ctype.as;
577 mod2 = source->ctype.modifiers;
578 as2 = source->ctype.as;
579 if (target->type == SYM_NODE) {
580 target = target->ctype.base_type;
581 if (!target)
582 return "bad types";
583 if (target->type == SYM_PTR) {
584 mod1 = 0;
585 as1 = 0;
586 }
587 mod1 |= target->ctype.modifiers;
588 as1 |= target->ctype.as;
589 }
590 if (source->type == SYM_NODE) {
591 source = source->ctype.base_type;
592 if (!source)
593 return "bad types";
594 if (source->type == SYM_PTR) {
595 mod2 = 0;
596 as2 = 0;
597 }
598 mod2 |= source->ctype.modifiers;
599 as2 |= source->ctype.as;
600 }
601 if (target->type == SYM_ENUM) {
602 target = target->ctype.base_type;
603 if (!target)
604 return "bad types";
605 }
606 if (source->type == SYM_ENUM) {
607 source = source->ctype.base_type;
608 if (!source)
609 return "bad types";
610 }
611
612 if (target == source)
613 break;
614 if (!target || !source)
615 return "different types";
616
617 type1 = target->type;
618 base1 = target->ctype.base_type;
619
620 type2 = source->type;
621 base2 = source->ctype.base_type;
622
623 /*
624 * Pointers to functions compare as the function itself
625 */
626 if (type1 == SYM_PTR && base1) {
627 base1 = examine_symbol_type(base1);
628 switch (base1->type) {
629 case SYM_FN:
630 type1 = SYM_FN;
631 target = base1;
632 base1 = base1->ctype.base_type;
633 default:
634 /* nothing */;
635 }
636 }
637 if (type2 == SYM_PTR && base2) {
638 base2 = examine_symbol_type(base2);
639 switch (base2->type) {
640 case SYM_FN:
641 type2 = SYM_FN;
642 source = base2;
643 base2 = base2->ctype.base_type;
644 default:
645 /* nothing */;
646 }
647 }
648
649 /* Arrays degenerate to pointers for type comparisons */
650 type1 = (type1 == SYM_ARRAY) ? SYM_PTR : type1;
651 type2 = (type2 == SYM_ARRAY) ? SYM_PTR : type2;
652
653 if (type1 != type2 || type1 == SYM_RESTRICT)
654 return "different base types";
655
656 /* Must be same address space to be comparable */
657 if (as1 != as2)
658 return "different address spaces";
659
660 /* Ignore differences in storage types or addressability */
661 diff = (mod1 ^ mod2) & ~MOD_IGNORE;
662 diff &= (mod1 & ~target_mod_ignore) | (mod2 & ~source_mod_ignore);
663 if (diff) {
664 if (diff & MOD_SIZE)
665 return "different type sizes";
666 if (diff & ~MOD_SIGNEDNESS)
667 return "different modifiers";
668
669 /* Differs in signedness only.. */
670 if (Wtypesign) {
671 /*
672 * Warn if both are explicitly signed ("unsigned" is obvously
673 * always explicit, and since we know one of them has to be
674 * unsigned, we check if the signed one was explicit).
675 */
676 if ((mod1 | mod2) & MOD_EXPLICITLY_SIGNED)
677 return "different explicit signedness";
678
679 /*
680 * "char" matches both "unsigned char" and "signed char",
681 * so if the explicit test didn't trigger, then we should
682 * not warn about a char.
683 */
684 if (!(mod1 & MOD_CHAR))
685 return "different signedness";
686 }
687 }
688
689 if (type1 == SYM_FN) {
690 int i;
691 struct symbol *arg1, *arg2;
692 if (base1->variadic != base2->variadic)
693 return "incompatible variadic arguments";
694 PREPARE_PTR_LIST(target->arguments, arg1);
695 PREPARE_PTR_LIST(source->arguments, arg2);
696 i = 1;
697 for (;;) {
698 const char *diff;
699 diff = type_difference(arg1, arg2, 0, 0);
700 if (diff) {
701 static char argdiff[80];
702 sprintf(argdiff, "incompatible argument %d (%s)", i, diff);
703 return argdiff;
704 }
705 if (!arg1)
706 break;
707 NEXT_PTR_LIST(arg1);
708 NEXT_PTR_LIST(arg2);
709 i++;
710 }
711 FINISH_PTR_LIST(arg2);
712 FINISH_PTR_LIST(arg1);
713 }
714
715 target = base1;
716 source = base2;
717 }
718 return NULL;
719 }
720
721 static int is_null_ptr(struct expression *expr)
722 {
723 if (expr->type != EXPR_VALUE || expr->value)
724 return 0;
725 if (!is_ptr_type(expr->ctype))
726 warning(expr->pos, "Using plain integer as NULL pointer");
727 return 1;
728 }
729
730 static struct symbol *common_ptr_type(struct expression *l, struct expression *r)
731 {
732 /* NULL expression? Just return the type of the "other side" */
733 if (is_null_ptr(r))
734 return l->ctype;
735 if (is_null_ptr(l))
736 return r->ctype;
737 return NULL;
738 }
739
740 /*
741 * Ignore differences in "volatile" and "const"ness when
742 * subtracting pointers
743 */
744 #define MOD_IGN (MOD_VOLATILE | MOD_CONST)
745
746 static struct symbol *evaluate_ptr_sub(struct expression *expr, struct expression *l, struct expression **rp)
747 {
748 const char *typediff;
749 struct symbol *ctype;
750 struct symbol *ltype, *rtype;
751 struct expression *r = *rp;
752
753 ltype = degenerate(l);
754 rtype = degenerate(r);
755
756 /*
757 * If it is an integer subtract: the ptr add case will do the
758 * right thing.
759 */
760 if (!is_ptr_type(rtype))
761 return evaluate_ptr_add(expr, degenerate(l), rp);
762
763 ctype = ltype;
764 typediff = type_difference(ltype, rtype, ~MOD_SIZE, ~MOD_SIZE);
765 if (typediff) {
766 ctype = common_ptr_type(l, r);
767 if (!ctype) {
768 sparse_error(expr->pos, "subtraction of different types can't work (%s)", typediff);
769 return NULL;
770 }
771 }
772 examine_symbol_type(ctype);
773
774 /* Figure out the base type we point to */
775 if (ctype->type == SYM_NODE)
776 ctype = ctype->ctype.base_type;
777 if (ctype->type != SYM_PTR && ctype->type != SYM_ARRAY) {
778 sparse_error(expr->pos, "subtraction of functions? Share your drugs");
779 return NULL;
780 }
781 ctype = get_base_type(ctype);
782
783 expr->ctype = ssize_t_ctype;
784 if (ctype->bit_size > bits_in_char) {
785 struct expression *sub = alloc_expression(expr->pos, EXPR_BINOP);
786 struct expression *div = expr;
787 struct expression *val = alloc_expression(expr->pos, EXPR_VALUE);
788 unsigned long value = ctype->bit_size >> 3;
789
790 val->ctype = size_t_ctype;
791 val->value = value;
792
793 if (value & (value-1)) {
794 if (Wptr_subtraction_blows)
795 warning(expr->pos, "potentially expensive pointer subtraction");
796 }
797
798 sub->op = '-';
799 sub->ctype = ssize_t_ctype;
800 sub->left = l;
801 sub->right = r;
802
803 div->op = '/';
804 div->left = sub;
805 div->right = val;
806 }
807
808 return ssize_t_ctype;
809 }
810
811 static struct symbol *evaluate_sub(struct expression *expr)
812 {
813 struct expression *left = expr->left;
814 struct symbol *ltype = left->ctype;
815
816 if (is_ptr_type(ltype))
817 return evaluate_ptr_sub(expr, left, &expr->right);
818
819 return evaluate_arith(expr, 1);
820 }
821
822 #define is_safe_type(type) ((type)->ctype.modifiers & MOD_SAFE)
823
824 static struct symbol *evaluate_conditional(struct expression *expr, int iterator)
825 {
826 struct symbol *ctype;
827
828 if (!expr)
829 return NULL;
830
831 if (!iterator && expr->type == EXPR_ASSIGNMENT && expr->op == '=')
832 warning(expr->pos, "assignment expression in conditional");
833
834 ctype = evaluate_expression(expr);
835 if (ctype) {
836 if (is_safe_type(ctype))
837 warning(expr->pos, "testing a 'safe expression'");
838 }
839
840 return ctype;
841 }
842
843 static struct symbol *evaluate_logical(struct expression *expr)
844 {
845 if (!evaluate_conditional(expr->left, 0))
846 return NULL;
847 if (!evaluate_conditional(expr->right, 0))
848 return NULL;
849
850 expr->ctype = &bool_ctype;
851 return &bool_ctype;
852 }
853
854 static struct symbol *evaluate_shift(struct expression *expr)
855 {
856 struct expression *left = expr->left, *right = expr->right;
857 struct symbol *ltype = left->ctype, *rtype = right->ctype;
858
859 if (ltype->type == SYM_NODE)
860 ltype = ltype->ctype.base_type;
861 if (rtype->type == SYM_NODE)
862 rtype = rtype->ctype.base_type;
863 if (is_int_type(ltype) && is_int_type(rtype)) {
864 struct symbol *ctype = integer_promotion(ltype);
865 expr->left = cast_to(expr->left, ctype);
866 expr->ctype = ctype;
867 ctype = integer_promotion(rtype);
868 expr->right = cast_to(expr->right, ctype);
869 return expr->ctype;
870 }
871 return bad_expr_type(expr);
872 }
873
874 static struct symbol *evaluate_binop(struct expression *expr)
875 {
876 switch (expr->op) {
877 // addition can take ptr+int, fp and int
878 case '+':
879 return evaluate_add(expr);
880
881 // subtraction can take ptr-ptr, fp and int
882 case '-':
883 return evaluate_sub(expr);
884
885 // Arithmetic operations can take fp and int
886 case '*': case '/':
887 return evaluate_arith(expr, 1);
888
889 // shifts do integer promotions, but that's it.
890 case SPECIAL_LEFTSHIFT: case SPECIAL_RIGHTSHIFT:
891 return evaluate_shift(expr);
892
893 // The rest are integer operations
894 // '%', '&', '^', '|'
895 default:
896 return evaluate_arith(expr, 0);
897 }
898 }
899
900 static struct symbol *evaluate_comma(struct expression *expr)
901 {
902 expr->ctype = expr->right->ctype;
903 return expr->ctype;
904 }
905
906 static int modify_for_unsigned(int op)
907 {
908 if (op == '<')
909 op = SPECIAL_UNSIGNED_LT;
910 else if (op == '>')
911 op = SPECIAL_UNSIGNED_GT;
912 else if (op == SPECIAL_LTE)
913 op = SPECIAL_UNSIGNED_LTE;
914 else if (op == SPECIAL_GTE)
915 op = SPECIAL_UNSIGNED_GTE;
916 return op;
917 }
918
919 static struct symbol *evaluate_compare(struct expression *expr)
920 {
921 struct expression *left = expr->left, *right = expr->right;
922 struct symbol *ltype = left->ctype, *rtype = right->ctype;
923 struct symbol *ctype;
924
925 /* Type types? */
926 if (is_type_type(ltype) && is_type_type(rtype))
927 goto OK;
928
929 if (is_safe_type(ltype) || is_safe_type(rtype))
930 warning(expr->pos, "testing a 'safe expression'");
931
932 /* Pointer types? */
933 if (is_ptr_type(ltype) || is_ptr_type(rtype)) {
934 // FIXME! Check the types for compatibility
935 expr->op = modify_for_unsigned(expr->op);
936 goto OK;
937 }
938
939 ctype = compatible_integer_binop(&expr->left, &expr->right);
940 if (ctype) {
941 if (ctype->ctype.modifiers & MOD_UNSIGNED)
942 expr->op = modify_for_unsigned(expr->op);
943 goto OK;
944 }
945
946 ctype = compatible_float_binop(&expr->left, &expr->right);
947 if (ctype)
948 goto OK;
949
950 ctype = compatible_restricted_binop(expr->op, &expr->left, &expr->right);
951 if (ctype) {
952 if (ctype->ctype.modifiers & MOD_UNSIGNED)
953 expr->op = modify_for_unsigned(expr->op);
954 goto OK;
955 }
956
957 bad_expr_type(expr);
958
959 OK:
960 expr->ctype = &bool_ctype;
961 return &bool_ctype;
962 }
963
964 /*
965 * FIXME!! This should do casts, array degeneration etc..
966 */
967 static struct symbol *compatible_ptr_type(struct expression *left, struct expression *right)
968 {
969 struct symbol *ltype = left->ctype, *rtype = right->ctype;
970
971 if (ltype->type == SYM_NODE)
972 ltype = ltype->ctype.base_type;
973
974 if (rtype->type == SYM_NODE)
975 rtype = rtype->ctype.base_type;
976
977 if (ltype->type == SYM_PTR) {
978 if (is_null_ptr(right) || rtype->ctype.base_type == &void_ctype)
979 return ltype;
980 }
981
982 if (rtype->type == SYM_PTR) {
983 if (is_null_ptr(left) || ltype->ctype.base_type == &void_ctype)
984 return rtype;
985 }
986 return NULL;
987 }
988
989 /*
990 * NOTE! The degenerate case of "x ? : y", where we don't
991 * have a true case, this will possibly promote "x" to the
992 * same type as "y", and thus _change_ the conditional
993 * test in the expression. But since promotion is "safe"
994 * for testing, that's ok.
995 */
996 static struct symbol *evaluate_conditional_expression(struct expression *expr)
997 {
998 struct expression **true;
999 struct symbol *ctype, *ltype, *rtype;
1000 const char * typediff;
1001
1002 if (!evaluate_conditional(expr->conditional, 0))
1003 return NULL;
1004 if (!evaluate_expression(expr->cond_false))
1005 return NULL;
1006
1007 ctype = degenerate(expr->conditional);
1008 rtype = degenerate(expr->cond_false);
1009
1010 true = &expr->conditional;
1011 ltype = ctype;
1012 if (expr->cond_true) {
1013 if (!evaluate_expression(expr->cond_true))
1014 return NULL;
1015 ltype = degenerate(expr->cond_true);
1016 true = &expr->cond_true;
1017 }
1018
1019 ctype = compatible_integer_binop(true, &expr->cond_false);
1020 if (ctype)
1021 goto out;
1022 ctype = compatible_ptr_type(*true, expr->cond_false);
1023 if (ctype)
1024 goto out;
1025 ctype = compatible_float_binop(true, &expr->cond_false);
1026 if (ctype)
1027 goto out;
1028 ctype = compatible_restricted_binop('?', true, &expr->cond_false);
1029 if (ctype)
1030 goto out;
1031 ctype = ltype;
1032 typediff = type_difference(ltype, rtype, MOD_IGN, MOD_IGN);
1033 if (!typediff)
1034 goto out;
1035 sparse_error(expr->pos, "incompatible types in conditional expression (%s)", typediff);
1036 return NULL;
1037
1038 out:
1039 expr->ctype = ctype;
1040 return ctype;
1041 }
1042
1043 /* FP assignments can not do modulo or bit operations */
1044 static int compatible_float_op(int op)
1045 {
1046 return op == '=' ||
1047 op == SPECIAL_ADD_ASSIGN ||
1048 op == SPECIAL_SUB_ASSIGN ||
1049 op == SPECIAL_MUL_ASSIGN ||
1050 op == SPECIAL_DIV_ASSIGN;
1051 }
1052
1053 static int compatible_assignment_types(struct expression *expr, struct symbol *target,
1054 struct expression **rp, struct symbol *source, const char *where, int op)
1055 {
1056 const char *typediff;
1057 struct symbol *t;
1058 int target_as;
1059
1060 if (is_int_type(target)) {
1061 if (is_int_type(source))
1062 goto Cast;
1063 if (is_float_type(source))
1064 goto Cast;
1065 } else if (is_float_type(target)) {
1066 if (!compatible_float_op(op)) {
1067 sparse_error(expr->pos, "invalid assignment");
1068 return 0;
1069 }
1070 if (is_int_type(source))
1071 goto Cast;
1072 if (is_float_type(source))
1073 goto Cast;
1074 } else if (is_restricted_type(target)) {
1075 if (restricted_binop(op, target)) {
1076 sparse_error(expr->pos, "bad restricted assignment");
1077 return 0;
1078 }
1079 if (!restricted_value(*rp, target))
1080 return 1;
1081 } else if (is_ptr_type(target)) {
1082 if (op == SPECIAL_ADD_ASSIGN || op == SPECIAL_SUB_ASSIGN) {
1083 evaluate_ptr_add(expr, target, rp);
1084 return 1;
1085 }
1086 if (op != '=') {
1087 sparse_error(expr->pos, "invalid pointer assignment");
1088 return 0;
1089 }
1090 } else if (op != '=') {
1091 sparse_error(expr->pos, "invalid assignment");
1092 return 0;
1093 }
1094
1095 /* It's ok if the target is more volatile or const than the source */
1096 typediff = type_difference(target, source, MOD_VOLATILE | MOD_CONST, 0);
1097 if (!typediff)
1098 return 1;
1099
1100 /* Pointer destination? */
1101 t = target;
1102 target_as = t->ctype.as;
1103 if (t->type == SYM_NODE) {
1104 t = t->ctype.base_type;
1105 target_as |= t->ctype.as;
1106 }
1107 if (t->type == SYM_PTR || t->type == SYM_FN || t->type == SYM_ARRAY) {
1108 struct expression *right = *rp;
1109 struct symbol *s = source;
1110 int source_as;
1111
1112 // NULL pointer is always ok
1113 if (is_null_ptr(right))
1114 goto Cast;
1115
1116 /* "void *" matches anything as long as the address space is ok */
1117 source_as = s->ctype.as;
1118 if (s->type == SYM_NODE) {
1119 s = s->ctype.base_type;
1120 source_as |= s->ctype.as;
1121 }
1122 if (source_as == target_as && (s->type == SYM_PTR || s->type == SYM_ARRAY)) {
1123 s = get_base_type(s);
1124 t = get_base_type(t);
1125 if (s == &void_ctype || t == &void_ctype)
1126 goto Cast;
1127 }
1128 }
1129
1130 warning(expr->pos, "incorrect type in %s (%s)", where, typediff);
1131 info(expr->pos, " expected %s", show_typename(target));
1132 info(expr->pos, " got %s", show_typename(source));
1133 *rp = cast_to(*rp, target);
1134 return 0;
1135 Cast:
1136 *rp = cast_to(*rp, target);
1137 return 1;
1138 }
1139
1140 static void mark_assigned(struct expression *expr)
1141 {
1142 struct symbol *sym;
1143
1144 if (!expr)
1145 return;
1146 switch (expr->type) {
1147 case EXPR_SYMBOL:
1148 sym = expr->symbol;
1149 if (!sym)
1150 return;
1151 if (sym->type != SYM_NODE)
1152 return;
1153 sym->ctype.modifiers |= MOD_ASSIGNED;
1154 return;
1155
1156 case EXPR_BINOP:
1157 mark_assigned(expr->left);
1158 mark_assigned(expr->right);
1159 return;
1160 case EXPR_CAST:
1161 mark_assigned(expr->cast_expression);
1162 return;
1163 case EXPR_SLICE:
1164 mark_assigned(expr->base);
1165 return;
1166 default:
1167 /* Hmm? */
1168 return;
1169 }
1170 }
1171
1172 static void evaluate_assign_to(struct expression *left, struct symbol *type)
1173 {
1174 if (type->ctype.modifiers & MOD_CONST)
1175 sparse_error(left->pos, "assignment to const expression");
1176
1177 /* We know left is an lvalue, so it's a "preop-*" */
1178 mark_assigned(left->unop);
1179 }
1180
1181 static struct symbol *evaluate_assignment(struct expression *expr)
1182 {
1183 struct expression *left = expr->left, *right = expr->right;
1184 struct expression *where = expr;
1185 struct symbol *ltype, *rtype;
1186
1187 if (!lvalue_expression(left)) {
1188 sparse_error(expr->pos, "not an lvalue");
1189 return NULL;
1190 }
1191
1192 ltype = left->ctype;
1193
1194 rtype = degenerate(right);
1195
1196 if (!compatible_assignment_types(where, ltype, &where->right, rtype, "assignment", expr->op))
1197 return NULL;
1198
1199 evaluate_assign_to(left, ltype);
1200
1201 expr->ctype = ltype;
1202 return ltype;
1203 }
1204
1205 static void examine_fn_arguments(struct symbol *fn)
1206 {
1207 struct symbol *s;
1208
1209 FOR_EACH_PTR(fn->arguments, s) {
1210 struct symbol *arg = evaluate_symbol(s);
1211 /* Array/function arguments silently degenerate into pointers */
1212 if (arg) {
1213 struct symbol *ptr;
1214 switch(arg->type) {
1215 case SYM_ARRAY:
1216 case SYM_FN:
1217 ptr = alloc_symbol(s->pos, SYM_PTR);
1218 if (arg->type == SYM_ARRAY)
1219 ptr->ctype = arg->ctype;
1220 else
1221 ptr->ctype.base_type = arg;
1222 ptr->ctype.as |= s->ctype.as;
1223 ptr->ctype.modifiers |= s->ctype.modifiers;
1224
1225 s->ctype.base_type = ptr;
1226 s->ctype.as = 0;
1227 s->ctype.modifiers = 0;
1228 s->bit_size = 0;
1229 s->examined = 0;
1230 examine_symbol_type(s);
1231 break;
1232 default:
1233 /* nothing */
1234 break;
1235 }
1236 }
1237 } END_FOR_EACH_PTR(s);
1238 }
1239
1240 static struct symbol *convert_to_as_mod(struct symbol *sym, int as, int mod)
1241 {
1242 /* Take the modifiers of the pointer, and apply them to the member */
1243 mod |= sym->ctype.modifiers;
1244 if (sym->ctype.as != as || sym->ctype.modifiers != mod) {
1245 struct symbol *newsym = alloc_symbol(sym->pos, SYM_NODE);
1246 *newsym = *sym;
1247 newsym->ctype.as = as;
1248 newsym->ctype.modifiers = mod;
1249 sym = newsym;
1250 }
1251 return sym;
1252 }
1253
1254 #define MOD_PTRINHERIT (MOD_VOLATILE | MOD_CONST | MOD_STORAGE)
1255
1256 static struct symbol *create_pointer(struct expression *expr, struct symbol *sym, int degenerate)
1257 {
1258 struct symbol *node = alloc_symbol(expr->pos, SYM_NODE);
1259 struct symbol *ptr = alloc_symbol(expr->pos, SYM_PTR);
1260
1261 node->ctype.base_type = ptr;
1262 ptr->bit_size = bits_in_pointer;
1263 ptr->ctype.alignment = pointer_alignment;
1264
1265 node->bit_size = bits_in_pointer;
1266 node->ctype.alignment = pointer_alignment;
1267
1268 access_symbol(sym);
1269 if (sym->ctype.modifiers & MOD_REGISTER) {
1270 warning(expr->pos, "taking address of 'register' variable '%s'", show_ident(sym->ident));
1271 sym->ctype.modifiers &= ~MOD_REGISTER;
1272 }
1273 if (sym->type == SYM_NODE) {
1274 ptr->ctype.as |= sym->ctype.as;
1275 ptr->ctype.modifiers |= sym->ctype.modifiers & MOD_PTRINHERIT;
1276 sym = sym->ctype.base_type;
1277 }
1278 if (degenerate && sym->type == SYM_ARRAY) {
1279 ptr->ctype.as |= sym->ctype.as;
1280 ptr->ctype.modifiers |= sym->ctype.modifiers & MOD_PTRINHERIT;
1281 sym = sym->ctype.base_type;
1282 }
1283 ptr->ctype.base_type = sym;
1284
1285 return node;
1286 }
1287
1288 /* Arrays degenerate into pointers on pointer arithmetic */
1289 static struct symbol *degenerate(struct expression *expr)
1290 {
1291 struct symbol *ctype, *base;
1292
1293 if (!expr)
1294 return NULL;
1295 ctype = expr->ctype;
1296 if (!ctype)
1297 return NULL;
1298 base = examine_symbol_type(ctype);
1299 if (ctype->type == SYM_NODE)
1300 base = ctype->ctype.base_type;
1301 /*
1302 * Arrays degenerate into pointers to the entries, while
1303 * functions degenerate into pointers to themselves.
1304 * If array was part of non-lvalue compound, we create a copy
1305 * of that compound first and then act as if we were dealing with
1306 * the corresponding field in there.
1307 */
1308 switch (base->type) {
1309 case SYM_ARRAY:
1310 if (expr->type == EXPR_SLICE) {
1311 struct symbol *a = alloc_symbol(expr->pos, SYM_NODE);
1312 struct expression *e0, *e1, *e2, *e3, *e4;
1313
1314 a->ctype.base_type = expr->base->ctype;
1315 a->bit_size = expr->base->ctype->bit_size;
1316 a->array_size = expr->base->ctype->array_size;
1317
1318 e0 = alloc_expression(expr->pos, EXPR_SYMBOL);
1319 e0->symbol = a;
1320 e0->ctype = &lazy_ptr_ctype;
1321
1322 e1 = alloc_expression(expr->pos, EXPR_PREOP);
1323 e1->unop = e0;
1324 e1->op = '*';
1325 e1->ctype = expr->base->ctype; /* XXX */
1326
1327 e2 = alloc_expression(expr->pos, EXPR_ASSIGNMENT);
1328 e2->left = e1;
1329 e2->right = expr->base;
1330 e2->op = '=';
1331 e2->ctype = expr->base->ctype;
1332
1333 if (expr->r_bitpos) {
1334 e3 = alloc_expression(expr->pos, EXPR_BINOP);
1335 e3->op = '+';
1336 e3->left = e0;
1337 e3->right = alloc_const_expression(expr->pos,
1338 expr->r_bitpos >> 3);
1339 e3->ctype = &lazy_ptr_ctype;
1340 } else {
1341 e3 = e0;
1342 }
1343
1344 e4 = alloc_expression(expr->pos, EXPR_COMMA);
1345 e4->left = e2;
1346 e4->right = e3;
1347 e4->ctype = &lazy_ptr_ctype;
1348
1349 expr->unop = e4;
1350 expr->type = EXPR_PREOP;
1351 expr->op = '*';
1352 }
1353 case SYM_FN:
1354 if (expr->op != '*' || expr->type != EXPR_PREOP) {
1355 sparse_error(expr->pos, "strange non-value function or array");
1356 return &bad_ctype;
1357 }
1358 *expr = *expr->unop;
1359 ctype = create_pointer(expr, ctype, 1);
1360 expr->ctype = ctype;
1361 default:
1362 /* nothing */;
1363 }
1364 return ctype;
1365 }
1366
1367 static struct symbol *evaluate_addressof(struct expression *expr)
1368 {
1369 struct expression *op = expr->unop;
1370 struct symbol *ctype;
1371
1372 if (op->op != '*' || op->type != EXPR_PREOP) {
1373 sparse_error(expr->pos, "not addressable");
1374 return NULL;
1375 }
1376 ctype = op->ctype;
1377 *expr = *op->unop;
1378
1379 if (expr->type == EXPR_SYMBOL) {
1380 struct symbol *sym = expr->symbol;
1381 sym->ctype.modifiers |= MOD_ADDRESSABLE;
1382 }
1383
1384 /*
1385 * symbol expression evaluation is lazy about the type
1386 * of the sub-expression, so we may have to generate
1387 * the type here if so..
1388 */
1389 if (expr->ctype == &lazy_ptr_ctype) {
1390 ctype = create_pointer(expr, ctype, 0);
1391 expr->ctype = ctype;
1392 }
1393 return expr->ctype;
1394 }
1395
1396
1397 static struct symbol *evaluate_dereference(struct expression *expr)
1398 {
1399 struct expression *op = expr->unop;
1400 struct symbol *ctype = op->ctype, *node, *target;
1401
1402 /* Simplify: *&(expr) => (expr) */
1403 if (op->type == EXPR_PREOP && op->op == '&') {
1404 *expr = *op->unop;
1405 return expr->ctype;
1406 }
1407
1408 /* Dereferencing a node drops all the node information. */
1409 if (ctype->type == SYM_NODE)
1410 ctype = ctype->ctype.base_type;
1411
1412 node = alloc_symbol(expr->pos, SYM_NODE);
1413 target = ctype->ctype.base_type;
1414
1415 switch (ctype->type) {
1416 default:
1417 sparse_error(expr->pos, "cannot derefence this type");
1418 return NULL;
1419 case SYM_PTR:
1420 node->ctype.modifiers = target->ctype.modifiers & MOD_SPECIFIER;
1421 merge_type(node, ctype);
1422 break;
1423
1424 case SYM_ARRAY:
1425 if (!lvalue_expression(op)) {
1426 sparse_error(op->pos, "non-lvalue array??");
1427 return NULL;
1428 }
1429
1430 /* Do the implied "addressof" on the array */
1431 *op = *op->unop;
1432
1433 /*
1434 * When an array is dereferenced, we need to pick
1435 * up the attributes of the original node too..
1436 */
1437 merge_type(node, op->ctype);
1438 merge_type(node, ctype);
1439 break;
1440 }
1441
1442 node->bit_size = target->bit_size;
1443 node->array_size = target->array_size;
1444
1445 expr->ctype = node;
1446 return node;
1447 }
1448
1449 /*
1450 * Unary post-ops: x++ and x--
1451 */
1452 static struct symbol *evaluate_postop(struct expression *expr)
1453 {
1454 struct expression *op = expr->unop;
1455 struct symbol *ctype = op->ctype;
1456
1457 if (!lvalue_expression(expr->unop)) {
1458 sparse_error(expr->pos, "need lvalue expression for ++/--");
1459 return NULL;
1460 }
1461 if (is_restricted_type(ctype) && restricted_unop(expr->op, ctype)) {
1462 sparse_error(expr->pos, "bad operation on restricted");
1463 return NULL;
1464 }
1465
1466 evaluate_assign_to(op, ctype);
1467
1468 expr->ctype = ctype;
1469 expr->op_value = 1;
1470 if (is_ptr_type(ctype))
1471 expr->op_value = ptr_object_size(ctype) >> 3;
1472
1473 return ctype;
1474 }
1475
1476 static struct symbol *evaluate_sign(struct expression *expr)
1477 {
1478 struct symbol *ctype = expr->unop->ctype;
1479 if (is_int_type(ctype)) {
1480 struct symbol *rtype = rtype = integer_promotion(ctype);
1481 expr->unop = cast_to(expr->unop, rtype);
1482 ctype = rtype;
1483 } else if (is_float_type(ctype) && expr->op != '~') {
1484 /* no conversions needed */
1485 } else if (is_restricted_type(ctype) && !restricted_unop(expr->op, ctype)) {
1486 /* no conversions needed */
1487 } else {
1488 return bad_expr_type(expr);
1489 }
1490 if (expr->op == '+')
1491 *expr = *expr->unop;
1492 expr->ctype = ctype;
1493 return ctype;
1494 }
1495
1496 static struct symbol *evaluate_preop(struct expression *expr)
1497 {
1498 struct symbol *ctype = expr->unop->ctype;
1499
1500 switch (expr->op) {
1501 case '(':
1502 *expr = *expr->unop;
1503 return ctype;
1504
1505 case '+':
1506 case '-':
1507 case '~':
1508 return evaluate_sign(expr);
1509
1510 case '*':
1511 return evaluate_dereference(expr);
1512
1513 case '&':
1514 return evaluate_addressof(expr);
1515
1516 case SPECIAL_INCREMENT:
1517 case SPECIAL_DECREMENT:
1518 /*
1519 * From a type evaluation standpoint the pre-ops are
1520 * the same as the postops
1521 */
1522 return evaluate_postop(expr);
1523
1524 case '!':
1525 if (is_safe_type(ctype))
1526 warning(expr->pos, "testing a 'safe expression'");
1527 if (is_float_type(ctype)) {
1528 struct expression *arg = expr->unop;
1529 expr->type = EXPR_BINOP;
1530 expr->op = SPECIAL_EQUAL;
1531 expr->left = arg;
1532 expr->right = alloc_expression(expr->pos, EXPR_FVALUE);
1533 expr->right->ctype = ctype;
1534 expr->right->fvalue = 0;
1535 }
1536 ctype = &bool_ctype;
1537 break;
1538
1539 default:
1540 break;
1541 }
1542 expr->ctype = ctype;
1543 return &bool_ctype;
1544 }
1545
1546 static struct symbol *find_identifier(struct ident *ident, struct symbol_list *_list, int *offset)
1547 {
1548 struct ptr_list *head = (struct ptr_list *)_list;
1549 struct ptr_list *list = head;
1550
1551 if (!head)
1552 return NULL;
1553 do {
1554 int i;
1555 for (i = 0; i < list->nr; i++) {
1556 struct symbol *sym = (struct symbol *) list->list[i];
1557 if (sym->ident) {
1558 if (sym->ident != ident)
1559 continue;
1560 *offset = sym->offset;
1561 return sym;
1562 } else {
1563 struct symbol *ctype = sym->ctype.base_type;
1564 struct symbol *sub;
1565 if (!ctype)
1566 continue;
1567 if (ctype->type != SYM_UNION && ctype->type != SYM_STRUCT)
1568 continue;
1569 sub = find_identifier(ident, ctype->symbol_list, offset);
1570 if (!sub)
1571 continue;
1572 *offset += sym->offset;
1573 return sub;
1574 }
1575 }
1576 } while ((list = list->next) != head);
1577 return NULL;
1578 }
1579
1580 static struct expression *evaluate_offset(struct expression *expr, unsigned long offset)
1581 {
1582 struct expression *add;
1583
1584 /*
1585 * Create a new add-expression
1586 *
1587 * NOTE! Even if we just add zero, we need a new node
1588 * for the member pointer, since it has a different
1589 * type than the original pointer. We could make that
1590 * be just a cast, but the fact is, a node is a node,
1591 * so we might as well just do the "add zero" here.
1592 */
1593 add = alloc_expression(expr->pos, EXPR_BINOP);
1594 add->op = '+';
1595 add->left = expr;
1596 add->right = alloc_expression(expr->pos, EXPR_VALUE);
1597 add->right->ctype = &int_ctype;
1598 add->right->value = offset;
1599
1600 /*
1601 * The ctype of the pointer will be lazily evaluated if
1602 * we ever take the address of this member dereference..
1603 */
1604 add->ctype = &lazy_ptr_ctype;
1605 return add;
1606 }
1607
1608 /* structure/union dereference */
1609 static struct symbol *evaluate_member_dereference(struct expression *expr)
1610 {
1611 int offset;
1612 struct symbol *ctype, *member;
1613 struct expression *deref = expr->deref, *add;
1614 struct ident *ident = expr->member;
1615 unsigned int mod;
1616 int address_space;
1617
1618 if (!evaluate_expression(deref))
1619 return NULL;
1620 if (!ident) {
1621 sparse_error(expr->pos, "bad member name");
1622 return NULL;
1623 }
1624
1625 ctype = deref->ctype;
1626 address_space = ctype->ctype.as;
1627 mod = ctype->ctype.modifiers;
1628 if (ctype->type == SYM_NODE) {
1629 ctype = ctype->ctype.base_type;
1630 address_space |= ctype->ctype.as;
1631 mod |= ctype->ctype.modifiers;
1632 }
1633 if (!ctype || (ctype->type != SYM_STRUCT && ctype->type != SYM_UNION)) {
1634 sparse_error(expr->pos, "expected structure or union");
1635 return NULL;
1636 }
1637 offset = 0;
1638 member = find_identifier(ident, ctype->symbol_list, &offset);
1639 if (!member) {
1640 const char *type = ctype->type == SYM_STRUCT ? "struct" : "union";
1641 const char *name = "<unnamed>";
1642 int namelen = 9;
1643 if (ctype->ident) {
1644 name = ctype->ident->name;
1645 namelen = ctype->ident->len;
1646 }
1647 sparse_error(expr->pos, "no member '%s' in %s %.*s",
1648 show_ident(ident), type, namelen, name);
1649 return NULL;
1650 }
1651
1652 /*
1653 * The member needs to take on the address space and modifiers of
1654 * the "parent" type.
1655 */
1656 member = convert_to_as_mod(member, address_space, mod);
1657 ctype = get_base_type(member);
1658
1659 if (!lvalue_expression(deref)) {
1660 if (deref->type != EXPR_SLICE) {
1661 expr->base = deref;
1662 expr->r_bitpos = 0;
1663 } else {
1664 expr->base = deref->base;
1665 expr->r_bitpos = deref->r_bitpos;
1666 }
1667 expr->r_bitpos += offset << 3;
1668 expr->type = EXPR_SLICE;
1669 expr->r_nrbits = member->bit_size;
1670 expr->r_bitpos += member->bit_offset;
1671 expr->ctype = member;
1672 return member;
1673 }
1674
1675 deref = deref->unop;
1676 expr->deref = deref;
1677
1678 add = evaluate_offset(deref, offset);
1679 expr->type = EXPR_PREOP;
1680 expr->op = '*';
1681 expr->unop = add;
1682
1683 expr->ctype = member;
1684 return member;
1685 }
1686
1687 static int is_promoted(struct expression *expr)
1688 {
1689 while (1) {
1690 switch (expr->type) {
1691 case EXPR_BINOP:
1692 case EXPR_SELECT:
1693 case EXPR_CONDITIONAL:
1694 return 1;
1695 case EXPR_COMMA:
1696 expr = expr->right;
1697 continue;
1698 case EXPR_PREOP:
1699 switch (expr->op) {
1700 case '(':
1701 expr = expr->unop;
1702 continue;
1703 case '+':
1704 case '-':
1705 case '~':
1706 return 1;
1707 default:
1708 return 0;
1709 }
1710 default:
1711 return 0;
1712 }
1713 }
1714 }
1715
1716
1717 static struct symbol *evaluate_cast(struct expression *);
1718
1719 static struct symbol *evaluate_type_information(struct expression *expr)
1720 {
1721 struct symbol *sym = expr->cast_type;
1722 if (!sym) {
1723 sym = evaluate_expression(expr->cast_expression);
1724 if (!sym)
1725 return NULL;
1726 /*
1727 * Expressions of restricted types will possibly get
1728 * promoted - check that here
1729 */
1730 if (is_restricted_type(sym)) {
1731 if (sym->bit_size < bits_in_int && is_promoted(expr))
1732 sym = &int_ctype;
1733 }
1734 }
1735 examine_symbol_type(sym);
1736 if (is_bitfield_type(sym)) {
1737 sparse_error(expr->pos, "trying to examine bitfield type");
1738 return NULL;
1739 }
1740 return sym;
1741 }
1742
1743 static struct symbol *evaluate_sizeof(struct expression *expr)
1744 {
1745 struct symbol *type;
1746 int size;
1747
1748 type = evaluate_type_information(expr);
1749 if (!type)
1750 return NULL;
1751
1752 size = type->bit_size;
1753 if ((size < 0) || (size & 7))
1754 sparse_error(expr->pos, "cannot size expression");
1755 expr->type = EXPR_VALUE;
1756 expr->value = size >> 3;
1757 expr->ctype = size_t_ctype;
1758 return size_t_ctype;
1759 }
1760
1761 static struct symbol *evaluate_ptrsizeof(struct expression *expr)
1762 {
1763 struct symbol *type;
1764 int size;
1765
1766 type = evaluate_type_information(expr);
1767 if (!type)
1768 return NULL;
1769
1770 if (type->type == SYM_NODE)
1771 type = type->ctype.base_type;
1772 if (!type)
1773 return NULL;
1774 switch (type->type) {
1775 case SYM_ARRAY:
1776 break;
1777 case SYM_PTR:
1778 type = get_base_type(type);
1779 if (type)
1780 break;
1781 default:
1782 sparse_error(expr->pos, "expected pointer expression");
1783 return NULL;
1784 }
1785 size = type->bit_size;
1786 if (size & 7)
1787 size = 0;
1788 expr->type = EXPR_VALUE;
1789 expr->value = size >> 3;
1790 expr->ctype = size_t_ctype;
1791 return size_t_ctype;
1792 }
1793
1794 static struct symbol *evaluate_alignof(struct expression *expr)
1795 {
1796 struct symbol *type;
1797
1798 type = evaluate_type_information(expr);
1799 if (!type)
1800 return NULL;
1801
1802 expr->type = EXPR_VALUE;
1803 expr->value = type->ctype.alignment;
1804 expr->ctype = size_t_ctype;
1805 return size_t_ctype;
1806 }
1807
1808 static int evaluate_arguments(struct symbol *f, struct symbol *fn, struct expression_list *head)
1809 {
1810 struct expression *expr;
1811 struct symbol_list *argument_types = fn->arguments;
1812 struct symbol *argtype;
1813 int i = 1;
1814
1815 PREPARE_PTR_LIST(argument_types, argtype);
1816 FOR_EACH_PTR (head, expr) {
1817 struct expression **p = THIS_ADDRESS(expr);
1818 struct symbol *ctype, *target;
1819 ctype = evaluate_expression(expr);
1820
1821 if (!ctype)
1822 return 0;
1823
1824 ctype = degenerate(expr);
1825
1826 target = argtype;
1827 if (!target && ctype->bit_size < bits_in_int)
1828 target = &int_ctype;
1829 if (target) {
1830 static char where[30];
1831 examine_symbol_type(target);
1832 sprintf(where, "argument %d", i);
1833 compatible_assignment_types(expr, target, p, ctype, where, '=');
1834 }
1835
1836 i++;
1837 NEXT_PTR_LIST(argtype);
1838 } END_FOR_EACH_PTR(expr);
1839 FINISH_PTR_LIST(argtype);
1840 return 1;
1841 }
1842
1843 static void evaluate_initializer(struct symbol *ctype, struct expression **ep);
1844
1845 static int evaluate_one_array_initializer(struct symbol *ctype, struct expression **ep, int current)
1846 {
1847 struct expression *entry = *ep;
1848 struct expression **parent, *reuse = NULL;
1849 unsigned long offset;
1850 struct symbol *sym;
1851 unsigned long from, to;
1852 int accept_string = is_byte_type(ctype);
1853
1854 from = current;
1855 to = from+1;
1856 parent = ep;
1857 if (entry->type == EXPR_INDEX) {
1858 from = entry->idx_from;
1859 to = entry->idx_to+1;
1860 parent = &entry->idx_expression;
1861 reuse = entry;
1862 entry = entry->idx_expression;
1863 }
1864
1865 offset = from * (ctype->bit_size>>3);
1866 if (offset) {
1867 if (!reuse) reuse = alloc_expression(entry->pos, EXPR_POS);
1868 reuse->type = EXPR_POS;
1869 reuse->ctype = ctype;
1870 reuse->init_offset = offset;
1871 reuse->init_nr = to - from;
1872 reuse->init_expr = entry;
1873 parent = &reuse->init_expr;
1874 entry = reuse;
1875 }
1876 *ep = entry;
1877
1878 if (accept_string && entry->type == EXPR_STRING) {
1879 sym = evaluate_expression(entry);
1880 to = from + get_expression_value(sym->array_size);
1881 } else {
1882 evaluate_initializer(ctype, parent);
1883 }
1884 return to;
1885 }
1886
1887 static void evaluate_array_initializer(struct symbol *ctype, struct expression *expr)
1888 {
1889 struct expression *entry;
1890 int current = 0;
1891
1892 FOR_EACH_PTR(expr->expr_list, entry) {
1893 current = evaluate_one_array_initializer(ctype, THIS_ADDRESS(entry), current);
1894 } END_FOR_EACH_PTR(entry);
1895 }
1896
1897 /* A scalar initializer is allowed, and acts pretty much like an array of one */
1898 static void evaluate_scalar_initializer(struct symbol *ctype, struct expression *expr)
1899 {
1900 if (expression_list_size(expr->expr_list) != 1) {
1901 sparse_error(expr->pos, "unexpected compound initializer");
1902 return;
1903 }
1904 evaluate_array_initializer(ctype, expr);
1905 return;
1906 }
1907
1908 static struct symbol *find_struct_ident(struct symbol *ctype, struct ident *ident)
1909 {
1910 struct symbol *sym;
1911
1912 FOR_EACH_PTR(ctype->symbol_list, sym) {
1913 if (sym->ident == ident)
1914 return sym;
1915 } END_FOR_EACH_PTR(sym);
1916 return NULL;
1917 }
1918
1919 static int evaluate_one_struct_initializer(struct symbol *ctype, struct expression **ep, struct symbol *sym)
1920 {
1921 struct expression *entry = *ep;
1922 struct expression **parent;
1923 struct expression *reuse = NULL;
1924 unsigned long offset;
1925
1926 if (!sym) {
1927 sparse_error(entry->pos, "unknown named initializer");
1928 return -1;
1929 }
1930
1931 if (entry->type == EXPR_IDENTIFIER) {
1932 reuse = entry;
1933 entry = entry->ident_expression;
1934 }
1935
1936 parent = ep;
1937 offset = sym->offset;
1938 if (offset) {
1939 if (!reuse)
1940 reuse = alloc_expression(entry->pos, EXPR_POS);
1941 reuse->type = EXPR_POS;
1942 reuse->ctype = sym;
1943 reuse->init_offset = offset;
1944 reuse->init_nr = 1;
1945 reuse->init_expr = entry;
1946 parent = &reuse->init_expr;
1947 entry = reuse;
1948 }
1949 *ep = entry;
1950 evaluate_initializer(sym, parent);
1951 return 0;
1952 }
1953
1954 static void evaluate_struct_or_union_initializer(struct symbol *ctype, struct expression *expr, int multiple)
1955 {
1956 struct expression *entry;
1957 struct symbol *sym;
1958
1959 PREPARE_PTR_LIST(ctype->symbol_list, sym);
1960 FOR_EACH_PTR(expr->expr_list, entry) {
1961 if (entry->type == EXPR_IDENTIFIER) {
1962 struct ident *ident = entry->expr_ident;
1963 /* We special-case the "already right place" case */
1964 if (!sym || sym->ident != ident) {
1965 RESET_PTR_LIST(sym);
1966 for (;;) {
1967 if (!sym)
1968 break;
1969 if (sym->ident == ident)
1970 break;
1971 NEXT_PTR_LIST(sym);
1972 }
1973 }
1974 }
1975 if (evaluate_one_struct_initializer(ctype, THIS_ADDRESS(entry), sym))
1976 return;
1977 NEXT_PTR_LIST(sym);
1978 } END_FOR_EACH_PTR(entry);
1979 FINISH_PTR_LIST(sym);
1980 }
1981
1982 /*
1983 * Initializers are kind of like assignments. Except
1984 * they can be a hell of a lot more complex.
1985 */
1986 static void evaluate_initializer(struct symbol *ctype, struct expression **ep)
1987 {
1988 struct expression *expr = *ep;
1989
1990 /*
1991 * Simple non-structure/array initializers are the simple
1992 * case, and look (and parse) largely like assignments.
1993 */
1994 switch (expr->type) {
1995 default: {
1996 int is_string = expr->type == EXPR_STRING;
1997 struct symbol *rtype = evaluate_expression(expr);
1998 if (rtype) {
1999 /*
2000 * Special case:
2001 * char array[] = "string"
2002 * should _not_ degenerate.
2003 */
2004 if (!is_string || !is_string_type(ctype))
2005 rtype = degenerate(expr);
2006 compatible_assignment_types(expr, ctype, ep, rtype, "initializer", '=');
2007 }
2008 return;
2009 }
2010
2011 case EXPR_INITIALIZER:
2012 expr->ctype = ctype;
2013 if (ctype->type == SYM_NODE)
2014 ctype = ctype->ctype.base_type;
2015
2016 switch (ctype->type) {
2017 case SYM_ARRAY:
2018 case SYM_PTR:
2019 evaluate_array_initializer(get_base_type(ctype), expr);
2020 return;
2021 case SYM_UNION:
2022 evaluate_struct_or_union_initializer(ctype, expr, 0);
2023 return;
2024 case SYM_STRUCT:
2025 evaluate_struct_or_union_initializer(ctype, expr, 1);
2026 return;
2027 default:
2028 evaluate_scalar_initializer(ctype, expr);
2029 return;
2030 }
2031
2032 case EXPR_IDENTIFIER:
2033 if (ctype->type == SYM_NODE)
2034 ctype = ctype->ctype.base_type;
2035 if (ctype->type != SYM_STRUCT && ctype->type != SYM_UNION) {
2036 sparse_error(expr->pos, "expected structure or union for '%s' dereference", show_ident(expr->expr_ident));
2037 show_symbol(ctype);
2038 return;
2039 }
2040 evaluate_one_struct_initializer(ctype, ep,
2041 find_struct_ident(ctype, expr->expr_ident));
2042 return;
2043
2044 case EXPR_INDEX:
2045 if (ctype->type == SYM_NODE)
2046 ctype = ctype->ctype.base_type;
2047 if (ctype->type != SYM_ARRAY) {
2048 sparse_error(expr->pos, "expected array");
2049 return;
2050 }
2051 evaluate_one_array_initializer(ctype->ctype.base_type, ep, 0);
2052 return;
2053
2054 case EXPR_POS:
2055 /*
2056 * An EXPR_POS expression has already been evaluated, and we don't
2057 * need to do anything more
2058 */
2059 return;
2060 }
2061 }
2062
2063 static int get_as(struct symbol *sym)
2064 {
2065 int as;
2066 unsigned long mod;
2067
2068 if (!sym)
2069 return 0;
2070 as = sym->ctype.as;
2071 mod = sym->ctype.modifiers;
2072 if (sym->type == SYM_NODE) {
2073 sym = sym->ctype.base_type;
2074 as |= sym->ctype.as;
2075 mod |= sym->ctype.modifiers;
2076 }
2077
2078 /*
2079 * At least for now, allow casting to a "unsigned long".
2080 * That's how we do things like pointer arithmetic and
2081 * store pointers to registers.
2082 */
2083 if (sym == &ulong_ctype)
2084 return -1;
2085
2086 if (sym && sym->type == SYM_PTR) {
2087 sym = get_base_type(sym);
2088 as |= sym->ctype.as;
2089 mod |= sym->ctype.modifiers;
2090 }
2091 if (mod & MOD_FORCE)
2092 return -1;
2093 return as;
2094 }
2095
2096 static void cast_to_as(struct expression *e, int as)
2097 {
2098 struct expression *v = e->cast_expression;
2099
2100 if (!Wcast_to_address_space)
2101 return;
2102
2103 /* cast from constant 0 to pointer is OK */
2104 if (v->type == EXPR_VALUE && is_int_type(v->ctype) && !v->value)
2105 return;
2106
2107 warning(e->pos, "cast adds address space to expression (<asn:%d>)", as);
2108 }
2109
2110 static struct symbol *evaluate_cast(struct expression *expr)
2111 {
2112 struct expression *target = expr->cast_expression;
2113 struct symbol *ctype = examine_symbol_type(expr->cast_type);
2114 struct symbol *t1, *t2;
2115 enum type type1, type2;
2116 int as1, as2;
2117
2118 if (!target)
2119 return NULL;
2120
2121 expr->ctype = ctype;
2122 expr->cast_type = ctype;
2123
2124 /*
2125 * Special case: a cast can be followed by an
2126 * initializer, in which case we need to pass
2127 * the type value down to that initializer rather
2128 * than trying to evaluate it as an expression
2129 *
2130 * A more complex case is when the initializer is
2131 * dereferenced as part of a post-fix expression.
2132 * We need to produce an expression that can be dereferenced.
2133 */
2134 if (target->type == EXPR_INITIALIZER) {
2135 struct symbol *sym = expr->cast_type;
2136 struct expression *addr = alloc_expression(expr->pos, EXPR_SYMBOL);
2137
2138 sym->initializer = expr->cast_expression;
2139 evaluate_symbol(sym);
2140
2141 addr->ctype = &lazy_ptr_ctype; /* Lazy eval */
2142 addr->symbol = sym;
2143
2144 expr->type = EXPR_PREOP;
2145 expr->op = '*';
2146 expr->unop = addr;
2147 expr->ctype = sym;
2148
2149 return sym;
2150 }
2151
2152 evaluate_expression(target);
2153 degenerate(target);
2154
2155 t1 = ctype;
2156 if (t1->type == SYM_NODE)
2157 t1 = t1->ctype.base_type;
2158 if (t1->type == SYM_ENUM)
2159 t1 = t1->ctype.base_type;
2160
2161 /*
2162 * You can always throw a value away by casting to
2163 * "void" - that's an implicit "force". Note that
2164 * the same is _not_ true of "void *".
2165 */
2166 if (t1 == &void_ctype)
2167 goto out;
2168
2169 type1 = t1->type;
2170 if (type1 == SYM_ARRAY || type1 == SYM_UNION || type1 == SYM_STRUCT)
2171 warning(expr->pos, "cast to non-scalar");
2172
2173 t2 = target->ctype;
2174 if (!t2) {
2175 sparse_error(expr->pos, "cast from unknown type");
2176 goto out;
2177 }
2178 if (t2->type == SYM_NODE)
2179 t2 = t2->ctype.base_type;
2180 if (t2->type == SYM_ENUM)
2181 t2 = t2->ctype.base_type;
2182
2183 type2 = t2->type;
2184 if (type2 == SYM_ARRAY || type2 == SYM_UNION || type2 == SYM_STRUCT)
2185 warning(expr->pos, "cast from non-scalar");
2186
2187 if (!(ctype->ctype.modifiers & MOD_FORCE) && t1 != t2) {
2188 if (t1->type == SYM_RESTRICT)
2189 warning(expr->pos, "cast to restricted type");
2190 if (t2->type == SYM_RESTRICT)
2191 warning(expr->pos, "cast from restricted type");
2192 }
2193
2194 as1 = get_as(ctype);
2195 as2 = get_as(target->ctype);
2196 if (!as1 && as2 > 0)
2197 warning(expr->pos, "cast removes address space of expression");
2198 if (as1 > 0 && as2 > 0 && as1 != as2)
2199 warning(expr->pos, "cast between address spaces (<asn:%d>-><asn:%d>)", as2, as1);
2200 if (as1 > 0 && !as2)
2201 cast_to_as(expr, as1);
2202
2203 /*
2204 * Casts of constant values are special: they
2205 * can be NULL, and thus need to be simplified
2206 * early.
2207 */
2208 if (target->type == EXPR_VALUE)
2209 cast_value(expr, ctype, target, target->ctype);
2210
2211 out:
2212 return ctype;
2213 }
2214
2215 /*
2216 * Evaluate a call expression with a symbol. This
2217 * should expand inline functions, and evaluate
2218 * builtins.
2219 */
2220 static int evaluate_symbol_call(struct expression *expr)
2221 {
2222 struct expression *fn = expr->fn;
2223 struct symbol *ctype = fn->ctype;
2224
2225 if (fn->type != EXPR_PREOP)
2226 return 0;
2227
2228 if (ctype->op && ctype->op->evaluate)
2229 return ctype->op->evaluate(expr);
2230
2231 if (ctype->ctype.modifiers & MOD_INLINE) {
2232 int ret;
2233 struct symbol *curr = current_fn;
2234 current_fn = ctype->ctype.base_type;
2235 examine_fn_arguments(current_fn);
2236
2237 ret = inline_function(expr, ctype);
2238
2239 /* restore the old function */
2240 current_fn = curr;
2241 return ret;
2242 }
2243
2244 return 0;
2245 }
2246
2247 static struct symbol *evaluate_call(struct expression *expr)
2248 {
2249 int args, fnargs;
2250 struct symbol *ctype, *sym;
2251 struct expression *fn = expr->fn;
2252 struct expression_list *arglist = expr->args;
2253
2254 if (!evaluate_expression(fn))
2255 return NULL;
2256 sym = ctype = fn->ctype;
2257 if (ctype->type == SYM_NODE)
2258 ctype = ctype->ctype.base_type;
2259 if (ctype->type == SYM_PTR || ctype->type == SYM_ARRAY)
2260 ctype = get_base_type(ctype);
2261 if (!evaluate_arguments(sym, ctype, arglist))
2262 return NULL;
2263 if (ctype->type != SYM_FN) {
2264 sparse_error(expr->pos, "not a function %s", show_ident(sym->ident));
2265 return NULL;
2266 }
2267 args = expression_list_size(expr->args);
2268 fnargs = symbol_list_size(ctype->arguments);
2269 if (args < fnargs)
2270 sparse_error(expr->pos, "not enough arguments for function %s", show_ident(sym->ident));
2271 if (args > fnargs && !ctype->variadic)
2272 sparse_error(expr->pos, "too many arguments for function %s", show_ident(sym->ident));
2273 if (sym->type == SYM_NODE) {
2274 if (evaluate_symbol_call(expr))
2275 return expr->ctype;
2276 }
2277 expr->ctype = ctype->ctype.base_type;
2278 return expr->ctype;
2279 }
2280
2281 struct symbol *evaluate_expression(struct expression *expr)
2282 {
2283 if (!expr)
2284 return NULL;
2285 if (expr->ctype)
2286 return expr->ctype;
2287
2288 switch (expr->type) {
2289 case EXPR_VALUE:
2290 case EXPR_FVALUE:
2291 sparse_error(expr->pos, "value expression without a type");
2292 return NULL;
2293 case EXPR_STRING:
2294 return evaluate_string(expr);
2295 case EXPR_SYMBOL:
2296 return evaluate_symbol_expression(expr);
2297 case EXPR_BINOP:
2298 if (!evaluate_expression(expr->left))
2299 return NULL;
2300 if (!evaluate_expression(expr->right))
2301 return NULL;
2302 return evaluate_binop(expr);
2303 case EXPR_LOGICAL:
2304 return evaluate_logical(expr);
2305 case EXPR_COMMA:
2306 evaluate_expression(expr->left);
2307 if (!evaluate_expression(expr->right))
2308 return NULL;
2309 return evaluate_comma(expr);
2310 case EXPR_COMPARE:
2311 if (!evaluate_expression(expr->left))
2312 return NULL;
2313 if (!evaluate_expression(expr->right))
2314 return NULL;
2315 return evaluate_compare(expr);
2316 case EXPR_ASSIGNMENT:
2317 if (!evaluate_expression(expr->left))
2318 return NULL;
2319 if (!evaluate_expression(expr->right))
2320 return NULL;
2321 return evaluate_assignment(expr);
2322 case EXPR_PREOP:
2323 if (!evaluate_expression(expr->unop))
2324 return NULL;
2325 return evaluate_preop(expr);
2326 case EXPR_POSTOP:
2327 if (!evaluate_expression(expr->unop))
2328 return NULL;
2329 return evaluate_postop(expr);
2330 case EXPR_CAST:
2331 case EXPR_IMPLIED_CAST:
2332 return evaluate_cast(expr);
2333 case EXPR_SIZEOF:
2334 return evaluate_sizeof(expr);
2335 case EXPR_PTRSIZEOF:
2336 return evaluate_ptrsizeof(expr);
2337 case EXPR_ALIGNOF:
2338 return evaluate_alignof(expr);
2339 case EXPR_DEREF:
2340 return evaluate_member_dereference(expr);
2341 case EXPR_CALL:
2342 return evaluate_call(expr);
2343 case EXPR_SELECT:
2344 case EXPR_CONDITIONAL:
2345 return evaluate_conditional_expression(expr);
2346 case EXPR_STATEMENT:
2347 expr->ctype = evaluate_statement(expr->statement);
2348 return expr->ctype;
2349
2350 case EXPR_LABEL:
2351 expr->ctype = &ptr_ctype;
2352 return &ptr_ctype;
2353
2354 case EXPR_TYPE:
2355 /* Evaluate the type of the symbol .. */
2356 evaluate_symbol(expr->symbol);
2357 /* .. but the type of the _expression_ is a "type" */
2358 expr->ctype = &type_ctype;
2359 return &type_ctype;
2360
2361 /* These can not exist as stand-alone expressions */
2362 case EXPR_INITIALIZER:
2363 case EXPR_IDENTIFIER:
2364 case EXPR_INDEX:
2365 case EXPR_POS:
2366 sparse_error(expr->pos, "internal front-end error: initializer in expression");
2367 return NULL;
2368 case EXPR_SLICE:
2369 sparse_error(expr->pos, "internal front-end error: SLICE re-evaluated");
2370 return NULL;
2371 }
2372 return NULL;
2373 }
2374
2375 static void check_duplicates(struct symbol *sym)
2376 {
2377 int declared = 0;
2378 struct symbol *next = sym;
2379
2380 while ((next = next->same_symbol) != NULL) {
2381 const char *typediff;
2382 evaluate_symbol(next);
2383 declared++;
2384 typediff = type_difference(sym, next, 0, 0);
2385 if (typediff) {
2386 sparse_error(sym->pos, "symbol '%s' redeclared with different type (originally declared at %s:%d) - %s",
2387 show_ident(sym->ident),
2388 stream_name(next->pos.stream), next->pos.line, typediff);
2389 return;
2390 }
2391 }
2392 if (!declared) {
2393 unsigned long mod = sym->ctype.modifiers;
2394 if (mod & (MOD_STATIC | MOD_REGISTER))
2395 return;
2396 if (!(mod & MOD_TOPLEVEL))
2397 return;
2398 if (sym->ident == &main_ident)
2399 return;
2400 warning(sym->pos, "symbol '%s' was not declared. Should it be static?", show_ident(sym->ident));
2401 }
2402 }
2403
2404 static struct symbol *evaluate_symbol(struct symbol *sym)
2405 {
2406 struct symbol *base_type;
2407
2408 if (!sym)
2409 return sym;
2410 if (sym->evaluated)
2411 return sym;
2412 sym->evaluated = 1;
2413
2414 sym = examine_symbol_type(sym);
2415 base_type = get_base_type(sym);
2416 if (!base_type)
2417 return NULL;
2418
2419 /* Evaluate the initializers */
2420 if (sym->initializer)
2421 evaluate_initializer(sym, &sym->initializer);
2422
2423 /* And finally, evaluate the body of the symbol too */
2424 if (base_type->type == SYM_FN) {
2425 struct symbol *curr = current_fn;
2426
2427 current_fn = base_type;
2428
2429 examine_fn_arguments(base_type);
2430 if (!base_type->stmt && base_type->inline_stmt)
2431 uninline(sym);
2432 if (base_type->stmt)
2433 evaluate_statement(base_type->stmt);
2434
2435 current_fn = curr;
2436 }
2437
2438 return base_type;
2439 }
2440
2441 void evaluate_symbol_list(struct symbol_list *list)
2442 {
2443 struct symbol *sym;
2444
2445 FOR_EACH_PTR(list, sym) {
2446 check_duplicates(sym);
2447 evaluate_symbol(sym);
2448 } END_FOR_EACH_PTR(sym);
2449 }
2450
2451 static struct symbol *evaluate_return_expression(struct statement *stmt)
2452 {
2453 struct expression *expr = stmt->expression;
2454 struct symbol *ctype, *fntype;
2455
2456 evaluate_expression(expr);
2457 ctype = degenerate(expr);
2458 fntype = current_fn->ctype.base_type;
2459 if (!fntype || fntype == &void_ctype) {
2460 if (expr && ctype != &void_ctype)
2461 sparse_error(expr->pos, "return expression in %s function", fntype?"void":"typeless");
2462 return NULL;
2463 }
2464
2465 if (!expr) {
2466 sparse_error(stmt->pos, "return with no return value");
2467 return NULL;
2468 }
2469 if (!ctype)
2470 return NULL;
2471 compatible_assignment_types(expr, fntype, &stmt->expression, ctype, "return expression", '=');
2472 return NULL;
2473 }
2474
2475 static void evaluate_if_statement(struct statement *stmt)
2476 {
2477 if (!stmt->if_conditional)
2478 return;
2479
2480 evaluate_conditional(stmt->if_conditional, 0);
2481 evaluate_statement(stmt->if_true);
2482 evaluate_statement(stmt->if_false);
2483 }
2484
2485 static void evaluate_iterator(struct statement *stmt)
2486 {
2487 evaluate_conditional(stmt->iterator_pre_condition, 1);
2488 evaluate_conditional(stmt->iterator_post_condition,1);
2489 evaluate_statement(stmt->iterator_pre_statement);
2490 evaluate_statement(stmt->iterator_statement);
2491 evaluate_statement(stmt->iterator_post_statement);
2492 }
2493
2494 static void verify_output_constraint(struct expression *expr, const char *constraint)
2495 {
2496 switch (*constraint) {
2497 case '=': /* Assignment */
2498 case '+': /* Update */
2499 break;
2500 default:
2501 sparse_error(expr->pos, "output constraint is not an assignment constraint (\"%s\")", constraint);
2502 }
2503 }
2504
2505 static void verify_input_constraint(struct expression *expr, const char *constraint)
2506 {
2507 switch (*constraint) {
2508 case '=': /* Assignment */
2509 case '+': /* Update */
2510 sparse_error(expr->pos, "input constraint with assignment (\"%s\")", constraint);
2511 }
2512 }
2513
2514 static void evaluate_asm_statement(struct statement *stmt)
2515 {
2516 struct expression *expr;
2517 int state;
2518
2519 expr = stmt->asm_string;
2520 if (!expr || expr->type != EXPR_STRING) {
2521 sparse_error(stmt->pos, "need constant string for inline asm");
2522 return;
2523 }
2524
2525 state = 0;
2526 FOR_EACH_PTR(stmt->asm_outputs, expr) {
2527 struct ident *ident;
2528
2529 switch (state) {
2530 case 0: /* Identifier */
2531 state = 1;
2532 ident = (struct ident *)expr;
2533 continue;
2534
2535 case 1: /* Constraint */
2536 state = 2;
2537 if (!expr || expr->type != EXPR_STRING) {
2538 sparse_error(expr ? expr->pos : stmt->pos, "asm output constraint is not a string");
2539 *THIS_ADDRESS(expr) = NULL;
2540 continue;
2541 }
2542 verify_output_constraint(expr, expr->string->data);
2543 continue;
2544
2545 case 2: /* Expression */
2546 state = 0;
2547 if (!evaluate_expression(expr))
2548 return;
2549 if (!lvalue_expression(expr))
2550 warning(expr->pos, "asm output is not an lvalue");
2551 evaluate_assign_to(expr, expr->ctype);
2552 continue;
2553 }
2554 } END_FOR_EACH_PTR(expr);
2555
2556 state = 0;
2557 FOR_EACH_PTR(stmt->asm_inputs, expr) {
2558 struct ident *ident;
2559
2560 switch (state) {
2561 case 0: /* Identifier */
2562 state = 1;
2563 ident = (struct ident *)expr;
2564 continue;
2565
2566 case 1: /* Constraint */
2567 state = 2;
2568 if (!expr || expr->type != EXPR_STRING) {
2569 sparse_error(expr ? expr->pos : stmt->pos, "asm input constraint is not a string");
2570 *THIS_ADDRESS(expr) = NULL;
2571 continue;
2572 }
2573 verify_input_constraint(expr, expr->string->data);
2574 continue;
2575
2576 case 2: /* Expression */
2577 state = 0;
2578 if (!evaluate_expression(expr))
2579 return;
2580 continue;
2581 }
2582 } END_FOR_EACH_PTR(expr);
2583
2584 FOR_EACH_PTR(stmt->asm_clobbers, expr) {
2585 if (!expr) {
2586 sparse_error(stmt->pos, "bad asm output");
2587 return;
2588 }
2589 if (expr->type == EXPR_STRING)
2590 continue;
2591 sparse_error(expr->pos, "asm clobber is not a string");
2592 } END_FOR_EACH_PTR(expr);
2593 }
2594
2595 static void evaluate_case_statement(struct statement *stmt)
2596 {
2597 evaluate_expression(stmt->case_expression);
2598 evaluate_expression(stmt->case_to);
2599 evaluate_statement(stmt->case_statement);
2600 }
2601
2602 static void check_case_type(struct expression *switch_expr, struct expression *case_expr)
2603 {
2604 struct symbol *switch_type, *case_type;
2605 if (!case_expr)
2606 return;
2607 switch_type = switch_expr->ctype;
2608 case_type = evaluate_expression(case_expr);
2609
2610 if (case_type && switch_type) {
2611 /* Both integer types? */
2612 if (is_int_type(switch_type) && is_int_type(case_type))
2613 return;
2614 if (compatible_restricted_binop(SPECIAL_EQUAL, &switch_expr, &case_expr))
2615 return;
2616 }
2617
2618 sparse_error(case_expr->pos, "incompatible types for 'case' statement");
2619 }
2620
2621 static void evaluate_switch_statement(struct statement *stmt)
2622 {
2623 struct symbol *sym;
2624
2625 evaluate_expression(stmt->switch_expression);
2626 evaluate_statement(stmt->switch_statement);
2627 if (!stmt->switch_expression)
2628 return;
2629 FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
2630 struct statement *case_stmt = sym->stmt;
2631 check_case_type(stmt->switch_expression, case_stmt->case_expression);
2632 check_case_type(stmt->switch_expression, case_stmt->case_to);
2633 } END_FOR_EACH_PTR(sym);
2634 }
2635
2636 struct symbol *evaluate_statement(struct statement *stmt)
2637 {
2638 if (!stmt)
2639 return NULL;
2640
2641 switch (stmt->type) {
2642 case STMT_RETURN:
2643 return evaluate_return_expression(stmt);
2644
2645 case STMT_EXPRESSION:
2646 if (!evaluate_expression(stmt->expression))
2647 return NULL;
2648 return degenerate(stmt->expression);
2649
2650 case STMT_COMPOUND: {
2651 struct statement *s;
2652 struct symbol *type = NULL;
2653 struct symbol *sym;
2654
2655 /* Evaluate each symbol in the compound statement */
2656 FOR_EACH_PTR(stmt->syms, sym) {
2657 evaluate_symbol(sym);
2658 } END_FOR_EACH_PTR(sym);
2659 evaluate_symbol(stmt->ret);
2660
2661 /*
2662 * Then, evaluate each statement, making the type of the
2663 * compound statement be the type of the last statement
2664 */
2665 type = NULL;
2666 FOR_EACH_PTR(stmt->stmts, s) {
2667 type = evaluate_statement(s);
2668 } END_FOR_EACH_PTR(s);
2669 if (!type)
2670 type = &void_ctype;
2671 return type;
2672 }
2673 case STMT_IF:
2674 evaluate_if_statement(stmt);
2675 return NULL;
2676 case STMT_ITERATOR:
2677 evaluate_iterator(stmt);
2678 return NULL;
2679 case STMT_SWITCH:
2680 evaluate_switch_statement(stmt);
2681 return NULL;
2682 case STMT_CASE:
2683 evaluate_case_statement(stmt);
2684 return NULL;
2685 case STMT_LABEL:
2686 return evaluate_statement(stmt->label_statement);
2687 case STMT_GOTO:
2688 evaluate_expression(stmt->goto_expression);
2689 return NULL;
2690 case STMT_NONE:
2691 break;
2692 case STMT_ASM:
2693 evaluate_asm_statement(stmt);
2694 return NULL;
2695 case STMT_CONTEXT:
2696 evaluate_expression(stmt->expression);
2697 return NULL;
2698 case STMT_RANGE:
2699 evaluate_expression(stmt->range_expression);
2700 evaluate_expression(stmt->range_low);
2701 evaluate_expression(stmt->range_high);
2702 return NULL;
2703 }
2704 return NULL;
2705 }
Static analysis for C