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 struct smatch_state *merge_func(struct smatch_state *s1, struct smatch_state *s2)
 161 {
 162         struct smatch_state *ret;
 163         struct string_list *links;
 164
 165         links = combine_string_lists(s1->data, s2->data);
 166         ret = alloc_link_state(links);
 167         return ret;
 168 }
 169
 170 static void save_link(struct expression *expr, char *link)
 171 {
 172         struct smatch_state *old_state, *new_state;
 173         struct string_list *links;
 174         char *new;
 175
 176         old_state = get_state_expr(link_id, expr);
 177         if (old_state)
 178                 links = clone_str_list(old_state->data);
 179         else
 180                 links = NULL;
 181
 182         new = alloc_sname(link);
 183         insert_string(&links, new);
 184
 185         new_state = alloc_link_state(links);
 186         set_state_expr(link_id, expr, new_state);
 187 }
 188
 189 static void clear_links(struct sm_state *sm)
 190 {
 191         struct string_list *links;
 192         char *tmp;
 193
 194         links = sm->state->data;
 195
 196         FOR_EACH_PTR(links, tmp) {
 197                 set_state(compare_id, tmp, NULL, &undefined);
 198         } END_FOR_EACH_PTR(tmp);
 199         set_state(link_id, sm->name, sm->sym, &undefined);
 200 }
 201
 202 static void match_logic(struct expression *expr)
 203 {
 204         char *left = NULL;
 205         char *right = NULL;
 206         struct symbol *left_sym, *right_sym;
 207         int op, false_op;
 208         struct smatch_state *true_state, *false_state;
 209         char state_name[256];
 210
 211         if (expr->type != EXPR_COMPARE)
 212                 return;
 213         left = expr_to_var_sym(expr->left, &left_sym);
 214         if (!left || !left_sym)
 215                 goto free;
 216         right = expr_to_var_sym(expr->right, &right_sym);
 217         if (!right || !right_sym)
 218                 goto free;
 219
 220         if (strcmp(left, right) > 0) {
 221                 char *tmp = left;
 222                 left = right;
 223                 right = tmp;
 224                 op = flip_op(expr->op);
 225         } else {
 226                 op = expr->op;
 227         }
 228         false_op = falsify_op(op);
 229         snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
 230         true_state = &compare_states[op];
 231         false_state = &compare_states[false_op];
 232
 233         set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
 234         save_link(expr->left, state_name);
 235         save_link(expr->right, state_name);
 236 free:
 237         free_string(left);
 238         free_string(right);
 239 }
 240
 241 static void add_comparison(struct expression *left, int comparison, struct expression *right)
 242 {
 243         char *left_name = NULL;
 244         char *right_name = NULL;
 245         struct symbol *left_sym, *right_sym;
 246         struct smatch_state *state;
 247         char state_name[256];
 248
 249         left_name = expr_to_var_sym(left, &left_sym);
 250         if (!left_name || !left_sym)
 251                 goto free;
 252         right_name = expr_to_var_sym(right, &right_sym);
 253         if (!right_name || !right_sym)
 254                 goto free;
 255
 256         if (strcmp(left_name, right_name) > 0) {
 257                 char *tmp = left_name;
 258                 left_name = right_name;
 259                 right_name = tmp;
 260                 comparison = flip_op(comparison);
 261         }
 262         snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
 263         state = &compare_states[comparison];
 264
 265         set_state(compare_id, state_name, NULL, state);
 266         save_link(left, state_name);
 267         save_link(right, state_name);
 268 free:
 269         free_string(left_name);
 270         free_string(right_name);
 271
 272 }
 273
 274 static void match_assign_add(struct expression *expr)
 275 {
 276         struct expression *right;
 277         struct expression *r_left, *r_right;
 278         sval_t left_tmp, right_tmp;
 279
 280         right = strip_expr(expr->right);
 281         r_left = strip_expr(right->left);
 282         r_right = strip_expr(right->right);
 283
 284         if (!is_capped(expr->left)) {
 285                 get_absolute_max(r_left, &left_tmp);
 286                 get_absolute_max(r_right, &right_tmp);
 287                 if (sval_binop_overflows(left_tmp, '+', right_tmp))
 288                         return;
 289         }
 290
 291         get_absolute_min(r_left, &left_tmp);
 292         if (sval_is_negative(left_tmp))
 293                 return;
 294         get_absolute_min(r_right, &right_tmp);
 295         if (sval_is_negative(right_tmp))
 296                 return;
 297
 298         if (left_tmp.value == 0)
 299                 add_comparison(expr->left, SPECIAL_GTE, r_right);
 300         else
 301                 add_comparison(expr->left, '>', r_right);
 302
 303         if (right_tmp.value == 0)
 304                 add_comparison(expr->left, SPECIAL_GTE, r_left);
 305         else
 306                 add_comparison(expr->left, '>', r_left);
 307 }
 308
 309 static void match_assign_sub(struct expression *expr)
 310 {
 311         struct expression *right;
 312         struct expression *r_left, *r_right;
 313         int comparison;
 314         sval_t min;
 315
 316         right = strip_expr(expr->right);
 317         r_left = strip_expr(right->left);
 318         r_right = strip_expr(right->right);
 319
 320         if (get_absolute_min(r_right, &min) && sval_is_negative(min))
 321                 return;
 322
 323         comparison = get_comparison(r_left, r_right);
 324
 325         switch (comparison) {
 326         case '>':
 327         case SPECIAL_GTE:
 328                 if (implied_not_equal(r_right, 0))
 329                         add_comparison(expr->left, '>', r_left);
 330                 else
 331                         add_comparison(expr->left, SPECIAL_GTE, r_left);
 332                 return;
 333         }
 334 }
 335
 336 static void match_binop_assign(struct expression *expr)
 337 {
 338         struct expression *right;
 339
 340         right = strip_expr(expr->right);
 341         if (right->op == '+')
 342                 match_assign_add(expr);
 343         if (right->op == '-')
 344                 match_assign_sub(expr);
 345 }
 346
 347 static void match_normal_assign(struct expression *expr)
 348 {
 349         add_comparison(expr->left, SPECIAL_EQUAL, expr->right);
 350 }
 351
 352 static void match_assign(struct expression *expr)
 353 {
 354         struct expression *right;
 355
 356         right = strip_expr(expr->right);
 357         if (right->type == EXPR_BINOP)
 358                 match_binop_assign(expr);
 359         else
 360                 match_normal_assign(expr);
 361 }
 362
 363 int get_comparison(struct expression *a, struct expression *b)
 364 {
 365         char *one = NULL;
 366         char *two = NULL;
 367         char buf[256];
 368         struct smatch_state *state;
 369         int invert = 0;
 370         int ret = 0;
 371
 372         one = expr_to_var(a);
 373         if (!one)
 374                 goto free;
 375         two = expr_to_var(b);
 376         if (!two)
 377                 goto free;
 378
 379         if (strcmp(one, two) > 0) {
 380                 char *tmp = one;
 381
 382                 one = two;
 383                 two = tmp;
 384                 invert = 1;
 385         }
 386
 387         snprintf(buf, sizeof(buf), "%s vs %s", one, two);
 388         state = get_state(compare_id, buf, NULL);
 389         if (state)
 390                 ret = PTR_INT(state->data);
 391
 392         if (invert)
 393                 ret = flip_op(ret);
 394
 395 free:
 396         free_string(one);
 397         free_string(two);
 398         return ret;
 399
 400 }
 401
 402 void register_comparison(int id)
 403 {
 404         compare_id = id;
 405         add_hook(&match_logic, CONDITION_HOOK);
 406         add_hook(&match_assign, ASSIGNMENT_HOOK);
 407 }
 408
 409 void register_comparison_links(int id)
 410 {
 411         link_id = id;
 412         add_merge_hook(link_id, &merge_func);
 413         add_modification_hook(link_id, &clear_links);
 414 }