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