xref: /illumos-gate/usr/src/tools/smatch/src/smatch_comparison.c (revision 6523a3aa7f325d64841382707603be7a86e68147)
1 /*
2  * Copyright (C) 2012 Oracle.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16  */
17 
18 /*
19  * The point here is to store the relationships between two variables.
20  * Ie:  y > x.
21  * To do that we create a state with the two variables in alphabetical order:
22  * ->name = "x vs y" and the state would be "<".  On the false path the state
23  * would be ">=".
24  *
25  * Part of the trick of it is that if x or y is modified then we need to reset
26  * the state.  We need to keep a list of all the states which depend on x and
27  * all the states which depend on y.  The link_id code handles this.
28  *
29  */
30 
31 #include "smatch.h"
32 #include "smatch_extra.h"
33 #include "smatch_slist.h"
34 
35 int comparison_id;
36 static int link_id;
37 static int inc_dec_id;
38 static int inc_dec_link_id;
39 
40 static void add_comparison(struct expression *left, int comparison, struct expression *right);
41 
42 /* for handling for loops */
43 STATE(start);
44 STATE(incremented);
45 
46 ALLOCATOR(compare_data, "compare data");
47 
vsl_to_sym(struct var_sym_list * vsl)48 static struct symbol *vsl_to_sym(struct var_sym_list *vsl)
49 {
50 	struct var_sym *vs;
51 
52 	if (!vsl)
53 		return NULL;
54 	if (ptr_list_size((struct ptr_list *)vsl) != 1)
55 		return NULL;
56 	vs = first_ptr_list((struct ptr_list *)vsl);
57 	return vs->sym;
58 }
59 
show_comparison(int comparison)60 static const char *show_comparison(int comparison)
61 {
62 	if (comparison == IMPOSSIBLE_COMPARISON)
63 		return "impossible";
64 	if (comparison == UNKNOWN_COMPARISON)
65 		return "unknown";
66 	return show_special(comparison);
67 }
68 
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)69 struct smatch_state *alloc_compare_state(
70 		struct expression *left,
71 		const char *left_var, struct var_sym_list *left_vsl,
72 		int comparison,
73 		struct expression *right,
74 		const char *right_var, struct var_sym_list *right_vsl)
75 {
76 	struct smatch_state *state;
77 	struct compare_data *data;
78 
79 	state = __alloc_smatch_state(0);
80 	state->name = alloc_sname(show_comparison(comparison));
81 	data = __alloc_compare_data(0);
82 	data->left = left;
83 	data->left_var = alloc_sname(left_var);
84 	data->left_vsl = clone_var_sym_list(left_vsl);
85 	data->comparison = comparison;
86 	data->right = right;
87 	data->right_var = alloc_sname(right_var);
88 	data->right_vsl = clone_var_sym_list(right_vsl);
89 	state->data = data;
90 	return state;
91 }
92 
state_to_comparison(struct smatch_state * state)93 int state_to_comparison(struct smatch_state *state)
94 {
95 	if (!state || !state->data)
96 		return UNKNOWN_COMPARISON;
97 	return ((struct compare_data *)state->data)->comparison;
98 }
99 
100 /*
101  * flip_comparison() reverses the op left and right.  So "x >= y" becomes "y <= x".
102  */
flip_comparison(int op)103 int flip_comparison(int op)
104 {
105 	switch (op) {
106 	case UNKNOWN_COMPARISON:
107 		return UNKNOWN_COMPARISON;
108 	case '<':
109 		return '>';
110 	case SPECIAL_UNSIGNED_LT:
111 		return SPECIAL_UNSIGNED_GT;
112 	case SPECIAL_LTE:
113 		return SPECIAL_GTE;
114 	case SPECIAL_UNSIGNED_LTE:
115 		return SPECIAL_UNSIGNED_GTE;
116 	case SPECIAL_EQUAL:
117 		return SPECIAL_EQUAL;
118 	case SPECIAL_NOTEQUAL:
119 		return SPECIAL_NOTEQUAL;
120 	case SPECIAL_GTE:
121 		return SPECIAL_LTE;
122 	case SPECIAL_UNSIGNED_GTE:
123 		return SPECIAL_UNSIGNED_LTE;
124 	case '>':
125 		return '<';
126 	case SPECIAL_UNSIGNED_GT:
127 		return SPECIAL_UNSIGNED_LT;
128 	case IMPOSSIBLE_COMPARISON:
129 		return UNKNOWN_COMPARISON;
130 	default:
131 		sm_perror("unhandled comparison %d", op);
132 		return op;
133 	}
134 }
135 
negate_comparison(int op)136 int negate_comparison(int op)
137 {
138 	switch (op) {
139 	case UNKNOWN_COMPARISON:
140 		return UNKNOWN_COMPARISON;
141 	case '<':
142 		return SPECIAL_GTE;
143 	case SPECIAL_UNSIGNED_LT:
144 		return SPECIAL_UNSIGNED_GTE;
145 	case SPECIAL_LTE:
146 		return '>';
147 	case SPECIAL_UNSIGNED_LTE:
148 		return SPECIAL_UNSIGNED_GT;
149 	case SPECIAL_EQUAL:
150 		return SPECIAL_NOTEQUAL;
151 	case SPECIAL_NOTEQUAL:
152 		return SPECIAL_EQUAL;
153 	case SPECIAL_GTE:
154 		return '<';
155 	case SPECIAL_UNSIGNED_GTE:
156 		return SPECIAL_UNSIGNED_LT;
157 	case '>':
158 		return SPECIAL_LTE;
159 	case SPECIAL_UNSIGNED_GT:
160 		return SPECIAL_UNSIGNED_LTE;
161 	case IMPOSSIBLE_COMPARISON:
162 		return UNKNOWN_COMPARISON;
163 	default:
164 		sm_perror("unhandled comparison %d", op);
165 		return op;
166 	}
167 }
168 
rl_comparison(struct range_list * left_rl,struct range_list * right_rl)169 static int rl_comparison(struct range_list *left_rl, struct range_list *right_rl)
170 {
171 	sval_t left_min, left_max, right_min, right_max;
172 	struct symbol *type = &int_ctype;
173 
174 	if (!left_rl || !right_rl)
175 		return UNKNOWN_COMPARISON;
176 
177 	if (type_positive_bits(rl_type(left_rl)) > type_positive_bits(type))
178 		type = rl_type(left_rl);
179 	if (type_positive_bits(rl_type(right_rl)) > type_positive_bits(type))
180 		type = rl_type(right_rl);
181 
182 	left_rl = cast_rl(type, left_rl);
183 	right_rl = cast_rl(type, right_rl);
184 
185 	left_min = rl_min(left_rl);
186 	left_max = rl_max(left_rl);
187 	right_min = rl_min(right_rl);
188 	right_max = rl_max(right_rl);
189 
190 	if (left_min.value == left_max.value &&
191 	    right_min.value == right_max.value &&
192 	    left_min.value == right_min.value)
193 		return SPECIAL_EQUAL;
194 
195 	if (sval_cmp(left_max, right_min) < 0)
196 		return '<';
197 	if (sval_cmp(left_max, right_min) == 0)
198 		return SPECIAL_LTE;
199 	if (sval_cmp(left_min, right_max) > 0)
200 		return '>';
201 	if (sval_cmp(left_min, right_max) == 0)
202 		return SPECIAL_GTE;
203 
204 	return UNKNOWN_COMPARISON;
205 }
206 
comparison_from_extra(struct expression * a,struct expression * b)207 static int comparison_from_extra(struct expression *a, struct expression *b)
208 {
209 	struct range_list *left, *right;
210 
211 	if (!get_implied_rl(a, &left))
212 		return UNKNOWN_COMPARISON;
213 	if (!get_implied_rl(b, &right))
214 		return UNKNOWN_COMPARISON;
215 
216 	return rl_comparison(left, right);
217 }
218 
get_orig_rl(struct var_sym_list * vsl)219 static struct range_list *get_orig_rl(struct var_sym_list *vsl)
220 {
221 	struct symbol *sym;
222 	struct smatch_state *state;
223 
224 	if (!vsl)
225 		return NULL;
226 	sym = vsl_to_sym(vsl);
227 	if (!sym || !sym->ident)
228 		return NULL;
229 	state = get_orig_estate(sym->ident->name, sym);
230 	return estate_rl(state);
231 }
232 
unmatched_comparison(struct sm_state * sm)233 static struct smatch_state *unmatched_comparison(struct sm_state *sm)
234 {
235 	struct compare_data *data = sm->state->data;
236 	struct range_list *left_rl, *right_rl;
237 	int op = UNKNOWN_COMPARISON;
238 
239 	if (!data)
240 		return &undefined;
241 
242 	if (is_impossible_path()) {
243 		op = IMPOSSIBLE_COMPARISON;
244 		goto alloc;
245 	}
246 
247 	if (strstr(data->left_var, " orig"))
248 		left_rl = get_orig_rl(data->left_vsl);
249 	else if (!get_implied_rl_var_sym(data->left_var, vsl_to_sym(data->left_vsl), &left_rl))
250 		goto alloc;
251 
252 	if (strstr(data->right_var, " orig"))
253 		right_rl = get_orig_rl(data->right_vsl);
254 	else if (!get_implied_rl_var_sym(data->right_var, vsl_to_sym(data->right_vsl), &right_rl))
255 		goto alloc;
256 
257 	op = rl_comparison(left_rl, right_rl);
258 
259 alloc:
260 	return alloc_compare_state(data->left, data->left_var, data->left_vsl,
261 				   op,
262 				   data->right, data->right_var, data->right_vsl);
263 }
264 
265 /* remove_unsigned_from_comparison() is obviously a hack. */
remove_unsigned_from_comparison(int op)266 int remove_unsigned_from_comparison(int op)
267 {
268 	switch (op) {
269 	case SPECIAL_UNSIGNED_LT:
270 		return '<';
271 	case SPECIAL_UNSIGNED_LTE:
272 		return SPECIAL_LTE;
273 	case SPECIAL_UNSIGNED_GTE:
274 		return SPECIAL_GTE;
275 	case SPECIAL_UNSIGNED_GT:
276 		return '>';
277 	default:
278 		return op;
279 	}
280 }
281 
282 /*
283  * This is for when you merge states "a < b" and "a == b", the result is that
284  * we can say for sure, "a <= b" after the merge.
285  */
merge_comparisons(int one,int two)286 int merge_comparisons(int one, int two)
287 {
288 	int LT, EQ, GT;
289 
290 	if (one == UNKNOWN_COMPARISON || two == UNKNOWN_COMPARISON)
291 		return UNKNOWN_COMPARISON;
292 
293 	if (one == IMPOSSIBLE_COMPARISON)
294 		return two;
295 	if (two == IMPOSSIBLE_COMPARISON)
296 		return one;
297 
298 	one = remove_unsigned_from_comparison(one);
299 	two = remove_unsigned_from_comparison(two);
300 
301 	if (one == two)
302 		return one;
303 
304 	LT = EQ = GT = 0;
305 
306 	switch (one) {
307 	case '<':
308 		LT = 1;
309 		break;
310 	case SPECIAL_LTE:
311 		LT = 1;
312 		EQ = 1;
313 		break;
314 	case SPECIAL_EQUAL:
315 		EQ = 1;
316 		break;
317 	case SPECIAL_GTE:
318 		GT = 1;
319 		EQ = 1;
320 		break;
321 	case '>':
322 		GT = 1;
323 	}
324 
325 	switch (two) {
326 	case '<':
327 		LT = 1;
328 		break;
329 	case SPECIAL_LTE:
330 		LT = 1;
331 		EQ = 1;
332 		break;
333 	case SPECIAL_EQUAL:
334 		EQ = 1;
335 		break;
336 	case SPECIAL_GTE:
337 		GT = 1;
338 		EQ = 1;
339 		break;
340 	case '>':
341 		GT = 1;
342 	}
343 
344 	if (LT && EQ && GT)
345 		return UNKNOWN_COMPARISON;
346 	if (LT && EQ)
347 		return SPECIAL_LTE;
348 	if (LT && GT)
349 		return SPECIAL_NOTEQUAL;
350 	if (LT)
351 		return '<';
352 	if (EQ && GT)
353 		return SPECIAL_GTE;
354 	if (GT)
355 		return '>';
356 	return UNKNOWN_COMPARISON;
357 }
358 
359 /*
360  * This is for if you have "a < b" and "b <= c" and you want to see how "a
361  * compares to c".  You would call this like get_combined_comparison('<', '<=').
362  * The return comparison would be '<'.
363  */
combine_comparisons(int left_compare,int right_compare)364 int combine_comparisons(int left_compare, int right_compare)
365 {
366 	int LT, EQ, GT;
367 
368 	left_compare = remove_unsigned_from_comparison(left_compare);
369 	right_compare = remove_unsigned_from_comparison(right_compare);
370 
371 	LT = EQ = GT = 0;
372 
373 	switch (left_compare) {
374 	case '<':
375 		LT++;
376 		break;
377 	case SPECIAL_LTE:
378 		LT++;
379 		EQ++;
380 		break;
381 	case SPECIAL_EQUAL:
382 		return right_compare;
383 	case SPECIAL_GTE:
384 		GT++;
385 		EQ++;
386 		break;
387 	case '>':
388 		GT++;
389 	}
390 
391 	switch (right_compare) {
392 	case '<':
393 		LT++;
394 		break;
395 	case SPECIAL_LTE:
396 		LT++;
397 		EQ++;
398 		break;
399 	case SPECIAL_EQUAL:
400 		return left_compare;
401 	case SPECIAL_GTE:
402 		GT++;
403 		EQ++;
404 		break;
405 	case '>':
406 		GT++;
407 	}
408 
409 	if (LT == 2) {
410 		if (EQ == 2)
411 			return SPECIAL_LTE;
412 		return '<';
413 	}
414 
415 	if (GT == 2) {
416 		if (EQ == 2)
417 			return SPECIAL_GTE;
418 		return '>';
419 	}
420 	return UNKNOWN_COMPARISON;
421 }
422 
423 /*
424  * This is mostly used when you know from extra state that a <= b but you
425  * know from comparisons that a != b so then if take the intersection then
426  * we know that a < b.  The name is taken from the fact that the intersection
427  * of < and <= is <.
428  */
comparison_intersection(int left_compare,int right_compare)429 int comparison_intersection(int left_compare, int right_compare)
430 {
431 	int LT, GT, EQ, NE, total;
432 
433 	if (left_compare == IMPOSSIBLE_COMPARISON ||
434 	    right_compare == IMPOSSIBLE_COMPARISON)
435 		return IMPOSSIBLE_COMPARISON;
436 
437 	left_compare = remove_unsigned_from_comparison(left_compare);
438 	right_compare = remove_unsigned_from_comparison(right_compare);
439 
440 	LT = GT = EQ = NE = total = 0;
441 
442 	/* Only one side is known. */
443 	if (!left_compare)
444 		return right_compare;
445 	if (!right_compare)
446 		return left_compare;
447 
448 	switch (left_compare) {
449 	case '<':
450 		LT++;
451 		total += 1;
452 		break;
453 	case SPECIAL_LTE:
454 		LT++;
455 		EQ++;
456 		total += 2;
457 		break;
458 	case SPECIAL_EQUAL:
459 		EQ++;
460 		total += 1;
461 		break;
462 	case SPECIAL_NOTEQUAL:
463 		NE++;
464 		total += 1;
465 		break;
466 	case SPECIAL_GTE:
467 		GT++;
468 		EQ++;
469 		total += 2;
470 		break;
471 	case '>':
472 		GT++;
473 		total += 1;
474 		break;
475 	default:
476 		return UNKNOWN_COMPARISON;
477 	}
478 
479 	switch (right_compare) {
480 	case '<':
481 		LT++;
482 		total += 1;
483 		break;
484 	case SPECIAL_LTE:
485 		LT++;
486 		EQ++;
487 		total += 2;
488 		break;
489 	case SPECIAL_EQUAL:
490 		EQ++;
491 		total += 1;
492 		break;
493 	case SPECIAL_NOTEQUAL:
494 		NE++;
495 		total += 1;
496 		break;
497 	case SPECIAL_GTE:
498 		GT++;
499 		EQ++;
500 		total += 2;
501 		break;
502 	case '>':
503 		GT++;
504 		total += 1;
505 		break;
506 	default:
507 		return UNKNOWN_COMPARISON;
508 	}
509 
510 	if (LT == 2) {
511 		if (EQ == 2)
512 			return SPECIAL_LTE;
513 		return '<';
514 	}
515 
516 	if (GT == 2) {
517 		if (EQ == 2)
518 			return SPECIAL_GTE;
519 		return '>';
520 	}
521 	if (EQ == 2)
522 		return SPECIAL_EQUAL;
523 	if (total == 2 && EQ && NE)
524 		return IMPOSSIBLE_COMPARISON;
525 	if (GT && LT)
526 		return IMPOSSIBLE_COMPARISON;
527 	if (GT && NE)
528 		return '>';
529 	if (LT && NE)
530 		return '<';
531 	if (NE == 2)
532 		return SPECIAL_NOTEQUAL;
533 	if (total == 2 && (LT || GT) && EQ)
534 		return IMPOSSIBLE_COMPARISON;
535 
536 	return UNKNOWN_COMPARISON;
537 }
538 
pre_merge_hook(struct sm_state * cur,struct sm_state * other)539 static void pre_merge_hook(struct sm_state *cur, struct sm_state *other)
540 {
541 	struct compare_data *data = cur->state->data;
542 	int extra, new;
543 	static bool in_recurse;
544 
545 	// FIXME.  No data is useless
546 	if (!data)
547 		return;
548 
549 	if (in_recurse)
550 		return;
551 	in_recurse = true;
552 	extra = comparison_from_extra(data->left, data->right);
553 	in_recurse = false;
554 	if (!extra)
555 		return;
556 	new = comparison_intersection(extra, data->comparison);
557 	if (new == data->comparison)
558 		return;
559 
560 	// FIXME: we should always preserve implications
561 	set_state(comparison_id, cur->name, NULL,
562 		  alloc_compare_state(data->left, data->left_var, data->left_vsl,
563 				      new,
564 				      data->right, data->right_var, data->right_vsl));
565 }
566 
merge_compare_states(struct smatch_state * s1,struct smatch_state * s2)567 struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2)
568 {
569 	struct compare_data *data = s1->data;
570 	int op;
571 
572 	if (!data)
573 		return &undefined;
574 
575 	op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2));
576 	return alloc_compare_state(
577 			data->left, data->left_var, data->left_vsl,
578 			op,
579 			data->right, data->right_var, data->right_vsl);
580 }
581 
alloc_link_state(struct string_list * links)582 static struct smatch_state *alloc_link_state(struct string_list *links)
583 {
584 	struct smatch_state *state;
585 	static char buf[256];
586 	char *tmp;
587 	int i;
588 
589 	state = __alloc_smatch_state(0);
590 
591 	i = 0;
592 	FOR_EACH_PTR(links, tmp) {
593 		if (!i++) {
594 			snprintf(buf, sizeof(buf), "%s", tmp);
595 		} else {
596 			append(buf, ", ", sizeof(buf));
597 			append(buf, tmp, sizeof(buf));
598 		}
599 	} END_FOR_EACH_PTR(tmp);
600 
601 	state->name = alloc_sname(buf);
602 	state->data = links;
603 	return state;
604 }
605 
save_start_states(struct statement * stmt)606 static void save_start_states(struct statement *stmt)
607 {
608 	struct symbol *param;
609 	char orig[64];
610 	char state_name[128];
611 	struct smatch_state *state;
612 	struct string_list *links;
613 	char *link;
614 
615 	FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
616 		struct var_sym_list *left_vsl = NULL;
617 		struct var_sym_list *right_vsl = NULL;
618 
619 		if (!param->ident)
620 			continue;
621 		snprintf(orig, sizeof(orig), "%s orig", param->ident->name);
622 		snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig);
623 		add_var_sym(&left_vsl, param->ident->name, param);
624 		add_var_sym(&right_vsl, orig, param);
625 		state = alloc_compare_state(
626 				NULL, param->ident->name, left_vsl,
627 				SPECIAL_EQUAL,
628 				NULL, alloc_sname(orig), right_vsl);
629 		set_state(comparison_id, state_name, NULL, state);
630 
631 		link = alloc_sname(state_name);
632 		links = NULL;
633 		insert_string(&links, link);
634 		state = alloc_link_state(links);
635 		set_state(link_id, param->ident->name, param, state);
636 	} END_FOR_EACH_PTR(param);
637 }
638 
merge_links(struct smatch_state * s1,struct smatch_state * s2)639 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
640 {
641 	struct smatch_state *ret;
642 	struct string_list *links;
643 
644 	links = combine_string_lists(s1->data, s2->data);
645 	ret = alloc_link_state(links);
646 	return ret;
647 }
648 
save_link_var_sym(const char * var,struct symbol * sym,const char * link)649 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
650 {
651 	struct smatch_state *old_state, *new_state;
652 	struct string_list *links;
653 	char *new;
654 
655 	old_state = get_state(link_id, var, sym);
656 	if (old_state)
657 		links = clone_str_list(old_state->data);
658 	else
659 		links = NULL;
660 
661 	new = alloc_sname(link);
662 	insert_string(&links, new);
663 
664 	new_state = alloc_link_state(links);
665 	set_state(link_id, var, sym, new_state);
666 }
667 
match_inc(struct sm_state * sm,bool preserve)668 static void match_inc(struct sm_state *sm, bool preserve)
669 {
670 	struct string_list *links;
671 	struct smatch_state *state, *new;
672 	struct compare_data *data;
673 	char *tmp;
674 	int flip;
675 	int op;
676 
677 	links = sm->state->data;
678 
679 	FOR_EACH_PTR(links, tmp) {
680 		state = get_state(comparison_id, tmp, NULL);
681 		if (!state)
682 			continue;
683 		data = state->data;
684 		if (!data)
685 			continue;
686 
687 		flip = 0;
688 		if (strncmp(sm->name, tmp, strlen(sm->name)) != 0 ||
689 		    tmp[strlen(sm->name)] != ' ')
690 			flip = 1;
691 
692 		op = state_to_comparison(state);
693 
694 		switch (flip ? flip_comparison(op) : op) {
695 		case SPECIAL_EQUAL:
696 		case SPECIAL_GTE:
697 		case SPECIAL_UNSIGNED_GTE:
698 		case '>':
699 		case SPECIAL_UNSIGNED_GT:
700 			if (preserve)
701 				break;
702 			new = alloc_compare_state(
703 					data->left, data->left_var, data->left_vsl,
704 					flip ? '<' : '>',
705 					data->right, data->right_var, data->right_vsl);
706 			set_state(comparison_id, tmp, NULL, new);
707 			break;
708 		case '<':
709 		case SPECIAL_UNSIGNED_LT:
710 			new = alloc_compare_state(
711 					data->left, data->left_var, data->left_vsl,
712 					flip ? SPECIAL_GTE : SPECIAL_LTE,
713 					data->right, data->right_var, data->right_vsl);
714 			set_state(comparison_id, tmp, NULL, new);
715 			break;
716 		default:
717 			new = alloc_compare_state(
718 					data->left, data->left_var, data->left_vsl,
719 					UNKNOWN_COMPARISON,
720 					data->right, data->right_var, data->right_vsl);
721 			set_state(comparison_id, tmp, NULL, new);
722 		}
723 	} END_FOR_EACH_PTR(tmp);
724 }
725 
match_dec(struct sm_state * sm,bool preserve)726 static void match_dec(struct sm_state *sm, bool preserve)
727 {
728 	struct string_list *links;
729 	struct smatch_state *state;
730 	char *tmp;
731 
732 	links = sm->state->data;
733 
734 	FOR_EACH_PTR(links, tmp) {
735 		struct compare_data *data;
736 		struct smatch_state *new;
737 
738 		state = get_state(comparison_id, tmp, NULL);
739 		if (!state || !state->data)
740 			continue;
741 
742 		data = state->data;
743 
744 		switch (state_to_comparison(state)) {
745 		case SPECIAL_EQUAL:
746 		case SPECIAL_LTE:
747 		case SPECIAL_UNSIGNED_LTE:
748 		case '<':
749 		case SPECIAL_UNSIGNED_LT: {
750 			if (preserve)
751 				break;
752 
753 			new = alloc_compare_state(
754 					data->left, data->left_var, data->left_vsl,
755 					'<',
756 					data->right, data->right_var, data->right_vsl);
757 			set_state(comparison_id, tmp, NULL, new);
758 			break;
759 			}
760 		default:
761 			new = alloc_compare_state(
762 					data->left, data->left_var, data->left_vsl,
763 					UNKNOWN_COMPARISON,
764 					data->right, data->right_var, data->right_vsl);
765 			set_state(comparison_id, tmp, NULL, new);
766 		}
767 	} END_FOR_EACH_PTR(tmp);
768 }
769 
reset_sm(struct sm_state * sm)770 static void reset_sm(struct sm_state *sm)
771 {
772 	struct string_list *links;
773 	char *tmp;
774 
775 	links = sm->state->data;
776 
777 	FOR_EACH_PTR(links, tmp) {
778 		struct smatch_state *old, *new;
779 
780 		old = get_state(comparison_id, tmp, NULL);
781 		if (!old || !old->data) {
782 			new = &undefined;
783 		} else {
784 			struct compare_data *data = old->data;
785 
786 			new = alloc_compare_state(
787 					data->left, data->left_var, data->left_vsl,
788 					UNKNOWN_COMPARISON,
789 					data->right, data->right_var, data->right_vsl);
790 		}
791 		set_state(comparison_id, tmp, NULL, new);
792 	} END_FOR_EACH_PTR(tmp);
793 	set_state(link_id, sm->name, sm->sym, &undefined);
794 }
795 
match_add_sub_assign(struct sm_state * sm,struct expression * expr)796 static bool match_add_sub_assign(struct sm_state *sm, struct expression *expr)
797 {
798 	struct range_list *rl;
799 	sval_t zero = { .type = &int_ctype };
800 
801 	if (!expr || expr->type != EXPR_ASSIGNMENT)
802 		return false;
803 	if (expr->op != SPECIAL_ADD_ASSIGN && expr->op != SPECIAL_SUB_ASSIGN)
804 		return false;
805 
806 	get_absolute_rl(expr->right, &rl);
807 	if (sval_is_negative(rl_min(rl))) {
808 		reset_sm(sm);
809 		return false;
810 	}
811 
812 	if (expr->op == SPECIAL_ADD_ASSIGN)
813 		match_inc(sm, rl_has_sval(rl, zero));
814 	else
815 		match_dec(sm, rl_has_sval(rl, zero));
816 	return true;
817 }
818 
match_inc_dec(struct sm_state * sm,struct expression * mod_expr)819 static void match_inc_dec(struct sm_state *sm, struct expression *mod_expr)
820 {
821 	/*
822 	 * if (foo > bar) then ++foo is also > bar.
823 	 */
824 	if (!mod_expr)
825 		return;
826 	if (match_add_sub_assign(sm, mod_expr))
827 		return;
828 	if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP)
829 		return;
830 
831 	if (mod_expr->op == SPECIAL_INCREMENT)
832 		match_inc(sm, false);
833 	else if (mod_expr->op == SPECIAL_DECREMENT)
834 		match_dec(sm, false);
835 }
836 
is_self_assign(struct expression * expr)837 static int is_self_assign(struct expression *expr)
838 {
839 	if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=')
840 		return 0;
841 	return expr_equiv(expr->left, expr->right);
842 }
843 
match_modify(struct sm_state * sm,struct expression * mod_expr)844 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
845 {
846 	if (mod_expr && is_self_assign(mod_expr))
847 		return;
848 
849 	/* handled by match_inc_dec() */
850 	if (mod_expr &&
851 	    ((mod_expr->type == EXPR_PREOP || mod_expr->type == EXPR_POSTOP) &&
852 	     (mod_expr->op == SPECIAL_INCREMENT || mod_expr->op == SPECIAL_DECREMENT)))
853 		return;
854 	if (mod_expr && mod_expr->type == EXPR_ASSIGNMENT &&
855 	    (mod_expr->op == SPECIAL_ADD_ASSIGN || mod_expr->op == SPECIAL_SUB_ASSIGN))
856 		return;
857 
858 	reset_sm(sm);
859 }
860 
match_preop(struct expression * expr)861 static void match_preop(struct expression *expr)
862 {
863 	struct expression *parent;
864 	struct range_list *left, *right;
865 	int op;
866 
867 	/*
868 	 * This is an important special case.  Say you have:
869 	 *
870 	 * 	if (++j == limit)
871 	 *
872 	 * Assume that we know the range of limit is higher than the start
873 	 * value for "j".  Then the first thing that we process is the ++j.  We
874 	 * have not comparison states set up so it doesn't get caught by the
875 	 * modification hook.  But it does get caught by smatch_extra which sets
876 	 * j to unknown then we parse the "j == limit" and sets false to != but
877 	 * really we want false to be <.
878 	 *
879 	 * So what we do is we set j < limit here, then the match_modify catches
880 	 * it and we do a match_inc_dec().
881 	 *
882 	 */
883 
884 	if (expr->type != EXPR_PREOP ||
885 	    (expr->op != SPECIAL_INCREMENT && expr->op != SPECIAL_DECREMENT))
886 		return;
887 
888 	parent = expr_get_parent_expr(expr);
889 	if (!parent)
890 		return;
891 	if (parent->type != EXPR_COMPARE || parent->op != SPECIAL_EQUAL)
892 		return;
893 	if (parent->left != expr)
894 		return;
895 
896 	if (!get_implied_rl(expr->unop, &left) ||
897 	   !get_implied_rl(parent->right, &right))
898 		return;
899 
900 	op = rl_comparison(left, right);
901 	if (op == UNKNOWN_COMPARISON)
902 		return;
903 
904 	add_comparison(expr->unop, op, parent->right);
905 }
906 
chunk_to_var_sym(struct expression * expr,struct symbol ** sym)907 static char *chunk_to_var_sym(struct expression *expr, struct symbol **sym)
908 {
909 	expr = strip_expr(expr);
910 	if (!expr)
911 		return NULL;
912 	if (sym)
913 		*sym = NULL;
914 
915 	if (expr->type == EXPR_PREOP &&
916 	    (expr->op == SPECIAL_INCREMENT ||
917 	     expr->op == SPECIAL_DECREMENT))
918 		expr = strip_expr(expr->unop);
919 
920 	if (expr->type == EXPR_CALL) {
921 		char buf[64];
922 
923 		snprintf(buf, sizeof(buf), "return %p", expr);
924 		return alloc_string(buf);
925 	}
926 
927 	return expr_to_chunk_sym_vsl(expr, sym, NULL);
928 }
929 
chunk_to_var(struct expression * expr)930 static char *chunk_to_var(struct expression *expr)
931 {
932 	return chunk_to_var_sym(expr, NULL);
933 }
934 
get_state_chunk(int owner,struct expression * expr)935 static struct smatch_state *get_state_chunk(int owner, struct expression *expr)
936 {
937 	char *name;
938 	struct symbol *sym;
939 	struct smatch_state *ret;
940 
941 	name = chunk_to_var_sym(expr, &sym);
942 	if (!name)
943 		return NULL;
944 
945 	ret = get_state(owner, name, sym);
946 	free_string(name);
947 	return ret;
948 }
949 
save_link(struct expression * expr,char * link)950 static void save_link(struct expression *expr, char *link)
951 {
952 	char *var;
953 	struct symbol *sym;
954 
955 	expr = strip_expr(expr);
956 	if (expr->type == EXPR_BINOP) {
957 		char *chunk;
958 
959 		chunk = chunk_to_var(expr);
960 		if (!chunk)
961 			return;
962 
963 		save_link(expr->left, link);
964 		save_link(expr->right, link);
965 		save_link_var_sym(chunk, NULL, link);
966 		return;
967 	}
968 
969 	var = chunk_to_var_sym(expr, &sym);
970 	if (!var)
971 		return;
972 
973 	save_link_var_sym(var, sym, link);
974 	free_string(var);
975 }
976 
get_orig_comparison(struct stree * pre_stree,const char * left,const char * right)977 static int get_orig_comparison(struct stree *pre_stree, const char *left, const char *right)
978 {
979 	struct smatch_state *state;
980 	struct compare_data *data;
981 	int flip = 0;
982 	char state_name[256];
983 
984 	if (strcmp(left, right) > 0) {
985 		const char *tmp = right;
986 
987 		flip = 1;
988 		right = left;
989 		left = tmp;
990 	}
991 
992 	snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
993 	state = get_state_stree(pre_stree, comparison_id, state_name, NULL);
994 	if (!state || !state->data)
995 		return 0;
996 	data = state->data;
997 	if (flip)
998 		return flip_comparison(data->comparison);
999 	return data->comparison;
1000 
1001 }
1002 
have_common_var_sym(struct var_sym_list * left_vsl,struct var_sym_list * right_vsl)1003 static int have_common_var_sym(struct var_sym_list *left_vsl, struct var_sym_list *right_vsl)
1004 {
1005 	struct var_sym *tmp;
1006 
1007 	FOR_EACH_PTR(left_vsl, tmp) {
1008 		if (in_var_sym_list(right_vsl, tmp->var, tmp->sym))
1009 			return 1;
1010 	} END_FOR_EACH_PTR(tmp);
1011 
1012 	return 0;
1013 }
1014 
1015 /*
1016  * The idea here is that we take a comparison "a < b" and then we look at all
1017  * the things which "b" is compared against "b < c" and we say that that implies
1018  * a relationship "a < c".
1019  *
1020  * The names here about because the comparisons are organized like this
1021  * "a < b < c".
1022  *
1023  */
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)1024 static void update_tf_links(struct stree *pre_stree,
1025 			    struct expression *left_expr,
1026 			    const char *left_var, struct var_sym_list *left_vsl,
1027 			    int left_comparison, int left_false_comparison,
1028 			    const char *mid_var, struct var_sym_list *mid_vsl,
1029 			    struct string_list *links)
1030 {
1031 	struct smatch_state *state;
1032 	struct smatch_state *true_state, *false_state;
1033 	struct compare_data *data;
1034 	struct expression *right_expr;
1035 	const char *right_var;
1036 	struct var_sym_list *right_vsl;
1037 	int orig_comparison;
1038 	int right_comparison;
1039 	int true_comparison;
1040 	int false_comparison;
1041 	char *tmp;
1042 	char state_name[256];
1043 	struct var_sym *vs;
1044 
1045 	FOR_EACH_PTR(links, tmp) {
1046 		state = get_state_stree(pre_stree, comparison_id, tmp, NULL);
1047 		if (!state || !state->data)
1048 			continue;
1049 		data = state->data;
1050 		right_comparison = data->comparison;
1051 		right_expr = data->right;
1052 		right_var = data->right_var;
1053 		right_vsl = data->right_vsl;
1054 		if (strcmp(mid_var, right_var) == 0) {
1055 			right_expr = data->left;
1056 			right_var = data->left_var;
1057 			right_vsl = data->left_vsl;
1058 			right_comparison = flip_comparison(right_comparison);
1059 		}
1060 		if (have_common_var_sym(left_vsl, right_vsl))
1061 			continue;
1062 
1063 		orig_comparison = get_orig_comparison(pre_stree, left_var, right_var);
1064 
1065 		true_comparison = combine_comparisons(left_comparison, right_comparison);
1066 		false_comparison = combine_comparisons(left_false_comparison, right_comparison);
1067 
1068 		true_comparison = comparison_intersection(orig_comparison, true_comparison);
1069 		false_comparison = comparison_intersection(orig_comparison, false_comparison);
1070 
1071 		if (strcmp(left_var, right_var) > 0) {
1072 		  	struct expression *tmp_expr = left_expr;
1073 			const char *tmp_var = left_var;
1074 			struct var_sym_list *tmp_vsl = left_vsl;
1075 
1076 			left_expr = right_expr;
1077 			left_var = right_var;
1078 			left_vsl = right_vsl;
1079 			right_expr = tmp_expr;
1080 			right_var = tmp_var;
1081 			right_vsl = tmp_vsl;
1082 			true_comparison = flip_comparison(true_comparison);
1083 			false_comparison = flip_comparison(false_comparison);
1084 		}
1085 
1086 		if (!true_comparison && !false_comparison)
1087 			continue;
1088 
1089 		if (true_comparison)
1090 			true_state = alloc_compare_state(
1091 					left_expr, left_var, left_vsl,
1092 					true_comparison,
1093 					right_expr, right_var, right_vsl);
1094 		else
1095 			true_state = NULL;
1096 		if (false_comparison)
1097 			false_state = alloc_compare_state(
1098 					left_expr, left_var, left_vsl,
1099 					false_comparison,
1100 					right_expr, right_var, right_vsl);
1101 		else
1102 			false_state = NULL;
1103 
1104 		snprintf(state_name, sizeof(state_name), "%s vs %s", left_var, right_var);
1105 		set_true_false_states(comparison_id, state_name, NULL, true_state, false_state);
1106 		FOR_EACH_PTR(left_vsl, vs) {
1107 			save_link_var_sym(vs->var, vs->sym, state_name);
1108 		} END_FOR_EACH_PTR(vs);
1109 		FOR_EACH_PTR(right_vsl, vs) {
1110 			save_link_var_sym(vs->var, vs->sym, state_name);
1111 		} END_FOR_EACH_PTR(vs);
1112 		if (!vsl_to_sym(left_vsl))
1113 			save_link_var_sym(left_var, NULL, state_name);
1114 		if (!vsl_to_sym(right_vsl))
1115 			save_link_var_sym(right_var, NULL, state_name);
1116 	} END_FOR_EACH_PTR(tmp);
1117 }
1118 
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)1119 static void update_tf_data(struct stree *pre_stree,
1120 		struct expression *left_expr,
1121 		const char *left_name, struct var_sym_list *left_vsl,
1122 		struct expression *right_expr,
1123 		const char *right_name, struct var_sym_list *right_vsl,
1124 		int true_comparison, int false_comparison)
1125 {
1126 	struct smatch_state *state;
1127 
1128 	state = get_state_stree(pre_stree, link_id, right_name, vsl_to_sym(right_vsl));
1129 	if (state)
1130 		update_tf_links(pre_stree, left_expr, left_name, left_vsl, true_comparison, false_comparison, right_name, right_vsl, state->data);
1131 
1132 	state = get_state_stree(pre_stree, link_id, left_name, vsl_to_sym(left_vsl));
1133 	if (state)
1134 		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);
1135 }
1136 
iter_modify(struct sm_state * sm,struct expression * mod_expr)1137 static void iter_modify(struct sm_state *sm, struct expression *mod_expr)
1138 {
1139 	if (sm->state != &start ||
1140 	    !mod_expr ||
1141 	    (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP) ||
1142 	    mod_expr->op != SPECIAL_INCREMENT)
1143 		set_state(inc_dec_id, sm->name, sm->sym, &undefined);
1144 	else
1145 		set_state(inc_dec_id, sm->name, sm->sym, &incremented);
1146 }
1147 
handle_for_loops(struct expression * expr,char * state_name,struct smatch_state * false_state)1148 static void handle_for_loops(struct expression *expr, char *state_name, struct smatch_state *false_state)
1149 {
1150 	sval_t sval;
1151 	char *iter_name, *cap_name;
1152 	struct symbol *iter_sym, *cap_sym;
1153 	struct compare_data *data;
1154 
1155 	if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
1156 		return;
1157 
1158 	if (!__cur_stmt || !__prev_stmt)
1159 		return;
1160 	if (__cur_stmt->type != STMT_ITERATOR)
1161 		return;
1162 	if (__cur_stmt->iterator_pre_condition != expr)
1163 		return;
1164 
1165 	/* literals are handled in smatch_extra.c */
1166 	if (get_value(expr->right, &sval))
1167 		return;
1168 
1169 	/* First time checking the condition */
1170 	if (__prev_stmt == __cur_stmt->iterator_pre_statement) {
1171 		if (!get_implied_value(expr->left, &sval) ||
1172 		    sval.value != 0)
1173 			return;
1174 
1175 		iter_name = expr_to_var_sym(expr->left, &iter_sym);
1176 		cap_name = expr_to_var_sym(expr->right, &cap_sym);
1177 		if (!iter_name || !cap_name || !iter_sym || !cap_sym) {
1178 			free_string(iter_name);
1179 			free_string(cap_name);
1180 			return;
1181 		}
1182 
1183 		set_state(inc_dec_id, iter_name, iter_sym, &start);
1184 		store_link(inc_dec_link_id, cap_name, cap_sym, iter_name, iter_sym);
1185 
1186 		free_string(iter_name);
1187 		free_string(cap_name);
1188 		return;
1189 	}
1190 
1191 	/* Second time checking the condtion */
1192 	if (__prev_stmt != __cur_stmt->iterator_post_statement)
1193 		return;
1194 
1195 	if (get_state_chunk(inc_dec_id, expr->left) != &incremented)
1196 		return;
1197 
1198 	data = false_state->data;
1199 	false_state = alloc_compare_state(
1200 			data->left, data->left_var, data->left_vsl,
1201 			SPECIAL_EQUAL,
1202 			data->right, data->right_var, data->right_vsl);
1203 
1204 	// FIXME: This doesn't handle links correct so it doesn't set "param orig"
1205 	set_true_false_states(comparison_id, state_name, NULL, NULL, false_state);
1206 }
1207 
is_plus_one(struct expression * expr)1208 static int is_plus_one(struct expression *expr)
1209 {
1210 	sval_t sval;
1211 
1212 	if (expr->type != EXPR_BINOP || expr->op != '+')
1213 		return 0;
1214 	if (!get_implied_value(expr->right, &sval) || sval.value != 1)
1215 		return 0;
1216 	return 1;
1217 }
1218 
is_minus_one(struct expression * expr)1219 static int is_minus_one(struct expression *expr)
1220 {
1221 	sval_t sval;
1222 
1223 	if (expr->type != EXPR_BINOP || expr->op != '-')
1224 		return 0;
1225 	if (!get_implied_value(expr->right, &sval) || sval.value != 1)
1226 		return 0;
1227 	return 1;
1228 }
1229 
move_plus_to_minus_helper(struct expression ** left_p,struct expression ** right_p)1230 static void move_plus_to_minus_helper(struct expression **left_p, struct expression **right_p)
1231 {
1232 	struct expression *left = *left_p;
1233 	struct expression *right = *right_p;
1234 
1235 	/*
1236 	 * These two are basically equivalent: "foo + 1 != bar" and
1237 	 * "foo != bar - 1".  There are issues with signedness and integer
1238 	 * overflows.  There are also issues with type as well.  But let's
1239 	 * pretend we can ignore all that stuff for now.
1240 	 *
1241 	 */
1242 
1243 	if (!is_plus_one(left))
1244 		return;
1245 
1246 	*left_p = left->left;
1247 	*right_p = binop_expression(right, '-', left->right);
1248 }
1249 
move_plus_to_minus(struct expression ** left_p,struct expression ** right_p)1250 static void move_plus_to_minus(struct expression **left_p, struct expression **right_p)
1251 {
1252 	if (is_plus_one(*left_p) && is_plus_one(*right_p))
1253 		return;
1254 
1255 	move_plus_to_minus_helper(left_p, right_p);
1256 	move_plus_to_minus_helper(right_p, left_p);
1257 }
1258 
handle_comparison(struct expression * left_expr,int op,struct expression * right_expr,char ** _state_name,struct smatch_state ** _false_state)1259 static void handle_comparison(struct expression *left_expr, int op, struct expression *right_expr, char **_state_name, struct smatch_state **_false_state)
1260 {
1261 	char *left = NULL;
1262 	char *right = NULL;
1263 	struct symbol *left_sym, *right_sym;
1264 	struct var_sym_list *left_vsl = NULL;
1265 	struct var_sym_list *right_vsl = NULL;
1266 	int false_op;
1267 	int orig_comparison;
1268 	struct smatch_state *true_state, *false_state;
1269 	static char state_name[256];
1270 	struct stree *pre_stree;
1271 	sval_t sval;
1272 
1273 	if (!left_expr || !right_expr)
1274 		return;
1275 
1276 	left_expr = strip_parens(left_expr);
1277 	right_expr = strip_parens(right_expr);
1278 
1279 	while (left_expr->type == EXPR_ASSIGNMENT)
1280 		left_expr = strip_parens(left_expr->left);
1281 	while (right_expr->type == EXPR_ASSIGNMENT)
1282 		right_expr = strip_parens(right_expr->left);
1283 
1284 	false_op = negate_comparison(op);
1285 
1286 	move_plus_to_minus(&left_expr, &right_expr);
1287 
1288 	if (op == SPECIAL_UNSIGNED_LT &&
1289 	    get_implied_value(left_expr, &sval) &&
1290 	    sval.value == 0)
1291 		false_op = SPECIAL_EQUAL;
1292 
1293 	if (op == SPECIAL_UNSIGNED_GT &&
1294 	    get_implied_value(right_expr, &sval) &&
1295 	    sval.value == 0)
1296 		false_op = SPECIAL_EQUAL;
1297 
1298 	left = chunk_to_var_sym(left_expr, &left_sym);
1299 	if (!left)
1300 		goto free;
1301 	if (left_sym)
1302 		add_var_sym(&left_vsl, left, left_sym);
1303 	else
1304 		left_vsl = expr_to_vsl(left_expr);
1305 	right = chunk_to_var_sym(right_expr, &right_sym);
1306 	if (!right)
1307 		goto free;
1308 	if (right_sym)
1309 		add_var_sym(&right_vsl, right, right_sym);
1310 	else
1311 		right_vsl = expr_to_vsl(right_expr);
1312 
1313 	if (strcmp(left, right) > 0) {
1314 		char *tmp_name = left;
1315 		struct var_sym_list *tmp_vsl = left_vsl;
1316 		struct expression *tmp_expr = left_expr;
1317 
1318 		left = right;
1319 		left_vsl = right_vsl;
1320 		left_expr = right_expr;
1321 		right = tmp_name;
1322 		right_vsl = tmp_vsl;
1323 		right_expr = tmp_expr;
1324 		op = flip_comparison(op);
1325 		false_op = flip_comparison(false_op);
1326 	}
1327 
1328 	orig_comparison = get_comparison(left_expr, right_expr);
1329 	op = comparison_intersection(orig_comparison, op);
1330 	false_op = comparison_intersection(orig_comparison, false_op);
1331 
1332 	snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
1333 	true_state = alloc_compare_state(
1334 			left_expr, left, left_vsl,
1335 			op,
1336 			right_expr, right, right_vsl);
1337 	false_state = alloc_compare_state(
1338 			left_expr, left, left_vsl,
1339 			false_op,
1340 			right_expr, right, right_vsl);
1341 
1342 	pre_stree = clone_stree(__get_cur_stree());
1343 	update_tf_data(pre_stree, left_expr, left, left_vsl, right_expr, right, right_vsl, op, false_op);
1344 	free_stree(&pre_stree);
1345 
1346 	set_true_false_states(comparison_id, state_name, NULL, true_state, false_state);
1347 	__compare_param_limit_hook(left_expr, right_expr, state_name, true_state, false_state);
1348 	save_link(left_expr, state_name);
1349 	save_link(right_expr, state_name);
1350 
1351 	if (_false_state)
1352 		*_false_state = false_state;
1353 	if (_state_name)
1354 		*_state_name = state_name;
1355 free:
1356 	free_string(left);
1357 	free_string(right);
1358 }
1359 
__comparison_match_condition(struct expression * expr)1360 void __comparison_match_condition(struct expression *expr)
1361 {
1362 	struct expression *left, *right, *new_left, *new_right, *tmp;
1363 	struct smatch_state *false_state = NULL;
1364 	char *state_name = NULL;
1365 	int redo, count;
1366 
1367 	if (expr->type != EXPR_COMPARE)
1368 		return;
1369 
1370 	handle_comparison(expr->left, expr->op, expr->right, &state_name, &false_state);
1371 	if (false_state && state_name)
1372 		handle_for_loops(expr, state_name, false_state);
1373 
1374 	left = strip_parens(expr->left);
1375 	right = strip_parens(expr->right);
1376 
1377 	if (left->type == EXPR_BINOP && left->op == '+') {
1378 		new_left = left->left;
1379 		new_right = binop_expression(right, '-', left->right);
1380 		handle_comparison(new_left, expr->op, new_right, NULL, NULL);
1381 
1382 		new_left = left->right;
1383 		new_right = binop_expression(right, '-', left->left);
1384 		handle_comparison(new_left, expr->op, new_right, NULL, NULL);
1385 	}
1386 
1387 	redo = 0;
1388 	left = strip_parens(expr->left);
1389 	right = strip_parens(expr->right);
1390 	if (get_last_expr_from_expression_stmt(expr->left)) {
1391 		left = get_last_expr_from_expression_stmt(expr->left);
1392 		redo = 1;
1393 	}
1394 	if (get_last_expr_from_expression_stmt(expr->right)) {
1395 		right = get_last_expr_from_expression_stmt(expr->right);
1396 		redo = 1;
1397 	}
1398 
1399 	if (!redo)
1400 		return;
1401 
1402 	count = 0;
1403 	while ((tmp = get_assigned_expr(left))) {
1404 		if (count++ > 3)
1405 			break;
1406 		left = strip_expr(tmp);
1407 	}
1408 	count = 0;
1409 	while ((tmp = get_assigned_expr(right))) {
1410 		if (count++ > 3)
1411 			break;
1412 		right = strip_expr(tmp);
1413 	}
1414 
1415 	handle_comparison(left, expr->op, right, NULL, NULL);
1416 }
1417 
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)1418 static void add_comparison_var_sym(
1419 		struct expression *left_expr,
1420 		const char *left_name, struct var_sym_list *left_vsl,
1421 		int comparison,
1422 		struct expression *right_expr,
1423 		const char *right_name, struct var_sym_list *right_vsl)
1424 {
1425 	struct smatch_state *state;
1426 	struct var_sym *vs;
1427 	char state_name[256];
1428 
1429 	if (strcmp(left_name, right_name) > 0) {
1430 		struct expression *tmp_expr = left_expr;
1431 		const char *tmp_name = left_name;
1432 		struct var_sym_list *tmp_vsl = left_vsl;
1433 
1434 		left_expr = right_expr;
1435 		left_name = right_name;
1436 		left_vsl = right_vsl;
1437 		right_expr = tmp_expr;
1438 		right_name = tmp_name;
1439 		right_vsl = tmp_vsl;
1440 		comparison = flip_comparison(comparison);
1441 	}
1442 	snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1443 	state = alloc_compare_state(
1444 			left_expr, left_name, left_vsl,
1445 			comparison,
1446 			right_expr, right_name, right_vsl);
1447 
1448 	set_state(comparison_id, state_name, NULL, state);
1449 
1450 	FOR_EACH_PTR(left_vsl, vs) {
1451 		save_link_var_sym(vs->var, vs->sym, state_name);
1452 	} END_FOR_EACH_PTR(vs);
1453 	FOR_EACH_PTR(right_vsl, vs) {
1454 		save_link_var_sym(vs->var, vs->sym, state_name);
1455 	} END_FOR_EACH_PTR(vs);
1456 }
1457 
add_comparison(struct expression * left,int comparison,struct expression * right)1458 static void add_comparison(struct expression *left, int comparison, struct expression *right)
1459 {
1460 	char *left_name = NULL;
1461 	char *right_name = NULL;
1462 	struct symbol *left_sym, *right_sym;
1463 	struct var_sym_list *left_vsl, *right_vsl;
1464 	struct smatch_state *state;
1465 	char state_name[256];
1466 
1467 	left_name = chunk_to_var_sym(left, &left_sym);
1468 	if (!left_name)
1469 		goto free;
1470 	left_vsl = expr_to_vsl(left);
1471 	right_name = chunk_to_var_sym(right, &right_sym);
1472 	if (!right_name)
1473 		goto free;
1474 	right_vsl = expr_to_vsl(right);
1475 
1476 	if (strcmp(left_name, right_name) > 0) {
1477 		struct expression *tmp_expr = left;
1478 		struct symbol *tmp_sym = left_sym;
1479 		char *tmp_name = left_name;
1480 		struct var_sym_list *tmp_vsl = left_vsl;
1481 
1482 		left = right;
1483 		left_name = right_name;
1484 		left_sym = right_sym;
1485 		left_vsl = right_vsl;
1486 		right = tmp_expr;
1487 		right_name = tmp_name;
1488 		right_sym = tmp_sym;
1489 		right_vsl = tmp_vsl;
1490 		comparison = flip_comparison(comparison);
1491 	}
1492 	snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1493 	state = alloc_compare_state(
1494 			left, left_name, left_vsl,
1495 			comparison,
1496 			right, right_name, right_vsl);
1497 
1498 	set_state(comparison_id, state_name, NULL, state);
1499 	save_link(left, state_name);
1500 	save_link(right, state_name);
1501 
1502 free:
1503 	free_string(left_name);
1504 	free_string(right_name);
1505 }
1506 
match_assign_add(struct expression * expr)1507 static void match_assign_add(struct expression *expr)
1508 {
1509 	struct expression *right;
1510 	struct expression *r_left, *r_right;
1511 	sval_t left_tmp, right_tmp;
1512 
1513 	right = strip_expr(expr->right);
1514 	r_left = strip_expr(right->left);
1515 	r_right = strip_expr(right->right);
1516 
1517 	get_absolute_min(r_left, &left_tmp);
1518 	get_absolute_min(r_right, &right_tmp);
1519 
1520 	if (left_tmp.value > 0)
1521 		add_comparison(expr->left, '>', r_right);
1522 	else if (left_tmp.value == 0)
1523 		add_comparison(expr->left, SPECIAL_GTE, r_right);
1524 
1525 	if (right_tmp.value > 0)
1526 		add_comparison(expr->left, '>', r_left);
1527 	else if (right_tmp.value == 0)
1528 		add_comparison(expr->left, SPECIAL_GTE, r_left);
1529 }
1530 
match_assign_sub(struct expression * expr)1531 static void match_assign_sub(struct expression *expr)
1532 {
1533 	struct expression *right;
1534 	struct expression *r_left, *r_right;
1535 	int comparison;
1536 	sval_t min;
1537 
1538 	right = strip_expr(expr->right);
1539 	r_left = strip_expr(right->left);
1540 	r_right = strip_expr(right->right);
1541 
1542 	if (get_absolute_min(r_right, &min) && sval_is_negative(min))
1543 		return;
1544 
1545 	comparison = get_comparison(r_left, r_right);
1546 
1547 	switch (comparison) {
1548 	case '>':
1549 	case SPECIAL_GTE:
1550 		if (implied_not_equal(r_right, 0))
1551 			add_comparison(expr->left, '>', r_left);
1552 		else
1553 			add_comparison(expr->left, SPECIAL_GTE, r_left);
1554 		return;
1555 	}
1556 }
1557 
match_assign_divide(struct expression * expr)1558 static void match_assign_divide(struct expression *expr)
1559 {
1560 	struct expression *right;
1561 	struct expression *r_left, *r_right;
1562 	sval_t min;
1563 
1564 	right = strip_expr(expr->right);
1565 	r_left = strip_expr(right->left);
1566 	r_right = strip_expr(right->right);
1567 	if (!get_implied_min(r_right, &min) || min.value <= 1)
1568 		return;
1569 
1570 	add_comparison(expr->left, '<', r_left);
1571 }
1572 
match_binop_assign(struct expression * expr)1573 static void match_binop_assign(struct expression *expr)
1574 {
1575 	struct expression *right;
1576 
1577 	right = strip_expr(expr->right);
1578 	if (right->op == '+')
1579 		match_assign_add(expr);
1580 	if (right->op == '-')
1581 		match_assign_sub(expr);
1582 	if (right->op == '/')
1583 		match_assign_divide(expr);
1584 }
1585 
copy_comparisons(struct expression * left,struct expression * right)1586 static void copy_comparisons(struct expression *left, struct expression *right)
1587 {
1588 	struct string_list *links;
1589 	struct smatch_state *state;
1590 	struct compare_data *data;
1591 	struct symbol *left_sym, *right_sym;
1592 	char *left_var = NULL;
1593 	char *right_var = NULL;
1594 	struct var_sym_list *left_vsl;
1595 	struct expression *expr;
1596 	const char *var;
1597 	struct var_sym_list *vsl;
1598 	int comparison;
1599 	char *tmp;
1600 
1601 	left_var = chunk_to_var_sym(left, &left_sym);
1602 	if (!left_var)
1603 		goto done;
1604 	left_vsl = expr_to_vsl(left);
1605 	right_var = chunk_to_var_sym(right, &right_sym);
1606 	if (!right_var)
1607 		goto done;
1608 
1609 	state = get_state(link_id, right_var, right_sym);
1610 	if (!state)
1611 		return;
1612 	links = state->data;
1613 
1614 	FOR_EACH_PTR(links, tmp) {
1615 		state = get_state(comparison_id, tmp, NULL);
1616 		if (!state || !state->data)
1617 			continue;
1618 		data = state->data;
1619 		comparison = data->comparison;
1620 		expr = data->right;
1621 		var = data->right_var;
1622 		vsl = data->right_vsl;
1623 		if (strcmp(var, right_var) == 0) {
1624 			expr = data->left;
1625 			var = data->left_var;
1626 			vsl = data->left_vsl;
1627 			comparison = flip_comparison(comparison);
1628 		}
1629 		/* n = copy_from_user(dest, src, n); leads to n <= n which is nonsense */
1630 		if (strcmp(left_var, var) == 0)
1631 			continue;
1632 		add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1633 	} END_FOR_EACH_PTR(tmp);
1634 
1635 done:
1636 	free_string(right_var);
1637 }
1638 
match_assign(struct expression * expr)1639 static void match_assign(struct expression *expr)
1640 {
1641 	struct expression *right;
1642 
1643 	if (expr->op != '=')
1644 		return;
1645 	if (__in_fake_assign || outside_of_function())
1646 		return;
1647 
1648 	if (is_struct(expr->left))
1649 		return;
1650 
1651 	if (is_self_assign(expr))
1652 		return;
1653 
1654 	copy_comparisons(expr->left, expr->right);
1655 	add_comparison(expr->left, SPECIAL_EQUAL, expr->right);
1656 
1657 	right = strip_expr(expr->right);
1658 	if (right->type == EXPR_BINOP)
1659 		match_binop_assign(expr);
1660 }
1661 
get_comparison_strings(const char * one,const char * two)1662 int get_comparison_strings(const char *one, const char *two)
1663 {
1664 	char buf[256];
1665 	struct smatch_state *state;
1666 	int invert = 0;
1667 	int ret = 0;
1668 
1669 	if (!one || !two)
1670 		return UNKNOWN_COMPARISON;
1671 
1672 	if (strcmp(one, two) == 0)
1673 		return SPECIAL_EQUAL;
1674 
1675 	if (strcmp(one, two) > 0) {
1676 		const char *tmp = one;
1677 
1678 		one = two;
1679 		two = tmp;
1680 		invert = 1;
1681 	}
1682 
1683 	snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1684 	state = get_state(comparison_id, buf, NULL);
1685 	if (state)
1686 		ret = state_to_comparison(state);
1687 
1688 	if (invert)
1689 		ret = flip_comparison(ret);
1690 
1691 	return ret;
1692 }
1693 
get_comparison_helper(struct expression * a,struct expression * b,bool use_extra)1694 static int get_comparison_helper(struct expression *a, struct expression *b, bool use_extra)
1695 {
1696 	char *one = NULL;
1697 	char *two = NULL;
1698 	int ret = UNKNOWN_COMPARISON;
1699 	int extra = UNKNOWN_COMPARISON;
1700 
1701 	if (a == UNKNOWN_COMPARISON ||
1702 	    b == UNKNOWN_COMPARISON)
1703 		return UNKNOWN_COMPARISON;
1704 
1705 	a = strip_parens(a);
1706 	b = strip_parens(b);
1707 
1708 	move_plus_to_minus(&a, &b);
1709 
1710 	one = chunk_to_var(a);
1711 	if (!one)
1712 		goto free;
1713 	two = chunk_to_var(b);
1714 	if (!two)
1715 		goto free;
1716 
1717 	ret = get_comparison_strings(one, two);
1718 	if (ret)
1719 		goto free;
1720 
1721 	if (is_plus_one(a) || is_minus_one(a)) {
1722 		free_string(one);
1723 		one = chunk_to_var(a->left);
1724 		ret = get_comparison_strings(one, two);
1725 	} else if (is_plus_one(b) || is_minus_one(b)) {
1726 		free_string(two);
1727 		two = chunk_to_var(b->left);
1728 		ret = get_comparison_strings(one, two);
1729 	}
1730 
1731 	if (ret == UNKNOWN_COMPARISON)
1732 		goto free;
1733 
1734 	if ((is_plus_one(a) || is_minus_one(b)) && ret == '<')
1735 		ret = SPECIAL_LTE;
1736 	else if ((is_minus_one(a) || is_plus_one(b)) && ret == '>')
1737 		ret = SPECIAL_GTE;
1738 	else
1739 		ret = UNKNOWN_COMPARISON;
1740 
1741 free:
1742 	free_string(one);
1743 	free_string(two);
1744 
1745 	extra = comparison_from_extra(a, b);
1746 	return comparison_intersection(ret, extra);
1747 }
1748 
get_comparison(struct expression * a,struct expression * b)1749 int get_comparison(struct expression *a, struct expression *b)
1750 {
1751 	return get_comparison_helper(a, b, true);
1752 }
1753 
get_comparison_no_extra(struct expression * a,struct expression * b)1754 int get_comparison_no_extra(struct expression *a, struct expression *b)
1755 {
1756 	return get_comparison_helper(a, b, false);
1757 }
1758 
possible_comparison(struct expression * a,int comparison,struct expression * b)1759 int possible_comparison(struct expression *a, int comparison, struct expression *b)
1760 {
1761 	char *one = NULL;
1762 	char *two = NULL;
1763 	int ret = 0;
1764 	char buf[256];
1765 	struct sm_state *sm;
1766 	int saved;
1767 
1768 	one = chunk_to_var(a);
1769 	if (!one)
1770 		goto free;
1771 	two = chunk_to_var(b);
1772 	if (!two)
1773 		goto free;
1774 
1775 
1776 	if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) {
1777 		ret = 1;
1778 		goto free;
1779 	}
1780 
1781 	if (strcmp(one, two) > 0) {
1782 		char *tmp = one;
1783 
1784 		one = two;
1785 		two = tmp;
1786 		comparison = flip_comparison(comparison);
1787 	}
1788 
1789 	snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1790 	sm = get_sm_state(comparison_id, buf, NULL);
1791 	if (!sm)
1792 		goto free;
1793 
1794 	FOR_EACH_PTR(sm->possible, sm) {
1795 		if (!sm->state->data)
1796 			continue;
1797 		saved = ((struct compare_data *)sm->state->data)->comparison;
1798 		if (saved == comparison)
1799 			ret = 1;
1800 		if (comparison == SPECIAL_EQUAL &&
1801 		    (saved == SPECIAL_LTE ||
1802 		     saved == SPECIAL_GTE ||
1803 		     saved == SPECIAL_UNSIGNED_LTE ||
1804 		     saved == SPECIAL_UNSIGNED_GTE))
1805 			ret = 1;
1806 		if (ret == 1)
1807 			goto free;
1808 	} END_FOR_EACH_PTR(sm);
1809 
1810 	return ret;
1811 free:
1812 	free_string(one);
1813 	free_string(two);
1814 	return ret;
1815 }
1816 
get_all_comparisons(struct expression * expr)1817 struct state_list *get_all_comparisons(struct expression *expr)
1818 {
1819 	struct smatch_state *state;
1820 	struct string_list *links;
1821 	struct state_list *ret = NULL;
1822 	struct sm_state *sm;
1823 	char *tmp;
1824 
1825 	state = get_state_chunk(link_id, expr);
1826 	if (!state)
1827 		return NULL;
1828 	links = state->data;
1829 
1830 	FOR_EACH_PTR(links, tmp) {
1831 		sm = get_sm_state(comparison_id, tmp, NULL);
1832 		if (!sm)
1833 			continue;
1834 		// FIXME have to compare name with vsl
1835 		add_ptr_list(&ret, sm);
1836 	} END_FOR_EACH_PTR(tmp);
1837 
1838 	return ret;
1839 }
1840 
get_all_possible_equal_comparisons(struct expression * expr)1841 struct state_list *get_all_possible_equal_comparisons(struct expression *expr)
1842 {
1843 	struct smatch_state *state;
1844 	struct string_list *links;
1845 	struct state_list *ret = NULL;
1846 	struct sm_state *sm;
1847 	char *tmp;
1848 
1849 	state = get_state_chunk(link_id, expr);
1850 	if (!state)
1851 		return NULL;
1852 	links = state->data;
1853 
1854 	FOR_EACH_PTR(links, tmp) {
1855 		sm = get_sm_state(comparison_id, tmp, NULL);
1856 		if (!sm)
1857 			continue;
1858 		if (!strchr(sm->state->name, '='))
1859 			continue;
1860 		if (strcmp(sm->state->name, "!=") == 0)
1861 			continue;
1862 		add_ptr_list(&ret, sm);
1863 	} END_FOR_EACH_PTR(tmp);
1864 
1865 	return ret;
1866 }
1867 
get_all_possible_not_equal_comparisons(struct expression * expr)1868 struct state_list *get_all_possible_not_equal_comparisons(struct expression *expr)
1869 {
1870 	struct smatch_state *state;
1871 	struct string_list *links;
1872 	struct state_list *ret = NULL;
1873 	struct sm_state *sm;
1874 	struct sm_state *possible;
1875 	char *link;
1876 
1877 	return NULL;
1878 
1879 	state = get_state_chunk(link_id, expr);
1880 	if (!state)
1881 		return NULL;
1882 	links = state->data;
1883 
1884 	FOR_EACH_PTR(links, link) {
1885 		sm = get_sm_state(comparison_id, link, NULL);
1886 		if (!sm)
1887 			continue;
1888 		FOR_EACH_PTR(sm->possible, possible) {
1889 			if (strcmp(possible->state->name, "!=") != 0)
1890 				continue;
1891 			add_ptr_list(&ret, sm);
1892 			break;
1893 		} END_FOR_EACH_PTR(link);
1894 	} END_FOR_EACH_PTR(link);
1895 
1896 	return ret;
1897 }
1898 
update_links_from_call(struct expression * left,int left_compare,struct expression * right)1899 static void update_links_from_call(struct expression *left,
1900 				   int left_compare,
1901 				   struct expression *right)
1902 {
1903 	struct string_list *links;
1904 	struct smatch_state *state;
1905 	struct compare_data *data;
1906 	struct symbol *left_sym, *right_sym;
1907 	char *left_var = NULL;
1908 	char *right_var = NULL;
1909 	struct var_sym_list *left_vsl;
1910 	struct expression *expr;
1911 	const char *var;
1912 	struct var_sym_list *vsl;
1913 	int comparison;
1914 	char *tmp;
1915 
1916 	left_var = chunk_to_var_sym(left, &left_sym);
1917 	if (!left_var)
1918 		goto done;
1919 	left_vsl = expr_to_vsl(left);
1920 	right_var = chunk_to_var_sym(right, &right_sym);
1921 	if (!right_var)
1922 		goto done;
1923 
1924 	state = get_state(link_id, right_var, right_sym);
1925 	if (!state)
1926 		return;
1927 	links = state->data;
1928 
1929 	FOR_EACH_PTR(links, tmp) {
1930 		state = get_state(comparison_id, tmp, NULL);
1931 		if (!state || !state->data)
1932 			continue;
1933 		data = state->data;
1934 		comparison = data->comparison;
1935 		expr = data->right;
1936 		var = data->right_var;
1937 		vsl = data->right_vsl;
1938 		if (strcmp(var, right_var) == 0) {
1939 			expr = data->left;
1940 			var = data->left_var;
1941 			vsl = data->left_vsl;
1942 			comparison = flip_comparison(comparison);
1943 		}
1944 		comparison = combine_comparisons(left_compare, comparison);
1945 		if (!comparison)
1946 			continue;
1947 		add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1948 	} END_FOR_EACH_PTR(tmp);
1949 
1950 done:
1951 	free_string(right_var);
1952 }
1953 
__add_return_comparison(struct expression * call,const char * range)1954 void __add_return_comparison(struct expression *call, const char *range)
1955 {
1956 	struct expression *arg;
1957 	int comparison;
1958 	char buf[16];
1959 
1960 	if (!str_to_comparison_arg(range, call, &comparison, &arg))
1961 		return;
1962 	snprintf(buf, sizeof(buf), "%s", show_comparison(comparison));
1963 	update_links_from_call(call, comparison, arg);
1964 	add_comparison(call, comparison, arg);
1965 }
1966 
__add_comparison_info(struct expression * expr,struct expression * call,const char * range)1967 void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
1968 {
1969 	copy_comparisons(expr, call);
1970 }
1971 
get_mask_comparison(struct expression * expr,int ignore)1972 static char *get_mask_comparison(struct expression *expr, int ignore)
1973 {
1974 	struct expression *tmp, *right;
1975 	int count, param;
1976 	char buf[256];
1977 
1978 	/* The return value for "return foo & param;" is <= param */
1979 
1980 	count = 0;
1981 	while ((tmp = get_assigned_expr(expr))) {
1982 		expr = strip_expr(tmp);
1983 		if (count++ > 4)
1984 			break;
1985 	}
1986 
1987 	if (expr->type != EXPR_BINOP || expr->op != '&')
1988 		return NULL;
1989 
1990 	right = strip_expr(expr->right);
1991 	param = get_param_num(right);
1992 	if (param < 0 || param == ignore)
1993 		return NULL;
1994 
1995 	snprintf(buf, sizeof(buf), "[<=$%d]", param);
1996 	return alloc_sname(buf);
1997 }
1998 
range_comparison_to_param_helper(struct expression * expr,char starts_with,int ignore)1999 static char *range_comparison_to_param_helper(struct expression *expr, char starts_with, int ignore)
2000 {
2001 	struct symbol *param;
2002 	char *var = NULL;
2003 	char buf[256];
2004 	char *ret_str = NULL;
2005 	int compare;
2006 	int i;
2007 
2008 	if (!expr)
2009 		return NULL;
2010 
2011 	var = chunk_to_var(expr);
2012 	if (!var)
2013 		goto try_mask;
2014 
2015 	i = -1;
2016 	FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
2017 		i++;
2018 		if (i == ignore)
2019 			continue;
2020 		if (!param->ident)
2021 			continue;
2022 		snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
2023 		compare = get_comparison_strings(var, buf);
2024 		if (compare == UNKNOWN_COMPARISON ||
2025 		    compare == IMPOSSIBLE_COMPARISON)
2026 			continue;
2027 		if (show_comparison(compare)[0] != starts_with)
2028 			continue;
2029 		snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
2030 		ret_str = alloc_sname(buf);
2031 		break;
2032 	} END_FOR_EACH_PTR(param);
2033 
2034 	free_string(var);
2035 	if (!ret_str)
2036 		goto try_mask;
2037 
2038 	return ret_str;
2039 
2040 try_mask:
2041 	if (starts_with == '<')
2042 		ret_str = get_mask_comparison(expr, ignore);
2043 	return ret_str;
2044 }
2045 
name_sym_to_param_comparison(const char * name,struct symbol * sym)2046 char *name_sym_to_param_comparison(const char *name, struct symbol *sym)
2047 {
2048 	struct symbol *param;
2049 	char buf[256];
2050 	int compare;
2051 	int i;
2052 
2053 	i = -1;
2054 	FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
2055 		i++;
2056 		if (!param->ident)
2057 			continue;
2058 		snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
2059 		compare = get_comparison_strings(name, buf);
2060 		if (compare == UNKNOWN_COMPARISON ||
2061 		    compare == IMPOSSIBLE_COMPARISON)
2062 			continue;
2063 		snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
2064 		return alloc_sname(buf);
2065 	} END_FOR_EACH_PTR(param);
2066 
2067 	return NULL;
2068 }
2069 
expr_equal_to_param(struct expression * expr,int ignore)2070 char *expr_equal_to_param(struct expression *expr, int ignore)
2071 {
2072 	return range_comparison_to_param_helper(expr, '=', ignore);
2073 }
2074 
expr_lte_to_param(struct expression * expr,int ignore)2075 char *expr_lte_to_param(struct expression *expr, int ignore)
2076 {
2077 	return range_comparison_to_param_helper(expr, '<', ignore);
2078 }
2079 
expr_param_comparison(struct expression * expr,int ignore)2080 char *expr_param_comparison(struct expression *expr, int ignore)
2081 {
2082 	struct symbol *param;
2083 	char *var = NULL;
2084 	char buf[256];
2085 	char *ret_str = NULL;
2086 	int compare;
2087 	int i;
2088 
2089 	var = chunk_to_var(expr);
2090 	if (!var)
2091 		goto free;
2092 
2093 	i = -1;
2094 	FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
2095 		i++;
2096 		if (i == ignore)
2097 			continue;
2098 		if (!param->ident)
2099 			continue;
2100 		snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
2101 		compare = get_comparison_strings(var, buf);
2102 		if (!compare)
2103 			continue;
2104 		snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
2105 		ret_str = alloc_sname(buf);
2106 		break;
2107 	} END_FOR_EACH_PTR(param);
2108 
2109 free:
2110 	free_string(var);
2111 	return ret_str;
2112 }
2113 
get_printed_param_name(struct expression * call,const char * param_name,struct symbol * param_sym)2114 char *get_printed_param_name(struct expression *call, const char *param_name, struct symbol *param_sym)
2115 {
2116 	struct expression *arg;
2117 	char *name;
2118 	struct symbol *sym;
2119 	static char buf[256];
2120 	int len;
2121 	int i;
2122 
2123 	i = -1;
2124 	FOR_EACH_PTR(call->args, arg) {
2125 		i++;
2126 
2127 		name = expr_to_var_sym(arg, &sym);
2128 		if (!name || !sym)
2129 			continue;
2130 		if (sym != param_sym)
2131 			continue;
2132 
2133 		len = strlen(name);
2134 		if (strncmp(name, param_name, len) != 0)
2135 			continue;
2136 		if (param_name[len] == '\0') {
2137 			snprintf(buf, sizeof(buf), "$%d", i);
2138 			return buf;
2139 		}
2140 		if (param_name[len] != '-')
2141 			continue;
2142 		snprintf(buf, sizeof(buf), "$%d%s", i, param_name + len);
2143 		return buf;
2144 	} END_FOR_EACH_PTR(arg);
2145 
2146 	return NULL;
2147 }
2148 
match_call_info(struct expression * expr)2149 static void match_call_info(struct expression *expr)
2150 {
2151 	struct expression *arg;
2152 	struct smatch_state *state;
2153 	struct sm_state *sm;
2154 	struct compare_data *data;
2155 	int comparison;
2156 	struct string_list *links;
2157 	char *arg_name;
2158 	const char *right_name;
2159 	char *link;
2160 	char info_buf[256];
2161 	int i;
2162 
2163 	i = -1;
2164 	FOR_EACH_PTR(expr->args, arg) {
2165 		i++;
2166 
2167 		state = get_state_chunk(link_id, arg);
2168 		if (!state)
2169 			continue;
2170 
2171 		links = state->data;
2172 		FOR_EACH_PTR(links, link) {
2173 			struct var_sym_list *right_vsl;
2174 			struct var_sym *right_vs;
2175 
2176 
2177 			if (strstr(link, " orig"))
2178 				continue;
2179 			sm = get_sm_state(comparison_id, link, NULL);
2180 			if (!sm)
2181 				continue;
2182 			data = sm->state->data;
2183 			if (!data ||
2184 			    data->comparison == UNKNOWN_COMPARISON ||
2185 			    data->comparison == IMPOSSIBLE_COMPARISON)
2186 				continue;
2187 			arg_name = expr_to_var(arg);
2188 			if (!arg_name)
2189 				continue;
2190 
2191 			right_vsl = NULL;
2192 			if (strcmp(data->left_var, arg_name) == 0) {
2193 				comparison = data->comparison;
2194 				right_name = data->right_var;
2195 				right_vsl = data->right_vsl;
2196 			} else if (strcmp(data->right_var, arg_name) == 0) {
2197 				comparison = flip_comparison(data->comparison);
2198 				right_name = data->left_var;
2199 				right_vsl = data->left_vsl;
2200 			}
2201 			if (!right_vsl || ptr_list_size((struct ptr_list *)right_vsl) != 1)
2202 				goto free;
2203 
2204 			right_vs = first_ptr_list((struct ptr_list *)right_vsl);
2205 			if (strcmp(right_vs->var, right_name) != 0)
2206 				goto free;
2207 			right_name = get_printed_param_name(expr, right_vs->var, right_vs->sym);
2208 			if (!right_name)
2209 				goto free;
2210 			snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(comparison), right_name);
2211 			sql_insert_caller_info(expr, PARAM_COMPARE, i, "$", info_buf);
2212 
2213 free:
2214 			free_string(arg_name);
2215 		} END_FOR_EACH_PTR(link);
2216 	} END_FOR_EACH_PTR(arg);
2217 }
2218 
struct_member_callback(struct expression * call,int param,char * printed_name,struct sm_state * link_sm)2219 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *link_sm)
2220 {
2221 	struct sm_state *compare_sm;
2222 	struct string_list *links;
2223 	char *link;
2224 	struct compare_data *data;
2225 	struct var_sym *left, *right;
2226 	static char info_buf[256];
2227 	const char *right_name;
2228 
2229 	if (strstr(printed_name, " orig"))
2230 		return;
2231 
2232 	links = link_sm->state->data;
2233 	FOR_EACH_PTR(links, link) {
2234 		compare_sm = get_sm_state(comparison_id, link, NULL);
2235 		if (!compare_sm)
2236 			continue;
2237 		data = compare_sm->state->data;
2238 		if (!data || !data->comparison)
2239 			continue;
2240 
2241 		if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2242 		    ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2243 			continue;
2244 		left = first_ptr_list((struct ptr_list *)data->left_vsl);
2245 		right = first_ptr_list((struct ptr_list *)data->right_vsl);
2246 		if (left->sym == right->sym &&
2247 		    strcmp(left->var, right->var) == 0)
2248 			continue;
2249 		/*
2250 		 * Both parameters link to this comparison so only
2251 		 * record the first one.
2252 		 */
2253 		if (left->sym != link_sm->sym ||
2254 		    strcmp(left->var, link_sm->name) != 0)
2255 			continue;
2256 
2257 		right_name = get_printed_param_name(call, right->var, right->sym);
2258 		if (!right_name)
2259 			continue;
2260 		snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(data->comparison), right_name);
2261 		sql_insert_caller_info(call, PARAM_COMPARE, param, printed_name, info_buf);
2262 	} END_FOR_EACH_PTR(link);
2263 }
2264 
print_return_value_comparison(int return_id,char * return_ranges,struct expression * expr)2265 static void print_return_value_comparison(int return_id, char *return_ranges, struct expression *expr)
2266 {
2267 	char *name;
2268 	const char *tmp_name;
2269 	struct symbol *sym;
2270 	int param;
2271 	char info_buf[256];
2272 
2273 	/*
2274 	 * TODO: This only prints == comparisons. That's probably the most
2275 	 * useful comparison because == max has lots of implications.  But it
2276 	 * would be good to capture the rest as well.
2277 	 *
2278 	 * This information is already in the DB but it's in the parameter math
2279 	 * bits and it's awkward to use it.  This is is the simpler, possibly
2280 	 * cleaner way, but not necessarily the best, I don't know.
2281 	 */
2282 
2283 	if (!expr)
2284 		return;
2285 	name = expr_to_var_sym(expr, &sym);
2286 	if (!name || !sym)
2287 		goto free;
2288 
2289 	param = get_param_num_from_sym(sym);
2290 	if (param < 0)
2291 		goto free;
2292 	if (param_was_set_var_sym(name, sym))
2293 		goto free;
2294 
2295 	tmp_name = get_param_name_var_sym(name, sym);
2296 	if (!tmp_name)
2297 		goto free;
2298 
2299 	snprintf(info_buf, sizeof(info_buf), "== $%d%s", param, tmp_name + 1);
2300 	sql_insert_return_states(return_id, return_ranges,
2301 				PARAM_COMPARE, -1, "$", info_buf);
2302 free:
2303 	free_string(name);
2304 }
2305 
print_return_comparison(int return_id,char * return_ranges,struct expression * expr)2306 static void print_return_comparison(int return_id, char *return_ranges, struct expression *expr)
2307 {
2308 	struct sm_state *tmp;
2309 	struct string_list *links;
2310 	char *link;
2311 	struct sm_state *sm;
2312 	struct compare_data *data;
2313 	struct var_sym *left, *right;
2314 	int left_param, right_param;
2315 	char left_buf[256];
2316 	char right_buf[256];
2317 	char info_buf[258];
2318 	const char *tmp_name;
2319 
2320 	print_return_value_comparison(return_id, return_ranges, expr);
2321 
2322 	FOR_EACH_MY_SM(link_id, __get_cur_stree(), tmp) {
2323 		if (get_param_num_from_sym(tmp->sym) < 0)
2324 			continue;
2325 		links = tmp->state->data;
2326 		FOR_EACH_PTR(links, link) {
2327 			sm = get_sm_state(comparison_id, link, NULL);
2328 			if (!sm)
2329 				continue;
2330 			data = sm->state->data;
2331 			if (!data ||
2332 			    data->comparison == UNKNOWN_COMPARISON ||
2333 			    data->comparison == IMPOSSIBLE_COMPARISON)
2334 				continue;
2335 			if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2336 			    ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2337 				continue;
2338 			left = first_ptr_list((struct ptr_list *)data->left_vsl);
2339 			right = first_ptr_list((struct ptr_list *)data->right_vsl);
2340 			if (left->sym == right->sym &&
2341 			    strcmp(left->var, right->var) == 0)
2342 				continue;
2343 			/*
2344 			 * Both parameters link to this comparison so only
2345 			 * record the first one.
2346 			 */
2347 			if (left->sym != tmp->sym ||
2348 			    strcmp(left->var, tmp->name) != 0)
2349 				continue;
2350 
2351 			if (strstr(right->var, " orig"))
2352 				continue;
2353 
2354 			left_param = get_param_num_from_sym(left->sym);
2355 			right_param = get_param_num_from_sym(right->sym);
2356 			if (left_param < 0 || right_param < 0)
2357 				continue;
2358 
2359 			tmp_name = get_param_name_var_sym(left->var, left->sym);
2360 			if (!tmp_name)
2361 				continue;
2362 			snprintf(left_buf, sizeof(left_buf), "%s", tmp_name);
2363 
2364 			tmp_name = get_param_name_var_sym(right->var, right->sym);
2365 			if (!tmp_name || tmp_name[0] != '$')
2366 				continue;
2367 			snprintf(right_buf, sizeof(right_buf), "$%d%s", right_param, tmp_name + 1);
2368 
2369 			/*
2370 			 * FIXME: this should reject $ type variables (as
2371 			 * opposed to $->foo type).  Those should come from
2372 			 * smatch_param_compare_limit.c.
2373 			 */
2374 
2375 			snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(data->comparison), right_buf);
2376 			sql_insert_return_states(return_id, return_ranges,
2377 					PARAM_COMPARE, left_param, left_buf, info_buf);
2378 		} END_FOR_EACH_PTR(link);
2379 
2380 	} END_FOR_EACH_SM(tmp);
2381 }
2382 
parse_comparison(char ** value,int * op)2383 static int parse_comparison(char **value, int *op)
2384 {
2385 
2386 	*op = **value;
2387 
2388 	switch (*op) {
2389 	case '<':
2390 		(*value)++;
2391 		if (**value == '=') {
2392 			(*value)++;
2393 			*op = SPECIAL_LTE;
2394 		}
2395 		break;
2396 	case '=':
2397 		(*value)++;
2398 		(*value)++;
2399 		*op = SPECIAL_EQUAL;
2400 		break;
2401 	case '!':
2402 		(*value)++;
2403 		(*value)++;
2404 		*op = SPECIAL_NOTEQUAL;
2405 		break;
2406 	case '>':
2407 		(*value)++;
2408 		if (**value == '=') {
2409 			(*value)++;
2410 			*op = SPECIAL_GTE;
2411 		}
2412 		break;
2413 	default:
2414 		return 0;
2415 	}
2416 
2417 	if (**value != ' ') {
2418 		sm_perror("parsing comparison.  %s", *value);
2419 		return 0;
2420 	}
2421 
2422 	(*value)++;
2423 	return 1;
2424 }
2425 
split_op_param_key(char * value,int * op,int * param,char ** key)2426 static int split_op_param_key(char *value, int *op, int *param, char **key)
2427 {
2428 	static char buf[256];
2429 	char *p;
2430 
2431 	if (!parse_comparison(&value, op))
2432 		return 0;
2433 
2434 	snprintf(buf, sizeof(buf), "%s", value);
2435 
2436 	p = buf;
2437 	if (*p++ != '$')
2438 		return 0;
2439 
2440 	*param = atoi(p);
2441 	if (*param < 0 || *param > 99)
2442 		return 0;
2443 	p++;
2444 	if (*param > 9)
2445 		p++;
2446 	p--;
2447 	*p = '$';
2448 	*key = p;
2449 
2450 	return 1;
2451 }
2452 
db_return_comparison(struct expression * expr,int left_param,char * key,char * value)2453 static void db_return_comparison(struct expression *expr, int left_param, char *key, char *value)
2454 {
2455 	struct expression *left_arg, *right_arg;
2456 	char *left_name = NULL;
2457 	struct symbol *left_sym;
2458 	char *right_name = NULL;
2459 	struct symbol *right_sym;
2460 	int op;
2461 	int right_param;
2462 	char *right_key;
2463 	struct var_sym_list *left_vsl = NULL, *right_vsl = NULL;
2464 
2465 	if (left_param == -1) {
2466 		if (expr->type != EXPR_ASSIGNMENT)
2467 			return;
2468 		left_arg = strip_expr(expr->left);
2469 
2470 		while (expr->type == EXPR_ASSIGNMENT)
2471 			expr = strip_expr(expr->right);
2472 		if (expr->type != EXPR_CALL)
2473 			return;
2474 	} else {
2475 		while (expr->type == EXPR_ASSIGNMENT)
2476 			expr = strip_expr(expr->right);
2477 		if (expr->type != EXPR_CALL)
2478 			return;
2479 
2480 		left_arg = get_argument_from_call_expr(expr->args, left_param);
2481 		if (!left_arg)
2482 			return;
2483 	}
2484 
2485 	if (!split_op_param_key(value, &op, &right_param, &right_key))
2486 		return;
2487 
2488 	right_arg = get_argument_from_call_expr(expr->args, right_param);
2489 	if (!right_arg)
2490 		return;
2491 
2492 	left_name = get_variable_from_key(left_arg, key, &left_sym);
2493 	if (!left_name || !left_sym)
2494 		goto free;
2495 
2496 	right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2497 	if (!right_name || !right_sym)
2498 		goto free;
2499 
2500 	add_var_sym(&left_vsl, left_name, left_sym);
2501 	add_var_sym(&right_vsl, right_name, right_sym);
2502 
2503 	add_comparison_var_sym(NULL, left_name, left_vsl, op, NULL, right_name, right_vsl);
2504 
2505 free:
2506 	free_string(left_name);
2507 	free_string(right_name);
2508 }
2509 
param_compare_limit_is_impossible(struct expression * expr,int left_param,char * left_key,char * value)2510 int param_compare_limit_is_impossible(struct expression *expr, int left_param, char *left_key, char *value)
2511 {
2512 	struct smatch_state *state;
2513 	char *left_name = NULL;
2514 	char *right_name = NULL;
2515 	struct symbol *left_sym, *right_sym;
2516 	struct expression *left_arg, *right_arg;
2517 	int op, state_op;
2518 	int right_param;
2519 	char *right_key;
2520 	int ret = 0;
2521 	char buf[256];
2522 
2523 	while (expr->type == EXPR_ASSIGNMENT)
2524 		expr = strip_expr(expr->right);
2525 	if (expr->type != EXPR_CALL)
2526 		return 0;
2527 
2528 	if (!split_op_param_key(value, &op, &right_param, &right_key))
2529 		return 0;
2530 
2531 	left_arg = get_argument_from_call_expr(expr->args, left_param);
2532 	if (!left_arg)
2533 		return 0;
2534 
2535 	right_arg = get_argument_from_call_expr(expr->args, right_param);
2536 	if (!right_arg)
2537 		return 0;
2538 
2539 	left_name = get_variable_from_key(left_arg, left_key, &left_sym);
2540 	right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2541 	if (!left_name || !right_name)
2542 		goto free;
2543 
2544 	snprintf(buf, sizeof(buf), "%s vs %s", left_name, right_name);
2545 	state = get_state(comparison_id, buf, NULL);
2546 	if (!state)
2547 		goto free;
2548 	state_op = state_to_comparison(state);
2549 	if (!state_op)
2550 		goto free;
2551 
2552 	if (!comparison_intersection(remove_unsigned_from_comparison(state_op), op))
2553 		ret = 1;
2554 free:
2555 	free_string(left_name);
2556 	free_string(right_name);
2557 	return ret;
2558 }
2559 
impossibly_high_comparison(struct expression * expr)2560 int impossibly_high_comparison(struct expression *expr)
2561 {
2562 	struct smatch_state *link_state;
2563 	struct sm_state *sm;
2564 	struct string_list *links;
2565 	char *link;
2566 	struct compare_data *data;
2567 
2568 	link_state = get_state_expr(link_id, expr);
2569 	if (!link_state) {
2570 		if (expr->type == EXPR_BINOP &&
2571 		    (impossibly_high_comparison(expr->left) ||
2572 		     impossibly_high_comparison(expr->right)))
2573 			return 1;
2574 		return 0;
2575 	}
2576 
2577 	links = link_state->data;
2578 	FOR_EACH_PTR(links, link) {
2579 		sm = get_sm_state(comparison_id, link, NULL);
2580 		if (!sm)
2581 			continue;
2582 		data = sm->state->data;
2583 		if (!data)
2584 			continue;
2585 		if (!possibly_true(data->left, data->comparison, data->right))
2586 			return 1;
2587 	} END_FOR_EACH_PTR(link);
2588 
2589 	return 0;
2590 }
2591 
free_data(struct symbol * sym)2592 static void free_data(struct symbol *sym)
2593 {
2594 	if (__inline_fn)
2595 		return;
2596 	clear_compare_data_alloc();
2597 }
2598 
register_comparison(int id)2599 void register_comparison(int id)
2600 {
2601 	comparison_id = id;
2602 	set_dynamic_states(comparison_id);
2603 	add_hook(&save_start_states, AFTER_DEF_HOOK);
2604 	add_unmatched_state_hook(comparison_id, unmatched_comparison);
2605 	add_pre_merge_hook(comparison_id, &pre_merge_hook);
2606 	add_merge_hook(comparison_id, &merge_compare_states);
2607 	add_hook(&free_data, AFTER_FUNC_HOOK);
2608 	add_hook(&match_call_info, FUNCTION_CALL_HOOK);
2609 	add_split_return_callback(&print_return_comparison);
2610 
2611 	select_return_states_hook(PARAM_COMPARE, &db_return_comparison);
2612 	add_hook(&match_preop, OP_HOOK);
2613 }
2614 
register_comparison_late(int id)2615 void register_comparison_late(int id)
2616 {
2617 	add_hook(&match_assign, ASSIGNMENT_HOOK);
2618 }
2619 
register_comparison_links(int id)2620 void register_comparison_links(int id)
2621 {
2622 	link_id = id;
2623 	db_ignore_states(link_id);
2624 	set_dynamic_states(link_id);
2625 	add_merge_hook(link_id, &merge_links);
2626 	add_modification_hook(link_id, &match_modify);
2627 	add_modification_hook_late(link_id, match_inc_dec);
2628 
2629 	add_member_info_callback(link_id, struct_member_callback);
2630 }
2631 
register_comparison_inc_dec(int id)2632 void register_comparison_inc_dec(int id)
2633 {
2634 	inc_dec_id = id;
2635 	add_modification_hook_late(inc_dec_id, &iter_modify);
2636 }
2637 
register_comparison_inc_dec_links(int id)2638 void register_comparison_inc_dec_links(int id)
2639 {
2640 	inc_dec_link_id = id;
2641 	set_dynamic_states(inc_dec_link_id);
2642 	set_up_link_functions(inc_dec_id, inc_dec_link_id);
2643 }
2644 
clone_partial_sm(struct sm_state * sm,int comparison)2645 static struct sm_state *clone_partial_sm(struct sm_state *sm, int comparison)
2646 {
2647 	struct compare_data *data;
2648 	struct sm_state *clone;
2649 	struct stree *stree;
2650 
2651 	data = sm->state->data;
2652 
2653 	clone = clone_sm(sm);
2654 	clone->state = alloc_compare_state(data->left, data->left_var, data->left_vsl,
2655 					   comparison,
2656 					   data->right, data->right_var, data->right_vsl);
2657 	free_slist(&clone->possible);
2658 	add_possible_sm(clone, clone);
2659 
2660 	stree = clone_stree(sm->pool);
2661 	overwrite_sm_state_stree(&stree, clone);
2662 	clone->pool = stree;
2663 
2664 	return clone;
2665 }
2666 
create_fake_history(struct sm_state * sm,int op,struct state_list ** true_stack,struct state_list ** false_stack)2667 static void create_fake_history(struct sm_state *sm, int op,
2668 			       struct state_list **true_stack,
2669 			       struct state_list **false_stack)
2670 {
2671 	struct sm_state *true_sm, *false_sm;
2672 	struct compare_data *data;
2673 	int true_comparison;
2674 	int false_comparison;
2675 
2676 	data = sm->state->data;
2677 
2678 	if (is_merged(sm) || sm->left || sm->right)
2679 		return;
2680 
2681 	true_comparison = comparison_intersection(data->comparison, op);
2682 	false_comparison = comparison_intersection(data->comparison, negate_comparison(op));
2683 
2684 	true_sm = clone_partial_sm(sm, true_comparison);
2685 	false_sm = clone_partial_sm(sm, false_comparison);
2686 
2687 	sm->merged = 1;
2688 	sm->left = true_sm;
2689 	sm->right = false_sm;
2690 
2691 	add_ptr_list(true_stack, true_sm);
2692 	add_ptr_list(false_stack, false_sm);
2693 }
2694 
filter_by_sm(struct sm_state * sm,int op,struct state_list ** true_stack,struct state_list ** false_stack,bool * useful)2695 static void filter_by_sm(struct sm_state *sm, int op,
2696 		       struct state_list **true_stack,
2697 		       struct state_list **false_stack,
2698 		       bool *useful)
2699 {
2700 	struct compare_data *data;
2701 	int is_true = 0;
2702 	int is_false = 0;
2703 
2704 	if (!sm)
2705 		return;
2706 	data = sm->state->data;
2707 	if (!data)
2708 		goto split;
2709 	if (data->comparison == IMPOSSIBLE_COMPARISON)
2710 		return;
2711 
2712 	/*
2713 	 * We want to check that "data->comparison" is totally inside "op".  So
2714 	 * if data->comparison is < and op is <= then that's true.  Or if
2715 	 * data->comparison is == and op is <= then that's true.  But if
2716 	 * data->comparison is <= and op is < than that's neither true nor
2717 	 * false.
2718 	 */
2719 	if (data->comparison == comparison_intersection(data->comparison, op))
2720 		is_true = 1;
2721 	if (data->comparison == comparison_intersection(data->comparison, negate_comparison(op)))
2722 		is_false = 1;
2723 
2724 	if (!is_true && !is_false && !is_merged(sm)) {
2725 		create_fake_history(sm, op, true_stack, false_stack);
2726 		return;
2727 	}
2728 
2729 	if (debug_implied()) {
2730 		sm_msg("%s: %s: op = '%s' negated '%s'. true_intersect = '%s' false_insersect = '%s' sm = '%s'",
2731 		       __func__,
2732 		       sm->state->name,
2733 		       alloc_sname(show_comparison(op)),
2734 		       alloc_sname(show_comparison(negate_comparison(op))),
2735 		       alloc_sname(show_comparison(comparison_intersection(data->comparison, op))),
2736 		       alloc_sname(show_comparison(comparison_intersection(data->comparison, negate_comparison(op)))),
2737 		       show_sm(sm));
2738 	}
2739 
2740 	*useful = true;
2741 	if (is_true)
2742 		add_ptr_list(true_stack, sm);
2743 	if (is_false)
2744 		add_ptr_list(false_stack, sm);
2745 split:
2746 	filter_by_sm(sm->left, op, true_stack, false_stack, useful);
2747 	filter_by_sm(sm->right, op, true_stack, false_stack, useful);
2748 }
2749 
comparison_implication_hook(struct expression * expr,struct state_list ** true_stack,struct state_list ** false_stack)2750 struct sm_state *comparison_implication_hook(struct expression *expr,
2751 					     struct state_list **true_stack,
2752 					     struct state_list **false_stack)
2753 {
2754 	struct sm_state *sm;
2755 	char *left, *right;
2756 	int op;
2757 	static char buf[256];
2758 	bool useful = false;
2759 
2760 	if (expr->type != EXPR_COMPARE)
2761 		return NULL;
2762 
2763 	op = expr->op;
2764 
2765 	left = expr_to_var(expr->left);
2766 	right = expr_to_var(expr->right);
2767 	if (!left || !right) {
2768 		free_string(left);
2769 		free_string(right);
2770 		return NULL;
2771 	}
2772 
2773 	if (strcmp(left, right) > 0) {
2774 		char *tmp = left;
2775 
2776 		left = right;
2777 		right = tmp;
2778 		op = flip_comparison(op);
2779 	}
2780 
2781 	snprintf(buf, sizeof(buf), "%s vs %s", left, right);
2782 	sm = get_sm_state(comparison_id, buf, NULL);
2783 	if (!sm)
2784 		return NULL;
2785 	if (!sm->merged)
2786 		return NULL;
2787 
2788 	filter_by_sm(sm, op, true_stack, false_stack, &useful);
2789 	if (!useful)
2790 		return NULL;
2791 
2792 	if (debug_implied())
2793 		sm_msg("implications from comparison: (%s)", show_sm(sm));
2794 
2795 	return sm;
2796 }
2797