smatch_constraints.c

   1 /*
   2  * sparse/smatch_constraints.c
   3  *
   4  * Copyright (C) 2010 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * smatch_constraints.c is for tracking how variables are related
  12  *
  13  * if (a == b) {
  14  * if (a > b) {
  15  * if (a != b) {
  16  *
  17  * This is stored in a field in the smatch_extra dinfo.
  18  *
  19  * Normally the way that variables become related is through a
  20  * condition and you say:  add_constraint_expr(left, '<', right);
  21  * The other way it can happen is if you have an assignment:
  22  * set_equiv(left, right);
  23  *
  24  * One two variables "a" and "b" are related if then if we find
  25  * that "a" is greater than 0 we need to update "b".
  26  *
  27  * When a variable gets modified all the old relationships are
  28  * deleted.  remove_contraints(expr);
  29  *
  30  * Also we need an is_true_constraint(left, '<', right) and
  31  * is_false_constraint (left, '<', right).  This is used by
  32  * smatch_implied.
  33  *
  34  */
  35
  36 #include "smatch.h"
  37 #include "smatch_slist.h"
  38 #include "smatch_extra.h"
  39
  40 ALLOCATOR(relation, "related variables");
  41
  42 static struct relation *alloc_relation(int op, const char *name, struct symbol *sym)
  43 {
  44         struct relation *tmp;
  45
  46         tmp = __alloc_relation(0);
  47         tmp->op = op;
  48         tmp->name = alloc_string(name);
  49         tmp->sym = sym;
  50         return tmp;
  51 }
  52
  53 struct related_list *clone_related_list(struct related_list *related)
  54 {
  55         struct relation *rel;
  56         struct related_list *to_list = NULL;
  57
  58         FOR_EACH_PTR(related, rel) {
  59                 add_ptr_list(&to_list, rel);
  60         } END_FOR_EACH_PTR(rel);
  61
  62         return to_list;
  63 }
  64
  65 static int cmp_relation(struct relation *a, struct relation *b)
  66 {
  67         int ret;
  68
  69         if (a == b)
  70                 return 0;
  71
  72         if (a->op > b->op)
  73                 return -1;
  74         if (a->op < b->op)
  75                 return 1;
  76
  77         if (a->sym > b->sym)
  78                 return -1;
  79         if (a->sym < b->sym)
  80                 return 1;
  81
  82         ret = strcmp(a->name, b->name);
  83         if (ret)
  84                 return ret;
  85
  86         return 0;
  87
  88 }
  89
  90 struct related_list *get_shared_relations(struct related_list *one,
  91                                               struct related_list *two)
  92 {
  93         struct related_list *ret = NULL;
  94         struct relation *one_rel;
  95         struct relation *two_rel;
  96
  97         PREPARE_PTR_LIST(one, one_rel);
  98         PREPARE_PTR_LIST(two, two_rel);
  99         for (;;) {
 100                 if (!one_rel || !two_rel)
 101                         break;
 102                 if (cmp_relation(one_rel, two_rel) < 0) {
 103                         NEXT_PTR_LIST(one_rel);
 104                 } else if (cmp_relation(one_rel, two_rel) == 0) {
 105                         add_ptr_list(&ret, one_rel);
 106                         NEXT_PTR_LIST(one_rel);
 107                         NEXT_PTR_LIST(two_rel);
 108                 } else {
 109                         NEXT_PTR_LIST(two_rel);
 110                 }
 111         }
 112         FINISH_PTR_LIST(two_rel);
 113         FINISH_PTR_LIST(one_rel);
 114
 115         return ret;
 116 }
 117
 118 static void debug_addition(struct related_list *rlist, int op, const char *name)
 119 {
 120         struct relation *tmp;
 121
 122         if (!option_debug_related)
 123                 return;
 124
 125         sm_prefix();
 126         sm_printf("(");
 127         FOR_EACH_PTR(rlist, tmp) {
 128                 sm_printf("%s %s ", show_special(tmp->op), tmp->name);
 129         } END_FOR_EACH_PTR(tmp);
 130         sm_printf(") <-- %s %s\n", show_special(op), name);
 131 }
 132
 133 static void add_related(struct related_list **rlist, int op, const char *name, struct symbol *sym)
 134 {
 135         struct relation *rel;
 136         struct relation *new;
 137         struct relation tmp = {
 138                 .op = op,
 139                 .name = (char *)name,
 140                 .sym = sym
 141         };
 142
 143         debug_addition(*rlist, op, name);
 144
 145         FOR_EACH_PTR(*rlist, rel) {
 146                 if (cmp_relation(rel, &tmp) < 0)
 147                         continue;
 148                 if (cmp_relation(rel, &tmp) == 0)
 149                         return;
 150                 new = alloc_relation(op, name, sym);
 151                 INSERT_CURRENT(new, rel);
 152                 return;
 153         } END_FOR_EACH_PTR(rel);
 154         new = alloc_relation(op, name, sym);
 155         add_ptr_list(rlist, new);
 156 }
 157
 158 void del_related(struct smatch_state *state, int op, const char *name, struct symbol *sym)
 159 {
 160         struct relation *tmp;
 161
 162         FOR_EACH_PTR(estate_related(state), tmp) {
 163                 if (tmp->sym < sym || strcmp(tmp->name, name) < 0)
 164                         continue;
 165                 if (tmp->sym == sym && !strcmp(tmp->name, name)) {
 166                         DELETE_CURRENT_PTR(tmp);
 167                         continue;
 168                 }
 169                 return;
 170         } END_FOR_EACH_PTR(tmp);
 171 }
 172
 173 static void del_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
 174 {
 175         del_related(state, SPECIAL_EQUAL, name, sym);
 176 }
 177
 178 void remove_from_equiv(const char *name, struct symbol *sym)
 179 {
 180         struct sm_state *orig_sm;
 181         struct relation *rel;
 182         struct smatch_state *state;
 183         struct related_list *to_update;
 184
 185         // FIXME equiv => related
 186         orig_sm = get_sm_state(SMATCH_EXTRA, name, sym);
 187         if (!orig_sm || !get_dinfo(orig_sm->state)->related)
 188                 return;
 189
 190         state = clone_estate(orig_sm->state);
 191         del_equiv(state, name, sym);
 192         to_update = get_dinfo(state)->related;
 193         if (ptr_list_size((struct ptr_list *)get_dinfo(state)->related) == 1)
 194                 get_dinfo(state)->related = NULL;
 195
 196         FOR_EACH_PTR(to_update, rel) {
 197                 struct sm_state *new_sm;
 198
 199                 new_sm = clone_sm(orig_sm);
 200                 new_sm->name = rel->name;
 201                 new_sm->sym = rel->sym;
 202                 new_sm->state = state;
 203                 __set_sm(new_sm);
 204         } END_FOR_EACH_PTR(rel);
 205 }
 206
 207 void remove_from_equiv_expr(struct expression *expr)
 208 {
 209         char *name;
 210         struct symbol *sym;
 211
 212         name = get_variable_from_expr(expr, &sym);
 213         if (!name || !sym)
 214                 goto free;
 215         remove_from_equiv(name, sym);
 216 free:
 217         free_string(name);
 218 }
 219
 220 void set_related(struct smatch_state **estate, struct related_list *rlist)
 221 {
 222         if (!estate_related(*estate) && !rlist)
 223                 return;
 224         if (*estate == &estate_undefined)
 225                 *estate = clone_estate(&estate_undefined);
 226         get_dinfo(*estate)->related = rlist;
 227 }
 228
 229 /*
 230  * set_equiv() is only used for assignments where we set one variable
 231  * equal to the other.  a = b;.  It's not used for if conditions where
 232  * a == b.
 233  */
 234 void set_equiv(struct expression *left, struct expression *right)
 235 {
 236         struct sm_state *right_sm;
 237         struct smatch_state *state;
 238         struct relation *rel;
 239         char *left_name;
 240         struct symbol *left_sym;
 241         struct related_list *rlist;
 242
 243         left_name = get_variable_from_expr(left, &left_sym);
 244         if (!left_name || !left_sym)
 245                 goto free;
 246
 247         right_sm = get_sm_state_expr(SMATCH_EXTRA, right);
 248         if (!right_sm)
 249                 right_sm = set_state_expr(SMATCH_EXTRA, right, extra_undefined());
 250         if (!right_sm)
 251                 return;
 252
 253         remove_from_equiv(left_name, left_sym);
 254
 255         rlist = clone_related_list(estate_related(right_sm->state));
 256         add_related(&rlist, SPECIAL_EQUAL, right_sm->name, right_sm->sym);
 257         add_related(&rlist, SPECIAL_EQUAL, left_name, left_sym);
 258
 259         state = clone_estate(right_sm->state);
 260         get_dinfo(state)->related = rlist;
 261
 262         FOR_EACH_PTR(rlist, rel) {
 263                 struct sm_state *new_sm;
 264
 265                 new_sm = clone_sm(right_sm);
 266                 new_sm->name = rel->name;
 267                 new_sm->sym = rel->sym;
 268                 new_sm->state = state;
 269                 __set_sm(new_sm);
 270         } END_FOR_EACH_PTR(rel);
 271 free:
 272         free_string(left_name);
 273 }
 274
 275 void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state)
 276 {
 277         struct relation *rel;
 278         struct smatch_state *estate;
 279
 280         estate = get_state_expr(SMATCH_EXTRA, expr);
 281
 282         if (!estate)
 283                 return;
 284
 285         FOR_EACH_PTR(get_dinfo(estate)->related, rel) {
 286                 if (rel->op != SPECIAL_EQUAL)
 287                         continue;
 288                 set_state(id, rel->name, rel->sym, state);
 289         } END_FOR_EACH_PTR(rel);
 290 }