smatch_helper.c

   1 /*
   2  * Copyright (C) 2006 Dan Carpenter.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 /*
  19  * Miscellaneous helper functions.
  20  */
  21
  22 #include <stdlib.h>
  23 #include <stdio.h>
  24 #include "allocate.h"
  25 #include "smatch.h"
  26 #include "smatch_extra.h"
  27 #include "smatch_slist.h"
  28
  29 #define VAR_LEN 512
  30
  31 static struct expression *strip_expr_helper(struct expression *expr, bool set_parent, bool cast, int *nest);
  32
  33 char *alloc_string(const char *str)
  34 {
  35         char *tmp;
  36
  37         if (!str)
  38                 return NULL;
  39         tmp = malloc(strlen(str) + 1);
  40         strcpy(tmp, str);
  41         return tmp;
  42 }
  43
  44 char *alloc_string_newline(const char *str)
  45 {
  46         char *tmp;
  47         int len;
  48
  49         if (!str)
  50                 return NULL;
  51         len = strlen(str);
  52         tmp = malloc(len + 2);
  53         snprintf(tmp, len + 2, "%s\n", str);
  54         return tmp;
  55 }
  56
  57 void free_string(char *str)
  58 {
  59         free(str);
  60 }
  61
  62 void remove_parens(char *str)
  63 {
  64         char *src, *dst;
  65
  66         dst = src = str;
  67         while (*src != '\0') {
  68                 if (*src == '(' || *src == ')') {
  69                         src++;
  70                         continue;
  71                 }
  72                 *dst++ = *src++;
  73         }
  74         *dst = *src;
  75 }
  76
  77 struct smatch_state *alloc_state_num(int num)
  78 {
  79         struct smatch_state *state;
  80         static char buff[256];
  81
  82         state = __alloc_smatch_state(0);
  83         snprintf(buff, 255, "%d", num);
  84         buff[255] = '\0';
  85         state->name = alloc_string(buff);
  86         state->data = INT_PTR(num);
  87         return state;
  88 }
  89
  90 struct smatch_state *alloc_state_str(const char *name)
  91 {
  92         struct smatch_state *state;
  93
  94         state = __alloc_smatch_state(0);
  95         state->name = alloc_string(name);
  96         return state;
  97 }
  98
  99 struct smatch_state *merge_str_state(struct smatch_state *s1, struct smatch_state *s2)
 100 {
 101         if (!s1->name || !s2->name)
 102                 return &merged;
 103         if (strcmp(s1->name, s2->name) == 0)
 104                 return s1;
 105         return &merged;
 106 }
 107
 108 struct smatch_state *alloc_state_expr(struct expression *expr)
 109 {
 110         struct smatch_state *state;
 111         char *name;
 112
 113         expr = strip_expr(expr);
 114         name = expr_to_str(expr);
 115         if (!name)
 116                 return NULL;
 117
 118         state = __alloc_smatch_state(0);
 119         state->name = alloc_sname(name);
 120         free_string(name);
 121         state->data = expr;
 122         return state;
 123 }
 124
 125 static int FORMAT_ATTR(4) append(char *dest, int off, int len, const char *fmt, ...)
 126 {
 127         int n;
 128         va_list args;
 129
 130         if (len <= 0 || off < 0 || off >= len - 1)
 131                 return 0;
 132
 133         va_start(args, fmt);
 134         n = vsnprintf(dest + off, len - off, fmt, args);
 135         va_end(args);
 136
 137         if (n > len - off - 1)
 138                 return len - off - 1;
 139         return n;
 140 }
 141
 142 struct expression *get_assigned_call(struct expression *expr)
 143 {
 144         while (expr && expr->type == EXPR_ASSIGNMENT)
 145                 expr = strip_expr(expr->right);
 146         if (!expr || expr->type != EXPR_CALL)
 147                 return NULL;
 148         return expr;
 149 }
 150
 151 /*
 152  * If you have "foo(a, b, 1);" then use
 153  * get_argument_from_call_expr(expr, 0) to return the expression for
 154  * a.  Yes, it does start counting from 0.
 155  */
 156 struct expression *get_argument_from_call_expr(struct expression_list *args,
 157                                                int num)
 158 {
 159         struct expression *expr;
 160         int i = 0;
 161
 162         if (!args)
 163                 return NULL;
 164
 165         FOR_EACH_PTR(args, expr) {
 166                 if (i == num)
 167                         return expr;
 168                 i++;
 169         } END_FOR_EACH_PTR(expr);
 170         return NULL;
 171 }
 172
 173 struct expression *get_array_expr(struct expression *expr)
 174 {
 175         struct expression *parent;
 176         struct symbol *type;
 177
 178         if (expr->type != EXPR_BINOP || expr->op != '+')
 179                 return NULL;
 180
 181         type = get_type(expr->left);
 182         if (!type)
 183                 return NULL;
 184         if (type->type == SYM_ARRAY)
 185                 return expr->left;
 186         if (type->type != SYM_PTR)
 187                 return NULL;
 188
 189         parent = expr_get_parent_expr(expr);
 190         if (!parent)  /* Sometimes we haven't set up the ->parent yet. FIXME!! */
 191                 return expr->left;
 192         if (parent->type == EXPR_PREOP && parent->op == '*')
 193                 return expr->left;
 194
 195         return NULL;
 196 }
 197
 198 static struct expression *strip_star_address(struct expression *expr)
 199 {
 200         struct expression *unop;
 201
 202         if (expr->type != EXPR_PREOP || expr->op != '*')
 203                 return expr;
 204         unop = strip_parens(expr->unop);
 205         if (unop->type != EXPR_PREOP || unop->op != '&')
 206                 return expr;
 207
 208         return unop->unop;
 209 }
 210
 211 static struct expression *strip_parens_symbol(struct expression *expr)
 212 {
 213         struct expression *unop;
 214
 215         if (expr->type != EXPR_PREOP || expr->op != '(')
 216                 return expr;
 217         /*
 218          * This should probably be strip_parens() but expr_to_str() doesn't
 219          * print casts so we may as well strip those too.  In other words,
 220          * instead of fixing the code to print the cast, it's easier to just
 221          * write even more code that relies on the bug.  ;)
 222          */
 223         unop = strip_expr(expr->unop);
 224         if (unop->type != EXPR_SYMBOL)
 225                 return expr;
 226         return unop;
 227 }
 228
 229 static int __get_variable_from_expr(struct symbol **sym_ptr, char *buf,
 230                                      struct expression *expr, int off, int len,
 231                                      int *complicated)
 232 {
 233         int orig_off = off;
 234
 235         if (!expr) {
 236                 /* can't happen on valid code */
 237                 *complicated = 1;
 238                 return 0;
 239         }
 240
 241         expr = strip_star_address(expr);
 242         expr = strip_parens_symbol(expr);
 243
 244         switch (expr->type) {
 245         case EXPR_DEREF: {
 246                 struct expression *deref;
 247                 int op;
 248
 249                 op = expr->op;
 250                 deref = expr->deref;
 251
 252                 /* this is pure guess work and nonsense programming */
 253                 if (deref->type == EXPR_PREOP && deref->op == '*') {
 254                         op = '*';
 255                         deref = deref->unop;
 256                 }
 257
 258                 off += __get_variable_from_expr(sym_ptr, buf, deref, off, len, complicated);
 259
 260                 if (op == '*')
 261                         off += append(buf, off, len, "->");
 262                 else
 263                         off += append(buf, off, len, ".");
 264
 265                 if (expr->member)
 266                         off += append(buf, off, len, "%s", expr->member->name);
 267                 else
 268                         off += append(buf, off, len, "unknown_member");
 269                 return off - orig_off;
 270         }
 271         case EXPR_SYMBOL:
 272                 if (expr->symbol_name)
 273                         off += append(buf, off, len, "%s", expr->symbol_name->name);
 274                 if (sym_ptr) {
 275                         if (*sym_ptr)
 276                                 *complicated = 1;
 277                         *sym_ptr = expr->symbol;
 278                 }
 279                 return off - orig_off;
 280         case EXPR_PREOP: {
 281                 const char *tmp;
 282
 283                 if (get_expression_statement(expr)) {
 284                         *complicated = 2;
 285                         return 0;
 286                 }
 287                 if (expr->op == SPECIAL_DECREMENT ||
 288                     expr->op == SPECIAL_INCREMENT)
 289                         *complicated = 1;
 290
 291                 if (expr->op == '*' && get_array_expr(expr->unop))
 292                         tmp = "";
 293                 else
 294                         tmp = show_special(expr->op);
 295
 296                 off += append(buf, off, len, "%s", tmp);
 297                 off += __get_variable_from_expr(sym_ptr, buf, expr->unop, off,
 298                                                 len, complicated);
 299                 if (expr->op == '(')
 300                         off += append(buf, off, len, ")");
 301
 302                 return off - orig_off;
 303         }
 304         case EXPR_POSTOP: {
 305                 off += __get_variable_from_expr(sym_ptr, buf, expr->unop, off, len,
 306                                                 complicated);
 307                 off += append(buf, off, len, "%s", show_special(expr->op));
 308
 309                 if (expr->op == SPECIAL_DECREMENT || expr->op == SPECIAL_INCREMENT)
 310                         *complicated = 1;
 311                 return off - orig_off;
 312         }
 313         case EXPR_ASSIGNMENT:
 314         case EXPR_COMPARE:
 315         case EXPR_LOGICAL:
 316         case EXPR_BINOP: {
 317                 struct expression *array_expr;
 318
 319                 *complicated = 1;
 320                 array_expr = get_array_expr(expr);
 321                 if (array_expr) {
 322                         off += __get_variable_from_expr(sym_ptr, buf, array_expr, off, len, complicated);
 323                         off += append(buf, off, len, "[");
 324                 } else {
 325                         off += __get_variable_from_expr(sym_ptr, buf, expr->left, off, len, complicated);
 326                         off += append(buf, off, len, " %s ", show_special(expr->op));
 327                 }
 328                 off += __get_variable_from_expr(NULL, buf, expr->right, off, len, complicated);
 329                 if (array_expr)
 330                         off += append(buf, off, len, "]");
 331                 return off - orig_off;
 332         }
 333         case EXPR_VALUE: {
 334                 sval_t sval = {};
 335
 336                 *complicated = 1;
 337                 if (!get_value(expr, &sval))
 338                         return 0;
 339                 off += append(buf, off, len, "%s", sval_to_numstr(sval));
 340                 return off - orig_off;
 341         }
 342         case EXPR_FVALUE: {
 343                 sval_t sval = {};
 344
 345                 *complicated = 1;
 346                 if (!get_value(expr, &sval))
 347                         return 0;
 348
 349                 off += append(buf, off, len, "%s", sval_to_numstr(sval));
 350                 return off - orig_off;
 351         }
 352         case EXPR_STRING:
 353                 off += append(buf, off, len, "\"");
 354                 if (expr->string)
 355                         off += append(buf, off, len, "%s", expr->string->data);
 356                 off += append(buf, off, len, "\"");
 357                 return off - orig_off;
 358         case EXPR_CALL: {
 359                 struct expression *tmp;
 360                 int i;
 361
 362                 *complicated = 1;
 363                 off += __get_variable_from_expr(NULL, buf, expr->fn, off, len, complicated);
 364                 off += append(buf, off, len, "(");
 365                 i = 0;
 366                 FOR_EACH_PTR(expr->args, tmp) {
 367                         if (i++)
 368                                 off += append(buf, off, len, ", ");
 369                         off += __get_variable_from_expr(NULL, buf, tmp, off, len, complicated);
 370                 } END_FOR_EACH_PTR(tmp);
 371                 off += append(buf, off, len, ")");
 372                 return off - orig_off;
 373         }
 374         case EXPR_CAST:
 375         case EXPR_FORCE_CAST:
 376                 return __get_variable_from_expr(sym_ptr, buf,
 377                                                 expr->cast_expression, off, len,
 378                                                 complicated);
 379         case EXPR_SIZEOF: {
 380                 sval_t sval;
 381                 int size;
 382
 383                 if (expr->cast_type && get_base_type(expr->cast_type)) {
 384                         size = type_bytes(get_base_type(expr->cast_type));
 385                         off += append(buf, off, len, "%d", size);
 386                 } else if (get_value(expr, &sval)) {
 387                         off += append(buf, off, len, "%s", sval_to_str(sval));
 388                 }
 389                 return off - orig_off;
 390         }
 391         case EXPR_IDENTIFIER:
 392                 *complicated = 1;
 393                 if (expr->expr_ident)
 394                         off += append(buf, off, len, "%s", expr->expr_ident->name);
 395                 return off - orig_off;
 396         case EXPR_SELECT:
 397         case EXPR_CONDITIONAL:
 398                 *complicated = 1;
 399                 off += append(buf, off, len, "(");
 400                 off += __get_variable_from_expr(NULL, buf, expr->conditional, off, len, complicated);
 401                 off += append(buf, off, len, ") ?");
 402                 if (expr->cond_true)
 403                         off += __get_variable_from_expr(NULL, buf, expr->cond_true, off, len, complicated);
 404                 off += append(buf, off, len, ":");
 405                 off += __get_variable_from_expr(NULL, buf, expr->cond_false, off, len, complicated);
 406                 return off - orig_off;
 407         default:
 408                 off += append(buf, off, len, "$expr_%p(%d)", expr, expr->type);
 409                 return off - orig_off;
 410         }
 411 }
 412
 413 struct expr_str_cache_results {
 414         struct expression *expr;
 415         char str[VAR_LEN];
 416         struct symbol *sym;
 417         int complicated;
 418 };
 419
 420 static void get_variable_from_expr(struct symbol **sym_ptr, char *buf,
 421                                      struct expression *expr, int len,
 422                                      int *complicated)
 423 {
 424         static struct expr_str_cache_results cached[8];
 425         struct symbol *tmp_sym = NULL;
 426         static int idx;
 427         int i;
 428
 429         for (i = 0; i < ARRAY_SIZE(cached); i++) {
 430                 if (expr == cached[i].expr) {
 431                         strncpy(buf, cached[i].str, len);
 432                         if (sym_ptr)
 433                                 *sym_ptr = cached[i].sym;
 434                         *complicated = cached[i].complicated;
 435                         return;
 436                 }
 437         }
 438
 439         __get_variable_from_expr(&tmp_sym, buf, expr, 0, len, complicated);
 440         if (sym_ptr)
 441                 *sym_ptr = tmp_sym;
 442
 443         if (expr->smatch_flags & Tmp)
 444                 return;
 445
 446         cached[idx].expr = expr;
 447         strncpy(cached[idx].str, buf, VAR_LEN);
 448         cached[idx].sym = tmp_sym;
 449         cached[idx].complicated = *complicated;
 450
 451         idx = (idx + 1) % ARRAY_SIZE(cached);
 452 }
 453
 454 /*
 455  * This is returns a stylized "c looking" representation of the
 456  * variable name.
 457  *
 458  * It uses the same buffer every time so you have to save the result
 459  * yourself if you want to keep it.
 460  *
 461  */
 462
 463 char *expr_to_str_sym(struct expression *expr, struct symbol **sym_ptr)
 464 {
 465         static char var_name[VAR_LEN];
 466         int complicated = 0;
 467
 468         if (sym_ptr)
 469                 *sym_ptr = NULL;
 470         var_name[0] = '\0';
 471
 472         if (!expr)
 473                 return NULL;
 474         get_variable_from_expr(sym_ptr, var_name, expr, sizeof(var_name),
 475                                &complicated);
 476         if (complicated < 2)
 477                 return alloc_string(var_name);
 478         else
 479                 return NULL;
 480 }
 481
 482 char *expr_to_str(struct expression *expr)
 483 {
 484         return expr_to_str_sym(expr, NULL);
 485 }
 486
 487 /*
 488  * get_variable_from_expr_simple() only returns simple variables.
 489  * If it's a complicated variable like a->foo[x] instead of just 'a->foo'
 490  * then it returns NULL.
 491  */
 492 char *expr_to_var_sym(struct expression *expr,
 493                                     struct symbol **sym_ptr)
 494 {
 495         static char var_name[VAR_LEN];
 496         int complicated = 0;
 497
 498         if (sym_ptr)
 499                 *sym_ptr = NULL;
 500         var_name[0] = '\0';
 501
 502         if (!expr)
 503                 return NULL;
 504         expr = strip_expr(expr);
 505         get_variable_from_expr(sym_ptr, var_name, expr, sizeof(var_name),
 506                                &complicated);
 507
 508         if (complicated) {
 509                 if (sym_ptr)
 510                         *sym_ptr = NULL;
 511                 return NULL;
 512         }
 513         return alloc_string(var_name);
 514 }
 515
 516 char *expr_to_var(struct expression *expr)
 517 {
 518         return expr_to_var_sym(expr, NULL);
 519 }
 520
 521 struct symbol *expr_to_sym(struct expression *expr)
 522 {
 523         struct symbol *sym;
 524         char *name;
 525
 526         name = expr_to_var_sym(expr, &sym);
 527         free_string(name);
 528         return sym;
 529 }
 530
 531 int get_complication_score(struct expression *expr)
 532 {
 533         expr = strip_expr(expr);
 534
 535         /*
 536          * Don't forget to keep get_complication_score() and store_all_links()
 537          * in sync.
 538          *
 539          */
 540
 541         if (!expr)
 542                 return 990;
 543
 544         switch (expr->type) {
 545         case EXPR_CALL:
 546                 return 991;
 547         case EXPR_COMPARE:
 548         case EXPR_BINOP:
 549                 return get_complication_score(expr->left) +
 550                        get_complication_score(expr->right);
 551         case EXPR_SYMBOL:
 552                 return 1;
 553         case EXPR_PREOP:
 554                 if (expr->op == '*' || expr->op == '(')
 555                         return get_complication_score(expr->unop);
 556                 return 993;
 557         case EXPR_DEREF:
 558                 return get_complication_score(expr->deref);
 559         case EXPR_VALUE:
 560         case EXPR_SIZEOF:
 561                 return 0;
 562         default:
 563                 return 994;
 564         }
 565 }
 566
 567 struct expression *reorder_expr_alphabetically(struct expression *expr)
 568 {
 569         struct expression *ret;
 570         char *left, *right;
 571
 572         if (expr->type != EXPR_BINOP)
 573                 return expr;
 574         if (expr->op != '+' && expr->op != '*')
 575                 return expr;
 576
 577         left = expr_to_var(expr->left);
 578         right = expr_to_var(expr->right);
 579         ret = expr;
 580         if (!left || !right)
 581                 goto free;
 582         if (strcmp(left, right) <= 0)
 583                 goto free;
 584
 585         ret = binop_expression(expr->right, expr->op, expr->left);
 586 free:
 587         free_string(left);
 588         free_string(right);
 589
 590         return ret;
 591 }
 592
 593 char *expr_to_chunk_helper(struct expression *expr, struct symbol **sym, struct var_sym_list **vsl)
 594 {
 595         struct var_sym_list *tmp_vsl;
 596         char *name;
 597         struct symbol *tmp;
 598         int score;
 599
 600         if (vsl)
 601                 *vsl = NULL;
 602         if (sym)
 603                 *sym = NULL;
 604
 605         expr = strip_parens(expr);
 606         if (!expr)
 607                 return NULL;
 608
 609         name = expr_to_var_sym(expr, &tmp);
 610         if (name && tmp) {
 611                 if (sym)
 612                         *sym = tmp;
 613                 if (vsl)
 614                         add_var_sym(vsl, name, tmp);
 615                 return name;
 616         }
 617         free_string(name);
 618
 619         score = get_complication_score(expr);
 620         if (score <= 0 || score > 2)
 621                 return NULL;
 622
 623         tmp_vsl = expr_to_vsl(expr);
 624         if (vsl) {
 625                 *vsl = tmp_vsl;
 626                 if (!*vsl)
 627                         return NULL;
 628         }
 629         if (sym) {
 630                 if (ptr_list_size((struct ptr_list *)tmp_vsl) == 1) {
 631                         struct var_sym *vs;
 632
 633                         vs = first_ptr_list((struct ptr_list *)tmp_vsl);
 634                         *sym = vs->sym;
 635                 }
 636         }
 637
 638         expr = reorder_expr_alphabetically(expr);
 639
 640         return expr_to_str(expr);
 641 }
 642
 643 char *expr_to_known_chunk_sym(struct expression *expr, struct symbol **sym)
 644 {
 645         return expr_to_chunk_helper(expr, sym, NULL);
 646 }
 647
 648 char *expr_to_chunk_sym_vsl(struct expression *expr, struct symbol **sym, struct var_sym_list **vsl)
 649 {
 650         return expr_to_chunk_helper(expr, sym, vsl);
 651 }
 652
 653 int sym_name_is(const char *name, struct expression *expr)
 654 {
 655         if (!expr)
 656                 return 0;
 657         if (expr->type != EXPR_SYMBOL)
 658                 return 0;
 659         if (!strcmp(expr->symbol_name->name, name))
 660                 return 1;
 661         return 0;
 662 }
 663
 664 int expr_is_zero(struct expression *expr)
 665 {
 666         sval_t sval;
 667
 668         if (get_value(expr, &sval) && sval.value == 0)
 669                 return 1;
 670         return 0;
 671 }
 672
 673 int is_array(struct expression *expr)
 674 {
 675         struct symbol *type;
 676
 677         expr = strip_expr(expr);
 678         if (!expr)
 679                 return 0;
 680
 681         if (expr->type == EXPR_PREOP && expr->op == '*') {
 682                 expr = strip_expr(expr->unop);
 683                 if (!expr)
 684                         return 0;
 685                 if (expr->type == EXPR_BINOP && expr->op == '+')
 686                         return 1;
 687         }
 688
 689         if (expr->type != EXPR_BINOP || expr->op != '+')
 690                 return 0;
 691
 692         type = get_type(expr->left);
 693         if (!type || type->type != SYM_ARRAY)
 694                 return 0;
 695
 696         return 1;
 697 }
 698
 699 struct expression *get_array_base(struct expression *expr)
 700 {
 701         if (!is_array(expr))
 702                 return NULL;
 703         expr = strip_expr(expr);
 704         if (expr->type == EXPR_PREOP && expr->op == '*')
 705                 expr = strip_expr(expr->unop);
 706         if (expr->type != EXPR_BINOP || expr->op != '+')
 707                 return NULL;
 708         return strip_parens(expr->left);
 709 }
 710
 711 struct expression *get_array_offset(struct expression *expr)
 712 {
 713         if (!is_array(expr))
 714                 return NULL;
 715         expr = strip_expr(expr);
 716         if (expr->type == EXPR_PREOP && expr->op == '*')
 717                 expr = strip_expr(expr->unop);
 718         if (expr->type != EXPR_BINOP || expr->op != '+')
 719                 return NULL;
 720         expr = strip_parens(expr->right);
 721         if (expr->type == EXPR_POSTOP)
 722                 expr = strip_parens(expr->unop);
 723         return expr;
 724 }
 725
 726 const char *show_state(struct smatch_state *state)
 727 {
 728         if (!state)
 729                 return NULL;
 730         return state->name;
 731 }
 732
 733 struct statement *get_expression_statement(struct expression *expr)
 734 {
 735         /* What are those things called? if (({....; ret;})) { ...*/
 736
 737         if (expr->type != EXPR_PREOP)
 738                 return NULL;
 739         if (expr->op != '(')
 740                 return NULL;
 741         if (!expr->unop)
 742                 return NULL;
 743         if (expr->unop->type != EXPR_STATEMENT)
 744                 return NULL;
 745         if (expr->unop->statement->type != STMT_COMPOUND)
 746                 return NULL;
 747         return expr->unop->statement;
 748 }
 749
 750 struct expression *strip_parens(struct expression *expr)
 751 {
 752         if (!expr)
 753                 return NULL;
 754
 755         if (expr->type == EXPR_PREOP) {
 756                 if (!expr->unop)
 757                         return expr;  /* parsing invalid code */
 758
 759                 if (expr->op == '(' && expr->unop->type == EXPR_STATEMENT &&
 760                         expr->unop->statement->type == STMT_COMPOUND)
 761                         return expr;
 762                 if (expr->op == '(')
 763                         return strip_parens(expr->unop);
 764         }
 765         return expr;
 766 }
 767
 768 struct expression *strip__builtin_choose_expr(struct expression *expr)
 769 {
 770         struct expression *const_expr, *expr1, *expr2;
 771         sval_t sval;
 772
 773         if (expr->type != EXPR_CALL)
 774                 return expr;
 775
 776         if (!sym_name_is("__builtin_choose_expr", expr->fn))
 777                 return expr;
 778
 779         const_expr = get_argument_from_call_expr(expr->args, 0);
 780         expr1 = get_argument_from_call_expr(expr->args, 1);
 781         expr2 = get_argument_from_call_expr(expr->args, 2);
 782
 783         if (!get_value(const_expr, &sval) || !expr1 || !expr2)
 784                 return expr;
 785
 786         if (sval.value)
 787                 return strip_expr(expr1);
 788         else
 789                 return strip_expr(expr2);
 790 }
 791
 792 struct expression *strip_Generic(struct expression *expr)
 793 {
 794         struct type_expression *map;
 795         struct symbol *type, *tmp;
 796
 797         if (!expr || expr->type != EXPR_GENERIC)
 798                 return expr;
 799
 800         type = get_type(expr->control);
 801
 802         for (map = expr->map; map; map = map->next) {
 803                 tmp = get_real_base_type(map->type);
 804                 if (!types_equiv(type, tmp))
 805                         continue;
 806                 if (!map->expr)
 807                         return expr;
 808                 return map->expr;
 809         }
 810
 811         if (!expr->def)
 812                 return expr;
 813
 814         return expr->def;
 815 }
 816
 817 static struct expression *strip_plus_zero(struct expression *expr, bool set_parent, bool cast, int *nest)
 818 {
 819         struct symbol *left_type, *right_type;
 820
 821         if (*nest > 4)
 822                 return expr;
 823
 824         if (expr->type != EXPR_BINOP || expr->op != '+')
 825                 return expr;
 826
 827         /* don't strip away zero from the my_array[0] */
 828         if (!is_array(expr->left))
 829                 return expr;
 830
 831         left_type = get_type(expr->left);
 832         right_type = get_type(expr->right);
 833         if (!left_type || !right_type)
 834                 return expr;
 835
 836         if (expr_is_zero(expr->left)) {
 837                 if (type_positive_bits(left_type) > 31 &&
 838                     type_positive_bits(left_type) > type_positive_bits(right_type))
 839                         return expr;
 840                 return strip_expr_helper(expr->right, set_parent, cast, nest);
 841         }
 842         if (expr_is_zero(expr->right)) {
 843                 if (type_positive_bits(right_type) > 31 &&
 844                     type_positive_bits(right_type) > type_positive_bits(left_type))
 845                         return expr;
 846                 return strip_expr_helper(expr->left, set_parent, cast, nest);
 847         }
 848
 849         return expr;
 850 }
 851
 852 static struct expression *strip_expr_helper(struct expression *expr, bool set_parent, bool cast, int *nest)
 853 {
 854         (*nest)++;
 855
 856         if (!expr)
 857                 return NULL;
 858
 859         switch (expr->type) {
 860         case EXPR_FORCE_CAST:
 861         case EXPR_CAST:
 862                 if (set_parent)
 863                         expr_set_parent_expr(expr->cast_expression, expr);
 864
 865                 if (!expr->cast_expression)
 866                         return expr;
 867                 if (!cast) {
 868                         struct symbol *type;
 869
 870                         type = get_type(expr->cast_expression);
 871                         if (type != expr->cast_type)
 872                                 return expr;
 873                 }
 874                 return strip_expr_helper(expr->cast_expression, set_parent, cast, nest);
 875         case EXPR_PREOP: {
 876                 struct expression *unop;
 877
 878                 if (!expr->unop)  /* parsing invalid code */
 879                         return expr;
 880                 if (set_parent)
 881                         expr_set_parent_expr(expr->unop, expr);
 882
 883                 while (expr->op == '(' &&
 884                        expr->unop->type == EXPR_PREOP &&
 885                        expr->unop->op == '(')
 886                         expr = expr->unop;
 887
 888                 if (expr->op == '(' && expr->unop->type == EXPR_STATEMENT &&
 889                         expr->unop->statement->type == STMT_COMPOUND)
 890                         return expr;
 891
 892                 unop = strip_expr_helper(expr->unop, set_parent, cast, nest);
 893
 894                 if (expr->op == '*' && unop &&
 895                     unop->type == EXPR_PREOP && unop->op == '&') {
 896                         struct symbol *type = get_type(unop->unop);
 897
 898                         if (type && type->type == SYM_ARRAY)
 899                                 return expr;
 900                         return strip_expr_helper(unop->unop, set_parent, cast, nest);
 901                 }
 902
 903                 if (expr->op == '(')
 904                         return unop;
 905
 906                 return expr;
 907         }
 908         case EXPR_CONDITIONAL:
 909                 if (known_condition_true(expr->conditional)) {
 910                         if (expr->cond_true) {
 911                                 if (set_parent)
 912                                         expr_set_parent_expr(expr->cond_true, expr);
 913                                 return strip_expr_helper(expr->cond_true, set_parent, cast, nest);
 914                         }
 915                         if (set_parent)
 916                                 expr_set_parent_expr(expr->conditional, expr);
 917                         return strip_expr_helper(expr->conditional, set_parent, cast, nest);
 918                 }
 919                 if (known_condition_false(expr->conditional)) {
 920                         if (set_parent)
 921                                 expr_set_parent_expr(expr->cond_false, expr);
 922                         return strip_expr_helper(expr->cond_false, set_parent, cast, nest);
 923                 }
 924                 return expr;
 925         case EXPR_CALL:
 926                 if (sym_name_is("__builtin_expect", expr->fn) ||
 927                     sym_name_is("__builtin_bswap16", expr->fn) ||
 928                     sym_name_is("__builtin_bswap32", expr->fn) ||
 929                     sym_name_is("__builtin_bswap64", expr->fn)) {
 930                         expr = get_argument_from_call_expr(expr->args, 0);
 931                         return strip_expr_helper(expr, set_parent, cast, nest);
 932                 }
 933                 if (sym_name_is("__builtin_choose_expr", expr->fn))
 934                         return strip__builtin_choose_expr(expr);
 935                 return expr;
 936         case EXPR_BINOP:
 937                 return strip_plus_zero(expr, set_parent, cast, nest);
 938         case EXPR_GENERIC:
 939                 return strip_Generic(expr);
 940         }
 941         return expr;
 942 }
 943
 944 struct strip_cache_res {
 945         struct expression *expr;
 946         struct expression *res;
 947 };
 948 #define STRIP_CACHE_SIZE 4
 949 static struct strip_cache_res strip_cache[STRIP_CACHE_SIZE];
 950 static struct strip_cache_res strip_no_cast_cache[STRIP_CACHE_SIZE];
 951 static struct strip_cache_res strip_set_parent_cache[STRIP_CACHE_SIZE];
 952
 953 static struct expression *call_strip_helper(struct expression *expr,
 954                                             struct strip_cache_res *cache,
 955                                             int *idx,
 956                                             bool set_parent,
 957                                             bool cast)
 958 {
 959         struct expression *ret;
 960         int nest = 0;
 961         int i;
 962
 963         if (!expr)
 964                 return NULL;
 965
 966         for (i = 0; i < ARRAY_SIZE(strip_cache); i++) {
 967                 if (cache[i].expr == expr)
 968                         return cache[i].res;
 969         }
 970
 971         ret = strip_expr_helper(expr, set_parent, cast, &nest);
 972         *idx = (*idx + 1) % STRIP_CACHE_SIZE;
 973         cache[*idx].expr = expr;
 974         cache[*idx].res = ret;
 975         return ret;
 976 }
 977
 978 struct expression *strip_expr(struct expression *expr)
 979 {
 980         static int cache_idx;
 981
 982         return call_strip_helper(expr, strip_cache, &cache_idx, false, true);
 983 }
 984
 985 struct expression *strip_no_cast(struct expression *expr)
 986 {
 987         static int cache_idx;
 988
 989         return call_strip_helper(expr, strip_no_cast_cache, &cache_idx, false, false);
 990 }
 991
 992 struct expression *strip_expr_set_parent(struct expression *expr)
 993 {
 994         static int cache_idx;
 995
 996         return call_strip_helper(expr, strip_set_parent_cache, &cache_idx, true, true);
 997 }
 998
 999 void clear_strip_cache(void)
1000 {
1001         memset(strip_cache, 0, sizeof(strip_cache));
1002         memset(strip_no_cast_cache, 0, sizeof(strip_no_cast_cache));
1003         memset(strip_set_parent_cache, 0, sizeof(strip_set_parent_cache));
1004 }
1005
1006 static void delete_state_tracker(struct tracker *t)
1007 {
1008         __delete_state(t->owner, t->name, t->sym);
1009         __free_tracker(t);
1010 }
1011
1012 void scoped_state(int my_id, const char *name, struct symbol *sym)
1013 {
1014         struct tracker *t;
1015
1016         t = alloc_tracker(my_id, name, sym);
1017         add_scope_hook((scope_hook *)&delete_state_tracker, t);
1018 }
1019
1020 int is_error_return(struct expression *expr)
1021 {
1022         struct symbol *cur_func = cur_func_sym;
1023         struct range_list *rl;
1024         sval_t sval;
1025
1026         if (!expr)
1027                 return 0;
1028         if (cur_func->type != SYM_NODE)
1029                 return 0;
1030         cur_func = get_base_type(cur_func);
1031         if (cur_func->type != SYM_FN)
1032                 return 0;
1033         cur_func = get_base_type(cur_func);
1034         if (cur_func == &void_ctype)
1035                 return 0;
1036         if (option_project == PROJ_KERNEL &&
1037             get_implied_rl(expr, &rl) &&
1038             rl_type(rl) == &int_ctype &&
1039             sval_is_negative(rl_min(rl)) &&
1040             rl_max(rl).value == -1)
1041                 return 1;
1042         if (!get_implied_value(expr, &sval))
1043                 return 0;
1044         if (sval.value < 0)
1045                 return 1;
1046         if (cur_func->type == SYM_PTR && sval.value == 0)
1047                 return 1;
1048         return 0;
1049 }
1050
1051 int getting_address(struct expression *expr)
1052 {
1053         int deref_count = 0;
1054
1055         while ((expr = expr_get_parent_expr(expr))) {
1056                 if (expr->type == EXPR_PREOP && expr->op == '*') {
1057                         /* &foo->bar->baz dereferences "foo->bar" */
1058                         if (deref_count == 0)
1059                                 deref_count++;
1060                         return false;
1061                 }
1062                 if (expr->type == EXPR_PREOP && expr->op == '&')
1063                         return true;
1064         }
1065         return false;
1066 }
1067
1068 int get_struct_and_member(struct expression *expr, const char **type, const char **member)
1069 {
1070         struct symbol *sym;
1071
1072         expr = strip_expr(expr);
1073         if (expr->type != EXPR_DEREF)
1074                 return 0;
1075         if (!expr->member)
1076                 return 0;
1077
1078         sym = get_type(expr->deref);
1079         if (!sym)
1080                 return 0;
1081         if (sym->type == SYM_UNION)
1082                 return 0;
1083         if (!sym->ident)
1084                 return 0;
1085
1086         *type = sym->ident->name;
1087         *member = expr->member->name;
1088         return 1;
1089 }
1090
1091 char *get_member_name(struct expression *expr)
1092 {
1093         char buf[256];
1094         struct symbol *sym;
1095
1096         expr = strip_expr(expr);
1097         if (!expr || expr->type != EXPR_DEREF)
1098                 return NULL;
1099         if (!expr->member)
1100                 return NULL;
1101
1102         sym = get_type(expr->deref);
1103         if (!sym)
1104                 return NULL;
1105         if (sym->type == SYM_UNION) {
1106                 snprintf(buf, sizeof(buf), "(union %s)->%s",
1107                          sym->ident ? sym->ident->name : "anonymous",
1108                          expr->member->name);
1109                 return alloc_string(buf);
1110         }
1111         if (!sym->ident) {
1112                 struct expression *deref;
1113                 char *full, *outer;
1114                 int len;
1115
1116                 /*
1117                  * If we're in an anonymous struct then maybe we can find an
1118                  * outer struct name to use as a name.  This code should be
1119                  * recursive and cleaner.  I am not very proud of it.
1120                  *
1121                  */
1122
1123                 deref = strip_parens(expr->deref);
1124                 if (deref->type != EXPR_DEREF || !deref->member)
1125                         return NULL;
1126                 sym = get_type(deref->deref);
1127                 if (!sym || sym->type != SYM_STRUCT || !sym->ident)
1128                         return NULL;
1129
1130                 full = expr_to_str(expr);
1131                 if (!full)
1132                         return NULL;
1133                 deref = deref->deref;
1134                 if (deref->type == EXPR_PREOP && deref->op == '*')
1135                         deref = deref->unop;
1136                 outer = expr_to_str(deref);
1137                 if (!outer) {
1138                         free_string(full);
1139                         return NULL;
1140                 }
1141                 len = strlen(outer);
1142                 if (strncmp(outer, full, len) != 0) {
1143                         free_string(full);
1144                         free_string(outer);
1145                         return NULL;
1146                 }
1147                 if (full[len] == '-' && full[len + 1] == '>')
1148                         len += 2;
1149                 if (full[len] == '.')
1150                         len++;
1151                 snprintf(buf, sizeof(buf), "(struct %s)->%s", sym->ident->name, full + len);
1152                 free_string(outer);
1153                 free_string(full);
1154
1155                 return alloc_string(buf);
1156         }
1157         snprintf(buf, sizeof(buf), "(struct %s)->%s", sym->ident->name, expr->member->name);
1158         return alloc_string(buf);
1159 }
1160
1161 int cmp_pos(struct position pos1, struct position pos2)
1162 {
1163         /* the stream position is ... */
1164         if (pos1.stream > pos2.stream)
1165                 return -1;
1166         if (pos1.stream < pos2.stream)
1167                 return 1;
1168
1169         if (pos1.line < pos2.line)
1170                 return -1;
1171         if (pos1.line > pos2.line)
1172                 return 1;
1173
1174         if (pos1.pos < pos2.pos)
1175                 return -1;
1176         if (pos1.pos > pos2.pos)
1177                 return 1;
1178
1179         return 0;
1180 }
1181
1182 int positions_eq(struct position pos1, struct position pos2)
1183 {
1184         if (pos1.line != pos2.line)
1185                 return 0;
1186         if (pos1.pos != pos2.pos)
1187                 return 0;
1188         if (pos1.stream != pos2.stream)
1189                 return 0;
1190         return 1;
1191 }
1192
1193 struct statement *get_current_statement(void)
1194 {
1195         struct statement *prev, *tmp;
1196
1197         prev = last_ptr_list((struct ptr_list *)big_statement_stack);
1198
1199         if (!prev || !get_macro_name(prev->pos))
1200                 return prev;
1201
1202         FOR_EACH_PTR_REVERSE(big_statement_stack, tmp) {
1203                 if (positions_eq(tmp->pos, prev->pos))
1204                         continue;
1205                 if (prev->pos.line > tmp->pos.line)
1206                         return prev;
1207                 return tmp;
1208         } END_FOR_EACH_PTR_REVERSE(tmp);
1209         return prev;
1210 }
1211
1212 struct statement *get_prev_statement(void)
1213 {
1214         struct statement *tmp;
1215         int i;
1216
1217         i = 0;
1218         FOR_EACH_PTR_REVERSE(big_statement_stack, tmp) {
1219                 if (i++ == 1)
1220                         return tmp;
1221         } END_FOR_EACH_PTR_REVERSE(tmp);
1222         return NULL;
1223 }
1224
1225 struct expression *get_last_expr_from_expression_stmt(struct expression *expr)
1226 {
1227         struct statement *stmt;
1228         struct statement *last_stmt;
1229
1230         while (expr->type == EXPR_PREOP && expr->op == '(')
1231                 expr = expr->unop;
1232         if (expr->type != EXPR_STATEMENT)
1233                 return NULL;
1234         stmt = expr->statement;
1235         if (!stmt)
1236                 return NULL;
1237         if (stmt->type == STMT_COMPOUND) {
1238                 last_stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
1239                 if (!last_stmt)
1240                         return NULL;
1241                 if (last_stmt->type == STMT_LABEL)
1242                         last_stmt = last_stmt->label_statement;
1243                 if (last_stmt->type != STMT_EXPRESSION)
1244                         return NULL;
1245                 return last_stmt->expression;
1246         }
1247         if (stmt->type == STMT_EXPRESSION)
1248                 return stmt->expression;
1249         return NULL;
1250 }
1251
1252 int ms_since(struct timeval *start)
1253 {
1254         struct timeval end;
1255         double diff;
1256
1257         gettimeofday(&end, NULL);
1258         diff = (end.tv_sec - start->tv_sec) * 1000.0;
1259         diff += (end.tv_usec - start->tv_usec) / 1000.0;
1260         return (int)diff;
1261 }
1262
1263 int parent_is_gone_var_sym(const char *name, struct symbol *sym)
1264 {
1265         if (!name || !sym)
1266                 return 0;
1267
1268         if (parent_is_err_or_null_var_sym(name, sym) ||
1269             parent_is_free_var_sym(name, sym))
1270                 return 1;
1271         return 0;
1272 }
1273
1274 int parent_is_gone(struct expression *expr)
1275 {
1276         struct symbol *sym;
1277         char *var;
1278         int ret = 0;
1279
1280         expr = strip_expr(expr);
1281         var = expr_to_var_sym(expr, &sym);
1282         if (!var || !sym)
1283                 goto free;
1284         ret = parent_is_gone_var_sym(var, sym);
1285 free:
1286         free_string(var);
1287         return ret;
1288 }
1289
1290 int invert_op(int op)
1291 {
1292         switch (op) {
1293         case '*':
1294                 return '/';
1295         case '/':
1296                 return '*';
1297         case '+':
1298                 return '-';
1299         case '-':
1300                 return '+';
1301         case SPECIAL_LEFTSHIFT:
1302                 return SPECIAL_RIGHTSHIFT;
1303         case SPECIAL_RIGHTSHIFT:
1304                 return SPECIAL_LEFTSHIFT;
1305         }
1306         return 0;
1307 }
1308
1309 int op_remove_assign(int op)
1310 {
1311         switch (op) {
1312         case SPECIAL_ADD_ASSIGN:
1313                 return '+';
1314         case SPECIAL_SUB_ASSIGN:
1315                 return '-';
1316         case SPECIAL_MUL_ASSIGN:
1317                 return '*';
1318         case SPECIAL_DIV_ASSIGN:
1319                 return '/';
1320         case SPECIAL_MOD_ASSIGN:
1321                 return '%';
1322         case SPECIAL_AND_ASSIGN:
1323                 return '&';
1324         case SPECIAL_OR_ASSIGN:
1325                 return '|';
1326         case SPECIAL_XOR_ASSIGN:
1327                 return '^';
1328         case SPECIAL_SHL_ASSIGN:
1329                 return SPECIAL_LEFTSHIFT;
1330         case SPECIAL_SHR_ASSIGN:
1331                 return SPECIAL_RIGHTSHIFT;
1332         default:
1333                 return op;
1334         }
1335 }
1336
1337 int expr_equiv(struct expression *one, struct expression *two)
1338 {
1339         struct symbol *one_sym = NULL;
1340         struct symbol *two_sym = NULL;
1341         char *one_name = NULL;
1342         char *two_name = NULL;
1343         int ret = 0;
1344
1345         if (!one || !two)
1346                 return 0;
1347         if (one == two)
1348                 return 1;
1349         if (one->type != two->type)
1350                 return 0;
1351         if (is_fake_call(one) || is_fake_call(two))
1352                 return 0;
1353
1354         one_name = expr_to_str_sym(one, &one_sym);
1355         if (!one_name)
1356                 goto free;
1357         two_name = expr_to_str_sym(two, &two_sym);
1358         if (!two_name)
1359                 goto free;
1360         if (one_sym != two_sym)
1361                 goto free;
1362         /*
1363          * This is a terrible hack because expr_to_str() sometimes gives up in
1364          * the middle and just returns what it has.  If you see a () you know
1365          * the string is bogus.
1366          */
1367         if (strstr(one_name, "()"))
1368                 goto free;
1369         if (strcmp(one_name, two_name) == 0)
1370                 ret = 1;
1371 free:
1372         free_string(one_name);
1373         free_string(two_name);
1374         return ret;
1375 }
1376
1377 void push_int(struct int_stack **stack, int num)
1378 {
1379         int *munged;
1380
1381         /*
1382          * Just put the int on directly instead of a pointer to the int.
1383          * Shift it to the left because Sparse uses the last two bits.
1384          * This is sort of a dirty hack, yes.
1385          */
1386
1387         munged = INT_PTR(num << 2);
1388
1389         add_ptr_list(stack, munged);
1390 }
1391
1392 int pop_int(struct int_stack **stack)
1393 {
1394         int *num;
1395
1396         num = last_ptr_list((struct ptr_list *)*stack);
1397         delete_ptr_list_last((struct ptr_list **)stack);
1398
1399         return PTR_INT(num) >> 2;
1400 }
1401
1402 bool token_to_ul(struct token *token, unsigned long *val)
1403 {
1404         int cnt = 0;
1405
1406         /* this function only works for very specific simple defines */
1407         while (cnt++ < 20 && token) {
1408                 switch (token_type(token)) {
1409                 case TOKEN_IDENT:
1410                         if (macro_to_ul(show_ident(token->ident), val))
1411                                 return true;
1412                         break;
1413                 case TOKEN_NUMBER:
1414                         *val = strtoul(token->number, NULL, 0);
1415                         return true;
1416                 }
1417                 token = token->next;
1418         }
1419         return false;
1420 }
1421
1422 bool macro_to_ul(const char *macro, unsigned long *val)
1423 {
1424         struct symbol *macro_sym;
1425
1426         if (!macro)
1427                 return false;
1428
1429         macro_sym = lookup_macro_symbol(macro);
1430         if (!macro_sym || !macro_sym->expansion)
1431                 return false;
1432         return token_to_ul(macro_sym->expansion, val);
1433 }
1434
1435 int success_fail_return(struct range_list *rl)
1436 {
1437         char *str;
1438         sval_t sval;
1439
1440         if (!rl)
1441                 return RET_SUCCESS;
1442
1443         /* NFSv3 uses negative error codes such as -EIOCBQUEUED for success */
1444         if (rl_to_sval(rl, &sval) && sval.value == -529)
1445                 return RET_SUCCESS;
1446
1447         // Negatives are a failure
1448         if (sval_is_negative(rl_max(rl)))
1449                 return RET_FAIL;
1450
1451         // NULL and error pointers are a failure
1452         if (type_is_ptr(rl_type(rl)) && is_err_or_null(rl))
1453                 return RET_FAIL;
1454
1455         if (rl_to_sval(rl, &sval)) {
1456                 if (sval.value == 0) {
1457                         // Zero is normally success but false is a failure
1458                         if (type_bits(sval.type) == 1)
1459                                 return RET_FAIL;
1460                         else
1461                                 return RET_SUCCESS;
1462                 }
1463                 // true is success
1464                 if (sval.value == 1 && type_bits(sval.type) == 1)
1465                         return RET_SUCCESS;
1466         }
1467
1468         str = show_rl(rl);
1469         if (strcmp(str, "s32min-(-1),1-s32max") == 0)
1470                 return RET_FAIL;
1471
1472         if (strcmp(str, "0-s32max") == 0)
1473                 return RET_SUCCESS;
1474
1475         return RET_UNKNOWN;
1476 }