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 struct relation *get_common_relationship(struct smatch_state *state, int op,
 109                                         const char *name, struct symbol *sym)
 110 {
 111         struct relation *tmp;
 112
 113         // FIXME...
 114         // Find the common x < y and x <= y
 115         FOR_EACH_PTR(estate_related(state), tmp) {
 116                 if (tmp->op < op || tmp->sym < sym || strcmp(tmp->name, name) < 0)
 117                         continue;
 118                 if (tmp->op == op && tmp->sym == sym && !strcmp(tmp->name, name))
 119                         return tmp;
 120                 return NULL;
 121         } END_FOR_EACH_PTR(tmp);
 122         return NULL;
 123 }
 124
 125 static void debug_addition(struct smatch_state *state, int op, const char *name)
 126 {
 127         struct relation *tmp;
 128
 129         if (!option_debug_related)
 130                 return;
 131
 132         sm_prefix();
 133         sm_printf("(");
 134         FOR_EACH_PTR(estate_related(state), tmp) {
 135                 sm_printf("%s %s ", show_special(tmp->op), tmp->name);
 136         } END_FOR_EACH_PTR(tmp);
 137         sm_printf(") <-- %s %s\n", show_special(op), name);
 138 }
 139
 140 void add_related(struct smatch_state *state, int op, const char *name, struct symbol *sym)
 141 {
 142         struct data_info *dinfo;
 143         struct relation *tmp;
 144         struct relation *new;
 145
 146         debug_addition(state, op, name);
 147
 148         dinfo = get_dinfo(state);
 149         FOR_EACH_PTR(dinfo->related, tmp) {
 150                 if (tmp->op < op || tmp->sym < sym || strcmp(tmp->name, name) < 0)
 151                         continue;
 152                 if (tmp->op == op && tmp->sym == sym && !strcmp(tmp->name, name))
 153                         return;
 154                 new = alloc_relation(op, name, sym);
 155                 INSERT_CURRENT(new, tmp);
 156                 return;
 157         } END_FOR_EACH_PTR(tmp);
 158         new = alloc_relation(op, name, sym);
 159         add_ptr_list(&dinfo->related, new);
 160 }
 161
 162 void del_related(struct smatch_state *state, int op, const char *name, struct symbol *sym)
 163 {
 164         struct relation *tmp;
 165
 166         FOR_EACH_PTR(estate_related(state), tmp) {
 167                 if (tmp->sym < sym || strcmp(tmp->name, name) < 0)
 168                         continue;
 169                 if (tmp->sym == sym && !strcmp(tmp->name, name)) {
 170                         DELETE_CURRENT_PTR(tmp);
 171                         continue;
 172                 }
 173                 return;
 174         } END_FOR_EACH_PTR(tmp);
 175 }
 176
 177 void add_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
 178 {
 179         add_related(state, SPECIAL_EQUAL, name, sym);
 180 }
 181
 182 static void del_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
 183 {
 184         del_related(state, SPECIAL_EQUAL, name, sym);
 185 }
 186
 187 void remove_from_equiv(const char *name, struct symbol *sym)
 188 {
 189         struct sm_state *orig_sm;
 190         struct relation *rel;
 191         struct smatch_state *state;
 192         struct related_list *to_update;
 193
 194         // FIXME equiv => related
 195         orig_sm = get_sm_state(SMATCH_EXTRA, name, sym);
 196         if (!orig_sm || !get_dinfo(orig_sm->state)->related)
 197                 return;
 198
 199         state = clone_estate(orig_sm->state);
 200         del_equiv(state, name, sym);
 201         to_update = get_dinfo(state)->related;
 202         if (ptr_list_size((struct ptr_list *)get_dinfo(state)->related) == 1)
 203                 get_dinfo(state)->related = NULL;
 204
 205         FOR_EACH_PTR(to_update, rel) {
 206                 struct sm_state *new_sm;
 207
 208                 new_sm = clone_sm(orig_sm);
 209                 new_sm->name = rel->name;
 210                 new_sm->sym = rel->sym;
 211                 new_sm->state = state;
 212                 __set_sm(new_sm);
 213         } END_FOR_EACH_PTR(rel);
 214 }
 215
 216 void remove_from_equiv_expr(struct expression *expr)
 217 {
 218         char *name;
 219         struct symbol *sym;
 220
 221         name = get_variable_from_expr(expr, &sym);
 222         if (!name || !sym)
 223                 goto free;
 224         remove_from_equiv(name, sym);
 225 free:
 226         free_string(name);
 227 }
 228
 229 void add_constrain_expr(struct expression *left, int op, struct expression *right)
 230 {
 231
 232 }
 233
 234 void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state)
 235 {
 236         struct relation *rel;
 237         struct smatch_state *estate;
 238
 239         estate = get_state_expr(SMATCH_EXTRA, expr);
 240
 241         if (!estate)
 242                 return;
 243
 244         FOR_EACH_PTR(get_dinfo(estate)->related, rel) {
 245                 if (rel->op != SPECIAL_EQUAL)
 246                         continue;
 247                 set_state(id, rel->name, rel->sym, state);
 248         } END_FOR_EACH_PTR(rel);
 249 }