e0cad5e2daed4111dd032bbad4da718215c3744f
2 * sparse/smatch_equiv.c
4 * Copyright (C) 2010 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
11 * smatch_equiv.c is for tracking how variables are the same
17 * When a variable gets modified all the old relationships are
18 * deleted. remove_equiv(expr);
23 #include "smatch_slist.h"
24 #include "smatch_extra.h"
26 ALLOCATOR(relation
, "related variables");
28 static struct relation
*alloc_relation(int op
, const char *name
, struct symbol
*sym
)
32 tmp
= __alloc_relation(0);
34 tmp
->name
= alloc_string(name
);
39 struct related_list
*clone_related_list(struct related_list
*related
)
42 struct related_list
*to_list
= NULL
;
44 FOR_EACH_PTR(related
, rel
) {
45 add_ptr_list(&to_list
, rel
);
46 } END_FOR_EACH_PTR(rel
);
51 static int cmp_relation(struct relation
*a
, struct relation
*b
)
68 ret
= strcmp(a
->name
, b
->name
);
75 struct related_list
*get_shared_relations(struct related_list
*one
,
76 struct related_list
*two
)
78 struct related_list
*ret
= NULL
;
79 struct relation
*one_rel
;
80 struct relation
*two_rel
;
82 PREPARE_PTR_LIST(one
, one_rel
);
83 PREPARE_PTR_LIST(two
, two_rel
);
85 if (!one_rel
|| !two_rel
)
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
);
94 NEXT_PTR_LIST(two_rel
);
97 FINISH_PTR_LIST(two_rel
);
98 FINISH_PTR_LIST(one_rel
);
103 static void debug_addition(struct related_list
*rlist
, int op
, const char *name
)
105 struct relation
*tmp
;
107 if (!option_debug_related
)
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
);
118 static void add_related(struct related_list
**rlist
, int op
, const char *name
, struct symbol
*sym
)
120 struct relation
*rel
;
121 struct relation
*new;
122 struct relation tmp
= {
124 .name
= (char *)name
,
128 debug_addition(*rlist
, op
, name
);
130 FOR_EACH_PTR(*rlist
, rel
) {
131 if (cmp_relation(rel
, &tmp
) < 0)
133 if (cmp_relation(rel
, &tmp
) == 0)
135 new = alloc_relation(op
, name
, sym
);
136 INSERT_CURRENT(new, rel
);
138 } END_FOR_EACH_PTR(rel
);
139 new = alloc_relation(op
, name
, sym
);
140 add_ptr_list(rlist
, new);
143 void del_related(struct smatch_state
*state
, int op
, const char *name
, struct symbol
*sym
)
145 struct relation
*tmp
;
146 struct relation remove
= {
148 .name
= (char *)name
,
152 FOR_EACH_PTR(estate_related(state
), tmp
) {
153 if (cmp_relation(tmp
, &remove
) < 0)
155 if (cmp_relation(tmp
, &remove
) == 0) {
156 DELETE_CURRENT_PTR(tmp
);
160 } END_FOR_EACH_PTR(tmp
);
163 static void del_equiv(struct smatch_state
*state
, const char *name
, struct symbol
*sym
)
165 del_related(state
, SPECIAL_EQUAL
, name
, sym
);
168 void remove_from_equiv(const char *name
, struct symbol
*sym
)
170 struct sm_state
*orig_sm
;
171 struct relation
*rel
;
172 struct smatch_state
*state
;
173 struct related_list
*to_update
;
175 // FIXME equiv => related
176 orig_sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
177 if (!orig_sm
|| !get_dinfo(orig_sm
->state
)->related
)
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
;
186 FOR_EACH_PTR(to_update
, rel
) {
187 struct sm_state
*new_sm
;
189 new_sm
= clone_sm(orig_sm
);
190 new_sm
->name
= rel
->name
;
191 new_sm
->sym
= rel
->sym
;
192 new_sm
->state
= state
;
194 } END_FOR_EACH_PTR(rel
);
197 void remove_from_equiv_expr(struct expression
*expr
)
202 name
= expr_to_str_sym(expr
, &sym
);
205 remove_from_equiv(name
, sym
);
210 void set_related(struct smatch_state
*estate
, struct related_list
*rlist
)
212 if (!estate_related(estate
) && !rlist
)
214 get_dinfo(estate
)->related
= rlist
;
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
222 void set_equiv(struct expression
*left
, struct expression
*right
)
224 struct sm_state
*right_sm
;
225 struct smatch_state
*state
;
226 struct relation
*rel
;
228 struct symbol
*left_sym
;
229 struct related_list
*rlist
;
231 left_name
= expr_to_str_sym(left
, &left_sym
);
232 if (!left_name
|| !left_sym
)
235 right_sm
= get_sm_state_expr(SMATCH_EXTRA
, right
);
237 right_sm
= set_state_expr(SMATCH_EXTRA
, right
, alloc_estate_whole(get_type(right
)));
241 remove_from_equiv(left_name
, left_sym
);
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
);
247 state
= clone_estate(right_sm
->state
);
248 get_dinfo(state
)->related
= rlist
;
250 FOR_EACH_PTR(rlist
, rel
) {
251 struct sm_state
*new_sm
;
253 new_sm
= clone_sm(right_sm
);
254 new_sm
->name
= rel
->name
;
255 new_sm
->sym
= rel
->sym
;
256 new_sm
->state
= state
;
258 } END_FOR_EACH_PTR(rel
);
260 free_string(left_name
);
263 void set_equiv_state_expr(int id
, struct expression
*expr
, struct smatch_state
*state
)
265 struct relation
*rel
;
266 struct smatch_state
*estate
;
268 estate
= get_state_expr(SMATCH_EXTRA
, expr
);
273 FOR_EACH_PTR(get_dinfo(estate
)->related
, rel
) {
274 if (rel
->op
!= SPECIAL_EQUAL
)
276 set_state(id
, rel
->name
, rel
->sym
, state
);
277 } END_FOR_EACH_PTR(rel
);