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