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 struct related_list *get_shared_relations(struct related_list *one,
  90                                               struct related_list *two)
  91 {
  92         struct related_list *ret = NULL;
  93         struct relation *one_rel;
  94         struct relation *two_rel;
  95
  96         PREPARE_PTR_LIST(one, one_rel);
  97         PREPARE_PTR_LIST(two, two_rel);
  98         for (;;) {
  99                 if (!one_rel || !two_rel)
 100                         break;
 101                 if (cmp_relation(one_rel, two_rel) < 0) {
 102                         NEXT_PTR_LIST(one_rel);
 103                 } else if (cmp_relation(one_rel, two_rel) == 0) {
 104                         add_ptr_list(&ret, one_rel);
 105                         NEXT_PTR_LIST(one_rel);
 106                         NEXT_PTR_LIST(two_rel);
 107                 } else {
 108                         NEXT_PTR_LIST(two_rel);
 109                 }
 110         }
 111         FINISH_PTR_LIST(two_rel);
 112         FINISH_PTR_LIST(one_rel);
 113
 114         return ret;
 115 }
 116
 117 static void debug_addition(struct related_list *rlist, int op, const char *name)
 118 {
 119         struct relation *tmp;
 120
 121         if (!option_debug_related)
 122                 return;
 123
 124         sm_prefix();
 125         sm_printf("(");
 126         FOR_EACH_PTR(rlist, tmp) {
 127                 sm_printf("%s %s ", show_special(tmp->op), tmp->name);
 128         } END_FOR_EACH_PTR(tmp);
 129         sm_printf(") <-- %s %s\n", show_special(op), name);
 130 }
 131
 132 static void add_related(struct related_list **rlist, int op, const char *name, struct symbol *sym)
 133 {
 134         struct relation *rel;
 135         struct relation *new;
 136         struct relation tmp = {
 137                 .op = op,
 138                 .name = (char *)name,
 139                 .sym = sym
 140         };
 141
 142         debug_addition(*rlist, op, name);
 143
 144         FOR_EACH_PTR(*rlist, rel) {
 145                 if (cmp_relation(rel, &tmp) < 0)
 146                         continue;
 147                 if (cmp_relation(rel, &tmp) == 0)
 148                         return;
 149                 new = alloc_relation(op, name, sym);
 150                 INSERT_CURRENT(new, rel);
 151                 return;
 152         } END_FOR_EACH_PTR(rel);
 153         new = alloc_relation(op, name, sym);
 154         add_ptr_list(rlist, new);
 155 }
 156
 157 void del_related(struct smatch_state *state, int op, const char *name, struct symbol *sym)
 158 {
 159         struct relation *tmp;
 160         struct relation remove = {
 161                 .op = op,
 162                 .name = (char *)name,
 163                 .sym = sym,
 164         };
 165
 166         FOR_EACH_PTR(estate_related(state), tmp) {
 167                 if (cmp_relation(tmp, &remove) < 0)
 168                         continue;
 169                 if (cmp_relation(tmp, &remove) == 0) {
 170                         DELETE_CURRENT_PTR(tmp);
 171                         return;
 172                 }
 173                 return;
 174         } END_FOR_EACH_PTR(tmp);
 175 }
 176
 177 static void del_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
 178 {
 179         del_related(state, SPECIAL_EQUAL, name, sym);
 180 }
 181
 182 void remove_from_equiv(const char *name, struct symbol *sym)
 183 {
 184         struct sm_state *orig_sm;
 185         struct relation *rel;
 186         struct smatch_state *state;
 187         struct related_list *to_update;
 188
 189         // FIXME equiv => related
 190         orig_sm = get_sm_state(SMATCH_EXTRA, name, sym);
 191         if (!orig_sm || !get_dinfo(orig_sm->state)->related)
 192                 return;
 193
 194         state = clone_estate(orig_sm->state);
 195         del_equiv(state, name, sym);
 196         to_update = get_dinfo(state)->related;
 197         if (ptr_list_size((struct ptr_list *)get_dinfo(state)->related) == 1)
 198                 get_dinfo(state)->related = NULL;
 199
 200         FOR_EACH_PTR(to_update, rel) {
 201                 struct sm_state *new_sm;
 202
 203                 new_sm = clone_sm(orig_sm);
 204                 new_sm->name = rel->name;
 205                 new_sm->sym = rel->sym;
 206                 new_sm->state = state;
 207                 __set_sm(new_sm);
 208         } END_FOR_EACH_PTR(rel);
 209 }
 210
 211 void remove_from_equiv_expr(struct expression *expr)
 212 {
 213         char *name;
 214         struct symbol *sym;
 215
 216         name = get_variable_from_expr(expr, &sym);
 217         if (!name || !sym)
 218                 goto free;
 219         remove_from_equiv(name, sym);
 220 free:
 221         free_string(name);
 222 }
 223
 224 void set_related(struct smatch_state *estate, struct related_list *rlist)
 225 {
 226         if (!estate_related(estate) && !rlist)
 227                 return;
 228         get_dinfo(estate)->related = rlist;
 229 }
 230
 231 /*
 232  * set_equiv() is only used for assignments where we set one variable
 233  * equal to the other.  a = b;.  It's not used for if conditions where
 234  * a == b.
 235  */
 236 void set_equiv(struct expression *left, struct expression *right)
 237 {
 238         struct sm_state *right_sm;
 239         struct smatch_state *state;
 240         struct relation *rel;
 241         char *left_name;
 242         struct symbol *left_sym;
 243         struct related_list *rlist;
 244
 245         left_name = get_variable_from_expr(left, &left_sym);
 246         if (!left_name || !left_sym)
 247                 goto free;
 248
 249         right_sm = get_sm_state_expr(SMATCH_EXTRA, right);
 250         if (!right_sm)
 251                 right_sm = set_state_expr(SMATCH_EXTRA, right, extra_undefined(get_type(right)));
 252         if (!right_sm)
 253                 goto free;
 254
 255         remove_from_equiv(left_name, left_sym);
 256
 257         rlist = clone_related_list(estate_related(right_sm->state));
 258         add_related(&rlist, SPECIAL_EQUAL, right_sm->name, right_sm->sym);
 259         add_related(&rlist, SPECIAL_EQUAL, left_name, left_sym);
 260
 261         state = clone_estate(right_sm->state);
 262         get_dinfo(state)->related = rlist;
 263
 264         FOR_EACH_PTR(rlist, rel) {
 265                 struct sm_state *new_sm;
 266
 267                 new_sm = clone_sm(right_sm);
 268                 new_sm->name = rel->name;
 269                 new_sm->sym = rel->sym;
 270                 new_sm->state = state;
 271                 __set_sm(new_sm);
 272         } END_FOR_EACH_PTR(rel);
 273 free:
 274         free_string(left_name);
 275 }
 276
 277 void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state)
 278 {
 279         struct relation *rel;
 280         struct smatch_state *estate;
 281
 282         estate = get_state_expr(SMATCH_EXTRA, expr);
 283
 284         if (!estate)
 285                 return;
 286
 287         FOR_EACH_PTR(get_dinfo(estate)->related, rel) {
 288                 if (rel->op != SPECIAL_EQUAL)
 289                         continue;
 290                 set_state(id, rel->name, rel->sym, state);
 291         } END_FOR_EACH_PTR(rel);
 292 }