held_dev: delete this check
[smatch.git] / smatch_type.c
blob90d07d31229c72915d9aa93b28b98a57ce5326fb
1 /*
2 * Copyright (C) 2009 Dan Carpenter.
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.
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.
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
19 * The idea here is that you have an expression and you
20 * want to know what the type is for that.
23 #include "smatch.h"
24 #include "smatch_slist.h"
26 struct symbol *get_real_base_type(struct symbol *sym)
28 struct symbol *ret;
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;
42 int type_bytes(struct symbol *type)
44 int bits;
46 if (type && type->type == SYM_ARRAY)
47 return array_bytes(type);
49 bits = type_bits(type);
50 if (bits < 0)
51 return 0;
52 return bits_to_bytes(bits);
55 int array_bytes(struct symbol *type)
57 if (!type || type->type != SYM_ARRAY)
58 return 0;
59 if (!type->array_size)
60 return 0;
61 return bits_to_bytes(type->bit_size);
64 static struct symbol *get_binop_type(struct expression *expr)
66 struct symbol *left, *right;
68 left = get_type(expr->left);
69 if (!left)
70 return NULL;
72 if (expr->op == SPECIAL_LEFTSHIFT ||
73 expr->op == SPECIAL_RIGHTSHIFT) {
74 if (type_positive_bits(left) < 31)
75 return &int_ctype;
76 return left;
78 right = get_type(expr->right);
79 if (!right)
80 return NULL;
82 if (type_is_fp(left)) {
83 if (type_is_fp(right)) {
84 if (type_bits(left) > type_bits(right))
85 return left;
86 return right;
88 return left;
91 if (type_is_fp(right)) {
92 if (type_is_fp(left)) {
93 if (type_bits(right) > type_bits(left))
94 return right;
95 return left;
97 return right;
100 if (expr->op == '-' &&
101 (is_ptr_type(left) && is_ptr_type(right)))
102 return ssize_t_ctype;
104 if (left->type == SYM_PTR || left->type == SYM_ARRAY)
105 return left;
106 if (right->type == SYM_PTR || right->type == SYM_ARRAY)
107 return right;
109 if (type_positive_bits(left) < 31 && type_positive_bits(right) < 31)
110 return &int_ctype;
112 if (type_positive_bits(left) > type_positive_bits(right))
113 return left;
114 return right;
117 static struct symbol *get_type_symbol(struct expression *expr)
119 if (!expr || expr->type != EXPR_SYMBOL || !expr->symbol)
120 return NULL;
122 return get_real_base_type(expr->symbol);
125 static struct symbol *get_member_symbol(struct symbol_list *symbol_list, struct ident *member)
127 struct symbol *tmp, *sub;
129 FOR_EACH_PTR(symbol_list, tmp) {
130 if (!tmp->ident) {
131 sub = get_real_base_type(tmp);
132 sub = get_member_symbol(sub->symbol_list, member);
133 if (sub)
134 return sub;
135 continue;
137 if (tmp->ident == member)
138 return tmp;
139 } END_FOR_EACH_PTR(tmp);
141 return NULL;
144 static struct symbol *get_symbol_from_deref(struct expression *expr)
146 struct ident *member;
147 struct symbol *sym;
149 if (!expr || expr->type != EXPR_DEREF)
150 return NULL;
152 member = expr->member;
153 sym = get_type(expr->deref);
154 if (!sym) {
155 // sm_msg("could not find struct type");
156 return NULL;
158 if (sym->type == SYM_PTR)
159 sym = get_real_base_type(sym);
160 sym = get_member_symbol(sym->symbol_list, member);
161 if (!sym)
162 return NULL;
163 return get_real_base_type(sym);
166 static struct symbol *handle__builtin_choose_expr(struct expression *expr)
168 struct expression *const_expr, *expr1, *expr2;
169 sval_t sval;
171 const_expr = get_argument_from_call_expr(expr->args, 0);
172 expr1 = get_argument_from_call_expr(expr->args, 1);
173 expr2 = get_argument_from_call_expr(expr->args, 2);
175 if (!get_value(const_expr, &sval) || !expr1 || !expr2)
176 return NULL;
177 if (sval.value)
178 return get_type(expr1);
179 else
180 return get_type(expr2);
183 static struct symbol *get_return_type(struct expression *expr)
185 struct symbol *tmp;
187 if (sym_name_is("__builtin_choose_expr", expr->fn))
188 return handle__builtin_choose_expr(expr);
190 tmp = get_type(expr->fn);
191 if (!tmp)
192 return NULL;
193 /* this is to handle __builtin_constant_p() */
194 if (tmp->type != SYM_FN)
195 tmp = get_base_type(tmp);
196 return get_real_base_type(tmp);
199 static struct symbol *get_expr_stmt_type(struct statement *stmt)
201 if (stmt->type != STMT_COMPOUND)
202 return NULL;
203 stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
204 if (stmt->type == STMT_LABEL)
205 stmt = stmt->label_statement;
206 if (stmt->type != STMT_EXPRESSION)
207 return NULL;
208 return get_type(stmt->expression);
211 static struct symbol *get_select_type(struct expression *expr)
213 struct symbol *one, *two;
215 one = get_type(expr->cond_true);
216 two = get_type(expr->cond_false);
217 if (!one || !two)
218 return NULL;
220 * This is a hack. If the types are not equiv then we
221 * really don't know the type. But I think guessing is
222 * probably Ok here.
224 if (type_positive_bits(one) > type_positive_bits(two))
225 return one;
226 return two;
229 struct symbol *get_pointer_type(struct expression *expr)
231 struct symbol *sym;
233 sym = get_type(expr);
234 if (!sym)
235 return NULL;
236 if (sym->type == SYM_NODE) {
237 sym = get_real_base_type(sym);
238 if (!sym)
239 return NULL;
241 if (sym->type != SYM_PTR && sym->type != SYM_ARRAY)
242 return NULL;
243 return get_real_base_type(sym);
246 static struct symbol *fake_pointer_sym(struct expression *expr)
248 struct symbol *sym;
249 struct symbol *base;
251 sym = alloc_symbol(expr->pos, SYM_PTR);
252 expr = expr->unop;
253 base = get_type(expr);
254 if (!base)
255 return NULL;
256 sym->ctype.base_type = base;
257 return sym;
260 static struct symbol *get_type_helper(struct expression *expr)
262 struct symbol *ret;
264 expr = strip_parens(expr);
265 if (!expr)
266 return NULL;
268 if (expr->ctype)
269 return expr->ctype;
271 switch (expr->type) {
272 case EXPR_STRING:
273 ret = &string_ctype;
274 break;
275 case EXPR_SYMBOL:
276 ret = get_type_symbol(expr);
277 break;
278 case EXPR_DEREF:
279 ret = get_symbol_from_deref(expr);
280 break;
281 case EXPR_PREOP:
282 case EXPR_POSTOP:
283 if (expr->op == '&')
284 ret = fake_pointer_sym(expr);
285 else if (expr->op == '*')
286 ret = get_pointer_type(expr->unop);
287 else
288 ret = get_type(expr->unop);
289 break;
290 case EXPR_ASSIGNMENT:
291 ret = get_type(expr->left);
292 break;
293 case EXPR_CAST:
294 case EXPR_FORCE_CAST:
295 case EXPR_IMPLIED_CAST:
296 ret = get_real_base_type(expr->cast_type);
297 break;
298 case EXPR_COMPARE:
299 case EXPR_BINOP:
300 ret = get_binop_type(expr);
301 break;
302 case EXPR_CALL:
303 ret = get_return_type(expr);
304 break;
305 case EXPR_STATEMENT:
306 ret = get_expr_stmt_type(expr->statement);
307 break;
308 case EXPR_CONDITIONAL:
309 case EXPR_SELECT:
310 ret = get_select_type(expr);
311 break;
312 case EXPR_SIZEOF:
313 ret = &ulong_ctype;
314 break;
315 case EXPR_LOGICAL:
316 ret = &int_ctype;
317 break;
318 case EXPR_OFFSETOF:
319 ret = &ulong_ctype;
320 break;
321 default:
322 return NULL;
325 if (ret && ret->type == SYM_TYPEOF)
326 ret = get_type(ret->initializer);
328 expr->ctype = ret;
329 return ret;
332 static struct symbol *get_final_type_helper(struct expression *expr)
335 * The problem is that I wrote a bunch of Smatch to think that
336 * you could do get_type() on an expression and it would give
337 * you what the comparison was type promoted to. This is wrong
338 * but fixing it is a big of work... Hence this horrible hack.
342 expr = strip_parens(expr);
343 if (!expr)
344 return NULL;
346 if (expr->type == EXPR_COMPARE)
347 return &int_ctype;
349 return NULL;
352 struct symbol *get_type(struct expression *expr)
354 return get_type_helper(expr);
357 struct symbol *get_comparison_type(struct expression *expr)
360 * Eventually we will probably have to figure out how to make get_type()
361 * return &int_ctype so let's create a helper function to transition to.
363 return get_type_helper(expr);
366 struct symbol *get_final_type(struct expression *expr)
368 struct symbol *ret;
370 ret = get_final_type_helper(expr);
371 if (ret)
372 return ret;
373 return get_type_helper(expr);
376 struct symbol *get_promoted_type(struct symbol *left, struct symbol *right)
378 struct symbol *ret = &int_ctype;
380 if (type_positive_bits(left) > type_positive_bits(ret))
381 ret = left;
382 if (type_positive_bits(right) > type_positive_bits(ret))
383 ret = right;
385 if (type_is_ptr(left))
386 ret = left;
387 if (type_is_ptr(right))
388 ret = right;
390 return ret;
393 int type_signed(struct symbol *base_type)
395 if (!base_type)
396 return 0;
397 if (base_type->ctype.modifiers & MOD_SIGNED)
398 return 1;
399 return 0;
402 int expr_unsigned(struct expression *expr)
404 struct symbol *sym;
406 sym = get_type(expr);
407 if (!sym)
408 return 0;
409 if (type_unsigned(sym))
410 return 1;
411 return 0;
414 int expr_signed(struct expression *expr)
416 struct symbol *sym;
418 sym = get_type(expr);
419 if (!sym)
420 return 0;
421 if (type_signed(sym))
422 return 1;
423 return 0;
426 int returns_unsigned(struct symbol *sym)
428 if (!sym)
429 return 0;
430 sym = get_base_type(sym);
431 if (!sym || sym->type != SYM_FN)
432 return 0;
433 sym = get_base_type(sym);
434 return type_unsigned(sym);
437 int is_pointer(struct expression *expr)
439 return type_is_ptr(get_type(expr));
442 int returns_pointer(struct symbol *sym)
444 if (!sym)
445 return 0;
446 sym = get_base_type(sym);
447 if (!sym || sym->type != SYM_FN)
448 return 0;
449 sym = get_base_type(sym);
450 if (sym && sym->type == SYM_PTR)
451 return 1;
452 return 0;
455 static sval_t fp_max(struct symbol *type)
457 sval_t ret = { .type = type };
459 if (type == &float_ctype)
460 ret.fvalue = FLT_MAX;
461 else if (type == &double_ctype)
462 ret.dvalue = DBL_MAX;
463 else
464 ret.ldvalue = LDBL_MAX;
466 return ret;
469 sval_t sval_type_max(struct symbol *base_type)
471 sval_t ret;
473 if (type_is_fp(base_type))
474 return fp_max(base_type);
476 if (!base_type || !type_bits(base_type))
477 base_type = &llong_ctype;
478 ret.type = base_type;
480 ret.value = (~0ULL) >> (64 - type_positive_bits(base_type));
481 return ret;
484 static sval_t fp_min(struct symbol *type)
486 sval_t ret = { .type = type };
488 if (type == &float_ctype)
489 ret.fvalue = -FLT_MAX;
490 else if (type == &double_ctype)
491 ret.dvalue = -DBL_MAX;
492 else
493 ret.ldvalue = -LDBL_MAX;
495 return ret;
498 sval_t sval_type_min(struct symbol *base_type)
500 sval_t ret;
502 if (type_is_fp(base_type))
503 return fp_min(base_type);
505 if (!base_type || !type_bits(base_type))
506 base_type = &llong_ctype;
507 ret.type = base_type;
509 if (type_unsigned(base_type) || is_ptr_type(base_type)) {
510 ret.value = 0;
511 return ret;
514 ret.value = (~0ULL) << type_positive_bits(base_type);
516 return ret;
519 int nr_bits(struct expression *expr)
521 struct symbol *type;
523 type = get_type(expr);
524 if (!type)
525 return 0;
526 return type_bits(type);
529 int is_void_pointer(struct expression *expr)
531 struct symbol *type;
533 type = get_type(expr);
534 if (!type || type->type != SYM_PTR)
535 return 0;
536 type = get_real_base_type(type);
537 if (type == &void_ctype)
538 return 1;
539 return 0;
542 int is_char_pointer(struct expression *expr)
544 struct symbol *type;
546 type = get_type(expr);
547 if (!type || type->type != SYM_PTR)
548 return 0;
549 type = get_real_base_type(type);
550 if (type == &char_ctype)
551 return 1;
552 return 0;
555 int is_string(struct expression *expr)
557 expr = strip_expr(expr);
558 if (!expr || expr->type != EXPR_STRING)
559 return 0;
560 if (expr->string)
561 return 1;
562 return 0;
565 bool is_struct_ptr(struct symbol *type)
567 if (!type || type->type != SYM_PTR)
568 return false;
569 type = get_real_base_type(type);
570 if (!type || type->type != SYM_STRUCT)
571 return false;
572 return true;
575 int is_static(struct expression *expr)
577 char *name;
578 struct symbol *sym;
579 int ret = 0;
581 name = expr_to_str_sym(expr, &sym);
582 if (!name || !sym)
583 goto free;
585 if (sym->ctype.modifiers & MOD_STATIC)
586 ret = 1;
587 free:
588 free_string(name);
589 return ret;
592 static struct expression *get_symbol_expr(struct expression *expr)
594 if (!expr)
595 return NULL;
596 while (expr && expr->type == EXPR_DEREF && expr->op == '.')
597 expr = strip_expr(expr->deref);
598 return expr;
601 bool is_local_variable(struct expression *expr)
603 struct symbol *sym;
605 expr = get_symbol_expr(expr);
606 if (!expr || expr->type != EXPR_SYMBOL || !expr->symbol)
607 return false;
608 sym = expr->symbol;
609 if (!(sym->ctype.modifiers & MOD_TOPLEVEL))
610 return true;
611 return false;
614 int types_equiv(struct symbol *one, struct symbol *two)
616 if (!one && !two)
617 return 1;
618 if (!one || !two)
619 return 0;
620 if (one->type != two->type)
621 return 0;
622 if (one->type == SYM_PTR)
623 return types_equiv(get_real_base_type(one), get_real_base_type(two));
624 if (type_positive_bits(one) != type_positive_bits(two))
625 return 0;
626 return 1;
629 bool type_fits(struct symbol *type, struct symbol *test)
631 if (!type || !test)
632 return false;
634 if (type == test)
635 return true;
637 if (type_bits(test) > type_bits(type))
638 return false;
639 if (type_signed(test) && !type_signed(type))
640 return false;
641 if (type_positive_bits(test) > type_positive_bits(type))
642 return false;
643 return true;
646 int fn_static(void)
648 return !!(cur_func_sym->ctype.modifiers & MOD_STATIC);
651 const char *global_static(void)
653 if (cur_func_sym->ctype.modifiers & MOD_STATIC)
654 return "static";
655 else
656 return "global";
659 struct symbol *cur_func_return_type(void)
661 struct symbol *sym;
663 sym = get_real_base_type(cur_func_sym);
664 if (!sym || sym->type != SYM_FN)
665 return NULL;
666 sym = get_real_base_type(sym);
667 return sym;
670 struct symbol *get_arg_type(struct expression *fn, int arg)
672 struct symbol *fn_type;
673 struct symbol *tmp;
674 struct symbol *arg_type;
675 int i;
677 fn_type = get_type(fn);
678 if (!fn_type)
679 return NULL;
680 if (fn_type->type == SYM_PTR)
681 fn_type = get_real_base_type(fn_type);
682 if (fn_type->type != SYM_FN)
683 return NULL;
685 i = 0;
686 FOR_EACH_PTR(fn_type->arguments, tmp) {
687 arg_type = get_real_base_type(tmp);
688 if (i == arg) {
689 return arg_type;
691 i++;
692 } END_FOR_EACH_PTR(tmp);
694 return NULL;
697 static struct symbol *get_member_from_string(struct symbol_list *symbol_list, const char *name)
699 struct symbol *tmp, *sub;
700 int chunk_len;
702 if (strncmp(name, ".", 1) == 0)
703 name += 1;
704 else if (strncmp(name, "->", 2) == 0)
705 name += 2;
707 FOR_EACH_PTR(symbol_list, tmp) {
708 if (!tmp->ident) {
709 sub = get_real_base_type(tmp);
710 sub = get_member_from_string(sub->symbol_list, name);
711 if (sub)
712 return sub;
713 continue;
716 if (strcmp(tmp->ident->name, name) == 0)
717 return tmp;
719 chunk_len = tmp->ident->len;
720 if (strncmp(tmp->ident->name, name, chunk_len) == 0 &&
721 (name[chunk_len] == '.' || name[chunk_len] == '-')) {
722 sub = get_real_base_type(tmp);
723 if (sub->type == SYM_PTR)
724 sub = get_real_base_type(sub);
725 return get_member_from_string(sub->symbol_list, name + chunk_len);
728 } END_FOR_EACH_PTR(tmp);
730 return NULL;
733 static struct symbol *get_type_from_container_of_key(struct expression *expr, const char *key)
735 char *new_key;
737 expr = map_container_of_to_simpler_expr_key(expr, key, &new_key);
738 if (!expr)
739 return NULL;
740 return get_member_type_from_key(expr, new_key);
743 struct symbol *get_member_type_from_key(struct expression *expr, const char *key)
745 struct symbol *sym;
746 int star = 0;
747 int i;
749 if (strcmp(key, "$") == 0)
750 return get_type(expr);
752 if (strcmp(key, "*$") == 0) {
753 sym = get_type(expr);
754 if (!sym)
755 return NULL;
756 if (sym->type != SYM_PTR && sym->type != SYM_ARRAY)
757 return NULL;
758 return get_real_base_type(sym);
761 if (strstr(key, "<~$"))
762 return get_type_from_container_of_key(expr, key);
764 sym = get_type(expr);
765 if (!sym)
766 return NULL;
767 if (sym->type == SYM_PTR)
768 sym = get_real_base_type(sym);
770 while (*key == '*') {
771 key++;
772 star++;
775 if (*key != '$')
776 return NULL;
777 key++;
779 sym = get_member_from_string(sym->symbol_list, key);
780 if (!sym)
781 return NULL;
782 if (sym->type == SYM_RESTRICT || sym->type == SYM_NODE)
783 sym = get_real_base_type(sym);
784 for (i = 0; i < star; i++) {
785 if (!sym || sym->type != SYM_PTR)
786 return NULL;
787 sym = get_real_base_type(sym);
789 return sym;
792 struct symbol *get_arg_type_from_key(struct expression *fn, int param, struct expression *arg, const char *key)
794 struct symbol *type;
796 if (!key)
797 return NULL;
798 if (strcmp(key, "$") == 0)
799 return get_arg_type(fn, param);
800 if (strcmp(key, "*$") == 0) {
801 type = get_arg_type(fn, param);
802 if (!type || type->type != SYM_PTR)
803 return NULL;
804 return get_real_base_type(type);
806 return get_member_type_from_key(arg, key);
809 int is_struct(struct expression *expr)
811 struct symbol *type;
813 type = get_type(expr);
814 if (type && type->type == SYM_STRUCT)
815 return 1;
816 return 0;
819 static struct {
820 struct symbol *sym;
821 const char *name;
822 } base_types[] = {
823 {&bool_ctype, "bool"},
824 {&void_ctype, "void"},
825 {&type_ctype, "type"},
826 {&char_ctype, "char"},
827 {&schar_ctype, "schar"},
828 {&uchar_ctype, "uchar"},
829 {&short_ctype, "short"},
830 {&sshort_ctype, "sshort"},
831 {&ushort_ctype, "ushort"},
832 {&int_ctype, "int"},
833 {&sint_ctype, "sint"},
834 {&uint_ctype, "uint"},
835 {&long_ctype, "long"},
836 {&slong_ctype, "slong"},
837 {&ulong_ctype, "ulong"},
838 {&llong_ctype, "llong"},
839 {&sllong_ctype, "sllong"},
840 {&ullong_ctype, "ullong"},
841 {&int128_ctype, "lllong"},
842 {&sint128_ctype, "slllong"},
843 {&uint128_ctype, "ulllong"},
844 {&float_ctype, "float"},
845 {&double_ctype, "double"},
846 {&ldouble_ctype, "ldouble"},
847 {&string_ctype, "string"},
848 {&ptr_ctype, "ptr"},
849 {&lazy_ptr_ctype, "lazy_ptr"},
850 {&incomplete_ctype, "incomplete"},
851 {&label_ctype, "label"},
852 {&bad_ctype, "bad"},
853 {&null_ctype, "null"},
856 static const char *base_type_str(struct symbol *sym)
858 int i;
860 for (i = 0; i < ARRAY_SIZE(base_types); i++) {
861 if (sym == base_types[i].sym)
862 return base_types[i].name;
864 return "<unknown>";
867 static int type_str_helper(char *buf, int size, struct symbol *type)
869 int n;
871 if (!type)
872 return snprintf(buf, size, "<null type>");
874 if (type->type == SYM_BASETYPE) {
875 return snprintf(buf, size, "%s", base_type_str(type));
876 } else if (type->type == SYM_PTR) {
877 type = get_real_base_type(type);
878 n = type_str_helper(buf, size, type);
879 if (n > size)
880 return n;
881 return n + snprintf(buf + n, size - n, "*");
882 } else if (type->type == SYM_ARRAY) {
883 type = get_real_base_type(type);
884 n = type_str_helper(buf, size, type);
885 if (n > size)
886 return n;
887 return n + snprintf(buf + n, size - n, "[]");
888 } else if (type->type == SYM_STRUCT) {
889 return snprintf(buf, size, "struct %s", type->ident ? type->ident->name : "");
890 } else if (type->type == SYM_UNION) {
891 if (type->ident)
892 return snprintf(buf, size, "union %s", type->ident->name);
893 else
894 return snprintf(buf, size, "anonymous union");
895 } else if (type->type == SYM_FN) {
896 struct symbol *arg, *return_type, *arg_type;
897 int i;
899 return_type = get_real_base_type(type);
900 n = type_str_helper(buf, size, return_type);
901 if (n > size)
902 return n;
903 n += snprintf(buf + n, size - n, "(*)(");
904 if (n > size)
905 return n;
907 i = 0;
908 FOR_EACH_PTR(type->arguments, arg) {
909 if (i++)
910 n += snprintf(buf + n, size - n, ", ");
911 if (n > size)
912 return n;
913 arg_type = get_real_base_type(arg);
914 n += type_str_helper(buf + n, size - n, arg_type);
915 if (n > size)
916 return n;
917 } END_FOR_EACH_PTR(arg);
919 return n + snprintf(buf + n, size - n, ")");
920 } else if (type->type == SYM_NODE) {
921 n = snprintf(buf, size, "node {");
922 if (n > size)
923 return n;
924 type = get_real_base_type(type);
925 n += type_str_helper(buf + n, size - n, type);
926 if (n > size)
927 return n;
928 return n + snprintf(buf + n, size - n, "}");
929 } else if (type->type == SYM_ENUM) {
930 return snprintf(buf, size, "enum %s", type->ident ? type->ident->name : "<unknown>");
931 } else {
932 return snprintf(buf, size, "<type %d>", type->type);
936 char *type_to_str(struct symbol *type)
938 static char buf[256];
940 buf[0] = '\0';
941 type_str_helper(buf, sizeof(buf), type);
942 return alloc_sname(buf);