buf_size: remove memset() and memmove()
[smatch.git] / smatch_flow.c
blob31fe2688b7cf14b4224c3c19faff8a169c3cbb93
1 /*
2 * sparse/smatch_flow.c
4 * Copyright (C) 2006,2008 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
10 #define _GNU_SOURCE 1
11 #include <unistd.h>
12 #include <stdio.h>
13 #include "token.h"
14 #include "smatch.h"
15 #include "smatch_expression_stacks.h"
16 #include "smatch_extra.h"
17 #include "smatch_slist.h"
19 int final_pass;
21 static int __smatch_lineno = 0;
23 static const char *filename;
24 static char *pathname;
25 static char *full_filename;
26 static char *cur_func;
27 static int line_func_start;
28 static int loop_count;
29 int __expr_stmt_count;
30 static struct expression_list *switch_expr_stack = NULL;
32 struct expression_list *big_expression_stack;
33 struct statement_list *big_statement_stack;
34 int __in_pre_condition = 0;
35 int __bail_on_rest_of_function = 0;
36 char *get_function(void) { return cur_func; }
37 int get_lineno(void) { return __smatch_lineno; }
38 int get_func_pos(void) { return __smatch_lineno - line_func_start; }
39 int inside_loop(void) { return !!loop_count; }
40 int in_expression_statement(void) { return !!__expr_stmt_count; }
42 static void split_symlist(struct symbol_list *sym_list);
43 static void split_declaration(struct symbol_list *sym_list);
44 static void split_expr_list(struct expression_list *expr_list);
45 static void add_inline_function(struct symbol *sym);
47 int option_assume_loops = 0;
48 int option_known_conditions = 0;
49 int option_two_passes = 0;
50 struct symbol *cur_func_sym = NULL;
52 const char *get_filename(void)
54 if (option_full_path)
55 return full_filename;
56 return filename;
59 static void set_position(struct expression *expr)
61 int len;
62 static int prev_stream = -1;
64 __smatch_lineno = expr->pos.line;
66 if (expr->pos.stream == prev_stream)
67 return;
69 filename = stream_name(expr->pos.stream);
71 free(full_filename);
72 pathname = getcwd(NULL, 0);
73 if (pathname) {
74 len = strlen(pathname) + 1 + strlen(filename) + 1;
75 full_filename = malloc(len);
76 snprintf(full_filename, len, "%s/%s", pathname, filename);
77 } else {
78 full_filename = alloc_string(filename);
80 free(pathname);
83 static int is_inline_func(struct expression *expr)
85 if (expr->type != EXPR_SYMBOL || !expr->symbol)
86 return 0;
87 if (expr->symbol->ctype.modifiers & MOD_INLINE)
88 return 1;
89 return 0;
92 void __split_expr(struct expression *expr)
94 if (!expr)
95 return;
97 // sm_msg(" Debug expr_type %d %s", expr->type, show_special(expr->op));
99 push_expression(&big_expression_stack, expr);
100 set_position(expr);
101 __pass_to_client(expr, EXPR_HOOK);
103 switch (expr->type) {
104 case EXPR_PREOP:
105 if (expr->op == '*')
106 __pass_to_client(expr, DEREF_HOOK);
107 case EXPR_POSTOP:
108 __pass_to_client(expr, OP_HOOK);
109 __split_expr(expr->unop);
110 break;
111 case EXPR_STATEMENT:
112 __expr_stmt_count++;
113 __split_stmt(expr->statement);
114 __expr_stmt_count--;
115 break;
116 case EXPR_LOGICAL:
117 case EXPR_COMPARE:
118 __pass_to_client(expr, LOGIC_HOOK);
119 __handle_logic(expr);
120 break;
121 case EXPR_BINOP:
122 __pass_to_client(expr, BINOP_HOOK);
123 case EXPR_COMMA:
124 __split_expr(expr->left);
125 __split_expr(expr->right);
126 break;
127 case EXPR_ASSIGNMENT: {
128 struct expression *tmp;
130 /* foo = !bar() */
131 if (__handle_condition_assigns(expr))
132 break;
134 /* foo = (x < 5 ? foo : 5); */
135 if (__handle_select_assigns(expr))
136 break;
138 /* foo = ({frob(); frob(); frob(); 1;}) */
139 if (__handle_expr_statement_assigns(expr))
140 break;
142 __split_expr(expr->right);
143 __pass_to_client(expr, ASSIGNMENT_HOOK);
144 tmp = strip_expr(expr->right);
145 if (tmp->type == EXPR_CALL)
146 __pass_to_client(expr, CALL_ASSIGNMENT_HOOK);
147 __split_expr(expr->left);
148 break;
150 case EXPR_DEREF:
151 __pass_to_client(expr, DEREF_HOOK);
152 __split_expr(expr->deref);
153 break;
154 case EXPR_SLICE:
155 __split_expr(expr->base);
156 break;
157 case EXPR_CAST:
158 case EXPR_FORCE_CAST:
159 __split_expr(expr->cast_expression);
160 break;
161 case EXPR_SIZEOF:
162 /* there isn't anything to pass a client from inside a sizeof() */
163 break;
164 case EXPR_CONDITIONAL:
165 case EXPR_SELECT:
166 __split_whole_condition(expr->conditional);
167 __split_expr(expr->cond_true);
168 __push_true_states();
169 __use_false_states();
170 __split_expr(expr->cond_false);
171 __merge_true_states();
172 break;
173 case EXPR_CALL:
174 split_expr_list(expr->args);
175 __split_expr(expr->fn);
176 if (is_inline_func(expr->fn))
177 add_inline_function(expr->fn->symbol);
178 __pass_to_client(expr, FUNCTION_CALL_HOOK);
179 break;
180 case EXPR_INITIALIZER:
181 split_expr_list(expr->expr_list);
182 break;
183 case EXPR_IDENTIFIER:
184 __split_expr(expr->ident_expression);
185 break;
186 case EXPR_INDEX:
187 __split_expr(expr->idx_expression);
188 break;
189 case EXPR_POS:
190 __split_expr(expr->init_expr);
191 break;
192 case EXPR_SYMBOL:
193 __pass_to_client(expr, SYM_HOOK);
194 break;
195 case EXPR_STRING:
196 __pass_to_client(expr, STRING_HOOK);
197 break;
198 default:
199 break;
201 pop_expression(&big_expression_stack);
204 static int is_forever_loop(struct statement *stmt)
207 struct expression *expr;
209 expr = strip_expr(stmt->iterator_pre_condition);
210 if (!expr)
211 expr = stmt->iterator_post_condition;
212 if (!expr) {
213 /* this is a for(;;) loop... */
214 return 1;
217 if (expr->type == EXPR_VALUE && expr->value == 1) {
218 return 1;
221 return 0;
224 static int loop_num;
225 static char *get_loop_name(int num)
227 char buf[256];
229 snprintf(buf, 255, "-loop%d", num);
230 buf[255] = '\0';
231 return alloc_sname(buf);;
235 * Pre Loops are while and for loops.
238 static void handle_pre_loop(struct statement *stmt)
240 int once_through; /* we go through the loop at least once */
241 struct sm_state *extra_sm = NULL;
242 int unchanged = 0;
243 char *loop_name;
244 struct state_list *slist = NULL;
245 struct sm_state *sm = NULL;
247 loop_name = get_loop_name(loop_num);
248 loop_num++;
250 __split_stmt(stmt->iterator_pre_statement);
252 once_through = implied_condition_true(stmt->iterator_pre_condition);
254 loop_count++;
255 __push_continues();
256 __push_breaks();
258 __merge_gotos(loop_name);
260 extra_sm = __extra_handle_canonical_loops(stmt, &slist);
261 __in_pre_condition++;
262 __split_whole_condition(stmt->iterator_pre_condition);
263 __in_pre_condition--;
264 FOR_EACH_PTR(slist, sm) {
265 set_state(sm->owner, sm->name, sm->sym, sm->state);
266 } END_FOR_EACH_PTR(sm);
267 free_slist(&slist);
268 if (extra_sm)
269 extra_sm = get_sm_state(extra_sm->owner, extra_sm->name, extra_sm->sym);
271 if (option_assume_loops)
272 once_through = 1;
274 __split_stmt(stmt->iterator_statement);
275 __warn_on_silly_pre_loops();
276 if (is_forever_loop(stmt)) {
277 __save_gotos(loop_name);
278 /* forever loops don't have an iterator_post_statement */
279 __discard_continues();
280 __discard_false_states();
281 __use_breaks();
282 } else {
283 __merge_continues();
284 unchanged = __iterator_unchanged(extra_sm);
285 __split_stmt(stmt->iterator_post_statement);
286 __save_gotos(loop_name);
287 __split_whole_condition(stmt->iterator_pre_condition);
288 nullify_path();
289 __merge_false_states();
290 if (once_through) {
291 __discard_false_states();
292 } else {
293 __merge_false_states();
296 if (extra_sm && unchanged)
297 __extra_pre_loop_hook_after(extra_sm,
298 stmt->iterator_post_statement,
299 stmt->iterator_pre_condition);
300 __merge_breaks();
302 loop_count--;
306 * Post loops are do {} while();
308 static void handle_post_loop(struct statement *stmt)
310 char *loop_name;
312 loop_name = get_loop_name(loop_num);
313 loop_num++;
314 loop_count++;
316 __push_continues();
317 __push_breaks();
318 __merge_gotos(loop_name);
319 __split_stmt(stmt->iterator_statement);
320 __merge_continues();
321 if (!is_zero(stmt->iterator_post_condition))
322 __save_gotos(loop_name);
324 if (is_forever_loop(stmt)) {
325 __use_breaks();
326 } else {
327 __split_whole_condition(stmt->iterator_post_condition);
328 __use_false_states();
329 __merge_breaks();
331 loop_count--;
334 static int empty_statement(struct statement *stmt)
336 if (!stmt)
337 return 0;
338 if (stmt->type == STMT_EXPRESSION && !stmt->expression)
339 return 1;
340 return 0;
343 static int last_stmt_on_same_line()
345 struct statement *stmt;
346 int i = 0;
348 FOR_EACH_PTR_REVERSE(big_statement_stack, stmt) {
349 if (!i++)
350 continue;
351 if (stmt->pos.line == get_lineno())
352 return 1;
353 return 0;
354 } END_FOR_EACH_PTR_REVERSE(stmt);
355 return 0;
358 static struct statement *last_stmt;
359 static int is_last_stmt(struct statement *stmt)
361 if (stmt == last_stmt)
362 return 1;
363 return 0;
366 static void print_unreached_initializers(struct symbol_list *sym_list)
368 struct symbol *sym;
370 FOR_EACH_PTR(sym_list, sym) {
371 if(sym->initializer)
372 sm_msg("info: '%s' is not actually initialized (unreached code).",
373 (sym->ident ? sym->ident->name : "this variable"));
374 } END_FOR_EACH_PTR(sym);
377 static void print_unreached(struct statement *stmt)
380 static int print = 1;
382 if (!__path_is_null()) {
383 print = 1;
384 return;
386 if (!print)
387 return;
389 switch (stmt->type) {
390 case STMT_COMPOUND: /* after a switch before a case stmt */
391 case STMT_RANGE:
392 case STMT_CASE:
393 case STMT_LABEL:
394 return;
395 case STMT_DECLARATION: /* switch (x) { int a; case foo: ... */
396 print_unreached_initializers(stmt->declaration);
397 return;
398 case STMT_RETURN: /* gcc complains if you don't have a return statement */
399 if (is_last_stmt(stmt))
400 return;
401 break;
402 case STMT_GOTO:
403 if (!option_spammy)
404 return;
405 break;
406 default:
407 break;
409 if (!option_spammy && empty_statement(stmt))
410 return;
411 sm_msg("info: ignoring unreachable code.");
412 print = 0;
415 static void split_asm_constraints(struct expression_list *expr_list)
417 struct expression *expr;
418 int state = 0;
420 FOR_EACH_PTR(expr_list, expr) {
421 switch (state) {
422 case 0: /* identifier */
423 case 1: /* constraint */
424 state++;
425 continue;
426 case 2: /* expression */
427 state = 0;
428 __split_expr(expr);
429 continue;
431 } END_FOR_EACH_PTR(expr);
434 void __split_stmt(struct statement *stmt)
436 if (!stmt)
437 return;
439 if (out_of_memory() || __bail_on_rest_of_function) {
440 static char *printed = NULL;
442 if (printed != cur_func)
443 sm_msg("Function too hairy. Giving up.");
444 printed = cur_func;
445 return;
448 add_ptr_list(&big_statement_stack, stmt);
449 free_expression_stack(&big_expression_stack);
450 __smatch_lineno = stmt->pos.line;
451 print_unreached(stmt);
452 __pass_to_client(stmt, STMT_HOOK);
454 switch (stmt->type) {
455 case STMT_DECLARATION:
456 split_declaration(stmt->declaration);
457 return;
458 case STMT_RETURN:
459 __split_expr(stmt->ret_value);
460 __pass_to_client(stmt->ret_value, RETURN_HOOK);
461 nullify_path();
462 return;
463 case STMT_EXPRESSION:
464 __split_expr(stmt->expression);
465 return;
466 case STMT_COMPOUND: {
467 struct statement *tmp;
469 if (!last_stmt)
470 last_stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
471 __push_scope_hooks();
472 FOR_EACH_PTR(stmt->stmts, tmp) {
473 __split_stmt(tmp);
474 } END_FOR_EACH_PTR(tmp);
475 __call_scope_hooks();
476 return;
478 case STMT_IF:
479 if (known_condition_true(stmt->if_conditional)) {
480 __split_stmt(stmt->if_true);
481 return;
483 if (known_condition_false(stmt->if_conditional)) {
484 __split_stmt(stmt->if_false);
485 return;
487 if (option_known_conditions &&
488 implied_condition_true(stmt->if_conditional)) {
489 sm_info("this condition is true.");
490 __split_stmt(stmt->if_true);
491 return;
493 if (option_known_conditions &&
494 implied_condition_false(stmt->if_conditional)) {
495 sm_info("this condition is false.");
496 __split_stmt(stmt->if_false);
497 return;
499 __split_whole_condition(stmt->if_conditional);
500 __split_stmt(stmt->if_true);
501 if (empty_statement(stmt->if_true) &&
502 last_stmt_on_same_line() &&
503 !get_macro_name(&stmt->if_true->pos))
504 sm_msg("warn: if();");
505 __push_true_states();
506 __use_false_states();
507 __split_stmt(stmt->if_false);
508 __merge_true_states();
509 return;
510 case STMT_ITERATOR:
511 if (stmt->iterator_pre_condition)
512 handle_pre_loop(stmt);
513 else if (stmt->iterator_post_condition)
514 handle_post_loop(stmt);
515 else {
516 // these are for(;;) type loops.
517 handle_pre_loop(stmt);
519 return;
520 case STMT_SWITCH:
521 __split_expr(stmt->switch_expression);
522 push_expression(&switch_expr_stack, stmt->switch_expression);
523 __save_switch_states(top_expression(switch_expr_stack));
524 nullify_path();
525 __push_default();
526 __push_breaks();
527 __split_stmt(stmt->switch_statement);
528 if (!__pop_default())
529 __merge_switches(top_expression(switch_expr_stack),
530 NULL);
531 __discard_switches();
532 __merge_breaks();
533 pop_expression(&switch_expr_stack);
534 return;
535 case STMT_CASE:
536 __merge_switches(top_expression(switch_expr_stack),
537 stmt->case_expression);
538 __pass_case_to_client(top_expression(switch_expr_stack),
539 stmt->case_expression);
540 if (!stmt->case_expression)
541 __set_default();
542 __split_expr(stmt->case_expression);
543 __split_expr(stmt->case_to);
544 __split_stmt(stmt->case_statement);
545 return;
546 case STMT_LABEL:
547 if (stmt->label &&
548 stmt->label->type == SYM_LABEL &&
549 stmt->label->ident) {
550 loop_count = 1000000;
551 __merge_gotos(stmt->label->ident->name);
553 __split_stmt(stmt->label_statement);
554 return;
555 case STMT_GOTO:
556 __split_expr(stmt->goto_expression);
557 if (stmt->goto_label && stmt->goto_label->type == SYM_NODE) {
558 if (!strcmp(stmt->goto_label->ident->name, "break")) {
559 __process_breaks();
560 } else if (!strcmp(stmt->goto_label->ident->name,
561 "continue")) {
562 __process_continues();
564 } else if (stmt->goto_label &&
565 stmt->goto_label->type == SYM_LABEL &&
566 stmt->goto_label->ident) {
567 __save_gotos(stmt->goto_label->ident->name);
569 nullify_path();
570 return;
571 case STMT_NONE:
572 return;
573 case STMT_ASM:
574 __split_expr(stmt->asm_string);
575 split_asm_constraints(stmt->asm_outputs);
576 split_asm_constraints(stmt->asm_inputs);
577 split_asm_constraints(stmt->asm_clobbers);
578 return;
579 case STMT_CONTEXT:
580 return;
581 case STMT_RANGE:
582 __split_expr(stmt->range_expression);
583 __split_expr(stmt->range_low);
584 __split_expr(stmt->range_high);
585 return;
589 static void split_expr_list(struct expression_list *expr_list)
591 struct expression *expr;
593 FOR_EACH_PTR(expr_list, expr) {
594 __split_expr(expr);
595 } END_FOR_EACH_PTR(expr);
599 static void split_sym(struct symbol *sym)
601 if (!sym)
602 return;
603 if (!(sym->namespace & NS_SYMBOL))
604 return;
606 __split_stmt(sym->stmt);
607 __split_expr(sym->array_size);
608 split_symlist(sym->arguments);
609 split_symlist(sym->symbol_list);
610 __split_stmt(sym->inline_stmt);
611 split_symlist(sym->inline_symbol_list);
614 static void split_symlist(struct symbol_list *sym_list)
616 struct symbol *sym;
618 FOR_EACH_PTR(sym_list, sym) {
619 split_sym(sym);
620 } END_FOR_EACH_PTR(sym);
623 static struct expression *fake_assign_expr(struct symbol *sym)
625 struct expression *e_assign, *e_symbol;
627 e_assign = alloc_expression(sym->initializer->pos, EXPR_ASSIGNMENT);
628 e_symbol = alloc_expression(sym->initializer->pos, EXPR_SYMBOL);
629 e_assign->op = (int)'=';
630 e_symbol->symbol = sym;
631 e_symbol->symbol_name = sym->ident;
632 e_assign->left = e_symbol;
633 e_assign->right = sym->initializer;
634 return e_assign;
637 static void do_initializer_stuff(struct symbol *sym)
639 struct expression *assign;
641 if(!sym->initializer)
642 return;
643 assign = fake_assign_expr(sym);
644 __split_expr(assign);
647 static void split_declaration(struct symbol_list *sym_list)
649 struct symbol *sym;
651 FOR_EACH_PTR(sym_list, sym) {
652 __pass_to_client(sym, DECLARATION_HOOK);
653 do_initializer_stuff(sym);
654 split_sym(sym);
655 } END_FOR_EACH_PTR(sym);
658 static void split_function(struct symbol *sym)
660 struct symbol *base_type = get_base_type(sym);
662 cur_func_sym = sym;
663 if (base_type->stmt)
664 line_func_start = base_type->stmt->pos.line;
665 if (sym->ident)
666 cur_func = sym->ident->name;
667 __smatch_lineno = sym->pos.line;
668 last_stmt = NULL;
669 loop_count = 0;
670 sm_debug("new function: %s\n", cur_func);
671 if (option_two_passes) {
672 __unnullify_path();
673 loop_num = 0;
674 final_pass = 0;
675 __pass_to_client(sym, FUNC_DEF_HOOK);
676 __split_stmt(base_type->stmt);
677 __split_stmt(base_type->inline_stmt);
678 nullify_path();
680 __unnullify_path();
681 loop_num = 0;
682 final_pass = 1;
683 __pass_to_client(sym, FUNC_DEF_HOOK);
684 __split_stmt(base_type->stmt);
685 __split_stmt(base_type->inline_stmt);
686 __pass_to_client(sym, END_FUNC_HOOK);
687 cur_func = NULL;
688 line_func_start = 0;
689 clear_all_states();
690 free_data_info_allocs();
691 free_expression_stack(&switch_expr_stack);
692 __free_ptr_list((struct ptr_list **)&big_statement_stack);
693 __bail_on_rest_of_function = 0;
696 static struct symbol_list *inlines_called;
697 static void add_inline_function(struct symbol *sym)
699 static struct symbol_list *already_added;
700 struct symbol *tmp;
702 FOR_EACH_PTR(already_added, tmp) {
703 if (tmp == sym)
704 return;
705 } END_FOR_EACH_PTR(tmp);
707 add_ptr_list(&already_added, sym);
708 add_ptr_list(&inlines_called, sym);
711 static void process_inlines()
713 struct symbol *tmp;
715 FOR_EACH_PTR(inlines_called, tmp) {
716 split_function(tmp);
717 } END_FOR_EACH_PTR(tmp);
718 free_ptr_list(&inlines_called);
721 static void split_functions(struct symbol_list *sym_list)
723 struct symbol *sym;
725 FOR_EACH_PTR(sym_list, sym) {
726 if (sym->type == SYM_NODE && get_base_type(sym)->type == SYM_FN) {
727 split_function(sym);
728 process_inlines();
729 } else {
730 __pass_to_client(sym, BASE_HOOK);
732 } END_FOR_EACH_PTR(sym);
733 __pass_to_client_no_data(END_FILE_HOOK);
736 void smatch (int argc, char **argv)
739 struct string_list *filelist = NULL;
740 struct symbol_list *sym_list;
741 char *file;
743 if (argc < 2) {
744 printf("Usage: smatch [--debug] <filename.c>\n");
745 exit(1);
747 sparse_initialize(argc, argv, &filelist);
748 FOR_EACH_PTR_NOTAG(filelist, file) {
749 sym_list = sparse_keep_tokens(file);
750 split_functions(sym_list);
751 } END_FOR_EACH_PTR_NOTAG(file);