implied: re-order where we calculate implications
[smatch.git] / smatch_helper.c
blobc598977d02e98314144650e66389daa01c0ca0cd
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;
407 if (vsl)
408 *vsl = NULL;
410 expr = strip_parens(expr);
411 if (!expr)
412 return NULL;
413 if (sym)
414 *sym = NULL;
416 name = expr_to_var_sym(expr, &tmp);
417 if (name && tmp) {
418 if (sym)
419 *sym = tmp;
420 if (vsl)
421 *vsl = expr_to_vsl(expr);
422 return name;
424 free_string(name);
426 if (get_complication_score(expr) > 2)
427 return NULL;
429 if (vsl) {
430 *vsl = expr_to_vsl(expr);
431 if (!*vsl)
432 return NULL;
435 return expr_to_str(expr);
438 char *expr_to_known_chunk_sym(struct expression *expr, struct symbol **sym)
440 return expr_to_chunk_helper(expr, sym, NULL);
443 char *expr_to_chunk_sym_vsl(struct expression *expr, struct symbol **sym, struct var_sym_list **vsl)
445 return expr_to_chunk_helper(expr, sym, vsl);
448 int sym_name_is(const char *name, struct expression *expr)
450 if (!expr)
451 return 0;
452 if (expr->type != EXPR_SYMBOL)
453 return 0;
454 if (!strcmp(expr->symbol_name->name, name))
455 return 1;
456 return 0;
459 int is_zero(struct expression *expr)
461 sval_t sval;
463 if (get_value(expr, &sval) && sval.value == 0)
464 return 1;
465 return 0;
468 int is_array(struct expression *expr)
470 struct symbol *type;
472 expr = strip_expr(expr);
473 if (!expr)
474 return 0;
476 if (expr->type == EXPR_PREOP && expr->op == '*') {
477 expr = strip_expr(expr->unop);
478 if (expr->type == EXPR_BINOP && expr->op == '+')
479 return 1;
482 if (expr->type != EXPR_BINOP || expr->op != '+')
483 return 0;
485 type = get_type(expr->left);
486 if (!type || type->type != SYM_ARRAY)
487 return 0;
489 return 1;
492 struct expression *get_array_base(struct expression *expr)
494 if (!is_array(expr))
495 return NULL;
496 expr = strip_expr(expr);
497 if (expr->type == EXPR_PREOP && expr->op == '*')
498 expr = strip_expr(expr->unop);
499 if (expr->type != EXPR_BINOP || expr->op != '+')
500 return NULL;
501 return strip_parens(expr->left);
504 struct expression *get_array_offset(struct expression *expr)
506 if (!is_array(expr))
507 return NULL;
508 expr = strip_expr(expr);
509 if (expr->type == EXPR_PREOP && expr->op == '*')
510 expr = strip_expr(expr->unop);
511 if (expr->type != EXPR_BINOP || expr->op != '+')
512 return NULL;
513 return strip_parens(expr->right);
516 const char *show_state(struct smatch_state *state)
518 if (!state)
519 return NULL;
520 return state->name;
523 struct statement *get_expression_statement(struct expression *expr)
525 /* What are those things called? if (({....; ret;})) { ...*/
527 if (expr->type != EXPR_PREOP)
528 return NULL;
529 if (expr->op != '(')
530 return NULL;
531 if (expr->unop->type != EXPR_STATEMENT)
532 return NULL;
533 if (expr->unop->statement->type != STMT_COMPOUND)
534 return NULL;
535 return expr->unop->statement;
538 struct expression *strip_parens(struct expression *expr)
540 if (!expr)
541 return NULL;
543 if (expr->type == EXPR_PREOP) {
544 if (expr->op == '(' && expr->unop->type == EXPR_STATEMENT &&
545 expr->unop->statement->type == STMT_COMPOUND)
546 return expr;
547 if (expr->op == '(')
548 return strip_parens(expr->unop);
550 return expr;
553 struct expression *strip_expr(struct expression *expr)
555 if (!expr)
556 return NULL;
558 switch (expr->type) {
559 case EXPR_FORCE_CAST:
560 case EXPR_CAST:
561 return strip_expr(expr->cast_expression);
562 case EXPR_PREOP: {
563 struct expression *unop;
565 if (expr->op == '(' && expr->unop->type == EXPR_STATEMENT &&
566 expr->unop->statement->type == STMT_COMPOUND)
567 return expr;
569 unop = strip_expr(expr->unop);
571 if (expr->op == '*' &&
572 unop->type == EXPR_PREOP && unop->op == '&') {
573 struct symbol *type = get_type(unop->unop);
575 if (type && type->type == SYM_ARRAY)
576 return expr;
577 return strip_expr(unop->unop);
580 if (expr->op == '(')
581 return unop;
583 return expr;
585 case EXPR_CONDITIONAL:
586 if (known_condition_true(expr->conditional)) {
587 if (expr->cond_true)
588 return strip_expr(expr->cond_true);
589 return strip_expr(expr->conditional);
591 if (known_condition_false(expr->conditional))
592 return strip_expr(expr->cond_false);
593 return expr;
594 case EXPR_CALL:
595 if (sym_name_is("__builtin_expect", expr->fn)) {
596 expr = get_argument_from_call_expr(expr->args, 0);
597 return strip_expr(expr);
599 return expr;
601 return expr;
604 static void delete_state_tracker(struct tracker *t)
606 delete_state(t->owner, t->name, t->sym);
607 __free_tracker(t);
610 void scoped_state(int my_id, const char *name, struct symbol *sym)
612 struct tracker *t;
614 t = alloc_tracker(my_id, name, sym);
615 add_scope_hook((scope_hook *)&delete_state_tracker, t);
618 int is_error_return(struct expression *expr)
620 struct symbol *cur_func = cur_func_sym;
621 sval_t sval;
623 if (!expr)
624 return 0;
625 if (cur_func->type != SYM_NODE)
626 return 0;
627 cur_func = get_base_type(cur_func);
628 if (cur_func->type != SYM_FN)
629 return 0;
630 cur_func = get_base_type(cur_func);
631 if (cur_func == &void_ctype)
632 return 0;
633 if (!get_implied_value(expr, &sval))
634 return 0;
635 if (sval.value < 0)
636 return 1;
637 if (cur_func->type == SYM_PTR && sval.value == 0)
638 return 1;
639 return 0;
642 int getting_address(void)
644 struct expression *tmp;
645 int i = 0;
646 int dot_ops = 0;
648 FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
649 if (!i++)
650 continue;
651 if (tmp->type == EXPR_PREOP && tmp->op == '(')
652 continue;
653 if (tmp->op == '.' && !dot_ops++)
654 continue;
655 if (tmp->op == '&')
656 return 1;
657 return 0;
658 } END_FOR_EACH_PTR_REVERSE(tmp);
659 return 0;
662 char *get_member_name(struct expression *expr)
664 char buf[256];
665 struct symbol *sym;
667 expr = strip_expr(expr);
668 if (expr->type != EXPR_DEREF)
669 return NULL;
670 if (!expr->member)
671 return NULL;
673 sym = get_type(expr->deref);
674 if (!sym)
675 return NULL;
676 if (sym->type == SYM_UNION) {
677 sym = expr_to_sym(expr->deref);
678 sym = get_real_base_type(sym);
679 if (sym && sym->type == SYM_PTR)
680 sym = get_real_base_type(sym);
681 if (!sym || !sym->ident) {
682 snprintf(buf, sizeof(buf), "(union hack)->%s", expr->member->name);
683 return alloc_string(buf);
686 if (!sym->ident)
687 return NULL;
688 snprintf(buf, sizeof(buf), "(struct %s)->%s", sym->ident->name, expr->member->name);
689 return alloc_string(buf);
692 int cmp_pos(struct position pos1, struct position pos2)
694 /* the stream position is ... */
695 if (pos1.stream > pos2.stream)
696 return -1;
697 if (pos1.stream < pos2.stream)
698 return 1;
700 if (pos1.line < pos2.line)
701 return -1;
702 if (pos1.line > pos2.line)
703 return 1;
705 if (pos1.pos < pos2.pos)
706 return -1;
707 if (pos1.pos > pos2.pos)
708 return 1;
710 return 0;
713 int positions_eq(struct position pos1, struct position pos2)
715 if (pos1.line != pos2.line)
716 return 0;
717 if (pos1.pos != pos2.pos)
718 return 0;
719 if (pos1.stream != pos2.stream)
720 return 0;
721 return 1;
724 struct statement *get_current_statement(void)
726 struct statement *prev, *tmp;
728 prev = last_ptr_list((struct ptr_list *)big_statement_stack);
730 if (!prev || !get_macro_name(prev->pos))
731 return prev;
733 FOR_EACH_PTR_REVERSE(big_statement_stack, tmp) {
734 if (positions_eq(tmp->pos, prev->pos))
735 continue;
736 if (prev->pos.line > tmp->pos.line)
737 return prev;
738 return tmp;
739 } END_FOR_EACH_PTR_REVERSE(tmp);
740 return prev;
743 struct statement *get_prev_statement(void)
745 struct statement *tmp;
746 int i;
748 i = 0;
749 FOR_EACH_PTR_REVERSE(big_statement_stack, tmp) {
750 if (i++ == 1)
751 return tmp;
752 } END_FOR_EACH_PTR_REVERSE(tmp);
753 return NULL;
756 int get_param_num_from_sym(struct symbol *sym)
758 struct symbol *tmp;
759 int i;
761 if (!cur_func_sym)
762 return -1;
764 i = 0;
765 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, tmp) {
766 if (tmp == sym)
767 return i;
768 i++;
769 } END_FOR_EACH_PTR(tmp);
770 return -1;
773 int get_param_num(struct expression *expr)
775 struct symbol *sym;
776 char *name;
778 if (!cur_func_sym)
779 return -1;
780 name = expr_to_var_sym(expr, &sym);
781 free_string(name);
782 if (!sym)
783 return -1;
784 return get_param_num_from_sym(sym);
787 int ms_since(struct timeval *start)
789 struct timeval end;
790 double diff;
792 gettimeofday(&end, NULL);
793 diff = (end.tv_sec - start->tv_sec) * 1000.0;
794 diff += (end.tv_usec - start->tv_usec) / 1000.0;
795 return (int)diff;
798 int parent_is_gone_var_sym(const char *name, struct symbol *sym)
800 if (!name || !sym)
801 return 0;
803 if (parent_is_null_var_sym(name, sym) ||
804 parent_is_free_var_sym(name, sym))
805 return 1;
806 return 0;
809 int parent_is_gone(struct expression *expr)
811 struct symbol *sym;
812 char *var;
813 int ret = 0;
815 expr = strip_expr(expr);
816 var = expr_to_var_sym(expr, &sym);
817 if (!var || !sym)
818 goto free;
819 ret = parent_is_gone_var_sym(var, sym);
820 free:
821 free_string(var);
822 return ret;
825 int invert_op(int op)
827 switch (op) {
828 case '*':
829 return '/';
830 case '/':
831 return '*';
832 case '+':
833 return '-';
834 case '-':
835 return '+';
836 case SPECIAL_LEFTSHIFT:
837 return SPECIAL_RIGHTSHIFT;
838 case SPECIAL_RIGHTSHIFT:
839 return SPECIAL_LEFTSHIFT;
841 return 0;