?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
impossible: introduce is_impossible_path() to say if a path is reasonable
[smatch.git] / smatch_flow.c
blob2b27cb1ce41a90516298cd1c94cac065afdf6dd1
1 /*
2 * Copyright (C) 2006,2008 Dan Carpenter.
3 *
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.
8 *
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.
13 *
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
16 */
17
18 #define _GNU_SOURCE 1
19 #include <unistd.h>
20 #include <stdio.h>
21 #include "token.h"
22 #include "scope.h"
23 #include "smatch.h"
24 #include "smatch_expression_stacks.h"
25 #include "smatch_extra.h"
26 #include "smatch_slist.h"
27
28 int __in_fake_assign;
29 int final_pass;
30 int __inline_call;
31 struct expression *__inline_fn;
32
33 static int __smatch_lineno = 0;
34
35 static char *base_file;
36 static const char *filename;
37 static char *pathname;
38 static char *full_filename;
39 static char *cur_func;
40 static unsigned int loop_count;
41 static int last_goto_statement_handled;
42 int __expr_stmt_count;
43 int __in_function_def;
44 static struct expression_list *switch_expr_stack = NULL;
45 static struct expression_list *post_op_stack = NULL;
46
47 struct expression_list *big_expression_stack;
48 struct statement_list *big_statement_stack;
49 int __in_pre_condition = 0;
50 int __bail_on_rest_of_function = 0;
51 static struct timeval fn_start_time;
52 char *get_function(void) { return cur_func; }
53 int get_lineno(void) { return __smatch_lineno; }
54 int inside_loop(void) { return !!loop_count; }
55 int definitely_inside_loop(void) { return !!(loop_count & ~0x80000000); }
56 struct expression *get_switch_expr(void) { return top_expression(switch_expr_stack); }
57 int in_expression_statement(void) { return !!__expr_stmt_count; }
58
59 static void split_symlist(struct symbol_list *sym_list);
60 static void split_declaration(struct symbol_list *sym_list);
61 static void split_expr_list(struct expression_list *expr_list);
62 static void add_inline_function(struct symbol *sym);
63 static void parse_inline(struct expression *expr);
64
65 int option_assume_loops = 0;
66 int option_known_conditions = 0;
67 int option_two_passes = 0;
68 struct symbol *cur_func_sym = NULL;
69 struct stree *global_states;
70
71 long long valid_ptr_min = 4096;
72 long long valid_ptr_max = 2117777777;
73 sval_t valid_ptr_min_sval = {
74 .type = &ptr_ctype,
75 {.value = 4096},
76 };
77 sval_t valid_ptr_max_sval = {
78 .type = &ptr_ctype,
79 {.value = LONG_MAX - 100000},
80 };
81
82 static void set_valid_ptr_max(void)
83 {
84 if (type_bits(&ptr_ctype) == 32)
85 valid_ptr_max = 2117777777;
86 else if (type_bits(&ptr_ctype) == 64)
87 valid_ptr_max = 2117777777777777777LL;
88
89 valid_ptr_max_sval.value = valid_ptr_max;
90 }
91
92 int outside_of_function(void)
93 {
94 return cur_func_sym == NULL;
95 }
96
97 const char *get_filename(void)
98 {
99 if (option_info)
100 return base_file;
101 if (option_full_path)
102 return full_filename;
103 return filename;
104 }
105
106 const char *get_base_file(void)
107 {
108 return base_file;
109 }
110
111 static void set_position(struct position pos)
112 {
113 int len;
114 static int prev_stream = -1;
115
116 if (pos.stream == 0 && pos.line == 0)
117 return;
118
119 __smatch_lineno = pos.line;
120
121 if (pos.stream == prev_stream)
122 return;
123
124 filename = stream_name(pos.stream);
125
126 free(full_filename);
127 pathname = getcwd(NULL, 0);
128 if (pathname) {
129 len = strlen(pathname) + 1 + strlen(filename) + 1;
130 full_filename = malloc(len);
131 snprintf(full_filename, len, "%s/%s", pathname, filename);
132 } else {
133 full_filename = alloc_string(filename);
134 }
135 free(pathname);
136 }
137
138 int is_assigned_call(struct expression *expr)
139 {
140 struct expression *tmp;
141
142 FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
143 if (tmp->type == EXPR_ASSIGNMENT && strip_expr(tmp->right) == expr)
144 return 1;
145 if (tmp->pos.line < expr->pos.line)
146 return 0;
147 } END_FOR_EACH_PTR_REVERSE(tmp);
148 return 0;
149 }
150
151 static int is_inline_func(struct expression *expr)
152 {
153 if (expr->type != EXPR_SYMBOL || !expr->symbol)
154 return 0;
155 if (expr->symbol->ctype.modifiers & MOD_INLINE)
156 return 1;
157 return 0;
158 }
159
160 static int is_noreturn_func(struct expression *expr)
161 {
162 if (expr->type != EXPR_SYMBOL || !expr->symbol)
163 return 0;
164 if (expr->symbol->ctype.modifiers & MOD_NORETURN)
165 return 1;
166 return 0;
167 }
168
169 int inlinable(struct expression *expr)
170 {
171 struct symbol *sym;
172
173 if (__inline_fn) /* don't nest */
174 return 0;
175
176 if (expr->type != EXPR_SYMBOL || !expr->symbol)
177 return 0;
178 if (is_no_inline_function(expr->symbol->ident->name))
179 return 0;
180 sym = get_base_type(expr->symbol);
181 if (sym->stmt && sym->stmt->type == STMT_COMPOUND) {
182 if (ptr_list_size((struct ptr_list *)sym->stmt->stmts) <= 10)
183 return 1;
184 return 0;
185 }
186 if (sym->inline_stmt && sym->inline_stmt->type == STMT_COMPOUND) {
187 if (ptr_list_size((struct ptr_list *)sym->inline_stmt->stmts) <= 10)
188 return 1;
189 return 0;
190 }
191 return 0;
192 }
193
194 void __process_post_op_stack(void)
195 {
196 struct expression *expr;
197
198 FOR_EACH_PTR(post_op_stack, expr) {
199 __pass_to_client(expr, OP_HOOK);
200 } END_FOR_EACH_PTR(expr);
201
202 __free_ptr_list((struct ptr_list **)&post_op_stack);
203 }
204
205 static int handle_comma_assigns(struct expression *expr)
206 {
207 struct expression *right;
208 struct expression *assign;
209
210 right = strip_expr(expr->right);
211 if (right->type != EXPR_COMMA)
212 return 0;
213
214 __split_expr(right->left);
215 __process_post_op_stack();
216
217 assign = assign_expression(expr->left, right->right);
218 __split_expr(assign);
219
220 return 1;
221 }
222
223 void __split_expr(struct expression *expr)
224 {
225 if (!expr)
226 return;
227
228 // sm_msg(" Debug expr_type %d %s", expr->type, show_special(expr->op));
229
230 if (__in_fake_assign && expr->type != EXPR_ASSIGNMENT)
231 return;
232 if (__in_fake_assign >= 4) /* don't allow too much nesting */
233 return;
234
235 push_expression(&big_expression_stack, expr);
236 set_position(expr->pos);
237 __pass_to_client(expr, EXPR_HOOK);
238
239 switch (expr->type) {
240 case EXPR_PREOP:
241 if (expr->op == '*')
242 __pass_to_client(expr, DEREF_HOOK);
243 __split_expr(expr->unop);
244 __pass_to_client(expr, OP_HOOK);
245 break;
246 case EXPR_POSTOP:
247 __split_expr(expr->unop);
248 push_expression(&post_op_stack, expr);
249 break;
250 case EXPR_STATEMENT:
251 __expr_stmt_count++;
252 __split_stmt(expr->statement);
253 __expr_stmt_count--;
254 break;
255 case EXPR_LOGICAL:
256 case EXPR_COMPARE:
257 __pass_to_client(expr, LOGIC_HOOK);
258 __handle_logic(expr);
259 break;
260 case EXPR_BINOP:
261 __pass_to_client(expr, BINOP_HOOK);
262 case EXPR_COMMA:
263 __split_expr(expr->left);
264 __process_post_op_stack();
265 __split_expr(expr->right);
266 break;
267 case EXPR_ASSIGNMENT: {
268 struct expression *tmp;
269
270 if (!expr->right)
271 break;
272
273 __pass_to_client(expr, RAW_ASSIGNMENT_HOOK);
274
275 /* foo = !bar() */
276 if (__handle_condition_assigns(expr))
277 break;
278 /* foo = (x < 5 ? foo : 5); */
279 if (__handle_select_assigns(expr))
280 break;
281 /* foo = ({frob(); frob(); frob(); 1;}) */
282 if (__handle_expr_statement_assigns(expr))
283 break;
284 /* foo = (3, 4); */
285 if (handle_comma_assigns(expr))
286 break;
287
288 __split_expr(expr->right);
289 if (outside_of_function())
290 __pass_to_client(expr, GLOBAL_ASSIGNMENT_HOOK);
291 else
292 __pass_to_client(expr, ASSIGNMENT_HOOK);
293
294 __fake_struct_member_assignments(expr);
295
296 tmp = strip_expr(expr->right);
297 if (tmp->type == EXPR_CALL) {
298 __pass_to_client(expr, CALL_ASSIGNMENT_HOOK);
299 if (!is_fake_call(tmp))
300 __pass_to_client(tmp, FUNCTION_CALL_HOOK_AFTER);
301 }
302 if (get_macro_name(tmp->pos) &&
303 get_macro_name(expr->pos) != get_macro_name(tmp->pos))
304 __pass_to_client(expr, MACRO_ASSIGNMENT_HOOK);
305 __split_expr(expr->left);
306 break;
307 }
308 case EXPR_DEREF:
309 __pass_to_client(expr, DEREF_HOOK);
310 __split_expr(expr->deref);
311 break;
312 case EXPR_SLICE:
313 __split_expr(expr->base);
314 break;
315 case EXPR_CAST:
316 case EXPR_FORCE_CAST:
317 __pass_to_client(expr, CAST_HOOK);
318 __split_expr(expr->cast_expression);
319 break;
320 case EXPR_SIZEOF:
321 if (expr->cast_expression)
322 __pass_to_client(strip_parens(expr->cast_expression),
323 SIZEOF_HOOK);
324 break;
325 case EXPR_OFFSETOF:
326 case EXPR_ALIGNOF:
327 evaluate_expression(expr);
328 break;
329 case EXPR_CONDITIONAL:
330 case EXPR_SELECT:
331 if (known_condition_true(expr->conditional)) {
332 __split_expr(expr->cond_true);
333 break;
334 }
335 if (known_condition_false(expr->conditional)) {
336 __split_expr(expr->cond_false);
337 break;
338 }
339 __pass_to_client(expr, SELECT_HOOK);
340 __split_whole_condition(expr->conditional);
341 __split_expr(expr->cond_true);
342 __push_true_states();
343 __use_false_states();
344 __split_expr(expr->cond_false);
345 __merge_true_states();
346 break;
347 case EXPR_CALL:
348 if (sym_name_is("__builtin_constant_p", expr->fn))
349 break;
350 split_expr_list(expr->args);
351 __split_expr(expr->fn);
352 if (is_inline_func(expr->fn))
353 add_inline_function(expr->fn->symbol);
354 if (inlinable(expr->fn))
355 __inline_call = 1;
356 __process_post_op_stack();
357 __pass_to_client(expr, FUNCTION_CALL_HOOK);
358 __inline_call = 0;
359 if (inlinable(expr->fn)) {
360 parse_inline(expr);
361 }
362 __pass_to_client(expr, CALL_HOOK_AFTER_INLINE);
363 if (!is_assigned_call(expr))
364 __pass_to_client(expr, FUNCTION_CALL_HOOK_AFTER);
365 if (is_noreturn_func(expr->fn))
366 nullify_path();
367 break;
368 case EXPR_INITIALIZER:
369 split_expr_list(expr->expr_list);
370 break;
371 case EXPR_IDENTIFIER:
372 __split_expr(expr->ident_expression);
373 break;
374 case EXPR_INDEX:
375 __split_expr(expr->idx_expression);
376 break;
377 case EXPR_POS:
378 __split_expr(expr->init_expr);
379 break;
380 case EXPR_SYMBOL:
381 __pass_to_client(expr, SYM_HOOK);
382 break;
383 case EXPR_STRING:
384 __pass_to_client(expr, STRING_HOOK);
385 break;
386 default:
387 break;
388 };
389 pop_expression(&big_expression_stack);
390 }
391
392 static int is_forever_loop(struct statement *stmt)
393 {
394 struct expression *expr;
395
396 expr = strip_expr(stmt->iterator_pre_condition);
397 if (!expr)
398 expr = stmt->iterator_post_condition;
399 if (!expr) {
400 /* this is a for(;;) loop... */
401 return 1;
402 }
403
404 if (expr->type == EXPR_VALUE && expr->value == 1)
405 return 1;
406
407 return 0;
408 }
409
410 static int loop_num;
411 static char *get_loop_name(int num)
412 {
413 char buf[256];
414
415 snprintf(buf, 255, "-loop%d", num);
416 buf[255] = '\0';
417 return alloc_sname(buf);
418 }
419
420 /*
421 * Pre Loops are while and for loops.
422 */
423 static void handle_pre_loop(struct statement *stmt)
424 {
425 int once_through; /* we go through the loop at least once */
426 struct sm_state *extra_sm = NULL;
427 int unchanged = 0;
428 char *loop_name;
429 struct stree *stree = NULL;
430 struct sm_state *sm = NULL;
431
432 loop_name = get_loop_name(loop_num);
433 loop_num++;
434
435 __split_stmt(stmt->iterator_pre_statement);
436
437 once_through = implied_condition_true(stmt->iterator_pre_condition);
438
439 loop_count++;
440 __push_continues();
441 __push_breaks();
442
443 __merge_gotos(loop_name);
444
445 extra_sm = __extra_handle_canonical_loops(stmt, &stree);
446 __in_pre_condition++;
447 __pass_to_client(stmt, PRELOOP_HOOK);
448 __split_whole_condition(stmt->iterator_pre_condition);
449 __in_pre_condition--;
450 FOR_EACH_SM(stree, sm) {
451 set_state(sm->owner, sm->name, sm->sym, sm->state);
452 } END_FOR_EACH_SM(sm);
453 free_stree(&stree);
454 if (extra_sm)
455 extra_sm = get_sm_state(extra_sm->owner, extra_sm->name, extra_sm->sym);
456
457 if (option_assume_loops)
458 once_through = 1;
459
460 __split_stmt(stmt->iterator_statement);
461 __warn_on_silly_pre_loops();
462 if (is_forever_loop(stmt)) {
463 __merge_continues();
464 __save_gotos(loop_name);
465
466 __push_fake_cur_stree();
467 __split_stmt(stmt->iterator_post_statement);
468 stree = __pop_fake_cur_stree();
469
470 __discard_false_states();
471 __use_breaks();
472
473 if (!__path_is_null())
474 __merge_stree_into_cur(stree);
475 free_stree(&stree);
476 } else {
477 __merge_continues();
478 unchanged = __iterator_unchanged(extra_sm);
479 __split_stmt(stmt->iterator_post_statement);
480 __save_gotos(loop_name);
481 __in_pre_condition++;
482 __split_whole_condition(stmt->iterator_pre_condition);
483 __in_pre_condition--;
484 nullify_path();
485 __merge_false_states();
486 if (once_through)
487 __discard_false_states();
488 else
489 __merge_false_states();
490
491 if (extra_sm && unchanged)
492 __extra_pre_loop_hook_after(extra_sm,
493 stmt->iterator_post_statement,
494 stmt->iterator_pre_condition);
495 __merge_breaks();
496 }
497 loop_count--;
498 }
499
500 /*
501 * Post loops are do {} while();
502 */
503 static void handle_post_loop(struct statement *stmt)
504 {
505 char *loop_name;
506
507 loop_name = get_loop_name(loop_num);
508 loop_num++;
509 loop_count++;
510
511 __push_continues();
512 __push_breaks();
513 __merge_gotos(loop_name);
514 __split_stmt(stmt->iterator_statement);
515 __merge_continues();
516 if (!is_zero(stmt->iterator_post_condition))
517 __save_gotos(loop_name);
518
519 if (is_forever_loop(stmt)) {
520 __use_breaks();
521 } else {
522 __split_whole_condition(stmt->iterator_post_condition);
523 __use_false_states();
524 __merge_breaks();
525 }
526 loop_count--;
527 }
528
529 static int empty_statement(struct statement *stmt)
530 {
531 if (!stmt)
532 return 0;
533 if (stmt->type == STMT_EXPRESSION && !stmt->expression)
534 return 1;
535 return 0;
536 }
537
538 static int last_stmt_on_same_line(void)
539 {
540 struct statement *stmt;
541 int i = 0;
542
543 FOR_EACH_PTR_REVERSE(big_statement_stack, stmt) {
544 if (!i++)
545 continue;
546 if (stmt->pos.line == get_lineno())
547 return 1;
548 return 0;
549 } END_FOR_EACH_PTR_REVERSE(stmt);
550 return 0;
551 }
552
553 static void split_asm_constraints(struct expression_list *expr_list)
554 {
555 struct expression *expr;
556 int state = 0;
557
558 FOR_EACH_PTR(expr_list, expr) {
559 switch (state) {
560 case 0: /* identifier */
561 case 1: /* constraint */
562 state++;
563 continue;
564 case 2: /* expression */
565 state = 0;
566 __split_expr(expr);
567 continue;
568 }
569 } END_FOR_EACH_PTR(expr);
570 }
571
572 static int is_case_val(struct statement *stmt, sval_t sval)
573 {
574 sval_t case_sval;
575
576 if (stmt->type != STMT_CASE)
577 return 0;
578 if (!stmt->case_expression) {
579 __set_default();
580 return 1;
581 }
582 if (!get_value(stmt->case_expression, &case_sval))
583 return 0;
584 if (case_sval.value == sval.value)
585 return 1;
586 return 0;
587 }
588
589 static void split_known_switch(struct statement *stmt, sval_t sval)
590 {
591 struct statement *tmp;
592
593 __split_expr(stmt->switch_expression);
594
595 push_expression(&switch_expr_stack, stmt->switch_expression);
596 __save_switch_states(top_expression(switch_expr_stack));
597 nullify_path();
598 __push_default();
599 __push_breaks();
600
601 stmt = stmt->switch_statement;
602
603 __push_scope_hooks();
604 FOR_EACH_PTR(stmt->stmts, tmp) {
605 __smatch_lineno = tmp->pos.line;
606 if (is_case_val(tmp, sval)) {
607 __merge_switches(top_expression(switch_expr_stack),
608 stmt->case_expression);
609 __pass_case_to_client(top_expression(switch_expr_stack),
610 stmt->case_expression);
611 }
612 if (__path_is_null())
613 continue;
614 __split_stmt(tmp);
615 if (__path_is_null()) {
616 __set_default();
617 goto out;
618 }
619 } END_FOR_EACH_PTR(tmp);
620 out:
621 __call_scope_hooks();
622 if (!__pop_default())
623 __merge_switches(top_expression(switch_expr_stack),
624 NULL);
625 __discard_switches();
626 __merge_breaks();
627 pop_expression(&switch_expr_stack);
628 }
629
630 static int taking_too_long(void)
631 {
632 int ms;
633
634 ms = ms_since(&fn_start_time);
635 if (ms > 1000 * 60 * 5) /* five minutes */
636 return 1;
637 return 0;
638 }
639
640 static int is_last_stmt(struct statement *cur_stmt)
641 {
642 struct symbol *fn = get_base_type(cur_func_sym);
643 struct statement *stmt;
644
645 if (!fn)
646 return 0;
647 stmt = fn->stmt;
648 if (!stmt)
649 stmt = fn->inline_stmt;
650 if (!stmt || stmt->type != STMT_COMPOUND)
651 return 0;
652 stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
653 if (stmt && stmt->type == STMT_LABEL)
654 stmt = stmt->label_statement;
655 if (stmt == cur_stmt)
656 return 1;
657 return 0;
658 }
659
660 static void handle_backward_goto(struct statement *goto_stmt)
661 {
662 const char *goto_name, *label_name;
663 struct statement *func_stmt;
664 struct symbol *base_type = get_base_type(cur_func_sym);
665 struct statement *tmp;
666 int found = 0;
667
668 if (!option_info)
669 return;
670 if (last_goto_statement_handled)
671 return;
672 last_goto_statement_handled = 1;
673
674 if (!goto_stmt->goto_label ||
675 goto_stmt->goto_label->type != SYM_LABEL ||
676 !goto_stmt->goto_label->ident)
677 return;
678 goto_name = goto_stmt->goto_label->ident->name;
679
680 func_stmt = base_type->stmt;
681 if (!func_stmt)
682 func_stmt = base_type->inline_stmt;
683 if (!func_stmt)
684 return;
685 if (func_stmt->type != STMT_COMPOUND)
686 return;
687
688 FOR_EACH_PTR(func_stmt->stmts, tmp) {
689 if (!found) {
690 if (tmp->type != STMT_LABEL)
691 continue;
692 if (!tmp->label_identifier ||
693 tmp->label_identifier->type != SYM_LABEL ||
694 !tmp->label_identifier->ident)
695 continue;
696 label_name = tmp->label_identifier->ident->name;
697 if (strcmp(goto_name, label_name) != 0)
698 continue;
699 found = 1;
700 }
701 __split_stmt(tmp);
702 } END_FOR_EACH_PTR(tmp);
703 }
704
705 static void fake_a_return(void)
706 {
707 struct symbol *return_type;
708
709 nullify_path();
710 __unnullify_path();
711
712 return_type = get_real_base_type(cur_func_sym);
713 return_type = get_real_base_type(return_type);
714 if (return_type != &void_ctype) {
715 __pass_to_client(unknown_value_expression(NULL), RETURN_HOOK);
716 nullify_path();
717 }
718
719 __pass_to_client(cur_func_sym, END_FUNC_HOOK);
720 __pass_to_client(cur_func_sym, AFTER_FUNC_HOOK);
721 }
722
723 void __split_stmt(struct statement *stmt)
724 {
725 sval_t sval;
726
727 if (!stmt)
728 goto out;
729
730 if (__bail_on_rest_of_function || out_of_memory() || taking_too_long()) {
731 static char *printed = NULL;
732
733 __bail_on_rest_of_function = 1;
734 if (printed != cur_func)
735 sm_msg("Function too hairy. Giving up.");
736 fake_a_return();
737 final_pass = 0; /* turn off sm_msg() from here */
738 printed = cur_func;
739 return;
740 }
741
742 add_ptr_list(&big_statement_stack, stmt);
743 free_expression_stack(&big_expression_stack);
744 set_position(stmt->pos);
745 __pass_to_client(stmt, STMT_HOOK);
746
747 switch (stmt->type) {
748 case STMT_DECLARATION:
749 split_declaration(stmt->declaration);
750 break;
751 case STMT_RETURN:
752 __split_expr(stmt->ret_value);
753 __pass_to_client(stmt->ret_value, RETURN_HOOK);
754 __process_post_op_stack();
755 nullify_path();
756 break;
757 case STMT_EXPRESSION:
758 __split_expr(stmt->expression);
759 break;
760 case STMT_COMPOUND: {
761 struct statement *tmp;
762
763 __push_scope_hooks();
764 FOR_EACH_PTR(stmt->stmts, tmp) {
765 __split_stmt(tmp);
766 } END_FOR_EACH_PTR(tmp);
767 __call_scope_hooks();
768 break;
769 }
770 case STMT_IF:
771 if (known_condition_true(stmt->if_conditional)) {
772 __split_stmt(stmt->if_true);
773 break;
774 }
775 if (known_condition_false(stmt->if_conditional)) {
776 __split_stmt(stmt->if_false);
777 break;
778 }
779 if (option_known_conditions &&
780 implied_condition_true(stmt->if_conditional)) {
781 sm_info("this condition is true.");
782 __split_stmt(stmt->if_true);
783 break;
784 }
785 if (option_known_conditions &&
786 implied_condition_false(stmt->if_conditional)) {
787 sm_info("this condition is false.");
788 __split_stmt(stmt->if_false);
789 break;
790 }
791 __split_whole_condition(stmt->if_conditional);
792 __split_stmt(stmt->if_true);
793 if (empty_statement(stmt->if_true) &&
794 last_stmt_on_same_line() &&
795 !get_macro_name(stmt->if_true->pos))
796 sm_msg("warn: if();");
797 __push_true_states();
798 __use_false_states();
799 __split_stmt(stmt->if_false);
800 __merge_true_states();
801 break;
802 case STMT_ITERATOR:
803 if (stmt->iterator_pre_condition)
804 handle_pre_loop(stmt);
805 else if (stmt->iterator_post_condition)
806 handle_post_loop(stmt);
807 else {
808 // these are for(;;) type loops.
809 handle_pre_loop(stmt);
810 }
811 break;
812 case STMT_SWITCH:
813 if (get_value(stmt->switch_expression, &sval)) {
814 split_known_switch(stmt, sval);
815 break;
816 }
817 __split_expr(stmt->switch_expression);
818 push_expression(&switch_expr_stack, stmt->switch_expression);
819 __save_switch_states(top_expression(switch_expr_stack));
820 nullify_path();
821 __push_default();
822 __push_breaks();
823 __split_stmt(stmt->switch_statement);
824 if (!__pop_default())
825 __merge_switches(top_expression(switch_expr_stack),
826 NULL);
827 __discard_switches();
828 __merge_breaks();
829 pop_expression(&switch_expr_stack);
830 break;
831 case STMT_CASE:
832 __merge_switches(top_expression(switch_expr_stack),
833 stmt->case_expression);
834 __pass_case_to_client(top_expression(switch_expr_stack),
835 stmt->case_expression);
836 if (!stmt->case_expression)
837 __set_default();
838 __split_expr(stmt->case_expression);
839 __split_expr(stmt->case_to);
840 __split_stmt(stmt->case_statement);
841 break;
842 case STMT_LABEL:
843 if (stmt->label_identifier &&
844 stmt->label_identifier->type == SYM_LABEL &&
845 stmt->label_identifier->ident) {
846 loop_count |= 0x80000000;
847 __merge_gotos(stmt->label_identifier->ident->name);
848 }
849 __split_stmt(stmt->label_statement);
850 break;
851 case STMT_GOTO:
852 __split_expr(stmt->goto_expression);
853 if (stmt->goto_label && stmt->goto_label->type == SYM_NODE) {
854 if (!strcmp(stmt->goto_label->ident->name, "break")) {
855 __process_breaks();
856 } else if (!strcmp(stmt->goto_label->ident->name,
857 "continue")) {
858 __process_continues();
859 }
860 } else if (stmt->goto_label &&
861 stmt->goto_label->type == SYM_LABEL &&
862 stmt->goto_label->ident) {
863 __save_gotos(stmt->goto_label->ident->name);
864 }
865 nullify_path();
866 if (is_last_stmt(stmt))
867 handle_backward_goto(stmt);
868 break;
869 case STMT_NONE:
870 break;
871 case STMT_ASM:
872 __pass_to_client(stmt, ASM_HOOK);
873 __split_expr(stmt->asm_string);
874 split_asm_constraints(stmt->asm_outputs);
875 split_asm_constraints(stmt->asm_inputs);
876 split_asm_constraints(stmt->asm_clobbers);
877 break;
878 case STMT_CONTEXT:
879 break;
880 case STMT_RANGE:
881 __split_expr(stmt->range_expression);
882 __split_expr(stmt->range_low);
883 __split_expr(stmt->range_high);
884 break;
885 }
886 __pass_to_client(stmt, STMT_HOOK_AFTER);
887 out:
888 __process_post_op_stack();
889 }
890
891 static void split_expr_list(struct expression_list *expr_list)
892 {
893 struct expression *expr;
894
895 FOR_EACH_PTR(expr_list, expr) {
896 __split_expr(expr);
897 __process_post_op_stack();
898 } END_FOR_EACH_PTR(expr);
899 }
900
901 static void split_sym(struct symbol *sym)
902 {
903 if (!sym)
904 return;
905 if (!(sym->namespace & NS_SYMBOL))
906 return;
907
908 __split_stmt(sym->stmt);
909 __split_expr(sym->array_size);
910 split_symlist(sym->arguments);
911 split_symlist(sym->symbol_list);
912 __split_stmt(sym->inline_stmt);
913 split_symlist(sym->inline_symbol_list);
914 }
915
916 static void split_symlist(struct symbol_list *sym_list)
917 {
918 struct symbol *sym;
919
920 FOR_EACH_PTR(sym_list, sym) {
921 split_sym(sym);
922 } END_FOR_EACH_PTR(sym);
923 }
924
925 typedef void (fake_cb)(struct expression *expr);
926
927 static int member_to_number(struct expression *expr, struct ident *member)
928 {
929 struct symbol *type, *tmp;
930 char *name;
931 int i;
932
933 if (!member)
934 return -1;
935 name = member->name;
936
937 type = get_type(expr);
938 if (!type || type->type != SYM_STRUCT)
939 return -1;
940
941 i = -1;
942 FOR_EACH_PTR(type->symbol_list, tmp) {
943 i++;
944 if (!tmp->ident)
945 continue;
946 if (strcmp(name, tmp->ident->name) == 0)
947 return i;
948 } END_FOR_EACH_PTR(tmp);
949 return -1;
950 }
951
952 static struct ident *number_to_member(struct expression *expr, int num)
953 {
954 struct symbol *type, *member;
955 int i = 0;
956
957 type = get_type(expr);
958 if (!type || type->type != SYM_STRUCT)
959 return NULL;
960
961 FOR_EACH_PTR(type->symbol_list, member) {
962 if (i == num)
963 return member->ident;
964 i++;
965 } END_FOR_EACH_PTR(member);
966 return NULL;
967 }
968
969 static void fake_element_assigns_helper(struct expression *array, struct expression_list *expr_list, fake_cb *fake_cb);
970
971 struct member_set {
972 struct ident *ident;
973 int set;
974 };
975
976 static struct member_set *alloc_member_set(struct symbol *type)
977 {
978 struct member_set *member_set;
979 struct symbol *member;
980 int member_count;
981 int member_idx;
982
983 member_count = ptr_list_size((struct ptr_list *)type->symbol_list);
984 member_set = malloc(member_count * sizeof(*member_set));
985 member_idx = 0;
986 FOR_EACH_PTR(type->symbol_list, member) {
987 member_set[member_idx].ident = member->ident;
988 member_set[member_idx].set = 0;
989 member_idx++;
990 } END_FOR_EACH_PTR(member);
991
992 return member_set;
993 }
994
995 static void mark_member_as_set(struct symbol *type, struct member_set *member_set, struct ident *ident)
996 {
997 int member_count = ptr_list_size((struct ptr_list *)type->symbol_list);
998 int i;
999
1000 for (i = 0; i < member_count; i++) {
1001 if (member_set[i].ident == ident) {
1002 member_set[i].set = 1;
1003 return;
1004 }
1005 }
1006 // crap. this is buggy.
1007 // sm_msg("internal smatch error in initializer %s.%s", type->ident->name, ident->name);
1008 }
1009
1010 static void set_unset_to_zero(struct expression *symbol, struct symbol *type, struct member_set *member_set)
1011 {
1012 struct expression *deref, *assign;
1013 struct symbol *member, *member_type;
1014 int member_idx;
1015
1016 member_idx = 0;
1017 FOR_EACH_PTR(type->symbol_list, member) {
1018 if (!member->ident || member_set[member_idx].set) {
1019 member_idx++;
1020 continue;
1021 }
1022 member_type = get_real_base_type(member);
1023 if (!member_type || member_type->type == SYM_ARRAY) {
1024 member_idx++;
1025 continue;
1026 }
1027 /* TODO: this should be handled recursively and not ignored */
1028 if (member_type->type == SYM_STRUCT || member_type->type == SYM_UNION) {
1029 member_idx++;
1030 continue;
1031 }
1032 deref = member_expression(symbol, '.', member->ident);
1033 assign = assign_expression(deref, zero_expr());
1034 __split_expr(assign);
1035 member_idx++;
1036 } END_FOR_EACH_PTR(member);
1037
1038 }
1039
1040 static void fake_member_assigns_helper(struct expression *symbol, struct expression_list *members, fake_cb *fake_cb)
1041 {
1042 struct expression *deref, *assign, *tmp;
1043 struct symbol *struct_type, *type;
1044 struct ident *member;
1045 int member_idx;
1046 struct member_set *member_set;
1047
1048 struct_type = get_type(symbol);
1049 if (!struct_type ||
1050 (struct_type->type != SYM_STRUCT && struct_type->type != SYM_UNION))
1051 return;
1052
1053 member_set = alloc_member_set(struct_type);
1054
1055 member_idx = 0;
1056 FOR_EACH_PTR(members, tmp) {
1057 member = number_to_member(symbol, member_idx);
1058 while (tmp->type == EXPR_IDENTIFIER) {
1059 member = tmp->expr_ident;
1060 member_idx = member_to_number(symbol, member);
1061 tmp = tmp->ident_expression;
1062 }
1063 mark_member_as_set(struct_type, member_set, member);
1064 member_idx++;
1065 deref = member_expression(symbol, '.', member);
1066 if (tmp->type == EXPR_INITIALIZER) {
1067 type = get_type(deref);
1068 if (type && type->type == SYM_ARRAY)
1069 fake_element_assigns_helper(deref, tmp->expr_list, fake_cb);
1070 else
1071 fake_member_assigns_helper(deref, tmp->expr_list, fake_cb);
1072 } else {
1073 assign = assign_expression(deref, tmp);
1074 fake_cb(assign);
1075 }
1076 } END_FOR_EACH_PTR(tmp);
1077
1078 set_unset_to_zero(symbol, struct_type, member_set);
1079 }
1080
1081 static void fake_member_assigns(struct symbol *sym, fake_cb *fake_cb)
1082 {
1083 fake_member_assigns_helper(symbol_expression(sym),
1084 sym->initializer->expr_list, fake_cb);
1085 }
1086
1087 static void fake_element_assigns_helper(struct expression *array, struct expression_list *expr_list, fake_cb *fake_cb)
1088 {
1089 struct expression *offset, *binop, *assign, *tmp;
1090 struct symbol *type;
1091 int idx;
1092
1093 idx = 0;
1094 FOR_EACH_PTR(expr_list, tmp) {
1095 if (tmp->type == EXPR_INDEX) {
1096 if (tmp->idx_from != tmp->idx_to)
1097 return;
1098 idx = tmp->idx_from;
1099 if (!tmp->idx_expression)
1100 goto next;
1101 tmp = tmp->idx_expression;
1102 }
1103 offset = value_expr(idx);
1104 binop = array_element_expression(array, offset);
1105 if (tmp->type == EXPR_INITIALIZER) {
1106 type = get_type(binop);
1107 if (type && type->type == SYM_ARRAY)
1108 fake_element_assigns_helper(binop, tmp->expr_list, fake_cb);
1109 else
1110 fake_member_assigns_helper(binop, tmp->expr_list, fake_cb);
1111 } else {
1112 assign = assign_expression(binop, tmp);
1113 fake_cb(assign);
1114 }
1115 next:
1116 idx++;
1117 } END_FOR_EACH_PTR(tmp);
1118 }
1119
1120 static void fake_element_assigns(struct symbol *sym, fake_cb *fake_cb)
1121 {
1122 fake_element_assigns_helper(symbol_expression(sym), sym->initializer->expr_list, fake_cb);
1123 }
1124
1125 static void fake_assign_expr(struct symbol *sym)
1126 {
1127 struct expression *assign, *symbol;
1128
1129 symbol = symbol_expression(sym);
1130 assign = assign_expression(symbol, sym->initializer);
1131 __split_expr(assign);
1132 }
1133
1134 static void call_split_expr(struct expression *expr)
1135 {
1136 __split_expr(expr);
1137 }
1138
1139 static void do_initializer_stuff(struct symbol *sym)
1140 {
1141 if (!sym->initializer)
1142 return;
1143
1144 if (sym->initializer->type == EXPR_INITIALIZER) {
1145 if (get_real_base_type(sym)->type == SYM_ARRAY)
1146 fake_element_assigns(sym, call_split_expr);
1147 else
1148 fake_member_assigns(sym, call_split_expr);
1149 } else {
1150 fake_assign_expr(sym);
1151 }
1152 }
1153
1154 static void split_declaration(struct symbol_list *sym_list)
1155 {
1156 struct symbol *sym;
1157
1158 FOR_EACH_PTR(sym_list, sym) {
1159 __pass_to_client(sym, DECLARATION_HOOK);
1160 do_initializer_stuff(sym);
1161 split_sym(sym);
1162 } END_FOR_EACH_PTR(sym);
1163 }
1164
1165 static void call_global_assign_hooks(struct expression *assign)
1166 {
1167 __pass_to_client(assign, GLOBAL_ASSIGNMENT_HOOK);
1168 }
1169
1170 static void fake_global_assign(struct symbol *sym)
1171 {
1172 struct expression *assign, *symbol;
1173
1174 if (get_real_base_type(sym)->type == SYM_ARRAY) {
1175 if (sym->initializer && sym->initializer->type == EXPR_INITIALIZER) {
1176 fake_element_assigns(sym, call_global_assign_hooks);
1177 } else if (sym->initializer) {
1178 symbol = symbol_expression(sym);
1179 assign = assign_expression(symbol, sym->initializer);
1180 __pass_to_client(assign, GLOBAL_ASSIGNMENT_HOOK);
1181 } else {
1182 fake_element_assigns_helper(symbol_expression(sym), NULL, call_global_assign_hooks);
1183 }
1184 } else if (get_real_base_type(sym)->type == SYM_STRUCT) {
1185 if (sym->initializer && sym->initializer->type == EXPR_INITIALIZER) {
1186 fake_member_assigns(sym, call_global_assign_hooks);
1187 } else if (sym->initializer) {
1188 symbol = symbol_expression(sym);
1189 assign = assign_expression(symbol, sym->initializer);
1190 __pass_to_client(assign, GLOBAL_ASSIGNMENT_HOOK);
1191 } else {
1192 fake_member_assigns_helper(symbol_expression(sym), NULL, call_global_assign_hooks);
1193 }
1194 } else {
1195 symbol = symbol_expression(sym);
1196 if (sym->initializer)
1197 assign = assign_expression(symbol, sym->initializer);
1198 else
1199 assign = assign_expression(symbol, zero_expr());
1200 __pass_to_client(assign, GLOBAL_ASSIGNMENT_HOOK);
1201 }
1202 }
1203
1204 static void start_function_definition(struct symbol *sym)
1205 {
1206 __in_function_def = 1;
1207 __pass_to_client(sym, FUNC_DEF_HOOK);
1208 __in_function_def = 0;
1209 __pass_to_client(sym, AFTER_DEF_HOOK);
1210
1211 }
1212
1213 static void split_function(struct symbol *sym)
1214 {
1215 struct symbol *base_type = get_base_type(sym);
1216
1217 if (!base_type->stmt && !base_type->inline_stmt)
1218 return;
1219
1220 gettimeofday(&fn_start_time, NULL);
1221 cur_func_sym = sym;
1222 if (sym->ident)
1223 cur_func = sym->ident->name;
1224 __smatch_lineno = sym->pos.line;
1225 loop_count = 0;
1226 last_goto_statement_handled = 0;
1227 sm_debug("new function: %s\n", cur_func);
1228 __stree_id = 0;
1229 if (option_two_passes) {
1230 __unnullify_path();
1231 loop_num = 0;
1232 final_pass = 0;
1233 start_function_definition(sym);
1234 __split_stmt(base_type->stmt);
1235 __split_stmt(base_type->inline_stmt);
1236 nullify_path();
1237 }
1238 __unnullify_path();
1239 loop_num = 0;
1240 final_pass = 1;
1241 start_function_definition(sym);
1242 __split_stmt(base_type->stmt);
1243 __split_stmt(base_type->inline_stmt);
1244 __pass_to_client(sym, END_FUNC_HOOK);
1245 __pass_to_client(sym, AFTER_FUNC_HOOK);
1246
1247 cur_func_sym = NULL;
1248 cur_func = NULL;
1249 clear_all_states();
1250 free_data_info_allocs();
1251 free_expression_stack(&switch_expr_stack);
1252 __free_ptr_list((struct ptr_list **)&big_statement_stack);
1253 __bail_on_rest_of_function = 0;
1254 }
1255
1256 static void parse_inline(struct expression *call)
1257 {
1258 struct symbol *base_type;
1259 int loop_num_bak = loop_num;
1260 int final_pass_bak = final_pass;
1261 char *cur_func_bak = cur_func;
1262 struct statement_list *big_statement_stack_bak = big_statement_stack;
1263 struct expression_list *big_expression_stack_bak = big_expression_stack;
1264 struct expression_list *switch_expr_stack_bak = switch_expr_stack;
1265 struct symbol *cur_func_sym_bak = cur_func_sym;
1266
1267 __pass_to_client(call, INLINE_FN_START);
1268 final_pass = 0; /* don't print anything */
1269 __inline_fn = call;
1270
1271 base_type = get_base_type(call->fn->symbol);
1272 cur_func_sym = call->fn->symbol;
1273 if (call->fn->symbol->ident)
1274 cur_func = call->fn->symbol->ident->name;
1275 else
1276 cur_func = NULL;
1277 set_position(call->fn->symbol->pos);
1278
1279 save_all_states();
1280 big_statement_stack = NULL;
1281 big_expression_stack = NULL;
1282 switch_expr_stack = NULL;
1283
1284 sm_debug("inline function: %s\n", cur_func);
1285 __unnullify_path();
1286 loop_num = 0;
1287 start_function_definition(call->fn->symbol);
1288 __split_stmt(base_type->stmt);
1289 __split_stmt(base_type->inline_stmt);
1290 __pass_to_client(call->fn->symbol, END_FUNC_HOOK);
1291 __pass_to_client(call->fn->symbol, AFTER_FUNC_HOOK);
1292
1293 free_expression_stack(&switch_expr_stack);
1294 __free_ptr_list((struct ptr_list **)&big_statement_stack);
1295 nullify_path();
1296 free_goto_stack();
1297
1298 loop_num = loop_num_bak;
1299 final_pass = final_pass_bak;
1300 cur_func_sym = cur_func_sym_bak;
1301 cur_func = cur_func_bak;
1302 big_statement_stack = big_statement_stack_bak;
1303 big_expression_stack = big_expression_stack_bak;
1304 switch_expr_stack = switch_expr_stack_bak;
1305
1306 restore_all_states();
1307 set_position(call->pos);
1308 __inline_fn = NULL;
1309 __pass_to_client(call, INLINE_FN_END);
1310 }
1311
1312 static struct symbol_list *inlines_called;
1313 static void add_inline_function(struct symbol *sym)
1314 {
1315 static struct symbol_list *already_added;
1316 struct symbol *tmp;
1317
1318 FOR_EACH_PTR(already_added, tmp) {
1319 if (tmp == sym)
1320 return;
1321 } END_FOR_EACH_PTR(tmp);
1322
1323 add_ptr_list(&already_added, sym);
1324 add_ptr_list(&inlines_called, sym);
1325 }
1326
1327 static void process_inlines(void)
1328 {
1329 struct symbol *tmp;
1330
1331 FOR_EACH_PTR(inlines_called, tmp) {
1332 split_function(tmp);
1333 } END_FOR_EACH_PTR(tmp);
1334 free_ptr_list(&inlines_called);
1335 }
1336
1337 static struct symbol *get_last_scoped_symbol(struct symbol_list *big_list, int use_static)
1338 {
1339 struct symbol *sym;
1340
1341 FOR_EACH_PTR_REVERSE(big_list, sym) {
1342 if (!sym->scope)
1343 continue;
1344 if (use_static && sym->ctype.modifiers & MOD_STATIC)
1345 return sym;
1346 if (!use_static && !(sym->ctype.modifiers & MOD_STATIC))
1347 return sym;
1348 } END_FOR_EACH_PTR_REVERSE(sym);
1349
1350 return NULL;
1351 }
1352
1353 static void split_inlines_in_scope(struct symbol *sym)
1354 {
1355 struct symbol *base;
1356 struct symbol_list *scope_list;
1357 int stream;
1358
1359 scope_list = sym->scope->symbols;
1360 stream = sym->pos.stream;
1361
1362 /* find the last static symbol in the file */
1363 FOR_EACH_PTR_REVERSE(scope_list, sym) {
1364 if (sym->pos.stream != stream)
1365 continue;
1366 if (sym->type != SYM_NODE)
1367 continue;
1368 base = get_base_type(sym);
1369 if (!base)
1370 continue;
1371 if (base->type != SYM_FN)
1372 continue;
1373 if (!base->inline_stmt)
1374 continue;
1375 add_inline_function(sym);
1376 } END_FOR_EACH_PTR_REVERSE(sym);
1377
1378 process_inlines();
1379 }
1380
1381 static void split_inlines(struct symbol_list *sym_list)
1382 {
1383 struct symbol *sym;
1384
1385 sym = get_last_scoped_symbol(sym_list, 0);
1386 if (sym)
1387 split_inlines_in_scope(sym);
1388 sym = get_last_scoped_symbol(sym_list, 1);
1389 if (sym)
1390 split_inlines_in_scope(sym);
1391 }
1392
1393 static struct stree *clone_estates_perm(struct stree *orig)
1394 {
1395 struct stree *ret = NULL;
1396 struct sm_state *tmp;
1397
1398 FOR_EACH_SM(orig, tmp) {
1399 set_state_stree_perm(&ret, tmp->owner, tmp->name, tmp->sym, clone_estate_perm(tmp->state));
1400 } END_FOR_EACH_SM(tmp);
1401
1402 return ret;
1403 }
1404
1405 static void split_functions(struct symbol_list *sym_list)
1406 {
1407 struct symbol *sym;
1408
1409 __unnullify_path();
1410 FOR_EACH_PTR(sym_list, sym) {
1411 set_position(sym->pos);
1412 if (sym->type != SYM_NODE || get_base_type(sym)->type != SYM_FN) {
1413 __pass_to_client(sym, BASE_HOOK);
1414 fake_global_assign(sym);
1415 }
1416 } END_FOR_EACH_PTR(sym);
1417 global_states = clone_estates_perm(get_all_states_stree(SMATCH_EXTRA));
1418 nullify_path();
1419
1420 FOR_EACH_PTR(sym_list, sym) {
1421 set_position(sym->pos);
1422 if (sym->type == SYM_NODE && get_base_type(sym)->type == SYM_FN) {
1423 split_function(sym);
1424 process_inlines();
1425 }
1426 } END_FOR_EACH_PTR(sym);
1427 split_inlines(sym_list);
1428 __pass_to_client(sym_list, END_FILE_HOOK);
1429 }
1430
1431 void smatch(int argc, char **argv)
1432 {
1433
1434 struct string_list *filelist = NULL;
1435 struct symbol_list *sym_list;
1436
1437 if (argc < 2) {
1438 printf("Usage: smatch [--debug] <filename.c>\n");
1439 exit(1);
1440 }
1441 sparse_initialize(argc, argv, &filelist);
1442 set_valid_ptr_max();
1443 FOR_EACH_PTR_NOTAG(filelist, base_file) {
1444 if (option_file_output) {
1445 char buf[256];
1446
1447 snprintf(buf, sizeof(buf), "%s.smatch", base_file);
1448 sm_outfd = fopen(buf, "w");
1449 if (!sm_outfd) {
1450 printf("Error: Cannot open %s\n", base_file);
1451 exit(1);
1452 }
1453 }
1454 sym_list = sparse_keep_tokens(base_file);
1455 split_functions(sym_list);
1456 } END_FOR_EACH_PTR_NOTAG(base_file);
1457 }
Static analysis for C