11506 smatch resync
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 add_related(struct related_list **rlist, const char *name, struct symbol *sym) 106 { 107 struct relation *rel; 108 struct relation *new; 109 struct relation tmp = { 110 .name = (char *)name, 111 .sym = sym 112 }; 113 114 FOR_EACH_PTR(*rlist, rel) { 115 if (cmp_relation(rel, &tmp) < 0) 116 continue; 117 if (cmp_relation(rel, &tmp) == 0) 118 return; 119 new = alloc_relation(name, sym); 120 INSERT_CURRENT(new, rel); 121 return; 122 } END_FOR_EACH_PTR(rel); 123 new = alloc_relation(name, sym); 124 add_ptr_list(rlist, new); 125 } 126 127 static struct related_list *del_related(struct smatch_state *state, const char *name, struct symbol *sym) 128 { 129 struct relation *tmp; 130 struct relation remove = { 131 .name = (char *)name, 132 .sym = sym, 133 }; 134 struct related_list *ret = NULL; 135 136 FOR_EACH_PTR(estate_related(state), tmp) { 137 if (cmp_relation(tmp, &remove) != 0) 138 add_ptr_list(&ret, tmp); 139 } END_FOR_EACH_PTR(tmp); 140 141 return ret; 142 } 143 144 void remove_from_equiv(const char *name, struct symbol *sym) 145 { 146 struct sm_state *orig_sm; 147 struct relation *rel; 148 struct smatch_state *state; 149 struct related_list *to_update; 150 151 orig_sm = get_sm_state(SMATCH_EXTRA, name, sym); 152 if (!orig_sm || !get_dinfo(orig_sm->state)->related) 153 return; 154 155 state = clone_estate(orig_sm->state); 156 to_update = del_related(state, name, sym); 157 158 FOR_EACH_PTR(to_update, rel) { 159 struct sm_state *old_sm, *new_sm; 160 161 old_sm = get_sm_state(SMATCH_EXTRA, rel->name, rel->sym); 162 if (!old_sm) 163 continue; 164 165 new_sm = clone_sm(old_sm); 166 get_dinfo(new_sm->state)->related = to_update; 167 __set_sm(new_sm); 168 } END_FOR_EACH_PTR(rel); 169 } 170 171 void remove_from_equiv_expr(struct expression *expr) 172 { 173 char *name; 174 struct symbol *sym; 175 176 name = expr_to_var_sym(expr, &sym); 177 if (!name || !sym) 178 goto free; 179 remove_from_equiv(name, sym); 180 free: 181 free_string(name); 182 } 183 184 void set_related(struct smatch_state *estate, struct related_list *rlist) 185 { 186 if (!estate_related(estate) && !rlist) 187 return; 188 get_dinfo(estate)->related = rlist; 189 } 190 191 /* 192 * set_equiv() is only used for assignments where we set one variable 193 * equal to the other. a = b;. It's not used for if conditions where 194 * a == b. 195 */ 196 void set_equiv(struct expression *left, struct expression *right) 197 { 198 struct sm_state *right_sm, *left_sm, *other_sm; 199 struct relation *rel; 200 char *left_name; 201 struct symbol *left_sym; 202 struct related_list *rlist; 203 char *other_name; 204 struct symbol *other_sym; 205 206 left_name = expr_to_var_sym(left, &left_sym); 207 if (!left_name || !left_sym) 208 goto free; 209 210 other_name = get_other_name_sym(left_name, left_sym, &other_sym); 211 212 right_sm = get_sm_state_expr(SMATCH_EXTRA, right); 213 if (!right_sm) { 214 struct range_list *rl; 215 216 if (!get_implied_rl(right, &rl)) 217 rl = alloc_whole_rl(get_type(right)); 218 right_sm = set_state_expr(SMATCH_EXTRA, right, alloc_estate_rl(rl)); 219 } 220 if (!right_sm) 221 goto free; 222 223 /* This block is because we want to preserve the implications. */ 224 left_sm = clone_sm(right_sm); 225 left_sm->name = alloc_string(left_name); 226 left_sm->sym = left_sym; 227 left_sm->state = clone_estate_cast(get_type(left), right_sm->state); 228 /* FIXME: The expression we're passing is wrong */ 229 set_extra_mod_helper(left_name, left_sym, left, left_sm->state); 230 __set_sm(left_sm); 231 232 if (other_name && other_sym) { 233 other_sm = clone_sm(right_sm); 234 other_sm->name = alloc_string(other_name); 235 other_sm->sym = other_sym; 236 other_sm->state = clone_estate_cast(get_type(left), left_sm->state); 237 set_extra_mod_helper(other_name, other_sym, NULL, other_sm->state); 238 __set_sm(other_sm); 239 } 240 241 rlist = clone_related_list(estate_related(right_sm->state)); 242 add_related(&rlist, right_sm->name, right_sm->sym); 243 add_related(&rlist, left_name, left_sym); 244 if (other_name && other_sym) 245 add_related(&rlist, other_name, other_sym); 246 247 FOR_EACH_PTR(rlist, rel) { 248 struct sm_state *old_sm, *new_sm; 249 250 old_sm = get_sm_state(SMATCH_EXTRA, rel->name, rel->sym); 251 if (!old_sm) /* shouldn't happen */ 252 continue; 253 new_sm = clone_sm(old_sm); 254 new_sm->state = clone_estate(old_sm->state); 255 get_dinfo(new_sm->state)->related = rlist; 256 __set_sm(new_sm); 257 } END_FOR_EACH_PTR(rel); 258 free: 259 free_string(left_name); 260 } 261 262 void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state) 263 { 264 struct relation *rel; 265 struct smatch_state *estate; 266 267 estate = get_state_expr(SMATCH_EXTRA, expr); 268 269 if (!estate) 270 return; 271 272 FOR_EACH_PTR(get_dinfo(estate)->related, rel) { 273 set_state(id, rel->name, rel->sym, state); 274 } END_FOR_EACH_PTR(rel); 275 } --- EOF ---