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 smatch_state *state, 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(estate_related(state), 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 void add_related(struct smatch_state *state, int op, const char *name, struct symbol *sym)
 177 {
 178         struct data_info *dinfo;
 179         struct relation *tmp;
 180         struct relation *new;
 181
 182         debug_addition(state, op, name);
 183
 184         dinfo = get_dinfo(state);
 185         FOR_EACH_PTR(dinfo->related, tmp) {
 186                 if (tmp->op < op || tmp->sym < sym || strcmp(tmp->name, name) < 0)
 187                         continue;
 188                 if (tmp->op == op && tmp->sym == sym && !strcmp(tmp->name, name))
 189                         return;
 190                 new = alloc_relation(op, name, sym);
 191                 INSERT_CURRENT(new, tmp);
 192                 return;
 193         } END_FOR_EACH_PTR(tmp);
 194         new = alloc_relation(op, name, sym);
 195         add_ptr_list(&dinfo->related, new);
 196 }
 197
 198 void del_related(struct smatch_state *state, int op, const char *name, struct symbol *sym)
 199 {
 200         struct relation *tmp;
 201
 202         FOR_EACH_PTR(estate_related(state), tmp) {
 203                 if (tmp->sym < sym || strcmp(tmp->name, name) < 0)
 204                         continue;
 205                 if (tmp->sym == sym && !strcmp(tmp->name, name)) {
 206                         DELETE_CURRENT_PTR(tmp);
 207                         continue;
 208                 }
 209                 return;
 210         } END_FOR_EACH_PTR(tmp);
 211 }
 212
 213 void add_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
 214 {
 215         add_related(state, SPECIAL_EQUAL, name, sym);
 216 }
 217
 218 static void del_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
 219 {
 220         del_related(state, SPECIAL_EQUAL, name, sym);
 221 }
 222
 223 void remove_from_equiv(const char *name, struct symbol *sym)
 224 {
 225         struct sm_state *orig_sm;
 226         struct relation *rel;
 227         struct smatch_state *state;
 228         struct related_list *to_update;
 229
 230         // FIXME equiv => related
 231         orig_sm = get_sm_state(SMATCH_EXTRA, name, sym);
 232         if (!orig_sm || !get_dinfo(orig_sm->state)->related)
 233                 return;
 234
 235         state = clone_estate(orig_sm->state);
 236         del_equiv(state, name, sym);
 237         to_update = get_dinfo(state)->related;
 238         if (ptr_list_size((struct ptr_list *)get_dinfo(state)->related) == 1)
 239                 get_dinfo(state)->related = NULL;
 240
 241         FOR_EACH_PTR(to_update, rel) {
 242                 struct sm_state *new_sm;
 243
 244                 new_sm = clone_sm(orig_sm);
 245                 new_sm->name = rel->name;
 246                 new_sm->sym = rel->sym;
 247                 new_sm->state = state;
 248                 __set_sm(new_sm);
 249         } END_FOR_EACH_PTR(rel);
 250 }
 251
 252 void remove_from_equiv_expr(struct expression *expr)
 253 {
 254         char *name;
 255         struct symbol *sym;
 256
 257         name = get_variable_from_expr(expr, &sym);
 258         if (!name || !sym)
 259                 goto free;
 260         remove_from_equiv(name, sym);
 261 free:
 262         free_string(name);
 263 }
 264
 265 void add_constrain_expr(struct expression *left, int op, struct expression *right)
 266 {
 267
 268 }
 269
 270 void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state)
 271 {
 272         struct relation *rel;
 273         struct smatch_state *estate;
 274
 275         estate = get_state_expr(SMATCH_EXTRA, expr);
 276
 277         if (!estate)
 278                 return;
 279
 280         FOR_EACH_PTR(get_dinfo(estate)->related, rel) {
 281                 if (rel->op != SPECIAL_EQUAL)
 282                         continue;
 283                 set_state(id, rel->name, rel->sym, state);
 284         } END_FOR_EACH_PTR(rel);
 285 }