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