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