smatch_flow.c

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