smatch_comparison.c

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