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 /*
  43  * set_equiv() is only used for assignments where we set one variable
  44  * equal to the other.  a = b;.  It's not used for if conditions where
  45  * a == b.
  46  */
  47 void set_equiv(struct expression *left, struct expression *right)
  48 {
  49         struct sm_state *right_sm;
  50         struct smatch_state *state;
  51         struct relation *rel;
  52         char *left_name;
  53         struct symbol *left_sym;
  54
  55         left_name = get_variable_from_expr(left, &left_sym);
  56         if (!left_name || !left_sym)
  57                 goto free;
  58
  59         right_sm = get_sm_state_expr(SMATCH_EXTRA, right);
  60         if (!right_sm)
  61                 right_sm = set_state_expr(SMATCH_EXTRA, right, extra_undefined());
  62         if (!right_sm)
  63                 return;
  64
  65         remove_from_equiv(left_name, left_sym);
  66
  67         state = clone_estate(right_sm->state);
  68         if (!estate_related(state))
  69                 add_equiv(state, right_sm->name, right_sm->sym);
  70         add_equiv(state, left_name, left_sym);
  71
  72         FOR_EACH_PTR(estate_related(state), rel) {
  73                 struct sm_state *new_sm;
  74
  75                 new_sm = clone_sm(right_sm);
  76                 new_sm->name = rel->name;
  77                 new_sm->sym = rel->sym;
  78                 new_sm->state = state;
  79                 __set_sm(new_sm);
  80         } END_FOR_EACH_PTR(rel);
  81 free:
  82         free_string(left_name);
  83 }
  84
  85 static struct relation *alloc_relation(int op, const char *name, struct symbol *sym)
  86 {
  87         struct relation *tmp;
  88
  89         tmp = __alloc_relation(0);
  90         tmp->op = op;
  91         tmp->name = alloc_string(name);
  92         tmp->sym = sym;
  93         return tmp;
  94 }
  95
  96 struct related_list *clone_related_list(struct related_list *related)
  97 {
  98         struct relation *rel;
  99         struct related_list *to_list = NULL;
 100
 101         FOR_EACH_PTR(related, rel) {
 102                 add_ptr_list(&to_list, rel);
 103         } END_FOR_EACH_PTR(rel);
 104
 105         return to_list;
 106 }
 107
 108 static int cmp_relation(struct relation *a, struct relation *b)
 109 {
 110         int ret;
 111
 112         if (a == b)
 113                 return 0;
 114
 115         if (a->op > b->op)
 116                 return -1;
 117         if (a->op < b->op)
 118                 return 1;
 119
 120         if (a->sym > b->sym)
 121                 return -1;
 122         if (a->sym < b->sym)
 123                 return 1;
 124
 125         ret = strcmp(a->name, b->name);
 126         if (ret)
 127                 return ret;
 128
 129         return 0;
 130
 131 }
 132
 133 struct related_list *get_shared_relations(struct related_list *one,
 134                                               struct related_list *two)
 135 {
 136         struct related_list *ret = NULL;
 137         struct relation *one_rel;
 138         struct relation *two_rel;
 139
 140         PREPARE_PTR_LIST(one, one_rel);
 141         PREPARE_PTR_LIST(two, two_rel);
 142         for (;;) {
 143                 if (!one_rel || !two_rel)
 144                         break;
 145                 if (cmp_relation(one_rel, two_rel) < 0) {
 146                         NEXT_PTR_LIST(one_rel);
 147                 } else if (cmp_relation(one_rel, two_rel) == 0) {
 148                         add_ptr_list(&ret, one_rel);
 149                         NEXT_PTR_LIST(one_rel);
 150                         NEXT_PTR_LIST(two_rel);
 151                 } else {
 152                         NEXT_PTR_LIST(two_rel);
 153                 }
 154         }
 155         FINISH_PTR_LIST(two_rel);
 156         FINISH_PTR_LIST(one_rel);
 157
 158         return ret;
 159 }
 160
 161 static void debug_addition(struct related_list *rlist, int op, const char *name)
 162 {
 163         struct relation *tmp;
 164
 165         if (!option_debug_related)
 166                 return;
 167
 168         sm_prefix();
 169         sm_printf("(");
 170         FOR_EACH_PTR(rlist, tmp) {
 171                 sm_printf("%s %s ", show_special(tmp->op), tmp->name);
 172         } END_FOR_EACH_PTR(tmp);
 173         sm_printf(") <-- %s %s\n", show_special(op), name);
 174 }
 175
 176 static void add_related(struct related_list **rlist, int op, const char *name, struct symbol *sym)
 177 {
 178         struct relation *rel;
 179         struct relation *new;
 180         struct relation tmp = {
 181                 .op = op,
 182                 .name = (char *)name,
 183                 .sym = sym
 184         };
 185
 186         debug_addition(*rlist, op, name);
 187
 188         FOR_EACH_PTR(*rlist, rel) {
 189                 if (cmp_relation(rel, &tmp) < 0)
 190                         continue;
 191                 if (cmp_relation(rel, &tmp) == 0)
 192                         return;
 193                 new = alloc_relation(op, name, sym);
 194                 INSERT_CURRENT(new, rel);
 195                 return;
 196         } END_FOR_EACH_PTR(rel);
 197         new = alloc_relation(op, name, sym);
 198         add_ptr_list(rlist, new);
 199 }
 200
 201 void del_related(struct smatch_state *state, int op, const char *name, struct symbol *sym)
 202 {
 203         struct relation *tmp;
 204
 205         FOR_EACH_PTR(estate_related(state), tmp) {
 206                 if (tmp->sym < sym || strcmp(tmp->name, name) < 0)
 207                         continue;
 208                 if (tmp->sym == sym && !strcmp(tmp->name, name)) {
 209                         DELETE_CURRENT_PTR(tmp);
 210                         continue;
 211                 }
 212                 return;
 213         } END_FOR_EACH_PTR(tmp);
 214 }
 215
 216 void add_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
 217 {
 218         struct data_info *dinfo = get_dinfo(state);
 219
 220         add_related(&dinfo->related, SPECIAL_EQUAL, name, sym);
 221 }
 222
 223 static void del_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
 224 {
 225         del_related(state, SPECIAL_EQUAL, name, sym);
 226 }
 227
 228 void remove_from_equiv(const char *name, struct symbol *sym)
 229 {
 230         struct sm_state *orig_sm;
 231         struct relation *rel;
 232         struct smatch_state *state;
 233         struct related_list *to_update;
 234
 235         // FIXME equiv => related
 236         orig_sm = get_sm_state(SMATCH_EXTRA, name, sym);
 237         if (!orig_sm || !get_dinfo(orig_sm->state)->related)
 238                 return;
 239
 240         state = clone_estate(orig_sm->state);
 241         del_equiv(state, name, sym);
 242         to_update = get_dinfo(state)->related;
 243         if (ptr_list_size((struct ptr_list *)get_dinfo(state)->related) == 1)
 244                 get_dinfo(state)->related = NULL;
 245
 246         FOR_EACH_PTR(to_update, rel) {
 247                 struct sm_state *new_sm;
 248
 249                 new_sm = clone_sm(orig_sm);
 250                 new_sm->name = rel->name;
 251                 new_sm->sym = rel->sym;
 252                 new_sm->state = state;
 253                 __set_sm(new_sm);
 254         } END_FOR_EACH_PTR(rel);
 255 }
 256
 257 void remove_from_equiv_expr(struct expression *expr)
 258 {
 259         char *name;
 260         struct symbol *sym;
 261
 262         name = get_variable_from_expr(expr, &sym);
 263         if (!name || !sym)
 264                 goto free;
 265         remove_from_equiv(name, sym);
 266 free:
 267         free_string(name);
 268 }
 269
 270 void add_constrain_expr(struct expression *left, int op, struct expression *right)
 271 {
 272
 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 }