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 #define NOTIMPLIED 0
 307 #define IMPLIED 1
 308 #define FUZZYMAX 2
 309
 310 static long long _get_value(struct expression *expr, int *discard, int *undefined, int implied)
 311 {
 312         int dis = 0;
 313         long long ret = BOGUS;
 314
 315         if (!expr) {
 316                 *undefined = 1;
 317                 return BOGUS;
 318         }
 319         if (!discard)
 320                 discard = &dis;
 321         if (*discard) {
 322                 *undefined = 1;
 323                 return BOGUS;
 324         }
 325
 326         expr = strip_parens(expr);
 327
 328         switch (expr->type){
 329         case EXPR_VALUE:
 330                 ret = expr->value;
 331                 break;
 332         case EXPR_PREOP:
 333                 if (expr->op == '-') {
 334                         ret = - _get_value(expr->unop, discard, undefined, implied);
 335                 } else {
 336                         *undefined = 1;
 337                         *discard = 1;
 338                 }
 339                 break;
 340         case EXPR_CAST:
 341         case EXPR_FORCE_CAST:
 342         case EXPR_IMPLIED_CAST:
 343         {
 344                 struct symbol *type = get_base_type(expr->cast_type);
 345
 346                 ret = _get_value(expr->cast_expression, discard, undefined, implied);
 347                 switch (type->bit_size) {
 348                 case 8:
 349                         if (type->ctype.modifiers & MOD_UNSIGNED)
 350                                 ret = (int)(unsigned char) ret;
 351                         else
 352                                 ret = (int)(char) ret;
 353                         break;
 354                 case 16:
 355                         if (type->ctype.modifiers & MOD_UNSIGNED)
 356                                 ret = (int)(unsigned short) ret;
 357                         else
 358                                 ret = (int)(short) ret;
 359                         break;
 360                 case 32:
 361                         if (type->ctype.modifiers & MOD_UNSIGNED)
 362                                 ret = (int)(unsigned int) ret;
 363                         else
 364                                 ret = (int)(int) ret;
 365                         break;
 366                 }
 367                 return ret;
 368         }
 369         case EXPR_BINOP: {
 370                 int left, right;
 371
 372                 left = _get_value(expr->left, discard, undefined, implied);
 373                 right = _get_value(expr->right, discard, undefined, implied);
 374                 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 == '&') {
 385                         ret = left & right;
 386                 } else if (expr->op == SPECIAL_RIGHTSHIFT) {
 387                         ret = left >> right;
 388                 } else if (expr->op == SPECIAL_LEFTSHIFT) {
 389                         ret = left << right;
 390                 } else {
 391                         *undefined = 1;
 392                         *discard = 1;
 393                 }
 394                 break;
 395         }
 396         case EXPR_PTRSIZEOF:
 397         case EXPR_SIZEOF:
 398                 ret = get_expression_value(expr);
 399                 break;
 400         default:
 401                 if (implied == IMPLIED) {
 402                         if (!get_implied_single_val(expr, &ret)) {
 403                                 *undefined = 1;
 404                                 *discard = 1;
 405                         }
 406                 } else if (implied == FUZZYMAX) {
 407                         if (!get_implied_single_fuzzy_max(expr, &ret)) {
 408                                 *undefined = 1;
 409                                 *discard = 1;
 410                         }
 411                 } else {
 412                         *undefined = 1;
 413                         *discard = 1;
 414                 }
 415         }
 416         if (*discard) {
 417                 *undefined = 1;
 418                 return BOGUS;
 419         }
 420         return ret;
 421 }
 422
 423 /* returns 1 if it can get a value literal or else returns 0 */
 424 int get_value(struct expression *expr, long long *val)
 425 {
 426         int undefined = 0;
 427
 428         *val = _get_value(expr, NULL, &undefined, NOTIMPLIED);
 429         if (undefined)
 430                 return 0;
 431         return 1;
 432 }
 433
 434 int get_implied_value(struct expression *expr, long long *val)
 435 {
 436         int undefined = 0;
 437
 438         *val =  _get_value(expr, NULL, &undefined, IMPLIED);
 439         return !undefined;
 440 }
 441
 442 int get_fuzzy_max(struct expression *expr, long long *val)
 443 {
 444         int undefined = 0;
 445
 446         *val =  _get_value(expr, NULL, &undefined, FUZZYMAX);
 447         return !undefined;
 448 }
 449
 450 int is_zero(struct expression *expr)
 451 {
 452         long long val;
 453
 454         if (get_value(expr, &val) && val == 0)
 455                 return 1;
 456         return 0;
 457 }
 458
 459 int is_array(struct expression *expr)
 460 {
 461         expr = strip_expr(expr);
 462         if (expr->type != EXPR_PREOP || expr->op != '*')
 463                 return 0;
 464         expr = expr->unop;
 465         if (expr->op != '+')
 466                 return 0;
 467         return 1;
 468 }
 469
 470 struct expression *get_array_name(struct expression *expr)
 471 {
 472         if (!is_array(expr))
 473                 return NULL;
 474         return strip_expr(expr->unop->left);
 475 }
 476
 477 struct expression *get_array_offset(struct expression *expr)
 478 {
 479         if (!is_array(expr))
 480                 return NULL;
 481         return expr->unop->right;
 482 }
 483
 484 const char *show_state(struct smatch_state *state)
 485 {
 486         if (!state)
 487                 return NULL;
 488         return state->name;
 489 }
 490
 491 struct statement *get_block_thing(struct expression *expr)
 492 {
 493         /* What are those things called? if (({....; ret;})) { ...*/
 494
 495         if (expr->type != EXPR_PREOP)
 496                 return NULL;
 497         if (expr->op != '(')
 498                 return NULL;
 499         if (expr->unop->type != EXPR_STATEMENT)
 500                 return NULL;
 501         if (expr->unop->statement->type != STMT_COMPOUND)
 502                 return NULL;
 503         return expr->unop->statement;
 504 }
 505
 506 struct expression *strip_parens(struct expression *expr)
 507 {
 508         if (!expr)
 509                 return NULL;
 510
 511         if (expr->type == EXPR_PREOP) {
 512                 if (expr->op == '(' && expr->unop->type == EXPR_STATEMENT &&
 513                         expr->unop->statement->type == STMT_COMPOUND)
 514                         return expr;
 515                 if (expr->op == '(')
 516                         return strip_parens(expr->unop);
 517         }
 518         return expr;
 519 }
 520
 521 struct expression *strip_expr(struct expression *expr)
 522 {
 523         if (!expr)
 524                 return NULL;
 525
 526         switch (expr->type) {
 527         case EXPR_CAST:
 528                 return strip_expr(expr->cast_expression);
 529         case EXPR_PREOP:
 530                 if (expr->op == '(' && expr->unop->type == EXPR_STATEMENT &&
 531                         expr->unop->statement->type == STMT_COMPOUND)
 532                         return expr;
 533                 if (expr->op == '(')
 534                         return strip_expr(expr->unop);
 535         }
 536         return expr;
 537 }
 538
 539 static void delete_state_tracker(struct tracker *t)
 540 {
 541         delete_state(t->owner, t->name, t->sym);
 542         __free_tracker(t);
 543 }
 544
 545 void scoped_state(int my_id, const char *name, struct symbol *sym)
 546 {
 547         struct tracker *t;
 548
 549         t = alloc_tracker(my_id, name, sym);
 550         add_scope_hook((scope_hook *)&delete_state_tracker, t);
 551 }
 552
 553 int is_error_return(struct expression *expr)
 554 {
 555         struct symbol *cur_func = cur_func_sym;
 556         long long val;
 557
 558         if (!expr)
 559                 return 0;
 560         if (cur_func->type != SYM_NODE)
 561                 return 0;
 562         cur_func = get_base_type(cur_func);
 563         if (cur_func->type != SYM_FN)
 564                 return 0;
 565         cur_func = get_base_type(cur_func);
 566         if (cur_func == &void_ctype)
 567                 return 0;
 568         if (!get_value(expr, &val))
 569                 return 0;
 570         if (val < 0)
 571                 return 1;
 572         if (cur_func->type == SYM_PTR && val == 0)
 573                 return 1;
 574         return 0;
 575 }
 576
 577 int getting_address(void)
 578 {
 579         struct expression *tmp;
 580         int i = 0;
 581         int dot_ops = 0;
 582
 583         FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
 584                 if (!i++)
 585                         continue;
 586                 if (tmp->type == EXPR_PREOP && tmp->op == '(')
 587                         continue;
 588                 if (tmp->op == '.' && !dot_ops++)
 589                         continue;
 590                 if (tmp->op == '&')
 591                         return 1;
 592                 return 0;
 593         } END_FOR_EACH_PTR_REVERSE(tmp);
 594         return 0;
 595 }
 596