*new* check_check_deref.c: checking for null inconsistently
[smatch.git] / smatch_flow.c
blobcd1495e44f757a229045276e6e92b51f1a47f266
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 static int expr_stmt_count;
30 static struct expression_list *switch_expr_stack = NULL;
31 static struct statement *next_stmt;
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 get_func_pos(void) { return __smatch_lineno - line_func_start; }
40 int inside_loop(void) { return !!loop_count; }
41 int in_expression_statement(void) { return !!expr_stmt_count; }
42 struct statement *get_next_stmt(void) { return next_stmt; }
44 static void split_symlist(struct symbol_list *sym_list);
45 static void split_declaration(struct symbol_list *sym_list);
46 static void split_expr_list(struct expression_list *expr_list);
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)
55 if (option_full_path)
56 return full_filename;
57 return filename;
60 static void set_position(struct expression *expr)
62 int len;
63 static int prev_stream = -1;
65 __smatch_lineno = expr->pos.line;
67 if (expr->pos.stream == prev_stream)
68 return;
70 filename = stream_name(expr->pos.stream);
72 free(full_filename);
73 pathname = getcwd(NULL, 0);
74 if (pathname) {
75 len = strlen(pathname) + 1 + strlen(filename) + 1;
76 full_filename = malloc(len);
77 snprintf(full_filename, len, "%s/%s", pathname, filename);
78 } else {
79 full_filename = alloc_string(filename);
81 free(pathname);
84 void __split_expr(struct expression *expr)
86 if (!expr)
87 return;
89 // printf("%d Debug expr_type %d %s\n", get_lineno(), expr->type, show_special(expr->op));
91 push_expression(&big_expression_stack, expr);
92 set_position(expr);
93 __pass_to_client(expr, EXPR_HOOK);
95 switch (expr->type) {
96 case EXPR_PREOP:
97 if (expr->op == '*')
98 __pass_to_client(expr, DEREF_HOOK);
99 case EXPR_POSTOP:
100 __pass_to_client(expr, OP_HOOK);
101 __split_expr(expr->unop);
102 break;
103 case EXPR_STATEMENT:
104 expr_stmt_count++;
105 __split_stmt(expr->statement);
106 expr_stmt_count--;
107 break;
108 case EXPR_BINOP:
109 __pass_to_client(expr, BINOP_HOOK);
110 case EXPR_LOGICAL:
111 case EXPR_COMMA:
112 case EXPR_COMPARE:
113 __split_expr(expr->left);
114 __split_expr(expr->right);
115 break;
116 case EXPR_ASSIGNMENT: {
117 struct expression *tmp;
119 /* foo = !bar() */
120 if (__handle_condition_assigns(expr))
121 break;
123 /* foo = (x < 5 ? foo : 5); */
124 if (__handle_select_assigns(expr))
125 break;
127 __split_expr(expr->right);
128 __pass_to_client(expr, ASSIGNMENT_HOOK);
129 tmp = strip_expr(expr->right);
130 if (tmp->type == EXPR_CALL)
131 __pass_to_client(expr, CALL_ASSIGNMENT_HOOK);
132 __split_expr(expr->left);
133 break;
135 case EXPR_DEREF:
136 __pass_to_client(expr, DEREF_HOOK);
137 __split_expr(expr->deref);
138 break;
139 case EXPR_SLICE:
140 __split_expr(expr->base);
141 break;
142 case EXPR_CAST:
143 case EXPR_FORCE_CAST:
144 __split_expr(expr->cast_expression);
145 break;
146 case EXPR_SIZEOF:
147 /* there isn't anything to pass a client from inside a sizeof() */
148 break;
149 case EXPR_CONDITIONAL:
150 case EXPR_SELECT:
151 __split_whole_condition(expr->conditional);
152 __split_expr(expr->cond_true);
153 __push_true_states();
154 __use_false_states();
155 __split_expr(expr->cond_false);
156 __merge_true_states();
157 break;
158 case EXPR_CALL:
159 split_expr_list(expr->args);
160 __split_expr(expr->fn);
161 __pass_to_client(expr, FUNCTION_CALL_HOOK);
162 break;
163 case EXPR_INITIALIZER:
164 split_expr_list(expr->expr_list);
165 break;
166 case EXPR_IDENTIFIER:
167 __split_expr(expr->ident_expression);
168 break;
169 case EXPR_INDEX:
170 __split_expr(expr->idx_expression);
171 break;
172 case EXPR_POS:
173 __split_expr(expr->init_expr);
174 break;
175 case EXPR_SYMBOL:
176 __pass_to_client(expr, SYM_HOOK);
177 break;
178 case EXPR_STRING:
179 __pass_to_client(expr, STRING_HOOK);
180 break;
181 default:
182 break;
184 pop_expression(&big_expression_stack);
187 static int is_forever_loop(struct statement *stmt)
190 struct expression *expr;
192 expr = strip_expr(stmt->iterator_pre_condition);
193 if (!expr)
194 expr = stmt->iterator_post_condition;
195 if (!expr) {
196 /* this is a for(;;) loop... */
197 return 1;
200 if (expr->type == EXPR_VALUE && expr->value == 1) {
201 return 1;
204 return 0;
207 static int loop_num;
208 static char *get_loop_name(int num)
210 char buf[256];
212 snprintf(buf, 255, "-loop%d", num);
213 buf[255] = '\0';
214 return alloc_sname(buf);;
218 * Pre Loops are while and for loops.
221 static void handle_pre_loop(struct statement *stmt)
223 int once_through; /* we go through the loop at least once */
224 struct sm_state *extra_sm = NULL;
225 int unchanged = 0;
226 char *loop_name;
227 struct state_list *slist = NULL;
228 struct sm_state *sm = NULL;
230 loop_name = get_loop_name(loop_num);
231 loop_num++;
233 __split_stmt(stmt->iterator_pre_statement);
235 once_through = implied_condition_true(stmt->iterator_pre_condition);
237 loop_count++;
238 __push_continues();
239 __push_breaks();
241 __merge_gotos(loop_name);
243 extra_sm = __extra_handle_canonical_loops(stmt, &slist);
244 __in_pre_condition++;
245 __split_whole_condition(stmt->iterator_pre_condition);
246 __in_pre_condition--;
247 FOR_EACH_PTR(slist, sm) {
248 set_state(sm->owner, sm->name, sm->sym, sm->state);
249 } END_FOR_EACH_PTR(sm);
250 free_slist(&slist);
251 if (extra_sm)
252 extra_sm = get_sm_state(extra_sm->owner, extra_sm->name, extra_sm->sym);
254 if (option_assume_loops)
255 once_through = 1;
257 __split_stmt(stmt->iterator_statement);
258 __warn_on_silly_pre_loops();
259 if (is_forever_loop(stmt)) {
260 __save_gotos(loop_name);
261 /* forever loops don't have an iterator_post_statement */
262 __discard_continues();
263 __discard_false_states();
264 __use_breaks();
265 } else {
266 __merge_continues();
267 unchanged = __iterator_unchanged(extra_sm);
268 __split_stmt(stmt->iterator_post_statement);
269 __save_gotos(loop_name);
270 __split_whole_condition(stmt->iterator_pre_condition);
271 nullify_path();
272 __merge_false_states();
273 if (once_through) {
274 __discard_false_states();
275 } else {
276 __merge_false_states();
279 if (extra_sm && unchanged)
280 __extra_pre_loop_hook_after(extra_sm,
281 stmt->iterator_post_statement,
282 stmt->iterator_pre_condition);
283 __merge_breaks();
285 loop_count--;
289 * Post loops are do {} while();
291 static void handle_post_loop(struct statement *stmt)
293 char *loop_name;
295 loop_name = get_loop_name(loop_num);
296 loop_num++;
297 loop_count++;
299 __push_continues();
300 __push_breaks();
301 __merge_gotos(loop_name);
302 __split_stmt(stmt->iterator_statement);
303 __merge_continues();
304 if (!is_zero(stmt->iterator_post_condition))
305 __save_gotos(loop_name);
307 if (is_forever_loop(stmt)) {
308 __use_breaks();
309 } else {
310 __split_whole_condition(stmt->iterator_post_condition);
311 __use_false_states();
312 __merge_breaks();
314 loop_count--;
317 static int empty_statement(struct statement *stmt)
319 if (!stmt)
320 return 0;
321 if (stmt->type == STMT_EXPRESSION && !stmt->expression)
322 return 1;
323 return 0;
326 static struct statement *last_stmt;
327 static int is_last_stmt(struct statement *stmt)
329 if (stmt == last_stmt)
330 return 1;
331 return 0;
334 static void print_unreached_initializers(struct symbol_list *sym_list)
336 struct symbol *sym;
338 FOR_EACH_PTR(sym_list, sym) {
339 if(sym->initializer)
340 sm_msg("info: '%s' is not actually initialized (unreached code).",
341 (sym->ident ? sym->ident->name : "this variable"));
342 } END_FOR_EACH_PTR(sym);
345 static void print_unreached(struct statement *stmt)
348 static int print = 1;
350 if (!__path_is_null()) {
351 print = 1;
352 return;
354 if (!print)
355 return;
357 switch (stmt->type) {
358 case STMT_COMPOUND: /* after a switch before a case stmt */
359 case STMT_RANGE:
360 case STMT_CASE:
361 case STMT_LABEL:
362 return;
363 case STMT_DECLARATION: /* switch (x) { int a; case foo: ... */
364 print_unreached_initializers(stmt->declaration);
365 return;
366 case STMT_RETURN: /* gcc complains if you don't have a return statement */
367 if (is_last_stmt(stmt))
368 return;
369 break;
370 case STMT_GOTO:
371 if (!option_spammy)
372 return;
373 break;
374 default:
375 break;
377 if (!option_spammy && empty_statement(stmt))
378 return;
379 sm_msg("info: ignoring unreachable code.");
380 print = 0;
383 void __split_stmt(struct statement *stmt)
385 if (!stmt)
386 return;
388 if (out_of_memory() || __bail_on_rest_of_function) {
389 static char *printed = NULL;
391 if (printed != cur_func)
392 sm_msg("Function too hairy. Giving up.");
393 printed = cur_func;
394 return;
397 add_ptr_list(&big_statement_stack, stmt);
398 free_expression_stack(&big_expression_stack);
399 __smatch_lineno = stmt->pos.line;
400 print_unreached(stmt);
401 __pass_to_client(stmt, STMT_HOOK);
403 switch (stmt->type) {
404 case STMT_DECLARATION:
405 split_declaration(stmt->declaration);
406 return;
407 case STMT_RETURN:
408 __split_expr(stmt->ret_value);
409 __pass_to_client(stmt->ret_value, RETURN_HOOK);
410 nullify_path();
411 return;
412 case STMT_EXPRESSION:
413 __split_expr(stmt->expression);
414 return;
415 case STMT_COMPOUND: {
416 struct statement *tmp;
417 struct statement *prev = NULL;
419 if (!last_stmt)
420 last_stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
421 __push_scope_hooks();
422 FOR_EACH_PTR(stmt->stmts, tmp) {
423 if (!prev) {
424 next_stmt = tmp;
425 prev = tmp;
426 continue;
428 next_stmt = tmp;
429 __split_stmt(prev);
430 prev = tmp;
431 } END_FOR_EACH_PTR(tmp);
432 __split_stmt(prev);
433 __call_scope_hooks();
434 return;
436 case STMT_IF:
437 if (known_condition_true(stmt->if_conditional)) {
438 __split_stmt(stmt->if_true);
439 return;
441 if (known_condition_false(stmt->if_conditional)) {
442 __split_stmt(stmt->if_false);
443 return;
445 if (option_known_conditions &&
446 implied_condition_true(stmt->if_conditional)) {
447 sm_info("this condition is true.");
448 __split_stmt(stmt->if_true);
449 return;
451 if (option_known_conditions &&
452 implied_condition_false(stmt->if_conditional)) {
453 sm_info("this condition is false.");
454 __split_stmt(stmt->if_false);
455 return;
457 __split_whole_condition(stmt->if_conditional);
458 __split_stmt(stmt->if_true);
459 if (empty_statement(stmt->if_true))
460 sm_msg("warn: if();");
461 __push_true_states();
462 __use_false_states();
463 __split_stmt(stmt->if_false);
464 __merge_true_states();
465 return;
466 case STMT_ITERATOR:
467 if (stmt->iterator_pre_condition)
468 handle_pre_loop(stmt);
469 else if (stmt->iterator_post_condition)
470 handle_post_loop(stmt);
471 else {
472 // these are for(;;) type loops.
473 handle_pre_loop(stmt);
475 return;
476 case STMT_SWITCH:
477 __split_expr(stmt->switch_expression);
478 push_expression(&switch_expr_stack, stmt->switch_expression);
479 __save_switch_states(top_expression(switch_expr_stack));
480 nullify_path();
481 __push_default();
482 __push_breaks();
483 __split_stmt(stmt->switch_statement);
484 if (!__pop_default())
485 __merge_switches(top_expression(switch_expr_stack),
486 NULL);
487 __discard_switches();
488 __merge_breaks();
489 pop_expression(&switch_expr_stack);
490 return;
491 case STMT_CASE:
492 __merge_switches(top_expression(switch_expr_stack),
493 stmt->case_expression);
494 __pass_case_to_client(top_expression(switch_expr_stack),
495 stmt->case_expression);
496 if (!stmt->case_expression)
497 __set_default();
498 __split_expr(stmt->case_expression);
499 __split_expr(stmt->case_to);
500 __split_stmt(stmt->case_statement);
501 return;
502 case STMT_LABEL:
503 if (stmt->label &&
504 stmt->label->type == SYM_LABEL &&
505 stmt->label->ident) {
506 loop_count = 1000000;
507 __merge_gotos(stmt->label->ident->name);
509 __split_stmt(stmt->label_statement);
510 return;
511 case STMT_GOTO:
512 __split_expr(stmt->goto_expression);
513 if (stmt->goto_label && stmt->goto_label->type == SYM_NODE) {
514 if (!strcmp(stmt->goto_label->ident->name, "break")) {
515 __process_breaks();
516 } else if (!strcmp(stmt->goto_label->ident->name,
517 "continue")) {
518 __process_continues();
520 } else if (stmt->goto_label &&
521 stmt->goto_label->type == SYM_LABEL &&
522 stmt->goto_label->ident) {
523 __save_gotos(stmt->goto_label->ident->name);
525 nullify_path();
526 return;
527 case STMT_NONE:
528 return;
529 case STMT_ASM:
530 __split_expr(stmt->asm_string);
531 split_expr_list(stmt->asm_outputs);
532 split_expr_list(stmt->asm_inputs);
533 split_expr_list(stmt->asm_clobbers);
534 return;
535 case STMT_CONTEXT:
536 return;
537 case STMT_RANGE:
538 __split_expr(stmt->range_expression);
539 __split_expr(stmt->range_low);
540 __split_expr(stmt->range_high);
541 return;
545 static void split_expr_list(struct expression_list *expr_list)
547 struct expression *expr;
548 FOR_EACH_PTR(expr_list, expr) {
549 __split_expr(expr);
550 } END_FOR_EACH_PTR(expr);
554 static void split_sym(struct symbol *sym)
556 if (!sym)
557 return;
558 if (!(sym->namespace & NS_SYMBOL))
559 return;
561 __split_stmt(sym->stmt);
562 __split_expr(sym->array_size);
563 split_symlist(sym->arguments);
564 split_symlist(sym->symbol_list);
565 __split_stmt(sym->inline_stmt);
566 split_symlist(sym->inline_symbol_list);
569 static void split_symlist(struct symbol_list *sym_list)
571 struct symbol *sym;
573 FOR_EACH_PTR(sym_list, sym) {
574 split_sym(sym);
575 } END_FOR_EACH_PTR(sym);
578 static struct expression *fake_assign_expr(struct symbol *sym)
580 struct expression *e_assign, *e_symbol;
582 e_assign = alloc_expression(sym->initializer->pos, EXPR_ASSIGNMENT);
583 e_symbol = alloc_expression(sym->initializer->pos, EXPR_SYMBOL);
584 e_assign->op = (int)'=';
585 e_symbol->symbol = sym;
586 e_symbol->symbol_name = sym->ident;
587 e_assign->left = e_symbol;
588 e_assign->right = sym->initializer;
589 return e_assign;
592 static void do_initializer_stuff(struct symbol *sym)
594 struct expression *assign;
596 if(!sym->initializer)
597 return;
598 assign = fake_assign_expr(sym);
599 __split_expr(assign);
602 static void split_declaration(struct symbol_list *sym_list)
604 struct symbol *sym;
606 FOR_EACH_PTR(sym_list, sym) {
607 __pass_to_client(sym, DECLARATION_HOOK);
608 do_initializer_stuff(sym);
609 split_sym(sym);
610 } END_FOR_EACH_PTR(sym);
613 static void split_functions(struct symbol_list *sym_list)
615 struct symbol *sym;
617 FOR_EACH_PTR(sym_list, sym) {
618 struct symbol *base_type;
619 base_type = get_base_type(sym);
620 if (sym->type == SYM_NODE && base_type->type == SYM_FN) {
621 cur_func_sym = sym;
622 if (base_type->stmt)
623 line_func_start = base_type->stmt->pos.line;
624 if (sym->ident)
625 cur_func = sym->ident->name;
626 __smatch_lineno = sym->pos.line;
627 last_stmt = NULL;
628 loop_count = 0;
629 sm_debug("new function: %s\n", cur_func);
630 if (option_two_passes) {
631 __unnullify_path();
632 loop_num = 0;
633 final_pass = 0;
634 __pass_to_client(sym, FUNC_DEF_HOOK);
635 __split_stmt(base_type->stmt);
636 nullify_path();
638 __unnullify_path();
639 loop_num = 0;
640 final_pass = 1;
641 __pass_to_client(sym, FUNC_DEF_HOOK);
642 __split_stmt(base_type->stmt);
643 __pass_to_client(sym, END_FUNC_HOOK);
644 cur_func = NULL;
645 line_func_start = 0;
646 clear_all_states();
647 free_data_info_allocs();
648 free_expression_stack(&switch_expr_stack);
649 __free_ptr_list((struct ptr_list **)&big_statement_stack);
650 __bail_on_rest_of_function = 0;
651 } else {
652 __pass_to_client(sym, BASE_HOOK);
654 } END_FOR_EACH_PTR(sym);
655 __pass_to_client_no_data(END_FILE_HOOK);
658 void smatch (int argc, char **argv)
661 struct string_list *filelist = NULL;
662 struct symbol_list *sym_list;
663 char *file;
665 if (argc < 2) {
666 printf("Usage: smatch [--debug] <filename.c>\n");
667 exit(1);
669 sparse_initialize(argc, argv, &filelist);
670 FOR_EACH_PTR_NOTAG(filelist, file) {
671 sym_list = __sparse(file);
672 split_functions(sym_list);
673 } END_FOR_EACH_PTR_NOTAG(file);