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