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