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
 161         FOR_EACH_PTR(estate_related(state), tmp) {
 162                 if (tmp->sym < sym || strcmp(tmp->name, name) < 0)
 163                         continue;
 164                 if (tmp->sym == sym && !strcmp(tmp->name, name)) {
 165                         DELETE_CURRENT_PTR(tmp);
 166                         continue;
 167                 }
 168                 return;
 169         } END_FOR_EACH_PTR(tmp);
 170 }
 171
 172 static void del_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
 173 {
 174         del_related(state, SPECIAL_EQUAL, name, sym);
 175 }
 176
 177 void remove_from_equiv(const char *name, struct symbol *sym)
 178 {
 179         struct sm_state *orig_sm;
 180         struct relation *rel;
 181         struct smatch_state *state;
 182         struct related_list *to_update;
 183
 184         // FIXME equiv => related
 185         orig_sm = get_sm_state(SMATCH_EXTRA, name, sym);
 186         if (!orig_sm || !get_dinfo(orig_sm->state)->related)
 187                 return;
 188
 189         state = clone_estate(orig_sm->state);
 190         del_equiv(state, name, sym);
 191         to_update = get_dinfo(state)->related;
 192         if (ptr_list_size((struct ptr_list *)get_dinfo(state)->related) == 1)
 193                 get_dinfo(state)->related = NULL;
 194
 195         FOR_EACH_PTR(to_update, rel) {
 196                 struct sm_state *new_sm;
 197
 198                 new_sm = clone_sm(orig_sm);
 199                 new_sm->name = rel->name;
 200                 new_sm->sym = rel->sym;
 201                 new_sm->state = state;
 202                 __set_sm(new_sm);
 203         } END_FOR_EACH_PTR(rel);
 204 }
 205
 206 void remove_from_equiv_expr(struct expression *expr)
 207 {
 208         char *name;
 209         struct symbol *sym;
 210
 211         name = get_variable_from_expr(expr, &sym);
 212         if (!name || !sym)
 213                 goto free;
 214         remove_from_equiv(name, sym);
 215 free:
 216         free_string(name);
 217 }
 218
 219 void set_related(struct smatch_state **estate, struct related_list *rlist)
 220 {
 221         if (!estate_related(*estate) && !rlist)
 222                 return;
 223         if (*estate == &estate_undefined)
 224                 *estate = clone_estate(&estate_undefined);
 225         get_dinfo(*estate)->related = rlist;
 226 }
 227
 228 /*
 229  * set_equiv() is only used for assignments where we set one variable
 230  * equal to the other.  a = b;.  It's not used for if conditions where
 231  * a == b.
 232  */
 233 void set_equiv(struct expression *left, struct expression *right)
 234 {
 235         struct sm_state *right_sm;
 236         struct smatch_state *state;
 237         struct relation *rel;
 238         char *left_name;
 239         struct symbol *left_sym;
 240         struct related_list *rlist;
 241
 242         left_name = get_variable_from_expr(left, &left_sym);
 243         if (!left_name || !left_sym)
 244                 goto free;
 245
 246         right_sm = get_sm_state_expr(SMATCH_EXTRA, right);
 247         if (!right_sm)
 248                 right_sm = set_state_expr(SMATCH_EXTRA, right, extra_undefined());
 249         if (!right_sm)
 250                 return;
 251
 252         remove_from_equiv(left_name, left_sym);
 253
 254         rlist = clone_related_list(estate_related(right_sm->state));
 255         add_related(&rlist, SPECIAL_EQUAL, right_sm->name, right_sm->sym);
 256         add_related(&rlist, SPECIAL_EQUAL, left_name, left_sym);
 257
 258         state = clone_estate(right_sm->state);
 259         get_dinfo(state)->related = rlist;
 260
 261         FOR_EACH_PTR(rlist, rel) {
 262                 struct sm_state *new_sm;
 263
 264                 new_sm = clone_sm(right_sm);
 265                 new_sm->name = rel->name;
 266                 new_sm->sym = rel->sym;
 267                 new_sm->state = state;
 268                 __set_sm(new_sm);
 269         } END_FOR_EACH_PTR(rel);
 270 free:
 271         free_string(left_name);
 272 }
 273
 274 void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state)
 275 {
 276         struct relation *rel;
 277         struct smatch_state *estate;
 278
 279         estate = get_state_expr(SMATCH_EXTRA, expr);
 280
 281         if (!estate)
 282                 return;
 283
 284         FOR_EACH_PTR(get_dinfo(estate)->related, rel) {
 285                 if (rel->op != SPECIAL_EQUAL)
 286                         continue;
 287                 set_state(id, rel->name, rel->sym, state);
 288         } END_FOR_EACH_PTR(rel);
 289 }