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