?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
mtag_data: clear cache at start of function
[smatch.git] / smatch_flow.c
blob3f1427cf98ba09b9504541c234eb1e3b78d13f5e
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 __in_fake_struct_assign;
30 int in_fake_env;
31 int final_pass;
32 int __inline_call;
33 struct expression *__inline_fn;
34
35 static int __smatch_lineno = 0;
36
37 static char *base_file;
38 static const char *filename;
39 static char *pathname;
40 static char *full_filename;
41 static char *full_base_file;
42 static char *cur_func;
43 static unsigned int loop_count;
44 static int last_goto_statement_handled;
45 int __expr_stmt_count;
46 int __in_function_def;
47 static struct expression_list *switch_expr_stack = NULL;
48 static struct expression_list *post_op_stack = NULL;
49
50 static struct ptr_list *backup;
51
52 struct expression_list *big_expression_stack;
53 struct statement_list *big_statement_stack;
54 struct statement *__prev_stmt;
55 struct statement *__cur_stmt;
56 struct statement *__next_stmt;
57 int __in_pre_condition = 0;
58 int __bail_on_rest_of_function = 0;
59 static struct timeval fn_start_time;
60 char *get_function(void) { return cur_func; }
61 int get_lineno(void) { return __smatch_lineno; }
62 int inside_loop(void) { return !!loop_count; }
63 int definitely_inside_loop(void) { return !!(loop_count & ~0x08000000); }
64 struct expression *get_switch_expr(void) { return top_expression(switch_expr_stack); }
65 int in_expression_statement(void) { return !!__expr_stmt_count; }
66
67 static void split_symlist(struct symbol_list *sym_list);
68 static void split_declaration(struct symbol_list *sym_list);
69 static void split_expr_list(struct expression_list *expr_list, struct expression *parent);
70 static void add_inline_function(struct symbol *sym);
71 static void parse_inline(struct expression *expr);
72
73 int option_assume_loops = 0;
74 int option_two_passes = 0;
75 struct symbol *cur_func_sym = NULL;
76 struct stree *global_states;
77
78 long long valid_ptr_min = 4096;
79 long long valid_ptr_max = 2117777777;
80 sval_t valid_ptr_min_sval = {
81 .type = &ptr_ctype,
82 {.value = 4096},
83 };
84 sval_t valid_ptr_max_sval = {
85 .type = &ptr_ctype,
86 {.value = LONG_MAX - 100000},
87 };
88 struct range_list *valid_ptr_rl;
89
90 static void set_valid_ptr_max(void)
91 {
92 if (type_bits(&ptr_ctype) == 32)
93 valid_ptr_max = 2117777777;
94 else if (type_bits(&ptr_ctype) == 64)
95 valid_ptr_max = 2117777777777777777LL;
96
97 valid_ptr_max_sval.value = valid_ptr_max;
98 }
99
100 static void alloc_valid_ptr_rl(void)
101 {
102 valid_ptr_rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
103 valid_ptr_rl = cast_rl(&ptr_ctype, valid_ptr_rl);
104 valid_ptr_rl = clone_rl_permanent(valid_ptr_rl);
105 }
106
107 int outside_of_function(void)
108 {
109 return cur_func_sym == NULL;
110 }
111
112 const char *get_filename(void)
113 {
114 if (option_info && option_full_path)
115 return full_base_file;
116 if (option_info)
117 return base_file;
118 if (option_full_path)
119 return full_filename;
120 return filename;
121 }
122
123 const char *get_base_file(void)
124 {
125 if (option_full_path)
126 return full_base_file;
127 return base_file;
128 }
129
130 static void set_position(struct position pos)
131 {
132 int len;
133 static int prev_stream = -1;
134
135 if (in_fake_env)
136 return;
137
138 if (pos.stream == 0 && pos.line == 0)
139 return;
140
141 __smatch_lineno = pos.line;
142
143 if (pos.stream == prev_stream)
144 return;
145
146 filename = stream_name(pos.stream);
147
148 free(full_filename);
149 pathname = getcwd(NULL, 0);
150 if (pathname) {
151 len = strlen(pathname) + 1 + strlen(filename) + 1;
152 full_filename = malloc(len);
153 snprintf(full_filename, len, "%s/%s", pathname, filename);
154 } else {
155 full_filename = alloc_string(filename);
156 }
157 free(pathname);
158 }
159
160 int is_assigned_call(struct expression *expr)
161 {
162 struct expression *parent = expr_get_parent_expr(expr);
163
164 if (parent &&
165 parent->type == EXPR_ASSIGNMENT &&
166 parent->op == '=' &&
167 strip_expr(parent->right) == expr)
168 return 1;
169
170 return 0;
171 }
172
173 static int is_inline_func(struct expression *expr)
174 {
175 if (expr->type != EXPR_SYMBOL || !expr->symbol)
176 return 0;
177 if (expr->symbol->ctype.modifiers & MOD_INLINE)
178 return 1;
179 return 0;
180 }
181
182 static int is_noreturn_func(struct expression *expr)
183 {
184 if (expr->type != EXPR_SYMBOL || !expr->symbol)
185 return 0;
186 if (expr->symbol->ctype.modifiers & MOD_NORETURN)
187 return 1;
188 return 0;
189 }
190
191 static int inline_budget = 20;
192
193 int inlinable(struct expression *expr)
194 {
195 struct symbol *sym;
196 struct statement *last_stmt = NULL;
197
198 if (__inline_fn) /* don't nest */
199 return 0;
200
201 if (expr->type != EXPR_SYMBOL || !expr->symbol)
202 return 0;
203 if (is_no_inline_function(expr->symbol->ident->name))
204 return 0;
205 sym = get_base_type(expr->symbol);
206 if (sym->stmt && sym->stmt->type == STMT_COMPOUND) {
207 if (ptr_list_size((struct ptr_list *)sym->stmt->stmts) > 10)
208 return 0;
209 if (sym->stmt->type != STMT_COMPOUND)
210 return 0;
211 last_stmt = last_ptr_list((struct ptr_list *)sym->stmt->stmts);
212 }
213 if (sym->inline_stmt && sym->inline_stmt->type == STMT_COMPOUND) {
214 if (ptr_list_size((struct ptr_list *)sym->inline_stmt->stmts) > 10)
215 return 0;
216 if (sym->inline_stmt->type != STMT_COMPOUND)
217 return 0;
218 last_stmt = last_ptr_list((struct ptr_list *)sym->inline_stmt->stmts);
219 }
220
221 if (!last_stmt)
222 return 0;
223
224 /* the magic numbers in this function are pulled out of my bum. */
225 if (last_stmt->pos.line > sym->pos.line + inline_budget)
226 return 0;
227
228 return 1;
229 }
230
231 void __process_post_op_stack(void)
232 {
233 struct expression *expr;
234
235 FOR_EACH_PTR(post_op_stack, expr) {
236 __pass_to_client(expr, OP_HOOK);
237 } END_FOR_EACH_PTR(expr);
238
239 __free_ptr_list((struct ptr_list **)&post_op_stack);
240 }
241
242 static int handle_comma_assigns(struct expression *expr)
243 {
244 struct expression *right;
245 struct expression *assign;
246
247 right = strip_expr(expr->right);
248 if (right->type != EXPR_COMMA)
249 return 0;
250
251 __split_expr(right->left);
252 __process_post_op_stack();
253
254 assign = assign_expression(expr->left, '=', right->right);
255 __split_expr(assign);
256
257 return 1;
258 }
259
260 /* This is to handle *p++ = foo; assignments */
261 static int handle_postop_assigns(struct expression *expr)
262 {
263 struct expression *left, *fake_left;
264 struct expression *assign;
265
266 left = strip_expr(expr->left);
267 if (left->type != EXPR_PREOP || left->op != '*')
268 return 0;
269 left = strip_expr(left->unop);
270 if (left->type != EXPR_POSTOP)
271 return 0;
272
273 fake_left = deref_expression(strip_expr(left->unop));
274 assign = assign_expression(fake_left, '=', expr->right);
275
276 __split_expr(assign);
277 __split_expr(expr->left);
278
279 return 1;
280 }
281
282 static int prev_expression_is_getting_address(struct expression *expr)
283 {
284 struct expression *parent;
285
286 do {
287 parent = expr_get_parent_expr(expr);
288
289 if (!parent)
290 return 0;
291 if (parent->type == EXPR_PREOP && parent->op == '&')
292 return 1;
293 if (parent->type == EXPR_PREOP && parent->op == '(')
294 goto next;
295 if (parent->type == EXPR_DEREF && parent->op == '.')
296 goto next;
297
298 return 0;
299 next:
300 expr = parent;
301 } while (1);
302 }
303
304 static int handle__builtin_choose_expr(struct expression *expr)
305 {
306 struct expression *const_expr, *expr1, *expr2;
307 sval_t sval;
308
309 if (!sym_name_is("__builtin_choose_expr", expr->fn))
310 return 0;
311
312 const_expr = get_argument_from_call_expr(expr->args, 0);
313 expr1 = get_argument_from_call_expr(expr->args, 1);
314 expr2 = get_argument_from_call_expr(expr->args, 2);
315
316 if (!get_value(const_expr, &sval) || !expr1 || !expr2)
317 return 0;
318 if (sval.value)
319 __split_expr(expr1);
320 else
321 __split_expr(expr2);
322 return 1;
323 }
324
325 static int handle__builtin_choose_expr_assigns(struct expression *expr)
326 {
327 struct expression *const_expr, *right, *expr1, *expr2, *fake;
328 sval_t sval;
329
330 right = strip_expr(expr->right);
331 if (right->type != EXPR_CALL)
332 return 0;
333 if (!sym_name_is("__builtin_choose_expr", right->fn))
334 return 0;
335
336 const_expr = get_argument_from_call_expr(right->args, 0);
337 expr1 = get_argument_from_call_expr(right->args, 1);
338 expr2 = get_argument_from_call_expr(right->args, 2);
339
340 if (!get_value(const_expr, &sval) || !expr1 || !expr2)
341 return 0;
342
343 fake = assign_expression(expr->left, '=', sval.value ? expr1 : expr2);
344 __split_expr(fake);
345 return 1;
346 }
347
348 void __split_expr(struct expression *expr)
349 {
350 if (!expr)
351 return;
352
353 // sm_msg(" Debug expr_type %d %s", expr->type, show_special(expr->op));
354
355 if (__in_fake_assign && expr->type != EXPR_ASSIGNMENT)
356 return;
357 if (__in_fake_assign >= 4) /* don't allow too much nesting */
358 return;
359
360 push_expression(&big_expression_stack, expr);
361 set_position(expr->pos);
362 __pass_to_client(expr, EXPR_HOOK);
363
364 switch (expr->type) {
365 case EXPR_PREOP:
366 expr_set_parent_expr(expr->unop, expr);
367
368 if (expr->op == '*' &&
369 !prev_expression_is_getting_address(expr))
370 __pass_to_client(expr, DEREF_HOOK);
371 __split_expr(expr->unop);
372 __pass_to_client(expr, OP_HOOK);
373 break;
374 case EXPR_POSTOP:
375 expr_set_parent_expr(expr->unop, expr);
376
377 __split_expr(expr->unop);
378 push_expression(&post_op_stack, expr);
379 break;
380 case EXPR_STATEMENT:
381 __expr_stmt_count++;
382 if (expr->statement && !expr->statement) {
383 stmt_set_parent_stmt(expr->statement,
384 last_ptr_list((struct ptr_list *)big_statement_stack));
385 }
386 __split_stmt(expr->statement);
387 __expr_stmt_count--;
388 break;
389 case EXPR_LOGICAL:
390 case EXPR_COMPARE:
391 expr_set_parent_expr(expr->left, expr);
392 expr_set_parent_expr(expr->right, expr);
393
394 __pass_to_client(expr, LOGIC_HOOK);
395 __handle_logic(expr);
396 break;
397 case EXPR_BINOP:
398 expr_set_parent_expr(expr->left, expr);
399 expr_set_parent_expr(expr->right, expr);
400
401 __pass_to_client(expr, BINOP_HOOK);
402 case EXPR_COMMA:
403 expr_set_parent_expr(expr->left, expr);
404 expr_set_parent_expr(expr->right, expr);
405
406 __split_expr(expr->left);
407 __process_post_op_stack();
408 __split_expr(expr->right);
409 break;
410 case EXPR_ASSIGNMENT: {
411 struct expression *right;
412
413 expr_set_parent_expr(expr->left, expr);
414 expr_set_parent_expr(expr->right, expr);
415
416 right = strip_expr(expr->right);
417 if (!right)
418 break;
419
420 __pass_to_client(expr, RAW_ASSIGNMENT_HOOK);
421
422 /* foo = !bar() */
423 if (__handle_condition_assigns(expr))
424 break;
425 /* foo = (x < 5 ? foo : 5); */
426 if (__handle_select_assigns(expr))
427 break;
428 /* foo = ({frob(); frob(); frob(); 1;}) */
429 if (__handle_expr_statement_assigns(expr))
430 break;
431 /* foo = (3, 4); */
432 if (handle_comma_assigns(expr))
433 break;
434 if (handle_postop_assigns(expr))
435 break;
436 if (handle__builtin_choose_expr_assigns(expr))
437 break;
438
439 __split_expr(expr->right);
440 if (outside_of_function())
441 __pass_to_client(expr, GLOBAL_ASSIGNMENT_HOOK);
442 else
443 __pass_to_client(expr, ASSIGNMENT_HOOK);
444
445 __fake_struct_member_assignments(expr);
446
447 if (expr->op == '=' && right->type == EXPR_CALL)
448 __pass_to_client(expr, CALL_ASSIGNMENT_HOOK);
449
450 if (get_macro_name(right->pos) &&
451 get_macro_name(expr->pos) != get_macro_name(right->pos))
452 __pass_to_client(expr, MACRO_ASSIGNMENT_HOOK);
453
454 __pass_to_client(expr, ASSIGNMENT_HOOK_AFTER);
455
456 __split_expr(expr->left);
457 break;
458 }
459 case EXPR_DEREF:
460 expr_set_parent_expr(expr->deref, expr);
461
462 __pass_to_client(expr, DEREF_HOOK);
463 __split_expr(expr->deref);
464 break;
465 case EXPR_SLICE:
466 expr_set_parent_expr(expr->base, expr);
467
468 __split_expr(expr->base);
469 break;
470 case EXPR_CAST:
471 case EXPR_FORCE_CAST:
472 expr_set_parent_expr(expr->cast_expression, expr);
473
474 __pass_to_client(expr, CAST_HOOK);
475 __split_expr(expr->cast_expression);
476 break;
477 case EXPR_SIZEOF:
478 if (expr->cast_expression)
479 __pass_to_client(strip_parens(expr->cast_expression),
480 SIZEOF_HOOK);
481 break;
482 case EXPR_OFFSETOF:
483 case EXPR_ALIGNOF:
484 evaluate_expression(expr);
485 break;
486 case EXPR_CONDITIONAL:
487 case EXPR_SELECT:
488 expr_set_parent_expr(expr->conditional, expr);
489 expr_set_parent_expr(expr->cond_true, expr);
490 expr_set_parent_expr(expr->cond_false, expr);
491
492 if (known_condition_true(expr->conditional)) {
493 __split_expr(expr->cond_true);
494 break;
495 }
496 if (known_condition_false(expr->conditional)) {
497 __split_expr(expr->cond_false);
498 break;
499 }
500 __pass_to_client(expr, SELECT_HOOK);
501 __split_whole_condition(expr->conditional);
502 __split_expr(expr->cond_true);
503 __push_true_states();
504 __use_false_states();
505 __split_expr(expr->cond_false);
506 __merge_true_states();
507 break;
508 case EXPR_CALL:
509 expr_set_parent_expr(expr->fn, expr);
510
511 if (sym_name_is("__builtin_constant_p", expr->fn))
512 break;
513 if (handle__builtin_choose_expr(expr))
514 break;
515 split_expr_list(expr->args, expr);
516 __split_expr(expr->fn);
517 if (is_inline_func(expr->fn))
518 add_inline_function(expr->fn->symbol);
519 if (inlinable(expr->fn))
520 __inline_call = 1;
521 __process_post_op_stack();
522 __pass_to_client(expr, FUNCTION_CALL_HOOK_BEFORE);
523 __pass_to_client(expr, FUNCTION_CALL_HOOK);
524 __inline_call = 0;
525 if (inlinable(expr->fn)) {
526 parse_inline(expr);
527 }
528 __pass_to_client(expr, CALL_HOOK_AFTER_INLINE);
529 if (is_noreturn_func(expr->fn))
530 nullify_path();
531 break;
532 case EXPR_INITIALIZER:
533 split_expr_list(expr->expr_list, expr);
534 break;
535 case EXPR_IDENTIFIER:
536 expr_set_parent_expr(expr->ident_expression, expr);
537 __split_expr(expr->ident_expression);
538 break;
539 case EXPR_INDEX:
540 expr_set_parent_expr(expr->idx_expression, expr);
541 __split_expr(expr->idx_expression);
542 break;
543 case EXPR_POS:
544 expr_set_parent_expr(expr->init_expr, expr);
545 __split_expr(expr->init_expr);
546 break;
547 case EXPR_SYMBOL:
548 __pass_to_client(expr, SYM_HOOK);
549 break;
550 case EXPR_STRING:
551 __pass_to_client(expr, STRING_HOOK);
552 break;
553 default:
554 break;
555 };
556 pop_expression(&big_expression_stack);
557 }
558
559 static int is_forever_loop(struct statement *stmt)
560 {
561 struct expression *expr;
562 sval_t sval;
563
564 expr = strip_expr(stmt->iterator_pre_condition);
565 if (!expr)
566 expr = stmt->iterator_post_condition;
567 if (!expr) {
568 /* this is a for(;;) loop... */
569 return 1;
570 }
571
572 if (get_value(expr, &sval) && sval.value != 0)
573 return 1;
574
575 return 0;
576 }
577
578 static int loop_num;
579 static char *get_loop_name(int num)
580 {
581 char buf[256];
582
583 snprintf(buf, 255, "-loop%d", num);
584 buf[255] = '\0';
585 return alloc_sname(buf);
586 }
587
588 /*
589 * Pre Loops are while and for loops.
590 */
591 static void handle_pre_loop(struct statement *stmt)
592 {
593 int once_through; /* we go through the loop at least once */
594 struct sm_state *extra_sm = NULL;
595 int unchanged = 0;
596 char *loop_name;
597 struct stree *stree = NULL;
598 struct sm_state *sm = NULL;
599
600 loop_name = get_loop_name(loop_num);
601 loop_num++;
602
603 __split_stmt(stmt->iterator_pre_statement);
604 __prev_stmt = stmt->iterator_pre_statement;
605
606 once_through = implied_condition_true(stmt->iterator_pre_condition);
607
608 loop_count++;
609 __push_continues();
610 __push_breaks();
611
612 __merge_gotos(loop_name, NULL);
613
614 extra_sm = __extra_handle_canonical_loops(stmt, &stree);
615 __in_pre_condition++;
616 __pass_to_client(stmt, PRELOOP_HOOK);
617 __split_whole_condition(stmt->iterator_pre_condition);
618 __in_pre_condition--;
619 FOR_EACH_SM(stree, sm) {
620 set_state(sm->owner, sm->name, sm->sym, sm->state);
621 } END_FOR_EACH_SM(sm);
622 free_stree(&stree);
623 if (extra_sm)
624 extra_sm = get_sm_state(extra_sm->owner, extra_sm->name, extra_sm->sym);
625
626 if (option_assume_loops)
627 once_through = 1;
628
629 __split_stmt(stmt->iterator_statement);
630 if (is_forever_loop(stmt)) {
631 __merge_continues();
632 __save_gotos(loop_name, NULL);
633
634 __push_fake_cur_stree();
635 __split_stmt(stmt->iterator_post_statement);
636 stree = __pop_fake_cur_stree();
637
638 __discard_false_states();
639 __use_breaks();
640
641 if (!__path_is_null())
642 __merge_stree_into_cur(stree);
643 free_stree(&stree);
644 } else {
645 __merge_continues();
646 unchanged = __iterator_unchanged(extra_sm);
647 __split_stmt(stmt->iterator_post_statement);
648 __prev_stmt = stmt->iterator_post_statement;
649 __cur_stmt = stmt;
650
651 __save_gotos(loop_name, NULL);
652 __in_pre_condition++;
653 __split_whole_condition(stmt->iterator_pre_condition);
654 __in_pre_condition--;
655 nullify_path();
656 __merge_false_states();
657 if (once_through)
658 __discard_false_states();
659 else
660 __merge_false_states();
661
662 if (extra_sm && unchanged)
663 __extra_pre_loop_hook_after(extra_sm,
664 stmt->iterator_post_statement,
665 stmt->iterator_pre_condition);
666 __merge_breaks();
667 }
668 loop_count--;
669 }
670
671 /*
672 * Post loops are do {} while();
673 */
674 static void handle_post_loop(struct statement *stmt)
675 {
676 char *loop_name;
677
678 loop_name = get_loop_name(loop_num);
679 loop_num++;
680 loop_count++;
681
682 __push_continues();
683 __push_breaks();
684 __merge_gotos(loop_name, NULL);
685 __split_stmt(stmt->iterator_statement);
686 __merge_continues();
687 if (!is_zero(stmt->iterator_post_condition))
688 __save_gotos(loop_name, NULL);
689
690 if (is_forever_loop(stmt)) {
691 __use_breaks();
692 } else {
693 __split_whole_condition(stmt->iterator_post_condition);
694 __use_false_states();
695 __merge_breaks();
696 }
697 loop_count--;
698 }
699
700 static int empty_statement(struct statement *stmt)
701 {
702 if (!stmt)
703 return 0;
704 if (stmt->type == STMT_EXPRESSION && !stmt->expression)
705 return 1;
706 return 0;
707 }
708
709 static int last_stmt_on_same_line(void)
710 {
711 struct statement *stmt;
712 int i = 0;
713
714 FOR_EACH_PTR_REVERSE(big_statement_stack, stmt) {
715 if (!i++)
716 continue;
717 if (stmt->pos.line == get_lineno())
718 return 1;
719 return 0;
720 } END_FOR_EACH_PTR_REVERSE(stmt);
721 return 0;
722 }
723
724 static void split_asm_constraints(struct expression_list *expr_list)
725 {
726 struct expression *expr;
727 int state = 0;
728
729 FOR_EACH_PTR(expr_list, expr) {
730 switch (state) {
731 case 0: /* identifier */
732 case 1: /* constraint */
733 state++;
734 continue;
735 case 2: /* expression */
736 state = 0;
737 __split_expr(expr);
738 continue;
739 }
740 } END_FOR_EACH_PTR(expr);
741 }
742
743 static int is_case_val(struct statement *stmt, sval_t sval)
744 {
745 sval_t case_sval;
746
747 if (stmt->type != STMT_CASE)
748 return 0;
749 if (!stmt->case_expression) {
750 __set_default();
751 return 1;
752 }
753 if (!get_value(stmt->case_expression, &case_sval))
754 return 0;
755 if (case_sval.value == sval.value)
756 return 1;
757 return 0;
758 }
759
760 static struct range_list *get_case_rl(struct expression *switch_expr,
761 struct expression *case_expr,
762 struct expression *case_to)
763 {
764 sval_t start, end;
765 struct range_list *rl = NULL;
766 struct symbol *switch_type;
767
768 switch_type = get_type(switch_expr);
769 if (get_value(case_to, &end) && get_value(case_expr, &start)) {
770 start = sval_cast(switch_type, start);
771 end = sval_cast(switch_type, end);
772 add_range(&rl, start, end);
773 } else if (get_value(case_expr, &start)) {
774 start = sval_cast(switch_type, start);
775 add_range(&rl, start, start);
776 }
777
778 return rl;
779 }
780
781 static void split_known_switch(struct statement *stmt, sval_t sval)
782 {
783 struct statement *tmp;
784 struct range_list *rl;
785
786 __split_expr(stmt->switch_expression);
787 sval = sval_cast(get_type(stmt->switch_expression), sval);
788
789 push_expression(&switch_expr_stack, stmt->switch_expression);
790 __save_switch_states(top_expression(switch_expr_stack));
791 nullify_path();
792 __push_default();
793 __push_breaks();
794
795 stmt = stmt->switch_statement;
796
797 __push_scope_hooks();
798 FOR_EACH_PTR(stmt->stmts, tmp) {
799 __smatch_lineno = tmp->pos.line;
800 if (is_case_val(tmp, sval)) {
801 rl = alloc_rl(sval, sval);
802 __merge_switches(top_expression(switch_expr_stack), rl);
803 __pass_case_to_client(top_expression(switch_expr_stack), rl);
804 }
805 if (__path_is_null())
806 continue;
807 __split_stmt(tmp);
808 if (__path_is_null()) {
809 __set_default();
810 goto out;
811 }
812 } END_FOR_EACH_PTR(tmp);
813 out:
814 __call_scope_hooks();
815 if (!__pop_default())
816 __merge_switches(top_expression(switch_expr_stack), NULL);
817 __discard_switches();
818 __merge_breaks();
819 pop_expression(&switch_expr_stack);
820 }
821
822 static void split_case(struct statement *stmt)
823 {
824 struct range_list *rl = NULL;
825
826 expr_set_parent_stmt(stmt->case_expression, stmt);
827 expr_set_parent_stmt(stmt->case_to, stmt);
828
829 rl = get_case_rl(top_expression(switch_expr_stack),
830 stmt->case_expression, stmt->case_to);
831 while (stmt->case_statement->type == STMT_CASE) {
832 struct range_list *tmp;
833
834 tmp = get_case_rl(top_expression(switch_expr_stack),
835 stmt->case_statement->case_expression,
836 stmt->case_statement->case_to);
837 if (!tmp)
838 break;
839 rl = rl_union(rl, tmp);
840 if (!stmt->case_expression)
841 __set_default();
842 stmt = stmt->case_statement;
843 }
844
845 __merge_switches(top_expression(switch_expr_stack), rl);
846
847 if (!stmt->case_expression)
848 __set_default();
849 __split_stmt(stmt->case_statement);
850 }
851
852 int time_parsing_function(void)
853 {
854 return ms_since(&fn_start_time) / 1000;
855 }
856
857 static int taking_too_long(void)
858 {
859 if (time_parsing_function() > 60 * 5) /* five minutes */
860 return 1;
861 return 0;
862 }
863
864 static int is_last_stmt(struct statement *cur_stmt)
865 {
866 struct symbol *fn = get_base_type(cur_func_sym);
867 struct statement *stmt;
868
869 if (!fn)
870 return 0;
871 stmt = fn->stmt;
872 if (!stmt)
873 stmt = fn->inline_stmt;
874 if (!stmt || stmt->type != STMT_COMPOUND)
875 return 0;
876 stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
877 if (stmt && stmt->type == STMT_LABEL)
878 stmt = stmt->label_statement;
879 if (stmt == cur_stmt)
880 return 1;
881 return 0;
882 }
883
884 static void handle_backward_goto(struct statement *goto_stmt)
885 {
886 const char *goto_name, *label_name;
887 struct statement *func_stmt;
888 struct symbol *base_type = get_base_type(cur_func_sym);
889 struct statement *tmp;
890 int found = 0;
891
892 if (!option_info)
893 return;
894 if (last_goto_statement_handled)
895 return;
896 last_goto_statement_handled = 1;
897
898 if (!goto_stmt->goto_label ||
899 goto_stmt->goto_label->type != SYM_LABEL ||
900 !goto_stmt->goto_label->ident)
901 return;
902 goto_name = goto_stmt->goto_label->ident->name;
903
904 func_stmt = base_type->stmt;
905 if (!func_stmt)
906 func_stmt = base_type->inline_stmt;
907 if (!func_stmt)
908 return;
909 if (func_stmt->type != STMT_COMPOUND)
910 return;
911
912 FOR_EACH_PTR(func_stmt->stmts, tmp) {
913 if (!found) {
914 if (tmp->type != STMT_LABEL)
915 continue;
916 if (!tmp->label_identifier ||
917 tmp->label_identifier->type != SYM_LABEL ||
918 !tmp->label_identifier->ident)
919 continue;
920 label_name = tmp->label_identifier->ident->name;
921 if (strcmp(goto_name, label_name) != 0)
922 continue;
923 found = 1;
924 }
925 __split_stmt(tmp);
926 } END_FOR_EACH_PTR(tmp);
927 }
928
929 static void fake_a_return(void)
930 {
931 struct symbol *return_type;
932
933 nullify_path();
934 __unnullify_path();
935
936 return_type = get_real_base_type(cur_func_sym);
937 return_type = get_real_base_type(return_type);
938 if (return_type != &void_ctype) {
939 __pass_to_client(unknown_value_expression(NULL), RETURN_HOOK);
940 nullify_path();
941 }
942 }
943
944 static void fake_an_empty_default(struct position pos)
945 {
946 static struct statement none = {};
947
948 none.pos = pos;
949 none.type = STMT_NONE;
950 __merge_switches(top_expression(switch_expr_stack), NULL);
951 __split_stmt(&none);
952 }
953
954 static void split_compound(struct statement *stmt)
955 {
956 struct statement *prev = NULL;
957 struct statement *cur = NULL;
958 struct statement *next;
959
960 __push_scope_hooks();
961
962 FOR_EACH_PTR(stmt->stmts, next) {
963 /* just set them all ahead of time */
964 stmt_set_parent_stmt(next, stmt);
965
966 if (cur) {
967 __prev_stmt = prev;
968 __next_stmt = next;
969 __cur_stmt = cur;
970 __split_stmt(cur);
971 }
972 prev = cur;
973 cur = next;
974 } END_FOR_EACH_PTR(next);
975 if (cur) {
976 __prev_stmt = prev;
977 __cur_stmt = cur;
978 __next_stmt = NULL;
979 __split_stmt(cur);
980 }
981
982 /*
983 * For function scope, then delay calling the scope hooks until the
984 * end of function hooks can run. I'm not positive this is the right
985 * thing...
986 */
987 if (!is_last_stmt(cur))
988 __call_scope_hooks();
989 }
990
991 /*
992 * This is a hack, work around for detecting empty functions.
993 */
994 static int need_delayed_scope_hooks(void)
995 {
996 struct symbol *fn = get_base_type(cur_func_sym);
997 struct statement *stmt;
998
999 if (!fn)
1000 return 0;
1001 stmt = fn->stmt;
1002 if (!stmt)
1003 stmt = fn->inline_stmt;
1004 if (stmt && stmt->type == STMT_COMPOUND)
1005 return 1;
1006 return 0;
1007 }
1008
1009 void __split_label_stmt(struct statement *stmt)
1010 {
1011 if (stmt->label_identifier &&
1012 stmt->label_identifier->type == SYM_LABEL &&
1013 stmt->label_identifier->ident) {
1014 loop_count |= 0x0800000;
1015 __merge_gotos(stmt->label_identifier->ident->name, stmt->label_identifier);
1016 }
1017 }
1018
1019 static void find_asm_gotos(struct statement *stmt)
1020 {
1021 struct symbol *sym;
1022
1023 FOR_EACH_PTR(stmt->asm_labels, sym) {
1024 __save_gotos(sym->ident->name, sym);
1025 } END_FOR_EACH_PTR(sym);
1026 }
1027
1028 void __split_stmt(struct statement *stmt)
1029 {
1030 sval_t sval;
1031
1032 if (!stmt)
1033 goto out;
1034
1035 if (!__in_fake_assign)
1036 __silence_warnings_for_stmt = false;
1037
1038 if (__bail_on_rest_of_function)
1039 return;
1040
1041 if (out_of_memory() || taking_too_long()) {
1042 struct timeval stop;
1043
1044 gettimeofday(&stop, NULL);
1045
1046 __bail_on_rest_of_function = 1;
1047 final_pass = 1;
1048 sm_msg("Function too hairy. Giving up. %lu seconds",
1049 stop.tv_sec - fn_start_time.tv_sec);
1050 fake_a_return();
1051 final_pass = 0; /* turn off sm_msg() from here */
1052 return;
1053 }
1054
1055 add_ptr_list(&big_statement_stack, stmt);
1056 free_expression_stack(&big_expression_stack);
1057 set_position(stmt->pos);
1058 __pass_to_client(stmt, STMT_HOOK);
1059
1060 switch (stmt->type) {
1061 case STMT_DECLARATION:
1062 split_declaration(stmt->declaration);
1063 break;
1064 case STMT_RETURN:
1065 expr_set_parent_stmt(stmt->ret_value, stmt);
1066
1067 __split_expr(stmt->ret_value);
1068 __pass_to_client(stmt->ret_value, RETURN_HOOK);
1069 __process_post_op_stack();
1070 nullify_path();
1071 break;
1072 case STMT_EXPRESSION:
1073 expr_set_parent_stmt(stmt->expression, stmt);
1074 expr_set_parent_stmt(stmt->context, stmt);
1075
1076 __split_expr(stmt->expression);
1077 break;
1078 case STMT_COMPOUND:
1079 split_compound(stmt);
1080 break;
1081 case STMT_IF:
1082 stmt_set_parent_stmt(stmt->if_true, stmt);
1083 stmt_set_parent_stmt(stmt->if_false, stmt);
1084 expr_set_parent_stmt(stmt->if_conditional, stmt);
1085
1086 if (known_condition_true(stmt->if_conditional)) {
1087 __split_stmt(stmt->if_true);
1088 break;
1089 }
1090 if (known_condition_false(stmt->if_conditional)) {
1091 __split_stmt(stmt->if_false);
1092 break;
1093 }
1094 __split_whole_condition(stmt->if_conditional);
1095 __split_stmt(stmt->if_true);
1096 if (empty_statement(stmt->if_true) &&
1097 last_stmt_on_same_line() &&
1098 !get_macro_name(stmt->if_true->pos))
1099 sm_msg("warn: if();");
1100 __push_true_states();
1101 __use_false_states();
1102 __split_stmt(stmt->if_false);
1103 __merge_true_states();
1104 break;
1105 case STMT_ITERATOR:
1106 stmt_set_parent_stmt(stmt->iterator_pre_statement, stmt);
1107 stmt_set_parent_stmt(stmt->iterator_statement, stmt);
1108 stmt_set_parent_stmt(stmt->iterator_post_statement, stmt);
1109 expr_set_parent_stmt(stmt->iterator_pre_condition, stmt);
1110 expr_set_parent_stmt(stmt->iterator_post_condition, stmt);
1111
1112 if (stmt->iterator_pre_condition)
1113 handle_pre_loop(stmt);
1114 else if (stmt->iterator_post_condition)
1115 handle_post_loop(stmt);
1116 else {
1117 // these are for(;;) type loops.
1118 handle_pre_loop(stmt);
1119 }
1120 break;
1121 case STMT_SWITCH:
1122 stmt_set_parent_stmt(stmt->switch_statement, stmt);
1123 expr_set_parent_stmt(stmt->switch_expression, stmt);
1124
1125 if (get_value(stmt->switch_expression, &sval)) {
1126 split_known_switch(stmt, sval);
1127 break;
1128 }
1129 __split_expr(stmt->switch_expression);
1130 push_expression(&switch_expr_stack, stmt->switch_expression);
1131 __save_switch_states(top_expression(switch_expr_stack));
1132 nullify_path();
1133 __push_default();
1134 __push_breaks();
1135 __split_stmt(stmt->switch_statement);
1136 if (!__pop_default() && have_remaining_cases())
1137 fake_an_empty_default(stmt->pos);
1138 __discard_switches();
1139 __merge_breaks();
1140 pop_expression(&switch_expr_stack);
1141 break;
1142 case STMT_CASE:
1143 split_case(stmt);
1144 break;
1145 case STMT_LABEL:
1146 __split_label_stmt(stmt);
1147 __split_stmt(stmt->label_statement);
1148 break;
1149 case STMT_GOTO:
1150 expr_set_parent_stmt(stmt->goto_expression, stmt);
1151
1152 __split_expr(stmt->goto_expression);
1153 if (stmt->goto_label && stmt->goto_label->type == SYM_NODE) {
1154 if (!strcmp(stmt->goto_label->ident->name, "break")) {
1155 __process_breaks();
1156 } else if (!strcmp(stmt->goto_label->ident->name,
1157 "continue")) {
1158 __process_continues();
1159 }
1160 } else if (stmt->goto_label &&
1161 stmt->goto_label->type == SYM_LABEL &&
1162 stmt->goto_label->ident) {
1163 __save_gotos(stmt->goto_label->ident->name, stmt->goto_label);
1164 }
1165 nullify_path();
1166 if (is_last_stmt(stmt))
1167 handle_backward_goto(stmt);
1168 break;
1169 case STMT_NONE:
1170 break;
1171 case STMT_ASM:
1172 expr_set_parent_stmt(stmt->asm_string, stmt);
1173
1174 find_asm_gotos(stmt);
1175 __pass_to_client(stmt, ASM_HOOK);
1176 __split_expr(stmt->asm_string);
1177 split_asm_constraints(stmt->asm_outputs);
1178 split_asm_constraints(stmt->asm_inputs);
1179 split_asm_constraints(stmt->asm_clobbers);
1180 break;
1181 case STMT_CONTEXT:
1182 break;
1183 case STMT_RANGE:
1184 __split_expr(stmt->range_expression);
1185 __split_expr(stmt->range_low);
1186 __split_expr(stmt->range_high);
1187 break;
1188 }
1189 __pass_to_client(stmt, STMT_HOOK_AFTER);
1190 out:
1191 __process_post_op_stack();
1192 }
1193
1194 static void split_expr_list(struct expression_list *expr_list, struct expression *parent)
1195 {
1196 struct expression *expr;
1197
1198 FOR_EACH_PTR(expr_list, expr) {
1199 expr_set_parent_expr(expr, parent);
1200 __split_expr(expr);
1201 __process_post_op_stack();
1202 } END_FOR_EACH_PTR(expr);
1203 }
1204
1205 static void split_sym(struct symbol *sym)
1206 {
1207 if (!sym)
1208 return;
1209 if (!(sym->namespace & NS_SYMBOL))
1210 return;
1211
1212 __split_stmt(sym->stmt);
1213 __split_expr(sym->array_size);
1214 split_symlist(sym->arguments);
1215 split_symlist(sym->symbol_list);
1216 __split_stmt(sym->inline_stmt);
1217 split_symlist(sym->inline_symbol_list);
1218 }
1219
1220 static void split_symlist(struct symbol_list *sym_list)
1221 {
1222 struct symbol *sym;
1223
1224 FOR_EACH_PTR(sym_list, sym) {
1225 split_sym(sym);
1226 } END_FOR_EACH_PTR(sym);
1227 }
1228
1229 typedef void (fake_cb)(struct expression *expr);
1230
1231 static int member_to_number(struct expression *expr, struct ident *member)
1232 {
1233 struct symbol *type, *tmp;
1234 char *name;
1235 int i;
1236
1237 if (!member)
1238 return -1;
1239 name = member->name;
1240
1241 type = get_type(expr);
1242 if (!type || type->type != SYM_STRUCT)
1243 return -1;
1244
1245 i = -1;
1246 FOR_EACH_PTR(type->symbol_list, tmp) {
1247 i++;
1248 if (!tmp->ident)
1249 continue;
1250 if (strcmp(name, tmp->ident->name) == 0)
1251 return i;
1252 } END_FOR_EACH_PTR(tmp);
1253 return -1;
1254 }
1255
1256 static struct ident *number_to_member(struct expression *expr, int num)
1257 {
1258 struct symbol *type, *member;
1259 int i = 0;
1260
1261 type = get_type(expr);
1262 if (!type || type->type != SYM_STRUCT)
1263 return NULL;
1264
1265 FOR_EACH_PTR(type->symbol_list, member) {
1266 if (i == num)
1267 return member->ident;
1268 i++;
1269 } END_FOR_EACH_PTR(member);
1270 return NULL;
1271 }
1272
1273 static void fake_element_assigns_helper(struct expression *array, struct expression_list *expr_list, fake_cb *fake_cb);
1274
1275 static void set_inner_struct_members(struct expression *expr, struct symbol *member)
1276 {
1277 struct expression *edge_member, *assign;
1278 struct symbol *base = get_real_base_type(member);
1279 struct symbol *tmp;
1280
1281 if (member->ident)
1282 expr = member_expression(expr, '.', member->ident);
1283
1284 FOR_EACH_PTR(base->symbol_list, tmp) {
1285 struct symbol *type;
1286
1287 type = get_real_base_type(tmp);
1288 if (!type)
1289 continue;
1290
1291 edge_member = member_expression(expr, '.', tmp->ident);
1292 if (get_extra_state(edge_member))
1293 continue;
1294
1295 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
1296 set_inner_struct_members(expr, tmp);
1297 continue;
1298 }
1299
1300 if (!tmp->ident)
1301 continue;
1302
1303 assign = assign_expression(edge_member, '=', zero_expr());
1304 __split_expr(assign);
1305 } END_FOR_EACH_PTR(tmp);
1306
1307
1308 }
1309
1310 static void set_unset_to_zero(struct symbol *type, struct expression *expr)
1311 {
1312 struct symbol *tmp;
1313 struct expression *member = NULL;
1314 struct expression *assign;
1315 int op = '*';
1316
1317 if (expr->type == EXPR_PREOP && expr->op == '&') {
1318 expr = strip_expr(expr->unop);
1319 op = '.';
1320 }
1321
1322 FOR_EACH_PTR(type->symbol_list, tmp) {
1323 type = get_real_base_type(tmp);
1324 if (!type)
1325 continue;
1326
1327 if (tmp->ident) {
1328 member = member_expression(expr, op, tmp->ident);
1329 if (get_extra_state(member))
1330 continue;
1331 }
1332
1333 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
1334 set_inner_struct_members(expr, tmp);
1335 continue;
1336 }
1337 if (type->type == SYM_ARRAY)
1338 continue;
1339 if (!tmp->ident)
1340 continue;
1341
1342 assign = assign_expression(member, '=', zero_expr());
1343 __split_expr(assign);
1344 } END_FOR_EACH_PTR(tmp);
1345 }
1346
1347 static void fake_member_assigns_helper(struct expression *symbol, struct expression_list *members, fake_cb *fake_cb)
1348 {
1349 struct expression *deref, *assign, *tmp, *right;
1350 struct symbol *struct_type, *type;
1351 struct ident *member;
1352 int member_idx;
1353
1354 struct_type = get_type(symbol);
1355 if (!struct_type ||
1356 (struct_type->type != SYM_STRUCT && struct_type->type != SYM_UNION))
1357 return;
1358
1359 /*
1360 * We're parsing an initializer that could look something like this:
1361 * struct foo foo = {
1362 * 42,
1363 * .whatever.xxx = 11,
1364 * .zzz = 12,
1365 * };
1366 *
1367 * So what we have here is a list with 42, .whatever, and .zzz. We need
1368 * to break it up into left and right sides of the assignments.
1369 *
1370 */
1371 member_idx = 0;
1372 FOR_EACH_PTR(members, tmp) {
1373 deref = NULL;
1374 if (tmp->type == EXPR_IDENTIFIER) {
1375 member_idx = member_to_number(symbol, tmp->expr_ident);
1376 while (tmp->type == EXPR_IDENTIFIER) {
1377 member = tmp->expr_ident;
1378 tmp = tmp->ident_expression;
1379 if (deref)
1380 deref = member_expression(deref, '.', member);
1381 else
1382 deref = member_expression(symbol, '.', member);
1383 }
1384 } else {
1385 member = number_to_member(symbol, member_idx);
1386 deref = member_expression(symbol, '.', member);
1387 }
1388 right = tmp;
1389 member_idx++;
1390 if (right->type == EXPR_INITIALIZER) {
1391 type = get_type(deref);
1392 if (type && type->type == SYM_ARRAY)
1393 fake_element_assigns_helper(deref, right->expr_list, fake_cb);
1394 else
1395 fake_member_assigns_helper(deref, right->expr_list, fake_cb);
1396 } else {
1397 assign = assign_expression(deref, '=', right);
1398 fake_cb(assign);
1399 }
1400 } END_FOR_EACH_PTR(tmp);
1401
1402 set_unset_to_zero(struct_type, symbol);
1403 }
1404
1405 static void fake_member_assigns(struct symbol *sym, fake_cb *fake_cb)
1406 {
1407 fake_member_assigns_helper(symbol_expression(sym),
1408 sym->initializer->expr_list, fake_cb);
1409 }
1410
1411 static void fake_element_assigns_helper(struct expression *array, struct expression_list *expr_list, fake_cb *fake_cb)
1412 {
1413 struct expression *offset, *binop, *assign, *tmp;
1414 struct symbol *type;
1415 int idx;
1416
1417 if (ptr_list_size((struct ptr_list *)expr_list) > 1000)
1418 return;
1419
1420 idx = 0;
1421 FOR_EACH_PTR(expr_list, tmp) {
1422 if (tmp->type == EXPR_INDEX) {
1423 if (tmp->idx_from != tmp->idx_to)
1424 return;
1425 idx = tmp->idx_from;
1426 if (!tmp->idx_expression)
1427 goto next;
1428 tmp = tmp->idx_expression;
1429 }
1430 offset = value_expr(idx);
1431 binop = array_element_expression(array, offset);
1432 if (tmp->type == EXPR_INITIALIZER) {
1433 type = get_type(binop);
1434 if (type && type->type == SYM_ARRAY)
1435 fake_element_assigns_helper(binop, tmp->expr_list, fake_cb);
1436 else
1437 fake_member_assigns_helper(binop, tmp->expr_list, fake_cb);
1438 } else {
1439 assign = assign_expression(binop, '=', tmp);
1440 fake_cb(assign);
1441 }
1442 next:
1443 idx++;
1444 } END_FOR_EACH_PTR(tmp);
1445 }
1446
1447 static void fake_element_assigns(struct symbol *sym, fake_cb *fake_cb)
1448 {
1449 fake_element_assigns_helper(symbol_expression(sym), sym->initializer->expr_list, fake_cb);
1450 }
1451
1452 static void fake_assign_expr(struct symbol *sym)
1453 {
1454 struct expression *assign, *symbol;
1455
1456 symbol = symbol_expression(sym);
1457 assign = assign_expression(symbol, '=', sym->initializer);
1458 __split_expr(assign);
1459 }
1460
1461 static void do_initializer_stuff(struct symbol *sym)
1462 {
1463 if (!sym->initializer)
1464 return;
1465
1466 if (sym->initializer->type == EXPR_INITIALIZER) {
1467 if (get_real_base_type(sym)->type == SYM_ARRAY)
1468 fake_element_assigns(sym, __split_expr);
1469 else
1470 fake_member_assigns(sym, __split_expr);
1471 } else {
1472 fake_assign_expr(sym);
1473 }
1474 }
1475
1476 static void split_declaration(struct symbol_list *sym_list)
1477 {
1478 struct symbol *sym;
1479
1480 FOR_EACH_PTR(sym_list, sym) {
1481 __pass_to_client(sym, DECLARATION_HOOK);
1482 do_initializer_stuff(sym);
1483 split_sym(sym);
1484 } END_FOR_EACH_PTR(sym);
1485 }
1486
1487 static void call_global_assign_hooks(struct expression *assign)
1488 {
1489 __pass_to_client(assign, GLOBAL_ASSIGNMENT_HOOK);
1490 }
1491
1492 static void fake_global_assign(struct symbol *sym)
1493 {
1494 struct expression *assign, *symbol;
1495
1496 if (get_real_base_type(sym)->type == SYM_ARRAY) {
1497 if (sym->initializer && sym->initializer->type == EXPR_INITIALIZER) {
1498 fake_element_assigns(sym, call_global_assign_hooks);
1499 } else if (sym->initializer) {
1500 symbol = symbol_expression(sym);
1501 assign = assign_expression(symbol, '=', sym->initializer);
1502 __pass_to_client(assign, GLOBAL_ASSIGNMENT_HOOK);
1503 } else {
1504 fake_element_assigns_helper(symbol_expression(sym), NULL, call_global_assign_hooks);
1505 }
1506 } else if (get_real_base_type(sym)->type == SYM_STRUCT) {
1507 if (sym->initializer && sym->initializer->type == EXPR_INITIALIZER) {
1508 fake_member_assigns(sym, call_global_assign_hooks);
1509 } else if (sym->initializer) {
1510 symbol = symbol_expression(sym);
1511 assign = assign_expression(symbol, '=', sym->initializer);
1512 __pass_to_client(assign, GLOBAL_ASSIGNMENT_HOOK);
1513 } else {
1514 fake_member_assigns_helper(symbol_expression(sym), NULL, call_global_assign_hooks);
1515 }
1516 } else {
1517 symbol = symbol_expression(sym);
1518 if (sym->initializer)
1519 assign = assign_expression(symbol, '=', sym->initializer);
1520 else
1521 assign = assign_expression(symbol, '=', zero_expr());
1522 __pass_to_client(assign, GLOBAL_ASSIGNMENT_HOOK);
1523 }
1524 }
1525
1526 static void start_function_definition(struct symbol *sym)
1527 {
1528 __in_function_def = 1;
1529 __pass_to_client(sym, FUNC_DEF_HOOK);
1530 __in_function_def = 0;
1531 __pass_to_client(sym, AFTER_DEF_HOOK);
1532
1533 }
1534
1535 static void split_function(struct symbol *sym)
1536 {
1537 struct symbol *base_type = get_base_type(sym);
1538 struct timeval stop;
1539
1540 if (!base_type->stmt && !base_type->inline_stmt)
1541 return;
1542
1543 gettimeofday(&fn_start_time, NULL);
1544 cur_func_sym = sym;
1545 if (sym->ident)
1546 cur_func = sym->ident->name;
1547 set_position(sym->pos);
1548 loop_count = 0;
1549 last_goto_statement_handled = 0;
1550 sm_debug("new function: %s\n", cur_func);
1551 __stree_id = 0;
1552 if (option_two_passes) {
1553 __unnullify_path();
1554 loop_num = 0;
1555 final_pass = 0;
1556 start_function_definition(sym);
1557 __split_stmt(base_type->stmt);
1558 __split_stmt(base_type->inline_stmt);
1559 nullify_path();
1560 }
1561 __unnullify_path();
1562 loop_num = 0;
1563 final_pass = 1;
1564 start_function_definition(sym);
1565 __split_stmt(base_type->stmt);
1566 __split_stmt(base_type->inline_stmt);
1567 __pass_to_client(sym, END_FUNC_HOOK);
1568 if (need_delayed_scope_hooks())
1569 __call_scope_hooks();
1570 __pass_to_client(sym, AFTER_FUNC_HOOK);
1571
1572 clear_all_states();
1573
1574 gettimeofday(&stop, NULL);
1575 if (option_time && stop.tv_sec - fn_start_time.tv_sec > 2) {
1576 final_pass++;
1577 sm_msg("func_time: %lu", stop.tv_sec - fn_start_time.tv_sec);
1578 final_pass--;
1579 }
1580 cur_func_sym = NULL;
1581 cur_func = NULL;
1582 free_data_info_allocs();
1583 free_expression_stack(&switch_expr_stack);
1584 __free_ptr_list((struct ptr_list **)&big_statement_stack);
1585 __bail_on_rest_of_function = 0;
1586 }
1587
1588 static void save_flow_state(void)
1589 {
1590 __add_ptr_list(&backup, INT_PTR(loop_num << 2), 0);
1591 __add_ptr_list(&backup, INT_PTR(loop_count << 2), 0);
1592 __add_ptr_list(&backup, INT_PTR(final_pass << 2), 0);
1593
1594 __add_ptr_list(&backup, big_statement_stack, 0);
1595 __add_ptr_list(&backup, big_expression_stack, 0);
1596 __add_ptr_list(&backup, big_condition_stack, 0);
1597 __add_ptr_list(&backup, switch_expr_stack, 0);
1598
1599 __add_ptr_list(&backup, cur_func_sym, 0);
1600
1601 __add_ptr_list(&backup, __prev_stmt, 0);
1602 __add_ptr_list(&backup, __cur_stmt, 0);
1603 __add_ptr_list(&backup, __next_stmt, 0);
1604
1605 }
1606
1607 static void *pop_backup(void)
1608 {
1609 void *ret;
1610
1611 ret = last_ptr_list(backup);
1612 delete_ptr_list_last(&backup);
1613 return ret;
1614 }
1615
1616 static void restore_flow_state(void)
1617 {
1618 __next_stmt = pop_backup();
1619 __cur_stmt = pop_backup();
1620 __prev_stmt = pop_backup();
1621
1622 cur_func_sym = pop_backup();
1623 switch_expr_stack = pop_backup();
1624 big_condition_stack = pop_backup();
1625 big_expression_stack = pop_backup();
1626 big_statement_stack = pop_backup();
1627 final_pass = PTR_INT(pop_backup()) >> 2;
1628 loop_count = PTR_INT(pop_backup()) >> 2;
1629 loop_num = PTR_INT(pop_backup()) >> 2;
1630 }
1631
1632 static void parse_inline(struct expression *call)
1633 {
1634 struct symbol *base_type;
1635 char *cur_func_bak = cur_func; /* not aligned correctly for backup */
1636 struct timeval time_backup = fn_start_time;
1637 struct expression *orig_inline = __inline_fn;
1638 int orig_budget;
1639
1640 save_flow_state();
1641
1642 __pass_to_client(call, INLINE_FN_START);
1643 final_pass = 0; /* don't print anything */
1644 __inline_fn = call;
1645 orig_budget = inline_budget;
1646 inline_budget = inline_budget - 5;
1647
1648 base_type = get_base_type(call->fn->symbol);
1649 cur_func_sym = call->fn->symbol;
1650 if (call->fn->symbol->ident)
1651 cur_func = call->fn->symbol->ident->name;
1652 else
1653 cur_func = NULL;
1654 set_position(call->fn->symbol->pos);
1655
1656 save_all_states();
1657 big_statement_stack = NULL;
1658 big_expression_stack = NULL;
1659 big_condition_stack = NULL;
1660 switch_expr_stack = NULL;
1661
1662 sm_debug("inline function: %s\n", cur_func);
1663 __unnullify_path();
1664 loop_num = 0;
1665 loop_count = 0;
1666 start_function_definition(call->fn->symbol);
1667 __split_stmt(base_type->stmt);
1668 __split_stmt(base_type->inline_stmt);
1669 __pass_to_client(call->fn->symbol, END_FUNC_HOOK);
1670 __pass_to_client(call->fn->symbol, AFTER_FUNC_HOOK);
1671
1672 free_expression_stack(&switch_expr_stack);
1673 __free_ptr_list((struct ptr_list **)&big_statement_stack);
1674 nullify_path();
1675 free_goto_stack();
1676
1677 restore_flow_state();
1678 fn_start_time = time_backup;
1679 cur_func = cur_func_bak;
1680
1681 restore_all_states();
1682 set_position(call->pos);
1683 __inline_fn = orig_inline;
1684 inline_budget = orig_budget;
1685 __pass_to_client(call, INLINE_FN_END);
1686 }
1687
1688 static struct symbol_list *inlines_called;
1689 static void add_inline_function(struct symbol *sym)
1690 {
1691 static struct symbol_list *already_added;
1692 struct symbol *tmp;
1693
1694 FOR_EACH_PTR(already_added, tmp) {
1695 if (tmp == sym)
1696 return;
1697 } END_FOR_EACH_PTR(tmp);
1698
1699 add_ptr_list(&already_added, sym);
1700 add_ptr_list(&inlines_called, sym);
1701 }
1702
1703 static void process_inlines(void)
1704 {
1705 struct symbol *tmp;
1706
1707 FOR_EACH_PTR(inlines_called, tmp) {
1708 split_function(tmp);
1709 } END_FOR_EACH_PTR(tmp);
1710 free_ptr_list(&inlines_called);
1711 }
1712
1713 static struct symbol *get_last_scoped_symbol(struct symbol_list *big_list, int use_static)
1714 {
1715 struct symbol *sym;
1716
1717 FOR_EACH_PTR_REVERSE(big_list, sym) {
1718 if (!sym->scope)
1719 continue;
1720 if (use_static && sym->ctype.modifiers & MOD_STATIC)
1721 return sym;
1722 if (!use_static && !(sym->ctype.modifiers & MOD_STATIC))
1723 return sym;
1724 } END_FOR_EACH_PTR_REVERSE(sym);
1725
1726 return NULL;
1727 }
1728
1729 static bool interesting_function(struct symbol *sym)
1730 {
1731 static int prev_stream = -1;
1732 static bool prev_answer;
1733 const char *filename;
1734 int len;
1735
1736 if (!(sym->ctype.modifiers & MOD_INLINE))
1737 return true;
1738
1739 if (sym->pos.stream == prev_stream)
1740 return prev_answer;
1741
1742 prev_stream = sym->pos.stream;
1743 prev_answer = false;
1744
1745 filename = stream_name(sym->pos.stream);
1746 len = strlen(filename);
1747 if (len > 0 && filename[len - 1] == 'c')
1748 prev_answer = true;
1749 return prev_answer;
1750 }
1751
1752 static void split_inlines_in_scope(struct symbol *sym)
1753 {
1754 struct symbol *base;
1755 struct symbol_list *scope_list;
1756 int stream;
1757
1758 scope_list = sym->scope->symbols;
1759 stream = sym->pos.stream;
1760
1761 /* find the last static symbol in the file */
1762 FOR_EACH_PTR_REVERSE(scope_list, sym) {
1763 if (sym->pos.stream != stream)
1764 continue;
1765 if (sym->type != SYM_NODE)
1766 continue;
1767 base = get_base_type(sym);
1768 if (!base)
1769 continue;
1770 if (base->type != SYM_FN)
1771 continue;
1772 if (!base->inline_stmt)
1773 continue;
1774 if (!interesting_function(sym))
1775 continue;
1776 add_inline_function(sym);
1777 } END_FOR_EACH_PTR_REVERSE(sym);
1778
1779 process_inlines();
1780 }
1781
1782 static void split_inlines(struct symbol_list *sym_list)
1783 {
1784 struct symbol *sym;
1785
1786 sym = get_last_scoped_symbol(sym_list, 0);
1787 if (sym)
1788 split_inlines_in_scope(sym);
1789 sym = get_last_scoped_symbol(sym_list, 1);
1790 if (sym)
1791 split_inlines_in_scope(sym);
1792 }
1793
1794 static struct stree *clone_estates_perm(struct stree *orig)
1795 {
1796 struct stree *ret = NULL;
1797 struct sm_state *tmp;
1798
1799 FOR_EACH_SM(orig, tmp) {
1800 set_state_stree_perm(&ret, tmp->owner, tmp->name, tmp->sym, clone_estate_perm(tmp->state));
1801 } END_FOR_EACH_SM(tmp);
1802
1803 return ret;
1804 }
1805
1806 struct position last_pos;
1807 static void split_c_file_functions(struct symbol_list *sym_list)
1808 {
1809 struct symbol *sym;
1810
1811 __unnullify_path();
1812 FOR_EACH_PTR(sym_list, sym) {
1813 set_position(sym->pos);
1814 if (sym->type != SYM_NODE || get_base_type(sym)->type != SYM_FN) {
1815 __pass_to_client(sym, BASE_HOOK);
1816 fake_global_assign(sym);
1817 }
1818 } END_FOR_EACH_PTR(sym);
1819 global_states = clone_estates_perm(get_all_states_stree(SMATCH_EXTRA));
1820 nullify_path();
1821
1822 FOR_EACH_PTR(sym_list, sym) {
1823 set_position(sym->pos);
1824 last_pos = sym->pos;
1825 if (!interesting_function(sym))
1826 continue;
1827 if (sym->type == SYM_NODE && get_base_type(sym)->type == SYM_FN) {
1828 split_function(sym);
1829 process_inlines();
1830 }
1831 last_pos = sym->pos;
1832 } END_FOR_EACH_PTR(sym);
1833 split_inlines(sym_list);
1834 __pass_to_client(sym_list, END_FILE_HOOK);
1835 }
1836
1837 static int final_before_fake;
1838 void init_fake_env(void)
1839 {
1840 if (!in_fake_env)
1841 final_before_fake = final_pass;
1842 in_fake_env++;
1843 __push_fake_cur_stree();
1844 final_pass = 0;
1845 }
1846
1847 void end_fake_env(void)
1848 {
1849 __pop_fake_cur_stree();
1850 in_fake_env--;
1851 if (!in_fake_env)
1852 final_pass = final_before_fake;
1853 }
1854
1855 static void open_output_files(char *base_file)
1856 {
1857 char buf[256];
1858
1859 snprintf(buf, sizeof(buf), "%s.smatch", base_file);
1860 sm_outfd = fopen(buf, "w");
1861 if (!sm_outfd) {
1862 printf("Error: Cannot open %s\n", buf);
1863 exit(1);
1864 }
1865
1866 if (!option_info)
1867 return;
1868
1869 snprintf(buf, sizeof(buf), "%s.smatch.sql", base_file);
1870 sql_outfd = fopen(buf, "w");
1871 if (!sql_outfd) {
1872 printf("Error: Cannot open %s\n", buf);
1873 exit(1);
1874 }
1875
1876 snprintf(buf, sizeof(buf), "%s.smatch.caller_info", base_file);
1877 caller_info_fd = fopen(buf, "w");
1878 if (!caller_info_fd) {
1879 printf("Error: Cannot open %s\n", buf);
1880 exit(1);
1881 }
1882 }
1883
1884 void smatch(int argc, char **argv)
1885 {
1886 struct string_list *filelist = NULL;
1887 struct symbol_list *sym_list;
1888 struct timeval stop, start;
1889 char *path;
1890 int len;
1891
1892 gettimeofday(&start, NULL);
1893
1894 if (argc < 2) {
1895 printf("Usage: smatch [--debug] <filename.c>\n");
1896 exit(1);
1897 }
1898 sparse_initialize(argc, argv, &filelist);
1899 set_valid_ptr_max();
1900 alloc_valid_ptr_rl();
1901 FOR_EACH_PTR_NOTAG(filelist, base_file) {
1902 path = getcwd(NULL, 0);
1903 free(full_base_file);
1904 if (path) {
1905 len = strlen(path) + 1 + strlen(base_file) + 1;
1906 full_base_file = malloc(len);
1907 snprintf(full_base_file, len, "%s/%s", path, base_file);
1908 } else {
1909 full_base_file = alloc_string(base_file);
1910 }
1911 if (option_file_output)
1912 open_output_files(base_file);
1913 sym_list = sparse_keep_tokens(base_file);
1914 split_c_file_functions(sym_list);
1915 } END_FOR_EACH_PTR_NOTAG(base_file);
1916
1917 gettimeofday(&stop, NULL);
1918
1919 set_position(last_pos);
1920 if (option_time)
1921 sm_msg("time: %lu", stop.tv_sec - start.tv_sec);
1922 if (option_mem)
1923 sm_msg("mem: %luKb", get_max_memory());
1924 }
Static analysis for C