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