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         if (expr->type == EXPR_BINOP)
 127                 expr = preop_expression(expr, '(');
 128         return preop_expression(expr, '*');
 129 }
 130
 131 struct expression *deref_expression_no_parens(struct expression *expr)
 132 {
 133         return preop_expression(expr, '*');
 134 }
 135
 136 struct expression *assign_expression(struct expression *left, int op, struct expression *right)
 137 {
 138         struct expression *expr;
 139
 140         if (!right)
 141                 return NULL;
 142
 143         /* FIXME: make this a tmp expression. */
 144         expr = alloc_expression(right->pos, EXPR_ASSIGNMENT);
 145         expr->op = op;
 146         expr->left = left;
 147         expr->right = right;
 148         return expr;
 149 }
 150
 151 struct expression *assign_expression_perm(struct expression *left, int op, struct expression *right)
 152 {
 153         struct expression *expr;
 154
 155         if (!right)
 156                 return NULL;
 157
 158         expr = alloc_expression(right->pos, EXPR_ASSIGNMENT);
 159         expr->op = op;
 160         expr->left = left;
 161         expr->right = right;
 162         return expr;
 163 }
 164
 165 struct expression *create_fake_assign(const char *name, struct symbol *type, struct expression *right)
 166 {
 167         struct expression *left, *assign;
 168
 169         if (!right)
 170                 return NULL;
 171
 172         if (!type) {
 173                 type = get_type(right);
 174                 if (!type)
 175                         return NULL;
 176         }
 177
 178         left = fake_variable_perm(type, name);
 179
 180         assign = assign_expression_perm(left, '=', right);
 181
 182         assign->smatch_flags |= Fake;
 183
 184         assign->parent = right->parent;
 185         expr_set_parent_expr(right, assign);
 186
 187         __fake_state_cnt++;
 188
 189         return assign;
 190 }
 191
 192 struct expression *binop_expression(struct expression *left, int op, struct expression *right)
 193 {
 194         struct expression *expr;
 195
 196         expr = alloc_tmp_expression(right->pos, EXPR_BINOP);
 197         expr->op = op;
 198         expr->left = left;
 199         expr->right = right;
 200         return expr;
 201 }
 202
 203 struct expression *array_element_expression(struct expression *array, struct expression *offset)
 204 {
 205         struct expression *expr;
 206
 207         expr = binop_expression(array, '+', offset);
 208         return deref_expression_no_parens(expr);
 209 }
 210
 211 struct expression *compare_expression(struct expression *left, int op, struct expression *right)
 212 {
 213         struct expression *expr;
 214
 215         if (!left || !right)
 216                 return NULL;
 217
 218         expr = alloc_tmp_expression(get_cur_pos(), EXPR_COMPARE);
 219         expr->op = op;
 220         expr->left = left;
 221         expr->right = right;
 222         return expr;
 223 }
 224
 225 struct expression *alloc_expression_stmt_perm(struct statement *last_stmt)
 226 {
 227         struct expression *expr;
 228
 229         if (!last_stmt)
 230                 return NULL;
 231
 232         expr = alloc_tmp_expression(last_stmt->pos, EXPR_STATEMENT);
 233         expr->statement = last_stmt;
 234
 235         return expr;
 236 }
 237
 238 struct expression *gen_string_expression(char *str)
 239 {
 240         struct expression *ret;
 241         struct string *string;
 242         int len;
 243
 244         len = strlen(str) + 1;
 245         string = (void *)__alloc_sname(4 + len);
 246         string->length = len;
 247         string->immutable = 0;
 248         memcpy(string->data, str, len);
 249
 250         ret = alloc_tmp_expression(get_cur_pos(), EXPR_STRING);
 251         ret->wide = 0;
 252         ret->string = string;
 253
 254         return ret;
 255 }
 256
 257 struct expression *call_expression(struct expression *fn, struct expression_list *args)
 258 {
 259         struct expression *expr;
 260
 261         expr = alloc_tmp_expression(fn->pos, EXPR_CALL);
 262         expr->fn = fn;
 263         expr->args = args;
 264
 265         return expr;
 266 }
 267
 268 static struct expression *get_expression_from_base_and_str(struct expression *base, const char *addition)
 269 {
 270         struct expression *ret = NULL;
 271         struct token *token, *prev, *end;
 272         char *alloc;
 273
 274         if (addition[0] == '\0')
 275                 return base;
 276
 277         alloc = alloc_string_newline(addition);
 278
 279         token = tokenize_buffer(alloc, strlen(alloc), &end);
 280         if (!token)
 281                 goto free;
 282         if (token_type(token) != TOKEN_STREAMBEGIN)
 283                 goto free;
 284         token = token->next;
 285
 286         ret = base;
 287         while (token_type(token) == TOKEN_SPECIAL &&
 288                (token->special == SPECIAL_DEREFERENCE || token->special == '.')) {
 289                 prev = token;
 290                 token = token->next;
 291                 if (token_type(token) != TOKEN_IDENT)
 292                         goto free;
 293                 switch (prev->special) {
 294                 case SPECIAL_DEREFERENCE:
 295                         ret = deref_expression(ret);
 296                         ret = member_expression(ret, '*', token->ident);
 297                         break;
 298                 case '.':
 299                         ret = member_expression(ret, '.', token->ident);
 300                         break;
 301                 default:
 302                         goto free;
 303                 }
 304                 token = token->next;
 305         }
 306
 307         if (token_type(token) != TOKEN_STREAMEND)
 308                 goto free;
 309
 310 free:
 311         free_string(alloc);
 312
 313         return ret;
 314 }
 315
 316 static struct expression *gen_expression_from_name_sym_helper(const char *name, struct symbol *sym)
 317 {
 318         struct expression *ret;
 319         int skip = 0;
 320
 321         if (!sym)
 322                 return NULL;
 323
 324         if (name[0] == '&' ||
 325             name[0] == '*' ||
 326             name[0] == '(') {
 327                 ret = gen_expression_from_name_sym_helper(name + 1, sym);
 328                 return preop_expression(ret, name[0]);
 329         }
 330         while (name[skip] != '\0' && name[skip] != '.' && name[skip] != '-')
 331                 skip++;
 332
 333         return get_expression_from_base_and_str(symbol_expression(sym), name + skip);
 334 }
 335
 336 struct expression *gen_expression_from_name_sym(const char *name, struct symbol *sym)
 337 {
 338         struct expression *ret;
 339
 340         ret = gen_expression_from_name_sym_helper(name, sym);
 341         if (ret) {
 342                 char *new = expr_to_str(ret);
 343
 344                 /*
 345                  * FIXME: this sometimes changes "foo->bar.a.b->c" into
 346                  * "foo->bar.a.b.c".  I don't know why...  :(
 347                  *
 348                  */
 349                 if (!new || strcmp(name, new) != 0)
 350                         return NULL;
 351         }
 352         return ret;
 353 }
 354
 355 struct expression *gen_expression_from_key(struct expression *arg, const char *key)
 356 {
 357         struct expression *ret;
 358         struct token *token, *end;
 359         const char *p = key;
 360         char buf[4095];
 361         char *alloc;
 362         int cnt = 0;
 363         size_t len;
 364         bool star;
 365
 366         if (strcmp(key, "*$") == 0) {
 367                 if (arg->type == EXPR_PREOP &&
 368                     arg->op == '&')
 369                         return strip_expr(arg->unop);
 370                 return deref_expression(arg);
 371         }
 372
 373         /* The idea is that we can parse either $0->foo or $->foo */
 374         if (key[0] != '$')
 375                 return NULL;
 376         p++;
 377         while (*p >= '0' && *p <= '9')
 378                 p++;
 379         len = snprintf(buf, sizeof(buf), "%s\n", p);
 380         alloc = alloc_string(buf);
 381
 382         token = tokenize_buffer(alloc, len, &end);
 383         if (!token)
 384                 return NULL;
 385         if (token_type(token) != TOKEN_STREAMBEGIN)
 386                 return NULL;
 387         token = token->next;
 388
 389         ret = arg;
 390         while (token_type(token) == TOKEN_SPECIAL &&
 391                (token->special == SPECIAL_DEREFERENCE || token->special == '.')) {
 392                 if (token->special == SPECIAL_DEREFERENCE)
 393                         star = true;
 394                 else
 395                         star = false;
 396
 397                 if (cnt++ == 0 && ret->type == EXPR_PREOP && ret->op == '&') {
 398                         ret = strip_expr(ret->unop);
 399                         star = false;
 400                 }
 401
 402                 token = token->next;
 403                 if (token_type(token) != TOKEN_IDENT)
 404                         return NULL;
 405
 406                 if (star)
 407                         ret = deref_expression(ret);
 408                 ret = member_expression(ret, star ? '*' : '.', token->ident);
 409                 token = token->next;
 410         }
 411
 412         if (token_type(token) != TOKEN_STREAMEND)
 413                 return NULL;
 414
 415         return ret;
 416 }
 417
 418 struct expression *gen_expr_from_param_key(struct expression *expr, int param, const char *key)
 419 {
 420         struct expression *call, *arg;
 421
 422         if (!expr)
 423                 return NULL;
 424
 425         call = expr;
 426         while (call->type == EXPR_ASSIGNMENT)
 427                 call = strip_expr(call->right);
 428         if (call->type != EXPR_CALL)
 429                 return NULL;
 430
 431         if (param == -1) {
 432                 if (expr->type != EXPR_ASSIGNMENT)
 433                         return NULL;
 434                 arg = expr->left;
 435         } else {
 436                 arg = get_argument_from_call_expr(call->args, param);
 437                 if (!arg)
 438                         return NULL;
 439         }
 440
 441         return gen_expression_from_key(arg, key);
 442 }
 443
 444 bool is_fake_var(struct expression *expr)
 445 {
 446         if (expr && (expr->smatch_flags & Fake))
 447                 return true;
 448         return false;
 449 }
 450
 451 bool is_fake_var_assign(struct expression *expr)
 452 {
 453         struct expression *left;
 454         struct symbol *sym;
 455
 456         if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=')
 457                 return false;
 458         left = expr->left;
 459         if (left->type != EXPR_SYMBOL)
 460                 return false;
 461         if (!is_fake_var(left))
 462                 return false;
 463
 464         sym = left->symbol;
 465         if (strncmp(sym->ident->name, "__fake_", 7) != 0)
 466                 return false;
 467         return true;
 468 }
 469
 470 static struct expression *fake_variable_helper(struct symbol *type, const char *name, bool perm)
 471 {
 472         struct symbol *sym, *node;
 473         struct expression *ret;
 474         struct ident *ident;
 475
 476         if (!type)
 477                 type = &llong_ctype;
 478
 479         ident = alloc_ident(name, strlen(name));
 480
 481         sym = alloc_symbol(get_cur_pos(), type->type);
 482         sym->ident = ident;
 483         sym->ctype.base_type = type;
 484         sym->ctype.modifiers |= MOD_AUTO;
 485
 486         node = alloc_symbol(get_cur_pos(), SYM_NODE);
 487         node->ident = ident;
 488         node->ctype.base_type = type;
 489         node->ctype.modifiers |= MOD_AUTO;
 490
 491         if (perm)
 492                 ret = symbol_expression_helper(node, true);
 493         else
 494                 ret = symbol_expression(node);
 495
 496         ret->smatch_flags |= Fake;
 497
 498         return ret;
 499 }
 500
 501 struct expression *fake_variable(struct symbol *type, const char *name)
 502 {
 503         return fake_variable_helper(type, name, false);
 504 }
 505
 506 struct expression *fake_variable_perm(struct symbol *type, const char *name)
 507 {
 508         return fake_variable_helper(type, name, true);
 509 }
 510
 511 void expr_set_parent_expr(struct expression *expr, struct expression *parent)
 512 {
 513         struct expression *prev;
 514
 515         if (!expr || !parent)
 516                 return;
 517
 518         prev = expr_get_parent_expr(expr);
 519         if (prev == parent)
 520                 return;
 521
 522         if (parent && parent->smatch_flags & Tmp)
 523                 return;
 524
 525         expr->parent = (unsigned long)parent | 0x1UL;
 526 }
 527
 528 void expr_set_parent_stmt(struct expression *expr, struct statement *parent)
 529 {
 530         if (!expr)
 531                 return;
 532         expr->parent = (unsigned long)parent;
 533 }
 534
 535 struct expression *expr_get_parent_expr(struct expression *expr)
 536 {
 537         struct expression *parent;
 538
 539         if (!expr)
 540                 return NULL;
 541         if (!(expr->parent & 0x1UL))
 542                 return NULL;
 543
 544         parent = (struct expression *)(expr->parent & ~0x1UL);
 545         if (parent && (parent->smatch_flags & Fake))
 546                 return expr_get_parent_expr(parent);
 547         return parent;
 548 }
 549
 550 struct expression *expr_get_fake_parent_expr(struct expression *expr)
 551 {
 552         struct expression *parent;
 553
 554         if (!expr)
 555                 return NULL;
 556         if (!(expr->parent & 0x1UL))
 557                 return NULL;
 558
 559         parent = (struct expression *)(expr->parent & ~0x1UL);
 560         if (parent && (parent->smatch_flags & Fake))
 561                 return parent;
 562         return NULL;
 563 }
 564
 565 struct statement *expr_get_parent_stmt(struct expression *expr)
 566 {
 567         struct expression *parent;
 568
 569         if (!expr)
 570                 return NULL;
 571         if (expr->parent & 0x1UL) {
 572                 parent = (struct expression *)(expr->parent & ~0x1UL);
 573                 if (parent->smatch_flags & Fake)
 574                         return expr_get_parent_stmt(parent);
 575                 return NULL;
 576         }
 577         return (struct statement *)expr->parent;
 578 }
 579
 580 struct statement *get_parent_stmt(struct expression *expr)
 581 {
 582         struct expression *tmp;
 583         int count = 10;
 584
 585         if (!expr)
 586                 return NULL;
 587         while (--count > 0 && (tmp = expr_get_parent_expr(expr)))
 588                 expr = tmp;
 589         if (!count)
 590                 return NULL;
 591
 592         return expr_get_parent_stmt(expr);
 593 }