1 /* 2 * Copyright (C) 2010 Dan Carpenter. 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public License 6 * as published by the Free Software Foundation; either version 2 7 * of the License, or (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt 16 */ 17 18 /* 19 * smatch_equiv.c is for tracking how variables are the same 20 * 21 * if (a == b) { 22 * Or 23 * x = y; 24 * 25 * When a variable gets modified all the old relationships are 26 * deleted. remove_equiv(expr); 27 * 28 */ 29 30 #include "smatch.h" 31 #include "smatch_slist.h" 32 #include "smatch_extra.h" 33 34 ALLOCATOR(relation, "related variables"); 35 36 static struct relation *alloc_relation(const char *name, struct symbol *sym) 37 { 38 struct relation *tmp; 39 40 tmp = __alloc_relation(0); 41 tmp->name = alloc_string(name); 42 tmp->sym = sym; 43 return tmp; 44 } 45 46 struct related_list *clone_related_list(struct related_list *related) 47 { 48 struct relation *rel; 49 struct related_list *to_list = NULL; 50 51 FOR_EACH_PTR(related, rel) { 52 add_ptr_list(&to_list, rel); 53 } END_FOR_EACH_PTR(rel); 54 55 return to_list; 56 } 57 58 static int cmp_relation(struct relation *a, struct relation *b) 59 { 60 int ret; 61 62 if (a == b) 63 return 0; 64 65 if (a->sym > b->sym) 66 return -1; 67 if (a->sym < b->sym) 68 return 1; 69 70 ret = strcmp(a->name, b->name); 71 if (ret) 72 return ret; 73 74 return 0; 75 } 76 77 struct related_list *get_shared_relations(struct related_list *one, 78 struct related_list *two) 79 { 80 struct related_list *ret = NULL; 81 struct relation *one_rel; 82 struct relation *two_rel; 83 84 PREPARE_PTR_LIST(one, one_rel); 85 PREPARE_PTR_LIST(two, two_rel); 86 for (;;) { 87 if (!one_rel || !two_rel) 88 break; 89 if (cmp_relation(one_rel, two_rel) < 0) { 90 NEXT_PTR_LIST(one_rel); 91 } else if (cmp_relation(one_rel, two_rel) == 0) { 92 add_ptr_list(&ret, one_rel); 93 NEXT_PTR_LIST(one_rel); 94 NEXT_PTR_LIST(two_rel); 95 } else { 96 NEXT_PTR_LIST(two_rel); 97 } 98 } 99 FINISH_PTR_LIST(two_rel); 100 FINISH_PTR_LIST(one_rel); 101 102 return ret; 103 } 104 105 static void debug_addition(struct related_list *rlist, const char *name) 106 { 107 struct relation *tmp; 108 109 if (!option_debug_related) 110 return; 111 112 sm_prefix(); 113 sm_printf("("); 114 FOR_EACH_PTR(rlist, tmp) { 115 sm_printf("%s ", tmp->name); 116 } END_FOR_EACH_PTR(tmp); 117 sm_printf(") <-- %s\n", name); 118 } 119 120 static void add_related(struct related_list **rlist, const char *name, struct symbol *sym) 121 { 122 struct relation *rel; 123 struct relation *new; 124 struct relation tmp = { 125 .name = (char *)name, 126 .sym = sym 127 }; 128 129 debug_addition(*rlist, name); 130 131 FOR_EACH_PTR(*rlist, rel) { 132 if (cmp_relation(rel, &tmp) < 0) 133 continue; 134 if (cmp_relation(rel, &tmp) == 0) 135 return; 136 new = alloc_relation(name, sym); 137 INSERT_CURRENT(new, rel); 138 return; 139 } END_FOR_EACH_PTR(rel); 140 new = alloc_relation(name, sym); 141 add_ptr_list(rlist, new); 142 } 143 144 static struct related_list *del_related(struct smatch_state *state, const char *name, struct symbol *sym) 145 { 146 struct relation *tmp; 147 struct relation remove = { 148 .name = (char *)name, 149 .sym = sym, 150 }; 151 struct related_list *ret = NULL; 152 153 FOR_EACH_PTR(estate_related(state), tmp) { 154 if (cmp_relation(tmp, &remove) != 0) 155 add_ptr_list(&ret, tmp); 156 } END_FOR_EACH_PTR(tmp); 157 158 return ret; 159 } 160 161 void remove_from_equiv(const char *name, struct symbol *sym) 162 { 163 struct sm_state *orig_sm; 164 struct relation *rel; 165 struct smatch_state *state; 166 struct related_list *to_update; 167 168 orig_sm = get_sm_state(SMATCH_EXTRA, name, sym); 169 if (!orig_sm || !get_dinfo(orig_sm->state)->related) 170 return; 171 172 state = clone_estate(orig_sm->state); 173 to_update = del_related(state, name, sym); 174 175 FOR_EACH_PTR(to_update, rel) { 176 struct sm_state *old_sm, *new_sm; 177 178 old_sm = get_sm_state(SMATCH_EXTRA, rel->name, rel->sym); 179 if (!old_sm) 180 continue; 181 182 new_sm = clone_sm(old_sm); 183 get_dinfo(new_sm->state)->related = to_update; 184 __set_sm(new_sm); 185 } END_FOR_EACH_PTR(rel); 186 } 187 188 void remove_from_equiv_expr(struct expression *expr) 189 { 190 char *name; 191 struct symbol *sym; 192 193 name = expr_to_var_sym(expr, &sym); 194 if (!name || !sym) 195 goto free; 196 remove_from_equiv(name, sym); 197 free: 198 free_string(name); 199 } 200 201 void set_related(struct smatch_state *estate, struct related_list *rlist) 202 { 203 if (!estate_related(estate) && !rlist) 204 return; 205 get_dinfo(estate)->related = rlist; 206 } 207 208 /* 209 * set_equiv() is only used for assignments where we set one variable 210 * equal to the other. a = b;. It's not used for if conditions where 211 * a == b. 212 */ 213 void set_equiv(struct expression *left, struct expression *right) 214 { 215 struct sm_state *right_sm, *left_sm; 216 struct relation *rel; 217 char *left_name; 218 struct symbol *left_sym; 219 struct related_list *rlist; 220 221 left_name = expr_to_var_sym(left, &left_sym); 222 if (!left_name || !left_sym) 223 goto free; 224 225 right_sm = get_sm_state_expr(SMATCH_EXTRA, right); 226 if (!right_sm) 227 right_sm = set_state_expr(SMATCH_EXTRA, right, alloc_estate_whole(get_type(right))); 228 if (!right_sm) 229 goto free; 230 231 /* This block is because we want to preserve the implications. */ 232 left_sm = clone_sm(right_sm); 233 left_sm->name = alloc_string(left_name); 234 left_sm->sym = left_sym; 235 left_sm->state = clone_estate_cast(get_type(left), right_sm->state); 236 set_extra_mod_helper(left_name, left_sym, left, left_sm->state); 237 __set_sm(left_sm); 238 239 rlist = clone_related_list(estate_related(right_sm->state)); 240 add_related(&rlist, right_sm->name, right_sm->sym); 241 add_related(&rlist, left_name, left_sym); 242 243 FOR_EACH_PTR(rlist, rel) { 244 struct sm_state *old_sm, *new_sm; 245 246 old_sm = get_sm_state(SMATCH_EXTRA, rel->name, rel->sym); 247 if (!old_sm) /* shouldn't happen */ 248 continue; 249 new_sm = clone_sm(old_sm); 250 new_sm->state = clone_estate(old_sm->state); 251 get_dinfo(new_sm->state)->related = rlist; 252 __set_sm(new_sm); 253 } END_FOR_EACH_PTR(rel); 254 free: 255 free_string(left_name); 256 } 257 258 void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state) 259 { 260 struct relation *rel; 261 struct smatch_state *estate; 262 263 estate = get_state_expr(SMATCH_EXTRA, expr); 264 265 if (!estate) 266 return; 267 268 FOR_EACH_PTR(get_dinfo(estate)->related, rel) { 269 set_state(id, rel->name, rel->sym, state); 270 } END_FOR_EACH_PTR(rel); 271 } 272