implied: add a timeout in smatch_implied.c
[smatch.git] / smatch_type.c
blob0fa617257212a9eb1a7fe5fa82e43e17da9f6c35
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 ret = get_base_type(sym);
33 if (!ret)
34 return NULL;
35 if (ret->type == SYM_RESTRICT || ret->type == SYM_NODE)
36 return get_real_base_type(ret);
37 return ret;
40 int type_bytes(struct symbol *type)
42 int bits;
44 if (type && type->type == SYM_ARRAY)
45 return array_bytes(type);
47 bits = type_bits(type);
48 if (bits < 0)
49 return 0;
50 return bits_to_bytes(bits);
53 int array_bytes(struct symbol *type)
55 if (!type || type->type != SYM_ARRAY)
56 return 0;
57 return bits_to_bytes(type->bit_size);
60 static struct symbol *get_binop_type(struct expression *expr)
62 struct symbol *left, *right;
64 left = get_type(expr->left);
65 if (!left)
66 return NULL;
68 if (expr->op == SPECIAL_LEFTSHIFT ||
69 expr->op == SPECIAL_RIGHTSHIFT) {
70 if (type_positive_bits(left) < 31)
71 return &int_ctype;
72 return left;
74 right = get_type(expr->right);
75 if (!right)
76 return NULL;
78 if (expr->op == '-' &&
79 (left->type == SYM_PTR || left->type == SYM_ARRAY) &&
80 (right->type == SYM_PTR || right->type == SYM_ARRAY))
81 return ssize_t_ctype;
83 if (left->type == SYM_PTR || left->type == SYM_ARRAY)
84 return left;
85 if (right->type == SYM_PTR || right->type == SYM_ARRAY)
86 return right;
88 if (type_positive_bits(left) < 31 && type_positive_bits(right) < 31)
89 return &int_ctype;
91 if (type_positive_bits(left) > type_positive_bits(right))
92 return left;
93 return right;
96 static struct symbol *get_type_symbol(struct expression *expr)
98 if (!expr || expr->type != EXPR_SYMBOL || !expr->symbol)
99 return NULL;
101 return get_real_base_type(expr->symbol);
104 static struct symbol *get_member_symbol(struct symbol_list *symbol_list, struct ident *member)
106 struct symbol *tmp, *sub;
108 FOR_EACH_PTR(symbol_list, tmp) {
109 if (!tmp->ident) {
110 sub = get_real_base_type(tmp);
111 sub = get_member_symbol(sub->symbol_list, member);
112 if (sub)
113 return sub;
114 continue;
116 if (tmp->ident == member)
117 return tmp;
118 } END_FOR_EACH_PTR(tmp);
120 return NULL;
123 static struct symbol *get_symbol_from_deref(struct expression *expr)
125 struct ident *member;
126 struct symbol *sym;
128 if (!expr || expr->type != EXPR_DEREF)
129 return NULL;
131 member = expr->member;
132 sym = get_type(expr->deref);
133 if (!sym) {
134 // sm_msg("could not find struct type");
135 return NULL;
137 if (sym->type == SYM_PTR)
138 sym = get_real_base_type(sym);
139 sym = get_member_symbol(sym->symbol_list, member);
140 if (!sym)
141 return NULL;
142 return get_real_base_type(sym);
145 static struct symbol *get_return_type(struct expression *expr)
147 struct symbol *tmp;
149 tmp = get_type(expr->fn);
150 if (!tmp)
151 return NULL;
152 /* this is to handle __builtin_constant_p() */
153 if (tmp->type != SYM_FN)
154 tmp = get_base_type(tmp);
155 return get_real_base_type(tmp);
158 static struct symbol *get_expr_stmt_type(struct statement *stmt)
160 if (stmt->type != STMT_COMPOUND)
161 return NULL;
162 stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
163 if (stmt->type == STMT_LABEL)
164 stmt = stmt->label_statement;
165 if (stmt->type != STMT_EXPRESSION)
166 return NULL;
167 return get_type(stmt->expression);
170 static struct symbol *get_select_type(struct expression *expr)
172 struct symbol *one, *two;
174 one = get_type(expr->cond_true);
175 two = get_type(expr->cond_false);
176 if (!one || !two)
177 return NULL;
179 * This is a hack. If the types are not equiv then we
180 * really don't know the type. But I think guessing is
181 * probably Ok here.
183 if (type_positive_bits(one) > type_positive_bits(two))
184 return one;
185 return two;
188 struct symbol *get_pointer_type(struct expression *expr)
190 struct symbol *sym;
192 sym = get_type(expr);
193 if (!sym)
194 return NULL;
195 if (sym->type == SYM_NODE) {
196 sym = get_real_base_type(sym);
197 if (!sym)
198 return NULL;
200 if (sym->type != SYM_PTR && sym->type != SYM_ARRAY)
201 return NULL;
202 return get_real_base_type(sym);
205 static struct symbol *fake_pointer_sym(struct expression *expr)
207 struct symbol *sym;
208 struct symbol *base;
210 sym = alloc_symbol(expr->pos, SYM_PTR);
211 expr = expr->unop;
212 base = get_type(expr);
213 if (!base)
214 return NULL;
215 sym->ctype.base_type = base;
216 return sym;
219 struct symbol *get_type(struct expression *expr)
221 struct symbol *ret;
223 expr = strip_parens(expr);
224 if (!expr)
225 return NULL;
227 if (expr->ctype)
228 return expr->ctype;
230 switch (expr->type) {
231 case EXPR_STRING:
232 ret = &string_ctype;
233 break;
234 case EXPR_SYMBOL:
235 ret = get_type_symbol(expr);
236 break;
237 case EXPR_DEREF:
238 ret = get_symbol_from_deref(expr);
239 break;
240 case EXPR_PREOP:
241 case EXPR_POSTOP:
242 if (expr->op == '&')
243 ret = fake_pointer_sym(expr);
244 else if (expr->op == '*')
245 ret = get_pointer_type(expr->unop);
246 else
247 ret = get_type(expr->unop);
248 break;
249 case EXPR_ASSIGNMENT:
250 ret = get_type(expr->left);
251 break;
252 case EXPR_CAST:
253 case EXPR_FORCE_CAST:
254 case EXPR_IMPLIED_CAST:
255 ret = get_real_base_type(expr->cast_type);
256 break;
257 case EXPR_COMPARE:
258 case EXPR_BINOP:
259 ret = get_binop_type(expr);
260 break;
261 case EXPR_CALL:
262 ret = get_return_type(expr);
263 break;
264 case EXPR_STATEMENT:
265 ret = get_expr_stmt_type(expr->statement);
266 break;
267 case EXPR_CONDITIONAL:
268 case EXPR_SELECT:
269 ret = get_select_type(expr);
270 break;
271 case EXPR_SIZEOF:
272 ret = &ulong_ctype;
273 break;
274 case EXPR_LOGICAL:
275 ret = &int_ctype;
276 break;
277 default:
278 return NULL;
281 if (ret && ret->type == SYM_TYPEOF)
282 ret = get_type(ret->initializer);
284 expr->ctype = ret;
285 return ret;
288 int type_signed(struct symbol *base_type)
290 if (!base_type)
291 return 0;
292 if (base_type->ctype.modifiers & MOD_SIGNED)
293 return 1;
294 return 0;
297 int expr_unsigned(struct expression *expr)
299 struct symbol *sym;
301 sym = get_type(expr);
302 if (!sym)
303 return 0;
304 if (type_unsigned(sym))
305 return 1;
306 return 0;
309 int expr_signed(struct expression *expr)
311 struct symbol *sym;
313 sym = get_type(expr);
314 if (!sym)
315 return 0;
316 if (type_signed(sym))
317 return 1;
318 return 0;
321 int returns_unsigned(struct symbol *sym)
323 if (!sym)
324 return 0;
325 sym = get_base_type(sym);
326 if (!sym || sym->type != SYM_FN)
327 return 0;
328 sym = get_base_type(sym);
329 return type_unsigned(sym);
332 int is_pointer(struct expression *expr)
334 struct symbol *sym;
336 sym = get_type(expr);
337 if (!sym)
338 return 0;
339 if (sym == &string_ctype)
340 return 0;
341 if (sym->type == SYM_PTR)
342 return 1;
343 return 0;
346 int returns_pointer(struct symbol *sym)
348 if (!sym)
349 return 0;
350 sym = get_base_type(sym);
351 if (!sym || sym->type != SYM_FN)
352 return 0;
353 sym = get_base_type(sym);
354 if (sym->type == SYM_PTR)
355 return 1;
356 return 0;
359 sval_t sval_type_max(struct symbol *base_type)
361 sval_t ret;
363 if (!base_type || !type_bits(base_type))
364 base_type = &llong_ctype;
365 ret.type = base_type;
367 ret.value = (~0ULL) >> (64 - type_positive_bits(base_type));
368 return ret;
371 sval_t sval_type_min(struct symbol *base_type)
373 sval_t ret;
375 if (!base_type || !type_bits(base_type))
376 base_type = &llong_ctype;
377 ret.type = base_type;
379 if (type_unsigned(base_type)) {
380 ret.value = 0;
381 return ret;
384 ret.value = (~0ULL) << type_positive_bits(base_type);
386 return ret;
389 int nr_bits(struct expression *expr)
391 struct symbol *type;
393 type = get_type(expr);
394 if (!type)
395 return 0;
396 return type_bits(type);
399 int is_void_pointer(struct expression *expr)
401 struct symbol *type;
403 type = get_type(expr);
404 if (!type || type->type != SYM_PTR)
405 return 0;
406 type = get_real_base_type(type);
407 if (type == &void_ctype)
408 return 1;
409 return 0;
412 int is_char_pointer(struct expression *expr)
414 struct symbol *type;
416 type = get_type(expr);
417 if (!type || type->type != SYM_PTR)
418 return 0;
419 type = get_real_base_type(type);
420 if (type == &char_ctype)
421 return 1;
422 return 0;
425 int is_string(struct expression *expr)
427 expr = strip_expr(expr);
428 if (!expr || expr->type != EXPR_STRING)
429 return 0;
430 if (expr->string)
431 return 1;
432 return 0;
435 int is_static(struct expression *expr)
437 char *name;
438 struct symbol *sym;
439 int ret = 0;
441 name = expr_to_str_sym(expr, &sym);
442 if (!name || !sym)
443 goto free;
445 if (sym->ctype.modifiers & MOD_STATIC)
446 ret = 1;
447 free:
448 free_string(name);
449 return ret;
452 int is_local_variable(struct expression *expr)
454 struct symbol *sym;
455 char *name;
457 name = expr_to_var_sym(expr, &sym);
458 free_string(name);
459 if (!sym || !sym->scope || !sym->scope->token || !cur_func_sym)
460 return 0;
461 if (cmp_pos(sym->scope->token->pos, cur_func_sym->pos) < 0)
462 return 0;
463 if (is_static(expr))
464 return 0;
465 return 1;
468 int types_equiv(struct symbol *one, struct symbol *two)
470 if (!one && !two)
471 return 1;
472 if (!one || !two)
473 return 0;
474 if (one->type != two->type)
475 return 0;
476 if (one->type == SYM_PTR)
477 return types_equiv(get_real_base_type(one), get_real_base_type(two));
478 if (type_positive_bits(one) != type_positive_bits(two))
479 return 0;
480 return 1;
483 int fn_static(void)
485 return !!(cur_func_sym->ctype.modifiers & MOD_STATIC);
488 const char *global_static(void)
490 if (cur_func_sym->ctype.modifiers & MOD_STATIC)
491 return "static";
492 else
493 return "global";
496 struct symbol *cur_func_return_type(void)
498 struct symbol *sym;
500 sym = get_real_base_type(cur_func_sym);
501 if (!sym || sym->type != SYM_FN)
502 return NULL;
503 sym = get_real_base_type(sym);
504 return sym;
507 struct symbol *get_arg_type(struct expression *fn, int arg)
509 struct symbol *fn_type;
510 struct symbol *tmp;
511 struct symbol *arg_type;
512 int i;
514 fn_type = get_type(fn);
515 if (!fn_type)
516 return NULL;
517 if (fn_type->type == SYM_PTR)
518 fn_type = get_real_base_type(fn_type);
519 if (fn_type->type != SYM_FN)
520 return NULL;
522 i = 0;
523 FOR_EACH_PTR(fn_type->arguments, tmp) {
524 arg_type = get_real_base_type(tmp);
525 if (i == arg) {
526 return arg_type;
528 i++;
529 } END_FOR_EACH_PTR(tmp);
531 return NULL;
534 static struct symbol *get_member_from_string(struct symbol_list *symbol_list, char *name)
536 struct symbol *tmp, *sub;
537 int chunk_len;
539 if (strncmp(name, ".", 1) == 0)
540 name += 1;
541 if (strncmp(name, "->", 2) == 0)
542 name += 2;
544 FOR_EACH_PTR(symbol_list, tmp) {
545 if (!tmp->ident) {
546 sub = get_real_base_type(tmp);
547 sub = get_member_from_string(sub->symbol_list, name);
548 if (sub)
549 return sub;
550 continue;
553 if (strcmp(tmp->ident->name, name) == 0)
554 return tmp;
556 chunk_len = strlen(tmp->ident->name);
557 if (strncmp(tmp->ident->name, name, chunk_len) == 0 &&
558 (name[chunk_len] == '.' || name[chunk_len] == '-')) {
559 sub = get_real_base_type(tmp);
560 return get_member_from_string(sub->symbol_list, name + chunk_len);
563 } END_FOR_EACH_PTR(tmp);
565 return NULL;
568 struct symbol *get_member_type_from_key(struct expression *expr, char *key)
570 struct symbol *sym;
572 if (strcmp(key, "$") == 0)
573 return get_type(expr);
575 if (strcmp(key, "*$") == 0) {
576 sym = get_type(expr);
577 if (!sym || sym->type != SYM_PTR)
578 return NULL;
579 return get_real_base_type(sym);
582 sym = get_type(expr);
583 if (!sym)
584 return NULL;
585 if (sym->type == SYM_PTR)
586 sym = get_real_base_type(sym);
588 key = key + 1;
589 sym = get_member_from_string(sym->symbol_list, key);
590 if (!sym)
591 return NULL;
592 return get_real_base_type(sym);
595 int is_struct(struct expression *expr)
597 struct symbol *type;
599 type = get_type(expr);
600 if (type && type->type == SYM_STRUCT)
601 return 1;
602 return 0;
605 static struct {
606 struct symbol *sym;
607 const char *name;
608 } base_types[] = {
609 {&bool_ctype, "bool"},
610 {&void_ctype, "void"},
611 {&type_ctype, "type"},
612 {&char_ctype, "char"},
613 {&schar_ctype, "schar"},
614 {&uchar_ctype, "uchar"},
615 {&short_ctype, "short"},
616 {&sshort_ctype, "sshort"},
617 {&ushort_ctype, "ushort"},
618 {&int_ctype, "int"},
619 {&sint_ctype, "sint"},
620 {&uint_ctype, "uint"},
621 {&long_ctype, "long"},
622 {&slong_ctype, "slong"},
623 {&ulong_ctype, "ulong"},
624 {&llong_ctype, "llong"},
625 {&sllong_ctype, "sllong"},
626 {&ullong_ctype, "ullong"},
627 {&lllong_ctype, "lllong"},
628 {&slllong_ctype, "slllong"},
629 {&ulllong_ctype, "ulllong"},
630 {&float_ctype, "float"},
631 {&double_ctype, "double"},
632 {&ldouble_ctype, "ldouble"},
633 {&string_ctype, "string"},
634 {&ptr_ctype, "ptr"},
635 {&lazy_ptr_ctype, "lazy_ptr"},
636 {&incomplete_ctype, "incomplete"},
637 {&label_ctype, "label"},
638 {&bad_ctype, "bad"},
639 {&null_ctype, "null"},
642 static const char *base_type_str(struct symbol *sym)
644 int i;
646 for (i = 0; i < ARRAY_SIZE(base_types); i++) {
647 if (sym == base_types[i].sym)
648 return base_types[i].name;
650 return "<unknown>";
653 static int type_str_helper(char *buf, int size, struct symbol *type)
655 int n;
657 if (!type)
658 return snprintf(buf, size, "<unknown>");
660 if (type->type == SYM_BASETYPE) {
661 return snprintf(buf, size, base_type_str(type));
662 } else if (type->type == SYM_PTR) {
663 type = get_real_base_type(type);
664 n = type_str_helper(buf, size, type);
665 if (n > size)
666 return n;
667 return n + snprintf(buf + n, size - n, "*");
668 } else if (type->type == SYM_ARRAY) {
669 type = get_real_base_type(type);
670 n = type_str_helper(buf, size, type);
671 if (n > size)
672 return n;
673 return n + snprintf(buf + n, size - n, "[]");
674 } else if (type->type == SYM_STRUCT) {
675 return snprintf(buf, size, "struct %s", type->ident ? type->ident->name : "");
676 } else if (type->type == SYM_UNION) {
677 if (type->ident)
678 return snprintf(buf, size, "union %s", type->ident->name);
679 else
680 return snprintf(buf, size, "anonymous union");
681 } else if (type->type == SYM_FN) {
682 struct symbol *arg, *return_type, *arg_type;
683 int i;
685 return_type = get_real_base_type(type);
686 n = type_str_helper(buf, size, return_type);
687 if (n > size)
688 return n;
689 n += snprintf(buf + n, size - n, "(*)(");
690 if (n > size)
691 return n;
693 i = 0;
694 FOR_EACH_PTR(type->arguments, arg) {
695 if (i++)
696 n += snprintf(buf + n, size - n, ", ");
697 if (n > size)
698 return n;
699 arg_type = get_real_base_type(arg);
700 n += type_str_helper(buf + n, size - n, arg_type);
701 if (n > size)
702 return n;
703 } END_FOR_EACH_PTR(arg);
705 return n + snprintf(buf + n, size - n, ")");
706 } else if (type->type == SYM_NODE) {
707 n = snprintf(buf, size, "node {");
708 if (n > size)
709 return n;
710 type = get_real_base_type(type);
711 n += type_str_helper(buf + n, size - n, type);
712 if (n > size)
713 return n;
714 return n + snprintf(buf + n, size - n, "}");
715 } else {
716 return snprintf(buf, size, "<type %d>", type->type);
720 char *type_to_str(struct symbol *type)
722 static char buf[256];
724 buf[0] = '\0';
725 type_str_helper(buf, sizeof(buf), type);
726 return buf;