smatch_equiv.c

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