smatch_flow.c

   1 /*
   2  * sparse/smatch_flow.c
   3  *
   4  * Copyright (C) 2006,2008 Dan Carpenter.
   5  *
   6  *  Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #define _GNU_SOURCE 1
  11 #include <unistd.h>
  12 #include <stdio.h>
  13 #include "token.h"
  14 #include "smatch.h"
  15 #include "smatch_expression_stacks.h"
  16 #include "smatch_extra.h"
  17 #include "smatch_slist.h" // just for sname.
  18
  19 int final_pass;
  20
  21 static int __smatch_lineno = 0;
  22
  23 static char *filename;
  24 static char *pathname;
  25 static char *full_filename;
  26 static char *cur_func;
  27 static int line_func_start;
  28 static struct expression_stack *switch_expr_stack = NULL;
  29
  30 char *get_function(void) { return cur_func; }
  31 int get_lineno(void) { return __smatch_lineno; }
  32 int get_func_pos(void) { return __smatch_lineno - line_func_start; }
  33
  34 static void split_symlist(struct symbol_list *sym_list);
  35 static void split_declaration(struct symbol_list *sym_list);
  36 static void split_expr_list(struct expression_list *expr_list);
  37
  38 int option_assume_loops = 0;
  39 int option_known_conditions = 0;
  40 int option_two_passes = 0;
  41 struct symbol *cur_func_sym = NULL;
  42
  43 char *get_filename(void)
  44 {
  45         if (option_full_path)
  46                 return full_filename;
  47         return filename;
  48 }
  49
  50 void __split_expr(struct expression *expr)
  51 {
  52         if (!expr)
  53                 return;
  54
  55         // printf("%d Debug expr_type %d %s\n", get_lineno(), expr->type, show_special(expr->op));
  56
  57         __smatch_lineno = expr->pos.line;
  58         __pass_to_client(expr, EXPR_HOOK);
  59
  60         switch (expr->type) {
  61         case EXPR_PREOP:
  62                 if (expr->op == '*')
  63                         __pass_to_client(expr, DEREF_HOOK);
  64         case EXPR_POSTOP:
  65                 __pass_to_client(expr, OP_HOOK);
  66                 __split_expr(expr->unop);
  67                 return;
  68         case EXPR_STATEMENT:
  69                 __split_statements(expr->statement);
  70                 return;
  71         case EXPR_LOGICAL:
  72                 __split_whole_condition(expr);
  73                 __push_true_states();
  74                 __use_false_states();
  75                 __merge_true_states();
  76                 __pop_false_only_stack();
  77                 return;
  78
  79                 return;
  80         case EXPR_BINOP:
  81         case EXPR_COMMA:
  82         case EXPR_COMPARE:
  83                 __split_expr(expr->left);
  84                 __split_expr(expr->right);
  85                 return;
  86         case EXPR_ASSIGNMENT: {
  87                 struct expression *tmp;
  88
  89                 __split_expr(expr->right);
  90                 __pass_to_client(expr, ASSIGNMENT_HOOK);
  91                 tmp = strip_expr(expr->right);
  92                 if (tmp->type == EXPR_CALL)
  93                         __pass_to_client(expr, CALL_ASSIGNMENT_HOOK);
  94                 __split_expr(expr->left);
  95                 return;
  96         }
  97         case EXPR_DEREF:
  98                 __pass_to_client(expr, DEREF_HOOK);
  99                 __split_expr(expr->deref);
 100                 return;
 101         case EXPR_SLICE:
 102                 __split_expr(expr->base);
 103                 return;
 104         case EXPR_CAST:
 105                 __split_expr(expr->cast_expression);
 106                 return;
 107         case EXPR_SIZEOF:
 108                 /* there isn't anything to pass a client from inside a sizeof() */
 109                 return;
 110         case EXPR_CONDITIONAL:
 111         case EXPR_SELECT:
 112                 __split_whole_condition(expr->conditional);
 113                 __split_expr(expr->cond_true);
 114                 __push_true_states();
 115                 __use_false_states();
 116                 __split_expr(expr->cond_false);
 117                 __merge_true_states();
 118                 __pop_false_only_stack();
 119                 return;
 120         case EXPR_CALL:
 121                 split_expr_list(expr->args);
 122                 __split_expr(expr->fn);
 123                 __pass_to_client(expr, FUNCTION_CALL_HOOK);
 124                 return;
 125         case EXPR_INITIALIZER:
 126                 split_expr_list(expr->expr_list);
 127                 return;
 128         case EXPR_IDENTIFIER:
 129                 __split_expr(expr->ident_expression);
 130                 return;
 131         case EXPR_INDEX:
 132                 __split_expr(expr->idx_expression);
 133                 return;
 134         case EXPR_POS:
 135                 __split_expr(expr->init_expr);
 136                 return;
 137         default:
 138                 return;
 139         };
 140 }
 141
 142 static int is_forever_loop(struct statement *stmt)
 143 {
 144
 145         struct expression *expr;
 146
 147         expr = strip_expr(stmt->iterator_pre_condition);
 148         if (!expr)
 149                 expr = stmt->iterator_post_condition;
 150         if (!expr) {
 151                 /* this is a for(;;) loop... */
 152                 return 1;
 153         }
 154
 155         if (expr->type == EXPR_VALUE && expr->value == 1) {
 156                 return 1;
 157         }
 158
 159         return 0;
 160 }
 161
 162 static int loop_num;
 163 static char *get_loop_name(int num)
 164 {
 165         char buf[256];
 166
 167         snprintf(buf, 255, "-loop%d", num);
 168         buf[255] = '\0';
 169         return alloc_sname(buf);;
 170 }
 171
 172 /*
 173  * Pre Loops are while and for loops.
 174  */
 175
 176 static void handle_pre_loop(struct statement *stmt)
 177 {
 178         int once_through; /* we go through the loop at least once */
 179         struct sm_state *extra_state = NULL;
 180         int unchanged = 0;
 181         char *loop_name;
 182
 183         loop_name = get_loop_name(loop_num);
 184         loop_num++;
 185
 186         __split_statements(stmt->iterator_pre_statement);
 187
 188         once_through = implied_condition_true(stmt->iterator_pre_condition);
 189
 190         __push_continues();
 191         __push_breaks();
 192
 193         __merge_gotos(loop_name);
 194         __split_whole_condition(stmt->iterator_pre_condition);
 195         if (once_through)
 196                 extra_state = __extra_pre_loop_hook_before(stmt->iterator_pre_statement);
 197         if (option_assume_loops)
 198                 once_through = 1;
 199         __split_statements(stmt->iterator_statement);
 200
 201         __warn_on_silly_pre_loops();
 202         if (is_forever_loop(stmt)) {
 203                 __save_gotos(loop_name);
 204                 __pop_false_only_stack();
 205                 /* forever loops don't have an iterator_post_statement */
 206                 __pop_continues();
 207                 __pop_false_states();
 208                 __use_breaks();
 209         } else if (once_through) {
 210                 __merge_continues();
 211                 if (extra_state)
 212                         unchanged = __iterator_unchanged(extra_state, stmt->iterator_post_statement);
 213                 __split_statements(stmt->iterator_post_statement);
 214                 __save_gotos(loop_name);
 215                 __split_whole_condition(stmt->iterator_pre_condition);
 216                 nullify_path();
 217                 __merge_false_states();
 218                 if (extra_state && unchanged)
 219                         __extra_pre_loop_hook_after(extra_state,
 220                                 stmt->iterator_post_statement, stmt->iterator_pre_condition);
 221                 __pop_false_states();
 222                 __pop_false_only_stack();
 223                 __pop_false_only_stack();
 224                 __merge_breaks();
 225         } else {
 226                 __merge_continues();
 227                 __split_statements(stmt->iterator_post_statement);
 228                 __save_gotos(loop_name);
 229                 __merge_false_states();
 230                 __use_false_only_stack();
 231                 __merge_breaks();
 232         }
 233 }
 234
 235 /*
 236  * Post loops are do {} while();
 237  */
 238 static void handle_post_loop(struct statement *stmt)
 239 {
 240         char *loop_name;
 241
 242         loop_name = get_loop_name(loop_num);
 243         loop_num++;
 244
 245         __push_continues();
 246         __push_breaks();
 247         __merge_gotos(loop_name);
 248         __split_statements(stmt->iterator_statement);
 249         __merge_continues();
 250         if (!is_zero(stmt->iterator_post_condition))
 251                 __save_gotos(loop_name);
 252
 253         if (is_forever_loop(stmt)) {
 254                 __use_breaks();
 255         } else {
 256                 __split_whole_condition(stmt->iterator_post_condition);
 257                 __use_false_states();
 258                 __merge_breaks();
 259         }
 260         __pop_false_only_stack();
 261 }
 262
 263 static void print_unreached(struct statement *stmt)
 264 {
 265
 266         /*
 267          * GCC insists on a return statement even where it is never
 268          * reached.  Also BUG() sometimes is a forever loop and
 269          * sometimes not so people put code after a BUG().  There
 270          * are way to many false positives.
 271          */
 272         return;
 273
 274         if (__path_is_null()) {
 275                 switch(stmt->type) {
 276                 case STMT_COMPOUND: /* after a switch before a case stmt */
 277                 case STMT_CASE:
 278                 case STMT_LABEL:
 279                 case STMT_DECLARATION: /* switch(x) { int a; case foo: ... */
 280                         break;
 281                 default:
 282                         sm_msg("unreachable code. %d", stmt->type);
 283                 }
 284         }
 285 }
 286
 287 void __split_statements(struct statement *stmt)
 288 {
 289         if (!stmt)
 290                 return;
 291
 292         if (out_of_memory()) {
 293                 static char *printed = NULL;
 294
 295                 if (printed != cur_func)
 296                         sm_msg("Function too big.  Giving up.");
 297                 printed = cur_func;
 298                 return;
 299         }
 300
 301         __smatch_lineno = stmt->pos.line;
 302         print_unreached(stmt);
 303         __pass_to_client(stmt, STMT_HOOK);
 304
 305         switch (stmt->type) {
 306         case STMT_DECLARATION:
 307                 split_declaration(stmt->declaration);
 308                 return;
 309         case STMT_RETURN:
 310                 __split_expr(stmt->ret_value);
 311                 __pass_to_client(stmt->ret_value, RETURN_HOOK);
 312                 nullify_path();
 313                 return;
 314         case STMT_EXPRESSION:
 315                 __split_expr(stmt->expression);
 316                 return;
 317         case STMT_COMPOUND: {
 318                 struct statement *s;
 319                 __push_scope_hooks();
 320                 FOR_EACH_PTR(stmt->stmts, s) {
 321                         __split_statements(s);
 322                 } END_FOR_EACH_PTR(s);
 323                 __call_scope_hooks();
 324                 return;
 325         }
 326         case STMT_IF:
 327                 if (known_condition_true(stmt->if_conditional)) {
 328                         __split_statements(stmt->if_true);
 329                         return;
 330                 }
 331                 if (known_condition_false(stmt->if_conditional)) {
 332                         __split_statements(stmt->if_false);
 333                         return;
 334                 }
 335                 if (option_known_conditions &&
 336                     implied_condition_true(stmt->if_conditional)) {
 337                         sm_msg("info: this condition is true.");
 338                         __split_statements(stmt->if_true);
 339                         return;
 340                 }
 341                 if (option_known_conditions &&
 342                     implied_condition_false(stmt->if_conditional)) {
 343                         sm_msg("info: this condition is false.");
 344                         __split_statements(stmt->if_false);
 345                         return;
 346                 }
 347                 __split_whole_condition(stmt->if_conditional);
 348                 __split_statements(stmt->if_true);
 349                 __push_true_states();
 350                 __use_false_states();
 351                 __split_statements(stmt->if_false);
 352                 __merge_true_states();
 353                 __pop_false_only_stack();
 354                 return;
 355         case STMT_ITERATOR:
 356                 if (stmt->iterator_pre_condition)
 357                         handle_pre_loop(stmt);
 358                 else if (stmt->iterator_post_condition)
 359                         handle_post_loop(stmt);
 360                 else {
 361                         // these are for(;;) type loops.
 362                         handle_pre_loop(stmt);
 363                 }
 364                 return;
 365         case STMT_SWITCH:
 366                 __split_expr(stmt->switch_expression);
 367                 push_expression(&switch_expr_stack, stmt->switch_expression);
 368                 __save_switch_states(top_expression(switch_expr_stack));
 369                 nullify_path();
 370                 __push_default();
 371                 __push_breaks();
 372                 __split_statements(stmt->switch_statement);
 373                 if (!__pop_default())
 374                         __merge_switches(top_expression(switch_expr_stack),
 375                                       NULL);
 376                 __pop_switches();
 377                 __merge_breaks();
 378                 pop_expression(&switch_expr_stack);
 379                 return;
 380         case STMT_CASE:
 381                 __merge_switches(top_expression(switch_expr_stack),
 382                                       stmt->case_expression);
 383                 __pass_case_to_client(top_expression(switch_expr_stack),
 384                                       stmt->case_expression);
 385                 if (!stmt->case_expression)
 386                         __set_default();
 387                 __split_expr(stmt->case_expression);
 388                 __split_expr(stmt->case_to);
 389                 __split_statements(stmt->case_statement);
 390                 return;
 391         case STMT_LABEL:
 392                 if (stmt->label &&
 393                     stmt->label->type == SYM_LABEL &&
 394                     stmt->label->ident) {
 395                         __merge_gotos(stmt->label->ident->name);
 396                 }
 397                 __split_statements(stmt->label_statement);
 398                 return;
 399         case STMT_GOTO:
 400                 __split_expr(stmt->goto_expression);
 401                 if (stmt->goto_label && stmt->goto_label->type == SYM_NODE) {
 402                         if (!strcmp(stmt->goto_label->ident->name, "break")) {
 403                                 __process_breaks();
 404                         } else if (!strcmp(stmt->goto_label->ident->name,
 405                                            "continue")) {
 406                                 __process_continues();
 407                         }
 408                 } else if (stmt->goto_label &&
 409                            stmt->goto_label->type == SYM_LABEL &&
 410                            stmt->goto_label->ident) {
 411                         __save_gotos(stmt->goto_label->ident->name);
 412                 }
 413                 nullify_path();
 414                 return;
 415         case STMT_NONE:
 416                 return;
 417         case STMT_ASM:
 418                 __split_expr(stmt->asm_string);
 419                 //__split_expr(stmt->asm_outputs);
 420                 //__split_expr(stmt->asm_inputs);
 421                 //__split_expr(stmt->asm_clobbers);
 422                 return;
 423         case STMT_CONTEXT:
 424                 return;
 425         case STMT_RANGE:
 426                 __split_expr(stmt->range_expression);
 427                 __split_expr(stmt->range_low);
 428                 __split_expr(stmt->range_high);
 429                 return;
 430         }
 431 }
 432
 433 static void split_expr_list(struct expression_list *expr_list)
 434 {
 435         struct expression *expr;
 436         FOR_EACH_PTR(expr_list, expr) {
 437                 __split_expr(expr);
 438         } END_FOR_EACH_PTR(expr);
 439 }
 440
 441
 442 static void split_sym(struct symbol *sym)
 443 {
 444         if (!sym)
 445                 return;
 446         if (!(sym->namespace & NS_SYMBOL))
 447                 return;
 448
 449         __pass_to_client(sym, SYM_HOOK);
 450         __split_statements(sym->stmt);
 451         __split_expr(sym->array_size);
 452         split_symlist(sym->arguments);
 453         split_symlist(sym->symbol_list);
 454         __split_statements(sym->inline_stmt);
 455         split_symlist(sym->inline_symbol_list);
 456         __split_expr(sym->initializer);
 457 }
 458
 459 static void split_symlist(struct symbol_list *sym_list)
 460 {
 461         struct symbol *sym;
 462
 463         FOR_EACH_PTR(sym_list, sym) {
 464                 split_sym(sym);
 465         } END_FOR_EACH_PTR(sym);
 466 }
 467
 468 static struct expression *fake_assign_expr(struct symbol *sym)
 469 {
 470         struct expression *e_assign, *e_symbol;
 471
 472         e_assign = alloc_expression(sym->initializer->pos, EXPR_ASSIGNMENT);
 473         e_symbol = alloc_expression(sym->initializer->pos, EXPR_SYMBOL);
 474         e_assign->op = (int)'=';
 475         e_symbol->symbol = sym;
 476         e_symbol->symbol_name = sym->ident;
 477         e_assign->left = e_symbol;
 478         e_assign->right = sym->initializer;
 479         return e_assign;
 480 }
 481
 482 static void split_declaration(struct symbol_list *sym_list)
 483 {
 484         struct symbol *sym;
 485         struct expression *assign, *tmp;
 486
 487         FOR_EACH_PTR(sym_list, sym) {
 488                 __pass_to_client(sym, DECLARATION_HOOK);
 489                 __split_expr(sym->initializer);
 490                 if(sym->initializer) {
 491                         assign = fake_assign_expr(sym);
 492                         __pass_to_client(assign, ASSIGNMENT_HOOK);
 493                         tmp = strip_expr(assign->right);
 494                         if (tmp->type == EXPR_CALL)
 495                                 __pass_to_client(assign, CALL_ASSIGNMENT_HOOK);
 496                 }
 497                 split_sym(sym);
 498         } END_FOR_EACH_PTR(sym);
 499 }
 500
 501 static void split_functions(struct symbol_list *sym_list)
 502 {
 503         struct symbol *sym;
 504
 505         FOR_EACH_PTR(sym_list, sym) {
 506                 struct symbol *base_type;
 507                 base_type = get_base_type(sym);
 508                 if (sym->type == SYM_NODE && base_type->type == SYM_FN) {
 509                         cur_func_sym = sym;
 510                         if (base_type->stmt)
 511                                 line_func_start = base_type->stmt->pos.line;
 512                         if (sym->ident)
 513                                 cur_func = sym->ident->name;
 514                         __smatch_lineno = sym->pos.line;
 515                         sm_debug("new function:  %s\n", cur_func);
 516                         if (option_two_passes) {
 517                                 __unnullify_path();
 518                                 loop_num = 0;
 519                                 final_pass = 0;
 520                                 __pass_to_client(sym, FUNC_DEF_HOOK);
 521                                 __split_statements(base_type->stmt);
 522                                 nullify_path();
 523                         }
 524                         __unnullify_path();
 525                         loop_num = 0;
 526                         final_pass = 1;
 527                         __pass_to_client(sym, FUNC_DEF_HOOK);
 528                         __split_statements(base_type->stmt);
 529                         __pass_to_client(sym, END_FUNC_HOOK);
 530                         cur_func = NULL;
 531                         line_func_start = 0;
 532                         clear_all_states();
 533                         free_data_info_allocs();
 534                         free_expression_stack(&switch_expr_stack);
 535                 } else {
 536                         __pass_to_client(sym, BASE_HOOK);
 537                 }
 538         } END_FOR_EACH_PTR(sym);
 539         __pass_to_client_no_data(END_FILE_HOOK);
 540 }
 541
 542 void smatch (int argc, char **argv)
 543 {
 544
 545         struct string_list *filelist = NULL;
 546         struct symbol_list *sym_list;
 547
 548         if (argc < 2) {
 549                 printf("Usage:  smatch [--debug] <filename.c>\n");
 550                 exit(1);
 551         }
 552         sparse_initialize(argc, argv, &filelist);
 553         FOR_EACH_PTR_NOTAG(filelist, filename) {
 554                 int len;
 555
 556                 pathname = get_current_dir_name();
 557                 if (pathname) {
 558                         len = strlen(pathname) + 1 + strlen(filename) + 1;
 559                         full_filename = malloc(len);
 560                         snprintf(full_filename, len, "%s/%s", pathname, filename);
 561                 } else {
 562                         full_filename = filename;
 563                 }
 564
 565                 sym_list = __sparse(filename);
 566                 split_functions(sym_list);
 567
 568                 if (pathname) {
 569                         free(full_filename);
 570                         free(pathname);
 571                 }
 572         } END_FOR_EACH_PTR_NOTAG(filename);
 573 }