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_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 insert_string(struct string_list **str_list, char *new)
 160 {
 161         char *tmp;
 162
 163         FOR_EACH_PTR(*str_list, tmp) {
 164                 if (strcmp(tmp, new) < 0)
 165                         continue;
 166                 else if (strcmp(tmp, new) == 0) {
 167                         return;
 168                 } else {
 169                         INSERT_CURRENT(new, tmp);
 170                         return;
 171                 }
 172         } END_FOR_EACH_PTR(tmp);
 173         add_ptr_list(str_list, new);
 174 }
 175
 176 struct string_list *clone_str_list(struct string_list *orig)
 177 {
 178         char *tmp;
 179         struct string_list *ret = NULL;
 180
 181         FOR_EACH_PTR(orig, tmp) {
 182                 add_ptr_list(&ret, tmp);
 183         } END_FOR_EACH_PTR(tmp);
 184         return ret;
 185 }
 186
 187 static struct string_list *combine_string_lists(struct string_list *one, struct string_list *two)
 188 {
 189         struct string_list *ret;
 190         char *tmp;
 191
 192         ret = clone_str_list(one);
 193         FOR_EACH_PTR(two, tmp) {
 194                 insert_string(&ret, tmp);
 195         } END_FOR_EACH_PTR(tmp);
 196         return ret;
 197 }
 198
 199 static struct smatch_state *merge_func(struct smatch_state *s1, struct smatch_state *s2)
 200 {
 201         struct smatch_state *ret;
 202         struct string_list *links;
 203
 204         links = combine_string_lists(s1->data, s2->data);
 205         ret = alloc_link_state(links);
 206         return ret;
 207 }
 208
 209 static void save_link(struct expression *expr, char *link)
 210 {
 211         struct smatch_state *old_state, *new_state;
 212         struct string_list *links;
 213         char *new;
 214
 215         old_state = get_state_expr(link_id, expr);
 216         if (old_state)
 217                 links = clone_str_list(old_state->data);
 218         else
 219                 links = NULL;
 220
 221         new = alloc_sname(link);
 222         insert_string(&links, new);
 223
 224         new_state = alloc_link_state(links);
 225         set_state_expr(link_id, expr, new_state);
 226 }
 227
 228 static void clear_links(struct sm_state *sm)
 229 {
 230         struct string_list *links;
 231         char *tmp;
 232
 233         links = sm->state->data;
 234
 235         FOR_EACH_PTR(links, tmp) {
 236                 set_state(compare_id, tmp, NULL, &undefined);
 237         } END_FOR_EACH_PTR(tmp);
 238         set_state(link_id, sm->name, sm->sym, &undefined);
 239 }
 240
 241 static void match_logic(struct expression *expr)
 242 {
 243         char *left = NULL;
 244         char *right = NULL;
 245         struct symbol *left_sym, *right_sym;
 246         int op, false_op;
 247         struct smatch_state *true_state, *false_state;
 248         char state_name[256];
 249
 250         if (expr->type != EXPR_COMPARE)
 251                 return;
 252         left = expr_to_var_sym(expr->left, &left_sym);
 253         if (!left || !left_sym)
 254                 goto free;
 255         right = expr_to_var_sym(expr->right, &right_sym);
 256         if (!right || !right_sym)
 257                 goto free;
 258
 259         if (strcmp(left, right) > 0) {
 260                 char *tmp = left;
 261                 left = right;
 262                 right = tmp;
 263                 op = flip_op(expr->op);
 264         } else {
 265                 op = expr->op;
 266         }
 267         false_op = falsify_op(op);
 268         snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
 269         true_state = &compare_states[op];
 270         false_state = &compare_states[false_op];
 271
 272         set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
 273         save_link(expr->left, state_name);
 274         save_link(expr->right, state_name);
 275 free:
 276         free_string(left);
 277         free_string(right);
 278 }
 279
 280 int get_comparison(struct expression *a, struct expression *b)
 281 {
 282         char *one = NULL;
 283         char *two = NULL;
 284         char buf[256];
 285         struct smatch_state *state;
 286         int invert = 0;
 287         int ret = 0;
 288
 289         one = expr_to_var(a);
 290         if (!one)
 291                 goto free;
 292         two = expr_to_var(b);
 293         if (!two)
 294                 goto free;
 295
 296         if (strcmp(one, two) > 0) {
 297                 char *tmp = one;
 298
 299                 one = two;
 300                 two = tmp;
 301                 invert = 1;
 302         }
 303
 304         snprintf(buf, sizeof(buf), "%s vs %s", one, two);
 305         state = get_state(compare_id, buf, NULL);
 306         if (state)
 307                 ret = PTR_INT(state->data);
 308
 309         if (invert)
 310                 ret = flip_op(ret);
 311
 312 free:
 313         free_string(one);
 314         free_string(two);
 315         return ret;
 316
 317 }
 318
 319 void register_comparison(int id)
 320 {
 321         compare_id = id;
 322         add_hook(&match_logic, CONDITION_HOOK);
 323 }
 324
 325 void register_comparison_links(int id)
 326 {
 327         link_id = id;
 328         add_merge_hook(link_id, &merge_func);
 329         add_modification_hook(link_id, &clear_links);
 330 }