4 * Copyright (C) 2006,2008 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
15 #include "smatch_expression_stacks.h"
16 #include "smatch_extra.h"
17 #include "smatch_slist.h"
21 static int __smatch_lineno
= 0;
23 static char *base_file
;
24 static const char *filename
;
25 static char *pathname
;
26 static char *full_filename
;
27 static char *cur_func
;
28 static int line_func_start
;
29 static int loop_count
;
30 int __expr_stmt_count
;
31 static struct expression_list
*switch_expr_stack
= NULL
;
33 struct expression_list
*big_expression_stack
;
34 struct statement_list
*big_statement_stack
;
35 int __in_pre_condition
= 0;
36 int __bail_on_rest_of_function
= 0;
37 char *get_function(void) { return cur_func
; }
38 int get_lineno(void) { return __smatch_lineno
; }
39 int inside_loop(void) { return !!loop_count
; }
40 struct expression
*get_switch_expr(void) { return top_expression(switch_expr_stack
); }
41 int in_expression_statement(void) { return !!__expr_stmt_count
; }
43 static void split_symlist(struct symbol_list
*sym_list
);
44 static void split_declaration(struct symbol_list
*sym_list
);
45 static void split_expr_list(struct expression_list
*expr_list
);
46 static void add_inline_function(struct symbol
*sym
);
48 int option_assume_loops
= 0;
49 int option_known_conditions
= 0;
50 int option_two_passes
= 0;
51 struct symbol
*cur_func_sym
= NULL
;
53 const char *get_filename(void)
62 static void set_position(struct position pos
)
65 static int prev_stream
= -1;
67 __smatch_lineno
= pos
.line
;
69 if (pos
.stream
== prev_stream
)
72 filename
= stream_name(pos
.stream
);
75 pathname
= getcwd(NULL
, 0);
77 len
= strlen(pathname
) + 1 + strlen(filename
) + 1;
78 full_filename
= malloc(len
);
79 snprintf(full_filename
, len
, "%s/%s", pathname
, filename
);
81 full_filename
= alloc_string(filename
);
86 static int is_inline_func(struct expression
*expr
)
88 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
)
90 if (expr
->symbol
->ctype
.modifiers
& MOD_INLINE
)
95 static int is_noreturn_func(struct expression
*expr
)
97 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
)
99 if (expr
->symbol
->ctype
.modifiers
& MOD_NORETURN
)
104 void __split_expr(struct expression
*expr
)
109 // sm_msg(" Debug expr_type %d %s", expr->type, show_special(expr->op));
111 push_expression(&big_expression_stack
, expr
);
112 set_position(expr
->pos
);
113 __pass_to_client(expr
, EXPR_HOOK
);
115 switch (expr
->type
) {
118 __pass_to_client(expr
, DEREF_HOOK
);
120 __pass_to_client(expr
, OP_HOOK
);
121 __split_expr(expr
->unop
);
125 __split_stmt(expr
->statement
);
130 __pass_to_client(expr
, LOGIC_HOOK
);
131 __handle_logic(expr
);
134 __pass_to_client(expr
, BINOP_HOOK
);
136 __split_expr(expr
->left
);
137 __split_expr(expr
->right
);
139 case EXPR_ASSIGNMENT
: {
140 struct expression
*tmp
;
145 __pass_to_client(expr
, RAW_ASSIGNMENT_HOOK
);
148 if (__handle_condition_assigns(expr
))
150 /* foo = (x < 5 ? foo : 5); */
151 if (__handle_select_assigns(expr
))
153 /* foo = ({frob(); frob(); frob(); 1;}) */
154 if (__handle_expr_statement_assigns(expr
))
157 __split_expr(expr
->right
);
158 __pass_to_client(expr
, ASSIGNMENT_HOOK
);
159 tmp
= strip_expr(expr
->right
);
160 if (tmp
->type
== EXPR_CALL
)
161 __pass_to_client(expr
, CALL_ASSIGNMENT_HOOK
);
162 if (get_macro_name(tmp
->pos
) &&
163 get_macro_name(expr
->pos
) != get_macro_name(tmp
->pos
))
164 __pass_to_client(expr
, MACRO_ASSIGNMENT_HOOK
);
165 __split_expr(expr
->left
);
169 __pass_to_client(expr
, DEREF_HOOK
);
170 __split_expr(expr
->deref
);
173 __split_expr(expr
->base
);
176 case EXPR_FORCE_CAST
:
177 __pass_to_client(expr
, CAST_HOOK
);
178 __split_expr(expr
->cast_expression
);
181 if (expr
->cast_expression
)
182 __pass_to_client(strip_parens(expr
->cast_expression
),
187 evaluate_expression(expr
);
189 case EXPR_CONDITIONAL
:
191 if (known_condition_true(expr
->conditional
)) {
192 __split_expr(expr
->cond_true
);
195 if (known_condition_false(expr
->conditional
)) {
196 __split_expr(expr
->cond_false
);
199 __pass_to_client(expr
, SELECT_HOOK
);
200 __split_whole_condition(expr
->conditional
);
201 __split_expr(expr
->cond_true
);
202 __push_true_states();
203 __use_false_states();
204 __split_expr(expr
->cond_false
);
205 __merge_true_states();
208 if (sym_name_is("__builtin_constant_p", expr
->fn
))
210 split_expr_list(expr
->args
);
211 __split_expr(expr
->fn
);
212 if (is_inline_func(expr
->fn
))
213 add_inline_function(expr
->fn
->symbol
);
214 __pass_to_client(expr
, FUNCTION_CALL_HOOK
);
215 if (is_noreturn_func(expr
->fn
))
218 case EXPR_INITIALIZER
:
219 split_expr_list(expr
->expr_list
);
221 case EXPR_IDENTIFIER
:
222 __split_expr(expr
->ident_expression
);
225 __split_expr(expr
->idx_expression
);
228 __split_expr(expr
->init_expr
);
231 __pass_to_client(expr
, SYM_HOOK
);
234 __pass_to_client(expr
, STRING_HOOK
);
239 pop_expression(&big_expression_stack
);
242 static int is_forever_loop(struct statement
*stmt
)
244 struct expression
*expr
;
246 expr
= strip_expr(stmt
->iterator_pre_condition
);
248 expr
= stmt
->iterator_post_condition
;
250 /* this is a for(;;) loop... */
254 if (expr
->type
== EXPR_VALUE
&& expr
->value
== 1)
261 static char *get_loop_name(int num
)
265 snprintf(buf
, 255, "-loop%d", num
);
267 return alloc_sname(buf
);
271 * Pre Loops are while and for loops.
273 static void handle_pre_loop(struct statement
*stmt
)
275 int once_through
; /* we go through the loop at least once */
276 struct sm_state
*extra_sm
= NULL
;
279 struct state_list
*slist
= NULL
;
280 struct sm_state
*sm
= NULL
;
282 loop_name
= get_loop_name(loop_num
);
285 __split_stmt(stmt
->iterator_pre_statement
);
287 once_through
= implied_condition_true(stmt
->iterator_pre_condition
);
293 __merge_gotos(loop_name
);
295 extra_sm
= __extra_handle_canonical_loops(stmt
, &slist
);
296 __in_pre_condition
++;
297 __pass_to_client(stmt
, PRELOOP_HOOK
);
298 __split_whole_condition(stmt
->iterator_pre_condition
);
299 __in_pre_condition
--;
300 FOR_EACH_PTR(slist
, sm
) {
301 set_state(sm
->owner
, sm
->name
, sm
->sym
, sm
->state
);
302 } END_FOR_EACH_PTR(sm
);
305 extra_sm
= get_sm_state(extra_sm
->owner
, extra_sm
->name
, extra_sm
->sym
);
307 if (option_assume_loops
)
310 __split_stmt(stmt
->iterator_statement
);
311 __warn_on_silly_pre_loops();
312 if (is_forever_loop(stmt
)) {
313 struct state_list
*slist
;
315 __save_gotos(loop_name
);
317 __push_fake_cur_slist();
318 __split_stmt(stmt
->iterator_post_statement
);
319 slist
= __pop_fake_cur_slist();
321 __discard_continues();
322 __discard_false_states();
325 if (!__path_is_null())
326 __merge_slist_into_cur(slist
);
330 unchanged
= __iterator_unchanged(extra_sm
);
331 __split_stmt(stmt
->iterator_post_statement
);
332 __save_gotos(loop_name
);
333 __split_whole_condition(stmt
->iterator_pre_condition
);
335 __merge_false_states();
337 __discard_false_states();
339 __merge_false_states();
341 if (extra_sm
&& unchanged
)
342 __extra_pre_loop_hook_after(extra_sm
,
343 stmt
->iterator_post_statement
,
344 stmt
->iterator_pre_condition
);
351 * Post loops are do {} while();
353 static void handle_post_loop(struct statement
*stmt
)
357 loop_name
= get_loop_name(loop_num
);
363 __merge_gotos(loop_name
);
364 __split_stmt(stmt
->iterator_statement
);
366 if (!is_zero(stmt
->iterator_post_condition
))
367 __save_gotos(loop_name
);
369 if (is_forever_loop(stmt
)) {
372 __split_whole_condition(stmt
->iterator_post_condition
);
373 __use_false_states();
379 static int empty_statement(struct statement
*stmt
)
383 if (stmt
->type
== STMT_EXPRESSION
&& !stmt
->expression
)
388 static int last_stmt_on_same_line()
390 struct statement
*stmt
;
393 FOR_EACH_PTR_REVERSE(big_statement_stack
, stmt
) {
396 if (stmt
->pos
.line
== get_lineno())
399 } END_FOR_EACH_PTR_REVERSE(stmt
);
403 static struct statement
*last_stmt
;
404 static int is_last_stmt(struct statement
*stmt
)
406 if (stmt
== last_stmt
)
411 static void print_unreached_initializers(struct symbol_list
*sym_list
)
415 FOR_EACH_PTR(sym_list
, sym
) {
416 if (sym
->initializer
)
417 sm_msg("info: '%s' is not actually initialized (unreached code).",
418 (sym
->ident
? sym
->ident
->name
: "this variable"));
419 } END_FOR_EACH_PTR(sym
);
422 static void print_unreached(struct statement
*stmt
)
424 static int print
= 1;
426 if (!__path_is_null()) {
433 switch (stmt
->type
) {
434 case STMT_COMPOUND
: /* after a switch before a case stmt */
439 case STMT_DECLARATION
: /* switch (x) { int a; case foo: ... */
440 print_unreached_initializers(stmt
->declaration
);
442 case STMT_RETURN
: /* gcc complains if you don't have a return statement */
443 if (is_last_stmt(stmt
))
453 if (!option_spammy
&& empty_statement(stmt
))
455 sm_msg("info: ignoring unreachable code.");
459 static void split_asm_constraints(struct expression_list
*expr_list
)
461 struct expression
*expr
;
464 FOR_EACH_PTR(expr_list
, expr
) {
466 case 0: /* identifier */
467 case 1: /* constraint */
470 case 2: /* expression */
475 } END_FOR_EACH_PTR(expr
);
478 static int is_case_val(struct statement
*stmt
, sval_t sval
)
482 if (stmt
->type
!= STMT_CASE
)
484 if (!stmt
->case_expression
) {
488 if (!get_value(stmt
->case_expression
, &case_sval
))
490 if (case_sval
.value
== sval
.value
)
495 static void split_known_switch(struct statement
*stmt
, sval_t sval
)
497 struct statement
*tmp
;
499 __split_expr(stmt
->switch_expression
);
501 push_expression(&switch_expr_stack
, stmt
->switch_expression
);
502 __save_switch_states(top_expression(switch_expr_stack
));
507 stmt
= stmt
->switch_statement
;
510 last_stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
512 __push_scope_hooks();
513 FOR_EACH_PTR(stmt
->stmts
, tmp
) {
514 __smatch_lineno
= tmp
->pos
.line
;
515 if (is_case_val(tmp
, sval
)) {
516 __merge_switches(top_expression(switch_expr_stack
),
517 stmt
->case_expression
);
518 __pass_case_to_client(top_expression(switch_expr_stack
),
519 stmt
->case_expression
);
521 if (__path_is_null())
524 if (__path_is_null()) {
528 } END_FOR_EACH_PTR(tmp
);
530 __call_scope_hooks();
531 if (!__pop_default())
532 __merge_switches(top_expression(switch_expr_stack
),
534 __discard_switches();
536 pop_expression(&switch_expr_stack
);
539 void __split_stmt(struct statement
*stmt
)
546 if (out_of_memory() || __bail_on_rest_of_function
) {
547 static char *printed
= NULL
;
549 if (printed
!= cur_func
)
550 sm_msg("Function too hairy. Giving up.");
551 final_pass
= 0; /* turn off sm_msg() from here */
556 add_ptr_list(&big_statement_stack
, stmt
);
557 free_expression_stack(&big_expression_stack
);
558 set_position(stmt
->pos
);
559 print_unreached(stmt
);
560 __pass_to_client(stmt
, STMT_HOOK
);
562 switch (stmt
->type
) {
563 case STMT_DECLARATION
:
564 split_declaration(stmt
->declaration
);
567 __split_expr(stmt
->ret_value
);
568 __pass_to_client(stmt
->ret_value
, RETURN_HOOK
);
571 case STMT_EXPRESSION
:
572 __split_expr(stmt
->expression
);
574 case STMT_COMPOUND
: {
575 struct statement
*tmp
;
578 last_stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
579 __push_scope_hooks();
580 FOR_EACH_PTR(stmt
->stmts
, tmp
) {
582 } END_FOR_EACH_PTR(tmp
);
583 __call_scope_hooks();
587 if (known_condition_true(stmt
->if_conditional
)) {
588 __split_stmt(stmt
->if_true
);
591 if (known_condition_false(stmt
->if_conditional
)) {
592 __split_stmt(stmt
->if_false
);
595 if (option_known_conditions
&&
596 implied_condition_true(stmt
->if_conditional
)) {
597 sm_info("this condition is true.");
598 __split_stmt(stmt
->if_true
);
601 if (option_known_conditions
&&
602 implied_condition_false(stmt
->if_conditional
)) {
603 sm_info("this condition is false.");
604 __split_stmt(stmt
->if_false
);
607 __split_whole_condition(stmt
->if_conditional
);
608 __split_stmt(stmt
->if_true
);
609 if (empty_statement(stmt
->if_true
) &&
610 last_stmt_on_same_line() &&
611 !get_macro_name(stmt
->if_true
->pos
))
612 sm_msg("warn: if();");
613 __push_true_states();
614 __use_false_states();
615 __split_stmt(stmt
->if_false
);
616 __merge_true_states();
619 if (stmt
->iterator_pre_condition
)
620 handle_pre_loop(stmt
);
621 else if (stmt
->iterator_post_condition
)
622 handle_post_loop(stmt
);
624 // these are for(;;) type loops.
625 handle_pre_loop(stmt
);
629 if (get_value(stmt
->switch_expression
, &sval
)) {
630 split_known_switch(stmt
, sval
);
633 __split_expr(stmt
->switch_expression
);
634 push_expression(&switch_expr_stack
, stmt
->switch_expression
);
635 __save_switch_states(top_expression(switch_expr_stack
));
639 __split_stmt(stmt
->switch_statement
);
640 if (!__pop_default())
641 __merge_switches(top_expression(switch_expr_stack
),
643 __discard_switches();
645 pop_expression(&switch_expr_stack
);
648 __merge_switches(top_expression(switch_expr_stack
),
649 stmt
->case_expression
);
650 __pass_case_to_client(top_expression(switch_expr_stack
),
651 stmt
->case_expression
);
652 if (!stmt
->case_expression
)
654 __split_expr(stmt
->case_expression
);
655 __split_expr(stmt
->case_to
);
656 __split_stmt(stmt
->case_statement
);
659 if (stmt
->label_identifier
&&
660 stmt
->label_identifier
->type
== SYM_LABEL
&&
661 stmt
->label_identifier
->ident
) {
662 loop_count
= 1000000;
663 __merge_gotos(stmt
->label_identifier
->ident
->name
);
665 __split_stmt(stmt
->label_statement
);
668 __split_expr(stmt
->goto_expression
);
669 if (stmt
->goto_label
&& stmt
->goto_label
->type
== SYM_NODE
) {
670 if (!strcmp(stmt
->goto_label
->ident
->name
, "break")) {
672 } else if (!strcmp(stmt
->goto_label
->ident
->name
,
674 __process_continues();
676 } else if (stmt
->goto_label
&&
677 stmt
->goto_label
->type
== SYM_LABEL
&&
678 stmt
->goto_label
->ident
) {
679 __save_gotos(stmt
->goto_label
->ident
->name
);
686 __pass_to_client(stmt
, ASM_HOOK
);
687 __split_expr(stmt
->asm_string
);
688 split_asm_constraints(stmt
->asm_outputs
);
689 split_asm_constraints(stmt
->asm_inputs
);
690 split_asm_constraints(stmt
->asm_clobbers
);
695 __split_expr(stmt
->range_expression
);
696 __split_expr(stmt
->range_low
);
697 __split_expr(stmt
->range_high
);
702 static void split_expr_list(struct expression_list
*expr_list
)
704 struct expression
*expr
;
706 FOR_EACH_PTR(expr_list
, expr
) {
708 } END_FOR_EACH_PTR(expr
);
711 static void split_sym(struct symbol
*sym
)
715 if (!(sym
->namespace & NS_SYMBOL
))
718 __split_stmt(sym
->stmt
);
719 __split_expr(sym
->array_size
);
720 split_symlist(sym
->arguments
);
721 split_symlist(sym
->symbol_list
);
722 __split_stmt(sym
->inline_stmt
);
723 split_symlist(sym
->inline_symbol_list
);
726 static void split_symlist(struct symbol_list
*sym_list
)
730 FOR_EACH_PTR(sym_list
, sym
) {
732 } END_FOR_EACH_PTR(sym
);
735 static void fake_member_assigns(struct symbol
*sym
)
737 struct expression
*symbol
, *deref
, *assign
, *tmp
;
739 symbol
= symbol_expression(sym
);
740 FOR_EACH_PTR(sym
->initializer
->expr_list
, tmp
) {
741 if (tmp
->type
!= EXPR_IDENTIFIER
) /* how to handle arrays?? */
743 deref
= deref_expression(symbol
, '.', tmp
->expr_ident
);
744 assign
= assign_expression(deref
, tmp
->ident_expression
);
745 __split_expr(assign
);
746 } END_FOR_EACH_PTR(tmp
);
749 static void fake_assign_expr(struct symbol
*sym
)
751 struct expression
*assign
, *symbol
;
753 symbol
= symbol_expression(sym
);
754 assign
= assign_expression(symbol
, sym
->initializer
);
755 __split_expr(assign
);
758 static void do_initializer_stuff(struct symbol
*sym
)
760 if (!sym
->initializer
)
762 if (sym
->initializer
->type
== EXPR_INITIALIZER
)
763 fake_member_assigns(sym
);
765 fake_assign_expr(sym
);
768 static void split_declaration(struct symbol_list
*sym_list
)
772 FOR_EACH_PTR(sym_list
, sym
) {
773 __pass_to_client(sym
, DECLARATION_HOOK
);
774 do_initializer_stuff(sym
);
776 } END_FOR_EACH_PTR(sym
);
779 static void fake_global_assign(struct symbol
*sym
)
781 struct expression
*assign
, *symbol
;
783 if (!sym
->initializer
)
785 if (sym
->initializer
->type
== EXPR_INITIALIZER
) {
786 struct expression
*deref
, *tmp
;
788 symbol
= symbol_expression(sym
);
789 FOR_EACH_PTR(sym
->initializer
->expr_list
, tmp
) {
790 if (tmp
->type
!= EXPR_IDENTIFIER
) /* how to handle arrays?? */
792 deref
= deref_expression(symbol
, '.', tmp
->expr_ident
);
793 assign
= assign_expression(deref
, tmp
->ident_expression
);
794 __pass_to_client(assign
, GLOBAL_ASSIGNMENT_HOOK
);
795 } END_FOR_EACH_PTR(tmp
);
797 symbol
= symbol_expression(sym
);
798 assign
= assign_expression(symbol
, sym
->initializer
);
799 __pass_to_client(assign
, GLOBAL_ASSIGNMENT_HOOK
);
803 static void split_function(struct symbol
*sym
)
805 struct symbol
*base_type
= get_base_type(sym
);
809 line_func_start
= base_type
->stmt
->pos
.line
;
811 cur_func
= sym
->ident
->name
;
812 __smatch_lineno
= sym
->pos
.line
;
815 sm_debug("new function: %s\n", cur_func
);
817 if (option_two_passes
) {
821 __pass_to_client(sym
, FUNC_DEF_HOOK
);
822 __pass_to_client(sym
, AFTER_DEF_HOOK
);
823 __split_stmt(base_type
->stmt
);
824 __split_stmt(base_type
->inline_stmt
);
830 __pass_to_client(sym
, FUNC_DEF_HOOK
);
831 __pass_to_client(sym
, AFTER_DEF_HOOK
);
832 __split_stmt(base_type
->stmt
);
833 __split_stmt(base_type
->inline_stmt
);
834 __pass_to_client(sym
, END_FUNC_HOOK
);
838 free_data_info_allocs();
839 free_expression_stack(&switch_expr_stack
);
840 __free_ptr_list((struct ptr_list
**)&big_statement_stack
);
841 __bail_on_rest_of_function
= 0;
844 static struct symbol_list
*inlines_called
;
845 static void add_inline_function(struct symbol
*sym
)
847 static struct symbol_list
*already_added
;
850 FOR_EACH_PTR(already_added
, tmp
) {
853 } END_FOR_EACH_PTR(tmp
);
855 add_ptr_list(&already_added
, sym
);
856 add_ptr_list(&inlines_called
, sym
);
859 static void process_inlines()
863 FOR_EACH_PTR(inlines_called
, tmp
) {
865 } END_FOR_EACH_PTR(tmp
);
866 free_ptr_list(&inlines_called
);
869 static void split_functions(struct symbol_list
*sym_list
)
873 FOR_EACH_PTR(sym_list
, sym
) {
874 set_position(sym
->pos
);
875 if (sym
->type
== SYM_NODE
&& get_base_type(sym
)->type
== SYM_FN
) {
879 __pass_to_client(sym
, BASE_HOOK
);
880 fake_global_assign(sym
);
882 } END_FOR_EACH_PTR(sym
);
883 __pass_to_client_no_data(END_FILE_HOOK
);
886 void smatch(int argc
, char **argv
)
889 struct string_list
*filelist
= NULL
;
890 struct symbol_list
*sym_list
;
893 printf("Usage: smatch [--debug] <filename.c>\n");
896 sparse_initialize(argc
, argv
, &filelist
);
897 FOR_EACH_PTR_NOTAG(filelist
, base_file
) {
898 if (option_file_output
) {
901 snprintf(buf
, sizeof(buf
), "%s.smatch", base_file
);
902 sm_outfd
= fopen(buf
, "w");
904 printf("Error: Cannot open %s\n", base_file
);
908 sym_list
= sparse_keep_tokens(base_file
);
909 split_functions(sym_list
);
910 } END_FOR_EACH_PTR_NOTAG(base_file
);