smatch_expressions.c

   1 #include "smatch.h"
   2 #include "smatch_extra.h"
   3
   4 DECLARE_ALLOCATOR(sname);
   5 __ALLOCATOR(struct expression, "temporary expr", tmp_expression);
   6
   7 static struct position get_cur_pos(void)
   8 {
   9         static struct position pos;
  10         static struct position none;
  11         struct expression *expr;
  12         struct statement *stmt;
  13
  14         expr = last_ptr_list((struct ptr_list *)big_expression_stack);
  15         stmt = last_ptr_list((struct ptr_list *)big_statement_stack);
  16         if (expr)
  17                 pos = expr->pos;
  18         else if (stmt)
  19                 pos = stmt->pos;
  20         else
  21                 pos = none;
  22         return pos;
  23 }
  24
  25 struct expression *alloc_tmp_expression(struct position pos, int type)
  26 {
  27         struct expression *expr;
  28
  29         expr = __alloc_tmp_expression(0);
  30         expr->smatch_flags |= Tmp;
  31         expr->type = type;
  32         expr->pos = pos;
  33         return expr;
  34 }
  35
  36 void free_tmp_expressions(void)
  37 {
  38         clear_tmp_expression_alloc();
  39 }
  40
  41 struct expression *zero_expr(void)
  42 {
  43         struct expression *zero;
  44
  45         zero = alloc_tmp_expression(get_cur_pos(), EXPR_VALUE);
  46         zero->value = 0;
  47         zero->ctype = &int_ctype;
  48         return zero;
  49 }
  50
  51 struct expression *sval_to_expr(sval_t sval)
  52 {
  53         struct expression *expr;
  54
  55         expr = alloc_tmp_expression(get_cur_pos(), EXPR_VALUE);
  56         expr->value = sval.value;
  57         expr->ctype = sval.type;
  58         return expr;
  59 }
  60
  61 struct expression *value_expr(long long val)
  62 {
  63         struct expression *expr;
  64
  65         if (!val)
  66                 return zero_expr();
  67
  68         expr = alloc_tmp_expression(get_cur_pos(), EXPR_VALUE);
  69         expr->value = val;
  70         expr->ctype = &llong_ctype;
  71         return expr;
  72 }
  73
  74 static struct expression *symbol_expression_helper(struct symbol *sym, bool perm)
  75 {
  76         struct expression *expr;
  77
  78         if (perm)
  79                 expr = alloc_expression(sym->pos, EXPR_SYMBOL);
  80         else
  81                 expr = alloc_tmp_expression(sym->pos, EXPR_SYMBOL);
  82         expr->symbol = sym;
  83         expr->symbol_name = sym->ident;
  84         return expr;
  85 }
  86
  87 struct expression *symbol_expression(struct symbol *sym)
  88 {
  89         return symbol_expression_helper(sym, false);
  90 }
  91
  92 struct expression *cast_expression(struct expression *expr, struct symbol *type)
  93 {
  94         struct expression *cast;
  95
  96         cast = alloc_tmp_expression(expr->pos, EXPR_CAST);
  97         cast->cast_type = type;
  98         cast->cast_expression = expr;
  99         return cast;
 100 }
 101
 102 struct expression *member_expression(struct expression *deref, int op, struct ident *member)
 103 {
 104         struct expression *expr;
 105
 106         expr = alloc_tmp_expression(deref->pos, EXPR_DEREF);
 107         expr->op = op;
 108         expr->deref = deref;
 109         expr->member = member;
 110         expr->member_offset = -1;
 111         return expr;
 112 }
 113
 114 struct expression *preop_expression(struct expression *expr, int op)
 115 {
 116         struct expression *preop;
 117
 118         preop = alloc_tmp_expression(expr->pos, EXPR_PREOP);
 119         preop->unop = expr;
 120         preop->op = op;
 121         return preop;
 122 }
 123
 124 struct expression *deref_expression(struct expression *expr)
 125 {
 126         /* The *&foo is just foo */
 127         if (expr->type == EXPR_PREOP && expr->op == '&')
 128                 return strip_expr(expr->unop);
 129         if (expr->type == EXPR_BINOP)
 130                 expr = preop_expression(expr, '(');
 131         return preop_expression(expr, '*');
 132 }
 133
 134 struct expression *deref_expression_no_parens(struct expression *expr)
 135 {
 136         return preop_expression(expr, '*');
 137 }
 138
 139 struct expression *assign_expression(struct expression *left, int op, struct expression *right)
 140 {
 141         struct expression *expr;
 142
 143         if (!right)
 144                 return NULL;
 145
 146         /* FIXME: make this a tmp expression. */
 147         expr = alloc_expression(right->pos, EXPR_ASSIGNMENT);
 148         expr->op = op;
 149         expr->left = left;
 150         expr->right = right;
 151         return expr;
 152 }
 153
 154 struct expression *assign_expression_perm(struct expression *left, int op, struct expression *right)
 155 {
 156         struct expression *expr;
 157
 158         if (!right)
 159                 return NULL;
 160
 161         expr = alloc_expression(right->pos, EXPR_ASSIGNMENT);
 162         expr->op = op;
 163         expr->left = left;
 164         expr->right = right;
 165         return expr;
 166 }
 167
 168 struct expression *create_fake_assign(const char *name, struct symbol *type, struct expression *right)
 169 {
 170         struct expression *left, *assign;
 171
 172         if (!right)
 173                 return NULL;
 174
 175         if (!type) {
 176                 type = get_type(right);
 177                 if (!type)
 178                         return NULL;
 179         }
 180
 181         left = fake_variable_perm(type, name);
 182
 183         assign = assign_expression_perm(left, '=', right);
 184
 185         assign->smatch_flags |= Fake;
 186
 187         assign->parent = right->parent;
 188         expr_set_parent_expr(right, assign);
 189
 190         __fake_state_cnt++;
 191
 192         return assign;
 193 }
 194
 195 struct expression *binop_expression(struct expression *left, int op, struct expression *right)
 196 {
 197         struct expression *expr;
 198
 199         expr = alloc_tmp_expression(right->pos, EXPR_BINOP);
 200         expr->op = op;
 201         expr->left = left;
 202         expr->right = right;
 203         return expr;
 204 }
 205
 206 struct expression *array_element_expression(struct expression *array, struct expression *offset)
 207 {
 208         struct expression *expr;
 209
 210         expr = binop_expression(array, '+', offset);
 211         return deref_expression_no_parens(expr);
 212 }
 213
 214 struct expression *compare_expression(struct expression *left, int op, struct expression *right)
 215 {
 216         struct expression *expr;
 217
 218         if (!left || !right)
 219                 return NULL;
 220
 221         expr = alloc_tmp_expression(get_cur_pos(), EXPR_COMPARE);
 222         expr->op = op;
 223         expr->left = left;
 224         expr->right = right;
 225         return expr;
 226 }
 227
 228 struct expression *alloc_expression_stmt_perm(struct statement *last_stmt)
 229 {
 230         struct expression *expr;
 231
 232         if (!last_stmt)
 233                 return NULL;
 234
 235         expr = alloc_tmp_expression(last_stmt->pos, EXPR_STATEMENT);
 236         expr->statement = last_stmt;
 237
 238         return expr;
 239 }
 240
 241 struct expression *gen_string_expression(char *str)
 242 {
 243         struct expression *ret;
 244         struct string *string;
 245         int len;
 246
 247         len = strlen(str) + 1;
 248         string = (void *)__alloc_sname(4 + len);
 249         string->length = len;
 250         string->immutable = 0;
 251         memcpy(string->data, str, len);
 252
 253         ret = alloc_tmp_expression(get_cur_pos(), EXPR_STRING);
 254         ret->wide = 0;
 255         ret->string = string;
 256
 257         return ret;
 258 }
 259
 260 struct expression *call_expression(struct expression *fn, struct expression_list *args)
 261 {
 262         struct expression *expr;
 263
 264         expr = alloc_tmp_expression(fn->pos, EXPR_CALL);
 265         expr->fn = fn;
 266         expr->args = args;
 267
 268         return expr;
 269 }
 270
 271 static struct expression *get_expression_from_base_and_str(struct expression *base, const char *addition)
 272 {
 273         struct expression *ret = NULL;
 274         struct token *token, *prev, *end;
 275         char *alloc;
 276
 277         if (addition[0] == '\0')
 278                 return base;
 279
 280         alloc = alloc_string_newline(addition);
 281
 282         token = tokenize_buffer(alloc, strlen(alloc), &end);
 283         if (!token)
 284                 goto free;
 285         if (token_type(token) != TOKEN_STREAMBEGIN)
 286                 goto free;
 287         token = token->next;
 288
 289         ret = base;
 290         while (token_type(token) == TOKEN_SPECIAL &&
 291                (token->special == SPECIAL_DEREFERENCE || token->special == '.')) {
 292                 prev = token;
 293                 token = token->next;
 294                 if (token_type(token) != TOKEN_IDENT)
 295                         goto free;
 296                 switch (prev->special) {
 297                 case SPECIAL_DEREFERENCE:
 298                         ret = deref_expression(ret);
 299                         ret = member_expression(ret, '*', token->ident);
 300                         break;
 301                 case '.':
 302                         ret = member_expression(ret, '.', token->ident);
 303                         break;
 304                 default:
 305                         goto free;
 306                 }
 307                 token = token->next;
 308         }
 309
 310         if (token_type(token) != TOKEN_STREAMEND)
 311                 goto free;
 312
 313 free:
 314         free_string(alloc);
 315
 316         return ret;
 317 }
 318
 319 static struct expression *gen_expression_from_name_sym_helper(const char *name, struct symbol *sym)
 320 {
 321         struct expression *ret;
 322         int skip = 0;
 323
 324         if (!sym)
 325                 return NULL;
 326
 327         if (name[0] == '&' ||
 328             name[0] == '*' ||
 329             name[0] == '(') {
 330                 ret = gen_expression_from_name_sym_helper(name + 1, sym);
 331                 return preop_expression(ret, name[0]);
 332         }
 333         while (name[skip] != '\0' && name[skip] != '.' && name[skip] != '-')
 334                 skip++;
 335
 336         return get_expression_from_base_and_str(symbol_expression(sym), name + skip);
 337 }
 338
 339 struct expression *gen_expression_from_name_sym(const char *name, struct symbol *sym)
 340 {
 341         struct expression *ret;
 342
 343         ret = gen_expression_from_name_sym_helper(name, sym);
 344         if (ret) {
 345                 char *new = expr_to_str(ret);
 346
 347                 /*
 348                  * FIXME: this sometimes changes "foo->bar.a.b->c" into
 349                  * "foo->bar.a.b.c".  I don't know why...  :(
 350                  *
 351                  */
 352                 if (!new || strcmp(name, new) != 0)
 353                         return NULL;
 354         }
 355         return ret;
 356 }
 357
 358 struct expression *gen_expression_from_key(struct expression *arg, const char *key)
 359 {
 360         struct expression *ret;
 361         struct token *token, *end;
 362         const char *p = key;
 363         char buf[4095];
 364         char *alloc;
 365         int cnt = 0;
 366         size_t len;
 367         bool star;
 368
 369         if (strcmp(key, "$") == 0)
 370                 return arg;
 371
 372         if (strcmp(key, "*$") == 0) {
 373                 if (arg->type == EXPR_PREOP &&
 374                     arg->op == '&')
 375                         return strip_expr(arg->unop);
 376                 return deref_expression(arg);
 377         }
 378
 379         /* The idea is that we can parse either $0->foo or $->foo */
 380         if (key[0] != '$')
 381                 return NULL;
 382         p++;
 383         while (*p >= '0' && *p <= '9')
 384                 p++;
 385         len = snprintf(buf, sizeof(buf), "%s\n", p);
 386         alloc = alloc_string(buf);
 387
 388         token = tokenize_buffer(alloc, len, &end);
 389         if (!token)
 390                 return NULL;
 391         if (token_type(token) != TOKEN_STREAMBEGIN)
 392                 return NULL;
 393         token = token->next;
 394
 395         ret = arg;
 396         while (token_type(token) == TOKEN_SPECIAL &&
 397                (token->special == SPECIAL_DEREFERENCE || token->special == '.')) {
 398                 if (token->special == SPECIAL_DEREFERENCE)
 399                         star = true;
 400                 else
 401                         star = false;
 402
 403                 if (cnt++ == 0 && ret->type == EXPR_PREOP && ret->op == '&') {
 404                         ret = strip_expr(ret->unop);
 405                         star = false;
 406                 }
 407
 408                 token = token->next;
 409                 if (token_type(token) != TOKEN_IDENT)
 410                         return NULL;
 411
 412                 if (star)
 413                         ret = deref_expression(ret);
 414                 ret = member_expression(ret, star ? '*' : '.', token->ident);
 415                 token = token->next;
 416         }
 417
 418         if (token_type(token) != TOKEN_STREAMEND)
 419                 return NULL;
 420
 421         return ret;
 422 }
 423
 424 struct expression *gen_expr_from_param_key(struct expression *expr, int param, const char *key)
 425 {
 426         struct expression *call, *arg;
 427
 428         if (!expr)
 429                 return NULL;
 430
 431         call = expr;
 432         while (call->type == EXPR_ASSIGNMENT)
 433                 call = strip_expr(call->right);
 434         if (call->type != EXPR_CALL)
 435                 return NULL;
 436
 437         if (param == -1) {
 438                 if (expr->type != EXPR_ASSIGNMENT)
 439                         return NULL;
 440                 arg = expr->left;
 441         } else {
 442                 arg = get_argument_from_call_expr(call->args, param);
 443                 if (!arg)
 444                         return NULL;
 445         }
 446
 447         return gen_expression_from_key(arg, key);
 448 }
 449
 450 bool is_fake_var(struct expression *expr)
 451 {
 452         if (expr && (expr->smatch_flags & Fake))
 453                 return true;
 454         return false;
 455 }
 456
 457 bool is_fake_var_assign(struct expression *expr)
 458 {
 459         struct expression *left;
 460         struct symbol *sym;
 461
 462         if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=')
 463                 return false;
 464         left = expr->left;
 465         if (left->type != EXPR_SYMBOL)
 466                 return false;
 467         if (!is_fake_var(left))
 468                 return false;
 469
 470         sym = left->symbol;
 471         if (strncmp(sym->ident->name, "__fake_", 7) != 0)
 472                 return false;
 473         return true;
 474 }
 475
 476 static struct expression *fake_variable_helper(struct symbol *type, const char *name, bool perm)
 477 {
 478         struct symbol *sym, *node;
 479         struct expression *ret;
 480         struct ident *ident;
 481
 482         if (!type)
 483                 type = &llong_ctype;
 484
 485         ident = alloc_ident(name, strlen(name));
 486
 487         sym = alloc_symbol(get_cur_pos(), type->type);
 488         sym->ident = ident;
 489         sym->ctype.base_type = type;
 490         sym->ctype.modifiers |= MOD_AUTO;
 491
 492         node = alloc_symbol(get_cur_pos(), SYM_NODE);
 493         node->ident = ident;
 494         node->ctype.base_type = type;
 495         node->ctype.modifiers |= MOD_AUTO;
 496
 497         if (perm)
 498                 ret = symbol_expression_helper(node, true);
 499         else
 500                 ret = symbol_expression(node);
 501
 502         ret->smatch_flags |= Fake;
 503
 504         return ret;
 505 }
 506
 507 struct expression *fake_variable(struct symbol *type, const char *name)
 508 {
 509         return fake_variable_helper(type, name, false);
 510 }
 511
 512 struct expression *fake_variable_perm(struct symbol *type, const char *name)
 513 {
 514         return fake_variable_helper(type, name, true);
 515 }
 516
 517 void expr_set_parent_expr(struct expression *expr, struct expression *parent)
 518 {
 519         struct expression *prev;
 520
 521         if (!expr || !parent)
 522                 return;
 523
 524         prev = expr_get_parent_expr(expr);
 525         if (prev == parent)
 526                 return;
 527
 528         if (parent && parent->smatch_flags & Tmp)
 529                 return;
 530
 531         expr->parent = (unsigned long)parent | 0x1UL;
 532 }
 533
 534 void expr_set_parent_stmt(struct expression *expr, struct statement *parent)
 535 {
 536         if (!expr)
 537                 return;
 538         expr->parent = (unsigned long)parent;
 539 }
 540
 541 struct expression *expr_get_parent_expr(struct expression *expr)
 542 {
 543         struct expression *parent;
 544
 545         if (!expr)
 546                 return NULL;
 547         if (!(expr->parent & 0x1UL))
 548                 return NULL;
 549
 550         parent = (struct expression *)(expr->parent & ~0x1UL);
 551         if (parent && (parent->smatch_flags & Fake))
 552                 return expr_get_parent_expr(parent);
 553         return parent;
 554 }
 555
 556 struct expression *expr_get_fake_parent_expr(struct expression *expr)
 557 {
 558         struct expression *parent;
 559
 560         if (!expr)
 561                 return NULL;
 562         if (!(expr->parent & 0x1UL))
 563                 return NULL;
 564
 565         parent = (struct expression *)(expr->parent & ~0x1UL);
 566         if (parent && (parent->smatch_flags & Fake))
 567                 return parent;
 568         return NULL;
 569 }
 570
 571 struct statement *expr_get_parent_stmt(struct expression *expr)
 572 {
 573         struct expression *parent;
 574
 575         if (!expr)
 576                 return NULL;
 577         if (expr->parent & 0x1UL) {
 578                 parent = (struct expression *)(expr->parent & ~0x1UL);
 579                 if (parent->smatch_flags & Fake)
 580                         return expr_get_parent_stmt(parent);
 581                 return NULL;
 582         }
 583         return (struct statement *)expr->parent;
 584 }
 585
 586 struct statement *get_parent_stmt(struct expression *expr)
 587 {
 588         struct expression *tmp;
 589         int count = 10;
 590
 591         if (!expr)
 592                 return NULL;
 593         while (--count > 0 && (tmp = expr_get_parent_expr(expr)))
 594                 expr = tmp;
 595         if (!count)
 596                 return NULL;
 597
 598         return expr_get_parent_stmt(expr);
 599 }