smatch_comparison.c

   1 /*
   2  * smatch/smatch_comparison.c
   3  *
   4  * Copyright (C) 2012 Oracle.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * The point here is to store the relationships between two variables.
  12  * Ie:  y > x.
  13  * To do that we create a state with the two variables in alphabetical order:
  14  * ->name = "x vs y" and the state would be "<".  On the false path the state
  15  * would be ">=".
  16  *
  17  * Part of the trick of it is that if x or y is modified then we need to reset
  18  * the state.  We need to keep a list of all the states which depend on x and
  19  * all the states which depend on y.  The link_id code handles this.
  20  *
  21  * Future work:  If we know that x is greater than y and y is greater than z
  22  * then we know that x is greater than z.
  23  */
  24
  25 #include "smatch.h"
  26 #include "smatch_extra.h"
  27 #include "smatch_slist.h"
  28
  29 static int compare_id;
  30 static int link_id;
  31
  32 static struct smatch_state compare_states[] = {
  33         ['<'] = {
  34                 .name = "<",
  35                 .data = (void *)'<',
  36         },
  37         [SPECIAL_UNSIGNED_LT] = {
  38                 .name = "<",
  39                 .data = (void *)SPECIAL_UNSIGNED_LT,
  40         },
  41         [SPECIAL_LTE] = {
  42                 .name = "<=",
  43                 .data = (void *)SPECIAL_LTE,
  44         },
  45         [SPECIAL_UNSIGNED_LTE] = {
  46                 .name = "<=",
  47                 .data = (void *)SPECIAL_UNSIGNED_LTE,
  48         },
  49         [SPECIAL_EQUAL] = {
  50                 .name = "==",
  51                 .data = (void *)SPECIAL_EQUAL,
  52         },
  53         [SPECIAL_NOTEQUAL] = {
  54                 .name = "!=",
  55                 .data = (void *)SPECIAL_NOTEQUAL,
  56         },
  57         [SPECIAL_GTE] = {
  58                 .name = ">=",
  59                 .data = (void *)SPECIAL_GTE,
  60         },
  61         [SPECIAL_UNSIGNED_GTE] = {
  62                 .name = ">=",
  63                 .data = (void *)SPECIAL_UNSIGNED_GTE,
  64         },
  65         ['>'] = {
  66                 .name = ">",
  67                 .data = (void *)'>',
  68         },
  69         [SPECIAL_UNSIGNED_GT] = {
  70                 .name = ">",
  71                 .data = (void *)SPECIAL_UNSIGNED_GT,
  72         },
  73 };
  74
  75 static int flip_op(int op)
  76 {
  77         switch (op) {
  78         case 0:
  79                 return 0;
  80         case '<':
  81                 return '>';
  82         case SPECIAL_UNSIGNED_LT:
  83                 return SPECIAL_UNSIGNED_GT;
  84         case SPECIAL_LTE:
  85                 return SPECIAL_GTE;
  86         case SPECIAL_UNSIGNED_LTE:
  87                 return SPECIAL_UNSIGNED_GTE;
  88         case SPECIAL_EQUAL:
  89                 return SPECIAL_EQUAL;
  90         case SPECIAL_NOTEQUAL:
  91                 return SPECIAL_NOTEQUAL;
  92         case SPECIAL_GTE:
  93                 return SPECIAL_LTE;
  94         case SPECIAL_UNSIGNED_GTE:
  95                 return SPECIAL_UNSIGNED_LTE;
  96         case '>':
  97                 return '<';
  98         case SPECIAL_UNSIGNED_GT:
  99                 return SPECIAL_UNSIGNED_LT;
 100         default:
 101                 sm_msg("internal smatch bug.  unhandled comparison %d", op);
 102                 return op;
 103         }
 104 }
 105
 106 static int falsify_op(int op)
 107 {
 108         switch (op) {
 109         case 0:
 110                 return 0;
 111         case '<':
 112                 return SPECIAL_GTE;
 113         case SPECIAL_UNSIGNED_LT:
 114                 return SPECIAL_UNSIGNED_GTE;
 115         case SPECIAL_LTE:
 116                 return '>';
 117         case SPECIAL_UNSIGNED_LTE:
 118                 return SPECIAL_UNSIGNED_GT;
 119         case SPECIAL_EQUAL:
 120                 return SPECIAL_NOTEQUAL;
 121         case SPECIAL_NOTEQUAL:
 122                 return SPECIAL_EQUAL;
 123         case SPECIAL_GTE:
 124                 return '<';
 125         case SPECIAL_UNSIGNED_GTE:
 126                 return SPECIAL_UNSIGNED_LT;
 127         case '>':
 128                 return SPECIAL_LTE;
 129         case SPECIAL_UNSIGNED_GT:
 130                 return SPECIAL_UNSIGNED_LTE;
 131         default:
 132                 sm_msg("internal smatch bug.  unhandled comparison %d", op);
 133                 return op;
 134         }
 135 }
 136
 137 struct smatch_state *alloc_link_state(struct string_list *links)
 138 {
 139         struct smatch_state *state;
 140         static char buf[256];
 141         char *tmp;
 142         int i;
 143
 144         state = __alloc_smatch_state(0);
 145
 146         i = 0;
 147         FOR_EACH_PTR(links, tmp) {
 148                 if (!i++)
 149                         snprintf(buf, sizeof(buf), "%s", tmp);
 150                 else
 151                         snprintf(buf, sizeof(buf), "%s, %s", buf, tmp);
 152         } END_FOR_EACH_PTR(tmp);
 153
 154         state->name = alloc_sname(buf);
 155         state->data = links;
 156         return state;
 157 }
 158
 159 static void save_start_states(struct statement *stmt)
 160 {
 161         struct symbol *param;
 162         char orig[64];
 163         char state_name[128];
 164         struct smatch_state *state;
 165         struct string_list *links;
 166         char *link;
 167
 168         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
 169                 if (!param->ident)
 170                         continue;
 171                 snprintf(orig, sizeof(orig), "%s orig", param->ident->name);
 172                 snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig);
 173                 state = &compare_states[SPECIAL_EQUAL];
 174                 set_state(compare_id, state_name, NULL, state);
 175
 176                 link = alloc_sname(state_name);
 177                 links = NULL;
 178                 insert_string(&links,  link);
 179                 state = alloc_link_state(links);
 180                 set_state(link_id, param->ident->name, param, state);
 181         } END_FOR_EACH_PTR(param);
 182 }
 183
 184 static struct smatch_state *merge_func(struct smatch_state *s1, struct smatch_state *s2)
 185 {
 186         struct smatch_state *ret;
 187         struct string_list *links;
 188
 189         links = combine_string_lists(s1->data, s2->data);
 190         ret = alloc_link_state(links);
 191         return ret;
 192 }
 193
 194 static void save_link(struct expression *expr, char *link)
 195 {
 196         struct smatch_state *old_state, *new_state;
 197         struct string_list *links;
 198         char *new;
 199
 200         old_state = get_state_expr(link_id, expr);
 201         if (old_state)
 202                 links = clone_str_list(old_state->data);
 203         else
 204                 links = NULL;
 205
 206         new = alloc_sname(link);
 207         insert_string(&links, new);
 208
 209         new_state = alloc_link_state(links);
 210         set_state_expr(link_id, expr, new_state);
 211 }
 212
 213 static void match_inc(struct sm_state *sm)
 214 {
 215         struct string_list *links;
 216         struct smatch_state *state;
 217         char *tmp;
 218
 219         links = sm->state->data;
 220
 221         FOR_EACH_PTR(links, tmp) {
 222                 state = get_state(compare_id, tmp, NULL);
 223                 if (state == &compare_states[SPECIAL_EQUAL] ||
 224                     state == &compare_states[SPECIAL_GTE] ||
 225                     state == &compare_states[SPECIAL_UNSIGNED_GTE] ||
 226                     state == &compare_states['>'] ||
 227                     state == &compare_states[SPECIAL_UNSIGNED_GT]) {
 228                         set_state(compare_id, tmp, NULL, &compare_states['>']);
 229                 } else {
 230                         set_state(compare_id, tmp, NULL, &undefined);
 231                 }
 232         } END_FOR_EACH_PTR(tmp);
 233 }
 234
 235 static void match_dec(struct sm_state *sm)
 236 {
 237         struct string_list *links;
 238         struct smatch_state *state;
 239         char *tmp;
 240
 241         links = sm->state->data;
 242
 243         FOR_EACH_PTR(links, tmp) {
 244                 state = get_state(compare_id, tmp, NULL);
 245                 if (state == &compare_states[SPECIAL_EQUAL] ||
 246                     state == &compare_states[SPECIAL_LTE] ||
 247                     state == &compare_states[SPECIAL_UNSIGNED_LTE] ||
 248                     state == &compare_states['<'] ||
 249                     state == &compare_states[SPECIAL_UNSIGNED_LT]) {
 250                         set_state(compare_id, tmp, NULL, &compare_states['<']);
 251                 } else {
 252                         set_state(compare_id, tmp, NULL, &undefined);
 253                 }
 254         } END_FOR_EACH_PTR(tmp);
 255 }
 256
 257 static int match_inc_dec(struct sm_state *sm, struct expression *mod_expr)
 258 {
 259         if (!mod_expr)
 260                 return 0;
 261         if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP)
 262                 return 0;
 263
 264         if (mod_expr->op == SPECIAL_INCREMENT) {
 265                 match_inc(sm);
 266                 return 1;
 267         }
 268         if (mod_expr->op == SPECIAL_DECREMENT) {
 269                 match_dec(sm);
 270                 return 1;
 271         }
 272         return 0;
 273 }
 274
 275 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
 276 {
 277         struct string_list *links;
 278         char *tmp;
 279
 280         if (match_inc_dec(sm, mod_expr))
 281                 return;
 282
 283         links = sm->state->data;
 284
 285         FOR_EACH_PTR(links, tmp) {
 286                 set_state(compare_id, tmp, NULL, &undefined);
 287         } END_FOR_EACH_PTR(tmp);
 288         set_state(link_id, sm->name, sm->sym, &undefined);
 289 }
 290
 291 static void match_logic(struct expression *expr)
 292 {
 293         char *left = NULL;
 294         char *right = NULL;
 295         struct symbol *left_sym, *right_sym;
 296         int op, false_op;
 297         struct smatch_state *true_state, *false_state;
 298         char state_name[256];
 299
 300         if (expr->type != EXPR_COMPARE)
 301                 return;
 302         left = expr_to_var_sym(expr->left, &left_sym);
 303         if (!left || !left_sym)
 304                 goto free;
 305         right = expr_to_var_sym(expr->right, &right_sym);
 306         if (!right || !right_sym)
 307                 goto free;
 308
 309         if (strcmp(left, right) > 0) {
 310                 char *tmp = left;
 311                 left = right;
 312                 right = tmp;
 313                 op = flip_op(expr->op);
 314         } else {
 315                 op = expr->op;
 316         }
 317         false_op = falsify_op(op);
 318         snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
 319         true_state = &compare_states[op];
 320         false_state = &compare_states[false_op];
 321
 322         set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
 323         save_link(expr->left, state_name);
 324         save_link(expr->right, state_name);
 325 free:
 326         free_string(left);
 327         free_string(right);
 328 }
 329
 330 static void add_comparison(struct expression *left, int comparison, struct expression *right)
 331 {
 332         char *left_name = NULL;
 333         char *right_name = NULL;
 334         struct symbol *left_sym, *right_sym;
 335         struct smatch_state *state;
 336         char state_name[256];
 337
 338         left_name = expr_to_var_sym(left, &left_sym);
 339         if (!left_name || !left_sym)
 340                 goto free;
 341         right_name = expr_to_var_sym(right, &right_sym);
 342         if (!right_name || !right_sym)
 343                 goto free;
 344
 345         if (strcmp(left_name, right_name) > 0) {
 346                 char *tmp = left_name;
 347                 left_name = right_name;
 348                 right_name = tmp;
 349                 comparison = flip_op(comparison);
 350         }
 351         snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
 352         state = &compare_states[comparison];
 353
 354         set_state(compare_id, state_name, NULL, state);
 355         save_link(left, state_name);
 356         save_link(right, state_name);
 357 free:
 358         free_string(left_name);
 359         free_string(right_name);
 360
 361 }
 362
 363 static void match_assign_add(struct expression *expr)
 364 {
 365         struct expression *right;
 366         struct expression *r_left, *r_right;
 367         sval_t left_tmp, right_tmp;
 368
 369         right = strip_expr(expr->right);
 370         r_left = strip_expr(right->left);
 371         r_right = strip_expr(right->right);
 372
 373         if (!is_capped(expr->left)) {
 374                 get_absolute_max(r_left, &left_tmp);
 375                 get_absolute_max(r_right, &right_tmp);
 376                 if (sval_binop_overflows(left_tmp, '+', right_tmp))
 377                         return;
 378         }
 379
 380         get_absolute_min(r_left, &left_tmp);
 381         if (sval_is_negative(left_tmp))
 382                 return;
 383         get_absolute_min(r_right, &right_tmp);
 384         if (sval_is_negative(right_tmp))
 385                 return;
 386
 387         if (left_tmp.value == 0)
 388                 add_comparison(expr->left, SPECIAL_GTE, r_right);
 389         else
 390                 add_comparison(expr->left, '>', r_right);
 391
 392         if (right_tmp.value == 0)
 393                 add_comparison(expr->left, SPECIAL_GTE, r_left);
 394         else
 395                 add_comparison(expr->left, '>', r_left);
 396 }
 397
 398 static void match_assign_sub(struct expression *expr)
 399 {
 400         struct expression *right;
 401         struct expression *r_left, *r_right;
 402         int comparison;
 403         sval_t min;
 404
 405         right = strip_expr(expr->right);
 406         r_left = strip_expr(right->left);
 407         r_right = strip_expr(right->right);
 408
 409         if (get_absolute_min(r_right, &min) && sval_is_negative(min))
 410                 return;
 411
 412         comparison = get_comparison(r_left, r_right);
 413
 414         switch (comparison) {
 415         case '>':
 416         case SPECIAL_GTE:
 417                 if (implied_not_equal(r_right, 0))
 418                         add_comparison(expr->left, '>', r_left);
 419                 else
 420                         add_comparison(expr->left, SPECIAL_GTE, r_left);
 421                 return;
 422         }
 423 }
 424
 425 static void match_binop_assign(struct expression *expr)
 426 {
 427         struct expression *right;
 428
 429         right = strip_expr(expr->right);
 430         if (right->op == '+')
 431                 match_assign_add(expr);
 432         if (right->op == '-')
 433                 match_assign_sub(expr);
 434 }
 435
 436 static void match_normal_assign(struct expression *expr)
 437 {
 438         add_comparison(expr->left, SPECIAL_EQUAL, expr->right);
 439 }
 440
 441 static void match_assign(struct expression *expr)
 442 {
 443         struct expression *right;
 444
 445         right = strip_expr(expr->right);
 446         if (right->type == EXPR_BINOP)
 447                 match_binop_assign(expr);
 448         else
 449                 match_normal_assign(expr);
 450 }
 451
 452 static int get_comparison_strings(char *one, char *two)
 453 {
 454         char buf[256];
 455         struct smatch_state *state;
 456         int invert = 0;
 457         int ret = 0;
 458
 459         if (strcmp(one, two) > 0) {
 460                 char *tmp = one;
 461
 462                 one = two;
 463                 two = tmp;
 464                 invert = 1;
 465         }
 466
 467         snprintf(buf, sizeof(buf), "%s vs %s", one, two);
 468         state = get_state(compare_id, buf, NULL);
 469         if (state)
 470                 ret = PTR_INT(state->data);
 471
 472         if (invert)
 473                 ret = flip_op(ret);
 474
 475         return ret;
 476 }
 477
 478 int get_comparison(struct expression *a, struct expression *b)
 479 {
 480         char *one = NULL;
 481         char *two = NULL;
 482         int ret = 0;
 483
 484         one = expr_to_var(a);
 485         if (!one)
 486                 goto free;
 487         two = expr_to_var(b);
 488         if (!two)
 489                 goto free;
 490
 491         ret = get_comparison_strings(one, two);
 492 free:
 493         free_string(one);
 494         free_string(two);
 495         return ret;
 496 }
 497
 498 void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
 499 {
 500         struct expression *arg;
 501         int comparison;
 502         const char *c = range;
 503
 504         if (!str_to_comparison_arg(c, call, &comparison, &arg, NULL))
 505                 return;
 506         add_comparison(expr, SPECIAL_LTE, arg);
 507 }
 508
 509 char *range_comparison_to_param(struct expression *expr)
 510 {
 511         struct symbol *param;
 512         char *var = NULL;
 513         char buf[256];
 514         char *ret_str = NULL;
 515         int compare;
 516         sval_t min;
 517         int i;
 518
 519         var = expr_to_var(expr);
 520         if (!var)
 521                 goto free;
 522         get_absolute_min(expr, &min);
 523
 524         i = -1;
 525         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
 526                 i++;
 527                 if (!param->ident)
 528                         continue;
 529                 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
 530                 compare = get_comparison_strings(var, buf);
 531                 if (!compare)
 532                         continue;
 533                 if (compare == SPECIAL_EQUAL) {
 534                         snprintf(buf, sizeof(buf), "[%sp%d]", show_special(compare), i);
 535                         ret_str = alloc_sname(buf);
 536                 } else if (show_special(compare)[0] == '<') {
 537                         snprintf(buf, sizeof(buf), "%s-[%sp%d]", sval_to_str(min),
 538                                  show_special(compare), i);
 539                         ret_str = alloc_sname(buf);
 540
 541                 }
 542         } END_FOR_EACH_PTR(param);
 543
 544 free:
 545         free_string(var);
 546         return ret_str;
 547 }
 548
 549 void register_comparison(int id)
 550 {
 551         compare_id = id;
 552         add_hook(&match_logic, CONDITION_HOOK);
 553         add_hook(&match_assign, ASSIGNMENT_HOOK);
 554         add_hook(&save_start_states, AFTER_DEF_HOOK);
 555 }
 556
 557 void register_comparison_links(int id)
 558 {
 559         link_id = id;
 560         add_merge_hook(link_id, &merge_func);
 561         add_modification_hook(link_id, &match_modify);
 562 }