smatch_helper.c

   1 /*
   2  * sparse/smatch_helper.c
   3  *
   4  * Copyright (C) 2006 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * Miscellaneous helper functions.
  12  */
  13
  14 #include <stdlib.h>
  15 #include <stdio.h>
  16 #include "allocate.h"
  17 #include "smatch.h"
  18
  19 #define VAR_LEN 512
  20 #define BOGUS 12345
  21
  22 char *alloc_string(const char *str)
  23 {
  24         char *tmp;
  25
  26         if (!str)
  27                 return NULL;
  28         tmp = malloc(strlen(str) + 1);
  29         strcpy(tmp, str);
  30         return tmp;
  31 }
  32
  33 void free_string(char *str)
  34 {
  35         free(str);
  36 }
  37
  38 struct smatch_state *alloc_state_num(int num)
  39 {
  40         struct smatch_state *state;
  41         static char buff[256];
  42
  43         state = __alloc_smatch_state(0);
  44         snprintf(buff, 255, "%d", num);
  45         buff[255] = '\0';
  46         state->name = alloc_string(buff);
  47         state->data = (void *)num;
  48         return state;
  49 }
  50
  51 static void append(char *dest, const char *data, int buff_len)
  52 {
  53         strncat(dest, data, buff_len - strlen(dest) - 1);
  54 }
  55
  56 /*
  57  * If you have "foo(a, b, 1);" then use
  58  * get_argument_from_call_expr(expr, 0) to return the expression for
  59  * a.  Yes, it does start counting from 0.
  60  */
  61 struct expression *get_argument_from_call_expr(struct expression_list *args,
  62                                                int num)
  63 {
  64         struct expression *expr;
  65         int i = 0;
  66
  67         if (!args)
  68                 return NULL;
  69
  70         FOR_EACH_PTR(args, expr) {
  71                 if (i == num)
  72                         return expr;
  73                 i++;
  74         } END_FOR_EACH_PTR(expr);
  75         return NULL;
  76 }
  77
  78 static struct expression *get_array_expr(struct expression *expr)
  79 {
  80         struct symbol *type;
  81
  82         if (expr->type != EXPR_BINOP || expr->op != '+')
  83                 return NULL;
  84
  85         type = get_type(expr->left);
  86         if (!type || type->type != SYM_ARRAY)
  87                 return NULL;
  88         return expr->left;
  89 }
  90
  91 static void __get_variable_from_expr(struct symbol **sym_ptr, char *buf,
  92                                      struct expression *expr, int len,
  93                                      int *complicated)
  94 {
  95         struct expression *tmp;
  96
  97         switch (expr->type) {
  98         case EXPR_DEREF:
  99                 tmp = expr->deref;
 100                 if (tmp->op == '*')  {
 101                         tmp = tmp->unop;
 102                 }
 103                 __get_variable_from_expr(sym_ptr, buf, tmp, len, complicated);
 104
 105                 tmp = expr->deref;
 106                 if (tmp->op == '*')  {
 107                         append(buf, "->", len);
 108                 } else {
 109                         append(buf, ".", len);
 110                 }
 111                 append(buf, expr->member->name, len);
 112
 113                 return;
 114         case EXPR_SYMBOL:
 115                 if (expr->symbol_name)
 116                         append(buf, expr->symbol_name->name, len);
 117                 if (sym_ptr) {
 118                         if (*sym_ptr)
 119                                 *complicated = 1;
 120                         *sym_ptr = expr->symbol;
 121                 }
 122                 return;
 123         case EXPR_PREOP: {
 124                 const char *tmp;
 125
 126                 if (get_block_thing(expr)) {
 127                         *complicated = 2;
 128                         return;
 129                 }
 130
 131                 if (expr->op != '*' || !get_array_expr(expr->unop)) {
 132                         tmp = show_special(expr->op);
 133                         append(buf, tmp, len);
 134                 }
 135                 __get_variable_from_expr(sym_ptr, buf, expr->unop,
 136                                                  len, complicated);
 137
 138                 if (expr->op == '(') {
 139                         append(buf, ")", len);
 140                 }
 141
 142                 if (expr->op == SPECIAL_DECREMENT || expr->op == SPECIAL_INCREMENT)
 143                         *complicated = 1;
 144
 145                 return;
 146         }
 147         case EXPR_POSTOP: {
 148                 const char *tmp;
 149
 150                 __get_variable_from_expr(sym_ptr, buf, expr->unop,
 151                                                  len, complicated);
 152                 tmp = show_special(expr->op);
 153                 append(buf, tmp, len);
 154
 155                 if (expr->op == SPECIAL_DECREMENT || expr->op == SPECIAL_INCREMENT)
 156                         *complicated = 1;
 157                 return;
 158         }
 159         case EXPR_BINOP: {
 160                 const char *tmp;
 161                 struct expression *array_expr;
 162
 163                 *complicated = 1;
 164                 array_expr = get_array_expr(expr);
 165                 if (array_expr) {
 166                         __get_variable_from_expr(NULL, buf, array_expr, len, complicated);
 167                         append(buf, "[", len);
 168                 } else {
 169                         append(buf, "(", len);
 170                         __get_variable_from_expr(NULL, buf, expr->left, len,
 171                                          complicated);
 172                         tmp = show_special(expr->op);
 173                         append(buf, tmp, len);
 174                 }
 175                 __get_variable_from_expr(sym_ptr, buf, expr->right,
 176                                                  len, complicated);
 177                 if (array_expr)
 178                         append(buf, "]", len);
 179                 else
 180                         append(buf, ")", len);
 181                 return;
 182         }
 183         case EXPR_VALUE: {
 184                 char tmp[25];
 185
 186                 snprintf(tmp, 25, "%lld", expr->value);
 187                 append(buf, tmp, len);
 188                 return;
 189         }
 190         case EXPR_STRING:
 191                 append(buf, "\"", len);
 192                 append(buf, expr->string->data, len);
 193                 append(buf, "\"", len);
 194                 return;
 195         case EXPR_CALL: {
 196                 struct expression *tmp;
 197                 int i;
 198
 199                 *complicated = 1;
 200                 __get_variable_from_expr(NULL, buf, expr->fn, len,
 201                                          complicated);
 202                 append(buf, "(", len);
 203                 i = 0;
 204                 FOR_EACH_PTR_REVERSE(expr->args, tmp) {
 205                         if (i++)
 206                                 append(buf, ", ", len);
 207                         __get_variable_from_expr(NULL, buf, tmp, len,
 208                                                 complicated);
 209                 } END_FOR_EACH_PTR_REVERSE(tmp);
 210                 append(buf, ")", len);
 211                 return;
 212         }
 213         case EXPR_CAST:
 214                 __get_variable_from_expr(sym_ptr, buf,
 215                                          expr->cast_expression, len,
 216                                          complicated);
 217                 return;
 218         case EXPR_SIZEOF: {
 219                 int size;
 220                 char tmp[25];
 221
 222                 if (expr->cast_type && get_base_type(expr->cast_type)) {
 223                         size = (get_base_type(expr->cast_type))->bit_size;
 224                         snprintf(tmp, 25, "%d", size);
 225                         append(buf, tmp, len);
 226                 }
 227                 return;
 228         }
 229         default:
 230                 *complicated = 1;
 231                 //printf("unknown type = %d\n", expr->type);
 232                 return;
 233         }
 234 }
 235
 236
 237 /*
 238  * This is returns a stylized "c looking" representation of the
 239  * variable name.
 240  *
 241  * It uses the same buffer every time so you have to save the result
 242  * yourself if you want to keep it.
 243  *
 244  */
 245
 246 char *get_variable_from_expr_complex(struct expression *expr, struct symbol **sym_ptr)
 247 {
 248         static char var_name[VAR_LEN];
 249         int complicated = 0;
 250
 251         if (sym_ptr)
 252                 *sym_ptr = NULL;
 253         var_name[0] = '\0';
 254
 255         if (!expr)
 256                 return NULL;
 257         __get_variable_from_expr(sym_ptr, var_name, expr, sizeof(var_name),
 258                                  &complicated);
 259         if (complicated < 2)
 260                 return alloc_string(var_name);
 261         else
 262                 return NULL;
 263 }
 264
 265 /*
 266  * get_variable_from_expr_simple() only returns simple variables.
 267  * If it's a complicated variable like a->foo instead of just 'a'
 268  * then it returns NULL.
 269  */
 270
 271 char *get_variable_from_expr(struct expression *expr,
 272                                     struct symbol **sym_ptr)
 273 {
 274         static char var_name[VAR_LEN];
 275         int complicated = 0;
 276
 277         if (sym_ptr)
 278                 *sym_ptr = NULL;
 279         var_name[0] = '\0';
 280
 281         if (!expr)
 282                 return NULL;
 283         expr = strip_expr(expr);
 284         __get_variable_from_expr(sym_ptr, var_name, expr, sizeof(var_name),
 285                                  &complicated);
 286
 287         if (complicated) {
 288                 if (sym_ptr)
 289                         *sym_ptr = NULL;
 290                 return NULL;
 291         }
 292         return alloc_string(var_name);
 293 }
 294
 295 int sym_name_is(const char *name, struct expression *expr)
 296 {
 297         if (!expr)
 298                 return 0;
 299         if (expr->type != EXPR_SYMBOL)
 300                 return 0;
 301         if (!strcmp(expr->symbol_name->name, name))
 302                 return 1;
 303         return 0;
 304 }
 305
 306 static long long cast_to_type(struct expression *expr, long long val)
 307 {
 308         struct symbol *type = get_type(expr);
 309
 310         if (!type)
 311                 return val;
 312
 313         switch (type->bit_size) {
 314         case 8:
 315                 if (type->ctype.modifiers & MOD_UNSIGNED)
 316                         val = (long long)(unsigned char) val;
 317                 else
 318                         val = (long long)(char) val;
 319                 break;
 320         case 16:
 321                 if (type->ctype.modifiers & MOD_UNSIGNED)
 322                         val = (long long)(unsigned short) val;
 323                 else
 324                         val = (long long)(short) val;
 325                 break;
 326         case 32:
 327                 if (type->ctype.modifiers & MOD_UNSIGNED)
 328                         val = (long long)(unsigned int) val;
 329                 else
 330                         val = (long long)(int) val;
 331                 break;
 332         }
 333         return val;
 334 }
 335
 336 #define NOTIMPLIED 0
 337 #define IMPLIED 1
 338 #define FUZZYMAX 2
 339 #define FUZZYMIN 3
 340
 341 static long long _get_value(struct expression *expr, int *discard, int *undefined, int implied)
 342 {
 343         int dis = 0;
 344         long long ret = BOGUS;
 345
 346         if (!expr) {
 347                 *undefined = 1;
 348                 return BOGUS;
 349         }
 350         if (!discard)
 351                 discard = &dis;
 352         if (*discard) {
 353                 *undefined = 1;
 354                 return BOGUS;
 355         }
 356
 357         expr = strip_parens(expr);
 358
 359         switch (expr->type){
 360         case EXPR_VALUE:
 361                 ret = expr->value;
 362                 ret = cast_to_type(expr, ret);
 363                 break;
 364         case EXPR_PREOP:
 365                 switch(expr->op) {
 366                 case '~':
 367                         ret = ~ _get_value(expr->unop, discard, undefined, implied);
 368                         ret = cast_to_type(expr->unop, ret);
 369                         break;
 370                 case '-':
 371                         ret = - _get_value(expr->unop, discard, undefined, implied);
 372                         break;
 373                 default:
 374                         *undefined = 1;
 375                         *discard = 1;
 376                 }
 377                 break;
 378         case EXPR_CAST:
 379         case EXPR_FORCE_CAST:
 380         case EXPR_IMPLIED_CAST:
 381         {
 382                 struct symbol *type = get_base_type(expr->cast_type);
 383
 384                 ret = _get_value(expr->cast_expression, discard, undefined, implied);
 385                 switch (type->bit_size) {
 386                 case 8:
 387                         if (type->ctype.modifiers & MOD_UNSIGNED)
 388                                 ret = (long long)(unsigned char) ret;
 389                         else
 390                                 ret = (long long)(char) ret;
 391                         break;
 392                 case 16:
 393                         if (type->ctype.modifiers & MOD_UNSIGNED)
 394                                 ret = (long long)(unsigned short) ret;
 395                         else
 396                                 ret = (long long)(short) ret;
 397                         break;
 398                 case 32:
 399                         if (type->ctype.modifiers & MOD_UNSIGNED)
 400                                 ret = (long long)(unsigned int) ret;
 401                         else
 402                                 ret = (long long)(int) ret;
 403                         break;
 404                 }
 405                 return ret;
 406         }
 407         case EXPR_BINOP: {
 408                 long long left;
 409                 long long right;
 410
 411                 left = _get_value(expr->left, discard, undefined, implied);
 412                 right = _get_value(expr->right, discard, undefined, implied);
 413                 if (expr->op == '*') {
 414                         ret =  left * right;
 415                 } else if (expr->op == '/') {
 416                         ret = left / right;
 417                 } else if (expr->op == '+') {
 418                         ret = left + right;
 419                 } else if (expr->op == '-') {
 420                         ret = left - right;
 421                 } else if (expr->op == '|') {
 422                         ret = left | right;
 423                 } else if (expr->op == '&') {
 424                         ret = left & right;
 425                 } else if (expr->op == SPECIAL_RIGHTSHIFT) {
 426                         ret = left >> right;
 427                 } else if (expr->op == SPECIAL_LEFTSHIFT) {
 428                         ret = left << right;
 429                 } else if (expr->op == '^') {
 430                         ret = left ^ right;
 431                 } else {
 432                         *undefined = 1;
 433                         *discard = 1;
 434                 }
 435                 break;
 436         }
 437         case EXPR_PTRSIZEOF:
 438         case EXPR_SIZEOF:
 439                 ret = get_expression_value(expr);
 440                 break;
 441         default:
 442                 switch (implied) {
 443                 case IMPLIED:
 444                         if (!get_implied_single_val(expr, &ret)) {
 445                                 *undefined = 1;
 446                                 *discard = 1;
 447                         }
 448                         break;
 449                 case FUZZYMAX:
 450                         if (!get_implied_single_fuzzy_max(expr, &ret)) {
 451                                 *undefined = 1;
 452                                 *discard = 1;
 453                         }
 454                         break;
 455                 case FUZZYMIN:
 456                         if (!get_implied_single_fuzzy_min(expr, &ret)) {
 457                                 *undefined = 1;
 458                                 *discard = 1;
 459                         }
 460                         break;
 461                 default:
 462                         *undefined = 1;
 463                         *discard = 1;
 464                 }
 465         }
 466         if (*discard) {
 467                 *undefined = 1;
 468                 return BOGUS;
 469         }
 470         return ret;
 471 }
 472
 473 /* returns 1 if it can get a value literal or else returns 0 */
 474 int get_value(struct expression *expr, long long *val)
 475 {
 476         int undefined = 0;
 477
 478         *val = _get_value(expr, NULL, &undefined, NOTIMPLIED);
 479         if (undefined)
 480                 return 0;
 481         return 1;
 482 }
 483
 484 int get_implied_value(struct expression *expr, long long *val)
 485 {
 486         int undefined = 0;
 487
 488         *val =  _get_value(expr, NULL, &undefined, IMPLIED);
 489         return !undefined;
 490 }
 491
 492 int get_fuzzy_max(struct expression *expr, long long *val)
 493 {
 494         int undefined = 0;
 495
 496         *val =  _get_value(expr, NULL, &undefined, FUZZYMAX);
 497         return !undefined;
 498 }
 499
 500 int get_fuzzy_min(struct expression *expr, long long *val)
 501 {
 502         int undefined = 0;
 503
 504         *val =  _get_value(expr, NULL, &undefined, FUZZYMIN);
 505         return !undefined;
 506 }
 507
 508 int is_zero(struct expression *expr)
 509 {
 510         long long val;
 511
 512         if (get_value(expr, &val) && val == 0)
 513                 return 1;
 514         return 0;
 515 }
 516
 517 int is_array(struct expression *expr)
 518 {
 519         expr = strip_expr(expr);
 520         if (expr->type != EXPR_PREOP || expr->op != '*')
 521                 return 0;
 522         expr = expr->unop;
 523         if (expr->op != '+')
 524                 return 0;
 525         return 1;
 526 }
 527
 528 struct expression *get_array_name(struct expression *expr)
 529 {
 530         if (!is_array(expr))
 531                 return NULL;
 532         return strip_expr(expr->unop->left);
 533 }
 534
 535 struct expression *get_array_offset(struct expression *expr)
 536 {
 537         if (!is_array(expr))
 538                 return NULL;
 539         return expr->unop->right;
 540 }
 541
 542 const char *show_state(struct smatch_state *state)
 543 {
 544         if (!state)
 545                 return NULL;
 546         return state->name;
 547 }
 548
 549 struct statement *get_block_thing(struct expression *expr)
 550 {
 551         /* What are those things called? if (({....; ret;})) { ...*/
 552
 553         if (expr->type != EXPR_PREOP)
 554                 return NULL;
 555         if (expr->op != '(')
 556                 return NULL;
 557         if (expr->unop->type != EXPR_STATEMENT)
 558                 return NULL;
 559         if (expr->unop->statement->type != STMT_COMPOUND)
 560                 return NULL;
 561         return expr->unop->statement;
 562 }
 563
 564 struct expression *strip_parens(struct expression *expr)
 565 {
 566         if (!expr)
 567                 return NULL;
 568
 569         if (expr->type == EXPR_PREOP) {
 570                 if (expr->op == '(' && expr->unop->type == EXPR_STATEMENT &&
 571                         expr->unop->statement->type == STMT_COMPOUND)
 572                         return expr;
 573                 if (expr->op == '(')
 574                         return strip_parens(expr->unop);
 575         }
 576         return expr;
 577 }
 578
 579 struct expression *strip_expr(struct expression *expr)
 580 {
 581         if (!expr)
 582                 return NULL;
 583
 584         switch (expr->type) {
 585         case EXPR_FORCE_CAST:
 586         case EXPR_CAST:
 587                 return strip_expr(expr->cast_expression);
 588         case EXPR_PREOP:
 589                 if (expr->op == '(' && expr->unop->type == EXPR_STATEMENT &&
 590                         expr->unop->statement->type == STMT_COMPOUND)
 591                         return expr;
 592                 if (expr->op == '(')
 593                         return strip_expr(expr->unop);
 594         }
 595         return expr;
 596 }
 597
 598 static void delete_state_tracker(struct tracker *t)
 599 {
 600         delete_state(t->owner, t->name, t->sym);
 601         __free_tracker(t);
 602 }
 603
 604 void scoped_state(int my_id, const char *name, struct symbol *sym)
 605 {
 606         struct tracker *t;
 607
 608         t = alloc_tracker(my_id, name, sym);
 609         add_scope_hook((scope_hook *)&delete_state_tracker, t);
 610 }
 611
 612 int is_error_return(struct expression *expr)
 613 {
 614         struct symbol *cur_func = cur_func_sym;
 615         long long val;
 616
 617         if (!expr)
 618                 return 0;
 619         if (cur_func->type != SYM_NODE)
 620                 return 0;
 621         cur_func = get_base_type(cur_func);
 622         if (cur_func->type != SYM_FN)
 623                 return 0;
 624         cur_func = get_base_type(cur_func);
 625         if (cur_func == &void_ctype)
 626                 return 0;
 627         if (!get_value(expr, &val))
 628                 return 0;
 629         if (val < 0)
 630                 return 1;
 631         if (cur_func->type == SYM_PTR && val == 0)
 632                 return 1;
 633         return 0;
 634 }
 635
 636 int getting_address(void)
 637 {
 638         struct expression *tmp;
 639         int i = 0;
 640         int dot_ops = 0;
 641
 642         FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
 643                 if (!i++)
 644                         continue;
 645                 if (tmp->type == EXPR_PREOP && tmp->op == '(')
 646                         continue;
 647                 if (tmp->op == '.' && !dot_ops++)
 648                         continue;
 649                 if (tmp->op == '&')
 650                         return 1;
 651                 return 0;
 652         } END_FOR_EACH_PTR_REVERSE(tmp);
 653         return 0;
 654 }
 655