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.
26 #include "smatch_extra.h"
27 #include "smatch_slist.h"
31 char *alloc_string(const char *str
)
37 tmp
= malloc(strlen(str
) + 1);
42 void free_string(char *str
)
47 void remove_parens(char *str
)
52 while (*src
!= '\0') {
53 if (*src
== '(' || *src
== ')') {
62 struct smatch_state
*alloc_state_num(int num
)
64 struct smatch_state
*state
;
65 static char buff
[256];
67 state
= __alloc_smatch_state(0);
68 snprintf(buff
, 255, "%d", num
);
70 state
->name
= alloc_string(buff
);
71 state
->data
= INT_PTR(num
);
75 struct smatch_state
*alloc_state_str(const char *name
)
77 struct smatch_state
*state
;
79 state
= __alloc_smatch_state(0);
80 state
->name
= alloc_string(name
);
84 struct smatch_state
*alloc_state_expr(struct expression
*expr
)
86 struct smatch_state
*state
;
89 state
= __alloc_smatch_state(0);
90 expr
= strip_expr(expr
);
91 name
= expr_to_str(expr
);
92 state
->name
= alloc_sname(name
);
98 void append(char *dest
, const char *data
, int buff_len
)
100 strncat(dest
, data
, buff_len
- strlen(dest
) - 1);
104 * If you have "foo(a, b, 1);" then use
105 * get_argument_from_call_expr(expr, 0) to return the expression for
106 * a. Yes, it does start counting from 0.
108 struct expression
*get_argument_from_call_expr(struct expression_list
*args
,
111 struct expression
*expr
;
117 FOR_EACH_PTR(args
, expr
) {
121 } END_FOR_EACH_PTR(expr
);
125 static struct expression
*get_array_expr(struct expression
*expr
)
129 if (expr
->type
!= EXPR_BINOP
|| expr
->op
!= '+')
132 type
= get_type(expr
->left
);
133 if (!type
|| type
->type
!= SYM_ARRAY
)
138 static void __get_variable_from_expr(struct symbol
**sym_ptr
, char *buf
,
139 struct expression
*expr
, int len
,
140 int *complicated
, int no_parens
)
145 /* can't happen on valid code */
150 switch (expr
->type
) {
152 struct expression
*deref
;
158 struct expression
*unop
= strip_expr(deref
->unop
);
160 if (unop
->type
== EXPR_PREOP
&& unop
->op
== '&') {
165 if (!is_pointer(deref
))
170 __get_variable_from_expr(sym_ptr
, buf
, deref
, len
, complicated
, no_parens
);
173 append(buf
, "->", len
);
175 append(buf
, ".", len
);
178 append(buf
, expr
->member
->name
, len
);
180 append(buf
, "unknown_member", len
);
185 if (expr
->symbol_name
)
186 append(buf
, expr
->symbol_name
->name
, len
);
190 *sym_ptr
= expr
->symbol
;
196 if (get_expression_statement(expr
)) {
201 if (expr
->op
== '(') {
202 if (!no_parens
&& expr
->unop
->type
!= EXPR_SYMBOL
)
203 append(buf
, "(", len
);
204 } else if (expr
->op
!= '*' || !get_array_expr(expr
->unop
)) {
205 tmp
= show_special(expr
->op
);
206 append(buf
, tmp
, len
);
208 __get_variable_from_expr(sym_ptr
, buf
, expr
->unop
,
209 len
, complicated
, no_parens
);
211 if (expr
->op
== '(' && !no_parens
&& expr
->unop
->type
!= EXPR_SYMBOL
)
212 append(buf
, ")", len
);
214 if (expr
->op
== SPECIAL_DECREMENT
||
215 expr
->op
== SPECIAL_INCREMENT
)
223 __get_variable_from_expr(sym_ptr
, buf
, expr
->unop
,
224 len
, complicated
, no_parens
);
225 tmp
= show_special(expr
->op
);
226 append(buf
, tmp
, len
);
228 if (expr
->op
== SPECIAL_DECREMENT
|| expr
->op
== SPECIAL_INCREMENT
)
232 case EXPR_ASSIGNMENT
:
237 struct expression
*array_expr
;
240 array_expr
= get_array_expr(expr
);
242 __get_variable_from_expr(sym_ptr
, buf
, array_expr
, len
, complicated
, no_parens
);
243 append(buf
, "[", len
);
245 __get_variable_from_expr(sym_ptr
, buf
, expr
->left
, len
, complicated
, no_parens
);
246 snprintf(tmp
, sizeof(tmp
), " %s ", show_special(expr
->op
));
247 append(buf
, tmp
, len
);
249 __get_variable_from_expr(NULL
, buf
, expr
->right
, len
, complicated
, no_parens
);
251 append(buf
, "]", len
);
258 snprintf(tmp
, 25, "%lld", expr
->value
);
259 append(buf
, tmp
, len
);
263 append(buf
, "\"", len
);
265 append(buf
, expr
->string
->data
, len
);
266 append(buf
, "\"", len
);
269 struct expression
*tmp
;
273 __get_variable_from_expr(NULL
, buf
, expr
->fn
, len
, complicated
, no_parens
);
274 append(buf
, "(", len
);
276 FOR_EACH_PTR(expr
->args
, tmp
) {
278 append(buf
, ", ", len
);
279 __get_variable_from_expr(NULL
, buf
, tmp
, len
, complicated
, no_parens
);
280 } END_FOR_EACH_PTR(tmp
);
281 append(buf
, ")", len
);
285 case EXPR_FORCE_CAST
:
286 __get_variable_from_expr(sym_ptr
, buf
,
287 expr
->cast_expression
, len
,
288 complicated
, no_parens
);
295 if (expr
->cast_type
&& get_base_type(expr
->cast_type
)) {
296 size
= type_bytes(get_base_type(expr
->cast_type
));
297 snprintf(tmp
, 25, "%d", size
);
298 append(buf
, tmp
, len
);
299 } else if (get_value(expr
, &sval
)) {
300 snprintf(tmp
, 25, "%s", sval_to_str(sval
));
301 append(buf
, tmp
, len
);
305 case EXPR_IDENTIFIER
:
307 if (expr
->expr_ident
)
308 append(buf
, expr
->expr_ident
->name
, len
);
312 //printf("unknown type = %d\n", expr->type);
318 * This is returns a stylized "c looking" representation of the
321 * It uses the same buffer every time so you have to save the result
322 * yourself if you want to keep it.
326 char *expr_to_str_sym(struct expression
*expr
, struct symbol
**sym_ptr
)
328 static char var_name
[VAR_LEN
];
337 __get_variable_from_expr(sym_ptr
, var_name
, expr
, sizeof(var_name
),
340 return alloc_string(var_name
);
345 char *expr_to_str(struct expression
*expr
)
347 return expr_to_str_sym(expr
, NULL
);
351 * get_variable_from_expr_simple() only returns simple variables.
352 * If it's a complicated variable like a->foo[x] instead of just 'a->foo'
353 * then it returns NULL.
355 char *expr_to_var_sym(struct expression
*expr
,
356 struct symbol
**sym_ptr
)
358 static char var_name
[VAR_LEN
];
367 expr
= strip_expr(expr
);
368 __get_variable_from_expr(sym_ptr
, var_name
, expr
, sizeof(var_name
),
376 return alloc_string(var_name
);
379 char *expr_to_var(struct expression
*expr
)
381 return expr_to_var_sym(expr
, NULL
);
384 struct symbol
*expr_to_sym(struct expression
*expr
)
389 name
= expr_to_var_sym(expr
, &sym
);
394 int get_complication_score(struct expression
*expr
)
398 expr
= strip_expr(expr
);
401 * Don't forget to keep get_complication_score() and store_all_links()
409 switch (expr
->type
) {
414 score
+= get_complication_score(expr
->left
);
415 score
+= get_complication_score(expr
->right
);
418 if (is_local_variable(expr
))
423 return score
+ get_complication_score(expr
->unop
);
426 return score
+ get_complication_score(expr
->deref
);
434 struct expression
*reorder_expr_alphabetically(struct expression
*expr
)
436 struct expression
*ret
;
439 if (expr
->type
!= EXPR_BINOP
)
441 if (expr
->op
!= '+' && expr
->op
!= '*')
444 left
= expr_to_var(expr
->left
);
445 right
= expr_to_var(expr
->right
);
449 if (strcmp(left
, right
) <= 0)
452 ret
= binop_expression(expr
->right
, expr
->op
, expr
->left
);
460 char *expr_to_chunk_helper(struct expression
*expr
, struct symbol
**sym
, struct var_sym_list
**vsl
)
471 expr
= strip_parens(expr
);
475 name
= expr_to_var_sym(expr
, &tmp
);
480 *vsl
= expr_to_vsl(expr
);
485 score
= get_complication_score(expr
);
486 if (score
<= 0 || score
> 2)
490 *vsl
= expr_to_vsl(expr
);
495 expr
= reorder_expr_alphabetically(expr
);
497 return expr_to_str(expr
);
500 char *expr_to_known_chunk_sym(struct expression
*expr
, struct symbol
**sym
)
502 return expr_to_chunk_helper(expr
, sym
, NULL
);
505 char *expr_to_chunk_sym_vsl(struct expression
*expr
, struct symbol
**sym
, struct var_sym_list
**vsl
)
507 return expr_to_chunk_helper(expr
, sym
, vsl
);
510 int sym_name_is(const char *name
, struct expression
*expr
)
514 if (expr
->type
!= EXPR_SYMBOL
)
516 if (!strcmp(expr
->symbol_name
->name
, name
))
521 int is_zero(struct expression
*expr
)
525 if (get_value(expr
, &sval
) && sval
.value
== 0)
530 int is_array(struct expression
*expr
)
534 expr
= strip_expr(expr
);
538 if (expr
->type
== EXPR_PREOP
&& expr
->op
== '*') {
539 expr
= strip_expr(expr
->unop
);
542 if (expr
->type
== EXPR_BINOP
&& expr
->op
== '+')
546 if (expr
->type
!= EXPR_BINOP
|| expr
->op
!= '+')
549 type
= get_type(expr
->left
);
550 if (!type
|| type
->type
!= SYM_ARRAY
)
556 struct expression
*get_array_base(struct expression
*expr
)
560 expr
= strip_expr(expr
);
561 if (expr
->type
== EXPR_PREOP
&& expr
->op
== '*')
562 expr
= strip_expr(expr
->unop
);
563 if (expr
->type
!= EXPR_BINOP
|| expr
->op
!= '+')
565 return strip_parens(expr
->left
);
568 struct expression
*get_array_offset(struct expression
*expr
)
572 expr
= strip_expr(expr
);
573 if (expr
->type
== EXPR_PREOP
&& expr
->op
== '*')
574 expr
= strip_expr(expr
->unop
);
575 if (expr
->type
!= EXPR_BINOP
|| expr
->op
!= '+')
577 return strip_parens(expr
->right
);
580 const char *show_state(struct smatch_state
*state
)
587 struct statement
*get_expression_statement(struct expression
*expr
)
589 /* What are those things called? if (({....; ret;})) { ...*/
591 if (expr
->type
!= EXPR_PREOP
)
595 if (expr
->unop
->type
!= EXPR_STATEMENT
)
597 if (expr
->unop
->statement
->type
!= STMT_COMPOUND
)
599 return expr
->unop
->statement
;
602 struct expression
*strip_parens(struct expression
*expr
)
607 if (expr
->type
== EXPR_PREOP
) {
608 if (expr
->op
== '(' && expr
->unop
->type
== EXPR_STATEMENT
&&
609 expr
->unop
->statement
->type
== STMT_COMPOUND
)
612 return strip_parens(expr
->unop
);
617 struct expression
*strip_expr(struct expression
*expr
)
622 switch (expr
->type
) {
623 case EXPR_FORCE_CAST
:
625 return strip_expr(expr
->cast_expression
);
627 struct expression
*unop
;
629 if (expr
->op
== '(' && expr
->unop
->type
== EXPR_STATEMENT
&&
630 expr
->unop
->statement
->type
== STMT_COMPOUND
)
633 unop
= strip_expr(expr
->unop
);
635 if (expr
->op
== '*' && unop
&&
636 unop
->type
== EXPR_PREOP
&& unop
->op
== '&') {
637 struct symbol
*type
= get_type(unop
->unop
);
639 if (type
&& type
->type
== SYM_ARRAY
)
641 return strip_expr(unop
->unop
);
649 case EXPR_CONDITIONAL
:
650 if (known_condition_true(expr
->conditional
)) {
652 return strip_expr(expr
->cond_true
);
653 return strip_expr(expr
->conditional
);
655 if (known_condition_false(expr
->conditional
))
656 return strip_expr(expr
->cond_false
);
659 if (sym_name_is("__builtin_expect", expr
->fn
)) {
660 expr
= get_argument_from_call_expr(expr
->args
, 0);
661 return strip_expr(expr
);
668 static void delete_state_tracker(struct tracker
*t
)
670 delete_state(t
->owner
, t
->name
, t
->sym
);
674 void scoped_state(int my_id
, const char *name
, struct symbol
*sym
)
678 t
= alloc_tracker(my_id
, name
, sym
);
679 add_scope_hook((scope_hook
*)&delete_state_tracker
, t
);
682 int is_error_return(struct expression
*expr
)
684 struct symbol
*cur_func
= cur_func_sym
;
689 if (cur_func
->type
!= SYM_NODE
)
691 cur_func
= get_base_type(cur_func
);
692 if (cur_func
->type
!= SYM_FN
)
694 cur_func
= get_base_type(cur_func
);
695 if (cur_func
== &void_ctype
)
697 if (!get_implied_value(expr
, &sval
))
701 if (cur_func
->type
== SYM_PTR
&& sval
.value
== 0)
706 int getting_address(void)
708 struct expression
*tmp
;
712 FOR_EACH_PTR_REVERSE(big_expression_stack
, tmp
) {
715 if (tmp
->type
== EXPR_PREOP
&& tmp
->op
== '(')
717 if (tmp
->op
== '.' && !dot_ops
++)
722 } END_FOR_EACH_PTR_REVERSE(tmp
);
726 int get_struct_and_member(struct expression
*expr
, const char **type
, const char **member
)
730 expr
= strip_expr(expr
);
731 if (expr
->type
!= EXPR_DEREF
)
736 sym
= get_type(expr
->deref
);
739 if (sym
->type
== SYM_UNION
)
744 *type
= sym
->ident
->name
;
745 *member
= expr
->member
->name
;
749 char *get_member_name(struct expression
*expr
)
754 expr
= strip_expr(expr
);
755 if (expr
->type
!= EXPR_DEREF
)
760 sym
= get_type(expr
->deref
);
763 if (sym
->type
== SYM_UNION
) {
764 snprintf(buf
, sizeof(buf
), "(union %s)->%s",
765 sym
->ident
? sym
->ident
->name
: "anonymous",
767 return alloc_string(buf
);
771 snprintf(buf
, sizeof(buf
), "(struct %s)->%s", sym
->ident
->name
, expr
->member
->name
);
772 return alloc_string(buf
);
775 int cmp_pos(struct position pos1
, struct position pos2
)
777 /* the stream position is ... */
778 if (pos1
.stream
> pos2
.stream
)
780 if (pos1
.stream
< pos2
.stream
)
783 if (pos1
.line
< pos2
.line
)
785 if (pos1
.line
> pos2
.line
)
788 if (pos1
.pos
< pos2
.pos
)
790 if (pos1
.pos
> pos2
.pos
)
796 int positions_eq(struct position pos1
, struct position pos2
)
798 if (pos1
.line
!= pos2
.line
)
800 if (pos1
.pos
!= pos2
.pos
)
802 if (pos1
.stream
!= pos2
.stream
)
807 struct statement
*get_current_statement(void)
809 struct statement
*prev
, *tmp
;
811 prev
= last_ptr_list((struct ptr_list
*)big_statement_stack
);
813 if (!prev
|| !get_macro_name(prev
->pos
))
816 FOR_EACH_PTR_REVERSE(big_statement_stack
, tmp
) {
817 if (positions_eq(tmp
->pos
, prev
->pos
))
819 if (prev
->pos
.line
> tmp
->pos
.line
)
822 } END_FOR_EACH_PTR_REVERSE(tmp
);
826 struct statement
*get_prev_statement(void)
828 struct statement
*tmp
;
832 FOR_EACH_PTR_REVERSE(big_statement_stack
, tmp
) {
835 } END_FOR_EACH_PTR_REVERSE(tmp
);
839 int get_param_num_from_sym(struct symbol
*sym
)
848 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, tmp
) {
852 } END_FOR_EACH_PTR(tmp
);
856 int get_param_num(struct expression
*expr
)
863 name
= expr_to_var_sym(expr
, &sym
);
867 return get_param_num_from_sym(sym
);
870 int ms_since(struct timeval
*start
)
875 gettimeofday(&end
, NULL
);
876 diff
= (end
.tv_sec
- start
->tv_sec
) * 1000.0;
877 diff
+= (end
.tv_usec
- start
->tv_usec
) / 1000.0;
881 int parent_is_gone_var_sym(const char *name
, struct symbol
*sym
)
886 if (parent_is_null_var_sym(name
, sym
) ||
887 parent_is_free_var_sym(name
, sym
))
892 int parent_is_gone(struct expression
*expr
)
898 expr
= strip_expr(expr
);
899 var
= expr_to_var_sym(expr
, &sym
);
902 ret
= parent_is_gone_var_sym(var
, sym
);
908 int invert_op(int op
)
919 case SPECIAL_LEFTSHIFT
:
920 return SPECIAL_RIGHTSHIFT
;
921 case SPECIAL_RIGHTSHIFT
:
922 return SPECIAL_LEFTSHIFT
;
927 int expr_equiv(struct expression
*one
, struct expression
*two
)
929 struct symbol
*one_sym
= NULL
;
930 struct symbol
*two_sym
= NULL
;
931 char *one_name
= NULL
;
932 char *two_name
= NULL
;
937 if (one
->type
!= two
->type
)
940 one_name
= expr_to_str_sym(one
, &one_sym
);
943 two_name
= expr_to_str_sym(two
, &two_sym
);
946 if (one_sym
!= two_sym
)
949 * This is a terrible hack because expr_to_str() sometimes gives up in
950 * the middle and just returns what it has. If you see a () you know
951 * the string is bogus.
953 if (strstr(one_name
, "()"))
955 if (strcmp(one_name
, two_name
) == 0)
958 free_string(one_name
);
959 free_string(two_name
);
963 void push_int(struct int_stack
**stack
, int num
)
968 * Just put the int on directly instead of a pointer to the int.
969 * Shift it to the left because Sparse uses the last two bits.
970 * This is sort of a dirty hack, yes.
973 munged
= INT_PTR(num
<< 2);
975 add_ptr_list(stack
, munged
);
978 int pop_int(struct int_stack
**stack
)
982 num
= last_ptr_list((struct ptr_list
*)*stack
);
983 delete_ptr_list_last((struct ptr_list
**)stack
);
985 return PTR_INT(num
) >> 2;