?  search:
summary | log | graphiclog1 | graphiclog2 | refs | edit | fork

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