flow, conditions: handle label statements correctly
[smatch.git] / smatch_helper.c
blob17adb1a8097dab2a1d0c9038ca0bc546977416e2
1 /*
2 * Copyright (C) 2006 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 * Miscellaneous helper functions.
22 #include <stdlib.h>
23 #include <stdio.h>
24 #include "allocate.h"
25 #include "smatch.h"
26 #include "smatch_extra.h"
28 #define VAR_LEN 512
30 char *alloc_string(const char *str)
32 char *tmp;
34 if (!str)
35 return NULL;
36 tmp = malloc(strlen(str) + 1);
37 strcpy(tmp, str);
38 return tmp;
41 void free_string(char *str)
43 free(str);
46 void remove_parens(char *str)
48 char *src, *dst;
50 dst = src = str;
51 while (*src != '\0') {
52 if (*src == '(' || *src == ')') {
53 src++;
54 continue;
56 *dst++ = *src++;
58 *dst = *src;
61 struct smatch_state *alloc_state_num(int num)
63 struct smatch_state *state;
64 static char buff[256];
66 state = __alloc_smatch_state(0);
67 snprintf(buff, 255, "%d", num);
68 buff[255] = '\0';
69 state->name = alloc_string(buff);
70 state->data = INT_PTR(num);
71 return state;
74 struct smatch_state *alloc_state_str(const char *name)
76 struct smatch_state *state;
78 state = __alloc_smatch_state(0);
79 state->name = alloc_string(name);
80 return state;
83 void append(char *dest, const char *data, int buff_len)
85 strncat(dest, data, buff_len - strlen(dest) - 1);
89 * If you have "foo(a, b, 1);" then use
90 * get_argument_from_call_expr(expr, 0) to return the expression for
91 * a. Yes, it does start counting from 0.
93 struct expression *get_argument_from_call_expr(struct expression_list *args,
94 int num)
96 struct expression *expr;
97 int i = 0;
99 if (!args)
100 return NULL;
102 FOR_EACH_PTR(args, expr) {
103 if (i == num)
104 return expr;
105 i++;
106 } END_FOR_EACH_PTR(expr);
107 return NULL;
110 static struct expression *get_array_expr(struct expression *expr)
112 struct symbol *type;
114 if (expr->type != EXPR_BINOP || expr->op != '+')
115 return NULL;
117 type = get_type(expr->left);
118 if (!type || type->type != SYM_ARRAY)
119 return NULL;
120 return expr->left;
123 static void __get_variable_from_expr(struct symbol **sym_ptr, char *buf,
124 struct expression *expr, int len,
125 int *complicated, int no_parens)
127 switch (expr->type) {
128 case EXPR_DEREF: {
129 struct expression *deref;
130 int op;
132 deref = expr->deref;
133 op = deref->op;
134 if (op == '*') {
135 struct expression *unop = strip_expr(deref->unop);
137 if (unop->type == EXPR_PREOP && unop->op == '&') {
138 deref = unop->unop;
139 op = '.';
140 } else {
141 deref = deref->unop;
145 __get_variable_from_expr(sym_ptr, buf, deref, len, complicated, no_parens);
147 if (op == '*')
148 append(buf, "->", len);
149 else
150 append(buf, ".", len);
152 if (expr->member)
153 append(buf, expr->member->name, len);
154 else
155 append(buf, "unknown_member", len);
157 return;
159 case EXPR_SYMBOL:
160 if (expr->symbol_name)
161 append(buf, expr->symbol_name->name, len);
162 if (sym_ptr) {
163 if (*sym_ptr)
164 *complicated = 1;
165 *sym_ptr = expr->symbol;
167 return;
168 case EXPR_PREOP: {
169 const char *tmp;
171 if (get_expression_statement(expr)) {
172 *complicated = 2;
173 return;
176 if (expr->op == '(') {
177 if (!no_parens)
178 append(buf, "(", len);
179 } else if (expr->op != '*' || !get_array_expr(expr->unop)) {
180 tmp = show_special(expr->op);
181 append(buf, tmp, len);
183 __get_variable_from_expr(sym_ptr, buf, expr->unop,
184 len, complicated, no_parens);
186 if (expr->op == '(' && !no_parens)
187 append(buf, ")", len);
189 if (expr->op == SPECIAL_DECREMENT ||
190 expr->op == SPECIAL_INCREMENT)
191 *complicated = 1;
193 return;
195 case EXPR_POSTOP: {
196 const char *tmp;
198 __get_variable_from_expr(sym_ptr, buf, expr->unop,
199 len, complicated, no_parens);
200 tmp = show_special(expr->op);
201 append(buf, tmp, len);
203 if (expr->op == SPECIAL_DECREMENT || expr->op == SPECIAL_INCREMENT)
204 *complicated = 1;
205 return;
207 case EXPR_ASSIGNMENT:
208 case EXPR_COMPARE:
209 case EXPR_LOGICAL:
210 case EXPR_BINOP: {
211 char tmp[10];
212 struct expression *array_expr;
214 *complicated = 1;
215 array_expr = get_array_expr(expr);
216 if (array_expr) {
217 __get_variable_from_expr(sym_ptr, buf, array_expr, len, complicated, no_parens);
218 append(buf, "[", len);
219 } else {
220 __get_variable_from_expr(sym_ptr, buf, expr->left, len, complicated, no_parens);
221 snprintf(tmp, sizeof(tmp), " %s ", show_special(expr->op));
222 append(buf, tmp, len);
224 __get_variable_from_expr(NULL, buf, expr->right, len, complicated, no_parens);
225 if (array_expr)
226 append(buf, "]", len);
227 return;
229 case EXPR_VALUE: {
230 char tmp[25];
232 *complicated = 1;
233 snprintf(tmp, 25, "%lld", expr->value);
234 append(buf, tmp, len);
235 return;
237 case EXPR_STRING:
238 append(buf, "\"", len);
239 if (expr->string)
240 append(buf, expr->string->data, len);
241 append(buf, "\"", len);
242 return;
243 case EXPR_CALL: {
244 struct expression *tmp;
245 int i;
247 *complicated = 1;
248 __get_variable_from_expr(NULL, buf, expr->fn, len, complicated, no_parens);
249 append(buf, "(", len);
250 i = 0;
251 FOR_EACH_PTR(expr->args, tmp) {
252 if (i++)
253 append(buf, ", ", len);
254 __get_variable_from_expr(NULL, buf, tmp, len, complicated, no_parens);
255 } END_FOR_EACH_PTR(tmp);
256 append(buf, ")", len);
257 return;
259 case EXPR_CAST:
260 case EXPR_FORCE_CAST:
261 __get_variable_from_expr(sym_ptr, buf,
262 expr->cast_expression, len,
263 complicated, no_parens);
264 return;
265 case EXPR_SIZEOF: {
266 int size;
267 char tmp[25];
269 if (expr->cast_type && get_base_type(expr->cast_type)) {
270 size = type_bytes(get_base_type(expr->cast_type));
271 snprintf(tmp, 25, "%d", size);
272 append(buf, tmp, len);
274 return;
276 case EXPR_IDENTIFIER:
277 *complicated = 1;
278 if (expr->expr_ident)
279 append(buf, expr->expr_ident->name, len);
280 return;
281 default:
282 *complicated = 1;
283 //printf("unknown type = %d\n", expr->type);
284 return;
289 * This is returns a stylized "c looking" representation of the
290 * variable name.
292 * It uses the same buffer every time so you have to save the result
293 * yourself if you want to keep it.
297 char *expr_to_str_sym(struct expression *expr, struct symbol **sym_ptr)
299 static char var_name[VAR_LEN];
300 int complicated = 0;
302 if (sym_ptr)
303 *sym_ptr = NULL;
304 var_name[0] = '\0';
306 if (!expr)
307 return NULL;
308 __get_variable_from_expr(sym_ptr, var_name, expr, sizeof(var_name),
309 &complicated, 0);
310 if (complicated < 2)
311 return alloc_string(var_name);
312 else
313 return NULL;
316 char *expr_to_str(struct expression *expr)
318 return expr_to_str_sym(expr, NULL);
322 * get_variable_from_expr_simple() only returns simple variables.
323 * If it's a complicated variable like a->foo[x] instead of just 'a->foo'
324 * then it returns NULL.
326 char *expr_to_var_sym(struct expression *expr,
327 struct symbol **sym_ptr)
329 static char var_name[VAR_LEN];
330 int complicated = 0;
332 if (sym_ptr)
333 *sym_ptr = NULL;
334 var_name[0] = '\0';
336 if (!expr)
337 return NULL;
338 expr = strip_expr(expr);
339 __get_variable_from_expr(sym_ptr, var_name, expr, sizeof(var_name),
340 &complicated, 1);
342 if (complicated) {
343 if (sym_ptr)
344 *sym_ptr = NULL;
345 return NULL;
347 return alloc_string(var_name);
350 char *expr_to_var(struct expression *expr)
352 return expr_to_var_sym(expr, NULL);
355 struct symbol *expr_to_sym(struct expression *expr)
357 struct symbol *sym;
358 char *name;
360 name = expr_to_var_sym(expr, &sym);
361 free_string(name);
362 return sym;
365 int get_complication_score(struct expression *expr)
367 int score = 0;
369 expr = strip_expr(expr);
372 * Don't forget to keep get_complication_score() and store_all_links()
373 * in sync.
377 switch (expr->type) {
378 case EXPR_CALL:
379 return 999;
380 case EXPR_COMPARE:
381 case EXPR_BINOP:
382 score += get_complication_score(expr->left);
383 score += get_complication_score(expr->right);
384 return score;
385 case EXPR_SYMBOL:
386 if (is_local_variable(expr))
387 return 1;
388 return 999;
389 case EXPR_PREOP:
390 if (expr->op == '*')
391 return score + get_complication_score(expr->unop);
392 return 999;
393 case EXPR_DEREF:
394 return score + get_complication_score(expr->deref);
395 case EXPR_VALUE:
396 return 0;
397 default:
398 return 999;
402 char *expr_to_chunk_helper(struct expression *expr, struct symbol **sym, struct var_sym_list **vsl)
404 char *name;
405 struct symbol *tmp;
406 int score;
408 if (vsl)
409 *vsl = NULL;
410 if (sym)
411 *sym = NULL;
413 expr = strip_parens(expr);
414 if (!expr)
415 return NULL;
417 name = expr_to_var_sym(expr, &tmp);
418 if (name && tmp) {
419 if (sym)
420 *sym = tmp;
421 if (vsl)
422 *vsl = expr_to_vsl(expr);
423 return name;
425 free_string(name);
427 score = get_complication_score(expr);
428 if (score <= 0 || score > 2)
429 return NULL;
431 if (vsl) {
432 *vsl = expr_to_vsl(expr);
433 if (!*vsl)
434 return NULL;
437 return expr_to_str(expr);
440 char *expr_to_known_chunk_sym(struct expression *expr, struct symbol **sym)
442 return expr_to_chunk_helper(expr, sym, NULL);
445 char *expr_to_chunk_sym_vsl(struct expression *expr, struct symbol **sym, struct var_sym_list **vsl)
447 return expr_to_chunk_helper(expr, sym, vsl);
450 int sym_name_is(const char *name, struct expression *expr)
452 if (!expr)
453 return 0;
454 if (expr->type != EXPR_SYMBOL)
455 return 0;
456 if (!strcmp(expr->symbol_name->name, name))
457 return 1;
458 return 0;
461 int is_zero(struct expression *expr)
463 sval_t sval;
465 if (get_value(expr, &sval) && sval.value == 0)
466 return 1;
467 return 0;
470 int is_array(struct expression *expr)
472 struct symbol *type;
474 expr = strip_expr(expr);
475 if (!expr)
476 return 0;
478 if (expr->type == EXPR_PREOP && expr->op == '*') {
479 expr = strip_expr(expr->unop);
480 if (expr->type == EXPR_BINOP && expr->op == '+')
481 return 1;
484 if (expr->type != EXPR_BINOP || expr->op != '+')
485 return 0;
487 type = get_type(expr->left);
488 if (!type || type->type != SYM_ARRAY)
489 return 0;
491 return 1;
494 struct expression *get_array_base(struct expression *expr)
496 if (!is_array(expr))
497 return NULL;
498 expr = strip_expr(expr);
499 if (expr->type == EXPR_PREOP && expr->op == '*')
500 expr = strip_expr(expr->unop);
501 if (expr->type != EXPR_BINOP || expr->op != '+')
502 return NULL;
503 return strip_parens(expr->left);
506 struct expression *get_array_offset(struct expression *expr)
508 if (!is_array(expr))
509 return NULL;
510 expr = strip_expr(expr);
511 if (expr->type == EXPR_PREOP && expr->op == '*')
512 expr = strip_expr(expr->unop);
513 if (expr->type != EXPR_BINOP || expr->op != '+')
514 return NULL;
515 return strip_parens(expr->right);
518 const char *show_state(struct smatch_state *state)
520 if (!state)
521 return NULL;
522 return state->name;
525 struct statement *get_expression_statement(struct expression *expr)
527 /* What are those things called? if (({....; ret;})) { ...*/
529 if (expr->type != EXPR_PREOP)
530 return NULL;
531 if (expr->op != '(')
532 return NULL;
533 if (expr->unop->type != EXPR_STATEMENT)
534 return NULL;
535 if (expr->unop->statement->type != STMT_COMPOUND)
536 return NULL;
537 return expr->unop->statement;
540 struct expression *strip_parens(struct expression *expr)
542 if (!expr)
543 return NULL;
545 if (expr->type == EXPR_PREOP) {
546 if (expr->op == '(' && expr->unop->type == EXPR_STATEMENT &&
547 expr->unop->statement->type == STMT_COMPOUND)
548 return expr;
549 if (expr->op == '(')
550 return strip_parens(expr->unop);
552 return expr;
555 struct expression *strip_expr(struct expression *expr)
557 if (!expr)
558 return NULL;
560 switch (expr->type) {
561 case EXPR_FORCE_CAST:
562 case EXPR_CAST:
563 return strip_expr(expr->cast_expression);
564 case EXPR_PREOP: {
565 struct expression *unop;
567 if (expr->op == '(' && expr->unop->type == EXPR_STATEMENT &&
568 expr->unop->statement->type == STMT_COMPOUND)
569 return expr;
571 unop = strip_expr(expr->unop);
573 if (expr->op == '*' &&
574 unop->type == EXPR_PREOP && unop->op == '&') {
575 struct symbol *type = get_type(unop->unop);
577 if (type && type->type == SYM_ARRAY)
578 return expr;
579 return strip_expr(unop->unop);
582 if (expr->op == '(')
583 return unop;
585 return expr;
587 case EXPR_CONDITIONAL:
588 if (known_condition_true(expr->conditional)) {
589 if (expr->cond_true)
590 return strip_expr(expr->cond_true);
591 return strip_expr(expr->conditional);
593 if (known_condition_false(expr->conditional))
594 return strip_expr(expr->cond_false);
595 return expr;
596 case EXPR_CALL:
597 if (sym_name_is("__builtin_expect", expr->fn)) {
598 expr = get_argument_from_call_expr(expr->args, 0);
599 return strip_expr(expr);
601 return expr;
603 return expr;
606 static void delete_state_tracker(struct tracker *t)
608 delete_state(t->owner, t->name, t->sym);
609 __free_tracker(t);
612 void scoped_state(int my_id, const char *name, struct symbol *sym)
614 struct tracker *t;
616 t = alloc_tracker(my_id, name, sym);
617 add_scope_hook((scope_hook *)&delete_state_tracker, t);
620 int is_error_return(struct expression *expr)
622 struct symbol *cur_func = cur_func_sym;
623 sval_t sval;
625 if (!expr)
626 return 0;
627 if (cur_func->type != SYM_NODE)
628 return 0;
629 cur_func = get_base_type(cur_func);
630 if (cur_func->type != SYM_FN)
631 return 0;
632 cur_func = get_base_type(cur_func);
633 if (cur_func == &void_ctype)
634 return 0;
635 if (!get_implied_value(expr, &sval))
636 return 0;
637 if (sval.value < 0)
638 return 1;
639 if (cur_func->type == SYM_PTR && sval.value == 0)
640 return 1;
641 return 0;
644 int getting_address(void)
646 struct expression *tmp;
647 int i = 0;
648 int dot_ops = 0;
650 FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
651 if (!i++)
652 continue;
653 if (tmp->type == EXPR_PREOP && tmp->op == '(')
654 continue;
655 if (tmp->op == '.' && !dot_ops++)
656 continue;
657 if (tmp->op == '&')
658 return 1;
659 return 0;
660 } END_FOR_EACH_PTR_REVERSE(tmp);
661 return 0;
664 char *get_member_name(struct expression *expr)
666 char buf[256];
667 struct symbol *sym;
669 expr = strip_expr(expr);
670 if (expr->type != EXPR_DEREF)
671 return NULL;
672 if (!expr->member)
673 return NULL;
675 sym = get_type(expr->deref);
676 if (!sym)
677 return NULL;
678 if (sym->type == SYM_UNION) {
679 sym = expr_to_sym(expr->deref);
680 sym = get_real_base_type(sym);
681 if (sym && sym->type == SYM_PTR)
682 sym = get_real_base_type(sym);
683 if (!sym || !sym->ident) {
684 snprintf(buf, sizeof(buf), "(union hack)->%s", expr->member->name);
685 return alloc_string(buf);
688 if (!sym->ident)
689 return NULL;
690 snprintf(buf, sizeof(buf), "(struct %s)->%s", sym->ident->name, expr->member->name);
691 return alloc_string(buf);
694 int cmp_pos(struct position pos1, struct position pos2)
696 /* the stream position is ... */
697 if (pos1.stream > pos2.stream)
698 return -1;
699 if (pos1.stream < pos2.stream)
700 return 1;
702 if (pos1.line < pos2.line)
703 return -1;
704 if (pos1.line > pos2.line)
705 return 1;
707 if (pos1.pos < pos2.pos)
708 return -1;
709 if (pos1.pos > pos2.pos)
710 return 1;
712 return 0;
715 int positions_eq(struct position pos1, struct position pos2)
717 if (pos1.line != pos2.line)
718 return 0;
719 if (pos1.pos != pos2.pos)
720 return 0;
721 if (pos1.stream != pos2.stream)
722 return 0;
723 return 1;
726 struct statement *get_current_statement(void)
728 struct statement *prev, *tmp;
730 prev = last_ptr_list((struct ptr_list *)big_statement_stack);
732 if (!prev || !get_macro_name(prev->pos))
733 return prev;
735 FOR_EACH_PTR_REVERSE(big_statement_stack, tmp) {
736 if (positions_eq(tmp->pos, prev->pos))
737 continue;
738 if (prev->pos.line > tmp->pos.line)
739 return prev;
740 return tmp;
741 } END_FOR_EACH_PTR_REVERSE(tmp);
742 return prev;
745 struct statement *get_prev_statement(void)
747 struct statement *tmp;
748 int i;
750 i = 0;
751 FOR_EACH_PTR_REVERSE(big_statement_stack, tmp) {
752 if (i++ == 1)
753 return tmp;
754 } END_FOR_EACH_PTR_REVERSE(tmp);
755 return NULL;
758 int get_param_num_from_sym(struct symbol *sym)
760 struct symbol *tmp;
761 int i;
763 if (!cur_func_sym)
764 return -1;
766 i = 0;
767 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, tmp) {
768 if (tmp == sym)
769 return i;
770 i++;
771 } END_FOR_EACH_PTR(tmp);
772 return -1;
775 int get_param_num(struct expression *expr)
777 struct symbol *sym;
778 char *name;
780 if (!cur_func_sym)
781 return -1;
782 name = expr_to_var_sym(expr, &sym);
783 free_string(name);
784 if (!sym)
785 return -1;
786 return get_param_num_from_sym(sym);
789 int ms_since(struct timeval *start)
791 struct timeval end;
792 double diff;
794 gettimeofday(&end, NULL);
795 diff = (end.tv_sec - start->tv_sec) * 1000.0;
796 diff += (end.tv_usec - start->tv_usec) / 1000.0;
797 return (int)diff;
800 int parent_is_gone_var_sym(const char *name, struct symbol *sym)
802 if (!name || !sym)
803 return 0;
805 if (parent_is_null_var_sym(name, sym) ||
806 parent_is_free_var_sym(name, sym))
807 return 1;
808 return 0;
811 int parent_is_gone(struct expression *expr)
813 struct symbol *sym;
814 char *var;
815 int ret = 0;
817 expr = strip_expr(expr);
818 var = expr_to_var_sym(expr, &sym);
819 if (!var || !sym)
820 goto free;
821 ret = parent_is_gone_var_sym(var, sym);
822 free:
823 free_string(var);
824 return ret;
827 int invert_op(int op)
829 switch (op) {
830 case '*':
831 return '/';
832 case '/':
833 return '*';
834 case '+':
835 return '-';
836 case '-':
837 return '+';
838 case SPECIAL_LEFTSHIFT:
839 return SPECIAL_RIGHTSHIFT;
840 case SPECIAL_RIGHTSHIFT:
841 return SPECIAL_LEFTSHIFT;
843 return 0;
846 int expr_equiv(struct expression *one, struct expression *two)
848 struct symbol *one_sym, *two_sym;
849 char *one_name = NULL;
850 char *two_name = NULL;
851 int ret = 0;
853 if (!one || !two)
854 return 0;
855 if (one->type != two->type)
856 return 0;
858 one_name = expr_to_str_sym(one, &one_sym);
859 if (!one_name || !one_sym)
860 goto free;
861 two_name = expr_to_str_sym(two, &two_sym);
862 if (!two_name || !two_sym)
863 goto free;
864 if (one_sym != two_sym)
865 goto free;
866 if (strcmp(one_name, two_name) == 0)
867 ret = 1;
868 free:
869 free_string(one_name);
870 free_string(two_name);
871 return ret;