1 /*
2 * Copyright (C) 2009 Dan Carpenter.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 */
17
18 /*
19 * The idea here is that you have an expression and you
20 * want to know what the type is for that.
21 */
22
23 #include "smatch.h"
24 #include "smatch_slist.h"
25
26 struct symbol *get_real_base_type(struct symbol *sym)
27 {
28 struct symbol *ret;
29
30 if (!sym)
31 return NULL;
32 if (sym->type == SYM_BASETYPE)
33 return sym;
34 ret = get_base_type(sym);
35 if (!ret)
36 return NULL;
37 if (ret->type == SYM_RESTRICT || ret->type == SYM_NODE)
38 return get_real_base_type(ret);
39 return ret;
40 }
41
42 int type_bytes(struct symbol *type)
43 {
44 int bits;
45
46 if (type && type->type == SYM_ARRAY)
47 return array_bytes(type);
48
49 bits = type_bits(type);
50 if (bits < 0)
51 return 0;
52 return bits_to_bytes(bits);
53 }
54
55 int array_bytes(struct symbol *type)
56 {
57 if (!type || type->type != SYM_ARRAY)
58 return 0;
59 return bits_to_bytes(type->bit_size);
60 }
61
62 static struct symbol *get_binop_type(struct expression *expr)
63 {
64 struct symbol *left, *right;
65
66 left = get_type(expr->left);
67 if (!left)
68 return NULL;
69
70 if (expr->op == SPECIAL_LEFTSHIFT ||
71 expr->op == SPECIAL_RIGHTSHIFT) {
72 if (type_positive_bits(left) < 31)
73 return &int_ctype;
74 return left;
75 }
76 right = get_type(expr->right);
77 if (!right)
78 return NULL;
79
80 if (type_is_fp(left)) {
81 if (type_is_fp(right)) {
82 if (type_bits(left) > type_bits(right))
83 return left;
84 return right;
85 }
86 return left;
87 }
88
89 if (type_is_fp(right)) {
90 if (type_is_fp(left)) {
91 if (type_bits(right) > type_bits(left))
92 return right;
93 return left;
94 }
95 return right;
96 }
97
98 if (expr->op == '-' &&
99 (is_ptr_type(left) && is_ptr_type(right)))
100 return ssize_t_ctype;
101
102 if (left->type == SYM_PTR || left->type == SYM_ARRAY)
103 return left;
104 if (right->type == SYM_PTR || right->type == SYM_ARRAY)
105 return right;
106
107 if (type_positive_bits(left) < 31 && type_positive_bits(right) < 31)
108 return &int_ctype;
109
110 if (type_positive_bits(left) > type_positive_bits(right))
111 return left;
112 return right;
113 }
114
115 static struct symbol *get_type_symbol(struct expression *expr)
116 {
117 if (!expr || expr->type != EXPR_SYMBOL || !expr->symbol)
118 return NULL;
119
120 return get_real_base_type(expr->symbol);
121 }
122
123 static struct symbol *get_member_symbol(struct symbol_list *symbol_list, struct ident *member)
124 {
125 struct symbol *tmp, *sub;
126
127 FOR_EACH_PTR(symbol_list, tmp) {
128 if (!tmp->ident) {
129 sub = get_real_base_type(tmp);
130 sub = get_member_symbol(sub->symbol_list, member);
131 if (sub)
132 return sub;
133 continue;
134 }
135 if (tmp->ident == member)
136 return tmp;
137 } END_FOR_EACH_PTR(tmp);
138
139 return NULL;
140 }
141
142 static struct symbol *get_symbol_from_deref(struct expression *expr)
143 {
144 struct ident *member;
145 struct symbol *sym;
146
147 if (!expr || expr->type != EXPR_DEREF)
148 return NULL;
149
150 member = expr->member;
151 sym = get_type(expr->deref);
152 if (!sym) {
153 // sm_msg("could not find struct type");
154 return NULL;
155 }
156 if (sym->type == SYM_PTR)
157 sym = get_real_base_type(sym);
158 sym = get_member_symbol(sym->symbol_list, member);
159 if (!sym)
160 return NULL;
161 return get_real_base_type(sym);
162 }
163
164 static struct symbol *handle__builtin_choose_expr(struct expression *expr)
165 {
166 struct expression *const_expr, *expr1, *expr2;
167 sval_t sval;
168
169 const_expr = get_argument_from_call_expr(expr->args, 0);
170 expr1 = get_argument_from_call_expr(expr->args, 1);
171 expr2 = get_argument_from_call_expr(expr->args, 2);
172
173 if (!get_value(const_expr, &sval) || !expr1 || !expr2)
174 return NULL;
175 if (sval.value)
176 return get_type(expr1);
177 else
178 return get_type(expr2);
179 }
180
181 static struct symbol *get_return_type(struct expression *expr)
182 {
183 struct symbol *tmp;
184
185 if (sym_name_is("__builtin_choose_expr", expr->fn))
186 return handle__builtin_choose_expr(expr);
187
188 tmp = get_type(expr->fn);
189 if (!tmp)
190 return NULL;
191 /* this is to handle __builtin_constant_p() */
192 if (tmp->type != SYM_FN)
193 tmp = get_base_type(tmp);
194 return get_real_base_type(tmp);
195 }
196
197 static struct symbol *get_expr_stmt_type(struct statement *stmt)
198 {
199 if (stmt->type != STMT_COMPOUND)
200 return NULL;
201 stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
202 if (stmt->type == STMT_LABEL)
203 stmt = stmt->label_statement;
204 if (stmt->type != STMT_EXPRESSION)
205 return NULL;
206 return get_type(stmt->expression);
207 }
208
209 static struct symbol *get_select_type(struct expression *expr)
210 {
211 struct symbol *one, *two;
212
213 one = get_type(expr->cond_true);
214 two = get_type(expr->cond_false);
215 if (!one || !two)
216 return NULL;
217 /*
218 * This is a hack. If the types are not equiv then we
219 * really don't know the type. But I think guessing is
220 * probably Ok here.
221 */
222 if (type_positive_bits(one) > type_positive_bits(two))
223 return one;
224 return two;
225 }
226
227 struct symbol *get_pointer_type(struct expression *expr)
228 {
229 struct symbol *sym;
230
231 sym = get_type(expr);
232 if (!sym)
233 return NULL;
234 if (sym->type == SYM_NODE) {
235 sym = get_real_base_type(sym);
236 if (!sym)
237 return NULL;
238 }
239 if (sym->type != SYM_PTR && sym->type != SYM_ARRAY)
240 return NULL;
241 return get_real_base_type(sym);
242 }
243
244 static struct symbol *fake_pointer_sym(struct expression *expr)
245 {
246 struct symbol *sym;
247 struct symbol *base;
248
249 sym = alloc_symbol(expr->pos, SYM_PTR);
250 expr = expr->unop;
251 base = get_type(expr);
252 if (!base)
253 return NULL;
254 sym->ctype.base_type = base;
255 return sym;
256 }
257
258 static struct symbol *get_type_helper(struct expression *expr)
259 {
260 struct symbol *ret;
261
262 expr = strip_parens(expr);
263 if (!expr)
264 return NULL;
265
266 if (expr->ctype)
267 return expr->ctype;
268
269 switch (expr->type) {
270 case EXPR_STRING:
271 ret = &string_ctype;
272 break;
273 case EXPR_SYMBOL:
274 ret = get_type_symbol(expr);
275 break;
276 case EXPR_DEREF:
277 ret = get_symbol_from_deref(expr);
278 break;
279 case EXPR_PREOP:
280 case EXPR_POSTOP:
281 if (expr->op == '&')
282 ret = fake_pointer_sym(expr);
283 else if (expr->op == '*')
284 ret = get_pointer_type(expr->unop);
285 else
286 ret = get_type(expr->unop);
287 break;
288 case EXPR_ASSIGNMENT:
289 ret = get_type(expr->left);
290 break;
291 case EXPR_CAST:
292 case EXPR_FORCE_CAST:
293 case EXPR_IMPLIED_CAST:
294 ret = get_real_base_type(expr->cast_type);
295 break;
296 case EXPR_COMPARE:
297 case EXPR_BINOP:
298 ret = get_binop_type(expr);
299 break;
300 case EXPR_CALL:
301 ret = get_return_type(expr);
302 break;
303 case EXPR_STATEMENT:
304 ret = get_expr_stmt_type(expr->statement);
305 break;
306 case EXPR_CONDITIONAL:
307 case EXPR_SELECT:
308 ret = get_select_type(expr);
309 break;
310 case EXPR_SIZEOF:
311 ret = &ulong_ctype;
312 break;
313 case EXPR_LOGICAL:
314 ret = &int_ctype;
315 break;
316 case EXPR_OFFSETOF:
317 ret = &ulong_ctype;
318 break;
319 default:
320 return NULL;
321 }
322
323 if (ret && ret->type == SYM_TYPEOF)
324 ret = get_type(ret->initializer);
325
326 expr->ctype = ret;
327 return ret;
328 }
329
330 static struct symbol *get_final_type_helper(struct expression *expr)
331 {
332 /*
333 * The problem is that I wrote a bunch of Smatch to think that
334 * you could do get_type() on an expression and it would give
335 * you what the comparison was type promoted to. This is wrong
336 * but fixing it is a big of work... Hence this horrible hack.
337 *
338 */
339
340 expr = strip_parens(expr);
341 if (!expr)
342 return NULL;
343
344 if (expr->type == EXPR_COMPARE)
345 return &int_ctype;
346
347 return NULL;
348 }
349
350 struct symbol *get_type(struct expression *expr)
351 {
352 return get_type_helper(expr);
353 }
354
355 struct symbol *get_final_type(struct expression *expr)
356 {
357 struct symbol *ret;
358
359 ret = get_final_type_helper(expr);
360 if (ret)
361 return ret;
362 return get_type_helper(expr);
363 }
364
365 struct symbol *get_promoted_type(struct symbol *left, struct symbol *right)
366 {
367 struct symbol *ret = &int_ctype;
368
369 if (type_positive_bits(left) > type_positive_bits(ret))
370 ret = left;
371 if (type_positive_bits(right) > type_positive_bits(ret))
372 ret = right;
373
374 if (type_is_ptr(left))
375 ret = left;
376 if (type_is_ptr(right))
377 ret = right;
378
379 return ret;
380 }
381
382 int type_signed(struct symbol *base_type)
383 {
384 if (!base_type)
385 return 0;
386 if (base_type->ctype.modifiers & MOD_SIGNED)
387 return 1;
388 return 0;
389 }
390
391 int expr_unsigned(struct expression *expr)
392 {
393 struct symbol *sym;
394
395 sym = get_type(expr);
396 if (!sym)
397 return 0;
398 if (type_unsigned(sym))
399 return 1;
400 return 0;
401 }
402
403 int expr_signed(struct expression *expr)
404 {
405 struct symbol *sym;
406
407 sym = get_type(expr);
408 if (!sym)
409 return 0;
410 if (type_signed(sym))
411 return 1;
412 return 0;
413 }
414
415 int returns_unsigned(struct symbol *sym)
416 {
417 if (!sym)
418 return 0;
419 sym = get_base_type(sym);
420 if (!sym || sym->type != SYM_FN)
421 return 0;
422 sym = get_base_type(sym);
423 return type_unsigned(sym);
424 }
425
426 int is_pointer(struct expression *expr)
427 {
428 return type_is_ptr(get_type(expr));
429 }
430
431 int returns_pointer(struct symbol *sym)
432 {
433 if (!sym)
434 return 0;
435 sym = get_base_type(sym);
436 if (!sym || sym->type != SYM_FN)
437 return 0;
438 sym = get_base_type(sym);
439 if (sym && sym->type == SYM_PTR)
440 return 1;
441 return 0;
442 }
443
444 static sval_t fp_max(struct symbol *type)
445 {
446 sval_t ret = { .type = type };
447
448 if (type == &float_ctype)
449 ret.fvalue = FLT_MAX;
450 else if (type == &double_ctype)
451 ret.dvalue = DBL_MAX;
452 else
453 ret.ldvalue = LDBL_MAX;
454
455 return ret;
456 }
457
458 sval_t sval_type_max(struct symbol *base_type)
459 {
460 sval_t ret;
461
462 if (type_is_fp(base_type))
463 return fp_max(base_type);
464
465 if (!base_type || !type_bits(base_type))
466 base_type = &llong_ctype;
467 ret.type = base_type;
468
469 ret.value = (~0ULL) >> (64 - type_positive_bits(base_type));
470 return ret;
471 }
472
473 static sval_t fp_min(struct symbol *type)
474 {
475 sval_t ret = { .type = type };
476
477 if (type == &float_ctype)
478 ret.fvalue = -FLT_MAX;
479 else if (type == &double_ctype)
480 ret.dvalue = -DBL_MAX;
481 else
482 ret.ldvalue = -LDBL_MAX;
483
484 return ret;
485 }
486
487 sval_t sval_type_min(struct symbol *base_type)
488 {
489 sval_t ret;
490
491 if (type_is_fp(base_type))
492 return fp_min(base_type);
493
494 if (!base_type || !type_bits(base_type))
495 base_type = &llong_ctype;
496 ret.type = base_type;
497
498 if (type_unsigned(base_type) || is_ptr_type(base_type)) {
499 ret.value = 0;
500 return ret;
501 }
502
503 ret.value = (~0ULL) << type_positive_bits(base_type);
504
505 return ret;
506 }
507
508 int nr_bits(struct expression *expr)
509 {
510 struct symbol *type;
511
512 type = get_type(expr);
513 if (!type)
514 return 0;
515 return type_bits(type);
516 }
517
518 int is_void_pointer(struct expression *expr)
519 {
520 struct symbol *type;
521
522 type = get_type(expr);
523 if (!type || type->type != SYM_PTR)
524 return 0;
525 type = get_real_base_type(type);
526 if (type == &void_ctype)
527 return 1;
528 return 0;
529 }
530
531 int is_char_pointer(struct expression *expr)
532 {
533 struct symbol *type;
534
535 type = get_type(expr);
536 if (!type || type->type != SYM_PTR)
537 return 0;
538 type = get_real_base_type(type);
539 if (type == &char_ctype)
540 return 1;
541 return 0;
542 }
543
544 int is_string(struct expression *expr)
545 {
546 expr = strip_expr(expr);
547 if (!expr || expr->type != EXPR_STRING)
548 return 0;
549 if (expr->string)
550 return 1;
551 return 0;
552 }
553
554 int is_static(struct expression *expr)
555 {
556 char *name;
557 struct symbol *sym;
558 int ret = 0;
559
560 name = expr_to_str_sym(expr, &sym);
561 if (!name || !sym)
562 goto free;
563
564 if (sym->ctype.modifiers & MOD_STATIC)
565 ret = 1;
566 free:
567 free_string(name);
568 return ret;
569 }
570
571 bool is_local_variable(struct expression *expr)
572 {
573 struct symbol *sym;
574
575 if (!expr || expr->type != EXPR_SYMBOL || !expr->symbol)
576 return false;
577 sym = expr->symbol;
578 if (!(sym->ctype.modifiers & MOD_TOPLEVEL))
579 return true;
580 return false;
581 }
582
583 int types_equiv(struct symbol *one, struct symbol *two)
584 {
585 if (!one && !two)
586 return 1;
587 if (!one || !two)
588 return 0;
589 if (one->type != two->type)
590 return 0;
591 if (one->type == SYM_PTR)
592 return types_equiv(get_real_base_type(one), get_real_base_type(two));
593 if (type_positive_bits(one) != type_positive_bits(two))
594 return 0;
595 return 1;
596 }
597
598 int fn_static(void)
599 {
600 return !!(cur_func_sym->ctype.modifiers & MOD_STATIC);
601 }
602
603 const char *global_static(void)
604 {
605 if (cur_func_sym->ctype.modifiers & MOD_STATIC)
606 return "static";
607 else
608 return "global";
609 }
610
611 struct symbol *cur_func_return_type(void)
612 {
613 struct symbol *sym;
614
615 sym = get_real_base_type(cur_func_sym);
616 if (!sym || sym->type != SYM_FN)
617 return NULL;
618 sym = get_real_base_type(sym);
619 return sym;
620 }
621
622 struct symbol *get_arg_type(struct expression *fn, int arg)
623 {
624 struct symbol *fn_type;
625 struct symbol *tmp;
626 struct symbol *arg_type;
627 int i;
628
629 fn_type = get_type(fn);
630 if (!fn_type)
631 return NULL;
632 if (fn_type->type == SYM_PTR)
633 fn_type = get_real_base_type(fn_type);
634 if (fn_type->type != SYM_FN)
635 return NULL;
636
637 i = 0;
638 FOR_EACH_PTR(fn_type->arguments, tmp) {
639 arg_type = get_real_base_type(tmp);
640 if (i == arg) {
641 return arg_type;
642 }
643 i++;
644 } END_FOR_EACH_PTR(tmp);
645
646 return NULL;
647 }
648
649 static struct symbol *get_member_from_string(struct symbol_list *symbol_list, const char *name)
650 {
651 struct symbol *tmp, *sub;
652 int chunk_len;
653
654 if (strncmp(name, ".", 1) == 0)
655 name += 1;
656 else if (strncmp(name, "->", 2) == 0)
657 name += 2;
658
659 FOR_EACH_PTR(symbol_list, tmp) {
660 if (!tmp->ident) {
661 sub = get_real_base_type(tmp);
662 sub = get_member_from_string(sub->symbol_list, name);
663 if (sub)
664 return sub;
665 continue;
666 }
667
668 if (strcmp(tmp->ident->name, name) == 0)
669 return tmp;
670
671 chunk_len = tmp->ident->len;
672 if (strncmp(tmp->ident->name, name, chunk_len) == 0 &&
673 (name[chunk_len] == '.' || name[chunk_len] == '-')) {
674 sub = get_real_base_type(tmp);
675 if (sub->type == SYM_PTR)
676 sub = get_real_base_type(sub);
677 return get_member_from_string(sub->symbol_list, name + chunk_len);
678 }
679
680 } END_FOR_EACH_PTR(tmp);
681
682 return NULL;
683 }
684
685 struct symbol *get_member_type_from_key(struct expression *expr, const char *key)
686 {
687 struct symbol *sym;
688
689 if (strcmp(key, "$") == 0)
690 return get_type(expr);
691
692 if (strcmp(key, "*$") == 0) {
693 sym = get_type(expr);
694 if (!sym || sym->type != SYM_PTR)
695 return NULL;
696 return get_real_base_type(sym);
697 }
698
699 sym = get_type(expr);
700 if (!sym)
701 return NULL;
702 if (sym->type == SYM_PTR)
703 sym = get_real_base_type(sym);
704
705 key = key + 1;
706 sym = get_member_from_string(sym->symbol_list, key);
707 if (!sym)
708 return NULL;
709 return get_real_base_type(sym);
710 }
711
712 struct symbol *get_arg_type_from_key(struct expression *fn, int param, struct expression *arg, const char *key)
713 {
714 struct symbol *type;
715
716 if (!key)
717 return NULL;
718 if (strcmp(key, "$") == 0)
719 return get_arg_type(fn, param);
720 if (strcmp(key, "*$") == 0) {
721 type = get_arg_type(fn, param);
722 if (!type || type->type != SYM_PTR)
723 return NULL;
724 return get_real_base_type(type);
725 }
726 return get_member_type_from_key(arg, key);
727 }
728
729 int is_struct(struct expression *expr)
730 {
731 struct symbol *type;
732
733 type = get_type(expr);
734 if (type && type->type == SYM_STRUCT)
735 return 1;
736 return 0;
737 }
738
739 static struct {
740 struct symbol *sym;
741 const char *name;
742 } base_types[] = {
743 {&bool_ctype, "bool"},
744 {&void_ctype, "void"},
745 {&type_ctype, "type"},
746 {&char_ctype, "char"},
747 {&schar_ctype, "schar"},
748 {&uchar_ctype, "uchar"},
749 {&short_ctype, "short"},
750 {&sshort_ctype, "sshort"},
751 {&ushort_ctype, "ushort"},
752 {&int_ctype, "int"},
753 {&sint_ctype, "sint"},
754 {&uint_ctype, "uint"},
755 {&long_ctype, "long"},
756 {&slong_ctype, "slong"},
757 {&ulong_ctype, "ulong"},
758 {&llong_ctype, "llong"},
759 {&sllong_ctype, "sllong"},
760 {&ullong_ctype, "ullong"},
761 {&lllong_ctype, "lllong"},
762 {&slllong_ctype, "slllong"},
763 {&ulllong_ctype, "ulllong"},
764 {&float_ctype, "float"},
765 {&double_ctype, "double"},
766 {&ldouble_ctype, "ldouble"},
767 {&string_ctype, "string"},
768 {&ptr_ctype, "ptr"},
769 {&lazy_ptr_ctype, "lazy_ptr"},
770 {&incomplete_ctype, "incomplete"},
771 {&label_ctype, "label"},
772 {&bad_ctype, "bad"},
773 {&null_ctype, "null"},
774 };
775
776 static const char *base_type_str(struct symbol *sym)
777 {
778 int i;
779
780 for (i = 0; i < ARRAY_SIZE(base_types); i++) {
781 if (sym == base_types[i].sym)
782 return base_types[i].name;
783 }
784 return "<unknown>";
785 }
786
787 static int type_str_helper(char *buf, int size, struct symbol *type)
788 {
789 int n;
790
791 if (!type)
792 return snprintf(buf, size, "<unknown>");
793
794 if (type->type == SYM_BASETYPE) {
795 return snprintf(buf, size, "%s", base_type_str(type));
796 } else if (type->type == SYM_PTR) {
797 type = get_real_base_type(type);
798 n = type_str_helper(buf, size, type);
799 if (n > size)
800 return n;
801 return n + snprintf(buf + n, size - n, "*");
802 } else if (type->type == SYM_ARRAY) {
803 type = get_real_base_type(type);
804 n = type_str_helper(buf, size, type);
805 if (n > size)
806 return n;
807 return n + snprintf(buf + n, size - n, "[]");
808 } else if (type->type == SYM_STRUCT) {
809 return snprintf(buf, size, "struct %s", type->ident ? type->ident->name : "");
810 } else if (type->type == SYM_UNION) {
811 if (type->ident)
812 return snprintf(buf, size, "union %s", type->ident->name);
813 else
814 return snprintf(buf, size, "anonymous union");
815 } else if (type->type == SYM_FN) {
816 struct symbol *arg, *return_type, *arg_type;
817 int i;
818
819 return_type = get_real_base_type(type);
820 n = type_str_helper(buf, size, return_type);
821 if (n > size)
822 return n;
823 n += snprintf(buf + n, size - n, "(*)(");
824 if (n > size)
825 return n;
826
827 i = 0;
828 FOR_EACH_PTR(type->arguments, arg) {
829 if (i++)
830 n += snprintf(buf + n, size - n, ", ");
831 if (n > size)
832 return n;
833 arg_type = get_real_base_type(arg);
834 n += type_str_helper(buf + n, size - n, arg_type);
835 if (n > size)
836 return n;
837 } END_FOR_EACH_PTR(arg);
838
839 return n + snprintf(buf + n, size - n, ")");
840 } else if (type->type == SYM_NODE) {
841 n = snprintf(buf, size, "node {");
842 if (n > size)
843 return n;
844 type = get_real_base_type(type);
845 n += type_str_helper(buf + n, size - n, type);
846 if (n > size)
847 return n;
848 return n + snprintf(buf + n, size - n, "}");
849 } else if (type->type == SYM_ENUM) {
850 return snprintf(buf, size, "enum %s", type->ident ? type->ident->name : "<unknown>");
851 } else {
852 return snprintf(buf, size, "<type %d>", type->type);
853 }
854 }
855
856 char *type_to_str(struct symbol *type)
857 {
858 static char buf[256];
859
860 buf[0] = '\0';
861 type_str_helper(buf, sizeof(buf), type);
862 return buf;
863 }