11f5207b7SJohn Levon /*
21f5207b7SJohn Levon * Copyright (C) 2010 Dan Carpenter.
31f5207b7SJohn Levon *
41f5207b7SJohn Levon * This program is free software; you can redistribute it and/or
51f5207b7SJohn Levon * modify it under the terms of the GNU General Public License
61f5207b7SJohn Levon * as published by the Free Software Foundation; either version 2
71f5207b7SJohn Levon * of the License, or (at your option) any later version.
81f5207b7SJohn Levon *
91f5207b7SJohn Levon * This program is distributed in the hope that it will be useful,
101f5207b7SJohn Levon * but WITHOUT ANY WARRANTY; without even the implied warranty of
111f5207b7SJohn Levon * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
121f5207b7SJohn Levon * GNU General Public License for more details.
131f5207b7SJohn Levon *
141f5207b7SJohn Levon * You should have received a copy of the GNU General Public License
151f5207b7SJohn Levon * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
161f5207b7SJohn Levon */
171f5207b7SJohn Levon
181f5207b7SJohn Levon /*
191f5207b7SJohn Levon * smatch_equiv.c is for tracking how variables are the same
201f5207b7SJohn Levon *
211f5207b7SJohn Levon * if (a == b) {
221f5207b7SJohn Levon * Or
231f5207b7SJohn Levon * x = y;
241f5207b7SJohn Levon *
251f5207b7SJohn Levon * When a variable gets modified all the old relationships are
261f5207b7SJohn Levon * deleted. remove_equiv(expr);
271f5207b7SJohn Levon *
281f5207b7SJohn Levon */
291f5207b7SJohn Levon
301f5207b7SJohn Levon #include "smatch.h"
311f5207b7SJohn Levon #include "smatch_slist.h"
321f5207b7SJohn Levon #include "smatch_extra.h"
331f5207b7SJohn Levon
341f5207b7SJohn Levon ALLOCATOR(relation, "related variables");
351f5207b7SJohn Levon
alloc_relation(const char * name,struct symbol * sym)361f5207b7SJohn Levon static struct relation *alloc_relation(const char *name, struct symbol *sym)
371f5207b7SJohn Levon {
381f5207b7SJohn Levon struct relation *tmp;
391f5207b7SJohn Levon
401f5207b7SJohn Levon tmp = __alloc_relation(0);
411f5207b7SJohn Levon tmp->name = alloc_string(name);
421f5207b7SJohn Levon tmp->sym = sym;
431f5207b7SJohn Levon return tmp;
441f5207b7SJohn Levon }
451f5207b7SJohn Levon
clone_related_list(struct related_list * related)461f5207b7SJohn Levon struct related_list *clone_related_list(struct related_list *related)
471f5207b7SJohn Levon {
481f5207b7SJohn Levon struct relation *rel;
491f5207b7SJohn Levon struct related_list *to_list = NULL;
501f5207b7SJohn Levon
511f5207b7SJohn Levon FOR_EACH_PTR(related, rel) {
521f5207b7SJohn Levon add_ptr_list(&to_list, rel);
531f5207b7SJohn Levon } END_FOR_EACH_PTR(rel);
541f5207b7SJohn Levon
551f5207b7SJohn Levon return to_list;
561f5207b7SJohn Levon }
571f5207b7SJohn Levon
cmp_relation(struct relation * a,struct relation * b)581f5207b7SJohn Levon static int cmp_relation(struct relation *a, struct relation *b)
591f5207b7SJohn Levon {
601f5207b7SJohn Levon int ret;
611f5207b7SJohn Levon
621f5207b7SJohn Levon if (a == b)
631f5207b7SJohn Levon return 0;
641f5207b7SJohn Levon
651f5207b7SJohn Levon if (a->sym > b->sym)
661f5207b7SJohn Levon return -1;
671f5207b7SJohn Levon if (a->sym < b->sym)
681f5207b7SJohn Levon return 1;
691f5207b7SJohn Levon
701f5207b7SJohn Levon ret = strcmp(a->name, b->name);
711f5207b7SJohn Levon if (ret)
721f5207b7SJohn Levon return ret;
731f5207b7SJohn Levon
741f5207b7SJohn Levon return 0;
751f5207b7SJohn Levon }
761f5207b7SJohn Levon
get_shared_relations(struct related_list * one,struct related_list * two)771f5207b7SJohn Levon struct related_list *get_shared_relations(struct related_list *one,
781f5207b7SJohn Levon struct related_list *two)
791f5207b7SJohn Levon {
801f5207b7SJohn Levon struct related_list *ret = NULL;
811f5207b7SJohn Levon struct relation *one_rel;
821f5207b7SJohn Levon struct relation *two_rel;
831f5207b7SJohn Levon
841f5207b7SJohn Levon PREPARE_PTR_LIST(one, one_rel);
851f5207b7SJohn Levon PREPARE_PTR_LIST(two, two_rel);
861f5207b7SJohn Levon for (;;) {
871f5207b7SJohn Levon if (!one_rel || !two_rel)
881f5207b7SJohn Levon break;
891f5207b7SJohn Levon if (cmp_relation(one_rel, two_rel) < 0) {
901f5207b7SJohn Levon NEXT_PTR_LIST(one_rel);
911f5207b7SJohn Levon } else if (cmp_relation(one_rel, two_rel) == 0) {
921f5207b7SJohn Levon add_ptr_list(&ret, one_rel);
931f5207b7SJohn Levon NEXT_PTR_LIST(one_rel);
941f5207b7SJohn Levon NEXT_PTR_LIST(two_rel);
951f5207b7SJohn Levon } else {
961f5207b7SJohn Levon NEXT_PTR_LIST(two_rel);
971f5207b7SJohn Levon }
981f5207b7SJohn Levon }
991f5207b7SJohn Levon FINISH_PTR_LIST(two_rel);
1001f5207b7SJohn Levon FINISH_PTR_LIST(one_rel);
1011f5207b7SJohn Levon
1021f5207b7SJohn Levon return ret;
1031f5207b7SJohn Levon }
1041f5207b7SJohn Levon
add_related(struct related_list ** rlist,const char * name,struct symbol * sym)1051f5207b7SJohn Levon static void add_related(struct related_list **rlist, const char *name, struct symbol *sym)
1061f5207b7SJohn Levon {
1071f5207b7SJohn Levon struct relation *rel;
1081f5207b7SJohn Levon struct relation *new;
1091f5207b7SJohn Levon struct relation tmp = {
1101f5207b7SJohn Levon .name = (char *)name,
1111f5207b7SJohn Levon .sym = sym
1121f5207b7SJohn Levon };
1131f5207b7SJohn Levon
1141f5207b7SJohn Levon FOR_EACH_PTR(*rlist, rel) {
1151f5207b7SJohn Levon if (cmp_relation(rel, &tmp) < 0)
1161f5207b7SJohn Levon continue;
1171f5207b7SJohn Levon if (cmp_relation(rel, &tmp) == 0)
1181f5207b7SJohn Levon return;
1191f5207b7SJohn Levon new = alloc_relation(name, sym);
1201f5207b7SJohn Levon INSERT_CURRENT(new, rel);
1211f5207b7SJohn Levon return;
1221f5207b7SJohn Levon } END_FOR_EACH_PTR(rel);
1231f5207b7SJohn Levon new = alloc_relation(name, sym);
1241f5207b7SJohn Levon add_ptr_list(rlist, new);
1251f5207b7SJohn Levon }
1261f5207b7SJohn Levon
del_related(struct smatch_state * state,const char * name,struct symbol * sym)1271f5207b7SJohn Levon static struct related_list *del_related(struct smatch_state *state, const char *name, struct symbol *sym)
1281f5207b7SJohn Levon {
1291f5207b7SJohn Levon struct relation *tmp;
1301f5207b7SJohn Levon struct relation remove = {
1311f5207b7SJohn Levon .name = (char *)name,
1321f5207b7SJohn Levon .sym = sym,
1331f5207b7SJohn Levon };
1341f5207b7SJohn Levon struct related_list *ret = NULL;
1351f5207b7SJohn Levon
1361f5207b7SJohn Levon FOR_EACH_PTR(estate_related(state), tmp) {
1371f5207b7SJohn Levon if (cmp_relation(tmp, &remove) != 0)
1381f5207b7SJohn Levon add_ptr_list(&ret, tmp);
1391f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp);
1401f5207b7SJohn Levon
1411f5207b7SJohn Levon return ret;
1421f5207b7SJohn Levon }
1431f5207b7SJohn Levon
remove_from_equiv(const char * name,struct symbol * sym)1441f5207b7SJohn Levon void remove_from_equiv(const char *name, struct symbol *sym)
1451f5207b7SJohn Levon {
1461f5207b7SJohn Levon struct sm_state *orig_sm;
1471f5207b7SJohn Levon struct relation *rel;
1481f5207b7SJohn Levon struct smatch_state *state;
1491f5207b7SJohn Levon struct related_list *to_update;
1501f5207b7SJohn Levon
1511f5207b7SJohn Levon orig_sm = get_sm_state(SMATCH_EXTRA, name, sym);
1521f5207b7SJohn Levon if (!orig_sm || !get_dinfo(orig_sm->state)->related)
1531f5207b7SJohn Levon return;
1541f5207b7SJohn Levon
1551f5207b7SJohn Levon state = clone_estate(orig_sm->state);
1561f5207b7SJohn Levon to_update = del_related(state, name, sym);
1571f5207b7SJohn Levon
1581f5207b7SJohn Levon FOR_EACH_PTR(to_update, rel) {
1591f5207b7SJohn Levon struct sm_state *old_sm, *new_sm;
1601f5207b7SJohn Levon
1611f5207b7SJohn Levon old_sm = get_sm_state(SMATCH_EXTRA, rel->name, rel->sym);
1621f5207b7SJohn Levon if (!old_sm)
1631f5207b7SJohn Levon continue;
1641f5207b7SJohn Levon
1651f5207b7SJohn Levon new_sm = clone_sm(old_sm);
1661f5207b7SJohn Levon get_dinfo(new_sm->state)->related = to_update;
1671f5207b7SJohn Levon __set_sm(new_sm);
1681f5207b7SJohn Levon } END_FOR_EACH_PTR(rel);
1691f5207b7SJohn Levon }
1701f5207b7SJohn Levon
remove_from_equiv_expr(struct expression * expr)1711f5207b7SJohn Levon void remove_from_equiv_expr(struct expression *expr)
1721f5207b7SJohn Levon {
1731f5207b7SJohn Levon char *name;
1741f5207b7SJohn Levon struct symbol *sym;
1751f5207b7SJohn Levon
1761f5207b7SJohn Levon name = expr_to_var_sym(expr, &sym);
1771f5207b7SJohn Levon if (!name || !sym)
1781f5207b7SJohn Levon goto free;
1791f5207b7SJohn Levon remove_from_equiv(name, sym);
1801f5207b7SJohn Levon free:
1811f5207b7SJohn Levon free_string(name);
1821f5207b7SJohn Levon }
1831f5207b7SJohn Levon
set_related(struct smatch_state * estate,struct related_list * rlist)1841f5207b7SJohn Levon void set_related(struct smatch_state *estate, struct related_list *rlist)
1851f5207b7SJohn Levon {
1861f5207b7SJohn Levon if (!estate_related(estate) && !rlist)
1871f5207b7SJohn Levon return;
1881f5207b7SJohn Levon get_dinfo(estate)->related = rlist;
1891f5207b7SJohn Levon }
1901f5207b7SJohn Levon
1911f5207b7SJohn Levon /*
1921f5207b7SJohn Levon * set_equiv() is only used for assignments where we set one variable
1931f5207b7SJohn Levon * equal to the other. a = b;. It's not used for if conditions where
1941f5207b7SJohn Levon * a == b.
1951f5207b7SJohn Levon */
set_equiv(struct expression * left,struct expression * right)1961f5207b7SJohn Levon void set_equiv(struct expression *left, struct expression *right)
1971f5207b7SJohn Levon {
198*efe51d0cSJohn Levon struct sm_state *right_sm, *left_sm, *other_sm;
1991f5207b7SJohn Levon struct relation *rel;
2001f5207b7SJohn Levon char *left_name;
2011f5207b7SJohn Levon struct symbol *left_sym;
2021f5207b7SJohn Levon struct related_list *rlist;
203*efe51d0cSJohn Levon char *other_name;
204*efe51d0cSJohn Levon struct symbol *other_sym;
2051f5207b7SJohn Levon
2061f5207b7SJohn Levon left_name = expr_to_var_sym(left, &left_sym);
2071f5207b7SJohn Levon if (!left_name || !left_sym)
2081f5207b7SJohn Levon goto free;
2091f5207b7SJohn Levon
210*efe51d0cSJohn Levon other_name = get_other_name_sym(left_name, left_sym, &other_sym);
211*efe51d0cSJohn Levon
2121f5207b7SJohn Levon right_sm = get_sm_state_expr(SMATCH_EXTRA, right);
213*efe51d0cSJohn Levon if (!right_sm) {
214*efe51d0cSJohn Levon struct range_list *rl;
215*efe51d0cSJohn Levon
216*efe51d0cSJohn Levon if (!get_implied_rl(right, &rl))
217*efe51d0cSJohn Levon rl = alloc_whole_rl(get_type(right));
218*efe51d0cSJohn Levon right_sm = set_state_expr(SMATCH_EXTRA, right, alloc_estate_rl(rl));
219*efe51d0cSJohn Levon }
2201f5207b7SJohn Levon if (!right_sm)
2211f5207b7SJohn Levon goto free;
2221f5207b7SJohn Levon
2231f5207b7SJohn Levon /* This block is because we want to preserve the implications. */
2241f5207b7SJohn Levon left_sm = clone_sm(right_sm);
2251f5207b7SJohn Levon left_sm->name = alloc_string(left_name);
2261f5207b7SJohn Levon left_sm->sym = left_sym;
2271f5207b7SJohn Levon left_sm->state = clone_estate_cast(get_type(left), right_sm->state);
228*efe51d0cSJohn Levon /* FIXME: The expression we're passing is wrong */
2291f5207b7SJohn Levon set_extra_mod_helper(left_name, left_sym, left, left_sm->state);
2301f5207b7SJohn Levon __set_sm(left_sm);
2311f5207b7SJohn Levon
232*efe51d0cSJohn Levon if (other_name && other_sym) {
233*efe51d0cSJohn Levon other_sm = clone_sm(right_sm);
234*efe51d0cSJohn Levon other_sm->name = alloc_string(other_name);
235*efe51d0cSJohn Levon other_sm->sym = other_sym;
236*efe51d0cSJohn Levon other_sm->state = clone_estate_cast(get_type(left), left_sm->state);
237*efe51d0cSJohn Levon set_extra_mod_helper(other_name, other_sym, NULL, other_sm->state);
238*efe51d0cSJohn Levon __set_sm(other_sm);
239*efe51d0cSJohn Levon }
240*efe51d0cSJohn Levon
2411f5207b7SJohn Levon rlist = clone_related_list(estate_related(right_sm->state));
2421f5207b7SJohn Levon add_related(&rlist, right_sm->name, right_sm->sym);
2431f5207b7SJohn Levon add_related(&rlist, left_name, left_sym);
244*efe51d0cSJohn Levon if (other_name && other_sym)
245*efe51d0cSJohn Levon add_related(&rlist, other_name, other_sym);
2461f5207b7SJohn Levon
2471f5207b7SJohn Levon FOR_EACH_PTR(rlist, rel) {
2481f5207b7SJohn Levon struct sm_state *old_sm, *new_sm;
2491f5207b7SJohn Levon
2501f5207b7SJohn Levon old_sm = get_sm_state(SMATCH_EXTRA, rel->name, rel->sym);
2511f5207b7SJohn Levon if (!old_sm) /* shouldn't happen */
2521f5207b7SJohn Levon continue;
2531f5207b7SJohn Levon new_sm = clone_sm(old_sm);
2541f5207b7SJohn Levon new_sm->state = clone_estate(old_sm->state);
2551f5207b7SJohn Levon get_dinfo(new_sm->state)->related = rlist;
2561f5207b7SJohn Levon __set_sm(new_sm);
2571f5207b7SJohn Levon } END_FOR_EACH_PTR(rel);
2581f5207b7SJohn Levon free:
2591f5207b7SJohn Levon free_string(left_name);
2601f5207b7SJohn Levon }
2611f5207b7SJohn Levon
set_equiv_state_expr(int id,struct expression * expr,struct smatch_state * state)2621f5207b7SJohn Levon void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state)
2631f5207b7SJohn Levon {
2641f5207b7SJohn Levon struct relation *rel;
2651f5207b7SJohn Levon struct smatch_state *estate;
2661f5207b7SJohn Levon
2671f5207b7SJohn Levon estate = get_state_expr(SMATCH_EXTRA, expr);
2681f5207b7SJohn Levon
2691f5207b7SJohn Levon if (!estate)
2701f5207b7SJohn Levon return;
2711f5207b7SJohn Levon
2721f5207b7SJohn Levon FOR_EACH_PTR(get_dinfo(estate)->related, rel) {
2731f5207b7SJohn Levon set_state(id, rel->name, rel->sym, state);
2741f5207b7SJohn Levon } END_FOR_EACH_PTR(rel);
2751f5207b7SJohn Levon }
276