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, expr->string->data, len);
 192                 return;
 193         case EXPR_CALL: {
 194                 struct expression *tmp;
 195                 int i;
 196
 197                 *complicated = 1;
 198                 __get_variable_from_expr(NULL, buf, expr->fn, len,
 199                                          complicated);
 200                 append(buf, "(", len);
 201                 i = 0;
 202                 FOR_EACH_PTR_REVERSE(expr->args, tmp) {
 203                         if (i++)
 204                                 append(buf, ", ", len);
 205                         __get_variable_from_expr(NULL, buf, tmp, len,
 206                                                 complicated);
 207                 } END_FOR_EACH_PTR_REVERSE(tmp);
 208                 append(buf, ")", len);
 209                 return;
 210         }
 211         case EXPR_CAST:
 212                 __get_variable_from_expr(sym_ptr, buf,
 213                                          expr->cast_expression, len,
 214                                          complicated);
 215                 return;
 216         case EXPR_SIZEOF: {
 217                 int size;
 218                 char tmp[25];
 219
 220                 if (expr->cast_type && get_base_type(expr->cast_type)) {
 221                         size = (get_base_type(expr->cast_type))->bit_size;
 222                         snprintf(tmp, 25, "%d", size);
 223                         append(buf, tmp, len);
 224                 }
 225                 return;
 226         }
 227         default:
 228                 *complicated = 1;
 229                 //printf("unknown type = %d\n", expr->type);
 230                 return;
 231         }
 232 }
 233
 234
 235 /*
 236  * This is returns a stylized "c looking" representation of the
 237  * variable name.
 238  *
 239  * It uses the same buffer every time so you have to save the result
 240  * yourself if you want to keep it.
 241  *
 242  */
 243
 244 char *get_variable_from_expr_complex(struct expression *expr, struct symbol **sym_ptr)
 245 {
 246         static char var_name[VAR_LEN];
 247         int complicated = 0;
 248
 249         if (sym_ptr)
 250                 *sym_ptr = NULL;
 251         var_name[0] = '\0';
 252
 253         if (!expr)
 254                 return NULL;
 255         __get_variable_from_expr(sym_ptr, var_name, expr, sizeof(var_name),
 256                                  &complicated);
 257         if (complicated < 2)
 258                 return alloc_string(var_name);
 259         else
 260                 return NULL;
 261 }
 262
 263 /*
 264  * get_variable_from_expr_simple() only returns simple variables.
 265  * If it's a complicated variable like a->foo instead of just 'a'
 266  * then it returns NULL.
 267  */
 268
 269 char *get_variable_from_expr(struct expression *expr,
 270                                     struct symbol **sym_ptr)
 271 {
 272         static char var_name[VAR_LEN];
 273         int complicated = 0;
 274
 275         if (sym_ptr)
 276                 *sym_ptr = NULL;
 277         var_name[0] = '\0';
 278
 279         if (!expr)
 280                 return NULL;
 281         expr = strip_expr(expr);
 282         __get_variable_from_expr(sym_ptr, var_name, expr, sizeof(var_name),
 283                                  &complicated);
 284
 285         if (complicated) {
 286                 if (sym_ptr)
 287                         *sym_ptr = NULL;
 288                 return NULL;
 289         }
 290         return alloc_string(var_name);
 291 }
 292
 293 int sym_name_is(const char *name, struct expression *expr)
 294 {
 295         if (!expr)
 296                 return 0;
 297         if (expr->type != EXPR_SYMBOL)
 298                 return 0;
 299         if (!strcmp(expr->symbol_name->name, name))
 300                 return 1;
 301         return 0;
 302 }
 303
 304 #define NOTIMPLIED 0
 305 #define IMPLIED 1
 306 #define FUZZYMAX 2
 307
 308 static long long _get_value(struct expression *expr, int *discard, int *undefined, int implied)
 309 {
 310         int dis = 0;
 311         long long ret = BOGUS;
 312
 313         if (!expr) {
 314                 *undefined = 1;
 315                 return BOGUS;
 316         }
 317         if (!discard)
 318                 discard = &dis;
 319         if (*discard) {
 320                 *undefined = 1;
 321                 return BOGUS;
 322         }
 323
 324         expr = strip_parens(expr);
 325
 326         switch (expr->type){
 327         case EXPR_VALUE:
 328                 ret = expr->value;
 329                 break;
 330         case EXPR_PREOP:
 331                 if (expr->op == '-') {
 332                         ret = - _get_value(expr->unop, discard, undefined, implied);
 333                 } else {
 334                         *undefined = 1;
 335                         *discard = 1;
 336                 }
 337                 break;
 338         case EXPR_CAST:
 339         case EXPR_FORCE_CAST:
 340         case EXPR_IMPLIED_CAST:
 341         {
 342                 struct symbol *type = get_base_type(expr->cast_type);
 343
 344                 ret = _get_value(expr->cast_expression, discard, undefined, implied);
 345                 switch (type->bit_size) {
 346                 case 8:
 347                         if (type->ctype.modifiers & MOD_UNSIGNED)
 348                                 ret = (int)(unsigned char) ret;
 349                         else
 350                                 ret = (int)(char) ret;
 351                         break;
 352                 case 16:
 353                         if (type->ctype.modifiers & MOD_UNSIGNED)
 354                                 ret = (int)(unsigned short) ret;
 355                         else
 356                                 ret = (int)(short) ret;
 357                         break;
 358                 case 32:
 359                         if (type->ctype.modifiers & MOD_UNSIGNED)
 360                                 ret = (int)(unsigned int) ret;
 361                         else
 362                                 ret = (int)(int) ret;
 363                         break;
 364                 }
 365                 return ret;
 366         }
 367         case EXPR_BINOP: {
 368                 int left, right;
 369
 370                 left = _get_value(expr->left, discard, undefined, implied);
 371                 right = _get_value(expr->right, discard, undefined, implied);
 372                 if (expr->op == '*') {
 373                         ret =  left * right;
 374                 } else if (expr->op == '/') {
 375                         ret = left / right;
 376                 } else if (expr->op == '+') {
 377                         ret = left + right;
 378                 } else if (expr->op == '-') {
 379                         ret = left - right;
 380                 } else if (expr->op == '|') {
 381                         ret = left | right;
 382                 } else if (expr->op == '&') {
 383                         ret = left & right;
 384                 } else if (expr->op == SPECIAL_RIGHTSHIFT) {
 385                         ret = left >> right;
 386                 } else if (expr->op == SPECIAL_LEFTSHIFT) {
 387                         ret = left << right;
 388                 } else {
 389                         *undefined = 1;
 390                         *discard = 1;
 391                 }
 392                 break;
 393         }
 394         case EXPR_PTRSIZEOF:
 395         case EXPR_SIZEOF:
 396                 ret = get_expression_value(expr);
 397                 break;
 398         default:
 399                 if (implied == IMPLIED) {
 400                         if (!get_implied_single_val(expr, &ret)) {
 401                                 *undefined = 1;
 402                                 *discard = 1;
 403                         }
 404                 } else if (implied == FUZZYMAX) {
 405                         if (!get_implied_single_fuzzy_max(expr, &ret)) {
 406                                 *undefined = 1;
 407                                 *discard = 1;
 408                         }
 409                 } else {
 410                         *undefined = 1;
 411                         *discard = 1;
 412                 }
 413         }
 414         if (*discard) {
 415                 *undefined = 1;
 416                 return BOGUS;
 417         }
 418         return ret;
 419 }
 420
 421 /* returns 1 if it can get a value literal or else returns 0 */
 422 int get_value(struct expression *expr, long long *val)
 423 {
 424         int undefined = 0;
 425
 426         *val = _get_value(expr, NULL, &undefined, NOTIMPLIED);
 427         if (undefined)
 428                 return 0;
 429         return 1;
 430 }
 431
 432 int get_implied_value(struct expression *expr, long long *val)
 433 {
 434         int undefined = 0;
 435
 436         *val =  _get_value(expr, NULL, &undefined, IMPLIED);
 437         return !undefined;
 438 }
 439
 440 int get_fuzzy_max(struct expression *expr, long long *val)
 441 {
 442         int undefined = 0;
 443
 444         *val =  _get_value(expr, NULL, &undefined, FUZZYMAX);
 445         return !undefined;
 446 }
 447
 448 int is_zero(struct expression *expr)
 449 {
 450         long long val;
 451
 452         if (get_value(expr, &val) && val == 0)
 453                 return 1;
 454         return 0;
 455 }
 456
 457 int is_array(struct expression *expr)
 458 {
 459         expr = strip_expr(expr);
 460         if (expr->type != EXPR_PREOP || expr->op != '*')
 461                 return 0;
 462         expr = expr->unop;
 463         if (expr->op != '+')
 464                 return 0;
 465         return 1;
 466 }
 467
 468 struct expression *get_array_name(struct expression *expr)
 469 {
 470         if (!is_array(expr))
 471                 return NULL;
 472         return strip_expr(expr->unop->left);
 473 }
 474
 475 struct expression *get_array_offset(struct expression *expr)
 476 {
 477         if (!is_array(expr))
 478                 return NULL;
 479         return expr->unop->right;
 480 }
 481
 482 const char *show_state(struct smatch_state *state)
 483 {
 484         if (!state)
 485                 return NULL;
 486         return state->name;
 487 }
 488
 489 struct statement *get_block_thing(struct expression *expr)
 490 {
 491         /* What are those things called? if (({....; ret;})) { ...*/
 492
 493         if (expr->type != EXPR_PREOP)
 494                 return NULL;
 495         if (expr->op != '(')
 496                 return NULL;
 497         if (expr->unop->type != EXPR_STATEMENT)
 498                 return NULL;
 499         if (expr->unop->statement->type != STMT_COMPOUND)
 500                 return NULL;
 501         return expr->unop->statement;
 502 }
 503
 504 struct expression *strip_parens(struct expression *expr)
 505 {
 506         if (!expr)
 507                 return NULL;
 508
 509         if (expr->type == EXPR_PREOP) {
 510                 if (expr->op == '(' && expr->unop->type == EXPR_STATEMENT &&
 511                         expr->unop->statement->type == STMT_COMPOUND)
 512                         return expr;
 513                 if (expr->op == '(')
 514                         return strip_parens(expr->unop);
 515         }
 516         return expr;
 517 }
 518
 519 struct expression *strip_expr(struct expression *expr)
 520 {
 521         if (!expr)
 522                 return NULL;
 523
 524         switch (expr->type) {
 525         case EXPR_CAST:
 526                 return strip_expr(expr->cast_expression);
 527         case EXPR_PREOP:
 528                 if (expr->op == '(' && expr->unop->type == EXPR_STATEMENT &&
 529                         expr->unop->statement->type == STMT_COMPOUND)
 530                         return expr;
 531                 if (expr->op == '(')
 532                         return strip_expr(expr->unop);
 533         }
 534         return expr;
 535 }
 536
 537 static void delete_state_tracker(struct tracker *t)
 538 {
 539         delete_state(t->owner, t->name, t->sym);
 540         __free_tracker(t);
 541 }
 542
 543 void scoped_state(int my_id, const char *name, struct symbol *sym)
 544 {
 545         struct tracker *t;
 546
 547         t = alloc_tracker(my_id, name, sym);
 548         add_scope_hook((scope_hook *)&delete_state_tracker, t);
 549 }
 550
 551 int is_error_return(struct expression *expr)
 552 {
 553         struct symbol *cur_func = cur_func_sym;
 554         long long val;
 555
 556         if (!expr)
 557                 return 0;
 558         if (cur_func->type != SYM_NODE)
 559                 return 0;
 560         cur_func = get_base_type(cur_func);
 561         if (cur_func->type != SYM_FN)
 562                 return 0;
 563         cur_func = get_base_type(cur_func);
 564         if (cur_func == &void_ctype)
 565                 return 0;
 566         if (!get_value(expr, &val))
 567                 return 0;
 568         if (val < 0)
 569                 return 1;
 570         if (cur_func->type == SYM_PTR && val == 0)
 571                 return 1;
 572         return 0;
 573 }
 574
 575 int getting_address(void)
 576 {
 577         struct expression *tmp;
 578         int i = 0;
 579         int dot_ops = 0;
 580
 581         FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
 582                 if (!i++)
 583                         continue;
 584                 if (tmp->type == EXPR_PREOP && tmp->op == '(')
 585                         continue;
 586                 if (tmp->op == '.' && !dot_ops++)
 587                         continue;
 588                 if (tmp->op == '&')
 589                         return 1;
 590                 return 0;
 591         } END_FOR_EACH_PTR_REVERSE(tmp);
 592         return 0;
 593 }
 594