11f5207b7SJohn Levon /*
21f5207b7SJohn Levon  * Copyright (C) 2012 Oracle.
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  * The point here is to store the relationships between two variables.
201f5207b7SJohn Levon  * Ie:  y > x.
211f5207b7SJohn Levon  * To do that we create a state with the two variables in alphabetical order:
221f5207b7SJohn Levon  * ->name = "x vs y" and the state would be "<".  On the false path the state
231f5207b7SJohn Levon  * would be ">=".
241f5207b7SJohn Levon  *
251f5207b7SJohn Levon  * Part of the trick of it is that if x or y is modified then we need to reset
261f5207b7SJohn Levon  * the state.  We need to keep a list of all the states which depend on x and
271f5207b7SJohn Levon  * all the states which depend on y.  The link_id code handles this.
281f5207b7SJohn Levon  *
291f5207b7SJohn Levon  */
301f5207b7SJohn Levon 
311f5207b7SJohn Levon #include "smatch.h"
321f5207b7SJohn Levon #include "smatch_extra.h"
331f5207b7SJohn Levon #include "smatch_slist.h"
341f5207b7SJohn Levon 
355a0e240fSJohn Levon int comparison_id;
361f5207b7SJohn Levon static int link_id;
371f5207b7SJohn Levon static int inc_dec_id;
381f5207b7SJohn Levon static int inc_dec_link_id;
391f5207b7SJohn Levon 
401f5207b7SJohn Levon static void add_comparison(struct expression *left, int comparison, struct expression *right);
411f5207b7SJohn Levon 
421f5207b7SJohn Levon /* for handling for loops */
431f5207b7SJohn Levon STATE(start);
441f5207b7SJohn Levon STATE(incremented);
451f5207b7SJohn Levon 
461f5207b7SJohn Levon ALLOCATOR(compare_data, "compare data");
471f5207b7SJohn Levon 
vsl_to_sym(struct var_sym_list * vsl)481f5207b7SJohn Levon static struct symbol *vsl_to_sym(struct var_sym_list *vsl)
491f5207b7SJohn Levon {
501f5207b7SJohn Levon 	struct var_sym *vs;
511f5207b7SJohn Levon 
521f5207b7SJohn Levon 	if (!vsl)
531f5207b7SJohn Levon 		return NULL;
541f5207b7SJohn Levon 	if (ptr_list_size((struct ptr_list *)vsl) != 1)
551f5207b7SJohn Levon 		return NULL;
561f5207b7SJohn Levon 	vs = first_ptr_list((struct ptr_list *)vsl);
571f5207b7SJohn Levon 	return vs->sym;
581f5207b7SJohn Levon }
591f5207b7SJohn Levon 
show_comparison(int comparison)60c85f09ccSJohn Levon static const char *show_comparison(int comparison)
61c85f09ccSJohn Levon {
62c85f09ccSJohn Levon 	if (comparison == IMPOSSIBLE_COMPARISON)
63c85f09ccSJohn Levon 		return "impossible";
64c85f09ccSJohn Levon 	if (comparison == UNKNOWN_COMPARISON)
65c85f09ccSJohn Levon 		return "unknown";
66c85f09ccSJohn Levon 	return show_special(comparison);
67c85f09ccSJohn Levon }
68c85f09ccSJohn Levon 
alloc_compare_state(struct expression * left,const char * left_var,struct var_sym_list * left_vsl,int comparison,struct expression * right,const char * right_var,struct var_sym_list * right_vsl)691f5207b7SJohn Levon struct smatch_state *alloc_compare_state(
701f5207b7SJohn Levon 		struct expression *left,
711f5207b7SJohn Levon 		const char *left_var, struct var_sym_list *left_vsl,
721f5207b7SJohn Levon 		int comparison,
731f5207b7SJohn Levon 		struct expression *right,
741f5207b7SJohn Levon 		const char *right_var, struct var_sym_list *right_vsl)
751f5207b7SJohn Levon {
761f5207b7SJohn Levon 	struct smatch_state *state;
771f5207b7SJohn Levon 	struct compare_data *data;
781f5207b7SJohn Levon 
791f5207b7SJohn Levon 	state = __alloc_smatch_state(0);
80c85f09ccSJohn Levon 	state->name = alloc_sname(show_comparison(comparison));
811f5207b7SJohn Levon 	data = __alloc_compare_data(0);
821f5207b7SJohn Levon 	data->left = left;
831f5207b7SJohn Levon 	data->left_var = alloc_sname(left_var);
841f5207b7SJohn Levon 	data->left_vsl = clone_var_sym_list(left_vsl);
851f5207b7SJohn Levon 	data->comparison = comparison;
861f5207b7SJohn Levon 	data->right = right;
871f5207b7SJohn Levon 	data->right_var = alloc_sname(right_var);
881f5207b7SJohn Levon 	data->right_vsl = clone_var_sym_list(right_vsl);
891f5207b7SJohn Levon 	state->data = data;
901f5207b7SJohn Levon 	return state;
911f5207b7SJohn Levon }
921f5207b7SJohn Levon 
state_to_comparison(struct smatch_state * state)931f5207b7SJohn Levon int state_to_comparison(struct smatch_state *state)
941f5207b7SJohn Levon {
951f5207b7SJohn Levon 	if (!state || !state->data)
96c85f09ccSJohn Levon 		return UNKNOWN_COMPARISON;
971f5207b7SJohn Levon 	return ((struct compare_data *)state->data)->comparison;
981f5207b7SJohn Levon }
991f5207b7SJohn Levon 
1001f5207b7SJohn Levon /*
1011f5207b7SJohn Levon  * flip_comparison() reverses the op left and right.  So "x >= y" becomes "y <= x".
1021f5207b7SJohn Levon  */
flip_comparison(int op)1031f5207b7SJohn Levon int flip_comparison(int op)
1041f5207b7SJohn Levon {
1051f5207b7SJohn Levon 	switch (op) {
106c85f09ccSJohn Levon 	case UNKNOWN_COMPARISON:
107c85f09ccSJohn Levon 		return UNKNOWN_COMPARISON;
1081f5207b7SJohn Levon 	case '<':
1091f5207b7SJohn Levon 		return '>';
1101f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_LT:
1111f5207b7SJohn Levon 		return SPECIAL_UNSIGNED_GT;
1121f5207b7SJohn Levon 	case SPECIAL_LTE:
1131f5207b7SJohn Levon 		return SPECIAL_GTE;
1141f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_LTE:
1151f5207b7SJohn Levon 		return SPECIAL_UNSIGNED_GTE;
1161f5207b7SJohn Levon 	case SPECIAL_EQUAL:
1171f5207b7SJohn Levon 		return SPECIAL_EQUAL;
1181f5207b7SJohn Levon 	case SPECIAL_NOTEQUAL:
1191f5207b7SJohn Levon 		return SPECIAL_NOTEQUAL;
1201f5207b7SJohn Levon 	case SPECIAL_GTE:
1211f5207b7SJohn Levon 		return SPECIAL_LTE;
1221f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_GTE:
1231f5207b7SJohn Levon 		return SPECIAL_UNSIGNED_LTE;
1241f5207b7SJohn Levon 	case '>':
1251f5207b7SJohn Levon 		return '<';
1261f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_GT:
1271f5207b7SJohn Levon 		return SPECIAL_UNSIGNED_LT;
128c85f09ccSJohn Levon 	case IMPOSSIBLE_COMPARISON:
129c85f09ccSJohn Levon 		return UNKNOWN_COMPARISON;
1301f5207b7SJohn Levon 	default:
1311f5207b7SJohn Levon 		sm_perror("unhandled comparison %d", op);
1321f5207b7SJohn Levon 		return op;
1331f5207b7SJohn Levon 	}
1341f5207b7SJohn Levon }
1351f5207b7SJohn Levon 
negate_comparison(int op)1361f5207b7SJohn Levon int negate_comparison(int op)
1371f5207b7SJohn Levon {
1381f5207b7SJohn Levon 	switch (op) {
139c85f09ccSJohn Levon 	case UNKNOWN_COMPARISON:
140c85f09ccSJohn Levon 		return UNKNOWN_COMPARISON;
1411f5207b7SJohn Levon 	case '<':
1421f5207b7SJohn Levon 		return SPECIAL_GTE;
1431f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_LT:
1441f5207b7SJohn Levon 		return SPECIAL_UNSIGNED_GTE;
1451f5207b7SJohn Levon 	case SPECIAL_LTE:
1461f5207b7SJohn Levon 		return '>';
1471f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_LTE:
1481f5207b7SJohn Levon 		return SPECIAL_UNSIGNED_GT;
1491f5207b7SJohn Levon 	case SPECIAL_EQUAL:
1501f5207b7SJohn Levon 		return SPECIAL_NOTEQUAL;
1511f5207b7SJohn Levon 	case SPECIAL_NOTEQUAL:
1521f5207b7SJohn Levon 		return SPECIAL_EQUAL;
1531f5207b7SJohn Levon 	case SPECIAL_GTE:
1541f5207b7SJohn Levon 		return '<';
1551f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_GTE:
1561f5207b7SJohn Levon 		return SPECIAL_UNSIGNED_LT;
1571f5207b7SJohn Levon 	case '>':
1581f5207b7SJohn Levon 		return SPECIAL_LTE;
1591f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_GT:
1601f5207b7SJohn Levon 		return SPECIAL_UNSIGNED_LTE;
161c85f09ccSJohn Levon 	case IMPOSSIBLE_COMPARISON:
162c85f09ccSJohn Levon 		return UNKNOWN_COMPARISON;
1631f5207b7SJohn Levon 	default:
1641f5207b7SJohn Levon 		sm_perror("unhandled comparison %d", op);
1651f5207b7SJohn Levon 		return op;
1661f5207b7SJohn Levon 	}
1671f5207b7SJohn Levon }
1681f5207b7SJohn Levon 
rl_comparison(struct range_list * left_rl,struct range_list * right_rl)1691f5207b7SJohn Levon static int rl_comparison(struct range_list *left_rl, struct range_list *right_rl)
1701f5207b7SJohn Levon {
1711f5207b7SJohn Levon 	sval_t left_min, left_max, right_min, right_max;
1721f5207b7SJohn Levon 	struct symbol *type = &int_ctype;
1731f5207b7SJohn Levon 
1741f5207b7SJohn Levon 	if (!left_rl || !right_rl)
175c85f09ccSJohn Levon 		return UNKNOWN_COMPARISON;
1761f5207b7SJohn Levon 
1771f5207b7SJohn Levon 	if (type_positive_bits(rl_type(left_rl)) > type_positive_bits(type))
1781f5207b7SJohn Levon 		type = rl_type(left_rl);
1791f5207b7SJohn Levon 	if (type_positive_bits(rl_type(right_rl)) > type_positive_bits(type))
1801f5207b7SJohn Levon 		type = rl_type(right_rl);
1811f5207b7SJohn Levon 
1821f5207b7SJohn Levon 	left_rl = cast_rl(type, left_rl);
1831f5207b7SJohn Levon 	right_rl = cast_rl(type, right_rl);
1841f5207b7SJohn Levon 
1851f5207b7SJohn Levon 	left_min = rl_min(left_rl);
1861f5207b7SJohn Levon 	left_max = rl_max(left_rl);
1871f5207b7SJohn Levon 	right_min = rl_min(right_rl);
1881f5207b7SJohn Levon 	right_max = rl_max(right_rl);
1891f5207b7SJohn Levon 
1901f5207b7SJohn Levon 	if (left_min.value == left_max.value &&
1911f5207b7SJohn Levon 	    right_min.value == right_max.value &&
1921f5207b7SJohn Levon 	    left_min.value == right_min.value)
1931f5207b7SJohn Levon 		return SPECIAL_EQUAL;
1941f5207b7SJohn Levon 
1951f5207b7SJohn Levon 	if (sval_cmp(left_max, right_min) < 0)
1961f5207b7SJohn Levon 		return '<';
1971f5207b7SJohn Levon 	if (sval_cmp(left_max, right_min) == 0)
1981f5207b7SJohn Levon 		return SPECIAL_LTE;
1991f5207b7SJohn Levon 	if (sval_cmp(left_min, right_max) > 0)
2001f5207b7SJohn Levon 		return '>';
2011f5207b7SJohn Levon 	if (sval_cmp(left_min, right_max) == 0)
2021f5207b7SJohn Levon 		return SPECIAL_GTE;
2031f5207b7SJohn Levon 
204c85f09ccSJohn Levon 	return UNKNOWN_COMPARISON;
2051f5207b7SJohn Levon }
2061f5207b7SJohn Levon 
comparison_from_extra(struct expression * a,struct expression * b)2071f5207b7SJohn Levon static int comparison_from_extra(struct expression *a, struct expression *b)
2081f5207b7SJohn Levon {
2091f5207b7SJohn Levon 	struct range_list *left, *right;
2101f5207b7SJohn Levon 
2111f5207b7SJohn Levon 	if (!get_implied_rl(a, &left))
212c85f09ccSJohn Levon 		return UNKNOWN_COMPARISON;
2131f5207b7SJohn Levon 	if (!get_implied_rl(b, &right))
214c85f09ccSJohn Levon 		return UNKNOWN_COMPARISON;
2151f5207b7SJohn Levon 
2161f5207b7SJohn Levon 	return rl_comparison(left, right);
2171f5207b7SJohn Levon }
2181f5207b7SJohn Levon 
get_orig_rl(struct var_sym_list * vsl)2191f5207b7SJohn Levon static struct range_list *get_orig_rl(struct var_sym_list *vsl)
2201f5207b7SJohn Levon {
2211f5207b7SJohn Levon 	struct symbol *sym;
2221f5207b7SJohn Levon 	struct smatch_state *state;
2231f5207b7SJohn Levon 
2241f5207b7SJohn Levon 	if (!vsl)
2251f5207b7SJohn Levon 		return NULL;
2261f5207b7SJohn Levon 	sym = vsl_to_sym(vsl);
2271f5207b7SJohn Levon 	if (!sym || !sym->ident)
2281f5207b7SJohn Levon 		return NULL;
2291f5207b7SJohn Levon 	state = get_orig_estate(sym->ident->name, sym);
2301f5207b7SJohn Levon 	return estate_rl(state);
2311f5207b7SJohn Levon }
2321f5207b7SJohn Levon 
unmatched_comparison(struct sm_state * sm)2331f5207b7SJohn Levon static struct smatch_state *unmatched_comparison(struct sm_state *sm)
2341f5207b7SJohn Levon {
2351f5207b7SJohn Levon 	struct compare_data *data = sm->state->data;
2361f5207b7SJohn Levon 	struct range_list *left_rl, *right_rl;
237c85f09ccSJohn Levon 	int op = UNKNOWN_COMPARISON;
2381f5207b7SJohn Levon 
2391f5207b7SJohn Levon 	if (!data)
2401f5207b7SJohn Levon 		return &undefined;
2411f5207b7SJohn Levon 
242c85f09ccSJohn Levon 	if (is_impossible_path()) {
243c85f09ccSJohn Levon 		op = IMPOSSIBLE_COMPARISON;
244c85f09ccSJohn Levon 		goto alloc;
245c85f09ccSJohn Levon 	}
246c85f09ccSJohn Levon 
2471f5207b7SJohn Levon 	if (strstr(data->left_var, " orig"))
2481f5207b7SJohn Levon 		left_rl = get_orig_rl(data->left_vsl);
2491f5207b7SJohn Levon 	else if (!get_implied_rl_var_sym(data->left_var, vsl_to_sym(data->left_vsl), &left_rl))
250c85f09ccSJohn Levon 		goto alloc;
2511f5207b7SJohn Levon 
2521f5207b7SJohn Levon 	if (strstr(data->right_var, " orig"))
2531f5207b7SJohn Levon 		right_rl = get_orig_rl(data->right_vsl);
2541f5207b7SJohn Levon 	else if (!get_implied_rl_var_sym(data->right_var, vsl_to_sym(data->right_vsl), &right_rl))
255c85f09ccSJohn Levon 		goto alloc;
2561f5207b7SJohn Levon 
2571f5207b7SJohn Levon 	op = rl_comparison(left_rl, right_rl);
2581f5207b7SJohn Levon 
259c85f09ccSJohn Levon alloc:
260c85f09ccSJohn Levon 	return alloc_compare_state(data->left, data->left_var, data->left_vsl,
261c85f09ccSJohn Levon 				   op,
262c85f09ccSJohn Levon 				   data->right, data->right_var, data->right_vsl);
2631f5207b7SJohn Levon }
2641f5207b7SJohn Levon 
2651f5207b7SJohn Levon /* remove_unsigned_from_comparison() is obviously a hack. */
remove_unsigned_from_comparison(int op)2661f5207b7SJohn Levon int remove_unsigned_from_comparison(int op)
2671f5207b7SJohn Levon {
2681f5207b7SJohn Levon 	switch (op) {
2691f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_LT:
2701f5207b7SJohn Levon 		return '<';
2711f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_LTE:
2721f5207b7SJohn Levon 		return SPECIAL_LTE;
2731f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_GTE:
2741f5207b7SJohn Levon 		return SPECIAL_GTE;
2751f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_GT:
2761f5207b7SJohn Levon 		return '>';
2771f5207b7SJohn Levon 	default:
2781f5207b7SJohn Levon 		return op;
2791f5207b7SJohn Levon 	}
2801f5207b7SJohn Levon }
2811f5207b7SJohn Levon 
2821f5207b7SJohn Levon /*
2831f5207b7SJohn Levon  * This is for when you merge states "a < b" and "a == b", the result is that
2841f5207b7SJohn Levon  * we can say for sure, "a <= b" after the merge.
2851f5207b7SJohn Levon  */
merge_comparisons(int one,int two)2861f5207b7SJohn Levon int merge_comparisons(int one, int two)
2871f5207b7SJohn Levon {
2881f5207b7SJohn Levon 	int LT, EQ, GT;
2891f5207b7SJohn Levon 
290c85f09ccSJohn Levon 	if (one == UNKNOWN_COMPARISON || two == UNKNOWN_COMPARISON)
291c85f09ccSJohn Levon 		return UNKNOWN_COMPARISON;
292c85f09ccSJohn Levon 
293c85f09ccSJohn Levon 	if (one == IMPOSSIBLE_COMPARISON)
294c85f09ccSJohn Levon 		return two;
295c85f09ccSJohn Levon 	if (two == IMPOSSIBLE_COMPARISON)
296c85f09ccSJohn Levon 		return one;
2971f5207b7SJohn Levon 
2981f5207b7SJohn Levon 	one = remove_unsigned_from_comparison(one);
2991f5207b7SJohn Levon 	two = remove_unsigned_from_comparison(two);
3001f5207b7SJohn Levon 
3011f5207b7SJohn Levon 	if (one == two)
3021f5207b7SJohn Levon 		return one;
3031f5207b7SJohn Levon 
3041f5207b7SJohn Levon 	LT = EQ = GT = 0;
3051f5207b7SJohn Levon 
3061f5207b7SJohn Levon 	switch (one) {
3071f5207b7SJohn Levon 	case '<':
3081f5207b7SJohn Levon 		LT = 1;
3091f5207b7SJohn Levon 		break;
3101f5207b7SJohn Levon 	case SPECIAL_LTE:
3111f5207b7SJohn Levon 		LT = 1;
3121f5207b7SJohn Levon 		EQ = 1;
3131f5207b7SJohn Levon 		break;
3141f5207b7SJohn Levon 	case SPECIAL_EQUAL:
3151f5207b7SJohn Levon 		EQ = 1;
3161f5207b7SJohn Levon 		break;
3171f5207b7SJohn Levon 	case SPECIAL_GTE:
3181f5207b7SJohn Levon 		GT = 1;
3191f5207b7SJohn Levon 		EQ = 1;
3201f5207b7SJohn Levon 		break;
3211f5207b7SJohn Levon 	case '>':
3221f5207b7SJohn Levon 		GT = 1;
3231f5207b7SJohn Levon 	}
3241f5207b7SJohn Levon 
3251f5207b7SJohn Levon 	switch (two) {
3261f5207b7SJohn Levon 	case '<':
3271f5207b7SJohn Levon 		LT = 1;
3281f5207b7SJohn Levon 		break;
3291f5207b7SJohn Levon 	case SPECIAL_LTE:
3301f5207b7SJohn Levon 		LT = 1;
3311f5207b7SJohn Levon 		EQ = 1;
3321f5207b7SJohn Levon 		break;
3331f5207b7SJohn Levon 	case SPECIAL_EQUAL:
3341f5207b7SJohn Levon 		EQ = 1;
3351f5207b7SJohn Levon 		break;
3361f5207b7SJohn Levon 	case SPECIAL_GTE:
3371f5207b7SJohn Levon 		GT = 1;
3381f5207b7SJohn Levon 		EQ = 1;
3391f5207b7SJohn Levon 		break;
3401f5207b7SJohn Levon 	case '>':
3411f5207b7SJohn Levon 		GT = 1;
3421f5207b7SJohn Levon 	}
3431f5207b7SJohn Levon 
3441f5207b7SJohn Levon 	if (LT && EQ && GT)
345c85f09ccSJohn Levon 		return UNKNOWN_COMPARISON;
3461f5207b7SJohn Levon 	if (LT && EQ)
3471f5207b7SJohn Levon 		return SPECIAL_LTE;
3481f5207b7SJohn Levon 	if (LT && GT)
3491f5207b7SJohn Levon 		return SPECIAL_NOTEQUAL;
3501f5207b7SJohn Levon 	if (LT)
3511f5207b7SJohn Levon 		return '<';
3521f5207b7SJohn Levon 	if (EQ && GT)
3531f5207b7SJohn Levon 		return SPECIAL_GTE;
3541f5207b7SJohn Levon 	if (GT)
3551f5207b7SJohn Levon 		return '>';
356c85f09ccSJohn Levon 	return UNKNOWN_COMPARISON;
3571f5207b7SJohn Levon }
3581f5207b7SJohn Levon 
3591f5207b7SJohn Levon /*
360c85f09ccSJohn Levon  * This is for if you have "a < b" and "b <= c" and you want to see how "a
361c85f09ccSJohn Levon  * compares to c".  You would call this like get_combined_comparison('<', '<=').
3621f5207b7SJohn Levon  * The return comparison would be '<'.
3631f5207b7SJohn Levon  */
combine_comparisons(int left_compare,int right_compare)3641f5207b7SJohn Levon int combine_comparisons(int left_compare, int right_compare)
3651f5207b7SJohn Levon {
3661f5207b7SJohn Levon 	int LT, EQ, GT;
3671f5207b7SJohn Levon 
3681f5207b7SJohn Levon 	left_compare = remove_unsigned_from_comparison(left_compare);
3691f5207b7SJohn Levon 	right_compare = remove_unsigned_from_comparison(right_compare);
3701f5207b7SJohn Levon 
3711f5207b7SJohn Levon 	LT = EQ = GT = 0;
3721f5207b7SJohn Levon 
3731f5207b7SJohn Levon 	switch (left_compare) {
3741f5207b7SJohn Levon 	case '<':
3751f5207b7SJohn Levon 		LT++;
3761f5207b7SJohn Levon 		break;
3771f5207b7SJohn Levon 	case SPECIAL_LTE:
3781f5207b7SJohn Levon 		LT++;
3791f5207b7SJohn Levon 		EQ++;
3801f5207b7SJohn Levon 		break;
3811f5207b7SJohn Levon 	case SPECIAL_EQUAL:
3821f5207b7SJohn Levon 		return right_compare;
3831f5207b7SJohn Levon 	case SPECIAL_GTE:
3841f5207b7SJohn Levon 		GT++;
3851f5207b7SJohn Levon 		EQ++;
3861f5207b7SJohn Levon 		break;
3871f5207b7SJohn Levon 	case '>':
3881f5207b7SJohn Levon 		GT++;
3891f5207b7SJohn Levon 	}
3901f5207b7SJohn Levon 
3911f5207b7SJohn Levon 	switch (right_compare) {
3921f5207b7SJohn Levon 	case '<':
3931f5207b7SJohn Levon 		LT++;
3941f5207b7SJohn Levon 		break;
3951f5207b7SJohn Levon 	case SPECIAL_LTE:
3961f5207b7SJohn Levon 		LT++;
3971f5207b7SJohn Levon 		EQ++;
3981f5207b7SJohn Levon 		break;
3991f5207b7SJohn Levon 	case SPECIAL_EQUAL:
4001f5207b7SJohn Levon 		return left_compare;
4011f5207b7SJohn Levon 	case SPECIAL_GTE:
4021f5207b7SJohn Levon 		GT++;
4031f5207b7SJohn Levon 		EQ++;
4041f5207b7SJohn Levon 		break;
4051f5207b7SJohn Levon 	case '>':
4061f5207b7SJohn Levon 		GT++;
4071f5207b7SJohn Levon 	}
4081f5207b7SJohn Levon 
4091f5207b7SJohn Levon 	if (LT == 2) {
4101f5207b7SJohn Levon 		if (EQ == 2)
4111f5207b7SJohn Levon 			return SPECIAL_LTE;
4121f5207b7SJohn Levon 		return '<';
4131f5207b7SJohn Levon 	}
4141f5207b7SJohn Levon 
4151f5207b7SJohn Levon 	if (GT == 2) {
4161f5207b7SJohn Levon 		if (EQ == 2)
4171f5207b7SJohn Levon 			return SPECIAL_GTE;
4181f5207b7SJohn Levon 		return '>';
4191f5207b7SJohn Levon 	}
420c85f09ccSJohn Levon 	return UNKNOWN_COMPARISON;
4211f5207b7SJohn Levon }
4221f5207b7SJohn Levon 
423c85f09ccSJohn Levon /*
424c85f09ccSJohn Levon  * This is mostly used when you know from extra state that a <= b but you
425c85f09ccSJohn Levon  * know from comparisons that a != b so then if take the intersection then
426c85f09ccSJohn Levon  * we know that a < b.  The name is taken from the fact that the intersection
427c85f09ccSJohn Levon  * of < and <= is <.
428c85f09ccSJohn Levon  */
comparison_intersection(int left_compare,int right_compare)429c85f09ccSJohn Levon int comparison_intersection(int left_compare, int right_compare)
4301f5207b7SJohn Levon {
431c85f09ccSJohn Levon 	int LT, GT, EQ, NE, total;
4321f5207b7SJohn Levon 
433c85f09ccSJohn Levon 	if (left_compare == IMPOSSIBLE_COMPARISON ||
434c85f09ccSJohn Levon 	    right_compare == IMPOSSIBLE_COMPARISON)
435c85f09ccSJohn Levon 		return IMPOSSIBLE_COMPARISON;
4361f5207b7SJohn Levon 
437c85f09ccSJohn Levon 	left_compare = remove_unsigned_from_comparison(left_compare);
438c85f09ccSJohn Levon 	right_compare = remove_unsigned_from_comparison(right_compare);
439c85f09ccSJohn Levon 
440c85f09ccSJohn Levon 	LT = GT = EQ = NE = total = 0;
441c85f09ccSJohn Levon 
442c85f09ccSJohn Levon 	/* Only one side is known. */
443c85f09ccSJohn Levon 	if (!left_compare)
444c85f09ccSJohn Levon 		return right_compare;
445c85f09ccSJohn Levon 	if (!right_compare)
446c85f09ccSJohn Levon 		return left_compare;
447c85f09ccSJohn Levon 
448c85f09ccSJohn Levon 	switch (left_compare) {
4491f5207b7SJohn Levon 	case '<':
450c85f09ccSJohn Levon 		LT++;
451c85f09ccSJohn Levon 		total += 1;
452c85f09ccSJohn Levon 		break;
4531f5207b7SJohn Levon 	case SPECIAL_LTE:
454c85f09ccSJohn Levon 		LT++;
455c85f09ccSJohn Levon 		EQ++;
456c85f09ccSJohn Levon 		total += 2;
457c85f09ccSJohn Levon 		break;
4581f5207b7SJohn Levon 	case SPECIAL_EQUAL:
459c85f09ccSJohn Levon 		EQ++;
460c85f09ccSJohn Levon 		total += 1;
461c85f09ccSJohn Levon 		break;
4621f5207b7SJohn Levon 	case SPECIAL_NOTEQUAL:
463c85f09ccSJohn Levon 		NE++;
464c85f09ccSJohn Levon 		total += 1;
465c85f09ccSJohn Levon 		break;
4661f5207b7SJohn Levon 	case SPECIAL_GTE:
467c85f09ccSJohn Levon 		GT++;
468c85f09ccSJohn Levon 		EQ++;
469c85f09ccSJohn Levon 		total += 2;
470c85f09ccSJohn Levon 		break;
4711f5207b7SJohn Levon 	case '>':
472c85f09ccSJohn Levon 		GT++;
473c85f09ccSJohn Levon 		total += 1;
474c85f09ccSJohn Levon 		break;
475c85f09ccSJohn Levon 	default:
476c85f09ccSJohn Levon 		return UNKNOWN_COMPARISON;
4771f5207b7SJohn Levon 	}
478c85f09ccSJohn Levon 
479c85f09ccSJohn Levon 	switch (right_compare) {
480c85f09ccSJohn Levon 	case '<':
481c85f09ccSJohn Levon 		LT++;
482c85f09ccSJohn Levon 		total += 1;
483c85f09ccSJohn Levon 		break;
484c85f09ccSJohn Levon 	case SPECIAL_LTE:
485c85f09ccSJohn Levon 		LT++;
486c85f09ccSJohn Levon 		EQ++;
487c85f09ccSJohn Levon 		total += 2;
488c85f09ccSJohn Levon 		break;
489c85f09ccSJohn Levon 	case SPECIAL_EQUAL:
490c85f09ccSJohn Levon 		EQ++;
491c85f09ccSJohn Levon 		total += 1;
492c85f09ccSJohn Levon 		break;
493c85f09ccSJohn Levon 	case SPECIAL_NOTEQUAL:
494c85f09ccSJohn Levon 		NE++;
495c85f09ccSJohn Levon 		total += 1;
496c85f09ccSJohn Levon 		break;
497c85f09ccSJohn Levon 	case SPECIAL_GTE:
498c85f09ccSJohn Levon 		GT++;
499c85f09ccSJohn Levon 		EQ++;
500c85f09ccSJohn Levon 		total += 2;
501c85f09ccSJohn Levon 		break;
502c85f09ccSJohn Levon 	case '>':
503c85f09ccSJohn Levon 		GT++;
504c85f09ccSJohn Levon 		total += 1;
505c85f09ccSJohn Levon 		break;
506c85f09ccSJohn Levon 	default:
507c85f09ccSJohn Levon 		return UNKNOWN_COMPARISON;
508c85f09ccSJohn Levon 	}
509c85f09ccSJohn Levon 
510c85f09ccSJohn Levon 	if (LT == 2) {
511c85f09ccSJohn Levon 		if (EQ == 2)
512c85f09ccSJohn Levon 			return SPECIAL_LTE;
513c85f09ccSJohn Levon 		return '<';
514c85f09ccSJohn Levon 	}
515c85f09ccSJohn Levon 
516c85f09ccSJohn Levon 	if (GT == 2) {
517c85f09ccSJohn Levon 		if (EQ == 2)
518c85f09ccSJohn Levon 			return SPECIAL_GTE;
519c85f09ccSJohn Levon 		return '>';
520c85f09ccSJohn Levon 	}
521c85f09ccSJohn Levon 	if (EQ == 2)
522c85f09ccSJohn Levon 		return SPECIAL_EQUAL;
523c85f09ccSJohn Levon 	if (total == 2 && EQ && NE)
524c85f09ccSJohn Levon 		return IMPOSSIBLE_COMPARISON;
525c85f09ccSJohn Levon 	if (GT && LT)
526c85f09ccSJohn Levon 		return IMPOSSIBLE_COMPARISON;
527c85f09ccSJohn Levon 	if (GT && NE)
528c85f09ccSJohn Levon 		return '>';
529c85f09ccSJohn Levon 	if (LT && NE)
530c85f09ccSJohn Levon 		return '<';
531c85f09ccSJohn Levon 	if (NE == 2)
532c85f09ccSJohn Levon 		return SPECIAL_NOTEQUAL;
533c85f09ccSJohn Levon 	if (total == 2 && (LT || GT) && EQ)
534c85f09ccSJohn Levon 		return IMPOSSIBLE_COMPARISON;
535c85f09ccSJohn Levon 
536c85f09ccSJohn Levon 	return UNKNOWN_COMPARISON;
5371f5207b7SJohn Levon }
5381f5207b7SJohn Levon 
pre_merge_hook(struct sm_state * cur,struct sm_state * other)539c85f09ccSJohn Levon static void pre_merge_hook(struct sm_state *cur, struct sm_state *other)
5401f5207b7SJohn Levon {
541c85f09ccSJohn Levon 	struct compare_data *data = cur->state->data;
542c85f09ccSJohn Levon 	int extra, new;
543c85f09ccSJohn Levon 	static bool in_recurse;
5441f5207b7SJohn Levon 
5455a0e240fSJohn Levon 	// FIXME.  No data is useless
5461f5207b7SJohn Levon 	if (!data)
5471f5207b7SJohn Levon 		return;
548c85f09ccSJohn Levon 
549c85f09ccSJohn Levon 	if (in_recurse)
550c85f09ccSJohn Levon 		return;
551c85f09ccSJohn Levon 	in_recurse = true;
552c85f09ccSJohn Levon 	extra = comparison_from_extra(data->left, data->right);
553c85f09ccSJohn Levon 	in_recurse = false;
554c85f09ccSJohn Levon 	if (!extra)
555c85f09ccSJohn Levon 		return;
556c85f09ccSJohn Levon 	new = comparison_intersection(extra, data->comparison);
557c85f09ccSJohn Levon 	if (new == data->comparison)
5581f5207b7SJohn Levon 		return;
5591f5207b7SJohn Levon 
5605a0e240fSJohn Levon 	// FIXME: we should always preserve implications
5615a0e240fSJohn Levon 	set_state(comparison_id, cur->name, NULL,
5621f5207b7SJohn Levon 		  alloc_compare_state(data->left, data->left_var, data->left_vsl,
563c85f09ccSJohn Levon 				      new,
5641f5207b7SJohn Levon 				      data->right, data->right_var, data->right_vsl));
5651f5207b7SJohn Levon }
5661f5207b7SJohn Levon 
merge_compare_states(struct smatch_state * s1,struct smatch_state * s2)5671f5207b7SJohn Levon struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2)
5681f5207b7SJohn Levon {
5691f5207b7SJohn Levon 	struct compare_data *data = s1->data;
5701f5207b7SJohn Levon 	int op;
5711f5207b7SJohn Levon 
572c85f09ccSJohn Levon 	if (!data)
573c85f09ccSJohn Levon 		return &undefined;
574c85f09ccSJohn Levon 
5751f5207b7SJohn Levon 	op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2));
576c85f09ccSJohn Levon 	return alloc_compare_state(
577c85f09ccSJohn Levon 			data->left, data->left_var, data->left_vsl,
578c85f09ccSJohn Levon 			op,
579c85f09ccSJohn Levon 			data->right, data->right_var, data->right_vsl);
5801f5207b7SJohn Levon }
5811f5207b7SJohn Levon 
alloc_link_state(struct string_list * links)5821f5207b7SJohn Levon static struct smatch_state *alloc_link_state(struct string_list *links)
5831f5207b7SJohn Levon {
5841f5207b7SJohn Levon 	struct smatch_state *state;
5851f5207b7SJohn Levon 	static char buf[256];
5861f5207b7SJohn Levon 	char *tmp;
5871f5207b7SJohn Levon 	int i;
5881f5207b7SJohn Levon 
5891f5207b7SJohn Levon 	state = __alloc_smatch_state(0);
5901f5207b7SJohn Levon 
5911f5207b7SJohn Levon 	i = 0;
5921f5207b7SJohn Levon 	FOR_EACH_PTR(links, tmp) {
5931f5207b7SJohn Levon 		if (!i++) {
5941f5207b7SJohn Levon 			snprintf(buf, sizeof(buf), "%s", tmp);
5951f5207b7SJohn Levon 		} else {
5961f5207b7SJohn Levon 			append(buf, ", ", sizeof(buf));
5971f5207b7SJohn Levon 			append(buf, tmp, sizeof(buf));
5981f5207b7SJohn Levon 		}
5991f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
6001f5207b7SJohn Levon 
6011f5207b7SJohn Levon 	state->name = alloc_sname(buf);
6021f5207b7SJohn Levon 	state->data = links;
6031f5207b7SJohn Levon 	return state;
6041f5207b7SJohn Levon }
6051f5207b7SJohn Levon 
save_start_states(struct statement * stmt)6061f5207b7SJohn Levon static void save_start_states(struct statement *stmt)
6071f5207b7SJohn Levon {
6081f5207b7SJohn Levon 	struct symbol *param;
6091f5207b7SJohn Levon 	char orig[64];
6101f5207b7SJohn Levon 	char state_name[128];
6111f5207b7SJohn Levon 	struct smatch_state *state;
6121f5207b7SJohn Levon 	struct string_list *links;
6131f5207b7SJohn Levon 	char *link;
6141f5207b7SJohn Levon 
6151f5207b7SJohn Levon 	FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
6161f5207b7SJohn Levon 		struct var_sym_list *left_vsl = NULL;
6171f5207b7SJohn Levon 		struct var_sym_list *right_vsl = NULL;
6181f5207b7SJohn Levon 
6191f5207b7SJohn Levon 		if (!param->ident)
6201f5207b7SJohn Levon 			continue;
6211f5207b7SJohn Levon 		snprintf(orig, sizeof(orig), "%s orig", param->ident->name);
6221f5207b7SJohn Levon 		snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig);
6231f5207b7SJohn Levon 		add_var_sym(&left_vsl, param->ident->name, param);
6241f5207b7SJohn Levon 		add_var_sym(&right_vsl, orig, param);
6251f5207b7SJohn Levon 		state = alloc_compare_state(
6261f5207b7SJohn Levon 				NULL, param->ident->name, left_vsl,
6271f5207b7SJohn Levon 				SPECIAL_EQUAL,
6281f5207b7SJohn Levon 				NULL, alloc_sname(orig), right_vsl);
6295a0e240fSJohn Levon 		set_state(comparison_id, state_name, NULL, state);
6301f5207b7SJohn Levon 
6311f5207b7SJohn Levon 		link = alloc_sname(state_name);
6321f5207b7SJohn Levon 		links = NULL;
6331f5207b7SJohn Levon 		insert_string(&links, link);
6341f5207b7SJohn Levon 		state = alloc_link_state(links);
6351f5207b7SJohn Levon 		set_state(link_id, param->ident->name, param, state);
6361f5207b7SJohn Levon 	} END_FOR_EACH_PTR(param);
6371f5207b7SJohn Levon }
6381f5207b7SJohn Levon 
merge_links(struct smatch_state * s1,struct smatch_state * s2)6391f5207b7SJohn Levon static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
6401f5207b7SJohn Levon {
6411f5207b7SJohn Levon 	struct smatch_state *ret;
6421f5207b7SJohn Levon 	struct string_list *links;
6431f5207b7SJohn Levon 
6441f5207b7SJohn Levon 	links = combine_string_lists(s1->data, s2->data);
6451f5207b7SJohn Levon 	ret = alloc_link_state(links);
6461f5207b7SJohn Levon 	return ret;
6471f5207b7SJohn Levon }
6481f5207b7SJohn Levon 
save_link_var_sym(const char * var,struct symbol * sym,const char * link)6491f5207b7SJohn Levon static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
6501f5207b7SJohn Levon {
6511f5207b7SJohn Levon 	struct smatch_state *old_state, *new_state;
6521f5207b7SJohn Levon 	struct string_list *links;
6531f5207b7SJohn Levon 	char *new;
6541f5207b7SJohn Levon 
6551f5207b7SJohn Levon 	old_state = get_state(link_id, var, sym);
6561f5207b7SJohn Levon 	if (old_state)
6571f5207b7SJohn Levon 		links = clone_str_list(old_state->data);
6581f5207b7SJohn Levon 	else
6591f5207b7SJohn Levon 		links = NULL;
6601f5207b7SJohn Levon 
6611f5207b7SJohn Levon 	new = alloc_sname(link);
6621f5207b7SJohn Levon 	insert_string(&links, new);
6631f5207b7SJohn Levon 
6641f5207b7SJohn Levon 	new_state = alloc_link_state(links);
6651f5207b7SJohn Levon 	set_state(link_id, var, sym, new_state);
6661f5207b7SJohn Levon }
6671f5207b7SJohn Levon 
match_inc(struct sm_state * sm,bool preserve)668efe51d0cSJohn Levon static void match_inc(struct sm_state *sm, bool preserve)
6691f5207b7SJohn Levon {
6701f5207b7SJohn Levon 	struct string_list *links;
6711f5207b7SJohn Levon 	struct smatch_state *state, *new;
6721f5207b7SJohn Levon 	struct compare_data *data;
6731f5207b7SJohn Levon 	char *tmp;
6741f5207b7SJohn Levon 	int flip;
6751f5207b7SJohn Levon 	int op;
6761f5207b7SJohn Levon 
6771f5207b7SJohn Levon 	links = sm->state->data;
6781f5207b7SJohn Levon 
6791f5207b7SJohn Levon 	FOR_EACH_PTR(links, tmp) {
6805a0e240fSJohn Levon 		state = get_state(comparison_id, tmp, NULL);
6811f5207b7SJohn Levon 		if (!state)
6821f5207b7SJohn Levon 			continue;
6831f5207b7SJohn Levon 		data = state->data;
6841f5207b7SJohn Levon 		if (!data)
6851f5207b7SJohn Levon 			continue;
6861f5207b7SJohn Levon 
6871f5207b7SJohn Levon 		flip = 0;
6881f5207b7SJohn Levon 		if (strncmp(sm->name, tmp, strlen(sm->name)) != 0 ||
6891f5207b7SJohn Levon 		    tmp[strlen(sm->name)] != ' ')
6901f5207b7SJohn Levon 			flip = 1;
6911f5207b7SJohn Levon 
6921f5207b7SJohn Levon 		op = state_to_comparison(state);
6931f5207b7SJohn Levon 
6941f5207b7SJohn Levon 		switch (flip ? flip_comparison(op) : op) {
6951f5207b7SJohn Levon 		case SPECIAL_EQUAL:
6961f5207b7SJohn Levon 		case SPECIAL_GTE:
6971f5207b7SJohn Levon 		case SPECIAL_UNSIGNED_GTE:
6981f5207b7SJohn Levon 		case '>':
6991f5207b7SJohn Levon 		case SPECIAL_UNSIGNED_GT:
700efe51d0cSJohn Levon 			if (preserve)
701efe51d0cSJohn Levon 				break;
7021f5207b7SJohn Levon 			new = alloc_compare_state(
7031f5207b7SJohn Levon 					data->left, data->left_var, data->left_vsl,
7041f5207b7SJohn Levon 					flip ? '<' : '>',
7051f5207b7SJohn Levon 					data->right, data->right_var, data->right_vsl);
7065a0e240fSJohn Levon 			set_state(comparison_id, tmp, NULL, new);
7071f5207b7SJohn Levon 			break;
7081f5207b7SJohn Levon 		case '<':
7091f5207b7SJohn Levon 		case SPECIAL_UNSIGNED_LT:
7101f5207b7SJohn Levon 			new = alloc_compare_state(
7111f5207b7SJohn Levon 					data->left, data->left_var, data->left_vsl,
7121f5207b7SJohn Levon 					flip ? SPECIAL_GTE : SPECIAL_LTE,
7131f5207b7SJohn Levon 					data->right, data->right_var, data->right_vsl);
7145a0e240fSJohn Levon 			set_state(comparison_id, tmp, NULL, new);
7151f5207b7SJohn Levon 			break;
7161f5207b7SJohn Levon 		default:
717c85f09ccSJohn Levon 			new = alloc_compare_state(
718c85f09ccSJohn Levon 					data->left, data->left_var, data->left_vsl,
719c85f09ccSJohn Levon 					UNKNOWN_COMPARISON,
720c85f09ccSJohn Levon 					data->right, data->right_var, data->right_vsl);
7215a0e240fSJohn Levon 			set_state(comparison_id, tmp, NULL, new);
7221f5207b7SJohn Levon 		}
7231f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
7241f5207b7SJohn Levon }
7251f5207b7SJohn Levon 
match_dec(struct sm_state * sm,bool preserve)726efe51d0cSJohn Levon static void match_dec(struct sm_state *sm, bool preserve)
7271f5207b7SJohn Levon {
7281f5207b7SJohn Levon 	struct string_list *links;
7291f5207b7SJohn Levon 	struct smatch_state *state;
7301f5207b7SJohn Levon 	char *tmp;
7311f5207b7SJohn Levon 
7321f5207b7SJohn Levon 	links = sm->state->data;
7331f5207b7SJohn Levon 
7341f5207b7SJohn Levon 	FOR_EACH_PTR(links, tmp) {
735c85f09ccSJohn Levon 		struct compare_data *data;
736c85f09ccSJohn Levon 		struct smatch_state *new;
737c85f09ccSJohn Levon 
7385a0e240fSJohn Levon 		state = get_state(comparison_id, tmp, NULL);
739c85f09ccSJohn Levon 		if (!state || !state->data)
740c85f09ccSJohn Levon 			continue;
741c85f09ccSJohn Levon 
742c85f09ccSJohn Levon 		data = state->data;
7431f5207b7SJohn Levon 
7441f5207b7SJohn Levon 		switch (state_to_comparison(state)) {
7451f5207b7SJohn Levon 		case SPECIAL_EQUAL:
7461f5207b7SJohn Levon 		case SPECIAL_LTE:
7471f5207b7SJohn Levon 		case SPECIAL_UNSIGNED_LTE:
7481f5207b7SJohn Levon 		case '<':
7491f5207b7SJohn Levon 		case SPECIAL_UNSIGNED_LT: {
750efe51d0cSJohn Levon 			if (preserve)
751efe51d0cSJohn Levon 				break;
752efe51d0cSJohn Levon 
7531f5207b7SJohn Levon 			new = alloc_compare_state(
7541f5207b7SJohn Levon 					data->left, data->left_var, data->left_vsl,
7551f5207b7SJohn Levon 					'<',
7561f5207b7SJohn Levon 					data->right, data->right_var, data->right_vsl);
7575a0e240fSJohn Levon 			set_state(comparison_id, tmp, NULL, new);
7581f5207b7SJohn Levon 			break;
7591f5207b7SJohn Levon 			}
7601f5207b7SJohn Levon 		default:
761c85f09ccSJohn Levon 			new = alloc_compare_state(
762c85f09ccSJohn Levon 					data->left, data->left_var, data->left_vsl,
763c85f09ccSJohn Levon 					UNKNOWN_COMPARISON,
764c85f09ccSJohn Levon 					data->right, data->right_var, data->right_vsl);
7655a0e240fSJohn Levon 			set_state(comparison_id, tmp, NULL, new);
7661f5207b7SJohn Levon 		}
7671f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
7681f5207b7SJohn Levon }
7691f5207b7SJohn Levon 
reset_sm(struct sm_state * sm)770efe51d0cSJohn Levon static void reset_sm(struct sm_state *sm)
771efe51d0cSJohn Levon {
772efe51d0cSJohn Levon 	struct string_list *links;
773efe51d0cSJohn Levon 	char *tmp;
774efe51d0cSJohn Levon 
775efe51d0cSJohn Levon 	links = sm->state->data;
776efe51d0cSJohn Levon 
777efe51d0cSJohn Levon 	FOR_EACH_PTR(links, tmp) {
778c85f09ccSJohn Levon 		struct smatch_state *old, *new;
779c85f09ccSJohn Levon 
7805a0e240fSJohn Levon 		old = get_state(comparison_id, tmp, NULL);
781c85f09ccSJohn Levon 		if (!old || !old->data) {
782c85f09ccSJohn Levon 			new = &undefined;
783c85f09ccSJohn Levon 		} else {
784c85f09ccSJohn Levon 			struct compare_data *data = old->data;
785c85f09ccSJohn Levon 
786c85f09ccSJohn Levon 			new = alloc_compare_state(
787c85f09ccSJohn Levon 					data->left, data->left_var, data->left_vsl,
788c85f09ccSJohn Levon 					UNKNOWN_COMPARISON,
789c85f09ccSJohn Levon 					data->right, data->right_var, data->right_vsl);
790c85f09ccSJohn Levon 		}
7915a0e240fSJohn Levon 		set_state(comparison_id, tmp, NULL, new);
792efe51d0cSJohn Levon 	} END_FOR_EACH_PTR(tmp);
793efe51d0cSJohn Levon 	set_state(link_id, sm->name, sm->sym, &undefined);
794efe51d0cSJohn Levon }
795efe51d0cSJohn Levon 
match_add_sub_assign(struct sm_state * sm,struct expression * expr)796efe51d0cSJohn Levon static bool match_add_sub_assign(struct sm_state *sm, struct expression *expr)
797efe51d0cSJohn Levon {
798efe51d0cSJohn Levon 	struct range_list *rl;
799efe51d0cSJohn Levon 	sval_t zero = { .type = &int_ctype };
800efe51d0cSJohn Levon 
801efe51d0cSJohn Levon 	if (!expr || expr->type != EXPR_ASSIGNMENT)
802efe51d0cSJohn Levon 		return false;
803efe51d0cSJohn Levon 	if (expr->op != SPECIAL_ADD_ASSIGN && expr->op != SPECIAL_SUB_ASSIGN)
804efe51d0cSJohn Levon 		return false;
805efe51d0cSJohn Levon 
806efe51d0cSJohn Levon 	get_absolute_rl(expr->right, &rl);
807efe51d0cSJohn Levon 	if (sval_is_negative(rl_min(rl))) {
808efe51d0cSJohn Levon 		reset_sm(sm);
809efe51d0cSJohn Levon 		return false;
810efe51d0cSJohn Levon 	}
811efe51d0cSJohn Levon 
812efe51d0cSJohn Levon 	if (expr->op == SPECIAL_ADD_ASSIGN)
813efe51d0cSJohn Levon 		match_inc(sm, rl_has_sval(rl, zero));
814efe51d0cSJohn Levon 	else
815efe51d0cSJohn Levon 		match_dec(sm, rl_has_sval(rl, zero));
816efe51d0cSJohn Levon 	return true;
817efe51d0cSJohn Levon }
818efe51d0cSJohn Levon 
match_inc_dec(struct sm_state * sm,struct expression * mod_expr)8191f5207b7SJohn Levon static void match_inc_dec(struct sm_state *sm, struct expression *mod_expr)
8201f5207b7SJohn Levon {
8211f5207b7SJohn Levon 	/*
8221f5207b7SJohn Levon 	 * if (foo > bar) then ++foo is also > bar.
8231f5207b7SJohn Levon 	 */
8241f5207b7SJohn Levon 	if (!mod_expr)
8251f5207b7SJohn Levon 		return;
826efe51d0cSJohn Levon 	if (match_add_sub_assign(sm, mod_expr))
827efe51d0cSJohn Levon 		return;
8281f5207b7SJohn Levon 	if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP)
8291f5207b7SJohn Levon 		return;
8301f5207b7SJohn Levon 
8311f5207b7SJohn Levon 	if (mod_expr->op == SPECIAL_INCREMENT)
832efe51d0cSJohn Levon 		match_inc(sm, false);
8331f5207b7SJohn Levon 	else if (mod_expr->op == SPECIAL_DECREMENT)
834efe51d0cSJohn Levon 		match_dec(sm, false);
8351f5207b7SJohn Levon }
8361f5207b7SJohn Levon 
is_self_assign(struct expression * expr)8371f5207b7SJohn Levon static int is_self_assign(struct expression *expr)
8381f5207b7SJohn Levon {
8391f5207b7SJohn Levon 	if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=')
8401f5207b7SJohn Levon 		return 0;
8411f5207b7SJohn Levon 	return expr_equiv(expr->left, expr->right);
8421f5207b7SJohn Levon }
8431f5207b7SJohn Levon 
match_modify(struct sm_state * sm,struct expression * mod_expr)8441f5207b7SJohn Levon static void match_modify(struct sm_state *sm, struct expression *mod_expr)
8451f5207b7SJohn Levon {
8461f5207b7SJohn Levon 	if (mod_expr && is_self_assign(mod_expr))
8471f5207b7SJohn Levon 		return;
8481f5207b7SJohn Levon 
8491f5207b7SJohn Levon 	/* handled by match_inc_dec() */
8501f5207b7SJohn Levon 	if (mod_expr &&
8511f5207b7SJohn Levon 	    ((mod_expr->type == EXPR_PREOP || mod_expr->type == EXPR_POSTOP) &&
8521f5207b7SJohn Levon 	     (mod_expr->op == SPECIAL_INCREMENT || mod_expr->op == SPECIAL_DECREMENT)))
8531f5207b7SJohn Levon 		return;
854efe51d0cSJohn Levon 	if (mod_expr && mod_expr->type == EXPR_ASSIGNMENT &&
855efe51d0cSJohn Levon 	    (mod_expr->op == SPECIAL_ADD_ASSIGN || mod_expr->op == SPECIAL_SUB_ASSIGN))
856efe51d0cSJohn Levon 		return;
8571f5207b7SJohn Levon 
858efe51d0cSJohn Levon 	reset_sm(sm);
8591f5207b7SJohn Levon }
8601f5207b7SJohn Levon 
match_preop(struct expression * expr)8611f5207b7SJohn Levon static void match_preop(struct expression *expr)
8621f5207b7SJohn Levon {
8631f5207b7SJohn Levon 	struct expression *parent;
8641f5207b7SJohn Levon 	struct range_list *left, *right;
8651f5207b7SJohn Levon 	int op;
8661f5207b7SJohn Levon 
8671f5207b7SJohn Levon 	/*
8681f5207b7SJohn Levon 	 * This is an important special case.  Say you have:
8691f5207b7SJohn Levon 	 *
8701f5207b7SJohn Levon 	 * 	if (++j == limit)
8711f5207b7SJohn Levon 	 *
8721f5207b7SJohn Levon 	 * Assume that we know the range of limit is higher than the start
8731f5207b7SJohn Levon 	 * value for "j".  Then the first thing that we process is the ++j.  We
8741f5207b7SJohn Levon 	 * have not comparison states set up so it doesn't get caught by the
8751f5207b7SJohn Levon 	 * modification hook.  But it does get caught by smatch_extra which sets
8761f5207b7SJohn Levon 	 * j to unknown then we parse the "j == limit" and sets false to != but
8771f5207b7SJohn Levon 	 * really we want false to be <.
8781f5207b7SJohn Levon 	 *
8791f5207b7SJohn Levon 	 * So what we do is we set j < limit here, then the match_modify catches
8801f5207b7SJohn Levon 	 * it and we do a match_inc_dec().
8811f5207b7SJohn Levon 	 *
8821f5207b7SJohn Levon 	 */
8831f5207b7SJohn Levon 
8841f5207b7SJohn Levon 	if (expr->type != EXPR_PREOP ||
8851f5207b7SJohn Levon 	    (expr->op != SPECIAL_INCREMENT && expr->op != SPECIAL_DECREMENT))
8861f5207b7SJohn Levon 		return;
8871f5207b7SJohn Levon 
8881f5207b7SJohn Levon 	parent = expr_get_parent_expr(expr);
8891f5207b7SJohn Levon 	if (!parent)
8901f5207b7SJohn Levon 		return;
8911f5207b7SJohn Levon 	if (parent->type != EXPR_COMPARE || parent->op != SPECIAL_EQUAL)
8921f5207b7SJohn Levon 		return;
8931f5207b7SJohn Levon 	if (parent->left != expr)
8941f5207b7SJohn Levon 		return;
8951f5207b7SJohn Levon 
8961f5207b7SJohn Levon 	if (!get_implied_rl(expr->unop, &left) ||
8971f5207b7SJohn Levon 	   !get_implied_rl(parent->right, &right))
8981f5207b7SJohn Levon 		return;
8991f5207b7SJohn Levon 
9001f5207b7SJohn Levon 	op = rl_comparison(left, right);
901c85f09ccSJohn Levon 	if (op == UNKNOWN_COMPARISON)
9021f5207b7SJohn Levon 		return;
9031f5207b7SJohn Levon 
9041f5207b7SJohn Levon 	add_comparison(expr->unop, op, parent->right);
9051f5207b7SJohn Levon }
9061f5207b7SJohn Levon 
chunk_to_var_sym(struct expression * expr,struct symbol ** sym)9071f5207b7SJohn Levon static char *chunk_to_var_sym(struct expression *expr, struct symbol **sym)
9081f5207b7SJohn Levon {
9091f5207b7SJohn Levon 	expr = strip_expr(expr);
9101f5207b7SJohn Levon 	if (!expr)
9111f5207b7SJohn Levon 		return NULL;
9121f5207b7SJohn Levon 	if (sym)
9131f5207b7SJohn Levon 		*sym = NULL;
9141f5207b7SJohn Levon 
9151f5207b7SJohn Levon 	if (expr->type == EXPR_PREOP &&
9161f5207b7SJohn Levon 	    (expr->op == SPECIAL_INCREMENT ||
9171f5207b7SJohn Levon 	     expr->op == SPECIAL_DECREMENT))
9181f5207b7SJohn Levon 		expr = strip_expr(expr->unop);
9191f5207b7SJohn Levon 
9201f5207b7SJohn Levon 	if (expr->type == EXPR_CALL) {
9211f5207b7SJohn Levon 		char buf[64];
9221f5207b7SJohn Levon 
9231f5207b7SJohn Levon 		snprintf(buf, sizeof(buf), "return %p", expr);
9241f5207b7SJohn Levon 		return alloc_string(buf);
9251f5207b7SJohn Levon 	}
9261f5207b7SJohn Levon 
9271f5207b7SJohn Levon 	return expr_to_chunk_sym_vsl(expr, sym, NULL);
9281f5207b7SJohn Levon }
9291f5207b7SJohn Levon 
chunk_to_var(struct expression * expr)9301f5207b7SJohn Levon static char *chunk_to_var(struct expression *expr)
9311f5207b7SJohn Levon {
9321f5207b7SJohn Levon 	return chunk_to_var_sym(expr, NULL);
9331f5207b7SJohn Levon }
9341f5207b7SJohn Levon 
get_state_chunk(int owner,struct expression * expr)9351f5207b7SJohn Levon static struct smatch_state *get_state_chunk(int owner, struct expression *expr)
9361f5207b7SJohn Levon {
9371f5207b7SJohn Levon 	char *name;
9381f5207b7SJohn Levon 	struct symbol *sym;
9391f5207b7SJohn Levon 	struct smatch_state *ret;
9401f5207b7SJohn Levon 
9411f5207b7SJohn Levon 	name = chunk_to_var_sym(expr, &sym);
9421f5207b7SJohn Levon 	if (!name)
9431f5207b7SJohn Levon 		return NULL;
9441f5207b7SJohn Levon 
9451f5207b7SJohn Levon 	ret = get_state(owner, name, sym);
9461f5207b7SJohn Levon 	free_string(name);
9471f5207b7SJohn Levon 	return ret;
9481f5207b7SJohn Levon }
9491f5207b7SJohn Levon 
save_link(struct expression * expr,char * link)9501f5207b7SJohn Levon static void save_link(struct expression *expr, char *link)
9511f5207b7SJohn Levon {
9521f5207b7SJohn Levon 	char *var;
9531f5207b7SJohn Levon 	struct symbol *sym;
9541f5207b7SJohn Levon 
9551f5207b7SJohn Levon 	expr = strip_expr(expr);
9561f5207b7SJohn Levon 	if (expr->type == EXPR_BINOP) {
9571f5207b7SJohn Levon 		char *chunk;
9581f5207b7SJohn Levon 
9591f5207b7SJohn Levon 		chunk = chunk_to_var(expr);
9601f5207b7SJohn Levon 		if (!chunk)
9611f5207b7SJohn Levon 			return;
9621f5207b7SJohn Levon 
9631f5207b7SJohn Levon 		save_link(expr->left, link);
9641f5207b7SJohn Levon 		save_link(expr->right, link);
9651f5207b7SJohn Levon 		save_link_var_sym(chunk, NULL, link);
9661f5207b7SJohn Levon 		return;
9671f5207b7SJohn Levon 	}
9681f5207b7SJohn Levon 
9691f5207b7SJohn Levon 	var = chunk_to_var_sym(expr, &sym);
9701f5207b7SJohn Levon 	if (!var)
9711f5207b7SJohn Levon 		return;
9721f5207b7SJohn Levon 
9731f5207b7SJohn Levon 	save_link_var_sym(var, sym, link);
9741f5207b7SJohn Levon 	free_string(var);
9751f5207b7SJohn Levon }
9761f5207b7SJohn Levon 
get_orig_comparison(struct stree * pre_stree,const char * left,const char * right)9771f5207b7SJohn Levon static int get_orig_comparison(struct stree *pre_stree, const char *left, const char *right)
9781f5207b7SJohn Levon {
9791f5207b7SJohn Levon 	struct smatch_state *state;
9801f5207b7SJohn Levon 	struct compare_data *data;
9811f5207b7SJohn Levon 	int flip = 0;
9821f5207b7SJohn Levon 	char state_name[256];
9831f5207b7SJohn Levon 
9841f5207b7SJohn Levon 	if (strcmp(left, right) > 0) {
9851f5207b7SJohn Levon 		const char *tmp = right;
9861f5207b7SJohn Levon 
9871f5207b7SJohn Levon 		flip = 1;
9881f5207b7SJohn Levon 		right = left;
9891f5207b7SJohn Levon 		left = tmp;
9901f5207b7SJohn Levon 	}
9911f5207b7SJohn Levon 
9921f5207b7SJohn Levon 	snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
9935a0e240fSJohn Levon 	state = get_state_stree(pre_stree, comparison_id, state_name, NULL);
9941f5207b7SJohn Levon 	if (!state || !state->data)
9951f5207b7SJohn Levon 		return 0;
9961f5207b7SJohn Levon 	data = state->data;
9971f5207b7SJohn Levon 	if (flip)
9981f5207b7SJohn Levon 		return flip_comparison(data->comparison);
9991f5207b7SJohn Levon 	return data->comparison;
10001f5207b7SJohn Levon 
10011f5207b7SJohn Levon }
10021f5207b7SJohn Levon 
have_common_var_sym(struct var_sym_list * left_vsl,struct var_sym_list * right_vsl)10031f5207b7SJohn Levon static int have_common_var_sym(struct var_sym_list *left_vsl, struct var_sym_list *right_vsl)
10041f5207b7SJohn Levon {
10051f5207b7SJohn Levon 	struct var_sym *tmp;
10061f5207b7SJohn Levon 
10071f5207b7SJohn Levon 	FOR_EACH_PTR(left_vsl, tmp) {
10081f5207b7SJohn Levon 		if (in_var_sym_list(right_vsl, tmp->var, tmp->sym))
10091f5207b7SJohn Levon 			return 1;
10101f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
10111f5207b7SJohn Levon 
10121f5207b7SJohn Levon 	return 0;
10131f5207b7SJohn Levon }
10141f5207b7SJohn Levon 
10151f5207b7SJohn Levon /*
10161f5207b7SJohn Levon  * The idea here is that we take a comparison "a < b" and then we look at all
10171f5207b7SJohn Levon  * the things which "b" is compared against "b < c" and we say that that implies
10181f5207b7SJohn Levon  * a relationship "a < c".
10191f5207b7SJohn Levon  *
10201f5207b7SJohn Levon  * The names here about because the comparisons are organized like this
10211f5207b7SJohn Levon  * "a < b < c".
10221f5207b7SJohn Levon  *
10231f5207b7SJohn Levon  */
update_tf_links(struct stree * pre_stree,struct expression * left_expr,const char * left_var,struct var_sym_list * left_vsl,int left_comparison,int left_false_comparison,const char * mid_var,struct var_sym_list * mid_vsl,struct string_list * links)10241f5207b7SJohn Levon static void update_tf_links(struct stree *pre_stree,
10251f5207b7SJohn Levon 			    struct expression *left_expr,
10261f5207b7SJohn Levon 			    const char *left_var, struct var_sym_list *left_vsl,
10271f5207b7SJohn Levon 			    int left_comparison, int left_false_comparison,
10281f5207b7SJohn Levon 			    const char *mid_var, struct var_sym_list *mid_vsl,
10291f5207b7SJohn Levon 			    struct string_list *links)
10301f5207b7SJohn Levon {
10311f5207b7SJohn Levon 	struct smatch_state *state;
10321f5207b7SJohn Levon 	struct smatch_state *true_state, *false_state;
10331f5207b7SJohn Levon 	struct compare_data *data;
10341f5207b7SJohn Levon 	struct expression *right_expr;
10351f5207b7SJohn Levon 	const char *right_var;
10361f5207b7SJohn Levon 	struct var_sym_list *right_vsl;
10371f5207b7SJohn Levon 	int orig_comparison;
10381f5207b7SJohn Levon 	int right_comparison;
10391f5207b7SJohn Levon 	int true_comparison;
10401f5207b7SJohn Levon 	int false_comparison;
10411f5207b7SJohn Levon 	char *tmp;
10421f5207b7SJohn Levon 	char state_name[256];
10431f5207b7SJohn Levon 	struct var_sym *vs;
10441f5207b7SJohn Levon 
10451f5207b7SJohn Levon 	FOR_EACH_PTR(links, tmp) {
10465a0e240fSJohn Levon 		state = get_state_stree(pre_stree, comparison_id, tmp, NULL);
10471f5207b7SJohn Levon 		if (!state || !state->data)
10481f5207b7SJohn Levon 			continue;
10491f5207b7SJohn Levon 		data = state->data;
10501f5207b7SJohn Levon 		right_comparison = data->comparison;
10511f5207b7SJohn Levon 		right_expr = data->right;
10521f5207b7SJohn Levon 		right_var = data->right_var;
10531f5207b7SJohn Levon 		right_vsl = data->right_vsl;
10541f5207b7SJohn Levon 		if (strcmp(mid_var, right_var) == 0) {
10551f5207b7SJohn Levon 			right_expr = data->left;
10561f5207b7SJohn Levon 			right_var = data->left_var;
10571f5207b7SJohn Levon 			right_vsl = data->left_vsl;
10581f5207b7SJohn Levon 			right_comparison = flip_comparison(right_comparison);
10591f5207b7SJohn Levon 		}
10601f5207b7SJohn Levon 		if (have_common_var_sym(left_vsl, right_vsl))
10611f5207b7SJohn Levon 			continue;
10621f5207b7SJohn Levon 
10631f5207b7SJohn Levon 		orig_comparison = get_orig_comparison(pre_stree, left_var, right_var);
10641f5207b7SJohn Levon 
10651f5207b7SJohn Levon 		true_comparison = combine_comparisons(left_comparison, right_comparison);
10661f5207b7SJohn Levon 		false_comparison = combine_comparisons(left_false_comparison, right_comparison);
10671f5207b7SJohn Levon 
1068c85f09ccSJohn Levon 		true_comparison = comparison_intersection(orig_comparison, true_comparison);
1069c85f09ccSJohn Levon 		false_comparison = comparison_intersection(orig_comparison, false_comparison);
10701f5207b7SJohn Levon 
10711f5207b7SJohn Levon 		if (strcmp(left_var, right_var) > 0) {
10721f5207b7SJohn Levon 		  	struct expression *tmp_expr = left_expr;
10731f5207b7SJohn Levon 			const char *tmp_var = left_var;
10741f5207b7SJohn Levon 			struct var_sym_list *tmp_vsl = left_vsl;
10751f5207b7SJohn Levon 
10761f5207b7SJohn Levon 			left_expr = right_expr;
10771f5207b7SJohn Levon 			left_var = right_var;
10781f5207b7SJohn Levon 			left_vsl = right_vsl;
10791f5207b7SJohn Levon 			right_expr = tmp_expr;
10801f5207b7SJohn Levon 			right_var = tmp_var;
10811f5207b7SJohn Levon 			right_vsl = tmp_vsl;
10821f5207b7SJohn Levon 			true_comparison = flip_comparison(true_comparison);
10831f5207b7SJohn Levon 			false_comparison = flip_comparison(false_comparison);
10841f5207b7SJohn Levon 		}
10851f5207b7SJohn Levon 
10861f5207b7SJohn Levon 		if (!true_comparison && !false_comparison)
10871f5207b7SJohn Levon 			continue;
10881f5207b7SJohn Levon 
10891f5207b7SJohn Levon 		if (true_comparison)
10901f5207b7SJohn Levon 			true_state = alloc_compare_state(
10911f5207b7SJohn Levon 					left_expr, left_var, left_vsl,
10921f5207b7SJohn Levon 					true_comparison,
10931f5207b7SJohn Levon 					right_expr, right_var, right_vsl);
10941f5207b7SJohn Levon 		else
10951f5207b7SJohn Levon 			true_state = NULL;
10961f5207b7SJohn Levon 		if (false_comparison)
10971f5207b7SJohn Levon 			false_state = alloc_compare_state(
10981f5207b7SJohn Levon 					left_expr, left_var, left_vsl,
10991f5207b7SJohn Levon 					false_comparison,
11001f5207b7SJohn Levon 					right_expr, right_var, right_vsl);
11011f5207b7SJohn Levon 		else
11021f5207b7SJohn Levon 			false_state = NULL;
11031f5207b7SJohn Levon 
11041f5207b7SJohn Levon 		snprintf(state_name, sizeof(state_name), "%s vs %s", left_var, right_var);
11055a0e240fSJohn Levon 		set_true_false_states(comparison_id, state_name, NULL, true_state, false_state);
11061f5207b7SJohn Levon 		FOR_EACH_PTR(left_vsl, vs) {
11071f5207b7SJohn Levon 			save_link_var_sym(vs->var, vs->sym, state_name);
11081f5207b7SJohn Levon 		} END_FOR_EACH_PTR(vs);
11091f5207b7SJohn Levon 		FOR_EACH_PTR(right_vsl, vs) {
11101f5207b7SJohn Levon 			save_link_var_sym(vs->var, vs->sym, state_name);
11111f5207b7SJohn Levon 		} END_FOR_EACH_PTR(vs);
11121f5207b7SJohn Levon 		if (!vsl_to_sym(left_vsl))
11131f5207b7SJohn Levon 			save_link_var_sym(left_var, NULL, state_name);
11141f5207b7SJohn Levon 		if (!vsl_to_sym(right_vsl))
11151f5207b7SJohn Levon 			save_link_var_sym(right_var, NULL, state_name);
11161f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
11171f5207b7SJohn Levon }
11181f5207b7SJohn Levon 
update_tf_data(struct stree * pre_stree,struct expression * left_expr,const char * left_name,struct var_sym_list * left_vsl,struct expression * right_expr,const char * right_name,struct var_sym_list * right_vsl,int true_comparison,int false_comparison)11191f5207b7SJohn Levon static void update_tf_data(struct stree *pre_stree,
11201f5207b7SJohn Levon 		struct expression *left_expr,
11211f5207b7SJohn Levon 		const char *left_name, struct var_sym_list *left_vsl,
11221f5207b7SJohn Levon 		struct expression *right_expr,
11231f5207b7SJohn Levon 		const char *right_name, struct var_sym_list *right_vsl,
11241f5207b7SJohn Levon 		int true_comparison, int false_comparison)
11251f5207b7SJohn Levon {
11261f5207b7SJohn Levon 	struct smatch_state *state;
11271f5207b7SJohn Levon 
11281f5207b7SJohn Levon 	state = get_state_stree(pre_stree, link_id, right_name, vsl_to_sym(right_vsl));
11291f5207b7SJohn Levon 	if (state)
11301f5207b7SJohn Levon 		update_tf_links(pre_stree, left_expr, left_name, left_vsl, true_comparison, false_comparison, right_name, right_vsl, state->data);
11311f5207b7SJohn Levon 
11321f5207b7SJohn Levon 	state = get_state_stree(pre_stree, link_id, left_name, vsl_to_sym(left_vsl));
11331f5207b7SJohn Levon 	if (state)
11341f5207b7SJohn Levon 		update_tf_links(pre_stree, right_expr, right_name, right_vsl, flip_comparison(true_comparison), flip_comparison(false_comparison), left_name, left_vsl, state->data);
11351f5207b7SJohn Levon }
11361f5207b7SJohn Levon 
iter_modify(struct sm_state * sm,struct expression * mod_expr)11371f5207b7SJohn Levon static void iter_modify(struct sm_state *sm, struct expression *mod_expr)
11381f5207b7SJohn Levon {
11391f5207b7SJohn Levon 	if (sm->state != &start ||
11401f5207b7SJohn Levon 	    !mod_expr ||
11411f5207b7SJohn Levon 	    (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP) ||
11421f5207b7SJohn Levon 	    mod_expr->op != SPECIAL_INCREMENT)
11431f5207b7SJohn Levon 		set_state(inc_dec_id, sm->name, sm->sym, &undefined);
11441f5207b7SJohn Levon 	else
11451f5207b7SJohn Levon 		set_state(inc_dec_id, sm->name, sm->sym, &incremented);
11461f5207b7SJohn Levon }
11471f5207b7SJohn Levon 
handle_for_loops(struct expression * expr,char * state_name,struct smatch_state * false_state)11481f5207b7SJohn Levon static void handle_for_loops(struct expression *expr, char *state_name, struct smatch_state *false_state)
11491f5207b7SJohn Levon {
11501f5207b7SJohn Levon 	sval_t sval;
11511f5207b7SJohn Levon 	char *iter_name, *cap_name;
11521f5207b7SJohn Levon 	struct symbol *iter_sym, *cap_sym;
11531f5207b7SJohn Levon 	struct compare_data *data;
11541f5207b7SJohn Levon 
11551f5207b7SJohn Levon 	if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
11561f5207b7SJohn Levon 		return;
11571f5207b7SJohn Levon 
11581f5207b7SJohn Levon 	if (!__cur_stmt || !__prev_stmt)
11591f5207b7SJohn Levon 		return;
11601f5207b7SJohn Levon 	if (__cur_stmt->type != STMT_ITERATOR)
11611f5207b7SJohn Levon 		return;
11621f5207b7SJohn Levon 	if (__cur_stmt->iterator_pre_condition != expr)
11631f5207b7SJohn Levon 		return;
11641f5207b7SJohn Levon 
11651f5207b7SJohn Levon 	/* literals are handled in smatch_extra.c */
11661f5207b7SJohn Levon 	if (get_value(expr->right, &sval))
11671f5207b7SJohn Levon 		return;
11681f5207b7SJohn Levon 
11691f5207b7SJohn Levon 	/* First time checking the condition */
11701f5207b7SJohn Levon 	if (__prev_stmt == __cur_stmt->iterator_pre_statement) {
11711f5207b7SJohn Levon 		if (!get_implied_value(expr->left, &sval) ||
11721f5207b7SJohn Levon 		    sval.value != 0)
11731f5207b7SJohn Levon 			return;
11741f5207b7SJohn Levon 
11751f5207b7SJohn Levon 		iter_name = expr_to_var_sym(expr->left, &iter_sym);
11761f5207b7SJohn Levon 		cap_name = expr_to_var_sym(expr->right, &cap_sym);
11771f5207b7SJohn Levon 		if (!iter_name || !cap_name || !iter_sym || !cap_sym) {
11781f5207b7SJohn Levon 			free_string(iter_name);
11791f5207b7SJohn Levon 			free_string(cap_name);
11801f5207b7SJohn Levon 			return;
11811f5207b7SJohn Levon 		}
11821f5207b7SJohn Levon 
11831f5207b7SJohn Levon 		set_state(inc_dec_id, iter_name, iter_sym, &start);
11841f5207b7SJohn Levon 		store_link(inc_dec_link_id, cap_name, cap_sym, iter_name, iter_sym);
11851f5207b7SJohn Levon 
11861f5207b7SJohn Levon 		free_string(iter_name);
11871f5207b7SJohn Levon 		free_string(cap_name);
11881f5207b7SJohn Levon 		return;
11891f5207b7SJohn Levon 	}
11901f5207b7SJohn Levon 
11911f5207b7SJohn Levon 	/* Second time checking the condtion */
11921f5207b7SJohn Levon 	if (__prev_stmt != __cur_stmt->iterator_post_statement)
11931f5207b7SJohn Levon 		return;
11941f5207b7SJohn Levon 
11951f5207b7SJohn Levon 	if (get_state_chunk(inc_dec_id, expr->left) != &incremented)
11961f5207b7SJohn Levon 		return;
11971f5207b7SJohn Levon 
11981f5207b7SJohn Levon 	data = false_state->data;
11991f5207b7SJohn Levon 	false_state = alloc_compare_state(
12001f5207b7SJohn Levon 			data->left, data->left_var, data->left_vsl,
12011f5207b7SJohn Levon 			SPECIAL_EQUAL,
12021f5207b7SJohn Levon 			data->right, data->right_var, data->right_vsl);
12031f5207b7SJohn Levon 
12045a0e240fSJohn Levon 	// FIXME: This doesn't handle links correct so it doesn't set "param orig"
12055a0e240fSJohn Levon 	set_true_false_states(comparison_id, state_name, NULL, NULL, false_state);
12061f5207b7SJohn Levon }
12071f5207b7SJohn Levon 
is_plus_one(struct expression * expr)12081f5207b7SJohn Levon static int is_plus_one(struct expression *expr)
12091f5207b7SJohn Levon {
12101f5207b7SJohn Levon 	sval_t sval;
12111f5207b7SJohn Levon 
12121f5207b7SJohn Levon 	if (expr->type != EXPR_BINOP || expr->op != '+')
12131f5207b7SJohn Levon 		return 0;
12141f5207b7SJohn Levon 	if (!get_implied_value(expr->right, &sval) || sval.value != 1)
12151f5207b7SJohn Levon 		return 0;
12161f5207b7SJohn Levon 	return 1;
12171f5207b7SJohn Levon }
12181f5207b7SJohn Levon 
is_minus_one(struct expression * expr)12191f5207b7SJohn Levon static int is_minus_one(struct expression *expr)
12201f5207b7SJohn Levon {
12211f5207b7SJohn Levon 	sval_t sval;
12221f5207b7SJohn Levon 
12231f5207b7SJohn Levon 	if (expr->type != EXPR_BINOP || expr->op != '-')
12241f5207b7SJohn Levon 		return 0;
12251f5207b7SJohn Levon 	if (!get_implied_value(expr->right, &sval) || sval.value != 1)
12261f5207b7SJohn Levon 		return 0;
12271f5207b7SJohn Levon 	return 1;
12281f5207b7SJohn Levon }
12291f5207b7SJohn Levon 
move_plus_to_minus_helper(struct expression ** left_p,struct expression ** right_p)12301f5207b7SJohn Levon static void move_plus_to_minus_helper(struct expression **left_p, struct expression **right_p)
12311f5207b7SJohn Levon {
12321f5207b7SJohn Levon 	struct expression *left = *left_p;
12331f5207b7SJohn Levon 	struct expression *right = *right_p;
12341f5207b7SJohn Levon 
12351f5207b7SJohn Levon 	/*
12361f5207b7SJohn Levon 	 * These two are basically equivalent: "foo + 1 != bar" and
12371f5207b7SJohn Levon 	 * "foo != bar - 1".  There are issues with signedness and integer
12381f5207b7SJohn Levon 	 * overflows.  There are also issues with type as well.  But let's
12391f5207b7SJohn Levon 	 * pretend we can ignore all that stuff for now.
12401f5207b7SJohn Levon 	 *
12411f5207b7SJohn Levon 	 */
12421f5207b7SJohn Levon 
12431f5207b7SJohn Levon 	if (!is_plus_one(left))
12441f5207b7SJohn Levon 		return;
12451f5207b7SJohn Levon 
12461f5207b7SJohn Levon 	*left_p = left->left;
12471f5207b7SJohn Levon 	*right_p = binop_expression(right, '-', left->right);
12481f5207b7SJohn Levon }
12491f5207b7SJohn Levon 
move_plus_to_minus(struct expression ** left_p,struct expression ** right_p)12501f5207b7SJohn Levon static void move_plus_to_minus(struct expression **left_p, struct expression **right_p)
12511f5207b7SJohn Levon {
12521f5207b7SJohn Levon 	if (is_plus_one(*left_p) && is_plus_one(*right_p))
12531f5207b7SJohn Levon 		return;
12541f5207b7SJohn Levon 
12551f5207b7SJohn Levon 	move_plus_to_minus_helper(left_p, right_p);
12561f5207b7SJohn Levon 	move_plus_to_minus_helper(right_p, left_p);
12571f5207b7SJohn Levon }
12581f5207b7SJohn Levon 
handle_comparison(struct expression * left_expr,int op,struct expression * right_expr,char ** _state_name,struct smatch_state ** _false_state)12591f5207b7SJohn Levon static void handle_comparison(struct expression *left_expr, int op, struct expression *right_expr, char **_state_name, struct smatch_state **_false_state)
12601f5207b7SJohn Levon {
12611f5207b7SJohn Levon 	char *left = NULL;
12621f5207b7SJohn Levon 	char *right = NULL;
12631f5207b7SJohn Levon 	struct symbol *left_sym, *right_sym;
12641f5207b7SJohn Levon 	struct var_sym_list *left_vsl = NULL;
12651f5207b7SJohn Levon 	struct var_sym_list *right_vsl = NULL;
12661f5207b7SJohn Levon 	int false_op;
12671f5207b7SJohn Levon 	int orig_comparison;
12681f5207b7SJohn Levon 	struct smatch_state *true_state, *false_state;
12691f5207b7SJohn Levon 	static char state_name[256];
12701f5207b7SJohn Levon 	struct stree *pre_stree;
12711f5207b7SJohn Levon 	sval_t sval;
12721f5207b7SJohn Levon 
12731f5207b7SJohn Levon 	if (!left_expr || !right_expr)
12741f5207b7SJohn Levon 		return;
12751f5207b7SJohn Levon 
12761f5207b7SJohn Levon 	left_expr = strip_parens(left_expr);
12771f5207b7SJohn Levon 	right_expr = strip_parens(right_expr);
12781f5207b7SJohn Levon 
12791f5207b7SJohn Levon 	while (left_expr->type == EXPR_ASSIGNMENT)
12801f5207b7SJohn Levon 		left_expr = strip_parens(left_expr->left);
12811f5207b7SJohn Levon 	while (right_expr->type == EXPR_ASSIGNMENT)
12821f5207b7SJohn Levon 		right_expr = strip_parens(right_expr->left);
12831f5207b7SJohn Levon 
12841f5207b7SJohn Levon 	false_op = negate_comparison(op);
12851f5207b7SJohn Levon 
12861f5207b7SJohn Levon 	move_plus_to_minus(&left_expr, &right_expr);
12871f5207b7SJohn Levon 
12881f5207b7SJohn Levon 	if (op == SPECIAL_UNSIGNED_LT &&
12891f5207b7SJohn Levon 	    get_implied_value(left_expr, &sval) &&
12901f5207b7SJohn Levon 	    sval.value == 0)
12911f5207b7SJohn Levon 		false_op = SPECIAL_EQUAL;
12921f5207b7SJohn Levon 
12931f5207b7SJohn Levon 	if (op == SPECIAL_UNSIGNED_GT &&
12941f5207b7SJohn Levon 	    get_implied_value(right_expr, &sval) &&
12951f5207b7SJohn Levon 	    sval.value == 0)
12961f5207b7SJohn Levon 		false_op = SPECIAL_EQUAL;
12971f5207b7SJohn Levon 
12981f5207b7SJohn Levon 	left = chunk_to_var_sym(left_expr, &left_sym);
12991f5207b7SJohn Levon 	if (!left)
13001f5207b7SJohn Levon 		goto free;
13011f5207b7SJohn Levon 	if (left_sym)
13021f5207b7SJohn Levon 		add_var_sym(&left_vsl, left, left_sym);
13031f5207b7SJohn Levon 	else
13041f5207b7SJohn Levon 		left_vsl = expr_to_vsl(left_expr);
13051f5207b7SJohn Levon 	right = chunk_to_var_sym(right_expr, &right_sym);
13061f5207b7SJohn Levon 	if (!right)
13071f5207b7SJohn Levon 		goto free;
13081f5207b7SJohn Levon 	if (right_sym)
13091f5207b7SJohn Levon 		add_var_sym(&right_vsl, right, right_sym);
13101f5207b7SJohn Levon 	else
13111f5207b7SJohn Levon 		right_vsl = expr_to_vsl(right_expr);
13121f5207b7SJohn Levon 
13131f5207b7SJohn Levon 	if (strcmp(left, right) > 0) {
13141f5207b7SJohn Levon 		char *tmp_name = left;
13151f5207b7SJohn Levon 		struct var_sym_list *tmp_vsl = left_vsl;
13161f5207b7SJohn Levon 		struct expression *tmp_expr = left_expr;
13171f5207b7SJohn Levon 
13181f5207b7SJohn Levon 		left = right;
13191f5207b7SJohn Levon 		left_vsl = right_vsl;
13201f5207b7SJohn Levon 		left_expr = right_expr;
13211f5207b7SJohn Levon 		right = tmp_name;
13221f5207b7SJohn Levon 		right_vsl = tmp_vsl;
13231f5207b7SJohn Levon 		right_expr = tmp_expr;
13241f5207b7SJohn Levon 		op = flip_comparison(op);
13251f5207b7SJohn Levon 		false_op = flip_comparison(false_op);
13261f5207b7SJohn Levon 	}
13271f5207b7SJohn Levon 
13281f5207b7SJohn Levon 	orig_comparison = get_comparison(left_expr, right_expr);
1329c85f09ccSJohn Levon 	op = comparison_intersection(orig_comparison, op);
1330c85f09ccSJohn Levon 	false_op = comparison_intersection(orig_comparison, false_op);
13311f5207b7SJohn Levon 
13321f5207b7SJohn Levon 	snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
13331f5207b7SJohn Levon 	true_state = alloc_compare_state(
13341f5207b7SJohn Levon 			left_expr, left, left_vsl,
13351f5207b7SJohn Levon 			op,
13361f5207b7SJohn Levon 			right_expr, right, right_vsl);
13371f5207b7SJohn Levon 	false_state = alloc_compare_state(
13381f5207b7SJohn Levon 			left_expr, left, left_vsl,
13391f5207b7SJohn Levon 			false_op,
13401f5207b7SJohn Levon 			right_expr, right, right_vsl);
13411f5207b7SJohn Levon 
13421f5207b7SJohn Levon 	pre_stree = clone_stree(__get_cur_stree());
13431f5207b7SJohn Levon 	update_tf_data(pre_stree, left_expr, left, left_vsl, right_expr, right, right_vsl, op, false_op);
13441f5207b7SJohn Levon 	free_stree(&pre_stree);
13451f5207b7SJohn Levon 
13465a0e240fSJohn Levon 	set_true_false_states(comparison_id, state_name, NULL, true_state, false_state);
13471f5207b7SJohn Levon 	__compare_param_limit_hook(left_expr, right_expr, state_name, true_state, false_state);
13481f5207b7SJohn Levon 	save_link(left_expr, state_name);
13491f5207b7SJohn Levon 	save_link(right_expr, state_name);
13501f5207b7SJohn Levon 
13511f5207b7SJohn Levon 	if (_false_state)
13521f5207b7SJohn Levon 		*_false_state = false_state;
13531f5207b7SJohn Levon 	if (_state_name)
13541f5207b7SJohn Levon 		*_state_name = state_name;
13551f5207b7SJohn Levon free:
13561f5207b7SJohn Levon 	free_string(left);
13571f5207b7SJohn Levon 	free_string(right);
13581f5207b7SJohn Levon }
13591f5207b7SJohn Levon 
__comparison_match_condition(struct expression * expr)13601f5207b7SJohn Levon void __comparison_match_condition(struct expression *expr)
13611f5207b7SJohn Levon {
13621f5207b7SJohn Levon 	struct expression *left, *right, *new_left, *new_right, *tmp;
13631f5207b7SJohn Levon 	struct smatch_state *false_state = NULL;
13641f5207b7SJohn Levon 	char *state_name = NULL;
13651f5207b7SJohn Levon 	int redo, count;
13661f5207b7SJohn Levon 
13671f5207b7SJohn Levon 	if (expr->type != EXPR_COMPARE)
13681f5207b7SJohn Levon 		return;
13691f5207b7SJohn Levon 
13701f5207b7SJohn Levon 	handle_comparison(expr->left, expr->op, expr->right, &state_name, &false_state);
13711f5207b7SJohn Levon 	if (false_state && state_name)
13721f5207b7SJohn Levon 		handle_for_loops(expr, state_name, false_state);
13731f5207b7SJohn Levon 
13741f5207b7SJohn Levon 	left = strip_parens(expr->left);
13751f5207b7SJohn Levon 	right = strip_parens(expr->right);
13761f5207b7SJohn Levon 
13771f5207b7SJohn Levon 	if (left->type == EXPR_BINOP && left->op == '+') {
13781f5207b7SJohn Levon 		new_left = left->left;
13791f5207b7SJohn Levon 		new_right = binop_expression(right, '-', left->right);
13801f5207b7SJohn Levon 		handle_comparison(new_left, expr->op, new_right, NULL, NULL);
13811f5207b7SJohn Levon 
13821f5207b7SJohn Levon 		new_left = left->right;
13831f5207b7SJohn Levon 		new_right = binop_expression(right, '-', left->left);
13841f5207b7SJohn Levon 		handle_comparison(new_left, expr->op, new_right, NULL, NULL);
13851f5207b7SJohn Levon 	}
13861f5207b7SJohn Levon 
13871f5207b7SJohn Levon 	redo = 0;
13881f5207b7SJohn Levon 	left = strip_parens(expr->left);
13891f5207b7SJohn Levon 	right = strip_parens(expr->right);
13901f5207b7SJohn Levon 	if (get_last_expr_from_expression_stmt(expr->left)) {
13911f5207b7SJohn Levon 		left = get_last_expr_from_expression_stmt(expr->left);
13921f5207b7SJohn Levon 		redo = 1;
13931f5207b7SJohn Levon 	}
13941f5207b7SJohn Levon 	if (get_last_expr_from_expression_stmt(expr->right)) {
13951f5207b7SJohn Levon 		right = get_last_expr_from_expression_stmt(expr->right);
13961f5207b7SJohn Levon 		redo = 1;
13971f5207b7SJohn Levon 	}
13981f5207b7SJohn Levon 
13991f5207b7SJohn Levon 	if (!redo)
14001f5207b7SJohn Levon 		return;
14011f5207b7SJohn Levon 
14021f5207b7SJohn Levon 	count = 0;
14031f5207b7SJohn Levon 	while ((tmp = get_assigned_expr(left))) {
14041f5207b7SJohn Levon 		if (count++ > 3)
14051f5207b7SJohn Levon 			break;
14061f5207b7SJohn Levon 		left = strip_expr(tmp);
14071f5207b7SJohn Levon 	}
14081f5207b7SJohn Levon 	count = 0;
14091f5207b7SJohn Levon 	while ((tmp = get_assigned_expr(right))) {
14101f5207b7SJohn Levon 		if (count++ > 3)
14111f5207b7SJohn Levon 			break;
14121f5207b7SJohn Levon 		right = strip_expr(tmp);
14131f5207b7SJohn Levon 	}
14141f5207b7SJohn Levon 
14151f5207b7SJohn Levon 	handle_comparison(left, expr->op, right, NULL, NULL);
14161f5207b7SJohn Levon }
14171f5207b7SJohn Levon 
add_comparison_var_sym(struct expression * left_expr,const char * left_name,struct var_sym_list * left_vsl,int comparison,struct expression * right_expr,const char * right_name,struct var_sym_list * right_vsl)14181f5207b7SJohn Levon static void add_comparison_var_sym(
14191f5207b7SJohn Levon 		struct expression *left_expr,
14201f5207b7SJohn Levon 		const char *left_name, struct var_sym_list *left_vsl,
14211f5207b7SJohn Levon 		int comparison,
14221f5207b7SJohn Levon 		struct expression *right_expr,
14231f5207b7SJohn Levon 		const char *right_name, struct var_sym_list *right_vsl)
14241f5207b7SJohn Levon {
14251f5207b7SJohn Levon 	struct smatch_state *state;
14261f5207b7SJohn Levon 	struct var_sym *vs;
14271f5207b7SJohn Levon 	char state_name[256];
14281f5207b7SJohn Levon 
14291f5207b7SJohn Levon 	if (strcmp(left_name, right_name) > 0) {
14301f5207b7SJohn Levon 		struct expression *tmp_expr = left_expr;
14311f5207b7SJohn Levon 		const char *tmp_name = left_name;
14321f5207b7SJohn Levon 		struct var_sym_list *tmp_vsl = left_vsl;
14331f5207b7SJohn Levon 
14341f5207b7SJohn Levon 		left_expr = right_expr;
14351f5207b7SJohn Levon 		left_name = right_name;
14361f5207b7SJohn Levon 		left_vsl = right_vsl;
14371f5207b7SJohn Levon 		right_expr = tmp_expr;
14381f5207b7SJohn Levon 		right_name = tmp_name;
14391f5207b7SJohn Levon 		right_vsl = tmp_vsl;
14401f5207b7SJohn Levon 		comparison = flip_comparison(comparison);
14411f5207b7SJohn Levon 	}
14421f5207b7SJohn Levon 	snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
14431f5207b7SJohn Levon 	state = alloc_compare_state(
14441f5207b7SJohn Levon 			left_expr, left_name, left_vsl,
14451f5207b7SJohn Levon 			comparison,
14461f5207b7SJohn Levon 			right_expr, right_name, right_vsl);
14471f5207b7SJohn Levon 
14485a0e240fSJohn Levon 	set_state(comparison_id, state_name, NULL, state);
14491f5207b7SJohn Levon 
14501f5207b7SJohn Levon 	FOR_EACH_PTR(left_vsl, vs) {
14511f5207b7SJohn Levon 		save_link_var_sym(vs->var, vs->sym, state_name);
14521f5207b7SJohn Levon 	} END_FOR_EACH_PTR(vs);
14531f5207b7SJohn Levon 	FOR_EACH_PTR(right_vsl, vs) {
14541f5207b7SJohn Levon 		save_link_var_sym(vs->var, vs->sym, state_name);
14551f5207b7SJohn Levon 	} END_FOR_EACH_PTR(vs);
14561f5207b7SJohn Levon }
14571f5207b7SJohn Levon 
add_comparison(struct expression * left,int comparison,struct expression * right)14581f5207b7SJohn Levon static void add_comparison(struct expression *left, int comparison, struct expression *right)
14591f5207b7SJohn Levon {
14601f5207b7SJohn Levon 	char *left_name = NULL;
14611f5207b7SJohn Levon 	char *right_name = NULL;
14621f5207b7SJohn Levon 	struct symbol *left_sym, *right_sym;
14631f5207b7SJohn Levon 	struct var_sym_list *left_vsl, *right_vsl;
14641f5207b7SJohn Levon 	struct smatch_state *state;
14651f5207b7SJohn Levon 	char state_name[256];
14661f5207b7SJohn Levon 
14671f5207b7SJohn Levon 	left_name = chunk_to_var_sym(left, &left_sym);
14681f5207b7SJohn Levon 	if (!left_name)
14691f5207b7SJohn Levon 		goto free;
14701f5207b7SJohn Levon 	left_vsl = expr_to_vsl(left);
14711f5207b7SJohn Levon 	right_name = chunk_to_var_sym(right, &right_sym);
14721f5207b7SJohn Levon 	if (!right_name)
14731f5207b7SJohn Levon 		goto free;
14741f5207b7SJohn Levon 	right_vsl = expr_to_vsl(right);
14751f5207b7SJohn Levon 
14761f5207b7SJohn Levon 	if (strcmp(left_name, right_name) > 0) {
14771f5207b7SJohn Levon 		struct expression *tmp_expr = left;
14781f5207b7SJohn Levon 		struct symbol *tmp_sym = left_sym;
14791f5207b7SJohn Levon 		char *tmp_name = left_name;
14801f5207b7SJohn Levon 		struct var_sym_list *tmp_vsl = left_vsl;
14811f5207b7SJohn Levon 
14821f5207b7SJohn Levon 		left = right;
14831f5207b7SJohn Levon 		left_name = right_name;
14841f5207b7SJohn Levon 		left_sym = right_sym;
14851f5207b7SJohn Levon 		left_vsl = right_vsl;
14861f5207b7SJohn Levon 		right = tmp_expr;
14871f5207b7SJohn Levon 		right_name = tmp_name;
14881f5207b7SJohn Levon 		right_sym = tmp_sym;
14891f5207b7SJohn Levon 		right_vsl = tmp_vsl;
14901f5207b7SJohn Levon 		comparison = flip_comparison(comparison);
14911f5207b7SJohn Levon 	}
14921f5207b7SJohn Levon 	snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
14931f5207b7SJohn Levon 	state = alloc_compare_state(
14941f5207b7SJohn Levon 			left, left_name, left_vsl,
14951f5207b7SJohn Levon 			comparison,
14961f5207b7SJohn Levon 			right, right_name, right_vsl);
14971f5207b7SJohn Levon 
14985a0e240fSJohn Levon 	set_state(comparison_id, state_name, NULL, state);
14991f5207b7SJohn Levon 	save_link(left, state_name);
15001f5207b7SJohn Levon 	save_link(right, state_name);
15011f5207b7SJohn Levon 
15021f5207b7SJohn Levon free:
15031f5207b7SJohn Levon 	free_string(left_name);
15041f5207b7SJohn Levon 	free_string(right_name);
15051f5207b7SJohn Levon }
15061f5207b7SJohn Levon 
match_assign_add(struct expression * expr)15071f5207b7SJohn Levon static void match_assign_add(struct expression *expr)
15081f5207b7SJohn Levon {
15091f5207b7SJohn Levon 	struct expression *right;
15101f5207b7SJohn Levon 	struct expression *r_left, *r_right;
15111f5207b7SJohn Levon 	sval_t left_tmp, right_tmp;
15121f5207b7SJohn Levon 
15131f5207b7SJohn Levon 	right = strip_expr(expr->right);
15141f5207b7SJohn Levon 	r_left = strip_expr(right->left);
15151f5207b7SJohn Levon 	r_right = strip_expr(right->right);
15161f5207b7SJohn Levon 
15171f5207b7SJohn Levon 	get_absolute_min(r_left, &left_tmp);
15181f5207b7SJohn Levon 	get_absolute_min(r_right, &right_tmp);
15191f5207b7SJohn Levon 
15201f5207b7SJohn Levon 	if (left_tmp.value > 0)
15211f5207b7SJohn Levon 		add_comparison(expr->left, '>', r_right);
15221f5207b7SJohn Levon 	else if (left_tmp.value == 0)
15231f5207b7SJohn Levon 		add_comparison(expr->left, SPECIAL_GTE, r_right);
15241f5207b7SJohn Levon 
15251f5207b7SJohn Levon 	if (right_tmp.value > 0)
15261f5207b7SJohn Levon 		add_comparison(expr->left, '>', r_left);
15271f5207b7SJohn Levon 	else if (right_tmp.value == 0)
15281f5207b7SJohn Levon 		add_comparison(expr->left, SPECIAL_GTE, r_left);
15291f5207b7SJohn Levon }
15301f5207b7SJohn Levon 
match_assign_sub(struct expression * expr)15311f5207b7SJohn Levon static void match_assign_sub(struct expression *expr)
15321f5207b7SJohn Levon {
15331f5207b7SJohn Levon 	struct expression *right;
15341f5207b7SJohn Levon 	struct expression *r_left, *r_right;
15351f5207b7SJohn Levon 	int comparison;
15361f5207b7SJohn Levon 	sval_t min;
15371f5207b7SJohn Levon 
15381f5207b7SJohn Levon 	right = strip_expr(expr->right);
15391f5207b7SJohn Levon 	r_left = strip_expr(right->left);
15401f5207b7SJohn Levon 	r_right = strip_expr(right->right);
15411f5207b7SJohn Levon 
15421f5207b7SJohn Levon 	if (get_absolute_min(r_right, &min) && sval_is_negative(min))
15431f5207b7SJohn Levon 		return;
15441f5207b7SJohn Levon 
15451f5207b7SJohn Levon 	comparison = get_comparison(r_left, r_right);
15461f5207b7SJohn Levon 
15471f5207b7SJohn Levon 	switch (comparison) {
15481f5207b7SJohn Levon 	case '>':
15491f5207b7SJohn Levon 	case SPECIAL_GTE:
15501f5207b7SJohn Levon 		if (implied_not_equal(r_right, 0))
15511f5207b7SJohn Levon 			add_comparison(expr->left, '>', r_left);
15521f5207b7SJohn Levon 		else
15531f5207b7SJohn Levon 			add_comparison(expr->left, SPECIAL_GTE, r_left);
15541f5207b7SJohn Levon 		return;
15551f5207b7SJohn Levon 	}
15561f5207b7SJohn Levon }
15571f5207b7SJohn Levon 
match_assign_divide(struct expression * expr)15581f5207b7SJohn Levon static void match_assign_divide(struct expression *expr)
15591f5207b7SJohn Levon {
15601f5207b7SJohn Levon 	struct expression *right;
15611f5207b7SJohn Levon 	struct expression *r_left, *r_right;
15621f5207b7SJohn Levon 	sval_t min;
15631f5207b7SJohn Levon 
15641f5207b7SJohn Levon 	right = strip_expr(expr->right);
15651f5207b7SJohn Levon 	r_left = strip_expr(right->left);
15661f5207b7SJohn Levon 	r_right = strip_expr(right->right);
15671f5207b7SJohn Levon 	if (!get_implied_min(r_right, &min) || min.value <= 1)
15681f5207b7SJohn Levon 		return;
15691f5207b7SJohn Levon 
15701f5207b7SJohn Levon 	add_comparison(expr->left, '<', r_left);
15711f5207b7SJohn Levon }
15721f5207b7SJohn Levon 
match_binop_assign(struct expression * expr)15731f5207b7SJohn Levon static void match_binop_assign(struct expression *expr)
15741f5207b7SJohn Levon {
15751f5207b7SJohn Levon 	struct expression *right;
15761f5207b7SJohn Levon 
15771f5207b7SJohn Levon 	right = strip_expr(expr->right);
15781f5207b7SJohn Levon 	if (right->op == '+')
15791f5207b7SJohn Levon 		match_assign_add(expr);
15801f5207b7SJohn Levon 	if (right->op == '-')
15811f5207b7SJohn Levon 		match_assign_sub(expr);
15821f5207b7SJohn Levon 	if (right->op == '/')
15831f5207b7SJohn Levon 		match_assign_divide(expr);
15841f5207b7SJohn Levon }
15851f5207b7SJohn Levon 
copy_comparisons(struct expression * left,struct expression * right)15861f5207b7SJohn Levon static void copy_comparisons(struct expression *left, struct expression *right)
15871f5207b7SJohn Levon {
15881f5207b7SJohn Levon 	struct string_list *links;
15891f5207b7SJohn Levon 	struct smatch_state *state;
15901f5207b7SJohn Levon 	struct compare_data *data;
15911f5207b7SJohn Levon 	struct symbol *left_sym, *right_sym;
15921f5207b7SJohn Levon 	char *left_var = NULL;
15931f5207b7SJohn Levon 	char *right_var = NULL;
15941f5207b7SJohn Levon 	struct var_sym_list *left_vsl;
15951f5207b7SJohn Levon 	struct expression *expr;
15961f5207b7SJohn Levon 	const char *var;
15971f5207b7SJohn Levon 	struct var_sym_list *vsl;
15981f5207b7SJohn Levon 	int comparison;
15991f5207b7SJohn Levon 	char *tmp;
16001f5207b7SJohn Levon 
16011f5207b7SJohn Levon 	left_var = chunk_to_var_sym(left, &left_sym);
16021f5207b7SJohn Levon 	if (!left_var)
16031f5207b7SJohn Levon 		goto done;
16041f5207b7SJohn Levon 	left_vsl = expr_to_vsl(left);
16051f5207b7SJohn Levon 	right_var = chunk_to_var_sym(right, &right_sym);
16061f5207b7SJohn Levon 	if (!right_var)
16071f5207b7SJohn Levon 		goto done;
16081f5207b7SJohn Levon 
16091f5207b7SJohn Levon 	state = get_state(link_id, right_var, right_sym);
16101f5207b7SJohn Levon 	if (!state)
16111f5207b7SJohn Levon 		return;
16121f5207b7SJohn Levon 	links = state->data;
16131f5207b7SJohn Levon 
16141f5207b7SJohn Levon 	FOR_EACH_PTR(links, tmp) {
16155a0e240fSJohn Levon 		state = get_state(comparison_id, tmp, NULL);
16161f5207b7SJohn Levon 		if (!state || !state->data)
16171f5207b7SJohn Levon 			continue;
16181f5207b7SJohn Levon 		data = state->data;
16191f5207b7SJohn Levon 		comparison = data->comparison;
16201f5207b7SJohn Levon 		expr = data->right;
16211f5207b7SJohn Levon 		var = data->right_var;
16221f5207b7SJohn Levon 		vsl = data->right_vsl;
16231f5207b7SJohn Levon 		if (strcmp(var, right_var) == 0) {
16241f5207b7SJohn Levon 			expr = data->left;
16251f5207b7SJohn Levon 			var = data->left_var;
16261f5207b7SJohn Levon 			vsl = data->left_vsl;
16271f5207b7SJohn Levon 			comparison = flip_comparison(comparison);
16281f5207b7SJohn Levon 		}
16291f5207b7SJohn Levon 		/* n = copy_from_user(dest, src, n); leads to n <= n which is nonsense */
16301f5207b7SJohn Levon 		if (strcmp(left_var, var) == 0)
16311f5207b7SJohn Levon 			continue;
16321f5207b7SJohn Levon 		add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
16331f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
16341f5207b7SJohn Levon 
16351f5207b7SJohn Levon done:
16361f5207b7SJohn Levon 	free_string(right_var);
16371f5207b7SJohn Levon }
16381f5207b7SJohn Levon 
match_assign(struct expression * expr)16391f5207b7SJohn Levon static void match_assign(struct expression *expr)
16401f5207b7SJohn Levon {
16411f5207b7SJohn Levon 	struct expression *right;
16421f5207b7SJohn Levon 
16431f5207b7SJohn Levon 	if (expr->op != '=')
16441f5207b7SJohn Levon 		return;
16451f5207b7SJohn Levon 	if (__in_fake_assign || outside_of_function())
16461f5207b7SJohn Levon 		return;
16471f5207b7SJohn Levon 
16481f5207b7SJohn Levon 	if (is_struct(expr->left))
16491f5207b7SJohn Levon 		return;
16501f5207b7SJohn Levon 
16511f5207b7SJohn Levon 	if (is_self_assign(expr))
16521f5207b7SJohn Levon 		return;
16531f5207b7SJohn Levon 
16541f5207b7SJohn Levon 	copy_comparisons(expr->left, expr->right);
16551f5207b7SJohn Levon 	add_comparison(expr->left, SPECIAL_EQUAL, expr->right);
16561f5207b7SJohn Levon 
16571f5207b7SJohn Levon 	right = strip_expr(expr->right);
16581f5207b7SJohn Levon 	if (right->type == EXPR_BINOP)
16591f5207b7SJohn Levon 		match_binop_assign(expr);
16601f5207b7SJohn Levon }
16611f5207b7SJohn Levon 
get_comparison_strings(const char * one,const char * two)16621f5207b7SJohn Levon int get_comparison_strings(const char *one, const char *two)
16631f5207b7SJohn Levon {
16641f5207b7SJohn Levon 	char buf[256];
16651f5207b7SJohn Levon 	struct smatch_state *state;
16661f5207b7SJohn Levon 	int invert = 0;
16671f5207b7SJohn Levon 	int ret = 0;
16681f5207b7SJohn Levon 
16691f5207b7SJohn Levon 	if (!one || !two)
1670c85f09ccSJohn Levon 		return UNKNOWN_COMPARISON;
16711f5207b7SJohn Levon 
16721f5207b7SJohn Levon 	if (strcmp(one, two) == 0)
16731f5207b7SJohn Levon 		return SPECIAL_EQUAL;
16741f5207b7SJohn Levon 
16751f5207b7SJohn Levon 	if (strcmp(one, two) > 0) {
16761f5207b7SJohn Levon 		const char *tmp = one;
16771f5207b7SJohn Levon 
16781f5207b7SJohn Levon 		one = two;
16791f5207b7SJohn Levon 		two = tmp;
16801f5207b7SJohn Levon 		invert = 1;
16811f5207b7SJohn Levon 	}
16821f5207b7SJohn Levon 
16831f5207b7SJohn Levon 	snprintf(buf, sizeof(buf), "%s vs %s", one, two);
16845a0e240fSJohn Levon 	state = get_state(comparison_id, buf, NULL);
16851f5207b7SJohn Levon 	if (state)
16861f5207b7SJohn Levon 		ret = state_to_comparison(state);
16871f5207b7SJohn Levon 
16881f5207b7SJohn Levon 	if (invert)
16891f5207b7SJohn Levon 		ret = flip_comparison(ret);
16901f5207b7SJohn Levon 
16911f5207b7SJohn Levon 	return ret;
16921f5207b7SJohn Levon }
16931f5207b7SJohn Levon 
get_comparison_helper(struct expression * a,struct expression * b,bool use_extra)1694efe51d0cSJohn Levon static int get_comparison_helper(struct expression *a, struct expression *b, bool use_extra)
16951f5207b7SJohn Levon {
16961f5207b7SJohn Levon 	char *one = NULL;
16971f5207b7SJohn Levon 	char *two = NULL;
1698c85f09ccSJohn Levon 	int ret = UNKNOWN_COMPARISON;
1699c85f09ccSJohn Levon 	int extra = UNKNOWN_COMPARISON;
17001f5207b7SJohn Levon 
1701c85f09ccSJohn Levon 	if (a == UNKNOWN_COMPARISON ||
1702c85f09ccSJohn Levon 	    b == UNKNOWN_COMPARISON)
1703c85f09ccSJohn Levon 		return UNKNOWN_COMPARISON;
17041f5207b7SJohn Levon 
17051f5207b7SJohn Levon 	a = strip_parens(a);
17061f5207b7SJohn Levon 	b = strip_parens(b);
17071f5207b7SJohn Levon 
17081f5207b7SJohn Levon 	move_plus_to_minus(&a, &b);
17091f5207b7SJohn Levon 
17101f5207b7SJohn Levon 	one = chunk_to_var(a);
17111f5207b7SJohn Levon 	if (!one)
17121f5207b7SJohn Levon 		goto free;
17131f5207b7SJohn Levon 	two = chunk_to_var(b);
17141f5207b7SJohn Levon 	if (!two)
17151f5207b7SJohn Levon 		goto free;
17161f5207b7SJohn Levon 
17171f5207b7SJohn Levon 	ret = get_comparison_strings(one, two);
17181f5207b7SJohn Levon 	if (ret)
17191f5207b7SJohn Levon 		goto free;
17201f5207b7SJohn Levon 
17211f5207b7SJohn Levon 	if (is_plus_one(a) || is_minus_one(a)) {
17221f5207b7SJohn Levon 		free_string(one);
17231f5207b7SJohn Levon 		one = chunk_to_var(a->left);
17241f5207b7SJohn Levon 		ret = get_comparison_strings(one, two);
17251f5207b7SJohn Levon 	} else if (is_plus_one(b) || is_minus_one(b)) {
17261f5207b7SJohn Levon 		free_string(two);
17271f5207b7SJohn Levon 		two = chunk_to_var(b->left);
17281f5207b7SJohn Levon 		ret = get_comparison_strings(one, two);
17291f5207b7SJohn Levon 	}
17301f5207b7SJohn Levon 
1731c85f09ccSJohn Levon 	if (ret == UNKNOWN_COMPARISON)
17321f5207b7SJohn Levon 		goto free;
17331f5207b7SJohn Levon 
17341f5207b7SJohn Levon 	if ((is_plus_one(a) || is_minus_one(b)) && ret == '<')
17351f5207b7SJohn Levon 		ret = SPECIAL_LTE;
17361f5207b7SJohn Levon 	else if ((is_minus_one(a) || is_plus_one(b)) && ret == '>')
17371f5207b7SJohn Levon 		ret = SPECIAL_GTE;
17381f5207b7SJohn Levon 	else
1739c85f09ccSJohn Levon 		ret = UNKNOWN_COMPARISON;
17401f5207b7SJohn Levon 
17411f5207b7SJohn Levon free:
17421f5207b7SJohn Levon 	free_string(one);
17431f5207b7SJohn Levon 	free_string(two);
17441f5207b7SJohn Levon 
1745c85f09ccSJohn Levon 	extra = comparison_from_extra(a, b);
1746c85f09ccSJohn Levon 	return comparison_intersection(ret, extra);
17471f5207b7SJohn Levon }
17481f5207b7SJohn Levon 
get_comparison(struct expression * a,struct expression * b)1749efe51d0cSJohn Levon int get_comparison(struct expression *a, struct expression *b)
1750efe51d0cSJohn Levon {
1751efe51d0cSJohn Levon 	return get_comparison_helper(a, b, true);
1752efe51d0cSJohn Levon }
1753efe51d0cSJohn Levon 
get_comparison_no_extra(struct expression * a,struct expression * b)1754efe51d0cSJohn Levon int get_comparison_no_extra(struct expression *a, struct expression *b)
1755efe51d0cSJohn Levon {
1756efe51d0cSJohn Levon 	return get_comparison_helper(a, b, false);
1757efe51d0cSJohn Levon }
1758efe51d0cSJohn Levon 
possible_comparison(struct expression * a,int comparison,struct expression * b)17591f5207b7SJohn Levon int possible_comparison(struct expression *a, int comparison, struct expression *b)
17601f5207b7SJohn Levon {
17611f5207b7SJohn Levon 	char *one = NULL;
17621f5207b7SJohn Levon 	char *two = NULL;
17631f5207b7SJohn Levon 	int ret = 0;
17641f5207b7SJohn Levon 	char buf[256];
17651f5207b7SJohn Levon 	struct sm_state *sm;
17661f5207b7SJohn Levon 	int saved;
17671f5207b7SJohn Levon 
17681f5207b7SJohn Levon 	one = chunk_to_var(a);
17691f5207b7SJohn Levon 	if (!one)
17701f5207b7SJohn Levon 		goto free;
17711f5207b7SJohn Levon 	two = chunk_to_var(b);
17721f5207b7SJohn Levon 	if (!two)
17731f5207b7SJohn Levon 		goto free;
17741f5207b7SJohn Levon 
17751f5207b7SJohn Levon 
17761f5207b7SJohn Levon 	if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) {
17771f5207b7SJohn Levon 		ret = 1;
17781f5207b7SJohn Levon 		goto free;
17791f5207b7SJohn Levon 	}
17801f5207b7SJohn Levon 
17811f5207b7SJohn Levon 	if (strcmp(one, two) > 0) {
17821f5207b7SJohn Levon 		char *tmp = one;
17831f5207b7SJohn Levon 
17841f5207b7SJohn Levon 		one = two;
17851f5207b7SJohn Levon 		two = tmp;
17861f5207b7SJohn Levon 		comparison = flip_comparison(comparison);
17871f5207b7SJohn Levon 	}
17881f5207b7SJohn Levon 
17891f5207b7SJohn Levon 	snprintf(buf, sizeof(buf), "%s vs %s", one, two);
17905a0e240fSJohn Levon 	sm = get_sm_state(comparison_id, buf, NULL);
17911f5207b7SJohn Levon 	if (!sm)
17921f5207b7SJohn Levon 		goto free;
17931f5207b7SJohn Levon 
17941f5207b7SJohn Levon 	FOR_EACH_PTR(sm->possible, sm) {
17951f5207b7SJohn Levon 		if (!sm->state->data)
17961f5207b7SJohn Levon 			continue;
17971f5207b7SJohn Levon 		saved = ((struct compare_data *)sm->state->data)->comparison;
17981f5207b7SJohn Levon 		if (saved == comparison)
17991f5207b7SJohn Levon 			ret = 1;
18001f5207b7SJohn Levon 		if (comparison == SPECIAL_EQUAL &&
18011f5207b7SJohn Levon 		    (saved == SPECIAL_LTE ||
18021f5207b7SJohn Levon 		     saved == SPECIAL_GTE ||
18031f5207b7SJohn Levon 		     saved == SPECIAL_UNSIGNED_LTE ||
18041f5207b7SJohn Levon 		     saved == SPECIAL_UNSIGNED_GTE))
18051f5207b7SJohn Levon 			ret = 1;
18061f5207b7SJohn Levon 		if (ret == 1)
18071f5207b7SJohn Levon 			goto free;
18081f5207b7SJohn Levon 	} END_FOR_EACH_PTR(sm);
18091f5207b7SJohn Levon 
18101f5207b7SJohn Levon 	return ret;
18111f5207b7SJohn Levon free:
18121f5207b7SJohn Levon 	free_string(one);
18131f5207b7SJohn Levon 	free_string(two);
18141f5207b7SJohn Levon 	return ret;
18151f5207b7SJohn Levon }
18161f5207b7SJohn Levon 
get_all_comparisons(struct expression * expr)18171f5207b7SJohn Levon struct state_list *get_all_comparisons(struct expression *expr)
18181f5207b7SJohn Levon {
18191f5207b7SJohn Levon 	struct smatch_state *state;
18201f5207b7SJohn Levon 	struct string_list *links;
18211f5207b7SJohn Levon 	struct state_list *ret = NULL;
18221f5207b7SJohn Levon 	struct sm_state *sm;
18231f5207b7SJohn Levon 	char *tmp;
18241f5207b7SJohn Levon 
18251f5207b7SJohn Levon 	state = get_state_chunk(link_id, expr);
18261f5207b7SJohn Levon 	if (!state)
18271f5207b7SJohn Levon 		return NULL;
18281f5207b7SJohn Levon 	links = state->data;
18291f5207b7SJohn Levon 
18301f5207b7SJohn Levon 	FOR_EACH_PTR(links, tmp) {
18315a0e240fSJohn Levon 		sm = get_sm_state(comparison_id, tmp, NULL);
18321f5207b7SJohn Levon 		if (!sm)
18331f5207b7SJohn Levon 			continue;
18341f5207b7SJohn Levon 		// FIXME have to compare name with vsl
18351f5207b7SJohn Levon 		add_ptr_list(&ret, sm);
18361f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
18371f5207b7SJohn Levon 
18381f5207b7SJohn Levon 	return ret;
18391f5207b7SJohn Levon }
18401f5207b7SJohn Levon 
get_all_possible_equal_comparisons(struct expression * expr)18411f5207b7SJohn Levon struct state_list *get_all_possible_equal_comparisons(struct expression *expr)
18421f5207b7SJohn Levon {
18431f5207b7SJohn Levon 	struct smatch_state *state;
18441f5207b7SJohn Levon 	struct string_list *links;
18451f5207b7SJohn Levon 	struct state_list *ret = NULL;
18461f5207b7SJohn Levon 	struct sm_state *sm;
18471f5207b7SJohn Levon 	char *tmp;
18481f5207b7SJohn Levon 
18491f5207b7SJohn Levon 	state = get_state_chunk(link_id, expr);
18501f5207b7SJohn Levon 	if (!state)
18511f5207b7SJohn Levon 		return NULL;
18521f5207b7SJohn Levon 	links = state->data;
18531f5207b7SJohn Levon 
18541f5207b7SJohn Levon 	FOR_EACH_PTR(links, tmp) {
18555a0e240fSJohn Levon 		sm = get_sm_state(comparison_id, tmp, NULL);
18561f5207b7SJohn Levon 		if (!sm)
18571f5207b7SJohn Levon 			continue;
18581f5207b7SJohn Levon 		if (!strchr(sm->state->name, '='))
18591f5207b7SJohn Levon 			continue;
18601f5207b7SJohn Levon 		if (strcmp(sm->state->name, "!=") == 0)
18611f5207b7SJohn Levon 			continue;
18621f5207b7SJohn Levon 		add_ptr_list(&ret, sm);
18631f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
18641f5207b7SJohn Levon 
18651f5207b7SJohn Levon 	return ret;
18661f5207b7SJohn Levon }
18671f5207b7SJohn Levon 
get_all_possible_not_equal_comparisons(struct expression * expr)18681f5207b7SJohn Levon struct state_list *get_all_possible_not_equal_comparisons(struct expression *expr)
18691f5207b7SJohn Levon {
18701f5207b7SJohn Levon 	struct smatch_state *state;
18711f5207b7SJohn Levon 	struct string_list *links;
18721f5207b7SJohn Levon 	struct state_list *ret = NULL;
18731f5207b7SJohn Levon 	struct sm_state *sm;
18741f5207b7SJohn Levon 	struct sm_state *possible;
18751f5207b7SJohn Levon 	char *link;
18761f5207b7SJohn Levon 
18771f5207b7SJohn Levon 	return NULL;
18781f5207b7SJohn Levon 
18791f5207b7SJohn Levon 	state = get_state_chunk(link_id, expr);
18801f5207b7SJohn Levon 	if (!state)
18811f5207b7SJohn Levon 		return NULL;
18821f5207b7SJohn Levon 	links = state->data;
18831f5207b7SJohn Levon 
18841f5207b7SJohn Levon 	FOR_EACH_PTR(links, link) {
18855a0e240fSJohn Levon 		sm = get_sm_state(comparison_id, link, NULL);
18861f5207b7SJohn Levon 		if (!sm)
18871f5207b7SJohn Levon 			continue;
18881f5207b7SJohn Levon 		FOR_EACH_PTR(sm->possible, possible) {
18891f5207b7SJohn Levon 			if (strcmp(possible->state->name, "!=") != 0)
18901f5207b7SJohn Levon 				continue;
18911f5207b7SJohn Levon 			add_ptr_list(&ret, sm);
18921f5207b7SJohn Levon 			break;
18931f5207b7SJohn Levon 		} END_FOR_EACH_PTR(link);
18941f5207b7SJohn Levon 	} END_FOR_EACH_PTR(link);
18951f5207b7SJohn Levon 
18961f5207b7SJohn Levon 	return ret;
18971f5207b7SJohn Levon }
18981f5207b7SJohn Levon 
update_links_from_call(struct expression * left,int left_compare,struct expression * right)18991f5207b7SJohn Levon static void update_links_from_call(struct expression *left,
19001f5207b7SJohn Levon 				   int left_compare,
19011f5207b7SJohn Levon 				   struct expression *right)
19021f5207b7SJohn Levon {
19031f5207b7SJohn Levon 	struct string_list *links;
19041f5207b7SJohn Levon 	struct smatch_state *state;
19051f5207b7SJohn Levon 	struct compare_data *data;
19061f5207b7SJohn Levon 	struct symbol *left_sym, *right_sym;
19071f5207b7SJohn Levon 	char *left_var = NULL;
19081f5207b7SJohn Levon 	char *right_var = NULL;
19091f5207b7SJohn Levon 	struct var_sym_list *left_vsl;
19101f5207b7SJohn Levon 	struct expression *expr;
19111f5207b7SJohn Levon 	const char *var;
19121f5207b7SJohn Levon 	struct var_sym_list *vsl;
19131f5207b7SJohn Levon 	int comparison;
19141f5207b7SJohn Levon 	char *tmp;
19151f5207b7SJohn Levon 
19161f5207b7SJohn Levon 	left_var = chunk_to_var_sym(left, &left_sym);
19171f5207b7SJohn Levon 	if (!left_var)
19181f5207b7SJohn Levon 		goto done;
19191f5207b7SJohn Levon 	left_vsl = expr_to_vsl(left);
19201f5207b7SJohn Levon 	right_var = chunk_to_var_sym(right, &right_sym);
19211f5207b7SJohn Levon 	if (!right_var)
19221f5207b7SJohn Levon 		goto done;
19231f5207b7SJohn Levon 
19241f5207b7SJohn Levon 	state = get_state(link_id, right_var, right_sym);
19251f5207b7SJohn Levon 	if (!state)
19261f5207b7SJohn Levon 		return;
19271f5207b7SJohn Levon 	links = state->data;
19281f5207b7SJohn Levon 
19291f5207b7SJohn Levon 	FOR_EACH_PTR(links, tmp) {
19305a0e240fSJohn Levon 		state = get_state(comparison_id, tmp, NULL);
19311f5207b7SJohn Levon 		if (!state || !state->data)
19321f5207b7SJohn Levon 			continue;
19331f5207b7SJohn Levon 		data = state->data;
19341f5207b7SJohn Levon 		comparison = data->comparison;
19351f5207b7SJohn Levon 		expr = data->right;
19361f5207b7SJohn Levon 		var = data->right_var;
19371f5207b7SJohn Levon 		vsl = data->right_vsl;
19381f5207b7SJohn Levon 		if (strcmp(var, right_var) == 0) {
19391f5207b7SJohn Levon 			expr = data->left;
19401f5207b7SJohn Levon 			var = data->left_var;
19411f5207b7SJohn Levon 			vsl = data->left_vsl;
19421f5207b7SJohn Levon 			comparison = flip_comparison(comparison);
19431f5207b7SJohn Levon 		}
19441f5207b7SJohn Levon 		comparison = combine_comparisons(left_compare, comparison);
19451f5207b7SJohn Levon 		if (!comparison)
19461f5207b7SJohn Levon 			continue;
19471f5207b7SJohn Levon 		add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
19481f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
19491f5207b7SJohn Levon 
19501f5207b7SJohn Levon done:
19511f5207b7SJohn Levon 	free_string(right_var);
19521f5207b7SJohn Levon }
19531f5207b7SJohn Levon 
__add_return_comparison(struct expression * call,const char * range)19541f5207b7SJohn Levon void __add_return_comparison(struct expression *call, const char *range)
19551f5207b7SJohn Levon {
19561f5207b7SJohn Levon 	struct expression *arg;
19571f5207b7SJohn Levon 	int comparison;
1958c85f09ccSJohn Levon 	char buf[16];
19591f5207b7SJohn Levon 
19601f5207b7SJohn Levon 	if (!str_to_comparison_arg(range, call, &comparison, &arg))
19611f5207b7SJohn Levon 		return;
1962c85f09ccSJohn Levon 	snprintf(buf, sizeof(buf), "%s", show_comparison(comparison));
19631f5207b7SJohn Levon 	update_links_from_call(call, comparison, arg);
19641f5207b7SJohn Levon 	add_comparison(call, comparison, arg);
19651f5207b7SJohn Levon }
19661f5207b7SJohn Levon 
__add_comparison_info(struct expression * expr,struct expression * call,const char * range)19671f5207b7SJohn Levon void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
19681f5207b7SJohn Levon {
19691f5207b7SJohn Levon 	copy_comparisons(expr, call);
19701f5207b7SJohn Levon }
19711f5207b7SJohn Levon 
get_mask_comparison(struct expression * expr,int ignore)19721f5207b7SJohn Levon static char *get_mask_comparison(struct expression *expr, int ignore)
19731f5207b7SJohn Levon {
19741f5207b7SJohn Levon 	struct expression *tmp, *right;
19751f5207b7SJohn Levon 	int count, param;
19761f5207b7SJohn Levon 	char buf[256];
19771f5207b7SJohn Levon 
19781f5207b7SJohn Levon 	/* The return value for "return foo & param;" is <= param */
19791f5207b7SJohn Levon 
19801f5207b7SJohn Levon 	count = 0;
19811f5207b7SJohn Levon 	while ((tmp = get_assigned_expr(expr))) {
19821f5207b7SJohn Levon 		expr = strip_expr(tmp);
19831f5207b7SJohn Levon 		if (count++ > 4)
19841f5207b7SJohn Levon 			break;
19851f5207b7SJohn Levon 	}
19861f5207b7SJohn Levon 
19871f5207b7SJohn Levon 	if (expr->type != EXPR_BINOP || expr->op != '&')
19881f5207b7SJohn Levon 		return NULL;
19891f5207b7SJohn Levon 
19901f5207b7SJohn Levon 	right = strip_expr(expr->right);
19911f5207b7SJohn Levon 	param = get_param_num(right);
19921f5207b7SJohn Levon 	if (param < 0 || param == ignore)
19931f5207b7SJohn Levon 		return NULL;
19941f5207b7SJohn Levon 
19951f5207b7SJohn Levon 	snprintf(buf, sizeof(buf), "[<=$%d]", param);
19961f5207b7SJohn Levon 	return alloc_sname(buf);
19971f5207b7SJohn Levon }
19981f5207b7SJohn Levon 
range_comparison_to_param_helper(struct expression * expr,char starts_with,int ignore)19991f5207b7SJohn Levon static char *range_comparison_to_param_helper(struct expression *expr, char starts_with, int ignore)
20001f5207b7SJohn Levon {
20011f5207b7SJohn Levon 	struct symbol *param;
20021f5207b7SJohn Levon 	char *var = NULL;
20031f5207b7SJohn Levon 	char buf[256];
20041f5207b7SJohn Levon 	char *ret_str = NULL;
20051f5207b7SJohn Levon 	int compare;
20061f5207b7SJohn Levon 	int i;
20071f5207b7SJohn Levon 
20081f5207b7SJohn Levon 	if (!expr)
20091f5207b7SJohn Levon 		return NULL;
20101f5207b7SJohn Levon 
20111f5207b7SJohn Levon 	var = chunk_to_var(expr);
20121f5207b7SJohn Levon 	if (!var)
20131f5207b7SJohn Levon 		goto try_mask;
20141f5207b7SJohn Levon 
20151f5207b7SJohn Levon 	i = -1;
20161f5207b7SJohn Levon 	FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
20171f5207b7SJohn Levon 		i++;
20181f5207b7SJohn Levon 		if (i == ignore)
20191f5207b7SJohn Levon 			continue;
20201f5207b7SJohn Levon 		if (!param->ident)
20211f5207b7SJohn Levon 			continue;
20221f5207b7SJohn Levon 		snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
20231f5207b7SJohn Levon 		compare = get_comparison_strings(var, buf);
2024c85f09ccSJohn Levon 		if (compare == UNKNOWN_COMPARISON ||
2025c85f09ccSJohn Levon 		    compare == IMPOSSIBLE_COMPARISON)
20261f5207b7SJohn Levon 			continue;
2027c85f09ccSJohn Levon 		if (show_comparison(compare)[0] != starts_with)
20281f5207b7SJohn Levon 			continue;
2029c85f09ccSJohn Levon 		snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
20301f5207b7SJohn Levon 		ret_str = alloc_sname(buf);
20311f5207b7SJohn Levon 		break;
20321f5207b7SJohn Levon 	} END_FOR_EACH_PTR(param);
20331f5207b7SJohn Levon 
20341f5207b7SJohn Levon 	free_string(var);
20351f5207b7SJohn Levon 	if (!ret_str)
20361f5207b7SJohn Levon 		goto try_mask;
20371f5207b7SJohn Levon 
20381f5207b7SJohn Levon 	return ret_str;
20391f5207b7SJohn Levon 
20401f5207b7SJohn Levon try_mask:
20411f5207b7SJohn Levon 	if (starts_with == '<')
20421f5207b7SJohn Levon 		ret_str = get_mask_comparison(expr, ignore);
20431f5207b7SJohn Levon 	return ret_str;
20441f5207b7SJohn Levon }
20451f5207b7SJohn Levon 
name_sym_to_param_comparison(const char * name,struct symbol * sym)20461f5207b7SJohn Levon char *name_sym_to_param_comparison(const char *name, struct symbol *sym)
20471f5207b7SJohn Levon {
20481f5207b7SJohn Levon 	struct symbol *param;
20491f5207b7SJohn Levon 	char buf[256];
20501f5207b7SJohn Levon 	int compare;
20511f5207b7SJohn Levon 	int i;
20521f5207b7SJohn Levon 
20531f5207b7SJohn Levon 	i = -1;
20541f5207b7SJohn Levon 	FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
20551f5207b7SJohn Levon 		i++;
20561f5207b7SJohn Levon 		if (!param->ident)
20571f5207b7SJohn Levon 			continue;
20581f5207b7SJohn Levon 		snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
20591f5207b7SJohn Levon 		compare = get_comparison_strings(name, buf);
2060c85f09ccSJohn Levon 		if (compare == UNKNOWN_COMPARISON ||
2061c85f09ccSJohn Levon 		    compare == IMPOSSIBLE_COMPARISON)
20621f5207b7SJohn Levon 			continue;
2063c85f09ccSJohn Levon 		snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
20641f5207b7SJohn Levon 		return alloc_sname(buf);
20651f5207b7SJohn Levon 	} END_FOR_EACH_PTR(param);
20661f5207b7SJohn Levon 
20671f5207b7SJohn Levon 	return NULL;
20681f5207b7SJohn Levon }
20691f5207b7SJohn Levon 
expr_equal_to_param(struct expression * expr,int ignore)20701f5207b7SJohn Levon char *expr_equal_to_param(struct expression *expr, int ignore)
20711f5207b7SJohn Levon {
20721f5207b7SJohn Levon 	return range_comparison_to_param_helper(expr, '=', ignore);
20731f5207b7SJohn Levon }
20741f5207b7SJohn Levon 
expr_lte_to_param(struct expression * expr,int ignore)20751f5207b7SJohn Levon char *expr_lte_to_param(struct expression *expr, int ignore)
20761f5207b7SJohn Levon {
20771f5207b7SJohn Levon 	return range_comparison_to_param_helper(expr, '<', ignore);
20781f5207b7SJohn Levon }
20791f5207b7SJohn Levon 
expr_param_comparison(struct expression * expr,int ignore)20801f5207b7SJohn Levon char *expr_param_comparison(struct expression *expr, int ignore)
20811f5207b7SJohn Levon {
20821f5207b7SJohn Levon 	struct symbol *param;
20831f5207b7SJohn Levon 	char *var = NULL;
20841f5207b7SJohn Levon 	char buf[256];
20851f5207b7SJohn Levon 	char *ret_str = NULL;
20861f5207b7SJohn Levon 	int compare;
20871f5207b7SJohn Levon 	int i;
20881f5207b7SJohn Levon 
20891f5207b7SJohn Levon 	var = chunk_to_var(expr);
20901f5207b7SJohn Levon 	if (!var)
20911f5207b7SJohn Levon 		goto free;
20921f5207b7SJohn Levon 
20931f5207b7SJohn Levon 	i = -1;
20941f5207b7SJohn Levon 	FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
20951f5207b7SJohn Levon 		i++;
20961f5207b7SJohn Levon 		if (i == ignore)
20971f5207b7SJohn Levon 			continue;
20981f5207b7SJohn Levon 		if (!param->ident)
20991f5207b7SJohn Levon 			continue;
21001f5207b7SJohn Levon 		snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
21011f5207b7SJohn Levon 		compare = get_comparison_strings(var, buf);
21021f5207b7SJohn Levon 		if (!compare)
21031f5207b7SJohn Levon 			continue;
2104c85f09ccSJohn Levon 		snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
21051f5207b7SJohn Levon 		ret_str = alloc_sname(buf);
21061f5207b7SJohn Levon 		break;
21071f5207b7SJohn Levon 	} END_FOR_EACH_PTR(param);
21081f5207b7SJohn Levon 
21091f5207b7SJohn Levon free:
21101f5207b7SJohn Levon 	free_string(var);
21111f5207b7SJohn Levon 	return ret_str;
21121f5207b7SJohn Levon }
21131f5207b7SJohn Levon 
get_printed_param_name(struct expression * call,const char * param_name,struct symbol * param_sym)21141f5207b7SJohn Levon char *get_printed_param_name(struct expression *call, const char *param_name, struct symbol *param_sym)
21151f5207b7SJohn Levon {
21161f5207b7SJohn Levon 	struct expression *arg;
21171f5207b7SJohn Levon 	char *name;
21181f5207b7SJohn Levon 	struct symbol *sym;
21191f5207b7SJohn Levon 	static char buf[256];
21201f5207b7SJohn Levon 	int len;
21211f5207b7SJohn Levon 	int i;
21221f5207b7SJohn Levon 
21231f5207b7SJohn Levon 	i = -1;
21241f5207b7SJohn Levon 	FOR_EACH_PTR(call->args, arg) {
21251f5207b7SJohn Levon 		i++;
21261f5207b7SJohn Levon 
21271f5207b7SJohn Levon 		name = expr_to_var_sym(arg, &sym);
21281f5207b7SJohn Levon 		if (!name || !sym)
21291f5207b7SJohn Levon 			continue;
21301f5207b7SJohn Levon 		if (sym != param_sym)
21311f5207b7SJohn Levon 			continue;
21321f5207b7SJohn Levon 
21331f5207b7SJohn Levon 		len = strlen(name);
21341f5207b7SJohn Levon 		if (strncmp(name, param_name, len) != 0)
21351f5207b7SJohn Levon 			continue;
21361f5207b7SJohn Levon 		if (param_name[len] == '\0') {
21371f5207b7SJohn Levon 			snprintf(buf, sizeof(buf), "$%d", i);
21381f5207b7SJohn Levon 			return buf;
21391f5207b7SJohn Levon 		}
21401f5207b7SJohn Levon 		if (param_name[len] != '-')
21411f5207b7SJohn Levon 			continue;
21421f5207b7SJohn Levon 		snprintf(buf, sizeof(buf), "$%d%s", i, param_name + len);
21431f5207b7SJohn Levon 		return buf;
21441f5207b7SJohn Levon 	} END_FOR_EACH_PTR(arg);
21451f5207b7SJohn Levon 
21461f5207b7SJohn Levon 	return NULL;
21471f5207b7SJohn Levon }
21481f5207b7SJohn Levon 
match_call_info(struct expression * expr)21491f5207b7SJohn Levon static void match_call_info(struct expression *expr)
21501f5207b7SJohn Levon {
21511f5207b7SJohn Levon 	struct expression *arg;
21521f5207b7SJohn Levon 	struct smatch_state *state;
21531f5207b7SJohn Levon 	struct sm_state *sm;
21541f5207b7SJohn Levon 	struct compare_data *data;
21551f5207b7SJohn Levon 	int comparison;
21561f5207b7SJohn Levon 	struct string_list *links;
21571f5207b7SJohn Levon 	char *arg_name;
21581f5207b7SJohn Levon 	const char *right_name;
21591f5207b7SJohn Levon 	char *link;
21601f5207b7SJohn Levon 	char info_buf[256];
21611f5207b7SJohn Levon 	int i;
21621f5207b7SJohn Levon 
21631f5207b7SJohn Levon 	i = -1;
21641f5207b7SJohn Levon 	FOR_EACH_PTR(expr->args, arg) {
21651f5207b7SJohn Levon 		i++;
21661f5207b7SJohn Levon 
21671f5207b7SJohn Levon 		state = get_state_chunk(link_id, arg);
21681f5207b7SJohn Levon 		if (!state)
21691f5207b7SJohn Levon 			continue;
21701f5207b7SJohn Levon 
21711f5207b7SJohn Levon 		links = state->data;
21721f5207b7SJohn Levon 		FOR_EACH_PTR(links, link) {
21731f5207b7SJohn Levon 			struct var_sym_list *right_vsl;
21741f5207b7SJohn Levon 			struct var_sym *right_vs;
21751f5207b7SJohn Levon 
21761f5207b7SJohn Levon 
21771f5207b7SJohn Levon 			if (strstr(link, " orig"))
21781f5207b7SJohn Levon 				continue;
21795a0e240fSJohn Levon 			sm = get_sm_state(comparison_id, link, NULL);
21801f5207b7SJohn Levon 			if (!sm)
21811f5207b7SJohn Levon 				continue;
21821f5207b7SJohn Levon 			data = sm->state->data;
2183c85f09ccSJohn Levon 			if (!data ||
2184c85f09ccSJohn Levon 			    data->comparison == UNKNOWN_COMPARISON ||
2185c85f09ccSJohn Levon 			    data->comparison == IMPOSSIBLE_COMPARISON)
21861f5207b7SJohn Levon 				continue;
21871f5207b7SJohn Levon 			arg_name = expr_to_var(arg);
21881f5207b7SJohn Levon 			if (!arg_name)
21891f5207b7SJohn Levon 				continue;
21901f5207b7SJohn Levon 
21911f5207b7SJohn Levon 			right_vsl = NULL;
21921f5207b7SJohn Levon 			if (strcmp(data->left_var, arg_name) == 0) {
21931f5207b7SJohn Levon 				comparison = data->comparison;
21941f5207b7SJohn Levon 				right_name = data->right_var;
21951f5207b7SJohn Levon 				right_vsl = data->right_vsl;
21961f5207b7SJohn Levon 			} else if (strcmp(data->right_var, arg_name) == 0) {
21971f5207b7SJohn Levon 				comparison = flip_comparison(data->comparison);
21981f5207b7SJohn Levon 				right_name = data->left_var;
21991f5207b7SJohn Levon 				right_vsl = data->left_vsl;
22001f5207b7SJohn Levon 			}
22011f5207b7SJohn Levon 			if (!right_vsl || ptr_list_size((struct ptr_list *)right_vsl) != 1)
22021f5207b7SJohn Levon 				goto free;
22031f5207b7SJohn Levon 
22041f5207b7SJohn Levon 			right_vs = first_ptr_list((struct ptr_list *)right_vsl);
22051f5207b7SJohn Levon 			if (strcmp(right_vs->var, right_name) != 0)
22061f5207b7SJohn Levon 				goto free;
22071f5207b7SJohn Levon 			right_name = get_printed_param_name(expr, right_vs->var, right_vs->sym);
22081f5207b7SJohn Levon 			if (!right_name)
22091f5207b7SJohn Levon 				goto free;
2210c85f09ccSJohn Levon 			snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(comparison), right_name);
22111f5207b7SJohn Levon 			sql_insert_caller_info(expr, PARAM_COMPARE, i, "$", info_buf);
22121f5207b7SJohn Levon 
22131f5207b7SJohn Levon free:
22141f5207b7SJohn Levon 			free_string(arg_name);
22151f5207b7SJohn Levon 		} END_FOR_EACH_PTR(link);
22161f5207b7SJohn Levon 	} END_FOR_EACH_PTR(arg);
22171f5207b7SJohn Levon }
22181f5207b7SJohn Levon 
struct_member_callback(struct expression * call,int param,char * printed_name,struct sm_state * link_sm)22191f5207b7SJohn Levon static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *link_sm)
22201f5207b7SJohn Levon {
22211f5207b7SJohn Levon 	struct sm_state *compare_sm;
22221f5207b7SJohn Levon 	struct string_list *links;
22231f5207b7SJohn Levon 	char *link;
22241f5207b7SJohn Levon 	struct compare_data *data;
22251f5207b7SJohn Levon 	struct var_sym *left, *right;
22261f5207b7SJohn Levon 	static char info_buf[256];
22271f5207b7SJohn Levon 	const char *right_name;
22281f5207b7SJohn Levon 
22291f5207b7SJohn Levon 	if (strstr(printed_name, " orig"))
22301f5207b7SJohn Levon 		return;
22311f5207b7SJohn Levon 
22321f5207b7SJohn Levon 	links = link_sm->state->data;
22331f5207b7SJohn Levon 	FOR_EACH_PTR(links, link) {
22345a0e240fSJohn Levon 		compare_sm = get_sm_state(comparison_id, link, NULL);
22351f5207b7SJohn Levon 		if (!compare_sm)
22361f5207b7SJohn Levon 			continue;
22371f5207b7SJohn Levon 		data = compare_sm->state->data;
22381f5207b7SJohn Levon 		if (!data || !data->comparison)
22391f5207b7SJohn Levon 			continue;
22401f5207b7SJohn Levon 
22411f5207b7SJohn Levon 		if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
22421f5207b7SJohn Levon 		    ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
22431f5207b7SJohn Levon 			continue;
22441f5207b7SJohn Levon 		left = first_ptr_list((struct ptr_list *)data->left_vsl);
22451f5207b7SJohn Levon 		right = first_ptr_list((struct ptr_list *)data->right_vsl);
22461f5207b7SJohn Levon 		if (left->sym == right->sym &&
22471f5207b7SJohn Levon 		    strcmp(left->var, right->var) == 0)
22481f5207b7SJohn Levon 			continue;
22491f5207b7SJohn Levon 		/*
22501f5207b7SJohn Levon 		 * Both parameters link to this comparison so only
22511f5207b7SJohn Levon 		 * record the first one.
22521f5207b7SJohn Levon 		 */
22531f5207b7SJohn Levon 		if (left->sym != link_sm->sym ||
22541f5207b7SJohn Levon 		    strcmp(left->var, link_sm->name) != 0)
22551f5207b7SJohn Levon 			continue;
22561f5207b7SJohn Levon 
22571f5207b7SJohn Levon 		right_name = get_printed_param_name(call, right->var, right->sym);
22581f5207b7SJohn Levon 		if (!right_name)
22591f5207b7SJohn Levon 			continue;
2260c85f09ccSJohn Levon 		snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(data->comparison), right_name);
22611f5207b7SJohn Levon 		sql_insert_caller_info(call, PARAM_COMPARE, param, printed_name, info_buf);
22621f5207b7SJohn Levon 	} END_FOR_EACH_PTR(link);
22631f5207b7SJohn Levon }
22641f5207b7SJohn Levon 
print_return_value_comparison(int return_id,char * return_ranges,struct expression * expr)22651f5207b7SJohn Levon static void print_return_value_comparison(int return_id, char *return_ranges, struct expression *expr)
22661f5207b7SJohn Levon {
22671f5207b7SJohn Levon 	char *name;
22681f5207b7SJohn Levon 	const char *tmp_name;
22691f5207b7SJohn Levon 	struct symbol *sym;
22701f5207b7SJohn Levon 	int param;
22711f5207b7SJohn Levon 	char info_buf[256];
22721f5207b7SJohn Levon 
22731f5207b7SJohn Levon 	/*
22741f5207b7SJohn Levon 	 * TODO: This only prints == comparisons. That's probably the most
22751f5207b7SJohn Levon 	 * useful comparison because == max has lots of implications.  But it
22761f5207b7SJohn Levon 	 * would be good to capture the rest as well.
22771f5207b7SJohn Levon 	 *
22781f5207b7SJohn Levon 	 * This information is already in the DB but it's in the parameter math
22791f5207b7SJohn Levon 	 * bits and it's awkward to use it.  This is is the simpler, possibly
22801f5207b7SJohn Levon 	 * cleaner way, but not necessarily the best, I don't know.
22811f5207b7SJohn Levon 	 */
22821f5207b7SJohn Levon 
22831f5207b7SJohn Levon 	if (!expr)
22841f5207b7SJohn Levon 		return;
22851f5207b7SJohn Levon 	name = expr_to_var_sym(expr, &sym);
22861f5207b7SJohn Levon 	if (!name || !sym)
22871f5207b7SJohn Levon 		goto free;
22881f5207b7SJohn Levon 
22891f5207b7SJohn Levon 	param = get_param_num_from_sym(sym);
22901f5207b7SJohn Levon 	if (param < 0)
22911f5207b7SJohn Levon 		goto free;
22921f5207b7SJohn Levon 	if (param_was_set_var_sym(name, sym))
22931f5207b7SJohn Levon 		goto free;
22941f5207b7SJohn Levon 
22951f5207b7SJohn Levon 	tmp_name = get_param_name_var_sym(name, sym);
22961f5207b7SJohn Levon 	if (!tmp_name)
22971f5207b7SJohn Levon 		goto free;
22981f5207b7SJohn Levon 
22991f5207b7SJohn Levon 	snprintf(info_buf, sizeof(info_buf), "== $%d%s", param, tmp_name + 1);
23001f5207b7SJohn Levon 	sql_insert_return_states(return_id, return_ranges,
23011f5207b7SJohn Levon 				PARAM_COMPARE, -1, "$", info_buf);
23021f5207b7SJohn Levon free:
23031f5207b7SJohn Levon 	free_string(name);
23041f5207b7SJohn Levon }
23051f5207b7SJohn Levon 
print_return_comparison(int return_id,char * return_ranges,struct expression * expr)23061f5207b7SJohn Levon static void print_return_comparison(int return_id, char *return_ranges, struct expression *expr)
23071f5207b7SJohn Levon {
23081f5207b7SJohn Levon 	struct sm_state *tmp;
23091f5207b7SJohn Levon 	struct string_list *links;
23101f5207b7SJohn Levon 	char *link;
23111f5207b7SJohn Levon 	struct sm_state *sm;
23121f5207b7SJohn Levon 	struct compare_data *data;
23131f5207b7SJohn Levon 	struct var_sym *left, *right;
23141f5207b7SJohn Levon 	int left_param, right_param;
23151f5207b7SJohn Levon 	char left_buf[256];
23161f5207b7SJohn Levon 	char right_buf[256];
23171f5207b7SJohn Levon 	char info_buf[258];
23181f5207b7SJohn Levon 	const char *tmp_name;
23191f5207b7SJohn Levon 
23201f5207b7SJohn Levon 	print_return_value_comparison(return_id, return_ranges, expr);
23211f5207b7SJohn Levon 
23221f5207b7SJohn Levon 	FOR_EACH_MY_SM(link_id, __get_cur_stree(), tmp) {
23231f5207b7SJohn Levon 		if (get_param_num_from_sym(tmp->sym) < 0)
23241f5207b7SJohn Levon 			continue;
23251f5207b7SJohn Levon 		links = tmp->state->data;
23261f5207b7SJohn Levon 		FOR_EACH_PTR(links, link) {
23275a0e240fSJohn Levon 			sm = get_sm_state(comparison_id, link, NULL);
23281f5207b7SJohn Levon 			if (!sm)
23291f5207b7SJohn Levon 				continue;
23301f5207b7SJohn Levon 			data = sm->state->data;
2331c85f09ccSJohn Levon 			if (!data ||
2332c85f09ccSJohn Levon 			    data->comparison == UNKNOWN_COMPARISON ||
2333c85f09ccSJohn Levon 			    data->comparison == IMPOSSIBLE_COMPARISON)
23341f5207b7SJohn Levon 				continue;
23351f5207b7SJohn Levon 			if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
23361f5207b7SJohn Levon 			    ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
23371f5207b7SJohn Levon 				continue;
23381f5207b7SJohn Levon 			left = first_ptr_list((struct ptr_list *)data->left_vsl);
23391f5207b7SJohn Levon 			right = first_ptr_list((struct ptr_list *)data->right_vsl);
23401f5207b7SJohn Levon 			if (left->sym == right->sym &&
23411f5207b7SJohn Levon 			    strcmp(left->var, right->var) == 0)
23421f5207b7SJohn Levon 				continue;
23431f5207b7SJohn Levon 			/*
23441f5207b7SJohn Levon 			 * Both parameters link to this comparison so only
23451f5207b7SJohn Levon 			 * record the first one.
23461f5207b7SJohn Levon 			 */
23471f5207b7SJohn Levon 			if (left->sym != tmp->sym ||
23481f5207b7SJohn Levon 			    strcmp(left->var, tmp->name) != 0)
23491f5207b7SJohn Levon 				continue;
23501f5207b7SJohn Levon 
23511f5207b7SJohn Levon 			if (strstr(right->var, " orig"))
23521f5207b7SJohn Levon 				continue;
23531f5207b7SJohn Levon 
23541f5207b7SJohn Levon 			left_param = get_param_num_from_sym(left->sym);
23551f5207b7SJohn Levon 			right_param = get_param_num_from_sym(right->sym);
23561f5207b7SJohn Levon 			if (left_param < 0 || right_param < 0)
23571f5207b7SJohn Levon 				continue;
23581f5207b7SJohn Levon 
23591f5207b7SJohn Levon 			tmp_name = get_param_name_var_sym(left->var, left->sym);
23601f5207b7SJohn Levon 			if (!tmp_name)
23611f5207b7SJohn Levon 				continue;
23621f5207b7SJohn Levon 			snprintf(left_buf, sizeof(left_buf), "%s", tmp_name);
23631f5207b7SJohn Levon 
23641f5207b7SJohn Levon 			tmp_name = get_param_name_var_sym(right->var, right->sym);
23651f5207b7SJohn Levon 			if (!tmp_name || tmp_name[0] != '$')
23661f5207b7SJohn Levon 				continue;
23671f5207b7SJohn Levon 			snprintf(right_buf, sizeof(right_buf), "$%d%s", right_param, tmp_name + 1);
23681f5207b7SJohn Levon 
23691f5207b7SJohn Levon 			/*
23701f5207b7SJohn Levon 			 * FIXME: this should reject $ type variables (as
23711f5207b7SJohn Levon 			 * opposed to $->foo type).  Those should come from
23721f5207b7SJohn Levon 			 * smatch_param_compare_limit.c.
23731f5207b7SJohn Levon 			 */
23741f5207b7SJohn Levon 
2375c85f09ccSJohn Levon 			snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(data->comparison), right_buf);
23761f5207b7SJohn Levon 			sql_insert_return_states(return_id, return_ranges,
23771f5207b7SJohn Levon 					PARAM_COMPARE, left_param, left_buf, info_buf);
23781f5207b7SJohn Levon 		} END_FOR_EACH_PTR(link);
23791f5207b7SJohn Levon 
23801f5207b7SJohn Levon 	} END_FOR_EACH_SM(tmp);
23811f5207b7SJohn Levon }
23821f5207b7SJohn Levon 
parse_comparison(char ** value,int * op)23831f5207b7SJohn Levon static int parse_comparison(char **value, int *op)
23841f5207b7SJohn Levon {
23851f5207b7SJohn Levon 
23861f5207b7SJohn Levon 	*op = **value;
23871f5207b7SJohn Levon 
23881f5207b7SJohn Levon 	switch (*op) {
23891f5207b7SJohn Levon 	case '<':
23901f5207b7SJohn Levon 		(*value)++;
23911f5207b7SJohn Levon 		if (**value == '=') {
23921f5207b7SJohn Levon 			(*value)++;
23931f5207b7SJohn Levon 			*op = SPECIAL_LTE;
23941f5207b7SJohn Levon 		}
23951f5207b7SJohn Levon 		break;
23961f5207b7SJohn Levon 	case '=':
23971f5207b7SJohn Levon 		(*value)++;
23981f5207b7SJohn Levon 		(*value)++;
23991f5207b7SJohn Levon 		*op = SPECIAL_EQUAL;
24001f5207b7SJohn Levon 		break;
24011f5207b7SJohn Levon 	case '!':
24021f5207b7SJohn Levon 		(*value)++;
24031f5207b7SJohn Levon 		(*value)++;
24041f5207b7SJohn Levon 		*op = SPECIAL_NOTEQUAL;
24051f5207b7SJohn Levon 		break;
24061f5207b7SJohn Levon 	case '>':
24071f5207b7SJohn Levon 		(*value)++;
24081f5207b7SJohn Levon 		if (**value == '=') {
24091f5207b7SJohn Levon 			(*value)++;
24101f5207b7SJohn Levon 			*op = SPECIAL_GTE;
24111f5207b7SJohn Levon 		}
24121f5207b7SJohn Levon 		break;
24131f5207b7SJohn Levon 	default:
24141f5207b7SJohn Levon 		return 0;
24151f5207b7SJohn Levon 	}
24161f5207b7SJohn Levon 
24171f5207b7SJohn Levon 	if (**value != ' ') {
24181f5207b7SJohn Levon 		sm_perror("parsing comparison.  %s", *value);
24191f5207b7SJohn Levon 		return 0;
24201f5207b7SJohn Levon 	}
24211f5207b7SJohn Levon 
24221f5207b7SJohn Levon 	(*value)++;
24231f5207b7SJohn Levon 	return 1;
24241f5207b7SJohn Levon }
24251f5207b7SJohn Levon 
split_op_param_key(char * value,int * op,int * param,char ** key)24261f5207b7SJohn Levon static int split_op_param_key(char *value, int *op, int *param, char **key)
24271f5207b7SJohn Levon {
24281f5207b7SJohn Levon 	static char buf[256];
24291f5207b7SJohn Levon 	char *p;
24301f5207b7SJohn Levon 
24311f5207b7SJohn Levon 	if (!parse_comparison(&value, op))
24321f5207b7SJohn Levon 		return 0;
24331f5207b7SJohn Levon 
2434efe51d0cSJohn Levon 	snprintf(buf, sizeof(buf), "%s", value);
24351f5207b7SJohn Levon 
24361f5207b7SJohn Levon 	p = buf;
24371f5207b7SJohn Levon 	if (*p++ != '$')
24381f5207b7SJohn Levon 		return 0;
24391f5207b7SJohn Levon 
24401f5207b7SJohn Levon 	*param = atoi(p);
24411f5207b7SJohn Levon 	if (*param < 0 || *param > 99)
24421f5207b7SJohn Levon 		return 0;
24431f5207b7SJohn Levon 	p++;
24441f5207b7SJohn Levon 	if (*param > 9)
24451f5207b7SJohn Levon 		p++;
24461f5207b7SJohn Levon 	p--;
24471f5207b7SJohn Levon 	*p = '$';
24481f5207b7SJohn Levon 	*key = p;
24491f5207b7SJohn Levon 
24501f5207b7SJohn Levon 	return 1;
24511f5207b7SJohn Levon }
24521f5207b7SJohn Levon 
db_return_comparison(struct expression * expr,int left_param,char * key,char * value)24531f5207b7SJohn Levon static void db_return_comparison(struct expression *expr, int left_param, char *key, char *value)
24541f5207b7SJohn Levon {
24551f5207b7SJohn Levon 	struct expression *left_arg, *right_arg;
24561f5207b7SJohn Levon 	char *left_name = NULL;
24571f5207b7SJohn Levon 	struct symbol *left_sym;
24581f5207b7SJohn Levon 	char *right_name = NULL;
24591f5207b7SJohn Levon 	struct symbol *right_sym;
24601f5207b7SJohn Levon 	int op;
24611f5207b7SJohn Levon 	int right_param;
24621f5207b7SJohn Levon 	char *right_key;
24631f5207b7SJohn Levon 	struct var_sym_list *left_vsl = NULL, *right_vsl = NULL;
24641f5207b7SJohn Levon 
24651f5207b7SJohn Levon 	if (left_param == -1) {
24661f5207b7SJohn Levon 		if (expr->type != EXPR_ASSIGNMENT)
24671f5207b7SJohn Levon 			return;
24681f5207b7SJohn Levon 		left_arg = strip_expr(expr->left);
24691f5207b7SJohn Levon 
24701f5207b7SJohn Levon 		while (expr->type == EXPR_ASSIGNMENT)
24711f5207b7SJohn Levon 			expr = strip_expr(expr->right);
24721f5207b7SJohn Levon 		if (expr->type != EXPR_CALL)
24731f5207b7SJohn Levon 			return;
24741f5207b7SJohn Levon 	} else {
24751f5207b7SJohn Levon 		while (expr->type == EXPR_ASSIGNMENT)
24761f5207b7SJohn Levon 			expr = strip_expr(expr->right);
24771f5207b7SJohn Levon 		if (expr->type != EXPR_CALL)
24781f5207b7SJohn Levon 			return;
24791f5207b7SJohn Levon 
24801f5207b7SJohn Levon 		left_arg = get_argument_from_call_expr(expr->args, left_param);
24811f5207b7SJohn Levon 		if (!left_arg)
24821f5207b7SJohn Levon 			return;
24831f5207b7SJohn Levon 	}
24841f5207b7SJohn Levon 
24851f5207b7SJohn Levon 	if (!split_op_param_key(value, &op, &right_param, &right_key))
24861f5207b7SJohn Levon 		return;
24871f5207b7SJohn Levon 
24881f5207b7SJohn Levon 	right_arg = get_argument_from_call_expr(expr->args, right_param);
24891f5207b7SJohn Levon 	if (!right_arg)
24901f5207b7SJohn Levon 		return;
24911f5207b7SJohn Levon 
24921f5207b7SJohn Levon 	left_name = get_variable_from_key(left_arg, key, &left_sym);
24931f5207b7SJohn Levon 	if (!left_name || !left_sym)
24941f5207b7SJohn Levon 		goto free;
24951f5207b7SJohn Levon 
24961f5207b7SJohn Levon 	right_name = get_variable_from_key(right_arg, right_key, &right_sym);
24971f5207b7SJohn Levon 	if (!right_name || !right_sym)
24981f5207b7SJohn Levon 		goto free;
24991f5207b7SJohn Levon 
25001f5207b7SJohn Levon 	add_var_sym(&left_vsl, left_name, left_sym);
25011f5207b7SJohn Levon 	add_var_sym(&right_vsl, right_name, right_sym);
25021f5207b7SJohn Levon 
25031f5207b7SJohn Levon 	add_comparison_var_sym(NULL, left_name, left_vsl, op, NULL, right_name, right_vsl);
25041f5207b7SJohn Levon 
25051f5207b7SJohn Levon free:
25061f5207b7SJohn Levon 	free_string(left_name);
25071f5207b7SJohn Levon 	free_string(right_name);
25081f5207b7SJohn Levon }
25091f5207b7SJohn Levon 
param_compare_limit_is_impossible(struct expression * expr,int left_param,char * left_key,char * value)25101f5207b7SJohn Levon int param_compare_limit_is_impossible(struct expression *expr, int left_param, char *left_key, char *value)
25111f5207b7SJohn Levon {
25121f5207b7SJohn Levon 	struct smatch_state *state;
25131f5207b7SJohn Levon 	char *left_name = NULL;
25141f5207b7SJohn Levon 	char *right_name = NULL;
25151f5207b7SJohn Levon 	struct symbol *left_sym, *right_sym;
25161f5207b7SJohn Levon 	struct expression *left_arg, *right_arg;
25171f5207b7SJohn Levon 	int op, state_op;
25181f5207b7SJohn Levon 	int right_param;
25191f5207b7SJohn Levon 	char *right_key;
25201f5207b7SJohn Levon 	int ret = 0;
25211f5207b7SJohn Levon 	char buf[256];
25221f5207b7SJohn Levon 
25231f5207b7SJohn Levon 	while (expr->type == EXPR_ASSIGNMENT)
25241f5207b7SJohn Levon 		expr = strip_expr(expr->right);
25251f5207b7SJohn Levon 	if (expr->type != EXPR_CALL)
25261f5207b7SJohn Levon 		return 0;
25271f5207b7SJohn Levon 
25281f5207b7SJohn Levon 	if (!split_op_param_key(value, &op, &right_param, &right_key))
25291f5207b7SJohn Levon 		return 0;
25301f5207b7SJohn Levon 
25311f5207b7SJohn Levon 	left_arg = get_argument_from_call_expr(expr->args, left_param);
25321f5207b7SJohn Levon 	if (!left_arg)
25331f5207b7SJohn Levon 		return 0;
25341f5207b7SJohn Levon 
25351f5207b7SJohn Levon 	right_arg = get_argument_from_call_expr(expr->args, right_param);
25361f5207b7SJohn Levon 	if (!right_arg)
25371f5207b7SJohn Levon 		return 0;
25381f5207b7SJohn Levon 
25391f5207b7SJohn Levon 	left_name = get_variable_from_key(left_arg, left_key, &left_sym);
25401f5207b7SJohn Levon 	right_name = get_variable_from_key(right_arg, right_key, &right_sym);
25411f5207b7SJohn Levon 	if (!left_name || !right_name)
25421f5207b7SJohn Levon 		goto free;
25431f5207b7SJohn Levon 
25441f5207b7SJohn Levon 	snprintf(buf, sizeof(buf), "%s vs %s", left_name, right_name);
25455a0e240fSJohn Levon 	state = get_state(comparison_id, buf, NULL);
25461f5207b7SJohn Levon 	if (!state)
25471f5207b7SJohn Levon 		goto free;
25481f5207b7SJohn Levon 	state_op = state_to_comparison(state);
25491f5207b7SJohn Levon 	if (!state_op)
25501f5207b7SJohn Levon 		goto free;
25511f5207b7SJohn Levon 
2552c85f09ccSJohn Levon 	if (!comparison_intersection(remove_unsigned_from_comparison(state_op), op))
25531f5207b7SJohn Levon 		ret = 1;
25541f5207b7SJohn Levon free:
25551f5207b7SJohn Levon 	free_string(left_name);
25561f5207b7SJohn Levon 	free_string(right_name);
25571f5207b7SJohn Levon 	return ret;
25581f5207b7SJohn Levon }
25591f5207b7SJohn Levon 
impossibly_high_comparison(struct expression * expr)25601f5207b7SJohn Levon int impossibly_high_comparison(struct expression *expr)
25611f5207b7SJohn Levon {
25621f5207b7SJohn Levon 	struct smatch_state *link_state;
25631f5207b7SJohn Levon 	struct sm_state *sm;
25641f5207b7SJohn Levon 	struct string_list *links;
25651f5207b7SJohn Levon 	char *link;
25661f5207b7SJohn Levon 	struct compare_data *data;
25671f5207b7SJohn Levon 
25681f5207b7SJohn Levon 	link_state = get_state_expr(link_id, expr);
25691f5207b7SJohn Levon 	if (!link_state) {
25701f5207b7SJohn Levon 		if (expr->type == EXPR_BINOP &&
25711f5207b7SJohn Levon 		    (impossibly_high_comparison(expr->left) ||
25721f5207b7SJohn Levon 		     impossibly_high_comparison(expr->right)))
25731f5207b7SJohn Levon 			return 1;
25741f5207b7SJohn Levon 		return 0;
25751f5207b7SJohn Levon 	}
25761f5207b7SJohn Levon 
25771f5207b7SJohn Levon 	links = link_state->data;
25781f5207b7SJohn Levon 	FOR_EACH_PTR(links, link) {
25795a0e240fSJohn Levon 		sm = get_sm_state(comparison_id, link, NULL);
25801f5207b7SJohn Levon 		if (!sm)
25811f5207b7SJohn Levon 			continue;
25821f5207b7SJohn Levon 		data = sm->state->data;
25831f5207b7SJohn Levon 		if (!data)
25841f5207b7SJohn Levon 			continue;
25851f5207b7SJohn Levon 		if (!possibly_true(data->left, data->comparison, data->right))
25861f5207b7SJohn Levon 			return 1;
25871f5207b7SJohn Levon 	} END_FOR_EACH_PTR(link);
25881f5207b7SJohn Levon 
25891f5207b7SJohn Levon 	return 0;
25901f5207b7SJohn Levon }
25911f5207b7SJohn Levon 
free_data(struct symbol * sym)25921f5207b7SJohn Levon static void free_data(struct symbol *sym)
25931f5207b7SJohn Levon {
25941f5207b7SJohn Levon 	if (__inline_fn)
25951f5207b7SJohn Levon 		return;
25961f5207b7SJohn Levon 	clear_compare_data_alloc();
25971f5207b7SJohn Levon }
25981f5207b7SJohn Levon 
register_comparison(int id)25991f5207b7SJohn Levon void register_comparison(int id)
26001f5207b7SJohn Levon {
26015a0e240fSJohn Levon 	comparison_id = id;
26025a0e240fSJohn Levon 	set_dynamic_states(comparison_id);
26031f5207b7SJohn Levon 	add_hook(&save_start_states, AFTER_DEF_HOOK);
26045a0e240fSJohn Levon 	add_unmatched_state_hook(comparison_id, unmatched_comparison);
26055a0e240fSJohn Levon 	add_pre_merge_hook(comparison_id, &pre_merge_hook);
26065a0e240fSJohn Levon 	add_merge_hook(comparison_id, &merge_compare_states);
26071f5207b7SJohn Levon 	add_hook(&free_data, AFTER_FUNC_HOOK);
26081f5207b7SJohn Levon 	add_hook(&match_call_info, FUNCTION_CALL_HOOK);
26091f5207b7SJohn Levon 	add_split_return_callback(&print_return_comparison);
26101f5207b7SJohn Levon 
26111f5207b7SJohn Levon 	select_return_states_hook(PARAM_COMPARE, &db_return_comparison);
26121f5207b7SJohn Levon 	add_hook(&match_preop, OP_HOOK);
26131f5207b7SJohn Levon }
26141f5207b7SJohn Levon 
register_comparison_late(int id)26151f5207b7SJohn Levon void register_comparison_late(int id)
26161f5207b7SJohn Levon {
26171f5207b7SJohn Levon 	add_hook(&match_assign, ASSIGNMENT_HOOK);
26181f5207b7SJohn Levon }
26191f5207b7SJohn Levon 
register_comparison_links(int id)26201f5207b7SJohn Levon void register_comparison_links(int id)
26211f5207b7SJohn Levon {
26221f5207b7SJohn Levon 	link_id = id;
2623efe51d0cSJohn Levon 	db_ignore_states(link_id);
2624efe51d0cSJohn Levon 	set_dynamic_states(link_id);
26251f5207b7SJohn Levon 	add_merge_hook(link_id, &merge_links);
26261f5207b7SJohn Levon 	add_modification_hook(link_id, &match_modify);
26271f5207b7SJohn Levon 	add_modification_hook_late(link_id, match_inc_dec);
26281f5207b7SJohn Levon 
26291f5207b7SJohn Levon 	add_member_info_callback(link_id, struct_member_callback);
26301f5207b7SJohn Levon }
26311f5207b7SJohn Levon 
register_comparison_inc_dec(int id)26321f5207b7SJohn Levon void register_comparison_inc_dec(int id)
26331f5207b7SJohn Levon {
26341f5207b7SJohn Levon 	inc_dec_id = id;
26351f5207b7SJohn Levon 	add_modification_hook_late(inc_dec_id, &iter_modify);
26361f5207b7SJohn Levon }
26371f5207b7SJohn Levon 
register_comparison_inc_dec_links(int id)26381f5207b7SJohn Levon void register_comparison_inc_dec_links(int id)
26391f5207b7SJohn Levon {
26401f5207b7SJohn Levon 	inc_dec_link_id = id;
2641efe51d0cSJohn Levon 	set_dynamic_states(inc_dec_link_id);
26421f5207b7SJohn Levon 	set_up_link_functions(inc_dec_id, inc_dec_link_id);
26431f5207b7SJohn Levon }
26441f5207b7SJohn Levon 
clone_partial_sm(struct sm_state * sm,int comparison)26455a0e240fSJohn Levon static struct sm_state *clone_partial_sm(struct sm_state *sm, int comparison)
26465a0e240fSJohn Levon {
26475a0e240fSJohn Levon 	struct compare_data *data;
26485a0e240fSJohn Levon 	struct sm_state *clone;
26495a0e240fSJohn Levon 	struct stree *stree;
26505a0e240fSJohn Levon 
26515a0e240fSJohn Levon 	data = sm->state->data;
26525a0e240fSJohn Levon 
26535a0e240fSJohn Levon 	clone = clone_sm(sm);
26545a0e240fSJohn Levon 	clone->state = alloc_compare_state(data->left, data->left_var, data->left_vsl,
26555a0e240fSJohn Levon 					   comparison,
26565a0e240fSJohn Levon 					   data->right, data->right_var, data->right_vsl);
26575a0e240fSJohn Levon 	free_slist(&clone->possible);
26585a0e240fSJohn Levon 	add_possible_sm(clone, clone);
26595a0e240fSJohn Levon 
26605a0e240fSJohn Levon 	stree = clone_stree(sm->pool);
26615a0e240fSJohn Levon 	overwrite_sm_state_stree(&stree, clone);
26625a0e240fSJohn Levon 	clone->pool = stree;
26635a0e240fSJohn Levon 
26645a0e240fSJohn Levon 	return clone;
26655a0e240fSJohn Levon }
26665a0e240fSJohn Levon 
create_fake_history(struct sm_state * sm,int op,struct state_list ** true_stack,struct state_list ** false_stack)26675a0e240fSJohn Levon static void create_fake_history(struct sm_state *sm, int op,
26685a0e240fSJohn Levon 			       struct state_list **true_stack,
26695a0e240fSJohn Levon 			       struct state_list **false_stack)
26705a0e240fSJohn Levon {
26715a0e240fSJohn Levon 	struct sm_state *true_sm, *false_sm;
26725a0e240fSJohn Levon 	struct compare_data *data;
26735a0e240fSJohn Levon 	int true_comparison;
26745a0e240fSJohn Levon 	int false_comparison;
26755a0e240fSJohn Levon 
26765a0e240fSJohn Levon 	data = sm->state->data;
26775a0e240fSJohn Levon 
26785a0e240fSJohn Levon 	if (is_merged(sm) || sm->left || sm->right)
26795a0e240fSJohn Levon 		return;
26805a0e240fSJohn Levon 
26815a0e240fSJohn Levon 	true_comparison = comparison_intersection(data->comparison, op);
26825a0e240fSJohn Levon 	false_comparison = comparison_intersection(data->comparison, negate_comparison(op));
26835a0e240fSJohn Levon 
26845a0e240fSJohn Levon 	true_sm = clone_partial_sm(sm, true_comparison);
26855a0e240fSJohn Levon 	false_sm = clone_partial_sm(sm, false_comparison);
26865a0e240fSJohn Levon 
26875a0e240fSJohn Levon 	sm->merged = 1;
26885a0e240fSJohn Levon 	sm->left = true_sm;
26895a0e240fSJohn Levon 	sm->right = false_sm;
26905a0e240fSJohn Levon 
26915a0e240fSJohn Levon 	add_ptr_list(true_stack, true_sm);
26925a0e240fSJohn Levon 	add_ptr_list(false_stack, false_sm);
26935a0e240fSJohn Levon }
26945a0e240fSJohn Levon 
filter_by_sm(struct sm_state * sm,int op,struct state_list ** true_stack,struct state_list ** false_stack,bool * useful)26951f5207b7SJohn Levon static void filter_by_sm(struct sm_state *sm, int op,
26961f5207b7SJohn Levon 		       struct state_list **true_stack,
26975a0e240fSJohn Levon 		       struct state_list **false_stack,
26985a0e240fSJohn Levon 		       bool *useful)
26991f5207b7SJohn Levon {
27001f5207b7SJohn Levon 	struct compare_data *data;
2701c85f09ccSJohn Levon 	int is_true = 0;
2702c85f09ccSJohn Levon 	int is_false = 0;
27031f5207b7SJohn Levon 
27041f5207b7SJohn Levon 	if (!sm)
27051f5207b7SJohn Levon 		return;
27061f5207b7SJohn Levon 	data = sm->state->data;
27075a0e240fSJohn Levon 	if (!data)
2708c85f09ccSJohn Levon 		goto split;
2709c85f09ccSJohn Levon 	if (data->comparison == IMPOSSIBLE_COMPARISON)
27101f5207b7SJohn Levon 		return;
27111f5207b7SJohn Levon 
2712c85f09ccSJohn Levon 	/*
2713c85f09ccSJohn Levon 	 * We want to check that "data->comparison" is totally inside "op".  So
2714c85f09ccSJohn Levon 	 * if data->comparison is < and op is <= then that's true.  Or if
2715c85f09ccSJohn Levon 	 * data->comparison is == and op is <= then that's true.  But if
2716c85f09ccSJohn Levon 	 * data->comparison is <= and op is < than that's neither true nor
2717c85f09ccSJohn Levon 	 * false.
2718c85f09ccSJohn Levon 	 */
2719c85f09ccSJohn Levon 	if (data->comparison == comparison_intersection(data->comparison, op))
2720c85f09ccSJohn Levon 		is_true = 1;
2721c85f09ccSJohn Levon 	if (data->comparison == comparison_intersection(data->comparison, negate_comparison(op)))
2722c85f09ccSJohn Levon 		is_false = 1;
2723c85f09ccSJohn Levon 
27245a0e240fSJohn Levon 	if (!is_true && !is_false && !is_merged(sm)) {
27255a0e240fSJohn Levon 		create_fake_history(sm, op, true_stack, false_stack);
27265a0e240fSJohn Levon 		return;
27275a0e240fSJohn Levon 	}
27285a0e240fSJohn Levon 
2729c85f09ccSJohn Levon 	if (debug_implied()) {
2730c85f09ccSJohn Levon 		sm_msg("%s: %s: op = '%s' negated '%s'. true_intersect = '%s' false_insersect = '%s' sm = '%s'",
2731c85f09ccSJohn Levon 		       __func__,
2732c85f09ccSJohn Levon 		       sm->state->name,
2733c85f09ccSJohn Levon 		       alloc_sname(show_comparison(op)),
2734c85f09ccSJohn Levon 		       alloc_sname(show_comparison(negate_comparison(op))),
2735c85f09ccSJohn Levon 		       alloc_sname(show_comparison(comparison_intersection(data->comparison, op))),
2736c85f09ccSJohn Levon 		       alloc_sname(show_comparison(comparison_intersection(data->comparison, negate_comparison(op)))),
2737c85f09ccSJohn Levon 		       show_sm(sm));
2738c85f09ccSJohn Levon 	}
27391f5207b7SJohn Levon 
27405a0e240fSJohn Levon 	*useful = true;
2741c85f09ccSJohn Levon 	if (is_true)
27421f5207b7SJohn Levon 		add_ptr_list(true_stack, sm);
2743c85f09ccSJohn Levon 	if (is_false)
27441f5207b7SJohn Levon 		add_ptr_list(false_stack, sm);
2745c85f09ccSJohn Levon split:
27465a0e240fSJohn Levon 	filter_by_sm(sm->left, op, true_stack, false_stack, useful);
27475a0e240fSJohn Levon 	filter_by_sm(sm->right, op, true_stack, false_stack, useful);
27481f5207b7SJohn Levon }
27491f5207b7SJohn Levon 
comparison_implication_hook(struct expression * expr,struct state_list ** true_stack,struct state_list ** false_stack)27501f5207b7SJohn Levon struct sm_state *comparison_implication_hook(struct expression *expr,
2751*6523a3aaSJohn Levon 					     struct state_list **true_stack,
2752*6523a3aaSJohn Levon 					     struct state_list **false_stack)
27531f5207b7SJohn Levon {
27541f5207b7SJohn Levon 	struct sm_state *sm;
27551f5207b7SJohn Levon 	char *left, *right;
27561f5207b7SJohn Levon 	int op;
27571f5207b7SJohn Levon 	static char buf[256];
27585a0e240fSJohn Levon 	bool useful = false;
27591f5207b7SJohn Levon 
27601f5207b7SJohn Levon 	if (expr->type != EXPR_COMPARE)
27611f5207b7SJohn Levon 		return NULL;
27621f5207b7SJohn Levon 
27631f5207b7SJohn Levon 	op = expr->op;
27641f5207b7SJohn Levon 
27651f5207b7SJohn Levon 	left = expr_to_var(expr->left);
27661f5207b7SJohn Levon 	right = expr_to_var(expr->right);
27671f5207b7SJohn Levon 	if (!left || !right) {
27681f5207b7SJohn Levon 		free_string(left);
27691f5207b7SJohn Levon 		free_string(right);
27701f5207b7SJohn Levon 		return NULL;
27711f5207b7SJohn Levon 	}
27721f5207b7SJohn Levon 
27731f5207b7SJohn Levon 	if (strcmp(left, right) > 0) {
27741f5207b7SJohn Levon 		char *tmp = left;
27751f5207b7SJohn Levon 
27761f5207b7SJohn Levon 		left = right;
27771f5207b7SJohn Levon 		right = tmp;
27781f5207b7SJohn Levon 		op = flip_comparison(op);
27791f5207b7SJohn Levon 	}
27801f5207b7SJohn Levon 
27811f5207b7SJohn Levon 	snprintf(buf, sizeof(buf), "%s vs %s", left, right);
27825a0e240fSJohn Levon 	sm = get_sm_state(comparison_id, buf, NULL);
27831f5207b7SJohn Levon 	if (!sm)
27841f5207b7SJohn Levon 		return NULL;
27851f5207b7SJohn Levon 	if (!sm->merged)
27861f5207b7SJohn Levon 		return NULL;
27871f5207b7SJohn Levon 
27885a0e240fSJohn Levon 	filter_by_sm(sm, op, true_stack, false_stack, &useful);
27895a0e240fSJohn Levon 	if (!useful)
27901f5207b7SJohn Levon 		return NULL;
27911f5207b7SJohn Levon 
2792c85f09ccSJohn Levon 	if (debug_implied())
27931f5207b7SJohn Levon 		sm_msg("implications from comparison: (%s)", show_sm(sm));
27941f5207b7SJohn Levon 
27951f5207b7SJohn Levon 	return sm;
27961f5207b7SJohn Levon }
2797